Algoritma Penjadwalan CPU

Penjadwalan CPU adalah permasalahan menentukan proses mana pada ready queue yang dialokasikan ke CPU. Terdapat beberapa algoritma penjadwalan CPU, diantaranya :

1. Algoritma Penjadwalan First Come, First Served (FIFO).
2. Algoritma Penjadwalan Shortest Job First.
3. Algoritma Penjadwalan Priority Schedulling (jadwal prioritas).
4. Algoritma Penjadwalan Round Robin.

• Algoritma Penjadwalan First Come, First Served (FCFS)

Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu. Dan rata-rata waktu tunggu (Average waiting time) cukup tinggi.

Algoritma penjadwalan FCFS merupakan salah satu strategi penjadwalan non-Preemptive karena sekali CPU dialokasikan pada suatu proses, maka proses tersebut akan tetap memakai CPU sampai proses tersebut melepaskannhya, yaitu jika proses berhenti atau meminta I/O

Kelemahan dari algoritma ini:

1.             Waiting time rata-ratanya cukup lama.

2.             Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU. Algoritma ini juga menerapkan konsep non-preemptive, yaitu setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh proses yang lain.

• Algoritma Shortest Job First Scheduler

Algoritma ini digunakan ketika CPU bebas proses yang mempunyai waktu terpendek untuk menyelesaikannya mendapat prioritas. Seandainya dua proses atau lebih mempunyai waktu yang sama maka FCFS algoritma digunakan untuk menyelsaikan masalah tersebut.

Prinsip algoritma penjadwalan ini adalah, proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu. Oleh karena itu, algoritma ini optimal jika digunakan, tetapi sulit untuk diimplementasikan karena sulit mengetahui CPU burst selanjutnya.

Ada dua skema dalam SJFS ini yaitu:

1. Non premptive— ketika CPU memberikan kepada proses itu tidak bisa ditunda hingga selesai.
2. premptive— bila sebuah proses datang dengan waktu proses lebih rendah dibandingkan dengan waktu proses yang sedang dieksekusi oleh CPU maka proses yang waktunya lebih rendah mendapatkan prioritas
3. Algoritma Penjadwalan Priority Schedulling (jadwal prioritas)

Penjadualan SJF (Shortest Job First) adalah kasus khusus untuk algoritma penjadual Prioritas. Prioritas dapat diasosiasikan masing-masing proses dan CPU dialokasikan untuk proses dengan prioritas tertinggi. Untuk proritas yang sama dilakukan dengan FCFS.

Ada pun algoritma penjadual prioritas adalah sebagai berikut:

• Setiap proses akan mempunyai prioritas (bilangan integer). Beberapa sistem menggunakan integer dengan urutan kecil untuk proses dengan prioritas rendah, dan sistem lain juga bisa menggunakan integer urutan kecil untuk proses dengan prioritas tinggi. Tetapi dalam teks ini diasumsikan bahwa integer kecil merupakan prioritas tertinggi.

• CPU diberikan ke proses dengan prioritas tertinggi (integer kecil adalah prioritas tertinggi).

• Dalam algoritma ini ada dua skema yaitu:

1. Preemptive: proses dapat di interupsi jika terdapat prioritas lebih tinggi yang memerlukan CPU.

2. Nonpreemptive: proses dengan prioritas tinggi akan mengganti pada saat pemakain time-slice habis.

• SJF adalah contoh penjadual prioritas dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya. Permasalahan yang muncul dalam penjadualan prioritas adalah indefinite blocking atau starvation.

• Kadang-kadang untuk kasus dengan prioritas rendah mungkin tidak pernah dieksekusi.

• Prioritas akan naik jika proses makin lama menunggu waktu jatah CPU.

• Algoritma Penjadwalan Round Robin.

Algoritma Round Robin (RR) dirancang untuk sistem time sharing. Algoritma ini mirip dengan penjadual FCFS, namun preemption ditambahkan untuk switch antara proses. Antrian ready diperlakukan atau dianggap sebagai antrian sirkular. CPU mengelilingi antrian ready dan mengalokasikan masing-masing proses untuk interval waktu tertentu sampai satu time slice/ quantum.

Berikut algoritma untuk penjadual Round Robin:

• Setiap proses mendapat jatah waktu CPU (time slice/ quantum) tertentu Time slice/quantum umumnya antara 10 – 100 milidetik.

1. Setelah time slice/ quantum maka proses akan di-preempt dan dipindahkan ke antrian ready.
2. Proses ini adil dan sangat sederhana.

• Jika terdapat n proses di “antrian ready” dan waktu quantum q (milidetik), maka:

1. Maka setiap proses akan mendapatkan 1/n dari waktu CPU.
2. Proses tidak akan menunggu lebih lama dari: (n-1)q time units.

• Kinerja dari algoritma ini tergantung dari ukuran time quantum.

1. Time Quantum dengan ukuran yang besar maka akan sama dengan FCFS.
2. Time Quantum dengan ukuran yang kecil maka time quantum harus diubah ukurannya lebih besar dengan respek pada alih konteks sebaliknya akan memerlukan ongkos yang besar

Video Simulasi Algoritma Penjadwalan

http://www.youtube.com/watch?v=e3WCqgkpk4w