Многозадачность и операционная система

Подробности

Родительская категория: Память. Верхний уровень

Категория: Многозадачность

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

Рассмотрим методы планирования и диспетчерирования. Различают несколько видов планирования (см. таблица ниже).

Виды планирования

Задача (поток) в процессе жизни в ОС может находиться в одном из состояний:

• Ready (готова) — готова к выполнению;
• Standby (простаивает) — выбрана следующей для выполнения на конкретном процессоре, диспетчер переключит контекст на эту задачу;
• Running (выполняется) — задача выполняется до момента:
  -Завершения;
  -Вытеснения задачей с более высоким приоритетом;
  -Самостоятельного перехода в состояние ожидания;
  -Окончания выделенного кванта времени.
• Waiting (ожидает) — задача переходит в это состояние самостоятельно на синхронизирующем объекте или по команде ОС, по окончании ожидания задача переходит в состояние Running или Ready;
• Transition (переходное состояние) — стек задачи выгружен из памяти, при загрузке переходи в состояние Ready;
• Terminated (завершена) — заканчивается выполнение, может удаляться из памяти;
• Initialized (инициализирована) — загужена из ROM или винчестера.

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

Initialized — Ready — Standby — Running — Terminated. Более полно схема прохождения задачи по состояниям показана на рисунке (Win 2000 — см. рисунок ниже).

Схема продвижения задачи по состояниям

Способы планирования

Подробности

Родительская категория: Память. Верхний уровень

Категория: Многозадачность

1. Невытесняемое планирование. Новая задача переходит в состояние Running, если предыдущая задача закончила свое выполнение или перешла в состояние Waiting.

2. Посностью вытесняемое планирование (см. рисунок ниже). Задача вытесняется задачей с более высоким приоритетом. Така ситуация может быть в двух случаях: пришла задача большего приоритета или приоритет текущей задачи понизился. Когда задача вытесняется она встает в очередь готовых задач соответствующего уровня приоритета. На рисунке задача (поток) с приоритетом 18 выходит из состояния ожидания и захватывает процессор, вытесняя выполняемую в этот момент задачу (с приоритетом 16) в очередь готовых потоков. Заметьте, что вытесненная задача помещается не в конец, а в начало очереди. После завершения вытеснившей задачи вытесненная сможет отработать остаток своего времени.

Полностью вытесняемое планирование

3. Круговое планирование. Используется операция уступить новой задаче. Такое планирование может применяться для задач одного приоритета.

4. Завершение кванта. Каждой задаче выделяется квант времени. По окончании выполняется другая задача с текущим уровнем приоритета. Если такой нет, то второй квант времени выполняется первая задача. Вытесненная задача ставится в очередь задач данного приоритета (см. рисунок ниже) и переводится из состояния Running в состояние Ready. В Win 2000 у каждой задачи (потока) свое значение кванта. Это значение выражается не в единицах времени, а целым числом в так называемых квантовых единицах. Минимальный квант (6 единиц) по умолчанию равен двум интервалам системного таймера. Максимальный соответствует 36 единиц. Длительный квант в ряде случаев позволяет свести к минимому переключения контекста. Получая больший квант программы обслуживания клиентского запроса (в серверах) имеют больше шансов выполнить запрос и вернуться в состояние ожидания до истечения выделенного кванта. Длина временного интервала таймера зависит от аппаратной платформы и на большинстве однопроцессорных х86систем составляет 10 мс, а на бльшинстве многопроцессорных систем — 15 мс. Величиной выделенного кванта можно управлять, в частности динамически приращивая квант при круговом планировании.

Завершение кванта

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

6. Планирование по расписанию. Данное планирование предполагает использование комбинации разных способов.

Адаптивное планирование

Распределение приоритетов. Контекст. Переключение контекста.

Подробности

Родительская категория: Память. Верхний уровень

Категория: Многозадачность

Распределение приоритетов

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

Приоритеты потоков Windows 2000 повышает в следующих случаях:

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

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

Распределение приоритетов задач

 

Контекст. Переключение контекста

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

В типичном случае полный контекст включает следующие данные:

• счетчик команд,
• регистр состояния процессора (регистр флагов),
• содержимое остальных регистров процессора,
• указатели на стеки ядра ОС и пользователя,
• указатели на адресное пространство задачи (см. каталог таблиц страниц CR3 для х86),
• промежуточные результаты работы программы.

Переключение контекста позволяет из памяти загрузить в процессор на выполнение новую задачу, а информацию о старой сохранить. Объем контекста 32-разрядного процессора составляет 64 байта и более. Объем контекста RISC процессора значительно больше, так в процессоре Itanium число 64-разрядных регистров около 500. Ряд задач не требуют сохранения полного контекста, достаточно сохранить/ восстановить счетчик команд и регистр состояния процессора. Такими задачами могут быть задачи обслуживания прерываний клавиатуры, таймера и др. В этом случае размер контекста 8 байт (два слова).

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

Планирование потоков в системах с симметричной мультипроцессорной обработкой

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

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

Если в момент прихода задачи (переход в состояние Ready) все процессоры заняты, проверяетcя, нельзя ли вытеснить задачу на одном из процессоров. Какой процессор рассматривается в первую очередь? Сначала идеальный, затем — остальные.