Механизмы синхронизации и взаимодействия процессов и потоков

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ) Кафедра 302

Автоматизированные системы обработки информации и управления

Доклад на тему

«Механизмы синхронизации и взаимодействия процессов и потоков»

Курс: «Системы реального времени»

Выполнил студент группы 03−423:

Вертушков А.В.

Проверил:

Секретарев В.Е.

Москва 2013 г.

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

Введение

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

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

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

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

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

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

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

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

Так, потоки, принадлежащие разным процессам, не имеют возможности вмешиваться каким-либо образом в работу друг друга. Без посредничества операционной системы они не могут приостановить друг друга или оповестить о произошедшем событии. Средства синхронизации используются операционной системой не только для синхронизации прикладных процессов, но и для ее внутренних нужд. Обычно разработчики операционных систем предоставляют в распоряжение прикладных и системных программистов широкий спектр средств синхронизации. Эти средства могут образовывать иерархию, когда на основе более простых средств строятся более сложные, быть функционально специализированными. Например, средства для синхронизации потоков одного процесса, средства для синхронизации потоков разных процессов при обмене данными и т. д. Часто функциональные возможности разных системных вызовов синхронизации перекрываются, так что для решения одной задачи программист может воспользоваться несколькими вызовами в зависимости от своих личных предпочтений. Пренебрежение вопросами синхронизации в многопоточной системе может привести к неправильному решению задачи или даже к краху системы. 2. Критические секции Важным понятием синхронизации потоков является понятие «критической секции» программы.

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

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

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

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

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

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

Операция wait для семафора имеет такое же функциональное значение, что и инструкция test_and_set. Если несколько процессов ждут одного и того же семафора, то после выполнения операции signal только один из них может продолжить свое развитие. В зависимости от реализации процессы могут ждать в очереди, упорядоченной либо по принципу FIFO (Firstln, FirstOut — первым вошел, первым вышел), либо в соответствии с приоритетами, или выбираться случайным образом. Названия управляющей структуры «семафор» и операций signal и wait имеют очевидное мнемоническое значение. В литературе вместо signal и wait применяются и другие названия с тем же самым функциональным смыслом. С помощью семафоров проблема защиты ресурсов решается следующим образом:

program sem_example (* защита ресурса *) var P1: semaphore begin P1 := 1; cobegin while true do (* бесконечный цикл *) begin (* процесс, А *) wait(P1); (* защищенный ресурс *) signal(P1); … end; (* процесс, А *) while true do (* бесконечный цикл *) begin (* процесс В *) wait(Pl); (* защищенный ресурс *) signal (Pl); … end; (* процесс В *) coend; end. (* sem_example *) Семафор гарантирует, что два процесса могут получить доступ к защищенному ресурсу только по очереди.

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

Само по себе применение семафоров не гарантирует предотвращения тупиковых ситуаций. Если два процесса используют семафоры следующим образом wait(Pl) wait(P2) wait(P2) wait(Pl) … … (* защищенный ресурс *) (* защищенный ресурс *) … … signal(Pl) signal (P2) signal(P2) signal(Pl) то по-прежнему существует риск возникновения тупика. Если переключение процессов происходит между двумя операторами wait первой программы, а вторая программа выполнит свои операторы wait, то это приводит к тупику, поскольку каждая программа ожидает от другой освобождения семафора.

Проблема состоит в том, что, хотя семафор гарантирует неразрывность проверки и установки значения, он сам остается защищенным ресурсом. В приведенном примере явно нарушен запрет последовательного выделения, и это приводит к возможности тупиковых ситуаций. Семафор может помочь при синхронизации взаимосвязанных действий. Например, если процесс должен работать с данными только после того, как они считаны с внешнего порта, программа может иметь следующий вид: Process «Чтение данных» Process «Обработка данных» while true do while true do begin begin (* чтение новых данных *) wait(data_available); signal(data_available); (*обработка данных *) end; end; Это решение отделяет операцию ввода данных от их обработки. На появление новых данных указывает значение семафора, отличное от 0. Если существует механизм буферизации (промежуточного хранения) новых данных, то процедура обработки сможет получить все данные, даже если они поступают быстрее, чем она в состоянии их принять. В системах реального времени принято отделять процедуры, требующие быстрой реакции, например прием данных с внешнего порта, от других процессов.

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

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

Ошибки синхронизации, связанные с неправильным использованием семафоров, трудно выявляются. Процесс, не выполняющий операциюwait, может войти в критическую секцию одновременно с другим процессом, что приведет к непредсказуемым результатам. Естественно, нельзя говорить, что такая ошибка выявится при тестировании; она даже может никогда не произойти за все время существования системы. Легче найти противоположную ошибку — отсутствующая операция signal может в определенный момент привести к остановке, по крайней мере, одного из процессов, что достаточно просто обнаружить. Компилятор не имеет возможности проверить, правильно ли используются семафоры, то есть, согласованы ли операции wait с операциямиsignal в других модулях и связаны ли семафоры с соответствующими ресурсами, поскольку это зависит от логики алгоритма. Более того, размещение семафоров в программе, как и других команд, произвольно. Забота о проверке правильности программы лежит на программисте. Использование структурного программирования существенно облегчает решение этой задачи.

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

begin wait until condition; modify data; end Программа делится на две основные части. Сначала проверяются условия, а затем производятся операции над данными. Процедура проверки условия не изменяет данных и поэтому не требует какой-либо специальной защиты доступа.

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

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

Операции с событиями можно реализовать либо с помощью двоичной переменной, либо с помощью счетчика, при этом основные принципы остаются одинаковыми. Глагол to await имеет значение не только «ждать», но и «предстоять», то есть конструкцию await (А) можно трактовать, как «предстоит событие А». Глагол to cause означает «быть причиной», побудительным мотивом, «вызвать что-либо». Конструкция cause (А) интерпретируется как «вызвать событие А» (в литературе и в операционных системах иногда используются и другие названия).

В противоположность семафору, переменную события нельзя использовать для защиты ресурса от конкурирующего доступа нескольких процессов, поскольку по определению она освобождает все ожидающие процессы. Вышеприведенная проблема решается с помощью переменной события и семафора, если все программы имеют следующий вид var mutex: semaphore; change: event; begin while not condition do await(change); wait(mutex); (* обработка общих переменных *) signal(mutex); cause(change); end; При каждом изменении переменной event все процессы проверяют condition, и только те из них, для которых condition выполнено, могут продолжаться.

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

Взаимоисключения

Объекты-взаимоисключения (мьютексы, mutex — от MUTual EXclusion) позволяют координировать взаимное исключение доступа к разделяемому ресурсу. Сигнальное состояние объекта (т.е. состояние «установлен») соответствует моменту времени, когда объект не принадлежит ни одной нити и его можно «захватить». И наоборот, состояние «сброшен» (не сигнальное) соответствует моменту, когда какая-либо нить уже владеет этим объектом. Доступ к объекту разрешается, когда нить, владеющая объектом, освободит его. синхронизация поток процесс семафор Две (или более) нити могут создать мьютекс с одним и тем же именем, вызвав функцию CreateMutex. Первая нить действительно создает мьютекс, а следующие — получают дескриптор уже существующего объекта. Это дает возможность нескольким нитям получить дескриптор одного и того же мьютекса, освобождая программиста от необходимости заботиться о том, кто в действительности создает мьютекс. Если используется такой подход, желательно установить флаг bInitialOwner в FALSE, иначе возникнут определенные трудности при определении действительного создателя мьютекса. Несколько нитей могут получить дескриптор одного и того же мьютекса, что делает возможным взаимодействие между процессами. Можно использовать следующие механизмы такого подхода:

· Дочерний процесс, созданный при помощи функции CreateProcess может наследовать дескриптор мьютекса в случае, если при создании мьютекса функцией CreateMutex был указан параметр lpMutexAttributes.

· Нить может получить дубликат существующего мьютекса с помощью функции DuplicateHandle.

· Нить может указать имя существующего мьютекса при вызове функций OpenMutex или CreateMutex.

Для того чтобы объявить взаимоисключение принадлежащим текущей нити, надо вызвать одну из ожидающих функций. Нить, которой принадлежит объект, может его «захватывать» повторно сколько угодно раз (это не приведет к самоблокировке), но столько же раз она должна будет его освобождать с помощью функции ReleaseMutex.

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

Пример. Синхронизация нитей с помощью мьютексов.

#include

#include

HANDLE hMutex;

int a[5];

HANDLE hThr;

unsigned long uThrID;

void Thread (void* pParams)

{

int i, num = 0;

while (1)

{

WaitForSingleObject (hMutex, INFINITE);

for (i=0; i<5; i++) a[i] = num;

num++;

ReleaseMutex (hMutex);

}

}

int main (void)

{

hMutex=CreateMutex (NULL, FALSE, NULL);

hThr=CreateThread (NULL, 0,(LPTHREAD_START_ROUTINE)Thread, NULL, 0,&uThrID);

while (1)

{

WaitForSingleObject (hMutex, INFINITE);

printf («%d %d %d %d %dn», a[0], a[1], a[2], a[3], a[4]);

ReleaseMutex (hMutex);

}

return 0;

}