ОС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

1 + 2^N - 1 = 2^3 = 8

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 myThead : public Thread {
public:
	myThead(int val) {
		this->val = val;
		start();
	}
protected:
	void run() {
		if(val & 1) {
			new myThead(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
2. Višestruko definisan simbol - tokom prvog prolaza

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. Остала су два слободна фрагмента
2. Најмањи је величине 8KB
3. Највећи је величине 48КВ

Скица решења, једна цртица = 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

Страница од 4KB нам захтева 12 бита за померај, 8 бита за страницу првог нивоа и остатак битова за страницу другог нивоа
VA(32):8,12,12

Уколико процес користи све странице, потребна му је страница првог нивоа и све странице другог нивоа, улаз у обе је по 32b,тј 4В

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>

// Исписује "Hello world!".
int main(void) {
    FILE f = open("proba.txt");
    char a;
    int size = size(f);
    while(1){
        cin >> a;
        if(a=='X')break;
        
        append(f,2);                  //проширивање фајла, 1 за слово и 1 јер се курзор помера на место после уписаног знака
        seek(f,size);           
        write(f,&a);
        
        size+=2;                      //ажурирање тренутне величине фајла
    }
    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. n
2. 2