Обедающие философы, уменьшить возможность возникновения deadlock-а

@Линда95 · Регистрация: 22.11.2013

Author24 — интернет-сервис помощи студентам

Есть программа, которая решает задачу обедающих философов.

Java

public class Phil {
    int pos; 
      Fork left; 
      Fork right; 
      int eatCount = 0; 
      long waitTime = 0; 
      long startWait; 
 
      Random rnd = new Random(); 
      public Phil (int pos, Fork left, Fork rigth){ 
      this.pos = pos; 
      this.left = left; 
      this.right = rigth; 
      } 
      
      public void eat(){ 
      waitTime+=System.currentTimeMillis()+startWait; 
      System.out.println("Философ "+pos+" ест"); 
      try{ 
       Thread.sleep(rnd.nextInt(100)); 
      } catch (InterruptedException e){ 
       e.printStackTrace(); 
      } 
      eatCount++; 
      System.out.println("Философ "+pos+" поел"); 
      } 
          public void think(){ 
       System.out.println("Философ "+pos+" думает"); 
       try{ 
        Thread.sleep(rnd.nextInt(100)); 
       } catch (InterruptedException e){ 
        e.printStackTrace(); 
       } 
       System.out.println("Философ "+pos+" проголодался"); 
       startWait=System.currentTimeMillis(); 
      }
}
 
public class MyPhil extends Phil implements Runnable { 
  volatile boolean stopFlag = false; 
  public MyPhil(int pos, Fork left, Fork rigth) { 
  super(pos, left, rigth); 
  } 
  
  public void run() { 
  while(!stopFlag){ 
   think(); 
   synchronized(left){ 
       } 
   synchronized(right){ 
 
     eat(); 
   } 
  } 
  System.out.println("Философ "+pos+" stop"); 
  } 
  
  public static void main(String[] args) throws Exception{ 
  int count = 5; 
  MyPhil[] phils = new MyPhil[count]; 
  Fork last = new Fork(); 
  Fork left = last; 
  for (int i=0; i<count; i++){ 
   Fork right=(i==count-1)? last: new Fork(); 
   phils[i] = new MyPhil (i,left,right); 
   left = right; 
  } 
  Thread[] threads = new Thread [count]; 
  for (int i=0; i<count; i++){ 
   threads[i] = new Thread (phils[i]); 
 
   threads[i].start(); 
  } 
  Thread.sleep(60000); 
  for (MyPhil phil: phils){ 
   phil.stopFlag = true; 
  } 
  for (Thread thread:threads){ 
   thread.join(); 
  } 
  for (MyPhil phil: phils){ 
   System.out.println("Философ "+phil.pos+" поел "+phil.eatCount+" раз и прождал "+phil.waitTime); 
   phil.stopFlag = true; 
  } 
  } }

Подскажите, пожалуйста, как можно оптимизировать этот код, чтобы уменьшить возможность возникновения ситуации deadlock(взаимная блокировка)?

HighPredator · 07.10.2016, 16:34

А в каком кейсе текущая имплементация позволяет схватить дедлок? Что-то из кода не пойму..

@Линда95 · 09.10.2016, 14:36 **[ТС]**

Вероятность дедлока увеличивается, если в функциях eat и think убрать sleep(). Подскажите, пожалуйста, что нужно изменить?

HighPredator · 10.10.2016, 08:06

Ну я бы сделал так:

Java

public class MyPhil extends Phil implements Runnable {
    private boolean stopFlag = false;
 
    private volatile Object volatileMutex;
 
    public MyPhil(int pos, Fork left, Fork right) {
        super(pos, left, right);
    }
 
    @Override
    public void run() {
        while (!getStopFlag()) {
            think();
            synchronized (left) {
            }
            synchronized (right) {
                eat();
            }
        }
        System.out.println("Философ " + pos + " stop");
    }
 
    public void stop() {
        synchronized (mutex()) {
            stopFlag = true;
        }
    }
 
    private boolean getStopFlag() {
        synchronized (mutex()) {
            return stopFlag;
        }
    }
 
    private Object mutex() {
        Object mutex = volatileMutex;
        if (mutex == null) {
            synchronized (this) {
                mutex = volatileMutex;
                if (mutex == null) {
                    mutex = new Object();
                    volatileMutex = mutex;
                }
            }
        }
        return mutex;
    }
}

@Линда95 · 10.10.2016, 16:39 **[ТС]**

Спасибо огромное! А можете объяснить принцип работы private Object mutex()? Насколько я поняла, это взаимное исключение?

HighPredator · 10.10.2016, 16:53

Сообщение от Линда95

это взаимное исключение?

Не понял, что вы под этим понимаете. Это специальный мьютекс -- объект по которому будет идти блокировка доступа. Он спроектирован так (сейчас могу неточно объяснить, ибо сам новичок в джаве, так что терминология достаточно новая), чтобы гарантировать детерминированное состояние в среде конкурентного доступа. На нем фиксируется монитор. Механизм работы в принципе вам станет ясен, если вы по шагам каждую инструкцию рассмотрите.

@turbanoff · 10.10.2016, 19:21

HighPredator, Зачем все эти пляски с ленивой инициализацией volatileMutex?
Обычно лок объявляют как

Java

1	private final Object mutext = new Object();

Вроде философ может есть только когда обе вилки у него, а у вас он одну отпускает, перед тем как взяться за вторую. synchronized (left) и synchronized (right) должны быть вложены друг в друга.

HighPredator · 10.10.2016, 23:03

Сообщение от turbanoff

Зачем все эти пляски с ленивой инициализацией volatileMutex?

Увидел у гугла, понравилось, пользую везде

И это вроде не ленивая инициализация, а double-checking locking idiom если не ошибаюсь.

@Линда95 · 11.10.2016, 18:23 **[ТС]**

Сообщение от turbanoff

synchronized (left) и synchronized (right) должны быть вложены друг в друга.

То есть должно получиться так?

Java

 public void run() {
        while (!getStopFlag()) {
            think();
            synchronized (left) {
                System.out.println("Философ "+pos+" левая вилка");
                synchronized (right) {
                System.out.println("Философ "+pos+" правая вилка");
                eat();
            }
            }
           
        }
        System.out.println("Философ " + pos + " stop");
    }

@turbanoff · 11.10.2016, 18:29

Линда95, да. eat можно вызывать только когда оба лока захвачены
Но, вот если так прямо сделать - то в вашем коде будет возможен deadlock.
Нужно хитро захватывать локи, чтобы такого не было.

@Линда95 · 12.10.2016, 19:31 **[ТС]**

Сообщение от turbanoff

Нужно хитро захватывать локи, чтобы такого не было.

А каким образом это можно сделать, не подскажете?

@turbanoff · 12.10.2016, 21:29

На википедии описаны возможные решения - https://ru.wikipedia.org/wiki/Проблема_обедающих_философов
Вот решение с официантом:

Java

class Fork {
}
 
class Waiter {
    private final Set<Fork> usedForks = Collections.newSetFromMap(new IdentityHashMap<>());
 
    void letMeEat(Fork a, Fork b, Runnable eat) {
        synchronized (usedForks) {
            while (usedForks.contains(a) || usedForks.contains(b)) {
                try {
                    usedForks.wait();
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }
            usedForks.add(a);
            usedForks.add(b);
        }
        synchronized (a) {
            synchronized (b) {
                eat.run();
            }
        }
        synchronized (usedForks) {
            usedForks.remove(a);
            usedForks.remove(b);
            usedForks.notifyAll();
        }
    }
}
 
class MyPhil implements Runnable {
    volatile boolean stopFlag = false;
    int pos;
    Fork left;
    Fork right;
    private final Waiter waiter;
    int eatCount = 0;
    long waitTime = 0;
    long startWait;
    Random rnd = new Random();
 
    public MyPhil(int pos, Fork left, Fork right, Waiter waiter) {
        this.pos = pos;
        this.left = left;
        this.right = right;
        this.waiter = waiter;
    }
 
    public void run() {
        while (!stopFlag) {
            think();
            waiter.letMeEat(left, right, () -> {
                if (Thread.holdsLock(left) && Thread.holdsLock(right)) {
                    eat();
                } else {
                    throw new RuntimeException("Waiter is a liar!");
                }
            });
        }
        System.out.println("Философ " + pos + " stop");
    }
 
    public static void main(String[] args) throws Exception {
        int count = 5;
        Fork[] forks = new Fork[count];
        for (int i = 0; i < forks.length; i++) {
            forks[i] = new Fork();
        }
        MyPhil[] phils = new MyPhil[count];
        Waiter waiter = new Waiter();
        for (int i = 0; i < count; i++) {
            Fork left = forks[i];
            Fork right = (i == count - 1) ? forks[0] : forks[i + 1];
            phils[i] = new MyPhil(i, left, right, waiter);
        }
        Thread[] threads = new Thread[count];
        for (int i = 0; i < count; i++) {
            threads[i] = new Thread(phils[i]);
            threads[i].start();
        }
        Thread.sleep(60000);
        for (MyPhil phil : phils) {
            phil.stopFlag = true;
        }
        for (Thread thread : threads) {
            thread.join();
        }
        for (MyPhil phil : phils) {
            System.out.println("Философ " + phil.pos + " поел " + phil.eatCount + " раз и прождал " + phil.waitTime);
        }
    }
 
    public void eat() {
        waitTime += System.currentTimeMillis() + startWait;
        System.out.println("Философ " + pos + " ест");
        try {
            Thread.sleep(rnd.nextInt(100));
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        eatCount++;
        System.out.println("Философ " + pos + " поел");
    }
 
    public void think() {
        System.out.println("Философ " + pos + " думает");
        try {
            Thread.sleep(rnd.nextInt(100));
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Философ " + pos + " проголодался");
        startWait = System.currentTimeMillis();
    }
}

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	07.10.2016, 16:34	2
	А в каком кейсе текущая имплементация позволяет схватить дедлок? Что-то из кода не пойму.. 1

@Линда95 2 / 2 / 0 Регистрация: 22.11.2013 Сообщений: 101
	09.10.2016, 14:36 [ТС]	3
	Вероятность дедлока увеличивается, если в функциях eat и think убрать sleep(). Подскажите, пожалуйста, что нужно изменить? 0

@Линда95 2 / 2 / 0 Регистрация: 22.11.2013 Сообщений: 101
	10.10.2016, 16:39 [ТС]	5
	Спасибо огромное! А можете объяснить принцип работы private Object mutex()? Насколько я поняла, это взаимное исключение? 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	10.10.2016, 16:53	6
	Сообщение от Линда95 это взаимное исключение? Не понял, что вы под этим понимаете. Это специальный мьютекс -- объект по которому будет идти блокировка доступа. Он спроектирован так (сейчас могу неточно объяснить, ибо сам новичок в джаве, так что терминология достаточно новая), чтобы гарантировать детерминированное состояние в среде конкурентного доступа. На нем фиксируется монитор. Механизм работы в принципе вам станет ясен, если вы по шагам каждую инструкцию рассмотрите. 1

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	10.10.2016, 23:03	8
	Сообщение от turbanoff Зачем все эти пляски с ленивой инициализацией volatileMutex? Увидел у гугла, понравилось, пользую везде И это вроде не ленивая инициализация, а double-checking locking idiom если не ошибаюсь. 0

@turbanoff 4091 / 3825 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 11
	11.10.2016, 18:29	10
	Линда95, да. eat можно вызывать только когда оба лока захвачены Но, вот если так прямо сделать - то в вашем коде будет возможен deadlock. Нужно хитро захватывать локи, чтобы такого не было. 1

@Линда95 2 / 2 / 0 Регистрация: 22.11.2013 Сообщений: 101
	12.10.2016, 19:31 [ТС]	11
	Сообщение от turbanoff Нужно хитро захватывать локи, чтобы такого не было. А каким образом это можно сделать, не подскажете? 0

	12.10.2016, 21:29

Обедающие философы, уменьшить возможность возникновения deadlock-а

Решение