ОС1/Јул 2020

Zadaci na stranici predmeta.

1. zadatak

Postavka

Na asembleru nekog zamišljenog RISC procesora sa load/store arhitekturom napisati program koji vrši prenos bloka podataka iz memorije na izlazni uređaj tehnikom programiranog izlaza korišćenjem prozivanja (polling). Samostalno usvojiti potrebne detaljne pretpostavke.

Rešenje

Pretpostavke:

• Memorija se prenosi sa adrese 1000h
• Ulazno/izlazni i adresni prostor su razdvojeni
• Kontrolni registar uređaja je na FF00h, registar podataka na FF01h a statusni registar na FF02h
• Adresiranje je bajtovsko
• Blok je veličine 100h bajtova
• Registri su veličine 16 bita i kad se čita ili piše iz memorije ili na uređaj koristi se najnižih 8 bita
• Najniži bit kontrolnog registra je bit Start, najniži bit statusnog registra je bit Ready
• Periferija automatski postaje nespremna za upis sledećeg podatka kada se u nju upiše podatak koji se još nije preneo

        load r0, #1000h             ; adresa
        load r1, #100h              ; brojač
        load r2, #0                 ; nula
        load r3, #1                 ; privremeni registar
        out FF00h, r3               ; pokrećemo periferiju
loop:   in FF02h, r3                ; čitamo statusni registar
        and r3, r3, #1              ; proveravamo ready bit
        jz loop                     ; ako je ready = 0 čitamo ponovo
        load r3, (r0)               ; učitavamo podatak iz memorije
        out FF01h, r3               ; šaljemo podatak na periferiju
        inc r0                      ; inkrementiramo adresu
        dec r1                      ; dekrementiramo brojač (postavlja se PSW)
        jnz loop                    ; ako brojač != 0 vraćamo se na čekanje
        load r3, #0                 ; gasimo periferiju
        out FF00h, r3

2. zadatak

Postavka

Korišćenjem školskog jezgra napisati kod klase koja apstrahuje nit koja, ukoliko se kreira sa neparnim celobrojnim parametrom, kreira još jednu takvu istu nit, samo sa za jedan manjim istim celobrojnim parametrom (sve dok ne stigne do 0), a u suprotnom se samo završava.

Rešenje

class ForkThread : public Thread {
    public:
        ForkThread(unsigned n) : n(n) {}
        virtual void run();
    private:
        unsigned n;
};

void ForkThread::run() {
    if (n % 2) {
        ForkThread thr(n-1);
        thr.start();
        thr.join();
    }
}

3. zadatak

Postavka

U nekom sistemu primenjuje se best-fit algoritam kontinualne alokacije memorije. Inicijalno je prostor veličine 512KB potpuno slobodan za alokaciju korisničkih procesa. Potom su različiti procesi zadavali sledeće zahteve (slovna oznaka označava proces koji je postavio zahtev, brojna oznaka označava veličinu alociranog prostora u KB, a minus označava gašenje procesa i oslobađanje njegove memorije):

A128, B32, C256, D64, A-, E16, F64, B-

Odgovoriti na sledeća pitanja koja se odnose na stanje memorije nakon ove sekvence zahteva:

1. Koliko je ukupno slobodnih fragmenata?
2. Kolika je veličina najmanjeg slobodnog fragmenta?
3. Kolika je veličina najvećeg slobodnog fragmenta?

Rešenje

Po koracima, alokacija memorije će izgledati ovako (jedno slovo = 16KB):

AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDDE-
FFFF----BBCCCCCCCCCCCCCCCCDDDDE-
FFFF------CCCCCCCCCCCCCCCCDDDDE-

1. 2 su slobodna fragmenta.
2. Najmanji slobodan fragment je 16KB.
3. Najveći slobodan fragment je 96KB.

4. zadatak

Postavka

Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, PMT je organizovana u dva nivoa, deskriptor stranice je 32-bitni u tabelama oba nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. Koliki prostor bi ukupno zauzimala PMT nekog procesa kada bi taj proces:

1. koristio ceo svoj virtuelni adresni prostor?
2. alocirao samo jedan logički segment veličine samo jedne stranice?

Rešenje

Adresa ima strukturu VA(32): Page1(8) Page2(12) Offset(12). PMT prvog nivoa ima $2^8$ ulaza, a PMT drugog nivoa $2^{12}$, i oba imaju ulaze veličine $2^5$ bajtova.

• $2^8 * 2^{12} * 2^5 + 2^8 * 2^5 = 2^{25} + 2^{13} = 32M + 8K$
• $2^8 * 2^5 + 2^{12} * 2^5 = 2^{13} + 2^{17} = 8K + 128K = 136K$

5. zadatak

Postavka

Umesto tehnike spooling, pristup uporednih procesa štampaču u nekom sistemu omogućuje se međusobnim isključenjem pomoću operacije rezervacije: svaki proces, pre nego što zatraži bilo koju operaciju sa štampačem, mora da ga rezerviše, a tu rezervaciju otpušta tek kada završi sa celim jednim poslom štampe. Šta je nedostatak ove tehnike?

Rešenje

Nedostatak ove tehnike je što se procesi dok čekaju na štampač blokiraju, a za to vreme su mogli da rade nešto korisnije.

6. zadatak

Postavka

Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:

• FHANDLE open(char* filename) Otvara fajl sa datim imenom.
• void close(FHANDLE) Zatvara dati fajl.
• int size(FHANDLE) Vraća trenutnu veličinu sadržaja fajla u znakovima.
• void append(FHANDLE, int) Proširuje sadržaj fajla za dati broj znakova na kraju.
• void seek(FHANDLE, int) Postavlja kurzor datog fajla na datu poziciju (redni broj znaka počev od 0).
• void write(FHANDLE, char*) Na poziciju kurzora datog fajla upisuje dati niz znakova, ne uključujući završni znak ‘\0’, i pomera kurzor iza upisanog niza znakova.

Napisati program koji na kraj postojećeg fajla sa imenom proba.txt upisuje sve što je uneseno preko standardnog ulaza, sve dok se na ulazu ne unese znak ’X’. Zanemariti sve potencijalne greške u ulazu/izlazu.

Rešenje

int main(void) {
    FHANDLE file = open("proba.txt");
    seek(file, size(file));
    char buf[2];
    buf[1] = '\0';
    while (true) {
        buf[0] = getchar();
        if (buf[0] == 'X') {
            break;
        }
        append(file, 1);
        write(file, buf);
    }
    close(file);
    return 0;
}

7. zadatak

Postavka

Koliko pristupa blokovima na disku treba izvršiti za pristup n-tom logičkom bloku sadržaja fajla ako je alokacija fajla

1. FAT, pri čemu je FAT uvek inicijalno učitana u memoriju prilikom montiranja fajl sistema,
2. indeksna, pri čemu je ceo indeks fajla u jednom bloku, a broj tog bloka zapisan je u FCB koji je učitan prilikom otvaranja fajla?

Rešenje

1. 1, jer je FAT već u memoriji pa se samo treba pristupiti bloku koji je tražen.
2. 2, jedan da se pročita blok sa indeksom i jedan da se pristupi bloku koji je tražen.