2:31 PM
Deadlock adalah keadaan dimana 2 atau lebih proses
saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya.
Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah.
Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan
oleh 2 proses. Deadlock bisa digambarkan sebagai berikut :
Kejadian Deadlock selalu tidak lepas dari sumber daya,
bahwa hampir seluruhnya merupakan masalah sumber daya yang digunakan
bersama-sama. Oleh karena itu, kita juga perlu tahu tentang jenis sumber daya,
yaitu: sumber daya dapat digunakan lagi berulang-ulang dan sumber daya yang
dapat digunakan dan habis dipakai atau dapat dikatakan sumber daya sekali
pakai. Sumber daya ini tidak habis dipakai oleh proses mana pun.Tetapi setelah
proses berakhir, sumber daya ini dikembalikan untuk dipakai oleh proses lain
yang sebelumnya tidak kebagian sumber daya ini.
Contohnya prosesor, Channel I/O, disk, semaphore.
Contoh peran sumber daya jenis ini pada terjadinya Deadlock ialah misalnya
sebuah proses memakai disk A dan B, maka akan terjadi Deadlock jika setiap
proses sudah memiliki salah satu disk dan meminta disk yang lain. Masalah ini
tidak hanya dirasakan oleh pemrogram tetapi oleh seorang yang merancang sebuah
sistem operasi. Cara yang digunakan pada umumnya dengan cara memperhitungkan
dahulu sumber daya yang digunakan oleh proses-proses yang akan menggunakan
sumber daya tersebut. Contoh lain yang menyebabkan Deadlock dari sumber yang
dapat dipakai berulang-ulang ialah berkaitan dengan jumlah proses yang memakai
memori utama. Ada empat kondisi yang dapat menyebabkan terjadinya deadlock.
Keempat kondisi tersebut tidak dapat berdiri sendiri, namun saling mendukung.
·
Mutual
exclusion. Hanya ada satu proses yang boleh memakai sumber daya, dan proses
lain yang ingin memakai sumber daya tersebut harus menunggu hingga sumber daya
tadi dilepaskan atau tidak ada proses yang memakai sumber daya tersebut.
·
Hold and
wait. Proses yang sedang memakai sumber daya boleh meminta sumber daya lagi
maksudnya menunggu hingga benar-benar sumber daya yang diminta tidak dipakai
oleh proses lain, hal ini dapat menyebabkan kelaparan sumber daya sebab dapat
saja sebuah proses tidak mendapat sumber daya dalam waktu yang lama.
·
No
preemption. Sumber daya yang ada pada sebuah proses tidak boleh diambil begitu
saja oleh proses lainnya. Untuk mendapatkan sumber daya tersebut, maka harus
dilepaskan terlebih dahulu oleh proses yang memegangnya, selain itu seluruh
proses menunggu dan mempersilahkan hanya proses yang memiliki sumber daya yang
boleh berjalan.
·
Circular
wait. Kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang
dipegang proses berikutnya.
Strategi mengatasi Deadlock :
Add beberapa
cara untuk menanggulangi terjadinya deadlock, diantaranya adalah:
·
Mengabaikan
masalah deadlock.
·
Mendeteksi
dan memperbaiki
·
Penghindaran
yang terus menerus dan pengalokasian yang baik dengan menggunakan protocol
untuk memastikan sistem tidak pernah memasuki keadaan deadlock. Yaitu dengan
deadlock avoidance sistem untuk mendata informasi tambahan tentang proses mana
yang akan meminta dan menggunakan sumber daya.
·
Pencegahan
yang secara struktur bertentangan dengan empat kondisi terjadinya deadlock
dengan deadlock prevention sistem untuk memastikan bahwa salah satu kondisi
yang penting tidak dapat menunggu.
Mengabaikan Masalah Deadlock
Untuk
memastikan sistem tidak memasuki deadlock, sistem dapat menggunakan pencegahan
deadlock atau penghindaran deadlock. Penghindaran deadlock membutuhkan
informasi tentang sumber daya yang mana yang akan suatu proses meminta dan
berapa lama akan digunakan. Dengan informasi tersebut dapat diputuskan apakah
suatu proses harus menunggu atau tidak. Hal ini disebabkan oleh keberadaan
sumber daya, apakah ia sedang digunakan oleh proses lain atau tidak. Metode ini
lebih dikenal dengan Algoritma Ostrich. Dalam algoritma ini dikatakan bahwa
untuk menghadapi Deadlock ialah dengan berpura-pura bahwa tidak ada masalah apa
pun. Hal ini seakanakan melakukan suatu hal yang fatal, tetapi sistem operasi
Unix menanggulangi Deadlock dengan cara ini dengan tidak mendeteksi Deadlock
dan membiarkannya secara otomatis mematikan program sehingga seakan-akan tidak
terjadi apa pun. Jadi jika terjadi Deadlock, maka tabel akan penuh, sehingga
proses yang menjalankan proses melalui operator harus menunggu pada waktu
tertentu dan mencoba lagi.
Mendeteksi dan Memperbaiki
1. Caranya ialah dengan cara mendeteksi
jika terjadi deadlock pada suatu proses maka dideteksi system mana yang
terlibat di dalamnya. Setelah diketahui sistem mana saja yang terlibat maka
diadakan proses untuk memperbaiki dan menjadikan sistem berjalan kembali. Jika
sebuah sistem tidak memastikan deadlock akan terjadi, dan juga tidak didukung
dengan pendeteksian deadlock serta pencegahannya, maka kita akan sampai pada
kondisi deadlock yang dapat berpengaruh terhadap performance sistem karena sumber
daya tidak dapat digunakan oleh proses sehingga proses-proses yang lain juga
terganggu. Akhirnya sistem akan berhenti dan harus direstart.
Hal-hal yang
terjadi dalam mendeteksi adanya Deadlock adalah:
•
Permintaan
sumber daya dikabulkan selama memungkinkan.
•
Sistem
operasi memeriksa adakah kondisi circular wait secara periodik.
•
Pemeriksaan
adanya deadlock dapat dilakukan setiap ada sumber daya yang hendak digunakan
oleh sebuah proses.
•
Memeriksa
dengan algoritma tertentu.
Ada beberapa jalan untuk kembali
dari Deadlock, yaitu:
1.Lewat
Preemption
Dengan cara
untuk sementara waktu menjauhkan sumber daya dari pemakainya, dan memberikannya
pada proses yang lain. Ide untuk memberi pada proses lain tanpa diketahui oleh
pemilik dari sumber daya tersebut tergantung dari sifat sumber daya itu
sendiri. Perbaikan dengan cara ini sangat sulit atau dapat dikatakan tidak
mungkin. Cara ini dapat dilakukan dengan memilih korban yang akan dikorbankan
atau diambil sumber dayanya untuk sementara, tentu saja harus dengan perhitungan
yang cukup agar waktu yang dikorbankan seminimal mungkin. Setelah kita
melakukan preemption dilakukan pengkondisian proses tersebut dalam kondisi
aman. Setelah itu proses dilakukan lagi dalam kondisi aman tersebut.
2. Lewat Melacak Kembali
Setelah
melakukan beberapa langkah preemption, maka proses utama yang diambil sumber
dayanya akan berhenti dan tidak dapat melanjutkan kegiatannya, oleh karena itu
dibutuhkan langkah untuk kembali pada keadaan aman dimana proses masih berjalan
dan memulai proses lagi dari situ. Tetapi untuk beberapa keadaan sangat sulit
menentukan kondisi aman tersebut, oleh karena itu umumnya dilakukan cara
mematikan program tersebut lalu memulai kembali proses. Meski pun sebenarnya
lebih efektif jika hanya mundur beberapa langkah saja sampai deadlock tidak
terjadi lagi. Untuk beberapa sistem mencoba dengan cara mengadakan pengecekan
beberapa kali secara periodik dan menandai tempat terakhir kali menulis ke
disk, sehingga saat terjadi deadlock dapat mulai dari tempat terakhir
penandaannya berada.
3. Lewat mematikan proses yang
menyebabkan Deadlock
Cara yang
paling umum ialah mematikan semua proses yang mengalami deadlock. Cara ini
paling umum dilakukan dan dilakukan oleh hampir semua sistem operasi. Namun,
untuk beberapa sistem, kita juga dapat mematikan beberapa proses saja dalam
siklus deadlock untuk menghindari deadlock dan mempersilahkan proses lainnya
kembali berjalan. Atau dipilih salah satu korban untuk melepaskan sumber
dayanya, dengan cara ini maka masalah pemilihan korban menjadi lebih selektif,
sebab telah diperhitungkan beberapa kemungkinan jika si proses harus melepaskan
sumber dayanya.
Kriteria
pemilihan korban ialah:
• Yang
paling jarang memakai prosesor
• Yang
paling sedikit hasil programnya
• Yang
paling banyak memakai sumber daya sampai saat ini
• Yang
alokasi sumber daya totalnya tersedkit
• Yang
memiliki prioritas terkecil
4. Menghindari Deadlock
Pada sistem
kebanyakan permintaan terhadap sumber daya dilakukan sebanyak sekali saja.
Sistem sudah harus dapat mengenali bahwa sumber daya itu aman atau tidak (tidak
terkena deadlock), setelah itu baru dialokasikan. Ada dua cara yaitu:
1. Jangan
memulai proses apa pun jika proses tersebut akan membawanya pada kondisi
deadlock, sehingga tidak mungkin terjadi deadlock karena pada saat akan menuju
deadlock, proses sudah dicegah.
2. Jangan
memberi kesempatan pada suatu proses untuk meminta sumber daya lagi jika
penambahan ini akan membawa kita pada suatu keadaan deadlock. Jadi diadakan dua
kali penjagaan, yaitu saat pengalokasian awal, dijaga agar tidak deadlock dan
ditambah
dengan penjagaan kedua saat suatu proses meminta sumber daya, dijaga agar
jangan sampai terjadi deadlock. Pada sistem deadlock avoidance (penghindaran)
dilakukan dengan cara memastikan bahwa program memiliki maksimum permintaan.
Dengan kata lain cara sistem ini memastikan terlebih dahulu bahwa sistem akan
selalu dalam kondisi aman. Baik mengadakan permintaan awal atau pun saat
meminta permintaan sumber daya tambahan, sistem harus selalu berada dalam
kondisi aman.
Mutual exclusion
Dalam ilmu komputer, saling pengecualian mengacu pada
kebutuhan untuk menjamin bahwa tidak ada dua proses atau benang (selanjutnya
disebut hanya sebagai proses) berada di bagian kritis mereka pada waktu yang
sama. Di sini, bagian kritis mengacu pada periode waktu ketika proses mengakses
sumber daya bersama, seperti memori bersama. Masalah mutual exclusion pertama
kali diidentifikasi dan dipecahkan oleh Edsger W. Dijkstra dalam seminal 1965
makalahnya berjudul: Solusi dari masalah dalam kontrol pemrograman konkuren.
Contoh sederhana mengapa saling pengecualian penting
dalam praktek dapat divisualisasikan menggunakan linked list tunggal. Dalam
sebuah linked list penghapusan node dilakukan dengan mengubah
"berikutnya" pointer dari node sebelumnya untuk menunjuk ke simpul
berikutnya (misalnya, jika node i sedang dihapus maka "berikutnya"
pointer node i-1 akan diubah untuk menunjuk ke node i +1). Dalam eksekusi mana
seperti linked list sedang dibagi antara beberapa proses, dua proses mungkin
mencoba untuk menghapus dua node yang berbeda secara bersamaan mengakibatkan
masalah berikut: biarkan node i dan i +1 menjadi node yang akan dihapus, lebih
jauh lagi, janganlah dari mereka menjadi kepala atau ekor, pointer berikutnya
simpul i-1 akan berubah untuk menunjuk ke node i +1 dan pointer berikutnya node
i akan berubah untuk menunjuk ke node i +2. Meskipun kedua operasi penghapusan
lengkap berhasil, node i +1 tetap ada dalam daftar sejak i-1 dibuat untuk
menunjuk ke i +1 skipping node i (yang dibuat untuk menunjuk ke i +2). Hal ini
dapat dilihat pada Gambar 1. Masalah ini dapat dihindari dengan menggunakan
pengecualian bersama untuk memastikan bahwa update simultan ke bagian yang sama
dari daftar tidak dapat terjadi. Isi Menegakkan mutual exclusion
Ada baik perangkat lunak dan solusi perangkat keras
untuk menegakkan saling pengecualian. Beberapa solusi yang berbeda dibahas di
bawah ini.
Solusi
perangkat keras
Pada sistem prosesor tunggal, solusi yang paling
sederhana untuk mencapai saling pengecualian adalah untuk menonaktifkan
interupsi selama proses 'bagian kritis. Ini akan mencegah rutinitas layanan
interupsi dari berjalan (efektif mencegah proses dari yang mendahului).
Meskipun ini adalah solusi efektif, hal itu menyebabkan banyak masalah. Jika
suatu bagian kritis adalah panjang, maka jam sistem akan melayang setiap kali
bagian kritis dieksekusi karena interupsi timer tidak lagi dilayani, sehingga
pelacakan waktu mustahil selama bagian kritis. Juga, jika suatu proses
menghentikan selama bagian kritis, kontrol tidak akan pernah kembali ke proses
lain, secara efektif menghentikan seluruh sistem. Sebuah metode yang lebih
elegan untuk mencapai saling pengecualian adalah sibuk-tunggu.
Sibuk-tunggu adalah efektif untuk kedua uniprocessor
dan sistem multiprosesor. Penggunaan memori bersama dan tes-dan-set instruksi atom
memberikan pengecualian bersama. Sebuah proses dapat menguji-dan-set pada
sebuah lokasi di memori bersama, dan karena operasi adalah atom, hanya satu
proses dapat mengatur bendera pada suatu waktu. Setiap proses yang tidak
berhasil dalam menetapkan bendera dapat pergi untuk melakukan tugas-tugas lain
dan coba lagi nanti, lepaskan prosesor ke proses lain dan coba lagi nanti, atau
terus loop sementara memeriksa bendera sampai berhasil memperolehnya.
Preemption masih mungkin, jadi metode ini memungkinkan sistem untuk terus
berfungsi - bahkan jika suatu proses menghentikan sambil memegang kunci.
Beberapa operasi atom lainnya dapat digunakan untuk
memberikan mutual exclusion struktur data, yang paling terkenal adalah
Bandingkan-Dan-Swap (CAS). CAS dapat digunakan untuk mencapai saling
pengecualian menunggu gratis untuk setiap struktur data bersama dengan membuat
daftar link di mana setiap node merupakan operasi yang diinginkan yang akan
dilakukan. CAS kemudian digunakan untuk mengubah pointer dalam daftar terkait
selama penyisipan simpul baru. Hanya satu proses dapat berhasil dalam CAS nya,
semua proses lain mencoba untuk menambahkan node pada saat yang sama harus
mencoba lagi. Setiap proses kemudian dapat menyimpan salinan lokal dari
struktur data, dan setelah melintasi linked list, dapat melakukan setiap
operasi dari daftar pada copy lokal.
Solusi
Software.
Selain solusi perangkat keras yang didukung, beberapa
solusi perangkat lunak yang ada yang menggunakan sibuk menunggu untuk mencapai
saling pengecualian. Contoh ini meliputi:
·
Algoritma
Dekker
·
Algoritma
Peterson
·
Lamport
bakery algoritma.
·
Algoritma
Szymanski
·
Algoritma
roti hitam-putih Taubenfeld itu.
Algoritma ini tidak bekerja jika eksekusi out-of-order
yang digunakan pada platform yang mengeksekusi mereka. Programmer harus
menentukan memesan ketat pada operasi memori dalam thread.
Hal ini sering lebih baik untuk menggunakan fasilitas
sinkronisasi yang disediakan oleh multithreading perpustakaan sistem operasi,
yang akan mengambil keuntungan dari solusi perangkat keras jika memungkinkan,
tetapi akan menggunakan solusi perangkat lunak jika tidak ada solusi perangkat
keras yang ada. Misalnya, ketika perpustakaan kunci sistem operasi yang
digunakan dan benang mencoba untuk memperoleh kunci sudah diperoleh, sistem
operasi dapat menangguhkan benang menggunakan saklar konteks dan swap keluar
dengan benang lain yang siap untuk dijalankan, atau bisa menempatkan prosesor
ke dalam keadaan daya rendah jika tidak ada thread lain yang dapat dijalankan.
Oleh karena itu, metode saling pengecualian yang paling modern berusaha untuk
mengurangi latensi dan sibuk-menunggu dengan menggunakan antrian dan konteks
switch. Namun, jika waktu yang dihabiskan menangguhkan benang dan kemudian
mengembalikan itu dapat terbukti selalu lebih dari waktu yang harus menunggu
untuk sebuah thread untuk menjadi siap untuk menjalankan setelah diblokir dalam
situasi tertentu, maka spinlocks adalah denda solusi (untuk situasi yang
hanya).
Mutual
exclusion canggih
Solusi yang dijelaskan di atas dapat digunakan untuk
membangun sinkronisasi primitif di bawah ini:
·
Kunci
·
Mutexes
reentrant
·
Semaphore
·
Monitor
·
Message
passing
·
Ruang tupel
Banyak bentuk mutual exclusion memiliki efek samping.
Misalnya, Semaphore klasik mengizinkan deadlock, di mana satu proses
mendapatkan semaphore, proses lain mendapat semaphore kedua, dan kemudian
keduanya menunggu selamanya untuk semaphore lainnya akan dirilis. Lain efek
samping umum termasuk kelaparan, di mana proses pernah mendapat sumber daya
yang cukup untuk menjalankan sampai selesai, inversi prioritas, di mana thread
prioritas yang lebih tinggi menunggu thread prioritas rendah, dan "latency
tinggi", di mana respon terhadap interupsi adalah tidak cepat.
Banyak penelitian yang bertujuan untuk menghilangkan
efek di atas, sering dengan tujuan menjamin kemajuan non-blocking. Tidak ada
skema yang sempurna dikenal. Memblokir sistem panggilan digunakan untuk tidur
seluruh proses. Sampai panggilan tersebut menjadi benang aman, tidak ada
mekanisme yang tepat untuk tidur satu thread dalam proses .
Kunci eksklusif Reksa pada objek memori (dalam konteks
ini berbagi proses / benang memori) yang diperlukan seperti pada objek database
(kunci file). Tentu saja, objek database dapat memiliki non-eksklusif (baca)
kunci dan karenanya David Hostettler Wain diusulkan nonexs - kunci memori
non-eksklusif pada tahun 2006. Ini masih belum diterapkan secara luas.
No comments
Post a Comment