Процесс параллельной обработки данных

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

Северо - Казахстанский государственный университет им. М. Козыбаева

Факультет информационных технологии

Кафедра Информационных систем

Тема

Процесс параллельной обработки данных

Выполнила: Махкамбаева А.С.

Проверил: Касимов И. Р.

Петропавловск, 2014

Введение

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

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

В 1967 году Джин Амдал сформулировал закон ограничения роста производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время ее выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента». Согласно этому закону, ускорение выполнения программы за счет распараллеливания её инструкций ограничено временем, необходимым для выполнения её последовательных инструкций.

Классификация по Флинну

процесс синхронизация доступ планирование

В основе классификации лежат два понятия: потоки команд и потоки данных. Система с N процессорами имеет N счетчиков команд и, следовательно, N потоков команд.

SISD (Single Instruction, Single Data) -- архитектура компьютера, в которой один процессор выполняет один поток команд, оперируя одним потоком данных. Для данного класса возможен только псевдопараллелизм.

SIMD (Single Instruction, Multiple Data) -- архитектура компьютера, позволяющая обеспечить параллелизм на уровне данных. Основная идея подхода, основанного на параллелизме данных, заключается в том, что одна операция выполняется сразу над всеми элементами массива данных. Эти системы обычно имеют большое количество процессоров, от 1024 до 16384, которые могут выполнять одну и ту же инструкцию, созданную единственным блоком управления, относительно разных данных. В любой момент в каждом процессоре выполняется одна и та же команда, но обрабатываются различные данные. Реализуется синхронный параллельный вычислительный процесс.

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

MIMD (Multiple Instruction, Multiple Data) -- архитектура компьютера, где несколько независимых процессоров работают как часть большой системы. Обработка разделена на несколько потоков (обеспечивается параллелизм), каждый с собственным аппаратным состоянием процессора, в рамках единственного определённого программным обеспечением процесса или в пределах множественных процессов.

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

OpenMP

OpenMP (Open Multi-Processing) -- открытый стандарт для распараллеливания программ на языках С, С++ и Фортран. Описывает совокупность команд, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью. OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» поток создает набор подчиненных потоков и задача распределяется между ними.

Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка -- прагм. Программа на C должна включать файл "omp.h".

Следующий цикл складывает массивы «a» и «b» поэлементно. Все, что требуется для параллельного выполнения в этом случае - одна прагма, вставленная непосредственно перед циклом.

#pragma omp parallel for

for (i=0; i < numPixels; i++)

{

c[i] = a[i]+b[i];

}

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

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

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

#pragma omp parallel for

for (i=2; i < 10; i++)

{

factorial[i] = i * factorial[i-1];

}

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

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

MPI

MPI (Message Passing Interface) -- программный интерфейс для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. В первую очередь MPI ориентирован на системы с распределенной памятью. Существуют реализации для языков Фортран, С и С++.

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

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

Для C, общий формат имеет вид

rc = MPI_Xxxxx(parameter, ... );

Заметим, что регистр здесь важен. Например, MPI должно быть заглавным, так же как и первая буква после подчеркивания. Все последующие символы долны быть в нижнем регистре. Переменная rc - есть некий код возврата, имеющий целый тип. В случае успеха, он устанавливается в MPI_SUCCESS. Программа на C должна включать файл "mpi.h".

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

Данным соответствует старт буфера, число, тип данных. Буфер - это просто память, которую компилятор выделил для переменной (часто массива) в вашей программе. Старт буфера - адрес, где данные начинаются. Например, начало массива в вашей программе. Число - количество элементов (не байтов!) данных в сообщении. Тип данных определяет размер одного элемента.

К информации «на обложке» относятся ранг в коммуникаторе - идентификатор процесса в коммуникационном поле, тег - произвольное число, которое помогает различать сообщения и сам коммуникатор, проверка которого обеспечивает передачу внутри одного коммуникационного поля.

Параллельная обработка данных

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

* делегирование («управляющий-рабочий»);

* сеть с равноправными узлами;

* конвейер;

* «изготовитель-потребитель».

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

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

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

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

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

Синхронные и асинхронные процессы

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

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

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

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

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

Межпроцессное взаимодействие

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

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

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

С системами передачи сообщения связано большое количество проблем. Например, сообщение может потеряться. Чтобы избежать потери, получатель отсылает обратно сообщение с подтверждением приема. Если отправитель не получает подтверждения через некоторое время, он отсылает сообщение еще раз.

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

Семафор -- объект, позволяющий войти в заданный участок кода (обычно - критическую секцию) не более чем n процессам.

С семафором возможны три операции:

1) init(n); - инициализация счетчика (число, переданное счетчику, является количеством процессов, которые могут одновременно обращаться к критической секции)

2) wait(); - ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу.

3) leave(); - увеличить счетчик на единицу.

Перед обращением процесса к критической секции необходимо вызвать метод wait(), после выполнения которого гарантировано, что количество процессов, одновременно обращающихся к ней не превышает n-1. Тогда процесс может продолжить работу и выполнить метод leave() после работы с критической секцией, тем самым дав знать остальным процессам, что “место освободилось”.

Если количество вызовов методов wait() и leave() не совпадает, то работа системы будет не корректной так же, как и в случае взаимной блокировки процессов - ситуации, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами:

Отладка взаимных блокировок, как и других ошибок синхронизации, усложняется тем, что для их возникновения нужны специфические условия одновременного выполнения нескольких процессов (в вышеописанном примере если бы процесс 1 успел захватить ресурс B до процесса 2, то ошибка не произошла бы).

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

Задача мьютекса -- защита объекта от доступа к нему других потоков, отличных от того, который завладел мьютексом. В каждый конкретный момент только один поток может владеть объектом, защищённым мьютексом. Если другому потоку будет нужен доступ к переменной, защищённой мьютексом, то этот поток засыпает до тех пор, пока мьютекс не будет освобождён.

Test-and-set -- простая неразрывная (атомарная) процессорная инструкция, которая копирует значение переменной в регистр, и устанавливает некое новое значение. Во время исполнения данной инструкции процессор не может прервать её выполнение и переключится на выполнение другого потока. Если используется многопроцессорная архитектура, то пока один процессор выполняет эту инструкцию с ячейкой памяти, то другие процессоры не могут получить доступ к этой ячейке.

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

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

Одним из преимуществ алгоритма является то, что он не требует специальных Test-and-set инструкций и вследствие этого он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость к случаю только с двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).

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

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

Общий принцип алгоритмом Петерсона для 2-х потоков:

Размещено на http://www.allbest.ru/

Планирование процессов

Планирование - обеспечение поочередного доступа процессов к одному процессору.

Планировщик - отвечающая за это часть операционной системы.

Алгоритм планирования без вытеснения (неприоритетный) - не требует прерывание по аппаратному таймеру, процесс останавливается только когда блокируется или завершает работу.

Алгоритм планирования с вытеснением (приоритетный) - требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.

Процессы размещаются в приоритетных очередях в соответствии со стратегией Планирования. В системах UNIX/Linux используются две стратегии планирования: FIFO (сокр. от First In First Out, т.е. первым прибыл, первым обслужен) и RR (сокр. От round-robin, т.е. циклическая).

При использовании стратегии FIFO процессы назначаются процессору в соответствии со временем поступления в очередь.

RR-планирование совпадает с FIFO-планированием с одним исключением: после истечения кванта времени процесс помещается в конец своей приоритетной очереди, и процессору назначается следующий (по очереди) процесс.

Для обеспечения параллельной работы процессов может подойти приоритетное планирование. Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом. Приоритет может быть динамический и статический. Динамический приоритет может устанавливаться так: П=1/Т, где Т- часть использованного в последний раз кванта (если использовано 1/50 кванта, то приоритет 50. Если использован весь квант, то приоритет 1).

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

Размещено на Allbest.ur