История ОС е и 1950-е "Персональные ЭВМ" - "пультовый режим" Библиотека программ ввода-вывода, служебная программа. Середина 1950-х Пакетная обработка. Однопрограммный и мультипрограммный режимы. Инструкция оператору -> паспорт задачи (простейший язык управления заданиями). Требования к аппаратуре: защита памяти; прерывания; привилегированный режим; таймер. Середина 1960-х Режим разделения времени. Терминалы, квантование, свопинг, страничная и сегментная организация е Многопроцессорные ЭВМ, многомашинные комплексы, сети ЭВМ 1980-е Персональные ЭВМ 1990-е MPP, открытые системы, Internet

1.Введение в параллельные и распределенные системы 1.1 Достоинства многопроцессорных систем с общей памятью (мультипроцессоров) 1.Производительность 2.Надежность Недостатки мультипроцессоров 1.ПО (приложения, языки, ОС) сложнее, чем для однопроцессорных ЭВМ 2.Ограниченность при наращивании (физ. размеры - близость к памяти, 64 процессора - максимально достигнутое).

Распределенная система - совокупность независимых компьютеров, которая представляется пользователю единым компьютером. Примеры: сеть рабочих станций (выбор процессора для выполнения программы, единая файловая система), роботизированный завод (роботы связаны с разными компьютерами, но действуют как внешние устройства единого компьютера, банк со множеством филиалов, система резервирования авиабилетов. Почему создаются распределенные системы? В чем их преимущества перед централизованными ЭВМ? 1-ая причина - экономическая. Закон Гроша (Herb Grosh, 25 лет назад)- быстродействие процессора пропорциональна квадрату его стоимости. С появлением микропроцессоров закон перестал действовать - за двойную цену можно получить тот же процессор с несколько большей частотой. 2-ая причина - можно достичь такой высокой производительности путем объединения микропроцессоров, которая недостижима в централизованном компьютере. 3-я причина - естественная распределенность (банк, поддержка совместной работы группы пользователей ). 4-ая причина - надежность (выход из строя нескольких узлов незначительно снизит производительность). 5-я причина - наращиваемость производительности. В будущем главной причиной будет наличие огромного количества персональных компьютеров и необходимость совместной работы без ощущения неудобства от географического и физического распределения людей, данных и машин.

Почему нужно объединять PC в сети? 1.Необходимость разделять данные. 2.Преимущество разделения дорогих периферийных устройств, уникальных информационных и программных ресурсов. 3.Достижение развитых коммуникаций между людьми. Электронная почта во многих случаях удобнее писем, телефонов и факсов. 4.Гибкость использования различных ЭВМ, распределение нагрузки. 5.Упрощение постепенной модернизации посредством замены компъютеров. Недостатки распределенных систем: 1.Проблемы ПО (приложения, языки, ОС). 2.Проблемы коммуникационной сети (потери информации, перегрузка,развитие и замена). 3.Секретность.

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

Сетевая ОСРаспределенная ОС ОС мультипроцессора Компьютерная система выглядит как виртуальная однопроцессорная ЭВМ НЕТДА Одна и та же ОС выполняется на всех процессорах НЕТДА Сколько копий ОС имеется в памяти NN1 Как осуществляются коммуникации Разделяемые файлыСообщенияРазделяемая память Требуется ли согласованный сетевой протокол ДА НЕТ Имеется ли единая очередь выполняющихся процессов НЕТ ДА Имеется хорошо определенная семантика разделения файлов Обычно НЕТДА

Прозрачность расположения Пользователь не должен знать, где расположены ресурсы Прозрачность миграции Ресурсы могут перемещаться без изменения их имен Прозрачность размножения Пользователь не должен знать, сколько копий существует Прозрачность конкуренции Множество пользователей разделяет ресурсы автоматически Прозрачность параллелизма Работа может выполняться параллельно без участия пользователя 1.4. Принципы построения распределенных ОС (прозрачность, гибкость, надежность, эффективность, масштабируемость) (1) Прозрачность (для пользователя и программы).

(2) Гибкость (не все еще ясно - потребуется менять решения). Использование монолитного ядра ОС или микроядра. (3) Надежность. Доступность, устойчивость к ошибкам (fault tolerance). Секретность. (4) Производительность. Грануллированность. Мелкозернистый и крупнозернистый параллелизм (fine-grained parallelism, coarse-grained parallelism). Устойчивость к ошибкам требует дополнительных накладных расходов. (5) Масштабируемость.

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

2. Операционные системы мультипроцессорных ЭВМ Организация ОС: главный-подчиненный (master-slave, выделение одного процессора для ОС упрощает ее, но этот процессор становится узким местом с точки зрения загруженности и надежности); симметричная (наиболее эффективная и сложная). Процесс - это выполнение программы. Компоненты процесса - выполняющаяся программа, ее данные, ее ресурсы (например, память), и состояние выполнения. Традиционно, процесс имеет собственное адресное пространство и его состояние характеризуется следующей информацией:

таблицы страниц (или сегментов); дескрипторы файлов; заказы на ввод-вывод; регистры; и т.п. Большой объем этой информации делает дорогими операции создания процессов, их переключение. Потребность в легковесных процессах, нитях (threads) возникла еще на однопроцессорных ЭВМ (физические процессы или их моделирование, совмещение обменов и счета), но для использования достоинств многопроцессорных ЭВМ с общей памятью они просто необходимы. Процессы могут быть независимыми, которые не требуют какой-либо синхронизации и обмена информацией (но могут конкурировать за ресурсы), либо взаимодействующими.

2.2. Взаимодействие процессов Если приложение реализовано в виде множества процессов (или нитей), то эти процессы (нити) могут взаимодействовать двумя основными способами: посредством разделения памяти (оперативной или внешней) посредством передачи сообщений При взаимодействии через общую память процессы должны синхронизовать свое выполнение. Различают два вида синхронизации - взаимное исключение критических интервалов и координация процессов. Критические секции. Недетерминизм, race condition (условия гонок).

Процесс p1Процесс p2 Load R1,I Load R2,J Add R1,R2Sub R1,R2 Store R1,I Процесс p1 выполняет оператор I = I+J, а процесс p2 - оператор I = I-J. Машинные коды выглядят так: Результат зависит от порядка выполнения этих команд. Требуется взаимное исключение критических интервалов.

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

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

Когда в машине имеется лишь один процессор, параллельные процессы не могут перекрываться, а способны только чередоваться. Кроме того, процесс будет продолжаться до тех пор, пока не будет вызван сервис операционной системы или пока процесс не будет прерван. Следовательно, для того чтобы гарантировать взаимное исключение, достаточно защитить процесс от прерывания. Эта возможность может быть обеспечена в форме примитивов, определенных системным ядром для запрета и разрешения прерываний. Процесс в таком случае может обеспечить взаимоисключение следующим образом: while (true) { /* Запрет прерываний */; /* Критический раздел */; /* Разрешение прерываний */; /* Остальной код */; }

Наиболее общим механизмом может служить ограничение, согласно которому к некоторой ячейке памяти в определенный момент времени может осуществляться только одно обращение. Воспользовавшись этим ограничением, зарезервируем глобальную ячейку памяти, которую назовем turn. Процесс (РО или Р1), который намерен выполнить критический раздел, сначала проверяет содержимое ячейки памяти turn. Если значение turn равно номеру процесса, то процесс может войти в критический раздел; в противном случае он должен ждать, постоянно опрашивая значение turn до тех пор, пока оно не позволит процессу войти в критический раздел. Такая процедура известна как пережидание занятости (busy waiting),

После того как процесс, получивший право на вход в критический раздел, выходит из него по завершении работы, он должен обновить значение turn, присвоив ему номер другого процесса. Говоря формально, имеется глобальная переменная: int turn = 0; Это решение гарантирует корректную работу взаимоисключения, однако имеет два недостатка.

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

По сути, каждый процесс должен иметь собственный ключ к критическому разделу, так что если даже произойдет сбой одного процесса, второй все равно сможет получить доступ к критическому разделу. Для удовлетворения этого условия определен логический вектор flag, в котором flag[0] соответствует процессу РО, a flag[l] процессу Р1. Каждый процесс может ознакомиться с флагом другого процесса, но не может его изменить. Когда процессу требуется войти в критический раздел, он периодически проверяет состояние флага другого процесса до тех пор, пока тот не примет значение false, указывающее, что другой процесс покинул критический раздел. Процесс немедленно устанавливает значение своего собственного флага равным true и входит в критический раздел. По выходе из критического раздела процесс сбрасывает свой флаг, присваивая ему значение true.

Теперь разделяемые переменные выглядят следующим образом: enum boolean { false = 0, true =1; }; boolean flag[2] = { false, false }; Теперь если произойдет сбой одного из процессов вне критического раздела (включая код установки значения флага), то второй процесс заблокирован не будет. Этот второй процесс в таком случае сможет входить в критический раздел всякий раз, как только это потребуется.

Рассмотрим такую последовательность действий: РО выполняет инструкцию while и находит, что значение flag[l] равно false; PI выполняет инструкцию while и находит, что значение flag[0] равно false; РО устанавливает значение flag [0] равным true и входит в критический раздел; Р1 устанавливает значение flag [1] равным true и входит в критический раздел. Поскольку после этого оба процесса одновременно оказываются в критическом разделе, программа некорректна. Проблема заключается в том, что предложенное решение не является независимым от относительной скорости выполнения процессов

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

РО устанавливает значение flag[0] равным true; PI устанавливает значение flag[1] равным true; РО проверяет flag [ 1 ]; PI проверяет flag [ 0 ]; РО устанавливает значение flag[0] равным false; PI устанавливает значение flag[l] равным false; РО устанавливает значение flag[0] равным true; PI устанавливает значение flag[l] равным true. Эту последовательность можно продолжать до бесконечности и ни один из процессов до бесконечности так и не сможет войти в критический раздел. Строго говоря, это не взаимоблокировка, так как любое изменение относительной скорости двух процессов разорвет замкнутый круг и позволит одному из процессов войти в критический раздел.

У нас должна быть возможность следить за состоянием обоих процессов, что обеспечивается массивом flag и мы должны навязать определенный порядок действий двум процессам, чтобы избежать проблемы взаимной вежливости. С этой целью можно использовать переменную turn из первой попытки. Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критческую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов (индикаторов "намерения" войти в критическую секцию) и переменной turn (показывающей, очередь какого из процессов наступила).критическую секциюфлагов

flag[0] := false flag[1] := false Алгоритм Деккера turn := 0 // or 1 p0: flag[0] := true while flag[1] = true { if turn 0 { flag[0] := false while turn 0 { } flag[0] := true } // критическая секция... turn := 1 flag[0] := false // конец критической секции... p1: flag[1] := true while flag[0] = true { if turn 1 { flag[1] := false while turn 1 { } flag[1] := true } // критическая секция... turn := 0 flag[1] := false // конец критической секции

Процессы объявляют о намерении войти в критическую секцию; это проверяется внешним циклом «while». Если другой процесс не заявил о таком намерении, в критическую секцию можно безопасно войти (вне зависимости от того, чья сейчас очередь). Взаимное исключение всё равно будет гарантировано, так как ни один из процессов не может войти в критическую секцию до установки этого флага (подразумевается, что, по крайней мере, один процесс войдёт в цикл «while»). Это также гарантирует продвижение, так как не будет ожидания процесса, оставившего «намерение» войти в критическую секцию. В ином случае, если переменная другого процесса была установлена, входят в цикл «while» и переменная turn будет показывать, кому разрешено войти в критическую секцию. Процесс, чья очередь не наступила, оставляет намерение войти в критическую секцию до тех пор, пока не придёт его очередь (внутренний цикл «while»). Процесс, чья очередь пришла, выйдет из цикла «while» и войдёт в критическую секцию.

Одним из преимуществ алгоритма является то, что он не требует специальных Test-and-set (атомарная операция чтения, модификации и записи) инструкций и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость только к случаю с ровно двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).Test-and-setатомарнаяBusy waiting Современные операционные системы предоставляют примитивы синхронизации более общие и гибкие по сравнению с алгоритмом Деккера. Тем не менее, следует заметить, что в случае отсутствия реальной конкуренции между двумя процессами, операции входа в критическую секцию и выхода из неё будут являться очень эффективными при использовании этого алгоритма

Более простое решение – алгоритм Петерсона Используются те же переменные, что и в алгоритме Деккера. После установки своего флага процесс тут же передаёт свой ход (turn) другому. Ожидая оба условия одновременно, мы избегаем необходимости очищать и переустанавливать флаг. Ни один процесс не будет неопределенно долго ждать разрешения на вход в критическую секцию. При входе в критическую секцию процесс передает свой ход. Если другой процесс уже ждёт, то он продолжит свое выполнение.

typedef char booleans; shared boolean flags[n-1]; shared int turn; turn=i; flags[i]=FREE; flags[j]=FREE; /* claim the resource */ flags [i] = BUSY; /* give away the turn */ turn = j; /* wait while the other process is using the resource and has the turn */ while ((flags[j]==BUSY) && (turn!=i)) {} /* release the resource */ flags[i] = FREE;

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом: V(S) : переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции. P(S) : уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией. Короче Семафор – это неотрицательная целая переменная, которая может изменяться и проверяться только посредством двух функций: 1. P - функция запроса семафора P(s): [if (s == 0) ; else s = s-1;] 2. V - функция освобождения семафора V(s): [if (s == 0) ; s = s+1;]

Семафоры - переменные для подсчета сигналов запуска, сохраненных на будущее. Фундаментальный принцип заключается в том, что два или большее количество процессов могут сотрудничать посредством простых сигналов, так что в определенном месте процесс может приостановить работу до тех пор, пока не дождется соответствующего сигнала. Требования кооперации любой степени сложности могут быть удовлетворены соответствующей структурой сигналов. Для сигнализации используются специальные переменные, называющиеся семафорами. Для передачи сигнала через семафор s процесс выполняет примитив signal (s), а для получения сигнала примитив wait(s). В последнем случае процесс приостанавливается до тех пор, пока не осуществится передача соответствующего сигнала. Для достижения желаемого эффекта мы можем рассматривать семафор как переменную, имеющую целое значение. В статье Дейкстры и многих других источниках вместо wait используется буква Р. а вместо signal V ; это первые буквы голландских слов проверка (proberen ) и увеличение (verhogen ).

В листинге приведено более формальное определение примитивов семафоров. Предполагается, что примитивы wait и signal атомарны, т.е. они не могут быть прерваны, и каждая из подпрограмм может рассматриваться как единый шаг. Определение семафорных примитивов struct semaphore { int count; queueType queue; } void wait(semaphore s) { s.count--; if (s.count < 0} ( Поместить процесс в s.queue Заблокировать процесс } } void signal(semaphore s) { s.count++; if ( s.count

Для хранения процессов, ожидающих как обычные, так и бинарные семафоры, используется очередь. При этом возникает вопрос о порядке извлечения процессов из данной очереди. Наиболее корректный способ использование принципа первым вошел - первым вышел {first-in-first-out - FIFO). При этом первым из очереди освобождается процесс, который был заблокирован дольше других. Семафор, использующий данный метод, называется сильным семафором (strong semaphore). Семафор, порядок извлечения процессов из очереди которого не определен, называется слабым семафором (weak semaphore). Как упоминалось ранее, главное условие корректности работы семафоров заключается в требовании атомарности операций wait и signal. Один из очевидных путей выполнения этого условия состоит в реализации семафоров в аппаратном или микропрограммном обеспечении. Если этот путь недоступен, применяются различные программные подходы. Суть проблемы заключается в реализации взаимных исключений: в определенный момент времени работать с семафором посредством операций wait или signal может только один процесс. Следовательно, подойдет любая из рассматривавшихся программных схем, такая, как алгоритмы Деккера или Петерсона; но это может привести к определенным накладным расходам. Можно также использовать одну из схем поддержки взаимоисключений на аппаратном уровне.

Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов, выполняющихся в режиме мультипрограммирования, один из которых пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. Процесс "писатель" должен приостанавливаться, когда все буфера оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, процесс "читатель" приостанавливается, когда все буферы пусты, и активизируется при появлении хотя бы одной записи. put get Producer BufferConsumer

Решение проблемы переполненного буфера с помощью семафора Применим три семафора: full - подсчет заполненных сегментов (в начале = 0) empty - подсчет пустых сегментов (в начале = количеству сегментов) mutex - для исключения одновременного доступа к буферу двух процессов. (в начале = 1) Мьютекс упрощенная версия семафора, он управляет доступом к ресурсу. Показывает, блокирован или нет ресурс