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

Fedja: kategorije zadataka

2023-02-11T03:01:11Z

kategorije zadataka

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

	== 1. задатак ==		== {{категорија\|1. задатак\|Монитори}} ==
	{{делимично решено}}		{{делимично решено}}
	=== Поставка ===		=== Поставка ===
Ред 9:		Ред 9:
	=== Решење ===		=== Решење ===

	== 2. задатак ==		== {{категорија\|2. задатак\|Семафори}} ==
	=== Поставка ===		=== Поставка ===
	Рачун у банци може да дели више корисника (''The Savings Account Problem''). Сваки корисник може да уплаћује и подиже новац са рачуна под условом да салдо на том рачуну никада не буде негативан. Уколико на рачуну нема довољно новца, корисник треба да чека док неко други не уплати новац на тај рачун. Ниједан корисник не може бити исплаћен док год сви који су пре њега тражили исплату не добију свој новац. Решити проблем користећи семафоре (не треба проверавати да ли корисник сме да приступи неком рачуну; у банци може постојати више рачуна).		Рачун у банци може да дели више корисника (''The Savings Account Problem''). Сваки корисник може да уплаћује и подиже новац са рачуна под условом да салдо на том рачуну никада не буде негативан. Уколико на рачуну нема довољно новца, корисник треба да чека док неко други не уплати новац на тај рачун. Ниједан корисник не може бити исплаћен док год сви који су пре њега тражили исплату не добију свој новац. Решити проблем користећи семафоре (не треба проверавати да ли корисник сме да приступи неком рачуну; у банци може постојати више рачуна).
Ред 76:		Ред 76:
	</syntaxhighlight>		</syntaxhighlight>

	== 3. задатак ==		== {{категорија\|3. задатак\|C-Linda}} ==
	=== Поставка ===		=== Поставка ===
	Користећи ''C-Linda'' библииотеку решити проблем берберина који спава (''The Sleeping Barber Problem''). Берберница се састоји од чекаонице са n=5 столица и берберске столице на којој се људи брију. Уколико нема муштерија, брица спава. Уколико муштерија уђе у берберницу и све столице су заузете, муштерија не чека, већ одмах излази. Уколико је берберин зaузет, а има слободних столица, муштерија седа и чека да дође на ред. Уколико берберин спава, муштерија га буди.		Користећи ''C-Linda'' библииотеку решити проблем берберина који спава (''The Sleeping Barber Problem''). Берберница се састоји од чекаонице са n=5 столица и берберске столице на којој се људи брију. Уколико нема муштерија, брица спава. Уколико муштерија уђе у берберницу и све столице су заузете, муштерија не чека, већ одмах излази. Уколико је берберин зaузет, а има слободних столица, муштерија седа и чека да дође на ред. Уколико берберин спава, муштерија га буди.
Ред 138:		Ред 138:
	</syntaxhighlight>		</syntaxhighlight>

	== 4. задатак ==		== {{категорија\|4. задатак\|CSP}} ==
	=== Поставка ===		=== Поставка ===
	Аутомобили који долазе са севера и југа морају да пређу реку преко моста (''One lane bridge problem''). На мосту, на жалост, постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Користећи CSP написати програм који решава дати проблем. Спречити изгладњивање.		Аутомобили који долазе са севера и југа морају да пређу реку преко моста (''One lane bridge problem''). На мосту, на жалост, постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Користећи CSP написати програм који решава дати проблем. Спречити изгладњивање.

Fedja: Поништена измена бр. 5549 корисника Fedja (разговор)

2023-02-11T00:25:34Z

Поништена измена бр. 5549 корисника Fedja (разговор)

Прикажи измене

Fedja: feb2023, rešenje kačim kad dobijem rezultat

2023-02-11T00:23:49Z

feb2023, rešenje kačim kad dobijem rezultat

Прикажи измене

KockaAdmiralac: Objašnjenje tagova izbačeno van komentara

2022-06-12T10:48:37Z

Objašnjenje tagova izbačeno van komentara

@@ Ред 81: / Ред 81: @@
 === Решење ===
 <syntaxhighlight lang="cpp">
 const int N = 5;
 void barber() {

KockaAdmiralac: Treći i četvrti

2022-06-11T23:23:44Z

Treći i četvrti

Прикажи измене

KockaAdmiralac: Semafori za korisnike su po nalogu, parametar za ID korisnika se ne koristi

2022-04-01T11:53:28Z

Semafori za korisnike su po nalogu, parametar za ID korisnika se ne koristi

← Старија измена		Верзија на датум 1. април 2022. у 13:53
Ред 16:		Ред 16:
	У решењу се сматра да сваки корисник ради у само једној нити, да свака нит има свој идентификатор, и да се тај идентификатор прослеђује функцијама за уплаћивање и подизање новца.		У решењу се сматра да сваки корисник ради у само једној нити, да свака нит има свој идентификатор, и да се тај идентификатор прослеђује функцијама за уплаћивање и подизање новца.
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
			#include "common.h"

			const int NumOfAccounts = 100;
			const int NumOfUsers = 100;

	struct Account {		struct Account {
	int balance;		int balance;
Ред 22:		Ред 27:
	sem mutex = 1;		sem mutex = 1;
	sem balanceSem = 0;		sem balanceSem = 0;
			sem users[NumOfUsers] = {1, 0, 0, ...};
	};		};

	~~const int NumOfAccounts = 100;~~
	~~const int NumOfUsers = 100;~~
	Account accounts[NumOfAccounts];		Account accounts[NumOfAccounts];
	~~sem users[NumOfUsers] = {1, 0, 0, ...};~~

	void deposit(int amount, int accountId~~, int userId~~) {		void deposit(int amount, int accountId) {
	Account& account = accounts[accountId];		Account& account = accounts[accountId];
	account.mutex.wait();		account.mutex.wait();
Ред 44:		Ред 47:
	}		}

	void withdraw(int amount, int accountId~~, int userId~~) {		void withdraw(int amount, int accountId) {
	Account& account = accounts[accountId];		Account& account = accounts[accountId];
	// Дохватамо наше место у реду чекања за исплату.		// Дохватамо наше место у реду чекања за исплату.
Ред 53:		Ред 56:

	// Чекамо да нас претходни корисник у реду чекања прозове.		// Чекамо да нас претходни корисник у реду чекања прозове.
	users[ticket].wait();		account.users[ticket].wait();

	// Чекамо да се ослободи довољно средстава пре исплате.		// Чекамо да се ослободи довољно средстава пре исплате.
Ред 69:		Ред 72:

	// Јави следећем кориснику да може да изврши исплату.		// Јави следећем кориснику да може да изврши исплату.
	users[(ticket + 1) % NumOfUsers].signal();		account.users[(ticket + 1) % NumOfUsers].signal();
	}		}
	</syntaxhighlight>		</syntaxhighlight>

KockaAdmiralac: Moguće rešenje drugog zadatka

2022-03-23T19:53:28Z

Moguće rešenje drugog zadatka

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

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

== 1. задатак ==
{{делимично решено}}
=== Поставка ===
Реализовати монитор са ''Signal and Continue'' дисциплином за приступ ресурсима. Процеси који позивају мониторске процедуре могу да резервишу до две инстанце ресурса. Укупно иницијално постоје три слободне инстанце ресурса. Процеси приликом позива мониторске процедуре за заузимање ресурса дефинишу приоритет захтева као висок или нормалан. Када неки процес ослобађа две инстанце ресурса, а постоје процеси који су на чекању и који траже две инстанце ресурса, ти процеси увек имају предност у односу на процесе који су на чекању и траже један ресурс. Спречити изгладњивање.

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

== 2. задатак ==
=== Поставка ===
Рачун у банци може да дели више корисника (''The Savings Account Problem''). Сваки корисник може да уплаћује и подиже новац са рачуна под условом да салдо на том рачуну никада не буде негативан. Уколико на рачуну нема довољно новца, корисник треба да чека док неко други не уплати новац на тај рачун. Ниједан корисник не може бити исплаћен док год сви који су пре њега тражили исплату не добију свој новац. Решити проблем користећи семафоре (не треба проверавати да ли корисник сме да приступи неком рачуну; у банци може постојати више рачуна).

=== Решење ===
У решењу се сматра да сваки корисник ради у само једној нити, да свака нит има свој идентификатор, и да се тај идентификатор прослеђује функцијама за уплаћивање и подизање новца.
<syntaxhighlight lang="cpp">
struct Account {
int balance;
int maxTicket = 0;
int waitUntilAbove = 0;
sem mutex = 1;
sem balanceSem = 0;
};

const int NumOfAccounts = 100;
const int NumOfUsers = 100;
Account accounts[NumOfAccounts];
sem users[NumOfUsers] = {1, 0, 0, ...};

void deposit(int amount, int accountId, int userId) {
Account& account = accounts[accountId];
account.mutex.wait();
// Уплаћујемо паре на рачун.
account.balance += amount;
// Уколико је неки други корисник захтевао исплату, проверавамо да ли може бити задовољена.
if (account.waitUntilAbove != 0 && account.balance >= account.waitUntilAbove) {
// Уколико јесте, на нама је да ажурирамо стање.
account.balance -= account.waitUntilAbove;
account.waitUntilAbove = 0;
account.balanceSem.signal();
}
account.mutex.signal();
}

void withdraw(int amount, int accountId, int userId) {
Account& account = accounts[accountId];
// Дохватамо наше место у реду чекања за исплату.
account.mutex.wait();
// Рачуна се на то да неће један корисник истовремено радити две исплате са истог налога.
int ticket = (account.maxTicket++) % NumOfUsers;
account.mutex.signal();

// Чекамо да нас претходни корисник у реду чекања прозове.
users[ticket].wait();

// Чекамо да се ослободи довољно средстава пре исплате.
account.mutex.wait();
if (account.balance >= amount) {
// Уколико већ има довољно средстава, ажурирамо стање.
account.balance -= amount;
account.mutex.signal();
} else {
// Уколико нема, остављамо следећем кориснику који уплаћује да ажурира стање и обавести нас.
account.waitUntilAbove = amount;
account.mutex.signal();
account.balanceSem.wait();
}

// Јави следећем кориснику да може да изврши исплату.
users[(ticket + 1) % NumOfUsers].signal();
}
</syntaxhighlight>

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Користећи ''C-Linda'' библииотеку решити проблем берберина који спава (''The Sleeping Barber Problem''). Берберница се састоји од чекаонице са n=5 столица и берберске столице на којој се људи брију. Уколико нема муштерија, брица спава. Уколико муштерија уђе у берберницу и све столице су заузете, муштерија не чека, већ одмах излази. Уколико је берберин зaузет, а има слободних столица, муштерија седа и чека да дође на ред. Уколико берберин спава, муштерија га буди.

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

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко моста (''One lane bridge problem''). На мосту, на жалост, постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Користећи CSP написати програм који решава дати проблем. Спречити изгладњивање.

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

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