Scheduling

 1. First-Come First- Serve (FCFS)

Merupakan algoritma yang paling sederhana dalam penjadwalan proses. Proses yang melakukan request terhadap CPU akan diproses oleh CPU. Implementasinya dengan menggunakan algoritma First In First Out – FIFO.  FCFS bersifat non-preemptive yaitu proses yang dikerjakan oleh CPU tidak dapat diinterupsi oleh proses yang lainnya.

Sebagai contoh :

Proses	Burst
P1	10
P2	1
P3	2
P4	1
P5	5

Proses diasumsikan datang bersamaan dan masuk dalam antrian penggunaan CPU. Proses akan dikerjakan berdasarkan nomor urutan proses, sedangkan yang lainnya menunggu sampai proses diatasnya selesai dikerjakan.

Dari Gant Chart dapat diperoleh waktu tunggu proses dari CPU yang dapat diambil waktu rata-ratanya.

Waiting Time P1 = 0, Waiting Time P2 = 10, Waiting Time P3 = 11, Waiting Time P4 = 13, Waiting Time P5 = 14.

Avarage Waiting Time (AWT) =  (WT P1 + WT P2 + WT P3 + WT P4 + WT P5)/5

Avarage Waiting Time (AWT) =  (0 + 10 + 11 + 13 + 14)/5 = 9.6 ms

FCFS  dapat juga bekerja dengan adanya prioritas terhadap proses, prioritas dengan nilai terkecil akan diberi status sebagai prioritas tinggi dan akan dikerjakan terlebih dahulu.

Proses	Burst	Prioritas
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

Avarage Waiting Time (AWT) =  (0 + 1 + 6 + 16 + 18)/4 = 8.2 ms

Masalah utama pada FCFS adalah adanya antrian dari proses yang menjadi panjang karena waiting time yang rata-rata panjang. Proses-proses yang telah  berada dalam posisi ready akan tetapi CPU belum dapat memprosesnya. Hal ini yang disebut dengan starvation.

2. Shortest Job First (SJF)

Pendekatan  SJF berbeda dengan FCFS, algoritma SJF tergantung dengan panjang proses yang ada pada queue. Ketika CPU akan melakukan  proses, CPU akan memilik proses dengan CPU burst paling kecil. SJF dapat bekerja dengan mode preemptive maupun non-preemptive.

1.     Non-preemptive

Proses	Burst
P1	6
P2	8
P3	7
P4	3

Gant chat :

Waiting Time P1 = 3

Waiting Time P2 = 16

Waiting Time P3 = 9

Waiting Time P4 = 0

Avarage Waiting Time = (3 + 16 + 9 + 0)/4 = 7 ms

b. Preemptive

SJF dengan waktu kedatangan (arrival time) berbeda.

Proses	Arrival	Burst
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Proses akan di-preemptive jika ada proses masuk, dah penjadwalan dilakukan ulang dengan membandingkan proses yang masuk dengna proses yang sedang dijalankan. Sebaga contoh pada tabel ketika P1 dijalankan dengna membutuhkan 8 ms, akan tetapi datang burst dari proses P2 dengan burst time 4 ms pada deti ke-1. Proses akan berhenti pada detik 1 kemudian membandingkan proses P1 dengan P2. Karena P2 < P1 maka proses P1 akan dikembalikan ke ready queue dengan P1 = 7 dan memproses P2. Demikian seterusnya.

Gant chart :

Waiting Time P1 = 0 + (10-1) = 9

Waiting Time P2 = 1-1 = 0

Waiting Time P3 = 17-2 = 15

Waiting Time P4 =  5-3 = 2

Average Waiting Time = (9 + 0 + 15 + 2 )/4 =  6.5 ms

3. Round Robin (RR)

Round Robin hampir mirip dengan FCFS akan tetapi terdapat proses perpindahan antar proses dimana satu proses melakukan interupsi terhadap proses yang lainnya atau disebut juga dengan preemptive. Proses preemptivedengan menggunakan time quantum atau time slice.

Sebagai contoh :

Proses	Burst
P1	24
P2	3
P3	3

Dengan time slice sebesar 4 ms, penjadwalan yang terjadi adalah sebagai berikut:

P1 mendapatkan kesempatan pada 4 ms (time slice) pertama, karena P1 > time slice maka P1 hanya akan diproses selama time slice, sisa P1 sebesar P1 – time slice akan di preemptive-kan. Selanjutnya penjadwalan akan beralih ke P2, karena P2 < time slice maka P2 diproses hingga selesai, setelah itu penjadwalan beralih ke P3 dan seterusnya.

Waiting Time P1 = 0 + (10 – 4) = 6

Waiting Time P2 = 4

Waiting Time P3 = 7

Average Waiting Time = (6 + 4 + 7 )/3 = 5.66 ms

Pada algoritma RR, tidak ada proses yang dikerjakan dalam satu waktu lebih dari time slice yang disediakan. Jika terdapat n proses pada queue dengan time slice sebesar q, maka setiap proses akan mendapatkan waktu 1/n dengan masing-masing proses sebesar q .Setiap proses akan menunggu setidaknya sebanyak (n-1)x q untuk proses selanjutnya. Sebagai contoh terdapat 5 proses dengan time slice sebesar 20 ms maka masing-masing proses akan mendapatkan waktu sebanyak 20 ms setiap 100 ms.

Performance dari RR tergantung pada ukuran time slice. Jika time slice terlalu besar maka RR akan sama atau mendekati performance FCFS. Akan tetapi jika time slice kecil maka muncul problem context switch yang terlalu banyak, yaitu proses perpindahan dari satu proses ke proses lain yang akan menimbulkan permasalahan. Hal ini terjadi karena perbedaan kecepatan processor dan memori, dengan terjadinya perpindahan yang terlalu sering proses pembacaan CPU ke memori dan sebaliknya akan membebani sistem.

HRRN (highest Response Ratio Next)

merupakan penjadwalan non-preemptive, mengunakan proritas dinamis. Penjadwalan ini memperbaiki Shortest Job Frist perioritas proses tidak hanya merupakan fungsi waktu layanan,tetapi jumlah waktu tunggu proses. HRRN dihitung berdasarkan rumus :

            Prioritas=(waktu tunggu + waktu layanan)/waktu layanan

Algoritma ini merupakan Penjadwalan berprioritas dinamis Penjadwalan untuk mengoreksi kelemahan SJF. Adalah strategi penjadwalan dengan prioritas proses tidak hanya merupakan

fungsi waktu layanan tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemroses, proses berjalan sampai selesai. Prioritas dinamis HRN dihitung berdasarkan rumus :

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. Disebut HRN, karena waktu tunggu ditambah waktu layanan adalah waktu tanggap, yang berarti waktu tanggap tertinggi yang harus dilayan

GS (Guaranteed Schedulling )

merupakan penjadawalan preemptive menggunakan prioritas dinamis. Jika terdapat N pemakai, setiap pemakai diusahakan senantiasa mendapatkan(1/N) waktu Prosesor. Pada saat terjadi penjadwalan dihitung rasio waktu running semenjak login setiap pemakai dan waktu pemakai prosesor secara keseluruhan.

Penjadwalan ini memberikan janji yang realistis (memberi daya pemroses yang sama) untuk membuat dan menyesuaikan performance adalah jika ada N pemakai, sehingga 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. Kemudian jumlah waktu CPU, yaitu waktu mulai login dibagi dengan n, sehingga lebih mudah menghitung rasio waktu CPU. Karena jumlah waktu pemroses tiap pemakai dapat diketahui, maka dapat dihitung rasio antara waktu pemroses

yang sesungguhnya harus diperoleh, yaitu 1/N waktu pemroses seluruhnya dan waktu pemroses yang telah diperuntukkan proses itu. Rasio 0,5 berarti sebuah proses hanya punya 0,5 dari apa yang waktu CPU miliki dan rasio 2,0 berarti sebuah proses hanya punya 2,0 dari apa yang waktu CPU miliki. Algoritma akan menjalankan proses dengan rasio paling rendah hingga naik

ketingkat lebih tinggi diatas pesaing terdekatnya. Ide sederhana ini dapat diimplementasikan ke sistem real-time dan memiliki penjadwalan berprioritas dinamis.

MLQ ( Multi LeveL Queues )

merupakan penjadwalan preemptive, Peroses-proses dibagi atas group dan ditempatkan pada antrian yang berbeda. 

Dari gambar tersebut terlihat bahwa akan terjadi pengelompokan proses-proses berdasarkan prioritasnya. Kemudian muncul ide untuk menganggap kelompok-kelompok tersbut sebagai sebuah antrian-antrian kecil yang merupakan bagian dari antrian keseluruhan proses, yang sering disebut dengan algoritma multilevel queue.

Dalam hal ini, dapat dilihat bahwa seolah-olah algoritma dengan prioritas yang dasar adalah algoritma multilevel queue dimana setiap queue akan berjalan dengan algoritma FCFS yang memiliki banyak kelemahan. Oleh karena itu, dalam prakteknya, algoritma multilevel queue memungkinkan adanya penerapan algoritma internal dalam masing-masing sub-antriannya yang bisa memiliki algoritma internal yang berbeda untuk meningkatkan kinerjanya.

Berawal dari priority scheduling, algoritma ini pun memiliki kelemahan yang sama dengan priority scheduling, yaitu sangat mungkin bahwa suatu proses pada queue dengan prioritas rendah bisa saja tidak mendapat jatah CPU. Untuk mengatasi hal tersebut, salah satu caranya adalah dengan memodifikasi algoritma ini dengan adanya jatah waktu maksimal untuk tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu, maka prosesnya akan dihentikan dan digantikan oleh antrian dibawahnya, dan tentu saja batas waktu untuk tiap antrian bisa saja sangat berbeda tergantung pada prioritas masing-masing antrian.

9. MFQ (Multi Level feedback Queues)

merupakan algoritma penjadwalan preemptive berprioritas dinamis berdasarkan jumlah Quantum Time, MFQ menggunakan sejumlah antrian dengan prioritas dan Quantum Time yang berbeda.Algoritma ini merupakan penjadwalan berprioritas dinamis Penjadwalan ini  bertujuan untuk mencegah (mengurangi) banyaknya swapping dengan proses-proses yang sangat banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlah kwanta) lebih banyak dalam satu waktu. Penjadwalan ini juga menghendaki kelas-kelas prioritas bagi proses-proses yang ada. Kelas tertinggi berjalan selama satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelas berikutnya berjalan empat kwanta, dan seterusnya.

Proses yang masuk untuk pertama kali ke sistem langsung diberi kelas tertinggi. Mekanisme ini mencegah proses yang perlu berjalan lama swapping berkali-kali dan mencegah proses-proses interaktif yang singkat harus menunggu lama.