2009 overview ИУС РВ (1185197), страница 7
Текст из файла (страница 7)
Иногда можноотобрать ресурс у его текущего владельца и отдать его другому процессу. Способностьзабирать ресурс у процесса, отдавать его другому процессу и затем возвращать назад так, чтобыисходный процесс этого не замечает, в значительной мере зависит от свойств ресурса. Выйти изтупика таким образом зачастую трудно или невозможно. Выбор приостанавливаемого процессаглавным образом зависит от того, какой процесс владеет ресурсами, которые легко могут бытьу него отняты. Во многих случаях требуется ручное вмешательство.Восстановление через откат. Если разработчики системы знают, что есть вероятностьвзаимоблокировки, они могут организовать работу таким образом, чтобы процессыпериодически создавали контрольные точки.
Созданные процессом контрольные точкиозначают, что состояние процесса записывается в файл, в результате чего впоследствии процессможет быть возобновлен из этого файла. Контрольные точки содержат не только образ памяти,но и состояние ресурсов, то есть информацию о том, какие ресурсы в данный моментпредоставлены процессу. Когда взаимоблокировка обнаружена, достаточно понять, какиересурсы нужны процессам. Чтобы выйти из тупика, процесс откатывается к тому времени,перед которым он получил данный ресурс, для чего запускается одна из его контрольных точек.Вся работа, выполненная после этой контрольной точки, теряется. В результате процесс вновьзапускается с более раннего момента, когда он не занимал тот ресурс, который теперьпредоставляется одному из процессов, попавших в тупик.
Если возобновленный процесс вновьпытается получить данный ресурс, ему придется ждать того момента, когда ресурс опять станетдоступен.Восстановление путем уничтожения процессов. Простейший способ выхода из тупиказаключается в уничтожении одного или нескольких процессов. Легче всего уничтожать тепроцессы, которые можно запустить сначала без всяких болезненных эффектов.
При этом могутбыть уничтожены как процессы, входящие в цикл взаимоблокировки, так и процессы, ненаходящиеся в цикле, но владеющие ресурсами, необходимыми заблокированным процессам.Избежание взаимоблокировок. Предотвращение взаимоблокировок.В большинстве систем процессы запрашиваются не все сразу, а поочередно. Системадолжна уметь решать, является ли предоставление ресурса безопасным или нет, и предоставитьего процессу только в первом случае.
Таким образом, возникает вопрос: существует лиалгоритм, который всегда может избежать ситуации взаимоблокировки, все время делаяправильный выбор? Ответом будет условие «да» - мы можем избежать тупиков, но если заранеебудет доступна определенная информация.Основные алгоритмы, позволяющие предотвращать взаимоблокировки, базируются наконцепции безопасных состояний. Говорят, что состояние безопасно, если оно не находится втупике и существует некоторый порядок планирования, при котором каждый процесс можетработать до завершения, даже если все процессы вдруг захотят немедленно получитьмаксимальное количество ресурсов.Проиллюстрируем сказанное на примере с одним ресурсом.
Пусть в некотором состояниипроцесс A занимает 3 экземпляра ресурса, но может потребовать 9 экземпляров. Процесс B внастоящий момент занял 2 экземпляра, но может потребовать еще 4. Процесс C владеет 2экземплярами, и ему могут понадобиться еще 5. В системе есть всего 10 экземпляров ресурса, 7из которых в настоящий момент распределены, а 3 остаются свободными. Текущее состояниесистемы показано как «состояние а».Имеет Max392427Свободно 3Состояние аABCИмеет Max394427Свободно 1Состояние бABCИмеет Max39027Свободно 5Состояние вABCИмеет Max39077Свободно 0Состояние гABCИмеет Max3900Свободно 7Состояние дABC«Состояние а» безопасно, потому что существует такая последовательностьпредоставления ресурсов, которая позволяет завершиться всем процессам.
Например,планировщик может просто запустить в работу процесс B на то время, пока он запросит иполучит два дополнительных экземпляра ресурса, что приведет систему к «состоянию б».Когда процесс B закончится, мы получим «состояние в». Затем планировщик может запуститьпроцесс C, что приведет нас к «состоянию г». По завершении процесса C мы получим«состояние д». В этом состоянии процесс A может занять все необходимые ему ресурсы итакже завершиться.
Таким образом, «состояние а» является безопасным.Имеет MaxA39B24C27Свободно 3Состояние аИмеет MaxA49B24C27Свободно 2Состояние бИмеет MaxA49B44C27Свободно 0Состояние вИмеет MaxA49B0C27Свободно 4Состояние гТеперь предположим, что система первоначально находится в том же состоянии, но вданный момент процесс A запрашивает и получает еще один ресурс. Это приводит на с«состоянию б». В этом состоянии планировщик уже не сможет найти последовательность,которая гарантировала бы работу системы. Можно дать проработать процессу B до тогомомента, пока он не запросит свои ресурсы («состояние в»).
В итоге процесс B успешнозавершится и система окажется в «состоянии г». В этом месте система застревает: в системеосталось всего 4 свободных экземпляра ресурса, а каждому из активных процессов необходимо5 экземпляров. Следовательно, решение о предоставлении ресурса, приводящее систему в«состояние б», привело ее в небезопасное состояние. Если из этого состояния запуститьпроцесс A или C, система не выйдет из тупика.Следует отметить, что небезопасное состояние само по себе не является тупиком.
Системаеще может проработать какое-то время (в данном случае – может закончиться процесс B).Кроме того, возможна ситуация, что процесс A сможет освободить ресурс до следующегозапроса, позволяя процессу C успешно завершиться, а системе – избежать взаимоблокировки.Таким образом, разница между безопасным и небезопасным состоянием заключается в том, чтов безопасном состоянии система может гарантировать, что все процессы закончат свою работу,а в небезопасном состоянии такую гарантию дать нельзя.Алгоритм планирования, позволяющий избегать взаимоблокировок, был разработанДейкстрой и носит название алгоритма банкира.
Он представляет собой расширениеалгоритма обнаружения тупиков. Модель алгоритма основана на примере банкира, имеющегодело с группой клиентов, которым он выдал ряд кредитов. Алгоритм проверяет, ведет ливыполнение каждого запроса к небезопасному состоянию. Если да, запрос отклоняется. Еслиудовлетворение запроса приводит к безопасному состоянию, ресурс предоставляется процессу.Чтобы понять, является ли состояние безопасным, банкир проверяет, может ли он предоставитьдостаточно ресурсов для завершения работы какого-либо клиента.
Если да, то эти ссудысчитается погашенными, после чего проверяется ближайший к пределу займа клиент и т.д.Если, в конце концов, все ссуды могут быть погашены, состояние является безопасным иисходный запрос можно удовлетворить. На практике применение алгоритма банкиразатруднено, потому что нечасто можно определить заранее, сколько ресурсов потребуетсяпроцессам в будущем. Кроме того, количество процессов не фиксировано и динамическименяется по мере работы. Более того, ресурсы, про которые считалось, что они доступны,внезапно могут исчезнуть.Как видно, уклонение от взаимоблокировок, в сущности, невозможно. Тогда возникаетвопрос, как реальные системы могут избегать тупиков. Для этого следует вспомнить, чтовзаимоблокировки невозможны, если не выполняется хотя бы одно из условийвзаимоблокировки.Условие взаимного исключения.
Если в системе нет ресурсов, отданных в единоличноепользование одному процессу, система никогда не попадет в тупик. На практике невозможноотказаться от этого.Условие удержания и ожидания. Если мы сможем уберечь процессы, занимающиенекоторые ресурсы, от ожидания остальных ресурсов, мы устраним ситуациювзаимоблокировки.
Один из способов достижения этой цели состоит в требовании, следуякоторому любой процесс должен запрашивать все ресурсы до начала работы. Если ресурсысвободны, процесс получит все ему необходимое и сможет работать до успешного завершения.Если один или несколько ресурсов заняты, процессу ничего не представляется.Первая проблема при этом подходе заключается в том, что многие процессы не знают,сколько ресурсов им понадобится, до тех пор, пока не начнут работу.
Другая проблема –неоптимальное распределение ресурсов.Условие отсутствия принудительной выгрузки ресурса. Устранение этого условия такжепрактически невозможно. Например, если процесс получил принтер и печатает входныеданные, насильственное изъятие принтера по причине недоступности какого-либо другогоустройства в лучшем случае сложно, а в худшем – невозможно.Условие циклического ожидания.
Циклическое ожидание можно устранить несколькимиспособами. Один из них следующий: процессу дано право только на один ресурс в данныймомент времени. Если нужен второй ресурс, процесс должен освободить первый.Другой способ уклонения от циклического ожидания заключается в поддержке общейнумерации всех ресурсов. Тогда действует общее правило: процессы могут запрашивать ресурскогда хотят этого, но все запросы должны быть сделаны в соответствии с нумерацией ресурсов.При выполнении такого рода правила граф ресурсов никогда не будет иметь циклов.
Покажемэто на примере двух процессов.Пусть процесс A имеет в монопольном использовании ресурс с номером I, а процесс B –ресурс с номером J. Мы можем попасть в тупик, если процесс A запросит ресурс J, а процесс B– ресурс I. Предположим, что ресурсы I и J различны. Это значит, что они имеют разныеномера. Если I больше J, то процессу A не позволяется запрашивать ресурс J, потому что егономер меньше, чем номер имеющегося ресурса. Если J меньше I, отклоняется запрос процессаB по той же причине. Так или иначе, блокировка невозможна.При работе с несколькими процессами сохраняется та же самая логика.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
