[Www distributed net] или поиск
[www.distributed.net] или поиск внеземных цивилизаций [www.seti.org] поддаются масштабированию очень хорошо: можно включить в работу десятки и сотни тысяч процессоров, передавая при этом между ними относительно малые объемы данных. В этих случаях часто оказывается Целесообразно даже не устанавливать процессоры в одну машину, а использовать множество отдельных компьютеров, соединенных относительно низкоскоростными каналами передачи данных. Это позволяет задействовать процессоры, подключенные к сети (например, к Интернет) и не занятые в данный момент другой полезной работой.
Другие задачи, например, работа с базами данных, поддаются распараллеливанию в гораздо меньшей степени, однако и в этом случае обработка запросов может быть распределена между несколькими параллельно работающими процессорами. Количество процессоров в серверах СУБД обычно измеряется несколькими штуками, они подключены к обшей шине, совместно используют одну и ту же оперативную память и внешние устройства.
Многопроцессорность в таких системах обычно применяется только для ц0. вышения производительности, но очевидно, что ее же можно использовать и для повышения надежности: когда функционируют все процессоры, система работает быстро, а с частью процессоров работает хоть что-то, пусть и медленнее.
Некоторые многопроцессорные системы поддерживают исполнение на ных процессорах различных ОС — так, на IBM z90 часть процессоров M исполнять Linux, а остальные — z/OS. В такой конфигурации, работающий под управлением Linux Web-сервер может взаимодействовать с работающим под z/OS сервером транзакций через общую физическую память. Многопроцессорные серверы Sun Fire могут исполнять несколько копий Solaris.
Промежуточное положение между этими крайностями занимают специализированные массивно-параллельные компьютеры, используемые для таких задач, как численное решение эллиптических дифференциальных уравнений и численное же моделирование методом конечных элементов в геофизических, метеорологических и некоторых других приложениях.
Современные суперкомпьютеры этого типа (IBM „SP6000, Cray Origin) состоят из десятков, сотен, а иногда и тысяч отдельных процессорных модулей (каждый модуль представляет собой относительно самостоятельную вычислительную систему, обычно многопроцессорную, с собственной памятью и, нередко, с собственной дисковой подсистемой), соединенных между собой высокоскоростными каналами. Именно к этому типу относился шахматный суперкомпьютер Deep Blue, выигравший в 1997 году матч у чемпиона мира по шахматам Гарри Каспарова
[Www ibm com NUMAQ] Понятно что
[www.ibm.com NUMA-Q].
Понятно, что обе эти архитектуры не решают в корне проблемы неоднородности доступа: для обеих можно построить такую последовательность межпроцессорных взаимодействий, которая промоет1 все кэши и перегрузит межмодульные связи, а в случае СОМА приведет к постоянной перекачке страниц памяти между модулями. То же самое, впрочем, справедливо и для симметричных многопроцессорных систем с общей шиной.
В качестве резюме можно лишь подчеркнуть, что масштабируемость (отношение производительности системы к количеству процессоров) многопроцессорных систем определяется в первую очередь природой задачи и уровнем параллелизма, заложенным в использованный для решения этой задачи алгоритм. Разные типы многопроцессорных систем и разные топологии межпроцессорных соединений пригодны и оптимальны для различных задач.
Промывание кэша— довольно распространенный термин. Это последовательность обращении, которая намного больше объема кэша и в которой нет ни одного повторного обращения к одной и той же странице, или очень мало таких обращении.
[Www intel com Moore]) то производительность
[www.intel.com Moore]), то производительность многопроцессорных систем удваивается каждые десять месяцев [www.sun.com 2001-05].
На практике, даже хорошо распараллеливаемые алгоритмы практически никогда не обеспечивают линейного роста производительности с ростом числа процессоров. Это обусловлено, прежде всего, расходами вычислительных ресурсов на обмен информацией между параллельно исполняемыми потоками. На первый взгляд, проще всего осуществляется такой обмен в системах с процессорами, имеющими общую память, т. е. собственно многопроцессорных компьютерах.
В действительности, оперативная память имеет конечную, и небольшую по сравнению с циклом центрального процессора, скорость доступа. Даже один современный процессор легко может занять все циклы доступа ОЗУ, а несколько процессоров будут непроизводительно тратить время, ожидая доступа к памяти. Многопортовое ОЗУ могло бы решить эту проблему, но такая память намного дороже обычной, однопортовой, и применяется лишь в особых случаях и в небольших объемах.
Одно из основных решений, позволяющих согласовать скорости ЦПУ и ОЗУ, — это снабжение процессоров высокоскоростными кэшами команд и данных. Такие кэши нередко делают не только для центральных процессоров, но и для адаптеров шин внешних устройств. Это значительно уменьшает количество обращений к ОЗУ, однако мешает решению задачи, ради которой мы и объединяли процессоры в единую систему: обмена данными между потоками, исполняющимися на разных процессорах (Рисунок 6.2).
Www microchip com PICMicro
([www.microchip.com PICMicro] утверждает, что средняя задержка прерывания составляет 3,75 цикла). Таким образом, среднее время реакции на событие в режиме опроса составляет 2,5 цикла (по среднему времени опрос в выигрыше), а максимальное -5 циклов (в данном случае преимущество на стороне прерываний).
Однако у процессоров общего назначения, которые при обработке прерывания вынуждены сохранять несколько регистров и осуществлять относительно сложный диалог с вызвавшим прерывание устройством, задержка между установкой сигнала прерывания и исполнением первой команды его обработчика — этот интервал и называется задержкой прерывания (interrupt latency) — составляет десятки тактов.
Современные суперскалярные процессоры при обработке прерываний вынуждены сбрасывать очередь предварительной выборки команд и, по крайней мере, часть кэшей команд и данных, поэтому у .них накладные расходы еще больше. Задержка прерывания у современных реализаций архитектуры х86 лишь ненамного лучше, чем у 80386 хотя по скорости исполнения последовательных программ современные процессоры превосходят 80386 на несколько порядков. Поэтому младшие модели процессоров с архитектурой х86, 8086 и даже 8085, хотя и не находят применения в персональных компьютерах, но продолжают выпускаться для использования во встраиваемых приложениях или в качестве периферийных процессоров.
Так, например, "марсоход" Sojoumer использовал в качестве управляющего процессора 8085 на сапфировой подложке (для обеспечения радиационной устойчивости).
Это же обстоятельство является дополнительным доводом в пользу включения в систему канальных процессоров, в данном случае с целью освобождения центрального процессора не от опроса, а от обработки прерываний. Разработчики больших компьютеров часто реализовывали канальные процессоры старших моделей на основе центральных процессоров младших моделей той же серии.
[Www research ibm com]
[www.research.ibm.com].
Многопроцессорные системы различного рода получают все более и более широкое распространение. Если производительность отдельного процессора удваивается в среднем каждые полтора года ("закон Мура"
Гиперкубы с 4 8 и 16ю вершинами
Рисунок 6.5. Гиперкубы с 4, 8 и 16-ю вершинами
Различие в скорости доступа к локальной памяти процессорного модуля и Других модулей является проблемой, и при неудачном распределении загрузки между модулями (таком, что межмодульные обращения будут часты) Приведет к значительному снижению производительности системы. Известны два основных пути смягчения этой проблемы.
СОМА (Cache Only Memory Architecture) — архитектура памяти, при которой работа с ней происходит как с кэшем. Система переносит страницы памяти, с которой данный процессорный модуль работает чаще других, в его локальную память.Исключения
Исключения
Многие процессоры используют механизм, родственный прерываниям, для обработки не только внешних, но и внутренних событий: мы с вами уже сталкивались с исключительными ситуациями (exception) отсутствия страницы и ошибки доступа в процессорах с виртуальной памятью, а также некоторыми другими — ошибкой шины при доступе к невыровненным словам, заполнению и очистке регистрового окна у SPARC и т. д. Большинство современных процессоров предоставляют исключения при неизвестном коде операции, делении на ноль, арифметическом переполнении или, например, выходе значения операнда за допустимый диапазон в таких операциях, как вычисление логарифма, квадратного корня или арксинуса.
Исключительные ситуации обрабатываются аналогично внешним прерываниям: исполнение программы останавливается, и управление передается на процедуру-обработчик, адрес которой определяется природой исключения.
Отличие состоит в том, что прерывания обрабатываются после завершения текущей команды, а возврат из обработчика приводит к исполнению команды, следующей за прерванной. Исключение же приводит к прекращению исполнения текущей команды (если в процессе исполнения команды мы уже успели создать какие-то побочные эффекты, они отменяются), и сохраненный счетчик команд указывает на прерванную инструкцию. Возврат из обработчика, таким образом, приводит к попытке повторного исполнения операции, вызвавшей исключение.
Благодаря этому, например, обработчик страничного отказа может подкачать с диска содержимое страницы, вызвавшей отказ, перенастроить таблицу дескрипторов и повторно исполнить операцию, которая породила отказ. Обработчик исключения по неопределенному коду операции может использоваться для эмуляции расширений системы команд.
Например, при наличии арифметического сопроцессора операции с плавающей точкой исполняются им, а при отсутствии — пакетом эмулирующих подпрограмм. Благодаря этому может обеспечиваться полная бинарная совместимость между старшими (имеющими сопроцессор) и младшими (не имеющими его) моделями одного семейства компьютеров.
Исключения, возникающие при исполнении привилегированных команд в пользовательском режиме, могут использоваться системой виртуальных машин. Работающее в виртуальной машине ядро ОС считает, что исполняется в системном режиме. На самом же деле оно работает в пользовательском режиме, а привилегированные команды (переключения режима процессора, настройка диспетчера памяти, команды ввода/вывода) приводят к вызову СВМ.
При грамотной реализации обработчиков таких исключений их обработка Произойдет полностью прозрачно для породившей эти исключения программы. Конечно, "подкачка" страницы с диска или программная эмуляция плавающего умножения займет гораздо больше времени, чем простое обращение к памяти или аппаратно реализованное умножение, но, наверное, Потребитель вычислительной системы знал, что делал, когда устанавливал недостаточное количество памяти или приобретал машину без сопроцессора.
Многие другие исключения, такие, как деление на ноль, обычно бессмЬ1с ленно обрабатывать повторной попыткой деления на какое-то другое число В этом случае целесообразно возвратить управление не на команду, вызвав шую исключение, а в какую-то другую точку. Вопрос, впрочем, в том, куда именно следует возвращаться. Понятно, что код, который может восстано виться в случае деления на ноль, сильно зависит от контекста, в котором произошла ошибка (пример 6.2).
Канальные процессоры и прямой доступ к памяти
Канальные процессоры и прямой доступ к памяти
Одно из решений состоит в том, чтобы завести отдельный процессор и поручить ему всю работу по опросу. Процессор, занимающийся только организацией ввода-вывода, называют периферийным или канальным (channel).
Понятно, впрочем, что это повышает стоимость системы и не решает проблемы радикально — теперь вместо флагов, непосредственно сигнализирующих о внешних событиях, центральный процессор вынужден опрашивать флаги, выставляемые канальным процессором. В зависимости от характера событий и требуемой обработки это решение может оказаться и совсем неприемлемым, например, если на каждое событие требуется немедленная реакция именно центрального процессора.
В противном случае, если немедленно после события требуется лишь простая обработка, а сложные вычисления можно отложить на потом, канальный процессор можно упростить и сделать существенно дешевле центрального.
Так, при работе с контроллерами дисков, лент и других устройств массовой памяти возникает задача копирования отдельных байтов (или, в зависимости от разрядности шины контроллера, полуслов или слов) из контроллера в память и обратно. Передача одного блока (512 байт у большинства современных контроллеров) состоит из 128 операций передачи слова, идущих друг за другом с небольшими интервалами. Темп передачи данных определяется скоростью вращения диска или движения ленты. Этот темп обычно ниже скорости системной шины, поэтому передача данных должна включать в себя опрос признака готовности контроллера принять или предоставить следующее слово. Интервал между словами обычно измеряется несколькими циклами шины. Нередко бывает и так, что частоты шины и контроллера не кратны, поэтому последовательные слова надо передавать через различное число циклов.
Дополнительная сложность состоит в том, что, не предоставив вовремя следующее слово для записи, мы испортим весь процесс — эта проблема особенно серьезна на устройствах однократной записи, например прожигателях компакт-дисков. Аналогично, не успев прочитать очередное слово, мы потеряем его и вынуждены будем отматывать ленту назад пли ждать следующего оборота диска.
Видно, что это именно та ситуация, которую мы ранее описывали как показание к использованию режима опроса: поток следующих друг за другом с небольшим интервалом событий, каждое из которых нельзя потерять, а нужно обязательно обработать.
Обработка события, которая нужна, чтобы избежать такой неприятности, крайне проста, так что устройство, способное с ней справиться, не обязано даже быть полностью программируемым процессором.
При передаче надо всего лишь убедиться, что блок данных не кончился, взять следующее слово из памяти, дождаться готовности устройства, скопировать слово и вернуться к началу алгоритма. Если блок данных кончился или контроллер выдал ошибку, необходимо сообщить об этом центральному процессору.
Для реализации этого алгоритма достаточно трех регистров (указателя в памяти, значения текущего слова и счетчика переданных слов). Реализующее этот алгоритм устройство называют контроллером прямого доступа к памяти (Direct Memory Access controller, DMA controller) (Рисунок 6.1). Такие контроллеры часто рассчитаны на одновременную работу с несколькими устройствами — имеют несколько каналов — и, соответственно, больше регистров. Описание реальной микросхемы контроллера ПДП можно найтив [Паппас/Марри 1993].
Обычно контроллеры ПДП не считают процессорами, однако без большой натяжки можно сказать, что это все-таки канальный процессор, хотя и очень примитивный. Контроллеры ПДП, рассчитанные на совместную работу с процессором, обладающим виртуальной памятью, часто имеют некий аналог диспетчера памяти ЦП, для того, чтобы позволить операционной системе предоставлять указатель для ПДП в виртуальном адресном пространстве, или, во всяком случае, упростить работу по преобразованию виртуального адреса в физический.
Различают два типа реализаций ПДП:
Компьютер и внешние события
Компьютер и внешние события
| Мы ждали его слишком долго. Что может бытьглупее, чем ждать? Б. Гребенщиков |
Практически все функции современных вычислительных систем так или иначе
сводятся к обработке внешних событий. Единственная категория приложений,
для которых внешние события совершенно неактуальны — это так называемые
пакетные приложения, чаще всего — вычислительные задачи. Доля таких задач в общем объеме компьютерных приложений в наше время невелика и постоянно
падает. В остальных же случаях, даже если не вспоминать о специализированных
управляющих компьютерах, серверы обрабатывают внешние по отношению к ним
запросы клиентов, а персональный компьютер — реагирует на действия пользователя.
Различие между управляющими системами (приложениями реального времени)
и системами общего назначения (термин — система разделенного времени вышел из употребления и не всегда точно отражает суть дела) состоит лишь в том,
что первые должны обеспечивать гарантированное время реакции на событие,
в то время как вторые "всего лишь" — предоставить хорошее среднее
время такой реакции и/или обработку большого количества событий в секунду.
Примечание
Примечание
Время обработки одного события и количество событий, обрабатываемых в
единицу времени, далеко не всегда являются жестко взаимосвязанными — ведь при многопоточной обработке система может обрабатывать несколько событий параллельно.
Единственный способ, которым фон-неймановский компьютер может отреагировать
на что бы то ни было — это исполнить программу, последовательность команд.
В случае внешнего события, естественным решением кажется предоставить
команду условного перехода, условием которого является признак события.
В системах команд микроконтроллеров частореализуют именно такие переходы (см. например табл. 2.2). В качестве признака события в этом случае используется значение одного из битов специального регистра, биты которого соответствуют входам микросхемы контроллера. Бит равен единице, если на соответствующий вход подано высокое напряжение, и нулю — если низкое.
Наличие таких команд полезно, но решает проблему не полностью: да, сели событие произошло, мы моыжем вызвать программу и осуществить реакцию но что мы будем делать, если его еще не происходило?
Массивно параллельные системы Cray/SGI Origin
Массивно параллельные системы Cray/SGI Origin
Узлы суперкомпьютеров семейства Cray/SGI Origin соединены в гиперкуб каналами с пропускной способностью 1 Гбайт/с. Адаптеры соединений обеспечивают не просто обмен данными, а прозрачный (хотя и с падением производительности) доступ процессоров каждого из узлов к оперативной памяти других узлов и обеспечение когерентности процессорных кэшей.
Многопроцессорные архитектуры
Многопроцессорные архитектуры
Как уже говорилось, относительно большие накладные расходы, связанные с обработкой прерываний, нередко делают целесообразным включение в систему дополнительных процессоров. Есть и другие доводы в пользу создания многопроцессорных вычислительных систем.
Одним из доводов является повышение надежности вычислительной системы посредством многократного резервирования. Если один из процессоров многопроцессорной системы отказывает, система может перераспределить загрузку между оставшимися. Для компьютеров первых поколений, у которых наработка аппаратуры процессора на отказ была относительно невелика, повышение надежности таким способом часто оказывалось целесообразным, особенно в приложениях, требовавших круглосуточной доступности.
Примечание
Примечание
Понятно, что для обеспечения непрерывной доступности недостаточно просто поставить много процессоров, и даже недостаточно уметь своевременно обнаружить отказ и исключить сломавшийся процессор из системы. Необходима также возможность заменить отказавший узел без выключения и без перезагрузки системы, что накладывает весьма жесткие требования и на конструкцию корпуса, и на электрические параметры межмодульных соединений, и, наконец, на программное обеспечение, которое должно обнаружить вновь добавленный процессорный модуль и включить его в конфигурацию системы.
Другим доводом в пользу включения в систему дополнительных процессоров является тот факт, что алгоритмы, используемые для решения многих прикладных задач, нередко поддаются распараллеливанию: разделению работы между несколькими более или менее независимо работающими процессорами. В зависимости от алгоритма (и, косвенно, от природы решаемой задачи) уровень достижимого параллелизма может сильно различаться. Отношение производительности системы к количеству процессоров и производительности однопроцессорной машины называют коэффициентом масштабирования. Для различных задач, алгоритмов, ОС и аппаратных архитектур этот коэффициент различен, но всегда меньше единицы и всегда убывает по мере увеличения количества процессоров.
Некоторые задачи, например, построение фотореалистичных изображений методом трассировки лучей, взлом шифров полным перебором пространства ключей
Некогерентный кэш
Рисунок 6.2. Некогерентный кэш
Большинство контроллеров кэшей современных процессоров предоставляют средства обеспечения когерентности кэша — синхронизацию содержимого кэш-памятей нескольких процессоров без обязательной записи данных в основное ОЗУ.
Суперскалярные процессоры, у которых порядок реального исполнения операций может не совпадать с порядком, в котором соответствующие команды следуют в программе, дополнительно усугубляют проблему.
NUMAQ с тремя четырехпроцессорными модулями
Рисунок 6.4. NUMA-Q с тремя четырехпроцессорными модулями
Порядок доступа к памяти в SPARC
Порядок доступа к памяти в SPARC
Современные процессоры предоставляют возможность управлять порядком доступа команд к памяти. Например, у микропроцессоров SPARCvQ [www.sparc.com v9] определены три режима работы с памятью (модели памяти), переключаемые битами в статусном регистре процессора.
Свободный доступ к памяти (RMO, Relaxed Memory Order), когда процессор использует все средства кэширования и динамического переупорядочения команд, и не пытается обеспечить никаких требований к упорядоченности выбор-ки и сохранению операндов в основной памяти.
Частично упорядоченный доступ (PSO, Partial Store Order), когда процессор по-прежнему использует и кэширование, и переупорядочивание, но в потоке команд могут встречаться команды MEMBAR. Встретив такую команду, сор обязан гарантировать, что все операции чтения и записи из памяти, зако дированные до этой команды, будут исполнены (в данном случае под исполнением подразумевается перенос результатов всех операций из кэша в ОЗУ), д0 того, как процессор попытается произвести любую из операций доступа к памяти, следующих за MEMBAR.
Полностью упорядоченный доступ (TSO, Total Store Order), когда процессор гарантирует, что операции доступа к памяти будут обращаться к основному ОЗУ в точности в том порядке, в котором закодированы.
Каждый следующий режим повышает уверенность программиста в том, что его программа прочитает из памяти именно то, что туда записал другой процессор, но одновременно приводит и к падению производительности. Наибольший проигрыш обеспечивает наивная реализация режима TSO, когда мы просто выключаем и динамическое переупорядочение команд, и кэширование данных (кэширование кода можно оставить, если только мы не пытаемся исполнить код, который подвергается параллельной модификации другим задатчиком шины).
Другим узким местом многопроцессорных систем является системная шина. Современные компьютеры общего назначения, как правило, имеют шинную архитектуру, т. е. и процессоры, и ОЗУ, и адаптеры шин внешних устройств (PCI и т. д.) соединены общей магистралью данных, системной шиной или системной магистралью. В каждый момент магистраль может занимать только пара устройств, задатчик и ведомый (Рисунок 6.3). Обычно, задатчиком служит процессор — как центральный, так и канальный — или контроллер ПДП, а ведомым может быть память или периферийное устройство. При синхронизации содержимого кэшей процессорный модуль также может оказаться в роли ведомого.
Прерывания
Прерывания
Альтернатива опросу, применяемая практически во всех современных процессорах, называется прерываниями (interrupt), и состоит в значительном усложнении логики обработки команд процессором.
Процессор имеет один или несколько входов, называемых сигналами или линиями запроса прерывания. При появлении сигнала на одном из входов, Процессор дожидается завершения исполнения текущей команды и, вместо перехода к исполнению следующей команды, инициирует обработку прерывания.
Обработка состоит в сохранении счетчика команд и, возможно, некоторм других регистров (практически всегда сохраняется также слово состояния процессора. В процессорах с виртуальной памятью иногда сохраняются и регистры диспетчера памяти), и в передаче управления на адрес, определяемый типом прерывания. По этому адресу размещается программа, обработчик прерывания, которая и осуществляет реакцию на соответствующее прерыванию событие. Перед завершением обработчик восстанавливает регистры, и исполнение основной программы возобновляется с той точки, где она была прервана.
Как правило, адреса программ, соответствующих различным прерываниям собраны в таблицу, называемую таблицей векторов прерываний, размещаемую в определенном месте адресного пространства. У микроконтроллеров каждому возможному сигналу прерывания обычно соответствует свой вектор. Процессоры общего назначения часто используют более сложную схему, в которой устройство, запрашивающее прерывание, передает процессору номер прерывания или сразу адрес обработчика.
Для примера рассмотрим организацию прерываний
Прерывания в PDP-11
Для примера рассмотрим организацию прерываний в машинах семейства PDP-11. Процессоры данной архитектуры сейчас практически не используются в машинах общего назначения, но производятся и применяются в качестве микроконтроллеров. Ряд архитектурных решений PDP-11, разработанной в начале 70-х годов, не потерял актуальности и поныне. В частности, подход к реализации прерываний считается классическим [Кейслер 1986].
Процессоры семейства PDP-11 различают 128 типов прерываний и исключений (чем прерывание отличается от исключения, см. далее). Каждому типу соответствует процедура-обработчик. Адреса точек входа всех процедур собраны в таблицу векторов прерываний. Эта таблица занимает 256 слов физической памяти, начиная с нулевого адреса. Каждый элемент таблицы (вектор) содержит адрес обработчика и новое слово состояния процессора. Позже будет объяснено, для чего это сделано.
Процессор узнает о возникновении прерывания, если на один из входов запроса подан сигнал. Обычно этот сигнал генерируется одним из внешних устройств. Например, прерывание может сигнализировать о завершении операции перемещения головки дисковода или передачи данных в режиме ПДП.
Каждый вход соответствует определенному уровню приоритета. PDP-11 имеет восемь уровней приоритета прерывания. Прерывание происходит только когда уровень приоритета процессора ниже приоритета запрашиваемого прерывания. Если у процессора установлен приоритет, равный 7, внешние прерывания запрещены. Приоритет процессора задается его словом состояния. Получив запрос, процессор завершает исполнение текущей команды и выставляет
сигнал готовности к прерыванию. После этого внешнее устройство выставляет на шине данных номер вектора прерывания.
Процессор считывает номер и вызывает соответствующую процедуру из таблицы. При этом вызов обработчика прерывания отличается от вызова обычной процедуры: при обычном вызове в стеке сохраняется только адрес команды, на которую следует возвратить управление. При прерывании же в стеке сохраняются два значения: адреса команды и слова состояния процессора. Новое слово состояния берется из таблицы векторов.
При этом приоритет процессора автоматически устанавливается равным тому значению, которое разработчик программы обработки считает правильным. Обратите внимание: не равным приоритету обрабатываемого прерывания, а тому, которое требует разработчик.
При завершении процедуры обработки вызывается команда RTI (ReTurn from Interrupt— возврат из прерывания). Эта команда выталкивает из стека адрес прерванной команды и старое слово состояния, тем самым и продолжая исполнение прерванной программы, и восстанавливая приоритет процессора. [Кичев/Некрасов 1988].
Для сравнения: в процессорах семейства 180x86 вектор прерывания содержит только адрес программы-обработчика, а приоритет процессора задается не словом состояния процессора, а регистром внешнего устройства— контроллера прерываний. Контроллер прерываний обычно устанавливает приоритет, равным приоритету прерывания, обрабатываемого в данный момент. Чтобы повысить или понизить этот уровень, обработчик прерывания должен программировать контроллер. Перед завершением обработчика необходимо вернуть контроллер прерываний в исходное состояние, выполнив над ним серию магических команд — эпилог прерывания.
Обработка прерываний в системах с виртуальной памятью несколько усложняется: ведь кроме адреса обработчика нам надо еще задать адресное пространство, в котором этот адрес определен. В моделях PDP-11, имеющих диспетчер памяти, эта проблема решается просто: для процессора в каждый момент времени заданы два адресных пространства: пользовательское и системное. Все прерывания обрабатываются в системном адресном пространстве. Для реализации этого процессор имеет два набора регистров диспетчера памяти. Их наличие, с одной стороны, снимает с обработчика прерывания обязанность переключать адресные пространства, а с другой позволяет ядру при обработке системных вызовов обращаться к сегменту данных пользовательского процесса.
В защищенном режиме процессоров 180x86 использован более гибкий механизм установки адресного пространства для обработчика. По существу, с каждым обработчиком может быть ассоциировано свое виртуальное адресное пространство. О способе, которым это достигается, лучше прочитать в литературе по соответствующим процессорам, например [Паппас/Марри 1993]. Прерывания лишены недостатков, которые мы указали и выше для обработки событий при помощи опроса: ожидая события, процессор может заниматься какой-либо другой полезной работой, а когда событие произойдет, он приступит к обработке, не дожидаясь полного завершения этой работы.
Однако этот механизм имеет и собственные недостатки. В частности, обработка прерывания сопряжена с гораздо большими накладными расходами чем проверка флага и условный переход в режиме ожидания. У оптимизированных для обработки событий микроконтроллеров разница невелика или даже может быть в пользу механизма прерываний: приведенный в примере 6.1 цикл опроса занимает 5 циклов процессора, а обработчик прерывания у PIC вызывается в течение 3—4 циклов
Пример использования режима опроса
Пример 6.1. Пример использования режима опроса
; Приведенный фрагмент кода использует опрос таймера TMRO,
; работающего от "часового" кварцевого генератора с частотой 32768Гц.
; Цикл опроса в чистом виде TMRO — регистр таймера,
; Timervalue — просто переменная,
; регистр 0 — аккумулятор, обозначаемый также как W.
; Такой цикл ожидает одного отсчета таймера.
MovF TMRO, 0
MovWF TimerValue
G5H_Continuel
MovF TimerValue, 0
SubWF TMRO, 0
BNZ G5H_Continuel
; Код содержит два цикла опроса: первый цикл генерирует ; сигнал высокого напряжения, второй — низкого.
; В результате получается периодический сигнал, называемый меандром.
; Фрагмент определителя номера на основе микроконтроллера PIC
; (с) 1996, Дмитрий Иртегов.
; Запрос к АТС ка выдачу номера.
; Генератор меандра с частотой 501.5 гц. Выдает 50 периодов (100 мс).
; генерирует 2 периода по 16 тиков и один — по 17.
; Получается очень похоже.
6enerate500Hz
MovLW 50
MovWF AONByteCounter
MovLW 3
MovWF Tmpl
MovF TMRO, 0
MovWF TimerValue G5H_NextPeriod
MovLW 8
AddWF TimerValue, 1
BSF LINE_CTL_PORT, LINE_ANSWER G5H_Continuel
MovF TimerValue, 0
SubWF TMRO, 0
BNZ G5H_Continuel
MovLW 8
AddWF TimerValue, 1
BCF LINE_CTL_PORT, LINE_ANSWER
DecFSZ Tmpl, 1 GoTo G5H_ContinueO
MovLW 3
MovWF Tmpl
IncF TimerValue, 1 G5H_ContinueO
MovF TimerValue, 0
SubWF TMRO, 0
BNZ GSH_ContinueO
DecFSZ AONByteCounter, 1 GoTo G5H_NextPeriod
Return
Этот недостаток можно переформулировать и иначе: если процессор занят Чем-то другим, он может узнать о событии, только завершив текущую Деятельность. Если событие действительно важное, впрочем, мы можем расставить команды проверки его признака по всему коду программы, но для сложных программ, обрабатывающих много различных событий, это решение вряд ли можно считать практичным.
С точки зрения встраиваемых приложений, режим опроса имеет еще один существенный недостаток: опрашивающий процессор нельзя выключить В то же время, выключенный процессор потребляет гораздо меньше энергии и не создает электромагнитных помех, поэтому при разработке программ для таких приложений считается хорошим тоном выключать (переводить в режим ожидания) процессор всегда, когда это возможно. В этом случае конечно, необходимо предусмотреть какие-либо средства для вывода процессора из этого состояния при возникновении интересующего нас события.
Обработка исключения
Пример 6.2. Обработка исключения Floating underflow (антипереполние при операциях с плавающей точкой)
#tinclude <setjmp.h>
static jmp_buf fpe_retry;
void fpe_handler (int sig) {
4> __fpreset () ; longjmp (fpe__retry, -1) ;
int compare_pgms (Image * imgO, Image * img1) {
int xsize=256, ysize=256;
int i, j , pO, pi, pd;
double avg, avgsq, scale, smooth;
scale= (double) xsize* (double) ysize;
avg = 0.0; avgsq = 0.0;
/* Подавить возможные антипереполнения */
signal (SIGFPE, fpe_handler) ;
for(i=0; i<ysize; i smooth = (double) (imgO->picture [i*xsize] -imgl->picture [i*xsize] ) ; for(j=0; j<xsize; j++) { pO=imgO->picture [ j+i*xsize] ; pl=imgl->picture [ j+i*xsize] ; pd=(pO-pl) ;
if (setjmp (fpe_retry) == 0) { smooth = smooth* (1 . 0-SMOOTH_FACTOR) + (double) pd*SMOOTH_FACTOR;
vq += smooth; avgsq += smooth*smooth;
eise
smooth=0 . 0 ;
if (Setjmp(fpe_retry) == 0)
Aspersion = avgsq/scale-avg*avg/ (scale*scale) ;
else dispersion = 0.0;
signal (SIGFPE, SIGJDFL) ;
}
При программировании на ассемблере это может быть реализовано простой подменой адреса возврата в стеке. Многие языки высокого уровня (ЯВУ) реализуют те или иные средства для обработки исключений. Уровень этих средств различен в разных языках, начиная от пары функций setjmp и longjmp в С [Керниган-Ритчи 2000] (пример 6.3) и заканчивая операторами try/catch и throw C++ [Страуструп 1999] и Java [Вебер 1999].
Исходный текст функций
Пример 6.3. Исходный текст функций set jmp/ longjmp.
/ setjmp. s (emx+gcc) — Copyright (c) 1990-1996 by Eberhard Mattes
# include <emx/asm386.h>
.globl _setjmp, _longjmp
.text ALIGN
# define J_EBX 0
# define J_ESI 4
# define J_EDI 8
#define J_ESP 12
#define J_EBP 16
# define J_EIP 20
# define J_XCP 24
/ Слова со смещениями 28.. 44 зарезервированы
/ int setjmp (jmp_buf here)
_setjmp:
PROFILE__NOFRAME
movl l*4(%esp), %edx /* here */
raovl %ebx, J_EBX(%edx)
movl %esi, J_ESI(%edx)
movl ledi, J_EDI(%edx)
movl %ebp, J_EBP(%edx)
movl %esp, J_ESP(%edx)
movl 0*4(%esp), %eax /* Адрес возврата */
movl %eax, J_EIP(%edx)
cmpb $0, __osmode /* OS/2? */
je If /* No -> skip */
fs
movl 0, leax /* handler Обработчик исключений */
movl %eax, J_XCP(%edx) 1: xorl %eax, leax
EPILOGUE(setjmp)
ALIGN
/ void longjmp (jmp_buf there, int n)
_longjmp:
PROFILE_NOFRAME
cmpb $0, __osmode /* OS/2? */
je 2f /* No -> skip */
movl 1*4(%esp), %eax /* there */
pushl J_XCP(%eax)
call ___unwind2 /* восстановить обработчики сигналов */
addl $4, %esp 2: movl l*4(%esp), ledx /* there */
movl 2*4(%esp), leax /* n */
testl %eax, leax
jne 3f
incl %eax
3: movl J_EBX(%edx), %ebx
movl J_ESI(ledx), lesi
raovl J_EDI(%edx), %edi
movl J EBP(%edx), %ebp
J_ESP(%edx) ,
J_EIP(%edx>, %edx
%edx, 0*4(%espj /* адрес возврата */
EPILOGUE(longjmp) /* well, ... */
Исключения в ЯВУ часто позволяют избежать использования нелюбимого структурными программистами оператора goto. В объектно-ориентированных (ОО) языках этот механизм играет еще более важную роль: в большининстве таких языков — это единственный способ сообщить о неудаче при исполнении конструктора объекта.
Важно подчеркнуть, впрочем, что исключения в смысле ЯВУ и аппаратные исключения процессора — разные вещи. В многозадачной ОС пользовательская программа не имеет непосредственного доступа к обработке прерываний и исключений. ОС предоставляет сервис, позволяющий программисту регистрировать обработчики для тех или иных событий, как соответствующих аппаратным исключениям, так и порождаемых самой операционной системой, но вызов таких обработчиков всегда осуществляется в два этапа: сначала исполняется обработчик, зарегистрированный ядром (пример 6.4), а он, если сочтет нужным и возможным, переключается в пользовательский контекст и вызывает обработчик, зарегистрированный пользователем. Среда исполнения ЯВУ, в свою очередь, может реализовать и свои обработчики между сервисом операционной системы и средствами, доступными программисту.
Обработчик арифметических
Пример 6.4. Обработчик арифметических исключений в ядре Linux I
/*
* Iinux/arch/i386/traps.c *
* Copyright (С) 1991, 1992 Linus Torvalds *
* Поддержка Pentium III FXSR, SSE
* Gareth Hughes <gareth@valinux.com>, May 2000 */
void die(const char * str, struct pt_regs * regs, long err) I
console_verbose(); spin_lock_irq(&die_lock); Printk("%s: %041x\n", str, err & Oxffff}; show_registers(regs);
sPin_unlock_irq(&die_lock);
do_exit (SIGSEGV) ;
static inline void die_if_kernel (const char * str, struct pt_regs * regs long err)
{
if ( ! (regs->eflags & VM_MASK) && ! (3 & regs->xcs) ) die (str, regs, err);
static inline unsigned long get_cr2 (void) { unsigned long address;
/* получить адрес */
_ asm _ ("movl %%cr2, %0" : "=r" (address));
return address;
static void inline do_trap(int trapnr, int signr, char *str, int vm86,
struct pt_regs * regs, long error_code, siginfo_t *info) { if (vm86 && regs->eflags & VM_MASK)
goto vm86_trap; if ( ! (regs->xcs & 3) ) goto kernel_trap;
trap_signal: {
struct task_struct *tsk = current; tsk->thread. error_code = error_code; tsk->thread. trap_no = trapnr; if (info)
force_sig_info (signr, info, tsk) ; else
force_sig (signr, tsk) ; return;
kernel_trap:
unsigned long fixup = search_exception_table(regs->eip); if (fixup)
regs->eip = fixup; else
die(str, regs, error_code); return;
vm86_trap: {
int ret = handle_vm86_trap((struct kernel_vm86_regs *) regs, er-ror_code, trapnr);
if (ret) goto trap_signal; return;
fldefine DO_ERROR(trapnr, signr, str, name) \
asmlinkage void do_tt#name(struct pt_regs * regs, long error_code) \ { \ do_trap(trapnr, signr, str, 0, regs, error_code, NULL); \
Idefine DO_ERROR_INFO(trapnr, signr, str, name, sicode, siaddr) \ asmlinkage void do_t#name(struct pt_regs * regs, long error_code) \ { \
siginfo_t info; \
info.si_signo = signr; \
info.si_errno =0; \
info.si_code = sicode; \
info.si_addr = (void *)siaddr; \
do^trap(trapnr, signr, str, 0, regs, error_code, Sinfo); \ }
ttdefine DO_VM86_ERROR(trapnr, signr, str, name) \
asmlinkage void do_##name(struct pt_regs * regs, long error_code) \ ( \
do_trap(trapnr, signr, str, 1, regs, error_code, NULL); \ }
ttdefine DO_VM86__ERROR_INFO(trapnr, signr, str, name, sicode, siaddr) \
I
asmlinkage void do_##name(struct pt_regs * regs, long error_code) \ { \
siginfo_t info; \
info.si_signo = signr; \
info.si_errno =0; \
info.si_code = sicode; \
info.si_addr = (void *)siaddr; \
do_trap(trapnr, signr, str, 1, regs, error_code, sinfo); \
' "
DO_VM86_ERROR_INFO( 0, SIGFPE, "divide error", divide_error, FPE_INTDIV, regs->eip)
DO_VM86_ERROR( 3, SIGTRAP, "int3", int3)
DO_VM86_ERROR( 4, SIGSEGV, "overflow", overflow)
DO_VM86_ERROR( 5, SIGSEGV, "bounds", bounds)
DO_ERROR_INFO( 6, SIGILL, "invalid operand", invalid_op, ILL_ILLOPN, regs->eip)
DO_VM86_ERROR( 7, SIGSEGV, "device not available", device_not_available) DO_ERROR( 8, SIGSEGV, "double fault", double_fault)
DO_ERROR( 9, SIGFPE, "coprocessor segment overrun", coproces-sor_segment_overrun)
DO_ERROR(10, SIGSEGV, "invalid TSS", invalidJTSSl
DO_ERROR(11, SIGBUS, "segment not present", segment_not_present)
DO_ERROR(12, SIGBUS, "stack segment", stack_segment)
DO_ERROR_INFO(17, SIGBUS, "alignment check", alignment_check, BUS_ADRALN,
get_cr2 () )
Самый длинный путь в гиперкубе
Рисунок 6.6. Самый длинный путь в гиперкубе
CC-NUMA (Cache-Coherent Non-Uniform Memory Access, неоднородный доступ к памяти с обеспечением когерентности кэшей). В этой архитектуре адаптеры межмодульных соединений снабжаются собственной кэшпамятью, которая используется при обращениях к ОЗУ других модулей. Основная деятельность центрального коммутатора и каналов связи состоит в поддержании когерентности этих кэшей
Шинная архитектура
Рисунок 6.3. Шинная архитектура
Доступ к шине регулируется арбитром шины. Практически применяются две основные стратегии арбитража — приоритетная, когда устройство, имеющее высокий приоритет, всегда получает доступ, в том числе и при наличии запросов от низкоприоритетных устройств, и справедливая (fair), когда арбитр гарантирует всем устройствам доступ к шине в течение некоторого количества циклов.
Системы шинной архитектуры просты в проектировании и реализации, к ним легко подключать новые устройства и типы устройств, поэтому такая архитектура получила широкое распространение. Однако, особенно в многопроцессорных системах, шина часто является одним из основных ограничителей производительности. Повышение пропускной способности шины зачастую возможно, но приводит к повышению обшей стоимости системы.
Впрочем, при большом количестве узлов проблемы возникают и у систем со столь высокоскоростной шиной, как FirePane. Кроме того, по мере роста физических размеров системы, становится необходимо принимать во внимание физическую скорость передачи сигналов — как сигналов самой магистрали, так и запросов к арбитру шины и его ответов. Поэтому шинная топология соединений при многих десятках и сотнях узлов оказывается .неприемлема, и применяются более сложные топологии.
Системы NUMAQ
Системы NUMA-Q
Многопроцессорные серверы IBM NUMA-Q состоят из отдельных процессорных модулей. Каждый модуль имеет собственную оперативную память и четыре процессора х86. Модули называются quad (четверки) (Рисунок 6.4).
Четверки соединены высокоскоростными каналами IQ-Link с центральным коммутатором. Замена общей шины на звездообразную топологию с центральным коммутатором позволяет решить проблемы арбитража доступа к шине, в частности, устранить задержки при запросе к арбитру шины и ожидании его ответа запрашивающему устройству. NUMA-системы фирмы IBM могут содержать до 16 четверок, т. е. до 64 процессоров.
Архитектура позволяет также включать в эти системы процессоры с архитектурой, отличной от х86, например RS/6000 и System/390, позволяя, таким образом, создать в пределах одной машины гетерогенную сеть со сверхвысокоскоростными каналами связи.
При большем числе модулей применяются еще более сложные топологии, например гиперкубическая. В таких системах каждый узел обычно также содержит несколько процессоров и собственную оперативную память (Рисунок 6.5).
При гиперкубическом соединении, количество узлов N пропорционально степени двойки, а каждый узел имеет log2N соединений с другими узлами. Каждый узел способен не только обмениваться сообщениями с непосредственными соседями по топологии, но и маршрутизировать сообщения между узлами, не имеющими прямого соединения. Самый длинный путь между узлами, находящимися в противоположных вершинах куба, имеет длину log2N и не является единственным (Рисунок 6.6). Благодаря множественности путей, маршрутизаторы могут выбирать для каждого сообщения наименее загруженный в данный момент путь или обходить отказавшие узлы.
Структура контроллера ПДП
Рисунок 6.1. Структура контроллера ПДП
В качестве альтернативы ПДП можно предложить снабжение устройства буфером, который работает с частотой системной шины. Центральный процессор передает данные в буфер, и лишь когда заканчивает передачу, инициирует операцию устройства. Логика работы самого устройства с этим буфером, впрочем, ничем не отличается от ПДП, с той лишь разницей, что используется не общесистемная, а встроенная память. На практике, оба подхода часто используются совместно: ПДП позволяет минимизировать загрузку центрального процессора, а буфер — избежать потери данных, если системная шина занята другим устройством.
Типичный современный дисковый контроллер имеет и средства ПДП, и внутренний буфер. У кэширующих (имеющих кэш-память) и RAID-контроллеров объем буфера может измеряться многими мегабайтами. Кроме того, современные жесткие диски также имеют собственные буферы.
Периферийные процессоры находят широкое применение в современных вычислительных системах. Так, типичный современный персональный компьютер, кроме центрального процессора, обычно имеет и специализированный видеопроцессор, так называемый графический ускоритель. У кэширующих дисковых контроллеров и аппаратных реализаций RAID (см. разд. Дисковые массивы) обычно также есть собственный процессор, в данном случае, как правило, используются полностью программируемые процессоры. Лазерные и струйные печатающие устройства имеют процессор, который интерпретирует команды языка управления принтером (PCL или Postscript), есть процессоры модемах и во многих других периферийных устройствах. Впрочем, нередко встречаются и попытки обратить процесс децентрализации вычислений -так называемые "софтовые" или Win-модемы (называемые так потому, что программное обеспечение, способное работать с таким модемом, часто поставляется только под Windows), многие бытовые принтеры и т. д.
В отличие от перечисленных устройств, классический полностью программируемый канальный процессор подключен непосредственно к системной шине и может оперировать несколькими устройствами, в зависимости от загруженной в него канальной программы. Канатьные процессоры долгое время считались отличительной особенностью больших ЭВМ. В мини-и микрокомпьютерах использование специализированных канальных процессоров, более сложных, чем контроллер ПДП, считалось неприемлемым по стоимостным показателям. Удивительно, что даже современное радикальное удешевление оборудования не изменило положения: предложение консорциума I2O (Intelligent Input/Output) снабжать компьютеры на основе процессоров х86 канальным процессором Intel 960, с энтузиазмом поддержанное практически всеми поставщиками операционных систем, почему-то не было столь же горячо поддержано потребителями.
Потребители мини- и микросистем, нуждающиеся в высокой производительности, предпочитают использовать в качестве дополнительных процессоров устройства с той же архитектурой, что и центральный процессор. Это называется симметричной многопроцессорностью (SMP), и позволяет перераспределять между процессорами не только обработку событий, но и собственно вычислительную деятельность. Понятно, что обрабатывать все события по принципу опроса в такой архитектуре — бессмысленная, а зачастую и нетерпимая расточительность.
К счастью, еще с 60-х годов, практически все процессоры как центральные, так и канальные, используют стратегию работы с событиями, во многих отношениях гораздо более совершенную, чем опрос.
Алгоритм работы команд in и out
Рисунок 7.9. Алгоритм работы команд in и out
Аналогично обрабатываются запросы на чтение. Если мы имеем более двух процессов, пытающихся использовать один линк, то возникает серьезная проблема: внимательный читатель должен был заметить, что мы не сказали, где хранится информация о том, чего ожидает текущий процесс: чтения или записи. Проблема состоит в том, что эта информация нигде не хранится. Если процесс попытается записать данные в линк, на котором кто-то уже ожидает записи, то данные второго процесса будут записаны поверх данных ожидавшего. Если размеры буферов совпадут, то ожидавший процесс будет пребывать в убеждении, что он успешно передал все данные. Поэтому линки рекомендуется использовать только для однонаправленной передачи данных между двумя (не более!) процессами.
При работе с физическим линком данные не копируются, а передаются или принимаются через физический канал в режиме прямого доступа к памяти. Если на другом конце линка находится другой транспьютер, это все-таки можно считать копированием, но к линку может быть подключено и какое-то другое устройство.
В середине 90-х, в эпоху расцвета микропроцессоров этого семейства, фирма Inmos поставляла широкий набор трэмов (trem — TRansputer Extension module) — устройств ввода-вывода с линком в качестве интерфейса. В частности, поставлялись трэмы, позволявшие подключить к транспьютеру через линк адаптеры Ethernet или SCSI.
Взаимодействие с внешним устройством через линк позволяет транспьютеру синхронизовать свою деятельность с этими устройствами без использования механизма прерываний. В [INMOS 72 TRN 203 02] приводится пример программной имитации векторных прерываний с передачей вектора по линку
и мониторным процессом, который принимает эти векторы из линка и вызывает соответствующие обработчики.
Блокировка участков файла в Unix
Блокировка участков файла в Unix
Захват участков файла в качестве средства синхронизации был известен еще с 60-х годов, но в том виде, который описан в стандартах ANSI и POSIX, он был реализован в ОС UNIX в начале 70-х.
В UNIX возможны два режима захвата: допустимая (advisory) и обязательная (mandatory). Как та, так и другая блокировка может быть блокировкой чтения либо записи. Допустимая блокировка является "блокировкой для честных": она не оказывает влияния на подсистему ввода-вывода, поэтому программа, не проверяющая блокировок или игнорирующая их, сможет писать или читать из заблокированного участка без проблем. Обязательная блокировка требует больших накладных расходов, но запрещает физический доступ к файлу: чтение или запись, в зависимости от типа блокировки.
При работе с разделяемыми структурами данных в ОЗУ было бы удобно иметь аналогичные средства, но их реализация ведет к большим накладным расходам, даже на системах с виртуальной памятью, поэтому ни одна из известных автору систем таких средств не имеет. Библиотека POSIX threads предоставляет своеобразную форму мутекса, read/write lock, который, как и описанные файловые примитивы, может быть многократно захвачен для чтения и лишь однократно — для записи. Однако мы должны заводить такой примитив для каждой единицы разделяемого ресурса и не можем одним вызовом захватить сразу много подобных единиц.
Впрочем, в современных версиях системы UNIX есть возможность отображать файл в виртуальную память. Используя при этом допустимую блокировку участков файла, программы могут синхронизироовать доступ к нему (обязательная блокировка делает невозможным отображение в память).
Флаги событий в RSX11 и VMS
Флаги событий в RSX-11 и VMS
Так, например, в системах RSX-11 и VMS основным средством синхронизации являются флаги событий (event flags). Процессы и система могут очищать (clear) или взводить (set) эти флаги. Флаги делятся на локальные и глобальные. Локальные флаги используются для взаимодействия между процессом и ядром системы, глобальные — между процессами. Процесс может остановиться, ожидая установки определенного флага, поэтому флаги во многих ситуациях можно использовать вместо двоичных семафоров. Кроме того, процесс может связать с флагом события процедуру-обработчик AST (Asynchronous System Trap — асинхронно [вызываемый] системный обработчик).
AST во многом напоминают сигналы или аппаратные прерывания. В частности, флаги событий используются для синхронизации пользовательской программы с асинхронным исполнением запросов на ввод-вывод. Исполняя запрос, программа задает локальный флаг события. Затем она может остановиться, ожидая этого флага, который будет взведен после исполнения запроса. При этом мы получаем псевдосинхронный ввод-вывод, напоминающий синхронные операции чтения/записи в UNIX и MS DOS. Но программа может и не останавливаться! При этом запрос будет исполняться параллельно с исполнением самой программы, и она будет оповещена о завершении операции соответствующей процедурой AST.
Асинхронный ввод-вывод часто жизненно необходим в программах реального времени, но бывает полезен и в других случаях.
Формулировка задачи
Формулировка задачи
| Я что-то не вижу пивного ларька. Должно быть, его Успели снести за ночь. Б. Гребенщиков |
Чтобы понять, какие же методики применимы для взаимодействия параллельно исполняющихся нитей, давайте более четко сформулируем задачу. Для этого нам также надо ввести некоторое количество терминов. Кроме того, нам придется высказать ряд соображений, часть которых может показаться читателю банальностями.
Установим, что для каждой из нитей создается иллюзия строго последовательного исполнения (например, обработчик прерывания может создать для основного потока программы такую иллюзию, аккуратно сохраняя при вызове и восстанавливая при завершении все регистры процессора). Если для какой-то из нитей это условие не всегда соблюдается, мы будем считать ее двумя или большим числом различных нитей. Если это условие не соблюдается никогда, мы имеем дело с процессором нефон-неймановской архитектуры.
Общепринятое название для взаимодействия между различными нитями — асинхронное взаимодействие, в противоположность синхронному взаимодействию между различными модулями последовательно исполняемой программы.
Если нить работает только с объектами (под объектом мы, в данном случае, понимаем не только группу переменных в оперативной памяти или объект в смысле ООП, но и физические объекты, например управляемые компьютером внешние устройства), состояние которых не может быть изменено другими нитями, проблемы взаимодействия, да и самого взаимодействия, как такового, не существует.
Если нить работает с объектами, состояние которых вообще не подвергается модификации, например, с кодом или таблицами констант, проблемы также нет. Проблема возникает тогда и только тогда, когда модификации подвергается объект, разделяемый несколькими нитями. При этом для возникновения проблемы достаточно, чтобы только одна нить занималась модификацией, а остальные нити считывали состояние объекта.
Интервал, в течение которого модификация нарушает целостность разделяемой структуры данных, и, наоборот, интервал, в течение которого алгоритм нити полагается на целостность этой структуры, называется критической секцией. Задача написания корректной многопоточной программы, таким образом, может решаться двумя способами: либо искоренением критических секций из всех используемых алгоритмов, либо обеспечением гарантии того, что никакие две нити никогда одновременно не войдут в критическую секцию, связанную с одним и тем же разделяемым объектом. Наличие в программе критической секции с негарантированным исключением и есть ошибка соревнования, которая рано или поздно сработает.
Полное искоренение критических секций из кода требует глубокой переработки всех алгоритмов, которые используются для работы с разделяемыми данными. Результат такой переработки мы видели в примере 5.2: странная, на первый взгляд, двойная загрузка регистра в настроенной записи PLT в этом примере обусловлена именно желанием избежать проблем при параллельной настройке одной и той же записи двумя разными нитями (в качестве упражнения читателю предлагается разобраться, в каком порядке интерпретатор модифицирует запись, и как выглядит промежуточный код). У автора нет примеров, демонстрирующих невозможность такой переработки в обшем случае, но очевидно, что даже к крайне простым алгоритмам она совершенно не применима на практике.
Второй путь — предоставление гарантий взаимоисключения (mutual exclusion) — также непрост, но, в отличие от первого, практически реализуем и широко применяется.
Примечание
Примечание
Важно подчеркнуть, что сокращение времени, которое каждая из нитей проводит в критических секциях, хотя и полезно, со многих точек зрения, в частности с точки зрения улучшения масштабируемости алгоритма, само по себе оно проблемы решить не может. Без гарантии взаимоисключения, сокращение критического времени лишь понижает вероятность срабатывания ошибки соревнования (и, в частности, затрудняет поиск такой ошибки при тестировании), но не исправляет эту ошибку.
Группа операций модификации разделяемой структуры данных, которая происходит атомарно (неделимо), не прерываясь никакими другими операциями с той же структурой данных, называется транзакцией. В разд. Мониторы и серверы транзакций мы увидим более радикальное определение термина "транзакция" как группы операций, которые всегда либо происходят все вместе, либо не происходят вообще, даже если во время попытки их выполнения случится общесистемный сбой. Понятно, что для реализации так понимаемых транзакций одного только взаимоисключения недостаточно.
Программный модуль, внутри которого имеется хотя бы одна критическая секция, для которой не обеспечено взаимное исключение, называется нереентерабельным. Вызов процедур такого модуля из различных нитей приведет к ошибкам соревнования и допустим лишь при условии, что вызывающая программа реализует взаимное исключение самостоятельно. Соответственно, модуль, в котором таких секций нет, или который сам обеспечивает взаимное исключение для них, называется реентерабельным (от англ, re-enterable — способный к повторному вхождению) или реентрантным (reentrant). В современной англоязычной литературе часто также употребляются термины thread-unsafe (для обозначения нереентерабельных процедур) и thread-safe (соответственно, для реентерабельных).
Рассмотрим простейший случай разделяемого объекта: флаговую переменную, которая может принимать значения True и False. Такая переменная, в частности, может использоваться для реализации взаимного исключения в секции, работающей с более сложной структурой данных.
Если в критической секции не находится ни одной нити, переменная равна False, иначе — True. При входе в секцию нам необходимо проверить значение переменной и, если блокируемый участок свободен, присвоить ей True. Данный пример любопытен не только своей простотой, но и тем, что совмещает в себе оба типа критических секций: изменение разделяемых данных и анализ данных, которые могут параллельно модифицироваться кем-то еще.
Наивный способ работы с такой переменной приведен в примере 7.1 (пример реализован на паскалеподобном псевдокоде. Операторы parbegin/parend символизируют параллельное исполнение заключенных между ними операторов). Казалось бы, трудно представить себе более простую программу, однако именно благодаря простоте легко понять, что она никуда не годится: проверка флага и его установка реализуются двумя различными операторами, в промежутке между которыми другой процесс может получить управление и также установить флаговую переменную! Окно, в котором происходит соревнование, составляет всего две-три команды, но при попадании обоих процессов в это окно мы получаем как раз то, чего стремились избежать: оба процесса могут войти в критическую секцию одновременно.
Гармонически взаимодействующие последовательные потоки
Гармонически взаимодействующие последовательные потоки
В разд. Формулировка задачи мы видели, что проблемы взаимоисключения и синхронизации возникают тогда и только тогда, когда несколько нитей разделяют один и тот же ресурс. Взаимоисключение доступа к разделяемым данным приводит к необходимости вводить дополнительные сущности (семафоры и другие примитивы взаимоисключения и синхронизации) и усложнять программу.
Необоснованное расширение участков исключительного доступа приводит к росту времени реакции системы и снижению производительности, а стремление сократить их может привести к ошибкам соревнования. Поэтому разделяемые структуры данных являются предметом ненависти теоретиков и источником серьезных ошибок при разработке программ.
Желание устранить эти проблемы привело в свое время Э. Дейкстру к концепции, известной как гармонически взаимодействующие последовательные потоки. Эта концепция состоит в следующем.
Третье требование является ключевым. Поток, модифицирующий (в данном случае генерирующий) данные, исполняет примитив передачи данных тогда и только тогда, когда порожденные им данные уже целостны, или передает их такими блоками, каждый из которых целостен сам по себе.
Примечание
Примечание
Важно подчеркнуть, что гармоническое взаимодействие не исключает критических секций из алгоритма. Оно лишь сосредотачивает критические секции и связанные с ними примитивы взаимоисключения внутри примитивов передачи данных.
Гармоническое взаимодействие, строго говоря, не исключает проблему мертвой блокировки: замкнув гармонически взаимодействующие нити в кольцо (А получает информацию от В, В от С, С от А), мы можем получить классическую трехзвенную мертвую блокировку. Впрочем, в данном случае блокировка требует наличия циклической зависимости данных, которая свидетельствует о серьезных ошибках проектирования программы (и, возможно, о внутренней противоречивости требований к этой программе). Такая ошибка может быть относительно легко обнаружена посредством формального анализа спецификаций и потоков данных.
На практике, впрочем, гармоническое взаимодействие обходит основную массу проблем, возникающих при взаимоисключении доступа ко многим ресурсам — и блокировки, и "проблему голодного философа". Дело в том, что гармонически взаимодействующий поток имеет дело не с разделяемым ресурсом непосредственно, а с копией состояния этого ресурса. Если нам нужны два ресурса, мы (не обязательно одновременно) снимаем с них две копии — для этого нам не надо одновременно захватывать сами ресурсы.
В частности, поэтому групповые операции над примитивами гармонического взаимодействия (оператор select в Ada, системный вызов select в системах семейства Unix, команда alt в транспьютере) работают не по принципу транзакции, а возвращают управление и данные при условии, что хотя бы один из примитивов группы готов эти данные предоставить. Воспроизвести "проблему голодного философа" в этих условиях невозможно.
В современных системах реализован целый ряд средств, которые осуществляют передачу данных совместно с синхронизацией: почтовые ящики (mailboxes) в системах линии RSX-11 — VMS, трубы (pipes) (в русскоязычной литературе их часто называют программными каналами) в UNIX, рандеву (rendesvous — свидание) в языке Ada, линки (link — соединение) в микропроцессорах семейства Transputer и т. д. Большинство этих средств будет обсуждаться подробнее в разд. Примеры реализаций средств гармонического взаимодействия.
Примитивы синхронного обмена данными отличаются большим разнообразием. Основные принципы классификации таковы.
Синхронные примитивы могут использоваться не "только для гармонического взаимодействия, но и для реализации примитивов чистой синхронизации. В частности, в учебниках по языку Ada (например, [Василеску 1990]) и по программированию для транспьютеров (например, [Харп 1993]) почему-то любят приводить примеры реализации семафоров на основе, соответственно, рандеву и линков.
Буферизованные примитивы для синхронизации использованы быть не могут. Зато буферизация полезна, если нам надо согласовать скорости работы нитей, имеющих разные приоритеты — например, если нить реального времени должна быстро обработать событие и передать часть данных для отложенной обработки менее приоритетной нитью, не допустив при этом собственной блокировки.
Буферизованный примитив может быть легко реализован на основе пары синхронных примитивов и нити-монитора буфера (или очереди). В этом смысле, синхронные примитивы являются более низкоуровневыми, чем буферизованные.
Синхронные примитивы по природе своей всегда двухточечные. Да и в случае буферизованных примитивов многоточечное взаимодействие не всегда легко реализуемо, а иногда просто опасно, особенно в случае потоковой передачи данных: операция считывания данных из потока необратима, а естественного разбиения потока на сообщения нет, поэтому если один из приемников по ошибке захватит кусок сообщения, предназначенного не ему, то данные в потоке будут необратимо испорчены.
Впрочем, некоторые потоковые примитивы, например трубы (pipes) в системах семейства Unix, допускают (хотя документация и рекомендует пользо-яться этим с осторожностью) наличие нескольких передатчиков при одном приемнике.
Напротив, симметрично многоточечные очереди сообщений широко распространены. Часто такие примитивы позволяют потребителю отбирать сообщения из очереди по какому-то критерию, например по значению специального поля, называемому типом или тегом. Ряд широковещательных и групповых сервисов передачи данных относится к категории примитивов с негарантированной доставкой.
Второй и третий критерии нашей классификации (если пока отвлечься от сервисов с негарантированной доставкой) практически ортогональны друг другу: существуют все четыре варианта (табл. 7.1). Легко понять, что передавать поток неструктурированных данных в режиме негарантированной доставки бессмысленно: разрывы потока неизбежны, а мы не сможем даже узнать, произошел ли такой разрыв, и если произошел, то где. Все существующие сервисы с негарантированной доставкой передают только сообщения.
Голодный философ
Рисунок 7.5. Голодный философ
Линки транспьютера
Линки транспьютера
В микропроцессорах семейства Transputer микропрограммно реализованы линки (link — связь) — синхронный примитив, отчасти похожий на трубы.
Линки бывают двух типов — физические и логические. Операции над линками обоих типов осуществляются одними и теми же командами. Физический линк представляет собой последовательный интерфейс RS432, реализованный на кристалле процессора. С линком также ассоциировано одно слово памяти, смысл которого будет объяснен далее.
Современные транспьютеры имеют четыре физических линка. Физические линки могут передавать данные со скоростью до 20 Мбит/с и могут использоваться как для соединения транспьютеров между собой (Рисунок 7.7), так и для подключения внешних устройств. Благодаря этому физический линк может использоваться как для связи между процессами на разных транспьютерах, так и для синхронизации процесса с внешними событиями и даже просто для ввода-вывода.
Мертвая блокировка
Рисунок 7.1. Мертвая блокировка
Все остальные нити, пытающиеся получить доступ к стриммеру или кассете, также будут становиться в соответствующие очереди и ждать, пока администратор не снимет одну из "защелкнувшихся" задач.
Цикл взаимного ожидания может состоять и из большего количества нитей Возможна также мертвая блокировка с участием только одной нити и одного ресурса: для этого достаточно попытаться захватить одну и ту же флаговую переменную два раза. Критерием блокировки является образование замкнутого цикла в графе ожидающих друг друга задач.
Эта проблема может быть решена несколькими способами. Часто применяемое решение, обладающее, впрочем, серьезными недостатками — это отправка сообщения программе о том, что попытка установить примитив взаимоисключения приведет к мертвой блокировке. Это решение опасно во-первых, тем, что сильно усложняет кодирование: теперь мы вынуждены принимать во внимание не только возможность захвата примитива другой нитью, но и более сложные ситуации. Во-вторых, получив ошибку установки флага, программист испытывает сильный соблазн сделать именно то, чего делать в данном случае нельзя: повторить попытку захвата ресурса.
Рассмотрим ситуацию, когда две нити пытаются захватить необходимые им ресурсы, получают сообщение о возможности мертвой блокировки, и тут же повторяют попытку захвата того же ресурса. Поскольку освобождения ресурсов не происходит, взаимозависимость между этими нитями не устраняется, и повторный захват также приводит к сообщению о возможности мертвой блокировки. Если нити будут циклически повторять попытки захвата, мы получим состояние, которое называется живой блокировкой (livelock) (Рисунок 7.2). Это состояние реже рассматривается в учебниках, но теоретически оно ничуть не лучше мертвой блокировки. Практически же оно гораздо хуже — если нити, зацепившиеся намертво, тихо висят и причиняют вред только тем нитям, которым могли бы понадобиться занятые ими ресурсы, то нити, зацепившиеся заживо, непродуктивно расходуют время центрального процессора.
Мертвая блокировка в исполнении пяти философов
Рисунок 7.4. Мертвая блокировка в исполнении пяти философов
Цикл можно разомкнуть, пронумеровав вилки и потребовав, чтобы каждый философ брат сначала вилку с меньшим номером, и только потом — с большим. Если вилки пронумерованы по часовой стрелке, для всех философов, кроме одного, это требование совпадает с высказанным в предыдущем абзаце — сначала брать правую вилку, и лишь потом дожидаться левой. Однако для того, кто попал между пятой и первой вилками, это правило обращается — он должен сначала дождаться левой вилки, и только потом правую. Легко продемонстрировать, что этот философ в среднем будет своих вилок дольше, чем остальные четверо.
Если же философ берет вилки тогда и только тогда, когда они доступны обе одновременно, это может привести к проблеме голодного философа-согласовав свои действия, соседи бедняги могут неограниченно долгое время оставлять его голодным (Рисунок 7.5).
Мертвые и живые блокировки
Мертвые и живые блокировки
| Потом ударили морозы. Замерзло все, лиса ушла в кредит. Медведь же вмерз в дупло И до сих пор глядит. Б. Гребенщиков. |
Решив проблему взаимоисключения для одиночных разделяемых ресурсов, мы еще не можем расслабляться. Дело в том, что если мы используем любые механизмы взаимоисключения для доступа к нескольким различным ресурсам, может возникнуть специфическая проблема, называемая мертвой блокировкой (dead lock).
Рассмотрим две нити, каждая из которых работает с двумя различными ресурсами одновременно. Например, одна нить копирует данные со стриммера на кассету Exabyte, а другая — в обратном направлении. Доступ к стриммеру контролируется флаговой переменной flag1, а к кассете — flag2 (вместо флаговых переменных могут использоваться и более сложные средства взаимоисключения).
Первая нить сначала устанавливает flag1, затем fiag2, вторая поступает наоборот. Поэтому, если вторая нить получит управление и защелкнет flag2 в промежутке между соответствующими операциями первой нити, то мы получим мертвую блокировку (Рисунок 7.1) — первая нить никогда не освободит flag1, потому что стоит в очереди у переменной flag2, занятой второй нитью, которая стоит в очереди у flagi, занятой первой.
Мониторы и серверы транзакций
Мониторы и серверы транзакций
Захват участков файла теоретически позволяет реализовать любую требуемую структуру взаимоисключения для процессов, работающих с этим файлом. Однако, практически, при работе с файлом большого количества нитей (например, многопользовательской системы управления базами данных), различные нити часто оказываются вынуждены ждать друг друга, что приводит к резкому увеличению времени реакции системы. С этим явлением хорошо знакомы разработчики и пользователи файловых СУБД, таких, как FoxPro или dBase IV.
В случае СУБД решение состоит в создании сервера БД, или сервера транзакций, который вместо примитивов захвата участков файлов или таблиц предоставляет пользователям понятие транзакции.
Если пользовательская сессия объявила начало транзакции, изменения, которые она вносит в таблицы, непосредственно в таблицах не отражаются, и другие сессии, которые обращаются к вовлеченным в транзакцию данным, получают их исходные значения. Завершив модификацию, пользовательская сессия объявляет завершение транзакции. Транзакция может завершиться как выполнением (commit), так и откатом (rollback).
В случае отката измененные данные просто игнорируются. В случае же выполнения сервер вносит изменения в таблицы, однако во время изменений он все равно предоставляет другим нитям данные в том состоянии, в котором они были до начала транзакции. Такой подход увеличивает потребности в оперативной и дисковой памяти (все данные, изменяемые в ходе транзакции, должны храниться минимум дважды: в измененном и в исходном видах), но обеспечивает резкое сокращение времени реакции и определенное упрощение кодирования: программист теперь не должен явно перечислять все данные, которые ему надо заблокировать в ходе транзакции. Кроме того, Двойное хранение данных позволяет восстановить либо результат транзакции, либо состояние данных до ее начала, после сбоя системы.
Современные серверы СУБД представляют собой сложные программные Комплексы, которые, кроме собственно "развязки" транзакций предоставляют сложные сервисы оптимизации запросов, индексации и кэширования Данных. Да и точное описание понятия транзакции в современных языках запросов к реляционным СУБД (SQL, RPG и др.) несколько сложнее при-Веденного выше. Однако детальное обсуждение этого вопроса увело бы нас Далеко в сторону от темы книги. Читателю, интересующемуся этой темой, Можно порекомендовать книги [Дейт 1999, Бобровски 1998].
Аналогичный серверам транзакций подход нередко используется и в более простых случаях межпроцессного взаимодействия. С разделяемым ресурсом ассоциируется специальная нить, называемая монитором ресурса. Остальны нити не могут обращаться к ресурсу напрямую и взаимодействуют только с монитором. Монитор может предоставлять нитям-клиентам непротиворечивые состояния контролируемого им ресурса (необязательно совпадающие с текущим состоянием ресурса) и устанавливать очередность запросов на модификацию.
Даже при довольно простой стратегии управления ресурсом, монитор полезен тем, что скрывает (инкапсулирует) структуру и особенности реализации разделяемого ресурса от клиентских нитей. Типичный пример мониторного процесса — драйвер внешнего устройства в многозадачных ОС.
Обедающие философы
Рисунок 7.3. Обедающие философы
Возможны несколько вариантов разрешения происходящих при этом коллизий. Если, например, каждый из философов всегда берет ту вилку, которая свободна, и не отпускает ее, пока не насытится, мы можем получить (хотя и не обязательно получим) классическую мертвую блокировку, в которую будут включены все философы, сидящие вокруг стола (Рисунок 7.4). Вариант, при котором философ сначала всегда дожидается правой вилки, и лишь взяв ее, начинает дожидаться левой, только повысит вероятность образования цикла.
Передача данных через линк
Рисунок 7.8. Передача данных через линк
Аналогично, при приеме данных из линка, процесс должен исполнить команду in. Эта команда также имеет три операнда — адрес линка, адрес буфера, куда необходимо поместить данные, и размер буфера. При исполнении такой команды процесс блокируется до тех пор, пока буфер не будет заполнен данными. При этом приемник и передатчик могут использовать буферы разного размера, т. е. приемник может считывать большой массив данных в несколько приемов и т. д.
Существует также команда alt, позволяющая процессу ожидать данные из нескольких линков одновременно. В качестве одного из ожидаемых событий можно также использовать сигнал от системного таймера. Слово, связанное с линком, содержит указатель на дескриптор процесса, ожидающего приема или передачи данных через линк. Кроме того, это слово может принимать значение NotProcessP, указывающее, что соединения никто не ждет. Остальная информация, такая, как указатель на буфер и размер буфера, хранится в дескрипторе процесса.
Направление передачи данных определяется командой, которую исполнит очередной процесс при обращении к линку. Например, если исполняется команда out, предназначенные для записи данные копируются в буфер ожидающего процесса. При этом указатель буфера продвигается, а счетчик размера уменьшается на количество скопированных данных. Если же в линке записано значение NotProcessP, процесс переводится в состояние ожидания и указатель на его дескриптор помещается в линк (Рисунок 7.9).
Почтовые ящики VMS
Почтовые ящики VMS
Система VMS предоставляет средства, отчасти аналогичные трубам, называемые почтовые ящики (mailbox). Почтовый ящик также представляет собой кольцевой буфер, доступ к которому осуществляется теми же системными вызовами, что и работа с внешним устройством. Системная библиотека языка VAX С использует почтовые ящики для реализации труб, в основном совместимые с UNIX и стандартом POSIX. Широко используемый сервис сетевой передачи данных, сокеты протокола TCP, также очень похожи на трубу.
Наивная реализация
Пример 7.1. Наивная реализация взаимного исключения на основе флаговой переменной
program флаг;
var flag: Boolean;
procedure процессодин;
begin
while True do begin
while flag do;
flag := True;
критическаясекция!;
flag := False;
...
end
end;
procedure процессдва; begin
while True do begin
while flag do;
flag := True;
критическаясекция2;
flag := False;
end
end;
oegin
flag:= False;
parbegin
процессодин;
процессдва;
parend
еnd.
Алгоритм Деккера (цит
Пример 7.2. Алгоритм Деккера (цит. по [Дейтел 1987])
program АлгоритмДеккера;
var
избранныйпроцесс: (первый, второй); п!хочетвойти, п2хочетвойти: Boolean; procedure процессодин;
begin
while true do begin
п1хочетвойти := True;
while п2хочетвойти do
if избранныйпроцесс=второй then
begin
п1хочетвойти := False;
while избранныйпроцесс=второй do;
п!хочетвойти := True;
end
критическийучасток1;
избранныйпроцесс := второй;
п!хочетвойти := False;
...
end
end
procedure процессдва;
begin
while true do
begin
п2хочетвойти := True;
while п1хочетвойти do
if избранныйпроцесс=первый then
begin
п2хочетвойти := False;
while избранныйпроцесс=первый do;
п2хочетвойти := True;
end
критическийучасток2 ;
избранныйпроцесс := первый;
п2хочетвойти := False;
...
end
end D
begin
п1хочетвойти := False;
п2хочетвойти := False;
избранныйпроцесс := первый;
parbegin процессодин;
процессдва;
parend
end.
Недостатки этого решения очевидны. Первый из них — для доступа к одной и той же критической секции из третьей нити мы должны значительно сложнить код обеих нитей.
Нa практике, для решения проблемы работы с флаговыми и другими ска-ярными переменными в многопроцессорных конфигурациях большинство овременных процессоров предоставляют аппаратные примитивы взаимоисключения: средства, позволяющие процессору монопольно захватить шину : выполнить несколько операций над памятью. Реализации этих примитивов различны у разных процессоров. Например, у х86 это специальный код операции, префикс захвата шины, который сам по себе не совершает никаких действий, но зато исполняет следующую за ним операцию в монопольном режиме.
Благодаря этому мы можем одновременно получить старое значение флаговой переменной и установить новое командой xchg (eXCHanGe, обменять — операнды обмениваются значениями между собой — пример 7.3)- Если память модифицируется только одним процессором, исполняющим программу, префикс блокировки шины не нужен — зато, если процессоров (или других задатчиков шины) в системе несколько, префикс гарантирует взаимоисключение и для модификаций флага с их стороны.
Реализация примитива
Пример 7.3. Реализация примитива testandset через блокировку шины
.globl flag
; 0 = False, I = True
flag: .db 0
proc process1
tryagain:
move eax, 1
lock xchg eax, flag
tst eax
bnz tryagain
критическая секция
; в данном случае о взаимоисключении можно не заботиться
xor eax, eax
move flag, eax
ret
endp
Другие процессоры, например VAX, предоставляют отдельные команды, исполняющиеся в режиме монопольного захвата шины. В частности, Именно так этот процессор исполняет команды вставки в очередь и исключения из нее.
Имея возможность произвести атомарно исполняющуюся операцию над скалярной переменной, мы можем реализовать более сложные схемы взаимоисключения, используя эту переменную в качестве флаговой, при помощи относительно простого кода (пример 7.4). В отличие от алгоритма Деккера этот код легко распространяется на случай более чем двух нитей.
Реализация взаимоисключения
Пример 7.4. Реализация взаимоисключения при помощи атомарной операции testandset (ЦИТ. ПО [Дейтел 1987])
progam npimeptestandset
var активный: Boolean;
procedure процессодин;
var первомувходитьнельзя: Boolean;
begin
while true do
begin
первомувходитьнельзя := True;
while первомувходитьнельзя do
testandset(первомувходитьнельзя, активный);
критический участокодин;
активный := False;
....
end
end;
procedure процессдва;
var второмувходитьнельзя: Boolean; begin
while true do
begin
второмувходитьнельзя := True;
while второмувходитьнельзя do
testandset(второмувходитьнельзя, активный);
критический участокдва;
активный := False;
.....
end
end;
В том случае, если одной из нитей является обработчик прерывания, можно воспользоваться сервисом, который предоставляют все современные процессоры: запретить прерывания на время нахождения основной нити программы в критической секции. Впрочем, указанным способом необходимо пользоваться с осторожностью — это приводит к увеличению времени обработки прерывания, что не всегда допустимо, особенно в задачах реального времени.
Ошибка потерянного пробуждения (lost wakeup bug)
Пример 7.5. Ошибка потерянного пробуждения (lost wake-up bug)
program пауза
var flag: Boolean;
procedure процесс1
var myflag: Boolean
while True do
begin
myflag := True;
testandset(myflag, flag);
if myflag then
(* Обратите внимание, что проверка флага *
* и засыпание — это разные операторы! *)
pause;
критическаясекция();
flag := False;
end
end;
Одно из решений состоит в усложнении примитива pause: он должен засыпать, если и только если сигнал еще не приходил. Усложнение получается значительное: мало того, что перед засыпанием надо проверять нетривиальное условие, необходимо еще предусмотреть какой-то способ сброса этого условия, если мы предполагаем многократное использование нашего примитива.
Если писать на ассемблере или родственных ему языках, можно пойти и более изощренным путем (пример 7.6). Подмена адреса возврата в обработчике прерывания гарантирует нам, что если прерывание по установке флага произойдет в промежутке между метками label и ok, мы перейдем на метку label и, вместо того, чтобы заснуть навеки, благополучно проверим флаг и войдем в критическую секцию.
Обход ошибки потерянного пробуждения globl flag
Пример 7.6. Обход ошибки потерянного пробуждения
.globl flag
flag: db 0
jmpbuf: dw 0
proc flag_interrupt
push eax
tst jmpbuf
bz setflagonly
; подменяем адрес возврата
move eax, jmpbuf
move sp[RETURN_ADDRESS_OFFSET] , eax setflagonly
move eax, 1
move flag, eax
pop eax
iret endp
proc process!
inove eax, setjmp
move jmpbuf, eax setjmp:
move eax, 1
lock xchg eax, flag
tst eax
bz ok
halt
ok
xor eax, eax move jmpbuf, eax
критическая секция
xor eax, eax move flag, eax
endp
Более элегантный и приемлемый для языков высокого уровня путь решения этой проблемы состоит в том, чтобы объединить в атомарную операцию проверку флага и засыпание. Нас с читателем можно поздравить с изобретением двоичного семафора Дейкстры.
Код создающий конвейер
Пример 7.7. Код, создающий конвейер при помощи труб
#include <unistd.h>
void pipeline(void) {
/* stage 1 */
int pipel[2];
int childl;
int pipe2[2];
int child2;
int child3;
pipe(pipel);
if ((childl=fork())==0) {
close(pipel[0]); /* Закрыть лишний конец трубы */
closed); /* Переназначить стандартный вывод */
dup(pipel[1]);
close(pipel[1]);
/* Исполнить программу */
execlpC'du", "du", "-s", ".", NULL);
/* Мы можем попасть сюда только при ошибке exec */
perror("Cannot exec");
exit(0);
}
close(pipel [1] ) ;
if (childl==-l) {
perror("Cannot fork");
}
/* stage 2 */
pipe(pipe2);
if ( (child2=fork() )==0) { '. close (0) ; /J" Переназначить стандартный ввод */
dup(pipel[0]} ; close (pipel [0] ) ;
•'close (pipe2 [0] ) ; /* Закрыть лишний конец трубы */ close (1) ; /* Переназначить стандартный вывод */
close (pipe2 [1] ) ;
/* Исполнить программу */
execlp ("sort", "sort", "-nr", NULL);
/* Мы можем попасть сюда только при ошибке exec */
perror ("Cannot exec");
exit(O) ;
}
close (pipel [0] ) ;
close (pipe2 [1] ) ;
if (child2==-l) {
perror ("Cannot fork");
}
/* stage 3 */
if ( (child3=fork() )==0) {
close (0) ; /* Переназначить стандартный ввод */
dup(pipe2 [0] ) ;
close (pipe2 [0] ) ;
/* Исполнить программу */
execlp ("tail", "tail", "-1", NULL) ;
/* Мы можем попасть сюда только при ошибке exec */
perror ("Cannot exec");
exit (0) ;
}
close (pipe2 [0] ) ;
if (child3==-l) {
perror ("Cannot fork");
}
while (wait (NULL) !=-!) ;
return ;
}
Понятно, что такие трубы можно использовать только для связи родственны задач, т. е. таких, которые связаны отношением родитель-потомок или являются потомками одного процесса.
Для связи между неродственными задачами используется другое средство. именованные трубы (named pipes) в System V и UNIX domain sockets в BSD UNIX. В разных системах именованные трубы создаются различными систем ными вызовами, но очень похожи по свойствам, поэтому стандарт POSIX пред лагает для создания именованных труб библиотечную функцию mkfifc {c--ls. char * name, mode_t flags);. Эта функция создает специальный файл" Открывая такой файл, программа получает доступ к одному из концов трубы Когда две программы откроют именованную трубу, они смогут использовать ее для обмена данными точно так же, как и обычную.
Современные системы семейства Unix предоставляют возможность для одновременной работы с несколькими трубами (а также с другими объектами, описываемыми дескриптором файла — собственно файлами, сокетами и т. д.)_, системный вызов select. Этот вызов возвращает список дескрипторов файлов, которые способны передать или принять данные. Если ни один из дескрипторов не готов к обмену данными, select блокируется.
Трубы широко используются системами семейства Unix, и они внесены в стандарт POSIX. Ряд операционных систем, не входящих в семейство Unix, например VxWorks, также предоставляют этот сервис.
Обработчик оконных
Пример 7.8. Обработчик оконных событий в OS/2 Presentation Manager
/* фрагмент примера из поставки IBM Visual Age for C++ 3.0.
* Обработчик событий меню предоставляется системой,
* а обработку командных событий, порождаемых меню,
* вынужден брать на себя разработчик приложения. */
/****************************************************************
Copyright (С) 1992 IBM Corporation
ОТКАЗ ОТ ГАРАНТИЙ. Следующий код представляет собой пример кода созданный IBM Corporation. Этот пример кода не является частью ни одного стандарта или продукта IBM и предоставляется вам с единственной целью — помочь в разработке ваших приложений. Код предоставляется "КАК ЕСТЬ", без каких-либо гарантий. IBM не несет ответственности за какие бы то ни было повреждения, возникшие в результате использования вами этого кода, даже если она и могла предполагать возможность таких повреждений.
/****************************************************************
* Имя: MainWndProc *
Описание: Оконная процедура главного окна клиента. *
* Концепции: Обрабатывает сообщения, посылаемые главному
окну клиента. Эта процедура обрабатывает основные сообщения, которые должны обрабатывать все клиентские окна, и передает все остальные [функции] UserWndProc, в которой разработчик может обработать любые другие
сообщения. *
API: He используются
* Параметры: hwnd — Идентификатор окна, которому адресовано сообщение
* msg — Тип сообщения
* mpl — Первый параметр сообщения
* тр2 — Второй параметр сообщения.
* Возвращаемое значение: определяется типом сообщения
*/
****************************************************************
MRESULT EXPENTRY MainWndProc(HWND hwnd, USHORT msg, MPARAM mpl,
MPARAM mp2)
{
switch(msg) {
case WM_CREATE:
return(InitMainWindow(hwnd, mpl, mp2)};
break;
case WM_PAINT:
«
MainPaint(hwnd); break;
case WM_COMMAND:
MainCommand(mpl,. mp2); break;
case WM_INITMENU:
Ini tMenu(mpl, mp2); break;
case HM_QUERY_KEYS_HELP:
return (MRESULT)PANEL_HELPKEYS;/* Вернуть Id панели подсказки ' break;
/*
* Все необработанные сообщения передаются
* пользовательской процедуре окна.
* Она отвечает за передачу всех необработанных
* сообщений функции WinDefWindowProc(); */
default:
return(UserWndProc(hwnd, msg, mpl, mp2)); break;
return (MRESULT)O; /* Все оконные процедуры должны по умолчанию возвращать 0 */
} /* Конец MainWndProc() */
/****************************************************************
* Имя: MainCommand
* Назначение: Главная процедура окна, обрабатывающая WM_COMMAND *
* Концепции: Процедура вызывается, когда сообщение WM_COMMAND
* отправляется главному окну. Оператор switch
* переключается в зависимости от id меню, которое
* породило сообщение и предпринимает действия,
* соответствующие этому пункту меню. Все id меню,
* не являющиеся частью стандартного набора команд,
* передаются пользовательской процедуре обработки
* WM_COMMAND.
* API : WinPostMsg *
* Параметры : mpl — Первый параметр сообщения
тр2 — Второй параметр сообщения *
* Возвращает: VOID *
\*************+**************************************************^
VOID MainCommand(MPARAM mpl, MPARAM mp2)
switch(SHORT1FROMMP(mpl))
I
case IDM_EXIT:
WinPostMsg( hwndMain, WM_QUIT, NULL, NULL break;
case IDM__FILENEW: FileNew(mp2); break;
case IDM_FILEOPEN: FileOpen(mp2); break;
case IDM_FILESAVE: FileSave(mp2); break;
case IDM_FILESAVEAS: FileSaveAs(mp2); break;
case IDM_EDITUNDO: EditUndo(mp2); break;
case IDM_EDITCUT: EditCut(mp2); break;
case IDM_EDITCOPY: EditCopy(mp2); break;
case IDM_EDITPASTE: EditPaste(mp2); break;
case IDM_EDITCLEAR: EditClear(mp2); break;
case IDM_HELPUSINGHELP: HelpUsingHelp(mp2); break;
case IDM_HELPGENERAL: HelpGeneral(mp2); break;
case IDM_HELPKEYS: HelpKeys(mp2); break;
case IDM_HELPINDEX: Helplndex(mp2); break;
case IDM_HELPPRODINFO: HelpProdInfo(mp2); break; /*
* Здесь вызывается пользовательская процедура
* обработки команд, чтобы обработать те id',
* которые еще не были обработаны. */
default:
UserCammand(mpl, mp2); break; )
} /* MainCommand() */
Специальная программа, менеджер событий (Рисунок 7.12), просматривает очередь и передает поступающие события обработчикам. События, связанные с экранными координатами, передаются обработчику, ассоциированному с соответствующим окном. Клавиатурные события передаются фокусу клавиатуры — текущему активному обработчику клавиатуры.
Управление событиями позволяет относительно легко разрабатывать динамичные пользовательские интерфейсы, привычные для пользователей современных графических оболочек.
Высокая динамичность интерфейса проще всего обеспечивается, если каждый обработчик быстро завершается. Если же в силу природы запрашиваемой операции она не может завершиться быстро — например, если мы вставили символ, параграф удлинился на строку, и в результате текстовому процессору Типа WYSIWYG приходится переформатировать и переразбивать на страни-Цы весь последующий текст — мы можем столкнуться с проблемой.
Рисунок 7.12. Менеджер и обработчики событий
В такой ситуации (а при написании реальных приложений она возникает сплошь и рядом) мы и вынуждены задуматься о том, что же в действительности представляют собою обработчики — процедуры, синхронно вызываемые единственной нитью менеджера событий, или параллельно исполняющиеся нити. Первая стратегия называется синхронной обработкой сообщений, а вторая, соответственно, — асинхронной.
Графические интерфейсы первого поколения — Mac OS, Winl6 — реализовывали синхронную обработку сообщений, а когда обработчик задумывался надолго, рисовали неотъемлемый атрибут этих систем — курсор мыши в форме песочных часов.
Несколько более совершенную архитектуру предлагает оконная подсистема OS/2, Presentation Manager. PM также реализует синхронную стратегию обработки сообщений (менеджер событий всегда ждет завершения очередного обработчика), но в системе, помимо менеджера событий, могут существовать и другие нити. Если обработка события требует длительных вычислений или других действий (например, обращения к внешним устройствам или к сети), рекомендуется создать для этого отдельную нить и продолжить обработку асинхронно. Если же приложение этого не сделает (например, обработчик события просто зациклится или заснет на семафоре), системная очередь сообщений будет заблокирована и ни одно из графических приложений не сможет работать. Современные версии РМ предоставляют в этом случае возможность отцепить "ненормальное" приложение от очереди или паже принудительно завершить его.
Асинхронные очереди сообщений предоставляют Win32 и оконная система X Window. Впрочем, и при асинхронной очереди впавший в философские размышления однопоточный обработчик событий — тоже малоприятное зрелище, ведь он не может перерисовать собственное окно, поэтому передвижение других окон по экрану порождает любопытные спецэффекты (к сожалению, запечатлеть эти эффекты при помощи утилит сохранения экрана невозможно — все известные автору средства дожидаются, пока все попавшие в сохраняемую область окна перерисуются. А фотографии монитора обычно имеют низкое качество). Разработчикам приложений для названных систем также рекомендуется выносить длительные вычисления в отдельные нити.
Большинство реальных приложений для современных ОС, имеющих пользовательский интерфейс, таким образом, имеют двух- или более слойную архитектуру. При этом архитектура ближайшего к пользователю стоя (frontend), как правило, тяготеет к событийно-управляемой, а следующие слои (backend) обычно состоят из более традиционных взаимодействующих (не всегда, впрочем, строго гармонически) параллельно исполняющихся нитей, зачастую даже разнесенных по разным вычислительным системам.
Примеры реализаций средств гармонического взаимодействия
Примеры реализаций средств гармонического взаимодействия
Примитивы синхронизации
Примитивы синхронизации
| Я слышу крик в темноте Наверное, это сигнал. В. Бутусов |
Посмотрев на примеры 7.2 и 7.4, внимательный читатель должен отметить, что используемая конструкция подозрительно похожа на работу с внешними устройствами в режиме опроса. Действительно, опрос флаговой переменном в цикле хотя и обеспечивает гарантию взаимоисключения, но обладает всеми недостатками, которые мы указывали для опроса внешнего устройства.
g случае исполнения параллельных нитей на одном процессоре, данный метод имеет еще один недостаток: пока одна из нитей занимается опросом, никакая другая нить не может исполняться, потому что процессор загружен непродуктивной работой.
Легко видеть, что в данном случае использование прерываний или какого-то их аналога проблемы не решит: в лучшем случае, "прерывание" будет вызываться не в той нити, в которой нужно, сводя задачу взаимоисключения к предыдущей, только с уже новой флаговой переменной, а в худшем — приведет к возникновению еще одной нити. Задача взаимодействия между асинхронными нитями, таким образом, сводится к требованию того, чтобы нити в какие-то моменты переставали быть асинхронными, синхронизовались.
Если у нас уже есть примитив взаимного исключения, мы можем решить задачу синхронизации, предоставив еще один примитив, который позволяет активному процессу остановиться, ожидая, пока флаговая переменная не примет "правильное" значение, и продолжить исполнение после этого. При обработке прерываний роль такого примитива может исполнять команда остановки процессора: у всех современных процессоров прерывание останавливает "исполнение" этой команды, а возврат из обработчика передает управление на следующую команду, таким образом выводя процессор из спящего состояния. В многопроцессорной конфигурации можно ввести средство, при помощи которого один процессор может вызывать прерывание другого — и тогда каждый из процессоров системы сможет ожидать другого, переходя в режим сна. При реализации же многопоточностп на одном процессоре (см. разд. Вытесняющая многозадачность) примитив засыпания (блокировки) нити должен предоставляться модулем, ответственным за переключение потоков.
Впрочем, если операции над флагом, засыпание потока и его пробуждение реализованы разными примитивами, мы рискуем получить новую проблему (пример 7.5). Она состоит в том, что если пробуждающий сигнал поступит в промежутке между операторами testandset и pause, мы его не получим. В результате операция pause приведет к засыпанию нашей нити навсегда.
Примитивы взаимоисключения
Примитивы взаимоисключения
В классической работе Г. М. Дейтела [Дейтел 1987] предлагается несколько последовательных усовершенствований механизма взаимоисключений, основанного на флаговых переменных, и как завершающий этап этого анализа приводится алгоритм взаимоисключений Деккера (пример 7.2).
Программные каналы Unix
Программные каналы Unix
Одним из наиболее типичных средств такого рода является труба (pipe) или программный канал — основное средство взаимодействия между процессами в ОС семейства Unix. В русскоязычной литературе трубы иногда ошибочно называют конвейерами. В действительности, конвейер — это группа процессов, последовательно соединенных друг с другом однонаправленными трубами.
Труба представляет собой поток байтов. Поток этот имеет начало (исток) и конец (приемник). В исток этого потока можно записывать данные, а из приемника — считывать. Нить, которая пытается считать данные из пустой трубы, будет задержана, пока там что-нибудь не появится. Наоборот, пишущая нить может записать в трубу некоторое количество данных, прежде чем труба заполнится, и дальнейшая запись будет заблокирована. На практике труба реализована в виде небольшого (несколько килобайтов) кольцевого буфера. Передатчик заполняет этот буфер, пока там есть место. Приемник считывает данные, пока буфер не опустеет.
Трубу можно установить в режим чтения и записи без блокировки. При этом вызовы, которые в других условиях были бы остановлены и вынуждены были бы ожидать партнера на другом конце трубы, возвращают ошибку с особым кодом.
По-видимому, трубы являются одной из первых реализаций гармонически взаимодействующих процессов по терминологии Дейкстры.
Самым интересным свойством трубы является то, что чтение данных из и запись в нее осуществляется теми же самыми системными вызовами read и write, что и работа с обычным файлом, внешним устройством или сетевым соединением (сокетом). На этом основана техника переназначения ввода-вывода, широко используемая в командных интерпретаторах UNIX. Она состоит в том, что большинство системных утилит получают данные из потока стандартного ввода (stdin) и выдают их в поток стандартного вывода (stdout). При этом, указывая в качестве этих потоков терминальное устройство, файл или трубу, мы можем использовать в качестве ввода, соответственно: текст, набираемый с клавиатуры, содержимое файла или стандартный вывод другой программы. Аналогично мы можем выдавать данные сразу на экран, в файл или передавать их на вход другой программы.
Так, например, компилятор GNU С состоит из трех основных проходов: препроцессора, собственно компилятора, генерирующего текст на ассемблере, и ассемблера. При этом внутри компилятора, на самом деле, также выполняется несколько проходов по тексту (в описании перечислено восемнадцать), в основном для оптимизации, но нас это в данный момент не интересует, поскольку все они выполняются внутри одной задачи. При этом все три задачи объединяются трубами в единую линию обработки входного текста — конвейер (pipeline), так что промежуточные результаты компиляции не занимают места на диске.
В системе UNIX труба создается системным вызовом pipe(int flldes;2]) Этот вызов создает трубу и помещает дескрипторы файлов, соответствующие входному и выходному концам трубы, в массив fildes. Затем мы можем вы полнить fork, в различных процессах переназначить соответствующие конць трубы на место stdin и stdout и запустить требуемые программы (пример 7.7). При этом мы получим типичный конвейер — две задачи, стандартный ввод и вывод которых соединены трубой.
Семафоры
Семафоры
| Но когда ты проспишься, скрой спой испуг, Это был не призрак, эти был только звук Это тронулся поезд, на который ты не попадешь. Б. Гребенщиков |
Семафор Дейкстры представляет собой целочисленную переменную, с которой ассоциирована очередь ожидающих нитей. Пытаясь пройти через сема-Фор, нить пытается вычесть из значения переменной 1. Если значение переменной больше или равно 1, нить проходит сквозь семафор успешно (семафор открыт). Если переменная равна нулю (семафор закрыт), нить останавливается и ставится в очередь.
Закрытие семафора соответствует захвату объекта или ресурса, доступ к кото-Рому контролируется этим семафором. Если объект захвачен, остальные нити вынуждены ждать его освобождения. Закончив работу с объектом (выйдя из критической секции), нить увеличивает значение семафора на единицу, открывая его. При этом первая из стоявших в очереди нитей активизируется и вычитает из значения семафора единицу, снова закрывая семафор. Если же очередь была пуста, то ничего не происходит, просто семафор остается открытым. Тогда первая нить, подошедшая к семафору, успешно проГцет через него. Это действительно похоже на работу железнодорожного семафо. ра, контролирующего движение поездов по одноколейной ветке (Рисунок 7.6)
Семафоры и прерывания
Семафоры и прерывания
Большинство современных ОС предоставляют сервисы, позволяющие без вреда для остальной системы приостановить и возобновить исполнение пользовательской нити. Однако мало какая ОС предоставляет такой же сервис для обработчиков прерываний. Поэтому если ОС и разрешает использование примитивов синхронизации из прерываний, то всегда с условием, что такое использование не может приводить к блокировке обработчика.
Например, если для синхронизации используется мутекс, обработчик прерывания не может его устанавливать, а может только снимать. Это требование накладывает определенные ограничения на стиль использования семафоров. Если при синхронизации равноправных нитей каждая из них устанавливает семафор в начале критической секции и снимает его в конце, используя его и для взаимоисключения, и для синхронизации, то при взаимодействии нити с обработчиком прерывания для реализации взаимоисключения приходится использовать запрет прерываний, а мутекс — только для синхронизации.
Стандартная техника использования мутекса в обработчике прерывания состоит в следующем (порядок операций важен!): процесс захватывает мутекс, инициирует операцию на устройстве, которая должна завершиться прерыванием, и захватывает мутекс еще раз. Если к этому моменту прерывание уже произошло, мутекс будет свободен и процесс ничего не будет ждать. Если же прерывания еще не происходило, процесс заснет, ожидая его. Обработчик же прерывания только снимает мутекс.
Сеть транспьютеров соединенных физическими линками
Рисунок 7.7. Сеть транспьютеров, соединенных физическими линками
Логический линк— это просто структура данных, выделенная в физическом адресном пространстве процессора. С точки зрения программы, физический и логический линки ничем не отличаются, кроме того, что описатель физического линка привязан к определенному физическому адресу. Логический линк может использоваться только для связи между процессами (напоминаем, что по принятой в транспьютере терминологии, нити называются процессами), исполняющимися на одном транспьютере.
Транспьютер Т9000 предоставляет также виртуальные линки— протокол, позволяющий двум транспьютерам организовать несколько линий взаимодействия через один физический линк, или даже через цепочку маршрутизаторов.
При передаче данных в линк процесс должен исполнить команду out. Эта команда имеет три операнда: адрес линка, адрес массива данных и количество данных. Для передачи операндов используется регистровый стек процессора. Процесс, исполнивший такую команду, задерживается до тех пор, пока все данные не будут переданы (Рисунок 7.8).
Системы управляемые событиями
Системы, управляемые событиями
В начале 70-х годов появилась новая архитектура многозадачных систем довольно резко отличающаяся от вышеописанной модели последовательных процессов. Речь идет о так называемых системах, управляемых событиями (event-driven systems).
На первый взгляд, концепция систем, управляемых событиями, близко родственна гармонически взаимодействующим процессам. Во всяком случае, одно из ключевых понятий этой архитектуры, очередь событий, мы упоминали в числе средств гармонического межпоточного взаимодействия. Различие между этими архитектурами состоит, скорее, во взгляде на то, что представляет собой программа.
В модели гармонически взаимодействующих потоков процесс исполнения программного комплекса представляет собой совокупность взаимодействующих нитей управления. В системе, управляемой событиями, программа представляет собой совокупность объектов, обменивающихся сообщениями о событиях, а также реагирующих на сообщения, приходящие из внешних источников.
В идеале, объекты взаимодействуют между собой только через сообщения. Приходящие сообщения побуждают объект изменить свое состояние и, возможно, породить некоторое количество сообщений, предназначенных для других объектов. При такой модели взаимодействия нам неважно, исполняются ли методы объектов как параллельные (или псевдопараллельные) нити, или же последовательно вызываются единой нитью, менеджером или диспетчером сообщений.
Впервые эта архитектура была реализована в экспериментальных настольных компьютерах Alto, разработанных в 1973 году в исследовательском центре PARC фирмы Xerox. Целью эксперимента было создание операционной среды, удобной для создания интерактивных программ с динамичным пользовательским интерфейсом.
В этих системах впервые была реализована многооконная графика, когда пользователь одновременно видит на экране графический вывод нескольких программ и может активизировать любую из них, указав на соответствующее окно при помощи манипулятора-"мыши".
При каждом движении мыши, нажатии на ее кнопки или клавиши на клавиатуре генерируется событие. События могут также генерироваться системным таймером или пользовательскими программами. Нельзя не упомянуть "визуальные" события, которые порождаются в ситуации, когда пользователь
сдвинул или закрыл одно из окон и открыл при этом часть окна, находившегося внизу. Этому окну посылается событие, говорящее о том, что ему нужно перерисовать часть себя (Рисунок 7.10).
Примитивы синхронизованной передачи данных
Таблица 7.1. Примитивы синхронизованной передачи данных
| Примитивы | Синхронные | Буферизованные |
| Потоковые | Линки (транспьютер) | Трубы (Unix), сокеты (TCP/IP) |
| Структурированные | Рандеву (Ada) | Очереди сообщений |
На первый взгляд, вообще непонятно, почему кому-то может быть полезен сервис с негарантированной доставкой. Но под это описание подходят многие низкоуровневые сетевые протоколы (Ethernet, IP) и некоторые относительно высокоуровневые сетевые сервисы, так называемые дейтаграммные протоколы. Примером такого сервиса является UDP (User Datagram Protocol), входящий в семейство протоколов TCP/IP.
В сетевых протоколах отсутствие гарантии доставки сообщения имеет двоякий смысл — сообщение может быть потеряно не только по невниманию получателя, но и из-за физических ошибок передачи или перегрузки маршрутизаторов и/или каналов связи по дороге от передатчика к приемнику. В этом смысле можно сказать, что разработчики сетевых протоколов вынуждены использовать негарантированную доставку не потому, что им нужна Именно она, а потому, что других средств-то и нет.
В чистом виде негарантированная доставка приемлема для реализации одиночных запросов, на которые должен последовать одиночный же ответ. Если ответа за определенный протоколом интервал времени нет, передатчик повторяет запрос, а после некоторого количества попыток приходит к выводу, что приемник не функционирует, либо вообще отсутствует.
Для реализации надежной связи на основе сервисов с негарантированной доставкой используются различного рода подтверждения, так называемое квитирование. Понятно, что при реализации квитирования необходимо принимать во внимание возможность потери не только самого подтверждаемого сообщения, но и пакета-подтверждения. Понятно также, что в большинстве случаев посылка подтверждения на каждое пришедшее сообщение нецелесообразна. Поэтому реальные протоколы такого рода относительно сложны (см. например [RFC 0793]) и их обсуждение заслуживает отдельной книги. Накладные расходы при реализации таких протоколов значительны, поэтому часто оказывается целесообразно смириться с негарантированной доставкой.
Концепция гармонически взаимодействующих процессов очень привлекательна с теоретической точки зрения и позволяет легко писать правильные программы. Однако все примитивы синхронизованной передачи данных плохи именно тем, что требуют передачи, копирования данных. И передатчик, и приемник вынуждены иметь по буферу, в котором данные следует хранить (в случае буферизованных примитивов данные хранятся трижды). Накладные расходы при копировании данных большого объема также могут оказаться значительными.
Если нити исполняются на разных компьютерах, не имеющих общей памяти и соединенных лишь относительно (по сравнению с системной шиной) низкоскоростными сетевыми каналами, мы так или иначе не можем обойтись без передачи и двойного хранения данных. Впрочем, даже и в этом случае иногда имеет смысл подумать о применении многопортовой памяти или реализаций NUMA или СОМА-архитектуры.
При исполнении же нитей на одной машине, по соображениям производительности и экономии памяти нередко оказывается нецелесообразно отказываться от разделяемой памяти и полностью переходить на примитивы гармонического взаимодействия. Чаще всего это происходит, когда к ресурсу выполняется много обращений для чтения, а модификации относительно редки, и при этом данные имеют большой объем. Даже в этом случае бывает целесообразно заменить прямое разделение памяти на мониторный процесс. а при доступе к данным получать у него лишь непосредственно необходимое их подмножество. Однако ситуации бывают разные, и не всегда такое решение оказывается оптимальным.
В этом смысле разделяемая память напоминает другой предмет ненависти структурных программистов — оператор goto. И то, и другое при неразумном использовании является потенциальным источником ошибок и проблем, но иногда без них оказывается нельзя обойтись.
Визуальное событие
Рисунок 7.10. Визуальное событие
Каждое сообщение о событии представляет собой структуру данных, которая содержит код, обозначающий тип события: движение мыши, нажатие кнопки и т. д., а также поля, различные для различных типов событий. Для "мышиных" событий — это текущие координаты мыши и битовая маска, обозначающая состояние кнопок (нажата/отпущена). Для клавиатурных событий — это код нажатой клавиши, обычно, ASCII-код символа для алфавитно-цифровых и специальные коды для стрелок и других "расширенных" и "функциональных" клавиш — и битовая маска, обозначающая состояние различных модификаторов, таких как SHIFT, CNTRL, ALT и т. д. Для визуальных событий — это координаты прямоугольника, который нужно перерисовать, и т. д.
Все сообщения о событиях помещаются в очередь в порядке их возникновения.
В системе существует понятие обработчика событий. Обработчик событий Представляет собой объект, т. е. структуру данных, с которой связано несколько подпрограмм — методов. Один из методов вызывается при поступлении сообщения. Обычно он также называется обработчиком событий. Некоторые системы предлагают объектам-обработчикам предоставлять различные методы для обработки различных событий — например, метод onClick будет вызываться, когда придет событие, сигнализирующее о том что кнопка мыши была нажата и отпущена, когда курсор находился над областью, занимаемой объектом на экране.
Рассмотрим объект графического интерфейса, например меню. При нажатии на кнопку мыши в области этого меню вызывается обработчик события Он разбирается, какой из пунктов меню был выбран, и посылает соответствующее командное сообщение объекту, с которым ассоциировано меню Этот объект, в свою очередь, может послать командные сообщения каким-то другим объектам. Например, если была выбрана команда File/Open, меню передаст обработчику основного окна приложения сообщение FILEOPEN, а тот, в свою очередь, может передать команду Open объекту, отвечающему за отрисовку и обработку файлового диалога.
Таким образом, вместо последовательно исполняющейся программы, время от времени вызывающей систему для исполнения той или иной функции, мы получаем набор обработчиков, вызываемых системой в соответствии с желаниями пользователя. Каждый отдельный обработчик представляет собой конечный автомат, иногда даже вырожденный, не имеющий переменной состояния. Код обработчика и по реализации обычно похож на конечный
автомат, и состоит m большого оператора switch, выбирающего различные действия в зависимости от типа пришедшего сообщения (пример 7.8).
Захват участков файлов
Захват участков файлов
Семафоры удобны при синхронизации доступа к единому ресурсу, такому как принтер или неделимая структура данных. Если же нам нужна синхронизация доступа к ресурсу, имеющему внутреннюю структуру, например к файлу с базой данных, лучше использовать другие методы.
Если говорить именно о файле, оказывается удобным блокировать доступ к участкам файла. При этом целесообразно ввести два типа захватов: для чтения и для записи. Захват для чтения разрешает другим нитям читать из заблокированного участка и даже ставить туда такую же блокировку, но запрещает писать в этот участок и, тем более, блокировать его для записи. Этим достигается уверенность в том, что структуры данных, считываемые из захваченного участка, никем не модифицируются, поэтому гарантирована их целостность и непротиворечивость.
В свою очередь, захват для записи запрещает всем, кроме установившей его нити, любой доступ к заблокированному участку файла. Это означает, что данный участок файла сейчас будет модифицироваться, и целостность данных в нем не гарантирована.
Железнодорожный семафор
Рисунок 7.6. Железнодорожный семафор
Наиболее простым случаем семафора является двоичный семафор. Начальное значение флаговой переменной такого семафора равно 1, и вообще она может принимать только значения 1 и 0. Двоичный семафор соответствует случаю, когда с разделяемым ресурсом в каждый момент времени может работать только одна нить.
Семафоры общего вида могут принимать любые неотрицательные значения. В современной литературе такие семафоры называют семафорами-счетчиками (counting semaphore). Это соответствует случаю, когда несколько нитей могут работать с объектом одновременно, или когда объект состоит из нескольких независимых, но равноценных частей — например, несколько одинаковых принтеров. При работе с такими семафорами часто разрешают процессам вычитать и добавлять к флаговой переменной значения, большие единицы. Это соответствует захвату/освобождению нескольких частей ресурса.
Многие системы предоставляют также сервисы, позволяющие просмотреть состояние семафора без его изменения и произвести "неблокируюшуюся" форму захвата, которая возвращает ошибку в ситуации, когда нормальный захват семафора привел бы к блокировке. Теоретики не очень любят такие примитивы, но при разработке сложных сценариев взаимодействия с участием многих семафоров они бывают полезны.
Во многих современных книгах и операционных системах семафорами называются только семафоры общего вида, двоичные же семафоры носят более краткое и выразительное имя мутекс (mutex — от MUTnal EXclusion, взаимное исключение). Проследить генезис этого названия автору не удалось, но можно с уверенностью сказать, что оно вошло в широкое употребление не ранее конца 80-х. Так, в разрабатывавшейся в середине 80-х годов OS/2 1.0, двоичные семафоры еще называются семафорами, а в Win32, разработка которой происходила в начале 90-х, уже появляется название mutex. Операции над мутексом называются захватом (acquire) (соответствует входу в критическую секцию) и освобождением (release) (соответствует выходу из нее).
Многие ОС предоставляют для синхронизации семафоры Дейкстры или похожие на них механизмы.
Живая блокировка
Рисунок 7.2. Живая блокировка
Как живая, так и мертвая блокировки возможны и в ситуации, когда ресурс только один, но примитив взаимоисключения не атомарен, т. е. операция захвата выполняется в несколько этапов.
Живая блокировка при арбитраже шины
Живая блокировка при арбитраже шины
Рассмотрим процесс арбитража шины: два устройства соревнуются за доступ к среде передачи. Устройство начинает передачу и при этом сравнивает передаваемый сигнал с принимаемым из шины. Возникновение расхождений между этими сигналами интерпретируется как коллизия (collision) — предполагается, что расхождения обусловлены работой другого передатчика. Обнаружив коллизию, устройство прекращает передачу. Сигнал распространяется по шине с конечной скоростью, поэтому прекратить передачу будут вынуждены оба устройства (в разд. Устройства графического выхода мы увидим пример того, как в низкоскоростных локальных шинах это ограничение можно обойти). Таким образом, оба устройства не могут начать передачу сразу же после того, как в шине "установится тишина": это приведет к живой блокировке. Схема разрешения коллизий CSMA/CD (Carrier Sence Multiple Access/Collision Detection, множественный доступ с прослушиванием несущей и обнаружением коллизий), используемая в протоколах локальных сетей семейства Ethernet, требует от устройства, обнаружившего коллизию, ожидания в течение случайного интервала времени.
Единственно правильная реакция на получение сообщения о мертвой блокировке — это освободить все занятые нитью ресурсы и подождать в течение случайного промежутка времени. Таким образом, поиск возможных блокировок сильно усложняет и логику работы самих примитивов взаимоисключения (нужно поддерживать граф, описывающий, кто кого ждет), и код, использующий эти примитивы.
Простейшее альтернативное решение — разрешить каждой нити в каждый момент времени держать захваченным только один объект — прост и решает проблему в корне, но часто оказывается неприемлемым. Больше подходит соглашение о том, что захваты ресурсов должны всегда происходить в определенном порядке. Этот порядок может быть любым, важно только, чтобы он всегда соблюдался.
Еще один вариант решения состоит в предоставлении возможности объединять примитивы и/или операции над ними в группы. При этом программа может выполнить операцию захвата флагов fiag1 и fiag2 единой командой, во время исполнения которой никакая другая программа не может получить доступ к этим переменным. Групповая операция выполняется как транзакция, т. е. либо происходит вся целиком, либо не происходит вообще. Если хотя бы одна из операций группы приводит к ожиданию, групповой примитив снимает все флаги, которые успел поставить до этого.
Ожидание с освобождением ресурсов, впрочем, порождает ряд более специфических проблем. Рассмотрим одну из них: нити А нужны ресурсы X и Y, которые она разделяет, соответственно, с нитями В и С. Если нить А захватывает ресурсы в соответствии с предложенным протоколом (освобождая их при неудачной попытке захвата), возможен такой сценарий исполнения нитей В и С, при котором нить А не получит доступа к ресурсам никогда. Напротив, захват ресурсов по мере их освобождения другими нитями может (если В и С сцеплены по каким-то другим ресурсам) привести к мертвой блокировке. Общего решения задачи разрешения блокировок и родственных им ситуаций при взаимоисключении доступа ко многим ресурсам на сегодня не предложено.
Описанное выше явление иногда называют "проблемой голодного философа". История этого колоритного названия восходит к модели, которую использовал для демонстрации описанного этого феномена.
Некоторое количество (у Э. Дейкстры — пять) философов сидят вокруг стола, на котором стоит блюдо спагетти (вместо спагетти можно взять, например, блины). Спагетти едят двумя вилками. В нашем случае, количество вилок равно количеству философов, так что соседи за столом разделяют вилку (гигиенический аспект проблемы мы опускаем).
Каждый философ некоторый (переменный) промежуток времени размышляет, затем пытается взять лежащие рядом с ним вилки (Рисунок 7.3). Если ему это удается, он принимается за еду. Ест он также переменный промежуток времени, после этого откладывает вилки и вновь погружается в размышления. Проблемы возникают, когда философ не может взять одну из вилок.
