home *** CD-ROM | disk | FTP | other *** search
/ Columbia Kermit / kermit.zip / ckscripts / dining-drinking-philosophers < prev    next >
Lisp/Scheme  |  2020-01-01  |  7KB  |  281 lines
  1. # From: "Dat Nguyen"
  2. # Subject: DiningAndDrinkingPhilosophers
  3. # Date: Thu, 06 May 2004 10:43:20 -0400
  4. #
  5. # Besides the binary semaphore which flipflops to allow access to a resource 
  6. # one at a time, regular semaphore mediates multiple requests to a resource. 
  7. # This element can be realized in C-Kermit easily. I offer the Philosophers 
  8. # some bottles wine which are managed by a winepool object. The philosopher 
  9. # object sends the request to the winepool which assigns an availble bottle to 
  10. # the philosopher or puts him on a queue for the bottle with the least numbers 
  11. # of waiting philosophers for it. To create a fierce competition for the wine, 
  12. # only a few bottles are to serve all philosophers. The more philosophers 
  13. # there are, some more bottles are served.
  14. # 
  15. # Since the original concept is solid, it can accomdate this extension 
  16. # smoothly.
  17. # 
  18. # Please enjoy the modern version of the philosopher society: The 
  19. # DiningAndDrinkingPhilosophers attached here.
  20. # 
  21. take class
  22.  
  23. define randnum {
  24. # \%1 random seed
  25.     while true {
  26.         if {\fsexpr(> (let rd \frandom(\%1)) 0)} return \m(rd)
  27.     }
  28. }
  29.  
  30. class Semaphore
  31.  
  32. define Semaphore::new: {
  33.     (setq \%1.Semaphore.stat -1)
  34.     _asg \%1.Semaphore.Queue |
  35.     (\%1)
  36. }
  37.  
  38. define Semaphore>>acquire {
  39.     (++ \%1.Semaphore.stat)
  40.     if > \%1.Semaphore.stat 0 {
  41.         _asg \%1.Semaphore.Queue \m(\%1.Semaphore.Queue)\%2|
  42.         echo \%2 waits for \m(\%2.\%1.ChopStick)
  43.     } else {
  44.         echo \%2 grabs \m(\%2.\%1.ChopStick)
  45.     }
  46.     (! \%1.Semaphore.stat)
  47. }
  48.  
  49. define Semaphore>>release {
  50.     (-- \%1.Semaphore.stat)
  51.     local \&w[] 
  52.     if > \fsplit(\m(\%1.Semaphore.Queue),&w,|) 0 {
  53.         _asg \%1.Semaphore.Queue \freplace(\m(\%1.Semaphore.Queue),|\&w[1]|,|)
  54.         DiningPhilosophers add: \&w[1]
  55.         echo \&w[1] grabs \m(\&w[1].\%1.ChopStick)
  56.     }
  57.     (\%1)
  58. }
  59.  
  60. define Semaphore>>inspect {
  61.     echo \%1 \m(\%1.Semaphore.stat)
  62.     echo \%1 \m(\%1.Semaphore.Queue)
  63. }
  64.  
  65. class Bottle
  66. define Bottle::new: {
  67.     (setq \%1.Bottle.stat -1)
  68.     _asg \%1.Bottle.Queue |
  69.     (\%1)
  70. }
  71. define Bottle>>val {
  72.     (\%1.Bottle.stat)
  73. }
  74. define Bottle>>acquire {
  75.     (++ \%1.Bottle.stat)
  76.     if > \%1.Bottle.stat 0 {
  77.         _asg \%1.Bottle.Queue \m(\%1.Bottle.Queue)\%2|
  78.         echo \%2 waits for bottle \%1
  79.     } else {
  80.         echo \%2 grabs bottle \%1
  81.     }
  82.     (! \%1.Bottle.stat)
  83. }
  84. define Bottle>>release {
  85.     (-- \%1.Bottle.stat)
  86.     echo \%2 returns \%1
  87.     local \&w[] 
  88.     if > \fsplit(\m(\%1.Bottle.Queue),&w,|) 0 {
  89.         _asg \%1.Bottle.Queue \freplace(\m(\%1.Bottle.Queue),|\&w[1]|,|)
  90.         DiningPhilosophers add: \&w[1]
  91.         echo \&w[1] grabs Bottle \%1
  92.     }
  93.     (\%1)
  94. }
  95.  
  96. class Philosopher
  97.  
  98. define Philosopher::new:leftChopStick:rightChopStick:place: {
  99. # \%2 leftChopStick
  100. # \%3 rightChopStick
  101. # \%4 no. seat
  102.     if {\fsexpr(mod \%4 2)} {       # odd
  103.         _asg \%1.firstChopStick \%2
  104.         _asg \%1.secondChopStick \%3
  105.     } else {            # even
  106.         _asg \%1.firstChopStick \%3
  107.         _asg \%1.secondChopStick \%2
  108.     }
  109.     _asg \%1.\%2.ChopStick left ChopStick
  110.     _asg \%1.\%3.ChopStick right ChopStick
  111.     _asg \%1.Philosopher.act thinking
  112.     (setq \%1.Philosopher.timeRepeat (randnum 15))
  113.     (\%1)
  114. }
  115.  
  116. define Philosopher>>act {
  117.     if {\fsexpr(> (-- \%1.Philosopher.timeRepeat) 0)} return 1
  118.     (setq \%1.Philosopher.timeRepeat (randnum 50))
  119.     (\%1 '\m(\%1.Philosopher.act))
  120. }
  121.  
  122. define Philosopher>>thinking {
  123.     echo \%1 is thinking
  124.     _asg \%1.Philosopher.act getChopStick
  125.     (1)     # line up in the process queue
  126. }
  127.  
  128. define Philosopher>>getChopStick {
  129.     (AND (\%1 'getFirstChopStick) (\%1 'getSecondChopStick))
  130. }
  131.  
  132. define Philosopher>>getFirstChopStick {
  133.     _asg \%1.Philosopher.act getSecondChopStick
  134.     (\m(\%1.firstChopStick) 'acquire \%1)
  135. }
  136.  
  137. define Philosopher>>getSecondChopStick {
  138.     _asg \%1.Philosopher.act eat
  139.     (\m(\%1.secondChopStick) 'acquire \%1)
  140. }
  141.  
  142. define Philosopher>>eat {
  143.     echo \%1 is eating
  144.     _asg \%1.Philosopher.act grabBottle
  145.     (1)
  146. }
  147.  
  148. define Philosopher>>grabBottle {
  149.     _asg \%1.Philosopher.act drink
  150.     (WinePool 'grabBottle: '\%1)
  151. }
  152.  
  153. define Philosopher>>drink {
  154.     echo \%1 is drinking
  155.     _asg \%1.Philosopher.act dropBottle
  156.     (1)
  157. }
  158.  
  159. define Philosopher>>dropBottle {
  160.     _asg \%1.Philosopher.act release_ChopSticks
  161.     WinePool dropBottle: \%1
  162.     (1)
  163. }
  164.  
  165. define Philosopher>>release_ChopSticks {
  166.     echo \%1 releases both Chopsticks
  167.     _asg \%1.Philosopher.act sleep
  168.     (\m(\%1.firstChopStick) 'release)
  169.     (\m(\%1.secondChopStick) 'release)
  170.     (1)
  171. }
  172.  
  173. define Philosopher>>sleep {
  174.     echo \%1 is sleeping
  175.     _asg \%1.Philosopher.act wakeup
  176.     (1)
  177. }
  178.  
  179. define Philosopher>>wakeup {
  180.     echo \%1 wakes up
  181.     _asg \%1.Philosopher.act thinking
  182.     (1)
  183. }
  184.  
  185. define Philosopher>>inspect {
  186.     echo \fsexp(\m(\%1.leftChopStick) 'inspect) and \fsexp(\m(\%1.rightChopStick) 'inspect)
  187.     (\%1)
  188. }
  189.  
  190. class winePoolMgr
  191. define winePoolMgr::new:numberOfBottles: {
  192.     local \%i
  193.     _asg \%1.winePool.numberOfBottles \%2
  194.     for \%i 1 \%2 1 {
  195.         Bottle new: \%1.Bottle.\%i
  196.         _asg \%1.Bottle.\%i.has |
  197.     }
  198. }
  199.  
  200. define winePoolMgr>>grabBottle: {
  201.     local \%i \%m \%k
  202.     (setq \\\\%m 9999999)
  203.     for \%i 1 \%1.winePool.numberOfBottles 1 {
  204.         (if (< (\%1.Bottle.\%i 'val) \%m)
  205.             (. (setq \\\\%k \%i) (setq \\\\%m (\%1.Bottle.\%i 'val))
  206.             )
  207.         )
  208.     }
  209.     _asg \%1.\%2.hasBottle \%k      # Philosopher has this bottle
  210.     (\%1.Bottle.\%k 'acquire \%2)
  211. }
  212.  
  213. define winePoolMgr>>dropBottle: {
  214.     (let \\\\%k \%1.\%2.hasBottle)
  215.     \%1.Bottle.\%k release \%2
  216. }
  217.  
  218. class Process
  219.  
  220. define Process>>run {
  221.     while true {
  222.         local \&w[]
  223.         (if (\fsplit(\m(\%1.Process.Queue),&w,|)) (\%1 'remove: '\&w[1]))
  224.         (if (\&w[1] 'act) (\%1 'add: \&w[1]))
  225.     }
  226. }
  227.  
  228. define Process>>add: {
  229.     _asg \%1.Process.Queue \m(\%1.Process.Queue)\%2|
  230.     (\%1)
  231. }
  232.  
  233. define Process>>remove: {
  234.     _asg \%1.Process.Queue \freplace(\m(\%1.Process.Queue),|\%2|,|)
  235.     (\%1)
  236. }
  237.  
  238. define Process>>inspect {
  239.     echo \m(\%1.Process.Queue)
  240.     (\%1)
  241. }
  242.  
  243. define Process::new:number: {
  244. # \%2   Number of Philosophers and ChopSticks
  245.     _asg \%1.Process.Queue |
  246.     local \%i \%n
  247.     for \%i 1 \%2 1 {
  248.         Semaphore new: chopstk_\%i
  249.     }
  250.     for \%i 1 \%2 1 {
  251.         (let \\\\%L \%i \\\\%R (+ (mod \%i \%2) 1))
  252.         Philosopher new: Philosopher_\%i leftChopStick: chopstk_\%L rightChopStick: chopstk_\%R place: \%i
  253.         \%1 add: Philosopher_\%i
  254.     }
  255.     (setq \\\\%n (floor (/ \%2 7)))
  256.     (if (== 0 \%n) (setq \\\\%n 1))
  257.     winePoolmgr new: winePool numberOfBottles: \%n
  258.     (\%1)
  259. }
  260.  
  261. define ASKME {
  262.     local \%n
  263.     while true {
  264.         ask \%n { Number of Philosophers: }
  265.         if not def \%n continue
  266.         if not numeric \%n {
  267.             echo Not numeric - "\%n"
  268.             continue
  269.         }
  270.         break
  271.     }
  272.     if < \%n 2 {
  273.         echo One needs at least two chopsticks to eat rice. Sorry!
  274.         EXIT
  275.     }
  276.     return \%n
  277. }
  278.  
  279. (Process 'new: 'DiningPhilosophers 'number: (askme))
  280. DiningPhilosophers run
  281.