Задача обедающих философов - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:22:30Z

rollbackEdits.php mass rollback

185.220.101.186 в 05:07, 1 сентября 2022

2022-09-01T05:07:49Z

Yeputons: /* Обобщение */

2019-06-02T16:30:19Z

‎Обобщение

Yeputons: /* Token ring */

2019-06-02T16:29:56Z

‎Token ring

Yeputons: /* Token ring */

2019-06-02T16:29:48Z

‎Token ring

Yeputons: /* Алгоритм обедающих философов */

2019-06-02T16:28:22Z

‎Алгоритм обедающих философов

Yeputons: /* Задача обедающих философов */

2019-06-02T16:10:33Z

‎Задача обедающих философов

5.18.249.29: /* Алгоритм обедающих философов */

2018-03-09T18:28:51Z

‎Алгоритм обедающих философов

5.18.249.29: /* Алгоритм обедающих философов */

2018-03-09T18:27:39Z

‎Алгоритм обедающих философов

5.18.249.29: /* Решение */

2018-03-09T18:16:26Z

‎Решение

← Предыдущая		Версия 16:22, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	[[Категория: Параллельное программирование]]		[[Категория: Параллельное программирование]]
	==Задача обедающих философов==		==Задача обедающих философов==

← Предыдущая		Версия 05:07, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	[[Категория: Параллельное программирование]]		[[Категория: Параллельное программирование]]
	==Задача обедающих философов==		==Задача обедающих философов==

@@ Строка 7: / Строка 7: @@
 ==Обобщение==
-Взаимное исключение -- это полный граф конфликтов, т.е есть вилка для каждой пары философов.
+В случае с философами у нас есть $N$ процессов и граф конфликтов между ними из $N$ рёбер (одно ребро — один общий для двух процессов ресурс). Процессу для работы надо собрать все конфликтующие с другими потоками ресурсы.
-Вначале раздадим вилки, например, по результатам сравнения id философов.
 ==Решение==

← Предыдущая		Версия 16:29, 2 июня 2019
Строка 39:		Строка 39:
	То есть, если ни один из процессов не заинтересован в критической секции, то маркер будет просто циркулировать по кольцу.		То есть, если ни один из процессов не заинтересован в критической секции, то маркер будет просто циркулировать по кольцу.

−	[[Файл:mutex-distributed-token.png]]	+	[[Файл:mutex-distributed-token.png\|400px]]

← Предыдущая		Версия 16:29, 2 июня 2019
Строка 38:		Строка 38:

	То есть, если ни один из процессов не заинтересован в критической секции, то маркер будет просто циркулировать по кольцу.		То есть, если ни один из процессов не заинтересован в критической секции, то маркер будет просто циркулировать по кольцу.
		+
		+	[[Файл:mutex-distributed-token.png]]

@@ Строка 14: / Строка 14: @@
 ===Алгоритм обедающих философов===
-) Все соседние вилки должны быть чистые, чтобы философ мог войти в критическую секцию.
+Как построить алгоритм (вроде описан в "The Drinking Philosophers Problem" от K.M.Chandy и K.Misra):
-) После еды он должен отдать вилки, но мы не будем тратить сообщения на их передачу. Просто помечаем, что вилки грязные.
+# Ориентируем граф конфликтов так, чтобы он стал ациклическим. Например, по результатам сравнения id философов. Ориентация ребра задаёт, у кого вилка. Так как в ациклическом графе есть исток, то хотя бы у кого-то все вилки есть. А когда поест, то можно перевернуть все рёбра у истока, тогда граф останется ациклическим. Если предположить, что философы всегда хотят есть (но едят конечное количество времени), то философы будут бесконечно есть.
-) При запросе соседа-философа будем мыть совместную вилку (делать ее чистой) и отдавать ее, даже если сами хотим есть.
+Другое описание:
-) При получении запроса на вилку, чистые вилки отдавать не будем.
+# Все соседние вилки должны быть чистые, чтобы философ мог войти в критическую секцию.
 Итого:

@@ Строка 1: / Строка 1: @@
 [[Категория: Параллельное программирование]]
 ==Задача обедающих философов==
-За круглым столом сидят шесть философов. На столе шесть тарелок с рисом и шесть вилок.
+За круглым столом сидят шесть философов (процессы). На столе шесть тарелок с рисом и шесть вилок.
 В каждый момент философ может либо есть (тогда ему необходимо две вилки), либо думать (для этого ему нужен только он сам). Философы не разговаривают между собой. Необходимо, чтобы все философы поели и не возникло драки за вилки.
 ==Обобщение==

← Предыдущая		Версия 18:28, 9 марта 2018
Строка 19:		Строка 19:

	4) При получении запроса на вилку, чистые вилки отдавать не будем.		4) При получении запроса на вилку, чистые вилки отдавать не будем.
		+
		+	Итого:
		+	* 0 сообщений на повторный заход в CS одним философом (процессом);
		+	* 2N-2 сообщений в худшем случае;
		+	* Количество сообщений пропорционально числу процессов, которые хотят попасть в критическую секцию.

	===Token ring===		===Token ring===

@@ Строка 18: / Строка 18: @@
 ) При запросе соседа-философа будем мыть вилки (делать их чистыми) и отдавать их, даже если сами хотим есть.
-) При получении запроса на вилку, чистые вилки не отдавать не будем.
+) При получении запроса на вилку, чистые вилки отдавать не будем.
 ===Token ring===