CSE 451

Winter 2000

Homework assignment 3 solutions

6.7 Sleeping Barber

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);

}

6.8 Cigarette Smokers

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.

6.12 Simplified Semaphores

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.

6.13

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:

Create a new kind of condition variable in which the Wait() operation takes a priority for scheduling
Create a condition variable for each possible client
Wake several of the waiters, and allow them to coordinate who goes next.

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

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

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

// 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

6.14

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();

}

5.2 Preemptive vs. Nonpreemptive Scheduling

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.

5.4

In first-come, first-server scheduling, the schedule of execution is as follows:

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

With shortest job first, the schedule is as follows:

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.

With modified shortest job first, the schedule is as follows:

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.

5.8

These algorithms are related, by setting the parameter from one algorithm to equal the parameter of another.

Priority scheduling is the same as shortest job first, when the priority is equal to the job length.
Multilevel feedback queues may include first-come, first-serve, as a scheduling policy for one level.
First-come, first-serve, is equivalent to priority scheduling with only one priority level.
If round robin is used with a very short time quantum, then the finishing time for threads is the same as shortest job first, as no job will be able to finish in just one quanta.