Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Воронежский государственный лесотехнический университет имени Г.Ф. Морозова

Механический факультет

«Информационные системы и технологии»

Курсовая работа

по дисциплине «Операционные системы»

На тему: Сравнение алгоритмов планирования ввода-вывода в ОС на базе ядра GNU/Linux и ОС семейства Windows

Студент ИС2-151-ОБ группы

Белов Семён Вадимович

Руководитель, доц.

Соловей Денис Евгеньевич

Воронеж 2018



Задание

операционный windows linux коммерциализация

на курсовую работу по дисциплине «Операционные системы»

1. Тема курсовой работы

Сравнение алгоритмов планирования ввода-вывода в ОС на базе ядра GNU/Linux и ОС семейства Windows

2. Технические условия выполнения

Работа выполнена на ОС Linux

Руководитель курсовой работы доцент Соловей Д.Е.



Оглавление

Введение

1. Обзорная часть

2. Теоретическая часть

3. Практическая часть

Заключение

Библиографический список

Приложение



Введение

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

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

Планировщик ввода/вывода отвечает за распределение дисковых операций по процессам. В ранних ядрах Linux (как минимум в ядре 2.4) существовал только один планировщик -- Linus Elevator. Он был слишком примитивным, и поэтому в ядре 2.6 появились еще три планировщика, часть из которых ныне уже ушла в небытие. Таким образом, сейчас в ядре существует три планировщика, а в ближайшее время, возможно, прибавится еще и четвертый

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



1. Обзорная часть

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

Первые версии UNIX были написаны на Ассеблере, затем система была переписана на СИ. Это дало системе уникальную переносимость. На PC UNIX был портирован, а точнее заново написан (Linux) сразу, как только развитие PC, а точнее выпуск PC на процессоре i386, позволило это сделать.

В 1985 году стартовал проект POSIX. Это стандарт на интерфейсы UNIX-подобных ОС. Во многом благодаря наличию такого стандарта, так быстро смог появится на свет и достигнуть зрелости Linux -- свободная воплощение UNIX.

Развитие интернета с самого начала и до нашего времени неразрывно связано с серверами под управлением ОС UNIX. Сначала с коммерческими, а теперь все больше и больше со свободными.

С точки зрения коммерциализации развитие UNIX можно разделить на три этапа.

Некоммерческое распространение в университетах.

Распространение коммерческих UNIX систем.

Появление свободных реализаций (Linux, FreeBSD) и вытеснение коммерческих систем (настоящий момент).

До появления системы X Window System UNIX была системой с текстовым интерфейсом, затем добавился графический, но традиционно текстовый интерфейс сохраняет важное значение.

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

Фирменной чертой всех UNIX-подобных ОС была и остается надежность.

С точки зрения пользователя UNIX устроен так:

Ядро. Работает с устройствами, управляет памятью и процессами.

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

Графическая подсистема Xwindow. Запускается как процесс в системе.

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

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

Система передачи графического окна приложения на другой компьютер. Позволяет запустив приложение на одном компьютере, управлять им с другого компьютера, через окно приложения, передаваемое на этот другой компьютер. Количество сессий ограничено ресурсами компьютеров.

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

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

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

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

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

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

Первой ОС из этого семейства была DOS. Может показаться, что DOS собственно имеет косвенное отношение к обсуждаемому предмету. Но, многие традиции, база пользователей и разработчиков, их привычки, идут именно оттуда.

DOS была однозадачной однопользовательской операционной системой с текстовым интерфейсом. Первая версия Windows представляла собой нечто, негодное для работы и распространения не получила. Работать стало в Windows стало возможно, начиная с версии 3. В версии Windows For Workgroups 3.1 появилась возможность работы с сетью. Winodws серии 3 представляли собой запускаемую поверх DOS систему. Отличались невысокой надежностью.

В 1995 годы вышла новая версия -- Windows 95. Код частично был 32 разрядным, частично 16 разрядным, встроенная сеть. По сравнению с Windows серии 3 это был серьезный шаг вперед. Повысилась надежность, но до надежности UNIX-подобных ОС было еще далеко. В качестве рабочей станции с натяжкой конечно, надежности хватало, в качестве сервера, нет. Позже были выпущены еще две ОС этой линии, Windows 98 и Windows Me. После этого линия была закрыта.

В 1993 году вышла новая версия -- Windows NT 3.1. Это уже была полностью 32 разрядная система. Разработана она была с нуля, для ее разработки были наняты известные специалисты. Были внедрены новые концепции. Это подняло надежность почти до уровня надежности UNIX-подобных систем. Эта ОС уже могла работать в качестве сервера. Продолжение этой линии, операционные системы Windows 2000, Windows XP и Windows Vista.

ОС линии NT были многозадачными, начиная с Windows XP появилась и возможность работать нескольким пользователям, хотя и более ограниченная, и гораздо менее удобная, чем у UNIX-подобных ОС.

Ядро. Работает с устройствами, управляет памятью и процессами, управляет графической подсистемой.

Графическая подсистема. Обеспечивает интерфейс с пользователем. Приоритетная система для пользовательского интерфейса.

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

Система удаленного доступа. Появилась впервые, как встроенная в систему, в Windows NT Server 4.0. До этого были только продукты других фирм. В связи с тем, что запускается полноценная графическая сессия, кушает очень много ресурсов. Наличие системы удаленного доступа и количество одновременных сессий может вообще отсутствовать или быть ограничено в разных версиях из коммерческих соображений.

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

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

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

Конечно, в обоих системах не доминирует свой подход на 100 процентов. Как в Windows есть возможность пользоваться текстовой консолью и создавать .bat файлы, так и в UNIX есть большой набор программ, со свойствами присущими скорее "тостерному" подходу. И все таки описанная разница в подходах есть и она достаточно ярко выражена.

2. Теоретическая часть

1.1 Планирование процессов ввода-вывода на базе ядра ОС Windows Процессы Windows NT имеют следующие характерные свойства:

Процессы Windows NT реализованы в форме объектов, и доступ к ним осуществляется посредством службы объектов.

Процесс Windows NT имеет многонитевую организацию.

Как объекты-процессы, так и объекты-нити имеют встроенные средства синхронизации.

Менеджер процессов Windows NT не поддерживает между процессами отношений типа "родитель-потомок".

В любой системе понятие "процесс" включает следующее:

исполняемый код,

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

ресурсы системы, такие как файлы, семафоры и т.п., которые назначены процессу операционной системой.

хотя бы одну выполняемую нить.

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

В Windows NT процесс - это просто объект, создаваемый и уничтожаемый менеджером объектов. Объект-процесс, как и другие объекты, содержит заголовок, который создает и инициализирует менеджер объектов. Менеджер процессов определяет атрибуты, хранимые в теле объекта-процесса, а также обеспечивает системный сервис, который восстанавливает и изменяет эти атрибуты.

В число атрибутов тела объекта-процесса входят:

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

Токен доступа - исполняемый объект, содержащий информацию о безопасности.

Базовый приоритет - основа для исполнительного приоритета нитей процесса.

Процессорная совместимость - набор процессоров, на которых могут выполняться нити процесса.

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

Время исполнения - общее количество времени, в течение которого выполняются все нити процесса.

Объект-нить имеет следующие атрибуты тела:

Идентификатор клиента - уникальное значение, которое идентифицирует нить при ее обращении к серверу.

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

Динамический приоритет - значение приоритета нити в данный момент.

Базовый приоритет - нижний предел динамического приоритета нити.

Процессорная совместимость нитей - перечень типов процессоров, на которых может выполняться нить.

Время выполнения нити - суммарное время выполнения нити в пользовательском режиме и в режиме ядра, накопленное за период существования нити.

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

Счетчик приостановок - текущее количество приостановок выполнения нити.

Как видно из перечня, многие атрибуты объекта-нити аналогичны атрибутам объекта-процесса. Весьма сходны и сервисные функции, которые могут быть выполнены над объектами-процессами и объектами-нитями: создание, открытие, завершение, приостановка, запрос и установка информации, запрос и установка контекста и другие функции.

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

В ОС Windows NT нить в ходе своего существования может иметь одно из шести состояний (рисунок 1.3). Жизненный цикл нити начинается в тот момент, когда программа создает новую нить. Запрос передается NT executive, менеджер процессов выделяет память для объекта-нити и обращается к ядру, чтобы инициализировать объект-нить ядра. После инициализации нить проходит через следующие состояния:

Рис. 1 Граф состояний нити

Готовность. При поиске нити на выполнение диспетчер просматривает только нити, находящиеся в состоянии готовности, у которых есть все для выполнения, но не хватает только процессора.

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

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

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

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

Завершение. Когда выполнение нити закончилось, она входит в состояние завершения. Находясь в этом состоянии, нить может быть либо удалена, либо не удалена. Это зависит от алгоритма работы менеджера объектов, в соответствии с которым он и решает, когда удалять объект. Если executive имеет указатель на объект-нить, то она может быть инициализирована и использована снова.

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

Windows NT поддерживает 32 уровня приоритетов, разделенных на два класса - класс реального времени и класс переменных приоритетов. Нити реального времени, приоритеты которых находятся в диапазоне от 16 до 31, являются более приоритетными процессами и используются для выполнения задач, критичных ко времени.

Каждый раз, когда необходимо выбрать нить для выполнения, диспетчер прежде всего просматривает очередь готовых нитей реального времени и обращается к другим нитям, только когда очередь нитей реального времени пуста. Большинство нитей в системе попадают в класс нитей с переменными приоритетами, диапазон приоритетов которых от 0 до 15. Этот класс имеет название "переменные приоритеты" потому, что диспетчер настраивает систему, выбирая (понижая или повышая) приоритеты нитей этого класса.

Алгоритм планирования нитей в Windows NT объединяет в себе обе базовых концепции - квантование и приоритеты. Как и во всех других алгоритмах, основанных наквантовании, каждой нити назначается квант, в течение которого она может выполняться. Нить освобождает процессор, если: блокируется, уходя в состояние ожидания; завершается; исчерпан квант; в очереди готовых появляется более приоритетная нить.

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

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

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

1.2 Планирование процессов ввода-вывода на базе ядра ОС Linux NOOP -- наиболее простой планировщик. Он банально помещает все запросы в очередь FIFO и исполняет их вне зависимости от того, пытаются ли приложения читать или писать. Планировщик этот, тем не менее, пытается объединять однотипные запросы для сокращения операций ввода/вывода.

CFQ был разработан в 2003 году. Заключается его алгоритм в следующем. Каждому процессу назначается своя очередь запросов ввода/вывода. Каждой очереди затем присваивается квант времени. Планировщик же циклически обходит все процессы и обслуживает каждый из них, пока не закончится очередь либо не истечет заданный квант времени. Если очередь закончилась раньше, чем истек выделенный для нее квант времени, планировщик подождет (по умолчанию 10 мс) и, в случае напрасного ожидания, перейдет к следующей очереди. Отмечу, что в рамках каждой очереди чтение имеет приоритет над записью.

Deadline в настоящее время является стандартным планировщиком, был разработан в 2002 году. В основе его работы, как это ясно из названия, лежит предельный срок выполнения -- то есть планировщик пытается выполнить запрос в указанное время. В дополнение к обычной отсортированной очереди, которая появилась еще в Linus Elevator, в нем есть еще две очереди -- на чтение и на запись. Чтение опять же более приоритетно, чем запись. Кроме того, запросы объединяются в пакеты. Пакетом называется последовательность запросов на чтение либо на запись, которая идет в сторону б?льших секторов («алгоритм лифта»). После его обработки планировщик смотрит, есть ли запросы на запись, которые не обслуживались длительное время, и в зависимости от этого решает, создавать ли пакет на чтение либо же на запись.

BFQ (Budget Fair Queueing) -- относительно новый планировщик. Базируется на CFQ. Если не вдаваться в технические подробности, каждой очереди (которая, как и в CFQ, назначается попроцессно) выделяется свой «бюджет», и, если процесс интенсивно работает с диском, данный «бюджет» увеличивается.

Но, как говорится, не все грибочки одинаково полезны -- планировщик для домашнего компьютера (который мы и попытаемся выбрать в статье) отличается от планировщика для сервера.

В FreeBSD имеется фреймворк (GEOM scheduler framework), позволяющий создавать планировщики ввода/вывода. На текущий момент, однако, на нем базируется только планировщик rr.



3. Практическая часть

Первым делом скачаем ядро и наложим патч BFQ (на момент написания статьи существовал для ядер по версию 3.13 включительно):

$ RELEASE=3.13.0-v7r2

$ git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git linux

$ cd linux

$ git checkout -b stable-3.13 v3.13.7

$ wget -nd --no-parent --level 1 -r -R "*.html*" --reject $RELEASE http://algo.ing.unimo.it/people/paolo/disk_sched/patches/$RELEASE

$ patch -p1 < ./0001-block-cgroups-kconfig-build-bits-for-BFQ-v7r2-3.13.patch

$ patch -p1 < ./0002-block-introduce-the-BFQ-v7r2-I-O-sched-for-3.13.patch

$ patch -p1 < ./0003-block-bfq-add-Early-Queue-Merge-EQM-to-BFQ-v7r2-for-3.13.0.patch

$ cp /boot/config-`uname -r` ./.config

Затем включим этот планировщик в Enable the block layer -> IO Schedulers (планировщик по умолчанию можно оставить стандартный -- все равно их можно переключать как во время работы, так и используя опции ядра) и скомпилируем ядро:

$ fakeroot make-kpkg --initrd --append-to-version=-my kernel_image kernel_headers

Перед этим нужно убедиться, что в файле /etc/kernel-pkg.conf стоит многопоточная сборка (параметр CONCURRENCY_LEVEL в идеале должен быть равен количеству ядер процессора плюс один).



Рис.2 Включение планировщика BFQ в menuconfig

Следом же устанавливаем получившиеся пакеты:

$ sudo dpkg -i ../linux-image-3.13.7-my+_3.13.7-my+-10.00.Custom_amd64.deb ../linux-headers-3.13.7-my+_3.13.7-my+-10.00.Custom_amd64.deb

И перезагружаемся.

Помимо ядра, нужно установить некоторые пакеты для собственно бенчмаркинга:

$ sudo apt-get install hdparm bonnie++



Тестирование

Рис.3 Установка Bonnie++

Как правило, планировщики не требуют тонкой подстройки. Однако если тебе захочется поэкспериментировать -- такая возможность у нас есть. Рассмотрим некоторые параметры подстройки BFQ, находящиеся (в моем случае) в каталоге /sys/block/sda/queue/iosched:

slice_idle -- время ожидания поступления запросов (в миллисекундах). По умолчанию 8;

quantum -- число запросов ввода/вывода, передаваемых дисковому контроллеру за один раз (тем самым ограничивая длину очереди). Нужно соблюдать осторожность при его увеличении, поскольку при высокой нагрузке система может начать тормозить. По умолчанию 4;

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

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

Прежде чем приступить к проведению бенчмарков, нужно рассказать о тестовом стенде. Железо: материнская плата ASUS Sabertooth 990FX R2.0, 16 Гб RAM, Seagate ST3000DM001-1CH166. ПО: Xubuntu 13.10 x64 с ядром 3.13.7. Также в моем случае имело смысл создать отдельный раздел как минимум вдвое большего объема, чем вся доступная оперативная память, что я и сделал, создав таковой в размере 35 Гб с файловой системой ext4. Сначала удостоверимся, что текущий планировщик для диска -- Deadline, для чего наберем следующую команду:

$ cat /sys/block/sda/queue/scheduler

Текущий планировщик выделяется квадратными скобками.

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

# hdparm -tT /dev/sda

Для более точного результата лучше запускать эту команду три -- пять раз.

Следующим бенчмарком будет тест с помощью команды dd. Этот тест тоже достаточно полезен для оценки производительности ввода/вывода, хоть и кажется примитивным.

# cd /media/rom/benchmarking

# time dd if=/dev/zero of=./benchfile bs=1M count=19900 conv=fdatasync,notrunc

Затем нужно будет очистить кеш, записав цифру 3 в файл /proc/sys/vm/drop_caches. Запись этой цифры в данный файл очищает как страничный кеш, так и кеш инод с dentry. Лишь после очистки можно будет запустить вторую часть теста:

# time dd if=./benchfile of=/dev/null bs=1M count=19900

Как и в случае с hdparm, обе части теста лучше запустить несколько раз.

Переходим к очередному тесту -- им у нас будет распаковка архива с ядром. Скачиваем его и запускаем распаковку (опять же три -- пять раз):

# wget https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.13.7.tar.xz

# time tar xJf linux-3.13.7.tar.xz

Следующий тест будет сделан с помощью утилиты Bonnie++, о которой стоит рассказать подробнее. Это крайне гибкий набор бенчмарков для тестирования производительности ввода/вывода. Операции с файлами, к сожалению, не сводятся только к последовательному чтению/записи одного файла или к распаковке архива, поэтому приведенные тесты не дают однозначного результата для всех ситуаций. Bonnie++ же, хоть и является синтетическим тестом, более реалистично симулирует обращения к подсистеме ввода/вывода. Так, в число тестов входит симуляция работы СУБД -- в данном случае создается файл (либо файлы, если указан размер больший, чем 1 Гб) и производится как последовательное, так и рандомное чтение/запись, при этом чтение в несколько потоков. Помимо этого теста есть еще тест на создание/изменение/удаление тысяч маленьких файлов. Опции у данного приложения следующие:

-d -- каталог для работы программы;

-s -- размер файла в мегабайтах для первого теста (симуляция работы СУБД). Как я уже сказал, если размер будет указан больший, чем 1 Гб, файлов будет больше одного;

-n -- количество файлов для второго теста (симуляция работы Squid или какого-нибудь сервера электронной почты, использующего для хранения писем файлы). Формат аргумента таков: num:max_size:min_size:num_dirs, где num -- количество файлов, кратное 1024, max_size и min_size -- соответственно, максимальный и минимальный размер в байтах для создаваемых файлов (по умолчанию оба этих размера равны нулю, если же их установить, размер файлов будет задаваться рандомно), а num_dirs -- количество каталогов, в которых файлы будут размещаться;

-x -- количество проходов тестов;

-q -- «тихий» режим. Кроме результатов теста и ошибок, ничего не выводится;

-u -- пользователь, под которым запускать тесты. Поскольку они сильно нагружают, пользователь root не рекомендуется -- во избежание всяческих ошибок.

Итоговые команды будут следующими:

# mkdir rom && chown rom:rom rom

$ bonnie++ -d ./rom -n 115:25381:0:27 -x 5 -q > ~/bonnie_out_deadline.csv

То есть запускаем пять проходов тестов в текущей директории с количеством файлов 115*1024, максимальным размером 25 381 байт, количеством каталогов 27 в «тихом» режиме. Затем нужно преобразовать этот самый CSV в удобочитаемый вид, для чего в составе пакета есть утилиты -- можно преобразовывать как в txt, так и в HTML:

$ cat ~/bonnie_out_deadline.csv |bon_csv2html > ~/bonnie_out_deadline.html

Напомню, что данные тесты нужно проводить на всех планировщиках, а не только на текущем. Для их переключения есть два способа. Первый способ -- использовать параметр загрузки ядра elevator. При этом нужно будет редактировать файл /etc/default/grub и обновлять загрузочный конфиг GRUB. Второй способ не требует перезагрузки и состоит в указании планировщика через sysfs. Например, для указания планировщика CFQ на устройстве /dev/sda достаточно следующей команды:

# echo cfq > /sys/block/sda/queue/scheduler

Лично мне в конечном итоге оказалось проще написать скрипт, который запускает по пять проходов каждого теста (за исключением Bonnie++ -- в нем указывается параметр -x) для каждого планировщика. Посмотрим же, что у нас получилось.

Рис.4 Скрипт для Benchmark

BFQ не приняли в основную ветку ядра, несмотря на позитивный отклик общественности. Причиной тому послужили замечания Дженса Аксбо (Jens Axboe). С одной стороны, он был обеспокоен сложностью движка планировщика, сетовал на то, что эта сложность обернется проблемами с поддержкой кода, если его добавят в ядро. С другой -- он был убежден, что в Linux должен быть только один главный планировщик ввода/вывода. Им был (и есть) CFQ.

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

Тем временем я наткнулся на одну занимательную ветку LKML по теме ввода/вывода. В ней обсуждалось время старта некоторых популярных приложений, таких как Firefox и терминал. Я был поражен, насколько оно может быть мало. По сути, такое время достигалось только при последовательном чтении соответствующего бинарного файла. Я вдохновился этой идеей и придумал новую фичу для планировщика: необходимо определять и давать привилегии интерактивным приложениям. После добавления этого и некоторых других незначительных улучшений я представил BFQ-v1 в июле 2010-го.

С этого момента BFQ начал набирать обороты: за прошедшие годы некоторые модифицированные Linux-ядра, Android-ядра, дистрибутивы Linux приняли BFQ в качестве планировщика по умолчанию или дополнительного планировщика (pf-kernel, многие ядра для Android, CyanogenMod, Sabayon, Gentoo Linux, Arch Linux, OpenMandriva, Rosa, ныне Manjaro). Кроме того, по моим данным, в течение последних нескольких лет каждый день планировщик скачивают несколько десятков пользователей разных дистрибутивов.

Между тем я продолжал добавлять новые функции и усовершенствования, например эвристические методы распознавания интерактивных приложений. Я добавил поддержку новых характеристик жестких дисков, например NCQ, а также оптимизировал работу с SSD. К счастью, в этой работе мне помогали такие хорошие люди, как Франческо Аллертсен (Francesco Allertsen), Мауро Андреолини (Mauro Andreolini) и особенно Арианна Аванцини (Arianna Avanzini). За несколько лет она внесла большой вклад в проект BFQ, разработала новые решения и подготовила патчи для множеств версий ядра.

Все расширения для правильной обработки новых устройств, которые Арианна и я добавили в BFQ, были до этого добавлены и в CFQ. Вместе с этим в CFQ появлялись некоторые другие полезные функции. Мы не только портируем все эти функции в BFQ, но и по возможности дорабатываем их для улучшения пропускной способности, времени отклика и быстроты исполнения. Так, нами был разработан унифицированный механизм обработки ввода/вывода QEMU для достижения высоких показателей пропускной способности.

Поддерживать такую высокую скорость разработки совсем не легко. Без поддержки Арианны проект, скорее всего, пришлось бы закрыть. Однако с выходом версии v7r3 мы в конце концов сделали это: теперь BFQ поддерживает весь спектр популярных устройств для хранения информации. Кроме этого, весь функционал, который я планировал реализовать, теперь работает стабильно. Наконец-то код выглядит зрелым и достаточно стройным.

Вот почему я думаю, что сейчас BFQ готов для представления в LKML. С этой целью мы уже подготовили патчсет для ревью. Но, прежде чем приступить к добавлению в основную ветку, нам нужно закончить тестирование версии v7r3 и выпустить релиз. Надеюсь, мы сможем это сделать в ближайшую неделю.

Паоло Валенте (Paolo Valente), основатель планировщика BFQ

Поскольку написание статьи связано с планировщиком BFQ, сосредоточимся именно на нем.

Запись с помощью dd у меня заняла в среднем 137,71 с, что, конечно, немного больше, чем при использовании планировщика Deadline (в среднем 136,89 с), но меньше, чем при использовании других планировщиков, -- например, при сравнении с CFQ BFQ опережает его почти на 4 с.

Чтение же с помощью dd столь значительной разницы не показало. Тем не менее в этом тесте BFQ впереди планеты всей, а CFQ опять аутсайдер.

Тесты с помощью hdparm (чтение как из кеша, так и из дискового буфера) по неизвестным причинам вывели на первое место планировщик Deadline. Впрочем, полагаться на результат именно этого теста особого смысла нет -- выглядит он слишком уж синтетическим.

Замер общего времени выполнения распаковки ядра с помощью команды time снова вывел BFQ на второе место -- хотя и этот тест выглядит не менее синтетическим, чем предыдущий.



Рис. 5 Таблица результатов моих собственных тестов

А теперь перейдем к результатам Bonnie++. Результатов там много, но я покажу только самые основные. Рассматривать я буду исключительно максимальную задержку для одной операции (опять же усредненную). При использовании функции putc() задержка у нашего кандидата на включение в ядро составляет 12 901 мкс, что выводит его на первое место. То же самое можно сказать и про запись блока -- при данном тесте BFQ вырывается далеко вперед. А вот при чтении блока выигрывает CFQ с его 9082,6 мкс, BFQ же в этом тесте (как и в тесте на перезапись блока) стоит на втором месте. В тесте последовательного создания файлов BFQ на втором месте, зато в тестах рандомного создания/удаления он вновь лидирует.

Рис.6 Таблица результатов (среднее значение задержки) для Bonnie++

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



Заключение

В ходе проделанной курсовой работы были изучены основы работы планировщика процессов, изучены алгоритмы планирования процессов в операционных системах на базе ядра Linux, был произведён анализ работы планировщика процессов, разобраны основные программные функции, реализующие алгоритм



Библиографический список

1. Замятин, А. В. Операционные системы. Теория и практика [Текст] : учеб. пособие / А. В. Замятин ; М-во образования и науки РФ, Гос. образоват. учреждение высш. проф. образования "Нац. исслед. Том. политехн. ун-т". - Томск : ТПУ, 2011. - 281 с.

2. Иртегов, Д. В. Введение в операционные системы [Текст] : рек. УМО вузов по унив. политехн. образованию в качестве учеб. пособия для студентов, обучающихся по направлению 230100 "Информатика и выч. техника" / Д. В. Иртегов ; - 2-е изд., [перераб. и доп.]. - СПб. : БХВ-Петербург, 2008.

3. Синицын, С. В. Операционные системы [Текст] : рек. УМО по образованию в обл. прикладной информатики в качестве учеб. для студентов высш. учеб. заведений, обучающихся по специальности "Прикладная информатика (по областям)" и другим экон. специальностям / С. В. Синицын, А. В. Батаев, Н. Ю. Налютин ; - М. : Академия, 2010. - 304 с.

4. Стандарт оформления студенческих работ [Текст] / Д.Н. Афоничев, Д.Ю. Харитонов, Н.Н.Харченко, А.С.Черных; М-во образования и науки Рос. Федерации, Гос. Образоват. Учреждение высш. Проф. Образования «Воронеж. гос. лесотехн. акад.». - Воронеж, 2011. - 59 с. - Электронная версия в ЭБС ВГЛТА Макрообъект : 1556.

5. Девис, У. Операционные системы [Текст] = Operating systems: A systematic view : функциональный подход / У. Девис ; пер. с англ. В. В. Фролова. - М. : Мир, 1980. - 436 с.



Приложение

$ RELEASE=3.13.0-v7r2

$ git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git linux

$ cd linux

$ git checkout -b stable-3.13 v3.13.7

$ wget -nd --no-parent --level 1 -r -R "*.html*" --reject $RELEASE http://algo.ing.unimo.it/people/paolo/disk_sched/patches/$RELEASE

$ patch -p1 < ./0001-block-cgroups-kconfig-build-bits-for-BFQ-v7r2-3.13.patch

$ patch -p1 < ./0002-block-introduce-the-BFQ-v7r2-I-O-sched-for-3.13.patch

$ patch -p1 < ./0003-block-bfq-add-Early-Queue-Merge-EQM-to-BFQ-v7r2-for-3.13.0.patch

$ cp /boot/config-`uname -r` ./.config

Enable the block layer -> IO Schedulers

$ fakeroot make-kpkg --initrd --append-to-version=-my kernel_image kernel_headers

$ sudo dpkg -i ../linux-image-3.13.7-my+_3.13.7-my+-10.00.Custom_amd64.deb ../linux-headers-3.13.7-my+_3.13.7-my+-10.00.Custom_amd64.deb

$ sudo apt-get install hdparm bonnie++

$ cat /sys/block/sda/queue/scheduler

# hdparm -tT /dev/sda

# cd /media/rom/benchmarking

# time dd if=/dev/zero of=./benchfile bs=1M count=19900 conv=fdatasync,notrunc

# time dd if=./benchfile of=/dev/null bs=1M count=19900

# wget https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.13.7.tar.xz

# time tar xJf linux-3.13.7.tar.xz

# mkdir rom && chown rom:rom rom

$ bonnie++ -d ./rom -n 115:25381:0:27 -x 5 -q > ~/bonnie_out_deadline.csv

$ cat ~/bonnie_out_deadline.csv |bon_csv2html > ~/bonnie_out_deadline.html

# echo cfq > /sys/block/sda/queue/scheduler

# cd /media/rom/benchmarking

# time dd if=/dev/zero of=./benchfile bs=1M count=19900 conv=fdatasync,notrunc

# time dd if=./benchfile of=/dev/null bs=1M count=19900

# wget https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.13.7.tar.xz

# time tar xJf linux-3.13.7.tar.xz

# mkdir rom && chown rom:rom rom

$ bonnie++ -d ./rom -n 115:25381:0:27 -x 5 -q > ~/bonnie_out_deadline.csv

# echo cfq > /sys/block/sda/queue/scheduler

Размещено на Allbest.ru