Den tyngste enkeltoppgaven på eksamen

Oppgave 5 er tråder, og den er verdt mellom 10 og 36 poeng — i 2024 var den alene mer enn en tredel av hele eksamen. Formuleringen er alltid: «Du skal skrive én trådklasse som heter X og én som heter Y. Begge skal implementere Runnable. Du skal også skrive en klasse Z som skal være en monitor.» Og i de nyere settene står det uttrykkelig: «bruk Condition og ReentrantLock; ikke bruk synchronized.» Dette er den delen studentene oftest ikke rekker, så øv på å skrive den raskt.

Trådklassen

class Leter implements Runnable {
    private final Tog tog;
    private final Monitor monitor;
    private final String prefiks;

    Leter(Tog tog, Monitor monitor, String prefiks) {
        this.tog = tog;
        this.monitor = monitor;
        this.prefiks = prefiks;
    }

    public void run() {
        for (Skinnegaende s : tog) {
            if (s.hentId().startsWith(prefiks)) monitor.leggTil(s);
        }
        monitor.ferdigLeting();
    }
}

Klassen implementerer Runnable og har én metode, run(), uten parametere og uten returverdi. All informasjon tråden trenger, må derfor komme inn gjennom konstruktøren. Selve tråden startes utenfra:

Thread t = new Thread(new Leter(tog, monitor, "LOK"));
t.start();     // ny tråd starter og kaller run()
t.join();      // vent til den er ferdig

Skriver du t.run() i stedet for t.start(), kjøres run() som et helt vanlig metodekall i den tråden du allerede er i — ingen ny tråd oppstår, og all parallellitet er borte. Det er den vanligste feilen på hele oppgaven. Alternativet class Leter extends Thread er også lovlig, men da brenner du opp den ene arven du har.

Hvorfor monitoren trengs

To tråder som skriver til den samme variabelen uten synkronisering, kan miste oppdateringer. teller++ er ikke én operasjon, men tre — les, legg til, skriv tilbake — og to tråder kan lese samme gamle verdi. Området der bare én tråd om gangen kan være, kalles den kritiske regionen. En monitor er en klasse der alle metodene beskytter den kritiske regionen med den samme låsen.

Monitormalen

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;

class Monitor {
    private final Lock laas = new ReentrantLock();
    private final Condition ikkeTom = laas.newCondition();

    private Skinnegaende forste;      // egen liste av funn
    private int aktiveLetere;

    Monitor(int antallLetere) { aktiveLetere = antallLetere; }

    void leggTil(Skinnegaende s) {
        laas.lock();
        try {
            s.neste = forste;
            forste = s;
            ikkeTom.signal();
        } finally {
            laas.unlock();
        }
    }

    void ferdigLeting() {
        laas.lock();
        try {
            aktiveLetere--;
            if (aktiveLetere == 0) ikkeTom.signalAll();
        } finally {
            laas.unlock();
        }
    }

    Skinnegaende hentNeste() throws InterruptedException {
        laas.lock();
        try {
            while (forste == null && aktiveLetere > 0) {
                ikkeTom.await();
            }
            if (forste == null) return null;      // alle er ferdige
            Skinnegaende ut = forste;
            forste = forste.neste;
            ut.neste = null;
            return ut;
        } finally {
            laas.unlock();
        }
    }
}

Dette er malen. Lær den utenat, og bytt bare ut innmaten. Fem ting sensor sjekker, ordrett fra sensorveiledningene: låsen og Condition-variabelen må være deklarert riktig; alle metodene må låses og låses opp; await() må stå i en while-løkke; signal() må finnes i de metodene som endrer tilstanden; og metoden må returnere null når jobben er ferdig.

Hvorfor while og ikke if

Dette spørsmålet kommer i en eller annen form hvert år. await() slipper låsen og legger tråden til å vente. Når den vekkes, må den ta låsen tilbake før den fortsetter — og i mellomtiden kan en annen tråd ha kommet inn og tømt beholderen igjen. Betingelsen som var sann i det øyeblikket signalet ble sendt, kan altså være usann igjen når tråden faktisk kjører videre. I tillegg kan tråder våkne uten at noen har signalisert (spuriøs oppvåkning). Derfor må betingelsen sjekkes på nytt etter oppvåkningen, og det er nøyaktig det while gjør. Med if går tråden rett videre og leser fra en tom beholder.

finally rundt unlock

Mønsteret laas.lock(); try { ... } finally { laas.unlock(); } er ikke pynt. Kastes et unntak inne i den kritiske regionen uten finally, blir låsen aldri sluppet, og hver eneste tråd som senere prøver å låse, blir stående for alltid. Merk også at lock() skal stå utenfor try: klarte den ikke å ta låsen, skal finally heller ikke slippe den.

Toveis synkronisering

V2024 5d ba om oppgraderingen fra «busy waiting» til ekte toveis synkronisering: flygelederen skulle slutte å spørre hvert minutt og i stedet vente på en egen betingelse som pilotene signaliserer. To parter som begge kan vente, krever to Condition-variabler på den samme låsen.

class Rullebane {
    private final Lock laas = new ReentrantLock();
    private final Condition ventendeFly = laas.newCondition();   // leder venter her
    private final Condition startTillatelse = laas.newCondition(); // piloter venter her
    private int antallVentende = 0;

    void sjekkAvganger() throws InterruptedException {
        laas.lock();
        try {
            while (antallVentende == 0) ventendeFly.await();
            antallVentende--;
            startTillatelse.signal();          // slipp ETT fly av gårde
        } finally {
            laas.unlock();
        }
    }

    void hentStartTillatelse() throws InterruptedException {
        laas.lock();
        try {
            antallVentende++;
            ventendeFly.signal();              // vekk flygelederen
            startTillatelse.await();           // vent på klarsignal
        } finally {
            laas.unlock();
        }
    }
}

Poenget er at hver Condition er sin egen ventekø. Hadde begge partene ventet på den samme, kunne signal() vekket feil part, og systemet kunne stoppe helt. Bruk signalAll() når du er usikker på hvem som venter, og signal() når det er likegyldig hvilken av flere like tråder som slipper til.

Vranglås

To tråder som holder hver sin lås og venter på hverandres, står låst for alltid. Standardkuren er at alle tråder tar låsene i samme rekkefølge. På IN1010-eksamen har oppgavene som regel bare én lås, så vranglås oppstår sjelden i praksis — men spørsmålet om hva vranglås er, og hvordan man unngår det, kan komme.

Å vente på at alle er ferdige

V2022 ba om en metode som starter alle trådene, venter til de er ferdige og skriver ut resultatet. To løsninger godtas:

Thread[] traader = new Thread[n];
for (int i = 0; i < n; i++) {
    traader[i] = new Thread(new Teller(hoteller[i], monitor));
    traader[i].start();
}
for (Thread t : traader) t.join();     // vent på hver enkelt
skrivUt(monitor.hentResultat());

Alternativet er en CountDownLatch som opprettes med antall tråder, telles ned med countDown() sist i run(), og ventes på med await(). Begge deler gir full uttelling. Merk at join() og await() kaster InterruptedException, som er checked — enten deklarerer du throws, eller så pakker du inn i try/catch.

Den eldre stilen

Før ReentrantLock brukte man synchronized-metoder med wait() og notifyAll(). Prinsippene er identiske: wait() slipper låsen og skal stå i en while-løkke, notifyAll() vekker alle ventende. Forskjellen er at hvert objekt bare har én ventekø, så toveis synkronisering blir tungvint. Kan du malen ovenfor, kan du oversette den ene veien om oppgaven skulle be om det — men de nyere settene ber uttrykkelig om ReentrantLock.

Studieguide: Tråder og synkronisering