КДП/Фебруар 2024 — разлика између измена

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу
(Tagovi za delimicno reseno)
 
(Једна међуизмена истог корисника није приказана)
Ред 1: Ред 1:
{{tocright}}
{{tocright}}
{{нерешено}}<!-- Ово ставити уколико НИЈЕДАН задатак није решен, док уколико само неки задаци нису решени на првом месту у њиховој секцији поставити {{делимично решено}}. Уколико се користи било који од ова два шаблона, ОБАВЕЗНО проверити да ли постоји излиставање тих рокова коришћењем {{рокови}} шаблона на страници предмета у одељку за потребну помоћ (како би се знало да нерешени рокови постоје). -->


== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
{{делимично решено}}
=== Поставка ===
=== Поставка ===
Написати и објаснити ''Test and set'' решење за критичну секцију (''coarse grain'' и ''fine grain''). Дати решење за смањење инвалидације кеш меморија у том случају.
Написати и објаснити ''Test and set'' решење за критичну секцију (''coarse grain'' и ''fine grain''). Дати решење за смањење инвалидације кеш меморија у том случају.
Ред 8: Ред 8:


== {{категорија|2. задатак|Региони}} ==
== {{категорија|2. задатак|Региони}} ==
{{делимично решено}}
=== Поставка ===
=== Поставка ===
Користећи условне критичне регионе написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Није потребно оптимизовати пут лифта и путника.
Користећи условне критичне регионе написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Није потребно оптимизовати пут лифта и путника.
Ред 18: Ред 19:
=== Решење ===
=== Решење ===
<syntaxhighlight lang="cpp">
<syntaxhighlight lang="cpp">
const int N = ...; //broj citalaca + broj pisaca
const int N; // broj citalaca + broj pisaca
chan s(int, int); //id, op
enum op_kind { START_READ, END_READ, START_WRITE, END_WRITE };
chan r[N](int, int);
chan request(int id, op_kind op);
 
chan reply[N](bool);
// 0 - start read
// 1 - end read
// 2 - start write
// 3 - end write


void reader(int id) {
void reader(int id) {
     bool status;
     bool status;
     while(true) {
     while (true) {
         send s(id, 0);
         send request(id, START_READ);
         receive r[id](status);
         receive reply[id](status);
         //read
         // read
         send s(id, 1);
         send request(id, END_READ);
        receive r[id](status);
     }
     }
}
}


void writer(int id) {
void writer(int id) {
     bool status;
     bool status;
     while(true) {
     while (true) {
         send s(id, 2);
         send request(id, START_WRITE);
         receive r[id](status);
         receive reply[id](status);
         //write
         // write
         send s(id, 3);
         send request(id, END_WRITE);
        receive r[id](status);
     }
     }
}
}


void monitor() {
void monitor() {
     int id, op, numR = 0;
     int numR = 0, numW = 0;
     queue buffer(int, int);
     queue buffer(int, int);


     while(true) {
     while (true) {
         if(buffer.isNotEmpty()) id, op = buffer.get();
        int id, op;
         else receive s(id, op);
        receive s(id, op);
 
         if (op == START_READ || op == START_WRITE) {
            buffer.push(id, op);
        }
        if (op == END_READ) numR--;
         if (op == END_WRITE) numW--;


         if(op == 0) {
         if (numW == 0 && numR == 0 && !buffer.empty()) {
            id, op = buffer.pop();
            if (op == START_READ) numR++;
            if (op == START_WRITE) numW++;
            send reply[id](true);
        }
        while (numW == 0 && !buffer.empty() && buffer.front().op == START_READ) {
            id, op = buffer.pop();
             numR++;
             numR++;
             send r[id](true);
             send reply[id](true);
        } else if(op == 1) {
            numR--;
            send r[id](true);
        } else if(op == 2) {
            int id2, op2;
            while(numR > 0) {
                receive s(id2, op2);
                if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
                else if(op2 == 1) {
                    numR--;
                    send r[id2](true);
                }
            }
            send r[id](true);
            while(true) {
                receive s(id2, op2);
                if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
                else if(op2 == 3) {
                    send r[id2](true);
                    break;
                }
            }
         }
         }
     }
     }
Ред 90: Ред 74:


== {{категорија|4. задатак|CSP}} ==
== {{категорија|4. задатак|CSP}} ==
{{делимично решено}}
=== Поставка ===
=== Поставка ===
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.
=== Решење ===
=== Решење ===


<!-- Наставити са копирањем одељака изнад уколико има још задатака. -->


[[Категорија:Рокови]]
[[Категорија:Рокови]]
[[Категорија:КДП]]
[[Категорија:КДП]]

Тренутна верзија на датум 14. септембар 2025. у 15:35

1. задатак

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

Поставка

Написати и објаснити Test and set решење за критичну секцију (coarse grain и fine grain). Дати решење за смањење инвалидације кеш меморија у том случају.

Решење

2. задатак

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

Поставка

Користећи условне критичне регионе написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Није потребно оптимизовати пут лифта и путника.

Решење

3. задатак

Поставка

Решити проблем читалаца и писаца (Readers-Writers problem) користећи активне мониторе. Обезбедити да процес који је пре упутио захтев за приступ ресурсу пре треба да буде опслужен.

Решење

const int N; // broj citalaca + broj pisaca
enum op_kind { START_READ, END_READ, START_WRITE, END_WRITE };
chan request(int id, op_kind op);
chan reply[N](bool);

void reader(int id) {
    bool status;
    while (true) {
        send request(id, START_READ);
        receive reply[id](status);
        // read
        send request(id, END_READ);
    }
}

void writer(int id) {
    bool status;
    while (true) {
        send request(id, START_WRITE);
        receive reply[id](status);
        // write
        send request(id, END_WRITE);
    }
}

void monitor() {
    int numR = 0, numW = 0;
    queue buffer(int, int);

    while (true) {
        int id, op;
        receive s(id, op);

        if (op == START_READ || op == START_WRITE) {
            buffer.push(id, op);
        }
        if (op == END_READ) numR--;
        if (op == END_WRITE) numW--;

        if (numW == 0 && numR == 0 && !buffer.empty()) {
            id, op = buffer.pop();
            if (op == START_READ) numR++;
            if (op == START_WRITE) numW++;
            send reply[id](true);
        }
        while (numW == 0 && !buffer.empty() && buffer.front().op == START_READ) {
            id, op = buffer.pop();
            numR++;
            send reply[id](true);
        }
    }
}

4. задатак

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

Поставка

Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.

Решење

Преузето из „https://siwiki.rs/w/index.php?title=КДП/Фебруар_2024&oldid=7998”