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
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
Hariyanto, Bambang, Ir., Sistem Operasi, Penerbit Informatika, Bandung, 1999
