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

АОР2/Јун 2023

2024-06-02T17:25:46Z

Jaksa: /* Решење */

{{tocright}}
'''Јунски рок 2023. године''' одржан је 5. јуна и трајао је 120 минута.

== 1. задатак ==
=== Поставка ===
'''[5п]''' Описати технику оптимизације векторских инструкција која се заснива на коришћењу регистра маски вектора ('''''Vector mask registers'''''). На примеру израчунавања максимума кореспондентних елемената низа (<code>Z[i] = MAX(X[i], Y[i])</code>) приказати коришћење овог регистра.

=== Решење ===
Регистар маске вектора служи како би се одређене операције над векторима извршиле само над њиховим одређеним члановима, тиме што на одређеним битовима регистра маске стоје нуле или јединице. На пример, следећи код за рачунање максимума:
<syntaxhighlight lang="c">
for (int i = 0; i < n; ++i)
if (X[i] > Y[i])
Z[i] = X[i];
else
Z[i] = Y[i];
</syntaxhighlight>
би могао да се преведе у следећу секвенцу векторских инструкција:
<syntaxhighlight lang="asm">
...
LV V1, X # Учитавамо део низа X у вектор V1
LV V2, Y # Учитавамо део низа Y у вектор V2
SGTVS.D V1, V2 # Постављамо регистар маске на 1 на местима где важи X[i] > Y[i]
MOVVV.D V3, V1 # Постављамо елементе V3 на елементе V1 на местима где је маска 1
MVFM V1, VM # Учитавамо маску у V1
NOTV V1 # Негирамо V1
MVTM V1, VM # Учитавамо V1 у маску
MOVVV.D V3, V2 # Постављамо елементе V3 на елементе V2 на местима где је маска 1
SV V3, Z # Уписујемо део низа Z
...
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
'''[5п]''' Посматра се предвиђање скока коришћењем ''gshare'' предиктора. Описати рад овог предиктора. Упоредити рад овог предиктора и корелисаног предиктора који користи исти број бита одговарајућих улазних података.

=== Решење ===
''gshare'' предиктор садржи следеће елементе:
* ''Branch History Register'' (BHR) који функционише као ''shift'' регистар који чува глобалну историју скокова (да ли је услов испуњен или није),
* ''Pattern History Table'' (PHT) која садржи аутомате стања који одређују крајња предвиђања, и
* хеш функцију која комбинује BHR и битове адресе скока како би адресирала PHT.
За разлику од ''gshare'', корелисани предиктор одвојено адресира једну од више PHT помоћу BHR, а затим један од аутомата у оквиру PHT помоћу адресе скока. Може се приметити да је корелисани предиктор, због свог већег броја PHT, за исте ширине улазних података доста скупљи од ''gshare''. Такође се показало да је већина улаза у овакве PHT неискоришћено, па је ''gshare'' направљен како би побољшао ово искоришћење и смањио цену производње корелисаног предиктора.

== 3. задатак ==
=== Поставка ===
'''[10п]''' Разматра се рачунарски систем у коме се извршавање одређене инструкција одвија у 6 фаза помоћу измењеног процесора са стандардном проточном обрадом (слика 3.1.). У процесор са стандардом проточном обрадом је додата као други степен јединица PD (''Instruction PreDecode'') који<sup>[sic]</sup> обавља трансформацију инструкција задате архитектуре у инструкције RISC архитектуре. Сматрати да приступ меморији траје два сигнала такта. Архитектура процесора дефинише 16 регистра<sup>[sic]</sup> опште намене. Адресе и подаци су величине 16 бита.
[[Датотека:AOR2 organizacija PreDecode.svg|thumb|center|500px|Слика 4.1.<sup>[sic]</sup> — организација процесора]]
<div class="abc-list">
# Написати секвенцу инструкција (микроинструкција) циљне RISC архитектуре у коју се обавља пресликавање за део инструкцијског сета из табеле 3.1. изворишне CISC архитектуре. Уколико је потребно проширити број регистара опште намене у регистарском фајлу, онда треба за сваки додат регистар написати чему служи. Регистар R13 представља указивач на врх стека (SP) и показује на последњу слободну локацију. Стек расте према вишим адресама. Регистар R14 представља указивач на базну адресу стека (BP). Регистар R0 се користи као акумулатор, регистар R12 се користи као бројачки регистар и као такав има посебне инструкције које га користе. У табели 3.1. акције нису оптимизовано написане, већ описно.
# Нацртати формат инструкција циљне RISC архитектуре (на основу инструкција из табеле 3.1.).
</div>
{| class="wikitable"
|+ Табела 3.1. — део инструкцијског сета процесора
! Асемблерска инструкција
! Акција
! Микро инструкције
|-
| <code>SWP Rx</code>
|
MEM[Rx] ↔ ACC
|
|-
| <code>DEC</code>
|
ACC = ACC - 1
|
|-
| <code>RTS</code>
|
POP PC
|
|-
| <code>LOOP disp</code>
|
R12 = R12 - 1
IF R12 == 0 THEN
PC = PC + disp
|
|-
| <code>JMP adr</code>
|
PC = adr
|
|-
| <code>ADD (adr)</code>
|
ACC = ACC + MEM[MEM[adr]]
|
|-
| <code>LDB Rx</code>
|
ACC = 0.Rx<sub>7..0</sub>
|
|-
| <code>STRLEN adr</code>
|
ACC = 0
WHILE MEM[adr] != 0 DO
ACC = ACC + 1
adr = adr + 1
END WHILE
|
|-
| <code>VECADD adr</code>
|
R1 = R1 + MEM[adr]
R2 = R2 + MEM[adr]
R3 = R3 + MEM[adr]
R4 = R4 + MEM[adr]
|
|-
| <code>MUL R1</code>
|
TMP = ACC
ACC = 0
FOR X = 0; X < R1; X++ DO
ACC = ACC + TMP
END FOR
|
|}

=== Решење ===
Претпоставља се да се под AX регистром у задатку мисли на акумулатор. Уводимо регистре:
* R16: привремени регистар
* R17: вредност 0
* R18: још један привремени регистар
{| class="wikitable"
|+ Решење трећег задатка.
! Асемблерска инструкција
! Акција
! Микро инструкције
! Коментар
|-
| <code>SWP Rx</code>
|
MEM[Rx] ↔ ACC
|
LD R0, (Rx)0
ADDIS R16, R0, #0
ST R16, (Rx)0
| Уколико би после ове секвенце микроинструкција дошла микроинструкција која користи меморију, то би био хазард по подацима.
|-
| <code>DEC</code>
|
ACC = ACC - 1
|
ADDIS R0, R0, #-1
|-
| <code>RTS</code>
|
POP PC
|
LD R16, (R13)-1
ADDI R13, R13, #-1
BEQZ R17, (R17+R16)
| У последњој инструкцији се кроз горњи мултиплексер пропушта вредност R17 (0), која се користи и као услов скока, а кроз доњи вредност R16, која садржи жељену вредност PC, па стога и специфичан начин обележавања (који је еквивалентан са <code>(R16)0</code>).
|-
| <code>LOOP disp</code>
|
R12 = R12 - 1
IF R12 == 0 THEN
PC = PC + disp
|
SUB R12, R12, #1
BEQZPI R12, (PC)disp
|
|-
| <code>JMP adr</code>
|
PC = adr
|
BEQZI R17, (R17)adr
|-
| <code>ADD (adr)</code>
|
ACC = ACC + MEM[MEM[adr]]
|
LD R16, (R17)adr
LD R16, (R16)0
ADDS R0, R0, R16
| Дешава се хазард по подацима између прве и друге и између друге и треће микроинструкције.
|-
| <code>LDB Rx</code>
|
ACC = 0.Rx<sub>7..0</sub>
|
ANDIS R0, RX, #00FF
|
|-
| <code>STRLEN adr</code>
|
ACC = 0
WHILE MEM[adr] != 0 DO
ACC = ACC + 1
adr = adr + 1
END WHILE
|
ADDI R0, R17, #0
LD R16, (R0)adr
ADDIS R0, R0, #1
BNEZPI R16, (PC)-3 * len(mInst)
ADDI R0, R0, #-1
| За ову ставку је речено на колоквијуму да може да се претпостави како PC броји микроинструкције уместо инструкције. Главне идеје су да се уклони хазард тиме што радимо <code>ADD</code> инструкцију испод <code>LD</code>, да се акумулатор користи уместо неког новог регистра за чување <code>adr</code> (јер се свакако увећава сваке итерације) и да након петље која обухвата другу, трећу и четврту микроинструкцију морамо смањити акумулатор за један, јер нам је претходна петља ефективно била ''do-while'' уместо ''while''.
|-
| <code>VECADD adr</code>
|
R1 = R1 + MEM[adr]
R2 = R2 + MEM[adr]
R3 = R3 + MEM[adr]
R4 = R4 + MEM[adr]
|
LD R16, (R17)adr
ADDI R18, R17, #adr
LD R16, (R18)1
ADD R1, R1, R16
LD R16, (R18)2
ADD R2, R2, R16
LD R16, (R18)3
ADD R3, R3, R16
ADD R4, R4, R16
| Разлог из ког ова секвенца микроинструкција може изгледати чудно јесте избегавање хазарда по подацима. Са учитавањем првог податка почиње се већ у првој микроинструкцији, али како у међувремену треба обавити чување <code>adr</code> у новом привременом регистру и започињање новог учитавања, она се не сабира са регистром R1 до четврте микроинструкције (када је та вредност и даље доступна у одговарајућем регистру). Након тога се логика понавља неколико пута: започели смо учитавање наредног податка, а док се тај податак учитава ми радимо сабирање претходно учитаног податка са одговарајућим регистром. Како је до девете микроинструкције завршено учитавање и последњег податка, можемо извршити последње сабирање.
|-
| <code>MUL R1</code>
|
TMP = ACC
ACC = 0
FOR X = 0; X < R1; X++ DO
ACC = ACC + TMP
END FOR
|
ADDI R16, R0, #0
ADDIS R0, R17, #0
ADDI R18, R1, #0
ADDS R0, R0, R16
ADDI R18, R18, #-1
BNEZPI R18, (PC)-3 * len(mInst)
SUB R0, R0, R16
| Идеја јесте да R16 користимо као претходну вредност акумулатора и R18 као бројач итерација који почиње од R1 и завршава се са 0. Уколико би нам провера за <code>R18 == 0</code> била на врху, наша петља би се састојала из четири микроинструкције: провере, сабирања, декрементирања и безусловног скока. Уместо тога, проверу стављамо на дно па се наша петља састоји од три микроинструкције (резултујући у мањем укупном броју извршених микроинструкција), али због тога што смо опет ефективно направили ''do-while'' петљу ефекат последње итерације морамо да поништимо на крају. Као и за <code>STRLEN</code>, за ову ставку може да се претпостави како PC броји микроинструкције уместо инструкције. (На колоквијуму је накнадно речено да је податак у R1 означен, али то у овом решењу није узето у обзир јер такво коришћење и нема смисла.)
|}
Користимо укупно седам RISC инструкција у овом сету:
# LD
# ST
# ADD
# SUB
# AND
# BEQZ
# BNEZ
Ово нам оставља следећи формат инструкције:
{| class="wikitable"
|+ Формат инструкције у четвртом задатку
! 36 !! 35 !! 34 !! 33 !! 32 !! 31 !! 30 !! 29 !! 28 !! 27 !! 26 !! 25 !! 24 !! 23 !! 22 !! 21 !! 20 !! 19 !! 18 !! 17 !! 16 !! 15 !! 14 !! 13 !! 12 !! 11 !! 10 !! 9 !! 8 !! 7 !! 6 !! 5 !! 4 !! 3 !! 2 !! 1 !! 0
|-
| colspan="3" | Код
| colspan="3" | PIS флегови
| colspan="5" | Одредишни регистар
| colspan="5" | Изворишни регистар 1
| colspan="5" | Изворишни регистар 2
| colspan="16" | Непосредна вредност
|}

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

АОР2/Јун 2023

2024-06-02T16:52:23Z

Jaksa: /* Решење */

{{tocright}}
'''Јунски рок 2023. године''' одржан је 5. јуна и трајао је 120 минута.

== 1. задатак ==
=== Поставка ===
'''[5п]''' Описати технику оптимизације векторских инструкција која се заснива на коришћењу регистра маски вектора ('''''Vector mask registers'''''). На примеру израчунавања максимума кореспондентних елемената низа (<code>Z[i] = MAX(X[i], Y[i])</code>) приказати коришћење овог регистра.

=== Решење ===
Регистар маске вектора служи како би се одређене операције над векторима извршиле само над њиховим одређеним члановима, тиме што на одређеним битовима регистра маске стоје нуле или јединице. На пример, следећи код за рачунање максимума:
<syntaxhighlight lang="c">
for (int i = 0; i < n; ++i)
if (X[i] > Y[i])
Z[i] = X[i];
else
Z[i] = Y[i];
</syntaxhighlight>
би могао да се преведе у следећу секвенцу векторских инструкција:
<syntaxhighlight lang="asm">
...
LV V1, X # Учитавамо део низа X у вектор V1
LV V2, Y # Учитавамо део низа Y у вектор V2
SGTVS.D V1, V2 # Постављамо регистар маске на 1 на местима где важи X[i] > Y[i]
MOVVV.D V3, V1 # Постављамо елементе V3 на елементе V1 на местима где је маска 1
MVFM V1, VM # Учитавамо маску у V1
NOTV V1 # Негирамо V1
MVTM V1, VM # Учитавамо V1 у маску
MOVVV.D V3, V2 # Постављамо елементе V3 на елементе V2 на местима где је маска 1
SV V3, Z # Уписујемо део низа Z
...
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
'''[5п]''' Посматра се предвиђање скока коришћењем ''gshare'' предиктора. Описати рад овог предиктора. Упоредити рад овог предиктора и корелисаног предиктора који користи исти број бита одговарајућих улазних података.

=== Решење ===
''gshare'' предиктор садржи следеће елементе:
* ''Branch History Register'' (BHR) који функционише као ''shift'' регистар који чува глобалну историју скокова (да ли је услов испуњен или није),
* ''Pattern History Table'' (PHT) која садржи аутомате стања који одређују крајња предвиђања, и
* хеш функцију која комбинује BHR и битове адресе скока како би адресирала PHT.
За разлику од ''gshare'', корелисани предиктор одвојено адресира једну од више PHT помоћу BHR, а затим један од аутомата у оквиру PHT помоћу адресе скока. Може се приметити да је корелисани предиктор, због свог већег броја PHT, за исте ширине улазних података доста скупљи од ''gshare''. Такође се показало да је већина улаза у овакве PHT неискоришћено, па је ''gshare'' направљен како би побољшао ово искоришћење и смањио цену производње корелисаног предиктора.

== 3. задатак ==
=== Поставка ===
'''[10п]''' Разматра се рачунарски систем у коме се извршавање одређене инструкција одвија у 6 фаза помоћу измењеног процесора са стандардном проточном обрадом (слика 3.1.). У процесор са стандардом проточном обрадом је додата као други степен јединица PD (''Instruction PreDecode'') који<sup>[sic]</sup> обавља трансформацију инструкција задате архитектуре у инструкције RISC архитектуре. Сматрати да приступ меморији траје два сигнала такта. Архитектура процесора дефинише 16 регистра<sup>[sic]</sup> опште намене. Адресе и подаци су величине 16 бита.
[[Датотека:AOR2 organizacija PreDecode.svg|thumb|center|500px|Слика 4.1.<sup>[sic]</sup> — организација процесора]]
<div class="abc-list">
# Написати секвенцу инструкција (микроинструкција) циљне RISC архитектуре у коју се обавља пресликавање за део инструкцијског сета из табеле 3.1. изворишне CISC архитектуре. Уколико је потребно проширити број регистара опште намене у регистарском фајлу, онда треба за сваки додат регистар написати чему служи. Регистар R13 представља указивач на врх стека (SP) и показује на последњу слободну локацију. Стек расте према вишим адресама. Регистар R14 представља указивач на базну адресу стека (BP). Регистар R0 се користи као акумулатор, регистар R12 се користи као бројачки регистар и као такав има посебне инструкције које га користе. У табели 3.1. акције нису оптимизовано написане, већ описно.
# Нацртати формат инструкција циљне RISC архитектуре (на основу инструкција из табеле 3.1.).
</div>
{| class="wikitable"
|+ Табела 3.1. — део инструкцијског сета процесора
! Асемблерска инструкција
! Акција
! Микро инструкције
|-
| <code>SWP Rx</code>
|
MEM[Rx] ↔ ACC
|
|-
| <code>DEC</code>
|
ACC = ACC - 1
|
|-
| <code>RTS</code>
|
POP PC
|
|-
| <code>LOOP disp</code>
|
R12 = R12 - 1
IF R12 == 0 THEN
PC = PC + disp
|
|-
| <code>JMP adr</code>
|
PC = adr
|
|-
| <code>ADD (adr)</code>
|
ACC = ACC + MEM[MEM[adr]]
|
|-
| <code>LDB Rx</code>
|
ACC = 0.Rx<sub>7..0</sub>
|
|-
| <code>STRLEN adr</code>
|
ACC = 0
WHILE MEM[adr] != 0 DO
ACC = ACC + 1
adr = adr + 1
END WHILE
|
|-
| <code>VECADD adr</code>
|
R1 = R1 + MEM[adr]
R2 = R2 + MEM[adr]
R3 = R3 + MEM[adr]
R4 = R4 + MEM[adr]
|
|-
| <code>MUL R1</code>
|
TMP = ACC
ACC = 0
FOR X = 0; X < R1; X++ DO
ACC = ACC + TMP
END FOR
|
|}

=== Решење ===
Претпоставља се да се под AX регистром у задатку мисли на акумулатор. Уводимо регистре:
* R16: привремени регистар
* R17: вредност 0
* R18: још један привремени регистар
{| class="wikitable"
|+ Решење трећег задатка.
! Асемблерска инструкција
! Акција
! Микро инструкције
! Коментар
|-
| <code>SWP Rx</code>
|
MEM[Rx] ↔ ACC
|
LD R0, (Rx)0
ADDIS R16, R0, #0
ST R16, (Rx)0
| Уколико би после ове секвенце микроинструкција дошла микроинструкција која користи меморију, то би био хазард по подацима.
|-
| <code>DEC</code>
|
ACC = ACC - 1
|
ADDIS R0, R0, #-1
|-
| <code>RTS</code>
|
POP PC
|
LD R16, (R13)-1
ADDI R13, R13, #-1
BEQZ R17, (R17+R16)
| У последњој инструкцији се кроз горњи мултиплексер пропушта вредност R17 (0), која се користи и као услов скока, а кроз доњи вредност R16, која садржи жељену вредност PC, па стога и специфичан начин обележавања (који је еквивалентан са <code>(R16)0</code>).
|-
| <code>LOOP disp</code>
|
R12 = R12 - 1
IF R12 == 0 THEN
PC = PC + disp
|
SUB R12, R12, #1
BEQZPI R12, (PC)disp
|
|-
| <code>JMP adr</code>
|
PC = adr
|
BEQZI R17, (R17)adr
|-
| <code>ADD (adr)</code>
|
ACC = ACC + MEM[MEM[adr]]
|
LD R16, (R17)adr
LD R16, (R16)0
ADDS R0, R0, R16
| Дешава се хазард по подацима између прве и друге и између друге и треће микроинструкције.
|-
| <code>LDB Rx</code>
|
ACC = 0.Rx<sub>7..0</sub>
|
ANDIS R0, RX, #00FF
|
|-
| <code>STRLEN adr</code>
|
ACC = 0
WHILE MEM[adr] != 0 DO
ACC = ACC + 1
adr = adr + 1
END WHILE
|
ADDI R0, R17, #0
LD R16, (R0)adr
ADDI R0, R0, #1
BNEZPI R16, (PC)-3 * len(mInst)
ADDIS R0, R0, #-1
| За ову ставку је речено на колоквијуму да може да се претпостави како PC броји микроинструкције уместо инструкције. Главне идеје су да се уклони хазард тиме што радимо <code>ADD</code> инструкцију испод <code>LD</code>, да се акумулатор користи уместо неког новог регистра за чување <code>adr</code> (јер се свакако увећава сваке итерације) и да након петље која обухвата другу, трећу и четврту микроинструкцију морамо смањити акумулатор за један, јер нам је претходна петља ефективно била ''do-while'' уместо ''while''.
|-
| <code>VECADD adr</code>
|
R1 = R1 + MEM[adr]
R2 = R2 + MEM[adr]
R3 = R3 + MEM[adr]
R4 = R4 + MEM[adr]
|
LD R16, (R17)adr
ADDI R18, R17, #adr
LD R16, (R18)1
ADD R1, R1, R16
LD R16, (R18)2
ADD R2, R2, R16
LD R16, (R18)3
ADD R3, R3, R16
ADD R4, R4, R16
| Разлог из ког ова секвенца микроинструкција може изгледати чудно јесте избегавање хазарда по подацима. Са учитавањем првог податка почиње се већ у првој микроинструкцији, али како у међувремену треба обавити чување <code>adr</code> у новом привременом регистру и започињање новог учитавања, она се не сабира са регистром R1 до четврте микроинструкције (када је та вредност и даље доступна у одговарајућем регистру). Након тога се логика понавља неколико пута: започели смо учитавање наредног податка, а док се тај податак учитава ми радимо сабирање претходно учитаног податка са одговарајућим регистром. Како је до девете микроинструкције завршено учитавање и последњег податка, можемо извршити последње сабирање.
|-
| <code>MUL R1</code>
|
TMP = ACC
ACC = 0
FOR X = 0; X < R1; X++ DO
ACC = ACC + TMP
END FOR
|
ADDI R16, R0, #0
ADDIS R0, R17, #0
ADDI R18, R1, #0
ADDS R0, R0, R16
ADDI R18, R18, #-1
BNEZPI R18, (PC)-3 * len(mInst)
SUB R0, R0, R16
| Идеја јесте да R16 користимо као претходну вредност акумулатора и R18 као бројач итерација који почиње од R1 и завршава се са 0. Уколико би нам провера за <code>R18 == 0</code> била на врху, наша петља би се састојала из четири микроинструкције: провере, сабирања, декрементирања и безусловног скока. Уместо тога, проверу стављамо на дно па се наша петља састоји од три микроинструкције (резултујући у мањем укупном броју извршених микроинструкција), али због тога што смо опет ефективно направили ''do-while'' петљу ефекат последње итерације морамо да поништимо на крају. Као и за <code>STRLEN</code>, за ову ставку може да се претпостави како PC броји микроинструкције уместо инструкције. (На колоквијуму је накнадно речено да је податак у R1 означен, али то у овом решењу није узето у обзир јер такво коришћење и нема смисла.)
|}
Користимо укупно седам RISC инструкција у овом сету:
# LD
# ST
# ADD
# SUB
# AND
# BEQZ
# BNEZ
Ово нам оставља следећи формат инструкције:
{| class="wikitable"
|+ Формат инструкције у четвртом задатку
! 36 !! 35 !! 34 !! 33 !! 32 !! 31 !! 30 !! 29 !! 28 !! 27 !! 26 !! 25 !! 24 !! 23 !! 22 !! 21 !! 20 !! 19 !! 18 !! 17 !! 16 !! 15 !! 14 !! 13 !! 12 !! 11 !! 10 !! 9 !! 8 !! 7 !! 6 !! 5 !! 4 !! 3 !! 2 !! 1 !! 0
|-
| colspan="3" | Код
| colspan="3" | PIS флегови
| colspan="5" | Одредишни регистар
| colspan="5" | Изворишни регистар 1
| colspan="5" | Изворишни регистар 2
| colspan="16" | Непосредна вредност
|}

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

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

2023-08-27T08:58:39Z

Jaksa: /* Rešenje */

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

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

=== Rešenje ===
<syntaxhighlight lang="asm">
log: LD R1, #n[SP]
CMP R1, #2
JGE else
LD R0, #0
RTS
else: LD R0, #1
SHR R1, R0
PUSH R1
CALL log
POP R1
ADD R0, #1 //zato sto se nakon poziva f-je log, povratna vrednost nalazi u registru R0
RTS
</syntaxhighlight>

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

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

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

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

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

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

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

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

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

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

== 6. zadatak ==
=== Postavka ===
Navesti osnovne sličnosti i osnovne razlike između tehnike dinamičkog učitavanja memorije i preklopa (''overlays'').

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

== 7. zadatak ==
=== Postavka ===
Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, deskriptor stranice je 32-bitni, a PMT je organizovana u dva nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. U koje ulaze PMT prvog nivoa i drugog nivoa se preslikava stranica broj 5423Dh?

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

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

=== Rešenje ===
Videti [[ОС1/Јун 2013#8. zadatak|8. zadatak iz junskog roka 2013. godine]].

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

=== Rešenje ===
# Ne
# Da

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

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

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

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

2023-08-27T08:58:12Z

Jaksa: /* Rešenje */

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

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

=== Rešenje ===
<syntaxhighlight lang="asm">
log: LD R1, #n[SP]
CMP R1, #2
JGE else
LD R0, #0
RTS
else: LD R0, #1
SHR R1, R0
PUSH R1
CALL log
POP R1
ADD R0, #1
RTS
</syntaxhighlight>

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

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

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

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

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

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

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

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

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

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

== 6. zadatak ==
=== Postavka ===
Navesti osnovne sličnosti i osnovne razlike između tehnike dinamičkog učitavanja memorije i preklopa (''overlays'').

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

== 7. zadatak ==
=== Postavka ===
Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, deskriptor stranice je 32-bitni, a PMT je organizovana u dva nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. U koje ulaze PMT prvog nivoa i drugog nivoa se preslikava stranica broj 5423Dh?

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

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

=== Rešenje ===
Videti [[ОС1/Јун 2013#8. zadatak|8. zadatak iz junskog roka 2013. godine]].

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

=== Rešenje ===
# Ne
# Da

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

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

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

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

2023-08-27T08:55:50Z

Jaksa: /* Rešenje */

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

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

=== Rešenje ===
<syntaxhighlight lang="asm">
log: LD R1, #n[SP]
CMP R1, #2
JGE else
LD R0, #0
RTS
else: LD R0, #1
SHR R1, R0
PUSH R1
CALL log
POP R1
ADD R0, R1
RTS
</syntaxhighlight>

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

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

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

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

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

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

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

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

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

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

== 6. zadatak ==
=== Postavka ===
Navesti osnovne sličnosti i osnovne razlike između tehnike dinamičkog učitavanja memorije i preklopa (''overlays'').

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

== 7. zadatak ==
=== Postavka ===
Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, deskriptor stranice je 32-bitni, a PMT je organizovana u dva nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. U koje ulaze PMT prvog nivoa i drugog nivoa se preslikava stranica broj 5423Dh?

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

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

=== Rešenje ===
Videti [[ОС1/Јун 2013#8. zadatak|8. zadatak iz junskog roka 2013. godine]].

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

=== Rešenje ===
# Ne
# Da

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

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

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

ОС1/Јул 2017

2023-08-26T17:58:16Z

Jaksa: /* Rešenje */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2017/jul/Jul%202017.pdf Zadaci sa stranice predmeta.]

== 1. zadatak ==
=== Postavka ===
Šta je hard, a šta soft sistem za rad u realnom vremenu (real-time system)?

=== Rešenje ===
Tvrdi sistemi za rad u realnom vremenu su sistemi u kojima odziv mora da stigne u određenom vremenu (''deadline''). Prekoračenje može dovesti do rezličitih katastrofa. Meki sistemi za rad u realnom vremenu su sistemi kojima je rok bitan ali smeju ga prekoračiti dok god performanse ulaze u zadate okvire.

== 2. zadatak ==
=== Postavka ===
Objasniti značenje mašinske instrukcije tipa ''test-and-set'' i njenu upotrebu u jezgru operativnog sistema.

=== Rešenje ===
<code>test_and_set</code> je instrukcija koja omogućava sinhronizaciju na hardverskom nivou. Služi za međusobno isključenje izvršavanja na više procesora. Ona atomično čita i vraća sadržaj zadate memorijske lokacije, i u tu lokaciju upisuje vrednost 1. Može da se koristi u implementaciji <code>lock()</code> funkcije.

== 3. zadatak ==
=== Postavka ===
Korišćenjem školskog jezgra napisati program koji u ''n'' uporednih niti izračunava kvadrat svakog elementa nekog celobrojnog niza (<code>a[i]*=a[i]</code>) veličine ''n*k'', tako što svaka nit obrađuje ''k'' elemanata<sup>[sic]</sup> (jednu particiju niza).

=== Rešenje ===
<syntaxhighlight lang="c++">
class ArrThread : Thread {
public:
ArrThread(int* a, int s, int f): arr(a), start(s), finish(f) {}
protected:
void run() {
for (int i = start; i < finish; i++) {
arr[i] *= arr[i];
}
}
private:
int* arr;
int start;
int finish;
};

int main() {
ArrThread* t[n];
int start = 0;
for (int i = 0; i < n; i++) {
t[i] = new ArrThread(array, start, start + k);
start += k;
}
for (int i = 0; i < n; i++) {
delete t[i];
}
return 0;
}
</syntaxhighlight>

== 4. zadatak ==
Videti zadatak iz [[ОС1/Јул 2019#4. zadatak|julskog roka 2019]].

== 5. zadatak ==
=== Postavka ===
Precizno objasniti zašto klasičan linker svoj posao obavlja u dva prolaza (a ne može samo ujednom). Obrazloženje ilustrovati primerom.

=== Rešenje ===
Linkerov zadatak je da spoji sve fajlove u jedan izvršni, ali da bi to uradio, linker mora naći sve simbole koji se uvoze odnosno izvoze.

U prvom prolazu analizira ulazne fajlove, veličinu njihovog binarnog sadržaja (prevoda), i pravi mapu ''exe'' fajla; osim toga, sakuplja infomacije iz tabela simbola ''obj'' fajlova i izgrađuje svoju tabelu simbola; u tu tabelu simbola unosi izvezene simbole iz ''obj'' fajlova, za koje odmah može da izračuna adresu u odnosu na ceo ''exe'' fajl. U drugom prolazu spaja sve te fajlove u jedan, i ujedno razrešava nerazrešena adresna polja mašinskih instrukcija na osnovu informacija o adresama u koje se preslikavaju simboli iz njegove tabele simbola.

Primer: Recimo da imamo dva objektna fajla, <code>a.obj</code> i <code>b.obj</code>. <code>a.obj</code> izvozi simbol <code>f</code> i uvozi simbol <code>c</code>. Linker će iz prvog objektnog fajla dodati u tabelu simbol <code>f</code>. <code>b.obj</code> uvozi simbol <code>f</code> i izvozi simbol <code>c</code>, pa će linker u svoju tabelu dodati simbol <code>c</code>. U drugom prolazu će linker razrešiti <code>c</code> polje u <code>a.obj</code> i polje <code>f</code> u <code>b.obj</code>.

== 6. zadatak ==
=== Postavka ===
Objasniti uslugu koju program očekuje od operativnog sistema ako koristi preklope (''overlay'').

=== Rešenje ===
Obaveza OS-a je samo da obezbedi uslugu (sistemski poziv) koji alocira deo (virtuelnog) adresnog prostora procesa, kao i uslugu kojom u dati prostor procesa učitava sadržaj iz nekog binarnog fajla i sadržaj iz memorije upisuje u neki fajl (uobičajene sistemske usluge za rad sa fajlovima); OS ne zna za šta se te usluge koriste, tj. ne zna da se one upotrebljavaju baš za dinamičko učitavanje i zamenu delova procesa.

== 7. zadatak ==
=== Postavka ===
Virtuelni adresni prostor je veličine 1GB, organizovan je segmentno, sa maksimalnom veličinom segmenta od 4KB, adresibilna jedinica je bajt. Svi segmenti nekog procesa su stvarne veličine od po 2KB i u fizičku memoriju smešteni su odmah jedan iza drugog, pri čemu segment broj 0 počinje od fizičke adrese F000h. Prikazati logičku strukturu virtuelne adrese i izračunati u koju fizičku adresu se preslikava virtuelna adresa 2543h.

=== Rešenje ===
VA(30) : seg(18) offset(12)

Virtuelna adresa 2543h tj. 0010 | 0101 0100 0011b pripada 2. segmentu koji počinje od fizičke adrese 10000h i završava na 10800h.

Fizička adresa se dobija sabiranjem bazne adrese u fizičkom adresnom prostoru i offsetnog dela virtuelne adrese:
PA = 10000h + 543h = 10543h.

== 8. zadatak ==
Videti zadatak iz [[ОС1/Јун 2021#6. zadatak|junskog roka 2021. godine]].

== 9. zadatak ==
Videti zadatak iz [[ОС1/Јун 2020#7. zadatak|junskog roka 2020. godine]].

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

=== Rešenje ===
Pošto je blok veličine <math>2^{19}B</math> a adresa <math>2^3B</math> to znači da u jedan indeks može da stane <math>2^{16}</math> adresa blokova. Konačan broj bajtova koji je na ovaj način mogu adresirati jeste <math>2^{16} \cdot 2^{16} \cdot 2^{19} = 2^{51}B = 2PB</math>.

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

ОС1/Јул 2019

2023-08-26T17:45:52Z

Jaksa: /* 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 ===
Ne. Ukoliko bi se na tom steku čuvao kontekst prekinutog procesa, jedino na njega bismo se mogli i vratiti jer bi svi ostali konteksti bili ispod kontekteksta trenutnog procesa na steku.

== 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 Thread {
public:
SumThread(int* arr, size_t _size, long* res): array(arr), size(_size), result(res) {}
protected:
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/Јул 2020

2023-08-26T17:19:34Z

Jaksa: /* Rešenje */

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

== 1. 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 ===
Pretpostavke:
* Memorija se prenosi sa adrese 1000h
* Ulazno/izlazni i adresni prostor su razdvojeni
* Kontrolni registar uređaja je na FF00h, registar podataka na FF01h a statusni registar na FF02h
* Adresiranje je bajtovsko
* Blok je veličine 100h bajtova
* Registri su veličine 16 bita i kad se čita ili piše iz memorije ili na uređaj koristi se najnižih 8 bita
* Najniži bit kontrolnog registra je bit ''Start'', najniži bit statusnog registra je bit ''Ready''
* Periferija automatski postaje nespremna za upis sledećeg podatka kada se u nju upiše podatak koji se još nije preneo
<syntaxhighlight lang="asm">
load r0, #1000h ; adresa
load r1, #100h ; brojač
load r2, #0 ; nula
load r3, #1 ; privremeni registar
out FF00h, r3 ; pokrećemo periferiju
loop: in FF02h, r3 ; čitamo statusni registar
and r3, r3, #1 ; proveravamo ready bit
jz loop ; ako je ready = 0 čitamo ponovo
load r3, (r0) ; učitavamo podatak iz memorije
out FF01h, r3 ; šaljemo podatak na periferiju
inc r0 ; inkrementiramo adresu
dec r1 ; dekrementiramo brojač (postavlja se PSW)
jnz loop ; ako brojač != 0 vraćamo se na čekanje
load r3, #0 ; gasimo periferiju
out FF00h, r3
</syntaxhighlight>

== 2. 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 za jedan manjim istim celobrojnim parametrom (sve dok ne stigne do 0), a u suprotnom se samo završava.

=== Rešenje ===
<syntaxhighlight lang="cpp">
class ForkThread : public Thread {
public:
ForkThread(unsigned n) : n(n) {}
protected:
virtual void run();
private:
unsigned n;
};

void ForkThread::run() {
if (n % 2) {
ForkThread thr(n-1);
thr.start();
thr.join();
}
}
</syntaxhighlight>

== 3. 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 ===
Po koracima, alokacija memorije će izgledati ovako (jedno slovo = 16KB):
AAAAAAAABBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDD--
--------BBCCCCCCCCCCCCCCCCDDDDE-
FFFF----BBCCCCCCCCCCCCCCCCDDDDE-
FFFF------CCCCCCCCCCCCCCCCDDDDE-
# 2 su slobodna fragmenta.
# Najmanji slobodan fragment je 16KB.
# Najveći slobodan fragment je 96KB.

== 4. zadatak ==
=== Postavka ===
Virtuelna memorija organizovana je stranično, a adresibilna jedinica je bajt. Virtuelna adresa je 32-bitna, stranica je veličine 4KB, PMT je organizovana u dva nivoa, deskriptor stranice je 32-bitni u tabelama oba nivoa, pri čemu je polje za straničenje prvog nivoa veličine 8 bita. Koliki prostor bi ukupno zauzimala PMT nekog procesa kada bi taj proces:
<div class="abc-list">
# koristio ceo svoj virtuelni adresni prostor?
# alocirao samo jedan logički segment veličine samo jedne stranice?
</div>

=== Rešenje ===
Adresa ima strukturu VA(32): Page1(8) Page2(12) Offset(12). PMT prvog nivoa ima <math>2^8</math> ulaza, a PMT drugog nivoa <math>2^{12}</math>, i oba imaju ulaze veličine <math>2^2</math> bajtova.
* <math>2^8 * 2^{12} * 2^2 + 2^8 * 2^2 = 2^{22} + 2^{10} = 4M + 1K</math>
* <math>2^8 * 2^2 + 2^{12} * 2^2 = 2^{10} + 2^{14} = 1K + 16K = 17K</math>

== 5. 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 ===
Nedostatak ove tehnike je što se procesi dok čekaju na štampač blokiraju, a za to vreme su mogli da rade nešto korisnije.

== 6. zadatak ==
=== Postavka ===
Neki fajl sistem pruža sledeće operacije u svom API za tekstualne fajlove:
* <syntaxhighlight lang="c" inline>FHANDLE open(char* filename)</syntaxhighlight> Otvara fajl sa datim imenom.
* <syntaxhighlight lang="c" inline>void close(FHANDLE)</syntaxhighlight> Zatvara dati fajl.
* <syntaxhighlight lang="c" inline>int size(FHANDLE)</syntaxhighlight> Vraća trenutnu veličinu sadržaja fajla u znakovima.
* <syntaxhighlight lang="c" inline>void append(FHANDLE, int)</syntaxhighlight> Proširuje sadržaj fajla za dati broj znakova na kraju.
* <syntaxhighlight lang="c" inline>void seek(FHANDLE, int)</syntaxhighlight> Postavlja kurzor datog fajla na datu poziciju (redni broj znaka počev od 0).
* <syntaxhighlight lang="c" inline>void write(FHANDLE, char*)</syntaxhighlight> 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">
int main(void) {
FHANDLE file = open("proba.txt");
seek(file, size(file));
char buf[2];
buf[1] = '\0';
while (true) {
buf[0] = getchar();
if (buf[0] == 'X') {
break;
}
append(file, 1);
write(file, buf);
}
close(file);
return 0;
}
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
Koliko pristupa blokovima na disku treba izvršiti za pristup ''n''-tom logičkom bloku sadržaja fajla ako je alokacija fajla
<div class="abc-list">
# 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, a broj tog bloka zapisan je u FCB koji je učitan prilikom otvaranja fajla?
</div>

=== Rešenje ===
<div class="abc-list">
# 1, jer je FAT već u memoriji pa se samo treba pristupiti bloku koji je tražen.
# 2, jedan da se pročita blok sa indeksom i jedan da se pristupi bloku koji je tražen.
</div>

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

ОС1/Јун 2012

2023-08-26T15:58:14Z

Jaksa: /* Rešenje */

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="asm">
f: LD R0, #0 ;Registar u kome se nalazi povratna vrednost
LD R1, #n[SP]
CMP R1, R0
JG else
RTS
else: LD R2, #1
SUB R1, R2
PUSH R1
call f ;nakon zavrsetka funkcije f, u R0 se nalazi rezultat
POP R1
ADD R0, R2
RTS
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Ukoliko su svi sistemski pozivi izvršeni uspešno, koliko procesa se ukupno kreira kada se nad sledećim programom kreira jedan proces (računajući i taj jedan)?
<syntaxhighlight lang="c">
void main() {
for (int i = 0; i < 7; i++) if (fork() > 0) return;
}
</syntaxhighlight>

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

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

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

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

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

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

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

== 6. zadatak ==
=== Postavka ===
Neki sistem primenjuje kontinualnu alokaciju memorije i ''best-fit'' algoritam alokacije, pri čemu su segmenti slobodne memorije organizovani u sledeću strukturu podataka:
# sortiranu ulančanu listu,
# balansirano binarno stablo.
Koliko segmenata treba obići u najgorem slučaju da bi se pronašao odgovarajući slobodan segment prilikom alokacije, ukoliko je slobodnih segmenata ''n''?

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

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

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

Odgovor: <math>30\%</math>

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

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

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="c">
void write(FHANDLE f, int position, char* s, int size){
int curSize = size(f);
if(position + size > curSize){
append(f, position + size - curSize);
}
seek(f, position);
write(f, s, size);
}
</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:
# ulančana lista blokova, pri čemu na prvi blok sadržaja fajla ukazuje polje u FCB,
# indeksna, pri čemu je indeks fajla uvek u dva nivoa, a na blok sa indeksom prvog nivoa ukazuje polje u FCB? FCB fajla je u memoriji

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

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

ОС1/Јун 2012

2023-08-26T14:03:13Z

Jaksa: /* Rešenje */

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="asm">
f: LD R0, #0 ;Registar u kome se nalazi povratna vrednost
LD R1, #n[SP]
CMP R1, R0
JG else
RTS
else: LD R2, #1
SUB R1, R2
PUSH R1
call f ;nakon zavrsetka funkcije f, u R0 se nalazi rezultat
POP R1
ADD R0, R2
RTS
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Ukoliko su svi sistemski pozivi izvršeni uspešno, koliko procesa se ukupno kreira kada se nad sledećim programom kreira jedan proces (računajući i taj jedan)?
<syntaxhighlight lang="c">
void main() {
for (int i = 0; i < 7; i++) if (fork() > 0) return;
}
</syntaxhighlight>

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

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

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

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

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

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

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

== 6. zadatak ==
=== Postavka ===
Neki sistem primenjuje kontinualnu alokaciju memorije i ''best-fit'' algoritam alokacije, pri čemu su segmenti slobodne memorije organizovani u sledeću strukturu podataka:
# sortiranu ulančanu listu,
# balansirano binarno stablo.
Koliko segmenata treba obići u najgorem slučaju da bi se pronašao odgovarajući slobodan segment prilikom alokacije, ukoliko je slobodnih segmenata ''n''?

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

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

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

Odgovor: <math>30\%</math>

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

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

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="c">
void write(FHANDLE f, int position, char* s, int size){
int curSize = size(f);
if(position + size >= curSize){
append(f, position + size + 1 - curSize);
}
seek(f, position);
write(f, s, size);
}
</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:
# ulančana lista blokova, pri čemu na prvi blok sadržaja fajla ukazuje polje u FCB,
# indeksna, pri čemu je indeks fajla uvek u dva nivoa, a na blok sa indeksom prvog nivoa ukazuje polje u FCB? FCB fajla je u memoriji

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

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

ОС1/Јун 2012

2023-08-26T14:02:59Z

Jaksa: /* Rešenje */

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="asm">
f: LD R0, #0 ;Registar u kome se nalazi povratna vrednost
LD R1, #n[SP]
CMP R1, R0
JG else
RTS
else: LD R2, #1
SUB R1, R2
PUSH R1
call f ;nakon zavrsetka funkcije f, u R0 se nalazi rezultat
POP R1
ADD R0, R2
RTS
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Ukoliko su svi sistemski pozivi izvršeni uspešno, koliko procesa se ukupno kreira kada se nad sledećim programom kreira jedan proces (računajući i taj jedan)?
<syntaxhighlight lang="c">
void main() {
for (int i = 0; i < 7; i++) if (fork() > 0) return;
}
</syntaxhighlight>

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

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

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

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

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

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

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

== 6. zadatak ==
=== Postavka ===
Neki sistem primenjuje kontinualnu alokaciju memorije i ''best-fit'' algoritam alokacije, pri čemu su segmenti slobodne memorije organizovani u sledeću strukturu podataka:
# sortiranu ulančanu listu,
# balansirano binarno stablo.
Koliko segmenata treba obići u najgorem slučaju da bi se pronašao odgovarajući slobodan segment prilikom alokacije, ukoliko je slobodnih segmenata ''n''?

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

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

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

Odgovor: <math>30\%</math>

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

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

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="c">
void write(FHANDLE f, int position, char* s, int size){
int curSize = size(f);
if(position + size > curSize){
append(f, position + size + 1 - curSize);
}
seek(f, position);
write(f, s, size);
}
</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:
# ulančana lista blokova, pri čemu na prvi blok sadržaja fajla ukazuje polje u FCB,
# indeksna, pri čemu je indeks fajla uvek u dva nivoa, a na blok sa indeksom prvog nivoa ukazuje polje u FCB? FCB fajla je u memoriji

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

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

ОС1/Јун 2012

2023-08-26T13:57:56Z

Jaksa: /* Rešenje */

ОС1/Јун 2014

2023-08-26T12:33:18Z

Jaksa: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Ukratko objasniti značenje pojmova multiprogramiranje i multiprocesiranje.

=== Rešenje ===
Videti zadatak iz [[ОС1/Јануар 2014#1. zadatak|januarskog roka 2014]].

== 2. zadatak ==
=== Postavka ===
Korišćenjem standardnih bibliotečnih funkcija <code>setjmp()</code> i <code>longjmp()</code> implementirati funkciju <syntaxhighlight lang="c" inline>void yield(jmp_buf old, jmp_buf new)</syntaxhighlight> koja vrši promenu konteksta procesora.

=== Rešenje ===
<syntaxhighlight lang="c">
void yield(jmp_buf old, jmp_buf new) {
if (setjmp(old) == 0) {
longjmp(new, 1);
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Korišćenjem niti u školskom jezgru (klasa <code>Thread</code>) napisati kod koji konkurentno i rekurzivno obilazi binarno stablo tako što tekuća nit nastavlja da obilazi levo podstablo, a kreira novu nit koja će obići desno podstablo. Struktura <syntaxhighlight lang="c" inline>Node {Node *left, *right}</syntaxhighlight> predstavlja čvor stabla

=== Rešenje ===
<syntaxhighlight lang="c">
class MyThread : public Thread {
public:
MyThread(Node* root) {
this->root = root;
start();
}
protected:
void run() {
visit(root);
}
private:
Node* root;
};

void visit(Node* root) {
if (root->right) {
new MyThread(root->right);
}
if (root->left) {
visit(root->left);
}
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Korišćenjem standardnih brojačkih semafora napisati kod za kontrolu kritične sekcije koju uporedo sme da izvršava najviše ''N'' procesa.

=== Rešenje ===
Videti zadatak iz [[ОС1/Јун 2013#4. zadatak|junskog roka 2013]].

== 5. zadatak ==
=== Postavka ===
Šta je osnovni razlog toga (osnovni problem koji se rešava time) što linker svoj posao obavlja u dva prolaza? Precizno i kratko objasniti.

=== Rešenje ===
Videti rešenje [[ОС1/Јул 2017#5. zadatak|5. zadatka iz jula 2017. godine]].

== 6. zadatak ==
=== Postavka ===
Objasniti kako se kod kontinualne alokacije memorije obezbeđuje zaštita memorijskog prostora drugih procesa od ilegalnog adresiranja jednog procesa.

=== Rešenje ===
Zaštita memorijskog prostora drugih procesa od ilegalnog adresiranja jednog procesa kod kontinualne alokacije se obezbeđuje limit registrom. U ovaj registar procesora OS upisuje vrednost prilikom promene konteksta.

== 7. zadatak ==
=== Postavka ===
U nekom sistemu sa straničnom organizacijom virtuelne memorije virtuelna i fizička adresa su 32-bitne, adresibilna jedinica je bajt, a stranica je veličine 64 KB. PMT je organizovana u dva nivoa i jedan ulaz u PMT oba nivoa zauzima po jednu 32-bitnu reč. PMT oba nivoa su iste veličine. Koliko ukupno zauzimaju PMT za proces koji je alocirao samo svoju prvu i poslednju stranicu?

=== Rešenje ===
<math>2^8 \cdot 4B + 2 \cdot 2^8 \cdot 4B = 3KB</math>

== 8. zadatak ==
=== Postavka ===
Ukratko objasniti tehniku dvostrukog baferisanja.

=== Rešenje ===
Koristi se kod sprege uređaja ili tokova kontrole koji su jako različiti po brzini transfera ili jedinici prenosa. Uvode se 2 bafera.

U prvoj fazi bafer A je ulazni bafer, bafer za proizvođača, a bafer B je izlazni bafer, bafer za potrošača. Kada oba učesnika završe fazu punjenja tj. pražnjenja svog bafera, baferi A i B menjaju uloge.

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem koristi dve vrste ključeva za fajlove, deljene i ekskluzivne, i fajlove zaključava prilikom otvaranja fajla, u zavisnosti od najavljenog načina korišćenja fajla. Procesi A, B, C i D izvršavaju sistemske pozive otvaranja i zatvaranja istog fajla u sledećem redosledu (neki proces izvršava poziv zatvaranja fajla samo ako ga je uspešno otvorio):
# A: open(READ)
# B: open(WRITE)
# C: open(READ)
# A: close
# C: close
# D: open(WRITE)

=== Rešenje ===
Operacija 2. će se izvršiti neuspešno, a ostale uspešno.

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

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

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

ОС1/Јун 2014

2023-08-26T12:32:58Z

Jaksa: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Ukratko objasniti značenje pojmova multiprogramiranje i multiprocesiranje.

=== Rešenje ===
Videti zadatak iz [[ОС1/Јануар 2014#1. zadatak|januarskog roka 2014]].

== 2. zadatak ==
=== Postavka ===
Korišćenjem standardnih bibliotečnih funkcija <code>setjmp()</code> i <code>longjmp()</code> implementirati funkciju <syntaxhighlight lang="c" inline>void yield(jmp_buf old, jmp_buf new)</syntaxhighlight> koja vrši promenu konteksta procesora.

=== Rešenje ===
<syntaxhighlight lang="c">
void yield(jmp_buf old, jmp_buf new) {
if (setjmp(old) == 0) {
longjmp(new, 1);
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Korišćenjem niti u školskom jezgru (klasa <code>Thread</code>) napisati kod koji konkurentno i rekurzivno obilazi binarno stablo tako što tekuća nit nastavlja da obilazi levo podstablo, a kreira novu nit koja će obići desno podstablo. Struktura <syntaxhighlight lang="c" inline>Node {Node *left, *right}</syntaxhighlight> predstavlja čvor stabla

=== Rešenje ===
<syntaxhighlight lang="c">
class MyThread : public Thread {
public:
MyThread(Node* root) {
this->root = root;
start();
}
protected:
void run() {
visit(root);
}
private:
Node* root;
};

void visit(Node* root) {
if (root->right) {
new MyThread(root->right);
}
if (root->left) {
visit(root->left);
}
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Korišćenjem standardnih brojačkih semafora napisati kod za kontrolu kritične sekcije koju uporedo sme da izvršava najviše ''N'' procesa.

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

== 5. zadatak ==
=== Postavka ===
Šta je osnovni razlog toga (osnovni problem koji se rešava time) što linker svoj posao obavlja u dva prolaza? Precizno i kratko objasniti.

=== Rešenje ===
Videti rešenje [[ОС1/Јул 2017#5. zadatak|5. zadatka iz jula 2017. godine]].

== 6. zadatak ==
=== Postavka ===
Objasniti kako se kod kontinualne alokacije memorije obezbeđuje zaštita memorijskog prostora drugih procesa od ilegalnog adresiranja jednog procesa.

=== Rešenje ===
Zaštita memorijskog prostora drugih procesa od ilegalnog adresiranja jednog procesa kod kontinualne alokacije se obezbeđuje limit registrom. U ovaj registar procesora OS upisuje vrednost prilikom promene konteksta.

== 7. zadatak ==
=== Postavka ===
U nekom sistemu sa straničnom organizacijom virtuelne memorije virtuelna i fizička adresa su 32-bitne, adresibilna jedinica je bajt, a stranica je veličine 64 KB. PMT je organizovana u dva nivoa i jedan ulaz u PMT oba nivoa zauzima po jednu 32-bitnu reč. PMT oba nivoa su iste veličine. Koliko ukupno zauzimaju PMT za proces koji je alocirao samo svoju prvu i poslednju stranicu?

=== Rešenje ===
<math>2^8 \cdot 4B + 2 \cdot 2^8 \cdot 4B = 3KB</math>

== 8. zadatak ==
=== Postavka ===
Ukratko objasniti tehniku dvostrukog baferisanja.

=== Rešenje ===
Koristi se kod sprege uređaja ili tokova kontrole koji su jako različiti po brzini transfera ili jedinici prenosa. Uvode se 2 bafera.

U prvoj fazi bafer A je ulazni bafer, bafer za proizvođača, a bafer B je izlazni bafer, bafer za potrošača. Kada oba učesnika završe fazu punjenja tj. pražnjenja svog bafera, baferi A i B menjaju uloge.

== 9. zadatak ==
=== Postavka ===
Neki fajl sistem koristi dve vrste ključeva za fajlove, deljene i ekskluzivne, i fajlove zaključava prilikom otvaranja fajla, u zavisnosti od najavljenog načina korišćenja fajla. Procesi A, B, C i D izvršavaju sistemske pozive otvaranja i zatvaranja istog fajla u sledećem redosledu (neki proces izvršava poziv zatvaranja fajla samo ako ga je uspešno otvorio):
# A: open(READ)
# B: open(WRITE)
# C: open(READ)
# A: close
# C: close
# D: open(WRITE)

=== Rešenje ===
Operacija 2. će se izvršiti neuspešno, a ostale uspešno.

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

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

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

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

2023-08-25T21:48:21Z

Jaksa: /* Rešenje */

{{tocright}}
[http://os.etf.bg.ac.rs/OS1/rokovi/2014/okt/OS1%20Okt%202014.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 ===
Korišćenjem standardnih bibliotečnih operacija <code>setjmp</code> i <code>longjmp</code>, implementirati operaciju <code>wait</code> na binarnom semaforu koji je realizovan klasom <code>Event</code> poput one u školskom jezgru.

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

== 3. zadatak ==
=== Postavka ===
Na jeziku C, korišćenjem sistemskog poziva <code>fork()</code> za Unix, napisati program koji prihvata celobrojni argument ''n'' i koji, kada se nad njim pokrene proces, pokreće jedan proces-dete i završava se, ovaj proces-dete pokreće svoje dete, itd, tako da ukupno bude ''n'' procesa u relaciji roditelj-dete (''n'' „generacija“).

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

== 4. zadatak ==
=== Postavka ===
Korišćenjem standardnih brojačkih semafora u školskom jezgru, na jeziku C++ napisati kod za ograničeni bafer (''bounded buffer'').

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

== 5. zadatak ==
=== Postavka ===
Koja je osnovna razlika između tehnika dinamičkog učitavanja i preklopa (''overlays'')?

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

== 6. zadatak ==
=== Postavka ===
Ko i kada upisuje vrednosti u registar bazne adrese i registar ograničenja procesora kod kontinualne alokacije memorije? Ukratko objasniti svrhu ovih registara.

=== Rešenje ===
Kada se kreira novi proces, stavlja se u ulazni red. OS alocira memorijske zahteve u ulaznom redu i trenutno stanje memorije i bira proces za učitavanje. OS učitava izabran proces i upisuje vrednost u base i limit registar. Bazni je koristan kod realokacije procesa a limit služi za zaštitu zauzete memorije jednog procesa od drugog.

== 7. zadatak ==
=== Postavka ===
Primenom tehnike ''copy-on-write'' kod virtuelne memorije, hardver je generisao izuzetak tipa „nedozvoljen upis u adresiranu stranicu“. Precizno objasniti šta dalje radi operativni sistem.

=== Rešenje ===
Kada proces prvi put upisuje u neku deljenu stranicu hardver generiše izuzetak tipa nedozvoljen upis u adresiranu stranicu. Operativni sistem zaključuje da je upis logički dozvoljen ali je stranica deljena, stranica se tada kopira, prestaje da bude deljena.

== 8. zadatak ==
=== Postavka ===
Navesti tipične operacije apstrakcije blokovski orijentisanog izlaznog uređaja sa '''sekvencijalnim''' pristupom.

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

== 9. 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 kako i zašto se ovo dogodilo.

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

== 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 cela FAT u memoriji
# kontinualna?

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

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

ОС1/Јун 2021

2023-08-25T20:00:41Z

Jaksa: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta je sistemski poziv, a šta sistemski program?

=== Rešenje ===
Sistemski poziv je određena funkcionalnost koju operativni sistem pruža korisničkim programima. Korisnički programi mogu pozvati sistemski poziv, često korišćenjem mehanizma softverskih prekida, kako bi od operativnog sistema zatražili neke osnovne usluge kojima najčešće iz korisničkog režima i nemaju pristup. Primer sistemskog poziva bi bio <code>fork()</code> na ''Unix-like'' sistemima.

Sistemski program je program koji obavlja osnovne operacije sa korisničkim sistemom, na primer brisanje fajlova (<code>rm</code> na ''Unix-like'' sistemima).

== 2. zadatak ==
=== Postavka ===
Šta su nedostaci organizacije memorije sa particijama?

=== Rešenje ===
* Pojavljuje se interna fragmentacija, jer ako procesu ne treba ceo svoj memorijski prostor onda je rezervisani deo prostora koji taj proces ne koristi bespotrebno bačen.
* Balansira se između veličine adresnog prostora jednog procesa i ukupnog broja procesa.
* Stepen multiprogramiranja (broj aktivnih procesa koji su u memoriji i koji se mogu uporedo izvršavati) je ograničen brojem particija.

== 3. zadatak ==
=== Postavka ===
Korisnik nekog računara radi u veb pregledaču (''web browser'') u kom je otvorio veliki broj kartica (''tab'') u kojima pregleda različite sajtove. Primetio je da mu se računar ponaša neobično, da sporo reaguje na akcije (ima veliko vreme odziva), da sporo prikazuje sadržaj stranica itd.
<div class="abc-list">
# ''Precizno'' objasniti zašto se ovo dešava.
# Korisnik je dalje primetio da kada zatvori većinu kartica i ostavi svega dve-tri, računar se ne ponaša ništa bolje. Ali kada ugasi ceo pregledač, računar se ponovo ponaša valjano. ''Precizno'' objasniti uzrok oba ova ponšaanja<sup>[sic]</sup>.
</div>

=== Rešenje ===
<div class="abc-list">
# Veb pregledači obično za svaki tab pokrenu odvojenu nit, tako da se sa više tabova češće dešava promena konteksta. Pored toga, veće je zauzeće memorije, i može da se dešava da se sve stranice u fizičkom adresnom prostoru potroše pa mora da se radi zamena stranica, što zahteva spore operacije upisa i čitanja sa spoljašnje memorije i više promašaja keša, a može doći i do batrganja.
# Moguće je da pretraživač ne oslobodi sve resurse koje je zauzeo, pa se gašenjem tabova ne oslobodi korišćena memorija. Kada se ugasi ceo proces, operativni sistem će osloboditi sve resurse koje je proces koristio pa će moći da nastavi sa normalnijim radom.
</div>

== 4. 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.

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

== 5. 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:
* A: upisuje vrednost u deljene promenljive <code>x</code> i <code>y</code>, a zatim čeka da proces B upiše zbir <code>x</code> i <code>y</code> u promenljivu <code>z</code> čiju vrednost onda ispisuje na standardni izlaz;
* B: čeka da proces A upiše vrednosti u deljene promenljive <code>x</code> i <code>y</code>, zatim ove dve vrednosti sabira i zbir upisuje u deljenu promenljivu <code>z</code>.

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

Semaphore waitA(0);
Semaphore waitB(0);

class A : public Thread {
public:
virtual void run() {
while (true) {
x = 1;
y = 2;
waitA.signal();
waitB.wait();
std::cout << z << std::endl;
}
}
};

class B : public Thread {
public:
virtual void run() {
while (true) {
waitA.wait();
z = x + y;
waitB.signal();
}
}
};

int main(void) {
A a;
B b;
a.start();
b.start();
a.join();
b.join();
return 0;
}
</syntaxhighlight>

== 6. 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 ===
Tehnikom ''spooling'' se nedeljevi uređaj može učiniti virtuelno deljivim, i klasičan primer takvog uređaja je štampač.

== 7. 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 ===
Maksimalna veličina fajla se dostiže kada svi ulazi u indeks prvog nivoa pokazuju na indekse drugog nivoa, a svi indeksi drugog nivoa pokazuju na zauzete blokove. Indeksi prvog i drugog nivoa su veličine jednog bloka, tako da se broj ulaza u indeksu dobija deljenjem veličine bloka (<math>256KB = 2^{18}B</math>) i veličine ulaza (<math>64b = 8B = 2^3B</math>): <math>\frac{2^{18}B}{2^3B} = 2^{15}</math>. To znači da je moguće adresirati <math>2^{15}</math> indeksa drugog nivoa, i iz svakog indeksa drugog nivoa adresirati <math>2^{15}</math> blokova, a u svakom bloku ima <math>2^{18}B</math>, tako da je krajnja maksimalna veličina jednaka <math>2^{15+15+18} = 2^{48} = 256TB</math>.

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

ОС1/Јун 2021

2023-08-25T19:52:59Z

Jaksa: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta je sistemski poziv, a šta sistemski program?

=== Rešenje ===
Sistemski poziv je određena funkcionalnost koju operativni sistem pruža korisničkim programima. Korisnički programi mogu pozvati sistemski poziv, često korišćenjem mehanizma softverskih prekida, kako bi od operativnog sistema zatražili neke osnovne usluge kojima najčešće iz korisničkog režima i nemaju pristup. Primer sistemskog poziva bi bio <code>fork()</code> na ''Unix-like'' sistemima.

Sistemski program je program koji obavlja osnovne operacije sa korisničkim sistemom, na primer brisanje fajlova (<code>rm</code> na ''Unix-like'' sistemima).

== 2. zadatak ==
=== Postavka ===
Šta su nedostaci organizacije memorije sa particijama?

=== Rešenje ===
* Pojavljuje se interna fragmentacija, jer ako procesu ne treba ceo svoj memorijski prostor onda je rezervisani deo prostora koji taj proces ne koristi bespotrebno bačen.
* Balansira se između veličine adresnog prostora jednog procesa i ukupnog broja procesa.
* Stepen multiprogramiranja (broj aktivnih procesa koji su u memoriji i koji se mogu uporedo izvršavati) je ograničen brojem particija.

== 3. zadatak ==
=== Postavka ===
Korisnik nekog računara radi u veb pregledaču (''web browser'') u kom je otvorio veliki broj kartica (''tab'') u kojima pregleda različite sajtove. Primetio je da mu se računar ponaša neobično, da sporo reaguje na akcije (ima veliko vreme odziva), da sporo prikazuje sadržaj stranica itd.
<div class="abc-list">
# ''Precizno'' objasniti zašto se ovo dešava.
# Korisnik je dalje primetio da kada zatvori većinu kartica i ostavi svega dve-tri, računar se ne ponaša ništa bolje. Ali kada ugasi ceo pregledač, računar se ponovo ponaša valjano. ''Precizno'' objasniti uzrok oba ova ponšaanja<sup>[sic]</sup>.
</div>

=== Rešenje ===
<div class="abc-list">
# Veb pregledači obično za svaki tab pokrenu odvojenu nit, tako da se sa više tabova češće dešava promena konteksta. Pored toga, veće je zauzeće memorije, i može da se dešava da se sve stranice u fizičkom adresnom prostoru potroše pa mora da se radi zamena stranica, što zahteva spore operacije upisa i čitanja sa spoljašnje memorije i više promašaja keša, a može doći i do batrganja.
# Moguće je da pretraživač ne oslobodi sve resurse koje je zauzeo, pa se gašenjem tabova ne oslobodi korišćena memorija. Kada se ugasi ceo proces, operativni sistem će osloboditi sve resurse koje je proces koristio pa će moći da nastavi sa normalnijim radom.
</div>

== 4. 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.

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

== 5. 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:
* A: upisuje vrednost u deljene promenljive <code>x</code> i <code>y</code>, a zatim čeka da proces B upiše zbir <code>x</code> i <code>y</code> u promenljivu <code>z</code> čiju vrednost onda ispisuje na standardni izlaz;
* B: čeka da proces A upiše vrednosti u deljene promenljive <code>x</code> i <code>y</code>, zatim ove dve vrednosti sabira i zbir upisuje u deljenu promenljivu <code>z</code>.

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

Semaphore waitA(0);
Semaphore waitB(0);

class A : public Thread {
public:
virtual void run() {
while (true) {
x = 1;
y = 2;
waitA.signal();
waitB.wait();
std::cout << z << std::endl;
}
}
};

class B : public Thread {
public:
virtual void run() {
while (true) {
waitA.wait();
z = x + y;
waitB.signal();
}
}
};

int main(void) {
A a;
B b;
a.start();
b.start();
a.join();
b.join();
return 0;
}
</syntaxhighlight>

== 6. 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 ===
Tehnikom ''spooling'' se nedeljevi uređaj može učiniti virtuelno deljivim, i klasičan primer takvog uređaja je štampač.

== 7. 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 ===
Maksimalna veličina fajla se dostiže kada svi ulazi u indeks prvog nivoa pokazuju na indekse drugog nivoa, a svi indeksi drugog nivoa pokazuju na zauzete blokove. Indeksi prvog i drugog nivoa su veličine jednog bloka, tako da se broj ulaza u indeksu dobija deljenjem veličine bloka (<math>256KB = 2^{18}B</math>) i veličine ulaza (<math>64b = 8B = 2^3B</math>): <math>\frac{2^{18}B}{2^3B} = 2^{15}</math>. To znači da je moguće adresirati <math>2^{15}</math> indeksa drugog nivoa, i iz svakog indeksa drugog nivoa adresirati <math>2^{15}</math> blokova, a u svakom bloku ima <math>2^{18}B</math>, tako da je krajnja maksimalna veličina jednaka <math>2^{15+15+18} = 2^{48} = 256TB</math>.

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

ОС1/Јун 2016

2023-08-25T18:43:40Z

Jaksa: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta se smatralo najvećim nedostatkom prvobitnih paketnih (''batch'') sistema i kako je taj nedostatak rešen?

=== Rešenje ===
Prvobitni batch sistemi su efikasno delili resurse ali nisu interaktivni. Osnovni nedostatak bio je slabo iskorišćenje glavnog resursa računara - procesora. Nedostatak je rešen uvođenjem deljenja vremena.

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

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

== 3. zadatak ==
=== Postavka ===
Za sledeće slučajeve navesti u koje stanje prelazi tekući (''running'') proces i naznačiti da li se to dešava kao posledica sistemskog poziva od strane tog tekućeg procesa ili spoljašnjeg prekida.

=== Rešenje ===
{| class="wikitable"
! Slučaj
! Tekući proces prelazi u stanje
! Uzrok (prekid ili sistemski poziv)
|-
| Istek vremenskog kvantuma kod ''time-sharing'' sistema
| ''ready''
| prekid
|-
| Operacija <code>wait</code> na semaforu koji ima vrednost 0
| ''blocked''
| sistemski poziv
|-
| Došlo vreme aktivacije prioritetnijeg periodičnog procesa
| ''ready''
| prekid
|}

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

=== Rešenje ===
<syntaxhighlight lang="pascal">
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 ===
Precizno objasniti zašto klasičan linker svoj posao obavlja u dva prolaza (a ne može samo u jednom). Obrazloženje ilustrovati primerom.

=== Rešenje ===
Videti rešenje [[ОС1/Јул 2017#5. zadatak|5. zadatka iz jula 2017. godine]].

== 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 prvog nivoa ima 2K ulaza. Svaki ulaz u PMT oba nivoa zauzima samo onoliko koliko je potrebno da se smesti broj okvira (PMT drugog nivoa je poravnata na okvir). Koliko memorije zauzimaju ukupno PMT procesa koji je alocirao svojih prvih 128 stranica?

=== Rešenje ===
* Virtuelni adresni prostor je <math>2^{33}B</math>, a adresibilna jedinica dva bajta, tako da dobijamo da je virtuelna adresa 32 bita.
* Veličina stranice je <math>32KB = 2^{15}B</math>, tako da je za stranicu u virtuelnoj adresi potrebno odvojiti 14 bita.
* Fizički adresni prostor je <math>2GB = 2^{31}B</math>, tako da je fizička adresa 30 bitova.
* PMT prvog nivoa ima <math>2K = 2^{11}</math> ulaza, tako da je to 11 bita adrese potrebno za PMT prvog nivoa.
* Iz toga dobijamo da je struktura VA: page1(11) page2(7) offset(14)
* Za 128 stranica potreban je jedan PMT prvog nivoa i jedan drugog, tako da je to ukupno <math>2^{11} * 2^2B + 2^7 * 2^2 = 8.5KB</math>

== 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 ===
Procesor će generisati izuzetak ''access violation'', jer je u desktriptoru ove stranice označeno da ona nije dozvoljena za upis zbog tek kreiranog procesa deteta.

== 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="pascal">
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], R0
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Ako fajl sistem koristi dve vrste ključeva, deljeni (''shared'') i ekskluzivni (''exclusive''), sa implicitnim zaključavanjem prilikom otvaranja fajla, koji ključ će biti zahtevan od strane procesa koji otvara fajl sa najavom samo operacije čitanja?

=== Rešenje ===
Deljeni (''shared'') ključ.

== 10. zadatak ==
=== Postavka ===
Neki sistem evidentira slobodne blokove fajl sistema tako što u jedan slobodan blok smešta spisak (indeks) do ''n'' narednih slobodnih blokova (najmanje 0, najviše ''n''), kao i broj sledećeg takvog indeksnog bloka. Koliki je broj blokova kojima sistem treba da pristupi (na čitanje ili upis) u najgorem slučaju prilikom alokacije jednog slobodnog bloka za sadržaj fajla? Broj prvog takvog bloka u lancu je globalni podatak koji se nalazi u memoriji i njegova eventualna izmena se ne broji.

=== Rešenje ===
Broj blokova kojima sistem treba da pristupi je u svakom slučaju 1. Kada se na spisku nalazi bar jedan slobodan blok, on se alocira i briše sa spiska. Kada se na spisku ne nalazi nijedan slobodan blok, blok u kome se nalazi spisak se alocira kao slobodan blok i u memoriji se menja pokazivač sa njega na sledeći blok sa spiskom.

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

ОС1/Јун 2016

2023-08-25T18:43:06Z

Jaksa: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta se smatralo najvećim nedostatkom prvobitnih paketnih (''batch'') sistema i kako je taj nedostatak rešen?

=== Rešenje ===
Prvobitni batch sistemi su efikasno delili resurse ali nisu interaktivni. Osnovni nedostatak bio je slabo iskorišćenje glavnog resursa računara - procesora. Nedostatak je rešen uvođenjem deljenja vremena.

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

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

== 3. zadatak ==
=== Postavka ===
Za sledeće slučajeve navesti u koje stanje prelazi tekući (''running'') proces i naznačiti da li se to dešava kao posledica sistemskog poziva od strane tog tekućeg procesa ili spoljašnjeg prekida.

=== Rešenje ===
{| class="wikitable"
! Slučaj
! Tekući proces prelazi u stanje
! Uzrok (prekid ili sistemski poziv)
|-
| Istek vremenskog kvantuma kod ''time-sharing'' sistema
| ''ready''
| prekid
|-
| Operacija <code>wait</code> na semaforu koji ima vrednost 0
| ''blocked''
| sistemski poziv
|-
| Došlo vreme aktivacije prioritetnijeg periodičnog procesa
| ''ready''
| prekid
|}

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

=== Rešenje ===
<syntaxhighlight lang="pascal">
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 ===
Precizno objasniti zašto klasičan linker svoj posao obavlja u dva prolaza (a ne može samo u jednom). Obrazloženje ilustrovati primerom.

=== Rešenje ===
Videti rešenje [[ОС1/Јул 2017#5. zadatak|5. zadatka iz jula 2017. godine]].

== 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 prvog nivoa ima 2K ulaza. Svaki ulaz u PMT oba nivoa zauzima samo onoliko koliko je potrebno da se smesti broj okvira (PMT drugog nivoa je poravnata na okvir). Koliko memorije zauzimaju ukupno PMT procesa koji je alocirao svojih prvih 128 stranica?

=== Rešenje ===
* Virtuelni adresni prostor je <math>2^{33}B</math>, a adresibilna jedinica dva bajta, tako da dobijamo da je virtuelna adresa 32 bita.
* Veličina stranice je <math>32KB = 2^{15}B</math>, tako da je za stranicu u virtuelnoj adresi potrebno odvojiti 14 bita.
* Fizički adresni prostor je <math>2GB = 2^{31}B</math>, tako da je fizička adresa 30 bitova.
* PMT prvog nivoa ima <math>2K = 2^{11}</math> ulaza, tako da je to 11 bita adrese potrebno za PMT prvog nivoa.
* Iz toga dobijamo da je struktura VA: page1(11) page2(7) offset(14)
* Za 128 stranica potreban je jedan PMT prvog nivoa i jedan drugog, tako da je to ukupno <math>2^(11) * 2^2B + 2^7 * 2^2 = 8.5KB</math>

== 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 ===
Procesor će generisati izuzetak ''access violation'', jer je u desktriptoru ove stranice označeno da ona nije dozvoljena za upis zbog tek kreiranog procesa deteta.

== 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="pascal">
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], R0
</syntaxhighlight>

== 9. zadatak ==
=== Postavka ===
Ako fajl sistem koristi dve vrste ključeva, deljeni (''shared'') i ekskluzivni (''exclusive''), sa implicitnim zaključavanjem prilikom otvaranja fajla, koji ključ će biti zahtevan od strane procesa koji otvara fajl sa najavom samo operacije čitanja?

=== Rešenje ===
Deljeni (''shared'') ključ.

== 10. zadatak ==
=== Postavka ===
Neki sistem evidentira slobodne blokove fajl sistema tako što u jedan slobodan blok smešta spisak (indeks) do ''n'' narednih slobodnih blokova (najmanje 0, najviše ''n''), kao i broj sledećeg takvog indeksnog bloka. Koliki je broj blokova kojima sistem treba da pristupi (na čitanje ili upis) u najgorem slučaju prilikom alokacije jednog slobodnog bloka za sadržaj fajla? Broj prvog takvog bloka u lancu je globalni podatak koji se nalazi u memoriji i njegova eventualna izmena se ne broji.

=== Rešenje ===
Broj blokova kojima sistem treba da pristupi je u svakom slučaju 1. Kada se na spisku nalazi bar jedan slobodan blok, on se alocira i briše sa spiska. Kada se na spisku ne nalazi nijedan slobodan blok, blok u kome se nalazi spisak se alocira kao slobodan blok i u memoriji se menja pokazivač sa njega na sledeći blok sa spiskom.

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

ОС1/Јун 2017

2023-08-25T17:39:50Z

Jaksa: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta je multiprogramiranje, a šta multiprocesiranje?

=== Rešenje ===
Videti zadatak iz [[ОС1/Јануар 2014#1. zadatak|januarskog roka 2014]].

== 2. zadatak ==
=== Postavka ===
Objasniti kako se obezbeđuje međusobno isključenje pristupa kritičnim sekcijama jezgra operativnog sistema od strane uporednih tokova kontrole (niti) koji se izvršavaju na istom, odnosno na različitim procesorima.

=== Rešenje ===
Videti zadatak iz [[ОС1/Фебруар 2014#2. zadatak|februarskog roka 2014]].

== 3. zadatak ==
=== Postavka ===
Korišćenjem sistemskog poziva <syntaxhighlight lang="c" inline>create_thread(void(*f)(void*),void* p)</syntaxhighlight> koji kreira nit koja izvršava datu funkciju <code>f</code> sa datim argumentom <code>p</code>, na jeziku C napisati program koji u ''n'' uporednih niti izračunava kvadrat svakog elementa nekog celobrojnog niza (<syntaxhighlight lang="c" inline>a[i]*=a[i]</syntaxhighlight>) veličine <code>n*k</code>, tako što svaka nit obrađuje ''k'' elemanata (jednu particiju niza).

=== Rešenje ===
<syntaxhighlight lang="c">
int n = ...;
int k = ...;
int a[n * k];

void square(void* p) {
int part = *(int*)(p);
free(p);
part *= k;
for (int i = 0; i < k; i++) {
a[part + i] *= a[part + i];
}
}

void main() {
for (int i = 0; i < n; i++) {
int* context = malloc(sizeof(int));
*context = i;
create_thread(square, context);
}
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
Korišćenjem standardnih brojačkih semafora u školskom jezgru, na jeziku C++ napisati implementaciju ograničenog bafera (''bounded buffer'').

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

== 5. zadatak ==
=== Postavka ===
Ako u svom C programu ni u jednom fajlu ne definišete funkciju <code>main()</code>, ko će prijaviti grešku i kog tipa, prevodilac ili linker? Precizno obrazložiti na osnovu čega se ta greška prijavljuje.

=== Rešenje ===
Linker prijavljuje grešku o nedefinisanom simbolu <code>main</code>. Kada se povezuje C/C++ program, lista obj fajlova mora da sadrži i obavezno generiše modul koji poziva funkciju <code>main</code>, pa je zato i referiše kao spoljni simbol kog uvozi, što dovodi do greške ako ga nema.

== 6. zadatak ==
=== Postavka ===
Da li se količina memorije koju program zahteva u najgorem slučaju njegovog izvršavanja smanjuje primenom tehnike dinamičkog učitavanja (u odnosu na količinu koju zahteva kada se ta tehnika ne koristi)? Kratko obrazložiti.

=== Rešenje ===
Ne smanjuje se, jer u najgorem slučaju on zahteva sve svoje potprograme i strukture, a tehnika dinamičkog učitavanja obezbeđuje da delovi ne moraju da se učitavaju samo dok se prvi put ne javi potreba za njima.

== 7. zadatak ==
=== Postavka ===
Virtuelni adresni prostor je veličine 1GB, organizovan je segmentno, sa maksimalnom veličinom segmenta od 4KB, adresibilna jedinica je bajt. Svi segmenti nekog procesa su stvarne veličine od po 2KB i u fizičku memoriju smešteni su odmah jedan iza drugog, pri čemu segment broj 0 počinje od fizičke adrese F000h. Prikazati logičku strukturu virtuelne adrese i izračunati u koju fizičku adresu se preslikava virtuelna adresa 2564h.

=== Rešenje ===
* Virtuelni adresni prostor je <math>2^{30}B</math>.
* Segment od 4KB, odnosno <math>2^{12}B</math>, znači da će deo za pomeraj zauzeti 12 bita, tako da struktura izgleda VA(30): segment(18) offset(12).
* Virtuelna adresa 2564h označava adresu sa segmentom 2 i pomerajem 564h. Ako na F000h dodamo još 2 puta veličinu fizičkog segmenta, što je 2KB, dobijamo fizičku adresu 10564h.

== 8. zadatak ==
=== Postavka ===
Objasniti kako se znakovno orijentisani sekvencijalni ulazni uređaj može učiniti (virtuelno) istim takvim, ali sa direktnim pristupom?

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

== 9. zadatak ==
=== Postavka ===
Ako je tekući direktorijum nekog procesa <code>/a/b/c</code>, koja je apsolutna staza do fajla koga ovaj proces otvara zadajući sledeću stazu: <code>../../d/e/../f.txt</code>?

=== Rešenje ===
<code>/a/d/f.txt</code>

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem koristi kombinovani indeksirani pristup alokaciji fajlova sa indeksima od jednog do tri nivoa. Objasniti zašto taj fajl sistem pokušava da alocira blokove za sadržaj fajla što bliže jedan drugome na disku, kad god je to moguće?

=== Rešenje ===
Da bi vreme pristupa blokovima bilo što kraće.

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

ОС1/Јун 2012

2023-08-21T17:54:14Z

Jaksa: /* Rešenje */

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="asm">
f: LD R0, #0 ;Registar u kome se nalazi povratna vrednost
LD R1, #n[SP]
CMP R1, R0
JG else
RTS
else: LD R2, #1
SUB R1, R2
PUSH R1
call f ;nakon zavrsetka funkcije f, u R0 se nalazi rezultat
POP R1
ADD R0, R2
RTS
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Ukoliko su svi sistemski pozivi izvršeni uspešno, koliko procesa se ukupno kreira kada se nad sledećim programom kreira jedan proces (računajući i taj jedan)?
<syntaxhighlight lang="c">
void main() {
for (int i = 0; i < 7; i++) if (fork() > 0) return;
}
</syntaxhighlight>

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

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

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

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

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

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

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

== 6. zadatak ==
=== Postavka ===
Neki sistem primenjuje kontinualnu alokaciju memorije i ''best-fit'' algoritam alokacije, pri čemu su segmenti slobodne memorije organizovani u sledeću strukturu podataka:
# sortiranu ulančanu listu,
# balansirano binarno stablo.
Koliko segmenata treba obići u najgorem slučaju da bi se pronašao odgovarajući slobodan segment prilikom alokacije, ukoliko je slobodnih segmenata ''n''?

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

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

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

Odgovor: <math>30\%</math>

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

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

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

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

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

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

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

== 10. zadatak ==
=== Postavka ===
Koliko pristupa blokovima na disku treba izvršiti za pristup ''n''-tom logičkom bloku sadržaja fajla ako je alokacija fajla:
# ulančana lista blokova, pri čemu na prvi blok sadržaja fajla ukazuje polje u FCB,
# indeksna, pri čemu je indeks fajla uvek u dva nivoa, a na blok sa indeksom prvog nivoa ukazuje polje u FCB? FCB fajla je u memoriji

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

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