Другая проблема, которая может возникнуть во время распределения ресурсов, — взаимная блокировка (deadlock), состояние, когда два или более процесса блокируются, поскольку каждый ждет освобождения ресурса, используемого другим. Например, один процесс имеет доступ к принтеру, но ждет освобождения запоминающего устройства, в то время как другой процесс имеет доступ к запоминающему устройству, но ждет освобождения принтера. Похожая ситуация может возникнуть, когда процессы создают новые процессы для выполнения подзадач. Если планировщик не располагает свободным местом в таблице процессов, а каждый процесс системы должен создать дополнительный процесс для завершения задачи, тогда ни один из них не может продолжаться. Такие условия могут значительно ухудшить работу системы (рис. 3.9).
Взаимная блокировка возникает, когда выполняются все три приведенные ниже условия.
1. Существует конкуренция за ресурс, который не может использоваться совместно.
2. Ресурсы запрашиваются по частям, то есть, получив некоторые ресурсы, процесс позже возвращается, чтобы получить больше.
3. Если ресурс распределен, то его уже нельзя принудительно извлечь.
Проблему взаимной блокировки можно ликвидировать, устранив одно из этих условий. Для разрешения ситуаций, определяемых третьим условием, пользуются методами обнаружения и коррекции тупиковой ситуации. В этих случаях вероятность появления взаимной блокировки считается настолько незначительной, что не предпринимается никаких действий для ее устранения. Вместо этого взаимная блокировка обнаруживается, когда она уже возникла, и устраняется с помощью принудительного освобождения некоторых ресурсов. Наш пример с переполнением таблицы процессов попадает в эту категорию. Обычно системный администратор создает таблицу процессов, которой достаточно для данной установки. Однако если тупик все-таки возникает из-за переполнения таблицы, администратор просто удаляет (профессиональный термин «убивает») некоторые из процессов, освобождая место в таблице для других процессов.
Методы, которые устраняют первые два условия, называются способами устранения тупиковых ситуаций. Например, один из них ликвидирует второе условие благодаря тому, что все процессы запрашивают все необходимые им ресурсы сразу. Другой способ ликвидирует первое условие не с помощью непосредственного устранения конкуренции, а трансформируя ресурсы, которые нельзя использовать совместно, в совместно используемые. Предположим, что несколько процессов запрашивают доступ к принтеру. Каждый раз, когда процессу нужен доступ к принтеру, операционная система предоставляет его. Однако вместо того чтобы соединить процесс с драйвером принтера, операционная система соединяет его с драйвером устройства, хранящего информацию, которую нужно распечатать на диске. Таким образом, каждый процесс, считая, что у него есть доступ к принтеру, продолжает выполнение задачи. Позже, когда принтер освобождается, операционная система передает данные с диска на принтер. Следовательно, операционная система трансформирует ресурсы, которые нельзя использовать совместно, в совместно используемые, создавая иллюзию существования нескольких принтеров. Техника сохранения данных на диске для последующего распечатывания в более удобное время называется спулингом (spooling).
Конечно, когда процессы конкурируют за ресурсы, возникают и другие трудности. Например, программа управления файлами может предоставить доступ к файлу одновременно нескольким процессам, если они просто считывают данные из файла. Если же несколько процессов одновременно будут пытаться изменить данные в файле, то может возникнуть конфликт. Следовательно, программа управления файлами должна распределять доступ к файлу в соответствии с потребностями процессов, разрешая доступ для чтения нескольким процессам, а доступ для записи — только одному. Другие системы делят файл на части, чтобы разные процессы одновременно могли изменять разные части файла. Однако при этом возникают другие сложности. Как, например, процессы с доступом только для чтения узнают, когда процесс с доступом для записи изменяет файл?