PENYELESAIN MASALAH MUTUAL EXCLUSION
DEADLOCK DAN STARVATION
LUKMAN ADE PUTRA TAMA
08.7540
SISTEM OPERASI
MENEJEMEN INFORMATIKA – MI
STIE MANDALA JEMBER
2011
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();
};
}
DEADLOCK DAN STARVATION
Kejadian deadlock yang berlangsung secara terus-menerus dan tiada akhir dapat menyebabkan terjadinya starvation. Akan tetapi, deadlock bukanlah satu-satunya penyebab terjadinya starvation. Starvation adalah keadaan dimana satu atau beberapa proses 'kelaparan' karena terus dan terus menunggu kebutuhan sumber dayanya dipenuhi. Namun, karena sumber daya tersebut tidak tersedia atau dialokasikan untuk proses lain, akhirnya proses yang membutuhkan tidak bisa memilikinya. Kondisi seperti ini merupakan akibat dari keadaan menunggu yang berkepanjangan. Contoh ilustrasi sederhana dari starvation adalah suatu client yang sedang berinteraksi dengan sebuah server dalam waktu yang lama mengakibatkan server tersebut tidak dapat melayani client yang lain.
MENCEGAH DEADLOCK
Metode ini berkaitan dengan pengkondisian sistem agar menghilangkan
kemungkinan terjadinya deadlock. Pencegahan merupakan solusi yang bersih
dipandang dari sudut tercegahnya deadlock. Metode ini sering menghasilkan utilisasi sumber daya yang buruk. Pencegahan deadlock merupakan metode yang banyak dipakai.
Untuk mencegah deadlock dilakukan dengan meniadakan salah satu dari syarat
perlu sebagai berikut :
• 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.
• Mencegah Hold and Wait
Untuk mencegah hold and wait, sistem harus menjamin bila suatu proses meminta sumber daya, maka proses tersebut tidak sedang memegang sumber daya yang lain.
Proses harus meminta dan dialokasikan semua sumber daya yang diperlukan
sebelum proses memulai eksekusi atau mengijinkan proses meminta sumber daya hanya jika proses tidak membawa sumber daya lain. Model ini mempunyai utilitas sumber daya yang rendah dan kemungkinan terjadi starvation jika proses
membutuhkan sumber daya yang popular sehingga terjadi keadaan menunggu yang tidak terbatas karena setidaknya satu dari sumber daya yang dibutuhkannya dialokasikan untuk proses yang lain.
• Mencegah Non Preemption
Peniadaan non preemption mencegah proses-proses lain harus menunggu. Seluruh proses menjadi preemption, sehingga tidak ada tunggu menunggu. Cara mencegah kondisi non preemption :
a. Jika suatu proses yang membawa beberapa sumber daya meminta sumber daya lain yang tidak dapat segera dipenuhi untuk dialokasikan pada proses tersebut, maka semua sumber daya yang sedang dibawa proses tersebut harus dibebaskan.
b. Proses yang sedang dalam keadaan menunggu, sumber daya yang dibawanya ditunda dan ditambahkan pada daftar sumber daya.
c. Proses akan di restart hanya jika dapat memperoleh sumber daya yang lama dan sumber daya baru yang diminta.
• Mencegah Kondisi Menunggu Sirkular
Sistem mempunyai total permintaan global untuk semua tipe sumber daya. Proses dapat meminta proses kapanpun menginginkan, tapi permintaan harus dibuat terurut secara numerik. Setiap proses yang membutuhkan sumber daya dan memintanya maka nomor urut akan dinaikkan. Cara ini tidak akan menimbulkan siklus.
Masalah yang timbul adalah tidak ada cara pengurutan nomor sumber daya yang
memuaskan semua pihak.
Penanganan DEADLOCK
Secara umum terdapat 4 cara untuk menangani keadaan deadlock, yaitu:
1. Pengabaian. Maksud dari pengabaian di sini adalah sistem mengabaikan terjadinya deadlock dan pura-pura tidak tahu kalau deadlock terjadi. Dalam penanganan dengan cara ini dikenal istilah ostrich algorithm. Pelaksanaan algoritma ini adalah sistem tidak mendeteksi adanya deadlock dan secara otomatis mematikan proses atau program yang mengalami deadlock.
2. Pencegahan. Penanganan ini dengan cara mencegah terjadinya salah satu karakteristik deadlock. Penanganan ini dilaksanakan pada saat deadlock belum terjadi pada sistem. Intinya memastikan agar sistem tidak akan pernah berada pada kondisi deadlock.
3. Penghindaran. Menghindari keadaan deadlock. Bagian yang perlu diperhatikan oleh pembaca adalah bahwa antara pencegahan dan penghindaran adalah dua hal yang berbeda. Pencegahan lebih kepada mencegah salah satu dari empat karakteristik deadlock terjadi, sehingga deadlock pun tidak terjadi. Sedangkan penghindaran adalah memprediksi apakah tindakan yang diambil sistem, dalam kaitannya dengan permintaan proses akan sumber daya, dapat mengakibatkan terjadi deadlock.
4. Pendeteksian dan Pemulihan. Pada sistem yang sedang berada pada kondisi deadlock, tindakan yang harus diambil adalah tindakan yang bersifat represif. Tindakan tersebut adalah dengan mendeteksi adanya deadlock, kemudian memulihkan kembali sistem. Proses pendeteksian akan menghasilkan informasi apakah sistem sedang deadlock atau tidak serta proses mana yang mengalami deadlock.
PERBAIKAN DARI DEADLOCK
Terdapat dua pilihan untuk membebaskan deadlock. Satu solusi sederhana
adalah dengan menghentikan satu atau beberapa proses untuk membebaskan kondisi menunggu sirkular. Pilihan kedua adalah menunda beberapa sumber daya dari satu atau lebih proses yang deadlock.
Terminasi Proses
Untuk memperbaiki deadlock dengan terminasi proses, dapat diguankan salah
satu dari dua metode di bawah ini :
• Menghentikan (abort) semua proses yang deadlock
• Menghentikan satu proses setiap waktu sampai siklus deadlock hilang.
Untuk menentukan urutan proses yang harus dihentikan ada beberapa faktor yang harus diperhatikan :
• Prioritas proses.
• Berapa lama proses dijalankan dan berapa lama lagi selesai.
• Sumber daya yang digunakan proses.
• Sumber daya proses yang diperlukan untuk menyelesaikan task.
• Berapa proses yang perlu diterminasi.
• Apakah proses interaktif atau batch.
Menunda Sumber Daya
Untuk menghilangkan deadlock dengan menunda sumber daya, sumber daya
dari proses harus ditunda dan memberikan sumber daya tersebut ke proses lain sampai siklus deadlock hilang.
Jika penundaan dibutuhkan untuk menghilangkan deadlock, terdapat tiga hal
yang perlu diperhatikan :
• Pilihlah korban (sumber daya) yang mempunyai biaya minimal.
• Lakukan rollback yaitu memulai kembali (restart) proses pada state yang selamat.
• Harus dijamin starvation tidak akan terjadi karena kemungkinan beberapa proses selalu terpilih sebagai korban termasuk jumlah rollback sebagai faktor biaya.
Tidak ada komentar:
Posting Komentar