home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
kermit.columbia.edu
/
kermit.columbia.edu.tar
/
kermit.columbia.edu
/
archives
/
ckermit.zip
/
dining-drinking-philosophers
< prev
next >
Wrap
Lisp/Scheme
|
2004-05-06
|
7KB
|
281 lines
# From: "Dat Nguyen"
# Subject: DiningAndDrinkingPhilosophers
# Date: Thu, 06 May 2004 10:43:20 -0400
#
# Besides the binary semaphore which flipflops to allow access to a resource
# one at a time, regular semaphore mediates multiple requests to a resource.
# This element can be realized in C-Kermit easily. I offer the Philosophers
# some bottles wine which are managed by a winepool object. The philosopher
# object sends the request to the winepool which assigns an availble bottle to
# the philosopher or puts him on a queue for the bottle with the least numbers
# of waiting philosophers for it. To create a fierce competition for the wine,
# only a few bottles are to serve all philosophers. The more philosophers
# there are, some more bottles are served.
#
# Since the original concept is solid, it can accomdate this extension
# smoothly.
#
# Please enjoy the modern version of the philosopher society: The
# DiningAndDrinkingPhilosophers attached here.
#
take class
define randnum {
# \%1 random seed
while true {
if {\fsexpr(> (let rd \frandom(\%1)) 0)} return \m(rd)
}
}
class Semaphore
define Semaphore::new: {
(setq \%1.Semaphore.stat -1)
_asg \%1.Semaphore.Queue |
(\%1)
}
define Semaphore>>acquire {
(++ \%1.Semaphore.stat)
if > \%1.Semaphore.stat 0 {
_asg \%1.Semaphore.Queue \m(\%1.Semaphore.Queue)\%2|
echo \%2 waits for \m(\%2.\%1.ChopStick)
} else {
echo \%2 grabs \m(\%2.\%1.ChopStick)
}
(! \%1.Semaphore.stat)
}
define Semaphore>>release {
(-- \%1.Semaphore.stat)
local \&w[]
if > \fsplit(\m(\%1.Semaphore.Queue),&w,|) 0 {
_asg \%1.Semaphore.Queue \freplace(\m(\%1.Semaphore.Queue),|\&w[1]|,|)
DiningPhilosophers add: \&w[1]
echo \&w[1] grabs \m(\&w[1].\%1.ChopStick)
}
(\%1)
}
define Semaphore>>inspect {
echo \%1 \m(\%1.Semaphore.stat)
echo \%1 \m(\%1.Semaphore.Queue)
}
class Bottle
define Bottle::new: {
(setq \%1.Bottle.stat -1)
_asg \%1.Bottle.Queue |
(\%1)
}
define Bottle>>val {
(\%1.Bottle.stat)
}
define Bottle>>acquire {
(++ \%1.Bottle.stat)
if > \%1.Bottle.stat 0 {
_asg \%1.Bottle.Queue \m(\%1.Bottle.Queue)\%2|
echo \%2 waits for bottle \%1
} else {
echo \%2 grabs bottle \%1
}
(! \%1.Bottle.stat)
}
define Bottle>>release {
(-- \%1.Bottle.stat)
echo \%2 returns \%1
local \&w[]
if > \fsplit(\m(\%1.Bottle.Queue),&w,|) 0 {
_asg \%1.Bottle.Queue \freplace(\m(\%1.Bottle.Queue),|\&w[1]|,|)
DiningPhilosophers add: \&w[1]
echo \&w[1] grabs Bottle \%1
}
(\%1)
}
class Philosopher
define Philosopher::new:leftChopStick:rightChopStick:place: {
# \%2 leftChopStick
# \%3 rightChopStick
# \%4 no. seat
if {\fsexpr(mod \%4 2)} { # odd
_asg \%1.firstChopStick \%2
_asg \%1.secondChopStick \%3
} else { # even
_asg \%1.firstChopStick \%3
_asg \%1.secondChopStick \%2
}
_asg \%1.\%2.ChopStick left ChopStick
_asg \%1.\%3.ChopStick right ChopStick
_asg \%1.Philosopher.act thinking
(setq \%1.Philosopher.timeRepeat (randnum 15))
(\%1)
}
define Philosopher>>act {
if {\fsexpr(> (-- \%1.Philosopher.timeRepeat) 0)} return 1
(setq \%1.Philosopher.timeRepeat (randnum 50))
(\%1 '\m(\%1.Philosopher.act))
}
define Philosopher>>thinking {
echo \%1 is thinking
_asg \%1.Philosopher.act getChopStick
(1) # line up in the process queue
}
define Philosopher>>getChopStick {
(AND (\%1 'getFirstChopStick) (\%1 'getSecondChopStick))
}
define Philosopher>>getFirstChopStick {
_asg \%1.Philosopher.act getSecondChopStick
(\m(\%1.firstChopStick) 'acquire \%1)
}
define Philosopher>>getSecondChopStick {
_asg \%1.Philosopher.act eat
(\m(\%1.secondChopStick) 'acquire \%1)
}
define Philosopher>>eat {
echo \%1 is eating
_asg \%1.Philosopher.act grabBottle
(1)
}
define Philosopher>>grabBottle {
_asg \%1.Philosopher.act drink
(WinePool 'grabBottle: '\%1)
}
define Philosopher>>drink {
echo \%1 is drinking
_asg \%1.Philosopher.act dropBottle
(1)
}
define Philosopher>>dropBottle {
_asg \%1.Philosopher.act release_ChopSticks
WinePool dropBottle: \%1
(1)
}
define Philosopher>>release_ChopSticks {
echo \%1 releases both Chopsticks
_asg \%1.Philosopher.act sleep
(\m(\%1.firstChopStick) 'release)
(\m(\%1.secondChopStick) 'release)
(1)
}
define Philosopher>>sleep {
echo \%1 is sleeping
_asg \%1.Philosopher.act wakeup
(1)
}
define Philosopher>>wakeup {
echo \%1 wakes up
_asg \%1.Philosopher.act thinking
(1)
}
define Philosopher>>inspect {
echo \fsexp(\m(\%1.leftChopStick) 'inspect) and \fsexp(\m(\%1.rightChopStick) 'inspect)
(\%1)
}
class winePoolMgr
define winePoolMgr::new:numberOfBottles: {
local \%i
_asg \%1.winePool.numberOfBottles \%2
for \%i 1 \%2 1 {
Bottle new: \%1.Bottle.\%i
_asg \%1.Bottle.\%i.has |
}
}
define winePoolMgr>>grabBottle: {
local \%i \%m \%k
(setq \\\\%m 9999999)
for \%i 1 \%1.winePool.numberOfBottles 1 {
(if (< (\%1.Bottle.\%i 'val) \%m)
(. (setq \\\\%k \%i) (setq \\\\%m (\%1.Bottle.\%i 'val))
)
)
}
_asg \%1.\%2.hasBottle \%k # Philosopher has this bottle
(\%1.Bottle.\%k 'acquire \%2)
}
define winePoolMgr>>dropBottle: {
(let \\\\%k \%1.\%2.hasBottle)
\%1.Bottle.\%k release \%2
}
class Process
define Process>>run {
while true {
local \&w[]
(if (\fsplit(\m(\%1.Process.Queue),&w,|)) (\%1 'remove: '\&w[1]))
(if (\&w[1] 'act) (\%1 'add: \&w[1]))
}
}
define Process>>add: {
_asg \%1.Process.Queue \m(\%1.Process.Queue)\%2|
(\%1)
}
define Process>>remove: {
_asg \%1.Process.Queue \freplace(\m(\%1.Process.Queue),|\%2|,|)
(\%1)
}
define Process>>inspect {
echo \m(\%1.Process.Queue)
(\%1)
}
define Process::new:number: {
# \%2 Number of Philosophers and ChopSticks
_asg \%1.Process.Queue |
local \%i \%n
for \%i 1 \%2 1 {
Semaphore new: chopstk_\%i
}
for \%i 1 \%2 1 {
(let \\\\%L \%i \\\\%R (+ (mod \%i \%2) 1))
Philosopher new: Philosopher_\%i leftChopStick: chopstk_\%L rightChopStick: chopstk_\%R place: \%i
\%1 add: Philosopher_\%i
}
(setq \\\\%n (floor (/ \%2 7)))
(if (== 0 \%n) (setq \\\\%n 1))
winePoolmgr new: winePool numberOfBottles: \%n
(\%1)
}
define ASKME {
local \%n
while true {
ask \%n { Number of Philosophers: }
if not def \%n continue
if not numeric \%n {
echo Not numeric - "\%n"
continue
}
break
}
if < \%n 2 {
echo One needs at least two chopsticks to eat rice. Sorry!
EXIT
}
return \%n
}
(Process 'new: 'DiningPhilosophers 'number: (askme))
DiningPhilosophers run