Tugas 2 SO "Critical Section"

Critical Section

      Critical section adalah dengan mendesain sebuah protokol di mana proses-proses dapat menggunakannya secara bersama-sama. Setiap proses harus ‘meminta izin’ untuk memasuki critical section-nya. Bagian dari kode yang mengimplementasikan izin ini disebut entry section. Akhir dari critical section itu disebut exit section. Bagian kode selanjutnya disebut remainder section.

Struktur umum dari proses Pi yang memiliki segmen critical section adalah :

do {

entry section

critical section

exit section

remainder section

} while (1);

Solusi dari masalah critical section harus memenuhi tiga syarat berikut:

1. Mutual Exclusion.

Jika suatu proses sedang menjalankan critical section-nya, maka proses-proses lain tidak dapat menjalankan critical section mereka. Dengan kata lain, tidak ada dua proses yang berada dicritical section pada saat yang bersamaan.

2. Terjadi kemajuan (progress).

Jika tidak ada proses yang sedang menjalankan critical section-nya dan ada proses-proses lain yang ingin masuk ke critical section, maka hanya proses-proses yang yang sedang berada dalamentry section saja yang dapat berkompetisi untuk mengerjakan critical section.

3. Ada batas waktu tunggu (bounded waiting).

Jika seandainya ada proses yang sedang menjalankan critical section, maka proses lain memiliki waktu tunggu yang ada batasnya untuk menjalankan critical section -nya, sehingga dapat dipastikan bahwa proses tersebut dapat mengakses critical section-nya (tidak mengalamistarvation: proses seolah-olah berhenti, menunggu request akses ke critical sectiondiperbolehkan).

Solusi Untuk Dua Proses

Ada dua jenis solusi masalah critical section, yaitu:

1. Solusi 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.

2. Solusi perangkat keras.

Tergantung pada beberapa instruksi mesin tertentu, misalnya dengan me-non-aktifkan interupsi atau dengan mengunci suatu variabel tertentu

Selanjutnya akan dibahas sebuah algoritma sebagai solusi masalah dari critical section yang memenuhi tiga syarat seperti yang telah disebutkan di atas. Solusi ini tidak tergantung pada asumsi mengenai instruksi-instruksi perangkat keras atau jumlah prosesor yang dapat didukung oleh perangkat keras. Namun, kita mengasumsikan bahwa insruksi bahasa mesin yang dasar (instruksi-instruksi primitif seperti load,store, dan test) dieksekusi secara atomik. Artinya, jika dua instruksi tersebut dieksekusi secara konkuren, hasilnya ekuivalen dengan eksekusi instruksi tersebut secara sekuensial dalam urutan tertentu. Jadi, jika load dan store dieksekusi secara konkuren, load akan mendapatkan salah satu dari nilai yang lama atau nilai yang baru, tetapi tidak kombinasi dari keduanya.

         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.

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 turnmenjadi 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 waiting mesti 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 section padahal 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 danterminate, 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 flag menyimpan 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 membutuhkancritical sectionakan men- set nilai flagnya bernilai false.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-nya true), maka proses tersebut harus menunggu dan “mempersilakan” proses lain menggunakan critical section-nya. Disini terlihat bahwa sebelum memasuki critical 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 mengakses critical section, ia akan mengubah flag[0] menjadi true. Kemudian P0 akan mengecek apakah P1 juga membutuhkan critical section, jika flag[1] bernilai false maka P0 akan menggunakan critical section. Namun jika flag[1] bernilai true maka P0 harus menunggu P1 menggunakan critical section dan mengubah flag[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-setflag[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 mengaksescritical 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 variabelflag. 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 kecritical sectionatau tidak.

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 mengubahflag-nya menjadi true (memberikan tanda bahwa ia butuh critical section) lalu proses tersebut memberikan turn kepada lawannya. Jika lawannya tidak menginginkan critical section (flag-nya false), maka proses tersebut dapat menggunakan critical 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 memasuki critical section, dan proses tersebut harus menunggu sampai proses lawan menyelesaikan critical sectiondan mengubah flag-nya menjadi false.

Misalkan ketika P0 membutuhkan critical section, maka P0 akan mengubah flag[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 sectionterlebih 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 dan bounded waiting yang tidak dipenuhi pada Algoritma I dan II dapat dipenuhi oleh algoritma ini karena ketika ada proses yang ingin mengaksescritical 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.

Solusi Untuk Proses Jamak: 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.

Algoritma ini dapat digunakan untuk memecahkan masalah critical section untuk n buah proses, yang diilustrasikan dengan n buah pelanggan. Ketika memasuki toko, setiap pelanggan menerima sebuah nomor. Sayangnya, algoritma tukang roti ini tidak dapat menjamin bahwa dua proses (dua pelanggan) tidak akan menerima nomor yang sama. Dalam kasus di mana dua proses menerima nomor yang sama, maka proses dengan nomor ID terkecil yang akan dilayani dahulu. Jadi, jika Pi dan Pj menerima nomor yang sama dani < j, maka Pi dilayani dahulu. Karena setiap nama proses adalah unik dan berurut, maka algoritma ini dapat digunakan untuk memecahkan masalah critical sectionuntuk n buah proses.

Struktur data umum algoritma ini adalah

boolean choosing[n];

int number [n];

Awalnya, struktur data ini diinisialisasi masing-masing ke false dan 0, dan menggunakan notasi berikut:

- (a, b) < (c, d) jika a < a=” c”>

- max(a0, …, an-1) adalah sebuah bilangan k, sedemikian sehingga k >= ai untuk setiap i= 0, …, n – 1

Algoritma Tukang Roti

do {

choosing[i] = true;

number[i] = max(number[0], number [1], ..., number [n+1])+1;
choosing[i] = false;
    for (j=0; j < n; j++) {

while ((number[j]!=0) && ((number[j],j) < number[i],i)));
while (choosing[j]);
    }

number[i] = 0;
<foreignphrase>critical section</foreignphrase>

} while (1);

<foreignphrase>remainder section</foreignphrase>

       Rangkuman

          Solusi critical section harus memenuhi ketiga syarat berikut:

1. Mutual Exclusion
2. Progress
3. Bounded Waiting

Algoritma I dan II terbukti tidak dapat memecahkan masalah critical section untuk dua proses karena tidak memenuhi syarat progress dan bounded waiting. Algoritma yang dapat menyelesaikan masalah critical sectionpada dua proses adalah Algoritma III. Sedangkan untuk masalah critical section pada n-buah proses dapat diselesaikan dengan menggunakan Algoritma Tukang Roti.

Penjadwalan CPU secara garis besar dibagi menjadi 2, yaitu Penjadwalan Preemptive dan Penjadwalan Non Preemptive.

1. Penjadwalan Pre-emptive

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 I/O.

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 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.

Lama waktu suatu proses diizinkan untuk dieksekusi dalam penjadwalan Preemptive 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.

Dalam waktu-waktu tertentu, proses dapat dikelompokkan ke dalam dua kategori: proses yang memiliki Burst I/O 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 penjadwalan Preemptive, hal tersebut dapat dihindari.

Keuntungan penggunaan penjadwalan pre-emptive:

a.       sistem lebih responsif daripada sistem yang memakai penjadwalan Non Preemptive.

b.       Sistem terhindar dari keadaan busywait.

contoh sistem operasi yang menerapkan penjadwalan Preemptive:

Windows 95, Windows XP, Linux, Unix, AmigaOS, MacOS X, dan Windows NT .

2. Penjadwalan Non Pre-emptive

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:

1. Berjalan dari running state sampai waiting state.

2. Dihentikan.

Ini berarti CPU menjaga proses sampai proses itu pindah ke waiting state ataupun dihentikan (proses tidak diganggu). Metode ini digunakan oleh Microsoft Windows 3.1 dan Macintosh. Ini adalah metode yang dapat digunakan untuk platforms hardware tertentu, karena tidak memerlukan perangkat keras khusus (misalnya timer yang digunakan untuk meng interupt pada metode penjadwalan Preemptive).

Dispatcher

Komponen yang lain yang terlibat dalam penjadwalan CPU adalah dispatcher.

Dispatcher adalah modul yang memberikan kontrol CPU kepada proses yang sedang terjadwal. Fungsinya:

1. Context switching

Mengganti state dari suatu proses dan mengembalikannya untuk menghindari monopoli CPU time. Context switching dilakukan untuk menangani suatu interrupt(misalnya menunggu waktu I/O). Untuk menyimpan state dari proses-proses yang terjadwal sebuah Process Control Block harus dibuat untuk mengingat proses-proses yang sedang diatur scheduler. Selain state suatu proses, PCB juga menyimpan process ID, program counter(posisi saat ini pada program), prioritas proses dan data-data tambahan lainnya.

1. Switching to user mode dari kernel mode.
2. Lompat dari suatu bagian di progam user untuk mengulang program.

Sumber : 

http://agustriadi17.blogspot.com/2011/03/critical-section.html

https://mediekaputra.wordpress.com/2011/03/26/critical-section/