© 1999-2003, Flemming Koch Jensen Alle rettigheder forbeholdt

Klassiske problemer Opgaver (endnu ingen opgaver)

 

 

	Vi skal i dette kapitel se på to af de klassiske problemer, eller opgaver, som man har dyrket i forbindelse med samtidighed.
	1. Readers & writers
Læse ofte, opdatere sjældent	Problemstillingen i readers & writers er meget enkel. Der findes "et stykke data", som nogle tråde ønsker at læse, og nogle tråde ønsker at opdatere (skrive i). Hvis det er relativ sjældent at tråde ønsker at opdatere, mens læsning er tilsvarende hyppigere, er det uhensigtsmæssigt med mutex. Det skyldes, at der en betydelig del af tiden, kun er tråde der ønsker at læse; hvilket ikke kræver mutex. Mutex vil i disse perioder lægge en uhensigtsmæssig dæmper på afviklingen af trådene.
	Opgaven er derfor at lave en konstruktion, så readers ikke behøver at have mutex i relation til hinanden, men kun i forhold til writers.
	1.1 Løsning med semaforer
	Vi vil først se en løsning med semaforer. Den er meget enkel, men som vi skal se, har det en pris.
	RW_Data.java public class RW_Data { private Semafor readersSemafor, dataSemafor; private int readers; private int value; public RW_Data() { readersSemafor = new Semafor(); dataSemafor = new Semafor(); readers = 0; value = 0; } public int read() { readersSemafor.down(); readers++; if ( readers == 1 ) dataSemafor.down(); readersSemafor.up(); int res = value; readersSemafor.down(); readers--; if ( readers == 0 ) dataSemafor.up(); readersSemafor.up(); return res; } public void write( int value ) { dataSemafor.down(); this.value = value; dataSemafor.up(); } }
	Vi har her farvet de to semaforer henholdsvis blå og rød.
	De to semaforer er binære semaforer og anvendes til at opnå mutex på de to variable: readers og value. readersSemafor er mutex lås for readers-variablen, mens dataSemafor er mutex lås for value.
	Ser man ned over read-metoden, bemærker man, at dataSemafor'en beskytter læsningen af value, men at down og up på denne semafor er beskyttet af en anden semafor: readersSemafor. Inden vi ser nærmere på denne beskyttelse, vil vi se hvilken rolle variablen: readers spiller.
	De to if-sætninger, før og efter læsningen af value, drejer sig om tage, henholdsvis frigive, mutex låsen til value.
	Hvis én reader har læselås betyder det, at readers bare kan myldre ind, men den sidste skal huske at "lukke og slukke" - dvs. frigive låsen på value. Når en reader kalder read-metoden, starter den med at checke om den er den første der vil have en læselås; hvis det er tilfældet, tager den mutex låsen på value, eller venter om nødvendigt på at den kan få den, ved at kalde down på dataSemafor.
	Når en reader giver afkald på sin læselås, skal den omvendt checke om den er den sidste der gør dette. I givet fald skal den også frigive låsen på value, ved at kalde up på dataSemafor.
	På denne måde sørger den første reader for at tage mutex låsen på value, mens den sidste frigiver den igen.
	At dette fungerer afhænger dog af readersSemafor'en. Uden den, er der race conditions!
	Lad os se hvad der sker; hvis vi fjerner beskyttelsen af den første del af read-metoden:
	Hvis de første to readers kalder read-metoden samtidig, vil de begge tæller readers op med 1, så den bliver 2. Dernæst vil de begge fejlagtigt konstatere, at de ikke er den første der ønsker en læselås, og begge vil dernæst tilgå value uden at have mutex låsen.
	Kommer de to første readers i stedet hurtigt efter hinanden, mens mutex låsen på value er optaget, vil den første vente på mutex låsen, mens den anden vil tælle readers op til 2 og dernæst tilgå value uden at have mutex låsen.
	Lad os dernæst se hvad der sker; hvis vi fjerner beskyttelsen af den sidste del af read-metoden:
	Hvis de sidste to readers samtidig beslutter sig for at frigive deres læselås, vil de samtidig tælle readers ned med 1, så den bliver 0. Dernæst vil de samtidig konstatere, at de begge er den sidste reader, og begge frigive mutex låsen; ved at kalde up på dataSemafor. Derved bliver dataSemafor 2, og den er dermed ikke længer en mutex lås.
	Selvom ovenstående løsning virker, så har den et problem - den udsulter writers!
	En writer kan kun få en skrivelås, hvis der ikke er nogen reader der har en læselås, men da readers kan få læselås selvom andre også har det, kan der ske udsultning, da readers i en lind strøm kan sørge for at deres fælles mutex lås aldrig bliver frigivet. At hyppigheden af læsninger er større en skrivninger gør kun det hele endnu værre!
	Vi skal i det følgende se på løsninger, der prioriterer writers, og derved ikke udsulter dem. Disse løsninger kan til gengæld udsulte readers, men da hyppigheden af skrivinger er mindre end læsninger, antager vi at dette kun sker kortvarigt i praksis.
	[Løsningen er lavet af Courtois oa. i 1971. Han har også lavet en løsning der favoriserer writers. Courtois P.J., Heymans F. og Parnas, D.L.: "Concurrent Control with Readers and Writers", Comm. of the ACM, vol. 10, s. 667-68, Okt. 1971 (har fået en kopi af den, og skal have studeret den nærmere ved en senere lejlighed)]
	1.2 Den symmetrisk løsning
	Følgende løsning har jeg valgt at betegne som "den symmetriske løsning", da implementationen er meget ensartet for både readers og writers.
	Lock.java public interface Lock { public void getWriteLock(); public void getReadLock(); public void releaseWriteLock(); public void releaseReadLock(); }
	Først erklærer vi et interface: Lock, som vi vil bruge i denne og den næste løsning vi vil se. Det er et interface, som tilbyder metoder til at opnå/frigive de to typer låse vi arbejder med: læse-lås og skrive-lås.
	Den løsning vi først vil se, laves med klassen: RW_Lock:
	RW_Lock.java public abstract class RW_Lock implements Lock { protected int activeReaders, activeWriters; protected int waitingReaders, waitingWriters; public RW_Lock() { activeReaders = activeWriters = 0; waitingReaders = waitingWriters = 0; } public synchronized void getWriteLock() { waitingWriters++; while ( !allowWriter() ) Sleeper.wait( this ); waitingWriters--; activeWriters++; } public synchronized void getReadLock() { waitingReaders++; while ( !allowReader() ) Sleeper.wait( this ); waitingReaders--; activeReaders++; } public synchronized void releaseWriteLock() { activeWriters--; notifyAll(); } public synchronized void releaseReadLock() { activeReaders--; notifyAll(); } protected abstract boolean allowReader(); protected abstract boolean allowWriter(); }
	Som nævnt er løsningen meget symmetrisk. De to get- henholdsvis release-metoder er slående ens! Det skyldes til dels de to abstrakte metoder: allowReader og allowWriter. Det er subklassen: RW_Lock_W, der realiserer forskellen på de to typer låse:
	RW_Lock_W.java public class RW_Lock_W extends RW_Lock { protected boolean allowReader() { return waitingWriters==0 && activeWriters==0; } protected boolean allowWriter() { return activeWriters==0 && activeReaders==0; } }
	Her ser vi at allowWriter er mere restriktiv end allowReader, og de boolske udtryk afspejler direkte den betydning de to låse har. allowReader tillader at der gives en læse-lås; hvis der blot ikke er nogen der er ved at skrive eller ønsker at komme til det - altså ingen krav vedrørende andre der læser, mens allowWriter er mere restriktiv. Den tillader kun, at man får en skrive-lås; hvis der hverken er nogen der læser eller skriver.
	Dernæst skal vi have en testanvendelse, og til det formål laver vi en data-klasse, der skal indholde den kritiske region:
	Data.java public class Data { private int data; private Lock lock; public Data( int data, Lock lock ) { this.data = data; this.lock = lock; } public int get() { lock.getReadLock(); System.out.println( thread() + " - read start" ); int res = data; System.out.println( thread() + " - read end" ); lock.releaseReadLock(); return res; } public void set( int data ) { lock.getWriteLock(); System.out.println( thread() + " - write start" ); this.data = data; System.out.println( thread() + " - write end" ); lock.releaseWriteLock(); } private String thread() { return Thread.currentThread().getName(); } }
	I selve get/set-metoderne foretages kaldene til låse-objektet, med de fire get/release-metoder. Der er foretaget indrykninger der understreger denne sammenhæng.
	Dernæst skal vi have to klasser, der kan repræsenterer henholdsvis readers og writers:
	Reader.java public class Reader extends Thread { private Data data; public Reader( String id, Data data ) { super( "Reader " + id ); this.data = data; } public void run() { while ( true ) { Sleeper.sleepRandom( 1 ); // oftere end en writer System.out.println( getName() + " read: " + data.get() ); } } }
	Writer.java import java.util.Random; public class Writer extends Thread { private Data data; private static final Random rnd=new Random(); public Writer( String id, Data data ) { super( "Writer " + id ); this.data = data; } public void run() { while ( true ) { Sleeper.sleepRandom( 3 ); // ikke så ofte som en reader int newValue = rnd.nextInt( 10 ); data.set( newValue ); System.out.println( getName() + " wrote: " + newValue ); } } }
	Disse er lavet så de aldrig stopper. Bemærk at en reader er mere aktiv end en writer; hvilket afspejler vores udgangspunkt - at der læses oftere end der skrives.
	Endelig har vi selve main-metoden, der laver to readers og en writer (dette afspejler igen at der er flere der ønsker at læse end at skrive):
	Main.java public class Main { public static void main( String[] argv ) { Data data = new Data( 5, new RW_Lock_W() ); new Reader( "A", data ).start(); new Reader( "B", data ).start(); new Writer( "1", data ).start(); } } Reader A - read start Reader A - read end Reader A read: 5 Writer 1 - write start Writer 1 - write end Writer 1 wrote: 5 Reader B - read start Reader B - read end Reader B read: 5 Reader B - read start Reader B - read end Reader B read: 5 Writer 1 - write start Writer 1 - write end Writer 1 wrote: 5 Reader A - read start Reader A - read end Reader A read: 5 ...
	[Løsningen er en lettere omskrivning af Doug Lea's løsning fra hans bog: "Concurrent Programming in Java, design principles and patterns", s. 132-34, Addison-Wesley, 1996. Omskrivningen er ligeledes inspireret Martin Olsen's omskriving af nævnte løsning]
	1.3 Writers i kø
	Den tredie og sidste løsning vi skal studere, arbejder med en kø; hvori writers venter, samtidig med at de har prioritet fremfor readers
	ReadWriteLock.java import java.util.LinkedList; public class ReadWriteLock implements Lock { private LinkedList waitingWriters; private int waitingReaders; private int readLocks; private Thread writer; public ReadWriteLock() { waitingWriters = new LinkedList(); waitingReaders = 0; readLocks = 0; writer = null; } public synchronized void getReadLock() { waitingReaders++; while ( writer != null ) Sleeper.wait( this ); waitingReaders--; readLocks++; } public void getWriteLock() { Thread me = Thread.currentThread(); synchronized ( this ) { if ( writer == null && readLocks == 0 ) { writer = me; return; } else waitingWriters.addLast( me ); } synchronized ( me ) { while ( me != writer ) Sleeper.wait( me ); } } public synchronized void releaseReadLock() { readLocks--; if ( readLocks == 0 && waitingWriters.size() > 0 ) nextWriter(); } public synchronized void releaseWriteLock() { if ( waitingWriters.size() > 0 ) nextWriter(); else { writer = null; if ( waitingReaders > 0 ) notifyAll(); } } private void nextWriter() { writer = (Writer) waitingWriters.removeFirst(); synchronized ( writer ) { writer.notify(); } } }
	Klassen har fire instansvariable:
	waitingWriters er listen med writers, der venter på en skrivelås. waitingReaders og readLocks tæller hvor mange der henholdsvis venter på, og har, en læselås. Endelig er writer en reference til den tråd der har skrivelås; hvis ingen, så null.
	Dernæst er der de fire metoder fra Lock-interfacet:
	getReadLock giver en læselås med mindre, der er en tråd der har skrivelås. Hvis der ikke kan opnås en læselås sætter tråden sig til at vente, for senere at blive vækket af releaseWriterLock-metoden.
	releaseReadLock checker om der er nogen der ønsker en skrivelås, og en sådan bevilges hvis der ikke er andre der har læselås. Dette gøres ved at kalde nextWriter-metoden.
	getWriteLock er den mest komplicerede af de fire metoder. Den består af to dele.
	Først checkes det om man umiddelbart kan få en skrivelås. Hvis dette ikke er tilfældet indsættes tråden i listen over ventende writere, og vi går videre til anden del af metoden. I anden del sætter vi os til at vente indtil vi eksplicit bliver vækket, efter at have fået tildelt en skrivelås af nextWriter-metoden.
	releaseWriteLock lader en anden writer overtage skrivelåsen; hvis en sådan venter i waitingWriters-listen. Ellers vækkes de ventende readers; hvis der er nogle sådanne.
	nextWriter-metoden anvendes af de to release-metoder når de ønsker at give en skrivelås til en ventende writer (det er de kaldende metoder, der checker om der er en sådan). Metoden udtager den første af de ventende writere og vækker denne efter at have givet den skrivelåsen. På denne måde kommer listen til at fungere som en kø.
	[Løsningen er en lettere omskrivning/optimering af Mark Grand's løsning fra hans bog: "Patterns in Java, Volume 1", s. 431-39, Wiley, 1998]
	1.3.1 Kobling med writer'nes tråde
	Når vi udvælger en writer fra køen ovenfor, bruger vi notify til at vække den. I den forbindelse anvender vi selve tråd-objektet for den pågældende writer, så vi eksplicit kan vække den pågældende writer, uden at vække andre. Det virker derfor umiddelbart naturligt at vi bruger ikke bruger notifyAll, da der kun kan være én der venter i relation til tråd-objektet, og notifyAll derfor ville være unødvendigt.
	Det er dog ikke så hensigtmæssigt set i et større perspektiv. I forbindelse med reader'ne bruger vi venten i relation til selve ReadWriteLock-objektet; hvilket holder løsningen inden for rammerne af låsen. At vi i forbindelse med writer'ne bruger objekter (writer'nes tråd-objekter), der kan spille en rolle i relation til andre dele af systemet, skaber en kobling mellem vores løsning og det øvrige objektsystem. Det er en kobling som vi bør tage i betragtning!
	Andre dele af systemet kan også vælge at vente i relation til writer'nes tråd-objekter (f.eks. så enkelt som, at de har join'et tråden), og vi kan derfor ikke være sikre på, at der kun er én tråd (den der venter i kaldet af getWriteLock) der venter. Anvender vi notify, og en af disse andre tråde bliver vækket i stedet for en writer, vil låsen være permanent blokket. Vi bliver derfor nød til at bruge notifyAll.
	Læren af disse betragtninger, er ikke kun et spørgsmål om koblinger, men det er i lige så høj grad en advarsel mht. at anvende notify i stedet for notifyAll - man bør kun foretage denne optimering; hvis man er 110% sikker i sin sag. Det skal samtidig bemærkes, at i mange anvendelser er en sådan optimering alligevel en meget beskeden gevinst.
	2. Dining philosophers
	Dining philosophers (De spisende filosoffer) er en sand klassisker, som Dijkstra konstruerede i 1965. Det er samtidig er et eksempel på en finurlig anvendelse af semaforer.
	Situationen er den, at en gruppe af filosoffer er samlet omkring middagsbordet. Der er spaghetti på menu'en. Enhver spaghetti entusiast ved at man til spisning af spaghetti kun behøver en gaffel, men af ukendte årsager skal filosofferne i vores eksempel bruge to gafler til at spise spaghetti. Desværre er det lidt små med gafler - faktisk har man kun, hvad der svarer til én gaffel pr. filosof. Man har placeret gaflerne på det obligatoriske runde bord, således at der er en gaffel imellem hver tallerken:
	Hver filosof skal nu bemægtige sig de to gafler ved hans tallerken. Det er naturligvis en fremgangsmåde der giver nogle forviklinger - hvilket er det interessante ved problemet.
	Filosoffer er jo civiliserede mennesker og når de har haft lejlighed til at spise lidt spaghetti lægger de igen begge gafler, så deres kolleger også kan få lejlighed til at spise - og så fremdeles.
Ineffektiv løsning	Det er åbenlyst at vi har et samtidighedsproblem, og det er meget enkelt at løse. Vi sætter blot en mutex lås på det hele og lader en filosof spise af gangen. Løsningen er nem nok, men den er ikke optimal. Med flere gafler burde det kunne lade sig gøre at flere filosoffer kunne spise på en gang. På figuren ovenfor burde der f.eks. kunne være to filosoffer, der spiste samtidig.
Deadlock	Desværre dur det ikke at lade filosofferne selv tage en gaflerne, for derved kan der opstå deadlock. Hvis alle filosoffer samtidig tager den venstre (eller den højre) gaffel, sidder de alle med en gaffel, og så sker der ikke mere!
	Idéen i den løsning vi her skal se, er at vi sætter en mutex lås på det at undersøger om man kan tage de to gafler man skal bruge. En filosof der ønsker at spise vil derfor først skulle tage mutex låsen. Dernæst undersøger han om han kan tage de to gafler. Hvis det er muligt, tager han dem og frigiver låsen. Er det derimod ikke muligt sætter han sig til at vente passivt (filosoffere; hvilket sikkert har givet Dijkstra idéen til, at det skulle være filosoffer).
Checker for nabo	Ovenstående var, så at sige, den nemme del, for hvordan skal filosoffen blive vækket, hvis de to gafler bliver ledige? Det sker naturligvis ved at en af nabo-filosofferne lægger sin gafler - den sidste af de to som vores filosof behøver. Når en filosof lægger sine gafler, undersøger han samtidig om hans nabo-filosoffer kan komme til at spise, og i givet fald vækker han dem.
	Der er dermed to måder hvor på en filosof kan få de to gafler: Enten ved at han selv ser at de er ledige, eller ved at en af hans nabo-filosoffer gør ham opmærksom på det.
Semafor	Den passive venten realiseres med en semafor til hver filosof. Når filosoffen ønsker at gå i passiv venten kalder han down på sin semafor, og når en kollega vil sætte ham igang med at spise, kalder denne up på hans semafor. For semaforen vedkommende betyder det, at denne skal initialiseres til 0, så down også blokkerer første gang den kaldes.
To arrays	Mutex låsen som vi bragte ind i billedet overnfor, kommer til at fungere som lås for de variable der beskriver tilstanden. Tilstanden beskrives med et array af Semafor'er - med en semafor til hver filosof. Ud over dette array, skal der også bruges et array, der beskriver tilstanden for den enkelte filosof : Om han filosofferer: THINKING, om han er sulten: HUNGRY eller om han er ved at spise: EATING.
	Vi er ved at være klar til at se løsningen:
	Table.java public class Table { // States public static final int THINKING=0; public static final int HUNGRY=1; public static final int EATING=2; private Semafor mutex; private Semafor[] pSemafor; private int[] pState; public Table( int philosophers ) { mutex = new Semafor(); pSemafor = new Semafor[ philosophers ]; for ( int i=0; i<philosophers; i++ ) { pSemafor[i] = new Semafor(); pSemafor[i].down(); } pState = new int[ philosophers ]; for ( int i=0; i<philosophers; i++ ) pState[i] = THINKING; } public void takeForks( int philosopher ) { mutex.down(); pState[ philosopher ] = HUNGRY; check( philosopher ); mutex.up(); // blokkerer kun hvis vi ikke fik gaflerne pSemafor[ philosopher ].down(); } public void putForks( int philosopher ) { mutex.down(); pState[ philosopher ] = THINKING; check( leftOf( philosopher ) ); check( rightOf( philosopher ) ); mutex.up(); } private void check( int philosopher ) { if ( pState[ philosopher ] == HUNGRY && pState[ leftOf( philosopher ) ] != EATING && pState[ rightOf( philosopher ) ] != EATING ) { pState[ philosopher ] = EATING; pSemafor[ philosopher ].up(); } } private int leftOf( int philosopher ) { if ( philosopher == 0 ) return pState.length-1; else return philosopher-1; } private int rightOf( int philosopher ) { return (philosopher + 1) % pState.length; } }
	I konstruktoren ser man at semaforerne initialiseres, som binære semaforer, som der kaldes down på, for at bringe dem ned på 0 fra starten. Tilstandene beskrives med tre tal-konstanter.
	Man bemærker at mutex beskytter de to arrays (markeret med blåt)
	Kontrollen af, om de to gafler er til stede er placeret i en service-metode: check, der kaldes både af filosoffen selv, og hans nabo-filosoffer når de lægger gaflerne. Bemærk i den forbindelse, hvordan check-metodens kald af up hindrer at down efterfølgende blokkerer (forudsat at gaflerne er ledige), hvis man selv har kaldt metoden. På den måde slipper vi i takeFork-metoden, for at differenciere mellem om gaflerne er ledige eller ej.
	Til vores testanvendelse bruger vi en klasse: Philosopher, til at realisere filosoferne:
	Philosopher.java public class Philosopher extends Thread { private int id; private Table table; public Philosopher( int id, Table table ) { this.id = id; this.table = table; } public void run() { while ( true ) { System.out.println( "Philosopher " + id + " thinking" ); Sleeper.sleepRandom( 3 ); // tænker tanker ... System.out.println( "Philosopher " + id + " want to take forks" ); table.takeForks( id ); System.out.println( "Philosopher " + id + " eating" ); Sleeper.sleepRandom( 3 ); // spiser ... System.out.println( "Philosopher " + id + " putting down forks" ); table.putForks( id ); } } }
	Endelig har vi main-metoden, der instantierer og byder filosofferne til bords:
	Main.java public class Main { public static void main( String[] argv ) { int philosophers = 5; Table table = new Table( philosophers ); for ( int i=0; i<philosophers; i++ ) new Philosopher( i, table ).start(); } } Philosopher 0 thinking Philosopher 1 thinking Philosopher 2 thinking Philosopher 3 thinking Philosopher 4 thinking Philosopher 1 want to take forks Philosopher 1 eating Philosopher 1 putting down forks Philosopher 1 thinking Philosopher 2 want to take forks Philosopher 2 eating Philosopher 0 want to take forks Philosopher 0 eating Philosopher 1 want to take forks Philosopher 4 want to take forks Philosopher 3 want to take forks Philosopher 0 putting down forks Philosopher 4 eating Philosopher 0 thinking Philosopher 2 putting down forks Philosopher 1 eating Philosopher 2 thinking ...