TUGAS SISTEM OPERASI
DEADLOCK
Disusun Oleh :
1. Anna Gracia M / 1606020002
2. Arumdhany / 1606020004
3. Dena Nur Arifah / 1606020006
POLITEKNIK NEGERI CILACAP
PROGRAM STUDI D3 TEKNIK INFORMATIKA
Pengertian Deadlock
Deadlock adalah keadaan dimana 2 atau lebih proses saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya. Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah. Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses.
Model Deadlock
Urutan kejadian operasi perangkat masukan/keluaran adalah :
· Meminta (request) : meminta layanan perangkat masukan/keluaran.
· Memakai (use) : memakai perangkat masukan/keluaran.
Syarat-syarat Perlu bagi Terjadinya Deadlock
Coffman, menyatakan empat syarat terjadinya deadlock, yaitu:
1. Mutual exclusion (mutual exclution condition)
Sumber daya saat itu diberikan pada tepat satu proses.
2. Kondisi genggam dan tunggu (hold and wait condition)
Proses-proses yang sedang menggenggam sumber daya, mnunggu sumber daya – sumber daya baru.
3. Kondisi non-preemption (non-preemption condition)
Sumber daya – sumber daya yang sebelumnya diberikan tidak dapat diambil paksa dari proses yang sedang menggenggamnya. Sumber daya – sumber daya harus secara eksplisit dilepaskan dari proses yag menggenggamnya.
4. Kondisi meunggu secara sirkuler (circular wait condition)
Harus terdapat rantai sirkuler dari dua proses atau lebih, masing-masing menunggu sumber daya yang digenggam oleh anggota berikutnya pada rantai itu.
Deadlock baru benar-benar terjadi bila kondisi keempat terpenuhi. Kondisi keempat merupakan kharusan bagi terjadinya peristiwa deadlock. Bila salah satu dari keempat kondisi itu tidak terpenuhi maka deadlock tidak terjadi.
Metode-metode Mengatasi Deadlock
Ragam metode untuk mengatasi deadlock dapat dikelompokkan menjadi 3 yaitu (Bambang, 2006) :
1. Metode Pencegahan Terjadinya Deadlock (deadlock prevention)
Metode ini berkaitan dengan pengkondisian sistem sehingga menghilangkan kemungkinan terjadinya deadlock. Pencegahan merupakan solusi yang bersih dipandang dari sisi tercegahnya deadlock. Nmun metode ini sering menghasilkan penggunaan sumber daya yang buruk.
2. Metode Penghindaran Terjadinya Deadlock (deadlock avoidance)
Tujuan metode ini adalah menghindaran kondisi-kondisi yang paling mungkin menimbulkan deadlock agar memperoleh utilitas sumber daya yang lebih baik. Penghindaran bukan berati menghilangkan semua kemungkinan terjadinya deadlock. Secara teoris, deadlock dimungkinkan. Sistem operasi memeriksa semua permintaan sumbr daya secara hati-hati. Jika sistem operasi mengetahui bahwa alokasi sumber daya menimbulkan resiko deadlock, sistem menolak pengaksesan itu. Dengan itu menghindari terjadinya deadlock.
3. Metode Deteksi dan Pemulihan dari Deadlock (deadlock detection and recorvery)
Metode ini digunakan pada sistem yang mengijinkan terjadinya deadlock. Tujuan metode ini adalah memeriksa apakah telah terjadi deadlock dan menentukan proses-proses dan sumber daya – sumber daya yang terlibat deadlock. Begitu telah dapat ditentukan, sistem dipulihkan dari deadlock dengan metode pemulihan. Metode pemulihan dari deadlock berupaya untuk menghilangkan deadlock dari sistem sehingga sistem beroperasi kembali bebas dari deadlock.
Pencegahan Deadlock
Havender (HAV-68) mengemukakan bahwa jika sembarang syarat dari keempat syarat terjadinya deadlock tidak terpenuhi maka tidak akan terjadi deadlock. Havender menyarankan strategi-strategi berikut :
1. Tiap proses harus meminta semua sumber daya yang diperlukan sekaligus dan tidak berlanjut sampai semuanya diberikan.
2. Jika proses telah sedang memegang sumber daya tertentu, untuk permintaan berikutnya proses harus melepas dulu sumber daya yang dipegangnya. Jika diperlukan, proses meminta kembali sekaligus dengan sumber daya yang baru.
3. Memberi pengurutan linear terhadap tipe-tipe sumber daya pada semua proses, yaitu jika proses telah dialokasikan suatu tipe sumber daya, proses hanya boleh berikutnya meminta sumber daya-sumber daya tipe pada urutan yang berikutnya.
A. Meniadakan Mutual Exclusion
Deadlock disebabkan terdapatnya pengaksesan eksklusif terhadap sumber daya jika tidak ada sumber daya eksklusif untuk satu proses tunggal maka tidak pernah dijumpai deadlock. Cara yang dapat ditempuh untuk mengakali pengaksesan eksklusif adalah melakukan spooling peragkat-perangkat yang harus didedikasikan ke suatu proses. Pengaksesan sumber daya seolah-olah tidak eksklusif walausebenarnya tetap eksklusif, hanya dengan spooling berarti permintaan-permintaan itu diantrikan di hard disk. Job-job diantrikan spooler akan dilayani satu persatu.
Terdapat masalah terhadap tenik ini adalah
1. Tidak setiap sumber daya eksklusif dapat di spooling misalnya table proses.
2. Kompetisi terhadap ruang hard disk untuk spooling dapat menuntun ke deadlock. Abstraksi ini sebenarnya berarti kembali terjadi kondisi yang mengharuskan kondisi exclusion namun mutual exclusion menjadi di level lebih bawah yaitu level suatu lokasi memori bukan lagi satu perangkat.
Mutual exclution benar – benar tidak dapat dihindari, hanya mampu dperkecil lama waktu berlangsungnya.
B. Meniadakan Syarat Hold and Wait
Metode untuk meniadakan syarat hold and wait dapat dilakukan dengan cara :
1. Mengalokasikan Semua Sumber Daya atau Tidak Sama Sekali
Proses hanya dilayani permintaannya bila sumber daya yang diperlukan tersedia. Teknik ini berbass pada kaidah memperoleh semua atau tidak sama sekali.
a. Jika semua sumber daya tersedia, proses dialokasikan semua sumber daya yang diperlukannya dan berjalan sampai selesai.
b. Jika tidak tersedai sedikitnya satu sumber daya maka proses harus menunggu sampai semua sumber daya yang diperlukannya tersedia untuk dialokasikan padanya.
Masalah
a. Sukar mengetahui lebih dulu semua sumber daya yang diperlukan suatu proses karena diawal proses tidak diketahui beberapa sumber daya yang akan diperlukan
b. Cara ini dapat mengakibatkan penggunaan sumber daya yang sangat tidak efisien.
2. Hold and Relase
Yaitu setiap kali terjadi permintaan suatu sumber daya maka proses harus melepas sumber daya lan yang telah digunakan. Pada satu saat hanya satu sumber daya yang dialokasikan pada proses.
Masalah
Teknik ini tidak mungkin sebab terdapat proses yang mengsyaratkan harus memegang beberapa sumber daya sekaligus untuk melanjutkan eksekusinya.
C. Meniadakan non-preemption
Peniadan non-preemptio mecegah proses lain harus menunggu. Seluruh proses menjadi preemption agar tidak ada kejadian tunggu menunggu.
Masalah
Tidak mungkin meniadakan non-preemptive
Misalnya saat proses a menulis ke printer tiba-tiba dihentikan oleh proses b yang juga akan menulis ke printer yan sama. Bila kondisi preemption ini dimungkinkan maka kedua proses akan mencetak secara tidak benar.
D. Meniadakan Menunggu Sircular
Kondisi ini dapat ditiadakan dalam bermacam cara, antara lain :
1. Proses hanya dibolehka menggenggam satu daya pada satu saat.
Proses hanya dibolehkan menggenggam satu sumber daya pada satu saat telah dibahas. Jika perlu sumber daya kedua, proses harus melepas sumber daya yang pertama.
Teknik ini tidak dimungkinkan karena terdapat proses yang mengharuskan memegang lebih dari satu sumber daya pada saat yang sama untuk menyelesaikan prosesnya.
2. Penomoran global semua sumber daya
Proses dapat meminta proses kapanpun menginginkan tapi permintaan harus dibuat terurut secara numeric. Cara ini tidak akan menimbulkan siklus. Masalahnya tidak ada cara pengurutan nomor sumber daya yang memuaskan semua pihak.
Penghindaran Deadlock
Gagasan dasar penghindaran deadlock adalah hanya memberi akses ke permintaan suber daya yang tidak mungkin menimbulkan deadlock. Strategi ini biasanya diimplementasikan dengan pengalokasi sumber daya memeriksa dampak – dampak pemberian permintaan.
· Jika pemberian akses sumber daya tidak mungkin menuju deadlock, sumber daya diberikan ke peminta.
· Jika tidak aman(memungkinkan timbulnya deadlock), proses yang meminta di – suspend sampai suatu waktu permintaannya aman diberikan. Kondisi ini biasanya terjadi setelah sumber daya atau lebih yang semula dipegang oleh proses – proses aktif lain dilepaskan.
Metode alternative untuk menghindari deadlock adalah digunakan informasi tambahan tentang bagaimana sumber daya diminta. Misalnya pada sistem dengan stu tape drive dan satu printer. Proses P pertama meminta tape drive dan kemudian printer sebelum melepaskan kedua sumber daya tersebut. Sebaliknya proses Q pertama meminta printer kemudian tape drive.
Dengan mengetahui urutan permintaan dan pelepasan sumber daya untuk setiap proses, dapat diputuskan bahwa untuk setiap permintaan apakah proses harus menunggu atau tidak. Setiap permintaan ke sistem harus dipertimbangkan apakah sumber daya tersedia, sumber daya sedang dialokasikan untuk proses dan permintaan kemudian serta pelepasan oleh proses untuk menentukan apakah permintaan dapat dipenuhi atau harus menunggu untuk menghindari deadlock. (Pangera & Ariyus, 2010)
Model yang sederhana dan sangat penting dibutuhkan adalah setiap proses menentukan jumlah maksimum sumber daya dari setiap tipe yang mungkin diperlukan.
A. State Selamat dan State Tidak Selamat
State Selamat (safe state)
State yang dinyatakan sebagai state selamat(safe state) jika tidak deadlock dan terdapat cara untuk memenuhi semua permintaan yang ditunda tanpa menghasilkan deadlock dengan menjalankan proses – proses secara hati – hati mengikuti suatu urutan tertentu.
State Tak Selamat(unsafe state)
State dinyatakan sebagai state tak selamat (unsafe state) jika tidak terdapat cara untuk memenuhi semua permintaan yang saat ini ditunda dengan menjalankan proses – proses degan suatu urutan.
Ketika suatu proses meminta sumber daya yang tersedia, sistem harus menentukan apakah alokasi sumber daya pada proses mengakibatkan siste dalam safe state. Sistem dikatakan dalam safe state jika sistem dapat mengalokasikan sumber daya untuk setiap proses secara berurutan dan menghindari deadlock. Untuk proses <P1, P2, …Pn> safe jika untuk setiap P1, sumber daya yang masih diminta Pi masih memenuhi sumber daya yang tersedia dan sumber daya yan dibawa oleh setiap Pj, dimana j<i. Jika sumber daya yang diperlukan Pi tidak dapat segera disediakan maka Pi dapat menunggu sampai semua Pj selesai.
Ketika Pj selesai, Pi dapat memperoleh sumber daya yang diperlukan, mengeksekusi, menembalikan sumber daya yang dialokasikan dan terminasi. Ketika Pi selesai, Pi+ 1 dapat memperoleh sumber daya yang diperlukan dan seterusnya. Jika sistem dalam safe state maka tidak terjadi deadlock, sedangkan jika sistem dalam unsafe state maka kemungkinan terjadi deadlock.
Gambar 1 Ruang Safe state, unsafe, dan deadlock
B. Algoritma Banker oleh Dijkstra
Disebut algoritma Banker karena memodelkan banker di kota kecil yang berurusan dengan sekumpulan nasabah yang meminta kredit. Pada algoritma Banker ini, kodisi mutual exlusion, hold-and-wait, dan no-preemption diijinkan dan proses – proses melakukan klaim penggunaan eksklusif sumber daya – sumber daya yang diperlukan. Proses – proses diijinkan menggenggam sumber daya – sumber daya sambil meminta dan menunggu sumber daya – sumber daya lain serta sumber daya – sumber daya itu tidak diijinkan di-preempt prosese lain.
Proses – proses dapat meminta satu sumber daya pada suatu waktu. Sistem operasi dapat memberikan akses sumber daya atau menolak permintaan. Jika ditolak, proses masih menggeggam sumber daya yang telah dialokasikan untuknya dan menunggu selama waktu berhingga sampai permintaannya dapa diberikan.
Sistem hanya memberikan permintaan yang menghasilkan state selamat. Permintaan proses akan menghasilkan state tak selamat secara berulang ditolak sampai permintaan dapat terpenuhi. Tentunya karna sistem selalu memelihara agar dalam state safe, cpat atau lambat(yaitu dalam waktu yang berhingga) semua permintaan dapat dipenuhi dan semua proses dapat berakhir.
Kelemahan :
Kelemahan algoritma banker adalah sebagai berikut : [TAN-92, STA-95, DEI-90]
1. Proses – proses jarang megetahui di awal proses jumlah maksimum sumber daya yang akan diperlukan.
2. Jumlah proses tidak tetap, secara dinamis beragam begitu pemakai – pemakai baru ogin dan logout.
3. Sumber daya yang dihitung sebagai tersedia dapa saja tiba – tiba ditanggalka sehingga tidak tersedia lagi.
4. Proses –proses indepeden, yaitu urutan proses –proses dieksekusi tidak dibatasi kebutuhan sinkronsasi antarproses.
5. Algoritma menghendaki memberika semua permintaan selama waktu yang berhingga.
6. Algoritma menghendaki client – vlient mengembalikan sumber daya setelah suatu waktu yang berhingga.
Deteksi dan Pemulihan Deadlock
A. Deteksi adanya deadlock
Deteksi Deadlock adalah teknik untuk menentukan apakah deadlock terjadi serta mengidentifikasi proses-proses dan sumber daya – sumber daya yang terlibat deadlock. Umumnya algoritma – algoritma deteksi yang digunakan adalah menentukan keberadaan menunggu sircular (circular wait). Penggunaan algoritma deteksi deadlock melibatkan overhead pada saat berjalan karena secara periodik dijalankan untuk mendeteksi menunggu sircular. Sembarang algoritma pendeteksian siklus pada graph berarah yang digunakan.
Periode yang biasa dilakukan adalah memonitor permintaan dan pelepasan sumber daya. Setiap terdapat permintaan dan pelepasan maka dilakukan perbaruan graph dan deteksi adanya siklus. Bila terdapat siklus berarti terjadi kondisi menunggu sircular dan deadlock terjadi.
1. Satu Anggota untuk Setiap Tipe Sumber Daya
Jika setiap sumber daya hanya mempunyai satu anggota, kita dapat menentukan algoritma mendeteksi deadlock menggunakan bentuk resource allocation graph yan disebut wait-graph
2. Beberapa Anggota untuk Setiap Tipe Sumber Daya
Untuk tipe sumber daya yang mempunyai bebrapa anggota digunakan algoritma Banker.
3. Penggunaan Algoritma Deteksi
Untuk menjawab kapan dan berapa sering menggunakan algoritma deteksi, hal ini bergantung pada :
a. Seberapa sering terjadi deadlock
b. Berapa proses yang perlu dilakukan roll back.
Jika algoritma deteksi digunakan, terdapat beberapa siklus pada graph, hal ini tidak dapat mengetahui berapa proses yang menyebabkan deadlock.
B. Pemulihan dari deadlock
Begitu sistem terjadi deadlock, deadlock harus diputuskan dengan menghilangkan satu syarat perlu atau lebih. Biasanya beberapa proses akan kehilangan sebagian atau semua kerja yang telah dilakukan. Hal ini merupakan ongkos yang harus dibayar disbanding terjadinya deadlock yang berarti semua proses tidak menghasilkan apapun. Pemilihan dari deadlock dirumitkan oleh factor-faktor berikut :
1. Belum tentu dapat menentukan adanya deadlock secepatnya.
2. Kebanyakan sistem tidak memiliki fasilitas atau mempunyai fasilitas – fasilitas buruk untuk men-suspend proses, menghilangkan dari sistem dan men-resume proses dilain waktu. Pada sstem waktu nyata yang harus berfungsi terus – menerus, proses – proses tidak dapat di-suspend dan di-resume.
3. Bahkan jika terdapat kemampuan suspend dan resume yang efektif. Kekampuan ini meibatkan sejumlah overhead berarti dan memerlukan perhatian operator yang berkemampuan tinggi. Operator semacam ini tidak selalu tersedia.
4. Pemulihan memerlukan sejumlah kerja yang berarti.
Pada sistem operasi dengan hanya tiga state dasar (Running,Ready,Blocked), maka tidak ada cara lain kecuali dilakukan penyingkiran terhadap proses itu(Kill Process). Proses benar – benar hilang dari memori dan harus dimuat kembali. Pada sistem operasi modern sistem biasanya menerapkan state suspendedblocked dan suspendedready, dimana suber daya dilepas tetapi proses masih dimemory dan akan ditetapkan kembali sumber daya untuk proses itu begitu terjadi resume.
Teknik pemulihan yang biasa digunakan adalah mengihilangkan(dengan suspend atau kill). Proses – proses dari sistem dan pengklaiman kembali ( reclaim) sumber daya – sumber daya yang dipegang proses – proses itu. Proses yang dihilangkan biasanya akan cacat, tapi proses – proses lain dapat menyelesaikan prosesnya. Kadang perlu menyingkirkan beberapa proses sampai tidak terjadi deadlock. Istilah “pemulihan” sebenarnya kurang beararti karena yang terjadi sesungguhnya adalah penyingkiran beberapa proses.
Pendekatan berikut dapat dilakukan untuk pemulihan deadlock. Pendekatan – pendekatan dituliskan terurut kecanggihan penyelesaiannya.
1. Abaikan(singkirkan) semua proses yang terlibat deadlock. Teknik ini merupakan cara termudah dan solusi yang paling sering dipilih.
2. Back-up semua proses yang terlibat deadlock ke suatu check point yang didefinisikan sebelumnya dan dijalankan kembali semua proses itu. Teknik ini memerlukan mekanisme rollback dan restart. Risiko pendekatan ini adalah deadlock semula pada terjadi lagi. Tetapi karena ketidaktentuan pemrosesan konkuren, biasanya menjamin tidak akan terjadi deadlock serupa.
3. Secara berturutan abaikan(singkirkan) proses – proses sampai deadlock tidak ada lagi. Urutan proses yang dipilih untuk disingkirkan berdasar kriteria ongkos minimum. Setelah masing – masing penyingkiran, algoritma deteksi harus dijalankan untuk melihat apakah masih terdapat deadlock.
4. Secara berturutan preempt sumber daya – sumber daya sampai tidak ada deadlock lagi. Sebagaimana item 3 pemilihan berdasarkan ongkos yang digunakan kehilangan sumber daya karena preemption harus dikembalikan (roll-back) ketitik sebelum memperoleh sumber daya.
Untuk item 3 dan 4 kriteria pemilihan proses yang akan disingkirkan atau disuspend adalah dengan kriteria – kriteria sebagai berikut :
1. Waktu pemrosesan yang telah dijalankan paling kecil.
2. Jumlah baris keluaran yang diproduksi paling kecil.
3. Mempunyai estimasi sisa waktu eksekusi terbesar.
4. Jumlah total sumber daya terkecil yang telah dialokasikan.
5. Prioritas terkecil.
Hal – hal yang harus diperhatikan dalam penyingkiran proses adalah sistem harus mengembalikan berkas – berkas yang dimodifikasi proses – proses yang disingkirkan ke keadaan asli karena berpengaruh terhadap konsistensi data sistem itu.
Strategi Penanggulangan Deadlock Terpadu
Masing-masing teknik mempunyai keunggulan dan kelemahan, maka daripada berusaha merancang fasilitas sistem operasi dengan satu strategi penanggulangan deadlock maka lebih efisisen mengunakan strategi-strategi berbeda untuk situasi-situasi berbeda.Silberschatz[SIL-94] menyarankan satu pendekatan terpadu, yaitu:
1. Kelompokkan sumber daya – sumber daya menjadi sejumlah kelas sumber daya.
2. Gunakan strategi pengurutan linear seperti yang didefinisikan pada pencegahan menggu sircular. Strategi ini digunakan untuk mencegah deadlock diantara kelas-kelas sumber daya berbeda.
3. Dalam satu kelas sumber daya, gunaka lagoritma yang paling cocok untuk kelas-kelas sumber daya itu.
References
Bambang, H. (2006). Sistem Operasi. Bandung: Informatika.
Pangera, A. A., & Ariyus, D. (2010). SIstem Operasi. Yogyakarta: ANDI Yogyakarta.
