OS1/Jul 2017
1. zadatak
Postavka
Šta je hard, a šta soft sistem za rad u realnom vremenu (real-time system)?
Rešenje
Tvrdi sistemi za rad u realnom vremenu su sistemu u kojima odziv mora da stigne u određenom vremenu (deadline). Prekoračenje može dovesti do rezličitih katastrofa. Meki sistemi za rad u realnom vremenu su sistemi kojima je rok bitan ali smeju ga prekoračiti dok god performanse ulaze u zadate okvire.
2. zadatak
Postavka
Objasniti značenje mašinske instrukcije tipa test_and_set i njenu upotrebu u jezgru operativnog sistema.
Rešenje
test_and_set je instrukcija koja omogućava sinhronizaciju na hardverskom nivou. Služi za međusobno isključenje izvršavanja na više procesora. Ona čita i vraća vrednost zadate memorijske lokacije a u tu lokaciju stavlja vrednost 1. Koristi se u implementaciji lock() funkcije.
3. zadatak
Postavka
Korišćenjem školskog jezgra napisati program koji u n uporednih niti izračunava kvadrat svakog elementa nekog celobrojnog niza (a[i]*=a[i]) veličine n*k, tako što svaka nit obrađuje kelemanata(jednu particiju niza).
Rešenje
class ArrThread : Thread{
public:
ArrThread(int* a, int s, int f): arr(a), start(s), finish(f) {}
void run(){
for (int i=start;i<finish;i++){
arr[i] *= arr[i];
}
}
private:
int* arr;
int start;
int finish;
};
int main(){
ArrThread *t[n];
int start=0;
for (int i=0;i<n;i++){
t[i] = new ArrThread(array,start,start+k);
start += k;
}
for (int i=0;i<n;i++){
t[i]->waitToComplete();
delete t[i];
}
}
4. zadatak
Postavka
Implementirati Petersonov algoritam za međusobno isključenje kritičnih sekcija dva uporedna procesa.
Rešenje
shared var turn : integer := 1, flag1, flag2 : boolean := false;
process P1
begin
loop
flag1 := true; turn := 2;
while flag2 and turn = 2 do null;
<critical section>
flag1 := false;
<non-critical section>
end
end P1;
process P2
begin
loop
flag2 := true; turn := 1;
while flag1 and turn = 1 do null;
<critical section>
flag2 := false;
<non-critical section>
end
end P2;5. zadatak
Postavka
Precizno objasniti zašto klasičan linker svoj posao obavlja u dva prolaza (a ne može samo ujednom). Obrazloženje ilustrovati primerom.
Rešenje
Linkerov zadatak je spojiti sve fajlove u jedan izvriš ali da bi to uradio, linker mora naći sve simbole koji se uvoze odnosno izvoze. U prvom prolazu analizira ulazne fajlove, veličinu njihovog binarnog sadržaja (prevoda), i pravi mapu exe fajla; osim toga, sakuplja infomacije iz tabela simbola obj fajlova i izgrađuje svoju tabelu simbola; u tu tabelu simbola unosi izvezene simbole iz obj fajlova, za koje odmah može da izračuna adresu u odnosu na ceo exe fajl. U drugom prolazu generiše binarni kod, i ujedno razrešava nerazrešena adresna polja mašinskih instrukcija na osnovu informacija o adresama u koje se preslikavaju simboli iz njegove tabele simbola Primer: Recimo da imamo dva objektna fajla, a.obj i b.obj. a.obj izvozi simbol f i uvozi simbol c. Linker ce prvo izvozni fajl dodati u tabelu f. b.obj uvozi simbol f i izvozi simbol c, pa ce linker u svojoj tabeli dodati simbol c. U drugom prolazu ce linker razresiti c polje u a.obj i polje f u b.obj.
6. zadatak
Postavka
Objasniti uslugu koju program očekuje od operativnog sistema ako koristi preklope(overlay).
Rešenje
Obaveza OS-a je samo da obezbedi uslugu (sistemski poziv) koji alocira deo (virtuelnog) adresnog prostora procesa, kao i uslugu kojom u dati prostor procesa učitava sadržaj iz nekog binarnog fajla i sadržaj iz memorije upisuje u neki fajl (uobičajene sistemske usluge za rad sa fajlovima); OS ne zna za šta se te usluge koriste, tj. ne zna da se one upotrebljavaju baš za dinamičko učitavanje i zamenu delova procesa
7. zadatak
Postavka
Virtuelni adresni prostor je veličine 1GB, organizovan je segmentno, sa maksimalnom veličinom segmenta od 4KB, adresibilna jedinica je bajt. Svi segmenti nekog procesa su stvarne veličine od po 2KB i u fizičku memoriju smešteni su odmah jedan iza drugog, pri čemu segment broj 0 počinje od fizičke adrese F000h. Prikazati logičku strukturu virtuelne adrese i izračunati u koju fizičku adresu se preslikava virtuelna adresa 2543h.
Rešenje
8. zadatak
Postavka
Objasniti kako se nedeljivi izlazni uređaj može učiniti (virtuelno) deljivim?
Rešenje
Jedan način da se ovo reši je tehnikom rezervacije uređaja. To je zapravo međusobno isključenje operacija sa ovakvim uređajem. Problem je što operacije sa uređajima mogu trajati dugo pa ti procesi mogu dugo i da čekaju. Rešenje jeste u tehnici koja se naziva spuling. Ovde kada neki proces zahteva korišćenje, OS otvara poseban fajl u kome se preusmeravaju sve izlazne operacije sa tim uređajem. Kada se završi, proces nastavlja da izvršava svoj tok, dok se fajl šalje posebnoj niti operativnog sistema, spuleru koja onda izvršava jedan po jedan fajl iz liste čekanja i njegov sadržaj šalje uređaju.
9. zadatak
Postavka
Navestii objasniti razlog zašto bi neki fajl sistem koristio klastere na disku različite veličine.
Rešenje
Način da se reči problem režijske potrošnje prostora za pokazivače je povećavanjem bloka ili alokacije više susednih blokova kao jedna jedinica alokacije, i to se naziva klaster.
10. zadatak
Postavka
Neki fajl sistem koristi indeksirani pristup alokaciji fajlova sa indeksima u dva nivoa, blokom veličine 512KB i 64-bitnim adresama fizičkih blokova. Kolika je maksimalna veličina fajla u ovom sistemu?
Rešenje
2^45 B, odnosno 35 TB