Pada bagian akhir ini, kita menjalankan ketiga algoritma pada task set yang sama, menghitung metrik (waiting time, turnaround time), dan mencetak Gantt chart untuk visualisasi eksekusi. Hasil simulasi kita bandingkan untuk memahami trade-off antar algoritma.
Perhitungan Metrik #
Dari startTime dan finishTime yang sudah diisi scheduler:
- Waiting time =
startTime - arrival - Turnaround time =
finishTime - arrival
Average dari kedua metrik menjadi indikator kualitas algoritma.
cpp
struct Metrics {
double avgWait;
double avgTurnaround;
};
Metrics computeMetrics(const std::vector<Task>& result) {
double totalWait = 0, totalTurn = 0;
for (const auto& t : result) {
totalWait += t.startTime - t.arrival;
totalTurn += t.finishTime - t.arrival;
}
double n = (double)result.size();
return { totalWait / n, totalTurn / n };
}Gantt Chart Sederhana #
Gantt chart menampilkan urutan eksekusi sebagai deretan segmen [Task:start-finish]:
cpp
void printGantt(const std::vector<Task>& result) {
std::cout << "Gantt: ";
for (const auto& t : result) {
std::cout << "[" << t.id << ":" << t.startTime << "-" << t.finishTime << "]";
}
std::cout << "\n";
}Program Lengkap Bagian 4 #
Berikut program yang menjalankan ketiga algoritma, mencetak Gantt chart dan tabel metrik.
cpp
#include <algorithm>
#include <iomanip>
#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> 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; 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> 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;
}
struct Metrics { double avgWait; double avgTurnaround; };
Metrics computeMetrics(const std::vector<Task>& result) {
double totalWait = 0, totalTurn = 0;
for (const auto& t : result) {
totalWait += t.startTime - t.arrival;
totalTurn += t.finishTime - t.arrival;
}
double n = (double)result.size();
return { totalWait / n, totalTurn / n };
}
void printGantt(const std::vector<Task>& result) {
std::cout << "Gantt: ";
for (const auto& t : result) {
std::cout << "[" << t.id << ":" << t.startTime << "-" << t.finishTime << "]";
}
std::cout << "\n";
}
void printMetrics(const std::vector<Task>& result) {
std::cout << "Task Wait Turnaround\n";
for (const auto& t : result) {
int wait = t.startTime - t.arrival;
int turn = t.finishTime - t.arrival;
std::cout << " " << t.id << " " << std::setw(4) << wait
<< " " << std::setw(7) << turn << "\n";
}
Metrics m = computeMetrics(result);
std::cout << "Avg wait=" << std::fixed << std::setprecision(1) << m.avgWait
<< " avg turnaround=" << m.avgTurnaround << "\n";
}
void runScenario(const std::string& name,
const std::vector<Task>& tasks,
std::vector<Task> (*algo)(std::vector<Task>)) {
std::cout << "=== " << name << " ===\n";
auto result = algo(tasks);
printGantt(result);
printMetrics(result);
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}
};
std::cout << "Daftar task:\n";
for (const auto& t : tasks) {
std::cout << " " << t.id << " arrival=" << t.arrival
<< " burst=" << t.burst << " prio=" << t.priority << "\n";
}
std::cout << "\n";
runScenario("FCFS", tasks, scheduleFCFS);
runScenario("SJF", tasks, scheduleSJF);
runScenario("Priority", tasks, schedulePriority);
return 0;
}Output yang Dihasilkan:
text
Daftar task:
T1 arrival=0 burst=5 prio=2
T2 arrival=1 burst=3 prio=1
T3 arrival=2 burst=8 prio=3
T4 arrival=3 burst=6 prio=2
T5 arrival=4 burst=4 prio=1
=== FCFS ===
Gantt: [T1:0-5][T2:5-8][T3:8-16][T4:16-22][T5:22-26]
Task Wait Turnaround
T1 0 5
T2 4 7
T3 6 14
T4 13 19
T5 18 22
Avg wait=8.2 avg turnaround=13.4
=== SJF ===
Gantt: [T1:0-5][T2:5-8][T5:8-12][T4:12-18][T3:18-26]
Task Wait Turnaround
T1 0 5
T2 4 7
T5 4 8
T4 9 15
T3 16 24
Avg wait=6.6 avg turnaround=11.8
=== Priority ===
Gantt: [T1:0-5][T2:5-8][T5:8-12][T4:12-18][T3:18-26]
Task Wait Turnaround
T1 0 5
T2 4 7
T5 4 8
T4 9 15
T3 16 24
Avg wait=6.6 avg turnaround=11.8Bedah Hasil dan Analisis #
- FCFS menghasilkan avg wait 8.2 — paling buruk di antara tiga algoritma. Penyebabnya: T5 (burst=4, prio tinggi) harus menunggu 18 unit karena T3 (burst=8) dijalankan lebih dulu meski T5 sudah tiba sejak t=4. Ini convoy effect: task kecil menunggu task besar.
- SJF menghasilkan avg wait 6.6 — 19% lebih baik dari FCFS. T5 dijalankan lebih awal (start=8) karena burst-nya kecil. SJF secara teori optimal untuk avg wait pada skema non-preemptive.
- Priority menghasilkan avg wait yang sama dengan SJF karena kebetulan: T2 dan T5 punya prio=1 (tertinggi) dan juga burst terkecil. Pada task set berbeda, hasil Priority bisa lebih buruk dari SJF bila ada task dengan prio tinggi tetapi burst besar.
Ringkasan Proyek #
Kita telah membangun simulator CPU scheduler lengkap: pemodelan Task (Bagian 1), priority queue dengan custom comparator (Bagian 2), tiga algoritma scheduling non-preemptive (Bagian 3), dan simulasi dengan perhitungan metrik + Gantt chart (Bagian 4). Temuan utama yang harus diingat:
- FCFS sederhana tetapi rentan convoy effect (task kecil menunggu task besar),
- SJF optimal untuk avg wait non-preemptive tetapi bisa menyebabkan starvation task burst besar,
- Priority scheduler efektif bila priority mencerminkan urgensi, tetapi perlu aging untuk mencegah starvation,
- Pemilihan algoritma terbaik bergantung pada karakteristik task set dan tujuan (avg wait vs fairness).
Kompilasi dan Pengujian #
bash
g++ -std=c++17 -O2 -Wall -Wextra -o simulate.bin simulate.cpp
./simulate.binCoba modifikasi task set dengan burst atau priority berbeda untuk mengamati perubahan urutan eksekusi dan metrik.