Makalah Dining Philosophers

Prendzz, Kali ini saya akan share tentang tugas Makul Sistem Operasi mengenai Dining Philosophers, seperti apa??langsung ke TKP ya.. :)

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 sesuaididapatkan 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 meungkinkan 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 anda 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 diatas 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.

a.      Gambar Simulasi dari Dining Philosophers

Gambar 1

Keterangan :

1. Terdapat 3 philosopher yang kegiatannya makan dan berfikir.

2. Mereka duduk mengelilingi sebuah meja  dan diatas meja tersebut tersedia semangkuk nasi untuk tiap pholosophers.

3. Tiap diantara mangkok terdapat sebuah sumpit.

Gambar 2 

Keterangan :

-  Jika ketiga philosopher merasa lapar pada daat bersamaan, mak mereka akan mencoba mengambil sumpit di kanan dan kiri mereka pada saat bersamaan

-  Namun mereka hanya akan berhasil mengambil salah satu sumpit karena sumpit yang berada disisi yang lain telah diambil oleh philosopher yang lain.

-  Ketiga philosopher menunggu philosopher lain untuk melepaskan sumpit yang diperlukannya sehingga terjadi saling menunggu dan tidaj ada philosopher yang bisa makan.

b.      Kesimpulan

Algoritma yang dibangun ternyata efektif karena memberikan solusi setelah di implementasikan ke bentuk program di mana  kondisi deadlock  dan  starvation tidak terjadi. Algoritma tersebut tidak melakukan pelanggaran  pada  critical section, Dining philosophers merupakan masalah yang timbul disebabkan kurangnya sumber daya yang dimiliki setiap proses. Untuk mengatasi masalah critical section yang di hadapi dining philosophers  dapat digunakan berbagai solusi software. Namun masalah yang akan timbul dengan solusi  software biasa  adalah solusi software tidak mampu menangani masalah yang lebih berat dari  critical section. Sedangkan solusi software dengan menggunakan   Semaphores mampu menanganinya, terbukti dari software  yang penulis buat  dengan menggunakan  semaphore  dapat mengatasi masalah sinkronisasi  dining philosophers, proses  dining philosophers berjalan dengan benar juga dapat menghidari kondisi deadlock dan  starvation  yang menjadi masalah utama pada sinkronisari dining philosophers.

Itu dulu kawan tugas lain yang aku share buat kalian, untuk tugas lain bisa di lihat di posting lainya. Semoga bermanfaat dan jangan lupa untuk mencari sumber lain sebagai bahan pertimbangan yang lainnya, Tenkiew, seeyaaa :)