Concurrency & Deadlock

Concurrency

Concurrency merupakan komunikasi antara proses , sharing resources, sinkronisasi banyak proses, pengalokasian waktu processor.
Contoh penerapan concurrency ini dapat ditemukan dalam multiprogramming (penggunaan beberapa aplikasi pada saat yang sama), di dalam aplikasi terstruktur (structured application, aplikasi ini juga disusun dari berbagai perintah yang concurrent), dan di dalam struktur sistem operasi (karena OS itu adalah sekumpulan proses atau thread).
Masalah dalam Concurrency :
- Sharing Global Resources
- Pengelolaan alokasi resources
- Kesalahan-kesalahan dimana terjadi ketika programming susah ditemukan (di-debug) ketika setelah dieksekusi.
  - Contoh : printer, jadi jika satu printer dalam 3 divisi dalam suatu perusahaan , lalu sama sama digunakan .
Operating System Concern :
- Melacak proses yang aktif
- Mengalokasikan dan DEALLOCATE sumber :
  - waktu prosesor
  - ingatan
  - File
  - I / O
- Melindungi data dan sumber
  - mengamankan data dan resourses
- Hasil proses harus independen dari kecepatan eksekusi proses konkurenlainnya
Competition among Processes for Resources :
- Mutual Exclusion = terdapat hak khususnya
  - Critical sections
    - Hanya satu program pada suatu waktu yang diijinkan dalam section critical
  - Deadlock
  - Starvation
    - saling menunggu dan pada akhirnya tidak terpakai
Cooperation among process
- By sharing
  - Penulisan harus eksklusif
  - Bagian penting yang digunakan untuk menyediakan integritas data
- By communication
  - Pesan dilewati
    - Mutual exclusion bukan persyaratan kontrol
  - Memungkinkan terjadi deadlock
    - Setiap proses menunggu pesan dari proses lainnya
  - Memungkinkan terjadi starvation
    - Dua proses mengirim pesan satu sama lain sementara proses lainmenunggu pesan
Mutual exclusion merupakan suatu metode yang memungkinkan supaya hanya ada 1 proses dalam 1 waktu yang berhak berada dalam critical section dari suatu resource. Sebuah proses yang berhenti di non-critical section dari suatu proses harus melakukannya tanpa mengganggu proses-proses yang lain. Oleh sebab itu, dalam mutual exclusion tidak ada yang namanya deadlock ataupun starvation. Dengan metode ini, suatu proses tidak boleh terhambat dalam memasuki critical section dari suatu resource jika critical section itu lagi kosong, tapi setelah berada di dalamnya, proses itu terbatas berada disana dalam satu waktu tertentu.
Agar mencapai mutual exclusion ini, ada beberapa cara yang dapat dilakukan :
- Disabling interupts
  - contoh : non-preemptive, tidak dapat di interupts
- Lock variables
  - biasanya terjadi di dalam jabascript
- Strict alternation
- Peterson’s solution
- The TSL instruction
Cara penyelesaian Dining Philosopher’s Problem :
- Semaphore
- Monitor
  - mencatat setiap fork yang tersedia
Semaphores = mengatur jalannya proses, tidak boleh negative harus bilangan positive untuk penandanya.
- Variabel khusus yang disebut semaphore digunakan untuk sinyal
- Jika suatu proses menunggu sinyal, itu ditangguhkan sampai sinyal yang dikirimkan
- Tunggu dan operasi sinyal tidak dapat terganggu
- Antrian digunakan untuk menyimpan proses menunggu di semaphore
Monitor
- Pemrograman konstruksi bahasa yang mendukung akses dikendalikan ke data bersama
  - Compiler Menambahkan sinkronisasi otomatis
  - Enforced Saat runtime
Message Passing
- Mengkomunikasikan informasi dari satu proses lain melalui (komunikasi informasi dari 1 proses ke lainnya ) :
  - send (dest, & message)
    - Synchronous
      - Mengembalikan setelah data dikirim
      - Mengeblock jika buffer penuh
    - Asynchronous
      - Returns as soon as I/O started
      - Done ?
        
        Explicit check
        
        Signal atau acknowledgement
      - Block jika buffer penuh (memungkinkan)
  - receive (source, & message)
    - Synchronous
      - Mengembalikan jika ada pesan
      - Block jika tidak ada pesan
    - Asynchronous
      - Mengembalikan pesan pertama jika ada satu
Mengembalikan indikasi jika tidak ada pesan
Penerima dapat menentukan ANY
Receiver dapat memilih untuk memblokir atau tidak
Berlaku untuk single dan multi–processor dan sistem terdistribusi
Pre–tanggal Semaphore
Tidak memerlukan ruang alamat bersama!

Deadlock

Deadlock adalah suatu kejadian ketika ada proses yg :

saling memperebutkan
saling menunggu
saling menghalangi

Permanent blocking adalah sekumpulan proses yg saling berkompetisi untuk mendapatkan sumber informasi bagi sistem dan juga untuk berkomunikasi dengan proses yg lain. Karena permanent blocking tersebutlah muncul adanya deadlock.

Pada gambar (a) diatas merupakan gambar kemungkinan terjadinya suatu deadlock, sedangkan gambar (b) merupakan kejadian disaat deadlock sudah terjadi.

CONDITION FOR RESOURCE DEADLOCK

Kondisi-kondisi yg mungkin terjadi saat deadlock :

Mutual exclusion
hanya ada 1 proses yg dapat mengakses sumber informasi
Hold and wait
proses yg sedang memegang 1 sumber informasi juga sedang menunggu untuk mengakses sumber informasi lain yg sedang dipegang oleh proses yg lain
No preemption
suatu sumber informasi akan secara sukarela dilepaskan oleh proses yg sedang mengaksesnya, setelah proses tersebut selesai melakukan tugasnya
Circular wait
suatu keadaan dimana semua proses saling ingin mengakses sumber informasi yg sama, namun mereka saling menunggu karena masih ada 1 proses yg sedang mengaksesnya

Pada gambar (a) merupakan gambar resource R sedang diakses oleh proses A. Sedangkan gambar (b) adalah proses B yg merequest resource R. Pada gambar (c) merupakan gamabr circular wait.

Gambar deadlock yg terjadi :

Berikut ini adalah gambar untuk solusi masalah deadlock :

Cara-cara untuk mencegah deadlock ada 4 :

biarkan saja masalahnya (menurut algoritma Ostrich)
deteksi dan pemulihan kembali, biarkan deadlock terjadi, deteksi deadlocknya dimana lalu ambil tindakan
pencegahan secara dinamik
pencegahan

Ada beberapa cara untuk menunjukkan deteksi terjadinya deadlock :

dengan menggunakan resource graph
dengan menggunakan cycle yg telah diekstrak dari resource graph

Deadlock avoidance, membutuhkan sistem yg mempunyai informasi yg penting :

setiap proses mendefinisikan sumber maksimum yg dibutuhkan
memastikan bahwa tidak akan pernah terjadi kondisi circular wait
Resource algorithm didefinisikan oleh jumlah sumber informasi yg dialokasi dan jumlah maksimum dari proses tersebut

Deadlock detection, memastikan permintaan sumber informasi dapat terjadi. Ada 4 cara :

mutual exclusion
hold and wait
circular wait
no preemption

Kondisi dalam deadlock detection serta cara pendekatannya

STARVATION

Starvation adalah sebuah algoritma untuk mengalokasikan sejumlah sumber informasi, dan mungkin memberikan shortest job first, tapi memungkinkan juga untuk terjadi penundaan waktu yg sangat panjang, meskipun tidak diblock. Maka solusi untuk mengatasi starvation adalah first-come first-serve algorithm.

Deadlock recovery, digunakan untuk membatalkan semua proses yg sudah deadlock (untuk proses terminasi). Untuk mencegah terjadinya interupsi sumber informasi adalah dengan :