1. Состояние гонки. Race condition.. Ошибка программирования многозадачной системы, при которой работа системы зависит от того, в каком порядке выполняются части кода. Состояние гонки является классическим гейзенбагом. Состояние гонки возникает тогда, когда несколько потоков многопоточного приложения пытаются одновременно получить доступ к данным, причем хотя бы один поток выполняет запись. Для предотвращения состояния гонки используются приемы синхронизации, позволяющие правильно упорядочить операции, выполняемые разными потоками. Приведем пример. Пусть, один поток выполняет над общей переменной x операцию x = x + 3, а второй поток - операцию x = x + 5. Данные операции для каждого потока фактически разбиваются на три отдельных подоперации: считать x из памяти, увеличить x, записать x в память. В зависимости от взаимного порядка выполнения потоками подопераций финальное значение переменной x может быть больше исходного на 3, 5 или 8.

2. Критическая секция — часть программы, в которой есть обращение к совместно используемым данным. При нахождении в критической секции двух (или более) процессов, возникает состояние «гонки» («состязания»). Для избежания данной ситуации необходимо выполнение четырех условий:1. Два процесса не должны одновременно находиться в критических областях.2. В программе не должно быть предположений о скорости или количестве процессоров.

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

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

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

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

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

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

3. Алгоритм Петерсона - программный алгоритм взаимного исключения потоков исполнения кода, разработанный Г. Петерсоном в 1981 г. Хотя изначально был сформулирован для 2-х поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Алгоритм условно называется программным, т.к. не основан на использовании специальных команд процессора для запрета прерываний, блокировки шины памяти и т.д., используются только общие переменные памяти и цикл для ожидания входа в критическую секцию исполняемого кода.

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

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

4. Алгоритм Деккера - первое известное корректное решение проблемы взаимного исключения в конкурентном программировании. Эдсгер Дейкстра ссылается на голландского математика Т. Деккера как на автора данного алгоритма в своей работе о межпроцессном взаимодействии[1]. Он позволяет двум потокам выполнения совместно использовать неразделяемый ресурс без возникновения конфликтов, используя только общую память для коммуникации.

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

5. Test-and-set — простая неразрывная (атомарная) процессорная инструкция, которая копирует значение переменной в регистр, и устанавливает некое новое значение. Во время исполнения данной инструкции процессор не может прервать её выполнение и переключится на выполнение другого потока. Если используется многопроцессорная архитектура, то пока один процессор выполняет эту инструкцию с ячейкой памяти, то другие процессоры не могу получить доступ к этой ячейке, может достигаться путем кратковременного блокирования шины памяти. Она считывает содержимое слова памяти lock в регистр, а по адресу памяти, отведенному для lock, записывает ненулевое значение. При этом гарантируется неделимость операций чтения слова и сохранение в нем нового значения — никакой другой процесс не может получить доступ к слову в памяти, пока команда не завершит свою работу. Центральный процессор, выполняющий команду TSL, блокирует шину памяти, запрещая другим центральным процессорам доступ к памяти до тех пор, пока не будет выполнена эта команда. Альтернативой команде TSL служит команда XCHG, осуществляющая атомарный обмен содержимого двух областей памяти, например регистра и слова памяти. Команда XCHG используется для низкоуровневой синхронизации всеми центральными процессорами семейства Intel х86.

6. Семафор Дейкстры представляет собой целочисленную переменную, с которой ассоциирована очередь ожидающих нитей. Пытаясь пройти через сема-Фор, нить пытается вычесть из значения переменной 1. Если значение переменной больше или равно 1, нить проходит сквозь семафор успешно (семафор открыт). Если переменная равна нулю (семафор закрыт), нить останавливается и ставится в очередь.

Закрытие семафора соответствует захвату объекта или ресурса, доступ к кото-Рому контролируется этим семафором. Если объект захвачен, остальные нити вынуждены ждать его освобождения. Закончив работу с объектом (выйдя из критической секции), нить увеличивает значение семафора на единицу, открывая его. При этом первая из стоявших в очереди нитей активизируется и вычитает из значения семафора единицу, снова закрывая семафор. Если же очередь была пуста, то ничего не происходит, просто семафор остается открытым. Тогда первая нить, подошедшая к семафору, успешно проГцет через него.

7. Активное ожидание. Постоянная проверка значения переменной в ожидании некоторого значения называется активным ожиданием. Этого способа следует избегать, поскольку он является бесцельной тратой процессорного времени. Активное ожидание используется только тогда, когда есть уверенность в небольшом сроке ожидания. Блокировка, использующая активное ожидание называется спин-блокировкой. Вместо циклов ожидания применяются примитивы межпроцессного взаимодействия, которые блокируют процессы в случае запрета на вход в критическую область. Одной из простейших является пара примитивов sleep и wakeup. Примитив sleep – системный запрос, в результате которого вызывающий процесс блокируется, пока его не запустит другой процесс. У запроса wakeup есть один параметр – процесс, который следует запустить. Также возможно наличие одного параметра у обоих запросов – адреса ячейки памяти, используемой для согласования запросов ожидания и запуска.

Два процесса совместно используют буфер ограниченного размера. Один из них, производитель, помещает данные в буфер, а потребитель считывает их оттуда.

8. Два процесса совместно используют буфер ограниченного размера. Один из них, производитель, помещает данные в буфер, а потребитель считывает их оттуда. Трудности начинаются в тот момент, когда производитель хочет поместить в буфер очередную порцию данных и обнаруживает, что буфер полон. Для производителя решением является ожидание, пока потребитель полностью или частично не очистит буфер. Аналогично, если потребитель хочет забрать данные из буфера, а буфер пуст, потребитель уходит в состояние ожидания и выходит из него, как только производитель положит что-нибудь в буфер и разбудит его. Если максимальное число элементов, хранящихся в буфере, равно N, программа производителя должна проверить, не равно ли N значение count прежде, чем поместить в буфер следующую порцию данных. Если значение count равно N, то производитель уходит в состояние ожидания; в противном случае производитель помещает данные в буфер и увеличивает значение count.

Код программы потребителя прост: сначала проверить, не равно ли значение count нулю. Если равно, то уйти в состояние ожидания; иначе забрать порцию данных из буфера и уменьшить значение count.

9. Наиболее простым случаем семафора является двоичный семафор. Начальное значение флаговой переменной такого семафора равно 1, и вообще она может принимать только значения 1 и 0. Двоичный семафор соответствует случаю,когда с разделяемым ресурсом в каждый момент времени может работать толькоодна программа.

10. Монитор - это конструкция параллелизма, которая содержит как данные, так и процедуры, необходимые для управления распределением общего ресурса или группы общих ресурсов. Информация спрятана внутри монитора, процессы, обращающиеся к монитору, не знают, какие данные находятся внутри монитора, и не получают к ним доступа. Монитор – набор процедур, переменных и других структур данных, объединенных в особый модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора. При обращении к монитору в любой момент времени активным может быть только один процесс. Переменные состояния

В отличие от семафоров они не аккумулируют сигналы, чтобы впоследствии воспользоваться ими. Это означает, что в случае выполнения операции signal на переменной состояния, с которой не связано ни одного блокированного процесса, сигнал будет утерян. Проще говоря, операция wait должна выполняться прежде, чем signal. Последнее правило существенно упрощает реализацию. На практике оно не создает проблем, поскольку отслеживать состояния процессов при необходимости не очень трудно. Процесс, который собирается выполнить signal, может оценить необходимость этого действия по значениям переменных.

12. Синхронизация с помощью сообщений (в распределенных системах). К вопросам связи процессов, реализуемой путем передачи сообщений или вызовов RPC, тесно примыкают и вопросы синхронизации процессов. Синхронизация необходима процессам для организации совместного использования ресурсов, таких как файлы или устройства, а также для обмена данными. В однопроцессорных системах решение задач взаимного исключения, критических областей и других проблем синхронизации осуществлялось с использованием общих методов, таких как семафоры и мониторы. Однако эти методы не совсем подходят для распределенных систем, так как все они базируются на использовании разделяемой оперативной памяти. Например, два процесса, которые взаимодействуют, используя семафор, должны иметь доступ к нему. Если оба процесса выполняются на одной и той же машине, они могут иметь совместный доступ к семафору, хранящемуся, например, в ядре, делая системные вызовы. Однако, если процессы выполняются на разных машинах, то этот метод не применим, для распределенных систем нужны новые подходы.

13. Барьеры исполнения. Барьер использования (степень важности – 0,28) – это следствие оторванности описания программных интерфейсов и типов данных от собственно интерфейсов и типов данных. Да и кроме того, следствие невразумительности, нечеткости собственно описаний.Барьер понимания (степень важности – 0,29) возникает из-за огромного отрыва между программой – последовательностью воспринимаемых человеком символов – и программами времени компиляции и исполнения. К слову, многие специалисты склонны считать, что попытки решить эту проблему «в лоб», например максимально сблизив все три фазы существования программы, до сих пор к успехам не приводили. В качестве примера можно использовать замечательную во всех отношениях систему программирования Forth, в которой язык вынуждает программиста держать «в голове» среду времени исполнения программы (если быть точным, стеки Forth-системы).Последний барьер – информационный. Он связан с неочевидностью и сложностью механизмов получения информации о внутреннем поведении программы времени исполнения, с отсутствием четко определенных способов проверки гипотез программиста о внутреннем поведении программы во время исполнения.

14. Взаимная блокировка. Deadlock. Другое название: Тупик. Ситуация в многозадачной системе, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, захваченных самими этими процессами. Приведем пример. Допустим в системе существуют две задачи с низким (А) и высоким (Б) приоритетом, которые используют два ресурса - X и Y. В момент времени T1 задача (А) блокирует ресурс X. Затем в момент времени T2 задачу (А) вытесняет более приоритетная задача (Б), которая в момент времени T3 блокирует ресурс Y. Если задача (Б) попытается заблокировать ресурс X (T4) не освободив ресурс Y, то она будет переведена в состояние ожидания, а выполнение задачи (А) будет продолжено. Если в момент времени T5 задача (А) попытается заблокировать ресурс Y, не освободив X, возникнет состояние взаимной блокировки - ни одна из задач (А) и (Б) не сможет получить управление.

15. Графы. Объявим два множества:

• 

• 

Ресурсный граф – это направленный двудольный граф с непересекающимся множеством ресурсов.

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

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

- дуга запроса, стрелка направлена от процесса к ресурсу, то есть процесс запрашивает одну единицу ресурса.

Наоборот, дуга от ресурса к процессу - дуга назначения, значит процессу выделена одна единица ресурса.

- дуга от расходуемого ресурса – дуга производителя. Обозначает, что процесс является производителем ресурса.

То есть с помощью ресурсного графа можно наглядно увидеть возможность взаимной блокировки.

16.Атака Циклическое ожидание можно устранить несколькими способами. Один из них: просто следовать правилу, гласящему, что процессу дано право только на один ресурс в конкретный момент времени. Если нужен второй ресурс, процесс обязан освободить первый. Но подобное ограничение неприемлемо для процесса, копирующего огромный файл с магнитной ленты на принтер. Потому другой способ уклонения от циклического ожидания заключается в общей нумерации всех ресурсов, тогда действует следующее правило: процессы могут запрашивать ресурс, когда хотят этого, но все запросы должны быть сделаны в соответствии с нумерацией ресурсов.

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

Представим теперь, что после выделения процессу В одного из двух оставшихся принтеров затребует последний принтер. Удовлетворение этого запроса уменьшит значение вектора доступных ресурсов до (1 0 0 0), что приведет к взаимоблокировке. Совершенно ясно, что запрос процесса ? должен быть на некоторое время отклонен.

18. Двухфазовое блокирование. Хотя и уклонение от взаимоблокировок, и предупреждение их возникновения в общем случае оказались не слишком перспективными средствами, для определенных приложений известно множество превосходных алгоритмов специального назначения. К примеру, во многих системах управления базами данных часто встречающимися операциями являются запросы на блокирование нескольких записей с последующим обновлением всех заблокированных записей. Когда одновременно запущено несколько процессов, существует реальная опасность возникновения взаимоблокировок. Часто используемый при этом подход называется двухфазным блокированием. В первой фазе процесс пытается заблокировать по одной все необходимые ему записи. Если все проходит успешно, он приступает ко второй фазе, осуществляя свои обновления и снимая блокировку. При этом в первой фазе не проводится никакой реальной работы. Если в первой фазе встретятся некоторые необходимые записи, которые уже заблокированы, процесс просто снимает все свои блокировки и начинает первую фазу зановоВ некоторых версиях двухфазного блокирования, если заблокированная запись обнаружилась во время первой фазы, то никакого снятия блокировок и перезапуска первой фазы с начала не происходит. Эти версии подвержены возникновению взаимоблокировок.

19. Проблема “Обедающих философов”. Алгоритм Дейкстры. В 1965 году Дейкстра сформулировал и решил проблему синхронизации, названную им проблемой обедающих философов. С тех пор каждый, кто изобретал еще один новый примитив синхронизации, считал своим долгом продемонстрировать достоинства нового примитива на примере проблемы обедающих философов. Проблему можно сформулировать следующим образом: пять философов сидят за круглым столом, и у каждого есть тарелка со спагетти. Спагетти настолько скользкие, что каждому философу нужно две вилки, чтобы с ними управиться. Между каждыми двумя тарелками лежит одна вилка. Жизнь философа состоит из чередующихся периодов поглощения пищи и размышлений. (Разумеется, это абстракция.) Когда философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удалось получить две вилки, он некоторое время ест, затем кладет вилки обратно и продолжает размышления.

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

1. Стратегии выборки:

а) стратегии выборки по запросу (по требованию);

б) стратегии упреждающей выборки.

2. Стратегии размещения.

3. стратегии замещения.

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

21. Учет памяти. Битовые карты.

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

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

22. Учет памяти. Связанные списки. В информатике, свя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями. Связный список - это разновидность линейных структур данных, представляющая собой последовательность элементов, обычно отсортированную в соответствии с заданным правилом. Последовательность может содержать любое количество элементов, поскольку при создании списка используется динамическое распределение памяти. Каждый элемент связного списка представляет собой отдельный объект, содержащий поле для хранения информации и указатель на следующий элемент списка (а в случае двусвязного списка в объекте хранится также указатель на предыдущий элемент).

23. Загрузка программы. Фиксированные адреса. Использование фиксированных адресов упрощает диагностику сети; в этом случае, вызывая команду ping, не приходится выяснять, какой именно адрес присвоен в данный момент тому или иному компьютеру. При наличии фиксированных IP-адресов появляется также возможность вместо адреса указывать при обращении к компьютеру доменное имя. (Далее в этой главе будет обсуждаться способ связывания доменных имен с динамическими IP-адресами.) Программа dhcpd позволяет присваивать компьютерам фиксированные IP-адреса. Для этого надо задать МАС-адреса и сконфигурировать dhcpd так, чтобы МАС-адресу соответствовал определенный IP-адрес. Конфигурация dhcpd для выделения фиксированных адресов несколько сложнее, чем. конфигурация, при которой выполняется динамическое распределение IP-адресов.