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

САБ/К2Н 2023

2023-07-30T17:54:39Z

IvnSvc: Надокнада К2 из САБ 2023, датум 14 јун

=== Поставка ===
У систему болничког лечења прате се информације о лекарима који раде у болници и прегледима који су ти лекари обавили. Сваки пацијент може имати највише један картон у свакој од болница. Сваки картон се повремено оверава када се уписује назив послодавца преко кога је пацијент осигуран. У случајевима када је то потребно пацијенти могу бити хоспитализовани, тј. примљени на болничко лечење (датум отпуштања се попуњава тек након што се лечење заврши, а до тада је NULL). <br>
Одговарајућа шема базе је:

{|
|Mesto(<u>IDMes</u>, Naziv)
|-
|Bolnica (<u>IDBol</u>, Naziv, Kapacitet, Iskoriscenost, IDMes)
|-
|Pacijent(<u>IDPac</u>, Ime, JMBG, GodineStarosti, IDMes)
|-
|Lekar(<u>IDLek</u>, Ime, JMBG, Specijalizacija)
|-
|Karton(<u>IdKar</u>, IDPac, IDBol)
|-
|Pregled(<u>IdPre</u>, Datum, ObjektivniNalaz, DIjagnoza, IDKar, IdLek)
|-
|Hospitalizacija(<u>IDHos</u>, DatumPri, DatumOtp, Dijagnoza, KlinickaSlika, IDPac, IDBol)
|-
|Overa(<u>IDKar</u>, <u>RedBr</u>, DatumOd, NazivPoslodavca)
|-
|Radi(<u>IDLek</u>, IDBol)
|}
Iskoriscenost: N- Niska, S - Srednja, V - Viskoa

За посматрани систем саставити SQLServer процедуру AzurirajIskoriscenost(), која поставља атрибут искоришћеност у релацији Болница. Искоришћеност се поставља на основу врше (максималне) вредности попуњености болнице у било којем тренутку до сада. Конкретно, уколико је у било ком тренутку број хоспитализованих паицјената био преко 75% капацитета, она је висока. Уколико је мање или једнако од 75%, а више од 25% онда је средња. У супротном, уколико је мање или једнако 25% онда је њена искоришћеност ниска. У дане боравка у болници треба укључити датум пријема, али не и датум отпуштања из болнице.

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

Базе података 2/К2 2023

2023-05-21T19:58:24Z

IvnSvc: К2 из база података 2 2023 лета Господњег

За део базе података који обухвата дате табеле одредити најбољи план извршавања и проценити цену за дати упит. За сваку операцију из плана навести како се израчунава и по којој цени.

Odeljenje (<u>IDOde</u>, Opis)
Zaposleni (<u>IDZap</u>, Ime, IDOde)
Projekat (<u>IDPro</u>, Naziv)
Radi (<u>IDZar</u>,<u>IDPro</u>, Procenat)
Упит:
SELECT R.Procenat, R.IDPro, Z.Ime
FROM Radi R, Zaposleni Z
WHERE Z.IDZap = R.IDZap AND R.Procenat > 99 AND Z.Ime = 'Ivan'
ORDER BY R.Procenat

Познато је да у бази: <br>
-Табела запослени има 10к редова, табела ради 20к редова<br>
-У табелама Запослени и Ради има по 40 редова по страници<br>
-Бафер је величине 30 страница<br>
-За атрибут име посотји 1000 различитих вредности<br>
-проценат је вредност [0,100]<br>
-у табели Запослени постоји unclustered Hash index по атрибуту Ime<br>
-у табели Ради постоји unclustered Hash index по атрибуту IDZap, и clustered B+ index од 2 нивоа по атрибуту Procenat (индекс се не чува у меморији)<br>

=== Скица решења ===
Потребно је направити тотално потиснуто стабло. Спајање је "бесплатно" јер се после филтрирања спаја јако мало података и сви стају у меморију

Базе података 2/К1 2023

2023-04-10T17:34:37Z

IvnSvc: Додат рок без решења

{{tocright}}
{{нерешено}}
'''Први колоквијум 2023. године''' први колоквијум икад

== Поставка ==
Компанија уговара пројекте израде софтвера по наруџбинама клијента. У компанији су запослени програмери и менаџери.
У систему се води евиденција о сваком кораку рада (захтевима, развијеном коду, додели посла). За сваки пројекат неког клијента евидентирају се датум креирања, менаџер, као и сви кориснички захтеви. Пре него што пројекат почне он мора бити испланиран (статус I). Имплементација може почети тек након што се пројекат имплементира. Током имплементације, целокупан код који програмери развију се такође евидентира у систему и то тако што се за сваки код евидентира које корисничке захтеве имплементира. <br>

Шема базе:

Klijent (<u>SifК</u>, Naziv, Kontakt)
Radnik (<u>SifR</u>, Ime)
Menadzer (<u>SifR</u>, Iskustvo)
Programer (<u>SifR</u>, Specijalnost)
Projekat (<u>SifP</u>, Naziv, Status, Vrednost, DatumPocetka, BrojProgramera, MaksProgramera, SifK, SifR)
Zahtev (<u>SifZ</u>, Opis, SiP)
Posao (<u>SifJ</u>, DatumPocetka, DatumKraja, BrPlaniranihProgramera, SifP, SifZ)
Angazman (<u>SifA</u>, SifR, SifJ)
Kod (<u>SifK</u>, Kod)
Implementira (<u>SifK</u>, <u>SifZ</u>)

Статус: K, I, Z - креиран, испланиран, завршен.

== 1. задатак ==
Написати исказ релационе алгебре који даје шифре менаџера који су били надлежни за више од једног пројекта вредности преко 1000. Оператор груписања није дозвољен.

== 2. задатак ==
Написати исказ релационе алгебре који даје шифре менаџера који даје шифре програмера који су били ангажовани на свим пословима пројекта "ETФ". Оператор груписања није дозвољен.

== 3. задатак ==
За дати исказ релационе алгебре дати еквивалентат SQL упит: <br>
<syntaxhighlight lang="latex">
πSifR (Angazman⨝ ( πSifJ(σBrojPlaniranih>5 (Posao))-πSifJ(σBrojPlaniranih>10 (Posao)))) )
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:Базе података 2]]

САБ/К1 2022

2023-04-03T19:13:05Z

IvnSvc: додатни атрибута табела у првом

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

== 1. задатак ==
{{delimično rešeno}}
=== Поставка ===
За дати модел објеката и односа (с лева на десно, преглед објеката и односа и преглед ентитета и
својстава) саставити модел података у ИЕ нотацији. Подразумеване кардиналности су:: за специјализирање
0-1, за условљавање 0-n, за условљеност 1 и за учешће у вези 0-n.

{|
|A
|
|-
|B
|
|
|V1
|-
|B1
|
|-
|-
|C
|
|
|V2
|-
|D
|}
B има атрибут <BB1, BB2>, <br>
С има атрбут {CC2}

Додатак: пуна стрелица А(0,1)->B, пуна стрелица B(1-1)->B1, испрекидана B1->(2)С, пуна стрелица B->D. Веза V1 спаја A и B1, веза V2 спаја V1 и D

== 2. задатак ==
{{delimično rešeno}}
=== Поставка ===
За посматрани систем саставити модел података у ИЕ нотацији. За ентитете треба назна~ити само
примарне кључеве и мигриране стране кључеве. За ентитете означене * треба означити и динамичке референцијалне интегритете само са "parent" стране.

{|
|Sala(<u>SifS</u>)
|-
|Konfiguracija (<u>SifK</u>)
|-
|Osoba(<u>SifO</u>)
|-
|Gost(<u>SifO</u>)
|-
|Organizator(<u>SifO</u>)
|-
|Proslava(<u>SifP</u>, SifS, SifK)
|-
|Ulaznica(<u>SifU</u>, SifP, SifO)*
|-
|Refundacija(<u>SifR</u>, SifU)*
|-
|Podrzava(<u>SifS</u>, <u>SifK</u>)*
|-
|Organizuje(<u>SifP</u>, SifO)
|}
*изостављени су небитне колоне табела. Особа је или гост или радник или оба.

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

САБ/К1 2022

2023-04-03T19:04:46Z

IvnSvc: САБ К1 2023 лета, нерешен

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

== 1. задатак ==
{{delimično rešeno}}
=== Поставка ===
За дати модел објеката и односа (с лева на десно, преглед објеката и односа и преглед ентитета и
својстава) саставити модел података у ИЕ нотацији. Подразумеване кардиналности су:: за специјализирање
0-1, за условљавање 0-n, за условљеност 1 и за учешће у вези 0-n.

{|
|A
|
|-
|B
|
|
|V1
|-
|B1
|
|-
|-
|C
|
|
|V2
|-
|D
|}

Додатак: пуна стрелица А(0,1)->B, пуна стрелица B(1-1)->B1, испрекидана B1->(2)С, пуна стрелица B->D. Веза V1 спаја A и B1, веза V2 спаја V1 и D

== 2. задатак ==
{{delimično rešeno}}
=== Поставка ===
За посматрани систем саставити модел података у ИЕ нотацији. За ентитете треба назна~ити само
примарне кључеве и мигриране стране кључеве. За ентитете означене * треба означити и динамичке референцијалне интегритете само са "parent" стране.

{|
|Sala(<u>SifS</u>)
|-
|Konfiguracija (<u>SifK</u>)
|-
|Osoba(<u>SifO</u>)
|-
|Gost(<u>SifO</u>)
|-
|Organizator(<u>SifO</u>)
|-
|Proslava(<u>SifP</u>, SifS, SifK)
|-
|Ulaznica(<u>SifU</u>, SifP, SifO)*
|-
|Refundacija(<u>SifR</u>, SifU)*
|-
|Podrzava(<u>SifS</u>, <u>SifK</u>)*
|-
|Organizuje(<u>SifP</u>, SifO)
|}
*изостављени су небитне колоне табела. Особа је или гост или радник или оба.

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

Заштита података/К1 2023

2023-04-03T18:29:47Z

IvnSvc: (не)решени тагови

{{tocright}}
'''Prvi kolokvijum 2023. godine''' održan je 31. marta.
== 1. grupa ==
=== 1. zadatak ===
Koji bi nacin kriptoanalize koristili za napade na "One-time pad" nacin kriptovanja ? Da li je One-time pad otporan na te algoritme, ukoliko ne koji ima ?
Odgovor: <span class="spoiler" data-solution="text">ne moze nista da probije one-time pad</span>

=== 2. zadatak ===
Hill alogitam 2x2 matrica

=== 3. zadatak ===
{{delimično rešeno}}
Primenjuje se Miler-Rabinov algoritam za utvrđivanje da li je dat broj <math>n = 91</math> prost. Dati rezultat algoritma za dati slučajno određen broj <math>a</math>.
<div class="abc-list">
<ol>
<li data-solution="single">
<math>a = 9</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* Možda prost
* Nije prost
* Ne znam
</li>
<li data-solution="single">
<math>a = 11</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* Nije prost
* Možda prost
* Ne znam
</li>
</ol>
</div>

=== 4. zadatak ===
{{delimično rešeno}}
Branko salje broj svoje kreditne kartice, ali da bi ga zastitio odlucio je da ga sifruje, prvo sa "rail fence" u 4 reda, potom monoalfabetski sa kljucem 1597302846, potom ponovo sa "rail fence" u 4 reda. Originalni broj kartice je
4812 2391 0028 5722.
Dobijeni broj kartice je: <span class="spoiler" data-solution="text">nerešeno</span>

=== 5. zadatak ===
{{delimično rešeno}}
SAES posle prve iteracije.

== 2. grupa ==
=== 1. zadatak ===
{{delimično rešeno}}
Objasniti šta je poznato pri ''known plaintext'' metodi kriptoanalize. Da li je ''Hill''-ov algoritam otporan na known plaintext napade?

=== 2. zadatak ===
Ana želi da pošalje Marku poruku koristeći ''Vigenère'' šifru sa ''autokey'' poboljšanjem.
Ana je pomoću RSA algoritma poslala Marku šifrovan ključ za ''Vigenère'' algoritam koji glasi <math>C = \mathtt{432899}</math>.
Svaka cifra iz šifre se mapira u slovo pod tim rednim brojem (npr. 123=ABC).
Izabrali su <math>n = \mathtt{1003883}</math>, dok je Anin privatni ključ <math>d = \mathtt{2003}</math>.
Marko je primio poruku KNHFMMDVIMMPLZDU.

<div class="abc-list">
<ol>
<li>Ključ za ''Vigenère'' je : <span class="spoiler" data-solution="text">HFCAEI</span></li>
<li>Poruka koju je Ana poslala je : <span class="spoiler" data-solution="text">DIFFIEANDHELLMAN</span></li>
<li data-solution="single">
''Vigenère'' algoritam sa ''autokey'' poboljšanjem menja učestalost pojavljivanja slova u šifrovanoj poruci. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* Ne
* <span class="solution">Da</span>
* Ne znam
</li>
</ol>
</div>

=== 3. zadatak ===
Primenjuje se Miler-Rabinov algoritam za utvrđivanje da li je dat broj <math>n = 247</math> prost. Dati rezultat algoritma za dati slučajno određen broj <math>a</math>.
<div class="abc-list">
<ol>
<li data-solution="single">
<math>a = 12</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* <span class="solution">Možda prost</span>
* Nije prost
* Ne znam
</li>
<li data-solution="single">
<math>a = 15</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* <span class="solution">Nije prost</span>
* Možda prost
* Ne znam
</li>
</ol>
</div>

=== 4. zadatak ===
{{delimično rešeno}}
Složeni algoritam šifrovanja se koristi za šifrovanje nečijeg broja kreditne kartice. Broj kreditne kartice koji treba šifrovati je: '''4812 2391 0028 5722'''.
Složeni algoritam se sastoji od:
# ''Row Transposition'' algoritma za dešifrovanje sa ključem (4,3,2,1)
# Cezarovom šifrom sa pomerajem 3
# ''Row Transposition'' algoritma za šifrovanje sa ključem (4,3,2,1)

Šifrovan broj kreditne kartice glasi: <span class="spoiler" data-solution="text">nerešeno</span>

=== 5. zadatak ===
{{delimično rešeno}}
SAES algoritam se koristi za šifrovanje bloka '''2468h''' sa ključem '''5B9Fh'''. Parametri algoritma su: '''<math>RCON(1) = \mathtt{80h}, RCON(2) = \mathtt{30h} </math>'''. Nesvodljivi polinom '''0011b'''.
{| class="wikitable"
|+ S-Box tabela
!
! 00b !! 01b !! 10b !! 11b
|-
! 00b
| 9h || 4h || Ah || Bh
|-
! 01b
| Dh || 1h || 8h || 5h
|-
! 10b
| 6h || 2h || 0h || 3h
|-
! 11b
| Ch || Eh || Fh || 7h
|}
{| class="wikitable"
|+ MixColumns
| 1 || 4
|-
| 4 || 1
|}

<div class="abc-list">
<ol>
<li>Ključ za prvu rundu <math>K_1</math> glasi : <span class="spoiler" data-solution="text">nerešeno</span></li>
<li>Stanje pred MixColumns korak : <span class="spoiler" data-solution="text">nerešeno</span></li>
<li>Stanje na kraju prve runde : <span class="spoiler" data-solution="text">nerešeno</span></li>
</ol>
</div>

[[Категорија:Рокови]]
[[Категорија:Заштита података]]

Заштита података/К1 2023

2023-04-03T18:28:27Z

IvnSvc: /* 3. zadatak */ Разл решења трећег

{{tocright}}
'''Prvi kolokvijum 2023. godine''' održan je 31. marta.
== 1. grupa ==
=== 1. zadatak ===
{{delimično rešeno}}
Koji bi nacin kriptoanalize koristili za napade na "One-time pad" nacin kriptovanja ? Da li je One-time pad otporan na te algoritme, ukoliko ne koji ima ?
Odgovor: <span class="spoiler" data-solution="text">ne moze nista da probije one-time pad</span>

=== 2. zadatak ===
Hill alogitam 2x2 matrica

=== 3. zadatak ===
Primenjuje se Miler-Rabinov algoritam za utvrđivanje da li je dat broj <math>n = 91</math> prost. Dati rezultat algoritma za dati slučajno određen broj <math>a</math>.
<div class="abc-list">
<ol>
<li data-solution="single">
<math>a = 9</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* Možda prost
* Nije prost
* Ne znam
</li>
<li data-solution="single">
<math>a = 11</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* Nije prost
* Možda prost
* Ne znam
</li>
</ol>
</div>

=== 4. zadatak ===
{{delimično rešeno}}
Branko salje broj svoje kreditne kartice, ali da bi ga zastitio odlucio je da ga sifruje, prvo sa "rail fence" u 4 reda, potom monoalfabetski sa kljucem 1597302846, potom ponovo sa "rail fence" u 4 reda. Originalni broj kartice je
4812 2391 0028 5722.
Dobijeni broj kartice je: <span class="spoiler" data-solution="text">nerešeno</span>

=== 5. zadatak ===
{{delimično rešeno}}
SAES posle prve iteracije.

== 2. grupa ==
=== 1. zadatak ===
{{delimično rešeno}}
Objasniti šta je poznato pri ''known plaintext'' metodi kriptoanalize. Da li je ''Hill''-ov algoritam otporan na known plaintext napade?

=== 2. zadatak ===
Ana želi da pošalje Marku poruku koristeći ''Vigenère'' šifru sa ''autokey'' poboljšanjem.
Ana je pomoću RSA algoritma poslala Marku šifrovan ključ za ''Vigenère'' algoritam koji glasi <math>C = \mathtt{432899}</math>.
Svaka cifra iz šifre se mapira u slovo pod tim rednim brojem (npr. 123=ABC).
Izabrali su <math>n = \mathtt{1003883}</math>, dok je Anin privatni ključ <math>d = \mathtt{2003}</math>.
Marko je primio poruku KNHFMMDVIMMPLZDU.

<div class="abc-list">
<ol>
<li>Ključ za ''Vigenère'' je : <span class="spoiler" data-solution="text">HFCAEI</span></li>
<li>Poruka koju je Ana poslala je : <span class="spoiler" data-solution="text">DIFFIEANDHELLMAN</span></li>
<li data-solution="single">
''Vigenère'' algoritam sa ''autokey'' poboljšanjem menja učestalost pojavljivanja slova u šifrovanoj poruci. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* Ne
* <span class="solution">Da</span>
* Ne znam
</li>
</ol>
</div>

=== 3. zadatak ===
Primenjuje se Miler-Rabinov algoritam za utvrđivanje da li je dat broj <math>n = 247</math> prost. Dati rezultat algoritma za dati slučajno određen broj <math>a</math>.
<div class="abc-list">
<ol>
<li data-solution="single">
<math>a = 12</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* <span class="solution">Možda prost</span>
* Nije prost
* Ne znam
</li>
<li data-solution="single">
<math>a = 15</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* <span class="solution">Nije prost</span>
* Možda prost
* Ne znam
</li>
</ol>
</div>

=== 4. zadatak ===
{{delimično rešeno}}
Složeni algoritam šifrovanja se koristi za šifrovanje nečijeg broja kreditne kartice. Broj kreditne kartice koji treba šifrovati je: '''4812 2391 0028 5722'''.
Složeni algoritam se sastoji od:
# ''Row Transposition'' algoritma za dešifrovanje sa ključem (4,3,2,1)
# Cezarovom šifrom sa pomerajem 3
# ''Row Transposition'' algoritma za šifrovanje sa ključem (4,3,2,1)

Šifrovan broj kreditne kartice glasi: <span class="spoiler" data-solution="text">nerešeno</span>

=== 5. zadatak ===
{{delimično rešeno}}
SAES algoritam se koristi za šifrovanje bloka '''2468h''' sa ključem '''5B9Fh'''. Parametri algoritma su: '''<math>RCON(1) = \mathtt{80h}, RCON(2) = \mathtt{30h} </math>'''. Nesvodljivi polinom '''0011b'''.
{| class="wikitable"
|+ S-Box tabela
!
! 00b !! 01b !! 10b !! 11b
|-
! 00b
| 9h || 4h || Ah || Bh
|-
! 01b
| Dh || 1h || 8h || 5h
|-
! 10b
| 6h || 2h || 0h || 3h
|-
! 11b
| Ch || Eh || Fh || 7h
|}
{| class="wikitable"
|+ MixColumns
| 1 || 4
|-
| 4 || 1
|}

<div class="abc-list">
<ol>
<li>Ključ za prvu rundu <math>K_1</math> glasi : <span class="spoiler" data-solution="text">nerešeno</span></li>
<li>Stanje pred MixColumns korak : <span class="spoiler" data-solution="text">nerešeno</span></li>
<li>Stanje na kraju prve runde : <span class="spoiler" data-solution="text">nerešeno</span></li>
</ol>
</div>

[[Категорија:Рокови]]
[[Категорија:Заштита података]]

Заштита података/К1 2023

2023-04-03T18:26:29Z

IvnSvc: Додати и делови прве групе

{{tocright}}
'''Prvi kolokvijum 2023. godine''' održan je 31. marta.
== 1. grupa ==
=== 1. zadatak ===
{{delimično rešeno}}
Koji bi nacin kriptoanalize koristili za napade na "One-time pad" nacin kriptovanja ? Da li je One-time pad otporan na te algoritme, ukoliko ne koji ima ?
Odgovor: <span class="spoiler" data-solution="text">ne moze nista da probije one-time pad</span>

=== 2. zadatak ===
Hill alogitam 2x2 matrica

=== 3. zadatak ===
Primenjuje se Miler-Rabinov algoritam za utvrđivanje da li je dat broj <math>n = 91</math> prost. Dati rezultat algoritma za dati slučajno određen broj <math>a</math>.
<div class="abc-list">
<ol>
<li data-solution="single">
<math>a = 9</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* <span class="solution">Možda prost</span>
* Nije prost
* Ne znam
</li>
<li data-solution="single">
<math>a = 11</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* <span class="solution">Nije prost</span>
* Možda prost
* Ne znam
</li>
</ol>
</div>

=== 4. zadatak ===
{{delimično rešeno}}
Branko salje broj svoje kreditne kartice, ali da bi ga zastitio odlucio je da ga sifruje, prvo sa "rail fence" u 4 reda, potom monoalfabetski sa kljucem 1597302846, potom ponovo sa "rail fence" u 4 reda. Originalni broj kartice je
4812 2391 0028 5722.
Dobijeni broj kartice je: <span class="spoiler" data-solution="text">nerešeno</span>

=== 5. zadatak ===
{{delimično rešeno}}
SAES posle prve iteracije.

== 2. grupa ==
=== 1. zadatak ===
{{delimično rešeno}}
Objasniti šta je poznato pri ''known plaintext'' metodi kriptoanalize. Da li je ''Hill''-ov algoritam otporan na known plaintext napade?

=== 2. zadatak ===
Ana želi da pošalje Marku poruku koristeći ''Vigenère'' šifru sa ''autokey'' poboljšanjem.
Ana je pomoću RSA algoritma poslala Marku šifrovan ključ za ''Vigenère'' algoritam koji glasi <math>C = \mathtt{432899}</math>.
Svaka cifra iz šifre se mapira u slovo pod tim rednim brojem (npr. 123=ABC).
Izabrali su <math>n = \mathtt{1003883}</math>, dok je Anin privatni ključ <math>d = \mathtt{2003}</math>.
Marko je primio poruku KNHFMMDVIMMPLZDU.

<div class="abc-list">
<ol>
<li>Ključ za ''Vigenère'' je : <span class="spoiler" data-solution="text">HFCAEI</span></li>
<li>Poruka koju je Ana poslala je : <span class="spoiler" data-solution="text">DIFFIEANDHELLMAN</span></li>
<li data-solution="single">
''Vigenère'' algoritam sa ''autokey'' poboljšanjem menja učestalost pojavljivanja slova u šifrovanoj poruci. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* Ne
* <span class="solution">Da</span>
* Ne znam
</li>
</ol>
</div>

=== 3. zadatak ===
Primenjuje se Miler-Rabinov algoritam za utvrđivanje da li je dat broj <math>n = 247</math> prost. Dati rezultat algoritma za dati slučajno određen broj <math>a</math>.
<div class="abc-list">
<ol>
<li data-solution="single">
<math>a = 12</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* <span class="solution">Možda prost</span>
* Nije prost
* Ne znam
</li>
<li data-solution="single">
<math>a = 15</math>. (netačan odgovor na ovo pitanje nosi -1 poen, odgovor "Ne znam" donosi 0 poena):
* <span class="solution">Nije prost</span>
* Možda prost
* Ne znam
</li>
</ol>
</div>

=== 4. zadatak ===
{{delimično rešeno}}
Složeni algoritam šifrovanja se koristi za šifrovanje nečijeg broja kreditne kartice. Broj kreditne kartice koji treba šifrovati je: '''4812 2391 0028 5722'''.
Složeni algoritam se sastoji od:
# ''Row Transposition'' algoritma za dešifrovanje sa ključem (4,3,2,1)
# Cezarovom šifrom sa pomerajem 3
# ''Row Transposition'' algoritma za šifrovanje sa ključem (4,3,2,1)

Šifrovan broj kreditne kartice glasi: <span class="spoiler" data-solution="text">nerešeno</span>

=== 5. zadatak ===
{{delimično rešeno}}
SAES algoritam se koristi za šifrovanje bloka '''2468h''' sa ključem '''5B9Fh'''. Parametri algoritma su: '''<math>RCON(1) = \mathtt{80h}, RCON(2) = \mathtt{30h} </math>'''. Nesvodljivi polinom '''0011b'''.
{| class="wikitable"
|+ S-Box tabela
!
! 00b !! 01b !! 10b !! 11b
|-
! 00b
| 9h || 4h || Ah || Bh
|-
! 01b
| Dh || 1h || 8h || 5h
|-
! 10b
| 6h || 2h || 0h || 3h
|-
! 11b
| Ch || Eh || Fh || 7h
|}
{| class="wikitable"
|+ MixColumns
| 1 || 4
|-
| 4 || 1
|}

<div class="abc-list">
<ol>
<li>Ključ za prvu rundu <math>K_1</math> glasi : <span class="spoiler" data-solution="text">nerešeno</span></li>
<li>Stanje pred MixColumns korak : <span class="spoiler" data-solution="text">nerešeno</span></li>
<li>Stanje na kraju prve runde : <span class="spoiler" data-solution="text">nerešeno</span></li>
</ol>
</div>

[[Категорија:Рокови]]
[[Категорија:Заштита података]]

ОО1/К1 2022

2022-12-05T06:27:07Z

IvnSvc: /* 4. zadatak */ Залутали таг

{{tocright}}
{{rešenja}}

== 1. zadatak ==
Šta može da stoji umesto XXX da bi se kod pokretao uspešno?
<syntaxhighlight lang="cpp">
int g(int i) { return i; }

int main() {
int a = 5;
decltype (XXX) b = 5;
}

</syntaxhighlight>
<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="cpp" inline>int;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">a+1;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">a++;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">g(g(4));</syntaxhighlight>
</div>

== 2. zadatak ==
Šta se ispisuje prilikom pokretanja sledećeg koda?
<syntaxhighlight lang="cpp">
class X {
public:
X(int p) : z(++p), y(++p), x(++p) {cout << x << y << z;}
private:
int x, y, z;
}

int main() {
X x(3);
}
</syntaxhighlight>
'''Odgovor:''' <span class="spoiler" data-solution="text">456</span>

'''Objašnjenje:''' <span class="spoiler" data-solution="explanation">Inicijalizacija atributa se vrši redosledom navođenja u klasi, bez obzira na redosled u listi inicijalizatora.</span>

== 3. zadatak ==
Šta ispisuje sledeći kod na programskom jeziku C++:
<syntaxhighlight lang="cpp">
class A {
public:
~A() {cout << "A";}
}

class B {
public:
~B() {cout << "B";}
}

class C {
A a;
B b;
public:
~C() {cout << "C";}
}

int main() {
delete new C();
}
</syntaxhighlight>
'''Odgovor:''' <span class="spoiler" data-solution="text">CBA</span>

'''Objašnjenje:''' <span class="spoiler" data-solution="explanation">Redosled pozivanja destruktora je obrnut od redosleda pozivanja konstruktora.</span>

== 4. zadatak ==
Šta važi za prijateljske funkcije?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Prijateljska funkcija može biti metod neke druge klase.</span>
# Prijateljska funkcija deklarisana u javnom odeljku nema pristup privatnim atributima.
# Da bi funkcija bila prijateljska ona mora da bude definisana unutar klase.
# <span class="solution">Prijateljska funkcija definisana unutar klase je podrazumevano <code>inline</code>.</span>
</div>

== 5. zadatak ==
Koje aspekte je po Stroustrupu trebalo da ispuni C++:
<div class="abc-list" data-solution="multiple">
# Da bude brži od C-a
# Da bude prenosiv
# <span class="solution">Da bude dovoljno blizak mašini</span>
# <span class="solution">Da bude dovoljno blizak problemu</span>
# Da se koristi za programiranje intefejsa
</div>

== 6. zadatak ==
Šta važi za prava pristupa:
<div class="abc-list" data-solution="multiple">
# <span class="solution">U strukturi je podrazumevan <code>public</code> odeljak.</span>
# Privatni nestatički metod ima pravo pristupa samo privatnim atributima.
# Postoji samo po jedan <code>public</code>, <code>private</code> i <code>protected</code> odeljak.
# <span class="solution">U klasi je podrazumevan <code>private</code> odeljak.</span>
</div>

== 7. zadatak ==
Šta je validna operacija nad sledećim nizom?
<syntaxhighlight lang="cpp">
int niz[] = {1,2,3,4};
</syntaxhighlight>
<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="cpp" inline class="solution">niz[0] = 1;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">int x = niz[1];</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline >niz++;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">int *novi_niz = niz;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline >int *niz = new int[4];</syntaxhighlight>
</div>

== 8. zadatak ==
Sa kojim modifikatorima mogu da se pozivaju funkcije za promenljive objekte?
<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="cpp" inline class="solution">const</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">const volatile</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline >this</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">volatile</syntaxhighlight>
# <span class="solution" >bez modifikatora</span>
</div>

== 9. zadatak ==
Šta može da stoji umesto ??? da bi kod bio ispravan?
<syntaxhighlight lang="cpp">
#include <iostream>

int& f(int& i, const int& j);

const int& g(int &i) { return i; }

int main() {
int a = 3;
int* p = &a;
const int *pk = &a;

???

return 0;
}
</syntaxhighlight>
<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="cpp" inline >f(a + 1, a);</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">f(a, a);</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline >f(*pk, a);</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">f(a, g(a));</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution" >f(a, *p);</syntaxhighlight>
</div>

== 10. zadatak ==
Koje od sledećih deklaracija funkcija su ispravne?
<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="cpp" inline >int f(int a = 1, int b, int c);</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">int f(int a = 1, int b = 2, int c = 3);</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline >int f(int a = 1, int b = 2, int c);</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">int f(int a, int b = 2, int c = 3); </syntaxhighlight>
# <syntaxhighlight lang="cpp" inline>int f(int a, int b = 2, int c);</syntaxhighlight>
</div>

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

КДП/Јун 2022

2022-07-25T02:41:25Z

IvnSvc: /* 3. задатак */ скинут нерешени таг

{{tocright}}
'''Испит у јунском испитном року 2022. године''' одржан је 14. јуна. Поставка овог рока још увек није доступна са странице предмета.

== 1. задатак ==
{{делимично решено}}
=== Поставка ===
Објасните шта је ''At-Most-Once-Property''. Објасните зашто, када је испуњена та особина, критична референца има особине атомске акције. Дати два примера у којима су по два процеса.

=== Решење ===

== 2. задатак ==
{{делимично решено}}
=== Поставка ===
Постоје три особе међу којима треба изабрати једну (''The Odd Person Wins Game''). Свака од тих особа поседује новчић који има две стране. Избор особе се одиграва тако што свака особа независно баца свој новчић. Уколико постоји особа којој је новчић пао на другу страну у односу на преостале особе, онда се та особа изабира. Уколико све особе имају исто постављен новчић, поступак се понавља све док се не изабере једна. Особе након сваког бацања морају да знају да ли су изабране или не или се поступак понавља. Користећи семафоре написати програм који описује понашање особе. Ниједној особи не треба давати предност на основу њиховог идентификатора.

=== Решење ===

== 3. задатак ==
=== Поставка ===
Монитор треба да регулише распоред уласка пацијената на преглед код једног лекара. Сваки регуларно заказани пацијент је пре приступања том монитору добио један од 12 хронолошки поређаних полусатних интервала за тај дан (прављење распореда није део задатка). Пацијент када дође на преглед (не мора да буде тачан) позива мониторску процедуру <code>želim_da_se_pregledam</code> и том приликом доставља ID и почетак полусатног интервала у коме је њему заказан преглед. Ако је лекар заузет, пацијенти на чекању ће се поређати на основу хронолошког редоследа у распореду за тај дан. Лекар позива мониторску процедуру <code>sledeći</code>, која враћа идентификатор следећег пацијента, када жели да прегледа следећег пацијента. Ако нема пацијената у том случају, лекар се поствља у стање чекања из кога излази када наиђе први пацијент. Написати овакав монитор користећи дисциплину ''Signal and Wait'' и условне променљиве код којих нема приоритетних редова чекања. Монитор не треба да садржи синхронизацију везану за крај прегледа.

=== Решење ===
<syntaxhighlight lang="java">

// pretpostavka da je ID 0-11
class Monitor{
private Condition[] awaitPatient[12], awaitDoctor;
private boolean[] patientChecked[12]; // da li je pacijent pregledan, potreban zbog signal&wait
private PriorityQueue<<int,int>> pq; // prioritetni red slot,ID, sortiran po slotu

public synchornized void zelim_da_se_pregledam(int ID, int slot){
pq.add(slot,ID);
awaitDoctor.signal();
// potrebno jer signal&wait predaje kontrolu pa je pacijent u medjuvremenu mozda pregledan
if(patientChecked[ID]==false) awaitPatient[ID].wait();
}

public synchronized int sledeci(){
if(pq.size()==0) awaitDoctor.wait();
int id = pq.pop().first;
pq.remove();
patientChecked[id] = true;
awaitPatient[id].signal()
return id;
}

</syntaxhighlight>

== 4. задатак ==
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарно постављене једна иза друге. Камион заузима три, аутобус две, а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у којем чекају у реду, док на трајекту има места. Када наредно возило у реду за трајект нема места да се укрца или када је трајект пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од редоследа у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи регионе написати програм који решава овај проблем.

=== Решење ===
<syntaxhighlight lang="cpp">

struct Trajekt{
int cap = N;
int cur=0, next=0, ticketIn = 0, ticketOut = 0;
boolean ukrcavanje = false, iskrcavanje = false
}

Trajekt t;

void vozilo(int space){
int myTicketIn, myTicketOut;
regiot(t){
myTicketIn = t.ticketIn++;
await(t.ukrcavanje+=true && t.ticketIn==myTicketIn)
if(t.cap - t.curr < space){
// ukoliko nema mesta za mene, posalji trajekt pa sacekaj da se vrati
t.ukrcavanje = false;
await(t.ukrcavanje==true)
}
t.curr+=space;
myTicketOut = ++t.ticketOut;
t.next++;
if(t.curr==t.cap)
t.ukrcavanje=false;
}
// prevozimo se
region(t){
await(t.iskrcavanje==true && myTicketOut==t.ticketOut)
if(--t.ticketOut == 0)
// ukoliko sam poslednji, posalji trajekt nazad
t.iskrcavanje = false
}
}

void trajekt(){
while(1){
region(t){
t.ukrcavanje = true
await(t.ukrcavanje == false)
}
preveziVozila()
region(t){
t.ukrcavanje = true
await(t.ukrcavanje == false)
}
vratiSeNazad()
}
}
</syntaxhighlight>

== 5. задатак ==
=== Поставка ===
Користећи синхрону размену порука написати дистрибуирано решење за проблем филозофа који ручавају (''The Dining Philosophers Problem''). Код дистрибуираног решења процеси филозофи комуницирају само са процесима виљушкама и процеси виљушке комуницирају само са процесима филозофима.

=== Решење ===
<syntaxhighlight lang="cpp">
void philosopher(int ID, chan<string> release, chan<char> forkL, chan<char> forkR) {
while (true) {
// Филозофирамо
if (ID % 2 == 0) {
forkL.send('R');
forkR.send('L');
} else {
forkR.send('L');
forkL.send('R');
}
// Једемо
release.receive();
release.receive();
}
}

void fork(chan<char> acquire, chan<string> philL, chan<string> philR) {
while (true) {
char dir = acquire.receive();
if (dir == 'L') {
philL.send("release");
} else {
philR.send("release");
}
}
}
</syntaxhighlight>

== 6. задатак ==
=== Поставка ===
Постоји P произвођача и C потрошача који деле заједнички бафер капацитета B (''Atomic broadcast problem''). Произвођачи генеришу производ по производ на које чекају свих C потрошача. Сваки потрошач мора да прими производе у тачно оном редоследу у коме су произведени, мада различити потрошачи могу у исто време да узимају различите производе. Решити проблем користећи ''C-Linda'', тако да се ни у ком тренутку у заједничком простору не нађе више од B производа.

=== Решење ===
Тагови коришћени у овој имплементацији су:
* <code>buffer empty</code>: постоји места да произвођач убацује у бафер
* <code>buffer full</code>: постоје производи у баферу које потрошачи могу да читају
* <code>product</code>: производ са одређеним индексом у низу
* <code>size</code>: величина бафера
* <code>producer index</code>: индекс у баферу до ког су произвођачи стигли са попуњавањем
* <code>consumer count</code>: број потрошача који је преостао да прочита производ на одређеном индексу
<syntaxhighlight lang="cpp">
const int P = 100;
const int C = 100;
const int B = 100;

struct Product {};
Product produce();
void consume(Product p);

int producer() {
while (true) {
Product p = produce();
in("buffer empty");
int index;
in("producer index", &index);
out("product", index, p);
out("consumer count", index, C);
out("producer index", (index + 1) % B);
int size;
in("size", &size);
if (size == 0) {
out("buffer full");
}
out("size", ++size);
if (size < B) {
out("buffer empty");
}
}
}

void consumer() {
int index = 0;
while (true) {
in("buffer full");
Product p;
int count;
in("consumer count", index, &count);
if (count == 1) {
in("product", index, &p);
int size;
in("size", &size);
if (size == B) {
out("buffer empty");
}
out("size", --size);
if (size > 0) {
out("buffer full");
}
} else {
rd("product", index, &p);
out("consumer count", index, count-1);
out("buffer full");
}
index = (index + 1) % B;
consume(p);
}
}

void initialize() {
out("buffer empty");
out("size", 0);
out("producer index", 0);
}
</syntaxhighlight>

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

КДП/Јун 2022

2022-07-25T02:41:05Z

IvnSvc: /* 4. задатак */ скинут нерешени таг

{{tocright}}
'''Испит у јунском испитном року 2022. године''' одржан је 14. јуна. Поставка овог рока још увек није доступна са странице предмета.

== 1. задатак ==
{{делимично решено}}
=== Поставка ===
Објасните шта је ''At-Most-Once-Property''. Објасните зашто, када је испуњена та особина, критична референца има особине атомске акције. Дати два примера у којима су по два процеса.

=== Решење ===

== 2. задатак ==
{{делимично решено}}
=== Поставка ===
Постоје три особе међу којима треба изабрати једну (''The Odd Person Wins Game''). Свака од тих особа поседује новчић који има две стране. Избор особе се одиграва тако што свака особа независно баца свој новчић. Уколико постоји особа којој је новчић пао на другу страну у односу на преостале особе, онда се та особа изабира. Уколико све особе имају исто постављен новчић, поступак се понавља све док се не изабере једна. Особе након сваког бацања морају да знају да ли су изабране или не или се поступак понавља. Користећи семафоре написати програм који описује понашање особе. Ниједној особи не треба давати предност на основу њиховог идентификатора.

=== Решење ===

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Монитор треба да регулише распоред уласка пацијената на преглед код једног лекара. Сваки регуларно заказани пацијент је пре приступања том монитору добио један од 12 хронолошки поређаних полусатних интервала за тај дан (прављење распореда није део задатка). Пацијент када дође на преглед (не мора да буде тачан) позива мониторску процедуру <code>želim_da_se_pregledam</code> и том приликом доставља ID и почетак полусатног интервала у коме је њему заказан преглед. Ако је лекар заузет, пацијенти на чекању ће се поређати на основу хронолошког редоследа у распореду за тај дан. Лекар позива мониторску процедуру <code>sledeći</code>, која враћа идентификатор следећег пацијента, када жели да прегледа следећег пацијента. Ако нема пацијената у том случају, лекар се поствља у стање чекања из кога излази када наиђе први пацијент. Написати овакав монитор користећи дисциплину ''Signal and Wait'' и условне променљиве код којих нема приоритетних редова чекања. Монитор не треба да садржи синхронизацију везану за крај прегледа.

=== Решење ===
<syntaxhighlight lang="java">

// pretpostavka da je ID 0-11
class Monitor{
private Condition[] awaitPatient[12], awaitDoctor;
private boolean[] patientChecked[12]; // da li je pacijent pregledan, potreban zbog signal&wait
private PriorityQueue<<int,int>> pq; // prioritetni red slot,ID, sortiran po slotu

public synchornized void zelim_da_se_pregledam(int ID, int slot){
pq.add(slot,ID);
awaitDoctor.signal();
// potrebno jer signal&wait predaje kontrolu pa je pacijent u medjuvremenu mozda pregledan
if(patientChecked[ID]==false) awaitPatient[ID].wait();
}

public synchronized int sledeci(){
if(pq.size()==0) awaitDoctor.wait();
int id = pq.pop().first;
pq.remove();
patientChecked[id] = true;
awaitPatient[id].signal()
return id;
}

</syntaxhighlight>

== 4. задатак ==
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарно постављене једна иза друге. Камион заузима три, аутобус две, а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у којем чекају у реду, док на трајекту има места. Када наредно возило у реду за трајект нема места да се укрца или када је трајект пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од редоследа у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи регионе написати програм који решава овај проблем.

=== Решење ===
<syntaxhighlight lang="cpp">

struct Trajekt{
int cap = N;
int cur=0, next=0, ticketIn = 0, ticketOut = 0;
boolean ukrcavanje = false, iskrcavanje = false
}

Trajekt t;

void vozilo(int space){
int myTicketIn, myTicketOut;
regiot(t){
myTicketIn = t.ticketIn++;
await(t.ukrcavanje+=true && t.ticketIn==myTicketIn)
if(t.cap - t.curr < space){
// ukoliko nema mesta za mene, posalji trajekt pa sacekaj da se vrati
t.ukrcavanje = false;
await(t.ukrcavanje==true)
}
t.curr+=space;
myTicketOut = ++t.ticketOut;
t.next++;
if(t.curr==t.cap)
t.ukrcavanje=false;
}
// prevozimo se
region(t){
await(t.iskrcavanje==true && myTicketOut==t.ticketOut)
if(--t.ticketOut == 0)
// ukoliko sam poslednji, posalji trajekt nazad
t.iskrcavanje = false
}
}

void trajekt(){
while(1){
region(t){
t.ukrcavanje = true
await(t.ukrcavanje == false)
}
preveziVozila()
region(t){
t.ukrcavanje = true
await(t.ukrcavanje == false)
}
vratiSeNazad()
}
}
</syntaxhighlight>

== 5. задатак ==
=== Поставка ===
Користећи синхрону размену порука написати дистрибуирано решење за проблем филозофа који ручавају (''The Dining Philosophers Problem''). Код дистрибуираног решења процеси филозофи комуницирају само са процесима виљушкама и процеси виљушке комуницирају само са процесима филозофима.

=== Решење ===
<syntaxhighlight lang="cpp">
void philosopher(int ID, chan<string> release, chan<char> forkL, chan<char> forkR) {
while (true) {
// Филозофирамо
if (ID % 2 == 0) {
forkL.send('R');
forkR.send('L');
} else {
forkR.send('L');
forkL.send('R');
}
// Једемо
release.receive();
release.receive();
}
}

void fork(chan<char> acquire, chan<string> philL, chan<string> philR) {
while (true) {
char dir = acquire.receive();
if (dir == 'L') {
philL.send("release");
} else {
philR.send("release");
}
}
}
</syntaxhighlight>

== 6. задатак ==
=== Поставка ===
Постоји P произвођача и C потрошача који деле заједнички бафер капацитета B (''Atomic broadcast problem''). Произвођачи генеришу производ по производ на које чекају свих C потрошача. Сваки потрошач мора да прими производе у тачно оном редоследу у коме су произведени, мада различити потрошачи могу у исто време да узимају различите производе. Решити проблем користећи ''C-Linda'', тако да се ни у ком тренутку у заједничком простору не нађе више од B производа.

=== Решење ===
Тагови коришћени у овој имплементацији су:
* <code>buffer empty</code>: постоји места да произвођач убацује у бафер
* <code>buffer full</code>: постоје производи у баферу које потрошачи могу да читају
* <code>product</code>: производ са одређеним индексом у низу
* <code>size</code>: величина бафера
* <code>producer index</code>: индекс у баферу до ког су произвођачи стигли са попуњавањем
* <code>consumer count</code>: број потрошача који је преостао да прочита производ на одређеном индексу
<syntaxhighlight lang="cpp">
const int P = 100;
const int C = 100;
const int B = 100;

struct Product {};
Product produce();
void consume(Product p);

int producer() {
while (true) {
Product p = produce();
in("buffer empty");
int index;
in("producer index", &index);
out("product", index, p);
out("consumer count", index, C);
out("producer index", (index + 1) % B);
int size;
in("size", &size);
if (size == 0) {
out("buffer full");
}
out("size", ++size);
if (size < B) {
out("buffer empty");
}
}
}

void consumer() {
int index = 0;
while (true) {
in("buffer full");
Product p;
int count;
in("consumer count", index, &count);
if (count == 1) {
in("product", index, &p);
int size;
in("size", &size);
if (size == B) {
out("buffer empty");
}
out("size", --size);
if (size > 0) {
out("buffer full");
}
} else {
rd("product", index, &p);
out("consumer count", index, count-1);
out("buffer full");
}
index = (index + 1) % B;
consume(p);
}
}

void initialize() {
out("buffer empty");
out("size", 0);
out("producer index", 0);
}
</syntaxhighlight>

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

КДП/Јун 2022

2022-07-25T02:40:13Z

IvnSvc: /* Решење */

{{tocright}}
'''Испит у јунском испитном року 2022. године''' одржан је 14. јуна. Поставка овог рока још увек није доступна са странице предмета.

== 1. задатак ==
{{делимично решено}}
=== Поставка ===
Објасните шта је ''At-Most-Once-Property''. Објасните зашто, када је испуњена та особина, критична референца има особине атомске акције. Дати два примера у којима су по два процеса.

=== Решење ===

== 2. задатак ==
{{делимично решено}}
=== Поставка ===
Постоје три особе међу којима треба изабрати једну (''The Odd Person Wins Game''). Свака од тих особа поседује новчић који има две стране. Избор особе се одиграва тако што свака особа независно баца свој новчић. Уколико постоји особа којој је новчић пао на другу страну у односу на преостале особе, онда се та особа изабира. Уколико све особе имају исто постављен новчић, поступак се понавља све док се не изабере једна. Особе након сваког бацања морају да знају да ли су изабране или не или се поступак понавља. Користећи семафоре написати програм који описује понашање особе. Ниједној особи не треба давати предност на основу њиховог идентификатора.

=== Решење ===

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Монитор треба да регулише распоред уласка пацијената на преглед код једног лекара. Сваки регуларно заказани пацијент је пре приступања том монитору добио један од 12 хронолошки поређаних полусатних интервала за тај дан (прављење распореда није део задатка). Пацијент када дође на преглед (не мора да буде тачан) позива мониторску процедуру <code>želim_da_se_pregledam</code> и том приликом доставља ID и почетак полусатног интервала у коме је њему заказан преглед. Ако је лекар заузет, пацијенти на чекању ће се поређати на основу хронолошког редоследа у распореду за тај дан. Лекар позива мониторску процедуру <code>sledeći</code>, која враћа идентификатор следећег пацијента, када жели да прегледа следећег пацијента. Ако нема пацијената у том случају, лекар се поствља у стање чекања из кога излази када наиђе први пацијент. Написати овакав монитор користећи дисциплину ''Signal and Wait'' и условне променљиве код којих нема приоритетних редова чекања. Монитор не треба да садржи синхронизацију везану за крај прегледа.

=== Решење ===
<syntaxhighlight lang="java">

// pretpostavka da je ID 0-11
class Monitor{
private Condition[] awaitPatient[12], awaitDoctor;
private boolean[] patientChecked[12]; // da li je pacijent pregledan, potreban zbog signal&wait
private PriorityQueue<<int,int>> pq; // prioritetni red slot,ID, sortiran po slotu

public synchornized void zelim_da_se_pregledam(int ID, int slot){
pq.add(slot,ID);
awaitDoctor.signal();
// potrebno jer signal&wait predaje kontrolu pa je pacijent u medjuvremenu mozda pregledan
if(patientChecked[ID]==false) awaitPatient[ID].wait();
}

public synchronized int sledeci(){
if(pq.size()==0) awaitDoctor.wait();
int id = pq.pop().first;
pq.remove();
patientChecked[id] = true;
awaitPatient[id].signal()
return id;
}

</syntaxhighlight>

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарно постављене једна иза друге. Камион заузима три, аутобус две, а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у којем чекају у реду, док на трајекту има места. Када наредно возило у реду за трајект нема места да се укрца или када је трајект пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од редоследа у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи регионе написати програм који решава овај проблем.

=== Решење ===
<syntaxhighlight lang="cpp">

struct Trajekt{
int cap = N;
int cur=0, next=0, ticketIn = 0, ticketOut = 0;
boolean ukrcavanje = false, iskrcavanje = false
}

Trajekt t;

void vozilo(int space){
int myTicketIn, myTicketOut;
regiot(t){
myTicketIn = t.ticketIn++;
await(t.ukrcavanje+=true && t.ticketIn==myTicketIn)
if(t.cap - t.curr < space){
// ukoliko nema mesta za mene, posalji trajekt pa sacekaj da se vrati
t.ukrcavanje = false;
await(t.ukrcavanje==true)
}
t.curr+=space;
myTicketOut = ++t.ticketOut;
t.next++;
if(t.curr==t.cap)
t.ukrcavanje=false;
}
// prevozimo se
region(t){
await(t.iskrcavanje==true && myTicketOut==t.ticketOut)
if(--t.ticketOut == 0)
// ukoliko sam poslednji, posalji trajekt nazad
t.iskrcavanje = false
}
}

void trajekt(){
while(1){
region(t){
t.ukrcavanje = true
await(t.ukrcavanje == false)
}
preveziVozila()
region(t){
t.ukrcavanje = true
await(t.ukrcavanje == false)
}
vratiSeNazad()
}
}
</syntaxhighlight>

== 5. задатак ==
=== Поставка ===
Користећи синхрону размену порука написати дистрибуирано решење за проблем филозофа који ручавају (''The Dining Philosophers Problem''). Код дистрибуираног решења процеси филозофи комуницирају само са процесима виљушкама и процеси виљушке комуницирају само са процесима филозофима.

=== Решење ===
<syntaxhighlight lang="cpp">
void philosopher(int ID, chan<string> release, chan<char> forkL, chan<char> forkR) {
while (true) {
// Филозофирамо
if (ID % 2 == 0) {
forkL.send('R');
forkR.send('L');
} else {
forkR.send('L');
forkL.send('R');
}
// Једемо
release.receive();
release.receive();
}
}

void fork(chan<char> acquire, chan<string> philL, chan<string> philR) {
while (true) {
char dir = acquire.receive();
if (dir == 'L') {
philL.send("release");
} else {
philR.send("release");
}
}
}
</syntaxhighlight>

== 6. задатак ==
=== Поставка ===
Постоји P произвођача и C потрошача који деле заједнички бафер капацитета B (''Atomic broadcast problem''). Произвођачи генеришу производ по производ на које чекају свих C потрошача. Сваки потрошач мора да прими производе у тачно оном редоследу у коме су произведени, мада различити потрошачи могу у исто време да узимају различите производе. Решити проблем користећи ''C-Linda'', тако да се ни у ком тренутку у заједничком простору не нађе више од B производа.

=== Решење ===
Тагови коришћени у овој имплементацији су:
* <code>buffer empty</code>: постоји места да произвођач убацује у бафер
* <code>buffer full</code>: постоје производи у баферу које потрошачи могу да читају
* <code>product</code>: производ са одређеним индексом у низу
* <code>size</code>: величина бафера
* <code>producer index</code>: индекс у баферу до ког су произвођачи стигли са попуњавањем
* <code>consumer count</code>: број потрошача који је преостао да прочита производ на одређеном индексу
<syntaxhighlight lang="cpp">
const int P = 100;
const int C = 100;
const int B = 100;

struct Product {};
Product produce();
void consume(Product p);

int producer() {
while (true) {
Product p = produce();
in("buffer empty");
int index;
in("producer index", &index);
out("product", index, p);
out("consumer count", index, C);
out("producer index", (index + 1) % B);
int size;
in("size", &size);
if (size == 0) {
out("buffer full");
}
out("size", ++size);
if (size < B) {
out("buffer empty");
}
}
}

void consumer() {
int index = 0;
while (true) {
in("buffer full");
Product p;
int count;
in("consumer count", index, &count);
if (count == 1) {
in("product", index, &p);
int size;
in("size", &size);
if (size == B) {
out("buffer empty");
}
out("size", --size);
if (size > 0) {
out("buffer full");
}
} else {
rd("product", index, &p);
out("consumer count", index, count-1);
out("buffer full");
}
index = (index + 1) % B;
consume(p);
}
}

void initialize() {
out("buffer empty");
out("size", 0);
out("producer index", 0);
}
</syntaxhighlight>

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

КДП/Јун 2022

2022-07-25T02:30:29Z

IvnSvc: /* Решење */

{{tocright}}
'''Испит у јунском испитном року 2022. године''' одржан је 14. јуна. Поставка овог рока још увек није доступна са странице предмета.

== 1. задатак ==
{{делимично решено}}
=== Поставка ===
Објасните шта је ''At-Most-Once-Property''. Објасните зашто, када је испуњена та особина, критична референца има особине атомске акције. Дати два примера у којима су по два процеса.

=== Решење ===

== 2. задатак ==
{{делимично решено}}
=== Поставка ===
Постоје три особе међу којима треба изабрати једну (''The Odd Person Wins Game''). Свака од тих особа поседује новчић који има две стране. Избор особе се одиграва тако што свака особа независно баца свој новчић. Уколико постоји особа којој је новчић пао на другу страну у односу на преостале особе, онда се та особа изабира. Уколико све особе имају исто постављен новчић, поступак се понавља све док се не изабере једна. Особе након сваког бацања морају да знају да ли су изабране или не или се поступак понавља. Користећи семафоре написати програм који описује понашање особе. Ниједној особи не треба давати предност на основу њиховог идентификатора.

=== Решење ===

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Монитор треба да регулише распоред уласка пацијената на преглед код једног лекара. Сваки регуларно заказани пацијент је пре приступања том монитору добио један од 12 хронолошки поређаних полусатних интервала за тај дан (прављење распореда није део задатка). Пацијент када дође на преглед (не мора да буде тачан) позива мониторску процедуру <code>želim_da_se_pregledam</code> и том приликом доставља ID и почетак полусатног интервала у коме је њему заказан преглед. Ако је лекар заузет, пацијенти на чекању ће се поређати на основу хронолошког редоследа у распореду за тај дан. Лекар позива мониторску процедуру <code>sledeći</code>, која враћа идентификатор следећег пацијента, када жели да прегледа следећег пацијента. Ако нема пацијената у том случају, лекар се поствља у стање чекања из кога излази када наиђе први пацијент. Написати овакав монитор користећи дисциплину ''Signal and Wait'' и условне променљиве код којих нема приоритетних редова чекања. Монитор не треба да садржи синхронизацију везану за крај прегледа.

=== Решење ===

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарно постављене једна иза друге. Камион заузима три, аутобус две, а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у којем чекају у реду, док на трајекту има места. Када наредно возило у реду за трајект нема места да се укрца или када је трајект пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од редоследа у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи регионе написати програм који решава овај проблем.

=== Решење ===
<syntaxhighlight lang="cpp">

struct Trajekt{
int cap = N;
int cur=0, next=0, ticketIn = 0, ticketOut = 0;
boolean ukrcavanje = false, iskrcavanje = false
}

Trajekt t;

void vozilo(int space){
int myTicketIn, myTicketOut;
regiot(t){
myTicketIn = t.ticketIn++;
await(t.ukrcavanje+=true && t.ticketIn==myTicketIn)
if(t.cap - t.curr < space){
// ukoliko nema mesta za mene, posalji trajekt pa sacekaj da se vrati
t.ukrcavanje = false;
await(t.ukrcavanje==true)
}
t.curr+=space;
myTicketOut = ++t.ticketOut;
t.next++;
if(t.curr==t.cap)
t.ukrcavanje=false;
}
// prevozimo se
region(t){
await(t.iskrcavanje==true && myTicketOut==t.ticketOut)
if(--t.ticketOut == 0)
// ukoliko sam poslednji, posalji trajekt nazad
t.iskrcavanje = false
}
}

void trajekt(){
while(1){
region(t){
t.ukrcavanje = true
await(t.ukrcavanje == false)
}
preveziVozila()
region(t){
t.ukrcavanje = true
await(t.ukrcavanje == false)
}
vratiSeNazad()
}
}
</syntaxhighlight>

== 5. задатак ==
=== Поставка ===
Користећи синхрону размену порука написати дистрибуирано решење за проблем филозофа који ручавају (''The Dining Philosophers Problem''). Код дистрибуираног решења процеси филозофи комуницирају само са процесима виљушкама и процеси виљушке комуницирају само са процесима филозофима.

=== Решење ===
<syntaxhighlight lang="cpp">
void philosopher(int ID, chan<string> release, chan<char> forkL, chan<char> forkR) {
while (true) {
// Филозофирамо
if (ID % 2 == 0) {
forkL.send('R');
forkR.send('L');
} else {
forkR.send('L');
forkL.send('R');
}
// Једемо
release.receive();
release.receive();
}
}

void fork(chan<char> acquire, chan<string> philL, chan<string> philR) {
while (true) {
char dir = acquire.receive();
if (dir == 'L') {
philL.send("release");
} else {
philR.send("release");
}
}
}
</syntaxhighlight>

== 6. задатак ==
=== Поставка ===
Постоји P произвођача и C потрошача који деле заједнички бафер капацитета B (''Atomic broadcast problem''). Произвођачи генеришу производ по производ на које чекају свих C потрошача. Сваки потрошач мора да прими производе у тачно оном редоследу у коме су произведени, мада различити потрошачи могу у исто време да узимају различите производе. Решити проблем користећи ''C-Linda'', тако да се ни у ком тренутку у заједничком простору не нађе више од B производа.

=== Решење ===
Тагови коришћени у овој имплементацији су:
* <code>buffer empty</code>: постоји места да произвођач убацује у бафер
* <code>buffer full</code>: постоје производи у баферу које потрошачи могу да читају
* <code>product</code>: производ са одређеним индексом у низу
* <code>size</code>: величина бафера
* <code>producer index</code>: индекс у баферу до ког су произвођачи стигли са попуњавањем
* <code>consumer count</code>: број потрошача који је преостао да прочита производ на одређеном индексу
<syntaxhighlight lang="cpp">
const int P = 100;
const int C = 100;
const int B = 100;

struct Product {};
Product produce();
void consume(Product p);

int producer() {
while (true) {
Product p = produce();
in("buffer empty");
int index;
in("producer index", &index);
out("product", index, p);
out("consumer count", index, C);
out("producer index", (index + 1) % B);
int size;
in("size", &size);
if (size == 0) {
out("buffer full");
}
out("size", ++size);
if (size < B) {
out("buffer empty");
}
}
}

void consumer() {
int index = 0;
while (true) {
in("buffer full");
Product p;
int count;
in("consumer count", index, &count);
if (count == 1) {
in("product", index, &p);
int size;
in("size", &size);
if (size == B) {
out("buffer empty");
}
out("size", --size);
if (size > 0) {
out("buffer full");
}
} else {
rd("product", index, &p);
out("consumer count", index, count-1);
out("buffer full");
}
index = (index + 1) % B;
consume(p);
}
}

void initialize() {
out("buffer empty");
out("size", 0);
out("producer index", 0);
}
</syntaxhighlight>

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

ИЕП/Јул 2022

2022-07-08T19:35:04Z

IvnSvc: Нерешен, тагови предмета и рока

{{tocright}}
{{нерешено}}
'''Испит у јулском року 2022. године''' одржан је 8. јула. Били су доступни материјали са предавања и трајао је 90 минута.
== Поставка ==
Хостинг компанија планира да инвестира у сервер салу коју ће користити за сопствене потребе, али и за изнајмљивање. Сервер сала ће садржати 800 сервера величине 1RU(рек јунита), распоређених у рек ормане. Конфигурација сервера се састоји од 2 процесора, 64GB DRAM по процесору и два HD од 600GB. Планирани начин рада целокупне опреме 24 сати дневно, 7 дана недељно. У сваком тренутку рада сервер сале , неопходно је да постоји дежуран инжењер. Познато је да цена kWh износи 0,05. Сервери у једном реку су повезани помоћу једног рек рутера, док су сви рекови повезани једним агрегационим рутером са 128 порта. За потребе сервер сале потребан је простор од 4 метара квадратних по реку. Изнајмљивање климатизованог простора плаћа се 35 по квадрату месечно. За повезивање сервер сале на интернет користи се интернет 10Gbs по цени 3000 месечно. Плата дежурног инжењера за осмочасовно радно време је 1500 месечно. За потребе отпремања сале, компанија је узела позајмицу са фиксном каматном ратом од 5% на годишњем нивоу. Период амортизације рачунарске опреме је 3, мрежне опреме 4, а расхладне опреме 7 година.
{| class="wikitable"
! Компонента
! Kaрактеристике
! Потрошња W
! Цена
|-
| Процесор
| 2.3GHz, 10 core
| 105
| 1200
|-
| DRAM
| 16GB, ECC
| 3.5
| 20
|-
| HD
| 600GB, 10krpm, AFR=0.5%
| 6.5
| 700
|-
| Рек рутер
| 48 порта, 2RU
| 500
| 2500
|-
| Агрег. рутер
| 128 порта, 2RU
| 3000
| 70000
|-
| Рек орман
| 42RU
| 0
| 900
|}

Колико износе капитална улагања за опремање описане сервер сале. Занемарити потребу за резерцним деловима ?

Колико износе оперативна улагања за месец дана планираног начина рада сервера ?
== ==
Ова компанија разматра издавање датог рачунарског центра клијентима из целог света за постављање њихових сајтова. Параметри приступа једном просечбном сајту су такви да се сваки посетилац задржава 8 минута у за то време посети 9 страница. Да би се учитала једна страница потребна су 24 захтева кастатичким елем, 10 ка динамичним. Код сваког динамичног потребна су у просеку 4 приступа бази података. Унутар вуртуелне машине на једном језгру време обраде статичких захтева износи 0.25мс и захтева 3GB, динамичких 0.4ms и захтева 5GB, a приступ бази траје 2.5ms и захтева 6GB меморије. Веб, апликативни и сервер БП се налазе на различитим виртуелним серверима. Број корисника током ноћи је 10 000 на сат, а током дана 30 000 на сат. Дан и ноћ су по 12 сати, сигурносни фактор је 2.5 .
Ова компанија наплаћује само сервере према приложеним конфигурацијама и ценовнику, док остале компоненте обезбеђује бесплатно својим клијентима.
{| class="wikitable"
! Тип
! Цена по сату
! Број језгара
! Меморија GB
|-
| Стандардна мала
| 0.085
| 1
| 4
|-
| Стандардна велика
| 0.340
| 4
| 8
|-
| Стандардна веома велика
| 0.680
| 6
| 15
|}
Предложити минималну хардверску конфугурацију за један овакав сајт. Уколико више њих задовољава услов одабрати најјефтинију

== ==
Сервери се могу користити да обављају функцију фајервола или балансера. Уколико се сервери користе као фајервол онда може обрадити 20000 захтева у секунди, а ако се користи као балансер онда се може обрадити 40000 захтева у секунди.

Колико минимално оваквих сајтова хостинг компанија треба да хостује да би се инвестиција исплатила ?

[[Категорија:ИЕП]]
[[Категорија:Рокови]]

ИЕП/Јул 2022

2022-07-08T19:33:27Z

IvnSvc: Јулски рок испитни део, К3

{{tocright}}
'''Испит у јулском року 2022. године''' одржан је 8. јула. Били су доступни материјали са предавања и трајао је 90 минута.
== Поставка ==
Хостинг компанија планира да инвестира у сервер салу коју ће користити за сопствене потребе, али и за изнајмљивање. Сервер сала ће садржати 800 сервера величине 1RU(рек јунита), распоређених у рек ормане. Конфигурација сервера се састоји од 2 процесора, 64GB DRAM по процесору и два HD од 600GB. Планирани начин рада целокупне опреме 24 сати дневно, 7 дана недељно. У сваком тренутку рада сервер сале , неопходно је да постоји дежуран инжењер. Познато је да цена kWh износи 0,05. Сервери у једном реку су повезани помоћу једног рек рутера, док су сви рекови повезани једним агрегационим рутером са 128 порта. За потребе сервер сале потребан је простор од 4 метара квадратних по реку. Изнајмљивање климатизованог простора плаћа се 35 по квадрату месечно. За повезивање сервер сале на интернет користи се интернет 10Gbs по цени 3000 месечно. Плата дежурног инжењера за осмочасовно радно време је 1500 месечно. За потребе отпремања сале, компанија је узела позајмицу са фиксном каматном ратом од 5% на годишњем нивоу. Период амортизације рачунарске опреме је 3, мрежне опреме 4, а расхладне опреме 7 година.
{| class="wikitable"
! Компонента
! Kaрактеристике
! Потрошња W
! Цена
|-
| Процесор
| 2.3GHz, 10 core
| 105
| 1200
|-
| DRAM
| 16GB, ECC
| 3.5
| 20
|-
| HD
| 600GB, 10krpm, AFR=0.5%
| 6.5
| 700
|-
| Рек рутер
| 48 порта, 2RU
| 500
| 2500
|-
| Агрег. рутер
| 128 порта, 2RU
| 3000
| 70000
|-
| Рек орман
| 42RU
| 0
| 900
|}

Колико износе капитална улагања за опремање описане сервер сале. Занемарити потребу за резерцним деловима ?

Колико износе оперативна улагања за месец дана планираног начина рада сервера ?
== ==
Ова компанија разматра издавање датог рачунарског центра клијентима из целог света за постављање њихових сајтова. Параметри приступа једном просечбном сајту су такви да се сваки посетилац задржава 8 минута у за то време посети 9 страница. Да би се учитала једна страница потребна су 24 захтева кастатичким елем, 10 ка динамичним. Код сваког динамичног потребна су у просеку 4 приступа бази података. Унутар вуртуелне машине на једном језгру време обраде статичких захтева износи 0.25мс и захтева 3GB, динамичких 0.4ms и захтева 5GB, a приступ бази траје 2.5ms и захтева 6GB меморије. Веб, апликативни и сервер БП се налазе на различитим виртуелним серверима. Број корисника током ноћи је 10 000 на сат, а током дана 30 000 на сат. Дан и ноћ су по 12 сати, сигурносни фактор је 2.5 .
Ова компанија наплаћује само сервере према приложеним конфигурацијама и ценовнику, док остале компоненте обезбеђује бесплатно својим клијентима.
{| class="wikitable"
! Тип
! Цена по сату
! Број језгара
! Меморија GB
|-
| Стандардна мала
| 0.085
| 1
| 4
|-
| Стандардна велика
| 0.340
| 4
| 8
|-
| Стандардна веома велика
| 0.680
| 6
| 15
|}
Предложити минималну хардверску конфугурацију за један овакав сајт. Уколико више њих задовољава услов одабрати најјефтинију

== ==
Сервери се могу користити да обављају функцију фајервола или балансера. Уколико се сервери користе као фајервол онда може обрадити 20000 захтева у секунди, а ако се користи као балансер онда се може обрадити 40000 захтева у секунди.

Колико минимално оваквих сајтова хостинг компанија треба да хостује да би се инвестиција исплатила

ОС2/Фебруар 2022

2022-02-23T10:42:18Z

IvnSvc: Добар линк до задатака на страници

{{tocright}}
[http://os.etf.rs/OS2/rokovi/2022/februar/Feb%202022.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Da li se kod algoritma raspoređivanja Multi-level Feedback Queue Scheduling procesu koji
je došao u red spremnih iz stanja suspenzije po pravilu smanjuje ili povećava prioritet? Zašto?
=== Rešenje ===
* Ставља се у виши(приоритетнији) ред.
* Зато што смо прошлом проценом преценили дужину његовог налета или смо потценили његову интерактивност. Зато стављамо процес у ред у којем ће краће чекати следећи налет, али ће имати и мање време налета

== 2. zadatak ==
=== Postavka ===
Na programskom jeziku Java realizovati monitor sa dve operacije, op1 i op2, pri čemu
monitor održava sledeću invarijantu: ukupan broj izvršavanja operacije op1 je uvek ne manji od
broja izvršavanja operacije op2. Zanemariti prekoračenje ograničenog opsega celobrojnih brojača.
=== Rešenje ===
<syntaxhighlight lang="java">

public class MyMonitor{
private int count;

public synchronized void op1(){
this.count+=1;
if(this.count == 1) notifyAll()
}
public synchronized void op2(){
while(--this.count <0)wait()
}
}

</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
U koju kategoriju međuprocesne komunikacije po pitanju imenovanja spada koncept
cevovoda (pipe)? Obrazložiti. Šta je osnovna motivacija za ovakav koncept?
=== Rešenje ===
* Индиректно, не морамо знати тачну индетификацију процеса којем шаљемо/узимамо податке, већ само име цевовода
* Мотивација је распрезање кода што омогућава лакше одржавање и независно мењање кода
== 4. zadatak ==
=== Postavka ===
Navesti i precizno objasniti bar dva načina sprečavanja mrtve blokade ukidanjem uslova
„držanje i čekanje“ (hold and wait).
=== Rešenje ===
* Процеси не смеју тражити нови ресурс уколико већ имају/треже неки други. За hold&wait су потребна бар 2 ресурса што овај приступ онемогућава.
* Процеси све своје ресурсе морају тражити истовремено, уколико не добију све све које заузели ослобађају па после неког времена покушавају поново све док не добију све тражене ресурсе. За hold&wait морамо држати неки ресурс док тражимо други, а овим приступом се то онемогућава јер се сви ресурси заузимају истовремено

== 5. zadatak ==
=== Postavka ===
Dati sistem primenjuje izbegavanje mrtve blokade. Tri procesa, P1, P2 i P3, najavila su
korišćenje oba resursa R1 i R2. Nacrtati graf zauzeća resursa nakon sledeće sekvence: P1 traži R1,
P3 traži R2, P2 traži R1, P1 oslobađa R1. Ako više procesa čeka na isti resurs, dobiće ga najpre onaj
koji ga je najranije tražio
=== Skica rešenja ===
* П1 најављује коришћење свих ресурса
* П2 тражи Р1, најављује корићење Р2
* П3 користи Р2, најављује коришћење Р1
== 6. zadatak ==
=== Postavka ===
Kod LRU algoritma zamene stranica korišćenjem dodatnih bita referenciranja, navesti šta
tačno radi operativni sistem u sledeće dve situacije:
* periodično ažuriranje evidencije:
* izbor žrtve za izbacivanje:
=== Rešenje ===
* Шифтује додатне бите референцирања и у њих убацује бит референцирања који угађа хардвер који потом ресетује на 0
* Путује по кружној листи и понавља корак под а док не наиђе на страницу којој сви бити референцирања 0

== 7. zadatak ==
=== Postavka ===
Neki sistem primenjuje sistem parnjaka (buddy) za alokaciju memorije. Stanje sistema u
datom trenutku prikazano je na sledećoj slici:
* X__XX__X_X__X___
Svako polje predstavlja jedan elementarni blok (najmanju jedinicu alokacije), a blokovi označeni sa
X su zauzeti. Prikazati stanje nakon zahteva za alokaciju segmenta veličine dva bloka:
=== Rešenje ===
* X__XX__X_XXXX___ или X__XX__X_X__X_XX

== 8. zadatak ==
=== Postavka ===
Koja RAID konfiguracija ima veći efektivni prostor za podatke, RAID0 ili RAID1, i koliki
je efektivni prostor za 2N jednakih diskova? A koja ima veću pouzdanost?
=== Rešenje ===
* Већу поузданост има RAID0,а већи ефективни простор има RAID1
* У овом примеру RAID0 има 2N, a RAID1 има N ефективног простора

== 9. zadatak ==
=== Postavka ===
Ukratko objasniti koncept modula jezgra u sistemu Linux, uključujući i motivaciju za
uvođenje tog kocnepta.
=== Rešenje ===
* Језгро линукса "довлачи" потребне делове кода тек када му затребају, нпр драјвери, иначе их не садржи у свом коду.
* Мотивација је жеља да линукс може радити и на хардверски лошим рачунарима

== 10. zadatak ==
=== Postavka ===
Koji način alokacije fajlova primenjuje Linux ext fajl sistem? Ukratko ga objasniti.
=== Rešenje ===
* Индексни, са највише 3 нивоа индирекције.
* Налик је алокацији страница за процесе коришћењем PCBa.

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

ОС2/Фебруар 2022

2022-02-23T10:40:47Z

IvnSvc: Нова страница: {{tocright}} [http://os.etf.rs/OS2/rokovi/2021/avgust/OS2%20avgust%202021.pdf Zadaci na stranici predmeta.] == 1. zadatak == === Postavka === Da li se kod algoritma ra…

{{tocright}}
[http://os.etf.rs/OS2/rokovi/2021/avgust/OS2%20avgust%202021.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Da li se kod algoritma raspoređivanja Multi-level Feedback Queue Scheduling procesu koji
je došao u red spremnih iz stanja suspenzije po pravilu smanjuje ili povećava prioritet? Zašto?
=== Rešenje ===
* Ставља се у виши(приоритетнији) ред.
* Зато што смо прошлом проценом преценили дужину његовог налета или смо потценили његову интерактивност. Зато стављамо процес у ред у којем ће краће чекати следећи налет, али ће имати и мање време налета

== 2. zadatak ==
=== Postavka ===
Na programskom jeziku Java realizovati monitor sa dve operacije, op1 i op2, pri čemu
monitor održava sledeću invarijantu: ukupan broj izvršavanja operacije op1 je uvek ne manji od
broja izvršavanja operacije op2. Zanemariti prekoračenje ograničenog opsega celobrojnih brojača.
=== Rešenje ===
<syntaxhighlight lang="java">

public class MyMonitor{
private int count;

public synchronized void op1(){
this.count+=1;
if(this.count == 1) notifyAll()
}
public synchronized void op2(){
while(--this.count <0)wait()
}
}

</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
U koju kategoriju međuprocesne komunikacije po pitanju imenovanja spada koncept
cevovoda (pipe)? Obrazložiti. Šta je osnovna motivacija za ovakav koncept?
=== Rešenje ===
* Индиректно, не морамо знати тачну индетификацију процеса којем шаљемо/узимамо податке, већ само име цевовода
* Мотивација је распрезање кода што омогућава лакше одржавање и независно мењање кода
== 4. zadatak ==
=== Postavka ===
Navesti i precizno objasniti bar dva načina sprečavanja mrtve blokade ukidanjem uslova
„držanje i čekanje“ (hold and wait).
=== Rešenje ===
* Процеси не смеју тражити нови ресурс уколико већ имају/треже неки други. За hold&wait су потребна бар 2 ресурса што овај приступ онемогућава.
* Процеси све своје ресурсе морају тражити истовремено, уколико не добију све све које заузели ослобађају па после неког времена покушавају поново све док не добију све тражене ресурсе. За hold&wait морамо држати неки ресурс док тражимо други, а овим приступом се то онемогућава јер се сви ресурси заузимају истовремено

== 5. zadatak ==
=== Postavka ===
Dati sistem primenjuje izbegavanje mrtve blokade. Tri procesa, P1, P2 i P3, najavila su
korišćenje oba resursa R1 i R2. Nacrtati graf zauzeća resursa nakon sledeće sekvence: P1 traži R1,
P3 traži R2, P2 traži R1, P1 oslobađa R1. Ako više procesa čeka na isti resurs, dobiće ga najpre onaj
koji ga je najranije tražio
=== Skica rešenja ===
* П1 најављује коришћење свих ресурса
* П2 тражи Р1, најављује корићење Р2
* П3 користи Р2, најављује коришћење Р1
== 6. zadatak ==
=== Postavka ===
Kod LRU algoritma zamene stranica korišćenjem dodatnih bita referenciranja, navesti šta
tačno radi operativni sistem u sledeće dve situacije:
* periodično ažuriranje evidencije:
* izbor žrtve za izbacivanje:
=== Rešenje ===
* Шифтује додатне бите референцирања и у њих убацује бит референцирања који угађа хардвер који потом ресетује на 0
* Путује по кружној листи и понавља корак под а док не наиђе на страницу којој сви бити референцирања 0

== 7. zadatak ==
=== Postavka ===
Neki sistem primenjuje sistem parnjaka (buddy) za alokaciju memorije. Stanje sistema u
datom trenutku prikazano je na sledećoj slici:
* X__XX__X_X__X___
Svako polje predstavlja jedan elementarni blok (najmanju jedinicu alokacije), a blokovi označeni sa
X su zauzeti. Prikazati stanje nakon zahteva za alokaciju segmenta veličine dva bloka:
=== Rešenje ===
* X__XX__X_XXXX___ или X__XX__X_X__X_XX

== 8. zadatak ==
=== Postavka ===
Koja RAID konfiguracija ima veći efektivni prostor za podatke, RAID0 ili RAID1, i koliki
je efektivni prostor za 2N jednakih diskova? A koja ima veću pouzdanost?
=== Rešenje ===
* Већу поузданост има RAID0,а већи ефективни простор има RAID1
* У овом примеру RAID0 има 2N, a RAID1 има N ефективног простора

== 9. zadatak ==
=== Postavka ===
Ukratko objasniti koncept modula jezgra u sistemu Linux, uključujući i motivaciju za
uvođenje tog kocnepta.
=== Rešenje ===
* Језгро линукса "довлачи" потребне делове кода тек када му затребају, нпр драјвери, иначе их не садржи у свом коду.
* Мотивација је жеља да линукс може радити и на хардверски лошим рачунарима

== 10. zadatak ==
=== Postavka ===
Koji način alokacije fajlova primenjuje Linux ext fajl sistem? Ukratko ga objasniti.
=== Rešenje ===
* Индексни, са највише 3 нивоа индирекције.
* Налик је алокацији страница за процесе коришћењем PCBa.

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

ОО1/К1 2021

2021-12-11T11:25:10Z

IvnSvc: /* 4. zadatak */ Фали текст задатка, а врв је овако гласио

{{tocright}}
{{rešenja}}

== 1. zadatak ==
Data je sledeća klasa:
<syntaxhighlight lang="cpp">
class X {
public:
X(int a) {}
explicit X(const string&) {}
};
</syntaxhighlight>
Koji isečci koda od navedenih će se uspešno izvršiti?
<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="cpp" class="solution">
X f() {
return 0;
}
int main() {
f();
}
</syntaxhighlight>
# <syntaxhighlight lang="cpp">
X g() {
return "abc";
}
int main() {
g();
}
</syntaxhighlight>
# <syntaxhighlight lang="cpp" class="solution">X(3);</syntaxhighlight>
# <syntaxhighlight lang="cpp" class="solution">X("abc");</syntaxhighlight>
</div>

== 2. zadatak ==
Šta može da stoji umesto dela označenog sa *** a da se program uspešno prevodi?
<syntaxhighlight lang="cpp">
int i = 0;
enum dan {PON, UTO, SRE};

int main() {
dan s;
int j = 1;
class L {
void g() {
***
}
};
}
</syntaxhighlight>
<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="cpp" inline>s = UTO;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline>j++;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">i++;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">i = PON;</syntaxhighlight>
</div>

== 3. zadatak ==
Šta ispisuje sledeći kod na programskom jeziku C++:
<syntaxhighlight lang="cpp">
#include <iostream>
using namespace std;

void f1(int& a) { cout << 2; }
void f2(const int& a) { cout << 1; }
void f3(int&& a) { cout << 3; }

int main() {
int x = 0;
const int y = 0;
f1(x);
f2(y);
f3(x+1);
}
</syntaxhighlight>
Odgovor: <span class="spoiler" data-solution="text">213</span>

== 4. zadatak ==
Šta ispisuje sledeći kod na programskom jeziku C++:
<syntaxhighlight lang="cpp">
#include <iostream>
using namespace std;

int x = 5;

int f(int x) {
return x = x+1;
}

int main() {
cout << f(x) << ::x;
}
</syntaxhighlight>
Odgovor: <span class="spoiler" data-solution="text">65</span>

== 5. zadatak ==
Šta u sledećem kodu može da stoji umesto dela označenog sa ### a da se on ispravno prevodi:
<syntaxhighlight lang="cpp">
#include <iostream>
using namespace std;

int main() {
int a = 3;
const int* const p = &a;
###
}
</syntaxhighlight>
<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="cpp" inline class="solution">cout << p;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline>p++;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline>*p = 4;</syntaxhighlight>
# <syntaxhighlight lang="cpp" inline class="solution">cout << *p;</syntaxhighlight>
</div>

== 6. zadatak ==
Gde se skladište sledeći podaci:
{| class="wikitable"
|+ Ponuđene opcije
! Podaci
! Lokacija
|-
| <div data-solution="select" data-options="a,b,c,d">
* Privremeni podaci <span class="spoiler">b</span><ref>Naknadno je za ovaj odgovor bila priznavana opcija pod c, jer privremeni podaci mogu da se čuvaju i na steku.</ref>
* Dinamički podaci <span class="spoiler">a</span>
* Automatski podaci <span class="spoiler">c</span>
</div>
| <div class="abc-list">
# Heap
# Registri
# Stek
# EPROM
</div>
|}

== 7. zadatak ==


== 8. zadatak ==


== 9. zadatak ==


== 10. zadatak ==

== Napomene ==
<references />

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

Пројектовање софтвера/Пробни тестови 2021

2021-10-25T19:30:05Z

IvnSvc: исправка трећехг задатка

{{tocright}}
{{rešenja}}

== Пробни тест ==
=== 1. задатак ===
Повезати појмове са одговарајућим дефиницијама принципа ОО модела.
{| class="wikitable"
|+ Опције
! Дефиниција
! Појам
|-
|
<div data-solution="select" data-options="a,b,c">
* <code>tipizacija</code> <span class="spoiler">b</span>
* <code>рerzistencija</code> <span class="spoiler">a</span>
* <code>konkurentnost</code> <span class="spoiler">c</span>
</div>
| <div class="abc-list">
# Oсобина по којој се постојање објекта протеже кроз време
# Особине да се објекти различитих класа не могу уопште или се могу замењивати на одређене начине
# Особина која разликује активне објекте од пасивних

</div>
|}

=== 2. задатак ===
Навести симбол пакетског права приступа на језику UML<br>
Одговор: <span class="spoiler" data-solution="text">~</span>

=== 3. задатак ===
Означите тачна тврђења везана за класе у језику UML ?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Класа је опис скупа објеката који деле исту спецификацију карактеристика (атрибута и операција), ограничења и семантике.</span>
# <span class="solution">Подразумевано право приступа за атрибуте/операције у класи је јавно</span>
# Добро осмишљена класа треба да има велики број одговорности
# <span class="solution">Атрибуте/операције класе је могуће груписати уз навођење описног префиксног назива групе</span>
# Симбол класе може да садржи празан одељак за атрибуте/операције само ако одговарајућа класа нема атрибуте/операције
</div>
=== 4. задатак ===
Која од следећих особина испуњава пакет на језику UML ?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Пакет је власник садржаних елемената</span>
# <span class="solution">Пакет може да садржи друге пакете</span>
# Пакет је физичка ствар
# <span class="solution">Пакет представља простор имена</span>
# Пакет је стереотип класе
</div>

=== 5. задатак ===
Ако се у пакету А налази јавна класа Х, да би се у пакету В та класа могла користити директним именовањем Х, али да се у пакету С не би могла користити под именом B::X, коју релацију треба успоставити између пакета В и пакета А ?
<div class="abc-list" data-solution="multiple">
# Стереотип асоцијације <<private>>
# Стереотип генерализације <<public>>
# Стереотип зависности <<import>>
# <span class="solution">Стереотип зависности <<access>></span>
# Стереотип реализације <<include>>
</div>

=== 6. задатак ===
Шта представља дијаграм објеката у UML ?
<div class="abc-list" data-solution="multiple">
# Дијаграм за приказ динамичких аспеката модела
# Дијаграм представља формалну спецификацију модела
# <span class="solution">Дијаграм за приказ статичких аспеката модела</span>
# <span class="solution">Дијаграм представља само пример и служи за боље разумевање модела </span>
# <span class="solution">Дијаграм за приказ физичких аспеката модела</span>
# Дијаграм за приказ логичких аспеката модела
</div>

=== 7. задатак ===
Која од понуђених тврњи су тачне за пројектни узорак УНИКАТ (енлг. Singleton) ?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Уникат спада у објектне узорке стварања</span>
# <span class="solution">Иако то није по канонском узорку УНИКАТ, једноставно (по малој цени) се може контролисано повећати број дозвољених објеката</span>
# Конструктор класе која имплементира објектни узорак увек мора бити приватан
# Добар примерак класе која га имплементира је услужна (енлг. utility) класа
# Канонски узорак не ограничава број објеката класе Unikat, која имплементира пројектни узорак
</div>

=== 8. задатак ===
Колико различитих типова учесника постоји у пројектном узорку ''Prototip'' ?
Odgovor: <span class="spoiler" data-solution="text">3</span>

=== 9. задатак ===
У апликацији графичког едитора се примењује узорак ''Sastav''. Упарити поједине називе класа у апликацији са називима учесника у пројектном узорку

{| class="wikitable"
|+ Опције
! Учесници
! Класе
|-
|
<div data-solution="select" data-options="a,b,c,d">
* <code>List</code> <span class="spoiler">b</span>
* <code>Sklop</code> <span class="spoiler">a</span>
* <code>Element</code> <span class="spoiler">c</span>
* <code>Klijent</code> <span class="spoiler">d</span>
</div>
| <div class="abc-list">
# Crtez
# Linija
# Grafik
# Editor

</div>
|}

=== 10. задатак ===
Пројектни узорак који не дозвољава више његових примерака<br>
Одговор: <span class="spoiler" data-solution="text">Unikat</span>

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

Пројектовање софтвера/Пробни тестови 2021

2021-10-25T19:09:43Z

IvnSvc: /* 1. задатак */

{{tocright}}
{{rešenja}}

== Пробни тест ==
=== 1. задатак ===
Повезати појмове са одговарајућим дефиницијама принципа ОО модела.
{| class="wikitable"
|+ Опције
! Дефиниција
! Појам
|-
|
<div data-solution="select" data-options="a,b,c">
* <code>tipizacija</code> <span class="spoiler">b</span>
* <code>рerzistencija</code> <span class="spoiler">a</span>
* <code>konkurentnost</code> <span class="spoiler">c</span>
</div>
| <div class="abc-list">
# Oсобина по којој се постојање објекта протеже кроз време
# Особине да се објекти различитих класа не могу уопште или се могу замењивати на одређене начине
# Особина која разликује активне објекте од пасивних

</div>
|}

=== 2. задатак ===
Навести симбол пакетског права приступа на језику UML
Одговор: <span class="spoiler" data-solution="text">~</span>

=== 3. задатак ===
Означите тачна тврђења везана за класе у језику UML ?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Класа је опис скупа објеката који деле исту спецификацију карактеристика (атрибута и операција), ограничења и семантике.</span>
# Подразумевано право приступа за атрибуте/операције у класи је јавно
# Добро осмишљена класа треба да има велики број одговорности
# Атрибуте/операције класе је могуће груписати уз навођење описног префиксног назива групе
# <span class="solution">Симбол класе може да садржи празан одељак за атрибуте/операције само ако одговарајућа класанема атрибуте/операције</span>
</div>
=== 4. задатак ===
Која од следећих особина испуњава пакет на језику UML ?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Пакет је власник садржаних елемената</span>
# <span class="solution">Пакет може да садржи друге пакете</span>
# Пакет је физичка ствар
# <span class="solution">Пакет представља простор имена</span>
# Пакет је стереотип класе
</div>

=== 5. задатак ===
Ако се у пакету А налази јавна класа Х, да би се у пакету В та класа могла користити директним именовањем Х, али да се у пакету С не би могла користити под именом B::X, коју релацију треба успоставити између пакета В и пакета А ?
<div class="abc-list" data-solution="multiple">
# Стереотип асоцијације <<private>>
# Стереотип генерализације <<public>>
# Стереотип зависности <<import>>
# <span class="solution">Стереотип зависности <<access>></span>
# Стереотип реализације <<include>>
</div>

=== 6. задатак ===
Шта представља дијаграм објеката у UML ?
<div class="abc-list" data-solution="multiple">
# Дијаграм за приказ динамичких аспеката модела
# Дијаграм представља формалну спецификацију модела
# <span class="solution">Дијаграм за приказ статичких аспеката модела</span>
# <span class="solution">Дијаграм представља само пример и служи за боље разумевање модела </span>
# <span class="solution">Дијаграм за приказ физичких аспеката модела</span>
# Дијаграм за приказ логичких аспеката модела
</div>

=== 7. задатак ===
Која од понуђених тврњи су тачне за пројектни узорак УНИКАТ (енлг. Singleton) ?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Уникат спада у објектне узорке стварања</span>
# <span class="solution">Иако то није по канонском узорку УНИКАТ, једноставно (по малој цени) се може контролисано повећати број дозвољених објеката</span>
# Конструктор класе која имплементира објектни узорак увек мора бити приватан
# Добар примерак класе која га имплементира је услужна (енлг. utility) класа
# Канонски узорак не ограничава број објеката класе Unikat, која имплементира пројектни узорак
</div>

=== 8. задатак ===
Колико различитих типова учесника постоји у пројектном узорку ''Prototip'' ?
Odgovor: <span class="spoiler" data-solution="text">3</span>

=== 9. задатак ===
У апликацији графичког едитора се примењује узорак ''Sastav''. Упарити поједине називе класа у апликацији са називима учесника у пројектном узорку

{| class="wikitable"
|+ Опције
! Учесници
! Класе
|-
|
<div data-solution="select" data-options="a,b,c,d">
* <code>List</code> <span class="spoiler">b</span>
* <code>Sklop</code> <span class="spoiler">a</span>
* <code>Element</code> <span class="spoiler">c</span>
* <code>Klijent</code> <span class="spoiler">d</span>
</div>
| <div class="abc-list">
# Crtez
# Linija
# Grafik
# Editor

</div>
|}

=== 10. задатак ===
Пројектни узорак који не дозвољава више његових примерака
Одговор: <span class="spoiler" data-solution="text">Unikat</span>

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

Пројектовање софтвера/Пробни тестови 2021

2021-10-25T19:09:06Z

IvnSvc: Пробни тест, 10*. питање нисам сц па нзм тачан текст

{{tocright}}
{{rešenja}}

== Пробни тест ==
=== 1. задатак ===
Повезати појмове са одговарајућим дефиницијама принципа ОО модела.
{| class="wikitable"
|+ Опције
! Дефиниција
! Појам
|-
|
<div data-solution="select" data-options="a,b,c">
* <code>tipizacija</code> <span class="spoiler">b</span>
* <code>erzistencija</code> <span class="spoiler">a</span>
* <code>konkurentnost</code> <span class="spoiler">c</span>
</div>
| <div class="abc-list">
# Oсобина по којој се постојање објекта протеже кроз време
# Особине да се објекти различитих класа не могу уопште или се могу замењивати на одређене начине
# Особина која разликује активне објекте од пасивних

</div>
|}

=== 2. задатак ===
Навести симбол пакетског права приступа на језику UML
Одговор: <span class="spoiler" data-solution="text">~</span>

=== 3. задатак ===
Означите тачна тврђења везана за класе у језику UML ?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Класа је опис скупа објеката који деле исту спецификацију карактеристика (атрибута и операција), ограничења и семантике.</span>
# Подразумевано право приступа за атрибуте/операције у класи је јавно
# Добро осмишљена класа треба да има велики број одговорности
# Атрибуте/операције класе је могуће груписати уз навођење описног префиксног назива групе
# <span class="solution">Симбол класе може да садржи празан одељак за атрибуте/операције само ако одговарајућа класанема атрибуте/операције</span>
</div>
=== 4. задатак ===
Која од следећих особина испуњава пакет на језику UML ?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Пакет је власник садржаних елемената</span>
# <span class="solution">Пакет може да садржи друге пакете</span>
# Пакет је физичка ствар
# <span class="solution">Пакет представља простор имена</span>
# Пакет је стереотип класе
</div>

=== 5. задатак ===
Ако се у пакету А налази јавна класа Х, да би се у пакету В та класа могла користити директним именовањем Х, али да се у пакету С не би могла користити под именом B::X, коју релацију треба успоставити између пакета В и пакета А ?
<div class="abc-list" data-solution="multiple">
# Стереотип асоцијације <<private>>
# Стереотип генерализације <<public>>
# Стереотип зависности <<import>>
# <span class="solution">Стереотип зависности <<access>></span>
# Стереотип реализације <<include>>
</div>

=== 6. задатак ===
Шта представља дијаграм објеката у UML ?
<div class="abc-list" data-solution="multiple">
# Дијаграм за приказ динамичких аспеката модела
# Дијаграм представља формалну спецификацију модела
# <span class="solution">Дијаграм за приказ статичких аспеката модела</span>
# <span class="solution">Дијаграм представља само пример и служи за боље разумевање модела </span>
# <span class="solution">Дијаграм за приказ физичких аспеката модела</span>
# Дијаграм за приказ логичких аспеката модела
</div>

=== 7. задатак ===
Која од понуђених тврњи су тачне за пројектни узорак УНИКАТ (енлг. Singleton) ?
<div class="abc-list" data-solution="multiple">
# <span class="solution">Уникат спада у објектне узорке стварања</span>
# <span class="solution">Иако то није по канонском узорку УНИКАТ, једноставно (по малој цени) се може контролисано повећати број дозвољених објеката</span>
# Конструктор класе која имплементира објектни узорак увек мора бити приватан
# Добар примерак класе која га имплементира је услужна (енлг. utility) класа
# Канонски узорак не ограничава број објеката класе Unikat, која имплементира пројектни узорак
</div>

=== 8. задатак ===
Колико различитих типова учесника постоји у пројектном узорку ''Prototip'' ?
Odgovor: <span class="spoiler" data-solution="text">3</span>

=== 9. задатак ===
У апликацији графичког едитора се примењује узорак ''Sastav''. Упарити поједине називе класа у апликацији са називима учесника у пројектном узорку

{| class="wikitable"
|+ Опције
! Учесници
! Класе
|-
|
<div data-solution="select" data-options="a,b,c,d">
* <code>List</code> <span class="spoiler">b</span>
* <code>Sklop</code> <span class="spoiler">a</span>
* <code>Element</code> <span class="spoiler">c</span>
* <code>Klijent</code> <span class="spoiler">d</span>
</div>
| <div class="abc-list">
# Crtez
# Linija
# Grafik
# Editor

</div>
|}

=== 10. задатак ===
Пројектни узорак који не дозвољава више његових примерака
Одговор: <span class="spoiler" data-solution="text">Unikat</span>

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

Вероватноћа и статистика/Август 2021

2021-10-04T16:38:50Z

IvnSvc: август овог лета

{{tocright}}
== Испитни део - Статистика ==
=== 1. задатак ===
==== Поставка ====
Дате су променљиве X и Y, <math>Y = 2X + 1</math>. <math> X \sim Uni[ \,0,2] \,</math>. Нађи <math> \rho ( \,X,Y) \,</math> .

==== Решењe ====
*1

=== 2. задатак ===
==== Поставка ====
#Како гласи Чебишевљева неједнакост, извести је.
#Уколико ради 10 000 сијалица, одредити горњу границу за <math> P( \,|X-EX| <200)\,</math>

==== Решење ====

=== 3. задатак ===
==== Поставка ====
За {| border="1" style="border-collapse:collapse"
| -1
| 0
|1
|2
|-
| <math> \frac{p}{3}</math>
| <math> \frac{p}{3}</math>
| 1-p
|<math> \frac{p}{3}</math>
|}
оценити р са<br>
#Методом момента, узорак 1,1,0,0,0,-1,-1,-1,0,2,2,2
#Методом максималне веродостојности
==== Решење ====

=== 4. задатак ===
==== Поставка ====
Имамо 213 места на авиону, шанса да путник не дође на резервисано место је 0.0995. Колико максимално резервација можемо направити ако шанса да свако има место буде већа од 0.9 ?
==== Решење ====

=== 5. задатак ===
==== Поставка ====
Одредити област одбацивања за <math> \mathcal{N}( \,\mu,80^2) \, </math> , узорак је величине 100. Одредити и вероватноћу грешке другог реда уколико је <math> \mu = 210</math>

==== Решење ====

[[Категорија:Вероватноћа_и_статистика]]
[[Категорија:Рокови]]

Вероватноћа и статистика/Јул 2021

2021-10-03T17:50:08Z

IvnSvc: /* Поставка */ латек грешка

== Испитни део - Статистика ==
=== 1. задатак ===
==== Поставка ====
Наћи <math>\rho</math>(x,y) и испитати јесу ли зависни<br>
{| class="wikitable"
|+
|-
|x\y
|0
|1
|2
|3
|4
|5
|-
|1
|0.05
|0.05
|0.1
|0
|0.1
|0.1
|-
|2
|0.1
|0.1
|0.2
|0.05
|0.1
|0.05
|}

==== Решење ====

=== 2. задатак ===
==== Поставка ====
На журку нам долази 120 људи, вероватноће да ће неко узети 0,1 или 2 сендвича су <math>\frac{1}{4},\frac{1}{2},\frac{1}{4}</math>
Колико је најмање сендвича потребно да се направи да би са вероватноћом од 0.95 били сигурни да ће их бити за све ? Коју теорему сте користили да би сте решили задатак ?

==== Скица решења ====
Коришћењем ЦГТ долази се до око 130 потребних сендвича

=== 3. задатак ===
==== Поставка ====
Нека променљива имаваријансу 1.44 код је очекивање непознато. Приликом оцена параметра добијен је интервал поверењадужине 0.9408. Колики треба бити узорак да би се ово десило ? <math> \alpha = 0.05 </math>
==== Скица решења ====
Одузимањем горње и доње границе интерцала долазимо до израза из којег извлачима n које је минимум 25

=== 4. задатак ===
==== Поставка ====
Нека су <math> X_1, X_2,...X_n</math> променљиве са расподелом <math> Exp(\frac{1}{\lambda}) </math> . Aко је U оцена параметра добијена методом максималне веродостојности, V оцена <math> \lambda = min\{X_1, X_2,...X_n\}</math>. Која од оцена је боља ?
==== Решење ====

=== 5. задатак ===
==== Поставка ====
Мерен је промет аутомобила на неком месту у периоду од 100 минута (ауто/минут). Резултату су дати у табели. Да ли ови резултати прате Пуасонову расподелу ?
{| class="wikitable"
|+
|-
| Бр. аутомобила
|0
|1
|2
|3
|4
|5
|-
|Бр. проласка
|8
|28
|31
|18
|9
|6
|}

==== Скица решења ====
Прво морамо оценити параметар Пуасонове расподеле јер није дат. После правимо табелу за тестирање непараметарских хипотеза <math> \chi^2 </math> јер је Пуасонова раподела дискретна. Након тога користимо квантили из <math> \chi^2 </math> расподеле са степеном слободе 4 (6-1-1).

[[Категорија:Вероватноћа_и_статистика]]
[[Категорија:Рокови]]

Вероватноћа и статистика/Јул 2021

2021-10-03T17:48:47Z

IvnSvc: Нова страница: == Испитни део - Статистика == === 1. задатак === ==== Поставка ==== Наћи <math>\rho</math>(x,y) и испитати јесу л…

== Испитни део - Статистика ==
=== 1. задатак ===
==== Поставка ====
Наћи <math>\rho</math>(x,y) и испитати јесу ли зависни<br>
{| class="wikitable"
|+
|-
|x\y
|0
|1
|2
|3
|4
|5
|-
|1
|0.05
|0.05
|0.1
|0
|0.1
|0.1
|-
|2
|0.1
|0.1
|0.2
|0.05
|0.1
|0.05
|}

==== Решење ====

=== 2. задатак ===
==== Поставка ====
На журку нам долази 120 људи, вероватноће да ће неко узети 0,1 или 2 сендвича су <math>\frac{1}{4},\frac{1}{2},frac{1}{4}</math>
Колико је најмање сендвича потребно да се направи да би са вероватноћом од 0.95 били сигурни да ће их бити за све ? Коју теорему сте користили да би сте решили задатак ?

==== Скица решења ====
Коришћењем ЦГТ долази се до око 130 потребних сендвича

=== 3. задатак ===
==== Поставка ====
Нека променљива имаваријансу 1.44 код је очекивање непознато. Приликом оцена параметра добијен је интервал поверењадужине 0.9408. Колики треба бити узорак да би се ово десило ? <math> \alpha = 0.05 </math>
==== Скица решења ====
Одузимањем горње и доње границе интерцала долазимо до израза из којег извлачима n које је минимум 25

=== 4. задатак ===
==== Поставка ====
Нека су <math> X_1, X_2,...X_n</math> променљиве са расподелом <math> Exp(\frac{1}{\lambda}) </math> . Aко је U оцена параметра добијена методом максималне веродостојности, V оцена <math> \lambda = min\{X_1, X_2,...X_n\}</math>. Која од оцена је боља ?
==== Решење ====

=== 5. задатак ===
==== Поставка ====
Мерен је промет аутомобила на неком месту у периоду од 100 минута (ауто/минут). Резултату су дати у табели. Да ли ови резултати прате Пуасонову расподелу ?
{| class="wikitable"
|+
|-
| Бр. аутомобила
|0
|1
|2
|3
|4
|5
|-
|Бр. проласка
|8
|28
|31
|18
|9
|6
|}

==== Скица решења ====
Прво морамо оценити параметар Пуасонове расподеле јер није дат. После правимо табелу за тестирање непараметарских хипотеза <math> \chi^2 </math> јер је Пуасонова раподела дискретна. Након тога користимо квантили из <math> \chi^2 </math> расподеле са степеном слободе 4 (6-1-1).

[[Категорија:Вероватноћа_и_статистика]]
[[Категорија:Рокови]]

Вероватноћа и статистика/К 2021

2021-10-03T17:10:34Z

IvnSvc:

== Колоквијум - Вероватноћа ==
=== 1. задатак ===
==== Поставка ====
Искра и Марко се налазе између 15-18h, ко први дође чека 45 минута пре него што оде. Колика је шанса да ће се Марко и Искра срести.

==== Скица решења ====
Направити координатни систем који иде до 3 по обе осе. Повући праве <math>y = x + \frac{1}{4}</math>, <math>y = x - \frac{1}{4}</math>, y=1 и x=1. Одредити површину шестоугла који они одређују у то је вероватноћа њиховог сусрета.

=== 2. задатак ===
==== Поставка ====
# Шта је условна вероватноћа ?
# Дефинисати независност догађаја?
==== Решење ====

=== 3. задатак ===
==== Поставка ====
Дати дефиницију потпуне веротноће.
==== Решење ====

=== 4. задатак ===
==== Поставка ====
Фирма А проиводи 23%, В 52%, а фирма С 27% производа. Шкарта има у А 1%, В 3% а у С 5%. Колика је шанса да смо изабрали неки неисправан производ са гомиле на којој се налазе производи само ових компанија ?
==== Скица Решења ====
Коришћењем формуле тоталне вероватноће и Бајесовe формулe се долази до решења

=== 5. задатак ===
==== Поставка ====
У просеку у пошту уђе две особе у 3 минута. Колика је вероватноћа да у 5 минута не уђе ниједна особа, а колика да је ушло бар 3 особе

==== Скица Решења ====
Ретки догађаји као што је и овај имају Пуасонову расподелу. Пондеришемо број особа на 5 минута и израчунамо P(0) за ниједну и <br> 1 - [ P(0) + P(1) + P(2) ] за 3+ (преко инверзног догађаја).

=== 6. задатак ===
==== Поставка ====
Написати дефиницију математичког очекивања и навести његове особине

==== Решење ====

=== 7. задатак ===
==== Поставка ====
Ако је Х непрекидна случајна променљива са густином <math>fx</math> и расподелом <math>Fx</math> одредити густину и расподелу за <math> Y=|X| </math>

==== Решење ====

[[Категорија:Вероватноћа_и_статистика]]
[[Категорија:Рокови]]

Вероватноћа и статистика/КП 2021

2021-10-03T17:09:19Z

IvnSvc:

== Колоквијум - Вероватноћа ==
=== 1. задатак ===
==== Поставка ====
Навести аксиоме вероватноће

==== Решење ====

=== 2. задатак ===
==== Поставка ====
Бинарни сигнал може послати апарат А,В и С са шансама за слање са А,В,С од <math> \frac{1}{2}</math>, <math> \frac{1}{3}</math> и<math> \frac{1}{6}</math> респективно. Ако је послат сигнал са А, он садржи 20% јединица, са В садржи 30% док са С садржи 40% јединица. Примљен је сигнал од 10 знака са 4 јединице. Одредити вероватноћу да је сигнал послат са апарата В.
==== Скица решења ====
Користити формулу тоталне вероватноће и Бајесову формулу

=== 3. задатак ===
==== Поставка ====
У пошту уђе једна особа у 9 минута. Одредити вероватноћу да у 9 минута : <br>
*Уђе више од три особе
*Не уђе ни једна особа
==== Решење ====
Ретки догађаји као што је и овај имају Пуасонову расподелу. Пондеришемо број особа на 9 минута и израчунамо P(0) за нула особа и
1 - [ P(0) + P(1) + P(2) ] за 3+ особе (преко инверзног догађаја).

=== 4. задатак ===
==== Поставка ====
Навести дефиницију варијансе и три теорије њене особине.
==== Решење ====

=== 5. задатак ===
==== Поставка ====
Штап дужине 3 метра јеполомљен. Наћи расподелу и густину површине правоугаоника којег бисмо добили његовим деловима
==== Решење ====

[[Категорија:Вероватноћа_и_статистика]]
[[Категорија:Рокови]]

Вероватноћа и статистика/КП 2021

2021-10-03T17:01:52Z

IvnSvc: страница поправног колоквијума 2021

Вероватноћа и статистика

2021-10-03T15:04:07Z

IvnSvc: брисање редундантног линка

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

== Странице ==
* [http://matematika.etf.bg.ac.rs/predmeti/vis.htm Страница предмета]


== Корисне везе ==
{{Материјали
| vuk = 1-BD4Q8qtq_R10M1Bn-kKO0f4EY8nm4UN 
| box = 8381665857 
| scientificmind = IR2VIS  }}

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

== Потребна помоћ ==
* {{zadaci|postavke}}

[[Категорија:Четврти семестар]]
[[Категорија:Изборни предмети]]

Вероватноћа и статистика

2021-10-03T15:01:21Z

IvnSvc:

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

== Странице ==
* [http://matematika.etf.bg.ac.rs/predmeti/vis.htm Страница предмета]


== Корисне везе ==
{{Материјали
| vuk = 1-BD4Q8qtq_R10M1Bn-kKO0f4EY8nm4UN 
| box = 8381665857 
| scientificmind = IR2VIS  }}

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

== Колоквијуми ==
* [[Вероватноћа_и_статистика/К_2021|Колоквијум 2021 - регуларни]]

== Потребна помоћ ==
* {{zadaci|postavke}}

[[Категорија:Четврти семестар]]
[[Категорија:Изборни предмети]]

Вероватноћа и статистика/К 2021

2021-10-03T14:52:16Z

IvnSvc: Овогодишњи регуларни колоквијум

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

2021-10-03T14:02:52Z

IvnSvc: /* Rešenje */ Додатне мане уколико немамо спулинг

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2015/feb/OS1%20Feb%202015.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Šta je bio osnovni motiv za uvođenje multiprogramiranja u računarske sisteme?

=== Rešenje ===
Videti zadatak iz [[ОС1/Септембар 2011#1. zadatak|septembarskog roka 2011]].

== 2. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog dvoadresnog RISC procesora sa ''load/store'' arhitekturom napisati program koji vrši prenos bloka podataka iz memorije na izlazni uređaj tehnikom programiranog izlaza korišćenjem prekida. Samostalno usvojiti potrebne detaljne pretpostavke.

=== Rešenje ===
<syntaxhighlight lang="asm">
main: LD R1, blockAddr
LD R2, cnt
LD R3, #0
ST [ctrl], #0..1
wait: CMP R3, #1
JNZ wait

intr: LD R0, [R1]
ST [data], R0
INC R1
DEC R2
JNZ ret
ST R3, #1
ST [ctrl], #0
ret: RTI
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Korišćenjem Unix sistemskih poziva <code>fork()</code> i <code>execlp()</code> napisati program koji prima jedan celobrojni argument i koji, ukoliko se proces pokrene sa parametrom -c, kreira još jedan isti takav proces, samo bez parametra, a u suprotnom se samo završava. Sistemski poziv <code>execlp</code> prima argumente komandne linije:
<code>
int execlp(char const *file, char const *arg0, ...)
</code>

=== Rešenje ===
<syntaxhighlight lang="c">
int main(int argc, char* argv) {
if(argc < 2) return -1;
if(argv[2][1] == 'c') {
int pid = fork();
if(pid < 0) return -1;
else if(pid == 0) execlp(argv[0], 0);
else wait(0);
}
return 0;
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Napisati kod za međusobno isključenje kritične sekcije korišćenjem binarnih semafora.

=== Rešenje ===
<syntaxhighlight lang="ada">
var mutex : Semaphore := 1;

process P
begin
loop
wait(mutex);
<critical>
signal(mutex);
<non-critical>
end
end P;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Objasniti zašto linkeru ne predstavlja nikakav problem prilikom povezivanja to što fajl a.obj uvozi simbol koji je definisan u b.obj, a b.obj uvozi simbol koji je definisan u a.obj. Kako se ova situacija rešava?

=== Rešenje ===
U prvom prolazu će se napraviti tabele simbola, a u drugom prolazu razrešiti imena pa ova situacija nije nikakav problem sem ako se ne radi o istom simbolu kada će doći do linkerske greške ako simbol nije nigde definisan.

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

A128, B32, C256, D64, A-, E16, F64, 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 ===
#2
#16KB
#96KB

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

=== Rešenje ===
VA(32) page 4KB -> 12b, descriptor 4B

pmt1 -> 8b

VA(32) : page1(8) : page2(12) : offset(12)

a) ceo prostor: 2^8 * 4 + 2^8 * 2^12 * 4 = 4MB + 1KB

b) prva i poslednja stranica u v. a. prostoru: 2^8 * 4 + 2^12 * 4 * 2 = 1KB + 32KB = 33KB

== 8. zadatak ==
=== Postavka ===
Umesto tehnike ''spooling'', pristup uporednih procesa štampaču u nekom sistemu omogućuje se međusobnim isključenjem pomoću operacije rezervacije: svaki proces, pre nego što zatraži bilo koju operaciju sa štampačem, mora da ga rezerviše, a tu rezervaciju otpušta tek kada završi sa celim jednim poslom štampe. Pored eventualnog sprečavanja mrtve blokade, o čemu još mora da vodi računa operativni sistem da se ne bi dešavalo neograničeno zauzeće štampača

=== Rešenje ===
Треба водити рачуна и о томе да ли је процес који тренутно користи уређај "отказао" или постао трајно суспендован без ослобађања уређаја.

== 9. zadatak ==
=== Postavka ===
Izvod iz jednog uputstva za Unix fajl sistem i dodelu prava pristupa fajlu iz komandne linije:

''To change the mode of a file, use the chmod command. The general form is chmod X@Y file1 file2 ... where: X is any combination of the letters 'u' (for owner), 'g' (for group), 'o' (for others), 'a' (for all; that is, for 'ugo'); @ is either '+' to add permissions, '-' to remove permissions, or '=' to assign permissions absolutely; and Y is any combination of 'r', 'w', 'x'.''

Na primer, komanda <code>chmod u=rx file</code> daje vlasniku prava ''rx'', ali ne i pravo ''w''.
Napisati komande koje za dati fajl postavljaju prava na sledeći način:

=== Rešenje ===
a) grupi i ostalima oduzimaju prava na rx, ali ne i na w: <code>chmod go-rx file</code>

b) svima dodaju pravo na izvršavanje: <code>chmod a+x file</code>

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem podržava kombinovano indeksiran pristup alokaciji fajlova, pri čemu FCB sadrži 256 ulaza sa direktnim indeksom (sadrže brojeve blokova za podatke). Ako sadržaj fajla preraste veličinu koju podržava ovaj indeks nultog nivoa, za blokove preko te veličine postoji indeks prvog nivoa sa 256 ulaza u FCB; svaki od tih ulaza sadrži pokazivač na indeks drugog nivoa u kome je po 256 ulaza sa pokazivačima na blokove sa sadržajem. Koliki je maksimalni kapacitet fajla u blokovima? (Odgovor dati kao izraz.)

=== Rešenje ===
(256 + 256*256) * blockSize

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

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

2021-10-03T14:00:54Z

IvnSvc: /* Rešenje */ Опис пресликавања странице у оквир

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

== 1. zadatak ==
=== Postavka ===
Neki interaktivni višeprocesni i višekorisnički sistem ne podržava raspodelu vremena (''time sharing''). Šta je njegov osnovni problem?

=== Rešenje ===
Osnovni problem je nejednakost u vremenu odziva na korisničku akciju. Ukoliko je više procesa spremno i treba da obradi korisničku akciju, oni procesi koji ranije dobiju procesor imaće kraće vreme odziva, dok oni koji kasnije dobiju procesor imaju duže vreme odziva. Još gore, vreme odziva istog procesa na sukcesivne korisničke akcije potpuno je nedeterminističko i zavisi od toga kako se rasporede procesi čineći da se korinsici osećaju kao da "smetaju" jedni drugima.

== 2. zadatak ==
=== Postavka ===
Ako se nad sledećim programom kreira jedan proces, koliko će ukupno biti elemenata sa vrednošću 0 u nizovima pid svih kreiranih procesa (uključujući i taj jedan početni) kada svi ti procesi izađu iz petlje, pod pretpostavkom da su svi sistemski pozivi uspeli?
<syntaxhighlight lang="c">
const int N=2;
int pid[N];
void main () {
for (int i=0; i<N; i++)
pid[i] = fork();
}
</syntaxhighlight>
=== Rešenje ===
Biće ukupno 4 elemenata sa vrednošću 0.

== 3. zadatak ==
=== Postavka ===
Šta je problem sledeće implementacije kritične sekcije uposlenim čekanjem?
<syntaxhighlight lang="ada">
process P1
loop
while flag2 = true do null end; (* Busy wait *)
flag1 := true;
<critical section> (* Critical section *)
flag1 := false; (* Exit protocol *)
<non-critical section>
end
end P1;

process P2
loop
while flag1 = true do null end; (* Busy wait *)
flag2 := true;
<critical section> (* Critical section *)
flag2 := false; (* Exit protocol *)
<non-critical section>
end
end P2;
</syntaxhighlight>
=== Rešenje ===
Problem je u tome što ovo rešenje uopšte ne obezbeđuje međusobno isključenje jer oba procesa mogu da uđu u kritičnu sekciju.

== 4. zadatak ==
=== Postavka ===
Dva procesa ''X'' i ''Y'' "proizvode" cele brojeve uporedo, nezavisnim i promenljivim brzinama. Proces ''Z'' treba da uzima po dva proizvedena broja, i to uvek tačno jedan koji je proizveo ''X'' i jedan koji je proizveo ''Y'', i njihov zbir ispisuje na standardni izlaz. Važno je obezbediti da proces Z uvek uzima samo "sveže" proizvedene brojeve, tj. nikada ne uzme više puta isti proizvedeni broj. Korišćenjem deljenih promenljivih i klasičnih brojačkih semafora, napisati sve potrebne deklaracije i kod procesa ''X'' i ''Z''.

=== Rešenje ===
Potrebno je ''X'' i ''Y'' implementirati kao bounded buffer jer mogu proizvoditi cele brojeve različitim brzinama. Proces ''Z'' će jednostavno pozivati operaciju take() nad tim dvama baferima.

== 5. zadatak ==
=== Postavka ===
U prvom prolazu kroz ulazne .obj fajlove, linker nailazi na izvezeni simbol koji se već nalazi u njegovoj tabeli simbola. Da li će to prijaviti kao grešku?

=== Rešenje ===
Da, jer ako se nalazi u tabeli simbola znači da je već definisan i dolazi do sukoba imena.

== 6. zadatak ==
=== Postavka ===
Da li kod stranične organizacije virtuelne memorije ima smisla hardverski vršiti proveru prekoračenja granice opsega dozvoljenih adresa unutar stranice radi zaštite od nedozvoljenog pristupa fizičkim adresama koje koriste drugi procesi? Kratko obrazložiti.

=== Rešenje ===
Нема потребе, код страничне организације величина странице у виртуелној меморији је иста као величина оквира у физичкој меморији тако да се не може десити да исти оквир деле 2 различита процеса, нити да је једна страница пресликана у 2+ oквира.

== 7. zadatak ==
=== Postavka ===
U nekom sistemu postoje sledeći sistemski pozivi:
<syntaxhighlight lang="c">
int async_write (char* buffer);
void wait (int request_id);
</syntaxhighlight>
Operacija <code>async_write</code> asinhrono zadaje operaciju izlaza datog niza znakova na neki izlazni uređaj i vraća interni sistemski identifikator tog zahteva (veći od 0), odnosno kod greške (manji od nula). Operacija wait suspenduje pozivajući proces sve dok operacija sa datim identifikatorom nije završena. Korišćenjem ovih sistemskih poziva, realizovati sinhroni izlaz:
<syntaxhighlight lang="c">
int sync_write (char* buffer);
</syntaxhighlight>
=== Rešenje ===
<syntaxhighlight lang="c">
int sync_write (char* buffer) {
int id = async_write(buffer);
if(id < 0) return id;
wait(id);
return 0;
}
</syntaxhighlight>
== 8. zadatak ==
=== Postavka ===
Ukratko objasniti šta je ''spooling''.

=== Rešenje ===
Kada neki nedeljivi spori uređaj želi da odradi posao, prvo se zatraži korišćenje tog uređaja sistemskim pozivom, OS tada pravi poseban fajl na određenom mestu u svom fajl sistemu u koji će preusmeriti sve ulazne operacije tog procesa sa štampaem i vraća kontrolu procesu. OS predaje fajl na obradu posebnom procesu ili niti (spuleru) koji će jedan po jedan fajl da uzima i njihove sadržaje da šalje datom uređaju.

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem podržava implicitno zaključavanje fajla prilikom njegovog otvaranja. Postoje dve vrste ključa: deljeni (''shared''), koji se traži prilikom otvaranja fajla samo za čitanje (proces koji je tako otvorio fajl ima pravo samo da čita iz fajla) i ekskluzivni (''exclusive''), koji se traži prilikom otvaranja fajla i za upis (proces koji je otvorio fajl ima pravo upisa). Popuniti sledeću tabelu upisivanjem oznaka onih procesa čiji će zahtev za otvaranjem istog fajla biti ispunjen, za svaki od dva data slučaja. Procesi postavljaju zahteve redom navedenim u drugoj koloni, pri čemu oznaka npr. A-Rd označava da proces A postavlja zahtev za otvaranjem fajla za čitanje, a B-Wr da proces B postavlja zahtev za otvaranjem fajla za upis

1. A-Rd, B-Wr, C-Rd, D-Rd, E-Wr

2. A-Wr, B-Rd, C-Wr, D-Rd, E-Rd

=== Rešenje ===
U 1. slučaju A, C i D su uspeli da otvore fajl.

U 2. slučaju samo A je uspeo da otvori fajl.

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem koristi indeksirani pristup alokaciji blokova za fajlove sa indeksima u dva nivoa. Prvi nivo indeksa smešten je u sam FCB (''file control block'') i ima 256 ulaza koji direktno referenciraju blokove sa podacima, a još jedan ulaz u FCB ukazuje na jedan blok sa indeksom drugog nivoa čiji ulazi takođe ukazuju na blokove sa podacima. Veličina ulaza u indeksnom bloku (reference na blok diska) je 8 bajtova, a veličina bloka na disku je 512KB. Kolika je maksimalna veličina fajla u ovom fajl sistemu?

=== Rešenje ===
512KB / 8B = 64K ulaza

(256 + 2^16) * 512KB = 2^27 + 2^35 = 32GB + 128MB = 32.125GB

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

ОС1/Септембар 2014

2021-10-03T13:58:09Z

IvnSvc: /* Rešenje */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2014/sep/OS1%20Sep%202014.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Šta je multiprocesni, a šta multiprocesorski operativni sistem?

=== Rešenje ===
Multiprocesni OS je OS koji podržava izvršavanje više procesa uporedo (nad istim procesorom).

Multiprocesorski sistem je računarski sistem sa više procesora koji imaju deljenu memoriju. Procesori mogu da pristupaju toj deljenoj memoriji preko zajedničke magistrale na koju su povezani.

== 2. zadatak ==
=== Postavka ===
Korišćenjem operacije <code>yield(PCB* old, PCB* new)</code> koja čuva kontekst izvršavanja prvog i restaurira kontekst izvršavanja drugog datog procesa, implementirati operaciju ''wait'' na semaforu koji je realizovan klasom <code>Semaphore</code> poput one u školskom jezgru.

=== Rešenje ===
<syntaxhighlight lang = "c">
Semaphore::wait() {
lock();
if(--val < 0) {
PCB* old = Thread::running->myPCB;
blocked.put(Thread::running);
Thread::running = Scheduler::get();
PCB* new = Thread::running->myPCB;
yield(old, new);
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Na jeziku C, korišćenjem sistemskih poziva <code>fork()</code> i <code>execlp()</code> za Unix, napisati program koji pokreće drugi program iz fajla čiji je naziv zadat kao parametar komandne linije prvog programa.

=== Rešenje ===
<syntaxhighlight lang = "c">
int main(int argc, char* argv[]) {
if(argc < 2)
return -1;
int pid = fork();
if(pid < 0)
return -2;
else if(pid == 0) {
execlp(argv[1]);
return -3;
}
else
wait(0);
return 0;
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Korišćenjem standardnih brojačkih semafora u školskom jezgru, na jeziku C++ napisati globalne deklaracije i inicijalizacije, kao i kod tela dve uporedne niti A i B koje ciklično rade sledeće:

A: upisuje vrednost u deljene promenljive x i y, a zatim čeka da proces B upiše zbir x i y u promenljivu z čiju vrednost onda ispisuje na standardni izlaz;

B: čeka da proces A upiše vrednosti u deljene promenljive x i y, zatim ove dve vrednosti sabira i zbir upisuje u deljenu promenljivu z.

=== Rešenje ===
<syntaxhighlight lang = "c">
#include <iostream>

Semaphore semA(0), semB(0);
int x, y, z;

class A : public Thread {
protected:
void run() {
while(1) {
x = ...
y = ...
semB.signal();
semA.wait();
}
}
};

class B : public Thread {
protected:
void run() {
while(1) {
semB.wait();
z = x + y;
semA.signal();
}
}
};
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Šta je osnovni razlog za to da linker obavlja zadatak u dva prolaza? Precizno objasniti.

=== Rešenje ===
U prvom prolazu linker analizira ulazne fajlove, veličinu njihovog binarnog sadržaja i pravi maou izvršivog fajla. U tabelu simbola unosi sve izvezene simbole iz objektnih fajlova za koje može da izračuna adresu u odnosu na ceo izvršivi fajl.
U drugom prolazu linker generiše binarni kod i ujedno razrešava nerazrešena adresna polja mašinskih instrukcija na osnovu informacija o adresama u koje se premeštaju simboli iz tabele simbola.

== 6. zadatak ==
=== Postavka ===
Navesti najmanje tri sličnosti (npr. zajednički zahtevi, ograničenja ili problemi) između kontinualne alokacije memorije i segmentne alokacije memorije procesa.

=== Rešenje ===
# OS mora da organizuje i održava strukturu podataka za evidenciju slobodnih fragmenata
# OS mora da sprovodi neku od tehnika dinamičke alokacije
# problem eksterne fragmentacije

== 7. zadatak ==
=== Postavka ===
Kojom tehnikom se nedeljivi uređaj može učiniti virtuelno deljivim? Navesti klasičan primer takvog uređaja za koji se najčešće primenjuje ova tehnika.

=== Rešenje ===
Spooling-om. Klasičan primer je štampač.

== 8. zadatak ==
=== Postavka ===
U fajl podsistemu nekog operativnog sistema ne vodi se tabela otvorenih fajlova za svaki proces, već postoji samo jedna globalna tabela otvorenih fajlova za ceo sistem. Drugim rečima, ne postoji nikakva informacija o upotrebi otvorenog fajla lokalna (privatna) za pojedinačni proces, već su sve takve informacije globalno deljene. Da li pojam pokazivača trenutne lokacije (kurzora) za čitanje/upis u fajl ima smisla čuvati u globalnoj tabeli otvorenih fajlova i zašto?

=== Rešenje ===
Не, јер се више различитих процеса могу имати различиту вредност курзора.

== 9. zadatak ==
=== Postavka ===
Dati procenu kompleksnosti datih operacija sa direktorijumom u odnosu na broj postojećih fajlova n u direktorijumu, za navedene implementacije direktorijuma, ukoliko u slučaju hash tabele nema nijedne kolizije.

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

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem koristi indeksirani pristup alokaciji fajlova sa indeksima u dva nivoa, blokom veličine 256KB i 64-bitnim adresama fizičkih blokova. Kolika je maksimalna veličina fajla u ovom sistemu?

=== Rešenje ===
Broj ulaza: 256KB / 8B = 2^15

Maksimalna veličina fajla: 2^15 * 2^15 * 2^18 = 2^48

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

ОС1/Септембар 2012

2021-10-03T13:56:40Z

IvnSvc: /* Rešenje */ Base и Limit за контекст континуалне алокације

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

== 1. zadatak ==
=== Postavka ===
Kod kakvih sistema se najpre pojavljuje ''time sharing'' i sa kakvim motivom?

=== Rešenje ===
Time sharing se najpre pojavljuje kod interaktivnih višekorisničkih sistema. Motiv je da se postigne ravnomerniji odziv na akcije više korisnika nego bez time sharing-a.

== 2. zadatak ==
=== Postavka ===
Korišćenjem funkcija <code>setjmp</code> i <code>longjmp</code> iz standardne C biblioteke realizovati operaciju <code>wait</code> na binarnom semaforu u školskom jezgru

=== Rešenje ===
Videti zadatak iz [[ОС1/Јул 2012#2. zadatak|julskog roka 2012]].

== 3. zadatak ==
=== Postavka ===
Korišćenjem sistemskih poziva <code>fork()</code> i <code>execlp()</code> napisati program ''P'' koji pokreće proces nad programom u fajlu čiji je naziv zadat kao argument izvršavanja programa ''P''.

=== Rešenje ===
<syntaxhighlight lang = "c">
int main(int argc, char* argv[]) {
if(argc < 2) return -1;
pid_t pid = fork();
if(pid < 0) return -2;
if(pid == 0) {
execlp(argv[1]);
return -3;
}
else wait(0);
return 0;
}
</syntaxhighlight>

== 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 ===
Videti zadatak iz [[ОС1/Фебруар 2012#4. zadatak|februarskog roka 2012]].

== 5. zadatak ==
=== Postavka ===
Koja dva podatka čine memorijski kontekst procesa kod kontinualne alokacije memorije za proces sa dinamičkim preslikavanjem adresa?

=== Rešenje ===
SegmentBase ponter - говори која је почетна адреса од које се пресликава меморија <br>
limit Pointer - садржи или величину сегмента или последњу адресу у њему, зависно од имплементације хардвера

== 6. zadatak ==
=== Postavka ===
Virtuelni adresni prostor sistema je 8GB, adresibilna jedinica je 16-bitna reč, a virtuelni adresni prostor je organizovan stranično sa stranicom veličine 32KB. Fizički adresni prostor je veličine 2GB. Tabele preslikavanja stranica su organizovane u dva nivoa, s tim da tabela drugog nivoa ima 1K ulaza. Ako deskriptori u PMT i prvog i drugog nivoa sadrže samo broj okvira u koji se stranica preslikava i ništa više (posebna vrednost označava da preslikavanje nije moguće), koliko bajtova zauzima jedna PMT prvog, a koliko drugog nivoa?

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

== 7. zadatak ==
=== Postavka ===
Zaokružiti slovo ispred one ili onih podataka koji ''nisu'' neophodni u deskriptoru stranice u PMT koji koristi hardver za preslikavanje adresa kod virtuelne memorije:
#Informacija da preslikavanje nije moguće izvršiti
#Adresa bloka na disku u kome se nalazi stranica
#Informacija da je stranica deljena sa drugim procesom tehnikom copy-on-write
#Informacija da je stranica zabranjena za izbacivanje jer se koristi kao I/O bafer
#Da li je dozvoljen upis u stranicu
#Broj okvira u koji se stranica preslikava.

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

== 8. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji prenosi blok podataka zadate dužine na zadatu adresu sa ulaznog uređaja korišćenjem programiranog ulaza/izlaza sa prozivanjem (''polling'').

=== Rešenje ===
<syntaxhighlight lang = "asm">
main: LD R1, blockAddr
LD R2, cnt
ST [ctrl], #0..1
wait: LD R0, [status]
AND R0, #1..0
JZ wait
LD R0, [data]
INC R1
DEC R2
JNZ wait
ST [ctrl], #0
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
U fajl podsistemu nekog operativnog sistema ne vodi se tabela otvorenih fajlova za svaki proces, već postoji samo jedna globalna tabela otvorenih fajlova za ceo sistem. Drugim rečima, ne postoji nikakva informacija o upotrebi otvorenog fajla lokalna (privatna) za pojedinačni proces, već su sve takve informacije globalno deljene. Kako treba da izgleda API funkcija za čitanje bloka podataka dužine <code>len</code> iz nekog fajla, da bi se procesu obezbedila mogućnost sekvencijalnog čitanja svih podataka iz fajla?

=== Rešenje ===
<syntaxhighlight lang = "c">
IOStatus readFile(FHANDLE fh, void* buffer, long len, long offset);
</syntaxhighlight>

== 10. zadatak ==
=== Postavka ===
Posmatra se disk kapaciteta 80MB i blokom veličine 1KB. Ako se za evidenciju slobodnog prostora koristi bit-vektor sa maksimalnom kompakcijom (svih 8 bita u bajtu su iskorišćeni itd.), koliko celih blokova treba zauzeti na disku za smeštanje ovog vektora?

=== Rešenje ===
80MB / 1KB = 80K blokova

80K / 8b/B = 10KB

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

ОС1/Октобар 2012

2021-10-03T13:53:09Z

IvnSvc: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta je multiprocesorski, a šta distribuirani sistem?

=== Rešenje ===
Мултипроцесорски систем је сиситем у коме више процесора раде над истом оперативном меморијом.<br>
Дистрибуирани систем је систем у коме више одвојених рачунара уз помоћ рачунарских мрежа чини једну логичку целину.

== 2. zadatak ==
=== Postavka ===
Data je operacija <code>yield(jmp_buf old, jmp_buf new)</code> koja čuva kontekst niti čiji je <code>jmp_buf</code> dat kao prvi argument, oduzima joj procesor i restaurira kontekst niti čiji je <code>jmp_buf</code> dat kao drugi argument, kojoj predaje procesor. Koristeći ovu operaciju, realizovati operaciju <code>dispatch()</code> koja ima isti efekat kao i ona data u školskom jezgru.

=== Rešenje ===
<syntaxhighlight lang="c">
void dispatch () {
lock();
jmp_buf old = Thread::running->context;
Scheduler::put(Thread::running);
Thread::running = Scheduler::get();
jmp_buf new = Thread::running->context;
yield(old,new);
unlock();
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Kako se u kodu koji se izvršava nakon sistemskog poziva <code>fork()</code> može znati da li se taj kod izvršava u kontekstu procesa-roditelja ili procesa-deteta? Objasniti i dati primer.

=== Rešenje ===
Može se znati u kom se kontekstu izvršava kod na osnovu povratne vrednosti fork-a. Tj. 0 u kontekstu deteta, vrednost veća od 0 u kontekstu roditelja, a manja od 0 ako dođe do greške.

<syntaxhighlight lang="c">
int main(int argc, char* argv[]) {
pid_t pid = fork();

if(pid < 0) {
return -1;
// greska
}
else if(pid == 0) {
// dete
}
else {
// roditelj
}

return 0;

}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Napisati kod jednog od dva procesa koji pristupaju kritičnoj sekciji sa međusobnim isključenjem pomoću uposlenog čekanja (''busy waiting'') Petersonovim algoritmom

=== Rešenje ===
<syntaxhighlight lang="ada">
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 ===
Date su sledeće deklaracije u jednom izvornom C fajlu. Koji od ovih simbola će biti označeni kao „izveženi“, a koji kao „uveženi“ u .obj fajlu?
<syntaxhighlight lang="c">
extern int a(int);
void b(int);
void b(int) {}
void c(int);
extern int d;
static int e;
int f;
</syntaxhighlight>

=== Rešenje ===
Uveženi: a, c, d
Izveženi: b, f

== 6. zadatak ==
=== Postavka ===
Neki sistem koristi kontinualnu alokaciju operativne memorije. Data je deklaracija strukture podataka koja predstavlja zaglavlje svakog slobodnog fragmenta memorije. Ova zaglavlja čine dvostruko ulančanu listu slobodnih fragmenata i upisuju se na sam početak svakog slobodnog fragmenta memorije. Napisati telo funkcije <code>getFirstFitFragment()</code> koja treba da pronađe fragment slobodne memorije veličine date argumentom po ''first-fit'' algoritmu i vrati njegovu adresu. Preostali deo fragmenta treba da postane novi (manji) fragment u listi slobodnih
<syntaxhighlight lang="c">
typedef unsigned int size_t;
struct FreeFragment {
size_t size; // Veličina fragmenta u jedinicama sizeof(char)
FreeFragment* prev; // Prethodni u listi
FreeFragment* next; // Sledeći u listi
}
FreeFragment* head; // Glava liste slobodnih fragmenata
void* getFirstFitFragment(size_t);
</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="c">
void* getFirstFitFragment(size_t sz) {
if(head == 0 || sz == 0) return 0;
for(FreeFragment* cur = head; cur; cur = cur->next) {
if(cur->size < sz) continue;
FreeFragment* newFrg = (FreeFragment*)((char*)cur + sz);
if(cur->prev) cur->prev->next = newFrg;
else head = cur->next;
if(cur->next) cur->next->prev = newFrg;
newFrg->prev = curr->prev;
newFrg->next = curr->next;
newFrg->size = cur->size - sz;
return cur;
}
return 0;
}
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Objasniti šta je osnovni motiv i pogodnost tehnike straničenja u više nivoa u odnosu na straničenje u jednom nivou?

=== Rešenje ===
Veći kapacitet virtuelne memorije.

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

== 9. zadatak ==
=== Postavka ===
Neki proces otvara neki fajl samo za čitanje, iako „vlasnik“ tog procesa ima i pravo upisa u taj fajl. Da li se informacija da je taj proces otvorio taj fajl samo za čitanje čuva u tabeli otvorenih fajlova koja je globalna za sve procese, ili u onoj koja je lokalna za taj proces

=== Rešenje ===
Ta informacija čuva se u tabeli otvorenih fajlova lokalnoj za taj proces.

== 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 tako da je svaki fajl maksimalne veličine takve da ima samo jedan indeksni klaster, koliki procenat ukupnog prostora za smeštanje fajlova na ovom disku zauzimaju indeksi?

=== Rešenje ===
32GB / 2KB = 16M = 2^24 -> 3B adresa

2KB / 3B = 682 ulaza u indeksu

procenat zauzetosti: 100/(682 + 1)%

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

ОС1/Октобар 2011

2021-10-03T13:51:21Z

IvnSvc: /* Rešenje */ Проверити, а би требало бити вишеструко дефинисано, а б недефинисано

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2011/oktobar/Okt%202011.doc Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Ukratko objasniti osnovni motiv uvođenja raspodele vremena (''time sharing'') u multiprogramiranje.

=== Rešenje ===
U zavisnosti od toga u kom hronološkom poretku su se dogodile akcije korisnika, što je potpuno proizvoljno, korisnici bi dobijali odzive nakon različitog vremena i zavisili bi od broja i aktivnosti drugih korisnika, te bi korisnici imali osećaj da smetaju jedni drugima. Mehanizmom raspodele vremena korisniku se odaje utisak da računar radi samo za njega sa dovoljno dobrim i ujednačenim vremenom odziva, iako opslužuje više korisnika istovremeno.

== 2. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji vrši učitavanje bloka podataka sa ulaznog uređaja tehnikom programiranog ulaza korišćenjem prekida. Samostalno usvojiti potrebne detaljne pretpostavke.

=== Rešenje ===
<syntaxhighlight lang="asm">
main: LD R1, blockAddr
LD R2, count
LD R3, #0
ST [ctrl], #00..01
wait: CMP R3, #1
JNZ wait
HALT

intr: LD R0, [data]
ST [R1], R0
INC R1
DEC R2
JNZ ret
LD R3, #1
ST [ctrl], #0
ret: RTI
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Navesti najmanje četiri uzroka zbog kojih proces može izgubiti procesor. Za svaki od navedenih načina navesti da li se dešava sinhrono (kao posledica operacije koju je izvršio sam proces) ili asinhrono (nezavisno od izvršavanja procesa).

=== 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 ===
Korišćenjem standardnih brojačkih semafora u školskom jezgru, na jeziku C++ u potpunosti realizovati klasu za ograničeni bafer (''bounded buffer'').

=== Rešenje ===
Videti zadatak iz [[ОС1/Јул 2011#4. zadatak|julskog roka 2011]].

== 5. zadatak ==
=== Postavka ===
Dati primer delova koda dva fajla sa izvornim C/C++ kodom za koje će linker generisati grešku tipa višestrukih simbola i nedefinsanih simbola, pod pretpostavkom da su to jedina dva fajla koja se linkuju.

=== Rešenje ===
<syntaxhighlight lang="c">
//a.h
#include "b.h"

int a;

int main(void) {
cout<<b;
return 0;
}

/////////////////////////////////////////////

//b.h

double a;

int function(){
a=12;
return 0;
}

</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Virtuelna memorija nekog računara organizovana je stranično. Veličina virtuelnog adresnog prostora je 2 MB, adresibilna jedinica je 16-bitna reč, a veličina stranice je 128 KB. Veličina fizičkog adresnog prostora je 32 MB. Operativni sistem učitava stranice na zahtev, tako što se stranica učitava u prvi slobodni okvir fizičke memorije kada joj se pristupi. Kada se kreira proces, ni jedna njegova stranica se ne učitava odmah, već tek kad joj se prvi put pristupi. U početnom trenutku, slobodni okviri fizičke memorije su okviri počev od 10h zaključno sa 1Fh. Neki proces generiše sledeću sekvencu virtuelnih adresa tokom svog izvršavanja (sve vrednosti su heksadecimalne):

30F00, 30F02, 30F04, 922F0, 922F2, 322F0, 322F2, 322F4, 522F0, 522F2, 402F0, 402F2

Prikazati izgled cele tabele preslikavanja stranica (PMT) za ovaj proces nakon izvršavanja ove sekvence. Za svaki ulaz u PMT prikazati indikator prisutnosti stranice u fizičkoj memoriji (0 ili 1) i broj okvira u fizičkoj memoriji u koji se stranica preslikava, ukoliko je stranica učitana; ukoliko nije, prikazati samo ovaj indikator.

=== Rešenje ===
VAS: 2MB = 2^21B -> VA: 20b

page = 128KB = 64K AU -> 16b

VA: page(4) : offset(16)

== 7. zadatak ==
=== Postavka ===
Navesti tipične operacije apstrakcije blokovski orijentisanog ulazno/izlaznog uređaja sa direktnim pristupom.

=== Rešenje ===
Tipične operacije su:
*<code>int readBlock(BlockNo block, void* buffer);</code>
*<code>int writeBlock(BlockNo block, void* buffer);</code>

== 8. zadatak ==
=== Postavka ===
Neki proces izvršava sistemski poziv za upis u fajl koji je prethodno uspešno otvorio i sistem mu to ne dozvoljava, sa porukom da tom procesu nije dozvoljena ta operacija, iako je korisniku u čije ime se taj proces izvršava dozvoljena operacija upisa u taj fajl. Objasnite zašto se ovo dogodilo.

=== Rešenje ===
Fajl je otvoren u režimu čitanja.

== 9. zadatak ==
=== Postavka ===
Šta znači termin „presna particija“ (''raw partition'')?

=== Rešenje ===
Presna particija je particija koja nije formatizovana, na njoj nije organizovan fajl sistem. Može se upotrebljavati za posebne namene, npr. za zamenu stranica.

== 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,
#kontinualna

=== Rešenje ===
# ''n''
# ''1''

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

ОС1/Јун 2011

2021-10-03T13:45:36Z

IvnSvc: /* Rešenje */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2011/jun/Jun%202011.doc Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Dati kratke definicije multiprocesorskog sistema i distribuiranog sistema.

=== Rešenje ===
Multiprocesorski sistem je računarski sistem sa više procesora koji imaju zajedničku (deljenu) operativnu memoriju (''engl. shared memory''). Procesori mogu da pristupaju toj deljenoj memoriji, tj. da čitaju iz nje i u nju upisuju, npr. preko zajedničke magistrale na koju su povezani.

Distribuirani sistem je računarski sistem sa više procesora koji nemaju zajedničku operativnu memoriju, već svaki procesor ima svoju, ali su svi povezani komunikacionom mrežom.

== 2. zadatak ==
=== Postavka ===
Koji je razlog deobe procesorskog vremena (''time sharing'') kod interaktivnih sistema?

=== Rešenje ===
Ravnomerniji odziv na akcije više korisnika nego bez deobe vremena.

== 3. zadatak ==
=== Postavka ===
Zašto je stek deo konteksta izvršavanja programa?

=== Rešenje ===
Stek predstavlja deo konteksta izvršavanja programa zato što se prilikom poziva bilo kog potprograma u programu na steku pamti mesto odakle je potprogram pozvan kako bi se po povratku moglo nastaviti odakle se stalo.

== 4. zadatak ==
=== Postavka ===
Napisati deo koda koji obezbeđuje kritičnu sekciju pomoću brojačkih semafora, uz dozvolu konkurentnog izvršavanja kritične sekcije do ''N'' uporednih procesa.

=== Rešenje ===
<syntaxhighlight lang="ada">
var mutex : Semaphore := N;
process P
begin
loop
wait(mutex);
<critical section>
signal(mutex);
<non-critical section>
end
end P
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Korišćenjem sistemskih poziva <code>fork()</code> i <code>execlp()</code> napisati C program koji kreira proces nad programom u fajlu čije je ime zadato argumentom komandne linije.

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

pid_t pid = fork();

if(pid < 0)
return -2;
else if(pid == 0)
execlp(argv[1]);
else wait(0);

return 0;

}
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Memorija nekog računara organizovana je stranično, sa stranicom veličine 4KB. Adresibilna jedinica je bajt, a virtuelna adresa je 32-bitna. Fizička adresa je veličine 32 bita. Ako je PMT organizovana u dva nivoa, s tim da su veličine polja za broj ulaza u tabele oba nivoa isti, kolika je veličina (u bajtovima) PMT prvog nivoa?

=== Rešenje ===
VA(32): 10,10,12<br>
Улаз је величине 32b тј 4В <br>
<math> 2^{10} \cdot 4B = 2^{12}B </math>

== 7. zadatak ==
=== Postavka ===
Da li linker prilikom povezivanja sa ciljem dobijanja izvršnog programa (.exe) pravi razliku između fajlova tipa .obj i tipa .lib?

=== Rešenje ===
Linker ne pravi razliku između .obj i .lib fajlova prilikom povezivanja. Razlika je jedino što je .obj fajl nastao prevođenjem jednog fajla dok je lib fajl nastao povezivanjem više objektnih, moguće i više drugih fajlova.

== 8. zadatak ==
=== Postavka ===
Kojom tehnikom se znakovno orijentisani ulazni uređaj može učiniti logički (virtuelno) blokovski orijentisanim?

=== Rešenje ===
Tehnikom baferisanja.

== 9. zadatak ==
=== Postavka ===
Neki proces izvršava redom sledeće sistemske pozive. Pod pretpostavkom da korisnik u čije ime se izvršava ovaj proces ima pravo pristupa do oba fajla i na čitanje i na upis, i da oba poziva za otvaranje fajlova uspevaju, navesti koji od preostalih poziva će biti uspešan, a koji neuspešan (upisati na liniji pored poziva).
<syntaxhighlight lang="c">
FHANDLE f1 = fopen(“x.doc”,read);
FHANDLE f2 = fopen(“y.doc”,read|write);
</syntaxhighlight>
#<code>fread(f1,buffer1,n1);</code>
#<code>fwrite(f1,buffer2,n2);</code>
#<code>fread(f2,buffer1,n1);</code>
#<code>fwrite(f2,buffer2,n2);</code>

=== Rešenje ===
#uspešan
#neuspešan
#uspešan
#uspešan

== 10. zadatak ==
=== Postavka ===
Korišćenjem podataka iz koje tabele otvorenih fajlova sistem proverava pravo pristupa za pozive iz prethodnog zadatka (<code>fread</code> i <code>fwrite</code>), u globalnoj tabeli ili u tabeli koja je deo konteksta datog procesa?

=== Rešenje ===
U tabeli koja je kontekst datog procesa.

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

ОС1/Јул 2019

2021-10-03T13:42:32Z

IvnSvc: /* 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/Јануар 2013

2021-10-03T13:38:30Z

IvnSvc: /* Rešenje */ Опис copyOnWrite

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

== 1. zadatak ==
=== Postavka ===
Šta je to multiprocesorski sistem, a šta distribuirani sistem? Navesti po jedan primer svakog.

=== Rešenje ===
Videti zadatak iz [[ОС1/Јул 2012#1. zadatak|julskog roka 2012]].

== 2. zadatak ==
=== Postavka ===
Korišćenjem funkcije <code>yield(jmp_buf old, jmp_buf new)</code> koja čuva kontekst jedne niti i predaje procesor drugoj niti, realizovati operaciju <code>wait</code> na brojačkom semaforu u školskom jezgru.

=== Rešenje ===
<syntaxhighlight lang="c">
void Semaphore::wait() {
lock(lck);
if(--val < 0) {
jmp_buf old = Thread::running->context;
blocked.put(Thread::running);
Thread::running = Scheduler::get();
jmp_buf new = Thread::running->context;
yield(old, new);
}
unlock(lck);
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Navesti najmanje tri slučaja (povoda) u kojima proces gubi procesor i prelazi u red suspendovanih (blokiranih) i naznačiti da li se to dešava kao posledica sistemskog poziva tog procesa ili spoljašnjeg prekida

=== Rešenje ===
#Zbog operacije na sinhronizacionoj primitivi, tj. na semaforu ili događaju
#Prilikom eksplicitnog poziva metode koja čeka da se nit/niti završe (join npr.)
#Pri sinhronoj I/O operaciji, posledica sistemskopg poziva tog procesa

== 4. zadatak ==
=== Postavka ===
Napisati kod koji realizuje Petersonov algoritam međusobnog isključenja dva uporedna procesa pomoću uposlenog čekanja.

=== 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>
flag1 := false
<non-critical>
end
end P1;

process P2
begin
loop
flag2 = true; turn := 1;
while flag1 and turn = 1 do null;
<critical>
flag2 := false
<non-critical>
end
end P2;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
U čemu je razlika između tehnika dinamičkog učitavanja (''dynamic loading'') i preklopa (''overlay'')?

=== Rešenje ===
Videti zadatak iz [[ОС1/Јул 2011#5. zadatak|julskog roka 2012]].

== 6. zadatak ==
=== Postavka ===
Virtuelni adresni prostor sistema je 8GB, adresibilna jedinica je 16-bitna reč, a virtuelni adresni prostor je organizovan stranično sa stranicomveličine 32KB. Fizički adresni prostor je veličine 2GB. Tabele preslikavanja stranica su organizovaneu dva nivoa, s tim da tabela prvog nivoa ima 2K ulaza. Prikazati logičku strukturu virtuelneadresei označiti širinu svakog polja. Označiti i podelu polja za broj stranice na polja zaindeksiranje PMT prvog i drugog nivoa.
=== Rešenje ===

PA:frame(16),offset(14)

VA:PMT1(11),PMT2(7),offset(14)

== 7. zadatak ==
=== Postavka ===
Neki sistem sa straničnom organizacijom memorije koristi tehniku ''copy on write''. Jedan proces je tek kreirao drugi proces pozivom <code>fork()</code>. Ako novokreirani proces odmah po pokretanju izvrši operaciju upisa u memoriju, koji izuzetak će generisati procesor, ''page fault'' ili neki drugi i koji? Precizno objasniti zašto i kako.
=== Rešenje ===
Десиће се "access violeation", јер процес има све странице тренутно учитане, али у њиховим дескрипторима у PMT je записано да се у њих несме уписивати, ОС погледа у описе сегмената и види да је дозвољен упис у ту страницу па је закључак да се она тренутно дели са неким другим процесом, страница ће се копирати и у ту нову копију, чији је власник тренутни процес, ће бити извршен упис.

== 8. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji prenosi blok podataka zadate dužine sa zadate adrese na izlazni uređaj korišćenjem programiranog ulaza/izlaza sa prozivanjem (''polling'').

=== Rešenje ===
<syntaxhighlight lang="asm">
main: LD R1, blockAddr
LD R2, cnt
ST [ctrl], #0..1
wait: LD R0, [status]
AND R0, #1..0
JZ wait
LD R0, [R1]
ST [data], R0
INC R1
DEC R2
JNZ wait
ST [ctrl], #0
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Šta je osnovna svrha (motiv) postojanja operacije otvaranja fajla?

=== Rešenje ===
Svrha toga jeste da pri svakom obraćanju fajlu ne koristimo njegovo ime već koristimo ID u nizu fajl deskriptora koji sadrže pokazivače deskriptor u tabeli otvorenih fajlova koja sadrži pokazivač na FCB datog fajla.

== 10. zadatak ==
=== Postavka ===
Navesti i objasniti neku tehniku organizacije strukture podataka za rukovanje slobodnim prostorom fajl sistema na disku, osim bit-vektora.

=== Rešenje ===
Slobodni blokovi se mogu grupisati tako da prvi blok u grupi slobodnih sadrži pokazivač na naredne slobodne blokove.

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

ОС1/Јануар 2013

2021-10-03T13:34:02Z

IvnSvc: /* Rešenje */ Додат још један разлог блокирања процеса (трећи), чекање на И/О

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

== 1. zadatak ==
=== Postavka ===
Šta je to multiprocesorski sistem, a šta distribuirani sistem? Navesti po jedan primer svakog.

=== Rešenje ===
Videti zadatak iz [[ОС1/Јул 2012#1. zadatak|julskog roka 2012]].

== 2. zadatak ==
=== Postavka ===
Korišćenjem funkcije <code>yield(jmp_buf old, jmp_buf new)</code> koja čuva kontekst jedne niti i predaje procesor drugoj niti, realizovati operaciju <code>wait</code> na brojačkom semaforu u školskom jezgru.

=== Rešenje ===
<syntaxhighlight lang="c">
void Semaphore::wait() {
lock(lck);
if(--val < 0) {
jmp_buf old = Thread::running->context;
blocked.put(Thread::running);
Thread::running = Scheduler::get();
jmp_buf new = Thread::running->context;
yield(old, new);
}
unlock(lck);
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Navesti najmanje tri slučaja (povoda) u kojima proces gubi procesor i prelazi u red suspendovanih (blokiranih) i naznačiti da li se to dešava kao posledica sistemskog poziva tog procesa ili spoljašnjeg prekida

=== Rešenje ===
#Zbog operacije na sinhronizacionoj primitivi, tj. na semaforu ili događaju
#Prilikom eksplicitnog poziva metode koja čeka da se nit/niti završe (join npr.)
#Pri sinhronoj I/O operaciji, posledica sistemskopg poziva tog procesa

== 4. zadatak ==
=== Postavka ===
Napisati kod koji realizuje Petersonov algoritam međusobnog isključenja dva uporedna procesa pomoću uposlenog čekanja.

=== 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>
flag1 := false
<non-critical>
end
end P1;

process P2
begin
loop
flag2 = true; turn := 1;
while flag1 and turn = 1 do null;
<critical>
flag2 := false
<non-critical>
end
end P2;
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
U čemu je razlika između tehnika dinamičkog učitavanja (''dynamic loading'') i preklopa (''overlay'')?

=== Rešenje ===
Videti zadatak iz [[ОС1/Јул 2011#5. zadatak|julskog roka 2012]].

== 6. zadatak ==
=== Postavka ===
Virtuelni adresni prostor sistema je 8GB, adresibilna jedinica je 16-bitna reč, a virtuelni adresni prostor je organizovan stranično sa stranicomveličine 32KB. Fizički adresni prostor je veličine 2GB. Tabele preslikavanja stranica su organizovaneu dva nivoa, s tim da tabela prvog nivoa ima 2K ulaza. Prikazati logičku strukturu virtuelneadresei označiti širinu svakog polja. Označiti i podelu polja za broj stranice na polja zaindeksiranje PMT prvog i drugog nivoa.
=== Rešenje ===

PA:frame(16),offset(14)

VA:PMT1(11),PMT2(7),offset(14)

== 7. zadatak ==
=== Postavka ===
Neki sistem sa straničnom organizacijom memorije koristi tehniku ''copy on write''. Jedan proces je tek kreirao drugi proces pozivom <code>fork()</code>. Ako novokreirani proces odmah po pokretanju izvrši operaciju upisa u memoriju, koji izuzetak će generisati procesor, ''page fault'' ili neki drugi i koji? Precizno objasniti zašto i kako.
=== Rešenje ===
{{delimično rešeno}}

== 8. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji prenosi blok podataka zadate dužine sa zadate adrese na izlazni uređaj korišćenjem programiranog ulaza/izlaza sa prozivanjem (''polling'').

=== Rešenje ===
<syntaxhighlight lang="asm">
main: LD R1, blockAddr
LD R2, cnt
ST [ctrl], #0..1
wait: LD R0, [status]
AND R0, #1..0
JZ wait
LD R0, [R1]
ST [data], R0
INC R1
DEC R2
JNZ wait
ST [ctrl], #0
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Šta je osnovna svrha (motiv) postojanja operacije otvaranja fajla?

=== Rešenje ===
Svrha toga jeste da pri svakom obraćanju fajlu ne koristimo njegovo ime već koristimo ID u nizu fajl deskriptora koji sadrže pokazivače deskriptor u tabeli otvorenih fajlova koja sadrži pokazivač na FCB datog fajla.

== 10. zadatak ==
=== Postavka ===
Navesti i objasniti neku tehniku organizacije strukture podataka za rukovanje slobodnim prostorom fajl sistema na disku, osim bit-vektora.

=== Rešenje ===
Slobodni blokovi se mogu grupisati tako da prvi blok u grupi slobodnih sadrži pokazivač na naredne slobodne blokove.

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

ОС1/Јануар 2012

2021-10-03T13:31:17Z

IvnSvc: /* Rešenje */ Пошто је ФАТ у једном блоку, онда имамо само један приступ, по тражени блок у фајлу

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

== 1. zadatak ==
=== Postavka ===
Ukratko objasniti osnovni motiv uvođenja multiprogramiranja u računarske sisteme.

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

== 2. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji vrši prenos bloka podataka iz memorije na izlazni uređaj tehnikom programiranog izlaza korišćenjem prozivanja (''polling''). Samostalno usvojiti potrebne detaljne pretpostavke.

=== Rešenje ===
<syntaxhighlight lang="asm">
LD R1, blockAddr
LD R2, cnt
ST [ctrl], #00..01
wait: LD R0, [status]
AND R0, #1
JZ wait

LD R0, [R1]
ST [data], R0
INC R1
DEC R2
JNZ wait
ST [ctrl], #0
HALT
</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<3; i++) fork();
}
</syntaxhighlight>
=== Rešenje ===
1 + 2^N - 1 = 2^3 = 8

== 4. zadatak ==
=== Postavka ===
Korišćenjem školskog jezgra napisati kod klase koja apstrahuje nit koja, ukoliko se kreira sa neparnim celobrojnim parametrom, kreira još jednu takvu istu nit, samo sa parnim celobrojnim parametrom, a u suprotnom se samo završava.

=== Rešenje ===
<syntaxhighlight lang="asm">
class myThead : public Thread {
public:
myThead(int val) {
this->val = val;
start();
}
protected:
void run() {
if(val & 1) {
new myThead(val + 1);
}
}
private:
int val;
};
</syntaxhighlight>

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

=== Rešenje ===
#Nedefinisan simbol - nakon drugog prolaza
#Višestruko definisan simbol - tokom prvog prolaza

== 6. zadatak ==
=== Postavka ===

U nekom sistemu primenjuje se ''best-fit'' algoritam kontinualne alokacije memorije. Inicijalno je prostor veličine 256KB potpuno slobodan za alokaciju korisničkih procesa. Potom su različiti procesi zadavali sledeće zahteve (slovna oznaka označava proces koji je postavio zahtev, brojna oznaka označava veličinu alociranog prostora u KB, a minus označava gašenje procesa i oslobađanje njegove memorije)

A64, B16, C128, D32, A-, E8, F32, B-

Odgovoriti na sledeća pitanja koja se odnose na stanje memorije nakon ove sekvence zahteva:
#Koliko je ukupno slobodnih fragmenata?
#Kolika je veličina najmanjeg slobodnog fragmenta?
#Kolika je veličina najvećeg slobodnog fragmenta?

=== Rešenje ===
1. Остала су два слободна фрагмента<br>
2. Најмањи је величине 8KB<br>
3. Највећи је величине 48КВ<br>

Скица решења, једна цртица = 8KB<br>

--------------------------------<br>
AAAAAAAA------------------------<br>
AAAAAAAABB----------------------<br>
AAAAAAAABBCCCCCCCCCCCCCCCC------<br>
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF----BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF------CCCCCCCCCCCCCCCCDDDDE-<br>

== 7. zadatak ==
=== Postavka ===
Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, deskriptor stranice je 32-bitni, a PMT je organizovana u dva nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. Koliki prostor bi ukupno zauzimala PMT nekog procesa kada bi:
#Proces koristio ceo svoj virtuelni adresni prostor?
#Proces koristio samo jednu stranicu?

=== Rešenje ===

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

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

1. <math>2^8 \cdot 4B + 2^8 \cdot 2^12 \cdot 4B = 2^{10}B + 2^{22} = 1KB + 4MB</math> <br>

2. <math>2^8 \cdot 4B + 2^12 \cdot 4B = 2^{10}B + 2^{16} = 65KB</math>

== 8. zadatak ==
=== Postavka ===
Umesto tehnike ''spooling'', pristup uporednih procesa štampaču u nekom sistemu omogućuje se međusobnim isključenjem pomoću operacije rezervacije: svaki proces, pre nego što zatraži bilo koju operaciju sa štampačem, mora da ga rezerviše, a tu rezervaciju otpušta tek kada završi sa celim jednim poslom štampe. Šta je nedostatak ove tehnike?

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

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:
#<code>FHANDLE open(char* filename)</code> Otvara fajl sa datim imenom.
#<code>void close(FHANDLE)</code> Zatvara dati fajl.
#<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*)</code> Na poziciju kurzora datog fajla upisuje dati niz znakova, ne uključujući završni znak ‘\0’, i pomera kurzor iza upisanog niza znakova.
Napisati program koji na kraj postojećeg fajla sa imenom <code>proba.txt</code> upisuje sve što je uneseno preko standardnog ulaza, sve dok se na ulazu ne unese znak ’X’. Zanemariti sve potencijalne greške u ulazu/izlazu.

=== Rešenje ===

<syntaxhighlight lang="c">
#include <stdio.h>

// Исписује "Hello world!".
int main(void) {
FILE f = open("proba.txt");
char a;
int size = size(f);
while(1){
cin >> a;
if(a=='X')break;

append(f,2); //проширивање фајла, 1 за слово и 1 јер се курзор помера на место после уписаног знака
seek(f,size);
write(f,&a);

size+=2; //ажурирање тренутне величине фајла
}
return 0;
}
</syntaxhighlight>

== 10. zadatak ==
=== Postavka ===
Koliko pristupa blokovima na disku treba izvršiti za pristup ''n''-tom logičkom bloku sadržaja fajla ako je alokacija fajla:
#FAT, pri čemu je FAT uvek inicijalno učitana u memoriju prilikom montiranja fajl sistema
#indeksna, pri čemu je ceo indeks fajla u jednom bloku?

=== Rešenje ===
#1
#2

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

ОС1/Јануар 2012

2021-10-03T13:29:54Z

IvnSvc: /* Rešenje */ Ово би било добро проверити

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

== 1. zadatak ==
=== Postavka ===
Ukratko objasniti osnovni motiv uvođenja multiprogramiranja u računarske sisteme.

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

== 2. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji vrši prenos bloka podataka iz memorije na izlazni uređaj tehnikom programiranog izlaza korišćenjem prozivanja (''polling''). Samostalno usvojiti potrebne detaljne pretpostavke.

=== Rešenje ===
<syntaxhighlight lang="asm">
LD R1, blockAddr
LD R2, cnt
ST [ctrl], #00..01
wait: LD R0, [status]
AND R0, #1
JZ wait

LD R0, [R1]
ST [data], R0
INC R1
DEC R2
JNZ wait
ST [ctrl], #0
HALT
</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<3; i++) fork();
}
</syntaxhighlight>
=== Rešenje ===
1 + 2^N - 1 = 2^3 = 8

== 4. zadatak ==
=== Postavka ===
Korišćenjem školskog jezgra napisati kod klase koja apstrahuje nit koja, ukoliko se kreira sa neparnim celobrojnim parametrom, kreira još jednu takvu istu nit, samo sa parnim celobrojnim parametrom, a u suprotnom se samo završava.

=== Rešenje ===
<syntaxhighlight lang="asm">
class myThead : public Thread {
public:
myThead(int val) {
this->val = val;
start();
}
protected:
void run() {
if(val & 1) {
new myThead(val + 1);
}
}
private:
int val;
};
</syntaxhighlight>

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

=== Rešenje ===
#Nedefinisan simbol - nakon drugog prolaza
#Višestruko definisan simbol - tokom prvog prolaza

== 6. zadatak ==
=== Postavka ===

U nekom sistemu primenjuje se ''best-fit'' algoritam kontinualne alokacije memorije. Inicijalno je prostor veličine 256KB potpuno slobodan za alokaciju korisničkih procesa. Potom su različiti procesi zadavali sledeće zahteve (slovna oznaka označava proces koji je postavio zahtev, brojna oznaka označava veličinu alociranog prostora u KB, a minus označava gašenje procesa i oslobađanje njegove memorije)

A64, B16, C128, D32, A-, E8, F32, B-

Odgovoriti na sledeća pitanja koja se odnose na stanje memorije nakon ove sekvence zahteva:
#Koliko je ukupno slobodnih fragmenata?
#Kolika je veličina najmanjeg slobodnog fragmenta?
#Kolika je veličina najvećeg slobodnog fragmenta?

=== Rešenje ===
1. Остала су два слободна фрагмента<br>
2. Најмањи је величине 8KB<br>
3. Највећи је величине 48КВ<br>

Скица решења, једна цртица = 8KB<br>

--------------------------------<br>
AAAAAAAA------------------------<br>
AAAAAAAABB----------------------<br>
AAAAAAAABBCCCCCCCCCCCCCCCC------<br>
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF----BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF------CCCCCCCCCCCCCCCCDDDDE-<br>

== 7. zadatak ==
=== Postavka ===
Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, deskriptor stranice je 32-bitni, a PMT je organizovana u dva nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. Koliki prostor bi ukupno zauzimala PMT nekog procesa kada bi:
#Proces koristio ceo svoj virtuelni adresni prostor?
#Proces koristio samo jednu stranicu?

=== Rešenje ===

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

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

1. <math>2^8 \cdot 4B + 2^8 \cdot 2^12 \cdot 4B = 2^{10}B + 2^{22} = 1KB + 4MB</math> <br>

2. <math>2^8 \cdot 4B + 2^12 \cdot 4B = 2^{10}B + 2^{16} = 65KB</math>

== 8. zadatak ==
=== Postavka ===
Umesto tehnike ''spooling'', pristup uporednih procesa štampaču u nekom sistemu omogućuje se međusobnim isključenjem pomoću operacije rezervacije: svaki proces, pre nego što zatraži bilo koju operaciju sa štampačem, mora da ga rezerviše, a tu rezervaciju otpušta tek kada završi sa celim jednim poslom štampe. Šta je nedostatak ove tehnike?

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

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:
#<code>FHANDLE open(char* filename)</code> Otvara fajl sa datim imenom.
#<code>void close(FHANDLE)</code> Zatvara dati fajl.
#<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*)</code> Na poziciju kurzora datog fajla upisuje dati niz znakova, ne uključujući završni znak ‘\0’, i pomera kurzor iza upisanog niza znakova.
Napisati program koji na kraj postojećeg fajla sa imenom <code>proba.txt</code> upisuje sve što je uneseno preko standardnog ulaza, sve dok se na ulazu ne unese znak ’X’. Zanemariti sve potencijalne greške u ulazu/izlazu.

=== Rešenje ===

<syntaxhighlight lang="c">
#include <stdio.h>

// Исписује "Hello world!".
int main(void) {
FILE f = open("proba.txt");
char a;
int size = size(f);
while(1){
cin >> a;
if(a=='X')break;

append(f,2); //проширивање фајла, 1 за слово и 1 јер се курзор помера на место после уписаног знака
seek(f,size);
write(f,&a);

size+=2; //ажурирање тренутне величине фајла
}
return 0;
}
</syntaxhighlight>

== 10. zadatak ==
=== Postavka ===
Koliko pristupa blokovima na disku treba izvršiti za pristup ''n''-tom logičkom bloku sadržaja fajla ako je alokacija fajla:
#FAT, pri čemu je FAT uvek inicijalno učitana u memoriju prilikom montiranja fajl sistema
#indeksna, pri čemu je ceo indeks fajla u jednom bloku?

=== Rešenje ===
#n
#2

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

ОС1/Јануар 2012

2021-10-03T13:22:05Z

IvnSvc: /* Rešenje */ Додато решење

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

== 1. zadatak ==
=== Postavka ===
Ukratko objasniti osnovni motiv uvođenja multiprogramiranja u računarske sisteme.

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

== 2. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji vrši prenos bloka podataka iz memorije na izlazni uređaj tehnikom programiranog izlaza korišćenjem prozivanja (''polling''). Samostalno usvojiti potrebne detaljne pretpostavke.

=== Rešenje ===
<syntaxhighlight lang="asm">
LD R1, blockAddr
LD R2, cnt
ST [ctrl], #00..01
wait: LD R0, [status]
AND R0, #1
JZ wait

LD R0, [R1]
ST [data], R0
INC R1
DEC R2
JNZ wait
ST [ctrl], #0
HALT
</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<3; i++) fork();
}
</syntaxhighlight>
=== Rešenje ===
1 + 2^N - 1 = 2^3 = 8

== 4. zadatak ==
=== Postavka ===
Korišćenjem školskog jezgra napisati kod klase koja apstrahuje nit koja, ukoliko se kreira sa neparnim celobrojnim parametrom, kreira još jednu takvu istu nit, samo sa parnim celobrojnim parametrom, a u suprotnom se samo završava.

=== Rešenje ===
<syntaxhighlight lang="asm">
class myThead : public Thread {
public:
myThead(int val) {
this->val = val;
start();
}
protected:
void run() {
if(val & 1) {
new myThead(val + 1);
}
}
private:
int val;
};
</syntaxhighlight>

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

=== Rešenje ===
#Nedefinisan simbol - nakon drugog prolaza
#Višestruko definisan simbol - tokom prvog prolaza

== 6. zadatak ==
=== Postavka ===

U nekom sistemu primenjuje se ''best-fit'' algoritam kontinualne alokacije memorije. Inicijalno je prostor veličine 256KB potpuno slobodan za alokaciju korisničkih procesa. Potom su različiti procesi zadavali sledeće zahteve (slovna oznaka označava proces koji je postavio zahtev, brojna oznaka označava veličinu alociranog prostora u KB, a minus označava gašenje procesa i oslobađanje njegove memorije)

A64, B16, C128, D32, A-, E8, F32, B-

Odgovoriti na sledeća pitanja koja se odnose na stanje memorije nakon ove sekvence zahteva:
#Koliko je ukupno slobodnih fragmenata?
#Kolika je veličina najmanjeg slobodnog fragmenta?
#Kolika je veličina najvećeg slobodnog fragmenta?

=== Rešenje ===
1. Остала су два слободна фрагмента<br>
2. Најмањи је величине 8KB<br>
3. Највећи је величине 48КВ<br>

Скица решења, једна цртица = 8KB<br>

--------------------------------<br>
AAAAAAAA------------------------<br>
AAAAAAAABB----------------------<br>
AAAAAAAABBCCCCCCCCCCCCCCCC------<br>
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF----BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF------CCCCCCCCCCCCCCCCDDDDE-<br>

== 7. zadatak ==
=== Postavka ===
Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, deskriptor stranice je 32-bitni, a PMT je organizovana u dva nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. Koliki prostor bi ukupno zauzimala PMT nekog procesa kada bi:
#Proces koristio ceo svoj virtuelni adresni prostor?
#Proces koristio samo jednu stranicu?

=== Rešenje ===

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

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

1. <math>2^8 \cdot 4B + 2^8 \cdot 2^12 \cdot 4B = 2^{10}B + 2^{22} = 1KB + 4MB</math> <br>

2. <math>2^8 \cdot 4B + 2^12 \cdot 4B = 2^{10}B + 2^{16} = 65KB</math>

== 8. zadatak ==
=== Postavka ===
Umesto tehnike ''spooling'', pristup uporednih procesa štampaču u nekom sistemu omogućuje se međusobnim isključenjem pomoću operacije rezervacije: svaki proces, pre nego što zatraži bilo koju operaciju sa štampačem, mora da ga rezerviše, a tu rezervaciju otpušta tek kada završi sa celim jednim poslom štampe. Šta je nedostatak ove tehnike?

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

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:
#<code>FHANDLE open(char* filename)</code> Otvara fajl sa datim imenom.
#<code>void close(FHANDLE)</code> Zatvara dati fajl.
#<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*)</code> Na poziciju kurzora datog fajla upisuje dati niz znakova, ne uključujući završni znak ‘\0’, i pomera kurzor iza upisanog niza znakova.
Napisati program koji na kraj postojećeg fajla sa imenom <code>proba.txt</code> upisuje sve što je uneseno preko standardnog ulaza, sve dok se na ulazu ne unese znak ’X’. Zanemariti sve potencijalne greške u ulazu/izlazu.

=== Rešenje ===
{{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:
#FAT, pri čemu je FAT uvek inicijalno učitana u memoriju prilikom montiranja fajl sistema
#indeksna, pri čemu je ceo indeks fajla u jednom bloku?

=== Rešenje ===
#n
#2

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

ОС1/Јануар 2012

2021-10-03T13:12:42Z

IvnSvc: /* Rešenje */ словна грешка

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

== 1. zadatak ==
=== Postavka ===
Ukratko objasniti osnovni motiv uvođenja multiprogramiranja u računarske sisteme.

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

== 2. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji vrši prenos bloka podataka iz memorije na izlazni uređaj tehnikom programiranog izlaza korišćenjem prozivanja (''polling''). Samostalno usvojiti potrebne detaljne pretpostavke.

=== Rešenje ===
<syntaxhighlight lang="asm">
LD R1, blockAddr
LD R2, cnt
ST [ctrl], #00..01
wait: LD R0, [status]
AND R0, #1
JZ wait

LD R0, [R1]
ST [data], R0
INC R1
DEC R2
JNZ wait
ST [ctrl], #0
HALT
</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<3; i++) fork();
}
</syntaxhighlight>
=== Rešenje ===
1 + 2^N - 1 = 2^3 = 8

== 4. zadatak ==
=== Postavka ===
Korišćenjem školskog jezgra napisati kod klase koja apstrahuje nit koja, ukoliko se kreira sa neparnim celobrojnim parametrom, kreira još jednu takvu istu nit, samo sa parnim celobrojnim parametrom, a u suprotnom se samo završava.

=== Rešenje ===
<syntaxhighlight lang="asm">
class myThead : public Thread {
public:
myThead(int val) {
this->val = val;
start();
}
protected:
void run() {
if(val & 1) {
new myThead(val + 1);
}
}
private:
int val;
};
</syntaxhighlight>

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

=== Rešenje ===
#Nedefinisan simbol - nakon drugog prolaza
#Višestruko definisan simbol - tokom prvog prolaza

== 6. zadatak ==
=== Postavka ===

U nekom sistemu primenjuje se ''best-fit'' algoritam kontinualne alokacije memorije. Inicijalno je prostor veličine 256KB potpuno slobodan za alokaciju korisničkih procesa. Potom su različiti procesi zadavali sledeće zahteve (slovna oznaka označava proces koji je postavio zahtev, brojna oznaka označava veličinu alociranog prostora u KB, a minus označava gašenje procesa i oslobađanje njegove memorije)

A64, B16, C128, D32, A-, E8, F32, B-

Odgovoriti na sledeća pitanja koja se odnose na stanje memorije nakon ove sekvence zahteva:
#Koliko je ukupno slobodnih fragmenata?
#Kolika je veličina najmanjeg slobodnog fragmenta?
#Kolika je veličina najvećeg slobodnog fragmenta?

=== Rešenje ===
1. Остала су два слободна фрагмента<br>
2. Најмањи је величине 8KB<br>
3. Највећи је величине 48КВ<br>

Скица решења, једна цртица = 8KB<br>

--------------------------------<br>
AAAAAAAA------------------------<br>
AAAAAAAABB----------------------<br>
AAAAAAAABBCCCCCCCCCCCCCCCC------<br>
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF----BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF------CCCCCCCCCCCCCCCCDDDDE-<br>

== 7. zadatak ==
=== Postavka ===
Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, deskriptor stranice je 32-bitni, a PMT je organizovana u dva nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. Koliki prostor bi ukupno zauzimala PMT nekog procesa kada bi:
#Proces koristio ceo svoj virtuelni adresni prostor?
#Proces koristio samo jednu stranicu?

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

== 8. zadatak ==
=== Postavka ===
Umesto tehnike ''spooling'', pristup uporednih procesa štampaču u nekom sistemu omogućuje se međusobnim isključenjem pomoću operacije rezervacije: svaki proces, pre nego što zatraži bilo koju operaciju sa štampačem, mora da ga rezerviše, a tu rezervaciju otpušta tek kada završi sa celim jednim poslom štampe. Šta je nedostatak ove tehnike?

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

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:
#<code>FHANDLE open(char* filename)</code> Otvara fajl sa datim imenom.
#<code>void close(FHANDLE)</code> Zatvara dati fajl.
#<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*)</code> Na poziciju kurzora datog fajla upisuje dati niz znakova, ne uključujući završni znak ‘\0’, i pomera kurzor iza upisanog niza znakova.
Napisati program koji na kraj postojećeg fajla sa imenom <code>proba.txt</code> upisuje sve što je uneseno preko standardnog ulaza, sve dok se na ulazu ne unese znak ’X’. Zanemariti sve potencijalne greške u ulazu/izlazu.

=== Rešenje ===
{{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:
#FAT, pri čemu je FAT uvek inicijalno učitana u memoriju prilikom montiranja fajl sistema
#indeksna, pri čemu je ceo indeks fajla u jednom bloku?

=== Rešenje ===
#n
#2

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

ОС1/Јануар 2012

2021-10-03T13:06:34Z

IvnSvc: /* Rešenje */ Додато решење

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

== 1. zadatak ==
=== Postavka ===
Ukratko objasniti osnovni motiv uvođenja multiprogramiranja u računarske sisteme.

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

== 2. zadatak ==
=== Postavka ===
Na asembleru nekog zamišljenog RISC procesora sa LOAD/STORE arhitekturom napisati program koji vrši prenos bloka podataka iz memorije na izlazni uređaj tehnikom programiranog izlaza korišćenjem prozivanja (''polling''). Samostalno usvojiti potrebne detaljne pretpostavke.

=== Rešenje ===
<syntaxhighlight lang="asm">
LD R1, blockAddr
LD R2, cnt
ST [ctrl], #00..01
wait: LD R0, [status]
AND R0, #1
JZ wait

LD R0, [R1]
ST [data], R0
INC R1
DEC R2
JNZ wait
ST [ctrl], #0
HALT
</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<3; i++) fork();
}
</syntaxhighlight>
=== Rešenje ===
1 + 2^N - 1 = 2^3 = 8

== 4. zadatak ==
=== Postavka ===
Korišćenjem školskog jezgra napisati kod klase koja apstrahuje nit koja, ukoliko se kreira sa neparnim celobrojnim parametrom, kreira još jednu takvu istu nit, samo sa parnim celobrojnim parametrom, a u suprotnom se samo završava.

=== Rešenje ===
<syntaxhighlight lang="asm">
class myThead : public Thread {
public:
myThead(int val) {
this->val = val;
start();
}
protected:
void run() {
if(val & 1) {
new myThead(val + 1);
}
}
private:
int val;
};
</syntaxhighlight>

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

=== Rešenje ===
#Nedefinisan simbol - nakon drugog prolaza
#Višestruko definisan simbol - tokom prvog prolaza

== 6. zadatak ==
=== Postavka ===

U nekom sistemu primenjuje se ''best-fit'' algoritam kontinualne alokacije memorije. Inicijalno je prostor veličine 256KB potpuno slobodan za alokaciju korisničkih procesa. Potom su različiti procesi zadavali sledeće zahteve (slovna oznaka označava proces koji je postavio zahtev, brojna oznaka označava veličinu alociranog prostora u KB, a minus označava gašenje procesa i oslobađanje njegove memorije)

A64, B16, C128, D32, A-, E8, F32, B-

Odgovoriti na sledeća pitanja koja se odnose na stanje memorije nakon ove sekvence zahteva:
#Koliko je ukupno slobodnih fragmenata?
#Kolika je veličina najmanjeg slobodnog fragmenta?
#Kolika je veličina najvećeg slobodnog fragmenta?

=== Rešenje ===
1. Остала су два слободна фрагмента<br>
2. Најмањи је величине 8KB<br>
3. Највечи је величине 48КВ<br>

Скица решења, једна цртица = 8KB<br>

--------------------------------<br>
AAAAAAAA------------------------<br>
AAAAAAAABB----------------------<br>
AAAAAAAABBCCCCCCCCCCCCCCCC------<br>
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDD--<br>
--------BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF----BBCCCCCCCCCCCCCCCCDDDDE-<br>
FFFF------CCCCCCCCCCCCCCCCDDDDE-<br>

== 7. zadatak ==
=== Postavka ===
Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, deskriptor stranice je 32-bitni, a PMT je organizovana u dva nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. Koliki prostor bi ukupno zauzimala PMT nekog procesa kada bi:
#Proces koristio ceo svoj virtuelni adresni prostor?
#Proces koristio samo jednu stranicu?

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

== 8. zadatak ==
=== Postavka ===
Umesto tehnike ''spooling'', pristup uporednih procesa štampaču u nekom sistemu omogućuje se međusobnim isključenjem pomoću operacije rezervacije: svaki proces, pre nego što zatraži bilo koju operaciju sa štampačem, mora da ga rezerviše, a tu rezervaciju otpušta tek kada završi sa celim jednim poslom štampe. Šta je nedostatak ove tehnike?

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

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:
#<code>FHANDLE open(char* filename)</code> Otvara fajl sa datim imenom.
#<code>void close(FHANDLE)</code> Zatvara dati fajl.
#<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*)</code> Na poziciju kurzora datog fajla upisuje dati niz znakova, ne uključujući završni znak ‘\0’, i pomera kurzor iza upisanog niza znakova.
Napisati program koji na kraj postojećeg fajla sa imenom <code>proba.txt</code> upisuje sve što je uneseno preko standardnog ulaza, sve dok se na ulazu ne unese znak ’X’. Zanemariti sve potencijalne greške u ulazu/izlazu.

=== Rešenje ===
{{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:
#FAT, pri čemu je FAT uvek inicijalno učitana u memoriju prilikom montiranja fajl sistema
#indeksna, pri čemu je ceo indeks fajla u jednom bloku?

=== Rešenje ===
#n
#2

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

АСП2/К2 2018

2020-12-10T20:28:33Z

IvnSvc: Није било урађено брисање 4,11 и 9 после додавања 1-14.

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K2_1819.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
U 2-3-4 stablo sa slike ubaciti ključeve 17 i 25 i prikazati ekvivalentno crveno-crno stablo.
[ |23|45]
/ | \
[ 1|15|20] [28|36| ] [ |72| ]

=== Rešenje ===
[[Датотека:ASP2 K2 2018 zadatak 1 stablo.png|thumb|Ekvivalentno crveno-crno stablo u rešenju 1. zadatka.]]
Ključ 17 dolazi između ključeva 15 i 20. Pošto je taj čvor pun, crni ključ 15 ide u roditeljski čvor, ključ 1 dolazi u sredinu i postaje crn, ključ 20 se odvaja u desni čvor i postaje crn a ključ 17 završava kao crveni ključ levo od ključa 20.
[15|23|45]
/ | \
[ | 1| ] [17|20| ] [28|36| ] [ |72| ]
Ključ 20 dolazi levo od ključa 28.
[15|23|45]
/ | | \
[ | 1| ] [17|20| ] [20|28|36] [ |72| ]

== 2. zadatak ==
=== Postavka ===
B+-stabla
<div class="abc-list">
# Prikazati maksimalno popunjeno B+-stablo reda ''m'' = 3 i visine ''h'' = 1. Odrediti za ovo stablo prosečan broj pristupa prilikom uspešne i neuspešne pretrage.
# Posmatra se B+-stablo reda 4 koje sadrži 7 ključeva. Odrediti za ovo stablo srednji broj pristupa prilikom uspešne i neuspešne pretrage i obrazložiti odgovor.
</div>

=== Rešenje ===
(2|4)
/ | \
[1|2]->[3|4]->[5|6]
2 je prosečan broj pristupa i pri uspešnoj i pri neuspešnoj pretrazi.
(3|6| )
/ | \
[1|2|3]->[4|5|6]->[7| | ]
Pretpostavljajući da se ovde radi o broju ključeva u listovima (pošto se ključevi iz unutrašnjih čvorova dupliciraju u listovima), prosečan broj pristupa je ponovo 2. Sve uspešne pretrage, kao i neuspešne, moraju završiti u listovima jer se samo u listovima nalaze pokazivači ka traženim strukturama, a visina ovako napravljenog stabla je 1.

== 3. zadatak ==
=== Postavka ===
Posmatra se ''trie'' stablo čiji su ključevi znakovni nizovi koji sadrže cifre u brojnom sistemu sa osnovom 10. Napisati u pseudokodu funkciju koja za dato stablo na čiji koren pokazuje pokazivač ''root'' računa razliku najvećeg i najmanjeg tako predstavljenog broja.

=== Rešenje ===
<syntaxhighlight lang="milo">
CALC(root)
if root = nil then
return 0
end_if
min, max = CALC_R(root)
return max - min
</syntaxhighlight>
<syntaxhighlight lang="milo">
CALC R(root)
min = +∞
max = -∞
for i = 0 to 9 do
field = fields(root)[i]
if field ≠ nil then
if is_leaf(field) then
f_max = f_min = value(field)
else
f_max, f_min = CALC_R(field)
end_if
if f_max > max then
max = f_max
end_if
if f_min < min then
min = f_min
end_if
end_if
end_for
return max, min
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Posmatra se B stablo reda m u kojem su svi listovi minimalno popunjeni, a njihovi roditelji su popunjeni iznad minimuma. Iz takvog stabla se briše ključ key iz lista sa adresom node. Napisati iterativnu funkciju u pseudokodu za datu situaciju brisanja. Smatrati da u čvoru postoji pokazivač na roditelja i podatak o broju ključeva smeštenih u njemu.

=== Rešenje ===
<syntaxhighlight lang="milo">
B-DELETE-NO-BORROW(root, m, node, key)
child_index = 0
parent = parent(node)
for i = 0 to num(parent) do
if pointers(parent)[i] = node then
child_index = i
break
end_if
end_for
if child_index = num(parent) then
left_node = pointers(parent)[child_index-1]
num(left_node) = num(left_node) + 1
keys(left_node)[num(left_node)] = keys(parent)[child_index]
for i = 1 to num(node) do
if keys(node)[i] ≠ key then
num(left_node) = num(left_node) + 1
keys(left_node)[num(left_node)] = keys(node)[i]
end_if
end_for
FREENODE(node)
else
right_node = pointers(parent)[child_index+1]
offset = 0
for i = 1 to num(node) then
if keys(node)[i] = key then
offset = 1
else
keys(node)[i-offset] = keys(node)[i]
end_if
end_for
keys(node)[num(node)] = keys(parent)[child_index+1]
for i = 1 to num(right_node) do
num(node) = num(node) + 1
keys(node)[num(node)] = keys(right_node)[i]
end_for
for i = child_index to num(parent)-1 do
keys(parent)[i+1] = keys(parent)[i+2]
pointers(parent)[i] = pointers(parent)[i+1]
end_for
FREENODE(right_node)
end_if
num(parent) = num(parent) - 1
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
U B* stablo reda 4 se umeću ključevi od 1 do 14. Nakon toga se redom brišu ključevi 4, 11 i 9. Nacrtati izgled stabla nakon svake izmene.

=== Rešenje ===
* Red stabla: <math>m = 4</math>
* Minimalni broj ključeva u ne-korenskom čvoru: <math>\left\lceil\frac{2m - 1}{3}\right\rceil - 1 = 2</math>
* Maksimalni broj ključeva u korenu: <math>2 \left\lfloor\frac{2m - 2}{3}\right\rfloor = 4</math>
* Raspodela ključeva pri prelomu: 2-2-2
Umećemo ključ 1 u prazno stablo.
[ 1| | | ]
Umećemo ključ 2.
[ 1| 2| | ]
Umećemo ključ 3.
[ 1| 2| 3| ]
Umećemo ključ 4.
[ 1| 2| 3| 4]
Pri umetanju ključa 5 dolazi do prelamanja čvora, tako da ključevi 1 i 2 idu u levi a 4 i 5 u desni čvor.
[ 3| | | ]
| |
[ 1| 2| ] [ 4| 5| ]
Umećemo ključ 6.
[ 3| | | ]
| |
[ 1| 2| ] [ 4| 5| 6]
Pri umetanju ključa 7 desni čvor se prepunjuje, pa se dešava prelivanje u levi čvor. Ključ 3 iz roditeljskog čvora silazi u levi a ključ 4 iz desnog ide u roditeljski.
[ 4| | | ]
| |
[ 1| 2| 3] [ 5| 6| 7]
Pri umetanju ključa 8 desni čvor se ponovo prepunjuje, pa se dešava prelamanje. Ključevi 1 i 2 ostaju u levom čvoru, ključ 3 ide u roditeljski čvor, 4 i 5 dolaze u novi, srednji čvor, 6 ide u roditeljski čvor a 7 i 8 ostaju u desnom čvoru.
[ 3| 6| | ]
/ | \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| ]
Umećemo ključ 9.
[ 3| 6| | ]
/ | \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| 9]
Pri umetanju ključa 10 dešava se prelivanje iz desnog u srednji čvor.
[ 3| 7| | ]
/ | \
[ 1| 2| ] [ 4| 5| 6] [ 8| 9|10]
Pri umetanju ključa 11 dešava se prelamanje.
[ 3| 6| 9| ]
/ | \ \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| ] [10|11| ]
Umećemo ključ 12.
[ 3| 6| 9| ]
/ | \ \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| ] [10|11|12]
Pri umetanju ključa 13 dešava se prelivanje.
[ 3| 6|10| ]
/ | \ \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| 9] [11|12|13]
Pri umetanju ključa 14 dešava se prelamanje.
[ 3| 6| 9|12]
/ / | \ \
[ 1| 2| ] [ 4| 5| ] [ 7| 8| ] [10|11| ] [13|14| ]
При брисању кључа 4, због немогућности позајмице, спајање три чвора у два.
[ 5| 9| 12 |]
/ / | \
[ 1| 2| 3 ] [ 6| 7| 8 ] [ 10|11| ] [13|14| ]
При брисању кључа 11 могућа је позајмица, али од левог брата.
[ 5| 8| 12 |]
/ / | \
[ 1| 2| 3 ] [ 6| 7|] [ 9 |10| ] [13|14| ]
При брисању кључа 9 могућа је позајмица али од брата са удаљеношћу два.
[ 3| 7| 12 |]
/ / | \
[ 1| 2| ] [ 5| 6| ] [ 8 |10| ] [13|14| ]

== 6. zadatak ==
=== Postavka ===
Dato je digitalno stablo formirano od nekog skupa ključeva tipa znakovnih nizova. Implementirati funkciju COUNT_KEYS koja pronalazi broj ključeva u stablu koji odgovaraju zadatom formatu znakovnog niza. Pokazivač na koren stabla i zadati format su prosleđeni kao parametri funkcije. Format znakovnog niza pored cifara i slova može sadržati i simbole koji imaju specijano značenje. Specijalni simboli su tačka (.) koja menja bilo koji znak niza i zvezda (*) koja predstavlja ponavljanje nekog znaka niza 0 ili više puta. Smatrati da se zvezda odnosi na prvi znak koji joj prethodi.

Primer:

skup ključeva u stablu: abccc4a, ab3a, aacda

format: abc*.a

rezultat: 2

=== Rešenje ===
<syntaxhighlight lang="milo">
COUNT KEYS(root, format)
len = STRING_LENGTH(format)
if len = 0 then
return 0
end_if
count = 0
for i = 1 to num(root) do
node = pointers(root)[i]
if (len > 1) and (format[2] = '*') then
if (key(node) = format[1]) or (format[1] = '.') then
count = count + COUNT_KEYS(node, format)
else
count = count + COUNT_KEYS(root, format + 2)
end_if
else if (key(node) = format[1]) or (format[1] = '.') then
count = count + COUNT_KEYS(node, format + 1)
end_if
end_for
return count
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Neka se u ''top-down'' stablo ''m''-arnog pretraživanja redom ubacuju ključevi ''k'', 2''k'', 3''k'', …, ''nk'', ''nk'' – 1, ''nk'' – 2, ''nk'' – 3, …, ''n''(''k'' – 1) +1. Nacrtati izgled stabla i odrediti visinu. Pretpostaviti da su ''n'' i ''k'' mnogo veći od ''m''.

=== Rešenje ===
Nakon ubacivanja ključa ''nk'' dobiće se degenerisano stablo udesno, tj. jedino najdesniji pokazivači u svakom unutrašnjem čvoru će pokazivati na sledeći list, i većina ključeva će biti popunjena, tako da će visina stabla biti <math>\left\lceil\frac{n}{m - 1}\right\rceil</math> a u listu će ostati <math>(m - 1) - (n \bmod (m - 1))</math> slobodnih mesta. Nakon ubacivanja svih ključeva stablo će u listovima krenuti da raste ulevo iz listova, tako da će visina porasti na ukupno: <math>h = \left\lceil\frac{n}{m - 1}\right\rceil + \left\lceil\frac{k - 1 - (m - 1) + (n \bmod (m - 1))}{m - 1}\right\rceil</math>.

== 8. zadatak ==
=== Postavka ===
Heširanje.
<div class="abc-list">
# Šta je minimalna savršena heš funkcija?
# Za ključeve 54, 91, 57, 23 i 28 naći što jednostavniju minimalnu savršenu heš funkciju i ispisati je. Obrazložiti odgovor i nacrtati heš tabelu sa umetnutim ključevima.
</div>

=== Rešenje ===

[[Категорија:АСП2]]
[[Категорија:Рокови]]

АСП2/К2 2019

2020-11-21T21:48:40Z

IvnSvc: /* Rešenje */ Преправио 61 у 64. 64 се нигде не појављује у задатку па је врв грешка у куцању

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K2_1920.pdf Zadaci na stranici predmeta.]

== 1. zadatak ==
=== Postavka ===
Izomorfizam crveno-crnih i 2-3-4 stabala.
<div class="abc-list">
# Dato binarno crveno-crno stablo transformisati u izomorfno 2-3-4 stablo. Osenčeni čvorovi su crni.
# Iz stabla dobijenog pod a) brišu se ključevi 63 i 60. Nacrtati stabla dobijena nakon svakog od ova dva brisanja.
# Ako se stablo dobijeno pod a) posmatra kao obično B stablo reda 4, da li bi bilo razlike u konačnom izgledu stabla nakon brisanja ključeva 63 i 60? Ukratko objasniti.
</div>

=== Rešenje ===
Ekvivalentno izomorfno 2-3-4 stablo je:
[57|74| ]
/ | \
[21|43| ] [60|63| ] [88|91|94]
Pri izbacivanju ključa 63, ključ 60 dolazi na njegovo mesto (i postaje crn).
[57|74| ]
/ | \
[21|43| ] [ |60| ] [88|91|94]
Pri izbacivanju ključa 60, vrši se pozajmljivanje od pravog brata, koji je ovde levi brat u izomorfnom 2-3-4 stablu, pa ključ 43 postaje razdelni a ključ 57 silazi u čvor iz kojeg se briše.
[43|74| ]
/ | \
[ |21| ] [ |57| ] [88|91|94]
Ekvivalentna crveno-crna stabla su data ispod.

Da je stablo bilo obično B stablo reda 4, u drugom koraku bi se pozajmljivalo od desnog brata umesto od levog brata, jer B stabla nemaju pravilo da se prvo pozajmljuje od pravog brata. Takođe, ključevi 21 i 57 ne bi stajali u središnjem polju čvora, već najlevljem.
<gallery>
ASP2 K2 2019 zadatak 1 stablo.png | Originalno crveno-crno stablo
ASP2 K2 2019 zadatak 1 korak 1.png | Crveno-crno stablo nakon brisanja čvora 63
ASP2 K2 2019 zadatak 1 korak 2.png | Crveno-crno stablo nakon brisanja čvora 60
</gallery>

== 2. zadatak ==
=== Postavka ===
U B+ stablo sa slike redom se umeću ključevi 6, 25, 21 i 27, nakon čega se uklanjaju ključevi 33, 27 i 6. Prikazati ažuriranje stabla po koracima.
[33|64| ]
/ | \
[20|22|33]->[42|64| ]->[71|81| ]

=== Rešenje ===
* Red stabla: <math>m = 4</math>
* Minimalni broj ključeva u unutrašnjim čvorovima: <math>\left\lceil\frac{m}{2}\right\rceil-1 = 1</math>
* Minimalni broj ključeva u listovima: <math>\left\lfloor\frac{m}{2}\right\rfloor = 2</math>
Ključ 6 se umeće levo od čvora 20. Dolazi do preloma i 6 i 20 ostaju u čvoru, 20 ide u roditelja, a 22 i 33 se odvajaju u novi čvor.
(20|33|64)
/ | | \
[ 6|20| ]->[22|33| ]->[42|64| ]->[71|81| ]
Ključ 25 se umeće između ključeva 22 i 33.
(20|33|64)
/ | | \
[ 6|20| ]->[22|25|33]->[42|64| ]->[71|81| ]
Ključ 21 se umeće levo od ključa 22. Dolazi do preloma, 21 i 22 ostaju u čvoru, 22 ide u roditeljski čvor, a 25 i 33 se odvajaju u novi čvor. Pošto u roditelju nema mesta, i on se prelama tako da koren postaje čvor sa 22, levi čvor sa 20 i desni sa 33 i 64.
(22| | )
/ \
(20| | ) (33|64| )
/ | / | \
[ 6|20| ]->[21|22| ]->[25|33| ]->[42|64| ]->[71|81| ]
Ključ 27 se umeće između ključeva 25 i 33.
(22| | )
/ \
(20| | ) (33|64| )
/ | / | \
[ 6|20| ]->[21|22| ]->[25|27|33]->[42|64| ]->[71|81| ]
Pri uklanjanju ključa 33, pošto je najveći ključ u čvoru, mora se ažurirati roditeljski čvor tako da 33 u roditeljskom čvoru postaje 27.
(22| | )
/ \
(20| | ) (27|64| )
/ | / | \
[ 6|20| ]->[21|22| ]->[25|27| ]->[42|64| ]->[71|81| ]
Pri uklanjanju ključa 27, ostaje manje nego dovoljno ključeva u tom čvoru. Pozajmica od oba brata nije moguća, i zato se taj čvor spaja sa svojim desnim bratom. U tom procesu se takođe izbacuje ključ iz roditeljskog čvora.
(22| | )
/ \
(20| | ) (64| | )
/ | / |
[ 6|20| ]->[21|22| ]->[25|42|64]->[71|81| ]
Pri uklanjanju ključa 6, ostaje manje nego dovoljno ključeva u tom čvoru. Pozajmica od brata nije moguća, i zato se taj čvor spaja sa svojim desnim bratom. U tom procesu roditeljski čvor ostaje prazan, tako da se spajaju svi unutrašnji čvorovi u jedan, čime se dobija konačno stablo:
(22|64| )
/ | \
[20|21|22]->[25|42|64]->[71|81| ]

== 3. zadatak ==
=== Postavka ===
Dato digitalno stablo je potrebno transformisati u kompaktniju formu kako bi se smanjila veličina stabla.
<div class="abc-list">
# Predložiti i objasniti način na koji se može ostvariti transformacija digitalnog stabla u kompaktniju formu i prikazati izgled digitalnog stabla nakon opisane transformacije.
# Implementirati funkciju <u>TRIE COMPACTION</u> koja transformiše stablo na prethodno opisani način. Pokazivač na koren stabla ''root'' je prosleđen funkciji. Smatrati da je digitalno stablo predstavljeno po principu levi sin - desni brat.
</div>
A
/ | \
B C S
| | |
K J 4
/ \ | |
D T M 6
| | | |
9 * * A
| |
3 *
|
*

=== Rešenje ===
Kompaktnija forma ovog stabla može se dobiti tako što sve čvorove koji imaju samo jednu putanju do listova zamenimo sa listovima koji sadrže pokazivače na zapise na koje su listovi prethodno pokazivali i celu vrednost ključa. U tom slučaju ne mora da postoji čvor za kraj ključa.

<syntaxhighlight lang="milo">
TRIE COMPACTION(root)
if root ≠ nil then
compacted_root = COMPACT(root, "")
if compacted_root ≠ nil then
root = compacted_root
end_if
end_if
</syntaxhighlight>
<syntaxhighlight lang="milo">
COMPACT(node, str)
if key(node) = '*' then
FREENODE(node)
return str
end_if
compacted_child = COMPACT(right(node), str + key(node))
if left(node) = nil then
FREENODE(node)
return compacted_child
else
COMPACT(left(node))
if compacted_child ≠ nil then
right(node) = compacted_child
end_if
return nil
end_if
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Napisati u pseudokodu funkciju koja iz '<nowiki />''top-down''' stabla ''m''-arnog pretraživanja briše na čiji koren pokazuje pokazivač ''root'' briše zadati ključ key.

=== Rešenje ===
<syntaxhighlight lang="milo">
DELETE(root, m, key)
parent = nil
parent_index = 0
p = root
i = 0
found = false
while (p ≠ nil) and (not found) do
for i = 1 to num(p) do
if keys(p)[i] = key then
found = true
break
else if keys(p) > key then
parent = p
parent_index = i
p = pointers(p)[i-1]
break
end_if
end_for
if i = num(p) + 1 then
p = pointers(p)[i-1]
end_if
end_while
if p = nil then
ERROR(Ključ nije pronađen)
end_if
q = pointers(p)[i]
if q ≠ nil then
prev = p
while q ≠ nil do
parent = prev
parent_index = 1
prev = q
q = pointers(q)[0]
end_while
keys(p)[i] = key(prev)
p = prev
i = 1
end_if
for j = i to num(p) do
keys(node)[i-1] = keys(node)[i]
end_for
num(p) = num(p) - 1
if num(p) = 0 then
FREENODE(p)
pointers(parent)[parent_index-1] = nil
end_if
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
U B* stablo reda 5 sa slike se umeću ključevi 18, 23, 7, 37, 19. Nakon toga se redom brišu ključevi 80, 55, 18, 9 i 15. Nacrtati izgled stabla nakon svake izmene.
[15|24|41|80]
/ / | \ \
[ 2| 9|10| ] [16|20|21| ] [27|33|40| ] [55|75| | ] [93|96| | ]

=== Rešenje ===
* Red stabla: <math>m = 5</math>
* Minimalan broj ključeva u ne-korenskim čvorovima: <math>\left\lceil\frac{2m - 1}{3}\right\rceil-1 = 3 - 1 = 2</math>
* Maksimalan broj ključeva u korenu: <math>2\left\lfloor\frac{2m - 2}{3}\right\rfloor = 4</math>
* Raspodela ključeva pri prelomu: 2-3-3
Ključ 18 umećemo između ključeva 16 i 20.
[15|24|41|80]
/ / | \ \
[ 2| 9|10| ] [16|18|20|21] [27|33|40| ] [55|75| | ] [93|96| | ]
Ključ 23 umećemo desno od ključa 21. Dešava se prelivanje u desni čvor, 23 završava u roditelju a 24 u desnom čvoru.
[15|23|41|80]
/ / | \ \
[ 2| 9|10| ] [16|18|20|21] [24|27|33|40] [55|75| | ] [93|96| | ]
Ključ 7 umećemo između ključeva 2 i 9.
[15|23|41|80]
/ / | \ \
[ 2| 7| 9|10] [16|18|20|21] [24|27|33|40] [55|75| | ] [93|96| | ]
Ključ 37 umećemo između ključeva 33 i 40. Dešava se prelivanje u desni čvor, 40 završava u roditelju a 41 u desnom čvoru.
[15|23|40|80]
/ / | \ \
[ 2| 7| 9|10] [16|18|20|21] [24|27|33|37] [41|55|75| ] [93|96| | ]
Ključ 19 umećemo između ključeva 18 i 20. Prelivanje u levog i desnog brata je nemoguće, pa se dešava prelom. Ključevi 16 i 18 ostaju u čvoru, 19 ide u roditeljski čvor, 20, 21 i 23 idu u novi čvor, 24 ide u roditeljski čvor i 27, 33 i 37 ostaju u desnom bratu. Prelom se dešava i u roditeljskom čvoru, tako da 15 i 19 idu u levo dete novog korena, 24 ide u novi koren a 40 i 80 idu u desno dete novog korena.
[24| | | ]
/ \
[15|19| | ] [40|80| | ]
/ | \ / | \
[ 2| 7| 9|10] [16|18| | ] [20|21|23| ] [27|33|37| ] [41|55|75| ] [93|96| | ]
Ključ 80 menjamo svojim sledbenikom, 93, pa ga brišemo iz lista. U listu ostaje nedovoljno mnogo ključeva, pa vršimo pozajmicu od levog brata. Tom prilikom se ključ 93 vraća nazad u list u kojem je bio a 75 dolazi na mesto gde je ranije bio ključ 80.
[24| | | ]
/ \
[15|19| | ] [40|75| | ]
/ | \ / | \
[ 2| 7| 9|10] [16|18| | ] [20|21|23| ] [27|33|37| ] [41|55| | ] [93|96| | ]
Pri brisanju ključa 55 iz lista ostaje nedovoljno ključeva, pa pozajmljujemo od levog brata. Tom prilikom ključ 37 dolazi na mesto 40 u roditeljskom čvoru a 40 se spušta u list.
[24| | | ]
/ \
[15|19| | ] [37|75| | ]
/ | \ / | \
[ 2| 7| 9|10] [16|18| | ] [20|21|23| ] [27|33| | ] [40|41| | ] [93|96| | ]
Pri brisanju ključa 18 iz lista ostaje nedovoljno ključeva, pa pozajmljujemo od desnog brata. Tom prilikom ključ 20 ide u roditeljski čvor a ključ 19 se spušta u list.
[24| | | ]
/ \
[15|20| | ] [37|75| | ]
/ | \ / | \
[ 2| 7| 9|10] [16|19| | ] [21|23| | ] [27|33| | ] [40|41| | ] [93|96| | ]
Brišemo ključ 9 iz lista.
[24| | | ]
/ \
[15|20| | ] [37|75| | ]
/ | \ / | \
[ 2| 7|10| ] [16|19| | ] [21|23| | ] [27|33| | ] [40|41| | ] [93|96| | ]
Ključ 15 menjamo svojim sledbenikom, 16, pa brišemo ključ iz lista. U tom listu ostaje nedovoljno mnogo ključeva, pa se pozajmljuje od levog brata tako što se ključ 16 vrati na svoje prethodno mesto a ključ 10 ode u roditeljski čvor.
[24| | | ]
/ \
[10|20| | ] [37|75| | ]
/ | \ / | \
[ 2| 7| | ] [16|19| | ] [21|23| | ] [27|33| | ] [40|41| | ] [93|96| | ]

== 6. zadatak ==
=== Postavka ===
Posmatra se baza podataka studenata.
<div class="abc-list">
# Ukoliko se zna da je najčešći upit nad zadatom bazom dohvatanje svih studenata koji su fakultet upisali u zadatom periodu (između dve godine), predložiti strukturu podataka koja bi podržala efikasno izvršavanje ovakvog upita i detaljno opisati razloge.
# Implementirati funkciju FIND_STUDENTS_IN_RANGE koja nad odabranom strukturom vrši pretragu i vraća rezultat upita navedenog pod tačkom a). Parametri funkcije su pokazivač na odabranu strukturu, početna godina i krajnja godina traženog perioda, respektivno. Rezultat vratiti u formi niza.
</div>

=== Rešenje ===
Struktura koja se ovde može upotrebiti je B+ stablo, jer nam dozvoljava lak sekvencijalni pristup (za izlistavanje svih studenata u rasponu od dve godine) kao i brzo pronalaženje prvog ključa (za prvog studenta iz raspona). Ključevi ovakvog stabla mogu biti kombinacija godine i broja indeksa studenta, tako da je godina primarni a broj indeksa sekundarni ključ.

<syntaxhighlight lang="milo">
FIND STUDENTS IN RANGE(structure, year1, year2)
p = structure
while (not IS_LEAF(p)) do
if key(p) < year1 then
p = right(p)
else
p = left(p)
end_if
end_while
length = 0
q = p
while (q ≠ nil) and (year(q) ≤ year2) do
length = length + 1
q = next(q)
end_while
arr = ALLOCATE(length)
for i = 1 to length do
arr[i] = p
p = next(p)
end_while
return arr
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Neka se za indeksnu strukturu datoteke koristi B stablo reda ''m''. U okviru datoteke se smeštaju zapisi veličine 256 bitova zajedno sa 32-bitnim poljem ključa. Neka se na datom sistemu adrese predstavljaju na 64 bita. Odrediti vrednosti ''m'' u zavisnosti od toga da li se u čvoru B stabla smešta samo ključ ili čitav podataka, pod pretpostavkom da je veličina bloka na disku 2KB. Diskutovati rešenje.

=== Rešenje ===
Jedan čvor B stabla mora stati u jedan blok na disku, što je 2KiB, odnosno 2048B, odnosno 16384b. Zapis čvora obuhvata:
* <math>m-1</math> ključeva (32b) zajedno sa adresama njihovih zapisa (64b), odnosno u drugoj varijanti ceo zapis (256b)
* <math>m</math> adresa (64b) podstabala
Tako je veličina jednog čvora stabla u prvoj varijanti jednaka <math>(m-1) \cdot (32 + 64) + m \cdot 64 = m \cdot 96 + m \cdot 64 - 96 = m \cdot 160 - 96</math>. Ako pretpostavimo da je ovo jednako veličini bloka, dobijamo <math>m \cdot 160 = 16480 \implies m = \frac{16480}{160} = 103</math>.

U drugoj varijanti, veličina čvora je jednaka <math>(m-1) \cdot 256 + m \cdot 64 = m \cdot 256 - 256 + m \cdot 64 = m \cdot 320 - 256</math>. Sa istom pretpostavkom dobijamo <math>m \cdot 320 = 16640 \implies m = \frac{16640}{320} = 52</math>.

== 8. zadatak ==
=== Postavka ===
Heširanje.
<div class="abc-list">
# Kako funkcioniše metod deljenja i koje su njegove osnovne osobine? Koje vrednosti delioca treba izbegavati?
# Neka je dat skup ključeva 19, 10, 4, 37, 49, 52. Ukoliko je poznatao da se prilikom heširanja koristi metod deljenja i veličina tabele ''n'' = 9, komentarisati izbor veličine tabele u odnosu na verovatnoću mogućih kolizija zadatog skupa ključeva. Predložiti alternativnu, blisku veličinu tabele kako bi se verovatnoća kolizija smanjila.
</div>

=== Rešenje ===

[[Категорија:АСП2]]
[[Категорија:Рокови]]