Bagian 3: Aturan Penjadwalan

Priority queue siap, sekarang kita menerapkan tiga algoritma scheduling: FCFS (First-Come First-Served), SJF (Shortest Job First non-preemptive), dan Priority (non-preemptive). Ketiganya berbagi kerangka yang sama: simulasi berjalan dari waktu t=0, task dimasukkan ke ready queue saat arrival-nya tercapai, dan scheduler memilih satu task untuk dieksekusi sampai selesai (non-preemptive).

Kerangka Umum Non-Preemptive Scheduler #

text
t = 0
while masih ada task yang belum selesai:
    tambahkan task dengan arrival <= t ke ready queue
    if ready queue kosong:
        t = min arrival dari task yang belum tiba
        continue
    task = ready_queue.top()  // sesuai algoritma
    ready_queue.pop()
    task.startTime = t
    t += task.burst
    task.finishTime = t

Perbedaan antar algoritma hanya pada baris task = ready_queue.top() — FCFS pakai queue FIFO biasa, SJF pakai priority_queue dengan SjfComparator, Priority pakai priority_queue dengan PriorityComparator.

Implementasi FCFS #

FCFS adalah yang paling sederhana: task dijalankan sesuai urutan kedatangan. Cukup std::sort berdasarkan arrival lalu iterasi.

cpp
#include <algorithm>

std::vector<Task> scheduleFCFS(std::vector<Task> tasks) {
    std::sort(tasks.begin(), tasks.end(),
        [](const Task& a, const Task& b) { return a.arrival < b.arrival; });
    int t = 0;
    for (auto& task : tasks) {
        if (t < task.arrival) t = task.arrival;   // idle wait
        task.startTime = t;
        t += task.burst;
        task.finishTime = t;
    }
    return tasks;
}

Implementasi SJF Non-Preemptive #

SJF memakai priority queue dengan comparator burst terkecil. Tantangannya: kita hanya boleh push task ke ready queue saat arrival-nya tercapai.

cpp
std::vector<Task> scheduleSJF(std::vector<Task> tasks) {
    std::vector<Task> result;
    std::priority_queue<Task, std::vector<Task>, SjfComparator> ready;
    int t = 0, idx = 0;
    std::sort(tasks.begin(), tasks.end(),
        [](const Task& a, const Task& b) { return a.arrival < b.arrival; });
    while (result.size() < tasks.size()) {
        while (idx < (int)tasks.size() && tasks[idx].arrival <= t) {
            ready.push(tasks[idx]);
            ++idx;
        }
        if (ready.empty()) {
            t = tasks[idx].arrival;   // skip idle
            continue;
        }
        Task cur = ready.top(); ready.pop();
        cur.startTime = t;
        t += cur.burst;
        cur.finishTime = t;
        result.push_back(cur);
    }
    return result;
}

Implementasi Priority Non-Preemptive #

Sama dengan SJF, hanya ganti comparator.

cpp
std::vector<Task> schedulePriority(std::vector<Task> tasks) {
    std::vector<Task> result;
    std::priority_queue<Task, std::vector<Task>, PriorityComparator> ready;
    int t = 0, idx = 0;
    std::sort(tasks.begin(), tasks.end(),
        [](const Task& a, const Task& b) { return a.arrival < b.arrival; });
    while (result.size() < tasks.size()) {
        while (idx < (int)tasks.size() && tasks[idx].arrival <= t) {
            ready.push(tasks[idx]);
            ++idx;
        }
        if (ready.empty()) {
            t = tasks[idx].arrival;
            continue;
        }
        Task cur = ready.top(); ready.pop();
        cur.startTime = t;
        t += cur.burst;
        cur.finishTime = t;
        result.push_back(cur);
    }
    return result;
}

Program Lengkap Bagian 3 #

Berikut program yang menjalankan ketiga algoritma dan mencetak ringkasan start/finish.

cpp
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

struct Task {
    std::string id;
    int arrival;
    int burst;
    int priority;
    int startTime = -1;
    int finishTime = -1;
};

struct SjfComparator {
    bool operator()(const Task& a, const Task& b) const {
        if (a.burst != b.burst) return a.burst > b.burst;
        return a.arrival > b.arrival;
    }
};

struct PriorityComparator {
    bool operator()(const Task& a, const Task& b) const {
        if (a.priority != b.priority) return a.priority > b.priority;
        return a.arrival > b.arrival;
    }
};

std::vector<Task> scheduleFCFS(std::vector<Task> tasks) {
    std::sort(tasks.begin(), tasks.end(),
        [](const Task& a, const Task& b) { return a.arrival < b.arrival; });
    int t = 0;
    for (auto& task : tasks) {
        if (t < task.arrival) t = task.arrival;
        task.startTime = t;
        t += task.burst;
        task.finishTime = t;
    }
    return tasks;
}

std::vector<Task> scheduleGeneric(
        std::vector<Task> tasks,
        std::priority_queue<Task, std::vector<Task>, SjfComparator>& ready,
        bool /*useSjf*/) {
    std::vector<Task> result;
    int t = 0, idx = 0;
    std::sort(tasks.begin(), tasks.end(),
        [](const Task& a, const Task& b) { return a.arrival < b.arrival; });
    while (result.size() < tasks.size()) {
        while (idx < (int)tasks.size() && tasks[idx].arrival <= t) {
            ready.push(tasks[idx]);
            ++idx;
        }
        if (ready.empty()) {
            t = tasks[idx].arrival;
            continue;
        }
        Task cur = ready.top(); ready.pop();
        cur.startTime = t;
        t += cur.burst;
        cur.finishTime = t;
        result.push_back(cur);
    }
    return result;
}

std::vector<Task> scheduleSJF(std::vector<Task> tasks) {
    std::priority_queue<Task, std::vector<Task>, SjfComparator> ready;
    return scheduleGeneric(std::move(tasks), ready, true);
}

std::vector<Task> schedulePriority(std::vector<Task> tasks) {
    // Reuse generic logic with PriorityComparator.
    std::vector<Task> result;
    std::priority_queue<Task, std::vector<Task>, PriorityComparator> ready;
    int t = 0, idx = 0;
    std::sort(tasks.begin(), tasks.end(),
        [](const Task& a, const Task& b) { return a.arrival < b.arrival; });
    while (result.size() < tasks.size()) {
        while (idx < (int)tasks.size() && tasks[idx].arrival <= t) {
            ready.push(tasks[idx]);
            ++idx;
        }
        if (ready.empty()) {
            t = tasks[idx].arrival;
            continue;
        }
        Task cur = ready.top(); ready.pop();
        cur.startTime = t;
        t += cur.burst;
        cur.finishTime = t;
        result.push_back(cur);
    }
    return result;
}

void printSchedule(const std::string& name, const std::vector<Task>& result) {
    std::cout << "=== " << name << " ===\n";
    std::cout << "ID   start  finish\n";
    for (const auto& t : result) {
        std::cout << t.id << "     " << t.startTime << "       "
                  << t.finishTime << "\n";
    }
    std::cout << "\n";
}

int main() {
    std::vector<Task> tasks = {
        {"T1", 0, 5, 2},
        {"T2", 1, 3, 1},
        {"T3", 2, 8, 3},
        {"T4", 3, 6, 2},
        {"T5", 4, 4, 1}
    };
    printSchedule("FCFS", scheduleFCFS(tasks));
    printSchedule("SJF",  scheduleSJF(tasks));
    printSchedule("Priority", schedulePriority(tasks));
    return 0;
}

Output yang Dihasilkan:

text
=== FCFS ===
ID   start  finish
T1     0       5
T2     5       8
T3     8       16
T4     16       22
T5     22       26

=== SJF ===
ID   start  finish
T1     0       5
T2     5       8
T5     8       12
T4     12       18
T3     18       26

=== Priority ===
ID   start  finish
T1     0       5
T2     5       8
T5     8       12
T4     12       18
T3     18       26

Bedah Baris Penting #

std::sort(tasks.begin(), tasks.end(), ... a.arrival < b.arrival): task di-sort berdasarkan arrival agar loop dapat memproses task yang tiba lebih awal lebih dulu. Tanpa sort, logika while (idx < n && tasks[idx].arrival <= t) tidak bekerja karena idx tidak ada di urutan arrival.
while (idx < tasks.size() && tasks[idx].arrival <= t): masukkan semua task yang sudah tiba (arrival ≤ t) ke ready queue. Task yang belum tiba menunggu sampai t mencapai arrival mereka.
if (ready.empty()) t = tasks[idx].arrival: bila tidak ada task di ready queue (semua task sudah tiba dan dijalankan, atau belum ada yang tiba), lompat ke arrival task berikutnya. Ini menangani idle time di mana CPU tidak melakukan apa-apa.
scheduleGeneric: refactor SJF untuk menggunakan template-like pattern. Kita lewatkan priority queue by reference; bila komparator berbeda (Priority), kita tidak bisa langsung pakai fungsi yang sama karena tipe queue berbeda. Pada kode di atas, schedulePriority menulis ulang loop — solusi cleaner adalah template, tetapi kita pertahankan agar mudah dibaca.
std::move(tasks): parameter passed by value ke scheduleSJF lalu di-std::move ke scheduleGeneric menghindari salinan tak perlu. Task dengan string ID bisa relatif besar bila ada ribuan.

Kompilasi dan Pengujian #

bash
g++ -std=c++17 -O2 -Wall -Wextra -o schedule.bin schedule.cpp
./schedule.bin

Perhatikan bahwa pada task set ini, SJF dan Priority menghasilkan urutan eksekusi yang sama persis — kebetulan karena T2 dan T5 sama-sama prio=1 dan burst kecil. Pada Bagian 4 kita menghitung metrik dan membandingkan keduanya.