Opdracht 14 - Dining Philosophers problem

Doel

In deze opdracht veroorzaak je een deadlock in de programmeertaal Java. Je leert hoe je verschillende delen van je code gelijktijdig (concurrent) kan uitvoeren met behulp van Threads.

Hierdoor krijg je praktische inzichten in de moeilijkheden van concurrency en hoe deze ontstaan.

Na het voltooien van deze opdracht kan je:

• Code gelijktijdig uitvoeren in Java
• Het verschil tussen processen en resources praktisch uitleggen
• Uitleggen hoe een deadlock ontstaat
• Redeneren over hoe een deadlock te voorkomen of op te lossen

Merk op: je hoeft deze opgave niet in een virtuele machine uit te voeren, je hebt nl. reeds Java geïnstalleerd op je computer. Je kan de bestanden dus gewoon op je eigen computer bewerken en compileren.

Kadering opdracht

Binnen dit labo bootsen we het voorbeeld uit de theorie na: het Dining Philosophers-probleem. We hebben een tafel met filosofen die willen eten. Tussen elke twee filosofen ligt een vork, dus er zijn evenveel filosofen als vorken.

Een filosoof neemt de vork aan zijn linkerkant op (ervan uitgaande dat deze nog niet door een andere filosoof is opgenomen), voordat hij de vork aan zijn rechterkant oppakt. Wanneer een filosoof beide vorken vastheeft, kan hij eten. Deze opstelling is te zien in de volgende illustratie:

Het Dining Philosophers probleem ontstaat doordat de verschillende filosofen allemaal tegelijk de vork aan hun linkerkant opnemen (waardoor er geen vorken meer op de tafel liggen) en vervolgens wachten tot de persoon rechts van hen klaar is met eten en de vork neerlegt. Elke filosoof wacht op een andere, waardoor er niets meer gebeurt behalve wachten.

Een deadlock ontstaat dus wanneer verschillende processen resources vasthouden en de resources van de ander nodig hebben om verder te kunnen. In dit labo stellen de filosofen de processen voor (zij willen iets doen) en de vorken de resources (zij zijn nodig om het te kunnen doen).

Begrenzingen van dit labo

Als beperking voor dit laboratorium stellen we dat er altijd minstens 2 filosofen aan tafel moeten zitten. Daarnaast, om te voorkomen dat we de limieten van onze eigen apparaten overschrijden (en om timingproblemen te vermijden), stellen we een maximum van 10 filosofen aan de tafel in.

Implementatie - Setup

Fork

Om te beginnen maken we een record aan voor de vorken, met als enige attribuut "order". Op deze manier kunnen we vorken aanmaken waarbij we hun volgorde meegeven. Dit ziet er als volgt uit:

public record Fork(int order) {}

Philosopher

Daarnaast maken we een record aan voor de filosofen. Voor elke filosoof willen we bijhouden wat zijn "order" is, evenals welke vork links van hem ligt en welke rechts. Dit maakt het eenvoudiger om te simuleren dat een filosoof een vork opneemt. Dit ziet er als volgt uit:

public record Philosopher(int order, Fork leftFork, Fork rightFork) {}

DiningTable

Tot slot maken we een klasse DiningTable aan, die de volledige setup van filosofen en vorken aanmaakt. De bedoeling is om aan de constructor mee te geven hoeveel filosofen aan onze tafel zitten (houd rekening met de grenzen waarbinnen dit het beste ligt, maar probeer ook eens wat er misgaat wanneer je deze niet respecteert).

De dining table zal twee arrays bevatten: één met vorken en één met filosofen. In de constructor wordt eerst de lijst met vorken gevuld. We laten de order van vorken starten vanaf 0 omdat dit de programmalogica eenvoudiger maakt.

Daarna wordt de lijst met filosofen aangemaakt, waarbij we per filosoof de order (ook vanaf 0) en de vorken links en rechts van hem meegeven.

Dit zou er als volgt uit moeten zien:

public class DiningTable {
    private Fork[] forks;
    private Philosopher[] philosophers;

    public DiningTable(int amountOfPhilosophers) {
        forks = new Fork[amountOfPhilosophers];
        philosophers = new Philosopher[amountOfPhilosophers];

        for(int i = 0; i < amountOfPhilosophers; i++) {
            forks[i] = new Fork(i);
        }

        for(int i = 0; i < amountOfPhilosophers; i++) {
            Fork leftFork = forks[i];
            Fork rightFork = forks[(i+1) % amountOfPhilosophers];

            Philosopher philosopher = new Philosopher(i, leftFork, rightFork);

            philosophers[i] = philosopher;
        }
    }
}

Main

Om ons programma te kunnen starten, hebben we ook een main-methode nodig. Hierin maken we onze DiningTable aan en geven we het aantal filosofen mee.

public class Main {
    public static void main(String... args) {
        DiningTable diningTable = new DiningTable(5);
    }
}

Deadlock: Dine

De deadlock die we nu willen veroorzaken doet zich voor wanneer de filosofen willen eten. Hiervoor zullen we in de klasse DiningTable een methode dine aanmaken die ervoor zorgt dat onze filosofen tegelijkertijd proberen te eten.

Om dit gelijktijdig te laten gebeuren, moeten we gebruikmaken van Threads in Java. Dit doen we als volgt:

Wat threads exact zijn, zal je in hoofdstuk 7 leren.

public void dine() {
    for(int i = 0; i < philosophers.length; i++) {
        new Thread(philosophers[i]).start();
    }
}

Wanneer we deze code toevoegen, zal de Java-compiler een foutmelding geven, maar dat is volkomen normaal. Dit komt doordat de constructor van de klasse Thread een specifiek type nodig heeft, namelijk een Runnable. Daarom laten we onze Philosopher-klasse de Runnable-interface implementeren:

public record Philosopher(int order, Fork leftFork, Fork rightFork) implements Runnable {
    @Override
    public void run() {
        // TODO
    }
}

Hierbij moeten we natuurlijk nog implementeren wat het betekent voor een filosoof om te eten. We weten dat de linkervork van de ene filosoof altijd de rechtervork van een andere filosoof is en omgekeerd. Aangezien het in de realiteit niet mogelijk is dat beide filosofen dezelfde vork vasthouden, moeten we dit in ons programma ook voorkomen.

Java biedt hiervoor het keyword synchronized. Dit zorgt ervoor dat een bepaald object slechts door één thread tegelijkertijd gebruikt mag worden. In ons geval betekent dit dat we bij de filosoof het opnemen van de linkervork simuleren door synchronized(leftFork) {...} te gebruiken. Alles binnen de accolades stelt voor wat er gebeurt terwijl de huidige filosoof de linkervork vasthoudt.

Om onze deadlock te garanderen (er is een kleine vertraging bij het aanmaken van nieuwe threads), moeten we ervoor zorgen dat elke filosoof een seconde wacht na het opnemen van de linkervork, voordat hij de rechtervork opneemt. We moeten ook de gepaste logregels toevoegen voor het opnemen van de linkervork, bij het opnemen van de linkervork, voor het opnemen van de rechtervork en bij het opnemen van de rechtervork. Hierbij verwachten we dus te zien dat de rechtervork nooit wordt opgenomen. De voorbeeldimplementatie ziet er als volgt uit:

@Override
public void run() {
    System.out.printf("Philosopher %d wants to pick up left fork (fork %d).\n", order, leftFork.order());
    synchronized (leftFork) {
        System.out.printf("Philosopher %d picks up left fork (fork %d). He waits 1 second before picking up right fork (fork %d)\n", order, leftFork.order(), rightFork.order());
        try {
            Thread.sleep(1000);
        } catch(InterruptedException e) {
            e.printStackTrace();
        }

        System.out.printf("Philosopher %d wants to pick up right fork (fork %d).\n", order, rightFork.order());
        synchronized(rightFork) {
            System.out.printf("Philosopher %d successfully picks up right fork (fork %d).\n", order, rightFork.order());
        }
    }
}

Main

Vergeet niet om in de main-methode ook de dine-functie aan te roepen, anders gebeurt er niets:

public class Main {
    public static void main(String... args) {
       DiningTable diningTable = new DiningTable(5);

       diningTable.dine();
    }
}

Deadlock vaststellen

Een voorbeeld van hoe de logs eruit kunnen zien is als volgt:

Philosopher 0 wants to pick up left fork (fork 0).
Philosopher 0 picks up left fork (fork 0). He waits 1 second before picking up right fork (fork 1)
Philosopher 4 wants to pick up left fork (fork 4).
Philosopher 4 picks up left fork (fork 4). He waits 1 second before picking up right fork (fork 0)
Philosopher 2 wants to pick up left fork (fork 2).
Philosopher 2 picks up left fork (fork 2). He waits 1 second before picking up right fork (fork 3)
Philosopher 3 wants to pick up left fork (fork 3).
Philosopher 3 picks up left fork (fork 3). He waits 1 second before picking up right fork (fork 4)
Philosopher 1 wants to pick up left fork (fork 1).
Philosopher 1 picks up left fork (fork 1). He waits 1 second before picking up right fork (fork 2)
Philosopher 3 wants to pick up right fork (fork 4).
Philosopher 4 wants to pick up right fork (fork 0).
Philosopher 2 wants to pick up right fork (fork 3).
Philosopher 1 wants to pick up right fork (fork 2).
Philosopher 0 wants to pick up right fork (fork 1).

Opmerking: deze volgorde kan (en zal waarschijnlijk) telkens anders zijn. Dit is een van de zaken die multi-threading en concurrency zo moeilijk maken. We zien hierbij ook dat, ongeacht hoelang we wachten, er nooit een filosoof een rechtervork zal opnemen.

Extra opdracht

Probeer eens of je dit programma kan aanpassen zodanig dat de deadlock opgevangen wordt.