КДП/Јануар 2023
Испит у јануарском испитном року 2023. године одржан је 18. јанаура. Поставка је доступна на страници предмета.
1. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Имплементирати и објасните основну разлику и разлоге за постојање те разлике између имплементација бафера коначног капацитета (bounded buffer) за случајеве 1 произвођач и 1 потрошач, као и M произвођача и N потрошача помоћу семафора. У складу са објашњењем, прикажите разлике и за случајеве M произвођача и 1 потрошач, као и 1 произвођач и N потрошача.
Решење
// 1 произвођач и 1 потрошач
typeT buff[n];
int front = 0, rear = 0;
sem empty = n, full = 0;
// empty се користи као број празних места, а full као број попуњених места у баферу
process Producer{
while(true){
... //произведи податак
wait(empty); //чекај да бафер има празних места
buf[rear] = data; rear = (rear + 1)%n;
signal(full); //попуни једно место у баферу
...
}
}
process Consumer{
while(true){
... //потроши податак
wait(full); //чекај да бафер није празан
res = buf[front]; front = (front + 1)%n;
signal(empty); //ослободи једно место у баферу
...
}
}
//За M произвођача и N потрошача потребан нам је још један пар семафора - да се осигура да ће само један произвођач убацивати (deposit) у бафер, ерго да ће само један потрошач узимати (fetch) из бафера у било ком тренутку
typeT buff[n]; const M = ..., N = ...;
int front = 0, rear = 0;
sem empty = n, full = 0;
sem mutexD = 1, mutexF = 1; // за међусобно искључивање током deposit и fetch
process Producer[i = 1 to M]{
while(true){
... //произведи податак
wait(mutexD); wait(empty); //чекај да сам једини који убацује у бафер и да бафер има празних места
buf[rear] = data; rear = (rear + 1)%n;
signal(mutexD); signal(full); //допусти да неки други поризвођач убацује у бафер и попуни једно место у баферу
...
}
}
process Consumer[i = 1 to N]{
while(true){
... //потроши податак
wait(mutexF); wait(full);
res = buf[front]; front = (front + 1)%n;
signal(mutexF); signal(empty);
...
}
}
//За случај M произвођача и 1 потрошач није потребан семафор mutexF јер не постоји више потрошача који желе да узимају из бафера. Аналогно је за 1 произвођач и N потрошача.
2. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Аутомобили који долазе са севера и југа морају да пређу реку преко неког старог моста (Old Bridge problem). На мосту постоји само једна возна трака, па сви аутомобили на мосту морају да се крећу у истом смеру. Због оптерећења моста које мост може да поднесе, број аутомобила који се налазе на мосту не сме да пређе K (K > 0). Написати монитор са signal and continue дисциплином који решава дати проблем.
Решење
const K = ...;
monitor Bridge {
int waitingS = 0, waitingN = 0;
int cnt = 0; // тренутан број аутића на мосту
int dir = 0; // 0 - нико не чека и нико није на мосту, 1 - тренутно прелазе кола са севера, 2 - са југа
cond go;
void EnterNorth() {
waitingN++;
// Чекај ако прелазе кола са југа или ако је на мосту већ К аутића
while(dir == 2 || cnt == K) wait(go);
waitingN--; dir = 1; cnt++;
}
void ExitNorth() {
cnt--;
if(cnt == 0) { // мост је слободан
if(waitingS > 0) dir = 2; // прво проверава супротан смер и препушта мост њима ако неко чека
else if(waitingN > 0) dir = 1;
else dir = 0;
signal(go);
}
}
}
3. задатак
Поставка
Решити проблем читалаца и писаца користећи CSP. Решење треба да обезбеди да када стигне захтев од писца за тражење дозволе за започињање писања не треба прихватати захтеве за започињање било од читалаца било од писаца док тај писац не заврши са писањем.
Решење
[reader(i:1..N)::READER || writer(i:1..M)::WRITER || conductor::CONDUCTOR]
READER :: *[
conductor!request
conductor!pass
// reading
conductor!done
]
WRITER :: *[
conductor!request
conductor!pass
// writing
conductor!done
]
CONDUCTOR :: [
read_count: integer = 0
write_count: integer = 0
queue: (0..C) integer
who: (0..C) char
head: integer = 0
tail: integer = 0
*[
head == tail, write_count == 0, (i:1..N) reader(i)?request ->
reader(i)!pass
read_count++
□
head == tail, write_count == 0, read_count == 0, (i:1..M) writer(i)?request ->
writer(i)!pass
write_count++
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..N) reader(i)?request ->
queue(head) = i
who(head) = 'r'
head = (head + 1) % N
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..M) writer(i)?request ->
queue(head) = i
who(head) = 'w'
head = (head + 1) % N
□
read_count == 1, (i:1..N) reader(i)?done ->
read_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
□
read_count != 1, (i:1..N) reader(i)?done ->
read_count--
□
(i:1..M) writer(i)?done ->
write_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
]
]
4. задатак
Поставка
Трајект за превоз возила превози возила са обале на обалу. Трајект поседује M трака од којих свака има N позиција које су линеарно постављене једна иза друге. Возило заузима једну позицију. Возило приликом доласка стаје у ред за случајно изабрану траку и чека на укрцавање. Нема могућности за престројавањем. Возила улазе у своју траку једно по једно по редоследу у којем чекају у траци, док на трајекту има места. Када је пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају из своје траке у редоследу супротном од редоследа у којем су се укрцала у своју траку. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи C-Linda написати програм који решава овај проблем.