Transcript Slides

Process Synchronization
Chapter 9
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Process Synchronization
•
Processes that work toward a common goal must
coordinate their activities
– Such coordination is achieved through synchronization
– We discuss two kinds of synchronization defined in Chapter 3
* Data access synchronization
 Avoiding race conditions through mutual exclusion
* Control synchronization
 Ensuring that processes perform their actions in a desired
order
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Interacting processes
•
Definition:
– Processes Pi, Pj are interacting processes if
read_seti ∩ write_setj ≠ Ø or
write_seti ∩ read_setj ≠ Ø,
where
* Read-set : Set of variables merely read by a process
* Write-set : Set of variables read and written to by a process
– Non-interacting processes are independent processes
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Critical Section (CS)
•
Definition
– A critical section (CS) for a data item ds is a section of code that
cannot be executed concurrently with itself or with another
critical section for ds
* We will use a dashed rectangular box to indicate a critical section in
a code segment (see next slide)
•
Data access synchronization
– Is defined as ensuring an absence of race conditions over a
shared data item ds
* It is achieved by enclosing all uses of ds within critical sections
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
A process having critical sections
We assume a process to consist of a single infinite loop; a dashed
rectangular box depicts a critical section
(a) A process having many critical sections
(b) A process having a single critical section
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Use of CS in airline reservation
to avoid race conditions
• All processes have an identical form
• nextseatno is examined and incremented within a CS
• Hence a race condition does not exist
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Essential properties of a CS implementation
•
A CS implementation must posses three properties
– Correctness
* At most one process can be in a CS for a data item ds at any time
– Progress
* When no process is in a CS for ds, a process wishing to enter a CS
for ds can get in immediately
 One of the processes requesting a CS on ds will definitely make
progress
– Bounded wait
* If Pi wishes to use a CS for ds, the number of times another
process can request entry to CS and get in ahead of Pi is bounded
by a constant
 A process is not denied entry to a CS indefinitely
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Busy wait
•
A CS can be implemented as follows:
while { some process is in a CS for ds }
{ do nothing }
{ CS }
•
It causes a busy wait
– Definition: Busy wait is a situation in which a process checks a
condition over and over again until the condition is satisfied
– A busy wait wastes CPU power
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Busy wait
•
A busy wait
– May lead to priority inversion
* A high priority process is blocked for an I/O operation
* A low priority process is scheduled and gets into a CS for ds
* The high priority process becomes ready, gets scheduled and
wishes to enter a CS for ds but gets into a busy wait for the CS
* Both processes wait for one another indefinitely!
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Avoiding priority inversion
•
The Priority inheritance protocol
– A low priority process holding a resource (or CS) inherits priority
of the highest priority process that is waiting for the resource (or
CS)
* It enables the low priority process to complete use of the resource
(or CS) and release it
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Control Synchronization
•
Processes should perform actions in a desired order
– This order depends on logic of the application, e.g., in the
satellite data logging example, a record received from a satellite
is to be written into a disk file via a buffer
* A process should copy a record from the buffer into a disk file only
after another process has written a record into the buffer
* A process should write a record into a buffer only after some other
process has copied the previous record out of the buffer
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Control Synchronization
•
Processes should perform actions in a desired order
– e.g., Process Pi should perform action ai after another process Pj
has performed action aj
* Block process Pi before performing action aj if Pi has not yet
performed action aj
* Pi should be activated after Pj has performed action aj
•
We need a signaling arrangement for this
– (no connection with signals in processes)
– Next slide shows an arrangement using boolean variables
– Q: If variables are used for signaling, could race conditions arise
on these variables?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
An attempt at signaling through boolean variables
• Variable operation_aj_performed indicates whether aj has been performed
• Process Pi becomes blocked before operation ai if it has the value false
• After performing aj, process Pj either sets this variable or activates Pi
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Race condition in process synchronization
• The table shows the times when Pi and Pj perform their actions
• A race condition exists in this program
– Process Pi tests value of action_aj_performed but gets
preempted before it can set pi_blocked to true
– Process Pj sets action_aj_performed, but does not activate
process P
• Q: Can the race condition have another consequence?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Indivisible operation
•
An indivisible operation on a set of data items {ds}
– is an operation that cannot be executed concurrently with any
other operation involving a data item included in {ds}
* How are indivisible operations implemented? We will see that later
– To avoid the race condition of previous slide, we define two
indivisible operations
* Check_aj: If action_aj_performed is false, it sets pi_blocked to true
and blocks Pi
 This way, Pj would not test pi_blocked before it is set
* Post_aj: (Q: What actions should it perform?)
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Control synchronization by signaling using
indivisible operations
• Process Pi invokes check_aj before performing operation ai
• Process Pj invokes post_aj after performing operation aj
• Code of these actions is shown in the next slide
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Indivisible operations for signaling
• check_aj either sets pi_blocked
and blocks Pi, or does not perform
any actions
• post_aj either changes pi_blocked
to false and activates process Pi,
or sets action_aj_blocked
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Implementing a critical section or indivisible
operation using a lock variable
• The process checks the boolean variable lock repeatedly until
it can enter the critical section
• The actions of checking the value of lock and setting it to closed
should be performed in an indivisible manner; it avoids a race
condition on lock
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
CS using Test-and-set (TS) instruction
• The TS instruction performs following actions indivisibly:
– Check the value of LOCK and set condition code to
indicate whether it is ‘open’ or ‘closed’
– Set LOCK to ‘closed’
• The BC instruction checks the condition code set by TS
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
CS or indivisible operation using Swap instruction
• TEMP is initialized to the value ‘closed’
• The SWAP instruction swaps LOCK and TEMP
• The COMP instruction checks the old value of LOCK and
decides whether the process may enter CS
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Classic process synchronization problems
•
Why study these problems?
– These problems represent frequently encountered situations in
process synchronization
* Hence it helps to analyze their synchronization requirements and
discuss how they can be implemented
– A ‘good’ solution to a process synchronization problem must
have three properties
* Correctness
* Maximum concurrency
* No busy waits
Hence we shall focus on these three aspects in this study
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Classic process synchronization problems
•
Three classic problems
– Producers and consumers
* Producers produce items of information in a finite set of buffers;
consumers consume the information items from the buffers
* Goal: Smoothen out occasional mismatch of produce and consume
rates
– Readers and writers
* Some processes merely read some data, others may modify it
* Goal: Ensure concurrency of processes and consistency of data
– Dining philosophers
* Adjoining philosophers have to share forks with their neighbours.
* Goal: Ensure that they may eat without indefinite waits for forks
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Producers and consumers
• A producer produces an item of information and writes it into
an ‘empty’ buffer; this action makes the buffer ‘full’
• A consumer copies an item of information out of a full buffer and uses it
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Producers and consumers
•
A solution to this problem must satisfy the following
conditions:
– A producer must not overwrite a ‘full’ buffer
* It must wait until an empty buffer is available
– A consumer must not consume an ‘empty’ buffer
* It must wait until a full buffer is available
– Producers and consumers must access buffers in a mutually
exclusive manner
* Otherwise, race conditions would arise
– An optional condition:
* Information must be consumed in the same order in which it is
produced, i.e. in FIFO order
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Solution outline for producers–consumers
• The producer checks for an empty buffer inside of a critical section
• The consumer checks for a full buffer inside of a critical section
• Q: What are the deficiencies of this solution? Busy waits!
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
An improved outline for a single buffer
producers–consumers system using signaling
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Indivisible operations for
the producers–consumers problem
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Readers and writers in a banking system
• A reader process merely reads values of account balances
• A writer process modifies account balances
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Readers and writers
•
Conditions to be satisfied by a solution to the
readers–writers problem
– Many readers may perform reading concurrently
– Reading is prohibited while a writer is writing
– Only one writer can perform writing at any time
– An optional condition:
* A writer should have priority over readers
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Solution outline for
readers–writers without writer priority
• Reading of data is not performed inside a critical section
• A write operation is performed inside a critical section
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Dining philosophers
• A fork is placed between every pair of philosophers
• A philosopher needs two forks to eat; waits if a fork is not available
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Outline of a philosopher process Pi
• A philosopher checks for
availability of forks one by one
• Q: Can starvation arise?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
An improved outline of a philosopher process
• A philosopher checks for
both forks simultaneously
• Q: Does it avoid starvation?
• Q: Does it provide high
concurrency?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Concurrent systems
•
Components of a concurrent system
– Processes
– Shared data: It can be of two kinds
* Data belonging to the application that is implemented by processes:
we call it application data
* Synchronization data introduced to implement synchronization
– Operations on shared data can also be of two kinds
* Operations belonging to the application
* Synchronization operations (i.e., operations on synchronization
data)
•
We introduce pictorial conventions to depict state of a
concurrent system—it is called a snapshot
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Pictorial conventions for
snapshots of concurrent systems
• Note the conventions for shared data, queue of blocked processes
and mutually exclusive operations (a dashed box)
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Snapshots of the system of slide 16
check_aj, post_aj are mutually exclusive operations
(a) Pi performs check_aj while Pj performs operation aj
(b) Pi gets blocked, Pj performs post_aj
(c) Pi performs operation ai
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Algorithmic approach to CS implementation
•
In the algorithmic approach
– when a process wishes to use a CS, it checks a condition
* It enters a busy wait until the condition is satisfied
* It enters the CS when the condition is satisfied
– This approach does not require any support from the architecture
* It does not require indivisible instructions
– However, the condition could be complex
* Proofs of correctness are difficult to construct
•
This approach is not used in practice
– We study it to understand concurrency and race conditions
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Two Process Algorithms: First attempt
• Processes enter their CSs according to the value of turn
• Q: Does it satisfy the progress, bounded wait properties ?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
First attempt
•
Properties of this solution:
– Processes enter the CS strictly by turn
* Hence the solution satisfies the bounded wait condition
– A process enters busy wait if it is not its turn to use the CS
* This is so even if the other process is not interested in using the CS,
which violates the progress condition
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Second attempt
• c1, c2 are status flags for the processes
• c1 = 0 if process P1 is in the CS. Similarly c2
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Second attempt
•
Properties of this solution:
– A process enters the CS if the other process is not in CS
* Value of c1 indicates whether process P1 is in the CS
* Hence the solution satisfies the progress condition
– Mutual exclusion is not ensured when both processes try to use
the CS at the same time
* Exchanging the while statement with c1 := 0 in P1, and similarly in
P2, would help; however, it causes a deadlock
– A process should wait for the other process if it also wishes to
use the CS
* However, processes must not wait for each other indefinitely; this
situation is called a livelock condition
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Dekker's algorithm
• This solution avoids
deadlock and livelock
problems
Q: How?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Dekker’s algorithm
•
Employs useful elements of the previous two algorithms
– Variable turn is used to avoid livelocks
– Variables c1, c2 are used as status flags for P1 and P2 to indicate
whether the process is interested in entering the CS
•
Peterson’s algorithm (next slide) is simpler than Dekker’s
– The boolean array flag has an element for each process; it is
used analogous to c1, c2 of Dekker’s algorithm
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Peterson's algorithm
• Show how
mutual exclusion,
progress and
bounded wait
properties hold
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
An n process algorithm: Code of process Pi
• The status flag has three values idle, want-in and in-CS
• A process enters CS if none of the processes ahead of it in the
modulo order wishes to enter CS
• Q: How are race conditions avoided?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
An n process algorithm
•
Explanation of some features
– A process wishing to enter the CS checks whether some process
ahead of it in the modulo order starting on Pturn wishes to use the
CS
– More than one process may reach the same conclusion (a race
condition!)
* Hence it checks whether any other process wishes to enter the CS
(see the second while loop)
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Bakery algorithm
•
Features of the algorithm
– The algorithm hands out tokens to processes
* A token contains a number, which is larger than the number in all
previously issued tokens
* Processes enter the CS in the order of numbers in their tokens
– When a process wishes to enter the CS, it obtains a token
* A special provision is needed to avoid a deadlock when two or more
processes obtain a token at the same time
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Bakery algorithm
• A process obtains a
token and checks
whether it may enter CS
• Q: What is the purpose
of the first while loop?
• Q: The second while loop?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Condition used in the Bakery algorithm
•
Use of the following condition avoids a race condition:
If the token numbers are identical, the tie is broken by favouring
the process with the smaller process id
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Semaphores
•
What is a semaphore?
– A semaphore is a special integer that takes only non-negative
values on which only the following three operations can be
performed
* Initialization
* Indivisible operation wait
* Indivisible operation signal
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Semantics of wait & signal operations
on semaphores
• The wait operation reduces the value of S if S > 0; otherwise it
blocks the process
• The signal operation wakes a process if processes are blocked
on the semaphore; otherwise, it increases the value of S
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Uses of semaphores
•
Semaphores can be put to three uses
– Mutual exclusion
* Use a semaphore that is initialized to 1
* A binary semaphore takes only 0 and 1 as its values
– Bounded concurrency
* Bounded concurrency implies that a function can be performed by
up to n processes, 1 ≤ n ≤ c, where c is constant
* Can be implemented using a semaphore initialized to n
– Signaling to ensure that an operation ai is performed after some
other operation aj
* Can be implemented using a semaphore S initialized to 0
* A signal(S) operation is performed after aj
* A wait(S) operation is performed before ai
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
CS implementation with semaphores
• Only one process can be in its critical section at any time
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Snapshots of the concurrent system
of previous slide
(a)
(b)
(c)
(d)
Pi has performed a wait operation on sem_CS
Pj has performed a wait operation while Pi is inside the CS
Pi has exited the CS and Pj has entered CS
Pj has exited the CS
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Bounded concurrency using semaphores
• Up to 5 processes can simultaneously use a printer each
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Signaling using semaphores
• Process Pi will be blocked if it performs wait before Pj has
performed signal; otherwise, it will not be blocked
• The signal operation performed by process Pj would activate
Pi if it is blocked for performing operation ai
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Single buffer producers–consumers
using semaphores
• The producer performs a wait on empty and signal on full
• The consumer performs a wait on full and signal on empty
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Snapshots of single buffer producers–consumers
using semaphores
(a) Semaphore full is initialized to 0 and empty to 1
(b) Consumer performed wait (full) and got blocked; producer is producing
(c) Consumer is activated when producer finishes producing
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Bounded buffers using semaphores
• n buffers exist
• prod_ptr points to next empty buffer, cons_ptr to next full buffer
• Q: How to generalize to multiple producers and consumers?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Readers–writers without writer priority
Refined solution outline
• The last exiting reader activates one writer
• An exiting writer activates either all waiting readers or one writer
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Readers–writers using semaphores
•
We use four counters
– runread : number of readers currently reading
– totread : number of readers currently waiting to read or reading
– runwrite : number of writers currently writing
– totwrite : number of writers currently waiting to write or writing
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Readers–writers
using semaphores
and four counters
• Readers and writers are
controlled by a semaphores
reading and writing
• Mutex is used to avoid
race conditions on the
counters
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Implementation of Semaphores
•
Three features are needed to implement semaphores
– Kernel support
* The kernel must support blocking and activation of processes
– Use of lock variables
* A lock variable should be used to implement wait and signal
operations of a semaphore as indivisible operations
– Architectural assistance
* Indivisible instructions, e.g., Test-and-set, are needed to set and
reset the lock variable in a manner that prevents race conditions
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Implementation of wait and signal operations
of semaphores
• A list of blocked
processes is
maintained
• block_me is a
system call that
blocks the calling
process
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Methods of implementing semaphores
•
Kernel-level implementation
– Kernel implements the wait and signal operations shown before
* High overhead—every wait, signal operation leads to a system call
•
User-level implementation
– wait and signal operations are coded as library procedures
* block_me and activate are also calls on library procedures
 It imposes some restrictions on concurrency and parallelism as in userlevel threads
* This method suits user-level threads due to presence of library
•
Hybrid implementation
– wait and signal operations are implemented in a library
* block_me and activate are system calls
* Eliminates the restrictions of a user-level implementation
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Problems in using semaphores
•
Wait and signal operations are primitives
– They can be used in an arbitrary manner in a program, which
may lead to deadlocks, e.g., if a process implements a CS as
follows:
signal (mutex)
{ CS }
signal (mutex)
Q: Can it lead to correctness problems?
– Hence we need control structures for synchronization
* They ensure validity of usage
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Conditional Critical Region (CCR)
•
•
CCR is a control structure on shared data x
Features:
– Mutual exclusion
* Only one process can be in a CCR on a variable x at any time
– The process in a CCR can use the await (boolean condition)
primitive
* The process is blocked if the boolean condition is not true
* It is activated when the condition becomes true
* Use of the boolean condition avoids the need for explicit signaling
actions
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Bounded buffer using conditional critical region
• A region .. do
statement is a
CCR
• Producer awaits
the condition
‘full < n’
• Consumer awaits
the condition
‘full > 0’
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Readers–writers without writer priority
• A reader awaits
runwrite = 0
• A writer awaits
runread = 0
• A write is
performed inside
the CCR, which
is a CS on
read_write
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Conditional critical regions
•
Implementation outline:
– The boolean condition on which processes are blocked should
be checked periodically. Any processes whose conditions have
become true should be activated
– Q: How often should a condition be checked?
* Tradeoff between delays in synchronization and overhead
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Monitors
•
A monitor is a language construct that resembles a class
in C++ or Java and provides
– Data abstraction
* A data type is defined by
 Specifying legal values that data items of that type can take
 Specifying legal operations on data items of that type
– Encapsulation for mutual exclusion
* Operations on data are performed in a mutually exclusive manner
– Facilities for process synchronization
* Condition variables, wait and signal statements
•
Use of monitors facilitates proof of correctness
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Components of a monitor type
•
A monitor type consists of four components
– Data declaration
* Data declared here exists in every object of the monitor type
* We call each object a monitor variable, or simply a monitor
– Data initialization
* When a monitor is created, its data is initialized as indicated here
– Operations on shared data
* Operations are coded as procedures
* They are encapsulated for mutual exclusion
– Synchronization statements
* <cv>.wait and <cv>.signal statements perform process
synchronization, where <cv> is name of a condition variable
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Using a monitor for process synchronization
•
Follow these steps:
– Identify the data shared by processes and operations to be performed
on them
– Define a monitor type with the following features
* The shared data is declared in the data declaration section
* Initial values of the data are indicated in the initialization section
* Operations on the data are coded as procedures of the monitor type
 Condition variables are declared for process synchronization
 Monitor procedures use wait and signal statements to synchronize
processes that have invoked them
– Create objects of the monitor type (we call each of them a monitor)
– Create concurrent processes of the application
* These processes invoke operations of a monitor
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Condition variables
•
A condition in a monitor is analogous to an event in OS
– A condition variable is associated with a condition
– A queue of blocked processes is associated with a condition
* A procedure in the monitor can use a ‘condition variable.wait’
statement for process synchronization
 This statement blocks the process that had invoked the monitor
procedure
 It is entered in a queue associated with the condition variable
* A monitor procedure uses a ‘condition variable.signal’ statement to
signal occurrence of a condition
 The first process in the queue associated with the condition
variable is activated when the condition is signaled
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
A monitor implementing a binary semaphore
• non_busy is a condition variable
• Operations sem_signal and sem_wait perform wait and signal
operations on it under the correct conditions
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Monitor implementation of a binary semaphore
• The monitor type was
defined in the previous slide
• Operation sem_wait blocks
a process if some other
process is using the CS
implemented through
the semaphore
• Operation sem_signal
activates a blocked process
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Snapshot of the system using binary semaphores
•
•
•
•
Process P1 executed operation sem_wait and entered its CS
Process P2 executed operation sem_wait and got blocked
Process P1 is currently executing operation sem_signal
Process P3 wishes to execute sem_signal but gets blocked
due to mutual exclusion over operations of the semaphore
Q: What will be the next event in this system?
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Producers—consumers
using monitors
• Data consists of
buffers, prod_ptr,
cons_ptr and full
• The produce operation
blocks a process if all
buffers are full
• The consume operation
blocks a process if all
buffers are empty
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Disk scheduler: A case study of monitors
•
Design a monitor to implement a disk scheduler
– The disk scheduler uses a policy such as SCAN or C-SCAN to
perform scheduling of I/O requests (described in Chapter 12)
* A Process directs an I/O request at the disk scheduler through one
of the monitor operations
 It becomes blocked if some other I/O is in progress
* The disk scheduler stores the I/O requests in a data structure
– When an I/O request completes
* The scheduler activates the process that had initiated the I/O
request
* It also schedules a pending I/O request, if any, according to the
scheduling policy in force
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
User processes and the monitor variable
• Operation IO_request blocks a process until its I/O operation
is scheduled
• When scheduled, the process performs its I/O operation and
invokes operation IO_complete
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Monitor Disk_Mon_type
• A condition variable is associated
with each process
• Operation IO_request schedules
the requested I/O operation if no
other operations are pending;
otherwise, it queues the operation
and blocks the process through a
wait on its condition variable
• Operation IO_complete
schedules one of the queued
operations and activates the
process that had issued it
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
A snapshot of the disk monitor
• Processes make the following requests
Process
Track no
Time
P1
12
10
P2
85
50
P3 P4 P5
40 100 75
100 120 175
P6
55
0
• P6 is the first process to issue an I/O request; its request is
scheduled straightaway
• P1–P4 make their requests while P6’s I/O is in progress;
each of them is blocked on its own condition variable
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Monitors in Java
•
A class becomes a monitor type when the attribute
synchronized is associated with one of its methods
– Each monitor type contains a single unnamed condition variable
* Calls wait() and notify() are analogous to monitor operations wait
and signal
* Notifyall() activates all threads waiting on a condition variable
– When an application requires use of several conditions
* All these conditions are replaced by the unnamed condition
 Notifyall() has to be used to activate a process
 It wakes up all processes. Each process checks a condition to
decide whether it should go back to sleep
» This is a busy wait!
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Process synchronization in Unix
•
System V implements kernel-level semaphores
– A user specified key is associated with an array of semaphores;
all processes using this key share this semaphore array
– To reduce overhead, processes may place semaphores in
shared memory and perform wait / signal operations as in a
user-level implementation
* A process makes a system call only when it has to block itself or
activate another process
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Process synchronization in Unix
•
semop is the semaphore operation
– It identifies a semaphore array and issues several (subscript, op)
operations on semaphores in the array
– A process may wait on many semaphores simultaneously; it is
activated only when waits on all semaphores are satisfied
* This feature helps in avoiding deadlocks
– For a process, the kernel keeps track of all of its operations on a
semaphore. It performs an undo on these operations when the
process terminates
* It helps in ensuring reliability
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Process synchronization in Linux
•
Linux provides two special semaphores for kernel use
– Conventional semaphore, implemented with less overhead
* Indivisible instructions are used to increment / decrement a
semaphore’s value; it eliminates the need for a lock
* The waiting process flag reduces overhead of activating processes
– reader-writer semaphore to protect kernel data structures
* Entry to the CS is FIFO
•
Futex is a user-space mutex
– Represented in shared memory
* System calls are made only to activate or block processes
* A wait call fails when a specified amount of time is exceeded
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Process synchronization in Windows
•
Dispatcher objects are used for synchronization
– Each process, file and event object embeds a dispatcher object
* Hence synchronization can be performed on these entities
•
States of dispatcher objects
– Non-signaled state: A process performing a wait call on it gets
blocked
* When the state changes to Signaled, one or more waiting
processes are activated (see table)
– A process can specify a time interval in a wait call
•
Kernel provides several synchronization locks
– Spinlock, queued spinlock, fast mutex, push locks
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008
Windows synchronization objects
• A process enters the signaled state when the last thread in it
terminates; all processes blocked on it are activated
• An event enters the signaled state when it is set; all threads
blocked on it are activated
Chapter 9:
Process Synchronization
Dhamdhere: Operating Systems—
A Concept-Based Approach, 2 ed
Slide No: ‹#›
Copyright © 2008