КДП/Јануар 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;
    private int childCount = 0;
    // Група која је тренутно у тоалету
    // -1 - нема никога, 0 - мушкарци, 1 - жене, 2 - домар
    private int group = -1;
    private final Condition queue = new Condition();
    private final Condition childrenQueue = new Condition();
    private final Condition waitingForChildren = new Condition();
    private int ticket = 1;
    private void signalPersonOrChild() {
        boolean personWaiting = queue.queue() && queue.minrank() % 3 == group;
        boolean childWaiting = childrenQueue.queue();
        if (personWaiting && childWaiting) {
            if (queue.minrank() > childrenQueue.minrank() * 3) {
                // Одрасла особа је стигла пре детета
                queue.signal();
            } else {
                // Дете је стигло пре одрасле особе
                childrenQueue.signal();
            }
        } else if (personWaiting) {
            queue.signal();
        } else if (childWaiting) {
            childrenQueue.signal();
        }
    }
    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;
        } else if (waitingForChildren.queue()) {
            // Ако има мушкарца који чека децу јавља му се да не мора више да чека
            waitingForChildren.signal();
        }
        if (count != capacity) {
            signalPersonOrChild();
        }
    }
    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;
        } else if (waitingForChildren.queue()) {
            // Ако има жена која чека децу јавља јој се да не мора више да чека
            waitingForChildren.signal();
        }
        if (count != capacity) {
            signalPersonOrChild();
        }
    }
    public synchronized void enterJanitor() {
        int myTicket = ticket++;
        if (group != -1) {
            // У тоалету или испред тоалета има било кога
            queue.wait(myTicket * 3 + 2);
        }
        ++count;
        // Означавамо да је домар тренутно у тоалету
        group = 2;
    }
    public synchronized void enterChild() {
        int myTicket = ticket++;
        if (count == capacity || group == 2 || group == -1 || queue.queue() || childrenQueue.queue() || waitingForChildren.queue()) {
            // Пун тоалет, у њему нема никога, у њему је домар, има других особа
            // испред тоалета или има особа која је унутра и чека да деца изађу
            childrenQueue.wait(myTicket);
        }
        ++count;
        ++childCount;
        if (count != capacity) {
            signalPersonOrChild();
        }
    }
    public synchronized void exitMan() {
        if (count == childCount + 1) {
            // Мушкарац не може да изађе док су деца сама у тоалету
            waitingForChildren.wait();
        }
        --count;
        if (count == 0) {
            // Нема више никог у тоалету, пусти следећу одраслу особу ако је има
            group = -1;
            if (queue.queue()) {
                queue.signal();
            }
        } else {
            signalPersonOrChild();
        }
    }
    public synchronized void exitWoman() {
        if (count == childCount + 1) {
            // Жена не може да изађе док су деца сама у тоалету
            waitingForChildren.wait();
        }
        --count;
        if (count == 0) {
            // Нема више никог у тоалету, пусти следећу одраслу особу ако је има
            group = -1;
            if (queue.queue()) {
                queue.signal();
            }
        } else  {
            signalPersonOrChild();
        }
    }
    public synchronized void exitJanitor() {
        --count;
        // Сигурно нема више никог у тоалету
        group = -1;
        if (queue.queue()) {
            queue.signal();
        }
    }
    public synchronized void exitChild() {
        --count;
        --childCount;
        if (waitingForChildren.queue() && childCount == 0) {
            // Јави особи која чека на излазак детета да су сва деца изашла
            waitingForChildren.signal();
        }
        if (count == 0) {
            // Нема више никог у тоалету, пусти следећу одраслу особу ако је има
            group = -1;
            if (queue.queue()) {
                queue.signal();
            }
        } else {
            signalPersonOrChild();
        }
    }
}

3. задатак

Поставка

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

Решење

Није јасно на шта се мисли под coarse grain реализацијом у овом случају, али је испод једна могућа имплементација ticket алгоритма за улазак у критичну секцију користећи CSP.

[ticket::TICKET || user(i: 1..N)::USER]

TICKET::
    users: (1..N) integer;
    head: integer;
    tail: integer;
    head := 0;
    tail := 0;
    *[
        head == tail; (i: 1..N) user(i)?enter ->
            // Нема никога, па пуштамо овог корисника
            user(i)!pass;
            tail := (tail + 1) mod N
        □
        head <> tail; (i: 1..N) user(i)?enter ->
            // Додајемо корисника у ред чекања
            users(tail) := i;
            tail := (tail + 1) mod N
        □
        (i: 1..N) user(i)?exit ->
            head := (head + 1) mod N;
            [
                // Пуштамо следећег корисника, уколико га има
                users(head) <> 0 ->
                    user(users(head))!pass;
                    users(head) := 0
            ]
        □
    ]

USER::
    ticket!enter;
    // У критичној секцији
    ticket!exit

4. задатак

Поставка

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

Решење

Следећи тагови су коришћени током реализације:

• ticket: редослед воза по пристизању
• current: воз који тренутно окупира улаз (било да излази из улаза и иде у слепи колосек, излази из улаза и иде на станицу или излази из слепог колосека и иде на станицу)
• sidetrack: возови који се налазе у слепом колосеку, прва вредност је редослед у слепом колосеку а друга редослед пристизања воза
• sidetrackHead: први воз који следећи треба да изађе из слепог колосека, по редоследу у слепом колосеку
• sidetrackTail: број возова у слепом колосеку
• station: возови који су тренутно на једном од регуларних N колосека

Начин на који је у овом решењу било одређено да ли је воз пристигао током квара или после је провера да ли је његов редослед пристизања већи или једнак константи M, што је број возова који су пристигли током квара. Након почетне иницијализације стања након поправљања квара очекује се да новопристигли возови сами направе train процес.

const int N = 10;
const int M = 100;

void setCurrentFromSidetrack() {
    int sidetrackTicket;
    int sidetrackHead;
    in("sidetrackHead", &sidetrackHead);
    in("sidetrack", sidetrackHead, &sidetrackTicket);
    out("sidetrackHead", sidetrackHead + 1);
    out("current", sidetrackTicket);
}

void train(bool isInternational) {
    int ticket;
    in("ticket", &ticket);
    out("ticket", ticket + 1);
    in("current", ticket);
    bool arrivedLater = ticket >= M;
    bool isSidetrack = !isInternational && !arrivedLater;
    if (isSidetrack) {
        // Прво идемо у слепи колосек
        int sidetrackTail;
        in("sidetrackTail", &sidetrackTail);
        out("sidetrack", sidetrackTail, ticket);
        out("sidetrackTail", sidetrackTail + 1);
        if (ticket == M - 1) {
            // Ми смо последњи воз који је стигао током квара,
            // треба да предамо првом из слепог колосека
            setCurrentFromSidetrack();
            in("current", ticket);
        } else {
            // Предајемо следећем возу који је стигао током квара
            out("current", ticket + 1);
            in("current", ticket);
        }
    }
    int station;
    in("station", &station);
    // Идемо на станицу, па чим ослободимо улаз пуштамо следећег
    if (isSidetrack) {
        if (rdp("sidetrack")) {
            // Пуштамо следећег из слепог колосека
            setCurrentFromSidetrack();
        } else {
            // Нема више никог из слепог колосека, пуштамо обичну колону
            out("current", M);
        }
    } else {
        if (ticket == M - 1) {
            // Ми смо последњи воз који је стигао током квара,
            // треба да предамо возовима из слепог колосека, уколико постоје
            if (rdp("sidetrack")) {
                setCurrentFromSidetrack();
            } else {
                // Нико није ушао у слепи колосек
                out("current", ticket + 1);
            }
        } else {
            // Пуштамо следећи воз, пошто још увек колона која је стигла
            // током квара није изашла из улаза
            out("current", ticket + 1);
        }
    }
    // Одлазимо са станице
    out("station", station);
}

void initialize() {
    out("ticket", 0);
    for (int i = 0; i < M; ++i) {
        eval(train, rand() % 2 == 1);
        // Чекамо да воз покупи свој ticket
        rd("ticket", i + 1);
    }
    for (int i = 0; i < N; ++i) {
        out("station", i);
    }
    out("current", 0);
    out("sidetrackHead", 0);
    out("sidetrackTail", 0);
}