Понятие моделирования и типы моделей

Тупики

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

Рис. 5.3

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

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

а) процесс P 1 запрашивает ресурс типа R 1; стрелка от P 1 доходит только до большого кружка, что означает, что в текущий момент запрос от процесса на выделение данного ресурса находится в стадии рассмотрения; б) ресурс типа R 2 выделяется процессу P 2 (стрелка от маленького кружка, находящегося внутри большого кружка R 2, до квадрата P 2); в) процесс Р 3 запрашивает ресурс R 3, который выделен процессу P 4; ситуация приближается к потенциальному тупику; г) классическая тупиковая ситуация; процессу P 5 выделен ресурс R 5, необходимый процессу P 6, которому выделен ресурс R 4, необходимый процессу P 5 («круговое ожидание»).

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

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

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

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

Рис. 5.4. Редукция графа

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

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

Разработчиками операционных систем были сформулированы следующие необходимые условия наличия тупика:

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

− процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (условие ожидания ресурсов);

− ресурсы нельзя отобрать у процессов, удерживающих их, пока эти ресурсы не будут использованы для завершения работы (условие неперераспределяемости);

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

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

В проблеме тупиков можно выделить четыре основных направления:

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

− обход тупиков;

− обнаружение тупиков;

− восстановление после тупиков.

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

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

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

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

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

Для предотвращения тупиков в 1969 г. одним из сотрудников фирмы IBM J. W. Havender было предложено 3 стратегических принципа.

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

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

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

Сложность восстановления системы после тупиковой ситуации обусловливается рядом факторов:

- неочевидность того, что система попала в тупиковую ситуацию;

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

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

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

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

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

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

Контрольные вопросы

1. Понятие архитектуры иерархической операционной системы.

2. Определение процесса в иерархической операционной системе.

3. Определение операции в операционной системе.

4. Понятие планирования в иерархии уровней ОС.

5. Структура планировщика.

6. Механизм планирования.

7. Основные блоки операционной системы.

8. Эффективность, показатель эффективности, определение оптимальной системы.

9. Понятие критической области.

10. Типы отношения предшествования.

11. Семафор, операции синхронизации.

12. Понятие тупика.

13. Необходимые условия наличия тупика.

14. Основные направления решения проблемы тупиков.

ГЛАВА 6. ФОРМАЛЬНАЯ МОДЕЛЬ ОПЕРАЦИОННОЙ СИСТЕМЫ

Модель − это физическая или абстрактная система, адекватно представляющая собой объект исследования.

Физические модели образуются из совокупности материальных объектов, причем природа применяемых в модели материальных элементов не обязательно та же, что и в исследуемом объекте.

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

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

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

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

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

Дата добавления: 2014-12-29