| << Chapter < Page | Chapter >> Page > |
What is wrong with this code?
Multiprocessor solution:
Step 1: when P fails, put process to sleep; on V just wake up everybody, processes all try P again.
Step 2: label each process with semaphore it's waiting for, then just wakeup relevant processes.
Step 3: just wakeup a single process.
Step 4: add a queue of waiting processes to the semaphore. On failed P, add to queue. On V, remove from queue.
Why can we get away with only removing one process from queue at a time?
There are several tradeoffs implicit here: how many processes in the system, how much queuing on semaphores, storage requirements,etc. The most important thing is to avoid busy-waiting.
Is it "busy-waiting" if we use the solution in step 1 above?
What do we do in a multiprocessor to implement P's and V's? Cannot just turn off interrupts to get low-level mutual exclusion.
In a multiprocessor, there must be busy-waiting at some level: cannot go to sleep if do not have mutual exclusion.
Most machines provide some sort of atomic read- modify-write instruction. Read existing value, store back in one atomicoperation.
Using test and set for mutual exclusion: It is like a binary semaphore in reverse, except that it does not include waiting. 1 meanssomeone else is already using it, 0 means it is OK to proceed. Definition of test and set prevents two processes from getting a 0->1 transition simultaneously.
Test and set is tricky to use. Using test and set to implement semaphores: For each semaphore, keep a test-and-set integer inaddition to the semaphore integer and the queue of waiting processes.
class semaphore {
private int t;private int count;
private queue q;public semaphore(int init)
{t = 0;
count = init;q = new queue();
}public void P()
{Disable interrupts;
while (TAS(t) != 0) { /* just spin */ };if (count>0) {
count--;t = 0;
Enable interrupts;return;
}Add process to q;
t = 0;Enable interrupts;
Redispatch;}
public V(){
Disable interrupts;while (TAS(t) != 0) { /* just spin */ };
if (q == empty) {count++;
} else {Remove first process from q;
Wake it up;}
t = 0;Enable interrupts;
}}
Why do we still have to disable interrupts in addition to using test and set?
Important point: implement some mechanism once, very carefully. Then always write programs that use that mechanism. Layering is veryimportant.
Remark: Whereas we use the term semaphore to mean binary semaphore and explicitly say generalized or countingsemaphore for the positive integer version, Tanenbaum uses semaphore for the positive integer solution and mutex for the binary version. Also, as indicatedabove, for Tanenbaum semaphore/mutex implies a blocking primitive; whereas I use binary/counting semaphore for both busy-waiting and blocking implementations.Finally, remember that in this course we are studying only busy-waiting solutions.
Notification Switch
Would you like to follow the 'Operating systems' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|