ОС1/Јануар 2012

Zadaci na stranici predmeta.

1. zadatak

Postavka

Ukratko objasniti osnovni motiv uvođenja multiprogramiranja u računarske sisteme.

Rešenje

Multiprogramiranje se uvodi kako bi se izvršavalo više poslova uporedo. Dok jedan proces čeka na završetak I/O operacije, procesor može da izvršava i opslužuje neki drugi proces.

2. 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

		LD R1, blockAddr
		LD R2, cnt
		ST [ctrl], #00..01
wait:	LD R0, [status]
		AND R0, #1
		JZ wait
		
		LD R0, [R1]
		ST [data], R0
		INC R1
		DEC R2
		JNZ wait
		ST [ctrl], #0
		HALT

3. zadatak

Postavka

Ukoliko su svi sistemski pozivi izvršeni uspešno, koliko procesa se ukupno kreira kada se nad sledećim programom kreira jedan proces (računajući i taj jedan)?

void main () {
  for (int i=0; i<3; i++) fork();
}

Rešenje

Petlja ima tri iteracije. U prvoj iteraciji, prvi kreirani proces će pozvati fork() i od tada postoje dva procesa. Oba procesa izvršavaju svoju drugu iteraciju i od tada postoje četiri procesa, a nakon što ta četiri procesa izvrše svoju treću iteraciju postoji 8 procesa.

4. 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 parnim celobrojnim parametrom, a u suprotnom se samo završava.

Rešenje

class MyThread : public Thread {
public:
    MyThread(int val) : val(val) {
        start();
    }
protected:
    void run() {
        if (val & 1) {
            new MyThread(val + 1);
        }
    }
private: 
    int val;
};

5. zadatak

Postavka

Kada najranije linker može prijaviti grešku tipa nedefinisanog simbola, a kada višestruko definisanog simbola (tokom prvog prolaza, nakon prvog prolaza, tokom drugog prolaza, ili nakon drugog prolaza)?

Rešenje

1. Nedefinisan simbol - nakon drugog prolaza, jer tek tad zna koji su svi definisani i traženi simboli
2. Višestruko definisan simbol - tokom prvog prolaza, jer ako je već ranije naišao na definiciju zna da treba da baci grešku

6. zadatak

Postavka

U nekom sistemu primenjuje se best-fit algoritam kontinualne alokacije memorije. Inicijalno je prostor veličine 256KB 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)

A64, B16, C128, D32, A-, E8, F32, 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

1. Ostala su dva slobodna fragmenta
2. Najmanji je veličine 8KB
3. Najveći je veličine 48КВ

Skica rešenja, jedna crtica = 8KB

--------------------------------
AAAAAAAA------------------------
AAAAAAAABB----------------------
AAAAAAAABBCCCCCCCCCCCCCCCC------
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDDE-
FFFF----BBCCCCCCCCCCCCCCCCDDDDE-
FFFF------CCCCCCCCCCCCCCCCDDDDE-

7. zadatak

Postavka

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

1. Proces koristio ceo svoj virtuelni adresni prostor?
2. Proces koristio samo jednu stranicu?

Rešenje

Stranica od 4KB nam zahteva 12 bita za pomeraj, 8 bita za stranicu prvog nivoa i ostatak bitova za stranicu drugog nivoa: VA(32): 8, 12, 12

Ukoliko proces koristi sve stranice, potrebna mu je stranica prvog nivoa i sve stranice drugog nivoa, ulaz u obe je po 32b, tj. 4B.

1. $2^8 \cdot 4B + 2^8 \cdot 2^{12} \cdot 4B = 2^{10}B + 2^{22} = 1KB + 4MB$
2. $2^8 \cdot 4B + 2^{12} \cdot 4B = 2^{10}B + 2^{16} = 65KB$

8. 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

Pošto operacije sa štampačem traju prilično dugo, primenom opisane tehnike rezervacije, proces može vrlo dugo da zauzima štampač zbog čega će se ostali procesi suspendovati. Ovo je veoma loše jer se gubi konkurentnost.

9. zadatak

Postavka

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

1. FHANDLE open(char* filename) Otvara fajl sa datim imenom.
2. void close(FHANDLE) Zatvara dati fajl.
3. int size(FHANDLE) Vraća trenutnu veličinu sadržaja fajla u znakovima.
4. void append(FHANDLE, int) Proširuje sadržaj fajla za dati broj znakova na kraju.
5. void seek(FHANDLE, int) Postavlja kurzor datog fajla na datu poziciju (redni broj znaka počev od 0).
6. 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

#include <stdio.h>

int main(void) {
    FILE f = open("proba.txt");
    char a;
    int size = size(f);
    while (1) {
        scanf("%c", &a);
        if (a == 'X') {
            break;
        }
        append(f, 2); // proširivanje fajla, 1 za slovo i 1 jer se kurzor pomera na mesto posle upisanog znaka
        seek(f, size);
        write(f, &a);
        size += 2;    // ažuriranje trenutne veličine fajla
    }
    return 0;
}

10. 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?

Rešenje

1. 1
2. 2