Winter 2000
Homework assignment 3 solutions
The sleeping barber problem can be implemented using a monitor. There are three conditions of interest: the barber is sleeping and a customer arrives, a customer is waiting and the barber starts cutting her hair, and the barber is done cutting hair. Hence, we need three condition variables. In addition, we also need to keep track of whether the barber is busy, and how many chairs are available.
Semaphore Barber =
0;
Semaphore Customers
= 0;
Sempahore Mutex = 1;
int ChairsAvailable
= 3;
void BarberShop()
{
repeat {
//
//
Wait for customers to arrive
//
wait(Customers);
//
//
Update the number of chairs available
wait(Mutex);
ChairsAvailable++;
signal(mutex);
CutHair();
//
//
Signal that the barber is done
//
Signal(Barber);
} until (false);
}
Boolean Customer()
{
Boolean HairWasCut = false;
wait(mutex);
if (ChairsAvailable != 0)
{
ChairsAvailable--;
Signal(Mutex);
//
//
Signal that there is a customer in a chair
//
signal(Customers);
//
//
Wait for a barber to cut my hair
//
wait(Barber);
HairWasCut
= true;
} else {
signal(mutex);
}
return(HairWasCut);
}
Semaphores are a convenient mechanism for implementing this, because they remember what elements are on the table.
Sempahore
TobaccoAndPaper = 0;
Sempahore
PaperAndMatches = 0;
Semaphore
MatchesAndTobacco = 0;
Sempaphore
DoneSmoking = 1;
void agent()
{
wait(DoneSmoking);
int r = rand() % 3;
//
// Signal which ever combination was
// chosen.
//
switch( r ) {
case
0: signal(TobaccoAndPaper);
break;
case
1: signal(PaperAndMatches);
break;
case
2: signal(MatchesAndTobacco);
break;
}
}
void Smoker_A()
{
while(true) {
//
//
Wait for our two ingredients
//
wait(TobaccoAndPaper);
smoke();
//
//
Signal that we’re done smoking
//
so the next agent can put down
//
ingredients.
//
signal(DoneSmoking);
}
}
Smoker b and c are similar.
If a Signal() statement can only be the last statement of a monitor procedure, then the signaling procedure need not wait until the waiting thread completes. Thus, when a thread signals, it is always about to leave the monitor. It may then transfer ownership of the mutex to a waiting thread, so it need not signal the mutex. Instead, it signals the semaphore for the waiting thread and returns.
Thus, the body of the semaphore is now:
wait(mutex)
…
body of F
…
signal(mutex)
The wait operation is now:
x-count = x-count +
1;
signal(mutex)
wait(x-sem)
x-count = x-count –
1;
and the signal operation is now
if (x-count > 0)
signal(x-sem)
else
signal(mutex)
In this case, the signal operation also performs the function of leaving the monitor, which normally would be done by the “end” statement.
To allocate printers, there needs to be a map indicating which printers are available, and a condition variable indicating that the availability of printers has changed. The difficulty here is that the scheduling of the waiters must change. There are three ways to do this:
I’ll show all three solutions. In the first one, the Wait function has been modified to store a priority queue rather than a normal queue.
a. Using a modified condition variable (that support conditional wait, using priority queuing for the waiters) that allows priority in the waiting queue.
type
printer-allocator = monitor;
var PrinterAvailable : condition;
int PrintersAvailable;
Boolean Available[NUM_PRINTERS];
//
// Find a printer in
the bitmap of available printers and return it
//
procedure
FindPrinter() : int
begin
int I;
for (I = 0 to NUM_PRINTERS)
begin
if (Available[I])
begin
Available[I]
= false;
Break;
end
end
PrintersAvailable--;
return(i);
end
//
// Allocate a
printer. If non are available, block until one is available.
//
procedure entry
AllocatePrinter(int Priority) : int
begin
if (PrintersAvailable == 0)
begin
wait(PrinterAvailable,Priority);
end;
return(FindPrinter());
end
//
// Return a printer
that has been allocated. If anybody is waiting
// for a printer,
signal them.
//
procedure entry
ReturnPrinter(int Printer)
begin
Available[Printer] = TRUE;
PrintersAvailable++;
signal(PrinterAvailable);
end
//
// Initialize the
variables, indicating that all the printers are
// available.
begin
PrintersAvailable = NUM_PRINTERS;
For (I = 0 to NUM_PRINTERS)
begin
Available[I]
= true;
end
end
b. Using a condition variable per waiter. In this case, there is an array of condition variables, one for each process. Each caller waits only on its condition variable, and the signaler signals only the process at the head of the priority queue.
type
printer-allocator = monitor;
var PrinterAvailable [NUM_PROCESSES]:
condition;
int PrintersAvailable;
Boolean Available[NUM_PRINTERS];
// The queue holds the condition variables
to signal
PriorityQueue WaitQueue{Condition,};
procedure entry
AllocatePrinter(int ProcessId, int Priority) : int
begin
if (PrintersAvailable == 0)
begin
//
Wait on the condition variable for the callers process
WaitQueue.AddToQueue(PrinterAvailable[ProcessId],
Priority)
wait(PrinterAvailable[ProcessId]);
WaitQueue.RemoveHead();
end;
return(FindPrinter());
end
procedure entry
ReturnPrinter(int Printer)
begin
Available[Printer] = TRUE;
PrintersAvailable++;
// If the wait queue is non-empty, signal
the waiter at the head.
if (!WaitQueue.Empty)
begin
Signal(WaitQueue.Head.Condition);
end
end
// Initialize the
variables.
begin
PrintersAvailable = NUM_PRINTERS;
For (I = 0 to NUM_PRINTERS)
begin
Available[I]
= true;
end
WaitQueue = Empty;
Counter = 0;
end
c. using a single condition variable and an explicit priority queue. In this case, the waiters add themselves to a queue. When woken up, they check to see if they are at the head of the priority queue. If they aren’t, they signal the condition variable and then wait to be signaled again.
type
printer-allocator = monitor
condition PrintersChanged;
Boolean
Available[NUM_PRINTERS];
int
PrintersAvailable;
//
Keep a priority queue of the unique priorities of the
//
callers.
PriorityQueue
WaitQueue{int};
procedure
entry AllocatePrinter(int Priority) : int
begin
// If there aren’t any printers available,
add us
// the queue and wait until a printer becomes
available.
if (PrintersAvailable == 0)
begin
//
Insert us on the queue, with our priority.
WaitQueue.Insert(Priority);
//
Wait until there are printers available and we
// are at the head of the queue. Since
priorities
// are unique, we can wait for the priority
of the
// queue head to be our priority.
wait(PrintersChanged);
While ((WaitQueue.Head != Priority)
begin
// We aren’t at the head, so signal the next
// waiter on the queue.
signal(PrintersChanged);
wait(PrintersChanged);
end
WaitQueue.RemoveHead();
end
retur(FindPrinter());
end
procedure
entry ReturnPrinter(int Printer)
begin
// Set the printer to be available, and
signal
//
that a printer has become ready to allocate
Available[Printer] = TRUE;
PrintersAvailable++;
Signal(PrintersChanged);
end
//
Initialization code
begin
…
end
This can be implemented using a condition variable. Note that after a caller adds its process ID to the count, it will wake up the next waiter if there is any resource left. This is important, because it allows multiple waiters to be woken up when a process with a large ID releases the file.
int count;
Lock Mutex;
Condition Available;
AccessFile(int
ProcessId)
{
Mutex.acquire();
while
(count + ProcessId < n) {
wait(Available);
}
Count += ProcessId;
//
// If there are still resources, wake up
the next waiter
//
if (Count < N) {
signal(Available);
}
Mutex.release();
}
ReleaseFile(int
ProcessId)
{
Mutex.acquire();
Count += ProcessId;
Signal(Available);
Mutex.release();
}
In nonpreemptive scheduling, the operating system will never interrupt a thread that is executing and context switch to another thread. Instead, control of the processor is only given up when the thread explicitly yields or performs another activity that allows the system to context switch, such as making a system call. In preemptive scheduling, the operating system will interrupt executing threads using a timer interrupt as a trigger, and then schedule other threads. Nonpreemptive scheduling is rarely used on multi-user systems, because it allows a single user to monopolize the CPU by never performing operations that would cause it to yield.
Process |
Arrival Time |
Burst Time |
Start Time |
End Time |
Turnaround Time |
P1 |
0.0 |
8 |
0.0 |
8 |
8 |
P2 |
0.4 |
4 |
8 |
12 |
11.6 |
P3 |
1 |
1 |
12 |
13 |
12 |
In this case, the average turnaround time (endtime - arrival time) = 10.53 units
Process |
Arrival Time |
Burst Time |
Start Time |
End Time |
Turnaround Time |
P1 |
0.0 |
8 |
0.0 |
8 |
8 |
P2 |
0.4 |
4 |
9 |
13 |
12.6 |
P3 |
1 |
1 |
8 |
9 |
8 |
The average turnaround time is
9.53 units.
Process |
Arrival Time |
Burst Time |
Start Time |
End Time |
Turnaround Time |
P1 |
0.0 |
8 |
6 |
14 |
14 |
P2 |
0.4 |
4 |
2 |
6 |
5.6 |
P3 |
1 |
1 |
1 |
2 |
1 |
In this case, the average turnaround time is 6.86 units.
These algorithms are related, by setting the parameter from one algorithm to equal the parameter of another.