MAKALAH
DEADLOCK DIAJUKAN UNTUK MEMENUHI TUGAS MATA KULIAH Sistem Operasi Dosen Penampu Bapak Adi Sucipto, Ir., M.Kom.
oleh :
Damas Fahmi Assena
NIM : 161240000500
PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NAHDLATUL ULAMA JEPARA 2017
KATA PENGANTAR
Puji syukur kehadiran Allah SWT Yang Maha mendengar lagi Maha Melihat dan atas segala limpahan rahmat, taufik, serta hidayah-Nya sehingga penulis dapat menyelesakan makalah sesuai waktu yang telah direncanakan Shalawat serta salam semoga senantiasa tercurahkan kepada baginda Nabi Besar Muhammad SAW beserta seleruh keluarga dan sahabatnya. Penulisan makalah ini merupakan tugas mata kuliah Sistem Operasi di semester 2 tahun akademik 2016/2017. Dalam penulisan makalah ini, tentunya banyak pihak yang telah memberikan bantuan baik moril maupun materil. Penulis menyadari bahwa makalah ini masih jauh dari kesempurnaan, maka saran dan kritik yang konstruktif dari semua pihak sangat diharapkan demi penyempurnaan selanjutnya.
Jepara, 14 Juli 2017
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...................................................................................... 11
BAB III ................................................................................................................. 13 PENUTUP ............................................................................................................. 13 3.1
Kesimpulan ............................................................................................. 13
3.2
Saran ....................................................................................................... 13
Daftar Pustaka ...................................................................................................... 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
permasalahan 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 artikelartikel 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 masingmasing 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 memberi 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 Deadlock
Page 4
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. Contohnya dapat dilihat dari kode berikut ini: //dari kelas proses kita tambahkan method yaitu meminta public void meminta (int banyakA) { //meminta dari sumber daya a if ( banyakA < banyak ) banyak = banyak - banyakA; else wait(); } //mengubah kode pada mainnya sebagai berikut public 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;
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
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: //menambahkan method receive dan send public void receive( Proses p ) { //method untuk menerima sumber daya } public void send ( Proses p ) { //method untuk memberi sumber daya }
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
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 memungkinkan. 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. Deadlock
Page 10
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) 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.
Deadlock
Page 11
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. 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
DAFTAR PUSTAKA
Permana, I Kadek Adi. 2013. Deadlock : Manajemen Informatika https://www.slideshare.net/search
Deadlock
Page 14