(Назад)
(Cкачать работу)Любое взаимодействие процессов или потоков связано с их синхронизацией, которая заключается в согласовании их скоростей путем приостановки процесса до наступления некоторого события и последующей его активизации при наступлении этого события. Например, процесс-получатель должен обращаться за данными только после того, как они помещены в буфер процессом-отправителем, в противном случае процесс-получатель должен быть приостановлен.
Важным понятием синхронизации является понятие критической секции программы. Критическая программная секция – часть программы, результат выполнения которой может непредсказуемо изменяться, если переменные, относящиеся к этой части программы, изменяются другими потоками в то время, когда выполнение этой части программы еще не завершено. Критическая секция всегда определяется по отношению к критическим данным. Нарушение синхронизации приводит к неправильным результатам и ошибкам в вычислениях.
Для синхронизации необходимо обеспечить, чтобы в каждый момент времени в критической секции, связанной с критическими данными, находился только один процесс или поток. Этот прием получил название взаимного исключения.
Для организации взаимных исключений разработаны различные системные программные средства: блокирующие переменные, семафоры, мьютексы, мониторы /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.
www.ronl.ru
Любое взаимодействие процессов или потоков связано с их синхронизацией, которая заключается в согласовании их скоростей путем приостановки процесса до наступления некоторого события и последующей его активизации при наступлении этого события. Например, процесс-получатель должен обращаться за данными только после того, как они помещены в буфер процессом-отправителем, в противном случае процесс-получатель должен быть приостановлен.
Важным понятием синхронизации является понятие критической секции программы. Критическая программная секция – часть программы, результат выполнения которой может непредсказуемо изменяться, если переменные, относящиеся к этой части программы, изменяются другими потоками в то время, когда выполнение этой части программы еще не завершено. Критическая секция всегда определяется по отношению к критическим данным. Нарушение синхронизации приводит к неправильным результатам и ошибкам в вычислениях.
Для синхронизации необходимо обеспечить, чтобы в каждый момент времени в критической секции, связанной с критическими данными, находился только один процесс или поток. Этот прием получил название взаимного исключения.
Для организации взаимных исключений разработаны различные системные программные средства: блокирующие переменные, семафоры, мьютексы, мониторы /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.
www.ronl.ru
Для синхронизации действий, выполняемых разными потокамисуществует несколько различных способов. Условно их можно разделить наследующие:
· синхронизация с помощью глобальныхпеременных
· синхронизация с помощью обменасобытиями
· синхронизация с помощью специальныхобъектов (событий, семафоров, критических секций, объектов исключительноговладения и других)
Первый метод синхронизации следует признать самым неудачным,так как он требует постоянного опроса состояния глобальной переменной. У этогометода есть и более серьезные недостатки — так, например, возможна полнаяблокировка потоков, если поток, ожидающий изменения глобальной переменной имеетболее высокий приоритет, чем поток, изменяющий эту переменную. Правда, егоможно несколько улучшить — вводя дополнительные временные задержки междупоследовательными опросами.
Второй метод потребует создания объектов, способных получатьсообщения или извещения о выполнении некоторых действий. Это могут быть окна,файлы (например, при использовании асинхронных операций или операций суведомлением), каталоги и т.д. Во многих случаях может быть удобно создатьневидимое окно, участвующее в обмене сообщениями или ожидающее получениясообщений для выполнения тех или иных действий.
Третий метод — синхронизация с помощью специальных объектов —потребует рассмотрения разных объектов и разных методов синхронизации сиспользованием объектов. В Win32 API существует большое число объектов, которыемогут быть применены в качестве синхронизирующих, причем во многих случаяхвместо одного объекта может применяться объект другого типа. Поэтому будетинтересно рассмотреть несколько основных методов синхронизации с использованиемобъектов.
Общие представления о методахсинхронизацииПри рассмотрении способов синхронизации удобно выделитьнесколько основных способов, применяемых разными операционными системами. Вчисле таких способов можно выделить четыре метода:
· критические секции
· объекты исключительного владения
· события
· синхронизация группой объектов
Последовательно рассмотрим эти основные методы, используя вкачестве примера функции по работе с глобальной кучей. Попробуем абстрактноразобраться со свойствами этих функций, что бы понять, какие методысинхронизации и в каких случаях удобно применять.
Во–первых, глобальную кучу в целом можно рассматривать какнекий сложный объект, над которым могут выполняться некоторые операции (пока мырассматриваем только операции над кучей в целом, не вдаваясь в нюансы работы сотдельными блоками — при необходимости доступ к отдельным блокам кучи долженбыть синхронизирован, но это уже не функции кучи, а проблема того, ктопользуется кучей).
Часть операций, например получение указателя на какой–либоблок в куче, не нуждается в изменении самой кучи. То есть функции, осуществляющиеподобные операции могут выполняться одновременно разными потоками не конфликтуядруг с другом. Такие функции удобно назвать “читателями” — они не изменяют кучукак единый объект.
Другие операции, например выделение нового блока в куче,требуют внесения изменений в кучу — изменения в цепочке выделяемых блоков.Обычно такие изменения осуществляются не в одном месте, а требуетсясогласованное внесение изменений в нескольких структурах данных. В процессетакой операции структура кучи какое–то время оказывается нарушенной, вследствиечего одновременное выполнение таких действий должно быть исключено. Такиефункции удобно назвать “писателями” — они изменяют кучу как единый объект.
Применительно к куче возможен одновременный доступ несколькихчитателей и исключительный — писателей. Более того, если к куче получает доступписатель, то читатели также должны быть лишены доступа (в других случаях этоможет быть не так — читатели могут работать одновременно с писателем).
Можно сформулировать несколько правил для работы с такимобъектом:
· если к объекту имеет доступ писатель,то ни читатели, ни другие писатели доступа не имеют;
· если к объекту имеет доступ читатель,то возможен одновременный доступ других читателей и запрещен доступ писателям;
· если объект свободен, то первыйпришедший писатель или читатель имеет право доступа.
Рассмотренный пример очень удобен, так как подобная ситуация(много читателей, единственный писатель) встречается сплошь и рядом — астандартного объекта для синхронизации доступа к такому объекту нет. Благодаряэтому такой пример становится благодатной почвой для рассмотрения разныхспособов синхронизации.
www.ronl.ru
Любое взаимодействие процессов или потоков связано с их синхронизацией, которая заключается в согласовании их скоростей путем приостановки процесса до наступления некоторого события и последующей его активизации при наступлении этого события. Например, процесс-получатель должен обращаться за данными только после того, как они помещены в буфер процессом-отправителем, в противном случае процесс-получатель должен быть приостановлен.
Важным понятием синхронизации является понятие критической секции программы. Критическая программная секция – часть программы, результат выполнения которой может непредсказуемо изменяться, если переменные, относящиеся к этой части программы, изменяются другими потоками в то время, когда выполнение этой части программы еще не завершено. Критическая секция всегда определяется по отношению к критическим данным. Нарушение синхронизации приводит к неправильным результатам и ошибкам в вычислениях.
Для синхронизации необходимо обеспечить, чтобы в каждый момент времени в критической секции, связанной с критическими данными, находился только один процесс или поток. Этот прием получил название взаимного исключения.
Для организации взаимных исключений разработаны различные системные программные средства: блокирующие переменные, семафоры, мьютексы, мониторы /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.
www.ronl.ru
(Назад) (Cкачать работу)
Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!
МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)
Кафедра 302
Автоматизированные системы обработки информации и управления Доклад на тему
«Механизмы синхронизации и взаимодействия процессов и потоков»
Курс: «Системы реального времени» Выполнил студент
группы 03-423:
Вертушков А.В.
Проверил:
Секретарев В.Е. Москва 2013г.
Введение Синхронизация процессов в системах реального времени Организация некоторого порядка исполнения процессов называется синхронизацией (synchronization). Синхронизация процессов является основной функцией многозадачных операционных систем и используется для защиты ресурсов - с помощью механизма синхронизации упорядочивается доступ к ресурсу. То есть, процесс может получить доступ к ресурсу только после того, как другой процесс освободил его. Введение дополнительных переменных для защиты ресурсов не лучший выход, поскольку эти переменные сами становятся общим ресурсом. Существо проблемы состоит в том, что операции проверки и изменения значения переменной защиты разделены во времени и могут быть прерваны в любой момент. Более того, непрерывный контроль значений этих переменных представляет собой излишние затраты процессорного времени.
Существует достаточно обширный класс средств операционных систем, с помощью которых обеспечивается взаимная синхронизация процессов и потоков. Потребность в синхронизации потоков возникает только в мультипрограммной операционной системе и связана с использованием аппаратных и информационных ресурсов вычислительной системы. Синхронизация необходима для исключения гонок и тупиков при обмене данными между потоками, разделении данных, при доступе к процессору и устройствам ввода-вывода.
Ситуации, когда два или более потоков обрабатывают разделяемые данные и конечный результат зависит от соотношения скоростей потоков, называются гонками. Во многих операционных системах эти средства называются средствами межпроцессного взаимодействия. Выполнение потока в мультипрограммной среде всегда имеет асинхронный характер. Очень сложно с полной определенностью сказать, на каком этапе выполнения будет находиться процесс в определенный момент времени. Даже в однопрограммном режиме не всегда можно точно оценить время выполнения задачи.
Это время во многих случаях существенно зависит от значения исходных данных, которые влияют на количество циклов, направления разветвления программы, время выполнения операций ввода-вывода и т. п. Так как исходные данные в разные моменты запуска задачи могут быть разными, то и время выполнения отдельных этапов и задачи в целом является весьма неопределенной величиной. Еще более неопределенным является время выполнения программы в мультипрограммной системе. Моменты прерывания потоков, время нахождения их в очередях к разделяемым ресурсам, порядок выбора потоков для выполнения - все эти события являются результатом стечения многих обстоятельств и могут быть интерпретированы как случайные.
В лучшем случае можно оценить вероятностные характеристики вычислительного процесса, например вероятность его завершения за данный период времени. Таким образом, потоки в общем случае (когда программист не предпринял специальных мер по их синхронизации) протекают независимо, асинхронно друг другу, Это справедливо как по отношению к потокам одного процесса, выполняющим общий программный код, так и по отношению к потокам разных процессов, каждый из которых выполняет собственную программу.
Любое взаимодействие процессов или потоков связано с их синхронизацией, которая заключается в согласовании их скоростей путем приостановки потока до наступления некоторого события и последующей его активизации при наступлении этого события. Синхронизация лежит в основе любого взаимодействия потоков, связано ли это взаимодействие с разделением ресурсов или с обменом данными. Например, поток-получатель должен обращаться за данными только после того, как они помещены в буфер потоком-отправителем. Если же поток-получатель обратился к данным до момента их поступления в буфер, то он должен быть приостановлен. При совместном использовании аппаратных ресурсов синхронизация также совершенно необходима.
Когда, например, активному потоку требуется доступ к последовательному порту, а с этим портом в монопольном режиме работает другой поток, находящийся в данный момент в состоянии ожидания, то операционная система (ОС) приостанавливает активный поток и не активизирует его до тех пор, пока нужный ему порт не освободится. Часто нужна также синхронизация с событиями, внешними по отношению к вычислительной системе, например реакции на нажатие комбинации клавиш Сtгl+С. Ежесекундно в системе происходят сотни событий, связанных с распределением и освобождением ресурсов, и операционная система должна иметь надежные и производительные средства, которые бы позволяли ей синхронизировать потоки с происходящими в системе событиями.
Для синхронизации потоков прикладных программ программист может использовать как собственные средства и приемы синхронизации, так и средства операционной системы. Например, два потока одного прикладного процесса могут координировать свою работу с помощью доступной для них обоих глобальной логической переменной, которая устанавливается в единицу при осуществлении некоторого события, например выработки одним потоком данных, нужных для продолжения работы другого. Однако во многих случаях более эффективными или даже единственно возможными являются средства синхронизации, предоставляемые операционной системой в форме системных вызовов.
Так, потоки, принадлежащие разным процессам, не имеют возможности вмешиваться каким-либо образом в работу друг друга. Без посредничества операционной системы они не могут приостановить друг друга или оповестить о произошедшем событии. Средства синхронизации используются операционной системой не только для синхронизации прикладных процессов, но и для ее внутренних нужд. Обычно разработчики операционных систем предоставляют в распоряжение прикладных и системных программистов широкий спектр средств синхронизации. Эти средства могут образовывать иерархию, когда на основе более простых средств строятся более сложные, быть функционально специализированными. Например, средства для синхронизации потоков одного процесса, средства для синхронизации потоков разных процессов при обмене данными и т. д. Часто функциональные возможности разных системных вызовов синхронизации перекрываются, так что для решения одной задачи программист может воспользоваться несколькими вызовами в зависимости от своих личных предпочтений. Пренебрежение вопросами синхронизации в многопоточной системе может привести к неправильному решению задачи или даже к краху системы. 2. Критические секции Важным понятием синхронизации потоков является понятие «критической секции» программы.
Критическая секция - это часть программы, результат выполнения которой может непредсказуемо меняться, если переменные, относящиеся к этой части программы, изменяются другими потоками в то время, когда выполнение этой части еще не завершено. Критическая секция всегда определяется по отношению к определенным критическим данным, при несогласованном изменении которых могут возникнуть нежелательные эффекты. Во всех потоках, работающих с критическими данными, должна быть определена критическая секция. В разных потоках критическая секция состоит в общем случае из разных последовательностей команд. Чтобы исключить эффект гонок по отношению к критическим данным, необходимо обеспечить, чтобы в каждый момент времени в критической секции, связанной с этими данными, находился только один поток. При этом неважно, находится этот поток в активном или в приостановленном состоянии. Этот прием называют взаимным исключением. Операционная система использует разные способы реализации взаимного исключения. Некоторые способы пригодны для взаимного исключения при вхождении в критическую секцию только потоков одного процесса, в то время как другие могут обеспечить взаимное исключение и для потоков разных процессов. Самый
referat.co
Любое взаимодействие процессов или потоков связано с их синхронизацией, которая заключается в согласовании их скоростей путем приостановки процесса до наступления некоторого события и последующей его активизации при наступлении этого события. Например, процесс-получатель должен обращаться за данными только после того, как они помещены в буфер процессом-отправителем, в противном случае процесс-получатель должен быть приостановлен.
Важным понятием синхронизации является понятие критической секции программы. Критическая программная секция – часть программы, результат выполнения которой может непредсказуемо изменяться, если переменные, относящиеся к этой части программы, изменяются другими потоками в то время, когда выполнение этой части программы еще не завершено. Критическая секция всегда определяется по отношению к критическим данным. Нарушение синхронизации приводит к неправильным результатам и ошибкам в вычислениях.
Для синхронизации необходимо обеспечить, чтобы в каждый момент времени в критической секции, связанной с критическими данными, находился только один процесс или поток. Этот прием получил название взаимного исключения.
Для организации взаимных исключений разработаны различные системные программные средства: блокирующие переменные, семафоры, мьютексы, мониторы /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.
www.ronl.ru
Любое взаимодействие процессов или потоков связано с их синхронизацией, которая заключается в согласовании их скоростей путем приостановки процесса до наступления некоторого события и последующей его активизации при наступлении этого события. Например, процесс-получатель должен обращаться за данными только после того, как они помещены в буфер процессом-отправителем, в противном случае процесс-получатель должен быть приостановлен.
Важным понятием синхронизации является понятие критической секции программы. Критическая программная секция – часть программы, результат выполнения которой может непредсказуемо изменяться, если переменные, относящиеся к этой части программы, изменяются другими потоками в то время, когда выполнение этой части программы еще не завершено. Критическая секция всегда определяется по отношению к критическим данным. Нарушение синхронизации приводит к неправильным результатам и ошибкам в вычислениях.
Для синхронизации необходимо обеспечить, чтобы в каждый момент времени в критической секции, связанной с критическими данными, находился только один процесс или поток. Этот прием получил название взаимного исключения.
Для организации взаимных исключений разработаны различные системные программные средства: блокирующие переменные, семафоры, мьютексы, мониторы /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.
www.ronl.ru
