База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C

Планиране с round-robin

Планирането с round-robin разпределя процесорно време поред на готовите задачи, за не повече от един времеви квант на задача. Примерът на C симулира тази политика и изчислява времето за изчакване и времето за оборот при изрично зададен ред на пристигане.

Версия: C23; repository compiler flag, production runtime not attested

Синтаксис

slice = min(remaining, quantum); turnaround = completion - arrival; waiting = turnaround - burst

Планирането с round-robin (RR) обслужва опашка от готови задачи. Задачата в началото се изпълнява най-много един quantum, тоест положителен времеви интервал. Ако все още е готова и не е завършила, тя се премества в края на опашката; завършените задачи я напускат, а блокираните чакат извън опашката на готовите. По-краткият quantum подобрява отзивчивостта, но увеличава разходите за превключване; RR по принцип не минимизира средното време за оборот.

Редът на пристигане изисква изрично правило: новите задачи се добавят в края на опашката, а равенствата се разрешават детерминистично. Пристигането по време на quantum само по себе си не прекъсва интервала. На границите на quantum трябва да се уточни дали първо се обработват новите пристигания или повторното включване на текущата задача. Тук всички задачи пристигат в момент 0 в ред P1, P2, P3; цикличното обхождане на масива е достатъчно само за това опростяване.

Времето за оборот е completion - arrival. Времето за изчакване обхваща общото време в опашката на готовите задачи, а не само чакането преди първото изпълнение. В приетия модел без входно-изходни операции и допълнителни разходи то е равно на turnaround - burst. Примерът използва quantum = 2 и нужди от процесорно време 5, 3, 1; времената на завършване са съответно 9, 8, 5.

Това е детерминистична симулация на един процесор в абстрактни времеви единици, а не конфигурация на планировчик на операционна система или доказателство за поведението на C нишки. Обхват на версията: C23; repository compiler flag, production runtime not attested. Изпълнение в производствена среда не е удостоверено.

Примери

#include <stdio.h>

int main(void)
{
    const int quantum = 2;
    const int burst[3] = {5, 3, 1};
    int remaining[3] = {5, 3, 1};
    int completion[3] = {0};
    int time = 0;
    int unfinished = 3;

    while (unfinished > 0) {
        for (int i = 0; i < 3; ++i) {
            if (remaining[i] == 0) {
                continue;
            }
            int slice = remaining[i] < quantum
                      ? remaining[i] : quantum;
            printf("P%d [%d,%d)\n", i + 1, time, time + slice);
            time += slice;
            remaining[i] -= slice;
            if (remaining[i] == 0) {
                completion[i] = time;
                --unfinished;
            }
        }
    }

    puts("job waiting turnaround");
    for (int i = 0; i < 3; ++i) {
        int turnaround = completion[i]; /* arrival = 0 */
        int waiting = turnaround - burst[i];
        printf("P%d %d %d\n", i + 1, waiting, turnaround);
    }
    return 0;
}

Резултат

P1 [0,2)
P2 [2,4)
P3 [4,5)
P1 [5,7)
P2 [7,8)
P1 [8,9)
job waiting turnaround
P1 4 9
P2 5 8
P3 4 5

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници