home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Columbia Kermit
/
kermit.zip
/
ckscripts
/
dining-philosophers-1
< prev
next >
Wrap
Lisp/Scheme
|
2020-01-01
|
6KB
|
221 lines
# From: Dat Thuc Nguyen
# Date: Sun, 02 May 2004 18:09:41 -0400
# Subject: The Art of Programming in C-Kermit
#
# From time to time I sent in C-Kermit scripts that solve some problems people
# also solved in other programming languages.
#
# Today I am sending in a program that's difficult since it requires
# the notions of semaphore, process, timer and concurrency.
#
# The "dinning philosophers" problem is stated in Operating System Concepts by
# Peterson and Silberschatz, 1985, pp. 347-348.
#
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 {
local s
(setq s (++ \%1.Semaphore.stat))
if > s 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)
}
(! s)
}
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 Philosopher
define Philosopher::new:leftChopStick:rightChopStick:number: {
# \%2 leftChopStick
# \%3 rightChopStick
(setq \%1.leftChopStick \%2)
(setq \%1.rightChopStick \%3)
(setq \%1.Philosopher.Number \%4)
_asg \%1.\%2.ChopStick left ChopStick
_asg \%1.\%3.ChopStick right ChopStick
_asg \%1.Philosopher.act Philosopher>>thinking
(setq \%1.Philosopher.timeRepeat (randnum 15))
(\%1)
}
define Philosopher>>act {
(-- \%1.Philosopher.timeRepeat)
if == \m(\%1.Philosopher.timeRepeat) 0 {
(setq \%1.Philosopher.timeRepeat (randnum 50))
return \fsexpr(\%1 '\m(\%1.Philosopher.act))
} else {
return 1 # line up in the process queue
}
}
define Philosopher>>thinking {
echo \%1 is thinking
_asg \%1.Philosopher.act Philosopher>>getFirstChopStick
(1) # line up in the process queue
}
define Philosopher>>getFirstChopStick {
local gotChopStick
if {\fsexpr(mod \%1.Philosopher.Number 2)} { # odd
(setq gotChopStick (\m(\%1.leftChopStick) 'acquire \%1))
if gotChopStick {
_asg \%1.Philosopher.act Philosopher>>eat
(setq gotChopStick (\m(\%1.rightChopStick) 'acquire \%1))
if gotChopStick {
return 1
} else {
return 0
}
}
} else { # even
(setq gotChopStick (\m(\%1.rightChopStick) 'acquire \%1))
if gotChopStick {
_asg \%1.Philosopher.act Philosopher>>eat
(setq gotChopStick (\m(\%1.leftChopStick) 'acquire \%1))
if gotChopStick {
return 1
} else {
return 0
}
}
}
_asg \%1.Philosopher.act Philosopher>>getSecondChopStick
return 0 # wait for semaphore
}
define Philosopher>>getSecondChopStick {
local gotChopStick
_asg \%1.Philosopher.act Philosopher>>eat
if {\fsexpr(mod \%1.Philosopher.Number 2)} { # odd
(setq gotChopStick (\m(\%1.rightChopStick) 'acquire \%1))
if gotChopStick {
return 1
} else {
return 0
}
} else { # even
(setq gotChopStick (\m(\%1.leftChopStick) 'acquire \%1))
if gotChopStick {
return 1
} else {
return 0
}
}
}
define Philosopher>>eat {
echo \%1 is eating
_asg \%1.Philosopher.act Philosopher>>release_ChopSticks
(1)
}
define Philosopher>>release_ChopSticks {
_asg \%1.Philosopher.act Philosopher>>sleep
(\m(\%1.leftChopStick) 'release)
(\m(\%1.rightChopStick) 'release)
(1)
}
define Philosopher>>sleep {
echo \%1 is sleeping
_asg \%1.Philosopher.act Philosopher>>wakeup
(1) #
}
define Philosopher>>wakeup {
echo \%1 wakes up
_asg \%1.Philosopher.act Philosopher>>thinking
(1)
}
define Philosopher>>inspect {
echo \fsexp(\m(\%1.leftChopStick) 'inspect) and \fsexp(\m(\%1.rightChopStick) 'inspect)
(\%1)
}
class Process
define Process::new: {
_asg \%1.Process.Queue |
(\%1)
}
define Process>>run {
while true {
local \&w[] \%n
asg \%n \fsplit(\m(\%1.Process.Queue),&w,|)
if = 0 \%n break
\%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)
}
# Create five ChopSticks:
Semaphore new: chopstk_1_2 # ChopStick between p1 and p2
Semaphore new: chopstk_2_3 # ChopStick between p2 and p3
Semaphore new: chopstk_3_4 # ChopStick between p3 and p4
Semaphore new: chopstk_4_5 # ChopStick between p4 and p5
Semaphore new: chopstk_5_1 # ChopStick between p5 and p1
# Create five Philosophers:
Philosopher new: Philosopher_1 leftChopStick: chopstk_5_1 rightChopStick: chopstk_1_2 number: 1
Philosopher new: Philosopher_2 leftChopStick: chopstk_1_2 rightChopStick: chopstk_2_3 number: 2
Philosopher new: Philosopher_3 leftChopStick: chopstk_2_3 rightChopStick: chopstk_3_4 number: 3
Philosopher new: Philosopher_4 leftChopStick: chopstk_3_4 rightChopStick: chopstk_4_5 number: 4
Philosopher new: Philosopher_5 leftChopStick: chopstk_4_5 rightChopStick: chopstk_5_1 number: 5
Process new: DiningPhilosophers
for \%i 1 5 1 {
DiningPhilosophers add: Philosopher_\%i
}
DiningPhilosophers run
# end