- •Раздел 4. Взаимодействие процессов
- •4.1. Примитивы синхронизации процессов
- •4.1.1. Простейшие примитивы, не учтенные в классификации
- •4.1.2. Примитивы временной синхронизации
- •4.1.3. Примитивы событийной синхронизации процессов
- •4.2. Общий семафор как средство событийной синхронизации
- •4.3. Примитивы ядра для обмена сообщениями
- •Примитивы синхронизации процессов;
- •4.3.1. Буфер как средство коммуникации между процессами
- •4.4. Условные переменные
- •4.5. Монитор как средство реализации взаимного исключения
- •4.6. Проблема тупиков при взаимодействии процессов
- •4.7. Планирование загрузки процессора в ядре
- •4.7.1. Классификация алгоритмов планирования
- •4.7.2. Классификация задач с точки зрения планируемости
- •4.7.3. Динамическое планирование
- •4.7.3.1. Планирование независимых задач
- •1. Алгоритм монотонной скорости.
- •2. Алгоритм “задача с минимальным предельным сроком завершения - первая”
- •3. Алгоритм минимальной неопределенности
- •4.7.3.2. Планирование зависимых задач
- •4.7.4. Статическое планирование
- •Раздел 4
4.3. Примитивы ядра для обмена сообщениями
Напомню, что мы классифицировали примитивы ядра на три группы:
Примитивы управления процессами;
Примитивы синхронизации процессов;
Примитивы обмена данными.
Синхронизация и обмен данными вместе называются обобщенно взаимодействием.
Если опять построить некоторую многоуровневую классификацию, то примитивы второго и третьего класса следует поместить в следующую иерархическую схему:
Обмен данными
─────────────
Синхронизация
Т.е. обмен данными - это логически более высокий уровень взаимодействия процессов, чем синхронизация.
Обмен данными не может быть реализован без синхронизации.
При этом средства синхронизации «встраиваются» в средства обмена данными таким образом, что они оказываются скрытыми от пользователя.
Пользователю предоставляется пара примитивов типа: SEND, RECEIVE или READ, WRITE.
Обмен данными может рассматриваться в двух аспектах.
Обмен происходит между процессами, выполняющимися на одной физической машине;
Обмен происходит между процессами, выполняющимися на различных физических машинах.
В данном параграфе мы рассмотрим первый вариант обмена данными, рассматривая средства обмена как примитивы ядра. Мы увидим, кстати, что эти примитивы подпадают под определение понятия МОНИТОР, рассмотренное выше. Обмену данными в целом, с учетом возможности выполнения взаимодействующих процессов на различных машинах, посвящен специальный раздел, рассматривающий восьмой уровень базовой классификации операционной среды - уровень коммуникаций.
Как и ранее, мы рассмотрим модели обмена данными, а затем приведем примеры средств обмена данными в реальных операционных средах. Базовым средством обмена данными между процессами является средство, называемое буфером.
4.3.1. Буфер как средство коммуникации между процессами
При организации связи между процессами с помощью любого средства требуется составить спецификацию к этому средству.
Спецификация буфера как средства связи выглядит следующим образом:
Сообщения в буфере имеют фиксированный размер;
Размер буфера ограничен, буфер - кольцевой;
Посылка сообщения в полный буфер недопустима;
Чтение сообщения из пустого буфера также недопустима.
Перечислив условия функционирования буфера, можно построить его описание, рассматривая буфер в виде монитора.
Class TBuffer {
int N; //текущее количество сообщений в буфере от 0 до N
int in; //индекс ячейки, в которую производится тек. запись от 0 до N-1
int out; //индекс ячейки, из которой производится тек. чтение 0 - N-1
char Buf[N];
TList* RList; //очередь процессов, ждущих чтения
TList* WList; //очередь процессов, ждущих записи
TBuffer();
~ TBuffer();
void Write(char M);
void Read(char & M);
}
Схема использования буфера выглядит следующим образом.
{
TBuffer * B;
B = new TBuffer();
...
delete B;
}
Процесс 1: Процесс 2:
void Производитель() void Потребитель()
{ {
char Message; char Message;
while (1) { While (1) {
... ...
Сформировать(Message); B->Read(Message);
B->Write(Message); Обработать(Message);
... ...
} }
} }
Целью использования буфера при обмене данными между процессами является согласование скоростей записи и чтения информации различными процессами. Если скорости записи и чтения одинаковы, то рисунок состояния буфера будет выглядеть примерно так:
Если скорость чтения превышает скорость записи, то схема состояния буфера будет выглядеть следующим образом.
Т.е. буфер будет большее время пустым, чем занятым, а процесс, читающий из буфера, будет ждать записи. Если скорость записи превышает скорость чтения, то схема состояния буфера будет выглядеть следующим образом.
Т.е. буфер будет большее время полным, чем свободным, а процесс, записывающий в буфер, будет ждать чтения.
Распишем теперь методы монитора БУФЕР.
TBuffer::TBuffer()
{
N = 0;
in = 0;
out = 0;
RList = new TList();
WList = new TList();
}
TBuffer::~TBuffer()
{
delete RList;
delete WList;
}
void TBuffer::Write(char M)
{
Запрет прерываний;
if (n == N) { //буфер полон
WList->Insert(Текущий процесс); //ждем записи
ПЕРЕНАЗНАЧИТЬ ПРОЦЕССОР;
}
n++;
Buf[in] = M;
in = (in + 1) % N;
if (RList не пустая) { //активизация ждущего чтения
Очередь_готовых->Insert(Текущий процесс);
RList->Remove(Первый процесс);
Передать управление(Текущий процесс,Первый процесс);
}
Разрешение прерываний;
}
void TBuffer::Read(char & M)
{
Запрещение прерываний;
if (n == 0) {
RList->Insert(Текущий процесс); //ждем чтения
ПЕРЕНАЗНАЧИТЬ ПРОЦЕССОР;
}
n--;
M = Buf[out];
out = (out + 1) % N;
if (WList не пустая) { //активизация ждущего записи
Очередь_готовых->Insert(Текущий процесс);
WList->Remove(Первый процесс);
Передать управление(Текущий процесс,Первый процесс);
}
Разрешение прерываний;
}
Выводы
Внешне работа с буфером напоминает работу с файлом: Создать; Записать; Прочитать; Разрушить; Работа любых средств обмена данными похожа на эти действия.
Две очереди процессов используются в качестве средств синхронизации записи и чтения. Вместо прямого использования очередей могут использоваться семафоры.
Недостатками буфера являются: 1) фиксированный размер буфера; 2) реальная перезапись данных в буфер и из буфера.
Недостатки буфера устраняются механизмами очередей сообщений, рассмотренными в разделе 5.