Процессы sleep и wakeup на мультипроцессоре с памятью совместного использования

Роб Пайк
Дейв Пресотто
Кен Томпсон
Джерард Хольцманн

rob,presotto,ken,gerard@plan9.bell-labs.com
АБСТРАКТНО

Проблема временного приостановления выполнения процесса («перехода ко сну») на мультипроцессоре с совместным использованием памяти (Shared-memory Multiprocessor) считается одной из самый труднорешимых, особенно если процесс должен перейти в состояние готовности к выполнению (так называемое «пробуждение») вследствие определенного события. Здесь нами представлен код для примитивов «перехода ко сну» и «пробуждения», которые мы используем в нашей многопроцессорной системе. Код испытан годами активного использования, а также верификационной системой.

Наша проблема заключается в синхронизации процессов на симметричном мультипроцессоре (Symmetric MultiProcessor — SMP) с памятью совместного использования. Процессы временно приостанавливают выполнение, или переходят ко сну, до наступления события наподобие прерывания ввода-вывода. Когда происходит прерывание, процесс пробуждается и переходит в состояние «готовности к выполнению». В это время могут запускаться другие процессы, при чем на процессоры будут влиять другие прерывания.

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

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

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

В этом документе описаны наши попытки решения проблемы перехода ко сну/пробуждения в Plan 9 [4]. У нас появлялись разные реализации решений в течение нескольких месяцев и каждый раз мы ошибочно убеждали себя в их корректности. Для доказательства корректности верификацией, алгоритмы, предназначенные для мультипроцессоров, могут быть основательно трудными, формальная аргументация для них непрактична. Наконец, мы разработали алгоритм, проверенный инструментальным средством эмпирического тестирования. Этот код приведен здесь вместе с несколькими комментариями о процессе, для которого он был создан.

История

Поскольку процессы в системах Plan 9 и Unix имеют схожую структуру и особенности, возникает резонный вопрос, а нельзя ли Unix sleep и wakeup [1] адаптировать из их стандартной унипроцессорной реализации для наших мультипроцессорных нужд? Оказывается, что нет.

Программы Unix как аргумент принимают единственный глобальный адрес, который служит уникальным идентификатором для связи пробуждения с соответствующим процессом или процессами. Этому методу присущие существенные недостатки. С точки зрения sleep и wakeup, трудность состоит в ассоциации структуры данных с произвольным адресом; программы неспособны поддерживать запись переменной состояния значением состояний события и процессов. (Обратная операция, конечно, легка — мы можем требовать адрес для указания на специальные структуры данных. Но, исследовав Unix sleep и wakeup, мы узнали, что код, вызывающий их, нам не подходит.) Также, многочисленные процессы переходят ко сну «по» данному адресу, вследствие чего wakeup должен допускать их всех, и позволять планировщику процессов определять, какой процесс действительно имеет преимущество для события. Это неэффективно; хотя механизм организаций очереди (queueing) может быть предпочтительным, но, вновь, наличествует трудность в ассоциации очереди с общим адресом. Кроме того, отсутствие состояния означает, что sleep и wakeup не могут знать какой точно процесс (или прерывание) выполняется; sleep и wakeup должны запускаться автоматически. На унипроцессоре для этого достаточно отключить прерывания в течение их выполнения. На том же унипроцессоре, тем не менее, большинство процессоров могут тормозить прерывания только на текущем процессоре, так что пока процесс выполняется, требуемое прерывание для sleep может прийти и отправиться на другой процессор. Если пробуждение инициировано другим процессом, то проблема становится намного сложнее. В этом случае должен использоваться какой-нибудь механизм межпроцессового взаимного выполнения, который, еще раз, трудно осуществить без средств передачи состояний.

В итоге, полезные на унипроцессоре Unix sleep и wakeup должны либо запускаться автоматически на одном процессоре (как с использованием проверок), либо же есть потребность в более богатой модели для своей связи.

Конструкция

Рассмотрим вариант пробуждений от прерываний пребывающих во сне процессов. (Другой вариант, процесс, который будит другой процесс, легче в реализации, поскольку атомарность здесь может быть достигнута с использованием взаимоблокировки.) Когда происходит событие, все приостановленные процессы пробуждаются, поскольку значение условия, связанного с событием, больше не является истинным. Условие может быть просто происходящим событием, или чем-то другим. Мы представляем условие как функцию с одним аргументом типа void*; поддерживаемый устройством код генерирует прерывания, тем самым представляя функцию, которая используется sleep и wakeup, для синхронизации. Функция возвращает false если событие не произошло, и true — в противном случае. Программы sleep и wakeup должны, конечно, работать корректно если событие происходит пока процесс выполняет sleep.

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

Для эффективности, мы хотим чтобы на нашем мультипроцессоре многочисленные примеры sleep и wakeup могли запускаться одновременно. Например, процессу, вызывающему sleep для ожидания получения символа из входящего канала, необязательно ожидать другой процесс для завершения sleep — для ожидания дискового блока. На высшем уровне, мы хотим чтобы у процесса, считывающего данные из входного канала, была возможность выполнить sleep параллельно с процессом, получающим данные из другого входного канала. Стандартный метод синхронизации заключается во взаимоблокировке канального «драйвера», как результат, за раз только один процесс будет выполняться в канальном коде. Этот способ несомненно неадекватен для наших нужд; нам требуется «мелкозернистая» синхронизация, и что конкретнее, применение взаимоблокировок на уровне индивидуальных каналов вместо уровня канального драйвера.

Наш метод заключается в использовании объекта под названием rendezvous, который представляет собой структуру данных, посредством которой sleep и wakeup синхронизируются. (Подобно названная конструкция в языке Ada является управляющей структурой; наша же структура данных не имеет к ней никакого отношения.) Rendezvous распределена для каждого активного источника событий: по одной для каждого канала ввода-вывода, для каждого конца pipe, и т.д. Rendezvous хранится как взаимоблокирующая структура, в которой производится запись состояния спящего процесса, таким образом, sleep и wakeup могут общаться если событие происходит перед или после выполнения sleep.

Как следствие, наша конструкция sleep — функция

вызываемая спящим процессом. Аргумент r соединяет вызов к sleep с вызовом к wakeup, и является частью структуры данных для (скажем) устройства. Описание функции condition дано выше; вызываемая с аргументом arg, она используется sleep для установления чем было вызвано событие. У wakeup более простая спецификация:

Wakeup должен вызываться после того как условие получило значение истина.

Реализация

Тип данных Rendezvous описывается следующим образом

Наши Locks — test-and-set spin блокировки. Программа lock(Lock *l) возвращается когда текущий процесс имеет эту блокировку; unlock(Lock *l) осуществляет блокировку.

Вот наша реализация процесса sleep. Ее детали описаны ниже. Thisp — это указатель на текущий процесс на текущем процессоре. (Его значение варьируется на каждом процессоре.)

Теперь wakeup.

Sleep и wakeup оба начинаются с отключения прерываний и блокировки структуры rendezvous. Из-за того что wakeup может быть вызван программой прерывания, блокировка должна быть установлена только с прерываниями, отключенными на данном процессоре, так что если прерывание происходит в течение sleep, оно будет действовать лишь на другой процессор; если оно получено во время выполнения процессором sleep, то spin блокировка в wakeup зависнет навсегда. В конце каждой программы блокировка опускается и приоритет процессора приобретает предыдущее значение. (Wakeup требует торможения прерываний в случае если он вызван процессом; это no-op, если вызван прерыванием.)

Sleep проверяет выполнение условия, если результат позитивен, то он возвращается. В противном случае процесс посылает свое имя в структуру rendezvous, где его должен найти wakeup, отмечает его состояние как «ожидающий пробуждения» (используется для проверки на ошибки) и посредством вызова sched() переходит в сон. Обработка структуры rendezvous осуществляется во время блокировки, и wakeup только проверяет его, так что атомарность и исключение гарантированы.

У wakeup более простая задача. Когда он вызван, условие принимает истинное значение, при этом блокируется rendezvous, далее выполняется проверка, находится ли процесс в ожидании, и подготовка для запуска.

Обсуждение

Техника синхронизации использовалась здесь подобно известным методам, даже значительно поодаль от тезиса Saltzer [5]. Код выглядит тривиально корректным в ретроспективе: весь доступ к структурам данных осуществляется во время блокировки, и здесь нет места тому, что вещи могут выходить вне порядка. Тем не менее, нам потребовалось несколько итераций для достижения такой реализации, поскольку действия, которые могут произойти не правильно, часто трудно усмотреть. У нас было четыре ранних реализации, которые были проверены за большой отрезок времени, но неисправность была обнаружена лишь тогда, когда устройство отличного стиля или активности было добавлено в систему.

Вот, к примеру, некорректная реализация wakeup, имеет тесное отношение к одной из наших версий.

Ошибка кроется в том, что чтение r->p должно происходить в то время, когда другой процесс вызывает sleep, так что когда прерывание проверяет структуру, то не обнаруживается ни один процесс, нуждающийся в пробуждении, и спящий процесс избегает этого выхода из сна. Мы написали этот код, потому что осознали, что выборка p = r->p была в сущности элементарная и необходимости во взаимоблокировке нет. Баг был обнаружен путем проверки когда новое, очень быстрое устройство было добавлено в систему и прерывания были тесно перекрыты. Тем не менее, он присутствовал в системе в течение нескольких месяцев без причинения неудобств.

Какое количество ошибок таится в нашей предположительно корректной вышеописанной реализации? Нам бы очень хотелось гарантировать ее правильность; формальные доказательства вне наших возможностей когда вовлечены тонкости прерываний и мультипроцессоров. Первые три автора предложили идею попробовать как поведут себя их автоматизированные инструментальные средства для проверки протоколов [3] с новыми sleep и wakeup. Код был транслирован в язык для системы (к сожалению, без возможности доказательства корректности самой трансляции) и проверен в условиях полной эмуляции.

Программой проверки был найден баг. При нашем предположении, что есть лишь одно прерывание, баг не выявлял себя, но в более общем случае многочисленных прерываний, синхронизирующихся через одну и ту же условную функцию и rendezvous, процесс и прерывание могут входить в специфическое состояние. Процесс должен возвращаться из sleep с условной функцией значения false, если была задержка между условием, стающим истинным и вызовом wakeup, с задержкой, происходящей просто как будто бы получающий процесс вызывает sleep. Теперь условие имеет истинное значение, так что процесс возвращается немедленно, выполняет все что от него требуется, и затем (скажем) решает вызвать sleep вновь. Если условие неверное — переход в сон. Далее wakeup осуществляет поиск спящего процесса, и будит его, но условие теперь — false.

Наличествует легкое (и проверенное) решение: в конце sleep или после возвращения из sleep, если условие неверное, — вновь вызов sleep. Предполагается, что это повторное выполнение не может повториться; вторая синхронизация гарантировано будет действовать на внешних условиях.

Несмотря на то, что оригинальный код полностью защищен взаимоблокировками и был проверен всеми нами на корректность, с ним все еще возникают проблемы. Мы считаем, что для гарантии безопасности мультипроцессорных алгоритмов требуется полный специальный автоматизированный анализ. Наш опыт подтверждает, что правильность мультипроцессорного алгоритма почти невозможно гарантировать путем верификации или простого тестирования. Тестирование может показать наличие ошибок, но никак не их отсутствие [2].

Мы утверждаем, что вышеприведенный код с предложенной модификацией проходит все тесты на правильность. Но мы не можем с полной уверенностью сказать, тем не менее, что код универсально корректен.

Литература

[1] Maurice J. Bach, The Design of the UNIX Operating System, Prentice-Hall, Englewood Cliffs, 1986.
[2] Edsger W. Dijkstra, The Humble Programmer - 1972 Turing Award Lecture, Comm. ACM, 15(10), pp. 859-866, October 1972.
[3] Gerard J. Holzmann, Design and Validation of Computer Protocols, Prentice-Hall, Englewood Cliffs, 1991.
[4] Rob Pike, Dave Presotto, Ken Thompson, Howard Trickey, Plan 9 from Bell Labs, Proceedings of the Summer 1990 UKUUG Conference, pp. 1-9, London, July, 1990.
[5] Jerome H. Saltzer, Traffic Control in a Multiplexed Computer System MIT, Cambridge, Mass., 1966.

Copyright © 2000 Lucent Technologies Inc. All rights reserved.
Copyright © 2003 Перевод Андрей С. Кухар.