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