Transcript PPT Chapter 06

Chapter 6
Process Synchronization
Copyright © 2008
Introduction
•
•
•
•
•
•
What is Process Synchronization?
Race Conditions
Critical Sections
Control Synchronization and Indivisible Operations
Synchronization Approaches
Structure of Concurrent Systems
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.2
2
Introduction (continued)
•
•
•
•
•
Classic Process Synchronization Problems
Algorithmic Approach to Implementing Critical Sections
Semaphores
Monitors
Case Studies of Process Synchronization
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.3
3
What is Process Synchronization?
• The term process is a generic term for both a process
and a thread
• Processes that do not interact are independent
processes
• Process synchronization is a generic term for the
techniques used to delay and resume processes to
implement process interactions
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.4
4
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.5
5
Race Conditions
• Uncoordinated accesses to shared data may affect
consistency of data
• Consider processes Pi and Pj that update the value of
ds through operations ai and aj , respectively:
Operation ai : ds := ds + 10; Let fi(ds) represent its result
Operation aj : ds := ds + 5; Let fj(ds) represent its result
– What situation could arise if they execute concurrently?
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.6
6
An Example of Race Condition
Race conditions
in cases 2 and 3
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.7
7
Race Conditions (continued)
• Race conditions in Figure 6.2 are prevented by
ensuring that operations ai and aj of Definition 6.2 do
not execute concurrently
– This is called mutual exclusion
• Data access synchronization is coordination of
processes to implement mutual exclusion over shared
data
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.8
8
Critical Sections
• Mutual exclusion is implemented by using critical
sections (CS) of code
• Using CSs causes delays in operation of processes
– Process must not execute for too long inside CS
– Process must not make system calls while in the CS that
might put it in blocked state
– Kernel must not preempt a process that is engaged in
executing a CS
• We use a dashed box in the code to mark a CS
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.9
9
Critical Sections (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.10
10
Properties of a Critical Section
Implementation
• The progress and bounded wait properties together
prevent starvation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.11
11
Control Synchronization and Indivisible
Operations
• Interacting processes need to coordinate their
execution with respect to one another, to perform their
actions in a desired order
– Requirement met through control synchronization
– Signaling is a general technique of control
synchronization
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.12
12
Control Synchronization and Indivisible
Operations (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.13
13
Control Synchronization and Indivisible
Operations (continued)
• Naive signaling in previous example does not work
– Pi may face indefinite blocking in some situations
• Use indivisible or atomic operations instead
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.14
14
Control Synchronization and Indivisible
Operations (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.15
15
Synchronization Approaches
• Looping versus Blocking
• Hardware Support for Process Synchronization
• Algorithmic Approaches, Synchronization Primitives,
and Concurrent Programming Constructs
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.16
16
Looping versus Blocking
• Busy wait:
• A busy wait has many consequences
–
–
–
–
Cannot provide the bounded wait property
System performance degradation due to looping
Deadlock
Priority inversion
• Typically addressed through the priority inheritance protocol
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.17
17
Looping versus Blocking (continued)
• To avoid busy waits, a process waiting for entry to a CS
is put in blocked state
– Changed to ready only when it can enter the CS
• Process decides to loop or block
– Decision is subject to race conditions. Avoided through
• Algorithmic approach
• Use of computer hardware features
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.18
18
Hardware Support for Process
Synchronization
• Indivisible instructions
– Avoid race conditions on memory locations
• Used with a lock variable to implement CS and
indivisible operations
– entry_test performed with indivisible instruction
• Test-and-set (TS) instruction
• Swap instruction
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.19
19
Hardware Support for Process
Synchronization (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.20
20
Algorithmic Approaches,
Synchronization Primitives, and
Concurrent Programming Constructs
• Algorithmic Approaches
– For implementing mutual exclusion
– Independent of hardware or software platform
• Busy waiting for synchronization
• Synchronization Primitives
– Implemented using indivisible instructions
– E.g., wait and signal of semaphores
• Problem: can be used haphazardly
• Concurrent Programming Constructs
– Monitors
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.21
21
Structure of Concurrent Systems
• Three key components:
– Shared data
• Application data used and manipulated by processes
• Synchronization data
– Operations on shared data
• Convenient unit of code which accesses and manipulates
shared data
– A synchronization operation is on synchronization data
– Interacting processes
• A snapshot of a concurrent system is a view of the
system at a specific time instant
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.22
22
Structure of Concurrent Systems
(continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.23
23
Example: Snapshots of a Concurrent
System
(a) Pi performs operation check_aj
(b) Pi is blocked; Pj performs operation post_aj
(c) post_aj activates Pi; Pj exits post_aj
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.24
24
Classic Process Synchronization
Problems
• A solution to a process synchronization problem should
meet three important criteria:
– Correctness
– Maximum concurrency
– No busy waits
• Some classic problems:
– Producers-Consumers with Bounded Buffers
– Readers and Writers
– Dining Philosophers
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.25
25
Producers-Consumers with Bounded
Buffers
•
A solution must satisfy the following:
1. A producer must not overwrite a full buffer
2. A consumer must not consume an empty buffer
3. Producers and consumers must access buffers in a
mutually exclusive manner
4. (Optional) Information must be consumed in the same
order in which it is put into the buffers
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.26
26
Producers-Consumers with Bounded
Buffers (continued)
• Suffers from two problems:
– Poor concurrency and busy waits
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.27
27
Producers-Consumers with Bounded
Buffers (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.28
28
Producers-Consumers with Bounded
Buffers (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.29
29
Readers and Writers
•
A solution must satisfy the following:
1.
2.
3.
4.
Many readers can perform reading concurrently
Reading is prohibited while a writer is writing
Only one writer can perform writing at any time
(optional) A reader has a nonpreemptive priority over
writers
─ Called readers preferred readers–writers system
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.30
30
Readers and Writers (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.31
31
Dining Philosophers
• Design processes to represent the philosophers so that
each philosopher can eat when hungry and none dies
of hunger
– Solution shouldn’t suffer from deadlocks or livelocks
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.32
32
Dining Philosophers (continued)
• Prone to deadlocks and race conditions, unless:
– If right fork is unavailable, release left fork, retry later
• It suffers from livelocks
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.33
33
Dining Philosophers (continued)
• Problem: loop causes a busy wait condition
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.34
34
Algorithmic Approach to Implementing
Critical Sections
• Two-Process Algorithms
• n-Process Algorithms
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.35
35
Two-Process Algorithms
• Violates the progress condition
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.36
36
Two-Process Algorithms (continued)
• Violates mutual exclusion condition
• Can lead to deadlock
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.37
37
Turn is effective only when
Both processes try to enter
CS at the same time
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.38
38
Two-Process Algorithms (continued)
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.39
39
n-Process Algorithms
Contains a certain form of
unfairness since processes do
not enter their CSs in the same
order in which they requested
entry to a CS.
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.40
40
(number[j],j) < number[i],i) if
number[j] < number[i], or
number[j] = number[i] and j < i
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.41
41
Semaphores
• Also called counting semaphores due to operations on S
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.42
42
Uses of Semaphores in Concurrent
Systems
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.43
43
Uses: Mutual Exclusion
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.44
44
Uses: Bounded Concurrency
• Implemented by initializing a semaphore sem_c to c
• Every process wishing to perform opi performs a
wait(sem_c) before performing opi and a signal(sem_c)
after performing it
• Up to c processes can concurrently perform opi
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.45
45
Uses: Signaling between Processes
• Race conditions cannot arise because the wait and
signal operations are indivisible
• Binary semaphore: Can have values 0 and 1 only
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.46
46
Producers-Consumers Using
Semaphores
• Avoids busy waits since semaphores are used to check
for empty or full buffers
• Total concurrency in system is 1
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.47
47
Example: Producers-Consumers with
a Single Buffer through Semaphores
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.48
48
Producers-Consumers Using
Semaphores (continued)
• Solution to n-buffer producers–consumers problem:
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.49
49
Readers-Writers Using Semaphores
• Significance of counters:
– runread: Number of readers reading
– totread: Number of readers wishing to read or reading
– Similarly runwrite and totwrite
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.50
50
Implementation of Semaphores
Implementations of wait and signal:
• Kernel-Level: Through system calls
• User-Level: System calls only to
block/activate
• Hybrid: Combination of the two
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.52
52
Monitors
• A monitor type resembles a class in a language like
C++ or Java
– Contains declarations of shared data
– Its procedures encode operations that manipulate shared
data and implement process synchronization
• A condition is a situation of interest in a monitor
• A condition variable is associated with a condition
• A process executing a wait operation on condition variable
is blocked until some process performs a signal operation
• In a concurrent system, processes share data by
creating a monitor object
– We call it simply monitor
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.53
53
Example: Monitor Implementation of a
Binary Semaphore
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.54
54
Example: Producers-Consumers
Using Monitors
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.55
55
Monitors in Java
• A Java class becomes a monitor type when the
attribute synchronized is associated with one or more
methods in the class
• An object of such a class is a monitor
• Each monitor contains a single unnamed condition
variable
– Can lead to busy waits in an application that has many
conditions
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.56
56
Case Studies of Process
Synchronization
•
•
•
•
•
Synchronization of POSIX Threads
Process Synchronization in Unix
Process Synchronization in Linux
Process Synchronization in Solaris
Process Synchronization in Windows
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.57
57
Synchronization of POSIX Threads
• POSIX threads provide:
– Mutexes for mutual exclusion
• A mutex is a binary semaphore
– Condition variables for control synchronization between
processes
• An OS may implement POSIX threads as kernel-level
threads or user-level threads
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.58
58
Process Synchronization in Unix
• Unix system V provides a kernel-level implementation
of semaphores
– Name of a semaphore is called a key
• Key is associated with an array of semaphores
• Processes share a semaphore by using the same key
• Unix SVR4 keeps track of all operations performed by a
process on each semaphore used by it
– Performs an undo on them when process terminates
– It helps to make programs more reliable
• Unix 4.4BSD places a semaphore in shared memory
areas and uses a hybrid implementation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.59
59
Process Synchronization in Linux
• Linux has Unix-like semaphore for user processes
• Also provides semaphores for use by the kernel:
– Conventional semaphore
• Uses efficient kernel-level implementation scheme
– Reader–writer semaphore
• Kernels older than 2.6 implemented mutual exclusion in
the kernel space through system calls
• 2.6 kernel has a fast user space mutex called futex
– Uses a hybrid implementation
– Provides time-bound wait operation
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.60
60
Process Synchronization in Solaris
• Interesting features:
– Reader–writer semaphores
• Analogous to the one in Linux
– Adaptive mutexes
• Useful in a multiprocessor OS
– Uses the priority inheritance protocol to reduce
synchronization delays
– Data structure called a turnstile
• Holds information concerning threads that are blocked on a
mutex or reader–writer semaphore
– Used for synchronization and priority inheritance
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.61
61
Process synchronization in Windows
• Dispatcher object is embedded in every object over
which synchronization is needed
– It can be in signaled/nonsignaled state
– Dispatcher objects used in process, file, etc. (next slide)
• Provides spinlock, queued spinlock, fast mutex and
push locks
• Vista provides a reader-writer lock
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.62
62
Process Synchronization in Windows
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.63
63
Summary
• Process synchronization is a generic term for data
access synchronization and control synchronization
• A race condition occurs when actions of concurrent
processes may have unexpected consequences
– Avoided through mutual exclusion
• Avoidance of race conditions is a primary issue in
process synchronization
• Critical section: section of code that accesses some
shared data in a mutually exclusive manner
• Synchronization achieved through: indivisible
instructions, semaphores, monitors
Operating Systems, by Dhananjay Dhamdhere
Copyright © 2008
6.64
64