CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Name the model (20 minutes)

Name the model for each: 100 user threads on one kernel thread; every pthread_create gets a kernel thread; 1,000 user threads over 4 kernel threads.

Done when: many-to-one, one-to-one, many-to-many.

Hint

Count how many kernel threads exist for the user threads.

Easy 2: Which flag (20 minutes)

Which clone flag makes two tasks see the same global variables? Which makes them show the same process ID?

Done when: CLONE_VM, and CLONE_THREAD.

Hint

One flag is about memory and one about the thread group.

Easy 3: Predict the time (20 minutes)

Three tasks each call sleep(2). Give the total time with user-level tasks that all block the process, and with three kernel threads.

Done when: about 6 seconds, and about 2 seconds.

Hint

A blocked process runs none of its tasks.

Medium

Medium 1: Run the user-level scheduler (30 minutes)

Compile and run the swapcontext program. Then add a third task and a fourth round, and check the order of the output.

Done when: the lines alternate among three tasks for four rounds, 12 lines in total.

Hint

Make the arrays of contexts three long and loop four times.

Medium 2: Prove the blocking (30 minutes)

Time two user-level tasks that each sleep 1 second, and two pthread threads that do the same. Then replace sleep by a loop of pure computing and time both on one processor with taskset -c 0.

Done when: a table: 2.0 s against 1.0 s for sleeping, and similar times for computing on one processor.

Hint

taskset -c 0 keeps all threads on one processor.

Medium 3: Look at clone (30 minutes)

Run strace -f -e trace=clone,clone3 on a program that creates three threads. Count the calls and list the flags of one.

Done when: three calls, and the flag list including CLONE_THREAD and CLONE_VM.

Hint

Run with 2>&1 | grep -c clone.

Hard

Hard 1: Measure user-level switch cost (60 minutes)

Time a million swapcontext round trips as in the example. Then use strace -c to count how many system calls the program makes. Explain the difference between the per-switch time and the cost of a pure user-level switch.

Done when: a time near 240 ns, a count of about two million rt_sigprocmask calls, and an explanation about the signal mask.

Hint

strace -c -e trace=rt_sigprocmask ./prog.

Hard 2: Parallel speed-up (60 minutes)

Run the spinning program with 1, 2, 3 and 4 threads on your machine, without taskset. Plot or tabulate the elapsed time, and explain where it stops improving.

Done when: a table of four times, and a note that the speed-up ends at the number of processors (nproc).

Hint

nproc gives the number of processors.

Hard 3: Fork or clone by hand (60 minutes)

Use the clone library function to start a task with CLONE_VM | CLONE_FILES and a separate stack. Make it set a global and show the parent sees the change. Then remove CLONE_VM and show the parent does not.

Done when: two outputs showing the global changed and unchanged, with a sentence tying each to the flag.

Hint

Use mmap or malloc for the stack and pass its top, since stacks grow downward.