Due: 4pm on Wednesday, 4/18
Q1. A semaphore is a generalization of a lock. The Python library defines them as follows (see the documentation for threading.Semaphore):
"This is one of the oldest synchronization primitives in the history of computer science, invented by the early Dutch computer scientist Edsger W. Dijkstra (he used the names P() and V() instead of acquire() and release()).
A semaphore manages an internal counter which is decremented by each acquire() call and incremented by each release() call. The counter can never go below zero; when acquire() finds that it is zero, it blocks, waiting until some other thread calls release()."
As a result, if the initial value of the counter is n, up to n processes can acquire the semaphore before one blocks.
Implement a semaphore class, using conditions (type threading.Condition).
Q2. (A CS classic: The Dining Philosophers) Five philosophers sit around a round table, each in front of an endless bowl of rice. Five chopsticks lay on the table, one between each adjacent pair of philosophers. Hence, each philosopher has one chopstick to his/her left and one to his/her right.
At any time, a philosopher may try to:
- Pick up the left chopstick, which must be on the table.
- Pick up the right chopstick, which must be on the table.
- Eat, which requires both left and right chopsticks to be in hand.
- Replace the left chopstick, which requires that it be in hand.
- Replace the right chopstick, which requires that it be in hand.
- Think, which requires an absence of chopsticks.
If all five pick up their left chopstick and then wait for their right, they will all starve. Implement the dine function so that no one starves.
One solution to this problem is described on Wikipedia:
"[Introduce] a waiter at the table. Philosophers must ask his permission before taking up any [chopsticks]. Because the waiter is aware of how many [chopsticks] are in use, he is able to arbitrate and prevent deadlock. When four of the [chopsticks] are in use, the next philosopher to request one has to wait for the waiter's permission, which is not given until a [chopstick] has been released. The logic is kept simple by specifying that philosophers always seek to pick up their left hand [chopstick] before their right hand [chopstick] (or vice versa)."
Implement the run method of the Philosopher thread, as well as the methods of the Waiter class. Feel free to use your Sem class in the solution.
Q3. Given the Stream class presented in Lecture 34, produce a function uniq that takes a stream and returns a stream in which duplicates of any value are filtered out. This should work for infinite streams as well as finite ones.
Q4. [Extra for Experts] It is most likely that your solution to Q2, even though (if correct) it avoids deadlock, can nevertheless allow a philosopher to starve, because his neighbor philosophers can keep beating him to one of his forks. Python does not guarantee that, once I start waiting on a lock, I will acquire it before someone who starts waiting on it after I do. For example, suppose that we have two processes executing:
Process 1: Process 2-3
---------- -----------
aLock.acquire() while True:
doSomething aLock.acquire()
aLock.release() doSomethingElse
aLock.release()
Technically, we could see this sequence of events:
- Process 2 acquires the lock.
- Process 1 attempts to acquire the lock and blocks.
- Process 3 attempts to acquire the lock and blocks.
- Process 2 releases the lock.
- Process 3 acquires the lock.
- Process 2 attempts to acquire the lock and blocks.
- Process 3 releases the lock.
- Process 2 acquires the lock.
- Process 3 attempts to acquire the lock and blocks.
- Process 2 releases the lock.
- etc.
Thus, even if a process that releases a lock always hands it over to some process that is blocked on it (if there is one), that fact alone does not guarantee fairness when there are more than two processes involved.
Try to build a "fair" lock out of "unfair" ones that act as suggested by the event sequence above. Assume that every thread has a unique nonnegative integer id (and knows what it is). Assume also that there is a predetermined maximum value for this integer. Your solution may use threading.Lock, but no other types from the threading module.