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

Часто выделяют три технологии обеспечения параллельной работы: симметричные многопроцессорные системы (SMP — symmetrical multiprocessing), кластерные конфигурации и распределенные вычислительные системы (Grid). SMP требует поддержки как со стороны аппаратуры, так и со стороны операционной системы, а кластеры и Grid-среды больше зависят от организации сетевого взаимодействия.

Параллелизм ядра

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

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

Блокировки требуют соблюдения правил доступа к памяти, на поддержку которых тратятся определенные вычислительные ресурсы, причем даже работая на однопроцессорных компьютерах, поэтому, чтобы не включать в ядро Linux лишний код используется условная компиляция по макроопределению CONFIG_SMP, устанавливаемому утилитой autoconf. Все фрагменты кода, помеченные этим макросом, относятся к многопроцессорной системе; таких мест в общем коде операционной системы, содержащемся в каталоге kernel, восемнадцать. В основном они сосредоточены в планировщике, системе управления потоками, обработке исключительных ситуаций и сигналов, в коде управления таймером. Ядро, собранное с этим макросом, обычно поставляется в отдельном пакете, который устанавливается только в случае необходимости. В частности, если Linux устанавливался на компьютер с одним процессором, а потом в него был добавлен второй, то нужно переустановить ядро.

В ядре Linux для организации параллельных вычислений предусмотрено три группы примитивов: атомарные операции (include/asm-/atomic.h, где вместо нужно подставить код соответствующей аппаратной архитектуры), семафоры (include/asm-/semaphore.h) и спин-блокировка (include/linux/spinlock.h). Из 17 вариантов различных процессорных архитектур, для которых разработана ОС Linux, поддержка SMP не реализована только у четырех: ARM, М68000, SuperH и встроенных сетевых процессорах Etrax. Разберем каждую из этих групп.

Атомарные операции

Под атомарными операциями подразумеваются команды изменения данных в оперативной памяти, которые выполняются процессором с полной блокировкой шины памяти, т. е. ни один другой процессор гарантированно не будет конкурировать с монополистом. Так, на платформе i386, для реализации атомарных операций используется специально для этого предназначенный командный префикс lock, заставляющий процессор выполнять следующую команду с блокировкой шины памяти. В Linux в качестве атомарной выбраны операции инкремента и декремента с проверкой счетчика на равенство нулю. (Архитектура i386 также содержит команду test and set bit, которая используется для атомарного изменения бита с одновременной проверкой его.)

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

Семафоры

Семафоры — стандартное средство синхронизации процессов в Unix. Для того чтобы их можно было использовать и в SMP-системах, нужно обеспечить атомарность изменения счетчика семафора, поэтому в многопроцессорных версиях функций up (увеличение счетчика семафора) и down (его уменьшение) также используются атомарные команды (для i386 с префиксом lock). Основное отличие семафора от атомарных операций в том, что он предоставляет стандартный сервис, доступный для пользовательских программ. Есть варианты семафоров, которые останавливают процесс, пока не будут открыты, а есть не блокируемые семафоры, помеченные суффиксом interruptible. Для некоторых платформ семафор базируется на атомарных операциях, а для остальных оказалось лучше написать отдельный, более эффективный код. В частности, для платформы i386 пошли по второму варианту. Впрочем, в общем коде ядра семафоры используются достаточно редко, чаще встречается его частный случай — спин-блокировка.

Спин-блокировка

Термин spin lock можно перевести как «блокировка в цикле» или «вращающаяся блокировка». Однако, похоже, его авторы попытались обобщить понятие спина, как свойство ядерных объектов физической природы, таких как электроны, на ядерные объекты ОС Linux. Мы будем использовать термин «спин-блокировка», чтобы подчеркнуть эту связь. Смысл механизма спин-блокировки состоит в том, чтобы предоставить процессу возможность монопольно захватить какой-либо объект памяти. При этом получить доступ на чтение объекта могут несколько процессов одновременно, но запись может происходить только в том случае, когда нет других читающих и пишущих процессов. Чтобы воспользоваться механизмом спин-блокировки достаточно, чтобы объект имел тип spinlock_t. По сути своей спин-блокировка является частным случаем семафора, однако для всех платформ, поддерживающих SMP, ее реализуют с помощью специального кода.

Фрагменты кода

Кроме этих специализированных функций в ОС Linux в различных местах ядра есть фрагменты кода, которые так же используются только в многопроцессорной конфигурации. Например, такие фрагменты есть в планировщике (функция schedule), в которой предусмотрены механизмы перемещения процессов с одного процессора на другой. Обеспечивается работа с контроллерами прерываний, которых в многопроцессорной системе несколько. Большинство этого кода содержится в файле arch//kernel/smp.c. Впрочем часто они опираются на универсальные для Linux многопроцессорные примитивы.

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

Кластерные технологии и распределенные вычисления

С точки зрения ядра операционной системы поддержка кластеров и распределенных систем заключается в эффективной работе с сетью, что выражается во взаимодействии с сетевым процессором. Собственно, сейчас практически любой компьютер является многопроцессорным, кроме центрального процессора есть еще микропроцессоры видеоплат, дисков и сетевых плат. Каждый из процессоров работает со своей собственной операционной системой, которая должна корректно взаимодействовать с ядром Linux. Так, в первом драйвере для платы Gigabit Ethernet каждый полученный по сети пакет вызывал прерывание центрального процессора и, в результате, могла возникнуть ситуация, когда прерываний генерировалось так много, что процессор был полностью загружен их обработкой. В следующих версиях эта проблема была решена путем компоновки пакетов в большие блоки. Тем не менее, разработчикам программного обеспечения постоянно приходится помнить о «многопроцессорности» даже однопроцессорного компьютера.

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

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

Следует отметить, что на кластере нужно исполнять приложения, которые уже написаны с учетом параллельных вычислений и «знают», что разные части программы будут выполняться на разных узлах кластера. Основные стандартные компоненты современных многоуровневых систем, как правило, соответствуют этим требованиям. Так сервер Apache каждый запрос отрабатывает отдельным потоком, и может быть эффективно использован как на одной SMP-машине, так и на сбалансированном по нагрузке кластере. Серверы приложений и баз данных, такие как WebSphere, DB2, Oracle, MySQL, Postgress, также могут быть сконфигурированы с учетом многопроцессорности (а иногда — и многокомпьютерности), что позволяет запускать их на кластере и балансировать нагрузки на каждый узел.

Для взаимодействия процессов, принадлежащих одному приложению, но работающих на разных узлах кластера можно использовать как стандартные для Unix механизмы взаимодействия: потоки, трубы, разделяемые файлы, так и специализированные библиотеки передачи сообщений. Для Linux самыми популярными из таких библиотек являются PVM и MPI, хотя они могут обеспечивать взаимодействие компонентов, работающих под управлением разных операционных систем. Если приложение написано с их использованием, то оно идеально подходит для работы на кластере.

Авторами книги «Параллельные вычисления» Валентином и Владимиром Воеводиными была проведена большая работа по изучению существующих программ, написанных на языке Фортран для решения задач минимизации, линейной алгебры и математической физики. На основе этого исследования ими была разработана теория изучения и выделения параллельной структуры программ для определенного ими линейного класса алгоритмов. Оказалось, что среди 12 тыс. строк, изученных ими алгоритмов, к линейному классу можно свести около 90-95% текстов. Таким образом, постепенно появляются теоретические основы для выделения параллельной структуры алгоритмов с последующей их реализацией в виде параллельных программ. В то же время часто в бизнес-приложениях решаются комбинаторные задачи, которые связаны с изучением небольшой выборки из достаточно большого массива информации.

Собственно, многие ресурсоемкие задачи представляют собой достаточно короткие фрагменты кода, обрабатывающие небольшую выборку данных из большого массива. Такие фрагменты можно выносить на удаленные компьютеры в отдельные потоки и только выдавать им новые порции данных, получать и обрабатывать результат. Именно так и устроено большинство распределенных вычислительных систем, например, seti@home. В них есть центральный сервер, раздающий задания множеству клиентов, получающий и обрабатывающий результаты. Клиенты в большинстве своем работают только в фоновом режиме при минимальной загрузке центрального процессора. Хотя все приложения, которые требуют распределенных вычислений, индивидуальны, имеется базовый набор компонентов, позволяющих упростить создание необходимой инфраструктуры. В качестве примера можно привести свободно распространяемый пакет Globus Toolkit, который позволяет разрабатывать кроссплатформные распределенные системы. Таким образом, для Linux как для наиболее распространенного представителя семейства Unix сегодня имеется полный спектр решений для параллельных вычислений.

Реализация атомарной функции down в ядре Linux

static inline void down(struct semaphore * sem) {
__asm__ __volatile__(
"# atomic down operation
	"
/*A*/       LOCK "decl %0
	"
     /* -sem->count */
/*B*/       "js 2f
"
"1:
"
/*C*/       LOCK_SECTION_START("")
/*D*/       "2:	call __down_failed
	"
"jmp 1b
"
/*E*/        LOCK_SECTION_END
:"=m" (sem->count)
:"c" (sem)
:"memory");
}

Данная inline-функция уменьшения значения семафора написана на встроенном ассемблере gcc, которым компилируется ядро Linux. В строке, помеченной литерой A, выполняется атомарная операция уменьшения счетчика на единицу. В строке B проверяется стал ли счетчик после этого отрицательным, и если это произошло, управление передается на строку, помеченную литерой D, в которой вызывается функция __down_failed, дожидающаяся освобождения семафора и захватывающая его.

Макрос из строки C определен в файле include/linux/spinlock.h. Он заставляет компилятор собирать фрагмент кода между литерами C и E в отдельной секции ядра. Это означает, что код до строки C вставляется компилятором в тело функции, откуда вызвана down (поскольку она помечена модификатором inline), а для кода между C и E отводиться специальное место в памяти. На него исполнение передается только в случае, если семафор закрыт.

Реализация спин-блокировки для процессоров i386

#define spin_lock_string 
"
1:	" 
/*A*/"lock ; decb %0
	" 
/*B*/"js 2f
" 
LOCK_SECTION_START("") 
/*C*/"2:	" 
"cmpb $0,%0
	" 
"rep;nop
	" 
/*D*/"jle 2b
	" 
/*E*/"jmp 1b
" 
LOCK_SECTION_END

Спин-блокировка полностью реализована в виде макроопределения, которому в качестве параметра передается ссылка на блокируемый объект. В строке A делается атомарная попытка захватить объект. Если она не удается, то (строка B) управление передается в отдельную секцию ядра, аналогично тому, как это было сделано в функции down. После этого процесс попадает в жесткий цикл между строками C и D, где постоянно проверяется, освободился объект или нет. Причем эта проверка выполняется не атомарно, т. е. не блокирует шину памяти. Как только объект освободился (строка E) управление передается в начало до строки A для повторной атомарной попытки его захвата.