Операционные системы
Самостоятельная работа №3B
Исследование методов буферизации сообщений
Цель работы: изучение метода обмена сообщениями между процессами с помощью буфера.
Общие сведения
Буферизация является средством согласования скорости записи сообщений одним процессом и скорости чтения сообщений другим процессом. При этом буфер является общим, разделяемым объектом для пишущего и читающего процессов.
Существуют следующие требования к алгоритмам функционирования буфера:
- нельзя записать сообщение в полный буфер; процесс, делающий такую попытку, должен быть блокирован до появления свободной ячейки в буфере;
- нельзу прочитать сообщение из пустого буфера; процесс, делающий такую попытку, должен быть блокирован до появления сообщения в буфере.
Как правило, механизмы синхронизации записи в буфер и чтения из буфера являются скрытыми для пользователя, которым предоставляются лишь примитивы СОЗДАТЬ, УНИЧТОЖИТЬ, ЗАПИСАТЬ и ПРОЧИТАТЬ, внешне напоминающие работу с файлами.
Простейший вариант синхронизации записи и чтения для буфера размером в 1 ячейку памяти рассмотрен в практическом задании 3A. В данной работе рассматривается общий случай буфера размером в N элементов.
Структура буфера.
Буфер представляет собой массив из N элементов определенного типа. Состояние буфера описывается количеством n сообщений, находящихся в буфере, и двумя индексами – индексом out чтения и индексом in записи.
Запись в буфер предваряется проверкой условия "буфер полон", то есть n = N, чтение из буфера предваряется проверкой условия "буфер пуст", то есть n = 0.
Выполнение условия "буфер полон" означает, что скорость записи опередила скорость чтения, а выполнение условия "буфер пуст" означает, что скорость чтения опередила скорость записи. В нормальном состоянии значение индекса записи немного превышает значение индекса чтения.
Как правило, буфер рассматривается как кольцевой, то есть после записи в последнюю ячейку буфера запись продолжается с первой ячейки буфера, чтение осуществляется аналогично.
Синхронизация записи и чтения реализуется использованием очередей ожидания двух видов:
- очереди процессов, ждущих записи, когда буфер полон;
- очереди процессов, ждущих чтения, когда буфер пуст.
Описание буфера
Представим буфер в виде объекта:
TBuffer = Object
in, out : [0..N-1];
n : [0..N];
Buf : Array[0..N-1] Of AnyType;
ReadList, WriteList : TList;
Constructor Init;
Destructor Done; Virtual;
Procedure Write(M : AnyType);
Procedure Read(Var M : AnyType);
Procedure Wait_Read;
Procedure Signal_Read;
Procedure Wait_Write;
Procedure Signal_Write;
End {TBuffer}.
Constructor TBuffer.Init;
Begin
in := 0; out := 0; n := 0;
ReadList.Init;
WriteList.Init;
End {TBuffer.Init};
Destructor TBuffer.Done;
Begin
ReadList.Done;
WriteList.Done;
End {TBuffer.Done};
Синхронизация записи и чтения реализуется следующими четырьмя методами объекта-буфер.
Procedure TBuffer.Wait_Read;
{заставляет процесс ждать чтения, если буфер пустой}
Var
Предыдущий : Процесс;
Begin
Предыдущий := Текущий;
ReadList.Включить(Предыдущий);
Текущий := Очерередь_готовых.Первый;
Очередь_готовых.Извлечь(Текущий);
Передать_управление(Предыдущий, Текущий);
End {TBuffer.Wait_Read};
Procedure TBuffer.Wait_Write;
{заставляет процесс ждать записи, если буфер полный}
Var
Предыдущий : Процесс;
Begin
Предыдущий := Текущий;
WriteList.Включить(Предыдущий);
Текущий := Очерередь_готовых.Первый;
Очередь_готовых.Извлечь(Текущий);
Передать_управление(Предыдущий, Текущий);
End {TBuffer.Wait_Write};
Procedure TBuffer.Signal_Read;
{"сигнализирует" о том, что произведена запись и возможна активи-
зация одного из процессов, ждущих чтения}
Var
Локальный : Процесс;
Begin
Локальный := ReadList.Первый;
If Локальный <> NIL Then Begin {очередь не пустая}
ReadList.Извлечь(Локальный);
Очередь_готовых.Включить(Локальный);
End {If};
End {TBuffer.Signal_Read}.
Procedure TBuffer.Signal_Write;
{"сигнализирует" о том, что произведено чтение и возможна активи-
зация одного из процессов, ждущих записи}
Var
Локальный : Процесс;
Begin
Локальный := WriteList.Первый;
If Локальный <> NIL Then Begin {очередь не пустая}
WriteList.Извлечь(Локальный);
Очередь_готовых.Включить(Локальный);
End {If};
End {TBuffer.Signal_Write}.
Procedure TBuffer.Write(M : AnyType);
Begin
Запретить прерывания;
If n = N Then Wait_Write; {буфер полный}
n := n + 1;
Buf[in] := M;
in := (in + 1) MOD N;
Signal_Read;
Разрешить прерывания;
End {TBuffer.Write};
Procedure TBuffer.Read(Var M : AnyType);
Begin
Запретить прерывания;
If n = 0 Then Wait_Read; {буфер пустой}
n := n - 1;
М := Buf[out];
- 31 -
out := (out + 1) MOD N;
Signal_Write;
Разрешить прерывания;
End {TBuffer.Read};
В методах Signal_Read и Signal_Write управление не передается активизируемым процессам, а они лишь ставятся в очередь готовых процессов. Это может породить неопределенность, состоящую в том что, пока до их выполнения дойдет очередь, неизвестно, что будет с буфером. Поэтому активизацию процессов лучше выполнять не до включения в очередь готовых процессов, а до передачи управления активизируемому процессу. Метод Signal_Read для этого случая представлен ниже, а метод Signal_Write реализуется аналогично.
Procedure TBuffer.Signal_Read;
Var
Предыдущий, Локальный : Процесс;
Begin
Локальный := ReadList.Первый;
If Локальный <> NIL Then Begin {очередь не пустая}
Предыдущий := Текущий;
Текущий := Локальный;
ReadList.Извлечь(Локальный);
Очередь_готовых.Включить(Предыдущий);
Передать_управление(Предыдущий, Текущий);
End {If};
End {TBuffer.Signal_Read}.
Задание
- Реализовать объект-буфер в библиотечном модуле для некоторого типа передаваемых данных.
- Написать демонстрационную программу, иллюстрирующую работу буфера при
различных скоростях записи и чтения сообщений. Скорости записи и чтения можно
менять путем изменения количества процессов, пишущих в буфер или читающих из
буфера, или включая операторы задержки между следующими действиями:
- порождением сообщения и записью его в буфер;
- чтением сообщения из буфера и обработкой сообщения.