06.sinkronisasi dan deadlock
TRANSCRIPT
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 1/52
SINKRONISASI DANDEADLOCK
BAB 6
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 2/52
SINKRONISASI
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 3/52
LATAR BELAKANG
Akses-akses yang dilakukan secara bersama-sama ke data yang sama, dapat menyebabkandata menjadi tidak konsisten.
Untuk menjaga agar data tetap konsisten,dibutuhkan mekanisme-mekanisme untukmemastikan pemintaan ekseskusi dari prosesyang bekerja.
Race Condition: Situasi dimana beberapa prosesmengakses dan memanipulasi data secarabersamaan. Nilai terakhir dari data bergantung
dari proses mana yang selesai terakhir. Untuk menghindari Race Condition, proses-
proses secara bersamaan harusdisinkronisasikan.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 4/52
Kasus Produsen-Konsumer
Dua proses berbagi sebuah buffer dengan ukuran yangtetap. Salah satunya produser, meletakkan informasi kebuffer yang lainnya. Konsumen mengambil informasi daribuffer. Ini juga dapat digeneralisasi untuk masalah yangmemiliki m buah produsen dan n buah konsumen, tetapikita hanya akan memfokuskan kasus dengan satu produsen
dan satu konsumen karena diasumsikan dapatmenyederhanakan solusi.
Masalah akan timbul ketika produsen ingin menaruh barangyang baru tetapi buffer sudah penuh. Solusi untukprodusen adalah istirahat (sleep) dan akan dibangunkanketika konsumen telah mengambil satu atau lebih barang
dari buffer. Biasanya jika konsumen ingin mengambilbarang dari buffer dan melihat bahwa buffer sedangkosong, maka konsumen istirahat (sleep) sampai produsenmeletakkan barang pada buffer dan membangunkan (wakeup) consumer.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 5/52
Kasus Produsen-Konsumer
Untuk mengetahui jumlah barang di buffer, kitamembutuhkan sebuah variabel kita namakan count. Jika jumlah maksimum dairi barang yang dapat ditampungbuffer adalah N, kode produser pertama kali akan mencobauntuk mengetahui apakah nilai count sama dengan nilai N.Jika itu terjadi maka produsen akan istirahat (sleep), tetapi
jika nilai count tidak sama dengan N, produsen akan terusmenambahkan barang dan menaikkan nilai count. Sekarang mari kita kembali ke permasalahan race
condition. Ini dapat terjadi karena akses ke count tidakdipaksakan. Situasi seperti itu mungkin dapat terjadi.Buffer sedang kosong dan konsumen baru saja membacacount untuk melihat apakah count bernilai 0. Pada saat itu,penjadual memutuskan untuk mengentikan proseskonsumen sementara dan menjalakan produsen. Produsenmemasukkan barang ke buffer, menaikkan nilai count, danmemberitahukan bahwa count sekarang bernilai 1.Pemikiran bahwa count baru saja bernilai 0 sehinggakonsumen harus istirahat (sleep). Produsen memanggil
fungsi wake up untuk membangkitkan konsumen.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 6/52
Kasus Produsen-Konsumer
Sayangnya, konsumen secara logika belumistirahat. Jadi sinyal untuk membangkitkankonsumen, tidak dapat ditangkap olehkonsumen. Ketika konsumen bekerja berikutnya,konsumen akan memeriksa nilai count yang
dibaca sebelumnya, dan mendapatkan nilai 0,kemudian konsumen istirahat (sleep) lagi. Cepatatau lambat produsen akan mengisi buffer dan juga pergi istirahat (sleep). Keduanya akanistirahat selamanya.
Inti permasalahannya disini adalah pesan untukmembangkitkan sebuah proses tidaktersampaikan. Jika pesan/ sinyal ini tersampaikandengan baik, segalanya akan berjalan lancar.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 7/52
Race Condition
Race Condition adalah situasi di mana beberapa prosesmengakses dan memanipulasi data bersama pada saat besamaan.Nilai akhir dari data bersama tersebut tergantung pada prosesyang terakhir selesai. Unutk mencegah race condition, proses-proses yang berjalan besamaan haus di disinkronisasi.
Dalam beberapa sistem operasi, proses-proses yang berjalan
bersamaan mungkin untuk membagi beberapa penyimpananumum, masing-masing dapat melakukan proses baca (read ) danproses tulis (write). Penyimpanan bersama (shared storage)mungkin berada di memori utama atau berupa sebuah berkasbersama, lokasi dari memori bersama tidak merubah kealamiandari komunikasi atau masalah yang muncul. Untuk mengetahuibagaimana komunikasi antar proses bekerja, mari kita simaksebuah contoh sederhana, sebuah print spooler. Ketika sebuahproses ingin mencetak sebuah berkas, proses tersebutmemasukkan nama berkas ke dalam sebuah spooler direktoriyang khusus. Proses yang lain, printer daemon, secara periodikmemeriksa untuk mengetahui jika ada banyak berkas yang akandicetak, dan jika ada berkas yang sudah dicetak dihilangkan namaberkasnya dari direktori.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 8/52
Race Condition
Bayangkan bahwa spooler direktori memiliki slotdengan jumlah yang sangat besar, diberi nomor0, 1, 2, 3, 4,... masing-masing dapat memuatsebuah nama berkas. Juga bayangkan bahwa adadua variabel bersama, out, penunjuk berkas
berikutnya untuk dicetak, dan in, menunjuk slotkosong di direktori. Dua vaiabel tersebut dapatmenamgami sebuah two-word berkas untuksemua proses. Dengan segera, slot 0, 1, 2, 3kosong (berkas telah selesai dicetak), dan slot 4,
5, 6 sedang terisi (berisi nama dari berkas yangantre untuk dicetak). Lebih atau kurang secarabesamaan, proses A dan B, mereka memutuskanuntuk antre untuk sebuah berkas untuk dicetak.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 9/52
Race Condition
ILUSTRASI RACE CONDITION
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 10/52
Race Condition Dalam Murphy's Law kasus tesebut dapat terjadi. Proses A
membaca in dan menyimpan nilai "7" di sebuah variabel lokalyang disebut next_free_slot. Sebuah clock interrupt terjadi danCPU memutuskan bahwa proses A berjalan cukup lama,sehingga digantika oleh proses B. Proses B juga membaca in,dan juga mengambil nilai 7, sehingga menyimpan nama berkasdi slot nomor 7 dan memperbaharui nilai in menjadi 8. Maka
proses mati dan melakukan hal lain. Akhirnya proses A berjalan lagi, dimulai dari tempat di mana
proses tersebut mati. Hal ini terlihat dalam next_free_slot,ditemukan nilai 7 di sana, dan menulis nama berkas di slotnomor 7, menghapus nama berkas yang bau saja diletakkanoleh proses B. Kemudian proses A menghitung next_free_slot +1, yang nilainya 8 dan memperbaharui nilai in menjadi 8.Direktori spooler sekarang secara internal konsisten, sehinggaprinter daemon tidak akan memberitahukan apa pun yangterjadi, tetapi poses B tidak akan mengambil output apa pun.Situasi seperti ini, dimana dua atau lebih proses melakukanproses reading atau writing beberapa shared data dan hasilnyabergantung pada ketepatan berjalan disebut race condition.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 11/52
Critical Condition
Walau pun dapat mencegah race conditions, tapitidak cukup untuk melakukan kerjasama antarproses secara pararel dengan baik dan efisiendalam menggunakan shared data.
Kita butuh 4 kondisi agar menghasilkan solusiyang baik:1. Tidak ada dua proses secara bersamaan masuk ke
dalam citical section.2. Tidak ada asumsi mengenai kecepatan atau jumlah
cpu.
3. Tidak ada proses yang berjalan di luar critical secionyang dapat mengeblok proses lain.4. Tidak ada proses yang menunggu selamamya untuk
masuk critical section.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 12/52
Critical Condition
Critical Section adalah sebuah segmen kode dimana sebuah proses yang mana sumber dayabersama diakses. Terdiri dari:
Entry Section: kode yang digunakan untuk
masuk ke dalam critical section Critical Section: Kode di mana hanya ada satu
proses yang dapat dieksekusi pada satu waktu
Exit Section: akhir dari critical section,mengizinkan proses lain
Remainder Section: kode istirahat setelah masukke critical section
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 13/52
Critical Condition
Solusi yang diberikan harus memuaskanpermintaaan berikut:1. Mutual exclution 2. Deadlock free 3. Starvation free
Pendekatan yang mungkin untuk solusi prosessinkronisasi
1. Solusi Piranti lunak (Software solution)•
Tanpa Sinkronisasi.• Dengan Sinkronisasi.
Low-level primitives: semaphore High-level primitives: monitors
2. Solusi Piranti Keras (Hardware solution)
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 14/52
Critical Condition
Mutual Exclusion
Mutual Exclusion: Kondisi-kondisi untuksolusi
Tiga kondisi untuk menentukan mutual Exclusion 1. Tidak ada dua proses yang pada saat
bersamaan berada di critical region.
2. Tidak ada proses yang berjalan diluar critical region yang bisa menghambat proses lain
3. Tidak ada proses yang tidak bisa masuk kecritical region
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 15/52
Critical Condition
Mutual Exclusion (lanjutan)
Solusi1. Cara-cara memecahkan masalah
2. Hanya dua proses, Po dan P13. Struktur umum dari proses adalah Pi (proses lain
Pj)
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 16/52
Critical Condition
Mutual Exclusion (Lanjutan)
Algoritma 1 : Disini kita akan mencoba membuat sebuah rangkaian solusi-
solusi dari permasalahan yang makin meningkat kerumitannya. Pada semua contoh, i adalah proses yang sedang berjalan, j
adalah proses yang lain. Pada contoh ini code.Shared variables
int turninitially turn=0turn = i, Pi can enter its critical section
Process Pi :
do{while(turn!=1);critical section turn=j;remainder section}while(1);
Memenuhi mutual exclusion, tapi bukan progress.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 17/52
Critical Condition
Mutual Exclusion (Lanjutan)
Algoritma 1 : Disini kita akan mencoba membuat sebuah rangkaian solusi-
solusi dari permasalahan yang makin meningkat kerumitannya. Pada semua contoh, i adalah proses yang sedang berjalan, j
adalah proses yang lain. Pada contoh ini code.Shared variables
int turninitially turn=0turn = i, Pi can enter its critical section
Process Pi :
do{while(turn!=1);critical section turn=j;remainder section}while(1);
Memenuhi mutual exclusion, tapi bukan progress.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 18/52
Critical Condition
Mutual Exclusion (Lanjutan)
Algoritma 2 : FLAG untuk setiap proses yang memberi STATE: Setiap proses memantau suatu flag yang mengindikasikan ia
ingin memasuki critical section. Dia memeriksa flag poses laindan tidak akan memasuki critical section bila ada proses lainyang sedang masuk.
Shared variablesboolean flag[2];initially flag [0] = flag [1] = falseflag [i] = true , Pi ready to enter its critical section
Process Pi do{ flag[i]:=true; while(turn!=1);critical section turn=j;remainder section }while(1);
Memenuhi mutual exclusion, tapi tidak memenuhi progess.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 19/52
Critical Condition
Mutual Exclusion (Lanjutan)
Algoritma 3 : FLAG untuk meminta izin masuk: Setiap proses mengeset sebuah flag untuk meminta izin masuk. Lalu
setiap proses mentoggle bit untuk mengizinkan yang lain untuk yang
pertama Kode ini dijalankan untuk setiap proses i
Shared variablesF boolean flag[2];initially flag[0] = flag[1] = falseF flag[i] = true;Pi ready to enter its critical section
Gabungan shared variables dari algorima 1 dan 2Process Pi
do { flag[i]:=true;turn = j; while(flag[j] and turn = j);critical section flag[i] = false;remainder section }while(1);
Memenuhi ketiga persyaratan, memecahkan persoalan critical section untuk kedua proses
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 20/52
Semaphore
Jika kita ingin dapat melakukan proses tulis lebih rumitkita membutuhkan sebuah bahasa untuk melakukannya.Kita akhirnya medefinisikan semaphore yang kitaasumsikan sebagai sebuah operasi atomik.
Semaphore adalah pendekatan yang diajukan olehDjikstra, dengan prinsip bahwa dua proses atau lebihdapat bekerja sama dengan menggunakan penanda-penanda sederhana. Seperti proses dapat dipaksaberhenti pada suatu saat, sampai proses mendapatkanpenanda tertentu itu. Sembarang kebutuhan koordinasikompleks dapat dipenuhi dengan struktur penanda yangcocok untuk kebutuhan itu. Variabel khusus untukpenanda ini disebut semaphore.
Semaphore mempunyai dua sifat, yaitu:1. Semaphore dapat diinisialisasi dengan nilai non-negatif.2. Terdapat dua operasi terhadap semaphore, yaitu Down dan
Up. Usulan asli yang disampaikan Djikstra adalah operasi Pdan V.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 21/52
Semaphore
Operasi Down
Operasi ini menurunkan nilai semaphore, jika nilaisemaphore menjadi non-positif maka proses yangmengeksekusinya diblocked.
Ilustrasi Block :Type Semaphore = Integer,Procedure Down(Var: semaphore);Begins := s-1; if s <= 0 Then BeginTempatkan antrian pada antrian untuk semaphore s Proses diblockedEnd;
End; Operasi Down adalah atomic, tak dapat diinterupsi
sebelaum diselesaikan.Emnurunkan nilai, memeriksanilai, menempatkan proses pada antrian danmemblocked sebagai instruksi tunggal. Sejak dimulai,tak ada proses alain yang dapat mengakses
semaphore sampai operasi selesai atau diblocked.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 22/52
Semaphore
Operasi Up
Operasi Up menakkan nilai semaphore. Jika satu prosesatau lebih diblocked pada semaphore itu tak dapatmenyelesaikan operasi Down, maka salah satu dipiliholeh system dan menyelesaikan operasi Down-nya.
Urutan proses yang dipilih tidak ditentukan oleh Djikstra,dapat dipilih secara acak. Block :
Type Semaphore = Integer,Procedure Down(Var: semaphore);Begins := s + 1; if s <= 0 ThenBeginPindahkan satu proses P dari antrian untuk semaphore s
Tempatkan proses P di senarai readyEnd;End;
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 23/52
Problem Klasik pada Sinkronisasi
1. Problem Readers-Writers Problem lain yang terkenal adalah readers-writer problem yang
memodelkan proses yang mengakses database. Sebagai contohsebuah sistem pemesanan sebuah perusahaan penerbangan,dimana banyak proses berkompetisi berharap untuk membaca(read ) dan menulis (write). Hal ini dapat diterima bahwa banyak
proses membaca database pada saat yang sama, tetapi jikasuatu proses sedang menulis database, tidak boleh ada proseslain yang mengakses database tersebut, termasuk membacadatabase tersebut.
Dalam solusi ini, pertama-tama pembaca mengakses databasekemudian melakukan DOWN pada semaphore db.. Langkahselanjutnya readers hanya menaikkkan nilai sebuah counter.Hasil dari pembaca nilai counter diturunkan dan nilai terakhirdilakukan UP pada semaphore, mengizinkan memblok writer.
Misalkan selama sebuah reader menggunakan database, readerlain terus berdatangan. Karena ada dua reader pada saatbersamaan bukanlah sebuah masalah, maka reader yang keduaditerima, reader yang ketiga juga dapat diterima jika terusberdatangan reader-reader baru.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 24/52
Problem Klasik pada Sinkronisasi
Sekarang misalkan writer berdatangan terus menerus. Writertidak dapat diterima ke database karena writer hanya bisamengakses data ke database secara ekslusif, jadi writerditangguhkan. Nanti penambahan reader akan menunjukkanpeningkatan. Selama paling tidak ada satu reader yang aktif,reader berikutnya jika datang akan diterima.
Sebagai konsekuensi dari strategi ini, selama terdapat suplaireader yang terus-menerus, mereka akan dilayani segerasesuai kedatanga mereka. Writer akan ditunda sampai tidakada reader lagi. Jika sebuah reader baru tiba, katakan, setiapdua detik, dan masing-masing reader mendapatkan limadetik untuk melakukan tugasnya, writer tudak akan pernahmendapatkan kesempatan.
Untuk mencegah situasi seperti itu, program dapat ditulisagak sedikit berbeda: Ketika reader tiba dan writermenunggu, reader ditunda dibelakang writer yang justruditerima dengan segera. Dengan cara ini, writer tidak harusmenunggu reader yang sedang aktif menyelesaikanpekerjaannya, tapi tidak perlu menunggu reader lain yang
datang berturut-turut setelah itu.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 25/52
Problem Klasik pada Sinkronisasi
2. Problem Dining Philosopers Pada tahun 1965, Djikstra menyelesaikan sebuah
masalah sinkronisasi yang beliau sebut dengan diningphilisophers problem. Dining philosophers dapat diuraikansebagai berikut: Lima orang filosuf duduk mengelilingisebuah meja bundar. Masing-masing filosof mempunyai
sepiring spageti. Spageti-spageti tersebut sangat licin danmembutuhkan dua garpu untuk memakannya. Diantarasepiring spageti terdapat satu garpu.
Kehidupan para filosof terdiri dari dua periode, yaitumakan atau berpikir. Ketika seorang filosof lapar, diaberusaha untuk mendapatkan garpu kiri dan garpu kanan
sekaligus. Jika sukses dalam mengambil dua garpu,filosof tersebut makan untuk sementara waktu, kemudianmeletakkan kedua garpu dan melanjutkan berpikir.
Pertanyaan kuncinya adalah, dapatkah anda menulisprogram untuk masing-masing filosof yang melakukanapa yang harus mereka lakukan dan tidak pernahmengalami kebuntuan.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 26/52
Problem Klasik pada Sinkronisasi Prosedur take-fork menunggu sampai garpu-garpu yang
sesuaididapatkan dan kemudian menggunakannya.Sayangnya dari solusi ini ternyata salah. Seharusnya limaorang filosof mengambil garpu kirinya secara bersamaan.Tidak akan mungkin mereka mengambil garpu kananmereka, dan akan terjadi deadlock.
Kita dapat memodifikasi program sehingga setelah
mengambil garpu kiri, program memeriksa apakah garpukanan meungkinkan untuk diambil. Jika garpu kanan tidakmungkin diambil, filosof tersebut meletakkan kembali garpukirinya, menunggu untuk beberapa waktu, kemudiamengulangi proses yang sama. Usulan tersebut juga salah,walau pun dengan alasan yang berbeda. Dengan sedikitnasib buruk, semua filosof dapat memulai algoritma secarabersamaan, mengambil garpu kiri mereka, melihat garpukanan mereka yang tidak mungkin untuk diambil,meletakkan kembali garpu kiri mereka, menunggu,mengambil garpu kiri mereka lagi secara bersamaan, danbegitu seterusnya. Situasi seperti ini dimana semua programterus berjalan secara tidak terbatas tetapi tidak ada
perubahan/kemajuan yang dihasilkan disebut starvation.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 27/52
Problem Klasik pada Sinkronisasi Sekarang anda dapat berpikir "jika filosof dapat saja
menunggu sebuah waktu acak sebagai pengganti waktu yangsama setelah tidak dapat mengambil garpu kiri dan kanan,kesempatan bahwa segala sesuatau akan berlanjut dalamkemandegan untuk beberapa jam adalah sangat kecil."Pemikiran seperti itu adalah benar,tapi beberapa aplikasimengirimkan sebuah solusi yang selalu bekerja dan tidak ada
kesalahan tidak seperti hsk nomor acak yang selalu berubah. Sebelum mulai mengambil garpu, seorang filosof melakukan
DOWN di mutex. Setelah menggantikan garpu dia harusmelakukan UP di mutex. Dari segi teori, solusi ini cukupmemadai. Dari segi praktek, solusi ini tetap memilikimasalah. Hanya ada satu filosof yang dapat makan spagetidalam berbagai kesempatan. Dengan lima buah garpu,seharusnya kita bisa menyaksikan dua orang filosof makanspageti pada saat bersamaan.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 28/52
Monitor
Solusi sinkronisasi ini dikemukakan oleh Hoare padatahun 1974. Monitor adalah kumpulan prosedur,variabel dan struktur data di satu modul atau paketkhusus. Proses dapat memanggil prosedur-prosedurkapan pun diinginkan. Tapi proses tak dapatmengakses struktur data internal dalam monitor secara
langsung. Hanya lewat prosedur-prosedur yangdideklarasikan minitor untuk mengakses strukturinternal.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 29/52
Monitor Properti-properti monitor adalah sebagai berikut: Variabel-variabel data lokal, hanya dapat diakses oleh
prosedur-prosedur dala monitor dan tidak oleh prosedur diluar monitor.
Hanya satu proses yang dapat aktif di monitor pada satu saat.Kompilator harus mengimplementasi ini(mutual exclusion).
Terdapat cara agar proses yang tidak dapat berlangsung di-blocked. Menambahkan variabel-variabel kondisi, dengan duaoperasi, yaitu Wait dan Signal.
Wait: Ketika prosedur monitor tidak dapat berkanjut (misalproducer menemui buffer penuh) menyebabkan prosespemanggil diblocked dan mengizinkan proses lain masukmonitor.
Signal: Proses membangunkan partner-nya yang sedang
diblocked dengan signal pada variabel kondisi yang sedangditunggu partnernya. Versi Hoare: Setelah signal, membangunkan proses baru agar
berjalan dan menunda proses lain. Versi Brinch Hansen: Setelah melakukan signal, proses segera
keluar dari monitor.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 30/52
Monitor
Dengan memaksakan disiplin hanya satu proses padasatu saat yang berjalan pada monitor, monitormenyediakan fasilitas mutual exclusion. Variabel-variabel data dalam monitor hanya dapat diakses olehsatu proses pada satu saat. Struktur data bersamadapat dilindungi dengan menempatkannya dalam
monitor. Jika data pada monitor merepresentasikansumber daya, maka monitor menyediakan fasilitasmutual exclusion dalam mengakses sumber daya itu.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 31/52
DEADLOCK
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 32/52
LATAR BELAKANG Misalkan pada suatu komputer terdapat dua buah program,
sebuah tape drive dan sebuah printer . Program Amengontrol tape drive, sementara program B mengontrol printer . Setelah beberapa saat, program A meminta printer ,tapi printer masih digunakan. Berikutnya, B meminta tapedrive, sedangkan A masih mengontrol tape drive. Duaprogram tersebut memegang kontrol terhadap sumber
daya yang dibutuhkan oleh program yang lain. Tidak adayang dapat melanjutkan proses masing-masing sampaiprogram yang lain memberikan sumber dayanya, tetapitidak ada yang mengalah. Kondisi inilah yang disebutDeadlock atau pada beberapa buku disebut Deadly Embrace
Deadlock yang mungkin dapat terjadi pada suatu prosesdisebabkan proses itu menunggu suatu kejadian tertentuyang tidak akan pernah terjadi. Dua atau lebih prosesdikatakan berada dalam kondisi deadlock , bila setiap prosesyang ada menunggu suatu kejadian yang hanya dapatdilakukan oleh proses lain dalam himpunan tersebut.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 33/52
LATAR BELAKANG Terdapat kaitan antara overhead dari mekanisme koreksi
dan manfaat dari koreksi deadlock itu sendiri. Padabeberapa kasus, overhead atau ongkos yang harus dibayaruntuk membuat sistem bebas deadlock menjadi hal yangterlalu mahal dibandingkan jika mengabaikannya.Sementara pada kasus lain, seperti pada real-time processcontrol, mengizinkan deadlock akan membuat sistem
menjadi kacau dan membuat sistem tersebut tidakberguna. Contoh berikut ini terjadi pada sebuah persimpangan jalan.
Beberapa hal yang dapat membuat deadlock pada suatupersimpangan, yaitu:1. Terdapat satu jalur pada jalan.
2. Mobil digambarkan sebagai proses yang sedang menujusumber daya.3. Untuk mengatasinya beberapa mobil harus preempt (mundur).4. Sangat memungkinkan untuk terjadinya starvation (kondisi
proses tak akan mendapatkan sumber daya).
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 34/52
ILUSTRASI DEADLOCK
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 35/52
Resources-Allocation Graph
Sebuah cara visual (matematika) untukmenentukan apakah ada deadlock , ataukemungkinan terjadinya.
G = (V, E) Graf berisi node and edge. Node Vterdiri dari proses-proses = {P1, P2, P3, ...} dan
jenis resource. {R1, R2, ...} Edge E adalah (Pi,Rj) atau (Ri, Pj)
Sebuah panah dari process ke resource menandakan proses meminta resource. Sebuahpanah dari resource ke process menunjukkan
sebuah instance dari resource telah dtempatkanke proses. Process adalah lingkaran, resource adalah kotak; titik-titik merepresentasikan jumlah instance dari resource Dalam tipe.Meminta poin-poin ke kotak, perintah datang darititik.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 36/52
Resources-Allocation Graph
Jika graf tidak berisilingkaran, makatidak ada prosesyang deadlock .
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 37/52
Resources-Allocation Graph
Jika membentuklingkaran, maka:
jika tipe resource memiliki banyakinstance, maka
deadlock DAPATada.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 38/52
Resources-Allocation Graph
jika setiap tiperesource mempunyaisatu instance, makadeadlock telah terjadi.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 39/52
Model Sistem
Menurut Coffman dalam bukunya "OperatingSystem" menyebutkan empat syarat bagiterjadinya deadlock , yaitu :1. Mutual Exclusion -- Suatu kondisi dimana setiap sumber
daya diberikan tepat pada satu proses pada suatu
waktu.2. Hold and Wait -- Kondisi yang menyatakan proses-proses yang sedang memakai suatu sumber daya dapatmeminta sumber daya yang lain.
3. Non-pre-emptive -- Kondisi dimana suatu sumber dayayang sedang berada pada suatu proses tidak dapat
diambil secara paksa dari proses tersebut,sampaiproses itu melepaskannya.4. Circular Wait -- Kondisi yang menyatakan bahwa
adanya rantai saling meminta sumber daya yangdimiliki oleh suatu proses oleh proses lainnya.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 40/52
STRATEGI MENGHADAPIDEADLOCK
Strategi untuk menghadapi deadlock dapat dibagimenjadi tiga pendekatan, yaitu:
1. Mengabaikan adanya deadlock .
2. Memastikan bahwa deadlock tidak akan pernah ada,baik dengan metode Pencegahan, dengan mencegahempat kondisi deadlock agar tidak akan pernah terjadi.Metode Menghindari deadlock , yaitu mengizinkanempat kondisi deadlock , tetapi menghentikan setiapproses yang kemungkinan mencapai deadlock .
3. Membiarkan deadlock untuk terjadi, pendekatan ini
membutuhkan dua metode yang saling mendukung,yaitu:1. Pendeteksian deadlock , untuk mengidentifikasi ketika
deadlock terjadi.
2. Pemulihan deadlock , mengembalikan kembali sumberdaya yang dibutuhkan pada proses yang memintanya.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 41/52
CONTOH METODEMENGHADAPI DEADLOCK
1. Strategi Ostrich
Pendekatan yang paling sederhana adalah denganmenggunakan strategi burung unta: masukkan kepala dalampasir dan seolah-olah tidak pernah ada masalah sama sekali.
Beragam pendapat muncul berkaitan dengan strategi ini.Menurut para ahli Matematika, cara ini sama sekali tidakdapat diterima dan semua keadaan deadlock harus ditangani.Sementara menurut para ahli Teknik, jika komputer lebihsering mengalami kerusakkan disebabkan oleh kegagalanhardware, error pada kompilator atau bugs pada sistem
operasi. Maka ongkos yang dibayar untuk melakukan penanganan
deadlock sangatlah besar dan lebih baik mengabaikankeadaan deadlock tersebut. Metode ini diterapkan pada
sistem operasi UNIX dan MINIX.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 42/52
CONTOH METODEMENGHADAPI DEADLOCK
Metode ini merupakan metode yang paling seringdigunakan. Metode Pencegahan dianggap sebagai solusiyang bersih dipandang dari sudut tercegahnya deadlock .Tetapi pencgahan akan mengakibatkan kinerja utilisasi
sumber daya yang buruk. Metode pencegahan menggunakan pendekatan dengan
cara meniadakan empat syarat yang dapat menyebabkandeadlock terjadi pada saat eksekusi Coffman (1971).
Syarat pertama yang akan dapat ditiadakan adalah Mutual Exclusion, jika tidak ada sumber daya yang secara khusus
diperuntukkan bagi suatu proses maka tidak akan pernahterjadi deadlock . Namun jika membiarkan ada dua ataulebih proses mengakses sebuah sumber daya yang samaakan menyebabkan chaos. Langkah yang digunakan adalahdengan spooling sumber daya, yaitu dengan mengantrikan job-job pada antrian dan akan dilayani satu-satu.
2. MENCEGAH DEADLOCK
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 43/52
CONTOH METODEMENGHADAPI DEADLOCK
Beberapa masalah yang mungkin terjadi adalah:1. Tidak semua dapat di-spool , tabel proses sendiri tidak mungkin untuk di-
spool 2. Kompetisi pada ruang disk untuk spooling sendiri dapat mengarah pada
deadlock
Hal inilah yang menyebabkan mengapa syarat pertama tidakdapat ditiadakan, jadi mutual exclusion benar-benar tidakdapat dihilangkan.
Cara kedua dengan meniadakan kondisi hold and wait terlihatlebih menjanjikan. Jika suatu proses yang sedangmenggunakan sumber daya dapat dicegah agar tidak dapatmenunggu sumber daya yang lain, maka deadlock dapat
dicegah. Langkah yang digunakan adalah dengan membuatproses agar meminta sumber daya yang mereka butuhkanpada awal proses sehingga dapat dialokasikan sumber dayayang dibutuhkan. Namun jika terdapat sumber daya yangsedang terpakai maka proses tersebut tidak dapat memulaiprosesnya.
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 44/52
CONTOH METODEMENGHADAPI DEADLOCK
Masalah yang mungkin terjadi:1. Sulitnya mengetahui berapa sumber daya yang
dibutuhkan pada awal proses
2. Tidak optimalnya pengunaan sumber daya jika adasumber daya yang digunakan hanya beberapa waktu dan
tidak digunakan tapi tetap dimiliki oleh suatu prosesyang telah memintanya dari awal.
Meniadakan syarat ketiga non preemptive ternyata tidak lebih menjanjikan darimeniadakan syarat kedua, karena dengan
meniadakan syarat ketiga maka suatu prosesdapat dihentikan ditengah jalan. Hal ini tidakdimungkinkan karena hasil dari suatu prosesyang dihentikan menjadi tidak baik.
CONTOH METODE
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 45/52
CONTOH METODEMENGHADAPI DEADLOCK
Cara terakhir adalah dengan meniadakan syarat keempatcircular wait . Terdapat dua pendekatan, yaitu:
1. Mengatur agar setiap proses hanya dapatmenggunakan sebuah sumber daya pada suatuwaktu, jika menginginkan sumber daya lain makasumber daya yang dimiliki harus dilepas.
2. Membuat penomoran pada proses-proses yangmengakses sumber daya. Suatu prosesdimungkinkan untuk dapat meminta sumber dayakapan pun, tetapi permintaannya harus dibuatterurut.
Masalah yang mungkin terjadi dengan mengatur bahwa
setiap proses hanya dapat memiliki satu proses adalahbahwa tidak semua proses hanya membutuhkan satusumber daya, untuk suatu proses yang kompleksdibutuhkan banyak sumber daya pada saat yangbersamaan. Sedangkan dengan penomoran masalahyang dihadapi adalah tidak terdapatnya suatupenomoran yang dapat memuaskan semua pihak.
CONTOH METODE
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 46/52
CONTOH METODEMENGHADAPI DEADLOCK
Tabel Deadlock
Syarat Langkah Kelemahan
Mutual Exclusion
Spooling sumber daya Dapat menyebabkan chaos
Hold and Wait
Meminta sumber daya diawal
Sulit memperkirakan di awal dantidak optimal
No Pre- emptive
Mengambil sumber daya ditengah proses
Hasil proses tidak akan baik
Circular Wait
Penomoran permintaansumber daya
Tidak ada penomoran yangmemuaskan semua pihak
CONTOH METODE
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 47/52
CONTOH METODEMENGHADAPI DEADLOCK
Pendekatan metode ini adalah dengan hanya memberikesempatan ke permintaan sumber daya yang tidakmungkin akan menyebabkan deadlock . Metode inimemeriksa dampak pemberian akses pada suatu
proses, jika pemberian akses tidak mungkin menujukepada deadlock , maka sumber daya akan diberikanpada proses yang meminta. Jika tidak aman, prosesyang meminta akan di-suspend sampai suatu waktupermintaannya aman untuk diberikan. Kondisi initerjadi ketika setelah sumber daya yang sebelumnya
dipegang oleh proses lain telah dilepaskan. Kondisi aman yang dimaksudkan selanjutnya disebut
sebagai safe-state, sedangkan keadaan yang tidakmemungkinkan untuk diberikan sumber daya yangdiminta disebut unsafe-state.
2. MENGHINDARI DEADLOCK
CONTOH METODE
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 48/52
CONTOH METODEMENGHADAPI DEADLOCK
Kondisi Aman (Safe state) Suatu keadaan dapat dinyatakan sebagai
safe state jika tidak terjadi deadlock danterdapat cara untuk memenuhi semuapermintaan sumber daya yang ditundatanpa menghasilkan deadlock . Dengan caramengikuti urutan tertentu.
Kondisi Tak Aman (Unsafe state)
Suatu state dinyatakan sebagai state takselamat (unsafe state) jika tidak terdapatcara untuk memenuhi semua permintaaanyang saat ini ditunda dengan menjalankanproses-proses dengan suatu urutan.
CONTOH METODE
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 49/52
CONTOH METODEMENGHADAPI DEADLOCK
KONDISI SAFE DAN KONDISI UNSAFE
M d t k i D dl k d
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 50/52
Mendeteksi Deadlock danMemulihkan Deadlock
Metode ini mengunakan pendekatan denganteknik untuk menentukan apakah deadlock sedang terjadi serta proses-proses dan sumberdaya yang terlibat dalam deadlock tersebut.Setelah kondisi deadlock dapat dideteksi, makalangkah pemulihan dari kondisi deadlock dapatsegera dilakukan.
Langkah pemulihan tersebut adalah denganmemperoleh sumber daya yang diperlukan olehproses-proses yang membutuhkannya. Beberapa
cara digunakan untuk mendapatkan sumber dayayang diperlukan, yaitu dengan terminasi prosesdan pre-emption (mundur) suatu proses. Metodeini banyak digunakan pada komputer mainframeberukuran besar.
M d t k i D dl k d
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 51/52
Mendeteksi Deadlock danMemulihkan Deadlock
Terminasi Proses
Metode ini akan menghapus proses-proses yang terlibatpada kondisi deadlock dengan mengacu pada beberapasyarat. Beberapa syarat yang termasuk dalam metode iniadalah, sebagai berikut:1. Menghapus semua proses yang terlibat dalam kondisi
deadlock (solusi ini terlalu mahal).2. Menghapus satu persatu proses yang terlibat, sampai
kondisi deadlock dapat diatasi (memakan banyakwaktu).
3. Menghapus proses berdasarkan prioritas, waktueksekusi, waktu untuk selesai, dan kedalaman darirollback .
M d t k i D dl k d
5/16/2018 06.Sinkronisasi Dan Deadlock - slidepdf.com
http://slidepdf.com/reader/full/06sinkronisasi-dan-deadlock 52/52
Mendeteksi Deadlock danMemulihkan Deadlock
Resources Preemption
Metode ini lebih menekankan kepada bagaimanamenghambat suatu proses dan sumber daya, agar tidakterjebak pada unsafe condition.
Beberapa langkahnya, yaitu:1. Pilih salah satu - proses dan sumber daya yang akan
di- preempt .2. Rollback ke safe state yang sebelumnya telah
terjadi.3. Mencegah suatu proses agar tidak terjebak pada
starvation karena metode ini.