ОС2/Јануар 2020

Zadaci na stranici predmeta.

1. zadatak

Postavka

Ukratko objasniti tehniku predviđanja trajanja narednog naleta izvršavanja pomoću eksponencijalnog usrednjavanja kod SJF algoritma raspoređivanja procesa.

Rešenje

Tehnika predviđanja trajanja narednog naleta izvršavanja pomoću eksponencijalnog usrednjavanja teži da što preciznije proceni trajanje narednog naleta. To postiže težinskim faktorisanjem prethodnih procena i trajanja prethodnih naleta.

Formula koja se koristi za predviđanje:

$\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$

Gde je:

• $\tau_n$: predviđeno vreme izvršavanja $n$
• $t_n$: stvarno vreme izvršavanja $n$
• $\alpha$: koeficijent koji predstavlja uticaj istorije na naredna predviđanja.

• Na primer, ako je $\alpha=0$, istorija nema nikakvog značaja, a ako je $\alpha=1$, samo poslednje izvršavanje se uzima u obzir procene. Generalno se koristi $\alpha=\frac{1}{2}$.

2. zadatak

Postavka

Na jeziku Java implementirati monitor sa dve operacije, flip i flop, koje klijenti mogu da pozivaju strogo naizmenično.

Rešenje

public class Monitor {
	public boolean flipIsNext = true;

	public synchronized void flip() {
    	while (!flipIsNext) {
        	try {
            	wait();
            } catch (InterruptedException e) {}
        }
        flipIsNext ^= true;
        // execute flip operation
        notifyAll();
    }

	public synchronized void flop() {
    	while (flipIsNext) {
        	try {
            	wait();
            } catch (InterruptedException e) {}
        }
        flipIsNext ^= true;
        // execute flop operation
        notifyAll();
    }
}

3. zadatak

Postavka

Šta je marshalling? Šta je SOAP?

Rešenje

• marshalling je serijalizacija strukture podataka nekog izvornog jezika u niz bajtova pogodnih za prenos.
• SOAP je message protokol koji postoji kao "međujezik" za komunikaciju između veb aplikacija napisanih u različitim izvornim jezicima.

4. zadatak

Postavka

Stanje zauzeća resursa nekog sistema u nekom trenutku definisano je sledećim strukturama:

	Allocation			Max			Available
	A	B	C	A	B	C	A	B	C
P1	2	0	1	3	3	2	1	0	1
P2	0	1	1	2	3	3
P3	2	2	1	3	2	2

Da li u datom stanju treba odobriti zahtev (1,0,0) procesu P1 (sprovesti ceo postupak i obrazložiti odgovor)?

Rešenje

Stanje posle predloga:

	Allocation			Max			Available
	A	B	C	A	B	C	A	B	C
P1	3	0	1	3	3	2	0	0	1
P2	0	1	1	2	3	3
P3	2	2	1	3	2	2

U ovom stanju nije moguće završiti ni jedan proces - P1 zahteva još 3xB (nedostupan) i 1xA. P2 zahteva još 2xA, 2xB i 2xC (svi nedostupni). P3 zahteva 1xA (nedostupan) i 1xC. To znači da je mrtva blokada moguća.

P3 bi mogao da se završi da procesu P1 nije bio odobren zahtev. Zaključak je da ne treba odobriti zahtev P1(1,0,0).

5. zadatak

Postavka

Jedna realizacija protokola više čitalaca-jedan pisac (multiple readers – single writer) radi tako što pušta novog čitaoca ako već postoji čitalac koji čita. Koji problem postoji u toj realizaciji?

Rešenje

Problem u ovoj realizaciji je slučaj u kome pisac dolazi i čeka da čitalac završi čitanje. Moguće je beskrajno izgladnjivanje pisca ako neprestano dolaze novi čitaoci dok god postoji makar jedan čitaoc u sistemu.

Ovaj problem se može zaobići ako, dok neki čitaoc čita, ne puštamo nove čitaoce ako je u međuvremenu u red došao i pisac.

6. zadatak

Postavka

Data je sledeća sekvenca referenciranja stranica od strane nekog procesa:

2, 5, 7, 4, 5, 7, 5, 3, 2, 5, 6, 7, 5, 6, 7, 2, 4, 5, 7

Procesu su dodeljena 4 okvira, zamena se vrši lokalno, samo u skupu stranica dodeljenih tom procesu, a inicijalno nije učitana nijedna stranica ovog procesa. Koliko puta ovaj proces generiše straničnu grešku (page fault) ako je algoritam zamene stranica LRU, a koliko ako je OPT?

Rešenje

Odgovor LRU: 10

Odgovor OPT: 7

7. zadatak

Postavka

Ukratko objasniti tehniku korišćenja rezervoara (pool) slobodnih okvira.

Rešenje

Sistemi obično održavaju rezervoar (pool) slobodnih okvira: kada se traži slobodan okvir, odmah je raspoloživ u bazenu, tako da se nova stranica učitava pre nego što se pokrene izbacivanje neke druge radi dopune rezervoara (što je moguće uraditi kasnije).

8. zadatak

Postavka

U redu zahteva za pristup disku nalaze se zahtevi za pristup sledećim cilindrima (po redosledu pristizanja):

57, 38, 90, 125, 65, 36, 46.

Prethodno opsluženi zahtev je bio na cilindru 41, a glava se kreće prema cilindrima sa većim brojevima. Napisati redosled opsluživanja ovih zahteva ukoliko je algoritam raspoređivanja LOOK.

Rešenje

Odgovor: 46, 57, 65, 90, 125, 36, 38.

9. zadatak

Postavka

Ukratko opisati principe mikrokernel arhitekture operativnog sistema.

Rešenje

• Motiv: svesti OS jezgro na minimum, sve nepotrebne delove pretvoriti u sistemske programe i procese koji rade u korisničkom modu.

• U kernelu ostaje samo sistemi za upravljanje procesa i memorije.

• Prednosti: proširivost, promenljivost i prenosivost.
• Mane: lošije performanse.

10. zadatak

Postavka

Koji mehanizam koristi sistem Android da bi iz Java programa pozivao usluge iz C biblioteka?

Rešenje

JNI (Java Native Interface)