Параллельные структуры программ. Организация параллельных вычислений.

Я уже показал вам, что ядро Linux (на 32-битной архитектуре) делит виртуальную память в отношении 3:1 - 3 GB виртуальной памяти для пространства пользователя и 1 GB для пространства ядра. Код ядра и его структуры данных должны размещаться в этом 1 GB адресного пространства, но даже еще большим потребителем этого адресного пространства является виртуальное отображение физической памяти.

Это происходит потому, что ядро не может манипулировать памятью, если она не отображена в его адресное пространство. Таким образом, максимальным количеством физической памяти, которое может обработать ядро, является объем памяти, который мог бы отобразиться в виртуальное адресное пространство ядра минус объем, необходимый для отображения самого кода ядра. В итоге Linux на основе x86-системы смогла бы работать с объемом менее 1 GB физической памяти. И это максимум.

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

· ZONE_DMA (0-16 MB): Диапазон памяти, расположенный в нижней области памяти, чего требуют некоторые устройства ISA/PCI.

· ZONE_NORMAL (16-896 MB): Диапазон памяти, который непосредственно отображается ядром в верхние участки физической памяти. Все операции ядра могут выполняться только с использованием этой зоны памяти; таким образом, это самая критичная для производительности зона.

· ZONE_HIGHMEM (896 MB и выше): Оставшаяся доступная память системы не отображается ядром.

Концепция узла реализована в ядре при помощи структуры struct pglist_data. Зона описывается структурой struct zone_struct. Физический страничный фрейм представлен структурой struct Page, и все эти структуры хранятся в глобальном массиве структур struct mem_map, который размещается в начале NORMAL_ZONE. Эти основные взаимоотношения между узлом, зоной и страничным фреймом показаны на рисунке 4.

Рисунок 4. Взаимоотношения между узлом, зоной и страничным фреймом

Зона верхней области памяти появилась в системе управления памятью ядра тогда, когда были реализованы расширение виртуальной памяти Pentium II (для доступа к 64 GB памяти средствами PAE - Physical Address Extension - на 32-битных системах) и поддержка 4 GB физической памяти (опять же, на 32-битных системах). Эта концепция применима к платформам x86 и SPARC. Обычно эти 4 GB памяти делают доступными отображение ZONE_HIGHMEM в ZONE_NORMAL посредством kmap(). Обратите внимание, пожалуйста, на то, что не желательно иметь более 16 GB RAM на 32-битной архитектуре даже при разрешенном PAE.

(PAE - разработанное Intel расширение адресов памяти, разрешающее процессорам увеличить количество битов, которые могут быть использованы для адресации физической памяти, с 32 до 36 через поддержку в операционной системе приложений, использующих Address Windowing Extensions API.)

Управление этой зоной физической памяти выполняется распределителем (allocator) зоны. Он отвечает за разделение памяти на несколько зон и рассматривает каждую зону как единицу для распределения. Любой конкретный запрос на распределение использует список зон, в которых распределение может быть предпринято, в порядке от наиболее предпочтительной к наименее предпочтительной.

Например:

· Запрос на пользовательскую страницу должен быть сначала заполнен из "нормальной" зоны (ZONE_NORMAL);

· если завершение неудачно - с ZONE_HIGHMEM;

· если опять неудачно - с ZONE_DMA.

Список зон для такого распределения состоит из зон ZONE_NORMAL, ZONE_HIGHMEM и ZONE_DMA в указанном порядке. С другой стороны, запрос DMA-страницы может быть выполнен из зоны DMA, поэтому список зон для таких запросов содержит только зону DMA.

Параллельные структуры программ. Организация параллельных вычислений.

1. Независимые и взаимодействующие вычислительные процессы.

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

3. Реализации параллельных вычислений.

1. Независимые и взаимодействующие вычислительные процессы

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

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

Итак, параллельными называются такие последовательные вычислительные процессы, которые одновременно находятся в каком-нибудь активном состоянии. Два параллельных процесса могут быть независимыми (independed processes) либо взаимодействующими (cooperating processes).

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

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

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

Пример.

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

Таблица 1

Поскольку при мультипрограммировании процессы могут иметь различные скорости исполнения, то может иметь место любая последовательность выполнения операций во времени. Например, если сначала будут выполнены все операции процесса Р1, а уже потом — все операции процесса Р2 (рис. 1) или, наоборот, сначала — операции 4-6, а затем — операции 1-3, то в итоге переменная X получит значение, равное X + 2.

Рис. 1.

Однако если в промежуток времени между выполнением операций 1 и 3 будет выполнена хотя бы одна из операций 4-6 (рис. 2), то значение переменной X после выполнения всех операций будет не (X + 2), а (Х + 1).

Рис. 2

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

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

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

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

Допустим, что «поставщик» — это процесс, который отправляет порции информации (сообщения) другому процессу, имя которого — «потребитель». Например, некоторая задача пользователя, порождающая данные для вывода их на печать, может выступать как поставщик, а системный процесс, который выводит эти строки на устройство печати, — как потребитель. Один из методов, применяемых при передаче сообщений, состоит в том, что заводится пул (pool) свободных буферов, каждый из которых может содержать одно сообщение. Причем длина сообщения может быть произвольной, но ограниченной размером буфера. В этом случае между процессами «поставщик» и «потребитель» будет существовать очередь заполненных буферов, содержащих сообщения. Когда поставщик хочет послать очередное сообщение, он добавляет в конец этой очереди еще один буфер. Потребитель, чтобы получить сообщение, забирает из очереди буфер, который стоит в ее начале. Такое решение, хотя и кажется тривиальным, требует, чтобы поставщик и потребитель синхронизировали свои действия. Например, они должны следить за количеством свободных и заполненных буферов. Поставщик может передавать сообщения только до тех пор, пока имеются свободные буферы. Аналогично, потребитель может получать сообщения, только если очередь не пуста. Ясно, что для учета заполненных и свободных буферов нужны разделяемые переменные, поэтому, так же как и для конкурирующих процессов, для сотрудничающих процессов тоже возникает необходимость во взаимном исключении. Таким образом, до окончания обращения одной задачи к общим переменным следует исключить возможность обращения к ним другой задачи. Эта ситуация и называется взаимным исключением. Другими словами, при организации различного рода взаимодействующих процессов приходится организовывать взаимное исключение и решать проблему корректного доступа к общим переменным (критическим ресурсам). Те места в программах, в которых происходит обращение к критическим ресурсам, называются критическими секциями (Critical Section, CS). Решение проблемы заключается в организации такого доступа к критическому ресурсу, при котором только одному процессу разрешается входить в критическую секцию. Данная задача только на первый взгляд кажется простой, ибо критическая секция, вообще говоря, не является последовательностью операторов программы, а является процессом, то есть последовательностью действий, которые выполняются этими операторами. Другими словами, несколько процессов могут выполнять критические секции, использующие одну и ту же последовательность операторов программы.

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

Требования к критическим секциям:

в любой момент времени только один процесс должен находиться в своей критической секции;

ни один процесс не должен бесконечно долго находиться в своей критической секции;

ни один процесс не должен бесконечно долго ожидать разрешение на вход в свою критическую секцию. В частности:

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

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

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