SI Wiki - Кориснички доприноси [sr]

Мултипроцесорски системи/К1 2020

2022-11-01T19:05:35Z

Дејан Ковачевић: broj -> veličina

{{tocright}}
'''Prvi kolokvijum 2020. godine''' održan je 3. novembra i trajao je 105 minuta. Postavka roka je dostupna sa [http://mups.etf.bg.ac.rs/ispiti/2020-2021/si4mps_k1_20202021.pdf stranice predmeta.]

== 1. zadatak ==
=== Postavka ===
Objasniti promenu principa projektovanja procesora koji favorizuju paralelno procesiranje.

=== Rešenje ===
Industrija je naišla na tri glavne prepreke pri povećanju kapaciteta procesora, ''power wall'' (struja je skupa, tranzistori su jeftini), ''memory wall'' (operacije sa memorijom su mnogo skuplje od operacija procesora) i ''ILP wall'' (dobici od paralelizma na nivou instrukcija su sve manji). Tu je uočena potreba da se ide ka slabijim višejezgarnim procesorima umesto jačim jednojezgarnim, pošto performanse procesora napreduju mnogo sporije nego ranije i takt više ne može da raste toliko brzo kao ranije, dok se na paralelizaciji programa mogu dobiti mnogo veći dobici u performansama.

== 2. zadatak ==
=== Postavka ===
Šta je pretpostavka ''Gustafson''-ovog zakona? Izvesti i precizno objasniti ovaj zakon.

=== Rešenje ===
''Gustafson''-ov zakon pretpostavlja da paralelni deo programa raste sa brojem procesora. To znači da ako za procesor sa <math>p</math> jezgara uzmemo da se program izvršava <math>T_p = \alpha T + \left(1 - \alpha\right) T</math> gde je <math>\alpha</math> procenat sekvencijalnog koda u aplikaciji, onda se za procesor sa jednim jezgrom taj isti program izvršava <math>T_1 = \alpha T + \left(1 - \alpha\right) pT</math>. Ubrzanje je onda <math>S_p = \frac{T_1}{T_p} = \frac{\alpha T + \left(1 - \alpha\right) pT}{\alpha T + \left(1 - \alpha\right) T} = \frac{\alpha T + \left(1 - \alpha\right) pT}{T} = \alpha + \left(1 - \alpha\right) p</math>. Ovo znači da <math>\lim_{p \to +\infty} S_p = +\infty</math>, ali ova pretpostavka važi samo za skalabilne aplikacije.

== 3. zadatak ==
=== Postavka ===
Opisati tehnološke trendove u procesorskoj tehnologiji i njihove posledice.

=== Rešenje ===
* Trend u procesorskoj tehnologiji je bio smanjenje veličine tranzistora. Smanjenjem veličine tranzistora možemo da spakujemo više tranzistora na istu količinu mesta i na taj način pravimo jače procesore. Nažalost, smanjenjem tranzistora oni menjaju svoje elektronske karakteristike, kola u kojima se oni koriste postaju nestabilnija i postoji ograničenje do kojeg se veličina tranzistora može smanjivati.
* Trend je takođe bio povećanje takta procesora, povećavajući broj izvršenih instrukcija po sekundi. Nažalost, kako su procesori rasli tako je raslo i kašnjenje između logičkih kola, i to predstavlja problem za povećanje takta procesora, koje je poslednje decenije usporilo. Takođe se dešava sa povećavanjem takta da se veća energija disipira na tako maloj površini, pa je procesoru potrebno mnogo bolje hlađenje, i tu takođe nailazimo na ''power wall''.

== 4. zadatak ==
=== Postavka ===
Dati uporedni pregled karakteristika programskih modela zajedničke memorije i prenosa poruka. U čemu se razlikuju arhitekture i organizacije sistema koji direktno podržavau<sup>[sic]</sup> ove modele.

=== Rešenje ===
{| class="wikitable"
|+ Pregled karakteristika
! Karakteristika
! Zajednička memorija
! Prenos poruka
|-
! Pristup memoriji
| Direktan pristup istoj memoriji
| Direktan pristup svojoj memoriji, posredstvom poruka pristup tuđim memorijama
|-
! Sinhronizacija
| Moraju se koristiti odvojene strukture (kapaciteti operativnog sistema i hardvera) kako bi se pristup memoriji sinhronizovao
| Implicitna, jer razmenjuju poruke
|-
! Kopiranje podataka
| Nije potrebno, drugi imaju pristup istoj memoriji kao mi
| Potrebno, jer jedino tako drugi mogu da dobiju sadržaj naše privatne memorije
|-
! Identitet
| Procesi ne (moraju da) znaju jedan za drugog
| Procesi znaju jedan za drugog
|-
! Arhitektura i organizacija
| Složenija, postoje UMA i NUMA varijante kako bi procesori delili memoriju između sebe i potrebno je održavati koherenciju keš memorija
| Manje složena, pošto procesori eksplicitno zahtevaju jedni od drugih memoriju koja im je potrebna, ali je zato softver koji to radi složeniji
|}

== 5. zadatak ==
=== Postavka ===
Korišćenjem OpenMP tehnologije, paralelizovati funkciju u prilogu koji računa vrednost određenog integrala korišćenjem Simpsonovog 1/3 pravila. Obratiti pažnju na efikasnost i korektnost paralelizacije. Smatrati da su sve promenljive ispravno deklarisane.
<syntaxhighlight lang="c">
float simpsons(float ll, float ul, int n) {
float h = (ul - ll) / n, x[10], fx[10];
for (int i = 0; i <= n; i++) {
x[i] = ll + i * h; fx[i] = func(x[i]);
}
float res = 0;
for (int i = 0; i <= n; i++) {
if (i == 0 || i == n) res += fx[i];
else if (i % 2 != 0) res += 4 * fx[i];
else res += 2 * fx[i];
}
res = res * (h / 3);
return res;
}
</syntaxhighlight>

=== Rešenje ===
Sledeće rešenje je pisano pod uslovom da su deklaracije <code>x</code> i <code>fx</code> kao nizove od 10 brojeva simbolične i da <code>n</code> zapravo sme da bude veće 10, jer inače paralelizacija ovog programa ne bi imala nikakvog smisla.
<syntaxhighlight lang="c" highlight="3,8">
float simpsons(float ll, float ul, int n) {
float h = (ul - ll) / n, x[10], fx[10];
#pragma omp parallel for default(none) shared(x, fx, ll, ul, n, h)
for (int i = 0; i <= n; i++) {
x[i] = ll + i * h; fx[i] = func(x[i]);
}
float res = 0;
#pragma omp parallel for default(none) shared(fx) reduction(+:res)
for (int i = 0; i <= n; i++) {
if (i == 0 || i == n) res += fx[i];
else if (i % 2 != 0) res += 4 * fx[i];
else res += 2 * fx[i];
}
res = res * (h / 3);
return res;
}
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Da li i na koji način OpenMP podržava ugneždeni paralelizam? Da li je moguće u okviru paralelnog regiona pokrenuti novi paralelni region i pod kojim uslovima?

=== Rešenje ===
OpenMP podržava ugneždeni paralelizam, u smislu da je moguće ugnezditi paralelni region unutar drugog paralelnog regiona. Pri ugneždavanju će se stvoriti tim niti sa jednom niti u njemu, osim ukoliko ugneždavanje nije omogućeno korišćenjem <code>omp_set_nested(true)</code> funkcije, ili <code>OMP_NESTED</code> promenljive okruženja. Neke implementacije ne podržavaju ove metode ugneždavanja, i u njima će ugneždeni tim niti uvek imati jednu nit.

== 7. zadatak ==
=== Postavka ===
Neka se posmatra jedna aplikacija za prikupljanje i agregaciju podataka sa interneta. Aplikacija se sastoji od veb tragača (''web crawler'') koji prikuplja određene informacije na internetu, a zatim se radi obrada. Nakon merenja performansi sekvencijalne implementacije posmatrane aplikacije pri uobičajenoj upotrebi, dobijeni su sledeći rezultati: aplikacija 45% vremena provodi obavljajući ulazno-izlazne operacije (sekvencijalno prikupljanje podataka iz jednog izvora), a 55% vremena provodi u obradi podataka. Tipično vreme obrade jednog paketa podataka korišćenjem jednog jezgra je 1s.
<div class="abc-list">
# Ukoliko se aplikacija paralelizuje za izvršavanje na SMP sistemu sa 8 jezgara na 2GHz sa 32GB memorije, navesti formulu za Amdalov zakon i odrediti maksimalno moguće ubrzanje koje se može postići za zadatu aplikaciju.
# Da li i na koji način može organizovati paralelno izvršavanje sekvencijalnog dela aplikacije, ukoliko paketi sa interneta mogu nezavisno da se obrađuju? Smatrati da paketi imaju neujednačeno vreme obrade i diskutovati moguće načine paralelne obrade.
</div>

=== Rešenje ===
Formula za Amdalov zakon glasi:
* <math>T_p = \alpha T_1 + (1 - \alpha) \frac{T_1}{p}</math>
* <math>S_p = \frac{T_1}{T_P} = \frac{1}{\alpha + \frac{1 - \alpha}{p}} = \frac{p}{\alpha p + 1 - \alpha}</math>
Kako je nama ovde <math>\alpha = 0.45</math> i <math>p = 8</math> maksimalno ubrzanje koje možemo da postignemo je <math>S_p = \frac{8}{0.45 \cdot 8 + 1 - 0.45} \approx 1.93</math>.

Aplikacija može da održava osam niti, od kojih jedna nit radi primanje podataka preko interneta i kako pristižu paketi ubacuje ih u neku deljenu strukturu i nekom sinhronizacionom primitivom signalizira da ima paketa za obradu (slično ''bag of tasks'' pristupu korišćenjem programskog modela deljene memorije). Ostalih sedam niti mogu da iz ove vreće zadataka preuzimaju pakete za obradu i obrađuju ih paralelno. Bez obzira na to što paketi imaju neujednačeno vreme obrade, niti ne moraju da čekaju jedna na drugu tako da dok jedna nit obrađuje zahtevniji paket ostale niti ne zavise od nje (ne postoji ''bottleneck''). Više od osam niti verovatno neće ubrzati aplikaciju jer će svesti na klasičan ''time-sharing'' umesto paralelne obrade.

[[Категорија:Рокови]]
[[Категорија:Мултипроцесорски системи]]

Веб дизајн/К2 2022

2022-07-10T11:18:37Z

Дејан Ковачевић: додат К2 2022 из Веб дизајна

{{tocright}}
{{нерешено}}

== Поставка ==
Потребно је направити игру меморије. Треба направити квадрат 3x3 и слајдер за избор броја случајно генерисаних поља. Игра почиње тако што се генерише изабрани број случајних поља и поља се обоје у плаво (поља се боје једно по једно, и држе се обојена 1 s након чега се враћају у белу боју). Након тога треба да се изаберу та поља притиском миша. Све док се бирају добра поља она се боје у зелено, када се први пут изабере поље које није генерисано сва изабрана поља се боје у црвено и држе се тако 1 s након чега се враћају у белу боју. Треба омогућити да се након тога поново могу погађати поља. Ако се погоде сва поља треба исписати поруку да је игра завршена и омогућити да се поново могу генерисати поља.

== Решење ==

[[Категорија:Веб дизајн]]
[[Категорија:Рокови]]

Пројектовање софтвера/Фебруар 2022

2022-02-22T19:17:00Z

Дејан Ковачевић: mala ispravka u tekstu 3. zadatka

{{tocright}}
{{nerešeno}}
'''Februarski ispit 2022. godine''' održan je 22. februara. Tekst zadataka ispod je po sećanju studenata.
{{rešenja}}

== 1. zadatak ==
Povezati definicije principa OO modela sa njihovim nazivima:
<div class="abc-list" data-solution="select" data-options="tipizacija,konkurentnost,perzistencija,modularnost,hijerarhija">
# Osobina koja razlikuje aktivne objekte od pasivnih: <span class="spoiler">konkurentnost</span>
# Osobina sistema da se razlaže na skup kohezivnih i slabo spregnutih modula: <span class="spoiler">modularnost</span>
# Osobina da se objekti različitih klasa ne mogu uopšte ili mogu zamenjivati na ograničene načine: <span class="spoiler">tipizacija</span>
# Osobina po kojoj se postojanje objekta može protezati kroz vreme ili prostor: <span class="spoiler">perzistencija</span>
# Rangiranje ili uređivanje apstrakcija: <span class="spoiler">hijerarhija</span>
</div>

== 2. zadatak ==
Označiti tačne tvrdnje za dati dijagram:
[[Датотека:PS februar 2022 zadatak 2 dijagram sekvence.svg|мини|Dijagram iz drugog zadatka.]]
<div class="abc-list" data-solution="multiple">
# <span class="solution">Prikazani dijagram je dijagram sekvence.</span>
# <span class="solution">Objekat sa <code>{transient}</code> ograničenjem se stvara i uništava u toku sekvence.</span>
# Metoda <code>promptKomanda()</code> je sinhrona.
# <span class="solution">Metoda <code><<create>></code> stvara objekat tipa <code>Transakcija</code>.</span>
# Metoda <code>provera()</code> nema parametre.
</div>

== 3. zadatak ==
Koji dijagram se koristi za modeliranje izvršnih izdanja?
<div class="abc-list" data-solution="single">
# raspoređivanja
# klasa
# <span class="solution">komponenata</span>
# interakcija
# aktivnosti
</div>

== 4. zadatak ==
Kolika je multiplikativnost sa suprotne strane kvalifikatora na datom dijagramu?
[[Датотека:PS februar 2022 zadatak 4 dijagram klasa.svg|мини|Dijagram klasa iz četvrtog zadatka.]]
<div class="abc-list" data-solution="single">
# <span class="solution">*</span>
# 0..1
# 1
# 1..*
</div>

== 5. zadatak ==
Označiti tačna tvrđenja za dijagram klasa:
[[Датотека:PS februar 2022 zadatak 5 dijagram klasa.svg|мини|Dijagram klasa iz petog zadatka.]]
<div class="abc-list" data-solution="multiple">
# Objekat klase B može da preko asocijacije pristupi objektu klase A.
# <span class="solution">Metod klase A može preko asocijacije da pristupi objektima klase C.</span>
# Metod klase B može preko asocijacije da pristupi objektima klase C.
# Objekat klase A može da poziva privatne metode objekta klase C.
# Metod klase C može preko asocijacije da pristupi objektima klase A.
</div>

== 6. zadatak ==
Sa kojim projektnim uzorcima se slaže projektni uzorak Prototip:
<div class="abc-list" data-solution="multiple">
# <span class="solution">Sastav</span>
# Unikat
# Fabrički metod
# <span class="solution">Dekorater</span>
# Strategija
# Podsetnik
# ...
</div>

== 7. zadatak ==
Koju ulogu u Podsetniku ima Konkretna komanda u slučaju da se komanda koristi za poništavanje operacija (undo)?
<div class="abc-list" data-solution="single">
# Klijent
# Subjekat
# <span class="solution">Čuvar</span>
# Podsetnik
# Fabrika
</div>

== 8. zadatak ==
Označiti tačne tvrdnje za projektni uzorak Fabrički metod.
<div class="abc-list" data-solution="multiple">
# <span class="solution">Uzorak eliminiše potrebu da se klijentski kod vezuje za aplikativno-specifične klase.</span>
# <span class="solution">Apstraktna fabrika se često implementira pomoću Fabričkog metoda.</span>
# Učesnik Fabrika mora da zna za postojanje Konkretnih proizvoda.
# <span class="solution">Drugo ime za Fabrički metod je virtuelni konstruktor.</span>
# Fabrički metod je objektni uzorak kreiranja.
</div>

== 9. zadatak ==
Označiti tačne tvrdnje u vezi sa projektnim uzorkom Graditelj.
<div class="abc-list" data-solution="multiple">
# Graditelj stvara cele objekte odjednom.
# <span class="solution">Graditelj stvara objekte iz delova.</span>
# Upravljač stvara objekte Konkretnog graditelja.
# <span class="solution>Uzorak Graditelj često ima sličnu objektnu i klasnu strukturu kao Strategija.</span>
# Graditelj je objektni uzorak strukture.
</div>

== 10. zadatak ==
Označiti tačne tvrdnje u vezi sa projektnim uzorkom Zastupnik.
<div class="abc-list" data-solution="multiple">
# Virtuelni zastupnik je ambasador.
# Svaki zastupnik mora da što duže odlaže kreiranje objekta kojeg zastupa.
# <span class="solution">Zastupnik može biti implementiran kao Dekorater.</span>
# Zastupnik je klasni uzorak strukture.
# <span class="solution">Zastupnik se koristi za implementaciju copy-on-write funkcionalnosti.</span>
</div>

[[Категорија:Рокови]]
[[Категорија:Пројектовање софтвера]]

Пројектовање софтвера/Фебруар 2022

2022-02-22T19:12:58Z

Дејан Ковачевић: dodat jos jedan odgovor za 9. pitanje

{{tocright}}
{{nerešeno}}
'''Februarski ispit 2022. godine''' održan je 22. februara. Tekst zadataka ispod je po sećanju studenata.
{{rešenja}}

== 1. zadatak ==
Povezati definicije principa OO modela sa njihovim nazivima:
<div class="abc-list" data-solution="select" data-options="tipizacija,konkurentnost,perzistencija,modularnost,hijerarhija">
# Osobina koja razlikuje aktivne objekte od pasivnih: <span class="spoiler">konkurentnost</span>
# Osobina sistema da se razlaže na skup kohezivnih i slabo spregnutih modula: <span class="spoiler">modularnost</span>
# Osobina da se objekti različitih klasa ne mogu uopšte ili mogu zamenjivati na ograničene načine: <span class="spoiler">tipizacija</span>
# Osobina po kojoj se postojanje objekta može protezati kroz vreme ili prostor: <span class="spoiler">perzistencija</span>
# Rangiranje ili uređivanje apstrakcija: <span class="spoiler">hijerarhija</span>
</div>

== 2. zadatak ==
Označiti tačne tvrdnje za dati dijagram:
[[Датотека:PS februar 2022 zadatak 2 dijagram sekvence.svg|мини|Dijagram iz drugog zadatka.]]
<div class="abc-list" data-solution="multiple">
# <span class="solution">Prikazani dijagram je dijagram sekvence.</span>
# <span class="solution">Objekat sa <code>{transient}</code> ograničenjem se stvara i uništava u toku sekvence.</span>
# Metoda <code>promptKomanda()</code> je sinhrona.
# <span class="solution">Metoda <code><<create>></code> stvara objekat tipa <code>Transakcija</code>.</span>
# Metoda <code>provera()</code> nema parametre.
</div>

== 3. zadatak ==
Koji dijagram se koristi za modeliranje izvršnog okruženja?
<div class="abc-list" data-solution="single">
# raspoređivanja
# klasa
# <span class="solution">komponenata</span>
# interakcija
# aktivnosti
</div>

== 4. zadatak ==
Kolika je multiplikativnost sa suprotne strane kvalifikatora na datom dijagramu?
[[Датотека:PS februar 2022 zadatak 4 dijagram klasa.svg|мини|Dijagram klasa iz četvrtog zadatka.]]
<div class="abc-list" data-solution="single">
# <span class="solution">*</span>
# 0..1
# 1
# 1..*
</div>

== 5. zadatak ==
Označiti tačna tvrđenja za dijagram klasa:
[[Датотека:PS februar 2022 zadatak 5 dijagram klasa.svg|мини|Dijagram klasa iz petog zadatka.]]
<div class="abc-list" data-solution="multiple">
# Objekat klase B može da preko asocijacije pristupi objektu klase A.
# <span class="solution">Metod klase A može preko asocijacije da pristupi objektima klase C.</span>
# Metod klase B može preko asocijacije da pristupi objektima klase C.
# Objekat klase A može da poziva privatne metode objekta klase C.
# Metod klase C može preko asocijacije da pristupi objektima klase A.
</div>

== 6. zadatak ==
Sa kojim projektnim uzorcima se slaže projektni uzorak Prototip:
<div class="abc-list" data-solution="multiple">
# <span class="solution">Sastav</span>
# Unikat
# Fabrički metod
# <span class="solution">Dekorater</span>
# Strategija
# Podsetnik
# ...
</div>

== 7. zadatak ==
Koju ulogu u Podsetniku ima Konkretna komanda u slučaju da se komanda koristi za poništavanje operacija (undo)?
<div class="abc-list" data-solution="single">
# Klijent
# Subjekat
# <span class="solution">Čuvar</span>
# Podsetnik
# Fabrika
</div>

== 8. zadatak ==
Označiti tačne tvrdnje za projektni uzorak Fabrički metod.
<div class="abc-list" data-solution="multiple">
# <span class="solution">Uzorak eliminiše potrebu da se klijentski kod vezuje za aplikativno-specifične klase.</span>
# <span class="solution">Apstraktna fabrika se često implementira pomoću Fabričkog metoda.</span>
# Učesnik Fabrika mora da zna za postojanje Konkretnih proizvoda.
# <span class="solution">Drugo ime za Fabrički metod je virtuelni konstruktor.</span>
# Fabrički metod je objektni uzorak kreiranja.
</div>

== 9. zadatak ==
Označiti tačne tvrdnje u vezi sa projektnim uzorkom Graditelj.
<div class="abc-list" data-solution="multiple">
# Graditelj stvara cele objekte odjednom.
# <span class="solution">Graditelj stvara objekte iz delova.</span>
# Upravljač stvara objekte Konkretnog graditelja.
# <span class="solution>Uzorak Graditelj često ima sličnu objektnu i klasnu strukturu kao Strategija.</span>
# Graditelj je objektni uzorak strukture.
</div>

== 10. zadatak ==
Označiti tačne tvrdnje u vezi sa projektnim uzorkom Zastupnik.
<div class="abc-list" data-solution="multiple">
# Virtuelni zastupnik je ambasador.
# Svaki zastupnik mora da što duže odlaže kreiranje objekta kojeg zastupa.
# <span class="solution">Zastupnik može biti implementiran kao Dekorater.</span>
# Zastupnik je klasni uzorak strukture.
# <span class="solution">Zastupnik se koristi za implementaciju copy-on-write funkcionalnosti.</span>
</div>

[[Категорија:Рокови]]
[[Категорија:Пројектовање софтвера]]

Информациони системи 1/Лаб 2 2022 јануар

2022-02-03T18:58:44Z

Дејан Ковачевић: valjda se gledalo da li je tekući rok otvoren za prijavu predmeta ako ne grešim

{{tocright}}
'''Prva nadoknada druge laboratorijske vežbe 2022. godine''' održana je početkom februara 2022. godine. Baza je takođe bila identična kao prethodnih godina.

== Postavka ==
Za deo baze podataka fakulteta kreirati servis sa sledećim krajnjim tačkama:
* ''(8 poena)'' <code>POST .../prijava/{idPredmeta}</code>
** ''request body:'' prazno
** ''response body:'' prazno
** Pravo za izvršavanje ove metode ima samo student. Student može da prijavi predmet samo ukoliko prati taj predmet, za tekući rok je omogućena prijava predmeta i rok prijave predmeta je u istom semestru kao i sam predmet.
* ''(4 poena)'' <code>POST .../admin/</code>
** ''request body:'' (<code>text/xml</code>) Sve informacije su u sledećem formatu: <syntaxhighlight lang="xml">
<korisnik>
<imeKor>...</imeKor>
<sifra>...</sifra>
</korisnik>
</syntaxhighlight>
** ''response body:'' prazno
** Pravo za izvršavanje ove metode ima samo admin. Metoda kreijra novog admina sa datim informacijama.

== ER dijagram ==
: ''Baza i skripta ispod su identični kao na [[Информациони системи 1/Лаб 2 2020|drugoj laboratorijskoj vežbi 2020. godine]].''
Na slici je dat model dela baze podataka fakulteta.
[[Датотека:IS1 lab 2 2020 dijagram.svg|center|frame|Дати ЕР дијаграм базе података.]]
Status u <code>semestar</code> ima vrednosti:
* <code>N</code> — nije u toku
* <code>P</code> — omogućena nova praćenja predmeta
* <code>T</code> — u toku
Status u <code>rok</code> ima vrednosti:
* <code>N</code> — nije u toku
* <code>P</code> — omogućena prijava predmeta
* <code>T</code> — u toku

=== SQL ===
Sledeća SQL skripta pravi bazu prikazanu na dijagramu iznad zajedno sa podacima koji mogu da se koriste za testiranje.
<syntaxhighlight lang="sql">
CREATE TABLE `korisnik` (
`id` INT PRIMARY KEY AUTO_INCREMENT,
`korisnicko_ime` VARCHAR(45),
`sifra` VARCHAR(45)
);
CREATE TABLE `admin` (
`korisnik_id` INT PRIMARY KEY,
FOREIGN KEY (`korisnik_id`) REFERENCES `korisnik` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION
);
CREATE TABLE `student` (
`korisnik_id` INT PRIMARY KEY,
`indeks` VARCHAR(45),
`ime_prezime` VARCHAR(45) NOT NULL,
`godina` INT,
FOREIGN KEY (`korisnik_id`) REFERENCES `korisnik` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION
);
CREATE TABLE `nastavnik` (
`korisnik_id` INT PRIMARY KEY,
`ime_prezime` VARCHAR(45),
FOREIGN KEY (`korisnik_id`) REFERENCES `korisnik` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION
);
CREATE TABLE `semestar` (
`id` INT PRIMARY KEY AUTO_INCREMENT,
`naziv` VARCHAR(45) NOT NULL,
`status` VARCHAR(1)
);
CREATE TABLE `predmet` (
`id` INT PRIMARY KEY AUTO_INCREMENT,
`sifra` VARCHAR(45) NOT NULL,
`naziv` VARCHAR(45) NOT NULL,
`semestar_id` INT NOT NULL,
`godina` INT,
FOREIGN KEY (`semestar_id`) REFERENCES `semestar` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION
);
CREATE TABLE `predaje` (
`nastavnik_korisnik_id` INT,
`predmet_id` INT,
PRIMARY KEY (`nastavnik_korisnik_id`, `predmet_id`),
FOREIGN KEY (`nastavnik_korisnik_id`) REFERENCES `nastavnik` (`korisnik_id`)
ON DELETE CASCADE
ON UPDATE NO ACTION,
FOREIGN KEY (`predmet_id`) REFERENCES `predmet` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION
);
CREATE TABLE `prati` (
`id` INT PRIMARY KEY AUTO_INCREMENT,
`predmet_id` INT NOT NULL,
`student_korisnik_id` INT NOT NULL,
FOREIGN KEY (`predmet_id`) REFERENCES `predmet` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION,
FOREIGN KEY (`student_korisnik_id`) REFERENCES `student` (`korisnik_id`)
ON DELETE CASCADE
ON UPDATE NO ACTION
);
CREATE TABLE `rok` (
`id` INT PRIMARY KEY AUTO_INCREMENT,
`naziv` VARCHAR(45) NOT NULL,
`semestar_id` INT NOT NULL,
`status` VARCHAR(1),
FOREIGN KEY (`semestar_id`) REFERENCES `semestar` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION
);
CREATE TABLE `prijava` (
`id` INT PRIMARY KEY AUTO_INCREMENT,
`prati_id` INT NOT NULL,
`rok_id` INT NOT NULL,
FOREIGN KEY (`prati_id`) REFERENCES `prati` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION,
FOREIGN KEY (`rok_id`) REFERENCES `rok` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION
);
CREATE TABLE `ocena` (
`id` INT PRIMARY KEY AUTO_INCREMENT,
`ocena` INT,
`prijava_id` INT NOT NULL,
FOREIGN KEY (`prijava_id`) REFERENCES `prijava` (`id`)
ON DELETE CASCADE
ON UPDATE NO ACTION
);

INSERT INTO `korisnik` (`korisnicko_ime`, `sifra`) VALUES
('admin', 'admin'), -- 1
('pera', 'peric'), -- 2
('mika', 'mikic'), -- 3
('zika', 'zikic'), -- 4
('cmilos', 'cmilos'), -- 5
('tasha', 'tasha'), -- 6
('stubic', 'stubic'), -- 7
('tartalja', 'tartalja'); -- 8

INSERT INTO `admin` (`korisnik_id`) VALUES (1);

INSERT INTO `student` (`korisnik_id`, `indeks`, `ime_prezime`, `godina`) VALUES
(2, '0001', 'Pera Perić', 2019),
(3, '0002', 'Mika Mikić', 2020),
(4, '0010', 'Žika Žikić', 2018);

INSERT INTO `nastavnik` (`korisnik_id`, `ime_prezime`) VALUES
(5, 'Miloš Cvetanović'),
(6, 'Tamara Šekularac'),
(7, 'Stefan Tubić'),
(8, 'Igor Tartalja');

INSERT INTO `semestar` (`naziv`, `status`) VALUES
('Peti semestar 2019', 'N'), -- 1
('Peti semestar 2021', 'T'), -- 2
('Treći semestar 2021', 'T'), -- 3
('Drugi semestar 2022', 'P'), -- 4
('Četvrti semestar 2022', 'P'); -- 5

INSERT INTO `predmet` (`sifra`, `naziv`, `semestar_id`, `godina`) VALUES
('13S113IS1', 'Informacioni sistemi 1', 2, 2021), -- 1
('13E114IS1', 'Informacioni sistemi 1', 2, 2021), -- 2
('13S112OO1', 'Objektno orijentisano programiranje 1', 3, 2021), -- 3
('13E112OO1', 'Objektno orijentisano programiranje 1', 3, 2021), -- 4
('13S112OO2', 'Objektno orijentisano programiranje 2', 5, 2022), -- 5
('13E112OO2', 'Objektno orijentisano programiranje 2', 5, 2022); -- 6

INSERT INTO `predaje` (`nastavnik_korisnik_id`, `predmet_id`) VALUES
(8, 3),
(8, 4),
(8, 5),
(8, 6),
(5, 1),
(5, 2),
(6, 1),
(6, 2),
(7, 1),
(7, 2);

INSERT INTO `prati` (`predmet_id`, `student_korisnik_id`) VALUES
(1, 2), -- 1: Pera prati IS1
(2, 3), -- 2: Mika prati IS1
(3, 3), -- 3: Mika prati OO1
(3, 4); -- 4: Žika prati OO1

INSERT INTO `rok` (`naziv`, `semestar_id`, `status`) VALUES
('Januar', 1, 'N'), -- 1
('Januar', 2, 'T'), -- 2
('Januar', 3, 'T'), -- 3
('Februar', 2, 'P'), -- 4
('Februar', 3, 'P'); -- 5

INSERT INTO `prijava` (`prati_id`, `rok_id`) VALUES
(1, 2), -- 1: Pera prijavio IS1 za januar
(1, 4), -- 2: Pera prijavio IS1 za februar
(2, 2), -- 3: Mika prijavio IS1 za februar
(3, 5), -- 4: Mika prijavio OO1 za februar
(4, 3); -- 5: Žika prijavio OO1 za januar

INSERT INTO `ocena` (`ocena`, `prijava_id`) VALUES
(5, 1),
(10, 5);
</syntaxhighlight>

== Rešenje ==
=== <code>persistence.xml</code> ===
Definiše jedinicu perzistencije <code>mypu</code>. Pretpostavlja se postojanje resursa <code>fakultetResource</code> koji je povezan na odgovarajući Connection Pool na Glassfish.
<syntaxhighlight lang="xml">
<?xml version="1.0" encoding="UTF-8"?>
<persistence version="2.2" xmlns="http://java.sun.com/xml/ns/persistence" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://xmlns.jcp.org/xml/ns/persistence http://xmlns.jcp.org/xml/ns/persistence/persistence_2_2.xsd">
<persistence-unit name="mypu" transaction-type="JTA">
<jta-data-source>fakultetResource</jta-data-source>
<exclude-unlisted-classes>false</exclude-unlisted-classes>
</persistence-unit>
</persistence>
</syntaxhighlight>

=== <code>models</code> paket ===
Ovde su generisane klase entiteta iz baze priložene iznad sa podrazumevanim podešavanjima.

=== <code>filters</code> paket ===
==== <code>BasicAuthFilter.java</code> ====
{{делимично решено}}

=== <code>resources</code> paket ===
{{делимично решено}}

[[Категорија:Информациони системи 1]]
[[Категорија:Лабораторијске вежбе]]

ОРТ2

2021-10-05T15:47:37Z

Дејан Ковачевић: prepisan rok

{{tocright}}
'''Основи рачунарске технике 2''' је обавезан предмет у трећем семестру.

== Странице ==
* [https://rti.etf.bg.ac.rs/rti/ir2ort2/ Страница предмета]
* [https://elearning.rcub.bg.ac.rs/moodle/course/view.php?id=604 ''Moodle'' курс]

== Корисне везе ==
{{Материјали
| vuk = 1-4dW6LftaVw6CtwuuXwUEVrnrH9TgfER
| box = 8374329465
}}
* [https://sourceforge.net/projects/circuit/ ''Logisim''] — Симулатор дигиталне логике који се користи при изради пројекта, као и за решења рокова на викију.
* ''[[github:reds-heig/logisim-evolution|Logisim-evolution]]'' — Унапређена верзија ''Logisim''
* [https://mega.nz/folder/As1A1TZY#z-SnQ4VsucNAwTLQgZjFug Рокови и решења (РТИ)]

== Пројекат ==
Пројекат се од 2020/21. године ради на ''Logisim'' симулатору дигиталне логике. У одељку [[#Корисне везе|Корисне везе]] изнад доступне су везе за преузимање ''Logisim'' и ''Logisim-evolution'' симулатора, а потребне су и ЕТФ библиотеке са компонентама које су доступне за:
* Стари ''Logisim'', на страници предмета под одељком "Пројекат"
* [[Медиј:ORT2 ETF-evolution.circ|''Logisim-evolution'']] - препоручује се именовање преузете датотеке као <code>ETF-evolution.circ</code>
Ове библиотеке је најбоље поставити у исти директоријум као шеме које преузимате са викија, али ће вас ''Logisim'' свакако питати да изаберете путању до ових библиотека уколико то не урадите.

За пројекат школске 2020/21. године је доступан [[ОРТ2/Пројекат 2021|водич]], а могуће је да ће и следећих година информације из њега остати релевантне.

== Испитни рокови ==
=== Колоквијум 1 ===
{{#dpl:
| titleregexp = ОРТ2/К1
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]],,
}}

=== Колоквијум 2 ===
{{#dpl:
| titleregexp = ОРТ2/К2
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]],,
}}

=== Колоквијум 3 ===
{{#dpl:
| titleregexp = ОРТ2/К3
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]],,
}}

=== Испит ===
{{#dpl:
| titleregexp = ОРТ2/Јануар
| titleregexp = ОРТ2/Фебруар
| titleregexp = ОРТ2/Јул
| titleregexp = ОРТ2/Август
| titleregexp = ОРТ2/Септембар
| titleregexp = ОРТ2/Октобар
| noresultsheader = Тренутно нема решених рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦6¦-1}²]],,
}}

== Лаб вежбе ==
На предмету се одржавају две лабораторијске вежбе од којих свака носи по 5 бодова. Лабораторијска вежба почиње улазним тестом на ''Moodle'' платформи од 10 минута и 3 питања, за који се примери могу наћи на страници предмета у одељку "Лабораторијске вежбе" (питалице су истог облика као на лабораторијској вежби). После улазног теста се прелази на рад у симулатору и за тај део се пишу одговори на задата питања у вези са задатим програмом у документу који се на крају вежбе предаје на мрежни диск. Током лабораторијске вежбе демонстратор такође испитује студента за 3 бода. Уколико је студент на улазном тесту освојио 2 бода, на бодове демонстратора се додаје 1 бод, а уколико је освојио 3 бода, на бодове демонстратора се додају 2 бода. Ако је студент освојио 0 или 1 бод на улазном тесту, не наставља с радом лабораторијске вежбе и добија 0 бодова. Збир бодова са улазног теста и од демонстратора се скалира са процентом урађености дела лабораторијске вежбе са симулатором, и тако се израчунавају коначни бодови на тој лабораторијској вежби.

Укратко:
* <math>T</math> — Бодови освојени на улазном тесту (од 0 до 3)
* <math>D</math> — Бодови освојени од демонстратора (од 0 до 3)
* <math>S</math> — Проценат урађености дела лабораторијске вежбе са симулатором (од 0 до 1)
* Коначна оцена: <math>\left\{\begin{array}{ll} 0 & T < 2 \\ (T - 1 + D) \cdot S & T \geq 2 \end{array}\right.</math>

== Начин оцењивања ==
* '''K1''', '''K2''' — Бодови са првог и другог колоквијума, носе по 20 бодова.
* '''L1''', '''L2''' — Бодови са лабораторијских вежби, носе по 5 бодова.
* '''I''' — Испитни део, носи 20 бодова.
* '''Pr''' — Носи 30 бодова.
* '''P''' — Коначан број бодова: <math>P = K_1 + K_2 + I + L_1 + L_2 + Pr</math>.
{| class="wikitable"
! Бодови
| <math>P \leq 50</math> || <math>50 < P \leq 60</math> || <math>60 < P \leq 70</math> || <math>70 < P \leq 80</math> || <math>80 < P \leq 90</math> || <math>90 < P</math>
|-
! Оцена
| 5 || 6 || 7 || 8 || 9 || 10
|}

== Потребна помоћ ==
* {{zadaci|postavke}}
* {{zadaci|rešenja}}
*: Рокови који су преписани а нису решени су: {{rokovi|нерешени}}
*: Рокови којима недостаје понеко решење су: {{rokovi|делимично решени}}
*: Од решења лошијег квалитета које би требало преписати на вики доступан је [https://cdn.discordapp.com/attachments/693906682228506634/774674602785767424/ORT2_KLK1_2018.zip К1 2018.]
* Пошто су задаци за први колоквијум обично шаблонски, али је први колоквијум обично најтежи, од користи би био водич за решавање првог колоквијума.

[[Категорија:Трећи семестар]]
[[Категорија:Обавезни предмети]]
[[Категорија:ОРТ2]]

ОРТ2/К3 Август 2021

2021-09-30T18:09:58Z

Дејан Ковачевић: dodat sadrzaj

{{tocright}}

== Поставка ==
Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција. Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налаѕи на вишој, а млађи на нижој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар података меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 3 бајта, акумулатор А дужине 2 бајта, прихватни регистар података B дужине 2 бајта, регистри опште намене R0 до R3 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Програмска статусна реч PSW садржи битове N, Z, C и V који се ажурирају приликом рада процесора. Инструкције су дужине 1, 2 или 3 бајта.

Битови 7, 6 и 5 првог бајта инструкције су 000 за све инструкције скока. Код инструкција условног скока бит 4 првог бајта инструкције је 0, док код инструкција безусловног скока бит 4 првог бајта инструкције је 1. Инструкција условног скока је инструкција условног скока уколико је резултат већи (BGRT - ''not((PSWN xor PSWV) or PSWZ)'') и инструкције безусловног скока су инструкција безусловног скока (JMP) и инструкција скока на потпрограм (JSR). Битовима 3 до 0 првог бајта инструкције специфира се код инструкције и на освову тога су за инструкције BGRT, JMP и JSR усвојени кодови операције 00000000, 00010000 и 00010001, респективно. Инструкције JMP и JSR се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта. Инструкција BGRT се реализује као релативни скок у односу на текућу вредност програмског бројача PC, а померај је 8-битна целобројна величина са знаком дата другим бајтом инструкције. Дужина инструкције је 2 бајта.

Битови 7, 6 и 5 првог бајта инструкције су 001 за све безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и инструкција декрементирања акумулатора (DEC). Битовима 4 до 0 првог бајта инструкције специфира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и DEC усвојени кодови операција 00100000, 00100001 и 00100010, респективно. Дужина инструкција је 1 бајт.

Битови 7, 6 и 5 првог бајта инструкције имају вредности од 010 до 111 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), инструкција аритметичког померања удесно за једно место (ASR), инструкција упоређивања акумулатора са операндом (CMP), инструкција сабирања (ADD) и инструкција одузимања (SUB). На основу тога су за инструкције LD, ST, ASR, CMP, ADD и SUB усвојени кодови операција 010, 011, 100, 101, 110 и 111, респективно. Дужина инструкција је 2 или 3 бајта и зависи од специфичног начина адресирања.

Начини адресирања су специфирани битовима 4, 3 и 2 првог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-меморијско индиректно адресирање (memind), 010-регистарско директно адресирање (regdir), 011-регистарско инсиректно адресирање (regind), 100-релативно адресирање са померајем (pcrel), 101-непосредно адресирање (immed) и 110-регистарско индиректно адресирање са преинкрементирањем (preincr). Код меморијског директног и меморијског индиректног адресирања 16-битна адреса меморијске локације је дата другим и трећим бајтом инструкције. Битови 1 и 0 првог бајта инструкције се не користе. Дужина инструкције је 3 бајта. Регистарско директно, регистарско индиректно и регистарско индиректно адресирање са преинкрементирањем користе неке од регистара опште намене R0 до R3 специфиране битовима 1 и 0 првог бајта. Дужина инструкција је 1 бајт. Код релативног адресирања са померајем други бајт инструкције садржи 8-битни померај који је дат као целобројна величина са знаком. Битови 1 и 0 првог бајта инструкције се не користе. Дужина инструкција је 2 бајта. Код непосредног адресирања 16-битни операнд дат је другим и трећим бајтом инструкције. Битови 1 и 0 првог бајта инструкције се не користе. Дужина инструкција је 3 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на прву слободну меморијску локацију. Процесор нема могућност обраде прекида.

<div class="abc-list">
#Пројектовати део операционе јединице процесора (фазе: FETCH, ADDR и EXEC) која је потребна да се изврши инструкција '''CMP (PC)pom'''. Померај '''pom''' је целобројна величина са знаком који је дат другим бајтом инструкције. Цртати само неопходне компоненте које су потребне за извршавање наведене инструкције.
#Дати су почетни садржаји регистара и индикатора: PC = 1000h, SP = 2000h, ACC = 0010h, R0 = 0000h, R1 = 0001h, R2 = 0002h, R3 = 0003h, N = 0, Z = 0, V = 0 и C = 0. Индикатори статусне речи на које инструкција не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистара IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одрђивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора А и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>

== Решење ==
{{delimično rešeno}}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОРТ2/К3 Август 2021

2021-09-30T18:00:34Z

Дејан Ковачевић: Нова страница: == Поставка == Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета…

== Поставка ==
Посматра се део рачунара који чине меморија и процесор. Меморија је капацитета 2<sup>16</sup> бајтова. Ширина меморијске речи је 1 бајт. Процесор је са једноадресним форматом инструкција. Адресе и подаци су дужине 16 бита и заузимају по две суседне меморијске локације, при чему се старији бајт налаѕи на вишој, а млађи на нижој адреси.

У процесору постоји регистар програмског бројача PC дужине 2 бајта, адресни регистар меморије MAR дужине 2 бајта, прихватни регистар података меморије MDR дужине 1 бајт, прихватни регистар инструкције IR дужине 3 бајта, акумулатор А дужине 2 бајта, прихватни регистар података B дужине 2 бајта, регистри опште намене R0 до R3 дужине 2 бајта, програмска статусна реч PSW дужине 1 бајт. Програмска статусна реч PSW садржи битове N, Z, C и V који се ажурирају приликом рада процесора. Инструкције су дужине 1, 2 или 3 бајта.

Битови 7, 6 и 5 првог бајта инструкције су 000 за све инструкције скока. Код инструкција условног скока бит 4 првог бајта инструкције је 0, док код инструкција безусловног скока бит 4 првог бајта инструкције је 1. Инструкција условног скока је инструкција условног скока уколико је резултат већи (BGRT - ''not((PSWN xor PSWV) or PSWZ)'') и инструкције безусловног скока су инструкција безусловног скока (JMP) и инструкција скока на потпрограм (JSR). Битовима 3 до 0 првог бајта инструкције специфира се код инструкције и на освову тога су за инструкције BGRT, JMP и JSR усвојени кодови операције 00000000, 00010000 и 00010001, респективно. Инструкције JMP и JSR се реализују као апсолутни скокови, при чему је адреса дата другим и трећим бајтом инструкције. Дужина инструкција је 3 бајта. Инструкција BGRT се реализује као релативни скок у односу на текућу вредност програмског бројача PC, а померај је 8-битна целобројна величина са знаком дата другим бајтом инструкције. Дужина инструкције је 2 бајта.

Битови 7, 6 и 5 првог бајта инструкције су 001 за све безадресне инструкције. Безадресне инструкције су инструкције стављања садржаја акумулатора на стек (PUSH), пуњења акумулатора садржајем са стека (POP) и инструкција декрементирања акумулатора (DEC). Битовима 4 до 0 првог бајта инструкције специфира се код операције за безадресне инструкције. На основу тога су за инструкције PUSH, POP и DEC усвојени кодови операција 00100000, 00100001 и 00100010, респективно. Дужина инструкција је 1 бајт.

Битови 7, 6 и 5 првог бајта инструкције имају вредности од 010 до 111 за адресне инструкције. Адресне инструкције су инструкција преноса у акумулатор (LD), инструкција преноса из акумулатора (ST), инструкција аритметичког померања удесно за једно место (ASR), инструкција упоређивања акумулатора са операндом (CMP), инструкција сабирања (ADD) и инструкција одузимања (SUB). На основу тога су за инструкције LD, ST, ASR, CMP, ADD и SUB усвојени кодови операција 010, 011, 100, 101, 110 и 111, респективно. Дужина инструкција је 2 или 3 бајта и зависи од специфичног начина адресирања.

Начини адресирања су специфирани битовима 4, 3 и 2 првог бајта инструкције и то на следећи начин: 000-меморијско директно адресирање (memdir), 001-меморијско индиректно адресирање (memind), 010-регистарско директно адресирање (regdir), 011-регистарско инсиректно адресирање (regind), 100-релативно адресирање са померајем (pcrel), 101-непосредно адресирање (immed) и 110-регистарско индиректно адресирање са преинкрементирањем (preincr). Код меморијског директног и меморијског индиректног адресирања 16-битна адреса меморијске локације је дата другим и трећим бајтом инструкције. Битови 1 и 0 првог бајта инструкције се не користе. Дужина инструкције је 3 бајта. Регистарско директно, регистарско индиректно и регистарско индиректно адресирање са преинкрементирањем користе неке од регистара опште намене R0 до R3 специфиране битовима 1 и 0 првог бајта. Дужина инструкција је 1 бајт. Код релативног адресирања са померајем други бајт инструкције садржи 8-битни померај који је дат као целобројна величина са знаком. Битови 1 и 0 првог бајта инструкције се не користе. Дужина инструкција је 2 бајта. Код непосредног адресирања 16-битни операнд дат је другим и трећим бајтом инструкције. Битови 1 и 0 првог бајта инструкције се не користе. Дужина инструкција је 3 бајта.

Стек расте према вишим меморијским локацијама, а регистар SP указује на прву слободну меморијску локацију. Процесор нема могућност обраде прекида.

<div class="abc-list">
#Пројектовати део операционе јединице процесора (фазе: FETCH, ADDR и EXEC) која је потребна да се изврши инструкција '''CMP (PC)pom'''. Померај '''pom''' је целобројна величина са знаком који је дат другим бајтом инструкције. Цртати само неопходне компоненте које су потребне за извршавање наведене инструкције.
#Дати су почетни садржаји регистара и индикатора: PC = 1000h, SP = 2000h, ACC = 0010h, R0 = 0000h, R1 = 0001h, R2 = 0002h, R3 = 0003h, N = 0, Z = 0, V = 0 и C = 0. Индикатори статусне речи на које инструкција не утиче треба да остану непромењени. Извршити 7 сукцесивних наредби и за сваку наредбу одредити следеће: у фази читања инструкције - меморијске адресе са којих је прочитана инструкција, садржај регистара IR, инструкцију која је прочитана и нови садржај регистра PC; у фази одрђивања адресе операнда и читања операнда - меморијске адресе са којих је прочитана адреса операнда, меморијске адресе са којих је прочитан операнд, вредност операнда и нови садржај регистара опште намене који су у овој фази промењени; у фази извршавања операције - меморијске адресе којима се у овој фази приступа, садржај акумулатора А и индикатора N, Z, V и C након извршавања инструкције и нови садржај регистара и меморијских локација који су у овој фази промењени. Резултате представити у табелама 1, 2 и 3 формулара.
</div>

== Решење ==
{{delimično rešeno}}

[[Категорија:ОРТ2]]
[[Категорија:Рокови]]

ОС1/Јул 2013

2021-09-23T18:17:21Z

Дејан Ковачевић: /* Rešenje */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2013/jul/OS1%20-%20Jul%202013.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Objasniti pojam raspodele vremena (''time sharing'') kod multiprocesnih sistema.

=== Rešenje ===
OS dodeljuje procesoru vreme izvršavanja svakog posla i relativno često preuzima procesor. Osnovna ideja je da posao (engl. task) može da izgubi procesor nakon isteka dodeljenog procesorskog vremena ili kada sam zatraži promenu konteksta. Rezultat je da svaki korisnik ima utisak da računar radi samo za njega sa dovoljno dobrim vremenskim odzivom, dok računar opslužuje više korisnika.

== 2. zadatak ==
=== Postavka ===
Data je '''pogrešna''' implementacija operacije <code>yield()</code> za neki troadresni procesor. Ova operacija bi trebalo da izvrši preuzimanje procesora od niti na čiji vrh steka ukazuje vrednost sačuvana na lokaciji na koju ukazuje argument <code>cur</code>, i predaju procesora niti na čiji vrh steka ukazuje vrednost sačuvana na lokaciji na koju ukazuje argument <code>next</code>. Objasniti zašto ova implementacija nije ispravna i korigovati je.

<syntaxhighlight lang="c">
void yield (void* cur, void* next) {
asm {
push r0
push r1
...
push rn
add r0,sp,#cur
mov [r0],sp
add r0,sp,#next
mov sp,[r0]
pop rn
...
pop r1
pop r0
pop pc ; return
}
}
</syntaxhighlight>

=== Rešenje ===
Umesto <code>add r0,sp,#cur</code> treba napisati <code>mov r0, #cur[sp]</code>, tj. u <code>r0</code> treba upisati adresu <code>sp</code> pa ubaciti na tu adresu <code>sp</code>.
Umesto <code>add r0,sp,#next</code> treba napisati <code>mov r0, #next[sp]</code>, tj. u <code>r0</code> treba upisati adresu novog <code>sp</code>.

== 3. zadatak ==
=== Postavka ===
Korišćenjem sistemskog poziva <code>fork()</code>, napisati program koji, kada se pokrene kao proces, kreira onoliko procesa-dece, koliko je dato argumentom tog programа. Ni taj proces, ni njegova deca ne treba da rade ništa više.

=== Rešenje ===
<syntaxhighlight lang="c">
int main(int argc, char* argv[]) {
if(argc < 2) return -1;
int N = atoi(argv[1]);
for(int i = 0; i < N; i++)
if(fork() == 0)
return 0;

return 0;
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Data dva procesa međusobno se iključuju pri ulazu u dve kritične sekcije pomoću semafora čija je inicijalna vrednost 1. Objasniti šta je problem ove implementacije.
<syntaxhighlight lang="ada">
process P1; process P2:
wait(S1); wait(S2);
wait(S2); wait(S1);
... ...
signal(S2); signal(S1);
signal(S1); signal(S2);
end P1; end P2;
</syntaxhighlight>

=== Rešenje ===
Problem je što će doći do deadlock-a, odnosno, moguće je da ''P1'' i ''P2'' prođu prvi <code>wait</code> jer je inicijalna vrednost semafora 1 ali će se zatim blokirati na drugim <code>wait()</code>-ovima.

== 5. zadatak ==
=== Postavka ===
Koju uslugu operativni sistem treba da obezbedi procesima da bi oni koristili preklope (''overlays'')?

=== Rešenje ===
Preklopi ne zahtevaju podršku OS-a. Sve obavlja prevodilac i generisani kod. OS samo obezbeđuje usluge za alokaciju dela virtuelnog adresnog prostora.

== 6. zadatak ==
=== Postavka ===
Data je definicija strukture <code>FreeSegment</code> koja predstavlja jedan segment slobodne memorije. Ove strukture uvezane su u dvostruko ulančanu, neuređenu listu čija je glava <code>freeSegHead</code>. Implementirati funkciju <code>getWorstFit(size_t)</code> koja treba da pronađe i vrati (ali ne menja ni njega ni listu) segment slobodne memorije u koji se može smestiti blok date veličine, po ''worst fit'' algoritmu.
<syntaxhighlight lang = "c">
struct FreeSegment {
size_t size;
FreeSegment *prev, *next;
};
</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang = "c">
FreeSegment* getWorstFit(size_t size) {
FreeSegment *curr = freeSegHead, *max = NULL;
size_t maxSize = 0;
while(curr) {
if(curr->size >= size && curr->size > maxSize) {
max = curr;
maxSize = curr->size;
}
curr = curr->next;
}
return max;
}
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Neki računar podržava segmentno-straničnu organizaciju virtuelne memorije, pri čemu je virtuelna adresa 16-bitna, fizički adresni prostor je veličine 8GB, a adresibilna jedinica je 16-bitna reč. Stranica je veličine 512B. Maksimalan broj segmenata u virtuelnom adresnom prostoru je 4. Prikazati logičku strukturu virtuelne i fizičke adrese i navesti širinu svakog polja.

=== Rešenje ===
{{delimično rešeno}}

== 8. zadatak ==
=== Postavka ===
Kojom tehnikom se fizički nedeljiv izlazni uređaj može učiniti logički (virtuelno) deljivim između procesa koji ga uporedo koriste?

=== Rešenje ===
Tehnikom spooling.

== 9. zadatak ==
=== Postavka ===
Napisati punu stazu (''path'') do fajla <code>resenja.doc</code> koji se nalazi u direktorijumu <code>d:/nastava/os/ispiti/jul2013</code> na uređaju <code>d:</code> posle sledeće operacije montiranja (prvi argument je fajl sistem koji montira, drugi je odredište montaže): <code>mount d: /etf/rti</code>

=== Rešenje ===
<code>/etf/rti/nastava/os/ispiti/jul2013</code>

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem koristi indeksiranu alokaciju fajlova na disku sa jednostrukim indeksom. Ako se pretpostavlja da je prostor za smeštanje fajlova (uključujući i njihove indekse) na disku veličine 32 GB, veličina klastera (jedine jedinice alokacije) 2 KB, i ceo prostor potpuno ispunjen fajlovima, gde je svaki fajl maksimalne veličine i ima samo jedan indeksni klaster, koliki procenat ukupnog prostora za smeštanje fajlova na ovom disku zauzimaju indeksi?

=== Rešenje ===
Videti zadatak iz [[ОС1/Октобар 2012#10. zadatak|oktobarskog roka 2012]].

[[Категорија:Рокови]]
[[Категорија:ОС1]]

ОС1/Јун 2018

2021-09-22T23:32:20Z

Дејан Ковачевић: ipak je bolje po starom

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2018/jun/Jun%202018.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Objasniti razliku između pojmova ''proces'' i ''nit'' (engl. ''thread'').

=== Rešenje ===
Proces je jedno izvršavanje programa sa jednim adresnim prostorom. Nit (''thread'') ili laki proces je tok kontrole koji teče uporedo sa drugim tokovima kontrole, ali koji deli virtuelni adresni prostor sa nekim drugim tokom ili tokovima kontrole.

== 2. zadatak ==
=== Postavka ===
Korišćenjem standardnih bibliotečnih operacija <code>setjmp</code> i <code>longjmp</code>, implementirati operaciju ''wait'' na binarnom semaforu koji je realizovan klasom <code>Event</code> poput one u školskom jezgru.

=== Rešenje ===
<syntaxhighlight lang="cpp">
void Event::wait() {
if (val == 1) {
val = 0;
} else {
if (setjmp(Thread::running->context) == 0) {
blocked.put(running);
Thread::running = Scheduler::get();
longjmp(Thread::running->context, 1);
}
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Korišćenjem sistemskih poziva <code>fork</code> i <code>exec</code>, napisati funkciju <code>run</code> koja kreira proces nad programom u fajlu sa zadatom putanjom i vraća negativnu vrednost u slučaju greške, a <code>pid</code> kreiranog procesa u slučaju uspeha pri <code>fork</code>. Ukoliko ne uspe <code>exec</code>, kreirani proces-dete treba ugasiti.

=== Rešenje ===
<syntaxhighlight lang="cpp">
int run(char* path) {
pid_t pid = fork();
if (pid < 0) {
return -1;
}
if (pid == 0) {
int t = exec(path);
if (t < 0) {
exit(-2);
}
}
return pid;
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Dva procesa pristupaju kritičnoj sekciji. Dat je presudokod jednog od njih, koji bi trebalo da obezbedi međusobno isključenje uposlenim čekanjem (kod drugog procesa izgleda analogno). Da li ovo rešenje obezbeđuje međusobno isključenje? Da li ima neki problem (ako ima, koji)?
<syntaxhighlight lang="milo">
process P1
begin
loop
flag1 := true;
while flag2 = true do null end;
<critical section>
flag1 := false;
<non-critical section>
end
end P1;
</syntaxhighlight>

=== Rešenje ===
Ovo rešenje ne valja jer se dešava ''livelock'' odnosno oba procesa se međusobno zaključaju i ni jedan ni drugi se neće dalje izvršavati. To se desi kada proces P1 postavi <code>flag1</code> na <code>true</code> a zatim se desi promena konteksta i P2 postavi <code>flag2</code> na <code>true</code>.

== 5. zadatak ==
=== Postavka ===
Za koju od ove dve tehnike, dinamičko učitavanje (''dynamic loading'') ili preklopi (''overlays''), se može očekivati duže izvršavanje istog programa u najgorem slučaju? Precizno obrazložiti.

=== Rešenje ===
Duže vreme izvršavanja u najgorem slučaju se može očekivati kod preklopa jer će program stalno učitavati iz memorije iznova i iznova, dok će dinamičko učitavanje zauzeti više memorije, svaki potreban modul će učitati po jednom.

== 6. zadatak ==
=== Postavka ===
U nekom sistemu primenjuje se ''worst-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 ===
Jedno slovo označava 8KB prostora.
AAAAAAAA------------------------
AAAAAAAABB----------------------
AAAAAAAABBCCCCCCCCCCCCCCCC------
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDD--
E-------BBCCCCCCCCCCCCCCCCDDDD--
EFFFF---BBCCCCCCCCCCCCCCCCDDDD--
EFFFF-----CCCCCCCCCCCCCCCCDDDD--
* Slobodnih fragmenata: 2
* Najmanji slobodan fragment: 16KB
* Najveći slobodan fragment: 40KB

== 7. zadatak ==
=== Postavka ===
Prilikom preslikavanja virtuelne adrese, procesor je generisao izuzetak zbog pokušaja upisa na tu adresu koji je u deskriptoru stranice označen kao zabranjen. Operativni sistem ipak neće ugasiti taj proces. Precizno objasniti zašto.

=== Rešenje ===
Neće ugasiti program jer se zapravo radi o tehnici ''copy-on-write'' odnosno kopiranja na upis. U ovoj tehnici, MMU vidi tu memoriju kao zabranjenu za upis. Prilikom generisanja greške, OS proverava da li je zabranjena, i kako vidi da zapravo nije nije, to znači da se radi o tehnici kopiranja na upis pa će operativni sistem kopirati stranicu i reći MMU da je dozvoljena za upis.

== 8. zadatak ==
=== Postavka ===
Navesti tri usluge vezane za realno vreme koje operativni sistem može da nudi i predložiti i kratko objasniti funkcije – sistemske pozive za te usluge.

=== Rešenje ===
# Informacija o tekućem realnom vremenu:
#: <syntaxhighlight lang="c" inline>time_t time (time_t* tloc);</syntaxhighlight>
#: Vraća broj sekundi koje su protekle od 1. 1. 1970. u 0 časova. Postoje i bibliotečke funkcije u <code>time.h</code> koje vraćaju “kalendarsko” vreme, rastavljeno na datum i sat itd, a oslanjaju se na ovaj sistemski poziv: <code>asctime</code>, <code>ctime</code>, <code>gmtime</code>, <code>localtime</code>.
# Suspenzija pozivajućeg procesa (“uspavljivanje”) za zadato vreme
#: <syntaxhighlight lang="c" inline>unsigned int sleep (unsigned int seconds);</syntaxhighlight>
# Čekanje na događaje, uslove ili na sinhronizacione primitive, ali vremenski ograničeno (tzv. ''timeout'' kontrole); ako se proces ne deblokira u zadatom vremenu, biće deblokiran zbog isteka vremenske kontrole; npr. za semafore:
#: <syntaxhighlight lang="c" inline>int sem_timedwait (sem_t *sem, const struct timespec *abs_timeout);</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Ako je tekući direktorijum nekog procesa <code>/a/b/c</code>, koja je apsolutna putanja do fajla koji taj proces otvara davanjem putanje <code>d/../../e/f.txt</code>?

=== Rešenje ===
Raščlanimo relativnu putanju na delove:
* <code>d</code>: idemo u direktorijum <code>d</code>, sada je putanja <code>/a/b/c/d</code>
* <code>..</code> idemo jedan direktorijum iznad, sada je putanja <code>/a/b/c</code>
* <code>..</code> idemo jedan direktorijum iznad, sada je putanja <code>/a/b</code>
* <code>e</code> idemo u direktorijum <code>e</code>, sada je putanja <code>/a/b/e</code>
* <code>f.txt</code> posećujemo fajl <code>f.txt</code>, krajnja putanja je <code>/a/b/e/f.txt</code>

== 10. zadatak ==
=== Postavka ===
Fajl sistem primenjuje ulančanu alokaciju, s tim da se i slobodni blokovi ulančavaju u listu. U strukturi FCB polje <code>head</code> sadrži broj prvog bloka sa sadržajem fajla, a polje <code>size</code> veličinu sadržaja. Funkcija jezgra <code>free</code> prima kao argument broj prvog bloka u lancu blokova koje treba proglasiti slobodnim. Napisati funkciju jezgra <code>truncate</code> koja briše sadržaj fajla na čiji <code>FCB</code> ukazuje argument.

=== Rešenje ===
Pretpostavimo da <code>free_head</code> i <code>free_tail</code> predstavljaju pokazivače na početak i kraj ulančane liste slobodnih blokova.
<syntaxhighlight lang="c">
void truncate(FCB *f) {
if (f->head == NULL) return;
int numOfBlocks = f->size / BLOCK_SIZE, i = 0, cur = f->head, tmp_head = f->head, prev;
while (i < numOfBlocks) {
free(cur);
prev = cur;
cur = cur->next;
i++;
}
if (free_head == NULL) free_head = tmp_head;
else free_tail->next = tmp_head;
free_tail = prev;
}
</syntaxhighlight>
[[Категорија:Рокови]]
[[Категорија:ОС1]]

ОС1/Јун 2018

2021-09-22T21:06:16Z

Дејан Ковачевић: free_tail treba da pokazuje na poslednji a ne na head

ОС1/Фебруар 2012

2021-09-22T17:51:16Z

Дејан Ковачевић: treba proveriti ovo

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2012/februar/Feb%202012.doc Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Na asembleru nekog dvoadresnog RISC procesora sa LOAD/STORE arhitekturom napisati prevod sledeće funkcije:
<syntaxhighlight lang="c">
int log (int n) {
if (n<2) return 0;
else return 1+log(n/2);
}
</syntaxhighlight>
=== Rešenje ===
<syntaxhighlight lang="asm">
log: LD R1, #n[SP]
CMP R1, #2
JGE else
LD R0, #0
RTS
else: LD R0, #1
ASL R1, R0
PUSH R1
CALL log
POP R1
ADD R0, R1
RTS
</syntaxhighlight>

== 2. zadatak ==
=== Postavka ===
Na koji način se u programu koga izvršava procesor može znati da je DMA završio operaciju koja mu je zadata?

=== Rešenje ===
#Ispitivanjem indikatora u statusnom registru DMA kontrolera.
#Kada DMA kontroler završi sa radom, generiše prekid.

== 3. zadatak ==
=== Postavka ===
Navesti najmanje tri slučaja (uzroka) u kojima tekući proces gubi procesor.

=== Rešenje ===
#Eksplicitnim zahtevom za promenu konteksta - dispatch, yield - sinhrono.
#Isteklo je dodeljeno CPU vreme - time exceeded - asinhrono.
#Prekid - maskirajući ili nemaskirajući - asinhrono.
#Zbog operacije na nekoj sinhronizacionoj primitivi tj. semaforu ili događaju - sinhrono.

== 4. zadatak ==
=== Postavka ===
Proces ''P'' treba da sačeka da sva tri procesa ''X'', ''Y'' i ''Z'' ispune neki svoj uslov, u bilo kom redosledu. Napisati deo koda procesa ''P'' i bilo kog od druga tri procesa, uz potrebne deklaracije, koji obezbeđuju ovu uslovnu sinhronizaciju pomoću jednog standardnog brojačkog semafora.

=== Rešenje ===
<syntaxhighlight lang="ada">
var sem : Semaphore := 0, semX, semY, semZ : Semaphore := 1;

process P
begin
...
wait(sem);
wait(sem);
wait(sem);
...
signal(semX);
signal(semY);
signal(semZ);
end
end P;

process X // ali isto i Y i Z
begin
wait(semX);
...
signal(sem);
...
end
end X;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
<syntaxhighlight lang = "c">
float base = 2.0;
float log(float);
float ln(float);
float log(float x) {
return ln(x)/ln(base);
}
</syntaxhighlight>
#Koliko nerazrešenih adresnih polja instrukcija prevodilac ostavlja u ovom fajlu?
#Koje simbole izvozi ovaj fajl?
#Koje simbole uvozi ovaj fajl?

=== Rešenje ===
# Prevodilac ostavlja 2 nerazrešena polja, jer se dva puta poziva funkcija ln, pa će se u asemblerskom kodu dva puta naći red call ?.
# Izvoze se log i base.
# Uvozi se ln.

== 6. zadatak ==
=== Postavka ===
Navesti osnovne sličnosti i osnovne razlike između tehnike dinamičkog učitavanja memorije i preklopa (''overlays'').
=== Rešenje ===
{{delimično rešeno}}

== 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. U koje ulaze PMT prvog nivoa i drugog nivoa se preslikava stranica broj 5423Dh?
=== Rešenje ===
{{delimično rešeno}}

== 8. zadatak ==
=== Postavka ===
Ukratko objasniti princip dvostrukog baferisanja kod ulazno-izlaznih operacija.

=== Rešenje ===
U jedan bafer proizvođač upisuje podatke a iz drugog potrošač izvlači podatke. Kada oba učesnika završe fazu - punjenje odnosno pražnjenje, baferi zamenjuju uloge.

== 9. zadatak ==
=== Postavka ===
Da li je veličina fajla ograničena ako je način alokacije blokova za fajlove na disku:
#ulančani
#indeksirani

=== Rešenje ===
#ne
#da

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem koristi indeksirani pristup alokaciji blokova za fajlove na disku, sa kombinovanom tehnikom indeksiranja u jednom, dva i tri nivoa, kao kod UNIX ''inode'' strukture. Pretpostavljajući da disk ima uniformno srednje vreme pristupa do bilo kog bloka na disku, da li je vreme pristupa do različitih delova veoma velikih fajlova jednako? Ako jeste, precizno objasniti zašto jeste, a ako nije, objasniti kako se i zašto razlikuje.

=== Rešenje ===
Nije. Vreme pristupa za blokove bliže kraju velikog fajla je veće nego na početni deo fajla jer se mora prolaziti kroz višestruke indekse.

[[Категорија:Рокови]]
[[Категорија:ОС1]]

ОС1/Јун 2012

2021-09-20T17:51:41Z

Дејан Ковачевић: 2 -> 3

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2012/jun/Jun%202012.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Šta je to sistem sa raspodelom vremena (engl. ''time-sharing'')?

=== Rešenje ===
Sistem sa raspodelom vremena je sistem u kome OS dodeljuje procesor nekom procesu na određeno vreme, zatim se procesu preotima procesor, vrši promena konteksta i procesor predaje drugom procesu kome se ponovo ograničava vreme izvršavanja. Na ovaj način procesi dele vreme na procesoru.

== 2. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati prevod sledeće rekurzivne funkcije:
<syntaxhighlight lang="c">
int f (int n) {
if (n<=0) return 0;
else return f(n-1)+1;
}
</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="asm">
f: LD R1, #n[SP]
LD R0, #0
CMP R1, R0
JG else
RTS ; u R0 je 0
else: LD R0, #1
SUB R1, R0
PUSH R1
CALL f
POP R1
ADD R0, R1
RTS
</syntaxhighlight>

== 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)?
<syntaxhighlight lang="c">
void main () {
for (int i=0; i<7; i++) if(fork() > 0) return;
}
</syntaxhighlight>

=== Rešenje ===
Pošto samo dete nastavlja dalje, a pravi se 7 dece, ukupno ima 8 procesa.

== 4. zadatak ==
=== Postavka ===
Korišćenjem standardnih brojačkih semafora napisati kod dva uporedna procesa koji sarađuju na sledeći način. Proces ''A'' upisuje jednu vrednost u deljenu promenljivu ''x'', koju proces ''B'' potom čita. Tek kada je ''B'' pročitao tu vrednost, proces ''A'' upisuje novu vrednost u ''x'', koju proces ''B'' onda čita, i tako ciklično

=== Rešenje ===
<syntaxhighlight lang="ada">
shared var x : Integer;
semA : Semaphore := 0;
semB : Semaphore := 0;

process A
begin
loop
x = ...
signal(semB);
wait(semA);
end
end A;

process B
begin
loop
wait(semB);
y = ...
signal(semA);
end
end B;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Neki program koristi dve velike strukture podataka naizmenično: najpre za neku složenu obradu koristi samo prvu strukturu, pa onda za neku drugu obradu koristi samo drugu strukturu, pa onda ponovo prvu, pa drugu itd. Ako se ove dve strukture učitavaju dinamički i preklapaju se (kod korišćenja preklopa, overlays), u kom slučaju će izvršavanje tog programa trajati duže, a u kom će koristiti više memorije: kada se koristi samo dinamičko učitavanje, ili kada se koriste preklopi? Kratko obrazložiti.

=== Rešenje ===
Kod preklopa će izvršavanje trajati duže zbog učitavanja, a dinamičko učitavanje će koristiti više memorije.

== 6. zadatak ==
=== Postavka ===
Neki sistem primenjuje kontinualnu alokaciju memorije i ''best-fit'' algoritam alokacije, pri čemu su segmenti slobodne memorije organizovani u sledeću strukturu podataka:
#sortiranu ulančanu listu,
#balansirano binarno stablo.

Koliko segmenata treba obići u najgorem slučaju da bi se pronašao odgovarajući slobodan segment prilikom alokacije, ukoliko je slobodnih segmenata ''n''?

=== Rešenje ===
# <math> n </math>
# <math> log_{2}(n) </math>

== 7. zadatak ==
=== Postavka ===
Učestanost pogotka u TLB je 90%, a PMT je organizovana u dva nivoa. TLB je 10 puta brža nego operativna memorija. Koliko je efektivan pristup memoriji sporiji od pristupa fizičkoj memoriji?

=== Rešenje ===
<math> 0.9 \cdot (0.1 t_{RAM} + t_{RAM}) + 0.1 \cdot (0.1t_{RAM} + 3t_{RAM}) = 1.3t_{RAM} </math>

<math> 30\% </math>

== 8. zadatak ==
=== Postavka ===
Navesti osnovne operacije klase blokovski orijentisanih uređaja sa direktnim pristupom

=== Rešenje ===
{{delimično rešeno}}

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:
*<code>int size(FHANDLE)</code> Vraća trenutnu veličinu sadržaja fajla u znakovima.
*<code>void append(FHANDLE,int)</code> Proširuje sadržaj fajla za dati broj znakova na kraju.
*<code>void seek(FHANDLE,int)</code> Postavlja kurzor datog fajla na datu poziciju (redni broj znaka počev od 0).
*<code>void write(FHANDLE,char*,int size)</code> Na poziciju kurzora datog fajla upisuje dati niz znakova zadate dužine, i pomera kurzor iza upisanog niza znakova.

Operacije <code>seek</code> i <code>write</code> rade samo u opsegu trenutne veličine sadržaja fajla (ne pomeraju kurzor i ne upisuju iza kraja sadržaja fajla). Napisati operaciju

<code>write(FHANDLE,int position,char*,int size);</code>

koja na zadatu poziciju upisuje zadati niz znakova date veličine, pri čemu se fajl implicitno najpre
proširuje na potrebnu veličinu ukoliko bi zadata pozicija ili zadati upis prekoračio trenutnu veličinu
sadržaja fajla. Zanemariti sve moguće greške u ulazu/izlazu

=== Rešenje ===
{{delimično rešeno}}

== 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
# ulančana lista blokova, pri čemu na prvi blok sadržaja fajla ukazuje polje u FCB,
# indeksna, pri čemu je indeks fajla uvek u dva nivoa, a na blok sa indeksom prvog nivoa ukazuje polje u FCB? FCB fajla je u memoriji

=== Rešenje ===
# n
# 3

[[Категорија:Рокови]]
[[Категорија:ОС1]]

ОС1/Модификације предрок 2019

2021-09-06T14:27:59Z

Дејан Ковачевић: /* addOwner -> removeOwner */

{{tocright}}
{{нерешено}}

Следеће модификације су се појавиле на одбрани пројекта у предроку 2019.

== 20 поена ==
* Проширити класу <code>Semaphore</code> статичком методом <code>addOwner()</code> и нестатичком методом <code>removeOwner(ID id)</code> које додају и уклањају власнике семафора, респективно.
* <code>addOwner()</code> додаје текућу нит као власника. <code>removeOwner(ID id)</code> уклања нит са задатим <code>ID</code>- јем уколико је она била власник.
* Уколико методе <code>wait()</code> или <code>signal()</code> позове нит која не припада скупу власника, оне немају ефекта.

[[Категорија:Лабораторијске вежбе]]
[[Категорија:ОС1]]

ОС1/Јун 2018

2021-09-03T13:13:11Z

Дејан Ковачевић: /* 2. zadatak */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2018/jun/Jun%202018.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Objasniti razliku između pojmova ''proces'' i ''nit'' (engl. ''thread'').

=== Rešenje ===
Proces je jedno izvršavanje programa sa jednim adresnim prostorom. Nit (''thread'') ili laki proces je tok kontrole koji teče uporedo sa drugim tokovima kontrole, ali koji deli virtuelni adresni prostor sa nekim drugim tokom ili tokovima kontrole.

== 2. zadatak ==
=== Postavka ===
Korišćenjem standardnih bibliotečnih operacija <code>setjmp</code> i <code>longjmp</code>, implementirati operaciju ''wait'' na binarnom semaforu koji je realizovan klasom <code>Event</code> poput one u školskom jezgru.

=== Rešenje ===
<syntaxhighlight lang="cpp">
Event::wait() {
if(val == 1) {
val = 0;
}
else {
if(setjmp(Thread::running->context) == 0) {
blocked.put(running);
Thread::running = Scheduler::get();
longjmp(Thread::running->context, 1);
}
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Korišćenjem sistemskih poziva <code>fork</code> i <code>exec</code>, napisati funkciju <code>run</code> koja kreira proces nad programom u fajlu sa zadatom putanjom i vraća negativnu vrednost u slučaju greške, a <code>pid</code> kreiranog procesa u slučaju uspeha pri <code>fork</code>. Ukoliko ne uspe <code>exec</code>, kreirani proces-dete treba ugasiti.

=== Rešenje ===
<syntaxhighlight lang="cpp">
int run(char* path) {
pid_t pid = fork();
if (pid < 0) {
return -1;
}
if (pid == 0) {
int t = exec(path);
if (t < 0) {
exit(-2);
}
}
return pid;
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Dva procesa pristupaju kritičnoj sekciji. Dat je presudokod jednog od njih, koji bi trebalo da obezbedi međusobno isključenje uposlenim čekanjem (kod drugog procesa izgleda analogno). Da li ovo rešenje obezbeđuje međusobno isključenje? Da li ima neki problem (ako ima, koji)?
<syntaxhighlight lang="milo">
process P1
begin
loop
flag1 := true;
while flag2 = true do null end;
<critical section>
flag1 := false;
<non-critical section>
end
end P1;
</syntaxhighlight>

=== Rešenje ===
Ovo rešenje ne valja jer se dešava ''livelock'' odnosno oba procesa se međusobno zaključaju i ni jedan ni drugi se neće dalje izvršavati. To se desi kada proces P1 postavi <code>flag1</code> na <code>true</code> a zatim se desi promena konteksta i P2 postavi <code>flag2</code> na <code>true</code>.

== 5. zadatak ==
=== Postavka ===
Za koju od ove dve tehnike, dinamičko učitavanje (''dynamic loading'') ili preklopi (''overlays''), se može očekivati duže izvršavanje istog programa u najgorem slučaju? Precizno obrazložiti.

=== Rešenje ===
Duže vreme izvršavanja u najgorem slučaju se može očekivati kod preklopa jer će program stalno učitavati iz memorije iznova i iznova, dok će dinamičko učitavanje zauzeti više memorije, svaki potreban modul će učitati po jednom.

== 6. zadatak ==
=== Postavka ===
U nekom sistemu primenjuje se ''worst-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 ===
Jedno slovo označava 8KB prostora.
AAAAAAAA------------------------
AAAAAAAABB----------------------
AAAAAAAABBCCCCCCCCCCCCCCCC------
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDD--
E-------BBCCCCCCCCCCCCCCCCDDDD--
EFFFF---BBCCCCCCCCCCCCCCCCDDDD--
EFFFF-----CCCCCCCCCCCCCCCCDDDD--
* Slobodnih fragmenata: 2
* Najmanji slobodan fragment: 16KB
* Najveći slobodan fragment: 40KB

== 7. zadatak ==
=== Postavka ===
Prilikom preslikavanja virtuelne adrese, procesor je generisao izuzetak zbog pokušaja upisa na tu adresu koji je u deskriptoru stranice označen kao zabranjen. Operativni sistem ipak neće ugasiti taj proces. Precizno objasniti zašto.

=== Rešenje ===
Neće ugasiti program jer se zapravo radi o tehnici ''copy-on-write'' odnosno kopiranja na upis. U ovoj tehnici, MMU vidi tu memoriju kao zabranjenu za upis. Prilikom generisanja greške, OS proverava da li je zabranjena, i kako vidi da zapravo nije nije, to znači da se radi o tehnici kopiranja na upis pa će operativni sistem kopirati stranicu i reći MMU da je dozvoljena za upis.

== 8. zadatak ==
=== Postavka ===
Navesti tri usluge vezane za realno vreme koje operativni sistem može da nudi i predložiti i kratko objasniti funkcije – sistemske pozive za te usluge.

=== Rešenje ===
# Informacija o tekućem realnom vremenu:
#: <syntaxhighlight lang="c" inline>time_t time (time_t* tloc);</syntaxhighlight>
#: Vraća broj sekundi koje su protekle od 1. 1. 1970. u 0 časova. Postoje i bibliotečke funkcije u <code>time.h</code> koje vraćaju “kalendarsko” vreme, rastavljeno na datum i sat itd, a oslanjaju se na ovaj sistemski poziv: <code>asctime</code>, <code>ctime</code>, <code>gmtime</code>, <code>localtime</code>.
# Suspenzija pozivajućeg procesa (“uspavljivanje”) za zadato vreme
#: <syntaxhighlight lang="c" inline>unsigned int sleep (unsigned int seconds);</syntaxhighlight>
# Čekanje na događaje, uslove ili na sinhronizacione primitive, ali vremenski ograničeno (tzv. ''timeout'' kontrole); ako se proces ne deblokira u zadatom vremenu, biće deblokiran zbog isteka vremenske kontrole; npr. za semafore:
#: <syntaxhighlight lang="c" inline>int sem_timedwait (sem_t *sem, const struct timespec *abs_timeout);</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Ako je tekući direktorijum nekog procesa <code>/a/b/c</code>, koja je apsolutna putanja do fajla koji taj proces otvara davanjem putanje <code>d/../../e/f.txt</code>?

=== Rešenje ===
Raščlanimo relativnu putanju na delove:
* <code>d</code>: idemo u direktorijum <code>d</code>, sada je putanja <code>/a/b/c/d</code>
* <code>..</code> idemo jedan direktorijum iznad, sada je putanja <code>/a/b/c</code>
* <code>..</code> idemo jedan direktorijum iznad, sada je putanja <code>/a/b</code>
* <code>e</code> idemo u direktorijum <code>e</code>, sada je putanja <code>/a/b/e</code>
* <code>f.txt</code> posećujemo fajl <code>f.txt</code>, krajnja putanja je <code>/a/b/e/f.txt</code>

== 10. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Fajl sistem primenjuje ulančanu alokaciju, s tim da se i slobodni blokovi ulančavaju u listu. U strukturi FCB polje <code>head</code> sadrži broj prvog bloka sa sadržajem fajla, a polje <code>size</code> veličinu sadržaja. Funkcija jezgra <code>free</code> prima kao argument broj prvog bloka u lancu blokova koje treba proglasiti slobodnim. Napisati funkciju jezgra <code>truncate</code> koja briše sadržaj fajla na čiji <code>FCB</code> ukazuje argument.

=== Rešenje ===

[[Категорија:Рокови]]
[[Категорија:ОС1]]

ОС1/Јул 2019

2021-09-03T13:10:49Z

Дејан Ковачевић: resen pogresan zadatak, sad ispravljeno

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2019/jul/Jul%202019.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Šta se smatra multiprocesorskim računarskim sistemom? Šta je simetričan multiprocesorski sistem?

=== Rešenje ===
Multiprocesorski sistem je sistem sa više procesora koji imaju zajedničku memoriju. Simetričan multiprocesorski sistem znači da su svi procesori opšte namene, jednaki i imaju isto vreme pristupa operativnoj memoriji. Asimetrični multiprocesorski sistem ima i specijalizovane procesore ili procesore sa različitim vremenom pristupa memoriji.

== 2. zadatak ==
=== Postavka ===
Neki procesor prilikom obrade prekida prebacuje svoje izvršavanje na korišćenje posebnog pokazivača steka koji se koristi u privilegovanom režimu rada, i pritom čuva sve registre na steku na čiji vrh ukazuje ovaj pokazivač. Operativni sistem na ovom procesoru koristi samo jedan sistemski stek za izvršavanje celog kernel koda. Da li se kontekst izvršavanja procesa (kontekst procesora) može čuvati na ovom steku?

=== Rešenje ===
{{delimično rešeno}}

== 3. zadatak ==
=== Postavka ===
Korišćenjem niti u školskom jezgru napisati funkciju <code>sum</code> koja kreira nit koja će sabrati sve elemente zadatog niza zadate dužine i rezultat upisati na traženo mesto; u slučaju greške ove funkcije vraćaju negativnu vrednost.
<syntaxhighlight lang="c">int sum (int array[], size_t size, long* result);</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="cpp">
class SumThread {
public:
SumThread(int* arr, size_t _size, long* res): array(arr), size(_size), result(res) {}
void run() {
long res = 0;
for (size_t i = 0; i < size; i++) {
res += array[i];
}
*result = res;
}
private:
int* array;
size_t size;
long* result;
};

int sum (int array[], size_t size, long* result) {
if (result == nullptr) return -1;
SumThread* st = new SumThread(array, size, result);
st->start();
delete st;
return 0;
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Napisati pseudokod koji obezbeđuje međusobno isključenje pristupa kritičnoj sekciji dva procesa pomoću Petersonovog algoritma.

=== Rešenje ===
<syntaxhighlight lang="ada">
shared var turn : integer := 1, flag1, flag2 : boolean := false;
process P1
begin
loop
flag1 := true;
turn := 2;
while flag2 and turn = 2 do null;
<critical section>
flag1 := false;
<non-critical section>
end
end P1;
process P2
begin
loop
flag2 := true;
turn := 1;
while flag1 and turn = 1 do null;
<critical section>
flag2 := false;
<non-critical section>
end
end P2;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Zbog čega operativni sistem ne radi zamenu (''swapping'') procesa njegovim izbacivanjem iz memorije prilikom svake promene konteksta, kada procesu koji je izgubio procesor memorija svakako nije potrebna?

=== Rešenje ===
Zato što je pristup hard disku vrlo spor te će takva implementacija znatno uticati na performanse. Ovo se primenjivalo na ''[[wikipedia:Windows 3.1|Windows 3.1]]'', i bilo je vrlo sporo. Danas, ''swapping'' se koristi kada nema dovoljno mesta u operativnoj memoriji.

== 6. zadatak ==
=== Postavka ===
Šta je kompakcija kod kontinualne alokacije memorije?

=== Rešenje ===
Kod kontinualne alokacije može doći do eksterne fragmentacije, odnosno da su slobodni fragmenti toliko mali da ni jedan proces ne može stati na tom delu, ali zbirno ih ima dovoljno za neki procos. Kompakcija rešava taj problem realokacijom svih zauzetih delova i spajanjem svih slobodnih fragmenata u jedan veliki slobodan fragment. Dok se dešava kompakcija, nijedan proces koji se pomera se ne može izvršavati.

== 7. zadatak ==
=== Postavka ===
Virtuelni adresni prostor je velične 8GB, a adresibilna jedinica je 16-bitna reč. Stranica je veličine 4KB, a preslikavanje je u dva nivoa, s tim da PMT prvog nivoa ima dva puta manje ulaza nego PMT drugog nivoa. Prikazati strukturu virtuelne adrese i označiti širinu svakog polja.

=== Rešenje ===
VA(32): Page1(10), Page2(11), Offset(11)

== 8. zadatak ==
=== Postavka ===
Navesti tipične usluge operativnog sistema vezane za pristup blokovski orijentisanom ulaznom uređaju sa direktnim pristupom i predložiti potpise odgovarajućih funkcija za te sistemske pozive.

=== Rešenje ===
Osnovne usluge jesu pisanje i čitanje.
<syntaxhighlight lang="c">
int readBlock(int fd, BlockNo block, void* buffer);
int writeBlock(int fd, BlockNo block, void* buffer);
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Objasniti koncept ACL (''access control list'').

=== Rešenje ===
Da bi se fajlovi zaštitili, jedan način je da se ograniče prava pristupa korisnika. Potrebno je definisati koji korisnik (ili grupa korisnika) može da izvršava koju operaciju. Jedan pristup je svakom fajlu pridružiti listu ovih parova (korisnik i operacija). Takva lista je lista kontrole pristupa (ACL).

== 10. zadatak ==
=== Postavka ===
Fajl sistem primenjuje FAT alokaciju, s tim da se i slobodni blokovi ulančavaju u listu. U strukturi FCB polje <code>head</code> sadrži broj prvog bloka sa sadržajem fajla, a polje <code>size</code> veličinu sadržaja. Globalna promenljiva <code>fat_free_head</code> sadrži broj prvog bloka (glavu liste), a <code>fat_free_tail</code> poslednjeg bloka (rep liste) u lancu slobodnih. FAT je u memoriju učitana kao niz. Napisati funkciju jezgra <code>truncate</code> koja briše sadržaj fajla na čiji FCB ukazuje argument.

=== Rešenje ===
<syntaxhighlight lang="cpp">
const unsigned long FAT_SIZE = ...;
unsigned long FAT[FAT_SIZE];

void truncate(FCB* file) {
unsigned long b = file->head;
for (unsigned long i = 0; i < file->size; ++i) {
unsigned long next = FAT[b];
FAT[b] = 0;
// Ovde se smatra da fat_free_tail pokazuje na blok 0 kada nema slobodnih blokova.
if (fat_free_tail) {
FAT[fat_free_tail] = b;
fat_free_tail = b;
} else {
fat_free_head = b;
fat_free_tail = b;
}
b = next;
}
file->size = 0;
file->head = 0;
}
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:ОС1]]

ОС1/Јун 2018

2021-09-03T13:09:30Z

Дејан Ковачевић: /* Rešenje */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2018/jun/Jun%202018.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Objasniti razliku između pojmova ''proces'' i ''nit'' (engl. ''thread'').

=== Rešenje ===
Proces je jedno izvršavanje programa sa jednim adresnim prostorom. Nit (''thread'') ili laki proces je tok kontrole koji teče uporedo sa drugim tokovima kontrole, ali koji deli virtuelni adresni prostor sa nekim drugim tokom ili tokovima kontrole.

== 2. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Korišćenjem standardnih bibliotečnih operacija <code>setjmp</code> i <code>longjmp</code>, implementirati operaciju ''wait'' na binarnom semaforu koji je realizovan klasom <code>Event</code> poput one u školskom jezgru.

=== Rešenje ===
<syntaxhighlight lang="cpp">
Event::wait() {
if(val == 1) {
val = 0;
}
else {
if(setjmp(Thread::running->context) == 0) {
blocked.put(running);
Thread::running = Scheduler::get();
longjmp(Thread::running->context, 1);
}
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Korišćenjem sistemskih poziva <code>fork</code> i <code>exec</code>, napisati funkciju <code>run</code> koja kreira proces nad programom u fajlu sa zadatom putanjom i vraća negativnu vrednost u slučaju greške, a <code>pid</code> kreiranog procesa u slučaju uspeha pri <code>fork</code>. Ukoliko ne uspe <code>exec</code>, kreirani proces-dete treba ugasiti.

=== Rešenje ===
<syntaxhighlight lang="cpp">
int run(char* path) {
pid_t pid = fork();
if (pid < 0) {
return -1;
}
if (pid == 0) {
int t = exec(path);
if (t < 0) {
exit(-2);
}
}
return pid;
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Dva procesa pristupaju kritičnoj sekciji. Dat je presudokod jednog od njih, koji bi trebalo da obezbedi međusobno isključenje uposlenim čekanjem (kod drugog procesa izgleda analogno). Da li ovo rešenje obezbeđuje međusobno isključenje? Da li ima neki problem (ako ima, koji)?
<syntaxhighlight lang="milo">
process P1
begin
loop
flag1 := true;
while flag2 = true do null end;
<critical section>
flag1 := false;
<non-critical section>
end
end P1;
</syntaxhighlight>

=== Rešenje ===
Ovo rešenje ne valja jer se dešava ''livelock'' odnosno oba procesa se međusobno zaključaju i ni jedan ni drugi se neće dalje izvršavati. To se desi kada proces P1 postavi <code>flag1</code> na <code>true</code> a zatim se desi promena konteksta i P2 postavi <code>flag2</code> na <code>true</code>.

== 5. zadatak ==
=== Postavka ===
Za koju od ove dve tehnike, dinamičko učitavanje (''dynamic loading'') ili preklopi (''overlays''), se može očekivati duže izvršavanje istog programa u najgorem slučaju? Precizno obrazložiti.

=== Rešenje ===
Duže vreme izvršavanja u najgorem slučaju se može očekivati kod preklopa jer će program stalno učitavati iz memorije iznova i iznova, dok će dinamičko učitavanje zauzeti više memorije, svaki potreban modul će učitati po jednom.

== 6. zadatak ==
=== Postavka ===
U nekom sistemu primenjuje se ''worst-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 ===
Jedno slovo označava 8KB prostora.
AAAAAAAA------------------------
AAAAAAAABB----------------------
AAAAAAAABBCCCCCCCCCCCCCCCC------
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDD--
E-------BBCCCCCCCCCCCCCCCCDDDD--
EFFFF---BBCCCCCCCCCCCCCCCCDDDD--
EFFFF-----CCCCCCCCCCCCCCCCDDDD--
* Slobodnih fragmenata: 2
* Najmanji slobodan fragment: 16KB
* Najveći slobodan fragment: 40KB

== 7. zadatak ==
=== Postavka ===
Prilikom preslikavanja virtuelne adrese, procesor je generisao izuzetak zbog pokušaja upisa na tu adresu koji je u deskriptoru stranice označen kao zabranjen. Operativni sistem ipak neće ugasiti taj proces. Precizno objasniti zašto.

=== Rešenje ===
Neće ugasiti program jer se zapravo radi o tehnici ''copy-on-write'' odnosno kopiranja na upis. U ovoj tehnici, MMU vidi tu memoriju kao zabranjenu za upis. Prilikom generisanja greške, OS proverava da li je zabranjena, i kako vidi da zapravo nije nije, to znači da se radi o tehnici kopiranja na upis pa će operativni sistem kopirati stranicu i reći MMU da je dozvoljena za upis.

== 8. zadatak ==
=== Postavka ===
Navesti tri usluge vezane za realno vreme koje operativni sistem može da nudi i predložiti i kratko objasniti funkcije – sistemske pozive za te usluge.

=== Rešenje ===
# Informacija o tekućem realnom vremenu:
#: <syntaxhighlight lang="c" inline>time_t time (time_t* tloc);</syntaxhighlight>
#: Vraća broj sekundi koje su protekle od 1. 1. 1970. u 0 časova. Postoje i bibliotečke funkcije u <code>time.h</code> koje vraćaju “kalendarsko” vreme, rastavljeno na datum i sat itd, a oslanjaju se na ovaj sistemski poziv: <code>asctime</code>, <code>ctime</code>, <code>gmtime</code>, <code>localtime</code>.
# Suspenzija pozivajućeg procesa (“uspavljivanje”) za zadato vreme
#: <syntaxhighlight lang="c" inline>unsigned int sleep (unsigned int seconds);</syntaxhighlight>
# Čekanje na događaje, uslove ili na sinhronizacione primitive, ali vremenski ograničeno (tzv. ''timeout'' kontrole); ako se proces ne deblokira u zadatom vremenu, biće deblokiran zbog isteka vremenske kontrole; npr. za semafore:
#: <syntaxhighlight lang="c" inline>int sem_timedwait (sem_t *sem, const struct timespec *abs_timeout);</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Ako je tekući direktorijum nekog procesa <code>/a/b/c</code>, koja je apsolutna putanja do fajla koji taj proces otvara davanjem putanje <code>d/../../e/f.txt</code>?

=== Rešenje ===
Raščlanimo relativnu putanju na delove:
* <code>d</code>: idemo u direktorijum <code>d</code>, sada je putanja <code>/a/b/c/d</code>
* <code>..</code> idemo jedan direktorijum iznad, sada je putanja <code>/a/b/c</code>
* <code>..</code> idemo jedan direktorijum iznad, sada je putanja <code>/a/b</code>
* <code>e</code> idemo u direktorijum <code>e</code>, sada je putanja <code>/a/b/e</code>
* <code>f.txt</code> posećujemo fajl <code>f.txt</code>, krajnja putanja je <code>/a/b/e/f.txt</code>

== 10. zadatak ==
{{delimično rešeno}}
=== Postavka ===
Fajl sistem primenjuje ulančanu alokaciju, s tim da se i slobodni blokovi ulančavaju u listu. U strukturi FCB polje <code>head</code> sadrži broj prvog bloka sa sadržajem fajla, a polje <code>size</code> veličinu sadržaja. Funkcija jezgra <code>free</code> prima kao argument broj prvog bloka u lancu blokova koje treba proglasiti slobodnim. Napisati funkciju jezgra <code>truncate</code> koja briše sadržaj fajla na čiji <code>FCB</code> ukazuje argument.

=== Rešenje ===

[[Категорија:Рокови]]
[[Категорија:ОС1]]

ОС1/Јул 2019

2021-09-03T13:08:40Z

Дејан Ковачевић: /* Rešenje */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2019/jul/Jul%202019.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Šta se smatra multiprocesorskim računarskim sistemom? Šta je simetričan multiprocesorski sistem?

=== Rešenje ===
Multiprocesorski sistem je sistem sa više procesora koji imaju zajedničku memoriju. Simetričan multiprocesorski sistem znači da su svi procesori opšte namene, jednaki i imaju isto vreme pristupa operativnoj memoriji. Asimetrični multiprocesorski sistem ima i specijalizovane procesore ili procesore sa različitim vremenom pristupa memoriji.

== 2. zadatak ==
=== Postavka ===
Neki procesor prilikom obrade prekida prebacuje svoje izvršavanje na korišćenje posebnog pokazivača steka koji se koristi u privilegovanom režimu rada, i pritom čuva sve registre na steku na čiji vrh ukazuje ovaj pokazivač. Operativni sistem na ovom procesoru koristi samo jedan sistemski stek za izvršavanje celog kernel koda. Da li se kontekst izvršavanja procesa (kontekst procesora) može čuvati na ovom steku?

=== Rešenje ===

== 3. zadatak ==
=== Postavka ===
Korišćenjem niti u školskom jezgru napisati funkciju <code>sum</code> koja kreira nit koja će sabrati sve elemente zadatog niza zadate dužine i rezultat upisati na traženo mesto; u slučaju greške ove funkcije vraćaju negativnu vrednost.
<syntaxhighlight lang="c">int sum (int array[], size_t size, long* result);</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="cpp">
class SumThread {
public:
SumThread(int* arr, size_t _size, long* res): array(arr), size(_size), result(res) {}
void run() {
long res = 0;
for (size_t i = 0; i < size; i++) {
res += array[i];
}
*result = res;
}
private:
int* array;
size_t size;
long* result;
};

int sum (int array[], size_t size, long* result) {
if (result == nullptr) return -1;
SumThread* st = new SumThread(array, size, result);
st->start();
delete st;
return 0;
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Napisati pseudokod koji obezbeđuje međusobno isključenje pristupa kritičnoj sekciji dva procesa pomoću Petersonovog algoritma.

=== Rešenje ===
<syntaxhighlight lang="ada">
shared var turn : integer := 1, flag1, flag2 : boolean := false;
process P1
begin
loop
flag1 := true;
turn := 2;
while flag2 and turn = 2 do null;
<critical section>
flag1 := false;
<non-critical section>
end
end P1;
process P2
begin
loop
flag2 := true;
turn := 1;
while flag1 and turn = 1 do null;
<critical section>
flag2 := false;
<non-critical section>
end
end P2;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Zbog čega operativni sistem ne radi zamenu (''swapping'') procesa njegovim izbacivanjem iz memorije prilikom svake promene konteksta, kada procesu koji je izgubio procesor memorija svakako nije potrebna?

=== Rešenje ===
Zato što je pristup hard disku vrlo spor te će takva implementacija znatno uticati na performanse. Ovo se primenjivalo na ''[[wikipedia:Windows 3.1|Windows 3.1]]'', i bilo je vrlo sporo. Danas, ''swapping'' se koristi kada nema dovoljno mesta u operativnoj memoriji.

== 6. zadatak ==
=== Postavka ===
Šta je kompakcija kod kontinualne alokacije memorije?

=== Rešenje ===
Kod kontinualne alokacije može doći do eksterne fragmentacije, odnosno da su slobodni fragmenti toliko mali da ni jedan proces ne može stati na tom delu, ali zbirno ih ima dovoljno za neki procos. Kompakcija rešava taj problem realokacijom svih zauzetih delova i spajanjem svih slobodnih fragmenata u jedan veliki slobodan fragment. Dok se dešava kompakcija, nijedan proces koji se pomera se ne može izvršavati.

== 7. zadatak ==
=== Postavka ===
Virtuelni adresni prostor je velične 8GB, a adresibilna jedinica je 16-bitna reč. Stranica je veličine 4KB, a preslikavanje je u dva nivoa, s tim da PMT prvog nivoa ima dva puta manje ulaza nego PMT drugog nivoa. Prikazati strukturu virtuelne adrese i označiti širinu svakog polja.

=== Rešenje ===
VA(32): Page1(10), Page2(11), Offset(11)

== 8. zadatak ==
=== Postavka ===
Navesti tipične usluge operativnog sistema vezane za pristup blokovski orijentisanom ulaznom uređaju sa direktnim pristupom i predložiti potpise odgovarajućih funkcija za te sistemske pozive.

=== Rešenje ===
Osnovne usluge jesu pisanje i čitanje.
<syntaxhighlight lang="c">
int readBlock(int fd, BlockNo block, void* buffer);
int writeBlock(int fd, BlockNo block, void* buffer);
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Objasniti koncept ACL (''access control list'').

=== Rešenje ===
Da bi se fajlovi zaštitili, jedan način je da se ograniče prava pristupa korisnika. Potrebno je definisati koji korisnik (ili grupa korisnika) može da izvršava koju operaciju. Jedan pristup je svakom fajlu pridružiti listu ovih parova (korisnik i operacija). Takva lista je lista kontrole pristupa (ACL).

== 10. zadatak ==
=== Postavka ===
Fajl sistem primenjuje FAT alokaciju, s tim da se i slobodni blokovi ulančavaju u listu. U strukturi FCB polje <code>head</code> sadrži broj prvog bloka sa sadržajem fajla, a polje <code>size</code> veličinu sadržaja. Globalna promenljiva <code>fat_free_head</code> sadrži broj prvog bloka (glavu liste), a <code>fat_free_tail</code> poslednjeg bloka (rep liste) u lancu slobodnih. FAT je u memoriju učitana kao niz. Napisati funkciju jezgra <code>truncate</code> koja briše sadržaj fajla na čiji FCB ukazuje argument.

=== Rešenje ===
<syntaxhighlight lang="cpp">
const unsigned long FAT_SIZE = ...;
unsigned long FAT[FAT_SIZE];

void truncate(FCB* file) {
unsigned long b = file->head;
for (unsigned long i = 0; i < file->size; ++i) {
unsigned long next = FAT[b];
FAT[b] = 0;
// Ovde se smatra da fat_free_tail pokazuje na blok 0 kada nema slobodnih blokova.
if (fat_free_tail) {
FAT[fat_free_tail] = b;
fat_free_tail = b;
} else {
fat_free_head = b;
fat_free_tail = b;
}
b = next;
}
file->size = 0;
file->head = 0;
}
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:ОС1]]

ОС1/Јул 2019

2021-09-03T13:05:15Z

Дејан Ковачевић: /* Rešenje */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2019/jul/Jul%202019.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Šta se smatra multiprocesorskim računarskim sistemom? Šta je simetričan multiprocesorski sistem?

=== Rešenje ===
Multiprocesorski sistem je sistem sa više procesora koji imaju zajedničku memoriju. Simetričan multiprocesorski sistem znači da su svi procesori opšte namene, jednaki i imaju isto vreme pristupa operativnoj memoriji. Asimetrični multiprocesorski sistem ima i specijalizovane procesore ili procesore sa različitim vremenom pristupa memoriji.

== 2. zadatak ==
=== Postavka ===
Neki procesor prilikom obrade prekida prebacuje svoje izvršavanje na korišćenje posebnog pokazivača steka koji se koristi u privilegovanom režimu rada, i pritom čuva sve registre na steku na čiji vrh ukazuje ovaj pokazivač. Operativni sistem na ovom procesoru koristi samo jedan sistemski stek za izvršavanje celog kernel koda. Da li se kontekst izvršavanja procesa (kontekst procesora) može čuvati na ovom steku?

=== Rešenje ===
<syntaxhighlight lang="cpp">
Event::wait() {
if(val == 1) {
val = 0;
}
else {
if(setjmp(Thread::running->context) == 0) {
blocked.put(running);
Thread::running = Scheduler::get();
longjmp(Thread::running->context, 1);
}
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Korišćenjem niti u školskom jezgru napisati funkciju <code>sum</code> koja kreira nit koja će sabrati sve elemente zadatog niza zadate dužine i rezultat upisati na traženo mesto; u slučaju greške ove funkcije vraćaju negativnu vrednost.
<syntaxhighlight lang="c">int sum (int array[], size_t size, long* result);</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="cpp">
class SumThread {
public:
SumThread(int* arr, size_t _size, long* res): array(arr), size(_size), result(res) {}
void run() {
long res = 0;
for (size_t i = 0; i < size; i++) {
res += array[i];
}
*result = res;
}
private:
int* array;
size_t size;
long* result;
};

int sum (int array[], size_t size, long* result) {
if (result == nullptr) return -1;
SumThread* st = new SumThread(array, size, result);
st->start();
delete st;
return 0;
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Napisati pseudokod koji obezbeđuje međusobno isključenje pristupa kritičnoj sekciji dva procesa pomoću Petersonovog algoritma.

=== Rešenje ===
<syntaxhighlight lang="ada">
shared var turn : integer := 1, flag1, flag2 : boolean := false;
process P1
begin
loop
flag1 := true;
turn := 2;
while flag2 and turn = 2 do null;
<critical section>
flag1 := false;
<non-critical section>
end
end P1;
process P2
begin
loop
flag2 := true;
turn := 1;
while flag1 and turn = 1 do null;
<critical section>
flag2 := false;
<non-critical section>
end
end P2;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Zbog čega operativni sistem ne radi zamenu (''swapping'') procesa njegovim izbacivanjem iz memorije prilikom svake promene konteksta, kada procesu koji je izgubio procesor memorija svakako nije potrebna?

=== Rešenje ===
Zato što je pristup hard disku vrlo spor te će takva implementacija znatno uticati na performanse. Ovo se primenjivalo na ''[[wikipedia:Windows 3.1|Windows 3.1]]'', i bilo je vrlo sporo. Danas, ''swapping'' se koristi kada nema dovoljno mesta u operativnoj memoriji.

== 6. zadatak ==
=== Postavka ===
Šta je kompakcija kod kontinualne alokacije memorije?

=== Rešenje ===
Kod kontinualne alokacije može doći do eksterne fragmentacije, odnosno da su slobodni fragmenti toliko mali da ni jedan proces ne može stati na tom delu, ali zbirno ih ima dovoljno za neki procos. Kompakcija rešava taj problem realokacijom svih zauzetih delova i spajanjem svih slobodnih fragmenata u jedan veliki slobodan fragment. Dok se dešava kompakcija, nijedan proces koji se pomera se ne može izvršavati.

== 7. zadatak ==
=== Postavka ===
Virtuelni adresni prostor je velične 8GB, a adresibilna jedinica je 16-bitna reč. Stranica je veličine 4KB, a preslikavanje je u dva nivoa, s tim da PMT prvog nivoa ima dva puta manje ulaza nego PMT drugog nivoa. Prikazati strukturu virtuelne adrese i označiti širinu svakog polja.

=== Rešenje ===
VA(32): Page1(10), Page2(11), Offset(11)

== 8. zadatak ==
=== Postavka ===
Navesti tipične usluge operativnog sistema vezane za pristup blokovski orijentisanom ulaznom uređaju sa direktnim pristupom i predložiti potpise odgovarajućih funkcija za te sistemske pozive.

=== Rešenje ===
Osnovne usluge jesu pisanje i čitanje.
<syntaxhighlight lang="c">
int readBlock(int fd, BlockNo block, void* buffer);
int writeBlock(int fd, BlockNo block, void* buffer);
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Objasniti koncept ACL (''access control list'').

=== Rešenje ===
Da bi se fajlovi zaštitili, jedan način je da se ograniče prava pristupa korisnika. Potrebno je definisati koji korisnik (ili grupa korisnika) može da izvršava koju operaciju. Jedan pristup je svakom fajlu pridružiti listu ovih parova (korisnik i operacija). Takva lista je lista kontrole pristupa (ACL).

== 10. zadatak ==
=== Postavka ===
Fajl sistem primenjuje FAT alokaciju, s tim da se i slobodni blokovi ulančavaju u listu. U strukturi FCB polje <code>head</code> sadrži broj prvog bloka sa sadržajem fajla, a polje <code>size</code> veličinu sadržaja. Globalna promenljiva <code>fat_free_head</code> sadrži broj prvog bloka (glavu liste), a <code>fat_free_tail</code> poslednjeg bloka (rep liste) u lancu slobodnih. FAT je u memoriju učitana kao niz. Napisati funkciju jezgra <code>truncate</code> koja briše sadržaj fajla na čiji FCB ukazuje argument.

=== Rešenje ===
<syntaxhighlight lang="cpp">
const unsigned long FAT_SIZE = ...;
unsigned long FAT[FAT_SIZE];

void truncate(FCB* file) {
unsigned long b = file->head;
for (unsigned long i = 0; i < file->size; ++i) {
unsigned long next = FAT[b];
FAT[b] = 0;
// Ovde se smatra da fat_free_tail pokazuje na blok 0 kada nema slobodnih blokova.
if (fat_free_tail) {
FAT[fat_free_tail] = b;
fat_free_tail = b;
} else {
fat_free_head = b;
fat_free_tail = b;
}
b = next;
}
file->size = 0;
file->head = 0;
}
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:ОС1]]

Архитектура рачунара/Јун 2021

2021-07-08T16:20:42Z

Дејан Ковачевић: /* Штампарске грешке */

{{tocright}}

== 1. задатак ==
{{делимично решено}}
=== Поставка ===
'''[5п]''' У посматраном рачунарском систему процесор има 3 пара линија по којима улазно/излазни уређаји могу процесору да шаљу захтеве за прекид и од процесора добијају сигнале потврда. У датом систему има 8 улазно/излазних уређаја које треба некако повезати помоћу та 3 пара линија на процесор и омогућити за сваки улазно/излазни уређај скок на одговарајућу прекидну рутину векторисаним механизмом прекида.
# Нацртати како тих 8 улазно/излазних уређаја треба повезати помоћу та 3 пара линија на процесор.
# Нацртати интерну структуру контролера периферије који дозвољава серијско слање прекида наредној периферији у ланцу.

== 2. задатак ==
=== Поставка ===
'''[5п]''' Haписати оптималну секвенцу инструкција неопходних за срачунавање израза:
<syntaxhighlight lang="C">
int a,b,c,d,e,f;
...
a = (b+c) - (d+e);
if (a == 0) f = (b+c);
else f = (d+e);
</syntaxhighlight>
На располаrању је процесор код кога аритметичке, логичке и померачке инструкције имају формат: ОС reg, reg, reg/imm где је ОС код операције, одредишни операнд и први операнд морају бити у регистру (reg), док други може бити или у регистру или дат непосредно (reg/imm). Инструкција LOAD има формат: LOAD reg, mem где је првим операндом дат одредишни регистар (reg), a другим извориште. Инструкцијa STORE има формат: STORE reg, mem где је првим операндом дат изворишни регистар (reg), a другим одредиште. А, В, С, D, E и F су глобалне променљиве које одговарају симболичким ознакама адреса меморијских локација у којима се налазе операнди. Садржај меморијских локација означених адресама В, С, D и Е треба да остане непромењен, садржај одговарајућих регистара је дозвољено мењати. На располагању стоји 8 регистара опште намене. Претпоставити да су сви подаци и адресе исте дужине која је једнака адресибилној јединици

=== Решење ===
<syntaxhighlight lang="asm">
LOAD R1, b
LOAD R2, c
ADD R1, R1, R2
LOAD R2, d
LOAD R3, e
ADD R2, R2, R3
SUB R3, R1, R2
STORE R3, a
JNZ else
STORE R1, f
JMP end
else: STORE R2, f
end: ...
</syntaxhighlight>

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
'''[5п]''' Написати оптималну секвенцу инструкција која одговара следећој стандардној библиотечкој С функцији која копира ''n'' бајта низа ''src'' y низ ''dst'':
<syntaxhighlight lang="C">void *memсру (void *dst, const void *src, int n);</syntaxhighlight>
Функција као резултат враћа показивач на одредишни низ ''dst''. Формати инструкција и података су као у задатку 2. На располагању стоје и сложене инструкције.

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
'''[25п]''' У рачунарском систему се налази једноадресни процесор, меморија и периферије РЕR0, PER1 до РERN. Cматрати да број N припада скупу од 1 до 15 и да може да се користи као непосредна вредност у програму (#N). Периферији РER0 jе придружен DMA0 контролер. Све компоненте рачунара су повезане системском магистралом са 16 битном адресном и 16 битном магистралом података. Адресирање је на нивоу 16 битних речи. Сви подаци и адресе су ширине 16 бита. Узети да је тип података '''іnt''' дужине 16 бита. Улазно-излазни адресни простор и меморијски адресни простор су преклопљени. Адресе релевантних регистара периферија РER0 и DМА0 контролера су:
{|
| PER0_CONTROL || F000h || DMA0_CONTROL || F003h || DMA0_ADDR || F006h
|-
| PER0_STATUS || F001h || DMA0_STATUS || F004h || DMA0_CNT || F007h
|-
| PER0_DATA || F002h || DMA0_DATA || F005h
|}
Адресе релевантних регистара периферија РER1 до РERN се добијају као резултат потпрограма
<syntaxhighlight lang="C">int* getPеrRegAddr (unsigned int N, unsigned int typе);</syntaxhighlight>
где N представља број периферије, type представља тип регистра (1 - ENTRY, 2 - CONTROL, 3 - STATUS, 4 - DATA). Потпрограм ''getPerRegAddr'' не треба имплементирати, већ само позивати на одговарајућем месту у програму.

У управљачким регистрима бит 0 је ''Start'' којим се дозвољава почетак операције, бит 1 одрeђују тип преноса података (1 - улаз (''input''), 0 - излаз (''output'')), бит 2 је ''Enable'' којим се дозвољава прекид. Бит 3 управљачког регистра контролера DMA0 се задаје режим рада (0-блоковски (''burst''), 1-циклус по циклус (''сусle stealing'')). У статусним регистрима бит 0 је ''Ready'' који сигнализира спремност контролера периферије.

Написати главни програм, одговарајући потпрограм и прекидну рутину којима се обавља следећи пренос.

Периферија РER0 шаље низ од 100h означених целих бројева који се смештају у меморију почев од адресе 5000h. Hакон учитаног низа у меморију потребно је проследити максималну вредност низа периферијама РER1 до РЕRN. Пренос максималне вредности периферијама треба обављати у паралели, чим периферија буде спремна да прими податак. Након што је свака периферија примила максималну вредност, потребно је да РER0 учита нов низ (од 100h означених целих бројева који се смештају у меморију почев од адресе 5000h), да се проследи нова максимална вредност низа периферијама РER1 до PERN и тако циклично да ради програм.

Периферије PER1 до РERN када се једном укључе, није дозвољено да се потом искључе. Ради евиденције којoј периферији је прослеђена тренутна максимална вредност низа потребно је увести променљиву ''mask''. Bредност бита ''mask<sub>i</sub>'' треба да има вредност 1 уколико је тренутна максимална вредност низа прослеђена периферији РER<sub>i</sub>, a да има вредност 0 уколико тренутна максимална вредност низа није још прослеђена периферији РER<sub>i</sub>. Након прослеђене максималне вредности свим периферијама, вредност променльиву ''mask'' треба ресетовати на 0.

Потребно је имплементирати и у програму на одговарајуhем месту позвати потпрограм
<syntaxhighlight lang="C">int max (int* arrAddr, unsigned int length);</syntaxhighlight>
Који враћа максималну вредност низа задатом почетном адресом аrrAddr и дужине length eлемената.

Примање података са периферије РERO реализовати коришћењем DMА0 контролера у блоковском режиму рада. Слање података на периферије РER1 до РERN peализовати испитивањем бита спремности.

Сматрати да су доступни регистри ВР и SP приликом писања потпрограма. Обратити пажњу да потпрограм не сме да користи глобалне променљиве, већ само параметре потпрограма и локане променљиве. Позивалац потпрограма је дужан да уклони параметре са стека. Резултат потпрограма се враћа кроз акумулатор. Процесор не поседује регистре опште намене, као ни регистар IМR. Стек расте од виших ка нижим локацијама, а SP указује на последњу заузету локацију. Дозвољено је користити додатне променљиве, али њихове називе треба писати описно и семантички исправно. '''Обавезно је писање концизних коментара над семантичким целинама.'''

[[Категорија:Архитектура рачунара]]
[[Категорија:Рокови]]

НАД/К1 2020

2020-11-15T18:56:16Z

Дејан Ковачевић: /* Мислим да су били ови бројеви */

{{tocright}}

== Теорија ==
=== 1. питање ===
==== Поставка ====
Исказати и доказати теорему о потребним и довољним условима за постојање и јединстевеност непокретне тачке функције g(x) на интервалу [a, b].
==== Решење ====
'''Теорема 2.2''' на 15. страни из књиге.

=== 2. питање ===
==== Поставка ====
Како је помоћу LU композиције матрице А могуће израчунати њену детерминатну? (Подразумевало се да је већ извршена декомпозиција)
==== Решење ====
Одељак '''Одређивање детерминатне матрице LU декомпозицијом''' на 46. страни из књиге.

=== 3. питање ===
==== Поставка ====
Исказати услове теореме за матрицу коефицијената система под којим Јакобијева и Гаус-Зајделова итеративна метода конвергирају ка решењу линеарног система једначина.
==== Решење ====
'''Теорема 3.1''' на 57. страни из књиге.
Било је потребно дефинати и строгу дијагоналну доминантност матрице - '''Дефиниција 3.3''' на 48. страни из књиге.

=== 4. питање ===
==== Поставка ====
Извести Лагранжов интерполациони полином.
==== Решење ====
Одељак '''Лагранжов интерполациони полином''' на 67. и 68. страни из књиге.

== Задаци ==
=== 1. задатак ===
==== Поставка ====
Функција <math>f(x)</math> је задата следећом табелом:
{| class="wikitable"
! <math>x</math>
| 18.0 || 18.1 || 18.2 || 18.3 || 18.4 || 18.5 || 18.6
|-
! <math>f(x)</math>
| 0.0621 || 0.0599 || 0.0640 || 0.0740 || 0.0892 || 0.1098 || 0.1413
|}
Формирајући одговарајући Њутнов интерполациони полином трећег степена, израчунати <math>f</math>(18,09) и проценити грешку интерполације у тачки 18,09.

==== Решење ====
Поступак сличан '''14. задатку''' на 82. страни из књиге. За <math>x_0</math> узети 18.

=== 2. задатак ===
==== Поставка ====
Њутновом методом са тачношћу <math>10^{-4}</math>, одредити највеће негативно решење једначине
<math>e^x = \sin\frac{\pi x}{3}</math>
==== Решење ====
'''9. задатак''' на 25. страни у књизи. x је приближно -3,0454.

[[Категорија:НАД]]
[[Категорија:Рокови]]