Masalah Klasik Sinkronisasi

 Pada posting kali ini, saya akan membahas mengenai masalah-masalah klasik terkait dengan sinkronisasi yaitu Bounded Buffer Problem, Readers and Writers Problem, dan Dining Philosophers Problem.

Readers/Writers dan Bounded Buffer Problem

Misalnya suatu program memiliki tugas untuk menerima memproduksi (producing) suatu nilai dan melakukan konsumsi/proses (consuming) terhadap suatu nilai yang sudah diproduksi. Proses produksi dan konsumsi dilakukan secara terus menerus dan paralel. Untuk menampung data hasil produksi maka dibuat suatu array yang disebut buffer dengan ukuran tertentu. Dalam kasus ini kita buat ukurannya 5. Untuk mengetahui berapa banyak nilai yang sudah terisi maka dibuat variabel counter. Berikut ini adalah contoh kode pada bahasa C#.

Pertama ada fungsi Produce. Fungsi ini tugasnya adalah untuk membuat angka acak lalu menambahkan angka acak tersebut ke buffer. Setelah itu menaikkan nilai counter. Pada fungsi Consume tugasnya adalah mengambil nilai terakhir yang ada pada buffer lalu menurunkan nilai counter.

Masalahnya adalah ukuran buffer terbatas sehingga jika tidak ada validasi ukuran buffer maka akan terjadi error yang menyebabkan program crash. Solusinya adalah dengan membuat pengecekan pada fungsi Produce jika buffer sedang penuh (baris 16) maka nilai yang barusan dibuat harus dibuang/diabaikan (baris 18). Untuk beberapa kasus ini tidak menjadi masalah namun untuk kasus seperti pemrosesan data transaksi bank maka tidak boleh ada nilai yang diabaikan dan semuanya harus diproses/dikonsumsi.

Masalah kedua yang muncul adalah terjadinya race condition terhadap nilai counter. Karena fungsi Produce dan Consume berjalan secara paralel maka ada kemungkinan nilai counter diakses dan diubah secara bersamaan. Misalnya ketika fungsi Consume sedang membaca nilai terakhir dan pada waktu yang bersamaan fungsi Produce menaikkan nilai counter maka setelah Consume selesai dan menurunkan nilai counter yang baru saja dinaikkan maka data yang barusan dimasukkan oleh Produce tidak akan dianggap oleh Consume pada iterasi berikutnya alias hilang. Untuk mengatasinya kita bisa menggunakan metode mutex yang intinya hanya ada satu proses/thread yang bisa membaca dan mengubah isi variabel counter seperti pada contoh di bawah ini.

Dalam C# untuk menggunakan mutex bisa dengan menambahkan blok lock() seperti pada baris 14 dan 36. Dengan menambahkan kedua blok ini maka masalah race condition (Readers/Writers Problem) sudah teratasi.

Untuk masalah data yang diabaikan/terbuang, maka kita bisa menggunakan Semaphore. Logikanya adalah jika buffer sudah penuh, maka Produce harus menunggu hingga buffer tersebut kosong atau setidaknya nilainya sudah berukurang sehingga data yang diproduksi bisa dimasukkan ke dalam buffer. Cara kerja Semaphore adalah pertama diinisialisasi nilai sekarang dan nilai maksimal. Pada Semaphore ada 2 fungsi yaitu WaitOne dan Release. Jika nilai sekarang masih 0, maka fungsi WaitOne akan membuat thread yang memanggilnya berhenti sampai nilai sekarang lebih dari 0. Fungsi Release lah yang akan menaikkan nilai semaphore sekarang sebesar 1. Perlu diperhatikan bahwa nilai sekarang tidak bisa melebihi nilai maksimal semaphore dan jika dipaksa maka akan terjadi error.

Dalam kasus ini implementasinya adalah dengan membuat 2 semaphore yaitu full dan empty. Kedua semaphore memiliki nilai maksimal sebesar 5 (sebesar ukuran buffer). Nilai sekarang full adalah 0 sementara nilai sekarang empty adalah 5 (baris 9 dan 10). Jadi ketika fungsi Produce dipanggil, maka Produce akan mengecek apabila nilai semaphore empty sekarang di atas 0, maka isikan nilai ke buffer dan naikkan counter serta turunkan nilai empty. Jika nilai empty sudah 0, maka tunggu hingga nilai empty menjadi lebih dari 0 (baris 18). Setelah memasukkan nilai maka naikkan nilai full (baris 27).

Pada fungsi Consume, terjadi hal yang sama pada semaphore full dan empty hanya saja dibalik. Jika pada Produce semaphore yang dicek lalu diturunkan adalah empty, maka pada Consume semaphore full yang dicek dan diturunkan (baris 35). Sementara itu nilai empty lah yang dinaikkan (baris 44). Dengan adanya kedua semaphore ini maka validasi nilai counter pada fungsi Produce dan Consume dapat dihilangkan karena fungsi Produce akan berhenti ketika buffer penuh dan akan resume kembali ketika isi buffer berkurang. Sebaliknya fungsi Consume akan berhenti jika buffer kosong serta resume kembali ketika isi buffer bertambah. 

Contoh kasus nyata pada masalah ini yaitu pada web server yang memproses request dari browser secara paralel tanpa ada satu request yang dibuang/diabaikan.

Dining Philosopher Problem

Masalah ini merupakan contoh dari deadlock yang terjadi ketika resource sistem digunakan secara bersama-sama oleh beberapa proses secara paralel. Masalah ini dianalogikan dengan 3 filsuf yang ingin makan di restoran. Satu garpu disediakan kepada setiap filsuf sehingga ada 3 garpu yang tersedia. Untuk memakan makanan yang ada, satu filsuf perlu 2 garpu. Filsuf pertama menggunakan garpunya dan meminta garpu filsuf 2. Pada saat yang bersamaan, garpu 2 sudah digunakan oleh filsuf 2 dan filsuf 2 juga meminta garpu filsuf 3. Filsuf 3 pun juga sudah menggunakan garpu 3 serta meminta garpu filsuf 1 sementara garpu 1 sudah digunakan oleh filsuf 1. Karena tidak ada filsuf yang dapat menggunakan resource yang dibutuhkan maka terjadi deadlock karena setiap filsuf menunggu garpu yang sedang digunakan oleh filsuf lain selesai digunakan padahal semua filsuf juga sedang menunggu garpu berikutnya selesai digunakan. Berikut ini merupakan contoh kode dalam bahasa C# yang mendemonstrasikan masalah ini.

Pada kode di atas terdapat fungsi TakeFork. Fungsi ini pertama-tama mengecek apabila garpu yang diminta sedang digunakan atau tidak (0 menyatakan digunakan, 1 menyatakan tersedia). Bila sedang digunakan maka tunggu hingga selesai digunakan. Blok lock() digunakan di sini untuk mencegah race condition. Fungsi ReturnFork berfungsi untuk mengembalikan state garpu ke awal (tersedia alias 1).

Setiap filsuf pertama-tama melakukan request garpu pertama dan kedua pada baris 31 dan 32 (garpu ke N dan N+1). Setelah kedua garpu didapatkan, filsuf lalu melakukan 'proses' yang diibaratkan pada baris ke 34. Setelah itu kedua garpu dikembalikan pada baris 38 dan 39. Ada 3 thread filsuf yang dijalankan. Jika program di atas dijalankan maka setelah beberapa saat deadlock akan terjadi dan program akan hang.

Untuk mengatasinya, kita akan mengubah fungsi TakeFork untuk mengambil kedua id garpu sekaligus dan melakukan pengecekan apabila salah satu dari kedua garpu tersebut masih ada yang dipakai maka tunggu hingga kedua garpu selesai dipakai (baris 14).

Jalankan program di atas maka program akan berjalan selamanya. Contoh nyata dari kasus ini adalah penggunaan resource sistem seperti network, disk, port, dan sebagainya yang hanya bisa diakses oleh satu program dalam satu waktu namun ada banyak program yang perlu menggunakannya sehingga diperlukan semacam scheduling sehingga tidak terjadi deadlock.

Demikian posting kali ini tentang masalah klasik sinkronisasi. Semoga dapat dipahami. Sekian.

Reference: 

https://www.youtube.com/watch?v=l6zkaJFjUbM

https://www.youtube.com/watch?v=rCiQc3ife90