1.
Bounded-Buffer Problem ( in producer – consumer
program)
The code for producer process
While(true)
{
// produce an item in //nextProduced
while(counter==BUFFER_SIZE)
; //do-nothing
Buffer[in]=nextProduced;
In=(in+1)%BUFFER_SIZE;
Counter++;
}
Structure of Producer Process
Do{
.
. .
//produce
an item in nextP
.
. .
Wait(empty);
Wait(mutex);
.
. .
//add
nextP to buffer
.
. .
Signal(mutex);
Signal(full);
}while(TRUE);
The code for Consumer Process
While(true)
{
While(counter==0)
; // do- nothing
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
counter--;
//consume the
item in //nextConsumed
}
Structure
of Consumer Process
Do
{
Wait(full);
Wait(mutex);
. . .
//remove an item
from buffer to nextC
. . .
Signal(mutex);
Signal(empty);
. . .
//consume the
item nextC
. . .
}while(TRUE);
Note:-
·
Pool of ‘n’ buffers, each capable of holding one
item.
·
“mutex” semaphore provides MUTUAL
EXCLUSION.
·
“empty” &
“full” semaphores – count number of empty and full buffers.
·
Initialization
o Empty=n
o Full=0
2.
Readers – Writers Problem
·
Database is to
be shared among several concurrent processes.
·
Readers – read
the database
·
Writers – write
to database
·
No problem –
when multiple Readers tries to simultaneously access shared data.
·
Chaos – When a
writer and some other process (Reader/Writer) access the database
simultaneously.
·
Writers require
exclusive access to database while writing to database. This synchronization
problem is referred as “Readers – Writers Problem”.
·
Several
variations
o First Readers – Writers Problem ( Simplest)
o Second Readers – Writers Problem
·
First Readers – Writers Problem
o No reader be kept waiting unless a writer has
already obtained permission to use the shared object.
(or)
No Reader should wait for other readers
to finish simply because a writer is waiting.
o Solution to this problem may result starvation
(Writer).
·
Second Readers – Writers Problem
o Once a Writer is Ready, that Writer perform its
write operation as soon as possible.
(or)
If a Writer is waiting to access the
object, no new readers may start reading.
o Solution to this problem may result starvation
(Reader).
·
Solution to the First Readers – Writers Problem
o Reader process Data Structures
§ Semaphore mutex, wrt;//initialized to 1
int readcount;//initialized to 0
§ ‘wrt’ Semaphore
·
Common to both
Reader & Writer Processes.
·
Functions as mutual-exclusion
semaphore for Writers.
·
Used by first or
last Reader that enters or exits the critical section.
·
Not used by
Readers while entering or exiting the critical-section.
§ Mutex Semaphore
·
Used to ensure
Mutual-Exclusion when ‘readcount’ is updated.
§ ‘Readcount’ – counts no. of processes currently
reading the object.
·
Structure of Writers Process
Do{
Wait(wrt);
.
. .
//writing is performed
.
. .
Signal(wrt);
}while(TRUE);
·
Structure of Readers Process
Do{
Wait(mutex);
Readcount++;
If(readcount==1)
Wait(wrt);
Signal(mutex);
. . .
//reading is
performed
. . .
Wait(mutex);
Readcount--;
If(readcount==0)
Signal(wrt);
Signal(mutex);
}while(TRUE);
·
If a Writer is
in critical section and ‘n’ readers are waiting, then one reader is queued on
‘wrt’, and (n-1) readers are queued on ‘mutex’.
·
When a Writer
executes ‘signal(wrt)’, then we may resume the execution of either waiting
readers or single waiting writer.(Scheduler will select)
·
Generalized Form
o Reader – Writer Lock is maintained.
o In order to acquire the lock, mode of access is to
be mentioned i.e., read mode / write mode.
o Multiple processes can obtain READ MODE at once, but
only one process to get WRITE MODE .
o These LOCKs are useful when
§ We identify processes that read shared data and
processes that write data.
§ In applications which has more Readers than Writers.
3.
Dining Philosopher’s Problem
·
Philosophers
spend their lives thinking and eating
·
They do not
interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time, on either side) to eat from bowl
§ Need both
chopsticks to eat
§ Cannot pick up a
chopstick that is already in the hand of neighbor.
§ Put back in
their place both chopsticks when done eating
·
Shared data
for 5 philosophers
o Bowl of rice (data set)
o Semaphore
chopstick[5] initialized to 1
·
One simple solution – Represent each chopstick with a semaphore
·
Wait() – To grab
a chopstick by a philosopher
·
Signal() – To release
chopstick
·
The structure of
Philosopher i :
do {
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
//
eat
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
//
think
} while (TRUE);
·
Deadlock – when all
philosophers want to eat at once by picking their right side chopstick.
·
Several Possible
remedies to deadlock problem
o Allow atmost
4 philosophers to sit simultaneously
o Allow to pick
both only when both are available
o Odd philosophers
– first right & then left
Even Philosopher
– first left & then right
·
Satisfactory
Solution – stop possibility of one philosopher starvation
·
Deadlock-free
solution may not necessarily eliminate starvation.
