Perbedaan Bounded Buffer Problem, Readers and Writers Problem, Dining Philosophers Problem

PERBEDAAN BOUNDED BUFFER PROBLEM, READERS AND WRITERS PROBLEM, DINING PHILOSOPHERS PROBLEM

·     Bounded Buffer Problem

Bounded Buffer Problem adalah suatu struktur data untuk menampung (buffer) suatu nilai dimana kapasitasnya tertentu/terbatas (bounded). Masalah bounded buffer merupakan salah satu masalah yang menerangkan sinkronisasi antara proses-proses yang berjalan secara konkuren untuk mengakses data yang sama.

Masalah ini menjelaskan dua proses, produsen dan konsumen, yang berbagi umum, tetap ukuran buffer digunakan sebagai antrian. Tugas produser adalah untuk menghasilkan data, memasukkannya ke dalam buffer, dan mulai lagi. Pada saat yang bersamaan, konsumen mengkonsumsi data (yaitu, mengeluarkannya dari buffer), satu bagian pada suatu waktu. Yang menjadi pokok pembahasan utama dalam masalah bounded buffer adalah bagaimana jika ada dua proses berbeda yang berusaha mengakses buffer tersebut. Salah satu proses akan memberi nilai pada buffer dan mengisi buffer tersebut. Proses yang lain akan membaca nilai dan mengosongkan buffer tersebut.

Solusi untuk produsen adalah baik pergi tidur atau membuang data jika buffer penuh. Lain kali konsumen menghapus item dari buffer, itu akan memberitahu produser, yang mulai mengisi buffer lagi. Dengan cara yang sama, konsumen bisa tidur jika menemukan buffer kosong. Lain kali produser menempatkan data ke dalam buffer, itu bangun yang tidur konsumen. solusi dapat dicapai dengan sarana komunikasi antar-proses, biasanya menggunakan Semaphore. Sebuah solusi yang tidak memadai bisa mengakibatkan kebuntuan di mana kedua proses sedang menunggu untuk dibangunkan. Masalahnya juga dapat digeneralisasi untu memiliki beberapa produsen dan konsumen. Kita dapat menerapkan konsep semaphore untuk menyelesaikan masalah tersebut. Disini kita menggunakan tiga buah semaphore yaitu mutex, full dan empty. Mutex digunakan untuk menjamin hanya boleh satu proses yang berjalan mengakses buffer pada suatu waktu, awalnya dinisialisasi sebesar satu (1). Full digunakan untuk menghitung jumlah buffer yang berisi, yang pada awalnya diinisialisasi sebesar nol (0). Sedangkan empty digunakan untuk menghitung jumlah buffer yang kosong, yang awalnya dinisialisasi sebesar ukuran buffer. Beriku variabel umumt :semaphore full, empty, mutex; Inisialisasi untuk variable di atas, full = 0, empty = n, mutex = 1.

 Jadi dapat disimpulkan bahwa pokok permasalahan bounded buffer adalah bagaimana mengatur sinkronisasi dari beberapa proses yang secara konkuren ingin mengakses buffer (mengisi dan mengosongkan buffer). Pengaturan itu dilakukan dengan menerapkan konsep semaphore yang menjamin hanya ada satu proses dalam suatu waktu yang boleh mengakses buffer sehingga tidak terjadi race condition.

·     Readers and Writers Problem

Masalah Readers/Writers adalah salah satu masalah sinkronisasi klasik yang sering digunakan untuk mendiskusikan dan membandingkan berbagai cara untuk menyelesaikan masalah sinkronisasi. Secara singkat, masalah ini terjadi ketika ada beberapa pembaca dan penulis ingin mengakses suatu berkas pada saat bersamaan.

Contohnya: masalah pemesanan tiket pesawat terbang. Ketika seseorang memesan tiket pesawat, dia pertama-tama harus mengecek apakah masih ada tempat yang tersisa. Sekiranya prosedur pemesanan tiket tersebut tidak ditangani secara hati-hati, bisa terjadi masalah ketika dia memesan tiket. Misalkan, sebelum proses pemesanan tiket selesai, ada orang lain yang memesan tiket yang sama dan lebih cepat menyelesaikan proses pemesanan tiket. Dengan demikian, tiket yang seharusnya menjadi miliknya tanpa perlu usaha berlebih, sekarang harus dia perebutkan dengan orang lain yang kebetulan mendaftar pada saat yang bersamaan.

Inti dari permasalahan Readers/Writers adalah adanya beberapa pembaca dan penulis yang ingin mengakses suatu berkas secara simultan. Sebagai syarat bahwa data yang terkandung dalam berkas tersebut tetap konsisten, maka setiap kali berkas tersebut ditulis, maka hanya ada boleh maksimal satu penulis yang menulisnya. Untuk pembaca, hal ini tidak perlu dikhawatirkan sebab membaca suatu berkas tidak mengubah isinya. Dengan kata lain, pada suatu saat diperbolehkan untuk beberapa pembaca untuk membaca berkas tersebut. Akan tetapi, ketika ada yang sedang menulis, tidak boleh ada satupun yang membaca. Ini berarti bahwa thread penulis menjalankan tugasnya secara eksklusif.

Untuk mengatasi masalah ini, ada tiga macam solusi yang akan dibahas. Dasar pembagian solusi ini adalah prioritas. Pertama, solusi dengan pembaca diprioritaskan akan dibahas. Kemudian dilanjutkan dengan solusi dengan penulis yang diprioritaskan. Terakhir, solusi dengan pembaca dan penulis saling bergantian. Pada setiap solusi akan dilihat mengenai tingkat kesuksesan solusi tersebut bila kita lihat dari sudut pandang syarat penyelesaian critical section. Ilustrasi:

        

 Keterangan:

          TL = Thread Penulis

          BC = Thread Pembaca   

-          Kotak dengan sisi putus-putus menandakan thread tersebut sedang menunggu di antrian.

-          Kotak dengan sisi tidak putus-putus menandakan thread tersebut melaksanakan critical sectionnya.

Seperti terlihat di atas, thread-thread pembaca (BC0, BC1, BC2) mendominasi thread-thread penulis (TL0, TL1, TL2) dalam hal akses berkas, sehingga semua thread penulis harus menunggu hingga semua thread pembaca selesai.

·     Dining-Philosophers Problem

Masalah ini pertama kali ditulis dan diselesaikan oleh Djikstra pada tahun 1965. Masalah ini memodelkan masalah enkapsulasi dari ketergantungan mesin dan masalah portabilitas. Dalam masalah Dining Philosophers, diketahui sejumlah (N) filsuf yang hanya memiliki tiga status, berpikir, lapar, dan makan. Semua filsuf berada di sebuah meja makan bundar yang ditata sehingga di depan setiap filsuf ada sebuah piring berisi mie dan di antara dua piring yang bersebelahan terdapat sebuah sumpit.

Pada awalnya, semua filsuf akan berpikir selama waktu yang tidak tentu. Setelah berpikir lama, filsuf akan merasa lapar. Pada saat lapar, ia berusaha untuk mengambil 2 buah sumpit yang ada di kanan dan di kirinya untuk makan. Dia mengambil sumpitnya satu per satu. Begitu ia mendapat sebuah sumpit, ia tidak akan melepaskannya. Jika ia hanya berhasil mengambil kurang dari 2 sumpit, maka ia akan menunggu sampai 2 sumpit diambil. Begitu dia mendapatkan 2 sumpit, maka dia akan makan mienya untuk sementara waktu dan kemudian meletakkan kedua sumpitnya. Kedua sumpit ini kemudian dapat digunakan oleh filsuf-filsuf yang lain. Dia sendiri kemudian kembali berpikir. Tujuan dari masalah ini adalah untuk mencari cara sehingga para filsuf tidak akan pernah mati kelaparan.

Posisi Meja Filsuf dengan N = 4

Salah satu solusi yang mungkin langsung terlihat adalah dengan menggunakan semafor. Setiap sumpit mewakili sebuah semafor. Kemudian, ketika seorang filsuf lapar, maka dia akan mencoba mengambil sumpit di kiri dan di kanannya, atau dengan kata lain dia akan menunggu sampai kedua sumpit tersebut dapat ia gunakan. Setelah selesai makan, sumpit diletakkan kembali dan sinyal diberikan ke semafor sehingga filsuf lain yang membutuhkan dapat menggunakan sumpitnya.

Akan tetapi, solusi ini tidak dapat diterima. Alasannya sangat sederhana, yaitu deadlock dapat terjadi. Contoh kasusnya adalah ketika semua filsuf telah mengambil sumpit di sebelah kirinya, maka tidak ada lagi sumpit yang tersisa di meja. Karena tidak ada sumpit yang tersisa di meja, maka setiap filsuf kekurangan sebuah sumpit. Berhubung setelah berhasil mengambil sebuah sumpit, sumpit tersebut tidak akan diletakkan kembali sampai filsuf yang bersangkutan makan, maka tidak akan ada satu filsuf pun yang akan makan.

Alternatif lain yang cukup menarik disajikan oleh Stallings, antara lain dengan menyuruh setiap filsuf untuk mengambil sumpitnya secara berselang-seling. Filsuf dengan urutan bilangan ganjil pertama kali mengambil sumpit di sebelah kanannya, sementara filsuf dengan urutan bilangan genap pertama kali mengambil sumpit di sebelah kirinya. Alternatif lain yang juga disajikan antara lain: menyediakan sebanyak N sumpit lagi, sehingga lebih higienis di samping dijamin tidak menghasilkan deadlock; mengurangi banyak filsuf yang boleh duduk di meja makan sebanyak 1.