Repository navigation
Expand file tree
/
Copy pathSemaphores.mod
More file actions
executable file
·118 lines (106 loc) · 2.18 KB
/
Copy pathSemaphores.mod
File metadata and controls
executable file
·118 lines (106 loc) · 2.18 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
(*
(c) copyright 1988 by the Vrije Universiteit, Amsterdam, The Netherlands.
See the copyright notice in the ACK home directory, in the file "Copyright".
*)
(*$R-*)
IMPLEMENTATION MODULE Semaphores [1];
(*
Module: Processes with semaphores
Author: Ceriel J.H. Jacobs
Version: $Header$
Quasi-concurrency implementation
*)
FROM SYSTEM IMPORT ADDRESS, NEWPROCESS, TRANSFER;
FROM Storage IMPORT Allocate;
FROM random IMPORT Uniform;
FROM Traps IMPORT Message;
TYPE Sema = POINTER TO Semaphore;
Processes = POINTER TO Process;
Semaphore =
RECORD
level: CARDINAL;
END;
Process =
RECORD next: Processes;
proc: ADDRESS;
waiting: Sema;
END;
VAR cp: Processes; (* current process *)
PROCEDURE StartProcess(P: PROC; n: CARDINAL);
VAR s0: Processes;
wsp: ADDRESS;
BEGIN
s0 := cp;
Allocate(wsp, n);
Allocate(cp, SIZE(Process));
WITH cp^ DO
next := s0^.next;
s0^.next := cp;
waiting := NIL;
END;
NEWPROCESS(P, wsp, n, cp^.proc);
TRANSFER(s0^.proc, cp^.proc);
END StartProcess;
PROCEDURE Up(VAR s: Sema);
BEGIN
s^.level := s^.level + 1;
ReSchedule;
END Up;
PROCEDURE Down(VAR s: Sema);
BEGIN
IF s^.level = 0 THEN
cp^.waiting := s;
ELSE
s^.level := s^.level - 1;
END;
ReSchedule;
END Down;
PROCEDURE NewSema(n: CARDINAL): Sema;
VAR s: Sema;
BEGIN
Allocate(s, SIZE(Semaphore));
s^.level := n;
RETURN s;
END NewSema;
PROCEDURE Level(s: Sema): CARDINAL;
BEGIN
RETURN s^.level;
END Level;
PROCEDURE ReSchedule;
VAR s0: Processes;
i, j: CARDINAL;
BEGIN
s0 := cp;
i := Uniform(1, 5);
j := i;
LOOP
cp := cp^.next;
IF Runnable(cp) THEN
DEC(i);
IF i = 0 THEN EXIT END;
END;
IF (cp = s0) AND (j = i) THEN
(* deadlock *)
Message("deadlock");
HALT
END;
END;
IF cp # s0 THEN TRANSFER(s0^.proc, cp^.proc); END;
END ReSchedule;
PROCEDURE Runnable(p: Processes): BOOLEAN;
BEGIN
IF p^.waiting = NIL THEN RETURN TRUE; END;
IF p^.waiting^.level > 0 THEN
p^.waiting^.level := p^.waiting^.level - 1;
p^.waiting := NIL;
RETURN TRUE;
END;
RETURN FALSE;
END Runnable;
BEGIN
Allocate(cp, SIZE(Process));
WITH cp^ DO
next := cp;
waiting := NIL;
END
END Semaphores.