ILUSTRASI KLASIK: BOUNDED BUFFER

ILUSTRASI KLASIK: BOUNDED BUFFER Oleh kelompok 54.4: Reza Lesmana (1203000978) Suryamita Harindrari (1203001087) Fitria Rahma Sari (1203007034) Kritik dapat dikirimkan melalui [email protected] 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

1

Komunikasi proses dalam sistem Pertukaran pesan memerlukan antrian sementara (buffer), ada tiga: •

Kapasitas nol

•

Kapasitas terbatas

•

Kapasitas tidak terbatas 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

2

Bounded Buffer? n

Suatu struktur data yang mampu untuk menyimpan beberapa nilai dan mengeluarkannya kembali ketika diperlukan

54.4 Ilustrasi Klasik: Bounded Buffer© 2004

3

Implementasi n

Producer – Consumer Problem Dua proses berbagi buffer yang sama dengan ukuran tertentu. Producer menaruh informasi ke dalam buffer, dan consumer mengambilnya. 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

4

Hal yang harus diperhatikan n n n

n

Bounded buffer memiliki batas banyaknya data yang dimasukkan Barang yang dikonsumsi oleh konsumer terbatas Jika bounded buffer telah penuh produser tidak mampu menaruh lagi dan akan menunggu sampai ada tempat yang kosong Jika bounded buffer kosong maka konsumer harus menunggu sampai ada barang yang ditaruh oleh produser 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

5

4 Masalah dalam Bounded Buffer n n n n

Busy wait Race Condition Deadlock Livelock


6

UnsynchronizedBoundedBuffer public class protected protected protected protected

UnsynchronizedBoundedBuffer { final Object[] goods; int putPtr = 0; int takePtr = 0; int usedSlots = 0;

public UnsynchronizedBoundedBuffer( int capacity ) throws IllegalArgumentException { if( capacity <= 0 ) throw new IllegalArgumentException(); goods = new Object[capacity]; } public void put( Object x) throws InterruptedException { while( usedSlots == goods.length ) Thread.yield(); usedSlots++; goods[putPtr] = x; putPtr = ( putPtr + 1) % goods.length; } 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

7

Cont. public Object take() throws InterruptedException { while( usedSlots == 0) Thread.yield(); Object x = goods[takePtr]; goods[takePtr] = null; takePtr = ( takePtr + 1) % goods.length; usedSlots--; return x; } }


8

yield()

Thread tetap dalam runnable state tetapi mengizinkan JVM untuk mengambil runnable thread lainnya untuk dijalankan.


9

SynchronizedBoundedBuffer public class protected protected protected protected

SynchronizedBoundedBuffer{ final Object[] goods; int putPtr = 0; int takePtr = 0; int usedSlots = 0;

public SynchronizedBoundedBuffer( int capacity ) throws IllegalArgumentException { if( capacity <= 0 ) throw new IllegalArgumentException(); goods = new Object[capacity]; } public synchronized void put( Object x) throws InterruptedException { while( usedSlots == goods.length ) wait(); goods[putPtr] = x; putPtr = ( putPtr + 1) % goods.length; 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

10

Cont. if( usedSlots++ == 0 ) notifyAll(); } public synchronized Object take() throws InterruptedException { while( usedSlots == 0) wait(); Object x = goods[takePtr]; goods[takePtr] = null; takePtr = ( takePtr + 1) % goods.length; if( usedSlots-- == goods.length ) notifyAll(); return x; } } 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

11

Wait() n

1. Thread melepas lock terhadap objek.

n

2. Status thread diubah menjadi blocked.

n

3. Thread diletakkan dalam wait set untuk objek tersebut. 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

12

notify() & notifyAll() n

1. Mengambil thread dari daftar tunggu dari objek yang telah dilepas lock-nya

n

2. Memindahkan T dari wait set ke entry set

n

3. Mengubah status T dari blocked ke runnable 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

13

BufferArray public class BufferArray { protected final Object[] array; protected final putPtr = 0; protected final takePtr = 0; public BufferArray( int n ){ array = new Object[n]; } synchronized void insert( Object x ){ array[putPtr] = x; putPtr = ( putPtr + 1 )%array.length; } synchronized Object extract(){ Object x = array[ takePtr ]; array[ takePtr ] = null; takePtr = ( takePtr + 1)%array.length; return x; } 54.4 Ilustrasi Klasik: Bounded Buffer© 2004 }

14

Semaphore : Counting Version Counting Semaphore bisa digunakan untuk mengontrol akses ke resource dalam jumlah terbatas yang diberikan.


15

Ide dasar Bounded Buffer dengan Semaphore n

n

n

1. Untuk buffer berukuran n,ada sebanyak n put permits dan 0 take permits. 2. Operasi take harus acquire sebuah takepermits dan kemudian me-release sebuah put-permits. 3. Operasi put harus acquire sebuah putpermits dan kemudian me-release sebuah take-permits. 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

16

BoundedBufferWithSemaphore public class protected protected protected

BoundedBufferWithSemaphore { final BufferArray buffer; final Semaphore putPermits; final Semaphore takePermits;

public BoundedBufferWithSemaphore(int capacity ){ if( capacity <= 0 ) throw new IllegalArgumentException(); buffer = new BufferArray ( capacity ); putPermits = new Semaphore ( capacity ); takePermits = new Semaphore (0); } public void put (Object x) throws InterruptedException{ putPermits.acquire(); buffer.insert( x ); takePermits.release(); } 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

17

Cont. public Object take() throws InterruptedException{ takePermits.acquire(); Object x = buffer.extract(); putPermits.release(); return x; } }


18

Semaphore public class Semaphore implements Sync{ protected long permits; public Semaphore( long initialPermits ){ permits = initialPermits; } public synchronized void release(){ ++permits; notify(); } public void acquire() throws InterruptedException{ if( Thread.interrupted() ) throw new InterruptedException(); synchronized( this ){ try{ while( permits <= 0 ){ wait(); 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

19

Cont. --permits; } catch( InterruptedException ie ){ notify(); throw ie; } } } } // Sync interface public interface Sync{ void acquire() throws InterruptedException; void release(); } 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

20

Livelock Keadaan dimana suatu proses terus berusaha melakukan sesuatu namun selalu gagal, dikarenakan kondisi yang diperlukan agar proses tersebut bisa terus berjalan tidak terpenuhi. 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

21

Copyright Silahkan menampilkan, menyebarkan, atau mendistribusikan slide ini secara bebas, selama tidak mengubah isinya, dan tidak diperbolehkan digunakan untuk tujuan komersial. (educational only ). Kelompok 54.4 Semester gasal 2004; 54.4 Ilustrasi Klasik: Bounded Buffer© 2004

22

ILUSTRASI KLASIK: BOUNDED BUFFER

Recommend Documents