CRITICAL REGIONS DAN MONITORS Oleh Sergio (1203001052) - <
[email protected]> Tedi Kurniadi (1203001109) -
Copyright © 2004 Sergio - Tedi Kurniadi – silahkan menggunakan, memodifikasi, ataupun menyebarluaskan isi dokumen ini, selama tidak untuk tujuan komersil dan tidak menghilangkan nama penulis. 1
Kelemahan Semafor 1. Konsep low level 2. Menghilangkan wait à tidak memenuhi mutex (mutual exclusion) 3. Menghilangkan signal à deadlock 4. Kode Semafor tersebar pada program à problem maintenance
Butuh konsep high level! 2
Critical Regions 1. 2. 3.
Bagian kode yang selalu dieksekusi dengan syarat mutex Melepas tanggung jawab mutex dari sisi programmer kepada compiler Terdiri dari dua bagian: a. Variabel yang harus diakses secara mutex b. Statement yang mengidentifikasi sebuah critical region yang dimana variabel-variabel di dalamnya dapat diakses Var v : shared T; region v do { begin … end } 3
Conditional Critical Regions Critical Regions != Semafor CR tidak hanya menggunakan mutex, tetapi juga boolean expression dalam implementasi sinkronisasinya (conditional). region v when B do{ begin ... end }
4
Cara Kerja CCR m=0 main queue
join
event queue
m = mutex
m=1 m--
cek kondisi B = true (boolean B)
Eksekusi statement
B = false m++ selesai 5
Implementasi CCR Bounded Buffer buffer: record { buf: array[1..SIZE] of data next_full, next_empty: integer := 1,1 full_slots: integer := 0 } procedure insert(d: bdata) region buffer when full_slots < SIZE { buf[next_empty] := d next_empty := next_empty mod SIZE + 1 full_slots +:= 1 }
6
Implementasi CCR (cont.) function remove: bdata region buffer when full_slots > 0 { d: bdata := buf[next_full] next_full := next_full mod SIZE + 1 full_slots -:= 1 return d }
Implementasi pada Java? synchronized (object) { … } 7
Monitors
Bagan Ilustrasi Monitors 8
Monitors • • • • •
•
terdiri dari private data dan operasi-operasi terhadap data tersebut dpt berisi type, konstanta, variabel, dan prosedur monitor body melakukan inisialisasi pada private data compiler mengawasi syarat mutex pada monitor setiap monitor memiliki boundary queue, tempat dimana proses-proses yg ingin memanggil routine dalam monitor menunggu, apabila monitor sedang digunakan monitor adalah pengembangan CCR - semua code yang mengakses shared data dilokalisasi 9
Variable Condition memungkinkan proses untuk melakukan block sampai kondisi true condition x,y;
Contoh variabel condition: Delay dan Resume * x.delay() : melakukan block pada proses yang memanggil operasi ini dan melepas lock monitor (menunggu) * x.resume() : meneruskan satu buah proses yang blocked. Apabila tidak ada proses yg blocked, operasi resume tidak menimbulkan efek. (berbeda dengan signal pada semafor yang selalu mengubah status dari semafor) 10
Variable Condition (Problem) x.resume() pada monitor dengan sebuah proses lainnya sedang menunggu (x.delay()) Solusi: -Resume-and-Continue à proses Q harus menunggu sampai P melepas monitor -Resume-and-Wait à proses P harus menunggu sampai Q melepas monitor -Immediate Resumption à P langsung melepas monitor (Pascal-FC) 11
Implementasi Monitors Dining Philosopher monitor diningPhilosophers{ int[] state = new int[5]; static final int THINKING = 0; static final int HUNGRY = 1; static final int EATING = 2; condition[] self = new condition[5]; public diningPhilosophers { for (int i = 0; i < 5; i++) state[i] = THINKING; } 12
Implementasi Monitors (cont.) public entry pickUp(int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self[i].wait; } public entry putDown(int i) { state[i] = THINKING; // test left and right neighbors test(i + 4 % 5); test(i + 1 % 5); } 13
Implementasi Monitors (cont.) private test(int i) { if ( (state[i + 4 % 5) != EATING) && (state[i] == HUNGRY) && (state[i + 1 % 5 != EATING) ) { state[i] = EATING; self[i].signal; } } }
Applet Dining Philosopher: http://www.hta-be.bfh.ch/~fischli/kurse/threads/phil/ 14
Resource Allocation Monitor Resource Allocation { boolean busy; condition x; void acquire (int time) { if (busy) x.wait(time); busy = true; } 15
Resource Allocation (cont.) void release() { busy = false; x.signal(); } void init() { busy = false; } } 16
