КДП/Фебруар 2021 - Историја измена

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

2024-02-06T23:31:12Z

Решење

← Старија измена		Верзија на датум 7. фебруар 2024. у 01:31
Ред 9:		Ред 9:
	У ''Test-and-set'' решењу при свакој провери дељене промењиве се истовремено и уписује у њу а то захтева синхронизацију кеш меморија језгара процесора и значајно окупира магистралу и не дозвољавва другим процесима да је користе. Ради боље перформансе програма потребно је што је могуће више смањити уписе у дељене промењиве.		У ''Test-and-set'' решењу при свакој провери дељене промењиве се истовремено и уписује у њу а то захтева синхронизацију кеш меморија језгара процесора и значајно окупира магистралу и не дозвољавва другим процесима да је користе. Ради боље перформансе програма потребно је што је могуће више смањити уписе у дељене промењиве.

	''Test and test and set'' решење ради баш то. Прво се процес ~~црти~~ у петљи док је критична секција закључана, па тек онда кад се откључа покуша да добије приступ, а ако није успео опет се врти у петљи док процес који је заузео критичну секцију пре њега не ослободи кључ.		''Test and test and set'' решење ради баш то. Прво се процес врти у петљи док је критична секција закључана, па тек онда кад се откључа покуша да добије приступ, а ако није успео опет се врти у петљи док процес који је заузео критичну секцију пре њега не ослободи кључ.

	''Fine grain'' решење користећи <syntaxhighlight lang="cpp" inline>SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; ></syntaxhighlight> би могло да се реши на следећи начин:		''Fine grain'' решење користећи <syntaxhighlight lang="cpp" inline>SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; ></syntaxhighlight> би могло да се реши на следећи начин:

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

2024-02-06T23:30:40Z

@@ Ред 3: / Ред 3: @@
 == {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
 === Поставка ===
 Написати и објасните ''test and test and set'' решење за критичну секцију. Уколико би уместо TS(var) постојала операција SWAP која би недељиво обављала замену вредности два операнда (<syntaxhighlight lang="cpp" inline>SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; ></syntaxhighlight>), да ли је могуће направити Fine grain решење и ако је могуће – направите га.
 === Решење ===
 == {{категорија|2. задатак|Штафетна_палица}} ==

Fedja: kategorije zadataka

2023-02-11T17:08:32Z

kategorije zadataka

← Старија измена		Верзија на датум 11. фебруар 2023. у 19:08
Ред 2:		Ред 2:
	Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2021/KDP_2021_feb.pdf странице предмета.]		Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2021/KDP_2021_feb.pdf странице предмета.]

	== 1. задатак ==		== {{категорија\|1. задатак\|Синхронизациони_алгоритми}} ==
	{{делимично решено}}		{{делимично решено}}
	=== Поставка ===		=== Поставка ===
Ред 10:		Ред 10:


	== 2. задатак ==		== {{категорија\|2. задатак\|Штафетна_палица}} ==
	{{делимично решено}}		{{делимично решено}}
	=== Поставка ===		=== Поставка ===

KockaAdmiralac: Deluje rešeno

2023-02-11T16:47:21Z

Deluje rešeno

← Старија измена		Верзија на датум 11. фебруар 2023. у 18:47
Ред 18:		Ред 18:

	== {{категорија\|3. задатак\|Филтерски_процеси}} ==		== {{категорија\|3. задатак\|Филтерски_процеси}} ==
	~~{{делимично решено}}~~
	=== Поставка ===		=== Поставка ===
	Филтерски процеси имају један улаз и један излаз, и до три локације за примљене бројева. Направите проточну обраду (''pipeline'') од n ових филтерских процеса која сортира па сабира до 2*n улазних реалних бројева које се убацују на почетак проточне обраде, а завршавају се са EOS. На излаз проточне обраде се шаље сума па EOS.		Филтерски процеси имају један улаз и један излаз, и до три локације за примљене бројева. Направите проточну обраду (''pipeline'') од n ових филтерских процеса која сортира па сабира до 2*n улазних реалних бројева које се убацују на почетак проточне обраде, а завршавају се са EOS. На излаз проточне обраде се шаље сума па EOS.

Fedja: kategorije zadataka

2023-02-11T03:00:00Z

kategorije zadataka

← Старија измена		Верзија на датум 11. фебруар 2023. у 05:00
Ред 17:		Ред 17:
	=== Решење ===		=== Решење ===

	== 3. задатак ==		== {{категорија\|3. задатак\|Филтерски_процеси}} ==
	{{делимично решено}}		{{делимично решено}}
	=== Поставка ===		=== Поставка ===
Ред 51:		Ред 51:
	</syntaxhighlight>		</syntaxhighlight>

	== 4. задатак ==		== {{категорија\|4. задатак\|CSP}} ==
	=== Поставка ===		=== Поставка ===
	Посматра се једна подземна гаража. Постоји само једна рампа која служи и за улаз, и за излаз из гараже. У гаражи има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико слободног места нема, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другом гаражом. Аутомобили при изласку плаћају услуге гараже и излазе један по један. Аутомобили се опслужују по ФИФО редоследу. Решити задатак користећи CSP.		Посматра се једна подземна гаража. Постоји само једна рампа која служи и за улаз, и за излаз из гараже. У гаражи има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико слободног места нема, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другом гаражом. Аутомобили при изласку плаћају услуге гараже и излазе један по један. Аутомобили се опслужују по ФИФО редоследу. Решити задатак користећи CSP.

KockaAdmiralac: Zapravo CSP koristi obične zagrade za indeksiranje niza

2022-06-12T23:38:20Z

Zapravo CSP koristi obične zagrade za indeksiranje niza

← Старија измена		Верзија на датум 13. јун 2022. у 01:38
Ред 99:		Ред 99:
	[		[
	// Ово је измишљена синтакса за приступање пољу структуре		// Ово је измишљена синтакса за приступање пољу структуре
	entering > 0; parked + exiting < N; enterQueue[enterHead].ticket > exitQueue[exitHead].ticket ->		entering > 0; parked + exiting < N; enterQueue(enterHead).ticket > exitQueue(exitHead).ticket ->
	car(enterQueue[enterHead].carId)!pass;		car(enterQueue(enterHead).carId)!pass;
	enterHead := (enterHead + 1) mod N		enterHead := (enterHead + 1) mod N
	□		□
	exiting > 0; parked + exiting = N or enterQueue[enterHead].ticket < exitQueue[exitHead].ticket ->		exiting > 0; parked + exiting = N or enterQueue(enterHead).ticket < exitQueue(exitHead).ticket ->
	car(exitQueue[exitHead].carId)!pass;		car(exitQueue(exitHead).carId)!pass;
	exitHead := (exitHead + 1) mod N		exitHead := (exitHead + 1) mod N
	]		]
Ред 125:		Ред 125:
	[		[
	// Ово је измишљена синтакса за приступање пољу структуре		// Ово је измишљена синтакса за приступање пољу структуре
	entering > 0; parked + exiting < N; enterQueue[enterHead].ticket > exitQueue[exitHead].ticket ->		entering > 0; parked + exiting < N; enterQueue(enterHead).ticket > exitQueue(exitHead).ticket ->
	car(enterQueue[enterHead].carId)!pass;		car(enterQueue(enterHead).carId)!pass;
	enterHead := (enterHead + 1) mod N		enterHead := (enterHead + 1) mod N
	□		□
	exiting > 0; parked + exiting = N or enterQueue[enterHead].ticket < exitQueue[exitHead].ticket ->		exiting > 0; parked + exiting = N or enterQueue(enterHead).ticket < exitQueue(exitHead).ticket ->
	car(exitQueue[exitHead].carId)!pass;		car(exitQueue(exitHead).carId)!pass;
	exitHead := (exitHead + 1) mod N		exitHead := (exitHead + 1) mod N
	]		]

KockaAdmiralac: Treći i četvrti zadatak

2022-06-12T23:34:42Z

Treći i četvrti zadatak

Нова страница

{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2021/KDP_2021_feb.pdf странице предмета.]

== 1. задатак ==
{{делимично решено}}
=== Поставка ===
Написати и објасните ''test and test and set'' решење за критичну секцију. Уколико би уместо TS(var) постојала операција SWAP која би недељиво обављала замену вредности два операнда (<syntaxhighlight lang="cpp" inline>SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; ></syntaxhighlight>), да ли је могуће направити Fine grain решење и ако је могуће – направите га.

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

== 2. задатак ==
{{делимично решено}}
=== Поставка ===
Посматра се семафор за регулацију саобраћаја на улици са једним пешачким прелазом. Када пешак стигне до пешачког прелаза, уколико је светло за пешаке зелено, он прелази улицу. Уколико је у моменту његовог доласка светло за пешаке црвено, он чека да се укључи зелено светло. Зелено светло за пешаке се укључује или након К секунди од појаве првог пешака који је затекао црвено светло, или након проласка C аутомобила од последњег активног зеленог светла за пешаке. Зелено светло за пешаке трајања G секунди се пали само уколико је испуњен неки од наведених услова и барем један пешак чека. Користећи расподељене бинарне семафоре и технику предаје штафетне палице написати програме за пешаке, аутомобиле и семафор за регулацију саобраћаја. Доступна је функција <code>system_time()</code> која враћа тренутно време система. Учесницима треба неко време да пређу улицу.

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

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Филтерски процеси имају један улаз и један излаз, и до три локације за примљене бројева. Направите проточну обраду (''pipeline'') од n ових филтерских процеса која сортира па сабира до 2*n улазних реалних бројева које се убацују на почетак проточне обраде, а завршавају се са EOS. На излаз проточне обраде се шаље сума па EOS.

=== Решење ===
Када стигне EOS, уколико су се све остале вредности пропагирале кроз мрежу, ове вредности ће бити сортиране од највеће ка најмањој како се редом буде ишло кроз садржај филтерских процеса. У задатку није специфицирано на који начин треба да се види чињеница да се низ сортира, па је ово узето као претпоставка.
<syntaxhighlight lang="cpp">
void process() {
chan<int> in;
chan<int> out;
int numReceived = 0;
int input;
int mem[2];
while ((input = in.receive()) != EOS) {
if (numReceived < 2) {
mem[numReceived++] = input;
} else {
if (input <= mem[0] && input <= mem[1]) {
out.send(input);
} else if (mem[0] <= input && mem[0] <= mem[1]) {
out.send(mem[0]);
mem[0] = input;
} else {
out.send(mem[1]);
mem[1] = input;
}
}
}
out.send(mem[0] + mem[1]);
out.send(EOS);
}
</syntaxhighlight>

== 4. задатак ==
=== Поставка ===
Посматра се једна подземна гаража. Постоји само једна рампа која служи и за улаз, и за излаз из гараже. У гаражи има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико слободног места нема, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другом гаражом. Аутомобили при изласку плаћају услуге гараже и излазе један по један. Аутомобили се опслужују по ФИФО редоследу. Решити задатак користећи CSP.

=== Решење ===
<syntaxhighlight lang="pascal">
[ramp::RAMP, car(i: 0..2*N+1)::CAR]

RAMP::
entering: integer;
exiting: integer;
parked: integer;
// Ово је измишљена синтакса за низ структура
enterQueue: (0..N) (carId, ticket: integer);
exitQueue: (0..N) (carId, ticket: integer);
enterHead: integer;
exitHead: integer;
enterTail: integer;
exitTail: integer;
ticket := integer;
entering := 0;
exiting := 0;
parked := 0;
enterHead := 0;
exitHead := 0;
enterTail := 0;
exitTail := 0;
ticket := 0;
*[
parked - exiting + entering >= N; (i: 0..2*N+1) car(i)?enter -> car(i)!full
□
parked - exiting + entering < N; (i: 0..2*N+1) car(i)?enter ->
entering := entering + 1;
[
entering = 1; exiting = 0; parked < N -> car(i)!pass
□
entering > 1 or exiting > 0 or parked = N ->
// Ово је измишљена синтакса за убацивање структуре у низ
enterQueue(enterTail) := (i, ticket);
ticket := ticket + 1;
enterTail := (enterTail + 1) mod N
]
□
(i: 0..2*N+1) car(i)?entered ->
entering := entering - 1;
parked := parked + 1;
[
// Ово је измишљена синтакса за приступање пољу структуре
entering > 0; parked + exiting < N; enterQueue[enterHead].ticket > exitQueue[exitHead].ticket ->
car(enterQueue[enterHead].carId)!pass;
enterHead := (enterHead + 1) mod N
□
exiting > 0; parked + exiting = N or enterQueue[enterHead].ticket < exitQueue[exitHead].ticket ->
car(exitQueue[exitHead].carId)!pass;
exitHead := (exitHead + 1) mod N
]
□
(i: 0..2*N+1) car(i)?exit ->
exiting := exiting + 1;
parked := parked - 1;
[
exiting = 1; entering = 0 -> car(i)!pass
□
exiting > 1 or entering > 0 ->
// Ово је измишљена синтакса за убацивање структуре у низ
exitQueue(exitTail) := (i, ticket);
ticket := ticket + 1;
exitTail := (exitTail + 1) mod N
]
□
(i: 0..2*N+1) car(i)?exited ->
exiting := exiting - 1;
[
// Ово је измишљена синтакса за приступање пољу структуре
entering > 0; parked + exiting < N; enterQueue[enterHead].ticket > exitQueue[exitHead].ticket ->
car(enterQueue[enterHead].carId)!pass;
enterHead := (enterHead + 1) mod N
□
exiting > 0; parked + exiting = N or enterQueue[enterHead].ticket < exitQueue[exitHead].ticket ->
car(exitQueue[exitHead].carId)!pass;
exitHead := (exitHead + 1) mod N
]
]

CAR::
ramp!enter;
[
// Тражимо другу гаражу
ramp?full -> skip
□
ramp?pass ->
// Пролазимо кроз рампу
ramp!entered;
// Паркирани смо
ramp!exit;
ramp?pass;
// Пролазимо кроз рампу
ramp!exited
]
</syntaxhighlight>

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