SEMAFORY

1.	semafor ogólny  

Definicja klasyczna: 
semafor - zmienna całkowita S z wyróżnionymi operacjami: 

V: poniesienie (V vrijmaken, verhogen; signal):  
S= S+1 
P: opuszczenie (P passeren, proberen; wait): 
czekaj, aż S>0; S= S-1  (niepodzielna, gdy warunek jest prawdziwy)

Definicja "praktyczna":
	semafor - zmienna całkowita S z wyróżnionymi operacjami:
	
V: jeśli są procesy wstrzymane po operacji P(S), to wznów jeden z nich, 
w przeciwnym razie S=S+1
		P: jeśli S>0, to S=S-1, 
w przeciwnym razie wstrzymaj proces wykonujący te operacje 
2. semafor binarny
Rozwinięcia (semafory):

Definicja klasyczna: 
semafor - zmienna całkowita (logiczna) z wyróżnionymi operacjami:

	VB: S=1
	PB: czekaj, aż S=1; S=0  (niepodzielna, gdy warunek jest prawdziwy)

Definicja "praktyczna":
semafor - zmienna całkowita (logiczna) z wyróżnionymi operacjami:

VB: jeśli są procesy wstrzymane w wyniku P(S), to wznów jeden z nich, 
w przeciwnym razie S=1
	PB: jeśli S=1, to S=0, 
w przeciwnym razie wstrzymaj proces wykonujący te operacje
	
Uwagi: 
1.	Semafor ogólny da się symulować  dwoma semaforami  binarnymi i jedna zmienna całkowita,
2.	W semaforze ogólnym operacja P może wstrzymać proces, operacja V zaś nie wstrzymuje.

Semaphore.java (by S.Hartley)	
package Synchronization;

public abstract class Semaphore {

   // if value < 0, then abs(value) is the size of the P() queue
   protected int value = 0;
   protected Semaphore() {value = 0;}

//   protected Semaphore(int initial) {value = (initial > 0) ? initial : 0;}
   protected Semaphore(int initial) {
      // Don't be silent about bad initial value; tell the user!
      if (initial < 0) throw new IllegalArgumentException("initial<0");
      value = initial;
   }

   public synchronized void P() {
      value--;
      if (value < 0) {
         while (true) {     // we must be notified not interrupted
            try {
               wait();
               break;       // notify(), so P() succeeds
            } catch (InterruptedException e) {                           // CCCCCCCCCCCCC
                        System.err.println("Semaphore.P(): InterruptedException, wait again");
                        if (value >= 0) break; // race condition fix
                        else continue;         // no V() yet
            }
         }
      }
   }

   public synchronized void V() { // this technique prevents
      value++;                               // barging since any caller of
      if (value <= 0) notify();          // P() will wait even if it
   }                                              // enters before signaled thread

   // do not do a `if (S.value() > 0) S.P(); else ...'  because there is a race condition; use S.tryP() instead
   public synchronized int value() {
      return value;
   }

   public synchronized String toString() {
      return String.valueOf(value);
   }

   public synchronized void tryP() throws WouldBlockException {
      if (value > 0) this.P();  // nested locking, but already have lock
      else throw new WouldBlockException();
   } 
   
public synchronized void interruptibleP() throws InterruptedException {
      value--;
      if (value < 0) {
         try { wait(); }
         catch (InterruptedException e) {
            System.err.println ("Semaphore.interruptibleP(): InterruptedException");
            value++;      // backout, i.e., restore semaphore value
            throw e;
         }
      }
   }
}	

Uwaga do komentarza CCCCCCCCCCCC w metodzie P(): 

Może dojść do konfliktu, jeśli notify() wystąpi w tym samym czasie, co przerwanie jakiegoś oczekującego wątku przez inny watek (przerwanie wątku następuje, gdy wywołana jest jego metoda interrupt() ). 

Przypuśćmy, że zbiór  wątków oczekujących na semaforowym obiekcie składa się dokładnie z jednego wątku i że jakiś wątek próbuje wejść do V() aby wywołać notify(), gdy jakiś inny wątek wywołał metodę interrupt() wątku oczekującego. Wątek przerwany przechodzi wtedy z kolejki wątków oczekujących (wstrzymanych) do kolejki wątków gotowych,  gdzie oczekuje na otrzymanie zamka (lock) semaforowego obiektu.

W Javie każdy obiekt ma "osobisty zamek"-lock. Wątek wywołujący zsynchronizowaną metodę musi otrzymać ten właśnie lock przed jej wykonaniem. Zamek zaś jest tylko jeden, więc w danej chwili tylko jeden wątek może go posiadać. 

Teraz może nastąpić jedno z dwóch:
1.	notify() jest wykonane i ponieważ zbiór wątków oczekujących jest pusty, nic się nie dzieje; następnie przerwany wątek wraca do P() wewnątrz bloku catch  i ponownie zaczyna oczekiwać. 
2.	przerwany wątek powraca do P() i ponownie wywołuje  wait,  a po notify przechodzi  do wykonywania dalszej części metody.

W przypadku pierwszym tracony jest sygnał, natomiast w przypadku drugim już nie. Zgubione sygnały zaś mogą doprowadzić do blokady lub naruszenia algorytmu wzajemnego wykluczania. Aby zapobiec niepożądanym skutkom można: 
-	albo przesunąć `while(true)' poza `value--; if (value < 0)' oraz wstawić `value++' tuż przed `continue';  
-	albo wstawić `if (value >= 0) break' tuż przed `continue' (jak to zostało zrobione). Użytkownicy korzystający z interrupt() powinni wprowadzić takie zmiany.

BinarySemaphore.java	
package Synchronization;

// is final so subclassing cannot upset if (...) wait() and notify()
// but notify() (and wait() too) are public methods so still risky;
// better to create a private object and do notify(), wait() inside it
public final class BinarySemaphore extends Semaphore {

   public BinarySemaphore() {super();}  // constructors

//   public BinarySemaphore(int initial) {super((initial!=0) ? 1:0);}
   public BinarySemaphore(int initial) {
      super(initial);
      // Don't be silent about bad initial value; tell the user!
      if (initial > 1) throw new IllegalArgumentException("initial>1");
   }

   public BinarySemaphore(boolean initial) {super(initial ? 1:0);}

   public final synchronized void V() {
      super.V();
      if (value > 1) value = 1; // cap the value
   }
}

CountingSemaphore.java	
package Synchronization;

// is final so subclassing cannot upset if (...) wait() and notify()
// but notify() (and wait() too) are public methods so still risky;
// better to create a private object and do notify(), wait() inside it
public final class CountingSemaphore extends Semaphore {

   public CountingSemaphore() {super();}  // constructors

   public CountingSemaphore(int initial) {super(initial);}
}

Przykład wykorzystania semaforów (trzy watki wypisujące odpowiednio literki A, B, C, z tym, ze 1. A B musi wystąpić zanim pojawi się C; 2. B i C musza się pojawiać na przemian; 3. Suma całkowita wyprowadzonych B i C nie może przekroczyć liczby wystąpień A, licząc od początku pracy programu)