Algoritma Penjadwalan CPU

Penjadwalan CPU memiliki tujuan untuk memaksimumkan penggunaan (utilization) CPU. Maksimisasi penggunaan ini dapat diperoleh melalui multiprogramming yang dapat melakukan beberapa proses sekaligus, seolah-olah (terutama pada komputer uniprocessor), secara bersamaan. Eksekusi proses terdiri dari sebuah siklus eksekusi CPU dan tunggu (wait) I/O yang mana disebut Siklus Bakar CPU-I/O (CPU-I/O Burst Cycle).

Proses-proses dalam memori yang siap untuk dijalankan akan dipilih dan diberikan jatah CPU oleh penjadwal CPU (CPU scheduler). Keputusan yang diambil oleh penjadwal CPU terhadap sebuah proses berdasarkan keadaan-keadaan berikut: peralihan (switch) dari status jalan (running) ke tunggu (waiting), peralihan dari status jalan ke siap (ready), peralihan dari status tunggu ke siap, dan selesai/berhenti (terminate). Keempat tipe penjadwalan tersebut adalah nonpremptive (tidak dapat disela), sedangkan yang lainnya adalah preemptive (dapat disela).

Modul dispatcher memberikan kendali kepada CPU terhadap proses yang dipilih oleh penjadwal jangka pendek (short-term scheduler). Kendali ini meliputi: peralihan konteks (switching context), peralihan ke mode pemakai, dan melompat ke lokasi yang tepat dalam program pemakai untuk memulai ulang (restart) program tersebut. Waktu yang dibutuhkan oleh dispatcher untuk memberhentikan proses yang sedang berjalan dan memulai proses yang lain disebut dengan dispatch latency.

Kriteria penjadwalan yang digunakan oleh CPU adalah: CPU utilization, throughput, turnaround time, waiting time, dan response time. CPU utilization menjaga agar CPU tetapsesibuk mungkin. Throughput menyatakan banyaknya proses yang sudah selesaidieksekusi dalam satuan waktu tertentu. Turnaround time adalah lamanya waktu yangdibutuhkan untuk menjalankan sebuah proses. Waiting time merupakan lamanya waktutunggu sebuah proses dalam antrian siap (ready queue). Response time dihitung mulai darisebuah permintaan diberikan (submitted) sampai respon pertama diterima/dihasilkan,bukan keluarannya (biasanya digunakan untuk lingkungan time-sharing). Optimasi kriteriapenjadwalan diperoleh dengan cara memaksimumkan CPU utilization dan throughput, danmeminimumkan turnaround time, waiting time, dan response time.

Beberapa algoritme penjadwalan proses yang umum digunakan adalah FCFS (First Come First Served), SJF (Shortest Job First), SRTF (Shortest Remaining Time First), danRR (Round Robin).

Algoritme FCFS akan mengeksekusi proses-proses sesuai denganwaktu kedatangannya masing masing, maksudnya proses yang datang lebih dulu akandijalankan lebih dulu. Misalkan ada tiga proses P1, P2, dan P3 yang datang secaraberurutan dengan burst time masing-masing 24, 3, dan 3. Waktu tunggu untuk setiapproses tersebut secara berurutan adalah 0, 24, dan 27. Dalam hal ini P1 tidak menunggu,karena P1 datang pertama kali dan langsung dieksekusi, seperti terlihat dalam Gantt Chartpada Gambar 44. Oleh karena itu waktu tunggu rata-rata (average waiting time) prosesprosestersebut dapat dihitung sebagai berikut: (0+24+27)/3 = 17.

Gantt Chart untuk Proses-proses P1, P2, dan P3 dapat dilihat di bawah ini :

Seandainya urutan kedatangan adalah P2, P3, dan P1, maka akan diperoleh Gantt Chart seperti pada Gambar 45. Waktu tunggu rata-rata untuk kasus ini, sesuai urutan nama P1, P2, dan P3, adalah (6+0+3)/3 = 3. Dalam kasus ini, waktu tunggu rata-ratanya lebih baik dibandingkan dengan kasus sebelumnya, karena tidak memiliki convoy effect, yaitu proses-proses yang memiliki waktu eksekusi (burst time) lebih pendek tidak mengantri di belakang proses-proses yang memiliki waktu eksekusi lebih panjang.

Berikut ini adalah Gantt Chart untuk Proses-proses P2, P3, dan P1 :

Dalam Algoritme SJF, setiap proses yang datang diasosiakan dengan waktu eksekusi yang dibutuhkannya, dimana waktu eksekusi ini akan dijadikan panduan penjadwalan proses tersebut nantinya. SJF memiliki dua mekanisme penjadwalan: non-preemptive dan preemptive. Mekanisme SJF non-preemptive akan mengeksekusi sebuah proses sampai selesai tanpa dapat disela oleh siapapun, sedangkan mekanisme SJF preemptive, jika sebuah proses sedang dieksekusi oleh CPU dan seandainya ada proses baru yang datang dengan waktu eksekusi yang lebih pendek dibandingkan dengan sisa waktu (remaining time) eksekusi proses yang sedang berjalan, maka proses tersebut dapat disela oleh proses yang baru datang. Oleh karena itu, penjadwalan SJF preemptive dikenal juga dengan nama SRTF (Shortest Remaining Time First). Dalam hal ini, SJF dapat dikatakann optimal, karena memberikan waktu tunggu rata-rata yang minimum untuk sekumpulan proses.

Sebagai contoh, diberikan empat proses P1, P2, P3, dan P4 berikut dengan pasangan waktu kedatangan (arrival time) dan waktu eksekusi untuk setiap proses tersebut secara berurutan adalah: (0, 7), (2, 4), (4, 1), dan (5, 4). Hasil perhitungan waktu tunggu rata-rata dengan penjadwalan SJF non-preemptive adalah 4 ({0+6+3+7}/4)

Grantt Chart Contoh kasus penjadwalan proses dengan SJF non-preemptive dapat dilihat di bawah ini :

Adapun waktu tunggu rata-rata untuk kasus ini jika menggunakan algoritme SJF preemptive (SRTF) adalah 3 ({9+1+0+2}/4). Gantt Chart untuk penjadwalan kasus ini dengan SRTF dapat dilihat di bawah ini :

Penjadwalan prioritas (priority scheduling) mengasosiakan sebuah angka prioritas dengan setiap proses. Dalam penjadwalan ini, CPU akan diberikan kepada proses yang memiliki prioritas tertinggi, yaitu proses yang memiliki bilangan bulat terkecil. Mekanisme penjadwalan prioritas terdiri dari dua: non-premptive dan preemptive. SJF termasuk ke dalam kategori penjadwalan prioritas, dimana prioritasnya berupa perkiraan waktu eksekusi sebuah proses. Adapun permasalahan dalam penjadwalan prioritas adalah  terjadinya kelaparan (starvation), yaitu kasus dimana proses-proses dengan prioritas rendah sangat dimungkinkan untuk tidak pernah dieksekusi. Permasalahan ini dapat diatasi dengan mekanisme penuaan (aging), yaitu seiring dengan berjalannya waktu, prioritas untuk setiap proses ditingkatkan.

Penjadwalan RR (Round Robin) memberikan sedikit satuan waktu (time quantum) CPU untuk setiap proses, biasanya berkisar 10 – 100 milidetik. Setelah waktu ini berlalu, maka proses yang sedang dieksekusi akan ditunda (preempted) dan disimpan dalam ujung/akhir antrian siap (ready queue). Seandainya ada n proses dalam antrian siap dan satuan waktu q, maka setiap proses akan memperoleh 1/n bagian waktu CPU yang paling banyak q waktu pada satu waktu. Oleh karena itu, tidak ada proses yang menunggu lebih dari (n-1)*q satuan waktu. Kinerja dari RR akan berperilaku seperti FIFO (First In First Out) jika q cukup besar dan akan terjadi overhead dalam context switch (untuk perpindahan proses) jika q terlalu kecil, sehingga perlu ada cara tertentu yang dapat menentukan dengan optimal berapa ukuran q yang sebaiknya, seperti terlukiskan pada Gambar di bawah :

Sebagai ilustrasi Algoritme RR dengan q = 20, diberikan empat proses P1, P2, P3, dan P4 dengan waktu eksekusi yang diperlukan masing-masing adalah 53, 17, 68, dan 24. Gantt Chart untuk ke empat proses tersebut dideskripsikan dalam Gambar di bawah :

Secara umum, RR menghasilkan waktu rataan turnaround yang lebih lama dibandingkan dengan SJF, tetapi memiliki waktu respon yang lebih cepat (baik). Pada Gambar di bawah digambarkan bahwa waktu turnaround bervariasi sesuai dengan ukuran q.

Optimasi penjadwalan proses dapat dilakukan dengan cara menerapkan antrian bertingkat (multilevel queue), dimana antrian siap dibagi ke dalam dua antrian: foreground untuk proses interaktif dan background untuk batch proses. Setiap antrian tersebut memiliki algoritme penjadwalan yang berbeda, misal: RR untuk foreground dan FCFS untuk background. Penjadwalan antar antrian harus dilakukan juga, misal: prioritas tetap (fixed priority) dan potongan waktu (time slice). Prioritas tetap akan mengeksekusi semua proses yang ada dalam antrian foreground terlebih dahulu sampai semuanya selesai, kemudian dilanjutkan dengan proses yang ada dalam antrian background. Dalam hal ini, kelaparan dapat terjadi seandainya foreground proses mendominasi background proses. Dalam mekanisme penjadwalan potongan waktu, setiap antrian akan diberikan jatah sejumlah waktu CPU tertentu untuk menjadwalkan proses-proses dalam antriannya masing-masing, misal: 80% untuk foreground dengan RR dan 20% untuk background dengan FCFS.

Referensi :

– Hermadi, Irman, S.Kom, MS dan Ramadhan, Arief, S.Kom. 2007. Bahan Ajar Kuliah Mata Kuliah Sistem Operasi. Institut Pertanian Bogor

– Silberschatz, A., Galvin, P.B., dan Gagne, G. 2004. Operating System Concepts with Java, 6th Edition. John Wiley & Sons, Inc., USA.

– Tanenbaum, A.S. 2007. Modern Operating System, 3rd Edition. Prentice Hall.

Iklan

Jangan sungkan berpendapat

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s