Стратегии распределения памяти

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

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

1. Первое возможное размещение.

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

2. Наилучшее размещение.

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

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

Объектно-ориентированное программирование

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

Внутренность объекта. Каждый объект содержит переменные, в которых находятся данные, его описывающие (в различных ООЯ названия некоторых характеристик могут отличаться, например в языке Object Pascal (Delphi) переменные называются полями). Пусть объект с именем «Окружность А» (рис.14) – это фигура, которая может быть нарисована на экране компьютера. Переменные этого объекта: позиция (позиция на экране центра окружности) и размер (радиус окружности).

Операции над данными объекта запускаются при получении им сообщения, указывающего нужную последовательность действий. Конкретная процедура, которая идентифицируется с сообщением, содержится внутри объекта в виде внутренней программы, которая называется методом. Метод выполняет манипуляции с данными объекта, а также может посылать сообщения другим объектам с целью получения нужного результата, который затем возвращается назад к первому объекту. Объект «Окружность А» имеет три метода. Метод форма говорит объекту как описать его форму, обращаясь к своим переменным, а также посылая сообщения другому объекту «Маркер», который выполняет работу по вычерчиванию. На рис. обозначены методы объекта «Маркер» (сообщение, вызывающее метод Маркер сдвигК посылает координаты центра окружности, т.е. значение переменной Позиция). В объекте «Окружность А» метод форма вызывается своими же методами высветить и стереть. Методы высветить и стереть посылают сообщения Себе – встроенному имени, позволяющему объекту (в нашем случае «Окружность А») направлять сообщения самому себе. Метод высветить приказывает Себе использовать метод форма для создания окружности, послав предварительно сообщение Маркеру о том, что он должен рисовать черные линии. Метод стереть говорит Себе использовать метод форма для удаления окружности, что делается с применением Маркера, рисующего белым цветом.

Каждый объект в объектно-ориентированном окружении имеет собственные характеристики. Однако объекты имеющие одинаковые свойства и ведущие себя сходным образом объединяются в классы. Класс­ задает общие свойства его составляющих (называются экземплярами), т.е. все они имеют одинаковое число переменных одного и того же типа, реагируют на одни и те же сообщения и реализуют одни и те же методы работы со своими переменными. Экземпляры класса отличаются один от другого конкретными значениями собственных переменных. Рассмотрим пример упрощенного объектно-ориентированного языка, организованного как иерархия суперклассов и подклассов (рис.15). На самом нижнем уровне находится класс «Объект», который задает общие свойства всех объектов, например, их способность отвечать на сообщения. «Дисплейный объект» – это подкласс класса «Объект». Подкласс наследует сообщения и методы суперкласса, кроме того, он может содержать новые сообщения и методы, реализующие его особенности. «Дисплейный объект» представляет собой как бы эскиз объектов, которые отображаются на экране. Он задает методы построения дуг, прямых, и т.д. Класс «Многоугольник» имеет переменные позиция, стороны, угол,…и методы форма, высветить, стереть.

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

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

Показано, что наиболее удобными для реализации программных систем, разработанных в рамках объектно-ориентированного подхода, являются объектно-ориентированные языки программирования, хотя возможна реализация и на обычных (не объектно-ориентированных) языках (например, на языке C и на языке Fortran). Первый объектно-ориентированный язык программирования Simula 67 был разработан в конце 60-х годов в Норвегии. Авторы этого языка очень точно угадали перспективы развития программирования, но их язык намного опередил свое время. Однако современники (программисты 60-х годов) оказались не готовы воспринять ценности языка Simula 67, и он не выдержал конкуренции с другими языками программирования (прежде всего, с языком Fortran). Прохладному отношению к языку Simula 67 способствовало и то обстоятельство, что он был реализован как интерпретируемый (а не компилируемый) язык, что было совершенно неприемлемым в 60-е годы, так как интерпретация связана со снижением эффективности (скорости выполнения) программ. Но достоинства языка Simula 67 были замечены некоторыми программистами, и в 70-е годы было разработано большое число экспериментальных объектно-ориентированных языков программирования: например, языки CLU, Alphard, Concurrent Pascal и др. Эти языки так и остались экспериментальными, но в результате их исследования были разработаны современные объектно-ориентированные языки программирования: C++, Smalltalk, Eiffel и др. Наиболее распространенным объектно-ориентированным языком программирования безусловно является C++. Свободно распространяемые коммерческие системы программирования C++ существуют практически на любой платформе. Широко известна свободно распространяемая система программирования G++, которая дает возможность всем желающим разобрать достаточно хорошо и подробно прокомментированный исходный текст одного из образцовых компиляторов языка C++. Разработка новых объектно-ориентированных языков программирования продолжается.

Дескриптивные языки (языки логического программирования).