ОС1/Јул 2011

Zadaci na stranici predmeta.

1. zadatak

Postavka

Ako se nad sledećim programom kreira jedan proces, koliko će ukupno procesa biti kreirano (uključujući i taj jedan početni), 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

Petlja ukupno ima dve iteracije. U prvoj iteraciji početni proces pravi jedan drugi, dok u drugoj iteraciji oba procesa prave još jedan, pa na kraju ima 4 procesa.

2. zadatak

Postavka

Šta je razlika između „teškog“ procesa i niti (thread)?

Rešenje

Teški proces (ili samo proces) je jedno izvršavanje jednog programa sa sopstvenim adresnim prostorom odnosno memorijskim kontekstom, dok se svaki tok kontrole koji koristi taj adresni prostor zove laki proces (ili nit).

3. zadatak

Postavka

Šta je problem sledeće implementacije kritične sekcije uposlenim čekanjem?

process P1
begin
  loop
    while flag2 = true do null end; (* Busy wait *)
    flag1 := true;
    <critical section>          (* Critical section *)
    flag1 := false;             (* Exit protocol *)
    <non-critical section>
  end
end P1;

process P2
begin
  loop
    while flag1 = true do null end; (* Busy wait *)
    flag2 := true;
    <critical section>          (* Critical section *)
    flag2 := false;             (* Exit protocol *)
    <non-critical section>
  end
end P2;

Rešenje

Ne obezbeđuje međusobno isključenje, dolazi do utrkivanja.

4. zadatak

Postavka

Na jeziku C++ implementirati klasu BoundedBuffer koja realizuje ograničeni bafer elemenata tipa Data kapaciteta N pomoću semafora.

Rešenje

const int N = ...;
class Data;
class BoundedBuffer {
public:
    BoundedBuffer();
    void append(Data*);
    Data* take();
private:
    Semaphore mutex, spaceAvailable, itemAvailable;
    Data* buffer[N];
    int head, tail;
};

BoundedBuffer::BoundedBuffer() : mutex(1), spaceAvailable(N), itemAvailable(0), head(0), tail(0) {}

void BoundedBuffer::append(Data* d) {
    spaceAvailable.wait();
    mutex.wait();
    buffer[tail] = d;
    tail = (tail + 1) % N;
    mutex.signal();
    itemAvailable.signal();
}

Data* BoundedBuffer::take() {
    itemAvailable.wait();
    mutex.wait();
    Data* d = buffer[head];
    head = (head + 1) % N;
    mutex.signal();
    spaceAvailable.signal();
    return d;
}

5. zadatak

Postavka

Šta je osnovna razlika između tehnike dinamičkog učitavanja i tehnike preklopa (overlays)?

Rešenje

Tehnikom dinamičkog učitavanja proces alocira memoriju i iz fajlova učitava delove samo ako su stvarno potrebni.

Tehnika preklopa podrazumeva da se moduli u kojima su grupisani programi i/ili podaci koji se koriste zajedno a u alternaciji sa drugim modulima dinamički učitavaju u memoriju i izbacuju iz nje na isto mesto, preklapajući se sa onim modulima sa kojima nisu potrebni istovremeno.

Razlike su u tome što:

1. više modula se naizmenično učitava na isto mesto u virtuelnom adresnom prostoru procesa, preklapajući se,
2. modul može biti odsutan ne samo kada mu se prvi put pristupi, nego i kasnije, jer je na njegovo mesto učitan neki drugi modul, pa program o tome mora da vodi računa; program mora da vodi računa o tome koji je od preklopljenih modula trenutno učitan na datom mestu, kao i o tome da je pre pristupa određenom potprogramu/podatku modul u kome se on nalazi sigurno učitan, isto kao i kod dinamičkog učitavanja, i
3. ako neki modul koji se preklapa sadrži podatke koji se menjaju, pre nego što se na njegovo mesto učita neki drugi modul, mora se sačuvati sadržaj izbačenog modula upisom u neki fajl, ako će taj modul kasnije biti ponovo upotrebljavan.

6. zadatak

Postavka

Ukratko objasniti zašto je kod segmentne organizacije virtuelne memorije obavezna provera prekoračenja granice segmenta prilikom svakog adresiranja, a kod stanične organizacije ta provera ne postoji.

Rešenje

Kod segmentne organizacije virtuelne memorije obavezno se proverava prekoračenje granice segmenta jer ako prelazi limit to znači da je proces adresirao virtuelnu adresu izvan deklarisanog segmenta. Kod stranične organizacije virtuelni adresni prostor procesa je podeljen na stranice iste veličine a fizički okviri su iste veličine kao stranice.

7. zadatak

Postavka

U nekom sistemu postoje sledeći sistemski pozivi:

int async_write (char* buffer);
void wait (int request_id);

Operacija async_write asinhrono zadaje operaciju izlaza datog niza znakova na neki izlazni uređaj i vraća interni sistemski identifikator tog zahteva (veći od 0), odnosno kod greške (manji od nula). Operacija wait suspenduje pozivajući proces sve dok operacija sa datim identifikatorom nije završena. Korišćenjem ovih sistemskih poziva, realizovati sinhroni izlaz: int sync_write (char* buffer);

Rešenje

int sync_write (char* buffer) {
    int id = async_write(buffer);
    if (id < 0) {
        return id;
    }
    wait(id);
    return 0;
}

8. zadatak

Postavka

Ukratko objasniti kako se u Unix fajl sistemu definišu prava pristupa do fajla.

Rešenje

Po 3 bita (rwx) za vlasnika, grupu i ostale (ukupno 9 bitova) određuju prava pristupa do fajla.

9. zadatak

Postavka

Navesti razlog zašto bi neki fajl sistem koristio klastere na disku različite veličine.

Rešenje

Zbog smanjenja interne fragmentacije.

10. zadatak

Postavka

Ukratko objasniti šta je inkrementalni, a šta totalni bekap (backup) fajl sistema?

Rešenje

1. Inkrementalni bekap: bekapuju se samo izmenjeni fajlovi.
2. Totalni bekap: kopiraju se svi fajlovi iz jednog fajl sistema ili njegovog dela.