Сетевые операционные системы

Глава 4. Процессы и потоки

2004-12-27

Продолжение

Синхронизация процессов и потоков

Цели и средства синхронизации

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

Во многих операционных системах эти средства называются средст-вами межпроцессного взаимодействия - Inter Process Communications (IPC), что отражает историческую первичность понятия "процесс" по отношению к понятию "поток". Обычно к средствам IPC относят не только средства меж-процессной синхронизации, но и средства межпроцессного обмена данными.

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

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

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

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

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

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

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

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

Необходимость синхронизации и гонки

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

• Считать из файла базы данных в буфер запись о клиенте с заданным идентификатором.
• Внести новое значение в поле Заказ (для потока А) или Оплата (для пото-ка В).
• Вернуть модифицированную запись в файл базы данных

Обозначим соответствующие шаги для потока А как Al, A2 и A3, а для потока В как Bl, B2 и ВЗ. Предположим, что в некоторый момент поток А об-новляет поле Заказ записи о клиенте N. Для этого он считывает эту запись в свой буфер (шаг Al), модифицирует значение поля Заказ (шаг A2), но внести запись в базу данных (шаг A3) не успевает, так как его выполнение прерыва-ется, например, вследствие завершения кванта времени.

Предположим также, что потоку В также потребовалось внести сведе-ния об оплате относительно того же клиента N. Когда подходит очередь по-тока В, он успевает считать запись в свой буфер (шаг Bl) и выполнить обнов-ление поля Оплата (шаг B2), а затем прерывается. Заметим, что в буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение.

Когда в очередной раз управление будет передано потоку А, то он, продолжая свою работу, запишет запись о клиенте N с модифицированным полем Заказ в базу данных (шаг A3). После прерывания потока А и активиза-ции потока В последний запишет в базу данных поверх только что обновлен-ной записи о клиенте N свой вариант записи, в которой обновлено значение поля Оплата. Таким образом, в базе данных будут зафиксированы сведения о том, что клиент N произвел оплату, но информация о его заказе окажется по-терянной (рис. 4.17, а).

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

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

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

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

Блокирующие переменные

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

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

Блокирующие переменные могут использоваться не только при дос-тупе к разделяемым данным, но и при доступе к разделяемым ресурсам лю-бого вида.

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

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

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

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

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

Продолжение следует...