Transcript wait() - Universidade de Coimbra

Synchronization!
Welcome to the most
important part of this course!
1
Operating
Systems
4. Synchronization
2006/2007
4.1 A Systems Programmer’s View
Paulo Marques
Departamento de Eng. Informática
Universidade de Coimbra
[email protected]
Disclaimer

This slides and notes are heavily based on the companion material of
[Silberschatz05].The original material can be found at:


In some cases, material from [Stallings04] may also be used. The
original material can be found at:


http://codex.cs.yale.edu/avi/os-book/os7/slide-dir/index.html
http://williamstallings.com/OS/OS5e.html
The respective copyrights belong to their owners.
3
Consider the following library call
Process A
send_to_printer(59, “What a beautiful day!”);
Process B
send_to_printer(12, “I hate going to school!”);
4
Resulting in…
Job from user --- 59 --What a beautiful day!
------------------------------Job from user --- 12 --I hate going to school!
------------------------------What I expected!

Job from user --- 59 --Job from user --- 12 --What I hate a beautiful day!
------------------------------going to school!
------------------------------Or not so!!!!
Race condition: The situation where several processes
access – and manipulate shared data concurrently. The
result critically depends on timing of these processes,
which are “racing”.
5
Mutual Exclusion!
This piece of code has to be executed Atomically,
in Mutual Exclusion! These three lines
constitute a Critical Section.

This routine is neither Thread-Safe nor Reentrant!
6
Mutexes
Only one thread/process can be in here!

A mutex is a synchronization primitive available for
processes and threads. It has two primitives:


lock(): allows a thread to acquire the mutex, ensuring that only
one flow of execution exists inside the critical section. If a second
thread calls lock(), it becomes blocked.
unlock(): signals that a thread is leaving the critical section. If
there are other threads waiting for the critical section, one of
them is allowed to run: it becomes ready.
7
A mutex is also called a
BINARY SEMAPHORE!
8
Semaphores – Powerful Friends

A semaphore is a synchronization object



wait()



Controlled access to a counter (a value)
Two operations are supported: wait() and post()
If the semaphore is positive, decrement it and continue
If not, block the calling thread (process)
post()


Increment the semaphore value
If there was any (process) thread blocked due to the semaphore,
unblock one of them.


Semaphores are used to count things!
Blocked Processes in a semaphore do not
consume resources (CPU)!
9
The anatomy of a Semaphore
value
5
blocked
process list
P1
P6
P3
NULL
“A semaphore”
10
“Real Semaphores”

System V Semaphores




POSIX Semaphores





Quite easy to use
sem_init(), sem_close(), sem_post(), sem_wait()
Also work with threads!
But... in Linux, they only work with threads (kernel 2.4)
Java  Typically uses “monitors”, now it has:


Works with semaphore arrays
semget(), semctl(), semop()
A little bit hard to use by themselves
 Use a library to encapsulate them!
java.util.concurrent.Semaphore
.NET  Typically uses “monitors”, but it has:

System.Threading.Semaphore
11
My Semaphore Library
12
Classical – Producer/Consumer Problem


A producer puts elements on a finite buffer. If the buffer is
full, it blocks until there’s space.
The consumer retrieves elements. If the buffer is empty, it
blocks until something comes along.
Producer

Consumer
We will need three semaphores



One to count the empty slots
One to count the full slots
One to provide for mutual exclusion to the shared buffer
13
Producer/Consumer – Basic Implementation
mutex
read_pos
write_pos
Producer
Consumer
empty
put_element(e) {
sem_wait(empty);
sem_wait(mutex);
buf[write_pos] = e;
write_pos = (write_pos+1) % N;
sem_post(mutex);
sem_post(full);
}
full
get_element() {
sem_wait(full);
sem_wait(mutex);
e = buf[read_pos];
read_pos = (read_pos+1) % N;
sem_post(mutex);
sem_post(empty);
return e;
}
14
The result of executing it!
15
Remember

Always cleanup...
16
Main loop
void producer() {
for (int i=TOTAL_VALUES; i>0; i--) {
printf("[PRODUCER] Writing %d\n", i);
put_element(i);
}
}
void consumer() {
for (int i=0; i<TOTAL_VALUES; i++) {
int e = get_element();
printf("[CONSUMER] Retrieved %d\n", e);
sleep(1);
}
terminate();
}
void main(int argc, char* argv[]) {
init();
if (fork() == 0) {
producer();
exit(0);
}
else {
consumer();
exit(0);
}
17
put_element() and get_element()
void put_element(int e) {
sem_wait(sem, EMPTY);
sem_wait(sem, MUTEX);
buf[write_pos] = e;
write_pos = (write_pos+1) % N;
sem_post(sem, MUTEX);
sem_post(sem, FULL);
}
int get_element() {
sem_wait(sem, FULL);
sem_wait(sem, MUTEX);
int e = buf[read_pos];
read_pos = (read_pos+1) % N;
sem_post(sem, MUTEX);
sem_post(sem, EMPTY);
return e;
}
18
init() and terminate()
int sem, shmid;
int write_pos, read_pos;
int* buf;
void init() {
sem = sem_get(3, 0);
sem_setvalue(sem, EMPTY, N);
sem_setvalue(sem, FULL, 0);
sem_setvalue(sem, MUTEX, 1);
// N is the number of slots
write_pos = read_pos = 0;
shmid = shmget(IPC_PRIVATE, N*sizeof(int), IPC_CREAT|0700);
buf = (int*) shmat(shmid, NULL, 0);
}
void terminate() {
sem_close(sem);
shmctl(shmid, IPC_RMID, NULL);
}
19
What should I care?






When you read some data from a
pipe…
When you write some data to the
network…
When your windows application is
processing all those “Open Window”,
“Close Window” messages…
When your bank is processing the
money you are depositing…
When the a space probe sends
images and telemetry from space…
… When you are playing Unreal and
all those guys simply “must die”!
20
Classical – Readers/Writers Problem


Writer processes have to update shared data.
Reader processes have to check the values of the data.
The should all be able to read at the same time.
Reader
Writer
Shared Data
Reader
Writer
Reader


Why is this different from the Producer/Consumer problem?
Why not use a simple mutex?
21
Readers/Writers Problem

We will need two semaphores:


One to stop the writers and guarantying mutual exclusion when a
writer is updating the data
One to protect mutual exclusion of a shared variable that counts
readers
n_readers
Writer
Reader
mutex
Reader
Writer
stop_writers
Reader
22
Readers/Writers Algorithm (Priority to Readers)
n_readers
Writer
Reader
Reader
mutex
Writer
stop_writers
read() {
sem_wait(mutex);
++n_readers;
if (n_readers == 1)
sem_wait(stop_writers);
sem_post(mutex);
e = buffer;
sem_wait(mutex);
--n_readers;
if (n_readers == 0)
sem_post(stop_writers);
sem_post(mutex);
return e;
write(e) {
sem_wait(stop_writers);
buffer = e;
sem_post(stop_writers);
}
}
23
Some Considerations

The previous algorithm gives priority to readers

Not always what you want to do

There’s a different version that gives priority to writers

Why should I care?

This algorithm is the fundament of all database systems!
Concurrent reads of data; single update.

… One bank agency deposits some money in an account; at the
same time, all over the country, many agencies can be reading it
… You are booking a flight. Although someone in England in also
booking a flight, you and thousands of people can still see what
are the available places in the place.

24
Classical – Buffer Cleaner Problem

A buffer can hold a maximum of N elements. When it is
full, it should be immediately emptied. While the buffer is
being emptied, no thread can put things into it.
Producer
Producer
Producer
Cleaner
25
Bounded Buffer Problem
Can you solve it??
26
Classical – Sleeping Barber



A barbershop has N
waiting chairs and a
barber chair
If there are no customers,
the barber goes to sleep
When a customer enters:



If all chairs are occupied, he
leaves
If the barber is busy but
there are chairs, then the
customer sits and waits
If the barber is sleeping,
the customer wakes him up
Can you solve it??
27
Synchronization – Some basic rules...

Never Interlock waits!


Locks should always be taken in the same order in all
processes
Locks should be released in the reverse order they have
been taken
sem_wait(A)
sem_wait(B)
// Critical Section
sem_post(B)
sem_post(A)

Deadlock!
sem_wait(B)
sem_wait(A)
// Critical Section
sem_post(A)
sem_post(B)
One way to assure that you always take locks in the same
order is to create a lock hierarchy. I.e. associate a
number to each lock using a table and always lock in
increasing order using that table as reference (index).
28
Synchronization – Some basic rules... (2)

Sometimes it is not possible
to know what order to take
when locking (or using
semaphores)


Example: you are using two
resources owned by the
operating system. They are
controlled by locks. You
cannot be sure if another
application is not using
exactly the same resources
and locking in reverse
order.
In that case, use
pthread_mutex_trylock() or
sem_trywait() and back off
if you are unsuccessful.

Allow the system to make
progress and not deadlock!
29
Synchronization – Some basic rules... (3)

Mutexes are used for implementing mutual exclusion, not for signaling
across threads!!!


Only the thread that has locked a mutex can unlock it. Not doing so will
probably result in a core dump!
To signal across threads use semaphores!
A
B
A
lock(&m)
B
lock(&m)
(in mutual
exclusion)
unlock(&m)
lock(&m)
(blocked)
unlock(&m)
(in mutual exclusion)
unlock(&m)
CORRECT!
INCORRECT!
30
Synchronization – Some basic rules... (4)

Don’t mess with thread priorities unless you really need to.

Although apparently “correct” and “logical” in design, it’s quite easy to
make a system deadlock, live-lock or some threads to starve.
The Mars PathFinder
would run ok for a while and,
after some time, it would stop
and reset.
The watch-dog timer was
resetting the system because of
some unknown reason…
31
The Mars PathFinder Problem

Priority Inversion Problem
(in Mars Path Finder):




Low priority thread locks a
semaphore.
High priority thread starts to
execute and tries to lock the
same semaphore. It’s
suspended since it cannot
violate the other thread’s lock.
Medium priority threads comes
to execute and preempts the
low priority thread. Since it
doesn’t need the semaphore, it
continues to execute.
Meanwhile the high priority
thread is starving. After a
while, the watchdog timer
detects that the high priority
thread is not executing and
resets the machine.
(Solution: Thread Locking Priority Inheritance.)
starts to
execute
tries to get
the lock and watchdog timer
is suspended resets the machine
as the high priority
one doesn’t get to
execute
A
B
C
starts to
execute
and gets
the lock
continues
to execute
is preempted as
medium priority
gets to execute
32
Some important concepts to always remember!

Deadlock
When two or more processes are unable to make progress
being blocked waiting for each other

Livelock
When two or more processes are alive and working but
are unable to make progress

Starvation
When a process is not being able to access resources that
its needs to make progress
33
The inventor of the “Semaphore”

Edsger Dijkstra was one of the most
brilliant computer scientists ever!

Inventor of the semaphore, one of
the key contributions for modern
operating systems; developed the
THE operating system


Created the Dijkstra algorithm for
finding the shortest path in a graph


Used in all operating systems today!
Used in all computer networks today
(e.g. in OSPF routing)!
Wrote “A Case against the GO TO
Statement”, and was one of the
fathers of Algol-60

Which introduced the revolution of
structured programming!
Edsger Dijkstra
34
Writings by E.W. Dijkstra (EWD)
…
35
Reference

Chapter 6: Process Synchronization

Read Section 3.4.1 first

6.1, 6.2, 6.5, 6.6
36
Operating
Systems
4. Synchronization
2006/2007
4.2. Other Synchronization Primitives
Paulo Marques
Departamento de Eng. Informática
Universidade de Coimbra
[email protected]
Semaphores are correct and
very convenient but…
EASY TO GET WRONG!



It’s easy to forget a wait() or post()…
It’s easy to do wait() and post() in different semaphores on
opposite order
It’s difficult to ensure correctness when several semaphores are
involved
38
Monitors

A monitor is an abstraction where only one thread or
process can be executing at a time.


Normally, it has associated data
When inside a monitor, a thread executes in mutual exclusion
Thread D
Thread C
Want to enter
the monitor…
Thread B
Monitor
In mutual exclusion
Protected Data
Thread A
39
A Monitor in Java
Protected
Data
Only one thread
can be inside these
methods at a time;
the others wait
outside
40
Monitors (2)


Until now monitors look a lot like a simple MUTEX…
Two more primitives are provided:



wait()  Suspends the execution of the current thread,
immediately relinquishing the monitor. The thread is put on a
blocked threads list, waiting to be notified that “something” has
changed.
notify()  Informs one of the threads that is waiting for something
to change that “something” has changed. Thus, one of the awaiting
threads is put on the “ready to execute” list. Note that only after the
thread that has called notify exits the monitor will the thread that
was awaken be allowed to check was has changed and enter the
monitor!
[notifyAll()  Notifies all waiting threads to check the condition]
Important!

wait() and notify() are not like wait() and post() in semaphores. If
notify is called when there is no awaiting thread, it is lost. There is
no associated counter, only the means to notify threads that things
changed.
41
putValue() and getValue()
42
Main Program
43
Producer
44
Consumer
45
Running…
46
(A possible) Structure of a monitor
Blocked threads waiting (ready)
to enter the monitor
MONITOR
Only one thread can
be inside
Blocked threads due to a wait()
Whenever a thread calls wait(),
the monitor is released and the
thread is put on the “wait() queue”
Whenever a thread calls notify(),
one of the threads in the “wait()
queue” is transferred to the “ready to
enter the monitor” queue
47
Important
Why notifyAll() and not notify()?
Why ‘while’ and not ‘if’?
48
Monitors in Unix?

In “C” you don’t have monitors but you have
CONDITION VARIABLES

Condition variables are somewhat similar to monitors.
They allow the programmer to suspend a thread until a
certain condition is satisfied or notify a thread that a
certain condition has changed.


The condition can be anything you like!
Counting semaphores are a special type of condition
variables  The condition is “counter==0”
49
Primitives
50
Synchronization – Condition Variables (2)

Important rule:



A condition variable always has an associated mutex.
Always check the condition variable in mutual exclusion. The mutex must
be locked.
How does it work?
Makes thread A
check its condition
again
51
Synchronization – Condition Variables (3)




The thread tests a condition in
mutual exclusion. If the condition
is false, pthread_cond_wait()
atomically releases de mutex
AND waits until someone
signals that the condition
should be tested again.
When the condition is
signaled AND the mutex is
available, pthread_cond_wait()
atomically reacquires the
mutex AND releases the
thread.
pthread_cond_signal() indicates
that exactly one blocked
thread should test the
condition again. Note that this
is note a semaphore. If there is
no thread blocked, the “signal” is
lost.
If all threads should re-check the
condition, use
pthread_cond_broadcast(). Since
a mutex is involved, each one
will test it one at a time, in
mutual exclusion.
52
Buffer Cleaner Revised

Suppose a buffer that can hold a maximum of N elements.
When it is full, it should immediately be emptied. While
the buffer is being emptied, no thread can put things into
it.
Producer
Producer
Producer
Cleaner
53
bounded_buffer.c
54
bounded_buffer.c (2)
55
With 3 producers and one cleaner...
56
Condition Variables – Rules (!)


The condition must always be tested with a while loop, never an if!
Being unlocked out of a condition variable only means that the
condition must be re-checked, not that it has become true
The condition must always be checked and signaled inside a locked
mutex.
While condition() may be
true while Thread B is executing,
something may happen between
the time that the condition is signaled
and Thread A is unblock (e.g. another
thread may change the condition)
57
Classical Problem – Dinning Philosophers

Five philosophers are sitting at a table eating rice from a
bowl. For eating rice two chopsticks are needed. There’s
only one chopstick on each side of a philosopher.

How to design an algorithm that allows the philosophers
to eat without deadlocks, starvation, or live-locking?
58
Dinning Philosophers – Some notes

The following algorithm is bound to deadlock. Why?
philosopher(i)
{
wait(chopstick[i]);
wait(chopstick[(i+1)%N]);
eat();
post(chopstick[(i+1)%N]);
post(chopstick[i]);
}

The following algorithm may live-lock. Why? (Tip: what
happens if all philosophers start to eat at exactly the same
time?)
 Try to obtain left chopstick.
 If successful, obtain right chopstick and eat.
 If unsuccessful, put down the left chopstick and wait for a while
59
Reference

[Silberschatz05]
Chapter 6: Process Synchronization


6.6, 6.7
[Robbins03]



Chapter 12: POSIX Threads
Chapter 13: Thread Synchronization
Chapter 14: Critical Sections and Semaphores
60
Operating
Systems
4. Synchronization
2006/2007
4.3. Hardware Issues
Paulo Marques
Departamento de Eng. Informática
Universidade de Coimbra
[email protected]
Bounded-Buffer, from the beginning…
62
Besides
puttingfrom
the CPU
to 100% without
Bounded-Buffer,
the beginning…
doing anything useful, why is it wrong???
63
Some possible problems with ++nElements;

The compiler may generate the following code:
LD
R1, @nElements
ADD R1, R1, 1
SW @nElements, R1
Depending on the interleaving of putItem() and
getItem() the final value can be -1, correct, or +1!!!
64
Some possible problems with ++nElements;

Possible solution… Disable the interrupts!
CLI
LD
R1, @nElements
ADD R1, R1, #1
SW @nElements, R1
STI


Works on simple processors with non-preemptive
kernels.
But, in a (e.g.) dual-core machine, disabling interrupts in
one processor does not prevent the other processor from
modifying the variable!


Non-preemptive kernels: A process executing in kernel mode
cannot be suspended. E.g. Windows XP, Traditional UNIX
Preemptive Kernels: While executing in kernel mode a process
can be suspended. E.g. Linux 2.6.XX series and Solaris 10.
65
Some possible problems with ++nElements;

Even in architectures providing an atomic INC variable:
INC
@nElements
it may not work!

The compiler may optimize a tight loop putting the
variable in a register. In another process, the variable may
be being written to memory, but it’s not visible from the
first process. This is especially relevant in multiprocessor
Process B
Process A
machines.
…
while (nElements == 0)
;
…
a “smart compiler” has put
nElements in a register
…
++nElements;
…
nElements is being updated
in memory (or a different
register)
66
All leading to…
The need for having atomic locks!
67
Conditions for solving the critical section problem

Mutual Exclusion


Progress


Only one process can be
executing in the critical section
at a time
If on process is in the critical
section only the processes that
are either at the entry or exit
sections can be involved in
choosing the next process to
enter. The decision must be
reached in bounded time.
Bounded Waiting

No process will starve
indefinitely while trying to
enter a critical section in
detriment of other processes
which repeatedly enter it.
68
Solutions for the Critical Section Problem

Software Algorithms: E.g. Peterson’s Algorithm





In reality, software algorithms implement locks!



See Section 6.3 of the book (important!)
Complicated to implement and prove correct
Very difficult to generalize for several concurrent processes
May not work with current hardware
(multi-processor environments with deep speculative out-of-order
execution pipelines, having several levels of caches)
enter section  lock()
exit section  unlock()
Solutions in hardware

Simple “old” single processor machines  Disable Interrupts


Even in modern single processor machines may not work
TestAndSet and Swap instructions
69
TestAndSet

Instruction that atomically, implemented in hardware,
returns the value of a target variable, setting it to TRUE.

Solution for mutual exclusion:
70
Swap

Instruction that atomically swaps the contents of two
variables.

Solution for mutual exclusion:
71
Notes on Hardware-Based Support

The two previous algorithms:




Solve the mutual exclusion problem and the progress condition
Do not satisfy the bounded waiting condition (why??)
Slightly more sophisticated algorithms exist that do so
The implementations shown before are called spin-locks




In general they should be avoided
Nevertheless, in controlled ways, they are the basis for
implementing true mutexes and semaphores at the operating
system level
This is especially relevant on preemptive kernels running on
multiprocessors. (Somehow, the kernel must, in a controlled way,
allow to signal across processors in mutual exclusion!)
In some high performance applications, sometimes programmers
spin-lock for a few moments before blocking on a true
lock/semaphore. In this way they are able to prevent a heavy
process switch if the resource becomes available in a very short
time.
72
Linux 2.6.XX



Linux 2.6 is a fully preemptive kernel. I.e. processes can
be suspended while executing in kernel mode.
Basic underlying locking mechanism depends on whether
an SMP or non-SMP kernel is being used.
Spin-locks are only used for very short durations.

Longer durations imply passing control to a true lock/semaphore,
releasing the processor(s) involved.
single processor
multi-processor
Disable kernel preemption
Acquire spin-lock
Enable kernel preemption
Release spin-lock
73
Reference

Chapter 6: Process Synchronization

Read Section 3.4.1 first

6.1, 6.2, 6.3, 6.4, 6.8
74