Рассылка закрыта
При закрытии подписчики были переданы в рассылку "Обзор инструментов SEO-оптимизатора и методов продвижения" на которую и рекомендуем вам подписаться.
Вы можете найти рассылки сходной тематики в Каталоге рассылок.
← Январь 2005 → | ||||||
2
|
||||||
---|---|---|---|---|---|---|
3
|
4
|
5
|
7
|
8
|
9
|
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
21
|
22
|
23
|
24
|
25
|
26
|
27
|
28
|
29
|
30
|
31
|
Статистика
0 за неделю
Создай свою операционную систему! #8
Информационный Канал Subscribe.Ru |
Сетевые операционные системы |
Глава 4. Процессы и потоки |
2005-01-01 |
Продолжение Синхронизация процессов и потоковСемафорыОбобщением блокирующих переменных являются так называемые семафоры Дийкстры. Вместо двоичных переменных Дийкстра (Dijkstra) предложил использовать переменные, которые могут принимать целые неот-рицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, получили название семафоров. Для работы с семафорами вводятся два примитива, традиционно обо-значаемых Р и V. Пусть переменная S представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом: V(S): переменная S увеличивается на 1 единым действием. Выборка, нара-щивание и запоминание не могут быть прерваны. К переменной S нет дос-тупа другим потокам во время выполнения этой операции. P(S): уменьшение S на 1, если это возможно. Если S = 0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию Р, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также являются не-делимой операцией. Никакие прерывания во время выполнения примитивов V и Р недо-пустимы. В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную, которую по этой при-чине часто называют двоичным семафором. Операция Р заключает в себе по-тенциальную возможность перехода потока, который ее выполняет, в состоя-ние ожидания, в то время как операция V может при некоторых обстоятель-ствах активизировать другой поток, приостановленный операцией Р. Рассмотрим использование семафоров на классическом примере взаимодействия двух выполняющихся в режиме мультипрограммирования потоков, один из которых пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. В общем случае поток-писатель и по-ток-читатель могут иметь различные скорости и обращаться к буферному пу-лу с переменой интенсивностью. В один период скорость записи может пре-вышать скорость чтения, в другой - наоборот. Для правильной совместной работы поток-писатель должен приостанавливаться, когда все буферы оказы-ваются занятыми, и активизироваться при освобождении хотя бы одного бу-фера. Напротив, поток-читатель должен приостанавливаться, когда все буфе-ры пусты, и активизироваться при появлении хотя бы одной записи. Введем два семафора: е - число пустых буферов, и f - число запол-ненных буферов, причем в исходном состоянии е = N, а f = 0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис. 4.20). Поток-писатель прежде всего выполняет операцию Р(е), с помощью которой он проверяет, имеются ли в буферном пуле незаполненные буферы. В соответствии с семантикой операции Р, если семафор е равен 0 (то есть свободных буферов в данный момент нет), то поток-писатель переходит в со-стояние ожидания. Если же значением е является положительное число, то он уменьшает число свободных буферов, записывает данные в очередной сво-бодный буфер и после этого наращивает число занятых буферов операцией V(f). Поток-читатель действует аналогичным образом, с той разницей, что он начинает работу с проверки наличия заполненных буферов, а после чтения данных наращивает количество свободных буферов. В данном случае предпочтительнее использовать семафоры вместо блокирующих переменных. Действительно, критическим ресурсом здесь яв-ляется буферный пул, который может быть представлен как набор идентич-ных ресурсов - отдельных буферов, а значит, с буферным пулом могут рабо-тать сразу несколько потоков, и именно столько, сколько буферов в нем со-держится. Использование двоичной переменной не позволяет организовать доступ к критическому ресурсу более чем одному потоку. Семафор же реша-ет задачу синхронизации более гибко, допуская к разделяемому пулу ресур-сов заданное количество потоков. Так, в нашем примере с буферным пулом могут работать максимум N потоков, часть из которых может быть "писате-лями", а часть - "читателями". Таким образом, семафоры позволяют эффективно решать задачу син-хронизации доступа к ресурсным пулам, таким, например, как набор иден-тичных в функциональном назначении внешних устройств (модемов, прин-теров, портов), или набор областей памяти одинаковой величины, или ин-формационных структур. Во всех этих и подобных им случаях с помощью семафоров можно организовать доступ к разделяемым ресурсам сразу не-скольких потоков. Семафор может использоваться и в качестве блокирующей перемен-ной. В рассмотренном выше примере, для того чтобы исключить коллизии при работе с разделяемой областью памяти, будем считать, что запись в бу-фер и считывание из буфера являются критическими секциями. Взаимное ис-ключение будем обеспечивать с помощью двоичного семафора b (рис. 4.21). Оба потока после проверки доступности буферов должны выполнить провер-ку доступности критической секции. ТупикиПриведенный выше пример позволяет также проиллюстрировать еще одну проблему синхронизации - взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch), или тупиками. Покажем, что если переставить местами операции Р(е) и Р(b) в потоке-писателе, то при некото-ром стечении обстоятельств эти два потока могут взаимно блокировать друг друга. Итак, пусть поток-писатель начинает свою работу с проверки доступ-ности критической секции - операции Р(b), и пусть он первым войдет в кри-тическую секцию. Выполняя операцию Р(е), он может обнаружить отсутст-вие свободных буферов и перейти в состояние ожидания. Как уже было пока-зано, из этого состояния его может вывести только поток-читатель, который возьмет очередную запись из буфера. Но поток-читатель не сможет этого сделать, так как для этого ему потребуется войти в критическую секцию, вход в которую заблокирован потоком-писателем. Таким образом, ни один из этих потоков не может завершить начатую работу и возникнет тупиковая си-туация, которая не может разрешиться без внешнего воздействия. Рассмотрим еще один пример тупика. Пусть двум потокам, принадле-жащим разным процессам и выполняющимся в режиме мультипрограммиро-вания, для выполнения их работы нужно два ресурса, например принтер и последовательный порт. Такая ситуация может возникнуть, например, во время работы приложения, задачей которого является распечатка информа-ции, поступающей по модемной связи. На рис. 4.22, а показаны фрагменты соответствующих программ. По-ток А запрашивает сначала принтер, а затем порт, а поток В запрашивает уст-ройства в обратном порядке. Предположим, что после того, как ОС назначи-ла принтер потоку А и установила связанную с этим ресурсом блокирующую переменную, поток А был прерван. Управление получил поток В, который сначала выполнил запрос на получение СОМ-порта, затем при выполнении следующей команды был заблокирован, так как принтер оказался уже заня-тым потоком А. Управление снова получил поток А, который в соответствии со своей программой сделал попытку занять порт и был заблокирован, по-скольку порт уже выделен потоку В. В таком положении потоки А и В могут находиться сколь угодно долго. В зависимости от соотношения скоростей потоков они могут либо вза-имно блокировать друг друга (рис. 4.22, б), либо образовывать очереди к разделяемым ресурсам (рис. 4.22, в), либо совершенно независимо использо-вать разделяемые ресурсы (рис. 4.22, г). ПРИМЕЧАНИЕ. Тупиковые ситуации надо отличать от простых очередей, хотя те и дру-гие возникают при совместном использовании ресурсов и внешне выглядят похоже: поток приостанавливается и ждет освобождения ресурса. Однако очередь - это нормальное яв-ление, неотъемлемый признак высокого коэффициента использования ресурсов при слу-чайном поступлении запросов. Очередь появляется тогда, когда ресурс недоступен в дан-ный момент, но освободится через некоторое время, позволив потоку продолжить выпол-нение. Тупик же, что видно из его названия, является в некотором роде неразрешимой си-туацией. Необходимым условием возникновения тупика является потребность потока сра-зу в нескольких ресурсах. В рассмотренных примерах тупик был образован двумя потоками, но взаимно блокировать друг друга может и большее число потоков. На рис. 4.23 показано такое распределение ресурсов R1 между несколькими потоками Tj, которое привело к возникновению взаимных блокировок. Стрелки обозна-чают потребность потока в ресурсах. Сплошная стрелка означает, что соот-ветствующий ресурс был выделен потоку, а пунктирная стрелка соединяет поток с тем ресурсом, который необходим, но не может быть пока выделен, поскольку занят другим потоком. Например, потоку Т1 для выполнения рабо-ты необходимы ресурсы R1 и R2, из которых выделен только один - R1, а ре-сурс R2 удерживается потоком Т2. Ни один из четырех показанных на рисунке потоков не может продолжить свою работу, так как не имеет всех необходи-мых для этого ресурсов. Невозможность потоков завершить начатую работу из-за возникнове-ния взаимных блокировок снижает производительность вычислительной сис-темы. Поэтому проблеме предотвращения тупиков уделяется большое вни-мание. На тот случай, когда взаимная блокировка все же возникает, система должна предоставить администратору-оператору средства, с помощью кото-рых он смог бы распознать тупик, отличить его от обычной блокировки из-за временной недоступности ресурсов. И, наконец, если тупик диагностирован, то нужны средства для снятия взаимных блокировок и восстановления нор-мального вычислительного процесса. Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть при любом соотношении взаимных скоростей потоков. Так, если бы в примере, показанном на рис. 4.22, поток А и поток В запрашивали ре-сурсы в одинаковой последовательности, то тупик был бы в принципе невоз-можен. Другой, более гибкий подход к предотвращению тупиков заключает-ся в том, что ОС каждый раз при запуске задач анализирует их потребности в ресурсах и определяет, может ли в данной мультипрограммной смеси воз-никнуть тупик. Если да, то запуск новой задачи временно откладывается. ОС может также использовать определенные правила при назначении ресурсов потокам, например, ресурсы могут выделяться операционной системой в оп-ределенной последовательности, общей для всех потоков. В тех же случаях, когда тупиковую ситуацию не удалось предотвра-тить, важно быстро и точно ее распознать, поскольку блокированные потоки не выполняют никакой полезной работы. Если тупиковая ситуация образова-на множеством потоков, занимающих массу ресурсов, распознавание тупика является нетривиальной задачей. Существуют формальные, программно-реализованные методы распознавания тупиков, основанные на ведении таб-лиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки. Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные потоки. Можно снять только часть из них, освободив ресурсы, ожидаемые остальными потоками, можно вернуть неко-торые потоки в область подкачки, можно совершить "откат" некоторых по-токов до так называемой контрольной точки, в которой запоминается вся ин-формация, необходимая для восстановления выполнения программы с данно-го места. Контрольные точки расставляются в программе в тех местах, после которых возможно возникновение тупика. Синхронизирующие объекты ОСРассмотренные выше механизмы синхронизации, основанные на ис-пользовании глобальных переменных процесса, обладают существенным не-достатком - они не подходят для синхронизации потоков разных процессов. В таких случаях операционная система должна предоставлять потокам сис-темные объекты синхронизации, которые были бы видны для всех потоков, даже если они принадлежат разным процессам и работают в разных адрес-ных пространствах. Примерами таких синхронизирующих объектов ОС являются систем-ные семафоры, мьютексы, события, таймеры и другие - их набор зависит от конкретной ОС, которая создает эти объекты по запросам процессов. Чтобы процессы могли разделять синхронизирующие объекты, в разных ОС исполь-зуются разные методы. Некоторые ОС возвращают указатель на объект. Этот указатель может быть доступен всем родственным процессам, наследующим характеристики общего родительского процесса. В других ОС процессы в за-просах на создание объектов синхронизации указывают имена, которые должны быть им присвоены. Далее эти имена используются разными процес-сами для манипуляций объектами синхронизации. В таком случае работа с синхронизирующими объектами подобна работе с файлами. Их можно созда-вать, открывать, закрывать, уничтожать. Кроме того, для синхронизации могут быть использованы такие "обычные" объекты ОС, как файлы, процессы и потоки. Все эти объекты мо-гут находиться в двух состояниях: сигнальном и несигнальном - свободном. Для каждого объекта смысл, вкладываемый в понятие "сигнальное состоя-ние", зависит от типа объекта. Так, например, поток переходит в сигнальное состояние тогда, когда он завершается. Процесс переходит в сигнальное со-стояние тогда, когда завершаются все его потоки. Файл переходит в сигналь-ное состояние в том случае, когда завершается операция ввода-вывода для этого файла. Для остальных объектов сигнальное состояние устанавливается в результате выполнения специальных системных вызовов. Приостановка и активизация потоков осуществляются в зависимости от состояния синхрони-зирующих объектов ОС. Потоки с помощью специального системного вызова сообщают опе-рационной системе о том, что они хотят синхронизировать свое выполнение с состоянием некоторого объекта. Будем далее называть этот системный вы-зов Wait(X), где Х - указатель на объект синхронизации. Системный вызов, с помощью которого поток может перевести объект синхронизации в сигналь-ное состояние, назовем Set(X). Поток, выполнивший системный вызов Wait(X), переводится операци-онной системой в состояние ожидания до тех пор, пока объект Х не перейдет в сигнальное состояние. Примерами системных вызовов типа Wait() и Set() являются вызовы WaitForSingleObject() и SetEvent() в Windows NT, DosSemWait() и DosSemSet() в OS/2, sleep() и wakeup() в UNIX. Поток может ожидать установки сигнального состояния не одного объекта, а нескольких. При этом поток может попросить ОС активизировать его при установке либо одного из указанных объектов, либо всех объектов. Поток может в качестве аргумента системного вызова Wait() указать также максимальное время, которое он будет ожидать перехода объекта в сигналь-ное состояние, после чего ОС должна его активизировать в любом случае. Может случиться, что установки некоторого объекта в сигнальное состояние ожидают сразу несколько потоков. В зависимости от объекта синхронизации в состояние готовности могут переводиться либо все ожидающие это собы-тие потоки, либо один из них. Синхронизация тесно связана с планированием потоков. Во-первых, любое обращение потока с системным вызовом Wait(X) влечет за собой дей-ствия в подсистеме планирования - этот поток снимается с выполнения и помещается в очередь ожидающих потоков, а из очереди готовых потоков выбирается и активизируется новый поток. Во-вторых, при переходе объекта в сигнальное состояние (в результате выполнения некоторого потока - либо системного, либо прикладного) ожидающий этот объект поток (или потоки) переводится в очередь готовых к выполнению потоков. В обоих случаях осуществляется перепланирование потоков, при этом если в ОС предусмот-рены изменяемые приоритеты и/или кванты времени, то они пересчитывают-ся по правилам, принятым в этой операционной системе. Рассмотрим несколько примеров, когда в качестве синхронизирую-щих объектов используются файлы, потоки и процессы. Пусть программа приложения построена так, что для выполнения за-просов, поступающих из сети, основной поток создает вспомогательные сер-верные потоки. При поступлении от пользователя команды завершения приложения основной поток должен дождаться завершения всех серверных потоков и только после этого завершиться сам. Следовательно, процедура завершения должна включать вызов Wait(Xl, Х2. ...), где X1, Х2 - указатели на серверные потоки. В результате выполнения данного системного вызова основной поток будет переведен в состояние ожидания и останется в нем до тех пор, пока все серверные потоки не перейдут в сигнальное состояние, то есть завершатся. После этого ОС переведет основной поток в состояние готовности. При по-лучении доступа к процессору основной поток завершится. Другой пример. Пусть выполнение некоторого приложения требует последовательных работ-этапов. Для каждого этапа имеется свой отдельный процесс. Сигналом для начала работы каждого следующего процесса являет-ся завершение предыдущего. Для реализации такой логики работы необхо-димо в каждом процессе, кроме первого, предусмотреть выполнение систем-ного вызова Wait(X), в котором синхронизирующим объектом является предшествующий поток. Объект-файл, переход которого в сигнальное состояние соответствует завершению операции ввода-вывода с этим файлом, используется в тех слу-чаях, когда поток, инициировавший эту операцию, решает дождаться ее за-вершения, прежде чем продолжить свои вычисления. Однако круг событий, с которыми потоку может потребоваться син-хронизировать свое выполнение, отнюдь не исчерпывается завершением по-тока, процесса или операции ввода-вывода. Поэтому в ОС, как правило, имеются и другие, более универсальные объекты синхронизации, такие как событие (event), мьютекс (mutex), системный семафор и другие. Мьютекс, как и семафор, обычно используется для управления досту-пом к данным. В отличие от объектов-потоков, объектов-процессов и объектов-файлов, которые при переходе в сигнальное состояние переводят в состояние готовности все потоки, ожидающие этого события, объект-мьютекс "освобо-ждает" из очереди ожидающих только один поток. Работа мьютекса хорошо поясняется в терминах "владения". Пусть поток, который, пытаясь получить доступ к критическим данным, выполнил системный вызов Wait(X), где Х - указатель на мьютекс. Предположим, что мьютекс находится в сигнальном состоянии, в этом случае поток тут же ста-новится его владельцем, устанавливая его в несигнальное состояние, и вхо-дит в критическую секцию. После того как поток выполнил работу с крити-ческими данными, он "отдает" мьютекс, устанавливая его в сигнальное со-стояние. В этот момент мьютекс свободен и не принадлежит ни одному по-току. Если какой-либо поток ожидает его освобождения, то он становится следующим владельцем этого мьютекса, одновременно мьютекс переходит в несигнальное состояние. Объект-событие (в данном случае слово "событие" используется в уз-ком смысле, как обозначение конкретного вида объектов синхронизации) обычно используется не для доступа к данным, а для того, чтобы оповестить другие потоки о том, что некоторые действия завершены. Пусть, например, в некотором приложении работа организована таким образом, что один поток читает данные из файла в буфер памяти, а другие потоки обрабатывают эти данные, затем первый поток считывает новую порцию данных, а другие по-токи снова ее обрабатывают и так далее. В начале работы первый поток ус-танавливает объект-событие в несигнальное состояние. Все остальные пото-ки выполнили вызов Wait(X), где Х - указатель события, и находятся в приос-тановленном состоянии, ожидая наступления этого события. Как только бу-фер заполняется, первый поток сообщает об этом операционной системе, вы-полняя вызов Set(X). Операционная система просматривает очередь ожи-дающих потоков и активизирует все потоки, которые ждут этого события. Продолжение следует...
|
Copyright (C) 2004 UzhOS-Team |
Ведущий рассылки Igene Smith (winexp[@]yandex.ru) |
Designed by Vladimir Tsarkov (bvbn[@]lipetsk.ru) |
http://subscribe.ru/
http://subscribe.ru/feedback/ |
Подписан адрес: Код этой рассылки: comp.soft.othos.osmaker |
Отписаться |
В избранное | ||