DEADLOCK
1. Pendahuluan
Proses terlibat di dalam deadlock jika proses menunggu suatu kejadian tertentu yang tidak akan pernah terjadi.
Syarat-syarat perlu terjadinya deadlock :
Coffiman, et al. [Cof-71] menyatakan empat syarat terjadinya deadlock, yaitu :
a. Mutual exclusion.
Sumber daya saat itu diberikan pada tepat satu proses.
b. Kondisi genggam dan tunggu.
Proses-proses yang sedang menggenggam sumber daya, menunggu sumber daya-sumber daya baru.
c. Kondisi non-preemption.
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 yang menggenggamnya.
d. Kondisi menunnggu secara sirkuler.
Harus terdapat rantai sirkuler dari dua proses atau lebih, masing-masing menunggu sumber daya yang digenggam oleh anggota berikutnya pada rantai itu.
2. Metode Mengatasi Deadlock
a. Metode pencegahan terjadinya deadlock.
b. Metode penghindaran terjadinya deadlock.
c. Metode deteksi dan pemulihan dari deadlock.
Strategi Burung Unta. Strategi ini mengasumsikan kejadian dadlock jarang terjadi dibandingkan kejadian computer mengalami crash. Mengapa bersusah payah mengatasi deadlock ? Toh, sistem lebih sering rusak karena crash. Disebut strategi burung unta karena solusi ini sebenarnya tidak mempedulikan adanya masalah. Strategi ini berarti sama sekali tidak berusaha untuk mengatasi deadlock atau sama sekali tidak ada metode yang diterapkan untuk mengatasi deadlock.
3. Metode 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 untuk meniadakan syarat-syarat tersebut, yaitu :
a. Tiap proses harus meminta semua sumber daya yang diperlukan sekaligus dan tidak berlanjut sampai semuanya diberikan.
b. 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.
c. Memberi pengurutan linear terhhadap 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.
3.1 Mutual Exclusion
Deadlock disebabkan adanya pengaksesan ekslusif terhadap sumber daya. Jika tidak ada sumber daya ekslusif untuk suatu proses tunggal maka tidak akan pernah terjadi deadlock. Cara yang dapat ditempuh adalah dengan melakukan spooling perangkat-perangkat yang harus didedikasikan ke suatu proses. Pengaksesan sumber daya seolah-olah tidak ekslusif walau sebenarnya tetap ekslusif, hanya dengan spooling berarti permintaan-permintaan itu diantrikan di hardisk. Job-job di antrian spooler akan dilayani satu per satu.
Masalah :
a. Tidak setiap sumber daya ekslusif dapat di-spooling, misalnya tabel proses.
b. Kompetisi terhadap ruang hardisk untuk spooling dapat menuntun ke deadlock.
c. Mutual exclusion benar-benar tidak dapat dihindari, hanya mampu diperkecil granularitas/lama waktu berlangsungnya
3.2 Meniadakan Syarat Genggam dan Tunggu
a. Mengalokasikan semua sumber daya atau tidak sama sekali.
Proses hanya dilayani permintaannya bila semua sumber daya yang diperlukan tersedia. Jika tidak tersedia sedikitnya satu sumber daya, maka proses harus menunggu sampai semua sumber daya yang diperlukan tersedia untuk dialokasikan padanya.
Masalah : Sukar mengetahui lebih dulu semua sumber daya yang diperlukan suatu proses karena di awal tidak diketahui berapa sumber daya yang diperlukan dan cara ini dapat mengakibatkan penggunaan sumber daya yang tidak efisien.
b. Hold and release
Genggam dan lepaskan, yaitu setiap kali terjadi permintaan suatu sumber daya maka proses harus melepas sumber daya lain yang telah digunakan. Pada satu saat, hanya satu sumber daya yang dialokasikan untuk proses.
Masalah : Teknik ini tidak memungkinkan sebab terdapat proses yang mensyaratkan harus memegang beberapa sumber daya sekaligus untuk melanjutkan eksekusinya.
3.3 Meniadakan Non-Preemption
Peniadaan non-preemption mencegah proses-proses lain harus menunggu. Seluruh proses menjadi preemption agar tidak ada kejadian tunggu-menunggu.
Masalah : Tidak mungkin meniadakan non-preemption.
3.4 Meniadakan Menunggu Sirkular
a. Proses hanya dibolehkan menggenggam satu sumber daya pada satu saat. Jika perlu sumber daya kedua, proses harus melepas sumber daya yang pertama (hold and release).
Masalah : Teknik ini tidak dimungkinkan karena terdapat proses yang mengharuskan memegang lebih dari satu sumber daya pada saat yang sama untuk menyelesaikan prosesnya
b. Penomoran global semua sumber daya. Proses dapat meminta dijalankan kapanpun menginginkan tapi permintaan harus dibuat terurut secara numeric. Cara ini tidak akan menimbulkan siklus.
Masalah : Tidak ada cara pengurutan nomor sumber daya yang memuaskan semua pihak.
4. Metode Menghindari Terjadinya deadlock
Gagasan dasar penghindaran deadlock adalah hanya memberi akses ke permintaan sumber daya yang tidak mungkin menimbulkan deadlock. Strategi ini biasanya diimplementasikan dengan pengalokasi sumber daya memeriksa dampak-dampak pemberian akses ke suatu permintaan.
• Jika pemberian akses sumber daya tidak mungkin menuju deadlock, sumber daya diberikan permintaan
• Jika tidak aman (memungkinkan terjadinya deadlock), proses yang meminta di-suspend sampai suatu waktu permintaannya aman diberikan. Kondisi ini biasanya terjadi setelah satu sumber daya atau lebih yang semula dipegang oleh proses-proses aktif lain dilepaskan.
Agar dapat mengevaluasi safe-nya state, penghindaran deadlock mengharuskan semua proses menyatakan jumlah kebutuhan sumber daya maksimum sebelum eksekusi. Jika kebutuhannya melebihi kapasitas total sistem maka proses tidak dapat dieksekusi. Jika kebutuhan sumber daya yang diperlukan sudah tersedia semua, maka sistem akan memeriksa apakah pemberian sumber daya akan menuntun ke deadlock (memeriksa apakah proses-proses yang telah aktif dapat secara selamat selesai). Jika dapat berakhir secara selamat, maka sumber daya dialokasikan ke proses yang meminta.
State selamat (safe state)
State 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 jika tidak terdapat cara untuk memenuhi semua permintaan yang saat ini ditunda dengan menjalankan proses-proses dengan suatu urutan.
5. Metode Deteksi dan Pemulihan dari 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 sirkular (circular wait). Penggunaan algoritma deteksi deadlock melibatkan overhead pada saat berjalan karena secara periodik dijalankan untuk mendeteksi circular wait. Sembarang algoritma pendeteksian siklus pada graph berarah dapat digunakan.
• Begitu sistem terdapat deadlock dpat dipulihkan dengan menghilangkan satu syarat perlu atau lebih. Biasanya beberapa proses akan kehilanggan sebagian atau semua kerja yang telah dilakukan. Hal ini merupakan ongkos yang harus dibayar disbanding terjadinya deadlock yang berarti proses tidak menghasilkan apa pun.
Pemulihan dari deadlock dirumitkan oleh faktor-faktor berikut :
a. Belum tentu dapat menentukan adanya deadlock dengan cepat
b. Kebanyakan sistem mempunyai fasilitas buruk untuk men-suspend proses, menghilangkan proses dari sistem untuk di-resume di lain waktu.
c. Jika kemampuan men-suspend dan me-resume ini tersedia dan efektif, maka akan melibatkan sejumlah overhead. Itu berarti memerlukan kemampuan operator yang tinggi. Operator semacam ini tidak selalu tersedia.
d. Pemulihan memerlukan sejumlah kerja yang berarti.
Teknik pemulihan yang biasa digunakan adalah menghilangkan (dengan suspend atau kill) proses-proses dari sistem dan pengklaiman kembali (reclaim) sumber daya-sumber daya yang dipegang proses-roses itu. Proses yang dihilangkan biasanya akan cacat, tapi proses-proses lain dapat menyelesaikan prosesnya.
Pendekatan berikut dapat dilakukan untuk pemulihan deadlock :
a. Abaikan (singkirkan) semua proses yang terlibat deadlock. Teknik ini merupakan cara termudah dan solusi yang paling sering dipilih.
b. Back-up semua proses yang terlibat deadlock ke suatu checkpoint yang didefinisikan sebelumnya dan jalankan kembali semua proses itu. Resikonya, deadlock semula dapat terjadi lagi, tetapi karena ketidaktentuan pemrosesan konkuren, biasanya menjamin tidak akan terjadi deadlock serupa.
c. Seacara berurutan abaikan (singkirkan) proses-proses sampai deadlock tidak ada lagi.
d. Secara berurutan preempt sumber daya-sumber daya sampai tidak ada lagi deadlock.
6. 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 efisien menggunakan strategi-strategi berbeda untuk situasi-situasi berbeda. Silberschatz [SIL-94] menyarankan satu pendekatan terpadu, yaitu :
a. Kelompokan sumber daya-sumber daya menjadi sejumlah kelas sumber daya
b. Gunakan strategi pengurutan linear seperti yang didefinisikan pada pencegahan menunggu sirkular. Strategi ini digunakan untuk mencegah deadlock di antara kelas-kelas sumber daya berbeda.
c. Dalam satu kelas sumber daya, gunakan algoritma yang paling cocok untuk kelas-kelas sumber daya itu.
Proses terlibat di dalam deadlock jika proses menunggu suatu kejadian tertentu yang tidak akan pernah terjadi.
Syarat-syarat perlu terjadinya deadlock :
Coffiman, et al. [Cof-71] menyatakan empat syarat terjadinya deadlock, yaitu :
a. Mutual exclusion.
Sumber daya saat itu diberikan pada tepat satu proses.
b. Kondisi genggam dan tunggu.
Proses-proses yang sedang menggenggam sumber daya, menunggu sumber daya-sumber daya baru.
c. Kondisi non-preemption.
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 yang menggenggamnya.
d. Kondisi menunnggu secara sirkuler.
Harus terdapat rantai sirkuler dari dua proses atau lebih, masing-masing menunggu sumber daya yang digenggam oleh anggota berikutnya pada rantai itu.
2. Metode Mengatasi Deadlock
a. Metode pencegahan terjadinya deadlock.
b. Metode penghindaran terjadinya deadlock.
c. Metode deteksi dan pemulihan dari deadlock.
Strategi Burung Unta. Strategi ini mengasumsikan kejadian dadlock jarang terjadi dibandingkan kejadian computer mengalami crash. Mengapa bersusah payah mengatasi deadlock ? Toh, sistem lebih sering rusak karena crash. Disebut strategi burung unta karena solusi ini sebenarnya tidak mempedulikan adanya masalah. Strategi ini berarti sama sekali tidak berusaha untuk mengatasi deadlock atau sama sekali tidak ada metode yang diterapkan untuk mengatasi deadlock.
3. Metode 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 untuk meniadakan syarat-syarat tersebut, yaitu :
a. Tiap proses harus meminta semua sumber daya yang diperlukan sekaligus dan tidak berlanjut sampai semuanya diberikan.
b. 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.
c. Memberi pengurutan linear terhhadap 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.
3.1 Mutual Exclusion
Deadlock disebabkan adanya pengaksesan ekslusif terhadap sumber daya. Jika tidak ada sumber daya ekslusif untuk suatu proses tunggal maka tidak akan pernah terjadi deadlock. Cara yang dapat ditempuh adalah dengan melakukan spooling perangkat-perangkat yang harus didedikasikan ke suatu proses. Pengaksesan sumber daya seolah-olah tidak ekslusif walau sebenarnya tetap ekslusif, hanya dengan spooling berarti permintaan-permintaan itu diantrikan di hardisk. Job-job di antrian spooler akan dilayani satu per satu.
Masalah :
a. Tidak setiap sumber daya ekslusif dapat di-spooling, misalnya tabel proses.
b. Kompetisi terhadap ruang hardisk untuk spooling dapat menuntun ke deadlock.
c. Mutual exclusion benar-benar tidak dapat dihindari, hanya mampu diperkecil granularitas/lama waktu berlangsungnya
3.2 Meniadakan Syarat Genggam dan Tunggu
a. Mengalokasikan semua sumber daya atau tidak sama sekali.
Proses hanya dilayani permintaannya bila semua sumber daya yang diperlukan tersedia. Jika tidak tersedia sedikitnya satu sumber daya, maka proses harus menunggu sampai semua sumber daya yang diperlukan tersedia untuk dialokasikan padanya.
Masalah : Sukar mengetahui lebih dulu semua sumber daya yang diperlukan suatu proses karena di awal tidak diketahui berapa sumber daya yang diperlukan dan cara ini dapat mengakibatkan penggunaan sumber daya yang tidak efisien.
b. Hold and release
Genggam dan lepaskan, yaitu setiap kali terjadi permintaan suatu sumber daya maka proses harus melepas sumber daya lain yang telah digunakan. Pada satu saat, hanya satu sumber daya yang dialokasikan untuk proses.
Masalah : Teknik ini tidak memungkinkan sebab terdapat proses yang mensyaratkan harus memegang beberapa sumber daya sekaligus untuk melanjutkan eksekusinya.
3.3 Meniadakan Non-Preemption
Peniadaan non-preemption mencegah proses-proses lain harus menunggu. Seluruh proses menjadi preemption agar tidak ada kejadian tunggu-menunggu.
Masalah : Tidak mungkin meniadakan non-preemption.
3.4 Meniadakan Menunggu Sirkular
a. Proses hanya dibolehkan menggenggam satu sumber daya pada satu saat. Jika perlu sumber daya kedua, proses harus melepas sumber daya yang pertama (hold and release).
Masalah : Teknik ini tidak dimungkinkan karena terdapat proses yang mengharuskan memegang lebih dari satu sumber daya pada saat yang sama untuk menyelesaikan prosesnya
b. Penomoran global semua sumber daya. Proses dapat meminta dijalankan kapanpun menginginkan tapi permintaan harus dibuat terurut secara numeric. Cara ini tidak akan menimbulkan siklus.
Masalah : Tidak ada cara pengurutan nomor sumber daya yang memuaskan semua pihak.
4. Metode Menghindari Terjadinya deadlock
Gagasan dasar penghindaran deadlock adalah hanya memberi akses ke permintaan sumber daya yang tidak mungkin menimbulkan deadlock. Strategi ini biasanya diimplementasikan dengan pengalokasi sumber daya memeriksa dampak-dampak pemberian akses ke suatu permintaan.
• Jika pemberian akses sumber daya tidak mungkin menuju deadlock, sumber daya diberikan permintaan
• Jika tidak aman (memungkinkan terjadinya deadlock), proses yang meminta di-suspend sampai suatu waktu permintaannya aman diberikan. Kondisi ini biasanya terjadi setelah satu sumber daya atau lebih yang semula dipegang oleh proses-proses aktif lain dilepaskan.
Agar dapat mengevaluasi safe-nya state, penghindaran deadlock mengharuskan semua proses menyatakan jumlah kebutuhan sumber daya maksimum sebelum eksekusi. Jika kebutuhannya melebihi kapasitas total sistem maka proses tidak dapat dieksekusi. Jika kebutuhan sumber daya yang diperlukan sudah tersedia semua, maka sistem akan memeriksa apakah pemberian sumber daya akan menuntun ke deadlock (memeriksa apakah proses-proses yang telah aktif dapat secara selamat selesai). Jika dapat berakhir secara selamat, maka sumber daya dialokasikan ke proses yang meminta.
State selamat (safe state)
State 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 jika tidak terdapat cara untuk memenuhi semua permintaan yang saat ini ditunda dengan menjalankan proses-proses dengan suatu urutan.
5. Metode Deteksi dan Pemulihan dari 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 sirkular (circular wait). Penggunaan algoritma deteksi deadlock melibatkan overhead pada saat berjalan karena secara periodik dijalankan untuk mendeteksi circular wait. Sembarang algoritma pendeteksian siklus pada graph berarah dapat digunakan.
• Begitu sistem terdapat deadlock dpat dipulihkan dengan menghilangkan satu syarat perlu atau lebih. Biasanya beberapa proses akan kehilanggan sebagian atau semua kerja yang telah dilakukan. Hal ini merupakan ongkos yang harus dibayar disbanding terjadinya deadlock yang berarti proses tidak menghasilkan apa pun.
Pemulihan dari deadlock dirumitkan oleh faktor-faktor berikut :
a. Belum tentu dapat menentukan adanya deadlock dengan cepat
b. Kebanyakan sistem mempunyai fasilitas buruk untuk men-suspend proses, menghilangkan proses dari sistem untuk di-resume di lain waktu.
c. Jika kemampuan men-suspend dan me-resume ini tersedia dan efektif, maka akan melibatkan sejumlah overhead. Itu berarti memerlukan kemampuan operator yang tinggi. Operator semacam ini tidak selalu tersedia.
d. Pemulihan memerlukan sejumlah kerja yang berarti.
Teknik pemulihan yang biasa digunakan adalah menghilangkan (dengan suspend atau kill) proses-proses dari sistem dan pengklaiman kembali (reclaim) sumber daya-sumber daya yang dipegang proses-roses itu. Proses yang dihilangkan biasanya akan cacat, tapi proses-proses lain dapat menyelesaikan prosesnya.
Pendekatan berikut dapat dilakukan untuk pemulihan deadlock :
a. Abaikan (singkirkan) semua proses yang terlibat deadlock. Teknik ini merupakan cara termudah dan solusi yang paling sering dipilih.
b. Back-up semua proses yang terlibat deadlock ke suatu checkpoint yang didefinisikan sebelumnya dan jalankan kembali semua proses itu. Resikonya, deadlock semula dapat terjadi lagi, tetapi karena ketidaktentuan pemrosesan konkuren, biasanya menjamin tidak akan terjadi deadlock serupa.
c. Seacara berurutan abaikan (singkirkan) proses-proses sampai deadlock tidak ada lagi.
d. Secara berurutan preempt sumber daya-sumber daya sampai tidak ada lagi deadlock.
6. 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 efisien menggunakan strategi-strategi berbeda untuk situasi-situasi berbeda. Silberschatz [SIL-94] menyarankan satu pendekatan terpadu, yaitu :
a. Kelompokan sumber daya-sumber daya menjadi sejumlah kelas sumber daya
b. Gunakan strategi pengurutan linear seperti yang didefinisikan pada pencegahan menunggu sirkular. Strategi ini digunakan untuk mencegah deadlock di antara kelas-kelas sumber daya berbeda.
c. Dalam satu kelas sumber daya, gunakan algoritma yang paling cocok untuk kelas-kelas sumber daya itu.
0 comments: