Проблемы тупиков. Бесконечное откладывание и старение процессов.
Тупиковая ситуация (тупик) - это ситуация, возникающая в результате монопольного использования разделяемых ресурсов, когда процесс, владея ресурсом, запрашивает другой ресурс, занятый непосредственно или через цепочку запросов другим процессом, ожидающим освобождения ресурса занятого первым процессом.
Тупик (клинч, дедлок) - ситуация, которая никогда не разрешится, т.е. процесс ждет ресурса, но он ему не будет выделен.
ОС в состоянии тупика ("зависание") - когда несколько процессов находятся в состоянии тупика.
Простая тупиковая ситуация в ОС:
Пусть имеются 2 процесса A и B, которым перед началом работы предоставлены ресурсы P1 и P2 соответственно. В какой-то момент времени процессу A понадобился P2, а процессу B - P1, но они их не получат, т.к. они удерживаются предыдущими процессами => наступила простая тупиковая ситуация в ОС.
Правила предотвращения тупиков в ОС:
Прежде чем процесс начнет свою работу, ему должны быть предоставлены все требуемые ресурсы.
В том случае, если во время работы ему понадобился дополнительный ресурс, ему необходимо возвратить все ранее выделенные ресурсы ОС и затем запросить все требуемые ресурсы с этим дополнительным ресурсом.
Бесконечное откладывание процесса.
В системе, где процессам приходится ждать пока она выделит ему требуемый ресурс может возникнуть ситуация, что будут приходить процессы с более высоким приоритетом, требующие тот же самый ресурс - ситуация бесконечного откладывания процесса.
В некоторых ОС данная ситуация предотвращается благодаря увеличению приоритетности ("старению" процесса) для того, чтобы ему был предоставлен требуемый ресурс, после чего приоритет понижается до прежнего уровня.
Бесконечное откладывание
Процессы, ожидающие ресурсов, встают в очереди к этим ресурсам. Такая очередь может обслуживаться любой невытесняющей стратегией планирования. Моментом, когда менеджер ресурса принимает решение об обслуживании, является освобождение ресурса.
Единственной дисциплиной, которая гарантирует, что все процессы в очереди будут в конце концов обслужены, является FCFS. Другие методы базируются на приоритетах - внешних или вычисляемых на основании размера запроса или/и безопасности ситуации. Очередь может быть упорядочена по возрастанию размера запроса, и при освобождении ресурсов последние могут отдаваться по запросу "самого подходящего" размера. Очередь может быть упорядочена в порядке возрастания опасности выделения ресурсов, и освободившийся ресурс может отдаваться тому процессу, запрос которого самый безопасный. При упорядочении очереди, процесс, выдавший самый большой или самый опасный запрос, может надолго в ней застрять, то есть, попасть в ситуацию бесконечного откладывания. С другой стороны, применение FCFS в чистом виде может привести к снижению уровня мультипрограммирования, к опасному состоянию и даже к тупику - если процесс со слишком большим запросом окажется первым в очереди. Отчасти это противоречие может быть сглажено, если мы допустим частичное выделение ресурсов: запрос, стоящий в очереди первым получает столько ресурсов, сколько ему можно выделить, сохраняя ситуацию безопасной, остальные - отдаются следующему в очереди процессу.
Поскольку тупиковая ситуация более опасна, чем бесконечное откладывание, ОС все же отдает предпочтение критериям безопасности, следовательно, заведомо предотвратить бесконечное откладывание невозможно. Бесконечное откладывание процесса устанавливается по времени его пребывания в очереди: если процесс пребывает в очереди дольше некоторого установленного времени, то считается, что он ожидает бесконечно. В зависимости от политики ОС в отношении справедливости обслуживания и от характеристик процесса (если они известны) допустимое время ожидания может устанавливаться большим или меньшим. Если же бесконечное откладывание установлено, то для его ликвидации ОС приостанавливает выдачу ресурсов новым процессам, пока не будет обслужен отложенный процесс.
Проблема тупиков до некоторой степени теряет актуальность в современных ОС, так как они имеют тенденцию к уменьшению количества неразделяемых ресурсов. Одним из способов сделать неразделяемое устройство разделяемым является буферизация, которую мы рассмотрим в следующей главе. Системные структуры данных разделяются с использованием средств взаимного исключения доступа, которым будет посвящена глава 8. Эта проблема, однако, становится все более актуальной для современных СУБД, которые обеспечивают одновременный доступ к ресурсам-данным для тысяч и десятков тысяч пользователей.