Operasi dan Hukum Himpunan Singkat

Operasi terhadap himpunan
1. Irisan

2. Gabungan

3. Komplemen

4. Selisih

5. Beda Setangkup

Hukum terhadap himpunan

Metoda Mengatasi Deadlock

Cara mengatasi deadlock :
A. Pencegahan deadlock (deadlock prevention)
1. Meniadakan mutual exclusion
Deadlock disebabkan terdapatnya  pengaksesan eksklusif sumber daya. Jika tidak ada sumber daya ekslusif ke satu proses tunggal, maka tidak pernah dijumpai deadlock. Cara yang ditempuh untuk mengganti pengaksesan eksklusif adalah dengan spooling sumber daya yaitu proses pengakesan sumber daya diantrikan di disk.

2. Mencegah hold and wait
Proses me-request seluruh sumber daya pada sekaligus dan proses terblock samapai seluruh permintaan terpenuhi. Proses ini tidak efisien karena :

• Proses menjadi lama karena menunggu semua  sumber daya yang diminta terpenuhi yang sebenarnya dapat dikerjakan hanya dengan beberapa sumber daya.
• Sumber daya yang sudah dialokasikan pada proses ini mungkin saja tidak langsung digunakan tetapi karena sudah dialokasikan tidak dapat dipakai oleh proses lain.

3. Mencegah no-preemption, dilakukan dengan alternatif:
Jika sebuah proses yang telah menggenggam (hold) sumber daya tidak diperbolehkan meminta (request) lagi sumber daya, proses harus melepaskan (release) sumber daya tersebut dulu jika diperlukan dapat juga meminta kembali sumber daya yang dilepaskan bersamaan dengan sumber daya tambahannya.
Jika proses meminta sumber daya yang sedang digenggam oleh proses lain, sistem operasi dapat menyela (preempt) proses yang menggenggam dengan meminta melepaskan sumber daya tersebut. Alternatif ini dapat dilakukan jika tidak ada dua proses yang memiliki prioritas yang sama. Contoh kasus ini adalah prosesor.

4. Mencegah Circular wait
Dapat dilakukan dengan mendefinisikan urutan linier dari jenis sumber daya. Jika proses telah dialokasikan pada sumber daya berjenis R maka urutan permintaan berikutnya dari proses tersebut adalah hanya yang berjenis R. Misal sumber daya Ri mendahului Rj dengan urutan i < j. Jika terdapat dua proses A dan B deadlock karena A telah memperoleh Ri dan meminta Rj dan B telah memperoleh Rj dan  meminta Ri. Kondisi ini tidak akan terjadi karena pada kasus ini  i < j dan juga j < I.

B. Pendeteksian dan pemulihan deadlock (deadlock detection and recovery)
Berbeda dengan Deadlock prevention, deadlock detection tidak membatasi akses sumber daya dan memberi larangan pada proses. Permintaan terhadap sumber daya akan diberikan jika memungkinkan

Pengecekan deadlock dilakukan setiap kali ada permintaan sumber daya. Pendeteksian deadlock ini menguntungkan karena algoritmanya mudah hanya  didasari perubahan state dan tidak mengkonsumsi waktu prosesor yang banyak.

Setelah dideteksi ada deadlock dilakukan beberapa strategi pemulihan berikut :

• Keluarkan seluruh proses yang mengalami deadlock.
• Salin setiap proses yang deadlock ke titik pengecekan yang telah didefinisikan sebelumnya dan mulai kembali dari awal seluruh proses. Resikonya deadlock bisa terjadi lagi tapi karena proses kongkurensi tidak menentu hal ini tidak terjadi.
• Sela (preempt) sumber daya sampai tidak ada deadlock.

C. Penghindaran deadlock (deadlock avoidance)
Pada metode ini keputusan dibuat dinamik untuk mengetahui apakah suatu permintaan sumber daya jika dipenuhi dapat menyebabkan deadlock atau tidak.
Dua pendekatan penghindaran deadlock:

• Jangan memulai proses jika proses tersebut akan menghasilkan deadlock
• Jangan penuhi permintaan penambahan sumber daya jika alokasi ini dapat menyebabkan proses jadi deadlock

Untuk mengetahui kondisi mendatang akan menyebabkan deadlock atau tidak digunakan langkah berikut
Process Initiation Denial
Misal terdapat n proses dan m jenis sumber daya. Didefinisikan dalam bentuk vektor dan matriks

Yang memiliki hubungan

• Sumber daya terdiri dari yang teralokasi dan yang available 
• Untuk semua k,Ck<= Resource Tidak ada proses yang meminta sumber daya melebihi jumlah yang ada 
• Untuk semua k,Ak<=Ck 

Jadi suatu proses akan dimulai hanya jika

Resource Allocation Denial

State : sumber daya yang sedang dialokasikan pada suatu proses

Safe state : state yang setidaknya memiliki satu urutan yang dapat menyebabkan seluruh proses selesai tanpa deadlock (Completion without deadlock)

Contoh safe state dengan total sumber daya R1 = 9, R2 = 3 dan R3 =6

Contoh unsafe state

Tidak ada sumber daya yang dapat dialokasikan agar proses selesai karena sumber daya yang available tidak mencukupi

Pengertian dan Kondisi Deadlock

Deadlock terjadi jika proses menunggu suatu kejadian tertentu yang tidak pernah terjadi. Sekumpulan proses berkondisi deadlock bila setiap proses yang ada di kumpulan menunggu suatu kejadian yang hanya dapat dilakukan proses lain yang juga berada di kumpulan itu.

Prinsip Deadlock:Deadlock dapat didefinisikan sebagai blocking permanen pada beberapa proses yang saling berkompetisi maupun berkomunikasi untuk memperoleh suatu sumber daya

Sumber daya dapat dikatagorikan secara umum menjadi:

1. Reusable resource

Didefinisikan sebagai :Sumber daya yang dapat digunakan dengan aman oleh satu proses pada suatu saat. Terdapat tiga kondisi perlakukan sumber daya oleh proses yaitu : request – hold – release.

Contoh reusable resource :

• Processor
• I/O channel
• Main memory dan secondary memory
• Device
• File
• Database
• Semaphore

Contoh deadlock yang melibatkan reusable resource

Misal terdapat dua proses yang berkompetisi untuk mengakses disk file (D) dan tape drive (T)

Deadlock terjadi jika masing-masing proses memegang (hold) sumber daya dan meminta (request) sumber daya yang lain yang dipegang oleh proses yang lain. Cara mengatasinya dengan memberi batasan pada disain sistem untuk perintah request (Constraint on design system).

2. Consumable resource

Merupakan sumber daya yang dapat dibuat atau dilenyapkan. Kondisi tidak terblock menghasilkan proses-proses yang siap melepaskan sumber daya saat suatu sumber daya diperlukan oleh sebuah proses sumber daya tersebut akan muncul.

Contoh consumable resource :

• interrupt
• sinyal
• message
• informasi dalam I/O buffer

Contoh Deadlock yang melibatkan consumable resource :

Deadlock terjadi jika pesan Recive terblock di salah satu proses.

Beberapa kondisi yang memungkinkan terjadinya deadlock:

• Mutual exclusion :hanya satu proses yang boleh menggunakan sebuah sumber daya pada suatu saat
• Hold and wait :suatu proses dapat mememegang (hold) sumber daya yang sebenarnya ditunggu-tunggu oleh proses lain
• No preemption :Tidak ada sumber daya yang dapat dipaksa lepas dari suatu proses yang memegangnya
• Circular wait :Rantai tertutup yang menyatakan suatu proses memegang sumber daya yang diperlukan oleh proses lain sehingga terjadi saling menunggu

Circular Wait