Распределение ресурсов. Проблема тупиков

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

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

О процессах известно следующее.

1. Их требования к объему памяти не будут превышать определенного предела.

2. Каждый вычислительный процесс завершится при условии, что требуемый процессу объем памяти будет предоставлен в его распоряжение. Завершение вычислительного процесса будет означать, что его требование к памяти уменьшилось до нуля.

Имеющаяся память поделена на страницы фиксированного размера, эквивалентные с точки зрения программы.

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

Если на вычислительной машине выполняется один процесс, или они последовательно следуют один за другим, единственным условием является то, чтобы запрашиваемый процессом объём памяти не превышал доступный объём памяти вычислительной машины. Если параллельно развиваются несколько процессов, то могут возникнуть проблемы с выделением им ресурсов и надо предусмотреть выделение памяти таким образом, чтобы все начатые процессы смогли завершить свое выполнение.

Ситуация, когда какой-либо из процессов может быть завершён лишь при условии уничтожения какого-либо другого процесса, называется «смертельными объятиями» или тупиком.

Рисунок - Тупиковая ситуация

Ситуация, приведенная выше, является тупиковой. Из этой ситуации невозможно выйти без уничтожения какого-либо из процессов.

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