Masalah Filsuf Makan di Jawa

1. Perkenalan

Masalah Makan Filsuf adalah salah satu masalah klasik yang digunakan untuk menggambarkan masalah sinkronisasi dalam lingkungan multi-utas dan menggambarkan teknik untuk memecahkannya . Dijkstra pertama kali merumuskan masalah ini dan mempresentasikannya mengenai komputer yang mengakses periferal tape drive.

Formulasi ini diberikan oleh Tony Hoare, yang juga dikenal sebagai penemu algoritma pengurutan quicksort. Pada artikel ini, kami menganalisis masalah terkenal ini dan mengkodekan solusi populer.

2. Masalah

Diagram di atas mewakili masalahnya. Ada lima filsuf bisu (P1 - P5) duduk mengelilingi meja bundar, menghabiskan hidup mereka untuk makan dan berpikir.

Ada lima garpu untuk mereka bagi (1 - 5) dan untuk dapat makan, seorang filsuf harus memiliki garpu di kedua tangannya. Setelah makan, dia meletakkan keduanya dan kemudian mereka dapat dipilih oleh filsuf lain yang mengulangi siklus yang sama.

Tujuannya adalah untuk menghasilkan skema / protokol yang membantu para filsuf mencapai tujuan mereka untuk makan dan berpikir tanpa mati kelaparan.

3. Solusi

Solusi awal adalah membuat masing-masing filsuf mengikuti protokol berikut:

while(true) { // Initially, thinking about life, universe, and everything think(); // Take a break from thinking, hungry now pick_up_left_fork(); pick_up_right_fork(); eat(); put_down_right_fork(); put_down_left_fork(); // Not hungry anymore. Back to thinking! } 

Seperti yang dijelaskan oleh kode semu di atas, setiap filsuf pada awalnya berpikir. Setelah waktu tertentu, sang filsuf merasa lapar dan ingin makan.

Pada titik ini, dia meraih garpu di kedua sisinya dan begitu dia mendapatkan keduanya, lanjutkan untuk makan . Setelah selesai makan, sang filsuf meletakkan garpu itu agar tersedia untuk tetangganya.

4. Implementasi

Kami memodelkan setiap filsuf kami sebagai kelas yang mengimplementasikan antarmuka Runnable sehingga kami dapat menjalankannya sebagai utas terpisah. Setiap Filsuf memiliki akses ke dua percabangan di sisi kiri dan kanannya:

public class Philosopher implements Runnable { // The forks on either side of this Philosopher private Object leftFork; private Object rightFork; public Philosopher(Object leftFork, Object rightFork) { this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run() { // Yet to populate this method } }

Kami juga memiliki metode yang menginstruksikan seorang Filsuf untuk melakukan suatu tindakan - makan, berpikir, atau memperoleh garpu sebagai persiapan untuk makan:

public class Philosopher implements Runnable { // Member variables, standard constructor private void doAction(String action) throws InterruptedException { System.out.println( Thread.currentThread().getName() + " " + action); Thread.sleep(((int) (Math.random() * 100))); } // Rest of the methods written earlier }

Seperti yang diperlihatkan dalam kode di atas, setiap tindakan disimulasikan dengan menangguhkan utas pemanggilan untuk waktu yang acak, sehingga urutan eksekusi tidak diberlakukan oleh waktu saja.

Sekarang, mari kita terapkan logika inti seorang Filsuf .

Untuk mensimulasikan memperoleh garpu, kita perlu menguncinya sehingga tidak ada dua utas Filsuf yang mendapatkannya pada saat yang sama.

Untuk mencapai ini, kami menggunakan kata kunci tersinkronisasi untuk memperoleh monitor internal objek garpu dan mencegah utas lain melakukan hal yang sama. Panduan untuk kata kunci tersinkronisasi di Java dapat ditemukan di sini. Kami melanjutkan dengan menerapkan metode run () di kelas Philosopher sekarang:

public class Philosopher implements Runnable { // Member variables, methods defined earlier @Override public void run() { try { while (true) { // thinking doAction(System.nanoTime() + ": Thinking"); synchronized (leftFork) { doAction( System.nanoTime() + ": Picked up left fork"); synchronized (rightFork) { // eating doAction( System.nanoTime() + ": Picked up right fork - eating"); doAction( System.nanoTime() + ": Put down right fork"); } // Back to thinking doAction( System.nanoTime() + ": Put down left fork. Back to thinking"); } } } catch (InterruptedException e) { Thread.currentThread().interrupt(); return; } } } 

Skema ini secara tepat menerapkan skema yang telah dijelaskan sebelumnya: seorang Filsuf berpikir sejenak dan kemudian memutuskan untuk makan.

Setelah ini, dia mendapatkan garpu di kiri dan kanannya dan mulai makan. Setelah selesai, dia meletakkan garpu ke bawah. Kami juga menambahkan stempel waktu ke setiap tindakan, yang akan membantu kami memahami urutan peristiwa terjadi.

Untuk memulai seluruh proses, kami menulis klien yang membuat 5 Filsuf sebagai utas dan memulai semuanya:

public class DiningPhilosophers { public static void main(String[] args) throws Exception { Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; philosophers[i] = new Philosopher(leftFork, rightFork); Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } }

Kami memodelkan setiap percabangan sebagai objek Java generik dan menjadikannya sebanyak mungkin filsuf. Kami melewati setiap Philosopher garpu kiri dan kanannya yang dia coba kunci menggunakan kata kunci tersinkronisasi .

Menjalankan kode ini menghasilkan keluaran yang mirip dengan berikut ini. Output Anda kemungkinan besar akan berbeda dari yang diberikan di bawah ini, sebagian besar karena metode sleep () dipanggil untuk interval yang berbeda:

Philosopher 1 8038014601251: Thinking Philosopher 2 8038014828862: Thinking Philosopher 3 8038015066722: Thinking Philosopher 4 8038015284511: Thinking Philosopher 5 8038015468564: Thinking Philosopher 1 8038016857288: Picked up left fork Philosopher 1 8038022332758: Picked up right fork - eating Philosopher 3 8038028886069: Picked up left fork Philosopher 4 8038063952219: Picked up left fork Philosopher 1 8038067505168: Put down right fork Philosopher 2 8038089505264: Picked up left fork Philosopher 1 8038089505264: Put down left fork. Back to thinking Philosopher 5 8038111040317: Picked up left fork

Semua Filsuf pada awalnya mulai berpikir, dan kita melihat bahwa Filsuf 1 melanjutkan untuk mengambil garpu kiri dan kanan, kemudian makan dan melanjutkan untuk menempatkan keduanya ke bawah, setelah itu `Filsuf 5` mengambilnya.

5. Masalah Dengan Solusi: Deadlock

Meskipun tampaknya solusi di atas benar, ada masalah kebuntuan yang muncul.

Kebuntuan adalah situasi di mana kemajuan sistem terhenti karena setiap proses menunggu untuk memperoleh sumber daya yang dipegang oleh beberapa proses lain.

Kami dapat mengonfirmasi hal yang sama dengan menjalankan kode di atas beberapa kali dan memeriksa bahwa beberapa kali, kode hanya hang. Berikut adalah contoh keluaran yang menunjukkan masalah di atas:

Philosopher 1 8487540546530: Thinking Philosopher 2 8487542012975: Thinking Philosopher 3 8487543057508: Thinking Philosopher 4 8487543318428: Thinking Philosopher 5 8487544590144: Thinking Philosopher 3 8487589069046: Picked up left fork Philosopher 1 8487596641267: Picked up left fork Philosopher 5 8487597646086: Picked up left fork Philosopher 4 8487617680958: Picked up left fork Philosopher 2 8487631148853: Picked up left fork

Dalam situasi ini, masing-masing Filsuf telah memperoleh garpu kiri, tetapi tidak dapat memperoleh garpu kanan, karena tetangganya sudah mendapatkannya. Keadaan ini biasa disebut dengan circular wait dan merupakan salah satu kondisi yang mengakibatkan terjadinya kebuntuan dan menghambat kemajuan sistem.

6. Mengatasi Kebuntuan

Seperti yang kita lihat di atas, alasan utama dari kebuntuan adalah kondisi menunggu melingkar di mana setiap proses menunggu sumber daya yang ditahan oleh beberapa proses lain. Oleh karena itu, untuk menghindari situasi deadlock kita perlu memastikan bahwa kondisi circular wait rusak. Ada beberapa cara untuk mencapai ini, yang paling sederhana adalah sebagai berikut:

Semua filsuf meraih garpu kiri mereka terlebih dahulu, kecuali orang yang lebih dulu meraih garpu kanannya.

Kami menerapkan ini dalam kode yang ada dengan membuat perubahan yang relatif kecil pada kode:

public class DiningPhilosophers { public static void main(String[] args) throws Exception { final Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; if (i == philosophers.length - 1) { // The last philosopher picks up the right fork first philosophers[i] = new Philosopher(rightFork, leftFork); } else { philosophers[i] = new Philosopher(leftFork, rightFork); } Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } } 

Perubahan terjadi pada baris 17-19 dari kode di atas, di mana kami memperkenalkan kondisi yang membuat filsuf terakhir meraih garpu kanannya terlebih dahulu, bukan ke kiri. Ini merusak kondisi menunggu melingkar dan kita bisa menghindari kebuntuan.

Output berikut menunjukkan salah satu kasus di mana semua Filsuf mendapatkan kesempatan untuk berpikir dan makan, tanpa menyebabkan kebuntuan:

Philosopher 1 88519839556188: Thinking Philosopher 2 88519840186495: Thinking Philosopher 3 88519840647695: Thinking Philosopher 4 88519840870182: Thinking Philosopher 5 88519840956443: Thinking Philosopher 3 88519864404195: Picked up left fork Philosopher 5 88519871990082: Picked up left fork Philosopher 4 88519874059504: Picked up left fork Philosopher 5 88519876989405: Picked up right fork - eating Philosopher 2 88519935045524: Picked up left fork Philosopher 5 88519951109805: Put down right fork Philosopher 4 88519997119634: Picked up right fork - eating Philosopher 5 88519997113229: Put down left fork. Back to thinking Philosopher 5 88520011135846: Thinking Philosopher 1 88520011129013: Picked up left fork Philosopher 4 88520028194269: Put down right fork Philosopher 4 88520057160194: Put down left fork. Back to thinking Philosopher 3 88520067162257: Picked up right fork - eating Philosopher 4 88520067158414: Thinking Philosopher 3 88520160247801: Put down right fork Philosopher 4 88520249049308: Picked up left fork Philosopher 3 88520249119769: Put down left fork. Back to thinking 

Hal tersebut dapat diverifikasi dengan menjalankan kode beberapa kali, bahwa sistem bebas dari situasi kebuntuan yang terjadi sebelumnya.

7. Kesimpulan

Dalam artikel ini, kami mengeksplorasi masalah Makan Philosophers yang terkenal dan konsep menunggu melingkar dan kebuntuan . Kami membuat kode solusi sederhana yang menyebabkan kebuntuan dan membuat perubahan sederhana untuk menghentikan menunggu melingkar dan menghindari kebuntuan. Ini baru permulaan, dan solusi yang lebih canggih memang ada.

Kode untuk artikel ini dapat ditemukan di GitHub.