Тема 2.3. Планирование процессов
Процесс это программный модуль, выполняемый процессором. С каждым процессом связывают его адресное пространство – список адресов в памяти от минимума (обычно от 0) до максимума, которые процесс может прочесть и в которые может писать. Адресное пространство содержит саму программу, данные к ней и стек. Со всяким процессом связывают некий набор регистров, включая счетчик команд, указатель стека и другие аппаратные регистры, а также другую информацию, необходимую для запуска программ (контекст процесса).
Предположим, периодически ОС решает остановить работу одного процесса и запустить другой, потому, что первый израсходовал отведенную для него часть рабочего времени ЦП. Позже этот процесс должен быть запущен заново из того же состояния, в котором его остановили, следовательно, всю информацию нужно где-либо сохранить на время приостановки процесса.
Во многих ОС вся информация о каждом процессе, дополнительная к содержимому его собственного адресного пространства, хранится в таблице ОС. Эта таблица называется таблицей процессов (блок управления процессом) и представляет собой массив структур, по одной на каждый существующий в данный момент процесс.
Т.о. приостановленный процесс состоит из собственного адресного пространства, называемого образом памяти, и компонентов таблицы процесса, содержащей помимо других величии, его регистры.
Состояния процессов
Различают следующие состояния процессов:
новый (только что создан);
работающий (в этот конкретный момент используемый ЦП);
готовый к работе (процесс временно приостановлен, чтобы позволить выполниться другому процессу);
ожидающий или заблокированный (процесс не может быть запущен прежде, чем произойдет некоторое внешнее событие, например операция ввода- вывода).
Переход от одного состояния в другое не может осуществляться произвольным образом. На рисунке 1 показана типовая диаграмма перехода процессов.
Рис. 1. Типовая диаграмма перехода процессов.
Создание процессов
В универсальных системах необходим способ завершения и создания процессов по мере необходимости.
Основные события, приводящие к созданию процессов:
инициализация системы,
выполнение изданного работающим процессом системного запроса на создание процесса;
запрос пользователя на создание процесса;
инициирование пакетного задания.
Обычно при запуске ОС создаются несколько процессов. Некоторые из них являются высокоприоритетными процессами, т.е. обеспечивающими взаимодействие с пользователями и выполняющие заданную работу. Остальные процессы являются фоновыми, они не связаны с конкретными пользователями, но выполняют особые функции
Например: один фоновый процесс может быть предназначен для обработки приходящей на компьютер почты, активизируясь по мере появления писем. Другой фоновый процесс может обрабатывать запросы к web-страницам, расположенным на компьютере, и активизироваться для обслуживания полученного запроса. Фоновые процессы называются демонами. В больших системах насчитывается десятки демонов. Для вывода запущенных процессов используется программа PS. В Windows 95/98 –Ctrl-Alt-Del. В Windows 2000 можно воспользоваться Диспетчером задач.
Процессы могут создаваться «по просьбе» текущего процесса. Создание нового процесса особенно полезно в тех случаях, когда выполняемую задачу проще сформировать как набор связанных, но независимых взаимодействующих процессов. Если необходимо организовать выборку большого количества данных из сети для дальнейшей обработки, удобно создать один процесс для выборки данных и размещения их в буфере совместно используемом, в то время как второй процесс будет считывать данные из буфера и обрабатывать их.
В интерактивных системах пользователь может запустить программу, набрав на клавиатуре команду или щелкнув по пиктограмме. В результате будет создано окно и запущена в нем программа. Пользователь может открыть несколько окон, каждому из которых будет соответствовать свой процесс. Пользователь может переключаться между окнами и взаимодействовать с процессом, например, вводя данные.
Системы пакетной обработки. Пользователь посылает пакетное задание, а ОС создает новый процесс и запускает следующее задание из очереди в тот момент, когда освобождаются необходимые ресурсы.
Во всех этих случаях новый процесс формируется одинаково: текущий процесс выполняет системный запрос на создание нового процесса.
Завершение процессов
Завершение процессов осуществляется чаще всего благодаря одному из следующих событий:
Обычный выход (преднамеренно). По мере выполнения своей работы процессы завершаются. После окончания компиляции программы компилятор выполняет системный запрос, чтобы сообщить ОС об окончании работы. Программы, рассчитанные Ра работу с экраном, также поддерживают преднамеренное завершение. В текстовых редакторах, браузерах и других программах такого типа обычно есть кнопка или пункт меню, щелкнув по которому можно удалить все временные файлы, открытые процессом и, затем, завершить процесс.
Выход по ошибке (преднамеренно). Например, по неустранимой ошибке. Если пользователь набрал команду для компиляции программы, а соответствующего файла не существует, компилятор просто закончит свою работу. Интерактивные процесс, рассчитанные на работу с экраном, обычно не завершают работу при получении неверных параметров, вместо этого выводят диалоговое окно, прося ввести правильные параметры.
Выход по неисправимой ошибке (непреднамеренно). Чаще всего связан с ошибкой в самой программе. Например: обращение к несуществующей области памяти и деление на нуль. Процесс прерывается, а не завершается.
уничтожение другим процессом (непреднамеренно). Причиной завершения процесса может быть выполнение другим процессом системного запроса на уничтожение процесса. В обоих случаях «киллер» должен обладать соответствующими правами по отношению к «убиваемому» процессу.
И ерархия процессов
Если процесс может создавать несколько других процессов, то созданные - называются дочерними. Связанные процессы,- это те, которые объединены для выполнения некоторой задачи, и им нужно часто передавать данные от одного к другому и синхронизировать свою деятельность.
В Unix процесс и его «дети» и дальнейшие потомки образуют группу процессов. Сигнал, посылаемый пользователем с клавиатуры, доставляется всем членам группы, взаимодействующим с клавиатурой в данный момент (обычно это процессы, созданные в текущем окне). Каждый их процессов может перехватить сигнал, игнорировать его или выполнить другое действие, предусмотренное по умолчанию.
Например: в Unix, процесс init. При запуске этот процесс считывает файл, в котором находится информация о количестве терминалов. Затем процесс разветвляется таким образом, чтобы каждому терминалу соответствовал один процесс. Процессы ждут, пока пользователь какой-либо не войдет в систему. Если пароль правильный, процесс входит в систему, запускает оболочку для команд пользователя, которые в свою очередь могут запускать процессы. Т.о. все процессы принадлежат дереву процессов, начинающемуся с процесса init.
В Windows не существует иерархии процессов, все процессы равноправны.
Вытесняющие и невытесняющие алгоритмы планирования
С самых общих позиций все множество алгоритмов планирования можно разделить на два класса: вытесняющие и невытесняющие алгоритмы планирования.
Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению поток.
Вытесняющие (preemptive) алгоритмы — это такие способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается операционной системой, а не активной задачей.
Основным различием между вытесняющими и невытесняющими алгоритмами является степень централизации механизма планирования потоков. При вытесняющем мультипрограммировании функции планирования потоков целиком сосредоточены в операционной системе и программист пишет свое приложение, не заботясь о том, что оно будет выполняться одновременно с другими задачами. При этом операционная система выполняет следующие функции: определяет момент снятия с выполнения активного потока, запоминает его контекст, выбирает из очереди готовых потоков следующий, запускает новый поток на выполнение, загружая его контекст.
При невытесняющем мультипрограммировании механизм планирования распределен между операционной системой и прикладными программами. Прикладная программа, получив управление от операционной системы, сама определяет момент завершения очередного цикла своего выполнения и только затем передает управление ОС с помощью какого-либо системного вызова. ОС формирует очереди потоков и выбирает в соответствии с некоторым правилом (например, с учетом приоритетов) следующий поток на выполнение. Такой механизм создает проблемы как для пользователей, так и для разработчиков приложений.
Почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, OS/2, VAX/VMS), реализована вытесняющая многозадачность.
Алгоритмы планирования, основанные на квантовании
В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому процессу поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени — квант. Смена активного процесса происходит, если:
процесс завершился и покинул систему;
произошла ошибка;
процесс перешел в состояние ожидания;
исчерпан квант процессорного времени, отведенный данному процессу.
Алгоритмы, основанные на приоритетах.
Вытесняющие алгоритмы этого класса основаны на механизме абсолютных приоритетов, при котором задача снимается с выполнения, когда появляется в системе задание с более высоким приоритетом
Метод очередей ресурсов
Одним из методов планирования процессов является метод очередей ресурсов.
Новые процессы находятся во входной очереди, называемой очередью заданий (работ).
Входная очередь располагается во внешней памяти, во входной очереди процессы ожидают освобождения ресурса – адресного пространства в оперативной памяти.
Готовые к выполнению процессы располагаются в основной памяти и связаны с очередью готовых процессов. Процессы в этой очереди ожидают освобождения ресурса процессорное время.
Процесс в состоянии ожидания завершения операции ввода- вывода находится в одной из очередей к оборудованию ввода- вывода.
При прохождении через компьютер процесс мигрирует между очередями под управление программы, которая называется планировщик (scheduler). Операционная система, обеспечивающая режим мультипрограммирования, обычно включает два планировщика – долгосрочный и краткосрочный.
На уровень долгосрочного планирования выносятся редкие системные действия, требующие больших затрат системных ресурсов, на уровень краткосрочного планирования – частые и более короткие процессы.
Основное отличие между долгосрочным и краткосрочным планированием заключается в частоте запуска. Например, краткосрочный планировщик может запускаться каждые 100 мс, долгосрочный – один раз в несколько минут.
Долгосрочный планировщик решает, какой из процессов, находящийся во входной очереди, должен быть переведен в очередь готовых процессов в случае освобождения ресурса памяти. Он выбирает процесс из входной очереди с целью создания неоднородной мультипрограммной смеси. Мультипрограммная смесь- это множество одновременно выполняемых задач. Выбираются задачи, предъявляющие разные требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины. Например, желательно одновременное присутствие вычислительных задач и задач с интенсивным вводом- выводом.
На уровне долгосрочного планирования объектом является не отдельный процесс, а некоторое объединение процессов по функциональному назначению, которое называется приложением.
Краткосрочный планировщик решает, какой из процессов, находящихся в очереди готовых процессов, должен быть передан на выполнение в CPU.
В различных средах требуются различные алгоритмы планирования. Это связано с тем, что различные ОС и различные приложения ориентированы на разные задачи. Можно выделить 3 среды:
системы с пакетной обработкой данных;
интерактивные системы;
системы реального времени.
Существуют различные алгоритмы или стратегии решения этой задачи.
Первый пришел – первый обслуживается (first come – first served - FCFS) заключается в том, что процессор передается тому процессу, который раньше всех его запросил.
Когда процесс попадает в очередь готовых процессов, таблица управления готовых процессов присоединяется к хвосту очереди.
Стратегии FCFS присущ “эффект конвоя”. В том случае, когда в компьютере имеется один большой процесс и несколько малых, то все процессы собираются в начало очереди к оборудованию. Т.о., “эффект конвоя” приводит к снижению загруженности как процессора так и периферийного оборудования.
Стратегия “наиболее короткая работа выполняется первой”(FJF – Shortest Job First). Одним из методов борьбы с “эффектом конвоя” является стратегия, позволяющая процессу из очереди выполняться первым. Стратегия SJF снижает время ожидания очереди. Используется в основном в системах с пакетной обработкой.
Приоритетное планирование. Эта стратегия предполагает, что каждому процессу приписывается приоритет, определяющий очередность представления ему CPU.
Обычно приоритет – это целое положительное число, находящееся в диапазоне, например, от 0 до 7 или от 0 до 1024. Чем меньше число, тем выше приоритет. Приоритеты назначаются исходя из совокупности внутренних и внешних по отношению к ОС факторов.
Внутренние:
требования к памяти;
количество открытых файлов;
отношение среднего времени ввода- вывода к среднему использованию ресурсов CPU и т.д.
Внешние:
важность процесса;
тип и величина файлов.
Внутренние факторы могут использоваться для автоматического назначения приоритетов самой ОС, а внешние для принудительного, с помощью оператора.
Главный недостаток приоритетного планирования – возможность блокирования на неопределенно долгое время низкоприоритетных процессов.
Для устранения этого недостатка используют следующие методы: процессы, время ожидания которых превышает фиксированную величину, например , 15 минут, автоматически получают единичное приращение.
“Карусельная” или циклическая стратегия планирования (RR- Round Robin) – применяется в системах разделения времени. Определяется небольшой отрезок времени tk- квант времени (10,..,100 мс). Очередь готовых процессов рассматривается как кольцевая. Процессы циклически перемещаются по очереди, получая CPU на время, равное 1 кванту. Новый процесс добавляется в хвост очереди. Если процесс не завершился в пределах выделенного ему кванта, его работа принудительно прерывается, и он перемещается в хвост очереди.
Свойства RR сильно зависят от величины кванта. Чем больше временной квант, тем ближе стратегия RR к FCFS. При очень малых квантах стратегию называют разделением процессора.
Планирование с использованием многоуровневой очереди. Эта стратегия разработана для ситуации, когда процессы могут быть легко классифицированы на несколько групп. Например: интерактивные (процессы переднего плана) и пакетные (фоновые).
Интерактивные и пакетные процессы имеют различные требования к краткосрочному планировщику.
Стратегия многоуровневой очереди разделяет очередь готовых процессов на несколько очередей, в каждой из которых находятся процессы с одинаковыми свойствами, и каждый из которых может планироваться индивидуальной стратегией, например, RR – стратегия для интерактивных процессов и FCFS для пакетных процессов.
Взаимодействие очередей осуществляется по следующим правилам: ни один процесс с более низким приоритетом не может быть запущен, пока не выполнятся процессы во всех очередях с более высоким приоритетом.
Работа процесса из очереди с более низким приоритетом может быть приостановлена, если в одной из очередей с более высоким приоритетом появился процесс.
Использование многоуровневой очереди с обратными связями. Обычная многоуровневая очередь не допускает перемещение процессов между очередями.
Многоуровневая очередь с обратными связями предполагает, что процессы при определенных условиях могут перемещаться между очередями. Здесь организуется N очередей. Все новые процессы поступают в конец первой очереди. Первый процесс из i-той очереди поступает на обслуживание лишь тогда, когда все очереди от 1 до i-той пустые.
На обслуживание выделяется квант времени tk. Если за это время обслуживание процесса завершится полностью, то он покидает систему. В противном случае недообслуженный процесс поступает в конец i+1 очереди.
После обслуживания процесса из i-той очереди система выбирает для обслуживания процесс из непустой очереди с самым младшим номером. Таким процессом может быть следующий процесс из очереди i или из очереди i+1 (если i- пустая). Новый процесс поступает в новую очередь (i=1). В такой ситуации после окончания tk, выделенного для обслуживания процесса из очереди i, будет начато обслуживание процесса первой очереди.
Если система выходит на обслуживание процессов из N- ой очереди, то они обслуживаются либо по алгоритму FCFS (каждая заявка обслуживается до конца), либо по циклическому алгоритму. Данная система наиболее быстро обслуживает все короткие по времени обслуживания процессы.
Недостаток: затраты времени на перемещение процессов из одной очереди в другую.
Данная система является универсальной и сочетает в себе свойства стратегий FCFS, SJF, приоритетной, RR, многоуровневой очереди.
Приоритетная многоочередная стратегия обслуживания.
Вновь поступающие процессы устанавливаются не обязательно в первую очередь, а в очередь в соответствии с использующимися приоритетами, которые определяются параметрами обслуживания процессов. Приоритетные многоочередные алгоритмы могут быть с абсолютным и относительным приоритетом.
При абсолютном приоритете процесса приоритет определяется номером очереди, и первыми обслуживаются процессы, обладающие наивысшим приоритетом. Процесс из очереди i-1 будет прерывать обработку процесса из очереди i.
Время ожидания высокоприоритетных процессов сокращается, но за счет большой задержки в обслуживании низкоприоритетных процессов.
Обслуживание с относительным приоритетом не вызывает прерывания обслуживаемого процесса до его завершения, даже если он менее приоритетный.
Контрольные вопросы
В каких состояниях может находиться поток в мультипрограммной системе?
Какое из состояний потока возможно только в мультипрограммной системе и невозможно в однопрограммной?
В каких состояниях может находиться несколько потоков, образуя при этом очередь, а в каких – только один поток?
По каким причинам поток может перейти из состояния выполнения в состояние готовности?
По каким причинам поток может выйти из состояния выполнения? В каких состояниях он может при этом оказаться?
Может ли произойти переход из состояния готовности в состояние ожидания? Почему?
Что представляет из себя дескриптор процесса и каково его назначение? Какая информация может в нём содержаться?
Что такое контекст активности процесса? Из чего он состоит?
Что включает в себя контекст памяти?
Каков механизм вызова одной процедуры из другой? Какие действия при этом совершаются?
Что такое стек выполнения? Как он реализуется?
Что представляет из себя контекст процессора?
Что такое слово состояния процессора? Какая информация в нём содержится?
|
