 |
Планирование в интерактивных системах
|
|
|
|
Планирование в интерактивных системах
1. Циклическое планирование
Самый простой алгоритм планирования и часто используемый.
Каждому процессу предоставляется квант времени процессора. Когда квант заканчивается процесс переводится планировщиком в конец очереди. При блокировке процессор выпадает из очереди.
Преимущества:
- простота;
- справедливость (как в очереди покупателей, каждому только по килограмму).
Недостатки:
- если частые переключения (квант - 4мс, а время переключения равно 1мс), то происходит уменьшение производительности;
- если редкие переключения (квант - 100мс, а время переключения равно 1мс), то происходит увеличение времени ответа на запрос.
2. Приоритетное планирование
Каждому процессу присваивается приоритет и управление передается процессу с самым высоким приоритетом.
Приоритет может быть динамический и статический.
Часто процессы объединяют по приоритетам в группы и используют приоритетное планирование среди групп, но внутри группы используют циклическое планирование.
3. Группы с разным квантом времени.
Сначала процесс попадает в группу с наибольшим приоритетом и наименьшим квантом времени, если он использует весь квант, то попадает во вторую группу и т. д. Самые длинные процессы оказываются в группе наименьшего приоритета и наибольшего кванта времени.
Процесс, отвечающий на запрос, переходит в группу с наивысшим приоритетом.
Такой механизм позволяет повысить приоритет работы с клиентом.
4. Гарантированное планирование
В системе с n-процессами, каждому процессу будет предоставлено 1/n времени процессора.
Планирование в системах реального времени
|
|
|
Системы реального времени делятся на:
- жесткие (жесткие сроки для каждой задачи), например, управление движением;
- гибкие (нарушение временного графика не желательны, но допустимы), например, управление видео и аудио.
Внешние события, на которые система должна реагировать, делятся:
- периодические, например, потоковое видео и аудио;
- непериодические (непредсказуемые), например, сигнал о пожаре.
При общем планирование реального времени используется модель, когда каждый процесс борется за процессор со своим заданием и графиком его выполнения.
Планировщик должен знать:
- частоту, с которой должен работать каждый процесс;
- объем работ, который ему предстоит выполнить;
- ближайший срок выполнения очередной порции задания.
РАСПРЕДЕЛЕНИЕ РЕСУРСОВ
Концепция процесса преследует цель выработки механизма распределения и управления ресурсами. При разработке первых систем ресурсами считались процессорное время, память, каналы ввода-вывода, периферийные устройства.
Однако очень скоро понятие ресурса стало гораздо более универсальным и общим. Различного рода программные и информационные ресурсы также могут быть определены для системы как объекты, которые могут распределяться, и доступ к которым необходимо соответствующим образом контролировать.
В настоящее время понятие ресурса превратилось в абстрактную структуру с целым рядом атрибутов, характеризующих способы доступа к этой структуре и ее физическое представление в системе. Ресурсами стали называть и такие объекты, как сообщения и синхросигналы, которыми обмениваются задачи.
Классификация ресурсов.
1. По признаку реальности ресурсы делятся на физические и виртуальные (последние только в отдельных свойствах схожие с физическими ресурсами).
2. По возможности расширения свойств делятся на эластичные и жесткие (не допускающие виртуализации).
|
|
|
3. По степени активности разделяются на пассивные и активные (могут выполнять действия по отношению к другим ресурсам).
4. По времени существования: постоянные (доступны во все время процесса и до, и после его работы) и временные.
5. По степени важности: основные и второстепенные (допускают альтернативное развитие процесса при их отсутствии).
6. По функциональной избыточности при распределении: дорогой, не предоставляемый быстро, и дешевый, но предоставляемый с ожиданием.
7. По структуре: простые (не содержит составных элементов) и составные. Они различаются числом состояний: простой может быть только в двух состояниях — доступен или занят.
8. По характеру использования распределяемых ресурсов: потребляемые и воспроизводимые ресурсы (допускают многократное использование и освобождение).
9. По характеру использования: выделенными и разделяемыми (используются несколькими процессами).
10. По форме реализации: жесткие (в принципе не допускают копирования) и мягкие (допускают тиражирование и подразделяются на программные и информационные ресурсы).
Форма распределения ресурсаопределяет порядок использования многими процессами того или иного ресурса, который в каждый момент времени может обслуживать только один процесс.
Традиционная последовательность событий при работе с ресурсом состоит из запроса, использования и освобождения ресурса. Тип запроса зависит от природы ресурса и от ОС.
Однако в некоторых случаях могут возникнуть непредвиденные затруднения. Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое может вызвать только другой процесс данного множества. Так как все процессы чего-то ожидают, то ни один из них не сможет инициировать событие, которое разбудило бы другого члена множества и, следовательно, все процессы будут спать вместе.
Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация или «зависание системы» является следствием того, что один или более процессов находятся в состоянии тупика. Иногда подобные ситуации называют взаимоблокировками.
|
|
|
Тупики могут иметь место в разных ситуациях. Например, в системах управления базами данных записи могут быть локализованы процессами, чтобы избежать состояния гонок. В этом случае может получиться так, что один из процессов заблокировал записи, необходимые другому процессу, и наоборот. Таким образом, тупики могут иметь место, как на аппаратных, так и на программных ресурсах.
Тупики также могут быть вызваны ошибками программирования. Например, процесс может напрасно ждать открытия семафора, потому что в некорректно написанном приложении эту операцию забыли предусмотреть. Другой причиной бесконечного ожидания может быть дискриминационная политика по отношению к некоторым процессам. Однако чаще всего событие, которого ждет процесс в тупиковой ситуации, – освобождение ресурса, поэтому в дальнейшем будут рассмотрены методы борьбы с тупиками ресурсного типа.
Условия возникновения тупиков.
1. Условие взаимоисключения. Одновременно использовать ресурс может только один процесс.
2. Условие ожидания ресурсов. Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.
3. Условие неперераспределяемости. Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.
4. Условие кругового ожидания. Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.
Для образования тупика необходимым и достаточным является выполнение всех четырех условий.
|
|
|
