©2000, Flemming Koch Jensen
Alle rettigheder forbeholdt
Kritiske regioner

Opgaver

"Here be dragons"

- Gammelt kort

 

 

 

Samarbejde Tråde skal ligesom mennesker kunne samarbejde. Når vi i et program laver mere end den ene tråd vi altid starter ud med (main-tråden), skyldes det ønsket om at løse en opgave på en effektiv og overskuelig måde. Vi finder det naturligt at formulere visse løsninger i termer af tråde, da disse tråde bedst udtrykker vores forståelse af hvordan problemet kan løses.
  Ligesom mennesker kan have problemer med at samarbejde - kan tråde det også. Når vi laver et fler-trådet program skal vi forudse de problemer der kan opstå og håndtere dem.
  I dette kapitel skal vi se på problemer - samarbejdsproblemer, og hvordan vi kan løse dem.
 

 

1. Race conditions

  Når flere tråde deles om en fælles resource, kan der opstå problemer, idet trådene som udgangspunkt ikke tager hensyn til at andre bruger den samme resource.
   
  At flere tråde anvender den samme resource, uden hensyntagen til hinanden, behøver ikke nødvendigvis give problemer. På et kontor kan personalet deles om et ur der hænger på væggen. Når de har brug for at vide hvad klokken er, kan de blot se på uret. Der er ikke noget problem i at de deles om denne resource! Den objektorienterede læser vil måske straks bemærker, at de manglende problemer, i det fælles ur, skyldes at ingen af klienterne (personalet) ændrer objektets (urets) tilstand. I sådanne situationer kan der ikke opstå problemer - De kan ikke mærke at de deles om resourcen.
   
  I situationer hvor tråde ændrer tilstanden i en fælles resource, kan der derimod opstå problemer. På engelsk kalder man det "race conditions". Det er situationer hvor trådenes anvendelse af resourcen kan gå i smadder, idet resourcen fra hver enkelt tråds synspunkt begynder at opfører sig mærkeligt/mystisk. Fra en komponentbaseret synsvinkel kunne man sige, at resourcen ikke ser ud til at opfylde sine specifikationer - den virker ikke som aftalt.
  Forestil dig følgende surrealistiske undervisningssituation:
  To lærere deles om det samme auditorie; hvor de begge forsøger at gennemføre hver deres forelæsning - samtidig!
  Som man kan forestille sig, kan det give visse problemer for lærerne og deres (stakkels) studerende. Lad os nævne nogle i flæng:
 

- Lærerne støder ind i hinanden, når de går frem og tilbage foran tavlen

- Det de skriver på tavlen bliver ødelagt af hinandens skriverier

- De taler i munden på hinanden

  I alle tre race conditions, er der tale om en fælles resource: gulvet foran tavlen, tavlen og "æteren" (Med "æteren" menes der "tale-rummet"). Hvordan kan vi løse problemerne?
  Her tænker vi ikke på de pædagogiske problemer, der formodentlig kun kan løses ved at give lærerne hvert deres auditorie, eller planlægge deres forelæsninger så de ikke overlapper.
  Hvis de skal deles om resourcerne - hvad så? De kan undgå at støde ind i hinanden ved at holde et vågent øje med den andens bevægelser. Ligeledes kan de med øjenkontakt undgå de værste problemer med at afbryde hinanden. Med andre ord: Løsningen kan ligge i en eller anden form for kommunikation mellem klienterne.
  Inden vi bevæger os alt for langt i retning af at løse problemerne, vil vi se et eksempel i Java; hvor det går galt:
 
Konto.java
public class Konto {
  private int saldo;
  
  public Konto( int saldo ) {
    setSaldo( saldo );
  }
  
  public void setSaldo( int saldo ) {
    this.saldo = saldo;
    
    System.out.println( "Ny saldo: " + saldo );
  }
  
  public int getSaldo() {
    return saldo;
  }
}
  Konto-klassen er en ganske triviel heltals-wrapper, der udskriver den nye saldo hver gang den ændres.
   
  Dernæst har vi en Kasserer-klasse, der tilgår en Konto.
 
Kasserer.java
import java.util.*;

public class Kasserer extends Thread {
  private Konto konto;
  private String navn;

  private Random rnd;
  
  public Kasserer( String navn, Konto konto ) {
    this.navn = navn;
    this.konto = konto;

    rnd = new Random( (int) (Math.random() * 1000) );
  }
  
  public void run() {
    for ( int i=0; i<2; i++ ) {
      indsæt();
      Sleeper.sleep( 2 );
      
      hæv();
      Sleeper.sleep( 2 );
    }
  }
  
  private void indsæt() {
    int indskud = rnd.nextInt( 500 );
    System.out.println( this + " vil indsætte " + indskud + " kr." );
  
    int saldo = konto.getSaldo();
    System.out.println( this + " læser " + saldo + " kr." );

    Sleeper.sleepRandom( 2 );
  
    saldo += indskud;
    System.out.println( this + " skriver " + saldo + " kr." );
    konto.setSaldo( saldo );
  }
  
  private void hæv() {
    int træk = rnd.nextInt( 500 );
    System.out.println( this + " vil hæve " + træk + " kr." );
  
    int saldo = konto.getSaldo();
    System.out.println( this + " læser " + saldo + " kr." );

    Sleeper.sleepRandom( 2 );
  
    if ( saldo >= træk ) {
      saldo -= træk;
      System.out.println( this + " skriver " + saldo + " kr." );
      konto.setSaldo( saldo );
    } else
      System.out.println( this + " konstaterer at der ikke er penge nok" );
  }
  
  public String toString() {
    return "[Kasserer: " + navn + "]";
  }
}
  Da det interessante er de problemer der opstår i forbindelse med Kasserer'nes anvendes af en fælles Konto, er der i Kasserer'ens implementation placeret en række udskrifter, så vi kan følge udviklingen.
  Når vi kører en Kasserer, vil denne hæv, henholdsvis indsætte, på Konto'en to gange. Dette er normalt et tilstrækkeligt antal gange til at illustrere problemet.
  Man bemærker at vi har indsat en række pauser. Det har vi gjort for at øge hyppigheden af de problemer som vi vil studere i det følgende.
   
  Endelig har vi testanvendelsen, der instantierer to Kasserer'e, som tilgår den samme Konto:
 
Main.java
public class Main {

  public static void main( String[] argv ) {
    Konto konto = new Konto( 500 );
    
    Kasserer a = new Kasserer( "A", konto );
    Kasserer b = new Kasserer( "B", konto );
    
    a.start();
    b.start();
  }
}
Ny saldo: 500
[Kasserer: A] vil indsætte 366 kr.
[Kasserer: A] læser 500 kr.
[Kasserer: B] vil indsætte 280 kr.
[Kasserer: B] læser 500 kr.
[Kasserer: A] skriver 866 kr.
Ny saldo: 866
[Kasserer: B] skriver 780 kr.
Ny saldo: 780
[Kasserer: A] vil hæve 498 kr.
[Kasserer: A] læser 780 kr.
[Kasserer: B] vil hæve 259 kr.
[Kasserer: B] læser 780 kr.
[Kasserer: A] skriver 282 kr.
Ny saldo: 282
[Kasserer: A] vil indsætte 312 kr.
[Kasserer: A] læser 282 kr.
[Kasserer: A] skriver 594 kr.
Ny saldo: 594
[Kasserer: B] skriver 521 kr.
Ny saldo: 521
[Kasserer: B] vil indsætte 146 kr.
[Kasserer: B] læser 521 kr.
[Kasserer: A] vil hæve 180 kr.
[Kasserer: A] læser 521 kr.
[Kasserer: B] skriver 667 kr.
Ny saldo: 667
[Kasserer: A] skriver 341 kr.
Ny saldo: 341
[Kasserer: B] vil hæve 278 kr.
[Kasserer: B] læser 341 kr.
[Kasserer: B] skriver 63 kr.
Ny saldo: 63
  Det er ganske underholdende at følge udskriften, og se hvordan de to Kasserer'e modarbejder hinanden.
  Først aflæser både A og B kontoen, og konstaterer der er en saldo på 500,- kr. A indsætter 366,- kr. ved at lægge dem til de læste 500,- kr., hvorefter den skriver de 866,- kr. tilbage til kontoen. B, der er uvidende om denne ændring, indsætter selv 280,- kr. ved at lægge dem til de læste 500,- kr. (der nu er en forældet information) og skriver 780,- kr. tilbage til kontoen. De 366,- kr. som A indsatte er forsvundet!
  Dette er den situation som vi beskrev i starten af kapitlet: For klienten (kasseren), ser det ud som om resourcen (kontoen) opfører sig mærkeligt/mystisk.
  Man kan fortsætte med at gennemgå resten af udskriften, og følge hvordan der igen opstår lignende problemer. Dette overlades til læseren!
  Inden vi begynder vores rejse gennem diverse muligheder, for at løse race conditions - både i vores bankkonto-eksempel og generelt, vil vi definere præcist hvad vi forstår ved en race condition:
 

Definition: Race Condition & Kritisk Region

Hvis forekomsten af en logisk fejl i en del af et program afhænger af trådenes schedulering, er der en race condition i den pågældende del af programmet, og denne del betegnes som en kritisk region.

  Det er i definitionen undeforstået af den del af et programmet der tales om, er en minimeret del. Det vil derfor ikke være seriøst at betegne hele programmet som en kritisk region, såfremt der blot er et mindre sted i dette, hvor en race condition forekommer.
  Vi fik her defineret en kritisk region - det begreb, der har givet overskriften til dette kapitel. Som man ser giver det ikke meget mening at tale om race conditions uden at tale om kritiske regioner - de er to sider af det samme fænomen.
 

 

2. Dekker's algoritme

  Den første løsning vi skal se, kaldes Dekker's algoritme. Det gør den naturligvis fordi det var Dekker der fandt på den, men det bør bemærkes at det egentlig var Dijkstra, der fandt på at bruge den i forbindelse med kritiske regioner. [Jeg skal have fundet ud af hvad Dekker egentlig lavede den til, og hvor gammel den er]
  Dekker's algoritme beskytter en kritisk region som to tråde ønsker at anvende:
Dekker's algoritme
KritiskRegion.java
public class KritiskRegion {
  private int turn;
  private boolean interested[];
  
  public KritiskRegion() {
    turn = 0;
    interested = new boolean[2];
  }
  
  public void enter( int threadNo ) {
    interested[ threadNo ] = true;
    
    while ( interested[ other( threadNo ) ] ) {
      // den er i brug, så vi må vente
    
      if ( turn != threadNo )  {
        // det er heller ikke vores tur, så det må vi også vente på
        
        interested[ threadNo ] = false; // frigiv mens vi venter
        
        while ( turn != threadNo ) // vent på det bliver vores tur
          Sleeper.nap();

        interested[ threadNo ] = true; // tage den derefter igen
      }
      
      Sleeper.nap();
    }
  }
  
  public void exit( int threadNo ) {
    turn = other( threadNo ); // lad det være den andens tur
    
    interested[ threadNo ] = false; // vi bruger den ikke mere
  }
  
  private int other( int threadNo ) {
    return 1 - threadNo;
  }
}
enter kan blokkerer Når en tråd ønsker at gå ind i den kritiske region kalder den enter-metoden, og når den er færdig med den kritiske region kalder den exit-metoden. Hvis tråden ikke kan få lov at gå ind i den kritiske region, vil enter-metoden vente indtil det er muligt. Med andre ord: enter-metoden returnerer ikke før vi har adgang til den kritiske region - den blokkerer.
Flag I forbindelse med denne algoritme, resten af kapitlet og opgaverne, vil vi anvende betegnelsen: flag, for visse boolske variable. I den sammenhæng betyder, det at sætte et flag, at man sætter den pågældende boolske variable til true. Når man sætter den boolske variabel til false, siger vi: at vi clearer flaget.
 

 

2.1 Analyse af Dekker's algoritme

  Lad os se hvordan algoritmen opfører sig i en række situationer:
 
Ingen af trådene er i den krtiske region, og kun én af dem ønsker at gå ind i den
Tråden der ønsker at gå ind i den kritiske region kalder enter med sit threadNo som parameter (threadNo er altid 0 eller 1). Den sætter sit flag i interested-array'et, for at markere sit ønske om at gå ind, og da den anden tråd ikke har sat sit tilsvarende flag returnerer metoden, og vi er inde!
 
Den ene tråd er i den kritiske region, og den anden ønsker også at gå ind
Tråden der allerede er inde har, da den gik ind, sat sit flag i interested-array'et. Når den anden kalder enter sætter den også sit flag, men kommer til at hænge i while-løkken indtil den første tråd forlader den kritiske region (se evt. exit-metoden).
I while-løkken checker den om det er dens tur ved at se på turn. Idéen med turn er at undgå udsultning af en tråd, ellers kunne tråden der gerne vil ind, være så uheldig at det altid blev den anden tråd, der slap ud af while-løkken først og kunne returnere fra enter. Hvis det ikke er vores tur går vi i en while-løkke, og venter på, at det bliver vores tur. Vi venter så at sige på, at det bliver vores tur til at forlade den ydre while-løkke, når ellers den anden tråd bliver færdig med at bruge den kritiske region.
Lad os præcisere, hvad vi generelt mener med udsultning:

Definition: Udsultning

Hvis det er muligt, at en tråd kan vente uendelig lang tid på at få adgang til en kritisk region, er der risiko for udsultning. Og vi siger at der kan ske udsultning i forbindelse med den pågældende situation.

Bemærk at vi sletter vores flag mens vi venter på at det bliver vores tur. Hvis vi ikke gjorde det kunne der opstår en såkaldt deadlock. Det ville ske hvis den tråd der gerne vil ind, men endnu ikke kan komme det, står i den indre while-løkke, med sit flag sat. Og den anden tråd i løbet af sin time slice, når at forlade den kritiske region, og kalde enter igen, og når at sætte sit flag. Så vil begge tråde blive fanget i while-løkken, og ingen af dem kan komme ud!
Lad os præcisere, hvad vi generelt forstår ved en deadlock:

Definition: Deadlock

Den situation, hvor to tråde begge venter på, at den anden tråd udfører en handling, mens de gensidigt forhindrer hinanden i at udføre de pågældende handlinger, betegnes som en deadlock. En deadlock kan også opstå i kombinationer med mere end to tråde.

De handlinger, der refereres til i definitionen, kan typisk være: at forlade en kritisk region, eller: at ændre tilstanden i et objekt.
 
Ingen af trådene er i den kritiske region, men de ønsker begge at gå ind
Trådene kalder begge enter - de sætter begge deres flag i interested-array'et - de går begge ind i den ydre while-løkken fordi den anden har sat sit flag - den ene vil udføre if-sætningen, fordi det ikke er dens tur, mens den anden ikke vil gøre det.

Den der udfører if-sætningen clearer sit flag, mens den venter på det bliver dens tur i den indre while-løkke. Den anden slipper ud af den ydre while-løkke, fordi den konkurrerende tråd har cleared sit flag, mens den venter. Med andre ord: det er turn der sikrer, at den ene tråd slipper ind i den kritiske region, mens den anden må vente.

 

 

2.2 Bankkonto-eksemplet

  Lad os se hvordan klassen KritiskRegion, og dermed Dekker's algoritme, kan anvendes i vores bankkonto-eksempel.
  Den instans af KritiskRegion der vedrører en given konto, aggregeres naturligt nok Konto-klassen:
 
Konto.java
public class Konto {
  private int saldo;
  
  private KritiskRegion kritiskRegion;
  
  public Konto( int saldo ) {
    setSaldo( saldo );
    
    kritiskRegion = new KritiskRegion();
  }
  
  public KritiskRegion getKritiskRegion() {
    return kritiskRegion;
  }
  
  public void setSaldo( int saldo ) {
    this.saldo = saldo;
    
    System.out.println( "Ny saldo: " + saldo );
  }
  
  public int getSaldo() {
    return saldo;
  }
}
  Med getKritiskRegion-metoden kan tråde, der ønsker at anvende kontoens metoder får adgang til det objekt, som styrer adgangen til disse.
  Det er vores Kasserer-klasse der ønsker en sådan adgang:
 
Kasserer.java
import java.util.*;

public class Kasserer extends Thread {
  private Konto konto;
  private String navn;
  
  private int threadNo;
  
  private Random rnd;
  
  public Kasserer( String navn, Konto konto, int threadNo ) {
    this.navn = navn;
    this.konto = konto;
    
    this.threadNo = threadNo;

    rnd = new Random( (int) (Math.random() * 1000) );
  }
  
  public void run() {
    for ( int i=0; i<2; i++ ) {
      indsæt();
      Sleeper.sleep( 2 );
      
      hæv();
      Sleeper.sleep( 2 );
    }
  }
  
  private void indsæt() {
    int indskud = rnd.nextInt( 500 );
    System.out.println( this + " vil indsætte " + indskud + " kr." );
    
    konto.getKritiskRegion().enter( threadNo );
    
    int saldo = konto.getSaldo();
    System.out.println( this + " læser " + saldo + " kr." );

    Sleeper.sleepRandom( 2 );
  
    saldo += indskud;
    System.out.println( this + " skriver " + saldo + " kr." );
    konto.setSaldo( saldo );
    
    konto.getKritiskRegion().exit( threadNo );
  }
  
  private void hæv() {
    int træk = rnd.nextInt( 500 );
    System.out.println( this + " vil hæve " + træk + " kr." );
    
    konto.getKritiskRegion().enter( threadNo );
    
    int saldo = konto.getSaldo();
    System.out.println( this + " læser " + saldo + " kr." );

    Sleeper.sleepRandom( 2 );
  
    if ( saldo >= træk ) {
      saldo -= træk;
      System.out.println( this + " skriver " + saldo + " kr." );
      konto.setSaldo( saldo );
    } else
      System.out.println( this + " konstaterer at der ikke er penge nok" );
  
    konto.getKritiskRegion().exit( threadNo );
  }
  
  public String toString() {
    return "[Kasserer: " + navn + "]";
  }
}
  Bemærk at vi her udstyrer instanser af Kasserer-klassen med et id, da det er en forudsætning for Dekker's algoritme, og dermed for at kunne få adgang til den kritiske region (kontoen)
  Vi har placeret enter- og exit-kald omkring vores anvendelse af kontoen. Bemærk at disse placeres udenom transaktionerne, da vi vil have eksklusiv adgang til kontoen, mens vi udfører hele transaktionen: hæv eller indsæt.
  Lad os endelig se testanvendelsen:
 
Main.java
public class Main {

  public static void main( String[] argv ) {
    Konto konto = new Konto( 500 );
    
    Kasserer a = new Kasserer( "A", konto, 0 );
    Kasserer b = new Kasserer( "B", konto, 1 );
    
    a.start();
    b.start();
  }
}
Ny saldo: 500
[Kasserer: A] vil indsætte 436 kr.
[Kasserer: A] læser 500 kr.
[Kasserer: B] vil indsætte 472 kr.
[Kasserer: A] skriver 936 kr.
Ny saldo: 936
[Kasserer: B] læser 936 kr.
[Kasserer: B] skriver 1408 kr.
Ny saldo: 1408
[Kasserer: A] vil hæve 328 kr.
[Kasserer: A] læser 1408 kr.
[Kasserer: B] vil hæve 369 kr.
[Kasserer: A] skriver 1080 kr.
Ny saldo: 1080
[Kasserer: B] læser 1080 kr.
[Kasserer: B] skriver 711 kr.
Ny saldo: 711
[Kasserer: A] vil indsætte 487 kr.
[Kasserer: A] læser 711 kr.
[Kasserer: A] skriver 1198 kr.
Ny saldo: 1198
[Kasserer: B] vil indsætte 239 kr.
[Kasserer: B] læser 1198 kr.
[Kasserer: B] skriver 1437 kr.
Ny saldo: 1437
[Kasserer: A] vil hæve 204 kr.
[Kasserer: A] læser 1437 kr.
[Kasserer: A] skriver 1233 kr.
Ny saldo: 1233
[Kasserer: B] vil hæve 93 kr.
[Kasserer: B] læser 1233 kr.
[Kasserer: B] skriver 1140 kr.
Ny saldo: 1140
  En minutiøs gennemgang af outputet ovenfor vil vise, at der nu ikke længere opstår fejl. En sådan gennemgang overlades til læseren.
 

 

2.3 Mutex

  Mutex betyder: Mutual exclusion, eller på dansk: gensidig udelukkelse. Det er den måde vi generelt søger at undgå race conditions. Vi vil opbygger en mekanisme, der sikrer at kun en tråd af gangen kan være i en kritisk region (vi skal senere under afsnittet om monitorer, slække lidt på kravet om, hvor mange tråde der samtidig må være i en kritisk region).
  At der kun kan være én tråd af gangen i en kritisk region, betyder at andre tråde, der ønsker at komme ind, må vente. Dekker's algoritme giver os mutex - den sikrer at højest én tråd ad gangen kan være i den kritiske region.
  I forbindelse med beskrivelsen af mutex, taler man ofte om en mutex lås (eng.: mutex lock):
 

Definition: Mutex lås

En mutex lås er en lås, hvorom det gælder, at det kun er muligt for én tråd at have den. Enhver anden tråd der ønsker at få låsen, må venter til den bliver frigivet, af den tråd der allerede måtte have den.

  Selvom der i f.eks. Dekker's algoritme ikke er nogen entitet, man konkret kan sætte fingeren på, og sige: "Dette er låsen!", taler man alligevel om en mutex lås. Den tråd, der har opnået adgang til den kritiske region, siges "at have låsen", mens de tråde der hænger i enter-metoden, og venter på adgang, venter på "at låsen bliver frigivet".
 

 

3. Peterson's algoritme

  Peterson's algoritme udemærker sig ved at være en del simplere en Dekker's, og den er i datalogisk sammenhæng overraskende ny - den er fra 1981.
  I Peterson's algoritme får enter- og exit-metoderne følgende implementation:
 
KritiskRegion.java
public class KritiskRegion {
  private int turn;
  private boolean[] interested;
  
  public KritiskRegion() {
    interested = new boolean[2];
  }
  
  public void enter( int threadNo ) {
    interested[ threadNo ] = true;
    
    turn = threadNo;
    
    while ( turn == threadNo && interested[ other( threadNo ) ] )
      Sleeper.nap();
  }
  
  public void exit( int threadNo ) {
    interested[ threadNo ] = false;
  }
  
  private int other( int threadNo ) {
    return 1 - threadNo;
  }
}
  Når man sammenligner med Dekker's algoritme, bemærker man først, at der nu kun er én while-løkke i enter-metoden. Begge enter-metoder starter med at sætte flaget i interested-array'et, men adskiller sig dernæst fra hinanden, idet deres anvendelse af turn-variablen er forskellig.
 

 

3.1 Analyse af Peterson's algoritme

  Lad os se hvordan Peterson's algoritme fungerer i de tre situationer vi studerende i forbindelse med Dekker's algoritme. For bedre at kunne sammenligne med den tilsvarende analyse for Dekker's algoritme, har vi valgt at farve den del af analyse, der er den samme, blå:
 
Ingen af trådene er i den krtiske region, og kun én af dem ønsker at gå ind i den
Tråden der ønsker at gå ind i den kritiske region kalder enter med sit threadNo som parameter (threadNo er altid 0 eller 1). Den sætter sit flag i interested-array'et, for at markere sit ønske om at gå ind, og da den anden tråd ikke har sat sit tilsvarende flag returnerer metoden, og vi er inde!

Man bemærker, at der i denne situation sker det samme som i Dekker's algoritme, fordi turn ikke spiller nogen rolle, når kun én tråd vil ind i den kritiske region.

 
Den ene tråd er i den kritiske region, og den anden ønsker også at gå ind
Tråden der allerede er inde har, da den gik ind, sat sit flag i interested-array'et. Når den anden kalder enter sætter den også sit flag, men kommer til at hænge i while-løkken indtil den første tråd forlader den kritiske region (se evt. exit-metoden).
Hvad sker der, hvis den anden tråd, efter at have slettet sit flag, med det samme ønsker at bruge den kritiske region igen, og dens time-slice fortsætter en rum tid endnu? Vil den kunne udsulte den tråd der står og venter?

Svaret er nej! Når den kalder enter igen, vil den sætte turn til sit threadNo og komme til at hænge i while-løkken, fordi den tråd, der står og venter har sat sit flag. Når den ventende tråd endelig får en time-slice, vil dens while-løkke terminere. Nu vil det ikke være fordi den anden tråd har cleared sit flag, for det har den jo nået at sætte igen, da den kaldte enter, men det vil være fordi turn ikke længere er threadNo for den ventende tråd. Det skyldes at tråden, der gerne vil ind igen, har ændret turn til sit threadNo, siden den ventende tråd begyndte at vente i while-løkken.

 
Ingen af trådene er i den kritiske region, men de ønsker begge at gå ind
Trådene kalder begge enter - de sætter begge deres flag i interested-array'et - de prøver begge samtidig at sætte turn til deres respektive threadNo, men dette kan naturligvis ikke lade sig gøre, så det vil være den tråd, der i forbindelse med en time-slice, sidst sætter turn's værdi som "får sin vilje".

I while-løkken kommer kun den ene tråd til at vente, mens den anden kan returnere fra enter-kaldet. Det skyldes, at det kun vil være for én af trådene, at turn kan være lig med dens threadNo. Man bemærker, at det vil være den tråd der "fik sin vilje" mht. turn's værdi, som kommer til at vente - man bliver altså belønnet for at "tabe".

 

 

4. Semaforer

  Med semaforer tager vi et spring tilbage i tiden, til 1965, da Dijkstra foreslog at bruge en simpel tæller til at opnå mutex.
Busy waiting Problemet med de to foregående løsninger, Dekker's og Peterson's algoritmer, er ikke at de ikke virker - for det gør de. Problemet er derimod at de baserer sig på aktiv venten (eng.: busy waiting). Med sleep-kaldene bliver CPU'en ikke stresset, men det er trods alt ikke så elegant.
  Skal man anvende semaforer kræver det umiddelbart, at de er en del af sproget. Alternativt kan man selv implementere dem vha, mekanismer der sikrer mutex; hvilket naturligvis er at gå over åen efter vand, da semaforer i givet er overflødige!
  Da Java ikke har semaforer må vi selv implementere dem - og vi gør det primært for at kunne studere anvendelsen af semaforer, snarere end for at bruge dem til at opnå mutex. Til at implementere semaforer anvender vi Java's mutex understøttelse, som vi dog først vil studere senere i kapitlet; hvorfor vi udskyde en forklaring af dele af implementation.
  Implementationen er som følger - idet vi ignorerer de med rødt markerede dele:
 
Semafor.java
public class Semafor {
  private int counter;
  
  public Semafor() {
    this( 1 );
  }
  
  public Semafor( int n ) {
    counter = n;
  }
  
  public synchronized void down() {
    while ( counter == 0 )
      try {
        wait();
      } catch ( InterruptedException e ) {
        // ignore
      }
      
    counter--;
  }
  
  public synchronized void up() {
    if ( counter == 0 )
      notify();

    counter++;
  }
}
  Idéen er, at en counter != 0 betyder, at der er adgang til den kritiske region, mens en counter på 0, betyder, at der allerede er en tråd i den kritiske region. Man kan se på counter'en som en tæller, der fortæller hvor mange ledige nøgler der er til den (aflåste) kritiske region. Er der nogen der har taget nøglen, må vi vente på, at dén der er i den kritiske region kommer ud og hænger den tilbage på plads igen.
  Når vi kalder down-metoden, vil vi blive hængende i while-løkken indtil der er en ledig nøgle, og når der er det, tæller vi counter ned med én, for at indikere at vi nu har taget en nøgle. Når vi er færdig med at bruge den kritiske region hænger vi nøglen tilbage ved at kalde up-metoden, der tæller counter op igen.
  Det er en meget simpel idé, men der er to ting man finder anledning til at bemærke. Uden Java's mutex-understøttelse ville der være race conditions "over det hele", og for det andet ville det være enklere at bruge en boolean i stedet for en tæller.
  Den første observation kendte vi i forvejen, men hvorfor bruges der en tæller når det ville være mere enkelt at bruge en boolean?
 

 

4.1 Producer-Consumer eksemplet

Klassisk For at forstå de muligheder det giver, at vi bruger en tæller i stedet for et flag (en boolean) skal vi studere et klassisk eksempel: Producer-Consumer.
Buffer I Producer-Consumer, er situationen den, at en tråd producerer produkter i en lind strøm, som en anden tråd konsumerer - også i en lind strøm. Denne udveksling af produkter sker ved en indekseret datastruktur - man vælger typisk at bruge et array. Denne datastruktur fungerer som en buffer mellem Produceren og Consumeren.
  Man vil ofte tænke på en kø, i forbindelse med den datastruktur, der anvendes til at udveksle produkterne. Vi vælger dog at bruge en stak, da implementationen er simplere, og vi derved får nemmere ved at fokusere på problematikken med samtidighed.
  Lad os se hvordan den naive udgave af Producer-Consumer implementeres - den udgave der ikke tager hensyn til race conditions.
  Først har vi stakken:
 
Stak.java
public class Stak {
  private int[] stak;
  private int pos;
  
  public Stak() {
    stak = new int[5];
    pos = 0;
  }
  
  public void push( int x ) {
    while ( pos == stak.length )
      Sleeper.nap();
    
    stak[pos] = x;
    pos++;
    
    System.out.println( this );
  }
  
  public int pop() {
    while ( pos == 0 )
      Sleeper.nap();
    
    pos--;
    return stak[pos];
  }
  
  public String toString() {
    StringBuffer sb = new StringBuffer();
    
    for ( int i=0; i<pos; i++ )
      sb.append( stak[i] + " " );
    
    return sb.toString();
  }
}
  Selve implementationen af stakken er traditionel, og vil ikke blive beskrevet yderligere her.
  Derimod vil vi bemærke de to while-løkker, man normalt ikke finder i implementationen af push og pop. Løkkernes formål er at vente! For push's vedkommende venter vi på, at der bliver plads i stakken, mens vi for pop's vedkommende venter på, at der er et element at pop'e.
  Man bemærker, at der er tale om aktiv ventet, idet while-løkkerne jævnligt kontrollerer om situationen har ændret sig.
  Dernæst har vi de to klienter til denne klasse: Producer og Consumer:
 
Producer.java
public class Producer extends Thread {
  private Stak stak;
  
  public Producer( Stak stak ) {
    this.stak = stak;
  }
  
  public void run() {
    for ( int i=0; i<10; i++ ) {
      stak.push( i );
      
      Sleeper.sleepRandom( 1 );
    }
  }
}
 
Consumer.java
public class Consumer extends Thread {
  private Stak stak;
  
  public Consumer( Stak stak ) {
    this.stak = stak;
  }
  
  public void run() {
    for ( int i=0; i<10; i++ ) {
      System.out.println( "[" + stak.pop() + "]" );
      
      Sleeper.sleepRandom( 2 );
    }
  }
}
  Disse er også ukomplicerede. Man bemærker, at vi anvender kald af randomSleep til at opnå en variation i antallet af elementer der ligger på stakken. Pausen i Consumer gøres længere end i Produceren, så stakken har en bedre chance for at løbe fuld.
  Endelig har vi en testanvendelse:
 
Main.java
public class Main {

  public static void main( String[] argv ) {
    Stak stak = new Stak();
    
    Producer producer = new Producer( stak );
    Consumer consumer = new Consumer( stak );
    
    producer.start();
    consumer.start();
  }
}
0
[0]
1 
1 2
1 2 3
[3]
1 2 4 
1 2 4 5 
[5]
1 2 4 6 
1 2 4 6 7
[7]
1 2 4 6 8
[8]
1 2 4 6 9
[9]
[6]
[4]
[2]
[1]
  Gennemgår man udskriften, vil man se at alt er som det skal være. Men der er et problem!
  Selvom der ikke viser sig nogen fejl i testanvendelsen, kan det i sjældne tilfælde gå galt. Betragt igen Stak-klassen. Hvad er det svage punkt i push- og pop-metoderne? Det er opdateringen af pos-variablen!
  Hvis f.eks. Producer er ved at push'e et tal på stakken og vores time slice udløber lige efter vi har sat stak[pos] til den nye værdi. Og Consumer dernæst kalder pop, vil den aflæse det element som i virkeligheden er den næstøverste, og det er gået galt!
  Som tidligere nævnt er en semafor en speciel velegnet løsning i dette eksempel. Vi skal dog bruge ialt tre semaforer, så specielt enkel er løsningen måske ikke ved første øjekast:
 
  Vi ser her de tre semaforer, samt Producer og Consumer's anvendelse af dem.
mutex En semafor, der kun kan antage værdierne 0 og 1, bruges til at beskytte den kritiske region, dvs. stakken. Før man anvender stakken, skal man derfor down'e mutex-semaforen, og efter afsluttet anvendelse up'e den igen.
empty Når Producer ønsker at placere et produkt i bufferen, down'er den empty-semaforen, da den derved vil reducere antallet af ledige pladser i bufferen med én. Er der plads, er dette muligt, ellers hænger den i down indtil Consumer up'er empty - når den tager et produkt ud af bufferen.
full På samme måde down'er Consumer full-semaforen før den tager et produkt ud af bufferen. Hvis der er et produkt i bufferen, er dette muligt, ellers hænger den i down indtil Producer up'er full - når den placerer et produkt i bufferen.
  Den sikre udgave af Stak-klassen bliver:
 
Stak.java
public class Stak {
  private int[] stak;
  private int pos;
  
  private Semafor empty, full, mutex;
  
  public Stak() {
    stak = new int[5];
    pos = 0;
    
    empty = new Semafor( stak.length );
    full  = new Semafor( 0 );
    mutex = new Semafor( 1 ); // adgang okay
  }
  
  public void push( int x ) {
    empty.down();
      mutex.down();
        stak[ pos++ ] = x;
        System.out.println( this );
      mutex.up();
    full.up();
  }
  
  public int pop() {
    full.down();
      mutex.down();
        int value = stak[ --pos ];
      mutex.up();
    empty.up();
    
    return value;
  }
  
  public String toString() {
    StringBuffer sb = new StringBuffer();
    
    for ( int i=0; i<pos; i++ )
      sb.append( stak[i] + " " );
    
    return sb.toString();
  }
}
  Vi vil undlade at gentage testanvendelsen, den er den samme.
  I de to metoder: push og pop, har vi gjort alle down-kaldene røde og alle up-kaldene blå.
Deadlock Det er karakteristisk, at mutex-semaforen anvendes lige omkring den kritiske region. Det skyldes at man kun ønsker at opnå mutex, når man ved, at man kan udføre hele operationen. F.eks. kræver push, at der er plads på stakken for at operationen kan gennemføres, og det ville derfor være uhensigtsmæssigt at forhindre consumeren i at gennemføre et pop, da det netop er det produceren i givet fald vil vente på! Mao. mutex-semaforen skal "stå inderst", ellers opstår der en deadlock hvis stakken løber fuld eller bliver tom.
Aktiv venten Man bemærker hvordan de to semaforer: empty og full, håndterer spørgsmålet om ledig plads, henholdsvis produkter i bufferen. På den måde undgår vi aktiv venten.
 

 

4.2 Binær semafor

  Vi har tidligere fremført den idé, at en semafor lige så vel kunne være bygget op omkring en boolean, men eksemplet overnfor har vist os, at man kan have nytte af, at en semafor rent faktisk bruger en tæller (semaforerne: empty og full). Det betyder dog ikke, at en semafor der kun anvender en boolean ikke har sin berettigelse. I eksemplet så vi nemlig også en semafor: mutex, der ikke udnyttede semaforens tæller-egenskab. En sådan semafor kaldes en binær semafor:
 

Definition: Binær Semafor

En semafor, hvis tæller kun kan antage værdierne 0 og 1, kaldes en binær semafor.

  Anvender man en semafor som simpel mutex lås, har man kun behov for en binær semafor.
 

 

5. Monitorer

En killer! Der er et problem med alle de løsninger vi hidtil har set. Ikke, at de ikke virker - for det gør de! Problemet er ikke teknisk men praktisk. Hvis man laver fejl i forbindelse med anvendelse af ovenstående løsninger, er det mere end almindelig svært at finde dem. Det skyldes at fejlene ikke vil være periodiske - der vil ikke være noget system i hvornår de opstår. Hvis fejlen samtidig kun opstår under sjældne sammenfald af tråde, der er ved at udføre bestemte ting, er det fuldkomne horror-scenarie etableret, og fejlsøgning er en killer!
Java har monitorer Det var i erkendelse af dette, at Hoare (1974) og Brinch Hansen1 (1975) fremkom med idéen om monitorer. Idéen med en monitor er i virkeligheden meget enkel, men det har knebet gevaldigt med programmeringssprog der tilbyder denne konstruktion. Java er faktisk det første sprog med en nævneværdig markedsandel, der har monitorer.
Lad maskinen gøre arbejdet Monitor-idéen bygger i al sin enkelthed på indkapsling. Når kritisker regioner typisk er kendetegnet ved at være mindre dele af et program, er det nærliggende at indkapsle dem, så kun en tråd kan komme ind af gangen. Det, der giver denne idé sin endelig styrker, er at det ene og alene er runtime systemets opgave at håndhæve denne restriktion - programmøren skal intet gør. De skal kun markere hvad der er den kritiske region. Denne løsning er helt i tråd med den udvikling vi altid tilstræber i vores forhold til computere - hvis vi har et problem, så lad dog maskinen løse det for os! Dette kræver vel at mærke, at vi kan finde ud af at få den til det! De fleste af de løsninger vi har set i dette kapitel, har drejet sig om at løse problemet uden at gøre det til en del af sproget. Vi må bare erkende, at det kan ikke gøres ordentlig uden sprogunderstøttelse.
  Følgende figur illustrerer idéen med en monitor:
 
  Ved monitorernes fremkomst i midten af 70'erne var objektorienteret programming på ingen måde slået igennem, og perspektivet i ovenstående figur, er derfor ikke objektorienteret - og måske alligevel!
  Vi ser programmet som en samling af variable og metoder (eller funktioner og procedurer). Blandt disse er der nogle metoder og et par variable, der er indsluttet i en monitor. Som nævnt betyder det, at højest en tråd kan være inde i monitoren af gangen.
  Ser man længe nok på figuren, kan man dog ikke undgå at blive slået af den tanke, at en monitor er en samling af variable og metoder, ligesom en klasse! Man kunne derfor lade monitor-egenskaben, være en særlig klasse-egenskab, når man designede et objektorienteret sprog med monitorer. Idéen er meget enkel, men viser sig dog at være lidt for firekantet. I Java vælger man derfor at lade det være en mindre del af en klasse, der får monitor-egenskaben. Det skyldes, at man kun ønsker, at det skal være den kritiske region, og ikke mere end højest nødvendigt, der placeres i monitoren. Ellers ville tråde skulle vente unødigt!
 

 

5.1 Monitorer i Java

  Som nævnt bruger Java monitorer til mutex. Det sker ved, at man for hver metode i en klasse specificerer om den skal tilhøre klassens monitor. Instansvariable kan ikke selvstændigt tilhøre klassens monitor, men man opnår mutex for disse, ved at lade de metoder, der tilgår de pågældende variable tilhører monitoren.
  Lad os se et eksempel:
 

public class A {
  ...
  
  public void metodeA() {
    ...
  }
  
  public synchronized void metodeB {
    ...
  }
  
  public void metodeC() {
    ...
  }
  
  public synchronized void metodeD {
    ...
  }
}

  Med det reserverede ord: synchronized angiver man, at de to metoder: metodeB og metodeD er i klassens monitor. Det betyder, at der ikke samtidig kan være to tråde, der er ved at udføre et kald, af en af de to metoder. De to metoder: metodeA og metodeC er ikke i monitoren og tråde kan kalde disse metoder, uden at skulle vente på hinanden.
  Billedet er altså:
 
 

 

5.1.1 Synkroniserede blokke

  Som vi allerede har berørt ovenfor, ønsker vi ikke, at det er mere end højest nødvendigt, der skal placeres i monitoren. Hvis vi placerer ting i monitoren, der ikke behøver mutex, vil der være tråde der spilder tiden på at vente på adgang til disse dele.
  Selvom vi kan specificere ned til metode-niveau, hvad der skal være i monitoren, vil der stadig være dele af programmet, der overflødigt er placeret i monitoren. Til at optimere dette yderligere har Java synkroniserede blokke.
  En synkroniseret blok, har følgende syntaktiske opbygning:
 

public class A {
  ...
  
  public void metodeA() {
    ...
	
    synchronized ( <reference til objekt> ) {

      // kritisk region

    }
	
    ...
  }

  ...
}

  En synkroniseret blok, er syntaktisk opbygget som en if- eller en while-sætning. Først er der et reserveret ord: synchronized, dernæst en parantes og endelig en sætning - i dette tilfælde, altid i tuborg-paranteser. Alt mellem tuborg-paranteserne er med i monitoren, mens det udenfor ikke er.
Flere monitorer Ikke alene giver en synkroniseret blok os mulighed for at "slanke" den del af koden som monitoren beskytter, den gør det også muligt at have mere end én monitor i et objekt.
Synkroniserer på objekter I paranteserne skal der angives en reference til et objekt. Alle synkroniserede blokke, der angiver en reference til det samme objekt, tilhører den samme monitor. Det er her væsentligt at bemærke, at det ikke er referencen, men objektet, der "synkroniseres på". Hvis vi f.eks. har to forskellige referencer, der refererer til det samme objekt, og vi anvender de to referencer i forbindelse med hver deres synkroniserede blok, vil begge blokke tilhøre den samme monitor.
  En almindelig synkroniseret metode synkroniserer i virkeligheden på objektet selv - dvs. this. Og en synkroniseret metode er ækvivalent med en metode med følgende opbygning:
 

public class A {
  ...
  
  public void metodeA() {
    synchronized ( this ) {

      // kritisk region

    }
  }

  ...
}

  Dvs. at hele metodens krop er indeholdet i den synkroniserede blok, samt at denne synkroniserer på objektet selv.
 

 

5.1.2 wait og notify

Flere tråde i samme monitor Vi har ovenfor antydet at vi i en monitor ikke nødvendigvis vil kræve, at kun en tråd kan være inde af gangen. Det lyder umiddelbart som et brud på mutex, men er det ikke. Det skyldes at vi i stedet kræver at kun en tråd må være aktiv i en monitor. Det skal forstås på den måde, at kun en tråd må have mutex låsen, og det at en anden tråd også indtræder i monitoren kræver at den tråd der allerede er inde, frigiver låsen, mens den bliver inde i monitoren. Tråde der er inde i monitoren, men ikke har låsen, kan ikke fortsætte deres udførelse før de igen erhverver låsen.
Konsistent tilstand Når man som tråd vælger at give afkald på mutex låsen, skal man derfor være meget opmærksom på at man kun gør det i situationer hvor resourcerne i den kritiske region er i en sådan tilstand, at man kan tillade andre at bruge dem - de skal befinde sig i en konsistent tilstand.
   
  Lad os se et eksempel med wait og notify:
  I Producer-Consumer var der risiko for deadlock, som vi dog undgik ved at bruge semaforer. Havde vi i stedet brugt aktiv venten, ville den situation kunne have opstået, at produceren kaldte push, konstaterede at der ikke var plads, begyndt at vente, og på den måde forhindrede consumeren i at komme ind i den kritske region, tage en vare, og dermed skabe den ledige plads som produceren venter på.
  Hvis vi i produceren i stedet for at vente aktivt, kunne have frigivet låsen, ventet hvor vi var kommet til, og fortsat når der kom en ledig plads, ville vi undgå en deadlock. Dette er muligt med wait og notify:
 
Stak.java
public class Stak {
  private int[] stak;
  private int pos;
  
  public Stak() {
    stak = new int[5];
    pos = 0;
  }
  
  public synchronized void push( int x ) {
    while ( pos == stak.length )
      Sleeper.wait( this );
        
    stak[ pos++ ] = x;
    System.out.println( this );
  }
  
  public synchronized int pop() {
    int value = stak[ --pos ];
    
    notify();
    
    return value;
  }
  
  public String toString() {
    StringBuffer sb = new StringBuffer();
    
    for ( int i=0; i<pos; i++ )
      sb.append( stak[i] + " " );
    
    return sb.toString();
  }
}
  For at undgå den try-catch, der kræves i forbindelse med kald af wait-metoden, har vi her valgt at placere den sammen med sleep-metoderne i Sleeper, der befinder sig der af samme grund. Bruger man den wait-metode, der er i Sleeper-klassen, skal man altid anføre this som parameter.
Sove på ubestemt tid Når wait-metoden kaldes i forbindelse med udførelsen af push, vil tråden afgive sin lås og lægge sig til at sove på ubestemt tid. Når en anden tråd kalder notify vil den vække tråden der sover, og denne må nu på samme vilkår som andre tråde erhverve sig låsen igen. Det betyder at den vågner, men umiddelbart ikke kan foretage sig noget, men må vente på at låsen bliver frigivet igen. Når den igen erhverver låsen, fortsætter den udførelsen af push, hvor den var kommet til.
  Med disse metoder, kan vi nu tillade flere tråd at være inde i monitoren, blot der kun er en, der har mutex låsen.
Muligt at rode Man bemærker at wait- og notify-metoderne, ikke stammer fra Thread-klassen, men fra selve Object-klassen, hvorfra de er nedarvet. Det skyldes at tråde der sætter sig til at vente, gør det i relation til det objekt som de befinder sig i. Det betyder samtidig at tråde kan vente på forskellige ting i forskellige monitorer i det samme objekt; hvilket kan blive rodet.
Vækker alle der venter notify vækker kun en af de ventende tråde, men der findes en anden metode, der vækker dem alle: notifyAll. notifyAll giver sikkerhed for, at man ikke vækker en tråd der venter på noget andet end det man har ændret. I så fald ville den tråd der vågnede lægge sig til at sove igen, og andre tråde, der måske i virkeligheden ventede på den skete ændring, vil ikke få lejlighed til at reagere på denne. At bruge notify i stedet for notifyAll er en optimering, der kan vise sig dyr. At bruge notify kræver, at man er helt sikker på at alle tråde, der kan lægge sig til at sove, med wait, venter på det samme.
Ikke sleep Det bør for en ordens skyld bemærkes at tråde, der har lagt sig til at sove med et kald af sleep ikke bliver vækket med hverken notify eller notifyAll.
 

 

5.1.3 Interrupts

  I forbindelse med sleep- og wait-metoderne i det foregående, har vi ikke været interesseret i, at de kan kaste en InterruptedException. Vi har derfor lavet en klasse: Sleeper, så vi kunne slippe for at bruge try-catch i forbindelse med disse metoder.
  Det er ikke uden grund, at metoderne kan kaste en sådan exception, og man bør i almindelighed ikke ignorere en sådan - den tjener nemlig et formål.
"Fraværende" tråd Det kendetegner både wait, sleep og join, at tråden i en periode ikke vil blive tildelt en time-slice - mao. tråden er "fraværende". Det betyder også, at vi umiddelbart er afskåret fra at kunne kommunikere med den. Et af de budskaber vi kunne tænkes at sende en tråd, er en request om at den skal terminere. Hvis vi i en sådan situation ikke har mulighed for at vække en tråd kan vi komme til at vente længe - endog meget længe - før den vågner op, opdager at den skal terminere, og gør det.
  Vi har tidligere set hvordan notify kan vække tråde, men problemet med notify i denne sammenhæng, er at vi ikke har mulighed for at vække en bestemt tråd. Til dette formål har enhver tråd i stedet følgende metode:
void interrupt()
  Når denne metode kaldes, vil der blive kastet en InterruptedException hvis tråden sover. Samtidig bliver der sat et flag i tråden, så den kan checke om den er blevet interrupted. Sidstnævnte skyldes primært, at vi ikke kan være sikre på, at den tråd vi interrupter, rent faktisk er "fraværende", og dermed igang med noget der kan kaste en InterruptedException. Hvis tråden ikke sover, skal den alligevel have mulighed for at registrere, at den har modtaget en interrupt-request - af denne grund har man flaget.
  Flaget kan aflæses med metoden:
boolean isInterrupted()
  Er man selv i tråden, behøver man ikke kende Thread-objektet, men kan blot kalde den statiske metode:
boolean Thread.interrupted()
  Som nævnt ovenfor kan man bruge interrupts i forbindelse med terminering af tråde, og det er da også deres primære anvendelse. Lad os se hvordan to-fase termineringen vi så på i kapitlet "Threads", kan laves med interrupts.
 

 

Eksempel: To-fase terminering

  I forhold til eksemplet i kapilet: "Threads", skal vi kun ændre i RunningThread-klassen:
 
RunningThread.java
public class RunningThread extends Thread implements Shutdownable {
  
  public void run() {
    while ( !interrupted() ) {
      System.out.println( "running..." );
      try {
        Thread.sleep( 2000 );
      } catch ( InterruptedException e ) {
        System.out.println( "InterruptedException kastet" );
        interrupt(); // sætte interrupt flag igen
      }
    }
    
    System.out.println( "shutdown in progress" );
    
    // afslut tråden
    Sleeper.sleep( 2 );
    
    System.out.println( "stopped" );
  }
  
  public void shutdown() {
    interrupt(); // sætte interrupt flag
    System.out.println( "shutdown requested" );
  }
}
  Man bemærker at vi kalder interrupt-metoden i catch-blokken. Det skyldes at interrupt-flaget bliver cleared når en InterruptedException bliver kastet. Hvis vi derfor ikke kaldte interrupt igen, ville while-løkken ikke terminere.
  Flaget bliver ligeledes cleared når interrupted-metoden kaldes, mens den ikke bliver cleared når man kalder isInterrupted-metoden. Det sidste er logisk, da denne metode er tiltænkt andre tråde, der ønsker at aflæse flaget; hvilket nødigt skulle clear'e det.
 

 

5.1.4 volatile

  Java garanterer, at tråde der er ved at opdatere en variabel af en primitive type (pånær double og long) ikke kan blive preempted før assignment er fuldført. Der er dog det problem, at mange compilere gør sig overvejelser om hvordan de kan optimere den oversatte bytekode.
  Sådanne optimering kan bla. ligge i, at den virtuelle maskine undlader at læse en variabel gentagne gange; hvis den vurderer at variablen ikke kan ændre værdi imellem to anvendelser. Det er naturligvis en udemærket idé, idet det tager tid at hente en variabels værdi, men det kan give problemer. Compilere har svært ved at optimere fler-trådede programmer, og deres antagelser om at variable ikke ændres kan derfor være forkerte. De ser anvendelsen af en variabel fra én tråd og tager ikke i betragtning at en anden tråd i mellemtiden kan have ændret værdien.
  Man kan måske undre sig over at compilere laver denne optimering, når det kan gå galt i forbindelse med tråde. Det skyldes at det så ofte går godt, og man flytter derfor byrden over på programmøren; hvis opgave det er at sikre, at denne optimering ikke forfejler programmets udførelse. Programmøren skal markere hvilke variable, der altid skal genlæses, og dermed ikke må indgå i en optimering. Dette gøres med det reserverede ord: volatile. F.eks.:
 
Stak.java
public class Stak {
  private int[] stak;
  private volatile int pos;
  
  ...
  
}
  Her har vi gjort pos-variablen volatile i Stak-klassen.
Som ændres Variable der tilgås af flere tråde, og som vel at mærke ændres, skal man altid gøre volatile. Vi har undladt at gøre det i eksemplerne hidtil, for at simplificere dem.
 

 

5.1.5 Tilstandsdiagram

  Efter vi nu har set på de mange muligheder med tråde i Java, er tiden kommet hvor vi vil samle det hele i et tilstandsdiagram, der beskriver hvordan tråde "lever":
 
  I diagrammet er der fem tilstande: New Thread, Runnable, Running, Not Runnable og Dead.
   
  Når man laver en instans af en Thread, befinder denne sig i New Thread tilstanden. Ved at kalde start-metoden bringer vi den dernæst i Running tilstanden. Idet vi i det følgende antager, at computeren kun har én CPU, kan kun en tråd befinde sig i Running tilstanden - det er den der er igang med sin time-slice.
  På et tidspunkt bliver tråden preempted og skifter til Runnable tilstanden. Her afventer den, at den igen tildeles en time-slice. Når run-metoden terminerer, terminerer også tråden og den ender i Dead tilstanden.
  Som vi tiligere har berørt, kan en tråd give afkald på resten af sin time-slice og derved gå i Runnable tilstanden. [Det er lidt svært at vise i figuren, da Runnable og Running tilstandene grafisk er sammenfaldende]
  Endenlig har vi Not Runnable tilstanden. En tråd kommer i denne tilstand hvis den kalder wait, sleep eller join. Og forlader den igen ved notify, interrupt eller en timeout. Tråde kan også gå i Not Runnable tilstanden hvis de venter på I/O operationer, der blokkerer.
   
fodnoter:

1

 

Per Brinch Hansen er, som man måske kunne gætte på navnet, dansker. Han er uddannet ingeniør fra DTH i 1962, og er kendt for sin omfattende forskning indenfor operativsystemer. I den forbindelse er han i første række kendt for to ting: monitorer og programmeringssproget: Concurrent Pascal. Sidst nævnte var det første sprog, der havde monitorer som en del af sproget.