Teorija
Graf dodjele resursa
Deadlock (potpuni zastoj) je trajno blokiranje skupa procesa koji se natječu za resurse ili komuniciraju: svaki čeka događaj koji može izazvati samo neki drugi proces iz istog skupa. Reusable resources (ponovno upotrebljivi resursi), npr. uređaji, datoteke i semafori, nakon korištenja se vraćaju; consumable resources (potrošni resursi), npr. poruke i prekidi, nastaju i nestaju (na ovoj stranici samo prvi). Stanje se crta kao resource allocation graph (graf dodjele resursa): proces je krug, resurs pravokutnik s jednom točkom po jedinici, brid P → R je zahtjev koji čeka, a brid od točke jedinice do P dodjela. Kad svaki resurs ima jednu jedinicu, graf se sažima u wait-for graph (graf čekanja) među samim procesima. Kartica RAG izvodi sinkrone runde: u svakom taktu svaki živi proces izvede jednu operaciju svoje skripte, redom indeksa, pa se ishod ne mijenja od pokretanja do pokretanja; stvarno preplitanje prikazuje Sinkronizacija, a joint progress diagram (dijagram zajedničkog napretka) iz udžbenika ovdje se ne crta.
Resource allocation graph
Deadlock is the permanent blocking of a set of processes that either compete for system resources or communicate with each other: each process waits for an event that only another process of the same set can cause. Reusable resources, such as devices, files and semaphores, are returned after use; consumable resources, such as messages and interrupts, are produced and consumed (this page uses only the former). The state is drawn as a resource allocation graph: a process is a circle, a resource a rectangle with one dot per unit, an edge P → R is a pending request and an edge from a unit dot to P is an allocation. When every resource has one unit, the graph reduces to a wait-for graph among the processes alone. The RAG tab runs synchronous rounds: in every tick each live process performs one operation of its script, in index order, so the outcome is the same from run to run; real interleaving is shown on the Synchronization page, and the textbook's joint progress diagram is not drawn here.
Četiri uvjeta
Stallings navodi tri nužna uvjeta: mutual exclusion (međusobno isključivanje), resurs u jednom trenutku koristi samo jedan proces; hold and wait (drži i čeka), proces drži dodijeljene resurse dok čeka nove; no preemption (nema preempcije), resurs se procesu ne može oduzeti. Oni omogućuju zastoj, ali ga ne uzrokuju. Tek četvrti, circular wait (kružno čekanje), zatvoren lanac procesa u kojem svaki drži resurs koji traži sljedeći, uz prva tri čini uvjete i dovoljnima. Tanenbaum & Bos (prema Coffmanu) navode sva četiri kao jednake uvjete. Ciklus u grafu dokazuje zastoj samo kad svaki resurs ima jednu jedinicu; s više jedinica ciklus može postojati bez zastoja (scenarij „Ciklus nije zastoj”), pa se odlučuje algoritmom otkrivanja.
Four conditions
Stallings lists three necessary conditions: mutual exclusion, only one process may use a resource at a time; hold and wait, a process holds allocated resources while it waits for new ones; no preemption, no resource can be forcibly taken away from a process. They make a deadlock possible but do not cause it. Only the fourth, circular wait, a closed chain of processes in which each holds a resource that the next one requests, makes the conditions sufficient together with the first three. Tanenbaum & Bos (after Coffman) list all four as equal conditions. A cycle in the graph proves a deadlock only when every resource has one unit; with several units a cycle can exist without a deadlock (scenario “A cycle is not a deadlock”), so the detection algorithm decides.
Sprečavanje
Deadlock prevention (sprečavanje) unaprijed isključuje jedan uvjet. Međusobno isključivanje ne može se ukloniti kad resurs to traži. Hold and wait se uklanja tako da proces sve što treba traži odjednom i čeka dok sve ne bude slobodno (politika „Sve odjednom”): resursi dugo stoje neiskorišteni, a proces mora unaprijed znati što će trebati. No preemption se uklanja tako da proces kojem je zahtjev odbijen otpusti sve što drži i kasnije ponovno traži (politika „Povlačenje”), ili tako da operacijski sustav oduzme resurs; to ima smisla samo za resurse čije se stanje može spremiti i vratiti, poput procesora. Circular wait se uklanja linearnim poretkom vrsta resursa: proces smije tražiti samo resurs višeg broja od onih koje drži (politika „Poredak resursa”; ovdje se proces koji prekrši poredak prekida).
Prevention
Deadlock prevention rules out one condition in advance. Mutual exclusion cannot be removed when a resource requires it. Hold and wait is removed by having a process request everything it needs at once and wait until all of it is free (the “All at once” policy): resources stay unused for a long time, and a process must know in advance what it will need. No preemption is removed by having a process whose request is refused release everything it holds and request it again later (the “Backoff” policy), or by having the operating system take the resource away; this makes sense only for resources whose state can be saved and restored, such as the processor. Circular wait is removed by a linear ordering of resource types: a process may request only a resource with a higher number than those it holds (the “Resource ordering” policy; here a process that breaks the order is aborted).
Izbjegavanje: bankarev algoritam
Deadlock avoidance (izbjegavanje) dopušta sva tri uvjeta, ali svaki zahtjev odlučuje tako da zastoj ne bude moguć. Process initiation denial (uskraćivanje pokretanja procesa) pokreće novi proces samo ako je R ≥ C(n+1) + zbroj potraživanja već pokrenutih procesa, tj. ako bi resursa bilo dovoljno i kad bi svi tražili svoj maksimum; to je vrlo oprezno (sl. 6.7 dopušta samo P1 i P2). Resource allocation denial (uskraćivanje dodjele resursa) je banker's algorithm (bankarev algoritam): uz vektor resursa R, claim matrix (matrica potraživanja) C, allocation matrix (matrica dodjele) A i available vector (vektor raspoloživih resursa) V = R − (zbroj redaka A), zahtjev se probno dodijeli i provjeri je li stanje safe state (sigurno stanje): postoji li poredak u kojem svaki proces može dobiti ostatak potraživanja C − A i završiti. Provjera redom ispituje najniži neoznačeni proces i nakon svakog uspjeha kreće ponovno od najnižeg, pa za sl. 6.7 daje P2, P1, P3, P4. Unsafe state (nesigurno stanje) nije zastoj, nego stanje u kojem zastoj više nije isključen, pa se zahtjev odbija i proces blokira (stanje Blocked, vidi Procesi). Ograničenja: potraživanja moraju biti poznata unaprijed, procesi neovisni, broj resursa stalan, a proces ne smije završiti držeći resurse.
Avoidance: the banker's algorithm
Deadlock avoidance allows the first three conditions but decides every request so that a deadlock cannot occur. Process initiation denial starts a new process only if R ≥ C(n+1) + the sum of the claims of the processes already started, that is, if there would be enough resources even if all of them requested their maximum; this is very cautious (Fig. 6.7 admits only P1 and P2). Resource allocation denial is the banker's algorithm: with the resource vector R, the claim matrix C, the allocation matrix A and the available vector V = R − (sum of the rows of A), a request is allocated tentatively and the algorithm checks whether the result is a safe state: whether there is an order in which every process can get the rest of its claim, C − A, and finish. The check examines the lowest unmarked process and after every success starts again from the lowest one, so for Fig. 6.7 it gives P2, P1, P3, P4. An unsafe state is not a deadlock but a state in which a deadlock is no longer ruled out, so the request is denied and the process blocks (the Blocked state, see Processes). Restrictions: the claims must be known in advance, the processes must be independent, the number of resources must be fixed, and no process may exit while it holds resources.
Otkrivanje i oporavak
Deadlock detection (otkrivanje) ne ograničava zahtjeve, nego povremeno traži zastoj. Stallingsov algoritam koristi matricu zahtjeva Q: prvo označi procese čiji je redak u A nula (ništa ne drže, pa ne mogu biti dio zastoja), zatim postavi W = V i označava proces čiji je redak Q ≤ W, dodajući njegovu dodjelu u W (kao da završi i otpusti). Neoznačeni procesi su u zastoju. Tanenbaum & Bos kreću sa svim procesima neoznačenima, pa u sl. 6.10 prijave i P4, koji ništa ne drži, ali ne može dobiti što traži. Recovery (oporavak) ima četiri strategije: prekinuti sve procese u zastoju; vratiti ih na checkpoint (kontrolna točka) i ponovno pokrenuti (zastoj se može ponoviti); prekidati jednog po jednog dok zastoj ne nestane; oduzimati resurse jedan po jedan. Žrtva se bira po trošku (potrošeno vrijeme, preostali rad, prioritet, broj resursa); ovdje je žrtva proces s najmanjom ukupnom dodjelom, a kod izjednačenja manji indeks.
Detection and recovery
Deadlock detection does not limit requests but looks for a deadlock periodically. Stallings's algorithm uses a request matrix Q: it first marks each process whose row in A is zero (it holds nothing, so it cannot be part of a deadlock), then sets W = V and marks a process whose row of Q is ≤ W, adding its allocation to W (as if it finished and released it). The unmarked processes are deadlocked. Tanenbaum & Bos start with every process unmarked, so in Fig. 6.10 they also report P4, which holds nothing but cannot get what it requests. Recovery has four strategies: abort all deadlocked processes; back them up to a checkpoint and restart them (the deadlock may recur); abort them one at a time until the deadlock disappears; preempt resources one at a time. The victim is chosen by cost (processor time used, work remaining, priority, number of resources); here the victim is the process with the least total allocation, and in a tie the lower index.
Filozofi za stolom i integrirana strategija
Dining philosophers problem (problem filozofa za stolom): pet filozofa, pet vilica, svakom trebaju obje susjedne. Naivno rješenje (sl. 6.12) u kojem svatko uzme lijevu pa desnu vilicu upada u zastoj kad svi istodobno uzmu lijevu. Soba za četiri (sl. 6.13) uklanja kružno čekanje jer za stolom istodobno sjede najviše četvorica; monitor (sl. 6.14) dodjeljuje vilice unutar monitora s uvjetnim varijablama ForkReady; poredak resursa (prvo vilica manjeg broja) razbija krug jer P4 prvo traži F0. Bez zastoja još uvijek može doći do starvation (izgladnjivanje), vidi Raspoređivanje, a isti problem nastaje među dretvama, vidi Dretve. Stallingsova integrirana strategija (§6.5) dijeli resurse u klase, između klasa koristi poredak resursa, a unutar svake klase najprikladniju metodu: za prostor za razmjenu (swappable space) sprečavanje tako da se sve traži odjednom (moguće je i izbjegavanje); za resurse procesa (uređaji, datoteke) izbjegavanje; za glavnu memoriju sprečavanje preempcijom; za unutarnje resurse sustava poredak resursa.
Dining philosophers and an integrated strategy
Dining philosophers problem: five philosophers, five forks, and each philosopher needs both adjacent forks. The naive solution (Fig. 6.12), in which everyone picks up the left fork and then the right one, deadlocks when all of them pick up their left fork at the same time. A room for four (Fig. 6.13) removes circular wait because at most four sit at the table at a time; a monitor (Fig. 6.14) allocates the forks inside the monitor with the condition variables ForkReady; resource ordering (the lower-numbered fork first) breaks the circle because P4 asks for F0 first. Even without deadlock, starvation is still possible, see Scheduling, and the same problem arises among threads, see Threads. Stallings's integrated strategy (Section 6.5) groups resources into classes, uses resource ordering between the classes and the most suitable method within each class: for swappable space, prevention by requesting everything at once (avoidance is also possible); for process resources (devices, files), avoidance; for main memory, prevention by preemption; for internal system resources, resource ordering.
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 6 Concurrency: Deadlock and Starvation (§6.1 načela, sl. 6.5 i 6.6; §6.2 sprečavanje; §6.3 izbjegavanje, sl. 6.7 i 6.8; §6.4 otkrivanje, sl. 6.10; §6.5 integrirana strategija; §6.6 filozofi, sl. 6.12–6.14); alternativno Tanenbaum & Bos, Modern Operating Systems, 5. izd., pogl. 6 Deadlocks (§6.2, 6.4–6.6); filozofi u 4. izd. §2.5.1.Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 6 Concurrency: Deadlock and Starvation (sec. 6.1 principles, Figs. 6.5 and 6.6; sec. 6.2 prevention; sec. 6.3 avoidance, Figs. 6.7 and 6.8; sec. 6.4 detection, Fig. 6.10; sec. 6.5 integrated strategy; sec. 6.6 dining philosophers, Figs. 6.12–6.14); alternatively Tanenbaum & Bos, Modern Operating Systems, 5th ed., ch. 6 Deadlocks (sec. 6.2, 6.4–6.6); dining philosophers in the 4th ed., sec. 2.5.1.