Что такое очередь процессов
Очереди, связанные с диспетчеризацией процессов
Подобно каждому гражданину в известный, ныне ушедший в прошлое период нашей истории, каждый процесс всю свою жизнь проводит в очередях. Для управления процессами ОС организует следующие очереди:
· Очередь заданий (job queue)– cодержит множество всех процессов в системе. В нее попадает каждый новый процесс и остается в ней в течение всего пребывания в системе.
· Очередь готовых процессов (ready queue)– наиболее часто используемая и изменяемая очередь, содержащая множество всех процессов, находящихся в основной памяти и готовых к выполнению. В нее попадает каждый новый процесс, который система допускает к выполнению, а также каждый процесс после выполнения ввода-вывода или наступление ожидаемого события.
· Очереди процессов, ожидающих ввода-вывода (device queues)– множества процессов, ожидающих результата работы устройств ввода-вывода (для каждого устройства организуется своя очередь).
Управление процессами операционной системой и поведение процессов в системе можно рассматривать как миграцию между различными очередями.
На рис. 8.4 изображена схема организации очереди готовых процессов и очередей к устройствам ввода-вывода.
Рис. 8.4.Очередь готовых процессов и очереди к устройствам ввода-вывода.
Схема диспетчеризации процессов и работа с очередями представлена на рис. 8.5.
Рис. 8.5.Графическое представление диспетчеризации процессов.
Из очереди готовых процессов каждый процесс в конце концов попадает на процессор и выполняется. При выполнении могут возникнуть следующие ситуации, при которых выполнение приостанавливается:запрос на синхронный ввод-вывод, исчерпание выделенного процессу кванта времени, прерывание или создание дочернего процесса. Особого пояснения требует, пожалуй, лишь последняя ситуация. В классической схеме UNIX при создании дочернего процесса системным вызовом fork для дочернего процесса создается новое пространство виртуальной памяти, в которую копируется содержимое памяти процесса-родителя. После этого процесс-родитель уступает процессор дочернему процессу. Подобная схема создания дочернего процесса, разумеется, не всегда удобна. Стратегии распараллеливания процессов рассмотрены в следующей лекции.
Планировщики, выполняющие диспетчеризацию процессов
В операционной системе диспетчеризация процессов выполняется обычно несколькими планировщиками,каждый из которых имеет свою периодичность вызовов и свою определенную задачу, которую он решает.
Долговременный планировщик (планировщик заданий)определяет, какие процессы должны быть перемещены в очередь готовых процессов.
Кратковременный планировщик (планировщик процессора)– определяет, какие процессы должны быть выполнены следующими и каким процессам должен быть предоставлен процессор.
Для реализации режима разделения времени в систему может быть добавлен также планировщик откачки и подкачки процессов, определяющий, какие пользовательские процессы должны быть подкачаны впамять или откачаны на диск. Схема работы системы, включающей такой планировщик, изображена на рис. 8.6.
Рис. 8.6.Добавление в систему планировщика откачки и подкачки процессов.
Особенности планировщиков и процессов.Каждый планировщик имеет свои особенности поведения, как и каждый процесс.
Кратковременный планировщиквызывается очень часто, по крайней мере не реже, чем по истечение очередного кванта времени процессора. Поэтому он должен быть очень быстрым, максимально эффективно реализованным. Понятно, что недопустимо, например, если время работы этого планировщика окажется сравнимым с размером самого кванта времени – слишком велики будут накладные расходы.
Долговременный планировщиквызывается относительно редко, так как система не столь часто принимает решения о переводе процесса в очередь готовых процессов. Поэтому он может быть сравнительно медленным, не столь эффективно реализованным.
Однако, поскольку основной задачей системы в целом остается обслуживание как можно большего числа процессов, именно долговременный планировщик определяет степень (коэффициент) мультипрограммирования– число процессов, которое обслуживает система в единицу времени.
Сами процессы также могут вести себя по-разному, с точки зрения их диспетчеризации. Процессы могут быть:
· Ориентированными на ввод-вывод (I/O-bound)– процессы, которые тратят больше времени на ввод-вывод, чем на вычисления. Такие процессы обычно расходуют много коротких квантов процессорного времени.
· Ориентированные на использование процессора (CPU-bound)– процессы, которые тратят основное время на вычисления. Такие процессы расходуют небольшое число долговременных квантов процессорного времени.
Переключение контекста
Когда процессор переключается на другой процесс, система должна сохранить состояние старого процесса и загрузить сохраненное состояние для нового процесса. Такое действие системы называетсяпереключением контекста (context switch).
Переключение контекста относится к накладным расходам (overhead), так как система не выполняет никаких полезных действий при переключении с одного процесса на другой.
Время переключения контекста зависит от аппаратной поддержки. Выше мы рассматривали необходимые действия системы в таких случаях – сохранение состояния приостанавливаемого процесса в его PCB и восстановление состояния возобновляемого процесса из его PCB.
Планирование процессов. Понятие «Очередь»
Распределение между имеющими ресурсами носит название «планирование процессов». Одним из методов планирования процессов ориентированных на эффективную загрузку ресурсов является метод «очередей процессов». Новые процессы находятся во входной очереди называемой очередью задания. Входная очередь располагается во внешней памяти, в ней процессы ожидают освобождение ресурса адресного пространства основной памяти. Готовые к выполнению процессы располагаются в основной памяти и связанны очередью готовых процессов. Процессы в этой очереди ожидают освобождения ресурса – процессорное время.
При прохождении через ПК процесс мигрирует между различными очередями под управлением программы, которая называется «планировщик». Его функции:
1. Отвечает за регистрацию информации о состоянии всех заданий. Для этого ему необходимо иметь информацию о всех заданиях ждущих своей очереди на обработку и о всех состояниях находящихся в работе.
2. Обеспечивает определенные правила выбора заданий на обработку. Для этого ему необходимы следующие характеристики задания:
b. Необходимые ресурсы
c. Равномерные загрузки оборудования вычислительной системы
3. Выделяет необходимые ресурсы для задания поступающего на обработку. Для дэтого программа обращается к ком
4. понентам управления памятью, устройствами, и процессорами.
5. Освобождает ресурсы после выполнения задания.
ОС обеспечивающая режим мультипрограммирования обычно включает 2 планировщика – долгосрочный и краткосрочный.
На уровень долгосрочного планирования выносятся редкие системные действия требующие больших затрат системных ресурсов. На уровень краткосрочного – частые и более короткие процессы.
На каждом уровне существует свой объект и собственные средства управления им.
Основное различие между планировщиками заключается в частоте запуска.
Долгосрочный планировщик решает какой из процессов находящийся во входной очереди должен быть переведен в очередь готовых процессов в случае освобождения ресурсов памяти. Долгосрочный планировщик выбирает процесс из входной очереди с целью создания неоднородной мультипрограммной смеси. Это означает что в очереди готовых процессов должны находиться в разной пропорции как процессы ориентированные на ввод/вывод, так и процессы ориентированные на работу с ЦП. На этом уровне объектом является не отдельный процесс, а некоторое объединение процессов. По функциональному назначению которое называется приложением. Краткосрочный планировщик решает какой из процессов, находящийся в очереди готовых, должен быть передан на выполнение ЦП. В некоторых ОС долгосрочный планировщик может отсутсвовать. На уровне краткосрочного объектом управления являются процессы которые выступают как потребители ЦП для внутренних процессов, или внешнего процессора для внешних процессов. Причиной порождения процессов могут быть процессы на том же уровне или сигналы посылаемые от долгосрочного планировщика. Выделение процессора процессу производится многократно с целью достижения эффекта мультипрограммирования, и такой процесс называется диспетчеризацией.
Планирование процессов. Понятие очереди
Система управления процессами обеспечивает прохождение процесса через компьютер. В зависимости от состояния процесса ему должен быть предоставлен тот или иной ресурс. Например, новый процесс необходимо разместить в основной памяти, следовательно, ему необходимо выделить часть адресного пространства. Процессу в состоянии готовый должно быть предоставлено процессорное время. Выполняемый процесс может потребовать оборудование ввода-вывода и доступ к файлу [14].
Распределение процессов между имеющимися ресурсами носит название планирование процессов. Одним из методом планирования процессов, ориентированных на эффективную загрузку ресурсов, является метод очередей ресурсов. Новые процессы находятся во входной очереди, часто называемой очередью работ — заданий.
Входная очередь располагается во внешней памяти, во входной очереди процессы ожидают освобождения ресурса — адресного пространства основной памяти.
Готовые к выполнению процессы располагаются в основной памяти и связаны очередью готовых процессов. Процессы в этой очереди ожидают освобождения ресурса процессорное время.
Процесс в состоянии ожидания завершения операции ввода-вывода находится в одной из очередей к оборудованию ввода-вывода.
При прохождении через компьютер процесс мигрирует между различными очередями под управлением программы, которая называется планировщик (scheduler).
Операционная система, обеспечивающая режим мультипрограммирования, обычно включает два планировщика — долгосрочный и краткосрочный. Например, в OS/360 долговременный планировщик назывался планировщиком заданий, а краткосрочный — супервизором задач.
На уровень долгосрочного планирования выносятся редкие системные действия, требующие больших затрат системных ресурсов, на уровень краткосрочного планирования — частые и более короткие процессы. На каждом уровне существует свой объект и собственные средства управления им.
Основное отличие между долгосрочным и краткосрочным планировщиками заключается в частоте запуска, например: краткосрочный планировщик может запускаться каждые 100 мс, долгосрочный — один раз за несколько минут.
Долгосрочный планировщик решает, какой из процессов, находящихся во входной очереди, должен быть переведен в очередь готовых процессов в случае освобождения ресурсов памяти.
Долгосрочный планировщик выбирает процесс из входной очереди с целью создания неоднородной мультипрограммной смеси. Это означает, что в очереди готовых процессов должны находиться в разной пропорции как процессы, ориентированные на ввод-вывод, так и процессы, ориентированные на преимущественную работу с CPU.
На уровне долгосрочного планирования объектом является не отдельный процесс, а некоторое объединение процессов по функциональному назначению, которое называется работой (приложением). Каждая работа рассматривается как независимая от других работ деятельность, связанная с использованием одной или многих программ и характеризующаяся конечностью и определенностью. По мере порождения новых работ создается собственная виртуальная машина для их выполнения. Например, в ОС Windows 95 для каждого 32-разрядного приложения реализуется своя виртуальная машина. Распределение машин производится однократно в отличие от краткосрочного планирования, где процессор процессу может выделяться многократно.
Краткосрочный планировщик решает, какой из процессов, находящихся в очереди готовых процессов, должен быть передан на выполнение в CPU. B некоторых операционных системах долгосрочный планировщик может отсутствовать. Например, в системах разделения времени (time-sharing system) каждый новый процесс сразу же помещается в основную память.
На уровне краткосрочного планирования объектом управления являются процессы, которые выступают как потребители центрального процессора для внутренних процессов или внешнего процессора для внешних процессов. Причинами порождения процесса могут быть процессы на том же уровне или сигналы, посылаемые от долгосрочного планировщика.
Выделение процессора процессу производится многократно, с целью достижения эффекта мультипрограммирования, и такой процесс называется диспетчеризацией.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Многозадачность ОС в разрезе системы массового обслуживания
Мне бы хотелось рассказать немного о многозадачности операционной системы. О концепте управления процессами и потоками с точки зрения ОС (и процессора/процессоров) как системы массового обслуживания. О том, «как это происходит».
Процессов ведь много, а ресурсы ограничены. На всех сразу не хватает. Что же делать? И вот тут возникает аналогия с системой массового обслуживания. Можно представить пул процессов как очередь в кассу. Ой, простите, в процессор. И архаичных вариантов обработки такой очереди [мне известно] три.
Предислование
Изначально я буду ориентироваться на то, что процессор один. Для упрощения. Потом расскажу, в чем, на мой, взгляд разница.
Для начала: общие сведения.
Картинка процессора
Что же такое «процесс» и в чем его отличие от «потока»? Процесс — это (грубо говоря) — заявка на реализацию чего-либо. Точнее, на потребление системных ресурсов. ОС генерирует системную информацию, в которой говорит, какие необходимы это процессу ресурсы. А так же о тех ресурсах, которые ему фактически были выделены. И это — для каждого вновь создаваемого процесса отдельно. О том, сколько ему необходимо памяти, сколько процессорного времени, и т.д.
Так о чем же я? Ах, да.
О способах обработки очереди процессов
Архаичных способов обработки очереди, как я говорила, мне известно три.
Т.е., каждому процессу выделяется определенный квант времени, после которого процессор радостно рапортует: «Свободная касса!», и получает на обслуживание следующий процесс. Текущий процесс же идет в конец очереди. Ибо «все равны». Недостатки: (грубый пример) у Вас идет видеоконференция. Очень важная. Прямо на самом интересном месте: бабах! И начинает печатается «важный» документ. Он же письмо с просьбой перенести время доставки ежедневного обеда с 13:00 на 14:00. А Ваша видеоконференция «неизвестно когда» будет возобновлена. Конечно, на практике так не бывает, потому что принтер работает по прерыванию, и там вообще все иначе. Но аналогия, мне кажется, в целом ясна.
Это когда «не все равны». Процессу назначается приоритет, и пока процесс с более высоким приоритетом не будет обслужен (ой, простите, обработан), другие к кассе (ой, простите, к процессору) подойти не смогут. Недостатки: могут быть процессы, которые из-за низкого приоритета не обработаются вообще никогда. Т.е., письмо Вы так никогда и не распечатаете.
На практике же зачастую используется подход «все равны, но некоторые ровнее». Т.е., «смешанный». Когда процессу выделяется квант времени и приоритет одновременно. Тогда процесс уходит не в конец очереди, а куда-то в «свою» середину. И там ждет.
Схема ясна, но как же обрабатываются процессы? В какой очередности? Тут все та же система массового обслуживания. Есть несколько подходов к обработке процессов в случае квантования и «смешанного» типа:
— FIFO. Первый пришел, первый вышел. (First-In-First-Out)
— LIFO. Последний пришел, первый вышел. (ИМХО, не очень честно… ) (Last-In-First-Out)
— SIRO. Ну, тут полный рандом. Service-In-Random-Out.
В случае «чистых» приоритетов таких вопросов не возникает, ясное дело.
А что же там с многопроцессорными системами?
Ведь я обещала поделиться своими мыслями на этот счет. Ну, давайте представим, что касс (процессоров) несколько. И тут те же принципы, только либо несколько очередей, и процессы попадают в рандомном или не очень порядке в очередь (что мне кажется не очень логичным, ну, например, хотя бы потому, что на новых процессорах по прежнему работают «однопроцессорные» системы). Либо так же очередь (пул, из которого берутся процессы) — одна, а обрабатывают их несколько касс. Но это исключительно мысли автора, не более того.
Может возникнуть вполне резонный вопрос.
А в чем же все-таки отличие процесса от потока?
А все просто. В начале статьи вскользь упоминалось, что программе для выполнения необходимы ресурсы и процессорное время. Так вот, система «воспринимает» процесс как заявку на любые виды ресурсов, кроме процессорного времени. Заявка на процессорное время — это поток. Именно процессорное время распределяется между потоками. Таким образом, процесс состоит из нескольких потоков. Раньше, конечно, это все было единое целое. И процесс, и поток, и все в одном, и вообще, «зачем платить больше?». Как оказалось, в данном случае мы, скорее, «платим меньше». Когда потоков несколько.
Для того, чтобы процессы не могли вмешиваться в распределение ресурсов, система их «изолирует». Предоставляет каждому из них своё виртуальное адресное пространство. Так что ни один процесс не может получить прямого доступа к командам и данным другого процесса.
При необходимости взаимодействия процессы обращаются к ОС, в буквальном смысле, как к посреднику. А она уже им помогает, выдаёт средства связи.
А вот между потоками одного и того же процесса нет полной защиты. Потому что это не только невозможно, но и никому не нужно. Чтобы обмениваться данными потокам вовсе не обязательно обращаться к ОС. Они используют общую память. Один записывает данные, другой читает. И все хорошо. Кроме того, потоки разных процессов по-прежнему хорошо защищены друг от друга.
Мультипрограммирование более эффективно на уровне потоков, а не процессов. Каждый поток имеет свой счетчик команд и стек. Задача, оформленная в виде нескольких потоков может быть выполнена быстрее за счет параллельного (или псевдопараллельного в однопроцессорной системе) выполнения её частей.
Очевидные выводы
Процесс — это заявка на потребление всех ресурсов, кроме процессорного времени. Процессы изолированы друг от друга, и включает в себя потоки. Собственно, потоки — это заявки на потребление этого самого процессорного времени.
Наибольший эффект от введения многопоточной обработки достигается в мультипроцессорных системах, в которых потоки (даже в рамках одного процесса) могут выполняться действительно параллельно, а не псевдо.
Ко всему прочему, был продемонстрировано на примере непосредственно концепт работы системы [массового обслуживания] как таковой.
Я немного «смахлевала» в начале и в середине статье, рассказывая по поводу процессорного времени для «процесса» как такового. Но не сильно, и, я надеюсь, Вы меня простите за эту вынужденную неточность.
Управление процессами. Планирование и диспетчеризация процессов
Ключевые термины
Диспетчеризация – поочередное выделение процессам планировщиком операционной системы квантов процессорного времени.
Ориентированный на ввод-вывод (I/O-bound) – процесс, который тратит больше времени на ввод-вывод, чем на вычисления.
Ориентированный на использование процессора (CPU-bound) – процесс, который тратит основное время на вычисления.
Очереди процессов, ожидающих ввода-вывода (device queues) – множества процессов, ожидающих результата работы устройств ввода-вывода (для каждого устройства организуется своя очередь ).
Переключение контекста (context switch) – действия ОС при переключении с одного процесса на другой по сохранению состояния старого процесса и загрузки сохраненного состояния для нового процесса.
Поток управления (control flow) – последовательность выполняемых процессом команд.
Процесс (process)– программа пользователя при ее выполнении.
Степень (коэффициент) мультипрограммирования – число процессов, которое обслуживает система в единицу времени.
Краткие итоги
Для управления процессами ОС использует следующие очереди: очередь заданий (всех процессов в системе), очередь готовых к выполнению процессов, очереди (к каждому устройству) процессов, ожидающих ввода-вывода.
По их поведению процессы можно классифицировать как ориентированные на ввод-вывод и ориентированные на вычисления (использование процессора).
Переключение контекста (время, расходуемое ОС при переключении с одного процесса на другой) относится к накладным расходам системы. Оно зависит от аппаратной поддержки.