Classical Problem of Synchronization

Classical Problem of Synchronization

Sistem operasi merupakan suatu program yang bertindak sebagai interface antara user dengan sistem komputer. Dalam suatu sistem pasti terdapat masalah-masalah yang akan terjadi. Masalah tersebut biasanya terdapat pada proses-prosesnya

proses-proses yang berinteraksi, terdapat beberapa masalah yang harus diselesaikan seperti deadlock dan sinkronisasi. Salah satu masalah klasik yang dapat menggambarkan masalah tersebut adalah Bounded-Buffer Problem, Readers and Writers Problem, Dining-Philosophers Problem.

BOUNDED BUFFER PROBLEM :

Produsen menghasilkan barang dan konsumen yang akan menggunakannya. Ada beberapa batasan yang harus dipenuhi, antara lain : 

-- Barang yang dihasilkan oleh produsen terbatas 

--Barang yang dipakai konsumen terbatas 

--Konsumen hanya boleh menggunakan barang yang dimaksud setelah produsen menghasilkan barang dalam jumlah tertentu 

-- Produsen hanya boleh memproduksi barang jika konsumen sudah kehabisan barang Untuk penyelesaian permasalahan bounded buffer menggunakan semaphore menggunakan variabel umum berikut : semaphore full, empty, mutex; Inisialisasi untuk variable di atas, full = 0, empty = n, mutex = 1. 

 READERS AND WRITER PROBLEM:

Terdapat dua variasi pada masalah ini, yaitu :

          1. seorang reader tidak perlu menuggu reader lain untuk selesai hanya karena ada writer menunggu

          2. Jika ada writer yang sedang menunggu, maka tidak boleh ada reader lain yang bekerja

Jika terdapat writer dalam critical section dan terdapat n reader yang menunggu, maka satu
reader akan antri di wrt dan n-1 reader akan antri di mutex. Jika writer mengeksekusi signal(wrt), maka dapat disimpulkan bahwa eksekusi adalah menunggu reader atau menunggu satu writer. Variabel umum yang digunakan adalah 

semaphore mutex, wrt; 

 Inisialisasi variable di atas adalah mutex = 1, wrt = 1, readcount = 0.
 

DINING-PHILOSHOPERS PROBLEM:

Pada tahun 1965, Djikstra menyelesaikan sebuah masalah sinkronisasi yang beliau sebut dengan dining philisophers problem. Dining philosophers dapat diuraikan sebagai berikut: Lima orang

filosuf duduk mengelilingi sebuah meja bundar. Masing-masing filosof mempunyai sepiring spageti. Spageti-spageti tersebut sangat licin dan membutuhkan dua garpu untuk memakannya. Diantara sepiring spageti terdapat satu garpu.

Kehidupan para filosof terdiri dari dua periode, yaitu makan atau berpikir. Ketika seorang filosof lapar, dia berusaha untuk mendapatkan garpu kiri dan garpu kanan sekaligus. Jika sukses dalam mengambil dua garpu, filosof tersebut makan untuk sementara waktu, kemudian meletakkan kedua garpu dan melanjutkan berpikir. 

Pertanyaan kuncinya adalah, dapatkah anda menulis program untuk masing-masing filosof yang melakukan apa yang harus mereka lakukan dan tidak pernah mengalami kebuntuan. Prosedur take-fork menunggu sampai garpu-garpu yang sesuai didapatkan dan kemudian menggunakannya. Sayangnya dari solusi ini ternyata salah. Seharusnya lima orang filosof mengambil garpu kirinya secara bersamaan. Tidak akan mungkin mereka mengambil garpu kanan mereka, dan akan terjadi deadlock.

Kita dapat memodifikasi program sehingga setelah mengambil garpu kiri, program memeriksa apakah garpu kanan memungkinkan untuk diambil. Jika garpu kanan tidak mungkin diambil, filosof tersebut meletakkan kembali garpu kirinya, menunggu untuk beberapa waktu, kemudia mengulangi proses yang sama. Usulan tersebut juga salah, walau pun dengan alasan yang berbeda.

Dengan sedikit nasib buruk, semua filosof dapat memulai algoritma secara bersamaan, mengambil garpu kiri mereka, melihat garpu kanan mereka yang tidak mungkin untuk diambil, meletakkan kembali garpu kiri mereka, menunggu, mengambil garpu kiri mereka lagi secara bersamaan, dan begitu seterusnya. Situasi seperti ini dimana semua program terus berjalan secara tidak terbatas tetapi tidak ada perubahan/kemajuan yang dihasilkan disebut starvation.

Sekarang kita dapat berpikir "jika filosof dapat saja menunggu sebuah waktu acak sebagai pengganti waktu yang sama setelah tidak dapat mengambil garpu kiri dan kanan, kesempatan bahwa segala sesuatau akan berlanjut dalam kemandegan untuk beberapa jam adalah sangat kecil." Pemikiran seperti itu adalah benar,tapi beberapa aplikasi mengirimkan sebuah solusi yang selalu bekerja dan tidak ada kesalahan tidak seperti hsk nomor acak yang selalu berubah.

Sebelum mulai mengambil garpu, seorang filosof melakukan DOWN di mutex. Setelah menggantikan garpu dia harus melakukan UP di mutex. Dari segi teori, solusi ini cukup memadai. Dari segi praktek, solusi ini tetap memiliki masalah. Hanya ada satu filosof yang dapat makan spageti dalam berbagai kesempatan. Dengan lima buah garpu, seharusnya kita bisa menyaksikan dua orang filosof makan spageti pada saat bersamaan.

Solusi yang diberikan di atas benar dan juga mengizinkan jumlah maksimum kegiatan paralel untuk sebuah jumlah filosf yang berubah-ubah ini menggunakan sebuah array, state, untuk merekam status seorang filosof apakah sedang makan (eating), berpikir (think), atau sedang lapar (hungry) karena sedang berusaha mengambil garpu. Seorang filosof hanya dapat berstatus makan (eating) jika tidak ada tetangganya yang sedang makan juga. Tetangga seorang filosof didefinisikan ole LEFT dan RIGHT.

Dengan kata lain, jika i = 2, maka tetangga kirinya (LEFT) = 1 dan tetangga kanannya (RIGHT) = 3. Program ini menggunakan sebuah array dari semaphore yang lapar (hungry) dapat ditahan jika garpu kiri atau kanannya sedang dipakai tetangganya. Catatan bahwa masing-masing proses menjalankan prosedur filosof sebagai kode utama, tetapi prosedur yang lain seperti take-forks, dan test adalah prosedur biasa dan bukan proses-proses yang terpisah

Meskipun solusi ini menjamin bahwa tidak ada 2 tetangga yang makan bersama sama, namun masih mungkin terjadi deadlock, yaitu jika tiap-tiap filosof lapar dan mengambil supit kiri, maka semua nilai supit = 0, dan juka kemudian tiap-tiap filosof akan mengambil supit kanan, maka akan terjadi deadlock. Ada beberapa cara untuk menghindari deadlock, antara lain :

1. mengijinkan paling banyak 4 orang filosof yang duduk bersama-sama pada satu meja.

2. Mengijinkan seorang filosof mangambil supit hanya jika kedua supit itu ada (dengan catatan, bahwa ia harus mengambil pada critical section)

3. Menggunakan suatu solusi asimetrik, yaitu filosof pada nomor ganjil mengambil supit kanan dulu baru supit kiri. Sedangkan filosof yang duduk di kursi genap mengambil supit kanan dulu baru supit kiri.

PERBEDAAN :

• Bounded-Buffer Problem

Barang yang dihasilkan selalu dibatasi,ketika barang sudah habis maka akan diproduksi lagi

• Readers and Writers Problem

Readers memiliki prioritas lebih tinggi dibanding writer,dan jika writer menunggu maka tidak ada readers yang bekerja (saling bergantian)

• Dining-Philosophers Problem

Masalah  yang timbul disebabkan kurangnya sumber daya yang dimiliki setiap proses.