Параллельная работа
4. Параллельная работа
Основной областью применения языков ООП является моделирование - представление знаний в ЭВМ о процессах и явлениях окружающего мира.
Для адекватного моделирования необходима реализация механизма, обеспечивающего параллельную работу системы. В Смолтоке такая работа обеспечивается использованием трех механизмов: параллелизма (parallelism), планирования (scheduling) и синхронизации (synchronisation).
Параллелизм обеспечивает синхронное выполнение двух и более процессов (программ), планирование - управление распределением процессорного времени между этими независимо выполняющимися программами, а синхронизация - правильный обмен информацией между отдельными выполняющимися программами. В языке Смолток для реализации этих функций имеются три класса: Process, ProcessScheduler и Semaphore, которые и выполняют работу по организации параллелизма, планирования и синхронизации соответственно.
Параллелизм. Класс Process реализует механизм распараллеливания. В общем случае при создании экземпляра класса Process оператору блока посылается сообщение fork. Например, если программа computeFunc, вычисляющая значение некоторой функции, определяется как метод класса для класса Float и выполняется
[Float computeFunc] fork,
то создается процесс вычисления функции, начинающий свою работу независимо от других процессов. Поскольку программа, породившая этот процесс, продолжает по-прежнему работать, одновременно с вычислением функции может продолжаться и другая работа в порождающей программе. Основными сообщениями, посылаемыми другими процессами, являются следующие:
newProcess создать новый процесс, но не выполнять его;
resume выполнить остановленный процесс;
suspend остановить процесс;
terminate закончить процесс.
Например, если выполнить выражение
FProcess = [Float computeFunc] newProcess,
то сформируется новый процесс, однако он будет находиться в состоянии ожидания и выполняться не будет. Выполнение его начнется только после того, как будет выполнено сообщение:
FProcess resume.
Диспетчеризация. Система Смолток (Смолток-80) построена так, что она может работать только на однопроцессорной машине. Поэтому при наличии нескольких работающих одновременно процессов могут возникать конфликтные ситуации (например, при одновременном обращении к внешним устройствам или к файлам).
Для предотвращения конфликтных ситуаций необходима реализация методов организации вычислительных процессов (диспетчеризация или планирование). Для этого создается класс ProcessScheduler. Этот класс имеет единственный экземпляр, указателем на который является глобальная переменная Processor.
Алгоритм диспетчеризации реализуется через простую систему приоритетов (priority system). Каждому процессу назначается приоритет. Если процесс, выполняющийся в данный момент, останавливается или завершается, то из процессов, находящихся в состоянии ожидания, выбирается и запускается тот, который обладает наивысшим приоритетом. Чтобы остановить выполняющийся в данный момент процесс, посылается сообщение suspend либо внутри самого выполняемого процесса вызывается процедура с наименованием yield. Процедура yield
представляет собой метод, с помощью которого выполняется следующее. Если имеется остановленный процесс с приоритетом, равным приоритету процесса, который выполняется в настоящий момент, то он запускается. Если же такого процесса нет, то продолжается выполнение текущего процесса. Приоритет вычисляется системой, и если необходимо программу вычисления функции из предыдущего примера запустить как фоновую задачу, то это запишется в следующем виде:
[Float computeFunc] forkAt:Processor userBackgroundPriority
Пример сеанса работы (рабочее окно Smalltalk Express):
|aStream n block1 block2 w nfibo flimit|
w := TextWindow windowLabeled: 'Fibo' frame: (100@100 extent: 400@200).
flimit := 25.
aStream := WriteStream on: String new.
block1 := [ n := 0.
[n<flimit] whileTrue:
[n:=n+1.
nfibo := ( n fibo).
nfibo printOn: aStream. ' ' printOn: aStream.
w nextPutAll: ' P-1 '.
w nextPutAll: (n radix:10).
w nextPutAll: ' : '.
w nextPutAll: (nfibo radix:10); cr.].
w nextPutAll: 'Process 1 done.'; cr.].
block2 := [ n := 0.
[n<flimit] whileTrue:
[n:=n+1.
nfibo := ( n fibo).
nfibo printOn: aStream. ' ' printOn: aStream.
w nextPutAll: ' P-2 '.
w nextPutAll: (n radix:10).
w nextPutAll: ' : '.
w nextPutAll: (nfibo radix:10); cr.].
w nextPutAll: 'Process 2 done.'; cr.].
block1 forkAt: (ProcessScheduler new lowUserPriority).
block2 forkAt: (ProcessScheduler new lowUserPriority).
Результаты работы отображаются как в окне, так и в потоке
aStream (aStream contents).
Процессы можно породить и вызовами
Processor fork: block1.
block1 fork.
Приоритеты процессов в Smalltalk Express определяются методами класса ProcessScheduler
userPriority
highUserPriority
lowUserPriority
topPriority
Синхронизация. Методы управления и синхронизации процессов (обрабатывающих единиц), находящихся между собой в конкурентных отношениях, делятся на две большие группы. Одна из них включает в себя методы, основанные на общих переменных, вторая - на посылке заявок. Метод семафоров Дейкстры, рассматриваемый ниже, относится к методу управления и синхронизации, основанному на общих переменных. Для реализации семафоров Дейкстры используют переменные семафоров и функции P и V.
Пусть sem - переменная семафора. Ее значения - целые неотрицательные числа. Если при выполнении функции P(sem) в работающем в данный момент процессе значение sem окажется равным нулю, то процесс останавливается, переводится в состояние ожидания, ставится в очередь, связанную с данным семафором, и будет находиться в этом состоянии до тех пор, пока переменная sem не станет больше нуля (пока не откроется семафор).
Если при этом имеется какой-либо другой процесс, готовый к выполнению, то он выполняется. Если sem > 0, то оператор P уменьшает значение sem на единицу (процесс закрывает семафор).
При выполнении функции V к значению sem прибавляется единица (семафор открывается), и если в очереди к семафору имеются процессы, то выбирается один из них, делается активным, а от значения sem вычитается единица (семафор вновь закрывается).
Естественно, что операторы P и V являются взаимоисключающими. Кроме того, функции P и V для одного семафора должны быть доступны внешним прерываниям.
Аналогичный механизм реализован в объектах языка Смолток. Экземпляры класса Semaphore являются переменными семафора. Сообщение signal соответствует операции V, а сообщение wait - операции P. Создаваемому семафору присваивается значение 0.
Рассмотрим решение задачи создания кольцевого буфера на N ячеек с использованием механизма семафоров:
Схема кольцевого буфера на 10 ячеек
Этому буферу посылаются сообщения fetch (принести) и store:data (сохранить). При этом считается, что при пустом буфере должны останавливаться все процессы, посылающие ему сообщения fetch до тех пор, пока в буфер не будет занесено значение. При полном буфере должны останавливаться те процессы, которые посылают сообщения store:data. Во всех остальных случаях процессы чтения и записи должны действовать независимо друг от друга.
Для этого создаются два семафора: EMPTY и FULL. Семафору EMPTY присваивается начальное значение 0, семафору FULL - значение N - число ячеек в буфере (в нашем примере N = 10). Таким образом, при сообщении fetch
посылаются сообщения EMPTY wait и FULL signal, а при сообщении store:data посылаются сообщения FULL wait и EMPTY signal. В результате содержимое семафора EMPTY оказывается равным количеству данных, содержащихся в буфере, а содержимое семафора FULL - количеству свободных мест в буфере. При пустом буфере процесс, пытающийся осуществить доступ к нему, останавливается сообщением EMPTY wait, при полном - сообщением FULL wait.
Кроме того, нельзя допускать одновременного доступа к переменным экземпляра HEAD и TAIL. Доступ должен быть взаимоисключающим. Для этого используются переменные FetchProtect и StoreProtect.
Описание классов BUFFER и RINGBUFFER выглядит так:
" Класс BUFFER "
Object subclass: #Buffer
instanceVariableNames:
'next val '
classVariableNames: ''
poolDictionaries: '' !
!Buffer methods !
next
^next.!
next: link
next := link.!
put: data
val := data.!
val
^val.! !
" Класс RINGBUFFER "
Object subclass: #RingBuffer
instanceVariableNames:
'empty full head tail fetchprotect storeprotect '
-- семафоры:
-- empty - количество данных в буфере
-- full - количество свободных мест
-- head, tail - указатели на начало и конец
-- fetchprotect и storeprotect - вспомогательные переменные, обеспечивающие
-- взаимоисключение
classVariableNames: ''
poolDictionaries: '' ! !
!RRingBuffer class methods !
create: size
^self new init: size.! !
!RRingBuffer methods !
init: size
head := tail := Buffer new.
1 to: size - 1 do: [ :i | tail next: Buffer new. tail := tail next].
tail next: head.
tail := head.
empty := Semaphore new.
full := Semaphore new.
1 to: size do: [:i | full signal].
fetchprotect := Semaphore new signal.
storeprotect := Semaphore new signal.!
fetch
|data|
empty wait.
fetchprotect wait.
data := tail val.
tail := tail next.
fetchprotect signal.
full signal.
^data.!
store: data
full wait.
storeprotect wait.
head put: data.
head := head next.
storeprotect signal.
empty signal.! !
Ниже приведен фрагмент рабочего окна:
|n block1 block2 w nfibo rb d flimit|
flimit := 25.
rb := RingBuffer new init: 20.
w := TextWindow windowLabeled: 'Ring Buffer' frame: (100@100 extent: 400@200).
block1 := [ n := 0.
[n<flimit] whileTrue:
[n:=n+1.
nfibo := ( n fibo).
rb store: nfibo.].
w nextPutAll: 'Process 1 done.'; cr.].
block2 := [ n := 0.
[n<flimit] whileTrue:
[ n := n+1.
d := rb fetch.
w nextPutAll: (d radix:10); cr.].
w nextPutAll: 'Process 2 done.'; cr.].
block1 forkAt: 1.
block2 forkAt: 1.
