MUTUAL EXCLUTION

       I.            Pengertian Mutual Exclution

Pada system computer terdapat sumber daya yang tidak dapat dipakai bersama pada saat yang bersamaan seperti pada penggunaan printer. Sumber daya seperti hanya dapat menjalankan satu proses pada suatu saat, sumber daya ini disebut sumber daya kritis. Program yang menggunakan sumber daya kritis disebut sedang memasuki critical region / section.

Sistem operasi memberikan fasilitas untuk pemrogram dapat memberikan indikasi keberadaan critical region. Sistem operasi menyediakan layanan ( berupa system call ) untuk mencagah suatu proses masuk kedalam critical region akan tetapi di dalam critical region terdapat proses lain yang sedang berjalan. Mutual exclusion merupakan solusi bagi masalah pada critical region / section. Mutual exclusion adalah persoalan untuk menjamin hanya satu proses saja yang berjalan dalam suatu critical region / section.

    II.            Critical Section

Beberapa proses memiliki suatu segmen kode dimana jika segmen itu dieksekusi, maka proses-proses itu dapat saling mengubah variabel, mengupdate suatu tabel, menulis ke suatu file, dan lain sebagainya, dan hal ini dapat membawa proses tersebut ke dalam bahaya race condition. Segmen kode yang seperti inilah yang disebut Critical Section. Sedangkan race condition sendiri adalah kondisi dimana ada beberapa proses yang memanipulasi suatu data secara kongkuren, sehingga data tersebut tidak sinkron lagi. Nilai akhirnya akan tergantung pada proses mana yang terakhir dieksekusi. Maka dibutuhkan sinkronisasi.

 III.            Sumber Daya

Yang dimaksud dengan sumber daya pada sistem komputer adalah semua komponen yang memberikan fungsi (manfaat) atau dengan pengertian lain adalah semua yang terdapat atau terhubung ke sistem komputer yang dapat untuk memindahkan, menyimpan, dan memproses data, serta untuk mengendalikan fungsi-fungsi tersebut. Sumber daya pada sistem komputer, antara lain :

a. Sumber daya fisik

Contoh dari sumber daya fisik diantaranya keyboard, bar-code reader, mouse, joystick, lightpen, track-ball, touchscreen, pointing devices, floppy disk drive, hard-disk, tape drive, optical disk, CD ROM drive, CRT, LCD, printer, modem, ethernet card, PCMCIA, RAM, cache memory, register, kamera, sound card, radio, digitizer, scanner, plotter, dan sebagainya.

b. Sumber daya abstrak

Terdiri dari :

1.       Data, misalnya :Semaphore untuk pengendalian sinkronisasi proses-proses, PCB (Process Control Block) untuk mencatat dan mengendalikan proses, tabel segmen, tabel page, i-node, FAT, file dan sebagainya.

2.      Program yang berupa kumpulan instruksi yang dapat dijalankan oleh system komputer, yang dapat berupa utilitas dan program aplikasi pengolahan data tertentu.

3.      Proses yang berada di critical section harus menunggu dalam waktu yang berhingga dan proses yang berada didalam critical section pun harus dalam jangka waktu yang berhingga pula

Jelas sekali hal ini harus terjadi pada manajemen proses disebuah operating system, karena hal ini untuk menghindari deadlock. Deadlock sendiri merupakan kondisi terparah karena banyak proses dapat terlibat dan semuanya tidak dapat mengakhiri prosesnya secara benar. Hal ini dapat terjadi jika waktu tunggu proses diluar critical section tidak jelas maka proses tersebut akan masuk kapan saja kedalam critical section, entah itu kosong atau masih ada proses didalam critical section. Jika dalam critical sectionnya masih ada proses maka kasus tersebut telah melanggar mutual exclusion.

Sebaliknya jika waktu proses tidak berhingga atau tidak jelas maka tidak jelas pula kapan critical section kosong, maka proses yang diluar akan selamanya menunggu dan akan terjadi deadlock.

Proses-Proses (Masuk) Ke Daerah Critical Section Tidak Boleh Saling Memblok

Jika proses-proses saling memblok ketika akan masuk ke critical section maka akan terjadi pula deadlock. Ini salah satu penyebab lain deadlock. Karena jika proses-proses saling memblok maka selamanya proses-proses tersebut tidak akan masuk ke critical section, oleh karena itu akan terjadi deadlock atau buntu dan proses-proses yang telah berjalan tidak akan selesai dengan sempurna.

Ketika Tidak Ada Proses Di Critical Section Maka Proses Yang Ingin Masuk Ke Critical Section Harus Diijinkan Tanpa Waktu Tunda

Fungsi seperti itu mutlak harus ada dalam system operasi. Hal ini berfungsi untuk mencegah adanya deadlock. Ketika critical section kosong maka proses selanjutnya harus masuk dan menyelesaikan prosesnya sampai selesai. Jika tidak berarti tidak ada kejelasan waktu tunggu atau tidak ada kejelasanan waktu proses dan hal ini akan menyebabkan deadlock.

 IV.            Metode Penyelesaian Masalah Mutual Exclusion

Ada beberapa metode penyelesaian masalah mutual exclusion, antara lain :

1.         Sinkronisasi.

Algoritma 1

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 P0 terlihat pada gambar dibawah ini :

repeat

while turn ≠0 do

critical section

turn := 1

remainder section

until false

Solusi ini sudah menunjukkan adanya mutual exclusion, karena pada suatu saat hanya ada satu proses yang masuk critical section. Namun belum menunjukkan adanya progress dan bounded waiting. Sebagai contoh:

1.      Jika P0 meninggalkan critical section, maka nilai turn=1 yang berarti bahwa P1  siap untuk masuk ke critical section;

2.      P1 selesai menggunakan critical section dengan cepat maka baik P1  maupun P0 beradapada remainder section dengan nilai turn=0.

3.      P0 kembali menggunakan critical section dengan cepat dan segera masuk ke  remainder section dengan nilai turn=1.

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

Algoritma 2

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 gambar dibawah ini.

repeat

flag[0]:=true;

while flag[1] do

critical section

flag[0]

remainder section

until false

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. Namun progress belum juga dipenuhi. 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. Pada dasarnya, 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 gambar dibawah ini :

repeat

flag[0]:=true;

turn:=1;

while (flag[1] and turn=1) do

critical section

flag[0]

remainder section

until false

Untuk masuk ke critical section, proses P0 mengeset flag[0] = true, dan melihat apakah ada proses lain yang mencoba masuk critical section (turn=1).

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. Jika proses Pi dan Pj menerima nomor, jika i

shared data

var choosing : array[0..n-1] of boolean;

number : array[0..n-1] of integer;

Struktur data diinisialisaikan dengan false dengan nilai 0. Struktur proses P1 seperti terlihat pada gambar dibawah ini :

repeat

choosing[i]:=true;

number[i]:=max(number[0], number[1], …, number[n-1])+1;

choosing[i]:=false;

for j:= 0 to n-1

do begin

while choosing[j] do no_op;

while number[j] ? 0

and (number[j],j) < (number[i],i) do no_op;

end;

critical section

number[i]:=0;

remainder section

until false

Algoritma Dekker

Algoritma ini diperkenalkan oleh Dekker, seorang matematikawan dari Belanda. Algoritma ini memiliki ciri-ciri khusus sebagai berikut:

1.      Tidak memerlukan instruksi-instruksi perangkat keras khusus.\

2.      Proses yang beroperasi di remainder section tidak dapat mencegah proses lain yang ingin masuk critical section.

3.      Proses yang ingin masuk critical section akan segera memasuki kawasan tersebut jika dimungkinkan.

Dimana prosesnya seperti ini :

bool Fail = false;

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();

};

}

2.          Semaphore

Model semaphore secara umum untuk penyelesaian mutual exclusion adalah sebagai berikut :

mtype = { idle, masuk, critical, keluar };

#define state mtype

bool Fail = false;

bool semaphore = false;

proctype USER_0() {

state user_state = idle;

do

::atomic{

user_state==idle ->

if

::user_state = idle;

::user_state = masuk;

fi;

};

::atomic{

((user_state==masuk)&&(!semaphore)) ->

user_state = critical;

semaphore = true;

};

::atomic{

((user_state==masuk)&&(semaphore)) ->

user_state = masuk;

};

::atomic{

user_state==critical ->

if

::user_state = critical;

::user_state = keluar;

fi;

};

::atomic{

user_state==keluar ->

user_state = idle;

semaphore = false;

};

od;

}

proctype USER_1() {

state user_state = idle;

do

::atomic{

user_state==idle ->

if

::user_state = idle;

::user_state = masuk;

fi;

};

::atomic{

((user_state==masuk)&&(!semaphore)) ->

user_state = critical;

semaphore = true;

};

::atomic{

((user_state==masuk)&&(semaphore)) ->

user_state = masuk;

};

::atomic{

user_state==critical ->

if

::user_state = critical;

::user_state = keluar;

fi;

};

::atomic{

user_state==keluar ->

user_state = idle;

semaphore = false;

};

od;

}

init {

atomic{

run USER_0();

run USER_1();

};

}

Pun juga terdapat metode-metode dan Algoritma untuk menjamin Mutual Exclusion, diantaranya :

a. Disabling interrupt / mematikan interupsi

Dengan cara mematikan interupsi yang masuk pada saat proses sedang berada pada critical section-nya. Cara ini kadang cukup berguna untuk kernel tetapi tidak untuk user. Dan cara inipun tidak terlalu baik untuk CPU yang jumlahnya lebih dari satu, dimana disable interrupt hanya mengenai CPU yang sedang menjalankan proses itu dan tidak berpengaruh terhadap CPU lain

b. Lock variables

Setiap proses yang akan mengakses ke critical section-nya harus meng-cek lock variable. Jika 0 berarti proses dapat memasuki critical section-nya dan jika 1 maka proses harus menunggu sampai lock variable = 0. Kelemahannya adalah 2 proses masih dapat memasuki critical section-nya pada saat yang bersamaan. Sewaktu satu proses meng-cek lock variable = 0, pada saat akan men-set 1 ada interupsi untuk melaksanakan proses lain yang juga ingin memasuki critical sectionnya, maka akan terjadi race condition.

c. Strict alternation

Dengan mengamati variable turn untuk menentukan siapa yang akan memasuki critical section-nya bukanlah ide yang baik jika proses lebih lambat dari yang lain.

Contohnya :

While (true)

{

while (turn != 0) /*wait*/;

critical_section ( );

turn = 1;

noncritical_section ( );

}

while (true)

{

while (turn != 1) /*wait*/;

critical_section ( );

turn = 0;

noncritical_section ( );

}

d. Peterson’s Solution

Proses tidak akan diteruskan sampai while terpenuhi, bila interested[other] = TRUE, maka proses akan menunggu sampai FALSE.

Kelemahannya : jika proses memanggil enter_region-nya secara hampir bersamaan, yang disimpan di turn adalah data yang ditulis terakhir.

Contohnya :

# include “prototype.h”

# define FALSE 0

# define TRUE 1

# define N 2 /*banyaknya proses*/

int turn;

int interested [N]; /*nilai awal di-set = 0 (false)*/

void enter_region(int process) /*proses = 1 atau 0*/

{

int other; /*jumlah proses lainnya*/

other = 1 – process; /*proses lainnya*/

interested[process] = TRUE; /*menunjukkan tertarik*/

turn = process; /*set flag*/

while (turn==process && interested[other] == TRUE)

}

void leave_region(int process) /*proses yang selesai*/

{

interested[process] = FALSE; /*meninggalkan critical region*/

}

e. Test and Set Lock Instruction / Instruksi TSL

Dengan bantuan hardware, menentukan siapa yang berhak memasuki critical_region (section)

Contoh :

Enter_region :

Tsl reg,flag | copy flag ke reg dan set flag = 1

Cmp reg,#0 | apakah flag = 0

Jnz enter_region |jika <> 0 loop lagi

Ret |return ke caller, masuk critical region

Leave_region :

Mov flag, #0 |simpan 0 ke flag

Ret |return ke caller

Proses harus memanggil ini pada saat yang tepat.