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

Fedja: kategorije zadataka

2023-02-11T02:44:08Z

kategorije zadataka

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

	== 1. задатак ==		== {{категорија\|1. задатак\|Монитори}} ==
	=== Поставка ===		=== Поставка ===
	Потребно је да N процеса деле два штампача. Пре употребе штампача, процес P[i] позива мониторску процедуру <code>request()</code>, а процедура враћа идентификатор додељеног штампача - printer. По завршетку штампања, процес P[i] ослобађа штампач са <code>release(printer)</code>. Дефинишите мониторску инваријанту. Развити монитор који користи ''Signal and Continue'' дисциплину. Након тога, претпоставити да код процедуре <code>request</code> постоји додатни аргумент којим процес доставља приоритет захтева. Модификовати монитор, тако да се штампачи добијају у складу са приоритетом. При истом приоритету треба да важи редослед пристизања захтева - ''FCFS''.		Потребно је да N процеса деле два штампача. Пре употребе штампача, процес P[i] позива мониторску процедуру <code>request()</code>, а процедура враћа идентификатор додељеног штампача - printer. По завршетку штампања, процес P[i] ослобађа штампач са <code>release(printer)</code>. Дефинишите мониторску инваријанту. Развити монитор који користи ''Signal and Continue'' дисциплину. Након тога, претпоставити да код процедуре <code>request</code> постоји додатни аргумент којим процес доставља приоритет захтева. Модификовати монитор, тако да се штампачи добијају у складу са приоритетом. При истом приоритету треба да важи редослед пристизања захтева - ''FCFS''.
Ред 71:		Ред 71:
	</syntaxhighlight>		</syntaxhighlight>

	== 2. задатак ==		== {{категорија\|2. задатак\|Региони}} ==
	=== Поставка ===		=== Поставка ===
	Посматра се агенција за изнајмљивање аутомобила. У возном парку постоје 20 стандардних возила и 10 лукс возила. Приликом доласка клијента да изнајми ауто, он се изјашњава да ли жели да изнајми стандардно или лукс возило или му је све једно. Након тога он чека у реду све док му се возило не додели на коришћење. По завршетку коришћења, корисник долази још једном у агенцију и враћа ауто. У агенцији постоји један запослени који води евиденцију о томе који ауто је тренутно на коришћењу код ког корисника. Клијентима није дозвољено напуштање агенције све док запослени не обради њихов захтев за преузимање или враћање возила. Користећи регионе написати методу које се позива приликом доласка клијента да изнајми ауто, методу које се позива приликом доласка клијента да врати ауто и методу која симулира рад запосленог, као и код за иницијализацију. Потребно је обезбедити да возила не стоје на паркингу агенције, уколико постоји било који клијент који жели да изнајми тај тип возила.		Посматра се агенција за изнајмљивање аутомобила. У возном парку постоје 20 стандардних возила и 10 лукс возила. Приликом доласка клијента да изнајми ауто, он се изјашњава да ли жели да изнајми стандардно или лукс возило или му је све једно. Након тога он чека у реду све док му се возило не додели на коришћење. По завршетку коришћења, корисник долази још једном у агенцију и враћа ауто. У агенцији постоји један запослени који води евиденцију о томе који ауто је тренутно на коришћењу код ког корисника. Клијентима није дозвољено напуштање агенције све док запослени не обради њихов захтев за преузимање или враћање возила. Користећи регионе написати методу које се позива приликом доласка клијента да изнајми ауто, методу које се позива приликом доласка клијента да врати ауто и методу која симулира рад запосленог, као и код за иницијализацију. Потребно је обезбедити да возила не стоје на паркингу агенције, уколико постоји било који клијент који жели да изнајми тај тип возила.
Ред 239:		Ред 239:
	</syntaxhighlight>		</syntaxhighlight>

	== 3. задатак ==		== {{категорија\|3. задатак\|Прстен}} ==
	=== Поставка ===		=== Поставка ===
	Посматра се прстен у коме сваки чвор може да прими поруку само од свог претходника и који може да пошаље поруку смо<sup>[sic]</sup> свом следбенику. Сваки чвор садржи целобројну вредност. Потребно је остварити интеракције између тих чворова користећи синхрону комуникацију да би се сазнало која је минимална а која је максимална вредност. Сваки чвор треба да сазна које су максимална и минимална вредност.		Посматра се прстен у коме сваки чвор може да прими поруку само од свог претходника и који може да пошаље поруку смо<sup>[sic]</sup> свом следбенику. Сваки чвор садржи целобројну вредност. Потребно је остварити интеракције између тих чворова користећи синхрону комуникацију да би се сазнало која је минимална а која је максимална вредност. Сваки чвор треба да сазна које су максимална и минимална вредност.
Ред 277:		Ред 277:
	</syntaxhighlight>		</syntaxhighlight>

	== 4. задатак ==		== {{категорија\|4. задатак\|C-Linda}} ==
	=== Поставка ===		=== Поставка ===
	Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, који седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између два суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када неки играч објави да има све 4 карте истог броја, у различитим бојама, и тада сви играчи прекидају игру. Сваки играч, док год нема 4 исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи C-Linda, написати изглед процедуре за једног играча. Поред играча, не постоји ниједан други процес.		Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, који седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између два суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када неки играч објави да има све 4 карте истог броја, у различитим бојама, и тада сви играчи прекидају игру. Сваки играч, док год нема 4 исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи C-Linda, написати изглед процедуре за једног играча. Поред играча, не постоји ниједан други процес.

KockaAdmiralac: Sad ne mogu dva igrača istovremeno da postave game over

2022-06-14T12:52:06Z

Sad ne mogu dva igrača istovremeno da postave game over

← Старија измена		Верзија на датум 14. јун 2022. у 14:52
Ред 286:		Ред 286:
	* <code>deck</code>: садржај једног шпила на столу		* <code>deck</code>: садржај једног шпила на столу
	* <code>game over</code>: да ли је игра готова		* <code>game over</code>: да ли је игра готова
			* <code>can set game over</code>: да ли играч може да објави да је победио (семафор око <code>game over</code>)
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	~~#include "common.h"~~

	typedef pair<int, int> Card;		typedef pair<int, int> Card;

Ред 321:		Ред 320:
	while (true) {		while (true) {
	if (hasWon(cards)) {		if (hasWon(cards)) {
	out("game over");		in("can set game over");
			if (!rdp("game over")) {
			out("game over");
			}
			out("can set game over");
	out("deck", (i + 1) % 4, Card(-1, -1));		out("deck", (i + 1) % 4, Card(-1, -1));
	break;		break;
Ред 337:		Ред 340:
	void initialize() {		void initialize() {
	// Празнимо простор торки од претходне игре		// Празнимо простор торки од претходне игре
	while (inp("deck") \|\| inp("player") \|\| inp("game over"));		while (inp("deck") \|\| inp("player") \|\| inp("game over") \|\| inp("can set game over"));
	// Вршимо насумичну расподелу шпила		// Вршимо насумичну расподелу шпила
	vector<Card> cards;		vector<Card> cards;
Ред 358:		Ред 361:
	eval(player, p);		eval(player, p);
	}		}
			out("can set game over");
	}		}
	</syntaxhighlight>		</syntaxhighlight>

KockaAdmiralac: Poslednji proces ne treba da se zablokira

2022-06-13T11:22:58Z

Poslednji proces ne treba da se zablokira

← Старија измена		Верзија на датум 13. јун 2022. у 13:22
Ред 270:		Ред 270:
	min = newPair.first;		min = newPair.first;
	max = newPair.second;		max = newPair.second;
	values[i].send({min, max});		if (i != N-1) {
			// Ако смо последњи процес не треба да шаљемо првом опет, јер неће примити
			values[i].send({min, max});
			}
	}		}
	</syntaxhighlight>		</syntaxhighlight>

KockaAdmiralac: Treći i četvrti zadatak

2022-06-12T12:48:45Z

Treći i četvrti zadatak

@@ Ред 240: / Ред 240: @@
 == 3. задатак ==
 === Поставка ===
-Посматра се прстен у коме сваки чвор може да прими поруку само од свог претходника и који може да пошаље поруку смо свом следбенику. Сваки чвор садржи целобројну вредност. Потребно је остварити интеракције између тих чворова користећи синхрону комуникацију да би се сазнало која је минимална а која је максимална вредност. Сваки чвор треба да сазна које су максимална и минимална вредност.
+Посматра се прстен у коме сваки чвор може да прими поруку само од свог претходника и који може да пошаље поруку смо<sup>[sic]</sup> свом следбенику. Сваки чвор садржи целобројну вредност. Потребно је остварити интеракције између тих чворова користећи синхрону комуникацију да би се сазнало која је минимална а која је максимална вредност. Сваки чвор треба да сазна које су максимална и минимална вредност.
 === Решење ===
 == 4. задатак ==
 === Поставка ===
 Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, који седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између два суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када неки играч објави да има све 4 карте истог броја, у различитим бојама, и тада сви играчи прекидају игру. Сваки играч, док год нема 4 исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи C-Linda, написати изглед процедуре за једног играча. Поред играча, не постоји ниједан други процес.
 === Решење ===
 [[Категорија:КДП]]
 [[Категорија:Рокови]]

KockaAdmiralac: Nema potrebe za waiting u prvom zadatku

2022-05-15T11:09:53Z

Nema potrebe za waiting u prvom zadatku

← Старија измена		Верзија на датум 15. мај 2022. у 13:09
Ред 36:		Ред 36:
	private int ticket = 0;		private int ticket = 0;
	private int id = 0;		private int id = 0;
	~~private int waiting = 0;~~
	public PrintersMonitor() {		public PrintersMonitor() {
	for (int i = 0; i < N; ++i) {		for (int i = 0; i < N; ++i) {
Ред 56:		Ред 55:
	ProcessPriority pp = new ProcessPriority(priority, myTicket, myId);		ProcessPriority pp = new ProcessPriority(priority, myTicket, myId);
	pq.push(pp);		pq.push(pp);
	~~++waiting;~~
	free[myId].wait();		free[myId].wait();
	// Одблокирао нас је неки процес који је раније држао неки штампач		// Одблокирао нас је неки процес који је раније држао неки штампач
	~~--waiting;~~
	return pp.printer;		return pp.printer;
	}		}
	public synchronized void release(int printer) {		public synchronized void release(int printer) {
	if (~~waiting == 0~~) {		if (pq.isEmpty()) {
	busy[printer] = false;		busy[printer] = false;
	} else {		} else {

KockaAdmiralac: Zapravo nešto ubaci u PQ

2022-05-14T18:42:36Z

Zapravo nešto ubaci u PQ

← Старија измена		Верзија на датум 14. мај 2022. у 20:42
Ред 55:		Ред 55:
	id = (id + 1) % N;		id = (id + 1) % N;
	ProcessPriority pp = new ProcessPriority(priority, myTicket, myId);		ProcessPriority pp = new ProcessPriority(priority, myTicket, myId);
			pq.push(pp);
	++waiting;		++waiting;
	free[myId].wait();		free[myId].wait();

KockaAdmiralac: Ne možemo da podrazumevamo FIFO raspored na Condition pa ovo mora mnogo drugačije

2022-05-14T17:49:11Z

Ne možemo da podrazumevamo FIFO raspored na Condition pa ovo mora mnogo drugačije

@@ Ред 10: / Ред 10: @@
 <syntaxhighlight lang="java">
 class PrintersMonitor {
      private boolean[] busy = new boolean[2];
-     private Condition free = new Condition();
+     private Condition[] free = new Condition[N];
      public synchronized int request(int priority) {
-         while (true) {
+         // Прво проверимо да ли има слободних штампача
-            for (int i = 0; i < 2; ++i) {
+        for (int i = 0; i < 2; ++i) {
-                if (!busy[i]) {
+            if (!busy[i]) {
-                    return i;
+                busy[i] = true;
+                 return i;
+             }
+         }
+     }
      public synchronized void release(int printer) {
-         busy[printer] = false;
+         if (waiting == 0) {
-         free.signal();
+            busy[printer] = false;
+     }
+}

KockaAdmiralac: +dve postavke

2022-05-11T10:59:16Z

+dve postavke

← Старија измена		Верзија на датум 11. мај 2022. у 12:59
Ред 200:		Ред 200:
	{{делимично решено}}		{{делимично решено}}
	=== Поставка ===		=== Поставка ===
			Посматра се прстен у коме сваки чвор може да прими поруку само од свог претходника и који може да пошаље поруку смо свом следбенику. Сваки чвор садржи целобројну вредност. Потребно је остварити интеракције између тих чворова користећи синхрону комуникацију да би се сазнало која је минимална а која је максимална вредност. Сваки чвор треба да сазна које су максимална и минимална вредност.

	=== Решење ===		=== Решење ===
Ред 206:		Ред 207:
	{{делимично решено}}		{{делимично решено}}
	=== Поставка ===		=== Поставка ===
			Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, који седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између два суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када неки играч објави да има све 4 карте истог броја, у различитим бојама, и тада сви играчи прекидају игру. Сваки играч, док год нема 4 исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи C-Linda, написати изглед процедуре за једног играча. Поред играча, не постоји ниједан други процес.

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

KockaAdmiralac: Moguća rešenja prvog i drugog zadatka

2022-05-11T10:58:29Z

Moguća rešenja prvog i drugog zadatka

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

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

== 1. задатак ==
=== Поставка ===
Потребно је да N процеса деле два штампача. Пре употребе штампача, процес P[i] позива мониторску процедуру <code>request()</code>, а процедура враћа идентификатор додељеног штампача - printer. По завршетку штампања, процес P[i] ослобађа штампач са <code>release(printer)</code>. Дефинишите мониторску инваријанту. Развити монитор који користи ''Signal and Continue'' дисциплину. Након тога, претпоставити да код процедуре <code>request</code> постоји додатни аргумент којим процес доставља приоритет захтева. Модификовати монитор, тако да се штампачи добијају у складу са приоритетом. При истом приоритету треба да важи редослед пристизања захтева - ''FCFS''.

=== Решење ===
Мониторска инваријанта, уколико je <math>N</math> број штампача, je <math>0 \leq N \leq 2</math>. Крајње модификовани монитор изгледа:
<syntaxhighlight lang="java">
class PrintersMonitor {
private boolean[] busy = new boolean[2];
private Condition free = new Condition();
public synchronized int request(int priority) {
while (true) {
for (int i = 0; i < 2; ++i) {
if (!busy[i]) {
return i;
}
}
free.wait(priority);
}
}
public synchronized void release(int printer) {
busy[printer] = false;
free.signal();
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Посматра се агенција за изнајмљивање аутомобила. У возном парку постоје 20 стандардних возила и 10 лукс возила. Приликом доласка клијента да изнајми ауто, он се изјашњава да ли жели да изнајми стандардно или лукс возило или му је све једно. Након тога он чека у реду све док му се возило не додели на коришћење. По завршетку коришћења, корисник долази још једном у агенцију и враћа ауто. У агенцији постоји један запослени који води евиденцију о томе који ауто је тренутно на коришћењу код ког корисника. Клијентима није дозвољено напуштање агенције све док запослени не обради њихов захтев за преузимање или враћање возила. Користећи регионе написати методу које се позива приликом доласка клијента да изнајми ауто, методу које се позива приликом доласка клијента да врати ауто и методу која симулира рад запосленог, као и код за иницијализацију. Потребно је обезбедити да возила не стоје на паркингу агенције, уколико постоји било који клијент који жели да изнајми тај тип возила.

=== Решење ===
<syntaxhighlight lang="cpp">
#include <map>
#include <queue>

using namespace std;

// Структуре за упућивање захтева запосленом
struct Request {
int customerId;
unsigned place;
};
enum RequestType {
STANDARD_VEHICLE,
LUXURY_VEHICLE,
ANY_VEHICLE,
RETURN_VEHICLE
};

// Монитор
struct CarDealership {
queue<Request> standardRequests;
queue<Request> luxuryRequests;
queue<Request> anyRequests;
queue<Request> returnRequests;
map<int, int> rentedCars;
int place = 1;
};
CarDealership dealership;

// Ова два реда се мењају само из запосленог, тако да не морају да буду у региону.
queue<int> standardCars;
queue<int> luxuryCars;

int rentCar(int customerId, int which) {
region (dealership) {
unsigned myPlace = dealership.place++;
switch (which) {
case STANDARD_VEHICLE:
dealership.standardRequests.push({customerId, myPlace});
break;
case LUXURY_VEHICLE:
dealership.luxuryRequests.push({customerId, myPlace});
break;
case ANY_VEHICLE:
dealership.anyRequests.push({customerId, myPlace});
break;
}
await (dealership.rentedCars[customerId]);
}
}

void returnCar(int customerId) {
region (dealership) {
unsigned myPlace = dealership.place++;
dealership.returnRequests.push({customerId, myPlace});
await (!dealership.rentedCars[customerId]);
}
}

void employee() {
while (true) {
Request req;
int request = 0;
region (dealership) {
await (
dealership.standardRequests.size() +
dealership.luxuryRequests.size() +
dealership.anyRequests.size() +
dealership.returnRequests.size() > 0
);
unsigned minPlace = -1;
if (
!dealership.standardRequests.empty() &&
!standardCars.empty() &&
dealership.standardRequests.front().place < minPlace
) {
minPlace = dealership.standardRequests.front().place;
request = STANDARD_VEHICLE;
}
if (
!dealership.luxuryRequests.empty() &&
!luxuryCars.empty() &&
dealership.luxuryRequests.front().place < minPlace
) {
minPlace = dealership.luxuryRequests.front().place;
request = LUXURY_VEHICLE;
}
if (
!dealership.anyRequests.empty() &&
(!standardCars.empty() || !luxuryCars.empty()) &&
dealership.anyRequests.front().place < minPlace
) {
minPlace = dealership.anyRequests.front().place;
request = ANY_VEHICLE;
}
if (!dealership.returnRequests.empty() && dealership.returnRequests.front().place < minPlace) {
minPlace = dealership.returnRequests.front().place;
request = RETURN_VEHICLE;
}
switch (request) {
case STANDARD_VEHICLE:
req = dealership.standardRequests.front();
dealership.standardRequests.pop();
break;
case LUXURY_VEHICLE:
req = dealership.luxuryRequests.front();
dealership.luxuryRequests.pop();
break;
case ANY_VEHICLE:
req = dealership.anyRequests.front();
dealership.anyRequests.pop();
break;
case RETURN_VEHICLE:
req = dealership.returnRequests.front();
dealership.returnRequests.pop();
break;
}
}
// Овде запослени ради неки свој посао бележења
region (dealership) {
switch (request) {
case STANDARD_VEHICLE:
dealership.rentedCars[req.customerId] = standardCars.front();
standardCars.pop();
break;
case LUXURY_VEHICLE:
dealership.rentedCars[req.customerId] = luxuryCars.front();
luxuryCars.pop();
break;
case ANY_VEHICLE:
if (standardCars.empty()) {
dealership.rentedCars[req.customerId] = luxuryCars.front();
luxuryCars.pop();
} else {
dealership.rentedCars[req.customerId] = standardCars.front();
standardCars.pop();
}
break;
case RETURN_VEHICLE:
int carId = dealership.rentedCars[req.customerId];
dealership.rentedCars[req.customerId] = 0;
if (carId > 20) {
luxuryCars.push(carId);
} else {
standardCars.push(carId);
}
break;
}
}
}
}

int main() {
for (int i = 0; i < 20; ++i) {
standardCars.push(i + 1);
}
for (int i = 0; i < 10; ++i) {
luxuryCars.push(i + 21);
}
return 0;
}
</syntaxhighlight>

== 3. задатак ==
{{делимично решено}}
=== Поставка ===

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

== 4. задатак ==
{{делимично решено}}
=== Поставка ===

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

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