Transcript Lecture OS - University of Wisconsin

Computer Architecture and
Operating Systems
CS 3230: Operating System Section
Lecture OS-5
Process Synchronization
Department of Computer Science and Software Engineering
University of Wisconsin-Platteville
Outlines
 Critical Section Problem
 Mutual Exclusion
 Mutual Exclusion Algorithms
 Synchronization Hardware
 Semaphores
Critical Section Problem
 n processes all competing to use some shared data
 Each process has a code segment, called critical
section, in which the shared data is accessed.
 Mutual Exclusion (MX) – ensure that when one
process is executing in its critical section, no
other process is allowed to execute in its critical
section

MX – basic synchronization problem
MX: Hardware Support 1
 A process runs until it invokes an operating-system
service or until it is interrupted

Interrupt Problem: MX violation
 Hardware Solution:
 Single Processor:
• Interrupt Disabling
– Processor is limited in its ability to interleave programs
• Disabling interrupts guarantees mutual exclusion

Multiprocessor:
• disabling interrupts will not guarantee mutual exclusion
MX: General Solution
 There is a set of threads/processes that switch
between executing the critical section (CS) of
code and non-critical section
 Before entering the CS, a thread/process
requests it
 MX Solution requirement:


safety – at most one thread at a time execute the CS
liveness – a thread requesting the CS is given a chance to
enter it
• Liveness violation: starvation – a requesting thread is not
allowed to enter the CS
– deadlock – all threads are blocked and cannot proceed
– livelock – threads continue to operate but none could
enter the CS
MX: Process Structure
 General structure of process Pi
MX: Algorithm 1
P1 ( )
{
while (true)
{
while (turn != 1)
;
/* do nothing */
CS
turn = 2;
non-CS
}
}
P2 ( )
{
while (true)
{
while (turn != 2)
; /* do nothing */
CS
turn = 1;
non-CS
}
}
 Pre condition: only two
processes/threads in
the system
 Shared variables:
 int turn;
 OS sets turn to an
initial value (1 or 2)
 Advantages:
 Safety
 Problems:
 Violates liveness
MX: Algorithm 2a
P1 ( ) {
while (true) {
while (P2_in_CS == true)
;
/* do nothing */
P1_in_CS = true;
CS
P1_in_CS = false;
non-CS
}
}
P2 ( ) {
while (true) {
while (P1_in_CS == true)
;
/* do nothing */
P2_in_CS = true;
CS
P2_in_CS = false;
non-CS
}
}
 Pre condition: only two
processes/threads in
the system
 Shared variables:
 Boolean variables
• P1_in_CS
• P2_in_CS
• Boolean variables
initially false
 Advantages:
liveness
 Problems:
 Violates Safety

MX: Algorithm 2b
P1 ( ) {
while (true) {
P1_in_CS = true;
while (P2_in_CS == true)
;
/* do nothing */
CS
P1_in_CS = false;
non-CS
}
}
P2 ( ) {
while (true) {
P2_in_CS = true;
while (P1_in_CS == true)
;
/* do nothing */
CS
P2_in_CS = false;
non-CS
}
}
 Pre condition: only two
processes/threads in
the system
 Shared variables:
 Boolean variables
• P1_in_CS
• P2_in_CS
• Boolean variables
initially false
 Advantages:
Safety
 Problems:
 Violates liveness

MX: Algorithm 3 (Peterson’s)
P1 ( ) {
while (true) {
P1_in_CS = true;
turn=2;
while (P2_in_CS == true
&& turn==2)
;
/* do nothing */
CS
P1_in_CS = false;
non-CS
}
}
P2 ( ) {
while (true) {
P2_in_CS = true;
turn=1;
while (P1_in_CS == true
&& turn==1)
;
/* do nothing */
CS
P2_in_CS = false;
non-CS
}}
 Pre condition: only two
processes/threads in
the system
 Shared variables:
 int turn;
initially turn = 0
 Boolean variables
• P1_in_CS
• P2_in_CS
• Boolean variables
initially false
 Advantages:


Safety
liveness
MX: Multiple Processes
 Bakery Algorithm
 MX solution for n processes
 Algorithm:
 Before entering its critical section, process receives a
number. Holder of the smallest number enters the
critical section.
 If processes Pi and Pj receive the same number, if i < j,
then Pi is served first; else Pj is served first.
 The numbering scheme always generates numbers in
increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5...
MX: Multiple Processes
int i; /* unique process id */
 Shared data
while (true) {
 boolean choosing[n]
choosing[i]=true;
 int number[n]
number[i]=max(number[0],…,
number[n-1])+1;
 Data structures are
choosing[i]=false;
initialized to false
for (j=0; j<n; j++) {
and 0 respectively
while (choosing[j])
;
/* do nothing */
while (number[j]>0 &&
(number[j]<number[i] ||
number[j]==number[i] &&
j<i))
;
/do nothing */
}
CS
number[i] = 0;
non-CS
}
MX: Hardware Support 2
 Special Machine Instructions
 Test and Set Instruction
 Swap (Exchange) Instruction
MX: Test and Set Instruction
boolean TestAndSet (boolean
&target) {
boolean rv = target;
tqrget = true;
return rv;
}
 Shared data:
boolean lock = false;
 Process Pi
while (true) {
while (TestAndSet(lock))
/* do nothing */
CS
lock = false;
non-CS
}
MX: Swap Instruction
void Swap (boolean &a,
boolean &b) {
boolean temp = a;
a = b;
b = temp;
}
 Shared data:
boolean lock=false;
 Process Pi
while (true) {
boolean key=true;
while (key == true)
Swap(lock,key);
CS
lock = false;
non-CS
}
MX: Special Machine
Instructions
 Advantages
 Applicable to any number of processes on either a single
processor or multiple processors sharing main memory
 It is simple and therefore easy to verify
 It can be used to support multiple critical sections
 Disadvantages
 Busy-waiting consumes processor time
 Starvation is possible when a process leaves a critical
section and more than one process is waiting.
 Deadlock
• If a low priority process has the critical region and a higher
priority process needs, the higher priority process will
obtain the processor to wait for the critical region
Semaphores
 Semaphore is a special integer variable that is
used for synchronization
 Semaphore supports two atomic operations : wait
and signal

The atomicity means that the two operations on the
same semaphore can not overlap
 How semaphore works ?
 The semaphore initialized to 1 or a positive value
 Before entering the critical section, a process/thread
calls wait (semaphore)
 After leaving the critical section, a process /thread calls
signal (semaphore)
Semaphores
 Assume our semaphore is called s
wait (s):
s=s–1
if (s < 0)
block the thread
that called wait(s)
otherwise
continue into CS
signal (s):
s=s+1
if (s <= 0)
wake up & run one of
the waiting threads
 Note :
 Negative semaphore = number of blocked threads, where
only one right now in the critical section
Using Semaphores for MX
P1 () {
while (true) {
wait(s);
/* CS */
signal(s);
/* non-CS */
}
}
P2 ()
{
while (true) {
wait(s);
/* CS */
signal(s);
/* non-CS */
}
}
Readers /Writers Problem
int readcount=0;
semaphore wrt(1),mx(1);
writer() {
wait(wrt);
/* perform write */
signal(wrt);
}
reader() {
wait(mx);
readcount++;
if(readcount==1)
wait(wrt);
signal(mx);
/* perform read */
wait(mx);
readconut--;
if(readcount==0)
signal(wrt);
signal(mx);
}
 Readers and writers
can access concurrently same item
 writers cannot concurrently writing
same item, readers can
 If a writer is writing the item, no
reader may read it
 Any writer must wait for all readers



First reader races with writers
Last reader signals writers
Readers can starve writers
 readcount - number of readers
wishing to read the item
 mx - protects manipulation with
readcount
 wrt- writer can get to item if open