Beranda algoritma komputasi sistem operasi teknologi

Ini Dia Beda SJF Preemptive dan Non-preemptive yang Wajib Kamu Tahu

Updated: • 0 • min read
Table of Contents

Oke, kita ngomongin CPU scheduling nih, bagian penting banget di sistem operasi yang ngatur gimana CPU itu ‘dibagi-bagi’ buat ngerjain banyak tugas (proses) yang antre. Bayangin aja CPU itu koki di dapur, dan proses-proses itu pesanan makanan yang masuk. Nah, scheduling algorithm ini resep atau panduan si koki buat mutusin pesanan mana yang dikerjain duluan biar semua pesanan selesai secepat mungkin atau adil.

Salah satu algoritma yang populer dan sering jadi bahasan itu Shortest Job First (SJF). Sesuai namanya, algoritma ini prioritinya ke proses atau tugas yang paling pendek waktu eksekusinya (sering disebut burst time). Idenya simpel: selesaikan yang sebentar-sebentar dulu biar antrean cepet habis dan waktu tunggu rata-rata jadi minim. Kedengarannya bagus, kan?

CPU Scheduling
Image just for illustration

Tapi, SJF ini punya dua ‘rasa’ atau mode kerja yang beda banget cara ngejalaninnya: SJF Non-Preemptive dan SJF Preemptive. Perbedaan mendasar di antara keduanya ada di kemampuan algoritma untuk menginterupsi atau mengganti proses yang lagi jalanin CPU kalau ada proses lain yang tiba-tiba datang. Nah, ini dia yang bakal kita bedah tuntas.

Apa Itu SJF Scheduling Secara Umum?

Sebelum masuk ke bedanya, kita pahami dulu inti dari SJF. Tujuan utama SJF adalah meminimalkan average waiting time (waktu tunggu rata-rata) semua proses. Caranya ya itu tadi, mendahulukan proses dengan burst time (lama waktu eksekusi CPU) terpendek.

Secara teori, SJF ini optimal banget buat average waiting time kalau kita tahu burst time setiap proses di awal. Masalahnya, di dunia nyata, kita nggak selalu tahu pasti berapa lama sebuah proses bakal jalan. Ini salah satu tantangan implementasi SJF di sistem operasi modern.

Meskipun ada tantangannya, konsep SJF tetap penting dipelajari karena jadi dasar pengembangan algoritma lain. Algoritma ini nunjukkin bahwa mendahulukan pekerjaan pendek bisa efektif dalam konteks tertentu. Nah, sekarang kita lihat dua cara SJF beroperasi.

Shortest Job First Algorithm
Image just for illustration

SJF Non-Preemptive: Sampai Tuntas Baru Ganti

Mode Non-Preemptive ini adalah versi SJF yang paling ‘sabar’. Begini cara kerjanya:

  1. Ketika CPU kosong, sistem operasi bakal melihat semua proses yang sudah siap (ada di ready queue) dan memilih proses yang punya burst time paling pendek.
  2. Proses yang terpilih ini kemudian diberikan CPU untuk dieksekusi.
  3. Nah, kuncinya di sini: Begitu proses itu mulai dieksekusi, dia akan terus berjalan sampai selesai (sampai burst time-nya habis).
  4. Selama proses itu berjalan, meskipun ada proses baru yang datang di ready queue dan ternyata burst time-nya jauh lebih pendek dari sisa waktu proses yang lagi jalan, proses yang lagi jalan tidak akan diganggu atau dihentikan sementara. Dia harus selesai dulu.
  5. Setelah proses yang lagi jalan selesai, CPU kembali kosong, dan sistem akan memilih lagi proses dengan burst time terpendek dari antrean proses yang sekarang ada dan siap.

Simpelnya, kalau udah mulai, ya selesain dulu. Nggak peduli ada yang lebih penting (lebih pendek) datang belakangan.

Kelebihan SJF Non-Preemptive:

  • Simpel: Logikanya mudah dipahami dan diimplementasikan.
  • Overhead Rendah: Tidak ada overhead (biaya tambahan) untuk context switching (proses ganti-ganti CPU dari satu proses ke proses lain) di tengah eksekusi proses.

Kekurangan SJF Non-Preemptive:

  • Waktu Tunggu yang Mungkin Lebih Lama untuk Proses Pendek yang Datang Terlambat: Ini kekurangan utama. Bayangkan ada proses super panjang lagi jalan, lalu datang proses super pendek. Proses pendek itu harus nungguin yang panjang selesai dulu, padahal kalau dia jalan duluan, dia bisa beres cepat dan ‘membebaskan’ CPU lebih awal.
  • Masalah Starvation: Proses-proses yang punya burst time panjang banget bisa jadi nggak pernah dapat jatah CPU kalau selalu ada proses-proses pendek baru yang datang terus-menerus. Proses panjang ini ‘kelaparan’.

SJF Non Preemptive
Image just for illustration

SJF Preemptive: Si Gesit yang Bisa Menyela

Ini dia versi SJF yang lebih ‘agresif’ atau ‘responsif’. Nama lain dari SJF Preemptive adalah Shortest Remaining Time First (SRTF). Nama SRTF ini lebih menggambarkan cara kerjanya karena dia fokus pada waktu yang tersisa (remaining time), bukan waktu total awal.

Begini cara kerja SJF Preemptive / SRTF:

  1. Sama seperti Non-Preemptive, ketika CPU kosong, sistem memilih proses dengan burst time terpendek dari proses yang siap saat itu.
  2. Proses itu mulai dieksekusi.
  3. Nah, bedanya di sini: Setiap kali ada proses baru yang tiba di ready queue, sistem akan melakukan perbandingan.
  4. Sistem akan membandingkan sisa waktu eksekusi (remaining time) dari proses yang sedang berjalan dengan burst time total dari proses baru yang datang.
  5. Kalau ternyata proses baru yang datang itu punya burst time yang lebih pendek dari sisa waktu proses yang lagi berjalan, maka proses yang lagi berjalan akan dihentikan sementara (preempted), dan CPU langsung dialihkan ke proses baru yang lebih pendek itu.
  6. Proses yang dihentikan sementara akan masuk lagi ke ready queue dengan sisa waktu eksekusinya yang belum selesai.
  7. Kalau proses baru yang datang ternyata tidak lebih pendek dari sisa waktu proses yang sedang berjalan, proses yang sedang berjalan akan terus lanjut.
  8. Ketika proses yang lagi jalan selesai, atau ketika ada preemption, sistem akan kembali memilih proses dengan sisa waktu eksekusi terpendek dari semua proses yang ada di ready queue (termasuk yang baru datang atau yang sebelumnya dihentikan).

Jadi, SRTF itu selalu melihat proses mana yang paling cepat selesai dari sisa waktu yang dia punya saat ini, dan mendahulukannya, bahkan kalau itu berarti menghentikan proses lain.

Kelebihan SJF Preemptive (SRTF):

  • Waktu Tunggu Rata-rata Lebih Rendah: Secara umum, SRTF cenderung menghasilkan average waiting time yang lebih rendah dibandingkan SJF Non-Preemptive, terutama di lingkungan di mana proses-proses datang di waktu yang berbeda. Ini karena proses-proses pendek bisa langsung ‘menyelip’ begitu mereka datang.
  • Lebih Responsif: Sistem terasa lebih responsif karena proses-proses pendek bisa cepat dieksekusi bahkan jika mereka tiba saat proses panjang sedang berjalan.

Kekurangan SJF Preemptive (SRTF):

  • Overhead Tinggi: Ada overhead context switching yang lebih sering karena proses bisa dihentikan kapan saja. Ini butuh waktu dan sumber daya CPU.
  • Masih Ada Potensi Starvation: Sama seperti Non-Preemptive, proses yang sangat panjang masih berisiko starvation jika ada aliran konstan proses-proses yang lebih pendek datang.
  • Kompleksitas Implementasi: Lebih rumit untuk diimplementasikan dibandingkan versi Non-Preemptive karena perlu melacak remaining time setiap proses dan sering melakukan perbandingan setiap kali ada proses baru tiba.

SJF Preemptive SRTF
Image just for illustration

Perbedaan Kunci: Tabel Komparasi

Biar makin jelas, yuk kita lihat perbedaan utamanya dalam bentuk tabel:

Fitur Kunci SJF Non-Preemptive SJF Preemptive (SRTF)
Kemampuan Menyela Tidak (Proses yang berjalan dieksekusi sampai selesai) Ya (Proses yang berjalan bisa dihentikan jika ada proses baru dengan sisa waktu lebih pendek tiba)
Dasar Pemilihan Burst time total (saat pertama kali dipilih) Sisa waktu eksekusi (remaining time)
Responsivitas Kurang responsif terhadap kedatangan proses pendek Lebih responsif, terutama untuk proses pendek baru
Average Waiting Time Cenderung lebih tinggi (dibanding SRTF) Cenderung lebih rendah (seringkali optimal secara teori)
Overhead Rendah (minim context switching) Tinggi (sering terjadi context switching)
Kompleksitas Simpel Lebih kompleks
Risiko Starvation Ada Ada (meskipun dampaknya bisa beda tergantung pola kedatangan proses)

Tabel ini memberikan gambaran cepat tentang bagaimana kedua mode SJF ini berperilaku di bawah kondisi yang berbeda. Intinya, bedanya ada di kemampuan preemption dan dasar pengambilan keputusan (burst time total vs. remaining time).

Ilustrasi Dengan Contoh Nyata

Supaya lebih kebayang, mari kita pakai contoh. Misalkan ada 4 proses (P1, P2, P3, P4) dengan waktu kedatangan (Arrival Time - AT) dan Burst Time (BT) sebagai berikut:

Proses Arrival Time (AT) Burst Time (BT)
P1 0 7
P2 2 4
P3 4 1
P4 5 4

Kita akan lihat bagaimana kedua algoritma ini menjadwalkan proses-proses ini dan menghitung Average Waiting Time-nya.

SJF Non-Preemptive

  • Waktu 0: Hanya P1 yang tiba. P1 mulai jalan. CPU mengeksekusi P1.
  • Waktu 2: P2 tiba. P1 masih jalan (sisa waktu 7-2=5). P1 tidak bisa diganggu.
  • Waktu 4: P3 tiba. P1 masih jalan (sisa waktu 7-4=3). P1 tidak bisa diganggu.
  • Waktu 5: P4 tiba. P1 masih jalan (sisa waktu 7-5=2). P1 tidak bisa diganggu.
  • Waktu 7: P1 selesai dieksekusi. CPU kosong. Proses yang siap sekarang: P2 (AT 2, BT 4), P3 (AT 4, BT 1), P4 (AT 5, BT 4).
  • Sistem melihat burst time mereka: P2(4), P3(1), P4(4). Yang terpendek adalah P3 (BT 1).
  • P3 mulai jalan dari waktu 7 sampai 7+1=8.
  • Waktu 8: P3 selesai. CPU kosong. Proses yang siap: P2 (AT 2, BT 4), P4 (AT 5, BT 4).
  • Sistem melihat burst time mereka: P2(4), P4(4). Ada dua dengan burst time sama (P2 dan P4). Di kasus ini, kita bisa pakai aturan First-Come, First-Served (FCFS) untuk memecah tie. P2 tiba lebih dulu (AT 2 vs AT 5), jadi P2 dipilih.
  • P2 mulai jalan dari waktu 8 sampai 8+4=12.
  • Waktu 12: P2 selesai. CPU kosong. Proses yang siap: P4 (AT 5, BT 4). Tinggal satu proses.
  • P4 mulai jalan dari waktu 12 sampai 12+4=16.
  • Waktu 16: P4 selesai. Semua proses beres.

Urutan Eksekusi (Gantt Chart Mental): [P1 (0-7)] [P3 (7-8)] [P2 (8-12)] [P4 (12-16)]

Perhitungan:

  • Completion Time (CT):
    • P1: 7
    • P2: 12
    • P3: 8
    • P4: 16
  • Turnaround Time (TAT = CT - AT):
    • P1: 7 - 0 = 7
    • P2: 12 - 2 = 10
    • P3: 8 - 4 = 4
    • P4: 16 - 5 = 11
  • Waiting Time (WT = TAT - BT):
    • P1: 7 - 7 = 0
    • P2: 10 - 4 = 6
    • P3: 4 - 1 = 3
    • P4: 11 - 4 = 7
  • Average Waiting Time (AWT): (0 + 6 + 3 + 7) / 4 = 16 / 4 = 4 ms

Process Scheduling Table
Image just for illustration

SJF Preemptive (SRTF)

  • Waktu 0: Hanya P1 yang tiba. P1 mulai jalan. Sisa waktu P1 = 7.
  • Waktu 2: P2 tiba (AT 2, BT 4). P1 sedang jalan dengan sisa waktu 7 - 2 = 5. Bandingkan sisa waktu P1 (5) dengan BT P2 (4). Karena BT P2 (4) < sisa waktu P1 (5), P1 di-preempt. P2 mulai jalan. Sisa waktu P2 = 4.
  • Waktu 4: P3 tiba (AT 4, BT 1). P2 sedang jalan dengan sisa waktu 4 - (4-2) = 4 - 2 = 2. Bandingkan sisa waktu P2 (2) dengan BT P3 (1). Karena BT P3 (1) < sisa waktu P2 (2), P2 di-preempt. P3 mulai jalan. Sisa waktu P3 = 1.
  • Waktu 5: P4 tiba (AT 5, BT 4). P3 sedang jalan dengan sisa waktu 1 - (5-4) = 1 - 1 = 0. Oh, P3 sudah selesai di waktu 5. CPU kosong.
    • Proses yang siap sekarang: P1 (sisa 5), P2 (sisa 2), P4 (BT 4, sisa 4).
    • Sistem melihat sisa waktu: P1(5), P2(2), P4(4). Yang terpendek adalah P2 (sisa 2).
  • P2 mulai jalan lagi dari waktu 5 sampai 5+2=7.
  • Waktu 7: P2 selesai. CPU kosong. Proses yang siap: P1 (sisa 5), P4 (sisa 4).
  • Sistem melihat sisa waktu: P1(5), P4(4). Yang terpendek adalah P4 (sisa 4).
  • P4 mulai jalan dari waktu 7 sampai 7+4=11.
  • Waktu 11: P4 selesai. CPU kosong. Proses yang siap: P1 (sisa 5). Tinggal P1.
  • P1 mulai jalan lagi dari waktu 11 sampai 11+5=16.
  • Waktu 16: P1 selesai. Semua proses beres.

Urutan Eksekusi (Gantt Chart Mental): [P1 (0-2)] [P2 (2-4)] [P3 (4-5)] [P2 (5-7)] [P4 (7-11)] [P1 (11-16)]

Perhitungan:

  • Completion Time (CT):
    • P1: 16
    • P2: 7
    • P3: 5
    • P4: 11
  • Turnaround Time (TAT = CT - AT):
    • P1: 16 - 0 = 16
    • P2: 7 - 2 = 5
    • P3: 5 - 4 = 1
    • P4: 11 - 5 = 6
  • Waiting Time (WT = TAT - BT):
    • P1: 16 - 7 = 9
    • P2: 5 - 4 = 1
    • P3: 1 - 1 = 0
    • P4: 6 - 4 = 2
  • Average Waiting Time (AWT): (9 + 1 + 0 + 2) / 4 = 12 / 4 = 3 ms

Perbandingan Hasil Contoh

  • SJF Non-Preemptive AWT: 4 ms
  • SJF Preemptive (SRTF) AWT: 3 ms

Dari contoh ini, terlihat SJF Preemptive (SRTF) menghasilkan average waiting time yang lebih rendah (3 ms vs 4 ms). Ini sesuai dengan teori bahwa SRTF cenderung lebih baik dalam meminimalkan waktu tunggu rata-rata.

Fakta Menarik dan Tips Terkait SJF

  • SJF Ideal? SJF (terutama SRTF) secara teoritis adalah algoritma optimal untuk meminimalkan average waiting time jika semua proses tiba pada saat yang sama dan burst time mereka diketahui di awal. Di skenario yang lebih realistis (proses tiba di waktu berbeda), SRTF tetap optimal untuk average waiting time.
  • Bagaimana Tahu Burst Time? Ini tantangan besarnya. Sistem operasi modern biasanya tidak tahu pasti berapa lama proses akan berjalan. Mereka sering menggunakan prediksi berdasarkan perilaku proses di masa lalu (misalnya, menggunakan exponential averaging). Akurasi prediksi ini sangat memengaruhi performa SJF.
  • Mengatasi Starvation: Masalah starvation pada SJF (baik preemptive maupun non-preemptive) bisa diatasi dengan teknik Aging. Aging adalah mekanisme di mana prioritas proses akan meningkat seiring bertambahnya waktu tunggu mereka di ready queue. Jadi, proses yang sudah menunggu lama akan mendapatkan prioritas tinggi, mencegahnya kelaparan selamanya.
  • SJF di Dunia Nyata: Algoritma SJF murni jarang digunakan di sistem interactive (seperti OS di PC atau smartphone) karena masalah prediksi burst time dan potensi starvation untuk proses panjang. Namun, konsep dasarnya (mendahulukan pekerjaan pendek) sering diadaptasi atau digabungkan dengan algoritma lain, seperti di penjadwalan berbasis prioritas atau algoritma yang memprediksi next CPU burst. SJF lebih cocok untuk sistem batch processing di mana burst time pekerjaan mungkin lebih mudah diprediksi.

Kesimpulan

Jadi, perbedaan utama antara SJF Non-Preemptive dan SJF Preemptive (SRTF) ada pada kemampuan preemption. Versi Non-Preemptive mengeksekusi proses sampai tuntas tanpa gangguan, sementara versi Preemptive bisa menghentikan proses yang sedang berjalan jika ada proses baru yang datang dengan sisa waktu yang lebih pendek.

SRTF umumnya memberikan average waiting time yang lebih baik karena lebih responsif terhadap kedatangan proses-proses pendek, memungkinkan mereka untuk ‘menyelip’. Namun, ini datang dengan biaya overhead context switching yang lebih tinggi dan implementasi yang lebih kompleks. Kedua versi sama-sama punya risiko starvation untuk proses panjang, yang bisa diatasi dengan teknik seperti Aging.

Pemilihan antara keduanya (atau modifikasinya) bergantung pada kebutuhan sistem operasi: apakah meminimalkan waktu tunggu rata-rata adalah prioritas utama (SRTF unggul di sini) atau apakah menghindari overhead context switching dan kesederhanaan lebih diutamakan (SJF Non-Preemptive lebih cocok).

Semoga penjelasan ini membantu kamu memahami perbedaan fundamental antara kedua mode SJF ini, ya!

Gimana, ada pertanyaan atau pengalaman menarik terkait scheduling di sistem operasi yang mau dibagi? Yuk, diskusi di kolom komentar!

Posting Komentar