---
# System prepended metadata

title: L2 - zarys teoretyczny (bez wyprowadzenia wzorów)

---

# 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**

![](https://i.imgur.com/zpcwltW.png)

* **Algorytm Petersona**:
```java 
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ń:
![](https://i.imgur.com/esV6feR.png)
