KDP/K2 2022

Drugi kolokvijum 2022. godine održan je 15. maja.

1. zadatak

Postavka

Rešiti problem Čitalaca i pisaca (Readers/Writers) koristeći monitore sa disciplinom Signal and Continue. Problem rešiti koristeći tehniku prosleđivanja uslova (Passing the Condition). Monitor treba da poseduje 4 metode: lockShared() — želim da čitam, lockExclusive() — želim da pišem, unlock() — završavam, i upgradeLock() — sa čitanja prelazim na pisanje.

Rešenje

class ReadersWriters {
    private int readers = 0;
    private int writers = 0;
    private int ticket = 1;
    private Condition okToRead = new Condition();
    private Condition okToWrite = new Condition();
    public synchronized void lockShared() {
        if (writers == 0 && okToWrite.empty()) {
            ++readers;
        } else {
            okToRead.wait(ticket++);
        }
    }
    public synchronized void lockExclusive() {
        if (readers == 0 && writers == 0) {
            ++writers;
        } else {
            okToWrite.wait(ticket++);
        }
    }
    public synchronized void unlock() {
        if (readers > 0) {
            if (--readers == 0 && okToWrite.queue()) {
                writers = 1;
                okToWrite.signal();
            }
        } else {
            boolean readersNext = okToRead.queue() && (okToWrite.empty() || okToRead.minrank() < okToWrite.minrank());
            boolean writersNext = okToWrite.queue() && (okToRead.empty() || okToWrite.minrank() < okToRead.minrank());
            if (readersNext) {
                while (okToRead.queue() && okToRead.minrank() < okToWrite.minrank()) {
                    ++readers;
                    okToRead.signal();
                }
            } else if (writersNext) {
                okToWrite.signal();
            } else {
                writers = 0;
            }
        }
    }
    public synchronized void upgradeLock() {
        if (readers == 1) {
            // Ако је само један читалац, конвертуј га у писца
            readers = 0;
            writers = 1;
        } else {
            // У супротном, мораће да сачека остале читаоце и писце како би постао писац
            unlock();
            lockExclusive();
        }
    }
}

2. zadatak

Postavka

Na obali reke se nalazi čamac koji može da primi tačno deset putnika. Čamac mogu da koriste muškarci, žene i deca. Čamac može da isplovi samo ako se u njemu nalazi tačno onoliko putnika koliki mu je kapacitet, ali samo pod uslovom da se u čamcu nalaze bar dva muškarca. Deca ne smeju ući u čamac ukoliko se u njemu ne nalaze bar jedna odrasla osoba i po završetku vožnje u čamcu ne smeju da ostanu samo deca. Smatrati da će se^[sic] čamac nakon iskrcavanja svih putnika odmah biti spreman da primi narednu grupu putnika. Koristeći regione napisati program koji rešava ovaj problem.

Rešenje

struct Boat {
    // Број мушкараца, жена и деце
    int men = 0;
    int women = 0;
    int children = 0;
    // Да ли је вожња готова (да ли је у току искрцавање)
    bool done;
    // Помоћне методе
    int total() {
        return men + women + children;
    }
    int adults() {
        return men + women;
    }
};
Boat boat;

void boatP() {
    while (true) {
        region (boat) {
            boat.done = false;
            await (boat.total() == 10 && boat.men >= 2);
        }
        // Вожња
        region (boat) {
            boat.done = true;
            await (boat.total() == 0);
        }
    }
}

void man() {
    while (true) {
        region (boat) {
            await (!boat.done);
            if (boat.total() < 10) {
                ++boat.men;
                break;
            } else {
                // Нисмо се укрцали, чекамо да се заврши вожња па поново
                await (boat.done);
            }
        }
    }
    // Укрцани смо
    region (boat) {
        await (boat.done);
        // Ако смо последњи одрасли, чекамо да сва деца изађу
        if (boat.adults() == 1 && boat.children > 0) {
            await (boat.children == 0);
        }
        --boat.men;
    }
}

void woman() {
    while (true) {
        region (boat) {
            await (!boat.done);
            if (boat.total() < 10 && boat.total() - boat.men <= 7) {
                ++boat.women;
                break;
            } else {
                // Нисмо се укрцали, чекамо да се заврши вожња па поново
                await (boat.done);
            }
        }
    }
    // Укрцани смо
    region (boat) {
        await (boat.done);
        // Ако смо последњи одрасли, чекамо да сва деца изађу
        if (boat.adults() == 1 && boat.children > 0) {
            await (boat.children == 0);
        }
        --boat.women;
    }
}

void child() {
    while (true) {
        region (boat) {
            await (!boat.done);
            if (boat.total() < 10 && boat.total() - boat.men <= 7 && boat.adults() > 0) {
                ++boat.children;
                break;
            } else {
                // Нисмо се укрцали, чекамо да се заврши вожња па поново
                await (boat.done);
            }
        }
    }
    // Укрцани смо
    region (boat) {
        await (boat.done);
        --boat.children;
    }
}