DEADLOCK dan PENANGANAN
Dalam sistem
komputer, terdapat banyak sumber daya yang hanya bisa dimanfaatkan oleh satu
proses pada suatu waktu. Contohnya adalah penggunaan sumber daya seperti printer,
tape drives dan CD-ROM drives. Dua buah proses yang menggunakan slot yang sama
pada tabel proses dapat menyebabkan kerusakan pada sistem. Untuk itu, setiap
sistem operasi memiliki mekanisme yang memberikan akses eksklusif pada sumber
daya. Pada kenyataannya, proses membutuhkan akses eksklusif untuk beberapa
sumber daya sekaligus. Bayangkan apabila sebuah proses, sebut saja proses A,
meminta sumber daya X dan mendapatkannya. Kemudian ada proses B yang meminta
sumber daya Y dan mendapatkannya juga. Setelah itu, proses A meminta sumber
daya Y dan proses B meminta sumber daya X. Pada situasi tersebut, kedua proses
harus ter-block dan menunggu secara terus-menerus. Keadaan seperti itu
dinamakan deadlock.
PENGERTIAN
Deadlock adalah
suatu kondisi dimana proses tidak berjalan lagi ataupun tidak ada komunikasi
lagi antarproses di dalam sistem operasi. Deadlock disebabkan karena proses
yang satu menunggu sumber daya yang sedang dipegang oleh proses lain yang
sedang menunggu sumber daya yang dipegang oleh proses tersebut. Dengan kata
lain setiap proses dalam set menunggu untuk sumber yang hanya dapat dikerjakan
oleh proses lain dalam set yang sedang menunggu. Jadi tidak ada satu pun proses
yang bisa running, melepaskan sumber daya, atau dibangunkan.
CONTOH DALAM
KEHIDUPAN
1.
DEADLOCK DI LALU LINTAS
JEMBATAN
Pada contoh di
atas, digambarkan ilustrasi dari kejadian deadlock pada dunia nyata, yaitu pada
lalu lintas di jembatan. Dapat dilihat bahwa kedua mobil yang berada di
tengah-tengah jembatan tidak dapat maju dan hanya menunggu. Penyelesaian dari
masalah tersebut adalah salah satu dari mobil tersebut mundur, sehingga mobil
yang lain dapat maju. Mobil pada kasus ini adalah proses, sedangkan jembatan
adalah sumber daya. Kedua mobil berebut untuk menggunakan sumber daya, namun
karena sumber daya tersebut hanya dapat digunakan oleh satu proses saja, maka
terjadilah deadlock. Kondisi tersebut bila terjadi dalam waktu yang lama dapat
menyebabkan terjadinya starvation
2.
DEADLOCK DI INTERSECTION
Gambar di atas
adalah contoh lain terjadinya deadlock pada dunia nyata. Pada gambar jelas
terlihat bahwa lalu lintas terhenti dan terjadi antrian pada empat arah
datangnya mobil. Tidak ada mobil yang bisa melanjutkan perjalanan dan hanya
menunggu saja. Permasalahan ini dapat dipecahkan dengan cara salah satu dari
antrian tersebut mundur dan memberikan kesempatan antrian lain untuk berjalan
terlebih dahulu. Kasus seperti ini sangat potensial untuk terjadinya
starvation. Berikut ini diberikan contoh situasi deadlock yang dideskripsikan
dengan pseudocode.
TestAndSet
Mutex M1, M2;
/* Thread 1 */
while (1)
{
NonCriticalSection()
Mutex_lock(&M1);
Mutex_lock(&M2);
CriticalSection();
Mutex_unlock(&M2);
Mutex_unlock(&M1);
}
/* Thread 2 */
while (1)
{
NonCriticalSection()
Mutex_lock(&M2);Mutex_lock(&M1);
CriticalSection();
Mutex_unlock(&M1);
Mutex_unlock(&M2);
}
Misalkan thread
1 berjalan dan mengunci M1. Akan tetapi sebelum ia dapat mengunci M2, ia
diinterupsi. Kemudian thread 2 mulai berjalan dan mengunci M2. Ketika ia mencoba
untuk mendapatkan dan mengunci M1, ia terblok karena M1 telah dikunci oleh
thread 1. Selanjutnya thread 1 berjalan lagi dan mencoba untuk mendapatkan dan mengunci
M2, namun terblok karena M2 telah dikunci oleh thread 2. Kedua thread terblok
dan saling menunggu terjadinya sesuatu yang tak pernah akan terjadi.
Kesimpulannya, terjadi deadlock yang melibatkan thread 1 dan thread 2.
CONTOH DI
KOMPUTER
hannel I/O,
disk, semaphore. Contoh peran sumber daya jenis ini pada terjadinya Deadlock
ialah misalnya sebuah proses memakai disk A dan B, maka akan terjadi Deadlock
jika setiap proses sudah memiliki salah satu disk dan meminta disk yang lain.
Masalah ini tidak hanya dirasakan oleh pemrogram tetapi oleh seorang yang
merancang sebuah sistem operasi. Cara yang digunakan pada umumnya dengan cara
memperhitungkan dahulu sumber daya yang digunakan oleh proses-proses yang akan
menggunakan sumber daya tersebut. Contoh lain yang menyebabkan Deadlock dari
sumber yang dapat dipakai berulang-ulang ialah berkaitan dengan jumlah proses
yang memakai memori utama. Ada empat kondisi yang dapat menyebabkan terjadinya
deadlock. Keempat kondisi tersebut tidak dapat berdiri sendiri, namun saling
mendukung.
MODELAN
SISTEM
Maksud dari
model sistem adalah pemodelan yang dibuat oleh sistem dalam mengatur permintaan
akan sumber daya oleh proses – proses yang sedang berjalan.
• Request.
Pada langkah ini, pertama kali proses mengajukan diri untuk bisa mendapatkan
sumber daya. Proses dapat meminta satu atau lebih sumber daya yang tersedia
ataupun yang sedang dimiliki oleh proses yang lain.
• Use.
Selanjutnya, setelah proses mendapatkan sumber daya yang dibutuhkannya, proses
akan melakukan eksekusi. Sumber daya digunakan oleh proses sampai proses
selesai melakukan eksekusi dan tidak membutuhkan lagumber daya tersebut.
• Release.
Setelah memanfaatkan sumber daya untuk melakukan eksekusi, proses pun akan
melepaskan sumber day yang dimilikinya. Sumber daya tersebut dibutuhkan oleh
proses lain yang mungkin sedang menunggu untuk menggunakan
KARAKTERISTIK
TERJADINYA DEADLOCK
·
Mutual Exclusion.
·
Hold and Wait.
Kondisi yang kedua adalah hold and wait yaitu beberapa proses saling menunggu sambil menahan sumber daya yang dimilikinya. Suatu proses yang memiliki minimal satu buah sumber daya melakukan request lagi terhadap sumber daya. Akan tetapi, sumber daya yang dimintanya sedang dimiliki oleh proses yang lain. Pada saat yang sama, kemungkinan adanya proses lain yang juga mengalami hal serupa dengan proses pertama cukup besar terjadi. Akibatnya, proses-proses tersebut hanya bisa saling menunggu sampai sumber daya yang dimintanya dilepaskan. Sambil menunggu, sumber daya yang telah dimilikinya pun tidak akan dilepas. Semua proses itu pada akhirnya saling menunggu dan menahan sumber daya miliknya.
·
No Preemption.
Kondisi yang selanjutnya adalah no
preemption yaitu sebuah sumber daya hanya dapat dilepaskan oleh proses yang
memilikinya secara sukarela setelah ia selesai menggunakannya. Proses yang
menginginkan sumber daya tersebut harus menunggu sampai sumber daya tersedia,
tanpa bisa merebutnya dari proses yang memilikinya.
·
Circular Wait.
Kondisi yang terakhir adalah circular
wait yaitu kondisi membentuk siklus yang berisi proses[1]proses
yang saling membutuhkan. Proses pertama membutuhkan sumber daya yang dimiliki
proses kedua, proses kedua membutuhkan sumber daya milik proses ketiga, dan
seterusnya sampai proses ke n-1 yang membutuhkan sumber daya milik proses ke n.
Terakhir, proses ke n membutuhkan sumber daya milik proses yang pertama. Yang
terjadi adalah proses-proses tersebut akan selamanya menunggu. Circular wait
oleh penulis diistilahkan sebagai 'Lingkaran Setan' tanpa ujung.
PENAGANAN
Mengabaikan Masalah Deadlock
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.
Kebanyakan sistem operasi yang ada mengadaptasi cara ini untuk menangani
keadaan deadlock. Cara penanganan dengan mengabaikan deadlock banyak dipilih
karena kasus deadlock tersebut jarang terjadi dan relatif rumit dan kompleks
untuk diselesaikan. Sehingga biasanya hanya diabaikan oleh sistem untuk
kemudian diselesaikan masalahnya oleh user dengan cara melakukan terminasi
dengan Ctrl+Alt+Del atau melakukan restart terhadap computer
Mencegah Terjadinya Deadlock
Penanganan ini dengan cara mencegah
terjadinya salah satu karakteristik deadlock. Penanganan ini dilaksanakan pada
saat deadlock belum terjadi pada sistem
1.
Mutual Exclusion
Cara yang dapa ditempuh untuk mengakali pengaksesan eksklusif adalah
spooling perangkat-perangkat yang harus didedikasikan ke suatu proses.
Pengaksesan sumber daya seolah-seolah tidak eksklusif walau sebenarnya tetap
eksklusif, hanya sekarang diantrikan di disk
2.
Hold and Wait
Mengalokasikan semua sumber daya atau tidak sama sekali Proses hanya
dilayani permintaannya bila semua sumber daya yang diperlukan tersedia. Proses
ini berbasis pada semua atau tidak sama sekali.
3.
No Preemption.
Pencegahan kondisi ini dengan cara membolehkan terjadinya
preemption. Maksudnya bila ada proses yang sedang memiliki sumber daya dan
ingin mendapatkan sumber daya tambahan, namun tidak bisa langsung dialokasikan,
maka akan preempted. Sumber daya yang dimiliki proses tadi akan diberikan pada
proses lain yang membutuhkan dan sedang menunggu.
4.
Circular Wait.
Kondisi 'lingkaran setan' ini dapat 'diputus' dengan jalan
menentukan total kebutuhan terhadap semua tipe sumber daya yang ada. Selain
itu, digunakan pula mekanisme enumerasi terhadap tipe-tipe sumber daya yang
ada. Setiap proses yang akan meminta sumber daya harus meminta sumber daya
dengan urutan yang menaik. Misalkan sumber daya printer memiliki nomor 1
sedangkan CD-ROM memiliki nomor 3. Proses boleh melakukan permintaan terhadap
printer dan kemudian CD-ROM, namun tidak boleh sebaliknya
Penghindaran Terjadinya Deadlock
Penghindaran terhadap deadlock adalah
cara penanganan yang selanjutnya. Inti dari penghindaran adalah jangan sampai
sistem berada dalam kondisi yang memungkinkan untuk terjadinya deadlock. Jadi,
Jika pemberian akses suatu resource tidak mungkin mengarah pada deadlock, maka
resource akan diberikan pada proses yang meminta, jika kemungkinan akan
mengarah ke deadlock maka proses yang meminta akan di-suspend sampai suatu
waktu permintaannya aman untuk diberikan. Langkah lain untuk menghindari adalah
dengan cara tiap proses memberitahu jumlah kebutuhan maksimum untuk setiap tipe
sumber daya yang ada
Algoritma penghindaran yang pertama
yaitu resource-allocation graph
01
work dan finish adalah vektor yang diinisialisasi:
work
= available
finish[i]
= FALSE untuk i= 1,2,3,..,n-1.
02
cari i yang memenuhi finish[i] == FALSE dan needi <= work
jika
tak ada, ke tahap 04
03
work = work + allocationi
finish
[i] = TRUE
kembali
ke tahap 02
04
jika finish[i]==TRUE untuk semua i, maka sistem safe state.
Untuk algoritma yang kedua yaitu
banker's algorithm
Request
= sumber daya yang dibutuhkan proses Pi. Pada request,
Pi
membutuhkan k instances dari Rj.
01
Jika Requesti <= Needi, ke tahap 02.
Selain
itu error karena melebihi maximum permintaan
02
Jika Requesti <= Available, ke tahap 03.
Selain
itu Pi harus menunggu karena tidak tersedia
03
Ubah kondisi state setelah request dikabulkan
Available
= Available - Requesti
Allocationi
= Allocationi + Requesti
Needi
= Needi - Requesti
if
safe => sumber daya dialokasikan pada Pi
if
unsafe => Pi menunggu, state kembali sebelumnya
Pendeteksian
Terhadap Deadlock
Mekanisme pendeteksian adalah dengan
menggunakan detection algorithm yang akan memberitahu sistem mengenai proses
mana saja yang terkena deadlock. Setelah diketahui proses mana saja yang
terlibat dalam deadlock, selanjutnya adalah dengan menjalankan mekanisme
pemulihan sistem yang akan dibahas pada bagian selanjutnya. Berikut ini adalah
algoritma pendeteksian deadlock
Pemuliah Deadlock
1.
Terminasi proses
Pemulihan sistem dapat dilakukan dengan cara melalukan terminasi
terhadap semua proses yang terlibat dalam deadlock. Dapat pula dilakukan
terminasi terhadap proses yang terlibat dalam deadlock secara satu per satu
sampai 'lingkaran setan' atau circular wait hilang. terdapat beberapa faktor
yang menentukan proses mana yang akan diterminasi. Faktor pertama adalah
prioritas dari proses-proses yang terlibat deadlock. Faktor kedua adalah berapa
lama waktu yang dibutuhkan untuk eksekusi dan waktu proses menunggu sumber
daya. Faktor ketiga adalah berapa banyak sumber daya yang telah dihabiskan dan
yang masih dibutuhkan. Terakhir, faktor utilitas dari proses pun menjadi
pertimbangan sistem untuk melakukan terminasi pada suatu proses.
2.
Rollback and Restart.
Dalam
memulihkan keadaan sistem yang deadlock, dapat dilakukan dengan cara sistem
melakukan preempt terhadap sebuah proses dan kembali ke state yang aman. Pada
keadaan safe state tersebut, proses masih berjalan dengan normal, sehingga
sistem dapat memulai proses dari posisi aman tersebut. Untuk menentukan pada
saat apa proses akan rollback, tentunya ada faktor yang menentukan. Diusahakan
untuk meminimalisasi kerugian yang timbul akibat memilih suatu proses menjadi
korban
Kesimpulan
Deadlock
adalah suatu keadaan dimana sistem seperti terhenti dikarenakan setiap proses
memiliki sumber daya yang tidak bisa dibagi dan menunggu untuk mendapatkan
sumber daya yang sedang dimiliki oleh proses lain.
Karakteristik terjadinya
deadlock:
• Mutual Exclusion
→ hanya satu proses dalam
satu waktu yang dapat memegang (hold) resource.
• Hold and Wait
→ suatu proses memegang
satu resource dan me-request resource yang lain.
• No Preemption
→ resource hanya dapat
di-release setelah proses menyelesaikan task-nya pada resource.
• Circular Wait
→ Masing-masing proses
menunggu resource yang digunakan oleh proses lain secara berantai.
→ Terdapat himpunan
proses yang sedang menunggu {P0, P1, …, P0} sedemikian sehingga P0 menunggu
resource yang dipegang
oleh P1 , P1 sedang menunggu resource yang dipegang oleh P2, …, Pn–1 . Pn–
menunggu resource yang
dipegang oleh Pn . Dan Pnmenunggu resource yang dipegang oleh P0 .
Mekanisme penanganan
deadlock:
• Pengabaian. Ostrich
Algorithm.
• Pencegahan. Mencegah
terjadinya salah satu kondisi deadlock.
• Penghindaran.
Memastikan sistem berada pada safe state dan dengan menggunakan deadlock
avoidance
algorithm.
• Pendeteksian dan
Pemulihan. Mekanisme pendeteksian menggunakan detection algorithm, sedangkan
pemulihan
dengan cara rollback and restart sistem ke
safe state.
https://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2006-2007/Makalah/Makalah0607-8.pdf
http://ftp.gunadarma.ac.id/linux/docs/v06/Kuliah/SistemOperasi/2008/240/23.pdf
https://student.blog.dinus.ac.id/ganiarianto/2016/11/30/deadlock-pada-sistem-operasi/
Comments
Post a Comment