Эволюция алгоритмов планирования задач




Скачать 30.94 Kb.
НазваниеЭволюция алгоритмов планирования задач
Дата18.10.2012
Размер30.94 Kb.
ТипДокументы

УДК 004(06) Компьютерные системы и технологии


А.C. ЛАПУШКИН, А.Б. ВАВРЕНЮК

Московский инженерно-физический институт (государственный университет)


ЭВОЛЮЦИЯ АЛГОРИТМОВ ПЛАНИРОВАНИЯ ЗАДАЧ
В ОПЕРАЦИОННЫХ СИСТЕМАХ СЕМЕЙСТВА LINUX



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


Неотъемлемой частью любой многозадачной операционной системы (ОС) является планировщик. С точки зрения ОС центральный процессор наряду с памятью и устройствами ввода/вывода является общим ресурсом, разделяемым между всеми задачами системы. Именно планировщик осуществляет принятие решения, какая из задач должна получить в свое распоряжение процессор в данный момент времени и как долго она может занимать его.

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

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

Алгоритмы планирования Linux 2.2.x и 2.4.x схожи по своей реализации. Основное преимущество данных алгоритмов – простота логики. Все время работы планировщика делится на т.н. эпохи. В начале эпохи каждой задаче выделяется промежуток (квант) времени для работы. Эпоха считается завершенной, когда все активные задачи исчерпают свои кванты времени. По завершении эпохи приоритеты задач пересчитываются. Выбор очередной задачи осуществляется планировщиком путем последовательного сравнения приоритетов задач с целью поиска обладателя максимального приоритета. Недостаток планировщика кроется в его архитектуре – алгоритме планирования. Время выполнения алгоритма напрямую зависит от количества задач в системе. С ростом количества задач растут издержки на их планирование [1].

Алгоритм планирования Linux 2.6.x был полностью переработан Инго Молнаром (Ingo Molnar). Для поиска очередной для запуска задачи взамен неэффективной операции последовательного сравнения приоритетов применяется битовая строка приоритетов и процессорная операция поиска первого установленного бита в ней, выполняющаяся за фиксированное количество тактов. Таким образом, время планирования перестает зависеть от количества задач в системе.

Алгоритм планирования стал более гибким, способным подстроиться к работе как в среде серверных приложений, так и на desktop системе, в первом случае обеспечивая приемлемый уровень эффективной производительности, а во втором достаточную интерактивность системы для пользователя [2].

Наибольший интерес представляет идея внедрения генетических алгоритмов в процесс планирования задач впервые предложенная Джейком Мойланеном (Jake Moilanen). Идея заключается в кодировании политик планирования в виде строк хромосом. Первоначально создается популяция различных политик, и каждая из них апробируется в условиях текущей нагрузки. Далее выбираются наиболее удачные политики, к их хромосомам применяются операции взаимного скрещивания и мутации. В результате получается новая популяция, обладающая близкими к наиболее оптимальным признаками. Далее процесс повторяется. Постепенно культивируется политика планирования с наилучшими характеристиками. По своей сути алгоритм аналогичен процессу естественного отбора в природе [3].

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


Список литературы


  1. Ю. Вахалия. Unix изнутри. СПб.: Питер, 2003.

  2. Daniel P. Bovet, Marco Cesati. Understanding the Linux Kernel – O’Reilly, 2000.

  3. Интернет ресурс, посвященный возможности применения генетических алгоритмов в ОС Linux: http://www.jakem.net.




ISBN 5-7262-0710-6. НАУЧНАЯ СЕССИЯ МИФИ-2007. Том 12

Похожие:

Эволюция алгоритмов планирования задач iconАлгоритмы
Основы алгоритмизации. Понятие об алгоритме. Применение алгоритмов. Свойства алгоритмов. Типы алгоритмов: линейные, циклические,...
Эволюция алгоритмов планирования задач iconПостроение и анализ комбинаторных алгоритмов
Сложность в худшем случае. Сложность в среднем. Примеры задач и алгоритмов. Полиномиальные алгоритмы
Эволюция алгоритмов планирования задач iconСодержание, основные понятия
Понятие алгоритма, свойства алгоритмов. Использование алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...
Эволюция алгоритмов планирования задач iconЛабораторная работа №1 «Алгоритмы»
Цель: получение базовых навыков предпрограммирования, изучение видов и свойств алгоритмов, изучение способов составления алгоритмов...
Эволюция алгоритмов планирования задач iconКомплекс программ для оценки эффективности алгоритмов решения нелинейных навигационных задач фильтрации
Разработка такого комплекса позволит существенно облегчить процесс синтеза и анализа точности при проектировании алгоритмов решения...
Эволюция алгоритмов планирования задач iconБилет №4
Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Способы описания алгоритмов....
Эволюция алгоритмов планирования задач iconРешение задач по физике повышенной сложности
Курс направлен на отработку и закрепление умений решения задач, выработке алгоритмов, овладение методами решения задач повышенной...
Эволюция алгоритмов планирования задач iconПлан-конспект урока на тему "Алгоритм. Свойства алгоритмов. Виды алгоритмов и формы записи алгоритмов"
...
Эволюция алгоритмов планирования задач iconРабочая программа лекционного курса
Задача курса состоит в выработке у студентов навыков использования структур данных и методов разработки алгоритмов на примере классических...
Эволюция алгоритмов планирования задач iconПрограммные средства реализации ассоциативного планирования
Рассмотрены критерии отбора стереотипов для получения эффективного плана. Приведены решения интеллектуальных многошаговых задач,...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница