# L2 - zarys teoretyczny (bez wyprowadzenia wzorów)

* relacja **A $\rightarrow$ B** mówi, że zdarzenie A było wcześniej, niż zdarzenie B

* **FCFS** (first-come first-served) - jeśli wątek **A** wykonał **doorway-section** przed wątkiem **B**, to **B** nie może wyprzedzić **A**


* **Algorytm Petersona**:

public void lock() {
 flag[i] = true; 
 victim = i;
 while (flag[j] && victim == i) {};
}
public void unlock() {
 flag[i] = false; 
}

dla dwóch wątków jest bardzo dobry

* własność **r-ograniczonego czekania** - wątek, który wykonał sekcję wejściową będzie “wyprzedzony” co najwyżej r razy przez wątek, który wykonał tę sekcję po nim (r-ograniczenie implikuje niezagłodzenie, ale nie działa to w drugą stronę)

Algorytm Petersona ma własność 0-ograniczonego czekania (bo żaden wątek który będzie próbował wejść po nas nas nie wyprzedzi)
* **sekcja wejściowa** (doorway section) - początkowy fragment metody lock(), liczbę kroków możemy z góry ograniczyć
* **sekcja oczekiwania** (waiting section) - fragment metody lock(), którego nie możemy ograniczyć z góry (np. pętla w której wątek czeka na zwolnienie sekcji krytycznej)

**Aby lock był poprawny musi zachodzić:**
- niezakleszczenie
- niezagłodzenie
- wzajemne wykluczanie

Notacje wielokrotnych wydarzeń: