Mutual Exclusion dan Deadlock

MUTUAL EXCLUSION

Pentingnya Mutual Exclusion

Mutual exclusion adalah persoalan untuk menjamin hanya ada satu proses yang mengakses sumber daya pada suatu interval waktu tertentu. Pentingnya mutual exclusion dapat dilihat pada dua ilustrasi berikut .

1)      Ilustrasi  printer daemon

Daemon untuk printer adalah proses penjadwalan dan pengendalian untuk mencetak berkas-berkas di printer sehingga menjadikan seolah-olah printer dapat digunakan secara  simultan oleh proses-proses. Daemon untuk printer mempunyai tempat penyimpanan di harddisk ( disebut spooler) untuk menyimpan berkas-berkas yang akan dicetak . Direktori spooler itu terbagi ddalam sejumlah slot. Slot berisi satu berkas yang akan dicetak . Terdapat variabel in yang menunjuk slot bebas di ruang harddisk yang dipakai untuk menyimpan berkas yang hendak dicetak.

Perhatikan program dibawah ini :

1

Skenario yang membuat  situasi kacau

Misal A dan B ingin mencetak berkas , variabel in bernilai 9

2

Skenario

Proses A membaca variabel in bernilai 9 . Belum sempat A mengerjakan proses , penjadwal menjadwalkan proses B berjalan . Prose B yang juga ingin mencetak segera membaca variabel in , variabel in masih bernilai 9. Proses B dapat menyelesaikan prosesnya . Proses B menyimpan berkas B di slot 9. Proses a dijadwalkan kembali dan segera menyimpan berkas A di slot 9. Berkas B tertimpa berkas A , B tidak akan pernah mendapat cetakan.

Pada contoh , terdapat kondisi yaitu 2 proses atau lebih sedang membaca atau menulis data bersama ( yaitu variabel in) dengan hasil akhir bergantung jalanya proses-proses . hasil akhir tidak bisa diprediksi , kondisi yang tidak dapat diprediksi hasilnya bergantung pada jalanya proses-proses yang bersaing disebut kondisi pacu ( race condition) Kondisi pacu harus dihilangkan agar hasil dapat diprediksi dan tidak bergantung jalanya proses-proses itu.

Pokok penyelesaian  permasalahan adalah sisitem harus mencegah lebih dari satu proses membaca atau menulis data bersama disaat yang bersamaan karena bagian program yang sedang mengakses memori atau sumber daya yang dipakai bersama dapat menimbulkan kondisi pacu/critical section/region.

Kesuksesan proses-proses konkuren memerlukan pendefinisian critical section dan memaksakan mutual exclusion diantaraproses-proses konkuren yang sedang berjalan . Penyelesaian mutual exclusion merupakan landasan pemrosesan konkuren.

2)      Ilustrasi Aplikasi Tabungan

Seluruh sistem yang melibatkan banyak proses mengakses satu sumber daya bersama selalu menimbulkan masalah mutual exclusion.

Contoh :

Pada aplikasi tabungan , misalnya rekening A berisi Rp1.000.000,-  yang terdaftar di kantor cabang di bandung.

Pada suatu saat program aplikasi kantor cabang di jakarta melayani penyetoran Rp3.000.000,- ke rekening a. Program aplikasi membaca saldo akhir rekening A.

Pada waktu hampir bersamaan , di kantor cabang Bandung juga terjadi transaksi penyetoran Rp5.000.000,- ke rekening A . Program aplkasi di Bandung membaca saldo A masih Rp1.000.000,-

Beberapa skenario dapat terjadi bila mutual exclusion tidak terjamin yaitu :

1)      Program aplikasi Bandung menulis ke rekening A secara cepat sehingga dihasilkan saldo Rp6.000.000,_ Setelah itu , program aplikasi kantor cabang jakarta menimpa hsil itu dengan saldo Rp4.000.000,- hasil akhir yang diperoleh adalah Rp4.000.000,- bukan Rp10.000.000,- (yang seharusnya).

2)      Program aplikasi Jakarta dilakukan menulis rekening A secara cepat sehingga dihasilkan saldo Rp4.000.000,- Setelah itu program aplikasi di kantor Bandung menimpa hasil itu dengan saldo Rp6.000.000,- hasil yang lebih baik dibandingkan skenario pertama tetapi masih di bawah yang seharusnya yaitu Rp10.000.000,-

Kriteria Penyelesaian mutual exclusion

Kemampuan menjamin mutual exclusion harus memeuhi kriteria-kriteria berikut : [TAN-92,STA-95]

1)      mutual exclusion harus dijamin

2)      Hanya satu proses pada satu saat yang diizinkan masuk critical section. Proses-proses lain dlarang masuk critical section yang sama pada saat telah ada proses yang masuk critical section itu.

3)      Proses yang berada di noncritical section , dilarang memblock proses-proses lain yang ingin masuk critical section.

4)      Harus dijamin proses yang ingin masuk critical section tidak menunggu selama waktu yang tidak terhingga . Atau tak boleh terdapat deadlock atau starvation .

5)      Ketika tidak ada proses di critical section maka proses yang ingin masuk critical section  harus diizinkan segera masuk tanpa waktu tunda.

6)      Tidak ada asumsi mengenai kecepatan relatif proses atau jumlah proses yang ada.

Kriteria 1 merupakan kriteria mutlak yang harus dipenuhi. Metode yang melanggar kriteria 1 tidak bisa digunakan. Pelanggaran kriteria lain , masih bisa digynakan tetapi kita wajib berhati-hati.

 

 

Metode-Metode Penjaminan mutual exclusion

1)      Metode Naif

Metode ini disebut metode naif kkarena tidak menyelesaikan masalah mutual exclusion.

  • Metode Variabel lock sederhana

Metode ini sederhana , meniru mekanisme penguncian pintu bahwa kunci pintu diganti variabel lock . Variabel lock bernilai 0 berarti pintu tidak terkunci , bernilai 1 berarti pintu terkunci. Metode ini gagal karena analoinya tidak sepenuhnya sama.

Mekanisme yang diiusulkan

Ketika prosesss hendak masuk mutual exclusion , proses lebih dulu memeriksa variabel lock dengan ketentuan sebagai berikut :

  • Jika variabel lock bernilai 0,proses menge-set variabel lock menjadi 1 dan segera masuk mutual exclusion
  • Jika variabel lock bernilai 1, proses menunggu sampai nilai variabel lock menjadi 0 ( situasi ini berarti sedang terdapat proses lain di mutual exclusion )

3

Skenario yang membuat situasi kacau

Metode tidak dapat digunakan karena skenario di bawah ini dapat terjadi. Perhatikan skenario di gambar 6-2 berikut ini.

4

Metode ini tidak menjamin proses memasuki critical section yang telah dimasui proses lain . Saat proses A telah membaca variabel lock dan sebelum men-set variabel lock dan sebelum menset variabel lock menjadi 1 , penjadwal dapat menjadwalkan proses B. Proses B pun membaca variabel lock yang masih bernilai 0 dan masuk critical section . Penjadwal kemudian menggilir A lagi , karena telah membaca variabel lock bernilai 0 maka proses A pun segera masuk critical section yang sedang dimasuki B . Secara bersamaan A dan B masuk critical section yang sama . Kriteria 1 terlanggar , metode ini sama sekali tidak bisa digunakan.

2)      Metode untuk situasi tertentu

1)      Metode Bergantian secara ketat

Metode ini mengasumsikan dapat menggilir proses-proses yang hendak masuk critical section secara bergantian terus-menerus . Perhatikan program di bawah ini.

5

Variabel turn (giliran)

Variabel turn mencatat (nomor) proses yang sedang masuk critical section. Variabel turn diinisialisasi 0.

Skenario yang terjadi adalah :

  • Proses 0 memeriksa variabel turn , bernilai 0 dan segera memasuki critical section.
  • Proses 1 , menemukan variabel turn bernilai 0 , melakukan loop memeriksa variabel turn terus-menerus , memeriksa apakah turn telah bernilai 1.

Busy waiting

Kondisi memeriksa variabel terus-menerus , menunggu sampai satu nilai muncul disebut busy waiting. Kalau busy waiting berlangsung lama , cara ini harus dihindari karena banyak menyiakan waktu pemroses. Hanya kalau selang waktu menunggu singkat maka metode dengan busy waiting bisa digunakan.

Skenario yang membuat situasi kacau

Skenario berikut dapat terjadi . Misal proses  0 adalah proses cepat , proses 1 adalah proses lambat. Gambar -3 menunjukkan skenario yang membuat metode gagal.

6

Skenario terlanggarnya mutual exclusion dengan metode bergantian

 

Skenario pelanggaran adalah:

  • Proses 0 meninggalkan critical_section, men-set turn 1, menginjinkan proses 1 memasuki critical_section.
  • Proses 1 mengakhiri critical_section dengan cepat maka keduanya berada di noncritical_section dengan variable turn bernilai 0.
  • Proses 0 kembali memasuki critical_section dengan cepat dan dengan segera memasuki noncritical_section maka variable turn bernilai 1.
  • Proses 0 hendak kembali memasuki critical_section tapi variable turn bernilai 1.

Proses 1 di non_critical_section memblok proses 0 sehingga tidak dapat memasuki critical_section. Metode ini melanggar criteria 2, yaitu proses dapat di blok oleh proses yang tidak sedang berada di critical_section.

Metode ini masih dapat digunakan selama diketahui memang proses-proses harus secara bergantian memasuki critical section. Ciri-ciri ini adalah untuk aplikasi batch sekuen (sequential-batch application) seperti pada kompilator dengan banyak pass.

 

 Metode Dengan Busy Waiting

 Metode penyelesaian Dekker

 

Implementasi mutual exclusion secara perangkat lunak yang sukses pertama kali diberikan Dekker, matematikawan Belanda.

Perhatikan program penyelesaian Dekker berikut ini:

78

Algoritma Dekker untuk menyelesaikan mutual-exclusion adalah rumit. Algoritma Dekker mempunyai properti-properti berikut:

  • Tidak memerlukan instruksi-instruksi perangkat keras khusus.
  • Proses yang beroperasi di luar critical section tidak dapat mencegah proses lain memasuki critical section itu.
  • Proses yang ingin masuk critical section akan segera masuk bila dimungkinkan.

Program sulit diikuti dan pembuktian kebenarannya memerlukan kecerdikan. Peterson member penyelesaian sederhana dan elegan terhadap persoalan mutual exclusion.

Metode Penyelesaian Peterson

Penyelesaian Peterson adalah sebagai berikut:

 910

 

Mekanisme kerja Peterson adalah sebagai berikut:

Sebelum masuk critical_section, proses memanggil enter_critical_section. Sebelum memanggil enter_critical_section, proses memeriksa sampai kondisi aman untuk enter_critical_section. Terjadi busy Waiting. Setelah selesai di critical section, proses menandai pekerjaan telah selesai dan mengizinkan proses lain masuk.

Skenario

Keadaan awal adalah tidak ada proses di critical_section. Proses o akan masuk critical section. Proses menandai elemen array-nya dan menge-set turn ke o. Proses memeriksa kondisi untuk masuk critical region. Karena proses 1 tidak berkepentingan (elemen interested tidak di tandai) maka prosedur enter_critical_section segera dilaksanakan.

Jika kemudian, proses 1 akan masuk critical section. Proses akan menunggu sampai interested[0] menjadi FALSE. Kondisi ini hanya terjadi ketika proses 0 menge-set elemen itu yaitu ketika keluar dari critical section. Metode ini terjadi busy waiting, yaitu proses harus menghabiskan jatahnya untuk memeriksa kondisi.

Skenario proses o dan 1 memanggil enter_critical_section hamper simultan

Keduanya menyimpan normor proses di turn, yang terakhir dipertimbangkan, yang terdahulu hilang karena ditimpa. Misalnya, proses 1 menyimpan lebih akhir maka turn bernilai 1. Ketika kedua proses mengeksekusi pernyataan while, proses o mengeksekusi o kali dan memasuki critical_section. Proses 1 loop dan tidak memasuki critical_section.

Dengan algoritma Peterson, proses-proses dapat masuk critical section dengan aman tanpa terganggu proses lain. Penyelesaian Peterson dapat di generalisasi untuk banyak proses konkuren secara mudah, tidak Cuma untuk dua proses.

Metode dengan Dukungan Perangkat Keras

Metode Pematian Interupsi

 

Proses mematikan interupsi ke pemroses dan segera memasuki critical section. Proses kembali pengaktifan interupsi segera setelah meninggalkan critical section .

Cara pematian interupsi mengakibatkan:

  • Pemroses tidak dapat beralih ke proses lain karena interupsi clock dimatikan sehingga penjadwal pun tidak dieksekusi. Karena penjadwal tidak beroperasi maka tidak terjadi alih proses.
  • Proses dapat memakai memori bersama tanpa takut intervensi proses lain karena memang tidak ada proses lain yang dieksekusi saat itu.

Kelemahan Utama

  • Bila proses yang mematikan interupsi mengalami gangguan (yaitu crash) maka proses tidak akan pernah menghidupkan interupsi kembali. Kejadian ini mengakibatkan kematian seluruh system.
  • Jika terdapat dua pemroses atau lebih, mematikan interupsi hanya berpengaruh pada pemroses yang mengeksekusi instruksi itu. Pematian interupsi tidak memengaruhi pemroses-pemroses lain. Pemroses-pemroses lai masih bebas memasuki critical section yang sedang dimasuki proses lain di pemroses-pemroses lain. Teknik ini tidak dapat di terapkan pada system multiprocessor.

Teknik mematikan interupsi dapat digunakan untuk proses-proses kernel (di system uniprocessor) yang sangat kritis yang tidak boleh di intervensi proses lain seperti saat memodifikasi PCB. Teknik pematian interupsi ini tidak cocok untuk mekanisme mutual exclusion pada proses-proses pemakai.

Pemroses Intel mendukung mekanisme ini dengan menyediakan instruksi berikut:

  • cli – mematikan interupsi
  • sti – mengaktifkan kembali interupsi

Interupsi tersebut hanya dapat dijalankan proses yang berkewenangan tinggi.

Metode dengan instruksi test and set lock

Pada system multiprocessor, pemroses-pemroses bertindak independent. Interupsi di satu pemroses tidak mempengaruhi pemroses- pemroses lain. Pemroses- pemroses yang memakai memori bersama maka pengaksesan terhadap suatu memori dijaga pada tingkat perangkat keras agar pemroses lain tidak boleh meakses suatu lokasi yang sama disaat yang sama.

Perancang perangkat keras menyediakan instruksi-instruksi atomic yang tidak dapat di interupsi, instruksi dilaksanakan sampai selesai. Instruksi ini biasanya dilaksanakan dengan cara mengunci bus sehingga pemroses- pemroses lain tidak dapat menggunakan bus. Pemroses yang mengunci bus dengan leluasa membaca dan/atau memodifikasi suatu lokasi memori.

Instruksi-instruksi dirancang untuk menyelesaikan mutual exclusion di system multiprocessor. Beragam instruksi disediakan perancang pemroses guna membantu implementasi mutual exclusion. Di antara instruksi-instruksi itu adalah

  • tsl (test and set lock)
  • tas atau ts (test and set), digunakan IBM S/360, keluarga Motorola M68000, dan lain-lain
  • cs (compare and set), digunakan IBM 370 series
  • xchg (exchange), digunakan intel x86
  • dan sebagainya.

Instruksi tsl (test and set lock)

Instruksi ini membaca isi memori ke register dan kemudian menyimpan nilai bukan nol ke alamat memori itu. Operasi membaca isi memori dan menyimpan ke memori atomic dijamin tidak dapat diinterupsi. Tidak ada pemroses lain yang dapat mengakses memori itu sampai instruksi berakhir. Pemroses yang mengkesekusi instruksi tsl mengunci bus memori, mencegah pemroses- pemroses lain mengakses memori.

Dengan instruksi tsl, kita dapat menggunakan flag untuk koordinasi pengaksesan ke memori bersama. Ketika flag bernilai 0, proses boleh menge-set-nya menjadi 1 menggunakan instruksi tsl dan kemudian masuk critical section. Ketika telah selesai dengan critical region, proses menge-set flag dengan 0.

Dengan adanya instruksi ini maka dapat dibuat prosedur

  • prosedur tsl_to_critical_section
  • prosedur tsl_leave_critical_section

prosedur-prosedur itu adalah sebagai berikut:

11

Maka program untuk mutual exclusion dengan instruksi tsl adalah sebagai berikut:

1213

Sebelum masuk critical section, proses memanggil tsl_to_critical_section yang melakukan busy waiting sampai flag terbebas. Setelah selesai dengan critical section, proses memanggil tsl_leave_section yang menyimpan 0 ke flag agar proses lain dapat memasuki critical section itu.

Metode dengan instruksi Exchange (XCHG)

Instruksi Exchange (xchg)

Instruksi xchg disediakan mesin. Intel menyediakan instruksi ini. Instruksi ini menukarkan dua isi memori. Dalam pascal instruksi itu dapat di tulis sebagai berikut:

14

Operasi pembacaan dan penukaran itu di pandang sebagai atomik, tidak dapat disela. Instruksi dapat digunakan untuk implementasi mutual exclusion. Dengan instruksi xchg tersebut dapat dibuat

  • prosedur Xchg_to_critical_section
  • prosedur Xchg_leave_critical_section

prosedur- prosedur itu sebagai berikut:

15

maka program mutual exclusion dengan xchg adalah sebagai berikut:

16

Sebelum mengeksekusi seluruh proses maka flag diinisialisasi dengan nilai 0. Proses sebelum masuk critical_section, proses menge-set dengan kunci (key) proses itu sebagai 1 kemudian memanggil xchg_to_enter_section. Proses melakukan busy waiting sampai terbebas. Selesai dengan critical section, proses memanggil xchg_leave_critical_section menukarkan nilai 0 ke flag agar proses lain dapat memasuki critical section itu.

Karakteristik Pendekatan dengan Instruksi Mesin

Penggunaan instruksi mesin untuk memaksakan mutual exclusion mempunyai keunggulan dan kelemahan.

Keunggulan

  • sederhana dan mudah di verifikasi.
  • Dapat diterapkan ke sembarang jumlah proses baik di pemroses tunggal maupun banyak pemroses yang memakai memori bersama.
  • Dapat digunakan untuk mendukung banyak critical region, masing-masing critical region didefinisikan dengan suatu variable.

Kelemahan Serius

  • Merupakan metode dengan Busy waiting, sangat tidak efisien. Selagi proses menunggu memasuki critical region, proses berlanjut mengkonsumsi waktu pemroses.
  • Adanya busy waiting memungkinkan deadlock dan startvation.

Dampak Adanya Busy Waiting

Metode metode dengan busy waiting mempunyai keterbatasan yaitu tidak dapat diterapkan pada system dengan penjadwalan berprioritas. Pada system – system dengan penjadwalan berprioritas, metode dengan busy waiting dapat menimbulkan deadlock.

Aturan penjadwalan berprioritas selalu menjadwalkan proses – proses berprioritas lebih tinggi di antrian proses Ready.

Misalnya terdapat dua proses,

  1. Proses H berprioritas tinggi
  2. Proses L berprioritas rendah

Maka penjadwalan berprioritas akan selalu menjadwalkan H bila proses H Ready.

Perhatikan scenario berikut:

  • Saat L masuk critical section.
  • H menjadi Ready (yaitu operasi masukan/keluaran proses H selesai dilayani).
  • H segera dijadwalkan dan ingin masuk critical section.
  • Karena ingin masuk critical region yang telah dimasuki L maka H dalam busy waiting menunggu L keluar dari critical section.
  • Tapi karena L tidak pernah di jadwalkan saat proses H Ready yang lebih tinggi prioritasnya daripada L maka L tidak pernah berkesempatan keluar dari critical section.
  • H loop selamanya dan L tidak pernah dijadwalkan. H dan L saling menunggu. H menunggu L keluar dari critical section, L menunggu H selesai agar dapat dijadwalkan dan keluar dari critical section.
  • H dan L tidak pernah membuat kemajuan apapun setelah itu terjadilah deadlock yakni H dan L tidak membuat kemajuan apapun.

 

Metode dengan Semaphore

Karenan terdapat kelemahan yang tidak dapat diterima dari metode dengan busy waiting maka perlu dicari metode metode lain.

Deskripsi Semaphore

Semaphore dikemukanan Dijkstra[DIJ-65]. Prinsip semaphore sebagai berikut:

Dua proses atau lebih dapat bekerja sama dengan menggunakan penanda – penanda sederhana. Proses dipaksa berhenti sampai proses memperoleh penanda tertentu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan struktur penanda yang sesuai dengan kebutuhannya. Variable khusus untuk penandaan ini disebut semaphore.

Semaphore mempunyai dua property yaitu:

  1. Semaphore dapat diinisialisasi dengan nilai bukan negative.
  2. Terdapat dua operasi terhadap semaphore yaitu Down dan Up. Kata asli yang disampaikan Dijkstra adalah operasi P dan V.

Operasi Down

Operasi ini menurunkan nilai semaphore. Jika nilai semaphore menjadi bukan positif maka proses yang mengeksikusinya di block.

Misalnya semaphore sederhana berupa bilangan bulat.

17

Operasi down adalah atomic (atomic action), tidak dapat diinterupsi sebelum selesai. Menurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan mem-block sebagai instruksi tunggal. Sejak dimulai, tidak ada proses lain yang mengakses semaphore sampai operasi selesai atau di-block.

Operasi Up menaikkan nilai semaphore. Jika satu proses atau lebih telah di-block pada suatu semaphore tidak dapat menyelesaikan operasi Down maka salah satu dipilih oleh sistemdam dibolehkan menyelesaikan operasi Down-nya. Urutan dan sebagainya sesuai keperluan dan kepentingan system.

Deskripsi lebih formal adalah

18

Operasi Up menaikkan nilai semaphore, memindahkan dari antrian dan menempatkan satu proses ke senarai Ready tidak dapat diinterupsi.

Mutual Exclusion dengan Semaphore

Adanya semaphore mempermudah persoalan mutual exclusion. Skema penyelesaian mutual exclusion mempunyai began sebagai berikut:

19

Sebelum masuk critical section, proses melakukan Down. Bila berhasil maka proses masuk critical section. Bila tidak berhasil maka proses di-Block pada semaphore itu. Proses yang di-block akan melanjutkan kembali bila proses yang berada di critical section keluar dan melakukan operasi Up dan menjadikan proses yang di-block menjadi Ready dan berlanjut sehingga operasi Down-nya berhasil.

Implementasi Semaphore

Operasi Up dan Down adalah promitif atomic. Beragam skema dapat diterapkan untuk implementasi Up dan Down. Esensi masalah implementasi adalah menjamin mutual exclusion variable semaphore, yaitu hanya mengizinkan satu proses pada satu saat yang boleh memanipulasi semaphore.

Skema implementasi dapat dilakukan secara perangkat lunak atau dengan dukungan perangkat keras.

Dengan Pematian Interupsi

Sistem operasi mematikan interupsi selagi memeriksa semaphore, memperbarui dan menjadikan proses di-block. Karena semua aksi hanya memerlukan beberapa interuksi, pematian interupsi tidak merugikan.

 20

Dengan Instruksi Isi

Pada banyak pemroses, tiap semaphore dilindungi variable lock dan instruksi tsl agar menjamin hanya satu pemroses yang saat itu memanipulasi semaphore.

21

Deadlock

          Deadlock adalah keadaan dimana dua program memegang kontrol terhadap sumber daya yang dibutuhkan oleh program yang lain. Tidak ada yang dapat melanjutkan proses masing-masing sampai program yang lain memberikan sumber dayanya, tetapi tidak ada yang mengalah.

Deadlock yang mungkin dapat terjadi pada suatu proses disebabkan proses itu menunggu suatu kejadian tertentu yang tidak akan pernah terjadi. Dua atau lebih proses dikatakan berada dalam kondisi deadlock, bila setiap proses yang ada menunggu suatu kejadian yang hanya dapat dilakukan oleh proses lain dalam himpunan tersebut.

Proses terlibat didalam deadlock jika proses menunggu suatu kejadian tertentu yang tidaka akan pernah terjadi. Sekumpulan proses berkondisi deadlock bila setiap proses yang berada di kumpulan itu menuggu suatu kejadian yang hanya dapat menunggu kejadian yang tidak akan pernah terjadi.

Deadlock terjadi ketika proses – proses mengakses sumber daya secara eksklusif. Semua deadlock yang terjadi melibatkan persaingan untuk memperoleh sumberdaya ekslusif oleh dua proses atau lebih.

Terjadi trade-off antara overhead mekanisme penyelesaian deadlock dan manfaat manfaat yang diperoleh. Pada bebarapa kasus, ongkos yang harys di bayar untuk membebaskan system dari peristiwa deadlock adalah sangat mahal. Pada kasus – kasus tertentu seperti pada system pengendalian proses waktu nyata (real-time process control system) maka tidak ada pilihan lain kecuali harus membayar semua kemahalan itu karena keberadaan deadlock akan mengakibatkan kekacauan system.

Model deadlock

Untuk kejadian operasi perangkat masukan/keluaran adalah

  • Meminta (request)                         : Meminta layanan perangkat masukkan/keluaran.
  • Memakai (use)                                 : Memakai perangkat masukkan/keluaran.
  • Melepaskan(release)                     : Melepaskan pemakaian perangkat masukkan/keluaran.

Model deadlock dua proses dan dua sumber daya. Deadlock dapat digambarkan sebagai graph.

Misalnya:

  • Dua proses P0 dan P1
  • Dua sumber daya R0 dan R1

Gambar menunjukkan model graph permintaan dan alokasi sumber daya.

P0 meminta sumber daya R0, ditandai busur berarah dari proses P0 ke sumber daya R0. Pada gambar kedua sumberdaya R1 dialokasikan P1, ditandai busur berarah dari sumber daya R1 ke proses P1.

 

Skenario yang menimbulkan deadlock

Dapat terjadi scenario berikut:

  • P0 dialokasikan R0
  • P1 dialokasikan R1

Skenario ini di gambarkan pada gambar pertama diatas

Kemudian

  • P0 sambil masih menggenggam Ro, meminta R1.
  • P1 sambil masih menggenggam R1, meminta R0.

Kejadian ini mengakibatkan deadlock karena sama – sama proses Po dan P1 akan saling menunggu. Graph deadlock ini digambarkan seperti gambar di bawah ini. Terjadinya deadlock ditandai munculnya (terjadinya) graph melingkar.

Deadlock tidak hanya terjadi pada dua proses dan dua sumber daya, deadlock dapat terjadi dengan melibatkan lebih dari dua proses dan dua sumber daya.

Syarat – syarat Perlu bagi Terjadinya Deadlock

Coffman, at al. [Cof-71] menyatakan empat syarat terjadinya deadlock yaitu;

  1. Mutual exclusion (mutual exclution condition).
  2. Kondisi genggam dan tunggu (hold and wait condition).
  3. Kondisi non-preemtion (non-preemtion condition).
  4. Kondisi menunggu secara sirkuler (circular wait condition).

Mutual Exclution (Mutual Exclution Condition)

Sumber daya saat itu diberikan pada tepat satu proses.

Kondisi genggaman dan tunggu (hold and wait condition)

Proses yang sedang menggenggam sumber daya, menunggu sumber daya-sumber daya baru.

Kondisi non-preemption (non-preemption condition)

Sumber daya-sumber daya yang sebelumnya diberikan tidak dapat diambil paksa dari proses yang sedang menggenggamnya. Sumber daya-sumber daya harus secara eksplisit dilepaskan dari proses yang menggenggamnya.

Kondisi menunggu secara Sirkuler (circular wait condition)

Harus terdapat rantai sirkuler dari dua proses atau lebih, masing-masing menunggu sumber daya yang digenggam oleh anggota berikutnya pada rantai itu.

Ketiga syarat pertama merupakan syarat perlu (necessary conditians) bagi terjadinya deadlock. Keberadaan deadlock selalu berarti terpenuhi ketiga kondisi itu. Tidak mungkin terjadi deadlock bila tidak ada ketiga kondisi itu. Deadlock terjadi berarti terdapat ketiga syarat itu tetapi adanya ketiga kondisi itu belum berarti terjadi deadlock.

Deadlock baru benar-benar terjadi bila kondisi keempat terpenuhi. Kondisi keempat merupakan keharusan bagi terjadinya peristiwa deadlock tidak terjadi.

 

Metode-metode mengatasi Deadlock

Ragam metode untuk mengatasi deadlock dapat dikelompokkan menjadi tiga, yaitu:

  1. Metode pencegahan terjadinya deadlock (deadlock prevention)
  2. Metode penghindaran terjadinya deadlock (deadlock avoidance)
  3. Metode deteksi dan pemulihan dari deadlock (deadlock detection and recovery)

Metode pencegahan terjadinya Deadlock (deadlock prevention)

Metode ini berkaitan dengan pengkondisian system sehingga menghilangkan kemungkinan terjadinya deadlock. Pencegahan merupakan solusi yang bersih dipandang dari sisi tercegahnya deadlock. Namun metode ini sering menghasilkan penggunaan sumber daya yang buruk.

Pencegahan deadlock merupakan metode yang banyak dipakai.

Metode penghindaran terjadinya Deadlock (deadlock avoidance)

Tujuan metode ini adalah menghindarkan kondisi-kondisi yang paling mungkin menimbulkan deadlock agar memperoleh utilitasasi sumber daya yang lebih baik. Penghindaran bukan berarti menghilangkan semua kemungkinan terjadinya deadlock. Secara teoretis, deadlock dimungkinkan. System operasi memeriksa semua permintaan sumber daya secara hati-hati. Jika system operasi mengetahui bahwa alokasi sumber daya menimbulkan risiko deadlock, system menolak pengaksesan itu. Dengan itu menghindari terjadinya deadlock.

Metode deteksi dan pemulihan dari Deadlock (deadlock detection and recovery)

Metode deteksi digunakan pada system yang mengijinkan terjadinya deadlock. Tujuan metode ini adalah memeriksa apakah telah terjadi deadlock dan menentukkan proses-proses dan sumber daya-sumber daya yang terlibat deadlock secara presisi. Begitu telah dapat ditentukan, system dipulihkan dari deadlock dengan metode pemulihan.

Metode pemulihan dari deadlock berupaya untuk menghilangkan deadlock dari system sehingga system beropasi kembali, bebas dari deadlock. Proses-proses yang terlibat deadlock mungkin dapat menyelesaikan eksekusi dan membebaskan sumber daya-sumber dayanya.

 

 Strategi Burung Unta

Strategi ini mengasumsikan kejadian deadlock jarang terjadi dibandingkan kejadian computer mengalami crash. Mengapa bersusah payah berupaya mengatasi deadlock? Toh, system lebih sering rusak karena crash. Strategi ini disebut strategi burung unta karena kabar yang telah tersebar (yang sebenarnya tidak benar) bahwa burung unta akan menyembunyikan kepalanya ke tanah bila mengetahui adanya bahaya yang mengancamnya.

Disebut strategi burung unta apabila solusi yang dilakukkan justru sebenarnya tidak mempedulikan adanya masalah. Strategi ini berarti sama sekali tidak berusaha untuk mengatasi deadlock atau sama sekali tidak ada metode yang diterapkan untuk mengatasi masalah deadlock.

 

Pencegahan Deadlock

Havender [HAV-68] mengemukakan bahwa jika sembarang syarat dari keempat syarat terjadinya deadlock tidak terpenuhi maka tidak akan terjadinya deadlock. Havender menyarankan strategi-strategi berikut untuk meniadakan syarat-syarat tersebut, yaitu:

  • Tiap proses harus meminta semua sumber daya yang yang diperlukan sekaligus dan tidak berlanjutan sampai semuanya diberikan.
  • Jika proses telah sedang memegang sumber daya tertentu, untuk permintaan berikutnya proses harus melepas dulu sumber daya yang dipegangnya. Jika diperlukan, proses meminta kembali sekaligus dengan sumber daya yang baru.
  • Memberi pengurutan linear terhadap tipe-tipe sumber daya pada semua proses, yaitu jika proses telah dialokasikan suatu tipe sumber daya, proses hanya boleh berikutnya meminta sumber daya-sumber daya tipe pada urutan yang berikutnya. Saran yang diberikan Havender merupakan cara meniadakan salah satu dari syarat perlu. Syarat perlu pertama jelas tidak bias ditiadakan kalau tidak menghendaki kekacauan hasil.

 

Meniadakan Mutual Exsklusion

Deadlock disebabkan terdapatnya pengaksesan aksklusif terhadap sumber daya. Jika tidak ada sumber daya eksklusif untuk satu proses tunggal maka tidak pernah akan dijumpai deadlock: cara yang dapat ditempuh untuk mengakali pengaksesan eksklusif adalah melakukan spooling perangkat-perangkat yang harus didedikasikan ke suatu proses. Pengaksesan sumber daya seolah-olah tidak tidak eksklusif walau sebenarnya tetap eksklusif, hanya dengan spooling berarti permintaan-permintaan itu diantrikan di harddisk. Job-job diantrian spooler akan dilayani satu per satu.

Terdapat masalah terhadap teknik ini adalah

  • Tidak setiap sumber daya eksklusif dapat di-spooling, misalnya table proses.
  • Kompetisi terhadap ruang harddisk untuk spooling dapat menuntun ke deadlock. Abstraksi ini sebenarnya berarti kembali terdi kondisi yang mengharuskan mutual exclusion namun mutual exclusion menjadi di level lebih bawah yaitu level suatu lokasi memori bukan lagi satu perangkat.

Mutual exclution benar-benar tidak dapat dihindari, hanya mampu diperkecil granularitas/ lama waktu berlangsungnya.

Meniadakan syarat Hold and Wait

Metode untuk meniadakan syarat hold and wait dapat dilakukan dengan cara :

  • Mengalokasikan semua sumber daya atau tidak sama sekali
  • Hold and release

Mengalokasikan semua sumber daya atau tidak sama sekali

Proses hanya dilayani permintaannya bila semua sumber daya yang diperlukan tersedia. Teknik ini berbasis pada kaidah memperoleh semua atau tidak sama sekali.

  • Jika semua sumber daya tersedia, proses dialokasikan semua sumber daya yang diperlukannya dan berjalan sampai selesai.
  • Jika tidak tersedia sedikitnya satu sumber daya maka proses harus menunggu sampai semua daya diperlukannya tersedia untuk dialokasikan padanya.

Masalah

  • Sukar mengetahui lebih dulu semua sumber daya yang diperlukan suatu proses karena di awal proses tidak diketahui berapa sumber daya yang akan diperlukan.
  • Cara ini dapat mengakibatkan penggunaan sumber daya yang sangat tidak efisien.

Cara ini dapat menjadi sangat tidak efisien

Misalnya prose memerlukan sepuluh disk maka proses meminta sepuluh disk dan menerima sepuluh disk di awal proses.

  • Jika kesepuluh disk memang diperlukan sepanjang eksekusi proses maka tidak ada pemborosan yang serius.
  • Jika proses hanya membutuhkan satu disk di awal eksekusi (atau lebih buruk lagi tanpa disk sama sekali) dan mengangurkan disk-disk lain selama beberapa jam.

Perlunya proses meminta dan menerima seluruh disk yang diperlukan sebelum eksekusi dimulai menyebabkan sumber daya – sumber daya menganggurkan harus menunggu.

Hold and release

Genggam dan lepaskan (hold and release), yaitu setiap kali terjadi permintaan suatu sumber daya maka proses harus melepas sumber daya lain yang telah digunakan. Pada satu sumber daya yang dialokasikan untuk proses.

Masalah

Teknik ini tidak mengkin sebab terdapat proses yang mensyaratkan harus memegang beberapa sumber daya sekaligus untuk melanjutkan eksekusinya. Misalnya menggambar pada plotter memerlukan plotter srta disk yang menyimpan dat gambar yang diplot.

 

 Meniadakan Non-preemption

Peniadaan non-preemption mencegah proses-proses lain harus menunggu. Selain prose menjadi preemption agar tidak ada kejadian tunggu-menunggu.

Masalah

Tidak mungkin meniadakan non-preemptive.

Misalnya; saat prose A menulis ke printer, tiba-tiba dihentikan oleh proses B yang juga akan menulis ke printer yang sama. Bila kondisi preemption ini dimungkinkan maka kedua proses akan mencetak secara tidak benar.

 

Meniadakan menunggu Sirkular

Kondisi ini dapat ditiadakan dengan bermacam cara, antara lain:

  • Proses hanya dibolehkan menggenggam satu sumber daya pada satu saat
  • Penomoran global semua sumber daya

Proses hanya dibolehkan menggenggam satu sumber daya pada satu saat

Proses hanya diperbolehkan menggengam satu sumber daya pada satu saat telah dibahas. Jika perlu sumber daya kedua, proses harus melepas sumber daya yang pertama (sama dengan hold and release).

Teknik ini tidak dimungkinkan karena terdapat proses yang mengharuskan memegang lebih dari satu sumber daya pada saat sama untuk menyelesaikan prosesnya.

Penomoran global semua Sumber daya

Proses dapat meminta proses kapanpun menginginkakan tapi permintaan harus dibuat terurut secara numeric. Cara ini tiadak akan menimbulkan siklus.

Masalah

Tidak ada cara pengurutan nomor sumber daya yang memuaskan semua pihak.

 Penghindaran Deadlock

Gagasan dasar penghindaran deadlock adalah hanya memberi akses ke permintaan sumber daya yang tidak mungkin menimbulkan deadlock. Strategi ini basanya diimplementasikan denag pengalokasian sumber daya memeriksa dampak-dampak pemberian akses ke suatu permintaan.

  • Jika pemberian akses sumber daya tidak mungkin menuju deadlock, sumber daya diberikan ke peminta.
  • Jika tidak aman (memungkinkan timbulnya deadlock), proses yang meminta biasanya terjadi setelah satu sumber daya atau lebih yang semula dipegang oleh proses-proses aktif lain dilepaskan.

Agar dapat mengevaluasi safenya sate system individu, penghindaran deadlock mengharuskan semua proses menyatakan jumlah kebutuhan sumber daya maksimum sebelum eksekusi. Begitu eksekusi dimulia, tiap proses meminta sumber daya saat diperlukan sampai batas maksimum yang dinyatakan di awal. Proses-proses yang menyatakan kebutuhan sumber daya melebihi kapasitas total system tidak dapat dieksekusi.

Pengalokasi sumber daya mencatat jumlah sumber daya teralokasi dan jumlah sumber daya masing-masing tipe, serta mencatat jumlah sumber day tersisa yang diklaim tapi belum diminta proses. Proses yang meminta sumber daya yang tidak tersedia harus menunggu sementara. Jika sumber daya yang diminta tersedia, pengelokasi sumber daya memeriksa apakah pemberian dapat menuntun ke deadlock dengan memeriksa apakah prose-proses yang telah aktif dapat secar selamat selesai. Jika dapat berakhir secara selamat, stae system setelah alokasi adalah selamat (safe) maka sumber daya dialokasikan ke proses yang meninta. Jika pemberian sumber daya mempunyai potensi menuntun ke state deadlock, maka pengalokasi sumber daya men-suspend proses yang meminta sampai sumber daya dapat diberikan dengan selamat.

Untuk penghindaran deadlock diperlukan pengertian mengenai state selamat (safe state) dan state tak selamat (unsafe state).

 State selamat dan State tak selamat

State selamat (safe state)

State dinyatakan sebagai state selamat (safe state) jika tidak deadlock dan terdapat cara untuk memenuhi semua permintaan yang ditunda tanpa menghasilkan deadlock dengan menjalankan proses-proses secara hati-hati mengikuti suatu urutan tertentu.

Contoh

Pada system 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 sumber daya. Proses C memerlukan sumber daya maksimum sebanyak 7 sedang saat ini menggenggam 3 sumber daya. Masih tersedia 4 sumber daya.

Proses

Jumlah Sumber daya yang digenggam

Maksimum sumber daya dibutuhkan

A

2

10

B

1

3

C

3

7

Tersedia                                                                                            4

gambar 7-3 Contoh state selamat (safe state)

ada cara pengurutan nomor sumber daya yang memuaskan semua pihak.

k.gang lebih dari satu sumber daya pada saat sama untuk menyel state pada gambar 7-3 dinyatakan sebagai selamat (safe) karena terdapat (dapat ditemukan) barisan pengalokasian yang dapat memungkinkan semua proses selesai. Dengan penjadwalan secara hati-hati, system dapat terhindarkan dari deadlock. Barisan tersebut adalah:

langkah 1: alokasikan empat sumber daya ke proses C, sehingga sumber daya tersedia tinggal 1 dan nantikan sampai proses C berakhir.

Proses

Jumlah Sumber daya yang digenggam

Maksimum sumber daya dibutuhkan

A

2

10

B

1

3

C

3

7

Tersedia                                                                                            0

Maka setelah proses C selesai menjadi

Proses

 

Jumlah sumber daya yang digenggam

Maksimum daya yang dibutuhkan

A 2 10
B 1 3
C 0
Tersedia                                                                        7

Langkah 2: alokasikan lima sumber daya ke proses B, nantinya proses B sampai berakhir.

Proses

 

Jumlah sumber daya yang digenggam

Maksimum daya yang dibutuhkan

A 2 10
B 1 3
C 0
Tersedia                                                                        5

Maka setelah proses B selesai menjadi

Proses

 

Jumlah sumber daya yang digenggam

Maksimum daya yang dibutuhkan

A 2 10
B 0
C 0
Tersedia                                                                        8

Langkah 3: alokasikan delapan sumber daya ke proses A,nantikan proses A sampai berakhir.

Proses

 

Jumlah sumber daya yang digenggam

Maksimum daya yang dibutuhkan

A 10 10
B 0
C 0
Tersedia                                                                        0

Maka setelah proses A selesai menjadi

Proses

 

Jumlah sumber daya yang digenggam

Maksimum daya yang dibutuhkan

A 0
B 0 0
C 0
Tersedia                                                                        0

Maka ketiga proses tersebut dengan penjadwalan hati-hati dapat menyelesaikan proses mereka dengan sempurna.

 

State tak selamat (unsafe state)

State dinyatakan sebagai state tak selamat (unsafe state) jika tidak terdapat cara untuk memenuhi semua permintaan yang saat ini ditunda dengan menjalankan proses-proses dengan suatu urutan.

Contoh

Gambar dibawah ini adalah seperti gambar 7-2 menunjukkan state selamat. State ini dapat berubah menjadi state tak selamat bila alokasi sumber daya tak terkendali.

Proses

 

Jumlah sumber daya yang digenggam

Maksimum daya yang dibutuhkan

A 2 10
B 1 3
C 3 7
Tersedia                                                                        4

State tesebut dapat menjadi state tak selamat apalagi

  • Dua permintaan sumber daya oleh proses A dilayani,kemudian
  • Permintaan satu sumber daya oleh proses B dilayani.

Maka state menjadi

Proses

 

Jumlah sumber daya yang digenggam

Maksimum daya yang dibutuhkan

A 4 10
B 2 3
C 3 7
Tersedia                                                                        1

Gambar 7-4 contoh state tak selamat (unsafe state)

State ini pada gambar 7-4 adalah state tak selamt,pada state ini tidak terdapatbarisan pengalokisian 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 sumber daya yang digenggam

Maksimum daya yang dibutuhkan
A 4 10
B 3 3
C 3 7
Tersedia                                                                        0

Maka setelah proses B selesai menjadi

Proses

 

Jumlah sumber daya yang digenggam

Maksimum daya yang dibutuhkan
A 4 10
B 0
C 3 7
Tersedia                                                                        3

Saat ini hanya tersedia tiga sumber daya sementara dua proses yang sedang aktif masing-masing membutuhkan enam dan empat sumber daya.

Rangkaian keterangan di atas adalah untuk alokasi sumber daya sejenis. Alokasi dan pengertian-pengertian mengenai state selamat dan state tak selamat dapat diperluas untuk sumber daya-sumber daya yang tak sejenis.

Perlu diingat bahwa state tak selamat bukan berarti deadlock, hanya menyatakan bahwa state tersebut berkemungkinan menuju deadlock.

Algoritma Banker oleh Dijkstra

Algoritma ini disebut algoritma Banker karena memodelkan baker di kota kecil yang berurusan dengan sekumpulan nasabah yang memohon kredit. Pada algoritma Banker ini, kondisi mutual exclusion, hold-and-wait dan  no-preemption diijinkan dan proses-proses melakukan klaim penggunaan eksklusuf sumber daya-sumber daya yang diperlukan. Proses-proses diijinkan menggenggam sumber daya-sumber daya itu tidak diijinkan di-preempt proses lain.

Proses-proses dapat meminta satu sumber daya pada suatu waktu. Sistem operasi dapat memberikan akses sumber daya ataumenolak permintaan. Jika ditolak, proses masih menggenggam sumber daya yang telah dialokasikan untuknya dan menunggu selama waktu berhingga sampai permintaannya dapat diberikan.

Sistem hanya memberikan permintaan yang menghasilkan state selamat.permintaan proses yang menghasilkan state tak selamat secara berulang ditolak sampai permintaan dapat dipenuhi. Tentunya karena sistem selalu memelihara agar dalam state safe, cepat atau lambat (yaitu dalam waktu yang berhingga) semua permintaan dapat dipenuhi dan semua proses dapat berakhir.

Implementasi algoritma ini dijelaskan secara rinci pada buku Stallings [STA-95]. Bagi yang ingin mengetahui lebih rinci, silahkan mengacu buku itu.

Kelemahan Algoritma Banker

Kelemahan algoritma Banker adalah sebagai berikut: ]TAN-92,STA-95,DEI-90]

  1. Prose-prose jarang mengetahui di awal proses jumlah maksimum sumber daya yang akan diperlukan.
  2. Jumlah proses tidak tetap, secara dinamis beragam begitu pemakai-pemakai baru login dan logout.
  3. Sumber daya yang dihitung sebagai tersedia dapat saja tiba-tiba ditinggalkan sehingga sebenarnya menjadi tidak tersedia.
  4. Proses-proses harus independen, yaitu urutan proses-proses dieksekusi tidak dibatasi kebutuhan sinkronisasi antarproses.
  5. Algoritma menghendaki memberikan semua permintaan selama waktu yang berhingga.
  6. Algoritma menghendaki client-client mengembalikan sumber daya setelah suatu waktu yang berhingga.

 

Deteksi dan Pemulihan Deadlock

Deteksi Adanya Deadlock

Deteksi  deadlock adalah teknik untuk menentukan apakah deadlock terjadi serta mengidentifikasi proses-proses dan sumber daya yang terlibat deadlock. Umumnya algoritma-algoritma deteksi yang digunakan adalah menentukan keberadaan menunggu sirkular (circular wait). Penggunaan algoritma deteksi deadlock melibatkan overhead padasaat berjalan karena secara periodik dijalankan untuk mendeteksi menunggu sirkular. Sembarang algoritma pendeteksian siklus pada graph berarah dapat digunakan.

Periode yang biasa dilakukan adalah memonitor permintaan dan pelepasan sumber daya. Setiap terdapat permintaan dan pelepasan maka dilakukan perbaruan graph dan deteksi adanya siklus. Bila terdapat siklus berarti terjadi kondisi menunggu sirkular  dan deadlock terjadi.

Pemulihan dari deadlock

Begitu sistem terdapat deadlock, deadlock harus diputuskan dengan menghilangkan satu syarat perlu atau lebih. Biasanya beberapa proses akan kehilangan sebagian atau semua kerja yang telah dilakukan. Hal ini merupakan ongkos yang harus dibayar dibanding terjadinya deadlock yang berarti semua proses tidak menghasilkan apapun. Pemulihan dari deadlock dirumitkan dengan faktor-factor tersebut:

  • Belum tentu dapat menentukan adanya deadlock secepatnya.
  • Kebanyakan sistem tidak memiliki fasilitas atau mempunyai fasilitas-fasilitas buruk untuk men-suspend proses, menghilangkan dari sistem dan me-resume proses dilain wakt. Pada sistem waktu nyata yang harus berfungsi terus-menerus, proses-proses tidak dapat di-suspend dan di-resume.
  • Bahkan jika ada kemampuan suspend dan yang efektif. Kemampuan ini melibatkan sejumlah overhead berarti dan memerlukan perhatian operator yang berkemampuan tinggi. Operator semacam ini tidak selalu tersedia.
  • Pemulihan memerlukan sejumlah kerja yang berarti.

Pada sistem operasi dengan hanya tiga state dasar (Running, Reading, Blocked),maka tidak ada cara lain kecuali dilakukan penyingkiran terhadap proses itu (kill process). Proese benar-benar hilang dari memori dan harus dimuat kembali. Pada sistem operasi modern, sistem biasanya menerapkan state suspendedBlocked dan suspendedReady, diman sumber daya dilepas tetapi proses masih di memori dan akan ditetapkan kembali sumber daya untuk proses itu begitu terjadi resume.

Teknik pemulihan yang biasa digunakan adalah menghilangkan (dengan suspend atau kill) proses-proses dari sistem dan pengklaiman kembali (reclaim) sumber daya-sumber daya yang dipegang proses-proses itu. Proses yang dihilangkan biasanya akan cacat, tapi proses-proses lain dapat menyelesaikan prosesnya.kadang perlu menyingkirkan beberapa proses sampai tidak terjadi deadlock (yaitu tidak membentuk siklus). Istilah “pemulihan” sebenarnya kurang berarti di sini karena yang terjadi sesungguhnya adalah penyingkiran beberapa proses “untuk memberi manfaat” proses-proses lain.

Pendekatan berikut dapat dilakukan untuk pemulihan deadlock. Pendekatan-pendekatan dituliskan terurut kecanggihan penyelesaiannya.[STA-95]

  1. Abaikan (singkirkan)semua proses yang terlibat deadlock. Teknik ini merupakan teknik termudah dan solusi yang sering dipilih.
  2. Back-up semua proses yang terlibat deadlock ke semua checkpoint yang didefinisikan sebelumnya dan jalankan kembali semua proses itu. Teknik ini memerlukan mekanisme rollback dan restart. Resiko pendekatan ini adalah deadlock semula dapat terjadi lagi. Tetapi karena ketidak tentuan pemrosesan konkuler, biasanya menjamin tidak akan terjadi deadlock serupa.
  3. Secara berurutan abaikan (singkirkan) proses-proses sampai deadlock tidak ada lagi. Urutan proses yang dipilih untuk disingkirkan berdasarkan kriteria ongkos minimum. Setelah masing-masing  penyingkiran,algoritma deteksi harus dijalankan untuk melihat apakah masih terdapat deadlock.
  4. Secara berurutan preempt sumber daya-sumber daya sampai tidak ada deadlock lagi. Sebagaiman item 3, pemilihan berdasarkan ongkos yang digunakan dan algoritma deteksi harus dijalankan setelah tiap preempt. Proses yang kehilangan sumber daya karena preemption harus dikembalikan (roll-back) ke titik sebelum memperoleh sumber daya.

Untuk item 3 dan 4,kriteria pemilihan proses yang akan disingkirkan atau disuspend adalah dengan kriteria-kriteria sebagai berikut:

  • Waktu pemrosesan yang telah dijalankan paling kecil.
  • Jumlah baris keluaran yang diproduksi paling kecil.
  • Mempunyai estimasi sisa waktu eksekusi terbesar.
  • Jumlah total sumber daya terkecil yang telah di alokasikan.
  • Prioritas terkecil.

Hal-hal yang harus diperhatikan dalam penyingkiran proses adalah sistem harus mengembalikan berkas-berkas yang disingkirkan ke keadaan asli karena berpengaruh terhadap konsistensi data sistem itu.

Strategi Penanggulangan Deadlock Terpadu

Tabel 7-1 dari isloor [ISL-80] memperlihatkan keunggulan dan kelemahan skema-skema penanggulangan deadlock.

Masing-masing teknik mempunyaikeunggulan dan kelemahan, maka daripada berusaha merancang fasilitas sistem operasi dengan satu strategi penanggulangan deadlock maka lebih efisien menggunakan strategi-strategi berbeda untuk situasi-situsai berbeda. Silberschatz [SIL-94] menyarankan satu pendekatan terpadu, yaitu:

  • Kelompokkan sumber daya-sumber daya menjadi sejumlah kelas sumber daya.
  • Gunakan strategi pengurutan linier seperti yang didefinisikan pada pencegahan menunggu sirkular. Strategi ini digunakan untuk mencegah deadlock di antara kelas-kelas sumber daya berbeda.
  • Dalam satu kelas sumber daya, gunakan algoritma yang paling cocok untuk kelas-kelas sumber daya itu.

Prinsip

Kebijaksanaan alokasi sumber daya

Skema-skema

Keunggulan utama

Kelemahan utama

Pencegahan Konservatif,menurukan efisiensi sumber daya Meminta semua sumber daya sekaligus
  • Bekerja bagus untuk proses-prose yang melakukan sat barisan aktifitas tunggal.
  • Tidak diperlukan preemption
  • Tidak efisien
  • Memerlukan waktu tunda inisiasi proses
preemption
  • Cocok ketika diterapkan di sumberdaya yang state nya dapat disimpan dan dikembalikan dengan mudah
  • Preempt akan terjadi lebih sering daripada yang diperlukan
  • Dapat terjadi restart yang siklus
Pengurutan sumber daya
  • Layak dipaksakan lewat pemeriksaan saat kompilasi
  • Tidak perlu kompulasi saat berjalan karena  masalah diselesaikan sewaktu perancangan sistem
  • Preempt tanpa banyak penggunaan
  • Tak mengijinkan permintraan sumber daya yang meningkat
Deteksi Lebih bebas,sumber daya yang diminta diberikan bila mungkin Dijalankan secara periodik
  • Tak pernah waktu tunda inisiasi proses
  • Memberi  fasilitas penanganan on-line
  • Kehilangan preempt yang inheren
Penghindaran Memilih jalan tengah antara deteksi dan pencegahan Memanipulasi untuk menemukan pada setidaknya satu jalur selamat
  • Tidak diperlukan preemption
  • Kebutuhan-kebutuhan sumber daya masa datang harus diketahui
  • Proses-proses dapat diblock untuk periode yang lama

Tabel 7-1 Metode-metode penanggulangan deadlocK

Sumber : 1. Sistem Operasi Revisi kelima , Bambang Hariyanto.

                   2. http://bayuzu.blogspot.com/

Posted on 25 April 2013, in Sistem Operasi II and tagged , , , , , , . Bookmark the permalink. 2 Komentar.

  1. Tx gan infonya , berguna sekali buat saya🙂

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: