Ограничения (слабые места) современных компьютеров (стр. 3 )

http://www. *****/department/os/bmos/12/

http://*****/education/infor1/lecture5-2.htm

20. Взаимное исключение, назначение, требования к реализации. Методы реализации взаимного исключения. Принцип реализации алгоритмов взаимного исключения

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

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

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

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

Решения проблемы критической секции бывают

1)  программная реализация

2)  системная реализация

3)  аппаратная реализация

Программная реализация

Алгоритм Деккера (2 процесса)

Алгоритм Петерсона (n)

Алгоритм булочной (bakery algorithm) (n)

В алгоритме для n процессов используется булевский массив choosing[n]: значение choosing[i] == true будет означать, что в данный момент система определяет номер в очереди i -го процесса. Используется также целочисленный массив number[n]: number[i] будет обозначать вычисленный порядковый номер в очереди (приоритет) i- го процесса.

Алгоритм булочной (для i -го процесса) имеет вид:

do {

choosing[i] = true;

number [i] = max (number[0], number[1], …, number[n-1]) + 1;

choosing[i] = false;

for (j = 0; j < n; j++) {

while choosing[j];

while ((number[j] != 0) && (number[j] < number[i]));

}

критическая секция

number [i] = 0;

остальная часть кода

} while (1)

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

Аппаратная реализация

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

Рассмотрим одну из этих операций, традиционно используемых для синхронизации, - операциюTestAndSet, которая атомарно выполняет считывание и запоминание значения переменной, затем изменяет его на заданное значение, но в результате выдает первоначальное значение переменной.

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

boolean TestAndSet (boolean & target) {

boolean rv = target;

target = true;

return rv;

}

С помощью данной операции реализовать синхронизацию процессов по критическим секциям очень просто. Введем в качестве блокировщика общую булевскую переменную:

boolean lock = false;

Код i -го процесса будет иметь вид:

do {

while (TestAndSet (lock));

критическая секция

lock = false;

остальная часть кода

} while (1)

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

Другое распространенное аппаратное решение для синхронизации – атомарная операция Swap, выполняющая перестановку значений двух переменных:

void Swap (Boolean * a, Boolean * b) {

Boolean temp = * a;

a = * b;

* b = temp;

}

Взаимное исключение по критическим секциям с помощью атомарной операции Swap реализуется следующим образом (приведен код i -го процесса) :

/* общие данные */

boolean lock = false;

Boolean key = false;

/* код процесса i */

do {

key = true;

while (key) {

Swap (&lock, &key);

}

Критическая секция

lock = false;

остальная часть кода

} while (1)

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

Системная реализация

Общий семафор (counting semaphore),по Э. Дейкстре, - это целая переменная S, над которой определены две атомарных семафорных операции wait (S) и signal (S) со следующей семантикой:

wait (S):

while (S <= 0) do no-op;

S--;

signal (S):

S++;

Фактически, если начальное значение общего семафора равно n (> 0), то это число задает количество процессов, которые могут беспрепятственно выполнить над семафором операцию wait.

Синхронизация по критическим секциям с помощью общего семафора осуществляется следующим образом:

/* общие данные */

semaphore mutex = 1;

do {

wait (mutex);

критическая секция

signal (mutex);

остальная часть кода

} while (1)

Наиболее простой вид синхронизации действий, выполняемых в двух процессах, - это исполнение действия B в процессе Pj после того, как действие A исполнено в процессе Pi . Рассмотрим, как такую синхронизацию осуществить с помощью семафоров.

Используем семафор flag, инициализированный 0.

Код процесса Pi:

. . .

A;

signal (flag);

Код процесса Pj:

. . .

wait (flag);

B;

21. Проблемы использования флагов для взаимного исключения. Аппаратные методы организации взаимного исключения

Почему нельзя использовать простые флаги при организации совместного доступа нескольких процессов или потоков к одному ресурсу? Зачем нужны алгоритмы Петерсона, Деккера и семафорфы, если все обычно используют простые флаги?

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

2. Переключатель процессов может прервать процесс на любой команде.

3. Процесс 1 проверил флаг критической секции. Флаг свободен.

4. Процесс 1 начал модифицировать флаг. Процесс 1 может считать, что он модифицировал флаг критической секции. На самом деле его прервал процесс 2.

5. Процесс 2 изменяет флаг критической секции и начинает работать с данными.

6. Процесс 1 прерывает процесс 2. Он уже проверил флаг и считает, что он свободен. Процесс 1 модифицирует флаг и начинает работать с критическими данными. Возникает конфликт.

7. Для получения атомарности, используют два основных метода: реализация неделимых операций TEST_AND_SET и CLEAR_TEST_AND_SET (реализация двоичного семафора Дейкстры на уровне системы команд ЦП).

8. Использование аппаратных прерываний.

Аппаратная реализация

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

Рассмотрим одну из этих операций, традиционно используемых для синхронизации, - операцию TestAndSet, которая атомарно выполняет считывание и запоминание значения переменной, затем изменяет его на заданное значение, но в результате выдает первоначальное значение переменной.

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

boolean TestAndSet (boolean & target) {

boolean rv = target;

target = true;

return rv;

}

С помощью данной операции реализовать синхронизацию процессов по критическим секциям очень просто. Введем в качестве блокировщика общую булевскую переменную:

boolean lock = false;

Код i -го процесса будет иметь вид:

do {

while (TestAndSet (lock));

критическая секция

lock = false;

остальная часть кода

} while (1)

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

Другое распространенное аппаратное решение для синхронизации – атомарная операция Swap, выполняющая перестановку значений двух переменных:

void Swap (Boolean * a, Boolean * b) {

Boolean temp = * a;

a = * b;

* b = temp;

}

Взаимное исключение по критическим секциям с помощью атомарной операции Swap реализуется следующим образом (приведен код i -го процесса) :

/* общие данные */

boolean lock = false;

Boolean key = false;

/* код процесса i */

do {

key = true;

while (key) {

Swap (&lock, &key);

}

критическая секция

lock = false;

остальная часть кода

} while (1)

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

22. Проблемы синхронизации. Гонки и взаимная блокировка

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

Различают следующие проблемы:

Состоя́ние го́нки  (англ. race condition)  — ошибка проектирования многопоточной системы или приложения, при которой работа системы или приложения зависит от того, в каком порядке выполняются части кода. Название ошибка получила от похожей ошибки проектирования электронных схем (см. Гонки сигналов (электроника)).

Состояние гонки — специфическая ошибка, проявляющаяся в случайные моменты времени и «затихающая» при попытке её локализовать.

Рассмотрим пример кода (на Java)[1]

int x;

// Поток 1:

while (!stop)

{

x++;

…

}

// Поток 2:

while (!stop)

{

if (x%2 == 0)

System. out. println("x=" + x);

…

}

Пусть x=0. Предположим, что выполнение программы происходит в таком порядке:

1.  if в потоке 2 проверяет x на чётность.

2.  Оператор «x++» в потоке 1 увеличивает x на единицу.

3.  Оператор вывода в потоке 2 выводит «x=1», хотя, казалось бы, переменная проверена на чётность.

Способы решения

Локальная копия

Самый простой способ решения — копирование переменной x в локальную переменную. Вот исправленный код:

// Поток 2:

while (!stop)

{

int cached_x = x;

if (cached_x%2 == 0)

System. out. println("x=" + cached_x);

…

}

Естественно, этот способ работает только тогда, когда переменная одна и копирование производится за одну машинную команду.

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

Более сложный, но и более универсальный метод решения — синхронизация потоков, а именно:[1]

int x;

// Поток 1:

while (!stop)

{

synchronized(SomeObject)

{

x++;

}

…

}

// Поток 2:

while (!stop)

{

synchronized(SomeObject)

{

if (x%2 == 0)

System. out. println("x=" + x);

}

…

}

Комбинированный способ

Предположим, что переменная x имеет тип не int, а long (на 32-битных ЭВМ её копирование выполняется за две машинных команды), а во втором потоке вместо System. out. println стоит более сложная обработка. В этом случае оба метода неудовлетворительны: первый — потому что x может измениться, пока идет копирование; второй — потому что засинхронизирован слишком большой объём кода.

Эти способы можно скомбинировать, копируя «опасные» переменные в синхронизированном блоке. С одной стороны, это снимет ограничение на одну машинную команду, с другой — позволит избавиться от слишком больших синхроблоков.

long x;

// Поток 1:

while (!stop)

{

synchronized(SomeObject)

{

x++;

}

…

}

// Поток 2:

while (!stop)

{

long cached_x;

synchronized (SomeObject)

{

cached_x = x;

}

if (cached_x%2 == 0)

DoSomethingComplicated(cached_x);

…

}

Очевидных способов выявления и исправления состояний гонки не существует. Лучший способ избавиться от гонок — правильное проектирование многозадачной системы.

Взаи́мная блокиро́вка (англ. deadlock) — ситуация в многозадачной среде или СУБД, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами.

Простейший пример взаимной блокировки

Шаг	Процесс 1	Процесс 2
0	Хочет захватить A и B, начинает с A	Хочет захватить A и B, начинает с B
1	Захватывает ресурс A	Захватывает ресурс B
2	Ожидает освобождения ресурса B	Ожидает освобождения ресурса A
3	Взаимная блокировка

Отладка взаимных блокировок, как и других ошибок синхронизации, усложняется тем, что для их возникновения нужны специфические условия одновременного выполнения нескольких процессов (в вышеописанном примере если бы процесс 1 успел захватить ресурс B до процесса 2, то ошибка не произошла бы).

Livelock

Это слово означает такую ситуацию: система не «застревает» (как в обычной взаимной блокировке), а занимается бесполезной работой, её состояние постоянно меняется — но, тем не менее, она «зациклилась», не производит никакой полезной работы.

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

Обнаружение взаимных блокировок

Поиск взаимных блокировок осуществляется путем построения и анализа графа ожидания. В графе ожидания узлами отмечаются процессы и объекты. Блокировки отмечаются рёбрами, направленными от узла, соответствующего захваченному объекту, к узлу, соответствующему захватившему его процессу. Ожидания отмечаются рёбрами, направленными от узла, соответствующего ожидающему процессу, к узлу, соответствующему ожидаемому объекту.

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

Существуют алгоритмы удаления взаимной блокировки. В то же время, выполнение алгоритмов поиска удаления взаимных блокировок может привести к livelock — взаимная блокировка образуется, сбрасывается, снова образуется, снова сбрасывается и так далее.

Кроме того, эти алгоритмы реализуются менеджером ресурсов — программой, отвечающей за блокировку и разблокировку. Если же часть занятых в блокировке ресурсов распределяется кем-то другим, обнаружение взаимной блокировки невозможно. К примеру, СУБД Oracle обнаруживает взаимную блокировку запросов к её базам данных, но если в приведенном примере объекты — это поле базы и, к примеру, файл на жестком диске, взаимная блокировка обнаружена не будет — СУБД этот файл не обрабатывает и для неё взаимной блокировки нет.

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

Классический способ борьбы с проблемой — разработка иерархии блокировок, установление правила, что некоторые блокировки никогда не могут захватываться в состоянии, в котором уже захвачены какие-то другие блокировки. Говоря точно, речь о разработке отношения сравнения между блокировками, и о запрете захвата «большей» блокировки в состоянии, когда уже захвачена «меньшая».

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

В файловой системе существуют блокировки, «защищающие» переменные «размер файла» и «длина реально записанных данных в файле». В некоторых случаях возможно исполнение ввода/вывода на диск с удержанием этих блокировок.

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

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

Есть способы избежания данной проблемы:

1. Не бери ложку, если не положил вилку

2. Бери ложку и вилку сразу (WaitForMultipleObjects)

23. Методы работы с общей(разделяемой) памятью

Разделяемая память

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

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

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

shmctl служит для управления параметрами, связанными с существующим сегментом

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

shmid = shmget(key, size, flag);

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

virtaddr = shmat(id, addr, flags);

id - это ранее полученный дескриптор сегмента addr - желаемый процессом виртуальный адрес, который должен соответствовать началу сегмента в виртуальной памяти virtaddr - реальный виртуальный адрес начала сегмента не обязательно совпадает со значением прямого параметра addr если addr == 0, ядро выбирает наиболее удобный виртуальный адрес начала сегмента

shmdt(addr);

addr - виртуальный адрес начала сегмента в виртуальной памяти, ранее полученный от системного вызова shmat

shmctl(id, cmd, shsstatbuf);

cmd идентифицирует требуемое конкретное действие важна функция уничтожения сегмента разделяемой памяти

В этой статье я хотел бы рассказать о такой замечательной штуке, как файлы, отображаемые в память(memory-mapped files, далее — MMF).
Иногда их использование может дать довольно таки существенный прирост производительности по сравнению с обычной буферизированной работой с файлами.

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

«Клёво, конечно, но что это даёт?» — спросите вы. Поясню на примере.
Допустим, перед нами стоит задача обработки большого файла(несколько десятков или даже сотен мегабайт). Казалось бы, задача тривиальна — открываем файл, поблочно копируем из него в память, обрабатываем. Что при этом происходит. Каждый блок копируется во временный кэш, затем из него в нашу память. И так с каждым блоком. Налицо неоптимальное расходование памяти под кэш + куча операций копирования. Что же делать?
Тут-то нам на помощь и приходит механизм MMF. Когда мы обращаемся к памяти, в которую отображен файл, данные загружаются с диска в кэш(если их там ещё нет), затем делается отображение кэша в адресное пространство нашей программы. Если эти данные удаляются — отображение отменяется. Таким образом, мы избавляемся от операции копирования из кэша в буфер. Кроме того, нам не нужно париться по поводу оптимизации работы с диском — всю грязную работу берёт на себя ядро ОС.
В своё время я проводил эксперимент. Замерял с помощью quantify скорость работы программы, которая буферизировано копирует большой файл размером 500 мб в другой файл. И скорость работы программы, которая делает то же, но с помощью MMF. Так вот вторая работает быстрее почти на 30% (в Solaris, в других ОС результат может отличаться). Согласитесь, неплохо. 
Чтобы воспользоваться этой возможностью, мы должны сообщить ядру о нашем желании отобразить файл в память. Делается это с помощью функции mmap().