Эмпирический алгоритм решения задачи сегментации. Степень сложности алгоритма решения
Эмпирический алгоритм решения задача сегментации.
Степень сложности алгоритма решения
Рамазанов Е.Т.
За
последнее время в области компьютерных технологии большее внимание
исследователей занимает не инженерные решении различных устройств, а сами
программы. Иными словами именно программы выступают в качестве основных
объектов исследования. Эта направление исследований не является новым, еще в
советское время благодаря фундаментальным работам Ляпунова А. А., Ю.Н. Янова
С.С. Лаврова давши основу такой области знания как теоретическое
программирование, уделялось внимание исследованию программ. Было определено ряд
проблем и задач теоретического программирования, которые в связи с повышением
интереса к исследованию программ находят новое свое рождение и становятся одним
из многих актуальных проблем современной науки. Одним из таких задач является
задача сегментации. Задача сегментации связана с проблемами оценки
производительности и управлением вычислительными процессами ЭВМ с виртуальной
памятью. Под задачей сегментации обычно принято понимать задачу разбиение
последовательной программы на взаимозависимые по управлению и информационно
части (блоки, секции, сегменты и. т.д) в соответствии с той или иной целью[1.
9-11]. В случае рассмотренном в данной статье задача сегментации определяется
как задача разбиение программы на части по сегментам или страницам виртуальной
памяти.
Проблема
заключается в том, что при размещении программы по сегментам виртуальной
памяти каждый элемент программы получает свой адрес. Операционная система
выделяет каждой программе некоторый участок основной памяти. Причем объем
выделенной памяти меньше чем сама программа. По мере выполнения программы в
памяти находятся копии страниц программ. Обмен между вспомогательной памятью и
основной осуществляется целыми страницами, во время обмена центральный
процессор переключается на выполнение команд другого сегмента, если во время
выполнения программы происходит ссылка на сегмент программы, которая
отсутствует в основной памяти, то происходит страничное прерывание. Выполнение
программы прерывается. Из-за программ, в которых происходит страничные
прерывание, снижается производительность самой операционной системы. Существуют
различные алгоритмы разрешение данной проблемы[1,16-20]. Такие алгоритмы
обеспечивают как можно меньшее число страничных отказов.
Интересен теоретическии подход решение данной проблемы как задачи сегментации.
Известны различные подходы решения задачи сегментации одним из которых является
графовый подход.
Идея
графового подхода заключается в определении графа. Вершинам графа
соответствует блоки программ, ребрам- передачи управления между блоками
программы. Вес вершины определяет размер блока программы.а вес ребра число
передач управления между блоками. Задача состоит в разбиении вершин на
множества так чтобы сумммарный вес вершин попавших в одно множество не
превосходил веса множества т.е. страницы. А суммарный вес ребер между
разбитыми множествам вершин был бы минимален. На основе графового
определение задачи сегментации была построена модель решения задачи сегментации
дающию возможность испольовать методы кластерного анализа. Принципиальную
возможность применение кластерного алгоритма и условия при котором алгоритм находил
бы найболее точное решение обосновал в своем фундаментальном труде профессора Каз НУ им. аль-Фараби Дюсембаев А.Е. [1]. Следуя идеям Журавлева Ю.И., операторный алгоритм решения задачи
имеет степень сложности, зависящий от исходных данных задачи. По определению степень сложности имеет вид
; где максимальное
значение матрицы оценок. -
число блоков программы, -число
сегментов виртуальной памяти, - пороговые значения решаюшего правила
алгоритма определенные в [1] причем
обладают свойствам .
Напомним, степень сложности определяет что, для заданной задачи существует
различные информационные матрицы, т.е. по Журавлеву существует различные
корректные алгоритмы решения. Определение степени сложности алгоритма приводит
к решению вопроса точности алгоритма. Одним из путей разрешения токого вопроса
состоит в определении условии при которых алгоритм был бы заданной степени
сложности. Естественно возникает вопросы, можно ли понизить степень и как выбор
степени влияет на решающее правило. Степень сложности операторного алгоритма для задачи сегментации описанного в работе[1] можно понизить до второго порядка если задать
пороговые значения зависимостью
имеющии вид :
Доказательство:
представим задачу на нахождение экстремума функции. Так как степен сложности , то ; будет . Это будет справедливо и для
соотношения так
как . Рассмотрим
случай когда модули равны соответственно:
Построим задачу
поиска экстремума функции
Предполагается, что
значение функции доставляющие
локальный экстреммум этой функции будет точкой экстремума и функции , так как при выборе
значении выполняется
условия можеранты. следуя правилам высшей матиматики заключим что, решение
поставленной задачи понижает степень до второго порядка.
Представим
эмпирический алгоритм решение задачи сегментации использующий принцип
оптимальности Беллмана. Пусть задана блоков. И размеры заданных блоков соответственно. Память
выделенной операционной системой разбита на сегментов. Допустим ,что число блоков
программы больше числа сегментов . Причем где сегмент. С практической точки зрения
рассмотрим случай когда .
Также пусть задана матрица передач управления между блоками число передач между блоками и . Очевидно матрица передач
симметричная матрица ,
так как суммарное число передач имеет свойство ассоциативности. Необходимо
разбить блоки, по сегментам так, чтобы суммарное число передач между
сегментами было минимально. Сегменты обладают свойством . Выполнение заданного свойства
гарантирует тот факт, что при разбиении блоков по сегментам каждый блок
программы может принадлежать только одному сегменту. Алгоритм является
последовательным и выполняет шаги до тех пор, пока все блоки не будут разбиты
по сегментам. Представим таблицу передач (таблица 1). В таблице по главной
диагонали, все ячейки сделаем нулевыми. Идея алгоритма заключается в
следующем: На первом шаге выбираем произвольный блок пусть выбран определим его в
произвольно выбранный блок, пусть . Находим по матрице в первом столбце
максимальное число, если в столбце несколько чисел равны между собой и являются
максимальными, то выбирается произвольный из них. Выбрав максимальное число по
столбцу, алгоритм определяет блок с которым определенный в сегмент блок имеет максимальное число передач.
Далее алгоритм проверяет, может ли найденный блок быть определен в сегмент . Т.е. вычисляет по таблице
размеров сумму ,
если выполняется условие, то блок и на следующем шаге рассматривается этот
блок. Если «нет», то блок присваивают следующему сегменту. Суть
алгоритма заключается в рассмотрении каждого блока по его признакам. Каждый
блок обладает признаками
при . При присвоении блока
сегменту, сегмент наследует эти признаки. И на каждой итерации при рассмотрении
нового блока, этот блок присваивается тому сегменту которая в на данном шаге
имеет характеристику, которая является более оптимальным с точки зрения цели
задачи. Алгоритм продолжает свою работу до тех пор пока не будут рассмотрены
все блоки.
Литература
1.
Дюсембаев А.Е. Математические модели сегментации
программ:-М. Физматлит. 2001г.
2.
Журавлев Ю.И. Корректные алгебры над множествами
эвристических алгоритмов/ Кибернетика 1978г № 2.