Hubungan Algoritma Ostrich dengan Deadlock

Apa itu Deadlock ?

Rangkaian proses 'menemui jalan buntu' jika setiap proses dalam rangkaian menunggu peristiwa yang hanya dapat disebabkan oleh proses lain dalam rangkaian ...

Deadlock adalah situasi yang terjadi di OS ketika setiap proses memasuki status menunggu karena proses menunggu lain menahan sumber daya yang diminta (misalnya Printer, Tabel dalam database, Tape Drivers) . Kebuntuan adalah masalah umum dalam multi-pemrosesan di mana beberapa proses berbagi jenis sumber daya yang saling eksklusif.

Karena semua proses sedang menunggu, tidak satu pun dari proses tersebut yang akan menyebabkan peristiwa apa pun yang dapat membangunkan salah satu anggota kumpulan, dan semua proses terus menunggu selamanya.

Dalam kebanyakan kasus, peristiwa yang menunggu setiap proses adalah pelepasan beberapa sumber daya yang saat ini diproses oleh anggota lain dari set. Dengan kata lain, setiap anggota rangkaian proses yang mengalami kebuntuan sedang menunggu sumber daya yang dimiliki oleh proses yang mengalami kebuntuan.

Tidak ada proses yang dapat berjalan, tidak ada yang dapat melepaskan sumber daya apa pun, dan tidak ada yang dapat dibangunkan. Jumlah proses dan jumlah serta jenis sumber daya yang dimiliki dan diminta tidak penting.

Penyebab Deadlock

Berikut empat syarat yang harus dipegang secara bersamaan untuk membangkitkan kebuntuan. Jika salah satu dari kondisi ini gagal, tidak ada kemungkinan kebuntuan sumber daya:

Pengecualian Reksa : Setiap sumber daya saat ini ditetapkan ke tepat satu proses. Artinya, sumber daya yang terlibat tidak dapat dibagikan.
Tahan dan Tunggu : Proses yang saat ini menahan sumber daya yang diberikan sebelumnya dapat meminta sumber daya baru.
Tidak Ada Preemption : Sumber daya yang sebelumnya diberikan tidak dapat diambil secara paksa dari suatu proses. Mereka harus dibebaskan secara eksplisit melalui proses menahan mereka.
Penantian Sirkuler : Harus ada rantai melingkar dari dua atau lebih proses, yang masing-masing menunggu sumber daya yang dipegang oleh anggota rantai berikutnya. Rantai proses melingkar, dengan setiap proses memegang sumber daya yang saat ini diminta oleh proses selanjutnya dalam rantai, tidak dapat ada. Jika ya, teorema siklus - siklus dalam grafik sumber daya diperlukan agar terjadi kebuntuan, yang menunjukkan bahwa kebuntuan akan terjadi.

Mencegah Deadlock

Kebuntuan dapat dicegah menggunakan beberapa metode khusus:

Deadlock Ignorance (Algoritma Ostrich).
Deteksi dan Pemulihan Kebuntuan.
Penghindaran Kebuntuan.
Pencegahan Kebuntuan.

Mengapa Mengabaikan Deadlock?

Secara singkat, Algoritma Ostrich adalah tentang mengabaikan kebuntuan jika itu terjadi. Semoga saja deadlock tidak akan pernah terjadi dalam suatu sistem. Secara umum, ini adalah strategi yang masuk akal. Suatu sistem dapat berjalan selama bertahun-tahun tanpa ada kebuntuan. Jika sistem operasi memiliki sistem pencegahan atau deteksi kebuntuan, maka itu mungkin berdampak negatif pada kinerja sistem. Karena setiap kali proses atau utas meminta sumber daya, sistem perlu memeriksa apakah pemberian sumber daya dapat menyebabkan potensi situasi kebuntuan. Pemeriksaan ini akan dilakukan meskipun tidak ada kebuntuan yang terjadi. Dan ini memperlambat kinerja sistem.

Algoritma Ostrich

Algoritma ini adalah metode yang digunakan dengan baik untuk mengabaikan masalah. Itu mendapatkan namanya dari Burung Unta / ostrich dan cara ia menempelkan kepalanya di pasir dan mengabaikan semua yang terjadi di sekitar seperti yang ditunjukkan gambar di bawah ini.

Pro dari ketidaktahuan di jalan buntu?

Tidak ada tenaga kerja yang diperlukan untuk melakukan pekerjaan tambahan. Saat sistem macet, mulai ulang. Ini hanya dapat dilakukan jika kebuntuan jarang terjadi. Jika komputer mengalami kebuntuan sekali per 10 tahun maka reboot sistem lebih disukai daripada sebelumnya

Kontra dari ketidaktahuan di jalan buntu?

Jika cukup sering terjadi, maka ini bukanlah solusi yang optimal. Anda harus menginvestasikan waktu untuk menangani kebuntuan dengan benar, itulah salah satu dari tiga metode berikutnya yang disebutkan di atas untuk mencegah kebuntuan.

Analisis Algoritma Ostrich

Orang yang berbeda bereaksi terhadap strategi ini dengan cara yang berbeda. Jika kebuntuan terjadi rata-rata sekali setiap lima tahun, tetapi sistem macet karena kegagalan perangkat keras, kesalahan kompiler, dan bug sistem operasi terjadi seminggu sekali, sebagian besar insinyur tidak akan bersedia membayar denda yang besar dalam kinerja atau kenyamanan untuk menghilangkan kebuntuan .

Kebanyakan sistem operasi berpotensi mengalami kebuntuan yang bahkan tidak terdeteksi, apalagi otomatis rusak. Jumlah proses dalam sistem ditentukan oleh jumlah entri dalam tabel proses. Jumlah proses dalam sistem ditentukan oleh jumlah entri dalam tabel proses. Slot tabel proses ini ( struktur data dipelihara oleh OS untuk pengalihan konteks dan penjadwalan ) adalah sumber daya yang terbatas. Jika garpu ( panggilan untuk membuat proses baru dari proses yang sedang berjalan ) gagal karena tabel penuh, pendekatan yang masuk akal untuk program yang melakukan garpu adalah menunggu waktu acak dan mencoba lagi.

Sekarang misalkan sistem UNIX memiliki 100 slot proses. 10 program sedang berjalan, yang masing-masing perlu membuat 12 (sub) proses (Total 10 × 12 = 120). Setelah setiap proses membuat 9 proses, 10 proses asli dan 90 proses baru telah menghabiskan tabel. Masing-masing dari 10 proses asli sekarang berada dalam loop forking tanpa akhir dan gagal - kebuntuan.

Kemungkinan terjadinya hal ini sangat kecil, tetapi itu bisa saja terjadi. Dalam hal ini, haruskah kita meninggalkan proses dan panggilan fork untuk menghilangkan masalah?

Jumlah maksimum file yang terbuka juga dibatasi oleh ukuran tabel i-node, jadi masalah serupa terjadi saat mengisi. Ruang swap pada disk adalah sumber daya terbatas lainnya. Nyatanya, hampir setiap tabel dalam sistem operasi mewakili sumber daya yang terbatas. Haruskah kita menghapus semua ini karena mungkin saja kumpulan dari n proses mungkin masing-masing mengklaim 1 / n dari total, dan kemudian masing-masing mencoba untuk mengklaim yang lain?

OS yang mengunakan Algoritma Ostrich

Sebagian besar sistem operasi, UNIX dan Windows, abaikan saja masalah dengan asumsi bahwa sebagian besar pengguna lebih suka kebuntuan sesekali ke aturan yang membatasi semua pengguna ke satu proses, satu file terbuka, dan satu dari semuanya. Jika kebuntuan bisa dihilangkan dengan gratis, tidak akan banyak diskusi. Masalahnya adalah bahwa harganya tinggi, sebagian besar dalam hal menempatkan batasan yang tidak nyaman pada proses. Jadi kita dihadapkan pada pertukaran yang tidak menyenangkan antara kenyamanan dan ketepatan. Dalam kondisi ini, solusi umum sulit ditemukan.

Kapan Algoritma Ostrich dibutuhkan ?

Algoritma Ostrich dapat digunakan jika:

Kebuntuan sangat jarang terjadi.
Kebuntuan sulit di deteksi.
Biaya pencegahan kebuntuan tinggi.

Kompromi dalam menggunakan Algoritma Ostrich

Meskipun efisien, menggunakan Algoritma Ostrich memperdagangkan kebenaran untuk kenyamanan. Karena algoritme secara langsung menangani kasus-kasus ekstrem, ini bukanlah trade-off yang besar. Faktanya, metode paling sederhana dan paling banyak digunakan untuk memulihkan dari kebuntuan adalah reboot.

Beberapa algoritme dengan kinerja kasus terburuk biasanya digunakan karena mereka menunjukkan kinerja yang buruk pada kasus buatan yang tidak terjadi dalam praktik. Misalnya, algoritme simpleks, algoritme Jenis Inferensi untuk ML Standar, overflow bilangan bulat dalam bahasa pemrograman dengan bilangan bulat lebar tetap juga diabaikan karena terjadi dalam kasus yang sangat luar biasa.

Preemptive dan Non Preemptive

1. Penjadwalaan Preemptive

preemptive digunakan ketika proses beralih dari status berjalan ke status siap atau dari status menunggu ke status siap. Sumber daya (terutama siklus CPU) dialokasikan ke proses untuk jumlah waktu yang terbatas dan kemudian diambil, dan proses tersebut ditempatkan kembali dalam antrian siap jika proses tersebut masih memiliki sisa waktu burst CPU. Proses itu tetap dalam antrian siap sampai mendapat kesempatan berikutnya untuk dieksekusi.

Algoritma berdasarkan penjadwalan preemptive adalah: Round Robin (RR) , Shortest Remaining Time First (SRTF) , Priority (versi preemptive) , dll.

2. Penjadwalaan Non Preemptive

Non-preemptive digunakan ketika proses berakhir, atau proses beralih dari berjalan ke status menunggu. Dalam penjadwalan ini, setelah sumber daya (siklus CPU) dialokasikan ke suatu proses, proses tersebut menahan CPU hingga dihentikan atau mencapai status menunggu. Dalam kasus penjadwalan non-preemptive tidak mengganggu proses yang menjalankan CPU di tengah eksekusi. Sebagai gantinya, ia menunggu hingga proses menyelesaikan waktu burst CPU-nya dan kemudian dapat mengalokasikan CPU ke proses lain.

Algoritma yang didasarkan pada penjadwalan non-preemptive adalah: Shortest Job First (SJF pada dasarnya non preemptive) dan Priority (versi non preemptive) , dll.

Perbedaan Utama Antara Penjadwlan Preemptive dan Penjadwalan Non-Preemptive :

Dalam penjadwalan preemptive, CPU dialokasikan ke proses untuk waktu yang terbatas sedangkan dalam penjadwalan Non-preemptive, CPU dialokasikan ke proses sampai ia berhenti atau beralih ke status menunggu.
Proses eksekusi dalam penjadwalan preemptive terputus di tengah eksekusi ketika prioritas yang lebih tinggi datang, sedangkan proses eksekusi dalam penjadwalan non-preemptive tidak terganggu di tengah eksekusi dan menunggu hingga eksekusi.
Dalam Penjadwalan Preemptive, ada overhead untuk mengalihkan proses dari status siap ke status berjalan, vise-ayat, dan mempertahankan antrean siap. Sedangkan dalam kasus penjadwalan non-preemptive tidak memiliki overhead untuk mengalihkan proses dari status berjalan ke status siap.
Dalam penjadwalan preemptive, jika proses dengan prioritas tinggi sering kali masuk dalam antrian siap, maka proses dengan prioritas rendah harus menunggu lama, dan mungkin harus kelaparan. Di sisi lain, dalam penjadwalan non-preemptive, jika CPU dialokasikan ke proses yang memiliki waktu burst lebih besar maka proses dengan waktu burst kecil mungkin harus kelaparan.
Penjadwalan preemptive menjadi fleksibel dengan memungkinkan proses kritis untuk mengakses CPU saat mereka tiba di antrian siap, tidak peduli proses apa yang sedang dijalankan saat ini. Penjadwalan non-preemptive disebut kaku karena meskipun proses kritis memasuki antrian siap, proses yang menjalankan CPU tidak terganggu.
Penjadwalan Terlebih Dahulu harus menjaga integritas data bersama, itulah mengapa ini bersifat asosiatif biaya karena tidak demikian dengan Penjadwalan Non-preemptive.

Grafik Perbandingan :

Paramenter	Penjadwalan Preemptive	Penjadwalaan Non Preemptive
Basic	Dalam sumber daya ini (Siklus CPU) dialokasikan ke proses untuk waktu yang terbatas.	Setelah sumber daya (Siklus CPU) dialokasikan ke suatu proses, proses akan menahannya hingga menyelesaikan waktu burstnya atau beralih ke status menunggu.
Interrupt	Proses dapat terputus di antaranya.	Proses tidak dapat dihentikan hingga berhenti sendiri atau waktunya habis.
Starvation	Jika proses yang memiliki prioritas tinggi sering kali masuk ke antrean siap, proses dengan prioritas rendah dapat menyebabkan kelaparan.	Jika proses dengan waktu burst yang lama menjalankan CPU, maka proses yang akan datang dengan waktu burst CPU yang lebih sedikit dapat menyebabkan kelaparan.
Overhead	Ini memiliki overhead penjadwalan proses.	Tidak ada biaya tambahan.
Flexibility	fleksibel	kaku
Cost	biaya terkait	tidak ada biaya yang terkait
Pemanfaatan CPU	Dalam penjadwalan preemptive, pemakaian CPU tinggi.	Ini rendah dalam penjadwalan non preemptive.
Contoh	Contoh penjadwalan preemptive adalah Round Robin dan Sisa Waktu Tersingkat Pertama.	Contoh penjadwalan non-preemptive adalah First Come First Serve dan Shortest Job First.

Alur Graph

Karena algoritma banker menggunakan beberapa jenis tabel seperti alokasi, permintaan, tersedia semua itu untuk memahami apa keadaan sistem. Demikian pula, jika Anda ingin memahami keadaan sistem daripada menggunakan tabel tersebut, sebenarnya tabel sangat mudah untuk mewakili dan memahaminya, tetapi Anda tetap dapat merepresentasikan informasi yang sama dalam grafik. Grafik tersebut disebut Resource Allocation Graph (RAG) .

Jadi, grafik alokasi sumber daya menjelaskan kepada kita apa status sistem dalam hal proses dan sumber daya . Seperti berapa banyak sumber daya yang tersedia, berapa banyak yang dialokasikan dan apa permintaan dari setiap proses. Semuanya dapat direpresentasikan dalam bentuk diagram. Salah satu keuntungan memiliki diagram adalah, terkadang Anda dapat melihat kebuntuan secara langsung dengan menggunakan RAG, tetapi Anda mungkin tidak dapat mengetahuinya dengan melihat tabel. Tetapi tabel akan lebih baik jika sistem berisi banyak proses dan sumber daya dan Grafik lebih baik jika sistem berisi lebih sedikit jumlah proses dan sumber daya.

Kita tahu bahwa setiap grafik mengandung simpul dan tepi. Jadi RAG juga berisi simpul dan tepi. Dalam simpul RAG ada dua jenis -

1. Proses simpul - Setiap proses akan direpresentasikan sebagai simpul proses. Umumnya, proses akan direpresentasikan dengan lingkaran.

2. Titik sumber daya - Setiap sumber daya akan direpresentasikan sebagai simpul sumber daya. Ini juga dua jenis -

Sumber daya jenis instans tunggal - Ini direpresentasikan sebagai kotak, di dalam kotak, akan ada satu titik. Jadi jumlah titik menunjukkan berapa banyak instance yang ada untuk setiap jenis sumber daya.
Sumber daya jenis instance multi-sumber daya - Ini juga mewakili sebagai kotak, di dalam kotak, akan ada banyak titik.

Sekarang sampai pada tepi RAG. Ada dua jenis tepi di RAG -

1. Assign Edge - Jika Anda sudah menetapkan sumber daya ke proses maka itu disebut Assign edge.

2. Request Edge - Ini berarti di masa depan proses mungkin menginginkan beberapa sumber daya untuk menyelesaikan eksekusi, yang disebut request edge.

Jadi, jika suatu proses menggunakan sumber daya, panah ditarik dari simpul sumber daya ke simpul proses. Jika suatu proses meminta sumber daya, panah ditarik dari simpul proses ke simpul sumber daya.

Contoh 1 (Single instance RAG) -

Jika ada siklus dalam Grafik Alokasi Sumber Daya dan setiap sumber daya dalam siklus hanya menyediakan satu contoh, maka prosesnya akan menemui jalan buntu. Sebagai contoh, jika proses P1 menahan resource R1, proses P2 menahan resource R2 dan proses P1 menunggu R2 dan proses P2 menunggu R1, maka proses P1 dan proses P2 akan mengalami deadlock.

Berikut contoh lain, yang menunjukkan Proses P1 dan P2 memperoleh sumber daya R1 dan R2 sementara proses P3 menunggu untuk memperoleh kedua sumber daya. Dalam contoh ini, tidak ada kebuntuan karena tidak ada ketergantungan melingkar.

Jadi siklus dalam jenis sumber daya instance tunggal adalah kondisi yang cukup untuk kebuntuan.

Contoh 2 (Multi-instance RAG) -

Dari contoh di atas, tidak mungkin untuk mengatakan RAG dalam status aman atau tidak aman. Jadi untuk melihat status RAG ini, mari kita buat matriks alokasi dan matriks permintaan.

Jumlah proses ada tiga; P1, P2 & P3 dan jumlah sumber daya adalah dua; R1 & R2.
Alokasi matriks -
Untuk menyusun matriks alokasi, cukup buka sumber daya dan lihat ke proses mana ia dialokasikan.
R1 dialokasikan ke P1, oleh karena itu tulis 1 dalam matriks alokasi dan demikian pula, R2 dialokasikan ke P2 serta P3 dan untuk elemen yang tersisa cukup tulis 0.
Matriks permintaan -
Untuk mengetahui matriks permintaan, Anda harus pergi ke proses dan melihat tepi keluar.
P1 meminta sumber daya R2, jadi tulis 1 dalam matriks dan demikian pula, P2 meminta R1 dan untuk elemen yang tersisa, tulis 0.
Jadi sekarang resource yang tersedia adalah = (0, 0).
Memeriksa kebuntuan (aman atau tidak) -
Jadi tidak ada deadlock pada RAG ini, walaupun ada cycle tapi tetap saja tidak ada deadlock. Oleh karena itu pada multi instance resource cycle tidak cukup kondisinya untuk terjadinya deadlock.
Contoh di atas sama dengan contoh sebelumnya kecuali itu, proses P3 meminta sumber daya R1.
Jadi tabelnya menjadi seperti gambar di bawah ini.
Jadi, Sumber daya yang tersedia adalah = (0, 0), tetapi persyaratannya adalah (0, 1), (1, 0) dan (1, 0]. Jadi Anda tidak dapat memenuhi salah satu persyaratan. Oleh karena itu, dalam kebuntuan .
Oleh karena itu, setiap siklus dalam grafik jenis sumber daya multi-instans bukanlah kebuntuan, jika harus ada kebuntuan, harus ada siklus. Jadi, dalam kasus RAG dengan jenis sumber daya multi-instans, siklus diperlukan kondisi kebuntuan, tapi tidak cukup.

Link Presentasi di Youtube :

https://youtu.be/Dfu-CFLfsU0

Daftar Pustaka :

Materi Hubungan Algoritma Ostrich dengan Deadlock :

Materi Preemtion dan Non Preemtion

https://www.geeksforgeeks.org/preemptive-and-non-preemptive-scheduling/
https://www.tutorialspoint.com/preemptive-and-non-preemptive-scheduling#:~:text=Preemptive%20Scheduling%20is%20a%20CPU,CPU%20to%20a%20given%20process.&text=Non%2Dpreemptive%20Scheduling%20is%20a,pushed%20to%20the%20waiting%20state.

Materi Alur Graph

https://www.geeksforgeeks.org/resource-allocation-graph-rag-in-operating-system/

Search This Blog

Julianti Y

Pertemuan 7 : Hubugan Algoritma Ostrich dengan Deadlock, Preemptive dan Non Preemptive & Alur Graph