КДП/Јануар 2021

Поставка овог рока може се наћи са странице предмета.

1. задатак

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

Потребно је реализовати тајмер користећи приватне семафоре и технику предаје штафетне палице. Тајмер има две методе, прва је метода wakeme која омогућава да се дата нит блокирана n јединица времена (ово је аргумент), а друга је метода tick која означава да је истекла једна јединица времена.

2. задатак

Поставка

Постоји тоалет капацитета N (N > 1) који могу да користе жене, мушкарци, деца и домар (Single Bathroom Problem) такав да важе следећа правила коришћења: у исто време у тоалету не могу наћи и жене и мушкарци; деца могу да деле тоалет и са женама и са мушкарцима; дете може да се нађе у тоалету само ако се тамо налази барем једна жена или мушкарац; домар има ексклузивно право коришћења тоалета. Написати монитор са signal and wait дисциплином који решава дати проблем, као и главне програме за мушкарце, жене, децу и домаре, кроз које су дати примери коришћења мониторских процедура.

Решење

class SingleBathroomProblem {
    public static final int capacity = 10;
    private int count = 0;
    // Група која је тренутно у тоалету
    // -1 - нема никога, 0 - мушкарци, 1 - жене, 2 - домар
    private int group = -1;
    private final Condition queue = new Condition();
    private int ticket = 1;
    public synchronized void enterMan() {
        int myTicket = ticket++;
        if (count == capacity || group == 1 || group == 2 || queue.queue()) {
            // Пун тоалет, у њему су жене/домар или има других особа испред тоалета
            queue.wait(myTicket * 3);
        }
        ++count;
        if (group == -1) {
            // Означавамо да је тренутно активна група мушкараца
            group = 0;
        }
        if (count != capacity && queue.queue() && queue.minrank() % 3 == group) {
            // Ако је и следећа особа мушкарац, пусти га
            queue.signal();
        }
    }
    public synchronized void enterWoman() {
        int myTicket = ticket++;
        if (count == capacity || group == 0 || group == 2 || queue.queue()) {
            // Пун тоалет или су у њему мушкарци/домар
            queue.wait(myTicket * 3 + 1);
        }
        ++count;
        if (group == -1) {
            // Означавамо да је тренутно активна група жена
            group = 1;
        }
        if (count != capacity && queue.queue() && queue.minrank() % 3 == group) {
            // Ако је и следећа особа жена, пусти је
            queue.signal();
        }
    }
    public synchronized void enterJanitor() {
        int myTicket = ticket++;
        if (group != -1) {
            // У тоалету или испред тоалета има било кога
            queue.wait(myTicket * 3 + 2);
        }
        ++count;
        if (group == -1) {
            // Означавамо да је домар тренутно у тоалету
            group = 2;
        }
    }
    public synchronized void exitMan() {
        --count;
        if (count == 0) {
            // Нема више никог у тоалету, пусти следећу особу ако је има
            group = -1;
            if (queue.queue()) {
                queue.signal();
            }
        } else if (queue.queue() && queue.minrank() % 3 == group) {
            // Има још неког у тоалету, пусти само ако је мушкарац
            queue.signal();
        }
    }
    public synchronized void exitWoman() {
        --count;
        if (count == 0) {
            // Нема више никог у тоалету, пусти следећу особу ако је има
            group = -1;
            if (queue.queue()) {
                queue.signal();
            }
        } else if (queue.queue() && queue.minrank() % 3 == group) {
            // Има још неког у тоалету, пусти само ако је жена
            queue.signal();
        }
    }
    public synchronized void exitJanitor() {
        --count;
        // Сигурно нема више никог у тоалету
        if (queue.queue()) {
            queue.signal();
        }
    }
}

3. задатак

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

Реализујте coarse grain ticket алгоритам за улазак у критичну секцију користећи CSP.

4. задатак

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

На уласку у једну железничку станицу са једном улазном пругом и једним слепим колосеком десио се квар, па се на улазу направила колона међународних и домаћих возова. Квар је отклоњен и треба пуштати возове. Да би међународни возови мање каснили, они се пуштају први, по редоследу доласка. Пошто постоји само једна пруга и возови се не могу „претицати”, сви домаћи возови који су били испред међународних у колони се пребацују на слепи колосек који је довољно велики да сви возови могу да стану. Када сви међународни возови оду, пуштају се прво возови са слепог колосека, па онда преостали домаћи возови из колоне. Сама станица има N перона, тј. N возова истовремено могу да укрцавају и искрцавају путнике. Возови који у међувремену пристижу треба да буду опслужени, али новопристигли међународни немају приоритет у односу на возове који су испред њих у колони. Решити проблем користећи C-Linda. Написати потребну иницијализацију која осликава стање након отклањања квара. Водити рачуна о томе да су композиције возова тешке и да је потребно време да се воз помери са једног места на друго.