Микроядерная архитектура ОС.

Архитектура ОС.

 

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

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

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

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

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

Привилегированные программные модули не могут быть прерваны во время своего выполнения, т. е. они работают при отключённой системе прерываний. Такие модули, начав работать, выполняются до конца.

Реентерабельные программные модули допускают повторное многократное прерывание своего выполнения и повторный их запуск, причём при каждом таком прерывании происходит запоминание промежуточных результатов в некоторой специально отведённой для этого области памяти. Такие модули обычно состоят из трёх секций. Первая секция предназначена для выделения памяти под промежуточные результаты выполнения. Вторая секция представляет собой непосредственный код программного модуля. Третья секция – это секция освобождения памяти, которая использовалась для хранения промежуточных результатов. Первая и третья секции работают как привилегированные секции, а вторая – как непривилегированная. Примерами реентерабельных модулей являются ряд драйверов из состава ОС.

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

 

 

Привилегированный режим.

 

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

 

 

Польз. Режим                                           Польз. режим

 

                              Режим ядра                                                                                                         

 

                      t1                            t2

 

Потеря производительности связана с тем, что на переход из пользовательского режима в привилегированный и обратно тратится определённое время (интервалы t1 и t2). Чем больше в пользовательской программе системных вызовов, тем больше таких переходов.

 

8. Структура ядра ОС. Микроядерная архитектура ядра ОС.

Структура ядра ОС

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

1. Средства аппаратной поддержки ОС.

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

2. Машиннозависимые компоненты ОС.

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

3. Базовые механизмы ядра.

Модули этого слоя выполняют простые (примитивные) операции (переключение процессов, перемещение станиц в оперативной памяти, диспетчеризация прерываний).

4. Менеджеры ресурсов.

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

5. Интерфейс системных вызовов.

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

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

- информация по идентификации задачи (имя задачи, тип задачи);

- информация о ресурсах, которые необходимы задаче для её выполнения и о ресурсах, которые используются в настоящее время (идентификаторы необходимых внешних устройств);

- информация о текущем состоянии задачи (содержимое некоторых регистров процессора);

- информация о родственных связях задачи (имена родительского процесса и процессов-предков);

- информация, необходимая для целей планирования и диспетчеризации (адресные ссылки на соседние дескрипторы, находящиеся в той же очереди, приоритет задачи, ссылки на объекты синхронизации).

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

10. Дисциплины диспетчеризации.

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

1. FCFS (first come – first served – первым пришёл, первым обслужился) – прежде процессор получает та задача, которая раньше перешла в состояние готовности. Данная дисциплина проста в реализации, равноправна по отношению как к “длинным ” так и к “коротким” процессам, среднее время пребывания в очереди готовности весьма значительное.

2.  SJN (shortest job next – следующий с кратчайшим заданием) – прежде процессор получает та задача, которая имеет минимальное заказное время обслуживания. Данная дисциплина требует, чтобы для каждой задачи была известна оценка потребности в машинном времени, значение которой задаётся как параметр задачи. Такая дисциплина более сложна в реализации по сравнению с FCFS, она дискриминационна по отношению к “длинным процессам”, среднее время пребывания в очереди готовности меньше чем для FCFS. SJN имеет существенный недостаток. Задачи, которые были временно заблокированы (например, ожидали завершения ввода/вывода), в результате попадут в конец очереди готовности, даже если для их выполнения требуется небольшое процессорное время.

3. SRT (shortest remaining time) – прежде процессор получает задача, которая имеет меньше всего времени для своего завершения. Это время определяется как разность между заказанным временем обслуживания и тем процессорным временем, которая задача уже получила. SRT свободна от недостатка, характерного для SJN. SRT сложна в реализации и дискриминационна по отношению к “длинным” процессам.

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

4. RR (round robin) – циклическая (карусельная) дисциплина. Диспетчер выделяет готовой к выполнению задаче некоторый квант процессорного времени (интервал мультиплексирования). Если задача не успевает выполниться в течение этого кванта, диспетчер переводит её обратно в конец очереди готовности и выделяет следующий квант процессорного времени для другой готовой задачи. Данная дисциплина является дискриминационной по отношению к длинным процессам. Её удобно использовать в многопользовательских вычислительных системах, где требуется обслуживать большое число запросов, поступающих с различных рабочих станций системы.

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

6. Дисциплины на основе динамических приоритетов задач. Для каждой задачи задаётся начальное значение приоритета, которое затем изменяется во времени. Таким образом, приоритет задачи есть функция времени. Конкретный вид таких функций может быть разный, но общая их направленность состоит в том, что, чем дольше задача находится в очереди готовности, тем выше становится её приоритет. Это позволяет гарантировать обслуживание как коротких так и длинных процессов.

7. Дисциплины с несколькими очередями. Диспетчер поддерживает несколько очередей готовых к выполнению задач. Каждая очередь обслуживается по своей дисциплине. Такой диспетчер сложен в реализации, так как в его составе должен быть дополнительный механизм переключения с одной очереди готовности на другую. Более простой способ реализации диспетчера (статический) предполагает, что задача попав в некоторую очередь готовности, там и остаётся до своего полного выполнения. Более сложным способом реализации (динамическим) является способ, при котором задача может переходить из одной очереди готовности в другую на интервале своего существования.

11. Память и отображения. Виртуальное адресное пространство.

Операционная система

	Физические адреса

 

При изучении данного вопроса необходимо выделить четыре возможных варианта отображения.

При первом варианте предполагается, что виртуальное адресное пространство тождественно физическому адресному пространству. Поэтому, система программирования целиком реализует отображение логических имён в физические адреса. Этот случай характерен для отображения так называемых “абсолютных программ”. В командах таких программ в явном виде указываются их физические адреса и физические адреса операндов. Задача операционной системы сводится к обычной загрузке в память по указанным адресам.

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

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

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

12. Распределение ОП разделами.

Распределение разделами.

Та часть оперативной памяти, которая предназначена для хранения пользовательских задач и приложений, распределяется на несколько разделов. Каждый раздел предназначен для единовременного хранения кода и данных одной задачи. Загружаемой в оперативную память логической единицей является задача. Число разделов может быть различным в разные моменты работы вычислительной системы, но экспериментально доказано, что для того чтобы процессор был загружен на 90%, необходимо иметь в оперативной памяти 4-5 задач. Число задач одновременно загруженных в оперативную память называется коэффициентом мультипрограммирования. Существует несколько стратегий (дисциплин) распределения памяти разделами. Рассмотрим основные дисциплины.

Part 1

    part 2

Part 3

Part 4

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

T 1                                                        t 2                                                     t 3            

kernel		kernel		kernel
Task1		Task1		Task1
Task5		Task5		Task5
				Task6
Task4				Task7

                                                                                

T 4                                                  t 5                                                       t 6           

В момент t1 в памяти находятся коды четырёх задач. В момент t2 закончилось выполнение задачи task2 и планировщик освободил память, достаточную для загрузки задачи task5 (момент t3). В момент t4 закончилось выполнение задачи task3, планировщик освободил память, но размеры свободных областей недостаточны по размеру для загрузки задачи task6. Поэтому, очередная загрузка произойдёт только после выполнения task4 и соответствующего освобождения памяти (момент t5). При этом, размер свободной области памяти оказался достаточным для загрузки кодов сразу двух задач – task6 и task7 (момент t6).

Данная дисциплина распределения является средством локальной оптимизации, так как оптимизируется местоположение в памяти для конкретной задачи, но не распределение всей памяти в целом.

T 1                                                     t2                                                    t3

В момент t1 в памяти имеется две свободные области, но ни одна из них недостаточна по размеру, чтобы загрузить следующую задачу. Планировщик делает смещение кода задачи task4, образуя одну, большую по размеру, непрерывную свободную область памяти (момент t2). Поэтому появляется возможность загрузить следующую задачу task6 (момент t3).

Смещение в памяти кода задачи, которое выполняет планировщик, должно быть согласовано по времени с окончанием операции ввода/вывода для этой задачи (в данном случае – task4). Если такое согласование отсутствует, то результаты ввода/вывода могут записаться на “старое” место в памяти, и задача будет разрушена. С другой стороны, такое согласование противоречит принципам мультипрограммирования, в соответствии с которыми внешние устройства должны работать независимо и асинхронно относительно центрального процессора. Поэтому данная дисциплина распределения разделами не нашла практического применения.

13. Сегментная организация памяти.

Begin

If busy then WAIT (free);

Busy:= true;

Выдать ресурс;

End;

Procedure Release; (* освобождение *)

Begin

Взять ресурс;

Busy:= false;

SIGNAL (free);

End;

Begin

Busy:= false;

End.

Единственный ресурс динамически запрашивается и освобождается процессами, которые обращаются к процедурам Request и Release. Если процесс обращается к процедуре Request в тот момент, когда ресурс используется, значение переменной busy будет true и Request выполнит операцию WAIT(free). Эта операция заблокирует обратившийся процесс, и он будет помещён в конец очереди процессов, ожидающих доступа к монитору. Когда процесс, использующий ресурс, обратится к процедуре Release, операция монитора SIGNAL  деблокирует процесс, находящийся в начале очереди, не позволяя исполняться никакой другой процедуре внутри того же монитора. Этот деблокированный процесс готов возобновить выполнение процедуры Request.

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

Использование мониторов имеет ряд преимуществ по сравнению с низкоуровневыми средствами:

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

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

 

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

Борьба с тупиковыми ситуациями основывается на одной из трех стратегий:

- предотвращение тупика;

- обход тупика;

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

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

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

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

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

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

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

Распознавание тупика   основано на анализе модели распреде­ления ресурсов. Один из алгоритмов использует информацию о состоянии системы, содержащуюся в двух таблицах: таблиц: таблице текущего распределения (назначения) peсурсов RATBL и таблице заблокированных процессов PWTBL (для каждого вида ресурса может быть свой список заблокированных процессов). При каждом запросе на получение или освобождении ресурсов содержимое этих таблиц мо­дифицируется, а при запросе на ранее выделенный ресурс анализируется в соответствии со следующим алгоритмом:

1. Запрос от процесса Y на занятый ресурс I.

2. Поместить номер ресурса I в PWTBI. в строке с номером процесса Y.

3. Использовать I в качестве смешения a RATBL чтобынайти
помер процесса К, который владеет ресурсом.

4. ИспользоватьК в качестве смещения в PWTBL.

5. Проверить, ждет ли процесс К освобождения какого-либо ресурса I’. Если нет, то перейти к пункту 6, в противном случае - к пункту 7.

6. Перевести Y в состояние ожидания и выйти из алгоритма.

7. Использовать I’ в качестве смещения в RATBL, чтобы найти
номер блокирующего его процесса К'.

8. Проверить К' = Y? Если да, то перейти к пункту 9, в про­тивном случае - к пункту 11.

9. Проверить, вся ли таблица PWI'BL просмотрена. Если да, то переход к пункту 6, в противном случае – к пункту 10.

10. Присвоение К:= К' ипереход к пункту 4.

11. Вывод о наличии тупика.
12. Конец aлгоритма.

Для иллюстрации описанного алгоритма распознавания ту­пика рассмотрим следующую последовательность событий:

1.Пр1 занимает ресурс R1.

2.Пр2 занимает ресурс R3.

3.ПрЗ занимаетресурс R2.

4.Пр2 занимает ресурс R4.

5.Пр1 занимает ресурс R5.

В результате RATBL принимает вид:

Ресурсы    Процессы

1 1

2 3

3 2

4 2

5 1

б. Пусть Пр1 пытается занять R3. поэтому в соответствии с описанным алгоритмом - Y = 1, I =3, К =2, процесс K не ждет никакого ресурса I’, поэтому Пр1 блокируется по R3.

7. Далее, пусть Пр2 пытается занять R2; Y =2, I=2, К=3;
Процесс К не ждет никакого ресурса, поэтому Пр2 блокируется и R2.

8. И, наконец, пусть ПрЗ пытается получить R5; Y = 3, I=5, К=1, I'= 3, К'= 2, К'!= Y, поэтому берем К=2, I'=2, K'=3. В этом случае К'=Y, т.е. тупик определен. Таблица PWTBL имеет следующий вид:

   Процесс       Ресурс

1 3

2 2

3 5

Равенство Y=K’означает, что существует замкнутая цепь взаимоисключающих и ожидающих процессов, т. е. выполняются все четыре условия существования тупика.

Распознавание тупика требует дальнейшего восстановления. Восстановление модно интерпретировать как запрет постоянного пребывания в опасном состоянии. Существуй¹ следующие методы восстановления:

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

- перезапуск процессов, находящихся в тупике, с некоторой контрольной точки, т.е. из состояния, предшествовавшего запросу на ресурс;

- перераспределение ресурсов с последующим последовательным перезапуском процессов, находящихся в тупике.

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

 

22. Тупики. Примеры тупиков. Условия существования тупиков.

Понятие тупика, примеры тупиков, условия существования тупиков.

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

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

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

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

- каждая единица ресурса или доступна, или распределена одному и только одному процессу;

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

Примерами таких ресурсов являются компоненты аппаратуры (оперативная память, внешняя память, внешние устройства, процессор), а также программные и информационные компоненты (файлы, таблицы, переменные и т.п.).

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

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

- процесс типа “Производитель” увеличивает число единиц ресурса, освобождая одну или более единиц;

- процесс типа “Потребитель” уменьшает число единиц ресурса, сначала запрашивая а затем приобретая одну или более единиц.

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

Рассмотрим несколько примеров образования тупиков.

Пример тупика на ресурсах типа CR.

Пусть три процесса Пр1, Пр2, Пр3 вырабатывают сообщения М1, М2, М3 по кольцевой схеме. Процесс Пр1 является потребителем сообщения М3, процесс Пр2 должен получить сообщение М1, а Пр3 – М2. Таким образом, каждый из процессов одновременно является и “Поставщиком ” и “Потребителем”, и вместе они образуют кольцевую схему передачи сообщений друг другу. Если связь между процессами устанавливается в следующем порядке:

 

Прi:    send_message (Прk, Mi, Пяk);

            Wait_message (Прj, Mj, Пяi);

(где i=1, 2, 3 k=2, 3, 1 j=3, 1, 2), то никаких сложностей при взаимодействии процессов не возникает, и тупика не будет. Однако перестановка этих двух операций местами приводит к тупику:

Пр1:      wait_message(Пр3, М3, Пя1);

              Send_message(Пр2, М1, Пя2);

 

 Пр2:      wait_message(Пр1, М1, Пя2);

              Send_message(Пр3, М2, Пя3);

 

Пр3:      wait_message(Пр2, М2, Пя3);

              Send_message(Пр1, М3, Пя1);

 

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

Пример тупика на ресурсах типа CR и SR.

Пусть некоторый процесс Пр1 должен обменяться сообщениями с процессом Пр2 и каждый из них запрашивает некоторый ресурс R, причём Пр1 требует три единицы этого ресурса для своего выполнения, а Пр2 – две единицы и только на время обработки сообщения. Всего же у системы имеется только четыре единицы ресурса R. Запрос на ресурс R можно реализовать через процедуру монитора Request(R, N) – запрос N единиц ресурса R, и Release(R, N) – освобождение N единиц ресурса R. Обмен сообщениям