This semester, I have the privilege of being a teaching fellow for Harvard’s legendary operating systems class, and I was tasked with writing the synchronization problems for this year’s synchprobs assignment! The goal of these problems is to get students to think carefully about the synchronization primitives and data structures needed to solve highly concurrent problems, avoiding the usual problems that come with concurrency: race conditions, deadlock, starvation, etc.
I remember how fun these problems
were last year (forming little fellowships of the ring and piazza posts,
meant to mimic creating barriers and reader-writer locks), and
I wanted to make sure the problems were just as fun this year.
I was tasked specifically to write problems to mimic the
synchronization one would use to implement
(how would you do it?) and the synchronization needed
between address spaces and the coremap when implementing
a virtual memory system in the third assignment. Given
these specifications, I came up with
Singing Cows and
Hunger Deletion Games synchprobs!
To keep up with the playful spirit of the problems, I
disguised the waitpid/exit problem as a Singing Cows Problem:
a daddy cow must wait until each baby cow finishes
singing “Call Me Maybe” before the daddy cow can congratulate
the baby! The final version of the problem eventually
wait() instead, essentially making the daddy
cow wait until any baby cow finishes singing.
I had just watched Hunger Games: Catching Fire, and this
was my inspiration for the second problem:
Hunger Deletion Games.
In this problem, Katniss and Peeta each have multiple threads
and are attempting to sever mappings between the districts
and the capitol (for the sake of the problem, assume there
NSLOTS districts). These mappings are represented
by a bijection between
capitol slots and district slots. The catch in this problem,
however, is that Katniss and Peeta are concurrently deleting
from opposite sides (Katniss from the capitol side and Peeta
from the district side), so students must avoid
both race conditions (concurrent deletions of the same slot)
and deadlock (concurrent deletions of the same mapping
from opposite sides). This situation mimics the coremap-address
space situation in which threads handling a page fault
need to access a page table entry and then
a coremap entry, while a cleaner thread simultaenously needs
to access a coremap entry and then the corresponding page
table entry. I remember it took me several weeks last year to fully
understand the synchronization needed for this coremap-address space
situation, and I was curious to see what kinds of solutions
students came up with. How would you solve this problem?
To see the source code for the problems and scripts to check the solutions, see the github repo.
The problem statements are shown below. Correct implementations should avoid big lock solutions, and should not allow race conditions, deadlocks, and starvation.
A cow has many children. Each baby cow puts on a performance by singing lyrics to “Call Me Maybe.” Like a good parent, the daddy cow must sit through each one of its baby cow’s performances until the end, in order to say “Congratulations Baby N!” where N corresponds to the N-th baby cow.
At any given moment, there is a single parent cow and possibly multiple baby cows singing. The parent cow is not allowed to congratulate a baby cow until that baby cow has finished singing. Your solution CANNOT wait for ALL the cows to finish before starting to congratulate the babies.
Here is an example of correct looking output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
Hunger Deletion Games
Katniss and Peeta are tired of Hunger Games and want to play a new kind
of game instead, the Deletion Games! They want to sever all ties between
the Capitol and all of its districts (for the sake of this problem, assume
that there are actually
NSLOTS districts). Katniss is severing ties
from the Capitol side, and Peeta is severing ties from the Districts’ side.
There is a 1:1 correspondence between
means that each slot in
capitol_slots has exactly one corresponding entry in
district_slots, and each slot in
district_slots has exactly one corresponding
capitol_slots. More formally:
1 2 3 4 5 6
Katniss and Peeta each will use
NTHREADS to delete these mappings. Katniss
will delete mappings based on randomly generated capitol indices, and Peeta
will delete mappings based on randomly generated district indices.
For example, suppose Katniss randomly chooses capitol index 4 to delete. She looks at capital slot 4, sees that the slot is still mapped, and finds the corresponding district index is 12. Then Katniss will free the mappings in capitol slot 4 and district slot 12.
Suppose Peeta, on the other hand, randomly chooses district index 12 to delete. He looks at district slot 12, sees that the slot is still mapped, and finds the corresponding capitol index is 4. Then Peeta will free the mappings in district slot 12 and capitol slot 4.
However, without proper synchronization, we may get:
- race conditions: if multiple threads attempt to delete the same mappings at the same time
- deadlock: Katniss and Peeta try to delete the (capitol 4, district 12) mappings at the same time starting from opposite sides
- starvation: all the mappings must eventually be deleted
Your solution must satisfy these conditions:
- Avoid race conditions.
- Avoid any unsynchronized reads (reads on a shared variable without holding the mutex for that variable).
- No threads may exit until all the mappings have been deleted.
- Guarantee no deadlock can occur. Your invariants and comments should
provide a convincing proof of this.
HINT: You should insert well-placed
thread_yield()calls in your code to convince yourself of no deadlock.
- When Katniss and Peeta generate random indices to delete, you may decide to IGNORE that index if you wish and move onto the next index. However, all mappings must eventually be deleted. HINT: Use this to your advantage to introduce some asymmetry to the problem.
Here is an example of correct looking output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16