Министерство образования и науки Российской Федерации
Московский физико-технический институт (государственный университет)
Факультет управления и прикладной математики
Кафедра Теоретической и прикладной информатики
(Направление подготовки 010900 «Прикладные математика и физика», Магистерская программа 010956 «Математические и информационные технологии»)
Выпускная квалификационная работа
Балансировка нагрузки высокопроизводительного кластера
студента 873 группы
Петрова Дмитрия Игоревича
Научный руководитель
д.ф.-м.н. Тормасов А.Г.
г. Долгопрудный 2014
Оглавление
Введение
виртуальный память оптимизация программный
Проблема распределения нагрузки в высокопроизводительных вычислительных систем стоит весьма остро уже несколько десятилетий. Особенно интересна данная задача в применении к современным виртуальным сервисам. Переход от реального железа к виртуализованному позволяет решать сразу несколько важнейших задач. Нет необходимости в физической машине, её техническому обслуживанию, обеспечению электричеством, охлаждения. Снижается плата за аренду площадей под дата-центры. Кроме того, в рамках одной реальной машины («хоста») могут сосуществовать несколько машин на различных операционных систем. [5]
Следующим шагом в виртуализационных технологиях является переход к так называемой контейнерной виртуализации. При таком подходе снижаются накладные расходы на непосредственно эмуляцию аппаратного обеспечения за счёт ресурсов исключительно хоста. Вместо полноценных «тяжёловесных» виртуальных машин в рамках основной системы существуют изолированные друг от друга контейнеры, которым достаточно только ядра хостовой системы.
При такой организации кластера естественным преимуществом является простота перемещения контейнеров между хостовыми системами, расположенными на различных вычислительных узлах, но объединённых в общую сеть. Как следствие, возникает проблема балансировки нагрузки виртуального кластера. В данной работе рассматриваются основные способы организации кластера, метрики его загруженности и способы балансировки.
Понятие о виртуальной памяти
Прежде чем рассматривать вопросы виртуализации и балансировки стоит рассмотреть абстракцию «виртуальная память», принятую во многих современных операционных системах. Прежде всего, мы рассматриваем семейство GNU/Linux, как одну из самых распространённых хостовых ОС. Организация этой подсистемы имеет непосредственное отношение к вопросам балансировки.
Физическая память
Машинная память, реализованная в виде микросхем, называется физической памятью. Распространены так же термины оперативная, главная, основная память. Она имеет линейную структуру в виде последовательных ячеек размером в один байт.
Наравне с центральным процессом, память является важнейшей частью фон-неймановской архитектуры, начиная с 40-х годов XX века. Имеет иерархическую структуру: начиная с процессорных регистров (самая быстрая и дорогая память), один или более уровней кэшей, и заканчивая, собственно, оперативной памятью. Часто эту иерархию продолжают и до внешних запоминающих устройств, как-то: жёсткие диски, флэш-память, компакт-диски и т.п. (см. рис. 1)
Рис. 1. Иерархия памяти.
В дальнейшем под этим термином будем понимать динамическую память с произвольным доступом (DRAM), -- которая в настоящее время используется в качестве ОЗУ персонального компьютера.
Задачей компьютерной памяти является хранение в своих ячейках состояния внешнего воздействия, запись информации. Эти ячейки могут фиксировать самые разнообразные физические воздействия (см. ниже). Они функционально аналогичны обычному электромеханическому переключателю и информация в них записывается в виде двух чётко различимых состояний -- 0 и 1 («выключено»/«включено»). Специальные механизмы обеспечивают доступ (считывание, произвольное или последовательное) к состоянию этих ячеек.
Процессор взаимодействует с памятью, выполняя машинные команды; к примеру, MOV (загрузка данных из ОЗУ в регистр или наоборот).
Виртуальная память
Хотя физическая память имеет довольно простую структуру, а именно, пронумерованный массив данных, в многозадачных ОС могут возникнуть определённые трудности. Действительно, одним из важнейших свойств процессов является их изоляция, которую крайне соблюсти в случае совместного пользования ОЗУ. Эту проблему можно разбить на несколько более простых подзадач.
1. Защита данных одного процесса от возможных изменений другими работающими процессами.
2. Упрощение логики работы процесса с памятью. Действительно, для программиста было бы удобно рассматривать память процесса как последовательность ячеек.
3. Возможность использовать больший объём памяти, использую внешнюю память.
4. Оптимизация использования ОЗУ: хранить только те данные, которые реально требуются системе.
Наиболее частым решение этой проблемы является использование абстракции «виртуальной памяти». Виртуальная память - это сочетание памяти ОЗУ и временного хранилища на жестком диске. Если памяти ОЗУ недостаточно, данные из оперативной памяти помещаются в хранилище, которое называется файлом подкачки. Перемещение данных в файл подкачки и из него освобождает достаточно оперативной памяти для выполнения операции.
Как правило, чем больше объем установленного в компьютере ОЗУ, тем быстрее работают программы. Если нехватка оперативной памяти замедляет работу компьютера, то для ее восполнения можно увеличить размер виртуальной памяти. При этом необходимо учитывать, что чтение данных из ОЗУ выполняется значительно быстрее, чем с жесткого диска, поэтому в качестве решения больше подойдет добавление ОЗУ.
В большинстве современных операционных систем виртуальная память организуется с помощью страничной адресации. Оперативная память делится на страницы: области памяти фиксированной длины (например, 4096 байт), которые являются минимальной единицей выделяемой памяти (то есть даже запрос на 1 байт от приложения приведёт к выделению ему страницы памяти). Процесс обращается к памяти с помощью адреса виртуальной памяти, который содержит в себе номер страницы и смещение внутри страницы. Процессор преобразует номер виртуальной страницы в адрес соответствующей ей физической страницы при помощи буфера ассоциативной трансляции. Если ему не удалось это сделать, то требуется обращение к таблице страниц (так называемый Page Walk), что может сделать либо сам процессор, либо операционная система (в зависимости от архитектуры). Если страница выгружена из оперативной памяти, то операционная система подкачивает страницу с жёсткого диска (см. свопинг). При запросе на выделение памяти операционная система может «сбросить» на жёсткий диск страницы, к которым давно не было обращений. Критические данные (например, код запущенных и работающих программ, код и память ядра системы) обычно находятся в оперативной памяти (исключения существуют, однако они не касаются тех частей, которые отвечают за обработку аппаратных прерываний, работу с таблицей страниц и использование файла подкачки).
Представление о том, как это работает, можно получить из рис. 2 на примере двух процессов: fileA.exe и fileB.exe. У каждого из них есть своё собственное непрерывное виртуальное адресное пространство (закрашенные прямоугольники - занятые страницы) и общее физическое. Часть виртуальных страниц транслируются в страничные кадры ОЗУ, другая часть выгружена в кэш. Логика работы процессов основывается на предположении о том, что других процессов в системе нет, а память имеет вид массива.
Рис. 2. Пример организации виртуальной пАМЯТИ
СТРАНИЧНАЯ АДРЕСАЦИЯ
Рассмотрим подробнее механизм трансляции виртуальных адресов в физические, который называется страничным преобразованием или пейджингом.
Сегментная модель
На уровне сегментов адрес преобразуется из виртуального в линейный. По виртуальному адресу вычисляется сегмент и смещение в сегменте. Большинство современных операционных систем, однако, используют так называемую плоскую модель памяти (flat model). При этом все сегменты начинаются с нулевого адреса, и фактически на этом уровне преобразование становится тождественным. В архитектуре x86-64 при включенном 64-битном режиме сегментация не используется.
Пейджинг
На уровне пейджинга адрес преобразуется из линейного в физический. Пейджинг можно отключить, в таком случае преобразование будет тождественным. В архитектуре Intel существует три режима пейджинга: 32BIT, PAE, EM64-T. Всех их объединяет следующая общая схема: есть несколько уровней пейджинговых структур (paging structure), элементы которых содержат физические адреса страниц, в том числе это может быть, например, адрес, содержащий другую (или даже ту же) пейджинговую структуру. Кроме физического адреса в элементах пейджинговых структур хранятся различные флаги. Среди них флаги, отвечающие за права доступа, за совместное использование страниц (для мультипроцессорных систем), флаги, устанавливаемые при произведении доступа к странице.
Таким образом, получается некий ориентированный граф, в котором вершины - это пейджинговые структуры и пользовательские страницы памяти, а ребра задаются элементами этих структур (paging structure entries). Структура верхнего уровня - одна, ее адрес содержится в специальном регистре (CR3). Линейный адрес задает путь в этом графе от структуры верхнего уровня до некоторой страницы. Делается это следующим образом: линейный адрес делится на несколько частей. Первая часть задает номер элемента (ребра графа) в первой вершине (структуре первого уровня), так определяется вторая вершина пути. Вторая часть линейного адреса дает номер ребра во второй вершине и так далее до конечной физической страницы, в которую и отображается заданная нашим виртуальным адресом страница виртуальной памяти (смещение внутри страницы остается неизменным при преобразовании). Этот процесс проще понять, глядя на следующий рисунок.
Рис. 3. Пример многоуровневой страничной адресации
TLB Кэш
Обращение к памяти - очень частая операция, поэтому выполняться она должна быстро. Каждый раз при доступе к странице просчитывать страничные преобразования заново не экономично. Поэтому процессор сохраняет найденный физический адрес вместе с необходимыми флагами в специальный кэш - TLB (Translation lookaside buffer - кэш страничных преобразований). TLB кэш является ассоциативной памятью, поиск в нем страницы по виртуальному адресу занимает в 10-60 раз меньше времени, чем обход таблиц страниц. При добавлении в граф пейджинга новых страниц (мапировании) TLB кэш подстраивается автоматически. Действительно, при обращении к новой странице процессор не найдя в TLB нужной записи обойдет таблицы страниц и добавит новую страницу в TLB. При удалении страниц, или более серьезном изменении дерева пейджинга (например, при переключении между процессами в операционной система) необходимо уведомить процессор о том, что одна или несколько записей в TLB стали недействительны. Это может быть, например, инструкция INVLPG, указывающая на недействительность записи с конкретным виртуальным адресом. Также, кэш TLB автоматически сбрасывается при переключении регистра CR3 [6].
Схематично логика работы TLB изображена на рис. 4.
РИС. 4. ЛОГИКА РАБОТЫ TLB
Аппаратно-независимая оптимизация работы с памятью
До сих пор мы рассматривали реализацию виртуальной память на уровне аппаратного обеспечения. Однако на уровне операционной системы доступны некоторые дополнительные механизмы оптимизации. Прежде всего, это касается механизма своппинга (выгрузки страниц физической памяти). В самом деле, скорость доступа к оперативной памяти отличается от скорости доступа к диску на порядки, поэтому целесообразно минимизировать время использования HDD. Система обращается к своп-файлу при возникновении исключительной ситуации “пропуск страницы” (page fault, pf). Задача оптимизации времени работы заключается в минимизации числа этих ситуаций. Для этого необходимо выбрать грамотную стратегию выгрузки страниц. Несложно представить идеальный алгоритм откачки: достаточно убирать ту страницу, которую меньше всего будут использовать. Проблема заключается в отсутствии «оракула», который бы предсказывал дальнейшую судьбу страниц в памяти.
Так как идеальная стратегия технически неосуществима, на практике используются всевозможные её приближения.
Алгорим FIFO
Одним из простых в реализации является алгоритм FIFO (first in, first out - первым вошёл, первым вышел). Нужно просто вытеснять самую долгоживущую в памяти страницу. При этом не делается никаких предположений о важности замещённой памяти, и велик риск отгрузить на диск активно используемую страницу.