CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: Read the signature (20 minutes)

Write the start function type that pthread_create expects, and name what each of the two void * stands for.

Done when: void *f(void *), argument in, result out.

Hint

The argument goes in as void *, and the result comes back as void *.

Easy 2: Hand-check the sums (20 minutes)

An array holds the numbers 1 to 100 and 4 threads each add a quarter. Give the four partial sums and the total.

Done when: 325, 950, 1575 and 2200, adding to 5050.

Hint

The quarters are 1 to 25, 26 to 50, 51 to 75 and 76 to 100.

Easy 3: Predict the end (20 minutes)

A program starts a thread that prints after 1 second, then main returns at once. What is printed, and what changes if main calls pthread_exit(NULL) instead?

Done when: nothing in the first case, and the thread's message in the second.

Hint

Returning from main calls exit.

Medium

Medium 1: Return a value (30 minutes)

Write a thread that computes the factorial of 10 and returns it through the join. Print the result.

Done when: the output is 3628800, and the allocated result is freed.

Hint

Allocate the result with malloc.

Medium 2: Fix the loop bug (30 minutes)

Run the program that passes &i. Then fix it three ways: an array of values, a struct, and a value cast to void *. Check that each prints 0, 1 and 2 in some order.

Done when: three fixed versions with correct output.

Hint

(void *)(long)i passes the value itself.

Medium 3: Parallel sum (30 minutes)

Change the array program to use 1, 2, 4 and 8 threads. Time each with clock_gettime, and check the total is always 4,500,000.

Done when: a table of four timings and the same total in each row.

Hint

The static array makes the sum identical in every run.

Hard

Hard 1: Uneven split (60 minutes)

Make the sum program work for any N, such as 1,000,003, and any number of threads, so the last thread takes the remainder. Test with 7 threads.

Done when: the total equals a single-threaded sum for three different values of N.

Hint

The last range ends at N, not at (k + 1) * (N / NT).

Hard 2: Thread limit (60 minutes)

Write a program that creates detached threads that each sleep for 10 seconds until pthread_create fails. Print how many were created and the error text. Compare with ulimit -u.

Done when: a count, an error such as "Resource temporarily unavailable", and a sentence relating them to the limit.

Hint

Detached threads give up their stacks as soon as they end, so make them sleep.

Hard 3: Parallel search (60 minutes)

Search a 10-million-element array for a value using 4 threads, where each thread stops early if another has found it. Use a shared volatile int found flag that only the finder sets, and report the index.

Done when: the right index is printed, and the search ends sooner when the value is near the start.

Hint

Only the finder writes the flag, so no two threads write it.