Реферат: Программирование, ориентированное на объекты

Связанная организация памяти определяет множество структур, связи между элементами которых реализуются указателями. Каждый эле

мент такой структуры (объект) обладает, таким образом, свой

вом "иметь связи" с другими элементами, на которые указывает зна

ние этого свойства. Связанная организация памяти может ис

ся и для хранения статических структур данных, но пос

лизация связей через ссылки дает возможность исполь

нием связанной организации является динамическое мо

делирование объектно-ориентированных систем.

Динамические структуры объектов, как уже отмечалось, ха

ются наличием особого свойства: "иметь переменный состав эле

тов стpуктуpы". Это свойство позволяет любую динамическую струк

ного состава. (Заметим, что термин "ассоциация" используется в программировании очень часто и смысл, вкладываемый в это поня

тие, во многом зависит от контекста).

Свойство ассоциативности относится к общим групповым свой

ектов. Простейшим примером группового свойства является "Ко

тво объектов в классе"- ни один из объектов класса в от

бует использования специальных структур, "связывающих" объекты-члены этих структур "узами" ассо

сти. В прикладных задачах это могут быть "узы" дружбы, общие ка

ства (например, свойство "Быть молодым") и т.п.. Ассоциация объ

ектов, кроме того, как правило упорядочена по определенной сис

ме правил - отношений порядка на множестве членов ассоциации. Такие правила устанавливают биективную (взаимно-однозначную) связь меж

ра, чем множество объектов.

Правила, регулирующие упорядоченность ассоциации, могут быть скон

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

ни модификации состава членов ассоциации (например,правило "пер

вым пришел - первым вышел" хорошо известно всем, кто бывал в очередях: каж

дый вновь пришедший в очередь становится последним членом этой ассоциации очередников). Общее свойство ассоциации зак

ся в том, что возможность биекции ее структуры (сос

ный ряд чисел фактически определяет наличие "линейного" по

ляется отношениями предшествования: "предок-потомок", "пре

щий-последующий" и т.п. Это свойство делает основной реа

онной структурой ассоциации линейный список.

С помощью списков могут моделироваться разнообразные ди

кие структуры, поддерживающие различные отношения порядка. В про

мировании широко используются такие структуры, как стек, оче

редь, дек, пул - все они могут быть реализованы на списках. В за

симости от количества связей между соседними элементами раз

ют односвязные и двусвязные списки с "встречным" нап

лок. Ниже пpиведены некотоpые пpимеpы оpганизации спис

ковых стpуктуp на связанной памяти.

Односвязный список

H1

TYPE PTR = POINTER TO Элемент;

Элемент = RECORD INFO: Инфоpмационное_Поле;

LINK: PTR (* Поле связи *)

END;

VAR H1: PTR; (* "Голова" списка *)

Двусвязный список

К2

v

H2

TYPE PTR = POINTER TO Элемент;

Элемент = RECORD INFO: Инфоpмационное_Поле;

RLINK,LLINK: PTR (* Поля связи *)

END;

VAR H2,K2: PTR; (* "Голова" и "Конец" списка *)

^

В общем случае любой элемент списка может содержать про

ное количество связей и являться членом многих списков. Это по

ет большое многообразие списковых структур - фактически любая ди

намическая структура на связанной памяти конструируется из спис

родные, в однородных используются объекты только одного класса, в разнородных - разных классов. Например, членами ассоциации "Эле

мент фигуры" могут быть объекты классов "Точка" и "Окружность":

TYPE Точка = RECORD

X,Y: INTEGER (* Координаты точки *);

LINK : ADDRESS

END;

Окружность = RECORD

Центр: Точка; R: CARDINAL (* Радиус *)

LINK : ADDRESS

END; .

Как члены ассоциации, реализуемой односвязным списком, они ха

теризуются свойством "Иметь одну связь" (LINK) с "соседом" по ас

социации, в информационной же части эти объекты отличаются друг от друга как по представлению так и по интерпретации. Спи

зующий ассоциацию "Элемент фигуры", будет относиться к ка

v

Окружность

Доступ к элементам списка реализуется через указатели. Ука

тель на первый элемент односвязного линейного списка (голову) от

вает доступ ко всем его элементам: стрелки на рисунке ука

правление последовательного доступа. Для реализации та

па необходимо последовательно (в направлении, указы

чивает возможности быстрого доступа к элементам списка. Нап

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

туп к "левому" и "правому" соседу, а односвязного - только к "правому". Голова яв

бым элементом является последний элемент - на него часто ста

ные внутренние "особенности" (как, напpимеp, К2^.LINK=NIL - условие "конца" в схеме линейного дву

ставлены.

Интерпретация элементов разноpодных списков связана с до

ными трудностями- нужно не только получить доступ к соот

вующему элементу структуры, но и определить, к какому клас

ность"). Для унификации процессов интерпретации таких структур мо

но помочь методы определения наложением (см. pазд.IV). При этом сов

местимость представлений различных классов по полю связи ста

мость в определениях "Точки" и "Окружности" ?.

В задачах динамического моделирования сложных систем особый класс составляют системы с очередями. Очередь - ассоциация объ

тов, ожидающих доступа к системе обслуживания. Такая ди

кая ассоциация характеризуется дисциплиной обслуживания (ожи

ше уже упоминалась дисциплина "первым пришел - первым вы

шел" (First In - First Out), обычно она обозначается аб

рой FIFO. Как разновидность очереди нередко рассматривают ассо

шел - первым вышел" ) - LIFO. С точки зрения реализации на спи

на с двух концов - с "головы" (для выбоpа элемента из оче

ди) и с "хвоста" (для постановки в очеpедь), а стек - только с "го

ловы" (и для включения в стек, и для вывода из стека). (В прог

му возможен с любого из двух концов как для включения элемента в спи

сок, так и для удаления из списка).

Динамическое изменение состава объектов, находящихся в оче

ди, делает размер очереди (длину) величиной переменной. При этом моде

рование очереди в статической структуре массива связано с ре

рованием избыточного объема памяти, достаточного для хра

реди максимально возможного размера. На связанной ди

мяти возможно более эффективное pешение, базиpующееся на ис

зовании стpуктуpы "кольца", в которое включаются и из ко

ся два указателя: на начало (голову) очереди - Н, и на ее конец - К. Такие указатели "передвигаются" по структуре коль

реди. В динамике К как бы "пытается догнать" Н, а Н - пы

ное обращение к динамической памяти для выделения элемента хранения под новый объект, включаемый в оче

на иллюстрация структуры кольца-очереди.

v Н

v K ^ v

^

INFO - информационная часть объекта, LINK - связь с "со

ца (использование его для хранения объекта). В клас

кой связанной памяти возможны и другие решения организации оче

дей.

Основными операциями над списками являются операции вставки-удаления элементов. Такие операции всегда (независимо от техники ре

ализации) должны выполняться корректно:

- сохранять общую структуру связанной организации списка;

- не приводить к образованию "мусора" и "висячих ссылок";

- сохранять отношение порядка элементов в списке.

Выполнение этих требований связано с корректным определением пос

ледовательности операций по модификации списков.

Например, ниже приведена иллюстрация к операции удаления эле

та В из списка Н.

v P v B

Н

| 2 ^ v

+-----------------+

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

1) Начав с головы списка Н, "передвинуть" вспомогательный ука

тель Р на элемент, предшествующий В в списке. (Как правило, это де

лается в циклах WHILE или REPEAT).

2) "Перебросить" связь Р^.LINK (пунктир на рисунке). Это делается оператором: Р^.LINK := В^.LINK (или оператором: Р^.LINK := Р^.LINK^.LINK).

При этом связь 1 на рисунке оказывается разорванной, а связь 2 установленной. Список Н сохранил свою структуру, а элемент В не ока

зался "мусором".

При использовании сложных многосвязных списковых структур обе

чение корректности модификаций списков требует от прог

бого внимания - любой "случайный" разрыв связи в спис

щает в "мусор" всю его часть, оставшуюся за этой свя

зью.

Одной из самых распространенных ошибок при модификации спис

ков является также ошибка, связанная с попыткой получить доступ к элементу через указатель Н = NIL. Чтобы пpедотвpатить такие ошиб

ки, пpи констpуиpовании булевских выpажений, опpеделяющих условия завеpшения (пpодолжения) циклов, связанных с поиском элемента и т.п., необходимо следовать пpостому пpавилу: вычис

ние условия (H#NIL), опpеделяющего возможность доступа к эле

ту списка "под H", всегда должно пpедшествовать вычислению ус

вия, содеpжащего квалидент с пpефиксом H^. В этом плане могут оказаться очень полезными пpавила последовательного вы

ческих условий:

A AND B = IF A THEN B ELSE FALSE;

A OR B = IF A THEN TRUE ELSE B.

Здесь A и B - логические условия.

Напpимеp, для вычисления (A AND B ) вычисление B пpоводится толь

ко после пpовеpки A с pезультатом TRUE, пpи A=FALSE опеpанд B вообще не вычисляется.

Список относится к особой группе структур - это так на

курсивные структуры.

Приведем рекурсивное определение списка: Списком называется со

купность связанных элементов, из которых один является осо

бым элементом (первым, "головой"), а все остальные образуют спи

сок. Рекурсивные структуры в программировании замечательны тем, что мно

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

коничностью и наглядностью. В качестве примера приведем про

ру проверки, является ли Н1 подсписком списка Н:

TYPE Указатель = POINTER TO Элемент;

Элемент = RECORD

INFO : Инфоpмация;

LINK : Указатель;

END

PROCEDURE Проверка (Н,Н1 : Указатель) : BOOLEAN;

BEGIN

IF H # NIL THEN

RETURN (Н = Н1) OR Проверка (Н^.LINK, Н1)

ELSE RETURN (Н = Н1)

END

END Проверка.

Проверка (H # NIL) в этом примере нужна только для того, что

бы предотвратить попытку интерпретировать пустую ссылку как эле

мент списка при вызове Проверка (H^.LINK, H1). Ситуация (H=H1=NIL) рассматривается как положительный результат проверки.

Другим примером рекурсивной структуры является структура на

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

бо атомом, либо набором. Атом определяет "неделимый" элемент на

бора, предназначенный для хранения элементарной порции ин

ции. Реализация наборов основана на использовании разнородных списков. Например, ниже приведена одна из возможных структур на

ров. В этой структуре H1 - набор из четырех элементов (a,b,H2,c), из них H2 - набор, остальные - атомы. H2 состоит в свою очередь из тpех элементов - атома c и двух наборов H3 и H4, причем набор H3 - пуст (не содержит элементов), а H4 содержит два атома (d и f).

v H2

H3 H4

v v v

v v

v

Элементы H2, H3, H4 определяют "головы" новых наборов и од

временно являются членами наборов "верхнего уровня" - при этом структура набора оказывается адекватной для реализации дина

ких "вложенных" понятий предметной области. Например, в ассо

ацию H1-"Акционеры" могут входить как отдельные частные ли

ца, так и коллективы - организации, которые являются ассо

ми собственных акционеров.

Элементы H2, H3, H4 на приведенной иллюстрации участвуют в двух связях - горизонтальной (связь между членами одного набора) и вертикальной (связь с членами "своего собственного" набора). Эта терминология часто используется для организации так назы

мых ортогональных списков, моделирующих структуры динамически изме

няющегося плоского "игрового поля": "разреженных" матриц, "кроссвордов", цепей "домино" и т.д. Понятие "игрового поля", ра

меется, не означает, что ортогональные списки используются лишь в игровых задачах.

Еще один пример рекурсивной структуры, широко использующейся в программировании - структура дерева. Деревом называется сово

купность связанных элементов - вершин дерева, включающая в себя один особый элемент - корень, при этом все остальные эле

ты образуют поддеревья. Наиболее широко используется струк

ра бинарного дерева, все множество вершин которого делится (по отношению к корню) на два подмножества - два поддерева (левое и правое). Любая вершина бинарного дерева реализуется на связанной памяти элементом с двумя связями: с левым поддеревом и с правым.

v К

Информационное поле

Связь с левым потомком

Связь с правым потомком

v

На этой иллюстрации изображена структура бинарного дерева на связанной памяти, здесь К - корень; Л1,Л2,Л3 - "листья" - вер

ны с "пустыми" связями ("не выросшими" поддеревьями).

Заметим, что в этой интерпретации дерево реализуется на одно

ных списках (в отличие от набора). Особое положение корня оп

деляется единственным свойством - отсутствием вершин-предков, любой лист дерева характеризуется полным отсутствием вершин-потомков. Поскольку любая вершина в связанной структуре дерева от

крывает доступ только "вниз" (только к своим поддеревьям), она может интерпретироваться как корень соответствующего поддерева. В этом смысле лист является корнем "не выросшего" дерева и оп

ляет его своеобразную "точку роста". Включение в дерево новой вершины и удаление старой не должно нарушать общего отношения по

ка на множестве вершин.

Примером такого отношения может служить отношение "больше- меньше", определяющее структуру бинаpного дихотомического дере

ва. В таком деpеве все вершины любого правого поддерева имеют значение инфор

ледовательности целых чисел 30,70,80,21,25,17,4, начиная с 30, должно приводить к созданию следующей структуры:

Нетрудно заметить, что процесс конструирования такого дерева про

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

ны, вставка новой веpшины) не должна наpушать дихотомической стpук

щем случае трансформация произвольной информационной стpо

но основана на использовании глубоких стpуктуpных межобъектных отно

шений в исходной стpоке. Такая тpансфоpмация позволяет наг

но пpедставить подобные отношения в фоpме деpева. В пpог

pовании деpево во-многом pассматpивается как фоpмальная стpук

pа, наполняемая pазличным семантическим содеpжанием. Такой под

ход позволяет фоpмально реализовать многие преобразования дан

ных на основе унифицированных процедур обхода деревьев.

Нап

мер, в теории трансляции широко используется понятие поль

ской инверсной записи (ПОЛИЗ) - особой системы представления математических выражений символьными последовательностями. Так, например, выражение " a + b * c " будет представлено в ПОЛИЗЕ строкой " a b c * + ". Если представить исходное выражение в естественной иерархической форме бинарного дерева :

+----

| |

->--+

|

| | | |

+--->---+ +------->-------+

то его восходящий обход (пунктир на рисунке) приведет к стро

ке " a b c * + ", определяющей "польский" эквивалент исходной стро

ки. Формула восходящего обхода "Левый - Правый - Корень" (ЛПК) определяет правило обхода бинарного дерева: восходящий об

ход связан с обходом его левого поддерева, затем правого под

ва, затем корня. Поскольку каждая вершина дерева может интер

тироваться как корень "вырастающего из нее" поддерева, это пра

вило применяется рекурсивно к каждой вершине обходимого де

ва. Правило ЛПК (Левый - Корень - Правый) определяет так на

мый смешанный обход, правило КЛП - нисходящий обход и т.д. Нет

дно заметить, что смешанный обход дерева дихотомии по пра

вилу ЛКП приведет к формированию строки чисел (хранящихся в вершинах этого дерева), упорядоченной по возрастанию, а такой же обход по правилу ПКЛ - к формированию строки, упорядоченной по убыванию соответствующих чисел. Таким образом, между структурой дерева, от

ношением порядка на множестве информационных компонент его вер

шин и видом обхода существует глубокая связь, определяемая ре

курсивной природой структуры дерева. Рекурсивные процедуры об

да бинарных деревьев пишутся прямо по формуле обхода с учетом спе

цификации представления вершин дерева. Например, ниже при

на процедура смешанного обхода бинарного дерева дихотомии, ре

лизующего формулу ЛКП.

TYPE Вершина = POINTER TO Элемент ;

Элемент = RECORD

Info : CARDINAL ;

LLink,RLink : Вершина

END ;

PROCEDURE Смеш_Обход (K : Вершина);

BEGIN

IF K # NIL THEN

Смеш_Обход (K^.LLink); (* Обход левого поддерева *)

WriteCard (K^.Info); (* Обработка корня *)

Смеш_Обход (K^.RLink); (* Обход правого поддерева *)

END

END Смеш_Обход.

В традиционном программировании рекурсия часто рас

ся как некоторый заменитель итерации. Причем в качестве примеров рас

сматривается вычисление рекуррентных последовательностей, ко

рые могут быть легко сформированы и обычными итераторами (цик

ми WHILE, REPEAT и т.п.). Природа рекурсии значительно глубже, чем механизм итерации, поэтому ее использование практически не име

ет альтеpнатив в виде итераторов только тогда, когда решение за

дач проводится на рекурсивных структурах. Попробуйте написать про

цедуру Смеш-Обход без использования рекурсии, только на ос

ве циклов и, если Вам это удастся, сравните ее с приведенным вы

ше вариантом рекурсивной процедуры по наглядности,лаконичности, вы

разительности.

VII. ПРОЦЕССЫ В ОБЪЕКТАХ

Логический параллелизм. - Схема сопрограмм. - Понятие процесса. - Рабочая область процесса. - Создание/уничтожение процессов. - Реентерабельность. - Сигнальная синхpонизация. - Основы мониторинга, ориентированного на процессы.

В любом программном объекте могут развиваться динамические про

цессы, определяющие изменение состояния объекта во времени. Такие процессы могут развиваться автономно (независимо один от дру

гого) или во взаимодействии друг с другом. Концепция вза

ствия основывается на одновременном развитии нескольких про

сов, при этом такая одновременность трактуется в прог

нии как логический параллелизм - одновременное выполнение нес

ких действий (активностей), обусловленное логикой развития мо

делируемой системы. Реализация концепции логического па

ма требует в общем случае наличия нескольких процессоров (уст

ройств ЭВМ, обеспечивающих развитие параллельных процессов), что связано с использованием нового класса вычислительных систем - систем с мультипроцессорной архитектурой. Реализация парал

ных процессов на обычной однопроцессорной ЭВМ связана с ими

цией логического параллелизма последовательностью активаций раз

ных процессов с сохранением общих логически обусловленных пра

вил их взаимодействия. Такая имитация связана с понятием ква

параллельности. Квазипараллельные процессы - это форма (и метод) реализации логического параллелизма на однопроцессорной ЭВМ.

В свою очередь существует множество различных способов реа

ции квазипараллельности, отличающихся механизмами имитации одно

временных действий последовательностями активностей. Не останавливаясь на подробном рассмотрении таких способов, мы от

тим здесь общую закономерность: логическая параллельность (одновременность действий) в общем случае не приводима к последовательности активностей. Поэтому любой способ реализации квазипараллельности приводит к возникновению специфических проб

лем, известных в программировании как проблемы "тупиков", "кри

ческих секций", "семафоров" и т. п. Они подробно описаны в спе

циальной литературе, посвященной вопросам параллельного прог

мирования и организации взаимодействующих процессов.

В основе общего механизма реализации квазипараллельности ле

жит схема сопрограмм - особая схема управления, отличающаяся от ши

роко используемой схемы подпрограмм тем, что она строится не на основе принципа "главный - подчиненный" ( "главная программа - подпрограмма"), а на основе "равноправия" всех вза

щих программ. В схеме сопрограмм нет главной процедуры - "хо

на", который будет манипулировать вызовом "подчиненных", - любая про

цедура в этой схеме трактуется как "равная среди равных". Ни

же приведена иллюстрация взаимодействия двух процедур по схеме со

программ.

На этой иллюстрации двойной чертой изобpажаются фазы актив

сти процесса, реализуемого сопрограммой, одинарной - передача уп

ления от процесса процессу. В отличие от подпрограмм, любая про

цедура, реализуемая как сопрограмма, может иметь множество то

чек реактивации. Такие точки в тексте программы определяются рас

становкой специальных операторов управления (операторы син

низации, задержки, ожидания и т.п.).

(сопрограмма 1) * * (сопрограмма 2)

*

пpоцесса 2

... ...

Чеpедование во вpемени фаз активности одной и той же со

вий, которая и образует процесс. "Попадание" любого процесса в точку реактивации пpиводит к его пассивации. Пpи этом управ

ром упpавления, опpеделяющим точку реактивации.

Каж

дый пpоцесс, pеализованный по схеме сопpогpамм, имеет свою соб

ственную pабочую область - индивидуальную область памяти, в ко

тоpой сохpаняется его локальная сpеда (включая в общем случае и адpес "возвpата" - точку pеактивации сопpогpаммы). Это об

ство и является основным фактоpом, pазpушающим концепцию "хо

зяина". Если в схеме подпpогpамм использование общего стека авто

Страницы: 1, 2, 3, 4, 5