concurency, deadlock, starvation

Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Concurency, Deadlock, Starvation

3/27/2016 2Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Concurency

• Proses-proses disebut concurrency jika proses-proses (lebih dari satu proses) berada pada saat yang sama.

• Proses-proses yang mengalami kongkuren dapat berdiri sendiri (independen) atau dapat saling berinteraksi, sehingga membutuhkan sinkronisasi atau koordinasi proses yang baik. 

3/27/2016 3Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Deadlock

• Suatu Blocking Permanen dari sekumpulan proses• Sekumpulan proses mengalami deadlock ketika masing-masing

process di block karena menunggu suatu even yang hanya dapat ditrigger oleh proses yang terblock lainnya dalam kumpulan proses tersebut

• Permanen• Tidak ada solusi yang efektif

3/27/2016 4Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Potensi terjadi Deadlock

Lurus melewati b dan c

Belok kiri melewati a dan

d

Belok kanan melewati c dan

b

Belok Kanan melewati d dan

a

3/27/2016 5Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Actual Deadlock

Halt until 3 is free

Halt until 2 is free

Halt until 4 is free

Halt until 1 is free

3/27/2016 6Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Deadlock Example

3/27/2016 7Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Starvation

• Starvation adalah kondisi yang biasanya terjadi setelah deadlock. Proses yang kekurangan resource (karena terjadi deadlock) tidak akan pernah mendapat resource yang dibutuhkan sehingga mengalami starvation (kelaparan)

3/27/2016 8Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

2 proses P dan Q

• Masing-masing proses membutuhkan akses ke sumber daya A dan B dalam waktu tertentu

3/27/2016 9Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

DiagramDeadlock

3/27/2016 10Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

DiagramNo Deadlock

3/27/2016 11Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Klasifikasi Sumber DayaReusable• Dapat digunakan oleh hanya 1 proses pada satu waktu.• Deadlock terjadi jika masing-masing proses memegang 1 sumber daya dan meminta sumber daya lainnya.• Misal: Prosesor, memori, kanal i/o, struktur data seperti file, basis data dan semaphore.

Consumable• Sesuatu yang dapat diciptakan (produced) dan dihilangkan

(consumed)• Misal : Interupsi, sinyal, messages, information I/O buffers• Deadlock dapat terjadi jika pesan/message di blocking

3/27/2016 12Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Reusable Resource

3/27/2016 13Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Contoh : Memory Request

•Terdapat ruang kosong sebesar 200KB dan terjadi urutan kejadian sebagai berikut :

•Deadlock terjadi jika kedua proses maju ke permintaan kedua

P1……

Request 80 KB;……

Request 60 KB;

P2……

Request 70 KB;……

Request 80 KB;

3/27/2016 14Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Consumable Resource Deadlock• Seandainya ada sepasang proses, masing-masing proses menunggu

untuk menerima message dari proses lainnya dan kemudian mengirimkan message ke proses lainnya :

• Deadlock terjadi jika penerimaan message terblocking

3/27/2016 15Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Deadlock

• Detection• Prevention• Avoidance

3/27/2016 16Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Resource Allocation Graph

Pemodelan menggunakan graph berarah untuk menggambarkn state dari istem proses dan sumber daya

3/27/2016 17Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Kondisi Kemungkinan Terjadinya Deadlock

Mutual Exclusion• Hanya ada 1 proses yang

dapat menggunakan resource dalam 1 waktu

Hold and wait• Suatu proses

menahan pengalokasian resource ketika menunggu assignment dari yang lainnya

No Preemption• Tidak ada sumber

daya yang dapat dipaksa untuk dilepaskan dari sebuah proses yang memegangnya

Circular Wait• Rantai tertutup dari

sebuah proses seperti jika ada masing-masing proses yang memegang sedikitnya 1 resource yang dibutuhkan oleh proses selanjutnya dalam rantai

3/27/2016 18Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Resource Allocation Graph (1)

3/27/2016 19Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Resource Allocation Graph (2)

3/27/2016 20Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Penanganan Deadlock

• Mengadopsi suatu aturan/merancang sistem yang mengeliminasi kemungknan terjadinya deadlock

Prevent Deadlock

• Membuat pilihan dinamis yang sesuai berdasarkan keadaan yang terjadi terhadap alokasi resource

Avoid Deadlock

• Mencoba untuk mendeteksi keberadaan deadlock dan melakukan aksi untuk mengatasinya

Detect Deadlock

3/27/2016 21Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Deadlock Prevention Strategi

• Ada 2 metode yaitu • Direct

• Mencegah salah satu dr 3 kondisi terjadi• Indirect

• Mencegah terjadinya circular wait

3/27/2016 22Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Deadlock condition Prevention

Mutual Exclusion

• Jika akses ke sumber daya membutuhkan mutual exclusion maka OS harus menyediakannya

Hold And Wait

• Membutuhkan permintaan proses terhadap semua resource yang dibutuhkan dalam satu waktu dan memblok proses sampai semua permintaan dapat dipenuhi secara simultan

3/27/2016 23Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Deadlock condition Prevention

No Preemption

• jika proses memegang sumber daya tertentu ditolak permintaan selanjutnya , proses harus melepaskan sumber aslinya dan meminta mereka lagi

• OS dapat mendahulukan proses kedua dan melepaskan sumber dayanya

Circulat Wait

• menentukan urutan linier dari jenis sumber daya

3/27/2016 24Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Deadlock Avoidance

• Sebuah keputusan dibuat secara dinamis apakah saat ini permintaan alokasi sumber daya akan berpotensi menyebabkan untuk kebuntuan , jika diberikan

• Membutuhkan pengetahuan tentang permintaan proses masa depan

3/27/2016 25Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

2 Pendekatan Deadlock Avoidance

• Process Initiation Denial• Tidak memulai suatu proses jika berpotensi deadlock• Sebuah proses hanya dimulai jika klaim maksimum dari semua proses saat ini ditambah proses

baru dapat dipenuhi• Tidak maksimal,

Mengasumsikan yang terburuk: bahwa semua proses akan membuat klaim maksimum mereka bersama-sama.

• Resource Allocation Denial• Jangan memberikan permintaan sumber daya tambahan untuk proses jika alokasi ini mungkin

menyebabkan deadlock• Pertimbangkan sistem dengan sejumlah sumber daya tetap

State dari sistem adalah alokasi saat ini sumber daya untuk memprosesSafe State adalah di mana ada setidaknya satu urutan yang tidak mengakibatkan unsafe state adalah keadaan yang tidak aman

3/27/2016 26Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Banker’s Algorithm

• Ketika proses membuat permintaan untuk sekumpulan sumber daya,

• asumsikan bahwa permintaan itu dikabulkan,• Update status sistemterus menerus,• Kemudian, tentukan apakah hasilnya aman (safe state).

• Jika demikian, kabulkan permintaan tersebut• jika tidak, hambat proses tersebut sampai aman untuk

mengabulkan permintaan tersebut.

3/27/2016 27Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Deadlock Detection

• strategi pencegahan deadlock ;• membatasi akses ke sumber daya dan memberlakukan pembatasan proses.

• strategi deteksi deadlock melakukan yang sebaliknya• permintaan sumber daya diberikan bila memungkinkan.• Secara teratur memeriksa deadlock

3/27/2016 28Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Strategi Recovery Jika Terdeteksi Deadlock

• Hentikan semua proses deadlock • Back up setiap proses deadlock dan restart semua proses

Risiko atau kebuntuan berulang• Berturut-turut membatalkan proses deadlock sampai deadlock tidak

ada lagi• Berturut-turut preemp sumber sampai deadlock tidak ada lagi

3/27/2016 29Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

3/27/2016 30Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Tugas

• Perbandingan Linux dan Window dalam hal penanganan deadlock

3/27/2016 31Kajian 1 : Teori Dasar Sistem OperasiTK1033-SISTEM OPERASITH AKADEMIK 2015-2016

Referensi

• William Stallings. Hak Cipta © 2001. Operating Systems. Prentice Hall.

• Andrew S. Tanenbaum. Hak Cipta © 1992. Modern Operating Systems. Prentice-Hall Inc.

• Avi Silberschatz, Peter Galvin, dan Grag Gagne. Hak Cipta © 2000. Operating Systems CONCEPTS

• William Stallings. The Linux Operating System• Frank G Fiamingo. Introduction to Unix