Menghindari Deadlock Pada Sistem Operasi Abas Ali Pangera, Dony Ariyus, Jurusan Teknik Informatika, STMIK AMIKOM Yogyakarta, Jl. Ring Road Utara, Condong Catur, Sleman, Yogyakarta - Indonesia Metode alternatif untuk menghindari deadlock adalah digunakan informasi tambahan tentang bagaimana sumber daya diminta. Misalnya pada sistem dengan satu 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. Model yang sederhana dan sangat penting dibutuhkan adalah setiap proses menentukan jumlah maksimum sumber daya dari setiap tipe yang mungkin diperlukan. Algoritma deadlock avoidance secara dinamis memeriksa status sumber daya yang dialokasikan untuk menjamin tidak pernah terjadi kondisi menunggu sirkular. Status alokasi sumber daya ditentukan oleh jumlah sumber daya yang tersedia dan yang dialokasikan dan maksimum permintaan oleh proses-proses. Untuk penghindaran deadlock diperlukan pengertian mengenai state selamat (safe state) dan state tak selamat (unsafe state). State Selamat (Safe State) Ketika suatu proses meminta sumber daya yang tersedia, sistem harus menentukan apakah alokasi sumber daya pada proses mengakibatkan sistem dalam state selamat. Sistem dikatakan dalam state selamat jika sistem dapat mengalokasikan sumber daya untuk setiap proses secara berurutan dan menghindari deadlock. Urutan proses
selamat jika untuk setiap Pi, sumber daya yang masih diminta Pi masih memenuhi sumber daya yang tersedia dan sumber daya yang 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 dapan memperoleh sumber daya yang diperlukan, mengeksekusi, mengembalikan sumber daya yang dialokasikan dan terminasi. Ketika Pi selesai, Pi+1 dapat memperoleh sumber daya yang diperlukan dan seterusnya. Jika sistem dalam state selamat maka tidak terjadi deadlock, sedangkan jika sistem dalam state tidak selamat (unsafe state) maka kemungkinan terjadi deadlock seperti Gambar 8-7. Metode menghindari deadlock menjamin bahwa sistem tidak pernah memasuki state tidak selamat.
Ruang State Selamat, Tak Selamat dan Deadlock Untuk menggambarkan sistem dapat berpindah dari state selamat ke state tidak selamat dapat dilihat ilustrasi berikut ini. Misalnya sistem mempunyai 12 magnetic tape drive dan 3 proses P0, P1 dan P2. Proses P0 membutuhkan 10 tape drive, proses P1 membutuhkan 4 dan proses P2 membutuhkan 9 tape drive. Misalnya pada waktu t0, proses P0 membawa 5 tape drive, P1 membawa 2 dan P2 membawa 2 tape drive sehingga terdapat 3 tape drive yang tidak digunakan.
Pada waktu t0, sistem dalam state selamat. Urutan < P1, P0, P2> memenuhi kondisi selamat karena P1 dapat segera dialokasikan semua tape drive dan kemudian mengembalikan semua tape drive sehingga sistem tersedia 5 tape drive. Kemudian P0 dapat memperoleh semua tape drive dan mengembalikan semua sehingga sistem tersedia 10 tape drive dan terakhir proses P2 dapat memperoleh semua tape drive dan mengembalikan semua tape drive sehingga system tersedia 12 tape drive. Sistem dapat berubah dari state selamat ke state tidak selamat. Misalnya pada waktu t1, proses P2 meminta tambahan alokasi 1 tape drive. Sistem menjadi tidak selamat. Pada saat ini, hanya proses P1 yang mendapatkan semua tape drive dan kemudian mengembalikan semua tape drive sehingga hanya tersedia 4 tape drive. Karena proses P0 sudah dialokasikan 5 tape drive tetapi membutuhkan maksimum 10 tape drive sehingga meminta 5 tape drive lagi. Karena tidak tersedia, proses P0 harus menunggu demikian juga P2 sehingga system menjadi deadlock. Algoritma Resource Allocation Graph Untuk menghindari deadlock pada sistem yang hanya mempunyai satu anggota untuk setiap tipe sumber daya, dapat digunakan algoritma resource allocation graph. Claim edge Pi → Rj menandakan bahwa proses Pi mungkin meminta sumber daya Rj yang direpresentasikan dengan garis putus-putus.
Claim edge akan berubah ke request edge bila proses meminta sumber daya. Bila sumber daya dibebaskan oleh proses, assignment edge diubah ke claim edge. Sumber daya sebelumnya harus diklaim pada sistem. Sehingga sebelum proses Pi mulai dieksekusi, semua claim edge harus muncul pada resource allocation graph. Misalnya proses Pi meminta sumber daya Rj. Permintaan dapat dipenuhi hanya jika mengubah request edge Pi → Rj ke assignment edge Rj → Pi tidak menyebabkan siklus pada graph. Jika tidak terdapat siklus, maka alokasi sumber daya menyebabkan sistem dalam state selamat. Jika terjadi siklus, maka alokasi akan membawa sistem pada state tak selamat. Sehingga proses Pi harus menunggu permintaan dipenuhi.
Menghindari Deadlock dengan Agoritma Resouce Allocation Graph Untuk menggambarkan algoritma ini, perhatikan resource allocation graphs Gambar 8-8. Misalnya P2 meminta R2. Meskipun R2 bebas, tetapi tidak dapat dialokasikan untuk P2, karena akan menyebabkan siklus pada graph (Gambar 8-9). Siklus menandakan sistem dalam state tak selamat. Jika P1 meminta R2 dan P2 meminta R1, maka terjadi deadlock.
State Tak Selamat Pada Resouce Allocation Graph
Algoritma Banker Algoritma resource allocation graph tidak dapat diaplikasikan pada sistem yang mempunyai beberapa anggota pada setiap tipe sumber daya. Setiap proses sebelum dieksekusi harus menentukan jumlah sumber daya maksimum yang dibutuhkan. Jika suatu proses meminta sumber daya kemungkinan proses harus menunggu. Jika suatu proses mendapatkan semua sumber daya maka proses harus mengembalikan semua sumber daya dalam jangka waktu tertentu. Struktur data yang digunakan untuk mengimplementasikan algoritma Banker akan menentukan state dari sumber daya yang dialokasikan oleh sistem. Misalnya n = jumlah proses dan m = jumlah tipe resource. Struktur data yang diperlukan : • Available : Vektor panjang m. Jika Available[j] = k, terdapat k anggota tipe sumber daya Rj yang tersedia. • Max : matrik n x m. Jika Max[i, j] = k, maka proses Pi meminta paling banyak k anggota tipe resource Rj. • Allocation : matrik n x m. Jika Allocation[i, j] = k maka Pi sedang dialokasikan k anggota tipe resource Rj. • Need : matrik n x m. Jika Need[i, j] = k, maka Pi membutuhkan k anggota tipe resource Rj untuk menyelesaikan task. Need[i, j] = Max[i, j] – Allocation[i, j]. Beberapa notasi yang perlu diketahui adalah misalnya X dan Y adalah vector dengan panjang n. X ≤ Y jika dan hanya jika X[i] ≤ Y[i] untuksemua i = 1, 2, .., n. Sebagai contoh jika X = (1, 7, 3, 2) dan Y = (0, 3, 2, 1) maka Y ≤ X. Contoh Banker’s Algorithm Terdapat 5 proses P0 melalui P4; 3 resource types A, (10 instances), B (5instances, dan C (7 instances). Snapshot pada waktu T0: Allocation Max Available Proses
Allocation
Max
Available
A
B
C
A
B
C
A
B
C
P0
0
1
0
7
5
3
3
3
2
P1
2
0
0
3
2
2
P2
3
0
2
9
0
2
P3
2
1
1
2
2
2
P4
0
0
2
4
3
3
Need dikenal sebagai Max – Allocation, Isi dari matriks
Sistem dalam safe state karena urutan < P1, P3, P4, P2, P0> sesuai dengan safety criteria Contoh P1 Requst (1, 0, 2) Memeriksa bahwa Request, Available (adalah, (1, 0, 2) ((3, 3, 2)), true. Allocation Need Available Proses
Allocation
Need
Available
A
B
C
A
B
C
A
B
C
P0
0
1
0
7
4
3
2
3
0
P1
2
0
0
0
2
0
P2
3
0
2
6
0
0
P3
2
1
1
0
1
1
P4
0
0
2
4
3
1
Mengeksekusi safety algorithm yang menunjuk urutan < P1, P3, P4, P0, P2> sesuai dengan safety requirement. Dapat meminta untuk (3, 3, 0) yang diterima oleh P4? Dapat meminta untuk (0, 2, 0) yang diterima oleh P0? Kelemahan Algoritma Banker Kelemahan algoritma banker adalah sebagai berikut: • Proses-proses jarang mengetahui di awal proses jumlah maksimum sumber daya yang akan diperlukan • Jumlah proses tidak tetap, secara dinamis beragam begitu user baru login dan logout • Sumber daya yang dihitung sebagai tersedia dapat saja tiba0tiba ditinggalkan sehingga sebenarnya menjadi tidak tersedia • Proses-proses harus independent, yaitu urutan proses-proses dieksekusi tidak dibatasi kebutuhan sinkronisasi antar proses • Algoritma menghendaki memberikan semua permintaan selama waktu yang berhingga • Algoritma menghendaki client-client mengembalikan sumber daya setelah suatu waktu yang berhingga Algoritma Safety Algoritma ini untuk menentukan apakah sistem berada dalam state selamat atau tidak. a. Work dan Finish adalah vector dengan panjang m dan n. Inisialisasi : Work = Available dan Finish[i] = false untuk i = 1,3, …, n.
b. Cari i yang memenuhi kondisi berikut : • Finish [i] = false • Needi ≤ Work Jika tidak terdapat i ke langkah 4. c. Work = Work + Allocationi • Finish[i] = true • Kembali ke langkah 2. d. Jika Finish [i] == true untuk semua i, maka sistem dalam state selamat. Algoritma Resouce Request Requesti adalah vector permintaan untuk proses Pi. Jika Requesti[j] = k, maka proses Pi menginginkan k anggota tipe sumber daya Rj. Jika permintaan untuk sumber daya dilakukan oleh proses Pi berikut ini algoritmanya. Request = request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of resource type Rj. 1. Jika Requesti ≤ Needi ke langkah 2. Selain itu, terjadi kondisi error karena proses melebihi maksimum klaim. 2. Jika Requesti ≤ Available, ke langkah 3. Selain itu Pi harus menunggu karena sumber daya tidak tersedia. 3. Alokasikan sumber daya untuk Pi dengan modifikasi state berikut : Available = Available - Requesti; Allocationi = Allocationi + Requesti; Needi = Needi – Requesti; Jika hasil state alokasi sumber daya adalah selamat, maka sumber daya dialokasikan ke Pi , sebaliknya jika tidak selamat, Pi harus menunggu dan state alokasi sumber daya yang lama disimpan kembali. Daftar Pustaka Ariyus,Dony,2006, “Computer Security”, Andi Offset, Yogyakarta Ariyus, Dony,2005,” kamus hacker”, Andi offset, Yogyakarta Bob DuCharme, 2001,” The Operating System Handbook or, Fake Your Way Through Minis and Mainframes” Singapore: McGraw-Hill Book Co Bill Venners.1998. “Inside the Java Virtual Machin”e . McGraw-Hill. Deitel, Harvey M, 2004 “ operating systems” 3th Edition, Massachusetts: Addison-Wesley Publshing Company Gary B. Shelly, 2007, ”Discovering Computers: Fundamentals” Thomson Gollmann, Dieter,1999 “Computer Security” Jhon Willey & Son Inc, Canada
Grosshans,D. 1986,” File system: design and implementation”, Englewwod Cliffs, New Jersey : Prentice-Hall Inc. Harvey M Deitel dan Paul J Deitel. 2005. Java How To Program. Sixth Edition. Prentice Hall. Hoare, C.A.R. 1985” Communication sequential processes”Englewood Cliffs, New Jersey, Prentice Hall Inc Jean Bacon, Tim Harris, 2003 “Operating Systems: Concurrent and Distributed Software Design” Massachhussets. Addison Wesley Kenneth H Rosen. 1999. “Discrete Mathematics and Its Application”. McGraw Hill. Madnick,Stuart E dan John J. Donovan, 1974 “ operating system”, Singapore: McGraw-Hill Book Co Michael Kifer and Scott A. Smolka, 2007 Introduction to Operating System Design and Implementation The OSP 2 Approach, Springer-Verlag London Microsoft 1999. Microsoft Windows User Experience. Microsoft Press. Milenkovie, Milan. 1992. “Operationg system: Concepts and Design”, Singapore: McGraw-Hill Book Co Randall Hyde. 2003. The Art of Assembly Language. First Edition. No Strach Press Robert betz, 2001 “Intoduction to Real-time operation system”, Department of Electrical and Computer Engineering University of Newcastle, Australia Robert Love. 2005. Linux Kernel Development . Second Edition. Novell Press Ron White,1998, How Computers Work, Fourth Edition, Que corporation, A Division of Macmillan Computer Publishing, USA Shay, William A. 1993, “ Introduction to Operationg System” New York: HarperCollins College Publishers Silberschatz, Peter Galvin, dan Grag Gagne. 2000. “Applied Operating System, 1s”t “ John Wile & Hiil Book Co Silberschatz, A., dan Galvin, P.2003, “Operating Sistem Concept. Sixth Edition”. Massachhussets. Addisson- Wasley Silberschatz, Peter Galvin, dan Grag Gagne. 2005. “Operating Systems Concepts”. Seventh Edition. John Wiley & Sons.
Stalling, William, 1995, “Operating Sistems”. New Jersey. Prentice – Hall Stalling, William, 1996” Computer Organization and Architecture”. New Jersey. Prentice – Hall Stalling William, 1995, “Network and Internetwork Security” Prentice-Hall, USA Tanenbaum, Andrew S, 1992 “Modern Operating Sistems”. New Jersey. Prentice – Hall Taenbaum, Andrew S, 2006, “Operating Systems Design and Implementation, Third Edition” Massachusetts
