OS1/Jul 2017

Zadaci sa stranice predmeta.

1. zadatak

Postavka

Šta je hard, a šta soft sistem za rad u realnom vremenu (real-time system)?

Rešenje

Tvrdi sistemi za rad u realnom vremenu su sistemi u kojima odziv mora da stigne u određenom vremenu (deadline). Prekoračenje može dovesti do rezličitih katastrofa. Meki sistemi za rad u realnom vremenu su sistemi kojima je rok bitan ali smeju ga prekoračiti dok god performanse ulaze u zadate okvire.

2. zadatak

Postavka

Objasniti značenje mašinske instrukcije tipa test-and-set i njenu upotrebu u jezgru operativnog sistema.

Rešenje

test_and_set je instrukcija koja omogućava sinhronizaciju na hardverskom nivou. Služi za međusobno isključenje izvršavanja na više procesora. Ona atomično čita i vraća sadržaj zadate memorijske lokacije, i u tu lokaciju upisuje vrednost 1. Može da se koristi u implementaciji lock() funkcije.

3. zadatak

Postavka

Korišćenjem školskog jezgra napisati program koji u n uporednih niti izračunava kvadrat svakog elementa nekog celobrojnog niza (a[i]*=a[i]) veličine n*k, tako što svaka nit obrađuje k elemanata^[sic] (jednu particiju niza).

Rešenje

class ArrThread : Thread {
    public:
        ArrThread(int* a, int s, int f): arr(a), start(s), finish(f) {}
    protected:
        void run() {
            for (int i = start; i < finish; i++) {
                arr[i] *= arr[i];
            }
        }
    private:
        int* arr;
        int start;
        int finish;
};

int main() {
    ArrThread* t[n];
    int start = 0;
    for (int i = 0; i < n; i++) {
        t[i] = new ArrThread(array, start, start + k);
        start += k;
    }
    for (int i = 0; i < n; i++) {
        delete t[i];
    }
    return 0;
}

4. zadatak

Videti zadatak iz julskog roka 2019.

5. zadatak

Postavka

Precizno objasniti zašto klasičan linker svoj posao obavlja u dva prolaza (a ne može samo ujednom). Obrazloženje ilustrovati primerom.

Rešenje

Linkerov zadatak je da spoji sve fajlove u jedan izvršni, ali da bi to uradio, linker mora naći sve simbole koji se uvoze odnosno izvoze.

U prvom prolazu analizira ulazne fajlove, veličinu njihovog binarnog sadržaja (prevoda), i pravi mapu exe fajla; osim toga, sakuplja infomacije iz tabela simbola obj fajlova i izgrađuje svoju tabelu simbola; u tu tabelu simbola unosi izvezene simbole iz obj fajlova, za koje odmah može da izračuna adresu u odnosu na ceo exe fajl. U drugom prolazu spaja sve te fajlove u jedan, i ujedno razrešava nerazrešena adresna polja mašinskih instrukcija na osnovu informacija o adresama u koje se preslikavaju simboli iz njegove tabele simbola.

Primer: Recimo da imamo dva objektna fajla, a.obj i b.obj. a.obj izvozi simbol f i uvozi simbol c. Linker će iz prvog objektnog fajla dodati u tabelu simbol f. b.obj uvozi simbol f i izvozi simbol c, pa će linker u svoju tabelu dodati simbol c. U drugom prolazu će linker razrešiti c polje u a.obj i polje f u b.obj.

6. zadatak

Postavka

Objasniti uslugu koju program očekuje od operativnog sistema ako koristi preklope (overlay).

Rešenje

Obaveza OS-a je samo da obezbedi uslugu (sistemski poziv) koji alocira deo (virtuelnog) adresnog prostora procesa, kao i uslugu kojom u dati prostor procesa učitava sadržaj iz nekog binarnog fajla i sadržaj iz memorije upisuje u neki fajl (uobičajene sistemske usluge za rad sa fajlovima); OS ne zna za šta se te usluge koriste, tj. ne zna da se one upotrebljavaju baš za dinamičko učitavanje i zamenu delova procesa.

7. zadatak

Postavka

Virtuelni adresni prostor je veličine 1GB, organizovan je segmentno, sa maksimalnom veličinom segmenta od 4KB, adresibilna jedinica je bajt. Svi segmenti nekog procesa su stvarne veličine od po 2KB i u fizičku memoriju smešteni su odmah jedan iza drugog, pri čemu segment broj 0 počinje od fizičke adrese F000h. Prikazati logičku strukturu virtuelne adrese i izračunati u koju fizičku adresu se preslikava virtuelna adresa 2543h.

Rešenje

VA(30) : seg(18) offset(12)

Virtuelna adresa 2543h tj. 0010 | 0101 0100 0011b pripada 2. segmentu koji počinje od fizičke adrese 10000h i završava na 10800h.

Fizička adresa se dobija sabiranjem bazne adrese u fizičkom adresnom prostoru i offsetnog dela virtuelne adrese: PA = 10000h + 543h = 10543h.

8. zadatak

Videti zadatak iz junskog roka 2021. godine.

9. zadatak

Videti zadatak iz junskog roka 2020. godine.

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

Pošto je blok veličine $2^{19}B$ a adresa $2^3B$ to znači da u jedan indeks može da stane $2^{16}$ adresa blokova. Konačan broj bajtova koji je na ovaj način mogu adresirati jeste $2^{16} \cdot 2^{16} \cdot 2^{19} = 2^{51}B = 2PB$.