ОС1/Јун 2013
1. zadatak
Postavka
Šta su multiprocesorski, a šta distribuirani sistemi?
Rešenje
Videti prvi zadatak iz julskog roka 2012. godine.
2. zadatak
Postavka
Ako se nad sledećim programom kreira jedan proces, koliko će ukupno biti elemenata sa vrednošću različitom od 0 u nizovima pid
svih kreiranih procesa (uključujući i taj jedan početni) kada svi ti procesi izađu iz petlje, pod pretpostavkom da su svi sistemski pozivi uspeli?
const int N = 2;
int pid[N];
void main() {
for (int i = 0; i < N; i++)
pid[i] = fork();
}
Rešenje
- Prva iteracija: P1 pravi P2,
pid[0] = 2
u P1 - Druga iteracija: P1 pravi P3,
pid[1] = 3
u P1 dok jepid[0] = 2
u P3 zbog toga što je taj niz kopiran iz P1 - Druga iteracija: P2 pravi P4,
pid[1] = 4
u P2
Na kraju postoji 4 vrednosti koje nisu nula.
3. zadatak
Postavka
Dokazati da Petersonov algoritam za međusobno isključenje kritičnih sekcija dva uporedna procesa uposlenim čekanjem zaista obezbeđuje međusobno isključenje, odnosno ne poseduje problem utrkivanja (race condition).
Rešenje
Pretpostavimo da oba procesa uposleno čekaju. Promenljiva turn "prelama" u situaciji kada oba procesa žele da uđu u kritičnu sekciju jer turn može imati vrednost ili 1 ili 2. Dakle, nemoguće je da dođe do utrkivanja.
4. zadatak
Postavka
Korišćenjem klasičnih brojačkih semafora, napisati kod za kritičnu sekciju u koju može uporedo ući najviše N procesa.
Rešenje
var mutex : Semaphore := N;
process P:
begin
loop
wait(mutex);
<critical>
signal(mutex);
<non-critical>
end
end
end P;
5. zadatak
Postavka
Koju uslugu operativni sistem treba da obezbedi procesima da bi oni koristili preklope (overlays)?
Rešenje
Videti rešenje 5. zadatka iz jula 2013. godine.
6. zadatak
Postavka
Data je definicija strukture FreeSegment
koja predstavlja jedan segment slobodne memorije. Ove strukture uvezane su u dvostruko ulančanu, neuređenu listu čija je glava freeSegHead
. Implementirati funkciju getBestFit(size_t)
koja treba da pronađe i vrati (ali ne menja ni njega ni listu) segment slobodne memorije u koji se može smestiti blok date veličine, po best fit algoritmu.
struct FreeSegment {
size_t size;
FreeSegment *prev, *next;
};
Rešenje
void* getBestFit(size_t sz) {
FreeSegment* bestFit = 0
size_t smallestFragment = MAX_SIZE;
for (FreeSegment* cur = freeSegHead; cur != 0; cur = cur->next) {
if (cur->size < sz) {
continue;
}
if (cur->size < smallestFragment) {
smallestFragment = cur->size;
bestFit = cur;
}
}
if (bestFit == 0) {
return 0;
}
FreeSegment* newFrag = (FreeSegment*)((char*)bestFit + sz);
if (bestFit->prev) {
bestFit->prev->next = newFrag;
} else {
freeSegHead = bestFit->next;
}
if (bestFit->next) {
bestFit->next->prev = newFrag;
}
newFrag->prev = bestFit->prev;
newFrag->next = bestFit->next;
newFrag->size = bestFit->size - sz;
return bestFit;
}
7. zadatak
Postavka
Memorija nekog računara organizovana je stranično, sa stranicom veličine 4KB. Adresibilna jedinica je bajt, a virtuelna adresa je 32-bitna. Fizička adresa je veličine 32 bita. Ako je PMT organizovana u dva nivoa, s tim da su veličine polja za broj ulaza u tabele oba nivoa isti, kolika je veličina (u bajtovima) PMT prvog nivoa?
Rešenje
VA: 10 PMT1 | 10 PMT2 | 12 offset
Ulaz PMT 1. nivoa sadrzi fizičku adresu početka PMT 2. nivoa. Kako je fizička adresa 32b = 4B odavde sledi da veličina PMT 1. nivoa je:
4B * 212 = 4KB
8. zadatak
Postavka
Ukratko objasniti tehniku dvostrukog baferisanja (double buffering) kod ulaza/izlaza.
Rešenje
Proizvođač upisuje u jedan bafer dok potrošač čita iz drugog bafora. Kada oba završe, baferi zamenjuju uloge.
9. zadatak
Postavka
Neki proces izvršava redom sledeće sistemske pozive. Pod pretpostavkom da korisnik u čije ime se izvršava ovaj proces ima pravo pristupa do oba fajla i na čitanje i na upis, i da oba poziva za otvaranje fajlova uspevaju, navesti koji od preostalih poziva će biti uspešan, a koji neuspešan (upisati na liniji pored poziva).
FHANDLE f1 = fopen(“x.doc”,read);
FHANDLE f2 = fopen(“y.doc”,read|write);
fread(f1,buffer1,n1);
fwrite(f1,buffer2,n2);
fread(f2,buffer1,n1);
fwrite(f2,buffer2,n2);
Rešenje
Videti zadatak iz junskog roka 2011.
10. zadatak
Postavka
Neki fajl sistem koristi bit vektor za evidenciju slobodnih blokova na disku. Kolika je veličina ovog vektora u bajtovima, za disk veličine 256 GB sa blokom veličine 512B
Rešenje
Na disku ima ukupno blokova. Pošto je za svaki blok potreban po jedan bit, količinu prostora određujemo kao .