Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия Последняя версия Следующая версия справа и слева | ||
ao [2016/04/14 17:21] prospero78 [2.5 SELF] |
ao [2022/08/17 16:45] iadenisov |
||
---|---|---|---|
Строка 1: | Строка 1: | ||
- | ====== | + | ====== |
- | Patrik Reali * | + | Активный Оберон произошел от Оберона, |
- | 27 октября 2004 г. | + | [[http:// |
- | Перевод Андреева М.В. опубликован | + | [[ao: |
- | ===== 1 Введение ===== | + | [[https:// |
- | **Active Oberon**((информация в [[https:// | + | Активный Оберон реализован в [[ao:a2|операционной системе A2]]. |
- | Проектирование расширения языка направлялось на достижение унификации и гармонии. Изменения основаны на устоявшихся концепциях, | ||
- | ==== 1.1 Благодарности ==== | ||
- | |||
- | |||
- | Большое спасибо **B. Kirk, A. Fischer, T. Frei, J. Gutknecht, D. Lightfoot**, | ||
- | |||
- | ==== 1.2 Предыстория и родственные работы ==== | ||
- | |||
- | Разработка языков программирования в **ETH Zurich** имеет богатые традиции. Язык **Oberon** — это последний наследник семейства **Algol, Pascal** и **Modula**. **Pascal** [16] задумывался как язык для представления маленьких программ; | ||
- | |||
- | Множество расширений языка **Oberon** было предложено как в **ETH**, так и вне его. **Object Oberon** [19], **Oberon-2** [18], и **Froderon** [7] исследуют добавление дополнительных объектно-ориентированных свойств в язык; **Oberon-V** [9] предлагает дополнения для поддержки параллельных операций на векторных компьютерах; | ||
- | |||
- | PIC FIXME | ||
- | Рис. 1: Эволюция языков семейства Pascal | ||
- | |||
- | **Active Oberon** — это первый представитель нового поколения языков в данном семействе. Мы старались добавить в язык поддержку параллелизма и моделирования компонентов ясным и безболезненным способом. | ||
- | |||
- | ==== 1.3 Дизайн языка ==== | ||
- | |||
- | На дизайн **Active Oberon** повлиял опыт, полученный при проектировании **Oberon** и **Oberon-2**. Мы следуем нотации **Object Oberon** для объявления классов и методов, | ||
- | |||
- | **Java** [8] и **C#** [4] разделяют некоторые похожие идеи с **Active Oberon**. Они так же являются объектно-ориентированными языками из мира императивных языков, | ||
- | |||
- | Оператор '' | ||
- | |||
- | **Concurrent Oberon** был первой попыткой реализовать параллелизм в системе **Oberon**. Это было сделано через специальный **API**, определяющий тип '' | ||
- | |||
- | ===== 2 Объектно-ориентированные расширения ===== | ||
- | |||
- | ==== 2.1 Указатель на безымянные типы записей ==== | ||
- | |||
- | <code oberon2> | ||
- | TYPE | ||
- | (* пример указателя на безымянные типы записей *) | ||
- | |||
- | (* указатели на именованные типы записей *) | ||
- | Tree = POINTER TO TreeDesc; | ||
- | TreeDesc = RECORD key: INTEGER; l, r: Node END; | ||
- | |||
- | (* указатели на безымянные типы записей *) | ||
- | Node = POINTER TO RECORD key: INTEGER; next: Node END; | ||
- | DataNode = POINTER TO RECORD (Node) data: Data END; | ||
- | DataTree = POINTER TO RECORD (Tree) data: Data END; | ||
- | </ | ||
- | |||
- | Типы '' | ||
- | |||
- | // | ||
- | |||
- | Типы '' | ||
- | |||
- | ==== 2.2 Объектные типы ==== | ||
- | |||
- | <code oberon2> | ||
- | TYPE | ||
- | (* объектные типы *) | ||
- | DataObj = OBJECT VAR data: Data; l, r: DataObj END DataObj; | ||
- | </ | ||
- | |||
- | '' | ||
- | |||
- | Синтаксис типа '' | ||
- | |||
- | Только // | ||
- | ==== 2.3 Связанные с типом процедуры ==== | ||
- | |||
- | <code oberon2> | ||
- | TYPE | ||
- | Coordinate = RECORD x, y: LONGINT END; | ||
- | |||
- | VisualObject = OBJECT | ||
- | VAR next: VisualObject; | ||
- | |||
- | PROCEDURE Draw*; (*нарисовать данный объект*) | ||
- | BEGIN HALT(99); (*заставить расширения переопределять этот метод*) | ||
- | END Draw; | ||
- | END VisualObject; | ||
- | |||
- | Point = OBJECT (VisualObject) | ||
- | VAR pos: Coordinate; | ||
- | |||
- | PROCEDURE Draw*; (*перекрываем метод Draw, объявленный в VisualObject*) | ||
- | BEGIN MyGraph.Dot(pos.x, | ||
- | END Draw; | ||
- | END Point; | ||
- | |||
- | Line = OBJECT (VisualObject) | ||
- | VAR pos1, pos2: Coordinate; | ||
- | |||
- | PROCEDURE Draw*; | ||
- | BEGIN MyGraph.Line(pos1.x, | ||
- | END Draw; | ||
- | END Line; | ||
- | |||
- | VAR | ||
- | objectRoot: VisualObject; | ||
- | |||
- | PROCEDURE DrawObjects*; | ||
- | VAR p: GraphObject; | ||
- | BEGIN | ||
- | (* рисуем все объекты из списка *) | ||
- | p := objectRoot; | ||
- | WHILE p # NIL DO p.Draw; p := p.next END; | ||
- | END DrawObjects; | ||
- | </ | ||
- | |||
- | // | ||
- | |||
- | **Замечание**: | ||
- | |||
- | Дан экземпляр объекта o типа '' | ||
- | |||
- | ==== 2.4 Инициализаторы ==== | ||
- | |||
- | Метод, помеченный символом ''&'' | ||
- | |||
- | Если объектный тип '' | ||
- | |||
- | **Замечание**: | ||
- | |||
- | <code oberon2> | ||
- | TYPE | ||
- | Point = OBJECT (VisualObject) | ||
- | VAR pos: Coordinate; | ||
- | |||
- | PROCEDURE & InitPoint(x, | ||
- | BEGIN pos.x := x; pos.y := y | ||
- | END InitPoint; | ||
- | |||
- | END Point; | ||
- | |||
- | PROCEDURE NewPoint(): Point; | ||
- | VAR p: Point; | ||
- | BEGIN NEW(p, x, y); (* вызывает NEW(p) и p.InitPoint(x, | ||
- | RETURN p | ||
- | END NewPoint; | ||
- | </ | ||
- | |||
- | ==== 2.5 SELF ==== | ||
- | |||
- | Ключевое слово '' | ||
- | |||
- | <code oberon2> | ||
- | TYPE | ||
- | ListNode = OBJECT | ||
- | VAR data: Data; next: ListNode; | ||
- | |||
- | PROCEDURE & InitNode (data: Data); | ||
- | BEGIN | ||
- | SELF.data := data; (* инициализируем данные объекта *) | ||
- | next := root; root := SELF (* добавляем node в начало списка *) | ||
- | END InitNode; | ||
- | END ListNode; | ||
- | |||
- | VAR | ||
- | root: ListNode; | ||
- | </ | ||
- | |||
- | ==== 2.6 Делегаты ==== | ||
- | |||
- | |||
- | < | ||
- | MediaPlayer = OBJECT | ||
- | PROCEDURE Play; .... показать фильм .... END Play; | ||
- | PROCEDURE Stop; .... остановить фильм .... END Stop; | ||
- | END MediaPlayer; | ||
- | |||
- | ClickProc = PROCEDURE {DELEGATE}; | ||
- | |||
- | Button = OBJECT | ||
- | VAR | ||
- | onClick: ClickProc; | ||
- | caption: ARRAY 32 OF CHAR; | ||
- | |||
- | PROCEDURE OnClick; | ||
- | BEGIN onClick END OnClick; | ||
- | |||
- | PROCEDURE & Init(caption: | ||
- | BEGIN SELF.onClick := onClick; COPY(caption, | ||
- | END Init; | ||
- | END Button; | ||
- | |||
- | PROCEDURE Init(p: MediaPlayer); | ||
- | VAR b0, b1, b2: Button; | ||
- | BEGIN | ||
- | (* Перезагрузка -> вызвать системную функцию *) | ||
- | NEW(b0, " | ||
- | |||
- | (* Интерфейс MediaPlayer: | ||
- | NEW(b1, " | ||
- | NEW(b2, " | ||
- | END Init;</ | ||
- | |||
- | Делегаты подобны процедурным типам; они совместимы как с процедурами так и с методами, | ||
- | |||
- | Делегаты процедурных типов помечаются модификатором DELEGATE. Делегатам могут быть назначены процедуры и методы. Пусть даны переменная с процедурным типом t, экземпляр объекта o и метод M связанный с o, тогда можно записать o.M в t, если конечно метод и t обладают совместимыми сигнатурами. Ссылка на сам объект исключается из сигнатуры процедурного типа. Всякий раз при вызове t назначенный объект o явно передается в self-ссылку (self-reference). Присваивания и вызовы процедур остаются совместимыми с описанием Oberon. | ||
- | |||
- | ==== 2.7 Описания (definitions) ==== | ||
- | |||
- | |||
- | Описание (definition) — это синтаксический контракт 1, определяющий набор сигнатур методов. Описание D0 может быть уточнено новым описанием D1, которое наследует все методы, | ||
- | |||
- | < | ||
- | PROCEDURE Start; | ||
- | PROCEDURE Stop; | ||
- | END Runnable; | ||
- | |||
- | DEFINITION Preemptable REFINES Runnable; | ||
- | PROCEDURE Resume; | ||
- | PROCEDURE Suspend; | ||
- | END Preemptable; | ||
- | |||
- | TYPE | ||
- | MyThread = OBJECT IMPLEMENTS Runnable; | ||
- | PROCEDURE Start; | ||
- | BEGIN .... END Start; | ||
- | |||
- | PROCEDURE Stop; | ||
- | BEGIN .... END Stop; | ||
- | END MyThread;</ | ||
- | |||
- | Ключевое слово IMPLEMENTS используется для указания описаний, | ||
- | |||
- | Описания можно понимать как дополнительные свойства, | ||
- | |||
- | < | ||
- | BEGIN | ||
- | Runnable(o).Start; | ||
- | Delay(timeout); | ||
- | Runnable(o).Stop; | ||
- | END Execute;</ | ||
- | |||
- | ===== 3 Поддержка параллелизма ===== | ||
- | |||
- | |||
- | ==== 3.1 Активные объекты ==== | ||
- | |||
- | |||
- | Определение объекта может включать StatBlock, названное телом объекта (object body). Тело --- это активность объекта, | ||
- | |||
- | Если не указан модификатор ACTIVE, тело исполняется синхронно; | ||
- | |||
- | Система сохраняет явные ссылки на активные объекты до завершения исполнения активности для того, чтобы избежать утилизацию объекта в процессе сборки мусора. Объект может пережить свою активность. | ||
- | |||
- | < | ||
- | (* определяем объект и его поведение *) | ||
- | Object = OBJECT | ||
- | BEGIN {ACTIVE} (* тело объекта *) | ||
- | ... делаем что-либо ... | ||
- | END Object; | ||
- | |||
- | PROCEDURE CreateAndStartObject; | ||
- | VAR o: Object; | ||
- | BEGIN | ||
- | ... NEW(o); ... | ||
- | END CreateAndStartObject;</ | ||
- | |||
- | Активность объекта завершается после завершения исполнения тела объекта. Пока исполняется тело, объект продолжает существовать (например, | ||
- | |||
- | ==== 3.2 Защита ==== | ||
- | |||
- | |||
- | Statement Block --- это последовательность операторов, | ||
- | |||
- | < | ||
- | VAR x, y, z: LONGINT; | ||
- | BEGIN | ||
- | x := 0; | ||
- | BEGIN | ||
- | y := 1 | ||
- | END; | ||
- | z := 3 | ||
- | END P;</ | ||
- | |||
- | Объект может рассматриваться как ресурс и различные активности могут потенциально соревноваться за его использование или за эксклюзивный доступ к предоставляемым им средствам; | ||
- | < | ||
- | TYPE | ||
- | MyContainer = OBJECT | ||
- | VAR x, y: LONGINT; (* Инвариант: | ||
- | |||
- | PROCEDURE Set(x: LONGINT); | ||
- | BEGIN {EXCLUSIVE} (* изменение x и y атомарно *) | ||
- | SELF.x := x; y := f(x) | ||
- | END Set; | ||
- | |||
- | PROCEDURE Reset; | ||
- | BEGIN | ||
- | ... | ||
- | BEGIN {EXCLUSIVE} (* изменение x и y атомарно *) | ||
- | x := x0; y := y0; | ||
- | END; | ||
- | .... | ||
- | END Reset; | ||
- | END MyContainer</ | ||
- | |||
- | Каждый экземпляр объекта защищен и единицей защиты является произвольный блок операторов от отдельного оператора до целого метода. Блок операторов может быть защищен от одновременного доступа при помощи модификатора EXLUSIVE. Активность остается на входе в эксклюзивный блок до тех пор, пока другая активность находится в эксклюзивном блоке того же экземпляра объекта. | ||
- | |||
- | Активность не может заблокировать объект более одного раза, повторный вход не допускается. | ||
- | |||
- | Каждый модуль считается объектным типом с единственным экземпляром (singleton instance), таким образом его процедуры тоже могут быть защищены. Областью видимости защиты является модуль целиком как и в случае мониторов [13]. | ||
- | |||
- | Замечание: | ||
- | |||
- | Замечание: | ||
- | |||
- | ==== 3.3 Синхронизация ==== | ||
- | |||
- | < | ||
- | Synchronizer = OBJECT | ||
- | awake: BOOLEAN | ||
- | |||
- | PROCEDURE Wait; | ||
- | BEGIN {EXCLUSIVE} AWAIT(awake); | ||
- | END Wait; | ||
- | |||
- | PROCEDURE WakeUp; | ||
- | BEGIN {EXCLUSIVE} awake := TRUE | ||
- | END WakeUp; | ||
- | END Synchronizer;</ | ||
- | |||
- | Встроенная процедура AWAIT используется для синхронизации активности с состоянием системы. Аргументом AWAIT может быть только логическое условие; | ||
- | |||
- | Система отвечает за проверку условий и за возобновление работы приостановленных активностей. Условия внутри экземпляра объекта перепроверяются в случае, | ||
- | |||
- | Когда несколько активностей соревнуются за одну и ту же блокировку, | ||
- | |||
- | Приложение B.6 демонстрирует синхронизацию внутри разделяемого буфера. | ||
- | |||
- | Замечание: | ||
- | |||
- | ===== 4 Прочие расширения языка ===== | ||
- | |||
- | В данном разделе описываются несколько важных изменений, | ||
- | |||
- | ==== 4.1 Последовательность определений и опережающие ссылки ==== | ||
- | |||
- | |||
- | В Active Oberon облась видимости описания символа распространяется на весь блок, содержащий его. Это означает, | ||
- | |||
- | ==== 4.2 HUGEINT ==== | ||
- | |||
- | В язык был добавлен 64 битный знаковый целый тип HUGEINT. Он вписывается в иерархию числовых типов следующим образом: | ||
- | |||
- | LONGREAL ⊇ REAL ⊇ HUGEINT ⊇ LONGINT ⊇ INTEGER ⊇ SHORTINT | ||
- | |||
- | Имя Тип аргумента Тип результата | ||
- | |||
- | Функция | ||
- | |||
- | SHORT(x) HUGEINT LONGINT | ||
- | |||
- | идентичность (возможно усечение) | ||
- | |||
- | LONG(x) LONGINT HUGEINT | ||
- | |||
- | идентичность | ||
- | |||
- | ENTIERH(x) вещественный HUGEINT | ||
- | |||
- | наибольшее целое, не превышающее x | ||
- | |||
- | Таблица 1: Новые процедуры изменения типа | ||
- | |||
- | Таблица 1 показывает новые процедуры для изменения типа. Никаких новых правил описания констант не вводится; | ||
- | |||
- | |||
- | Имя Функция | ||
- | |||
- | PUT8(adr: LONGINT; x: SHORTINT) Mem[adr] := x | ||
- | PUT16(adr: LONGINT; x: INTEGER) | ||
- | PUT32(adr: LONGINT; x: LONGINT) | ||
- | PUT64(adr: LONGINT; x: HUGEINT) | ||
- | |||
- | GET8(adr: LONGINT): SHORTINT RETURN Mem[adr] | ||
- | GET16(adr: LONGINT): INTEGER | ||
- | GET32(adr: LONGINT): LONGINT | ||
- | GET64(adr: LONGINT): HUGEINT | ||
- | |||
- | PORTIN(port: | ||
- | PORTOUT(port: | ||
- | |||
- | CLI отключить прерывания | ||
- | STI включить прерывания | ||
- | |||
- | PUTREG/ | ||
- | EAX, EBX, ECX, EDX, ESI, EDI, ESP, EBP 32-битовые регистры | ||
- | AX, BX, CX, DX, SI, DI 16-битовые регистры | ||
- | AL, AH, BL, BH, CL, CH, DL, DH 8-регистры | ||
- | |||
- | |||
- | Таблица 2: Новое в модуле SYSTEM для IA32 | ||
- | |||
- | ==== 4.3 Нетрассируемые указатели (untraced pointers) ==== | ||
- | |||
- | Нетрассируемые указатели --- это указатели, | ||
- | |||
- | Нетрассируемые указатели определяются при помощи модификатора UNTRACED. | ||
- | TYPE Untraced = POINTER {UNTRACED} TO T; | ||
- | |||
- | ==== 4.4 Новое для IA32 ==== | ||
- | |||
- | |||
- | Функции из таблицы 2 были добавлены в компилятор для платформы Intel IA32. | ||
- | |||
- | PUTx и GETx были добавлены ради безопасности, | ||
- | |||
- | ==== 4.5 Прочее ==== | ||
- | |||
- | Некоторые расширения из Oberon-2 были адаптированы для Active Oberon: | ||
- | |||
- | ASSERT | ||
- | FOR | ||
- | экспорт только для чтения | ||
- | динамические массивы | ||
- | |||
- | Переменные указатели автоматически инициализируются значением NIL. | ||
- | |||
- | |||
- | ===== Список литературы ===== | ||
- | |||
- | [1] A. Beugnard, J.-M. Jґezґequel, | ||
- | |||
- | [2] R. Brega. Real-time kernel for the Power-PC architecture. Master’s thesis, Institut fЁur Robotik, ETH ZЁurich, 1995. | ||
- | |||
- | [3] P. Brinch Hansen. Structured multiprogramming. Communications of the ACM, 15(7): | ||
- | |||
- | [4] | ||
- | |||
- | [5] | ||
- | |||
- | [6] H. Eberle. Development and Analysis of a Workstation Computer. Dissertation 8431, ETH ZЁurich, 1987. | ||
- | |||
- | [7] P. FrЁohlich. Projekt Froderon: Zur weiteren Entwicklung der Programmiersprache Oberon-2. Master’s thesis, Fachhochschule MЁunchen, 1997. | ||
- | |||
- | [8] J. Gosling, B. Joy, and G. Steele. The Java Language Specification. The Java Series. Addison-Wesley, | ||
- | |||
- | [9] R. Griesemer. A Programming Language for Vector Computers. Dissertation 10277, ETH ZЁurich, 1993. | ||
- | |||
- | [10] J. Gutknecht. Do the fish really need remote control? A proposal for selfactive objects in Oberon. In Proc. of Joint Modular Languages Conference (JMLC). LNCS 1024, Linz, Austria, March 1997. Springer Verlag. | ||
- | |||
- | [11] J. Gutknecht and N. Wirth. Project Oberon - The Design of an Operating System and Compiler. Addison-Wesley, | ||
- | |||
- | [12] B. Heeb and C. Pfister. Chameleon: A workstation of a different colour. In Field-Programmable Gate Arrays: Architectures and Tools for Rapid Prototyping. Second International Workshop on Field Programmable Logic and Applications, | ||
- | |||
- | [13] C. A. R. Hoare. Monitors: An operating system structuring concept. Communications of the ACM, 17(10): | ||
- | |||
- | [14] | ||
- | |||
- | [15] P. Januschke. Oberon-XSC - Eine Programmiersprache und Arithmetikbibliothek fЁur das Wissenschaftliche Rechnen. PhD thesis, UniversitЁat Karlsruhe, 1998. | ||
- | |||
- | [16] K. Jensen and N. Wirth. PASCAL - User Manual and Report, volume 18 of Lecture Notes in Computer Science. Springer, 1974. | ||
- | |||
- | [17] S. E. Knudsen. Medos-2: A Modula-2 oriented operating system for the personal computer Lilith. Diss no. 7346, ETH ZЁurich, 1983. | ||
- | |||
- | [18] B. Meyer. Object-Oriented Software Construction. Prentice Hall, 2nd edition, 1997. | ||
- | |||
- | [19] H. MЁossenbЁock, | ||
- | |||
- | [20] H. MЁossenbЁock and N. Wirth. The programming language Oberon-2. Structured Programming, | ||
- | |||
- | [21] P.J. Muller. The Active Object System – Design and Multiprocessor Implementation. PhD thesis, ETH ZЁurich, 2002. | ||
- | |||
- | [22] R. Ohran. Lilith: A Workstation Computer for Modula-2. Dissertation 7646, ETH ZЁurich, 1984. | ||
- | |||
- | [23] A. Radenski. Introducing objects and concurrency to an imperative programming language. Information Sciences, an International Journal, 87(1- 3): | ||
- | |||
- | [24] A. Radenski. Module embedding. Software - Concepts and Tools, 19(3): | ||
- | |||
- | [25] B. A. Sanders and S. Lalis. Adding concurrency to the Oberon system. In Proceedings of Programming Languages and System Architectures, | ||
- | |||
- | [26] C. Szyperski. Import is not inheritance – why we need both: modules and classes. In O. Lehrmann Madsen, editor, Proceedings, | ||
- | |||
- | [27] | ||
- | |||
- | [28] N. Wirth. MODULA : A language for modular multiprogramming. Software Practice and Experience, 7:3–35, 1977. | ||
- | |||
- | [29] N. Wirth. The programming language Oberon. Software Practice and Experience, 18(7): | ||
- | |||
- | [30] N. Wirth and M. Reiser. Programming in Oberon - Steps Beyond Pascal and Modula. Addison-Wesley, | ||
- | |||
- | |||
- | ===== A Синтаксис Active Oberon ===== | ||
- | |||
- | |||
- | < | ||
- | Module | ||
- | ImportList = IMPORT ident [‘:=’ ident] {‘,’ ident [‘:=’ ident ]} ‘; | ||
- | Definition = DEFINITION ident [REFINES Qualident] {PROCEDURE ident [FormalPars] ‘;’} END ident. | ||
- | DeclSeq | ||
- | ConstDecl | ||
- | TypeDecl | ||
- | VarDecl | ||
- | ProcDecl | ||
- | ProcHead | ||
- | SysFlag | ||
- | FormalPars = ‘(’ [FPSection {‘;’ FPSection}] ‘)’ [‘:’ Qualident]. | ||
- | FPSection | ||
- | Type = Qualident | ||
- | | ARRAY [SysFlag] [ConstExpr {‘,’ ConstExpr}] OF Type | ||
- | | RECORD [SysFlag] [‘(’ Qualident ‘)’] [FieldList] END | ||
- | | POINTER [SysFlag] TO Type | ||
- | | OBJECT [[SysFlag] [‘(’ Qualident ‘)’] [IMPLEMENTS Qualident] {DeclSec} Body] | ||
- | | PROCEDURE [SysFlag] [FormalPars]. | ||
- | FieldDecl | ||
- | FieldList | ||
- | Body = StatBlock | END. | ||
- | StatBlock | ||
- | StatSeq | ||
- | Statement | ||
- | | Designator [‘(’ ExprList‘)’] | ||
- | | IF Expr THEN StatSeq {ELSIF Expr THEN StatSeq}[ELSE StatSeq] END | ||
- | | CASE Expr DO Case {‘|’ Case} [ELSE StatSeq] END | ||
- | | WHILE Expr DO StatSeq END | ||
- | | REPEAT StatSeq UNTIL Expr | ||
- | | FOR ident ‘:=’ Expr TO Expr [BY ConstExpr] DO StatSeq END | ||
- | | LOOP StatSeq END | ||
- | | WITH Qualident ‘:’ Qualident DO StatSeq END | ||
- | | EXIT | ||
- | | RETURN [Expr] | ||
- | | AWAIT ‘(’ Expr ‘)’ | ||
- | | StatBlock | ||
- | | ||
- | Case = [CaseLabels { ‘,’ CaseLabels } ‘:’ StatSeq]. | ||
- | CaseLabels = ConstExpr [‘..’ ConstExpr]. | ||
- | ConstExpr | ||
- | Expr = SimpleExpr [Relation SimpleExpr]. | ||
- | SimpleExpr = Term {MulOp Term}. | ||
- | Term = [‘+‘|’-’] Factor {AddOp Factor}. | ||
- | Factor | ||
- | | NIL | Set | ‘(’Expr‘)‘|’ ’Factor. | ||
- | Set = ‘{’ [Element {‘,’ Element}] ‘}’. | ||
- | Element | ||
- | Relation | ||
- | MulOp = ‘*’ | DIV | MOD | ‘/’ | ‘&’ . | ||
- | AddOp = ‘+’ | ‘-’ | OR . | ||
- | Designator = Qualident { ‘.’ ident | ‘[’ExprList‘]’ | ‘^’ | ||
- | | ‘(’ Qualident ‘)’ }. | ||
- | ExprList | ||
- | IdentList | ||
- | Qualident | ||
- | IdentDef | ||
- | </ | ||
- | |||
- | |||
- | |||
- | ===== B Примеры синхронизации ===== | ||
- | |||
- | |||
- | ==== B.1 Читатели и писатели ==== | ||
- | |||
- | < | ||
- | MODULE ReaderWriter; | ||
- | |||
- | TYPE | ||
- | RW = OBJECT | ||
- | (* n = 0, пусто *) | ||
- | (* n < 0, n писателей *) | ||
- | (* n > 0, n читателей *) | ||
- | VAR n: LONGINT; | ||
- | |||
- | PROCEDURE EnterReader*; | ||
- | BEGIN {EXCLUSIVE} | ||
- | AWAIT(n >= 0); INC(n) | ||
- | END EnterReader; | ||
- | |||
- | PROCEDURE ExitReader*; | ||
- | BEGIN {EXCLUSIVE} | ||
- | DEC(n) | ||
- | END ExitReader; | ||
- | |||
- | PROCEDURE EnterWriter*; | ||
- | BEGIN {EXCLUSIVE} | ||
- | AWAIT(n = 0); DEC(n) | ||
- | END EnterWriter; | ||
- | |||
- | PROCEDURE ExitWriter*; | ||
- | BEGIN {EXCLUSIVE} | ||
- | INC(n) | ||
- | END ExitWriter; | ||
- | |||
- | PROCEDURE & Init; | ||
- | BEGIN n := 0 | ||
- | END Init; | ||
- | |||
- | END RW; | ||
- | |||
- | END ReaderWriter.</ | ||
- | |||
- | Образец Читатели --- Писатели регулирует доступ к данным в критической секции. Либо один Писатель (активность, | ||
- | |||
- | ==== B.2 Сигналы ==== | ||
- | |||
- | < | ||
- | TYPE | ||
- | Signal* = OBJECT | ||
- | VAR | ||
- | in: LONGINT; (* следующий билет для выдачи *) | ||
- | out: LONGINT; (* следующий билет для обслуживания *) | ||
- | |||
- | (* элементы с (out <= ticket < in) должны ждать *) | ||
- | PROCEDURE Wait*; | ||
- | VAR ticket: LONGINT; | ||
- | BEGIN {EXCLUSIVE} | ||
- | ticket := in; INC(in); AWAIT(ticket - out < 0) | ||
- | END Wait; | ||
- | |||
- | PROCEDURE Notify*; | ||
- | BEGIN {EXCLUSIVE} | ||
- | IF out # in THEN INC(out) END | ||
- | END Notify; | ||
- | |||
- | PROCEDURE NotifyAll*; | ||
- | BEGIN {EXCLUSIVE} | ||
- | out := in | ||
- | END NotifyAll; | ||
- | |||
- | PROCEDURE & Init; | ||
- | BEGIN in := 0; out := 0 | ||
- | END Init; | ||
- | END Signal; | ||
- | </ | ||
- | |||
- | Signal реализует примитивы для работы с сигналами Active Oberon подобно тому, как это сделано в Java и Modula-2. Он использует слегка измененный ticket-algorithm. Как в некоторых магазинах, | ||
- | |||
- | ==== B.3 Повторно входимые блокировки ==== | ||
- | |||
- | < | ||
- | ReentrantLock* = OBJECT | ||
- | VAR | ||
- | lockedBy: PTR; | ||
- | depth: LONGINT; | ||
- | |||
- | PROCEDURE Lock*; | ||
- | VAR me: PTR; | ||
- | BEGIN {EXCLUSIVE} | ||
- | me := AosActive.CurrentThread(); | ||
- | AWAIT((lockedBy = NIL) OR (lockedBy = me)); | ||
- | lockedBy := me; | ||
- | INC(depth) | ||
- | END Lock; | ||
- | |||
- | PROCEDURE Unlock*; | ||
- | BEGIN {EXCLUSIVE} | ||
- | DEC(depth); | ||
- | IF depth = 0 THEN lockedBy := NIL END | ||
- | END Unlock; | ||
- | END ReentrantLock; | ||
- | </ | ||
- | |||
- | ReentrantLock позволяет блокировать объект его хозяином более одного раза. Клиенты этого объекта должны явно использовать Lock и Unlock вместо пометки защищаемого участка оператором EXCLUSIVE. | ||
- | |||
- | ==== B.4 Бинарный и общий семафоры ==== | ||
- | |||
- | < | ||
- | MODULE Semaphores; | ||
- | |||
- | TYPE | ||
- | Sem* = OBJECT (* Бинарный семафор *) | ||
- | VAR taken: BOOLEAN | ||
- | |||
- | PROCEDURE P*; (* войти *) | ||
- | BEGIN {EXCLUSIVE} | ||
- | AWAIT(~taken); | ||
- | END P; | ||
- | |||
- | PROCEDURE V*; (* войти *) | ||
- | BEGIN {EXCLUSIVE} | ||
- | taken := FALSE | ||
- | END V; | ||
- | |||
- | PROCEDURE & Init; | ||
- | BEGIN taken := FALSE | ||
- | END Init; | ||
- | END Sem; | ||
- | |||
- | GSem* = OBJECT (* Общий семафор *) | ||
- | VAR slots: LONGINT; | ||
- | |||
- | PROCEDURE P*; | ||
- | BEGIN {EXCLUSIVE} | ||
- | AWAIT(slots > 0); DEC(slots) | ||
- | END P; | ||
- | |||
- | PROCEDURE V*; | ||
- | BEGIN {EXCLUSIVE} | ||
- | INC(slots) | ||
- | END V; | ||
- | |||
- | PROCEDURE & Init(n: LONGINT); | ||
- | BEGIN slots := n | ||
- | END Init; | ||
- | END GSem; | ||
- | END Semaphores. | ||
- | </ | ||
- | |||
- | Это хорошо известные синхронизирующие примитивы Дейкстры [5]. Заметим, | ||
- | |||
- | ==== B.5 Барьеры ==== | ||
- | |||
- | < | ||
- | MODULE Barriers; | ||
- | (* | ||
- | Барьер используется для синхронизации N активностей. | ||
- | *) | ||
- | TYPE | ||
- | Barrier = OBJECT | ||
- | VAR in, out, N: LONGINT; | ||
- | |||
- | PROCEDURE Enter*; | ||
- | VAR i: LONGINT; | ||
- | BEGIN {EXCLUSIVE} | ||
- | INC(in); | ||
- | AWAIT (in >= N); | ||
- | INC(out); | ||
- | IF (out = N) THEN in := 0; out := 0 END; | ||
- | END Enter; | ||
- | |||
- | PROCEDURE & Init (nofProcs: LONGINT); | ||
- | BEGIN | ||
- | N := nofProcs; in := 0; out := 0; | ||
- | END Init; | ||
- | END Barrier; | ||
- | END Barriers. | ||
- | </ | ||
- | |||
- | Барьер используется для синхронизации активностей друг с другом. Если активности определены как | ||
- | P = Phase ;P hase ;...P hase i i,0 i,1 i,n | ||
- | |||
- | то барьер используется для гарантии того, что все активности выполнят Phasei,j до начала Phasei,j+1. Отдельный поток исполнения будет выглядеть подобно следующему: | ||
- | < | ||
- | FOR j := 0 TO N DO | ||
- | Phase(i, j); barrier.Enter | ||
- | END; | ||
- | </ | ||
- | |||
- | Барьер сбрасывает счетчик in после выполнения условия чтобы избежать переполнения. Это возможно потому, | ||
- | |||
- | ==== B.6 Ограниченный буфер ==== | ||
- | |||
- | < | ||
- | MODULE Buffers; | ||
- | |||
- | CONST | ||
- | BufLen = 256; | ||
- | |||
- | TYPE | ||
- | (* Buffer - FIFO буфер *) | ||
- | Buffer* = OBJECT | ||
- | VAR | ||
- | data: ARRAY BufLen OF INTEGER; | ||
- | in, out: LONGINT; | ||
- | |||
- | (* Put - вставить элемент в буфер *) | ||
- | PROCEDURE Put* (i: INTEGER); | ||
- | BEGIN {EXCLUSIVE} | ||
- | AWAIT ((in + 1) MOD BufLen # out); (*AWAIT ~полный *) | ||
- | data[in] := i; | ||
- | in := (in + 1) MOD BufLen | ||
- | END Put; | ||
- | |||
- | (* Get - забрать элемент из буфера *) | ||
- | PROCEDURE Get* (VAR i: INTEGER); | ||
- | BEGIN {EXCLUSIVE} | ||
- | AWAIT (in # out); (*AWAIT ~пустой *) | ||
- | i := data[out]; | ||
- | out := (out + 1) MOD BufLen | ||
- | END Get; | ||
- | |||
- | PROCEDURE & Init; | ||
- | BEGIN | ||
- | in := 0; out := 0; | ||
- | END Init; | ||
- | |||
- | END Buffer; | ||
- | |||
- | END Buffers. | ||
- | </ | ||
- | |||
- | Buffer реализует ограниченный кольцевой буфер. Методы Put и Get защищены от одновременного доступа; | ||
- | |||
- | ===== C Примеры активных объектов ===== | ||
- | |||
- | |||
- | ==== C.1 Обедающие философы ==== | ||
- | |||
- | < | ||
- | MODULE Philo; | ||
- | |||
- | IMPORT Semaphores; | ||
- | |||
- | CONST | ||
- | NofPhilo = 5; (* количество философов *) | ||
- | |||
- | VAR | ||
- | fork: ARRAY NofPhilo OF Semaphores.Sem; | ||
- | i: LONGINT; | ||
- | |||
- | TYPE | ||
- | Philosopher = OBJECT | ||
- | VAR | ||
- | first, second: LONGINT; | ||
- | |||
- | (* вилки для философов *) | ||
- | PROCEDURE & Init(id: LONGINT); | ||
- | BEGIN | ||
- | IF id # NofPhilo-1 THEN | ||
- | first := id; second := (id+1) | ||
- | ELSE | ||
- | first := 0; second := NofPhilo-1 | ||
- | END | ||
- | END Init; | ||
- | |||
- | BEGIN {ACTIVE} | ||
- | LOOP | ||
- | .... Думает.... | ||
- | fork[first].P; | ||
- | .... Ест .... | ||
- | fork[first.V; | ||
- | END | ||
- | END Philosopher; | ||
- | |||
- | VAR | ||
- | philo: ARRAY NofPhilo OF Philosopher; | ||
- | BEGIN | ||
- | FOR i := 0 TO NofPhilo DO | ||
- | NEW(fork[i]); | ||
- | NEW(philo[i]); | ||
- | END; | ||
- | END Philo.</ | ||
- | |||
- | ==== C.2 Решето Эратосфена ==== | ||
- | |||
- | < | ||
- | MODULE Eratosthenes; | ||
- | |||
- | IMPORT Out, Buffers; | ||
- | |||
- | CONST | ||
- | N = 2000; | ||
- | Terminate = -1; (* охранник *) | ||
- | |||
- | TYPE | ||
- | Sieve = OBJECT (Buffers.Buffer) | ||
- | VAR prime, n: INTEGER; next: Sieve; | ||
- | |||
- | PROCEDURE & Init; | ||
- | BEGIN | ||
- | Init^; (* вызывает инициализатор Buffer (суперклас) *) | ||
- | prime := 0; next := NIL | ||
- | END Init; | ||
- | |||
- | BEGIN {ACTIVE} | ||
- | LOOP | ||
- | Get(n); | ||
- | |||
- | IF n = Terminate THEN | ||
- | (* прервать выполнение *) | ||
- | IF next # NIL THEN next.Put (n) END; | ||
- | EXIT | ||
- | ELSIF prime = 0 THEN | ||
- | (* первое число всегда простое *) | ||
- | Out.Int(n, 0); Out.String(" | ||
- | prime := n; | ||
- | NEW (next) | ||
- | ELSIF (n MOD prime) # 0 THEN | ||
- | (* передать дальше, | ||
- | | ||
- | END | ||
- | END | ||
- | END Sieve; | ||
- | |||
- | PROCEDURE Start*; | ||
- | VAR s: Sieve; i: INTEGER; | ||
- | BEGIN | ||
- | NEW(s); | ||
- | FOR i := 2 TO N-1 DO s.Put (i) END; | ||
- | s.Put(Terminate) (* использовать охранника для индикации выполнения *) | ||
- | END Start; | ||
- | |||
- | END Eratosthenes.</ | ||
- | |||
- | Eratosthenes использует отсеивающий алгоритм для поиска простых чисел. Каждое решето --- это активный объект, |