home *** CD-ROM | disk | FTP | other *** search
- # 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
-