MUTUAL EXCLUSION

MUTUAL EXCLUSION

Pengertian

Merupakan kondisi dimana terdapat sumber daya yang tidak dapat dipakai bersama pada waktu yang bersamaan (misalnya : printer, disk drive) maka terdapat jaminan hanya satu proses yang mengakses sumber daya pada satu interval tertentu.

Syarat penting solusi penjaminan mutual-exclusion adalah :

·      Bebas dari deadlock

·      Bebas dari startvation

·      Fairness

·      Fault-tolerance

Pendekatan penjaminan mutual-exclusion tersebar :

1.    Algoritma terpusat

§   Satu proses merupakan koordinator

§   Waktu proses-proses lain ingin masuk critical region proses mengirim pesan ke koordinator memberitahu critical region yang ingin dimasukinya dan meminta ijin.

§   Jika tidak ada proses lain di critical region  koordinator mengirim balik jawaban pemberian ijin

§   Ketika ijin tiba, proses yang meminta segera memasuki critical region

§   Jika da proses lain di critical region  koordinaror menolak ijin

2.    Klasifikasi algoritma tersebar :

§   Nontoken-bassed algorithms

§   Token based algorithms

1.    Nontoken-based algorithm

§   Lamport’s algorithm

§   Richart-agrawala algorithm

§   Maekawa algorithm

2.    Beberapa pendekatan token based algorithm:

§   Token-ring algorirthm

§   Suzuki-kasami’s broadcast algorirthm

§   Singhal’s heuristic algorirthm

§   Raymond’s tree-based algorirthm

Metode-metode dan Algoritma untuk Menjamin Mutual Exclusion

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.





Hariyanto, Bambang, Ir., Sistem Operasi, Penerbit Informatika, Bandung, 1999