Многопроцессорный вычислительный комплекс на основе коммутационной матрицы с симметричной обработкой заданий всеми процессорами

Московский государственный институт радиотехники, электроники и автоматики (Технический Университет)

Проект по курсу

“Вычислительные комплексы, системы и сети ЭВМ”

Группа: АВ-33-93

Студент: Липин В.В.

Москва

1998

1. Общая часть

1.1 Содержание

1. Общая часть

1.1. Содержание

1.2. Задание

1.3. Введение

2. Аппаратная организация МПВК

2.1. Структурная схема МПВК

2.2. Функциональная схема элемента коммутационной матрицы

2.3. Организация оперативной памяти

2.3.1. Память с расслоением

2.3.2. Применение кода Хэмминга в модулях памяти

2.4. Организация резервирования и восстановления при отказе любого компонента МПВК

3. Организация функционирования ОС на МПВК

3.1. Симметричная многопроцессорная обработка (SMP)

3.2. Нити

3.2.1. Подходы к организации нитей и управлению ими в разных вариантах ОС UNIX

3.3. Семафоры

3.3.1. Определение семафоров

3.3.2. Реализация семафоров

3.4. Тупиковые ситуации

3.5. Предотвращение тупиковых ситуаций

3.5.1. Линейное упорядочение ресурсов

3.5.2. Иерархическое упорядочение ресурсов

3.5.3. Алгоритм банкира

3.6. Защита информации

4. Литература

1.2 Задание

(вариант №16)

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

· использовать матрицу с перекрестной коммутацией;

· количество процессоров – 8;

· количество блоков ОЗУ – 4;

· количество каналов ввода-вывода – 4;

Требуется разработать структурную схему коммутационной матрицы и функциональную схему элемента коммутационной матрицы.

Описать функционирование ОС для организации многопроцессорной обработки.

Описать организацию резервирования и восстановления вычислительного процесса при отказе любого компонента многопроцессорного вычислительного комплекса.

1.3 Введение

Разработка многопроцессорных (МПВК) и многомашинных (ММВК) вычислительных комплексов, как правило, имеет свой целью повышение либо уровня надежности, либо уровня производительности комплекса до значений недоступных или труднореализуемых (реализуемых с большими экономическими затратами) в традиционных ЭВМ.

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

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

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

2. Аппаратная организация МПВК

2.1 Структурная схема МПВК

В МПВК с перекрестной коммутацией все связи осуществляются с помощью специального устройства – коммутационной матрицы. Коммутационная матрица позволяет связывать друг с другом любую пару устройств, причем таких пар может быть сколько угодно – связи не зависят друг от друга. Структурная схема МПВК приведена на рисунке:

Коммутационная матрица выполняет передачу данных между процессорами и памятью, а также между процессорами ввода-вывода и памятью. Коммутируются только внутренние шины МПВК, основное назначение которых – высокоскоростная передача данных, для этих шин нет смысла добиваться высокой протяженности проводников или стандартизации с целью упрощения подключения дополнительных устройств. Высокоскоростной обмен с периферийными устройствами осуществляется посредством процессоров ввода-вывода, которые являются контроллерами периферийных высокоскоростных шин, к которым, в свою очередь и подключаются контроллеры соответствующих устройств. На роль таких периферийных шин подходят, например, VME (применяется в МПВК фирмы Digital Equipment Company), SBus (применяется в МПВК фирмы Sun Microsystems) или PCI (применяется в МПВК, построенных на процессорах фирмы Intel семейства x86).

В SMP совместимой системе прерывания управляются контроллерами APIC (Advanced Programmable Interrupt Controller), БИС которых серийно выпускаются многими производителями микроэлектронных изделий (например DEC, Sun, IBM, Texas Instruments). Данные контроллеры обладают распределенной архитектурой, в которой функции управления прерываниями распределены между двумя функциональными блоками: локальным (ЛБ) и ввода-вывода (БВВ). Эти блоки обмениваются информацией через шину, называемую шиной коммуникаций контроллера прерываний (ШККП). Устройство ввода-вывода определяет появление прерывания, адресует его локальному блоку и посылает по шине ШККП. Блоки APIC совместно отвечают за доставку прерывания от источника прерываний до получателей по всей системе. Использование такой организации дополнительно увеличивает расширяемость за счет разгрузки разделения между процессорами нагрузки по обработке прерываний. Благодаря распределенной архитектуре, локальные блоки или блоки ввода-вывода могут быть реализованы в отдельной микросхеме или интегрированы с другими компонентами системы.

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

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

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

2.2 Функциональная схема элемента коммутационной матрицы

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

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

Выходом представляется применение специализированных интегральных микросхем, выпускаемых некоторыми производителями микроэлектроники. У Texas Instruments это ИМС SN74CBT3384 (разрядность 10 бит), SN74CBT16244 (разрядность 16 бит), SN74CBT16210 (разрядность 20 бит), у Cypress Semiconductor - CYBUS3384 (два коммутатора в одном корпусе с разрядностью 5 бит каждый), у Sun Microelectronics - STP2230SOP. Данные ИМС имеют достаточное быстродействие (задержка распространения 5.2 – 10.0 нс, что соответствует максимальной тактовой частоте 190 – 100 МГц) и достаточно невысокую цену (несколько долларов за единицу в партиях от 1000 штук).

Все ИМС этого семейства имеют практически одинаковую функциональную схему:

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

2.3 Организация оперативной памяти

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

С целью повышения быстродействия имеет смысл применить расслоение памяти по адресам на 4 модуля (разбиение на 4 модуля оговорено в задании, так что целесообразно применить данное разбиение для улучшения быстродействия МПВК). Более подробно расслоение по адресам будет рассмотрено ниже.

Для повышения надежности модулей памяти было решено применить корректирующие коды. Наиболее распространен код Хэмминга позволяющий исправлять одиночные и обнаруживать двойные ошибки. Более подробно его применение рассматривается ниже.

2.3.1 Память с расслоением

Наличие в системе множества микросхем памяти позволяет использовать потенциальный параллелизм, заложенный в такой организации. Для этого микросхемы памяти часто объединяются в банки или модули, содержащие фиксированное число слов, причем только к одному из этих слов банка возможно обращение в каждый момент времени. Как уже отмечалось, в реальных системах имеющаяся скорость доступа к таким банкам памяти редко оказывается достаточной. Следовательно, чтобы получить большую скорость доступа, нужно осуществлять одновременный доступ ко многим банкам памяти. Одна из общих методик, используемых для этого, называется расслоением памяти. При расслоении банки памяти обычно упорядочиваются так, чтобы N последовательных адресов памяти i, i+1, i+2, . . . , i+N-1 приходились на N различных банков. В i-том банке памяти находятся только слова, адреса которых имеют вид k*N + i (где 0 < k < M-1, а M число слов в одном банке). Можно достичь в N раз большей скорости доступа к памяти в целом, чем у отдельного ее банка, если обеспечить при каждом доступе обращение к данным в каждом из банков. Имеются разные способы реализации таких расслоенных структур. Большинство из них напоминают конвейеры, обеспечивающие рассылку адресов в различные банки и мультиплексирующие поступающие из банков данные. Таким образом, степень или коэффициент расслоения определяют распределение адресов по банкам памяти. Такие системы оптимизируют обращения по последовательным адресам памяти, что является характерным при подкачке информации в кэш-память при чтении, а также при записи, в случае использования кэш-памятью механизмов обратного копирования. Однако, если требуется доступ к непоследовательно расположенным словам памяти, производительность расслоенной памяти может значительно снижаться.

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

Если система памяти разработана для поддержки множества независимых запросов (как это имеет место при работе с кэш-памятью, при реализации многопроцессорной и векторной обработки), эффективность системы будет в значительной степени зависеть от частоты поступления независимых запросов к разным банкам. Обращения по последовательным адресам, или, в более общем случае, обращения по адресам, отличающимся на нечетное число, хорошо обрабатываются традиционными схемами расслоенной памяти. Проблемы возникают, если разница в адресах последовательных обращений четная. Одно из решений, используемое в больших компьютерах, заключается в том, чтобы статистически уменьшить вероятность подобных обращений путем значительного увеличения количества банков памяти. Например, в суперкомпьютере NEC SX/3 используются 128 банков памяти.

Подобные проблемы могут быть решены как программными, так и аппаратными средствами.

2.3.2 Применение кода Хэмминга в модулях памяти

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

Так как большинство современных высокопроизводительных микропроцессоров имеют разрядность 64 бита, необходимо обеспечить разрядность памяти не менее 64 бит. Этой разрядности соответствует код Хэмминга (72, 64), что означает наличие 64 информационных разрядов и 8 контрольных. Можно рассчитать эффект от применения корректирующего кодирования:

Пусть вероятность отказа одиночного модуля памяти разрядностью 1 бит за некоторое время P₁=10^-5, тогда вероятность отказа одного из необходимых 64 модулей памяти за то же время P_общ=64*P₁=6.4*10^-4. В случае применения кода Хэмминга для потери информации необходимы две ошибки в 72-х разрядах: P_общ=(72*P₁)*(71*P₁)= 5.112*10^-7. Таким образом надежность возрастает более чем на три порядка при увеличении стоимости на 12.5%. Разумеется эти рассуждения верны лишь в случае пренебрежимо малой вероятности отказов и стоимости кодера и декодера по сравнению с модулями памяти, однако в случае реальных объемов памяти это действительно так.

2.4 Организация резервирования и восстановления при отказе любого компонента МПВК

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

Отказы оперативной памяти были рассмотрены выше. Отказы в коммутационной матрице также как и отказы оперативной памяти целесообразно маскировать применением кодов, корректирующих ошибки. Наиболее сложны для обнаружения и восстановления информации отказы процессоров, однако в случае наличия встроенных средств самоконтроля или при периодическом прогоне на каждом процессоре контрольных тестов, задача обнаружения решается довольно легко. Восстановление вычислительного процесса состоит в исключении операционной системой отказавшего процессора из списка доступных и запуске на другом процессоре пострадавшего процесса с последней контрольной точки. Отказы процессоров ввода-вывода обнаруживаются довольно легко, восстановление ввиду наличия 4-х идентичных по функциям ПВВ также несложно – необходимо лишь подключение критичных для работы МПВК периферийных устройств ко всем ПВВ с соответствующей коммутацией. Отказы самих периферийных устройств – наиболее простая и хорошо проработанная часть организации отказоустойчивости. Наиболее часто применяется тот или иной вид резервирования на уровне устройств – нагруженное, ненагруженное или скользящее.

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

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

3. Организация функционирования ОС на МПВК

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

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

3.1 Симметричная многопроцессорная обработка
(Symmetric Multiprocessor Processing – SMP)

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

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

Хотя все процессоры в SMP системе функционально идентичны, выделяется два их типа: загрузочный процессор (BSP) и прикладные процессоры (АР). Какой процессор играет роль загрузочного, определяется аппаратными средствами или совместно аппаратурой и BIOS. Это сделано для удобства и имеет значение только во время инициализации и выключения. BSP-процессор отвечает за инициализацию системы и за загрузку ОС. АР-процессор активизируется после загрузки ОС.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В системе с одним процессором маскированное прерывание предотвращает использование процессором ресурса. Но в SMP-среде этот механизм не дает возможности гарантировать, что различные процессы не будут иметь доступа к тому же самому ресурсу через другое прерывание.

В SMP ОС целесообразно использовать метод взаимоблокировки для управления прерываниями между процессорами. По сути, взаимоблокировка является программной процедурой, которая блокирует доступ второго процессора к уже занятому ресурсу. Например, когда ядро хочет получить доступ к защищенной области, такой как очередь отложенных вызовов процедур, оно должно "приобрести" замок, который связан с очередью. Если замок находится в распоряжении какого-либо процессора, то другой процессор пытается получить замок до тех пор, пока его не освободит другой процессор.

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

Ядро также может управлять нитью, назначая ей одно из трех состояний: готова, выполняется или ждет. Когда нить ждет результатов запроса, ядро изменяет состояние нити с "выполняется" на "ждет" и удаляет ее из очереди на выполнение. После того как нить получила ожидаемую ею информацию, ядро изменяет состояние нити с "ждет" на "готова" и возвращает ее в очередь. Нить выполняется, когда появляется возможность.

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

3.2 Нити (threads)

Понятие "легковесного процесса" (light-weight process), или, как принято называть его в современных вариантах ОС, "thread" (нить, поток управления) давно известно в области операционных систем. Интуитивно понятно, что концепции виртуальной памяти и потока команд, выполняющегося в этой виртуальной памяти, в принципе, ортогональны. Ни из чего не следует, что одной виртуальной памяти должен соответствовать один и только один поток управления. Поэтому, например, в ОС Multics допускалось (и являлось принятой практикой) иметь произвольное количество процессов, выполняемых в общей (разделяемой) виртуальной памяти.

Понятно, что если несколько процессов совместно пользуются некоторыми ресурсами, то при доступе к этим ресурсам они должны синхронизироваться (например, с использованием семафоров, см. раздел “Семафоры”). Многолетний опыт программирования с использованием явных примитивов синхронизации показал, что этот стиль "параллельного" программирования порождает серьезные проблемы при написании, отладке и сопровождении программ (наиболее трудно обнаруживаемые ошибки в программах обычно связаны с синхронизацией). Это явилось одной из причин того, что в традиционных вариантах ОС понятие процесса жестко связывалось с понятием отдельной и недоступной для других процессов виртуальной памяти. Каждый процесс был защищен ядром операционной системы от неконтролируемого вмешательства других процессов. Многие годы это считалось одним из основных достоинств системы (впрочем, это мнение существует и сегодня).

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

Второй (и может быть более существенной) проблемой явилось появление так называемых симметричных мультипроцессорных компьютерных архитектур (SMP - Symmetric Multiprocessor Processing). В таких компьютерах физически присутствуют несколько процессоров, которые имеют одинаковые по скорости возможности доступа к совместно используемой основной памяти. Появление подобных машин на мировом рынке, естественно, вывело на первый план проблему их эффективного использования. Понятно, что при применении традиционного подхода к организации процессов от наличия общей памяти не очень много толка (хотя при наличии возможностей разделяемой памяти об этом можно спорить). К моменту появления SMP выяснилось, что технология программирования все еще не может предложить эффективного и безопасного способа реального параллельного программирования. Поэтому пришлось вернуться к явному параллельному программированию с использованием параллельных процессов в общей виртуальной (а тем самым, и основной) памяти с явной синхронизацией.

Что же понимается под "нитью" (thread)? Это независимый поток управления, выполняемый в контексте некоторого процесса. Фактически, понятие контекста процесса изменяется следующим образом. Все, что не относится к потоку управления (виртуальная память, дескрипторы открытых файлов и т. д.), остается в общем контексте процесса. Вещи, которые характерны для потока управления (регистровый контекст, стеки разного уровня и т. д.), переходят из контекста процесса в контекст нити. Общая картина показана на рисунке:

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

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

3.2.1 Подходы к организации нитей и управлению ими в разных вариантах ОС UNIX

Хотя концептуально реализации механизма нитей в разных современных вариантах практически эквивалентны (да и что особенное можно придумать по поводу легковесных процессов?), технически и, к сожалению, в отношении интерфейсов эти реализации различаются. Мы не ставим здесь перед собой цели описать в деталях какую-либо реализацию, однако постараемся в общих чертах охарактеризовать разные подходы.

Начнем с того, что разнообразие механизмов нитей в современных вариантах ОС UNIX само по себе представляет проблему. Сейчас достаточно трудно говорить о возможности мобильного паралл