выше эффективность (информация об открытых файлах может храниться в оперативной памяти).

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

убедиться в достоверности запроса легче, если есть состояние (например, хранить номер последнего запроса).

возможна операция захвата файла.

Серверы без состояния. Достоинства.

устойчивость к ошибкам.

не требуется операций ОТКРЫТЬ/ЗАКРЫТЬ.

не требуется память для таблиц.

нет ограничений на число открытых файлов.

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

1. Алгоритмы обеспечения консистентности кэшей в распределенных файловых системах.

• кэширование на сервере/на клиенте/диске клиента

• кэш в памяти клиента: в процессе/в ядре/кэш-менеджер

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

1. Способы организации размножения файлов и коррекции копий.

• цели: надежность/доступность/распределение нагрузки

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

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

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

• Коррекция: главная копия/голосование/

Тема-6

1. Последовательная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация 10 различных переменных 10-ю процессами (каждый процесс модифицирует одну переменную), находящимися на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания) и одновременно выдавшими запрос на модификацию. Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Последовательная консистентность – все процессы видят одну и ту же последовательность записей в память.(Как будто память едина и в каждый момент времени исполняется ровно одна команда какого-то процесса).

Из лекции:

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

Не из лекции: с процессом-координатором.

Реализация последовательной консистентности в DSM с полным размножением:

а) при записи:

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

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

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

• Координатор рассылает всем (кроме автора) модификацию.

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

б)при чтении:

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

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

г) блокируется ли процесс на время выполнения записи или рассылки значений переменных:

процесс – автор блокируется до записи для получения консистентной версии памяти.

Считаем, что всего 10 процессов/процессоров. 1 из них – координатор.

10 процессов модифицируют 10 переменных.

Каждый процесс посылает координатору запрос на модификацию. 9 сообщений (1 сообщение будет локальным). В ответ на каждый запрос на модификацию координатор вышлет 9 номеров и 9 модификаций. Координатору будут переданы 9 модифицированных блоков данных.

Итого получается 9*(9+9) сообщений = 9*(18* Ts+9*Tb*Ln+9*Tb*Lm+5*Tb*Lm)

1. Причинная консистентность памяти и алгоритм ее реализации в DSM с полным размножением при условии, что никаких сведений от компилятора о причинной зависимости операций записи не имеется. Сколько времени потребует модификация 10 различных переменных, если все 10 процессов (каждый процесс модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию своей переменной. Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

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

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

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

1. Процессорная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация 10 различных переменных, если все 10 процессов (каждый процесс модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию своей переменной. Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Процессорная консистентность – каждый процессор видит модификации, производимые одним процессором, в том же порядке, как они были произведены. Кроме того по каждой переменной есть согласие относительно поядка её модификаций.

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

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

а) при записи

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

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

• координатору при изменении

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

• процессам периодически (по таймеру/ при определенной длины последовательности и т.д) --- это приводит все копии данных в одинаковое состояние.

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

Временная оценка: в лучшем случае модификация закончится за 20*(Ts+ Tb*Lm). При этом ещё за время 10*(Ts+Tb*9*Lm) все процессы получат полный набор модификаций.

1. PRAM консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует 3-кратная модификация 10 различных переменных, если все 10 процессов (каждый процесс 3 раза модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию. Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

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

Производя запись процессор должен записать в локальную память и разослать всем свои изменения.Здесь требуется надёжность при передаче сообщений по каналам при сохранении их порядка.

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

Потребуется 9*3* (Ts+Tb*Lm)

1. Слабая консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация одним процессом 10 обычных переменных, а затем 3-х различных синхронизационных переменных, если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания). Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

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

а) при модификации обычных данных записываются в локальную память.

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

б) при чтении обычных данных они берутся из локальной памяти

при чтении синхр. переменных обращение к координатору происходит так же, как при записи.

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

Временная оценка: Ts+Tb*Lm*11+Ts*2+Tb*Lm*2= 3*Ts+13*Lm

1. Консистентность памяти по выходу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение каждым процессом критической секции, в которой модифицируются 10 переменных, если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания). Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

3*10*(2*(Ts+Tb*Lcs)+(Ts+Tb*Lv*10+Tb*Lcs))

1. Консистентность памяти по входу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение критической секции и модификация в ней 10 переменных каждым процессом, если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания). Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.

3*10*(2*(Ts+Tb*Lcs)+(Ts+Tb*Lv*10+Tb*Lcs))

Тема-7

1. Алгоритм надежных и неделимых широковещательных рассылок сообщений. Дайте оценку времени выполнения одной операции рассылки для сети из 10 ЭВМ с шинной организацией (без аппаратных возможностей широковещания), если отправитель сломался после посылки 5-го сообщения. Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.