Penjadwalan Proses pada Sistem Operasi

Deskripsi Penjadwalan Proses

Penjadwalan proses merupakan kumpulan kebijaksanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer. Sedangkan proses merupakan unit kerja terkecil yang secara individu memiliki sumberdaya atau unit pemilikan sumberdaya.
Tugas penjadwalan diantaranya adalah sebagai berikut :

• Memutuskan proses yang berjalan.
• Memutuskan kapan dan selama berapa lama proses itu berjalan.

Sasaran utama dalam penjadwalan proses adalah :
Ø  Adil (fairness)
Adil adalah proses-proses diperlukan sama yaitu mendapat jatah waktu pemrosesan yang sama dan tak ada pemroses yang tak kebagian layanan pemroses sehingga mengalami (starvation).

Ø  Efisiensi
Efisiensi atau utilisasi pemroses dihitung dengan perbandingan (rasio) waktu sibuk pemroses.

Ø  Waktu tanggap (response time), dibagi menjadi :
o   Sistem Interaktif
Waktu tanggap dalam sistem interaktif didefinisikan sebagai waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukkan atau transaksi sampai hasil pertama muncul dilayar (terminal). Waktu tanggap ini disebut terminal response time.
o   Sistem Realtime
Pada sistem waktu nyata (real-time), waktu tanggap di definisikan sebagai waktu dari saat kejadian (internal atau eksternal) sampai instruksi pertama rutin layanan yang dimaksud dieksekusi, disebut event response time. Sasaran penjadwalan adalah meminimalkan waktu tanggap.

Ø  Turn Arround Time
Waktu yang dihabiskan dari saat program atau job mulai masuk ke sistem sampai proses diselesaikan sistem.

Ø  Throughput
Throughput adalah jumlah kerja yang dapat diselesaikan dalam satu unit waktu.

Tipe-tipe Penjadwalan

Penjadwalan proses ada tiga tipe :

1. Penjadwalan jangka pendek (short-termscheduller). Penjadwalan ini bertugas menjadwalkan alokasi pemroses diantara proses-proses ready dimemori utama.
2. Penjadwalan jangka menengah (medium-termscheduller). Penjadwalan jangka menengah adalah menangani proses-proses swapping (aktivitas pemindahan proses yang tertunda dari memory utama ke memory sekunder).
3. Penjadwalan jangka panjang (long-termscheduller). Penjadwalan jangka panjang bekerja terhadap antrian batch (proses-proses dengan penggunaan sumberdaya yang intensif) dan memilih batch berikutnya yang harus di eksekusi.

Strategi Penjadwalan

Penjadwalan Nonpreemptive
Begitu proses diberi jatah waktu pemroses maka pemroses tidak dapat diambil alih oleh proses lain sampai proses itu selesai.

Penjadwalan Preemptive
Saat proses diberi jatah waktu pemroses maka pemroses dapat diambil alih oleh proses lain sehingga proses disela sebelum selesai dan harus dilanjutkan menunggu jatah waktu pemroses tiba kembali pada proses itu.



Algoritma Penjadwalan Proses

1.   Algoritma Non-preemptive
      CPU tidak memperbolehkan proses yang ada di ready queue untuk menggeser proses yang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time yang lebih kecil.

A.    First-Come, First-Served Scheduling (FCFS)
            Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU. Dengan menggunakan algoritma ini setiap proses yang berada pada status ready dimasukkan ke dalam FIFO queue sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi.
Kelemahan dari algoritma ini :

• Waiting time rata-ratanya cukup lama  
• Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU

B.     Shortest-Job-First-Scheduling (SJF)
Algoritma ini mempunyai cara penjadwalan yang berbeda dengan FCFS. Dengan algoritma ini maka setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.
Ada beberapa kekurangan dari algoritma ini yaitu:

• Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya
• Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil.

C.     Higest Ratio Next (HRN)
Higest Ratio Next (HRN) merupakan penjadwalan untuk mengoreksi kelemahan SJF yang berprioritas dinamis. HRN Adalah strategi penjadwalan dengan prioritas proses tidak hanya merupakan fungsi waktu layanan, tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemroses, maka proses berjalan sampai selesai. Prioritas dinamis HRN dihitung berdasarkan rumus berikut : Prioritas = (waktu tunggu + waktu layanan ) / waktu layanan. Karena waktu layanan muncul sebagai pembagi, maka job lebih pendek berprioritas lebih baik, karena waktu tunggu sebagai pembilang, maka proses yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus.

D.    Multilevel Feedback Queue (MFQ)
Algoritma ini merupakan algoritma yang mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Hal ini akan sangat menguntungkan karena akan menggunakan waktu yang sedikit dalam pengerjaan proses-proses tersebut. Demikian pula dengan proses yang menunggu lama maka prose ini akan dinaikkan ke tingkat yang lebih tinggi. Dengan begitu CPU akan bekerja dengan penuh dan M/K dapat terus sibuk. Semakin rendah tingkatnya, panjang CPU burst proses juga semakin panjang.


2.      Algoritma Preemptive
Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di ready queue dengan burst time yang lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di ready queue tersebut.

A.    Round Robin (RR)
Algoritma penjadwalan ini mirip dengan algoritma First Come First Served, tetapi proses ini memberi suatu batasan waktu untuk setiap proses yang disebut dengan time quantum. Time quantum adalah suatu satuan waktu yang kecil. Jika proses yang sedang dieksekusi selesai dalam waktu kurang dari 1 time quantum, tidak ada masalah. Tetapi jika proses berjalan melebihi 1 time quantum, maka proses tersebut akan dihentikan, lalu digantikan oleh proses yang berikutnya. Proses yang dihentikan tersebut akan diletakkan di queue di urutan paling belakang
Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai dalam 1 time quantum. Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma First Come First Served.

B.     Shortest Remaining First (SRF)
Pada algoritma ini setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.
Tabel Contoh Shortest Job First

Contoh : Ada 4 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 7 ms, P2 dengan arrival time pada 2.0 ms dan burst time 4 ms, P3 dengan arrival time pada 4.0 ms dan burst time 1 ms, P4 dengan arrival time pada 5.0 ms dan burst time 4 ms. Hitunglah waiting time rata-rata dan turn around time dari keempat proses tersebut dengan mengunakan algoritma SJF. Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0 +6+3+7)/4=4 ms.

C.     Priority Schedulling (PS)
Priority Scheduling merupakan algoritma penjadwalan yang mendahulukan proses yang memiliki prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing. Prioritas suatu proses dapat ditentukan melalui beberapa karakteristik antara lain: Time limit, Memory requirement, Akses file, Perbandingan antara burst M/K dengan CPU burst, Tingkat kepentingan proses.
Kelemahan pada priority scheduling adalah dapat terjadinya indefinite blocking( starvation). Suatu proses dengan prioritas yang rendah memiliki kemungkinan untuk tidak dieksekusi jika terdapat proses lain yang memiliki prioritas lebih tinggi darinya. Solusi dari permasalahan ini adalah aging, yaitu meningkatkan prioritas dari setiap proses yang menunggu dalam queue secara bertahap.

D.    Guaranteed Scheduling (GS)
Penjadwalan ini memberi daya pemroses yang sama untuk membuat dan menyesuaikan performance. Jika ada N pemakai, setiap proses (pemakai) akan mendapatkan 1/N dari daya pemroses CPU. Untuk mewujudkannya, sistem harus selalu menyimpan informasi tentang jumlah waktu CPU untuk semua proses sejak login dan juga berapa lama pemakai sedang login. Algoritma akan menjalankan proses dengan rasio paling rendah hingga naik ketingkat lebih tinggi diatas pesaing terdekatnya.