Конспектик (1162782)

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

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

История ОС. Распределенные системы.

• ОС – программа, которая позволяет многим пользователям удобно работать на машине (простое определение)

• РОС – совокупность компонент, которая работает на независимых компонентах, которые представляются пользователю как единый компьютер

• Два взгляда на ОС

  • Менеджер ресурсов

  • Один из слоев абстракции

• История ОС

  • 40 – нач 50. Пультовый режим. (ПЭВМ). Без ОС. Использовались

    • Программы ввода-вывода

    • Интерфейс пользователя – множество кнопок на пульте, которые выполняли аппаратно реализуемые функции

  • Сер. 50 – Пакетная обработка. Ввод-вывод – отдельная машина. Целевая машина переключает задачи во время ввода-вывода. Мультипрограммный режим работы:

    • Прерывания (для аварийных ситуаций). Два класса

      • Внутренние

      • Внешние

    • Защита ОП.

    • Привилегированный режим (режим ОС).

    • Таймер

    • Если всего того нет:

      • Интерпретация программ (можно не все, а только там, где возможны ошибки), или

      • Вставка некоторых проверок в компиляторах ЯП.

  • 60е - Режим разделения времени (РРВ). Понадобился

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

    • Планировщик (квантирование времени для очереди процессов)

    • Организация памяти (т.е. всем пользователям сложно поместиться в ОП).

      • Страничная (the most popular today)

      • Сегментная

      • Странично-сегментная

    • Многостаночный редактор

      • Обслуживает пользователей

      • Работает с файлами

      • Ведет статистику

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

    • Цели: специализация (АС-6), эффективность, надежность

    • ОС должна: передать с терминала пакет, обеспечить доступ к файлу на другом узле

• 80е – ПЭВМ

• 90е – MPP, Открытые системы, Internet.

• 2000е: Кластеры, Grid, Многоядерные системы(многопроцессорная ЭВМ с общей памятью и с общим КЭШем.)

Из OS-intr (Крюков)

• Преимущество распределенных систем:

  • Экономическое (Закон Гроша не выполняется).

  • Производительность.

  • Естественная распределенность (банк).

  • Надежность

  • Наращиваемость производительности

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

  • Сложность ПО

  • Проблемы коммуникации сети

  • Секретность

• Виды ОС

  • Сетевые ОС - машины обладают высокой степенью автономности (серверы файлов)

    • Вести диалог с другой ЭВМ

    • Вводить задания в ее очередь пакетных заданий

    • Иметь доступ к удаленным файлам

  • Распределенные ОС - единый глобальный межпроцессный коммуникационный механизм

    • Глобальный межпроцессный коммуникационный механизм

    • Глобальная схема контроля доступа

    • Одинаковое видение файловой системы.

    • Вообще – иллюзия единой ЭВМ.

  • ОС мультипроцессоров

    • Единая очередь процессов

    • Одна файловая система

• Принципы построения РОС:

  • Прозрачность

    • расположения (пользователь не должен знать, где расположены ресурсы)

    • миграции (ресурсы могут перемещаться без изменения их имен)

    • размножения (пользователь не должен знать, сколько копий существует)

    • конкуренции (множество пользователей разделяют ресурсы автоматически)

    • параллелизма (работа может выполняться параллельно без участия пользователя)

  • Гибкость - Использование монолитного ядра ОС или микроядра.

  • Надежность

    • доступность, устойчивость к ошибкам

    • секретность

  • Производительность (мелкозернистый и крупнозернистый параллелизм)

  • Масштабируемость

    • Централизованность – плохое решение!

    • Децентрализованные алгоритмы:

      • Ни одна машина не имеет полной информации о состоянии системы

      • Машины принимают решения на основании только локальной информации

      • Выход из строя одной машины не должен приводить к отказу

      • Нет глобальных часов

Из OS-MPI-Sync.doc. Коммуникации в распределенных системах

• Коммуникационные сети

  • Широкомасштабные (WANs)

    • Состоит из коммуникационных ЭВМ, связанных коммуникационными линиями

    • Обычно сообщения передаются с промежуточной буферизацией.

  • Локальные (LANs)

    • Небольшая область охвата

    • Высокая скорость

    • Малая вероятность ошибок передачи

    • Более простые протоколы чем ISO OSI (т.к. редки ошибки передачи)

• Коммутация пакетов или коммутация линий

• Семиуровневая модель ISO OSI – большие накладные расходы!

• Обмен сообщениями между прикладными процессами

  • Адресация

    • Физический/логический номер процессора

    • Уникальный ID процесса

  • Пересылка на соседний компьютер требует три копирования

    • Память отправителя – буфер ОС

    • Пересылка между буферами

    • Буфер ОС получателя – память получателя

  • Блокирующие и неблокирующие передачи

  • Буферизованные и небуферизованные передачи

  • Надежные и ненадежные передачи

Многопроцессорные ЭВМ с распределенной памятью. (Мои + Глазкова + Крюков)

• Основной минус ЭВМ с общей памятью

  • Поддержание когерентности КЭШей (КЭШи должны подслушивать шину)

• Шинная организация

  • Сеть с широковещанием

  • Сеть без широковещания

  • У шины есть арбитр

  • Tn = Ts + Tb*N (Ts – время старта (латентность). Tb – время передачи байта)

• Транспьютерные системы

  • Транспьютер – машина, в которую входи и выходит по 4 канала, для взаимодействия с другими транспьютерами

  • Особенности

    • Однобайтовые команды

    • Аппаратное планирование процессов и их обслуживание.

      • 2 аппаратные очереди – готовности и квантования.

      • 8 параллельно работающих каналов по обслуживанию связей.

    • В один момент времени можно сделать 4 посылки и 4 приема.

    • Язык Occam для транспьютера

  • Два метода ускорения передачи сообщения

    • Конвейер

    • Много путей

• Существует два вида параллелизма (в программах)

  • Параллелизм задач

  • Параллельная обработка циклов

• 1978, Хоар, работа CSP. Предложил отказаться от взаимодействия через общую память, и реализовать обмен сообщениями. Метод передачи – рандеву.

• PVM (Parallel Virtual Machine)

  • Надстройка над ОС Unix

  • Объединяет несколько рабочих станций, связанных сетью.

  • Задача пользователя – множество подзадач, которые динамически создаются на указанных процессорах РС и взаимодействуют передачей сбщ.

  • Достоинства

    • Простота (наследственность от Unix аппарата процессов и сигналов)

    • Возможность динамического добавления к группе новых процессов

  • Недостатки

    • Низкая производительность

    • Функциональная ограниченность (Ex: только буферизованный send)

• Процессы.

  • Имеет следующие компоненты

    • Выполняемая программа

    • Регистровый контекст

    • Заказы на ввод-вывод

    • Данные, которые процесс использует

    • Таблица дескрипторов открытых файлов

    • Идентификатор процессора в системе и т.д.

  • В контексте одного процессора имеется несколько нитей

  • Легковесные процессы (нити) – имеют общую память и файловые дескрипторы, отличается лишь регистровый контекст => быстрое переключение между нитями.

  • Два вида взаимодействия процессов:

    • Взаимное исключение критических интервалов

    • Координация процессов

  • Два способа взаимодействия

    • Через передачу сообщений

    • Через общую память

  • Требования к взаимному исключению:

    • КИ должен выполняться в монопольном режиме

    • Время нахождения любого процесса в КИ ограничено

    • Если нет других желающих, то входим в КИ сразу

    • Каждый запросивший вход должен его получить

    • принцип справедливости – кто раньше

    • нельзя ждать бесконечно долго

  • Обеспечение взаимного исключения на однопроцессорной ЭВМ. 2 решения:

    • Блокировка внешних прерываний

      • Плюс: простой и очень быстрый метод

      • Минус: теряем контроль. Процесс может зациклиться в КИ.

    • Блокировка переключения на другие процессы. Моно/мульти-режим Прерывания работают.

  • Взаимное исключение на многопроцессорной ЭВМ с общей памятью

    • Для двух процессов, с активным ожиданием. Основаны на неделимости операций записи и чтения из памяти.

      • Алгоритм Деккера (1968) (os-multipr.doc)

      • Алгоритм Петерсона (1981) (os-multipr.doc)

    • Для произвольного числа процессов

      • TSL (r, s) [r := s, s:=1] – неделимая операция

      • Семафоры (65г, Дейкстра)

        • Две операции

          • P(S) [if (s=0) <заблокировать процесс>, else s—]

          • V(S) [if (s=0) <разблокировать один из ранее заблокированных процессов; s++]

        • Нельзя освобождать семафор повторно

        • Задачи, решаемые семафорами:

          • Взаимное исключение

          • Координация

          • Поставщик-потребитель

      • Считающий монитор

      • Механизм событий

        • Событие – двоичная операция, которая имеет следующие операции:

          • Post(e) – объявить событие (e:=1, разблокировать всех, кто ждал) = V(S)

          • Wait(e) – если e==0, то ждать.

          • Clear(e) – чистка события, e:=0. = P(S)V(S)

  • Планирование процессов

    • Причины деградации производительности:

      • Накладные расходы на переключение процесса (регистровый контекст, откачка страниц, порча КЭШа).

      • Переключение на процесс, находящийся в активном ожидании

    • Стратегии борьбы с деградацией:

      • Совместное планирование – все процессы одного приложения одновременно выбираются на процессоры и одновременно снимаются с них (сокращает переключение контекста)

      • Находящиеся в КИ процессы не прерываются.

      • Процессы планируются на те процессоры, на которых были до переключения

MPI (Крюков + Антонов + Мои + Глазкова).

• MPI-1 (94г), MPI-2 (97г).

• Цели

  • Интерфейс прикладного и системного программиста

  • Эффективность коммуникаций (избегание лишнего копирования, разгрузка коммуникационных процессоров)

  • Расширение для неоднородных (гетерогенных).

    • При посылке элемент переводится во внутреннее представление MPI.

  • Исходить из надежности коммуникаций

  • Знакомый интерфейс (как в PVM, Express, P4).

  • Быстрая реализация на имеющейся базе.

• MPI включает:

  • Операции точка-точка

  • Коллективные операции (используется широковещательная способность используемой сети)

  • Группы процессоров.

  • Коммуникационный контекст (область видимости для сообщений)

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

  • Топология процессов. Можно посылать сообщения не в терминах номеров узлов, а в терминах «сосед сверху», «сосед слева».

  • Поддержка передачи производных типов данных

• Не включено

  • Общая память

  • Активные сообщения

  • Прием через прерывания

• Операции

  • Локальные – не требуется коммуникаций

  • Нелокальные – выполнение операции требует коммуникаций

  • Коллективная – в её выполнении участвуют все процессы группы.

• Группы

  • Множество идентификаторов процессов

  • Можно создавать подгруппы

  • Упрощает проблему адресации

• Коммуникаторы

  • Ограничивают область видимости сообщений рамками некоторой группы процессов (группа + контекст)

  • Оптимизация.

  • Коммуникационный объект позволяет отправителю опрашивать состояние операции передачи.

• Точечные коммуникации

  • Бывают блокирующими и неблокирующими

  • Send

    • адрес буфера в памяти;

    • количество посылаемых элементов;

    • тип данных каждого элемента;

    • номер процесса-адресата в его группе;

    • тег сообщения – неотрицательное число типа int. Чтобы отличать разные сообщения одного и того же отправителя

    • коммуникатор (типа MPI_Comm) – среда для передачи сообщений. Один процесс может быть приписан нескольким коммуникаторам.

    • статус сообщения (возвращает MPI_SUCCESS или код ошибки)

  • Receive

    • адрес буфера в памяти;

    • количество посылаемых элементов;

    • тип данных каждого элемента;

    • номер процесса-адресата в его группе (либо «любой»);

    • тег сообщения (либо «любой»);

    • коммуникатор;

    • статус (возвращает MPI_SUCCESS или код ошибки)

  • Режимы передачи

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

      • MPI_Send – блокирующая операция

      • MPI_ISend - неблокирующая

    • Буферизуемый (MPI_BSend) – завершается тогда, когда сообщение изъято из памяти и помещено в буфер. Локальная. (говорят, в лекциях бага. Нелокальная)

    • Синхронный (MPI_SSend) – рандеву. Нелокальная.

    • Готовности (MPI_RSend) – отработает корректно только если уже вызван MPI_Receive. Локальная. (говорят, в лекциях бага. Нелокальная)

  • Коллективные коммуникации

    • Барьер для всех членов группы (BARRIER)

    • Передача всем от одного (BROADCAST)

    • Сбор данных от всех одному (GATHER)

    • Рассылка одного всем по персональному куску (SCATTER)

    • Сбор данных по кускам от всех всем (ALLGATHER)

    • Рассылка всем от всех - каждый делает scatter (ALLTOALL)

    • Глобальные операции (редукцонные) – сумма, максимум, минимум.

    • Преимущества использования MPI

      • Выбирает наиболее оптимальные маршруты

      • Более удачно выбирает координатора (например, при барьерной синхронизации)

      • Учитывает загруженность линий связи.

• MPI-2

  • Динамическое создание и уничтожение процессов

  • Односторонние коммуникации – процесс имеет возможность прочитать область памяти другого процесса.

  • Параллельные операции ввода-вывода.

Синхронизация в распределенных системах (Крюков + Глазкова)

• 4 основные проблемы:

  • Синхронизация времени

  • Выбор координатора

  • Взаимное исключение

  • Координация процессов

• Синхронизация времени

  • Нет глобальных часов

  • Для большинства целей достаточно иметь логическое время (1978, Лампорт)

  • Отношение «а произошло до b»

    • Если оба события произошли в одном процессе

    • Если событие «а» есть операция SEND в одном процессе, а событие «b» - прием этого сообщения в другом процессе.

• Выбор координатора

  • Алгоритм задиры

Любой процесс может инициировать выборы. Он посылает «запрос» всем процессам с ID больше чем у него, и если не получает ответа – становится координатором, о чем извещает все процессы сообщением «координатор».

• Круговой алгоритм

Инициирующий процесс посылает соседу «запрос». Если тот не отвечает – следующему. Сосед добавляет ID из запроса в список и посылает дальше. Когда круг замкнется (процесс обнаружит себя в списке), он выбирает из списка процесс с наибольшим ID и извещает всех о новом координаторе.

• Взаимное исключение

  • Централизованный алгоритм

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

• Децентрализованный алгоритм на основе временных меток.

Требует глобальное упорядочение всех событий по времени. Желающий войти в КС посылает запросы всем процессам. Если получатель собирался войти в КС – сравнивает временные метки. Сидящий в КС не отвечает, остальные – говорят ОК. При выходе из КС – шлет ОК всем, от кого получил запросы. Минусы: много сообщений, снижение надежности.

• Круговой маркер

Маркер перемещается от процесса к процессу по логическому кольцу. Минусы:

• Маркер бегает по кругу, даже если никому не нужен.

• Если кто-то часто входит в КС, он все равно должен ждать маркер.

• Широковещательный запрос маркера

Маркер содержит: очередь запросов, массив из номеров последних выполненных запросов. Если хочешь маркер – рассылаешь всем запрос с новым номером запроса. Владелец маркера сверяет, что это не старый запрос, и добавляет отправителя в маркерную очередь. Затем отсылает маркер следующему по очереди. При выходе из КС в маркере в массиве номеров выставляется номер своего последнего запроса.

• Децентрализованный древовидный маркерный алгоритм

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

• Метрики сравнения алгоритмов исключения

  • MS/CS – число операций приема сообщений на одну КС

  • TR – время ответа (от появления запроса до разрешения)

  • SD – синхронизационная задержка (время от выхода одного из КС до входа следующего)

Распределенные файловые системы (Крюков – Глазкова – Таненбаум)

• Распределенная ФС – разделяет доступ к файлам на различных машинах сети.

• Цели

  • Сетевая прозрачность

  • Высокая доступность

• Файловый сервис – это то, что файловая система предоставляет своим клиентам (интерфейс)

• Файловый сервер – это процесс, который реализует файловый сервис.

• Примеры:

  • NFS – Network File System

  • RFS – Remote File System

  • AFS – Andrew File System

• Свойства, которым должна удовлетворять распределенная ФС:

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

  • Прозрачность расположения – неважно, где конкретно хранится файл

  • Независимость размещения – пользователь не знает, где физически лежат данные

  • Мобильность пользователя – независимость от машины пользователя

  • Устойчивость к сбоям

  • Масштабируемость – должны уметь модернизировать нашу ФС при увеличении нагрузки

  • Мобильность файлов – файл может передаваться от одного сервера к другому, чтобы обеспечить максимальную эффективность

• Распределенный ФС имеет два компонента

  • Файловый сервер

    • Файл – неинтерпретируемая последовательность байтов.

    • Защита файла

      • Список прав доступа

      • Мандат – билет, выданный пользователю для каждого файла с указанием прав доступа.

    • 2 способа работы с файлами:

      • Модель удаленного доступа – файл все время лежит на сервере

      • Модель загрузки/выгрузки – доступ осуществляется на клиенте.

  • Сервер директорий

    • Обеспечивает операции создания и удаления директорий, именования и переименования файлов, перемещение файлов из одной директории в другую.

    • Иерархичность директорий

    • Прозрачность именования

      • 2 формы прозрачности

        • Прозрачность расположения

        • Прозрачность миграции

      • 3 подхода к именованию

        • Машина + путь

        • Монтирование удаленных ФС в локальную иерархию файлов

        • Единственное пространство имен (необходимо для того, чтоб распределенная система выглядела как единый компьютер)

      • Двухуровневое именование

        • Файл имеет символьное имя (для пользователей)

        • Файл имеет внутреннее двоичное имя (для самой системы)

    • Разделение доступа фалов

      • Подход Unix

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

• Семантика сессий

Изменения файла сохраняются на сервере по операции CLOSE

• Неизменяемые файлы

Файлы можно только создавать и читать. Редактировать – нельзя.

• Семантика транзакций

Между операциями BEGIN_TRANSACTION и END_TRANSACTION сервер гарантирует, что никакого влияния других клиентов не будет.

• Реализация распределенных ФС

  • Выбирая политику, нужно определиться, как будут использоваться файлы

  • Структура системы

    • Должен ли клиент отличаться от сервера?

    • Должны ли быть файловый сервер и сервер директорий отдельными серверами?

    • Должны ли серверы хранить информацию о клиентах?

      • Сервер с состоянием

        • Хранят информацию о состоянии клиента

        • Таблицы открытых файлов -> бОльшая эффективность

        • Короче сообщения (двоичные имена используют таблицу открытых файлов)

        • Блоки информации могут читаться с упреждением.

        • Легко реализуется возможность блокировки файлов

        • Проблема – крах клиента

      • Без состояния

        • Не требуется память для таблиц открытых файлов (их нет)

        • Нет ограничений на количество файлов, с которыми система может работать

        • Не требуются операции OPEN/CLOSE

        • Простота реализации,

        • Устойчивость к ошибкам

        • Нет проблемы краха клиента.

• Кэширование

  • Виды кэширования:

    • В памяти сервера (минус: коммуникационные издержки)

    • На дисках клиента (сложно реализовать)

    • В памяти клиента (самый лучший подход)

  • Варианты использования КЭШа:

    • У каждого процесса – свой кэш

    • Единый кэш для всех процессов

      • Кэширование в ядре (накладные расходы на обращение к ядру растут)

      • Использование кэш-менеджера (минус: на пользовательском уровне трудно эффективно использовать память, особенно виртуальную)

  • Алгоритмы поддержания КЭШей на разных клиентах согласованными:

    • Алгоритм со сквозной записью

      • Удобен для мультипроцессорных систем

      • В распределенных системах:

        • Серверу придется слишком часто извещать клиентов

        • Сообщения о модификациях могут быть перепутаны (во времени)

    • Алгоритм с отложенной записью (NFS 3)

      • Сообщаем серверу об изменениях через заданный промежуток времени

    • Алгоритм записи в файл по закрытию, реализует семантику сессий (NFS 4)

    • Алгоритм централизованного управления (плохое решение)

• Размножение файлов

  • Цели

    • Распределение нагрузки на несколько серверов

    • Увеличение надежности

    • Увеличение эффективности (можно работать с ближайшим сервером)

    • Увеличение доступности

  • Способы размножения

    • Явное размножение (непрозрачно)

Клиент получает список дескрипторов файлов, и пишет сразу во все

• Ленивое размножение

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

• Симметричное размножение

Команды, которые выполняет пользователь, автоматически выполняются на нескольких серверах.

• Протоколы коррекции

  • Метод главной копии.

    • Один сервер объявляется главным. Все изменения файла посылаются главному серверу. Он корректирует свою главную копию, а затем рассылает подчиненным серверам указания о коррекции.

    • Минус: выход из строя главного сервера не позволяет сделать коррекцию.

  • Метод одновременной коррекции всех копий.

    • Все изменения посылаются всем серверам.

  • Метод голосования.

    • Запрашивать чтение и запись файла у многих серверов.

    • Для успешной записи Nw (кворум записи) серверов должны ее выполнить

    • У всех серверов должно быть согласие относительно номера текущей версии файла. Номер увеличивается на единицу с каждой коррекцией.

    • Для успешного чтения достаточно обратиться к Nr (кворум на чтения) серверам.

    • Nw+Nr>N. Как правило Nw=N, Nr=1.

• NFS 4 – размножение. У файла может быть атрибут FS_LOCATIONS.

• Надежность (отказоустойчивость) ФС

  • Аутентификация

  • Блокировка файлов

    • Плюс – крах клиента. Ничего плохого не происходит

    • Минус – крах сервера. Теряем информацию о блокировках.

    • Период амнистии – в этот период сервер не устанавливает новых блокировок, а ждет только продления блокировок. Если никто не обратился – блокировка считается снятой. Требуется при восстановлении сервера после отказа.

  • Делегирование прав на открытие файлов. Аналогично – период амнистии.

  • Защита – метод контроля доступа к файлам

    • Организация защищенных каналов

    • Контроль доступа к файлам

• NFS

  • Была разработана для использования в рабочих станциях на базе UNIX, но затем была реализована и на многих других платформах

  • Архитектура NFS

    • Модель лежащая в основе NFS – удаленная файловая служба (remote file service) или модель удаленного доступа (remote access model) – файл все время остается на сервере.

    • Пользователям виртуальный файловый интерфейс (VFS), похожий на интерфейс стандартной ФС Unix.

    • Все взаимодействия между клиентом и сервером – посредством RPC (remote procedure call)

    • NFS как отдельный компонент лежит ниже уровня VFS, который стоит между уровнем системных вызовов и интерфейсом локальной ФС.

    • NFS клиента взаимодействует с NFS сервера посредством RPC-вызовов (remote procedure call).

  • Сервера бывают

    • С состоянием (хранят информацию о состоянии клиентов) - в NFS 4

    • Без состояния - в NFS 3

  • Модель файловой системы

    • Файл – неинтерпретируемая последовательность байтов.

    • Файлы организованы в виде иерархического графа имен.

    • NFS поддерживает жесткие ссылки (как в Unix)

    • Двухуровневое именование файлов (Символьное имя, Дескриптор (file handle))

  • Основные операции работы с файлами в NFS:

    • READ, WRITE, GETTATR (имя, размер и пр.), SETATTR, READDIR, LOOCUP (получение по символьному имени дескриптор файла)

    • В NFS 4 дополнительно есть OPEN и CLOSE. OPEN – возвращает дескриптор файла. CLOSE – требует дескриптор в качестве аргумента.

  • Взаимодействие клиента и сервера:

    • NFS 3

      • Клиент посылает запрос LOOKUP

      • Получает дескриптор

      • Клиент вызывает операцию READ(дескриптор файла, количество байт)

      • Сервер пересылает запрошенные байты.

    • NFS 4

      • Используется составная процедура (LOOKUP, OPEN, READ)

  • Именование файлов в NFS

    • Применяется автоматическое монтирование: клиент запрашивает у автоматического монтировщика какой-то каталог. Монтировщик шлет запрос серверу, и монтирует каталог в ФС клиента.

    • Клиенту предоставляется его собственное пространство имен.

    • Сервер также может экспортировать каталоги у клиента или сервера. Затем он монтирует каталог в свою ФС (ака-Unix).

  • Атрибуты файлов

    • Обязательные (TYPE, SYZE, FSID – ID ФС)

    • Рекомендованные (TIME_ACCESS, FS_LOCATIONS – здесь перечислены имена серверов, на которых может располагаться файл)

    • Именованные атрибуты (Пары Имя_атрибута:Значение_атрибута)

  • Синхронизация

    • Пользователю разрешается иметь локальный кэш часто используемых файлов.

    • NFS использует семантику сеансов

    • Блокировка файлов

      • Для чтения нужна блокировка на чтение.

      • Если процесс хочет писать – он должен заблокировать запись.

      • Если при назначении блокировки конфликтуют – отказ.

      • Блокировка дается на время – аренда.

      • В NFS 3 – используется менеджер блокировок. Он перехватывает запросы от клиента к серверу и хранит информацию о файлах.

      • В NFS 4 – блокировка интегрирована в протокол доступа к файлам

      • В NFS 4 следующие команды блокировки:

        • Lock – блокировка набора байтов

        • Lockt – проверка установлена ли конфликтующая блокировка

        • Locku – снятие блокировки с набора байтов

        • Renew – продление аренды указанной блокировки

      • В NFS 4 - Особый способ блокировки – совместное использование файлов. Процесс указывает требуемый тип доступа для себя и других процессов.

    • Кэширование

      • В NFS 3 разрешено кэширование. Данные сверяются каждые несколько секунд.

      • В NFS 4

        • Разрешается иметь дисковый кэш, и кэш в кэш-памяти

        • Два способа кэширования:

          • Семантика сеансов – если файл в КЭШе был изменен, при закрытии он обновляется на сервере.

          • Делегирование открытия. Если несколько клиентов сидят на одной машине, они могут использовать один кэш и производить блокировки в обход сервера. При отмене делегирования клиент возвращает файл.

DSM – Distributed Shared Memory (Крюков + Мои + Глазкова)

• DSM - виртуальное адресное пространство, разделяемое всеми узлами (процессорами) распределенной системы.

• Достоинства DSM:

  • В терминах виртуальных адресов проще написание программ и отладка, чем при обмене сообщений.

  • В DSM проще передавать сложные структуры, в т.ч. указатели и ссылки.

  • Объемы ОП суммируются

  • Практически беспредельное наращивание

  • Программы, написанные для мультипроцессоров, работают и на DSM.

• Основные вопросы

  • Как поддерживать информацию о расположении удаленных данных

  • Как снизить коммуникационные издержки

  • Как сделать разделяемые данные доступными на нескольких узлах (для повышения производительности)

• Алгоритмы реализации DSM (НЕЭФФЕКТИВНЫЕ)

  • Алгоритм с центральным сервером

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

• Миграционный алгоритм

  • Данные не хранятся где-то в конкретном месте, она передается тому узлу, который в ней нуждается.

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

  • Плюс:

    • позволяет воспользоваться локальностью расположения данных

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

  • Минусы:

    • Трэшинг – страницы очень часто мигрируют между узлами, например при «ложном разделении», когда разным процессам нужны разные данные, но они находятся на одной странице ОП.

  • Реализует последовательную консистентность

• Алгоритм размножения для чтения

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

  • Требуется отслеживать расположение всех блоков данных и их копий.

  • Плюс: повышение производительности за счет одновременного доступа на чтение

  • Минус: большие затраты для уничтожения всех устаревших копий и коррекции

• Алгоритм размножения для чтения и записи

  • Позволяет многим узлам иметь одновременный доступ к разделяемым данным на чтение и запись

  • Требуется поддерживать согласованность данных

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

    • Эффективно только при редких записях.

• Модель консистентности - договор между программами и памятью, в котором указывается, что при соблюдении программами определенных правил работы с памятью будет обеспечена определенная семантика операций чтения/записи

  • Строгая консистентность

    • Условие: «Операция чтения ячейки памяти с адресом X должна возвращать значение, записанное самой последней операцией записи с адресом X»

    • Требуются глобальные часы

    • Невозможно реализовать для РС

  • Последовательная консистентность

    • Лэмпорт, 1979г.

    • Условие: при параллельном выполнении, все процессы должны «видеть» одну и ту же последовательность записей в память.

    • Миграционный алгоритм реализует последовательную консистентность

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

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

  • Причинная консистентность

    • Пусть процесс P1 модифицировал переменную x, затем процесс P2 прочитал x и модифицировал y. В этом случае модификация x и модификация y потенциально причинно зависимы, так как новое значение y могло зависеть от прочитанного значения переменной x.

    • Если два процесса одновременно изменяют значения различных переменных, то между этими событиями нет причинной связи.

    • Операции записи, которые причинно не зависят друг от друга, называются параллельными.

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

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

      • все модификации переменных на каждом процессоре нумеруются

      • всем процессорам вместе со значением модифицируемой переменной рассылается номер этой модификации на данном процессоре, а также номера модификаций всех процессоров, известных данному процессору к этому моменту;

      • выполнение любой модификации на каждом процессоре задерживается до тех пор, пока он не получит и не выполнит все те модификации, о которых было известно процессору - автору задерживаемой модификации.

  • Процессорная консистентность

    • PRAM+когерентность памяти. Когерентность памяти – записи в одну и ту же переменную должны быть видны в одном и том же порядке.

    • Записи в разные переменные могут быть видны в произвольном порядке.

    • Мы заводим много координаторов: для каждой переменной по серверу, или на сервер мы распределяем блок переменных. Сервер делает рассылку об изменении переменной.

  • PRAM консистентность (Pipeline RAM)

    • Условие: Операции записи, выполняемые одним процессором, видны всем остальным процессорам в том порядке, в каком они выполнялись, но операции записи, выполняемые разными процессорами, могут быть видны в произвольном порядке

    • Плюсы: простота реализации, эффективность

    • Минусы: результат противоречит интуитивному представлению

  • Слабая консистентность (использует операцию синхронизации)

    • Вводится синхронизационная переменная

      • Доступ к синхронизационным переменным определяется моделью последовательной консистентности

      • Доступ к синхронизационным переменным запрещен (задерживается), пока не выполнены все предыдущие операции записи

        • все изменения сделанные процессом, станут гарантированно видны всем остальным

      • Доступ к данным (запись, чтение) запрещен, пока не выполнены все предыдущие обращения к синхронизационным переменным.

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

    • Полезно, если обращения к общим переменным встречаются редко

  • Консистентность по выходу (использует операцию синхронизации)

    • введены специальные функции обращения к синхронизационным переменным:

      • ACQUIRE - захват синхронизационной переменной, информирует систему о входе в критическую секцию;

      • RELEASE - освобождение синхронизационной переменной, определяет завершение критической секции.

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

    • Требования:

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

      • Перед освобождением синхронизационной переменной должны быть закончены все операции чтения/записи, выполнявшиеся процессором прежде.

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

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

    • Ленивая консистентность по выходу (использует операцию синхронизации)

      • Не требует выталкивания модифицированных переменных в КС при выходе

      • При входе в КС обновляет значения защищаемых переменных.

  • Консистентность по входу

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

    • элементам массива могут соответствовать разные синхронизационные переменные.

    • Секции могут быть с монопольным и непонопольным доступом.

    • Требования:

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

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

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

• Протоколы когерентности памяти

  • Write update – сразу рассылаем изменения во все КЭШи

  • Write invalid – обновление только если нужно

  • Комбинирование двух предыдущих подходов в зависимости от размера данных

• Конструкторские решения

  • Страничная DSM

    • Общая память разбивается на порции одинаковой длины - страницы или блоки.

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

  • DSM на базе разделяемых переменных

    • Программист должен точно определить, какие переменные в программе должны разделяться, а какие не должны.

    • Для разных переменных в на различных участках кода можно использовать разные протоколы коллекции копий (редукция, приватность, поддержание когерентности)

  • DSM на базе объектов

    • программы для объектно-ориентированной DSM системы не могут напрямую использовать общие переменные, а только через специальные функции-методы.

    • Весь контроль осуществляется только программными средствами.

Обеспечение надежности в распределенных системах (Крюков)

• Отказом системы называется поведение системы, не удовлетворяющее ее спецификациям.

• Последствия отказа могут быть различными

• Отказ системы может быть вызван:

  • отказом (неверным срабатыванием) каких-то ее компонентов (CPU, RAM etc)

  • ошибками при конструировании, при производстве или программировании

• Отказы

  • Случайные – при повторном повторении исчезают (причина, например, электромагнитная помеха)

  • Периодические – повторяются часто в течение какого-то времени, а затем могут долго не происходить (например, кончились процессы. Достаточно перегрузиться)

  • Постоянные – не прекращаются до устранения причин.

• Отказы по характеру поведения

  • Византийские – система работает, но неправильно.

  • Пропажа признаков жизни

• Подходы к обеспечению надежности:

  • Восстановление после отказа

    • Прямое восстановление – своевременное обнаружение сбоя и ликвидация его последствий путем приведения некорректного состояния системы в корректное.

    • Возвратное восстановление

      • При работе ставятся контрольные точки. Если произошел сбой – мы делаем откат. Можно делать бэкапы и вести журнал с момента последнего бэкапа.

      • Минусы

        • Потери производительности (нужно хранить информацию о предыдущих состояниях системы)

        • Нет гарантии, что сбой снова не повторится после восстановления (скажем, если ошибка в коде программы – система будет постоянно на ней падать)

        • Для некоторых компонентов системы восстановление в предшествующее состояние может быть невозможно (торговый автомат).

      • Тем не менее, это более универсальный подход чем прямое восстановление.

      • Трудности

        • Сообщения-сироты.

          • Процесс отказал после отправки сообщения. Откатываемся назад, и посылаем снова то же самое сообщение (сирота).

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

        • Эффект домино

          • Процесс отказал после отправки сообщения.

          • После приема, процесс-получатель отправляет сообщение третьему процессу.

          • Теперь назад должны откатиться все три процесса.

        • Потеря сообщений

          • Процесс отказал после приема сообщения.

          • Процесс откатывается назад, но ему уже никто ничего не шлет

        • Проблема бесконечного восстановления

    • Консистентное множество контрольных точек

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

      • Множество контрольных точек называется строго консистентным, если во время его фиксации никаких обменов между процессами не было.

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

      • Простой метод фиксации консистентного множества контрольных точек

        • Фиксируем локальную контрольную точку после каждой операции посылки сообщения.

        • Чтобы избежать потерь при восстановлении – необходимо повторить отправку сообщений, квитанции о получении которых стали недействительными в результате отката. Используются временные метки.

      • Синхронная фиксация контрольных точек и восстановление

        • Алгоритм создания консистентного множества контрольных точек

          • Алгоритм создает в стабильной памяти два вида контрольных точек - постоянные и пробные

          • Только один процесс инициирует создание множества контрольных точек

          • Никто из участников не должен ломаться во время работы алгоритма

          • 1-я фаза

            • Инициатор создает пробную контрольную точку и просит все процессы сделать то же самое.

            • Процессы перестают посылать неслужебные сбщ.

            • Каждый процесс извещает, сделал ли он пробную контрольную точку

          • 2-я фаза.

            • Если все справились – инициатор извещает всех о том, что пробная точка становится постоянной.

            • Если нет – всем сообщается, что шухер отменяется.

        • Алгоритм отката (восстановления)

          • 1-я фаза. Инициатор отката спрашивает, все ли готовы

          • 2-я фаза. Когда все готовы, им говорят: «поехали».

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

        • Синхронная фиксация упрощает восстановление, но связана с большими накладными расходами

      • Асинхронная фиксация контрольных точек и восстановление

        • множество контрольных точек может быть неконсистентным

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

  • Отказоустойчивость

    • Некоторым системам нельзя откатываться из-за прерывания нормального функционирования

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

    • Два механизма

      • Протоколы голосования

        • Служат для маскирования отказов

        • Выбирается результат, полученный исправными исполнителями

        • Принцип работы:

          • Каждый файл имеет номер версии

          • Каждой копии файла приписано некоторое количество голосов.

          • Для получения права на запись писателю требуется запросить разрешение у всех серверов и получить Vw голосов от тех из них, кто владеет последней версией копии.

          • Для записи информации в файл писатель рассылает ее всем владельцам текущей версии файла и должен получить V_w голосов от тех, кто успешно выполнил запись.

          • Для получения права на чтение читателю достаточно получить Vr голосов от любых серверов.

          • Vr выбрано так, что среди ответивших серверов найдется хотя бы один с последней версией файла.

          • Два подхода: статическое и динамическое распределение голосов

          • Может понадобиться динамическое изменение состава (если какой-то сервер отказал).

      • Протоколы принятия коллективного решения

        • Два класса

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

          • Протоколы принятия согласованных решений – на основе полученных исправными исполнителями данных от остальных исправных исполнителей.

        • Алгоритм надежных широковещательных рассылок сбщ (жопа)

    • Избыточность. Достигается

      • Использование режимы «горячего резерва» (резервное ПО)

      • Использование активного размножения (размножение файлов в распределенной ФС)

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

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

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

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

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

Список файлов лекций