Penjadwalan Preemptive
- Berubah dari running ke waiting state.
- Berubah dari running ke ready state.
- Berubah dari waiting ke ready state.
- 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 Preemptivemempunyai 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 disebut CPU 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 penjadwalanPreemptive, 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 lainnyaPreemptive. 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 penjadwalanPreemptive 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:
- Berjalan dari running state sampai waiting state.
- Dihentikan.
Ini berarti CPU menjaga proses sampai proses itu pindah ke waiting stateataupun dihentikan (proses tidak diganggu). Metode ini digunakan oleh Microsoft Windows 3.1 dan Macintosh. Ini adalah metode yang dapat digunakan untukplatforms hardware tertentu, karena tidak memerlukan perangkat keras khusus (misalnya timer yang digunakan untuk meng interupt pada metode penjadwalanPreemptive).
Solusi Critical Section Pada Perangkat Lunak
Dengan menggunakan algoritma-alogoritma yang nilai kebenarannya tidak tergantung pada asumsi-asumsi lain, selain bahwa setiap proses berjalan pada kecepatan yang bukan nol. Berikut Algoritmanya:
Algoritma I
Algoritma I mencoba mengatasi masalah critical section untuk dua proses. Algoritma ini menerapkan sistem bergilir kepada kedua proses yang ingin mengeksekusi critical section, sehingga kedua proses tersebut harus bergantian menggunakan critical section.
Gambar 1 Algoritma I
Algoritma ini menggunakan variabel bernama turn, nilai turn menentukan proses mana yang boleh memasuki critical section dan mengakses data yang di-sharing. Pada awalnya variabel turn diinisialisasi 0, artinya P0 yang boleh mengakses critical section. Jika turn= 0 dan P0 ingin menggunakan critical section, maka ia dapat mengakses critical section-nya. Setelah selesai mengeksekusi critical section, P0 akan mengubah turn menjadi 1, yang artinya giliran P1 tiba dan P1 diperbolehkan mengakses critical section. Ketika turn= 1 dan P0 ingin menggunakan critical section, maka P0 harus menunggu sampai P1 selesai menggunakan critical section dan mengubah turn menjadi 0.
Ketika suatu proses sedang menunggu, proses tersebut masuk ke dalam loop, dimana ia harus terus-menerus mengecek variabel turn sampai berubah menjadi gilirannya. Proses menunggu ini disebut busy waiting. Sebenarnya busy waitingmesti dihindari karena proses ini menggunakan CPU. Namun untuk kasus ini, penggunaan busy waiting diijinkan karena biasanya proses menunggu hanya berlangsung dalam waktu yang singkat.
Pada algoritma ini masalah muncul ketika ada proses yang mendapat giliran memasuki critical section tapi tidak menggunakan gilirannya sementara proses yang lain ingin mengakses critical section. Misalkan ketika turn= 1 dan P1 tidak menggunakan gilirannya maka turn tidak berubah dan tetap 1. Kemudian P0 ingin menggunakan critical section, maka ia harus menunggu sampai P1 menggunakan critical section dan mengubah turn menjadi 0. Kondisi ini tidak memenuhi syarat progress karena P0 tidak dapat memasuki critical sectionpadahal saat itu tidak ada yang menggunakan critical section dan ia harus menunggu P1 mengeksekusi non- critical section-nya sampai kembali memasuki critical section. Kondisi ini juga tidak memenuhi syarat bounded waiting karena jika pada gilirannya P1 mengakses critical section tapi P1 selesai mengeksekusi semua kode dan terminate, maka tidak ada jaminan P0 dapat mengakses critical section dan P0-pun harus menunggu selamanya.
Algoritma II
Algoritma II juga mencoba memecahkan masalah critical section untuk dua proses. Algoritma ini mengantisipasi masalah yang muncul pada algoritma I dengan mengubah penggunaan variabel turn dengan variabel flag. Variabel flagmenyimpan kondisi proses mana yang boleh masuk critical section. Proses yang membutuhkan akses ke critical section akan memberikan nilai flag-nya true. Sedangkan proses yang tidak membutuhkan critical section akan men- set nilai flagnya bernilai false.
Gambar 2 Algoritma II
Suatu proses diperbolehkan mengakses critical section apabila proses lain tidak membutuhkan critical section atau flag proses lain bernilai false. Tetapi apabila proses lain membutuhkan critical section (ditunjukkan dengan nilai flag-nyatrue), maka proses tersebut harus menunggu dan "mempersilakan" proses lain menggunakan critical section-nya. Disini terlihat bahwa sebelum memasukicritical section suatu proses melihat proses lain terlebih dahulu (melalui flag-nya), apakah proses lain membutuhkan critical section atau tidak.
Awalnya flag untuk kedua proses diinisialisai bernilai false, yang artinya kedua proses tersebut tidak membutuhkan critical section. Jika P0 ingin mengaksescritical section, ia akan mengubah flag[0] menjadi true. Kemudian P0 akan mengecek apakah P1 juga membutuhkan critical section, jika flag[1] bernilaifalse maka P0 akan menggunakan critical section. Namun jika flag[1] bernilaitrue maka P0 harus menunggu P1 menggunakan critical section dan mengubahflag[1] menjadi false.
Pada algoritma ini masalah muncul ketika kedua proses secara bersamaan menginginkan critical section, kedua proses tersebut akan men- set masing-masing flag-nya menjadi true. P0 men- set flag[0] = true, P1 men- set flag[1] = true. Kemudian P0 akan mengecek apakah P1 membutuhkan critical section. P0 akan melihat bahwa flag[1] = true, maka P0 akan menunggu sampai P1 selesai menggunakan critical section. Namun pada saat bersamaan, P1 juga akan mengecek apakah P0 membutuhkan critical section atau tidak, ia akan melihat bahwa flag[0] = true, maka P1 juga akan menunggu P0 selesai menggunakan critical section-nya. Kondisi ini menyebabkan kedua proses yang membutuhkan critical section tersebut akan saling menunggu dan "saling mempersilahkan" proses lain untuk mengakses critical section, akibatnya malah tidak ada yang mengakses critical section. Kondisi ini menunjukkan bahwa Algoritma II tidak memenuhi syarat progress dan syarat bounded waiting, karena kondisi ini akan terus bertahan dan kedua proses harus menunggu selamanya untuk dapat mengakses critical section.
Algoritma III
Algoritma III ditemukan oleh G.L. Petterson pada tahun 1981 dan dikenal juga sebagai Algoritma Petterson. Petterson menemukan cara yang sederhana untuk mengatur proses agar memenuhi mutual exclusion. Algoritma ini adalah solusi untuk memecahkan masalah critical section pada dua proses. Ide dari algoritma ini adalah menggabungkan variabel yang di- sharing pada Algoritma I dan Algoritma II, yaitu variabel turn dan variabel flag. Sama seperti pada Algoritma I dan II, variabel turn menunjukkan giliran proses mana yang diperbolehkan memasuki critical section dan variabel flag menunjukkan apakah suatu proses membutuhkan akses ke critical section atau tidak.
Gambar 3 Algoritma III
Awalnya flag untuk kedua proses diinisialisai bernilai false, yang artinya kedua proses tersebut tidak membutuhkan akses ke critical section. Kemudian jika suatu proses ingin memasuki critical section, ia akan mengubah flag-nya menjadi true (memberikan tanda bahwa ia butuh critical section) lalu proses tersebut memberikan turn kepada lawannya. Jika lawannya tidak menginginkancritical section (flag-nya false), maka proses tersebut dapat menggunakancritical section, dan setelah selesai menggunakan critical section ia akan mengubah flag-nya menjadi false. Tetapi apabila proses lawannya juga menginginkan critical section maka proses lawan-lah yang dapat memasukicritical section, dan proses tersebut harus menunggu sampai proses lawan menyelesaikan critical section dan mengubah flag-nya menjadi false.
Misalkan ketika P0 membutuhkan critical section, maka P0 akan mengubahflag[0] = true, lalu P0 mengubah turn= 1. Jika P1 mempunyai flag[1] = false, (berapapun nilai turn) maka P0 yang dapat mengakses critical section. Namun apabila P1 juga membutuhkan critical section, karena flag[1] = true dan turn= 1, maka P1 yang dapat memasuki critical section dan P0 harus menunggu sampai P1 menyelesaikan critical section dan mengubah flag[1] = false, setelah itu barulah P0 dapat mengakses critical section.
Bagaimana bila kedua proses membutuhkan critical section secara bersamaan? Proses mana yang dapat mengakses critical section terlebih dahulu? Apabila kedua proses (P0 dan P1) datang bersamaan, kedua proses akan menset masing-masing flag menjadi true (flag[0] = true dan flag[1] = true), dalam kondisi ini P0 dapat mengubah turn = 1 dan P1 juga dapat mengubah turn = 0. Proses yang dapat mengakses critical section terlebih dahulu adalah proses yang terlebih dahulu mengubah turn menjadi turn lawannya. Misalkan P0 terlebih dahulu mengubah turn= 1, lalu P1 akan mengubah turn= 0, karena turn yang terakhir adalah 0 maka P0-lah yang dapat mengakses critical section terlebih dahulu dan P1 harus menunggu.
Algoritma III memenuhi ketiga syarat yang dibutuhkan. Syarat progress danbounded waiting yang tidak dipenuhi pada Algoritma I dan II dapat dipenuhi oleh algoritma ini karena ketika ada proses yang ingin mengakses critical section dan tidak ada yang menggunakan critical section maka dapat dipastikan ada proses yang bisa menggunakan critical section, dan proses tidak perlu menunggu selamanya untuk dapat masuk ke critical section.
Algoritma Tukang Roti
Algoritma Tukang Roti adalah solusi untuk masalah critical section pada n-buah proses. Algoritma ini juga dikenal sebagai Lamport's Baker Algorithm. Ide algoritma ini adalah dengan menggunakan prinsip penjadwalan seperti yang ada di tempat penjualan roti. Para pelanggan yang ingin membeli roti sebelumnya harus mengambil nomor urut terlebih dahulu dan urutan orang yang boleh membeli ditentukan oleh nomor urut yang dimiliki masing-masing pelanggan tersebut.
Prinsip algoritma ini untuk menentukan proses yang boleh mengakses critical section sama seperti ilustrasi tukang roti diatas. Proses diibaratkan pelanggan yang jumlahnya n-buah dan tiap proses yang membutuhkan critical sectiondiberi nomor yang menentukan proses mana yang diperbolehkan untuk masuk kedalam critical section. Nomor yang diberikan adalah sekuensial atau terurut, tapi seperti juga nomor urut yang ada di tukang roti, tidak ada jaminan bahwa tiap proses mendapat nomor urut yang berbeda. Untuk mengatasinya digunakan parameter lain yaitu proses ID. Dikarenakan tiap proses memiliki proses ID yang unik dan terurut maka dapat dipastikan hanya satu proses yang dapat mengakses critical section dalam satu waktu. Proses yang dapat mengakses critical section terlebih dahulu adalah proses yang memiliki nomor urut paling kecil. Apabila ada beberapa proses yang memiliki nomor yang sama maka proses yang mempunyai nomor ID paling kecil yang akan dilayani terlebih dahulu.
Kesimpulan :
Solusi critical section harus memenuhi ketiga syarat berikut:
- Mutual Exclusion
- Progress
- Bounded Waiting
Algoritma I dan II terbukti tidak dapat memecahkan masalah critical sectionuntuk dua proses karena tidak memenuhi syarat progress dan bounded waiting. Algoritma yang dapat menyelesaikan masalah critical section pada dua proses adalah Algoritma III. Sedangkan untuk masalah critical section pada n-buah proses dapat diselesaikan dengan menggunakan Algoritma Tukang Roti
Solusi Critical Section pada Perangkat Keras
Tergantung pada beberapa instruksi mesin tertentu, misalnya dengan me-non-aktifkan interupsi atau dengan mengunci suatu variabel tertentu.
sumber 3
0 komentar:
Post a Comment