Проблема тупиков
6. ПРОБЛЕМА ТУПИКОВ
Во вводной части этого раздела мы остановимся на логической задаче, которая возникает при взаимодействии различных процессов, когда они должны делить одни и те же ресурсы. Эта проблема выбрана по разным причинам. Во-первых, она является непосредственным обобщением известной ситуации, согласно которой два человека не могут воспользоваться одновременно одной секцией вращающейся двери. Во-вторых, решение этой проблемы, которое я считаю нетривиальным и которое будет приведено в ¬6.1, дает нам хороший пример более тонких правил взаимодействия, чем те, с которыми мы до сих пор встречались. В-третьих, она предоставляет нам возможность проиллюстрировать (в ¬6.2) методы программирования, с помощью которых может быть достигнут дальнейший прогресс в наглядности представления. Для начала я приведу один пример разделения ресурсов. В качестве "процессов" мы можем принять "программы", описывающие некоторый вычислительный процесс, выполняемый вычислительной машиной. Выполнение такого вычислительного процесса требует определенного времени, в течение которого в памяти вычислительной машины хранится информация. Ограничимся процессами, о которых заранее известно следующее:
- Их требования к объему памяти не будут превышать определенного предела.
- Каждый вычислительный процесс завершится при условии, что требуемый процессу объем памяти будет предоставлен в его распоряжение. Завершение вычислительного процесса будет означать, что его требования к памяти уменьшились до нуля.
Предполагаем, что имеющаяся память поделена на "страницы" фиксированного размера, которые с точки зрения программы считаются эквивалентными.
Фактическое требование нужного процессу объема памяти может быть функцией, изменяющейся по мере протекания процесса, но, конечно, в соответствии с заранее заданной верхней границей. Предположим, что отдельные процессы запрашивают и возвращают память единицами в одну страницу. "Эквивалентность" (см. последнее слово предыдущего абзаца) означает, что процесс, запрашивающий новую страницу, просит просто "новую страницу", но никогда не специальную страницу или страницу из специальной группы.
Теперь мы потребуем, чтобы процесс, однажды начатый, получил рано или поздно возможность завершить свои действия, и будем отбрасывать любую схему, при которой может случиться, что процесс уничтожается на полдороге из-за своих действий, тем самым напрасно растратив уже выделенное ему на вычисления время.
Если вычислительная машина выполняет процессы один за другим, то они должны удовлетворять единственному условию, чтобы максимально требуемый ими объем памяти не превышал общую емкость памяти машины.
Если, однако, вычислительная машина обслуживает одновременно более одного процесса, то можно придерживаться правила, что допускаются только такие программы, у которых сумма их максимальных требований не превышает общей емкости памяти. Это правило, хотя и обеспечивает безопасность, является излишне ограничивающим, так как предполагает, что каждый процесс действительно занимает максимальную память во все время выполнения. Если мы посмотрим на следующую таблицу (где процессы "заимствуют" страницы из имеющейся памяти)
| Процесс | Максимальное требование |
Настоящий объем |
Дальнейшее требование |
| П1 П2 |
80 60 |
40 + 20 |
40 40 |
| Свободная память = 100 - 60 = 40 |
Если бы, однако, оба процесса затребовали теперь по следующей странице, и получили бы ее, то сложилась бы такая ситуация:
| Процесс | Максимальное требование |
Настоящий объем |
Дальнейшее требование |
| П1 П2 |
80 60 |
41 + 21 |
39 39 |
| Свободная память = 100 - 62 = 38 |
Эта ситуация, когда один из процессов может быть продолжен только при условии, что другой будет сперва уничтожен, называется "Смертельное Объятие" ("The Deadly Embrace").Проблема, которую нам необходимо решить, заключается в следующем: как избежать опасности тупика, не накладывая слишком больших ограничений.
