Teorija
Literatura: Stallings, Operating Systems: Internals and Design Principles, 9. izd., pogl. 9 (odj. 9.1–9.2); alternativno Tanenbaum & Bos, Modern Operating Systems, pogl. 2 (4. izd. odj. 2.4; 5. izd. odj. 2.5.2–2.5.3).Reading: Stallings, Operating Systems: Internals and Design Principles, 9th ed., ch. 9 (sec. 9.1–9.2); alternatively Tanenbaum & Bos, Modern Operating Systems, ch. 2 (4th ed. sec. 2.4; 5th ed. sec. 2.5.2–2.5.3).
Vrste raspoređivanja
Scheduling (raspoređivanje) određuje koji proces kada dobiva procesor. Long-term scheduling (dugoročno raspoređivanje) prima nove procese u sustav, medium-term scheduling (srednjoročno raspoređivanje) odlučuje koji su u memoriji, a short-term scheduling (kratkoročno raspoređivanje) bira sljedeći spreman proces, npr. nakon clock interrupt (prekid sata). Ovdje se simulira kratkoročna razina: jedan procesor, procesi koji samo računaju i promjena konteksta bez troška. Stanja Ready (spreman) i Running (izvodi se) prikazuje modul Procesi.
Types of scheduling
Scheduling decides which process gets the processor and when. Long-term scheduling admits new processes to the system, medium-term scheduling decides which of them are in memory, and short-term scheduling picks the next ready process, for example after a timer interrupt. This page simulates the short-term level: one processor, processes that only compute, and process switches that cost no time. The Ready and Running states are shown on the Processes page.
Mjere i način odlučivanja
Proces traži service time (vrijeme posluživanja) Ts. Turnaround time (vrijeme obrtanja) je Tr = Tf − dolazak, a normalized turnaround time (normalizirano vrijeme obrtanja) Tr/Ts: 1,00 je idealno. Slijede waiting time (vrijeme čekanja) Tr − Ts, response time (vrijeme odziva) i throughput (propusnost). Politiku opisuju selection function (funkcija odabira), uz w = čekanje, e = izvođenje, s = posluživanje, i decision mode (način odlučivanja): s preemption (preempcija) ili bez nje. Preempciju pokreće timer interrupt (prekid timera), vidi Prekidi: prekid timera.
Politike prema Stallingsovoj tablici 9.3
| Politika | Funkcija odabira | Način odlučivanja | Starvation (izgladnjivanje) |
|---|
| FCFS | max[w] | bez preempcije | ne |
|---|
| RR | konstanta | preempcija na isteku kvanta | ne |
|---|
| SPN | min[s] | bez preempcije | moguće |
|---|
| SRT | min[s − e] | preempcija pri dolasku | moguće |
|---|
| HRRN | max((w + s)/s) | bez preempcije | ne |
|---|
| Feedback | vidi tekst | preempcija na isteku kvanta | moguće |
|---|
Measures and decision mode
A process requires a service time Ts. Turnaround time is Tr = Tf − arrival, and normalized turnaround time is Tr/Ts: 1.00 is ideal. Then come waiting time Tr − Ts, response time and throughput. A policy is described by its selection function, with w = time spent waiting, e = time spent in execution, s = total service time, and by its decision mode: preemptive or nonpreemptive. Preemption is triggered by the timer interrupt; see Interrupts: the timer interrupt.
Policies after Stallings's Table 9.3
| Policy | Selection function | Decision mode | Starvation |
|---|
| FCFS | max[w] | nonpreemptive | no |
|---|
| RR | constant | preemptive (at time quantum) | no |
|---|
| SPN | min[s] | nonpreemptive | possible |
|---|
| SRT | min[s − e] | preemptive (at arrival) | possible |
|---|
| HRRN | max((w + s)/s) | nonpreemptive | no |
|---|
| Feedback | see text | preemptive (at time quantum) | possible |
|---|
FCFS, RR, SPN, SRT i HRRN
FCFS poslužuje redom dolaska, pa kratki proces iza dugih dugo čeka (E: Tr/Ts 6,00). RR daje time quantum (kvant) q: mali kvant znači brz odziv, ali mnogo prekida timera; kvant dulji od svakog posluživanja daje FCFS (sl. 9.6). SPN (Tanenbaum: SJF) bira najkraći s, a SRT (Tanenbaum: SRTN) to radi s preempcijom i daje najmanji srednji Tr; obje trebaju trajanje unaprijed, a dugi procesi mogu gladovati. HRRN bira najveći response ratio (omjer odziva) R = (w + s)/s, koji dugom procesu raste dok čeka.
FCFS, RR, SPN, SRT and HRRN
FCFS serves processes in order of arrival, so a short process behind long ones waits a long time (E: Tr/Ts 6.00). RR gives each process a time quantum q: a small quantum means quick response but many timer interrupts; a quantum longer than every service time gives FCFS (Fig. 9.6). SPN (Tanenbaum: SJF) picks the smallest s, and SRT (Tanenbaum: SRTN) does the same with preemption and gives the lowest mean Tr; both need the service time in advance, and long processes may starve. HRRN picks the highest response ratio R = (w + s)/s, which grows for a long process while it waits.
Feedback
Feedback (multilevel feedback, višerazinski redovi; sl. 9.10) ne treba trajanje: novi proces ulazi u RQ0, a nakon svakog isteka kvanta spušta se red niže. Radi glava najvišeg nepraznog reda; unutar reda FCFS, u najnižem RR. Inačica q = 2^i daje nižim redovima dulji kvant. Kratki procesi mogu stalno pretjecati duge; Stallings kao lijek navodi podizanje procesa koji dugo čeka. Pravila izjednačenja su važna: da se proces spušta i kad je sam, Tf bi bili 11, 20, 16, 19, 10 umjesto brojki iz tablice 9.5.
Feedback
Feedback (multilevel feedback; Fig. 9.10) needs no service time: a new process enters RQ0 and moves one queue down after each expired quantum. The head of the highest nonempty queue runs; FCFS within a queue, RR in the lowest one. The variant q = 2^i gives lower queues a longer quantum. Short processes can keep overtaking long ones; as a remedy Stallings mentions promoting a process that has waited long. The tie-breaking rules matter: if a process moved down even when it was alone, Tf would be 11, 20, 16, 19, 10 instead of the numbers in Table 9.5.
Prioriteti i starenje
Kod raspoređivanja po prioritetu (sl. 9.4) RQ0 je najviši red; ovdje procesor dobiva najmanji broj prioriteta. Dok stižu važniji procesi, nevažan proces čeka neograničeno (scenarij „Izgladnjivanje”). Lijek je aging (starenje). Pravilo ovog simulatora (naše, ne Stallingsovo): efektivni prioritet = max(0, osnovni − cijeli dio od (čekanje / k)), zamrznut dok proces radi, a prekinuti proces vraća se na osnovni. Tanenbaum riječju aging zove i procjenu trajanja iz prošlih mjerenja, što je drugi pojam. Vidi i Sinkronizacija i Dretve.
Priorities and aging
In priority scheduling (Fig. 9.4) RQ0 is the highest queue; here the processor goes to the lowest priority number. While higher-priority processes keep arriving, a low-priority process waits indefinitely (the “Starvation” scenario). The remedy is aging. The rule in this simulator (ours, not Stallings's): effective priority = max(0, base − integer part of (waiting / k)), frozen while the process runs, and a preempted process returns to its base priority. Tanenbaum also uses the word aging for estimating the run time from past measurements, which is a different concept. See also Synchronization and Threads.
Usporedba politika
Tablica 9.5 i sl. 9.14–9.15 pokazuju da nema jedinstvenog pobjednika: SRT i SPN štite kratke procese, ali trebaju trajanje unaprijed; RR i Feedback ovise o kvantu; HRRN je kompromis bez preempcije. Gantt chart (Gantt dijagram) ispod simulacije prikazuje raspored po jedinicama; tipka 8 dodaje dvije politike na istu vremensku os. Kako se prekid, raspoređivanje i U/I slažu u jednom zahtjevu, pokazuje Put jednog poziva.
Comparing the policies
Table 9.5 and Figs. 9.14–9.15 show that there is no single winner: SRT and SPN protect short processes but need the service time in advance; RR and Feedback depend on the quantum; HRRN is a nonpreemptive compromise. The Gantt chart below the simulation shows the schedule unit by unit; key 8 adds two policies on the same time axis. How an interrupt, scheduling and I/O fit together in one request is shown on the Journey of a call page.