Proces, trag i dispečer

Process (proces) je program u izvođenju. Stallings ga prati kroz trace (trag), niz adresa instrukcija koje procesor izvodi za taj proces. Na jednom procesoru tragovi se isprepliću: kad proces potroši svoj time slice (vremenski odsječak) ili zatraži U/I, mali program dispatcher (dispečer) bira sljedeći proces i predaje mu procesor. Scenarij „Stallingsov trag” ponavlja sl. 3.4 i 3.7: odsječak je 6 ciklusa, dispečer radi na adresama 100–105, a od 52 ciklusa troši čak 24. Kojim redom dispečer bira procese, tema je stranice Raspoređivanje.

Modeli stanja: dva, pet i sedam

U modelu s dva stanja (sl. 3.5) proces je Running (izvodi se) ili Not Running (ne izvodi se); ulazi prijelazom Enter (ulaz), a mijenjaju ga Dispatch (dodjela procesora) i Pause (pauza). U redu Not Running stoje i procesi koji još čekaju U/I, pa ih dispečer mora preskakati (scenarij „Model s dva stanja”). Model s pet stanja (sl. 3.6) dodaje New (novi), Ready (spreman), Blocked (blokiran) i Exit (izlaz), s prijelazima Admit (prihvat), Timeout (istek vremena), Event Wait (čekanje na događaj), Event Occurs (događaj) i Release (otpuštanje). Prema tekstu (ne slici) roditelj može završiti dijete i iz stanja Ready ili Blocked: to je Terminate (prekidanje), na dijagramu crtkano. Tanenbaum & Bos koriste model s tri stanja (running, ready, blocked) s prijelazima označenim brojevima 1–4.

Kad su svi procesi u memoriji blokirani, procesor stoji besposlen. Tada swapping (izbacivanje) prebacuje dio procesa na disk i oslobađa mjesto za proces koji može raditi. Model sa sedam stanja (sl. 3.9b) zato dodaje Ready/Suspend (spreman/suspendiran) i Blocked/Suspend (blokiran/suspendiran) te prijelaze Suspend (suspendiranje) i Activate (aktiviranje). Biti suspendiran (slika procesa je na disku) i biti blokiran (proces čeka događaj) dva su neovisna svojstva, pa postoje sve četiri kombinacije. Scenarij „Suspendiranje zbog nedostatka memorije” pokazuje razliku: uz izbacivanje procesor ne stoji ni jedan ciklus, a u modelu s pet stanja stoji četiri. Kako se oslobođena memorija ponovno dodjeljuje, vidi Dodjela memorije.

PCB i slika procesa

Process image (slika procesa) sastoji se od korisničkog programa i podataka, korisničkog stoga i process control block (PCB, upravljački blok procesa), Stallingsove tablice 3.4 i 3.5. PCB ima tri skupine podataka: process identification (identifikacija: PID, PID roditelja, korisnik), processor state information (stanje procesora: PC, registri, SP, PSW) i process control information (kontrolne informacije: stanje, događaj koji proces čeka, redovi, roditelj i djeca, memorija, otvorene datoteke, potrošeni ciklusi). Dok proces radi, stvarne vrijednosti registara su u procesoru, a kopija u PCB-u je stara; zato je u kartici označena kao „zastarjelo” sve do sljedećeg spremanja konteksta.

Promjena načina rada i promjena konteksta

Procesor radi u user mode (korisnički način rada) ili kernel mode (jezgreni način rada). Mode switch (promjena načina rada) događa se pri svakom ulasku u jezgru i povratku iz nje, ali sam po sebi ne mijenja proces: nakon obrade prekida jezgra može nastaviti isti proces (u dnevniku „nema drugog spremnog procesa”). Process switch (promjena konteksta) moguć je kad god operacijski sustav preuzme kontrolu od procesa koji radi. Stallings to opisuje u odjeljku 3.4 When to Switch Processes (kada mijenjati proces), a tablica 3.8 navodi tri mehanizma kojima se prekida izvođenje procesa: interrupt (prekid, vanjski događaj kao timer ili završetak U/I), trap (iznimka koju izazove sama instrukcija) i supervisor call (sistemski poziv, npr. read ili fork). Promjena konteksta skuplja je od promjene načina rada i ima sedam koraka, prikazanih u panelu procesora: spremiti kontekst, ažurirati PCB, premjestiti ga u red, odabrati drugi proces, ažurirati njegov PCB, ažurirati upravljanje memorijom i vratiti kontekst. U simulatoru taj posao obavlja dispečer i traje D ciklusa. Kako ulazak u jezgru izgleda na stogu, pokazuju Prekidi i Sistemski pozivi.

UNIX: fork, exec, wait i exit

fork stvara dijete u šest koraka (Stallings 3.6): mjesto u tablici procesa, jedinstven PID, kopija slike roditelja, veći brojači za otvorene datoteke, stanje Ready i povratna vrijednost, PID djeteta roditelju i 0 djetetu. Jezgra zatim može nastaviti roditelja, prebaciti se na dijete ili na treći proces; simulator nastavlja roditelja. exec zamjenjuje program, a PID, roditelj i otvorene datoteke ostaju. Proces koji završi s exit postaje zombie (zombi; stanje Zombie u tablici 3.9): zauzima samo unos u tablici procesa dok roditelj ne pozove wait i pokupi izlazni status. Ako roditelj završi prvi, dijete postaje orphan (siroče) i posvaja ga init (PID 1), koji u petlji poziva wait; to je ponašanje POSIX-a i Linuxa. Veze roditelja i djece tvore process tree (stablo procesa). Tanenbaumova mini ljuska (sl. 1-19) spaja sve: ljuska poziva fork, dijete execve, a ljuska čeka u waitpid. Dretve istog procesa dijele jednu sliku procesa, vidi Dretve; put jednog čitanja kroz cijeli sustav prikazuje Put jednog poziva.

Process, trace and dispatcher

A process is a program in execution. Stallings follows it through its trace, the sequence of instruction addresses that the processor executes for that process. On a single processor the traces interleave: when a process uses up its time slice or requests I/O, a small program called the dispatcher selects the next process and gives it the processor. The scenario “Stallings's trace” replays Figs. 3.4 and 3.7: the time slice is 6 cycles, the dispatcher runs at addresses 100–105, and of 52 cycles it takes as many as 24. The order in which the dispatcher picks processes is the subject of the Scheduling page.

State models: two, five and seven

In the two-state model (Fig. 3.5) a process is either Running or Not Running; it comes in through the Enter transition and is moved by Dispatch and Pause. The Not Running queue also holds processes that are still waiting for I/O, so the dispatcher has to skip them (scenario “Two-state model”). The five-state model (Fig. 3.6) adds New, Ready, Blocked and Exit, with the transitions Admit, Timeout, Event Wait, Event Occurs and Release. According to the text (not the figure), a parent may also terminate a child from the Ready or Blocked state: this is Terminate, dashed in the diagram. Tanenbaum & Bos use a three-state model (running, ready, blocked) with transitions numbered 1–4.

When all processes in memory are blocked, the processor sits idle. Swapping then moves part of a process to disk and frees room for a process that can run. The seven-state model (Fig. 3.9b) therefore adds Ready/Suspend and Blocked/Suspend, and the transitions Suspend and Activate. Being suspended (the process image is on disk) and being blocked (the process waits for an event) are two independent properties, so all four combinations exist. The scenario “Suspension for lack of memory” shows the difference: with swapping the processor is not idle for a single cycle, while in the five-state model it is idle for four. How the freed memory is allocated again is shown on the Memory allocation page.

PCB and process image

The process image consists of the user program and data, the user stack and the process control block (PCB), Stallings Tables 3.4 and 3.5. The PCB holds three groups of data: process identification (PID, parent PID, user), processor state information (PC, registers, SP, PSW) and process control information (state, the event the process waits for, queues, parent and children, memory, open files, cycles used). While a process runs, the actual register values are in the processor and the copy in the PCB is out of date; that is why the card marks it “stale” until the next context save.

Mode switch and process switch

The processor runs in user mode or kernel mode. A mode switch happens on every entry into the kernel and every return from it, but by itself it does not change the process: after handling an interrupt the kernel can resume the same process (“no other ready process” in the log). A process switch may occur any time the operating system has gained control from the currently running process. Stallings describes this in Section 3.4, When to Switch Processes, and Table 3.8 lists three mechanisms for interrupting the execution of a process: interrupt (an external event such as the timer or the completion of I/O), trap (an exception caused by the instruction itself) and supervisor call (a system call, e.g. read or fork). A process switch costs more than a mode switch and has seven steps, shown in the processor panel: save the context, update the PCB, move it to a queue, select another process, update its PCB, update memory management and restore the context. In the simulator the dispatcher does this work and takes D cycles. What entering the kernel looks like on the stack is shown on the Interrupts and System calls pages.

UNIX: fork, exec, wait and exit

fork creates a child in six steps (Stallings, Section 3.6): a slot in the process table, a unique PID, a copy of the parent's image, incremented counters for open files, the Ready state, and the return value, the child's PID to the parent and 0 to the child. The kernel may then continue with the parent, switch to the child or to a third process; the simulator continues with the parent. exec replaces the program, while the PID, the parent and the open files stay. A process that ends with exit becomes a zombie (the Zombie state in Table 3.9): it holds only its process table entry until the parent calls wait and collects the exit status. If the parent terminates first, the child becomes an orphan and is adopted by init (PID 1), which calls wait in a loop; this is the POSIX and Linux behavior. The parent–child links form the process tree. Tanenbaum's mini shell (Fig. 1-19) puts it all together: the shell calls fork, the child execve, and the shell waits in waitpid. Threads of one process share a single process image, see Threads; the path of one read through the whole system is shown on the Journey of a call page.