ОС1/Јануар 2012
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
- Nedefinisan simbol - nakon drugog prolaza, jer tek tad zna koji su svi definisani i traženi simboli
- 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:
- Koliko je ukupno slobodnih fragmenata?
- Kolika je veličina najmanjeg slobodnog fragmenta?
- Kolika je veličina najvećeg slobodnog fragmenta?
Rešenje
- Ostala su dva slobodna fragmenta
- Najmanji je veličine 8KB
- 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:
- Proces koristio ceo svoj virtuelni adresni prostor?
- 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.
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:
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
#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:
- FAT, pri čemu je FAT uvek inicijalno učitana u memoriju prilikom montiranja fajl sistema
- indeksna, pri čemu je ceo indeks fajla u jednom bloku?
Rešenje
- 1
- 2