Dining Philosophers

Paper Dining Philosophers

Oleh : Yusuf Machsar

NRP : 100411100026

ABSTRAK

Pada awalnya kebanyakan orang memakai konsep-konsep sinkronisasi yang sederhana yang didukung oleh hardware, seperti pemakaian interrupt atau pemakaian rutin-rutin yang mungkin telah diimplementasi oleh hardware. Pada tahun 1967, Djikstra mengajukan suatu konsep pememakai suatu variable integer untuk menghitung banyaknya proses yang sedang aktif atau yang sedang tidak aktif. Tipe dari variable ini dinamakan semaphore. kebanyakkan semaphore juga digunakan untuk sinkronisasi dalam komunikasi antar device perangkat.Pada jurnal ini semaphore digunakan untuk menyelesaikan masalah singkronisasi dining philosophers.Dining philosophers tu sendiri adalah situasi dimana 5 philosopher duduk di meja makan untuk makan spageti, setiap philosopher diberi satu piring spageti dan diberi satu sumpit, untuk memakan spageti tersebut dibutuhkan dua sumpit untuk menyelesaikan masalah ini maka variable semaphore ini diterapkan pada setiap sumpit agar sumpit bisa di share ke-philosopher yang lainya.

PENDAHULUAN

Sistem operasi merupakan suatu program yang bertindak sebagai interface antara user dan sistem komputer. Sistem operasi ini harus mampu melakukan pengontrolan penggunaan resource. Dalam proses perancangan sistem operasi, terdapat suatu landasan umum yang disebut dengan kongkurensi. Proses-proses disebut kongkuren jika proses-proses (lebih dari satu proses) berada pada saat yang sama. Keadaan ini disebut dengan multitasking dari sistem operasi. Proses-proses kongkuren dapat sepenuhnya tak bergantung dengan lainnya tapi dapat juga saling berinteraksi. Proses-proses yang berinteraksi memerlukan sinkronisasi agar terkendali dengan baik. Namun, pada proses-proses kongkuren yang berinteraksi, terdapat beberapa masalah yang harus diselesaikan seperti deadlock dan sinkronisasi. Salah satu masalah klasik yang dapat menggambarkan masalah tersebut adalah Dining Philosophers Problem.

Dining Philosophers Problem dapat diilustrasikan sebagai berikut, terdapat lima orang filsuf yang akan makan. Di meja disediakan lima buah sumpit. Jika filsuf lapar betul, maka ia akan mengambil dua buah sumpit, yaitu di tangan kanan dan kiri. Namun adakalanya hanya diambil sumpit satu saja. Jika ada filsuf yang mengambil dua buah sumpit, maka ada filsuf yang harus menunggu sampai sumpit tersebut ditaruh kembali. Di dalam problema ini ada kemungkinan terjadi deadlock, yaitu suatu kondisi dimana dua proses atau lebih tidak dapat meneruskan eksekusinya.

Penulis bermaksud untuk menyelesaikan masalah tersebut, dengan cara merancang suatu perangkat lunak yang dapat mensimulasikan proses kerja dari problem tersebut sekaligus mensimulasikan pencegahan masalah deadlock tersebut.

PEMBAHASAN

1.1  Dining Philosophers 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.

            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:

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

b.      Mengijinkan seorang filsuf mengambil sumpit hanya jika kedua sumpit itu ada.

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

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.

            Dalam proses perancangan perangkat lunak simulasi ini, penulis mengambil beberapa asumsi, yaitu:

1. Hanya terdapat 5 (lima) orang filsuf dalam proses simulasi.
2. Masing-masing filsuf memiliki kondisi sebagai berikut:
1. Kenyang.

Filsuf akan berada dalam kondisi kenyang sesaat setelah makan.

2. Lapar.

Beberapa saat setelah makan, filsuf akan merasa lapar.

3. Mati.

Beberapa saat setelah merasa lapar dan apabila filsuf belum juga mendapatkan sumpit, maka filsuf akan mati.

3. Aksi yang dapat dilakukan oleh masing-masing filsuf, yaitu:
1. Berpikir.

Filsuf akan berpikir apabila filsuf berada dalam kondisi kenyang.

2. Cari Sumpit.

Filsuf akan mencari dan mengambil sumpit di kedua tangannya apabila filsuf berada dalam kondisi lapar.

3. Makan

Apabila filsuf mendapatkan dua sumpit di kedua tangannya, maka filsuf akan makan hingga kenyang. Setelah kenyang, filsuf kembali berpikir.

4. Di dalam perangkat lunak, kondisi filsuf di atas dirancang penulis secara matematis menjadi waktu-A dan waktu-B.
1. Waktu-A, yaitu waktu yang diperlukan untuk mengubah kondisi filsuf dari kenyang menjadi lapar (dalam sekon).
2. Waktu-B, yaitu waktu yang diperlukan untuk mengubah kondisi filsuf dari lapar menjadi mati (dalam sekon).
3. Masa Hidup, yaitu masa hidup filsuf pada saat itu (dalam sekon). Maksimum masa hidup adalah sebesar nilai waktu-A + waktu-B. Masa hidup filsuf akan bertambah ketika filsuf sedang makan dan akan senantiasa berkurang di luar aksi itu.

Ketiga komponen ini menjadi ukuran matematis kondisi filsuf di dalam perangkat lunak. Misalnya, seorang filsuf memiliki waktu-A = 10 sekon, waktu-B = 8 sekon dan masa hidup = 12 sekon. Karena masa hidup filsuf adalah 12 sekon atau lebih besar 4 sekon daripada waktu-B, maka dapat dihitung bahwa 4 sekon kemudian, filsuf akan mulai merasa lapar dan mulai mencari sumpit. Bila filsuf mendapatkan dua sumpit di kedua tangannya, maka filsuf akan mulai memakan mie yang ada di depannya. Ketika sedang makan, masa hidup filsuf akan bertambah kembali. Filsuf tidak akan berhenti makan hingga filsuf berada dalam kondisi kenyang atau masa hidupnya mencapai nilai maksimum yaitu 18 sekon (waktu-A + waktu-B). Setelah itu, filsuf akan berpikir dalam 10 sekon berikutnya, sebelum merasa lapar dan mencari sumpit lagi. Apabila filsuf merasa lapar dan tidak mendapatkan sumpit dalam waktu 8 sekon (waktu-B), maka masa hidup filsuf akan menjadi nol dan filsuf akan mati. Untuk mendapatkan sumpit, filsuf harus menunggu apabila sumpit sedang dipakai oleh filsuf di sampingnya. Dalam kondisi itu, masa hidup filsuf akan terus berkurang.

5. Untuk menghindari kondisi deadlock, penulis menyediakan 3 cara yang dapat dipilih, yaitu:
1. Solusi-A, yaitu mengizinkan paling banyak 4 orang filsuf yang duduk bersama-sama pada satu meja.
2. Solusi-B, yaitu mengizinkan seorang filsuf mengambil sumpit hanya jika kedua sumpit itu ada.
3. Solusi-C, yaitu filsuf pada nomor ganjil mengambil sumpit kiri dulu baru sumpit kanan, sedangkan filsuf pada nomor genap mengambil sumpit kanan dulu baru sumpit kiri. Solusi ini disebut solusi asimetrik.

Untuk dapat lebih memahami proses yang terjadi, perhatikan contoh illustrasi berikut ini. Misalkan properti 5 orang filsuf dalam simulasi adalah sebagai berikut:

Tabel 3.1 Tabel Properti Filsuf

	Waktu-A (sekon)	Waktu-B (sekon)	Kondisi Awal (sekon)
Filsuf-1	7	10	15
Filsuf-2	5	4	4
Filsuf-3	6	11	14
Filsuf-4	5	13	11
Filsuf-5	6	12	18

Dari tabel dapat diketahui kondisi masing-masing filsuf, yaitu filsuf-1 berada dalam kondisi kenyang karena kondisi awal 15 sekon berada di atas waktu-B yang hanya 10 sekon (filsuf-1 akan merasa lapar dan mencari sumpit 5 sekon kemudian). Filsuf-2 berada dalam kondisi lapar karena kondisi awal 4 sekon = waktu-B, filsuf-3 berada dalam kondisi kenyang, filsuf-4 berada dalam kondisi lapar dan filsuf-5 berada dalam kondisi kenyang. Kondisi awal problema dining philosophers dapat digambarkan dengan bagan illustrasi sebagai berikut:

Gambar 3.1 Bagan illustrasi kondisi awal simulasi

Proses simulasi adalah sebagai berikut:

Pada saat t = 1 sekon, filsuf-1, filsuf-3 dan filsuf-5 kenyang dan sedang berpikir, sedangkan filsuf-2 dan filsuf-4 lapar dan mendapatkan sumpit di tangan kiri. Pada saat t = 2 sekon, filsuf-2 dan filsuf-4 mendapatkan 2 sumpit dan mulai makan, sedangkan filsuf-1, filsuf-3 dan filsuf-5 masih kenyang dan sedang berpikir. Pada saat t = 3 sekon, filsuf-3 merasa lapar (karena masa hidup filsuf-3 saat ini = waktu-B yaitu 11 sekon) dan mulai mencari sumpit, tetapi tidak mendapatkan sumpit karena sumpit di sebelah kiri digunakan oleh filsuf-4 dan sumpit di sebelah kanan digunakan oleh filsuf-2. Bagan illustrasinya adalah sebagai berikut:

Gambar 3.2 Bagan illustrasi kondisi simulasi saat t=3 sekon

Pada saat t = 5 sekon, filsuf-1 merasa lapar (karena masa hidup filsuf-1 saat ini = waktu-B yaitu 10 sekon) dan mencari sumpit. Filsuf-1 mendapatkan sumpit di tangan kanan. Pada saat t = 6 sekon, filsuf-5 merasa lapar (karena masa hidup filsuf-5 saat ini = waktu-B yaitu 12 sekon) dan mencari sumpit. Filsuf-5 tidak mendapatkan sumpit. Pada saat t = 9 sekon, filsuf-2 kenyang (karena masa hidupnya sudah mencapai nilai maksimum, yaitu 9 sekon = waktu-A + waktu-B) dan mulai berpikir. Filsuf-3 mendapatkan sumpit di tangan kanan. Pada saat t = 10 sekon, filsuf-1 mendapatkan 2 sumpit dan mulai makan. Pada saat t = 11 sekon, filsuf-4 kenyang dan mulai berpikir. Filsuf-5 mendapatkan sumpit di tangan kanan. Pada saat t = 12 sekon, filsuf-3 mendapatkan 2 sumpit dan mulai makan. Bagan illustrasinya adalah sebagai berikut:

Gambar 3.3 Bagan illustrasi kondisi simulasi saat t=12 sekon

Proses simulasi akan berlanjut sesuai dengan prosedur. Simulasi hanya akan berhenti apabila terjadi kondisi deadlock. 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). Untuk kasus deadlock, perhatikan kondisi berikut:

Tabel 3.2 Tabel Properti Filsuf untuk Kasus Deadlock

	Waktu-A (sekon)	Waktu-B (sekon)	Kondisi Awal (sekon)
Filsuf-1	17	12	27
Filsuf-2	5	3	2
Filsuf-3	15	10	25
Filsuf-4	6	5	5
Filsuf-5	20	5	20

Bagan illustrasi kondisi awal adalah sebagai berikut:

Gambar 3.4 Bagan illustrasi kondisi awal (kasus deadlock)

Pada saat t = 1 sekon, filsuf-2 dan filsuf-4 lapar dan mendapatkan sumpit di tangan kiri, sedangkan filsuf-1, filsuf-3 dan filsuf-5 kenyang dan sedang berpikir. Pada saat t = 2 sekon, filsuf-2 dan filsuf-4 mendapat 2 sumpit dan mulai makan. Pada saat t = 10 sekon, filsuf-2 dan filsuf-4 kenyang dan mulai berpikir. Pada saat t = 15 sekon, semua filsuf secara bersamaan lapar dan mengambil sumpit di tangan kiri. Pada saat ini, telah terjadi kondisi deadlock, karena semua filsuf yang sedang mengenggam sumpit di tangan kiri menunggu sumpit di sebelah kanan. Semua filsuf akan saling menunggu. Bagan illustrasi kondisi deadlock adalah sebagai berikut:

Gambar 3.5 Bagan illustrasi kondisi deadlock

Dengan input properti filsuf dan kondisi awal yang sama, kondisi deadlock yang terjadi dapat dihindari dengan memilih satu dari tiga solusi berikut:

1. Solusi-A, yaitu mengizinkan paling banyak 4 orang filsuf yang duduk bersama-sama pada satu meja. Tidak akan terjadi kondisi deadlock apabila terdapat kurang dari 4 orang filsuf yang duduk bersama-sama mengelilingi meja dengan 5 tempat duduk (satu filsuf dianggap mati).
2. Solusi-B, yaitu mengizinkan seorang filsuf mengambil sumpit hanya jika kedua sumpit itu ada. Apabila semua filsuf lapar secara bersamaan, maka hanya 2 orang filsuf yang dapat makan, karena filsuf mengambil 2 sumpit pada saat yang bersamaan.
3. Solusi-C, yaitu solusi asimetrik. Filsuf pada nomor ganjil mengambil sumpit kiri dulu baru sumpit kanan, sedangkan filsuf pada nomor genap mengambil sumpit kanan dulu baru sumpit kiri. Apabila semua filsuf lapar secara bersamaan, cara pengambilan dengan solusi asimetrik akan mencegah semua filsuf mengambil sumpit kiri secara bersamaan, sehingga kondisi deadlock dapat dihindari.

DAFTAR PUSTAKA

1.         Bruce Schneier, Applied Crytography, Second Edition, 1996.

2.         Ir. Jusuf Kurniawan, M.T., Kriptografi, Keamanan Internet dan Jaringan Komunikasi, Penerbit Informatika Bandung, 2004.

3.         William Stallings, Cryptography and Network Security Third Edition, Prentice Hall.