ОС1/Јануар 2015

Zadaci na stranici predmeta.

1. zadatak

Postavka

Ukratko objasniti osnovni motiv nastanka koncepta raspodele vremena (time sharing).

Rešenje

Svaki korisnik treba da ima utisak da računar radi samo za njega sa dovoljno dobrim i ujednačenim vremenima odziva dok taj isti računar zapravo opslužuje više korisnika istovremeno.

2. zadatak

Postavka

Objasniti semantiku mašinske instrukcije test & set i način njene upotrebe za međusobno isključenje kritičnih sekcija kod miltiprocesorskih sistema.

Rešenje

Instrukcija test & set atomično čita i vraća vrednost sadržaja zadate promenljive i u nju upisuje 1. Ova atomičnost se obezbeđuje hardverski zaključavanjem magistrale. Svakoj kritičnoj sekciji, tj. deljenoj strukturi podataka kojoj pristupa kod kritičnih sekcija se pridruži jedna globalna deljena promenljiva L u deljenoj operativnoj memoriji multiprocesora.

lock(L):
	while test_and_set(L) do null;

unlock(L):
	L := 0;

3. zadatak

Postavka

Na jeziku C, korišćenjem sistemskih poziva fork() i execlp() za Unix, napisati program koji pokreće drugi program iz fajla čiji je naziv zadat kao parametar komandne linije prvog programa.

Rešenje

int main (int argc, const char *argv[]) {
	if (argc < 2) return -1;
	pid_t pid = fork();
	if (pid == 0) {
		int s = execlp(argv[1], NULL);
		if (s < 0) return -2;
	}
	return 0;
}

4. zadatak

Postavka

Napisati kod jednog od dva procesa sa međusobnim isključenjem kritične sekcije korišćenjem Petersonovog rešenja.

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>
		flag1 := false;
		<non-critical>
	end
end P1;

process P2
begin
	loop
		flag2 := true; turn := 1;
		while flag1 and turn = 1 do null;
		<critical>
		flag2 := false;
		<non-critical>
	end
end P2;

5. zadatak

Postavka

Zašto preklopi (overlays) ne mogu da se koriste ako program ima više niti koje obezbeđuje operativni sistem? Precizno objasniti.

Rešenje

Videti zadatak iz septembarskog roka 2011.

6. zadatak

Postavka

Potrebno je u nekoj strukturi podataka voditi evidenciju o slobodnim fragmentima memorije kod kontinualne alokacije sa best fit algoritmom. Koja struktura podataka je efikasnija za implementaciju operacije dealokacije segmenta memorije koju je zauzimao ugašeni proces: a) dvostruko ulančana lista slobodnih fragmenata uređenih po veličini ili b) dvostruko ulančana lista slobodnih fragmenata uređenih po poziciji u memoriji? Kratko obrazložiti.

Rešenje

Dvostruko ulančana lista slobodnih fragmenata uređenih po poziciji u memoriji, jer je potrebno ulančati sa slobodnim fragmentom iznad i ispod tog segmenta memorije koji dealociramo uz eventualno spajanje.

7. zadatak

Postavka

U nekom sistemu sa straničnom organizacijom virtuelne memorije virtuelna i fizička adresa su 32-bitne, adresibilna jedinica je bajt, a stranica je veličine 64 KB. PMT je organizovana u dva nivoa i jedan ulaz u PMT oba nivoa zauzima po jednu 32-bitnu reč. PMT oba nivoa su iste veličine. Koliko ukupno zauzimaju PMT za proces koji je alocirao samo svoju prvu i poslednju stranicu?

Rešenje

VA(32) = 8 (page1)|8 (page2)| 16 (offset)

$2^8 \cdot 4B + 2 \cdot 2^8 \cdot 4B = 3 \cdot 2^{10}B = 3KB$

8. zadatak

Postavka

Kojom tehnikom se nedeljivi uređaj može učiniti virtuelno deljivim?

Rešenje

spooling

9. zadatak

Postavka

U fajl podsistemu nekog operativnog sistema nema koncepta kurzora (pokazivača) trenutne lokacije za čitanje i upis sadržaja u fajl. Čime se može nadomestiti ovaj nedostatak u sistemskim pozivima za čitanje i upis u fajl? Precizno objasniti i ilustrovati potpisom funkcija za ove pozive.

Rešenje

Potrebno je dodati i poziciju odakle se želi čitati/upisivati.

void write(FHANDLE fh, int position, char* buffer, int size);
void read(FHANDLE fh, int position, char* buffer, int size);

10. zadatak

Postavka

Neki fajl sistem koristi indeksirani pristup alokaciji fajlova sa indeksima u dva nivoa, blokom veličine 512B i 32-bitnim adresama fizičkih blokova. Kolika je maksimalna veličina sadržaja fajla u ovom sistemu?

Rešenje

$\frac{512B}{4B} = 2^7B$ ulaza u indeksu

maksimalna veličina fajla: $2^7 \cdot 2^7 \cdot 2^9 = 2^{23}B = 8MB$