Concurrency 1 : Mutual Exclusion dan Sinkronisasi (P ( e P rtemuan ua ke-9) 9 September 2014

Concurrency 1: Mutual Exclusion dan Sinkronisasi (Pertemuan keke-9)

September 2014

Pokok Bahasan • Pokok Bahasan: – Sinkronisasi dan Mutual Exclusion • Sub Pokok Bahasan: – Prinsip semaphore biner – Pengendalian urutan eksekusi proses dengan semaphore – Kasus Producer-Consumer dengan semaphore • TIU: – Mahasiswa dapat memahami konsep sinkronisasi dan

mutual exclusion

• TIK: – Mahasiswa dapat menjelaskan prinsip semaphore biner – Mahasiswa dapat menjelaskan pengendalian urutan eksekusi proses dengan semaphore – Mahasiswa dapat menjelaskan solusi kasus ProducerConsumer dengan semaphore

Sistem Operasi/2014 #2

Semaphore Biner

(1)

• Ketentuan: – Inisialisasi variabel semaphore hanya bernilai 0 atau 1 – Prosedur semWaitB: • Akan memeriksa nilai variabel semaphore • Jika nilai variabel = 1  diubah menjadi 0 • Jika nilai variabel = 0  proses tersebut di-blok dan dimasukkan ke dalam antrian

– Prosedur semSignalB: • Akan memeriksa jumlah proses dalam antrian dengan fungsi is_empty() • Jika tidak ada proses dalam antrian  nilai variabel menjadi 1 • Jika ada proses dalam antrian:  Sebuah proses dipindahkan dari antrian ke status ready  Nilai variabel tetap = 0 Sistem Operasi/2014 #3

Semaphore Biner

(2)

• Definisi semaphore biner


Strong and weak semaphore

(1)

• Strong semaphore: – Adalah semaphore yang menentukan urutan proses yang akan dikeluarkan dari antrian – Dapat mencegah terjadinya starvation – Model semaphore yang ada di OS

• Weak semaphore:

– Adalah semaphore yang tidak menentukan urutan proses yang akan dikeluarkan dari antrian – Dapat terjadi

starvation


Strong and weak semaphore • Contoh strong

(2) •Nilai sebelum A dieksekusi

semaphore

• Proses A, B, dan C menggunakan semWait tanpa semSignal • Proses D menggunakan semSignal tanpa semWait  pemegang kunci



(3)



(4)

• Keterangan: 1. Mula-mula nilai s = 1, proses A, B, D, dan C berada dalam status ready; proses A dieksekusi, nilai s berkurang menjadi 0 2. Proses A selesai  masuk status ready; proses B dieksekusi  s menjadi -1  proses B di-blok  masuk antrian 3. Proses D dieksekusi 4. semSignal  s menjadi 0  proses B dibebaskan dari antrian; proses D selesai  masuk status ready lagi Urutan eksekusi: A, B, D Sistem Operasi/2014 #8

Strong and weak semaphore •

(5)

Keterangan: (cont’d) 5. Proses C dieksekusi  s menjadi -1  C di-blok  masuk antrian; hal yang sama terjadi pula untuk proses A dan B  diblok  masuk antrian  s menjadi -3 6. Proses D dieksekusi lagi 7. semSignal s menjadi -2  proses C dibebaskan Urutan eksekusi: A, B, D, C, A, B, D, C, D, A, D, B, D, C, D, A, D, …


Implementasi Mutual Exclusion dengan Semaphore (1) • Pemanfaatan semaphore primitif dalam mutex


Implementasi Mutual Exclusion dengan Semaphore (2) • Contoh uruturutan eksekusi 3 buah proses dengan semaphore


Contoh Kasus 1:

Producer Consumer (PC) – Infinite Buffer (1)

• Deskripsi masalah: – Terdapat satu atau lebih producer yang menghasilkan data (record, karakter, dsb) dan disimpan di buffer – Terdapat satu consumer yang mengambil data dari buffer – Masalahnya adalah bagaimana caranya supaya dalam satu saat hanya terdapat satu produser atau satu consumer saja yang dapat mengakses buffer…?


Contoh Kasus 1:

Producer Consumer – Infinite Buffer (2) • Fungsi producer dan consumer: producer: while (true) { /* produce item v */ b[in] = v; in++; }

consumer: while (true) { while (in <= out) /*do nothing */; w = b[out]; out++; /* consume item w */ }


Contoh Kasus 1:

Producer Consumer – Infinite Buffer (3) • Struktur buffer dengan kapasitas tidak terbatas

(infinite)

• Consumer tidak boleh mengakses buffer yang kosong Sistem Operasi/2014 #14

Contoh Kasus 1:

Producer Consumer – Infinite Buffer

(4)

• Solusi I: – Implementasi dengan

semaphore biner

– Supaya lebih sederhana variabel in dan out diganti dengan n yang menunjukkan jumlah data yang ada di buffer, dimana n = in-out – semSignalB(delay) digunakan untuk mencegah consumer mengakses buffer kosong


Contoh Kasus 1:


(5)

• Urutan eksekusi normal (PCPC…) OK


Contoh Kasus 1:

Producer Consumer – Infinite Buffer (6)

• Urutan eksekusi (PPPCCC…)  OK


Contoh Kasus 1:


(7)

• Urutan eksekusi consumer disela oleh producer (PCPCCC…)  not OK • Jika if(n==0) … dipindah ke critical section  belum menyelesaikan masalah  masih dapat terjadi deadlock setelah baris ke-10


Contoh Kasus 1:


(8)

• Penyelesaian: – Tambahkan variabel lokal pada program comsumer


Contoh Kasus 1:

Producer

Consumer – Infinite Buffer

(9)

• Pembuktian urutan PCPCC…  OK • Apakah sudah dapat mencegah terjadinya kesalahan ?? Buktikan…!!


Contoh Kasus 1:


(10)

• Solusi II: – Implementasi dengan

counting semaphore

– Lebih sederhana, lebih jelas


Contoh Kasus 1:


(11)

• Urutan eksekusi normal (PCPCC…)  OK


Contoh Kasus 1:


(12)

• Apa yang terjadi jika terjadi salah ketik program, sehingga

urutan semSignal pada producer terbalik ???  masih OK


Contoh Kasus 1:


(13)

• Apa yang terjadi jika terjadi salah ketik program, sehingga urutan

semWait pada consumer terbalik ??? 

deadlock


Pustaka [STA09] Stallings, William. 2009. Operating

System: Internal and Design Principles. 6th edition. Prentice Hall


Concurrency 1 : Mutual Exclusion dan Sinkronisasi (P ( e P rtemuan ua ke-9) 9 September 2014

Recommend Documents