Algoritma Penjadwalan CPU Preemptive Beserta Contoh - Dalam komputasi, preemption adalah tindakan sementara mengganggu tugas sedang dilakukan oleh sistem komputer, tanpa memerlukan kerjasama, dan dengan tujuan melanjutkan tugas di lain waktu. Perubahan ini dikenal sebagai context switch. Hal ini biasanya dilakukan oleh tugas istimewa atau bagian dari sistem yang dikenal sebagai scheduler preemptive, yang memiliki kekuatan untuk mendahului, atau mengganggu, dan kemudian melanjutkan, tugas-tugas lain dalam sistem
User mode and kernel mode
Dalam setiap desain sistem yang ada, beberapa operasi yang dilakukan oleh sistem mungkin tidak dapat didahulukan. Hal ini biasanya berlaku untuk fungis-fungsi kernel dan layanan interupsi, jika tidak diizinkan untuk berjalan sampai selesai, akan cenderung menghasilkan kondisi race yang mengakibatkan kebuntuan (Deadlock). Mencegah scheduler dari memberikan mode preempting pada tugas-tugas yang berupa fungsi-fungsi kernel akan menyederhanakan desain kernel dengan tanpa mengorbankan respon sistem. Perbedaan antara mode pengguna dan kernel mode, yang juga menentukan tingkat hak istimewaan sistem, juga dapat digunakan untuk membedakan apakah suatu tugas dalam status preemptive atau tidak.
Sebagian besar sistem modern memiliki kernel preemptive, dirancang untuk memungkinkan suatu tugas untuk didahukukan walaupun ketika dalam mode kernel. Contoh sistem seperti Solaris 2.0 / SunOS 5.0, Windows NT, Linux kernel 2.6 dan 3.x, AIX dan beberapa sistem BSD (NetBSD, mulai versi 5).
Preemptive multitasking
Istilah preemptive multitasking digunakan untuk membedakan sistem operasi multitasking, yang memungkinkan preemption (pendahuluan) suatu tugas, dari sistem multitasking koperasi dimana proses atau tugas harus secara eksplisit diprogram untuk dilepaskan ketika mereka tidak membutuhkan sumber daya sistem.
Secara sederhana: Preemptive multitasking melibatkan penggunaan mekanisme interupsi yang menunda proses yang sedang berjalan dan memanggil scheduler untuk menentukan proses mana yang harus dieksekusi berikutnya. Oleh karena itu, semua proses akan mendapatkan beberapa jumlah waktu CPU pada waktu tertentu.
Dalam preemptive multitasking, kernel sistem operasi juga dapat memulai context switch untuk memenuhi kebijakan penjadwalan prioritas ini, sehingga preempting tugas aktif. Secara umum, preemption berarti "penyitaan sebelumnya". Ketika tugas dengan prioritas tinggi pada sistem yang sedang berjalan yang merebut jadwal tugas yang sedang berjalan, itu dikenal sebagai penjadwalan preemptive.
Istilah "preemptive multitasking" kadang-kadang keliru digunakan ketika arti yang diinginkan adalah lebih spesifik, lebih mengarah kepada kebijakan penjadwalan yang dikenal sebagai time-shared scheduling, atau time-sharing.
Preemptive multitasking memungkinkan sistem komputer untuk lebih andal menjamin setiap proses "slice" biasa waktu operasi. Hal ini juga memungkinkan sistem untuk cepat menangani peristiwa eksternal penting seperti data yang masuk, yang mungkin memerlukan perhatian segera dari satu atau proses lain.
Pada setiap waktu tertentu, proses dapat dikelompokkan menjadi dua kategori: mereka yang menunggu input atau output (disebut "I/O bound"), dan mereka yang sepenuhnya memanfaatkan CPU ("CPU bound"). Dalam sistem-sistem awal, proses akan sering "poll", atau "busywait" sambil menunggu input yang diminta (seperti disk, keyboard atau input jaringan). Selama ini, proses itu tidak melakukan pekerjaan yang berguna, namun masih memegang penuh kontrol CPU. Dengan munculnya interupsi dan preemptive multitasking, proses I/O bound ini bisa "diblokir", atau ditunda, sambil menunggu kedatangan data yang diperlukan, yang memungkinkan proses lain untuk menggunakan CPU. Ketika data yang diminta datang, akan menghasilkan interrupt, proses yang diblokir akan mendapat jaminan untuk mendaptkan waktu eksekusi.
Meskipun teknik multitasking pada awalnya dikembangkan untuk memungkinkan beberapa pengguna untuk berbagi satu mesin, namun akhirnya menjadi jelas bahwa multitasking sangat berguna, terlepas dari berapa banyak jumlah pengguna. Banyak sistem operasi, mulai dari mainframe sampai ke komputer pribadi yang single-user dan sistem kontrol tanpa user (seperti yang ada di pesawat ruang angkasa robot), telah mengakui manfaat dari dukungan multitasking untuk berbagai alasan. Multitasking memungkinkan pengguna tunggal untuk menjalankan beberapa aplikasi pada saat yang sama, atau untuk menjalankan "latar belakang" proses sementara tetap mempertahankan kontrol komputer
Time Slice
Periode waktu yang dipergunakan oleh proses ketika berjalan dalam sistem preemptive multitasking umumnya disebut time slice, atau kuantum. Scheduler dijalankan sekali setiap irisan waktu untuk memilih proses selanjutnya untuk dijalankan. Panjang setiap irisan waktu dapat sangat penting untuk menyeimbangkan sistem kinerja vs proses tanggap - jika waktu slice terlalu pendek maka penjadwal akan mengkonsumsi terlalu banyak waktu proses, tetapi jika waktu slice terlalu panjang, proses akan memakan waktu lebih lama untuk merespon input.
Sebuah interupsi akan dijadwalkan untuk memungkinkan kernel sistem operasi untuk beralih antar proses ketika irisan waktu mereka berakhir, sehingga memungkinkan waktu prosesor untuk dibagi secara efektif antar sejumlah tugas, memberikan ilusi bahwa itu berurusan dengan tugas-tugas ini secara berurutan, atau bersamaan. Sistem operasi yang mengontrol desain seperti ini disebut sistem multi-tasking
Sistem pendukung preemptive multitasking
Saat ini, hampir semua sistem operasi mendukung preemptive multitasking, termasuk versi terbaru dari Windows, Mac OS, Linux, iOS dan Android.
Beberapa sistem operasi awal yang tersedia untuk pengguna rumahan menampilkan preemptive multitasking adalah Sinclair QDOS (1984) dan Amiga OS (1985). Keduanya berjalan pada keluarga mikroprosesor Motorola mikroprosesor 68000 tanpa manajemen memori. Amiga OS menggunakan dynamic loading dari blok kode yang dapat direlokasikan ("hunks" dalam jargon Amiga) untuk menjalankan multitasking preemptive pada semua proses dalam ruang alamat yang sama.
Awal sistem operasi PC seperti MS-DOS dan PC DOS, tidak mendukung metode multitasking sama sekali, namun sistem operasi alternatif seperti MP/M-86 (1981) dan CP/M-86 melakukan dukungan preemptive multitasking. Sistem Unix-like lainnya termasuk MINIX dan Coheren menyediakan metode multitasking preemptive pada komputer pribadi era 1980-an.
Versi DOS setelah itu secara native mendukung preemptive multitasking / multithreading termasuk Concurrent DOS, Multiuser DOS, Novell DOS (kemudian disebut Caldera OpenDos dan DR-DOS 7.02 dan lebih tinggi). Sejak Concurrent DOS 386, mereka juga bisa menjalankan beberapa program DOS bersamaan di mesin DOS virtual.
Versi awal Windows yang mendukung bentuk terbatas preemptive multitasking adalah Windows 2.1x, yang menggunakan mode virtual 8086 pada Intel 80386 untuk menjalankan aplikasi DOS di mesin virtual 8086-umumnya dikenal sebagai "kotak DOS"-yang bisa melakukan mode preemptive. Pada Windows 95, 98, dan Me, aplikasi 32-bit dibuat preemptive dengan cara menjalankan masing-masing aplikasi dalam ruang alamat yang terpisah, tetapi aplikasi 16 bit tetap menggunakan mode kooperatif untuk kompatibilitas. [3]
Windows NT (semua versi), OS / 2 (aplikasi-aplikasi nativenya), sistem Unix dan Unix-like (seperti Linux, BSD dan Mac OS X), VMS, OS / 360 dan banyak sistem operasi lainnya yang digunakan oleh akademik dan pasar bisnis menengah hingga besar, selalu mendukung preemptive multitasking
Algoritma-algoritma Penjadwalan Preemptive
Algoritma-algoritma yang menerapkan strategi preemptive diantaranya adalah:
RR (Round-Robin)
Penjadwalan Round Robin merupakan:
Semua proses dianggap penting dan diberi sejulah waktu premrosesan yang disebut kwanta (Quantum) atau time-slice tempat proses berjalan. Proses berjalan selama 1 kwanta, kemudian penjadwal akan mengalihkan kepada proses berikutnya, juga untuk berjalan satu kwanta, begitu seterusnya sampai kembali pada proses pertama dan berulang.
Ketentuan
Ketentuan algoritma Round Robin adalah sebagai berikut:
Algoritma penjadwalan ini dapat diimplementasikan sebagai berikut:
Masalah penjadwalan ini adalah dalam hal menentukan besar kwanta, yaitu:
Harus ditetapkan besar kwanta waktu yang optimal berdasarkan kebutuhan sistem terutama dari hasil percobaan atau data historis sistem. Besar kwanta waktu beragam yang bergantung beban sistem.
Berdasarkan kriteria penilaian penjadwalan
Penjadwalan Berprioritas (PS)
Gagasan penjadwalan ini adalah masing-masing proses diberi prioritas dan proses berprioritas tertinggi menjadi Running (yaitu mendapat jatah waktu pemrosesan)
Prioritas dapat diberikan secara:
1. Prioritas Statis
Prioritas statis berarti prioritas tidak akan berubah.
Keunggulan
Kelemahan
2. Prioritas Dinamis
Prioritas dinamis merupakan mekanisme menggapi perubahan lingkungan sistem saat beroperasi di lingkungan nyata. Prioritas awal yang diberikan ke proses mungkin hanya berumur pendek dalam hal ini sistem dapat menyesuaikan nilai prioritasnya ke nilai yang lebih tepat sesuai lingkungannya.
Kelemahan
Keunggulan
Overhead ini diimbangi dengan peningkatan daya tanggap sistem
Contoh Penjadwalan Berprioritas
Proses-proses sangat banyak menggunakan operasi masukan dan keluaran dan menghabiskan kebanyakan waktu untuk menunggu selesainya operasi masukan/keluaran. Proses demikian disebut I/O bound process. Proses-proses ini dapat diberi prioritas sangat tinggi sehingga begitu proses-proses memerlukan pemrosesan segera saja diberikan dan proses akan segera memulai permintaan masukan/keluaran berikutnya sehingga menyebabkan proses blocked menunggu selesainya operasi masukan/keluaran. Dengan demikian pemrosesan segera dialihkan, dapat dipergunakan oleh proses-proses lain tanpa menganggu proses I/O bound. Proses-proses I/O bound berjalan paralel bersama proses-proses lain yang benar-benar memerlukan pemroses.
Proses-proses yang sangat banyak operasi masuka/keluaran kalau harus mengunggu lama untuk memakai pemroses (karena diberikan prioritas rendah) hanya akan membebani memori karena sistem harus menyimpan tanpa perlu proses-proses itu di memori karena tidak selesai-selesai menunggu operasi masukan/keluaran dan menuggu jatah pemroses.
Algoritma Prioritas Dinamis
Algoritma ini dituntun oleh keputusan untuk memenuhi kebijaksanaan tertentu yang menjadi tujuan sistem komputer.
Algoritma sederhana yang memberi layanan bagus adalah dengan menge-set proses dengan prioritas berdasarkan rumus niali 1/f bahwa f adalah rasio kwanta terakhir yang digunakan proses.
Kebijaksanaan yang diterapkan adalah jaminan proses-proses mendapat layanan yang adil dari pemroses adalah arti jumlah waktu pemroses yang sama untuk masing-masing pemroses pada satu waktu.
Keunggulan Algoritma Penjadwalan Berprioritas.
Biasanya memenuhi kebijaksanaan yang ingin mencapai level maksimal berdasarkan suatu kriteria tertentu di sistem.
Kombinasi
Algoritma penjadwalan berprioritas dapat dikombinasikan yaitu dengan mengelompokkan proses-proses menjadi kelas-kelas prioritas. Penjawalan berprioritas diterapkan antar kelas-kelas proses-proses itu. Penjadwalan round-robin atau penjawalan FIFO diterapkan pada proses-proses didalam satu kelas.
Penjadwalan dengan banyak antrian (MFQ)
Penjadwalan MFQ ini merupakan
Sasaran penjadwalan MFQ ini adalah untuk mencegah banyaknya aktivitas swapping. Cara yang dilakukan adalah dengan:
Ketentuan yang berlaku adalah sebagai berikut:
Mekanisme MFQ ini dapat mencegah proses yang perlu berjalan lama mengalami swapping berulang kali dan mencegah proses-proses interaktif yang singkat harus menunggu lama untuk layanan pemroses.
Penggunaan
Sistem yang memiliki banyak proses lambat, memerlukan waktu lama, dan banyak proses singkat.
Penjadwalan dengan sisa waktu terpendek, lebih dahulu (SRF)
Penjadwalan SRF ini merupakan
Penjadwalan SRF merupakan perbaikan dari SJF. SJF merupakan penjadwalan nonpreemptive sedangkan SRF adalah preemptive yang dapat digunakan untuk sistem timesharing.
Ketentuan:
Perbedaan SRF dangan SJF:
Kelemahan
Secara teoritis, SRF memberi waktu tunggu minimum tapi karena adanya overhead peralihan maka pada situasi tertentu SJF bisa memberikan kinerja yang lebih baik disbanding SRF
Penjadwalan terjamin (GS)
Penjadwalan GS ini merupakan
Penjadwalan ini berupaya memberi masing-masing pemakai daya pemroses yang sama. Jika terdapat N pemakai, maka tiap pemakai diupayakan mendapat 1/N daya pemroses. Sistem merekam banyak waktu pemroses yang telah digunakan proses sejak login dan jumlah waktu pemroses yang digunakan seluruh proses.
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.
Penjadwal akan menjalankan proses dengan rasio terendah sampai rasio proses di atas pesaing terdekat.
Variasi yang digunakan pada sistem real-time
Karena sistem real-time sering mempunyai deadline absolut maka penjadwalan dapat berdasarkan deadline. Proses yang dijalankan adalah proses yang mempunyai deadline terdekat. Proses yang lebih dalam bahaya kehilangan deadline akan dijalankan lebih dahulu. Proses yang harus berakhir 10 detik lagi mendapat prioritas lebih tinggi disbanding dengan proses yang harus berakhir 10 menit lagi.
 |
| image source: agileroute.com |
baca juga: Algoritma Penjadwalan Non Preemptive Beserta Contoh
User mode and kernel mode
Dalam setiap desain sistem yang ada, beberapa operasi yang dilakukan oleh sistem mungkin tidak dapat didahulukan. Hal ini biasanya berlaku untuk fungis-fungsi kernel dan layanan interupsi, jika tidak diizinkan untuk berjalan sampai selesai, akan cenderung menghasilkan kondisi race yang mengakibatkan kebuntuan (Deadlock). Mencegah scheduler dari memberikan mode preempting pada tugas-tugas yang berupa fungsi-fungsi kernel akan menyederhanakan desain kernel dengan tanpa mengorbankan respon sistem. Perbedaan antara mode pengguna dan kernel mode, yang juga menentukan tingkat hak istimewaan sistem, juga dapat digunakan untuk membedakan apakah suatu tugas dalam status preemptive atau tidak.
Sebagian besar sistem modern memiliki kernel preemptive, dirancang untuk memungkinkan suatu tugas untuk didahukukan walaupun ketika dalam mode kernel. Contoh sistem seperti Solaris 2.0 / SunOS 5.0, Windows NT, Linux kernel 2.6 dan 3.x, AIX dan beberapa sistem BSD (NetBSD, mulai versi 5).
Preemptive multitasking
Istilah preemptive multitasking digunakan untuk membedakan sistem operasi multitasking, yang memungkinkan preemption (pendahuluan) suatu tugas, dari sistem multitasking koperasi dimana proses atau tugas harus secara eksplisit diprogram untuk dilepaskan ketika mereka tidak membutuhkan sumber daya sistem.
Secara sederhana: Preemptive multitasking melibatkan penggunaan mekanisme interupsi yang menunda proses yang sedang berjalan dan memanggil scheduler untuk menentukan proses mana yang harus dieksekusi berikutnya. Oleh karena itu, semua proses akan mendapatkan beberapa jumlah waktu CPU pada waktu tertentu.
Dalam preemptive multitasking, kernel sistem operasi juga dapat memulai context switch untuk memenuhi kebijakan penjadwalan prioritas ini, sehingga preempting tugas aktif. Secara umum, preemption berarti "penyitaan sebelumnya". Ketika tugas dengan prioritas tinggi pada sistem yang sedang berjalan yang merebut jadwal tugas yang sedang berjalan, itu dikenal sebagai penjadwalan preemptive.
Istilah "preemptive multitasking" kadang-kadang keliru digunakan ketika arti yang diinginkan adalah lebih spesifik, lebih mengarah kepada kebijakan penjadwalan yang dikenal sebagai time-shared scheduling, atau time-sharing.
Preemptive multitasking memungkinkan sistem komputer untuk lebih andal menjamin setiap proses "slice" biasa waktu operasi. Hal ini juga memungkinkan sistem untuk cepat menangani peristiwa eksternal penting seperti data yang masuk, yang mungkin memerlukan perhatian segera dari satu atau proses lain.
Pada setiap waktu tertentu, proses dapat dikelompokkan menjadi dua kategori: mereka yang menunggu input atau output (disebut "I/O bound"), dan mereka yang sepenuhnya memanfaatkan CPU ("CPU bound"). Dalam sistem-sistem awal, proses akan sering "poll", atau "busywait" sambil menunggu input yang diminta (seperti disk, keyboard atau input jaringan). Selama ini, proses itu tidak melakukan pekerjaan yang berguna, namun masih memegang penuh kontrol CPU. Dengan munculnya interupsi dan preemptive multitasking, proses I/O bound ini bisa "diblokir", atau ditunda, sambil menunggu kedatangan data yang diperlukan, yang memungkinkan proses lain untuk menggunakan CPU. Ketika data yang diminta datang, akan menghasilkan interrupt, proses yang diblokir akan mendapat jaminan untuk mendaptkan waktu eksekusi.
Meskipun teknik multitasking pada awalnya dikembangkan untuk memungkinkan beberapa pengguna untuk berbagi satu mesin, namun akhirnya menjadi jelas bahwa multitasking sangat berguna, terlepas dari berapa banyak jumlah pengguna. Banyak sistem operasi, mulai dari mainframe sampai ke komputer pribadi yang single-user dan sistem kontrol tanpa user (seperti yang ada di pesawat ruang angkasa robot), telah mengakui manfaat dari dukungan multitasking untuk berbagai alasan. Multitasking memungkinkan pengguna tunggal untuk menjalankan beberapa aplikasi pada saat yang sama, atau untuk menjalankan "latar belakang" proses sementara tetap mempertahankan kontrol komputer
Time Slice
Periode waktu yang dipergunakan oleh proses ketika berjalan dalam sistem preemptive multitasking umumnya disebut time slice, atau kuantum. Scheduler dijalankan sekali setiap irisan waktu untuk memilih proses selanjutnya untuk dijalankan. Panjang setiap irisan waktu dapat sangat penting untuk menyeimbangkan sistem kinerja vs proses tanggap - jika waktu slice terlalu pendek maka penjadwal akan mengkonsumsi terlalu banyak waktu proses, tetapi jika waktu slice terlalu panjang, proses akan memakan waktu lebih lama untuk merespon input.
Sebuah interupsi akan dijadwalkan untuk memungkinkan kernel sistem operasi untuk beralih antar proses ketika irisan waktu mereka berakhir, sehingga memungkinkan waktu prosesor untuk dibagi secara efektif antar sejumlah tugas, memberikan ilusi bahwa itu berurusan dengan tugas-tugas ini secara berurutan, atau bersamaan. Sistem operasi yang mengontrol desain seperti ini disebut sistem multi-tasking
Sistem pendukung preemptive multitasking
Saat ini, hampir semua sistem operasi mendukung preemptive multitasking, termasuk versi terbaru dari Windows, Mac OS, Linux, iOS dan Android.
Beberapa sistem operasi awal yang tersedia untuk pengguna rumahan menampilkan preemptive multitasking adalah Sinclair QDOS (1984) dan Amiga OS (1985). Keduanya berjalan pada keluarga mikroprosesor Motorola mikroprosesor 68000 tanpa manajemen memori. Amiga OS menggunakan dynamic loading dari blok kode yang dapat direlokasikan ("hunks" dalam jargon Amiga) untuk menjalankan multitasking preemptive pada semua proses dalam ruang alamat yang sama.
Awal sistem operasi PC seperti MS-DOS dan PC DOS, tidak mendukung metode multitasking sama sekali, namun sistem operasi alternatif seperti MP/M-86 (1981) dan CP/M-86 melakukan dukungan preemptive multitasking. Sistem Unix-like lainnya termasuk MINIX dan Coheren menyediakan metode multitasking preemptive pada komputer pribadi era 1980-an.
Versi DOS setelah itu secara native mendukung preemptive multitasking / multithreading termasuk Concurrent DOS, Multiuser DOS, Novell DOS (kemudian disebut Caldera OpenDos dan DR-DOS 7.02 dan lebih tinggi). Sejak Concurrent DOS 386, mereka juga bisa menjalankan beberapa program DOS bersamaan di mesin DOS virtual.
Versi awal Windows yang mendukung bentuk terbatas preemptive multitasking adalah Windows 2.1x, yang menggunakan mode virtual 8086 pada Intel 80386 untuk menjalankan aplikasi DOS di mesin virtual 8086-umumnya dikenal sebagai "kotak DOS"-yang bisa melakukan mode preemptive. Pada Windows 95, 98, dan Me, aplikasi 32-bit dibuat preemptive dengan cara menjalankan masing-masing aplikasi dalam ruang alamat yang terpisah, tetapi aplikasi 16 bit tetap menggunakan mode kooperatif untuk kompatibilitas. [3]
Windows NT (semua versi), OS / 2 (aplikasi-aplikasi nativenya), sistem Unix dan Unix-like (seperti Linux, BSD dan Mac OS X), VMS, OS / 360 dan banyak sistem operasi lainnya yang digunakan oleh akademik dan pasar bisnis menengah hingga besar, selalu mendukung preemptive multitasking
Algoritma-algoritma Penjadwalan Preemptive
Algoritma-algoritma yang menerapkan strategi preemptive diantaranya adalah:
- RR (Round-Robin)
- MFQ (Multiple Feedback Queues)
- SRF (Shortest Remaining First)
- PS (Priority Scheduling)
- GS (Guaranteed Scheduling)
RR (Round-Robin)
Penjadwalan Round Robin merupakan:
- Penjadwalan preemptive, namun proses tidak di-preempt secara langsung oleh proses lain namun oleh penjadwalan berdasarkan lama waktu berjalannya suatu proses maka penjadwalan ini disebut preempt-by-time.
- Penjadwalan tanpa prioritas
Semua proses dianggap penting dan diberi sejulah waktu premrosesan yang disebut kwanta (Quantum) atau time-slice tempat proses berjalan. Proses berjalan selama 1 kwanta, kemudian penjadwal akan mengalihkan kepada proses berikutnya, juga untuk berjalan satu kwanta, begitu seterusnya sampai kembali pada proses pertama dan berulang.
Ketentuan
Ketentuan algoritma Round Robin adalah sebagai berikut:
- Jika kwanta habis dan proses belum selesai maka proses Running itu menjadi Ready (Runnable) dan pemroses dialihkan ke proses lain.
- Jika kwanta belum habis dan proses menunggu suatu kejadian (misalnya menunggu selesainya suatu proses I/O), maka proses Running itu menjadi Blocked dan pemrosesan dialihkan ke proses lain.
- Jika kwanta belum habis tapi proses telah selesai maka proses Running itu diakhiri dan pemroses dialihkan ke proses lain.
Algoritma penjadwalan ini dapat diimplementasikan sebagai berikut:
- Sistem mengelola senarai proses Ready (Runnable) sesuai urutan kedatangan
- Sistem mengambil proses yang berada di ujung depan antrian Ready menjadi Running
- Bila kwanta belum habis dan proses selesai maka sistem mengambil proses di ujung depan antrian proses Ready.
- Jika kwanta habis dan proses belum selesai maka tempatkan proses Running ke ekor antrain proses Ready dan sistem mengambil proses di ujung depan antrian proses Ready.
Masalah penjadwalan ini adalah dalam hal menentukan besar kwanta, yaitu:
- Kwanta terlalu besar menyebabkan wkatu tanggap besar dan turn around time rendah
- Kwanta terlalu kecil mengakibatkan peralihan proses terlalu banyak sehingga menurunkan efisiensi pemrosesan.
Harus ditetapkan besar kwanta waktu yang optimal berdasarkan kebutuhan sistem terutama dari hasil percobaan atau data historis sistem. Besar kwanta waktu beragam yang bergantung beban sistem.
Berdasarkan kriteria penilaian penjadwalan
- Fairness
Penjadwalan RR adil bila dipandang dari persamaan pelayanan oleh pemroses. - Efisiensi
Penjadwalan RR cenderung efisien pada sistem interaktif. - Waktu Tanggap (Response Time)
Penjadwalan RR memuaskan untuk sistem ineraktif, tidak memadai untuk sistem real-time. - Turn Around Time
Penjadwalan RR cukup bagus. - Throughput
Penjadwalan RR cukup bagus.
Penjadwalan Berprioritas (PS)
Gagasan penjadwalan ini adalah masing-masing proses diberi prioritas dan proses berprioritas tertinggi menjadi Running (yaitu mendapat jatah waktu pemrosesan)
Prioritas dapat diberikan secara:
- Prioritas statis (static priorities)
- Prioritas dinamis (dynamic priorities)
1. Prioritas Statis
Prioritas statis berarti prioritas tidak akan berubah.
Keunggulan
- Mudah diimplementasikan
- Mempunyai overhead relative kecil
Kelemahan
- Penjadwalan prioritas statis tidak tanggap terhadap perubahan lingkungan yang memungkinkan menghendaki penyesuaian prioritas.
2. Prioritas Dinamis
Prioritas dinamis merupakan mekanisme menggapi perubahan lingkungan sistem saat beroperasi di lingkungan nyata. Prioritas awal yang diberikan ke proses mungkin hanya berumur pendek dalam hal ini sistem dapat menyesuaikan nilai prioritasnya ke nilai yang lebih tepat sesuai lingkungannya.
Kelemahan
- Implemetasi mekanisme prioritas dinamis lebih kompleks dan mempunyai overhead yang lebih besar dibandingkan dengan mekanisme prioritas static
Keunggulan
- Waktu tanggap sistem yang bagus.
Overhead ini diimbangi dengan peningkatan daya tanggap sistem
Contoh Penjadwalan Berprioritas
Proses-proses sangat banyak menggunakan operasi masukan dan keluaran dan menghabiskan kebanyakan waktu untuk menunggu selesainya operasi masukan/keluaran. Proses demikian disebut I/O bound process. Proses-proses ini dapat diberi prioritas sangat tinggi sehingga begitu proses-proses memerlukan pemrosesan segera saja diberikan dan proses akan segera memulai permintaan masukan/keluaran berikutnya sehingga menyebabkan proses blocked menunggu selesainya operasi masukan/keluaran. Dengan demikian pemrosesan segera dialihkan, dapat dipergunakan oleh proses-proses lain tanpa menganggu proses I/O bound. Proses-proses I/O bound berjalan paralel bersama proses-proses lain yang benar-benar memerlukan pemroses.
Proses-proses yang sangat banyak operasi masuka/keluaran kalau harus mengunggu lama untuk memakai pemroses (karena diberikan prioritas rendah) hanya akan membebani memori karena sistem harus menyimpan tanpa perlu proses-proses itu di memori karena tidak selesai-selesai menunggu operasi masukan/keluaran dan menuggu jatah pemroses.
Algoritma Prioritas Dinamis
Algoritma ini dituntun oleh keputusan untuk memenuhi kebijaksanaan tertentu yang menjadi tujuan sistem komputer.
Algoritma sederhana yang memberi layanan bagus adalah dengan menge-set proses dengan prioritas berdasarkan rumus niali 1/f bahwa f adalah rasio kwanta terakhir yang digunakan proses.
- Proses yang menggunakan 2 milidetik kwanta 100ms maka prioritasnya 50
- Proses yang berjalan selama 50 milidetik sebelum Blocked berprioritas 2.
- Proses yang menggunakan seluruh kwanta berprioritas 1.
Kebijaksanaan yang diterapkan adalah jaminan proses-proses mendapat layanan yang adil dari pemroses adalah arti jumlah waktu pemroses yang sama untuk masing-masing pemroses pada satu waktu.
Keunggulan Algoritma Penjadwalan Berprioritas.
Biasanya memenuhi kebijaksanaan yang ingin mencapai level maksimal berdasarkan suatu kriteria tertentu di sistem.
Kombinasi
Algoritma penjadwalan berprioritas dapat dikombinasikan yaitu dengan mengelompokkan proses-proses menjadi kelas-kelas prioritas. Penjawalan berprioritas diterapkan antar kelas-kelas proses-proses itu. Penjadwalan round-robin atau penjawalan FIFO diterapkan pada proses-proses didalam satu kelas.
Penjadwalan dengan banyak antrian (MFQ)
Penjadwalan MFQ ini merupakan
- Penjadwalan preemptive (preemptive by time)
- Penjadwalan berprioritas dinamis
Sasaran penjadwalan MFQ ini adalah untuk mencegah banyaknya aktivitas swapping. Cara yang dilakukan adalah dengan:
- Proses-proses yang sangat banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu yang sangat lama) diberi jatah waktu (jumlah kwanta) lebih banyak dalam satu waktu.
- Penjadwalan ini menghendaki kelas-kelas prioritas bagi proses-proses yang ada. Kelas tertinggi berjalan semala satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelas berikutnya lagi berjalan empat kwanta, kelas berikutnya-berikutnya lagi berjalan delapan kwanta dan seterusnya.
Ketentuan yang berlaku adalah sebagai berikut:
- Jalankan proses-proses yang berada pada kelas dengan prioritas tertinggi.
- Jika proses telah menggunakan seluruh kwanta yang dialokasikan maka proses itu diturunkan kelas prioritas-nya
- Proses yang masuk untuk pertama kali ke sistem langsung diberi kelas tertinggi.
Mekanisme MFQ ini dapat mencegah proses yang perlu berjalan lama mengalami swapping berulang kali dan mencegah proses-proses interaktif yang singkat harus menunggu lama untuk layanan pemroses.
Penggunaan
Sistem yang memiliki banyak proses lambat, memerlukan waktu lama, dan banyak proses singkat.
Penjadwalan dengan sisa waktu terpendek, lebih dahulu (SRF)
Penjadwalan SRF ini merupakan
- Penjadwalan preemptive
- Penjadwalan berprioritas dinamis
Penjadwalan SRF merupakan perbaikan dari SJF. SJF merupakan penjadwalan nonpreemptive sedangkan SRF adalah preemptive yang dapat digunakan untuk sistem timesharing.
Ketentuan:
- Pada SRF, proses yang diestimasi memiliki waktu jalan terendah akan dijalankan, termasuk proses-proses yang baru tiba.
Perbedaan SRF dangan SJF:
- Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai
- Pada SRF, proses yang sedang berjalan (Running) dapat diambil alih oleh proses baru dengan sisa waktu jalan yang diestimasi lebih rendah.
Kelemahan
- SRF mempunyai overhead yang lebih besar dibandingkan SJF. SRF memerlukan penyimpanan wkatu layanan yang telah dihabiskan proses dan kadang-kadang harus menangani peralihan.
- Tibanya proses-proses kecil akan segera dijalankan
- Proses-proses lebih lama berarti dengan lama dan variasi waktu tunggu lebih lama dibandingkan dengan SJF
Secara teoritis, SRF memberi waktu tunggu minimum tapi karena adanya overhead peralihan maka pada situasi tertentu SJF bisa memberikan kinerja yang lebih baik disbanding SRF
Penjadwalan terjamin (GS)
Penjadwalan GS ini merupakan
- Penjadwalan preemptive
- Penjadwalan berprioritas dinamis
Penjadwalan ini berupaya memberi masing-masing pemakai daya pemroses yang sama. Jika terdapat N pemakai, maka tiap pemakai diupayakan mendapat 1/N daya pemroses. Sistem merekam banyak waktu pemroses yang telah digunakan proses sejak login dan jumlah waktu pemroses yang digunakan seluruh proses.
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.
Penjadwal akan menjalankan proses dengan rasio terendah sampai rasio proses di atas pesaing terdekat.
Variasi yang digunakan pada sistem real-time
Karena sistem real-time sering mempunyai deadline absolut maka penjadwalan dapat berdasarkan deadline. Proses yang dijalankan adalah proses yang mempunyai deadline terdekat. Proses yang lebih dalam bahaya kehilangan deadline akan dijalankan lebih dahulu. Proses yang harus berakhir 10 detik lagi mendapat prioritas lebih tinggi disbanding dengan proses yang harus berakhir 10 menit lagi.
Sekian artikel tentang Algoritma Penjadwalan CPU Preemptive Beserta Contoh.
Algoritma Penjadwalan CPU Preemptive Beserta Contoh
4/
5
Oleh
Unknown