KDP/Januar 2023

Ispit u januarskom ispitnom roku 2023. godine održan je 18. janaura. Postavka je dostupna na stranici predmeta.

1. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Implementirati i objasnite osnovnu razliku i razloge za postojanje te razlike između implementacija bafera konačnog kapaciteta (bounded buffer) za slučajeve 1 proizvođač i 1 potrošač, kao i M proizvođača i N potrošača pomoću semafora. U skladu sa objašnjenjem, prikažite razlike i za slučajeve M proizvođača i 1 potrošač, kao i 1 proizvođač i N potrošača.

Rešenje

// 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. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Automobili koji dolaze sa severa i juga moraju da pređu reku preko nekog starog mosta (Old Bridge problem). Na mostu postoji samo jedna vozna traka, pa svi automobili na mostu moraju da se kreću u istom smeru. Zbog opterećenja mosta koje most može da podnese, broj automobila koji se nalaze na mostu ne sme da pređe K (K > 0). Napisati monitor sa signal and continue disciplinom koji rešava dati problem.

3. zadatak

Postavka

Rešiti problem čitalaca i pisaca koristeći CSP. Rešenje treba da obezbedi da kada stigne zahtev od pisca za traženje dozvole za započinjanje pisanja ne treba prihvatati zahteve za započinjanje bilo od čitalaca bilo od pisaca dok taj pisac ne završi sa pisanjem.

Rešenje

[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. zadatak

Postavka

Trajekt za prevoz vozila prevozi vozila sa obale na obalu. Trajekt poseduje M traka od kojih svaka ima N pozicija koje su linearno postavljene jedna iza druge. Vozilo zauzima jednu poziciju. Vozilo prilikom dolaska staje u red za slučajno izabranu traku i čeka na ukrcavanje. Nema mogućnosti za prestrojavanjem. Vozila ulaze u svoju traku jedno po jedno po redosledu u kojem čekaju u traci, dok na trajektu ima mesta. Kada je pun, trajekt započinje prevoz vozila na drugu obalu. Na drugoj obali vozila se iskrcavaju iz svoje trake u redosledu suprotnom od redosleda u kojem su se ukrcala u svoju traku. Kada se sva vozila iskrcaju, prazan trajekt se vraća na početnu obalu. Koristeći C-Linda napisati program koji rešava ovaj problem.