ОС1/Октобар 2013

Zadaci na stranici predmeta.

1. zadatak

Postavka

Koja je razlika između multiprocesorskih i distribuiranih računarskih sistema?

Rešenje

Videti prvi zadatak iz julskog roka 2012. godine.

2. zadatak

Postavka

Korišćenjem operacije yield(jmp_buf old, jmp_buf new) koja čuva kontekst niti čiji je jmp_buf dat kao prvi argument, oduzima joj procesor i restaurira kontekst niti čiji je jmp_buf dat kao drugi argument, kojoj predaje procesor, realizovati operaciju Semaphore::wait() u školskom jezgru.

Rešenje

Semaphore::wait() {
    lock();
    if (--val < 0) {
        jmp_buf old = Thread::running->context;
        blocked.put(Thread::running);
        Thread::running = Scheduler::get();
        jmp_buf new = Thread::running->context;
        yield(old, new);
    }
    unlock();
}

3. zadatak

Postavka

Koja je razlika između (teškog) procesa i niti (thread)?

Rešenje

Teški proces je izvršavanje jednog programa sa sopstvenim adresnim prostorom dok se nitima, tj. lakim procesima zove svaki tok kontrole koji koristi taj adresni prostor.

4. zadatak

Postavka

Korišćenjem standardnih brojačkih semafora, napisati kod za inicijalizaciju i potrebnu sinhronizaciju kritične sekcije u koju može ući najviše N uporednih procesa.

Rešenje

var mutex : Semaphore := N;

process P:
    begin
        loop
            wait(mutex);
            <critical>
            signal(mutex);
            <non-critical>
        end
    end
end P;

5. zadatak

Postavka

Ako tokom svog prvog prolaza linker u svojoj tabeli ne pronađe simbol koji je definisan u tekućem fajlu (izvozi se), da li će prijaviti grešku? Obrazložiti.

Rešenje

Ne jer ako se ne nalazi u tabeli simbola znači da simbol nije definisan i ne dolazi do konflikta imena.

6. zadatak

Postavka

Koja je razlika između best fit i worst fit algoritma kontinualne alokacije memorije?

Rešenje

Best fit algoritam ima cilj da nakon alokacije ostane što manji slobodan fragment kako bi se smanjila eksterna fragmentacija.

Worst fit algoritam ima cilja da preostali slobodan fragment bude što upotrebljiviji, odnosno takav da se poveća šansa da se može upotrebiti za dalju alokaciju, tj. ostavlja najveći slobodan fragment nakon alokacije.

7. zadatak

Postavka

U nekom sistemu sa virtuelnom memorijom broj stranice u virtuelnoj adresi je veličine 48 bita. Da bi čuvanje PMT učinio izvodljivim, sistem koristi hash tabelu sa 64K ulaza za smešanje PMT svakog procesa. Hash funkcija je prosta modulo funkcija: ulaz u tabelu određuje se pomoću 16 najnižih bita broja stranice. U svakom ulazu hash tabele nalazi se 64-bitna glava ulančane liste zapisa za alocirane stranice koje se preslikavaju u taj ulaz. Svaki zapis sadrži viših 32 bita broja stranice, broj okvira u koji je ta stranica preslikana (32 bita, vrednost 0 označava da stranica ne može da se preslika) i pokazivač na sledeći zapis (64 bita, vrednost 0 označava kraj liste). Neki proces je alocirao 256 najnižih i 256 najviših stranica svog virtuelnog adresnog prostora. Koliko prostora (u bajtovima) ukupno zauzima PMT ovog procesa?

Rešenje

Najnižih 256 će svi stati u prvi ulaz, tako da oni zauzimaju (32+32+64)*256 + 64 = 32832 bita. Najviši zauzimaju isto toliko, samo što svi staju u poslednji ulaz. Ukupno zauzima 2*32832 = 65664 bita, to jest 65664/8 = 8208B

8. zadatak

Postavka

U nekom sistemu podržan je samo asinhroni izlaz na izlazni uređaj pomoću sledeće funkcije IOReqID output (IODevID deviceID, IOReq* request); koja zadaje (asinhrono) izlaznu operaciju specifikovanu drugim argumentom na uređaju identifikovanom prvim argumentom. Ova funkcija odmah vraća kontrolu pozivaocu, uz identifikaciju zadate operacije (rezultat tipa IOReqID je veći od 0 u slučaju ispravno zadatog zahteva).

Funkcija void ioWait (IOReqID); blokira pozivajući proces sve dok operacija identifikovana argumentom nije završena u potpunosti. Pomoću ovih funkcija realizovati funkciju koja, u odnosu na jedan argument, može zadati operaciju sinhrono ili asinhrono, prema želji pozivaoca.

Rešenje

IOReqID output_user(IODevID deviceID, IOReq* request, bool synchronous) {
    IOReqID id = output(deviceID, request);
    if (synchronous && id > 0) {
        wait(id);
    }
    return id;
}

9. zadatak

Postavka

Šta označava skraćenica FTP? Ukratko objasniti čemu služi ovaj protokol.

Rešenje

File Transfer Protocol - u razmeni fajlova učestvuju 2 računara. Jedan igra ulogu servera a drugi ulogu klijenta. Na oba računara se izvršavaju programi koji implementiraju ovaj protokol.

10. zadatak

Postavka

Koja metoda alokacije fajlova je efikasnija za direktni pristup, ulančana ili indeksirana i zašto?

Rešenje

Efikasnija je indeksirana; kod ulančane alokacije je efikasan sekvencijalan pristup, ali direktni pristup nekom bloku n podrazumeva pristup svim blokovima počev od prvog pa do njega. Jedna od najvecih pogodnosti indeksne alokacije je upravo direktni pristup, jer indeksna alokacija podrazumeva postojanje indeksnog bloka u kome se nalazi spisak brojeva blokova sa sadržajem fajla redom, koji omogućava vrlo efikasan direktan pristup.