Имитационная модель и метод рационального распределения ресурсов операционной системы тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Белоусов, Сергей Михайлович

• Белоусов, Сергей Михайлович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Белоусов, Сергей Михайлович

ПРИНЯТЫЕ СОКРАЩЕНИЯ.

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ.

ВВЕДЕНИЕ.

Введение диссертации (часть автореферата) на тему «Имитационная модель и метод рационального распределения ресурсов операционной системы»

Цель работы, объект и предмет исследования.10

Методы исследования.10

Научная новизна.11

Практическая значимость.11

Апробация и реализация результатов работы.11

Положения, выносимые на защиту.12

Краткое описание диссертации.13

Анализ предметной области.14

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Белоусов, Сергей Михайлович

Выводы по главе 3

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

Применительно к рассматриваемому вопросу вторая группа методов позволяет более детально проконтролировать процесс оптимизации и сделать его более наглядным. Поэтому задачу обоснования оптимальных (рациональных) параметров планировщика ресурсов целесообразно представить в виде задачи математического программирования с главным показателем качества.

2. В зависимости от используемого главного показателя качества данная оптимизационная задача может быть сформулирована как задача его минимизации или максимизации. Учитывая сложность рельефа целевой функции целесообразно использовать численные методы многопараметрической оптимизации первого порядка. Для рассматриваемого случая такие методы позволят получить решение с приемлемой точностью за 110-120 обращений к процедуре вычисления целевой функции.

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

При этом оказывается проще получить решение задачи максимизации - потребуется в 25-35 раз меньшее количество статистических испытаний.

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

5. Результаты расчетов средних ресурсных потребностей вычислительной системы при различных характеристиках потока поступающих на ее вход задач, показали, что динамика ресурсных требований подобна профилю интенсивности поступления задач, но смещена по времени примерно на 1,6 часа сторону больших значений времени. Кроме этого, ресурсные требования существенно зависят от доли изменяемого ресурса задач 2-го класса (счетные задачи) при их перемещении из счетно-решающего устройства в накопитель, то есть для существующих систем наличие даже небольшого количества задач с большим временем исполнения на фоне стандартной нагрузки дает существенное изменение поведения системы (что наблюдается на практике, когда возникновение процесса резервного копирования, казалось бы не требующего больших ресурсов от системы, приводит к существенному повышению общего уровня нагрузки системы).

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

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

-105

Заключение

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

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

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

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

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

-1065. Существует большое количество разнообразных алгоритмов замещения страниц. Все они делятся на локальные и глобальные. Локальные алгоритмы, в отличие от глобальных, распределяют фиксированное или динамически настраиваемое число страниц для каждого процесса. Когда процесс израсходует все предназначенные ему страницы, система будет удалять из физической памяти одну из его страниц, а не из страниц других процессов. Глобальный же алгоритм замещения в случае возникновения исключительной ситуации удовлетворится освобождением любой физической страницы, независимо от того, какому процессу она принадлежала. Глобальные алгоритмы имеют несколько недостатков. Во-первых, они делают одни процессы чувствительными к поведению других процессов. Например, если один процесс в системе использует большое количество памяти, то все остальные приложения будут в результате ощущать сильное замедление из-за недостатка памяти. Во-вторых, некорректно работающее приложение может подорвать работу всей системы (если конечно в системе не предусмотрено ограничение на размер памяти, выделяемой процессу), пытаясь захватить все больше памяти. Поэтому в многозадачной системе лучше использовать более сложные, но эффективные локальные алгоритмы.

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

-1077. В качестве системы показателей качества управляемой вычислительной системы используются 4 показателя:

• уровень «накладных расходов»: средняя относительная величина суммарных дополнительных задержек задач в накопителе и в очереди;

• общая доля решенных задач за время функционирования системы в течение рабочего дня;

• «взвешенная» с учетом значимости каждого типа задачи доля решенных задач за время функционирования системы в течение рабочего дня;

• степень загрузки процессора - отношение суммарного времени решения задач во всех потоках к величине kxTmax.

8. Параметры планировщика ресурсов вычислительной системой подразделяются на 3 типа: долгосрочного, среднесрочного и краткосрочного управления. При этом общее количество параметров управления составляет N+1, где N - количество видов используемых ресурсов. Новой является предложенная технология взаимного перераспределения ресурсов - в процессе функционирования вычислительной системы периодически (при наличии сигнала о недостатке хотя бы одного из ресурсов) производится перераспределение свободных ресурсов между разными источниками для обеспечения пропорций, установленными параметрами долгосрочного управления.

9. Разработан и реализован алгоритм функционирования вычислительной системы, в котором учет неопределенных, в т.ч. - неблагоприятных, факторов моделируется розыгрышем совокупности случайных чисел, подчиненных показательному, усеченному нормальному и равномерному законам распределения. Параметры системы обновляются через малые интервалы («шаги») по времени; характерная величина шага в (3-5) раз меньше среднего промежутка времени между значимыми событиями; в рассматриваемом случае она составляет около 0,003 ед. времени при общем количестве шагов около 10 млн. за одну историю системы.

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

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

12. Определение оптимальных параметров планировщика ресурсов вычислительной системы должно осуществляться в результате применения оптимизирующей процедуры к целевой функции, сформированной на основе показателей качества системы. Задачу обоснования оптимальных (рациональных) параметров планировщика ресурсов целесообразно представить в виде задачи математического программирования с главным показателем качества.

-10913. В зависимости от используемого главного показателя качества данная оптимизационная задача может быть сформулирована как задача его минимизации или максимизации. Учитывая сложность рельефа целевой функции целесообразно использовать численные методы многопараметрической оптимизации первого порядка. Для рассматриваемого случая такие методы позволят получить решение с приемлемой точностью за 110-120 обращений к процедуре вычисления целевой функции.

14. Оценки возможного времени решения задачи математического программирования показали, что на современной вычислительной базе получение решения оптимизационной задачи невозможно по причине не методического, а технического свойства - недостаточным быстродействием современных вычислительных средств. В будущем, при повышении их производительности на 3 порядка, возможно получение решения за приемлемое время. При этом оказывается проще получить решение задачи максимизации - потребуется в 25-35 раз меньшее количество статистических испытаний.

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

16. Результаты расчетов средних ресурсных потребностей вычислительной системы при различных характеристиках потока поступающих на ее вход задач, показали, что динамика ресурсных требований подобна профилю интенсивности поступления задач, но смещена по времени примерно на 1,6 часа сторону больших значений времени. Кроме этого, ресурсные требования существенно зависят от доли изменяемого ресурса задач 2-го класса (счетные задачи) при их перемещении из счетно-решающего устройства в накопитель.

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Белоусов, Сергей Михайлович, 2006 год

1. Авен О.И., Турин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982.

2. Александров В. М. Приближенное решение задачи линейного быстродействия // Автоматика и телемеханика. 1998. ~ 12. С. 3-13.

3. Александров В. М. Численный метод решения задачи линейного быстродействия // Журнал вычислительной математики и математической физики. 1998. Т. 38. ~ 6. С. 918-931.

4. Баничук Н. В., Петров В. М., Черноусько Ф. JL Численное решение вариационных и краевых задач методом локальных вариаций // Журнал вычислительной математики и математической физики. 1966. Т. 6. ~ 6. С. 947-961.

5. Белман Р. Динамическое программирование. М.: Издательство иностранная литература, 1960.

6. Белоусов С.М. Математическая модель многопоточной системы массового обслуживания, управляемой планировщиком ресурсов // Вестник Новосибирского Государственного Университета. Серия: Информационные технологии, 2006 г., Том 4, Вып. 1, С. 14 - 26.

7. Белоусов С. М. «Об одной постановке задачи распределения ресурсов вычислительной системы» // Объединенный научный журнал 2005 г., № 14 (142), С. 53-57.

8. Белоусов С.М. Об одном подходе к эффективному распределению ресурсов вычислительной системы // Процессы и методы обработки информации. Сборник научных трудов. М.:МФТИ, 2005, с 58-67.

9. Белоусов С. М. «К вопросу об основных характеристиках и классификации операционных систем»// Объединенный научный журнал 2005 г., № 14 (142), С. 58-64.

10. Белоусов С. М., Протасов С. С., Тормасов А. Г. Использование виртуальных сред для предоставления услуг по размещению ресурсов в глобальной сети // Объединенный научный журнал 2004 г., № 24 (116), С. 74-78.

11. Белоусов С. М., Протасов С. С., Тормасов А. Г. Архитектура и особенности функционирования современных операционных систем // Объединенный научный журнал 2004 г., 24 (116), С. 78-83

12. Белоусов С. М., Протасов С. С., Тормасов А. Г. Прошлое, настоящее и будущее: развитие архитектуры и принципов создания операционных систем // Объединенный научный журнал 2004 г., №24 (116), С. 83-86.

13. Белоусов С. М., Протасов С. С. Использование виртуальных сред для повышения уровня утилизации ресурсов вычислительной системы (принята к публикации)

14. Белоусов С. М., Протасов С. С., Тормасов А.Г. Об одном методе балансировки нагрузки между серверами ассиметричной фермы // Электронный журнал "Исследовано в России", 4257, 10-31, 2004. http://zhurnal.gpi.ru/articles/2004/4257.pdf

15. БерзинЕ.А. Оптимальное распределение ресурсов и элементы синтеза систем. Под ред. Золотова Е.В. — М.: Советское радио, 1974.

16. Брайсон А., Хо Ю-Ши. Прикладная теория оптимального управления. М.: Мир, 1972.

17. Васильев О. В., Тятюшкин А. И. К численному решению задач линейного быстродействия // Дифференциальные и интегральные уравнения. Иркутск: Издательство Иркутского университета. 1973. Вып. 2. С. 57-69.

18. ВентцельЕ.С. Теория вероятностей. Изд.2-е — М.: Гос. издательство физико-математической литературы, 1962.

19. Вентцель Е.С., Овчаров JI.A. Теория вероятности и ее инженерные приложения. — М.: Наука, 1988.

20. Габасов Р., Кириллова Ф. М. Качественная теория оптимальных процессов. М.: Наука, 1971.

21. Гантмахер Р. Теория матриц. М.: Наука, 1966.

22. Гихман И.И., Скороход А.В., Ядренко М.Н. Теория вероятностей и математическая статистика. — Киев: Вища школа, 1979.

23. Гнеденко Б.В. и др. Приоритетные системы обслуживания. -М.: Изд-во МГУ, 1973.

24. Гнеденко Б.В. Курс теории вероятностей. Изд. 2-е — М.: Гос. издательство технико-теоретической литературы, 1954.

25. Головкин Б.А. Параллельные вычислительные системы. М.Наука, 1980.

26. Давыдов Э. Г. Исследование операций: Учебное пособие для студентов вузов. М.: Высш. шк., 1990. - 383 е.: ил.

27. Демьянов В. Ф., Рубинов А. М. Приближенные методы решения экстремальных задач. JL: Издательство Ленинградского государственного университета, 1968.

28. Джейсуол Н. Очереди с приоритетами. М.: Мир, 1973.

29. Евдокимов В.П., Маловицкий В.И., Семинишин Ю.А. и др. Моделирование систем сбора и обработки данных М.: Наука, 1983. - 128 с.

30. Иванов-Мусатов О.С. Теория вероятностей и математическая статистика. — М.: Наука, 1979.

31. Каган Б.М. Электронные машины и системы: Учебное пособие. 2-е изд., перераб. И доп. М.: Энергоатомиздат, 1985.

32. Карманов В. Г. Математическое программирование. М.: Наука, 1975.

33. Карманов В.Г. Математическое программирование. Изд. 2-е. — М: Наука, Главная редакция физико-математической литературы, 1980.

34. Киселев Ю. Н. Оптимальное управление. М.: Издательство Московского государственного университета, 1988.

35. Круглый 3.JL Алгоритмы расчета моделей структур вычислительных систем с различными классами заданий // Управляющие системы и машины. -1980.-№ 4 С. 73-79.

36. Моисеев Н.Н. "Математические задачи системного анализа". —М.: Наука, гл. ред. физ-мат. литературы, 1981.

37. Моисеев Н.Н., Столяров Ю.П., Столярова Е.М. Методы оптимизации — М., Наука, Главная редакция физико-математической литературы, 1978.

38. Мультипроцессорные системы и параллельные вычисления: Пер. с англ. / Под ред. Ф.Г. Энслоу. М.: Мир, 1976.

39. Олифер В., Олифер Н. Сетевые операционные системы. СПб., 2000. -512с.

40. Основы теории вычислительных систем: Учебное пособие / Под ред. С.А. Майорова. М.: Высшая школа, 1978.

41. Перегудов Ф.И., Тарасенко Ф.П. "Введение в системный анализ". —М.: Высшая школа, 1989.

42. Полак Э. Численные методы оптимизации. Единый подход. М.: Мир, 1974.

43. Поляк В. Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

44. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Сов. Радио, 1972.

45. Праневичус Г.И. Модели и методы исследования вычислительных систем. Вильнюс: Мокслас, 1982.

46. Рини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. Перев. с англ. В.В.Подиновского, М.Г.Гафта, В.С.Бабинцева под ред. И.Ф.Шахнова. — М: Радио и связь, 1981

47. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.

48. Смирнов В.И. Курс высшей математики. Том 1, изд. 23. — М: Наука, 1974.

49. Табак А., Куо Б. Оптимальное управление и математическое программирование. Пер. с англ. Мееровича Л.А. — М: Наука, главная ред. физико-математической литературы, 1975.

50. Теория прогнозирования и принятия решений. / Под ред. Саркисяна С.А. — М.: Высшая школа, 1977

51. Теория систем и методы системного анализа в управлении и связи /Под ред. Лазарева В.Г. и др. — М.: Радио и связь, 1983.

52. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1. М.: Мир, 1984.

53. Феррари Д. Оценка производительности вычислительных систем: Пер. с англ. М.: Мир, 1981.

54. Шрайбер Т.Дж. Моделирование на GPSS. Перевод с английского. М.: Машиностроение, 1980.

55. Pat. # 7099948. Virtual computing environment. Tormasov Alexander, Lunev Dennis, Beloussov Sergei, Protassov Stanislav, Pudgorodsky Yuri

56. Pat. # 7076633. Hosting service providing platform system and method. Tormasov Alexander, Lunev Dennis, Beloussov Serguei, Protassov Stanislav, Pudgorodsky Yuri

57. Pat. # 7047380. System and method for using file system snapshots for online data backup. Tormasov Alexander G., Beloussov Serguei M., Tsypliaev Maxim V., Lyadvinsky Maxim V.

58. Pat. # 6961868. Fault tolerant storage system and method using a network of servers. Tormasov Alexander, Khassine Mikhail, Beloussov Serguei, Protassov Stanislav

59. Pub. App. # 20060143501 System and method for rapid restoration of server from back up. Tormasov Alexander G.; Beloussov Serguei M.; Tsypliaev; Maxim V.; Lyadvinsky Maxim V.

60. Pub. App. # 20060089950 Common template file system tree. Tormasov Alexander; Beloussov Serguei; Protassov Stanislav; Pudgorodsky Yuri

61. Pub. App. # 20050066134 Method of implementation of data storage quota. Tormasov Alexander; Protassov Stanislav; Beloussov Serguei

62. Pub. App. # 20050027956 System and method for using file system snapshots for online data backup. Tormasov Alexander G.; Beloussov Serguei M.; Tsypliaev Maxim V.; Lyadvinsky Maxim V.

63. Pub. App. # 20020147815 Distributed network data storage system and method. Tormasov Alexander; Beloussov Sergei; Protassov Stanislav; Pudgorodsky Yuri

64. Pub. App. # 20020143906 Hosting service providing platform system and method. Tormasov Alexander; Lunev Dennis; Beloussov Serguei; Protassov Stanislav; Pudgorodsky Yuri

65. Pub. App. # 20020124072 Virtual computing environment 10 20020116659 Fault tolerant storage system and method. Tormasov Alexander ; Lunev Dennis; Beloussov Serguei; Protassov Stanislav; Pudgorodsky Yuri

66. Pub. App. # 20020116659 Fault tolerant storage system and method. Tormasov Alexander; Khassine Mikhail; Beloussov Serguei; Protassov Stanislav

67. Ali, H. and El-Rewini, H. On the intractability of task allocation in distributed systems. Parallel Processing Letters, 1994.

68. Allon, et al. July 23, 1996 United States Patent 5,539,883

69. B. Narahari, A. Youssef and H. Choi. Matching and Scheduling in a Generalized Optimal Selection Theory. Proceedings of the IEEE Heterogeneous Processing Workshop, pages 3-8,1994

70. Barak A. and La'adan O., The MOSIX Multicomputer Operating System for High Performance Cluster Computing, Journal of Future Generation Computer Systems, Vol. 13, No. 4-5, pp. 361-372, March 1998

71. Barak A., Guday S. and Wheeler R., The MOSIX Distributed Operating System, Load Balancing for UNIX. Lecture Notes in Computer Science, Vol. 672, Springer-Verlag, 1993

72. Bokhari, S. A shortest tree algorithm for optimal assignments across space and time in distributed processor system. IEEE Transaction on Software Engineering, SE-7 (6), 1981.

73. Brendel January 30, 2001 United States Patent 6,182,139

74. Brendel, et al. June 30,1998 United States Patent 5,774,660

75. C. Z. Xu and F. С. M. Lau. Analysis of the Generalized Dimension Exchange Method for Dynamic Load Balancing. Journal of Parallel Distributed Computing, vol. 16(4), pages 385-393,1992.

76. Chen, S. et al. A Selection Theory and Methodology for Heterogeneous Su-percomputing, Proc. Workshop on Heterogeneous Processing, IEEE CS Press, Los Alamitos, CA, Order No. 3532-02, 1993.

77. Coffman, E. G. Computer and Job-Shop Scheduling Theory, John Wiley, 1976.

78. Distributed Operating Systems by Andrew S. Tanenbaum, 1994 Prentice Hall; ISBN: 0132199084

79. El-Rewini, H. and AH, H. On considering communication in scheduling task graphs on parallel processors. Journal of Parallel Algorithms and Applications, 3,177-191,1994.

80. El-Rewini, H. and AH, H. Static scheduling of containing conditional branching in parallel programs. Journal of Parallel and Distributed Computing, 4154,1995.

81. El-Rewini, H. and Lewis, T. Scheduling parallel program tasks onto arbitrary target machines. Journal of Parallel and Distributed Computing, 138-153, 1990.

82. El-Rewini, H., Lewis, T. and AH, H. Task Scheduling in Parallel and Distributed Systems, Prentice-Hall, 1994.

83. Freund, R. and Siegel, H. Heterogeneous processing. IEEE Computer, 26, 1317,1993.

84. Fujii, M., Kasami, T. and Ninomiya, K. Optimal sequencing of two equivalent processors. SIAM Journal of Applied Mathematics, 17 (4), 1969.

85. Gabow, H. An almost linear algorithm for two-processor scheduling. Journal of ACM, 29 (3), 766-780, 1982.

86. Gerasoulis and Yang, T. A comparison of clustering heuristics for scheduling DAGs on multiprocessors. Journal of Parallel and Distributed Computing, 16 (4), 276-291, 1992.

87. H.S. Stone. Critical Load Factors in Two-Processor Distributed Systems. IEEE Transactions on Software Engineering, vol. SE-4(3), pages 254-258, May 1978.

88. L. M. Ni and P. K. McKinley. A Survey of Wormhole Routing Techniques in Direct Networks. IEEE Computer, vol. 26(2), pages 62-76, February 1993.

89. Lee, D. and Kim, M. Optimal task assignment in linear array networks. IEEE Transactions on Computers, 41 (7), 877-880, 1992.

90. Lewis, T. and El-Rewini, H. Parallax: A tool for parallel program scheduling. IEEE Parallel and Distributed Technology: Systems and Applications, 1 (2), 62-72,1993.

91. Lo, V. Heuristic algorithms for task assignment in distributed systems. IEEE Transactions on Computers, 37 (11), 1384-1397,1988.

92. M. H. Mickle and J. M. Paul. Load Balancing Using Heterogeneous Processors for Continuum Problems on a Mesh. Journal of Parallel and Distributed Computing, vol. 39, pages 66-73, 1996.

93. В. E. Карпов ,K. А. Коньков. Основы операционных систем. Курс лекций. Учебное пособие. М.: Интернет-университет информационных технологий, 2004. - 632 с.

94. Operating Systems: a design-oriented approach/Charles Crowley. Irwin. 1997. ISBN 0-256-15151-2

95. Papadimitriou, H. and Yannakakis, M. Scheduling interval-ordered tasks. SIAM Journal of Computing, 8,405-409,1979.

96. S. J. Kim and J. С Browne. A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures. Proceedings of the International Conference on Parallel Processing, vol. 3, pages 1-8,1988.

97. S. Ranka, Y. Won and S. Sahni. Programming a Hypercube Multicomputer. IEEE Software, pages 69-77, September, 1988.

98. Sarkar, V. Automatic partitioning of a program dependence graph into parallel tasks. IBM Journal Res. Develop., 35 (5/6), 1991.

99. Sethi, R. Scheduling graphs on two processors. SIAM Journal of Computing, 5 (1), 73-82, 1976.

100. Shen and W. Tsai. A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion. IEEE Transactions on Computers, vol. C-34(3), pages 197-203, March 1985.

101. Stone, H. Multiprocessor scheduling with the aid of network flow algorithms. IEEE Transaction on Software Engineering, 85-93,1977.

102. T. Yang and A. Gerasoulis. A Fast Static Scheduling Algorithm for DAG's on an Unbounded Number of Processors. Proceedings of IEEE Supercomput-ing'91, pages 633-642. Albuquerque, NM, November 199

103. Ullman, J. NP-complete scheduling problems. Journal of Computer and System Sciences, 10, 384-393, 1975.-117108. V. Sarkar. Partitioning and Scheduling Parallel Programs for Multiprocessors.