Τι είναι ένα deadlock, και πώς το αποτρέπετε, το αποφεύγετε ή το ανιχνεύετε;

Question

IT Interview Practice · Accepted Answer

Ένα **deadlock (αδιέξοδο)** είναι μια κατάσταση όπου δύο ή περισσότερα νήματα είναι το καθένα **μπλοκαρισμένο για πάντα**, με το καθένα να περιμένει έναν πόρο που κρατά ένα άλλο. Τίποτα δεν προχωρά.

## Οι τέσσερις αναγκαίες συνθήκες (Coffman)

Και οι τέσσερις πρέπει να ισχύουν ταυτόχρονα — αφαιρέστε οποιαδήποτε μία και το deadlock είναι αδύνατο:

```text
1. Mutual exclusion   → a resource is held exclusively (only one holder at a time)
2. Hold and wait      → a thread holds one resource while waiting to acquire another
3. No preemption      → resources can't be forcibly taken; only released voluntarily
4. Circular wait      → a cycle: T1 waits for R2 (held by T2), T2 waits for R1 (held by T1)
```

```text
   T1 ──holds──▶ R1        T1 wants R2 ──▶ (held by T2)
   T2 ──holds──▶ R2        T2 wants R1 ──▶ (held by T1)   ← cycle = deadlock
```

## Αντιμετώπιση του deadlock

- **Πρόληψη (prevention)** — σχεδιάστε έτσι ώστε μία συνθήκη να μην μπορεί ποτέ να ισχύσει. Το πιο πρακτικό: σκοτώστε το **circular wait** επιβάλλοντας μια **καθολική σειρά locking (global lock ordering)** (αποκτάτε πάντα το A πριν το B). Ή επιτεθείτε στο **hold-and-wait** αποκτώντας όλα τα απαραίτητα locks ταυτόχρονα.
- **Αποφυγή (avoidance)** — παραχωρήστε ένα αίτημα μόνο αν το σύστημα παραμένει σε μια "ασφαλή" κατάσταση όπου κάθε νήμα μπορεί ακόμη να ολοκληρώσει (ο **αλγόριθμος του Τραπεζίτη — Banker's algorithm**). Χρειάζεται εκ των προτέρων τις μέγιστες ανάγκες πόρων κάθε νήματος, οπότε σπάνια χρησιμοποιείται στην πράξη.
- **Ανίχνευση & ανάκαμψη (detection & recovery)** — αφήστε τα deadlocks να συμβούν, σαρώστε περιοδικά το **wait-for graph** για κύκλο, και μετά ανακάμψτε σκοτώνοντας ή κάνοντας rollback ένα θύμα. Οι βάσεις δεδομένων κάνουν ακριβώς αυτό: ανιχνεύουν deadlocks και ματαιώνουν μια συναλλαγή με σφάλμα "deadlock victim".
- **Αγνόηση (ο "αλγόριθμος της στρουθοκαμήλου")** — αν τα deadlocks είναι σπάνια, απλώς κάντε επανεκκίνηση· πολλά OS το αποδέχονται αυτό για ορισμένους πόρους.

## Γιατί έχει σημασία

Το deadlock είναι κλασικό θέμα συνέντευξης επειδή το πλαίσιο των τεσσάρων συνθηκών είναι ένα ακριβές διαγνωστικό εργαλείο: δεδομένου ενός κολλήματος (hang), μπορείτε να ρωτήσετε "ποια συνθήκη μπορώ να σπάσω;" Στα πραγματικά συστήματα η προτιμώμενη απάντηση είναι η **συνεπής σειρά locking** (που αποτρέπει το circular wait) — ένας κανόνας που εφαρμόζετε κάθε φορά που παίρνετε περισσότερα από ένα locks. Η αναγνώριση ότι η βάση δεδομένων σας πετά σφάλματα deadlock-victim, και η γνώση ότι απλώς πρέπει να ξαναδοκιμάσετε (retry) εκείνη τη συναλλαγή, είναι μια άμεση πρακτική εφαρμογή.

Οι τέσσερις αναγκαίες συνθήκες (Coffman)

Αντιμετώπιση του deadlock

Γιατί έχει σημασία

Σχετικές ερωτήσεις