Синхронизация процессов с помощью операций проверки и установки

Операция проверки и установки является, так же как и блокировка памяти, одним из аппаратных средств, которые могут быть использованы для решения задачи взаимного исключения при выполнении критической секции. Данная операция реа­лизована во многих компьютерах. Так, в знаменитой машине IBM 360 (370) эта команда называлась TS (Test and Set — проверка и установка).

Команда TS являет­ся двухадресной (двухоперандной). Ее действие заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Команда TS является неделимой опера­цией, то есть между ее началом и концом не могут выполняться никакие другие команды.

Чтобы использовать команду TS для решения проблемы критической секции, свя­жем с ней некоторую переменную П1, которая будет общей для всех процессов, исполь­зующих некоторый критический ресурс. Данная переменная будет принимать еди­ничное значение, если какой-либо из взаимодействующих процессов находится в своей критической секции.

Кроме того, с каждым процессом свяжем свою ло­кальную переменную, которая принимает значение, равное единице, если данный процесс хочет войти в свою критическую секцию.

Основной недостаток использования команд типа проверки и установки состоит в следующем: находясь в цикле проверки переменной common, процессы впустую потребляют время центрального процессора и другие ресурсы.

В микропроцессорах архитектуры ia32, с которыми мы теперь сталкиваемся по­стоянно, работая на персональных компьютерах, имеются специальные команды ВТС, BTS, BTR, которые как раз и являются вариантами реализации команды провер­ки и установки.

 

5.2.3 Семафорные примитивы Дейкстры

Понятие семафорных механизмов было введено Дейкстрой.

Семафор (semaphore) — это переменная специального типа, которая доступна параллельным процессам только для двух операций — закрытия и открытия, названных соответственно операциями Р и V^[3].

Эти операции являются примитивами относительно семафора, который указывается в качестве параметра операций. Здесь семафор играет роль вспомогательного критического ресурса, так как операции Р и V неделимы при своем выполнении и взаимно исключают друг друга.

Семафорный механизм работает по схеме, в которой сначала исследуется состояние критического ресурса, идентифицируемое значением семафора, а затем уже осуществляется допуск к критическому ресурсу или отказ от него на некоторое время. При отказе доступа к критическому ресурсу используется режим пассивного ожидания. Поэтому в состав механизма включаются средства формирования обслуживания очереди ожидающих процессов. Эти средства реализуются супервизором операционной системы. Необходимо отметить, что в силу взаимного исключения примитивов попытка в различных параллельных процессах одновремено выполнить примитив над одним и тем же семафором приведет к тому, что он окажется успешной только для одного процесса. Все остальные процессы на время выполнения примитива будут взаимно исключены.

Основным достоинством семафорных операций является отсутствие состояния активного ожидания, что может существенно повысить эффективность работы мультизадачной системы.

В настоящее время на практике используется много различных видов семафорных механизмов. Варьируемыми параметрами, которые отличают различные виды примитивов, являются начальное значение и диапазон изменения значения семафора, логика действий семафорных операций, количество семафоров, доступ­ных для обработки при исполнении отдельного примитива. Обобщенный смысл примитива P(S) состоит в проверке текущего значения сема­фора S. Если оно не меньше нуля, то осуществляется переход к следующей за при­митивом операции. В противном случае процесс снимается на некоторое время с выполнения и переводится в состояние пассивного ожидания. Находясь в списке заблокированных, ожидающий процесс не проверяет семафор непрерывно, как в случае активного ожидания. Вместо него процессор может исполнять другой про­цесс, реально выполняющий какую-то полезную работу.

 

5.2.4 Мониторы Хоара

Анализ рассмотренных задач показывает, что, несмотря на очевидные достоинства (простота, независимость от количества процессов, отсутствие активного ожида­ния), семафорные механизмы имеют и ряд недостатков. Эти механизмы являются слишком примитивными, так как семафор не указывает непосредственно на синхронизирующее условие, с которым он связан, или на критический ресурс. Поэто­му при построении сложных схем синхронизации алгоритмы решения задач по­рой получаются весьма непростыми, ненаглядными и трудными для доказатель­ства их правильности.

Необходимо иметь очевидные решения, которые позволят прикладным програм­мистам без лишних усилий, связанных с доказательством правильности алгорит­мов и отслеживанием большого числа взаимосвязанных объектов, создавать па­раллельные взаимодействующие программы. К таким решениям можно отнести так называемые мониторы, предложенные Хоаром.

В параллельном программировании монитор — это пассивный набор разделяемых переменных и повторно входимых процедур доступа к ним, которым процессы пользуются в режиме разделения, причем в каждый момент им может пользовать­ся только один процесс.

Рассмотрим, например, некоторый ресурс, который разделяется между процесса­ми каким-либо планировщиком. Каждый раз, когда процесс желает получить в свое распоряжение какие-то ресурсы, он должен обратиться к программе-планировщику. Этот планировщик должен иметь переменные, с помощью которых можно отслеживать, занят ресурс или свободен. Процедуру планировщика разделяют все процессы, и каждый процесс может в любой момент захотеть обратиться к плани­ровщику. Но планировщик не в состоянии обслуживать более одного процесса одновременно. Такая процедура-планировщик и представляет собой пример мо­нитора.

Таким образом, монитор — это механизм организации параллелизма, который со­держит как данные, так и процедуры, необходимые для динамического распреде­ления конкретного общего ресурса или группы общих ресурсов. Процесс, желаю­щий получить доступ к разделяемым переменным, должен обратиться к монитору, который либо предоставит доступ, либо откажет в нем. Необходимость входа в монитор с обращением к какой-либо его процедуре (например, с запросом на выделение требуемого ресурса) может возникать у многих процессов. Однако вход в монитор находится под жестким контролем — здесь осуществляется взаимное исключение процессов, так что в каждый момент времени только одному процессу разрешается войти в монитор. Процессам, которые хотят войти в монитор, когда он уже занят, приходится ждать, причем режимом ожидания автоматически управ­ляет сам монитор. При отказе в доступе монитор блокирует обратившийся к нему процесс и определяет условие ожидания. Проверка условия выполняется самим монитором, который и деблокирует ожидающий процесс. Поскольку механизм монитора гарантирует взаимное исключение процессов, исключаются серьезные проблемы, связанные с организацией параллельных взаимодействующих процес­сов.

Внутренние данные монитора могут быть либо глобальными (относящимися ко всем процедурам монитора), либо локальными (относящимися только к одной конкретной процедуре). Ко всем этим данным можно обращаться только изнутри монитора; процессы, находящиеся вне монитора и, по существу, только вызываю­щие его процедуры, просто не могут получить доступ к данным монитора. При первом обращении монитор присваивает своим переменным начальные значения. При каждом последующем обращении используются те значения переменных, которые остались от предыдущего обращения.

Если процесс обращается к некоторой процедуре монитора, а соответствующий ресурс уже занят, эта процедура выдает команду ожидания WAIT с указанием усло­вия ожидания. Процесс мог бы оставаться внутри монитора, однако, если в мони­тор затем войдет другой процесс, это будет противоречить принципу взаимного исключения. Поэтому процесс, переводящийся в режим ожидания, должен вне монитора ждать того момента, когда необходимый ему ресурс освободится. Со временем процесс, который занимал данный ресурс, обратится к монитору, что­бы возвратить ресурс системе. Соответствующая процедура монитора при этом может просто принять уведомление о возвращении ресурса, а затем ждать, пока не поступит запрос от другого процесса, которому потребуется этот ресурс. Однако может оказаться, что уже имеются процессы, ожидающие освобождения данного ресурса. В этом случае монитор выполняет команду извещения (сигнализации) SIGNAL, чтобы один из ожидающих процессов мог получить данный ресурс и поки­нуть монитор. Если процесс сигнализирует о возвращении (иногда называемом освобождением) ресурса и в это время нет процессов, ожидающих данного ресур­са, то подобное оповещение не вызывает никаких других последствий, кроме того, что монитор, естественно, вновь внесет ресурс в список свободных. Очевидно, что процесс, ожидающий освобождения некоторого ресурса, должен находиться вне монитора, чтобы другой процесс имел возможность войти в монитор и возвратить ему этот ресурс.

Чтобы гарантировать, что процесс, находящийся в ожидании некоторого ресурса, со временем получит этот ресурс, считается, что ожидающий процесс имеет более высокий приоритет, чем новый процесс, пытающийся войти в монитор. В против­ном случае новый процесс мог бы перехватить ожидаемый ресурс до того, как ожи­дающий процесс вновь войдет в монитор. Если допустить многократное повторение подобной нежелательной ситуации, то ожидающий процесс мог бы откладываться бесконечно. Для систем реального времени можно допустить использование дис­циплины обслуживания на основе абсолютных или динамически изменяемых при­оритетов.

Единственный ресурс динамически запрашивается и освобождается процессами, которые обращаются к процедурам REQUEST (запрос) и RELEASE (освободить). Если процесс обращается к процедуре REQUEST в тот момент, когда ресурс используется, значение переменной busy (занято) будет равно true, и процедура REQUEST выпол­нит операцию монитора WAIT(free). Эта операция блокирует не процедуру REQUEST, а обратившийся к ней процесс, который помещается в конец очереди процессов, ожидающих, пока не будет выполнено условие free (свободно).

Когда процесс, использующий ресурс, обращается к процедуре RELEASE, операция монитора SIGNAL деблокирует процесс, находящийся в начале очереди, не позво­ляя исполняться никакой другой процедуре внутри того же монитора. Этот дебло­кированный процесс будет готов возобновить исполнение процедуры REQUEST сразу же после операции WAIT(free), которая его и блокировала. Если операция SIGNAL(free) выполняется в то время, когда нет процесса, ожидающего условия free, то никаких действий не выполняется.

Использование монитора в качестве основного средства синхронизации и связи освобождает процессы от необходимости явно разделять между собой информа­цию. Напротив, доступ к разделяемым переменным всегда ограничен телом монито­ра, и, поскольку мониторы входят в состав ядра операционной системы, разделяемые переменные становятся системными переменными. Это автоматически исключа­ет необходимость в критических секциях (так как в каждый момент монитором может пользоваться только один процесс, то два процесса никогда не смогут полу­чить доступ к разделяемым переменным одновременно).

Монитор является пассивным объектом в том смысле, что это не процесс; его про­цедуры выполняются только по требованию процесса.

Хотя по сравнению с семафорами мониторы не представляют собой существенно более мощного инструмента для организации параллельных взаимодействующих вычислительных процессов, у них есть некоторые преимущества перед более при­митивными синхронизирующими средствами.

Во-первых, мониторы очень гибки. В форме мониторов можно реализовать не только семафоры, но и многие другие синхронизирующие операции.

Во-вторых, локализация всех разделяемых переменных внутри тела мо­нитора позволяет избавиться от малопонятных конструкций в синхронизируемых процессах — сложные взаимодействия процессов можно синхронизировать нагляд­ным образом.

В-третьих, мониторы дают процессам возможность совместно ис­пользовать программные модули, представляющие собой критические секции. Если несколько процессов совместно используют ресурс и работают с ним совершенно одинаково, то в мониторе достаточно только одной процедуры, тогда как решение с семафорами требует, чтобы в каждом процессе имелся собственный экземпляр критической секции. Таким образом, мониторы по сравнению с семафорами по­зволяют значительно упростить организацию взаимодействующих вычислитель­ных процессов и дают большую наглядность при совсем незначительной потере в эффективности.

Лекция 10

План лекции:

4. Почтовые ящики

5. Конвейеры и очереди сообщений

 

Литература:

А.В.Гордеев Операционные системы: учебник. 2007. 416с. Стр.209 –246

5.2 Почтовые ящики

Тесное взаимодействие между процессами предполагает не только синхрони­зацию — обмен временными сигналами, но также передачу и получение про­извольных данных, то есть обмен сообщениями. В системе с одним процессором посылающий и получающий процессы не могут работать одновременно. В мульти­процессорных системах также нет никакой гарантии их одновременного испол­нения. Следовательно, для хранения посланного, но еще не полученного сооб­щения необходимо место. Оно называется буфером сообщений, или почтовым ящиком

Если процесс Р1 хочет общаться с процессом Р2, то Р1 просит систему предоста­вить или образовать почтовый ящик, который свяжет эти два процесса так, чтобы они могли передавать друг другу сообщения. Для того чтобы послать процессу Р2 какое-то сообщение, процесс Р1 просто помещает это сообщение в почтовый ящик, откуда процесс Р2 может его в любое время получить. При применении почтового ящика процесс Р2 в конце концов обязательно получит сообщение, когда обратит­ся за ним (если вообще обратится). Естественно, что процесс Р2 должен знать о существовании почтового ящика.

Поскольку в системе может быть много почто­вых ящиков, необходимо обеспечить доступ процессу к конкретному почтовому ящику. Почтовые ящики являются системными объектами, и для пользования та­ким объектом необходимо получить его у операционной системы, что осуществ­ляется с помощью соответствующих запросов.

Если объем передаваемых данных велик, то эффективнее не передавать их непос­редственно, а отправлять в почтовый ящик сообщение, информирующее процесс- получатель о том, где можно их найти.

Почтовый ящик может быть связан с парой процессов, только с отправителем, толь­ко с получателем, или его можно получить из множества почтовых ящиков, кото­рые используют все или несколько процессов. Почтовый ящик, связанный с про­цессом-получателем, облегчает посылку сообщений от нескольких процессов в фиксированный пункт назначения. Если почтовый ящик не связан жестко с про­цессами, то сообщение должно содержать идентификаторы и процесса – отправителя и процесса – получателя.

Итак, почтовый ящик — это информационная структура, поддерживаемая опера­ционной системой. Она состоит из головного элемента, в котором находится ин­формация о данном почтовом ящике, и нескольких буферов (гнезд), в которые помещают сообщения. Размер каждого буфера и их количество обычно задаются при образовании почтового ящика.

Основные достоинства почтовых ящиков:

· процессу не нужно знать о существовании других процессов до тех пор, пока он не получит сообщения от них;

· два процесса могут обменяться более чем одним сообщением за один раз;

· операционная система может гарантировать, что никакой иной процесс не вме­шается во взаимодействие процессов, ведущих между собой «переписку»;

· очереди буферов позволяют процессу-отправителю продолжать работу, не об­ращая внимания на получателя.

Основным недостатком буферизации сообщений является появление еще одного ресурса, которым нужно управлять. Этим ресурсом являются сами почтовые ящики.

К другому недостатку можно отнести статический характер этого ресурса: количество буферов для передачи сообщений через почтовый ящик фиксировано. Поэтому есте­ственным стало появление механизмов, подобных почтовым ящикам, но реализован­ных на принципах динамического выделения памяти под передаваемые сообщения.

В операционных системах компании Microsoft тоже имеются почтовые ящики (mailslots). В частности, они достаточно часто используются при создании распре­деленных приложений для сети. При работе с ними в приложении, которое долж­но отправить сообщение другому приложению, необходимо указывать класс дос­тавки сообщений. Различают два класса доставки. Первый класс (first-class delivery) гарантирует доставку сообщений; он ориентирован на сеансовое взаимодействие между процессами и позволяет организовать посылки типа «один к одному» и «один ко многим». Второй класс (second-class delivery) основан на механизме датаграмм, и он уже не гарантирует доставку сообщений получателю.

 

5.3 Конвейеры и очереди сообщений

Конвейеры

Программный канал связи (pipe), или, как его иногда называют, конвейер, транс­портер, является средством, с помощью которого можно обмениваться данными между процессами. Принцип работы конвейера основан на механизме ввода-вывода файлов, то есть задача, передающая информацию, действует так, как будто она записывает данные в файл, в то время как задача, для которой предна­значается эта информация, читает ее из этого файла. Операции записи и чтения осуществляются не записями, как это делается в обычных файлах, а потоком бай­тов. Таким образом, функции, с помощью кото­рых выполняется запись в канал и чтение из него, являются теми же самыми, что и при работе с файлами. По сути, канал представляет собой поток данных между двумя (или более) процессами. Это упрощает программирование и избавляет про­граммистов от использования каких-то новых механизмов. На самом деле конвейеры не являются файлами на диске, а представляют собой буферную память, рабо­тающую по принципу FIFO, то есть по принципу обычной очереди. Однако не следует путать конвейеры с очередями сообщений; последние реализуются иначе и имеют другие возможности.

Конвейер имеет определенный размер^[4], который не может превышать 64 Кбайт и работает циклически. Вспомните реализацию очереди на массивах, когда имеются указатели начала и конца очереди, которые перемещаются циклически по массиву. То есть имеется некий массив и два указателя: один показывает на первый элемент (указатель на начало — head), а второй — на последний (указатель на конец — tail). В начальный момент оба указателя равны нулю. Добавление самого первого эле­мента в пустую очередь приводит к тому, что указатели на начало и на конец при­нимают значение, равное 1 (в массиве появляется первый элемент). В последую­щем добавление нового элемента вызывает изменение значения второго указателя, поскольку он отмечает расположение именно последнего элемента очереди. Чте­ние (и удаление) элемента (читается и удаляется всегда первый элемент из со­зданной очереди) приводит к необходимости модифицировать значение указате­ля на ее начало. В результате операций записи (добавления) и чтения (удаления) элементов в массиве, моделирующем очередь элементов, указатели будут переме­щаться от начала массива к его концу. При достижении указателем значения ин­декса последнего элемента массива значение указателя вновь становится единич­ным (если при этом не произошло переполнение массива, то есть количество элементов в очереди не стало большим числа элементов в массиве). Можно ска­зать, что мы как бы замыкаем массив в кольцо, организуя круговое перемещение указателей на начало и на конец, которые отслеживают первый и последний эле­менты в очереди. Сказанное иллюстрирует рис. 5.4. Именно так функционирует конвейер.

Как информационная структура конвейер описывается идентификатором, разме­ром и двумя указателями. Конвейеры представляют собой системный ресурс. Чтобы начать работу с конвейером, процесс сначала должен заказать его у операционной системы и получить в свое распоряжение. Процессы, знающие идентификатор кон­вейера, могут через него обмениваться данными.

Указатель на конец Указатель на начало

Рис.5.4-Организация очереди в массиве

В качестве иллюстрации приведем основные системные запросы для работы с кон­вейерами, которые имеются в API OS/2.

Функция создания конвейера:

DosCreatePipe (SReadHandle, &WriteHandle, PipeSize):

Здесь ReadHandle — дескриптор чтения из конвейера,

WriteHandle — дескриптор записи в конвейер,

PipeSize — размер конвейера.

Функция чтения из конвейера:

DosRead (SReadHandle, (PVOID)SInform. sizeof(Inform), SBytesRead):

Здесь ReadHandle — дескриптор чтения из конвейера,

Inform — переменная любого типа,

sizeof(Inform) — размер переменной Inform,

BytesRead — количество прочитанных байтов.

Данная функция при обращении к пустому конвейеру будет ожидать, пока в нем не появится информация для чтения.

Функция записи в конвейер:

DosWrite (SWriteHandle, (PVOID)&Inform, sizeof(Inform), &BytesWrite);

Здесь WriteHandle — дескриптор записи в конвейер,

BytesWrite — количество записанных байтов.

Читать из конвейера может только тот процесс, который знает идентификатор со­ответствующего конвейера. При работе с конвейером данные непосредственно помещаются в него. Еще раз отметим, что из-за ограничения на размер конвейера программисты сталкиваются и с ограничениями на размеры передаваемых через него сообщений.

Очереди сообщений

Очереди (queues) сообщений предлагают более удобный метод связи между взаимодействующими процессами по сравнению с каналами, но в своей реализации они сложнее. С помощью очередей также можно из одной или нескольких задач независимым образом посылать сообщения некоторой задаче-приемнику. При этом только процесс-приемник может читать и удалять сообщения из очереди, а процессы-клиенты имеют право лишь помещать в очередь свои сообщения. Таким образом, очередь работает только в одном направлении. Если же необходима двухсторонняя связь, то можно создать две очереди.

Работа с очередями сообщений отличается от работы с конвейерами.

Во-первых, очереди сообщений предоставляют возможность использовать несколько дисцип­лин обработки сообщений:

· FIFO — сообщение, записанное первым, будет первым и прочитано;

· LIFO — сообщение, записанное последним, будет прочитано первым;

· приоритетный доступ — сообщения читаются с учетом их приоритетов;

· произвольный доступ — сообщения читаются в произвольном порядке. Тогда как канал обеспечивает только дисциплину FIFO.

Во-вторых, если при чтении сообщения оно удаляется из конвейера, то при чтении сообщения из очереди этого не происходит, и сообщение при желании может быть прочитано несколько раз.

В-третьих, в очередях присутствуют не непосредственно сами сообщения, а толь­ко их адреса в памяти и размер. Эта информация размещается системой в сег­менте памяти, доступном для всех задач, общающихся с помощью данной оче­реди.

Каждый процесс, использующий очередь, должен предварительно получить раз­решение на доступ в общий сегмент памяти с помощью системных запросов API, ибо очередь — это системный механизм, и для работы с ним требуются системные ресурсы и, соответственно, обращение к самой ОС. Во время чтения из очереди задача-приемник пользуется следующей информацией:

· идентификатор процесса (Process Identifier, PID), который передал сообщение;

· адрес и длина переданного сообщения;

· признак необходимости ждать, если очередь пуста;

· приоритет переданного сообщения;

· номер освобождаемого семафора, когда сообщение передается в очередь.

Наконец, приведем перечень основных функций, управляющих работой очереди (без подробного описания передаваемых параметров, поскольку в различных ОС обращения к этим функциям могут существенно различаться):

· □	CreateQueue	- создание новой очереди;
· а	OpenQueue	- открытие существующей очереди;
· □	ReadQueue	- чтение и удаление сообщения из очереди;
· а	PeekQueue	- чтение сообщения без его последующего удаления из очереди;
· а	WriteQueue	- добавление сообщения в очередь;
· а	CloseQueue	- завершение использования очереди;
·	QueryQueue	- определение числа элементов в очереди
·	PurgeQueue	- удаление из очереди всех сообщений;

 

 

Контрольные вопросы и задачи

1. Какие последовательные вычислительные процессы мы называем параллель­ными и почему? Какие параллельные процессы называются независимыми, а какие — взаимодействующими?

2. Изложите алгоритм Деккера, позволяющий разрешить проблему взаимного исключения путем использования одной только блокировки памяти.

3. Объясните, как действует команда проверки и установки. Расскажите о рабо­те команд BTS и BTR, которые имеются в процессорах с архитектурой ia32.

4. Расскажите о семафорах Дейкстры. Чем обеспечивается взаимное исключе­ние при выполнении примитивов Р и V?

5. Изложите, как могут быть реализованы семафорные примитивы для мульти­процессорной системы?

6. Что такое мьютекс?

7. Изложите алгоритм решения задачи «поставщик-потребитель» при исполь­зовании семафоров Дейкстры.

8. Изложите алгоритм решения задачи «читатели-писатели» при использова­нии семафоров Дейкстры.

9. Что такое «монитор Хоара»? Приведите пример такого монитора.

10. Что представляют собой почтовые ящики?

11. Что представляют собой конвейеры (программные каналы)?

12. Что представляют собой очереди сообщений? Чем отличаются очереди сооб­щений от почтовых ящиков?

 

Лекция 11

Тема 6: Планирование и диспетчеризация процессов и задач

План лекции: 1. Операции планирования и диспетчеризации

2. Типы планирования процессора

3. Алгоритмы планирования

 

Литература:

А.В.Гордеев Операционные системы: учебник. 2007. 416с. Стр.50 – 71

М.Ф.Бондаренко, О.Г.Качко Операційні системи: навч.посібник. 2008. Стр.126-159

6.1 ОПЕРАЦИИ ПЛАНИРОВАНИЯ И ДИСПЕТЧЕРИЗАЦИИ

Самым критичным ресурсом в ЭВМ есть центральный процессор. Наличие нескольких процессоров в многопроцессорных системах только усложняет алгоритм управления временем процессоров. Для управления временем процессоров используются модули планирования и диспетчеризации.

Планирование –это формирование очереди процессов, готовых к выполнению.

Диспетчеризация –это выбор процессора для конкретного процесса, готового к выполнению.

Обычно процедуры обслуживания очереди процессов и выбора процессора выполняются одним модулем, который носит название планировщик – диспетчер. В очереди готовых процессов могут стоять процессы разных типов:

• Отложенные процессы – это те процессы, которые были прерваны в связи с необходимостью проведения операции ввода – вывода или доступа к другим системным ресурсам;
• Новые процессы – это процессы, только допущенные к выполнению;
• Процессы, для которых завершилось отпущенное время.

В многозадачных системах в основной памяти одновременно содержится код нескольких процессов. В работе каждого процесса периоды использования процессора чередуются с ожиданием завершения выполнения операций ввода-вывода или некоторых внешних событий. Процессор (или процессоры ) занят выполнением одного процесса, в то время как остальные находятся в состоянии ожидания.

Ключом к многозадачности является планирование. Обычно используются ч етыре типа планирования (табл. 6. 1). Одно из них — планирование ввода-вывода. Планирование остальных трех типов, является планированием процессора.

Таблица 6.1- Типы планирования

Долгосрочное планирование	Решение о добавлении процесса в пул выполняемых процессов
Среднесрочное планирование	Решение о добавлении процесса к числу процессов,полностью иличастично размещенных в основной памяти
Краткосрочное планирование	Решение о том, какой из доступных процессов будет выполнятьсяпроцессором
Планирование ввода-вывода	Решение о том, какой из запросов процессов на операции ввода- вывода будет обработан свободным устройством ввода-вывода

Поскольку изучение планирования при использовании нескольких процессоров сопряжено с дополнительными сложностями, методологически правильнее сначала рассмот­реть работу одного процессора, чтобы отчетливее увидеть отличия разных алго­ритмов планирования.

 

6.2 ТИПЫ ПЛАНИРОВАНИЯ ПРОЦЕССОРА

Цель планирования процессора состоит в распределении во времени процес­сов, выполняемых процессором (или процессорами) таким образом, чтобы удов­летворять требованиям системы, таким, как время отклика, пропускная способ­ность и эффективность работы процессора. Во многих системах планирование разбивается на три отдельные функции — долгосрочного, среднесрочного и краткосрочного планирования. Их названия соответствуют временным масшта­бам выполнения этих функций.

Долгосрочное планирова­ние осуществляется при создании нового процесса и представляет собой решение о добавлении нового процесса к множеству активных в настоящий момент про­цессов.

Среднесрочное планирование является частью свопинга и представляет собой решение о добавлении процесса к множеству по крайней мере частично расположенных в основной памяти (и, следовательно, доступных для выполне­ния) процессов.

Краткосрочное планирование является решением о том, какой из готовых к выполнению процессов будет выполняться следующим.

На рис. 6.1 диаграмма переходов реорганизована таким образом, чтобы показать вложен­ность функций планирования.

Планирование оказывает большое влияние на производительность системы, по­скольку именно оно определяет, какой процесс будет выполняться, а какой — ожи­дать выполнения.

На рис. 6.2 показаны очереди, включенные в диаграмму переходов состояний процесса.^[5]

По сути,планирование представляет собой управление очередя­ми с целью минимизации задержек и оптимизации производительности системы.

 

Долгосрочное планирование

Долгосрочное планирование указывает, какие программы допускаются к выполнению системой, и тем самым определяет степень многозадачности. Буду­чи допущенным к выполнению, задание (или пользовательская программа) ста­новится процессом, который добавляется в очередь для краткосрочного планиро­вания. В некоторых системах вновь созданный процесс добавляется к очереди среднесрочного планировщика, будучи целиком сброшенным на диск.

В пакетных системах (или в пакетной части операционной системы общего назначения) новое задание направляется на диск и хранится в очереди пакетных заданий, а долгосрочный планировщик по возможности создает процессы для заданий из очереди. В такой ситуации планировщик должен принять решение, во-первых, о том, способна ли операционная система работать с дополнительными процессами, а во-вторых, о том, какое именно задание (или задания) следует превратить в процесс (процессы). Рассмотрим вкратце эти решения.

 

Рис.6.1-Уровни планирования

Долгосрочное Тайм-аут Рис. 6.2- Диаграмма планирования с участием очередей

Решение о том, когда следует создавать новый процесс, в общем определяется желаемым уровнем многозадачности. Чем больше процессов будет создано, тем меньший процент времени будет тратиться на выполнение каждого из них (поскольку в борьбе за одно и то же время конкурирует большее количество процессов). Таким образом, долгосрочный планировщик может ограничить степень много­задачности, с тем чтобы обеспечить удовлетворительный уровень обслуживания те­кущего множества процессов. Каждый раз при завершении задания планировщик решает, следует ли добавить в систему один или несколько новых процессов. Кроме того, долгосрочный планировщик может быть вызван в случае, когда относительное время простоя процессора превышает некоторый предопределенный порог.

Решение о том, какое из заданий должно быть добавлено в систему, можетосновываться на простейшем принципе « первым поступил — первым обслужен »; кроме того, для управления производительностью системы может использовать­ся и специальный инструментарий. Используемые в последнем случае критерии могут включать приоритет заданий, ожидаемое время выполнения и требования для работы устройств ввода-вывода. Например, если заранее доступна детально информация о процессах, планировщик может пытаться поддерживать в системе смесь из процессов, ориентированных на вычисления и загружающих процессор, и процессов с высокой интерактивностью ввода-вывода и малой загрузкой прс- цессора. Принимаемое решение может также зависеть от того, какие именно ре­сурсы ввода-вывода будут запрашиваться процессом.

В случае использования интерактивных программ в системах с разделением времени запрос на запуск процесса может генерироваться действиями пользователя по подключению к системе. Пользователи не просто вносятся в очередь в ожидании, когда система обработает их запрос на подключение. Вместо этого операционная система принимает всех зарегистрированных пользователей до насыщения системы (пороговое значение которого определяется заранее). После достижения состояния насыщения на все запросы на вход в систему будет полу­чено сообщение о заполненности системы и временном прекращении доступа к ней с предложением повторить операцию входа попозже.

Среднесрочное планирование

Среднесрочное планирование является частью системы св опинга. Обычно решение о за­грузке процесса в память принимается в зависимости от степени многозадачно­сти; кроме того, в системе с отсутствием виртуальной памяти среднесрочное планирование также тесно связано с вопросами управления памятью. Таким об­разом, решение о загрузке процесса в память должно учитывать требования к памяти выгружаемого процесса.

 

Краткосрочное планирование

Рассматривая частоту работы планировщика, можно сказать, что долго­срочное планирование выполняется сравнительно редко, среднесрочное — не­сколько чаще. Краткосрочный же планировщик, известный также как диспетчер (dispatcher), работает чаще всего, определяя, какой именно процесс будет вы­полняться следующим.

Краткосрочный планировщик вызывается при наступлении события, кото­рое может приостановить текущий процесс или предоставить возможность пре­кратить выполнение данного процесса в пользу другого. Вот некоторые примеры таких событий:

· прерывание таймера;

· прерывания ввода-вывода;

· вызовы операционной системы;

· сигналы.

6.3 АЛГОРИТМЫ ПЛАНИРОВАНИЯ

Критерии краткосрочного планирования

Основная цель краткосрочного планирования состоит в распределении про­цессорного времени таким образом, чтобы оптимизировать один или несколько аспектов поведения системы. Вообще говоря, имеется множество критериев оценки различных стратегий планирования.

Наиболее распространенные критерии