Deadlock dan Starvation

Prinsip-Prinsip Deadlock

1. Definisi Deadlock

    Pemblokiran permanen sejumlah proses yang berkompetesi dalam mendapatkan sumber daya sistem                  atau yang berkomunikasi satu dengan lainnya.
    Semua Deadlock mencakup konflik kebutuhan akan sumber daya oleh dua proses atau lebih. Contoh yang umumnya adalah Deadlock lalu lintas . Gambar 1.1 menunjukan situasi empat mobil tiba dipersimpangan empat arah dalam waktu yang hampir bersamaan. keempat kuadran persimpangan itu merupakan sumber daya yang memerlukan kontrol, pada suatu saat, apabila keempat mobil itu ingin melintasi persimpangan, persyaratan sumber dayanya adalah sebagai berikut:

• Mobil yang bergerak ke utara membutuhkan kuadran 1 dan kuadran 2.
• Mobil yang bergerak ke barat membutuhkan kuadran 2 dan kuadran 3.
• Mobil yang bergerak ke selatan membutuhkan kuadran 3 dan kuadran 4.
• Mobil yang bergerak ke timur membutuhkan kuadran 4 dan kuadran 1.

Aturan jalan raya yang normal adalah bahwa mobil yang berada dipersimpangan empat arah harus memberikan jalan kepada mobil yang berada disebelah kanannya. Aturan ini akan berfungsi apabila terdapat hanya dua atau tiga mobil di persimpangan itu, Misalnya, apabila hanya mobil yang menuju utara dan yang menuju barat tiba dipersimpangan, mobil yang menuju utara akan menunggu, sedangkan mobil yang menuju barat melanjutkan perjalanannya. Namun apabila empat buah mobil tiba dipersimpangan pada saat yang hampir bersamaan, keempat mobil itu akan terjadi Deadlock.

• Penjelasan Deadlock (Gambar 1.1)

•  Contoh Deadlock (Gambar 1.2)

Apabila keempat mobil itu mengabaikan aturan  dan melanjutkan perjalanan dengan melintasi persimpangannya, keempat mobil itu akan mengambil satu sumber daya (satu kuadran) namun tidak dapat melanjutkan perjalannya karena sumber daya yang keduanya diperlukan telah diambil oleh mobil lainnya.   


       
2. Penyebab Deadlock  / Syarat Terjadi Deadlock

•     Mutual Exclusion : Suatu kondisi dimana setiap sumber daya diberikan tepat pada satu proses pada    suatu waktu.

•     Hold and Wait : Kondisi yang menyatakan proses-proses yang sedang memakai suatu sumber daya dapat meminta    sumber daya yang lain.

•     Non-pre-emptive : Kondisi dimana suatu sumber daya yang sedang berada pada suatu proses tidak dapat diambil secara paksa dari proses tersebut,sampai proses itu melepaskannya.

•     Circular Wait : Kondisi yang menyatakan bahwa adanya rantai saling meminta sumber daya yang dimiliki oleh suatu proses oleh proses lainnya.

3. Menghindari Deadlock
    Sistem perlu memiliki informasi awal mengenai kebutuhan sumber daya

•  Tiap proses menyatakan kebutuhan maksimum tiap jenis sumber yg dibutuhkan
•  Algoritma deadlock-avoidance secara dinamis memeriksa state alokasi sumber daya untuk   menjamin tdk terjadinya kondisi circular-wait
• State alokasi sumber daya didefinisikan oleh banyaknya sumber daya yg tersedia dan yg dialokasikan, dan permintaan sumber daya maksimum oleh proses

Jika proses meminta sumber daya yg tersedia, sistem harus memutuskan apakah alokasi sumber daya ini   akan menghasilkan safe state
Sistem berada pada safe state jika terdapat urutan event yg tidak menyebabkan deadlock jika semua proses meminta sumber daya maksimum sekaligus

•   Logikanya:
     – Jika sistem berada pd safe state 􀃆 no deadlock
     – Jika sistem berada pd unsafe state 􀃆 kemungkinan deadlock
     – Pencegahan: sistem tidak masuk ke unsafe state

4. Mengatasi Deadlock
   Prevention : memastikan paling sedikit satu penyebab Deadlock tidak berlaku

• Mutual Exclusion : membuat file spool untuk resource yang digunakan bersama-sama
• Hold and Wait : memaksa sebuah proses untuk melepaskan resource yang dimilikinya ketika meminta resource baru
• Circular Waiting : memberikan penamaan resource berdasarkan urutan atau level
• No Preemption : membolehkan adanya preemption
• Avoidance : sistem menolak request terhadap resource yang berpotensi deadlock, Algoritma Banker
• Resource manager menolak proses yang meminta resource yang berpotensi deadlock
• Jika ada permintaan resource yang maksimum digunakan, maka proses tersebut akan dipaksa untuk melepaskan resource yang sudah dimiliknya
• Perlu adanya informasi tambahan
• Detection and Recovery : membiarkan Deadlock terjadi, lalu mendeteksinya, kemudian melakukan recovery, Algoritma Ostrich
• Tindakan recovery yang dilakukan adalah : melakukan preemption, membuat checkpoint untuk rollback lalu membunuh proses yang prioritasnya kecil

5. Mencegah Deadlock
    Tiap proses harus meminta semua sumber daya yang diperlukan sekaligus dan tidak berlanjut sampai semuanya diberikan
    Jika proses telah sedang memegang resource tertentu, untuk permintaan berikutnya proses harus melepas dulu resource yg dipegangnya.
    Beri pengurutan linear terhadap resource pada semua proses

Pengertian Sistem Operasi

Nama Kelompok: 

1. Adi Setyawan            (210511058)
2. Andi Meri Tridinata    (210511076)
3. Agung Solehan           (210511049)
4. Galih Satria Wibisono (210511074)
5. Riyan Hardin Syam     (210511075)
6. Guno Triyanto             (210511046)

Pengertian Sistem operasi Komputer adalah suatu program yang mengontrol eksekusi program aplikasi berfungsi sebagai interface antara pengguna komputer dengan hardware komputer.

Gambaran umum sistem operasi:

A. Tujuan dan fungsi Sistem Operasi.

Kemudahan: Sistem operasi membuat komputer menjadi lebih mudah dipakai.

Efisien: Sistem operasi memungkinkan sumber daya sistem komputer untuk digunakan dengan cara yang efisien

Kemampuan berkembang: Sistem Operasi harus disusun sedemikian rupa sehingga memungkinkan pengembangan yang efektif, pengujian, dan penerapan fungsi-fungsi sistem yangbaru tanpa menggagu layanannya yang telah ada.

B. Evolusi Sistem Operasi

1.     Pengolahan Serial

Scheculing (penjadwalan): Umumnya istalasi menggunakan formulir pemesanan waktu mesin.

Set up time (waktu set up): Sebuah program tunggal, yang disebut job, dapat mencakup pemuatan kompiler serta proggram bahasa tingkat tinggi(program sumber) kedalam memori, pemyimpanan program yang telah di compile(program objek), dan kemudian pemuatan dan penggabugan program objek dengan fungsi yang umum.

     2. Sistem Batch Sederhana

     3. Sistem Batch Multiprogrammed

     4. Sistem Time-Sharing  

    

C. Karateristik Sistem Operasi Modern

          Sistem Operasi yang merupakan jawaban bagi perkembangan baru didalam hardware      dan aplikasi baru. Salah satu diantara driver hardware yang penting adalah mesin multiprosesor yang kecepatannya sangat meningkat, penyambungan jaringan kerja yang berkecepatan tinggi, dan peningkatan ukuran bermacam-macam perangkat penyimpanan memori.

     Pendekatan dan elemen rancangan dapat digolongkan menjadi: 

• Arsitektur microkernel
• Multithreading
• Multiprocessing simetris
• Sistem operasi terdistribusi
• Rancangan berorientasi objek

     Multitreading adalah teknik dimana suatu proses, yang mengeksekusi aplikasi, dibagi menjadi treath-treath yang dapat berjalan secara bersamaan.

Perbedaaan antara proses dengan treath: 

Treath: Satuan kerja yang dapat dikirimkan. Treath melakukan eksekusi secara sekuential dan dapat diinterupsi sehingga prosessor dapat beralih ketreath lainnya.

Proses: Kumpulan sebuah treath atau lebih dari sumber daya yang terkait (seperti memori, file terbuka, dan perangkat).