kennary island

eat, enjoy, explore

Writing Synchronization Problems for OS161

| Comments

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 waitpid()/exit() (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 mimicked 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 are 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.

Singing Cows

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
...
Baby   1 Cow: Hot night, wind was blowin'
Baby   2 Cow: Ripped jeans, skin was showin'
Baby   4 Cow: Don't ask me, I'll never tell
Baby   5 Cow: And this is crazy
Baby   8 Cow: Hot night, wind was blowin'
Parent   Cow: Congratulations Baby 7!
Baby   1 Cow: And now you're in my way
Baby   2 Cow: And now you're in my way
Baby   4 Cow: Hey, I just met you
Baby   5 Cow: Pennies and dimes for a kiss
Baby   8 Cow: But now you're in my way
Parent   Cow: Congratulations Baby 1!
Baby   2 Cow: Ripped jeans, skin was showin'
Baby   4 Cow: I'd trade my soul for a wish
Baby   8 Cow: Hey, I just met you
Parent   Cow: Congratulations Baby 5!
Baby   2 Cow: Your stare was holdin'
Baby   4 Cow: But now you're in my way
Baby   8 Cow: Don't ask me, I'll never tell
Baby   2 Cow: Your stare was holdin'
Baby   4 Cow: Hot night, wind was blowin'
Baby   8 Cow: But now you're in my way
Baby   2 Cow: Your stare was holdin'
Baby   4 Cow: I'd trade my soul for a wish
Baby   8 Cow: But here's my number
Baby   2 Cow: Ripped jeans, skin was showin'
Baby   4 Cow: But now you're in my way
Baby   8 Cow: But now you're in my way
Parent   Cow: Congratulations Baby 2!
Baby   4 Cow: Your stare was holdin'
Baby   8 Cow: Hey, I just met you
Baby   4 Cow: And this is crazy
Baby   8 Cow: I wasn't looking for this

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 capitol_slots and district_slots. This 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 entry in capitol_slots. More formally:

1
2
3
4
5
6
For all i in {0, 1, 2, ..., NSLOTS - 1},
if capitol_slot[i].is_mapped == true, then
district_slot[capitol_slot[i].district_index].is_mapped == true AND
district_slot[capitol_slot[i].district_index].capitol_index == i

AND similarly if district_slot[i].is_mapped == true.

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
...
{who: katniss, capitol: 86, district: 16, deleted: 114}
{who: katniss, capitol: 108, district: 97, deleted: 115}
{who: peeta, capitol: 89, district: 13, deleted: 116}
{who: katniss, capitol: 103, district: 49, deleted: 117}
{who: katniss, capitol: 5, district: 91, deleted: 118}
{who: peeta, capitol: 57, district: 44, deleted: 119}
{who: katniss, capitol: 39, district: 81, deleted: 120}
{who: katniss, capitol: 55, district: 96, deleted: 121}
{who: peeta, capitol: 101, district: 64, deleted: 122}
{who: katniss, capitol: 44, district: 58, deleted: 123}
{who: katniss, capitol: 59, district: 78, deleted: 124}
{who: katniss, capitol: 80, district: 85, deleted: 125}
{who: katniss, capitol: 122, district: 88, deleted: 126}
{who: katniss, capitol: 67, district: 114, deleted: 127}
{who: katniss, capitol: 61, district: 17, deleted: 128}

Comments