Dining Philosopher's Problem & Solution

Sebelumnya telah dibahas mengenai semafor yang dapat digunakan untuk menyelesaikan masalah sinkronisasi proses, menggunakan studi kasus producer-consumer. Selanjutnya akan mengimplementasikan semafor pada studi kasus lainnya yaitu, dining philosophers yang merupakan contoh/permasalahan klasik pada sinkronisasi.

Gambar Dining Philosophers.

Permasalahan Utama

Terdapat lima filsuf yang duduk mengelilingi sebuah menja bundar. Tepat didepan setiap fisuf, terdapat satu mangkuk mie, dan setiap disebelah mangkuk mie tersebut terdapat satu garpu. Filsuf akan makan jika menggunakan dua garpu secara bersamaan, yaitu dipegang ditangan kanan dan kiri. Jika filsuf tidak makan, berarti ia sedang berfikir dan sedang menunggu filsuf disebelah kanan atau kirinya selesai makan, untuk mendapatkan kedua garpu, sehingga ia bisa makan dan tidak kelaparan.

Solusi Permasalahan

Dalam studi kasus ini, solusi permasalahan akan dituangkan kedalam program sederhana untuk mengatasi tidak ada filsuf yang akan mengalami kelaparan.

Solusi Pertama

Berikut solusi studi kasus dining philoshoper dalam bentuk program pertama.

#define N 5
void philosopher(int i) {
	int Ri = i;
	int Li = ((i+1) % N);
	while(true) {
		think(); /* lakukan beberapa waktu */
		take_fork(Ri);
		take_fork(Li);
		eat();
		put_fork(Ri);
		put_fork(Li);
	}
}

Kemungkinan kondisi yang akan muncul dari program solusi pertama. Bisa saja hanya beberapa proses yang selalu diprioritaskan/tidak adil sebagai contoh hanya P1 dengan P2, sementara P3, P4, dan P4, akan mengalami kelaparan/starvation. Serta kemungkinan akan terjadi deadlock, yaitu bisa saja setiap filsuf hanya mengambil satu garpu secara bersamaan, kemudian menunggu satu sama lain dalam waktu yang tak terhingga untuk memperoleh garpu lainnya.

Solusi Kedua

Berikut solusi studi kasus dining philoshoper dalam bentuk program kedua.

#define N 5
void philosopher(int i) {
	int Ri = i;
	int Li = ((i+1) % N);
	int fix_time = 10;
	int random_time = rand() % 10; /* rentang nilai acak 0 sampai 9 */
	while(true) {
		think(); /* lakukan beberapa waktu */
		take_fork(Ri);
		if(available(Li)) {
			take_fork(Li);
			eat();
			put_fork(Li);
			put_fork(Ri);
		} else {
			put_fork(Ri);
			sleep(fix_time); /* tunggu sampai waktu yang ditentunkan */
			// sleep(random_time); /* tunggu sesuai dengan waktu yang telah diacak */
		}		
	}
}

Kemungkinan kondisi yang akan muncul dari program solusi kedua. Misal semua filsuf berjalan secara bersamaan/simultan, dan kemudian semuanya berfikir dalam satu waktu. Setelah berfikir, kemudian secara bersamaan juga mereka mengambil garpu di kanan, karena garpu disebelah kiri mereka tidak ada, maka secara bersamaan juga mereka meletakkan garpu yang mereka pegang, dan hal ini akan dilakukan mereka terus menerus. Kondisi ini disebut dengan livelock, walaupun tidak terjadi deadlock, tetapi mengakibatkan terjadinya starvation secara bersama-sama. Jika nilai fix_time diubah menjadi random_time, ini hanyalah akan mereduksi terjadinya starvation dengan kemungkinan terjadi secara bersamaan maupun hanya satu atau beberapa filsuf.

Solusi Ketiga

Berikut solusi studi kasus dining philoshoper dalam bentuk program ketiga.

#define N 5
void philosopher(int i) {
	int Ri = i;
	int Li = ((i+1) % N);
	while(true) {
		think(); /* lakukan beberapa waktu */
		lock(mutex);
		take_fork(Ri);
		take_fork(Li);
		eat();
		put_fork(Ri);
		put_fork(Li);
		unlock(mutex);
	}
}

Solusi ketiga menggunakan mutex untuk melindungi critical sections dalam hal ini saat mengakses garpu, serta mencengah terjadinya deadlock. Scara garis besar alur program mutex ini adalah, ketika fungsi lock dipanggil, maka mutex akan bernilai 0 yang artinya satu proses sedang menggunakan dua garpu. Sebaliknya jika mutex bernilai 1, yaitu pada saat fungsi unlock dipanggil, maka garpu sedang tidak digunakan oleh proses manapun. Namum solusi ini memiliki permasalahan kinerja yaitu hanya ada satu fisuf yang dapat makan dalam satu waktu dan merupakan solusi yang paling tidak efisien. Kinerja dalam hal ini adalah utilitas/pemanfaatan resource yang rendah oleh program, sehingga terjadi jedah/delay.

Solusi Keempat

Berikut solusi studi kasus dining philoshoper dalam bentuk program keempat.

/* 
status seorang filsuf bisa menjadi EATING 
hanya jika filsuf di sebalah kanan dan kirinya sedang tidak makan.
*/

semaphore s[1] = 0, s[2] = 0, s[3] = 0, s[4] = 0, s[5] = 0;

void philosopher(int i) {
	int RIGHT = (i + 1);
	int LEFT = (i - 1);
	while(true) {
		think(); /* lakukan beberapa waktu */
		take_forks(i);
		eat();
		put_fork(i);
	}
}

void take_forks(int i) {
	lock(mutex);
	state[i] = HUNGRY;
	test(i);
	unlock(mutex);
	semWait(s[i]);
}

void put_forks(int i) {
	lock(mutex);
	state[i] = THINGKING;
	test(RIGHT);
	test(LEFT);
	unlock(mutex);
}

void test(int i) {
	if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
		state[i] = EATING;
		semSignal(s[i]);
	}
}

Solusi dari progam keempat ini, dapat dikatakan tidak akan terjadi deadlock maupun starvation. Karena diatur menggunakan semafor maka setiap filsuf mendapatkan giliran yang adil. Tidak hanya mencegah kedua hal tersebut, terlebih lagi program ini dapat melakukan utiliasi/memanfaatkan resource/garpu dengan baik, salah satu alasannya karna hanya melakukan blocking terhadap proses tertentu yang mencoba mengakses proses lainnya yang sedang dalam status EATING, dan proses yang terblok tersebut tidak harus mengulang proses lainnya dari awal, cukup menunggu hingga proses yang membloknya selesai makan, sehingga mengurangi jedah/delay.

Pembahasan Studi Kasus

Berikut ini pembahasan studi kasus dining philosophers dalam bentuk video, dan secara garis besar membahas mengenai permasalahan utamanya, serta membahas mengenai berbagai program solusi yang diberikan.

Sebelum melihat video pembahasan, hendaknya terlebih dahulu membaca artikel ini, karna terdapat beberapa pembaharuan/perbaikan materi yang ada pada video pembahasan.

Kesimpulan

Berbagai solusi program sederhana diatas, diasumsikan berjalan secara konkuren maupun paralel. Pada permasalahan dining philosophers ini jika terjadi deadlock atau livelock, maka dapat dipastikan akan terjadi starvation. Solusi yang paling ideal adalah program keempat yang menggunakan semafor, meskipun demikian hal ini tidaklah mutlak, masih banyak algoritma lainnya yang dapat menyelesaikan permasalahan studi kasus dining philosophers.

Referensi

1. Operating Systems: Internals and Design Principles (8th Edition), William Stallings, 2014.
2. Operating System Concepts (9th Edition in Chinese) by Abraham Silberschatz et al.
3. The Linux Programming Interface: A Linux and UNIX System Programming Handbook, Michael Kerrisk.
4. https://medium.com/@zinayouhan33/dining-philosopher-problem-and-solution-9a273a5fa614