programmera.net -> java -> normal     för utskrift      info@programmera.net

Problemet Readers/Writers

1. Readers/Writers
2. Testmiljö
3. Kod
4. Utskrift
5. Länkar

1. Readers/Writers

Ett vanligt problem är Readers/Writers. Problemet går ut på att det finns en viktig resurs i systemet, en fil eller databas eller liknande, som vi vill skydda på detta sätt:

  • Resursen ska kunna läsas samtidigt av flera trådar.
  • Resursen ska bara kunna skrivas av en tråd i taget, och då tråden skriver får inga läsningar ske.

2. Testmiljö

Nu ska vi skriva ett program som fungerar som testmiljö för olika lösningar av problemet. Programmets struktur är denna:

  • Det finns en klass, Resourse, som representerar resursen. Klassen har två metoder: read() och write().
  • Det finns en mängd trådar, UserThread, som vill läsa och skriva till Resource.
  • Det finns en klass, Controller, som skyddar klassen Resource från trådarna. Controller har också metoderna read() och write() som i sin tur anropar metoderna i Resource. Trådarna måste anropa metoderna i Controller för att komma åt Resource.
Den klass som kommer att modifieras senare är Controller. I nuläget ser den ut såhär: 
// CONTROLLER
// This is the class we will modify
// to solve the readers/writers problem
class Controller{
  Resource  res;
  
  public Controller(Resource resource){
    this.res=resource;
  }
  
  public void read(UserThread t){
    res.read(t);
  }
  
  public void write(UserThread t){
    res.write(t);
  }
}
Som synes vidarebefordrar bara Controller anropen av read() och write() till Resource. Nedan beskrivs andra detaljer i programmet:
  • För att addera en gnutta realism till problemet tvingar vi trådarna att vänta en slumpivs lång tid mellan varje läsning eller skrivning. Själva läsningen och skrivningen tar också en liten tid. Jag har satt arbetstiden för skrivningar till genomsnittligt dubbla arbetstiden för läsningar.
  • Varje gång en tråd går in eller ut ur någon av metoderna Resource.read() eller Resource.write() ritas en bild av vilka trådar som använder resursen.

3. Kod

Här kommer koden: 
import java.io.*;
import java.util.*;

// The class with the main()
public class ReadersWriters{
  
  public static void main(String[] args){
    if(args.length != 3){
      System.out.println("Called with 3 arguments: readers writers rounds!");
      System.exit(1);
    }
    int readers=Integer.parseInt(args[0]);
    int writers=Integer.parseInt(args[1]);
    int rounds=Integer.parseInt(args[2]);
    Resource resource=new Resource(readers,writers);
    Controller controller=new Controller(resource);
    for(int i=0; i<readers; i++){ 
      new UserThread(rounds, true, controller).start();
    }
    for(int i=0; i<writers; i++){ 
      new UserThread(rounds, false, controller).start();
    }
    System.out.println("All readers and writers are created!");
  }
}
// UserThread
// This thread calls read() and write() of Controller
class UserThread extends Thread{
  Sleeper sleeper=new Sleeper();
  int rounds;
  boolean isReader;
  Controller controller;
  public UserThread(int rounds, boolean isReader, Controller controller){
    this.rounds=rounds;
    this.isReader=isReader;
    this.controller=controller;
  }
  public void run(){
    for(int i=0; i< rounds; i++){
      sleeper.rest(this,8); // take a break
      if(isReader) controller.read(this);
      else         controller.write(this);
    }
  }
}
// CONTROLLER
// This is the class we will modify
// to solve the readers/writers problem
class Controller{
  Resource  res;
  
  public Controller(Resource resource){
    this.res=resource;
  }
  
  public void read(UserThread t){
    res.read(t);
  }
  
  public void write(UserThread t){
    res.write(t);
  }
}

// This is the Resource we want to protect
// The methods call rest() to simulate some timeconsuming action.
// The methods call print() to print the state to screen.
class Resource{
  Sleeper sleeper=new Sleeper();
  int sblen; // Length of the StringBuffer
  int cr=0; // Number of concurrent readers
  int cw=0; // Number of concurrent writers
  
  public Resource(int readers,int writers){
    this.sblen=readers+writers+2;
  }
  public void read(UserThread t){
    cr++;
    print();
    sleeper.rest(t,2);
    cr--;
    print();
  }
  public void write(UserThread t){
    cw++;
    print();
    sleeper.rest(t,4);
    cw--;
    print();
  }
  // This method prints:
  // * one R for every concurrent reader that is inside read()
  // * one W for every concurrent writer that is inside write()
  public void print(){
    StringBuffer sb=new StringBuffer("  ");
    sb.setLength(sblen);
    for(int i=0; i<sblen; i++){
      sb.setCharAt(i,' ');
    }
    sb.setCharAt(0,'|'); 
    sb.setCharAt(sblen-1,'|');
  
    for(int i=0; i<cr; i++){
      sb.setCharAt(1+i,'R');
    }
    for(int i=0; i<cw; i++){
      sb.setCharAt(1+cr+i,'W');
    }
    System.out.println(sb);
  }
}

// This class controlls all delays
class Sleeper{
  Random rand=new Random();
  public void rest(UserThread t, int time){
    int x=Math.round(time*100*rand.nextFloat());
    try{
      t.sleep(x);
    }catch(Exception e){ System.out.println(e); }
  }
}

4. Utskrift

Nedan ges ett exempel på utskrift från ReadersWriters: 
[olle@dev1]$ java ReadersWriters 3 3 3
All readers and writers are created!
|R     |
|RR    |
|RRR   |
|RRRW  |
|RRRWW |
|RRRWWW|
|RRRWW |
|RRWW  |
|RRW   |
|RW    |
|W     |
|      |
|W     |
|RW    |
|RWW   |
|RW    |
|RRW   |
|RRRW  |
|RRW   |
|RW    |
|W     |
|WW    |
|W     |
|      |
|W     |
|      |
|R     |
|RR    |
|RRR   |
|RR    |
|R     |
|      |
|W     |
|WW    |
|W     |
|      |
Utskriften ska tolkas på detta sätt:

  • Varje R representerar en läsartråd som är inne i metoden Resource.read().
  • Varje W representerar en skrivartråd som är inne i metoden Resource.write().
Som vi ser tillåter denna naiva metod flera läsartrådar att samtidigt anropa Resource.read() vilket inte löser readers/writers-problemet.

5. Länkar

På följande sidor finns modifieringar av Controller som löser readers/writers-problemet: