Sistem Operasi: Algoritma 1 & 2

Algoritma 1

     Algoritma 1 mencoba mengatasi masalah criticalsection untuk dua proses. Algoritma ini menerapkan sistem bergilir kepada kedua proses yang ingin mengeksekusi criticalsection, sehingga kedua proses tersebut harus bergantian menggunakan criticalsection.

     Algoritma ini menggunakan variabel bernama turn, nilai turn menentukan proses mana yang boleh memasuki criticalsection dan mengakses data yang di- sharing. Pada awalnya variabel turn diinisialisasi 0, artinya P0 yang boleh mengakses criticalsection. Jika turn= 0 dan P0 ingin menggunakan criticalsection, maka ia dapat mengakses criticalsection-nya. Setelah selesai mengeksekusi criticalsection, P0 akan mengubah turn menjadi 1, yang artinya giliran P1 tiba dan P1 diperbolehkan mengakses criticalsection. Ketika turn= 1 dan P0 ingin menggunakan criticalsection, maka P0 harus menunggu sampai P1 selesai menggunakan criticalsection 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 busywaiting. Sebenarnya busywaiting mesti dihindari karena proses ini menggunakan CPU. Namun untuk kasus ini, penggunaan busywaiting diijinkan karena biasanya proses menunggu hanya berlangsung dalam waktu yang singkat.

     Pada algoritma ini masalah muncul ketika ada proses yang mendapat giliran memasuki criticalsection tapi tidak menggunakan gilirannya sementara proses yang lain ingin mengakses criticalsection. Misalkan ketika turn= 1 dan P1 tidak menggunakan gilirannya maka turn tidak berubah dan tetap 1. Kemudian P0 ingin menggunakan criticalsection, maka ia harus menunggu sampai P1 menggunakan criticalsection dan mengubah turn menjadi 0. Kondisi ini tidak memenuhi syarat progress karena P0 tidak dapat memasuki criticalsection padahal saat itu tidak ada yang menggunakan criticalsection dan ia harus menunggu P1 mengeksekusi non- criticalsection-nya sampai kembali memasuki criticalsection. Kondisi ini juga tidak memenuhi syarat boundedwaiting karena jika pada gilirannya P1 mengakses criticalsection tapi P1 selesai mengeksekusi semua kode dan terminate, maka tidak ada jaminan P0 dapat mengakses criticalsection dan P0-pun harus menunggu selamanya.

 

Algoritma 2

     Algoritma 2 juga mencoba memecahkan masalah criticalsection untuk dua proses. Algoritma ini mengantisipasi masalah yang muncul pada algoritma 1 dengan mengubah penggunaan variabel turn dengan variabel flag. Variabel flag menyimpan kondisi proses mana yang boleh masuk criticalsection. Proses yang membutuhkan akses ke criticalsection akan memberikan nilai flag-nya true. Sedangkan proses yang tidak membutuhkan criticalsection akan men- set nilai flagnya bernilai false.

  Suatu proses diperbolehkan mengakses criticalsection apabila proses lain tidak membutuhkan criticalsection atau flag proses lain bernilai false. Tetapi apabila proses lain membutuhkan criticalsection(ditunjukkan dengan nilai flag-nya true), maka proses tersebut harus menunggu dan "mempersilakan" proses lain menggunakan criticalsection-nya. Disini terlihat bahwa sebelum memasuki criticalsectionsuatu proses melihat proses lain terlebih dahulu (melalui flag-nya), apakah proses lain membutuhkan criticalsection atau tidak.

     Awalnya flag untuk kedua proses diinisialisai bernilai false, yang artinya kedua proses tersebut tidak membutuhkan criticalsection. Jika P0 ingin mengakses criticalsection, ia akan mengubah flag[0] menjadi true. Kemudian P0 akan mengecek apakah P1 juga membutuhkan criticalsection, jika flag[1] bernilai false maka P0 akan menggunakan criticalsection. Namun jika flag[1] bernilai true maka P0 harus menunggu P1 menggunakan criticalsection dan mengubah flag[1] menjadi false.

     
     Pada algoritma ini masalah muncul ketika kedua proses secara bersamaan menginginkan criticalsection, 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 criticalsection. P0 akan melihat bahwa flag[1] = true, maka P0 akan menunggu sampai P1 selesai menggunakancriticalsection. Namun pada saat bersamaan, P1 juga akan mengecek apakah P0 membutuhkan criticalsection atau tidak, ia akan melihat bahwa flag[0] = true, maka P1 juga akan menunggu P0 selesai menggunakan criticalsection-nya. Kondisi ini menyebabkan kedua proses yang membutuhkan criticalsection tersebut akan saling menunggu dan "saling mempersilahkan" proses lain untuk mengaksescriticalsection, akibatnya malah tidak ada yang mengakses criticalsection. Kondisi ini menunjukkan bahwa Algoritma II tidak memenuhi syarat progress dan syarat boundedwaiting, karena kondisi ini akan terus bertahan dan kedua proses harus menunggu selamanya untuk dapat mengakses criticalsection.

Penjelasan selanjutnya : Algoritma 3

Penjelasan sebelumnya : Solusi ke masalah criticalsection