автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Управление оперативной и внешней памятью в многоязыковой объектно-ориентированной системе программирования

РГБ ОД

- 8 МАГ! 1995

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ___ПО ВЫСШЕМУ ОБРАЗОВАНИЮ__

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

. На правах рукописи

АБРАМОВ Игорь Вячеславович

УДК 681.03.06

Управление оперативной и внешней памятью в многоязыковой объектно-ориентированной системе программирования

Специальность 05.13.11 . "Математическое и программное обеспечение вычислительных машин, комплексов, Систем и сетей"

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1995

Работа выполнена в Московском автомобилестроительном институте.

Научный руководитель: Официальные оппоненты:

Ведущая организация".

кандидат физико-математических наук, доцент А.Г. Кушнцренко.

доктор фщико-иатематпческих наук, профессор Е.А Жоголев.

доктор технических наук, С.Д. Кузнецов.

Вычислительный Центр Российской Академии Наук.

Защита состоится

1994г. в .

часов на

заседании специализированного Совета К 053.18.09 в Московском авиационном институте им. Серго Орджоникидзе.

С диссертацией можно ознакомиться в библиотеке МАИ.

Адрес института: 125871, Москва, A-8Q, Волоколамское ш., 4. Автореферат разослан "_"_1994г.

Ученый секретарь Совета

кандидат физ.-мат. наук, доцент ^ ^М.В. Ротанина

1. Общая характеристика работы

Актуальность темы работы. В любой достаточно сложной программной системе выбор схемы управления динамической памятью существенно влияет как на эффективность использования ресурсов памяти и процессора, так и на сложность написания и отладки частей программы, связанных с созданием и удалением объектов. Можно выделить два основных подхода к управлению динамической памятью — явное освобождение, при котором работа по возвращению памяти, занимаемой неиспользуемыми объектами, лежит на программисте, и автоматическое освобождение, при котором неиспользуемые объекты выявляются и уничтожаются специальными алгоритмами сборки мусора. Хотя явное освобождение обычно эффективнее автоматического, оно часто противоречит принципу модульности, а также провоцирует опасные и трудно обнаруживаемые ошибки (такие как висячие ссылки и утечка памяти). Развитие программного и аппаратного обеспечения, повышающиеся требования к надежности программ, распространение языков функционального, логического и объектно-ориентированного программирования приводят к постепенному расширению сферы применения управления памятью с автоматическим освобождением.

Некоторые программные системы, такие как САПР, издательские системы, интерактивные системы программирования, предъявляют дополнительные требования к алгоритмам управления памятью. Для реализации отдельных компонент таких систем целесообразно использовать свой, наиболее подходящий, язык программирования. Обычно это затрудняет совместное использование объектов компонентами, написанными на различных языках, так как схемы управления памятью в этих языках различаются. Многие приложения требуют сохранения некоторой части информации между сеансами работы и одновременного доступа к ней нескольких пользователей. Для решения этой задачи используются СУБД, причем в последнее время все больший интерес вызывают СУБД с объектно-ориентированной моделью данных, предоставляющие значительную гибкость в обращении с данными, но существенно усложняющие задачу управления памятью в базе данных.

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

го использования несколькими системами программирования и объектно-ориентированными СУБД.

Цели и задачи. Целью этой работы является разработка и реализация системы управления памятью для объектно-ориентированной многоязычной среды программирования. К системе предъявляются следующие требования:

в Эффективная поддержка языков программирования с существенно различными моделями памяти, в том числе С, С++, Ьэри С-Та!к

® Возможность автоматического освобождения неиспользуемой памяти. Паузы в работе программы, обусловленные выполнением алгоритма сборки мусора, должны быть достаточно малы, чтобы быть незаметны пользователю интерактивного приложения.

в Управление ■ памятью в многопользовательской распределенной объектно-ориентированной базе данных.

• Система должна функционировать под управлением современных многозадачных и многопользовательских операционных систем на 32-х и 64-х разрядных рабочих станциях и мощных персональных компьютерах. Алгоритмы управления памятью в базе данных должны допускать параллельную обработку в распределенной • конфигурации.

Научная новизна.

в Разработана специализированная архитектура системы управления оперативной и внешней памятью в многоязычной объектно-ориентированной системе программирования. На основе этой архитектуры программно реализована система управления памятью в среде С~Та1к

« Предложена классификация усовершенствованных сканирующих алгоритмов сборки мусора.

• Разработан алгоритм генерационной сборки мусора, основанный на использовании информации о типизации объектов. Доказана корректность сборки мусора, задаваемой этим алгоритмом. Разработан и реализован алгоритм параллельного автоматического освобождения памяти в распределенной объектно-ориентированной базе данных.

® Предложен эвристический алгоритм определения оптимального объема занимаемой виртуальной памяти.

Практическая ценность. Разработанная система управления памятью используется в многоязычной объектно-ориентированной среде С~Тз1ки в объектно-ориентированной СУБД GOODS.

Алгоритмы, предложенные в работе, могут быть использованы и в других системах управления памятью.

Внедрение результатов работы. Среда С—Talk используется в учебном процессе МАСИ.

На основе С~Та1к разработана система автоматизации деятельности лечебного учреждения, система доведена до уровня исследовательского прототипа.

Программные средства реализованы в ОС UNIX System V и UNIX BSD на рабочей станции БЕСТА-90, в ОС Linux, BSD и SCO UNIX на 32-х разрядных микроэвм, SunOS на рабочих станциях Sparestation и OSF-1 на DEC Alpha АХР.

Апробация работы. Основные результаты работы докладывались в 1990-94 годах на семинарах МАСИ, МАИ, ВЦ РАН, механико-математического факультета и факультета вычислительной математики и кибернетики МГУ.

Публикации. По теме диссертации опубликовано 7 печатных работ.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы, содержащего 139 наименований и 3 приложений. Машинописных страниц —192, рисунков —19, таблиц — 5, объем приложеиий —32страницы.

2. Краткое содержание работы

Во ВВЕДЕНИИ обосновывается актуальность диссертационной работы, формулируются ее цели и задачи.

В ПЕРВОЙ ГЛАВЕ дан обзор основных алгоритмов сборки мусора, сформулированы требования, предъявляемые к алгоритмам автоматического освобождения памяти в интерактивных многоязычных объектно-ориентированных системах программирования и системах управления базами данных. Описана архитектура и интерфейс системы управления памятью среды С~Talk

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

и интерфейса к основным функциям операционной системы. Библиотека предназначена для взаимодействия с компонентами, написанными на различных языках программирования. Библиотека изолирует от остальных компонент среды С—7а//с значительную часть кода, зависящего от аппаратуры и операционной системы.

Система управления памятью в среде С~7а//симеет трехуровневую организацию.

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

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

Верхний уровень предоставляет дополнительные средства явного управления памятью, доступные для использования'программами, написанными на языках программирования С, С++и Pascal. К таким средствам . относятся, так называемые, динамические стеки объектов. Динамическим стеком объектов называется отдельный пул динамической памяти, все объекты в котором освобождаются сразу. При создании объектов в таком динамическом стеке выделяется текущий объект, имеются средства расширения текущего объекта. Динамические стеки являются достаточно эффективным средством явного управления памятью. Например, компиляторы характеризуются активным созданием большого количества небольших объектов (например вершин дерева вывода) и одновременным освобождением всех таких объектов (входящих в дерево).

В состав среды С—Гз1к входит объектно-ориентированная СУБД GOODS. СУБД GOODS, как и базовая библиотека, ориентирована на использование программными компонентами, написанными на различных языках программирования. Она позволяет сохранять в базе данных

объекты произвольной структуры, поддерживает распределенную обработку, архитектуру клиент-сервер с возможностью работы со многими серверами, распределенные транзакции. Клиенту предоставляется возможность выполнения методов непосредственно на сервере. Система управления внешней памятью СУБД GOODS взаимодействует с системой управления оперативной памятью среды С~7з/Аи обеспечивает средства автоматического освобождения недоступных объектов. Алгоритм сборки мусора, используемый в GOODS, выполняется в фоновом режиме, параллельно с обработкой пользовательских запросов к базе данных.

Во ВТОРОЙ ГЛАВЕ дан обзор основных алгоритмов частичной сборки мусора, приведена математическая модель таких алгоритмов. Описан алгоритм частичной сборки мусора, основанный на использовании информации о типах объектов. Причиной создания математической модели алгоритмов частичной сборки мусора является необходимость доказательства их корректности, иногда неочевидной в случае алгоритмов, комбинирующих несколько различных методов частичной сборки. Так, например, проблемы возникают при разработке генерационного алгоритма, использующего консервативную технику распознавания ссылок. Дело в том, что генерационная сборка мусора обычно описывается в терминах копирования объектов, а консервативное распознавание ссылок, в классическом своем варианте, не допускает такого копирования. В применении к генерационным алгоритмам сборки мусора математическая модель обобщает понятия младших и старших поколений объектов до отношений частичного порядка. Следует отметить, однако, что в опубликованных изложениях этой математической модели встречаются неточности в формулировках и практически отсутствуют доказательства.

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

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

В качестве модели машинной памяти рассмотрим счетное бесконечное множество О объектов с выделенным начальным (корневым) объектом

reo.

ОПРЕДЕЛЕНИЕ 2.1. Состоянием памяти назовем пару <AS,P>, где Л5 — конечное подмножество множества О, есть множество занятых объектов, а Р С О х О —отношение "указывает на" —рефлексивное бинарное отношение на О.

ОПРЕДЕЛЕНИЕ 2.2. Состояние памяти назовем корректным, если оно удовлетворяет следующим инвариантам:

Ja : г € AS.

h : (((а, Ъ) € Р) А (а € Л5)) => (b £ /15).

Ь : (((а,Ь) € Р) А (а 4 AS)) (/> = а).

ОПРЕДЕЛЕНИЕ 2.3. Сборкой мусора для данного состояния памяти <AS,P> называется состояние памяти <AS',P'> такое, что

AS' С AS и

{aeAS')=>{P'{a)^P{a)). Сборка мусора называется корректной, если

(<AS,P> корректно) => (<Л5',Р'> корректно)

(Корректным)алгоритмом сборки мусора называется функция, отображающая корректные состояния памяти на (корректные) их сборки мусора.

Определение 2.4. Пусть <AS,P> и <AS,Q>—корректные состояния памяти, причем Q Э Р. Тогда <AS,Q> называется указательным расширением (pointeraugmentation) для <AS,P>.

Теорема 2.1. Пусть <AS,P> —корректное состояние памяти. Множество AS1 С AS задает корректную сборку мусора тогда и только тогда, когда найдется такое <AS,Q> —указательное расширение для <AS,P>, что AS1 =Q*(r)>

Определение 2.5. Указательное частично упорядоченное множество (сокращенно У-множество) есть тройка <D, >, _L>, где D —непустое множество, > — рефлексивное, транзитивное и антисимметричное отношение на D, a L 6 D — минимальный элемент, такой, что V.t 6 D выполнено х > _L.

Определение 2.6. Пусть V = <D,>,±> —У-множество, a S ~ <AS,P> —корректное состояние памяти. Вложение S в 'D есть пара <F, Л> функций из О в V таких, что

Va, Ь € О (а,Ь)€Р F(a) > Л(Ь).

Вложение <F,A> определяет индуцированное отношение "указываетна" PptA на О в виде

(«, Ь) € PF„i & F (а) > А(Ь) А ({а = 6) V ((a € AS) A {b G .4S))). Вложение называется точным, если Р^д = Р.

Определение 2.7. Пусть î> = <Д >d, -L/;> и £ = <E,>e, ±e> — У-множества. Функция h m V в E называется гомоморфизмом, если она есть отображение "на" и монотонна.

При консервативной идентификации указателей консервативное отношение "указывает на" есть просто указательное расширение для истинного отношения "указывает на".

Описание генерационной сборки мусора лишь немногим сложнее. Неформально можно рассматривать работу генерационного алгоритма сборки мусора как разбиение множества занятых объектов на подозрительные объекты, рассматриваемые как кандидаты на освобождение, п иммунные объекты, которые не будут освобождаться. Кроме того, алгоритм сборки мусора может, по соображениям эффективности, выделить множество посторонних объектов, заведомо не содержащих указатели на подозрительные объекты. Это множество не обязательно содержит все объекты без указателей на подозрительные объекты, однако выгодно отнести к посторонним возможно больше объектов, избавляя алгоритм сборки мусора от необходимости их просмотра.

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

Определение 2.8. Идеалом У-множества V ~ <D,>,±> называется непустое замкнутое по убыванию подмножество D.

Определение 2.9. Пусть Т>\ = <D],>\,h> и Т>2 — <7^2, >2--1-2> — У-множества. Их строгим (strict) декартовым произведением V — Х>1 х 2?2 называется У-множество V — <D,>,±>, где

D ={-L} U {(.гч,х-2) | xi € D\ \ {J-i} А х2 € D2 \ {±з}},

-L > J-, (z 1,Z2) > 1.

и (xi, X2) > (г/i, ¡/2) тогда и только тогда, когда xi >1 yi А хг >2 2/2-

Строгость операции прямого произведения заключается в том, что принимаются следующие соглашения относительно J. :

=(±,х2) = (_L,J.)=±.

Определение 2.10. Пусть даны функции f:S D и g: S Е. Определим f<g>g:S-lDxE как

U®g){x) = {f{x),g{x)) Vxes.

JIemma 2.2. Пусть S — <AS,P> —корректное состояние памяти. Пусть далее, <F, А> и <F', Ä> —вложения S в V и V соответственно. Тогда <F 0 F', А ® А'> —вложение S в V х V, причем

^F©F',A©A' — РF,A П Рр\Л' U

и {(М) I (a£AS) А (be AS) А ((Л ® A')(h) = ±)}.

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

Сделаем следующие предположения относительно системы управления памятью:

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

Рассмотрим корректное состояние памяти <AS,P>. Представим множество AS в виде AS = Ucee гДе С есть множество всех типов (классов) объектов, а AS(c) С О —множество всех занятых объектов

класса с. Будем рассматривать такие сборки мусора, при которых множества Т, I и В подозрительных, иммунных и посторонних объектов соответственно, представимы в виде объединения А!?(с).

Т = У / = и В = У Л5(с),

сбСт сес/ сес;»

где Ст и С/ и С'в = С. Заметим, что из последнего равенства следует соотношение ТИТИВ—АБ..

Здесь мы используем понятия иммунного и постороннего множеств, несколько отличающиеся от тех, что были даны раньше. Если обозначить через /' и В' соответственно множества иммунных в старом смысле и посторонних в старом смысле объектов, то новые множества могут быть выражены как В = В' ПГ н I = Г \ В.

Определим отношение Рс на множестве С следующим образом:

(с1, с2) Е Рс &

(из объекта типа с\ возможна ссылка на объект типа с'2).

Определение 2.11. Множества Ст,С'/ и С в называются согласованными с отношением Рс, если для них выполнены следующие три условия:

• Ст и С/ и Су = С.

• Для любого класса а Е С/ найдется класс Ь € Ст такой, что (а ,6)£Р,

• Если а е С'в и (а,б) е Рс, то Ь е Св и С/.

Теорема 2.3. Сборка мусора, определяемая согласованными множествами С'т, С[ и С в при помощи соотношений

Т= и / = и Л5(с), В= и А5(с)

с£Ст е€С1 с£ Сн

является корректной сборкой мусора.

С учетом этой теоремы представляет интерес описание всех согласованных троек (Сг,С/, Св) для данного множества классов С и отношения

Рс

Пусть Ьрс есть отношение на С, такое, что

где а б С и Ь а С, а Р^ обозначает рефлексивно-транзитивное замыкание отношения Рс- Ясно, что Ь —отношение эквивалентности на множестве С.

Рассмотрим фактормножество С/Ь и отношение Рс/Ь на нем, индуцированное отношением Рс- Можно показать, что ориентированный граф (С/Ь,Рс/Ь)—ациклический. Выбор произвольного множества вершин этого графа задает множество классов подозрительных объектов и однозначно определяет согласованные множества классов иммуннык и посторонних объектов.

Теорема 2.4. Для любого подмножества 5 € С/Ь множества

Ст = и

«е.?

С, = и 5 и

¿£(7

св=с\(с/ист),

где <т ={х £ (С/Ь \ 5) [ Зу € : (х, у) е Рс/Ь}, согласованы.

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

р := очередное значение порога чистки;

если р = 1.0 то Т := АБ;

иначе Ч := 0;

3 := множество всех классов, отсортированное по степени роста числа объектов с момента последней сборки мусора; цикл пока ^ < р выполнять

X := максимальный элемент в Б; удалить X из Б;

// Таблица А содержит дохло объектов // класса X среди объектов, созданных // после последней сборки мусора

q := q + А[х]; добавить х к Т;

цикл для всех у таких, что объекты класса у погут ссылаться на объекты класса X выполнять

если у не содержится в Т то удалить у из S; добавить у к Т;

q := q + А[у] ;

конец если конец цикла конец цикла конец если

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

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

Третья глава описывает алгоритм автоматического освобождения памяти в распределенной объектно-ориентированной СУБД.

Алгоритм, используемый в СУБД GOODS, позволяет выполнять сборку мусора в фоновом режиме одновременно на всех серверах распределенной базы данных. Алгоритм относится к классу "отметить —освободить". Основными трудностями при реализации маркировки достижимых объектов в распределенной СУБД являются децентрализация управления, потенциальная ненадежность и относительно низкая пропускная способность каналов связи между узлами сети. Другой проблемой, возникающей при реализации сборки мусора во внешней или виртуальной памяти, является поддержание локальности ссылок. Классические алгоритмы сборки мусора малопригодны с этой точки зрения. Потенциально большой объем базы данных приводит к необходимости параллельной сборки мусора. Поэтому на каждом сервере базы данных сборка мусора реализована в виде

Класс алгоритмов Вид неполноты

Генерационные типовые Сохраняются недостижимые объекты, не принадлежащие множеству типов, подвергаемых освобождению

Генерационные временные Сохраняются недостижимые объекты, созданные достаточно давно

Параллельные и инкрементальные Сохраняются некоторые объекты, ставшие недостижимыми во время работы алгоритма

Консервативные Сохраняются недостижимые объекты, на которые были обнаружены ложные ссылки

Таблица .1. Основные виды неполноты частичных сборок мусора

отдельного низкоприоритетного процесса.

2.1. Основные шаги алгоритма. Для синхронизации сборки мусора на различных узлах сети используется выделенный сервер базы данных. Алгоритм состоит из трех фаз:

• Инициализация. При наступлении некоторых условий, связанных с количеством и объемом создаваемых объектов, серверы базы данных посылают выделенному серверу базы данных запрос на выполнение сборки мусора. В случае отсутствия активного процесса сборки мусора выделенный сервер принимает решение о начале сборки и оповещает об этом все серверы.

• Маркировка. На всех серверах происходит независимая локальная маркировка доступных объектов с использованием информации об объектах, копии которых находятся у процессов-клиентов. Так как маркировка происходит в фоновом режиме, возможно изменение мутатором объектов, просмотренных сборщиком мусора. Обработка таких изменений происходит как в алгоритме Дейкс-тры (непомеченные объекты, непосредственно доступные из изменившихся, помечаются и помещаются в список непросмотренных). Для уменьшения числа обращений ко внешним устройствам

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

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

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

Четвертая глава посвящена описанию реализации алгоритмов сборки мусора в системе управления памятью среды С~Гз1к В главе достаточно подробно описаны структуры данных и алгоритмы использованные при реализации системы управления памятью, обсуждаются виды

Storage О

12

В'

■"».'ITT^Î ■fai^HM,,

СмЗ

п ь сз

А " "

balance

V а

- Ъ

-лЪу-А^сУ Ак\

Storage 1

Storage 2

f\k A 'HftHyj / r{e}if\{g}yJ \ \ [4

! ■ d i

'i BÏTi i^ii'i «il 1»1 "Г. 1 G / . ' G3 .

1 П- s-'h tjfr Yi i "в ;zj 1— ' "W*"^ 1___i ь&шЗ

| EES i IS3 • <■

iïnliïlt/r.'.i в j .....Г

Storage n

Рисунок .1. Очереди внешних запросов в начале второй фазы маркировки

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

Сложность С маркирующего алгоритма сборки мусора может быть приближенно выражена как С = miu-^-mofl, где и обозначает количество доступных объектов, а а —количество всех объектов, под которые отведена память (как доступных, так и недоступных), т\ —сложность маркировки и сканирования одного объекта, 1112 —сложность действий, производимых на втором проходе алгоритма сборки мусора. Для всех интересных с практической точки зрения алгоритмов выполнено соотношение т\ > тт.

Удобно рассматривать величины и и а как функции от числа запро-

чина а (г) достигает размера отведенной памяти I, запускается алгоритм сборки мусора, который делает а (г) равным «(>'), т.е. освобождает все недоступные объекты.

Предположим сначала, что программа вошла в установившийся режим, т.е. количество достижимых объектов постоянно, и(г) — и о -- const. Будем измерять затраты £ на алгоритм сборки мусора как отношение сложности С к количеству запрошенной памяти '72. £ характеризует время, затрачиваемое алгоритмом сборки мусора на единицу запрашиваемой динамической памяти. В качестве меры эффективности, примем величину обратную S. Тогда, для достаточно больших значений 71 имеем

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

В предыдущих рассуждениях мы предполагали, что функция «(/ ) есть константа. На практике это сильно меняющаяся неизвестная функция, для которой, как правило, невозможно заранее указать оптимальное значение t. Из формулы 2.1 видно, что эффективность алгоритма сборки мусора определяется отношением u/t. Поэтому во многих реализациях задаются некоторым априорным значением q для величины u/t. При старте программы для динамической памяти отводится некоторый начальный квант tQ. По исчерпании динамической памяти запускается алгоритм сборки мусора. После его выполнения становится известно те-

шенных объектов

что как только вели

кущее значение u(r). Если отношение u(i-)/t(r) превышает q, то для размещения объектов запрашивается дополнительное количество памяти

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

В системе управления памятью среды C~ialkиспользуется другой метод вычисления величины ia(r). На основании значений функции м(г) для двух последних запусков алгоритма сборки мусора прогнозируется значение функции u(r) в будущем. Прогнозирование производится путем линейной экстраполяции. Применение описанного эвристического алгоритма определения размера дополнительной памяти привело к заметному улучшению производительности системы С~Та1к, особенно, при старте программы.

Глава завершается обсуждением некоторых дополнительных возможностей системы управления памятью —слабых ссылок и финализаторов (деструкторов).

В заключении диссертации сформулированы ее основные результаты.

В приложении 1 дан обзор среды С~7а//с

ПРИЛОЖЕНИЕ 2 содержит описание представления объектов в среде

С-Та1к

Приложение 3 содержит описание представления объектов в СУБД

GOODS.

3. Основные результаты работы Основные результаты работы

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

• Разработан алгоритм частичной (генерационной) сборки мусора, основанный на использовании информации о типизации объектов. Доказана корректность сборки мусора, задаваемой этим алгоритмом.

• Разработан алгоритм параллельной фоновой сборки мусора в распределенной многопользовательской объектно-ориентированной базе данных.

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

• Программно реализована система управления памятью для среды

С-Та1к

4. Печатные работы по теме диссертации

Абрамов И.В., Книжник К.А., Роганов Е.А. С~Та1к—среда разработки программных систем. Базовое программное обеспечение. — М., МАСИ,

1993.-С. 5-12.

Абрамов И.В., Книжник К.А., Роганов Е.А. Справочное руководство по языку программирования С-Та!1<, Базовое программное обеспечение. — М., МАСИ, 1993. -С. 13-52.

Абрамов И.В. Алгоритмы распределения памяти с автоматическим освобождением, Базовое программное обеспечение. — М.,МАСИ, 1993. — С. 53-92.

Абрамов И.В. Алгоритм частичной сборки мусора, основанный на информации о типизации объектов, Базовое программное обеспечение. — М., МАСИ, 1994.

Абрамов И.В., Книжник К.А. Параллельный фоновый алгоритм сборки мусора в распределенной объектно-ориентирозанной базе данных, Базовое программное обеспечение. -М..МАСИ, 1994.

Абрамов И.В., Книжник К.А. Реализация системы программирования на языке С~Га1к, Базовое программное обеспечение. — М., МАСИ, 1994.

Абрамов И.В., Роганов Е.А. Архитектура системы ввода-вывода в объектно-ориентированных средах, Базовое программное обеспечение. -М., МАСИ, 1994.