Заметки к лекциям распределённые системы (2014)

Крюков Виктор Александрович (krukov@keldysh.ru), Бахтин Владимир Александрович (bakhtin@keldysh.ru)

Распределённые системы

Курс отличается от «распределённые операционные системы»

avasite

Лекция 1

На экзамене так же дают практические задачи – типо реализовать алгоритм для «а вот програмка»

Но экзамен устный (и задачи делают так, чтобы они покрывали как можно больше тем)

Разрешают всем пользоваться

Операционная система рассматривается с 2-х точек зрения:

1. Это абстрактная машина, на которой писать программы удобнее для программиста (есть некоторый уровень абстракции (например ввод/вывод))

2. Это менеджер ресурсов.

MS DOS фактически обеспечивал работу одной программы одного пользователя, за исключением мелочей, типо параллельного ввода с клавиатуры, но параллельности не было.

Ресурсы операционной системы – распределённые отдельные объекты.

История ОС:

Года будут условными.

1. 50-е – режим работы – «Персональные ЭВМ» (ПЭВМ) (или «Пультовые ЭВМ»). Человеку в конкретное время дня (или ночи) выдавали машину в полное распоряжение. Были программные компоненты, как «служебные программы» (интерфейс пользователя (можно было попросить её распечатать что-нибудь (скажем дамп памяти))) и «Программы вв./выв.» (чтобы не изучать внутреннее устройство железа и его работу)

Пользователь – (программист, математик, физик).

Существовали операторы, которые работали быстрее и правильнее, но всё равно машина простаивала пока вокруг неё прыгали

1. Середина 50-х годов – пакетная обработка. Человеческое введение данных выделили в отдельную задачу (формирование лент или пакетов перфокарт).

Даже если одно-программный режим, то в памяти машины всё равно находится программа (аналог ОС), и эту программу нельзя портить, её нельзя затирать, менять, …

Это привело к требованиям от аппаратуры:

1. защите ОП (Оперативной памяти). Для этого в машине ввели элементарный способ – 2 регистра, которые говорят, куда можно писать, а куда - нет

2. прерывания – для того, чтобы машина не зависала на выполнении пользовательской задачи (будь то вечный цикл, или деление на ноль, …), управление нужно передать в ОС

3. привилегированный режим – который разграничивает права между пользователем и ОС (например, только ОС имеет право менять регистры из первого пункта), так же нужно защищать и внешнюю память, нельзя давать кому-попало писать куда попало, поэтому для того, чтобы записать что-то – нужно вызывать стандартное средство ОС для записи.

4. Таймер – для предоставления возможности переключения работы с одного процесса на другой – позволяет сделать «псевдо»-программирование.

Без этих 4-х – организовать мультипрограммный режим – не обеспечить.

Мультипрограммирование позволило следить за работой программы и отлаживать её (ставить точки отладки, …).

1. Середина 60-х годов – режим разделения времени (РРВ) (в этом курсе почти не затрагиваем этот вопрос). РРВ – это возможность работы с программной многих пользователей одновременно.

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

Этот режим появлялся, потому что очень важен диалог пользователя с машиной (исправление ошибок компиляции, отладка, …)

Как меру набранного времени берётся отношение (время вып. программы) / (время астрономическое), и в зависимости от этого отношения, пришлось

1. Страничная и сегментная организация памяти (ведь нужно как-то распределять память между пользователями).

Мотивы:

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

2. Удобство программиста – ведь если нужен длинный массив, а в ОП нету столько места подряд, то только сегментация и её маппинг помогут позволить разбить массив в реальной памяти и динамическое изменение массива (не знаешь, на сколько он потом вырастет, но если выделять из свободных кусов страниц, то проблем не будет)

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

Если маппить одну виртуальную память, в несколько виртуальных памятей, разных редакторов, то при падении одного – другим ни горячо, ни холодно, и сам редактор делать – очень легко.

1. 70-е – многопроцессорные ЭВМ, сети и многомашинные комплексы.

Были проблемы с компиляцией – она была очень долгой, занимала больше половины времени. Казалось, что нужно делать машины с несколькими разными специализированными процессорами, чтобы ускорить нужное. Однако это не пошло, потому что пока делали это, уже другие сделали универсальный процессор, который работал в 10 раз быстрее (в общем – гонки, горячее время было). (он говорил, что на это нарвались те, кого он называл «мы»). Выбор между тем – делать специальную систему или универсальную систему – часто возникает.

(Чтобы запустить Буран – там использовался один язык для борта, а другой язык для земли, и там так было сделано, что язык понимал формально ту запись, на которой писались алгоритмы запуска другими людьми, этот язык был специализирован, но понимал чужое, - компромис между специализацией)

Процессоры вв/выв – пример специализации, которая прокатила.

Мотивы возникновения:

1. Специализация

2. Эффективность (машина с несколькими процессорами - эффективнее)

3. Надёжность (если в машине есть несколько процессоров, и один из них умер, то продолжить работу на остальных – не представляет особого труда) (+ возможно ещё, что, более специализированная аппаратура – более проста (занимается своим делом), а потому и надёжнее)

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

Сети – придумывались стандарты, которые в то время на аппаратуре не реализовывались, и появлялись проблемы.

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

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

1. 80-е – ПЭВТ (персональные ЭВМ) – пользователи были очень довольны, когда появлялся персональный компьютер, и не было уверенности, что всё, что придумано ранее – не нужно. Сама ОСь на ПЭВМ двигалась в направлении не многозадачности, а формировании графики, и другой «ерунды»

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

Лекция 2

В мультипроцессорных системах запись в кэш сквозная.

MPP – Massive Parallel Processing.

Многопроцессорные машины появлялись, потому что не получалось традиционным способом увеличивать производительность (увеличение тактовой частоты) (ибо сильно большое энергопотребление).

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

Гетерогенность – всё больше компьютеров используют ускорители – графические процессоры и процессоры intel. (фактически – это специализация)

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

Недостатки РОС:

1. Тяжело писать ось, программы, языки программирования, компиляторы, …

Легко ошибиться и нарваться на deadlock или ещё что-нибудь.

1. …

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

ссылка на материалы: ftp.keldysh.ru/K_student/Distributed_Systems/progDS2014-09_11.pdf

Существует 2 приёма позволяющих ускорить передачу сообщений в многопроцессорной системе:

1. Послать сообщение по нескольким маршрутам (часть туда и часть сюда)

2. Конвейеризация – послать сообщение k раз по кусочкам размера (сообщение/k) (было такое же на сетях – послать не весь пакет, а пакет кусочками) – это самое серьёзное улучшение

Может быть построено 2 варианта сети: широковещательная и не широковещательная. Наличие широковещания – очень полезно, потому что если нужно послать что-то всем, то это сделается за один раз, а не циклически каждому.

Если несколько процессоров обратилось к шине, то будет выбран тот, у которого меньше номер.

Нет никаких «захватить шину», …, есть только «послать» и «принять».

Коммуникационные операции могут быть неблокирующие и блокирующие.

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

Процессорное время он часто не считает, потому что процессор – гораздо быстрее, чем обмен по памяти.

Буферизация – мы можем класть в буфер данные на будущее, в случае, если шина пустует. Т.е. мы можем использовать send и receive – когда душе угодно, в расчёте на загрузку данных на будущее, но есть проблема с тем, что нужно затачиваться под конкретную машину. (к сожалению этот процесс вообще-то не автоматизирован)

Есть 2 проблемы – первая связанна с тем, что send ждёт подтверждения для receive (так нужно, потому что если данные отправят, а кто-то будет загружен и не сможет данные получить, то они будут сброшены у него, ибо девать их некуда), а другая проблема в том, что send можно сделать только после receive, и нельзя посылать биты дальше, сразу после получения первого бита сообщения.

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

Ошибка в MPI – это «потенциальный deadlock», который может случиться в синхронном режиме.

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

Коллективные коммуникации – шине нужно их уметь реализовывать на основе операции точка-точка.

Операция AllToAll – обычно для транспонирования матрицы.

Глобальные операции – раньше это были операции между областями памяти (не был известен тип), и поэтому невозможно было сделать операции глобальными.

Операции часто рассчитывают на то, что данные распределены между процессорами одинаково.

Лекция 3

Владимир Александрович Бахтин

(кажется, он читает не по лекциям, а просто разговаривает (на хорошо))

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

Другая проблема – энергопотребление, при росте тактовой частоты температура растёт не линейно, а быстрее, но всё равно проблема в том, что не получается общаться с памятью.

Поэтому решили сделать несколько ядер, но уменьшить немного тактовую частоту.

Сейчас приходится решать проблему синхронизации нитей, одного узла, и нитей с разных узлов (обмен сообщениями тут надо пользовать, чтобы узлы общались)

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

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

Проблема Гонок:

X = x + y x = x – y

Load r1, x