DBMS - Kebuntuan
Dalam sistem multi-proses, kebuntuan adalah situasi yang tidak diinginkan yang muncul dalam lingkungan sumber daya bersama, di mana proses menunggu sumber daya yang ditahan oleh proses lain tanpa batas waktu.
Misalnya, asumsikan satu set transaksi {T 0 , T 1 , T 2 , ..., T n }. T 0 membutuhkan sumber daya X untuk menyelesaikan tugasnya. Sumber daya X dipegang oleh T 1 , dan T 1 menunggu sumber daya Y, yang dipegang oleh T 2 . T 2 menunggu resource Z, yang dipegang oleh T 0 . Dengan demikian, semua proses menunggu satu sama lain untuk melepaskan sumber daya. Dalam situasi ini, tidak ada proses yang dapat menyelesaikan tugasnya. Situasi ini dikenal sebagai kebuntuan.
Kebuntuan tidak sehat untuk sistem. Jika sistem terjebak dalam kebuntuan, transaksi yang terlibat dalam kebuntuan akan dibatalkan atau dimulai ulang.
Pencegahan Kebuntuan
Untuk mencegah situasi kebuntuan dalam sistem, DBMS secara agresif memeriksa semua operasi, di mana transaksi akan dieksekusi. DBMS memeriksa operasi dan menganalisis apakah mereka dapat menciptakan situasi kebuntuan. Jika ditemukan bahwa situasi kebuntuan mungkin terjadi, maka transaksi tersebut tidak pernah diizinkan untuk dieksekusi.
Ada skema pencegahan kebuntuan yang menggunakan mekanisme pemesanan stempel waktu dari transaksi untuk menentukan situasi kebuntuan.
Skema Tunggu Mati
Dalam skema ini, jika transaksi meminta untuk mengunci sumber daya (item data), yang sudah dipegang dengan kunci yang bertentangan oleh transaksi lain, maka salah satu dari dua kemungkinan dapat terjadi -
Jika TS (T i ) <TS (T j ) - yaitu T i , yang meminta kunci yang bentrok, lebih tua dari T j - maka T i diizinkan untuk menunggu hingga item data tersedia.
Jika TS (T i )> TS (t j ) - yaitu T i lebih muda dari T j - maka T i mati. T i akan dimulai ulang nanti dengan penundaan acak tetapi dengan stempel waktu yang sama.
Skema ini memungkinkan transaksi yang lebih tua untuk menunggu tetapi membunuh yang lebih muda.
Skema Tunggu Luka
Dalam skema ini, jika transaksi meminta untuk mengunci sumber daya (item data), yang telah ditahan dengan kunci yang bertentangan oleh beberapa transaksi lain, salah satu dari dua kemungkinan dapat terjadi -
Jika TS (T i ) <TS (T j ), maka T i memaksa T j untuk digulung kembali - yaitu T i luka T j . T j dimulai kembali nanti dengan penundaan acak tetapi dengan stempel waktu yang sama.
Jika TS (T i )> TS (T j ), maka T i terpaksa menunggu hingga resource tersedia.
Skema ini, memungkinkan transaksi yang lebih muda untuk menunggu; tetapi ketika transaksi yang lebih lama meminta barang yang dipegang oleh yang lebih muda, transaksi yang lebih lama memaksa yang lebih muda untuk membatalkan dan melepaskan barang tersebut.
Dalam kedua kasus tersebut, transaksi yang memasuki sistem pada tahap selanjutnya dibatalkan.
Penghindaran Kebuntuan
Membatalkan transaksi tidak selalu merupakan pendekatan praktis. Sebagai gantinya, mekanisme penghindaran kebuntuan dapat digunakan untuk mendeteksi situasi kebuntuan sebelumnya. Metode seperti "grafik tunggu" tersedia tetapi hanya cocok untuk sistem yang transaksinya ringan memiliki lebih sedikit contoh sumber daya. Dalam sistem yang besar, teknik pencegahan kebuntuan dapat bekerja dengan baik.
Grafik Tunggu
Ini adalah metode sederhana yang tersedia untuk melacak jika ada situasi kebuntuan yang mungkin muncul. Untuk setiap transaksi yang masuk ke dalam sistem, sebuah node dibuat. Ketika transaksi T i meminta kunci pada suatu item, katakanlah X, yang ditahan oleh beberapa transaksi lain T j , tepi terarah dibuat dari T i ke T j . Jika T j melepaskan item X, tepi di antara mereka dijatuhkan dan T i mengunci item data.
Sistem mempertahankan grafik tunggu ini untuk setiap transaksi yang menunggu beberapa item data dipegang oleh orang lain. Sistem terus memeriksa apakah ada siklus dalam grafik.
Di sini, kita dapat menggunakan salah satu dari dua pendekatan berikut -
Pertama, jangan izinkan permintaan apa pun untuk item, yang sudah dikunci oleh transaksi lain. Ini tidak selalu dapat dilakukan dan dapat menyebabkan kelaparan, di mana transaksi tanpa batas waktu menunggu item data dan tidak akan pernah bisa mendapatkannya.
Opsi kedua adalah membatalkan salah satu transaksi. Tidak selalu mungkin untuk membatalkan transaksi yang lebih muda, karena mungkin penting daripada yang lama. Dengan bantuan beberapa algoritma relatif, sebuah transaksi dipilih, yang akan dibatalkan. Transaksi ini dikenal sebagaivictim dan prosesnya dikenal sebagai victim selection.