автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка и исследование метода управления двухуровневой памятью вычислительной системы на основе мультипроцессности

ВВЕДЕНИЕ

ГЛАВА I. ОБЗОР ИССЛЕДОВАНИЙ ПО УПРАВЛЕНИЮ ДВУХУРОВНЕВОЙ

ПАМЯТЬЮ ШЧИСЛИТЕЛЬНЫХ СИСТЕМ. ц

1.1. Общее состояние вопроса. ц

1.2. Алгоритмы замещения . Х

1.3. Поведение программ и сравнительный анализ алгоритмов замещения.

1.4. Двухуровневая память в системах управления базами данных

1.5. Методы улучшения поведения программ

1.6. Проблема совмещения вычислений и обменов.

Выводы.

ГЛАВА 2. РАЗРАБОТКА И РЕАЛИЗАЦИЯ МЕТОДА УПРАВЛЕНИЯ ДВУХУРОВНЕВОЙ ПАМЯТЬЮ НА ОСНОВЕ МУЛЬТИПРОЦЕССНОСТИ.

2.1. Квазипараллельная организация вычислительного процесса и управление обменами.

2.2. Мультипроцессный монитор

2.3. Система управления обменами.

2.4. Совмещение вычислений и обменов в мультипроцессной системе

Выводы.

ГЛАВА 3. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ УПРАВЛЕНИЯ ДВУХУРОВНЕВОЙ ПАМЯТЬЮ В МУЛЬТИПРОЦЕССНОЙ СИСТЕМЕ.

3.1. Эффективность мультипроцессной системы для модели независимых обращений к внешней памяти

3.2. Об оптимальной настройке мультипроцессности.

3.3. Оценка качества функционирования реальных систем обработки данных.

Быводы.

ГЛАВА 4. ПРИМЕНЕНИЕ МУЛЬТИПРОЦЕССНОСТИ В ЗАДАЧАХ ОБРАБОТКИ ДАННЫХ .Ю

4.1. Ввод документов в базу данных

4.2. Поиск в многофайловой базе данных.НО

4.3. Задача расчета входимости

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

4.5. Об аппаратной подцержке мультипроцессности .♦„«. 127 Выводы.

Актуальность темы диссертации. Широкое использование средств вычислительной техники в разнообразных автоматизированных системах управления производством, в системах научно-технической информации и в других крупных интегрированных системах делает актуальной задачу эффективного использования этих средств.

Для современных информационных систем одной из главных проблем является обеспечение возможности работы с очень большими объемами данных. Большой прогресс в технологии обработки данных связан с развитием систем управления базами данных, обеспечивших стандартизацию многих функций хранения и доступа для больших объемов информации 3. >15, 58]. Тем не менее проблема эффективности решения задач обработки данных, даже при использовании систем управления базами данных, остается крайне важной [2,6,9, 22.26].

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

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

Несмотря на широкое распространение методов распараллеливания программ в практике системного и прикладного программирования [ 16 , 2.2,28. 2.9, 50 3 , в настоящее время отсутствуют работы, посвященные управлению двухуровневой памятью, базирующемуся на внутрипрограммном параллелизме. Разработка такого метода управления и оценки его эффективности необходимы для целенаправленного применения данного подхода для повышения эффективности систем обработки данных.

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

Методы исследований базируются на использовании теории случайных процессов и имитационного моделирования. Практические вопросы решены путем разработки и реализации рассматриваемых алгоритмов в системе команд ЭВМ EC-I040.

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

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

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

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

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

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

Реализация результатов работы. Наиболее полное воплощение полученные в работе теоретические и практические результаты нашли в проекте специализированного процессора мультиобработки, созданного для повышения производительности ЭВМ серии ЕС на задачах "Автоматизированной информационно-справочной системы оперативного планирования перевозок, работы флота и портов, контроля и анализа выполнения планов" (АСУ "Морфлот"). Работа выполнялась специалистами Института проблем управления, Всесоюзного института системных исследований и Института им. М.Пупина по советско-югославскому контракту № 38/81661/30 от 15.02.1980 г.

Программная реализация предложенного метода - мультипроцесс-ный монитор входит в состав системы управления базами данных ИНЕС как инструментальное средство повышения эффективности программ и программных комплексов обработки данных. Соответствующее программное обеспечение передано в централизованный фонд алгоритмов и программ "Центрпрограммсистем".

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

Практическое использование результатов диссертационной работы подтверждено соответствующими актами о внедрении.

Апробация работы. Основные результаты диссертационной работы были доложены на конференции молодых ученых и специалистов Института проблем управления (Москва, 1976 г., 1-е место), на Конференции молодых ученых и специалистов Всесоюзного научно-исследовательского института системных исследований (Москва, 1979 г., 2-е место), на Второй всесоюзной конференции по банкам данных (Ташкент, 1983 г.). Наряду с этим результаты работы обсуждались на семинарах Института проблем управления, Всесоюзного научно-исследовательского института системных исследований, а также на консультативных встречах советских и югославских специалистов по проекту процессора мультиобработки в соответствии с планом работ по контракту № 38/81661/30.

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

1. Годунов А.Н., Свердлов С.С. Об организации виртуальной памяти в мультипроцессной системе. - Автоматика и телемеханика, 1978, № 12, с.139-142.

2. Волков А.Ф., Годунов А,Н., Дагурова Н.В., Емельянов Н.Е., Золотухина Г.М., Макаров В.А., Свердлов С.С. Программная реализация мультипроцессности. - Препринт Института проблем управления, М., 1979.

3. Годунов А.Н., Свердлов С.С. Алгоритмы замещения страниц виртуальной памяти в мультипроцессной системе. - В сб.: Методы исследования сложных систем, М., ВНИИСИ, 1980, с.46-49.

4. Годунов А.Н., Емельянов Н.Е., Свердлов С.С. 0 программной реализации мультипроцессности. - Программирование, 1981, № 5, с.44-49.

5. Асратян Р.Э., Волков А.Ф., Годунов А.Н., Дагурова Н.В., Емельянов Н.Е., Золотухина Г.М., Макаров В.А., Свердлов С.С.

Аппаратная реализация мультипроцессности в ЕС ЭВМ. - Препринт Института проблем управления, М., 1981. 6. Свердлов С.С. О повышении эффективности доступа к данный в СУЩ на основе мультипроцессности. - В сб.: Банки данных, Киев, 1983, с.12-15.

В работах, написанных в соавторстве, личным вкладом автора являются: в [ 4] - выбор и реализация системы команд мульти-процессного монитора для работы с внешней памятью, исследование мультипроцессности в натурных экспериментах с задачами обработки данных; в L 2.3 - алгоритмы управления обменами и их реализация в ьфгльтипроцессном мониторе, исследования по эффективности мультипроцессного управления обменами; в - алгоритмы функционирования системных процессов мультипроцессного монитора, управляющих обменами; в [5 ] - выбор системы команд процессора мультиобработки, связанных с вводом-выводом, общая методика их аппаратной реализации.

Структура диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения.

Выводы

1. Экспериментальные исследования реальных программ обработки данных, ориентированных на мультипроцессность,показали, что квазипараллельные алгоритмы могут дать выигрыш в 2-30 раз по числу обменов между уровнями памяти по сравнению с последовательными алгоритмами решения тех же задач. При этом трудоемкость программирования и отладки практически не возрастает по сравнению с последовательным программированием.

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

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

4. Показано, что мультипроцессность позволяет обеспечить совмещение работы центрального процессора и канала ввода-вывода при выполнении программы, в то время как в последовательных программах, если это и возможно, то в очень незначительной степени и требует специальных усилий при программировании. На реальных квазипараллельных программах обработки данных было достигнуто снижение общего времени решения за счет совмещения вычислений и обменов в диапазоне от 7 до 25%.

5. Проведенные эксперименты подтвердили целесообразность аппаратной поддержки мультипроцессности для уменьшения загрузки центрального процессора вычислительной системы, которая увеличивается на 5-40% за счет использования программного мультипроцес-сного монитора.

ЗАКЛЮЧЕНИЕ

1. Разработан новый адаптивный метод управления двухуровневой памятью вычислительной системы, базирующийся на широком распараллеливании программ. Показано, что управление обменами на основе мультипроцессности позволяет сокращать число повторных вызовов блоков в оперативную память и совмещать вычисления и обмены в программе.

2. Разработан программный мультипроцессный монитор, реализующий предложенный метод управления двухуровневой памятью и обеспечивающий поддержку мультипроцессной системы большого объема и высокого быстродействия.

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

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

5. Экспериментально исследован ряд типичных задач обработки данных и показано, что мультипроцессность дает выигрыш в 2-30 раз по числу обменов и в I.5-I0 раз по общему времени решения задач по сравнению с последовательной обработкой, причем в ряде случаев превосходит программы, оптимизированные "ручными" методами. 6. Результаты разработки метода управления двухуровневой памятью использованы в проекте процессора мультиобработки, предназначенного для повышения производительности ЭВМ серии ЕС. Мультипроцессный монитор, реализующий данный подход, входит в состав системы управления базами данных ИНЕС как средство повышения эффективности работы с данными. В частности, он использован при проектировании подсистемы декодирования документов "Системы сбора и анализа заявок на перевозку внешнеторговых грузов", входящей в АСУ "Морфлот". При этом достигнуто существенное снижение общего времени решения задачи при незначительных затратах на модификацию исходных последовательных программ.

1. Авен О.И., Киммельфельд Б.Н., Коган Я.А. Управление многоуровневой памятью вычислительной системы. - Автоматика и телемеханика, 1972, № 1., с.138-154.

2. Андон Ф.И., Дерецкий В.А., Поляченко Б.Е. Интегрированное мультипрограммирование в ОС ЕС. Управляющие системы и машины, 1982, № 5, с.58-62.

3. Арлазаров В.Л., Дюкалов А.Н., Емельянов Н.Е., Иванов Ю.Н., Кочин Ю.Я., Токарев В.В., Фараджев И.А. Информационная система ИНЭС. Автоматика и телемеханика, 1979, № 6, с.109-121.

4. Арлазаров В.Л., Волков А.Ф., Годунов А.Н., Емельянов Н.Е., Зенкин В.Д., Константинов Г., Лысиков В.Т. Об аппаратной реализации мультипроцессности. Автоматика и телемеханика, 1977, № 8, с.177-186.

5. Асратян Р.Э., Волков А.Ф., Годунов А.Н., Дагурова Н.В., Емельянов Н.Е., Золотухина Г.М., Макаров В.А., Свердлов С.С. Аппаратная реализация мультипроцессности в ЕС ЭВМ. Препринт Института проблем управления, М., 1981.

6. Бабенко Л.П., Ющенко Е.Л., Вопросы организации прикладного программирования в среде СУБД. Управляющие системы и машины, 1982. № б, с.79-83.

7. Бачурин А.С., Исаев А.Е., Отвагин П.Е., Фомин Б.Ф. Страничный метод доступа для фортрана и ПЛ/l ОС ЕС ЭВМ. Программирование, 1983, № I, с.27-32.

8. Бронштейн И.И. Об оптимальной стратегии замещения программ равных длин в оперативной памяти ЦВМ. Автоматика и телемеханика, 1972, № 3, с.117-123.

9. Бронштейн И.И., Меликян А.Л., Трахтенгерц Э.А. Факторы, влияющие на эффективность работы вычислительных систем. Препринт

10. Института проблем управления, М., 1981.

11. Волков А.Ф., Годунов А.Н., Дагурова Н.В., Емельянов Н.Е., Золотухина Г.М., Макаров В.А., Свердлов С.С. Программная реализация мультипроцессности. Препринт Института проблем управления, М., 1979.

12. Годунов А.Н., Емельянов Н.Е., Марон М.Е. Об эффективности мультипроцессной виртуальной памяти. Автоматика и телемеханика, 1980, № 4, с. 173-176.

13. Годунов А.Н., Емельянов Н.Е., Свердлов С.С. 0 программной реализации мультипроцессности. Программирование, 1981, № 5, с.44-49.

14. Годунов А.Н., Свердлов С.С. Об организации виртуальной памяти в мультипроцессной системе. Автоматика и телемеханика, 1978, № 12, с.139-142.

15. Годунов А.Н., Свердлов С.С. Алгоритмы замещения страниц виртуальной памяти в мультипроцессной системе. В сб.: Методы исследования сложных систем, М., ВНИИСИ, 1980, с.46-49.

16. Ершов А.П. Проблемы баз данных и информационных систем на конгрессе ИФИП-80. Управляющие системы и машины, 1981, № 4, с.140-143.

17. Игнатущенко В.В., Прангишвили И.В., Трахтенгерц Э.А., Фаткин Ю.М. Проблемная ориентация вычислительных систем путем ассоциативного обучения. Автоматика и телемеханика, 1981, № 2, с.156-163.

18. Дийкстра Э. Взаимодействие последовательных процессов. В сб.: Языки программирования, М., Мир, 1972, с.9-86.

19. Кнут Д. Искусство программирования для ЭВМ, т.З, М., Мир,1978.

20. Колин А. Введение в операционные системы, М., Мир, 1975.

21. Кутепов В.П., Пьянков В.П. Алгоритмы определения множества активных страниц (сегментов) программы, основанные на понятии динамического цикла. Программирование, 1979, № 4, с.44-52.

22. Мандрусова Г.П., Манович С,Ф., Медведева Н.М., Каратаева Н.В. Типовая процедура АСУ в среде СУБД ОКА и экспериментальные оценки .эффективности ее реализаций. Управляющие системы и машины, 1980, № 6, с.69-74.

23. Мэдник С., Донован Дж. Операционные системы, М., Мир, 1978.

24. Наумов В.В., Пеледов Г.В., Тимофеев Ю.А., Чекалов А.Г. Супервизор ОС ЕС ЭВМ. М., Статистика, 1975.

25. Операционная система IBM/360. Супервизор и управление данными. М., Советское радио, 1973.

26. Первин Ю.А., Шевякова Т.К. Динамические информационные системы на предприятии. М., Статистика, 1975.

27. Савенко В.А., Дворцин В.И. Параллельный обмен данными с внешними ЗУ на магнитных дисках. Управляющие системы и машины, 1983, № 2, с.95-98.

28. Свердлов С.С. 0 повышении эффективности доступа к данным в СУБД на основе ' мультипроцессности. В сб.: Банки данных, Киев, 1983, с.12-15.

29. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции, М., Наука, 1981.

30. Цикритзис Д., Бернстайн Ф. Операционные системы. М., Мир, 1977.

31. Шоу А. Логическое проектирование операционных систем, М., Мир, 1981.

32. Adams М.С., Millard G.E. Performance measurements on the Edinburgh multy access system (EMAS) Proc. ICS 75, Antibes, 1975.

33. Aho A.V., Denning P.J., Ullman J.D.' Principles of optimal page replacement, Journal ACM, 1971, v.18, n.1, p.80-93.

34. Arvind, Kain R.Y., Sadeh E. On reference string generation process. Operating systems rev., 1973» v.7, N 4, p.80-87.

35. Batson A.P. Program behavior at the symbolic level. -Computer, 1976, v.9, N 11, p.21-26.

36. Batson A.P., Madison A.W. Measurements of major locality phases in symbolic reference strings. Proc. Int. symp. on computer performance modeling measurements and evaluation. Cambrige, Mass., 1976, p.75-84.

37. Baylis M.H.J., Fletcher D.G., Howarth D.J. Paging studies made on the I.C.T. Atlas computer. Proc. IFIPS congress Edinburgh 1968, p.D113-D118.

38. Belady L.A. A study of replacement algorithms for a virtual storage computer. IBM systems journal, 1966, v.5, N 2, p.78-101.

39. Brawn B.S., Gustavson F. Program behavior in a paging environment. AFIPS conf. proc., EJCC, 1968, p.109-1032.

40. Chu W.W., Oliver N., Opderbeck H. Measurement data on the working set replacement algorithms and their applications. -Proc. Brooklyn Polytechnic Inst, symposium on computer communications and teletraffic, 1972, p.113-124.

41. Chu W.W., Opderbeck H. The page fault frequency replacement algorithm. AFIPS conf. proc., FJCC, 1972, p.597-609.

42. Chu W.W., Opderbeck H. Program behavior and page fault frequency replacement algorithm. Computer, 1976, V.9, N 11, p.29-38.

43. Coffman E.G., Denning P.J. Operating systems theory, Prentice Hall, 1973.43* Comeau L. A study of the effect of user program optimization in apaging system. Proc. ACM symp. on operating systems principles, Gatlinburg, 1967.

44. Corbato P.J. A paging experiment with the Multics system. -In Honour of P.M. Morse, Ingard K.U., Ed., Cambridge, Mass., MIT Press, 1969, p.217-228.

45. Denning P.J. The working set model for program behavior. -Comm. ACM, 1968, v.11, N 5, p.323-333.

46. Denning P.J. Virtual memory. Computer surveys, 1970, v.2, N3, p.153-189.

47. Denning P.J. Optimal multyprogrammed memory management. -Current trends in programming methododlogy, v.Ill, Software modelling, Chahdy K.M., Ed., N.J., Prentice Hall, 1978,p.298-322.

48. Denning P.J. Working sets past and present. IEEE trans, on software engeneering, 1980, v. SE-6, N 1, p.64-84.

49. Denning P.J., Graham G.S. Multiprogrammed memory management. -Proc. IEEE, 1975, v.63, N 6, p.^924-931.

50. Denning P.J., Schwartz S.C. Properties of the working set model. Comm. ACM, 1972, v.15, N 3, p.191-198.

51. Easton M.C. Model for database reference string based on behavior of reference clusters. IBM J. Res. and Dev., 1978, v.22, N2, p.197-202.

52. Easton M.C., Pagin R# Cold-start vs. warm-start miss rations and multiprogrammed performance. Comm. ACM, 1978, v.21, N10, p.866-872.

53. Pagin R. Asymptotic miss ratios over independent references. -Journal of сотр. and syst. sciencies, 1977, v.14, N2, p.222-250.

54. Fernandez E.B., Lang Т., Wood C. Effect of replacement algorithm on a page buffer database system, IBM J, res. and dev.,1978, v.22, N2, p.185-196.

55. Ferrary D. Tailoring programs to models of program behavior.- IBM J. res. and dev., 1975, v.19, N 3, p.244-251.

56. Ferrary D. The improvment of program behavior. Computer 1976, v.9. N11, p.39-47.

57. Hatfield D.J., Gerald J. Program restructuring for virtual memory. IBM syst. journal. 1971. v.10. N3, p.168-193.

58. Held G.D., Stonebraker M.R., Wong E. INGRESS a relational database system. - Proc. AFIPS, N.J., AFIPS Press, 1975, p.409-416.

59. Hoare C.A.R., McKeag R.M., A survey of store management techniques. Operating systems techniques, London, Academic, 1972, p.117-151.

60. Jamp R., Spirn J.R. VMIN-based determination of program macro- • behavior. Dep. Сотр. sci., Penn State Univ., Rep* CS-79-34,1979.

61. Joseph M. An analysis of paging and program behavior. -Computer J., 1970, v.13, N1, p.48-54.

62. King III, W.F. Analysis of demand paging algorithms. Proc. IF IP congress, Ljubljana, Yugoslavia, 1971, p.TA-3-155 -TA-3-159.

63. Knuth D.E. An empirical study of FORTRAN programs. Software- Practice and experience, 1971, v.1, N 2, p.105-133.

64. Lenfant J., Bargevin P. Empirical data on programm behavior.- Proc. ACM Int. symp., North Holland, 1975, p. 163-170.

65. Prieve B.G., Fabry R.S. VMIN an optimal variable space replacement algorithm. - Comm. ACM, 1976, v.19, N5, p.295-297.

66. Rogers J.G. Structured programming for virtual storage systems.- IBM syst. journal, 1975, v.14, N4, p.385-406.

67. Rodrigues-Rossel J. Empirical working set behavior. Comm. ACM, 1973, v.16, N9, p.556-560.

68. Rodrigues-Rossel J. Empirical data-reference behavior in data base systems. Computer, 1976, v.9, N11, p.9-13.

69. Rodrigues Rossel J., Dupuy J-P. The design, implementation and evaluation of working set dispatcher. Comm. ACM, 1973, v.16, N4, p.247-253.

70. Shedler G.S., Tung C. Locality in page reference strings.

71. Computer, 1976, v.9, N11, p.14-20, 79,Spirn J, Program behavior: models and measurement, Elsevier,

72. North Holland, 1977. 80.Spirn J,, Denning P#J, Experiments with program locality.