Vlasništvo nad resursima i izvođenje

Stallings u procesu razdvaja dvije stvari: resource ownership (vlasništvo nad resursima: adresni prostor sa slikom procesa, otvorene datoteke, uređaji) i scheduling/execution (raspoređivanje i izvođenje). Jedinica koja se raspoređuje je thread (dretva), a jedinica koja posjeduje resurse je process (proces). U procesu s više dretvi (sl. 4.1–4.2) svi dijele kod, podatke, heap (gomila) i otvorene datoteke, a svaka dretva ima vlastiti thread control block (TCB, upravljački blok dretve) sa stanjem, PC-om i registrima te vlastiti stack (stog). Tanenbaum & Bos to prikazuju tablicom stavki po procesu i po dretvi. Na crtežu „Proces P” gornja traka je zajednička, a stupci su dretve: kad jedna dretva upiše counter, ostale vide novu vrijednost jer postoji samo jedna kopija. Proces Q ima vlastiti adresni prostor, pa i vlastiti counter.

Prednosti, stanja i operacije

Stallings navodi četiri prednosti dretvi: nova dretva u postojećem procesu stvara se mnogo brže od novog procesa, brže i završava, promjena između dretvi istog procesa brža je od process switch (promjena konteksta) među procesima, a dretve istog procesa komuniciraju kroz zajedničku memoriju bez pozivanja jezgre. Ključna stanja dretve su Running (izvodi se), Ready (spremna) i Blocked (blokirana); suspendiranje je svojstvo procesa, pa suspendiranje procesa suspendira sve njegove dretve. Četiri osnovne operacije su Spawn (stvaranje dretve s vlastitim registrima i stogom), Block (dretva čeka događaj, procesor prelazi na drugu spremnu dretvu), Unblock (događaj se dogodio, dretva je ponovno spremna) i Finish (završetak, registri i stog se oslobađaju). U dnevniku su to oznake SPAWN, BLOCK, UNBLOCK i FINISH.

Korisničke dretve (ULT)

Kod user-level threads (ULT, korisničke dretve; sl. 4.5a) dretvama upravlja threads library (knjižnica dretvi) u korisničkom prostoru, a jezgra vidi samo proces. Promjena dretve ne traži mode switch (promjena načina rada), aplikacija sama bira raspoređivanje, a knjižnica radi na bilo kojem OS-u. Nedostaci: blocking system call (blokirajući poziv) jedne dretve blokira cijeli proces, a više dretvi istog procesa ne može raditi na više procesora (scenariji „ULT: blokirajući poziv blokira cijeli proces” i „Dva procesora”). Zaobilazno rješenje je jacketing (omotavanje): umjesto blokirajućeg poziva knjižnica pozove omotač koji provjeri uređaj i, ako bi poziv blokirao, blokira samo tu dretvu i prebaci se na drugu.

Sl. 4.6 pokazuje da se stanje dretve u knjižnici i stanje procesa u jezgri mogu razlikovati: (b) nakon blokirajućeg poziva proces je Blocked, a dretva je u knjižnici i dalje Running; (c) kad procesu istekne kvant, proces je Ready, a dretva i dalje Running; (d) dretva koja čeka drugu dretvu (ovdje mutex) je Blocked u knjižnici, a proces Running. Tablica „Stanje u knjižnici i u jezgri” to prikazuje uživo. Knjižnica u simulatoru je kooperativna: dretvu mijenja samo pri yield, čekanju na mutex, omotanom pozivu ili završetku dretve. To je izbor modela; neke stvarne knjižnice dretvu prekidaju i signalom timera.

Jezgrene dretve, kombinirani pristup i tablica 4.1

Kod kernel-level threads (KLT, jezgrene dretve; sl. 4.5b) jezgra vodi kontekst svake dretve i raspoređuje ih zasebno: kad jedna blokira, jezgra pokreće drugu dretvu istog procesa, a dretve mogu raditi istodobno na više procesora. Cijena je da svaka promjena dretve prolazi kroz jezgru. Combined approach (kombinirani pristup; sl. 4.5c) stvara dretve u knjižnici i preslikava ih na manji ili jednak broj lightweight processes (LWP, laki procesi) koje raspoređuje jezgra. Dretva vezana na LWP blokira zajedno s njim; kad dretva završi, isti LWP bez promjene u jezgri preuzima sljedeću spremnu dretvu. S jednim LWP-om ponašanje je kao kod ULT-a, a s jednim LWP-om po dretvi kao kod KLT-a.

Tablica 4.1 daje povijesne latencije u mikrosekundama, izmjerene na VAX-u s jednim procesorom: Null Fork 34 (ULT), 948 (KLT) i 11 300 (proces), Signal-Wait 37, 441 i 1 840. KLT je za red veličine sporiji od ULT-a jer ulazi u jezgru, a proces još za red veličine jer mijenja i adresni prostor. Oprez s nazivima: u Stallingsovoj tablici 4.2 oznaka M:1 znači mnogo dretvi u jednom procesu, a ne preslikavanje „many-to-one” iz drugih knjiga. Tanenbaum & Bos opisuju i hibridne implementacije, a u 4. izdanju i scheduler activations (aktivacije raspoređivača), gdje jezgra javi knjižnici da je dretva blokirala, pa knjižnica može pokrenuti drugu; 5. izdanje ih više ne navodi.

Dalje

Dretve istog procesa dijele podatke, pa dva istodobna upisa u counter mogu izgubiti ažuriranje: to je race condition (utrka), vidi Sinkronizacija. Kojim redom jezgra bira dretve ili procese (ovdje RR s kvantom) tema je stranice Raspoređivanje, a slika procesa i promjena konteksta opisani su na stranici Procesi. Blokirajuće čitanje korak po korak prikazuje Sistemski pozivi, a put jednog čitanja kroz cijeli sustav Put jednog poziva.

Resource ownership and execution

Stallings separates two things in a process: resource ownership (an address space holding the process image, open files, devices) and scheduling/execution. The unit that is scheduled is the thread, and the unit that owns resources is the process. In a multithreaded process (Figs. 4.1–4.2) all threads share the code, data, heap and open files, while each thread has its own thread control block (TCB) with its state, PC and registers, and its own stack. Tanenbaum & Bos show this as a table of per-process and per-thread items. In the “Process P” drawing the top band is shared and the columns are the threads: when one thread writes counter, the others see the new value because there is only one copy. Process Q has its own address space, and so its own counter.

Benefits, states and operations

Stallings lists four benefits of threads: a new thread in an existing process is created much faster than a new process, it also terminates faster, switching between threads of the same process is faster than a process switch, and threads of the same process communicate through shared memory without invoking the kernel. The key thread states are Running, Ready and Blocked; suspension is a process-level concept, so suspending a process suspends all its threads. The four basic operations are Spawn (a thread is created with its own registers and stack), Block (the thread waits for an event, and the processor moves to another ready thread), Unblock (the event has occurred, and the thread is ready again) and Finish (the thread ends; its registers and stack are freed). In the log these are the tags SPAWN, BLOCK, UNBLOCK and FINISH.

User-level threads (ULT)

With user-level threads (ULT; Fig. 4.5a) the threads are managed by a threads library in user space, and the kernel sees only the process. A thread switch needs no mode switch, the application chooses its own scheduling, and the library runs on any OS. The drawbacks: a blocking system call by one thread blocks the whole process, and several threads of the same process cannot run on several processors (scenarios “ULT: a blocking call blocks the whole process” and “Two processors”). The workaround is jacketing: instead of the blocking call, the library calls a jacket that checks the device and, if the call would block, blocks only that thread and switches to another.

Fig. 4.6 shows that the state of a thread in the library and the state of the process in the kernel can differ: (b) after a blocking call the process is Blocked, while in the library the thread is still Running; (c) when the process's time slice expires, the process is Ready, while the thread is still Running; (d) a thread that waits for another thread (here for a mutex) is Blocked in the library, while the process is Running. The table “State in the library and in the kernel” shows this live. The library in the simulator is cooperative: it switches threads only on yield, a mutex wait, a jacketed call or the end of a thread. That is a choice of the model; some real libraries also preempt a thread with a timer signal.

Kernel-level threads, the combined approach and Table 4.1

With kernel-level threads (KLT; Fig. 4.5b) the kernel keeps the context of every thread and schedules each one separately: when one blocks, the kernel runs another thread of the same process, and threads can run at the same time on several processors. The price is that every thread switch goes through the kernel. The combined approach (Fig. 4.5c) creates threads in the library and maps them onto a smaller or equal number of lightweight processes (LWPs), which the kernel schedules. A thread bound to an LWP blocks together with it; when a thread finishes, the same LWP takes the next ready thread without a kernel switch. With one LWP the behavior is like ULT, and with one LWP per thread like KLT.

Table 4.1 gives historical latencies in microseconds, measured on a uniprocessor VAX: Null Fork 34 (ULT), 948 (KLT) and 11,300 (process), Signal-Wait 37, 441 and 1,840. KLT is an order of magnitude slower than ULT because it enters the kernel, and a process is another order of magnitude slower because it also changes the address space. A word of caution about names: in Stallings's Table 4.2 the label M:1 means many threads in one process, not the “many-to-one” mapping of other books. Tanenbaum & Bos also describe hybrid implementations and, in the 4th edition, scheduler activations, where the kernel tells the library that a thread has blocked, so the library can run another; the 5th edition no longer covers them.

Further

Threads of the same process share data, so two concurrent writes to counter can lose an update: that is a race condition, see Synchronization. The order in which the kernel picks threads or processes (here RR with a quantum) is the topic of the Scheduling page, and the process image and the process switch are described on the Processes page. A blocking read step by step is shown on the System calls page, and the path of one read through the whole system on the Journey of a call page.