Понятие процесса и потока
4.2. Понятие процесса и потока
Понятие процесса и потока
Для того, чтобы перейти к более подробному рассмотрению понятия процесс, рассмотрим примеры, позволяющие выявить различия между понятиями программа, задача или процесс.
Пусть два студента запускают программу извлечения квадратного корня, при этом один хочет вычислить квадратный корень из 4, а второй – из 1. С точки зрения студентов, запущена одна и та же программа; с точки зрения компьютерной системы, ей приходится заниматься двумя различными вычислительными процессами, так как разные исходные данные приводят к разному набору вычислений. Следовательно, на уровне происходящего внутри вычислительной системы нельзя использовать термин «программа» в пользовательском смысле слова. Рассмотрим другой пример. Пусть два студента сформировали идентичные задания и пытаются извлечь квадратный корень из 1, но система выполняет эти вычисления с некоторым сдвигом во времени: в то время как одно из выполняемых заданий приступило к печати результата и ждет окончания операции ввода-вывода, второе только начинает исполняться. Очевидно, что в один момент времени в системе присутствуют различные задания, так как состояние процесса их выполнения различно.
В связи с этим, термины программа и задание правомерно применять для описания некоторых статических, неактивных объектов. Для описания динамических объектов используют термин процесс. Процесс характеризует некоторую совокупность набора исполняющихся команд, ассоциированных с ним ресурсов (выделенная для исполнения память или адресное пространство, стеки, используемые файлы и устройства ввода-вывода и т.д.) и информации о текущем моменте его исполнения (значения регистров, программного счетчика, состояние стека и значения переменных), находящуюся под управлением ОС. Такая обособленность нужна для того, чтобы защитить один процесс от другого, поскольку они, совместно используя все ресурсы вычислительной системы, конкурируют друг с другом за доступ к ресурсам. В общем случае процессы никак не связаны между собой и могут принадлежать даже разным пользователям, разделяющим одну вычислительную систему.
В настоящее время в большинстве ОС для поддержки мультипрограммирования кроме понятия процесс определена еще одна, более «мелкая» единица работы – поток.
Очевидно, что любая работа вычислительной системы заключается в выполнении некоторой программы. Поэтому и с процессом, и с потоком связывается определенный программный код, который для этих целей оформляется в виде исполняемого модуля. Очевидно, выполнение программы невозможно без предоставления ей процессорного времени, то есть времени, в течение которого процессор выполняет коды данной программы. В ОС, где существуют и процессы, и потоки, процесс рассматривается как заявка на потребление всех видов ресурсов, кроме одного – процессорного времени. Этот последний важнейший ресурс распределяется ОС между другими единицами работы – потоками, которые и получили свое название благодаря тому, что они представляют собой последовательности (потоки выполнения) команд.
В простейшем случае процесс состоит из одного потока, а это означает, что остается только одна единица работы и потребления ресурсов – процесс. Мультипрограммирование осуществляется в таких ОС на уровне процессов. Рассмотрим основные предпосылки, способствовавшие появлению потоков.
Как отмечалось выше, для того чтобы процессы не могли вмешаться в распределение ресурсов, а также не могли повредить коды и данные друг друга, важнейшей задачей ОС является изоляция одного процесса от другого. Для этого ОС обеспечивает каждый процесс отдельным виртуальным адресным пространством, так что ни один процесс не может получить прямого доступа к командам и данным другого процесса. При необходимости взаимодействия, процессы обращаются к ОС, которая, выполняя функции посредника, предоставляет им средства межпроцессной связи – конвейеры, разделяемые секции памяти и др. Очевидно, такой способ взаимодействия параллельно действующих процессов является достаточно затратным, т.к. требуются дополнительные затраты времени на переключение контекста.
Рекомендуемые материалы
В то же время, приложение, выполняемое в рамках одного процесса, может обладать внутренним параллелизмом, который в принципе мог бы позволить ускорить его работу. Если, например, в программе предусмотрено обращение к внешнему устройству, то на время этой операции можно не блокировать выполнение всего процесса, а продолжить вычисления по другой ветви программы. Параллелизм желателен как для обслуживания различных запросов к базе данных, так и для более быстрого выполнения отдельного запроса за счет одновременного просмотра различных записей базы.
Конечно, задача распараллеливания вычислений в рамках одного приложения может быть решена традиционными способами с использованием развитых функций программирования и стандартных средств межпроцессного взаимодействия без использования потоков.
Например, прикладной программист может взять на себя сложную задачу организации параллелизма, выделив в приложении некоторую подпрограмму-диспетчер, которая периодически передает управление той или иной ветви вычислений. При этом программа может получиться логически весьма сложной, с многочисленными передачами управления, что существенно затрудняет ее отладку и модификацию.
Другим способом является создание для одного приложения нескольких процессов для каждой из параллельных работ. Однако использование для создания процессов стандартных средств ОС не позволяет учесть тот факт, что эти процессы решают единую задачу, а значит, имеют много общего между собой – могут работать с одними и теми же данными, использовать один и тот же кодовый сегмент, наделяться одними и теми же правами доступа к ресурсам вычислительной системы. Например, создание отдельных процессов при поступлении каждого запроса к серверу баз данных, при условии, что все процессы будут выполнять один и тот же программный код и выполнять поиск в записях, общих для всех процессов файлов данных, не выглядит целесообразным. В особенности если ОС при таком подходе будет рассматривать эти процессы наравне со всеми остальными процессами и с помощью универсальных механизмов обеспечивать их изоляцию друг от друга. Очевидно, что в подобном случае достаточно громоздкие механизмы межпроцессного взаимодействия будут использоваться явно не по назначению, затрудняя обмен данными между различными частями приложения. Кроме того, на создание каждого процесса ОС тратит системные ресурсы, которые в данном случае неоправданно дублируются – каждому процессу выделяются собственное виртуальное адресное пространство, физическая память, закрепляются устройства ввода-вывода и т.п.
Из всего вышеизложенного, следует, что в ОС наряду с процессами нужен другой механизм распараллеливания вычислений, который учитывал бы тесные связи между отдельными ветвями вычислений одного и того же приложения. Для этих целей современные ОС предлагают механизм многопоточной обработки (англ. multithreading). При этом и необходима новая единица работы – поток или нить исполнения (нити, легковесные (англ. thin) процессы, треды (англ. threads)).
Следует отметить, что легковесными эти процессы называют потому, что ОС не должна для них организовывать полноценную виртуальную машину (с собственными ресурсами), а развиваются они в том же виртуальном адресном пространстве, могут пользоваться теми же файлами, виртуальными устройствами и иными ресурсами, выделенными ОС данному процессу. Единственное, что они имеют свое – это процессорный ресурс. Другими словами, понятию поток соответствует последовательный переход процессора от одной команды программы к другой, при этом ОС распределяет процессорное время между потоками. В то же время процессу ОС назначает адресное пространство и набор ресурсов, которые совместно используются всеми его потоками.
4.2.2. Создание процессов и потоков
Создание процессов и потоков
Создать процесс – это прежде всего означает создать описатель процесса, в качестве которого выступает одна или несколько информационных структур, содержащих все сведения о процессе, необходимые ОС для управления им. Примерами описателей процесса являются блок управления задачей (Task Control Block – ТСВ) в OS/360, управляющий блок процесса (Process Control Block – РСВ) в OS/2, дескриптор процесса в Unix, объект-процесс (object-process) в Windows NT.
Создание описателя процесса знаменует собой появление в системе еще одного претендента на вычислительные ресурсы. Начиная с этого момента при распределении ресурсов ОС должна принимать во внимание потребности нового процесса. Создание процесса включает загрузку кодов и данных исполняемой программы данного процесса с диска в оперативную память. Для этого ОС должна обнаружить местоположение такой программы на диске, перераспределить оперативную память и выделить память исполняемой программе нового процесса. Затем необходимо считать программу в выделенные для нее участки памяти и, возможно, изменить параметры программы в зависимости от размещения в памяти.
В системах с виртуальной памятью (подробнее особенности организации виртуальной памяти рассмотрены ниже п. 4.2) в начальный момент может загружаться только часть кодов и данных процесса, с тем чтобы «подкачивать» остальные по мере необходимости. Существуют системы, в которых на этапе создания процесса не требуется непременно загружать коды и данные в оперативную память, вместо этого исполняемый модуль копируется из того каталога файловой системы, в котором он изначально находился, в область подкачки – специальную область диска, отведенную для хранения кодов и данных процессов. При выполнении всех этих действий подсистема управления процессами тесно взаимодействует с подсистемой управления памятью и файловой системой.
Создание процесса состоит из нескольких этапов:
· присвоения идентификатора процессу;
· включения его в список активных процессов, известных системе;
· формирования блока управления процессом;
· выделения процессу начальных ресурсов.
В многопоточной системе при создании процесса ОС создает для каждого процесса как минимум один поток. При создании потока так же, как и при создании процесса, ОС генерирует специальную информационную структуру – описатель потока.
В исходном состоянии поток (или процесс, если речь идет о системе, в которой понятие «поток» не поддерживается) находится в приостановленном состоянии. Момент выборки потока на выполнение осуществляется в соответствии с принятым в данной системе правилом предоставления процессорного времени и с учетом всех существующих в данный момент потоков и процессов. В случае если коды и данные процесса находятся в области подкачки, необходимым условием активизации потока процесса является также наличие места в оперативной памяти для загрузки его исполняемого модуля.
В общем случае существующий процесс может породить новый процесс, и может иметь место иерархическая структура процессов. Задача может порождать подзадачу в мультипрограммном режиме, и в этом смысле будут появляться родительский и дочерний процессы. Уничтожение процесса означает удаление его из системы. Ресурсы возвращаются системе, имя процесса удаляется из списка, блок управления процессом освобождается.
В разных ОС по-разному строятся отношения между потоками-потомками и их родителями. Например, в одних ОС выполнение родительского потока синхронизируется с его потомками, в частности после завершения родительского потока ОС может снимать с выполнения всех его потомков. В других системах потоки-потомки могут выполняться асинхронно по отношению к родительскому потоку. Потомки, как правило, наследуют многие свойства родительских потоков. Во многих системах порождение потомков является основным механизмом создания процессов и потоков.
4.2.3. Управляющие структуры процессов и потоков
Управляющие структуры процессов и потоков
Для того чтобы ОС могла управлять процессами, она должна располагать всей необходимой для этого информацией, содержащейся в описателе процесса – дескрипторе процесса (контексте процесса). В общем случае дескриптор процесса, как правило, содержит следующую информацию:
· идентификатор процесса (Process Identifier, PID);
· тип (или класс) процесса, который определяет для супервизора некоторые правила предоставления ресурсов;
· приоритет процесса, в соответствии с которым супервизор предоставляет ресурсы (в рамках одного класса процессов в первую очередь обслуживаются более приоритетные процессы);
· переменную состояния, которая определяет, в каком состоянии находится процесс (готов к работе, выполняется, ожидает устройства ввода-вывода и т. д.);
· контекст задачи, то есть защищенную область памяти (или адрес такой области), в которой хранятся текущие значения регистров процессора, когда процесс прерывается, не закончив работы;
· информацию о ресурсах, которыми процесс владеет и/или имеет право пользоваться (указатели на открытые файлы, информация о незавершенных операциях ввода-вывода и др.);
· место (или его адрес) для организации общения с другими процессами;
· параметры времени запуска (момент времени, когда процесс должен активизироваться, и периодичность этой процедуры);
· в случае отсутствия системы управления файлами адрес задачи на диске в ее исходном состоянии и адрес на диске, куда она выгружается из оперативной памяти (ОП), если ее вытесняет другая задача (последнее справедливо для диск-резидентных задач, которые постоянно находятся во внешней памяти на системном магнитном диске и загружаются в ОП только на время выполнения).
В некоторых ОС количество описателей определяется жестко и заранее (на этапе генерации варианта ОС или в конфигурационном файле, который используется при загрузке ОС), в других по мере необходимости система может выделять участки памяти под новые описатели. Например, в уже мало кому известной системе OS/2, которая несколько лет тому назад многими специалистами считалась одной из лучших ОС для персональных компьютеров, максимально возможное количество описателей задач указывается в конфигурационном файле CONFIG.SYS. Например, строка THREADS = 1024 в файле CONFIG.SYS означает, что всего в системе может параллельно существовать и выполняться до 1024 задач, включая вычислительные процессы и их потоки. В системах Windows NT/2000/XP количество описателей в явном виде не задается – это переменная величина и она определяется самой ОС. Текущее количество таких описателей представлено в окне Диспетчера задач.
Описатели задач, как правило, постоянно располагаются в ОП с целью ускорить работу супервизора, который организует их в списки (очереди) и отображает изменение состояния процесса перемещением соответствующего описателя из одного списка в другой. Для каждого состояния (за исключением состояния исполнения для однопроцессорной системы) ОС ведет соответствующий список задач, находящихся в этом состоянии. Однако для состояния ожидания обычно имеется не один список, а столько, сколько различных видов ресурсов могут вызывать состояние ожидания.
Очереди процессов представляют собой дескрипторы отдельных процессов, объединенные в списки – каждый дескриптор, кроме всего прочего, содержит, по крайней мере, один указатель на другой дескриптор, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать процессы, переводить процессы из одного состояния в другое.
В ОСРВ чаще всего количество процессов фиксируется, и, следовательно, целесообразно заранее определять (на этапе генерации или конфигурирования ОС) количество дескрипторов. Для использования таких ОС в качестве систем общего назначения (что в настоящее время нехарактерно) обычно количество дескрипторов бралось с некоторым запасом, и появление новой задачи связывалось с заполнением этой информационной структуры. Поскольку дескрипторы процессов постоянно располагаются в оперативной памяти (с целью ускорить работу диспетчера), то их количество не должно быть очень большим.
Для более эффективной обработки данных в ОСРВ целесообразно иметь постоянные задачи, полностью или частично существующие в системе независимо от того, поступило на них требование или нет. Каждая постоянная задача обладает некоторой собственной областью оперативной памяти (ОЗУ-резидентная задача или просто резидентная задача) независимо от того, выполняется задача в данный момент или нет. Эта область, в частности, может использоваться для хранения данных, полученных задачей ранее. Данные могут храниться в ней и тогда, когда задача находится в состоянии ожидания или даже в состоянии бездействия.
Для аппаратной поддержки работы ОС с этими информационными структурами (дескрипторами задач) в процессорах могут быть реализованы соответствующие механизмы. Так, например, в микропроцессорах Intel 80x86 имеется специальный регистр (Task Register – TR), указывающий местонахождение специальной информационной структуры – сегмента состояния задачи (Task State Segment – TSS), в котором при переключении с задачи на задачу автоматически сохраняется содержимое регистров процессора.
4.2.4. Состояния процесса
Состояния процесса
Все, что выполняется в вычислительных системах (не только программы пользователей, но и, возможно, определенные части ОС), организовано как набор процессов. Понятно, что реально на однопроцессорной компьютерной системе в каждый момент времени может исполняться только один процесс. Для мультипрограммных вычислительных систем псевдопараллельная обработка нескольких процессов достигается с помощью переключения процессора с одного процесса на другой. Пока один процесс выполняется, остальные ждут своей очереди на получение процессора.
Каждый процесс может находиться как минимум в двух состояниях: процесс исполняется и процесс не исполняется. Диаграмма состояний процесса в такой модели изображена на рис. 9.
Рисунок 9 – Простейшая диаграмма состояний процесса
Процесс, находящийся в состоянии процесс исполняется, может через некоторое время завершиться или быть приостановлен ОС и снова переведен в состояние процесс не исполняется. Приостановка процесса может произойти, например, по следующим причинам: для его дальнейшей работы потребовалось возникновение какого-либо события (например, завершения операции ввода-вывода) или истек временной интервал, отведенный ОС для работы этого процесса. После этого ОС по определенному алгоритму выбирает для исполнения один из процессов, находящихся в состоянии процесс не исполняется, и переводит его в состояние процесс исполняется. Новый процесс, появляющийся в системе, первоначально помещается в состояние процесс не исполняется.
Приведенная модель является очень грубой. Она не учитывает, в частности то, что процесс, выбранный для исполнения, может все еще ждать события, из-за которого он был приостановлен, и реально к выполнению не готов. Для того чтобы избежать такой ситуации, разобьем состояние процесс не исполняется на два новых состояния: готовность и ожидание (рис. 10).
Всякий новый процесс, появляющийся в системе, попадает в состояние готовность. Операционная система, пользуясь каким-либо алгоритмом планирования, выбирает один из готовых процессов и переводит его в состояние исполнение. В состоянии исполнение происходит непосредственное выполнение программного кода процесса. Покинуть это состояние процесс может по трем причинам:
· либо он завершает свою деятельность;
· либо в результате возникновения прерывания в вычислительной системе (например, прерывания от таймера по истечении дозволенного времени выполнения) его возвращают в состояние готовность;
· либо он не может продолжать свою работу, пока не произойдет некоторое событие, и ОС (по прерыванию) переводит его в состояние ожидание.
Рисунок 10 – Диаграмма 3-х состояний процесса
Эта модель хорошо описывает поведение процессов во время их жизни, но она не показывает появление процесса в системе и его исчезновение из системы. Поэтому целесообразно показать еще два состояния процессов: рождение и закончил исполнение (рис. 11).
Рисунок 11 – Более детальная диаграмма состояний процесса
Теперь для появления в вычислительной системе процесс должен пройти через состояние рождение. При рождении процесс получает в свое распоряжение адресное пространство, в которое загружается программный код процесса, ему выделяются стек и системные ресурсы; устанавливается начальное значение программного счетчика этого процесса и т.д. Родившийся процесс переводится в состояние готовность. При завершении своей деятельности процесс из состояния исполнение попадает в состояние закончил исполнение.
Следует отметить, что в ОСРВ могут существовать дополнительное состояние приостановлен-готов, в которое процесс может перейти из состояния готовность через дополнительную операцию «приостановки», а вернуться – через «возобновление». Это играет важную роль в ОСРВ и используется в следующих случаях:
· при пиковой нагрузке вычислительной системы, когда она не может обеспечить требуемое быстродействие, при расходах времени на смену состояний, превышающих полезную работу;
· при ненадежной работе системы и возможном ее отказе;
· в случаях, когда промежуточные результаты работы процесса вызывают сомнение в правильности работы программы.
При приостановке процесс обязательно освобождает ОП, его копия сбрасывается на диск в специальный свопинг файл. Также могут быть освобождены и другие ресурсы.
Следует помнить, что количество состояний процесса в различных ОС может быть различно. Например, в ОС Windows NT – 7 состояний, а в ОС Unix – 9 состояний.
Изменением состояния процессов занимается ОС, совершая операции над ними. Основные операции над процессами удобно объединить в три пары:
· создание процесса – завершение процесса (для процесса выполняются однократно);
· приостановка процесса (перевод из состояния исполнение в состояние готовность) – запуск процесса (перевод из состояния готовность в состояние исполнение);
· блокирование процесса (перевод из состояния исполнение в состояние ожидание) – разблокирование процесса (перевод из состояния ожидание в состояние готовность).
Кроме того, следует выделить еще одну – непарную операцию: изменение приоритета процесса.
Указанные операции на процессом выполняются в соответствии с алгоритмом планирования процессов, реализуемым в данной ОС.
4.2.5. Критерии планирования
Критерии планирования
Вообще, планирование – это работа по определению того, в какой момент времени прервать выполнение одного процесса и какому процессу предоставить возможность выполняться. Планирование использования процессора впервые возникает в мультипрограммных вычислительных системах, где в состоянии готовность могут одновременно находиться несколько процессов. Планирование процессов включает в себя решение следующих задач:
· определение момента времени для смены выполняемого процесса;
· выбор процесса на выполнение из очереди готовых процессов;
· переключение контекстов «старого» и «нового» процессов.
В свою очередь, диспетчеризация – это реализация решения, найденного в результате планирования. Задачами диспетчеризации являются:
· сохранение контекста текущего потока;
· загрузка контекста нового потока;
· запуск нового потока на выполнение.
При построении алгоритмов планирования выделяют три различных уровня, которые обуславливают особенности работы этих алгоритмов:
· долгосрочное;
· краткосрочное;
· среднесрочное.
Долгосрочное планирование характеризуется тем, что:
· отвечает за порождение новых процессов в системе, определяя ее степень мультипрограммирования;
· осуществляется достаточно редко (между появлением процессов могут проходить минуты и даже десятки минут);
· оказывает влияние на функционирование вычислительной системы на протяжении достаточно длительного времени;
· в некоторых ОС сведено к минимуму или отсутствует совсем.
Краткосрочное планирование характеризуется тем, что:
· применяется при планировании использования процессора (например, при обращении исполняющегося процесса к устройствам ввода-вывода или по завершении определенного интервала времени);
· осуществляется не реже одного раза в 100 миллисекунд;
· оказывает влияние на функционирование системы до наступления очередного аналогичного события.
Среднесрочное планирование, в свою очередь, характеризуется тем, что применяется в вычислительных системах для повышения производительности при «swapping» .
4.2.6. Цели и свойства алгоритмов планирования
Цели и свойства алгоритмов планирования
Для каждого уровня планирования процессов можно предложить много различных алгоритмов. Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой, и целями, которые должны быть достигнуты планированием. К числу таких целей можно отнести следующие:
· Справедливость. Гарантировать каждому заданию или процессу определенную часть времени использования процессора в компьютерной системе, стараясь не допустить «захвата» процессора одним процессом.
· Эффективность. Постараться занять процессор на 100% рабочего времени, не позволяя простаивать ему в ожидании процессов, готовых к исполнению. В реальных вычислительных системах загрузка процессора составляет 40% - 90%.
· Сокращение полного времени выполнения (англ. turnaround time). Обеспечить минимальное время между стартом процесса или постановкой задания в очередь для исполнения и его завершением.
· Сокращение времени ожидания (англ. waiting time). Сократить время, которое проводят процессы в состоянии готовность в очереди для исполнения.
· Сокращение времени отклика (англ. response time). Минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.
Многие из приведенных выше целей и свойств являются противоречивыми. Улучшая работу алгоритма с точки зрения одного критерия, можно ухудшить его с точки зрения другого, поэтому задача разработчика алгоритма планирования заключается в поиске разумного компромисса.
Кроме целей планирования, которые необходимо достигнуть, желательно также, чтобы алгоритмы обладали следующими свойствами:
· Предсказуемость. Одно и то же задание должно выполняться приблизительно за одно и то же время.
· Минимальные накладные расходы. По сути означает, что tисполнения процесса >> tвыбора процесса. Другими словами, если на каждые 100 миллисекунд, выделенные процессу для использования процессора, будет приходиться 200 миллисекунд на определение того, какой именно процесс получит процессор в свое распоряжение, и на переключение контекста, то такой алгоритм, очевидно, применять не стоит.
· Равномерная загрузка ресурсов вычислительной системы, отдавая предпочтение тем процессам, которые будут занимать малоиспользуемые ресурсы.
· Масштабируемость. Рост количества процессов в системе в два раза не должен приводить к увеличению полного времени выполнения процессов на порядок.
Для достижения целей планирования алгоритмы планирования должны опираться на некоторые характеристики – параметры планирования как вычислительной системы в целом, так и самих процессов.
Среди параметров планирования вычислительной системы выделяют следующие:
· Статические (не изменяемые в ходе функционирования) – предельные значения ресурсов системы: размер оперативной памяти, максимальное количество памяти на диске для осуществления свопинга, количество подключенных устройств ввода-вывода и т.п.).
· Динамические (изменяемые в ходе функционирования) – значения ресурсов системы на текущий момент.
К статическим параметрам процессов относятся характеристики, как правило, присущие заданиям уже на этапе загрузки:
· пользователь, запустивший процесс;
· приоритетность выполнения поставленной задачи;
· соотношение процессорного времени и времени, необходимого для осуществления операций ввода-вывода;
· номенклатура (оперативная память, устройства ввода-вывода, специальные библиотеки и системные программы и т.д.) и величина необходимых заданию ресурсов вычислительной системы.
Алгоритмы долгосрочного планирования процессов используют в своей работе:
· параметры вычислительной системы (статические и динамические);
· статические параметры процессов (динамические параметры процессов на этапе загрузки заданий еще не известны);
Алгоритмы краткосрочного и среднесрочного планирования процессов дополнительно учитывают и динамические характеристики процессов. Для алгоритмов среднесрочного планирования в качестве динамических характеристик может использоваться следующая информация:
· время с момента выгрузки процесса на диск или его загрузки в ОП;
· размер занимаемой процессом ОП;
· количество процессорного времени, предоставленного процессу на данный момент.
4.2.7. Виды планирования
Виды планирования
Существует два основных вида алгоритмов планирования процессов – невытесняющие (non-preemptive, применяются в ОС NetWare) и вытесняющие (preemptive, применяются в ОС Unix, Windows, OS/2, VMS).
Невытесняющая многозадачность (non-preemptive multitasking) – это способ планирования процессов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику ОС для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.
Вытесняющая многозадачность (preemptive multitasking) – это такой способ планирования, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком ОС, а не самим активным процессом.
Алгоритмы планирования могут быть:
· основаны на квантовании;
· основаны на приоритетах.
В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:
· процесс завершился и покинул систему;
· произошла ошибка;
· процесс перешел в состояние «ожидание»;
· исчерпан квант процессорного времени, отведенный данному процессу.
Другая группа алгоритмов основана на понятии приоритет – числе, характеризующем степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени (чем выше приоритет, тем выше привилегии). Приоритет может выражаться целыми или дробными, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом (динамические приоритеты).
Выделяют две разновидности приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами. В обоих случаях выбор потока на выполнение из очереди готовых осуществляется одинаково – выбирается поток, имеющий наивысший приоритет. Отличие заключается в определении момента смены активного потока. В системах с относительными приоритетами активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или произойдет ошибка или поток завершится). В системах с абсолютными приоритетами выполнение активного потока прерывается, если в очереди готовых потоков появился поток, приоритет которого выше приоритета активного потока.
В системах, в которых планирование осуществляется на основе относительных приоритетов, минимизируются затраты на переключение процессора с одной работы на другую. С другой стороны, здесь могут возникать ситуации, когда одна задача занимает процессор долгое время. Ясно, что для систем разделения времени и реального времени такая дисциплина обслуживания не подходит: интерактивное приложение может ждать своей очереди часами, пока вычислительной задаче не потребуется ввод-вывод. А вот в системах пакетной обработки (в том числе известной ОС OS/360) относительные приоритеты использовались широко.
Во многих ОС алгоритмы планирования носят «смешанный» характер и построены как с использованием квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора потока из очереди готовых определяется приоритетами потоков. Именно так реализовано планирование в системе Windows NT, в которой квантование сочетается с динамическими абсолютными приоритетами.
4.2.8. Алгоритмы планирования
Алгоритмы планирования
Рассмотрев цели, свойства и виды алгоритмов планирования, которые могут существовать в вычислительной системе, перейдем к краткому рассмотрению некоторых конкретных алгоритмов планирования (применительно задачам кратковременного планирования).
FCFS. Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия – First Come, First Served (первым пришел, первым обслужен). Схема обслуживания задач согласно этой дисциплине представлена на рис. 12.
Рисунок 12 – Схема обслуживания задач согласно дисциплине FCFS
Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Процесс, получивший в свое распоряжение процессор, занимает его до истечения текущего времени выполнения. После этого для выполнения выбирается новый процесс из начала очереди. Преимуществом алгоритма FCFS является легкость его реализации, недостатками – среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Для подтверждения этого тезиса рассмотрим следующий пример.
Пусть в состоянии готовность находятся три процесса p0, p1 и p2, время выполнения которых в условных единицах, соответственно, составляет t1вып = 13, t2вып = 4 и t3вып = 1 (рис. 13). Для простоты будем полагать, что в выполнение процессов не вмешиваются операции типа ввода-вывода, а временем переключения контекста можно пренебречь.
Рисунок 13 – Временная диаграмма выполнения процессов в порядке p0, p1 и p2
Среднее время ожидания в данном случае можно рассчитать как (0 + 13 + 17)/3 = 10 усл. ед. времени, среднее полное время выполнения составит в этом случае (13 + 17 + 18)/3 = 16 усл. ед. времени.
В то же время, если очередность этих процессов изменить на обратную – p2, p1, p0, то временная диаграмма выполнения будет выглядеть так, как представлено на рис. 14.
Рисунок 14 – Временная диаграмма выполнения процессов в порядке p2, p1 и p0
В этом случае среднее время ожидания будет (5 + 1 + 0)/3 = 2 усл. ед. времени, а среднее полное время выполнения будет (18 + 5 + 1)/3 = 8 усл. ед. времени.
Все это означает, что при изменении очередности выполнения одних и тех же процессов среднее время ожидания уменьшилось в 5 раз, а полное время выполнения – уменьшилось в 2 раза, что подтверждает большую чувствительность алгоритма FCFS к изменению порядка очередности выполнения процессов.
Round Robin. Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (детская карусель) или сокращенно RR. Схематично обслуживание задач согласно алгоритму RR представлено на рис. 15. По сути, это алгоритм FCFS, только реализованный в режиме вытесняющего планирования (очередной процесс передается на исполнение по таймеру по истечении определенного кванта времени).
Рисунок 15 – Схема обслуживания задач согласно дисциплине RR
Можно представить себе все множество готовых процессов организованным циклически – процессы «сидят на карусели». Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени (см. рис. 16). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.
Рекомендация для Вас - 13 - Нарушители и вирусы.
Рисунок 16 – Процессы «на карусели»: а – момент времени t1, б – момент времени t2
На производительность алгоритма RR существенно влияет величина кванта времени – при очень больших величинах кванта алгоритм RR вырождается в алгоритм FCFS, при очень малых – создается иллюзия того, что каждый из n процессов работает на собственном виртуальном процессоре с производительностью ~ 1/n от производительности реального процессора (конечно, если не принимать во внимание время переключения контекста).
Shortest Job First. Если выбирать процесс не по порядку (как в FCFS и RR), а основываясь на его минимальном времени непрерывного использования процессора, то это позволит повысить производительность алгоритма планирования использования процессора. Описанный алгоритм получил название «кратчайшая работа первой» (англ. Shortest Job First, SJF).
Основную сложность при реализации алгоритма SJF представляет невозможность точно знать в каждом случае время исполнения очередного процесса.
