Worksheet 14: Multithreading (Thread Coordination)
Let’s fix the Doggy Manners
The Cat Kingdom captures 5 dogs and locks them up as hostages. The five dogs are given a bowl of dogfood to eat, but they keep fighting over food, barking, biting, chaos everywhere.
Nini is so disgusted by their rudeness: “You dogs have NO manners!”
Nini slams his paw on their doghouse: “Let me teach you some table manner (餐桌禮儀)”
“You want to eat? You need TWO spoons, one in each paw. No grabbing, no fighting!”
The dogs obey. Each grab the spoon to their left.
Now all 5 dogs hold ONE spoon… but need the spoon their neighbor was holding.
Nobody can eat. They just stare at each other, drooling (流口水 …).
“Stupid!” Niko laughs.
“Only 4 of you can sit at the table at once! One must wait outside the doghouse!”
One dog reluctantly leaves. Now with 4 dogs and 5 spoons, they can finally eat properly, taking turns, civilized, no chaos.
Niko: “Wow, the doghouse semaphore works!”
Nini nodded: “Concurrency control separates beasts from civilized beings.”
Video Lecture
Remember to open the English subtitle on Youtube: eLearn link of the video lecture
- In the lecture, “semaphore signal” and “semaphore post” are equivalent.
Readings
The textbook’s example might not be very easy to understand, but I think if you watch the video first, you will quickly understand what the textbook is talking about.
Learning Objectives
I understand the following concepts:
- producer/consumer + bounded buffer
- condition variable: the two operation, when lock is acquired, while v.s if
- a high-level understanding of how condition variable is implemented (also covered in the textbook)
- semaphore: the two operations
- a high-level understanding of how semaphore is implemented (also covered in the textbook)
- compare-and-swap
- how to implement a lock-free linked-list insert function
- the cause of deadlock
- the dining philosopher problem and its two solutions: global ordering and permits (doghouse, or “throttling” in the textbook).