Transcript os-3c

Operating Systems
Part III: Process
Management
(Process
Synchronization)
The Problem of Synchronization


Cooperating processes have to be synchronized to
avoid chaos
Example: Bounded capacity (Producer-Consumer)
–
–
–

Producer: puts new item, increment counter
Consumer: gets new item, decrement counter
Problem occurs when both execute concurrently
Race condition – several processes access and
manipulate shared data concurrently; outcome of
execution depends on order in which the access takes
place
The Critical Section Problem


Each process has a critical section (i.e.
updating a table, writing a file, etc.)
Basic implementation
repeat
ENTRY section
CRITICAL SECTION
EXIT section
REMAINDER section
until false
The Critical Section Problem

Three requirements:
–
–
Mutual exclusivity - if a process is in its critical
section, no other process is allowed
Progress - if no process is in its critical section, and
some processes want to enter their critical sections,
only those not in their remainders will participate in
decision of which will enter next and this selection
cannot be postponed indefinitely
The Critical Section Problem

Three requirements (continued)
–
Bounded waiting - there must be a limit on the
number of times that other processes are allowed to
enter their critical sections after a process has made
a request and before that request is granted
Solutions to the Critical Section
Problem

Two-process solution
–
applicable only to two processes at the most
shared variables: boolean flag[2]; int turn;
do { flag[i] = true; turn = j;
while( flag[j] && turn == j); // do nothing
do_critical_section();
flag[i] = false;
do_remainder_section();
} while(1);
Solutions to the Critical Section
Problem

Multiple-process solutions
–
–
–
Solution is called the bakery algorithm -> based on
scheduling commonly used in bakeries, banks, etc.
Developed for a distributed environment
Algorithm on page 197
Synchronization Hardware

As with other aspects of software, additional hardware
features
–
–

make programming task easier and,
improve system efficiency
If no special hardware, Critical Section can be
implemented by disabling interrupts -> may not always
be possible
–
–
disabling interrupts is time-consuming (message passed to all
processors) -> decreased efficiency
example: system clock (updated by interrupts)
Synchronization Hardware

Many machines provide special hardware to do
the following:
–
–
test and modify content of a word:
TestAndSet(boolean &x): atomically
{ boolean oldx = x;
x = true;
return oldx;
}
swap contents of two words, also atomically
Use of TestAndSet to provide
mutual exclusion


Variable lock = false, initially
do {
while (TestAndSet(lock) ); // do nothing
do_critical_section();
lock = false;
do_remainder_section():
} while (1);
Bounded-waiting not fulfilled.
Mutual exclusion & bounded-waiting
with TestAndSet


More complicated, requires the ff common data
structures:
boolean waiting [n];
boolean lock;
Algorithm is given in Figure 7.10, on page 200
Semaphores



Two- and multiple-process solution not easy to
generalize to more complex problems
To overcome, use a synchronization tool called
semaphore
A variable accessed only through two atomic
operations: wait and signal
wait(S)
while (S<=0); // do nothing
S:=S-1;
signal(S)
S:=S+1;
Mutual-exclusion using semaphores

Variable mutex = 1, initially
do {
wait(mutex);
do_critical_section();
signal(mutex);
do_remainder_section():
} while (1);
Semaphores

Example: We want S2 to execute only after S1
has completed.
Var mutex = 0, initially.
Process P1:
S1;
signal(mutex);
...
Process P2:
wait(mutex);
S2;
Busy waiting (spinlock)


While a process is in its critical section, any
other process that tries to enter its critical
section must loop continuously, while waiting for
the mutex variable to become positive – this
waiting is called spinlock, the process “spins”
while waiting for the lock.
When locks are held for short time periods –
spinlocks are okay. Can be a problem when
locks are held for long in a realtime OS
Solution to busy-waiting


Instead of busy waiting, a process can block itself,
placing itself into a waiting queue associated with the
semaphore S. A context switch can then take place.
When another process executes a signal(S), the waiting
process is restarted by a wakeup operation, which
changes the state of the process from waiting to ready.
typedef struct {
int value;
struct process *wlist;
} semaphore;
Code for blocking semaphore

wait (semaphore S) {
S.value-- ;
if (S.value < 0) {
add_process_to(S.wlist);
block():
}
}
Code for blocking semaphore

signal (semaphore S) {
S.value++ ;
if (S.value <= 0) {
P = remove_process_from(S.wlist);
wake_up(P);
}
}
Semaphores

Might result in a deadlock
P0
wait(S)
wait(Q)
…
signal(S)
signal(Q)
P1
wait(Q)
wait(S)
…
signal(Q)
signal(S)
Classical Problems of
Synchronization



Represent large class of concurrency control problems
Used for testing nearly every newly-proposed
synchronization scheme
Bounded-Buffer
–
–
–
Buffer size n; producer puts in buffer; consumer gets from the
buffer
commonly used to illustrate power of synchronization
primitives
Sample code on Figure 7.12, page 207
Classical Problems of
Synchronization

Readers and Writers
–
–
–
–
–
A data object is shared by several concurrent
processes
No problem if two readers access concurrently
Problem arises with writers and readers
To prevent chaos, writers must be allowed exclusive
access to the data
Code for writer: wait(wrt); do_write(); signal(wrt);
Classical Problems of
Synchronization

Dining-Philosophers
–
–
–
–
Simple representation of the need to allocate
resources properly (deadlock- and starvation-free)
Five philosophers in dining table; each has rice bowl
Five chopsticks laid, each put between philosopher
and his right and left neighbor
When thinking: does not interact with others
Classical Problems of
Synchronization

Dining-Philosopher (continued)
–
–
–
–
–
When eating: needs to use both chopsticks
Can pick up one chopstick at a time; cannot pick up
a chopstick being used
Does not release both chopsticks until finished
eating
After eating, philosopher starts thinking again
Deadlock-free solution does not eliminate starvation