Главная цель – максимальная загрузка ЦП, минимизация простоев. Максимальная пропускная способность – к-во задач / единицу времени.
Перед началом работы формируется пакет заданий, каждое из которых содержит требования к системным ресурсам. Из этого пакета на одновременное выполнение выбираются задачи, предъявляющие разные требования к ресурсам, что обеспечивает сбалансированную загрузку ЦП.
Выбирается самое выгодное задание – невозможно гарантировать выполнение задания за какой-то определенный промежуток времени.
Способы совмещения работы ЦП и ввода-вывода:
1) Канальный – у компа есть свой проц ввода-вывода (канал). Он умеет выполнять свои операции. ЦП дает ему параметры и указывает, какую именно инструкцию надо выполнить, после чего они работают параллельно.
2) На основе контроллеров. Внешние устройства управляются собственными контроллерами. Контроллер отрабатывает команды, поступившие от ЦП, но делает это медленнее, чем ЦП (т.к. устройства внешние - электромеханические). За счет этого достигается параллелизм.
Переключение с задачи на задачу в системах пакетной обработки – невытесняющее, по инициативе самой задачи, которая добровольно отказывается от процессора, когда ей нужно устройство ввода – вывода.
Задача может надолго занять процессор – это снижает эффективность работы пользователя, но повышает эффективность использования аппаратуры.
Системы разделения времени
Цель – удобство работы пользователя.
Одному или нескольким юзерам предоставляется возможность работать сразу с несколькими приложениями. Поэтому время работы каждого приложения ограничивается – ОС приостанавливает его выполнение по истечении кванта процессорного времени.
Т.о. ни одна задача не занимает ЦП надолго, и время ответа приложения остается приемлемым для юзера, который общается с системой через терминал. У всех пользователей складывается впечатление, что они используют систему единолично.
Такие системы обладают меньшей пропускной способностью, производительность системы снижается из-за более частых переключений процессора.
Системы реального времени
Предназначены для управления разными техническими объектами (спутники, станки, и тд). Существует предельно допустимое время, в течение которого должна быть выполнена та или иная задача. Иначе возникнет сбой с тяжелыми последствиями.
Критерий эффективности – способность выдерживать заранее заданные интервалы между запуском программы и получением результата – реактивность системы.
В системах реального времени мультипрограммная смесь состоит из фиксированного набора заранее разработанных программ (с известным временем их выполнения).
Запуск задач на выполнение осуществляется по прерываниям:
- либо исходя из текущего состояния объекта
- либо по плановому расписанию
Скорость ответа системы зависит от скорости обработки прерываний (опрос тысячи потенциальных устройств не подойдет). Это главный критерий выбора процессора для такой системы.
Загружать процессор по максимуму в этих системах нельзя, нужно оставлять запас вычислительной мощности на случай непредвиденной пиковой нагрузки. То, что вероятность ее возникновения крайне мала – здесь не аргумент, т.к. именно в этот момент больше всего понадобится адекватная реакция системы, от которой будет зависеть слишком многое (пример – зашкаливание датчиков при аварии на АЭС).
Понятия процесса и потока. Состояния потока. Планирование и диспетчеризация потоков в многопоточных системах (с использованием не вытесняющих алгоритмов, на основе квантования, на основе приоритетов, смешанные алгоритмы планирования).
Понятие процесса и потока
Процесс – деятельность ОС, связанная с выполнением программы и собственно выполнение этой программы.
Процесс – сущность, рассматриваемая как единица работы ОС.
Процесс – это динамичное понятие. Одна программа, запущенная дважды – это два процесса. Программа – понятие статичное.
Поток – это поток команд, выполняемый процессором.
Это сущность, которая используется системой для распределения процессорного времени.
Все ресурсы в системе, кроме процессорного времени, выделяются для процесса:
- память
- адресное пространство
- возможность доступа к файлам тд
Процессорное время выделяется потоку. Т.о мультипрограммирование реализовывается на уровне потоков, а не процессов.
Для создания процесса система создает ОПИСАТЕЛЬ ПРОЦЕССА – информационную структуру, содержащую все сведения о процессе: его id, приоритет, права доступа, данные о расположении в памяти его кода и данных.
После того, как создан новый описатель процесса, система принимает вновь появившийся процесс при планировании распределения своих ресурсов.
Для того, чтобы создать процесс, нужно загрузить коды и данные исполняемой программы в оперативную память (при использовании витруальной памяти в оперативную память загружается только часть процесса, остальные подкачиваются при необходимости.)
При создании процесса ОС создает для него как минимум 1 поток выполнения, для чего генерируется специальная структура – ОПИСАТЕЛЬ ПОТОКА. Сюда записывается информация о id потока, его приоритете, правах доступа и состоянии и тд. Вновь созданный поток находится в приостановленном состоянии и становится в очередь на выполнение в соответствии с определенными правилами системы.
При работе с процессами система использует понятия ДЕСКРИПТОР ПРОЦЕССА (он же описатель, см. выше) и КОНТЕКСТ ПРОЦЕССА.
· Дескриптор процесса содержит информацию, необходимую ядру в течение всего жизненного цикла процесса (не важно, в памяти он сейчас или выгружен из нее).
Дескрипторы объединяются в ТАБЛИЦУ ПРОЦЕССОВ, которая хранится в ядре. На основании информации из таблицы процессов осуществляется планирование и синхронизация процессов.
· Контекст процесса содержит более объемную и не такую важную информацию: содержимое регистров, указатели на открытые файлы и тд и тп.Контекст не хранится в области ядра, а выгружается на диск при необходимости (транзитный).
Состояния потока
ОС осуществляет планирование потоков в соответствии с их состоянием
Поток может находиться в одном из 3 основных состояний (есть еще и промежуточные)
1) Выполнение ( поток юзает процессор)
2) Готовность ( поток мог бы выполняться, но проц занят)
3) Ожидание или блокировка (потоку что-то надо: ждет данные, операцию ввода вывода или еще чего);
Переход из одного состояния в другое осуществляется в соотсветствии с алгоритмом планирования конкретной ОС.
Итак.
- Поток создан – в состоянии готовности, ждет очереди на выполнение.
- Поток выбран на выполнение – выполняется, пока сам не отдаст проц, или пока квант времени не истечет
- Потом – снова в готовность.
- Потоку понадобилась инфа – он идет в ожидание.
- Поток получил нужную инфу – он идет в готовность и в очередь.
Существует переходное состояние ПЕРВООЧЕРЕДНОЙ ГОТОВНОСТИ – когда поток готов получить ресурсы (между блокировкой и готовностью).
В состоянии выполнения может находиться только 1 поток (в однопроцессорной системе);
В ожидании и готовности – много. Тут процессы образуют очереди, организованные в виде однонаправленного списка. Это позволяет легко их переупорядочивать при необходимости.
Планирование и диспетчеризация потоков
От планирования потоков зависит эффективность работы системы. Критерии эффективности бывают разные (см. выше).
В самом общем случае алгоритмы планирования можно разделить
По степени централизации механизма планирования на:
- вытесняющие (preemptive) – поток выполняется, пока сам не решит отдать процессор другому
Есть плюсы:
- исключаются нерациональные прерывания программ в неудобное время
- нет проблем совместного использования данных
- более высокая скорость работы (не надо переключаться туда-сюда)
Но больше минусов
- неудобно для пользователя
- головная боль для программиста (ему нужно решать вопросы планирования, он должен быть очень высококвалифицированным)
Пример – файл-серверы NetWare
- невытесняющие (non-preeemptive) – решение о переключении процессора принимает ОС. Так работает большинство современных ОС, особенно пользовательских.
Невытесняющие алгоритмы планирования:
А) FIFO (First in first out) || FCFS (First come first served);
- Справедливо
- Просто
Но есть convoy effect – короткие процессы, выполняемые после длинных, увеличивают общее время ожидания.
Б) SJFS – shortest job first served – короткая задача обслуживается первой.
- без опережения (процесс не прерывается если уж пошел на исполнение)
- с опережением (прерывается, если появляется поток с еще более минимальным временем исполнения)
В) SRTF – shortest remaining time first – первым идет поток, которому меньше осталось.
- оптимален в системах реального времени
Оценка длины среднего периода активности вычисляется по формуле:
T (n + 1) = a*tn + (1 - a)*tn
T – текущее значение энного CPU burst
T (n + 1) – следующее его значение, которое мы предсказываем
А – коэффициент старения информации (от 0 до 1);
Вытесняющие алгоритмы планирования бывают разные:
- на основе квантования
- на основе приоритетов
- смешанные
1) Квантование – каждому потоку последовательно выделяется квант процессорного времени.
Смена потоков происходит при:
- поток завершился и покинул систему
- произошла ошибка
- поток перешел в заблокированное состояние
- поток исчерпал свой квант (переходит в состояние готовности)
Кванты бывают:
- одинаковые для всех потоков.
- разные
Длина кванта – q. Количество потоков – n. Поток ждет (n-1)*q времени. Чем больше потоков, тем больше ждет, но если квант достаточно маленький – это время ожидания все равно не заметно для пользователя. Обычно оно составляет десятки миллисекунд.
Но чем больше квант – тем больше вероятность, что поток все сделает в первом же цикле, и зависимость времени ожидания потока от времени выполения снижается. Если квант совсем большой – то система превращается в систему линейной обработки.
Кванты для одного потока бывают:
- фиксированной величины
- изменяться в течение жизни потока. (Например, сначала дают большой квант, а потом все меньше и меньше. Короткие задачи выполняются сразу, а длинные вычисления идут в фоновом режиме.)
Система может формировать несколько очередей готовых к выполнению потоков, в зависимости от того, сам ли поток отдал квант или его у него забрали (использован квант до конца или нет), и первыми брать на выполнение из очереди, где собрались потоки, недоиспользовавшие свои кванты.
При алгоритмах, основанных на квантовании, совершенно не учитывается предварительная инфа о задачах (длинные или короткие, важные или нет, сколько они будут использовать процессор, а сколько – устройства ввода-вывода).
Алгоритмы планирования, основанные на приоритетах
При приоритетном обслуживании каждый поток обладает изначально известной характеристикой – приоритетом.
Приоритет – число, характеризующее степень привилегированности потока при использовании процессорного времени. Чем выше приоритет – тем выше привилегии, тем меньше поток стоит в очередях.
Приоритет может быть целым, дробным, положительным, отрицаетельным, чем меньше – тем больше, чем больше – тем меньше и тд, в разных системах.
Приоритет потока непосредственно связан с приоритетом процесса, который назначался ему системой при его создании. Система при создании процесса, анализирует, системный он или пользовательский, каковы права пользователя, создавшего его, были ли явные указания на повышение приоритета – и на основании этого назначает потоку определнный приоритет.
Приоритеты бывают:
- фиксированные (один раз назначен – и до конца процесса не меняется)
- динамические (меняются в течение жизни потока)
- по инициативе юзера (он выполняет нужную команду) – в современных системах этого стараются избегать, повышать приоритеты потока могут только админы, и то в определенных пределах.
- по инициативе самого потока (обращается с вызовом к ОСи);
- по инициативе ОС в зависимости от ситуации в системе.
Приоритетное обслуживание бывает:
- с относительными приоритетами
Поток выбран и исполняется, хот гром греми.
Подходит для систем пакетной обработки
- с абсолютными приоритетами
Поток исполняется, пока в очереди не появится процесс с более высоким приоритетом.
Подходит для систем, где нужна быстрая реакция на событие.
Смешанные алгоритмы планирования
Используется как система квантования, так и система приоритетов. Например, в основе лежит квантование, но величина кванта и порядок выбора потока на исполнение определяется его приоритетами. Большинство ОС работают так.
13. Приоритеты и концепции планирования потоков в Windows 2000, ОС Unix System V и OS/2.
