КДП/Јул 2021

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

1. задатак

Поставка

Код Tie breaker алгоритма за n процеса се догодио следећи случај – приликом извршавања кода за улазак у критичну секцију, свих n процеса су ушли у стање 1 и ниједан још није ушао у стање 2. Одговорити на следећа питања и образложити одговор:

1. Да ли процес који је први ушао у стање 1 први улази у стање 2?
2. Да ли процес који је први ушао у стање n-2 први улази у критичну секцију?
3. Да ли процес који је последњи ушао у стање 1 може да буде трећи који улази у стање 2?
4. Да ли процес који је последњи ушао у стање 1 може да буде први који улази у критичну секцију?

Решење

1. У општем случају, не мора да значи да ће процес који је први ушао у стање 1 први ући и у стање 2. Пошто се у том тренутку сви процеси налазе у стању 1, било који процес који није последњи стигао у стање 1 ће моћи да први уђе у стање 2. Специјално, у случају када је $n = 2$, процес који је први ушао у стање 1 ће гарантовано први ући у стање 2.
2. У првом стању могу да се нађу $n$ процеса, у другом стању $n-1$ процеса... том логиком у стању $n-2$ могу да се нађу 3 процеса истовремено. Један од та три процеса ће последњи ући и неће моћи да напредује, док ће остала два моћи да напредују и не гарантује се који од та два процеса ће први напредовати.
3. Процес који је последњи ушао у стање 1 ће бити последњи који ће из њега изаћи. Могуће је да он буде трећи који улази у стање 2 уколико је $n = 3$, у супротном не мора да значи.
4. Процес који је последњи ушао у стање 1 је последњи који улази у критичну секцију. Да би такође био и први, морало би да важи $n = 1$ а то нема смисла.

2. задатак

Поставка

Посматра се агенција за изнајмљивање аутомобила. У возном парку постоје M стандардних возила и N лукс возила. Приликом доласка клијента који жели да изнајми ауто, он се изјашњава да ли жели да изнајми стандардно или лукс возило или му је свеједно. Клијент чека у реду све док му се возило не додели на коришћење. По завршетку коришћења, корисник долази још једном у агенцију и враћа ауто. Потребно је обезбедити да клијенти преузимају своје аутомобиле по редоследу доласка у агенцију. Клијент има могућност да изнајми више возила, али је сваки долазак везан искључиво за позајмицу једног аутомобила. Решити проблем користећи мониторе сa signal and continue дисциплином.

Решење

class CarAgency {
    public static final STANDARD_VEHICLE = 0;
    public static final LUXURY_VEHICLE = 1;
    public static final ANY_VEHICLE = 2;
    private int standardVehicles = 100;
    private int luxuryVehicles = 10;
    private final Condition[] queues = new Condition[3];
    private int ticket = 1;
    public CarAgency() {
        for (int i = 0; i < 3; ++i) {
            queues[i] = new Condition();
        }
    }
    public synchronized void rentCar(int which) {
        int myTicket = ticket++;
        if (
            standardVehicles == 0 && which == STANDARD_VEHICLE ||
            luxuryVehicles == 0 && which == LUXURY_VEHICLE ||
            (standardVehicles == 0 && luxuryVehicles == 0)
        ) {
            // Нема возила, чекамо
            queues[which].wait(myTicket);
            // Број возила је смањен већ при сигнализирању
        } else if (which == STANDARD_VEHICLE) {
            // Желели смо стандардно возило и добили смо
            --standardVehicles;
        } else if (which == LUXURY_VEHICLE) {
            // Желели смо луксузно возило и добили смо
            --luxuryVehicles;
        } else if (standardVehicles == 0) {
            // Желели смо било које возило и добили смо луксузно
            --luxuryVehicles;
        } else {
            // Желели смо било које возило и добили смо стандардно
            --standardVehicles;
        }
    }
    public synchronized void returnCar(int which) {
        if (which == STANDARD_VEHICLE) {
            ++standardVehicles;
            boolean qStandardVehicle = queues[STANDARD_VEHICLE].queue();
            boolean qAnyVehicle = queues[ANY_VEHICLE].queue();
            if (qStandardVehicle || qAnyVehicle) {
                --standardVehicles;
            }
            if (qStandardVehicle && qAnyVehicle) {
                if (queues[STANDARD_VEHICLE].minrank() < queues[ANY_VEHICLE].minrank()) {
                    queues[STANDARD_VEHICLE].signal();
                } else {
                    queues[ANY_VEHICLE].signal();
                }
            } else if (qStandardVehicle) {
                queues[STANDARD_VEHICLE].signal();
            } else if (qAnyVehicle) {
                queues[ANY_VEHICLE].signal();
            }
        } else {
            ++luxuryVehicles;
            boolean qLuxuryVehicle = queues[LUXURY_VEHICLE].queue();
            boolean qAnyVehicle = queues[ANY_VEHICLE].queue();
            if (qLuxuryVehicle || qAnyVehicle) {
                --luxuryVehicles;
            }
            if (qLuxuryVehicle && qAnyVehicle) {
                if (queues[LUXURY_VEHICLE].minrank() < queues[ANY_VEHICLE].minrank()) {
                    queues[LUXURY_VEHICLE].signal();
                } else {
                    queues[ANY_VEHICLE].signal();
                }
            } else if (qLuxuryVehicle) {
                queues[LUXURY_VEHICLE].signal();
            } else if (qAnyVehicle) {
                queues[ANY_VEHICLE].signal();
            }
        }
    }
}

3. задатак

Поставка

У Линди реализовати лицитацију у којој постоји један процес vođa_licitacije и n процеса učesnika_u_licitaciji и један процес tick који само ажурира време. Вођа лицитације треба да иницијализује торку са почетном вредношћу и да после датог временског интервала заврши лицитацију, успешно ако је излицитирана вредност већа од резервисане вредности, неуспешно иначе. Процеси учесници у лицитацији треба да се реализују тако да се не блокирају када се заврши дата лицитација, треба да знају која је излицитирана вредност и да ли су је они поставили.

Решење

Тагови у овом решењу означавају:

• value: Тренутна вредност лицитације
• time out: Поставља се кад истекне време
• ended: Поставља се кад вођа лицитације објави крај лицитације

const int FINAL_TIME = 100;
const int INITIAL_VALUE = 50;
const int RESERVE_VALUE = 100;

int getBid();
void sleep(unsigned int seconds);

void vodjaLicitacije() {
    out("value", INITIAL_VALUE, -1);
    in("time out");
    int value;
    int user;
    in("value", &value, &user);
    out("ended", value > RESERVE_VALUE);
    out("value", value, user);
}

void ucesnikULicitaciji(int i) {
    int value;
    int user;
    int bid = getBid();
    bool success;
    in("value", &value, &user);
    if (rdp("ended") || value > bid) {
        out("value", value, user);
    } else {
        out("value", bid, i);
    }
    rd("ended", &success);
    rd("value", &value, &user);
    if (success && user == i) {
        // Ми добијамо лицитацију
    }
}

void tick() {
    int time = 0;
    while (true) {
        sleep(1);
        if (++time == FINAL_TIME) {
            out("time out");
        }
    }
}

4. задатак

Поставка

Постоји N процеса node(i:1..N) који или чувају елементе листе или су слободни. Сваки од њих може да чува неку вредност (value) и показивач на следећи елемент у листи (next). Процес head чува показивач на први елемент у листи. Приликом брисања елемента из листе процес који га представља се пребацује на почетак листе слободних процеса на који указује процес free. Процес start иницира брисање елемента са задатом вредношћу из листе. Реализовати процедуре за све наведене процесе користећи CSP.

Решење

[node(i: 1..N)::NODE, head::HEAD, free::FREE, start::START]

NODE::
    value: integer;
    next: integer;
    free: boolean;
    free := true;
    [
        num = N -> next := 0
        □
        num <> N -> next := num + 1
    ];
    *[
        free = true; start?get -> start!value(value, next)
        □
        free = false; start?get -> start!novalue
        □
        start?setNext(newNext) -> next := newNext
        □
        start?erase(newNext) -> free := true
        // Акција постављања вредности није имплементирана
        // јер није ни тражена у задатку
    ]

HEAD::
    first: integer;
    first := 0;
    *[
        first = 0; start?get -> start!empty
        □
        first <> 0; start?get -> start!first(first)
        □
        start?set(value) -> first := value
    ]

FREE::
    free: integer;
    free := 1;
    *[
        free = 0; start?get -> start!full
        □
        free <> 0; start?get -> start!free(free)
        □
        start?set(newFree) -> free := newFree
    ]

START::
    // Претпоставимо да је задата вредност 14
    value: integer;
    value := 14;
    prev: integer;
    prev := 0;
    head!get;
    *[
        // Вредност не постоји у листи
        head?empty -> skip
        □
        head?first(first) -> node(first)!get
        □
        // Десила се нека грешка
        (i: 1..N) node(i)?novalue -> skip
        □
        (i: 1..N) node(i)?value(nodeValue, next) -> [
            nodeValue = value ->
                [
                    prev = 0 -> head!set(next)
                    □
                    prev <> 0 -> node(prev)!setNext(next)
                ];
                node(i)!erase;
                free!get;
                [
                    free?full -> node(i)!setNext(0)
                    □
                    free?free(nextFree) -> node(i)!setNext(nextFree)
                ];
                free!set(i)
            □
            nodeValue <> value -> [
                // Вредност не постоји у листи
                next = 0 -> skip
                □
                next <> 0 -> node(next)!get
            ]
        ]
    ]