Традиционно компьютер рассматривается как машина, предназначенная для выполнения последовательных действий. В большинстве языков программирования алгоритм задается в виде последовательных инструкций; при работе программы процессор выполняет машинные команды последовательно, одну за другой. Каждая команда представляется в виде последовательности операций (выборка команды, выборка операндов, выполнение операции, сохранение результатов).
Такая точка зрения на компьютер никогда не соответствовала действительности полностью. На уровне микроопераций одновременно генерируются несколько управляющих сигналов. Уже давно применяется конвейерная обработка команд, позволяющая выполнять одновременно по крайней мере операции выборки и выполнения. Оба приведенных примера являются образцами параллельного выполнения функций.
По мере развития компьютерных технологий и уменьшения стоимости аппаратного обеспечения разработчики компьютеров находили все больше возможностей реализации параллелизма. Обычно это делалось для повышения производительности, а в некоторых случаях — для повышения надежности. В данной книге исследуются два наиболее популярных подхода обеспечения одновременной работы процессоров в многопроцессорных системах: симметричная многопроцессорность (symmetric multiprocessor — SMP) и кластеры. Симметричная многопроцессорная обработка описана в этом разделе, а кластеры — в шестой части.
Архитектура SMP
Рассмотрим, каким образом архитектура SMP соотносится с общей категорией параллельных процессоров. Общепринятым методом классификации таких систем по-прежнему является систематика, в которой выделяются системы с параллельными процессорами, впервые введенная Флинном (Flynn) [FLYN72]. Флинн предложил ввести следующие классы компьютерных систем.
Архитектура с одним потоком команд и одним потоком данных (Single Instruction Single Data — SISD). На одном процессоре выполняется один поток команд; операции выполняются над данными, которые хранятся в единой области памяти.
Архитектура с одним потоком команд и многими потоками данных (Single Instruction Multiple Data — SIMD). С каждым из обрабатываемых элементов связаны хранящиеся в памяти данные, и каждая команда выполняет действия с различными наборами данных, относящимися к разным процессам. Под эту категорию подпадают векторный и матричный процессоры.
Архитектура со многими потоками команд и одним потоком данных (Multiple Instruction Single Data — MISD). Последовательность данных передается набору процессоров, каждый из которых выполняет свою последовательность команд. Такая структура еще не была реализована.
Архитектура со многими потоками команд и многими потоками данных (Multiple Instruction Multiple Data — MIMD). Несколько процессоров одновременно выполняют различные последовательности команд с различными наборами данных.
В схеме MIMD процессоры являются универсальными, потому что они должны иметь возможность обрабатывать все команды, необходимые для соответствующего преобразования данных. Дальнейшая классификация систем с архитектурой MIMD может производиться в соответствии с тем, как в них осуществляется обмен данными между процессорами (рис. 4.8). Если каждому процессору выделяется отдельная область памяти, то каждый обрабатывающий элемент является самостоятельным компьютером. Они обмениваются между собой информацией либо через специальные каналы, либо через какие-то сетевые устройства. Такие системы известны под названием кластеры (clusters) или мультикомпьютеры. Если процессоры совместно используют общую память, то каждый из них имеет доступ к программам и данным, которые там хранятся. Процессоры могут обмениваться информацией через эту память. Такие системы известны под названием многопроцессорных систем с общей памятью (shared-memory multiprocessor).
Параллельный процессор
Рис. 4.8. Архитектуры систем с параллельными процессорами
Одна из общих классификаций многопроцессорных систем основана на том, как процессы распределяются между процессорами. Два главных подхода — выделение основных и подчиненных процессоров и симметричная многопроцессорная обработка. В архитектуре с ведущим и ведомыми процессорами (muster/slave architecture) ядро операционной системы всегда выполняется на специально выделенном процессоре. На других процессорах могут выполняться только пользовательские программы и, возможно, утилиты операционной системы. Ведущий процессор отвечает за планирование процессов или потоков. Если выполняющемуся на ведомом процессоре процессу или потоку понадобится какой-нибудь системный сервис (например, вызов процедуры ввода-вывода), он должен будет послать запрос основному процессору, а затем ждать, пока сервисная программа не закончит свою работу. Такой подход довольно прост, и для его реализации достаточно немного усовершенствовать операционную систему, предназначенную для однопроцессорных многозадачных систем. Разрешение конфликтов упрощается, благодаря тому что всей памятью и всеми ресурсами ввода-вывода управляет один процессор. Этот подход имеет ряд недостатков.
Сбой в работе основного процессора влечет за собой отказ всей системы.
Основной процессор может тормозить работу всей системы, так как только на нем должны производиться все действия по планированию и управлению процессами.
В симметричной многопроцессорной системе (symmetric multiprocessor) ядро может выполняться на любом процессоре; как правило, каждый процессор сам планирует свою работу, извлекая имеющийся в наличии процесс или поток из накопителя. Ядро может быть выполнено в виде многих процессов или многих потоков; при этом разные его части способны работать параллельно. Симметричный подход несколько усложняет архитектуру операционной системы. Нужно принять меры предосторожности, чтобы два процессора не выбрали один и тот же процесс или чтобы процесс каким-нибудь образом не выпал из очереди. Необходимо применять специальные методы для разрешения запросов одного и того же ресурса различными процессами и синхронизации запросов.
Симметричные мультипроцессоры и кластеры имеют сложную архитектуру. Для их разработки нужно решать вопросы, связанные с физической организацией, структурами взаимосвязей, обменом информацией между процессорами, архитектурой операционной системы и обеспечением прикладными программами. Обсуждая такие системы в данном разделе и далее, в главе 13, "Распределенные вычисления, архитектура клиент/сервер и кластеры", мы затрагиваем в основном вопросы архитектуры операционных систем. Однако и здесь, и позже мы вскользь коснемся вопросов аппаратного устройства таких компьютерных систем.
Организация симметричной многопроцессорной системы
На рис. 4.9 проиллюстрирована общая архитектура симметричной многопроцессорной системы. В ней имеется несколько процессоров, каждый из которых содержит свой собственный управляющий модуль, арифметико-логическое устройство и свои регистры. Каждый из процессоров имеет доступ к общей основной памяти и устройствам ввода-вывода. Этот доступ осуществляется с помощью некоторого механизма взаимодействия; традиционно в роли такого механизма выступает общая шина. Процессоры могут обмениваться между собой информацией посредством общей памяти (т.е. с помощью сообщений и информации о состоянии, хранящихся в общем адресном пространстве). Кроме того, процессоры могут иметь возможность непосредственного обмена сигналами. Память зачастую имеет организацию, позволяющую осуществлять одновременный множественный доступ к ее отдельным блокам.
Как правило, в современных машинах процессоры имеют по крайней мере один уровень собственного кэша. Его использование вносит новые аспекты в рассмотрение архитектуры операционных систем. Поскольку в каждом локальном кэше хранится образ какой-то части основной памяти, то в результате изменения слова в одном кэше соответствующее слово в другом кэше может оказаться неверным. Чтобы предотвратить такую ситуацию, все процессоры, в кэше которых содержится данное слово, должны быть извещены о необходимости изменить его. Эта проблема известна как проблема когерентности кэшей и относится скорее к аппаратному обеспечению, чем к операционной системе.2
Рис. 4.9. Архитектура симметричной многопроцессорной системы
Архитектура многопроцессорных операционных систем
Операционная система, предназначенная для симметричной многопроцессорной системы, управляет процессорами и другими ресурсами компьютера таким образом, чтобы с точки зрения пользователя многопроцессорная система выглядела так же, как и многозадачная однопроцессорная. Пользователь может создавать приложения с использованием нескольких процессов или нескольких потоков в процессах, не заботясь о том, какое количество процессоров будет доступно — один или несколько. Таким образом, многопроцессорная операционная система должна выполнять все функции многозадачной системы, а также обладать дополнительными возможностями по распределению вычислений среди процессоров. В число особенностей архитектуры такой операционной системы входят следующие.
Одновременные параллельные процессы или потоки. Чтобы несколько различных процессов могли одновременно выполнять один и тот же код ядра, он должен быть реентерабельным. При выполнении несколькими процессорами одного и того же кода ядра (или разных его частей) необходима организация управления таблицами и управляющими структурами ядра, чтобы избежать взаимоблокировок или неправильного выполнения операции.
Планирование. Планирование может выполняться на любом из процессоров, поэтому необходимо предусмотреть механизм, позволяющий избежать конфликтов. При использовании многопоточности на уровне ядра несколько потоков одного и того же процесса могут выполняться на разных процессорах. Планирование в многопроцессорных системах рассматривается в главе 10, "Многопроцессорное планирование и планирование реального времени".
Синхронизация. В ситуации, когда несколько активных процессов имеют возможность доступа к совместным адресным пространствам или ресурсам ввода-вывода, необходимо позаботиться об их эффективной синхронизации. Синхронизация — это средство, обеспечивающее реализацию взаимоисключений и упорядочение событий. Общепринятым механизмом синхронизации в многопроцессорных операционных системах являются блокировки, описанные в главе 5, "Параллельные вычисления: взаимоисключения и многозадачность".
Управление памятью. Система управления памятью в многопроцессорной системе должна быть способна разрешать все проблемы, возникающие в однопроцессорных машинах, а кроме того, операционная система должна уметь использовать возможности, предоставляемые аппаратным обеспечением, например многопортовую память. Механизмы страничной организации памяти разных процессоров должны быть скоординированы, чтобы обеспечить согласованность работы в ситуации, когда несколько процессоров используют одну и ту же страницу или один и тот же сегмент и принимают решение по вопросу замещения страниц.
Надежность и отказоустойчивость. При отказе одного из процессоров операционная система должна обеспечить продолжение корректной работы системы. Планировщик операционной системы (как и другие ее части) должен получить информацию о потере одного из процессоров и соответствующим образом перестроить свои управляющие таблицы.
Поскольку при описании архитектуры многопроцессорной операционной системы, как правило, рассматриваются те же вопросы (с добавлением некоторых других), что и при описании устройства однопроцессорной операционной системы, мы не будем останавливаться на многопроцессорных операционных системах отдельно. Вместо этого по ходу изложения материала книги будем обращаться к вопросам, являющимся специфичными для многопроцессорных систем.
