pismeni Flashcards
Što je operacijski sustav, od čega se sastoji i čemu služi?
Program ili skup programa koji upravljaju svim uređajima u sustavu i omogućuju jednostavno sučelje korisničkim programima prema sklopovlju. Današnji operacijski sustavi omogućuju višekorisnički i višezadaćni rad.
Sastoji se od:
1) jezgre operacijskog sustava (eng. kernel) – dio koji upravlja sklopovljem
2) ljuske za izvođenje programa (eng. command shell) - spona korisničkog sučelja i kernela
3) datotečnog sustav (eng. file system)
4) sustavskih programa (eng. system utilities) - programi i programski jezici za dogradnju i razvoj OS-a
5) korisničkih programa - isporučuju se zajedno sa OS-om da bi korisniku bilo dostupno što više usluga bez
dodatne nabave programa
Navedite, skicirajte i ukratko objasnite razine između kojih je smješten OS.
Compilers | Editors | Command interpreter
——————————————————————-
Operating system
——————————————————————-
Machine language
——————————————————————-
Microarchitecture
——————————————————————-
physical devices
——————————————————————-
Smještaj OS-a:
– fizička razina - uređaji (IC-i, sklopovi, PCB, ožičenja, posebne komp.)
– razina mikroarhitekture - tu fizički uređaji zajedno formiraju pojedine funkcijske cjeline: registri - ALU – CPU
– razina strojnog jezika - mikroprogram u asembleru, upravlja tijekom podataka između registara CPU i registara U/I
uređaja
– operacijski sustav - sloj programske podrške koji djelomično skriva ovu sklopovsku složenost i programeru omogućuje
skup instrukcija kojima će lakše pristupiti do tog sklopovlja
– ostali sustavski programi - ljuska, kor. sučelje, prevoditelji, editori, ostali
– korisnički programi - kupljeni, “kupljeni” ili pisani od strane korisnika
Navedite 5 generacija operacijskih sustava i ukratko opišite njihova osnovna obilježja.
Prva generacija(1945 - 1955):
relejna tehnologija I vakumske cijevi, bušene kartice
Druga generacija(1955 - 1965):
Tranzistori,batch sustavi, pojavljuje se FORTRAN (OS), a podatke je bilo moguće snimiti na magnetske trake
Treća generacija(1965 - 1980):
pojava IC-a, multiprogramiranje, time sharing, spooling, MULTICS,UNIX,MINIX,Linux
Multiprogramiranje je dijeljenje memorije za različite poslove. (Uz to CPU ne stoji dok čeka podatke sa U/I sučelja. Nego dok čeka, obavlja drugi posao.) Spooling (Simultaneous Peripheral Operation On Line) - pri završetku posla, se učitava sljedeći posao.
Time Sharing je dijeljenje vremena korištenja CPU-a svakom poslu.
Četvrta generacija(1980 - danas):
LSI čipovi, osobna računala, mikroračunala
pojava operacijskih sustava MS-DOS,WIN NT/98/ME/2000/XP,Vista,W7,W8,W10
UNIX: X Windows, Motif, Niz Linux distribucija…
NOS (mrežni), DOS (raspodijeljeni)
Peta generacija(1990 - danas):
PDA, smartphone, Android iOS, Windows Phone, Symbian, RIM Blackberry
Navedite i ukratko opišite najznačajnije vrste operacijskih sustava prema računalnoj okolini i prema namjeni.
Operacijski sustavi velikih računala (mainframe, vratili se kao veliki web poslužitelji)
- slijed poslova, obrada transakcija, podjela vremena, posluga brojnih korisnika
Operacijski sustavi poslužitelja
- jači PC-i, radne stanice ili mainframe računala, posluga velikog broja korisnika koji dijele sklopovlje, programe i podatke
Višeprocesorski operacijski sustavi
- razlika u načinu spajanja i dijeljenu resursa: paralelna računala, višeračunalni i višeprocesorski sustavi (posebnost: komunikacija, spajanje)
Operacijski sustavi osobnih računala
- dobro sučelje prema korisniku (Windows, Linux)
Operacijski sustavi za rad u stvarnom vremenu (real-time)
- strogi, ublaženi i postojani vremenski zahtjevi, mobilni, ECos
Operacijski sustavi ugradbenih računalnih sustava (embedded)
- smanjeni resursi: kućanski aparati, TV, automobili: Windows CE, Windows Embedded, TV OS, Linux, Embedded Linux, QNX, VxWorks
Operacijski sustavi senzorskih čvorova
- Tiny OS
Operacijski sustavi pametnih kartica (smart card)
- pokreću se na kartici, JVM interpreter, Java Appleti, jedna ili više jednostavnih mogućnosti
Operacijski sustavi ručnih računala i mobilnih uređaja
- PDA, mali uređaji, pametni telefoni
Ukratko objasnite što je jezgrin, a što korisnički način rada operacijskog sustava i kako se postižu.
Jezgrin način rada ima ovlasti pristupati svim mogućnostima sklopovlja
Korisnički način rada je ograničen način rada I štiti sklopovlje od korisnika, samo podskup instrukcija i podskup mogučnosti
Navedite i ukratko opišite svaki od koncepata (načela) rada OS-a.
1) Procesi - proces je program u izvođenju. Svakom procesu pridružujemo:
- adresni prostor, odnosno listu memorijskih lokacija u koje i iz kojih proces može pisati i čitati; adresni prostor sadrži izvršni program, podatke programa i stog
- Skup registara (PC, SP i drugi) (Program Counter, Stack Pointer)
prekinuti proces može se ponovo pokrenuti samo ako su svi navedeni podaci sačuvani (čuvaju se u tablici procesa)
2) Zastoji (deadlocks)
- kada dva ili više procesa međudjeluju, mogu izazvati situacije iz kojih ne mogu izaći.
- Primjer: Proces A treba resurs D1, Proces B treba resurs D2, potom Proces A treba resurs D2, i Proces B treba resurs D1, time se dogodi da proces A nemože dobiti resurs D2 dok proces B ga koristi, a proces B neće otpustiti resurs D2, dok ne dobije D1. I time se dobije prekid.
3) Rukovanje memorijom
- zbog više programa istovremeno u memoriji OS mora rukovati memorijom i zaštiti glavnu memoriju (fizička i prividna (virtualna) memorija), te osigurati memorijski prostor procesima
4) Ulaz/izlaz podataka
- OS ima U/I podsustav koji brine o vrlo različitim i zahtjevnim U/I uređajima (pogonski programi – dio neovisan o uređaju, a dio poseban za svaki uređaj i za svakog proizvođača)
5) Datotečni sustav
- sakriva složenost U/I uređaja i pruža korisniku čisti apstraktni model datoteka i direktorija neovisnih o uređaju
- organiziran hijerarhijski u obliku stabala
- definirane ovlasti korisnika
- “UNIX – mounting file system: omogućuje rad s prenosivim U/I uređajima (CD, FDD)
- Posebne datoteke: UNIX – posebne datoteke omogućuju pristup I/O uređajima kao datotekama
- postoje blok datoteke (diskovi) i znakovne datoteke (pisač, modem)
- Cjevovod - vrsta pseudo-datoteke koja se može koristiti za spajanje dva procesa -
- ako proces A želi poslati podatke procesu B, on piše u cjevovod kao u izlaznu datoteku -
- proces B može čitati te podatke iz cjevovoda kao iz ulazne datoteke
6) Sigurnost
- tajni podaci dostupni samo ovlaštenim korisnicima
- datoteke u UNIX-u zaštićene 9-bitnim binarnim kodom: 3-bitno polje i to jedno za vlasnika, jedno za druge članove vlasnikove grupe i jedno za sve ostale; bitovi poznati kao rwx bitovi (read, write, execute)
- zaštita od nametljivaca (ljudi, virusa)
7) Ljuska (shell)
- OS je kod koji izvodi sustavske pozive
- UNIX ima shell interpreter naredbi – shell (sh, csh, ksh….), odzivni znak (prompt)
8) Recikliranje koncepata
Što je sustavski poziv? Nabrojite ili skicirajte korake nastanka sustavskog poziva. Pokažite na nekom primjeru izvođenje sustavskog poziva (npr. printf() – write ())
Sustavski poziv je sučelje između OS-a i korisničkih programa definirano skupom sustavskih poziva koje omogućuje OS.
Ti pozivi različiti su za svaki OS, pri čemu trebaju zadovoljiti zajedničke zahtjeve i posebnosti svakog OS-a.
Ti pozivi su ovisni o stroju.
Dok su oni često ostvareni u asembleru, biblioteka procedura omogućuje njihovo korištenje iz C-a i drugih VPJ.
(Viših Programskih Jezika)
Koraci nastanka sustavskih poziva:
1., 2. i 3. Pozivajući program najprije stavlja parametre na stog (1. i 2. parametar pozivaju se po vrijednosti, a treći po referenci)
4. Poziv bibliotečne procedure (instrukcija jednaka za pozivanje svih proc.)
5. Bibliotečna procedura stavlja broj sustavskog poziva u registar.
6. OS izvodi instrukciju TRAP s ciljem prijelaza iz korisničkog u jezgrin način rada.
7. Jezgrin kod utvrđuje broj poziva i dodjeljuje ga odgovarajućem rukovatelju poziva (handleru)
8. Pokreće se rukovatelj sustavskog poziva.
9. Kada rukovatelj odradi, nadzor se vraća bibliotečnoj proceduri korisničkog prostora, odnosno instrukciji koja slijedi TRAP instrukciju. (software interrupt)
10. Ta procedura vraća se na razinu korisničkog programa.
11. Za potpuni završetak, korisnički program briše stog i to poslije svakog poziva procedure.
Primjer:
void typefile(char* filename){
int fd, nread;
char buf[1024];
fd = open(filename,O_RDONLY);
if(fd == -1){
perror(filename);
return;
}
while( (nread = read(fd, buf, sizeof(buf) ) ) > 0 )
write(1,buf,nread);
close(fd);
}
Navedite i objasnite barem po dva sustavska poziva za:
a) rukovanje procesima
b) rad s datotekama
c) rad s direktorijima
d) razne zadaće
rukovanje procesima: fork (kreira novi proces dijete kao kopija procesa roditelja), waitpid (čeka da dijete završi)
rad s datotekama: close, open
rad s direktorijima: mkdir (stvara novi direktorij), rmdir (briše prazan direktorij)
razne zadaće: kill (ubija proces), time (vraća vrijeme u sekundama)
a) rukovanje procesima
- fork
- kreiranje novog procesa djeteta kao kopije procesa roditelja sa svim opisnicima, registrima itd
- Novi proces nastavlja samostalan put izvođenja, ali im je zajednički tekst programa.
- fork vraća vrijednost koja je 0 za proces dijete i odgovara njegovom PID-u, dok je za roditelja 1 (tako ih sustav razlikuje).
- nakon fork, dijete često treba izvršavati kod različit od roditelja(slika-Shell): čita naredbu s terminala, stvara proces dijete, čeka dijete da izvede naredbu i kada dijete završi, čita sljedeću naredbu s terminala.
- zbog čekanja da dijete (djeca) završi(e), roditelj izvodi poziv waitpid, a čeka postavljajući prvi parametar u -1.
- Kada waitpid završi, adresa na koju pokazuje parametar statloc, bit će postavljena na status za izlazak djeteta (exit).
- exit
- proces ga koristi kad završi izvođenje.
- Ima 1 parametar (0 - 255), koji se vraća roditelju preko statloc u waitpid pozivu.
b) rad s datotekama
- open
- zahtjeva ime datoteke, apsolutnu ili relativnu putanju i kod načina otvaranja:
- za čitanje(O_RDONLY),
- pisanje (O_WRONLY),
- ili oboje (O_RDWR),
- za kreiranje (O_CREATE).
- close
- zatvaranje datoteke, nakon čega je moguće ponovno otvaranje s open.
- lseek
- mijenja vrijednost pokazivača trenutnog položaja datoteke kod uzastopnog pisanja i čitanja i smješta ga u poziciju
- Ima 3 parametra: (opisnik datoteke, položaj datoteke relativni položaj datoteke u odnosu na njen početak)
- stat
- za dohvaćanje informacija o vrsti datoteke (obična, posebna, direktorij itd.), duljini, vremenu izmjene itd., a parametri su ime datoteke i pokazivač na strukturu gdje će se smjestiti informacija
c) rad s direktorijima
- mkdir i rmdir
- kreiranje i uklanjanje praznog direktorija
- link i unlink
- omogućuje da se ista datoteka pojavljuje pod više imena u različitim direktorijima (dijeljenje datoteka među više korisnika), unlink obrnuto.
- mount i unmount
- Dva sustava datoteka mogu biti spojeni u jedan, unmount obrnuto.
d) razne zadaće
- chdir
- mijenja trenutni radni direktorij
- chmod
- mijenja način korištenja datoteka (mode)
- kill
- način na koji korisnici ili korisnički procesi šalju signale.
- Ako je proces pripremljen za hvatanje nekog signala, kada se signal pojavi, pokreće se rukovatelj signala.
- Ako nije pripremljen za rukovanje signalom, njegov dolazak ubija proces.
- time
- vraća trenutno vrijeme u sekundama, a 0 odgovara 1.1.1970. 32-bitni PC ima maks. vrijednost vremena 232-1 sekundu (preko 136 godina – do 2106.)
Objasnite osnovne razlike između sustavskih poziva u Unix-u/Linux-u i Windowsima.
- UNIX program sastoji se od koda koji nešto radi, a sustavski pozivi omogućuju pojedinu uslugu
- Windows programi su obično pokretani događajima, odnosno glavni program čeka da dođe do nekog događaja, a zatim poziva proceduru koja će ga poslužiti.
- Obično su događaji: pritisak tipke, pomak miša, pritisak tipke miša, umetanje diska itd. Rukovatelji se pozivaju kako bi obradili događaj, osvježili zaslon i obnovili unutarnje stanje programa.
- UNIX ima 1-1 vezu između sustavskog poziva i procedure iz biblioteke koja ga poslužuje.
- u Windowsima su pozivi biblioteke i sustavski pozivi vrlo isprepleteni i povezani.
- Microsoft je definirao skup procedura zvanih Win32 API (Application Program Interface), a programer ih mora koristiti kako bi tražio usluge od OSa.
- Postoji na tisuće Win32 API poziva, pa je u Windowsima često nemoguće znati što je sustavski poziv (omogućen od jezgre), a što poziv biblioteke (u korisničkom prostoru)
Što su procesi i kako se modeliraju?
Procesi su apstrakcije programa u izvođenju. Prilikom izvođenja imamo dojam pseudoparalelizma.
(zbog brzine izvođenja čini nam se da se procesi izvode paralelno, no oni se zapravo izvode jedan po jedan.)
Model procesa:
- Svi izvršni programi računala (ponekad uključujući i OS), organizirani su kao određeni broj slijednih procesa
Proces
- program u izvođenju, uključujući trenutna stanja PC, registara i varijabli.
- Recimo, svaki proces ima svoju virtualnu CPU, a zapravo se na njoj procesi brzo izmjenjuju.
Navedite uobičajene događaje (i primjere) koji dovode do stvaranja procesa, te objasnite razliku u stvaranju procesa u UNIX-u/Linux-u i Windowsima.
- Inicijalizacija sustava
- kod boot-a stvaraju se prednji (sučelje prema korisniku)
- i pozadinski(daemons) (primanje e-mail-a, zahtjev za web stranicom) procesi.
- Lista procesa: UNIX - ps, Windows - CTRL-ALT-DEL CTRL-SHIFT-ESC (prečac za Task Manager)
(to je prečac za menu za; zaključavanje, odjavljivanje, i task manager.) - Izvođenje sustavskog poziva za stvaranje procesa od strane pokrenutog procesa (postojeći proces izaziva sustavski poziv za stvaranje novog procesa – npr. 1 proces dohvaća podatke s mreže, a drugi i dodjeljuje )
- Zahtjev korisnika za stvaranje novog procesa (u interaktivnim sustavima, korisnik s ENTER ili dvoklik pokreće program. To pokreće novi proces i pripadajuće zadatke – više otvorenih prozora u Windowsima)
- Iniciranje nakupine poslova (batch job) – korisnik postavlja poslove sustavu na izvođenje, a kada OS odluči da ima resursa za neki posao,kreira novi proces i pokreće sljedeći posao iz reda čekanja.
Sustavski poziv:
- u UNIX-u fork nakon kojega imamo dva procesa (roditelj i dijete) koji imaju jednaku sliku u memoriji, okolinu i otvorene datoteke. Dijete izvodi execve ili sličan poziv koji mijenja sliku u memoriji i pokreće novi program.
- u Windows-ima CreateProcess obavlja kreiranje procesa i učitavanje odgovarajućeg programa u novi proces. Poziv ima 10 parametara
U oba OS-a, nakon što je proces kreiran, i dijete i roditelj imaju vlastite odvojene adresne prostore
Navedite uobičajene razloge (i primjere) i uvjete završetka procesa
- Normalni izlazak (svojevoljno), nakon obavljenog posla. Npr. kada prevoditelj prevede program, on izvodi sustavski poziv kojim OS-u govori da je gotov (exit ili ExitProcess), ali i da nešto treba ukloniti.
- Izlazak zbog pogreške (svojevoljno), odnosno otkrivene pogreške. Npr. pokrenemo prevoditelj cc foo.c, a programa foo.c nema (Pop-Up prozor)
- Fatalna pogreška (nije svojevoljno), često zbog pogreške u programu. Npr. izvođenje nepostojeće instrukcije, referenciranje nepostojeće adrese u memoriji, dijeljenje s 0.
- Ubijanje od strane drugog procesa (nije svojevoljno), gdje proces izvodi sustavski poziv koji OS-u govori da ubije neki drugi proces. Ubojica mora biti ovlašten za ubijanje. U UNIX-u je to kill, a u Windows TerminateProcess.
Ukratko objasnite hijerarhiju procesa i razliku između Windowsa i UNIXa.
- Proces roditelj kreira proces dijete, a onda svaki ima svoj put izvođenja. Dijete može također kreirati više procesa, stvarajući hijerarhiju. Pri tome ima jednog roditelja, nijedno, jedno ili više djece.
- UNIX:
- proces, njegova djeca i daljnji nasljednici čine skupinu procesa.
- Kada korisnik tipkovnicom pošalje signal, on se prosljeđuje svim članovima skupine pridruženima tipkovnici, a proces ga može uhvatiti, ignorirati ili poduzeti neku “default” akciju.
- Posebni proces init nalazi se u boot-u. Kad se pokrene, gleda broj terminala, a onda stvara jednog ili više novih procesa po terminalu. Oni čekaju da se netko prijavi, što opet može razgranati stablo procesa.
- Windows:
- nema hijerarhije procesa - svi su procesi jednaki.
- Ipak, kreiranom procesu roditelj daje posebnu oznaku (token), zvanu rukovatelj (handle) koju koristi za nadzor djeteta.
- Dijete može oznaku dati drugom procesu.
Navedite moguća stanja procesa, te skicirajte i objasnite dijagram prijelaza stanja procesa.
Moguća stanja procesa:
- Pokrenut (trenutno koristi CPU)
- Pripravan (pokretljiv, ali zaustavljen da bi se mogao izvesti drugi proces)
- Blokiran (ne može se pokrenuti dok ne dođe do nekog vanjskog događaja)
Running
/ \ Blocked --> Ready
- Proces otkriva da se ne može pokrenuti, jer nema ulaznog podatka.
- Raspoređivač oduzima CPU trenutnom i dodjeljuje je nekom drugom procesu
- Raspoređivač vraća CPU procesu koji je bio pokretan prije trenutnog procesa
- Dogodio se događaj izvana na kojeg je proces čekao da bi se pokrenuo (npr. raspoloživost ulaznog podatka
Navedite barem 10 parametara iz svih skupina parametara iz tablice procesa potrebnih pri implementiranju procesa.
Process management:
- Registers
- Program counter
- Program status word
- Stack pointer
- Process state
- Priority
- Scheduling parameters
- Process ID
- Parent process
- Process group
Memory management:
- Pointer to text segment
- Pointer to data segment
- Pointer to stack segment
File Management:
- Root directory
- Working directory
- File descriptors
- User ID
- Group ID
Što su niti i kako se modeliraju?
Nit je dio procesa koji obavlja rad, niti se raspoređuju i izvode na CPU. Proces objedinjuje resurse potrebne za izvršavanje.
Sve niti u jednom procesu dijele isti adresni prostor (time i globalne varijable, otvorene datoteke, child procese)pa nisu neovisne. Niti kao i procesi, mogu biti u stanjima: Ready, Running, Blocked, Finished.
Navedite osnovne razlike između procesa i niti, te navedite parametre koji su nužni pri implementiranju niti.
Osnovne razlike između procesa i niti:
- Procesi su obično nezavisni, dok niti postoje kao podsetovi procesa.
- Procesi nose znatno više informacija stanja nego niti, dok niti u procesu dijele stanje procesa te memoriju i druge resurse.
- Procesi imaju zasebne adresne prostore, dok niti dijele adresni prostor.
- Procesi komuniciraju samo kroz sistemski dodijeljene IPC mehanizme.
- Zamjena konteksta je obično brža među nitima nego među procesima.
- Niti istog procesa su pokrenute u istom adresnom prostoru, procesi će postojati pojedinačno u svojim adresnim prostorima.
Parametri potrebni za implementiranje niti:
- Program counter
- Registers
- Stack
- State
Navedite razloge korištenja niti i ukratko opišite jedan primjer korištenja niti, te mogući način programskog ostvarenja višenitnosti.
include <Windows.h></Windows.h>
Razlozi za korištenje niti:
- Omogućavaju paralelne entitete u istom adresnom prostoru
- Niti nemaju pridružene resurse, pa ih je 100 puta brže kreirati i uništiti nego procese
- Znatno poboljšanje performansi pri korištenju U/I
- Vrlo pogodne pri višestrukim procesorima gdje je moguć pravi paralelizam
Primjer: Korištenje uređivača dokumenta. - Jedna nit se koristi za naredbu zamijeni, gdje zamijeni string u dokumentu, sa drugim stringom. - Ako bi korisnik u slučaju gdje se zamjena predao nekakvu naredbu, bilo sa tipkovnice ili miša, ta naredba bi bila ignorirana sve dok nit ne obavi svoje. - Da imamo više niti, to se ne bi dogodilo. Ta naredba bi se dovršila sve dok za nit koja zamjenjuje stringove, vrši. - U ovom slučaju više procesa na isti dokument ne bi bio moguć, jer procesi ne dijele isti adresni prostor i datoteke.
Primjer višenitnosti:
#include <iostream>
using namespace std;</iostream>
DWORD WINAPI thread1(__in LPVOID lpParameter) {
while (1) {
std::cout «_space;” From Thread 1 \n”; Sleep(1500);
}
}
DWORD WINAPI thread2(__in LPVOID lpParameter) {
while (1) {
std::cout «_space;” From thread 2\n”; Sleep(5000);
}
}
WORD WINAPI thread3(__in LPVOID lpParameter) {
while (1) {
std::cout «_space;” From thread 3\n”; Sleep(2000);
}
}
int main() {
DWORD threadID1, threadID2, threadID3;
HANDLE h1 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)thread1, 0, 0, &threadID1);
HANDLE h2 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)thread2, 0, 0, &threadID2);
HANDLE h3 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)thread3, 0, 0, &threadID3);
getchar();
return 0;
}
Što su Pthreads i kojim pozivima se njima upravlja.
Pthreads
- POSIX threads, dozvoljavaju programu da kontrolira više različitih tokova rada koji se odvijaju u isto vrijeme
Poziv - Opis:
Pthread_create | Create a new thread
Pthread_exit | Terminate the calling thread
Pthread_join | Wait for specific thread to exit
Pthread_yield | Release the CPU to let another thread run
Pthread_attr_init | Create and initialize a thread’s attribute structure
Pthread_attr_destroy | Remove a thread’s attribute structure
Što je kritični odsječak i zašto je potreban? Objasnite po potrebi i slikom.
Kritični odsječak je dio programa u kojem proces pristupa dijeljenoj memoriji. Služi za sprečavanje utrkivanja, tj. zabranjuje da više od jednog procesa čitaju ili pišu iz ili u dijeljeni prostor podataka u isto vrijeme - osigurati međusobno isključivanje (mutual exclusion)
Navedite četiri uvjeta koji omogućuju međusobno isključivanje.
Uvjeti sprečavanja isključivanja:
1. Dva procesa istovremeno ne mogu biti u kritičnom odsječku
2. Ne rade se pretpostavke o brzinama i broju procesora
3. Proces pokrenut izvan kritičnog odsječka ne može blokirati drugi proces
4. Proces ne mora beskonačno čekati do ulaska u svoj kritični odsječak
Navedite zahtjeve za komuniciranjem među procesima, te zahtjeve za komuniciranjem među nitima.
Prosljeđivanje informacije jednog procesa drugom
Sprječavanje ulaska procesa u kritične odsječke jedno drugom
Omogućavanje redoslijeda izvođenja koji poštuje međusobnu zavisnost među procesima
Za niti: komuniciranje među procesima treba biti jednako primjenjivo na niti, još lakše za niti u istom adresnom prostoru
Navedite postupke koji postižu međusobno isključivanje čekanjem, te ukratko opišite barem tri od njih. (Busy Waiting)
Zabrana prekida
Najjednostavnije je da svaki proces zabrani svaki prekid odmah kada uđe u K.O., a dozvoli čim izađe. CPU se samo prebacuje s procesa na proces prema takta ili na prekid. Postupak je nepopularan, jer nije zgodno korisničkom procesu dati mogućnost dozvole/zabrane prekida (može ga zaraniti i više nikad ne dozvoliti - crash). Zabrana prekida korisna, ali unutar OS-a, a ne na razini korisnika.
Varijable Ključanja
Imamo dijeljenu (lock) varijablu inicijalno u 0. Kada proces želi ući u K.O., ispituje lock. Ako je lock 0, proces ga postavlja u 1 u ulazi u K.O. Ako je lock već u 1, proces mora čekati dok ne bude 0.
Nedostatak: proces čita lock i vidi da je 0. Prije nego ga postavi u 1, drugi proces je raspoređen za izvođenje i postavlja lock u 1. Kada se prvi proces ponovo pokrene, on također postavi lock u 1 i oba su u K.O.
Strogo Izmjenjivanje Kod OS-a najčešće i je pisan u C ili C++ jeziku. Cjelobrojna varijabla turn je početno u 0, a postavlja se za ulaz u K.O. Proces 0 ispituje turn, utvrđuje da je 0, te ulazi u K.O. Proces 1 također vidi da je turn 0 i u petlji ispituje turn da vidi kad će biti 1. Stalno ispitivanje varijable do pojave neke vrijednosti naziva se busy waiting. Uglavnom se sprječava, jer troši vrijeme CPU. Kada proces 0 napusti K.O., postavlja turn u 1 kako bi u K.O. ušao proces1. S obzirom da narušava zahtjev 3., nije uvijek stvarno primjenjiv postupak.
Objasnite na čemu se zasniva Petersonovo rješenje međusobnog isključivanja?
Prije upotrebe dijeljenih varijabli (prije ulaska u K.O.), svaki proces poziva enter_region sa svojim vlastitim brojem procesa, 0 ili 1, kao parametrom.
Taj poziv uzrokuje njihovo čekanje do sigurnog ulaska u K.O. Nakon završetka s dijeljenim varijablama, proces zove leave_region da pokaže daje gotov i dozvoli drugom procesu ulazak u K.O.
Početno nijedan proces nije u K.O. Tada proces 0 poziva enter_region. To pokazuje njegov interes postavljanjem turn u 0. Ako proces 1 pozove enter_region, on tamo ostaje dok interested[0] ne bude FALSE…
Ukratko objasnite sljedeće pojmove i način njihovog korištenja: semafor, muteks, futeks, monitor.
Semafor:
- cjelobrojna varijabla u programu koja pamti broj buđenja za buduće korištenje
- Dvije operacije:
- down: ispituje je li vrijednost veća od 0, ako je dekrementira vrijednost i nastavlja, ako nije, proces odlazi na spavanje bez završetka down-a.
- up: inkrementira vrijednost semafora.Ako jedan ili više procesa spavaju na semaforu i ne mogu završiti prethodnu down operaciju, jedan on njih se bira da bi ju završio.
Muteks:
- pojednostavljeni semafor koji se koristi za upravljanje međusobnim isključivanjem na resursima programa
- ima dva moguća stanja (otključano i zaključano)
- Ako proces ili nit pozove resurs koji je zaključan(mutex_lock), oni idu u blokiranje sve dok taj resurs ne postane slobodan,tj. Sve dok ne postane otključan(mutex_unlock).
Futeks: fast user space mutex, mehanizam u Linux-u koji implementira mutex, radi na jezgri procesora
- Ako je lock početno u nuli (slobodan), nit upita za “decrement and test” te provjerava rezultat, ako je lock slobodan, nit se izvodi, ako nije, nit ide u red čekanja za jezgru i ulazi kad bude odblokirana.
Monitor: složena varijabla koja se sastoji od procedura i varijabli koja služi za sinkronizaciju procesa
- Isključivo jedan proces može biti aktivan u monitoru
- Proces poziva proceduru u monitor, da utvrdi da li već postoji proces u monitoru. Ako ima, poziv se odgađa dok trenutni proces ne napusti monitor
Ukratko objasnite postupak izmjene poruka i na tome zasnovano rješenje problema proizvođač – potrošač.
Koristi sustavske pozive send i receive kako bi se slala poruka procesu. Ta poruka može biti objekt, paralelni proces, funkcija, nit…
Pri slanju poruke je potrebna potvrda prijema i autentifikacija.
Rješava problem proizvođač-potrošač tako da za svakih N poruka koje su poslane a ne mogu biti primljene, potrošač šalje N praznih poruka proizvođaču.
(IPC - Inter-Process Communication)
Ukratko objasnite i skicirajte način rada i ulogu barijera.
Mehanizam usmjeren usklađivanju grupa procesa. Neke aplikacije podijeljene su u faze, pri čemu proces ne može ići u sljedeću fazu (blokira se), dok svi procesi ne budu spremni za ulazak u tu fazu. Zato se iza svake faze stavlja barijera (poziv barrier). Proces pristupa barijeri, od svih procesa, jedan blokira barijeru, posljednji proces dolazi, svi prolaze.
Objasnite pojam i razloge raspoređivanja, te navedite podjelu, vrste i ciljeve algoritama raspoređivanja.
Raspoređivanje je postupak izrade rasporeda za procese. Primjenjuje se kad se kreira novi proces, kada proces završava, pri prekidu ili blokade U/I…
Koristi se zbog pseudoparalelnog izvođenja procesa.
Algoritmi raspoređivanja:
- Batch - malo ili nimalo prekida,
- Interaktivni - prekidanje zbog hitnosti,
- Realtime - prvo se pokreće proces bitan za dovršavanje aplikacije, prekidi nisu nužni
Ciljevi:
- SVI SUSTAVI - fair share of CPU, poštivanje pravila, svi dijelovi sustava zaposleni;
- BATCH SUSTAVI - maksimizirati broj poslova po satu, minimizirati vremena između poslova, držati CPU stalno zaposlenog
- INTERAKTIVNI SUSTAVI - brzo reagiranje na zahtjev, proporcionalno udovoljiti svim korisnicima;
- REALTIME - poštivati zadane rokove, predvidljivost
Naučite za zadani skup zadataka po jedan primjer raspoređivanja koristeći: FCFS, SJF i SRTN algoritam.
FCFS (First-Come First-Served)
- jednostavan, neprekidan, jedan red, kratki poslovi čekaju vrlo duge
SJF (Shortest Job First)
- neprekidan, po SJF pojedinačna i prosječna vremena završetka poslova su bolja
- optimalan samo ako su poslovi istovremeno pripravni
SRTN (Shortest Remaining Time Next)
- prekidan, statičan, dolazak kraćeg procesa izaziva prekid
Objasnite što je trorazinsko raspoređivanje.
- prijemni raspoređivač: mješavina CPU i U/I poslova i SJF
- za primljeni posao, generira se proces i smješta u memoriju ili swap na disk (koji gdje – raspoređivač memorije:
- koliko dugo je od zadnjeg swapa procesa
- koliko je zauzimao CPU - trajanje procesa
- važnost procesa
- raspoređivanje na CPU(slika)
Naučite za zadani skup zadataka po jedan primjer raspoređivanja koristeći: Round Robin, raspoređivanje na više razina, višestruke redove, Shortest Process Next, Guaranteed Scheduling i Fair-Share Scheduling.
ROUND ROBIN
- svakom procesu dodjeljuje se vremenski interval
- na kraju tog intervala pokreće se drugi proces
- drugi proces se pokreće i ako se trentuni proces blokira
- pitanje je samo dužina intervala
RASPOREĐIVANJE S VIŠE RAZINA PRENSTVA
- svakom procesu dodjeljuje se određena razina prvenstva, a proces najviše razine pokreće se prvi
- razine prvenstva mogu se mijenjati svakim novim otkucajem sata
- razine se mijenjaju statički (Unix - nice) ili dinamički (posluživanje U/I uređaja)
- često grupiranje procesa na razine prvenstva
VIŠESTRUKI REDOVI
- bolje je procesu dati jednom duži interval, nego više kratkih (prekidi, swapping)
- daju li se svim procesima dugi intervali, dobivamo loše vrijeme odziva
- procesi se stavljaju u razrede prvenstva: najviša razina jedna jedinica vremena, ispod nje dvije, ispod nje tri…
- svaki put kad proces potroši cijeli iznos dozvoljenog vremena, spuštamo garazinu niže
SHORTEST PROCESS NEXT
- daje najkraće prosječno vrijeme odziva, pa je dobro i u interaktivnim sustavima
- koji od pokrenutih je najkraći: procjena dotadašnjeg ponašanja pokretanih naredbi (procesa) računanjem težinskih zbrojeva (aging) i pokretanje po procjeni najkraćeg procesa
GUARANTEED SCHEDULING
- n korisnika dobiva 1/n kapaciteta CPU (vrijedi i za jednokorisnički sustav i n procesa)
- načiniti omjer potrošenog i dodijeljenog vremena na CPU (1/2 – pola iskoristio, 2 – dvostruko iskoristio)
- pokretati proces najmanjeg omjera, dok omjer ne bude pomaknut iznad suparnika
FAIR-SHARE SCHEDULING
- Svaki korisnik, a ne proces dobije neki dio vremena, pa se to vrijeme dijeli na sve njegove procese
- (Korisnik 1 ima a,b,c,d ;a korisnik 2 ima e: raspored je abecdeabecde)»
Napišite izraz i ukratko objasnite uvjet rasporedivosti u sustavima stvarnog vremena.
Uvjet rasporedivosti u realtime: ∑_(i=1)^m (C〖_i〗)/(P〖_i〗)≤1
- za m periodnih događaja,
- događaj i se dogodi unutar perioda Pi i traje Ci
- ne može biti veći događaj(C) od predviđenog vremena trajanja P)
Navedite i opišite osnovne grupe procesa u operacijskom sustavu.
Postoje dvije grupe procesa:
- Prednji procesi - sučelja prema korisniku
- Pozadinski procesi (daemoni) - obrada raznih zahtjeva, i sve što se događa u pozadini
Opišite razlike između poznatih problema kontrole istovremenosti u višenitnim aplikacijama: međusobnog isključivanja, zastoja i gladovanja
Međusobno isključivanje – da se osigura da je jedna proces unutar kritičnog odsječka u slučaju utrke
Zastoj - izvršavanje međusobnog isključivanja može uzrokovati zastoj. Primjerice, ako 2 procesa istovremeno čekaju na 2 resursa, a operacijski sustav svakom da jedan od resursa. Tada su oba procesa u zastoju jer su im potrebna oba resursa za daljnji rad. Nijedan proces neće otpustiti resurs kojim raspolaže pa time neće dobiti ni pravo na drugi resurs.
Gladovanje – ako npr. imamo 3 resursa. P1, P2 i P3 te oni zahtijevaju periodički pristup. Prvo ide P1 te nakon izvršavanja resurs dijeli P3, nakon toga P3 daje P1 i tako dalje. U tom slučaju P2 je u gladovanju.
Objasnite što su računalna sredstva (resursi), te navedite primjere i tipove.
Računalni resursi su uređaji i mediji kojima računalo raspolaže. Primjer: pisač, diskovi, memorijski prostor, baza podataka…
Tipovi resursa:
- prekidivi - mogu se oduzeti procesu koji ih posjeduje a da ne dođe do zastoja (memorija)
- neprekidivi - ne mogu se oduzeti trenutnom procesu posjedniku, a da ne dođe do pogreške ili pada sustava (CD snimač); uglavnom uzrokuju zastoje
Prikažite i objasnite kako se semafori koriste za zaštitu (jednog i dva) resursa.
Ako imamo jedan resurs, proces mora obavljati poziv semaforu za zahtjev resursa (down), obavljanje rada sa resursom i onda oslobađanje resursa (up)
Ako imamo dva resursa, moramo prvo obaviti poziv semaforu za zahtjev jednog pa drugog resursa i tek kada su oba slobodna možemo obaviti rad na resursu. Nakon obavljenog rada resurs oslobađamo preko semafora.
Što su zastoji i koji su uvjeti nastanka i sprječavanja zastoja?
Skup procesa je u zastoju ako svaki proces skupa čeka događaj koji može uzrokovati samo neki drugi proces u istom skupu
Proces se ne može pokrenuti, osloboditi resurse ili biti probuđen
Uvjeti za zastoj:
Međusobno isključivanje - svaki resurs dodijeljen je istovremeno jednom procesu
Držanje i čekanje - proces koji trenutno koristi resurse zahtjeva dodatne
Neprekidivost - resurs ne može biti naglo oduzet procesu nego mora biti otpušten od procesa koji ga trenutno posjeduje
Kružno čekanje - kružni lanac 2 ili više procesa, čeka na resurs koji trenutno drži sljedeći lanac
Zastoj se sprječava uklanjanjem barem jednog od ovih uvjeta
Skicirajte i ukratko objasnite modeliranje zastoja usmjerenim grafom i strategije rada sa zastojima.
Strategije rada sa zastoijma:
- Potpuno ignorirati problem (i problem ignorira Vas)
- Detektiranje i oporavak (dopustiti zastoj i onda ga popravljati)
- Dinamičko sprječavanje (pažljivim dodjeljivanjem resursa)
- Prevencija (negiranje jedno od uvjeta za zastoj)
a) R –> A
b) B –> S
c) …D –> U –> C –> T –> D –> U… ( u krug)
- resurs R dodjeljen je procesu A
- proces B zahtjeva/čeka resurs S
- procesi C i D su u zastoju nad resursima T i U
Objasnite Nojev algoritam i uvjete kada se koristi.
Pretvaramo se da to nije problem, koristi se ako se zastoj događa vrlo rijetko ili ako su troškovi sprječavanja vrlo visoki
UNIX i Windows imaju takav pristup.
Navedite i ukratko objasnite načine oporavka od zastoja.
Oporavak od zastoja je moguć:
Prekidanjem (uzima se resurs nekog drugog procesa, ako moguće)
Povratkom unatrag (proces se provjerava periodno i ti podaci se čuvaju kako bi se mogla pokrenuti prijašnja inačica)
Ubijanjem procesa
Objasnite otkrivanje zastoja za jedan resurs svakog tipa, te za više resursa svakog tipa.
Otkrivanje zastoja:
za 1 resurs svakog tipa-algoritam detektira kružno čekanje u usmjerenom grafu
za više resursa svakog tipa-potrebni vektor postojećih resursa E, raspoloživih resursa A, matrica trenutnog dodjeljivanja resursa C i matrica potreba za resursima R: ∑_(i = 1)^n C_ij+ A_j= E_j;
algoritam otkriva proces za koji je i-ti red od R manji ili jednak A
Objasnite kako radi Bankarev algoritam za pojedinačne i višestruke resurse, te naučite korištenje tog algoritma na primjeru.
Bankarev algoritam je jedna od strategija za sprječavanje zastoja. Algoritam se zasniva na pažljivom dodjeljivanju resursa procesima. Postoji bankarev algoritam za pojedinačne te za višestruke resurse. Bankarev algoritam za pojedinačne resurse: Raspolaže se određenom količinom jednog resursa i to tako da se ne daje maksimalni traženi iznos odjednom, nego se daje onaj iznos kojim bi se određeni proces mogao završiti, nakon čega se resursi tog završenog procesa vraćaju u početnu količinu. Postupkom se otkriva je li stanje sigurno (do zastoja sigurno neće doći) ili nesigurno (do zastoja bi moglo doći).
Bankarev algoritam za višestruke resurse: Raspolaže se određenom količinom više različitih resursa, a postupak se vrši na jednak način kao kod algoritma za pojedinačne resurse, samo što se ovdje raspolaže s više različitih resursa odjednom. Uočavamo matrice: C (currently allocated resources) – količina zasebnih resursa koje svaki pojedini proces trenutno zauzima. R (request resources) – količina zasebnih resursa koje svaki pojedini proces treba kako bi završio. E (every resource) – suma trenutno ustupljene količine resursa (P) i trenutno dostupne količine resursa (A). P (preallocated resources) – trenutno ustupljena količina resursa. A (available resources) – trenutno dostupna količina resursa.
Navedite i ukratko objasnite preventivne mjere protiv zastoja.
- Međusobno isključivanje
- resurse dodjeljivati samo ako je nužno potrebno, sa što manje procesa istovremeno tražiti resurse - Držanje i čekanje
- zahtijevati da proces traži resurse prije pokretanja, te da oslobodi sve resurse prije traženja novih - Neprekidivost
- često nije dobro naglo prekinuti proces( npr. Printer) - Kružno čekanje
- resurse normalno poredati
Ukratko objasnite što su zastoji bez resursa i komunikacijski zastoji.
Zastoji bez resursa je zapravo zastoj dva procesa: oba čekaju drugog da nešto učini.
Mogu se dogoditi i sa semaforima, gdje svaki proces zahtjeva da učini down() na dva semafora (mutex ili drugo). Ako se napravi krivim redoslijedom, dolazi do zastoja.
Komunikacijski zastoji se događaju pri sinkronizaciji nadmetanja
Navedite i objasnite četiri osnovna stanja poslova (jobs) u operacijskom sustavu Linux.
- Running
- Sleeping / waiting - proces čeka resurse
- Zombie - ostatak završenog procesa koji nije do kraja zaustavljen
- Stopped
Objasnite razliku između monoprogramiranja i multiprogramiranja, te načine rješavanja problema odvojenim i jednostrukim redovima.
Kod monoprogramiranja imamo pokrenut samo jedan program koji dijeli memoriju sa OS-om
Kod multiprogramiranja imamo više procesa istovremeno; jedan radi dok su ostali blokirani, izmjenjuju se kroz vrijeme. Uz to potrebno je podijeliti memoriju na nejednake dijelove:
- Ako imamo odvojene ulazne redove za grupe procesa, red za velike dijelove je prazan a mali procesi će čekati u svom redu.
- Ako imamo jedan ulazni red, proces najbliži čelu reda ide u prazni dio koji mu odgovara.
Skicirajte i objasnite dijagram ovisnosti korisnosti CPU o stupnju multiprogramiranja i čekanju na ulaz/izlaz.
Korisnost CPU kao funkcija broja procesa u memoriji (približno)
- proces troši p vremena na čekanje U/I
- za n procesa odjednom u memoriji, vjerojatnost čekanja U/I je pn
- korisnost CPU = 1-pn
- za p vremena čekanja na U/I i n procesa u memoriji: (za veći broj procesa i manje vrijeme čekanja veća je korisnost)
Objasnite kako dolazi do povezivanje instrukcija i podataka s memorijom, te što je relociranje.
Događa se u tri različita stanja za:
- Vrijeme prevođenja:
○ ako je lokacija memorije poznata unaprijed, generira se apsolutni kod,
○ a ako se startna lokacija mijenja, mora se ponovno prevesti.
- Vrijeme učitavanja:
○ mora generirati relocirani kod na lokaciju memorije koja nije poznata za vrijeme prevođenja. - Vrijeme izvođenja:
○ povezivanje kasni do pokretanja ako se proces tijekom pokretanja premješta s jednog segmenta u drugi. - Relociranje:
Process dodjeljivanja “adrese učitavanja” za (memorijski-)pozicijski ovisni program i prilagođavanja koda i podataka programa da se odražavaju na dodijeljene adrese.
Objasnite pojam prividne (virtualne) memorije, postupke njene implementacije, te straničenje na zahtjev.
Virtualna memorija - ako programi ne stanu u prostor fizičke memorije, dijele se na sitnije dijelove, samo dio koji se izvodi OS ostavlja u memoriji, a ostatak ide na disk i tako se stvara privid veće memorije.
Omogućena je straničenjem: virtualna memorija se podijeli na stranice, a odgovarajuće jedinice u fizičkoj memoriji su okviri stranica.
Objasnite pojam izmjene (engl. swapping) i njegovo rješavanje kod procesa stalne i promjenjive veličine.
Kad ponestane memorije za sve procese, vrši se dohvaćanje procesa, njihovo pokretanje i vraćanje na disk. Taj proces se zove izmjena ili swapping.
Procesi stalne duljine su jednostavni za smještanje, smještaju se u rupe nastale izlaskom drugih procesa.
Procesi čiji podatkovni su promjenjive veličine su zahtjevni za swappanje:
- Ako imaju šupljine u memoriji susjedne procesu, on se slobodno širi.
- Ako je proces uz proces, neki procesi izlaze da bi se napravila dovoljno velika šupljina za širenje.
- Ako proces ne može rasti, čeka ga se ili ubija.
Objasnite i skicirajte postupak rukovanja memorijom korištenjem bitmapa, te korištenjem povezanih lista.
Uz bitmapu, memorija je podijeljena u jedinice za alociranje reda veličine čak do nekoliko kilobyte-a. Jedan bit u bitmapu ukazuje na to je li slobodan (0) ili je zauzet (1).
Povezana lista dodijeljenih i slobodnih dijelova memorije (proces ili šupljina) - proces (P), šupljina (H), početna adresa, duljina, pokazivač - kada proces završi, lista se lako ažurira - proces ima dva susjeda (osim ako je na vrhu ili dnu memorije)
Objasnite Best Fit, Worst Fit i First Fit algoritme dodjeljivanja memorije procesima.
First Fit - traži dok ne nađe dovoljno veliku prazninu
Next Fit - ne pretražuje od početka već od mjesta gdje je pronađena zadnja dovoljna praznina
Best Fit - pretražuje cijelu listu dok ne nađe najmanju odgovarajuću prazninu
Worst Fit - uvijek uzima najveću prazninu
Quick Fit - ima odvojene liste za najčešće zahtijevane dužine praznina, vrlo brz, pravi veliku fragmentaciju
Što je virtualna memorija i kako je ona omogućena straničenjem (engl. paging). Osvrnuti se na sliku i po potrebi je skicirati.
Virtualna memorija je kombinirana duljina programa i podataka koja prelazi raspoloživu memoriju. OS uz virtualnu memoriju u RAM memoriji ostavlja samo trenutno izvođeni program a ostatak ide na disk.
Paging je način upravljanja memorijom gdje računalo piše i čita podatke sa sekundarnog memorijskog prostora za korištenje u glavnom memorijskom prostoru (RAM podatci idu na disk).
Stranice su jedinice virtualnog adresnog prostora, koji po veličini odgovaraju okvirima u fizičkoj memoriji.
Broj stranice se koristi kao indeks u tablici stranica
Virtualna adresa = broj virtulane stranice + pomak
Paging je izmišljen da dobijemo dugački linearni adresni prostor bez da moramo uzimati više fizičke memorije
