In sharing a resource, it is necessary to ensure "mutual exclusion". That is, during a period of one process using that resource, other process that also want that resource must wait. Dijkstra invented "semaphore" (1965) to achieve this mutual exclusion ("mutex") behaviour. A semaphore is a variable (can be binary, 0/1 or an integer) associated with a resource, indicates availability of the resource to the process that requested it. Two operations are defined on a semaphore: wait, signal (originally Dijkstra called it P, V). Associated with each semaphore is a waiting list of the process that wait on this semaphore. They are defined as follows:
signal(sem)
is called before wait(sem)
, we will not increment its value, so
the negative value shows the number of process that are waiting on this
semaphore. The value will never grow more than 1).process1()
process2()
for i =
1..5
for i = 11..15
wait
sem1
wait sem2
signal
sem2
signal sem1
print
i
print i
newsem(),
wait(), signal().
A semaphore is a block of
memory. The first slot is its value, initially is 1; the rest is the
waiting list. The list is just a list of pointer to the process, the
list is terminated by 0. The length of this list is easily found
because the number of the waiting process is exactly the negative number of
the semaphore value.trap 20 newsem()
return pointer to a semaphore in r27trap 21 wait(sem)
input sem in r1trap 22 signal(sem)
input sem in r1newsem()
a = alloc(16)
a[0] = 1
a[1] = 0
return a
wait(sem)
sem[0]--
if( sem[0] < 0 )
put current process to the list
block current process
signal(sem)
if( sem[0] < 1 ) sem[0]++
if( sem[0] <= 0 )
dequeue the first process from the list
wake it up
nextp()
(in s2
assembly) so that the process queue is compacted when there is a process
terminated (otherwise the queue continues to grow when wait()
and signal()
moves a process in/out of the queue). Here
is its pseudo code: nextp()
if( nump == 0 ) return 0
if( Q[qindex] == 1 )
compact Q from qindex to qend
qend--
else
qindex++
if( Q[qindex] == 0 ) qindex = 0
return Q[qindex]
cnt
). Both processes
share the same code. st r0 cnt
; cnt = 0
trap r0 #newsem
st retval sem ; sem =
newsem()
mov r1 #count ;
create process1
jal link createp
mov r1 #count ;
create process2
jal link createp
count()
i = 0
while i < 20
wait(sem)
cnt = cnt + 1
// protected shared variable
print cnt
signal(sem)
i++
C:\s21i\test>as21i mos5.txt
C:\s21i\test>sim21i mos5.obj
load program, last address 123
>g
interrupt
nump 2; Q idx 0: 2100 2116 0
[1] [2] [3] [4] [5] [6] [7] interrupt
nump 2; Q idx 1: 2100 2116 0
interrupt
nump 1; Q idx 0: 1 2116 0
[8] interrupt
nump 1; Q idx 0: 1 2100 0
<9> interrupt
nump 1; Q idx 0: 1 2116 0
[10] interrupt
nump 1; Q idx 0: 1 2100 0
<11> interrupt
nump 1; Q idx 0: 1 2116 0
[12] interrupt
nump 1; Q idx 0: 1 2100 0
. . .
<19> interrupt
nump 1; Q idx 0: 1 2116 0
[20] interrupt
nump 1; Q idx 0: 1 2100 0
<21> interrupt
nump 1; Q idx 0: 1 2116 0
[22] interrupt
nump 0; Q idx 0: 1 0
stop, execute 1142 instructions
>q
cnt
. They do
not access cnt
at the same time because it is protected by
semaphore sem
. Because they are not synchronised so one
process races ahead initially before the task switched. (I made the trap
print3
instruction so that it prints from process1 and process2
differently).
[1] [2] [3] [4] [5] [6] [7] interrupt
Then the two processes
synchronised on wait(sem)
and they increment cnt
alternately. Please observe the state of the process queue that shows "1" as
terminated process, "2100" process1, "2116" process2, the end of queue is
"0" and nump
is the number of process in the process queue.[8] interrupt
nump 1; Q idx 0: 1 2100 0
<9> interrupt
nump 1; Q idx 0: 1 2116 0
[10] interrupt
nump 1; Q idx 0: 1 2100 0
<11> interrupt
nump 1; Q idx 0: 1 2116 0
Please also observe that the process did
not stop when the count reach 20 because the other process has increment it
"after" this process has checked the stopping condition.
<21> interrupt
nump 1; Q idx 0: 1 2116 0
[22] interrupt
nump 0; Q idx 0: 1 0
stop, execute 1142 instructions
>q
0,
10, 1, 11, 2, 12, ...
C:\s21i\test>sim21i mos-sync.obj
load program, last address 137
>g
interrupt
nump 2; Q idx 0: 2100 2116 0
[10] interrupt
nump 1; Q idx 1: 2100 1 0
<0> interrupt
nump 1; Q idx 0: 1 2116 0
[11] interrupt
nump 1; Q idx 0: 1 2100 0
<1> interrupt
nump 1; Q idx 0: 1 2116 0
[12] interrupt
nump 1; Q idx 0: 1 2100 0
<2> interrupt
nump 1; Q idx 0: 1 2116 0
[13] interrupt
nump 1; Q idx 0: 1 2100 0
<3> interrupt
nump 1; Q idx 0: 1 2116 0
[14] interrupt
nump 1; Q idx 0: 1 2100 0
<4> interrupt
nump 1; Q idx 0: 1 2116 0
interrupt
nump 1; Q idx 0: 1 2100 0
interrupt
nump 0; Q idx 0: 1 0
stop, execute 804 instructions
>q
wait()
and signal()
is implemented as
"trap" instructions, they are "atomic", that is, they are not
interruptable. When you want to implement them in assembly language
you have to be careful to preserve this "atomic" property.