Среды для параллельной обработки

⇐ ПредыдущаяСтр 9 из 12Следующая ⇒

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

3.1.1. Мультипрограммная среда. В мультипрограммной (или многозадачной) среде несколько задач разделяют единственный процессор. Виртуальный параллелизм обеспечивается операционной системой, которая управляет выделением процессора для отдельных задач, так что создается иллюзия, будто у каждой задачи есть свой процессор. Пример мультипрограммной среды приведен на рис. 3.1. Здесь изображены плата процессора (ЦП) и плата памяти (их может быть несколько). В памяти хранятся коды и данные каждой задачи, а также самой операционной системы. Платы соединены между собой системной шиной. В примере система включает также два устройства ввода/вывода, дисплей и датчик, все они подключаются к шине с помощью интерфейсных карт, на каждой из которых имеется контроллер устройства.

Рис. 3.1. Мультипрограммная среда (с одним процессором)

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

Рис. 3.2. Симметричная мультипроцессорная среда

3.1.3. Распределенная среда. На рис.3.3 показана типичная распределенная среда, где есть несколько узлов, связанных между собой сетью. Каждый узел – это компьютер с собственной локальной памятью, который обычно представляет собой мультипрограммную (см. рис. 3.1) или симметричную мультипроцессорную (см. рис. 3.2) среду. Кроме того, в каждом узле имеется сетевая карта. Важным отличием распределенной среды является то, что у узлов нет общей памяти. Следовательно, распределенное приложение состоит из параллельных процессов, работающих в разных узлах. Каждый процесс может иметь несколько потоков, исполняемых в том же узле. Поскольку разделяемой памяти нет, то процессы в разных узлах должны обмениваться информацией, посылая сообщения по сети.

Рис. 3.3. Распределенная среда

3.2. Поддержка исполнения в мультипрограммной

и мультипроцессорной средах

Поддержка исполнения параллельных вычислений реализуется:

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

– системой времени исполнения в языке программирования, поддерживающем параллелизм;

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

В языках, ориентированных на последовательное программирование, например С, C++, Pascal и Fortran, нет встроенной поддержки параллелизма. Поэтому при разработке параллельных многозадачных приложений на этих языках приходится прибегать к помощи ядра или библиотеки потоков.

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

3.2.1. Сервисы операционной системы. Ядро операционной системы обычно предоставляет следующие сервисы:

– вытесняющее планирование с приоритетами. Задача с наивысшим приоритетом исполняется, как только она будет готова, – например, если ее активизирует прерывание ввода/вывода;

– межзадачную коммуникацию посредством сообщений;

– взаимное исключение с помощью семафоров;

– синхронизацию по событию с использованием сигналов. Вместо этого для синхронизации могут применяться сообщения;

– обработку прерываний и базовые сервисы ввода/вывода;

– управление памятью. Эта подсистема отвечает за отображение виртуальной памяти каждой задачи на физическую память.

В качестве примеров широко распространенных систем с поддержкой параллелизма в ядре можно назвать несколько версий UNIX (в том числе Linux, Solaris и AIX), Windows 98, Windows NT и Windows 2000 [13, 16].

Если имеется поддержка в ядре, то операции send message и receive message для обмена сообщениями, а также wait и signal для синхронизации по событию реализуются как прямые вызовы ядра. Взаимно исключающий доступ к критическим секциям обеспечивается операциями над семафорами acquire и release, которые также предоставляет ядро.

3.2.2. Стандарт POSIX. POSIX (Portable Operating System Interface Standard – стандарт переносимого интерфейса операционной системы) – это стандарт разработки программного обеспечения операционных систем, принятый IEEE. Обычно его называют POSIX 1003. POSIX основан на операционной системе UNIX – наиболее распространенной переносимой ОС. POSIX 1003.1 определяет базовые сервисы операционной системы, POSIX 1003.b – расширения для режима реального времени, а POSIX 1003.1с – расширения для параллельной обработки.

Стандарт POSIX 1003.1 задает библиотечные функции, которые должна поддерживать любая POSIX-совместимая система UNIX, например open, read и fork. POSIX 1003.1b определяет стандартный интерфейс операционной системы реального времени: системные вызовы, списки параметров и информацию о состоянии, возвращаемую каждым вызовом.

В стандарте POSIX 1003.1b указаны следующие сервисы:

1. Сервисы для управления параллельными задачами. Следующие три сервиса предоставляют средства для обмена информацией между задачами и для синхронизации:

– двоичные семафоры;

– сигналы реального времени;

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

– вытесняющее планирование с приоритетами.

2. Сервисы времени.

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

– часы и таймеры реального времени.

3. Сервисы управления памятью:

– захват памяти задачей (см. следующий раздел);

– файлы, проецируемые на память, и разделяемая память.

4. Cервисы ввода/вывода:

– синхронный ввод/вывод;

– асинхронный ввод/вывод. Этот сервис необходим для реализации перекрытия между процессорными вычислениями и вводом/выводом.

Стандарт POSIX 1003.1с добавляет к POSIX спецификацию параллельных потоков, которые позволяют программе запускать несколько экземпляров процедуры, выполняемых в раздельных потоках управления (задачах). Исполняемая программа представляет собой тяжеловесный процесс, имеющий собственное адресное пространство. Поток внутри него – это облегченный процесс.

В терминологии POSIX тяжеловесные процессы называются просто процессами, а облегченные процессы – потоками (thread). Все потоки внутри данного процесса функционируют в одном и том же адресном пространстве.

3.2.3. Операционные системы реального времени. Большинство систем реального времени поддерживают ядро или микроядро. Рассмотрим требования к операционной системе реального времени. Итак, операционная система реального времени должна:

– поддерживать многозадачность;

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

– предоставлять механизмы синхронизации и обмена информацией между задачами;

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

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

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

Существует много специализированных операционных систем реального времени, в том числе pSOS, VRTX и iRMX. Растет также число систем реального времени, совместимых со стандартом POSIX: это, например, LynxOS, QNX и HP-RT. Кроме того, есть системы, доводящие Windows NT до уровня системы реального времени: RTX, INTime и Hyperkernel [16].

Планирование задач

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

3.3.1. Алгоритмы планирования задач. Цель циклического алгоритма планирования – обеспечить справедливое выделение ресурсов. Задача ставится в очередь, поддерживающую принцип «первым пришел – первым обслужен» (FIFO). Задаче, находящейся в начале списка готовых, назначается процессор, которым она может владеть в течение фиксированного промежутка времени, называемого квантом. Если квант времени истек до того, как задача приостановилась сама (например, в ожидании завершения ввода/ вывода или сообщения), то ее приостанавливает ядро, после чего задача помещается в конец списка готовых. Затем ЦП выделяется другой задаче, оказавшейся в начале списка.

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

3.3.2. Состояния задач. Рассмотрим различные состояния, которые проходит задача с момента создания до момента завершения (рис. 3.4). Эти состояния поддерживаются многозадачным ядром, где применяется алгоритм вытесняющего планирования с приоритетами.

Новая задача сразу оказывается в состоянии «Готова» и помещается в список готовых. Когда она передвигается в начало данного списка, ей выделяется ЦП, и задача переходит в состояние «Исполняется». Потом она может быть вытеснена другой задачей и снова окажется в состоянии «Готова»; в этот момент операционная система перенесет ее в нужное место в списке готовых.

Случается и так, что находящаяся в состоянии «Исполняется» задача будет заблокирована и перейдет в то или иное состояние блокировки. Блокировка вызывается ожиданием завершения ввода/вывода, ожиданием сообщения от другой задачи или ожиданием разрешения войти в критическую секцию. Заблокированная задача перейдет в состояние «Готова», как только будет устранена причина блокировки.

Рис. 3.4. Диаграмма состояний параллельной задачи

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

В мультипроцессорной среде с разделяемой памятью копия ядра обычно выполняется на каждом процессоре. Процессор выбирает задачу, находящуюся в начале списка готовых. Взаимно исключающий доступ к списку обеспечивает аппаратный семафор, который обычно реализуется с помощью команды Test and Set Lock (проверить и установить замок). Таким образом, одна и та же задача может в разные моменты времени исполняться на разных процессорах. В некоторых мультипроцессорных средах потоки одного многопоточного процесса могут параллельно выполняться на разных процессорах.

Вопросы ввода/вывода в операционной системе

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

3.4.1. Контроллеры устройств. Устройства ввода/вывода общаются с операционной системой при помощи контроллеров, которые находятся на интерфейсных платах устройства (см. рис. 3.1 и 3.2). Центральный процессор работает именно с контроллером, а не с самим устройством. У контроллера есть набор регистров, используемых для обмена информацией с ЦП. В некоторых компьютерах имеются специальные команды для доступа к регистрам контроллера. Если же применяется отображение устройств на память, то регистры контроллера представляются в виде обычных ячеек адресного пространства.

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

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

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

Рис. 3.5. Организация контроллера устройства ввода/вывода

3.4.2. Обработка прерываний. Если ввод/вывод управляется прерываниями, то при поступлении входных данных и завершении операции вывода генерируется прерывание. Есть множество способов, но наиболее распространены ввод/вывод с управлением от программы и ввод/вывод, запускаемый программой. В первом случае прерывание обычно генерируется после чтения или записи каждого символа, во втором между устройством ввода/вывода и основной памятью помещается устройство прямого доступа к памяти (Direct Memory Access – DMA), управляющее передачей блоков данных между ними. По завершении передачи устройство DMA генерирует прерывание.

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

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

Рассмотрим обмен данными между задачей и контроллером устройства посредством описанных выше регистров контроллера. В случае ввода драйвер устройства ввода посылает контроллеру команду прочитать символ, а затем приостанавливается до тех пор, пока снова не будет активизирован обработчиком прерывания. Контроллер получает символ от внешнего устройства, помещает его в буфер ввода, устанавливает в регистре состояния бит «буфер ввода полон» и генерирует прерывание. Обработчик получает это прерывание и пробуждает задачу драйвера. Драйвер считывает символ из буфера ввода и устанавливает в регистре состояния бит «буфер ввода пуст».

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

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

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

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

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

⇐ Предыдущая 3 4 5 6 7 8910 11 12 Следующая ⇒