Jenis Algoritma Berdasarkan Penjadwalan

Penjadwalan berkaitan dengan permasalahan memutuskan proses mana yang akan dilaksanakan dalam suatu sistem. Proses yang belum mendapat jatah alokasi dari CPU akan mengantri di ready queue. Algoritma penjadwalan berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan dieksekusi oleh CPU.

STRATEGI DASAR PENJADWALAN

Strategi penjadwalan proses secara umum dibedakan menjadi dua kelompok besar, yaitu penjadwalan non-preemptive dan preemptive.

1.      Non-preemptive (run-to-completion)

Pada strategi ini, begitu proses telah berjalan maka sistem operasi maupun proses lain tidak dapat mengmabil alih eksekusi prosesor. Pengalihan hanya dapat terjadi jika proses yang running sudah selesai, baik secara normal maupun abnormal. Strategi ini membahayakan sistem dan proses lain, sebab jika proses yang sedang berjalan mengalami kegagalan, crash ataupun looping tak berhingga maka sistem operasi menjadi tidak berfungsi dan proses lain tidak mendapatkan kesempatan untuk dieksekusi. Strategi penjadwalan non-preemptive umumnya digunakan pada sistem batch atau sekuensial.

2.      Preemptive

Pada strategi ini, sistem operasi dan proses lain dapat mengambil alih eksekusi prosesor tanpa harus menunggu proses yang sedang running menyelesaikan tugasnya. Penjadwalan preemptive merupakan fitur yang penting, terutama pada sistem dimana proses-proses memerlukan tanggapan prosesor secara cepat. Sebagai contoh adalah sistem real-time, dimana jika terjadi interupsi dan tidak segera dilayani maka dapat berakibat fatal. Contoh lain adalah sistem interaktif time-sharing, dimana pengguna sistem mengharapkan tanggapan yang cepat dari sistem. Secara umum, sistem konkuren seperti sistem operasi yang multitasking lebih menghendaki sistem penjadwalan preemptive.

PENJADWALAN PREEMPTIVE

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 M/K. 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 M/K yang sangat lama disebut I/O Bound, dan proses yang memiliki Burst CPU yang sangat lama disebutCPU 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.

PENJADWALAN NON PREEMPTIVE

Penjadwalan Non Preemptive ialah salah satu jenis penjadwalan dimana sistem operasi tidak pernah melakukan context switch dari proses yang sedang berjalan ke proses yang lain. Dengan kata lain, proses yang sedang berjalan tidak bisa di- interupt.

Penjadwalan Non Preemptive terjadi ketika proses hanya:

1. Berjalan dari running state sampai waiting state.
2. Dihentikan.

Ini berarti CPU menjaga proses sampai proses itu pindah ke waiting state ataupun dihentikan (proses tidak diganggu). Metode ini digunakan oleh Microsoft Windows 3.1 dan Macintosh. Ini adalah metode yang dapat digunakan untuk platforms hardware tertentu, karena tidak memerlukan perangkat keras khusus (misalnya timer yang digunakan untuk menginterupt pada metode penjadwalan Preemptive).

Dispatcher       

Komponen penjadwalan proses lainnya adalah dispatcher. Dispatcher adalah suatu rutin sistem operasi yang berfungsi untuk melakukan pengalihan eksekusi dari proses yang running ke proses yang terseleksi oleh short-term scheduler. Rutin ini memindahkan isi register prosesor, konteks prosesor, ke PCB proses yang dihentikan, kemudian mengubah statusnya menjadi ready, kemudian menginisiasi isi register prosesor menggunakan konteks prosesor yang tersimpan dalam PCB proses terpilih. Durasi waktu yang diperlukan untuk melakukan pengalihan (switching) disebut dengan dispatch latency.

JENIS-JENIS ALGORITMA PENJADWALAN ADALAH

1.  Nonpreemptive, menggunakan konsep :

a. FIFO (First In First Out) atau FCFS (First Come First Serve)

b. SJF (Shortest Job First)

c. HRN (Highest Ratio Next)

d. MFQ (Multiple Feedback Queues)

2.  Preemptive, menggunakan konsep :

a. RR (Round Robin)

b. SRF (Shortest Remaining First)

c. PS (Priority Schedulling)

d. GS (Guaranteed Schedulling)

Klasifikasi lain selain berdasarkan dapat/tidaknya suatu proses diambil secara paksa adalah klasifikasi berdasarkan adanya prioritas di proses-proses, yaitu :

1.  Algoritma penjadwalan tanpa berprioritas.

2.  Algoritma penjadwalan berprioritas, terdiri dari :

a. Berprioritas static

b. Berprioritas dinamis

Algoritma Nonpreemptive

1. First In First Out (FIFO)

First In First Out (FIFO) merupakan penjadwalan tidak berprioritas. FIFO adalah penjadwalan paling sederhana, yaitu proses-proses diberi jatah waktu pemroses berdasarkan waktu kedatangan. Pada saat proses mendapat jatah waktu pemroses, proses dijalankan sampai selesai.

Penilaian penjadwalan ini berdasarkan kriteria optimasi :

·         Adil, dalam arti resmi (proses yang datang duluan akan dilayani lebih dulu), tapi dinyatakan tidak adil karena job-job yang perlu waktu lama membuat job-job pendek menunggu. Job-job yang tidak penting dapat membuat job-job penting menunggu lama.

·         Efisiensi, sangat efisien.

·         Waktu tanggap sangat jelek, tidak cocok untuk sistem interaktif apalagi untuk sistem waktu nyata.

·         Turn around time kurang baik.

·         Throughtput kurang baik. FIFO jarang digunakan secara mandiri, tetapi dikombinasikan dengan skema lain.

·         Baik untuk sistem batch yang sangat jarang berinteraksi dengan pemakai. Contoh : aplikasi analisis numerik, maupun pembuatan tabel.

·         Sangat tidak baik (tidak berguna) untuk sistem interaktif, karena tidak memberi waktu tanggap yang baik.

·         Tidak dapat digunakan untuk sistem waktu nyata (real-time applications).

Contoh:Ada tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki burst time 24 ms, P2 memiliki burst time 3 ms, dan P3 memiliki burst time 3 ms. Hitunglah waiting time rata-rata dan turnaround time( burst time + waiting time) dari ketiga proses tersebut dengan menggunakan algoritma FCFS. 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 27 ms (menunggu P1 dan P2 selesai).

Urutan kedatangan adalah P1, P2 , P3; gantt chart untuk urutan ini adalah:

Waiting time rata-ratanya adalah sebesar(0+24+27)/3 = 17ms. Turnaround time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 27 ms (dihitung dari awal kedatangan P2 hingga selesai dieksekusi), untuk P3 sebesar 30 ms. Turnaround time rata-rata untuk ketiga proses tersebut adalah (24+27+30)/3 = 27 ms.

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.

Misalkan proses dibalik sehingga urutan kedatangan adalah P3, P2, P1. Waiting time adalah P1=6; P2=3; P3=0. Average waiting time: (6+3+0)/3=3.

2. Shortest Job First (SJF)

Penjadwalan ini mengasumsikan waktu berjalannya proses sampai selesai telah diketahui sebelumnya. Mekanismenya adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai, sehingga memberikan efisiensi yang tinggi dan turn around time rendah dan penjadwalannya tak berprioritas.

Contoh :

Terdapat empat proses (job) yaitu A,B,C,D dengan waktu jalannya masing-masing adalah 8,4,4 dan 4 menit. Apabila proses-proses tersebut dijalankan, maka turn around time untuk A adalah 8 menit, untuk B adalah 12, untuk C adalah 16 dan untuk D adalah 20. Apabila keempat proses tersebut menggunakan penjadwalan shortest job fisrt, maka turn around time untuk B adalah 4, untuk C adalah 8, untuk D adalah 12 dan untuk A adalah 20.

Karena SJF selalu memperhatikan rata-rata waktu respon terkecil, maka sangat baik untuk proses interaktif. Umumnya proses interaktif memiliki pola, yaitu menunggu perintah, menjalankan perintah, menunggu perintah dan menjalankan perintah, begitu seterusnya. Masalah yang muncul adalah tidak mengetahui ukuran job saat job masuk. Untuk mengetahui ukuran job adalah dengan membuat estimasi berdasarkan kelakukan sebelumnya. Prosesnya tidak datang bersamaan, sehingga penetapannya harus dinamis. Penjadwalan ini jarang digunakan karena merupakan kajian teoritis untuk pembandingan turn around time.

3. Highest Ratio Next (HRN)

Highest Ratio Next merupakan strategi penjadwalan dengan prioritas proses tidak hanya berdasarkan 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 dilayani.

4.      Multilevel Feedback Queue

Algoritma ini mirip sekali dengan algoritma multilevel queue. Perbedaannya ialah algoritma ini mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Hal ini menguntungkan proses interaksi karena proses ini hanya memakai waktu CPU yang sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini akan dinaikkan tingkatannya. Biasanya prioritas tertinggi diberikan kepada proses dengan CPU burst terkecil, dengan begitu CPU akan terutilisasi penuh dan M/K dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar.

 

Gambar 14.7. Multilevel Feedback Queue

Algoritma ini didefinisikan melalui beberapa parameter, antara lain:

a.       Jumlah antrian.

b.      Algoritma penjadwalan tiap antrian.

c.       Kapan menaikkan proses ke antrian yang lebih tinggi.

d.      Kapan menurunkan proses ke antrian yang lebih rendah.

e.       Antrian mana yang akan dimasuki proses yang membutuhkan.

Dengan pendefinisian seperti tadi membuat algoritma ini sering dipakai, karena algoritma ini mudah dikonfigurasi ulang supaya cocok dengan sistem. Tapi untuk mengatahui mana penjadwal terbaik, kita harus mengetahui nilai parameter tersebut.

Multilevel feedback queue adalah salah satu algoritma yang berdasar pada algoritma multilevel queue. Perbedaan mendasar yang membedakan multilevel feedback queue dengan multilevel queue biasa adalah terletak pada adanya kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah dengan prioritas yang lebih rendah ataupun lebih tinggi, misalnya pada contoh berikut.

1.      Semua proses yang baru datang akan diletakkan pada queue 0 ( quantum= 8 ms).

2.      Jika suatu proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan ke queue 1 ( quantum= 16 ms).

3.      Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue 0, dan jika suatu proses di queue 1 tidak selesai dalam 16 ms, maka proses tersebut akan dipindahkan ke queue 2.

4.      Queue 2 akan dikerjakan bila queue 0 dan 1 kosong, dan akan berjalan dengan algoritma FCFS.

Disini terlihat bahwa ada kemungkinan terjadinya perpindahan proses antar queue, dalam hal ini ditentukan oleh time quantum, namun dalam prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dengan mendefinisikan terlebih dahulu parameter-parameternya, yaitu:

1.      Jumlah antrian.

2.      Algoritma internal tiap queue.

3.      Aturan sebuah proses naik ke antrian yang lebih tinggi.

4.      Aturan sebuah proses turun ke antrian yang lebih rendah.

5.      Antrian yang akan dimasuki tiap proses yang baru datang.

Contoh: Terdapat tiga antrian; Q1=10 ms, FCFS Q2=40 ms, FCFS Q3=FCFS proses yang masuk, masuk ke antrian Q1. Jika dalam 10 ms tidak selesai, maka proses tersebut dipindahkan ke Q2. Jika dalam 40 ms tidak selesai, maka dipindahkan lagi ke Q3. Berdasarkan hal-hal di atas maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai dengan kebutuhan sistem. Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan.

Algoritma Preemptive

1.      Round Robin

Algoritma ini menggilir proses yang ada di antrian. Proses akan mendapat jatah sebesar time quantum. 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 yaitu (1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.

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

Gambar 14.4. Urutan Kejadian Algoritma Round Robin

Gambar 14.5. Penggunaan Waktu Quantum

2. Shortest Remaining First (SRF)

Merupakan :

·         Penjadwalan berprioritas.dinamis.

·         Preemptive untuk timesharing

·         Melengkapi SJF

Pada SRF,  proses dengan sisa waktu jalan diestimasi terendah dijalankan, termasuk proses-proses yang baru tiba.Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai.Pada SRF, proses yang sedang berjalan (running) dapat diambil alihproses baru dengan sisa waktu jalan yang diestimasi lebih rendah.

Kelemahan :

·         Mempunyai overhead lebih besar dibanding SJF. SRF perlu penyimpanan waktu layanan yang telah dihabiskan job dan kadang-kadang harus menangani peralihan.

·         Tibanya proses-proses kecil akan segera dijalankan.

·         Job-job lebih lama berarti dengan lama dan variasi waktu tunggu lebih lama dibanding pada SJF.

SRF perlu menyimpan waktu layanan yang telah dihabiskan , menambah overhead. Secara teoritis, SRF memberi waktu tunggu minimum tetapi karena overhead peralihan, maka pada situasi tertentu SFJ bisa memberi kinerja lebih baik dibanding SRF.

3.      Priority Scheduling

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:

1.      Time limit.

2.      Memory requirement.

3.      Akses file.

4.      Perbandingan antara burst M/K dengan CPU burst.

5.      Tingkat kepentingan proses.

Priority scheduling juga dapat dijalankan secara preemptive maupun non-preemptive. Pada preemptive, jika ada suatu proses yang baru datang memiliki prioritas yang lebih tinggi daripada proses yang sedang dijalankan, maka proses yang sedang berjalan tersebut dihentikan, lalu CPU dialihkan untuk proses yang baru datang tersebut. Sementara itu, pada non-preemptive, proses yang baru datang tidak dapat menganggu proses yang sedang berjalan, tetapi hanya diletakkan di depan queue.

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.

Contoh: Setiap 10 menit, prioritas dari masing-masing proses yang menunggu dalam queue dinaikkan satu tingkat. Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam 21 jam 20 menit, proses tersebut akan memiliki prioritas 0, yaitu prioritas yang tertinggi (semakin kecil angka menunjukkan bahwa prioritasnya semakin tinggi).

4. Guaranteed Schedulling (GS)

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.