Mutual Exclusion merupakan kondisi dimana suatu sumber daya tidak dapat digunakan bersamaan dalam waktu yang bersamaan. Misalnya proses pada penggunaan printer dan disk drive. Pada alat percetakan printer, terdapat proses yang melakukan penjadwalan dan pengendalian percetakan data di printer. Dalam ruang disk terdapat slot-slot yang digunakan untuk menyimpan data yang akan dijadwalkan untuk dicetak. Kondisi dimana suatu bagian program yang sedang mengakses memory atau sumber daya yang dipakai bersama ini disebut critical region / section. Jika critical section menghalangi proses lain dalam antrian akan menyebabkan terjadinya starvation dan deadlock. Deadlock adalah suatu kondisi dimana dua proses atau lebih tidak dapat meneruskan eksekusinya oleh pemroses. Biasanya deadlock terjadi karena proses mengalami startvation, yaitu suatu job yang sedang dieksekusi dan eksekusi job tersebut tidak ada hentinya, tidak diketahui kapan berhentinya proses tersebut atau bahkan job yang antri bisa dikatakan mempunyai status mati, padahal proses-proses lain sedang menunggu sumber daya proses.
Hanya terdapat satu program yang diijinkan masuk ke critical region. Pemrogram tidak bisa bergantung pada OS untuk memahami dan memaksakan batasan ini, karena apa yang dimaksud program tidak diketahui oleh sistem operasi. Hanya saja, system operasi menyediakan layanan (system call) yang bertujuan untuk mencegah proses lain masuk ke critical section yang sedang digunakan proses tertentu. Pemrograman harus menspesifikasikan bagian-bagian critical section, sehingga sistem operasi akan menjaganya. Karena Mutual exclusion disini adalah jaminan hanya satu proses yang mengakses sumber daya pada satu interval waktu tertentu. Sumber daya yang tidak dapat dipakai bersama pada saat bersamaan.
Sinkronisasi merupakan proses pengaturan jalannya beberapa proses pada saat yang bersamaan. Tujuannya untuk menghindari terjadinya inkonsitensi data karena pengaksesan oleh beberapa proses yang berbeda (mutual exclusion) serta untuk mengatur urutan jalannya proses-proses sehingga dapat berjalan dengan lancar dan terhindar dari deadlock dan starvation. Sinkronisasi umumnya dilakukan dengan bantuan perangkat sinkronisasi. Penyelesaian terhadap masalah ini sangat penting karena perkembangan teknologi sistem komputer menuju ke sistem multiprocessing, terdistribusi dan paralel yang mengharuskan adanya proses-proses kongkuren.
Suksesnya proses konkurensi memerlukan pendefinisian critical section dan memaksakan mutual exclusion di antara proses-proses konkuren yang sedang berjalan. Pemaksaan mutual exclusion merupakan landasan pemrosesan konkuren. Fasilitas atau kemampuan menyediakan dukungan mutual exclusion harus memenuhi 6 kriteria sebagai berikut:
- Mutual exclusion harus menjamin bahwa tidak ada proses lain yang berjalan kecuali dirinya sendiri (proses tunggal).
- Proses yang berada di noncritical section, dilarang menghalangi proses lain yang ingin masuk critical section. Karena bisa menyebabkan terjadinya starvation.
- Menjamin bahwa proses yang ingin masuk critical section tidak menunggu selama waktu yang tak terhingga. Karena dapat mengakibatkan deadlock dan antrian prosesnya akan menjadi bertambah panjang.
- Ketika tidak ada proses apapun dalam critical section, maka proses yang ingin masuk critical section harus diijinkan masuk tanpa waktu tunda.
- Tidak ada asumsi mengenai kecepatan relatif proses atau jumlah yang ada.
- Proses hanya tinggal pada critical section selama satu waktu yang berhingga
Beberapa metode yang diusulkan untuk menjamin Mutual Exclusion, antara lain:
- Metode Variable Lock Locking
- Metode bergantian secara ketat
Ada beberapa cara untuk menyelesaikan masalah mutual exclusion, antara lain :
- Hanya ada dua proses, yaitu P0 dan P1
- Struktur umum dari proses adalah Pi( proses lain Pj)
- Proses-proses dapat share variable untuk singkronisasi.
Pada bagian ini akan dibatasi pada aplikasi ke 2 proses yaitu Pi dan Pj , atau P0dan P1
Secara umum, jika ada proses Pimaka akan digunakan proses Pj sebagai proses lainnya, dengan j=1-i. Ada beberapa algoritma penyelesaian mutual exclusion dengan menggunakan sinkronisasi, yakni Kedua proses akan berbagi suatu variabel bertipe integer yaitu turn yang diinisialisaikan dengan 0 (atau 1). Jika turn=0, maka proses P0 diijinkan untuk mengeksekusi critical section. Struktur prosesnya seperti di bawah ini:
Shared variable:
int turn;
initially turn = 0
turn = 1 > Pi dapat masuk ke dalam critical section
Process Pi
do{
while(turn! = i);
critical section
turn = j;
reminder section
}while(1);
Solusi ini sudah memenuhi mutual exclusion tapi tidak memenuhi progress dan bounded waiting, karena pada suatu saat hanya ada satu proses yang masuk critical section. Sebagai contoh:
Jika P0 meninggalkan critical section, maka nilai turn=1 yang berarti bahwa P1 siap untuk masuk ke critical section;
- P1 selesai menggunakan critical section dengan cepat maka baik P1 maupun P0 beradapada remainder section dengan nilai turn=0.
- P0 kembali menggunakan critical section dengan cepat dan segera masuk ke remainder section dengan nilai turn=1.
- P0 hendak kembali menggunakan critical section namun nilai turn=1.Terlihat bahwa P1 yang berada pada remainder section memblok P0 sehingga tidak dapat memasuki critical section. Hal ini menentang progress, yaitu proses diblok oleh proses yang tidak berada di critical section.
2) Algoritma 2
Pada algoritma ini menggunakan flag untuk setiap proses dan memeriksa flag proses yang lain dan tidak akan masuk critical section jika ada proses lain yang sedang masuk. Masalah pada algoritma-1 tidak memberika cukup informasi mengenai status proses. Hanya mempertimbangkan yang masuk critical section. Untuk mengatasi masalah ini variabel “turn” diganti dengan :
var flag : array [0 ..1] of boolean;
Semua elemen array diinisialisasikan dengan false. Jika flag[0] bernilai true, maka nilai itu akan mengindikasikan bahwa P0 siap memasuki critical section. Struktur P0 terlihat pada proses dibawah ini.
Shared variabel :
Booleanflag[2];
initially flag [0] = flag [1] = false.
flag [i] = true Pi siap untuk masuk ke dalam critical section
Process Pi
do {
flag[i] := true;
while (flag[j]) ; critical section
flag [i] = false;
remainder section
} while (1);
Pada algoritma ini, proses P0 pertama kali menetapkan flag[i] = true, nilai ini mengindikasikan bahwa P0 siap memasuki critical section. Kemudian P0 mengecek untuk menyakinkan P1 tidak akan memasuki tidak kan memasuki critical section. Jika P1 juga telah memasuki critical section, maka P0 harus menunggu sampai P1 tidak membutuhkan critical section lagi (sampai flag[1] =false). Secepatnya P0 memasuki critical section. Pada exit section, P0 akan mengeset flag[0] menjadi false, hal ini mengijinkan proses la in (jika sedang menunggu) untuk memasuki critical section.Pada solusi ini, kondisi mutual exclusion telah dipenuhi tetapi tidak memenuhi progress. Untuk menggambarkan hal tersebut dapat dilihat :
T0 P0 menetapkan flag[0] = true;
T1 P1 menetapkan flag[1] = true;
Sekarang P0 dan P1 bersama-sama ada di statement while.
Algoritma –3 (Peterson)
Algoritma ketiga ini diperkenalkan oleh peterson. Dimana setiap proses mengset sebuah flag untuk meminta ijin masuk. Kemudian setiap proses men-toggle bit untuk mengijinkan proses lain menjadi yang pertama. Algoritma ini merupakan kombinasi antara algoritma –1 dan algoritma-2. Proses ini membutuhkan 2 variabel, yaitu :
Var Flag :array [0 .. 1] of boolean;
Turn : 0 .. 1;
Nilai awal flag[0] = flag = false, dan nilai turn (0 atau 1). Struktur proses P1 seperti terlihat pada proses dibawah ini :
do {
flag [i]:= true;
turn = j;
while (flag [j] and turn = j) ;
critical section
flag [i] = false;
remainder section
} while (1);
Pada algoritma ini sudah memenuhi ketiga persyaratan, memecahkan critical section untuk kedua proses. Untuk masuk ke critical section, proses P0 mengeset flag[0] = true, dan melihat apakah ada proses lain yang mencoba masuk critical section (turn=1).
3) Algoritma Bakery
Critical section untuk n proses:
Sebelum masuk ke critical section. Proses mendapatkan nomor. Yang memiliki nomor paling kecil lebih dahulu memasuki critical section. Pemegang nomor terkecil akan masuk ke critical section. Jika ada 2 proses atau lebih proses (Pi dan Pj) menerima nomor yang sama, maka proses yang memiliki indeks terkecil (i < j) dilayani lebih dahulu untuk masuk ke critical section kemudian melayani proses selanjutnya. Skema penomoran selalu naik berurutan, misal: 1,2,3,4,4,5,6,6,6…
shared data
boolean choosing[n];
int number[n];
Struktur data diinisialisaikan dengan false dengan nilai 0. Algoritmanya sebagai berikut:
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 (choosing[j]) ;
while ((number[j] != 0) && (number[j,j] < number[i,i])) ;
}
critical section
number[i] = 0;
remainder section
} while (1);
4) Algoritma Dekker
Algoritma ini diperkenalkan oleh Dekker, seorang matematikawan dari Belanda. Algoritma ini memiliki ciri-ciri khusus sebagai berikut:
- Tidak memerlukan instruksi-instruksi perangkat keras khusus.
- Proses yang beroperasi di remainder section tidak dapat mencegah proses lain yang ingin masuk critical section.
- Proses yang ingin masuk critical section akan segera memasuki kawasan tersebut jika dimungkinkan.
int share = 6;
int x = 0;
int y = 0;
bool z = true;
chan q_0_1 = [0] of {bit};
chan q_0_2 = [0] of {bit};
proctype A() {
bool dapat_dishare = true;
do
::atomic{
z -> x = 10;
};
::atomic{
dapat_dishare -> q_0_1?0;
share = share+1;
dapat_dishare = false;
q_0_1?1;
};
::atomic{
!dapat_dishare -> q_0_2?0;
dapat_dishare = true;
q_0_2?1;
};
od;
}
proctype B() {
bool dapat_dishare = false;
do
::atomic{
z -> y = 11;
};
::atomic{
dapat_dishare -> q_0_2!0;
share = share-1;
dapat_dishare = false;
q_0_2!1;
};
::atomic{
!dapat_dishare -> q_0_1!0;
dapat_dishare = true;
q_0_1!1;
};
od;
}
init {
atomic{
run A();
run B();
};
}
}
Mencegah Mutual Exclusion
Mutual exclusion benar-benar tak bisa dihindari. Hal ini dikarenakan tidak ada sumber daya yang dapat digunakan bersama-sama, seperti proses pada printer sebelumnya. jadi sistem harus membawa sumber daya yang tidak dapat digunakan bersama-sama.
