Transcript Synchronisation Primitives

Operating Systems: Sema
Synchronisation Primitives
Hardware Approach
–modifying a shared variable must be made an indivisible operation - atomic
• test-and-set
test-and-set (int lock) {
int temp;
temp = lock;
lock = 1;
return temp;
}
–mutual exclusion achieved by:
while (TRUE) {
while ( test-and-set(lock) == 1) { /* wait */ }
critical section
lock = 0;
....
}
1
Operating Systems: Sema
• swap
swap (int a, b) {
int temp;
temp = a;
a = b;
b = temp;
}
– mutual exclusion achieved by:
while (TRUE) {
key = 1;
while ( key == 1) { swap( lock, key ); }
critical section
lock = 0;
....
}
• increment-and-test with test-and-decrement
–for counting how many processes waiting to enter a critical section
2
Operating Systems: Sema
Motorola 68000
3
Operating Systems: Sema
Intel x86
4
Operating Systems: Sema
Intel x86
5
Operating Systems: Sema
Intel x86
6
Operating Systems: Sema
Sparc
7
Operating Systems: Sema
ICL2900
8
Operating Systems: Sema
ICL2900
9
Operating Systems: Sema
• hardware approach
– applicable to any number of processes on single or multi-processor
– simple and easy to verify
– can support multiple critical sections, each with their own control variable
• problems
– busy-waiting
– deadlock
– starvation
10
Operating Systems: Sema
• Bounded-waiting solution possible (Silberschatz & Galvin):
shared variable : waiting [0:n-1] = 0(n), lock = 0;
process I
variable key = 0;
while (TRUE) {
waiting [I] = 1;
key = 1;
while ( waiting [I]==1 && key==1) {
key = test-and-set (lock);
}
waiting [I] = 0;
critical section i
j = (I+1) % n;
while ( j!=i && waiting [j]==0) { j = (j+1)%n; }
if (j==i) lock = 0; else waiting [j] = 0;
....
}
11
Operating Systems: Sema
Abstract approach : Semaphores (Dijkstra)
• Definition: A semaphore is a non-negative integer which can only be acted
upon by the operations P and V, both of which are atomic
P : decrement the semaphore by 1 as soon as the result would be non-negative
V : increment the semaphore by 1
For a semaphore s :
P(s) :while (s==0) { /*wait */ }
s = s-1;
V(s) :s = s+1;
– busy-waiting still implied for P(s)
12
Operating Systems: Sema
• Mutual exclusion
semaphore mutex = 1;
process
while (TRUE) {
P(mutex);
critical section
V(mutex);
....
}
– mutex = 0 when process in its critical section
= 1 when outside
– binary semaphore only takes the values 0 and 1
– general or counting semaphores take any non-negative value
13
Operating Systems: Sema
• Synchronisation
– example: statement S1 of process 1 must be executed before statement S2
of process 2 :
semaphore : synch = 0;
process 1
process 2
S1;
V(synch);
....
P(synch);
S2;
....
– example: producer/consumer using unbounded buffer :
semaphore : items = 0;
producer process
while (TRUE) {
produce item
put item in buffer
V(items);
}
consumer process
while (TRUE) {
P(items);
take item from buffer
consume item
}
» items is a counting semaphore
14
Operating Systems: Sema
For a bounded circular buffer producer/consumer :
semaphore : items = 0, space = max;
producer process
consumer process
while (TRUE) {
while (TRUE) {
produce item
P(items);
P(space);
new item = buffer [get];
buffer [put] = new item;
get = (get+1) % max;
put = (put+1) % max;
V(space);
V(items);
consume item
}
}
15
Operating Systems: Sema
• Semaphores are used in real operating systems
– to protect access to shared areas e.g. file directories, kernel tables
– to synchronise process and I/O devices
» input device driver producer/consumer model, user process producing
output, device-driver consuming it
– client/server model:
server synchronised by semaphore s, user by semaphore u
server process
P(s)
....
....
V(u)
user process
....
V(s)
P(u)
....
– system call to create semaphores when required
– in practice, semaphores always implemented so as to avoid busy waiting
16
Operating Systems: Sema
• Counting semaphores
– can be implemented by a binary semaphore and a count variable
– relevant when atomic machine instructions only implement binary semaphores
semaphore : buff = 1, delay = 0;
int items = 0;
producer process
while (TRUE) {
produce item
P(buff);
put item in buffer
items =items+1;
if (items==1) V(delay);
V(buff);
}
consumer process
while (TRUE) {
P(delay);
P(buff);
take item from buffer
items = items -1;
if (items>0) V(delay);
V(buff);
consume item
}
– buff protects use of shared variable items
17
Operating Systems: Sema
Implementation of Semaphores
• Using hardware instructions
– for binary semaphores :
P(s) :
while ( test-and-set (s) == 1) { /* wait */ }
or
P(s) :
ss = 1;
while ( ss == 1) { swap (s, ss); }
V(s) :
s = 0;
– for counting semaphores
» test instructions set a condition code register, cc
P(s) :
V(s) :
wait: test-and-decrement (s);
if ( cc <= 0 ) { increment-and-test (s); goto wait; }
increment-and-test (s)
18
Operating Systems: Sema
• ICL 2900 used INCT and TDEC in reverse :
-1 : semaphore free
0 : semaphore claimed but no-one waiting
>0 : number of process waiting
– INCT used for P operation, TDEC used for V operation
– condition code tested the values:
>0
=0
-1
< -1
– used to synchronise CPU with peripheral I/O channel and device controllers
• Machines sometimes have built-in semaphore instructions
• Busy-waiting potentially very wasteful of CPU time and inefficient
• Semaphores most often implemented by system calls to kernel
– can avoid busy-waiting by using process scheduling queues
19
Operating Systems: Sema
Removal of Busy-waiting
• Kernel process scheduling functions include :
– maintaining a run queue of processes ready to run
– maintaining priority queues of processes e.g. background jobs
– maintaining queues of blocked processes, waiting on some event
– suspending processes and preserving their context
– re-activating processes - the dispatcher
• Events that can block processes include :
– page and segment faults
– completion of I/O transfers
– awaiting a signal of some sort
– awaiting an inter-process message
– process swapped out to disc
– awaiting a semaphore
20
Operating Systems: Sema
• Implementation of semaphores by system calls to the OS kernel
– semaphore variable held by the kernel
– each semaphore has its own scheduling queue
– P and V operations now modified :
P(s) :
if ( s>0 ) s = s-1;
else suspend process and enqueue it
V(s) :
if ( queue empty ) s = s+1;
else unqueue next waiting process and enqueue on ‘run’ queue
– dispatcher will re-activate released process in due course
21
Operating Systems: Sema
Suspend process
• to preserve to the complete state of the process - its context
• process can be resumed later without any effect except gap in time
• preserve the processes virtual memory contents :
– all programs, shells, libraries, stack, heap and data areas, comms buffers etc.
– option 1 : leave in situ
– option 2 : swap out to disc
22
Operating Systems: Sema
• preserve the volatile context
– processor registers :
» program counter, stack pointers etc.
» general purpose and floating point registers
» status registers, interrupt masks, condition codes etc.
• preserve per process kernel data
– segment and page virtual memory tables
– location of process swap area on disc
– scheduling status information
– IDs - user, group, parent etc.
– accounting data
– pending signals, events
– open files, sockets etc.
23
Operating Systems: Sema
Process Context Block (PCB)
• Process context is all held in a PCB (or referenced from it)
process number
program counter
stack pointer
status register, cc etc.
GP + FP registers
swap area on disc
pointer to VM tables
pointers to other kernel data
scheduling queue link
24
Operating Systems: Sema
• Some machines have replicated sets of registers for each mode
– one set for normal user execution
– another set for interrupt mode
– example : ICL 4-75 had 4 sets registers
» two full sets of 16 for user and kernel
» two more reduced sets for interrupt response modes
– example : the ARM processor has 6 modes:
» user - normal execution
» FIQ - Fast Interrupt reQuest
» IRQ - normal interrupt request
» Supervisor - protected and privileged for kernel execution
» Abort - after a data or instruction abort
» Undefined - after an undefined op. Code executed
25
Operating Systems: Sema
ARM
26
Operating Systems: Sema
• for machines without parallel register sets, the complete volatile context is
often dumped automatically into memory :
– on interrupt
– on mode change
– either into a dedicated memory area
– or onto the top of the stack
– example : Intel x86 TSS (Task State Segment)
• sometimes, just the PC and status registers are dumped
– the new mode has to preserve the GP and FP registers itself
» often single instructions to do this
» example : STM (store multiple registers) on the ARM (with LDM for reloading)
– very careful programming usually required!
» often needs to be in assembly code to avoid conflicts of register use from
compiled code
27
Operating Systems: Sema
Intel x86 Task
State Segment
28
Operating Systems: Sema
• linked PCBs often form the scheduling queues :
run queue
I/O blocked
queue
semaphore
queue
29
Operating Systems: Sema
• Changing from one process to another can be very costly :
– preserving and reloading the volatile context
– possibly swapping memory image out and in from disc
– kernel mode change
– loss of virtual memory context - TLB
– loss of CPU execution pipeline contents
– loss of cache context
» instructions and data caches relate to execution of previous process
• a significant loss of overall performance can result
– rate of changing between processes must be controlled
– for P and V operations between processes, context changing unavoidable
– use of threads can help considerably
• system calls can also consume significant amounts of CPU time
• total kernel overheads can be alarmingly large!
– not always as much concern as it should be!
30
Operating Systems: Sema
• Scheduler Run Queue
– the V semaphore operation releases a process waiting for a semaphore
– its PCB transferred from the semaphore queue :
» to the run queue if it is still memory resident and ready to go
» to a blocked queue while it is swapped back in from disc
• Scheduler
– organises PCB queues
» which priority queue
» which blocked queue - awaiting disc transfer, semaphore etc.
» and in what order - probably first-come-first-served
– tries to work ahead of currently running process
» so that there is always another process ready to run
» may need to reschedule memory usage ahead of time
» may need to initiate swapping in a process from disc
» may need to ensure process causing blockage is run
» possibility of deadlocks occurring otherwise
31
Operating Systems: Sema
– important to avoid CPU wastage
– overall scheduling strategy to meet particular objectives
» batch streams
» single user systems
» shared server systems
» real-time systems
• Dispatcher
– takes next PCB off run queue
– reloads its volatile context
– exits the kernel to continue the re-activated process
– ‘return-from-interrupt’ instruction often provided
» like a ‘return-from-subroutine’ instruction buts reloads context also
32
Operating Systems: Sema
• In more detail, semaphore ops are now :
P(s) :
if (s>0) { s = s-1; continue to run * }
else { preserve process context in PCB
goto dispatcher }
V(s) :
if (semaphore queue empty) { s = s+1; continue to run * }
else { take PCB off semaphore list
put PCB on Run queue
continue to run * }
– * instead of continue to run, could have instead :
preserve context
goto dispatcher
– i.e. process issuing P or V is also rescheduled
» gives the kernel more control - an extra opportunity to reschedule
33
Operating Systems: Sema
• Example: ICL 2900 semaphores
-1 : free
0 : claimed
>0 : number of processes waiting
P(s) :
INCT (s)
if (cc > 0) SVC (enqueue this process on semaphore s queue)
V(s) :
TDEC (s)
if (cc > 0) SVC (unqueue next process on semaphore s queue)
– potential problem ?
– advantage : no SVC overhead if no contention for semaphore
– disadvantage : kernel doesn’t know who has the semaphore
34
Operating Systems: Sema
• Example : device-driver
semaphore : dd, request, requestor
user process
device-driver process
set up request data
V(request);
P(requestor);
use transferred data
while (TRUE) {
P(request);
start transfer
P(dd);
deal with transfer termination interrupt
V(requestor)
– interrupt vector table consists of entry point addresses for each device :
.....
goto serial
goto parallel
.....
– code for each device :
serial:
V(serial_dd);
goto dispatcher
parallel:
V(parallel_dd);
goto dispatcher
35
Operating Systems: Sema
Intel x86
36
Operating Systems: Sema
Intel x86
37
Operating Systems: Sema
• Deadlocks very possible using semaphores :
process 1
process 2
P(s)
P(t)
....
V(s)
V(t)
P(t)
P(s)
....
V(t)
V(s)
– depending on the exact order of statement execution, each process could
claim their first semaphore and then wait forever to get the other
– deadlock loops can involve any number of processes :
process 1
P(s)
P(t)
....
V(s)
V(t)
process 2
P(t)
P(u)
....
V(t)
V(u)
process 3
P(u)
P(s)
....
V(u)
V(s)
– need to be very careful to avoid deadlocks
38