Bagian 2: Priority Queue

Pada bagian ini kita membangun custom comparator untuk std::priority_queue yang memilih task berdasarkan kriteria berbeda. Kita akan menulis dua comparator: satu untuk SJF (Shortest Job First — burst terkecil lebih dulu) dan satu untuk Priority (priority value terkecil lebih dulu). FCFS tidak butuh priority queue — cukup std::sort berdasarkan arrival.

Cara Kerja `std::priority_queue` #

std::priority_queue default adalah max-heap — elemen dengan nilai terbesar di top. Untuk mendapatkan elemen dengan nilai terkecil di top, kita pakai std::greater<T> sebagai comparator. Tapi bila elemen adalah Task (struct), kita perlu comparator custom.

cpp
// Comparator SJF: burst terkecil di top.
struct SjfComparator {
    bool operator()(const Task& a, const Task& b) const {
        return a.burst > b.burst;   // > because priority_queue is max-heap
    }
};

std::priority_queue<Task, std::vector<Task>, SjfComparator> pq;

Comparator untuk Tiga Algoritma #

cpp
// SJF: burst terkecil di top.
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;   // tie-breaker: FCFS
    }
};

// Priority: priority value terkecil di top.
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;   // tie-breaker: FCFS
    }
};

Tie-breaker FCFS (arrival lebih kecil lebih dulu) memberi determinisme — bila dua task memiliki burst sama atau priority sama, task yang tiba lebih awal dipilih lebih dulu.

Program Verifikasi Priority Queue #

Berikut program yang menguji kedua comparator pada data sample.

cpp
#include <functional>
#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;
    }
};

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}
    };

    std::cout << "=== SJF order (burst terkecil lebih dulu) ===\n";
    std::priority_queue<Task, std::vector<Task>, SjfComparator> sjfQ;
    for (const auto& t : tasks) sjfQ.push(t);
    while (!sjfQ.empty()) {
        auto t = sjfQ.top(); sjfQ.pop();
        std::cout << "  " << t.id << " burst=" << t.burst << "\n";
    }

    std::cout << "\n=== Priority order (prio terkecil lebih dulu) ===\n";
    std::priority_queue<Task, std::vector<Task>, PriorityComparator> prioQ;
    for (const auto& t : tasks) prioQ.push(t);
    while (!prioQ.empty()) {
        auto t = prioQ.top(); prioQ.pop();
        std::cout << "  " << t.id << " prio=" << t.priority << "\n";
    }
    return 0;
}

Output yang Dihasilkan:

text
=== SJF order (burst terkecil lebih dulu) ===
  T2 burst=3
  T5 burst=4
  T1 burst=5
  T4 burst=6
  T3 burst=8

=== Priority order (prio terkecil lebih dulu) ===
  T2 prio=1
  T5 prio=1
  T1 prio=2
  T4 prio=2
  T3 prio=3

Bedah Baris Penting #

struct SjfComparator: functor (objek dengan operator()) yang menjadi comparator std::priority_queue. Lebih efisien daripada function pointer karena compiler dapat inline.
a.burst > b.burst: arah “lebih dari” (bukan “kurang dari”) karena STL priority_queue adalah max-heap. Untuk mendapatkan “burst terkecil di top”, kita minta heap menganggap task dengan burst lebih besar sebagai “lebih rendah” dalam heap.
if (a.burst != b.burst) ... return a.arrival > b.arrival: tie-breaker FCFS. Bila dua task punya burst sama, task dengan arrival lebih awal didahulukan. Tanpa tie-breaker, urutan task dengan burst sama bisa non-deterministik (bergantung pada implementasi heap).
std::priority_queue<Task, std::vector<Task>, SjfComparator>: tiga template parameter: tipe elemen, container underlying (vector), dan comparator. Container default adalah std::vector, jadi bisa dihilangkan, tetapi eksplisit lebih jelas.
for (const auto& t : tasks) sjfQ.push(t): semua task dimasukkan ke queue sekaligus. Pada simulasi nyata (Bagian 4), task hanya dimasukkan saat arrival-nya sudah lewat — scheduler harus menunggu kedatangan task.

Kompleksitas Priority Queue #

Operasi	Kompleksitas
`push()`	O(log n)
`top()`	O(1)
`pop()`	O(log n)
Konstruksi dari n elemen	O(n) (Floyd’s algorithm)

Untuk n task, total waktu scheduling = O(n log n). Bandingkan dengan FCFS yang cukup std::sort berdasarkan arrival — O(n log n) juga, tetapi konstanta lebih kecil.

Kompilasi dan Pengujian #

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

Verifikasi bahwa SJF mengeluarkan T2 (burst=3) lebih dulu, dan Priority mengeluarkan T2 (prio=1) lebih dulu. Pada Bagian 3 kita menerapkan ketiga algoritma dalam simulasi nyata.