Transcript Module 7: Process Synchronization

Chapter 6: Process
Synchronization
Module 6: Process Synchronization
n Background
n The Critical-Section Problem
n Peterson’s Solution
n Synchronization Hardware
n Semaphores
n Classic Problems of Synchronization
n Monitors
n Synchronization Examples
n Atomic Transactions
Background
n Concurrent access to shared data may result in
data inconsistency
n Maintaining data consistency requires mechanisms
to ensure the orderly execution of cooperating
processes
n Suppose that we wanted to provide a solution to the
consumer-producer problem that fills all the buffers
rather than BUFFER_SIZE-1 items. We can do so
by having an integer count that keeps track of the
number of full buffers. Initially, count is set to 0. It is
incremented by the producer after it produces a
new buffer and is decremented by the consumer
after it consumes a buffer.
Producer
while (true) {
/* produce an item and put in nextProduced */
while (count == BUFFER_SIZE)
; // do nothing
buffer [in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
count++;
}
Consumer
while (true) {
while (count == 0)
; // do nothing
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;
/* consume the item in nextConsumed
}
Race Condition
n
count++ could be implemented as
register1 = count
register1 = register1 + 1
count = register1
n count-- could be implemented as
register2 = count
register2 = register2 - 1
count = register2
n
Consider this execution interleaving with “count = 5” initially:
S0: producer execute register1 = count {register1 = 5}
S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}
n To guard against the race condition, we need to ensure that only
one process at a time can be manipulating the variable count. We
require that processes be synchronized in some way.
Solution to Critical-Section Problem
n
The section of code implementing request to enter its critical
section is entry section. The critical section may be followed by
an exit section. The remaining code is the remainder section.
n
Solution must satisfy three requirements:
1. Mutual Exclusion - If process Pi is executing in its critical section,
then no other processes can be executing in their critical sections
2. Progress - If no process is executing in its critical section and
there exist some processes that wish to enter their critical section,
then the selection of the processes that will enter the critical
section next cannot be postponed indefinitely
3. Bounded Waiting - A bound must exist on the number of times
that other processes are allowed to enter their critical sections
after a process has made a request to enter its critical section and
before that request is granted


Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the N processes
Critical Section Problem
n E.g. if two processes were to open files simultaneously, the
separate updates to the kernel data structure, a list of all open
files, could result in a race condition.
n To handle critical sections in operating systems
l
Preemptive kernels – that allows a process to be
preempted while it is running in kernel mode
l
Nonpreemptive kernels – a kernel-mode process will run
until it exits kernel mode, blocks, or voluntarily yields
control of the CPU. Essentially free from race conditions on
kernel data structures, as only one process is active in the
kernel at a time.
n A preemptive kernel is more responsive, more suitable for
real-time programming, but difficult to design (especially for
SMP architectures, since in these environments it is possible
for two kernel-mode processes to run simultaneously on
different processors).
n Windows XP is nonpreemptive, with 2.6 Linux is preemptive.
Peterson’s Solution
Two process software-based solution
n Assume that the LOAD and STORE instructions are atomic; that is, cannot
be interrupted.
n The two processes share two variables:
l int turn;
n
Boolean flag[2]
The variable turn indicates whose turn it is to enter the critical section.
The flag array is used to indicate if a process is ready to enter the critical
section. flag[i] = true implies that process Pi is ready!
To enter the critical section, process Pi first sets flag[i] to be true and
then set turn to the value j (other process), thereby asserting that if the
other process wishes to enter the critical section, it can do so. If both
processes try to enter at the same time, turn will be set to both i and j at
about the same time. The last value of turn decides which of the two
processes is allowed to enter first.
One process (say Pj) must have successfully executed the while
statement, whereas Pi had to execute (“turn==j”). Since at that time,
flag[j]==true, and turn==j, and this condition will persist as long as
Pj is in its critical section. So “mutual exclusion is preserved”.
l
n
n
n
n
Peterson’s Solution
n A process Pi can be prevented from entering the critical section only if
it is stuck in the while loop with the condition flag[j] == true
and turn==j.
n If Pj is not ready to enter the critical section, flag[j]==false, and Pi
can enter its critical section.
n If Pj has set flag[j] to true and is also executing in its while
statement, then either turn==i or turn==j allowing only one of
them to enter the critical section.
n However, say once Pj exits its critical section, it will reset flag[j] to
false, allowing Pi to enter its critical section.
n If Pj resets flag[j] to true, it must also set turn to i.
n Thus, since Pi does not change the value of the variable turn while
executing the while statement,
l
Pi will enter the critical section (progress)
l
after at most one entry by Pj (bounded waiting)
Algorithm for Process Pi
while (true) {
flag[i] = TRUE;
turn = j;
while ( flag[j] && turn == j);
CRITICAL SECTION
flag[i] = FALSE;
REMAINDER SECTION
}
Synchronization Hardware
n A process must acquire a lock before entering a critical
section; it releases the lock when it exits the critical section.
n Many systems provide hardware support for critical section
code
n Uniprocessors – could disable interrupts
l Currently running code would execute without preemption
l Generally too inefficient on multiprocessor systems
 Operating systems using this not broadly scalable
n Modern machines provide special atomic hardware
instructions
 Atomic = non-interruptable
l Either test memory word and set value
l Or swap contents of two memory words
TestAndSet Instruction
n Definition:
boolean TestAndSet (boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv:
}
Solution using TestAndSet
n Shared boolean variable lock., initialized to false.
n Solution:
while (true) {
while ( TestAndSet (&lock ))
; /* do nothing
//
critical section
lock = FALSE;
//
}
remainder section
Swap Instruction
n Definition:
void Swap (boolean *a, boolean *b)
{
boolean temp = *a;
*a = *b;
*b = temp:
}
Solution using Swap
n Shared Boolean variable lock initialized to FALSE; Each
process has a local Boolean variable key.
n Solution:
while (true) {
key = TRUE;
while ( key == TRUE)
Swap (&lock, &key );
//
critical section
lock = FALSE;
//
}
remainder section
Problem with them
n Although these algorithms satisfy the mutual-exclusion
requirement, they do not satisfy the bounded-waiting
requirement.
n Next example solves these problems.
n The common data structures (initialized to false) are
boolean waiting[n];
boolean lock;
Semaphore
Synchronization tool that does not require busy waiting
n Semaphore S – integer variable
n Two standard operations modify S: wait() and signal()
n
l
Originally called P() and V()
Less complicated
n Can only be accessed via two indivisible (atomic) operations
n
l
l
wait (S) {
while S <= 0
; // no-op
S--;
}
signal (S) {
S++;
}
Semaphore as General Synchronization
Tool
n Counting semaphore – integer value can range over an
unrestricted domain
n Binary semaphore – integer value can range only between 0
and 1; can be simpler to implement
l
Also known as mutex locks
n Can implement a counting semaphore S as a binary
semaphore
n Provides mutual exclusion
l
Semaphore S;
l
wait (S);
// initialized to 1
Critical Section
signal (S);
Semaphore Usage
n Counting semaphores can be used to control access to a
given resource consisting of a finite number of instances.
n The semaphore is initialized to the number of resources
available.
n Each process that wishes to use a resource performs a
wait() operation on the semaphore (decrementing the
count).
n When a process releases a resource, it performs a
signal() operation (incrementing the count).
n When the count for the semaphore goes to 0, all resources
are being used. After that, processes that wish to use a
resource will block until the count becomes greater than 0.
Semaphore Implementation
n Must guarantee that no two processes can execute wait
() and signal () on the same semaphore at the same time
n Thus, implementation becomes the critical section
problem where the wait and signal code are placed in
the critical section.
l
Could now have busy waiting in critical section
implementation
 But
implementation code is short
 Little
busy waiting if critical section rarely
occupied
n Note that applications may spend lots of time in critical
sections and therefore this is not a good solution.
n This type of semaphore is also called a spinlock
because the process “spins” while waiting for the lock
Spinlocks
n Have an advantage in that no context switch is required
when a process must wait on a lock.
n When locks are expected to be held for short times,
spinlocks are useful.
n They are often employed on multiprocessor systems where
one thread can “spin” on one processor while another thread
performs its critical section on another processor.
Semaphore Implementation with no Busy
waiting
n Rather than engaging in busy waiting, process blocks
itself.
n With each semaphore there is an associated waiting
queue. Each entry in a waiting queue has two data
items:
l
value (of type integer)
l
pointer to next record (PCB) in the list
n Two operations:
l
block – place the process invoking the operation on
the
appropriate waiting queue.
l
wakeup – remove one of processes in the waiting
queue and place it in the ready queue.
n This implementation may have negative semaphore
values. If the semaphore value is negative, its magnitude
is the number of processes waiting on that semaphore.
Semaphore Implementation with no Busy
waiting (Cont.)
n
Implementation of wait:
wait (S){
value--;
if (value < 0) {
add this process to waiting queue
block(); }
}
n
Implementation of signal:
signal (S){
value++;
if (value <= 0) {
remove a process P from the waiting queue
wakeup(P); }
}
Semaphore Implementation with no Busy waiting (Cont.)
n
Semaphores should be executed atomically.
n
On a single-processor environment, we can solve it by simply
inhibiting interrupts during the time the wait() and signal()
executes.
n
In a multiprocessor environment, this wastes times and hence SMP
systems provide alternative locking techniques—such as spinlocks—to
ensure the atomicity of wait() and signal().
n
With this definition of wait() and signal(), we have removed busy
waiting from the entry section to the critical sections.
n
Furthermore, we have limited busy waiting to the critical sections of
the wait() and signal() operations which are short.
n
For applications with long critical sections, busy waiting is inefficient.
Deadlock and Starvation
n Deadlock – two or more processes are waiting indefinitely
for an event that can be caused by only one of the waiting
processes
n Let S and Q be two semaphores initialized to 1
P0
P1
wait (S);
wait (Q);
wait (Q);
.
.
.
wait (S);
.
.
.
signal (S);
signal (Q);
signal (Q);
signal (S);
n Starvation – indefinite blocking. A process may never be
removed from the semaphore queue in which it is
suspended.
Bounded-Buffer Problem
n N buffers, each can hold one item
n Semaphore mutex initialized to the value 1
l
Provides mutual exclusion for accesses to the buffer
pool
n Semaphore full initialized to the value 0
l
Number of full buffers
n Semaphore empty initialized to the value N.
l
Number of empty buffers
Bounded Buffer Problem (Cont.)
n
The structure of the producer process
while (true) {
The structure of the consumer process
while (true) {
wait (full);
// produce an item
wait (mutex);
wait (empty);
// remove an item from buffer
wait (mutex);
signal (mutex);
// add the item to the buffer
signal (empty);
signal (mutex);
// consume the removed item
signal (full);
}
}
Readers-Writers Problem
A data set is shared among a number of concurrent processes
Readers – only read the data set; they do not perform any updates
Writers – can both read and write.
Problem – allow multiple readers to read at the same time. Only one
single writer can access the shared data at the same time (exclusive
access)
Variations:
First readers-writers problem: Requires that no reader will be kept
waiting unless a writer has already obtained permission to use the
shared object. No reader should wait for other readers to finish
simply because a writer is waiting.
Second readers-writers problem: Requires that once a writer is
ready, that writer performs its write as soon as possible. If a writer is
waiting to access the object, no new readers may start reading.
In the first case writers may starve; in the second case, readers may
starve. We present a solution to the first readers-writers problem.
Readers-Writers Problem
Shared Data
Data set
Semaphore mutex initialized to 1.

Ensures mutual exclusion when readcount is updated.
Semaphore wrt initialized to 1.

A mutual exclusion semaphore for the writers. Also used by the
first or last reader that enters or exits the critical section.
Integer readcount initialized to 0.

Keeps track of how many processes are currently reading the
object.
If a writer is in the critical section and n readers waiting, then one reader
is queued on wrt, and n-1 readers are queued on mutex.
When a writer executes signal(wrt), we may resume the execution
of either the waiting readers or a single waiting writer. The selection is
made by the scheduler.
Readers-Writers Problem (Cont.)
The structure of a writer process
while (true) {
wait (wrt) ;
//
writing is performed
The structure of a reader process
while (true) {
wait (mutex) ;
readcount ++ ;
if (readcount == 1) wait (wrt) ;
signal (mutex)
// reading is performed
signal (wrt) ;
}
wait (mutex) ;
readcount - - ;
if (readcount == 0) signal (wrt) ;
signal (mutex) ;
}
Problems with Semaphores
Incorrect use of semaphore operations:
signal (mutex) ... Critical section ... wait (mutex)
 Several
processes may be executing in their critical
sections
wait (mutex) … Critical section ... wait (mutex)
A
deadlock will occur
Omitting of wait (mutex) or signal (mutex) (or both)
 Either
occur
mutual exclusion is violated or a deadlock will
Atomic Transactions
System Model
Log-based Recovery
Checkpoints
Concurrent Atomic Transactions
If two critical sections are executed concurrently, the result is
equivalent to their sequential execution in some unknown
order.
System Model
Assures that operations happen as a single logical unit of
work, in its entirety, or not at all
Related to field of database systems
Challenge is assuring atomicity despite computer system
failures
Transaction - collection of instructions or operations that
performs single logical function
Here we are concerned with changes to stable storage –
disk
Transaction is series of read and write operations
Terminated by commit (transaction successful) or abort
(transaction failed) operation
Aborted transaction must be rolled back to undo any
changes it performed
Types of Storage Media
Volatile storage – information stored here does not survive
system crashes
Example: main memory, cache
Nonvolatile storage – Information usually survives crashes
Example: disk and tape
Stable storage – Information never lost
Not actually possible, so approximated via replication or
RAID to devices with independent failure modes
Goal is to assure transaction atomicity where failures cause loss of
information on volatile storage
Log-Based Recovery
Record to stable storage information about all modifications
by a transaction
Most common is write-ahead logging
Log on stable storage, each log record describes single
transaction write operation, including
 Transaction
 Data
 Old
name (performing the write operation)
item name
value
 New
value
<Ti starts> written to log when transaction Ti starts
<Ti commits> written when Ti commits
Log entry must reach stable storage before
operation on data occurs
Performance and space penalty may worth the functionality
Log-Based Recovery Algorithm
Using the log, system can handle any volatile memory errors
Undo(Ti) restores value of all data updated by Ti to old
values
Redo(Ti) sets values of all data in transaction Ti to new
values
Undo(Ti) and redo(Ti) must be idempotent
Multiple executions must have the same result as one
execution even if a failure occurs during the recovery
process
If system fails, restore state of all updated data via log
If log contains <Ti starts> without <Ti commits>, undo(Ti)
If log contains <Ti starts> and <Ti commits>, redo(Ti)
Checkpoints
Log could become long, and recovery could take long
To determine those transactions that need to be redone
and those that need to be undone needs to search
entire log.
Most of the transactions that, according to our algorithm,
need to be redone have already actually updated the
data that the log says they need to modify. Redoing
cause no harm due to idempotency but, recovery take
longer.
Checkpoints shorten log and recovery time.
Checkpoints
Checkpoint scheme:
1.
Output all log records currently in volatile storage to
stable storage
2.
Output all modified data from volatile to stable storage
3.
Output a log record <checkpoint> to the log on stable
storage
First <checkpoint> recorded in the log backward and the
subsequent <Ti start> record is found.
Now recovery only includes Ti, such that Ti started
executing before the most recent checkpoint, and all
transactions after Ti All other transactions already on stable
storage
The recovery operations required are as follows:
For all transactions Tk in T such that the record <Tk
commits> appears in the log, execute redo(Tk).
For all transactions Tk in T that have no <Tk commits>
record in the log, execute undo (Tk).
Concurrent Transactions
Must be equivalent to serial execution – serializability
Could perform all transactions in critical section
All transactions share a common semaphore mutex.
Inefficient, too restrictive
Concurrency-control algorithms provide serializability
Serializability
Consider two data items A and B
Consider Transactions T0 and T1
Execute T0, T1 atomically
Execution sequence called schedule
Atomically executed transaction order called serial schedule
A serial schedule consists of a sequence of a sequence of
instructions from various transactions wherein the
instructions belonging to a particular transaction appear
together.
For N transactions, there are N! valid serial schedules
Schedule 1: T0 then T1
Nonserial Schedule
Nonserial schedule allows overlapped execute
Resulting execution not necessarily incorrect
Consider schedule S, operations Oi, Oj
Conflict if access same data item, with at least one write
If Oi, Oj consecutive and operations of different transactions
& Oi and Oj don’t conflict
Then S’ with swapped order Oj Oi equivalent to S
If S can become a serial schedule S’ via swapping
nonconflicting operations
S is conflict serializable
Schedule 2: Concurrent Serializable
Schedule
Schedule 2: Concurrent Serializable
Schedule
As the write(A) operation of T1 does not conflict with the
read(B) operation of T0, we can swap them to generate an
equivalent schedule. Continuing with this procedure:
Swap the read(B) operation of T0 with the read(A) operation of
T1.
Swap the write(B) operation of T0 with the write(A) operation
of T1.
Swap the write(B) operation of T0 with the read(A) operation
of T1.
The final result is equal to schedule 1 which is a serial schedule.
Locking Protocol
Ensure serializability by associating lock with each data item
Follow locking protocol for access control
Locks
Shared – Ti has shared-mode lock (S) on item Q, Ti can
read Q but not write Q
Exclusive – Ti has exclusive-mode lock (X) on Q, Ti can
read and write Q
Require every transaction on item Q acquire appropriate
lock
If lock already held, new request may have to wait.
E.g. if Ti requests a shared lock on Q, then Ti must wait
if Q is locked in exclusive mode. Otherwise it can obtain
the lock.
Similar to readers-writers algorithm
Two-phase Locking Protocol
A transaction must hold a lock on a data item as long as it
accesses that item. Moreover, it is not always desirable for a
transaction to unlock a data item immediately after its last
access of that data item, because serializability may not be
ensured.
Two-phase locking pr. generally ensures conflict
serializability
Each transaction issues lock and unlock requests in two
phases
Growing – obtaining locks
Shrinking – releasing locks
Does not prevent deadlock
In addition, it is possible that, for a given set of transactions,
there are conflict-serializable schedules that cannot be
obtained by use of the two-phase locking protocol
End of Chapter 6