Kebuntuan

Dalam komputasi serentak, kebuntuan adalah setiap situasi di mana tidak ada anggota dari beberapa kelompok entitas yang dapat melanjutkan karena masing-masing entitas menunggu anggota lain, termasuk dirinya sendiri, untuk mengambil tindakan, seperti mengirim pesan atau, lebih umum, melepaskan kunci . ^[1] Kebuntuan adalah masalah umum dalam sistem multipengolahan, komputasi paralel, dan sistem terdistribusi, karena dalam konteks ini sistem sering kali menggunakan kunci perangkat lunak atau perangkat keras untuk menengahi sumber daya bersama dan menerapkan sinkronisasi proses . ^[2]

Dalam sistem operasi, kebuntuan terjadi ketika suatu proses atau utas memasuki keadaan menunggu karena sumber daya sistem yang diminta ditahan oleh proses menunggu lainnya, yang kemudian menunggu sumber daya lain ditahan oleh proses menunggu lainnya. ^[3] Jika suatu proses tetap tidak dapat mengubah keadaannya tanpa batas waktu karena sumber daya yang diminta sedang digunakan oleh proses lain yang sedang menunggu, maka sistem dikatakan mengalami kebuntuan. ^[4]

Dalam sistem komunikasi, kebuntuan terjadi terutama karena hilangnya atau rusaknya sinyal, bukan karena perebutan sumber daya. ^[5]

Situasi kebuntuan pada suatu sumber daya hanya dapat muncul jika seluruh kondisi berikut terjadi secara bersamaan dalam suatu sistem: ^[6]

1. Pengecualian bersama : Setidaknya satu sumber daya harus disimpan dalam mode yang tidak dapat dibagikan; artinya, hanya satu proses pada satu waktu yang dapat menggunakan sumber daya tersebut.^[7] Jika tidak, proses tidak akan dicegah untuk menggunakan sumber daya bila diperlukan. Hanya satu proses yang dapat menggunakan sumber daya pada waktu tertentu.^[8]
2. Tahan dan tunggu atau simpan sumber daya: suatu proses saat ini memegang setidaknya satu sumber daya dan meminta sumber daya tambahan yang ditahan oleh proses lain.
3. Tidak ada perubahan siaran : sumber daya hanya dapat dilepaskan secara sukarela oleh proses yang memegangnya.
4. Tungguan melingkar: setiap proses harus menunggu sumber daya yang ditahan oleh proses lain, yang pada gilirannya menunggu proses pertama melepaskan sumber daya tersebut. Secara umum, ada serangkaian proses menunggu, P = { P ₁, P ₂, ..., P _N }, sehingga P ₁ menunggu sumber daya yang dimiliki oleh P ₂, P ₂ menunggu sumber daya yang dimiliki oleh P ₃ dan seterusnya hingga PN menunggu sumber daya _dimiliki oleh P ₁ . ^{[4] [9]}

Keempat kondisi ini dikenal sebagai kondisi Coffman dari uraian pertamanya dalam artikel tahun 1971 oleh Edward G. Coffman, ^[9]

Meskipun kondisi ini cukup untuk menghasilkan kebuntuan pada sistem sumber daya contoh tunggal, kondisi ini hanya menunjukkan kemungkinan kebuntuan pada sistem yang memiliki banyak contoh sumber daya.^[10]

Kebanyakan sistem operasi saat ini tidak dapat mencegah kebuntuan.^[11] Ketika kebuntuan terjadi, sistem operasi yang berbeda meresponsnya dengan cara non-standar yang berbeda. Sebagian besar pendekatan bekerja dengan mencegah terjadinya salah satu dari empat kondisi umum, terutama yang keempat. ^[12] Pendekatan utama adalah sebagai berikut.

Dalam pendekatan ini diasumsikan bahwa kebuntuan tidak akan pernah terjadi. Ini juga merupakan penerapan algoritma Burung Unta . ^{[12] [13]} Pendekatan ini awalnya digunakan oleh MINIX dan UNIX . ^[9] Hal ini digunakan ketika interval waktu antara terjadinya kebuntuan besar dan kehilangan data yang terjadi setiap kali dapat ditoleransi.

Mengabaikan kebuntuan dapat dilakukan dengan aman jika kebuntuan secara formal terbukti tidak pernah terjadi. Contohnya adalah kerangka RTIC.^[14]

Di bawah deteksi kebuntuan, kebuntuan diperbolehkan terjadi. Kemudian keadaan sistem diperiksa untuk mendeteksi telah terjadi kebuntuan dan selanjutnya diperbaiki. Algoritme digunakan untuk melacak alokasi sumber daya dan status proses, lalu memutar kembali dan memulai ulang satu atau lebih proses untuk menghilangkan kebuntuan yang terdeteksi. Memeriksa kebuntuan yang telah terjadi dapat dilakukan dengan mudah karena sumber daya yang telah dikunci dan/atau diminta oleh setiap proses diketahui oleh penjadwal sumber daya sistem operasi. ^[13]

Setelah kebuntuan terdeteksi, kebuntuan dapat diperbaiki dengan menggunakan salah satu metode berikut: 

1. Penghentian proses: satu atau lebih proses yang terlibat dalam kebuntuan dapat dibatalkan. Seseorang dapat memilih untuk membatalkan semua proses bersaing yang terlibat dalam kebuntuan tersebut. Hal ini memastikan bahwa kebuntuan diselesaikan dengan pasti dan cepat.^{[butuh rujukan][ <span title="This claim needs references to reliable sources. (May 2016)">kutipan diperlukan</span> ]} Namun biayanya tinggi karena sebagian perhitungan akan hilang. Atau, seseorang dapat memilih untuk membatalkan satu proses pada satu waktu hingga kebuntuan teratasi. Pendekatan ini mempunyai overhead yang tinggi karena setelah setiap pembatalan suatu algoritma harus menentukan apakah sistem masih dalam kebuntuan.^{[butuh rujukan][ <span title="This claim needs references to reliable sources. (May 2016)">kutipan diperlukan</span> ]} Beberapa faktor harus dipertimbangkan saat memilih kandidat untuk penghentian, seperti prioritas dan usia proses.^{[butuh rujukan]}
2. Perubahan siar sumber daya: sumber daya yang dialokasikan ke berbagai proses dapat didahulukan secara berturut-turut dan dialokasikan ke proses lain hingga kebuntuan terpecahkan.^{[15][Verifikasi gagal][ verifikasi gagal ]}

Pencegahan kebuntuan bekerja dengan mencegah terjadinya salah satu dari empat kondisi Coffman.

• Menghapus kondisi saling pengecualian berarti tidak ada proses yang memiliki akses eksklusif ke sumber daya. Hal ini terbukti mustahil bagi sumber daya yang tidak dapat dikumpulkan . Namun bahkan dengan sumber daya yang terbatas, kebuntuan masih bisa terjadi. Algoritma yang menghindari saling pengecualian disebut algoritma sinkronisasi nirhalang .
• Kondisi tunggu dan tahan atau simpanan sumber daya dapat dihilangkan dengan mewajibkan proses untuk meminta semua sumber daya yang diperlukan sebelum memulai (atau sebelum memulai serangkaian operasi tertentu). Pengetahuan tingkat lanjut ini sering kali sulit dipenuhi dan, dalam kasus apa pun, merupakan penggunaan sumber daya yang tidak efisien. Cara lain adalah dengan mengharuskan proses meminta sumber daya hanya jika tidak ada sumber daya; Pertama, mereka harus melepaskan semua sumber daya yang mereka miliki saat ini sebelum meminta semua sumber daya yang mereka perlukan dari awal. Hal ini juga seringkali tidak praktis. Hal ini terjadi karena sumber daya mungkin dialokasikan dan tidak digunakan dalam jangka waktu lama. Selain itu, suatu proses yang membutuhkan sumber daya populer mungkin harus menunggu tanpa batas waktu, karena sumber daya tersebut mungkin selalu dialokasikan ke suatu proses, sehingga mengakibatkan kekurangan sumber daya .^[16] (Algoritma ini, seperti serialisasi token, dikenal sebagai algoritma semua atau tidak sama sekali .)
• Kondisi tanpa perubahan siaran juga mungkin sulit atau tidak mungkin dihindari karena suatu proses harus mampu memiliki sumber daya untuk jangka waktu tertentu, atau hasil pemrosesan mungkin tidak konsisten atau mungkin terjadi deraan . Namun, ketidakmampuan untuk menerapkan perubahan siaran dapat mengganggu algoritma prioritas . Perubahan siaran dari sumber daya yang "terkunci" umumnya menyiratkan baik-belakang, dan harus dihindari karena biaya bubungan-nya sangat mahal. Algoritma yang memungkinkan perubahsiaran mencakup algoritma bebas kunci dan bebas tunggu serta kontrol konkurensi optimis . Jika suatu proses mempunyai beberapa sumber daya dan meminta beberapa sumber daya lain yang tidak dapat segera dialokasikan padanya, maka kondisi tersebut dapat dihilangkan dengan melepaskan semua sumber daya yang ada pada proses tersebut.
• Kondisi terakhir adalah kondisi menunggu melingkar . Pendekatan yang menghindari menunggu melingkar termasuk menonaktifkan interupsi selama bagian penting dan menggunakan hierarki untuk menentukan pengurutan sebagian sumber daya. Jika tidak ada hierarki yang jelas, bahkan alamat memori sumber daya telah digunakan untuk menentukan pengurutan dan sumber daya diminta dalam urutan pencacahan yang meningkat. ^[4] Solusi Dijkstra juga bisa digunakan.

Mirip dengan pencegahan kebuntuan, pendekatan penghindaran kebuntuan memastikan bahwa kebuntuan tidak akan terjadi dalam suatu sistem. Istilah "penghindaran kebuntuan" tampaknya sangat mirip dengan "pencegahan kebuntuan" dalam konteks linguistik, namun keduanya sangat jauh berbeda dalam konteks penanganan kebuntuan. Penghindaran kebuntuan tidak memaksakan kondisi apa pun seperti yang terlihat dalam pencegahan namun, di sini setiap permintaan sumber daya dianalisis secara cermat untuk melihat apakah permintaan tersebut dapat dipenuhi dengan aman tanpa menyebabkan kebuntuan.

Penghindaran kebuntuan mengharuskan sistem operasi diberikan informasi tambahan terlebih dahulu mengenai sumber daya mana yang akan diminta dan digunakan oleh suatu proses selama masa pakainya. Algoritma penghindaran kebuntuan menganalisis setiap permintaan dengan memeriksa bahwa tidak ada kemungkinan terjadinya kebuntuan di masa depan jika sumber daya yang diminta dialokasikan. Kelemahan dari pendekatan ini adalah diperlukannya informasi terlebih dahulu mengenai bagaimana sumber daya akan diminta di masa depan. Salah satu algoritma penghindaran kebuntuan yang paling banyak digunakan adalah algoritma Banker .^[17]

Kebukaan mirip dengan kebuntuan hanya saja keadaan proses yang terlibat dalam kebukaan terus berubah satu sama lain, tidak ada yang mengalami kemajuan.

Istilah ini diciptakan oleh Edward A. Ashcroft dalam makalah tahun 1975 ^[18] sehubungan dengan pemeriksaan sistem pemesanan maskapai penerbangan.^[19] Kebukaaan adalah kasus khusus kekurangan sumber daya ; definisi umum hanya menyatakan bahwa proses tertentu tidak berjalan.^[20]

Kebukaan adalah risiko dengan beberapa algoritma yang mendeteksi dan memulihkan dari kebuntuan . Jika lebih dari satu proses mengambil tindakan, algoritma pendeteksi kebuntuan dapat dipicu berulang kali. Hal ini dapat dihindari dengan memastikan bahwa hanya satu proses (dipilih secara sewenang-wenang atau berdasarkan prioritas) yang mengambil tindakan.^[21]

1. ^ Coulouris, George (2012). Distributed Systems Concepts and Design. Pearson. hlm. 716. ISBN 978-0-273-76059-7. 
2. ^ Padua, David (2011). Encyclopedia of Parallel Computing. Springer. hlm. 524. ISBN 9780387097657. Diarsipkan dari versi asli tanggal 18 April 2021. Diakses tanggal 16 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
3. ^ Falsafi, Babak; Midkiff, Samuel; Dennis, JackB; Dennis, JackB; Ghoting, Amol; Campbell, Roy H; Klausecker, Christof; Kranzlmüller, Dieter; Emer, Joel (2011). "Deadlocks". Encyclopedia of Parallel Computing. Boston, MA: Springer US. hlm. 524–527. doi:10.1007/978-0-387-09766-4_282. ISBN 978-0-387-09765-7. A deadlock is a condition that may happen in a system composed of multiple processes that can access shared resources. A deadlock is said to occur when two or more processes are waiting for each other to release a resource. None of the processes can make any progress. 
4. ^ ^{a b c} Silberschatz, Abraham (2006). Operating System Principles (edisi ke-7th). Wiley-India. hlm. 237. ISBN 9788126509621. Diarsipkan dari versi asli tanggal 25 January 2022. Diakses tanggal 16 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan) Kesalahan pengutipan: Tanda <ref> tidak sah; nama "os_galvin" didefinisikan berulang dengan isi berbeda
5. ^ Schneider, G. Michael (2009). Invitation to Computer Science. Cengage Learning. hlm. 271. ISBN 978-0324788594. Diarsipkan dari versi asli tanggal 18 April 2021. Diakses tanggal 16 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
6. ^ Silberschatz, Abraham (2006). Operating System Principles (edisi ke-7). Wiley-India. hlm. 239. ISBN 9788126509621. Diarsipkan dari versi asli tanggal 18 April 2021. Diakses tanggal 16 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
7. ^ Operating System Concepts. Wiley. 2012. hlm. 319. ISBN 978-1-118-06333-0. 
8. ^ "ECS 150 Spring 1999: Four Necessary and Sufficient Conditions for Deadlock". nob.cs.ucdavis.edu. Diarsipkan dari versi asli tanggal 29 April 2018. Diakses tanggal 29 April 2018.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
9. ^ ^{a b c} Shibu, K. (2009). Intro To Embedded Systems (edisi ke-1st). Tata McGraw-Hill Education. hlm. 446. ISBN 9780070145894. Diarsipkan dari versi asli tanggal 18 April 2021. Diakses tanggal 16 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
10. ^ "Operating Systems: Deadlocks". www.cs.uic.edu. Diarsipkan dari versi asli tanggal 28 May 2020. Diakses tanggal 2020-04-25. If a resource category contains more than one instance then the presence of a cycle in the resource-allocation graph indicates the possibility of a deadlock, but does not guarantee one. Consider, for example, Figures 7.3 and 7.4 below:  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
11. ^ Silberschatz, Abraham (2006). Operating System Principles (edisi ke-7). Wiley-India. hlm. 237. ISBN 9788126509621. Diarsipkan dari versi asli tanggal 18 April 2021. Diakses tanggal 16 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
12. ^ ^{a b} Stuart, Brian L. (2008). Principles of operating systems (edisi ke-1st). Cengage Learning. hlm. 446. ISBN 9781418837693. Diarsipkan dari versi asli tanggal 18 April 2021. Diakses tanggal 16 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
13. ^ ^{a b} Tanenbaum, Andrew S. (1995). Distributed Operating Systems (edisi ke-1st). Pearson Education. hlm. 117. ISBN 9788177581799. Diarsipkan dari versi asli tanggal 18 April 2021. Diakses tanggal 16 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
14. ^ "Preface - Real-Time Interrupt-driven Concurrency". Diarsipkan dari versi asli tanggal 18 September 2020. Diakses tanggal 1 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
15. ^ "IBM Knowledge Center". www.ibm.com. Diarsipkan dari versi asli tanggal 19 March 2017. Diakses tanggal 29 April 2018.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
16. ^ Silberschatz, Abraham (2006). Operating System Principles (edisi ke-7). Wiley-India. hlm. 244. ISBN 9788126509621. Diarsipkan dari versi asli tanggal 18 April 2021. Diakses tanggal 16 October 2020.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
17. ^ "Deadlock Avoidance Algorithms in Operating System (OS)". Electronics Mind. 26 January 2022. 
18. ^ Ashcroft, E.A. (1975). "Proving assertions about parallel programs". Journal of Computer and System Sciences. 10: 110–135. doi:10.1016/S0022-0000(75)80018-3. 
19. ^ Kwong, Y. S. (1979). "On the absence of livelocks in parallel programs". Semantics of Concurrent Computation. Lecture Notes in Computer Science. 70. hlm. 172–190. doi:10.1007/BFb0022469. ISBN 3-540-09511-X. 
20. ^ Anderson, James H.; Yong-jik Kim (2001). "Shared-memory mutual exclusion: Major research trends since 1986". Diarsipkan dari versi asli tanggal 25 May 2006.  Parameter |url-status= yang tidak diketahui akan diabaikan (bantuan)
21. ^ Zöbel, Dieter (October 1983). "The Deadlock problem: a classifying bibliography". ACM SIGOPS Operating Systems Review. 17 (4): 6–15. doi:10.1145/850752.850753. ISSN 0163-5980.