Semaphores.mod 2.2 KB

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