Язык Форт и его реализации

         

Многозадачный режим


Запуская на исполнение какое-либо форт-слово, программист имеет возможность исполнить следующее только по завершении исполнения предыдущего. Если исполнение данного слова требует значительного времени счета, то длительные перерывы в диалоге создают определенное неудобство. Ввиду этого представляется весьма привлекательной идея многозадачной форт-системы, в которой программист может создавать фоновые задачи и запускать их на исполнение, не прерывая диалога. Текстовый интерпретатор такой системы, обеспечивающий диалог, является одной из задач и разделяет центральный процессор наряду с другими задачами. Идея многозадачного режима привлекательна еще и тем, что разные задачи могут разделять значительную часть кода — практически все ядро форт-системы. Из стандартных слов только системные переменные (STATE, BASE и другие) и списки слов (FORTH, ASSEMBLER) не могут одновременно участвовать в нескольких вычислительных процессах (задачах), поскольку их код (значение поля параметров) в процессе работы может изменяться. В то же время вся остальная часть кода форт-системы, включая все слова, определенные через двоеточие и CONSTANT, в процессе работы не меняется и может даже размещаться в постоянной оперативной памяти (ПЗУ). Чтобы снять это ограничение, во многих реализациях выделены особая область для размещения значений, которые могут изменяться во время счета. Эта область называется пользовательской и обычно располагается в конце адресного форт-пространства рядом со стеками и буферным пулом. Распределение памяти внутри пользовательской области выполняет сам программист через определяющее слово USER (пользовательский):

: USER ( N:СМЕЩЕНИЕ-> ) CREATE , DOES> ( PFA->A:АДРЕС) @ U0 + ;

По характеру использования это слово аналогично CONSTANT; значение, которое оно снимает со стека и компилирует в поле параметров определяемого слова, представляет собой смещение от начала пользовательской области. При исполнении такого слова на стеке будет оставлен соответствующий адрес (слово U0, использованное в определении слова USER, дает адрес начала пользовательской области).
При наличии пользовательской области все системные переменные размещаются в ней, занимая какую-то ее начальную часть. Их словарные статьи определяются через слово USER, тем самым обеспечивается их неизменяемость в процессе работы.

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

Дальнейшие уточнения конкретного варианта многозадачного режима зависят от многих частных причин. Для примера рассмотрим реализацию системы ПОЛИФОРТ фирмы «Форт» []. Эта система реализована для целого ряда ЭВМ, включая персональный компьютер ИБМ. Использованный в ней механизм переключения задач основан на кольцевом принципе: все задачи связаны в кольцо через начальную часть своей пользовательской области (рис. 3.2). Задачи, составляющие кольцо, по очереди получают центральный процессор и удерживают его до тех пор, пока не исполнят слово PAUSE (пауза) или STOP (стоп). Для определений в машинном коде предусмотрен аналогичный код WAIT (ждать). Многие слова, которые выполняют асинхронные операции обмена (TYPE, EXPECT, BLOCK, BUFFER), содержат код WAIT или переход на STOP, чтобы в то время, когда они ждут завершения обмена, другие задачи могли использовать центральный процессор. Задачи, в которых для выполнения длительных вычислений нет необходимости обращаться к операциям обмена, должны сами периодически предоставлять процессор другим задачам, выполняя слово PAUSE.



Рис. 3.2. Кольцевой принцип реализации многозадачного режима



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

Для пробуждения задач часто используются асинхронные подпрограммы обработки прерываний. Например, если выход по прерыванию, установленный в слове EXPECT, распознает код возврата каретки, которым заканчивается вводимая строка, то он будит задачу, запросившую данный ввод с терминала, засылая команду WAKE (разбудить) на место ее команды JMP. Для этого часто используется какая-нибудь команда перехвата (например, для ЭВМ СМ-4 это команды TRAP и ЕМТ). Когда цикл передач управления по кольцу задач дойдет до этой команды, она передаст управление специальной подпрограмме-побудчику, которая и возобновит исполнение данной задачи от точки последнего остановка. При этом на место команды WAKE будет вновь заслана команда JMP, и исполнение данной задачи будет продолжаться до следующей операции PAUSE, STOP или WAIT. Пример цикла ввода и обработки данных с возобновлением по прерыванию дает следующее-определение:

: СБОР ( -> ) BEGIN ВВОД STOP ОБРАБОТКИ AGAIN ;

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

: СЧЕТ ( ->) 30000 0 DO ШАГ PAUSE LOOP ;

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

Действие STOP (для определений, заданных в машинном коде, аналогичное ему действие WAIT) состоит в сохранении текущего состояния задачи (указателя интерпретации, указателя вершины стека данных и указателя вершины стека возвратов) в ее пользовательской области и передаче управления по адресу из ее звена связи в кольце задач.




В результате центральный процессор будет исполнять цикл из передач управления по кольцу задач, пока не встретит команду WAKE. Действие PAUSE отличается от описанного действия STOP только тем, что предварительно засылает команду WAKE в начало области данной задачи, обеспечивая тем самым пробуждение данной задачи после полного круга передач управления. Действие WAKE заключается в том, что команда JMP засылается на отведенное ей место в начало пользовательской области, восстанавливается текущее состояние данной задачи из ее области сохранения, управление передается на точку NEXT адресного интерпретатора. В результате исполнение задачи возобновляется от точки останова.

Для определения фоновой задачи используется определяющее слово BACKGROUND (фон), которое снимает со стека три числа: размер пользовательской области, размер стека данных и размер стека возвратов. Это слово резервирует в словаре память указанного объема и указатели на эти области компилирует в поле параметров создаваемой статьи, например, 40 60 50 BACKGROUND T. При исполнении слова T на стеке оставляется адрес его поля параметров, через который можно добраться до пользовательской области и стеков задачи T. Данное описание только подготавливает задачу, но не включает ее в кольцо задач и не запускает на исполнение.

При запуске форт-системы в кольце задач присутствует только одна задача — OPERATOR (оператор), звено связи которой указывает на нее же. Для встраивания в кольцо новых задач используется слово BUILD (построить), например T BUILD. Это слово, используя адрес поля параметров статьи для задачи, инициализирует ее пользовательскую область и включает ее в кольцо задач после задачи OPERATOR. При этом в начало области вписывается команда JMP, предохраняющая данную задачу от преждевременного исполнения. Заметим, что форт-слова, составляющие программу данной задачи, могут быть определены значительно позже. Обратное действие — исключение задачи из кольца задач — выполняет аналогичное по употреблению слово RUIN (разрушить).



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

: СЧЕТ ( PFA->) ACTIVATE BEGIN ШАГ PAUSE LOOP ; Т СЧЕТ

Задача T будет выполнять бесконечный цикл, разделяя центральный процессор с текстовым интерпретатором форт-системы — задачей OPERATOR. Исполнение задачи можно оставить с помощью слова HALT (останов):

: HALT ( PFA-> ) ACTIVATE STOP ;

если в рамках задачи OPERATOR исполнить текст T HALT. После такого останова данную задачу можно запустить на счет с какой-нибудь другой форт-программой.

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

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

Определим слова GET (получить) и RELEASE (освободить), аналогичные семафорным операциям Дейкстры [].


В определениях этих слов используется вспомогательное слово FREE (свободен), проверяющее, свободен ли ресурс. Заметим, что ресурс свободен с точки зрения данной задачи, если он не занят или занят этой же задачей.

: FREE ( A:СЕМАФОР -> A,F:ПРИЗНАК СВОБОДНОСТИ ) @ DUP 0= SWAP U0 = OR ; : GET ( A:СЕМАФОР-> ) BEGIN PAUSE FREE UNTIL U0 SWAP ! ; : RELEASE ( A:СЕМАФОР ->) FREE IF 0 SWAP ! ELSE DROP THEN ;

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

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

VARIABLE ДИСК VARIABLE ЛЕНТА : ШАГ1 ДИСК GET ЛЕНТА GET ... ; : ШАГ2 ЛЕНТА GET ДИСК GET ... ;

Если слова ШАГ1 и ШАГ2 исполняются в разных задачах, то это может привести к их взаимной блокировке. Наилучший способ избежать такой ситуации — не запрашивать более одного ресурса единовременно. Например, в случае работы с диском и лентой, задача может запросить ресурс ДИСК, выполнить слово BLOCK для получения данных, затем переслать эти данные в свою локальную область и, освободив ДИСК, запросить ресурс ЛЕНТА.


Содержание раздела