{- Dining Philosophers at Formal Hall Dinner; runs on 1-5 machines (modify config file). A classical problem of dining philosophers brought up here to show how easily distributed protocols can be expressed in Nomadic Pict. The algorithm is based on the idea that one of the philosophers holds a privilege to be a speaker who always gives away his fork/chopstick when asked. That is why, a distributed deadlock should not happen. In order to avoid starvation, the privilege is passed fairly to everyone. The philosophers communicate using location-independent messages. Thus, an example communication infrastructure is also included (it could be replaced by any other infrastructure algorithm). -} {- Assumptions: - deadlock and starvation must be avoided. - people are gentlemen nd once somebody started eating, no one can grab his fork until he has finished. -} import "Nstd/Map" program param : [Site Site Site Site Site] = ( val [seat_1 seat_2 seat_3 seat_4 seat_5] = param agent butler = ( {- Learn about a local communication etiquette at the college -} new dinner_served : ^[Agent Agent] new ready : ^Agent new appoint : ^[] new accepted : ^[] new ask : ^[] new pass_bottle : ^Int {- Declare imponderables of each philosopher -} new ticket : ^Site {- a ticket telling the location around the table -} new table : ^[] {- space to keep my own fork (or chopstick)-} new plate : ^[] {- space to keep a borrowed fork -} new speaker : ^Bool {- privilege to be the main speaker; the title is passed fairly to everyone; the speaker (as more talkative than others) is always kind to lend his fork when asked -} run ticket?*seat= ( agent philosopher = ( new recall : ^Bool {- to remember a fork request -} run recall!false {- make up your mind -} val fork = [] {- name objects on the table -} run table!fork {- locate your fork -} val I = (sys.agent_id) {- introduce himself/herself -} run dinner_served?*[left_fellow:Agent right_fellow:Agent] = {- before eating you must grab two forks/chopsticks -} ( print!(+$ I ": the dinner has started!") | ask@left_fellow![] {- ask left fellow to lend his fork -} | plate?_ = {- wait here until it arrives -} ( print!(+$ I ": thanks for lending me the fork") | table?_= {- grab fork or wait if it has been borrowed ... -} ( {- ... now got two forks -} {- . . . . . eating, eating . . . . . -} print!": I have got two forks now! I can have my meal." | table@left_fellow!fork {- return to left fellow his fork -} {- . .time for chatting, dessert and port (one fork should suffice) . .-} | print!": OK. I have finished and can return the fork." {- check if right fellow didn't keep asking to lend him a fork. -} | recall?asked = ( if asked then {- actually, he did . . -} ( plate@right_fellow!fork {- help him to finish before a gong! -} | print!": you asked me for a fork some time ago. Please, take it!") else table!fork {- if not then put it back on table -} | recall!false) {- clean memory -} {- go to another formal hall -} | dinner_served![left_fellow right_fellow]) ) {- keep listening to other fellows while eating and chatting -} | ask?*_= {- right fellow asked to lend him fork -} speaker?me = {- check if indulged in conversation -} if me then {- yes, indeed! -} ( appoint@right_fellow![] {- honour right fellow to be a speaker -} | accepted?_= {- wait for his commitment -} ( speaker!false | table?fork = {- wait til fork is free and give it to him -} ( print!": Take my fork as you wish" | plate@right_fellow!fork) | print!": I nominate you to be a speaker!") ) else {- I'm not a speaker so he has to wait for a fork . . -} (recall?_= recall!true {- .. but remember about his request -} | speaker!false | print!": Sorry! I can't lend you a fork now but I don't forget about the request." ) {- accept a nomination to be a speaker -} | appoint?*_= speaker?_ = ( speaker!true | accepted@left_fellow![] | print!": I've just been elected a speaker !") {- celebrate a habit of a bottle circulating around the table until it's been emptied -} | pass_bottle?*port= if (<> port 0) then ( print!": A bottle arrived. I'm passing it to the left!" | pass_bottle@left_fellow!(- port 1)) else print!": No wine." ) migrate to seat {- take a seat as written on the ticket -} {- confirm place and say hello to people around -} (ready@butler!philosopher | print!"Hello everybody! My name is . . ") ) in ()) {- settle people around the table . . -} (ticket!seat_1 | ready?fellow_1= (ticket!seat_2 | ready?fellow_2 = (ticket!seat_3 | ready?fellow_3 = (ticket!seat_4 | ready?fellow_4 = (ticket!seat_5 | ready?fellow_5 = ( {- suggest a speaker -} speaker@fellow_1!true | speaker@fellow_2!false | speaker@fellow_3!false | speaker@fellow_4!false | speaker@fellow_5!false {- fill in a bottle of port and put it in front of one fellow -} | pass_bottle@fellow_3!100 {- . . and gong to start a dinner (so as everyone can hear) -} | dinner_served@fellow_1![fellow_5 fellow_2] | dinner_served@fellow_2![fellow_1 fellow_3] | dinner_served@fellow_3![fellow_2 fellow_4] | dinner_served@fellow_4![fellow_3 fellow_5] | dinner_served@fellow_5![fellow_4 fellow_1])))))) ) in ()) {-********************************************************************* * Copyright (c) 1998-2001 Pawel T. Wojciechowski * * Forwarding Pointers. * *********************************************************************-} {Agent} = [Agent Site Agent] {Site} = [Site Agent] new register : ^Agent new migrating : ^Agent new migrated : ^[Agent [Site Agent]] new message : ^[#X [Agent Site Agent] !X X] new currentloc : ^[Site Agent] new lock : ^[] new ack : ^[] {toplevel P pa} Agent = ( val s1 = (sys.get_site 0) val s2 = (sys.get_site 1) val s3 = (sys.get_site 2) val s4 = (sys.get_site 3) val s5 = (sys.get_site 4) {- Spawn daemons on sites -} new daemondaemon : ^Site new nd : ^[Site Agent] agent A = ( daemondaemon?*S:Site= (agent D = ( {- Daemon -} def daemon [S:Site DS:Agent] = ( def eq (a:Agent b:Agent) : Bool = (sys.== #Agent a b) new lock : ^(Map Agent ^[Site Agent]) (lock!(map.make eq) | register?*B:Agent= {- register a new agent -} lock?m= switch (map.lookup m B) of ( Found> Bstate:^[Site Agent] -> Bstate?_= ( Bstate![S DS] | lock!m | ack![]) NotFound> _:[] -> (new Bstate : ^[Site Agent] ( Bstate![S DS] | lock!(map.add m B Bstate) | ack![]))) | migrating?*B:Agent= {- set up a lock -} lock?m= switch (map.lookup m B) of ( Found> Bstate:^[Site Agent] -> Bstate?_= ( lock!m | ack![]) NotFound> _:[] -> ()) | migrated?*[B:Agent [U:Site DU:Agent]]= {- release the lock -} lock?m= switch (map.lookup m B) of ( Found> Bstate:^[Site Agent] -> ( lock!m | Bstate![U DU] | ack![]) NotFound> _:[] -> ()) | message?*[#X [B:Agent U:Site DU:Agent] c:!X v:X]= lock?m= switch (map.lookup m B) of ( Found> Bstate:^[Site Agent] -> ( lock!m | Bstate?[R DR]= iflocal c!v then Bstate![R DR] else ( message![#X [B U DU] c v] | Bstate![R DR])) NotFound> _:[] -> {- send to the recipient's home site -} ( lock!m | message![#X [B U DU] c v]) ))) {- End of Daemon -} migrate to S (daemon![S D] | print!"<> OK! Daemon installed." | nd![S D])) in ()) | daemondaemon!s1 | nd?s1= (daemondaemon!s2 | nd?s2= (daemondaemon!s3 | nd?s3= (daemondaemon!s4 | nd?s4= (daemondaemon!s5 | nd?s5= (val [S1 DS1] = s1 val a = [A S1 DS1] ( currentloc![S1 DS1] | register!A | ack?_= (val !pa = [s1 s2 s3 s4 s5] {P}A)) ))))) ) in ()) {- Create a new agent -} {agent b=P in Q}A = currentloc?[S DS]= ( agent B = ( val !b = [B S DS] ( currentloc![S DS] | register!B | ack?_= (ack![] | {P}B)) ) in val !b = [B S DS] ack?_= (currentloc![S DS] | {Q}A) ) {- Migrate to a site -} {migrate to u P} A = currentloc?[S DS]= ( val [U DU] = u {- check if not local, e.g. to prevent deadlock in daemon -} if (&& (sys.== #Agent DS DU) (sys.== #Site S U)) then ( currentloc![U DU] | {P}A) else ( migrating!A | ack?_= (migrate to U ( register!A | ack?_= ( migrated![A [U DU]] | ack?_= ( currentloc![U DU] | {P}A))))) ) {- Location-independent output to agent -} {c@b!v}A = currentloc?[S DS]= (val [B U DU] = b iflocal c!v then currentloc![S DS] else iflocal message![b c v] then currentloc![S DS] else currentloc![S DS]) {- Output to agent on specified site -} {c!v}A = ( val [B _ _] = b val [S _] = s iflocal c!v then () else (agent m = (migrate to S iflocal c!v then () else ()) in ()) ) {- Output to agent on current site -} {c!v}A = (val [B _ _] = b iflocal c!v then () else ()) {- Test & send -} {iflocal c!v then P else Q}A = (val [B _ _] = b iflocal c!v then {P}A else {Q}A)