Транспортеры (каналы)

Являются средством взаимодействия родственных процессов, представляют собой область памяти, имеющую файловую организацию, для которой обеспечивается запись и считывание данных транспортере. Реализуется очередь обслуживания. Порядок записи данных на транспортер не изменен, не допускается повторное считывание данных. Обмен данных происходит не непосредственно, а через транспортер. Из вызвавшего процесса создается размер транспортера. Дочерние процессы могут использовать родительский транспортер.

Каналы представляют собой циклические буфера, которые позволяют двум процессам связываться друг с другом в соответствии с моделью производитель/потребитель. Следовательно, канал – не что иное, как очередь, работающая по принципу “первым вошел - первым вышел”, запись, в которую осуществляется одним процессом, а чтение – другим.

При создании канала он получает буфер определенного размера. При записи в канал при наличии свободного места соответствующий запрос удовлетворяется немедленно: в противном случае процесс блокируется. Аналогично блокируется процесс, пытающийся прочесть из канала большее количество информации, чем имеющиеся в нем; в противном случае запрос на чтение выполняется немедленно. ОС обеспечивает взаимоисключения – одновременно доступ к каналу имеет только один процесс.

Существует два типа каналов: именованные и неименованные. Совместно использовать неименованные каналы могут только связанные друг с другом процессы; не связанные друг с другом процессы могут совместно использовать только именованные каналы.

Очереди

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

- создание очереди;

- просмотр очереди;

- чтение очереди;

- закрытие очереди.

Записывающий процесс осуществляет действие:

- открыть очередь;

- записать в очередь;

- закрыть очередь.

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

- определение количества элементов в очереди в текущий момент;

- очистка очереди создавшим её процессом.

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

Сигналы

Сигнал является механизмом передачи требований от одного процесса к другому на немедленное выполнение действия. Обработчик сигнала создается процессом и помещается в начале первого потока процесса. Является аналогом обработки прерывания. При передаче управления обработчику передается адрес возврата и тип принятого сигнала. Доставка сигнала выполняется путем обновления поля в таблице процесса, которому послан данный сигнал, каждый сигнал соответствует отдельному биту. Процесс, посылающий сигнал типа флаг, может передать дополнительную информацию обработчику сигнала. Характер выполняемых действий при возникновении сигнала: обработка системной обшивки при появлении сигнала, блокирование сигнала (игнорирование), передача управления подпрограмме, завершение процесса.

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

Семафоры

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

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

использующими его процессами, то он удаляется из системы.

Управление семафором реализуется с помощью функций:

- установки семафора с целью сигнализации;

- ожидание вызывающим потоком, пока семафор не будет выключен;

- ожидание потоком выключения одного из нескольких семафоров.

Семафор Дейкстры представляет собой целочисленную переменную, с которой ассоциирована очередь ожидающих процессов. Пытаясь пройти через семафор, процесс пытается вычесть из значения переменной 1. Если значение переменной больше или равно 1, нить проходит сквозь семафор успешно (семафор открыт). Если переменная равна 0 (семафор закрыт), процесс останавливается и ставится в очередь

Закрытие семафора соответствует захвату объекта или ресурса, доступ к которому контролируется этим семафором.

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

Наиболее простым случаем семафора является двоичный, или бинарный, семафор.

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

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

Иногда используется упрощённая версия семафора, называемая мьютексом. (mutex, сокращение от mutual exclusion- взаимное исключение). Мьютекс не способен считать, он может лишь управлять взаимным исключением доступа к совместно используемым ресурсам или кодам. Реализация мьютекса проста и эффективна, что делает использование мьютексов особенно полезным в случае потоков, действующих только в пространстве пользователя.

Мьютекс – переменная, которая может находиться в одном из 2-х состояний: блокированном или неблокированном, поэтому для описания мьютекса требуется всего один бит, хотя чаще используется целая переменная, у которой 0 означает неблокированное состояние, а все остальные значения соответствуют блокированному состоянию. Значение мьютекса устанавливается 2-мя процедурами. Если поток (или процесс) собирается войти в критическую область, он вызывает процедуру mutex-lock. Если мьютекс не заблокирован (т.е. вход в критическую область разрешён), запрос выполняется и вызывающий может попасть в критическую область.

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

Пример:

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

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

Введём два семафора: е-число пустых буферов, f-число заполненных буферов. В исходном состоянии e=N, a f=0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом.

Для работы с семафорами вводятся два примитива, традиционно обозначаемых P и V. Пусть переменная представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом:

V(S) – переменная S увеличивается на 1 единым действием.

P(S): уменьшение S на 1.

Если S=0, то в этом случае поток, вызывающий операцию Р, ждёт, пока это уменьшение станет возможным.

Поток-писатель прежде всего выполняет операцию P(e), с помощью которой он проверяет, имеется ли в буферном пуле незаполненные буферы. В соответствии с семантикой операции Р, если семафор е=0 (т.е. свободных буферов в данный момент нет), то поток-писатель переходит в состояние ожидания. Если же е положительное число, то он уменьшает число свободных буферов, записывает данные в очередной свободный буфер и после этого наращивает число занятых буферов операцией V(f). Поток-читатель действует аналогичным образом, с той разницей, что он начинает работу с проверки наличия заполненных буферов, а после чтения данных наращивает количество свободных буферов.

Начальные значение семафоров:

е=N

f=0

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

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

ОС используют разные термины для определения способов межпроцессорного взаимодействия.

В ОС ОS/2 и WINDOWS существует специальный механизм для взаимодействия процессов в реальном масштабе времени. Этот механизм называется DDE (Dynamic Data Exchange – динамический обмен данными). Он стандартизирует процесс обмена командами, сообщениями и объектами для обработки между задачами. Наиболее распространённым процессом, для которого используется ДДЕ, является печать.

Другим интерфейсом для обмена данными является OLE (Object Linking and Embedding – связывание и встраивание объектов). Этот интерфейс позволяет хранить объекты, созданные одной программой, в объектах, созданных другой программой, а также редактировать и печатать их без нарушения целостности информации и связей.

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

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

Категории алгоритмов планирования

В различных средах требуются различные алгоритмы планирования. Это связано с тем, что различные ОС и различные приложения ориентированы на разные задачи. Можно выделить 3 среды:

1) Системы пакетной обработки данных

2) Интерактивные системы

3) Системы реального времени

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

Во-первых, когда создаётся новый процесс, необходимо решить, какой процесс запустить: родительский или дочерний. Во-вторых, планирование необходимо, когда процесс завершает работу. Этот процесс уже не существует, следовательно, необходимо из набора готовых процессов выбрать и запустить следующий. В-третьих, когда процесс блокируется на операции ввода-вывода, семафоре, или по какой либо причине необходимо выбрать и запустить другой процесс. В-четвёртых, необходимость планирования может возникнуть при появлении прерывания ввода-вывода. Если аппаратный таймер выполняет периодические прерывания с частотой 50 Гц, 60 Гц или с любой другой частотой, решения планирования могут приниматься при каждом прерывании по таймеру или при каждом прерывании. Алгоритм планирования можно разделить на 2 категории согласно их поведению после прерываний. Алгоритмы планирования без переключений, иногда называемого также неприоритетным планированием, выбирают процесс и позволяют ему работать вплоть до блокировки (в ожидании ввода-вывода или другого процесса), либо вплоть до того момента, когда процесс сам не отдаст процессор. Процесс не будет прерван, даже если он работает часами. Собственно, решения планирования не принимаются по прерываниям от таймера. После обработки прерывания таймера управление всегда возвращается приостановленному процессу.

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

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

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

Известны следующие критерии, позволяющие сравнивать алгоритмы краткосрочных планировщиков:

¾ утилизация CPU (использование процессора). Утилизация CPU теоретически может находиться в пределах от 0 до 100%. В реальных системах утилизация CPU колеблется в пределах 40% для легко загруженного CPU, 90% для тяжело загруженного.

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

¾ время оборота – для некоторых процессов важным критерием является полное время выполнения, т.е. интервал от момента появления процесса во входной очереди до момента его завершения. Это время названо временем оборота и включает время ожидания в очередях к оборудованию, время выполнения в процессоре и время ввода-вывода.

¾ время ожидания – под этим понимается суммарное время нахождения процесса в очереди готовых процессов.

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

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

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