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