КДП/К2 2022

Други колоквијум 2022. године одржан је 15. маја.

1. задатак

Поставка

Решити проблем Читалаца и писаца (Readers/Writers) користећи мониторе са дисциплином Signal and Continue. Проблем решити користећи технику прослеђивања услова (Passing the Condition). Монитор треба да поседује 4 методе: lockShared() — желим да читам, lockExclusive() — желим да пишем, unlock() — завршавам, и upgradeLock() — са читања прелазим на писање.

Решење

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. задатак

Поставка

На обали реке се налази чамац који може да прими тачно десет путника. Чамац могу да користе мушкарци, жене и деца. Чамац може да исплови само ако се у њему налази тачно онолико путника колики му је капацитет, али само под условом да се у чамцу налазе бар два мушкарца. Деца не смеју ући у чамац уколико се у њему не налазе бар једна одрасла особа и по завршетку вожње у чамцу не смеју да остану само деца. Сматрати да ће се^[sic] чамац након искрцавања свих путника одмах бити спреман да прими наредну групу путника. Користећи регионе написати програм који решава овај проблем.

Решење

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 >= 2) {
                ++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 >= 2 && boat.adults() > 0) {
                ++boat.children;
                break;
            } else {
                // Нисмо се укрцали, чекамо да се заврши вожња па поново
                await (boat.done);
            }
        }
    }
    // Укрцани смо
    region (boat) {
        await (boat.done);
        --boat.children;
    }
}