Masalah Klasik Sinkronisasi

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 Bounded Buffer :

• Masalah ini digeneralisasikan dalam istilah masalah Konsumen Produsen , di mana kumpulan buffer terbatas digunakan untuk bertukar pesan antara proses produsen dan konsumen.
• Solusi untuk masalah ini adalah, membuat dua semaphore penghitungan "penuh" dan "kosong" untuk melacak masing-masing jumlah buffer penuh dan kosong saat ini.
• Dalam hal ini Produsen terutama menghasilkan produk dan konsumen mengkonsumsi produk tersebut, tetapi keduanya dapat menggunakan salah satu wadah setiap saat.
• Kompleksitas utama dari masalah ini adalah kita harus menjaga jumlah container kosong dan penuh yang tersedia.

Solusi untuk produsen adalah baik pergi tidur atau membuang data jika buffer penuh. Ketika konsumen menghapus item dari buffer, maka sistem akan memberitahu produser, yang mulai mengisi buffer lagi. Dengan cara yang sama, ketika produsen menempatkan data ke dalam buffer, maka konsumen lebih baik tidur sambail menunggu buffer terisi penuh.

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.

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 and Writers :

• Dalam masalah ini ada beberapa proses (disebut reader ) yang hanya membaca data yang dibagikan, dan tidak pernah mengubahnya, dan ada proses lain (disebut penulis ) yang dapat mengubah data sebagai tambahan untuk membaca, atau sebagai gantinya membacanya.
• Ada berbagai jenis masalah pembaca-penulis, kebanyakan berpusat pada prioritas relatif pembaca dan penulis.
• Kompleksitas utama dengan masalah ini terjadi karena mengizinkan lebih dari satu pembaca untuk mengakses data pada waktu yang sama.

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.

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.

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.

Link Presentadi di Youtube :

https://youtu.be/4_tRqziZyXo

Daftar Pustaka : 

https://www.studytonight.com/operating-system/classical-synchronization-problems

https://www.studytonight.com/operating-system/bounded-buffer

https://www.studytonight.com/operating-system/dining-philosophers-problem

https://www.studytonight.com/operating-system/readers-writer-problem

http://www.it.uu.se/education/course/homepage/os/vt18/module-4/bounded-buffer/#:~:text=A%20bounded%20buffer%20lets%20multiple,if%20the%20buffer%20is%20empty.

http://riskinesmeidita.blogspot.com/2017/05/perbedaan-bounded-buffer-problem.html#:~:text=Bounded%20Buffer%20Problem%20adalah%20suatu,untuk%20mengakses%20data%20yang%20sama.

http://ftp.gunadarma.ac.id/linux/docs/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-1/ch25.html