ZimmerCSCI38012/12/2018
BUSY WAITS
Example of two cooperating processes:
void Proc_0 (void)
{
// initial code
enter_region ( 0 );
// critical section
leave_region (0 );
// remaining code
}
void Proc_1 (void)
{
// initial code
enter_region ( 1 );
// critical section
leave_region (1 );
// remaining code
}
Attempt 1 -
shared int turn= 0;
void enter_region (int proc)
{
while (turn != proc) ; //busy wait
}
void leave_region (int proc)
{
turn = 1-proc // other process
}
Attempt 2 -
shared int flag[2] = {FALSE, FALSE};
void enter_region (int proc)
{
int other = 1- proc;
while (flag[other] == TRUE) ; //busy wait
flag[proc] = TRUE;
}
void leave_region (int proc)
{
flag[proc] = FALSE;
}
Attempt 3 -
shared int flag[2] = {FALSE, FALSE};
void enter_region (int proc)
{
int other = 1-proc;
flag[proc] = TRUE;
while (flag[other] == TRUE) ; //busy wait
}
void leave_region (int proc)
{
flag[proc] = FALSE;
}
Attempt 4 -
shared int flag[2] = {FALSE, FALSE};
void enter_region (int proc)
{
int other = 1- proc;
flag[proc] = TRUE;
while (flag[other] == TRUE)
{
flag[proc] = FALSE;
//busy wait for a random short time
flag[proc] = TRUE;
}
}
void leave_region (int proc)
{
flag[proc] = FALSE;
}
Attempt 5 -
shared int flag[2] = {FALSE, FALSE};
shared int turn = 0;
void enter_region (int proc)
{
int other = 1- proc;
flag[proc] = TRUE;
while (flag[other] == TRUE)
{
if (turn == other)
{
flag[proc] = FALSE;
while (turn == other); //busy wait
flag[proc] = TRUE;
}
}
}
void leave_region (int proc)
{
turn = 1 - proc;// other process
flag[proc] = FALSE;
}
Attempt 6 -
shared int flag[2] = {FALSE, FALSE};
shared int turn = 0;
void enter_region (int proc)
{
int other = 1- proc;
flag[proc] = TRUE;
turn = other;
while (flag[other] == TRUE) & (turn == other)) ; // busy wait
}
void leave_region (int proc)
{
flag[proc] = FALSE;
}
Semaphores
System calls:
void Signal(semaphore &s)void Wait(semaphore &s)
{{
if (a process is blocked on s)if (s == 0)
wakeup_proc(s);block_proc(s);
elseelse
s = s + 1;s = s-1;
}}
Mutual Exclusion Example:
shared semaphore mutex = 1;
void Proc_0(void)void Proc_1(void)
{{
// initial code// initial code
Wait(mutex);Wait(mutex);
// critical section// critical section
Signal(mutex);Signal(mutex);
// remaining code// remaining code
}}
Producer-Consumer Example:
#define N 100
shared semaphore mutex = 1;
shared semaphore empty = N;// indicates number of slots empty
shared semaphore full = 0;// indicates number of slots full
void Producer (void)void Consumer(void)
{{
int item;int item;
while (TRUE)while(TRUE)
{{
produce_item(item);Wait(full);
Wait(empty);Wait(mutex);
Wait(mutex);remove_item(item);
enter_item(item);Signal(mutex);
Signal(mutex);Signal(empty);
Signal(full);consume_item(item);
}}
}}
The Dining Philosophers Problem:
Five philosophers spend their life thinking and eating. They share a common table with five chairs. In the center of the table is a bowl of pasta and there are five forks (one between each philosopher). A philosopher needs two forks to eat without making a mess. When a philosopher gets hungry she tries to pick up her left then her right fork, if successful she eats, then sets down the forks and thinks some more.
Attempt 1 -
shared semaphore fork[5] = {1,1,1,1,1};
void philosopher(int i)
{
while (TRUE)
{
think();
Wait(fork[i]);
Wait(fork[(i+1)%5]);
eat();
Signal(fork[(i+1)%5]);
Signal(fork[i]);
}
}
Attempt 2 -
shared semaphore room = 4;// only allow 4 philosophers into the room to eat at a time.
shared semaphore fork[5] = {1,1,1,1,1};
void philosopher(int i)
{
while (TRUE)
{
think();
Wait(room);
Wait(fork[i]);
Wait(fork[(i+1)%5]);
eat();
Signal(fork[(i+1)%5]);
Signal(fork[i]);
Signal(room);
}
}
Monitors
Simple Resource Allocation Example:
monitor ResourceAllocator
{
bool ResourceInUse = FALSE;
condition ResourceIsFree;
void GetResource(void)
{
if (ResourceInUse)
wait(ResourceIsFree);
ResourceInUse = TRUE;
}
void ReturnResource(void)
{
ResourceInUse = FALSE;
signal(ResourceIsFree);
}
}
Readers and Writers Problem:
A data object is to be shared among several processes. Some processes want to read the contents of the shared object (readers), and others want to update (read and write) the shared object (writers).
monitor ReadersAndWriters
{
int readers = 0;
bool SomeOneIsWriting = FALSE;
condition ReadingAllowed, WritingAllowed;
void BeginReading(void)
{
if ((SomeOneIsWriting) || queue(WritingAllowed))
wait(ReadingAllowed);
readers++;
signal(ReadingAllowed);
}
void FinishReading(void)
{
readers--;
if (readers == 0)
signal(WritingAllowed);
}
void BeginWriting(void)
{
if ((readers > 0) || (SomeOneIsWriting))
wait(WritingAllowed);
SomeOneIsWriting = TRUE;
}
void FinishWriting(void)
{
SomeOneIsWriting = FALSE;
if ( queue(ReadingAllowed))
signal(ReadingAllowed);// precedence given to readers
else
signal(WritingAllowed);
}
}
Message Passing
Consumer - Producer Example:
void Producer (void)void Consumer(void)
{{
int item;int item;
while (TRUE)while(TRUE)
{{
produce_item(item);receive(producer, item)
send(consumer, item);consume_item(item);
}}
}}
1