Очереди сообщений.

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

Для работы с очередью сообщений процесс должен воспользоваться системным вызовом msgget, указав в качестве параметра значение ключа. Если очередь с данным ключом в наст. момент не используется ни одним процессом, то для нее резервируется область памяти, а затем процессу возвращается идентификатор очереди, который, как и дескриптор файла, имеет локальное для процесса значение. Если же очередь уже используется, то процессу просто возвращается её идентификатор.

После открытия очереди процесс может помещать в него сообщения с помощью вызова msgsnd или читать сообщения с помощью вызова msgrsv.

Почтовый ящик – это буфер для определенного количества сообщений, тип который задается при создании ящика. При использовании почтовых ящиков в качестве параметров send и receive задаются почтовые ящики, а не процессы. Если процесс пытается послать сообщение в полный почтовый ящик, то ему приходится подождать пока хотя бы одно сообщение не будет удалено из ящика.

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

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

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

Почтовый ящик может быть связан с парой процессов, только с отправителем, только с получателем или его можно получить из множества почтовых ящиков которые используют все или несколько процессов. Почтовый ящик, связанный с процессом - получателем облегчает посылку сообщений от нескольких процессов фиксированный пункт назначения. Если почтовый ящик не связан жестко с процессом, то сообщение должно содержать идентификаторы процесса- отправителя и процесса – получателя.

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

Правила работы почтового ящика могут быть различными в зависимости от его сложности. В простом случае сообщения передаются только в одном направлении. Процесс П1 может посылать сообщения до тех пор пока имеются свободные гнезда, если все гнезда заполнены, то процесс П2 может попытаться послать сообщение позже. Процесс П2 может получать сообщения до тех пор пока имеются заполненные гнёзда. Если сообщений нет, то он может либо ждать сообщений, либо продолжать работу.

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

Из- за того что некоторые сообщения не забрали свои сообщения связь может быть приостановлена. Если каждое сообщение снабдить пометкой времени, то управляющая программа может периодически удалять старые сообщения.

Процессы могут быть остановлены в связи с тем, что другие сообщения не смогли послать им сообщения. Если время процессов регистрируется, то управляющая может периодически посылать им сообщения, что бы они ни ждали чересчур долго.

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

Основные достоинства почтовых ящиков:

1. процессу не нужно знать о существовании других процессов до тех пор пока он не получит сообщения от них;

2. два процесса могут обмениваться более чем одним сообщением за раз;

3. ОС может гарантировать, что ни какой процесс не вмешается во взаимодействие других процессов;

4. очереди буферов позволяют процессу- получателю продолжить работу, не обращая внимания на получателя.

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

Сейчас появляются механизмы подобные почтовым ящикам, но реализованные на принципах динамического выделения памяти под передаваемые сообщения.

19) Проектирование параллельных вычислительных процессов. Мониторы Хоара.

Необходим более сложный объект, который позволяет отслеживать большое число взаимосвязанных процессов и к ним относится монитор, предложенный Хааром.

Монитор - пассивный набор разделяемых переменных или повторно входимых процедур доступа к ним, которыми процессы пользуются в режиме разделения, причем в каждый момент им может пользоваться только 1 процесс.

Монитор – механизм организации параллелизма, который содержит как данные, так и процедуры, необходимые для реализации динамического распределения группы общих ресурсов. Процесс, желающий получить доступ к разделяемым переменным, должен обратиться к монитору, который либо предоставит доступ либо откажет в нем. При входе в монитор осуществляется взаимоисключение процессов, так чтобы в каждый момент времени только 1 процессу разрешается войти в монитор. Режимом ожидания монитора управляет сам монитор. При отказе в доступе, монитор блокирует обратившийся к нему процесс и определяет условие, по которому процесс ждет. Внутренние данные монитора могут быть либо глобальными либо локальными ко всем этим данных можно обращаться только из нутрии монитора. Если процесс обращается к некоторой процедуре монитора и обнаруживается что соответствующий ресурс уже занят, эта процедура монитора выдает команду ожидания с указанием условия ожидания. Процесс, переводящийся в режим ожидания должен ожидать ресурс вне монитора. Чтобы обеспечить, что процесс находящийся в ожидании некоторого ресурса со временем получит этот ресурс, ожидающему процессу присваивается более высокий приоритет, чем новому, пытающемуся войти в монитор.

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

20) Проектирование параллельных процессов. Алгоритм Деккера. Алгоритм Петерсона.

Алгоритм Деккера - первое известное корректное решение проблемы взаимного исключения.

Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критическую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов (индикаторов " намерения" войти в критическую секцию) и переменной turn (показывающей, очередь какого из процессов наступила).

Процессы объявляют о намерении войти в критическую секцию; это проверяется внешним циклом «while». Если другой процесс не заявил о таком намерении, в критическую секцию можно безопасно войти (вне зависимости от того, чья сейчас очередь). Взаимное исключение всё равно будет гарантировано, так как ни один из процессов не может войти в критическую секцию до установки этого флага (подразумевается, что, по крайней мере, один процесс войдёт в цикл «while»). Это также гарантирует продвижение, так как не будет ожидания процесса, оставившего «намерение» войти в критическую секцию. В ином случае, если переменная другого процесса была установлена, входят в цикл «while» и переменная turn будет показывать, кому разрешено войти в критическую секцию. Процесс, чья очередь не наступила, оставляет намерение войти в критическую секцию до тех пор, пока не придёт его очередь (внутренний цикл «while»). Процесс, чья очередь пришла, выйдет из цикла «while» и войдёт в критическую секцию.

+ не требует специальных Test-and-set инструкций, по этому легко переносим на разные языки программирования и архитектуры компьютеров

-Действует только для двух процессов

Алгоритм Петерсона — программный алгоритм взаимного исключения потоков исполнения кода.

Перед тем как начать исполнение критической секции кода (то есть кода, обращающегося к защищаемым совместно используемым ресурсам), поток должен вызвать специальную процедуру (назовем ее EnterRegion) со своим номером в качестве параметра. Она должна организовать ожидание потока своей очереди входа в критическую секцию. После исполнения критической секции и выхода из нее, поток вызывает другую процедуру (назовем ее LeaveRegion), после чего уже другие потоки смогут войти в критическую область. Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу. При этом одно из предложений всегда следует после другого. Тем самым работу в критическом участке продолжит процесс, которому было сделано последнее предложение.

21) Типовые задачи, требующие организации параллельных вычислительных процессов.

· Задача поставщик-потребитель. Суть: Пусть 2 процесса обмениваются информацией через буфер ограниченного размера. Производитель закладывает информацию в буфер, а потребитель извлекает ее. Если буфер полностью заполнен, то производитель должен ждать пока в нем освободится место. Если буфер пуст, потребитель должен ждать появления новой информации. Простейшая реализация производится с помощью 3 семафоров. Sзаполнен используется для организации ожидания производителя при заполненном буфере. Sсвободен используется для гарантии того, что потребитель будет ждать пока в буфере появится информация. Sвзаимодействия используется для организации взаимоисключения входа в критический участок. Критическим участком является занесение и извлечение информации. Должны быть введены счетчики свободных и заполненных буферов защищенных со стороны обоих процессов. Чтение нескольких процессов из дной ячейки невозможно и не нарушает целостности данных.

· Задача о парикмахерской. Суть: В парикмахерской имеется 3 кресла, 3 парикмахера и зал ожидания в котором 4 клиента могут располагаться на диване, а остальные – стоя. Правила пожарной безопасности ограничивают количество клиентов в помещении числом N. Клиент не может войти в парикмахерскую, если она полностью заполнена. Клиент, войдя в парикмахерскую, если есть свободное место на диване, то он должен сесть там. Если парикмахер освободился, к нему направляется один из наиболее долго ожидающих клиентов с дивана. Если имеются стоящие клиенты то тот, кто из них наиболее долго стоит садится на диван. Деньги за стрижку может принять любой парикмахер, и он должен внести их в кассу, которая одна. Рабочее время парикмахера разделяется на стрижку, принятие платы и «сон» в ожидании клиента. Для обеспечения синхронизации необходимо анализировать следующие условия:

1) Вместимость парикмахерской и вместимость дивана. За это соответственно отвечают Smax, Ssofa. Каждый раз при попытке войти клиента в парикмахерскую семафор Smax уменьшается на единицу, при выходе – увеличивается.

2) Емкость парикмахерских кресел Schair гарантирует обслуживание одновременно не более 3х клиентов. Клиент не поднимается с дивана, пока хотя бы одно кресло не свободно.

3) Размещение клиента в кресле Sready, которое сигнализирует о том, что парикмахер должен проснуться.

4) Удержание клиента в кресле Sfinish

5) Оплата стрижки: используется семафор Spay, который сигнализирует о передаче денег кассиру. Sresed – о получении счета на оплату, Scoord – координация действий кассира и парикмахера, который обеспечивает выполнение парикмахером в один момент времени только одной функции.

· Задача об обедающих философах. В одном пансионате собрано 5 обедающих философов, которые сидят за круглым столом. Перед каждым философом стоит тарелка со спагетти. Справа и слева от тарелки по вилке. Каждый философ может находится в 2х состояниях: размышлять или есть. Философ может приступить к еде только в том случае, если у него в руках две вилки. Вилку, вторую можно брать только у соседа справа, если она свободна. Необходимо ввести 4 семафора: состояние философа, состояние правой вилки, состояние левой вилки и состояние взаимоисключения.

Задача о курильщиках

Задача читатель – писатель

Другой классической задачей синхронизации доступа к ресурсам является задача «Читатель – писатель», иллюстрирующая широко распространенную модель совместного доступа к данным. Например, в системе, резервирующей билеты, множество конкурирующих процессов читают одни и те же данные. Однако, когда один из процессов начинает модифицировать данные, ни какой другой процесс не должен иметь доступа к этим данным, даже для чтения.

Задачу «Читатель-писатель» можно решать, исходя из следующих предположений.

1) Наибольший приоритет имеет читатель: в этом случае любому из

процессов – писателей запрещается вход в критическую секцию до тех пор,

пока в ней находится хотя бы один читающий процесс.

Процесс, ожидающий доступа по записи, будет ждать до тех пор, пока

все читающие процессы не окончат работу, и если в это время появляется но-

вый читающий процесс, он тоже беспрепятственно получит доступ. Чтобы

этого избежать, можно модифицировать алгоритм.

2) Наибольший приоритет имеет писатель. Тогда в случае, если имеется

хотя бы один ожидающий процесс-писатель, новые процессы-читатели не по-

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

Отрицательная сторона данного решения заключается в том, что ﾕ €  +__ оно не-

сколько снижает производительность процессов-читателей, так как вынуждает

их ждать в тот момент, когда ресурс не занят в эксклюзивном режиме.

22)Тупики. Понятие тупика. Системные и потребляемые ресурсы. Примеры тупиковых ситуаций.

При параллельном исполнении процессов могут возникать ситуации, при кото­рых два или более процесса все время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из двух процессов ожидает ре­сурс, занятый другим процессом. Из-за такого ожидания ни один из процессов не может продолжить исполнение и освободить в конечном итоге ресурс, необхо­димый другому процессу. Эта тупиковая ситуация называется дедлоком, тупиком или клинчем. Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ждет события, которое никогда не произойдет. Тупики чаще всего возникают из-за конкуренции несвязанных параллельных процессов за ресурсы вычислительной системы, но иногда к тупикам приводят и ошибки программирования.

При рассмотрении проблемы тупиков целесообразно понятие ресурсов системы обобщить и разделить их все на два класса — повторно используемые (или сис­темные) ресурсы (типа RR или SR reusable resource или system resource) и по­требляемые (или расходуемые) ресурсы (типа CR - consumable resource).

Повторно используемый ресурс (SR) есть конечное множество идентичных еди­ниц со следующими свойствами:

· число единиц ресурса постоянно;

· каждая единица ресурса или доступна, или распределена одному и только од­ному процессу (разделение либо отсутствует, либо не принимается во внима­ние, так как не оказывает влияния на распределение ресурсов, а значит, и на возникновение тупиковой ситуации);

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

Данное определение выделяет существенные для изучения проблемы тупика свойства обычных системных ресурсов, к которым мы относим такие компонен­ты аппаратуры, как основная память, вспомогательная (внешняя) память, периферийные устройства и, возможно, процессоры, а также программное и информационное обеспечение, такое как файлы данных, таблицы и «разрешение войти в критическую секцию».

Расходуемый ресурс (CR) отличается от ресурса типа SR в нескольких важных отношениях:

· число доступных единиц некоторого ресурса типа CR изменяется по мере того, как приобретаются (расходуются) и освобождаются (производятся) от­дельные их элементы выполняющимися процессами, и такое число единиц ресурса является потенциально неограниченным; процесс «производитель» увеличивает число единиц ресурса, освобождая одну или более единиц, кото­рые он " создал";

· процесс «потребитель» уменьшает число единиц ресурса, сначала запрашивая и затем приобретая (потребляя) одну или более единиц. Единицы ресурса, которые приобретены, в общем случае не возвращаются ресурсу, а потребля­ются (расходуются). Эти свойства потребляемых ресурсов присущи многим синхронизирующим сигналам, сообщениям и данным, порождаемым как аппаратурой, так и программным обеспечением, и могут рассматриваться как ресурсы типа CR при изучении тупиков. В их число входят: прерывания от таймера и устройств ввода/вывода; сигналы синхронизации процессов; сооб­щения, содержащие запросы на различные виды обслуживания или данные, а также соответствующие ответы.

Для исследования параллельных процессов и, в частности, проблемы тупиков было разработано несколько моделей. Одной из них является модель повторно используемых ресурсов Холта. Согласно этой модели система представляет­ся как набор (множество) процессов и набор ресурсов, причем каждый из ресур­сов состоит из фиксированного числа единиц. Любой процесс может изменять состояние системы с помощью запроса, получения или освобождения единицы ресурса.

Пусть имеются три процесса ПР1, ПР2 и ПРЗ, которые вырабатывают соответ­ственно сообщения Ml, M2 и МЗ. Эти сообщения представляют собой ресурсы типа CR. Пусть процесс ПР1 является «потребителем s> сообщения МЗ, процесс ПР2 получает сообщение Ml, а ПРЗ — сообщение М2 от процесса ПР2, то есть каждый из процессов является и «поставщиком» и «потребителем» одновременно, и вместе они образуют «кольцевую» систему (рис. 2) передачи сообщений че­рез почтовые ящики (ПЯ). Если связь с помощью этих сообщений со стороны каждого процесса устанавливается в порядке, изображенном в листинге 1, то никаких трудностей не возникает. Однако перестановка этих двух процедур в каждом из процессов (листинг 2) вызывает тупик

Рис. 2 Кольцевая схема взаимодействия процессов

Пусть некоторый процесс ПР1 должен обменяться сообщениями с процессом ПР2 и каждый из них запрашивает некоторый ресурс R, причем ПР1 требует три еди­ницы этого ресурса для своей работы, а ПР2 — две единицы и только па время обработки сообщения. Всего же имеются только четыре единицы ресурса R. За­прос ресурса можно реализовать через соответствующий монитор с процедурами REQUEST(R, N)— запрос N единиц ресурса R и RELEASE(R, N) — освобождение, возврат N единиц ресурса R. Обмен сообщениями будем осуществлять через почтовый ящик M. Фрагменты программ ПР1 и ПР2 приведены в листинге 3.

Эти два процесса всегда будут попадать в тупик. Процесс ПР2, если будет вы­полняться первым, сначала ожидает сообщения от процесса ПР1, после чего будет заблокирован при запросе ресурса R, часть которого будет уже отдана ПР1. Процесс ПР1, завладев частью ресурса R, будет заблокирован на ожидании отве­та от ПР2, которого никогда не получит, так как для этого ПР2 нужно получить ресурс R, находящийся в распоряжении ПР1. Тупика можно избежать лишь при условии, что на время ожидания ответа от ПР2 процесс ПР1 будет отдавать хотя бы одну единицу ресурса R, которыми он сейчас владеет. В данном примере, как и в предыдущем, причиной тупика являются ошибки программирования.

23) Тупики. Методы борьбы с тупиками. Предотвращение тупиков.

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

Доказано, что для возникновения ситуации взаимоблокировки должны выполняться 4 условия:

Условие взаимного исключения – при котором процессы осуществляют монопольный доступ к ресурсам

Условие ожидания – когда процессы, в данный момент времени удерживающие полученные ранее ресурсы, могут запрашивать новые ресурсы и ожидать их освобождения или выделения

Условие отсутствия перераспределения – когда у процесса нельзя принудительным образом забрать ранее полученные ресурсы, процесс владеющий ими должен сам освободить эти ресурсы

Условие циклического ожидания – когда существует круговая последовательность из 2 или более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.

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

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

I – Страусовый алгоритм – никак не борются с тупиками

II – Предотвращение тупика с помощью опровержения одного из 4 условий, необходимых для взаимоблокировки

III – Обход тупиковых ситуаций с помощью аккуратного распределения ресурсов

IV – Обнаружение тупиков с последующим восстановлением - когда система позволяет взаимоблокировке произойти, обнаруживает ее и предпринимает какие либо действия.

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

Предотвращение можно рассматривать как запрет существования опасных состоя­ний. Поэтому дисциплина, предотвращающая тупик, должна гарантировать, что какое-либо из четырех условий, необходимых для его наступления, не может возникнуть.

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

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

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

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

Пусть имеются процессы ПР1 и ПР2, которые могут иметь доступ к ресурсам R1 и R2, причем R2 находится на более высоком уровне иерархии. Если ПР1 захватил R1, то ПР2 не может захватить R2, так как доступ к нему проходит через доступ к R1, который уже захвачен ПР1. Т.о., создание замкнутой цепи исключается. Иерархическое выделение ресурсов час­то не дает никакого выигрыша, если порядок использования ресурсов, опреде­ленный в описании процессов, отличается от порядка уровней иерархии. Тогда ресурсы будут использоваться крайне неэффективно.

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

В целом стратегия предотвращения тупиков — это очень дорогое решение про­блемы, и она используется нечасто.

24) Тупики. Методы борьбы с тупиками. Обход тупиков.

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

Доказано, что для возникновения ситуации взаимоблокировки должны выполняться 4 условия:

1) Условие взаимного исключения – при котором процессы осуществляют монопольный доступ к ресурсам

2) Условие ожидания – когда процессы, в данный момент времени удерживающие полученные ранее ресурсы, могут запрашивать новые ресурсы и ожидать их освобождения или выделения

3) Условие отсутствия перераспределения – когда у процесса нельзя принудительным образом забрать ранее полученные ресурсы, процесс владеющий ими должен сам освободить эти ресурсы

4) Условие циклического ожидания – когда существует круговая последовательность из 2 или более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности

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

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

I – Страусовый алгоритм – никак не борются с тупиками

II – Предотвращение тупика с помощью опровержения одного из 4 условий, необходимых для взаимоблокировки

III – Обход тупиковых ситуаций с помощью аккуратного распределения ресурсов

IV – Обнаружение тупиков с последующим восстановлением - когда система позволяет взаимоблокировке произойти, обнаруживает ее и предпринимает какие либо действия.

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

Небезопасное состояние само по себе не является тупиком, потому что возможно успешное завершение процессов. Разница между безопасным и небезопасным состояниями заключается в следующем:

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

Классическое решение этой задачи известно как алгоритм банкира Дейкстры. Алгоритм банкира напоминает процедуру принятия решения, может ли банк без­опасно для себя дать взаймы денег. Принятие решения основывается на инфор­мации о потребностях клиента (текущих и максимально возможных) и учете те­кущего баланса банка. Несмотря на то, что этот алгоритм нигде практически не используется, рассмотрим его, так как он интересен с методической и академиче­ской точек зрения. Текст программы алгоритма банкира приведен в листинге 4.

Пусть существует N процессов, для каждого из которых известно максимальное количество потребностей в некотором ресурсе R (обозначим эти потребности через Мах(i). Ресурсы выделяются не сразу все, а в соответствии с текущим запро­сом. Считается, что все ресурсы i-го процесса будут освобождены по его завер­шении. Количество полученных ресурсов для i-го процесса обозначим Получ(i). Остаток в потребностях i-гo процесса на ресурс R обозначим через Остаток(i). Признак того, что процесс может не завершиться — это значение false для пере­менной Заверш(i). Наконец, переменная Своб_рес будет означать количество сво­бодных единиц ресурса R, а максимальное количество ресурсов в системе опре­делено значением Всего_рес.

Каждый раз, когда какой-то остаток может быть выделен из числа остающихся незанятыми ресурсов, предполагается, что соответствующий процесс работает, пока не окончится, а затем его ресурсы освобождаются. Если в конце концов все ресурсы освобождаются, значит, все процессы могут завершиться и система на­ходится в безопасном состоянии. Другими словами, согласно алгоритму банкира система удовлетворяет только те запросы, при которых ее состояние остается на­дежным. Новое состояние безопасно тогда и только тогда, когда каждый процесс все же может окончиться. Именно это условие и проверяется в алгоритме банкира. Запросы процессов, приводящие к переходу системы в ненадежное состоя­ние, не выполняются и откладываются до момента, когда его нее же можно будет выполнить.

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

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

· Алгоритм исходит из того, что количество распределяемых ресурсов в систе­ме фиксировано, постоянно. Иногда это не так, например вследствие неис­правности отдельных устройств

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

· Алгоритм требует, чтобы число работающих процессов оставалось постоян­ным. Это возможно только для очень редких случаев. Очевидно, что выпол­нение этого требования в общем случае не реально, особенно в мультитерминальных системах либо если пользователь может запускать по несколько процессов параллельно.

25) Тупики. Методы борьбы с тупиками. Обнаружение тупиков.

Чтобы распознать тупиковое состояние, необходимо для каждого процесса определить, сможет ли он когда-либо снова развиваться, то есть изменять свои со­стояния. Так как нас интересует возможность развития процесса, а не сам про­цесс смены состояния, то достаточно рассмотреть только самые благоприятные изменения состояния. Очевидно, что незаблокированный процесс (он только что получил ресурс и по­этому не заблокирован) через некоторое время освобождает все свои ресурсы и затем благополучно завершается. Освобождение ранее занятых ресурсов может «разбудить» некоторые ранее заблокированные процессы, которые, в свою оче­редь, развиваясь, смогут освободить другие ранее занятые ресурсы. Это может продолжаться до тех пор, пока либо не останется незаблокированных процессов, либо какое-то количество процессов все же останется заблокированными. В по­следнем случае (если существуют заблокированные процессы при завершении указанной последовательности действий) начальное состояние S является состоя­нием тупика, а оставшиеся процессы находятся в тупике в состоянии S. В про­тивном случае S не есть состояние тупика.

· Обнаружение тупика посредством редукции графа повторно используемых ресурсов

· Методы обнаружения тупика по наличию замкнутой цепочки запросов

· Алгоритм обнаружения тупика по наличию замкнутой цепочки запросов

26) Ресурсы. Доступ к файлам как частный случай доступа к разделяемым ресурсам. Механизм контроля доступа.

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

Различают 2 основных подхода к определению прав доступа:

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

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