Transcript Synchronisation

Synchronisation
Sorin Manolache
[email protected]
Last on TTIT61
 Processes are executing programs
 Kernel manages them, their state, associated data (open
files, address translation tables, register values, etc.)
 Threads are lightweight processes, i.e. they share data
segments, are cheaper to spawn and terminate
 Scheduler selects next process to run among the ready
ones
 Various scheduling algorithms and criteria to evaluate them
S. Manolache, Process programming and operating systems, Synchronisation
2
Lecture Plan
1. What is an operating system? What are its functions?
Basics of computer architectures. (Part I of the textbook)
2. Processes, threads, schedulers (Part II , chap. IV-VI)
3. Synchronisation (Part II, chap. VII)
4. Primary memory management. (Part III, chap. IX, X)
5. File systems and secondary memory management (Part
III, chap. XI, XII, Part IV)
6. Security (Part VI)
S. Manolache, Process programming and operating systems, Synchronisation
3
Outline
 Need for synchronisation
 Synchronisation mechanisms
 System calls: pause, select, waitpid
 Message passing: blocking read/writes
 Race conditions, critical regions, atomic operations, busywaiting, hardware support for their implementation
 Synchronisation mechanisms
 Semaphores
 Monitors
 Re-entrant code
 Deadlock
 Classical problems of synchronisation
 Readers/writers, bounded buffer, dining philosophers
S. Manolache, Process programming and operating systems, Synchronisation
4
Need for Synchronisation
 Processes that do not interact with other processes (from
their functionality point of view) are independent
 Processes that do interact are co-operating
 E.g.:
 Web server and browser (client) (and all applications in
the client-server paradigm)
 Mail composer and spell checker
 sort –nr +1 -2 < grades.txt | cut –f2 | uniq | head -10
 Takes a files where the grades are on the second
column, sorts it in descending order of the grades,
takes the second column, eliminates duplicates, and
prints the highest ten grades
S. Manolache, Process programming and operating systems, Synchronisation
5
Need for Synchronisation
 The co-operating processes synchronise in some way
 Synchronous: happening at the same time (Chronos:
Greek god of time)
 E.g.:
 Web server pumps bytes down the connection after
getting a request. Browser reads served document after
the client starts sending it.
 The spell checking is triggered by the appearance of
new text in the composer.
S. Manolache, Process programming and operating systems, Synchronisation
6
Simple Solutions: Pause
 The pause system call
 The processes that invokes pause blocks until it gets a
signal. The spell checker could call pause, and the mail
composer could call kill –USR1 pid_of_spell_checker.
 Disadvantage: The composer must know to whom it
sends the signal (its pid). Also, it must have the right to
signal the spell checker.
S. Manolache, Process programming and operating systems, Synchronisation
7
Simple Solutions: Select
 The select system call
 The caller of select(fd, …) blocks until a specified
operation (read or write) is possible on the file descriptor
fd without blocking.
 The mail composer could write everything the user
types to a pipe descriptor and the spell checker could
call select on the pipe descriptor.
 Disadvantage: There must be a pipe, or socket, or file
shared between the caller of select and the processes
that makes the unblocking read or write possible.
S. Manolache, Process programming and operating systems, Synchronisation
8
Blocking Reads/Writes
 The previous problems could be solved with the
synchronisation mechanism of blocking reads or writes
 Blocking read:
 The invoking process attempts to read something from
a descriptor (socket, pipe, file, message queue). If no
data is available for reading, the invoking process
blocks until data is available.
 Blocking write:
 The invoking process attempts to write a data item to a
descriptor. It blocks until a process consumes the data
item.
S. Manolache, Process programming and operating systems, Synchronisation
9
Nachos, Lab 1, Bounded Buffer
Blocking
Not blocking
Read
X
Write
X
How many elements would the buffer contain
if the writing was blocking?
S. Manolache, Process programming and operating systems, Synchronisation
10
Outline
 Need for synchronisation
 Synchronisation mechanisms
 System calls: pause, select, waitpid
 Message passing: blocking read/writes
 Race conditions, critical regions, atomic operations, busywaiting, hardware support for their implementation
 Synchronisation mechanisms
 Semaphores
 Monitors
 Re-entrant code
 Deadlock
 Classical problems of synchronisation
 Readers/writers, bounded buffer, dining philosophers
S. Manolache, Process programming and operating systems, Synchronisation
11
Race Condition
 We say that we have a race condition when, given that
several processes access the same data, the execution
outcome depends on the order in which the concurrent
processes accessed the data.
 E.g.:
buffer[index] = processID;
++index;
S. Manolache, Process programming and operating systems, Synchronisation
12
Critical Sections
 A critical section is a section of code that no process may
execute it while another process executes it.
 The execution of critical sections by processes if mutually
exclusive in time
 The critical section problem is to design a protocol to
ensure the mutual exclusive execution
 Requirements for the solution of the critical section
problem:
 Mutual exclusion
 Progress
 Bounded waiting
S. Manolache, Process programming and operating systems, Synchronisation
13
Two-Process Solution (1)
do {
while (turn != 0) no-op;
critical section
turn = 1
remainder
} while (true);
 Progress?
S. Manolache, Process programming and operating systems, Synchronisation
14
Two-Process Solution (2)
do {
flag[0] = true;
while (flag[1]) no-op;
critical section
flag[0] = false;
remainder
} while (true);
 Progress? Deadlock!
S. Manolache, Process programming and operating systems, Synchronisation
15
Two-Process Solution (2’)
do {
while (flag[1]) no-op;
flag[0] = true;
critical section
flag[0] = false;
remainder
} while (true);
 Mutual exclusion?
S. Manolache, Process programming and operating systems, Synchronisation
16
Two-Process Solution (3)
do {
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1) no-op;
critical section
flag[0] = false;
remainder
} while (true);
 Works?
S. Manolache, Process programming and operating systems, Synchronisation
17
Multiple-Process Solution
do {
choosing[i] = true;
number[i] = max(number[0], …, number[n – 1]) + 1;
choosing[i] = false;
for (j = 0; j < n; j++) {
while (choosing[j]) no-op;
while (number[j] != 0 && (number[j], j) < (number[i], i))
no-op;
}
critical section
number[i] = 0;
remainder
} while (true);
S. Manolache, Process programming and operating systems, Synchronisation
18
Busy Waiting
 All algorithms on previous slides contained
while (condition) do nothing;
 The process is marked as ready, and whenever running, it
just wastes CPU time (and money, where one buys CPU
time)
 The process is said to be busy waiting
S. Manolache, Process programming and operating systems, Synchronisation
19
Busy Waiting
 It would be better if the waiting is supported by the OS. The
process marks itself as waiting, is not anymore ready, and
waits for the OS to notify it when it may wake up and
become ready again.
 No CPU cycles wasted, additional complexity in the OS,
additional context switches
 If we know that a process would wait for a very short time,
busy waiting loops could be preferred to OS support.
S. Manolache, Process programming and operating systems, Synchronisation
20
Hardware Support: Interrupts
 Disabling interrupts when entering the critical section.
 Not efficient for multi-processor systems
 If the critical section is long, the system is not
responsive and/or it may lose events
S. Manolache, Process programming and operating systems, Synchronisation
21
Hardware Support: Test and Set
boolean TestAndSet(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
 It runs atomically, i.e. as an uninterruptible unit.
do {
while (TestAndSet(lock)) no-op;
critical section
lock = false;
remainder
} while (true);
S. Manolache, Process programming and operating systems, Synchronisation
22
Hardware Support: Swap
do {
key[i] = true;
while (key[i] == true)
swap(lock, key[i]);
critical section
lock = false
remainder
} while (true);
 Are these two solutions, TestAndSet-based and Swapbased, two-process solutions or multiple-process
solutions?
S. Manolache, Process programming and operating systems, Synchronisation
23
Outline
 Need for synchronisation
 Synchronisation mechanisms
 System calls: pause, select, waitpid
 Message passing: blocking read/writes
 Race conditions, critical regions, atomic operations, busywaiting, hardware support for their implementation
 Synchronisation mechanisms
 Semaphores
 Monitors
 Re-entrant code
 Deadlock
 Classical problems of synchronisation
 Readers/writers, bounded buffer, dining philosophers
S. Manolache, Process programming and operating systems, Synchronisation
24
Message Passing
 Synchronisation by message passing is a rather high-level
mechanism
 We would need something at a lower level, more general,
that can be used to implement several higher-level
synchronisation mechanisms
S. Manolache, Process programming and operating systems, Synchronisation
25
Semaphores
 Semaphores:
 Synchronisation tool introduced by Dijkstra with the
following two operations:
 P (Dutch: probeeren = to test)
– while (S0) no-op; --S;
 V (Dutch: verhogen = to increment)
– ++S;
 No modification of S is allowed to be performed by a
process while another process operates on S.
 Testing and decrementing of S in P has to be done
without interruption by another process.
S. Manolache, Process programming and operating systems, Synchronisation
26
Non-Blocking Write, Blocking Read with Sem.
 Writer:
write(fd, data item);
sem.V();
 Reader:
sem.P();
data item = read(fd);
We assume an unbounded buffer associated to the descriptor fd
S. Manolache, Process programming and operating systems, Synchronisation
27
Critical Sections with Semaphores
do {
sem.P();
critical section
sem.V();
remainder
} while (true)
 Multi-process or two-process solution?
 What is the initial value of the semaphore in an n-process
solution?
S. Manolache, Process programming and operating systems, Synchronisation
28
Monitors
 Is a high-level synchronisation construct
 Contains a set of programmer-defined operators
 Represented by a set of variables (defining the state) and a
set of procedures
monitor name {
shared variables declaration
procedure P1(…) {
}
procedure Pn(…) {
}
{ initialisation code}
}
// the array of the BB
// put
// get
// array construction
S. Manolache, Process programming and operating systems, Synchronisation
29
Monitors
 Access on the shared data must be exclusive
Conditions
Entry queue
Shared data
operations
Initialisation code
S. Manolache, Process programming and operating systems, Synchronisation
30
Conditions
 Conditions:
 Wait:
 Invoking process appends itself to the queue
corresponding to the condition
 It releases the monitor
 It blocks
 After it is woken up, it re-acquires the monitor
 Signal
 A blocked process from the queue of processes that
wait on the condition is woken up
 Order?
S. Manolache, Process programming and operating systems, Synchronisation
31
Outline
 Need for synchronisation
 Synchronisation mechanisms
 System calls: pause, select, waitpid
 Message passing: blocking read/writes
 Race conditions, critical regions, atomic operations, busywaiting, hardware support for their implementation
 Synchronisation mechanisms
 Semaphores
 Monitors
 Re-entrant code
 Deadlock
 Classical problems of synchronisation
 Readers/writers, bounded buffer, dining philosophers
S. Manolache, Process programming and operating systems, Synchronisation
32
Re-Entrant Code
 A section of code that may be executed by a process before
another process leaves it
 E.g.:
char kernel_buffer[BUF_MAX];
void user_to_kernel(int virtualAddr, char kernel_buf[]) {
int physicalAddr, i = 0;
do {
physicalAddr = translate(virtualAddr);
kernel_buf [i++] = c = memory[physicalAddr];
} while (c != ‘\0’);
}
user_to_kernel(1000, kernel_buffer) || user_to_kernel(2000, kernel_buffer)
S. Manolache, Process programming and operating systems, Synchronisation
33
Re-Entrant Code
 The problem with the previous code is that both processes
share the kernel_buffer array.
 Do not use global variables when writing re-entrant code
 If you have to use them, then protect them with locks. The
protected accesses will not be re-entrant any more.
S. Manolache, Process programming and operating systems, Synchronisation
34
Outline
 Need for synchronisation
 Synchronisation mechanisms
 System calls: pause, select, waitpid
 Message passing: blocking read/writes
 Race conditions, critical regions, atomic operations, busywaiting, hardware support for their implementation
 Synchronisation mechanisms
 Semaphores
 Monitors
 Re-entrant code
 Deadlock
 Classical problems of synchronisation
 Readers/writers, bounded buffer, dining philosophers
S. Manolache, Process programming and operating systems, Synchronisation
35
Deadlock
 Process A blocks if resource R is unavailable
 Resource R may never become available again because
process B holds it and never releases it
 Process B may never release it because in its turn, it waits
for a different resource, R’, that could be held by process A
 Processes A and B deadlock
S. Manolache, Process programming and operating systems, Synchronisation
36
Conditions for Deadlock
 Mutual exclusion: At least one resource cannot be shared
 Hold and wait: A process must be holding at least one
resource and waiting to acquire additional resources, held
by other processes
 No preemption: Resources are released only voluntarily
 Circular wait: P0 must wait on a resource held by P1, which
in turn waits on a resource held by P2, … held by Pn-1,
which in turn waits on a resource held by P0
S. Manolache, Process programming and operating systems, Synchronisation
37
Resource Allocation Graph
R1
P1
R3
P2
R2
 Processresource edge
indicates resource request
 Resourceprocess edge
indicates that the resource is
held by the process
P3
R4
 Existence of cycles is a
necessary condition for the
existence of deadlocks
 Also sufficient if there exists only
one instance of each resource
S. Manolache, Process programming and operating systems, Synchronisation
38
Resource Allocation Graph
P2
R1
P3
P1
 We have a cycle, but no
deadlock
 When P4 releases an
instance of R2, P3 may
take it
R2
P4
S. Manolache, Process programming and operating systems, Synchronisation
39
Handling Deadlocks
 Deadlock avoidance
 Deadlock detection and recovery
S. Manolache, Process programming and operating systems, Synchronisation
40
Outline
 Need for synchronisation
 Synchronisation mechanisms
 System calls: pause, select, waitpid
 Message passing: blocking read/writes
 Race conditions, critical regions, atomic operations, busywaiting, hardware support for their implementation
 Synchronisation mechanisms
 Semaphores
 Monitors
 Re-entrant code
 Deadlock
 Classical problems of synchronisation
 Readers/writers, bounded buffer, dining philosophers
S. Manolache, Process programming and operating systems, Synchronisation
41
Classical Problems: Dining Philosophers
 Dining philosophers:
 They may eat only when they have both forks
 They cannot get both forks in one move
 Implement a resource (fork) access protocol for
philosophers such that they do not starve
S. Manolache, Process programming and operating systems, Synchronisation
42
Readers/Writers Problem
 There exists a shared resource
 Processes that do not change it upon an access are readers
 All the other are writers
 First readers/writers problem:
 No reader will be kept waiting unless a writer has already
obtained writing permission (Read accesses are not
blocked if a writer manifested interest in writing)
 Second readers/writers problem:
 Once a writer is ready, that writer performs its write as
soon as possible (Read accesses are blocked if a writer
manifested interest in writing)
S. Manolache, Process programming and operating systems, Synchronisation
43
Summary
 Need for processes synchronisation
 Race condition, critical section, atomic operations, mutual
exclusion
 Critical section access protocols
 Busy waiting
 Hardware support
 Semaphores, monitors, conditions
 Deadlocks
S. Manolache, Process programming and operating systems, Synchronisation
44