Sunday, 16 May 2021

Masalah Klasik Sinkronisasi

 

Terdapat 3 Masalah Klasis Sinkronisasi yaitu :

 

1. Bounded-Buffer Problem

2. Readers and writers problem

3. Dining-Philosophers Problem


Bounded-Buffer Problem

Bounded-Buffer (Producer-Consumer) Problem atau Masalah Bounded Buffer 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. Oleh karena itu kita banyak mengulang konsep sinkronisasi dalam membahas masalah bounded buffer ini.

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. Proses yang pertama biasa disebut producer sedangkan yang kedua disebut consumer. Produsen menghasilkan barang dan konsumen yang akan menggunakannya

Masalah Bounded Buffer :

1. Masalah ini digeneralisasikan dalam istilah masalah Konsumen Produsen , di mana kumpulan buffer terbatas digunakan untuk bertukar pesan antara proses produsen dan konsumen.

2. Solusi untuk masalah ini adalah, membuat dua semaphore penghitungan "penuh" dan "kosong" untuk melacak masing-masing jumlah buffer penuh dan kosong saat ini.

3. Dalam hal ini Produsen terutama menghasilkan produk dan konsumen mengkonsumsi produk tersebut, tetapi keduanya dapat menggunakan salah satu wadah setiap saat.

4. 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.

1. Mutex digunakan untuk menjamin hanya boleh satu proses yang berjalan mengakses buffer pada suatu waktu, awalnya dinisialisasi sebesar satu (1).

2. Full digunakan untuk menghitung jumlah buffer yang berisi, yang pada awalnya diinisialisasi sebesar nol (0).

3. 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 


Dalam masalah sinkronisasi ini terdapat dua macam proses, yaitu pembaca (reader) dan penulis (writer). Permasalahan ini muncul saat ada beberapa pembaca dan penulis yang berbagi data yang sama atau berbagi sumber daya penyimpanan yang sama. Data yang diakses dapat berupa buffer, file, ataupun objek dari suatu program.  Dalam permasalahan ini, di setiap proses yang berjalan, penulis yang melakukan kegiatan menulis hanya diperbolehkan satu penulis saja. Jika sedang ada penulis yang melakukan proses menulis, maka tidak boleh ada proses membaca. Dalam permasalahan ini diperbolehkan ada lebih dari satu pembaca yang mengakses berkas, namun jika ada penulis yang sedang mengakses berkas maka tidak boleh ada siapapun (pembaca dan penulis lain) yang mengakses berkas tersebut.

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.

Untuk mengatasi permasalahan ini, terdapat 3 solusi yang dapat dilakukan :

1. Pertama, solusi dengan memprioritaskan pembaca. Solusi ini tepat digunakan jika tujuan yang ingin dicapai adalah memperoleh throughput semaksimal mungkin.

2. Kedua, solusi dengan memprioritaskan penulis. Pada solusi ini, jika tidak ada yang mengaksess berkas maka penulis akan mengakses berkas dan pembaca akan dibiiarkan mengantri sampai semua penulis  menyelesaikan tugasnya.

3. Solusi yang ketiga adalah pembaca dan penulis memperoleh prioritas yang sama secara bergantian. Pada solusi ini, penulis dan pembaca diberi giliran yang adil dalam hal pengaksesan berkas. Jika tidak ada thread pembaca yang sedang mengakses berkas, maka penulis dapat mengaksesnya. Dan jika selesai maka akan memberikan giliran pada pembaca untuk mengakses berkas.


 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) filusuf yang hanya memiliki tiga status, berpikir, lapar, dan makan. Semua filusuf berada di sebuah meja makan bundar yang ditata sehingga di depan setiap filusuf ada sebuah piring berisi mie dan di antara dua piring yang bersebelahan terdapat sebuah sumpit.

Solusi Dining – Philosophers Problem ada dua, yakni : 

1. Solusi Waiter

Solusi Waiter : solusi sederhana ini dilakukan dengan mengadakan seorang waiter yang senantiasa mengawasi penggunaan sumpit di meja makan. Ketika empat buah (dua pasang) sumpit sedang dipakai,orang berikutnya yang ingin memakai sumpit harus meminta izin kepada sang waiter, yang hanya dapat diberi ketika salah satu sumpit telah selesai terpakai.

2. Solusi Hierarki Resource

Solusi Hirarki Resource: resources (sumpit) di meja makan telah diberi susunan hirarki. Setiap permintaan orang terhadap sebuah sumpit harus dilakukan pada susunan tertentu, dan dikembalikan pada susunan sebaliknya. Dalam hal ini, setiap orang dapat mengambil sumpit dimanapun diatas meja. Misalkan setiap sumpit diberi nomor sebagai tingkat hirarki dari 1 sampai 5, seseorang hanya dapat mengambil sumpit dengan nomor yang paling rendah, kemudian mengambil sumpit yang setingkat lebih tinggi. Ketika ia hendak mengembalikannya, orang itu harus meletakkan sumpit dengan nomor yang lebih tinggi terlebih dahulu, lalu yang rendah.


0 comments :

Post a Comment

Subscribe Admin

Annismus

 
Design by Free WordPress Themes | Bloggerized by Rz - Premium Blogger Themes | coupon codes