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

Рачунарски VLSI системи/Питања

2025-08-26T07:47:25Z

K0v4c: /* 4. задатак [фебруар 2024 - група 2] */

{{tocright}}
'''Питања''' на теоријском делу испита се, слично као на [[Рачунарске мреже 1/Питања|РМ1]], дохватају из корпуса питања и нису свим студентима иста, али долазе из сличних области. Испод су излистани неки задаци по категоријама питања.

== SystemVerilog ограничења ==
У оваквим задацима, једноставно, је дат SystemVerilog код са ограничењима на неке променљиве, и пита се нешто у вези са вредностима које та променљива може да има и њиховим вероватноћама појављивања.

=== 1. задатак ===
Које вредности може имати променљива <code>variable</code> из приказане класе <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
rand bit [3:0] variable;

constraint c1 { variable <= 4'd9; }
constraint c2 { variable inside {[4:14]}; }
constraint c3 { ! (variable inside {4'h0, 4'h5}); }
endclass
</syntaxhighlight>
Могуће вредности, сортиране од најмање ка највећој, у децималном бројном систему, раздвојене запетом без пратећег размака, навести као одговор.

Напомена: Приказ очекиваног формата одговора за следеће произвољно одабране вредности 15, 2, 7 и 10 јесте:
2,7,10,15
'''Одговор:''' <span class="spoiler" data-solution="text">4,6,7,8,9</span>

=== 2. задатак ===
Дата је класа <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
rand bit [2:0] variable;

constraint distribution { variable dist { 0:/20, 1:/30, [2:6]:/40, 7:/10 }; }
endclass
</syntaxhighlight>
Која је вероватноћа да променљива <code>variable</code> приликом генерисања псеудослучајне вредности добије вредност '''4'''? Вероватноћу представити као разломак у којем су бројилац и именилац узајамно прости бројеви.
<div data-solution="select" data-options="9,10,5,3,11,27,4,12,2,26,28,1,25,29,13">
* Бројилац: <span class="spoiler">2</span>
* Именилац: <span class="spoiler">25</span>
</div>

=== 3. задатак ===
Које вредности може имати променљива <code>v2</code> из приказане класе <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
randc bit [3:0] v1;
randc bit [3:0] v2;

constraint c1 { v1 > 4'b0100; }
constraint c2 { ! (v1 inside {[4'h8:4'hF]}); }
constraint c3 { v2 == v1 * 2 + 1; }
endclass
</syntaxhighlight>
Могуће вредности, сортиране од најмање ка највећој, у децималном бројном систему, раздвојене запетом без пратећег размака, навести као одговор.

Напомена: Приказ очекиваног формата одговора за следеће произвољно одабране вредности 15, 2, 7 и 10 јесте:
2,7,10,15
'''Одговор:''' <span class="spoiler" data-solution="text">11,13,15</span>

=== 4. задатак ===
Дата је класа <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
rand bit [2:0] variable;

constraint distribution { variable dist { 0:/20, 1:/30, [2:6]:/20, 7:/30 }; }
endclass
</syntaxhighlight>
Која је вероватноћа да променљива <code>variable</code> приликом генерисања псеудослучајне вредности добије вредност '''4'''? Вероватноћу представити као разломак у којем су бројилац и именилац узајамно прости бројеви.
<div data-solution="select" data-options="9,10,5,3,11,27,4,12,2,26,28,1,25,29,13">
* Бројилац: <span class="spoiler">1</span>
* Именилац: <span class="spoiler">25</span>
</div>

=== 5. задатак ===
Дата је класа <code>Constraints</code>:
<syntaxhighlight lang="systemverilog">
class Constraints;
rand bit [2:0] variable;

constraint distribution { variable dist { 0:/20, 1:/30, [2:6]:=20, 7:/30 }; }
endclass
</syntaxhighlight>
Која је вероватноћа да променљива <code>variable</code> приликом генерисања псеудослучајне вредности добије вредност '''4'''? Вероватноћу представити као разломак у којем су бројилац и именилац узајамно прости бројеви.
<div data-solution="select" data-options="9,10,5,3,11,27,4,12,2,26,28,1,25,29,13">
* Бројилац: <span class="spoiler">1</span>
* Именилац: <span class="spoiler">9</span>
</div>

Objašnjenje: <span class="spoiler" data-solution="explanation">Kada stoji := to znači da se svakom broju iz opsega dodeljuje ta verovatnoća, za razliku od :/ koji označava kumulativnu verovatnoću za ceo opseg. Samim tim ukupna verovatnoća je <math>20+30+20*5+30 = 180</math>, verovatnoća za broj 4 je 20, tako da će rezultat biti <math>\frac{20}{180}</math> čijim skraćivanjem se dobija traženo rešenje.</span>

== Сабирачи ==
У оваквим задацима обично је дат Verilog код одређеног сабирача (једног од типова као што су рађени на предавањима) и питају се ствари у вези са функционисањем тог сабирача.

=== 1. задатак ===
У наставку је дата имплементација једног осморазредног сабирача. О ком сабирачу се ради, ако се зна да модул <code>ripple_carry_adder_n</code> представља ''N''-разредни сабирач са серијским преносом, а да модул <code>multiplexer_2_1</code> представља двоулазни мултиплексер ширине ''N'' информационих улаза?
<syntaxhighlight lang="verilog">
module adder_8 (
input [7:0] a, b,
input carry_in,
output [7:0] sum,
output carry_out
);

wire carry_3_0, carry_3_1, carry_3;
wire [3:0] sum_low_0, sum_low_1, sum_low;

ripple_carry_adder_n #(4) rca_1 (a[3:0], b[3:0], 1'b0, sum_low_0, carry_3_0);
ripple_carry_adder_n #(4) rca_2 (a[3:0], b[3:0], 1'b1, sum_low_1, carry_3_1);

multiplexer_2_1 #(4) mpx_1 (sum_low_0, sum_low_1, carry_in, sum_low);

assign carry_3 = (carry_in & carry_3_1) | carry_3_0;

wire carry_7_0, carry_7_1, carry_7;
wire [3:0] sum_high_0, sum_high_1, sum_high;

ripple_carry_adder_n #(4) rca_3 (a[7:4], b[7:4], 1'b0, sum_high_0, carry_7_0);
ripple_carry_adder_n #(4) rca_4 (a[7:4], b[7:4], 1'b1, sum_high_1, carry_7_1);

multiplexer_2_1 #(4) mpx_2 (sum_high_0, sum_high_1, carry_3, sum_high);

assign carry_7 = carry_7_0 | (carry_3_0 & carry_7_1) | (carry_in & carry_3_1 & carry_7_1);

assign sum = {sum_high, sum_low};
assign carry_out = carry_7;

endmodule
</syntaxhighlight>
<div class="abc-list" data-solution="single">
# Условни сабирач (''Conditional Sum Adder'')
# Сабирач са серијским преносом (''Ripple Carry Adder'')
# Сабирач са чувањем преноса (''Carry Save Adder'')
# <span class="solution">Сабирач на основу бита преноса (''Carry Select Adder'')</span>
# Сабирач са паралелним преносом (''Carry Lookahead Adder'')
# Потпуни сабирач (''Full Adder'')
</div>
'''Објашњење:''' <span class="spoiler" data-solution="explanation">У коду се види карактеристични "осакаћени мултиплексер" код генерисања преноса <code>carry_3</code> и <code>carry_7</code>.</span>

=== 2. задатак ===
У наставку је дата непотпуна имплементација четвороразредног сабирача на основу бита преноса (''Carry Select Adder''). Допунити имплементацију, ако се зна да модул <code>ripple_carry_adder_n</code> представља ''N''-разредни сабирач са серијским преносом, а да модул <code>multiplexer_2_1</code> представља двоулазни мултиплексер ширине ''N'' информационих улаза?<sup>[sic]</sup>
<syntaxhighlight lang="verilog">
module carry_select_adder_4 (
input [3:0] a, b,
input carry_in,
output [3:0] sum,
output carry_out
);

wire carry_3_0, carry_3_1;
wire [3:0] sum_0, sum_1;

ripple_carry_adder_n #(4) rca_1 (a[3:0], b[3:0], БЕЛИНА_1, sum_0, БЕЛИНА_2);
ripple_carry_adder_n #(4) rca_2 (a[3:0], b[3:0], БЕЛИНА_3, sum_1, БЕЛИНА_4);

multiplexer_2_1 #(4) mpx_1 (sum_0, sum_1, carry_in, sum);

assign carry_out = (carry_in & carry_3_1) | carry_3_0;

endmodule
</syntaxhighlight>
<div class="abc-list" data-solution="select" data-options="carry_3_1,1'b1,sum,1'b0,carry_out,carry_in,carry_3_0,sum_0,sum_1">
# Белина 1: <span class="spoiler">1'b0</span>
# Белина 2: <span class="spoiler">carry_3_0</span>
# Белина 3: <span class="spoiler">1'b1</span>
# Белина 4: <span class="spoiler">carry_3_1</span>
</div>
'''Објашњење:''' <span class="spoiler" data-solution="explanation">Ово је само друга варијанта задатка изнад. Једном сабирачу се даје да рачуна као да је улазни пренос 0, а другом да је улазни пренос 1, па се њихови резултати смештају у одговарајуће сигнале.</span>

== Временски облици ==
У оваквим задацима дат је Verilog код са кашњењима и временски облици излазних сигнала у ''ModelSim'', па се студенти питају да препознају одговарајући временски облик.

=== 1. задатак ===
{{делимично решено}}
Који временски облик одговара следећем изворном коду:
<syntaxhighlight lang="verilog">
module delay_module_3 (
out1, out2, a, b, c, x, y, z
);

output reg out1, out2;
input a, b, c, x, y, z;
wire e, f, g;

always @(posedge a) out1 = #1 b & c;
always @(negedge a) out1 = #1 b | ~c;

always @(posedge x) out2 = #1 y ^ z;
always @(negedge x) out2 = #1 ~y;

endmodule

module top_display;

reg a, b, c, x, y, z;
wire o1, o2;
delay_module_3 d3(o1, o2, a, b, c, x, y, z);

initial begin
a = 1'b0; b = 1'b0; c = 1'b0; x = 1'b0; y = 1'b0; z = 1'b0;
#1 b = 1'b1;
#2 a = 1'b1; y = 1'b1;
#0 c = 1'b1;
#2 x = 1'b1;
#2 a = 1'b0;
#1 b = 1'b0;
#3 x = 1'b0;
#0 y = 1'b0;
#0 $finish;
end

endmodule
</syntaxhighlight>
<div class="abc-list" data-solution="single">
# [[Датотека:VLSI zadaci vremenski oblik 9.jpg|link=]]
# [[Датотека:VLSI zadaci vremenski oblik 10.jpg|link=]]
# [[Датотека:VLSI zadaci vremenski oblik 11.jpg|link=]]
# [[Датотека:VLSI zadaci vremenski oblik 12.jpg|link=]]
# Ниједан од понуђених временских облика.
</div>

== Померачи ==
У оваквим задацима дат је Фанел или Барел померач са одређеним карактеристикама, и траже се сви његови међурезултати.

=== 1. задатак ===
Дат је Фанел померач (''Funnel Shifter'') са дванаестобитним улазом и петобитним излазом. Допунити вредности добијене у сваком од корака овог померача као и вредност излзаног податка за следеће улазне вредности:
<div data-solution="select" data-options="29,16,1A,27,7,14,5A,13,D,B,A7,9">
* Улазни податак: 5A7
* Контролни сигнал (број померања удесно): 4
* Први корак: <span class="spoiler">5A</span>
* Други корак: <span class="spoiler">1A</span>
* Трећи корак: <span class="spoiler">1A</span>
* Излазни податак: <span class="spoiler">1A</span>
</div>
Све вредности су написане у хексадецималном бројном систему.

=== 2. задатак ===
Дат је Барел померач (''Barrel Shifter'') са осмобитним улазом и осмобитним излазом. Допунити вредности добијене у сваком од корака овог померача као и вредност излзаног податка за следеће улазне вредности:
<div data-solution="select" data-options="5E,F2,97,79,CB,E5,2F">
* Улазни податак: 79
* Контролни сигнал (број померања удесно): 7
* Први корак: <span class="spoiler">97</span>
* Други корак: <span class="spoiler">E5</span>
* Трећи корак: <span class="spoiler">F2</span>
* Излазни податак: <span class="spoiler">F2</span>
</div>
Све вредности су написане у хексадецималном бројном систему.

=== 3. задатак [фебруар 2024 - група 1]===
Дат је Фанел померач (''Funnel Shifter'') са дванаестобитним улазом и петобитним излазом. Допунити вредности добијене у сваком од корака овог померача као и вредност излзаног податка за следеће улазне вредности:
<div data-solution="select" data-options="26,16,1A,18,7,14,13,6D,B,A7,9">
* Улазни податак: 26D
* Контролни сигнал (број померања удесно): 5
* Први корак: <span class="spoiler">26</span>
* Други корак: <span class="spoiler">26</span>
* Трећи корак: <span class="spoiler">13</span>
* Излазни податак: <span class="spoiler">13</span>
</div>
Све вредности су написане у хексадецималном бројном систему.

=== 4. задатак [фебруар 2024 - група 2]===
Дат је Фанел померач (''Funnel Shifter'') са дванаестобитним улазом и петобитним излазом. Допунити вредности добијене у сваком од корака овог померача као и вредност излзаног податка за следеће улазне вредности:
<div data-solution="select" data-options="23,16,13,17,7,14,13,3F,B,F8,9">
* Улазни податак: 3F8
* Контролни сигнал (број померања удесно): 7
* Први корак: <span class="spoiler">3F</span>
* Други корак: <span class="spoiler">F</span>
* Трећи корак: <span class="spoiler">7</span>
* Излазни податак: <span class="spoiler">7</span>
</div>
Све вредности су написане у хексадецималном бројном систему.

== Верификација без UVM ==
У оваквим задацима дат је код из примера верификације без коришћења UVM стандарда са вежби и пита се шта се тачно дешава у коду и зашто.

=== 1. задатак ===
У наставку је дат део кода ''Driver''-a.
<syntaxhighlight lang="systemverilog">
class Driver;

virtual reg8_if vif;
mailbox mbx;
event done;

task run();
@(posedge vif.clk);
forever begin
dut_item item;
mbx.get(item);
// ...
@(posedge vif.clk);
->done;
end
endtask

endclass
</syntaxhighlight>
Koja класа чека на догађај <code>done</code> који се овде окида?

Напомена: Сматрати да се процес верификације врши без коришћења UVM стандарда.
<div class="abc-list" data-solution="single">
# ''Driver''
# <span class="solution">''Generator''</span>
# ''Monitor''
# ''Scoreboard''
</div>
'''Објашњење:''' <span class="spoiler" data-solution="explanation">Први пример са вежби. Генератор чека на овај догађај како не би генерисао више предмета него што драјвер може да конзумира.</span>

=== 2. задатак ===
У наставку је дат део кода ''Driver''-a.
<syntaxhighlight lang="systemverilog">
class Driver;

virtual reg8_if vif;
mailbox mbx;
event done;

task run();
@(posedge vif.clk);
forever begin
dut_item item;
mbx.get(item);
// ...
@(posedge vif.clk);
->done;
end
endtask

endclass
</syntaxhighlight>
Koja класа поставља <code>item</code> у ''mailbox'' који се овде дохвата?

Напомена: Сматрати да се процес верификације врши без коришћења UVM стандарда.
<div class="abc-list" data-solution="single">
# ''Driver''
# <span class="solution">''Generator''</span>
# ''Monitor''
# ''Scoreboard''
</div>

== UVM ==
Ова питања се обично односе на било шта из UVM стандарда.

=== 1. задатак ===
Које класе наслеђују класу <code>uvm_transaction</code>?
<div class="abc-list" data-solution="multiple">
# <span class="solution"><code>uvm_sequence_item</code></span>
# <code>uvm_driver</code>
# <code>uvm_monitor</code>
# <code>uvm_sequencer</code>
# <code>uvm_test</code>
# <span class="solution"><code>uvm_sequence</code></span>
</div>

=== 2. задатак ===
Које фазе кроз које пролазе UVM компоненте се реализују као ''task'' уместо као функције?
<div class="abc-list" data-solution="multiple">
# build
# connect
# end of elaboration
# start of simulation
# <span class="solution">run</span>
# extract
# check
# report
</div>

[[Категорија:Рачунарски VLSI системи]]
[[Категорија:Рокови]]

Програмски преводиоци 1/Јануар 2023

2025-08-16T18:39:07Z

K0v4c: /* Promena const_0 na const_2 -> Pocetak VT je u statickoj memoriji na adresi 2 jer postoje 2 globalne promenjive.*/

{{tocright}}
{{nerešeno}}
'''Januarski ispit 2023. godine''' održan je 19. januara. Postavka roka nije dostupna sa stranice predmeta.

== 1. zadatak ==
=== Postavka ===
Dat je sledeći program:
<syntaxhighlight lang="cpp">
int main() {
int count;
void procX() {
void report() {
writeln("count = " + count);
}
void proxY() {
int count;
count = 200;
report();
}
count = 100;
report();
procY();
}
count = 300;
procX();
}
</syntaxhighlight>
<div class="abc-list">
# Ukoliko se koristi statičko razrešavanje dosega, šta će ispisati dati program?
# Ukoliko se koristi dinamičko razrešavanje dosega, šta će ispisati dati program?
# Ukoliko se za nelokalne promenljive koriste displeji, nacrtati poslednje stanje steka i displeja nakon što je <code>report</code> funkcija pozvana poslednji put.
</div>

=== Rešenje ===

== 2. zadatak ==
=== Postavka ===
Dat je isečak koda klase <code>Struct</code>. Dopuniti metodu <code>AssignableTo</code> kodom koji fali.
<syntaxhighlight lang="java">
public class Struct {
private int kind;
private Struct elemType;
public boolean Equals(Struct other) {
return (this == other) || (kind == Kinds.Array && other.kind == Kinds.Array && elemType.Equals(other.ElemType));
}
public boolean IsRefType() {
return kind == Kinds.Class || kind == Kinds.Array;
}
public boolean AssignableTo(Struct dest) {
if (this.Equals(dest) ||
|| (kind == Kinds.Array && dest.kind == Kinds.Array && dest.elemType == Tab.noType)) {
return true;
}
return false;
}
}
</syntaxhighlight>

=== Rešenje ===
Preuzeto iz [http://ir4pp1.etf.rs/Predavanja/pp1_udzbenik.pdf udžbenika Programski prevodioci 1] (Dragan Bojić, Maja Vukasović) sa strane 209.
<syntaxhighlight lang="java">
class Struct {
...
// checks, if this can be assigned to dest (explicit. assignment, parameters)
public bool AssignableTo (Struct dest) {
if ( this.Equals(dest) || this == Tab.nullType && dest.IsRefType() ||
kind == Kinds.Arr && dest.kind == Kinds.Arr && // for len()
dest.elemType == Tab.noType) return true;
for (Struct s = elemType; s != null; s = s.elemType) {
if (s.equals(dest)) return true;
}
return false;
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Za dati blok koda napisati međukod a zatim nacrtati graf toka kontrole sa međukodom u SSA formi.
<syntaxhighlight lang="cpp">
int res = 10;
for (int i = 0; i < 10; i++) {
int n = res;
for (int j = i + 1; j < n; j++) {
if ((i + j) % 2 == 0) {
res++;
}
}
}
</syntaxhighlight>

=== Rešenje ===

== 4. zadatak ==
=== Postavka ===
Za datu gramatiku konstruisati karakteristički LR(0) automat i kontrolnu tabelu, a zatim dodati LALR(1) predikcione skupove.
# <S> → <S> <A>
# <A> → <A> a <A> b
# <A> → <S> a
# <A> → c

=== Rešenje ===

== 5. zadatak ==
=== Postavka ===
U datoj gramatici neterminalu <code><list></code> dodati sintetizovani atribut koji naizmenično sadrži cifre najvećih i najmanjih brojeva iz niza. Na primer, ukoliko je sekvenca koja se prepoznaje [1, 2, 3] [4, 5, 6] [7, 8, 9], taj atribut bi imao vrednost 349. Smatrati da terminal <code>INT</code> ima sintetizovani simbol sa svojom vrednošću.
# <list> → <list> <item>
# <list> → <item>
# <item> → [ <num_arr> ]
# <num_arr> → <num_arr>, INT
# <num_arr> → INT

=== Rešenje ===
Uvodimo sledeće sintetizovane atribute:
* INT<sub>digit</sub> - digit predstavlja cifru opisanu terminalom INT
* <num_arr><sub>minDigit, maxDigit</sub> - minDigit predstavlja minimalnu cifru sadržanu u nizu cifara <num_arr>, a maxDigit maksimalnu cifru sadržanu u nizu cifara <num_arr>
* <item><sub>minDigit, maxDigit</sub> - minDigit predstavlja minimalnu cifru sadržanu u nizu cifara koji se nalazi u neterminalu <item>, a maxDigit maksimalnu cifru sadržanu u nizu cifara koji se nalazi u neterminalu <item>
* <list><sub>value, takeMinDigit</sub> - value predstavlja vrednost koju treba izračunati po postavci zadatka, a takeMinDigit da li u sledećem koraku treba uzeti minimalnu ili maksimalnu cifru (ovo posmatramo kao neki flag kome u svakom koraku invertujemo vrednost, a čija je početna vrednost 1 jer u prvom koraku uzimamo maksimalnu, a u drugom minimalnu cifru)

Atributivno translaciona gramatika izgleda ovako (stvari koje su dodate u odnosu na gramatiku iz postavke su prikazane '''podebljanim slovima'''):

# <list><sub>'''value, takeMinDigit'''</sub> -> <list><sub>'''valueRHS, takeMinDigitRHS'''</sub> <item><sub>'''minDigit, maxDigit'''</sub> '''{ value = valueRHS * 10 + (takeMinDigitRHS == 1) ? minDigit : maxDigit; takeMinDigit = 1 - takeMinDigitRHS; }'''
# <list><sub>'''value, takeMinDigit'''</sub> -> <item><sub>'''minDigit, maxDigit'''</sub> '''{ value = maxDigit; takeMinDigit = 1; }'''
# <item><sub>'''minDigit, maxDigit'''</sub> -> [ <num_arr><sub>'''minDigitRHS, maxDigitRHS'''</sub> ] '''{ minDigit = minDigitRHS; maxDigit = maxDigitRHS; }'''
# <num_arr><sub>'''minDigit, maxDigit'''</sub> -> <num_arr><sub>'''minDigitRHS, maxDigitRHS'''</sub> , INT<sub>'''digit'''</sub> '''{ minDigit = min(minDigitRHS, digit); maxDigit = max(maxDigitRHS, digit); }'''
# <num_arr><sub>'''minDigit, maxDigit'''</sub> -> INT<sub>'''digit'''</sub> '''{ minDigit = digit; maxDigit = digit; }'''

== 6. zadatak ==
=== Postavka ===
Napisati kompletan prevod funkcija <code>f1</code>, <code>f2</code> i <code>main</code> na Mikrojava bajtkod. Smatrati da prevod <code>f1</code> kreće od adrese 0. Sekciju označenu sa <code>// ...</code> nije potrebno prevoditi i smatrati da je njena dužina jedna instrukcija.
<syntaxhighlight lang="cpp">
int b;
class A {
int fun1(int p) {...}
}
class B {
A[] arr;
}
B bObj;
int f1() {
return 1;
}
int f2() {
return 2;
}
void main() int x; {
bObj = new B;
// ...
b = bObj.arr[1].fun1(3);
if (b < x) {
b = f1();
}
else b = f2();
}
</syntaxhighlight>

=== Rešenje ===
<syntaxhighlight lang="asm">
00: enter 0 0
03: const_1
04: exit
05: return
06: enter 0 0
09: const_2
10: exit
11: return
12: enter 0 1
15: new 4
18: dup
19: const_2
20: putfield 0
23: putstatic 1
26: ...
27: getstatic 1
30: getfield 1
33: const_1
34: aload
35: const_3
36: getstatic 1
39: getfield 1
42: const_1
43: aload
44: getfield 0
47: invokevirtual 'f' 'u' 'n' '1' -1
68: putstatic 0
71: getstatic 0
74: load_0
75: jge 12
78: call -78
81: putstatic 0
84: jmp 9
87: call -81
90: putstatic 0
93: exit
94: return
95: ...
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]

КДП/Лаб 2 РТИ 2023

2023-12-28T18:07:56Z

K0v4c: Dodata stranica za lab2 rti 2023 kdp

{{tocright}}

== Поставка ==

У зависности од групе било је потребно решити један од следеће два проблема.

1. Решити DiningPhilosopher проблем користећи <code>ExecutorService</code> и где је потребно да сервер враћа филозоферу информацију када му је дозвољено да једе. Користити <code>System.currentTimeMillis()</code> за дохватање времена и дозвоњено је користити <code>Future</code> и друге синхронизационе примитиве за решавање задатка.

2. TODO.

== Решење ==

Испод је дато решење за DiningPhilosophers.

Изглед хијерархије фајлова:
.
├── client
│ └── Philosopher.java
├── common
│ └── Service.java
└── server
├── RequestHandler.java
└── Server.java

==== <code>Philosopher.java</code> ====
<syntaxhighlight lang="java">
package client;

import common.Service;

public class Philosopher extends Thread{

public static final int NUM_OF_PHILOSOPHERS = 30;
public static int curr_id = 0;
public int id = 0;
public Service service;

public Philosopher(Service service) {
this.id = curr_id++;

this.service = service;
}

@Override
public void run() {

while(true) {
// think
try {
Thread.sleep((long) (Math.random() * 1000));
} catch (InterruptedException e) {
throw new RuntimeException(e);
}

this.service.eat(this.id);
}

}

public static void main(String[] args) {

Philosopher[] arr = new Philosopher[NUM_OF_PHILOSOPHERS];

Service service = new Service("localhost", 4001);

for(int i = 0; i < NUM_OF_PHILOSOPHERS; i++) {
arr[i] = new Philosopher(service);
}

for(int i = 0; i < NUM_OF_PHILOSOPHERS; i++) {
arr[i].start();
}

}
}
</syntaxhighlight>

==== <code>Service.java</code> ====
<syntaxhighlight lang="java">
package common;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.net.Socket;

public class Service {

String host;
int port;

public Service(String host, int port) {
this.host = host;
this.port = port;
}

public void eat(int id) {

try (
Socket socket = new Socket(this.host, this.port);
BufferedReader buffered_reader = new BufferedReader(new InputStreamReader(socket.getInputStream()));
PrintWriter print_writer = new PrintWriter(new OutputStreamWriter(socket.getOutputStream()), true);
) {

print_writer.println("eat"+"#"+id);

// Get the resource
String time = buffered_reader.readLine();
System.out.println("Filozofer sa id: " + id + " je dobio pristup u trenutku: " + time);

} catch (Exception e) {
e.printStackTrace();
}

}
}
</syntaxhighlight>

==== <code>RequestHandler.java</code> ====
<syntaxhighlight lang="java">
package server;

import java.io.*;
import java.net.Socket;
import java.util.Scanner;

public class RequestHandler extends Thread {

Socket sock;
Server server;

public RequestHandler(Socket sock, Server server) {
this.sock = sock;
this.server = server;
}

@Override
public void run() {

try (
Socket socket = this.sock;
BufferedReader buffered_reader = new BufferedReader(new InputStreamReader(socket.getInputStream()));
PrintWriter print_writer = new PrintWriter(new OutputStreamWriter(socket.getOutputStream()), true);
) {

String in = buffered_reader.readLine();

String[] data = in.split("#");

String operation = data[0];
int id = Integer.parseInt(data[1]);

if ("eat".equalsIgnoreCase(operation)) {
server.test(id);
server.eat(buffered_reader, print_writer);
server.signal(id);
}

} catch (Exception e) {
e.printStackTrace();
}

}
}
</syntaxhighlight>

==== <code>Server.java</code> ====
<syntaxhighlight lang="java">
package server;

import java.io.BufferedReader;
import java.io.PrintWriter;
import java.net.ServerSocket;
import java.net.Socket;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Server {

ExecutorService pool;
final static int MAX_THREADS = 10;

public static final int NUM_OF_PHILOSOPHERS = 30;
int []forks;
int port;

public Server(int port) {
this.forks = new int[NUM_OF_PHILOSOPHERS];

for(int i = 0; i < NUM_OF_PHILOSOPHERS; i++) {
forks[i] = 2;
}

pool = Executors.newFixedThreadPool(MAX_THREADS);

this.port = port;
}

public synchronized void test(int id) {
int left = (id - 1 + NUM_OF_PHILOSOPHERS) % NUM_OF_PHILOSOPHERS;
int right = (id + 1 + NUM_OF_PHILOSOPHERS) % NUM_OF_PHILOSOPHERS;

while(forks[id] != 2) {
try {
wait();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}

forks[left]--;
forks[right]--;

}

public void eat(BufferedReader rd, PrintWriter pw) {
pw.println(System.currentTimeMillis());
}

public synchronized void signal(int id){
int left = (id - 1 + NUM_OF_PHILOSOPHERS) % NUM_OF_PHILOSOPHERS;
int right = (id + 1 + NUM_OF_PHILOSOPHERS) % NUM_OF_PHILOSOPHERS;
forks[left]++;
forks[right]++;

notifyAll();
}

public static void main(String[] args) {

Server server = new Server(4001);

try (
ServerSocket listener = new ServerSocket(server.port)
) {
while(true) {
Socket sock = listener.accept();

// new RequestHandler(sock, server).start();

server.pool.execute(new RequestHandler(sock, server));
}
} catch (Exception e) {
e.printStackTrace();
}

}
}

</syntaxhighlight>

[[Категорија:КДП]]
[[Категорија:Лабораторијске вежбе]]

КДП/Лаб 1 РТИ 2023

2023-12-27T18:56:41Z

K0v4c: Dodata nova stranica

{{tocright}}
== Поставка ==

У зависности од групе било је потребно решити један од следећих проблема:

1. Решити Унисеx Батхроом проблем користећи <code>ReentrantLock</code>. Потребно је да програм буде максимално конкурентан.

2. Решити Атомиц Броадцаст проблем користећи <code>AtomicInteger</code>. Потребно је да програм буде максимално конкурентан.

== Решење ==

Испод је решење за Unisex Bathroom.

==== <code>Test.java</code> ====

<syntaxhighlight lang="java">

package UnisexBathLocksLab1PrvaGrupa;

public class Test {

public static void main(String[] args) {

int m = 5;
int w = 5;

int N = 4;

Bathroom b = new Bathroom(N);

Thread mt[] = new Thread[m];
Thread wt[] = new Thread[m];

for(int i = 0; i < m; i++) {
mt[i] = new Man(b);
mt[i].start();
}

for(int i = 0; i < w; i++) {
wt[i] = new Woman(b);
wt[i].start();
}

}

}

</syntaxhighlight>

==== <code>Woman.java</code> ====

<syntaxhighlight lang="java">

package UnisexBathLocksLab1PrvaGrupa;

public class Woman extends Thread{

public int id;
public static int running_id = 0;

Bathroom bath;

public Woman(Bathroom bath) {
id = running_id++;
this.bath = bath;

}

@Override
public void run() {
while(true) {

bath.w_enter(id);

try {
Thread.sleep((int)(Math.random() * 1000));
} catch (InterruptedException e) {
e.printStackTrace();
}

bath.w_exit(id);

}
}

}

</syntaxhighlight>

==== <code>Man.java</code> ====

<syntaxhighlight lang="java">

package UnisexBathLocksLab1PrvaGrupa;

public class Man extends Thread{

public int id;
public static int running_id = 0;

Bathroom bath;

public Man(Bathroom bath) {
id = running_id++;
this.bath = bath;

}

@Override
public void run() {
while(true) {

bath.m_enter(id);

try {
Thread.sleep((int)(Math.random() * 1000));
} catch (InterruptedException e) {
e.printStackTrace();
}

bath.m_exit(id);

}
}

}

</syntaxhighlight>

==== <code>Bathroom.java</code> ====

<syntaxhighlight lang="java">

package UnisexBathLocksLab1PrvaGrupa;

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Bathroom {

private int woman_cnt = 0;
private int man_cnt = 0;

private int capacity = 0;

Lock lock = new ReentrantLock();
Condition all = lock.newCondition();

private int ticket = 0;
private int next = 0;

public Bathroom(int N) {
this.ticket = 0;
this.next = 0;
this.man_cnt = 0;
this.woman_cnt = 0;
this.capacity = N;
}

public void m_enter(int id) {
lock.lock();

try {
int my_ticket = ticket++;

System.out.println("Man(" + id + ") waiting");
while (my_ticket != next || woman_cnt > 0 || man_cnt >= capacity) {
all.awaitUninterruptibly();
}

System.out.println("Man(" + id + ") entered");

man_cnt += 1;
this.next += 1;

} finally {
lock.unlock();
}

}

public void m_exit(int id) {

lock.lock();

try {
System.out.println("Man(" + id + ") left");
man_cnt -= 1;
all.signalAll();
} finally {
lock.unlock();
}

}

public void w_enter(int id) {
lock.lock();

try {
int my_ticket = ticket++;

System.out.println("Woman(" + id + ") waiting");
while (my_ticket != next || man_cnt > 0 || woman_cnt >= capacity) {
all.awaitUninterruptibly();
}

System.out.println("Woman(" + id + ") entered");

woman_cnt += 1;
next += 1;

} finally {
lock.unlock();
}

}

public void w_exit(int id) {

lock.lock();

try {
System.out.println("Woman(" + id + ") left");
woman_cnt -= 1;
all.signalAll();
} finally {
lock.unlock();
}
}

}

</syntaxhighlight>

ОС1/Модификације август 2023

2023-09-06T21:28:01Z

K0v4c: jos uvek ne umem da kucam

{{tocright}}
Sledeće modifikacije su se pojavile na odbrani projekta u avgustu 2023.

== Modifikacija za 20 bodova ==

Potrebno je proširiti usluge klase Thread tako da zadovoljava sledeće uslove

Dodati statičku metodu <code>SetMaximumThreads(int num_of_threads)</code> koju korisnik poziva na početku programa. Ova metoda postavlja ograničenje na maksimalan broj '''korisničkih''' niti.

Nakon postavljanja maksimalnog broja niti, moguce je kreirati dati broj niti, nakon toga sve novokreirane niti se blokiraju. Kada jedna od kreiranih korisničkih niti završi svoje izvršavanje ona odblokira jednu od prethodno blokiranih niti u redosledu kojem su blokirane.

=== Test ===
Potrebno je staviti maksimalan broj niti na 3 i kreirati 20 niti. Svaka nit treba da ispiše svoje ime + ID niti ciklično 5 puta. Nakog toga treba da simulira spavanje semaforom ili busy wait-om koji je u linearnoj korelaciji sa ID-om date niti.

== Modifikacija za 30 bodova ==

Dodati statičku metodu <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> koju korisnik poziva na početku programa. Ova metoda postavlja ograničenje na maksimalan broj '''korisničkih''' niti.

Nakon pozivanja metode <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> moguće je kreirati slobodno kreirati num_of_threads niti. Nakon toga naredne niti se blokiraju. Kada nit završi svoje izvršavanje ona prestaje sa radom (ove niti '''ne treba''' da deblokiraju prethodno blokirane niti). Nakon isteka max_time vremena potrebno je ispisati '''Waiting done: ''', i zatim odblokirati niti jednu za drugom onako kako suu blokirane pritom da se izmedju 2 deblokiranja čeka interval_time vremena. Posle svakog deblokiranja niti treba ispisati '''Interval time elapsed '''.

=== Test ===

Potrebno je pozvati <code>SetMaximumThreads(3, 20, 10)</code> i kreirati 20 niti. Svaka nit treba da ispiše svoje ime + ID. Nakon toga treba nit da pozove <code>thread_sleep(10)</code>. Ovo se ponavlja dok sve niti ne završe.

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

ОС1/Модификације август 2023

2023-09-06T21:25:13Z

K0v4c: /* Test */

{{tocright}}
Sledeće modifikacije su se pojavile na odbrani projekta u avgustu 2023.

== Modifikacija za 20 bodova ==

Potrebno je proširiti usluge klase Thread tako da zadovoljava sledeće uslove

Dodati statičku metodu <code>SetMaximumThreads(int num_of_threads)</code> koju korisnik poziva na početku programa. Ova metoda postavlja ograničenje na maksimalan broj '''korisničkih''' niti.

Nakon postavljanja maksimalnog broja niti, moguce je kreirati dati broj niti, nakon toga sve novokreirane niti se blokiraju. Kada jedna od kreiranih korisničkih niti završi svoje izvršavanje ona odblokira jednu od prethodno blokiranih niti u redosledu kojem su blokirane.

=== Test ===
Potrebno je staviti maksimalan broj niti na 3 i kreirati 20 niti. Svaka nit treba da ispiše svoje ime + ID niti ciklično 5 puta. Nakog toga treba da simulira spavanje semaforom ili busy wait-om koji je u linearnoj korelacijai sa ID-om date niti.

== Modifikacija za 30 bodova ==

Dodati statičku metodu <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> koju korisnik poziva na početku programa. Ova metoda postavlja ograničenje na maksimalan broj '''korisničkih''' niti.

Nakon pozivanja metode <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> moguće je kreirati slobodno kreirati num_of_threads niti. Nakon toga naredne niti se blokiraju. Kada nit završi svoje izvršavanje ona prestaje sa radom (ove niti '''ne treba''' da deblokiraju prethodno blokirane niti). Nakon isteka max_time vremena potrebno je ispisati '''Waiting done: ''', i zatim odblokirati niti jednu za drugom onako kako suu blokirane pritom da se izmedju 2 deblokiranja čeka interval_time vremena. Posle svakog deblokiranja niti treba ispisati '''Interval time elapsed '''.

=== Test ===

Potrebno je pozvati <code>SetMaximumThreads(3 20, 10)</code> i kreirati 20 niti. Svaka nit treba da ispiše svoje ime + ID. Nakon toga treba nit da pozove <code>thread_sleep(10)</code>. Ovo se ponavlja dok sve niti ne završe.

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

ОС1/Модификације август 2023

2023-09-06T21:24:35Z

K0v4c: ne umem da kucam

{{tocright}}
Sledeće modifikacije su se pojavile na odbrani projekta u avgustu 2023.

== Modifikacija za 20 bodova ==

Potrebno je proširiti usluge klase Thread tako da zadovoljava sledeće uslove

Dodati statičku metodu <code>SetMaximumThreads(int num_of_threads)</code> koju korisnik poziva na početku programa. Ova metoda postavlja ograničenje na maksimalan broj '''korisničkih''' niti.

Nakon postavljanja maksimalnog broja niti, moguce je kreirati dati broj niti, nakon toga sve novokreirane niti se blokiraju. Kada jedna od kreiranih korisničkih niti završi svoje izvršavanje ona odblokira jednu od prethodno blokiranih niti u redosledu kojem su blokirane.

=== Test ===
Potrebno je staviti maksimalan broj niti na 3 i kreirati 20 niti. Svaka nit treba da ispiše svoje ime + ID niti ciklično 5 puta. Nakog toga treba da simulira spavanje semaforom ili busy wait-om koji je u linearnoj korelacijai sa ID-om date niti.

== Modifikacija za 30 bodova ==

Dodati statičku metodu <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> koju korisnik poziva na početku programa. Ova metoda postavlja ograničenje na maksimalan broj '''korisničkih''' niti.

Nakon pozivanja metode <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> moguće je kreirati slobodno kreirati num_of_threads niti. Nakon toga naredne niti se blokiraju. Kada nit završi svoje izvršavanje ona prestaje sa radom (ove niti '''ne treba''' da deblokiraju prethodno blokirane niti). Nakon isteka max_time vremena potrebno je ispisati '''Waiting done: ''', i zatim odblokirati niti jednu za drugom onako kako suu blokirane pritom da se izmedju 2 deblokiranja čeka interval_time vremena. Posle svakog deblokiranja niti treba ispisati '''Interval time elapsed '''.

=== Test ===

Potrebno je pozvati <code>SetMaximumThreads(3 20, 10)</code> i kreirati 20 niti. Svaka nit treba da ispise svoje ime + ID. Nakon toga treba nit da pozove <code>thread_sleep(10)</code>. Ovo se ponavlja dok sve niti ne zavrse.

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

OS1/Modifikacije avgust 2023

2023-09-06T21:16:27Z

K0v4c: K0v4c преместио је страницу OS1/Modifikacije avgust 2023 на ОС1/Модификације август 2023

#Преусмери [[ОС1/Модификације август 2023]]

ОС1/Модификације август 2023

2023-09-06T21:16:27Z

K0v4c: K0v4c преместио је страницу OS1/Modifikacije avgust 2023 на ОС1/Модификације август 2023

{{tocright}}
Sledeće modifikacije su se pojavile na odbrani projekta u avgustu 2023.

== Modifikacija za 20 bodova ==

Potrebno je prosiriti usluge klase Thread tako da zadovoljava sledece uslove

Dodati staticku metodu <code>SetMaximumThreads(int num_of_threads)</code> koju korisnik poziva na pocetku programa. Ova metoda postavlja ogranicenje na maksimalan broj '''korisnicnckih''' niti.

Nakon postavljanja maksimalnog broja niti, slobodno je moguce kreirati dati broj niti, nakon toga sve novokreirane niti se blokiraju. Kada jedna od kreiranih korisnickih niti zavrsi svoje izvrsavanje ona odblokira jednu od prethodno blokiranih niti u redosledu kojem su blokirane.

=== Test ===
Potrebno je staviti maksimalan broj niti na 3 i kreirati 20 niti. Svaka nit treba da ispise svoje ime + ID niti cilicno 5 puta. Nakog toga treba da simulira spavanje semaforom ili busy wait-om koji je u linearnoj korelacijai sa ID-om date niti.

== Modifikacija za 30 bodova ==

Dodati staticku metodu <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> koju korisnik poziva na pocetku programa. Ova metoda postavlja ogranicenje na maksimalan broj '''korisnicnckih''' niti.

Nakon pozivanja metode <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> moguce je kreirati slobodno kreirati num_of_threads niti. Nakon toga naredne niti se blokiraju. Kada nit zavrsi svoje izvrsavanje ona prestaje sa radom (ove niti ne treba da deblokiraju prethodno blokirane niti). Nakon isteka max_time vremena potrebno je ispisati '''Waiting done: ''', i zatim odblokirati niti jednu za drugom onako kako se blokirane pritom da se izmedju 2 deblokiranja ceka interval_time vremena. Posle svakog deblokiranja niti treba ispisati '''Interval time elapsed '''.

=== Test ===

Potrebno je pozvati <code>SetMaximumThreads(3 20, 10)</code> i kreirati 20 niti. Svaka nit treba da ispise svoje ime + ID. Nakon toga treba nit da pozove <code>thread_sleep(10)</code>. Ovo se ponavlja dok sve niti ne zavrse.

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

ОС1/Модификације август 2023

2023-09-06T21:14:52Z

K0v4c: /* Test */

ОС1/Модификације август 2023

2023-09-06T21:13:04Z

K0v4c:

{{tocright}}
Sledeće modifikacije su se pojavile na odbrani projekta u avgustu 2023.

== Modifikacija za 20 bodova ==

Potrebno je prosiriti usluge klase Thread tako da zadovoljava sledece uslove

Dodati staticku metodu <code>SetMaximumThreads(int num_of_threads)</code> koju korisnik poziva na pocetku programa. Ova metoda postavlja ogranicenje na maksimalan broj '''korisnicnckih''' niti.

Nakon postavljanja maksimalnog broja niti, slobodno je moguce kreirati dati broj niti, nakon toga sve novokreirane niti se blokiraju. Kada jedna od kreiranih korisnickih niti zavrsi svoje izvrsavanje ona odblokira jednu od prethodno blokiranih niti u redosledu kojem su blokirane.

=== Test ===
Potrebno je staviti maksimalan broj niti na 3 i kreirati 20 niti. Svaka nit treba da ispise svoje ime + ID niti cilicno 5 puta. Nakog toga treba da simulira spavanje semaforom ili busy wait-om koji je u linearnoj korelacijai sa ID-om date niti.

== Modifikacija za 30 bodova ==

Dodati staticku metodu <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> koju korisnik poziva na pocetku programa. Ova metoda postavlja ogranicenje na maksimalan broj '''korisnicnckih''' niti.

Nakon pozivanja metode <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> moguce je kreirati slobodno kreirati num_of_threads niti. Nakon toga naredne niti se blokiraju. Kada nit zavrsi svoje izvrsavanje ona prestaje sa radom (ove niti ne treba da deblokiraju prethodno blokirane niti). Nakon isteka max_time vremena potrebno je ispisati '''Waiting done: ''', i zatim odblokirati niti jednu za drugom onako kako se blokirane pritom da se izmedju 2 deblokiranja ceka interval_time vremena. Posle svakog deblokiranja niti treba ispisati '''Interval time elapsed '''.

=== Test ===

Potrebno je kreirati pozvati <code>SetMaximumThreads(3 20, 10)</code> i kreirati 20 niti. Svaka nit treba da ispise svoje ime + ID. Nakon toga treba nit da pozove <code>thread_sleep(10)</code>. Ovo se ponavlja dok sve niti ne zavrse.

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

ОС1/Модификације август 2023

2023-09-06T21:12:31Z

K0v4c: Dodata modifikacija

{{tocright}}
Sledeće modifikacije su se pojavile na odbrani projekta u avgustu 2023.

== Modifikacija za 20 bodova ==

Potrebno je prosiriti usluge klase Thread tako da zadovoljava sledece uslove

Dodati staticku metodu <code>SetMaximumThreads(int num_of_threads)</code> koju korisnik poziva na pocetku programa. Ova metoda postavlja ogranicenje na maksimalan broj '''korisnicnckih''' niti.

Nakon postavljanja maksimalnog broja niti, slobodno je moguce kreirati dati broj niti, nakon toga sve novokreirane niti se blokiraju. Kada jedna od kreiranih korisnickih niti zavrsi svoje izvrsavanje ona odblokira jednu od prethodno blokiranih niti u redosledu kojem su blokirane.

=== Test ===
Potrebno je staviti maksimalan broj niti na 3 i kreirati 20 niti. Svaka nit treba da ispise svoje ime + ID niti cilicno 5 puta. Nakog toga treba da simulira spavanje semaforom ili busy wait-om koji je u linearnoj korelacijai sa ID-om date niti.

== Modifikacija za 30 bodova ==

Dodati staticku metodu <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> koju korisnik poziva na pocetku programa. Ova metoda postavlja ogranicenje na maksimalan broj '''korisnicnckih''' niti.

Nakon pozivanja metode <code>SetMaximumThreads(int num_of_threads, int max_time, int interval_time)</code> moguce je kreirati slobodno kreirati num_of_threads niti. Nakon toga naredne niti se blokiraju. Kada nit zavrsi svoje izvrsavanje ona prestaje sa radom (ove niti ne treba da deblokiraju prethodno blokirane niti). Nakon isteka max_time vremena potrebno je ispisati '''Waiting done: ''', i zatim odblokirati niti jednu za drugom onako kako se blokirane pritom da se izmedju 2 deblokiranja ceka interval_time vremena. Posle svakog deblokiranja niti treba ispisati '''Interval time elapsed '''.

=== Test ===

Potrebno je kreirati pozvati <code>SetMaximumThreads(3 20, 10)</code> i kreirati 20 niti. Svaka nit treba da ispise svoje ime + ID. Nakon toga treba nit da pozove <code>thread_sleep(10)</code>. Ovo se ponavlja dok sve niti ne zavrse.

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

ОС1/Јун 2013

2023-08-26T11:22:36Z

K0v4c: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta su multiprocesorski, a šta distribuirani sistemi?

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

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

=== Rešenje ===
* Prva iteracija: P1 pravi P2, <code>pid[0] = 2</code> u P1
* Druga iteracija: P1 pravi P3, <code>pid[1] = 3</code> u P1 dok je <code>pid[0] = 2</code> u P3 zbog toga što je taj niz kopiran iz P1
* Druga iteracija: P2 pravi P4, <code>pid[1] = 4</code> u P2
Na kraju postoji 4 vrednosti koje nisu nula.

== 3. zadatak ==
=== Postavka ===
Dokazati da Petersonov algoritam za međusobno isključenje kritičnih sekcija dva uporedna procesa uposlenim čekanjem zaista obezbeđuje međusobno isključenje, odnosno ne poseduje problem utrkivanja (''race condition'').

=== Rešenje ===
Pretpostavimo da oba procesa uposleno čekaju. Promenljiva turn "prelama" u situaciji kada oba procesa žele da uđu u kritičnu sekciju jer turn može imati vrednost ili 1 ili 2. Dakle, nemoguće je da dođe do utrkivanja.

== 4. zadatak ==
=== Postavka ===
Korišćenjem klasičnih brojačkih semafora, napisati kod za kritičnu sekciju u koju može uporedo ući najviše ''N'' procesa.

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="c">
void* getBestFit(size_t sz) {
FreeSegment* bestFit = 0
size_t smallestFragment = MAX_SIZE;
for (FreeSegment* cur = freeSegHead; cur != 0; cur = cur->next) {
if (cur->size < sz) {
continue;
}
if (cur->size < smallestFragment) {
smallestFragment = cur->size;
bestFit = cur;
}
}
if (bestFit == 0) {
return 0;
}
FreeSegment* newFrag = (FreeSegment*)((char*)bestFit + sz);
if (bestFit->prev) {
bestFit->prev->next = newFrag;
} else {
freeSegHead = bestFit->next;
}
if (bestFit->next) {
bestFit->next->prev = newFrag;
}
newFrag->prev = bestFit->prev;
newFrag->next = bestFit->next;
newFrag->size = bestFit->size - sz;
return bestFit;
}
</syntaxhighlight>

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

=== Rešenje ===

VA: 10 PMT1 | 10 PMT2 | 12 offset

Ulaz PMT 1. nivoa sadrzi fizičku adresu početka PMT 2. nivoa. Kako je fizička adresa 32b = 4B odavde sledi da veličina PMT 1. nivoa je:

4B * 2<sup>10</sup> = 4KB

== 8. zadatak ==
=== Postavka ===
Ukratko objasniti tehniku dvostrukog baferisanja (''double buffering'') kod ulaza/izlaza.

=== Rešenje ===
Proizvođač upisuje u jedan bafer dok potrošač čita iz drugog bafora. Kada oba završe, baferi zamenjuju uloge.

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

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

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem koristi bit vektor za evidenciju slobodnih blokova na disku. Kolika je veličina ovog vektora u bajtovima, za disk veličine 256 GB sa blokom veličine 512B

=== Rešenje ===
Na disku ima ukupno <math>\frac{256GB}{512B} = 2^{29}</math> blokova. Pošto je za svaki blok potreban po jedan bit, količinu prostora određujemo kao <math>\frac{2^{29}}{2^3} = 64 MB</math>.

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

ОС1/Јун 2013

2023-08-26T11:22:22Z

K0v4c: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta su multiprocesorski, a šta distribuirani sistemi?

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

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

=== Rešenje ===
* Prva iteracija: P1 pravi P2, <code>pid[0] = 2</code> u P1
* Druga iteracija: P1 pravi P3, <code>pid[1] = 3</code> u P1 dok je <code>pid[0] = 2</code> u P3 zbog toga što je taj niz kopiran iz P1
* Druga iteracija: P2 pravi P4, <code>pid[1] = 4</code> u P2
Na kraju postoji 4 vrednosti koje nisu nula.

== 3. zadatak ==
=== Postavka ===
Dokazati da Petersonov algoritam za međusobno isključenje kritičnih sekcija dva uporedna procesa uposlenim čekanjem zaista obezbeđuje međusobno isključenje, odnosno ne poseduje problem utrkivanja (''race condition'').

=== Rešenje ===
Pretpostavimo da oba procesa uposleno čekaju. Promenljiva turn "prelama" u situaciji kada oba procesa žele da uđu u kritičnu sekciju jer turn može imati vrednost ili 1 ili 2. Dakle, nemoguće je da dođe do utrkivanja.

== 4. zadatak ==
=== Postavka ===
Korišćenjem klasičnih brojačkih semafora, napisati kod za kritičnu sekciju u koju može uporedo ući najviše ''N'' procesa.

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="c">
void* getBestFit(size_t sz) {
FreeSegment* bestFit = 0
size_t smallestFragment = MAX_SIZE;
for (FreeSegment* cur = freeSegHead; cur != 0; cur = cur->next) {
if (cur->size < sz) {
continue;
}
if (cur->size < smallestFragment) {
smallestFragment = cur->size;
bestFit = cur;
}
}
if (bestFit == 0) {
return 0;
}
FreeSegment* newFrag = (FreeSegment*)((char*)bestFit + sz);
if (bestFit->prev) {
bestFit->prev->next = newFrag;
} else {
freeSegHead = bestFit->next;
}
if (bestFit->next) {
bestFit->next->prev = newFrag;
}
newFrag->prev = bestFit->prev;
newFrag->next = bestFit->next;
newFrag->size = bestFit->size - sz;
return bestFit;
}
</syntaxhighlight>

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

=== Rešenje ===

VA: 10 PMT1 | 10 PMT2 | 12 offset

Ulaz PMT 1. nivoa sadrzi fizičku adresu početka PMT 2. nivoa. Kako je fizička adresa 32b = 4B odavde sledi da veličina PMT 1. nivoa je:

4B * 2<sup>12</sup> = 4KB

== 8. zadatak ==
=== Postavka ===
Ukratko objasniti tehniku dvostrukog baferisanja (''double buffering'') kod ulaza/izlaza.

=== Rešenje ===
Proizvođač upisuje u jedan bafer dok potrošač čita iz drugog bafora. Kada oba završe, baferi zamenjuju uloge.

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

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

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem koristi bit vektor za evidenciju slobodnih blokova na disku. Kolika je veličina ovog vektora u bajtovima, za disk veličine 256 GB sa blokom veličine 512B

=== Rešenje ===
Na disku ima ukupno <math>\frac{256GB}{512B} = 2^{29}</math> blokova. Pošto je za svaki blok potreban po jedan bit, količinu prostora određujemo kao <math>\frac{2^{29}}{2^3} = 64 MB</math>.

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

ОС1/Јун 2013

2023-08-26T11:21:58Z

K0v4c: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta su multiprocesorski, a šta distribuirani sistemi?

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

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

=== Rešenje ===
* Prva iteracija: P1 pravi P2, <code>pid[0] = 2</code> u P1
* Druga iteracija: P1 pravi P3, <code>pid[1] = 3</code> u P1 dok je <code>pid[0] = 2</code> u P3 zbog toga što je taj niz kopiran iz P1
* Druga iteracija: P2 pravi P4, <code>pid[1] = 4</code> u P2
Na kraju postoji 4 vrednosti koje nisu nula.

== 3. zadatak ==
=== Postavka ===
Dokazati da Petersonov algoritam za međusobno isključenje kritičnih sekcija dva uporedna procesa uposlenim čekanjem zaista obezbeđuje međusobno isključenje, odnosno ne poseduje problem utrkivanja (''race condition'').

=== Rešenje ===
Pretpostavimo da oba procesa uposleno čekaju. Promenljiva turn "prelama" u situaciji kada oba procesa žele da uđu u kritičnu sekciju jer turn može imati vrednost ili 1 ili 2. Dakle, nemoguće je da dođe do utrkivanja.

== 4. zadatak ==
=== Postavka ===
Korišćenjem klasičnih brojačkih semafora, napisati kod za kritičnu sekciju u koju može uporedo ući najviše ''N'' procesa.

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="c">
void* getBestFit(size_t sz) {
FreeSegment* bestFit = 0
size_t smallestFragment = MAX_SIZE;
for (FreeSegment* cur = freeSegHead; cur != 0; cur = cur->next) {
if (cur->size < sz) {
continue;
}
if (cur->size < smallestFragment) {
smallestFragment = cur->size;
bestFit = cur;
}
}
if (bestFit == 0) {
return 0;
}
FreeSegment* newFrag = (FreeSegment*)((char*)bestFit + sz);
if (bestFit->prev) {
bestFit->prev->next = newFrag;
} else {
freeSegHead = bestFit->next;
}
if (bestFit->next) {
bestFit->next->prev = newFrag;
}
newFrag->prev = bestFit->prev;
newFrag->next = bestFit->next;
newFrag->size = bestFit->size - sz;
return bestFit;
}
</syntaxhighlight>

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

=== Rešenje ===

VA: 10 PMT1 | 10 PMT2 | 12 offset

Ulaz PMT 1. nivoa sadrzi fizičku adresu početka PMT 2. nivoa. Kako je fizička adresa 32b = 4B odavde sledi da veličina PMT 1. nivoa je:

4B * 2^{10} = 4KB

== 8. zadatak ==
=== Postavka ===
Ukratko objasniti tehniku dvostrukog baferisanja (''double buffering'') kod ulaza/izlaza.

=== Rešenje ===
Proizvođač upisuje u jedan bafer dok potrošač čita iz drugog bafora. Kada oba završe, baferi zamenjuju uloge.

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

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

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem koristi bit vektor za evidenciju slobodnih blokova na disku. Kolika je veličina ovog vektora u bajtovima, za disk veličine 256 GB sa blokom veličine 512B

=== Rešenje ===
Na disku ima ukupno <math>\frac{256GB}{512B} = 2^{29}</math> blokova. Pošto je za svaki blok potreban po jedan bit, količinu prostora određujemo kao <math>\frac{2^{29}}{2^3} = 64 MB</math>.

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

ОС1/Јун 2013

2023-08-26T11:19:21Z

K0v4c: /* Rešenje */

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

== 1. zadatak ==
=== Postavka ===
Šta su multiprocesorski, a šta distribuirani sistemi?

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

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

=== Rešenje ===
* Prva iteracija: P1 pravi P2, <code>pid[0] = 2</code> u P1
* Druga iteracija: P1 pravi P3, <code>pid[1] = 3</code> u P1 dok je <code>pid[0] = 2</code> u P3 zbog toga što je taj niz kopiran iz P1
* Druga iteracija: P2 pravi P4, <code>pid[1] = 4</code> u P2
Na kraju postoji 4 vrednosti koje nisu nula.

== 3. zadatak ==
=== Postavka ===
Dokazati da Petersonov algoritam za međusobno isključenje kritičnih sekcija dva uporedna procesa uposlenim čekanjem zaista obezbeđuje međusobno isključenje, odnosno ne poseduje problem utrkivanja (''race condition'').

=== Rešenje ===
Pretpostavimo da oba procesa uposleno čekaju. Promenljiva turn "prelama" u situaciji kada oba procesa žele da uđu u kritičnu sekciju jer turn može imati vrednost ili 1 ili 2. Dakle, nemoguće je da dođe do utrkivanja.

== 4. zadatak ==
=== Postavka ===
Korišćenjem klasičnih brojačkih semafora, napisati kod za kritičnu sekciju u koju može uporedo ući najviše ''N'' procesa.

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

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

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

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

=== Rešenje ===
<syntaxhighlight lang="c">
void* getBestFit(size_t sz) {
FreeSegment* bestFit = 0
size_t smallestFragment = MAX_SIZE;
for (FreeSegment* cur = freeSegHead; cur != 0; cur = cur->next) {
if (cur->size < sz) {
continue;
}
if (cur->size < smallestFragment) {
smallestFragment = cur->size;
bestFit = cur;
}
}
if (bestFit == 0) {
return 0;
}
FreeSegment* newFrag = (FreeSegment*)((char*)bestFit + sz);
if (bestFit->prev) {
bestFit->prev->next = newFrag;
} else {
freeSegHead = bestFit->next;
}
if (bestFit->next) {
bestFit->next->prev = newFrag;
}
newFrag->prev = bestFit->prev;
newFrag->next = bestFit->next;
newFrag->size = bestFit->size - sz;
return bestFit;
}
</syntaxhighlight>

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

=== Rešenje ===

VA: 10 | 10 | 12

Ulaz PMT 1. nivoa sadrzi fizičku adresu početka PMT 2. nivoa. Kako je fizička adresa 32b = 4B odavde sledi da veličina PMT 1. nivoa je:

4B * 2^(10) = 4KB

== 8. zadatak ==
=== Postavka ===
Ukratko objasniti tehniku dvostrukog baferisanja (''double buffering'') kod ulaza/izlaza.

=== Rešenje ===
Proizvođač upisuje u jedan bafer dok potrošač čita iz drugog bafora. Kada oba završe, baferi zamenjuju uloge.

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

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

== 10. zadatak ==
=== Postavka ===
Neki fajl sistem koristi bit vektor za evidenciju slobodnih blokova na disku. Kolika je veličina ovog vektora u bajtovima, za disk veličine 256 GB sa blokom veličine 512B

=== Rešenje ===
Na disku ima ukupno <math>\frac{256GB}{512B} = 2^{29}</math> blokova. Pošto je za svaki blok potreban po jedan bit, količinu prostora određujemo kao <math>\frac{2^{29}}{2^3} = 64 MB</math>.

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