Deadlock

Referensi:

1. Abraham Silberschatz, Greg Gagne, dan Peter Baer Galvin, "Konsep Sistem Operasi, Edisi Kedelapan", Bab 7

7.1 Sistem Model

• Untuk keperluan diskusi kebuntuan, sistem dapat dimodelkan sebagai kumpulan sumber daya yang terbatas, yang dapat dibagi ke dalam kategori yang berbeda, yang akan dialokasikan untuk sejumlah proses, masing-masing memiliki kebutuhan yang berbeda.
• Kategori sumber daya dapat mencakup memori, printer, CPU, file terbuka, tape drive, CD-ROM, dll
• Menurut definisi, semua sumber daya dalam kategori yang sama, dan permintaan dari kategori ini bisa sama-sama puas dengan salah satu dari sumber daya dalam kategori tersebut. Jika hal ini tidak terjadi (yaitu jika ada beberapa perbedaan antara sumber daya dalam kategori), maka kategori tersebut harus dibagi lagi menjadi kategori terpisah. Misalnya, "printer" mungkin perlu dipisahkan menjadi "printer laser" dan "printer inkjet warna".
• Beberapa kategori mungkin memiliki satu sumber daya.
• Dalam operasi normal proses harus meminta sumber daya sebelum menggunakannya, dan melepaskannya ketika hal itu dilakukan, dalam urutan berikut:
  1. Permintaan - Jika permintaan tidak dapat segera diberikan, maka proses tersebut harus menunggu sampai sumber daya (s) perlu menjadi tersedia. Misalnya sistem panggilan terbuka (), malloc (), baru (), dan permintaan ().
  2. Gunakan - Proses menggunakan sumber daya, misalnya mencetak ke printer atau membaca dari file.
  3. Rilis - Proses relinquishes sumber daya. sehingga menjadi tersedia untuk proses lainnya. Misalnya, tutup (), free (), hapus (), dan release ().
• Untuk semua kernel yang dikelola sumber daya, kernel melacak sumber daya apa yang gratis dan yang dialokasikan, yang proses mereka dialokasikan, dan antrian proses menunggu sumber daya ini menjadi tersedia. Aplikasi yang dikelola sumber daya dapat dikendalikan dengan menggunakan mutexes atau menunggu () dan sinyal () panggilan, (yaitu binary atau Semaphore menghitung.)
• Satu set proses adalah jalan buntu ketika setiap proses dalam set menunggu untuk sumber daya yang saat ini dialokasikan untuk proses lain dalam set (dan yang hanya dapat dilepaskan ketika proses menunggu lainnya membuat kemajuan.)

7.2 Deadlock Karakterisasi

7.2.1 Kondisi Diperlukan

• Ada empat kondisi yang diperlukan untuk mencapai kebuntuan:
  1. Pengecualian Reksa - Setidaknya satu sumber daya harus dipegang dalam mode non-sharable, Jika ada permintaan proses lain sumber daya ini, maka proses itu harus menunggu untuk sumber daya akan dirilis.
  2. Tahan dan Tunggu - Sebuah proses harus secara simultan memegang setidaknya satu sumber daya dan menunggu setidaknya satu sumber daya yang saat ini ditahan oleh beberapa proses lain.
  3. Tidak ada preemption - Setelah proses yang memegang sumber daya (yaitu sekali permintaannya telah diberikan), maka sumber daya tidak dapat diambil dari proses tersebut sampai proses sukarela rilis itu.
  4. Tunggu Edaran - Satu set proses {P0, P1, P2,. . , PN.} Harus ada sedemikian rupa sehingga setiap P [i] sedang menunggu P [(i + 1)% (N + 1)]. (Perhatikan bahwa kondisi ini menyiratkan kondisi terus-dan-tunggu, tapi lebih mudah untuk berurusan dengan kondisi jika keempat dianggap secara terpisah.)

7.2.2 Sumber-Alokasi Grafik

• Dalam beberapa kasus deadlock dapat dipahami lebih jelas melalui penggunaan Sumber-Alokasi Grafik, memiliki sifat-sifat berikut:
  • Satu set kategori sumber daya, {R1, R2, R3,. . , RN}, yang muncul sebagai node persegi pada grafik.. Dots dalam node sumber daya menunjukkan contoh spesifik dari sumber daya. (Misalnya dua titik mungkin mewakili dua printer laser.)
  • Satu set proses, {P1, P2, P3,. . , PN.}
  • Permintaan Tepi - Satu set busur diarahkan dari Pi ke Rj, menunjukkan bahwa proses Pi telah meminta Rj, dan saat ini sedang menunggu sumber daya yang menjadi tersedia.
  • Tugas Tepi - Satu set busur diarahkan dari Rj ke Pi menunjukkan bahwa sumber daya Rj telah dialokasikan untuk memproses Pi, dan Pi yang saat ini memegang sumber daya Rj.
  • Perhatikan bahwa tepi permintaan dapat diubah menjadi keunggulan tugas dengan membalik arah busur ketika permintaan tersebut dikabulkan. (Namun perhatikan juga bahwa tepi permintaan menunjuk ke kotak kategori, sedangkan tepi tugas berasal dari titik contoh khusus dalam kotak.)
  • Sebagai contoh:

• Jika grafik alokasi sumber daya tidak mengandung siklus, maka sistem tidak menemui jalan buntu. (Bila mencari siklus, ingatlah bahwa ini adalah grafik diarahkan.) Lihat contoh pada Gambar 7.2 di atas.
• Jika grafik alokasi sumber daya tidak mengandung siklus DAN setiap kategori sumber daya hanya berisi satu contoh, maka deadlock ada.
• Jika kategori sumber daya mengandung lebih dari satu contoh, maka kehadiran siklus dalam grafik alokasi sumber daya menunjukkan kemungkinan kebuntuan, namun tidak menjamin satu. Perhatikan, misalnya, Angka 7.3 dan 7.4 di bawah:

7.3 Metode Penanganan Deadlock

• Secara umum ada tiga cara penanganan deadlock:
  1. Deadlock pencegahan atau penghindaran - Jangan biarkan sistem untuk masuk ke negara buntu.
  2. Deadlock deteksi dan pemulihan - proses Batalkan atau mendahului beberapa sumber daya ketika deadlock terdeteksi.
  3. Abaikan masalah semua bersama-sama - Jika deadlock hanya terjadi sekali setahun atau lebih, mungkin lebih baik untuk hanya membiarkan mereka terjadi dan reboot diperlukan daripada mendatangkan overhead konstan dan hukuman kinerja sistem yang berhubungan dengan pencegahan atau deteksi kebuntuan. Ini adalah pendekatan yang baik Windows dan UNIX ambil.
• Untuk menghindari deadlock, sistem harus memiliki informasi tambahan tentang semua proses. Secara khusus, sistem harus tahu apa sumber daya proses akan atau dapat meminta di masa depan. (Mulai dari maksimum terburuk sederhana untuk permintaan sumber daya yang lengkap dan rencana rilis untuk setiap proses, tergantung pada algoritma tertentu.)
• Deteksi Deadlock cukup mudah, namun pemulihan kebuntuan membutuhkan baik proses batal atau sumber daya preempting, baik yang merupakan alternatif yang menarik.
• Jika deadlock tidak dicegah atau dideteksi, maka ketika terjadi kebuntuan sistem secara bertahap akan melambat, sebagai proses lebih dan lebih menjadi terjebak menunggu sumber daya saat ini dipegang oleh kebuntuan dan oleh proses menunggu lainnya. Sayangnya perlambatan ini dapat dibedakan dari perlambatan sistem umum ketika proses real-time memiliki kebutuhan komputasi yang berat.

7,4 Deadlock Pencegahan

• Deadlock dapat dicegah dengan mencegah setidaknya satu dari empat kondisi yang diperlukan:

7.4.1 Reksa Pengecualian

• Sumber daya bersama seperti read-only file tidak mengakibatkan deadlock.
• Sayangnya beberapa sumber daya, seperti printer dan tape drive, memerlukan akses eksklusif oleh suatu proses tunggal.

7.4.2 Tahan dan Tunggu

• Untuk mencegah hal ini proses kondisi harus dicegah dari memegang satu atau lebih sumber daya sekaligus menunggu untuk satu atau lebih orang lain. Ada beberapa kemungkinan untuk ini:
  • Mengharuskan semua proses meminta semua sumber daya pada satu waktu. Hal ini dapat menjadi boros sumber daya sistem jika suatu proses membutuhkan satu sumber daya di awal pelaksanaannya dan tidak memerlukan beberapa sumber daya lainnya sampai lama kemudian.
  • Mengharuskan proses memegang sumber daya harus membebaskan mereka sebelum meminta sumber daya baru, dan kemudian kembali mendapatkan sumber daya yang dirilis bersama dengan orang-orang baru dalam permintaan single baru. Hal ini dapat menjadi masalah jika suatu proses telah selesai sebagian operasi menggunakan sumber daya dan kemudian gagal untuk mendapatkannya kembali dialokasikan setelah melepaskannya.
  • Salah satu metode yang dijelaskan di atas dapat menyebabkan kelaparan jika suatu proses membutuhkan satu atau lebih sumber daya yang populer.

7.4.3 Preemption ada

• Preemption alokasi sumber daya dapat mencegah proses ini kondisi deadlock, bila mungkin.
  • Salah satu pendekatan adalah bahwa jika proses dipaksa untuk menunggu ketika meminta sumber daya baru, maka semua sumber lain yang sebelumnya dipegang oleh proses ini secara implisit dirilis, (mendahului), memaksa proses ini untuk kembali mendapatkan sumber daya yang tua bersama dengan sumber daya baru di satu permintaan, mirip dengan pembahasan sebelumnya.
  • Pendekatan lain adalah bahwa ketika sumber daya yang diminta dan tidak tersedia, maka sistem terlihat untuk melihat apa proses lainnya saat ini memiliki sumber daya dan diri mereka diblokir menunggu untuk beberapa sumber daya lainnya. Jika proses seperti itu ditemukan, maka beberapa sumber daya mereka mungkin akan mendahului dan ditambahkan ke daftar sumber daya yang proses sedang menunggu.
  • Salah satu dari pendekatan ini mungkin berlaku untuk sumber daya yang negara yang mudah disimpan dan dikembalikan, seperti register dan memori, tetapi umumnya tidak berlaku untuk perangkat lain seperti printer dan tape drive.

7.4.4 Edaran Tunggu

• Salah satu cara untuk menghindari menunggu melingkar ke nomor semua sumber daya, dan mengharuskan proses meminta sumber daya hanya dalam ketat meningkat (atau menurun) pesanan.
• Dengan kata lain, dalam rangka untuk meminta sumber daya Rj, proses harus terlebih dahulu melepaskan Ri semua sehingga i> = j.
• Salah satu tantangan besar dalam skema ini adalah menentukan urutan relatif dari sumber yang berbeda

7,5 Deadlock Penghindaran

• Gagasan umum di belakang menghindari kebuntuan adalah untuk mencegah kebuntuan dari yang pernah terjadi, dengan mencegah setidaknya satu dari kondisi tersebut.
• Ini membutuhkan informasi lebih lanjut tentang setiap proses, DAN cenderung menyebabkan pemanfaatan perangkat rendah. (Ie itu adalah pendekatan konservatif.)
• Dalam beberapa algoritma scheduler hanya perlu untuk mengetahui jumlah maksimum masing-masing sumber daya bahwa proses berpotensi digunakan. Dalam algoritma yang lebih kompleks scheduler juga dapat mengambil keuntungan dari jadwal sumber daya apa mungkin diperlukan dalam rangka apa.
• Ketika scheduler melihat bahwa mulai proses atau pemberian permintaan sumber daya dapat menyebabkan kebuntuan masa depan, maka proses tidak dimulai atau permintaan tidak dikabulkan.
• Sebuah negara alokasi sumber daya ditentukan oleh jumlah sumber daya yang tersedia dan dialokasikan, dan persyaratan maksimum dari semua proses dalam sistem.

7.5.1 Aman Negara

• Sebuah negara aman jika sistem dapat mengalokasikan seluruh sumber daya yang diminta oleh semua proses (sampai dengan maksimal mereka lain) tanpa memasuki keadaan deadlock.
• Lebih formal, negara aman jika ada urutan aman proses {P0, P1, P2, ..., PN} sedemikian rupa sehingga semua permintaan sumber daya untuk Pi dapat diberikan dengan menggunakan sumber daya yang saat ini dialokasikan ke Pi dan semua proses pj mana j <i. (Yaitu jika semua proses sebelum Pi selesai dan membebaskan sumber daya mereka, maka Pi akan mampu menyelesaikan juga, dengan menggunakan sumber daya yang mereka telah dibebaskan.)
• Jika urutan yang aman tidak ada, maka sistem dalam keadaan tidak aman, yang MUNGKIN menyebabkan kebuntuan. (Semua negara yang aman adalah kebuntuan gratis, tetapi tidak semua negara yang tidak aman menyebabkan deadlock.)

• Sebagai contoh, mempertimbangkan sistem dengan 12 tape drive, dialokasikan sebagai berikut. Apakah ini sebuah negara yang aman? Apa urutan aman?

	Maksimum Kebutuhan	Saat Alokasi
P0	10	5
P1	4	2
P2	9	2

• Apa yang terjadi pada tabel di atas jika permintaan P2 proses dan diberikan satu tape drive lebih?
• Kunci pendekatan keadaan aman adalah bahwa ketika permintaan dibuat untuk sumber daya, permintaan ini disetujui hanya jika negara alokasi yang dihasilkan adalah satu aman.

7.5.2 Sumber-Alokasi Grafik Algoritma

• Jika kategori sumber daya hanya memiliki satu contoh sumber daya mereka, maka menyatakan kebuntuan dapat dideteksi oleh siklus dalam alokasi sumber daya grafik.
• Dalam hal ini, negara-negara yang tidak aman dapat dikenali dan dihindari dengan menambah grafik alokasi sumber daya dengan tepi klaim, dicatat oleh garis putus-putus, yang menunjukkan dari proses untuk sumber daya yang dapat meminta di masa depan.
• Agar teknik ini untuk bekerja, semua tepi klaim harus ditambahkan ke grafik untuk setiap proses tertentu sebelum proses yang diizinkan untuk meminta sumber daya apapun. (Atau, proses hanya dapat membuat permintaan untuk sumber daya yang mereka telah menetapkan tepi klaim, dan tepi klaim tidak dapat ditambahkan ke setiap proses yang saat ini memegang sumber daya.)
• Ketika sebuah proses membuat permintaan, tepi klaim Pi-> Rj dikonversi menjadi ujung permintaan. Demikian pula bila sumber daya yang dirilis, tugas beralih kembali ke tepi klaim.
• Pendekatan ini bekerja dengan menyangkal permintaan yang akan menghasilkan siklus dalam grafik alokasi sumber daya, mengambil tepi klaim berlaku.
• Pertimbangkan misalnya apa yang terjadi ketika proses P2 R2 permintaan sumber daya:

• Grafik alokasi sumber daya yang dihasilkan akan memiliki siklus di dalamnya, sehingga permintaan tidak dapat dikabulkan.

7.5.3 Banker Algoritma

• Untuk kategori sumber daya yang mengandung lebih dari satu contoh metode grafik alokasi sumber daya tidak bekerja, dan lebih kompleks (dan kurang efisien) metode harus dipilih.
• Algoritma Banker mendapatkan namanya karena merupakan metode yang bankir bisa menggunakan untuk memastikan bahwa ketika mereka meminjamkan sumber daya mereka masih akan dapat memuaskan semua klien mereka. (Seorang bankir tidak akan meminjamkan sedikit uang untuk mulai membangun sebuah rumah kecuali mereka yakin bahwa mereka nantinya akan dapat meminjamkan sisa uang untuk menyelesaikan rumah.)
• Ketika proses dijalankan, maka harus menyatakan di muka alokasi sumber daya maksimum dapat disampaikan sampai dengan jumlah yang tersedia pada sistem.
• Ketika permintaan dibuat, scheduler menentukan apakah pemberian permintaan akan meninggalkan sistem dalam keadaan aman. Jika tidak, maka proses harus menunggu sampai permintaan tersebut dapat diberikan dengan aman.
• Algoritma bankir bergantung pada beberapa struktur data kunci: (dimana n adalah jumlah proses dan m adalah jumlah kategori sumber daya.)
  • Tersedia [m] menunjukkan berapa banyak sumber daya yang saat ini tersedia dari masing-masing jenis.
  • Max [n] [m] menunjukkan kebutuhan maksimum dari setiap proses dari setiap sumber daya.
  • Alokasi [n] [m] menunjukkan jumlah setiap kategori sumber daya yang dialokasikan untuk setiap proses.
  • Perlu [n] [m] menunjukkan sumber daya yang tersisa dibutuhkan dari setiap jenis untuk setiap proses. (Perhatikan bahwa Need [i] [j] = Max [i] [j] -. Alokasi [i] [j] untuk semua i, j)
• Untuk penyederhanaan diskusi, kita membuat notasi berikut / pengamatan:
  • Salah satu baris dari vektor Kebutuhan, Need [i], dapat diperlakukan sebagai vektor yang sesuai dengan kebutuhan proses i, dan juga untuk Alokasi dan Max.
  • Sebuah vektor X dianggap <= a Y vektor jika X [i] <= Y [i] untuk semua i.

7.5.3.1 Keamanan Algoritma

• Dalam rangka menerapkan algoritma Banker, pertama kita perlu sebuah algoritma untuk menentukan apakah atau tidak negara tertentu aman.
• Algoritma ini menentukan apakah kondisi saat ini sistem aman, sesuai dengan langkah-langkah berikut:
  1. Mari Bekerja dan Finish menjadi vektor dengan panjang m dan n masing-masing.
  • Kerja adalah salinan kerja sumber daya yang tersedia, yang akan diubah selama analisis.
  • Finish adalah vektor dari boolean yang menunjukkan apakah suatu proses tertentu bisa menyelesaikan. (Atau telah selesai sejauh ini dalam analisis.)
  • Inisialisasi Bekerja untuk Tersedia, dan Finish ke false untuk semua elemen.
  2. Cari i sehingga keduanya (A) Finish [i] == false, dan (B) Need [i] <Work. Proses ini belum selesai, tapi bisa dengan himpunan kerja yang tersedia. Jika tidak seperti saya ada, lanjutkan ke langkah 4.
  3. Set Kerja = Bekerja + Alokasi [i], dan set Finish [i] menjadi true. Hal ini sesuai untuk memproses saya menyelesaikan dan melepaskan sumber daya kembali ke dalam kolam kerja. Kemudian loop kembali ke langkah 2.
  4. Jika selesai [i] == true untuk semua i, maka negara adalah negara yang aman, karena urutan yang aman telah ditemukan.
• (Modifikasi JTB ini:
  1. Pada langkah 1. alih-alih membuat Selesai array boolean diinisialisasi ke false, membuat array int diinisialisasi ke 0. Juga menginisialisasi s int = 0 sebagai counter langkah.
  2. Pada langkah 2, carilah Finish [i] == 0.
  3. Pada langkah 3, mengatur Finish [i] untuk + + s. S adalah menghitung jumlah proses selesai.
  4. Untuk langkah 4, tes dapat Finish baik [i]> 0 untuk semua i, atau s> = n. Manfaat dari metode ini adalah bahwa jika keadaan aman ada, kemudian Finish [] menunjukkan satu urutan yang aman (dari mungkin banyak.))

7.5.3.2 Sumber-Permintaan Algoritma (Algoritma Bankers)

• Sekarang bahwa kita memiliki alat untuk menentukan apakah suatu negara tertentu aman atau tidak, kita sekarang siap untuk melihat algoritma Banker itu sendiri.
• Algoritma ini menentukan apakah permintaan baru aman, dan memberikan hanya jika aman untuk melakukannya.
• Ketika permintaan dibuat (yang tidak melebihi sumber daya yang tersedia), berpura-pura telah diberikan, dan kemudian melihat apakah negara yang dihasilkan adalah satu aman. Jika demikian, mengabulkan permintaan tersebut, dan jika tidak, menolak permintaan tersebut, sebagai berikut:
  1. Biarkan Request [n] [m] menunjukkan jumlah sumber daya dari masing-masing jenis saat diminta oleh proses. Jika Request [i]> Kebutuhan [i] untuk setiap proses i, meningkatkan kondisi kesalahan.
  2. Jika Request [i]> Tersedia untuk setiap proses i, maka proses itu harus menunggu sumber daya untuk menjadi tersedia. Jika proses tersebut dapat lanjutkan ke langkah 3.
  3. Periksa untuk melihat apakah permintaan dapat diberikan dengan aman, dengan berpura-pura telah diberikan dan kemudian melihat apakah negara yang dihasilkan aman. Jika demikian, mengabulkan permintaan tersebut, dan jika tidak, maka proses harus menunggu sampai permintaan tersebut dapat diberikan prosedur untuk pemberian safely.The permintaan (atau berpura-pura untuk tujuan pengujian) adalah:
     • Bersedia = - Permintaan
     • Alokasi Alokasi = + Permintaan
     • Perlu Kebutuhan = - Permintaan

7.5.3.3 Contoh Ilustrasi

• Perhatikan situasi berikut:

• Dan sekarang mempertimbangkan apa yang terjadi jika proses P1 permintaan 1 instance dari A dan 2 contoh C. (Permintaan [1] = (1, 0, 2))

• Bagaimana dengan permintaan (3, 3,0) oleh P4? atau (0, 2, 0) oleh P0? Hal tersebut dapat diberikan dengan aman? Mengapa atau mengapa tidak?

7,6 Deadlock Detection

• Jika deadlock tidak dihindari, maka pendekatan lain adalah untuk mendeteksi ketika mereka telah terjadi dan memulihkan entah bagaimana.
• Selain kinerja hit terus-menerus memeriksa untuk kebuntuan, kebijakan / algoritma harus berada di tempat untuk pulih dari kebuntuan, dan ada potensi kehilangan pekerjaan ketika proses harus dibatalkan atau memiliki sumber daya mereka mendahului.

7.6.1 tunggal Instance dari Setiap Jenis Sumber Daya

• Jika setiap kategori sumber daya memiliki satu contoh, maka kita dapat menggunakan variasi dari grafik alokasi sumber daya yang dikenal sebagai grafik menunggu-untuk.
• Menunggu-untuk grafik dapat dibangun dari grafik alokasi sumber daya dengan menghilangkan sumber daya dan runtuh tepi terkait, seperti yang ditunjukkan pada gambar di bawah.
• Busur dari Pi Pj ke dalam grafik menunggu-untuk menunjukkan bahwa proses Pi sedang menunggu sumber daya yang proses Pj saat ini memegang.

• Seperti sebelumnya, siklus dalam grafik menunggu untuk menunjukkan kebuntuan.
• Algoritma ini harus menjaga menunggu-untuk grafik, dan secara berkala mencari untuk siklus.

7.6.2 Beberapa Contoh Tipe Sumber Daya

• Algoritma deteksi diuraikan di sini pada dasarnya sama dengan algoritma Banker, dengan dua perbedaan halus:
  • Pada langkah 1, Algoritma Banker dandanan Finish [i] menjadi false untuk semua i. Algoritma yang disajikan di sini set Finish [i] menjadi false hanya jika Alokasi [i] tidak nol. Jika sumber daya saat ini dialokasikan untuk proses ini adalah nol, algoritma set Finish [i] menjadi true. Hal ini pada dasarnya mengasumsikan bahwa JIKA semua proses lain dapat menyelesaikan, maka proses ini dapat selesai juga. Selain itu, algoritma ini secara khusus mencari proses apa yang terlibat dalam situasi kebuntuan, dan proses yang tidak memiliki sumber daya yang dialokasikan tidak dapat terlibat dalam kebuntuan, sehingga dapat dihapus dari pertimbangan lebih lanjut.
  • Langkah 2 dan 3 tidak berubah
  • Pada langkah 4, Algoritma Banker dasar mengatakan bahwa jika Finish [i] == true untuk semua i, bahwa ada kebuntuan ada. Algoritma ini lebih spesifik, dengan menyatakan bahwa jika Finish [i] == false untuk setiap Pi proses, maka proses yang secara khusus terlibat dalam kebuntuan yang telah terdeteksi.
• (Catatan: Metode alternatif yang disajikan di atas, di mana Finish diadakan bilangan bulat bukan boolean vektor ini akan diinisialisasi ke semua nol, dan kemudian diisi dengan bilangan bulat meningkat sebagai proses terdeteksi yang bisa menyelesaikan Jika ada proses yang tersisa di nol saat.. algoritma selesai, maka ada jalan buntu, dan jika tidak, maka bilangan bulat dalam menyelesaikan menggambarkan urutan yang aman Untuk memodifikasi algoritma ini untuk mencocokkan bagian teks, proses dengan alokasi = nol bisa diisi dengan N, N. - 1, N - 2, dll pada langkah 1, dan setiap proses tersisa dengan Finish = 0 pada langkah 4 adalah proses buntu).
• Perhatikan, misalnya, negara berikut, dan menentukan apakah itu saat menemui jalan buntu:

• Sekarang anggaplah bahwa P2 proses membuat permintaan untuk sebuah contoh tambahan tipe C, menghasilkan negara yang ditunjukkan di bawah ini. Apakah sistem sekarang jalan buntu?

7.6.3 Deteksi-Algoritma Penggunaan

• Kapan sebaiknya deteksi kebuntuan harus dilakukan? Sering, jarang atau?
• Jawabannya mungkin tergantung pada seberapa sering kebuntuan diharapkan terjadi, serta kemungkinan konsekuensi tidak menangkap mereka segera. (Jika deadlock tidak segera dihapus ketika mereka terjadi, maka proses lebih dan lebih dapat "back up" balik kebuntuan, membuat tugas akhirnya blokir sistem lebih sulit dan mungkin merusak proses lebih.)
• Ada dua pendekatan yang jelas, masing-masing dengan trade-off:
  1. Melakukan deteksi kebuntuan setelah setiap alokasi sumber daya yang tidak dapat segera diberikan. Ini memiliki keuntungan untuk mendeteksi kebuntuan segera, sementara jumlah minimum proses yang terlibat dalam kebuntuan. (Orang mungkin menganggap bahwa proses yang memicu permintaan kondisi kebuntuan adalah "penyebab" dari kebuntuan, tapi realistis semua proses dalam siklus sama-sama bertanggung jawab atas kebuntuan yang dihasilkan.) Sisi bawah dari pendekatan ini adalah biaya overhead yang luas dan kinerja memukul disebabkan oleh memeriksa deadlock begitu sering.
  2. Melakukan deteksi kebuntuan hanya ketika ada beberapa petunjuk bahwa kebuntuan mungkin terjadi, seperti ketika utilisasi CPU mengurangi sampai 40% atau angka ajaib lainnya. Keuntungannya adalah bahwa deteksi kebuntuan dilakukan lebih jarang, tapi sisi bawah adalah bahwa hal itu menjadi mustahil untuk mendeteksi proses yang terlibat dalam kebuntuan aslinya, sehingga pemulihan kebuntuan dapat lebih rumit dan merusak proses lebih.
  3. (Saat saya menulis ini, alternatif ketiga datang ke pikiran: Buatlah catatan sejarah alokasi sumber daya, sejak saat itu terakhir yang diketahui tidak ada deadlock Apakah cek kebuntuan berkala (setelah satu jam atau ketika penggunaan CPU rendah), dan kemudian menggunakan.? log historis untuk melacak melalui dan menentukan kapan kebuntuan terjadi dan apa yang menyebabkan kebuntuan proses awal Sayangnya saya tidak yakin bahwa memecahkan kebuntuan asli maka akan membebaskan kemacetan log yang dihasilkan..)

7,7 Pemulihan Dari Deadlock

• Ada tiga pendekatan dasar untuk pemulihan dari kebuntuan:
  1. Menginformasikan operator sistem, dan memungkinkan dia / dia untuk mengambil intervensi manual.
  2. Hentikan satu atau lebih proses yang terlibat dalam kebuntuan
  3. Mendahului sumber daya.

7.7.1 Proses Pemutusan

• Dua dasar pendekatan, baik yang memulihkan sumber daya yang dialokasikan untuk proses dihentikan:
  • Menghentikan semua proses yang terlibat dalam kebuntuan. Ini pasti memecahkan kebuntuan, tetapi dengan mengorbankan mengakhiri proses lebih akan benar-benar diperlukan.
  • Menghentikan proses satu per satu sampai kebuntuan rusak. Ini lebih konservatif, tetapi membutuhkan melakukan deteksi kebuntuan setelah setiap langkah.
• Dalam kasus terakhir ada banyak faktor yang bisa masuk ke memutuskan untuk mengakhiri proses selanjutnya:
  1. Proses prioritas.
  2. Berapa lama proses telah berjalan, dan seberapa dekat itu adalah untuk menyelesaikan.
  3. Berapa banyak dan apa jenis sumber daya adalah proses holding. (Apakah mereka mudah untuk mendahului dan memulihkan?)
  4. Berapa banyak sumber daya yang proses perlu untuk menyelesaikan.
  5. Berapa banyak proses perlu dihentikan
  6. Apakah proses yang interaktif atau batch.
  7. (Apakah atau tidak proses telah membuat non-restorable perubahan sumber daya apapun.)

7.7.2 Sumber Daya Preemption

• Ketika sumber daya preempting untuk meringankan kebuntuan, ada tiga isu penting yang akan dibahas:
  1. Memilih korban - Memutuskan mana sumber daya untuk mendahului dari mana proses melibatkan banyak kriteria keputusan yang sama yang diuraikan di atas.
  2. Rollback - Idealnya satu ingin memutar kembali proses yang mendahului ke keadaan aman sebelum titik di mana sumber daya yang pada awalnya dialokasikan untuk proses. Sayangnya hal itu bisa sulit atau tidak mungkin untuk menentukan apa keadaan yang aman, dan jadi rollback hanya aman adalah untuk memutar kembali semua jalan kembali ke awal. (Ie membatalkan proses dan membuatnya memulai lagi.)
  3. Kelaparan - Bagaimana Anda menjamin bahwa proses tidak akan kelaparan karena sumber daya yang terus-menerus mendahului? Salah satu pilihan akan menggunakan sistem prioritas, dan meningkatkan prioritas proses setiap kali mendapatkan sumber daya mendahului. Akhirnya harus mendapatkan prioritas yang cukup tinggi sehingga tidak akan mendahului lagi.

7,8 Ringkasan

sumber : http://translate.google.com/translate?hl=id&langpair=en|id&u=http://www1bpt.bridgeport.edu/sed/projects/cs503/Spring_2001/kode/os/deadlock.htm