Операционные системы распределенных вычислительных систем
Операционные системы распределенных вычислительных систем
Операционные системы распределенных вычислительных систем (распределенные ОС).
(Крюков В.А.)
Распределенная система - совокупность независимых компьютеров, которая представляется пользователю единым компьютером (metacomputer), использование которого не намного сложнее, чем использование персональной ЭВМ.
Введение в ОС однопроцессорных ЭВМ.
Два взгляда:
· менеджер ресурсов;
· один слой в множестве слоев абстрактных машин.
Представление ОС как менеджера ресурсов
| Управление файлами | |||||
| Управление процессами | Управление памятью | Управление устройствами | |||
| Процессоры | Память | Устройства |
Представление ОС как абстрактной машины
| Абстрактная машина | |||||
| Интерфейс пользователя | Интерфейс программы | ||||
| Языки управления заданиями Командные языки Окна, меню, пиктограммы | Система команд | Системные вызовы Процессы Память Файлы Информационные функции |
Место ОС среди ПО
| Прикладное ПО (отдельные приложения, пакеты прикладных программ, информационные системы, САПР) | |
| Системное ПО (ОС + системы программирования, СУБД, графические библиотеки, сервисные программы) |
История ОС.
1940-е и 1950-е
"Персональные ЭВМ" - "пультовый режим"
Библиотека программ ввода-вывода, служебная программа.
Середина 1950-х
Пакетная обработка. Однопрограммный и мультипрограммный режимы.
Инструкция оператору -> паспорт задачи (простейший язык управления заданиями).
Требования к аппаратуре:
· защита памяти;
· прерывания;
· привилегированный режим;
· таймер.
Как обеспечить мультипрограммный режим без таких механизмов.
Середина 1960-х
Режим разделения времени.
Терминалы, квантование, свопинг, страничная и сегментная организация.
1970-е
Многопроцессорные ЭВМ, многомашинные комплексы, сети ЭВМ
1980-е
Персональные ЭВМ
1990-е
MPP, открытые системы, Internet
*********Лекция 2
1 Введение в параллельные и распределенные системы
1.1 Достоинства многопроцессорных систем с общей памятью (мультипроцессоров)
(1) Производительность
(2) Надежность
1.2. Недостатки
(1) ПО (приложения, языки, ОС) сложнее, чем для однопроцессорных ЭВМ
(2) Ограниченность при наращивании (физ. размеры - близость к памяти, 64 процессора - максимально достигнутое).
1.2 Достоинства распределенных систем
Распределенная система - совокупность независимых компьютеров, которая представляется пользователю единым компьютером.
Примеры: сеть рабочих станций (выбор процессора для выполнения программы, единая файловая система), роботизированный завод (роботы связаны с разными компьютерами, но действуют как внешние устройства единого компьютера, банк со множеством филиалов, система резервирования авиабилетов.
Почему создаются распределенные системы? В чем их преимущества перед централизованными ЭВМ?
1-ая причина - экономическая.
Закон Гроша (Herb Grosh, 25 лет назад)- быстродействие процессора пропорциональна квадрату его стоимости. С появлением микропроцессоров закон перестал действовать - за двойную цену можно получить тот же процессор с несколько большей частотой.
2-ая причина - можно достичь такой высокой производительности путем объединения микропроцессоров, которая недостижима в централизованном компьютере.
3-я причина - естественная распределенность (банк, поддержка совместной работы группы пользователей ).
4-ая причина - надежность (выход из строя нескольких узлов незначительно снизит производительность).
5-я причина - наращиваемость производительности.
В будущем главной причиной будет наличие огромного количества персональных компьютеров и необходимость совместной работы без ощущения неудобства от географического и физического распределения людей, данных и машин.
Почему нужно объединять PC в сети?
1. Необходимость разделять данные.
2. Преимущество разделения дорогих периферийных устройств, уникальных информационных и программных ресурсов.
3. Достижение развитых коммуникаций между людьми. Электронная почта во многих случаях удобнее писем, телефонов и факсов.
4. Гибкость использования различных ЭВМ, распределение нагрузки.
5. Упрощение постепенной модернизации посредством замены компъютеров.
Недостатки распределенных систем:
1. Проблемы ПО (приложения, языки , ОС).
2. Проблемы коммуникационной сети (потери информации, перегрузка, развитие и замена).
3. Секретность.
1.3 Виды операционных систем (сетевые ОС, распределенные ОС, ОС мультипроцессоров).
Сетевые ОС - машины обладают высокой степенью автономности, общесистемных требований мало. Можно вести диалог с другой ЭВМ, вводить задания в ее очередь пакетных заданий, иметь доступ к удаленным файлам, хотя иерархия директорий может быть разной для разных клиентов. Пример - серверы файлов (многие WS могут не иметь дисков вообще).
Распределенные ОС - единый глобальный межпроцессный коммуникационный механизм, глобальная схема контроля доступа, одинаковое видение файловой системы. Вообще - иллюзия единой ЭВМ.
ОС мультипроцессоров
- единая очередь процессов, ожидающих выполнения, одна файловая система.
|
Сетевая ОС |
Распределенная ОС |
ОС мульти процессора |
|
|
Компьютерная система выглядит как виртуальная однопроцессорная ЭВМ |
НЕТ |
ДА |
ДА |
|
Одна и та же ОС выполняется на всех процессорах |
НЕТ |
ДА |
ДА |
|
Сколько копий ОС имеется в памяти |
N |
N |
1 |
|
Как осуществляются коммуникации |
Разделяемые файлы |
Сообщения |
Разделяемая память |
|
Требуется ли согласованный сетевой протокол |
ДА |
ДА |
НЕТ |
|
Имеется ли единая очередь выполняющихся процессов |
НЕТ |
НЕТ |
ДА |
|
Имеется хорошо определенная семантика разделения файлов |
Обычно НЕТ |
ДА |
ДА |
/p> 1.4. Принципы построения распределенных ОС (прозрачность, гибкость, надежность, эффективность, масштабируемость).
(1) Прозрачность (для пользователя и программы).
|
Прозрачность расположения |
Пользователь не должен знать, где расположены ресурсы |
|
Прозрачность миграции |
Ресурсы могут перемещаться без изменения их имен |
|
Прозрачность размножения |
Пользователь не должен знать, сколько копий существует |
|
Прозрачность конкуренции |
Множество пользователей разделяет ресурсы автоматически |
|
Прозрачность параллелизма |
Работа может выполняться параллельно без участия пользователя |
Использование монолитного ядра ОС или микроядра.
(3) Надежность.
Доступность, устойчивость к ошибкам (fault tolerance).
Секретность.
(4) Производительность.
Грануллированность. Мелкозернистый и крупнозернистый параллелизм (fine-grained parallelism, coarse-grained parallelism).
Устойчивость к ошибкам требует дополнительных накладных расходов.
(5) Масштабируемость.
Плохие решения:
· централизованные компоненты (один почтовый-сервер);
· централизованные таблицы (один телефонный справочник);
· централизованные алгоритмы (маршрутизатор на основе полной информации).
Только децентрализованные алгоритмы со следующими чертами:
· ни одна машина не имеет полной информации о состоянии системы;
· машины принимают решения на основе только локальной информации;
· выход из строя одной машины не должен приводить к отказу алгоритма;
· не должно быть неявного предположения о существовании глобальных часов.
Литература
1. DISTRIBUTED OPERATING SYSTEMS. Andrew S. Tanenbaum, Prentice-Hall, Inc., 1995
2. ADVANCED CONCEPTS IN OPERATING SYSTEMS. Mukesh Singhal, Niranjan G. Shivaratri, McGraw-Hill, Inc., 1994
3. CENTRALIZED AND DISTRIBUTED OPERATING SYSTEMS. Gary J. Nutt, Prentice-Hall, Inc., 1992
4. David W. Walker, "The design of a standard message-passing interface for distributed memory concurrent computers", Parallel Computing, v.20, n 4, April 1994, 657-673. (www.mpi-forum.org)
5. A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, V. Sunderam, “PVM 3 User’s Guide and Reference Manual”, Technical report, Oak Ridge National Laboratory ORNL/TM-12187 (1993).
Тема-1
1. (Т1) Какие аппаратные механизмы необходимы для организации мультипрограммного режима? Как обеспечить мультипрограммный режим без этих механизмов? Как обеспечить, если отсутствует только один из них?
Тема-2
1. (Т2) Если в алгоритме Деккера не изменять значение переменной turn при выходе из критической секции, то каким требованиям он перестанет удовлетворять? Объясните, почему.
2. (T2) Имеется механизм двоичных семафоров. Опираясь на него, реализуйте P-операцию и V-операцию для общего (считающего) семафора.
3. (Т2) Имеется механизм двоичных семафоров. Опираясь на него, реализуйте операторы POST(имя переменной-события) и WAIT(имя переменной-события).
4. (T2) Имеется команда TSL и команда объявления прерывания указанному процессору. Опираясь на него, реализуйте на мультипроцессоре P-операцию и V-операцию для двоичного семафора.
5. (Т2) Правильно ли использованы события в алгоритме, который реализует метод верхней релаксации? Оцените, насколько этот алгоритм можно выполнить быстрее, чем последовательный, если число процессоров мультипроцессора = N, время выполнения одного оператора присваивания (A[i][j]=....) равно 1, временами выполнения остальных операторов можно пренебречь.
float A[ L1 ][ L2 ];
struct condition s[ L1 ][ L2 ];
for ( i = 0; i < L1; i++)
for ( j = 0; j < L2; j++) { clear( s[ i ][ j ]) }
for ( j = 0; j < L2; j++) { post( s[ 0 ][ j ]) }
parfor ( i = 1; i < L1-1; i++)
for ( j = 1; j < L2-1; j++)
{ wait( s[ i-1 ][ j ]);
A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;
post( s[ i ][ j ]);
}
Тема-3
1. (Т3) В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию барьер (MPI_BARRIER) для всех процессов. Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно Ts, время передачи байта равно Tb (Ts=10,Tb=2). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
2. (Т3) В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию передачи сообщения длиной N байт всем процессам от одного (MPI_BCAST) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
3. (Т3) В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию сбора данных от всех процессов (длиной один байт) для одного (MPI_GATHER) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
4. (Т3) В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию рассылки данных (длиной один байт) всем процессам от одного (MPI_SCATTER) - процесса с координатами (0,0).
Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
5. (Т3) В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию суммирования 16 чисел (каждый процесс имеет свое число). Сколько времени потребуется для получения всеми суммы, если все процессы выдали эту операцию редукции одновременно? А сколько времени потребуется для суммирования 64 чисел в матрице 8*8? Время старта равно единице, время передачи байта равно нулю (Ts=1,Tb=0). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
6. (Т3) В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию нахождения максимума среди 16 чисел (каждый процесс имеет свое число). Сколько времени потребуется для получения всеми максимального числа, если все процессы выдали эту операцию редукции одновременно. А сколько времени потребуется для нахождения максимума среди 64 чисел в матрице 8*8? Время старта равно единице, время передачи байта равно нулю (Ts=1,Tb=0). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
7. (Т3) В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать очень длинное сообщение (длиной L байт) из узла с координатами (0,0) в узел с координатами (3,3). Сколько времени потребуется для этого. А сколько времени потребуется для пересылки из узла с координатами (1,1) в узел с координатами (2,2). Время старта равно времени передачи байта (Ts=Tb). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
8. (Т3) В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать сообщение длиной L байт из узла с координатами (0,0) в узел с координатами (3,3).
Сколько времени потребуется для этого, если передача сообщений выполняется в буферизуемом режиме MPI? А сколько времени потребуется при использовании синхронного режима и режима готовности? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
9. (Т3) В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать сообщение длиной L байт из узла с координатами (0,0) в узел с координатами (3,3). Сколько времени потребуется для этого при использовании а) неблокирующих и б) блокирующих операций MPI? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
Тема-4
1. (Т4) Все 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется круговой маркерный алгоритм. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
2. (Т4) Все 16 процессов, находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется древовидный маркерный алгоритм. Время старта (время «разгона» после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
3. (Т4) Все 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос на вход в критическую секцию.
Сколько времени потребуется для прохождения всеми критических секций, если используется децентрализованный алгоритм с временными метками. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
4. (Т4) Все 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется широковещательный маркерный алгоритм. Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
5. (Т4) 15 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, одновременно выдали запрос на вход в критическую секцию. Сколько времени потребуется для прохождения всеми критических секций, если используется централизованный алгоритм (координатор расположен в узле 0,0)? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
6. (Т4) Сколько времени потребует выбор координатора среди 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, если используется алгоритм «задиры»? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. «Задира» расположен в узле с координатами (0,0) и имеет уникальный номер 0.
7. (Т4) Сколько времени потребует выбор координатора среди 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, если используется круговой алгоритм? Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
Тема-5
1. (T5) Какие принципиальные решения приходится принимать при обеспечении файлового сервиса?
2. (T5)
Интерфейс сервера директорий.
3. (T5)
Семантика разделения файлов.
4. (T5) Серверы с состоянием и без состояния. Достоинства и недостатки.
5. (T5) Алгоритмы обеспечения консистентности кэшей в распределенных файловых системах.
6. (T5) Способы организации размножения файлов и коррекции копий.
Тема-6
1. (Т6) Какие модели консистентности памяти удовлетворяют алгоритму Деккера (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.
2. (Т6) Какие модели консистентности памяти удовлетворяют алгоритму Петерсона (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.
3. (T6) Последовательная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация 10 различных переменных 10-ю процессами (каждый процесс модифицирует одну переменную), находящимися на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания) и одновременно выдавшими запрос на модификацию. Время старта (время «разгона» после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
4. (T6) Причинная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация 10 различных переменных, если все 10 процессов (каждый процесс модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию своей переменной.
Время старта (время «разгона» после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми. Никаких сведений от компилятора о причинной зависимости операций модификации не имеется.
5. (T6)
Процессорная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация 10 различных переменных, если все 10 процессов (каждый процесс модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию своей переменной. Время старта (время «разгона» после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
6. (T6) PRAM консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует 3-кратная модификация 10 различных переменных, если все 10 процессов (каждый процесс 3 раза модифицирует одну переменную), находящихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания), одновременно выдали запрос на модификацию. Время старта (время «разгона» после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
7. (T6) Слабая консистентность памяти и алгоритм ее реализации в DSM с полным размножением.
Сколько времени потребует модификация одним процессом 10 обычных переменных, а затем 3-х различных синхронизационных переменных, если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания). Время старта (время «разгона» после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
8. (T6)
Консистентность памяти по выходу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение критической секции и модификация в ней 10 переменных каждым процессом , если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещания). Время старта (время «разгона» после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
9. (T6) Консистентность памяти по входу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение критической секции и модификация в ней 10 переменных каждым процессом, если DSM реализована на 10 ЭВМ сети с шинной организацией(с аппаратными возможностями широковещания). Время старта (время «разгона» после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.
