Синхронная и асинхронная обработка данных в высокопроизводительных ЭВМ. Параллельные процессы

 

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

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

 

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

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

 

Межпроцессное взаимодействие

 

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

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

 

Сообщение – метод взаимодействия, когда один процесс посылает сообщение второму, а тот получает его. Если сообщение не пришло – второй процесс блокируется (ожидает сообщения) или сразу возвращает код ошибки.

С системами передачи сообщения  связано большое количество проблем. Например, сообщение может потеряться. Чтобы избежать потери, получатель отсылает обратно сообщение с подтверждением приема. Если отправитель не получает подтверждения через некоторое время, он отсылает сообщение еще раз.

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

 

Семафор — объект, позволяющий войти в заданный участок кода (обычно – критическую секцию) не более чем n процессам.

 

С семафором возможны три операции:

1) init(n); - инициализация счетчика (число, переданное счетчику, является количеством процессов, которые могут одновременно обращаться к критической секции)

2) wait(); - ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу.

3) leave(); - увеличить счетчик на единицу.

 

Перед обращением процесса к критической  секции необходимо вызвать метод  wait(), после выполнения которого гарантировано, что количество процессов, одновременно обращающихся к ней не превышает n-1. Тогда процесс может продолжить работу и выполнить метод leave() после работы с критической секцией, тем самым дав знать остальным процессам, что “место освободилось”.

Если количество вызовов методов wait() и leave() не совпадает, то работа системы будет не корректной так же, как и в случае взаимной блокировки процессов – ситуации, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами:

 

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

 

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

 

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

Задача мьютекса — защита объекта от доступа к нему других потоков, отличных от того, который завладел мьютексом. В каждый конкретный момент только один поток может владеть объектом, защищённым мьютексом. Если другому потоку будет нужен доступ к переменной, защищённой мьютексом, то этот поток засыпает до тех пор, пока мьютекс не будет освобождён.

 

Test-and-set — простая неразрывная (атомарная) процессорная инструкция, которая копирует значение переменной в регистр, и устанавливает некое новое значение. Во время исполнения данной инструкции процессор не может прервать её выполнение и переключится на выполнение другого потока. Если используется многопроцессорная архитектура, то пока один процессор выполняет эту инструкцию с ячейкой памяти, то другие процессоры не могут получить доступ к этой ячейке.

 

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

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

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

 

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

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

Общий принцип алгоритмом Петерсона  для 2-х потоков:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Планирование  процессов

Планирование - обеспечение поочередного доступа процессов к одному процессору.

Планировщик - отвечающая за это часть операционной системы.

 

Алгоритм планирования без вытеснения (неприоритетный) - не требует прерывание по аппаратному таймеру, процесс останавливается только когда блокируется или завершает работу.

Алгоритм планирования с вытеснением (приоритетный) - требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.

 

Процессы размещаются в приоритетных очередях в соответствии со стратегией Планирования. В системах UNIX/Linux используются две стратегии планирования: FIFO (сокр. от First In First Out, т.е. первым прибыл, первым обслужен) и RR (сокр. От round-robin, т.е. циклическая).

При использовании стратегии FIFO процессы назначаются процессору в соответствии со временем поступления в очередь.

RR-планирование совпадает с FIFO-планированием  с одним исключением: после истечения кванта времени процесс помещается в конец своей приоритетной очереди, и процессору назначается следующий (по очереди) процесс.

              

 

Для обеспечения параллельной работы процессов может подойти приоритетное планирование. Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом. Приоритет может быть динамический и статический. Динамический приоритет может устанавливаться так: П=1/Т, где Т- часть использованного в последний раз кванта (если использовано 1/50 кванта, то приоритет 50. Если использован весь квант, то приоритет 1).

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

 

         

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Используемая  литература

 

Камерон Хьюз "Параллельное и распределенное программирование на С++"

http://www.f1-delphi.ru/books/parallelnoe_i_raspredelennoe_p/

 

Богомолов В.А. лекция "Планирование процессов"

http://www.moodle.ipm.kstu.ru/mod/page/view.php?id=55

 

Э. Таненбаум "Современные  операционные системы"

http://ipm.kstu.ru/os/lit/Sovremennie.OS.2-e.izd.djvu

 

Вдовикина Н.В., Машечкин И.В., Терехин А.Н., Томилин А.Н. "Операционные системы: взаимодействие процессов"

под издательством ВМиК МГУ

 

Курынин Р.В., Машечкин И.В., Терехин А.Н. "Операционные системы"

http://totktonada.ru/tmp/OS.pdf

 

Спецификация OpenMP: http://www.openmp.org

http://software.intel.com/ru-ru/articles/getting-started-with-openmp/

 

Спецификация MPI: http://www.open-mpi.org/

http://www.ccas.ru/mmes/educat/lab04k/01/basics.html