MODEL & METODE DEADLOCK

Nama : M Bagus Munandar

NIM : 110010586

Kelas : PE111

SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN

TEKNIK KOMPUTER

STIKOM BALI

2012

Kata Pengantar

Segala rahmat dan puji syukur kami panjatkan kepada Tuhan Yang Maha Esa

karena atas berkah dan petunjuk-Nya saya dapat menyelesaikan tugas makalah ini.

Tugas makalah ini dibuat agar mahasiswa dapat mengerti tentang model &

metode mengatasi deadlock. Cara penyampaian makalah ini cukup menarik, sehingga saya

termotivasi untuk mengembangkan pemahaman isi dari tugas ini.

Dalam pembuatan makalah ini, tidak sedikit kesulitan yang saya hadapi. Namun

saya menyadari bahwa kelancaran dalam penyusunan makalah ini, tidak lain berkat bantuan,

dukungan dan bimbingan dosen, sehingga kesulitan yang saya hadapi dapat teratasi. Oleh

karena itu, kami mengucapkan terima kasih kepada :

1. Dosen pembimbing yang telah memberikan tugas dan petunjuk kepada saya,

sehingga kami dapat menyelesaikan tugas ini.

2. Teman-teman mahasiswa kelas PE111

3. Partisipan

Semoga materi ini dapat bermanfaat dan menjadi sumbangan pemikiran bagi pihak

yang membutuhkan, khususnya bagi penulis, sehingga tujuan yang diharapkan dapat

terpenuhi.

Denpasar, Oktober 2012

Penulis

ii

DAFTAR ISI

Halaman Judul .............................................................................................................. i

Kata Pengantar .............................................................................................................. ii

Daftar Isi ....................................................................................................................... iii

BAB I PENDAHULUAN ......................................................................................... 1

1.1 Latar Belakang ........................................................................................ 1

1.2 Rumusan Masalah ................................................................................... 1

BAB II PEMBAHASAN ............................................................................................ 2

2.1 Deadlock ................................................................................................ 2

2.2 Model Deadlock ..................................................................................... 3

2.3 Metode Mengatasi Deadlock ............................................................... 5

2.4 Contoh Permasalahan ............................................................................. 10

Daftar Pustaka ................................................................................................................ 11

iii

BAB I

PENDAHULUAN

1.1 Latar Belakang

Pada sebuah sistem komputer dimana terdapat beberapa proses yang berjalan secara

konkuren, seringkali terjadi persaingan dalam memperebutkan sumber daya yang digunakan

sehingga dapat menyebabkan seluruh proses yang terlibat tidak dapat melanjutkan

eksekusinya, kondisi ini disebut dengan deadlock.

Deadlock yaitu kondisi dimana dua proses atau lebih tidak dapat menenuruskan

eksekusinya karena saling menunggu aksi ataupun sumber daya digunakan oleh proses

lainnya. Contoh sederhana adalah terjadinya kemacetan lalu lintas.

1.2 Rumusan Masalah

1. Deadlock

2. Model Deadlock

3. Metode Mengatasi Deadlock

4. Contoh Permasalahan

1

BAB II

PEMBAHASAN

2.1 Deadlock

Misalkan pada suatu komputer terdapat dua buah program, sebuah tape drive dan

sebuah printer. Program A mengontrol tape drive, sementara program B mengontrol printer.

Setelah beberapa saat, program A meminta printer, tapi printer masih digunakan. Berikutnya,

B meminta tape drive, sedangkan A masih mengontrol tape drive.

Dua program tersebut memegang kontrol terhadap sumber daya yang dibutuhkan oleh

program yang lain. Tidak ada yang dapat melanjutkan proses masing-masing sampai program

yang lain memberikan sumber dayanya, tetapi tidak ada yang mengalah.

Deadlock yang mungkin dapat terjadi pada suatu proses disebabkan proses itu menunggu

suatu kejadian tertentu yang tidak akan pernah terjadi. Dua atau lebih proses dikatakan berada

dalam kondisi deadlock, bila setiap proses yang ada menunggu suatu kejadian yang hanya

dapat dilakukan oleh proses lain dalam himpunan tersebut.

Terdapat kaitan antara overhead dari mekanisme koreksi dan manfaat dari koreksi deadlock

itu sendiri. Pada beberapa kasus, overhead atau ongkos yang harus dibayar untuk membuat

sistem bebas deadlock menjadi hal yang terlalu mahal dibandingkan jika mengabaikannya.

Sementara pada kasus lain, seperti pada real-time process control, mengizinkan deadlock

akan membuat sistem menjadi kacau dan membuat sistem tersebut tidak berguna.

Contoh berikut ini terjadi pada sebuah persimpangan jalan. Beberapa hal yang dapat membuat

deadlock pada suatu persimpangan, yaitu:

Terdapat satu jalur pada jalan.

Mobil digambarkan sebagai proses yang sedang menuju sumber daya.

Untuk mengatasinya beberapa mobil harus preempt (mundur).

Sangat memungkinkan untuk terjadinya starvation (kondisi proses tak akan

mendapatkan sumber daya).

2

2.2 Model Deadlock

Urutan kejadian pengoperasian perangkat I/O adalah :

1) meminta / request : meminta palayanan I/O

2) memakai / use : memakai perangkat I/O

3) melepaskan / release : melepaskan pamakaian perangkat I/O

Model deadlock dua proses dan dua sumber daya

Deadlock dapat digambarkan sebagai graph.

Misalnya :

- dua proses, P0 dan P1

- dua sumber daya kritis, R0 dan R1

- proses P0 dan P1 harus mengakses kedua sumber daya tersebut

kondisi berikut dapat terjadi :

- R0 diberikan ke P0 (P0 meminta sumber daya R0), ditandai busur (edge) berarah dari proses

P0 ke sumber daya R0

- sedangkan sumber daya R1 dialokasikan ke P1, ditandai dengan busur (edge) berarah dari

sumber daya R1 ke proses P1.

P0

R0 P1

R1

Skenario yang menimbulkan deadlock

Dapat terjadi skenario sebagai berikut :

- P0 dialokasikan R0

- P1 dialokasikan R1

Kemudian,

- P0 sambil masih menggenggam R0, meminta R1

- P1 sambil masih menggenggam R1, meminta R0

Kejadian ini mengakibatkan deadlock karena sama-sama akan saling menunggu. Graph

deadlock ini akan digambarkan sebagai graph melingkar. Terjadinya deadlock ditandai

munculnya / terjadinya graph melingkar.

Karena untuk melanjutkan eksekusi memerlukan kedua sumber daya sekaligus, maka kedua

proses akan saling menunggu sumber daya lain selamanya. Tak ada proses yang dapat

melepaskan sumber daya yang telah dipegangnya karena menunggu sumber daya lain yang

tak pernah diperolehnya. Kedua proses dalam kondisi deadlock, tidak dapat membuat

kemajuan apapun.

Deadlock tidak hanya terjadi pada dua proses dan dua sumber daya, deadlock dapat terjadi

dengan melibatkan lebih dari dua proses dan dua sumber daya.

P0

R0 P1

R1

P0

R0

P1

R1

3

Syarat-syarat terjadinya deadlock :

1. Mutual exclution condition

Tiap sumber daya saat itu diberikan pada tepat satu proses.

2. Hold and wait condition / kondisi genggam dan tunggu

Proses-proses yang sedang menggenggam sumber daya, menunggu sumber daya – sumber

daya yang baru.

3. Non-preemption condition / kondisi non-preemption

Sumber daya – sumber daya yang sebelumnya diberikan tidak dapat diambil paksa dari

proses itu. Sumber daya – sumber daya harus secara eksplisit dilepaskan dari proses yang

menggenggamnya.

4. Circular wait condition / kondisi menunggu secara sirkular

Harus terdapat rantai sirkuler dari dua proses atau lebih, masing-masing menunggu

sumber daya yang digenggam oleh anggota berikutnya pada rantai itu.

Ketiga syarat pertama merupakan syarat perlu bagi terjadinya deadlock. Keberadaan

deadlock selalu berarti terpenuhi kondisi-kondisi diatas, tidak mungkin terjadi deadlock bila

tidak ada ketiga kondisi itu. Deadlock terjadi berarti terdapat ketiga kondisi itu, tetapi adanya

ketiga kondisi itu belum berarti terjadi deadlock.

Deadlock baru benar-benar terjadi bila syarat keempat terpenuhi. Kondisi keempat merupakan

keharusan bagi terjadinya peristiwa deadlock. Bila salah satu dari kondisi tidak terpenuhi

maka deadlock tidak terjadi.

2.3 Metode Mengatasi deadlock

Ada 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

4

5

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 komputer.

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. Akan

dibahas secara lebih mendalam pada bagian selanjutnya.

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. Akan dibahas secara lebih

mendalam pada bagian selanjutnya.

4. Pendeteksian & 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. Akan dibahas secara lebih mendalam pada bagian

selanjutnya.

Pencegahan Deadlock

Pencegahan deadlock dapat dilakukan dengan cara mencegah salah satu dari empat

karakteristik terjadinya deadlock. Empat karakteristik itu adalah :

1. Mutual Exclusion

Kondisi mutual exclusion pada sumber daya adalah sesuatu yang wajar terjadi, yaitu

pada sumber daya yang tidak dapat dibagi (non-sharable). Sedangkan pada sumber

daya yang bisa dibagi tidak ada istilah mutual exclusive. Jadi, pencegahan kondisi

pertama ini sulit karena memang sifat dasar dari sumber daya yang tidak dapat dibagi.

2. Hold and Wait

Untuk kondisi yang kedua, sistem perlu memastikan bahwa setiap kali proses meminta

sumber daya, ia tidak sedang memiliki sumber daya lain. Atau bisa dengan proses

meminta dan mendapatkan sumber daya yang dimilikinya sebelum melakukan

eksekusi, sehingga tidak perlu menunggu.

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. Proses akan mengulang kembali eksekusi

setelah mendapatkan semua sumber daya yang dibutuhkannya, termasuk sumber daya

yang dimintanya terakhir.

4. Circular Wait

Kondisi 'lingkaran setan' ini dapat 'diputus' dengan cara 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 Deadlock

Penghindaran terhadap deadlock adalah cara penanganan yang selanjutnya. Inti dari

penghindaran adalah jangan sembarangan membolehkan proses untuk memulai atau meminta

lagi. Maksudnya jangan pernah memulai suatu proses apabila nantinya akan menuju ke

keadaan deadlock.

6

Kedua, jangan memberikan kesempatan pada proses untuk meminta sumber daya

tambahan jika penambahan tersebut akan membawa sistem pada keadaan deadlock. Tidak

mungkin akan terjadi deadlock apabila sebelum terjadi sudah kita hindari. Langkah lain untuk

menghindari adalah dengan cara tiap proses memberitahu jumlah kebutuhan maksimum untuk

setiap tipe sumber daya yang ada. Selanjutnya terdapat deadlock-avoidance algorithm yang

secara rutin memeriksa state dari sistem untuk memastikan tidak adanya kondisi circular wait

serta sistem berada pada kondisi safe state.

Safe state adalah suatu kondisi dimana semua proses mendapatkan sumber daya yang

dimintanya dengan sumber daya yang tersedia. Apabila tidak bisa langsung, ia harus

menunggu selama waktu tertentu, kemudian mendapatkan sumber daya yang diinginkan,

melakukan eksekusi, dan terakhir melepas kembali sumber daya tersebut. Terdapat dua jenis

algoritma penghindaran yaitu resource-allocation graph untuk single instances resources

serta banker's algorithm untuk multiple instances resources.

Dalam banker's algorithm, terdapat beberapa struktur data yang digunakan, yaitu:

- Available = Jumlah sumber daya yang tersedia.

- Max = Jumlah sumber daya maksimum yang diminta oleh tiap proses.

- Allocation = Jumlah sumber daya yang sedang dimiliki oleh tiap proses.

- Need = Sisa sumber daya yang masih dibutuhkan proses, didapat dari max-allocation.

- Safety algorithm = untuk menentukan apakah sistem berada pada safe state atau tidak.

Pendeteksian Deadlock

Pada dasarnya kejadian deadlock sangatlah jarang terjadi. Apabila kondisi tersebut

terjadi, masing-masing sistem operasi mempunyai mekanisme penanganan yang berbeda. Ada

sistem operasi yang ketika terdapat kondisi deadlock dapat langsung mendeteksinya. Namun,

ada pula sistem operasi yang bahkan tidak menyadari kalau dirinya sedang mengalami

deadlock. Untuk sistem operasi yang dapat mendeteksinya, digunakan algoritma pendeteksi.

Secara lebih mendalam, pendeteksian kondisi deadlock adalah cara penanganan

deadlock yang dilaksanakan apabila sistem telah berada pada kondisi deadlock. Sistem akan

mendeteksi proses mana saja yang terlibat dalam kondisi deadlock. Setelah diketahui proses

mana saja yang mengalami kondisi deadlock, maka diadakan mekanisme untuk memulihkan

sistem dan menjadikan sistem berjalan kembali dengan normal.

Mekanisme pendeteksian adalah dengan menggunakan detection algorithm yang akan

memberitahu sistem tentang proses mana saja yang terkena deadlock. Setelah diketahui proses

7

8

mana saja yang terlibat dalam deadlock.

Pemulihan Deadlock

Pemulihan kondisi sistem terkait dengan pendeteksian terhadap deadlock. Apabila

menurut algoritma pendeteksian deadlock sistem berada pada keadaan deadlock, maka harus

segera dilakukan mekanisme pemulihan sistem. Berbahaya apabila sistem tidak segera

dipulihkan dari deadlock, karena sistem dapat mengalami penurunan performance dan

akhirnya terhenti. Cara-cara yang ditempuh untuk memulihkan sistem dari deadlock adalah

sebagai berikut:

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. Seperti diketahui bahwa circular wait adalah salah satu karakteristik

terjadinya deadlock dan merupakan kesatuan dengan tiga karakteristik yang lain.

Untuk itu, dengan menghilangkan kondisi circular wait dapat memulihkan sistem dari

deadlock. Dalam melakukan terminasi terhadap proses yang deadlock, 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.

Harus pula dihindari keadaan dimana proses yang sama selalu menjadi korban,

sehingga proses tersebut tidak akan pernah sukses menjalankan eksekusi.

2.4 Contoh Permasalahan

Beberapa kasus deadlock pada sistem oprasi & cara mengatasinya :

Pada windows NT, deteksi deadlock yaitu berupa BSOD (Blue Screen Of Death),

recoverynya adalah reboot sederhana.

Pada linux untuk mengetahui apakah terjadi deadlock yaitu dengan menggunakan

xosview untuk mengetahui proses yang menggunakan CPU 100%, lalu kill saja proses

tersebut.

9

DAFTAR PUSTAKA

o http://bayuzu.blogspot.com/2010/04/deadlock-deadlock-adalah-keadaan-dimana.html

o http://mohiqbal.staff.gunadarma.ac.id/Downloads/files/5349/BAB6+-+Deadlock.doc

o http://ikc.dinus.ac.id/umum/ibam/ibam-os-html/i32.html

o http://kur2003.if.itb.ac.id/file/ Deadlock .ppt

9

10

11