Во многих операционных системах эти
средства называются средствами межпроцессного
взаимодействия — Inter Process Communications (IPC),
что отражает историческую первичность
понятия «процесс» по отношению к понятию
«поток».
Выполнение потока в мультипрограммной
среде всегда имеет асинхронный характер.
Очень сложно с полной определенностью
сказать, на каком этапе выполнения будет
находиться процесс в определенный момент
времени. Даже в однопрограммном режиме
не всегда можно точно оценить время выполнения
задачи. Это время во многих случаях существенно
зависит от значения исходных данных,
которые влияют на количество циклов,
направления разветвления программы,
время выполнения операций ввода-вывода
и т. п. Так как исходные данные в разные
моменты запуска задачи могут быть разными,
то и время выполнения отдельных этапов
и задачи в целом является весьма неопределенной
величиной.
Еще более неопределенным является
время выполнения программы в
мультипрограммной системе. Моменты
прерывания потоков, время нахождения
их в очередях к разделяемым ресурсам,
порядок выбора потоков для выполнения
— все эти события являются
результатом стечения многих обстоятельств
и могут быть интерпретированы как
случайные. В лучшем случае можно
оценить вероятностные характеристики
вычислительного процесса, например
вероятность его завершения за данный
период времени.
Любое взаимодействие процессов или
потоков связано с их синхронизацией,
которая заключается в согласовании
их скоростей путем приостановки
потока до наступления некоторого события
и последующей его активизации
при наступлении этого события.
Синхронизация лежит в основе
любого взаимодействия потоков, связано
ли это взаимодействие с разделением
ресурсов или с обменом данными.
Например, поток-получатель должен обращаться
за данными только после того, как
они помещены в буфер потоком-отправителем.
Если же поток-получатель обратился
к данным до момента их поступления
в буфер, то он должен быть приостановлен.
При совместном использовании аппаратных
ресурсов синхронизация также совершенно
необходима. Когда, например, активному
потоку требуется доступ к последовательному
порту, а с этим портом в монопольном
режиме работает другой поток, находящийся
в данный момент в состоянии ожидания,
то ОС приостанавливает активный поток
и не активизирует его до тех пор,
пока нужный ему порт не освободится.
Часто нужна также синхронизация
с событиями, внешними по отношению
к вычислительной системе, например
реакции на нажатие комбинации клавиш
Ctrl+C. Ежесекундно в системе происходят
сотни событий, связанных с распределением
и освобождением ресурсов, и ОС должна
иметь надежные и производительные средства,
которые бы позволяли ей синхронизировать
потоки с происходящими в системе событиями.
Для синхронизации потоков прикладных
программ программист может использовать
как собственные средства и приемы
синхронизации, так и средства операционной
системы. Например, два потока одного
прикладного процесса могут координировать
свою работу с помощью доступной
для них обоих глобальной логической
переменной, которая устанавливается
в единицу при осуществлении
некоторого события, например выработки
одним потоком данных, нужных для
продолжения работы другого. Однако
во многих случаях более эффективными
или даже единственно возможными
являются средства синхронизации, предоставляемые
операционной системой в форме системных
вызовов. Так, потоки, принадлежащие
разным процессам, не имеют возможности
вмешиваться каким- либо образом
в работу друг друга. Без посредничества
операционной системы они не могут
приостановить друг друга или
оповестить о произошедшем событии.
Средства синхронизации используются
операционной системой не только для синхронизации
прикладных процессов, но и для ее внутренних
нужд.
Обычно разработчики операционных
систем предоставляют в распоряжение
прикладных и системных программистов
широкий спектр средств синхронизации.
Эти средства могут образовывать
иерархию, когда на основе более
простых средств строятся более
сложные, а также быть функционально
специализированными, например средства
для синхронизации потоков одного
процесса, средства для синхронизации
потоков разных процессов при
обмене данными и т. д. Часто функциональные
возможности разных системных вызовов
синхронизации перекрываются, так
что для решения одной задачи
программист может воспользоваться
несколькими вызовами в зависимости
от своих личных предпочтений.
Блокирующие переменные
Для синхронизации потоков
одного процесса прикладной программист
может использовать глобальные
блокирующие переменные. С этими
переменными, к которым все
потоки процесса имеют прямой
доступ, программист работает, не
обращаясь к системным вызовам
ОС.
Каждому набору критических данных
ставится в соответствие двоичная переменная,
которой поток присваивает значение
0, когда он входит в критическую
секцию, и значение 1, когда он ее
покидает. На рис. 4.18 показан фрагмент
алгоритма потока, использующего
для реализации взаимного исключения
доступа к критическим данным
D блокирующую переменную F(D). Перед
входом в критическую секцию поток
проверяет, не работает ли уже какой-нибудь
поток с данными D. Если переменная
F(D) установлена в 0, то данные заняты
и проверка циклически повторяется.
Если же данные свободны (F(D) = 1), то значение
переменной F(D) устанавливается в 0 и
поток входит в критическую секцию.
После того как поток выполнит
все действия с данными О, значение
переменной F(D) снова устанавливается
равным 1.
Блокирующие переменные могут использоваться
не только при доступе к разделяемым
данным, но и при доступе к разделяемым
ресурсам любого вида.
Если все потоки написаны с учетом
вышеописанных соглашений, то взаимное
исключение гарантируется. При этом
потоки могут быть прерваны операционной
системой в любой момент и в
любом месте, в том числе в
критической секции.
Однако следует заметить, что
одно ограничение на прерывания все
же имеется. Нельзя прерывать поток
между выполнением операций проверки
и установки блокирующей переменной.
Поясним это. Пусть в результате
проверки переменной поток определил,
что ресурс свободен, но сразу после
этого, не успев установить переменную
в 0, был прерван. За время его приостановки
другой поток занял ресурс, вошел
в свою критическую секцию, но также
был прерван, не завершив работы с
разделяемым ресурсом. Когда управление
было возвращено первому потоку, он,
считая ресурс свободным, установил
признак занятости и начал
выполнять свою критическую секцию.
Таким образом, был нарушен принцип
взаимного исключения, что потенциально
может привести к нежелательным
последствиям. Во избежание таких
ситуаций в системе команд многих
компьютеров предусмотрена единая,
неделимая команда анализа и
присвоения значения логической переменной
(например, команды ВТС, BTR и ВТ5 процессора
Pentium). При отсутствии такой команды в процессоре
соответствующие действия должны реализовываться
специальными системными примитивами1,
которые бы запрещали прерывания на протяжении
всей операции проверки и установки.
Реализация взаимного исключения
описанным выше способом имеет существенный
недостаток: в течение времени, когда
один поток находится в критической
секции, другой поток, которому требуется
тот же ресурс, получив доступ к
процессору, будет непрерывно опрашивать
блокирующую переменную, бесполезно
тратя выделяемое ему процессорное
время, которое могло бы быть использовано
для выполнения какого-нибудь другого
потока. Для устранения этого недостатка
во многих ОС предусматриваются специальные
системные вызовы для работы с
критическими секциями.
- Синхронизация процессов и потоков. Семафоры. Операции над семафорами. Мьютексы. Использование семафоров на примере потоков «читатель/писатель».
Существует достаточно обширный класс
средств операционной системы, с
помощью которых обеспечивается
взаимная синхронизация процессов
и потоков1. Потребность в синхронизации
потоков возникает только в мультипрограммной
операционной системе и связана
с совместным использованием аппаратных
и информационных ресурс об вычислительной
системы. Синхронизация необходима
для исключения гонок и тупиков
при обмене данными между потоками,
разделении данных, при доступе к
процессору и устройствам ввода-вывода.
1 В данном разделе мы будем
говорить о синхронизации потоков,
имея в виду, что если операционная
система не поддерживает потоки,
то все сказанное относится
к синхронизации процессов.
Во многих операционных системах эти
средства называются средствами межпроцессного
взаимодействия — Inter Process Communications (IPC),
что отражает историческую первичность
понятия «процесс» по отношению к понятию
«поток». Обычно к средствам IPC относят
не только средства межпроцессной синхронизации,
но и средства межпроцессного обмена данными.
Выполнение потока в мультипрограммной
среде всегда имеет асинхронный
характер. Очень сложно с полной
определенностью сказать, на каком
этапе выполнения будет находиться
процесс в определенный момент времени.
Даже в однопрограммном режиме не
всегда можно точно оценить время
выполнения задачи. Это время во
многих случаях существенно зависит
от значения исходных данных, которые
влияют на количество циклов, направления
разветвления программы, время выполнения
операций ввода-вывода и т. п. Так
как исходные данные в разные моменты
запуска задачи могут быть разными,
то и время выполнения отдельных
этапов и задачи в целом является
весьма неопределенной величиной.
Еще более неопределенным является
время выполнения программы в
мультипрограммной системе. Моменты
прерывания потоков, время нахождения
их в очередях к разделяемым ресурсам,
порядок выбора потоков для выполнения
— все эти события являются
результатом стечения многих обстоятельств
и могут быть интерпретированы как
случайные. В лучшем случае можно
оценить вероятностные характеристики
вычислительного процесса, например
вероятность его завершения за данный
период времени.
Таким образом, потоки в общем случае
(когда программист не предпринял
специальных мер по их синхронизации)
протекают независимо, асинхронно друг
другу. Это справедливо как по
отношению к потокам одного процесса,
выполняющим общий программный
код, так и по отношению к потокам
разных процессов, каждый из которых
выполняет собственную программу.
Любое взаимодействие процессов или
потоков связано с их синхронизацией,
которая заключается в согласовании
их скоростей путем приостановки
потока до наступления некоторого события
и последующей его активизации
при наступлении этого события.
Синхронизация лежит в основе
любого взаимодействия потоков, связано
ли это взаимодействие с разделением
ресурсов или с обменом данными.
Например, поток-получатель должен обращаться
за данными только после того, как
они помещены в буфер потоком-отправителем.
Если же поток-получатель обратился
к данным до момента их поступления
в буфер, то он должен быть приостановлен.
При совместном использовании аппаратных
ресурсов синхронизация также совершенно
необходима. Когда, например, активному
потоку требуется доступ к последовательному
порту, а с этим портом в монопольном
режиме работает другой поток, находящийся
в данный момент в состоянии ожидания,
то ОС приостанавливает активный поток
и не активизирует его до тех пор,
пока нужный ему порт не освободится.
Часто нужна также синхронизация
с событиями, внешними по отношению
к вычислительной системе, например
реакции на зажатие комбинации клавиш
Ctrl+C.
Ежесекундно в системе происходят
сотни событий, связанных с распределением
и освобождением ресурсов, и ОС
должна иметь надежные и производительные
средства, которые бы позволяли ей
синхронизировать потоки с происходящими
в системе событиями.
Для синхронизации потоков прикладных
программ программист может использовать
как собственные средства и приемы
синхронизации, так и средства операционной
системы. Например, два потока одного
прикладного процесса могут координировать
свою работу с помощью доступной
для них обоих глобальной логической
переменной, которая устанавливается
в единицу при осуществлении
некоторого события, например выработки
одним потоком данных, нужных для
продолжения работы другого. Однако
во многих случаях более эффективными
или даже единственно возможными
являются средства синхронизации, предоставляемые
операционной системой в форме системных
вызовов. Так, потоки, принадлежащие
разным процессам, не имеют возможности
вмешиваться каким-либо образом
в работу друг друга. Без посредничества
операционной системы они не могут
приостановить друг друга или
оповестить о произошедшем событии.
Средства синхронизации используются
операционной системой не только для
синхронизации прикладных процессов,
но и для ее внутренних нужд. Обычно
разработчики операционных систем предоставляют
в распоряжение прикладных и системных
программистов широкий спектр средств
синхронизации. Эти средства могут
образовывать иерархию, когда на основе
более простых средств строятся
более сложные, а также быть функционально
специализированными, например средства
для синхронизации потоков одного
процесса, средства для синхронизации
потоков разных процессов при
обмене данными и т. д. Часто функциональные
возможности разных системных вызовов
синхронизации перекрываются, так
что для решения одной задачи
программист может воспользоваться
несколькими вызовами в зависимости от
своих личных предпочтений.
Семафоры
Обобщением блокирующих переменных
являются так называемые семафоры Дейкстры.
Вместо двоичных переменных Дейкстра
(Dijkstra) предложил использовать переменные,
которые могут принимать целые неотрицательные
значения. Такие переменные, используемые
для синхронизации вычислительных процессов,
получили название семафоров.