1. Введение
Задача Dining Philosophers — одна из классических задач, используемых для описания проблем синхронизации в многопоточной среде и иллюстрации методов их решения . Дейкстра впервые сформулировал эту проблему и представил ее относительно компьютеров, обращающихся к периферийным устройствам ленточных накопителей.
Настоящая формулировка была дана Тони Хоаром, который также известен изобретением алгоритма быстрой сортировки. В этой статье мы анализируем эту известную проблему и кодируем популярное решение.
2. Проблема
Диаграмма выше представляет проблему. Пять молчаливых философов (P1 – P5) сидят за круглым столом, проводят свою жизнь за едой и размышлениями.
У них есть пять вилок, которыми они могут поделиться (1 – 5), и чтобы иметь возможность есть, философ должен иметь вилки в обеих руках. Поев, он кладет их обоих, а затем их может взять другой философ, который повторяет тот же цикл.
Цель состоит в том, чтобы придумать схему/протокол, который поможет философам достичь своей цели — есть и думать, не умирая от голода.
3. Решение
Первоначальным решением было бы заставить каждого из философов следовать следующему протоколу:
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!
}
Как описывает приведенный выше псевдокод, каждый философ изначально думает. Через определенное время философ проголодается и захочет есть.
В этот момент он тянется к вилкам с обеих сторон и, получив их обе, приступает к еде . После еды философ кладет вилки так, чтобы они были доступны для соседа.
4. Реализация
Мы моделируем каждого из наших философов как классы, реализующие интерфейс Runnable , чтобы мы могли запускать их как отдельные потоки. Каждый Философ имеет доступ к двум развилкам слева и справа:
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
}
}
У нас также есть метод, предписывающий Философу выполнить действие — съесть, подумать или приобрести вилки, готовясь к еде:
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
}
Как показано в приведенном выше коде, каждое действие моделируется путем приостановки вызывающего потока на случайное время, чтобы порядок выполнения не зависел только от времени.
Теперь давайте реализуем основную логику Философа .
Чтобы имитировать получение форка, нам нужно заблокировать его, чтобы никакие два потока Philosopher не могли получить его одновременно.
Для этого мы используем ключевое слово synchronized , чтобы получить внутренний монитор объекта fork и предотвратить то же самое от других потоков. Руководство по ключевому слову synchronized в Java можно найти здесь . Теперь приступим к реализации метода run() в классе Philosopher :
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;
}
}
}
Эта схема в точности реализует описанную ранее: Философ немного думает, а потом решает поесть.
После этого он берет вилки слева и справа и начинает есть. Закончив, он опускает вилки. Мы также добавляем временные метки к каждому действию, что поможет нам понять порядок, в котором происходят события.
Чтобы запустить весь процесс, мы пишем клиент, который создает 5 Философов как потоки и запускает их всех:
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();
}
}
}
Мы моделируем каждую из вилок как общие объекты Java и делаем их столько, сколько философов. Мы передаем каждому Философу его левую и правую вилки, которые он пытается заблокировать с помощью ключевого слова synchronized .
Выполнение этого кода приводит к выводу, подобному следующему. Ваш вывод, скорее всего, будет отличаться от приведенного ниже, в основном потому, что метод sleep() вызывается для другого интервала:
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
Все Философы изначально начинают думать, и мы видим, что Философ 1 продолжает брать левую и правую вилки, затем ест и кладет обе вилки, после чего «Философ 5» берет ее.
5. Проблема с решением: тупик
Хотя кажется, что приведенное выше решение правильное, возникает проблема взаимоблокировки.
Взаимная блокировка — это ситуация, когда работа системы останавливается, поскольку каждый процесс ожидает получения ресурса, удерживаемого каким-либо другим процессом.
Мы можем подтвердить то же самое, запустив приведенный выше код несколько раз и проверив, что несколько раз код просто зависает. Вот пример вывода, который демонстрирует указанную выше проблему:
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
В этой ситуации каждый из Философов приобрел свою левую вилку, но не может приобрести правую вилку, потому что ее уже приобрел его сосед. Эта ситуация широко известна как циклическое ожидание и является одним из условий, которые приводят к взаимоблокировке и препятствуют работе системы.
6. Разрешение тупиковой ситуации
Как мы видели выше, основной причиной взаимоблокировки является циклическое ожидание, когда каждый процесс ожидает ресурса, удерживаемого другим процессом. Следовательно, чтобы избежать тупиковой ситуации, нам нужно убедиться, что условие циклического ожидания нарушено. Для этого есть несколько способов, самый простой из которых следующий:
> Все Философы первыми тянутся к своей левой вилке, кроме одного, который первым тянется к своей правой вилке.
Мы реализуем это в нашем существующем коде, внеся относительно небольшое изменение в код:
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();
}
}
}
Изменение происходит в строках 17-19 приведенного выше кода, где мы вводим условие, которое заставляет последнего философа сначала тянуться к своей правой вилке, а не к левой. Это нарушает условие циклического ожидания, и мы можем предотвратить взаимоблокировку.
Следующий вывод показывает один из случаев, когда все Философы получают шанс подумать и поесть, не вызывая тупиковой ситуации:
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
Можно проверить, запустив код несколько раз, что система свободна от тупиковой ситуации, которая возникла ранее.
7. Заключение
В этой статье мы рассмотрели известную проблему Dining Philosophers и концепции циклического ожидания и взаимоблокировки . Мы написали простое решение, которое вызвало взаимоблокировку, и внесли простое изменение, чтобы разорвать циклическое ожидание и избежать взаимоблокировки. Это только начало, и существуют более сложные решения.
Код для этой статьи можно найти на GitHub .