Tugas Sistem Operasi

" Makalah Dining Philosophers Problem "

BAB I

PENDAHULUAN

A.    Latar Belakang

Sistem operasi merupakan suatu program yang bertindak sebagai interface antara user dan sistem kompueter. Sistem operasi ini harus mampu melakukan pengontrolan penggunaan resource. Dalam suatu proses rancangan sistem operasi terdapat landasan umum yang disebut Kongkurensi. Proses – proses tersebut disebut kongkuren jika proses – proses berada pada saat yang sama. Keadaan tersebut disebut dengan multitasking dari sistem operasi.  Proses – proses kongkuren dapat sepenuhnya tak bergantung dengan yang lainnya tapi dapat juga saling berinteraksi. Proses yang berinteraksi memerlukan singkronisasi agar terkendali dengan baik. Namun ada kalanya pada proses kongkuren yang berinteraksi , terdapat beberapa masalah yang harus diselesaikan seperti deadlock dan singkronisasi. Salah satu masalah  klasik yang dapat menggambarkan hal tersebut adalah dining Philosophers Problem.

Dining Philosopher Problem dapat diilustrasikan sebagai berikut, terdapat lima orang filosof yang akan makan. Dimeja makan disediakan lima buah sumpit. Jika filosof lapar maka ia akan makan dan mengambil 2 buah sumpit, yaitu di tangan kanan dan kirinya. Namun adakalanya hanya diambil satu sumpit saja. Jika ada filosof yang mengambil dua sumpit ,maka akan ada filosof yang akan menunggu sampai sumpit tersebut diletakkan kembali. Di dalam masalah ini ada kemungkinan terjaid dadlock ( suatu kondisi dimana dua proses  atau lebih tidak dapat meneruskan eksekusinya).

B.     Rumusan Masalah

Berdasarkan latar belakang dari makalah ini, maka dapat ditentukan rumusan masalahnya adalah sebagai berikut :

1.      Apa maksud dari Dining Philosophers Problem?

2.      Bagaimana Cara menyelasaikan masalah Dining Philosophers?

C.     Tujuan

Adapun tujuan dari pembuatan makalah ini yaitu :

1.      Mahasiswa mengetahui aap itu Dining Philosophers Problem

2.      Mahasiswa mengetahui cara menyelesaikan masalah Dining Philosophers

D.    Sumber

Adapun sumber pembuatan makalah ini adalah dari internet.

  

BAB II

PEMBAHASAN

Dining Philosopher Problem

Dalam Literatur sistem operasi terdapat berbagai permasalahan menarik yang telah didiskusikan dan dianalisis. Berikut adalah  contoh permasalahan klasik dibidang komunikasi antar-proses yang harus dapat diselesaikan oleh sebuah sistem operasi.salah satu contoh permodelan proses yang bersaing untuk mendapatkan akses ekslusif ke sejumlah resource yang terbatas, seperti alat input/output. Pada tahun 1965, Djikstra menyelesaikan sebuah masalah sinkronisasi yang beliau sebut dengan dining philisophers problem. Dining Philosophers Problem merupakan salah satu masalah klasik dalam sinkronisasi.

Dining Philosohers Problem dapat diilustrasikan sebagai berikut, terdapat lima orang filsuf yang sedang duduk mengelilingi sebuah meja. Terdapat lima mangkuk mie di depan masing-masing filsuf dan satu sumpit di antara masing-masing filsuf. Para filsuf menghabiskan waktu dengan berpikir (ketika kenyang) dan makan (ketika lapar). Ketika lapar, filsuf akan mengambil dua buah sumpit (di tangan kiri dan tangan kanan) dan makan. Namun adakalanya, hanya diambil satu sumpit saja. Jika ada filsuf yang mengambil dua buah sumpit, maka dua filsuf di samping filsuf yang sedang makan harus menunggu sampai sumpit ditaruh kembali. Hal ini dapat diimplementasikan dengan wait dan signal.

   Lima filsof dalam satu meja makan

Kita dapat memodifikasi program sehingga setelah mengambil sumpit kiri, program memeriksa apakah sumpit kanan memungkinkan untuk diambil. Jika sumpit kanan tidak mungkin diambil, filosof tersebut meletakkan kembali sumpit 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 sumpit kiri mereka, melihat sumpit kanan mereka yang tidak mungkin untuk diambil, meletakkan kembali sumpit kiri mereka, menunggu, mengambil sumpit 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.

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

ü         - Mengijinkan paling banyak 4 orang filsuf yang duduk bersama-sama pada satu meja.

ü          -   Mengijinkan seorang filsuf mengambil sumpit hanya jika kedua sumpit itu ada.

ü         -    Menggunakan suatu solusi asimetrik, yaitu filsuf pada nomor ganjil mengambil sumpit kiri dulu baru sumpit   kanan. Sedangkan filsuf yang duduk di kursi genap mengambil sumpit kanan dulu baru sumpit kiri.

Proses disebut deadlock jika proses menunggu satu kejadian tertentu yang tak akan pernah terjadi. Sekumpulan proses berkondisi deadlock bila setiap proses yang ada di kumpulan itu menunggu suatu kejadian yang hanya dapat dilakukan proses lain yang juga berada di kumpulan itu. Proses menunggu kejadian yang tidak akan pernah terjadi. Deadlock terjadi ketika proses-proses mengakses secara ekslusif sumber daya. Semua deadlock yang terjadi melibatkan persaingan memperoleh sumber daya ekslusif oleh dua proses atau lebih.

Kondisi deadlock dalam simulasi dining philosophers problem terjadi apabila pada satu saat, semua filsuf merasa lapar secara bersamaan dan semua filsuf mengambil sumpit di tangan kiri. Pada saat filsuf akan mengambil sumpit di tangan kanan, maka terjadilah kondisi deadlock, karena semua filsuf akan saling menunggu sumpit di sebelah kanannya (kondisi yang tidak akan pernah terjadi).

Proses dikatakan sebagai mengalami starvation bila proses-proses itu menunggu alokasi sumber daya sampai tak berhingga, sementara proses-proses lain dapat memperoleh alokasi sumber daya. Starvation disebabkan bias pada kebijaksanaan atau strategi alokasi sumber daya. Kondisi ini harus dihindari karena tidak adil tetapi dikehendaki penghindaran dilakukan seefisien mungkin.

Sebelum mulai mengambil sumpit, seorang filosof melakukan DOWN di mutex. Setelah menggantikan sumpit dia harus melakukan UP di mutex. Dari segi teori, solusi ini cukup memadai. Tapi dari segi praktek, solusi ini tetap memiliki masalah. Hanya ada satu filosof yang dapat makan mie dalam berbagai kesempatan. Dengan lima buah sumpit, seharusnya kita bisa menyaksikan dua orang filosof makan mie 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 sumpit. 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 sumpit 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.

Salah satu solusi yang mungkin langsung terlihat adalah dengan menggunakan semafor. Setiap sumpit mewakili sebuah semafor. Kemudian, ketika seorang filusuf 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 filusuf lain yang membutuhkan dapat menggunakan sumpitnya.

Semafor adalah sebuah struktur data komputer yang digunakan untuk sinkronisasi proses, yaitu untuk memecahkan masalah di mana lebih dari satu proses atau thread dijalankan secara bersamaan dan harus diatur urutan kerjanya. Semafor dicetuskan oleh Edsger Dijkstra dan pertama digunakan dalam sistem operasi THE.

Nilai semafor diinisialisasi dengan jumlah resource yang dikendalikannya. Dalam kasus khusus di mana ada satu shared resource, semafornya disebut "semafor biner". Semafor adalah solusi klasik dari dining philosophers problem, walaupun tidak mencegah deadlock.

           

BAB III

PENUTUP

A.   Kesimpulan 

            Dining Philosophers Problem merupakan salah satu masalah klasik dalam sinkronisasi. Dining Philosohers Problem dapat diilustrasikan sebagai berikut, terdapat lima orang filsuf yang sedang duduk mengelilingi sebuah meja. Terdapat lima mangkuk mie di depan masing-masing filsuf dan satu sumpit di antara masing-masing filsuf. Para filsuf menghabiskan waktu dengan berpikir (ketika kenyang) dan makan (ketika lapar). Ketika lapar, filsuf akan mengambil dua buah sumpit (di tangan kiri dan tangan kanan) dan makan. Namun adakalanya, hanya diambil satu sumpit saja. Jika ada filsuf yang mengambil dua buah sumpit, maka dua filsuf di samping filsuf yang sedang makan harus menunggu sampai sumpit ditaruh kembali. Hal ini dapat diimplementasikan dengan wait dan signal.

            Semafor adalah sebuah struktur data komputer yang digunakan untuk sinkronisasi proses, yaitu untuk memecahkan masalah di mana lebih dari satu proses atau thread dijalankan secara bersamaan dan harus diatur urutan kerjanya. Semafor adalah solusi klasik dari dining philosophers problem, walaupun tidak mencegah deadlock.