Pregled ključnih pojmova operativnih sistema

Autor: Yueban Feiyu, izvor: https://mp.weixin.qq.com/s/G9ZqwEMxjrG5LbgYwM5ACQ

Struktura računara

Model savremenog računara zasnovan je na von Neumann-ovom modelu računara.

Prilikom rada, računar prvo iz memorije preuzima prvu instrukciju, kroz dekoder kontrolne jedinice tumači je, po zahtevu instrukcije iz memorije uzima podatke, vrši zadatu aritmetičku i logičku obradu, a zatim rezultat po adresi šalje nazad u memoriju. Zatim preuzima sledeću instrukciju i pod upravom kontrolne jedinice izvršava propisanu operaciju, i tako dalje, sve dok ne naiđe na instrukciju za zaustavljanje.

Program i podaci skladište se na isti način; instrukcije se, prema redosledu programa, korak po korak preuzimaju i automatski izvršavaju — to je osnovni model rada računara.

Pet ključnih delova računara

Kontrolna jedinica: centarni nerv računara; tumači kontrolne informacije iz programa, upravlja raspoređivanjem programa, podataka i adresa, i usklađuje rad svih delova računara, kao i pristup memoriji i periferijskim uređajima.

Aritmetičko-logička jedinica: vrši razne aritmetičke i logičke operacije nad podacima, odnosno obrađuje ih.

Memorija: skladišti program, podatke, signale i komande, i po potrebi ih stavlja na raspolaganje.

Ulaz: ulazni uređaji su važan deo računara; zajedno sa izlaznim uređajima čine periferiju. Ulazni uređaji služe za unos programa, sirovih podataka, teksta, znakova, kontrolnih komandi ili podataka prikupljenih na terenu u računar.

Najčešći ulazni uređaji su tastatura, miš, optički čitač, magnetna traka, disk jedinica, CD/DVD jedinica itd.

Izlaz: izlazni uređaji su, kao i ulazni, važan deo računara; oni daju intermediate ili konačne rezultate, podatke, znakove, tekst ili kontrolne signale. Najčešći izlazni uređaji su CRT terminal, štampač, laserski štampač, ploter, magnetna traka, disk jedinica itd.

Strukturu računara čini 5 delova:

Ulazni uređaj; izlazni uređaj; memorija; centralna procesorska jedinica; magistrala.

Memorija

U von Neumann-ovom modelu program i podaci smešteni su u linearno uređenom memorijskom prostoru koji nazivamo memorija.

Jedinica pohranjenih podataka je binarni ciferni mest, na engleskom bit; najmanja jedinica skladištenja zove se bajt, odnosno 8 bitova, engleski bajt — svaki bajt odgovara jednoj memorijskoj adresi.

Memorijske adrese numerisane su počevši od 0: prva adresa je 0, druga 1, i tako rastuće, sve do poslednje adrese, koja je za jedan manja od ukupnog broja bajtova u memoriji.

Memorija o kojoj obično govorimo jeste memorija sa slučajnim pristupom (RAM) — brzina čitanja podataka sa bilo koje adrese je ista, kao i brzina upisa podataka na bilo koju adresu.

CPU

U von Neumann-ovom modelu CPU je zadužen za upravljanje i računanje. Kako bi olakšao obračun većih vrednosti, CPU u jednom koraku može obraditi više bajtova podataka.

• Ako CPU u jednom koraku obrađuje 4 bajta, nazivamo ga 32-bitnim CPU;

• ako obrađuje 8 bajtova, nazivamo ga 64-bitnim CPU.

Brojevi 32 i 64 ovde označavaju širinu CPU-a (bit-width).

Zašto je CPU ovako projektovan?

Zato što je najveći opseg koji jedan bajt može da predstavi 0~255.

Na primer, za izračunavanje 20000*50 vrednost prelazi maksimalni opseg jednog bajta.

Zato CPU mora da podrži obračun sa više bajtova zajedno. Što je veća širina CPU-a, to se mogu izračunavati veće vrednosti; u praksi, međutim, nije uvek potrebno računati tako velike brojeve — 32-bitni CPU može izračunati najveći celi broj od 4294967295, što je već vrlo velika vrednost.

Kontrolna jedinica i aritmetičko-logička jedinica

Unutar CPU-a kontrolna jedinica upravlja radom CPU-a, dok aritmetičko-logička jedinica vrši proračune.

Registri

Da bi CPU vršio proračune — na primer, prosti zbir dva broja — pošto je od memorije udaljen, potrebno mu je skladište u neposrednoj blizini u kojem će držati brojeve koji se upravo obrađuju.

To skladište su registri. Oni se nalaze unutar samog CPU-a, vrlo blizu kontrolne i aritmetičko-logičke jedinice, pa su izuzetno brzi.

Najčešće vrste registara:

• Opšti registri — čuvaju podatke potrebne za proračun, npr. dva broja koje treba sabrati.
• Brojač programa (program counter) — čuva memorijsku adresu sledeće instrukcije koju CPU treba da izvrši. Napomena: on ne čuva samu sledeću instrukciju (ona je još uvek u memoriji), već samo njenu adresu.
• Instrukcijski registar — čuva instrukciju na koju ukazuje brojač programa, odnosno samu instrukciju; instrukcija ostaje ovde dok se ne izvrši.

Višenivojski keš

Radi povećanja efikasnosti i smanjenja razmene podataka između CPU-a i memorije (koja usporava CPU), savremeni CPU integrišu hijerarhiju višenivojskih keševa.

CPU keš je brza memorija male premosne širine koja se nalazi između CPU-a i glavne memorije.

Pošto je brzina CPU-a znatno veća od brzine glavne memorije, direktan pristup podacima iz memorije zahteva određeno vreme čekanja. Keš čuva deo podataka koje je CPU upravo koristio ili koje koristi u petlji; kada CPU ponovo zatreba te podatke, može ih preuzeti direktno iz keša, čime se smanjuje vreme čekanja i povećava efikasnost sistema. Postoji nekoliko nivoa:

L1-Cache

L1 keš nalazi se unutar CPU-a; u poređenju sa registrima, iako je nešto udaljeniji od jezgra, znatno je jeftiniji. Veličina mu je obično od nekoliko desetina Kb do nekoliko stotina Kb, a brzina čitanja/pisanja iznosi 2~4 CPU taktova.

L2-Cache

L2 keš takođe se nalazi unutar CPU-a, ali dalje od jezgra nego L1; veći je od L1 keša. Stvarna veličina zavisi od modela CPU-a — može biti 2 MB, ili manja/veća — a brzina iznosi 10~20 CPU taktova.

L3-Cache

L3 keš je takođe unutar CPU-a, još dalje od jezgra nego L2; obično je veći od L2 keša, a brzina čitanja/pisanja iznosi 20~60 CPU taktova.

Veličina L3 keša zavisi od modela: na primer, i9 CPU ima 512 KB L1 keša, 2 MB L2 keša i 16 MB L3 keša.

Kada CPU zatreba podatak iz memorije, prvo proverava registar; ako ga nema, potražiće ga u L1 kešu, zatim u L2, pa u L3, a tek ako ga nigde nema, otići će po njega u memoriju.

Rezime:

Veličina memorijskog prostora: memorija > L3 > L2 > L1 > registar;

Brzina: registar > L1 > L2 > L3 > memorija.

Nivoi bezbednosti

Nivoi izvršavanja CPU-a

CPU ima 4 nivoa izvršavanja:

• ring0, ring1, ring2, ring3

ring0 je rezervisan za operativni sistem, dok ring3 mogu da koriste svi.

ring0 je najviši nivo izvršavanja CPU-a, zatim ring1, pa ring2 i tako dalje.

Kôd sistema (kernela) izvršava se na najvišem nivou, ring0, gde sme da koristi privilegovane instrukcije — kontroliše prekide, menja tabele stranica, pristupa uređajima i sl.

Kôd aplikacija izvršava se na najnižem nivou, ring3, gde ne sme da vrši privilegovane operacije.

Ako aplikacija to ipak mora da uradi — na primer, da pristupi disku ili upiše fajl — to mora kroz sistemski poziv (funkciju). Pri sistemskom pozivu CPU menja nivo izvršavanja sa ring3 na ring0 i skače na odgovarajuću lokaciju kernel-kôda koja obavlja taj posao; po završetku se vraća sa ring0 na ring3.

Ovaj proces se naziva promena između korisničkog i kernel režima.

Princip lokalnosti

Kada CPU pristupa memorijskim uređajima, bilo za čitanje podataka ili instrukcija, tendencija je da pristupi grupiše u neprekidnim područjima — to je princip lokalnosti.

Vremenska lokalnost (Temporal Locality):

Ako se neka informacija upravo koristi, velika je verovatnoća da će uskoro biti ponovo korišćena.

Na primer: petlje, rekurzija, višestruki pozivi metoda.

Prostorna lokalnost (Spatial Locality):

Ako se referencira neka memorijska lokacija, i lokacije u njenoj blizini biće uskoro referencirane.

Na primer: sekvencijalno izvršavani kôd, dva uzastopno kreirana objekta, nizovi i sl.

Proces izvršavanja programa

Program je zapravo niz instrukcija, pa se izvršavanje programa svodi na postepeno izvršavanje svake instrukcije; instrukcije izvršava CPU.

Proces izvršavanja programa u CPU-u:

• Prvi korak: CPU pročita vrednost brojača programa — to je memorijska adresa instrukcije. Zatim kontrolna jedinica CPU-a postavlja adresnu magistralu na željenu memorijsku adresu, obaveštava memorijski uređaj da pripremi podatke, a kada su podaci spremni, instrukcija se preko magistrale podataka prosleđuje CPU-u, koji je smešta u instrukcijski registar.
• Drugi korak: CPU analizira instrukciju u instrukcijskom registru, utvrđuje njen tip i parametre; ako je to instrukcija za proračun, prosleđuje je aritmetičko-logičkoj jedinici, a ako je instrukcija za skladištenje, predaje je kontrolnoj jedinici.
• Treći korak: po izvršenju instrukcije, vrednost brojača programa se uvećava, čime ukazuje na sledeću instrukciju. Veličina tog uvećanja zavisi od širine CPU-a: npr. na 32-bitnom CPU-u instrukcija je duga 4 bajta i zauzima 4 memorijske adrese, pa se brojač programa uvećava za 4.

Ukratko: prilikom izvršavanja programa CPU na osnovu adrese u brojaču programa iz memorije preuzima instrukciju koju treba izvršiti, smešta je u instrukcijski registar, izvršava, a zatim na osnovu dužine instrukcije uvećava adresu i prelazi na sledeću.

Ciklus od čitanja instrukcije iz brojača programa, preko izvršenja, do sledeće instrukcije, ponavlja se sve dok se program ne završi — taj ciklus nazivamo ciklusom instrukcija CPU-a.

Magistrala

Između CPU-a, memorije i ostalih uređaja takođe je potrebna komunikacija, pa za to koristimo poseban uređaj — magistralu.

• Adresna magistrala — navodi memorijsku adresu na kojoj CPU operiše;
• Magistrala podataka — služi za čitanje i pisanje podataka u memoriji;
• Kontrolna magistrala — šalje i prima signale (prekidi, reset uređaja itd.); kada CPU primi signal, on prirodno reaguje, pri čemu je takođe potrebna kontrolna magistrala.

Kada CPU želi da pročita ili upiše memorijske podatke, obično su mu potrebne dve magistrale:

• prvo adresnom magistralom navodi memorijsku adresu;

• zatim magistralom podataka prenosi podatke;

Ulazni i izlazni uređaji

Ulazni uređaji unose podatke u računar; računar, nakon proračuna, rezultat prosleđuje spoljašnjem svetu preko izlaznih uređaja.

Ako ulazni ili izlazni uređaj želi da komunicira sa CPU-om — na primer, kada korisnik pritisne taster i CPU treba da odreaguje — koristi se kontrolna magistrala.

Osnove

Prekid

Vrste prekida

• Prema izvoru okidača, dele se na sinhroni i asinhroni prekid;

• Prema tome da li je prekid obavezan, dele se na maskirajuće i nemaskirajuće prekide.

Prekid može da okine sama instrukcija CPU-a — takav prekid nazivamo sinhroni prekid.

Sinhroni prekid ima nekoliko oblika.

• Na primer, sistemski poziv zahteva prelaz iz korisničkog u kernel režim; pritom program mora da okine prekid koji se zove klopka (Trap), nakon čega se nastavlja izvršenje sistemskog poziva.

• Još jedan oblik sinhronog prekida je greška (Fault) — obično zbog otkrivene greške koja zahteva prekid; po obradi prekida ponovo se izvršava instrukcija koja je grešku izazvala, kao npr. prekid usled nedostatka stranice o kom će biti reči kasnije.

• Konačno, postoji i izuzetak u programu; slično kao Trap, služi za obradu izuzetaka koje program baci.

Drugu vrstu prekida ne okida sam CPU, već nastaje kao odgovor na spoljnu napomenu — npr. reagovanje na taster miša ili tastature — te ga nazivamo asinhronim prekidom.

CPU obično podržava postavljanje bita za maskiranje prekida (jednog registra); kada se postavi na 1, CPU privremeno prestaje da reaguje na prekide.

Tako se privremeno maskiraju ulazi sa tastature i miša, kao i Trap, Fault i izuzeci.

Međutim, neki naročito važni prekidi — poput prekida usled gubitka napajanja zbog kvara na CPU-u — i dalje se normalno okidaju.

Prekide koje je moguće maskirati nazivamo maskirajućim prekidima; većina prekida spada u tu kategoriju.

Kernel režim i korisnički režim

Šta su korisnički i kernel režim

Kernel radi u režimu superprivilegija, pa ima vrlo visoka ovlašćenja.

Prema principu minimalnih privilegija, većina aplikacija treba da radi sa najmanjim potrebnim ovlašćenjima.

Zato mnogi operativni sistemi memoriju dele na dva područja:

• Kernel prostor (Kernal Space) — njemu može pristupiti samo kernel program;

• Korisnički prostor (User Space) — namenjen isključivo aplikacijama.

Kôd u korisničkom prostoru ograničen je na pristup samo delu memorije; kažemo da se takvi programi izvršavaju u korisničkom režimu.

Kôd u kernel prostoru može pristupiti celoj memoriji; kažemo da se izvršava u kernel režimu.

Prema nivoima privilegija:

Kada program radi na nivou privilegija 0, kažemo da radi u kernel režimu.

Kada program radi na nivou privilegija 3, kažemo da radi u korisničkom režimu.

Program koji radi u korisničkom režimu ne može direktno pristupiti strukturi podataka i programima kernela operativnog sistema.

Kada u sistemu pokrenemo program, najveći deo vremena on radi u korisničkom režimu; prelazi u kernel režim tek kada mu je potrebna pomoć operativnog sistema za poslove koje sam ne sme ili ne može da obavi (npr. upravljanje hardverom).

Glavne razlike između ova dva režima

U korisničkom režimu proces može da pristupa samo ograničenom memorijskom prostoru i skupu objekata, a procesor koji mu je dodeljen može biti preuzet (preempted).

U kernel režimu proces može da pristupa svim memorijskim prostorima i objektima, a procesor koji mu je dodeljen ne može biti preuzet.

Zašto uopšte postoje korisnički i kernel režim

Da bi se ograničila mogućnost pristupa između različitih programa — sprečilo da jedan program čita podatke iz memorije drugog ili pristupa periferijskim uređajima i šalje podatke na mrežu.

Prelaz iz korisničkog u kernel režim

Svi korisnički programi rade u korisničkom režimu, ali ponekad zaista moraju da obave nešto što pripada kernel režimu — na primer, da pročitaju podatke sa diska ili preuzmu unos sa tastature. To može samo operativni sistem, pa program mora da ga zamoli da, u njegovo ime, izvrši te operacije.

Prelaz između korisničkog i kernel režima

Sistemski poziv

Proces u korisničkom režimu preko sistemskog poziva traži od operativnog sistema da obavi potreban posao — na primer, fork() zapravo izvršava sistemski poziv koji kreira novi proces.

Mehanizam sistemskog poziva u svojoj suštini oslanja se na prekid koji operativni sistem posebno otvara za korisnike — na primer, int 80h prekid u Linux-u.

Primer:

Kao što prikaz pokazuje: kernel program izvršava se u kernel režimu (Kernal Mode), a korisnički program u korisničkom režimu (User Mode).

Kada dođe do sistemskog poziva, korisnički program ga inicira; pošto sistemski poziv sadrži privilegovane instrukcije, a korisnički program nema dovoljna ovlašćenja, njegovo izvršavanje se prekida — to je Trap (Trap je vrsta prekida).

Nakon prekida, program koji je CPU izvršavao se zaustavlja, skače na rutinu za obradu prekida i počinje izvršavanje kernel programa — odnosno obrada sistemskog poziva.

Kada kernel završi obradu, sam okida Trap, čime ponovo nastaje prekid i vraća se rad u korisnički režim.

Izuzetak

Kada CPU, izvršavajući program u korisničkom režimu, naiđe na neku prethodno nepredvidivu grešku, okida se prelaz sa trenutnog procesa na odgovarajući kernel program koji obrađuje tu grešku — time se prelazi u kernel režim (npr. izuzetak nedostatka stranice).

Prekid periferijskog uređaja

Kada periferijski uređaj završi operaciju koju je korisnik zahtevao, šalje CPU-u odgovarajući signal prekida; tada CPU pauzira izvršavanje sledeće instrukcije i prelazi na rutinu za obradu tog signala. Ako je prethodno izvršavana instrukcija pripadala programu u korisničkom režimu, ovaj prelaz prirodno podrazumeva i promenu iz korisničkog u kernel režim.

Na primer, kada se završi čitanje ili pisanje po disku, sistem prelazi u rutinu obrade prekida diska kako bi izvršio naknadne operacije.

Nit

Nit: osnovna jedinica kojoj sistem dodeljuje procesorsko vreme; najmanja jedinica izvršavanja programa.

Nit se može shvatiti kao laki proces — deli memorijski prostor, a svaka nit ima sopstveni stek izvršavanja i brojač programa; trošak promene među nitima je mali.

U okviru istog procesa (programa) istovremeno se izvršava više niti (putem CPU raspoređivanja, u svakom vremenskom isečku izvršava se samo jedna nit).

Proces može preko API-ja da kreira niti u korisničkom režimu, a može i preko sistemskog poziva da kreira niti u kernel režimu.

Korisničke niti

Korisnička nit, poznata i kao korisnička nit na nivou korisnika, nastaje potpuno u korisničkom prostoru — kernel operativnog sistema ni ne zna da postoji.

Korisničke niti imaju više prednosti:

• Mali trošak upravljanja: kreiranje i uništavanje ne zahtevaju sistemski poziv.

• Nizak trošak promene: program u korisničkom prostoru sam održava niti, bez potrebe za raspoređivanjem operativnog sistema.

Ali takve niti imaju i mnoge nedostatke:

• Visok trošak saradnje sa kernelom: budući da ih potpuno upravlja korisnički program, pri radu sa I/O ne mogu da iskoriste prednosti kernela i često moraju da prelaze iz korisničkog u kernel režim.

• Visok trošak saradnje među nitima: zamislimo da dve niti moraju da komuniciraju; komunikacija zahteva I/O, I/O zahteva sistemski poziv, pa korisničke niti snose dodatni trošak sistemskog poziva.

• Ne mogu iskoristiti višejezgarne prednosti: pošto operativni sistem i dalje raspoređuje proces kojem niti pripadaju, bez obzira na to koliko korisničkih niti proces ima, istovremeno se može izvršavati samo jedna — pa više niti jednog procesa ne mogu iskoristiti više jezgara.

Operativni sistem ne može da optimizuje raspoređivanje niti: kada se jedna korisnička nit procesa blokira (Block), operativni sistem to ne može blagovremeno da uoči i obradi, pa ne zamenjuje je drugom niti, što vodi rasipanju resursa.

Kernel niti

Kernel nit, poznata i kao nit na nivou kernela (Kernel Level Thread), izvršava se u kernel režimu i može se kreirati sistemskim pozivom.

Niti na nivou kernela imaju više prednosti:

• Iskorišćavanje višejezgarnih CPU-a: kernel ima visoka ovlašćenja, pa kernel niti može da se izvršava na više jezgara.

• Optimizacija na nivou operativnog sistema: kernel niti za I/O ne zahtevaju sistemski poziv; ako se jedna kernel nit blokira, druga može odmah da nastavi.

Naravno, kernel niti imaju i neke nedostatke:

• Visok trošak kreiranja: pri kreiranju potreban je sistemski poziv, odnosno prelazak u kernel režim.

• Loša skalabilnost: njima upravlja jedan kernel program, pa ne mogu biti brojne.

• Relativno visok trošak promene: pri promeni niti takođe su potrebne kernel operacije, odnosno prelazak u kernel režim.

Mapiranje između korisničkih i kernel niti

Ako imamo proces u korisničkom režimu sa više niti, kako taj proces može da izvrši neku od svojih niti?

Tada je jedan uobičajeni pristup da se program koji treba izvršiti poveri jednoj kernel niti.

Kernel nit je, na kraju krajeva, prava nit, jer dobija CPU resurse za izvršavanje.

Ako proces sam raspoređuje sve svoje niti, to je ekvivalentno tome da u glavnoj niti procesa implementira algoritam podeljenog vremena za svaku nit — odnosno sve niti se izvršavaju u vremenskim isečcima koje operativni sistem dodeli glavnoj niti.

Ovim pristupom operativni sistem raspoređuje glavnu nit procesa, dok glavna nit procesa vrši sekundarno raspoređivanje — raspoređuje sopstvene unutrašnje niti.

Nedostaci ovakvog pristupa su očigledni: ne može iskoristiti višejezgarne prednosti, svaka nit dobija malo vremena, a pri blokadi takva nit direktno predaje pravo izvršavanja celog procesa.

Odatle se vidi da su korisničke niti jeftine za kreiranje, ali sa jasnim problemima i bez mogućnosti korišćenja više jezgara.

Kernel niti su skupe za kreiranje, mogu iskoristiti više jezgara, ali su sporije pri promeni.

Zato obično unapred kreiramo određeni broj niti u kernelu i koristimo ih više puta.

Korutina

Korutina je još lakša od niti; nju ne upravlja kernel operativnog sistema, već isključivo sam program (odnosno izvršava se u korisničkom režimu).

Prednost ovoga je znatno bolje performanse — ne troši resurse kao promena niti.

Podprogram

Ili funkcija, u svim jezicima se poziva hijerarhijski: A poziva B, B tokom izvršavanja poziva C, C po završetku se vraća, B se završava i vraća, konačno se završava A.

Zato se poziv podprograma ostvaruje preko steka — jedna nit jeste izvršavanje jednog podprograma.

Poziv podprograma uvek ima jedan ulaz i jedan povrat, a redosled poziva je jasno određen.

Specifičnost korutine je da se izvršava u jednoj niti — koje su njene prednosti u poređenju sa višenitnim radom?

• Veoma visoka efikasnost: pošto promena podprograma nije promena niti već njom upravlja sam program, nema troška promene niti; što je više niti u višenitnom modelu, to je prednost korutine izraženija.
• Ne zahteva mehanizam brava višenitnog rada: pošto postoji samo jedna nit, nema ni istovremenog pisanja u istu promenljivu; u korutini se deljeni resursi kontrolišu bez brava, proverom stanja, pa je efikasnost znatno veća nego kod više niti.

Bezbednost niti

Ako u procesu gde se izvršava vaš kôd istovremeno radi više niti, te niti mogu istovremeno izvršavati taj isti kôd.

Ako rezultat svakog izvršavanja bude isti kao u jednoinstancnom (single-thread) režimu, i vrednosti ostalih promenljivih budu kao što se očekivalo, takav kôd je bezbedan za niti (thread-safe).

Proces

Pokrenuta aplikacija u sistemu; čim program počne da se izvršava, postaje proces; najmanja je jedinica dodele resursa.

U operativnom sistemu može istovremeno da se izvršava više procesa.

Pri pokretanju se kernel slika sa diska učitava u memoriju kao izvršna kopija i postaje kernel proces.

Procesi se dele na korisničke procese i kernel procese: korisnički procesi su obično kopije aplikacija, dok su kernel procesi procesi samog kernela.

Ako korisnički proces treba da zatraži resurse (npr. memoriju), to može sistemskim pozivom upućenim kernelu.

Svaki proces ima zaseban memorijski prostor u kojem čuva segment kôda, podatke i sl.; promena između programa nosi znatan trošak.

Podeljeno vreme i raspoređivanje

Svaki proces pri izvršavanju dobija vremenski isečak koji mu dodeljuje operativni sistem; kada istekne, na red dolazi sledeći proces (nit).

Napomena: savremeni operativni sistemi raspoređuju direktno niti, ne procese.

Dodela vremenskih isečaka

Kao što prikaz pokazuje, procesu 1 trebaju 2 isečka, procesu 2 samo 1, a procesu 3 tri isečka.

Zato kada proces 1 stigne do polovine, biva suspendovan i pokreće se proces 2; proces 2 se može završiti u jednom presečku, pa kreće proces 3, koji se ne može završiti odjednom — posle jednog isečka ponovo kreće proces 1; i tako u krug — to je tehnika podeljenog vremena.

Kreiranje procesa

Najdirektniji način da korisnik kreira proces jeste da iz komandne linije pokrene program ili dvoklikom otvori aplikaciju; ali programerima je očigledno potrebno nešto bolje.

Prvo, treba postojati API za otvaranje aplikacija — na primer, funkcija kojom se otvara određena aplikacija;

S druge strane, ako programer nakon skupog procesa inicijalizacije želi da trenutno stanje programa kopira u više primeraka koji postaju zasebni procesi, operativni sistem nudi instrukciju fork.

Drugim rečima, svaki fork stvara po jedan klon procesa; taj klon ima sva stanja originalnog procesa, ali sopstveni adresni prostor.

Ako želite da kreirate dva klonirana procesa, morate fork-ovati dva puta.

A šta ako želim da pokrenem novi program?

Operativni sistem nudi API za pokretanje novog programa.

Ako želite da u novom procesu izvršite samo mali deo programa — na primer, svaki put kada server primi zahtev od klijenta, želite da taj zahtev obradi zaseban proces.

U takvom slučaju preporučuje se da ne pokrećete zaseban proces, već da koristite nit.

Trošak kreiranja procesa je zaista visok, pa se ne preporučuje za ovakve potrebe: treba napraviti stavku, dodeliti memoriju, a posebno u memoriji formirati segmente podeljene na različite oblasti. Zato najčešće radije kreiramo više niti.

Različiti programski jezici nude sopstvene API-je za kreiranje niti: Java ima klasu Thread; Go ima go-routine (napomena: nije korutina, nego nit).

Stanja procesa

Stanje kreiranja

Proces nastaje procesom kreiranja; to je vrlo složen postupak koji se obično sastoji iz više koraka: proces prvo traži prazan kontrolni blok procesa (PCB) i u njega upisuje podatke za upravljanje; zatim mu se dodeljuju resursi potrebni za rad; konačno, proces prelazi u spremno stanje i umeće se u red spremnih procesa.

Spremno stanje

Ovo je stanje u kojem je proces spreman za izvršavanje, odnosno dobija sve potrebne resurse osim CPU-a; čim dobije CPU, može odmah da krene. Ako u sistemu ima više procesa u spremnom stanju, oni se po određenoj strategiji ređaju u tzv. red spremnih procesa. To su procesi koji imaju pravo na izvršavanje, ali nemaju nadležnost za izvršavanje.

Stanje izvršavanja

Ovo je stanje u kojem je proces dobio CPU i trenutno se izvršava. U svakom trenutku, u sistemu sa jednim procesorom samo je jedan proces u stanju izvršavanja, dok u sistemu sa više procesora može biti više procesa u izvršavanju — to su procesi koji imaju i pravo i nadležnost izvršavanja.

Blokirano stanje

Ovo je stanje u kojem proces u izvršavanju, zbog nekog događaja (npr. I/O zahtev, neuspešno zauzeje bafera), privremeno ne može da nastavi — kažemo da je proces blokiran. Tada se pokreće raspoređivanje procesa: operativni sistem dodeljuje procesor drugom spremnom procesu, dok blokirani proces ostaje u pauziranom stanju koje obično nazivamo blokiranim stanjem.

Završno stanje

Međuprocesna komunikacija (IPC)

Svaki proces ima sopstveni korisnički adresni prostor; globalne promenljive jednog procesa nisu vidljive drugom, pa razmena podataka između procesa mora da teče kroz kernel. U kernelu se otvara bafer: proces 1 kopira podatke iz korisničkog prostora u kernel bafer, a proces 2 ih odatle čita — ovaj mehanizam kernela nazivamo međuprocesnom komunikacijom.

Cevi (Pipes) / Anonimne cevi

Cev je poludupleks: podaci teku u jednom smeru; za obostranu komunikaciju potrebne su dve cevi.

• Mogu se koristiti samo između procesa roditelja i dece ili braće/sestara (u srodstvu);

• Čine zaseban fajlsistem: za procese na oba kraja cev je fajl, ali nije običan fajl — ne pripada standardnom fajlsistemu, već samostalno oblikuje svoj fajlsistem i postoji samo u memoriji.

• Čitanje i pisanje: ono što jedan proces upiše u cev čita proces na drugom kraju; upisani sadržaj se uvek dodaje na kraj bafera, a čita se uvek od početka bafera.

Imenovana cev (FIFO)

Anonimna cev, pošto nema ime, može se koristiti samo između procesa u srodstvu.

Da bi se prevazišao taj nedostatak, uvedena je imenovana cev (FIFO).

Razlika u odnosu na anonimnu cev jeste u tome što imenovana cev ima pridruženo ime putanje i postoji u fajlsistemu kao fajl tipa imenovane cevi. Tako, čak i procesi koji nisu u srodstvu sa procesom koji ju je kreirao, ukoliko mogu da pristupe toj putanji, mogu međusobno da komuniciraju preko imenovane cevi — dakle, i nerasrodni procesi mogu razmenjivati podatke.

Signal

Signal je mehanizam u Linux sistemu za međusobnu komunikaciju ili delovanje između procesa; signal se može poslati procesu u svakom trenutku, bez potrebe da se zna njegovo stanje.

Ako proces trenutno nije u stanju izvršavanja, kernel čuva taj signal dok proces ne nastavi rad i tada mu ga prosledi.

Ako je proces signal konfigurisao kao blokirani, njegovo isporučivanje se odgađa dok se blokada ne ukine.

Red poruka

Red poruka je ulančana lista poruka u kernelu; svaki red poruka predstavljen je identifikatorom reda poruka.

Za razliku od cevi (anonimne cevi: fajl koji postoji samo u memoriji; imenovane cevi: fajl na stvarnom disku ili fajlsistemu), red poruka se nalazi u kernelu i briše se tek kada se kernel ponovo pokrene (odnosno kada se operativni sistem ponovo pokrene) ili kada se eksplicitno obriše.

Takođe, za razliku od cevi, pre nego što jedan proces upiše poruku u red, ne mora da čeka da drugi proces na njemu čeka dolazak poruke.

Deljena memorija

Omogućava da više procesa direktno čita i piše iz istog memorijskog prostora; to je najbrži oblik IPC, projektovan kao odgovor na nisku efikasnost drugih mehanizama komunikacije.

Da bi se razmenjivale informacije između više procesa, kernel izdvaja memorijsku oblast koju procesi koji joj pristupaju mogu da mapiraju u svoj privatni adresni prostor; procesi zatim direktno čitaju i pišu po toj memoriji bez potrebe za kopiranjem podataka, što znatno povećava efikasnost.

Pošto više procesa deli istu memoriju, potrebno je osloniti se na neki mehanizam sinhronizacije (npr. semafor) radi sinhronizacije i međusobnog isključenja među procesima.

Šema deljene memorije:

Jednom kada takva memorija bude mapirana u adresne prostore procesa koji je dele, prenos podataka između tih procesa više ne prolazi kroz kernel — drugim rečima, procesi više ne moraju da ulaze u kernel putem sistemskog poziva da bi razmenjivali podatke.

Semafor

Semafor je brojač koji služi za kontrolu pristupa više procesa deljenim podacima; namera semafora je sinhronizacija među procesima.

Da bi dobio deljeni resurs, proces izvršava sledeće operacije:

1. Kreira semafor: pozivalac navodi početnu vrednost; za binarni semafor to je obično 1, a može biti i 0.

2. Čeka semafor: operacija ispituje vrednost semafora; ako je manja od 0, blokira se — poznato i kao P operacija.

3. Oslobađa semafor: operacija uvećava vrednost semafora za 1 — poznato i kao V operacija.

Soket (Socket)

Soket je mehanizam komunikacije pomoću kojeg razvoj klijent/server sistema (odnosno procesa koji komuniciraju) može da se obavi kako na lokalnoj mašini, tako i preko mreže. Drugim rečima, omogućava komunikaciju između procesa koji se nalaze na različitim računarima povezanim preko mreže.

Signal

Signal je jedini asinhroni mehanizam međuprocesne komunikacije; može se shvatiti kao asinhrono obaveštenje kojim se procesu koji prima signal saopštava šta se dogodilo.

Može se, jednostavno rečeno, shvatiti i kao neka vrsta softverskog prekida.

Komandom kill -l možete prikazati listu signala koje podržava Linux:

kill -l
 1) SIGHUP   2) SIGINT   3) SIGQUIT  4) SIGILL   5) SIGTRAP
 6) SIGABRT  7) SIGBUS   8) SIGFPE   9) SIGKILL 10) SIGUSR1
11) SIGSEGV 12) SIGUSR2 13) SIGPIPE 14) SIGALRM 15) SIGTERM
16) SIGSTKFLT 17) SIGCHLD 18) SIGCONT 19) SIGSTOP 20) SIGTSTP
21) SIGTTIN 22) SIGTTOU 23) SIGURG  24) SIGXCPU 25) SIGXFSZ
26) SIGVTALRM 27) SIGPROF 28) SIGWINCH  29) SIGIO 30) SIGPWR
31) SIGSYS  34) SIGRTMIN  35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3
38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8
43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7
58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2
63) SIGRTMAX-1  64) SIGRTMAX

Nekoliko najčešćih signala:

Signal	Opis
SIGHUP	Kada korisnik napusti terminal, svi procesi pokrenuti iz njega dobijaju ovaj signal; podrazumevana akcija je terminacija procesa.
SIGINT	Signal za prekid (interrupt) programa; šalje se kada korisnik pritisne karakter INTR (obično Ctrl+C); služi da obavesti foreground grupu procesa da prekine rad.
SIGQUIT	Sličan SIGINT, ali ga kontroliše karakter QUIT (obično Ctrl+\); kada proces izađe zbog SIGQUIT, generiše core fajl — u tom smislu je sličan signalu greške programa.
SIGKILL	Služi za trenutno prekidanje rada programa; ovaj signal ne može biti blokiran, obrađen niti ignorisan.
SIGTERM	Signal za završetak (terminate) programa; za razliku od SIGKILL, može biti blokiran i obrađen. Obično se koristi kada se od programa traži da se sam uredno završi.
SIGSTOP	Zaustavlja (stopped) izvršavanje procesa. Razlika u odnosu na terminate i interrupt je u tome što proces još uvek nije završen, već samo pauziran; ovaj signal ne može biti blokiran, obrađen niti ignorisan.

Sinhronizacija procesa

Kritična sekcija

Serijalizacijom pristupa više niti javnom resursu ili segmentu kôda; brza je i pogodna za kontrolu pristupa podacima.

Prednost: jednostavan način da se osigura da u jednom trenutku samo jedna nit pristupa podacima.

Mana: iako je brza, služi samo za sinhronizaciju niti unutar istog procesa, a ne i između različitih procesa.

Mutex

Projektovan radi usklađenog pojedinačnog pristupa deljenom resursu.

Mutex je vrlo sličan kritičnoj sekciji, ali složeniji; postoji samo jedan mutex objekat i samo nit koja ga poseduje ima pravo pristupa resursu.

Prednost: korišćenjem mutexa resurs se bezbedno deli ne samo između niti iste aplikacije, već i između niti različitih aplikacija.

Semafor

Projektovan za kontrolu resursa sa ograničenim brojem korisnika; dozvoljava više nita da istovremeno pristupaju istom resursu, ali uz ograničenje maksimalnog broja nita u istom trenutku. Mutex je specijalan slučaj semafora: kada je maksimalan broj resursa semafora 1, on postaje mutex.

Semafor (Semaphore) je celobrojna promenljiva nad kojom se izvršavaju operacije down i up, poznate i kao P i V operacije.

• down: ako je vrednost semafora veća od 0, izvršava operaciju -1; ako je jednaka 0, proces ide na spavanje i čeka da vrednost postane veća od 0;
• up: izvršava +1 nad semaforom i budi proces na spavanju da dovrši svoju down operaciju.

down i up operacije moraju se projektovati kao atomicne (nedeljive) primitive; uobičajeni pristup je da se tokom tih operacija maskiraju prekidi.

Ako semafor može uzimati samo vrednosti 0 ili 1, pretvara se u Mutex — 0 znači da je kritična sekcija zaključana, a 1 da je otključana.

Događaj (Event)

Služi da obavesti niti da se neki događaj zbio, čime se pokreće izvršavanje narednih zadataka.

Prednost: objekat dogđaja održava sinhronizaciju niti putem obaveštavanja i može da ostvari sinhronizaciju niti između različitih procesa.

Monitor

Monitor ima važnu osobinu: u jednom trenutku samo jedan proces može koristiti monitor.

Kada proces ne može da nastavi izvršavanje, ne sme trajno da drži monitor, inače drugi procesi nikada ne bi mogli da ga koriste.

Monitor uvodi uslovne promenljive i pridružene operacije: wait() i signal(), kojima se ostvaruje sinhronizacija.

Operacija wait() nad uslovnom promenljivom blokira pozivajući proces i prepušta monitor drugom procesu.

Operacija signal() služi da se blokiran proces probudi.

Rešenje problema proizvođača i potrošača pomoću semafora zahteva dosta kontrolnog kôda na strani klijenta, dok monitor izdvaja taj kontrolni kôd, što smanjuje mogućnost grešaka i olakšava pozive iz klijentskog kôda.

Promena konteksta

Za jednoprocesorski, jednonitni CPU, u jednom trenutku može se izvršiti samo jedna instrukcija.

Promena konteksta (Context Switch) mehanizam je kojim se CPU resursi preusmeravaju sa jednog procesa na drugi.

Sa korisnikovog aspekta računar paralelno izvršava više procesa — što je upravo rezultat brzog smenjivanja konteksta od strane operativnog sistema.

Pri promeni, operativni sistem prvo čuva stanje trenutnog procesa (uključujući pokazivač na memorijski prostor, poslednju izvršenu instrukciju itd.), zatim učitava stanje sledećeg procesa i preuzima njegovo izvršavanje.

Algoritmi raspoređivanja procesa

FCFS (First-Come, First-Served)

Ovaj algoritam može se koristiti kako za raspoređivanje poslova, tako i za raspoređivanje procesa. Pri raspoređivanju poslova, u svakom ciklusu se iz reda poslova u pozadini bira jedan ili više poslova koji su prvi ušli, ubacuju se u memoriju, dodeljuju im se resursi, kreira se proces i stavljaju u red spremnih.

SJF (Shortest Job First)

Bira se jedan ili više poslova iz reda sa najkraćim procenjenim vremenom izvršavanja i ubacuju u memoriju radi izvršavanja.

Rotacija vremenskih isečaka (Round Robin)

Pri svakom raspoređivanju CPU se dodeljuje procesu na čelu reda i daje mu se jedan vremenski isečak (od nekoliko ms do nekoliko stotina ms). Kada se isečak potroši, tajmer okida zahtev za prekid sata; raspoređivač na osnovu tog signala zaustavlja proces i šalje ga na kraj reda spremnih.

Zatim CPU dobija novi proces sa čela reda, koji takođe dobija jedan isečak; tako se osigurava da svi procesi u redu spremnih u zadatom periodu dobiju po jedan isečak procesorskog vremena.

SRTF (Shortest Remaining Time First)

Preemptivna verzija SJF-a; raspoređuje se po preostalom vremenu izvršavanja. Kada stigne novi posao, njegovo ukupno vreme se poredi sa preostalim vremenom tekućeg procesa.

Ako novom procesu treba manje vremena, trenutni proces se suspenduje i pokreće novi; u suprotnom, novi proces čeka.

Višeredno povratno raspoređivanje (Multilevel Feedback Queue)

Prethodno navedeni algoritmi imaju izvesna ograničenja — npr. SJF favorizuje kratke poslove, a zapostavlja duge. Višeredno povratno raspoređivanje istovremeno omogućava da visokoprioritetni poslovi dobiju odziv i da kratki poslovi brzo završe; zbog toga se danas smatra jednim od najboljih algoritama raspoređivanja, a UNIX operativni sistem koristi baš ovaj pristup.

Primer:

Višeredno raspoređivanje znači raspoređivanje preko više redova; krenimo od najjednostavnijeg dvorednog modela.

Gornji prikaz predviđa dva reda različitih prioriteta — idući odozdo naviše prioritet raste; gornji red opslužuje hitne zadatke, donji red obične zadatke.

Dok god u gornjem redu ima zadataka, donji red prepušta pravo izvršavanja.

Red niskog prioriteta može se realizovati kombinacijom preemptivnog pristupa i reda sa prioritetom — tako se nakon svakog isečka proverava da li u redu visokog prioriteta ima zadataka.

Red visokog prioriteta može se realizovati ne-preemptivno (svaki zadatak se dovrši pre sledećeg) sa redom prioriteta — tako se hitni zadaci razlikuju, a u izuzetno hitnim situacijama takav zadatak može odmah da se obradi.

Iako ovaj model rešava pitanje prioriteta među zadacima, još uvek ne rešava pitanje kratkih zadataka koji bi trebalo da idu prvi; može se dodati još redova, sa više nivoa.

Na primer, model na sledećem prikazu:

Hitni zadaci i dalje idu kroz red visokog prioriteta, ne-preemptivno.

Obični zadaci se prvo stavljaju u red čiji je prioritet odmah ispod visokog, i dobijaju vrlo mali vremenski isečak; ako se ne završe, znači da nisu kratki, pa se spuštaju za jedan nivo.

Na najnižem nivou, red najnižeg prioriteta ima velike vremenske isečke, što dugim zadacima ostavlja više prostora.

Na ovaj način kratki zadaci se završavaju u redovima višeg prioriteta, dok se dugi spuštaju — čime se, efektivno, rešava problem najkraćeg-posla-prvi.

U praksi može postojati n nivoa: sloj po sloj izdvajaju se veliki zadaci, a najduži se izvršavaju u najmirnijem vremenu; treba imati na umu da CPU veći deo vremena nije pod punim opterećenjem.

Raspoređivanje po prioritetu

Svakom procesu dodeljuje se prioritet; prvi se izvršava onaj sa najvišim prioritetom, i tako redom; procesi istog prioriteta izvršavaju se po FCFS-u. Prioritet se može odrediti na osnovu memorijskih zahteva, vremenskih zahteva ili bilo kojih drugih zahteva za resursima.

Daemon proces

Daemon je proces koji radi u pozadini, odvojen od terminala. Odvajanje od terminala služi da se poruke nastale tokom rada ne prikazuju na terminalu, i da proces ne prekidaju signali koje terminal generiše.

Životni vek daemon procesa obično traje od pokretanja do gašenja sistema.

U Linux-u postoji mnogo daemon procesa — najtipičniji su procesi usluga koje često vidimo.

Daemon procesi se naravno često koriste i za obavljanje sistemskih ili automatizovanih zadataka.

Siroče proces

Kada roditeljski proces završi pre procesa-deteta, a proces-dete još uvek radi, to dete postaje siroče. Linux postupa sa siročadima tako što im kao roditelja postavi proces sa brojem 1 — odnosno prepusti ga init procesu na staranje; init je odgovoran za čišćenje nakon izlaska procesa-deteta.

Zombi proces

Kada proces-dete završi, a ustanovi da roditeljski proces još nije izašao, šalje mu SIGCHLD signal; ali roditelj nije upotrebio wait/waitpid niti na drugi način obradio SIGCHLD, pa proces-dete postaje štetan zombi proces.

Pošto informacije koje proces-dete ostavi po izlasku nisu prikupljene, njegov kontrolni blok procesa (PCB) se ne oslobađa, te nastaje zombi proces — proces je mrtav, ali njegovi resursi nisu oslobođeni.

Problem i štetnost

Ako u sistemu postoji mnogo zombi procesa, njihovi brojevi (PID) ostaju zauzeti; pošto je broj dostupnih PID-ova ograničen, sistem zbog nedostatka PID-ova ne može da kreira nove procese.

Bilo koji proces-deteta (osim init) posle exit() ne nestaje odmah, već ostavlja strukturu podataka zvani zombi (Zombie) koja čeka da je roditelj obradi — to je faza kroz koju svaki proces-dete prolazi pri završetku. Ako roditelj ne stigne da je obradi nakon exit(), komandom ps se može videti da je status deteta Z.

Ako roditelj stigne blagovremeno, ps možda neće ni uhvatiti zombi stanje deteta, ali to ne znači da dete nije prošlo kroz zombi stanje.

Pravi krivac za nastanak zombija jeste roditeljski proces — ako se roditelj ubije, zombi postaje siroče i može biti prepušten init procesu na recikliranje.

Mrtva blokada (Deadlock)

Uzroci nastanka

Takmičenje za sistemske resurse: takmičenje za sistemske resurse dovodi do njihovog nedostatka, a i neprimerena alokacija može izazvati mrtvu blokadu.

Neodgovarajući redosled u kojem procesi traže i otpuštaju resurse tokom rada takođe može izazvati mrtvu blokadu.

Četiri neophodna uslova za nastanak mrtve blokade

Uslov međusobnog isključenja (mutual exclusion): resurs u jednom trenutku može koristiti samo jedan proces — odnosno, u određenom periodu resurs drži samo jedan proces; ako ga drugi proces zatraži, mora čekati.

Uslov zauzeća i čekanja (hold and wait): proces već drži barem jedan resurs, ali traži novi koji je već zauzeo drugi proces; tada proces koji traži biva blokiran, ali ne pušta resurse koje već drži.

Uslov neoduzimanja (no preemption): resurs koji proces dobio ne može biti silom oduzet od drugog procesa dok ga ovaj ne potroši — odnosno, može ga osloboditi samo proces koji ga drži (isključivo aktivnim otpuštanjem).

Uslov kružnog čekanja (circular wait): između više procesa formira se odnos kružnog čekanja resursa.

Ova četiri uslova su neophodni uslovi mrtve blokade; kada god sistem uđe u mrtvu blokadu, oni nužno vrede, a ako makar jedan od njih nije zadovoljen, mrtve blokade nema.

Dovoljno je da narušimo samo jedan od njih i uspešno ćemo izbeći mrtvu blokadu.

Među njima, uslov međusobnog isključenja ne možemo narušiti, jer nam brava upravo i služi za međusobno isključenje.

1. Uslov zauzeća i čekanja možemo narušiti tako što tražimo sve resurse odjednom — tada nema čekanja.
2. Uslov neoduzimanja možemo narušiti tako što nit koja drži deo resursa, kada zatraži dodatne i ne dobije ih, aktivno otpusti ono što već drži — čime taj uslov prestaje da važi.
3. Uslov kružnog čekanja može se sprečiti traženjem resursa po redosledu: resursi imaju linearni redosled, pa se prvo traže oni sa manjim brojem, a zatim oni sa većim; linearnim uređenjem kružno čekanje nestaje.

Načini obrade

Postoje uglavnom četiri pristupa:

• Strategija noja (ignorisanje)
• Detekcija i oporavak mrtve blokade
• Sprečavanje mrtve blokade narušavanjem 4 neophodna uslova
• Izbegavanje mrtve blokade — Bankar-ov algoritam

Strategija noja

Zabiti glavu u pesak i pretvarati se da problem ne postoji.

Pošto je rešenje mrtve blokade vrlo skupo, strategija noja — koja ne preduzima ništa — donosi veće performanse.

Kada mrtva blokada ne utiče znatno na korisnika ili je verovatnoća nastanka vrlo mala, može se prihvatiti strategija noja.

Detekcija mrtve blokade

Ne pokušava se sprečiti mrtva blokada, već kada se otkrije da je nastala, preduzimaju se koraci za oporavak.

1. Detekcija kada svaki tip resursa ima po jedan primerak

2. Detekcija kada svaki tip resursa ima više primeraka

Oporavak od mrtve blokade

• Oporavak iskorišćavanjem preuzimanja
• Oporavak iskorišćavanjem povratka (rollback)
• Oporavak ubijanjem procesa

Problem večere filozofa

Pet filozofa sedi oko okruglog stola; ispred svakog je hrana.

Život filozofa sastoji se iz dva naizmenična procesa: jedenja i razmišljanja.

Kada filozof jede, prvo mora uzeti štapiće sa svoje leve i desne strane, a može uzeti samo po jedan štapić.

Ako svih pet filozofa istovremeno uzmu levu štapić, svi će čekati da drugi završe i oslobode svoje štapiće — što vodi u mrtvu blokadu.

Problem večere filozofa može se posmatrati kao reprezentativan problem obrade deljenih resursa pri konkurentnom izvršavanju procesa.

Da bi se sprečila mrtva blokada, mogu se postaviti dva uslova:

• moraju se istovremeno uzeti oba štapića;
• dozvoljeno je jesti samo ako nijedan od dva suseda ne jede.

Bankar-ov algoritam

Bankar-ov algoritam je dobio ime po tome što se može koristiti u bankarskom sistemu: kada ne može da zadovolji sve potrebe klijenata, banka nikada neće raspodeliti svoja sredstva.

Kada nov proces uđe u sistem, mora navesti maksimalan broj primeraka svake vrste resursa koji bi mu mogao zatrebati — taj broj ne sme premašiti ukupne resurse sistema.

Kada korisnik zatraži grupu resursa, sistem mora utvrditi da li je njihova alokacija sigurna stanje; ako jeste, vrši alokaciju, a ako nije, proces mora čekati dok neki drugi proces ne oslobodi dovoljno resursa.

Sigurno stanje

U metodama izbegavanja mrtve blokade, procesima se dozvoljava da dinamički traže resurse, ali pre alokacije sistem treba da izračuna da li je ta alokacija sigurna; ako ne vodi u nesigurno stanje, resursi se dodeljuju, inače proces čeka.

Dakle, suština izbegavanja mrtve blokade je: pri alokaciji resursa obezbediti da sistem ne uđe u nesigurno stanje.

Funkcija fork

Funkcija fork kreira proces-dete koje je isto kao i tekući proces; proces-dete kopira segment kôda, segment podataka, BSS segment, heap, stek i sve ostale informacije korisničkog prostora roditeljskog procesa, dok kernel u jezgru ponovo obezbeđuje mesto gde će se proces-dete izvršavati.

Sistemski poziv fork kreira potpuno novi proces kopiranjem postojećeg; novi proces smešta se u dvostruku cikličnu ulančanu listu koja se zove red zadataka, gde je svaka stavka struktura kontrolnog bloka procesa PCB tipa task_struct.

Svaki proces ima jedinstveni identifikator procesa (PID). Funkcijom getpid() dobija se PID tekućeg procesa, a funkcijom getppid() PID roditeljskog procesa.

Postojeći proces pozivom funkcije fork kreira novi proces; proces koji nastaje pozivom fork zove se proces-dete (child process). Funkcija fork se poziva jednom, ali se vraća dva puta — razlika je u tome što u procesu-detetu vraća 0, a u roditeljskom procesu vraća PID procesa-deteta.

Zašto se fork vraća dva puta?

Pošto se pri kopiranju kopira i stek roditeljskog procesa, oba procesa ostaju u funkciji fork i čekaju povratnu vrednost, pa se vraća dva puta — jednom u roditelju i jednom u detetu; te dve vrednosti su različite.

• U roditeljskom procesu vraća PID novog procesa-deteta
• U procesu-detetu vraća 0
• U slučaju greške vraća negativan broj

Zato se na osnovu povratne vrednosti fork može utvrditi da li je tekući proces dete ili roditelj.

Tok izvršavanja fork

Kada proces pozove fork, kontrola prelazi u kernel, koji radi četiri stvari:

1. Dodeljuje novi memorijski blok i kernel strukturu podataka procesu-detetu
2. Kopira deo sadržaja struktura podataka roditeljskog procesa (prostor podataka, stek itd.) u proces-dete
3. Dodaje proces-dete u listu sistemskih procesa
4. fork se vraća i pokreće raspoređivač

Zašto je pid različit u roditelju i detetu?

To je, u suštini, poput ulančane liste: procesi formiraju listu, pid roditelja pokazuje na PID procesa-deteta; pošto proces-dete nema sopstveno dete, njegov PID je 0 — pid ovde igra ulogu pokazivača kao u ulančanoj listi.

Upravljanje uređajima

Algoritmi raspoređivanja diska

Na vreme čitanja ili pisanja bloka diska utiču:

• vreme rotacije
• vreme pozicioniranja glave i stvarno vreme prenosa podataka

Vreme pozicioniranja glave (seek) je najduže, pa je glavni cilj raspoređivanja diska da se minimizuje prosečno vreme pozicioniranja.

FCFS, First Come First Served

Raspoređuje se redom kojim stižu zahtevi; prednost je pravednost i jednostavnost, a mana očigledna — pošto ne optimizuje pozicioniranje, prosečno vreme pozicioniranja može biti dugo.

SSTF, Shortest Seek Time First

Prioritet ima zahtev na stazi koja je najbliža trenutnoj poziciji glave. Iako je prosečno vreme pozicioniranja niže, nije pravedno: ako novopristigli zahtev uvek bude bliži od onog koji čeka, onaj koji čeka može čekati zauvek — pojavljuje se izgladnjivanje, koje je tipično za zahteve na ivicama.

SCAN (algoritam lifta)

Lift se uvek kreće u jednom smeru dok u tom smeru ima zahteva, a zatim menja smer. Algoritam lifta (skeniranje) radi slično: vrši raspoređivanje diska u jednom smeru dok u tom smeru ima neispunjenih zahteva, a zatim menja smer. Pošto vodi računa o smeru kretanja, svi zahtevi će biti ispunjeni — čime se rešava problem izgladnjivanja iz SSTF-a.

Upravljanje memorijom

Logička i fizička adresa

U programiranju se obično susrećemo samo sa logičkim adresama. Na primer, u C-u vrednost koju pokazivač čuva može se shvatiti kao adresa u memoriji — to je upravo logička adresa, koju određuje operativni sistem.

Fizička adresa je adresa u stvarnoj fizičkoj memoriji, tačnije adresa u registru memorijskih adresa; ona je prava adresa memorijske jedinice.

Pri prevoodenju dovoljno je utvrditi da promenljiva x ima relativnu adresu 100 (odnosno adresu u odnosu na početnu adresu procesa u memoriji).

Da bi CPU pronašao stvarnu lokaciju x u memoriji, dovoljno je dodati početnoj adresi procesa vrednost 100.

Relativna adresa se još zove logička, a apsolutna adresa se još zove fizička.

Koje su vrste upravljanja memorijom

1. Upravljanje blokovima: memorija se deli na blokove fiksnih veličina; svaki blok sadrži samo jedan proces. Ako program zahteva memoriju, operativni sistem mu dodeli jedan blok; ako programu treba vrlo malo prostora, veći deo tog bloka ostaje neiskorišćen — taj neiskorišćeni prostor unutar bloka nazivamo fragmentacijom.
2. Upravljanje stranicama: glavna memorija se deli na stranice jednakih i fiksnih veličina; pošto su stranice manje od blokova, podela je sitnija, što povećava iskorišćenost memorije i smanjuje fragmentaciju. Upravljanje stranicama preko tabele stranica mapira logičke i fizičke adrese.

1. Upravljanje segmentima: iako upravljanje stranicama povećava iskorišćenost memorije, same stranice nemaju nikakvo stvarno značenje. Upravljanje segmentima glavnu memoriju deli na segmente; svaki segment je manji od stranice. Tabela segmenata mapira logičke i fizičke adrese.
2. Segmentno-stranično upravljanje: kombinuje prednosti upravljanja segmentima i stranicama; jednostavno rečeno, glavna memorija se prvo podeli na više segmenata, a zatim se svaki segment podeli na više stranica — odnosno, segmenti su međusobno diskretni, a i unutar segmenta raspored je diskretan.

Virtuelna adresa

Savremeni procesori koriste način adresiranja poznat kao virtuelno adresiranje (Virtual Addressing).

Pri virtuelnom adresiranju, CPU mora prevesti virtuelnu adresu u fizičku kako bi pristupio stvarnoj fizičkoj memoriji.

Hardver koji zapravo obavlja taj prevod jeste jedinica za upravljanje memorijom (Memory Management Unit, MMU) unutar CPU-a.

Zašto postoji virtuelni adresni prostor

Bez virtuelnog adresnog prostora, programi neposredno pristupaju fizičkoj memoriji i operišu nad njom.

Kakvi su tu problemi?

1. Korisnički program može pristupiti bilo kojoj memorijskoj lokaciji i adresirati svaki bajt, što lako oštećuje operativni sistem i dovodi do njegovog pada.
2. Istovremeno pokretanje više programa postaje vrlo teško — ne možete istovremeno pokrenuti WeChat i QQ Music. Zašto? Jednostavan primer: dok WeChat radi, upiše vrednost na adresu 1xxx; QQ Music zatim takođe upisuje vrednost na adresu 1xxx, čime prepisuje WeChat-ovu vrednost, što dovodi do pada WeChata.

Prednosti pristupa memoriji preko virtuelnih adresa:

• Program može koristiti niz susednih virtuelnih adresa da bi pristupio velikom, nesusednom memorijskom baferu u fizičkoj memoriji.
• Program može koristiti niz virtuelnih adresa da bi pristupio baferu većem od dostupne fizičke memorije.
• Virtuelni adresni prostori različitih procesa su međusobno izolovani: kôd u jednom procesu ne može izmeniti fizičku memoriju koju koristi drugi proces ili operativni sistem.

Kako MMU prevodi virtuelnu adresu u fizičku

Za svaki program, MMU čuva po jednu tabelu stranica u kojoj su upisana mapiranja virtuelnih stranica u fizičke.

Kada se za virtuelnu stranicu pronađe fizička stranica, u tabelu se dodaje zapis kojim se čuva to mapiranje; naravno, kako virtuelne stranice ulaze i izlaze iz fizičke memorije, sadržaj tabele stranica se stalno ažurira.

Virtuelna memorija

Često istovremeno otvaramo više programa koji troše mnogo memorije, pa njihova ukupna potrošnja može daleko premašiti fizičku memoriju računara.

Preko virtuelne memorije program može raspolagati memorijom većom od fizičke memorije sistema.

Pored toga, virtuelna memorija svakom procesu pruža dosledan, privatni adresni prostor i stvara mu iluziju da samostalno raspolaže glavnom memorijom (svaki proces ima neprekidan, celovit memorijski prostor), što memorijom upravlja efikasnije i smanjuje broj grešaka.

Virtuelna memorija je tehnika upravljanja memorijom u računarskom sistemu; virtuelnu memoriju svog računara možemo ručno podesiti.

Ključni značaj virtuelne memorije jeste u tome što ona definiše neprekidan virtuelni adresni prostor i proširuje memoriju na prostor diska.

Tri načina realizacije virtuelne memorije:

1. Upravljanje memorijom sa zahtevnim straničenjem: zahtevno straničenje je najčešće korišćen način realizacije virtuelne memorije. U sistemu sa zahtevnim straničenjem, pre nego što posao počne da se izvršava, potrebno je učitati samo deo segmenata koji će se izvršavati. Ako se tokom rada otkrije da stranica kojoj se pristupa nije u memoriji, procesor obaveštava operativni sistem da po odgovarajućem algoritmu zamene učita potrebnu stranicu u glavnu memoriju; operativni sistem takođe može privremeno neiskorišćene stranice izbaciti na spoljnu memoriju.
2. Upravljanje memorijom sa zahtevnom segmentacijom: slično zahtevnom straničenju; pre nego što posao krene, učitava se samo deo segmenata koji se izvršavaju; tokom rada se prekidom za zahtevno učitavanje dinamički unose segmenti kojima se pristupa, a nisu u memoriji; kada je memorija puna, a potreban je novi segment, po funkciji zamene izbacuje se neki segment kako bi se napravilo mesto za novi.
3. Upravljanje memorijom sa zahtevnom segmentacijom i straničenjem

Za bilo koju od ovih realizacija, opšte nam treba:

Određeni kapacitet memorije i spoljne memorije: pri učitavanju programa dovoljno je deo programa učitati u memoriju, a ostatak ostaviti na spoljnoj memoriji, nakon čega se program može izvršavati;

Prekid zbog nedostatka stranice (page fault)

Ako instrukcija koja treba da se izvrši ili podaci kojima se pristupa nisu u memoriji (tzv. nedostatak stranice ili segmenta), procesor obaveštava operativni sistem da u memoriju učita odgovarajuću stranicu ili segment, nakon čega program nastavlja izvršavanje.

U sistemu sa straničenjem, virtuelna stranica može biti ili u fizičkoj memoriji ili na disku.

Ako virtuelna adresa koju CPU generiše odgovara stranici koja nije u fizičkoj memoriji, nastaje prekid zbog nedostatka stranice; servisna rutina tog prekida pronalazi potrebnu virtuelnu stranicu i učitava je u memoriju.

Koraci obrade prekida nedostatka stranice su u sledećem prikazu (izostavljeni su mnogi međukoraci, ostavljeni samo ključni):

Algoritmi zamene stranica

Kada dođe do prekida nedostatka stranice, a u memoriji nema slobodne stranice, operativni sistem mora izabrati neku stranicu iz memorije i izbaciti je, kako bi napravio mesto za stranicu koja se tek učitava.

Pravilo po kojem se bira stranica koja se izbacuje zove se algoritam zamene stranica; algoritam zamene može se posmatrati kao pravilo za eliminaciju stranica.

• OPT (Optimalni algoritam zamene stranica): stranica koja se izbacuje je ona koja se nikada više neće koristiti, ili se najduže neće koristiti; to bi dao najnižu stopu promašaja. Pošto se ne može predvideti koja će stranica u memoriji biti najduže nekorišćena, ovaj algoritam se ne može implementirati i koristi se samo kao mera za ocenu drugih algoritama.

• FIFO (First In First Out): uvek izbacuje stranicu koja je prva ušla u memoriju, odnosno stranicu koja je najduže u memoriji.

• LRU (Least Recently Used): LRU svakoj stranici dodeljuje polje za praćenje vremena T proteklog od poslednjeg pristupa; kada stranicu treba izbaciti, bira se ona sa najvećim T — stranica koja je najduže bila nekorišćena.

• LFU (Least Frequently Used): izbacuje stranicu koja je u prethodnom periodu najređe korišćena.

Princip lokalnosti

Princip lokalnosti je osnova tehnike virtuelne memorije; upravo zato što programi ispoljavaju lokalnost, moguće je deo programa učitati u memoriju i započeti izvršavanje.

Lokalnost se ispoljava na dva načina:

1. Vremenska lokalnost: ako se neka instrukcija jednom izvrši, uskoro će se verovatno izvršiti ponovo; ako joj se jednom pristupilo, uskoro će se verovatno pristupiti ponovo. Tipičan uzrok vremenske lokalnosti jeste postojanje velikog broja petlji u programu.
2. Prostorna lokalnost: kada program jednom pristupi nekoj memorijskoj jedinici, uskoro će pristupiti i obližnjim jedinicama — odnosno adrese kojima program pristupa u određenom periodu mogu biti koncentrisane u ograničenom opsegu. Razlog je što se instrukcije obično nalaze i izvršavaju sekvencijalno, a podaci se često čuvaju u grozdovima kao vektori, nizovi, tabele i sl.

Vremenska lokalnost ostvaruje se čuvanjem nedavno korišćenih instrukcija i podataka u keš memoriji i korišćenjem hijerarhije keša.

Prostorna lokalnost obično se ostvaruje većim kešom i integracijom mehanizma preduzimanja (prefetch) u kontrolnu logiku keša.

Tabela stranica

Operativni sistem deli virtuelnu memoriju na blokove — svaki blok je jedna stranica (Page); i fizička memorija se deli na blokove — svaki blok se zove okvir (Frame).

Mapiranje stranica u okvire zahteva strukturu koja se zove tabela stranica.

Gornji prikaz pokazuje odnos između Page, Frame i tabele stranica (PageTable).

Veličina stranice i okvira obično su jednake; u tabeli stranica za svaku stranicu upisan je broj okvira koji joj odgovara.

I tabela stranica zauzima memorijski prostor: na primer, ako je virtuelna memorija velika 10G, a stranica 4K, potrebno je 10G/4K = 2621440 stavki.

Ako je svaka stavka 64 bita, ukupno je potrebno 20480K = 20M za tabelu stranica; operativni sistem u memoriji izdvaja male oblasti za tabelu stranica i o njoj brine.

Tabela stranica čuva mapiranje virtuelnih adresa u fizičke.

Pri svakom korišćenju memorije, virtuelna adresa mora se preračunati u fizičku; računanje ima tri koraka:

• Izračuna se broj stranice iz virtuelne adrese;

• Pregleda se tabela stranica i na osnovu broja stranice nalazi broj okvira;

• Virtuelna adresa se preračuna u fizičku.

Višenivojska tabela stranica

Uvođenje višenivojske tabele stranica ima za cilj da izbegne držanje cele tabele stalno u memoriji, gde bi zauzimala previše prostora — naročito one delove tabele koji uopšte nisu potrebni.

Jednonivojska tabela stranica:

Ako fizička memorija ukupno ima 1048576 stranica, tabela stranica zauzima 1048576 * 4B = 4M.

Drugim rečima, potrebno je 4M neprekidne memorije za smeštanje te tabele — to je jednonivojska tabela.

Sa porastom virtuelnog adresnog prostora raste i potreban neprekidan prostor za tabelu, što pri napetosti memorije ili većoj fragmentaciji donosi dodatni trošak.

Adresiranje preko tabele stranica služi se registrom za određivanje adrese jednonivojske tabele, pa adresa jednonivojske tabele mora pokazivati na određenu fizičku stranicu — inače bi došlo do greške; zato se kod jednonivojske tabele svi njeni delovi moraju učitati.

Dvonivojska tabela stranica:

Sa dvonivojskom tabelom potrebno je učitati samo tabelu direktorijuma stranica (jednonivojsku tabelu) veličine 4K, koja može upravljati sa 1024 dvonivojske tabele stranica.

Možda će te zapitati: i tih 1024 dvonivojske tabele zauzimaju memorijski prostor, pa sada treba 4MB+4KB — čak i više.

U stvari, dvonivojska tabela ne mora obavezno da bude u memoriji; u memoriji je dovoljno držati samo adresu jednonivojske tabele u registru, dok se dvonivojske tabele mogu preko prekida nedostatka stranice prebacivati iz spoljne u glavnu memoriju.

Višenivojska tabela stranica tipičan je primer razmene vremena za prostor.

TLB (brza tabela)

Da bi se ubrzao prevod virtuelnih adresa u fizičke, operativni sistem na rešenje sa tabelom stranica nadograđuje brzu tabelu (TLB) koja ubrzava taj prevod.

Brza tabela može se shvatiti kao poseban keš, čiji je sadržaj deo ili cela tabela stranica. Kao keš tabele stranica, služi istoj svrsi, ali povećava brzinu pristupa. Pošto se pri adresiranju preko tabele stranica CPU pri čitanju/pisanju podataka dva puta pristupa glavnoj memoriji, postojanjem brze tabele ponekad je dovoljno jednom pristupiti kešu i jednom glavnoj memoriji — čime se ubrzava pretraga i povećava brzina izvršavanja instrukcija.

Tok adresnog prevoda sa brzom tabelom:

1. Broj stranice iz virtuelne adrese potraži u brzoj tabeli;
2. Ako je stranica u brzoj tabeli, pročitaj njenu fizičku adresu;
3. Ako nije, pristupi tabeli stranica u memoriji, iz nje uzmi fizičku adresu i dodaj tu mapu u brzu tabelu;
4. Kada se brza tabela popuni, a treba upisati novu stranicu, po određenoj strategiji zamene izbaci jednu stranicu iz brze tabele.

Jedinica za upravljanje memorijom

Unutar CPU-a nalazi se mali uređaj — jedinica za upravljanje memorijom (MMU).

![](https://img-blog.csdnimg.cn/2da3a2f130cf415cb0b42c19fda70f30.png">

Kada CPU treba da izvrši instrukciju koja obuhvata čitanje ili pisanje po memoriji, CPU prosleđuje virtuelnu adresu MMU-u, koji automatski obavlja preračun u fizičku adresu; zatim, pošto je povezan na adresnu magistralu, MMU pomaže CPU-u da operiše nad stvarnom adresom.

MMU se razlikuje od CPU-a do CPU-a, pa se ovde javlja mnogo problema prenosivosti.

Rešavanje problema prenosivosti donosi i veliki obim posla i zahteva visoko programersko umeće.

Algoritmi dinamičke alokacije particija

Algoritmi alokacije memorije, grubo rečeno, dele se na: kontinualnu i nekontinualnu alokaciju.

Kontinualna alokacija podrazumeva smeštanje programa u memoriju celog, po redosledu; kontinualna alokacija može biti fiksna particija ili dinamička particija.

Nekontinualna alokacija znači da se program po određenom pravilu deli na delove — očigledno je to efikasnije, te savremeni operativni sistemi memorijsku alokaciju obavljaju na taj način.

Dinamička alokacija particija znači da memorija na početku nije podeljena na oblasti, već se pri učitavanju procesa memorijski prostor dinamički deli prema veličini procesa, čime se povećava iskorišćenost memorije i smanjuje veličina fragmentacije.

Postoje četiri algoritma dinamičke alokacije particija:

First Fit

Slobodne particije se povezuju u listu po rastućoj adresi; pri alokaciji se redom pretražuje i prva slobodna particija koja zadovoljava veličinu dodeljuje se.

![](https://img-blog.csdnimg.cn/e5cf8456bf9941758f6a1bd2ba1c351a.png">

Next Fit

Poznat i kao cirkularni First Fit; nastao je iz First Fit-a, s tom razlikom što pretragu pri alokaciji nastavlja od mesta gde je prethodna pretraga stala.

Best Fit

Slobodne particije povezuju se u listu po rastućoj veličini; prva particija koja zadovoljava zahtev dodeljuje se.

![](https://img-blog.csdnimg.cn/585a5ba3e4ad4eaeae77ebd1d8b02b32.png">

Worst Fit

Poznat i kao algoritam maksimalnog uklapanja; slobodne particije povezuju se po opadajućoj veličini; prva particija koja zadovoljava zahtev (odnosno najveća) dodeljuje se.

Rezime

First Fit je najjednostavniji i obično i najbolji i najbrži; mana mu je što na nižim adresama memorije stvara mnogo malih slobodnih particija kroz koje pretraga uvek mora da prođe, što povećava trošak pretrage.

Next Fit pokušava da reši taj problem, ali u praksi često dovodi do toga da se prostor na kraju memorije fragmentiše u sitne delove — obično daje lošije rezultate od First Fit-a.

Best Fit stvara mnogo fragmenata; Worst Fit ne ostavlja velike slobodne blokove.

Preklapanje memorije (Overlay)

Tehnike preklapanja i razmene dve su metode kojima program proširuje memoriju.

U ranim sistemima glavna memorija bila je vrlo mala; iako je u njoj bio samo jedan korisnički program, događalo se da korisnički proces ne stane u memoriju — ovaj problem rešava preklapanje.

Osnovna ideja preklapanja:

Pošto program tokom rada ne pristupa svim svojim delovima i podacima istovremeno (posebno veliki programi), korisnički prostor može se podeliti na jednu fiksnu zonu i više zona preklapanja.

Deo koji je stalno aktivan smešta se u fiksnu zonu, a ostatak se po relacijama poziva dele na segmente.

Segmenti koji će uskoro biti potrebni smeštaju se u zonu preklapanja, dok ostali idu na spoljnu memoriju; pre nego što im se zatreba pristup, sistem ih dovodi u zonu preklapanja, zamenjujući prethodni segment.

Preklapanje ukida ograničenje da ceo proces mora biti u memoriji da bi se izvršavao, ali ako ukupna količina kôda programa koji istovremeno radi premašuje glavnu memoriju, izvršavanje i dalje nije moguće.

Razmena memorije (Swap)

Osnovna ideja razmene

Program u stanju čekanja (ili onaj kome je, po pravilima CPU raspoređivanja, oduzeto pravo na rad) prenosi se iz memorije na spoljnu memoriju, čime se memorija oslobađa — taj proces nazivamo izbacivanjem (swap-out);

Program koji je spreman da se takmiči za CPU prebacuje se sa spoljne memorije u glavnu — taj proces nazivamo ubacivanjem (swap-in).

Na primer, višeprogramsko okruženje sa CPU-om koji koristi rotaciju vremenskih isečaka.

Kada istekne isečak, menadžer memorije izbacuje proces koji je upravo radio, a ubacuje drugi proces u oslobođeni memorijski prostor.

Istovremeno, CPU raspoređivač može dodeliti isečak nekom drugom procesu koji je već u memoriji.

Svaki proces, po potrošnji isečka, razmenjuje se sa drugim procesom.

U idealnom slučaju razmena je dovoljno brza, tako da u memoriji uvek ima procesa koji se može izvršavati.

Tehnika razmene se uglavnom koristi između različitih procesa (ili poslova), dok se preklapanje koristi unutar istog programa ili procesa.

Pošto preklapanje zahteva da se precizira struktura preklapanja između segmenata programa, ona nije transparentna za korisnika i programera — pa problem memorije koja ne može da primi korisnički program savremeni operativni sistemi rešavaju tehnikom virtuelne memorije.

Tako je preklapanje ostalo istorija, dok razmena i u savremenim operativnim sistemima zadržava snažnu ulogu.

Najčešća pitanja na intervjuu

Razlika između procesa i niti

Operativni sistem sistemskih resursa (CPU isečke, memoriju itd.) dodeljuje po procesima; proces je najmanja jedinica dodele resursa.

Raspoređivanje: nit je osnovna jedinica CPU raspoređivanja, dok je proces osnovna jedinica koja drži resurse.

Konkurentnost: ne samo da procesi mogu konkurentno da se izvršavaju, već i više niti istog procesa mogu.

Resursi:

Proces je nezavisna jedinica koja drži resurse; nit sama ne drži sistemske resurse, ali može pristupati resursima procesa kojem pripada.

Proces održava resurse programa (statične), kao što su adresni prostor, skup otvorenih fajl deskriptora, stanje fajlsistema, handler-i signala itd.;

Nit održava resurse vezane za izvršavanje (dinamične), kao što su stek izvršavanja, kontrolne informacije vezane za raspoređivanje, skup signala na čekanju itd.

Sistemski trošak:

Pri kreiranju ili uništavanju procesa sistem mora da alocira i dealocira resurse, pa je trošak znatno veći nego pri kreiranju ili uništavanju niti.

Međutim, proces ima sopstveni adresni prostor, pa ako jedan proces padne, u zaštićenom režimu ne utiče na druge procese; nit je samo drugačija putanja izvršavanja unutar procesa.

Nit ima sopstveni stek i lokalne promenljive, ali niti nemaju zasebne adresne prostore — pad procesa znači pad svih njegovih niti, pa su multiprocesni programi robusniji od multinitnih. Sa druge strane, promena procesa troši više resursa i niže je efikasnost.

Koliko niti može kreirati jedan proces

Teorijski, proces na raspolaganju ima 2G virtuelnog prostora; po podrazumevanim podešavanjima veličina steka niti je 1MB, te se teorijski može kreirati najviše 2048 niti.

Za više od 2048 potrebno je izmeniti podešavanja kompajlera.

U uobičajenim uslovima toliko niti nije potrebno; previše niti dovodi do gubitka vremena na njihovo smenjivanje i negativno utiče na efikasnost programa.

Koja je razlika između spoljnog prekida i izuzetka

Spoljni prekid izazvan je događajima izvan instrukcija CPU-a — npr. I/O prekid završetka, koji signalizira da je obrada ulaza/izlaza završena i da procesor može poslati sledeći I/O zahtev; tu spadaju i prekid sata, prekid konzole i sl.

Izuzetak je pak izazvan internim događajima pri izvršavanju instrukcija CPU-a — npr. ilegalan opkod, prelazak granice adrese, aritmetički overflow i sl.

Četiri metoda rešavanja Hash kolizija

Otvoreno adresiranje

• Otvoreno adresiranje znači da, čim dođe do kolizije, traži sledeća prazna hash adresa; ako je hash tabela dovoljno velika, prazna adresa će se uvek naći i zapis se u nju smešta.

Metod ulančanih lista

• Svaka jedinica hash tabele predstavlja prvi čvor liste; svi elementi sa hash adresom i formiraju sinonimnu listu. Drugim rečima, pri koliziji ključ se dodaje na kraj liste čiji je prvi čvor ta jedinica.

Ponovljeno heširanje

• Kada dođe do kolizije hash adrese, izračunava se nova adresa drugom hash funkcijom, i tako dok kolizija ne nestane.

Formiranje zajedničkog preliva

• Hash tabela se deli na osnovnu i prelivalnu tabelu; svi elementi u koliziji idu u prelivalnu.

Koje su zajedničke tačke, a koje razlike između straničenja i segmentacije

Zajedničke tačke

• I straničenje i segmentacija služe povećanju iskorišćenosti memorije i smanjenju fragmentacije.
• I stranice i segmenti diskretno se skladište, pa su oba metoda diskretna alokacija memorije; međutim, unutar svake stranice i segmenta memorija je neprekidna.

Razlike

• Veličina stranice je fiksna i određuje je operativni sistem; veličina segmenta nije fiksna i zavisi od programa koji se izvršava.
• Straničenje služi isključivo potrebama upravljanja memorijom operativnog sistema, dok je segment logička jedinica informacije — u programu se može pojaviti kao segment kôda, segment podataka — i bolje odgovara korisničkim potrebama.
• Straničenje jeste jednodimenzionalni adresni prostor, dok je segmentacija dvodimenzionalna.

Predstavljanje nekoliko tipičnih brava

RW brava (read-write lock)

• može se istovremeno čitati više puta
• pisci se međusobno isključuju (dozvoljen samo jedan pisac, niti smeju istovremeno čitaoci i pisci)
• pisac ima prioritet nad čitaocem (čim se pojavi pisac, naredni čitaoci moraju čekati; pri buđenju se prvo daje prednost piscu)

Mutex

Samo jedna nit u jednom trenutku može držati mutex, ostale moraju čekati.

Mutex pri neuspešnom zauzeću brave aktivno predaje CPU i prelazi u san, dok stanje brave ne promeni, kada se budi. Pošto operativni sistem upravlja raspoređivanjem niti i, radi buđenja blokirane niti ili procesa kada se stanje brave promeni, brava se prepušta operativnom sistemu na upravljanje, mutex pri zaključavanju uključuje promenu konteksta.

Stvarna efikasnost mutexa je prihvatljiva — vreme zaključavanja je oko 100ns; jedna moguća implementacija mutexa jeste da prvo određeno vreme spinuje, a tek kada spinovanje pređe prag, nit ide na spavanje, pa u konkurentnom računanju (gde se brava drži kratko) mutex može biti podjednako dobar kao spinlock.

Uslovna promenljiva (condition variable)

Jedna očigledna mana mutexa jeste što ima samo dva stanja: zaključano i otključano.

Uslovna promenljiva to nadoknađuje tako što dozvoljava niti da se blokiraju i čekaju signal druge niti; često se koristi zajedno sa mutexom, radi izbegavanja trka (race conditions).

Kada uslov nije ispunjen, nit obično otključa mutex, blokira se i čeka da se uslov promeni.

Čim neka druga nit promeni uslovnu promenljivu, ona će obavestiti odgovarajuću uslovnu promenljivu da probudi jednu ili više niti koje čekaju na njoj.

Ukratko: mutex je mehanizam međusobnog isključenja niti, dok je uslovna promenljiva mehanizam sinhronizacije.

Spinlock

Ako nit ne uspe da zauzme bravu, ne odustaje odmah od CPU isečka, već u petlji pokušava da je zauzme, sve dok ne uspe.

Ako druga nit dugo drži bravu, spinovanje troši CPU na uzaludan rad, ali spinlock se obično koristi u situacijama gde se brava drži vrlo kratko, pa je tada efikasan.

Iako je efikasniji od mutexa, ima i nedostataka:

• Spinlock stalno zauzima CPU; dok ne dobije bravu, stalno se vrti, čime drži CPU. Ako bravu ne dobije brzo, svakako smanjuje efikasnost CPU-a.
• Spinlock može dovesti do mrtve blokade, posebno pri rekurzivnom pozivu.

Kako pokrenuti proces u pozadini

1. Iza komande dodajte &; time se komanda zapravo stavlja u red poslova.

2. ctrl + z suspenduje proces; komandom jobs vidite broj, a zatim bg %broj proces nastavlja rad u pozadini.

3. nohup + &: standardni izlaz i standardna greška se preusmeravaju u fajl nohup.out, a ignorisu se svi signali SIGHUP.

nohup ping www.ibm.com &

4. Ispred komande dodajte setsid: time proces-roditelj postaje init proces, pa komanda nije pogođena SIGHUP signalom.

[root@pvcent107 ~]## setsid ping www.ibm.com
[root@pvcent107 ~]## ps -ef |grep www.ibm.com
root     31094     1  0 07:28 ?        00:00:00 ping www.ibm.com
root     31102 29217  0 07:29 pts/4    00:00:00 grep www.ibm.com

Gornji primer: PID našeg procesa jeste 31094, a njegov PPID jeste 1 (to je ID init procesa), a ne ID tekućeg terminala.

5. Komandu sa & stavite unutar zagrada (), čime proces takođe nije pogođen HUP signalom.

[root@pvcent107 ~]## (ping www.ibm.com &)

Razlika između izuzetka i prekida

Prekid

Kada pritisnemo taster na tastaturi nastaje prekid; kada disk završi čitanje ili pisanje podataka, takođe nastaje prekid. Treba znati da prekide generišu hardverski uređaji — fizički gledano to su električni signali koji se preko kontrolera prekida šalju CPU-u; CPU zatim procenjuje od kojeg hardverskog uređaja dolazi prekid (to je definisano u kernelu) i konačno ga prosleđuje kernelu koji obrađuje prekid.

Sledeći prikaz ilustruje tok obrade prekida:

![](https://img-blog.csdnimg.cn/6c0a43b5915e44bf8d05b6d871fd3b25.png">

Izuzetak

Pri obradi programa, ako programa nema u memoriji, CPU generiše izuzetak nedostatka stranice; kada pri deljenju delilac bude 0, nastaje izuzetak deljenja nulom.

Izuzetke generiše CPU, a zatim ih prosleđuje kernelu radi obrade.

Sledeći prikaz ilustruje tok obrade izuzetka:

Zajedničke tačke

• Na kraju oboje CPU prosleđuje kernelu, koji ih obrađuje
• Tok obrade je slično projektovan

Razlike

• Razlikuje se izvor: izuzetke generiše CPU, a prekide hardverski uređaji
• Kernel mora da poziva različite rutine obrade u zavisnosti od toga da li je u pitanju izuzetak ili prekid
• Prekid nije sinhron sa satom, što znači da može doći u bilo kom trenutku; izuzetak, pošto ga generiše CPU, sinhron je sa satom
• Pri obradi prekida nalazimo se u kontekstu prekida; pri obradi izuzetka u kontekstu procesa

---

Autor: Yueban Feiyu, izvor: https://mp.weixin.qq.com/s/G9ZqwEMxjrG5LbgYwM5ACQ