Попытка понять алгоритм N-процесса Петерсона

Question

Я пытаюсь понять алгоритм N-процесса Петерсона, и я столкнулся с этим вопросом.

Вопрос: Пусть 3 процессы имеют идентификаторы процессов 0, 1 and 2. Эти процессы выполняются одновременно на уни-процессоре и используют алгоритм N-процесса Петерсона для управления выполнением критического раздела. Каждый процесс выполняется следующий код псевдо:

lock(pid); 
<critical section>; 
unlock(pid 

, где lock() и unlock() функции, как определено

lock(for Process i): 

/* repeat for all partners */ 
for (count = 0; count < (NUMPROCS-1); count++) { 
    flags[i] = count; 
    turn[count] = i; 
    "wait until (for all k != i, flags[k]<count) or (turn[count] != i)" 
} 


Unlock (for Process i): 

/* tell everyone we are finished */ 
flags[i] = -1; 

Предположим, что состояние системы в любой момент времени определяется <flags[0], flags[1], flags[2], turn[0], turn[1]> значений и идентификатор выполняемый в настоящее время процесс. Предположим далее, что текущее состояние системы составляет <0,0,0,2,-1> с процессом 0Выполняется в настоящее время. Покажите один конкретный путь для запуска трех процессов, начиная с этого состояния. Когда вы отслеживаете одновременное выполнение трех процессов, покажите состояние системы на каждом шаге.

Мои наблюдения

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

// NUMPROCS = 3 

- Для i = 0

lock(for Process 0): 
for (count = 0; count < 2; count++) { 
    flags[0] = count; 
    turn[count] = 0; 
    "wait until (for all k != 0, flags[k]<count) or (turn[count] != 0)" 
} 


Unlock (for Process 0): 
flags[0] = -1; 

- Для i = 1

lock(for Process 1): 
for (count = 0; count < 2; count++) { 
    flags[1] = count; 
    turn[count] = 1; 
    "wait until (for all k != 1, flags[k]<count) or (turn[count] != 1)" 
} 


Unlock (for Process 1): 
flags[1] = -1; 

- Для i = 2

lock(for Process 2): 
for (count = 0; count < 2; count++) { 
    flags[2] = count; 
    turn[count] = 2; 
    "wait until (for all k != 2, flags[k]<count) or (turn[count] != 2)" 
} 


Unlock (for Process 2): 
flags[2] = -1; 

Мой вопрос в том, что С чего начать отслеживание кода? Дано, что flags[0]=0, flags[1]=0, flags[2]=0, turn[0]=2, turn[1]=-1, но как это поможет нам, где начать отслеживать код?

• Если мы начинаем непосредственно перед цикл процесса 0 то все значения поворота будет установлен, кроме того, что дано нам различные значения.

• Если мы предположим, выполнив вопрос означает, что процесс 0 в это критический участок, то цикл следующего процесса установит значения поворота к чему-то еще.

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

Было бы здорово, если бы я получил подсказку, чтобы помочь мне начать отслеживание кода.

Спасибо и простите за длинный вопрос.

Answer 1

Поскольку вы не просили ответа на вопрос, и вы задали разумный и разумный вопрос, я уверен, что могу указать вам в правильном направлении, не выполняя свою домашнюю работу (или что-то еще) для вас.

Во-первых, ключевая часть вопроса здесь:

Пусть состояние системы в любой момент времени определяется <flags[0], flags[1], flags[2], turn[0], turn[1]> значениями и идентификатор процесса исполняемой в данный момент. Предположим далее, что текущее состояние системы равно <0,0,0,2,-1> с процессом 0 в настоящее время выполняет.

Из этого можно предположить, что система была запущена нормально и достигла этого состояния во время ее выполнения. Поэтому нам нужно найти точку, в которой система может находиться в этом состоянии, а процесс 0 выполняется. Следующая часть дает нам некоторое пространство для маневра:

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

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

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

Процессы выполняются одновременно, но на одном процессоре. Таким образом, на самом деле только один из них когда-либо выполняется, но какая-то более высокая мощность (например, операционная система) переключается между ними так, как мы не можем определить. Вы говорите:

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

Я думаю, вы просто сформулировать это плохо, я подозреваю, что вы понимаете, реальность такова, что каждый процесс начинается с началом и работает, пока это не конец, поэтому «В то время как процесс выполняется на CPU она начинается там, где она была прервана и может запускать любое количество инструкций, пока не потеряет право запускать на CPU (количество инструкций зависит от того, что контролирует систему) »является более точной инструкцией.

Таким образом, самый простой способ - только начать с начала и повернуть ручку. Вопрос не говорит этого, но флаги и превратить обычно инициализируется -1 поэтому в начале мы имеем:

flags = [ -1, -1, -1 ]; turn = [ -1, -1 ] 

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

for (count = 0; count < (NUMPROCS-1); count++) { 

OK, считай = 0 для всех процессов, и все они идут к следующей строке:

flags[i] = count; 

Итак:

flags = [ 0, 0, 0 ]; turn = [ -1, -1 ] 

До сих пор, так хорошо - следующая строка :

turn[count] = i; 

ОК, это проблематично - каждый p rocess пытается установить одну и ту же переменную. Один из них выиграет, но мы не знаем, какой из них:

flags = [ 0, 0, 0 ]; turn = [ ?, -1 ] 

За исключением случаев, когда речь идет о нем. Мы можем сделать turn[0] = 2. Таким образом, мы находимся в подходящем состоянии с переменными, можно считать процесс 0 находится под контролем, и мы знаем, что на этой линии:

"wait until (for all k != i, flags[k]<count) or (turn[count] != i)" 

Для начала, для процесса 0, считать = 0 и я = 0 так

"wait until (for all k in {1,2}, flags[k]<0) or (turn[0] != i)" 

Вы можете увидеть, что положение or ложно, поэтому процесс 0 объедет петлю снова. Так будет обрабатываться 1. Предложение for all k не относится ни к кому. Таким образом, процесс 2 будет ждать из-за значения turn[0] - вы также можете увидеть, что это никогда не изменится, поэтому процесс 2 теперь заблокирован, ожидая, что предложение for all k станет истинным - на самом деле это ключ к тому, как работает эта система. Если вы будете следовать логике, чтобы ответить на вопрос, вы увидите, как процессы блокируют друг друга, так что только один из них выполняет критический раздел за раз. Просто продолжайте делать то, что я сделал выше, так как вам нужно всего лишь найти один путь, который вы можете выполнять в одно и то же время, и когда есть потенциальное столкновение, просто выберите значение и оттуда.

Вы также можете видеть, что если процесс 2 выполнил все свои строки сразу, прежде чем другие имели шанс, а затем обработали 1, а затем обработали 0, вы оказались бы в том же месте. Если вы работаете по всей системе по-разному, вы найдете подобный шаблон (обратите внимание, что нет гарантии о том, что процессы будут выполнять свои критические разделы, зависит от того, кто «выигрывает» на оспариваемых линиях).

Итак, вернемся к исходному вопросу, есть только несколько мест, где процесс 0 может находиться под контролем с этим состоянием системы. Либо на линии wait, либо на линии for, когда счетчик увеличен до 1 (после того, как он завершает цикл) или на линии, где он устанавливает flag[0]. После этого состояние системы не совпадает. Лучше всего считать самый ранний, поскольку процесс 1 не заблокирован (пока) и может также изменить состояние.

Конечная морщина, для полноты. Есть еще одно место, где этот процесс можно контролировать, и состояние системы может быть таким. И это как раз перед линией turn[count] = i;. В этом сценарии процесс 2 только что установил переменную, и процесс 0 вот-вот перепишет его. Вы можете продолжить здесь, но это будут процессы 1 и 2, которые идут вокруг цикла. Я включаю это, ожидая комментария об этом, я на самом деле не предлагаю вам использовать это в качестве отправной точки, хотя он полностью действителен. Вопрос почти наверняка предполагает, что вы начнете с процессов 0 и 1, идущих вокруг цикла, с 2 заблокированными в оживленном ожидании, чтобы узнать, что происходит оттуда.

Удачи вам.