Лабораторна робота №5. Моделювання алгоритмів планування процесора

Мета

Реалізувати й порівняти три алгоритми планування — FCFS, невитискальний SJF і Round-Robin — на одному наборі процесів, обчислити час очікування, обороту та відгуку й пояснити отримані компроміси.

Підготовка

Перед виконанням опрацюйте пов'язану лекцію:

Основи планування: FCFS, SJF і Round-Robin

Для роботи потрібне Linux-середовище з GCC. Робота виконується в межах папки lab-05. Програма нічого не змінює в системі: вона лише моделює планування в пам'яті процесу.

Використовується той самий набір процесів, що й у лекції: P1 (надходження 0, тривалість 5), P2 (1, 3), P3 (2, 1), P4 (4, 2).

Завдання

Завдання 1. Відтворіть симулятор трьох алгоритмів

У папці lab-05 створіть файл scheduler_sim.c:

#include <stdio.h>

#define MAX_N 8
#define Q 2

typedef struct {
    int id;
    int arrival;
    int burst;
    int remaining;
    int start;
    int finish;
    int done;
    int started;
} Proc;

static void reset(Proc procs[], int n) {
    for (int i = 0; i < n; i++) {
        procs[i].remaining = procs[i].burst;
        procs[i].start = -1;
        procs[i].finish = -1;
        procs[i].done = 0;
        procs[i].started = 0;
    }
}

static void report(Proc procs[], int n, const char *name) {
    double sw = 0, st = 0, sr = 0;
    printf("%s\n", name);
    for (int i = 0; i < n; i++) {
        int T = procs[i].finish - procs[i].arrival;
        int W = T - procs[i].burst;
        int R = procs[i].start - procs[i].arrival;
        sw += W; st += T; sr += R;
        printf("  P%d: start=%d finish=%d  W=%d T=%d R=%d\n",
               procs[i].id, procs[i].start, procs[i].finish, W, T, R);
    }
    printf("  Середнє: W=%.2f  T=%.2f  R=%.2f\n", sw / n, st / n, sr / n);
}

static void fcfs(Proc procs[], int n) {
    int time = 0;
    for (int i = 0; i < n; i++) {
        if (time < procs[i].arrival) time = procs[i].arrival;
        procs[i].start = time;
        time += procs[i].burst;
        procs[i].finish = time;
    }
    report(procs, n, "FCFS");
}

static void sjf(Proc procs[], int n) {
    int time = 0;
    int left = n;
    while (left > 0) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (!procs[i].done && procs[i].arrival <= time &&
                (best == -1 || procs[i].burst < procs[best].burst)) {
                best = i;
            }
        }
        if (best == -1) {
            int next = 1 << 30;
            for (int i = 0; i < n; i++) {
                if (!procs[i].done && procs[i].arrival < next) {
                    next = procs[i].arrival;
                }
            }
            time = next;
            continue;
        }
        procs[best].start = time;
        time += procs[best].burst;
        procs[best].finish = time;
        procs[best].done = 1;
        left--;
    }
    report(procs, n, "SJF (невитискальний)");
}

static void rr(Proc procs[], int n) {
    int queue[MAX_N];
    int head = 0, tail = 0;
    int time = 0;
    int arrived = 0;
    int left = n;

    while (left > 0) {
        while (arrived < n && procs[arrived].arrival <= time) {
            queue[tail++] = arrived;
            arrived++;
        }
        if (head == tail) {
            if (arrived < n) time = procs[arrived].arrival;
            continue;
        }
        int i = queue[head++];
        if (!procs[i].started) {
            procs[i].start = time;
            procs[i].started = 1;
        }
        int run = procs[i].remaining < Q ? procs[i].remaining : Q;
        procs[i].remaining -= run;
        time += run;
        while (arrived < n && procs[arrived].arrival <= time) {
            queue[tail++] = arrived;
            arrived++;
        }
        if (procs[i].remaining == 0) {
            procs[i].finish = time;
            procs[i].done = 1;
            left--;
        } else {
            queue[tail++] = i;
        }
    }
    report(procs, n, "Round-Robin (q=2)");
}

int main(void) {
    Proc procs[MAX_N] = {
        {1, 0, 5, 0, -1, -1, 0, 0},
        {2, 1, 3, 0, -1, -1, 0, 0},
        {3, 2, 1, 0, -1, -1, 0, 0},
        {4, 4, 2, 0, -1, -1, 0, 0},
    };
    int n = 4;

    reset(procs, n);
    fcfs(procs, n);
    reset(procs, n);
    sjf(procs, n);
    reset(procs, n);
    rr(procs, n);
    return 0;
}

Скомпілюйте та запустіть:

gcc -Wall -Wextra -pedantic -o scheduler_sim scheduler_sim.c
./scheduler_sim

Порівняйте вивід із розрахунками в лекції №6. Поясніть, чому SJF дав найменший середній час очікування на цьому наборі, а Round-Robin — найменший середній час відгуку.

Завдання 2. Додайте процес

Додайте п'ятий процес P5 (надходження 3, тривалість 4) у масив procs і змініть n = 4 на n = 5. Скомпілюйте та запустіть. Дайте відповіді:

який алгоритм тепер дав найменший середній час очікування;
чи зберіг Round-Robin найменший середній час відгуку;
чи змінилася послідовність виконання в SJF порівняно з чотирма процесами.

Поясніть результати словами, не лише числами.

Завдання 3. Прикладний: вплив кванта

Змініть #define Q 2 на #define Q 1 і, окремо, на #define Q 4. Для кожного значення знову використайте початкові чотири процеси (поверніть n = 4). Запишіть середні R і W у таблицю:

Квант	Середнє `R`	Середнє `W`
1
2
4

Сформулюйте висновок: як зміна кванта впливає на час відгуку, час очікування та кількість перемикань контексту.

Очікуваний результат

Для початкових чотирьох процесів симулятор має вивести:

FCFS
  P1: start=0 finish=5  W=0 T=5 R=0
  P2: start=5 finish=8  W=4 T=7 R=4
  P3: start=8 finish=9  W=6 T=7 R=6
  P4: start=9 finish=11  W=5 T=7 R=5
  Середнє: W=3.75  T=6.50  R=3.75
SJF (невитискальний)
  P1: start=0 finish=5  W=0 T=5 R=0
  P2: start=8 finish=11  W=7 T=10 R=7
  P3: start=5 finish=6  W=3 T=4 R=3
  P4: start=6 finish=8  W=2 T=4 R=2
  Середнє: W=3.00  T=5.75  R=3.00
Round-Robin (q=2)
  P1: start=0 finish=11  W=6 T=11 R=0
  P2: start=2 finish=10  W=6 T=9 R=1
  P3: start=4 finish=5  W=2 T=3 R=2
  P4: start=7 finish=9  W=3 T=5 R=3
  Середнє: W=4.25  T=7.00  R=1.50

Результати завдань 2 і 3 відкриті: вони залежать від вашого моделювання, тому запишіть спостереження та зробіть висновки самостійно.

Альтернатива Python

Якщо для вас зручніше Python, можете реалізувати ті самі алгоритми у файлі scheduler_sim.py. Наведено повний варіант із тими самими даними й очікуваними значеннями:

procs = [
    {"id": 1, "arrival": 0, "burst": 5},
    {"id": 2, "arrival": 1, "burst": 3},
    {"id": 3, "arrival": 2, "burst": 1},
    {"id": 4, "arrival": 4, "burst": 2},
]


def report(name, sched):
    print(name)
    sched = sorted(sched, key=lambda p: p["id"])
    ws, ts, rs = [], [], []
    for p in sched:
        w = p["finish"] - p["arrival"] - p["burst"]
        t = p["finish"] - p["arrival"]
        r = p["start"] - p["arrival"]
        ws.append(w)
        ts.append(t)
        rs.append(r)
        print(f'  P{p["id"]}: start={p["start"]} finish={p["finish"]}  '
              f'W={w} T={t} R={r}')
    n = len(sched)
    print(f'  Середнє: W={sum(ws) / n:.2f}  T={sum(ts) / n:.2f}  '
          f'R={sum(rs) / n:.2f}')


def fcfs():
    out, time = [], 0
    for p in procs:
        time = max(time, p["arrival"])
        out.append({"id": p["id"], "arrival": p["arrival"],
                    "burst": p["burst"], "start": time,
                    "finish": time + p["burst"]})
        time += p["burst"]
    report("FCFS", out)


def sjf():
    left = list(procs)
    out, time = [], 0
    while left:
        ready = [p for p in left if p["arrival"] <= time]
        if not ready:
            time = min(p["arrival"] for p in left)
            ready = [p for p in left if p["arrival"] <= time]
        p = min(ready, key=lambda x: (x["burst"], x["id"]))
        out.append({"id": p["id"], "arrival": p["arrival"],
                    "burst": p["burst"], "start": time,
                    "finish": time + p["burst"]})
        time += p["burst"]
        left.remove(p)
    report("SJF (невитискальний)", out)


def rr(q=2):
    import collections
    out = {p["id"]: {"id": p["id"], "arrival": p["arrival"],
                     "burst": p["burst"]} for p in procs}
    rem = {p["id"]: p["burst"] for p in procs}
    start = {}
    finish = {}
    queue = collections.deque()
    arrived = 0
    time = 0
    done = set()

    while len(done) < len(procs):
        while arrived < len(procs) and procs[arrived]["arrival"] <= time:
            queue.append(procs[arrived])
            arrived += 1
        if not queue:
            time = procs[arrived]["arrival"]
            continue
        p = queue.popleft()
        if p["id"] not in start:
            start[p["id"]] = time
        run = min(rem[p["id"]], q)
        rem[p["id"]] -= run
        time += run
        while arrived < len(procs) and procs[arrived]["arrival"] <= time:
            queue.append(procs[arrived])
            arrived += 1
        if rem[p["id"]] == 0:
            finish[p["id"]] = time
            done.add(p["id"])
        else:
            queue.append(p)

    sched = []
    for p in procs:
        out[p["id"]]["start"] = start[p["id"]]
        out[p["id"]]["finish"] = finish[p["id"]]
        sched.append(out[p["id"]])
    report(f"Round-Robin (q={q})", sched)


fcfs()
sjf()
rr()

Запуск:

python3 scheduler_sim.py

Вивід має збігатися з очікуваним результатом завдання 1.

Структура репозиторію

operational-systems/
├── README.md
├── lab-01/
├── lab-02/
├── lab-03/
├── lab-04/
└── lab-05/
    ├── scheduler_sim.c
    └── scheduler_sim.py

Що здати

Посилання на ваш особистий репозиторій operational-systems, надіслане у формі здачі на поточній сторінці.
Папку lab-05 із scheduler_sim.c (або scheduler_sim.py) і результатами спостережень завдань 2–3 у короткому файлі results.txt.
Оновлений кореневий README.md з назвою роботи та командою запуску.

Питання для захисту

Який алгоритм у завданні 1 дав найменший середній час очікування і чому?
Чому Round-Robin покращив середній час відгуку, але погіршив середній час очікування?
Як зміна кванта впливає на час відгуку та кількість перемикань контексту?
Що таке час очікування, час обороту та час відгуку?