{{tocright}}


== 1. задатак ==
== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објаснити CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вердности два операнда (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Објаснити зашто је то правична критична секција.
=== Решење ===
CLH алгоритам процесе уланчава у уланчану листу по редоследу којим долазе. Самим тим та листа се понаша као ред и тиме је овај алгоритам правичан јер користи FIFO принцип.
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev;
< prev = tail; tail = new_node; >
< await(tail == nullptr || !prev->locked); >
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
Пошто су prev и new_node локални показивачи, можемо да их усмеримо на новокреирани чвор. Затим се недељиво позива функција SWAP која ће недељиво заменити вредност prev и tail показивача.
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev = new_node;
SWAP(prev, tail);
while(prev!= nullptr && prev->locked) skip();
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>

== 2. задатак ==
== {{категорија|1. задатак|Монитори}} ==
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарлно постављене једна иза друге. Камиона заузима три, аутовус две а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у ком чекају у реду, док на трајекту има места. Када нема места да се наредно возило у реду укрца и трајект није у потпуности попуњен, преко реда се укрцавају мања возила док се трајект не попуни у потпуности. Када је комплетно пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од оног у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Написати монитор са ''signal and wait'' дисциплином који решава дати проблем.
=== Решење ===
{{делимично решено}}
== 3. задатак ==
== {{категорија|1. задатак|Филтерски_процеси}} ==
=== Поставка ===
Филтерски процеси имају један улаз и један излаз и раде следеће: примају позитивне вредности на улазу и прослеђују их на излаз ако су веће од запамћеног минимума процеса. Процеси имају само две локације, за сачувани минимум и за последњу примљену вредност. Када на улаз стигне EOS, избацују минималну вредност на излаз а затим EOS. Направите проточну обраду (''pipeline'') од n процеса који опадајуће соритају до n улазних позитивних вредности које се убацују на почетак проточне обраде а завршавају се са EOS.
=== Решење ===
<syntaxhighlight lang="cpp">
void process() {
chan<int> in;
chan<int> out;
int input;
int min;
while ((input = in.receive()) != EOS) {
if (input < min) {
out.send(min);
min = input;
} else out.send(input);
out.send(min);
out.send(EOS);
}
</syntaxhighlight>

== 4. задатак ==
== {{категорија|1. задатак|CSP}} ==
=== Поставка ===
Постоји N пчела и један гладан медвед (''The bear and honeybees''). Они користе заједничку кошницу. Кошница је иницијално празна и може да прими до N напрстака меда. Медвед спава док се кошница не напуни медом, када се напуни медом меда поједе сав мед након чега се враћа на спавање. Пчелице непрестано лете од света до света и сакупљају мед. Она пчела која је попунила кошницу буди медведа. Решити проблем користећи CSP.
=== Решење ===
{{делимично решено}}


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

КДП/Фебруар 2023

2024-02-05T21:20:31Z

Remaxsrb:

КДП/Фебруар 2023

2024-02-05T21:18:58Z

Remaxsrb: /* Решење */

КДП/Фебруар 2023

2024-02-05T15:08:12Z

Remaxsrb: /* Решење */

КДП/Септембар 2023

2024-02-05T15:05:42Z

Remaxsrb:

{{tocright}}


== 1. задатак ==
=== Поставка ===
Написати и објаснити CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вердности два операнда (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Објаснити зашто је то правична критична секција.
=== Решење ===
CLH алгоритам процесе уланчава у уланчану листу по редоследу којим долазе. Самим тим та листа се понаша као ред и тиме је овај алгоритам правичан јер користи FIFO принцип.
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev;
< prev = tail; tail = new_node; >
< await(tail == nullptr || !prev->locked); >
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
Пошто су prev и new_node локални показивачи, можемо да их усмеримо на новокреирани чвор. Затим се недељиво позива функција SWAP која ће недељиво заменити вредност prev и tail показивача.
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev = new_node;
SWAP(prev, tail);
while(prev!= nullptr && prev->locked) skip();
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарлно постављене једна иза друге. Камиона заузима три, аутовус две а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у ком чекају у реду, док на трајекту има места. Када нема места да се наредно возило у реду укрца и трајект није у потпуности попуњен, преко реда се укрцавају мања возила док се трајект не попуни у потпуности. Када је комплетно пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од оног у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Написати монитор са ''signal and wait'' дисциплином који решава дати проблем.
=== Решење ===
{{делимично решено}}
== 3. задатак ==
=== Поставка ===
Филтерски процеси имају један улаз и један излаз и раде следеће: примају позитивне вредности на улазу и прослеђују их на излаз ако су веће од запамћеног минимума процеса. Процеси имају само две локације, за сачувани минимум и за последњу примљену вредност. Када на улаз стигне EOS, избацују минималну вредност на излаз а затим EOS. Направите проточну обраду (''pipeline'') од n процеса који опадајуће соритају до n улазних позитивних вредности које се убацују на почетак проточне обраде а завршавају се са EOS.
=== Решење ===
<syntaxhighlight lang="cpp">
void process() {
chan<int> in;
chan<int> out;
int input;
int min;
while ((input = in.receive()) != EOS) {
if (input < min) {
out.send(min);
min = input;
} else out.send(input);
out.send(min);
out.send(EOS);
}
</syntaxhighlight>

== 4. задатак ==
=== Поставка ===
Постоји N пчела и један гладан медвед (''The bear and honeybees''). Они користе заједничку кошницу. Кошница је иницијално празна и може да прими до N напрстака меда. Медвед спава док се кошница не напуни медом, када се напуни медом меда поједе сав мед након чега се враћа на спавање. Пчелице непрестано лете од света до света и сакупљају мед. Она пчела која је попунила кошницу буди медведа. Решити проблем користећи CSP.
=== Решење ===
{{делимично решено}}


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

КДП/Септембар 2023

2024-02-05T15:00:17Z

Remaxsrb: /* Решење */

{{tocright}}
{{делимично решено}}

== 1. задатак ==
=== Поставка ===
Написати и објаснити CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вердности два операнда (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Објаснити зашто је то правична критична секција.
=== Решење ===
CLH алгоритам процесе уланчава у уланчану листу по редоследу којим долазе. Самим тим та листа се понаша као ред и тиме је овај алгоритам правичан јер користи FIFO принцип.
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev;
< prev = tail; tail = new_node; >
< await(tail == nullptr || !prev->locked); >
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
Пошто су prev и new_node локални показивачи, можемо да их усмеримо на новокреирани чвор. Затим се недељиво позива функција SWAP која ће недељиво заменити вредност prev и tail показивача.
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev = new_node;
SWAP(prev, tail);
while(prev!= nullptr && prev->locked) skip();
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>

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

== 3. задатак ==
=== Поставка ===
Филтерски процеси имају један улаз и један излаз и раде следеће: примају позитивне вредности на улазу и прослеђују их на излаз ако су веће од запамћеног минимума процеса. Процеси имају само две локације, за сачувани минимум и за последњу примљену вредност. Када на улаз стигне EOS, избацују минималну вредност на излаз а затим EOS. Направите проточну обраду (''pipeline'') од n процеса који опадајуће соритају до n улазних позитивних вредности које се убацују на почетак проточне обраде а завршавају се са EOS.
=== Решење ===
<syntaxhighlight lang="cpp">
void process() {
chan<int> in;
chan<int> out;
int input;
int min;
while ((input = in.receive()) != EOS) {
if (input < min) {
out.send(min);
min = input;
} else out.send(input);
out.send(min);
out.send(EOS);
}
</syntaxhighlight>

== 4. задатак ==
=== Поставка ===
Постоји N пчела и један гладан медвед (''The bear and honeybees''). Они користе заједничку кошницу. Кошница је иницијално празна и може да прими до N напрстака меда. Медвед спава док се кошница не напуни медом, када се напуни медом меда поједе сав мед након чега се враћа на спавање. Пчелице непрестано лете од света до света и сакупљају мед. Она пчела која је попунила кошницу буди медведа. Решити проблем користећи CSP.
=== Решење ===



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

КДП/Септембар 2023

2024-02-05T14:52:38Z

Remaxsrb: Нова страница: {{tocright}} {{делимично решено}}<!-- Ово ставити уколико НИЈЕДАН задатак није решен, док уколико само неки задаци нису решени на првом месту у њиховој секцији поставити {{делимично решено}}. Уколико се користи било који од ова два шаблона, ОБАВЕЗНО проверити да ли п…

{{tocright}}
{{делимично решено}}

== 1. задатак ==
=== Поставка ===
Написати и објаснити CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вердности два операнда (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Објаснити зашто је то правична критична секција.
=== Решење ===
CLH алгоритам процесе уланчава у уланчану листу по редоследу којим долазе. Самим тим та листа се понаша као ред и тиме је овај алгоритам правичан јер користи FIFO принцип.
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev;
< prev = tail; tail = new_node; >
< await(tail == nullptr || !prev->locked); >
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
Пошто су prev и new_node локални показивачи, можемо да их усмеримо на новокреирани чвор. Затим се недељиво позива функција SWAP која ће недељиво заменити вредност prev и tail показивача.
<syntaxhighlight lang="cpp">
struct Node {
bool locked;
Node() {
locked = true;
}
};

Node* tail = nullptr;

void process() {
while (true) {
Node* new_node = new Node();
Node* prev = new_node;
SWAP(prev, tail);
while(prev!= nullptr && prev->locked) skip();
/* критична секција */
new_node->locked=false;
/* некритична секција */
}
}
</syntaxhighlight>

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

== 3. задатак ==
=== Поставка ===
Филтерски процеси имају један улаз и један излаз и раде следеће: примају позитивне вредности на улазу и прослеђују их на излаз ако су веће од запамћеног минимума процеса. Процеси имају само две локације, за сачувани минимум и за последњу примљену вредност. Када на улаз стигне EOS, избацују минималну вредност на излаз а затим EOS. Направите проточну обраду (''pipeline'') од n процеса који опадајуће соритају до n улазних позитивних вредности које се убацују на почетак проточне обраде а завршавају се са EOS.
=== Решење ===
<syntaxhighlight lang="cpp">
void process() {
chan<int> in;
chan<int> out;
int input;
int min;
while ((input = in.receive()) != EOS) {
if (input < min) {
out.send(min);
min = input;
} else out.send(input);
out.send(EOS);
}
</syntaxhighlight>
== 4. задатак ==
=== Поставка ===
Постоји N пчела и један гладан медвед (''The bear and honeybees''). Они користе заједничку кошницу. Кошница је иницијално празна и може да прими до N напрстака меда. Медвед спава док се кошница не напуни медом, када се напуни медом меда поједе сав мед након чега се враћа на спавање. Пчелице непрестано лете од света до света и сакупљају мед. Она пчела која је попунила кошницу буди медведа. Решити проблем користећи CSP.
=== Решење ===



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

КДП/Фебруар 2023

2024-02-05T13:47:26Z

Remaxsrb: /* {{категорија|1. задатак|Синхронизациони_алгоритми}} */

КДП/Фебруар 2023

2024-02-05T13:42:24Z

Remaxsrb: /* Решење */