Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
kravam
быдлокодер
1711 / 898 / 105
Регистрация: 04.06.2008
Сообщений: 5,586
1

Алгоритм Петерсона: почему поток не может два раза подряд выполнить критическую секцию?

12.03.2016, 20:12. Просмотров 500. Ответов 2
Метки нет (Все метки)

Друзья! Имеем два потока.

Читаем:


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

Для двух потоков, которые планируются Алгоритмом Петерсона это означает, что один поток не может два раза подряд выполнить критическую секцию, то есть потоки работают так (чередуются):

1) нулевой поток выполнил критическую секцию
2) первый поток выполнил критическую секцию
3) нулевой поток выполнил критическую секцию
4) первый поток выполнил критическую секцию

и т. д.

И никак иначе! Но на самом-то деле это нет так. Вот код каждого из потоков:

C++
1
2
3
4
5
6
7
8
9
10
shared int ready[2] = {0, 0}; 
shared int turn; 
while (some condition) { 
   ready[i] = 1; 
   turn =1-i; 
   while(ready[1-i] && turn == 1-i);
      critical section 
   ready[i] = 0; 
      remainder section 
}
Потока два, нулевой и первый. На рисунке я показал пошагово (по атоммарным операциям)- сперва отработал нулевой поток, вошёл в remainder section и её выполняет. remainder section по условию не обязана быть атоммарной. Поэтому тут вступает в дело первый поток, выполняет свою критическую секцию спокойно ДВА РАЗА, пока нулевой поток крутится себе в remainder section. Нулевой поток зелёный, слева. Первый поток синий, справа. Красным написал важные пояснения.

Почему же мне удалось смоделировать ситуацию, когда используя алгоритм Петерсона, поток выполняет критическую секцию два раза? ЧЯДНТ? Спасибо, кто откликнется.
0
Миниатюры
Алгоритм Петерсона: почему поток не может два раза подряд выполнить критическую секцию?  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2016, 20:12
Ответы с готовыми решениями:

Передача указателя на критическую секцию
Уважаемые програмисты MFC и WinAPI, вопрос к вам! Есть класс наследованный от CWinThread и...

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

Вход потоков в критическую секцию по порядку
Как создать такое событие чтобы потоки входили в критическую секцию по порядку 1,2,3,4 ..... Пока...

Написать программу с семафорами которая входит в критическую секцию
На дом задали такую домашку "написать программу с семафорами которая входит в критическую секцию"....

Где нужно всунуть Критическую секцию для корректной работы
Здравствуйте, есть такая проблема, точнее я полагаю, что она там есть. В обще при создании форм я...

2
kravam
быдлокодер
1711 / 898 / 105
Регистрация: 04.06.2008
Сообщений: 5,586
12.03.2016, 23:22  [ТС] 2
Разобрался. Дело в том, что поток МОЖЕТ сколько угодно раз выполнять критическую секцию, пока другой поток выполняет remainder section (именно такой пример я и привёл)

Просто ни один поток не может выполнять критическую секцию более одного раза, если другой поток в это время находится не в remainder section, а в цикле while(ready[1-i] && turn == 1-i);. то есть не должно такого быть, что один поток ждёт-ждёт своей очереди на выполнение критической секции (инструкция while (ready[1-i] && turn == 1-i)), а второй в это время выполняет критическую секцию несколько раз.

Но это не приведённый мной случай.
1
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
13.03.2016, 07:29 3
Не понял. Пусть 0 выполняет critical section. В этот момент 1 пытается туда же войти и виснет на мутексе. Рано или поздно 0 освобождает мутекс. Пусть 1 в этот момент вытеснен - и что, кто же помешает 0 захватить мутекс опять?

Добавлено через 1 час 49 минут
Цитата Сообщение от kravam Посмотреть сообщение
while(ready[1-i] && turn == 1-i);
Недосмотрел последнюю точку с запятой Тогда да. Не знал такого приемчика, спасибо
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2016, 07:29

Реализовать критическую секцию на основе объекта синхронизации типа "событие"
Есть код, все, вреде бы логически правильно... Должно работать, но... Увы нет((( Если есть...

Цикл while выполняется два раза подряд
Есть такой код, у меня этот цикл выполняется 2 раза за одно нажатие клавиши, в чем может проблема?...

Symbol LS2208 считывает штрих-код два раза подряд
Здравствуйте. Есть 1С 8,3 Розница 1 и сканер штрих-кодов Symbol LS2208. Сканер подключен через...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru