17.4. ПРИМЕНЕНИЕ АЛГОРИТМОВ АВТОМАТИЧЕСКОЙ КЛАССИФИКАЦИИ
Алгоритмы автоматической классификации применялись для решения двух проблем:
1) уменьшения числа страниц памяти, требуемого при выполнении программы;
2) минимизации числа обменов информацией при использовании библиотеки подпрограмм.
В обоих случаях необходимы характеристики поведения программы или библиотеки. С одной стороны, во время создания программы или библиотеки нельзя предсказать, как они будут себя вести. С другой стороны, их поведение стабильно, т. е. значения характеристик в определенный промежуток времени говорит о поведении вообще.
Эти характеристики хранятся в виде матриц обмена 
где 
количество секций или модулей. В первом случае элемент этой
матрицы 
равен числу вызовов 
секции 
за фиксированный промежуток времени. При реструктуризации библиотек 
равно количеству одновременных вызовов 
модулей.
Применялись два алгоритма — динамических сгущений и иерархической классификации.
17.4.1. Применение алгоритма динамических сгущений
Алгоритм динамических сгущений использует матрицу расстояний, тогда как в нашем распоряжении есть только матрица обмена 
. В качестве расстояния возьмем величину, обратную 
Главная сложность заключается в необходимости априорного определения числа классов (сегментов). Уже нельзя определять размеры сегментов из условия наиболее полного заполнения страниц, т.е. чтобы минимизировать потери памяти в конце каждой страницы. Тем не менее удавалось получать хорошие результаты как для первой, так и для второй задачи [5]. Мы еще не пробовали применять мультикритериальную классификацию (см. гл. 3), которая кажется более уместной.
17.4.2. Применение алгоритмов иерархической классификации
Мы воспользовались алгоритмом иерархической классификации, работающим непосредственно с матрицей обмена. Основное преобразование заключалось во введении ограничений на размеры группируемых элементов. Перегруппировка осуществлялась только в том случае, когда сумма размеров группируемых элементов не превосходила, размеры страницы или кванта памяти. Благодаря этому ограничению процесс перегруппировки в определенный момент прекращался и полученные при этом блоки размещались на границах страниц (квантов).
Опыт показывает, что при такой реструктуризации потери памяти малы, а полученные структуры благоприятны.
