Labo Computersystemen : Dining Philosophers. P. Valckenaers

Labo Computersystemen : Dining Philosophers

P. Valckenaers Academiejaar 2006-2007

Alderweireldt Alexander

4II ELO ICT

1 Het wereldmodel 1.1 The Dining Philosophers The dining philosopher problem ofwel het dinerende filosofen probleem bestaat uit het synchronisatieprobleem van een aantal hongerige filosofen. Beschouw een aantal filosofen die hun leven doorbrengen met eten en nadenken. Ze zitten rond een tafel met elk een bord, en twee vorken (aan elke zijde één vork). Deze vorken moeten ze delen met hun buren.Bij het nadenken is er geen interactie met de andere filosofen. Na enige tijd wordt een filosoof hongerig. Na het eten begint elke filosoof terug te denken. Om te kunnen eten moet een filosoof beide vorken vastnemen. Na de maaltijd moet de filosoof zijn twee vorken terug langs hem neerleggen. herhaal 1: doe private denkactiviteiten tot je honger krijgt; 2: wacht tot de linker vork vrij is en neem die; 3: wacht tot de rechter vork vrij is en neem die; 4: doe kritische eetactiviteiten; 5: leg beide vorken neer;

Afbeelding 1 Welke vervelende situatie kan zich in deze situatie voordoen? Stel dat alle filosofen een tijdje denken en opeens tegelijkertijd willen eten. Ze nemen allemaal tegelijkertijd hun linkervork. Dit lukt omdat alle vorken vrij waren. Dan proberen ze allemaal de rechtervork te grijpen. Dit kan natuurlijk niet omdat alle vorken nu bezet zijn. De filosofen zullen omkomen van de honger. Dit fenomeen of probleem wordt gedefinieerd als “deadlock”. Een oplossing voor dit probleem die ik heb geimplementeerd is: een filosoof mag pas een vork trachten te nemen indien er minder dan 4 andere filosofen proberen twee vorken te nemen. Dit kan praktisch zo georganiseerd worden: bij het dekken van de tafel met vijf borden en vijf vorken worden er ook vier servetten in het midden van de tafel gelegd. Dan gaan de filosofen aan tafel. Voordat een filosoof een vork mag nemen, moet hij eerst een servet nemen en die rond zijn hals binden. Dan neemt hij een linkervork en daarna een rechtervork, eet dan een tijdje, legt beide vorken terug neer en legt ook de servet terug in het midden van de tafel. Indien er geen servet meer vrij is, moet hij wachten tot iemand anders een servet terug neerlegt. De filosofen kunnen we vergelijken met agenten of een stel onafhankelijke processen. De vorken kunnen we vergelijken met resources of een aantal beperkte gemeenschappelijke faciliteiten. Een agent moet dus twee resources kunnen locken voor hij zijn opdracht kan uitvoeren.

2/27

1.2 Software beschrijving De zonet uitgelegde situatie heb ik gesimuleerd in java. De software is opgedeeld in enkele classes. Dit is vooral om de ontwikkeling van de code makkelijker en overzichtelijker te maken. De volgende twee afbeeldingen geven een overzicht van de ontwikkelde java classes, samen met pijlen die het onderling gebruik weergeven.

Afbeelding 3: Software-versie 1 Afbeelding 2: Software-versie 2 De eerste software versie simuleert de zetelende filosofen die na een zekere tijd in deadlock gaan (verhongeren). Versie twee van de code simuleert the dining philosophers tafel, waar de filosofen niet meer in deadlock gaan. De classe Chopstick.java. Deze classe representeert de chopsticks ofwel vorken op de tafel. Elke filosoof krijgt 2 chopsticks toegewezen, een linker en een rechter, die hij kan opnemen en terug kan neerleggen. In software komt dit overeen met de functie Take() en Drop() van chopstick. De functie Take() is allereerst synchronized zodat crutiale functie niet door twee (filosoof) threads tegelijk kan uitgevoerd worden. Deze functie heeft als return-type boolean, wat wil zeggen dat hij een false aan de oproeper teruggeeft als de chopstick reeds in bezit is door een andere thread. Hij returned true als de oproeper met succes de chopstick in bezit heeft kunnen nemen. Met de functie Drop() wordt de chopstick terug vrij gegeven en beschikbaar gesteld voor andere filosofen (threads). De classe Philosopher.java. Deze classe stelt de filosofen voor die aan de tafel zetelen. Deze classe is een uitbreiding op de classe Thread (net zoals Dinner.java) zodat deze classe als een thread kan uitegvoerd worden. Ofwel zodat deze classe parrallel en onafhankelijk van de andere processen kan lopen. Elke filosoof krijgt bij aanmaak twee chopsticks, een randomgenerator en een datacontroller ter beschikking. Ook krijgt een filosoof een zekere looptijd opgelegd. Als deze looptijd verstreken is, dient de filosoof te stoppen. Elke filosoof houd ook bij aanmaak een eigen ID-nummer bij. Een filosoof kan zich in een aantal toestanden bevinden. De handelingen van de filosoof hangen af van de toestand waarin hij zich bevindt. Een filosoof blijft een vast traject van


4II ELO ICT

toestanden doorlopen, nl. denken(1), chopsticks nemen(2,3), eten(4). Bij de tweede software versie komt daar nog de toestand, servet nemen(2) bij. De classe Data_controller.java

Afbeelding 5: Filosoof Software-versie 1 Afbeelding 4: Filosoof Software-versie 2 De wachttijden van de filosofen aan een bepaalde tafel, worden centraal bijgehouden in deze classe. Deze classe beheert de data van de filosofen van een bepaalde tafel en output deze data op aanvraag in de gewenste vorm in een logbestand. Deze classe is als het ware een observator van de tafel, die de tafel opvolgt en analyseert. De classe Napkins.java. Deze classe wordt in de tweede software versie bijgevoegd om te vermijden dat de filosofen uithongeren (in deadlock gaan). Aan een tafel worden er een bak met een aantal servetten ter beschikking gesteld. Een filosoof mag pas naar zijn chopsticks grijpen als hij in het bezit is van een servet. Deze classe bezit een interne teller. 4/27

Telkens een filosoof een seviet wil nemen met de functie get_napkin() wordt nagegaan als er nog servetten beschikbaar zijn (teller>0). Zoniet, wacht de filosoof en wordt hij terug wakker gemaakt als er terug een servet beschikbaar is. Is eer servet beschikbaar, krijgt een filosoof een servet en wordt de interne teller van deze classe met één verlaagd. Als een filosoof een servet neerlegt met de drop_napkin() wordt de interne teller met één verhoogd. Deze classe is een implementatie van het principe 'semaforen'. Beide functies zijn ook hier synchronized om de zelfde reden als bij chopsticks.java. De classe Dinner.java. Deze classe representeerd een tafel waarrond een opgelegd aantal filosofen zetelen, elke voorzien van een linker en een rechter chopstick. We onderscheiden twee delen, de classe aanmaak en de functie met de thread-uitvoer. Bij het aanmaken van een dinnerobject wordt een data_controller, een gevraagd aantal chopsticks, een outputfile en het gevraagde aantal filosofen aangemaakt. In het functie voor de threaduitvoer worden als eerste alle filosofen thread gestart. Na 15 secondje wordt er nagekeken of alle filosofen minstens één maal gegeten hebben. Zoniet, zijn de filosofen al reeds in deadlock (één maaltijd duurt in het ergste geval hoogstens 5 sec) en heeft het geen nut om verder te wachten tot het einde van de looptijd om de resultaten te printen. In dit geval worden meteen de resultaten verwerkt en in een bestand weggeschreven. Als blijkt dat de filosofen reeds gegeten hebben na de eerste 15 seconden wacht de dinner-thread nog eens extra de gegeven loopduur. De eerste 15 seconden dienen ook als een veiligheidsmarge zeker te zijn dat alle filosofen al hun huidige handelingen kunnen afwerken en de tafel te verlaten. Vervolgens worden alle filosofen geforceerd gestopt indien nodig. Indien ze nog niet gestopt waren, bevonden de filosofen zich in een deadlocksituatie. In dat geval wordt de bestandnaam van de logfile ook aangepast door achteraan “[deadlock]” toe te voegen. Dit is een visueel hulpmiddel om te zien of er al dan niet een tafel(s) in deadlock is gegaan. De classe Main.java. Deze bevat de main functie die het programma beschrijft. Er wordt een randomgenerator aangemaakt en vervolgens wordt er een verkozen aantal tafels aangemaakt met de verkozen parameters en hun thread . Deze parameters zijn, het aantal filosofen er aan een tafel moeten zetelen, de totale looptijd van een tafel (de duur dat de filosofen moeten zetelen aan de tafel). Ook wordt aan elke tafel dezelfde random-generator meegegeven die initieel werd aangemaakt, om zo de pseudo-random gegenereerde code op elke tafel onafhankelijk van elkaar te maken.


4II ELO ICT

2 Test-Campagne Bij de eerste software versie, ofwel de deadlock versie heb ik verscheidene parameters ingesteld en laten varieren om zo te zien wat dat met de verhongering van de filosofen deed . Het tweede deel van de test campagne bestaat eruit dat ik de parameters van een eerste software versie die redelijk fel met het “dining philosophers” probleem te kampen had overneem in de tweede software versie ofwel de deadlockvrije versie. Hier werd er vooral getest op de tijden dat een filosoof moet wachten eer hij kan eten. Ook hier is achteraf nog wat met wat parameters gevarieerd.

2.1 Deadlock versie Een filosoof kan zich in een aantal toestanden bevinden. De handelingen van de filosoof hangen af van de toestand waarin hij zich bevindt. Een filosoof blijft een vast traject van toestanden doorlopen, nl. denken(1), chopsticks nemen(2,3), eten(4). Tussen toestand 2 en 3 kan hij even naar de toestand wachten(0) gaan als hij op een chopstick wacht (zie figuur 4). De tijd dat een filosoof denkt (1) en eet (4) is een random getal tussen 200 en 1200 ms. De wachttijd in de toestand wacht(0) varieerd tussen 100 en 150 ms. Tussen toestand 3 en 4 is er geen wachttijd, de filosoof begint meteen te eten. De tijd dat een filosoof wacht om zijn tweede chopstick op te nemen, zullen we met de tests laten varieren. Het aantal filosofen en de tijdsduur kan ingesteld worden in de file Main.java. In de file Philosopher.java is het mogelijk om de tijden die aangeven hoe lang een filosoof in een bepaalde toestand verblijft, aan te passen.

2.1.1 Test 1 : Tijd tussen toestand 2 en 3 laten varieren Er werden 15 tafels gestart. Een run van 6 minuten. Aan elke tafel zetelen 5 filosofen. Tijd

# deadlocks

100 ms

0*

250 ms

3

500 ms

6

750 ms

13

random** 13 * Ik heb ook bij deze parameters een run van 5uur gedaan, uiteindelijk gaat elke tafel in deadlock (tussen de 486 en 494 maaltijden). ** random = getal tussen 200 en 1200 ms Besluit : Hoe groter de tijd tussen 2 en 3, hoe sneller deadlock optreed. 6/27

2.1.2 Test 2 : Aantal filosofen laten varieren Er werden 15 tafels gestart. Een run van 6 minuten. Tijd tussen toestand 2 en 3 is 500 ms. # filosofen # deadlocks 3

15

5

6

7* 4 * Ik heb niet meer als 7 filosofen genomen omdat anders de pc te zwaar werd belast en dat misschien de test kon beinvloeden. Bij 15 tafels met elk 7 filosofen had de cpu van de pc een gemiddelde belasting van 60%. (bluej gaf 225 lopende threads aan). Tijd tussen toestand 2 en 3 is 750 ms. # filosofen # deadlocks 3

15

5

13

7

12

Tijd tussen toestand 2 en 3 is random getal tussen 200 en 1200 ms. # filosofen # deadlocks 3

15

5

11

7

4

Besluit : Hoe minder filosofen aanwezig aan een tafel, hoe sneller deadlock optreed. De kans dat alle filosofen tegelijk de linker chopstick vasthebben en bijgevolg een deadlock veroorzaken, wordt kleiner, vermits het aantal filosofen groter is.

2.1.3 Boxplots Ik heb ook nog twee boxplotten gemaakt bij deze deadlockversie zodat we die later ook nog met de boxplotten van de niet-deadlockversie kunnen vergelijken. De volgende parameters werden gebruikt hiervoor : 15 tafels, 5 filosofen, 500ms tussen toestand 2 en 3, run van 10min. Boxplot 1 = Wachttijden van elke filosoof van alle tafels. (950 maaltijden/filosoof) Boxplot 2 = Wachttijden van alle filosofen over alle tafels.(4750 maaltijden)


4II ELO ICT

Afbeelding 6: Boxplot 1

Afbeelding 7: Boxplot 2

De absolute minimum waarde dat een filosoof moet wachten is 500 ms. Dit is namelijk de minimum vaste tijd tussen het nemen van de rechterchopstick en na de linkerchopstick De meeste waarden liggen tussen de 2000 en de 2800 ms. De gemiddelde wachttijd ligt net onder de 2500 ms. Het minimum van 500 ms is eerder een uitzondering. Het maximum dat een filosoof moet wachten om te kunnen eten ligt ongeveer op 4500 ms. Dit is eerder zelden.

2.2 Deadlockvrije versie In deze tweede software versie zijn alle toestanden hetzelfde gebleven als in de eerste om zo geen appelen met peren te gaan vergelijken. Er is tussen de toestand denken en de toestand om de linker chopstick te grijpen enkel een toestand bijgekomen om de deadlock te voorkomen, namelijk bemachtig een servet. Dit weerspiegeld het oplossen van het filosofen probleem door middel van semaforen. Uit uitgebreide testen (6uur run) blijkt dat de filosofen blijven eten en niet meer in deadlock gaan.

8/27

2.2.1 Test 1 : Uitgebreide analyse van de situatie met deadlockpreventie De volgende parameters werden overgenomen uit versie één : Er worden telkens 15 tafels gestart, aan een tafel zetelen 5 filosofen, de tijd dat een filosoof wacht bij het grijpen van zijn linker chopstick om zijn rechterchopstick te nemen is 500 ms. We doen nu test-runs van 30 minuten om de filosofen zeker genoeg te laten eten om zo een correcte statistische weergave te verkrijgen van de situatie. Hieronder volgen een enkele boxplotten die wat meer inzicht moeten geven in de tijden dat de filosofen moeten wachten om te eten. Ik heb hier twee van de 15 tafels weergegeven, een boxplot van alle tafels samen en een boxplot van alle wachttijden samen. (achteraan bevinden zich de andere 13 tafels)

Afbeelding 8: Tafel 1

Afbeelding 10: Alle tafels

Afbeelding 9: Tafel 2

Afbeelding 11: Alle wachttijden

Zoals in deze boxplotten te zien is, is er een sterke overeenkomst met de karakteristieken van de wachttijden van software versie één en twee. Het toevoegen van de deadlockpreventie heeft niet veel invloed gehad op de wachttijden van de filosofen. Het gemiddelde ligt nogsteeds net onder 2500 ms.


4II ELO ICT

2.2.2 Test 2 : Variaties op het aantal servetten Zoals in de vorige boxplotten te zien was, was er nauwelijks een verandering van de wachttijden door het toevoegen van het anti-deadlock systeem met de servetten. In deze test heb ik het aantal beschikbare servetten laten varieren en gekeken wat dat met de wachttijden van de filosofen heeft gedaan. Bij figuur 12 werd het aantal beschikbare servetten ingesteld op 2 servetten minder dan het aantal aanwezige filosofen. Bij figuur 13 werd dit aangepast tot het aantal filosofen min 3. Het gaat hier telkens om 15 tafels die elke 15 minuten lopen met elk filosofen.

Afbeelding 12: # Servetten = #Filosofen - 2

Afbeelding 13: #Servetten = #filosofen - 3

Waarnemingen : Hier zien we duidelijk een sterke invloed van het aantal servetten dat ter beschikking wordt gesteld aan de tafel. Als we figuur 12 vergelijken met figuur 10 zien we dat het terugbrengen van 1 servet te weinig naar 2 servetten te weinig de wachttijd voor de filosofen drastisch vermindert. De gemiddelde wachttijd wordt met 1000 ms vermindert naar 1500 ms wat neerkomt om een reductie van 40%. Alhoewel de de meeste wachttijden verminderen (zie eerste en derde kwartiel) blijven de maximum wachttijden tot 4500 ms pieken. Als we figuur 13 met figuur 10 vergelijk is er nogaltijd een verbetering van 20% te merken, maar in vergelijking met figuur 12 zien we dat het verder verminder van het aantal servetten aan de tafel een negatief effect heeft op de gemiddelde wachttijd. We zien het gemiddelde terug met 33% stijgen. Ook hebben de maximum wachtentijden hogere uitschieters dan in de vorige 2 gevallen. De meest voorkomende wachttijden zijn wel minder gespreid dan voordien. Verklaring : Bij het ontbreken van 1 servet, is de kans nogaltijd groot dat een filosoof die een servet bemachtigd omringt wordt door filosofen die ook een servet in bezit hebben en dus zo de filosoof blokeren. Bij het ontbreken van 2 servetten verlaagd die kans en is de kans dat de filosoof direct kan starten met eten dus groter (500 ms). De filosofen kunnen vlotter eten en de gemiddelde wachttijden zakken dus. Bij het 10/27

weglaten van 3 servetten wordt de tijd weer verhoogd omdat het bemachtigen van een servet meer tijd in beslag neemt.

2.2.3 Test 3 : Variaties op het aantal zetelende filosofen Bij deze test gaan we onderzoeken welke invloed het aantal zetelende filosofen aan een tafel heeft op de wachttijden van de filosofen. De volgende resultaten zijn steeds gebaseerd testen op 15 tafels met elk een looptijd van 15 minuten. Achtereenvolgens werden 3, 5 en 7 filosofen per tafel getest.

Afbeelding 14: 3 filosofen

Afbeelding 16: 7 filsofen

Afbeelding 15: 5 filosofen


4II ELO ICT

Waarnemingen : We zien een sterk verband tussen het aantal aanwezige filosofen en de gemiddelde wachttijd die ze ondervinden om te kunnen eten. Hoe minder het aantal zetelende filosofen aan de tafel, hoe lager de wachttijden. We zien niet enkel een stijging in de gemiddelde wachttijden, maar ook een sterke stijging in de maximale wachttijden naar gelang het aantal filosofen stijgt aan tafel. Verklaring : Hoe kleiner het aantal filosofen aan de tafel, hoe hoger de kans dat als een je moet wachten en er een filosoof zijn bestek neerlegd, dat het bestek waar jij op wacte vrijkomt. Hoe hoger het aantal filosofen, hoe kleiner deze kans en hoe langer je dus blijft wachten.

2.2.4 Test 3 : Variaties in filosofen We gaan nu wat testen doen waarbij we het gedrag van enkele of alle filosofen veranderen. We gaan kijken welke invloed dat heeft op de filosoof/filosofen zelf en op de rest van de tafel. Specifiek is dit gerealiseerd door het verandere van de denktijd van een filosoof. De eettijden zijn hetzelfde gebleven. Ik heb telkens 1, 2 en dan alle filosofen aan een tafel een zwaardere 'weging-factor' meegegeven welke hun denktijd vergrootte. Hierop zijn 2 methodes. Methode 1 : wachttijd = ((weging-1)*1000)+ randomwachttijd Dit geeft bij 1, de normale randomtijd, en bij hogere waardes een vaste extra tijd bij de random.

Methode 2 : wachttijd = weging*randomwachttijd Deze methode vergroot het bereik waarover de randomtijd kan strijken.

Randomwachttijd, is de randomdenktijd van elke filosoof, namelijk gelegen tussen 200 en 1200 ms.

2.2.4.1 Denktijd variatie 1 : Allereerst wordt 1 filosoof met een weging-factor 2 op zijn denktijd beinvloed. Vervolgens is dit toegepast op 2 filosofen.

Afbeelding 18: 1 filosoof denk langer dan de rest Afbeelding 17: 2 filosofen denken langer 12/27

Vanwege de goede resultaten op de wachttijden van de filosofen, is dit ook eens op alle filosofen toegepast met een wegings-factor 2 en 3.

Afbeelding 19: Alle filosofen factor 2

Afbeelding 20: Alle filosofen factor 3

Waarnemingen : Allereerst zien we bij figuur 17 en 18, dat het langer denken van een filosoof een positieve invloed heeft op de wachttijden van die filosoof. Naar de andere filosofen toe ook heel gering. We zien dat de gemiddelde wachttijd bij figuur 17 bijna 2000 ms bedraagt en in figuur 18 gemiddeld 2000 ms gehaalt wordt. Bij het toepassen van deze wegings-factor 2 op alle filosofen zien we dat de karakteristieken van de wachttijden voor alle filosofen verbeteren. De gemiddelde wachttijd wordt nu terug gebracht tot 1500 ms in vergelijking met de 2500 ms van de default settings. Wanneer we de wegings-factor nu verder opschroeven naar 3, zien we dat de gemiddelde wachttijd voor elke filosoof verder zakt tot 750 ms wat zeer laag is. Maar, de uitschieters zijn bij deze configuratie wel extreem groot. Met als meest extreme waarde 12500 ms. Dit wel een uitzondering maar zeker niet gewenst. Verklaring : Als een filosoof langer wacht, blijven zijn chopsticks (resources) ook lang beschikbaar voor de andere filosofen aan de tafel. Dit leidt tot een vlottere werking van het eten en wachten op de gewenste chopsticks. Bij het toepassen van wegings-factor>1 op alle filosofen, geeft dit een positieve invloed op de wachttijden om dat de kans dat een buur aan het denken is en dus zijn chopsticks vrij zijn, groter is.

2.2.4.2 Denktijd variatie 2 : Bij de tweede variatie van denktijd manipulatie wordt allereerst 1 filosoof met een wegingsfactor 2 beinvloed. Vervolgens worden op alle filosofen een wegingsfactor 2 en 3 toegepast.


4II ELO ICT

Afbeelding 21: 1 filosoof denkt langer als de rest

Afbeelding 22: alle filosofen factor 2

Afbeelding 23: alle filosofen factor 3

Waarnemingen : We zien dat het toevoegen van een wegings-factor 2 een verlaging geeft van de gemiddelde denktijd. Bij een factor 3 daarintegen zien we weer de wachttijden en het gemiddelde toenemen in vergelijking met factor 2. De gemiddelde wachttijd van ongeveer 2000 ms is nog steeds beter dan de default settings. Verklaring : We zien hier hetzelfde fenomeen voorkomen dan bij de vorige denktijd variatie. De effecten van de weging-factor zijn minder heftig als bij de vorige variatie. Dit komt omdat de denktijd nu enkel in spreiding vergroot wordt en niet door een vaste factor toe te voegen. Klein denktijden zijn dus nog steeds morgelijk waardoor sommige filosofen al weer sneller hun linkervork gaan vastnemen en er blokeringen optreden. Met langere wachttijden als gevolg.

14/27

3 Deadlock 3.1 Welke methode heb ik gebruik om het geheel deadlock vrij te maken. Om een deadlock situatie te voorkomen heb ik gekozen om maar een beperkt aantal filosofen gelijktijdig te laten een poging te eten uit te voeren. Hierdoor kan nooit de situatie voorkomen dat elke filosoof 1 chopstick vastheeft en zo zijn buur blokeerd. Dus kan ook nooit een deadlock optreden. Er zal altijd 1 filosoof zijn die welk kan eten omdat zijn buur uitgesloten is. Na de maaltijd komen er terug chopsticks vrij en kan weer een volgende filosoof verder met eten. Pracktisch heb ik dit gedaan door het principe van semaforen toe te passen. Iemand moet eerst een semafoor kunnen verlagen voor hij zijn kritische functie mag uitvoeren. In mijn code en gedachtengang aan de tafel zijn dat servetten (napkins). Er zijn maar een aantal servetten aanwezig aan tafel. Weiniger dan het aantal filosofen. Een filosoof mag pas beginnen met bestek vast te nemen als hij een servet heeft kunnen bemachtigen. Na zijn maaltijd legt een filosoof samen met zijn bestek ook de servet terug neer in het midden van de tafel, zodat die weer beschikbaar wordt voor de andere filosofen.

3.2 Welke methodes die het geheel deadlockfree maken, kan je gebruiken. In het kort nog even enkele andere mogelijkheden die toegepast kunnen worden om een deadlock-probleem op te lossen. - Als een filosoof zijn linker chopstick opneemt en hij kan daarna zijn rechter chopstick niet vastnemen, moet hij zijn linker chopstick ook terug neer leggen. Hierna moet hij even een random tijd wachten vooreer hij opnieuw een poging mag probere om zijn bestek vast te krijgen. - Aan elke tafel een opzichter plaatsen. Deze bezit al het bestek en weet ook welke bestek bij welke filosoof hoort. Als een filosoof wil eten, moet hij dat aan de opzichter melden. De opzichter zal dan beslissen om wanneer en aan wie hij het bestek verdeelt. Na het eten keert het bestek ook terug naar de opzichter. - Een systeem maken om deadlock te detecteren. Als je opmerkt dat de tafel in deadlock zit, 1 of meerdere filosofen een wachttijd opleggen. Zo krijgen andere filosofen weer de mogelijkheid om verder te eten. - Bankers algoritme : een filosoof kijkt of zijn 2 noodzakelijker resources vrij zijn. Zoja, zal het bestek vastnemen. Anders wacht hij gewoon en kijkt even later nogeens opnieuw als deze gelegenheid zich ondertussen wel al voordoet.


4II ELO ICT

4 Aanvulling Boxplotten

16/27


4II ELO ICT

18/27


4II ELO ICT

20/27

5 Source code 5.1 Main.java import java.util.*; import java.io.*; public class Main extends Thread { public static void main(String args[]) { Dinner table; Random random; random = new Random(); System.out.println("Starting Application : \n-------------------------"); for(int i=0;i<15;i++) { // 5 phils, 1800sec = 30min table = new Dinner(5,1800,random); table.start(); try{sleep(1000);}catch (Exception e) {System.out.println(e); e.printStackTrace();} } } }

5.2 Dinner.java import java.awt.*; import java.util.*; import java.io.*; public class Dinner extends Thread { static int dinnercount = 0; Chopstick chop[]; Philosopher phil[]; Data_controller dc; // houd alle data bij van elke phil van deze tafel Napkins napkins; FileOutputStream out; // declare a file output object PrintStream ps; // declare a print stream object String filename; int philcount; int runtime; // runtime for the phils in seconds Dinner(int fAantal, int rtime, Random random_gen) { dinnercount++; philcount = fAantal; runtime = rtime; phil = new Philosopher[philcount]; chop = new Chopstick[philcount]; napkins = new Napkins(philcount); if(dinnercount<10) this.filename = "output/run0"+dinnercount+".txt"; else this.filename = "output/run"+dinnercount+".txt"; try{ // try–catch -> file // Create a new file output stream for this specific dinner out = new FileOutputStream(filename);


4II ELO ICT

// Connect print stream to the output stream ps = new PrintStream(out); dc = new Data_controller(philcount,500,ps); ps.println ("Init table "+dinnercount+" :"); for(int i = 0; i sleep for(int i = 0; i
22/27

5.3 Philosopher.java import java.util.*; import java.io.*; import java.lang.*; public class Philosopher extends Thread { static int counter = 1; boolean terminated = false; // to terminate the thread boolean deadlock = false; // set true if thread went into deadlock private int id; // phil id Chopstick left_chopstick; // 2 chopstick elements Chopstick right_chopstick; Napkins napkins; // the napkins at the table Random rand; // shared random generator PrintStream p; // shared printstream to file Data_controller dc; // controller unit that keeps track of the data at the table int toestandswaarde; // case counter int eetcount = 0; // keeps track on amount of meals String waiteside; // helps the waite get back to the previous state long runtime; long begin_time; long time; long time2;

// time that the philosopher should eat // remembers the time the thread started // container to get currentms in

// create philos (runtime in seconds) Philosopher(Chopstick left, Chopstick right, Random random_gen, PrintStream print, int rtime, Data_controller datac, Napkins npk) { this.id = counter++; // his id this.left_chopstick = left; // his 2 chopsticks this.right_chopstick = right; this.rand = random_gen; // shared randomgenerator this.p = print; // printstream to file this.runtime = (rtime*1000); // calc and the runtime in millisec this.begin_time = System.currentTimeMillis(); this.toestandswaarde = 1; this.dc = datac; this.napkins = npk; } public int get_id() {return this.id; } public int get_eetcount() {return this.eetcount; } public boolean deadlock(){return this.deadlock;} public void stopThread () // roept phil zelf aan als hij gedaan heeft { terminated = true; time = System.currentTimeMillis() - begin_time; System.out.println("Philosopher "+this.id+" stops... ["+time+" ms]"); } public void terminate() // roept dinner aan om zeker te zijn dat de philosopher stopt { // indien Deadlock : current status uit printen if(terminated) // no need to print current status return; else { terminated = true; deadlock = true; System.out.println("Philosopher "+this.id+" terminated from deadlock..");


4II ELO ICT

this.p.println("Philosopher "+this.id+" : \r\n> Deadlock <\r\n"); if(waiteside.equals("l")) this.p.println("Wacht op linker Chopstick("+this.left_chopstick.getId()+")..\r\n"); else if (waiteside.equals("r")) { this.p.println("Heeft linker Chopstick("+this.left_chopstick.getId()+") vast.."); this.p.println("Wacht op rechter Chopstick("+this.right_chopstick.getId()+")..\r\n"); } } } // the philos thread public void run() { int k; // container for random number try // try -catch voor de sleep { while(!terminated) // run till thread is stopped { k = rand.nextInt(1000)+200; // tijd = min 100ms => tussen 200ms <-> 1200ms switch(this.toestandswaarde) { case 0: // de wacht toestand k = rand.nextInt(50)+100; // tijd = min 100ms => tussen 100 en 150ms this.sleep(k); if(waiteside.equals("l")) this.toestandswaarde = 3; else if (waiteside.equals("r")) this.toestandswaarde = 4; else // is enkel voor vorige 2 waardes geschreven System.out.println(" >> ERROR at toestand 0 <<"); break; case 1 : // de denk toestand System.out.println("Philosopher "+this.id+" starts thinking ...(sleep "+k+"ms)"); this.sleep(k); this.toestandswaarde = 2; // gedaan met denken, nu wachten tot we kunnen eten time = System.currentTimeMillis(); // meet tijd tot eten = wachttijd break; case 2 : // grab napkin napkins.get_napkin(); this.toestandswaarde = 3; break; case 3 : // grab links if(left_chopstick.take(this,"linker")==true) { System.out.println("Philosopher "+this.id+" got his left chopstick..."); this.toestandswaarde = 4; this.sleep(500); } else { this.waiteside = "l"; this.toestandswaarde = 0; }

24/27

break; case 4 : // grab rechts if(right_chopstick.take(this,"rechter")==true) { // gedaan met wachten, nu eten time2 = System.currentTimeMillis(); // meet tijd tot eten = wachttijd this.dc.submit_time(this.id,eetcount,(int)(time2-time)); eetcount++; System.out.println("Philosopher "+this.id+" got his right chopstick..."); System.out.println("Philosopher "+this.id+" starts to eat...(for the "+eetcount+" time)"); this.toestandswaarde = 5; } else { this.waiteside = "r"; this.toestandswaarde = 0; } break; case 5 : this.sleep(k); // eet left_chopstick.drop(this,this.p); // gedaan met eten, gooi napkin en chopsticks neer right_chopstick.drop(this,this.p); napkins.drop_napkin(); // kijk na of de looptijd al afgelopen is time = System.currentTimeMillis() - begin_time; if(time < runtime) this.toestandswaarde = 1; else stopThread (); break; } // end switch case } // end while } // end try catch catch (Exception e) {System.out.println(e); e.printStackTrace();} } // end thread run } // end phil class

5.4 Chopstick.java import java.util.*; import java.io.*; public class Chopstick extends Thread { private boolean occupied; private int id; private int philid; private String philside; Chopstick(int idnr) { this.occupied = false; this.id = idnr; } public synchronized boolean take(Philosopher phil,String side) { if(this.occupied == true)


4II ELO ICT

return false; else { this.occupied = true; this.philid = phil.get_id(); this.philside = side; return true; } } public void drop(Philosopher philp,PrintStream print) { this.occupied = false; this.philid = -1; this.philside = null; } public int getId(){ return this.id;} }

5.5 Napkins.java import java.util.*; import java.io.*; public class Napkins { private int getal; public Napkins(int philcount) { getal = philcount-1; } public synchronized void get_napkin() { while (getal == 0) { try { wait(); } //wachten tot iemand ons wakker maakt catch (InterruptedException e) {} } --getal; } public synchronized void drop_napkin() { ++getal; notify(); } }

26/27

5.6 Data_controller.java import java.util.*; import java.io.*; public class Data_controller { private PrintStream p; private int philcount; private int [][]data; private int []counter; public Data_controller(int fAantal, int size, PrintStream print) { // size, moet een waarde ingeven in 2dim array this.p = print; this.philcount = fAantal; data = new int[philcount][size]; counter = new int[philcount]; } public synchronized void submit_time(int philid,int eetcounter,int waite_time) { int id = philid%philcount; // phils per 5 : vb 21->25 if(id == 0) id = 5; id--; // 21 -> 1, 22 -> 2, ... 25 -> 0 (if 0 -> 5) this.data[id][eetcounter] = waite_time; this.counter[id]= eetcounter; } public void print_matlab_matrix() { int a = this.counter[0]; for(int i=1;i

Labo Computersystemen : Dining Philosophers. P. Valckenaers

Recommend Documents