Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Министерство образования и науки Российской Федерации

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ
(государственный университет)

ФАКУЛЬТЕТ УПРАВЛЕНИЯ И ПРИКЛАДНОЙ МАТЕМАТИКИ

КАФЕДРА Теоретической и прикладной информатики

(Направление подготовки 010900 «Прикладные математика и физика»,

Магистерская программа 010956 «Математические и информационные технологии»)

Выпускная квалификационная работа

Балансировка нагрузки высокопроизводительного кластера

студента 873 группы

Петрова Дмитрия Игоревича

Научный руководитель

д.ф.-м.н. Тормасов А.Г.

г. Долгопрудный

2014

Оглавление

Введение 3

Понятие о виртуальной памяти 4

Физическая память 4

Виртуальная память 5

Страничная адресация 8

Сегментная модель 9

Пейджинг 9

TLB Кэш 10

Аппаратно-независимая оптимизация работы с памятью 12

Алгорим FIFO 12

Алгоритм LRU 12

Алгоритм NFU 13

Эвристика «рабочее множество процесса» 13

Пробуксовка 13

Формализация 15

Релизация модели «Рабочее множество» 16

Виртуализация. 17

Типы виртуализации. 17

Виртуализация аппаратуры. 17

Виртуализация рабочего места. 21

Виртуализация программного обеспечения. 22

Безопасность виртуализации. 23

Контейнерная виртуализация 24

Обзор технологии 24

Миграция контейнеров 26

Реализация 27

Методы балансировки и результаты 29

Distributed resource management 29

Метод оценки Process working set (PWS) 33

Заключение 35

Список публикаций автора 37

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

Приложение. Вычисление PWS 39

Введение

Проблема распределения нагрузки в высокопроизводительных вычислительных систем стоит весьма остро уже несколько десятилетий. Особенно интересна данная задача в применении к современным виртуальным сервисам. Переход от реального железа к виртуализованному позволяет решать сразу несколько важнейших задач. Нет необходимости в физической машине, её техническому обслуживанию, обеспечению электричеством, охлаждения. Снижается плата за аренду площадей под дата-центры. Кроме того, в рамках одной реальной машины («хоста») могут сосуществовать несколько машин на различных операционных систем. [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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ВКР