Лекция: Объекты взаимной синхронизации процессов и потоков

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

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

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

Для организации взаимных исключений разработаны различные системные программные средства: блокирующие переменные, семафоры, мьютексы, мониторы /2-9/. Научиться правильно применять эти средства – цель задания №2 курсовой работы.

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

Каждому набору критических данных ставится в соответствие двоичная переменная, которой поток присваивает значение 0, когда он входит в критическую секцию, и значение 1, когда он ее покидает. На рис. 3.1 показан фрагмент алгоритма потока, использующего для реализации взаимного исключения доступа к критическим данных D блокирующую переменную F(D). Перед входом в критическую секцию поток проверяет, не работает ли уже какой-нибудь поток с данными D. Если переменная F(D) установлена в 0, то данные заняты и проверка циклически повторяется. Если же данные свободны (F(D)=1), то значение переменной F(D) устанавливается в 0 и поток входит в критическую секцию. После того, как поток выполнит все действия с данными D, значение переменной F(D) снова устанавливается равным 1. Блокирующие переменные могут использоваться не только при доступе к разделяемым данным, но и при доступе к разделяемым ресурсам любого вида.

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

 
 

ВТСBTRBTS

 

При отсутствии такой команды в процессоре соответствующие действия должны реализоваться специальными системными примитивами, которые бы запрещали прерывания при выполнении всех операций проверки и установки. Реализация взаимного исключения описанным выше способом имеет существенный недостаток: в течение времени, когда один поток находится в критической секции, другой поток, которому требуется тот же ресурс, получив доступ к процессору, будет непрерывно опрашивать блокирующую переменную (активное ожидание), бесполезно тратя выделяемое ему процессорное время, которое могло бы быть использовано для выполнения другого потока. Для устранения этого недостатка во многих ОС предусматриваются специальные системные вызовы для работы с критическими секциями. На рис.3.2 показано, как с помощью этих функций реализовано взаимное исключение в современных версиях ОС Windows. Перед тем, как начать изменение критических данных, поток выполняет системный вызов EnterCriticalSection(). В рамках этого вызова сначала выполняется, как и в предыдущем случае, проверка блокирующей переменной, отражающей состояние критического ресурса. Если системный вызов определил, что ресурс занят (F(D)=0), он в отличие от предыдущего случая не выполняет циклический опрос, а переводит поток в состояние ожидания ресурса (D) и делает отметку о том, что данный поток должен быть активизирован, когда соответствующий ресурс ос

 
 

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

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

Семафоры являются обобщением блокирующих переменных. Вместо двоичных переменных Дийкстра (Dijkstra) предложил использовать переменные, которые могут принимать целые неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, получили название семафоров /10-13/.

Для работы с семафорами вводятся два примитива, обозначаемых Р и V. Пусть переменная S представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом.

V(S) — переменная S увеличивается на 1 единым действием. Выборка, наращивание и запоминание не могут быть прерваны. К переменной S нет доступа другим потокам во время выполнения этой операции.

P(S) – переменнаяS уменьшается на 1, если это возможно. Если S=0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию Р, ждет пока это уменьшение станет возможным. Проверка и уменьшение также являются неделимой операцией.

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

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

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

Введем два семафора: е – число пустых буферов и f – число заполненных буферов, причем в исходном состоянии е=N, а f=0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис.3.3).

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

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

 
 

Взаимное исключение будем обеспечивать с помощью двоичного семафора b. Оба потока после проверки доступности буферов должны выполнить проверку доступности критической секции.

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

Инициализация семафора включает в себя имя семафора и начальное значение: InitSem (имя_семафора, начальное_значение).

 

P(S): S:=S – 1;

If S<0 then {ставит процесс в очередь семафора S}

 

V(S): If S<0 then {поместить один из ожидающих процессов очереди семафора S в очередь готовности}

S:=S+1.

 

 

еще рефераты
Еще работы по информатике