Н. Вирт - Программирование на языке Модула-2 (1160777), страница 26
Текст из файла (страница 26)
Эти два условия приводят к описанию двух сигналов, называемых непуст и неполон,используемых для реактивации ждущих процессов. Монитор Буфер запрограммирован каклокальный модуль. Переменная п содержит число элементов, находящихся в буфере.MODULE Буфер [1];EXPORT Поместить,Извлечь;IMPORT SIGNAL,SEND,WAIT, Init,ТипЭлемента;CONST N = 128; (* размер буфера *)VAR n: [0..N]; (* число помещенных элементов *)неполон: SIGNAL; (* n < N *)непуст: SIGNAL; (* n > 0 *)in, out: [0..N-l]: (*индексы*)буф: ARRAY [0..N-1] OF ТипЭлемента;PROCEDURE Поместить(х: ТипЭлемента);BEGINIF n = N THEN WAIT(неполон) END;(* n < N *) n := n + 1; (* 0 < n <= N *)буФ[in] := x; in := (in + 1) MOD N;SEND(непуст)END Поместить;PROCEDURE Извлечь(VАР х: ТипЭлемента);BEGINIF n = 0 THEN WAIT(нenycт) END;(* n > 0 *) n := n - 1; (* 0 <= n < N *)x := буф[оut]; out := (out + 1) MOD N;SEND(неполон)END Извлечь;BEGIN n := 0; in := 0; out := 0;130Init(неполон); Inlt(HenycT)END БуферК сожалению, приведенная версия алгоритма буферизации имеет обыкновение посылатьсигнал всякий раз, как только элемент помещается в буфер или извлекается из него.
Однако, впринципе, синхронизирующие сигналы нужно посылать, только если есть процесс, который егодействительно ждет. Хороший принцип минимизировать число обменов сигналами и тем самымуменьшить степень связи процессов. Усовершенствование в этом направлении достигается вверсии алгоритма, предложенной Дейкстрой и носящей название "алгоритм спящегопарикмахера".
В этой версии диапазон переменной п расширяется. Теперь в случае, когда вмонитор не вошел ни один процесс, переменная п имеет такой смысл:n < 0:буфер пуст и - n потребителей в состоянии ожидания0 <= n <= N:буфер содержит n элементов и ожидающих процессов нетN < n:буфер полон и n - N поставщиков в состоянии ожиданияПроцедуры Поместить и Извлечь описываются так:PROCEDURE Поместить(х: ТипЭлемента);BEGIN0 n := n + 1;IF n > N THEN WAIT(неполон) END;(* n <= N *)буФ[in] := x; in := (in + 1) MOD N;IF n <= 0 THEN SEND(непуст) ENDEND Поместить;PROCEDURE Извлечь(VAR x: ТипЭлемента);BEGIN n := n - 1;IF n < 0 THEN WAIT(непуст) END;(* n >= 0 *)x := буф[out]; out := (out + 1) MOD N;IF n >= N THEN SEND(неполон) ENDEND Извлечь;Теперь обсудим проблему представления модуля Processes и дадим одно из возможныхрешений.
Подчеркнем, что это лишь одна из возможностей. Решение рассчитано наоднопроцессорную машину, и этот единственный процессор разделяется во времени дляобслуживания различных процессов. Решение основано на понятии сопрограммы. Сопрограмма последовательная программа, по существу сходная с процессом, как он обсуждался выше.Принципиальные различия между процессом и сопрограммой следующие:1.
Известно, что сопрограммы выполняются квазипараллельно. Следовательно, ихиспользование исключает трудную проблему взаимодействия истинно параллельных процессов.1312. Переключение процессора от одной сопрограммы к другой осуществляется явнымоператором передачи управления. Выполнение сопрограммы, которой передается управление,возобновляется с той точки, где она была приостановлена последним таким оператором.Очевидно, что на однопроцессорной машине процесс может быть реализовансопрограммой, возникающей на более низком концептуальном уровне. Ее близость к реальнымЭВМ становится очевидной, если сравнить оператор передачи управления Модулы с машиннымоператором перехода.
Такой сопрограммный переход должен запоминать текущее состояниевыполняемой процедуры, о которой говорят, что она приостанавливается. Эта процедура может бытьзатем возобновлена, если другая сопрограмма передаст управление назад приостановленной. Привыполнении операторов передачи управления сопрограмма указывается явно, в отличие отоператоров SEND и WAIT, используемых для синхронизации процессов.Поскольку в Модуле сопрограммы считаются средствами низкого уровня, связанные сними типы и операции должны импортироваться из модуля SYSTEM (см.
раздел, посвященныйсредствам низкого уровня) или из другого модуля низкого уровня. В частности, там имеются типADDRESS и процедура TRANSFER.Заголовок процедуры передачи управления выглядит так:PROCEDURE TRANSFER(VAR источн,приемн: ADDRESS);Ее вызов приводит к задержке вызывающей сопрограммы (чтобы позже бытьвозобновленной, начиная с оператора, следующего за вызовом) и возобновлению сопрограммы,принимающей управление, с точки задержки. Для создания сопрограммы должна вызыватьсяпроцедура NEWPROCESS (новый процесс).PROCEDURE NEWPROCESS(P: PROC; A: ADDRESS;n: CARDINAL; VAR Нов: ADDRESS);Идентификатор Р обозначает процедуру без параметров, представляющую программу длявновь создаваемой сопрограммы: А -начальный адрес рабочей области, в которой размещаютсялокальные переменные сопрограммы и запоминается состояние сопрограммы при задержке: n объем рабочей области в единицах памяти.
Вызов присваивает переменной Нов ссылку на вновьсоздаваемую сопрограмму, причем ее состояние инициализируется так, что при передаче ейуправления выполнение начинается от начала процедуры Р. Следовательно, сопрограммыначинаются явной передачей управления и должны заканчиваться тоже такой передачей.Теперь можно представить реализацию модуля Processes в терминах сопрограмм.Существенный аспект состоит в том, что вызовы WAIT и SEND должны транслироваться воператоры передачи, в которых необходимо указывать, куда именно передается управление.Следовательно, модуль Processes должен включать в себя административную систему, котораясправедливо распределяет процессорное время между процессами. Такая административнаясистема называется диспетчером.
Обычно это часть операционной системы ЭВМ. Вдействительности конкретные реализации могут запрещать введение сопрограмм и предоставлятьтолько средства высокого уровня, содержащиеся в модуле Processes.IMPLEMENTATION MODULE Processes [1];FROM SYSTEM IMPORT ADDRESS,TSIZE,NEWPROCESS,TRANSFER;FROM Storage IMPORT Allocate;TYPE SYGNAL = POINTER TOДескрипторПроцесса; ДескрипторПроцесса =132RECORD следующий: SIGNAL; (* кольцевой список *)очередь: SIGNAL; (* очередь ждущих процессов *)сопрг: ADDRESS;готов: BOOLEANEND;VAR ТекПроцесс: SIGNAL; (* текущий процесс *)PROCEDURE StartProcess(p: PROC; n: CARDINAL);VAR s0: SIGNAL; РОбл: ADDRESS;BEGIN s0 := ТекПроцесс;А11оса1е(Р0бл,n); Al1ocate(ТекПроцесс,TSIZE(ДескрипторПроцесса));WITH ТекПроцесс^ DOследующий := s0^.
следующий;s0^.следующий := ТекПроцесс;готов := TRUE; очередь := NILEND;NEWPROESS(P,РОбл,n,ТекПроцесс^. сопрг);TRANSFER(s0".сопрг,ТекПроцесс^. сопрг)END StartProcess;PROCEDURE SEND(VAR s: SIGNAL);VAR s0: SIGNAL;BEGINIF s # NIL THENs0 := ТекПроцесс; ТекПроцесс := s; WITH ТекПроцесс^ DOs := очередь; готов := TRUE; очередь := NIL END;TRANSFER(s0^.сопрг,ТекПроцесс^. сопрг)ENDEND SEND;PROCEDURE WAIT(VAR s: SIGNAL);133VAR s0,sl: SIGNAL;BEGIN (* вставить ТекПроцесс в очередь s *)IF s = NIL THEN s := ТекПроцессELSE s0 := s; si := s0^.очередь;WHILE si # NIL DOs0 := si; sl := s0^.очередьEND;s0^. очередь := ТекПроцессEND;s0 := ТекПроцесс;REPEAT ТекПроцесс := ТекПроцесс^. следующийUNTIL ТекПроцесс".готов;IF ТекПроцесс = s0 THEN (*тупик*) HALT END;s0^.готов := FALSE;TRANSFER(s0^.сопрг,ТекПроцесс^. сопрг)END WAIT;PROCEDURE Awaited(s: SIGNAL): BOOLEAN;BEGIN RETURN s # NILEND Awaited;PROCEDURE Inlt(VAR s: SIGNAL);BEGIN s := NILEND Init;BEGIN Allocate(ТекПроцесс,TSIZE(ДескрипторПроцесса));WITH ТекПроцесс^ DOследующий := ТекПроцесс; готов := TRUE; очередь := NILENDEND Processes.При запуске процесса вызовом StartProcess(P,n) происходит выделение памяти поддескриптор (описатель) процесса и рабочую область связанной с ним сопрограммы.
Дескрипторвставляется в кольцевой список, содержащий дескрипторы всех процессов, созданных до сих пор.134Переменная ТекПроцесс указывает на дескриптор текущего выполняемого процесса. Просмотромкольцевого списка можно добраться до любого процесса. Процесс-преемник обозначаетсякомпонентой следующий дескриптора.Ключевым вопросом является способ представления сигналов. В то время как на уровнеабстракции пользователя сигнал представляет возникающее условие, на уровне реализации - этомножество процессов, ждущих сигнала.
Так как число этих процессов неизвестно, будет разумнымрешением организовать их в связанный список. Следовательно, переменная типа SIGNALпредставляет собой голову списка, а каждый дескриптор процесса содержит компоненту очередь.связывающую его со следующим процессом, ждущим сигнала. Если ждущих процессов нет, то егозначение равно NIL.Из приведенного описания становятся очевидными функции процедур SEND и WAIT.SEND берет первый элемент списка s и возобновляет соответствующий ему процесс. Процесс,посылающий сигнал (на его дескриптор указывает переменная ТекПроцесс), приостанавливается.WAIT ставит вызывающий ее процесс (на его дескриптор указывает ТекПроцесс) в конец спискаждущих процессов. Вставка производится в конец, чтобы удовлетворить требованиюсправедливости распределения процессорного времени и обеспечить невозможность одномупроцессу обогнать другой, ждущий тот же сигнал, поскольку список реализует дисциплинуочереди. Получается так, что, в принципе, ни один процесс, не ждущий сигнала, не может бытьвозобновлен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
