Обеденная философская проблема с инструкцией по тестовому набору

Question

с инструкцией набора тестов, определенной как:

  function TestAndSet (var x: boolean): boolean;
  begin
    TestAndSet = x;
    x = true
  end;

Возможно ли решить проблему философов-столовых?И да, я знаю, что мы можем решить это с помощью семафоров или мониторов.

Answer 1

Да.

Для одного примера;с атомарной TestAndSet инструкцией и атомарной clear инструкцией;можно честно назначить «управляющего философа»;где назначенный управляющий философ проверяет, свободны ли обе их вилки, и решает, могут ли они есть / не могут есть, и затем освобождает контроль.

Например:

while(running) {
    if(testAndSet(controllerFlag) == TRUE) {
        if(nextController == ME) {
            if(bothForksAreFree()) {
                myNextState = EATING;
                markBothForksInUse(ME);
            } else {
                myNextState = WAITING;
            }
            nextController = nextController + 1;
            if(nextController > MAX_CONTROLLERS) {
                nextController = 0;
            }
        }
        clear(controllerFlag);
        if(myNextState == EATING) {
            eat();
            markBothForksFree(ME);
            think();
        }
    }
}

Для данных;это включает в себя присвоение каждому философу уникального и последовательного числа (например, от 0 до N), controllerFlag, а также флаг, представляющий состояние каждого разветвления (используется, свободен).markBothForksFree() может понадобиться использовать инструкцию "atomic clear", но все остальное защищено controllerFlag.

Answer 2

Конечно, атомарного TestAndSet достаточно для блокировки мьютекса.TestAndSet(fork) - это попытка блокировки, которая возвращает false, если она успешна.fork=false разблокирует его.

Вы можете использовать решение Дейкстры - каждый философ сначала блокирует самую северную вилку.