1. Semaforer

I C sköter man synkronisering med semaforer (Java använder som bekant monitorer). Semaforer är lättbegripliga, speciellt för villkorsynkronisering. Nackdelen är att de lätt skapar deadlock, så man måste vara försiktig. En semafor är ett objekt innehållande:

• En heltalsvariabel s, för vilken s>=0 alltid gäller.
• Metoden P() som tvingar tråden att vänta tills s>0. När s>0 så minskas s med 1.
• Metoden V() som minskar s och meddelar de väntande trådarna om förändringen.

// Semaphore class
public class Semaphore{
	// An s higher than 0
	private int s=1;
	// Constructor
	Semaphore(int s){
		this.s=s;
	}
	// P(): Request lock, and wait if lock is taken
	public synchronized void P(){
		while(s==0){
			try{ wait(); }
			catch(Exception e) {}
		}
		if(s>0) this.s--;
	}
	// V(): Release lock, and signal
	public synchronized void V(){
		this.s++;
		notify();
	}
}

2. Låsning

I detta fall använder man semaforen som ett lås för en viss kodsnutt. Man anropar P() då man vill låsa kodsnutten, och V() när man vill låsa upp kodsnutten.

• Semaforen ska initieras till 1 för att låset till den kritiska koden ska vara tillgängligt för den första tråden som kommer dit.
• OBS! För att verkligen få låsning bör metoden V() bara anropas av den tråd som nyss anropat P(). Alltså bara den tråd som låst semaforen får låsa upp den.

class Counter{
  private int i=1;
  public Semaphore mutex=new Semaphore(1);
  public test(){
    mutex.P(); // Lock the semaphore
    i=i+2;
    i=i-2;
    if(i>1){ 
      System.out.println("This can not happen!");
    }
    mutex.V(); // Unlock the semaphore
  }
}

3. Semaforer och synchronized

Det kan tyckas att semaforer som används på detta sätt utför samma sak som synchronized. Skillnaden är att synchronized låser hela objektet.

• Då en tråd går in i ett synchronized-block får ingen annan tråd gå in i något av objektets synchronized-block.
• Då en tråd går in i ett block som låses med semafor.P() kan objektet användas som vanligt. Bara det aktuella blocket är låst, d.v.s endast de trådar som exekverar satsen semafor.P() kommer att blockeras.

4. Villkorssynkronisering

I detta fall använder man semaforen för att signalera till en väntande process då ett visst villkor är uppfyllt. Metoden P() används här för att tvinga tråden att vänta på villkoret, och ett anrop till V() väcker den väntande tråden då villkoret är uppfyllt.

• Semaforen ska initieras till 0. Ty om s=0 börjar alla trådar som stöter på P() att vänta.

// Main class
public class Barrier{
  public static void main(String args[]){
    Semaphore cond=new Semaphore(0);
    for(int i=0; i<4; i++){
      new Stopper(cond).start();
    }
    new Talker(cond).start();
  }
}
// Doing nothing, just talking
class Talker extends Thread{
  Semaphore cond;
  public Talker(Semaphore cond){
    super();
    this.cond=cond;
  }
  public void run(){
    System.out.println("Hello, Im releasing you all!");
    cond.V(); // release the semaphore
  }
}
// Waiting until first V()
class Stopper extends Thread{
  Semaphore cond;
  public Stopper(Semaphore cond){
    super();
    this.cond=cond;
  }
  public void run(){
    System.out.println( getName()+" is running");
    cond.P();
    System.out.println( getName()+" Barrier broke");
    cond.V();
  }
}

[olle@dev1]$ java Barrier
Thread-1 is running
Thread-2 is running
Thread-3 is running
Thread-4 is running
Hello, Im releasing you all!
Thread-1 Barrier broke
Thread-2 Barrier broke
Thread-3 Barrier broke
Thread-4 Barrier broke

5. Readers/Writers

Nu ska vi modifiera klassen Controller i exemplet som beskrivs på sidan  Readers/Writers  till att lösa problemet med semaforer. En lösning med semaforer genererar mer kod än en lösning med monitorer, och är samtidigt svårare att skriva utan buggar. Å andra sidan lämnar lösnigen med semaforer möjligheter att göra programmet mer rättvist i det avseendet att läsarna inte får förtur. Nedan visas Controller:

// CONTROLLER // This is the class we will modify // to solve the readers/writers problem class Controller{ Resource res; int cr=0; // concurrent readers int dr=0; // delayed readers int cw=0; // concurrent writers int dw=0; // delayed writers Semaphore mutex=new Semaphore(1); Semaphore sem_r=new Semaphore(0); Semaphore sem_w=new Semaphore(0); public Controller(Resource resource){ this.res=resource; } public void read(UserThread t){ mutex.P(); // Lock if(cw>0){ dr++; mutex.V(); // Unlock sem_r.P(); // Wait for READ signal mutex.P(); // Lock dr--; } cr++; if(dr>0) sem_r.V(); // Signal READ mutex.V(); // Unlock //--- Call Read ---- res.read(t); mutex.P(); // Lock cr--; if(cr==0 && dw>0) sem_w.V(); // Signal WRITE mutex.V(); // Unlock } public void write(UserThread t){ mutex.P(); // Lock if(cw>0 || cr>0){ dw++; mutex.V(); // Unlock sem_w.P(); // Wait for WRITE signal mutex.P(); // Lock dw--; } cw++; mutex.V(); // Unlock //--- Call Write --- res.write(t); mutex.P(); // Lock cw--; if(dw>0) sem_w.V(); // Signal WRITE else if(dr>0) sem_r.V(); // Signal READ mutex.V(); // Unlock } }

Vi ser i lösningen att vi genomgående försökt ge write() förtur:

• I slutet av read() bryr vi oss bara om om det finns några fördröjda skrivare, eventuella fördröjda läsare ignoreras.
• I slutet av write() låter vi först alla fördröjda skrivar köra, och endast om det inte finns några skrivare så släpper vi lös de fördröjda läsarna.

[olle@dev1]$ java ReadersWriters 3 3 3
All readers and writers are created!
|R     |
|RR    |
|RRR   |
|RR    |
|R     |
|      |
|W     |
|      |
|W     |
|      |
|W     |
|      |
|W     |
|      |
|W     |
|      |
|W     |
|      |
|W     |
|      |
|W     |
|      |
|R     |
|RR    |
|RRR   |
|RR    |
|R     |
|      |
|W     |
|      |
|R     |
|RR    |
|R     |
|RR    |
|R     |
|      |