Многопоточное программирование. Виды параллелизма. Общая память Распределенная память. - презентация

1 Многопоточное программирование

2 Виды параллелизма. Общая память Распределенная память

3 Средства параллельного программирования Общая памятьРаспределенная память Системные средства threadssockets Специальные библиотеки OpenMPMPI PVM

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

5 Треды и процессы обмен через общую память обмен через посылку сообщений

6 Различие тредов и процессов Различные треды выполняются в одном адресном пространстве. Различные процессы выполняются в разных адресных пространствах. Треды имеют «собственный» стек и набор регистров. Глобальные данные являются общими. Как локальные, так и глобальные переменные процессов являются «собственными».

7 Средства многопоточного программирования Треды поддерживаются практически всеми современными операционными системами. Средства для многопоточного программирования встроены в язык Java. Переносимая библиотека pthreads, разработанная Xavier Leroy, предоставляет средства для создания и управления тредами.

8 Создание и завершение тредов int pthread_create ( pthread_t * outHandle, pthread_attr_t *inAttribute, void *(*inFunction)(void *), void *inArg ); void pthread_exit(void *inReturnValue) int pthread_join( pthread_t inHandle, void **outReturnValue, ); pthread_create pthread_join pthread_exit родительский тред тред-потомок

9 Создание треда int pthread_create ( pthread_t * outHandle, pthread_attr_t *inAttribute, void *(*inFunction)(void *), void *inArg); outHandle – используется для возвращение в тред-родитель идентификатора треда потомка; inAttribute – атрибуты треда; inFunction – указатель на функцию, содержащую код, выполняемый тредом; inArg – указатель на аргумент, передаваемый в тред;

10 Завершение треда void pthread_exit(void *inReturnValue) Вызов этой функции приводит к завершению треда. Процесс-родитель получает указатель в качестве возвращаемых данных. Обычное завершение функции и возврат указателя на void*, выполняемой тредом эквивалентно вызову функции pthread_exit, которая используется в случае, когда надо завершить тред из функций, вызванных этой функцией.

11 Обработка завершения треда на треде-родителе int pthread_join( pthread_t inHandle, void **outReturnValue); Вызов этой функции приводит к блокировке родительского треда до момента завершения треда-потомка, соответствующего индентификатору inHandle. В область, указанную параметром outReturnValue, записывается указатель, возвращенный завершившимся тредом. pthread_join приводит к освобождению ресурсов, отведенных на тред (в частности сохранненого возращаемого значения). Необходимо выполнять также для синхронизации основного треда и тредов- потомков.

12 Пример: вычисление определенного интеграла y = f(x) abxixi x i+1 SiSi x i-1

13 #include double a = 0.0, b = 1.0, h, *r; int numt, n; double f(double x) { return 4 / (1 + x * x); }

14 void* worker(void* addr) { int my, i; double s, p; my = *(int*)addr; s = 0.0; for(p = a + my * h; p < b; p += numt * h) { s += h*(f(p) + f(p + h))/2.; } r[my] = s; return (void*)(r + my); }

15 main(int arc, char* argv[]) { int i; double S; pthread_t *threads; numt = atoi(argv[1]); n = atoi(argv[2]); threads = malloc(numt * sizeof(pthread_t)); r = malloc(numt * sizeof(double)); h = (b - a) / n; for(i = 0; i < numt; i ++) pthread_create(threads + i, NULL, worker, (void*)&i); S = 0; for(i = 0; i < numt; i ++) { double* r; pthread_join(threads[i], (void**)&r); S += *r; } printf("pi = %lf\n", S); }

16 Проблема недетерминизма Программа называется недетерминированной, если при одних и тех же входных данных она может демонстрировать различное наблюдаемое поведение

17 a read write increment read increment write a = a + 1 a = 0 a = 1

18 a read write increment read increment write a = a + 1 a = 0 a = 2

19 a:=a+1 a=0 a=2 Неделимой называется операция, в момент выполнения которой состояние общих переменных не может «наблюдаться» другими тредами Неделимая операция

20 Семафоры Семафорами называются общие переменные, которые принимают неотрицательные значение целого типа для работы с которыми предусмотрены две неделимые операции: 1)увеличить значение семафора на 1; 2)дождаться пока значение семафора не станет положительным и уменьшить значение семафора на 1.

21 Поддержка семафоров в библиотеке pthreads sem_t – тип семафора sem_init(sem_t* semaphor, int flag, int value) semaphor – семафор, flag – флаг (0 – внутри процесса, 1 – между процессами) value – начальное значение sem_post(sem_t* semaphor) – увеличение семафора sem_wait(sem_t* semaphor) – уменьшение семафора

22 Кольцевой буфер frontrear producerconsumer

23 #include #define N 3 static int buf[N]; static int rear; static int front; static sem_t empty; static sem_t full; void init () { front = 0; rear = 0; sem_init (&empty, 0, N); sem_init (&full, 0, 0); }

24 void process(int number) { sleep(number); } void * consumer (void *arg) { int i = 0; while (i != -1) { sem_wait (&full); i = buf[rear]; process(i); printf ("consumed: %d\n", i); rear = (rear + 1) % N; sem_post (&empty); }

25 void * producer (void *arg) { int i; i = 0; while (i != -1) { sem_wait (&empty); printf ("Enter number:"); scanf ("%d", &i); buf[front] = i; front = (front + 1) % N; sem_post (&full); }

26 main (int argc, char *argv[]) { pthread_t pt; pthread_t ct; init (); pthread_create (&pt, NULL, producer, NULL); pthread_create (&ct, NULL, consumer, NULL); pthread_join (ct, NULL); pthread_join (pt, NULL); }

27 Критические секции Критической секцией называется фрагмент кода программы, который может одновременно выполнятся только одним тредом.

28 Пример: создание неделимой опреации 1-й тред: a = a й тред: a = a + 1 Как сделать операцию a = a + 1 неделимой?

29 1-й тред: while(true) { while(in2); in1 = true; a = a + 1; in1 = false; } 2-й тред: while(true) { while(in1); in2= true a = a + 1; in2 = false; }

30 Поддержка критических секций в pthreads «Мютекс» - mutex – mutual exclusion (взаимное исключение); Объявление и инициализация: pthread_mutex_t – тип для взаимного исключения; pthread_mutex_init(pthread_mutex_t* mutex, void* attribute); pthread_mutex_destroy(pthread_mutex_t* mutex); Захват и освобождение мютекса: pthread_mutex_lock(pthread_mutex_t* mutex); pthread_mutex_unlock(pthread_mutex_t* lock); Освобождение мютекса может быть осуществлено только тем тредом, который производил его захват.

31 Пример: умножение матриц C C = A * B каждый тред вычисляет свою строку матрицы

32 Умножение матриц: код программы #include pthread_mutex_t mut; static int N, nrow; static double *A, *B, *C;

33 void setup_matrices () { int i, j; A = malloc (N * N * sizeof (double)); B = malloc (N * N * sizeof (double)); C = malloc (N * N * sizeof (double)); for (i = 0; i < N; i++) for (j = 0; j < N; j++) { A[i * N + j] = 1; B[i * N + j] = 2; } void print_result () { … }

34 void * worker (void *arg) { int i, j; while (nrow < N) { int oldrow; pthread_mutex_lock (&mut); oldrow = nrow; nrow++; pthread_mutex_unlock (&mut);

35 for (i = 0; i < N; i++) { int j; double t = 0.0; for (j = 0; j < N; j++) t += A[oldrow * N + j] * B[j * N + i]; C[oldrow * N + i] = t; } return NULL; }

36 main (int argc, char *argv[]) { int i, nthreads; pthread_t *threads; pthread_mutex_init(&mut, NULL); nthreads = atoi (argv[1]); threads = malloc (nthreads * sizeof (pthread_t)); N = atoi (argv[2]); setup_matrices ();

37 for (i = 0; i < nthreads; i++) pthread_create (threads + i, NULL, worker, NULL); for (i = 0; i < nthreads; i++) pthread_join (threads[i], NULL); if (argc > 3) print_result (); pthread_mutex_destory(&mut); }