Тупики на ресурсах типа CR, CR и SR, SR.

При параллельном выполнении процессов в вычислительной системе могут возникать ситуации, при которых два или более процессов вс¨ время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из двух процессов ожидает ресурс, занятый другим процессом. Из-за такого ожидания ни один из процессов не может продолжит сво¨ выполнение и освободить в конечном итоге ресурс, необходимый другому процессу. Такая ситуация называется тупиком или клинчем. При рассмотрении проблемы тупиков целесообразно понятие ресурсов вычислительной системы обобщить и разделить их все на два класса – повторно используемые или системные ресурсы (SS – System Resource) и потребляемые или расходуемые ресурсы (CR – Consumable Resource)

Системный ресурс (SR) есть конечное множество единиц со следующими свойствами: число единиц ресурса постоянно; каждая единица ресурса или доступна, или распределена одному и только одному процессу; процесс может освободить единицу ресурса, только, если он раньше получил эту единицу, т. е. никакой процесс не может оказывать какое-либо влияние ни на один ресурс, если он ему не принадлежит. Примерами таких ресурсов являются компоненты аппаратуры (оперативная память, внешняя память, внешние устройства, процессор), а также программные и информационные компоненты (файлы, таблицы, переменные и т.п.). Расходуемый ресурс (CR) отличается от ресурса типа SR в нескольких важных отношениях: число доступных единиц некоторого ресурса типа CR изменяется по мере того как приобретаются и освобождаются отдельные его элементы выполняемыми процессами, а также число единиц ресурса является потенциально неограниченным; процесс типа “Производитель” увеличивает число единиц ресурса, освобождая одну или более единиц; процесс типа “Потребитель” уменьшает число единиц ресурса, сначала запрашивая а затем приобретая одну или более единиц. Примерами таких ресурсов являются синхронизирующие сигналы, сигналы прерываний, сообщения, которыми обмениваются процессы. Пример тупика на ресурсах типа CR. Пусть три процесса Пр1, Пр2, Пр3 вырабатывают сообщения М1, М2, М3 по кольцевой схеме. Процесс Пр1 является потребителем сообщения М3, процесс Пр2 должен получить сообщение М1, а Пр3 – М2. Таким образом, каждый из процессов одновременно является и “Поставщиком ” и “Потребителем”, и вместе они образуют кольцевую схему передачи сообщений друг другу. Пример тупика на ресурсах типа CR и SR. Пусть некоторый процесс Пр1 должен обменяться сообщениями с процессом Пр2 и каждый из них запрашивает некоторый ресурс R, прич¨м Пр1 требует три единицы этого ресурса для своего выполнения, а Пр2 – две единицы и только на время обработки сообщения. Всего же у системы имеется только четыре единицы ресурса R. Запрос на ресурс R можно реализовать через процедуру монитора Request(R, N) – запрос N единиц ресурса R, и Release(R, N) – освобождение N единиц ресурса R. Обмен сообщениями производится через почтовый ящик Пя Пример тупика на ресурсах типа SR. Предположим, что существуют два процесса Пр1 и Пр2, разделяющих два ресурса типа SR: R1 и R2. Пусть взаимное исключение доступа к этим ресурсам реализуется с помощью двоичных семафоров S1 и S2 соответственно. Процессы Пр1 и Пр2 обращаются к ресурсам Для того чтобы возник тупик, необходимо, чтобы одновременно выполнялись четыре условия: взаимного исключения, при котором процессы осуществляют монопольный доступ к ресурсам; ожидания, при котором процесс, запросивший ресурс, жд¨т до тех пор, пока его запрос не будет удовлетвор¨н, при этом удерживая ранее полученные ресурсы; отсутствия перераспределения, при котором ресурсы нельзя отобрать у процесса, если они уже ему выделены; кругового ожидания, при котором существует замкнутая цепь процессов, каждый из которых жд¨т ресурс, удерживаемый его предшественником в цепи.

Методы борьбы с тупиками.

Предотвращение тупиков за счет тщательного выделения ресурсов или нарушения одного из условий возникновения тупиков. Система, предоставляя ресурс в распоряжение процесса, должна принять решение, безопасно это или нет. Возникает вопрос: есть ли такой алгоритм, который помогает всегда избегать тупиков и делать правильный выбор. мы можем избегать тупиков, но только, если определенная информация известна заранее Предотвращение тупиков и алгоритм банкира.

Предположим, что у системы в наличии n устройств, например лент. Суть алгоритма состоит в следующем. ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n.Пользователь гарантирует, что если ОС в состоянии удовлетворить его запрос, то все устройства будут возвращены системе в течение конечного времени. Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнение в течение конечного времени.В соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным. Недостатки алгоритма банкира Алгоритм банкира исходит из фиксированного количества ресурсов. Он требует, чтобы число работающих пользователей оставалось постоянным Данный алгоритм требует, чтобы распределитель гарантированно удовлетворял запросы за конечный период времени. Алгоритм требует, чтобы клиенты гарантированно возвращали ресурсы. нарушения одного из условий возникновения тупиков.Если организовать работу системы так, что, по крайней мере, одно из этих условий не удовлетворено, тупик не возможен. Нарушение условия взаимоисключения Если в системе отсутствуют выделенные ресурсы, тупиков не будет. Hарушение условия ожидания дополнительных ресурсов- заставить все процессы затребовать все свои ресурсы перед выполнением (все или ничего). Если система в состоянии выделить процессу все необходимое, он может работать до завершения. Если хотя бы один из ресурсов занят, процесс будет ждать. Нарушение принципа неперераспределяемости. можно отбирать ресурсы у удерживающих их процессов до завершения этих процессов. Если бы это было всегда возможно, то можно было бы добиться невыполнения третьего условия возникновения тупиков. Если процесс в течение некоторого времени использует определенные ресурсы, а затем освобождает эти ресурсы, он теряет всю работу, проделанную до настоящего момента. Нарушение условия кругового ожидания каждый процесс может иметь только один ресурс в каждый момент времени. Если нужен второй ресурс - освободи первый. Другой способ - присвоить всем ресурсам уникальные номера и потребовать, чтобы процессы запрашивали ресурсы в порядке возрастания номеров. Тогда круговое ожидание возникнуть не может.

Задачи управления памятью.

Основная память (она же ОЗУ) является важнейшим ресурсом, эффективное использование которого решающим образом влияет на общую производительность системы.

Для однозадачных ОС управление памятью не является серьезной проблемой, поскольку вся память, не занятая системой под собственные нужды, может быть отдана в распоряжение единственного пользовательского процесса. Процедуры управления памятью решают следующие задачи:

- выделение памяти для процесса пользователя при его запуске и освобождение этой памяти при завершении процесса;

- обеспечение настройки запускаемой программы на выделенные адреса памяти;

- управление выделенными областями памяти по запросам программы пользователя (например, освобождение части памяти перед запуском порожденного процесса).

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