ОС1/Септембар 2011 - Историја измена

KockaAdmiralac: Formatiranje

2022-07-19T20:37:21Z

Formatiranje

← Старија измена		Верзија на датум 19. јул 2022. у 22:37
Ред 21:		Ред 21:

	=== Rešenje ===		=== Rešenje ===
	<syntaxhighlight lang = "c">		<syntaxhighlight lang="c">
	int main(int argc, char* argv[]) {		int main(int argc, char* argv[]) {
	if(argc < 2)		if (argc < 2) {
	return -1;		return -1;
			}
	pid_t pid = fork();		pid_t pid = fork();
			if (pid < 0) {
	if(pid < 0)		return -2;
	return -2;		} else if (pid == 0) {
	else if(pid == 0)		execlp(argv[1]);
	execlp(argv[1]);		} else {
	else wait(0);		wait(0);
			}
	return 0;		return 0;

	}		}
	</syntaxhighlight>		</syntaxhighlight>
Ред 48:		Ред 47:

	=== Rešenje ===		=== Rešenje ===
	<syntaxhighlight lang = "~~ada~~">		<syntaxhighlight lang="c">
	Semaphore xySem(0), zSem(0);		Semaphore xySem(0), zSem(0);
	int x, y, z;		int x, y, z;

	//A:		// A:
	while(1) {		while (1) {
	x = ...;		x = ...;
	y = ...;		y = ...;
	xySem.signal();		xySem.signal();
	zSem.wait();		zSem.wait();
	cout << z;		cout << z;
	}		}
	//B:
	while(1) {		// B:
	xySem.wait();		while (1) {
	z = x + y;		xySem.wait();
	zSem.signal();		z = x + y;
			zSem.signal();
	}		}
	</syntaxhighlight>		</syntaxhighlight>
Ред 73:		Ред 73:

	=== Rešenje ===		=== Rešenje ===
	Preklopi se realizuju bez podrške bilo kakve interakcije sa OS, tako što se na ulasku u određeni potprogram koji je alociran u neki preklop, prevodilac generiše kod koji proverava da li je taj kod učitan u preklop i učitava ga ako nije. Ako program koristi niti koje obezbeđuje OS, sistem održavanja preklopa (u odgovornosti programa) i promene konteksta niti (u odgovornosti OS) nemaju interakciju i ne znaju jedan za drugog.		Preklopi se realizuju bez podrške bilo kakve interakcije sa operativnim sistemom, tako što se na ulasku u određeni potprogram koji je alociran u neki preklop, prevodilac generiše kod koji proverava da li je taj kod učitan u preklop i učitava ga ako nije. Ako program koristi niti koje obezbeđuje operativni sistem, sistem održavanja preklopa (u odgovornosti programa) i promene konteksta niti (u odgovornosti operativnog sistema) nemaju interakciju i ne znaju jedan za drugog.

	Može se dogoditi sledeće:		Može se dogoditi sledeće:
	*jedna nit uđe u izvršavanje nekog potprograma P koji pripada jednom preklopu, proveri i po potrebi učita kod za taj potprogram u preklop X.		* jedna nit uđe u izvršavanje nekog potprograma P koji pripada jednom preklopu, proveri i po potrebi učita kod za taj potprogram u preklop X.
	*OS izvršava promenu konteksta niti i pokrene drugu nit		* operativni sistem izvršava promenu konteksta niti i pokrene drugu nit
	*ova druga nit ulazi u potprogram Q koji pripada drugom preklopu		* ova druga nit ulazi u potprogram Q koji pripada drugom preklopu
	*sistem preklopa učitava preklop kome pripada Q na mesto X		* sistem preklopa učitava preklop kome pripada Q na mesto X
	*ponovo dođe do promene konteksta i prva nit nastavi od adrese koju očekuje (potprogram P) ali se tu nalazi kod potprograma Q.		* ponovo dođe do promene konteksta i prva nit nastavi od adrese koju očekuje (potprogram P) ali se tu nalazi kod potprograma Q.

	== 6. zadatak ==		== 6. zadatak ==
	=== Postavka ===		=== 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:		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:
			<div class="abc-list">
	a) dvostruko ulančana lista slobodnih fragmenata uređenih po veličini ili		# dvostruko ulančana lista slobodnih fragmenata uređenih po veličini ili
			# dvostruko ulančana lista slobodnih fragmenata uređenih po poziciji u memoriji.
	b) dvostruko ulančana lista slobodnih fragmenata uređenih po poziciji u memoriji.		</div>

	Kratko obrazložiti.		Kratko obrazložiti.

Ред 113:		Ред 113:

	=== Rešenje ===		=== Rešenje ===
	#~~Hash~~ tabela sa dvostruko ulančanim listama za rešavanje kolizija:		# Heš tabela sa dvostruko ulančanim listama za rešavanje kolizija:
	#*Pronalaženje ulaza sa datim imenom - O(n)		#* Pronalaženje ulaza sa datim imenom - O(n)
	#*Brisanje pronađenog ulaza (ne računajući pronalaženje po imenu) - O(1)		#* Brisanje pronađenog ulaza (ne računajući pronalaženje po imenu) - O(1)
	#Dvostruko ulančana lista sa pokazivačima na glavu i rep liste:		# Dvostruko ulančana lista sa pokazivačima na glavu i rep liste:
	#*Pronalaženje ulaza sa datim imenom - O(n)		#* Pronalaženje ulaza sa datim imenom - O(n)
	#*Brisanje pronađenog ulaza (ne računajući pronalaženje po imenu) - O(1)		#* Brisanje pronađenog ulaza (ne računajući pronalaženje po imenu) - O(1)

	== 10. zadatak ==		== 10. zadatak ==
Ред 125:		Ред 125:

	=== Rešenje ===		=== Rešenje ===
	512KB / 8B = 64K ~~ulaza~~ = 2^16		<math>\frac{512KB}{8B} = 64K = 2^{16}</math> ulaza

	~~Maksimalna veličina je 2^16 * 2^16 * 512KB = 2^51B = 2PB~~

			Maksimalna veličina je <math>2^{16} \cdot 2^{16} \cdot 512KB = 2^{51}B = 2PB</math>

	[[Категорија:Рокови]]		[[Категорија:Рокови]]
	[[Категорија:ОС1]]		[[Категорија:ОС1]]

Ivan Pešić: средити 10. задатак

2021-09-20T16:40:58Z

средити 10. задатак

Нова страница

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2011/septembar/Sep%202011.doc Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Ukratko objasniti osnovni motiv nastanka koncepta multiprogramiranja.

=== Rešenje ===
Kod monoprocesnih računara uz sporu obradu i spore ulazno-izlazne uređaje, izvršavanje samog programa i iskorišćenje procesora je bilo slabo. Rešenje (multiprogramiranje) ogleda se u učitavanju više procesa u operativnu memoriju i njihovom uporedom izvršavanju. Dok jedan proces čeka na završetak I/O operacije, procesor može da izvršava instrukcije nekog drugog procesa.

== 2. zadatak ==
=== Postavka ===
Zašto nije dobro koristiti uposleno čekanje u prekidnoj rutini?

=== Rešenje ===
Dok se ne završi uposleno čekanje neće biti moguće promeniti kontekst jer se interrupt bit setuje na 0 pri ulasku u prekidnu rutinu. Pošto se kontekst neće moći promeniti, ceo sistem će ostati blokiran tu (ako se koristi jednoprocesorski sistem). Prekidna rutina takođe treba da bude što kraća da bi sistem imao što bolji "osećaj" o vremenu.

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

=== Rešenje ===
<syntaxhighlight lang = "c">
int main(int argc, char* argv[]) {
if(argc < 2)
return -1;

pid_t pid = fork();

if(pid < 0)
return -2;
else if(pid == 0)
execlp(argv[1]);
else wait(0);

return 0;

}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Korišćenjem standardnih brojačkih semafora u školskom jezgru, na jeziku C++ napisati globalne deklaracije i inicijalizacije, kao i kod tela dve uporedne niti A i B koje ciklično rade sledeće:

A: upisuje vrednost u deljene promenljive x i y, a zatim čeka da proces B upiše zbir x i y u promenljivu z čiju vrednost ispisuje na standardni izlaz;

B: čeka da proces A upiše vrednosti u deljene promenljive x i y, zatim ove dve vrednosti sabira i zbir upisuje u deljenu promenljivu z.

=== Rešenje ===
<syntaxhighlight lang = "ada">
Semaphore xySem(0), zSem(0);
int x, y, z;

//A:
while(1) {
x = ...;
y = ...;
xySem.signal();
zSem.wait();
cout << z;
}
//B:
while(1) {
xySem.wait();
z = x + y;
zSem.signal();
}
</syntaxhighlight>

== 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 ===
Preklopi se realizuju bez podrške bilo kakve interakcije sa OS, tako što se na ulasku u određeni potprogram koji je alociran u neki preklop, prevodilac generiše kod koji proverava da li je taj kod učitan u preklop i učitava ga ako nije. Ako program koristi niti koje obezbeđuje OS, sistem održavanja preklopa (u odgovornosti programa) i promene konteksta niti (u odgovornosti OS) nemaju interakciju i ne znaju jedan za drugog.
Može se dogoditi sledeće:
*jedna nit uđe u izvršavanje nekog potprograma P koji pripada jednom preklopu, proveri i po potrebi učita kod za taj potprogram u preklop X.
*OS izvršava promenu konteksta niti i pokrene drugu nit
*ova druga nit ulazi u potprogram Q koji pripada drugom preklopu
*sistem preklopa učitava preklop kome pripada Q na mesto X
*ponovo dođe do promene konteksta i prva nit nastavi od adrese koju očekuje (potprogram P) ali se tu nalazi kod potprograma Q.

== 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 ===
Lista slobodnih fragmenata uređenih po poziciji u memoriji je efikasnija zato što ako se dealocira, veća je verovatnoća da će fragmenti biti jedni pored drugih. Uređenje po veličini može značiti da treba proći čitavu listu u potrazi za fragmentima.

== 7. zadatak ==
=== Postavka ===
Kojom tehnikom se nedeljivi uređaj može učiniti virtuelno deljivim?

=== Rešenje ===
Tehnikom pod imenom spooling.

== 8. zadatak ==
=== Postavka ===
U fajl podsistemu nekog operativnog sistema ne vodi se tabela otvorenih fajlova za svaki proces, već postoji samo jedna globalna tabela otvorenih fajlova za ceo sistem. Drugim rečima, ne postoji nikakva informacija o upotrebi otvorenog fajla lokalna (privatna) za pojedinačni proces, već su sve takve informacije globalno deljene. Da li pojam pokazivača trenutne lokacije (kurzora) za čitanje/upis u fajl ima smisla čuvati u globalnoj tabeli otvorenih fajlova i zašto?

=== Rešenje ===
Nema smisla jer će svaki proces imati različitu vrednost ovog kurzora.

== 9. zadatak ==
=== Postavka ===
Dati procenu kompleksnosti u najgorem slučaju datih operacija sa direktorijumom u odnosu na broj postojećih fajlova n u direktorijumu, za navedene implementacije direktorijuma.

=== Rešenje ===
#Hash tabela sa dvostruko ulančanim listama za rešavanje kolizija:
#*Pronalaženje ulaza sa datim imenom - O(n)
#*Brisanje pronađenog ulaza (ne računajući pronalaženje po imenu) - O(1)
#Dvostruko ulančana lista sa pokazivačima na glavu i rep liste:
#*Pronalaženje ulaza sa datim imenom - O(n)
#*Brisanje pronađenog ulaza (ne računajući pronalaženje po imenu) - O(1)

== 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 ===
512KB / 8B = 64K ulaza = 2^16

Maksimalna veličina je 2^16 * 2^16 * 512KB = 2^51B = 2PB

[[Категорија:Рокови]]
[[Категорија:ОС1]]