Zadatak 1. (Broj bodova: 20)
Neka je barijera sljedeći sinkronizacijski princip. Kada neki proces dođe na barijeru, ostaje blokiran dok svi ostali procesi ne dođu na barijeru nakon čega svi procesi nastavljaju svoj rad. Napišite program sa nekoliko procesa koji simulira barijere na način da računa određeni dio matrice (odaberite sami što računati i kako, ali da bude smisleno). Nakon svih izračunatih dijelova svaki proces nastavlja svoj rad sa dijelom matrice i obavlja neki novi postupak itd..
Zadatak 2. (Broj bodova: 35)
Služba za korisnike neke tvrtke ima M 'pospanih' zaposlenika koji odgovaraju na pozive korisnika te telefonsku centralu koja na čekanju može držati N poziva. Ako nemaju posla zaposlenici drijemaju na radnom mjestu dok ih telefonski poziv ne probudi. Riješite problem sinkronizacije za korisnike, zaposlenike i telefonsku centralu na način da su pozivi korisnika ravnomjerno raspoređeni na djelatnike. U slučaju da nema slobodnog djelatnika, a manje od N poziva je u listi čekanja poziv se stavlja na čekanje, a ako je već N poziva na čekanju poziv se odbija. Pozivi se mogu događati u isto vrijeme. Program treba imati mogućnost ako mu se pošalje signal SIGUSR1 da ispiše trenutno stanje (npr. koliko je koji djelatnik puta odgovarao na pitanje i sl.).
Signal SIGINT treba uhvatiti, izbrisati sve alocirane resurse i završiti program uz prigodni izvještaj.
Zadatak 3. (Broj bodova: 25)
Napišite potrebne funkcije koje bi unutar jednog procesa omogućile više alarma na sastavu (sukcesivne pozive alarm poziva). Također napisati funkciju koja bi poništila listu trenutnih alarma. Napisati test primjer sa opcijama: a) kreiraj novi alarm za određeni broj sekundi b)ispiši listu alarma koji se trebaju pojaviti. te prilikom svake pojave alarma ispisati određenu poruku.
Zadatak 4. (Broj bodova: 20)
Napišite program koji korisniku omogućuje sljedeći meni: a) pokrenuti proces (neki unaprijed definirani koji npr. svake 3 sekunde ispisuje svoj pid) , b) ispisati listu aktivnih procesa zajedno sa opširnim podacima (npr. groupid, parentid, userid i sl) c) poslati signal određenom procesu za kraj izvršavanja d) završiti sve programe.
Zadatak 5. (Broj bodova: 20)
Napišite program koji demonstrira korištenje zajedničke memorije po Posix standardu. (Program može npr. radili slične stvari kao neki od programa koji rade sa System V zajedničkom memorijom).
Zadatak 6. (Broj bodova: 20)
Napišite funkcije koje bi omogućavale realiziranje primjera (vidi ispit 18.2.2002) sa negativnim vrijednostima semafora. (Uputa: Koristiti System V semafore i postaviti određenu vrijednost kao logičku nulu.)
Zadatak 7. (Broj bodova: 30)
Pomoću mutexa i uvjetnih varijabli implementirajte princip monitora na način da su u strukturi monitor dani pokazivači na monitorske funkcije insert i remove te napišite test primjer na problemu potrošača i proizvođača.
struct monitor{
int[] items;
... sve potrebne interne varijable ...
void (*produce)(int);
int (*consume)();
}
Zadatak 8. (Broj bodova: 20)
Implementirajte problem reader/writer (favorizirajući writera) sa vježbi.
Dozvoljene varijante: pomoću procesa, pomoću dretvi, C (Unix ili WinAPI) ili Java
Zadatak 9. (Broj bodova: 20)
Napišite program koji rješava problem kanibala i misionara opisan na vježbama ako je pokrenuto 5 cikličkih dretvi sa kanibalima i 5 cikličkih dretvi sa misionarima. Koristiti uvjetne varijable!
Zadatak 10. (Broj bodova: 20)
Riješite problem kanibala i misionara pomoću monitora u Javi.
Zadatak 11. (Broj bodova: 25)
Napišite program sa više procesa koji stvaraju zajedničku vezanu listu unutar zajedničke memorije. Obratiti pažnju što treba biti pokazivač na sljedeći element u listi. Dodavanje u vezanu listu je kritični odsječak pa ga treba pravilno zaštititi.
Zadatak 12. (Broj bodova: 20)
Implementirajte problem reader/writer favorizirajući readera.
Zadatak 13. (Broj bodova: 35)
Djed Mraz spava u svojoj kući na Sjevernom polu i može biti probuđen ako mu se vrati svih 9 sobova sa njihovog odmora (preciznije posljednji budi Djeda Mraza), ili od strane nekoliko patuljaka koji imaju poteškoća prilikom izrade igračaka. Ako samo jedan patuljak ima problem, to nije toliko ozbiljno da bi probudio Djeda Mraza, pa zato patuljci posjećuju Djeda Mraza u grupama po 3. Dok se jedna grupa patuljaka u isto vrijeme može ići Djeda Mrazu, ostale moraju čekati dok se ta grupa ne vrati. Ako se Djed Mraz probudi i ispred vrata vidi grupu patuljak i sve sobove, onda će smatrati da je došlo vrijeme za razvoženje poklona te da patuljci mogu čekati dok ne obavi zadatak. Nakon razvoženja poklona dat će svojim sobovima godišnji odmor. Općenito,nakon što patuljcima riješi problem Djed Mraz nastavi spavati.
Napišite program koji simulira gornje radnje pazeći na specifičnosti svakog od likova. Ispis programa mora biti detaljan.
Zadatak 14. (Broj bodova: 30)
Napišite program koji simulira bankarev algoritam. Unutar datoteke podaci_resursi.txt trebaju biti zadani potrebni podaci (u nekom određenom formatu). Glavni proces treba pokrenuti n procesa (zapisano u podaci_resursi.txt) koji će u slučajnim vremenskim razmacima zahtjevati određeni resurs. Glavni program treba prihvatiti takav zahtjev i odobriti ga ili odbiti ga usljed čega bi proces koji je zatražio resurs čekao dok mu zahtjev ne bude odobren. Glavni proces prije pokretanja procesa treba provjeriti da li je početno stanja sigurno stanje. Ako nije završiti svoje izvršavanje. Program završava kada svi procesi dobiju sve tražene resurse, izvrše neki zadatak i otpuste resurse.
Zadatak 15. (Broj bodova: 30)
Restoran na jezeru je sa ostatkom svijeta povezan putem jedne uske ceste na kojoj se ne mogu mimoići 2 automobila. U taj restoran dolaze ljudi sa osobnim automobilima, putnici u autobusima i vozači kamiona te se zadržavaju neko vrijeme. Za to vrijeme njihova vozila su parkirana ispred restorana. Problem je u tome što restoran ima ograničen kapacitet prostora za vozila i to u iznosu od 12 parkirnih jedinica. Osobni automobil zauzima jedno mjesto, autobus 2, i kamion 3 mjesta. (Npr. jedna od dozvoljenih kombinacija je 3 autobusa, jedan kamion i 3 osobna automobila i sl.) Riješite problem sinkronizacije dolaska, zadržavanja i odlaska iz restorana.
Napomena: Možemo smatrati da su vozila u svakom trenutku optimalno razmještena na parkiralištu, tako da problem parkirališne "fragmentacije" ne postoji, te da na cesti sa koje se skreće u restoran postoji mali display na kojem je prikazan trenutni broj slobodnih mjesta na parkiralištu
Zadatak 16. (Broj bodova: 20)
Napišite program koji kreira dva procesa, koja rade sljedeće:
Prvi proces čita sa standardnog ulaza cijele brojeve i upisuje ih u zajedničku memoriju. Proces prestaje raditi kad se unese negativni broj ili ako se popuni prethodno alocirani zajednički segment memorije. Na kraju završetka rada proces u zajednički segment upiše broj -1 kao znak za kraj. Drugi proces istovremeno čita iz zajedničkog segmenta te ispisuje u neku datoteku unešene brojeve. Na kraju rada ovih dvaju procesa glavni program mora ispisati sve unešene brojeve na standardni izlaz. Uputa : (Prilikom upisivanje svakog broja u zajednički segment, povećati vrijednost još jedne zajedničke varijable za 1, na osnovu čije promjene će drugi proces znati da treba ispisati unešeni broj).
Pitanje: Da li program (onako kako je dano sa uputom pati od race condition)? Objasnite odgovor.
Zadatak 17. (Broj bodova: 20)
Napisati program koji će sa tipkovnice učitati broj n, a zatim pokrenuti n procesa predavši im određene (potrebne) parametre. Svaki od procesa će na osnovu predanih parametara pronaći odgovarajuće elemente matrice A i B koji se nalaze u datoteci mat.txt i izračunati odgovarajuće elemente matrice A*B i zapisati ih u mat.txt. Zapisivanje u datoteku mat.txt se događa čim se izračuna pojedini element pa taj dio treba zaštiti pomoću semafora.
Zadatak 18. (Broj bodova: 20)
Koristeći funkciju clock_t times(struct tms *buf); iz zaglavlja <sys/times.h> i naredbu sistem napišite program koji kao argument iz komadne linije prima neku određenu naredbu i zatim je pomoću system izvršava.Program također treba ispisati vrijeme izvršavanja te naredbe i to ispisujući user cpu time i system cpu time
Zadatak 19. (Broj bodova: 25)
Implementirajte problem iz 3. zadataka sa kolokvija od 9.12.2002 (problem sinknonizacije robota u laboratoriju)
Zadatak 20. (Broj bodova: 40)
Na konferenciji svih filozofa svemira okupilo se N filozofa iz različitih rasa. Životni ciklus tokom konferencije bio je jesti-misliti. Za razliku od poznatog slučaja 5 filozofa, ovdje štapići stoje na sredini stola, ali zato u nekim rasama filozofi imaju više od dvije ruke (a da bi jeli u svakoj moraju držati štapić). Riješite problem sinkronizacije, ako je zadana datoteka sa podacima o filozofima i štapićima (datoteka u prvom retku sadrži broj štapića i broj filozofa, a zatim u svakom sljedećem broj ruku pojedinog filozofa)
Zadatak 21. (Broj bodova: 25)
Napišite program koji simulira bankarev algoritam. Program treba iz prve datoteke pročitati trenutne matrice, a u drugoj se nalazi određeni zahtjev. Program u neku treću datoteku spremiti novo stanje, ako se ispunjavanjem zahtjeva dolazi u sigurno stanje, ili na ekran ispisati poruku o grešci a u datoteku pospremiti staro stanje.
Zadatak 22. (Broj bodova: 20)
Napišite program koji za određeni ulazni niz zahtjeva za stranicama (npr. sa standarnog ulaza ili iz datoteke) i podatak o broju okvira ispisuje koliko promašaju imaju algoritmi LRU, FIFOi OPT. Napomena: Kod LRU algoritma pamtiti npr. zadnjih 10 korištenih stranica (ne cijelu povijest).
Zadatak 23. (Broj bodova: 25)
Napišite program kao u zadatku 4, ali tako da prilikom odabira opcija koristite nekanonski način. (tj. za opciju 3 ne treba stisnuti 3 pa enter, već samo 3 :uputa vidi 9. vježbe)
Zadatak 24. (Broj bodova: 25)
Napišite program koji simulira Multilevel Feedback Queueing način raspoređivanja sa 2 razine prioriteta. Unutar program treba postojati proces koji kreirati zadatke u slučajnim vremenskim intervalima (i također sa slučajnim odabirom vremena trajanja pojedinog zadatka). Program svake sekunde (ili nekom drugom prikladnom vremenskom intervalu) ispisivati sljedeća stanje: aktivni zadatak, popis završenih zadataka, popis zadataka u svakom od nivoa, zajedno sa njihovim ukupnim trajanjem i njihovim preostalim trajanjem
Zadatak 25. (Broj bodova: 30)
Pretpostavimo da na nekom kolegiju studenti žele elekrtonički slati nastavnom osoblju pitanja. Potrebno je napisati program koji će uz određena ograničenja uspješno simulirati sljedeće stvari: Određeni broj studenata (S) treba moći pisati poruke i slati ih u zajendički sandučić fiksne veličine (Q) . S druge strane dani broj nastavnika (T) odgovara na pitanja i briše ona na koja odgovori. Nažalost studenti imaju puno pitanja i svaki student proizvede fiksni broj poruka (M) td. vrijedi da je S*M>Q zbog čega student mora čekati dok se pretinac ne isprazni toliko da može primiti njegovu poruku.
U pojedinom trenutku samo jedna osoba može mijenjati sadržaj sandučića.
Svaki od studenata i nastavnika treba biti predstavljen svojom dretvo koja treba ispisati poruku u trenutcima kada proizvede poruku, kada je šalje, odnosno kad odgovori i kad briše poruku. Za sveku od ovih akcija, postaviti određeno čekanje (sleep random time) i ispis prije i poslije tog sleepa.
Zadatak 26. (Broj bodova: 30)
Napišite client-server aplikacije koja radi sljedeće. Server S1 radi na računalu R1 na portu P1, a server S2 na računalu R2 na portu P2. Server S1 može maksimalno primiti 10 konekcija i treba raditi sljedeće: Input svakog klijenta treba proslijediti serveru S2,a odgovor servera S2 proslijediti danom klijentu.
Zadatak 27. (Broj bodova: 20)
Napišite program koji će imati sljedeće opcije:
1 – izlistaj sadržaj trenutnog direktorija (+ ukupna veličina)
2 – izlistaj sadržaj svih poddirektorija krenuvši od trenutnog (+ ukupna veličina)
3 – ispiši trenutni direktorij
4 – promijeni direktorij u određeni direktorij.
5 – kraj
koristiti funkcije readdir, opendir ...
Zadatak 28. (Broj bodova: 30)
Napišite client-server aplikaciju koja neće za obradu svakog od klijenata imati posebnu dretvu već će njihov input čekati i uzimati koristeći funkciju select.