Обедающие философы
Published: 2023-11-25 22:19:15


**Задача**. Несколько философов сидят за круглым столом. Между каждым из них есть одна палочка для еды. Для того чтобы поесть, философу нужно получить две палочки для еды. Философы всегда сначала берут левую от себя палочку, а потом правую. Dead-lock может возникнуть если все философы одновременно возьмут левую от себя палочку и будут ждать пока освободится правая.

![](https://cdn-images-1.medium.com/max/2350/1*SCJX3VtCPLiDMDud3_GYAg.png)

**Решение**. Это классическая задача на Dead-lock. Давайте сначала реализуем версию программы, которая может привести к Dead-lock.

Будем использовать ReentrantLock:

```java
    class Chopstick {
      private Lock lock;
    
      public Chopstick() {
        this.lock = new ReentrantLock();
      }
    
      public void pickUp() {
        lock.lock();
      }
      
      public void putDown() {
        lock.unlock();
      }
    }
    
    class Philosopher extends Thread {
      private Chopstick left;
      private Chopstick right;
    
      public Philosopher(Chopstick left, Chopstick right) {
        this.left = left;
        this.right = right;
      }
    
      public void run() {
        pickUp();
        //eat
        putDown();
      }
      
      private void pickUp() {
        left.pickUp();
        right.pickUp();
      }
    
      private void putDown() {
        right.putDown();
        left.putDown();
      }
    }
```

При такой реализации может возникнуть ситуация, когда каждый философ получит лок на левую от себя палочку для еды, а когда попытается получить лок на правую от себя палочку, то она уже будет занята и все философы будут ждать друг друга по кругу.

**Одним из вариантов разрешения Dead-lock является получения локов в определенном глобальном порядке, который универсален для всех потоков.** Смотрите также задачу про перевод денег между счетами: [Thread Safe перевод денег между двумя банковскими аккаунтами](https://dev.to/faangmaster/zadacha-s-sobiesiedovaniia-na-java-proghrammista-thread-safe-pierievod-dieniegh-miezhdu-dvumia-bankovskimi-akkauntami-1l74).

Например, мы можем пронумеровать все палочки и получать локи в порядке этих номеров. Вначале получить лок на палочку с меньшим номером, а потом с большим. В таком случае все философы, кроме последнего будут брать сначала правую, а потом левую палочку. А последний наоборот, сначала левую, а потом правую.

![](https://cdn-images-1.medium.com/max/2252/1*cO6rxBILviB9VuwM4JrTAA.png)

Код в таком случае будет таким:

```java
    class Chopstick {
      private Lock lock;
      private int id;
    
      public Chopstick(int id) {
        this.lock = new ReentrantLock();
        this.id = id;
      }
    
      public void pickUp() {
        lock.lock();
      }
      
      public void putDown() {
        lock.unlock();
      }
    
      public int getId() {
        return this.id;
      }
    }
    
    class Philosopher extends Thread {
      private Chopstick first;
      private Chopstick second;
    
      public Philosopher(Chopstick left, Chopstick right) {
        if (left.getId() < right.getId()) {
          this.first = left;
          this.second= right;
        } else {
          this.first = right;
          this.second= left;
        }
      }
    
      public void run() {
        pickUp();
        //eat
        putDown();
      }
      
      private void pickUp() {
        first.pickUp();
        second.pickUp();
      }
    
      private void putDown() {
        second.putDown();
        first.putDown();
      }
    }
```