operating system
moqwerlop
Ch6.pdf
CMET 331 Operating Systems
6. Process Synchronization
Objectives
• To introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data.
• To present both software and hardware solutions of the critical-section problem.
• To introduce the concept of atomic transaction and describe mechanisms to ensure atomicity.
Synchronization
• Guarantee that one step should occur before/after another
The Problem with Concurrent Execution
• Concurrent processes (or threads) often need access to shared data and shared resources.
• If there is no controlled access to shared data, it is possible to obtain an inconsistent view of this data.
• Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes.
• Let us assume that two threads T1 and T2 each want to increment the value of a global integer by one.
• Ideally, the following sequence of operations would take place:
1. Integer i = 0; 2. T1 reads the value of i from
memory into a register : 0 3. T1 increments the value of i in the
register: (register contents) + 1 = 1
4. T1 stores the value of the register in memory : 1
5. T2 reads the value of i from memory into a register : 1
6. T2 increments the value of i in the register: (register contents) + 1 = 2
7. T2 stores the value of the register in memory : 2
8. Integer i = 2
Race Conditions - Simple Example
• If the two threads run simultaneously without locking or synchronization, the outcome of the operation could be wrong.
• The alternative sequence of operations below demonstrates
this scenario:
Race Conditions - Simple Example (cont.)
1. Integer i = 0; 2. T1 reads the value of i from memory into a register : 0 3. T2 reads the value of i from memory into a register : 0 4. T1 increments the value of i in the register: (register contents) + 1 = 1 5. T2 increments the value of i in the register: (register contents) + 1 = 1 6. T1 stores the value of the register in memory : 1 7. T2 stores the value of the register in memory : 1 8. Integer i = 1
Race Condition
• A race condition is a flaw in a system or process whereby the output of the process is unexpectedly and critically dependent on the sequence or timing of other events.
Critical Sections
• That part of the program where the shared memory is accessed is called the critical region or critical section.
• The key to preventing trouble is to find some way to prohibit more than one process from reading and writing the shared data at the same time.
• If we could arrange matters such that no two processes were ever in their critical regions at the same time, we could avoid race conditions.
The Critical Section Problem • n processes are competing to use some shared data. • Each process has a code segment, called critical section,
in which the shared data is accessed. • Goal: when one process is executing in its critical
section, no other process can execute in its critical section.
• Each process looks like this:
while (true) { entry section
critical section - CS exit section
remainder section - RS }
Solution to Critical-Section Problem
Three Conditions to meet:
1. Mutual Exclusion - No two processes may be simultaneously inside their critical regions.
2. Progress - No process running outside its critical region may block other processes.
3. Bounded Waiting - No process should have to wait forever to enter its critical region.
Solution to the critical-section problem using locks
Critical Region and Locking
critical region
critical regionlock
unlock
critical regionlock
critical regionunlock
• Software solutions —Algorithms whose correctness does not rely on any
assumptions other than positive processing speed (that may mean no failure).
—Busy waiting.
• Hardware solutions —Rely on some special machine instructions.
• Operating system solutions —Extending hardware solutions to provide some
functions and data structure support to the programmer.
Types of Solutions
Mutual Exclusion with Busy Waiting
Mutual exclusion using critical regions.
Peterson’s Solution
• Two process solution
• Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted.
• The two processes share two variables:
—int turn;
—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!
Algorithm for Process Pi while (true) {
flag[i] = TRUE;
turn = j;
while ( flag[j] && turn == j); //wait
CRITICAL SECTION
flag[i] = FALSE;
REMAINDER SECTION
}
Entry Section
Exit Section
Algorithm for Process P0, P1 //flag[ ] is Boolean array; and turn is an integer
flag[0] = false; flag[1] = false; turn;
P0: flag[0] = true; turn = 1; while (flag[1] && turn == 1) { // busy wait } // critical section ... // end of critical section flag[0] = false;
P1: flag[1] = true; turn = 0; while (flag[0] && turn == 0) { // busy wait } // critical section ... // end of critical section flag[1] = false;
• Mutual exclusion - good.
• Progress - good.
• Bounded time - good.
BUT: It only works for two processes!
Peterson’s Solution
Synchronization Hardware
• Many systems provide hardware support for critical section code
• Uniprocessors – could disable interrupts
— Currently running code would execute without preemption
— Generally too inefficient on multiprocessor systems
• Operating systems using this not broadly scalable
• Modern machines provide special atomic hardware instructions
• Atomic = non-interruptable
— Either test memory word and set value
— Or swap contents of two memory words
• Correct solution for a uni-processor machine.
• During critical section multiprogramming is not utilized - performance penalty.
• On a multiprocessor machine the solution is not correct.
Repeat
disable interrupts
critical section
enable interrupts
remainder section
Forever
Hardware Solution - Disable Interrupts
Hardware Solutions - TestAndSet Instruction
• Test and Set Instruction
—In one instruction cycle: Reg lock and lock Reg
—= swap (memory location, register)
• Use Test-and-Set for mutual exclusion R := true;
repeat Test-and-Set (R, lock);
until R = false;
< critical section >;
lock := false;
—Perform check and set in one instruction cycle
Hardware Solutions - Swap Instruction
• Swap Instruction Swap (a, b) —in one instruction cycle: a b and b a
• Use Swap for mutual exclusion local_lock := true;
repeat Swap (lock, local_lock);
until local_lock = false;
< critical section >
lock := false;
Semaphore - OS support for mutual exclusion
• Special variable called a semaphore is used for signaling
• If a process is waiting for a signal, it is suspended until that signal is sent
Semaphores • Semaphore is a variable that has an integer value
— May be initialized to a nonnegative number — Wait operation decrements the semaphore value — Signal operation increments semaphore value
—wait (S) {
while S <= 0 ; // no-op S--;
} — signal (S)
{ S++;
}
Semaphore as General Synchronization Tool
• Counting semaphore – integer value S is a counter for a set of available resources, rather than a locked/unlocked flag of a single resource
• Binary semaphore – integer value S can range only between 0 and 1; can be simpler to implement —Also known as mutex locks
• Provides mutual exclusion Semaphore S; // initialized to 1
wait (S);
Critical Section
signal (S);
Semaphore Usage Example
• Solve synchronization problems
—Example: Ensure process P2 executes only after process P1 completes
—Initialize binary semaphore synch = 0 • P2:
Wait(synch);
Statements2;
• P1:
Statements1;
signal(synch);
Semaphore Implementation
• The main disadvantage of the semaphore definition given here is that it requires busy waiting
—While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the entry code. It is also spinlock.
—Busy waiting wastes CPU cycles that some other process might be able to use productively
—An advantage in that no context switch
Semaphore Implementation with no Busy waiting
• With each semaphore there is an associated waiting queue. Each entry in a waiting queue has two data items: — value (of type integer)
— pointer to next record in the list
• Two operations: —block – place the process invoking the operation on
the appropriate waiting queue.
—wakeup – remove one of processes in the waiting queue and place it in the ready queue.
Semaphore Implementation with no
Busy waiting (Cont.) • Implementation of wait:
wait (S){ value--; if (value < 0) {
add this process to waiting queue block(); }
}
• Implementation of signal:
Signal (S){ value++; if (value >= 0) {
remove a process P from the waiting queue wakeup(P); }
}
Deadlock • Deadlock – two or more processes are waiting
indefinitely for an event that can be caused by only one of the waiting processes
• 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);
Starvation
• Starvation – indefinite blocking.
—A process may never be removed from the semaphore queue in which it is suspended.
—Can happen if processes are removed from the waiting queue in LIFO order
Classical Problems of Synchronization
• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem
Producer/Consumer Problem
• One or more producers are generating data and placing these in a buffer
• A single consumer is taking items out of the buffer one at time
• Only one producer or consumer may access the buffer at any one time
Bounded Buffer Problem
...
out
in n slots
# occupied slots = count
Initialization int count = 0 int in = out = 0
Bounded Buffer Problem
process consumer;
repeat
while count = 0 do nothing;
item := buffer[out];
out := (out+1) mod n;
count := count 1;
consume item;
until forever
process producer;
repeat
produce item;
while count = n do nothing;
buffer[in] := item;
in := (in+1) mod n;
count := count + 1;
until forever
Init: count = 9; n = 10 A: load count -- count = 9 B: load count -- count = 9 A: add count -- count = 10 B: add count -- count = 10 Wrong count!!!
Init: in = 5; A: buffer[5] := item_A; B: buffer[5] := item_B; Put in the same slot!!!
Bounded Buffer Problem
process consumer;
repeat
while count = 0 do nothing;
lock (lck);
item := buffer[out];
out := (out+1) mod n;
count := count 1;
unlock (lck);
consume item;
until forever
process producer;
repeat
produce item;
while count = n do nothing;
lock (lck);
buffer[in] := item;
in := (in+1) mod n;
count := count + 1;
unlock (lck);
until forever
Init: count = 9; n = 10 P1: check (count = n)
-- count = 9, not full P2: check (count = n)
-- count = 9, not full P2: get the lock
put item in buffer count = count + 1;
-- buffer full P1: buffer overflow
Put the while loop in
Bounded Buffer Problem
process consumer;
repeat
lock (lck);
while count = 0 do nothing;
item := buffer[out];
out := (out+1) mod n;
count := count 1;
unlock (lck);
consume item;
until forever
process producer;
repeat
produce item;
lock (lck);
while count = n do nothing;
buffer[in] := item;
in := (in+1) mod n;
count := count + 1;
unlock (lck);
until forever
Init: count = 10; n = 10; P: get the lock P: find count = 10, wait No one can enter CS Need to release lock
repeat lock(lck); localcounter := counter; if counter = n then
unlock(lck); until localcounter < n; Code can be messy
Use of Semaphores - Bounded Buffer Problem
process consumer;
repeat
wait (mutex);
while count = 0 do nothing;
item := buffer[out];
out := (out+1) mod n;
count := count 1;
signal (mutex);
consume item;
until forever
process producer;
repeat
produce item;
wait (mutex);
while count = n do nothing;
buffer[in] := item;
in := (in+1) mod n;
count := count + 1;
signal (mutex);
until forever
• Can semaphore help?
Bounded Buffer Problem
• Use semaphore count to do counting
process producer; loop
produce item; wait (full); wait (mutex); access
shared_buffer; signal (mutex); signal (empty);
end
end;
process consumer; loop
wait (empty); wait (mutex); access
shared_buffer; signal (full); signal (mutex); consume item;
end end;
full = N -- distance to full
empty = 0 -- distance to empty
mutex = 1
Bounded Buffer Problem
• Analysis —full: indicates how far from full
• full.count = 0 n items in buffer producer wait • producer decreases full.count
consumer increases full.count
—empty: indicates how far from empty • empty.count = 0 0 item in buffer consumer wait • producer increases empty.count
consumer decreases full.count
—Both have to wait on mutex before accessing buffer —If only one producer and one consumer, do we still
have to use mutex? • No, each uses a different buffer slot
• But we still need to use full and empty semaphores
End of Chapter 6
