PAPER MUTUAL EXCLUSION
Oleh : Yusuf Machsar
NRP : 100411100026
ABSTRAK
Mutual exclusion dapat mencegah
proses kongkurensi (concurrency) dikerjakan bersamaan oleh resource (sumber
daya). Sehingga dibutuhkan penanganan proses kongkurensi tersebut agar dapat
dikerjakan oleh resource. Metode penyelesaian masalah mutual exclusion ini
adalah mengatur proses yang akan memasuki critical section. Jika proses yang
sedang mengerjakan critical section, maka proses lain tidak boleh memasuki
critical section. Ada beberapa metode yang dapat meyelesaikan permasalahan ini.
Prinsip kerja antara satu metode dengan metode lainnya didalam mengatur
penanganan mutual exclusion adalah berbeda. Dalam bahasan ini akan membahas
bagaimana kinerja beberapa metode tersebut dalam menangani masalah mutual
exclusion jika terjadi proses kongkurensi.
PENDAHULUAN
Perkembangan sistem komputer mendatang adalah menuju ke sistem
multiprocessing, multip rogramming, terdistribus i dan paralel yang
mengharuskan adanya proses-proses yang berjalan bersama dalam waktu yang
bersamaan. Hal demikian merupakan masalah yang perlu perhatian dari perancang
sistem operasi. Kondisi dimana pada saat yang bersamaan terdapat lebih dari
satu proses disebut dengan kongkurensi (concurrency) atau proses-proses yang
kongkuren. Proses-proses yang mengalami kongkuren dapat berdiri sendiri
(independen) atau dapat saling berinteraksi, sehingga membutuhkan sinkronisasi
atau koordinasi proses yang baik. Untuk penanganan kongkuren, bahasa pemograman
saat ini telah memiliki mekanisme kongkurensi dimana dalam penerapannya perlu
dukungan sistem operasi dimana bahasa berada.
PEMBAHASAN
1.1 MUTUAL EXCLUSION
Merupakan kondisi dimana terdapat
sumber daya yang tidak dapat dipakai bersama pada waktu yang bersamaan
(misalnya : printer, disk drive). Kondisi demikian disebut sumber daya kritis,
dan bagian program yang menggunakan sumber daya kritis disebut critical region
/ section. Hanya satu program pada satu saat yang diijinkan masuk ke critical
region. Pemrogram tidak dapat bergantung pada sistem operasi untuk memahami dan
memaksakan batasan ini, karena maksud program tidak dapat 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.
Pentingnya mutual exclusion adalah jaminan hanya satu proses yang mengakses
sumber daya pada suatu interval waktu.
Pemaksaan atau pelanggaran mutual exclusion menimbulkan
:
Ø
Deadlock
Ø
Starvation
Critical Section
Segmen kode yang mengakses data yang digunakan secara
bersama-sama itu disebut critical section. Bagaimana menghindari race
conditions? Kunci untuk mencegah masalah ini da situasi yang lain yang
melibatkan shared memory, shared file, and shared sumber daya yang lain dalah
menemukan beberapa jalan untuk mencegah lebih dari satu proses untuk melakukan proses
writing dan reading kepada shared data pada saat yang sama. Dengan kata lain
kita membutuhkan mutual exclusion, sebuah jalan yang menjamin jika sebuah
proses sefang menggunakan shared files, proses lain dikeluarkan dari pekerjaan
yang sama. Kesulitan yang terjadi karena proses 2 menggunakan shared variabel
sebelum proses 1 menyelesaikan tugasnya.
Walaupun dapat mencegah race conditions, tapi tidak
cukup untuk melakukan kerjasama antar proses secara paralel dengan baik dan
efisien dalam menggunakan shared data. Kita butuh 4 kondisi untuk menghasilkan
solusi yang baik :
Ø
Tidak ada
dua proses secara bersamaan masuk kedalam critical section.
Ø
Tidak ada
asumsi mengenai kecepatan atau jumlah cpu.
Ø
Tidak ada
proses yang berjalan diluar critical section yang dapat mengeblok proses lain.
Ø
Tidak ada
proses yang menunggu selamanya untuk masuk critical section.
Tiga kondisi untuk menentukan mutual exclusion :
Ø
Tidak ada
dua proses yang pada saat bersamaan berada di critical section.
Ø
Tidak ada
proses yang berjalan diluar critical region yang bisa menghambat proses lain.
Ø
Tidak ada
proses yang tidak bisa masuk ke critical region.
Solusi masalah critical section
- Ide :
Ø
Mencakup
pemakaian secara “exclusive” dari shared variable tersebut
Ø
Menjamin
proses lain dapat menggunakan shared variable tersebut
- Solusi
“critical section problem” harus memenuhi:
Ø
Mutual Exclusion: Jika proses Pi sedang “eksekusi” pada bagian “critical section” (dari
proses Pi) maka tidak ada proses proses lain dapat “eksekusi” pada bagian
critical section dari proses-proses tersebut.
Ø
Progress: Jika tidak
ada proses sedang eksekusi pada critical section-nya dan jika terdapat lebih
dari satu proses lain yang ingin masuk ke critical section, maka pemilihan
siapa yang berhak masuk ke critical section tidak dapat ditunda tanpa terbatas.
- Bounded
Waiting:
Terdapat batasan berapa lama suatu proses harus menunggu giliran
untuk mengakses “critical section” – jika seandainya proses lain yang
diberikan hak akses ke critical section.
Ø
Menjamin
proses dapat mengakses ke “critical section” (tidak mengalami starvation:
proses se-olah berhenti menunggu request akses ke critical section
diperbolehkan).
Ø
Tidak ada
asumsi mengenai kecepatan eksekusi proses proses n tersebut.
1.2 Metode
Penyelesaian Masalah Mutual Exclusion.
Ada beberapa metode penyelesaian masalah mutual
exclusion, antara lain :
- a. 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:
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.
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<j, maka Pi lebih dahulu
masuk \critical section, sebaliknya Pj yang lebih dahulu masuk critical
section. skema penomoran selalu membangkitkan angka yang meningkat, seperti
1,2,3,4,5,6, …
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:
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.
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();
};
}
- b. 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();
};
}
1.3 Mencegah Mutual
Exclusion
Mutual
exclusion benar-benar tak dapat dihindari.
Hal ini dikarenakan tidak ada
sumber daya yang dapat digunakan
bersama-sama, jadi sistem harus membawa
sumber daya yang tidak dapat
digunakan bersama-sama.
DAFTAR
PUSTAKA
1. Hariyanto, Bambang. Sistem Operasi. Edisi 2.
Bandung. Informatika. 1999.
2. Kusumadewi, Sri. Sistem Operasi. Yogyakarta, J
& J Learning, 2000
3. Tenembaum, Andrew S., “Modern Operating System”,
Englewood Cliffs, New Jersey :
Prentice-Hall
Inc., 1992.
4. stalling, William, “Operating System”, 2nd
Englewood Cliffs, New Jersey : Prentice-Hall
Inc., 1995.
Postingan
