Selain mengelola siklus hidup proses, sistem operasi bertanggung jawab untuk melakukan penjadwalan proses. Sistem operasi modern umumnya merupakan sistem multitasking, yaitu sistem yang memiliki kemampuan untuk menjalankan sejumlah proses secara konkuren. Untuk mendapat- kan efek konkuren maka sistem operasi bertugas melakukan penjadwalan terhadap proses-proses untuk menggunakan prosesor secara berselang- seling. inter leaving
Kompleksitas algoritma penjadwalan proses yang dibutuhkan oleh setiap sistem komputer berbeda satu sama lainnya. Sebagai contoh, pada sistem operasi mula-mula, yang mengeksekusi proses secara batch, tugas pen- jadwalan proses hanya mengalihkan eksekusi dari proses yang telah selesai ke proses berikutnya yang sudah menunggu. Sedangkan pada sis- tem mainframe yang melayani operasi batch dan juga timesharing sejumlah pengguna lewat terminal, algoritma penjadwalan harus melaku- kan seleksi dari sejumlah proses dan permintaan layanan secara interaktif dari pengguna. Umumnya permintaan interaktif dari pengguna akan diprioritaskan dalam algoritma penjadwalan agar memberikan tanggapan waktu (response time) yang baik dan cepat bagi pengguna.
Sementara pada komputer desktop atau PC (Personal Computer) yang hanya mengakomodasi interaksi dengan satu pengguna pada setiap waktu algoritma penjadwalan umumnya akan memilih proses sedang dijalankan oleh pengguna dibandingkan proses sistem yang berjalan secara background.
Pada sistem komputer yang saling terhubung dan berinteraksi lewa jaringan, proses-proses yang berjalan sering kali berebut waktu untuk memakai prosesor. Sebagai contoh, seorang pengguna sedang mengirim email serta melakukan download berkas dari internet. Dalam kasus ini, urutan penjadwalan akan sangat memengaruhi persepsi pengguna terhadap kinerja sistem.
Sebagai contoh, jika proses download berkas yang umumnya cukup lama, misalnya membutuhkan 30 detik diprioritaskan maka waktu tunggu pe- ngiriman email yang sebenarnya hanya membutuhkan 2 detik akan terasa lama sekali, yaitu menjadi 32 detik. Pengguna akan mendapatkan persepsi bahwa pengiriman email lambat sekali, yaitu dari yang seharusnya 2 detik menjdai 32 detik.
Namun jika yang diprioritas adalah pengiriman email maka proses download berkas akan menjadi 32 detik, dari yang seharusnya 30 detik. Dari persepsi pengguna, tambahan waktu tunggu 2 detik tidak terlalu terasa dan cenderung dapat diterima.
Selain terkait sistem komputer yang digunakan, rancang bangun algorit- ma penjadwalan perlu memperhitungkan perbandingan antara jumlah operasi komputasi prosesor dengan jumlah operasi I/O dari suatu proses. Proporsi keduanya berbeda-beda dari satu proses ke proses lainnya.
Sebagai catatan, proses yang sedang melakukan operasi I/O akan berstatus blocked dan tidak ikut dalam penjadwalan proses. Proses-proses yang banyak siklus operasi I/O nya atau disebut I/O-bound, umumnya memili- ki durasi komputasi dan penggunaan prosesor yang singkat. Sementara proses yang sebagian besar siklus hidupnya melakukan komputasi atau disebut dengan compute-bound, proporsi operasi I/O sangat kecil. Pada sistem yang demikian, prioritas diberikan pada proses yang VO bound. Jadi begitu proses yang I/O bound beralih dari blocked ke ready, sistem operasi segera menjadwalnya dan kemungkinan proses tersebut kemudian akan memanggil operasi I/O berikutnya. Dengan demikian, kesinam- bungan dari proses I/O bound tetap terjaga, sedangkan selama operasi I/Onya sistem operasi dapat menjadwal proses-proses yang compute bound. Cara yang demikian dapat meningkatkan keluaran per satuan waktu (throughput) proses secara keseluruhan.
Subbab berikutnya akan menjelaskan definisi penjadwalan, komponen penjadwalan, kriteria dalam perancangan algoritma penjadwalan, strategi dasar penjadwalan serta hal-hal yang memicu terjadinya penjadwalan. Setelah itu akan dibahas berbagai macam algoritma penjadwalan proses yang ada.
4.2.1 DEFINISI DAN KOMPONEN PENJADWALAN PROSES
Penjadwalan proses dapat didefinisikan sebagai kumpulan kebijaksanaan dan mekanisme sistem operasi yang mengatur urutan dan jangka waktu eksekusi proses-proses yang aktif. Penjadwalan bertugas memilih proses, menentukan kapan serta berapa lama proses tersebut boleh menggunakan prosesor.
Untuk menjalankan penjadwalan proses, sistem operasi membutuhkan sejumlah komponen yang meliputi:
1. Antrian penjadwalan(Scheduling Queue)
Berbagai jenis antrian penjadwalan proses dapat dilihat pada Gambar 4.2. Umumnya antrian-antrian ini diimplementasikan dalam bentuk link-list. Header antrian berisi referensi atau pointer ke PCB suatu proses, yang pada gilirannya akan berisi referensi ke PCB proses lainnya. Header antrian juga berisi referensi ke PCB proses yang berada pada ujung antrian. Pada gambar terlihat proses 2 dan 7 berada pada antrian ready. Ini berarti salah satu dari proses 2 atau 7 berstatus running, sedangkan sisanya berstatus ready. Proses 3, 5, 6, 14 berstatus blocked karena menunggu operasi I/O. Proses 5 sedang menunggu input dari terminal dan ditempatkan pada antrian terminal unit 0, sedangkan proses 3, 6, 14 sedang menunggu operasi pada disk unit 0 dan ditempatkan pada antrian disk tersebut.
2. Penjadwal (Scheduler)
a. Penjadwal Jangka Pendek (Short-term scheduler)
b. Penjadwalan Jangka Menengah (Medium-term scheduler)
c. Penjadwal Jangka Panjang (Longterm-scheduler atau job scheduler)
3. 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 ter- seleksi oleh short-tem scheduler. Rutin ini memindahkan isi register prosesor, konteks prosesor, ke PCB proses yang dihentikan, kemudian mengubah statusnya menjadi ready, kemudian menginisiasi isi regis- ter prosesor menggunakan konteks prosesor yang tersimpan dalam PCB proses terpilih. Durasi waktu yang diperlukan untuk melakukan pengalihan (switching) disebut dengan dispatch latency.
4.2.2 KRITERIA PENJADWALAN PROSES
Dalam melakukan penjadwalan proses, sistem operasi mempertimbang- kan sejumlah faktor antara lain:
1. Keadilan (fairness)
Proses-proses harus diperlakukan sama, yaitu mendapatkan jatah waktu prosesor secara adil, namun tidak selalu berarti jatah waktu yang sama. Selain itu perlu dipastikan tidak terjadi starvation, yaitu terdapat proses yang tidak terlayani dalam jangka waktu yang lama.
2. Efisiensi (Processor utilization)
Penjadwalan menjaga agar prosesor terpakai secara terus menerus selama masih ada proses yang aktif di antrian ready. Umumnya proses-proses yang sedang menunggu inputan pengguna ataupun operasi I/O akan diblok dan berstatus blocked, sehingga tidak ikut dalam penjadwalan proses dan tidak memboroskan siklus hidup prosesor.
3. Waktu tanggapan (Response time)
Waktu tanggapan diusahakan seminimal dan sependek mungkin. Waktu tanggapan (response time) pada sistem interaktif adalah durasi waktu antara pengguna memberikan input dengan sistem operasi memberikan output atau umpan balik kepada pengguna. Faktor ini juga disebut dengan terminal response time. Pada sistem real-time response time merupakan durasi antara terjadinya suatu kejadian (event), baik eksternal maupun internal, dengan saat sistem memberikan tanggapan sehingga sering juga disebut dengan event response time.
4. Waiting time
Pada lingkungan sistem komputer konkuren berprosesor tunggal, dalam suatu waktu hanya satu proses yang running, sedangkan proses-proses lainnya menunggu di antrian ready. Waiting time merupakan durasi waktu yang dihabiskan suatu proses dalam antrian ready selama siklus hidupnya. Secara umum, algoritma penjadwalan yang baik menghasilkan rata-rata waiting time yang kecil untuk seluruh proses.
5. Turn around time
Terjadinya penjadwalan menyebabkan waktu total yang dibutuhkan suatu proses untuk menyelesaikan tugasnya menjadi lebih lama kare- na harus menunggu jika prosesor dijadwalkan ke proses lainnya. Turn around time merupakan durasi waktu dari saat suatu proses mulai aktif dalam sistem sampai proses tersebut selesai. Turn around time merupakan hasil penjumlahan antara durasi eksekusi proses (run- ning), durasi menunggu di antrian ready serta durasi proses terblok (blocked). Durasi proses terblok tergantung pada faktor luar seperti operasi I/O, interval penekanan keyboard oleh pengguna sehingga umumnya tidak diperhitungkan dalam menganalisa suatu algoritma penjadwalan. Sama halnya dengan waiting time, umumnya rata-rata turn around time yang kecil lebih dikehendaki.
6. Throughput
Throughput merupakan rata-rata proses yang dapat diselesaikan per satuan waktu. Algoritma penjadwalan yang baik memiliki nilai throughput yang tinggi. Ini artinya algoritma penjadwalan harus memastikan prosesor bekerja terus menerus serta meminimalkan hal- hal yang tidak berkaitan langsung dengan penyelesaian tugas proses, seperti proses switching. Jika process switching terlalu sering terjadi. berarti waktu prosesor banyak tersita untuk backup/restore konteks prosesor dan bukannya mengeksekusi kode instruksi proses.
Faktor-faktor di atas umumnya saling berbenturan satu sama lain. Misal- nya untuk mendapatkan throughput yang tinggi, proses switching perlu diminimalkan, tetapi dapat berdampak pada melambatnya waktu tang- gapan (response time) bagi pengguna. Penentuan faktor mana yang men jadi prioritas sangat bergantung pada jenis sistem komputernya. Misalnya pada sistem yang interaktif, multiuser, ataupun realtime, faktor response time menjadi faktor yang paling diprioritaskan dalam merancang algoritma penjadwalan proses. Sementara pada sistem batch, yang meng- eksekusi proses-proses secara sekuensial, faktor throughput dan processor utilization menjadi faktor yang paling diutamakan.
4.2.3 STRATEGI DASAR PENJADWALAN
Strategi penjadwalan proses secara umum dibedakan menjadi dua kelompok besar, yaitu penjadwalanan non-preemptive dan preemptive.
1. Non-preemptive (run-to-completion)
Pada strategy non-preemtive, begitu proses telah berjalan maka sistem operasi maupun proses lain tidak dapat mengambil 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 preemptive, 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 di mana proses- proses memerlukan tanggapan prosesor secara cepat. Sebagai contoh adalah sistem real-time, di mana jika terjadi interupsi dan tidak segera dilayani maka dapat berakibat fatal. Contoh lain adalah sistem interaktif time-sharing, di mana pengguna sistem mengharapkan tanggapan yang cepat dari sistem. Secara umum, sistem konkuren seperti sistem operasi yang multitasking lebih menghendaki sistem penjadwalan preemptive.
4.2.4 PEMICU TERJADINYA PENJADWALAN
Kapan sesungguhnya penjadwalan itu dilakukan oleh sistem operasi? Gambar 4.3 menunjukkan kemungkinan transisi proses yang memicu terjadinya penjadwalan proses.
Gambar 4.3 Pemicu terjadinya penjadwalan proses
Sejumlah pemicu atau keadaan yang mengaktifkan fungsi penjadwalan proses antara lain:
1. Proses berubah dari status running ke blocked
2. Proses berubah dari status running ke ready
3. Proses berubah dari status blocked 'ke ready
Ketika permintaan akses I/O ataupun event yang ditunggu oleh suatu proses yang berstatus blocked telah terpenuhi maka akan terjadi interupsi. Akibatnya proses yang sedang running akan terhenti dan terjadi pengalihan konteks eksekusi ke rutin penanganan interupsi. Rutin ini akan mengalihkan proses yang meminta akses I/O dari status blocked menjadi ready atau dengan kata lain memindahkan proses tersebut dari antrian I/O ke antrian ready. Pada akhirnya rutin ini akan memanggil fungsi penjadwalan proses. Perhatikan, proses yang terpilih dapat berupa proses yang terakhir running atau proses yang baru dipindahkan ke antrian ready ataupun proses lain yang ada sudah berada di antrian ready.
4. Proses berhenti (Terminated)
Proses yang berhenti secara normal akan memanggil system call "exit", sedangkan proses yang berhenti secara abnormal umumnya disertai dengan terjadinya trap. Rutin system call exit maupun rutin penangan trap seperti itu akan melakukan penghapusan proses dari sistem dan diakhiri dengan memanggil fungsi penjadwalan proses.
Pada sistem yang menggunakan strategi penjadwalan non-preemptive, fungsi penjadwalan proses hanya dipicu oleh keadaan nomor 1 dan 4.
4.2.5 ALGORITMA PENJADWALAN
Bagian ini akan membahas bagaimana scheduler melakukan pemilihan proses. Ada berbagai macam algoritma pemilihan atau penjadwalan. Beberapa yang akan dibahas disini adalah algoritma FIFO (First in First Out) atau disebut juga FCFS (First Come First Serve), SJF (Shortest Job First) dan HRRN (Highest Response Ratio Next) Ketiga algoritma ini merupakan algoritma penjadwalan non-preemptive. Namun untuk SJF dan HRRN dimungkinkan membuat versi preemptive-nya.
Selain itu, akan dibahas sejumlah algoritma penjadwalan preemptive lain- nya seperti RR (Round Robin). SRT (Shortest Remaining Time), GS (Guaranteed Scheduling), MLQ (Multi Level Queueing), MFQ (Multi Level Feedback Queueing). Algoritma RR tidak menggunakan prioritas dalam penjadwalannya, sedangkan algoritma lainnya memberikan nilai prioritas yang dinamis pada proses setiap kali terjadi penjadwalan.
Algoritma Penjadwalan Non-Preemptive
1. FIFO (First In First Out) / FCFS (First Come First Serve)
Sebagai contoh, ada tiga proses, yaitu P1, P2, P3 yang sedang menunggu dijadwal dengan prediksi burst time (waktu eksekusi) 24 ms (millisecond atau milidetik), 3 ms, dan 3 ms secara berturut-turut. Diasumsikan ketiga proses masuk pada saat yang hampir bersamaan, yaitu detik ke 0.
Process
Burst Time
P1
24 ms
P2
3 ms
P3
3 ms
Misalnya urutan masuknya proses: p_{1} , P2, P3 maka Gantt Chart untuk penjadwalnya adalah:
Secara umum, untuk menghitung waiting time suatu proses, rumusnya adalah waktu selesai waktu mulai - burst time atau:
t_waiting = t_end - t_start - t_burst_time
a. Waiting time untuk PI=0: P2=24~ms P3=27 ms, sehingga
b. Rerata Waiting time: (0+24+27)/3=17 ms
Sementara jika urutan masuknya proses: P2, P3, P1, maka Gantt Chart untuk penjadwalnya adalah
a. Waiting time untuk Pl=6ms ; P2=0; P3=3 ms, sehingga
b. Rerata waiting time. (6+0+3)/3= 3ms
Nilai rerata waiting time ini lebih baik dari dari sebelumnya sekalipun burst time setiap proses adalah sama. Perbedaanya di sini adalah proses yang lebih pendek ditaruh di depan antrian. Ini merupakan ide dari algoritma penjadwalan berikutnya SJF.
2. SJF (Shortest Job First)
(Tabel Data)
Gantt Chart untuk penjadwalnya adalah:
a. Waiting time P1=0ms, P2=6 ms, P3= 3ms, P4=7 ms, sehingga
b. Rerata waiting time = (0+6+3+7)/4 = 4 ms
3. HRRN (Highest Response Ratio Next)
HRRN merupakan penjadwalan non-preemptive menggunakan prioritas dinamis. Penjadwalan ini memperbaiki Shortest Job First. Prioritas proses tidak hanya merupakan fungsi waktu layanan, tetapi jumlah waktu tunggu proses. Prioritas dinamis HRRN dihitung berdasarkan rumus:
Prioritas = (waktu tunggu + waktu layanan) / waktu layanan
Dari rumusnya terlihat bahwa proses yang memiliki waktu eksekusi terpendek memiliki prioritas tinggi. Begitu juga untuk proses yang telah menunggu lama.
Algoritma Penjadwalan Preemptive
1. RR (Round Robin)
RR merupakan penjadwalan preemptive tanpa prioritas. Proses disela oleh sistem operasi berdasarkan lama waktu berjalannya proses. Semua proses dianggap penting dan diberi jatah waktu pemakaian prosesor yang disebut time slice atau quantum. Ketentuan algoritma round robin adalah sebagai berikut:
a. Jika quantum habis dan proses belum selesai maka proses akan dialihkan statusnya menjadi ready dan penjadwal akan dijalankan untuk memilih proses lain untuk dieksekusi.
b. Jika quantum belum habis dan proses sedang menunggu suatu event ataupun operasi I/O maka status proses menjadi blocked dan penjadwal akan dijalankan untuk memilih proses lain untuk dieksekusi.
c. Jika quantum belum habis, tetapi proses telah selesai maka proses diakhiri dan penjadwal akan dijalankan untuk memilih proses lain untuk dieksekusi.
Sebagi contoh:
Process
PI
53 ms
P2
P3
17 ms
68 ms
P4
Burst Time
24 ms
Dengan asumsi quantum time = 20 ms maka Gantt Chart penjadwalan prosesnya adalah:
a. Waiting time P1=(134-0-53)= 81ms, P2=(37-20-17)= 0ms, P3=(162-37-68)= 58ms, P4=(121-57-24) 40 ms, sehingga
b. Rerata waiting time adalah (81+0+58+40)/4=59,7~ms Umumnya algoritma round robin memiliki rata-rata turnaround time yang lebih tinggi dibanding SJF, tetapi dengan response time yang lebih baik.
2. SRT (Shortest-Remaining Time)
Sebagai contoh, jika diketahui:
Gantt Chart untuk penjadwalnya adalah:
a. Waiting time P1= 9ms, P2= 1ms, P2= 0 ms, P4= 2 ms, sehingga
b. Rerata waiting time =(9+1+0+2)/4= 3 ms.
3. PS (Priority Sheduling)
PS merupakan algoritma penjadwalan preemptive. Menggunakan PS, setiap proses diberi nilai prioritas. Nilai prioritas proses ini dapat bersifat statis ataupun dinamis (berubah terus dari waktu ke waktu). Proses dengan prioritas yang lebih tinggi akan dijadwal lebih dahulu. Jika ada proses baru yang masuk dengan prioritas lebih tinggi dari proses yang sedang berjalan maka akan terjadi preemption dan prosesor akan dialihkan ke proses yang baru tersebut.
4. GS (Guaranteed Schedulling)
GS merupakan penjadwalan preemptive menggunakan prioritas dinamis. Jika terdapat N pemakai, setiap pemakai diusahakan senan- tiasa mendapat (1/N) waktu prosesor. Pada saat terjadi penjadwalan dihitung rasio waktu running semenjak login setiap pemakai dan waktu pemakaian prosesor secara keseluruhan. Penjadwal akan men- jalankan proses dengan rasio terendah atau dengan kata lain proses yang paling sedikit mendapatkan jatah yang seharusnya.
5. MLQ (Multi Level Queues)
MLQ merupakan penjadwalan preemptive. Proses-proses dibagi atas group dan ditempatkan pada antrian yang berbeda. Perhatikan Gambar 4.4, setiap antrian memiliki prioritas yang berbeda dan jatah waktu eksekusi atau quantum yang berbeda. Algoritma penjadwalan pada masing-masing antrian dapat saja berbeda, misalnya satu antrian menggunakan RR sedangkan antrian lainnya menggunakan FCFS ataupun GS. Sementara algoritma penjadwalan antar antrian dapat menggunakan Priority Scheduling (PS) sedangkan Round Robin (RR). Jika dengan PS maka seluruh proses ses pada antrian yang berprioritas lebih tinggi akan dijadwal dahulu sampai selesai semuanya, baru penjadwalan dilakukan pada proses-proses yang berada pada antrian berprioritas lebih rendah berikutnya. Jika dengan RR maka setiap antrian akan mendapatkan jatah penjadwalan secara bergilir. Antrian yang berprioritas lebih tinggi diberi waktu quantum yang lebih lama.
Gambar 4.4 Model penjadwalan MLO
6. MFQ (Multi Level Feedback Queues)
Gambar 4.5 Algoritma MFQ
Suatu proses baru selalu dimasukkan pada antrian berprioritas tertinggi. Jika dalam waktu 1 quantum proses tersebut belum selesai maka proses bersangkutan akan dipindahkan ke antrian berikutnya yang memiliki quantum time yang lebih besar. Jika pada antrian berprioritas lebih tinggi masih terdapat proses maka penjadwalan akan memilih proses tersebut lebih dahulu sampai semuanya selesai ataupun dipindahkan ke antrian level bawahnya.
Pada antrian level paling bawah, proses-prosesnya akan dijadwal seca- ra batch dengan FCFS. Variasi algoritma penjadwalan pada masing- masing antrian sangat mungkin dilakukan. Keuntungan algoritma penjadwalan ini adalah, proses yang pendek ataupun proses baru tidak perlu menunggu proses panjang yang sedang berjalan. Proses baru akan segera dieksekusi, dan jika waktu eksekusinya pendek maka proses tersebut akan selesai dalam 1 quantum. Algoritma ini cen- derung memberikan nilai response time yang baik serta rerata waiting time yang kecil.
Tidak ada komentar:
Posting Komentar