Penjadwalan Proses

Penjadwalan CPU mungkin akan dijalankan ketika proses dalam keadaan:

1. Berubah dari running ke waiting state.
2. Berubah dari running ke ready state.
3. Berubah dari waiting ke ready state.
4. Dihentikan.

Penjadwalan Preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi. Penjadwalan ini bisa saja termasuk penjadwalan proses atau I/O. Penjadwalan Preemptive memungkinkan sistem untuk lebih bisa menjamin bahwa setiap proses mendapat sebuah slice waktu operasi. Dan juga membuat sistem lebih cepat merespon terhadap event dari luar (contohnya seperti ada data yang masuk) yang membutuhkan reaksi cepat dari satu atau beberapa proses. Membuat penjadwalan yang Preemptive mempunyai keuntungan yaitu sistem lebih responsif daripada sistem yang memakai penjadwalan Non Preemptive.

Dalam waktu-waktu tertentu, proses dapat dikelompokkan ke dalam dua kategori: proses yang memiliki Burst I/O yang sangat lama disebut I/O Bound, dan proses yang memiliki Burst CPU yang sangat lama disebut CPU Bound. Terkadang juga suatu sistem mengalami kondisi yang disebut busywait, yaitu saat dimana sistem menunggu request input(seperti disk, keyboard, atau jaringan). Saat busywait tersebut, proses tidak melakukan sesuatu yang produktif, tetapi tetap memakan resource dari CPU. Dengan penjadwalan Preemptive, hal tersebut dapat dihindari.

Dengan kata lain, penjadwalan Preemptive melibatkan mekanisme interupsi yang menyela proses yang sedang berjalan dan memaksa sistem untuk menentukan proses mana yang akan dieksekusi selanjutnya.

Penjadwalan nomor 1 dan 4 bersifat Non Preemptive sedangkan lainnya Preemptive. Penjadwalan yang biasa digunakan sistem operasi dewasa ini biasanya bersifat Preemptive. Bahkan beberapa penjadwalan sistem operasi, contohnya Linux 2.6, mempunyai kemampuan Preemptive terhadap system call-nya (preemptible kernel). Windows 95, Windows XP, Linux, Unix, AmigaOS, MacOS X, dan Windows NT adalah beberapa contoh sistem operasi yang menerapkan penjadwalan Preemptive.

Lama waktu suatu proses diizinkan untuk dieksekusi dalam penjadwalan Preemptive disebut time slice/quantum. Penjadwalan berjalan setiap satu satuan time slice untuk memilih proses mana yang akan berjalan selanjutnya. Bila time slice terlalu pendek maka penjadwal akan memakan terlalu banyak waktu proses, tetapi bila time slice terlau lama maka memungkinkan proses untuk tidak dapat merespon terhadap event dari luar secepat yang diharapkan.

2.      Kriteria Penjadwalan

Suatu algoritma penjadwalan CPU yang berbeda dapat mempunyai nilai yang berbeda untuk sistem yang berbeda. Banyak kriteria yang bisa dipakai untuk menilai algoritma penjadwalan CPU.

Kriteria yang digunakan dalam menilai adalah:

1. CPU Utilization . Kita ingin menjaga CPU sesibuk mungkin. CPU utilization akan mempunyai range dari 0 sampai 100 persen. Di sistem yang sebenarnya ia mempunyai range dari 40 sampai 100 persen.
2. Throughput . Salah satu ukuran kerja adalah banyaknya proses yang diselesaikan per satuan waktu. Jika kita mempunyai beberapa proses yang sama dan memiliki beberapa algoritma penjadwalan yang berbeda, throughput bisa menjadi salah satu kriteria penilaian, dimana algoritma yang menyelesaikan proses terbanyak mungkin yang terbaik.
3. Turnaround Time . Dari sudut pandang proses tertentu, kriteria yang penting adalah berapa lama untuk mengeksekusi proses tersebut. Memang, lama pengeksekusian sebuah proses sangat tergantung dari hardware yang dipakai, namun kontribusi algoritma penjadwalan tetap ada dalam lama waktu yang dipakai untuk menyelesaikan sebuah proses. Misal kita memiliki sistem komputer yang identik dan proses-proses yang identik pula, namun kita memakai algoritma yang berbeda, algoritma yang mampu menyelesaikan proses yang sama dengan waktu yang lebih singkat mungkin lebih baik dari algoritma yang lain. Interval waktu yang diijinkan dengan waktu yang dibutuhkan untuk menyelesaikan sebuah proses disebut turnaround time. Turnaround time adalah jumlah periode untuk menunggu untuk dapat ke memori, menunggu di ready queue, eksekusi CPU, dan melakukan operasi I/O.
4. Waiting Time . Algoritma penjadwalan CPU tidak mempengaruhi waktu untuk melaksanakan proses tersebut atau I/O, itu hanya mempengaruhi jumlah waktu yang dibutuhkan proses di antrian ready. Waiting time adalah jumlah waktu yang dibutuhkan proses di antrian ready.
5. Response Time . Di sistem yang interaktif, turnaround time mungkin bukan waktu yang terbaik untuk kriteria. Sering sebuah proses dapat memproduksi output di awal, dan dapat meneruskan hasil yang baru sementara hasil yang sebelumnya telah diberikan ke pengguna. Ukuran lain adalah waktu dari pengiriman permintaan sampai respon yang pertama diberikan. Ini disebut response time, yaitu waktu untuk memulai memberikan respon, tetapi bukan waktu yang dipakai output untuk respon tersebut.
6. Fairness . Suatu algoritma harus memperhatikan pengawasan nilai prioritas dari suatu proses (menghindari terjadinya starvation CPU time).
7. Efisiensi. Rendahnya overhead dalam context switching, penghitungan prioritas dan sebagainya menentukan apakah suatu algoritma efisien atau tidak.

Sebaiknya ketika kita akan membuat algoritma penjadwalan yang dilakukan adalah memaksimalkan CPU utilization dan throughput, dan meminimalkan turnaround time, waiting time, dan response time.

Algoritma Penjadwalan

Algoritma – Algoritma Penjadwalan Proses
Terdapat banyak algoritma penjadwalan, baik algoritma penjadwalan nonpreemtive maupun penjadwalan preemtive.
Algoritma – Algoritma merupakan yang menerapkan strategi nonpreemtive diantaranya :
• FIFO (Fist in,Fist Out) atau FCFS (Fist Come,Fist Serve).
• SJF (Shortest Job First).

Penjadwaln FIFO (FIFO)
Penjadwalan FIFO ini merupakan
• Penjadwala non-preemptive (run-to-completion).
• Penjadwal tidak berprioritas.

Ketentuan
Penjadwalan FIFO adlah penjadwalan dangan ketentuan2 paling sederhana, yaitu :

Penjadwalan ini menghendaki kela2 prioritas bagi proses2 yang ada. Kelas tertinggi berjalan selam satu kwanta, kelas berikutnya berjalan selama dua kwanta , kelas berikutnya lagi berjalan empat kwanta , kelas berikutnya2 lagi berjalan delapan kwanta, dan seterusnya.

Ketentuan yang berlaku adalah sebagai berikut :
• Jalankan proses2 yang beradapada kelas prioritas tertinggi.
• Jika proses telah menggunakan seluruh kwanta yang dialokasikan maka prose situ diturunkan kelas prioritasnya.
• Proses yang masuk untuk pertama kali ke system langsung diberi kelas tertingi.

Meknisme MFQ ini dapat mencegah proses yang perlu berjalanlama mengalami swapping berulangkali dan mencegah proses2 interaktif yang singkat harus menunggu lama untuk layanan pemroses.

Penggunaan
Sistem dengan proses2 Yang banyak proses lambat, memerlukan waktu lam, dan banyak proses singkat.

FIRST-COME FIRST-SERVED (FCFS)

Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU. Dengan menggunakan algoritma ini seiap proses yang berada pada status ready dimasukkan ke dalam antrian FIFO sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi terlebih dahulu.

Misalnya ada tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki burst time 24 ms, P2 memiliki burst time 5 ms, P3 memiliki burst time 3 ms. Hitunglah wating time rata-rata dan turnaround time (burst time +  waiting time) dari ketiga proses tersebut dengan menggunakan algoritma FCFS.

Proses  Burst time

P1 24 ms

P2 5 ms

P3 3 ms

Waiting time untuk p1 adalah 0 ms (P1 tidak perlu menunggu), sedangkan untuk p2 adalah sebesar 24 ms (menunggu P1 selesai) dan untuk p3 sebesar 29 ms (menunggu P1 dan P2 selesai). Waiting time rata-ratanya adalah sebesar (0+24+29)/3 = 17,6 ms.

Turnaround time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 29 ms (dihitung dari awal kedatangan P2 hingga selesai dieksekusi), untuk p3 sebesar 32 ms. Turnaround time rata-rata untuk ketiga proses tersebut adalah (24+29+32)/3 = 28,3 ms.

Kelemahan dari algoritma ini:

a. Waiting time rata-ratanya cukup lama.

b. Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu satu 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.

SHORTEST-JOB FIRST (SJF)

Algoritma ini mempunyai cara penjadwalan yang berbeda dengan FCFS. Dengan algoritma ini maka setiap proses yang ada di antrian  ready 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:

• Kesulitan 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.

Algoritma ini dapat dibagi menjadi dua bagian yaitu:

1.  Preemptive. Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di antrian ready 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 antrian ready tersebut. Preemptive SJF sering disebut juga Shortest-Remaining-Time-First scheduling.

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

Misalnya  ada empat buah proses dengan masing-masing waktu kedatangan burst time di jelaskan pada tabel di bawah ini. Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF.

Proses   Arrival time  Burst Time

P1  0 ms  7 ms

P2  2 ms  4 ms

P3  4 ms   1 ms

P4  5 ms  4 ms

Solusi Preemptive:

Rata-rata waiting time adalah (9 + 1 + 0 +2)/4 = 3, dimana :

P1: (0-0+11-2) = 9

P2: (2-2+5-4) = 1

P3: (4-4) = 0

P4: (7-5) = 2

Rata-rata turnaround time  adalah ((9+7)+(1+4)+(0+1)+(4+2))/4 = 7

Solusi Non-Preemptive:

Rata-rata waiting time adalah  (0 + 6 + 3 + 7)/4  = 4, dimana:

P1: (0-0) = 0

P2: (8-2) = 6

P3: (7-4) = 3

P4: (12-5) = 7

Rata-rata turnaround time  adalah ((0+7)+(6+4)+(3+1)+(7+4))/4 = 8

ROUND ROBIN

Algoritma ini didesin untuk sistem  time-sharing. Proses akan mendapat jatah sebesar time quantum dengan nilai quantum umumnya sebesar 10-100 ms. Jika time quantum-nya habis atau proses sudah selesai CPU akan dialokasikan ke proses berikutnya. Tentu proses ini cukup adil karena tak ada proses yang diprioritaskan, semua proses mendapat jatah waktu yang sama dari CPU (1/n), dan tak akan menunggu lebih lama dari (n-1)/q.

Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja dengan algoritma first-come first-served. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga banyak waktu terbuang.

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 (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma First Come First Served. Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.

Misalnya ada tiga proses dengan masing-masing mendapatkan waktu quantum adalah 4 ms, maka P1 mendapatkan 4 ms pertama. Karena membutuhkan 20 ms  lagi, sesudah quantum pertama P1 di preemptive dan CPU memberikan proses berikutnya ke proses P2 dan P2 tidak memerlukan 4 ms, P2 selesai sebelum jatah quantumnya habis, kemudian CPU memberikan ke proses berikutnya yaitu P3. Ketika setaiap proses meneriman satu quantum, CPU kembali ke proses P1 untuk tambahan waktu quantum.

Proses  Burst time

P1 24 ms

P2 3 ms

P3 3 ms

Rata-rata waiting time adalah (6+4+7)/3 = 5.66

Rata-rata turnaround time adalah ((6+24)+(4+3)+(7+3))/3 = 15.67