WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 |

Данный несложный алгоритм вызывает ряд вопросов, например:

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

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

// sdat. - глобальные переменные, разделяемые // всеми процессами slave_thr // и запускающим процессом main main() { // запускающая программа sdat.ntask=0 // число отрезков в глобальном стеке интервалов sdat.nactive=0 // число процессов, обрабатывающих в // данный момент один из интервалов - 15 Sem_init(sdat.sem_sum, 1) //доступ к глобальной сумме открыт Sem_init(sdat.sem_list, 1) //доступ к глобальному стеку открыт Sem_init(sdat.sem_task_present, 0) // отрезков в // глобальном стеке нет sdat.s_all=0 // Глобальная сума - переменная, // накапливающая частичные суммы PUT_INTO_GLOBAL_STACK[sdat.ntask] (A,B,fun(A),fun(B),(fun(A)+fun(B))*(B-A)/2.) sdat.ntask++ // в глобальный стек занесен первый из отрезков // откроем семафор, свидетельствующий о том, // что в глобальном стеке интервалов есть отрезки sem_post(&sdat.sem_task_present) // запуск np параллельных процессов, выполняющих функции slave_thr StartThrTask(p, slave_thr);

WaitThrTask();

// Параллельное выполнение функций slave_thr завершено J=sdat.s_all; // значение интеграла } Алг. 7. Запускающий процесс Уточним структуру интегрирующего процесса (Алг. 8).

slave_thr() { // начало цикла обработки стека интервалов while(sdat.ntask>0) { // чтение одного интервала из списка интервалов sdat.ntask-- // указатель глобального стека GET_FROM_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab) // начало цикла интегрирования одного интервала while(1) { c=(a+b)/fc=fun(c) sac=(fa+fc)*(c-a)/scb=(fc+fb)*(b-c)/sacb=sac+scb if(!BreakCond(sacb,sab)) { s+=sacb if(!sp) // локальный стек пуст break // выход из цикла интегрирования // одного интервала sp-- 16 GET_FROM_LOCAL_STACK[sp]( a, b, fa, fb, sab) } else { PUT_INTO_LOCAL_STACK[sp]( a, c, fa, fc, sac) sp++ a=c fa=fc sab=scb } // перемещение части локального стека // в общий список интервалов if((sp>SPK) && (!sdat.ntask)) { while((sp>1) && (sdat.ntask

- в конце цикла интегрирования одного интервала присутствует фрагмент переноса отрезков из локального стека в глобальный стек;

- по окончании цикла интегрирования выполняется суммирование частичных сумм, полученных всеми процессами.

Данный алгоритм неработоспособен по следующим причинам:

1. несмотря на проверку в начале цикла обработки стека интервалов (sdat.ntask>0) может возникнуть ситуация, в которой одна и та же запись будет извлечена более чем одним процессом;

2. возможно, не все частичные суммы будут добавлены к общему значению интеграла.

- 17 Рассмотрим последовательность действий, иллюстрирующую возникновение первой ошибки:

№ состояние Процесс1 Процессшага переменных 0 sdat.ntask=1 while(sdat.ntask>0) while(sdat.ntask>0) 2 sdat.ntask-3 sdat.ntask=0 sdat.ntask-4 sdat.ntask=-1 GET_OF_GLOBAL_STACK[sdat.ntask] GET_OF_GLOBAL_STACK[sdat.ntask] - чтение записи с номером -1 - чтение записи с номером -Два процесса успешно выполнили проверку наличия в глобальном стеке записей, затем первый процесс уменьшил указатель стека, ранее указывающий на первую свободную ячейку. После шага указатель стека направлен на ячейку, хранящую отрезок, что пока еще правильно. На шаге 3 второй процесс выполнил такое же действие. В результате указатель стека направлен на ячейку -1. В результате возникают сразу две проблемы: во-первых, на шаге 4 оба процесса прочтут одну и ту же запись; во-вторых, такой записи нет – она за пределами стека. Попытка чтения несуществующей записи приведет, в лучшем случае, к аварийной остановке программы, в худшем - к непредсказуемым неверным результатам.

Рассмотрим возникновение второй ошибки:

№ состояние Процесс1 Процессшага глобальных выполняемые действия выполняемые действия переменных состояние локальных переменных состояние локальных переменных 0 sdat.s_all=0 s=1 s=sdat.s_all= 0 + 1 sdat.s_all= 0 + 2 sdat.s_all= 1 или В результате выполнения указанных действий переменная sdat.s_all может получить как верное, так и не верное значение.



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

main().

Sem_init(sdat.sem_sum,1) //доступ к глобальной сумме открыт.

slave_thr().

// Начало критической секции сложения частичных сумм // sem_wait(sdat.sem_sum) sdat.s_all+=s - 18 sem_post(sdat.sem_sum) // // Конец критической секции сложения частичных сумм Алг. 9. Критическая секция накопления глобальной суммы Будем предполагать, что используемые нами семафоры являются бинарными и, в отличии от обычных переменных, могут принимать только два значения: 0 и 1, причем 1 соответствует открытому семафору, а 0 - закрытому. Инициализация семафора выполняется с помощью операции sem_init( семафор, 0 или 1 ). При выполнении над закрытым семафором операции sem_wait(семафор) процесс (или процессы), выполнивший ее, блокируется вплоть до открытия семафора.

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

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

main().

Sem_init(sdat.sem_list, 1) //доступ к глобальному стеку открыт.

slave_thr() {.while(1) { // Начало критической секции чтения из глобального // стека очередного интервала интегрирования // sem_wait(sdat.sem_list) if(sdat.ntask0) { sem_post(sdat.sem_list) // разрешить другим процессам // доступ к глобальному стеку break } sdat.ntask-- // указатель глобального стека GET_FROM_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab) sem_post(sdat.sem_list) - 19 // // Конец критической секции чтения из глобального // стека очередного интервала интегрирования.

}.

} Алг. 10. Критическая секция накопления глобальной суммы При выполнении алгоритма Алг. 10 возможна следующая последовательность действий:

№ состояние пере- Процесс1 Процессшага менных 0 sdat.ntask=1 sem_wait(sdat.sem_list) sdat.sem_list=2 sdat.ntask=1 sdat.ntask-sdat.sem_list=3 sdat.ntask=0 GET_OF_GLOBAL_STACK[0] sdat.sem_list=4 sdat.ntask=0 sem_wait(sdat.sem_list) sdat.sem_list=5 sdat.ntask=0 sem_wait(sdat.sem_list) sdat.sem_list=6 sdat.ntask=if(sdat.ntask0) sdat.sem_list= { sem_post(sdat.sem_list) break - выйти из цикла } 7 sdat.ntask=0 процесс завершил работу sdat.sem_list=В результате Процесс2 заканчивает работу раньше, чем Процесс1 полностью вычислит интеграл на заданном отрезке интегрирования. Таким образом, может оказаться, что Процесс1, после завершения Процесса2, породит некоторое количество отрезков и запишет их в глобальный стек. Процесс2 мог бы принять участие в их обработке, но не сделает этого, поскольку уже завершится к этому моменту. Обратим внимание на то, что в результате выполнения программы будет получен правильный результат - Процесс1 обработает все отрезки, но время выполнения программы будет больше, чем могло бы быть при работе двух процессов. Можно сделать вывод о том, что условие выхода из цикла обработки стека интервалов выбрано неудачно. Интегрирующие процессы не должны заканчивать работу до тех пор, пока все отрезки интервала интегрирования не будут полностью обработаны.

Отрезок интегрирования может находиться в нескольких состояниях:

- находится в глобальном стеке интервалов;

- обрабатывается некоторым интегрирующим процессом;

- 20 - находится в локальном стеке интервалов некоторого процесса;

- полностью обработан: известно значение интеграла на этом отрезке и оно прибавлено к локальной частичной сумме соответствующего процесса.

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

- функция проинтегрирована на всех отрезках, покрывающих исходный интервал интегрирования;

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

- 21 Таким образом, потребуются следующие основные общие данные:

семафоры доступа:

sdat.sem_list семафор доступа к глобальному стеку отрезков sdat.s_all семафор доступа к значению интеграла семафоры состояния:

sdat.sem_task_present семафор наличия записей в глобальном стеке отрезков переменные:

sdat.list_of_tasks глобальный стек отрезков sdat.ntask число записей в глобальном стеке отрезков указатель глобального стека отрезков sdat.nactive число активных процессов sdat.s_all значение интеграла Окончательная версия алгоритма, свободная от рассмотренных выше недостатков приведена в листинге Алг. 11. Процедуры доступа к глобальному стеку приведены в листинге Алг. 12, процедуры доступа к локальному стеку полностью аналогичны процедурам с листинга Алг. 4.





int slave_thr() { // все переменные, начинающиеся с sdat. являются глобальными, // к ним имеет доступ каждый из запущенных процессов slave_thr // и запускающая программа main // sp, s - локальные переменные процессов slave_thr sp=0 // указатель локального стека - локальный стек пуст s=0 // частичная сумма интегралов, вычисленных на отрезках, // обработанных данной копией процесса // начало цикла обработки стека интервалов while(1) { // ожидание появления в глобальном стеке интервалов для обработки sem_wait(sdat.sem_task_present) // чтение одного интервала из списка интервалов // Начало критической секции чтения из глобального // стека очередного интервала интегрирования // sem_wait(sdat.sem_list) sdat.ntask-- // указатель глобального стека GET_OF_GLOBAL_STACK[sdat.ntask](a,b,fa,fb,sab) - 22 if(sdat.ntask) sem_post(&sdat.sem_task_present) if(a<=b) // очередной отрезок не является терминальным sdat.nactive++ // увеличить число процессов, имеющих // интервал для интегрирования sem_post(sdat.sem_list) // // Конец критической секции чтения из глобального // стека очередного интервала интегрирования if(a>b) // отрезок является терминальным break // выйти из цикла обработки стека интервалов // начало цикла интегрирования одного интервала while(1) { c=(a+b)/fc=fun(c) sac=(fa+fc)*(c-a)/scb=(fc+fb)*(b-c)/sacb=sac+scb if(!BreakCond(sacb,sab)) { s+=sacb if(!sp) // локальный стек пуст break // выход из цикла интегрирования // одного интервала sp-GET_FROM_LOCAL_STACK[sp]( a, b, fa, fb, sab) } else { PUT_TO_LOCAL_STACK[sp]( a, c, fa, fc, sac) sp++ a=c fa=fc sab=scb } // перемещение части локального стека // в общий список интервалов if((sp>SPK) && (!sdat.ntask)) { // Начало критической секции заполнения глобального // стека отрезками интегрирования // sem_wait(sdat.sem_list) if(!sdat.ntask) { // установить семафор наличия // записей в глобальном стеке sem_post(sdat.sem_task_present) } while((sp>1) && (sdat.ntaskb) // sem_wait(&sdat.sem_list) sdat.nactive-if( (!sdat.nactive) && (!sdat.ntask) ) { // запись в глобальный стек списка терминальных отрезков for(i=0;i

} // в глобальном стеке есть записи sem_post(sdat.sem_task_present) } sem_post(sdat.sem_list) // // Конец критической секции заполнения глобального // стека терминальными отрезками } // конец цикла обработки стека интервалов // Начало критической секции сложения частичных сумм // sem_wait(&(sdat.sem_sum)) sdat.s_all+=s sem_post(&(sdat.sem_sum)) // // Конец критической секции сложения частичных сумм } Алг. 11. Параллельный алгоритм: метод глобального стека PUT_INTO_GLOBAL_STACK[sdat.ntask] (A,B,fA,fB,sAB) { sdat.list_of_tasks[sdat.ntask].a=A;

sdat.list_of_tasks[sdat.ntask].b=B;

sdat.list_of_tasks[sdat.ntask].fa=fA;

sdat.list_of_tasks[sdat.ntask].fb=fB;

sdat.list_of_tasks[sdat.ntask].s=sAB;

} - 24 PUT_FROM_GLOBAL_STACK[sdat.ntask] (A,B,fA,fB,sAB) { A=sdat.list_of_tasks[sdat.ntask].a;

B=sdat.list_of_tasks[sdat.ntask].b;

fA=sdat.list_of_tasks[sdat.ntask].fa;

fB=sdat.list_of_tasks[sdat.ntask].fb;

sAB=sdat.list_of_tasks[sdat.ntask].s;

} Алг. 12. Процедуры доступа к глобальному стеку Инициализация глобальных переменных выполняется в запускающей программе Алг. 7 перед запуском интегрирующих процессов slave_thr. В начале работы процессы slave_thr инициализируют свои локальные стеки, устанавливая в них нулевое количество записей, так же они устанавливают нулевые значения локальных сумм.

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

sem_wait(sdat.sem_task_present) Использование данного семафора предотвращает доступ к заведомо пустому стеку, однако не отменяет необходимости использования семафора доступа sdat.sem_list, гарантирующего корректную модификацию глобальных переменных несколькими процессами. Таким образом, чтение записи выполняется в критической секции, ограниченной строками:

sem_wait(sdat.sem_list) sem_post(sdat.sem_list) Внутри критической секции выполняется чтение и изъятие из глобального стека одного из отрезков. Далее открывается семафор наличия в глобальном стеке отрезков, если они есть:

if(sdat.ntask) sem_post(&sdat.sem_task_present) Затем выполняется анализ типа отрезка. Если правый конец меньше или равен левому, то отрезок интерпретируется как сигнал окончания работы («терминальный» отрезок). В противном случае увеличивается счетчик активных процессов – процессов, получивших интеграл интегрирования:

if(a<=b) sdat.nactive++ - 25 После выхода из критической секции осуществляется либо обработка очередного интервала в цикле интегрирования одного интервала, либо выход из цикла обработки стека интервалов, если получен терминальный отрезок.

Pages:     | 1 || 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.