Transcript Slides - CIS @ Temple University

CIS 5512 - Operating Systems
Synchronization
Professor Qiang Zeng
Fall 2016
Previous class…
• IPC for passing data
– Pipe, FIFO, Message Queue, Shared Memory
• Concepts
– Race condition, critical section, and mutual exclusion
• Mutual exclusion based on busy waiting
– Software-based solutions
– Hardware-assisted solutions
• Synchronization without busy waiting
– Kernel-assisted solutions: semaphore
– Language-assisted solutions: monitor
CIS 5512 – Operating Systems
2
Previous class…
IPC method
Features
Pipes
Can only be used among parent and child
FIFOs
(named pipes)
Can be referred to by a string, so doesn’t
have the limitation above
Compare the following four IPCs for data passing
Message queues Unlike Pipes and FIFOs, they support message
boundary and message types
Shared memory
Data passing doesn’t go through kernel, so it
is usually the most efficient one
CIS 5512 – Operating Systems
3
Previous class…
Can you give an example of race condition?
How to resolve such race condition bugs?
Example 1: counter++;
Example 2: if (account >= 100) account -=100;
Solution: identify critical sections in the program, and
enforce proper synchronization, e.g., mutual exclusion
CIS 5512 – Operating Systems
4
Big picture of synchronization primitives
Software solutions (Dekker’, Bakery, etc.)
Busy-waiting
Hardware-assisted solutions (based on
atomic read-modify-write instructions)
Semaphore: it contains an internal counter
indicating the number of resources.
Binary Semaphore is a special semaphore,
whose counter value can only be 0 or 1; it
can be used as a mutex
Sync.
Primitives
Blocking
Monitor: language-assisted
synchronization; data + procedures + lock
Condition variable: guarded by a lock to
wait on some event
CIS 5512 – Operating Systems
5
Previous class…
What is a Monitor?
Monitor: a language-assisted construct that
encapsulates shared data, procedures, and
synchronization. A monitor has a mutex lock and a
queue. A process has to acquire the lock of before
invoking any of the procedures; if the lock is not
available, the process sleeps at the queue
Compiler automatically inserts lock/unlock operations
upon entry/exit of each monitor procedure
CIS 5512 – Operating Systems
6
Previous class…
What is a Condition Variable? How to use it?
A CV allows a process that has acquired a lock to
relinquish the lock (so that other processes have
chance to progress) and sleeps; the process is waken
up when it is signaled by another process
CIS 5512 – Operating Systems
7
How to use a Condition Variable
Strange_withdraw(x) {
…
pthread_mutex_lock(&m);
while(account < x) // “if” will not work
pthread_cond_wait(&c, &m);
account -= x;
pthread_mutex_unlock(&m);
}
Deposit(y){
pthread_mutex_lock(&m);
account += y;
pthread_cond_signal(&c);
pthread_mutex_unlock(&m);
}
1. Always hold the lock while performing CV
operations
2. Always put the wait operation in a loop (Mesa type)
–
–
In order to check whether the condition is true
Note the the signal(c) only hints the conditions changes;
it does not imply that the condition is definite true
CIS 5512 – Operating Systems
8
Previous class…
“A Condition Variable has to be used with a lock.”
Is this true?
Yes. A CV is used either with an implicit lock (e.g., the
lock of a Monitor) or an explicit lock.
CIS 5512 – Operating Systems
9
Previous class: Semaphore – P() and V()
// Atomic
down(S) { // or, P()
if(S.cnt>0)
S.cnt--;
else
put the current process in queue;
block the current process;
}
// Atomic
up(S) { // or, V()
if(any process is in S’s wait queue)
remove a process from the queue;
resume it;
else
S.cnt++;
}
CIS 5512 – Operating Systems
10
Outline
•
•
•
•
•
Restroom problem
Bar problem
Enforcing execution order
Single-slot producer-consumer problem
Multi-slot producer-consumer problem
Using Semaphores:
The restroom problem and the bar problem
Binary Semaphore for the restroom
problem: mutual exclusion
• Given a single-spot restroom, write the function
for using the restroom
• Hint: Binary Semaphore, a special semaphore,
whose counter value can only be 0 or 1
• Here, Binary Semaphore is used as Mutex, a
blocking lock for enforcing MUTual EXclusion
S = 1; // shared among customers (processes)
use_restroom() {
down(S); // try to enter the restroom; = lock()
Use the restroom //critical section
up(S); // leave the restroom; = unlock()
}
Semaphore for the bar problem
•
•
•
•
Capacity = 100
Many customers try to enter the bar concurrently
Please write code describing the customers
Caution: a Mutex will not work well; why?
S = 100; // shared among processes
// each process does the following
down(S); // try to enter the bar
Have fun;
up(S); // leave the bar
CIS 5512 – Operating Systems
14
Using Semaphores:
Enforcing orders
Semaphore for enforcing order
• Process 0 and Process 1
• How to make sure statement A in Process 0 gets
executed before statement B in Process 1
• Hint: use a semaphore and initialize it as 0
S = 0; // shared
// Process 0
A;
up(S);
// Process 1
down(S);
B;
Semaphore for enforcing order
• Two processes: p0 and p1
• How to enforce the order: p0.A1 -> p1.B1 ->
p1.B2 -> p0.A2
• Hint: use two semaphores
S1 = 0; // shared
S2 = 0; // shared
// Process 0
A1;
up(S1);
down(S2);
A2;
// Process 1
down(S1);
B1;
B2;
up(S2);
CIS 5512 – Operating Systems
17
Using Semaphores:
Single-slot Producer-Consumer problem
Single-slot Producer-Consumer problem
• One slot; multi Producers keep producing items, while
multi Consumers keep consumes items
• Hint:
– Consumer.removeItem() has to occur after Producer.fillSlot()
– Once the slot is filled, Producer.fillSlot() has to occur after
Consumer.removeItem()
S_slot = 1; // shared
S_item = 0; // shared
// Producer
while(true) {
down(S_slot);
fillSlot();
up(S_item);
}
// Consumer
while(true) {
down(S_item);
removeItem();
up(S_slot);
}
CIS 5512 – Operating Systems
19
Using Semaphores:
The Producer-Consumer Problem
Acknowledgement: some slides courtesy of Dr. Brighten Godfrey
Producer-consumer problem
• Chefs cook items and put
them on a conveyer belt
Waiters pick items off the belt
Producer-consumer problem
• Now imagine many
chefs!
...and many waiters!
Producer-consumer problem
• A potential mess!
Producer-consumer problem
Chef (Producer)
Waiter (Consumer)
inserts items
removes items
Shared resource:
bounded buffer
Efficient implementation:
circular fixed-size buffer
Shared buffer
Chef (Producer)
Waiter (Consumer)
Shared buffer
Chef (Producer)
Waiter (Consumer)
insertPtr
removePtr
What does the
chef do with a
new pizza?
Where does the
waiter take a pizza
from?
Shared buffer
Chef (Producer)
Waiter (Consumer)
insertPtr
insertPtr
removePtr
Insert pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
insertPtr
removePtr
Insert pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
insertPtr
removePtr
Insert pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
insertPtr
removePtr
Remove pizza
removePtr
Shared buffer
Chef (Producer)
Waiter (Consumer)
insertPtr
Insert pizza
removePtr
Shared buffer
Chef (Producer)
Insert pizza
Waiter (Consumer)
insertPtr
removePtr
Shared buffer
Chef (Producer)
Waiter (Consumer)
BUFFER FULL:
Producer must
wait!
Insert pizza
insertPtr
removePtr
Shared buffer
Chef (Producer)
Waiter (Consumer)
removePtr
insertPtr
Remove pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
removePtr
insertPtr
Remove pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
removePtr
insertPtr
Remove pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
removePtr
insertPtr
Remove pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
removePtr
insertPtr
Remove pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
removePtr
insertPtr
Remove pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
removePtr
insertPtr
Remove pizza
Shared buffer
Chef (Producer)
Waiter (Consumer)
Buffer empty:
Consumer must be
blocked!
removePtr
Remove pizza
insertPtr
Designing a solution
Chef (Producer)
Waiter (Consumer)
Wait for empty slot
Insert item
Signal item arrival
Wait for item arrival
Remove item
Signal empty slot available
What synchronization do we need?
Designing a solution
Chef (Producer)
Waiter (Consumer)
Wait for empty slot
Insert item
Signal item arrival
Wait for item arrival
Mutex
Remove item
(shared buffer)
Signal empty slot available
What synchronization do we need?
Designing a solution
Chef (Producer)
Waiter (Consumer)
Wait for empty slot
Insert item
Signal item arrival
Wait for item arrival
Semaphore
Remove item
(# empty slots)
Signal empty slot available
What synchronization do we need?
Designing a solution
Chef (Producer)
Waiter (Consumer)
Wait for empty slot
Insert item
Signal item arrival
Wait for item arrival
Semaphore
Remove item
(# filled slots)
Signal empty slot available
What synchronization do we need?
Producer-Consumer Code
buffer[pi] = data;
pi = (pi + 1) % N;
result = buffer[ci];
ci = (ci +1) % N;
Single-slot Producer-Consumer problem
• One slot; multi Producers keep producing items, while
multi Consumers keep consumes items
• Hint:
– Consumer.removeItem() has to occur after Producer.fillSlot()
– Once the slot is filled, Producer.fillSlot() has to occur after
Consumer.removeItem()
S_slot = 1; // shared
S_item = 0; // shared
// Producer
while(true) {
down(S_slot);
fillSlot();
up(S_item);
}
// Consumer
while(true) {
down(S_item);
removeItem();
up(S_slot);
}
CIS 5512 – Operating Systems
47
Producer-Consumer Code
Counting semaphore – check
and decrement the number of
free slots
Counting semaphore – check
and decrement the number of
available items
sem_wait(&slots);
sem_wait(&items);
Block if
there are mutex_lock(&mutex);
no free buffer[pi] = data;
slots
pi = (pi + 1) % N;
mutex_unlock(&mutex);
mutex_lock(&mutex);
result = buffer[ci];
ci = (ci +1) % N;
mutex_unlock(&mutex);
sem_post(&items);
sem_post(&slots);
Done – increment the number
of available items
Done – increment the number
of free slots
Block if
there are
no items
to
take
Implementation based on Monitor and CV
monitor ProducerConsumer
condition cv_full, cv_cempty;
int count;
procedure produce();
{
while (count == N) wait(cv_full);
// if buffer is full, block
put_item(widget);
// put item in buffer
count = count + 1;
// increment count of full slots
if (count == 1) signal(cv_empty); // if buffer was empty, wake consumer
}
procedure consume();
{
while (count == 0) wait(cv_empty);
// if buffer is empty, block
remove_item(widget);
// remove item from buffer
count = count - 1;
// decrement count of full slots
if (count == N-1) signal(cv_full); // if buffer was full, wake producer
}
CIS 5512 – Operating Systems
51
Summary
•
•
•
•
•
Restroom problem
Bar problem
Enforcing execution order
Single-slot producer-consumer problem
Multi-slot producer-consumer problem