2009 overview ИУС РВ (1185197), страница 5
Текст из файла (страница 5)
2) загруженность процессора составила 0,808, алгоритм RMS ещеработал, хотя с другими периодами и временем обработки при том же коэффициентезагруженности процессора мог потерпеть неудачу. При увеличении коэффициентазагруженности на алгоритм RMS не было надежды.Время, мсAA1BB1A2A3B2C C1A1B1EDFA1B11020A2C1B43040C3НеудачаB2A2B250A5B3C2RMS0A460A370C280B390A4100110C3120A5130B4140Рис.
3. Пример, в котором алгоритм RMS не может быть использованДругим популярным алгоритмом планирования является алгоритм EDF (Earliest DeadlineFirst – процесс с ближайшим сроком завершения в первую очередь). Алгоритм EDFпредставляет собой динамический алгоритм, не требующий от процессов периодичности. Онтакже не требует и постоянства временных интервалов использования процессора.
Каждый раз,когда процессу требуется процессорное время, он объявляет о своем присутствии и о своемсроке выполнения задания. Планировщик хранит список процессов, сортированный по срокамвыполнения заданий. Алгоритм запускает первый процесс в списке, то есть тот, у которогосамый близкий по времени срок выполнения. Когда новый процесс переходит в состояниеготовности, система сравнивает его срок выполнения со сроком выполнения текущегопроцесса.
Если у нового процесса график более жесткий, он прерывает работу текущегопроцесса.Пример работы алгоритма EDF показан на рис. 2. Вначале все процессы находятся всостоянии готовности. Они запускаются в порядке своих крайних сроков. Процесс A долженбыть выполнен к моменту времени 30, процесс B должен закончить работу к моменту времени40, процесс C – 50. Таким образом, процесс A запускается первым. Вплоть до момента времени90 выбор алгоритма EDF не отличается от RMS. В момент времени 90 процесс A переходит всостояние готовности с тем же крайним сроком выполнения 120, что и у процесса B.Планировщик имеет право выбрать любой из процессов, но поскольку с прерыванием процессаB не связано никаких накладных расходов, лучше предоставить возможность продолжатьработу этому процессу.Рассмотрим рис.
3. В момент времени 30 между процессами A и C возникает спор.Поскольку срок выполнения процесса C равен 50 мс, а процесса A – 60 мс, планировщиквыбирает процесс C. Этим данный алгоритм отличается от алгоритма RMS, в которомпобеждает процесс A, как обладающий большим приоритетом. В момент времени 90 процесс Aпереходит в состояние готовности в 4 раз. Предельный срок процесса A такой же, что и утекущего процесса, поэтому у планировщика появляется выбор – прервать работу процесса Bили нет. Поскольку необходимости прерывать процесс B нет, то он продолжает работу.Алгоритм EDF работает с любым набором процессов, для которых возможнопланирование.
Платой за это является использование более сложного алгоритма.Межпроцессное взаимодействие. Ресурсы, их характеристики. Состязание процессов.Критические области. Взаимное исключение. Проблемы взаимодействия процессов.Межпроцессное взаимодействие – это тот или иной способ передачи информации изодного процесса в другой. Наиболее распространенными формами взаимодействия являются:1. Разделяемая память – два или более процесса могут иметь доступ к одному и томуже блоку памяти.
В системах с виртуальной памятью организация такого видавзаимодействия требует поддержки со стороны операционной системы, посколькунеобходимо отобразить соответствующие блоки виртуальной памяти на один и тот жеблок физической памяти.2. Семафоры – два и более процесса имеют доступ к одной переменной, принимающейзначение 0 или 1. Сама переменная часто находится в области данных операционнойсистемы и доступ к ней организуется с помощью специальных функций.3. Сигналы – это сообщения, доставляемые посредством операционной системыпроцессу. Процесс должен зарегистрировать обработчик этого сообщения уоперационной системы, чтобы получить возможность реагировать на него. Частооперационная система извещает процесс сигналом о наступлении какого-либо сбоя,например, делении на 0, или о каком-либо аппаратном прерывании, например,прерывании таймера.4.
Почтовые ящики – это очередь сообщений (обычно – тех или иных структур данных),которые помещаются в почтовый ящик процессами и/или операционной системой.Несколько процессов могут ждать поступления сообщения в почтовый ящик иактивизироваться по поступлении сообщения. Требует поддержки со стороныоперационной системы.Во многих ОСРВ компоненты операционной системы, также как и пользовательскиезадачи, способны принимать и передавать сообщения. Сообщения могут быть асинхроннымии синхронными. В первом случае доставка сообщений задаче производится после того, как онав плановом порядке получит управление, а во втором случае циркуляция сообщений оказываетнепосредственное влияние на планирование задач. Например, задача, пославшая какое-либосообщение, немедленно блокируется, если для продолжения работы ей необходимо дождатьсяответа, или если низкоприоритетная задача шлет высокоприоритетной задаче сообщение,которого последняя ожидает, то высокоприоритетная задача, если конечно, используетсяприоритетная многозадачность с вытеснением, немедленно получит управление.
Иногдасообщения передаются через буфер определенного размера (почтовый ящик). При этом, какправило, новое сообщение затирает старое, даже если последнее не было обработано.Однако наиболее часто используется принцип, когда каждая задача имеет свою очередьсообщений, в конец которой ставится всякое вновь полученное сообщение. Стандартныйпринцип обработки очереди сообщений по принципу FIFO не всегда оптимально соответствуетпоставленной задаче. В некоторых ОСРВ предусматривается такая возможность, когдасообщение от высокоприоритетной задачи обрабатывается в первую очередь (в этом случаеговорят, что сообщение наследует приоритет пославшей его задачи).Общие ресурсы.Ресурс - это общий термин, описывающий объект (физическое устройство, областьпамяти), который может одновременно использоваться только одной задачей.По своим характеристикам ресурсы разделяют на:• активные – способны изменить информацию (процессор)• пассивные – способны хранить информацию• локальные – принадлежат одному процессу; время жизни совпадает с временемжизни процесса• разделяемые – могут быть использованы несколькими процессами; существуют, покаесть хоть один процесс, который их использует• постоянные – используются посредством операций «захватить» и «освободить»• временные – используются посредством «создать» и «удалить».Разделяемые ресурсы бывают:• не критичные – могут быть использованы одновременно несколькими процессами(например, жесткий диск)• критичные – могут быть использованы только одним процессом, и пока этот процессне завершит работу с ресурсом, последний не доступен другим процессам (например,разделяемая память, доступная на запись).По типу взаимодействия различают:• сотрудничающие процессы:- процессы, разделяющие только коммуникационный канал, по которому одинпередает данные, а другой получает их;- процессы, осуществляющие взаимную синхронизацию: когда работает один,другой ждет окончания его работы (типично для программ, управляющих рядомтехнологических процессов)• конкурирующие процессы:- процессы, использующие совместно разделяемый ресурс;- процессы, использующие критические секции;- процессы, использующие взаимные исключения.Представим, например, что несколько процессов пытаются одновременно выводитьданные на принтер.
Если процессу требуется вывести на печать файл, он помещает его имя вспециальный каталог спулера. Другой процесс, демон печати, периодически проверяет наличиефайлов, которые нужно печатать, печатает файл и удаляет его имя из каталога. Пусть каталогспулера состоит из большого числа пронумерованных сегментов, в каждом из которых можетхраниться имя файла. Также есть две совместно используемые (и доступные всем процессам)переменные – out, указывающая на следующий файл для печати, и in, указывающая наследующий свободный сегмент.
Процессы A и B одновременно пытаются поставить файлы вочередь на печать. Процесс A считывает значение переменной in и сохраняет его в локальнойпеременной. После этого происходит прерывание по таймеру, и процессор переключается напроцесс B. Он, в свою очередь, также считывает значение переменной in и сохраняет его всвоей локальной переменной. Процесс B сохраняет в каталоге спулера имя файла и увеличиваетна 1 значение переменной in. После того как управление перейдет к процессу A, он продолжитвыполнение с того места, где был прерван. Он обращается к своей локальной переменной,хранящей старое значение переменной in, считывает ее значение и записывает имя файла в тотже сегмент, что и процесс B, а затем изменяет значение in.
Структура каталога не нарушена, нофайл процесса B не будет напечатан. Ситуация, в которой два процесса считывают илизаписывают данные одновременно и конечный результат зависит от того, какой процесс былпервым, называется состоянием состязания. Основным способом предотвращения состояниясостязания является запрет использования совместно используемых данных одновременнонескольким процессам.Критическая секция (области) – это участок программы, в котором есть обращение ксовместно используемым данным. На этом участке запрещается переключение задач дляобеспечения исключительного использования ресурсов процессом.
Все ОСРВ предоставляютвызовы «войти в критическую секцию» и «выйти из критической секции».Взаимное исключение (mutual exclusion, mutex) – это способ синхронизациипараллельно работающих процессов, использующих разделяемый постоянный критичныйресурс. Если ресурс занят, то системный вызов «захватить ресурс» переводит процесс изсостояния выполнения в состояние ожидания. Когда ресурс будет освобожден посредствомсистемного вызова «освободить ресурс», то этот процесс вернется в состояние выполнения ипродолжит работу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
