home *** CD-ROM | disk | FTP | other *** search
/ Columbia Kermit / kermit.zip / ckscripts / dining-philosophers < prev    next >
Lisp/Scheme  |  2020-01-01  |  5KB  |  206 lines
  1. # From: Dat Thuc Nguyen                                   -*-kermit-*-
  2. # Date: Mon, 03 May 2004 15:12:56 -0400
  3. # Subject: The Art of Programming in C-Kermit
  4. #
  5. # From time to time I sent in C-Kermit scripts that solve some problems people
  6. # also solved in other programming languages.
  7. #
  8. # Today I am sending in a program that's difficult since it requires
  9. # the notions of semaphore, process, timer and concurrency.
  10. #
  11. # The "dinning philosophers" problem is stated in Operating System Concepts by
  12. # Peterson and Silberschatz, 1985, pp. 347-348.
  13. #
  14. # Requires the 'class' module.
  15. #
  16. # Version 2: I fine tune the Dinning Philosophers script to
  17. # accomodate any numbers of hungry Philosophers instead of only five.
  18.  
  19. take class
  20.  
  21. define randnum {
  22. # \%1 random seed
  23.     while true {
  24.         if {\fsexpr(> (let rd \frandom(\%1)) 0)} return \m(rd)
  25.     }
  26. }
  27.  
  28. class Semaphore
  29.  
  30. define Semaphore::new: {
  31.     (setq \%1.Semaphore.stat -1)
  32.     _asg \%1.Semaphore.Queue |
  33.     (\%1)
  34. }
  35.  
  36. define Semaphore>>acquire {
  37.     local s
  38.     (setq s (++ \%1.Semaphore.stat))
  39.     if > s 0 {
  40.         _asg \%1.Semaphore.Queue \m(\%1.Semaphore.Queue)\%2|
  41.         echo \%2 waits for \m(\%2.\%1.ChopStick)
  42.     } else {
  43.         echo \%2 grabs \m(\%2.\%1.ChopStick)
  44.     }
  45.     (! s)
  46. }
  47.  
  48. define Semaphore>>release {
  49.     (-- \%1.Semaphore.stat)
  50.     local \&w[] 
  51.     if > \fsplit(\m(\%1.Semaphore.Queue),&w,|) 0 {
  52.         _asg \%1.Semaphore.Queue \freplace(\m(\%1.Semaphore.Queue),|\&w[1]|,|)
  53.         DiningPhilosophers add: \&w[1]
  54.         echo \&w[1] grabs \m(\&w[1].\%1.ChopStick)
  55.     }
  56.     (\%1)
  57. }
  58.  
  59. define Semaphore>>inspect {
  60.     echo \%1 \m(\%1.Semaphore.stat)
  61.     echo \%1 \m(\%1.Semaphore.Queue)
  62. }
  63.  
  64. class Philosopher
  65.  
  66. define Philosopher::new:leftChopStick:rightChopStick:place: {
  67. # \%2 leftChopStick
  68. # \%3 rightChopStick
  69.     (setq \%1.leftChopStick \%2)
  70.     (setq \%1.rightChopStick \%3)
  71.     (setq \%1.Philosopher.Number \%4)
  72.     _asg \%1.\%2.ChopStick left ChopStick
  73.     _asg \%1.\%3.ChopStick right ChopStick
  74.     _asg \%1.Philosopher.act thinking
  75.     (setq \%1.Philosopher.timeRepeat (randnum 15))
  76.     (\%1)
  77. }
  78.  
  79. define Philosopher>>act {
  80.     (-- \%1.Philosopher.timeRepeat)
  81.     if == \m(\%1.Philosopher.timeRepeat) 0 {
  82.         (setq \%1.Philosopher.timeRepeat (randnum 50))
  83.         return \fsexpr(\%1 '\m(\%1.Philosopher.act))
  84.     } else {
  85.         return 1    # line up in the process queue
  86.     }
  87. }
  88.  
  89. define Philosopher>>thinking {
  90.     echo \%1 is thinking
  91.     _asg \%1.Philosopher.act getChopStick
  92.     (1)     # line up in the process queue
  93. }
  94.  
  95. define Philosopher>>getChopStick {
  96.     (AND (\%1 'getFirstChopStick) (\%1 'getSecondChopStick))
  97. }
  98.  
  99. define Philosopher>>getFirstChopStick {
  100.     _asg \%1.Philosopher.act getSecondChopStick
  101.     if {\fsexpr(mod \%1.Philosopher.Number 2)} {    # odd
  102.         return \fsexpr(\m(\%1.leftChopStick) 'acquire \%1)
  103.     } else {    # even
  104.         return \fsexpr(\m(\%1.rightChopStick) 'acquire \%1)
  105.     }
  106. }
  107.  
  108. define Philosopher>>getSecondChopStick {
  109.     _asg \%1.Philosopher.act eat
  110.     if {\fsexpr(mod \%1.Philosopher.Number 2)} {    # odd
  111.         return \fsexpr(\m(\%1.rightChopStick) 'acquire \%1))
  112.     } else {    # even
  113.         return \fsexpr(\m(\%1.leftChopStick) 'acquire \%1))
  114.     }
  115. }
  116.  
  117. define Philosopher>>eat {
  118.     echo \%1 is eating
  119.     _asg \%1.Philosopher.act release_ChopSticks
  120.     (1)
  121. }
  122.  
  123. define Philosopher>>release_ChopSticks {
  124.     echo \%1 releases both Chopsticks
  125.     _asg \%1.Philosopher.act sleep
  126.     (\m(\%1.leftChopStick) 'release)
  127.     (\m(\%1.rightChopStick) 'release)
  128.     (1)
  129. }
  130.  
  131. define Philosopher>>sleep {
  132.     echo \%1 is sleeping
  133.     _asg \%1.Philosopher.act wakeup
  134.     (1)
  135. }
  136.  
  137. define Philosopher>>wakeup {
  138.     echo \%1 wakes up
  139.     _asg \%1.Philosopher.act thinking
  140.     (1)
  141. }
  142.  
  143. define Philosopher>>inspect {
  144.     echo \fsexp(\m(\%1.leftChopStick) 'inspect) and \fsexp(\m(\%1.rightChopStick) 'inspect)
  145.     (\%1)
  146. }
  147.  
  148. class Process
  149.  
  150. define Process>>run {
  151.     while true {
  152.         local \&w[] \%n
  153.         asg \%n \fsplit(\m(\%1.Process.Queue),&w,|)
  154.         if = 0 \%n break
  155.         \%1 remove: \&w[1]
  156.         (if (\&w[1] 'act) (\%1 'add: \&w[1]))
  157.     }
  158. }
  159.  
  160. define Process>>add: {
  161.     _asg \%1.Process.Queue \m(\%1.Process.Queue)\%2|
  162.     (\%1)
  163. }
  164.  
  165. define Process>>remove: {
  166.     _asg \%1.Process.Queue \freplace(\m(\%1.Process.Queue),|\%2|,|)
  167.     (\%1)
  168. }
  169.  
  170. define Process>>inspect {
  171.     echo \m(\%1.Process.Queue)
  172.     (\%1)
  173. }
  174.  
  175. define Process::new:number: {
  176. # \%2   Number of Philosophers and ChopSticks
  177.     _asg \%1.Process.Queue |
  178.     local \%i
  179.     for \%i 1 \%2 1 {
  180.         Semaphore new: chopstk_\%i
  181.     }
  182.     for \%i 1 \%2 1 {
  183.         (let \\\\%L \%i \\\\%R (+ (mod \%i \%2) 1))
  184.         Philosopher new: Philosopher_\%i leftChopStick: chopstk_\%L rightChopStick: chopstk_\%R place: \%i
  185.         \%1 add: Philosopher_\%i
  186.     }
  187.     (\%1)
  188. }
  189.  
  190. define ASKME {
  191.     local \%n
  192.     while true {
  193.     ask \%n { Number of Philosophers: }
  194.     if not def \%n continue
  195.     if not numeric \%n {
  196.         echo Not numeric - "\%n"
  197.         continue
  198.         }
  199.         break
  200.     }
  201.     return \%n
  202. }
  203.  
  204. (Process 'new: 'DiningPhilosophers 'number: (askme))
  205. DiningPhilosophers run
  206.