Algoritma 3

 

Algoritma 3 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 memecahka   n masalah critical section pada dua proses. Ide dari algoritma ini adalah menggabungkan variabel yang di- sharing pada Algoritma 1 dan Algoritma 2, yaitu variabel turn dan variabel flag. Sama seperti pada Algoritma 1I dan 2, 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.

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 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 section dan 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 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, karenaturn yang terakhir adalah 0 maka P0-lah yang dapat mengakses critical section terlebih dahulu dan P1 harus menunggu.

Algoritma 3 memenuhi ketiga syarat yang dibutuhkan. Syarat progress dan bounded waiting yang tidak dipenuhi pada Algoritma 1 dan 2 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.

1.   Semaphore

Semaphore adalah pendekatan yang diajukan oleh Djikstra seorang seorang ilmuwan komputer, dengan prinsip bahwa dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Seperti proses dapat dipaksa berhenti pada suatu saat, sampai proses mendapatkan penanda tertentu itu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan struktur penanda yang cocok untuk kebutuhan itu. Variabel khusus untuk penanda ini disebut semaphore.

Semaphore mempunyai dua sifat, yaitu:

1.     Semaphore dapat diinisialisasi dengan nilai non-negatif.

2.     Terdapat dua operasi terhadap semaphore, yaitu Down dan Up. Usulan asli yang disampaikan Djikstra adalah operasi P dan V.

1.     Operasi Down

Operasi ini menurunkan nilai semaphore, jika nilai semaphore menjadi non-positif maka proses yang mengeksekusinya diblocked. Operasi Down adalah atomic, tak dapat diinterupsi sebelaum diselesaikan.Emnurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan memblocked sebagai instruksi tunggal. Sejak dimulai, tak ada proses alain yang dapat mengakses semaphore sampai operasi selesai atau diblocked.

2.     Operasi Up

Operasi Up menakkan nilai semaphore. Jika satu proses atau lebih diblocked pada semaphore itu tak dapat menyelesaikan operasi Down, maka salah satu dipilih oleh system dan menyelesaikan operasi Down-nya. Urutan proses yang dipilih tidak ditentukan oleh Djikstra, dapat dipilih secara acak. Adanya semaphore mempermudah persoalan mutual exclusion. Skema penelesaian mutual exclusion mempunyai bagan sebagai berikut:

Sebelum masuk critical section, proses melakukan Down. Bila berhasil maka proses masuk ke critical section. Bila tidak berhasil maka proses di-blocked atas semaphore itu. Proses yang diblocked akan dapat melanjutkan kembali bila proses yang ada di critical section keluar dan melakukan opersai up sehingga menjadikan proses yang diblocked ready dan melanjutkan sehingga opersi Down-nya berhasil.

Penjelasan selanjutnya terdapat pada blog berikut : http://setiawan-alvin.blogspot.com/2013/04/sinkornisasi-deadlock.html

Uraian sebelumnya terdapat pada blog berikut : “link blog heru”