Deadlock adalah suatu
kondisi dimana dua proses atau lebih tidak dapat meneruskan eksekusinya oleh
pemroses. Pada umumnya deadlock terjadi karena proses mengalami startvation,
yaitu suatu job yang sedang dieksekusi dan eksekusi job tersebut tidak ada
hentinya, tidak diketahui kapan berhentinya proses tersebut atau bahkan job
yang antri bisa dikatakan mempunyai status mati, padahal proses-proses lain
sedang menunggu sumber daya proses.
Deadlock merupakan
kondisi terparah karena banyak proses dapat terlibat dan semuanya tidak dapat
mengakhiri prosesnya secara benar.
a.
Resource
Sistem operasi di sini
berperan sebagai pengatur berbagai tipe resource yang
berlainan, krena pada dasarnya proses-proses maupun job-job tersebut ingin
mengakses resource yang sama.
berlainan, krena pada dasarnya proses-proses maupun job-job tersebut ingin
mengakses resource yang sama.
Shareable resource
misalnya printer, tape drive.
b.
Karakteristik
Deadlock
Kondisi
yang dapat menimbulkan terjadinya deadlock:
- Mutual exclusion. Apabila proses telah menggunakan suatu resource, mka tidak boleh ada proses lain yang menggunakan resource tsb. Hanya satu proses yang dapat menggunakan sebuah resource pada satu waktu.
- Hold & Wait. Pada suatu proses sedang mengakses suatu resource, proses tsb dapat meminta ijin untuk mengakses resource lain yang dipakai oleh proses lain.
- No Preemption. Jika suatu proses meminta ijin untuk mengakses resource, sementara resource tersebut tidak tersedia, maka permintaan ijin tidak dapat dibatalkan.
- Circular Wait Condition. Jika proses P0 sedang mengakses Resource R1 dan minta ijin untuk mengakses resource R1 dan minta ijin untuk mengakses resource R2, dan pada saat yang bersamaan P1 sedang mengakses resource R2 dan mint ijin untuk mengakses R1.
Metode Mengendalikan Deadlock
- Menggunakan suatu protokol untuk meyakinkan bahwa sistem tidak akan pernah mengalami deadlock.
- Mengijinkan sistem mengalami deadlock, namun kemudian harus segera dapat memperbaikinya.
- Mengabaikan semua masalah dan menganggap deadlock tidak akan pernah terjadi lagi di dalam sistem.
Strategi untuk menghadapi deadlock dapat dibagi menjadi tiga
pendekatan, yaitu:
a.
Mengabaikan
adanya deadlock.
b.
Memastikan
bahwa deadlock tidak akan pernah ada, baik
dengan metode Pencegahan, dengan mencegah empat kondisi deadlock agar tidak akan pernah terjadi. Metode Menghindari deadlock, yaitu mengizinkan empat kondisi deadlock, tetapi
menghentikan setiap proses yang kemungkinan mencapai deadlock.
c.
Membiarkan
deadlock untuk terjadi, pendekatan ini
membutuhkan dua metode yang saling
mendukung, yaitu:
- Pendeteksian deadlock, untuk
mengidentifikasi ketika deadlock terjadi.
- Pemulihan deadlock, mengembalikan
kembali sumber daya yang dibutuhkan pada proses yang memintanya.
Pencegahan Deadlock
1.
Mutual exclusion.
Harus tetap menjaga
resource-resource yang bersifat non-shareable. Yaitu, proses menahan sebuah
resource, proses lain yang meminta resource tsb harus menunggu sampai proses
melepaskannya. Jika terjadi pada perangkat I/O dan berkas, maka sulit untuk
menghindari mutual exclusion pada sumber daya non shareable.
2.
Hold & Wait.
Apabila suatu proses
minta ijin untuk mengakses suatu resource, maka proses tersebut tidak boleh
membawa resource yang lainnya. Sebleum proses meminta resource, maka harus
melepas semua resource yang dibawa.
3.
Non Preemption.
Jika suatu proses minta
ijin mengakses resource, sementara resource tersebut tidak dapat dipenuhi
secepatnya, maka proses tersebut harus membebaskan semua resourcenya terlebih
dahulu.
4.
Circular Wait.
Memberi nomor pada setiap
resource yang ada, dan setiap resource hanya boleh mengakses resource2 secara
berurutan.
5.
Untuk
menghindari deadlock ikuti prinsip preemptive.
Tabel.
Deadlock
|
Syarat
|
Langkah
|
Kelemahan
|
|
Mutual
Exclusion
|
Spooling
sumber daya
|
Dapat
menyebabkan chaos
|
|
Hold and Wait
|
Meminta sumber
daya di awal
|
Sulit
memperkirakan di awal dan tidak optimal
|
|
No Pre-emptive
|
Mengambil
sumber daya di tengah proses
|
Hasil proses
tidak akan baik
|
|
Circular Wait
|
Penomoran
permintaan sumber daya
|
Tidak ada
penomoran yang memuaskan semua pihak
|
6.
Penghindaran Deadlock
1. State Selamat
Contoh :
Pada sistem dengan 10
sumber daya setipe, proses A memerlukan sumber daya maksimum sebanyak 10,
sedang saat ini menggenggam 2. Proses B memerlukan sumber daya maksimum
sebanyak 3, sedang saat ini menggenggam 1. Proses C memerlukan sumber daya
maksimum sebanyak 7, sedang saat ini menggenggam 3. Maka, masih tersedia 4
sumber daya.
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
2
|
10
|
|
B
|
1
|
3
|
|
C
|
3
|
7
|
|
|
Tersedia 4
|
|
Dengan hati-hati, sistem
penjadwalan ini dapat terhindarkan dari deadlock, dengan cara sbb:
Langkah
1 :
Alokasikan 4 sumber daya
ke proses C sehingga sumber daya yang tersedia tinggal 1 dan nantikan sampai
proses C berakhir.
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
2
|
10
|
|
B
|
1
|
3
|
|
C
|
7
|
7
|
|
|
Tersedia 0
|
|
Maka
setelah proses C selesai dan menjadi :
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
2
|
10
|
|
B
|
1
|
3
|
|
C
|
0
|
0
|
|
|
Tersedia 7
|
|
Langkah
2 :
Alokasikan 2 sumber daya ke proses B, nantikan proses B
sampai berakhir.
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
2
|
10
|
|
B
|
3
|
3
|
|
C
|
0
|
0
|
|
|
Tersedia 5
|
|
Maka, setelah proses B selesai dan menjadi:
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
2
|
10
|
|
B
|
0
|
0
|
|
C
|
0
|
0
|
|
|
Tersedia 8
|
|
Langkah
3:
Alokasikan 8 sumber daya ke proses A, nantikan proses A
sampai berakhir.
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
10
|
10
|
|
B
|
0
|
0
|
|
C
|
0
|
0
|
|
|
Tersedia 0
|
|
Maka,
setelah proses A selesai dan menjadi :
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
0
|
0
|
|
B
|
0
|
0
|
|
C
|
0
|
0
|
|
|
Tersedia 0
|
|
Maka,
ketiga proses tersebut dengan penjadwalan hati-hati dapat menyelesaikan proses
mereka dengan sempurna.
2.
State Tak Selamat (unsafe state)
State dikatakan sebagai
state tak selamat jika tidak terdapat cara untuk memenuhi semua permintaan yang
saat ini ditunda dengan menjalankan proses-proses dengan suatu urutan.
Contoh
Soal di bawah ini adalah
seperti soal pada state selamat, sate ini dapat berubah menjadi state tak
selamat bila alokasi sumber daya tak terkendali.
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
2
|
10
|
|
B
|
1
|
3
|
|
C
|
3
|
7
|
|
|
Tersedia 4
|
|
State tersebut dapat
menjadi state tak selamat bila:
- dua permintaan sumber daya oleh
proses A dilayani, kemudian
- Permintaan satu sumber daya oleh
proses B dilayani
Maka state menjadi:
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
4
|
10
|
|
B
|
2
|
3
|
|
C
|
3
|
7
|
|
|
Tersedia 1
|
|
Tabel di atas adalah
state tak selamat. Pada state ini tidak terdapat barisan pengalokasian yang dapat
membuat semua proses selesai. Misalnya, barisan pengalokasian yang ditempuh
adalah:
Langkah 1:
Alokasikan satu sumber
daya ke proses B sehingga sumber daya tersedia tinggal 1 dan nantikan sampai
proses B berakhir.
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
4
|
10
|
|
B
|
3
|
3
|
|
C
|
3
|
7
|
|
|
Tersedia 0
|
|
Maka, setelah proses B selesai dan
menjadi:
|
Proses
|
Jumlah Resource digenggam
|
Maksimum Resource yang dibutuhkan
|
|
A
|
4
|
10
|
|
B
|
0
|
-
|
|
C
|
3
|
7
|
|
|
Tersedia 3
|
|
Saat hanya tersedia tiga
sumber daya sementara dua proses yang sedang aktif masing-masing membutuhkan 6
dan 4 sumber daya.
Perlu diingat!, bahwa
state tak selamat bukan berarti deadlock, hanya menyatakan bahwa state tersebut
memiliki kemungkinan deadlock.
Gambar 2. Safe Sumber Bahan Kuliah IKI-20230 oleh Gabungan Kelompok
Kerja 21–28 IKI-20230 Semester Genap 2002/2003
Mendeteksi Deadlock
dan Memulihkan Deadlock
Metode ini mengunakan pendekatan dengan teknik untuk
menentukan apakah deadlock sedang terjadi serta proses-proses dan sumber
daya yang terlibat dalam deadlock tersebut. Setelah kondisi deadlock
dapat dideteksi, maka langkah pemulihan dari kondisi deadlock dapat
segera dilakukan. Langkah pemulihan tersebut adalah dengan memperoleh sumber
daya yang diperlukan oleh proses-proses yang membutuhkannya. Beberapa cara
digunakan untuk mendapatkan sumber daya yang diperlukan, yaitu dengan terminasi
proses dan pre-emption (mundur) suatu proses. Metode ini banyak
digunakan pada komputer mainframe berukuran besar.
a.
Terminasi Proses
Metode ini akan menghapus proses-proses yang terlibat pada kondisi deadlock
dengan mengacu pada beberapa syarat. Beberapa syarat yang termasuk dalam metode
ini adalah, sebagai berikut:
- Menghapus semua proses yang terlibat dalam kondisi deadlock (solusi ini terlalu mahal).
- Menghapus satu persatu proses yang terlibat, sampai kondisi deadlock dapat diatasi (memakan banyak waktu).
- Menghapus proses berdasarkan prioritas, waktu eksekusi, waktu untuk selesai, dan kedalaman dari rollback.
b.
Resources Preemption
Metode ini lebih menekankan kepada bagaimana menghambat suatu proses dan
sumber daya, agar tidak terjebak pada unsafe condition. Beberapa
langkahnya, yaitu:
- Pilih salah satu - proses dan sumber daya yang akan di-preempt.
- Rollback ke safe state yang sebelumnya telah terjadi.
- Mencegah suatu proses agar tidak terjebak pada starvation karena metode ini
2.
STARTVATION
Startvation adalah
keadaan dimana pemberian akses bergantian terus menerus, dan ada suatu proses
yang tidak mendapatkan gilirannya. Juga dapat dimaksudkan bahwa kondisi bila
beberapa proses-proses menunggu alokasi sumber daya sampai tak berhingga,
sementara proses-proses lain dapat memperoleh alokasi sumber daya.
Hal ini disebabkan bias
pada kebijaksanaan atau strategi alokasi sumber daya. Kondisi seperti ini harus
dihindari pada sistem operasi karena tidak adil, tapi dikehendaki penghindaran
dilakukan seefisien mungkin. Penanganan ini merupakan persoalan yang sulit untuk
menemukan kriteria yang benar, adil dan efesien dalam suatu strategi Sistem
Operasi.
Perhatikan contoh berikut:
c.
terdapat
tiga proses, P1, P2, dan P3.
d.
P1,
P2 dam P3 memerlukan pengaksesan sumber daya R secara periodik.
Skenario berikut terjadi:
e.
P1
sedang diberi sumber daya R, P2 dan P3 blocked menunggu sumber daya R.
f.
Ketika
P1 keluar dari critical section, P2 dan P3 diijinkan mengakses R.
g.
Asumsi
P3 diberi hak akses. Kemudian setelah selesai, hak akses kembali diberikan ke
P1 yang satu itu kembali membutuhkan sumber daya R.
Jika pemberian hak akses bergantian terus menerus antara P1
dan P3, maka P2 tidak pernah memperoleh pengaksesan sumber daya R, meski tidak
ada deadlock. Pada situasi ini, P2 mengalami situasi yang disebut dengan
startvation.
DAFTAR PUSTAKA
Ø Sistem
Operasi, SP Hariningsih, Penerbit
Graha Ilmu 2003.
Ø Silberschatz, A., Gagne, G. dan Galvin, P., "Applied
Operating System Concept", John Wiley and Sons Inc., 2000
Ø Hariyanto, B.,"Sistem Operasi", Bandung:
Informatika, Desember 1997
Ø Tanenbaum, Andrew S., "Modern Operating
Systems", Englewood Cliffs, New Jersey: Prentice-Hall Inc., 1992
Ø Coffman, E.G., Jr., M.J. Elphick dan A. Shoshani,
"System Deadlocks", Computing surveys, Vol.3, No.2, June 1971
Ø WWW.Google.com
0 komentar:
Posting Komentar