2015-05-05
1253
Классический пример взаимной блокировки, предложенный Дейкстрой — задача об обедающих философах. В стандартной формулировке говорилось о пяти философах, но допустимо любое количество философов (далее n). Часть времени философы проводят размышляя, часть времени проводят за едой. Когда они размышляют — они не нуждаются в общих ресурсах, но во время обеда они сидят за круглым столом с ограниченным количеством столовых приборов. В оригинальном описании задачи философы должны использовать две вилки, что бы набрать спагетти из миски в центре стола, но более логично задача выглядит при наличии палочек для еды, тогда очевидно, что каждому философу для еды необходимо иметь 2 палочки.
Философы, как это часто бывает, очень бедны, поэтому смогли купить только по одной палочке (итого имеем n философов и n палочек для еды). Последние разложены кругом по столу, между философами. Когда философу захочется поесть, ему придется взять палочки слева и справа от себя. Если с какой либо стороны палочка уже занята другим философом, придется ждать её освобождения.
Если философы почти не тратят времени на размышление — они постоянно будут конкурировать за палочки при попытках поесть, и взаимные блокировки возникают чаще. Если же философов очень много или они проводят большую часть времени за размышлениями, взаимная блокировка может и не возникнуть, хотя её теоретическая вероятность больше нуля. При этом может возникнуть иллюзия, что программа лишена взаимной блокировки, однако вероятность её возникновения на самом деле всё еще существует (этим и интересна эта задача).
Взаимная блокировка всех философов возникнет, если все философы одновременно сядут за стол, тогда каждый возьмет по одной палочке и все будут ожидать.
Для решения проблемы необходимо осознавать, что тупик имеет место про сочетании следующих четырех обстоятельств:
1) Взаимное исключение: по крайней мере один ресурс, используемый потоками, не должен быть совместно используемым. В нашем случае одной палочкой для еды не могут одновременно пользоваться 2 философа.
2) По крайней мере одна задача должна удерживать ресурс и ожидать выделения ресурса, в настоящее время удерживаемого другой задачей. То есть для возникновения тупика философ должен сохранять при себе одну палочку и ожидать другую.
3) Ресурс нельзя принудительно отбирать у задачи. Все процессы должны освобождать ресурсы естественным путем. Наши философы вежливы и не станут выхватывать палочки друг у друга.
4) Должно произойти круговое ожидание, когда процесс ожидает ресурс, занятый другим процессом, который в свою очередь ждет ресурс, удерживаемый еще одним процессом, и т. д., пока один из процессов не будет ожидать ресурса, занятого первым процессом, что и приведет к порочному кругу. В нашем примере круговое ожидание происходит потому, что каждый философ пытается получить сначала правую палочку, а потом левую.
Так как в.б. возникает только при соблюдении всех перечисленных условий, для упреждения тупика достаточно нарушить всего лишь одно из них.
