ОС1/Јул 2019

Zadaci na stranici predmeta.

1. zadatak

Postavka

Šta se smatra multiprocesorskim računarskim sistemom? Šta je simetričan multiprocesorski sistem?

Rešenje

Multiprocesorski sistem je sistem sa više procesora koji imaju zajedničku memoriju. Simetričan multiprocesorski sistem znači da su svi procesori opšte namene, jednaki i imaju isto vreme pristupa operativnoj memoriji. Asimetrični multiprocesorski sistem ima i specijalizovane procesore ili procesore sa različitim vremenom pristupa memoriji.

2. zadatak

Postavka

Neki procesor prilikom obrade prekida prebacuje svoje izvršavanje na korišćenje posebnog pokazivača steka koji se koristi u privilegovanom režimu rada, i pritom čuva sve registre na steku na čiji vrh ukazuje ovaj pokazivač. Operativni sistem na ovom procesoru koristi samo jedan sistemski stek za izvršavanje celog kernel koda. Da li se kontekst izvršavanja procesa (kontekst procesora) može čuvati na ovom steku?

Rešenje

Ne. Ukoliko bi se na tom steku čuvao kontekst prekinutog procesa, jedino na njega bismo se mogli i vratiti jer bi svi ostali konteksti bili ispod kontekteksta trenutnog procesa na steku.

3. zadatak

Postavka

Korišćenjem niti u školskom jezgru napisati funkciju sum koja kreira nit koja će sabrati sve elemente zadatog niza zadate dužine i rezultat upisati na traženo mesto; u slučaju greške ove funkcije vraćaju negativnu vrednost.

int sum (int array[], size_t size, long* result);

Rešenje

class SumThread: public Thread {
    public:
        SumThread(int* arr, size_t _size, long* res): array(arr), size(_size), result(res) {}
    protected:
        void run() {
            long res = 0;
            for (size_t i = 0; i < size; i++) {
                res += array[i];
            }
            *result = res;
        }
    private:
        int* array;
        size_t size;
        long* result;
};

int sum (int array[], size_t size, long* result) {
    if (result == nullptr) return -1;
    SumThread* st = new SumThread(array, size, result);
    st->start();
    delete st;
    return 0;
}

4. zadatak

Postavka

Napisati pseudokod koji obezbeđuje međusobno isključenje pristupa kritičnoj sekciji dva procesa pomoću Petersonovog algoritma.

Rešenje

shared var turn : integer := 1, flag1, flag2 : boolean := false;
process P1
begin
    loop
        flag1 := true;
        turn := 2;
        while flag2 and turn = 2 do null;
        <critical section>
        flag1 := false;
        <non-critical section>
    end
end P1;
process P2
begin
    loop
        flag2 := true;
        turn := 1;
        while flag1 and turn = 1 do null;
        <critical section>
        flag2 := false;
        <non-critical section>
    end
end P2;

5. zadatak

Postavka

Zbog čega operativni sistem ne radi zamenu (swapping) procesa njegovim izbacivanjem iz memorije prilikom svake promene konteksta, kada procesu koji je izgubio procesor memorija svakako nije potrebna?

Rešenje

Zato što je pristup hard disku vrlo spor te će takva implementacija znatno uticati na performanse. Ovo se primenjivalo na Windows 3.1, i bilo je vrlo sporo. Danas, swapping se koristi kada nema dovoljno mesta u operativnoj memoriji.

6. zadatak

Postavka

Šta je kompakcija kod kontinualne alokacije memorije?

Rešenje

Kod kontinualne alokacije može doći do eksterne fragmentacije, odnosno da su slobodni fragmenti toliko mali da ni jedan proces ne može stati na tom delu, ali zbirno ih ima dovoljno za neki procos. Kompakcija rešava taj problem realokacijom svih zauzetih delova i spajanjem svih slobodnih fragmenata u jedan veliki slobodan fragment. Dok se dešava kompakcija, nijedan proces koji se pomera se ne može izvršavati.

7. zadatak

Postavka

Virtuelni adresni prostor je velične 8GB, a adresibilna jedinica je 16-bitna reč. Stranica je veličine 4KB, a preslikavanje je u dva nivoa, s tim da PMT prvog nivoa ima dva puta manje ulaza nego PMT drugog nivoa. Prikazati strukturu virtuelne adrese i označiti širinu svakog polja.

Rešenje

VA(32): Page1(10), Page2(11), Offset(11)

8. zadatak

Postavka

Navesti tipične usluge operativnog sistema vezane za pristup blokovski orijentisanom ulaznom uređaju sa direktnim pristupom i predložiti potpise odgovarajućih funkcija za te sistemske pozive.

Rešenje

Osnovne usluge jesu pisanje i čitanje.

int readBlock(int fd, BlockNo block, void* buffer);
int writeBlock(int fd, BlockNo block, void* buffer);

9. zadatak

Postavka

Objasniti koncept ACL (access control list).

Rešenje

Da bi se fajlovi zaštitili, jedan način je da se ograniče prava pristupa korisnika. Potrebno je definisati koji korisnik (ili grupa korisnika) može da izvršava koju operaciju. Jedan pristup je svakom fajlu pridružiti listu ovih parova (korisnik i operacija). Takva lista je lista kontrole pristupa (ACL).

10. zadatak

Postavka

Fajl sistem primenjuje FAT alokaciju, s tim da se i slobodni blokovi ulančavaju u listu. U strukturi FCB polje head sadrži broj prvog bloka sa sadržajem fajla, a polje size veličinu sadržaja. Globalna promenljiva fat_free_head sadrži broj prvog bloka (glavu liste), a fat_free_tail poslednjeg bloka (rep liste) u lancu slobodnih. FAT je u memoriju učitana kao niz. Napisati funkciju jezgra truncate koja briše sadržaj fajla na čiji FCB ukazuje argument.

Rešenje

const unsigned long FAT_SIZE = ...;
unsigned long FAT[FAT_SIZE];

void truncate(FCB* file) {
    unsigned long b = file->head;
    for (unsigned long i = 0; i < file->size; ++i) {
        unsigned long next = FAT[b];
        FAT[b] = 0;
        // Ovde se smatra da fat_free_tail pokazuje na blok 0 kada nema slobodnih blokova.
        if (fat_free_tail) {
            FAT[fat_free_tail] = b;
            fat_free_tail = b;
        } else {
            fat_free_head = b;
            fat_free_tail = b;
        }
        b = next;
    }
    file->size = 0;
    file->head = 0;
}