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

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

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

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

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

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

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

Итак, пусть поток-писатель начинает свою работу с проверки доступности кри­тической секции – операции Р(b), и пусть он первым войдет в критическую сек­цию. Выполняя операцию Р(е), он может обнаружить отсутствие свободных бу­феров и перейти в состояние ожидания. Как уже было показано, из этого состоя­ния его может вывести только поток-читатель, который возьмет очередную за­пись из буфера. Но поток-читатель не сможет этого сделать, так как для этого ему потребуется войти в критическую секцию, вход в которую заблокирован по­током-писателем. Таким образом, ни один из этих потоков не может завершить начатую работу и возникнет тупиковая ситуация, которая не может разрешиться без внешнего воздействия.

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

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

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

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

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

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

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

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

Потоки с помощью специального системного вызова сообщают операционной сис­теме о том, что они хотят синхронизировать свое выполнение с состоянием неко­торого объекта. Будем далее называть этот системный вызов Wait(X), где Х – ука­затель на объект синхронизации. Системный вызов, с помощью которого поток может перевести объект синхронизации в сигнальное состояние, назовем Set(X).

Поток, выполнивший системный вызов Wait(X), переводится операционной сис­темой в состояние ожидания до тех пор, пока объект Х не перейдет в сигнальное состояние. Примерами системных вызовов типа Wait() и Set() являются вызовы MaitForSingleObject() и SetEvent() в Windows NT, DosSemWait() и DosSemSet() в OS/2, s1eep() и wakeup() в UNIX.

Поток может ожидать установки сигнального состояния не одного объекта, а не­скольких. При этом поток может попросить ОС активизировать его при установ­ке либо одного из указанных объектов, либо всех объектов. Поток может в каче­стве аргумента системного вызова Wait() указать также максимальное время, которое он будет ожидать перехода объекта в сигнальное состояние, после чего ОС должна его активизировать в любом случае. Может случиться, что установки некоторого объекта в сигнальное состояние ожидают сразу несколько потоков. В зависимости от объекта синхронизации в состояние готовности могут перево­диться либо все ожидающие это событие потоки, либо один из них.

Синхронизация тесно связана с планированием потоков. Во-первых, любое об­ращение потока с системным вызовом Wait(X) влечет за собой действия в под­системе планирования – этот поток снимается с выполнения и помещается в очередь ожидающих потоков, а из очереди готовых потоков выбирается и акти­визируется новый поток. Во-вторых, при переходе объекта в сигнальное состоя­ние (в результате выполнения некоторого потока – либо системного, либо при­кладного) ожидающий этот объект поток (или потоки) переводится в очередь готовых к выполнению потоков. В обоих случаях осуществляется перепланиро­вание потоков, при этом если в ОС предусмотрены изменяемые приоритеты и/или кванты времени, то они пересчитываются по правилам, принятым в этой опера­ционной системе.

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

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

При поступлении от пользователя команды завершения приложения основной поток должен дождаться завершения всех серверных потоков и только после этого завершиться сам. Следовательно, процедура завершения должна включать вызов Wait(X1, Х2, …), где X1, Х2 – указатели на серверные потоки. В результате выпол­нения данного системного вызова основной поток будет переведен в состояние ожидания и останется в нем до тех пор, пока все серверные потоки не перейдут в сигнальное состояние, т.е. завершатся. После этого ОС переведет основной поток в состояние готовности. При получении доступа к процессору основной поток завершится. Другой пример. Пусть выполнение некоторого приложения требует последова­тельных работ-этапов. Для каждого этапа имеется свой отдельный процесс. Сиг­налом для начала работы каждого следующего процесса является завершение предыдущего. Для реализации такой логики работы необходимо в каждом про­цессе, кроме первого, предусмотреть выполнение системного вызова Wait(X), в котором синхронизирующим объектом является предшествующий поток.

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

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