Файл: Оглавление Раздел I. Основные понятия.pdf

41
Если процесс вытесняется или добровольно отдает управле- ние планировщику, он попадает в состояние «готовность» и поме- щается в очередь планировщика. В это же состояние процесс пере- ходит из состояния «ожидание» после того, как произойдет ожида- емое событие.
Информационные структуры процесса. Информационные структуры, которые используются для управления исполнением процессов, называются контекст и дескриптор. Программный код только тогда начнет выполняться, когда для него операционной си- стемой будет создан процесс. Создание процесса состоит из трех этапов: создания дескриптора и контекста процесса; включения де- скриптора нового процесса в очередь готовых процессов; загрузки кодового сегмента процесса в оперативную память.
На протяжении существования процесса его выполнение мо- жет быть многократно прервано и продолжено. Для того, чтобы воз- обновить выполнение процесса, необходимо восстановить состояние его операционной среды. Состояние операционной среды состоит из значений регистров и программного счетчика, режима работы про- цессора, указателей на открытые файлы, информации о незавершен- ных операциях ввода-вывода, кодов ошибок, выполняемых данным процессом системных вызовов. Эта информация называется контек-
стом процесса. Контекст является зависимой от аппаратуры струк- турой данных.
Операционной системе для реализации планирования процес- сов требуется дополнительная информация: идентификатор процес- са, состояние процесса, данные о степени привилегированности процесса, данные о нахождении процесса в очередях, указатель на контекст процесса. Эта информация называется дескриптором про-
цесса. Содержание информационных полей дескриптора определя- ется разработчиком операционной системы, зависит от особенно- стей алгоритма планирования и не зависит от аппаратуры.
Очереди процессов представляют собой дескрипторы процес- сов, объединенные в списки. Поэтому каждый дескриптор содержит, по крайней мере, один указатель на другой дескриптор, соседству- ющий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать процессы, переводить процессы из одного состояния в другое.

42
Виды алгоритмов планирования. Управление процессами включает в себя решение следующих задач: определение момента времени для смены выполняемого процесса; выбор процесса на вы- полнение из очереди готовых процессов; переключение контекстов между вновь запускаемым и снимаемым с исполнения процессом.
Последняя задача решается аппаратно. То, каким образом решаются первые две задачи, определяется алгоритмом планирования.
Существует множество различных алгоритмов планирования процессов, по-разному решающих вышеперечисленные задачи, преследующих различные цели и обеспечивающих различное каче- ство мультипрограммирования. Однако на планирование можно повлиять двумя способами. Можно управлять длительностью ис- полнения процессов, воздействуя на переход между состоянием
«выполнение» – «готовность». Алгоритмы, использующие данный подход – это алгоритмы, основанные на квантовании. Можно управ- лять выбором готового процесса на исполнение, воздействуя на пе- реход «готовность» – «выполнение». Этот подход используют алго- ритмы, основанные на приоритетах.
В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если: процесс завершился и покинул систему; произошла ошибка; процесс перешел в состояние
«ожидание»; исчерпан квант процессорного времени для данного процесса. Длительность отводимых на исполнение промежутков времени (квантов времени) определяется системным таймером, ко- торый периодически шлет запросы прерывания центральному про- цессору. Обработчик прерывания передает управление планировщи- ку операционной системы, который и выполняет переключение кон- текстов между процессами.
Процесс, который исчерпал свой квант, переводится в состоя- ние «готовность» до тех пор, пока ему будет предоставлен новый квант процессорного времени. На выполнение в соответствии с определенным правилом выбирается новый процесс из очереди го- товых процессов. Таким образом, ни один процесс не занимает про- цессор надолго, поэтому квантование широко используется в систе- мах разделения времени.
Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному про- цессу, могут быть фиксированной величины или изменяться пока

43 процесс исполняется. Процессы, которые не полностью использова- ли выделенный им квант (например, из-за ухода на выполнение опе- раций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По-разному может быть организована очередь готовых процессов: циклически, по правилу «первый пришел – первый обслужен» (FIFO) или по пра- вилу «последний пришел – первый обслужен» (LIFO).
Другая группа алгоритмов использует понятие приоритет.
Приоритет – это число, характеризующее степень привилегирован- ности процесса. Приоритет может выражаться натуральными, целы- ми или вещественными числами. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет мо- жет назначаться директивно администратором системы в зависимо- сти от важности работы или внесенной платы, либо вычисляться самой операционной системой по определенным правилам. Он мо- жет оставаться фиксированным либо изменяться во времени в соот- ветствии с некоторым законом. В последнем случае приоритеты называются динамическими.
Существует две разновидности приоритетных алгоритмов: ал- горитмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты. В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одина- ково: выбирается процесс, имеющий наивысший приоритет. По- разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние «ожидание» (произойдет ошибка или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается, если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности.
Во многих операционных системах алгоритмы планирования построены с использованием как квантования, так и приоритетов.
Например, в основе планирования лежит квантование, но величина кванта и порядок выбора процесса из очереди готовых определяется приоритетами процессов.

44
Виды многозадачности. В зависимости от того, кто является инициатором перехода из состояния «выполнение» в состояние «го- товность», различают три вида многозадачности.
Вытесняющая многозадачность (preemptive multitasking) – это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком операционной системы, а не самой активной задачей.
Невытесняющая многозадачность (non-preemptive multitask- ing) – это способ планирования процессов, при котором операцион- ная система не является инициатором переключения контекста с те- кущего процесса на новый процесс. Такое переключение может осуществляться по инициативе пользователя с использованием про- граммы-переключателя на фоновый процесс или по инициативе ис- полняющегося процесса.
Вид многозадачности называется кооперативной или сов-
местной многозадачностью (cooperative multitasking), когда теку- щий процесс самостоятельно отдает управление планировщику опе- рационной системы для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.
Основным различием между вытесняющей и кооперативной многозадачностью является степень централизации механизма пла- нирования задач. При вытесняющей многозадачности механизм планирования задач целиком сосредоточен в операционной системе.
Программист пишет свое приложение, не заботясь о том, что оно будет выполняться параллельно с другими задачами. Операционная система выполняет следующие функции: определяет момент снятия с выполнения активной задачи; запоминает ее контекст; выбирает из очереди готовых задач следующую и запускает ее на выполнение, загружая ее контекст.
При кооперативной многозадачности механизм планирования распределен между системой и прикладными программами. При- кладная программа, получив управление от операционной системы, сама определяет момент завершения своей очередной итерации и передает управление операционной системе с помощью какого-либо системного вызова, а операционная система формирует очереди за- дач и выбирает следующую задачу на выполнение.

45
Для пользователей это означает, что управление системой те- ряется на произвольный период времени. Если приложение тратит слишком много времени на выполнение какой-либо работы, напри- мер на форматирование диска, пользователь не может переключить- ся с этой задачи на другую задачу. Эта ситуация нежелательна, так как пользователи обычно не хотят долго ждать, когда машина за- вершит свою задачу. Поэтому разработчики приложений для коопе- ративной операционной системы, возлагая на себя функции плани- ровщика, должны создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Например, программа формати- рования может отформатировать одну дорожку диска и вернуть управление системе. После выполнения других задач система воз- вратит управление программе форматирования, чтобы та отформа- тировала следующую дорожку. Подобный метод разделения време- ни между задачами затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Если про- изойдет зацикливание потока управления внутри задачи, это приве- дет к общему краху системы. В системах с вытесняющей многоза- дачностью такие ситуации, как правило, исключены, так как цен- тральный планирующий механизм снимет зависшую задачу с вы- полнения.
Однако распределение функций планировщика между систе- мой и приложениями не всегда является недостатком, а при опреде- ленных условиях может быть и преимуществом. Кооперативная многозадачность дает возможность разработчику приложений само- му проектировать алгоритм планирования, наиболее подходящий для решаемой задачи. Так как разработчик сам определяет в про- грамме момент отдачи управления, то исключаются нерациональные прерывания программ. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итера- ции использует их монопольно. На протяжении итерации никакой другой процесс не изменит данные. Существенным преимуществом систем с кооперативной многозадачностью является более высокая скорость переключения с задачи на задачу.
Кооперативная многозадачность реализована в Windows до версии 3.11 включительно, в Mac OS до версии Mac OS X, а также во многих ранних UNIX-подобных операционных системах.

46
Потоки исполнения. Важным аспектом реализации совре- менных многозадачных операционных систем является наличие по- токов выполнения или нитей (thread). Как отмечалось, процессы – это сущности, являющиеся единицами планирования и единицами выделения ресурсов. Концепция потоков позволяет определить не одну, а несколько единиц планирования внутри пула ресурсов, вы- деленных процессу.
Каждый поток исполнения имеет собственный программный счетчик, стек, регистры, состояние. Потоки разделяют: адресное пространство процесса, в котором они исполняются; глобальные переменные; открытые файлы; объекты, адресуемые через таблицу описателей объектов ядра процесса; статистическую информацию.
Существует несколько моделей реализации многопоточности в зависимости от того, как системные потоки, реализуемые в ядре операционной системы, соотносятся с пользовательскими потоками внутри процесса.
Потоки выполнения, созданные пользователем в модели пото-
ков ядра (1:1), соответствуют потокам ядра. Это простейший воз- можный вариант реализации многопоточности.
В модели пользовательских потоков (N:1) предполагается, что все потоки выполнения уровня пользователя отображаются на поток уровня ядра и ядро ничего не знает о составе прикладных потоков выполнения. При таком подходе переключение контекста может быть сделано очень быстро. Однако главным недостатком является отсутствие ускорения на многопроцессорных компьютерах, потому что только один поток выполнения ядра может быть запланирован на процессор.
В гибридной модели (M:N) некоторое число M прикладных по- токов выполнения отображаются на некоторое число N сущностей ядра или «виртуальных процессоров». Модель является компромис- сной между моделью уровня ядра (1:1) и моделью уровня пользова- теля.
Специальные сущности, используемые для реализации моде- лей многопоточности (N:1) – это файберы (fiber- волокно). В
Windows NT файберы организуются на базе потока. Особенностью является принудительное, выполняемое программистом переключе- ние контекста между файберами одного потока. Таким образом, на

47 основе файберов могут быть реализованы преимущества коопера- тивной многозадачности внутри одного процесса.
Есть много различных, несовместимых друг с другом реализа- ций потоков. К ним относятся как реализации на уровне ядра, так и реализации на пользовательском уровне. Чаще всего они придержи- ваются более или менее близко стандарта интерфейса POSIX
Threads.
Лекция 6. Многозадачность
в операционной системе Windows
Многозадачность на уровне процессов и на уровне потоков: группы процессов, планирование в режиме пользователя, пулы потоков, файберы. Планировщик: классы и уровни приоритета, структуры данных планировщика, переключение контекста, выбор готового потока на исполнение. Инверсия приоритета, способы преодоления.
Многопроцессорная обработка.
Многозадачность. Рассмотрим некоторые особенности реа- лизации многозадачности на примере операционной системы
Windows. В Windows используются все современные технологии управления многозадачностью для однопроцессорных и многопро- цессорных систем. Подробную информацию можно найти в библио- теке разработчика Microsoft Developer Network в разделе About Pro- cesses and Threads.
В Windows имеются два основных способа использования многозадачности: многозадачность на уровне процессов и многоза- дачность на уровне потоков.
Многозадачность на уровне процессов используется, если тре- буется изоляция адресного пространства и ресурсов. Примером яв- ляется реализация системных служб Windows в виде автономных процессов. Такая реализация предполагает наличие управляющего процесса, который запускает рабочие процессы, выполняет диагно- стику их состояния и при необходимости перезапускает. Крах си-

48 стемной службы не приводит к краху других процессов за счет изо- ляции ресурсов.
Для управления приложением, состоящим из нескольких про- цессов, в Windows предусмотрены специальные объекты – работы
(job objects). Работа позволяет рассматривать группу процессов как целое. Операция, применяемая к работе, влияет на все процессы, связанные с ней. Например, можно установить групповой приори- тет, размер рабочей области или одновременно удалить все процес- сы, ассоциированные с работой.
Многозадачность на уровне потоков исполнения может ис- пользоваться при выполнении следующих задач:
1. Управление вводом из нескольких окон. Примером является оконный менеджер, который для каждой папки создаёт отдельный поток.
2. Управление вводом из нескольких коммуникационных устройств. Данный подход применяется в многопоточных серверах в интернете. Каждого подключенного клиента обслуживает отдель- ный поток. Использование потоков позволяет упростить архитекту- ру программы сервера за счет применения блокирующих операций ввода-вывода с сохранением эффективности приложений, построен- ных на асинхронных операциях ввода-вывода.
3. Разделение задач различного приоритета. Может потребо- ваться для выполнения высокоприоритетным потоком критичных ко времени задач. Например, такой поток может заниматься сохра- нением телеметрической информации. Основной поток может осуществлять графическое отображение этой информации на тер- минале.
4. Сохранение интерактивности приложения при выполнении фоновой задачи. При выполнении длительных расчетов возникает необходимость в прерывании вычислений, ввода или корректировки параметров. Для этого вычисления организуют в фоновом низ- коприоритетном потоке. Когда пользователь активирует элементы графического интерфейса, более приоритетный поток GUI немед- ленно прерывает вычисления и обрабатывает команды пользователя.
5. Использование преимуществ многопроцессорных систем для ускорения вычислений. Требуется разделить программу на не- сколько потоков, если разрабатывается ресурсоемкое приложение, которому необходимо использовать все вычислительные ресурсы

49 современных многоядерных и многопроцессорных систем. Обычная однопоточная программа не сможет выполняться на нескольких яд- рах и эффективно использовать возможности современной аппара- туры.
Реализация многозадачности с использованием одного про- цесса и нескольких потоков, если не требуется изоляции ресурсов, предпочтительна по следующим соображениям: происходит более быстрое переключение контекста между потоками одного процесса по сравнению с переключением контекстов между потоками разных процессов; потоки одного процесса разделяют глобальные перемен- ные; потоки одного процесса разделяют описатели системных ре- сурсов.
Операционная система Windows обеспечивает альтернативные потокам методы многозадачности, например, асинхронный ввод- вывод, асинхронные вызовы процедур (APC) и другие.
Как отмечалось ранее, в Windows используется модель пото- ков ядра (1:1). Поэтому при использовании потоков рекомендуют использовать как можно меньше потоков для одного приложения, так как требуются ресурсы для хранения контекста потока, для от- слеживания нескольких активных потоков и, обычно, более сложная синхронизация.
В современных версиях системы Windows NT поддерживается гибридная потоковая модель (M:N). В Windows она называется пла- нированием в режиме пользователя (UMS – user mode scheduling).
Модель следует использовать при необходимости создавать боль- шое число потоков одновременно. При этом сочетаются преимуще- ства быстрого переключения между такими потоками и отсутствие блокировки всех UMS-потоков, когда один из них выполняет блоки- рующую операцию ядра.
Модель пользовательских потоков (N:1) реализуется при по- мощи файберов (fiber). Данная модель может использоваться, если требуется реализовать самостоятельно планировщик или для пере- носа в Windows приложений с кооперативной многозадачностью без значительной переделки кода.
В Windows также имеется встроенная поддержка парадигмы параллельного программирования «управляющий – рабочие». Она называется потоковые пулы (thread pools). Потоковый пул – это

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