Разработка и метод алгоритмов сокращения времени обработки данных в файлах прямого доступа (на примере АСУ металлургического предприятия)

• Автор: Соболев, Олег Серафимович
• Шифр специальности: 05.13.06
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 233 c. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

I. МЕТОДИКА ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНЫХ ПАРАМЕТРОВ ФАЙЛОВ

БАЗ ДАННЫХ ДЛЯ РЕГУЛЯРНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ОБРАБОТКИ ДАННЫХ

1.1. Постановка общей задачи определения оптимальных параметров файлов баз данныхдля регулярной последовательности обработки данных .

1.2. Многоуровневое проектирование информационного

фонда АСУ.
1.3. Задачи сокращения времени доступа за счет выбора оптимальных параметров файлов баз данных .

Краткие выводы.

П. МЕТОД ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ БЛОКОВ В ФАЙЛЕ ПРЯМОГО ДОСТУПА

2.1. Постановка задачи оптимального размещения блоков

в файле прямого доступа .
2.2. Сведение задачи оптимального размещения блоков по цилиндрам МД к набору задач линейного целочисленного программирования.
2.3. Метод решения задачи оптимального размещения блоков
в файле прямого доступа .
Краткие выводы
Ш. АЛГОРИТМ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ БЛОКОВ ФИКСИРОВАННОЙ ДЛИНЫ В ФАЙЛЕ ПРЯМОГО ДОСТУПА
3.1. Свойства множества перестановок блоков фиксирован
ной длины
3.2. Доказательство сходимости алгоритма
3.3. Оптимальное размещение блоков в группе с фиксированным корневым элементов
3.4. Оптимальное размещение блоков в группе со
свободным корневым элементом
3.5. Алгоритм переноса элементов в группе со свободным корневым элементом .
3.6. Свойства множества эквивалентных перестановок
3.7. Оценка временной сложности алгоритма .
3.8. Эвристические алгоритмы задачи размещения блоков
в файле прямого доступа .
Краткие выводы .
1У. АЛГОРИТМ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ БЛОКОВ ПЕРЕМЕННОЙ ДЛИНЫ В ФАЙЛЕ ПРЯМОГО ДОСТУПА
4.1 Свойства множества перестановок блоков перемен
4.2 Определение достаточных условий оптимальности Ю
4.3 Свойства множества эквивалентных перестановок Ц
4.4 Оценка временной сложности алгоритма .
Краткие выводы
У. ОБЛАСТЬ ПРИМЕНЕНИЯ АЛГОРИТМОВ
5.1 Измерение времени доступа, связанного с перемещением механизма доступа ИД.
5.2 Модификация метода доступа ОС ЕС
5.3 Схема использования в СУБД ОКА или СУБД
5.4 Схема использования в СУБД ИНЕС
5.5 Схема использования в СУБД
5.6 Программное обеспечение алгоритма оптимального
размещения блоков фиксированной длины в файле прямого доступа и алгоритма блокирования записей в файле прямого доступа .
5.7 Расчет экономической эффективности
Краткие выводы.
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ


З выбор языка программирования. Решение перечисленных задач повышает производительность вычислительной системы и необходимо в связи с возрастанием потребностей АСУ в увеличении производительности программных и технических средств, расширении оперативной и внешней памяти [9, ] . Одним из существенных путей сокращения времени обработки данных является минимизация времени доступа (ввода-вывода). Принцип минимизации времени ввода-вывода является одним из основ -ных принципов построения АСУорганизационного управления,сформулированных академиком Глушковым В. М.[I]. На основе статистических данных,собранных во время эксплуатации программ обработки данных в различных подсистемах ОАСУчермет [] с помощью средства сбора статистики ( 5МР ОС ЕС) [] и представленных на рис. Рис. К?0,5 для большей части программ обработки данных. Следовательно оптимизация времени доступа обеспечивает основной вклад в сокращение времени обработки данных в АСУ организационного типа. Задача минимизации времени доступа является многоэкстремальной задачей большой размерности с наличием связей по многим переменным, имеющей нелинейный вид функционала, обозначающего суммарное время доступа к данным [2] . Конструктивных методов решения этой задачи в рамках полного объекта управления, такого как металлургическое предприятие, в настоящий момент не существует. Б данной работе рассматривается одна из составляющих этой общей задачи - задача минимизации времени доступа группы функциональных программ АСУ с регулярной последовательностью обработки данных за счет выбора оптимальных параметров файлов или БД Под группой функциональных программ подразумевается либо все программы некоторой подсистемы АСУ, либо та их часть, которая отличается регулярной последовательностью обработки данных. При решении задачи, поставленной в таких предположениях, возможно разбить исходную задачу на ряд задач, оптимизирующих отдельные составляющие времени доступа и найти последовательность решения задач, в результате которой сокращается время доступа при решении очередной задачи в последовательности. Особенностью АСУ организационного типа является то, что характеристики программ обработки данных достаточно близки к детер-мированным и, практически, не зависят от случайных факторов-* [9,]. К таким характеристикам относятся объем обрабатываемых данных, последовательность обработки данных, времена, к которым должны быть выполнены программы обработки. На рис Л Л. ОАСУчермет,характеризующий относительную устойчивость этих подсистем во временном интервале, сравнимом с циклом функционирования АСУ, равным году. Детермированный порядок обработки данных справедлив для подсистем АСУ, использующих группы функциональных программ, в которые вносится небольшое количество изме -нений типа: добавление новой программы или модификация структуры алгоритма работающей программы. Исходной информацией для решения задачи минимизации времени доступа группы функциональных программ за счет выбора оптимальных параметров файлов или ЕД является 2 - последовательность (рис. ЭВМ в однопрограммном режиме группы программ и последовательности обработки данных каждой программой. На рис Л. Ь: - длина у-ой записи в файле. Преполагается, что последова -тельность программ построена априори на основе определения; оптимального расписания выполнения функциональных программ на ЭВМ в однопрограммном режиме, которое, в свою очередь, конструируется на основе установленных приоритетов программ и их информа -ционной зависимости. Последовательность обращения к данным в каждой программе построена априори в результате концептуального и логического проектирования. Рис. Мк •&? К ‘1^ ^ Мк'&і" ? Iх-*. I ^ в V. Ат? П, доступная программам, обращающимся к ? П, распределенной для ключей, если К -ый файл имеет ключи. Т , т. Рассмотрим некоторые свойства функционала Т . С? - константа, зависящая от организации файла, обозначающая время, затраченное на открытие К -ого файла. Тк - время доступа, связанное с передачей данных при обращении к К -ому файлу. Ъ'ЕЦС Т; * Г, * (1. К'-ому файлу.