Transcript Signals, Semaphores and Deadlock

Definition
A semaphore is simply:
A non-negative integer, which apart from it’s initialisation, can be acted on only by
two standard, atomic, non-interruptible operations, WAIT( which decrements the
value of the semaphore) and SIGNAL (which increments the value).
1
Semaphores
• The semaphore essentially indicates the availability of a resource.
• If it is greater than zero it is available, if it zero it is not.
• The signal operation signals that a process has released a resource
which can now be used by a waiting process.
• The wait operation may allow a process access to the resource (s >
0) or may cause the process to be blocked.
• Wait and signal are indivisible.
• When semaphore which can be only 0 or 1 is called a binary
semaphore, otherwise it is a counting semaphore.
2
Semaphores
Producer – Consumer problem
•Bounded buffer
•Can be accessed by both simultaneously
•There are N slots in buffer
e.g. a print routine sending characters to a printer driver
There are essentially two requirements
•To guard against attempting to write to the buffer when it is full
•To prevent the consumer reading from the buffer when it is empty
3
Producer – Consumer problem.
•
Bounded buffer – it has a limited size. Often implemented as a circular
buffer. i.e. when last location full it starts to overwrite first location.
•
Can be accessed by producer and consumer simultaneously – problem!
•
Initially imagine there are N slots in buffer, e.g. a print routine sending
characters to a printer driver.
•
There are essentially two requirements
– to guard against attempting to write to the buffer when it is full
– to prevent the consumer reading from the buffer when it is empty
4
Producer
produce item
Explanation
Application produces data item
wait (space)
If buffer full, wait for space signal
wait (free)
If buffer being used, wait for free signal
add item to buffer
All clear; put item in next buffer slot
signal (free)
Signal that buffer no longer in use
signal (data)
Signal that data has been put in buffer
Consumer
wait (data)
Wait until at least one item in buffer
wait (free)
If buffer being used, wait for free signal
get item from buffer
All clear; get item from buffer
signal (free)
signal (space)
Signal that buffer no longer in use
Signal that at least one space exists in
buffer
consume item
Application specific processing of item.
Semaphore
free
Purpose
Initial
value
Mutual exclusion for buffer access
1
space
Space available in buffer
N
data
Data available in buffer
5
0
Semaphores for Mutual Exclusion
After initialisation the semaphore is 1 as shown in (a) i.e there are no
processes in the wait queue. After the first WAIT the semaphore is set to 0
(b). If a second process does a WAIT, the semaphore is not decremented
further, but that process is blocked and put in a wait queue(c). Any
subsequent processes that WAIT on that semaphore are added to the tail of
the queue(d).1
1
^
0
^
0
*
(a)
(b)
(c)
P1
0
*
P1
P2
(d)
When the first process does a SIGNAL and leaves the critical section, one of
the waiting processes is woken up and moved from the wait queue to the
run queue. The value of the semaphore is unchanged. All waiting processes
are then run and only when the last one leaves the critical section if the
semaphore restored to1.
6
Semaphores for Synchronisation.
Imagine two processes where Process A must not pass a point P1 in it’s code until process B has
reached a point P2 in it’s code. For example, A may require an item at P1 which is only provided by B
at point P2.
Process A
Process B
P1: ---WAIT(S)
P2: --- SIGNAL(S)
0
^
(a)
(b)
0
*
PA
(c)
If process A gets to P1 before B gets to P2 then A executes a WAIT on the semaphore, It is
blocked (0 value semaphore), and put in the wait queue. The signal changes from (b) to (c).
When B eventually gets to P2 and does a SIGNAL on the semaphore, A will be woken up, and
continue execution. The value of the semaphore is always 0 in this case.
7
Semaphores for Synchronisation
Another scenario is that B can get to P2 before A gets to P1. In this
case the value of the semaphore is incremented to 1.
Process A
Process B
P2: --- SIGNAL(S)
P1: ---WAIT(S)
0
^
(a)
(b)
1
^
(c)
It changes from the state shown in (b) to (c). Then when A does a WAIT, it is not
held up, but the semaphore is decremented, and returns to state (b).
8
Semaphores for resource management.
Resources can be physical things like printers or can be virtual resources such
a slots in a buffer.
The semaphore is initialised to the number of instances available. For
example, suppose there are two printers available. A semaphore P, to control
printer allocation, is initialised to 2.
2
^
1
^
process1
WAIT
(a)
process2
WAIT
(b)
0
^
process3
WAIT
(c)
0
*
P3
(d)
As each process requests a printer, it does a WAIT on the semaphore P. The first
process changes state of the semaphore to (b) and is granted the first printer. The
second process changes the state of the semaphore to (c) and is granted the second
printer. When the third process requests a printer and does a WAIT on the (zero
valued) semaphore, it is not allowed to continue, as there is no printer available. It is
put to sleep (d).
When one of the processes returns a printer, it does a signal on the semaphore, which
wakes up the waiting process and moves the state of the semaphore back to (c). 9
Deadlock

a circle of wait conditions exists

the driver of each car only ‘sees’ the car in front; no-one can see the
global situation

the deadlock can only be broken by one or more cars relinquishing the
space they occupy

it will generally require intervention from an outside agency (the police)
to resolve the problem.
10
Deadlock
Example
Airline booking – using file locking
•A locks AB123 – outgoing flight
•B locks AB456 – return flight
•A requests AB456 – return flight
•B requests AB123 – outgoing flight
Clerk(s) may nor realise the long wait is their fault (can only see
car in front)
11
Deadlock
Consumer –producer problem
The normal situation for a producer is:
produce item
wait (space)
wait (free)
add item to buffer
signal (free)
signal (data)
12
Deadlock
Producer
produce item
wait (free)
wait (space)
add item to buffer
signal (free)
signal (data)
Consumer
wait (data)
wait (free)
get item from buffer
signal (free)
signal (space)
consume item
Explanation
Can enter if no process in critical region. free = 0
Can’t continue if buffer full - blocked
o.k. to proceed as buffer is full
can’t progress as free =0 – Deadlock!!!
13
Deadlock
There are three necessary and sufficient conditions for deadlock to occur:
1. The resources involved cannot be shared; only one process at a time can use
a particular resource.
2. No preemption – once a resource has been allocated to a process, that resource
cannot be preempted by another process. Processes hold on to the resources
they have been allocated until they release them voluntarily.
3. Processes can request additional resources at any time request additional
resources at any time.
These are necessary, but will not cause deadlock without
4. There must be a circular chain of two or more processes, each waiting
for a resource held by the next process in the chain
14
Critical Sections
• For satisfactory mutual exclusion
– no two processes in critical region at any time
– no assumptions are to be made about speed or
number of CPU’s
– no process outside critical region may be blocked
– no process to wait forever to enter critical region
• Solutions
– Disable interrupts
• unwise to allow processes to disable interrupts
• may not turn them on again
• more than one processor disabling interrupts affects only
one CPU – hence can still access shared memory
• kernel may disable interrupts
15
Deadlock
Since these are necessary and sufficient conditions, the deadlock can be
broken if any one of them is denied.
• If the trains could somehow magically pass through each other, then
the first condition would be denied since the trains could occupy the
same section of track at the same time.
• If the train could push the other down the track, it would be
preempting the use of track that the other was occupying, thus denying
the second condition.
• The third condition could be denied by forcing both trains to claim all
sections of the track at once before going on to the beginning of the
track..
• The fourth condition is denied if both trains are going in the same
direction, since the train in front never needs to use a section of track
occupied by the train behind.
16
Deadlock
Three strategies
•
Deadlock prevention
•
Deadlock avoidance
•
Deadlock detection
Deadlock prevention
•Mutual exclusion – not a starter
•Resource holding – process requests all its resources at once.
cannot proceed until it gets them all.
Inefficient resource required late in process
may prevent other processes proceeding
•No preemption – allow operating system to take away resources.
17
Deadlock
Circular wait – hierarchic allocation. Resource requests in a particular
order.
e.g.
(1) CD-ROM
(2) printer
(3) plotter
(4) tape drive
(5) robot arm
If Process A has CD-ROM and requests the printer while process B has
the printer and requests the CD-ROM we have deadlock. If resources
allocated in numerical order this cannot happen.
18
Deadlock
Deadlock avoidance
Predicts the possibility of a deadlock
Processes are allowed to make resource requests – but
will be denied if unsafe
Bankers algorithm –
Banker lends funds,(all same currency) to a number of clients
Each has declared maximum amount he will require
May request money in stages – doesn’t need to pay back until
he has taken the full loan
Bankers reserve is usually less than the sum of clients demands
Client requests loan – has banker enough left to make the further
loans that will allow clients to repay?
19
Bankers Algorithm
Name
Andy
Safe
6
Barbara
0
5
Marvin
0
4
Suzanne
Available 10
0
7
Used
Maximum
1
6
Barbara
1
5
Marvin
2
4
Suzanne
Available 2
4
7
Name
Andy
Unsafe
Maximum
0
Name
Andy
Safe
Used
Used
Maximum
1
6
Barbara
2
5
Marvin
2
4
Suzanne
Available 1
4
7
Replace
Banker Operating
system
Client  process
Funds  resource
20
Deadlock Detection and Recovery
•
The approach adopted by Unix and Microsoft. Assume that it is a low probability
risk, and to do nothing. Simplicity but not good in life critical situations
•
If deadlock occurs, first necessary to detect it, and then recover from it. The
‘Ostrich Algorithm leaves it to the user to notices that nothing much is happening
and kills one or more processes.
•
Automatic deadlock detection uses a separate process to monitor if there is a
circular chain and deduces that there is deadlock.
•
One way to recover is to apply force majeure by killing one or more of the
deadlocked processes. Could ask the user or to select a process at random to kill.
o.k. for a compiler but may cause problems with an editor where there may be a
lot of unsaved data which would be lost.
•
In some cases like a database, killing the process may leave the database in an
inconsistent state. Restarting the process could make matters worse.
•
A solution to situations like this is to take a checkpoint of each process after an
important update. A checkpoint is a snapshot of the state of the entire system.
This is saved on disk so that the process can be rolled back to the latest checkpointed state.
21
Livelock
• Two people are trying to pass in a corridor. Both single step
to the same side of the corridor, thus blocking each other.
In an attempt to correct the situation both move to the
other side of the corridor, blocking each other again.
– Differences in timing will normally resolve the situation. The
difference between livelock and deadlock is that there is still some
activity, but it may not be achieving anything useful.
• Ethernet is an example of livelock where two processes
transmit data at the same time and when they clash, both
back off and then retransmit after a random delay.
– On a heavily loaded network, the result will be that the competing
machines will back off for longer and longer periods. As the load
increases the network performance will drop gradually known as
graceful degradation, where the performance is degraded in a
22
graceful way rather than failing abruptly.
Deadlock
Problems
•Each process has to pre-declare its maximum resource requirements.
Not realistic for interactive systems
•The avoidance algorithm must be executed every time a resource
request is made. For a multi-user system, the processing overhead would
be too great
Deadlock detection
•Operating system must retain a list of what resource each blocked process is
waiting for and which process holds that resource.
•Algorithm to detect circular chains
•Recovery – usually means restarting one or more processes
•Sometimes unblocked processes run to completion and release resources
•Principal cost of recovery from deadlock is time
23
The End
24
Fig 1 Two processes competing for memory at the same time
Spooler
Directory
.
.
.
Process A
Process B
4
abc
5
Prog.c
6
Prog.n
7
out = 4
in = 7
25
Deadlock
The conditions for deadlock can be explained using the following analogy:
2 trains heading towards each other on the same track, where the processes or
threads are the trains, and the resources are the sections of track.
•
Condition 1 - The first condition means that you cannot have two trains at
exactly the same place at the same time.
•
Condition 2 - The second condition means that a train may not be pushed
aside or otherwise forcibly removed from the section of track that it is on.
•
Condition 3 - The third condition means that a train (which already occupies a
section of track) can occupy another section of track by moving forwards.
•
Condition 4 - The fourth condition occurs when the two trains meet head on;
they are both stuck waiting for an opportunity to move forward onto the
section of the track occupied the other, while at the same time occupying the
section of track that the other needs.
26
Lock Variables
Initially 0
process enters critical region
if lock = 0
process sets lock = 1
enter critical region
else if lock = 1
(i)
wait until lock = 0
if process gets to (i) and is interrupted
then 2nd process sets lock = 1
now if process 2 swapped out while in critical region
process 1 restarts it will now also be in critical region
27
Strict Alternation
while (TRUE)
{
while (turn = 0) ;
critical region();
turn = 0;
noncritical_region()
}
Process0
while (TRUE)
{
while (turn = 1);
critical region();
turn = 1;
noncritical_region()
}
Process1
•
turn is initially 1, hence Process0 enters critical region meanwhile Process1 sits
in loop. As Process0 leaves critical region , sets turn = 0 to allow Process1 to
enter critical region .
•
If one Process0 much slower than Process1, then process will not be able to reenter critical region .
28
Test and Set Lock(TSL)
Hardware solution
Copies the old value of lock from memory to CCR - sets lock = 1
Compare the old value with 0
if lock = 1
loop
else
enter critical region
Note The tsl command is indivisible therefore cannot be interrupted part way through
copying old value to CCR and setting lock to 1
On leaving the critical region reset lock to 0.
enter_region:
tsl register,lock
/*copy lock to register and set lock to 1 */
cmp register,#0 /* was lock zero? */
jne enter_region /*if it was non zero, lock was set, so loop*/
ret
/*return to caller; critical region entered*/
leave_region:
move lock,#0
/* store a 0 in lock */
ret
/* return to caller */
•
This solution works!
29
Semaphores
wait(s):
if s> 0 then
set s to s - 1
else
block the calling process (ie. wait on s)
endif
signal(s):
if any processes are waiting on s
start one of these processes
else
set s to s + 1
endif
30
Interprocess Communication
•
•
•
•
Signals
Shared files i.e pipes
Message passing
Shared memory
Signals
• Like an interrupt
• From user process to kernel
• e.g. CTRL C – kernel sends a signal SIGINT
terminates execution
31
• Signals are a relatively low level inter-process communication method
which is used in UNIX. The signal arranges for a user defined function
to be called, when a particular event occurs.
• Synchronous signals - frequently generated by the hardware when an
internal error has occurred such as - divide by zero, illegal instruction,
memory access violation etc. These always happen at the same place
each time a program is run – hence the term synchronous.
• Asynchronous signals – their occurrence is normally random. There
are three main sources of such signals:
 Another process. The system call used to send a signal is kill().
 A terminal driver sends a signal when a special key is pressed. e.g the
panic key combination in UNIX is CTRL-C. This sends the SIGINT
which generates an interrupt.
 The alarm() library call which resets any previous setting of a timer.
The kernel sends SIGALARM to the calling process when the time
expires. The default action terminates the process.
32
Signal Program
Example
#include <signal.h>
#include <stdio.h>
#include <unistd.h>
void ouch(int sig)
{
printf("OUCH! – I got signal %d\n, sig);
}
main()
{
signal(SIGINT, ouch);
while(1)
{
printf("Hello world\n");
sleep(1);
}
}
33
Name
Description
SIGHUP
hang up-sent to processes when terminal logs out
SIGINT
terminal initiated interrupt
SIGQUIT
another terminal interrupt which forces a memory dump
SIGILL
illegal instruction execution
SIGTRAP
trace trap-used by certain UNIX debuggers
SIGFPE
floating point exception
SIGKILL
sent by one process to terminate another
SIGSEGV
segment violation-memory addressing error
SIGSYS
irrecoverable error in system call
SIGPPE
write to a pipe with no reader process
SIGALARM
sent to a process from kernel after time expires
SIGTERM
sent by user process to terminate a process
SIGUSR1,2
user defined signals sent by user processes
34
Inter Process Communication
• Pipes
ls –l|more
Pipes remain alive only as long as process which created them
i.e. unread data when process terminates will be lost
• Named Pipes
FIFO – i.e. a permanent UNIX file
Can be opened by any number of processes for reading
and writing – would require access permissions.
• Message passing - communication via message queues
• Shared memory - area of memory shared by two or more
processes
35
Interprocess Communication
Name
Description
SIGHUP
hang up-sent to processes when terminal logs out
SIGINT
terminal initiated interrupt
SIGQUIT
another terminal interrupt which forces a memory dump
SIGILL
illegal instruction execution
SIGTRAP
trace trap-used by certain UNIX debuggers
SIGFPE
floating point exception
SIGKILL
sent by one process to terminate another
SIGSEGV
segment violation-memory addressing error
SIGSYS
irrecoverable error in system call
SIGPPE
write to a pipe with no reader process
SIGALARM
sent to a process from kernel after time expires
SIGTERM
sent by user process to terminate a process
SIGUSR1,2
user defined signals sent by user processes
36
Dynamic Data Exchange
Dynamic Data Exchange (DDE) system is actually a protocol (or set of
guidelines) that enables DDE-compatible Windows applications to share data
easily with other compatible applications.
DDE
Client
Initiate conversation
Send server command
Request server data
Receive server data
Send data to server
Close conversation
DDE
Server
37
Object Linking and Embedding
•OLE enables you to create data (called an object) in an application.
•An object can be almost anything, such as a bitmap, an audio file, a video clip,
or a spreadsheet.
•You can embed or link that object data to other data created with another
application.
•Editing becomes much more convenient because you can then edit from within
the compound document.
38
Question 7
Suggest a more appropriate name for the signal and kill system calls.
Answer to question 7
In order to reflect their actual usage, more appropriate names might be trapsig for
signal and sendsig for kill
39
Monitors
Program that all processes accessing shared data must use
The monitor obeys the following constraints:
•Only one process can be active
•Can only access data local to the monitor
•Variables cannot be accessed from outside (data hiding)
Entry
queue
2
1
Procedures
40
Interprocess Communication
•signals
•shared files i.e. pipes
•message passing
•shared memory
•Dynamic Data Exchange (DDE)
•Object Linking and Embedding (OLE)
Signals
•Like an interrupt
•From user process to kernel
•e.g. CTRL C – kernel sends a signal SIGINT
•
terminates execution
41
Interprocess Communication
Trapping and handling signals
1 Ignore the signal
2. Execute a special handler function
3. apply default handling (i.e. abort)
e.g.
signal(SIGFPE,handle_fpe)
where handle_fpe is the function called
Sending signals
where
kill(pid,sig)
pid is the process identifier
sig is the signal being sent
42
Interprocess Communication
Pipes
ls –l|more
Pipes remain alive only as long as process which created them
i.e. unread data when process terminates will be lost
Named Pipes
FIFO – i.e. a permanent UNIX file
Can be opened by any number of processes for reading
and writing – would require access permissions.
Message passing
communication via message queues
Shared memory
area of memory shared by two or more processes
43
File and Record Locking
Example
Airline seat reservations
•Flight AB101 2 customers for 1 seat
•2 clerks copy booking list to local terminals
•Customer A reserves seat
•Customer B still has original copy and also reserves seat overwriting
customer A’s reservation.
File locking may be used to prevent other people writing to a file which is
open.
There are 3 types of lock:
•File lock – can’t do anything – overkill, nobody can access this file,
even for other actions but o.k when archiving etc.
•Write lock – cannot modify or read. Used when records are being
updated, ensures mutual exclusion. No reads to prevent partially
updated records being read
44
•Read lock – can read but cannot write. Gives most freedom. All write
File and Record Locking
Pessimistic – as described on previous slide.
•
Assumes worst case
•
o.k. if high chance of simultaneous access
•
guaranteed – what you see is what you get
Optimistic – copies file, updates it.
•
on write back it locks the record and checks if anyone
•
else is modifying the data.
•
if they are then re-start the transaction
•
more efficient
•
more hassle if clash occurs
•
may not see latest data
45
int reader_count, busy;
condition ok_to_read, ok_to_write;
readercount = 0;
busy = false;
procedure start_read()
begin
if (busy then ok_to_read.wait);
reader_count++;
ok_to_read.signal; /*Once one reader can start they all can*/
end
procedure end_read()
begin
reader_count--;
if (reader_count ==0 then ok_to write.signal)
end
procedure start_write()
begin
if ( busy or reader_count != 0 then ok_to_write.wait)
busy = true;
end
procedure end_write()
begin
busy = false;
if (ok_to_read.queue then ok_to_read.signal);
else
ok_to_write.signal;
46