PENJADWALAN DALAM MANAJEMEN PROSES SISTEM OPERASI MODERN

Ketika komputer menjalankan multiprogram, sering mendapati beberapa proses untuk bersaing diproses CPU pada saat yang sama. Situsasi ini terjadi setiap kali dua atau lebih dari proses sudah memasuki keadaan siap untuk diproses. Jika hanya satu CPU yang tersedia maka harus ada pilihan proses yang akan dijalankan berikutnya. Ini lah salah satu bagian dari tugas sistem operasi dalam manajemen proses yaitu schedulling atau penjadwalan dan algoritmanya disebut algoritma penjadwalan.

A.Konsep Dasar dan Kriteria Penjadwalan

Penjadwalan merupakan kumpulan kebijaksanaan dan mekanisme dari sistem operasi yang berkaitan dengan urutan kerja yang akan dilaksanakan sistem komputer. Penjadwalan bertugas untuk memutuskan proses mana yang harus berjalan dan kapan proses itu berjalan.

Kriteria yang digunakan untuk mengukur kinerja penjadwalan antara lain adalah :

1.      Fairness (adil)

Kriteria yang pertama adalah fairnes atau adil, yang dimaksud dari adil adalah proses-proses diperlakukan dan mendapatkan layanan yang sama oleh CPU. Layanan ini berupa jatah waktu pemrosesan yang sama dan tidak ada proses yang tidak dilayani.

2.      Eficiency (efisiensi)

Efisiensi atau utilisasi pemroses dihitung dengan perbandingan (rasio) waktu. Sasaran penjadwalan adalah menjaga agar CPU tetap bekerja optimal sehingga mencapai efisiensi maksimum atau CPU tidak dalam proses menganggur (tidak melakukan apapun).

3.      Response time (waktu tanggap)

Respone time merupakan waktu yang dibutuhkan dari proses saat minta dilayani hingga proses pertama yang dilayani. Respone time dibedakan untuk :

a.       Sistem interaktif

Sistem interaktif ini didefinisikan sebagai waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukkan atau transaksi sampai hasil pertama muncul di layar. Waktu tanggap ini disebut terminal response time

b.      Sistem waktu nyata

Sistem waktu nyata Didefinisikan sebagaiwaktu dari saat kejadian (internal atau eksternal) sampai instruksi pertama rutin layanan yang dimaksud dieksekusi, disebut event response time.

4.      Turn arround time

Turn around time merupakan banyaknya waktu yang diperlukan untuk mengeksekusi proses, dari mulai menunggu untuk meminta tempat di memori utama, menuggu di ready queue, eksekusi oleh CPU dan mengerjakan I/O.

5.      Throughput

Throughput merupakan banyaknya proses yang selesai dikerjakan dalam satu satuan waktu.

Adapun tujuan atau sasaran dari penjadwalan berdasarkan kriteria-kriteria tersebut antara lain :

1.      Terjaminnya tiap proses mendapat perlakuan yang adil dalam pelayanan yang dilakukan oleh CPU.

2.      Menjaga agar CPU tetap dalam keadaan sibuk sehingga didapatkan efisiensi kinerja yang optimal.

3.      Meminimalkan waktu tanggap

4.      Meminimalkan turn around time

5.      Memaksimalkan CPU untuk memproses job dalam satu interval waktu sehingga semakin besar angka throughput maka semakin banyak job yang dapat dilakukan sistem.

B.     Macam Penjadwalan

Terdapat tiga macam penjadwalan dalam sistem operasi antara lain:

1.      Penjadwalan jangka pendek (short term scheduller)

Penjadwalan jangka pendek bertugas untuk menjadwalkan CPU diantara proses yang ready di memori utama.

2.      Penjadwalan jangka menengah (medium term scheduller)

Penjadwalan ini bertugas memindahkan proses yang tertunda dari memori utama ke memori sekunder atau disebut swapping. Sehingga ketika proses yang tertunda hilang maka proses dimasukkan kembali ke memori utama dan menjadi ready.

3.      Penjadwalan jangka penjang (long term scheduller)

Penjadwalan ini bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi.

C.    Kapan Harus Dilakukan Penjadwalan

Menurut Tanenbaum (2009) Masalah utama dalam penjadwalan adalah ketika membuat keputuasan penjadwalan itu. Terdapat beberapa situasi dimana penjadwalan diperlukan. Pertama, ketika sebuah proses baru dibuat, keputusan harus dibuat apakah akan menjalankan proses induk atau proses anak. Karena kedua proses berada dalam keadaan siap, ini adalah keputusan penjadwalan yang normal dan dapat berjalan baik yaitu scheduler dapat dengan sah memilih untuk menjalankan proses induk ataupun proses anak.

Kedua, keputusan penjadwalan harus dilakukan ketika sebuah proses keluar. Proses itu tidak bisa lagi berjalan (karena sudah tidak ada lagi) sehingga beberapa proses lain harus dipilih dari serangkaian proses yang telah siap.

Ketiga, ketika sebuah blok proses pada I/O, pada semaphore, atau beberapa alasan lainnya proses lain harus dipilih untuk dijalankan. Terkadang pemblokiran mungkin memainkan peran dalam menentukan pilihan. Sebagai contoh, jika A adalah proses penting dan A menunggu proses B untuk selesai, membiarkan proses B untuk berjalan hingga selesai sehingga dengan demikian proses A dapat melanjutkan proses. Masalahnya adalah scheduler umumnya tidak memiliki informasi yang diperlukan untuk mengambil ketergantungan ini.

Keempat, ketika sebuah interupsi I/O terjadi, keputusan penjadwalan dapat dilakukan jika interupsi datang dari I/O device yang telah menyelesaikan pekerjaanya, beberapa proses yang diblokir menunggu I/O yang mungkin sekarang siap untuk dijalankan. Keputusan ini terserah pada scheduler untuk memutuskan apakan akan menjalankan proses baru yang telah siap, proses yang berjalan pada saat interupsi atau beberapa proses ketiga.

Jika hardware clock memberikan interupsi berkala pada 50 dan 60 Hz atau beberapa frekuensi lainnya, keputusan penjadwalan dapat dibuat pada setiap clok interrupt. Algoritma penjadwalan dapat dibagi menjadi dua kategori sehubungan dengan bagaimana menangani clock interrupt. Pertama adalah nonpreemptive scheduling yaitu proses diberi jatah waktu oleh pemroses, maka pemroses tidak dapat diambil oleh proses lain sampai proses itu selesai.

Sebaliknya, algoritma penjadwalan preemptive mengambil proses dan memungkinkan untuk berjalan maksimal diwaktu yang tetap. Jika masih berjalan pada akhir waktu interval, itu ditangguhkan dan scheduler mengambil proses ain untuk menjalankan (jika ada yang tersedia). Melakukan penjadwalan preemptive memerlukan terjadinya clock interrupt di akhir interval waktu untuk memberikan CPU kembali ke scheduler. Jika tidak ada waktu yang tersedia maka penjadwalaan nonpreemptive adalah satu-satunya pilihan yang tersedia.

D.    Algoritma Penjadwalan

Seperti yang telah dijabarkan diatas algoritma penjadwalan dibedakan menjadi dua kategori yaitu nonpreemptive dan preemptive. Untuk algoritma nonpreemptive menggunakan konsep-konsep seperti FIFO (First In First Out) atau FCFS (First Come First Serve), SJF (Shortest Job First), HRN (Highest Ratio Next), MFQ (Multiple Feedback Queues). Sedangkan algoritma preemptive menggunakan konsep-konsep seperti Round Robin, SRF (Shortest Remaining First), Priority Schedulling dan Guaranteed Schedulling.

1.      Algoritma nonpreemptive

a.       First In First Out (FIFO)

Algoritma ini merupakan algoritma paling sederhana yang digunakan CPU. Setiap proses yang sudah dalam keadaan ready dimasukkan kedalam FIFO queue atau antrian dengan prinsip first in first out sesuai dengan waktu kedatangannya. Proses yang lebih dahulu masuk yang akan dieksekusi.

Misal terdapat tiga proses yang dengan urutan P1, P2 dan P3 dengan waktu CPU-burst dalam milidetik yang diberikan sebagai berikut :

Process	Burst Time
P1	24
P2	3
P3	3

Gant chart dengan penjadwalan FCFS adalah sebagai berikut :

Waktu tunggu untuk P1 adalah 0, P2 adalah 24 dan P3 adalah 27 sehingga rata-rata waktu tunggu adalah (0+24+27(/3 = 17 milidetik. Sedangkan apabila proses dtang degnan urutan P2, P3 dan P1 hasil penjadwalan CPU dapat dilihat sebagai berikut

Waktu tunggu sekarang untuk P1 adalah 6, P2 adalah 0 dan P3 adalah 3 sehingga diperoleh rata-rata waktu tunggu menjadi 3 milidetik. Rata-rata ini menjadi lebih baik dibandingkan dengan waktu tunggu yang sebelumnya.

Algoritma FIFO termasuk nonpreemptive karena sekali CPU dialokasikan pada suatu proses maka proses tersebut tetap akan memakai CPU sampai proses tersebut melepaskannya.

b.      SJF (Shortest Job First)

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

Misal terdapat empat proses yaitu A, B, C, D dengan waktu jalan masing-masing adalah 8,4,4 dan 4 menit. Apabila 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 first, 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

c.       HRN (Highest Ratio Next)

Higest Ratio Next merupakan penjadwalan dengan prioritas proses 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.

d.      MFQ (Multiple Feedback Queues)

Penjadwalan ini untuk mencegah atau mengurangi banyaknya swapping dengan proses-proses yang sangat banyak menggunakan CPU (karena menyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlah kuantum) 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. Ketentuan yang berlaku adalah menjalankan proses pada kelas tertinggi, jika proses menggunakan seluruh kwanta yang dialokasikan maka diturunkan kelas prioritasnya dan proses yang masuk untuk pertama kali ke sistem akan 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.

2.      Algoritma preemptive

a.       Round Robin

Merupakan salah satu penjadwalan tertua, paling sederhana, paling adil dan paling banyak digunakan. Setiap proses diberikan interval waktu yang disebut kuantum selama itu diperbolehkan dijalankan. Jika proses masih berjalan pada akhir kuantum, CPU di tahan eksekusinya dan diberikan kepada proses lain. Jika proses telah diblokir atau selesai sebelum kuantum terlampaui maka CPU akan dialihkan.

Masalah yang timbul dalam menerapkan Round Robin adalah menentukan besar kuantum. Jika kuantum terlalu besar akan menyebabkan waktu tanggap besar dan turn around time jadi rendah. Jika kuantum terlalu kecil akan menyebabkan peralihan proses terlalu banyak sehingga menurunkan efisiensi proses.

Penjadwalan ini baik untuk sistem interactive-time sharing dimana kebanyakan waktu digunakan untuk menunggu kejadian eksternal seperti text editor, kebanyakan waktu program adalah menunggu keybord sehingga dapat dijalankan proses lainnya. Penjadwalan ini tidak cocok untuk sistem waktu nyata apalagi hard real time applications.

b.      SRF (Shortest Remaining First)

Merupakan penjadwalan yang berprioritas dinamis. Pada SRF proses dengan sisa waktu jalan terendah akan dijalankan termasuk proses yang baru tiba. Apabila pada SJF begitu proses telah dieksekusi proses akan dijalankan sampai selsesai sedangkan pada SRF proses yang sedang berjalan dapat diambil alih proses yang baru datang dengan sisa waktu jalan yang lebih rendah.

            Kelemahan dari SRF adalah mempunyai overhead lebih besar dibanding SJF karena SRF perlu menyimpan waktu layanan yang telah dihabiskan job dan kadang harus menangani perlihan dengan keadaan seperti itu SRF perlu menambah overhead. Secara teoritis SRF memberi waktu tunggu minimum tetapi karena overhead perlihan, maka pada situasi tertentu SJF dapat lebih baik daripada SRF.

c.       Priority Schedulling

Penjadwalan menggunakan Priority Schedulling dengan memberikan prioritas pada proses dan proses yang berprioritas paling tinggi mendapat jatah waktu running terlebih dauhulu. Jika beberapa proses memiliki prioritas yang sama maka akan digunakan algoritma FIFO.

Penjadwalan berprioritas terdiri dari dua skema yaitu non preemptive dan preemptive.Jika ada proses P1 yang datang pada saat P0 sedang berjalan, maka akan dilihat prioritas P1.Seandainya prioritas P1 lebih besar dibanding dengan prioritas P0, maka pada non-preemptive, algoritma tetap akan menyelesaikan P0 sampai habis CPU burst-nya, dan meletakkan  P1 pada posisi head queue. Sedangkan pada preemptive, P0 akan dihentikan dulu, dan CPU ganti dialokasikan untuk P1.

Misalnya terdapat lima proses P1, P2, P3, P4  dan P5  yang datang secara berurutan dengan CPU burstdalam milidetik.

Process	Burst Time	Priority
P1	10	3
P2	1	1
P3	2	3
P4	1	4
P5	5	2

Penjadwalan proses dengan algoritma priority dapat dilihat pada gant chart berikut :

Waktu tunggu untuk P1adalah 6, P2adalah 0, P3adalah 16, P4 adalah 18 dan P5adalah 1 sehingga rata-rata waktu tunggu adalah (6 + 0 +16 + 18 + 1)/5 = 8.2 milidetik.

d.      Guaranteed Schedulling

Penjadwalan ini memberikan jaminan pemrosesan yang sama untuk membuat dan menyesuaikan performa. Jika ada n user yang login maka setiap proses (pemakai) akan mendapat 1/n dari daya CPU. Untuk mewujudkannya, sistem harus menyimpan infromasi 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 akan lebih mudah menghitung 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.