Elektrotehnički fakultet
Operativni sistemi 1
u Beogradu
Upravljanje procesima
Zad 1. Jun 2005.
(b)(10)
Dat je sledeći C API nekog operativnog sistema za koncept
standardnog brojačkog semafora:
typedef unsigned int SemID;
SemID createSemaphore ();
void releaseSemaphore (SemID);
void initSemaphore(SemID, int value);
void wait(SemID);
void signal(SemID);
Korišćenjem ovih funkcija 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
.
(c)(5) Posmatraju se dva procesa koji jedan drugom šalju i primaju podatke
korišćenjem dva kružna ograničena bafera A i B veličine po 4KB. Ukoliko je
bafer pun, proces koji želi u njega da upiše podatak se blokira sve dok se u
baferu ne pojavi mesto za upis podatka. Ova dva procesa izgledaju ovako:
Process 1:
Process 2:
send N bytes to BuffA
while (take 4KB of data
while(take data from BuffB)
from BuffA)
display data
process data
end
send 4KB result to BuffB
end
Za koju vrednost N > 4K ovi procesi uzrokuju mrtvo blokiranje (
deadlock
)?
Pretpostaviti da komanda
take
čeka neko vreme da se podaci pojave u
baferu (
timeout
). Ako se podaci jave u predviđenom roku, vraća vrednost
true
, inače
false
.
(d) Šta bi se desilo u tački c), da komanda
take
nema
timeout
? Koliko je
tada N koje uzrokuje blokiranje?
Operativni sistemi 1 Copyright
2006 Miloš Milovanović
Mart 2006
1 / 21
Elektrotehnički fakultet
Operativni sistemi 1
u Beogradu
Rešenje:
(b)(10)
// Globalne deklaracije i inicijalizacije:
SemID xySem = createSemaphore();
SemID zSem = createSemaphore();
initSemaphore(xySem,0);
initSemaphore(zSem,0);
// Kod tela niti A:
while (1) {
x = ...;
y = ...;
signal(xySem);
wait(zSem);
printf("%d
", z);
}
// Kod tela niti B:
while (1) {
wait(xySem);
z = x+y;
signal(zSem);
}
(c)(5) Odgovor:
N > 12 K.
Obrazloženje: mrtvo blokiranje nastaje u sledećem slučaju: bafer B je pun
sa 4KB podataka, ali proces 1 nije stigao do tačke kada iz njega uzima
podatke, jer želi da pošalje još podataka u bafer A; proces 2 je već uzeo 4KB
podataka iz bafera A i procesirao ih, ali ne može da ih smesti u bafer B jer
je ovaj pun; bafer A je pun sa 4KB podataka; proces 1 želi da pošalje bar još
jedan podatak u bafer A, ali ne može, jer je ovaj pun. Dakle, proces 1 je već
poslao 3 puta po 4KB podataka kroz bafer A, ali želi da pošalje bar još jedan
pre nego što uzme rezultat iz bafera B.
(d) Bilo koje N će uzrokovati blokiranje.
Operativni sistemi 1 Copyright
2006 Miloš Milovanović
Mart 2006
2 / 21
Elektrotehnički fakultet
Operativni sistemi 1
u Beogradu
Potrebno je napisati C/C++ kod koji će alocirati prostor za stek i formirati
početni kontekst novokreirane niti na tom steku. Pokazivač na vrh tog
steka treba smestiti u promenljivu
p
. Ovaj kod treba da obezbedi da se
prilikom promene konteksta sa
yield(&currSP,&p)
, gde je
currSP
pokazivač na vrh steka tekuće niti, započne izvršavanje koda nove niti koji
je definisan funkcijom
f()
. Iz funkcije
f()
se nikada ne izlazi sa
return
.
(b)(10)
Funkcija
wait()
iz C API nekog operativnog sistema vrši
sinhronizaciju procesa roditelja i njegove dece: proces-roditelj koji izvrši
poziv ove operacije blokira se sve dok svi njegovi potomci ne završe
izvršavanje. Predložiti realizaciju ove sinhronizacije pomoću standardnih
brojačkih semafora. Precizno navesti:
koje podatke treba obezbediti u PCB-u; precizno navesti njihove
deklaracije i objasniti njihovu namenu;
navesti tačno gde, kada i kako se ovi podaci inicijalizuju i menjaju;
pod takvim pretpostavkama, napisati kod operacije
wait()
.
(c)(5) U operativnim sistemima koji podržavaju i koncept procesa i
koncept niti, režijsko vreme kreiranja procesa značajno je veće, i po
nekoliko desetina puta, od vremena kreiranja niti. Šta po Vašem mišljenju
najviše utiče na ovakav odnos? Dati što preciznije objašnjenje.
Operativni sistemi 1 Copyright
2006 Miloš Milovanović
Mart 2006
4 / 21
Elektrotehnički fakultet
Operativni sistemi 1
u Beogradu
Rešenje:
(a)(10)
const unsigned long stackSize = ...;
int* p = new int[stackSize]; // U jeziku C može se
// koristiti malloc/calloc
*p++ = (int)(&f); // Smesti "povratnu adresu" na stek
p+=16; // Simulira 16 puta "push rn" za r0 do r15
(b)(10)
Potrebno je obezbediti sledeće strukture podataka i operacije:
Sastavni deo PCB-a treba da bude jedan brojački semafor
waitChildren
inicijalizovan na 0 prilikom kreiranja niti, koji služi
za sinhronizaciju roditelja i dece:
Semaphore waitChildren(0);
Sastavni deo PCB-a treba da bude pokazivač na roditeljsku nit koji se
inicijalizuje tako da ukazuje na roditelja koji kreira novu nit (to je
tekuća nit,
running
) prilikom kreiranja te nove niti:
// Deklaracija:
Thread* myParent;
// Incijalizacija:
myParent = running;
Sastavni deo PCB-a je celobrojni podatak
numOfChildren
koji čuva
broj kreiranih potomaka. Inicijalno je postavljen na 0, uvećava se za
jedan prilikom kreiranja potomka, npr. u operaciji
fork()
:
running->numOfChildren++
Na samom kraju svog izvršavanja, svaka nit, ukoliko ima roditelja,
signalizira roditelju svoj završetak:
if (myParent) myParent->waitChildren.signal();
Operacija
wait()
:
void wait () {
while(numOfChildren>0) {
waitChildren.wait();
numOfChildren--;
Operativni sistemi 1 Copyright
2006 Miloš Milovanović
Mart 2006
5 / 21
