Transcript OperatingSystems_FA15_6_Sync

Operating Systems
Dr. Jerry Shiao, Silicon Valley University
Fall 2015
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
1
Process Synchronization
 Overview





Process Synchronization
Race Condition: Concurrent Execution
The Critical-Section Problem
Synchronization Hardware
Semaphores





Synchronization Problems







Counting Semaphores
Binary Semaphores ( Mutexes )
Spinlocks
Priority Inversion / Priority Inheritance
The Bounded-Buffer Problem
The Reader-Writer Problem
The Dining-Philosopher Problem
Monitors
Synchronization in Solaris
Synchronization in Windows XP
Synchronization in Linux
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
2
Process Synchronization




Principle of Concurrency
Multiprogramming: Managing multiple processes in uniprocessor.
Multiprocessing: Managing multiple processes in multi-processor.
Speed of execution of processes unpredictable, leading to
concurrency and synchronization issues.
Interleaving (Multiprogramming: One Processor)
Copyright @ 2009 Pearson
Education, Inc.
Interleaving and Overlapping (Multiprocessing: Multiple Processors)
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
3
Process Synchronization

Principles of Concurrency
Character Echo Procedure:
Input character, stored in variable “chin”.
Transferred to “chout” and sent to display.

Protecting Shared Resource (Global Variable).
Shared global variable, “chin”.
Uniprocessor: P1 interrupted after “chin”
retrieved. P2 executes and overwrites “chin”.
Multiprocessor: P1 and P2 on
separate processors and timing causes
P2 to overwrite “chin”.

Solution: Controlled access to shared resources.
Copyright @ 2009 Pearson
Education, Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
4
Process Synchronization
 Operating System Concerns





What are the design and management issues that must be
resolved by the Operating System to handle concurrency?
Operating System must keep track of processes (Process
Control Block).
Operating System must manage the allocation and deallocation
of resources for every process. Resources are: Processor
(Scheduler), Memory (Memory Management Unit), Files (File
Management), and I/O Devices (I/O Management).
Operating System must protect data and physical resources of
each process (Access Control and Malware Detection).
Process execution must be independent of the relative execution
speed of other processes (Mutual Exclusion and
Synchronization).
Copyright @ 2009 Pearson
Education, Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
5
Process Synchronization
 Process Interaction:

Classified by degree of awareness to other processes.
Degree of Awareness
Relationship
Influence that One
Process Has on the
Other
Potential Control
Problems
Processes unaware of
each other.
Competition
o Results of one
process independent of
the action of others.
o Process slowed down
when waiting.
o Mutual exclusion
(Printer).
o Deadlock (renewable
resource).
o Starvation.
Process indirectly
aware of each other
(shared object).
Cooperation by sharing
data, to ensure integrity
of shared data.
P1: a=a+1, b=b+1
P2: b=2*b, a=2*a
o Results of one
process depends on
information from
another.
o Timing of processes
affects data.
o Mutual exclusion
(Printer).
o Deadlock (renewable
resource).
o Starvation.
o Data coherence.
Processes directly
aware of each
other(using
communication
primitives).
Cooperation by sending
are receiving
messages.
Copyright @ 2009 Pearson
Education, Inc.
o Results of one
process may depend on
information from
another.
o Timing of processes
SILICON VALLEY UNIVERSITY
affects data.
CONFIDENTIAL
o Messages not shared,
NO mutual exclusion.
o Starvation.
6
Process Synchronization


Process Synchronization and Mutual Exclusion Issues
are driven by cooperating processes utilizing shared
address space and shared data through files or
messages.
Cooperating Processes

Processes or Threads running asynchronously and possibly
sharing data.



Problem Bounded Buffer: Used by processes to share memory.
Producer and Consumer concurrent race condition accessing
shared memory.
Race Condition: Several processes access and manipulates same
data concurrently and outcome depends on the order in which
access takes place.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
7
Process Synchronization

Race Condition: Concurrent Execution
Producer:
...
buffer[ in ] = item;
++count;
...
register1=count
register1=register1 + 1
count=register1
Shared Critical Code
Section
Consumer:
...
Item = buffer[ out ];
--count;
...
register2=count
register2=register2 - 1
count=register2
int count;

Consumer and Producer processes do NOT block shared critical
section ( memory location “count” ).

Initial: “count” = 5
T0: producer execute
T1: producer execute
T2: consumer execute
T3: consumer execute
T4: producer execute
T5: consumer execute








register1 = count
{register1 = 5}
register1 = register1 + 1 {register1 = 6}
register2 = count
{register2 = 5}
register2 = register2 − 1 {register2 = 4}
count = register1
{count = 6}
count = register2
{count = 4}
Execute Separately, “count” = 5.
Execute Concurrently, “count” = 4
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
Shared critical section,
“count”, changed at
different times because
interleaved execution
with register contents
save wrong values to
“count”. “count” correct
value is “5”.
8
Process Synchronization


The Critical-Section Problem
Multiple processes sharing common resource (i.e.
memory or file).

Each process has Critical Section of code that will; change
common variables, update shared table, write shared file.
Permission to enter
critical section.
do {
entry section
Only one process at a
time is allowed into its
critical sectoin.
critical section
exit section
remainder section
Permission to exit
critical section.
} while ( TRUE );
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
9
Process Synchronization


The Critical-Section Problem
Multiple processes sharing common resource (i.e.
memory or file).


Each process has Critical Section of code that will; change
common variables, update shared table, write shared file.
Solution Requirements: Cooperation Protocol Between
Processes To Enter/Execute/Exit Critical Section



Mutual Exclusion: When process executes in its Critical Section,
no other process must execute in their Critical Section.
Progress: Process requesting to enter their Critical Section can
enter if no processes currently in their Critical Section.
Bounded Waiting: Bound or limit on the number of times other
processes are allowed to enter their Critical Section, after a
process has requested to enter its critical section.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
10
Process Synchronization


The Critical-Section Problem
Operating System Approaches:

Preemptive Kernel Approach





Kernel process can be preempted.
Race conditions on shared kernel data.
Required for real-time process to preempt kernel process when
real-time process need to run (i.e. real-time interrupt occurs).
Kernel more responsive, a kernel process must relinguish CPU to
other kernel processes.
Nonpreemptive Kernel Approach



Kernel process cannot be preempted and will run until it exits kernel
mode, blocks, or yields the CPU.
Uniprocessor system: Free from race conditions on kernel data
structures.
Multiprocessor system: Does not guarantee Mutual Exclusion.
Kernel response can be slow, a kernel process executes too long.

Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
11
Process Synchronization
 The Critical-Section Problem
 Peterson’s Solution: P(i) and P(j) Critical Section Problem
Process P ( i )
Share two data items: Flag array indicates Ready, turn indicates which process can enter its critical section.
while ( true ) { /* flag, turn Global */
Mutual Exclusion: Both flag[ I ] and flag [ j ]
flag [ i ] = TRUE;
are TRUE, but turn must be “j”when P(j) is
turn = j;
in its critical section. P(i) is waiting in the
while ( flag [ j ] && turn == j );
while loop.
Critical Section
flag[i] = FALSE;
Progress: When P(j) is ready to enter
critical section, it must set turn to “I”. This
allows P(i) to enter its critical section. Once
P(j) exits, sets flag[j] to FALSE, and allows
P(I) to enter its critical section.
Remainder Section
}
while ( true ) {
Process P ( j )
flag [ j ] = TRUE;
turn = i;
while ( flag [ i ] && turn == i );
Mutual Exclusion: Both flag[ I ] and flag [ j
] are TRUE, but turn must be “i”when P(i) is
in its critical section. P(j) is waiting in the
while loop.
Critical Section
flag[j] = FALSE;
Remainder Section
}
Copyright @ 2009 John
Wiley & Sons Inc.
Bounded Wait: Both flag[ I ] and flag [ j ]
are TRUE, but turn must be “i”when P(j) is
ready to enter its critical section. P(i) waits
one instruction before P(i) enters its critical
section.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
12
Process Synchronization
 Synchronization Hardware
 Current Computer Architecture Require a Lock.


Peterson’s Software Solution not guaranteed: Load and Store
hardware instruction.
Any solution requires a lock: A process must acquire a
lock before entering a critical section.
1) Process must acquire lock.
2) Execute Critical Section.
3) Process must release lock,.
while ( true ) {
Acquire Lock
Critical Section
Release Lock
}

Remainder Section
Operating Systems can use NonPreemption and disable
Interrupts. Feasible?

All processors of multi-processor system must receive “Disable
Interrupt” message. Time-consuming.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
13
Process Synchronization
 Synchronization Hardware
 Special Hardware Instruction: Atomic Operation is an
instruction sequence completed without interruption.



One uninterruptible unit.
Abstract TestAndSet( ) Atomically
Mutual Exclusion
Process1:
Step 1
1) lock = FALSE
2) TestAndSet sets lock = TRUE
3) Returns FALSE ** RUNS **
boolean TestAndSet ( boolean *target ) {
boolean rv = *target;
*target = TRUE;
return rv;
}
Process2:
Step 2
1) lock = TRUE
2) TestAndSet sets lock = TRUE
3) Returns TRUE ** WAITS **
lock = FALSE; /* Global */
Process1:
Step 3
1) lock = FALSE ** OUT **
do { /* PROCESS1 */
while (TestAndSet ( &lock ) ) ;
Critical Section
lock = FALSE;
Remainder Section
} while ( TRUE )
Copyright @ 2009 John
Wiley & Sons Inc.
do { /* PROCESS2 */
while (TestAndSet ( &lock ) ) ;
Critical Section
lock = FALSE;
Remainder Section
} while ( TRUE )
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
Process2:
Step 4
1) lock = FALSE
2) TestAndSet sets lock = TRUE
3) Returns FALSE ** RUNS **
14
Process Synchronization
 Synchronization Hardware
 Abstract swap( ) Atomically
 Mutual-Exclusion
void swap ( boolean *a, boolean *b) {
boolean temp = *a;
*a = *b;
*b = temp;
}
lock = FALSE; /* Global */
do { /* PROCESS1 */
key = TRUE;
while (key == TRUE)
swap ( &lock, &key );
Critical Section
lock = FALSE;
Remainter Section
} while ( TRUE );
do { /* PROCESS2 */
key = TRUE;
while (key == TRUE)
swap ( &lock, &key );
Critical Section
lock = FALSE;
Remainter Section
} while ( TRUE );
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
Process1:
Step 1
1) lock = FALSE
2) swap sets lock = TRUE and
key = FALSE
3) key = FALSE exits the while
statement and enters Critical
Section.
Process2:
Step 2
1) lock = TRUE
2) Swap sets lock = TRUE and
key = TRUE
3) Continue loop until key ==
FALSE
Process1:
Step 3
1) Exits Critical Section
2) lock = FALSE
Process2:
Step 4
1) lock = FALSE
2) Swap sets lock = TRUE and
key = FALSE
3) Key = FALSE exits the while
statement and enters Critical
Section.
15
Process Synchronization
 Synchronization Hardware
 Abstract TestAndSet( ) Atomically Satisfy Critical-Section
Requirements
lock = FALSE;
do { /* PROCESS1 */
waiting [ i ] = TRUE;
key = TRUE;
while ( waiting[ i ] && key )
key = TestAndSet( & lock );
waiting [ i ] = FALSE;
Critical Section
j = ( i + 1 ) % n;
while ( ( j != i ) && !waiting [ j ] )
j = ( j + 1 ) % n;
if ( j == i )
lock = FALSE;
else
waiting [ j ] = FALSE;
Remainder Section
} while ( TRUE );
Copyright @ 2009 John
Wiley & Sons Inc.
Creates Mutual Exclusion. The first process to execute will
have lock = FALSE and set key = FALSE.
Bounded-Waiting. After leaving Critical Section, the waiting
array is scanned and finds the next process to enter its
Critical Section.
Progress. Setting lock = FALSE or waiting [ j ] = FALSE
allows a process that is waiting to enter its Critical Section to
progress.
NOTE: If lock was set to FALSE, (j == i), then entire array
was scanned and no process was waiting.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
16
Process Synchronization
 Synchronization Hardware
 Advantages of Hardware Machine-Instruction Approach:



Applicable to uni-processor or multiprocessors sharing main
memory.
Support multiple critical sections, each with its own variable.
Disadvantages:




Busy waiting is employed: Process waiting to access critical
section is consuming processor time.
Starvation is possible: When more than one process is waiting,
selection of a waiting process is arbitrary.
Deadlock is possible: Process in its critical section can be
interrupted and interrupting process is locked out, waiting for the
same critical section.
Implementing atomic instructions on multiprocessors not trivial.
Copyright @ 2009 Pearson
Education, Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
17
Process Synchronization
 Semaphores





Synchronization Tool Favored by Application Programs.
Three atomic operations: Initialize, Decrement, Increment.
Decrement Operation: May result in blocking a process.
Increment Operation: May result in unblocking a process.
Wait ( ) Atomic Operation

Originally “P”: Mean “to test”.
wait ( S ) {
while S <= 0; // no-op
S--;
}

Signal ( ) Atomic Operation

Originally “V”: Mean “to increment”.
signal ( S ) {
S++;
}
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
18
Process Synchronization
 Semaphores

Counting Semaphores


Control access to resource to finite instances of the resource.
Wait ( S ) and Signal ( S ):



Binary Semaphores


Semaphore is either “0” or “1”.
Provide Mutual Exclusion: Wait ( S ) and Signal ( S ).



“S” emaphore initialized to number of resources available.
When Semaphore is zero, next process will Block.
When Semaphore is zero, next process will Block.
Busy Waiting ( Loop Continuously in Entry Code )
Spinlock: Semaphore with Busy Waiting.



Thread “spins” on a processor.
Used to wait short time for lock.
Multiprocessor System: One processor has thread executing spinlock while
thread on another processor performs Critical Section.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
19
Process Synchronization
 Semaphores
 Definition of Semaphore Primitive:
struct semaphore {
int count;
queueType queue;
}
void semWait ( semaphore s )
{
s.count- -;
if ( s.count < 0 ) {
/* Place this process in s.queue. */
/* Block this process. */
}
}
void semSignal ( semaphore s )
{
s.count + +;
if ( s.count <= 0 ) {
/* Remove a process P from s.queue. */
/* Place process P on Ready List. */
}
}
:
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
No way to know before a process
decrements a semaphore, whether
it will block or not.
After process increments a
semaphore and another process is
scheduled, both processes
continue running concurrently.
After signaling a semaphore, no
way to know whether another
process is waiting, so the number
of unblocked processes may be
zero or one.
20
Process Synchronization
 Semaphores
 Definition of Binary Semaphore:
struct binary_semaphore {
enum ( zero, one ) value;
queueType queue;
}
void semWaitB ( semaphore s )
{
if ( s.value == one )
s.value = zero;
else {
/* Place this process in s.queue. */
/* Block this process. */
}
}
void semSignalB ( semaphore s )
{
if ( s..queue is empty( ) )
s.value = one;
else {
/* Remove a process P from s.queue. */
/* Place process P on Ready List. */
}
SILICON VALLEY UNIVERSITY
}
Copyright
@ 2009 John
CONFIDENTIAL
Wiley: & Sons Inc.
A binary semaphore may be
initialized to 0 or 1.
The semWaitB checks the
semaphore value. If zero, the
process executing the semWaitB is
blocked. If one, the value is
changed to zero, and process
continues execution.
The semSignalB checks to see if
any processes are blocked on this
semaphore (semaphore value is
zero). If so, then process is blocked
by semWaitB is unblocked. If no
processes are blocked, then the
value of the semaphore is set to
one.
21
Process Synchronization
 Semaphores



block ( ) and wakeup ( ) instead of Busy Waiting
wait ( ) and signal ( ) must be Atomic.
Multiprocessor environment: Overhead Disabling Interrupts,
SMP Uses Spinlocks.
The semaphore structure contains
linked list of processes waiting for
semaphore.
typedef struct {
int value;
struct process *list;
} semaphore;
Disable interrupts when wait ( ) and
signal ( ) are executing.
wait ( semaphore *S ) {
 The
S  value - -;
if ( S  value < 0 ) {
add process to S  list;
block ( );
}
}
Copyright @ 2009 John
Wiley & Sons Inc.
signal ( semaphore *S ) {
S  value + +;
if ( S  value <= 0 ) {
remove process from S  list;
wakeup ( );
}
}
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
22
Process Synchronization
 Semaphores
A issues semWait on semaphore s,
s decrements to 0.
B runs and issues semWait on s. B
is blocked and D scheduled.
D runs issues semSignal on s. B is
moved to Ready Queue.
C runs and issues semWait on s. C
is blocked. B and A runs and issues
semWait on s.
D runs issues semSignal on s. C is
moved to Ready Queue.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
23
Process Synchronization
 Semaphores
 Mutex: Related to Binary Semaphore.


Process that locks the mutex (set to zero) must be the process to
unlock it (set to one).
Mutual Exclusion using Semaphores:
const int n = /* Number of processes. */;
semaphore s = 1;
void p ( int I )
{
while ( true ) {
semWait ( s );
/* Critical Section. */
semSignal ( s );
/* Remainder. */
}
}
void main ( )
Any number of processes may
attempt entry, each unsuccessful
entry results in a further decrement
of the semaphore s.
Departing from the critical section,
semaphore s is incremented and
one of the blocked processes (if
any) is put in the Ready List.
parbegin ( P ( 1 ), P ( 2 ), . . . , P ( n ) );
}
Copyright @ 2009 Pearson
Education, Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
24
Process Synchronization
 Semaphores
 Processes Accessing Shared Data Protected by
Semaphore:
semWait(lock)
semWait(lock)
semWait(lock)
semSignal(lock)
semSignal(lock)
semSignal(lock)
Copyright @ 2009 Pearson
Education, Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
Note: Normal execution
can proceed in parallel,
but that critical25
regions
are serialized.
Process Synchronization
 Semaphores
 Deadlocks


Deadlock when two or more processes waiting on event that is caused by one of
the waiting processes.
P0
P1
Starvation

wait(Q);
...
wait(S);
...
signal(Q);
Starvation or Infinite Blocking: Process wait indefinitely within
Semaphore.


wait(S);
...
wait(Q);
...
signal(S);
List in Semaphore is processed LIFO ( Last-In, First-Out ) order.
Priority Inversion

Higher priority task waiting on a semaphore held by a lower
priority task. Before lower priority task release the semaphore, it
is interrupted by another task (medium priority) and the higher
priority task has to wait.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
26
Process Synchronization




Priority Inheritance Protocol
All processes holding lock on resource needed by a
higher priority process has the process’s priority raised
to the higher priority process.
After process releases the Critical Section, it returns the
process to its original priority.
Unbounded Priority Inversion.
Unbounded Priority Inversion
Priority
Task H
6
2
Task M
4
Task L
1
3
5
Critical Section Execution
Normal Execution
Fall 2012
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
Process Synchronization

Priority Inheritance:


Low-priority task has priority raised until completes critical
section (releases shared resource).
Nested resource locks can lead to deadlock.
 Avoid deadlock by allowing each task to own one shared
resource.
 Do not allow nested locks.
 Overhead raising priority and then lowering priority.
- Task L Completes critical
section. Priority lowered.
- Task M receives resource.
Executes critical section.
- Task M request resource.
- Task L priority raised.
Executes critical section.
Task M
Task L
Fall 2012
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
Critical Section Execution
Normal Execution
28
Process Synchronization
 The Bounded-Buffer Problem



Semaphore mutex = 1
Semaphore empty = n
Semaphore full = 0
1)
2)
3)
4)
5)
Producer Process:
Add to Buffer Pool
do {
,,,
// produce an item in nextp
...
wait ( empty );
wait ( mutex );
...
// add nextp to buffer
...
signal ( mutex );
signal ( full );
...
} while ( TRUE );
Copyright @ 2009 John
Wiley & Sons Inc.
Calls wait(empty). Empty is nonzero.
Calls wait(mutex). Mutex becomes 0.
Updates buffer.
Calls signal(mutex). Mutex becomes 1.
Calls signal(full). Full becomes 1.
Consumer Process:
Remove from Buffer Pool
do {
...
wait ( full );
wait ( mutex );
...
// remove an item from buffer to nextc
...
signal ( mutex );
signal ( empty);
...
} while ( TRUE );
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
29
Process Synchronization
 The Reader-Writer Problem



Writer Exclusive Access, Reader Shared Access.
Semaphore mutex ( 1 ) mutual exclusion for “readcount” ( 0 ).
Semaphore wrt ( 1 ) mutual exclusion for writers.
Reader 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 );
Copyright @ 2009 John
Wiley & Sons Inc.
1)
Readers reading
database locks out
Writer.
Writer may starve,
when many readers
arrive.
Writer writes to
database, Readers are
locked out.
One reader queue on
wrt, other readers
queue on mutex.
2)
3)
First Reader wait(mutex) to update
“readcount”. Calls wait(wrt) to lock out
writer.
Readers can share database access,
wait(mutex) to update “readcount”.
Last Reader calls signal(wrt) to allow
writer to write database.
Writer Process
do {
wait ( wrt );
...
// Writing is Performed
...
signal ( wrt );
} while ( TRUE );
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
30
Process Synchronization
 The Dining-Philosophers Problem




Concurrency-control problem: Need to allocate several
resources amoung several processes in a deadlock-free and
starvation-free manner.
Semaphore chopstick [ 5 ]
Wait ( chopsticks [ I ] ) pick up chopstick.
Signal ( chopsticks [ I ] ) put down chopstick.
1)
2)
3)
4)
5)
Copyright @ 2009 John
Wiley & Sons Inc.
All Philosophers wait( ) when grab chopstick, signal ( )
when release choptstick.
Only allow 4 Philosophers at one time.
Only pick up chopsticks when both left and right
chopsticks are available, utilizing two wait ( ).
Odd Philosopher picks up left, then right chopsticks.
Even Philosopher picks up right, then left chopsticks.
NOTE: Possible DEADLOCK, all philosophers grab
their left chopstick and wait forever for the right
chopstick.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
31
Process Synchronization
 Monitor Type – High Level Synchronization Construct
 Abstract Data Type: Encapulates private data with public
methods to operate on that data
 Within a Monitor:



Variables for mutual exclusion.
Procedures or functions that operate on the variables.
Procedures can only access variables within the monitor.
Monitor monitor name {
/ / shared variable declarations
...
procedure p1 ( . . . ) {
...
}
...
condition x, y;
procedure pn ( . . . ) {
x.wait ( );
...
x.signal ( );
}
}
Copyright @ 2009 John
Wiley & Sons Inc.
Only one procedure within the monitor
can be active.
Add synchronization scheme using
wait ( ) and signal ( ).
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
32
Process Synchronization
 Monitor Dining-Philosophers Problem
Monitor dp {
enum { THINKING, HUNGRY, EATING } state [ 5 ];
condition self [ 5 ];
void pickup ( init I ) {
state [ I ] = HUNGRY;
test( I );
if ( state [ I [ != EATING )
self [ I ].wait ( );
}
void putdown ( int I ) {
state [ I ] = THINKING;
test ( ( I + 4) % 5 );
test ( ( I + 1 ) % 5 );
}
void test ( int I ) {
if ( (state [ I + 4 ) % 5 ] != EATING) &&
( state [ I ] == HUNGRY ) &&
( state [ ( I + 1 ) % 5 ] != EATING ) ) {
state [ I ] = EATING;
self [ I ].signal ( ) ;
}
}
Copyright @ 2009 John
Wiley & Sons Inc.
Create condition self. With self.wait ( )
suspend process and self.signal ( )
invoke a process. NOT Semaphores.
1)
2)
3)
4)
5)
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
First, pickup ( ) must be called.
Philosopher can pick up chopsticks
when both are available.
State EATING when both neighbors
are not EATING.
State NOT EATING, the process
suspended with self[i].wait ( ).
When finished eating, the process
must call putdown ( ) .
Putdown( ) will check for neighbors
and release the neighbor, self[ I
].signal( ), when the neighbor can
change state to EATING.
33
Process Synchronization
 Monitor Using Semaphores
wait ( mutex );
...
body of Procedure F
...
if ( next_count > 0 )
signal ( next )
else
signal ( mutex )

Process must execute wait (mutex) before
entering the monitor and execute signal
(mutex) after leaving the monitor.
Semaphore ( next ) used by process to wait
until the process in the monitor leaves.
Counter next_count counts number of
processes waiting for monitor.
No Guarantee the Correct Sequence is Used




A process might access a resource without first gaining access
permission.
A process might never release resource once granted permission.
A process might release resource that was not requested.
A process might request same resource without releasing resource.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
34
Process Synchronization


Synchronization in Solaris
Adaptive Mutex

On Multiprocessor system Adaptive Mutex initially a Spinlock.



On single processor system, Adaptive Mutex always blocks.
Critical code more than a few hundred instructions uses
semaphores (block).



If thread holding the lock not running on another processor, the
mutex blocks.
In short code segments, spinlock cost (putting thread to sleep,
waking it, and context switch) is less than blocking.
Reader-Writer Locks: Access protected data frequently, but in
read-only manner. Concurrent access, semaphores are serial
access.
TurnStile (Queue) maintained by first blocked process for
Adaptive Mutex and Reader-Writer Locks.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
35
Process Synchronization
 Synchronization in Windows XP
 Uniprocessor System, Windows XP kernel accesses a
global resource, will temporarily mask interrupts.
 Multiprocessor System, Windows XP uses spinlocks for
short code segments ( Solaris ).
 Thread Sychronization, Windows XP uses Dispatcher
Objects for mutexes, semaphores, events, and timers.


Signaled State: Dispatch object is available.
Nonsignaled State: Dispatch object is not available and access
will block.
Thread releases
Mutex Lock.
NonSignaled
Signaled
Thread acquires
Mutex Lock.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
Transition to Signaled, a
mutex will select one thread
from waiting queue.
When event object, all
threads selected from waiting
queue.
36
Process Synchronization
 Synchronization in Linux
 Uniprocessor Systems, Linux Enables and Disables
Kernel preemption.


preempt_disable ( )
preempt_enable ( ): Kernel is not preemptable when kernelmode process holding a lock.



preempt_count in thread-info structure to count number of locks.
Multiprocessor Systems, Spinlocks for short durations.
Single Processor
Multiple Processor
Disable Kernel Preemption
Acquire Spinlock
Enable Kernel Preemption
Release Spinlock
Synchronization in Pthreads API

Mutex Locks (fundamental synchronization technique), Condition
Variables, Read-Write Locks for Thread Synchronization.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
37
Summary






With cooperating sequential processes that share data, mutual
exclusion ensures critical section of code is used by one process or
thread at a time.
Special Hardware Instructions:
 Abstract TestAndSet() Atomic Variable
Software Semaphores with Atomic Operations.
 Wait() and Signal().
Synchronization or Concurrency Control Problems:
 Bounded-Buffer, Readers-Writers, Dining-Philosophers.
Monitors: Language Constructs encapulates private data with public
methods to operate on that data.
 Timing Errors or Programming Errors.
Solaris, Windows XP, Linux mechanisms (semaphores, mutexes,
spinlocks, condition variables) used to control access to shared data.
Copyright @ 2009 John
Wiley & Sons Inc.
SILICON VALLEY UNIVERSITY
CONFIDENTIAL
38