Day 3

Deadlock 

      Adalah kejadian atau peristiwa dimana lebih dari satu proses memperebutkan resources yang sama, contoh resources : Harddisk, Printer, dll. Pengertian deadlock menurut buku adalah
"Bloking secara permanent dari kumpulan proses yang mana memperebutkan system resources atau komunikasi antar proses" (terjemahan sendiri , No Google Translate).

 

Contoh Deadlock 

Kondisi untuk kejadian Deadlock Resources

• Mutual Exclusion : hanya satu proses yang boleh mengakses resources, sehingga proses
                           menunggu dengan lama dan sabar.
• Hold And Wait : sebuah kejadian dimana sebuah proses yang memegang resources
                       menunggu hasil inputan dari proses lain untuk run. contoh:
                       saat pembagian makanan di acara, yang duduk paling ujung langsung ambil
                       untuk dirinya sendiri, oleh karena itu jika makanan yang dibagi ternyata
                       tidak mencukupi, proses yang harusnya makan , malah tidak kedapatan, dan
                       proses yang tadi tidak akan makan sampai proses sebelumnya mendapat
                       makanan oleh karena itu terjadi deadlock (semuanya kelaparan wkwkwkwk).
• No-preemption : Sebuah proses yang sedang berjalan, tidak dapat diganggu gugat sampai
                         proses tersebut selesai menggunakan resources dan melepasnya untuk
                         digunakan proses lain.
• Circular wait :

Deadlock pun ada pemodelannya agar lebih mudah dalam menjelaskan situasi deadlock. Pemodelan menggunakan RAG (Resources Allocation Graph)
contoh :

 contoh kasusnya :


Jika kasus tersebut digambarkan kedalam RAG maka hasilnya seperti ini :


 dan penyelesaian dari deadlock tersebut bisa dengan cari ini :


Ada macam - macam cara untuk menghidari atau menghadapi deadlock seperti :

• Ostrich Algorithm (Just ignore the problem)
• Detection and Recovery : Membiarkan masalah terjadi, lalu masalahnya di analisa dan
                                     lakukan action yang sesuai untuk menghadapai masalah tersebut.
• Dynamic avoidance : Menghindari masalah di awal dengan alokasi resources yang cermat.
• Preventing : Mencegah deadlock dengan menghilangkan salah satu kondisi deadlock.

Deadlock avoidance juga mengandung algoritma yang akan membuat alokasi yang diberi adalah safe state sehingga menjamin bahwa tidak akan terjadi kondisi circular wait. Algoritma ini disebut juga sebagai Banker's Algorithm.

Berikut simulasinya :




Kondisi pencegahan dalam kondisi penyebab deadlock :

• Mutual Exclusion
       sebaiknya jangan digunakan untuk yang shareable resources.
   
• Hold and Wait
       harus dapat menjamin bahwa kapanpun sebuah proses ingin mengakses resources, proses tersebut tidak boleh memegang resources lain.

• Circular wait
       ada proses yang harus nunggu atau jalan duluan sehingga tidak terjadi saling nunggu.

• No-preemption
       bukan merupakan pilihan yang tepat untuk mencegah deadlock.

Oleh karena itu untuk deadlock prevention :

• Mutual exclusion
       dalam menggunakan metode ini, harus membuat antrian proses yang akan mengakses resources.

• Hold and Wait
       dalam menggunakan metode ini, semua proses harus menginisialisasi resources yang akan dipakai sejak awal

• No preemption
       mengambil semua resource.
   
• Circular wait
       buat antrian secara numerically.

untuk kasus starvation , solusinya dapat menggunakan kebijakan First-Come First-Serve  (antrian)

Memory Management

      Adalah cara - cara untuk memanage memory, agar memory yang dipakai se-efisien mungkin
Requirement untuk memory management :

• Relokasi
       saat program sedang berjalan , program tersebut dapat saja di swap ke main memory di lokasi yang berbeda 

• Proteksi
       sebuah proses yang aktif, tidak boleh mereference alamat memory di dalam proses lain tanpa ada permission

• Sharing
        memperbolehkan beberapa proses untuk mengakses  porsi yang sama dari memory

• Logical Organization
        program ditulis dalam bentuk modul - modul dan dicompile secara terpisah (share module)

• Physical Organization
        memanage secara physical.

Addressing ada yang untuk logical , relative,  dan physical

Logical addressing : referensi alamat memory independent terhadap tugas data sekarang di memory

Relative addressing : alamat diekspresikan sebagai lokasi yang relatif terhadap titik/point yang dikenal

Physical addressing : lokasi absolut atau lokasi sebenarnya dalam memory.

Cara - cara memory management :

• Partition
       membagi - bagi (partisi) memory yang digunakan sehingga mampu untuk memproses banyak job secara bersamaan.
   
• Swapping
        perpindahan (swap) alamat memory saat sebuah proses sedang berjalan.

•  Bit map
  

•  Linked list
  

Algoritma dalam memory allocation :

• First fit -> fastest (karena langsung menemukan)
• Next fit
• Best fit -> memilih blok memory yang terdekat dengan size yang diminta
• Worst fit
• Quick fit
• Buddy system -> menggunakan perhitungan , dan semua space dianggap single block 2^U
                          dengan rumus 2U-1 < s <= 2U

memory allocation dengan buddy system

Binus & Sky Connectiva