DEADLOCK

Oleh:

I Kadek Adi Permana

110010467

PE III

SEKOLAH TINGGI MANAJEMEN INFORMATIKA

DAN TEKNIK KOMPUTER (STMIK) STIKOM BALI

2013

KATA PENGANTAR

“Om swastyastu”

Puji syukur penulis panjatkan kehadapan Ida Sang Hyang Widhi Wasa,

atas berkat rahmat-Nya lah penulis dapat menyelesaikan tugas pembuatan laporan

mengenai “Sistem Operasi: Deadlock” dengan baik dan tepat waktu.

Penulis menyadari bahwa laporan ini masih banyak memiliki kekurangan

atau ketidak lengkapan isi dari pada laporan ini, oleh sebab itu kritik dan saran

yang mengarah pada perbaikan sangat diharapkan untuk kebaikan dan

kesempurnaan laporan ini. Semoga laporan ini dapat memberi pengetahuan

tambahan bagi pembaca. Akhir kata saya ucapkan terima kasih.

“Om Shanti, Shanti, Shanti, Om”

Denpasar, January 2013

Penulis

Deadlock Page i

DAFTAR ISI

KATA PENGANTAR..............................................................................................i

DAFTAR ISI............................................................................................................ii

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

PENDAHULUAN...................................................................................................1

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

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

1.3 Tujuan Penulisan.......................................................................................2

1.4 Manfaat Penulisan.....................................................................................2

BAB II......................................................................................................................3

PEMBAHASAN......................................................................................................3

2.1 Definisi Deadlock......................................................................................3

2.2 Model Sistem.............................................................................................3

2.3 Resource....................................................................................................4

2.4 Penyebab Deadlock...................................................................................6

2.5 Penanganan Deadlock...............................................................................7

2.5.1 Mengabaikan Masalah Deadlock.......................................................8

2.5.2 Mendeteksi dan Memperbaiki............................................................8

2.5.3 Penghindaran......................................................................................9

2.5.4 Pencegahan.......................................................................................10

BAB III..................................................................................................................13

PENUTUP..............................................................................................................13

3.1 Kesimpulan..............................................................................................13

3.2 Saran........................................................................................................13

Deadlock Page ii

BAB I

PENDAHULUAN

1.1 Latar Belakang

Dalam perkembangan dunia ilmu pengetahuan dan teknologi saat ini,

terkadang sangatlah sulit untuk menyelesaikan suatu permasalahan yang timbul

dengan menggunakan konsep konsep yang sudah ada. Untuk itu graph merupakan

salah satu bagian ilmu matematika yang dapat digunakan untuk mencari solusi

yang diharapkan.

Saat ini pemakaian teori graph semakin luas sesuai dengan tuntutan yang

senantiasa terus bertambah. Teori graph merupakan topik yang banyak mendapat

perhatian, karena model modelnya sangat berguna untuk aplikasi yang luas,

seperti masalah dalam jaringan komunikasi, transportasi, dan ilmu komputer.

Salah satu aplikasi graph pada sistem operasi adalah graph alokasi sumber

daya yang digunakan untuk melakukan pendeteksian dan pencegahan deadlock.

Deadlock dalam arti sebenarnya adalah kebuntuan. Kebuntuan yang dimaksud

dalam sistem operasi adalah kebuntuan proses. Jadi Deadlock ialah suatu kondisi

dimana proses tidak berjalan lagi atau pun tidak ada komunikasi lagi antar proses.

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.

1.2 Rumusan Masalah

Masalah dalam penulisan ini adalah bagaimana menyelesaikan

permsalahan dalam mendeteksi deadlock pada sistem operasi dan pencegahannya

dengan algoritma pencegahan dan pemulihan.

Deadlock Page 1

1.3 Tujuan Penulisan

Adapun tujuan penulisan ini adalah untuk mendeteksi dan mencegah

deadlock pada sistem operasi beserta contoh dan penanganannya.

1.4 Manfaat Penulisan

Manfaat penulisan ini untuk pembaca adalah agar bisa menambah

wawasannya, dan bagi penulis bisa menjadi pegangan referensi untuk artikel-

artikel selanjutnya.

Deadlock Page 2

BAB II

PEMBAHASAN

2.1 Definisi Deadlock

Deadlock adalah suatu kondisi dimana dua proses atau lebih saling

menunggu proses yang lain untuk melepaskan resource yang sedang dipakai.

Karena beberapa proses itu saling menunggu, maka tidak terjadi kemajuan dalam

kerja proses-proses tersebut. Deadlock dalam arti sebenarnya adalah kebuntuan.

Kebuntuan yang dimaksud dalam sistem operasi adalah kebuntuan proses.

Deadlock adalah masalah yang biasa terjadi ketika banyak proses yang membagi

sebuah resource yang hanya boleh dirubah oleh satu proses saja dalam satu waktu.

Jadi deadlock ialah suatu kondisi dimana proses tidak berjalan lagi atau pun tidak

ada komunikasi lagi antar proses. Salah satu contoh sebuah deadlock:

a. Proses A menggunakan CD-ROM.

b. Proses B menggunakan Scanner.

c. Proses A meminta Scanner (tanpa melepas CD-ROM) → menunggu.

d. Proses B meminta CD-ROM (tanpa melepas Scanner) → menunggu.

e. Menunggu… menunggu… DEADLOCK.

2.2 Model Sistem

Untuk memodelkan kondisi deadlock, maka bayangkan sebuah sistem

dengan:

a. Sekumpulan proses, P = {P1, P2, ..., Pn}

b. Sekumpulan tipe sumber daya yang berbeda, R = {R1, R2, ..., Rm}

c. Sumber daya Ri memiliki n bagian (instans) yang identik dan masing-

masing digunakan.

Pada model operasi normal, sebuah proses menggunakan sumber daya

dengan urutan sebagai berikut:

Deadlock Page 3

a. Mengajukan permohonan (request)

Bila permohonan tidak dapat dikabulkan dengan segera (misal

karena sumber daya sedang digunakan proses lain), maka proses itu

harus menunggu sampai sumber daya yang dimintanya tersedia.

b. Menggunakan sumber daya (use)

Proses dapat menggunakan sumber daya, misalnya printer untuk

mencetak, disk drive untuk melakukan operasi I/O, dan sebagainya.

c. Melepaskan sumber daya (relase)

Setelah proses menyelesaikan penggunaan sumber daya, maka

sumber daya harus dilepaskan sehingga dapat digunakan oleh proses

lain.

2.3 Resource

Deadlock bisa terjadi pada saat proses akan mengakses obyek secara tidak

semestinya. Obyek tersebut dinamakan sumber daya. Sumber daya ada dua jenis,

yaitu:

a. Preemptable

Sumber daya dikatakan preemptable jika sumber daya tersebut

dapat diambil (dilepas) dari proses yang sedang memakainya tanpa

member efek apapun pada proses tersebut. Sumber daya ini tidak habis

dipakai oleh proses mana pun. Tetapi setelah proses berakhir, sumber

daya ini dikembalikan untuk dipakai oleh proses lain yang sebelumnya

tidak kebagian sumber daya ini. Contohnya prosesor, kanal M/K, disk,

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

Deadlock Page 4

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. Contohnya dapat

dilihat dari kode berikut ini:

Setelah proses P dan Q telah melakukan fungsi meminta untuk

pertama kali, maka sumber daya yang tersedia dalam banyak ialah 50

(200-70-80). Maka saat P menjalankan fungsi meminta lagi sebanyak

60, maka P tidak akan menemukan sumber daya dari banyak sebanyak

60, maka P akan menunggu hingga sumber daya yang diminta dipenuhi.

Demikian juga dengan Q, akan menunggu hingga permintaannya

dipenuhi, akhirnya terjadi deadlock. Cara mengatasinya dengan

menggunakan memori maya.

Deadlock Page 5

//dari kelas proses kita tambahkan method yaitu memintapublic void meminta (int banyakA){

//meminta dari sumber daya aif ( banyakA < banyak )banyak = banyak - banyakA;elsewait();

}

//mengubah kode pada mainnya sebagai berikutpublic static void main ( String [] args ){

Proses P = new Proses();Proses Q = new Proses();P.meminta(80);Q.meminta(70);P.meminta(60);Q.meminta(80);

}

private int banyak = 200;private int banyakA;

b. Non-preemtable

Pada sumber daya jenis ini, sumber daya tidak dapat diambil dari

proses yang sedang membawanya karena akan menimbulkan kegagalan

komputasi. Printer adalah salah satu contohnya. Jika suatu proses

sedang menggunakan printer untuk mencetak sesuatu, maka printer

tersebut tidak dapat diambil untuk mencetak sesuatu dari proses lain.

Sumber daya jenis ini biasanya berpotensi terjadinya deadlock.

Contohnya seperti berikut:

Dari kedua fungsi tersebut ada yang bertindak untuk menerima dan

memberi sumber daya, tetapi ada kalanya proses tidak mendapat

sumber daya yang dibuat sehingga terjadi blok, karena itu terjadi

deadlock. Tentu saja hal ini sangat jarang terjadi mengingat tidak ada

batasan untuk memproduksi dan mengkonsumsi, tetapi ada suatu

keadaan seperti ini yang mengakibatkan deadlock. Hal ini

mengakibatkan deadlock jenis ini sulit untuk dideteksi. Selain itu

deadlock ini dihasilkan oleh beberapa kombinasi yang sangat jarang

terjadi.

2.4 Penyebab Deadlock

Setelah kita melihat beberapa illustrasi di atas, mungkin kita sekarang

mulai bisa membayangkan apa itu deadlock. Sebenarnya deadlock itu akan terjadi

apabila syarat-syarat dari deadlock tersebut terpenuhi. Adapun 4 kondisi penyebab

deadlock adalah sebagai berikut:

Deadlock Page 6

//menambahkan method receive dan sendpublic void receive( Proses p ){

//method untuk menerima sumber daya}

public void send ( Proses p ){//method untuk memberi sumber daya}

a. Mutual Exclusion

Hanya ada satu proses yang boleh memakai sumber daya, dan

proses lain yang ingin memakai sumber daya tersebut harus menunggu

hingga sumber daya tadi dilepaskan atau tidak ada proses yang

memakai sumber daya tersebut.

b. Hold and Wait

Proses yang sedang memakai sumber daya boleh meminta sumber

daya lagi maksudnya menunggu hingga benar-benar sumber daya yang

diminta tidak dipakai oleh proses lain, hal ini dapat menyebabkan

kelaparan sumber daya sebab dapat saja sebuah proses tidak mendapat

sumber daya dalam waktu yang lama.

c. No Preemption

Sumber daya yang ada pada sebuah proses tidak boleh diambil

begitu saja oleh proses lainnya. Untuk mendapatkan sumber daya

tersebut, maka harus dilepaskan terlebih dahulu oleh proses yang

memegangnya, selain itu seluruh proses menunggu dan

mempersilahkan hanya proses yang memiliki sumber daya yang boleh

berjalan.

d. Circular Wait

Kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber

daya yang dipegang proses berikutnya.

2.5 Penanganan Deadlock

Terdapat beberapa cara dalam menangani deadlock, yang secara umumnya

ada 4 cara untuk menanganinya, yaitu:

a. Mengabaikan masalah.

b. Mendeteksi dan memperbaiki.

c. Penghindaran.

d. Pencegahan.

Deadlock Page 7

2.5.1 Mengabaikan Masalah Deadlock

Untuk memastikan sistem tidak memasuki deadlock, sistem

dapat menggunakan pencegahan deadlock atau penghindaran

deadlock. Penghindaran deadlock membutuhkan informasi tentang

sumber daya yang mana yang akan suatu proses meminta dan

berapa lama akan digunakan. Dengan informasi tersebut dapat

diputuskan apakah suatu proses harus menunggu atau tidak. Hal ini

disebabkan oleh keberadaan sumber daya, apakah ia sedang

digunakan oleh proses lain atau tidak.

Metode ini lebih dikenal dengan Algoritma Ostrich. Dalam

algoritma ini dikatakan bahwa untuk menghadapi Deadlock ialah

dengan berpura-pura bahwa tidak ada masalah apa pun. Hal ini

seakan-akan melakukan suatu hal yang fatal, tetapi sistem operasi

Unix menanggulangi Deadlock dengan cara ini dengan tidak

mendeteksi Deadlock dan membiarkannya secara otomatis

mematikan program sehingga seakan-akan tidak terjadi apa pun.

Jadi jika terjadi Deadlock, maka tabel akan penuh, sehingga proses

yang menjalankan proses melalui operator harus menunggu pada

waktu tertentu dan mencoba lagi.

2.5.2 Mendeteksi dan Memperbaiki

Caranya ialah dengan cara mendeteksi jika terjadi Deadlock

pada suatu proses maka dideteksi sistem mana yang terlibat di

dalamnya. Setelah diketahui sistem mana saja yang terlibat maka

diadakan proses untuk memperbaiki dan menjadikan sistem

berjalan kembali. Jika sebuah sistem tidak memastikan deadlock

akan terjadi, dan juga tidak didukung dengan pendeteksian

deadlock serta pencegahannya, maka kita akan sampai pada kondisi

deadlock yang dapat berpengaruh terhadap performance sistem

karena sumber daya tidak dapat digunakan oleh proses sehingga

proses-proses yang lain juga terganggu. Akhirnya sistem akan

berhenti dan harus direstart.

Deadlock Page 8

Hal-hal yang terjadi dalam mendeteksi adanya Deadlock

adalah:

a. Permintaan sumber daya dikabulkan selama memungkin-

kan.

b. Sistem operasi memeriksa adakah kondisi circular wait

secara periodik.

c. Pemeriksaan adanya Deadlock dapat dilakukan setiap ada

sumber daya yang hendak digunakan oleh sebuah proses.

d. Memeriksa dengan algoritma tertentu.

2.5.3 Penghindaran

Pendekatan metode ini adalah dengan hanya memberi

kesempatan ke permintaan sumber daya yang tidak mungkin akan

menyebabkan deadlock. Metode ini memeriksa dampak pemberian

akses pada suatu proses, jika pemberian akses tidak mungkin

menuju kepada deadlock, maka sumber daya akan diberikan pada

proses yang meminta. Jika tidak aman, proses yang meminta akan

di-suspend sampai suatu waktu permintaannya aman untuk

diberikan. Kondisi ini terjadi ketika setelah sumber daya yang

sebelumnya dipegang oleh proses lain telah dilepaskan.

Kondisi aman yang dimaksudkan selanjutnya disebut

sebagai safe-state, sedangkan keadaan yang tidak memungkinkan

untuk diberikan sumber daya yang diminta disebut unsafe-state.

a. Kondisi Aman (Safe State)

Suatu keadaan dapat dinyatakan sebagai safe state

jika tidak terjadi deadlock dan terdapat cara untuk

memenuhi semua permintaan sumber daya yang ditunda

tanpa menghasilkan deadlock. Dengan cara mengikuti

urutan tertentu.

b. Kondisi Tak Aman (Unsafe State)

Suatu state dinyatakan sebagai state tak selamat

(unsafe state) jika tidak terdapat cara untuk memenuhi

Deadlock Page 9

semua permintaaan yang saat ini ditunda dengan

menjalankan proses-proses dengan suatu urutan.

Pada sistem kebanyakan permintaan terhadap

sumber daya dilakukan sebanyak sekali saja. Sistem

sudah harus dapat mengenali bahwa sumber daya itu

aman atau tidak (tidak terkena deadlock), setelah itu baru

dialokasikan.

Pada sistem deadlock avoidance (penghindaran) dilakukan

dengan cara memastikan bahwa program memiliki maksimum

permintaan. Dengan kata lain cara sistem ini memastikan terlebih

dahulu bahwa sistem akan selalu dalam kondisi aman. Baik

mengadakan permintaan awal atau pun saat meminta permintaan

sumber daya tambahan, sistem harus selalu berada dalam kondisi

aman. Status Aman Status ini terjadi jika sistem dapat

mengalokasikan sumber daya bagi tiap proses dalam keadaan

tertentu dan masih dapat terjadi deadlock. Status aman bukanlah

status deadlock, jadi status deadlock merupakan status tidak aman,

tetapi tidak selamanya status tidak aman mengakibatkan status

deadlock melainkan ada kemungkinan dapat terjadi.

2.5.4 Pencegahan

Metode Pencegahan dianggap sebagai solusi yang bersih

dipandang dari sudut tercegahnya deadlock. Tetapi pencegahan

akan mengakibatkan kinerja utilisasi sumber daya yang buruk.

Metode pencegahan menggunakan pendekatan dengan cara

meniadakan empat syarat yang dapat menyebabkan deadlock

terjadi pada saat eksekusi. Coffman (1971)

Deadlock Page 10

Syarat pertama yang akan dapat ditiadakan adalah Mutual

Exclusion, jika tidak ada sumber daya yang secara khusus

diperuntukkan bagi suatu proses maka tidak akan pernah terjadi

deadlock. Namun jika membiarkan ada dua atau lebih proses

mengakses sebuah sumber daya yang sama akan menyebabkan

chaos. Langkah yang digunakan adalah dengan spooling sumber

daya, yaitu dengan mengantrikan job-job pada antrian dan akan

dilayani satu-satu.

Beberapa masalah yang mungkin terjadi adalah:

a. Tidak semua dapat di-spool, tabel proses sendiri tidak

mungkin untuk di-spool.

b. Kompetisi pada ruang disk untuk spooling sendiri dapat

mengarah pada deadlock.

Hal inilah yang menyebabkan mengapa syarat pertama tidak

dapat ditiadakan, jadi mutual exclusion benar-benar tidak dapat

dihilangkan.

Cara kedua dengan meniadakan kondisi hold and wait

terlihat lebih menjanjikan. Jika suatu proses yang sedang

menggunakan sumber daya dapat dicegah agar tidak dapat

menunggu sumber daya yang lain, maka deadlock dapat dicegah.

Langkah yang digunakan adalah dengan membuat proses agar

meminta sumber daya yang mereka butuhkan pada awal proses

sehingga dapat dialokasikan sumber daya yang dibutuhkan. Namun

jika terdapat sumber daya yang sedang terpakai maka proses

tersebut tidak dapat memulai prosesnya.

Masalah yang mungkin terjadi:

a. Sulitnya mengetahui berapa sumber daya yang akan

dibutuhkan pada awal proses.

b. Tidak optimalnya pengunaan sumber daya jika ada

sumber daya yang digunakan hanya beberapa waktu dan

tidak digunakan tapi tetap dimiliki oleh suatu proses

yang telah memintanya dari awal.

Deadlock Page 11

Meniadakan syarat ketiga non preemptive ternyata tidak

lebih menjanjikan dari meniadakan syarat kedua, karena dengan

meniadakan syarat ketiga maka suatu proses dapat dihentikan

ditengah jalan. Hal ini tidak dimungkinkan karena hasil dari suatu

proses yang dihentikan menjadi tidak baik.

Cara terakhir adalah dengan meniadakan syarat keempat

circular wait. Terdapat dua pendekatan, yaitu:

a. Mengatur agar setiap proses hanya dapat menggunakan

sebuah sumber daya pada suatu waktu, jika

menginginkan sumber daya lain maka sumber daya yang

dimiliki harus dilepas.

b. Membuat penomoran pada proses proses yang mengakses

sumber daya. Suatu proses dimungkinkan untuk dapat

meminta sumber daya kapan pun, tetapi permintaannya

harus dibuat terurut.

Masalah yang mungkin terjadi dengan mengatur bahwa

setiap proses hanya dapat memiliki satu proses adalah bahwa tidak

semua proses hanya membutuhkan satu sumber daya, untuk suatu

proses yang kompleks dibutuhkan banyak sumber daya pada saat

yang bersamaan. Sedangkan dengan penomoran masalah yang

dihadapi adalah tidak terdapatnya suatu penomoran yang dapat

memuaskan semua pihak.

Deadlock Page 12

BAB III

PENUTUP

3.1 Kesimpulan

Dari uraian diatas, maka dapat ditarik kesimpulan yaitu:

Deadlock adalah suatu kondisi dimana sekumpulan proses tidak dapat berjalan kembali akibat kompetisi memperebutkan sumber daya.

Sebuah proses berada dalam keadaan deadlock apabila semua proses berada dalam keadaan menunggu (di dalam waiting queue) peristiwa yang hanya bisa dilakukan oleh proses yang berada dalam waiting queue tersebut.

Sebenarnya deadlock dapat disebabkan oleh empat hal yaitu:1. Proses Mutual Exclusion.2. Proses memegang dan menunggu.3. Proses Preemption.4. Proses Menunggu dengan siklus deadlock tertentu.

3.2 Saran

Saya sebagai penulis menyarankan agar setiap sistem yang akan kita buat

memiliki sebuah algoritma untuk menangani deadlock. Apabila pada sebuah

sistem tidak tersedia pencegahan ataupun penghindaran deadlock, kemungkinan

besar deadlock dapat terjadi. Pada keadaan seperti ini, sistem harus menyediakan

algoritma pendeteksian deadlock dan algoritma pemulihan deadlock.

Deadlock Page 13