ПОД (пособие) (1184372), страница 41
Текст из файла (страница 41)
Этот прием называют взаимнымисключением.Простейший способ обеспечить взаимное исключение - позволить процессу, находящемусяв критической секции, запрещать все прерывания. Однако этот способ непригоден, так какопасно доверять управление системой пользовательскому процессу; он может надолгозанять процессор, а при крахе процесса в критической области крах потерпит вся система,потому что прерывания никогда не будут разрешены.Другим способом является использование блокирующих переменных. С каждымразделяемым ресурсом связывается двоичная переменная, которая принимает значение 1,если ресурс свободен (то есть ни один процесс не находится в данный момент вкритической секции, связанной с данным процессом), и значение 0, если ресурс занят.
Нарисунке 2.4 показан фрагмент алгоритма процесса, использующего для реализациивзаимного исключения доступа к разделяемому ресурсу D блокирующую переменную F(D).Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если онзанят, то проверка циклически повторяется, если свободен, то значение переменной F(D)устанавливается в 0, и процесс входит в критическую секцию. После того, как процессвыполнит все действия с разделяемым ресурсом D, значение переменной F(D) сноваустанавливается равным 1.Если все процессы написаны с использованием вышеописанных соглашений, то взаимноеисключение гарантируется. Следует заметить, что операция проверки и установкиблокирующей переменной должна быть неделимой.
Поясним это. Пусть в результатепроверки переменной процесс определил, что ресурс свободен, но сразу после этого, неуспев установить переменную в 0, был прерван. За время его приостановки другой процессзанял ресурс, вошел в свою критическую секцию, но также был прерван, не завершивработы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он,считая ресурс свободным, установил признак занятости и начал выполнять своюкритическую секцию.
Таким образом был нарушен принцип взаимного исключения, чтопотенциально может привести к нежелаемым последствиям. Во избежание таких ситуацийв системе команд машины желательно иметь единую команду "проверка-установка", или жереализовывать системными средствами соответствующие программные примитивы,которые бы запрещали прерывания на протяжении всей операции проверки и установки.Реализация критических секций с использованием блокирующих переменных имеетсущественный недостаток: в течение времени, когда один процесс находится в критической130секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинныедействия по опросу блокирующей переменной, бесполезно тратя процессорное время. Дляустранения таких ситуаций может быть использован так называемый аппарат событий. Спомощью этого средства могут решаться не только проблемы взаимного исключения, но иболее общие задачи синхронизации процессов.
В разных операционных системах аппаратсобытий реализуется по своему, но в любом случае используются системные функциианалогичного назначения, которые условно назовем WAIT(x) и POST(x), где x идентификатор некоторого события. На рисунке 2.5 показан фрагмент алгоритма процесса,использующего эти функции. Если ресурс занят, то процесс не выполняет циклическийопрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие,заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активныйпроцесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процессожидает события D. Процесс, который в это время использует ресурс D, после выхода изкритической секции выполняет системную функцию POST(D), в результате чегооперационная система просматривает очередь ожидающих процессов и переводит процесс,ожидающий события D, в состояние ГОТОВНОСТЬ.Общий семафор - это целочисленная переменная, над которой разрешены только двенеделимые операции P и V.
Аргументом у этих операций является семафор. Определятьсемантику этих операций можно только для семафоров - положительных чисел, иливключать и отрицательный диапазон. Операции могут быть определены так:P(S) - декремент и анализ семафораS := S-1IF (S < 0) THEN <блокировка текущего процесса>ENDIFV(S) - инкремент семафораS := S+1IF S <= 0 THEN <запустить блокированный процесс>ENDIFP и V операции неделимы: в каждый момент только один процесс может выполнять Р или Vоперацию над данным семафором. Если семафор используется как счетчик ресурсов, то:S >= 1 - есть некоторое количество (S) доступных ресурсов,S = 0 - нет доступного ресурса,S < 0 - один или несколько (S) процессов находятся в очереди к ресурсу.Вводится, также, операция инициализации семафора (присвоение начального значения).Общий семафор - избыточный, т.к.
его можно реализовать через двоичные семафоры,которые принимают только два значения 0,1.Семафоры позволяют:- синхронизировать работу процессов,- управлять распределением ресурсом (использованием положительного диапазоназначений семафора как счетчика ресурсов) ,- организовывать очередь блокированных процессов (отрицательные значения семафорапоказывают число блокированных процессов).В системах программирования вводится специальный тип данных, определяющийструктуру семафора, например, SEMAPHOR,SIGNAL,GETA.Использование семафоровbegin integer S; S:=1;parbegintask1: begindo while (true)P(S);<критический участок 1>;131V(S);<обычный участок>;enddoend;task2: begindo while (true)P(S);<критический участок 2>;V(S);<обычный участок>;enddoendparendendУпорядоченные секции. Распараллелить цикл, используяупорядоченные секции и семафоры:DO I=2,NA(I) = 2*A(I) + C(I)B(I) = C(I)*sin(X(I))Y(I) = Y(I-1) + X(I)D(I) = P(I)*B(I)/A(I)ENDDOЧто-то на темуДиректива синхронизации OpenMP:ORDERED ...
END ORDERED //видиимо,это и есть упорядоченные секци… прим. А.Е.Определяет блок внутри тела цикла, который должен выполняться в том порядке, в которомитерации идут в последовательном цикле. Может использоваться для упорядочения выводаот параллельных нитей.Ограничения на использования OrderedМожет появляться только в динаических расширениях следующих деректив:DO or PARALLEL DO (Fortran)for or parallel for (C/C++)В упорядоченную секцию допускается только одна нить в единицу времени.Переходы на другие процессоры внутри Ordered-блока запрещены.Итерация цикла не может исполнять одну и ту же Odered-директиву более 1 раза и должнане исполнять более 1 Ordered-директивы.Цикл, имеющий внутри Ordered-директиву должен быть циклом, определенным как OrderedDO I=2,NA(I) = 2*A(I) + C(I)B(I) = C(I)*sin(X(I))Y(I) = Y(I-1) + X(I)D(I) = P(I)*B(I)/A(I)ENDDOИногда, почти полностью распараллеливающийся по данным,алгоритм имеетединственную зависимость данных, которая на векторных машинах может потребоватьрасщепления цикла, чтобы изолировать зависимость.Например:132DO I = 1,NA(I) = EXP(SIN(B(I))) * EXP(COS(B(I)))C(I) = (D(I) + E(I)) / F(I) * A(I)X(I) = S * X(I-1) + C(I)Z(I) = X(I) * Y(I) + EXP(Z(I))ENDDOОператор присваивания X(I) включает рекурсию, что запрещает векторизацию.
Обычнолибо компилятор, либо программист выделит этот оператор в отдельный скалярный цикл,чтобы позволить другим трем операторам присваивания выполняться в параллельномрежиме.Это не всегда необходимо делать при распараллеливании. Если имеется достаточноработы выше и/или ниже оператора присваивания X(I) и N достаточно велико, можнодостичь эффективного параллельного выполнения цикла путем помещения оператораприсваивания X(I) в упорядоченную критическую секцию. Она будет обеспечивать доступтолько одной нити в один и тот же момент явным или неявным замковым (lock)механизмом. В данном случае требуется выполнять итерации в таком порядке, чтобыудовлетворить требования рекурсии для вычисления X.Реальная система синхронизации для SEQCALL SETSEQ (SEQ,0)* инициализация, установка SEQ=0С$DIR DO_PARALLEL (ORDRED)DO I = 1,NA(I) = EXP(SIN(B(I))) * EXP(COS(B(I)))C(I) = (D(I) + E(I)) / F(I) * A(I)CALL WAITSEQ (SEQ,I-1)* ждать, пока SEQ будет равно I-1X(I) = S * X(I-1) + C(I)CALL POSTSEQ (SEQ,I)* установить SEQ в IZ(I) = X(I) * Y(I) + EXP(Z(I))ENDDOСемантика (для случая четырех процессоров):Инициализируются вычисления первых четырех итераций в заданном порядке на четырехпараллельных процессорах.
Все четыре процессора вычисляют свои A(I),C(I)одновременно. Первый процессор выполнит для I=1 присваивание X(1), в то время какдругие ждут. Первый процессор для I=1 вычисляет Z(1), в то время как X(2) вычисляетсявторым процессором для I=2. Первый процессор начинает вычислять новую итерацию дляI=5, в то время как другие три процессора проходят сквозь критическую секцию такжеупорядочено.Теперь, если работа по выполнению цикла хорошо сбалансирована, первый процессордля I=5 достигает точки WAITSEQ как раз тогда, когда четвертый процессор для I=4закончит POSTSEQ. С этой точки все процессоры работают без простоя, пока они недостигнут последние четыре итерации цикла.133Системы передачи сообщений.
Фортран-GNS.Статический и динамический способы образования параллельныхпроцессов."Процесс - группа ячеек памяти, содержимое которых меняется по определенным правилам.Эти правила описываются программой, которую интерпретирует процессор." /ЦикритзисД./.Вычислительный процесс можно рассматривать как последовательность команд ЭВМ,которая работает с данными ей ресурсами. (Задача, задание, процесс, нить, TASK).
Так, намикропроцессоре могут работать одновременно несколько независимых процессов: счетвычислительной задачи, редактирование текстов и т.д. Далее рассматриваютсявычислительные процессы, одновременно выполняющиеся на нескольких процессорах длярешения общей задачи. Работа такой задачи может начинаться с порождения главногопроцесса, который при работе может порождать другие процессы динамически.
Этипроцессы могут работать параллельно с главной и также порождать другие процессы.Другим способом порождения процессов является статический способ, когда производитсяодновременная инициализация на всех процессорах одинаковых процессов (SPMD – SingleProgram Multiple Data). Эти процессы опрашивают состояние решающего поля инастраиваются на выполнение своей части вычислений.(Они могут узнать: сколько ихпорождено, свои уникальные, внутренние имена, и т.д.)Процессы, работающие на равных правах (не вызовы процедур и не процессы, связанныепонятиями "главная-подчиненная"), иногда называемые сопроцессами, могут выполнятьсяпараллельно и при этом общаться друг с другом - не часто (слабо связанные процессы).Требования с системам программирования методом передачисообщений.Кое-что…Основной моделью параллельного выполнения программы на кластере является модельпередачи сообщений .В этой модели параллельная программа представляет собой систему процессов,взаимодействующих посредством передачи сообщений .Можно выбрать модель передачи сообщений и в качестве модели программирования.При этом возможны три способа построения языка программирования:·Расширение стандартного языка последовательного программированиябиблиотечными функциями (например, Фортран+MPI);·Расширение стандартного языка последовательного программирования специальнымиконструкциями (например, Fortran-GNS);·Разработка нового языка (например, Occam).Однако модель передачи сообщений является слишком низкоуровневой, непривычной инеудобной для программистов, разрабатывающих вычислительные программы.
Оназаставляет программиста иметь дело с параллельными процессами и низкоуровневымипримитивами передачи сообщений .Поэтому вполне естественно, что прикладной программист хотел бы получить инструмент,автоматически преобразующий его последовательную программу в параллельнуюпрограмму для кластера. К сожалению, такое автоматическое распараллеливаниеневозможно в силу следующих причин.134Во-первых, поскольку взаимодействие процессоров через коммуникационную системутребует значительного времени (латентность – время самого простого взаимодействия велика по сравнению со временем выполнения одной машинной команды), товычислительная работа должна распределяться между процессорами крупными порциями.Совсем другая ситуация была на векторных машинах и на мультипроцессорах, гдеавтоматическое распараллеливание программ на языке Фортран реально использовалось идавало хорошие результаты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
