Concurrency: Mutual Exclusion and Synchronization
Concurrency: Mutual Exclusion and Synchronization
Concurrency: Mutual Exclusion and Synchronization
Mutual Exclusion
and Synchronization
Chapter 5
Critical Sections & Mutual Exclusion
balance
Mutual exclusion Only one process can be in the critical section at a time
Without mutual exclusion, results of multiple execution are not consistent
We only want to prevent p1 and p2 from interfering with one another; this
prevents any other process pk to execute
void get(semaphore s)
get( ) P( ) wait( )
disable_interrupts();
{ s.count--;
if (s.count < 0) pthread_mutex_lock()
{place this process in s.queue;
block this process
}
enable_interrupts();
}
void release(semaphore s)
{disable_interrupts();
s.count++; release( ) V( ) signal( )
if (s.count <= 0)
{ remove a process P from s.queue; pthread_mutex_unlock()
place process P on ready queue;
}
enable_interrupts();
}
Another Possible Semaphore Implementation
Using Compare&Swap (Test&Set) instruction
semWait(s) semWait(s)
{ {
while (compare_and_swap(s.flag, 0 , 1) == 1) inhibi
/* do nothing */; s.coun
s.count--; if (s.
if (s.count < 0) { /*
/* place this process in s.queue*/; /*
/* block this process (must also set s.flag to 0) }
*/; else
} all
s.flag = 0; }
}
semSignal(
semSignal(s) {
{ inhibi
while (compare_and_swap(s.flag, 0 , 1) == 1) s.coun
/* do nothing */; if (s.
s.count++; /*
if (s.count <= 0) { /*
/* remove a process P from s.queue */; }
/* place process P on ready list */; allow
} }
s.flag = 0;
}
Dijkstras Semaphore
Invented in the 1960s
P0() P1()
{ {
. . . . . .
/* Enter the CS */ /* Enter the CS */
P(mutex); P(mutex);
balance += amount; balance -= amount;
V(mutex); V(mutex);
. . . . . .
} }
semaphore mutex = 1;
pthread_create(P0, 0);
pthread_create(P1, 0);
Important considerations for software locks
A is done!
What is going to happen now?
Processing Two Critical Sections
shared lock1 = FALSE; shared lock1 = FALSE;
shared lock2 = FALSE; shared lock2 = FALSE;
. . . . . .
Deadlock may occur
if locks are not used properly!
shared boolean lock1 = FALSE;
shared boolean lock2 = FALSE;
. . . . . .
get(lock1); get(lock2);
get(lock2); get(lock1);
<update length>; <add element>;
release(lock2); releaselock1);
release(lock1); release(lock2);
. . . . . .
OS concerns related to concurrency
Deadlock
synchronization communication
to enforce mutual to exchange information
exclusion
Producer: Consumer:
while (true) { while (true) {
/* produce item v */ while (in <= out) /* wait
*/;
b[in] = v;
w = b[out];
in++; out++;
}
/* consume item w */
}
Infinite Buffer
Producer: Consumer:
Bounded Buffer
EmptyPool
Producer Consumer
Producer Consumer
Producer
FullPool
Readers-Writers Problem
Reader Writer
Reader Writer
Reader Writer
Reader Writer
Reader Writer
Reader Writer
Reader Writer
Reader
Shared Resource
Readers-Writers Problem
Writer
Writer
Writer
Writer
Writer
Writer
Writer
Reader
Reader
Reader
Reader
Reader
Reader
Reader
Reader
Shared Resource
Readers-Writers Problem
Reader Writer
Reader Writer
Reader Writer
Reader Writer
Reader Writer
Reader Writer
Reader
Reader
Writer
Shared Resource
First Solution
reader() {
while(TRUE) {
<other computing>;
writer() {
while(TRUE) {
P(mutex);
<other computing>;
readCount++;
P(writeBlock);
if(readCount == 1)
/* Critical section */
P(writeBlock);
access(resource);
V(mutex);
V(writeBlock);
/* Critical section */
}
access(resource);
}
P(mutex);
readCount--;
if(readCount == 0)
V(writeBlock);
V(mutex); First reader competes with writers
} Last reader signals writers
}
resourceType *resource;
int readCount = 0;
semaphore mutex = 1;
semaphore writeBlock = 1;
First Solution
reader() { writer() {
while(TRUE) { while(TRUE) {
<other computing>; 5 <other computing>;
P(mutex); 2 P(writeBlock);
readCount++; /* Critical section */
if(readCount == 1) access(resource);
P(writeBlock); V(writeBlock);
V(mutex); }
4 /* Critical section */ }
3 access(resource);
1
P(mutex);
readCount--;
if(readCount == 0)
V(writeBlock); First reader competes with writers
}
V(mutex);
Last reader signals writers
} Any writer must wait for all readers
Readers can starve writers
resourceType *resource; Updates can be delayed forever
int readCount = 0;
semaphore mutex = 1;
not desirable!
semaphore writeBlock = 1;
Writers Take Precedence
reader() {
while(TRUE) {
<other computing>; writer() {
5 while(TRUE) {
4 P(readBlock); <other computing>;
P(mutex1); P(mutex2);
2 readCount++; writeCount++;
if(readCount == 1) if(writeCount == 1)
P(writeBlock); 3 P(readBlock);
V(mutex1); V(mutex2);
V(readBlock); P(writeBlock);
access(resource);
1 access(resource); V(writeBlock);
P(mutex1); P(mutex2)
readCount--; writeCount--;
if(readCount == 0) if(writeCount == 0)
V(writeBlock); V(readBlock);
V(mutex1); V(mutex2);
} }
} }
int readCount=0, writeCount=0;
semaphore mutex1=1, mutex2=1;
Semaphore readBlock=1,writeBlock=1
Writers Take Precedence
reader() {
while(TRUE) { writer() {
<other computing>; while(TRUE) {
5 <other computing>;
4 P(readBlock); P(mutex2);
P(mutex1); writeCount++;
readCount++; if(writeCount == 1)
if(readCount == 1) P(readBlock);
P(writeBlock); V(mutex2);
V(mutex1); 3 P(writeBlock);
V(readBlock); access(resource);
2 V(writeBlock);
1 access(resource); P(mutex2)
P(mutex1); writeCount--;
readCount--; if(writeCount == 0)
if(readCount == 0) V(readBlock);
V(writeBlock); V(mutex2);
V(mutex1); }
} }
}
No philosopher must
starve to death (avoid
deadlock and starvation)
P0
P4
P2
P3 P1
P0
P4
/* program diningphilosophers */
Figure 6.11 Dining Arrangement for Philosophers semaphore fork [5] = {1};
int i;
void philosopher (int i)
{
while (true) {
think();
wait (fork[i]);
Anything wrong with this code? wait (fork [(i+1) mod 5]);
eat();
signal(fork [(i+1) mod 5]);
signal(fork[i]);
}
}
void main()
Dining Philosophers
/* program diningphilosophers */
semaphore fork [5] = {1};
int i;
void philosopher (int i)
{
while (true) {
think();
wait (fork[i]);
wait (fork [(i+1) mod 5]);
eat();
signal(fork [(i+1) mod 5]);
signal(fork[i]);
}
}
void main()
{
parbegin (philosopher (0), philosopher (1)
(2),
philosopher (3), philosopher (4));
}
A Second Solution to the Dining Philosophers Problem
/* program diningphilosophers */
semaphore fork[5] = {1};
semaphore room = {4};
int i;
void philosopher (int i)
{
while (true) {
think();
wait (room);
wait (fork[i]);
wait (fork [(i+1) mod 5]);
eat();
signal (fork [(i+1) mod 5]);
signal (fork[i]);
signal (room);
}
}
void main()
{
parbegin (philosopher (0), philosopher (1), philosopher (2),
philosopher (3), philosopher (4));
}
The Barbershop Problem
semaphore max_capacity = 20, sofa = 4, barber_chair = 3, coord = 3;
semaphore cust_ready = 0, finished = 0, leave_b_chair = 0, payment= 0, receipt = 0;
void customer ()
{
wait(max_capacity);
enter_shop();
wait(sofa);
sit_on_sofa();
wait(barber_chair);
get_up_from_sofa();
signal(sofa); void barber()
sit_in_barber_chair; {
signal(cust_ready); while (true)
wait(finished); {
leave_barber_chair();
wait(cust_ready);
signal(leave_b_chair);
wait(coord);
pay();
signal(payment);
cut_hair();
wait(receipt); signal(coord);
exit_shop(); signal(finished);
signal(max_capacity) wait(leave_b_chair);
} signal(barber_chair);
}
}
The Barbershop (cont.)
void cashier()
{
while (true)
{
wait(payment);
wait(coord);
accept_pay();
signal(coord);
signal(receipt);
}
}
void main()
{
parbegin (customer, . . . 50 times . . . customer,
barber, barber, barber, cashier);
}