Алгоритм Философов Обеда

Я написал эту программу для решения этой проблемы с помощью алгоритма решения Arbitrator, упомянутого здесь , чтобы решить это. В нем говорится, что каждый философ должен запросить разрешение от Waiter, чтобы получить Fork. Philosopher не может начать есть, пока у него не будет обеих вилок. Я реализовал логику, чтобы он либо держал обе вилки, либо подавал, если удерживал только одну вилку.

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

DiningAlgorithm

package com.study.fundamentals.util;
    /**
     * This is starting point for the dining algorithm
     */
    public class DiningAlgorithm {

    public static void main(String[] args) {
        Thread thread1= new Thread(new Philosopher());
        Thread thread2= new Thread(new Philosopher());
        Thread thread3= new Thread(new Philosopher());
        Thread thread4= new Thread(new Philosopher());
        Thread thread5= new Thread(new Philosopher());
        thread1.start(); 
        thread2.start();
        thread3.start();
        thread4.start();
        thread5.start();
     }
    }

Philosopher

package com.study.fundamentals.util;
public class Philosopher implements Runnable{
    private static final int TIME_WHEN_PHILOSOPHER_FEELS_HUNGRY_AGAIN = 10;
    private static final int TIME_REQUIRED_TO_EAT = 5;
    private static int noOfPhilosophers =0;
    private int id;
    private Waiter waiter = new  Waiter();
    private Fork leftFork;
    private Fork rightFork;
    public Philosopher() {
        this.id=noOfPhilosophers;
        noOfPhilosophers++;
    }
    private void pickUpLeftFork(){
        if(null==leftFork){
            leftFork = waiter.getForkOnLeft(id);
        }
    }
    private void pickUpRightFork(){
        if(null==rightFork){
            rightFork = waiter.getForkOnRight(id);
        }
    }

    private void eat() throws InterruptedException{

        pickUpLeftFork();
        pickUpRightFork();
        if(bothForksAvailable()){
            System.out.println("both forks "+leftFork.getID() +" & "+rightFork.getID()+" are available for use for Philosopher "+id);
            eat(TIME_REQUIRED_TO_EAT);
        }

        putDownBothForks();
  }
    private void putDownBothForks() {
        if(null!=rightFork) {
            rightFork.putDownFork();
        }
        if(null!=leftFork){
            leftFork.putDownFork();
        }
        leftFork = null;
        rightFork =null;
    }
    private void eat(long miliseconds) throws InterruptedException {
        System.out.println(id+" has started eating");
        eatFor(miliseconds);
        System.out.println(id+" has finished eating");
    }
    private void eatFor(long miliseconds) throws InterruptedException {
        waitFor(miliseconds);
    }

    private void waitTillHeFeelsHungry() throws InterruptedException {
        waitFor(TIME_WHEN_PHILOSOPHER_FEELS_HUNGRY_AGAIN);
    }

    private void waitFor(long milliseconds) throws InterruptedException {
        Thread.currentThread().sleep(milliseconds);
    }

    public boolean bothForksAvailable(){
        return null!=leftFork && null!= rightFork;
    }
    @Override
    public void run() {
        System.out.println("Thread for philosopher "+id +" started");
         while(true){
             try {
                 eat();
                 waitTillHeFeelsHungry();
            } catch (InterruptedException e) {
                System.out.println("Interrupted Exception Occured, Reason "+e.getMessage());
            }
         }

    }
}

Waiter

package com.study.fundamentals.util;
import java.util.HashMap;
import java.util.Map;

public class Waiter {
    private static Map <Integer,Fork> map = new HashMap<Integer,Fork>(){{
        put(1,new Fork(1));
        put(2,new Fork(2));
        put(3,new Fork(3));
        put(4,new Fork(4));
        put(5,new Fork(5));
    }};

   private boolean canUseFork(int forkId){
       return !map.get(forkId).isBeingUsed();
   }

   public Fork getForkOnLeft(int philosopherId){
           return getFork(philosopherId+1);
   }

private Fork getFork(int forkId) {
    if(canUseFork(forkId)){
       map.get(forkId).useFork();
       return map.get(forkId);
    }
    return null;
}

   public Fork getForkOnRight(int philosopherId){
       if(philosopherId==0){
           return getFork(map.size());
       }
       else{
           return getFork(philosopherId);
       }
   }
}

Fork

package com.study.fundamentals.util;
/**
 * This is the resource which must be available for eating
 */
public class Fork {
 int id;
 boolean isBeingUsed ;
 public Fork(int id){
     this.id = id;
 }

public boolean isBeingUsed(){
    return isBeingUsed;
}

public void useFork(){
    isBeingUsed = true;
}

public void putDownFork(){
    isBeingUsed = false;
}

public int getID() {
    return id;
}

}
11 голосов | спросил Shirishkumar Bari 31 PM000000110000002031 2014, 23:17:20

3 ответа


7

Общий стиль

Стиль кодирования

  • Ваш интервал (например, this.id=noOfPhilosophers; vs leftFork = waiter.getForkOnLeft(id);, сравнения и т. д.), а также отступы (например, eat() и getFork()) довольно часто, что затрудняет чтение кода. Используйте любую IDE, чтобы исправить это легко.
  • Если вы используете this в конструкторе, всегда используйте его (this.id=noOfPhilosophers; vs noOfPhilosophers++;)

Передача идентификаторов

Я бы предпочел, если бы вы передали объекты вместо ids в методах Waiter, мне кажется более чистым, чем выставлять идентификаторы.

private

Ваши поля Fork должны быть закрытыми.

Слишком много методов

В Philosopher у вас есть eat(), eat(long miliseconds), eatFor(long miliseconds), waitFor(long milliseconds). Метод eat() имеет большой смысл, также как и код waitFor. Но другие методы на самом деле ничего не делают (за исключением того, что код сложнее читать).

использование static

Использование ключевого слова static в Waiter (а также класс Philosopher) несколько запутанный (его легко упускать) и ограничение. Я бы пошел с другим подходом, предлагая @Loki Astari .

Реализация решения арбитров

Фактически вы не применяете решение Arbitrator, как описано в Википедии.

  

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

Что вы на самом деле делаете:

  • выбрать левую вилку
  • выбрать правую вилку
  • ешьте, если можете, иначе не
  • положить вилки вниз

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

  

Если философ ел и один из его соседей запрашивал вилки, все остальные философы должны ждать, пока этот запрос не будет выполнен, даже если вилки для них все еще доступны.

Вы тоже этого не делаете. Всякий раз, когда философ спрашивает вилку (и она доступна), официант даст ему вилку.

  

Каждая вилка может быть грязной или чистой

У вас нет этого состояния.

И так далее.

В принципе, вы предотвращаете тупик, но ваш код по-прежнему открыт для жизни и голода.

ответил tim 1 stEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 01 Sep 2014 00:10:57 +0400 2014, 00:10:57
11

В конечном итоге ваш код не решает проблему из-за конфликтов потоков и синхронизации (см. ниже) и, таким образом, в конечном итоге терпит неудачу.

Но вы также не рассматриваете реальную проблему в основе этой проблемы. Как вы разрабатываете метод улучшения разрешения ресурсов?

В настоящий момент все 5 философов схватят вилку слева, когда они пойдут, чтобы получить вилку справа, теперь она уже принадлежит другому философу. Итак, сразу у вас есть 5 утверждений. Идея состоит в том, чтобы спроектировать систему, если бы вы минимизировали количество утверждений.

И почему вы берете правую вилку, когда у вас нет левой. Быть кровавым и говорить, если я не могу иметь обеих вилок, у меня может быть как минимум один, и попытаться помешать другим есть. Все дело не в том, чтобы быть жадным. Он должен быть спроектирован так, чтобы философы, как группа, получали столько пасты, сколько могли есть вместе (без какого-либо конкретного философа, голодающего).

Я бы предпочел, чтобы это выглядело так:

private void eat() throws InterruptedException
{
    // Only bother to try the right fork if the left succeeds.
    if (pickUpLeftFork() && pickUpRightFork())
    {
        System.out.println("both forks "+leftFork.getID() +
                           " & "+rightFork.getID()+
                           " are available for use for Philosopher "+id);
        eat(TIME_REQUIRED_TO_EAT);
    }

    putDownBothForks();
}

Обзор кода

Если у каждого Философа есть свой официант, тогда не будет никаких споров (так как у каждого официанта есть 5 вилок).

private Waiter waiter = new  Waiter();

Вам действительно нужен общий официант (или я бы назвал его таблицей). Элементы управления общими ресурсами. Таким образом, Философ N может использовать fork N и ((N+1)%MaxForks).

Также отсутствует синхронизация на Waiter, поэтому между тестом и получением другой нити можно легко создать вилку.

private Fork getFork(int forkId) {

    if(canUseFork(forkId)){           // Philosopher 1 tests and sees a fork.
       map.get(forkId).useFork();     // But before 1 can get the fork.
                                      // his thread is de-sheduled and Philosopher 2
                                      // tests and gets the fork.
                                      // Thus leaving them both using the fork.
       return map.get(forkId);
    }
    return null;
}
ответил Martin York 31 PM000000110000001331 2014, 23:33:13
6

(В дополнение к тому, что уже говорили другие)

Инкапсуляция

Когда вы передаете идентификаторы объектов в качестве параметров метода, это знак того, что вы не используете инкапсуляцию правильно. Идентификаторы объектов - это детали реализации, которые должны быть скрыты внутри класса. Класс Waiter не должен иметь знаний о «fork ids» и «philosopher ids», которые являются внутренними деталями реализации Fork и Philosopher.

Именование и логика

В текущей реализации Philospher делает это в цикле:

    eat литий> waitTillHeFeelsHungry литий>

Технически, он еще не ел . Он пытается есть , если официант позволяет ему. Поэтому tryToEat будет лучшим именем.

И поскольку waitTillHeFeelsHungry - это метод Философа, а не NuttyPhilosopher, поэтому он не должен ссылаться на себя в третьем человек, поэтому waitUntilHungry будет лучшим именем.

Затем в eat он вызывает pickUpLeftFork, а затем pickUpRightFork. Опять же, это не так, как это работает, он должен спросить разрешения на вилки. Таким образом, это название и дизайн будут лучше:

if (waiter.provideLeftFork(this) && waiter.provideRightFork(this)) {
    // ...
    eat(TIME_REQUIRED_TO_EAT);  // this time, for real
    waiter.thankYouItWasDelicious(this);  // signal that the forks are available
}

Что решает другую проблему: если Философ не может получить левую вилку, он не должен просить о праве, просто нет смысла, если он не захочет голодать своего товарища Философа по правую сторону в гоночном состоянии.

Кроме того, Философу не следует беспокоиться о том, чтобы управлять состояниями Форкса. Он может попросить их, использовать их и вернуть, ему не нужно знать, что заставляет их клевать.

жестко прописывать

Тот факт, что существует 5 философов и 5 вилок, жестко закодирован независимо в двух местах: в DiningAlgorithm.main , и в статической инициализации Waiter. Это может быть простительно для жесткого кода 5, но по крайней мере вы должны как-то убедиться, что если кто-то изменит код, чтобы добавить одного Философа, то автоматически добавится вилка.

Принцип единой ответственности

Подсчет уникальных идентификаторов в классе Философа нарушает принцип единой ответственности : в дополнение к еде, Философ должен также рассчитывать. Какое возмущение ;-) Вы можете использовать PhilosopherFactory, чтобы отвечать за создание Философов с уникальными идентификаторами.

Повторения

Вместо этого:

Thread thread1= new Thread(new Philosopher());
Thread thread2= new Thread(new Philosopher());
Thread thread3= new Thread(new Philosopher());
thread1.start(); 
thread2.start();
thread3.start();

Это было бы лучше:

for (int i = 0; i < 5; ++i) {
    new Thread(new Philosopher()).start();
}
ответил janos 1 stEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 01 Sep 2014 00:40:45 +0400 2014, 00:40:45

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132