Распределение времени процессора.

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

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

Наиболее характерными критериями эффективности вычислительных систем являются:

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

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

· Реактивность системы – способность системы выдерживать заранее заданные интервалы времени между запуском программы и получением результата.

В зависимости от этого ОС делятся на:

· Системы пакетной обработки;

· Системы разделения времени;

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

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

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

Для пакетных ОС характерно совмещение операций ввода-вывода и вычислений. Такое совмещение может достигаться разными способами :

1. Специализированный процессор ввода-вывода.

Иногда такие процессоры называют каналами. Канал имеет систему команд, отличающуюся от системы команд центрального процессора. Эти команды специально ориентированы для управления внешними устройствами :

· установить магнитную головку;

· напечатать строку и т.д.

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

1. Внешние устройства управляются контроллерами.

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

Максимальный эффект при пакетной обработке достигается при наиболее полном перекрытии вычислений и ввода-вывода.

В случае одной задачи ускорение зависит от её характера. При преобладании вычислений или ввода-вывода ускорение практически отсутствует.

Системы разделения времени.

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

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

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

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

Мультипроцессорная обработка.

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

В настоящее время стало обычным явлением включение нескольких процессоров в архитектуру персонального компьютера.

Функции поддержки мультипроцессорной обработки данных имеются во многих ОС, в том числе и такой как Windows NT.

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

· к архитектуре;

· к способу организации вычислительного процесса.

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

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

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

В ассиметричной архитектуре процессоры могут отличаться как своими характеристиками, так и функциональной ролью, которая поручается им в системе.

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

Ассиметричное мультипроцессирование является наиболее простым способом организации. Этот способ иногда называют «ведущий - ведомый».

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

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

Симметричное мультипроцессирование как способ организации вычислительного процесса может быть реализовано только в системах с симметричной мультипроцессорной архитектурой.

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

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

Понятия процесса и потока

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

В ряде ОС определены два типа работы. Более крупная единица – процесс, которая требует для своей реализации несколько более мелких работ, и эта более мелкая единица называется потоком.

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

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

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

Для этих целей в ряде современных ОС используется механизм многопоточной обработки. При этом вводится новая единица работы – поток выполнения, а понятие «процесс» в некоторой степени меняет смысл.

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

При управлении процессами ОС использует два основных типа информационных структур:

· дескриптор процесса;

· контекст процесса.

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

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

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

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

Контекст, так же как и дескриптор, доступен только программам ядра, т.е. находится в виртуальном адресном пространстве ОС.

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

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

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

При планировании могут приниматься во внимание приоритет потоков, время их ожидания в очереди, накопленное время выполнения, интенсивность обращения к вводу-выводу и др. факторы.

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

Планирование потоков включает в себя решение двух задач:

· определение момента времени для смены текущего активного потока;

· выбор для выполнения потока из очереди готовых потоков.

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

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

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

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

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

Планировщик называется статическим, если он принимает решения о планировании не во время работы системы, а заранее.

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

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

Контекст отражает:

· состояние аппаратуры компьютера в момент прерывания потока: значение счетчика команд, содержимое регистров общего назначения, режим работы процессора, флаги, маски и другие параметры;

· параметры операционной среды (ссылки на открытые файлы, данные о незавершенных операциях ввода-вывода, коды ошибок, выполняемых данным потоком системных вызовов и т.д.).

Диспетчеризация сводится к следующему :

· сохранение контекста текущего потока, который требуется сменить;

· загрузка контекста нового потока, выбранного в результате планирования;

· запуск нового потока на выполнение.

В мультипрограммной системе поток может находиться в одном из трех состояний:

· выполнение – выполняется процессором:

· ожидание – ждет осуществления некоторого события;

· готовность – имеет все необходимые для выполнения ресурсы, готов выполняться, но процессор занят выполнением другого потока.

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

Граф состояний потока в многозадачной среде можно представить как на рисунке:

«Вытеснение потока» означает прекращение его выполнения процессором, например, вследствие исчерпания отведенного для выполнения кванта времени.

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

Вытесняющие и невытесняющие алгоритмы планирования.

Все множество алгоритмов планирования можно разделить на два класса: вытесняющие и невытесняющие .

Невытесняющиеоснованы на том, что активному потоку позволено выполняться до тех пор, пока он сам не решит отдать управление ОС.

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

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

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

Почти все современные ОС, такие как UNIX, Windows NT/2000, OS-2, Windows 95/98 реализуют вытесняющие алгоритмы планирования потоков.

Алгоритмы планирования, основанные на квантовании.

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

Смена активного потока происходит, если:

· поток завершился и покинул систему;

· произошла ошибка;

· поток перешел в состояние ожидания;

· исчерпан квант процессорного времени.

Поток, исчерпавший свой квант, переводится в состояние готовности и ожидает в очереди. Граф состояний потока представлен на рисунке:

Кванты для потоков могут быть одинаковыми или различными.

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

Соответствующий граф состояний потока можно представить как:

Алгоритмы планирования, основанные на приоритетах.

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

В ОС Windows NT определено 32 уровня приоритетов и два класса потоков – потоки реального времени и потоки с переменными приоритетами.

Диапазон от 1 до 15 отведен для потоков с переменными приоритетами, а от 16 до 32 – для более критичных ко времени потоков реального времени.

Смешанные алгоритмы планирования.

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

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

Планирование в системах реального времени.

В системах реального времени главным критерием является обеспечение временных характеристик вычислительного процесса.

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

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

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

Моменты перепланировки.

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

· прерывание от таймера, сигнализирующее, что время, отведенное активной задаче, закончилось;

· активная задача выполнила системный вызов, связанный с запросом на ввод-вывод или на доступ к ресурсу, который в настоящий момент занят (например, файл данных);

· активная задача выполнила системный вызов, связанный с освобождением ресурса. Планировщик проверяет, не ожидает ли этот ресурс какая-либо задача. Если да, то задача переводится из состояния ожидания в состояние готовности и проверяется, имеет ли она наивысший приоритет. Если нет – возможна перепланировка;

· внешнее аппаратное прерывание. Оно сигнализирует о переводе соответствующей текущей задачи в очередь готовности и выполняется планировщик;

· внутреннее прерывание сообщает об ошибке в текущей задаче. Планировщик снимает задачу и выполняет перепланирование.

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