Взаимодействие процессов
Совместно выполняемые процессы могут быть либо независимыми, либо взаимодействующими. Взаимодействие процессов часто понимается в смысле взаимного обмена данными через общий буфер данных.
Взаимодействие процессов удобно рассматривать в схеме производитель-потребитель.
Например, программа вывода на печать производит последовательность символов, которые потребляются драйвером принтера, или компилятор производит ассемблерный текст, который затем потребляется ассемблером.
Для взаимодействия процесса-производителя и процесса-потребителя создается совместный буфер, заполняемый процессом-производителем и потребляемый процессом-потребителем.
Буфер имеет фиксированные размеры и, следовательно, процессы могут находиться в состоянии ожидания, когда:
• буфер заполнен — ожидает процесс-производитель;
• буфер пуст — ожидает процесс-потребитель.
Буфер может предоставляться и поддерживаться самой ОС, например с помощью средств межпроцессной коммуникации, либо должен быть организован прикладным программистом.
При этом оба процесса используют общий участок памяти. Взаимодействие заключается в передаче данных между процессами или совместном использовании некоторых ресурсов и обычно реализуется с помощью таких механизмов, как т р а н с по р т е р ы , о ч е р е д и , с и г н а л ы , с е м а ф о р ы .
Транспортеры (каналы). Являются средством взаимодействия родственных процессов, представляют собой область памяти, имеющую файловую организацию, для которой обеспечивается запись и считывание данных в транспортере. Реализуется очередь обслуживания. Порядок записи данных на транспортер неизменен, не допускается повторное считывание данных. Обмен данными происходит не непосредственно, а через транспортер. Из вызвавшего процесса задается размер транспортера. Дочерние процессы могут использовать родительский транспортер.
Очереди. Эти механизмы могут обеспечивать передачу или использование общих данных без перемещения данных, а с передачей элемента очереди, содержащего указатель данных и объем
массива данных. Очередь используется вместе с механизмом общей памяти. Элемент очереди может быть считан с уничтожением или без уничтожения этого элемента. Чтение элемента может осуществляться в соответствии с механизмом очереди или стека. Чтение элементов очереди осуществляет только создающий
очереди процесс, все другие процессы могут только записать элемент в очередь. Создающий процесс может выполнять следующие действия над очередью:
· обработка системной ошибки при появлении сигнала,
· блокирование сигнала,
· передача управления подпрограмме.
Семафоры. Являются механизмами передачи сообщений от одного потока к другому о наступлении некоторого события. Различают семафоры системные и оперативной памяти. Семафоры оперативной памяти - двойное слово в памяти системы, его описатель - адрес места в памяти. Такие семафоры не создаются и не открываются, а устанавливаются в определенное состояние. Процессы, использующие семафоры оперативной памяти, должны иметь доступ к соответствующему сегменту памяти. Операционная система такие семафоры не обслуживает и не сообщает об их освобождении или захвате. При создании семафора или его открытии возвращается описатель семафора, включающий его имя. Операционная система контролирует завершение каждого процесса, владеющего системным семафором, и освобождает его для процессов. Если семафор свободен, то он захватывается вызывающим его процессом, если семафор занят, то вызвавший его поток пе реходит в режим ожидания освобождения семафора или ожидает истечения времени. Если семафор освобождается всеми использующими его процессами, то он удаляется из системы.
Управление семафором реализуется с помощью функций:
· установки семафора с целью сигнализации;
· ожидания вызывающим потоком, пока семафор не будет выключен;
· ожидания потоком выключения одного из нескольких семафоров.
Операционные системы используют разные термины для определения способов межпроцессного взаимодействия. В операционных системах OS/2 и Microsoft Windows существует специальный механизм для взаимодействия процессов в реальном масштабе времени. Этот механизм называется DDE (Dynamic
Data Exchange — динамический обмен данными). Он стандартизирует процесс обмена командами, сообщениями и объектами для обработки между задачами. Наиболее распространенным процессом,
для которого используется DDE, является печать.
Другим интерфейсом для обмена данными является OLE (Object Linking and Embedding — связывание и встраивание объектов). Этот интерфейс позволяет хранить объекты, созданные одной программой, в объектах, созданных другой программой, а также редактировать (печатать) их без нарушения целостности
информации и связей. Одним из наиболее простых, удобных и интуитивных интерфейсов
межпрограммного взаимодействия является буфер обмена — clipboard. Буфер обмена может содержать в себе один информационный объект — фрагмент текста, рисунок и т. д.
С помощью системного вызова процесс может получить копию информации, содержащейся в буфере обмена, или сам поместить объект в буфер, при этом старое содержимое буфера теряется. Таким образом, программы получают простой, но эффективный способ обмена информацией в процессе своей работы.
Планирование работы процессора
Краткосрочный планировщик выбирает процессы из очереди готовых процессов и передает их на выполнение в CPU. Существуют различные алгоритмы или стратегии решения этой задачи, различающиеся отношением к критериям планирования.
Известны следующие критерии, позволяющие сравнивать алгоритмы краткосрочных планировщиков:
• утилизация CPU (использование процессора). Утилизация CPU теоретически может находиться в пределах от 0 до 100 %. В реальных системах утилизация CPU колеблется в пределах 40 % для легко загруженного CPU, 90 % для тяжело загруженного CPU;
• пропускная способность CPU. Пропускная способность CPU может измеряться количеством процессов, которые выполняются в единицу времени;
• время оборота. Для некоторых процессов важным критерием является полное время выполнения, т. е. интервал от момента появления процесса во входной очереди до момента его завершения. Это время названо временем оборота и включает время ожидания во входной очереди, время ожидания в очереди готовых процессов, время ожидания в очередях к оборудованию, время выполнения в процессоре и время ввода-вывода;
• время ожидания — под этим понимается суммарное время нахождения процесса в очереди готовых процессов;
• время отклика — для интерактивных программ важным показателем является время отклика или время, прошедшее от момента попадания процесса во входную очередь до момента первого обращения к терминалу.
Очевидно, что простейшая стратегия краткосрочного планировщика должна быть направлена на максимизацию средних значений загруженности и пропускной способности, времени ожидания и времени отклика.
В ряде случаев используются сложные критерии, например так называемый минимаксный критерий* т. е. вместо простого критерия минимум среднего времени отклика используется минимум максимального времени отклика.
Стратегии планирования
«Первый пришел — первый обслуживается» (FIFO — first in, first out, или FCFS — first come, first served). FCFS является наиболее простой стратегией планирования процессов и заключается в том, что процессор передается тому процессу, который раньше всех других его запросил.
Когда процесс попадает в очередь готовых процессов, УТП (РСВ) присоединяется к хвосту очереди. Среднее время ожидания для стратегии FCFS часто весьма велико и зависит от порядка поступления процессов в очередь готовых процессов. Стратегии FCFS присущ так называемый «эффект конвоя». В том случае, когда в компьютере имеется один большой процесс и несколько малых, то все процессы собираются в начале очереди готовых процессов, а затем в очереди к оборудованию. Таким образом, «эффект конвоя» приводит к снижению загруженности как процессора, так и периферийного оборудования.
Стратегия «наиболее короткая работа выполняется первой SJF — Shortest Job First. Одним из методов борьбы с «эффектом конвоя» является стратегия, позволяющая процессу из очереди выполняться первым. Стратегия SJF снижает время ожидания очереди. Наибольшая трудность в практической реализации SJF заключается в невозможности заранее определить величину времени последующего обслуживания.
Поэтому стратегия SJF часто применяется в долгосрочных планировщиках, обслуживающих пакетный режим. В этом случае вместо величины времени последующего обслуживания используется допустимое максимальное время выполнения задания, которое программист должен специфицировать перед отправкой задания в пакет.
Приоритетное планирование. Описанные ранее стратегии могут рассматриваться как частные случаи стратегии приоритетного планирования. Эта стратегия предполагает, что каждому процессу приписывается приоритет, определяющий очередность предоставления ему CPU. Например, стратегия FCFS предполагает, что все процессы имеют одинаковые приоритеты, а стратегия SJF предполагает, что приоритет есть величина, обратная времени последующего обслуживания.
Обычно приоритет — это целое положительное число, находящееся в некотором диапазоне, например от 0 до 7 или от 0 до 1024. Будем считать, что чем меньше значение числа, тем выше приоритет процесса. Приоритеты назначаются, исходя из совокупности внутренних и внешних по отношению к операционной системе факторов.
Внутренние факторы:
• требования к памяти;
• количество открытых файлов;
• отношение среднего времени ввода-вывода к среднему времени использования ресурсов CPU и т. д.
Внешние факторы:
• важность процесса;
• тип и величина файлов, используемых для оплаты;
• отделение, выполняющее работы, и т. д.
Внутренние факторы могут использоваться для автоматического назначения приоритетов самой операционной системой, а внешние — для принудительного, с помощью оператора.
Главный недостаток приоритетного планирования заключается в возможности блокирования на неопределенно долгое время низкоприоритетных процессов.
Известен случай, когда в 1973 г. в Массачусетском технологическом институте при остановке компьютера IBM 7094 в очереди готовых процессов были обнаружены процессы, активизированные в 1967 г., но так и не выполненные.
Для устранения отмеченного недостатка используются следующие методы: процессы, время ожидания которых превышает фиксированную величину, например 15 минут, автоматически получают единичное приращение приоритета.
«Карусельная» стратегия планирования RR-Round Robin применяется в системах разделения времени. Определяется небольшой отрезок времени tk, названный квантом времени (10......100 мс). Очередь готовых процессов рассматривается как кольцевая. Процессы циклически перемещаются по очереди, получая CPU на время, равное одному кванту. Новый процесс добавляется в хвост очереди. Если процесс не завершился в пределах выделенного ему кванта времени, его работа принудительно прерывается, и он перемещается в хвост очереди.
Свойства стратегии Round Robin сильно зависят от величины временного кванта tk. Чем больше временной квант, тем ближе стратегия Round Robin приближается к FCFS-стратегии. При очень малых значениях временного кванта Round Robin-стратегию называют разделением процессора — processor sharing. Теоретически это означает, что каждый из N процессов работает со своим собственным процессором, производительность процессора равна 1 /N от производительности физического процессора.
Планирование с использованием многоуровневой очереди (Multilevel queue scheduling). Эта стратегия разработана для ситуации, когда процессы могут быть легко классифицированы на несколько групп, например часто процессы разделяют на две группы: интерактивные (процессы переднего плана) и пакетные (фоновые).
Интерактивные и пакетные процессы имеют различные требования к краткосрочному планировщику, например по отношению ко времени отклика.
Стратегия многоуровневой очереди разделяет очередь готовых процессов на несколько очередей, в каждой из которых находятся процессы с одинаковыми свойствами, и каждый из которых может планироваться индивидуальной стратегией, например Round, Robin стратегия для интерактивных процессов и FCFS для пакетных процессов.
Взаимодействие очередей осуществляется по следующим правилам: ни один процесс с более низким приоритетом не может быть запущен, пока не выполнятся процессы во всех очередях с более высоким приоритетом.
Работа процесса из очереди с более низким приоритетом может быть приостановлена, если в одной из очередей с более высоким приоритетом появился процесс.
Использование многоуровневой очереди с обратными связями (multilevel feedback queue sheduling) .
Многоуровневая очередь с обратными связями
Обычная многоуровневая очередь не допускает перемещения процессов между очередями. Многоуровневая очередь с обратными связями предполагает, что процессы при определенных условиях могут перемещаться между очередями. Здесь организуется N очередей. Все новые запросы поступают в конец первой очереди. Первый запрос из i-й очереди поступает на обслуживание лишь тогда, когда все очереди от1-й до i - 1-й пустые. На обслуживание выделяется квант времени tk. Если за это время обслуживание запроса завершается полностью, то он покидает систему. В противном случае недообслуженный запрос поступает в конец i+ 1-й очереди. После обслуживания запроса из i-й очереди система выбирает для обслуживания запрос из непустой очереди с самым младшим номером. Недостаток системы заключается в затратах времени на перемещение запросов из одной очереди в другую.
Данная стратегия является универсальной и сочетает в себе свойства всех рассмотренных раньше стратегий — FCFS, SJF, приоритетная, Round Robin, многоуровневая очередь.
Приоритетная многоочередная дисциплина обслуживания (рис. 1.13). Вновь поступающие в систему запросы устанавливаются не обязательно в 1-ю очередь, а в очередь в соответствии с имеющимися п р и о р и т е т а м и , которые определяются параметрами обслуживания процессов. Приоритетные многоочередные дисциплины обслуживания могут использовать обслуживание с абсолютным и относительным приоритетом. При обслуживании с абсолютным приоритетом приоритет определяется номером очереди, и первыми обслуживаются запросы, обладающие наивысшим приоритетом (из очереди с меньшим номером запрос из очереди / - 1 будет прерывать обработку запроса из очереди /).
В данной дисциплине еще более увеличивается степень дискриминации по среднему времени ожидания в очереди между высоко- и низкоприоритетными запросами. Время ожидания высокоприоритетных заявок сокращается, но за счет большей задержки в обслуживании низкоприоритетных заявок. Достигается это за счет усложнения логики системы, дополнительной обработки запросов и выбора правила дообслуживания прерываемых процессов. Обслуживание с относительным приоритетом не вызывает прерывания обслуживаемой заявки до ее завершения, даже если она менее приоритетная.
Тема 2. 2 Планирование и диспетчеризация процессов и задач.
1. Планирование и диспетчеризация процессов и задач.
2. Качество диспетчеризации и гарантии обслуживания.
3. Диспетчеризация задач с использованием динамических приоритетов.
Планирование и диспетчеризация процессов и задач
Операционная система выполняет следующие основные функции, связанные с управлением процессами и задачами:
· создание и удаление задач;
· планирование процессов и диспетчеризация задач;
· синхронизация задач, обеспечение их средствами коммуникации.
Решение вопросов, связанных с тем, какой задаче следует предоставить процессор в данный момент, возлагается на специальный модуль операционной системы, чаще всего называемый диспетчером задач. Вопросы же подбор вычислительных процессов, которые не только можно, но и целесообразно решать возлагаются на планировщик процессов.
Иногда диспетчеризацию называют краткосрочным планированием.
В большинстве современных операционных систем, с которыми мы сталкиваемся, долгосрочный планировщик отсутствует.
Иногда используют термин стратегия обслуживания.
Стратегия планирования определяет, какие процессы мы планируем на выполнение для того, чтобы достичь поставленной цели. Среди стратегий, прежде всего, можно выбрать следующие:
• по возможности заканчивать вычисления (вычислительные процессы) в том же самом порядке, в котором они были начаты;
• отдавать предпочтение более коротким вычислительным задачам;
• предоставлять всем пользователям (процессам пользователей) одинаковые услуги, в том числе и одинаковое время ожидания.
Дисциплины диспетчеризации (дисциплины обслуживания) – правила формирования очереди готовых к выполнению задач.
Различают два больших класса дисциплин обслуживания: бесприоритетные и приоритетные.
При бесприоритетном обслуживании выбор задачи производится в некотором заранее установленном порядке без учета их относительной важности и времени обслуживания.
При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право попасть в состояние исполнения.
В концепции приоритетов имеем следующие варианты:
• приоритет, присвоенный задаче, является величиной постоянной;
• приоритет изменяется в течение времени решения задачи (динамический приоритет).
Диспетчеризация с динамическими приоритетами требует дополнительных расходов на вычисление значений приоритетов исполняющихся задач, поэтому во многих операционных системах реального времени используются методы диспетчеризации на основе абсолютных приоритетов.
Наиболее часто используемые дисциплины диспетчеризации.
1. FCFS (First Come First Served – первым пришел, первым обслужен) – задачи обслуживаются в порядке их появления. Те задачи, которые были заблокированы в процессе работы после перехода в состояние готовности вновь ставятся в эту очередь готовности. При этом возможны два варианта:
• ставить разблокированную задачу в конец очереди готовых к выполнению задач.
• диспетчер помещает разблокированную задачу перед теми задачами, которые еще не выполнялись. Образуется две очереди: одна очередь образуется из новых задач, а вторая очередь — из ранее выполнявшихся, но попавших в состояние ожидания.
2. SJN (Shortest Job Next — следующим выполняется самое короткое задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. Задания, которые в процессе своего исполнения были временно заблокированы (например, ожидали завершения операций ввода-вывода), вновь попадали в конец очереди готовых к выполнению наравне с вновь поступающими.
3. SRT (Shortest Remaining Time) — следующим будет выполняться задание, которому осталось меньше всего выполняться на процессоре.
4. Карусельная дисциплина обслуживания RR (Round Robin) – каждая задача получает процессорное время квантами времени (time slice) q. После окончания кванта времени q задача снимается с процессора, и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению. Величина кванта времени q выбирается как компромисс между приемлемым временем реакции системы на запросы пользователей и накладными расходами на частую смену контекста задач.
Невытесняющая (non-preemptive multitasking), или кооперативная многозадачность (cooperative multitasking), — это способ диспетчеризации задач, при котором активная задача выполняется до тех пор, пока она сама, «по собственной инициативе», не отдаст управление диспетчеру задач для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс или поток. FCFS, SJN, SRT относятся к невытесняющим.
Вытесняющая многозадачность (preemptive multitasking), —решение о переключении процессора с выполнения одной задачи на выполнение другой принимается диспетчером задач, а не самой активной задачей. RR и другие, построенные на ее основе, относятся к вытесняющим.