Интерактивные системы

3. Интерактивные системы

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

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

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

Достоинство: простота работы пользователя.

Недостаток: небольшая пропускная способность.

Алгоритмы:

1. Циклическое планирование

Самый простой алгоритм планирования и часто используемый (рис.3).

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

Преимущества

Простата

Справедливость (как в очереди покупателей, каждому только по килограмму)

Недостатки

Если частые переключения (малый квант - 4мс, а время переключения равно 1мс), то происходит уменьшение производительности.

Если редкие переключения (малый квант - 100мс), то происходит увеличение времени ответа на запрос.

2. Приоритетное планирование

Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом (рис.4).

Приоритет может быть динамический и статический.

Динамический приоритет может устанавливаться так:

П=1/Т,

где Т- часть использованного кванта

Если использовано 1/50 кванта, то приоритет 50.

Если использован весь квант, то приоритет 1.

Т.е. процессы ограниченные вводом/вывода, будут иметь приоритет над процессами ограниченными процессором.

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

3. Методы разделения процессов на группы

Группы с разным квантом времени (рис.5)

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

Процесс либо заканчивает работу, либо переходит в другую группу

Этот метод напоминает алгоритм - "Кратчайшая задача - первая".

Группы с разным назначением процессов (рис.6)

Процесс отвечающий на запрос, переходит в группу с наивысшим приоритетом.

Такой механизм позволяет повысить приоритет работы с клиентом.

4. Гарантированное планирование

В системе с n-процессами, каждому процессу будет предоставлено 1/n времени процессора.

5. Лотерейное планирование

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

6. Справедливое планирование

Процессорное время распределяется среди пользователей, а не процессов. Это справедливо если у одного пользователя несколько процессов, а у другого один.

4. Системы реального времени

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

Системы реального времени делятся на:

жесткие (жесткие сроки для каждой задачи) - управление движением

гибкие (нарушение временного графика не желательны, но допустимы) - управление видео и аудио

Внешние события на которые система должна реагировать, делятся:

периодические - потоковое видео и аудио

непериодические (непредсказуемые) - сигнал о пожаре

Что бы систему реального времени можно было планировать, нужно чтобы выполнялось условие:

m - число периодических событий

i - номер события

P(i) - период поступления события

T(i) - время, которое уходит на обработку события

Т.е. перегруженная система реального времени является не планируемой.

Алгоритмы:

1. Планирование однородных процессов

В качестве однородных процессов можно рассмотреть видео сервер с несколькими видео потоками (несколько пользователей смотрят фильм).

Т.к. все процессы важны можно использовать циклическое планирование.

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

2. Общее планирование реального времени

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

Планировщик должен знать:

частота, с которой должен работать каждый процесс

объем работ, который ему предстоит выполнить

ближайший срок выполнения очередной порции задания.