Посыпкин М.А. (С) 2006 Многопоточное программирование. - презентация

1 Посыпкин М.А. (С) 2006 Многопоточное программирование

2 Посыпкин М.А. (С) 2006 Виды параллелизма. Общая память Распределенная память

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

4 Посыпкин М.А. (С) 2006 ПРОЦЕССЫ В ОПЕРАЦИОННОЙ СИСТЕМЕ Процесс – это экземпляр выполняемой программы. Контекст: регистры; таблица трансляции адресов памяти;... Адресное пространство: текст программы; статические данные; стек; разделяемая память; динамическая память (куча).

5 Посыпкин М.А. (С) 2006 ПЛАНИРОВАНИЕ ПРОЦЕССОВ время процесс # 1 процесс # 2 процесс # 3 CPU

6 Посыпкин М.А. (С) 2006 ПЛАНИРОВАИЕ ПРОЦЕССОВ В МНОГОПРОЦЕССОРНОЙ СИСТЕМЕ время процесс # 1 процесс # 2 процесс # 3 CPU

7 Посыпкин М.А. (С) 2006 ТРЕДЫ Тредами (потоки, нити) называются параллельно выполняющиеся потоки управления в рамках одного процесса. Треды одного процесса разделяют его адресное пространство.

8 Посыпкин М.А. (С) 2006 ПЛАНИРОВАИЕ ТРЕДОВ время тред # 1 тред # 2 тред # 3 CPU процесс #2 процесс #1

9 Посыпкин М.А. (С) 2006 Треды и процессы обмен через общую память обмен через посылку сообщений

10 Посыпкин М.А. (С) 2006 Различие тредов и процессов Различные треды выполняются в одном адресном пространстве. Различные процессы выполняются в разных адресных пространствах. Треды имеют «собственный» стек и набор регистров. Глобальные данные являются общими. Как локальные, так и глобальные переменные процессов являются «собственными».

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

12 Посыпкин М.А. (С) 2006 Создание и завершение тредов 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 родительский тред тред-потомок

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

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

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

16 Посыпкин М.А. (С) 2006 Пример: вычисление определенного интеграла y = f(x) abxixi x i+1 SiSi x i-1

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

18 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); }

19 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); }

20 Посыпкин М.А. (С) 2006 Проблема недетерминизма Программа называется недетерминированной, если при одних и тех же входных данных она может демонстрировать различное наблюдаемое поведение

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

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

23 Посыпкин М.А. (С) 2006 a:=a+1 a=0 a=2 Неделимой называется операция, в момент выполнения которой состояние общих переменных не может «наблюдаться» другими тредами Неделимая операция

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

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

26 Посыпкин М.А. (С) 2006 Кольцевой буфер frontrear producerconsumer

27 #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); }

28 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); }

29 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); }

30 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); }

31 Посыпкин М.А. (С) 2006 Критические секции Критической секцией называется фрагмент кода программы, который может одновременно выполнятся только одним тредом.

32 Посыпкин М.А. (С) 2006 Поддержка критических секций в 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); Освобождение мютекса может быть осуществлено только тем тредом, который производил его захват.

33 Посыпкин М.А. (С) 2006 Пример: умножение матриц C C = A * B каждый тред вычисляет свою строку матрицы

34 Посыпкин М.А. (С) 2006 Умножение матриц: код программы #include pthread_mutex_t mut; static int N, nrow; static double *A, *B, *C;

35 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 () { … }

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

37 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; }

38 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 ();

39 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); }

40 Посыпкин М.А. (С) 2006 Концепция монитора Монитор – объект, методы которого выполняются в режиме чередования (взаимное исключение). У монитора также есть данные: monitor { int s; f(); g();... }

41 Посыпкин М.А. (С) 2006 Вызов функции монитора очередь вызовов выполнение вызов тред

42 Посыпкин М.А. (С) 2006 Условные переменные Условные переменные – специальные поля монитора, которые служат для синхронизации. Основные операции: wait(v) – поместить тред в очередь (FIFO) ожидания; signal(v) – запустить поток из очереди ожидания.

43 Посыпкин М.А. (С) 2006 Диаграмма состояний синхронизации по условной переменной очередь вызовов выполнение вызов тред очередь ожидания переменной v wait(v) signal(v) Дисциплина обслуживания: «сигнализировать и продолжить» – сигнализирующий тред продолжает выполнение.

44 Посыпкин М.А. (С) 2006 Диаграмма состояний синхронизации по условной переменной очередь вызовов выполнение вызов тред очередь ожидания переменной v wait(v) signal(v) Дисциплина обслуживания: «сигнализировать и прерваться» – сигнализирующий тред прерывает выполнение. signal(v)

45 Посыпкин М.А. (С) 2006 Инициализация условной переменной в pthread int pthread_cond_init(pthread_cond_t* cv, pthread_cond_attr_t* attr); cv – указатель на инициализируемую условную переменную attr – атрибуты (по умолчанию NULL)

46 Посыпкин М.А. (С) 2006 Освобождение условной переменной в pthread int pthread_cond_destroy(pthread_cond_t* cv); cv – указатель на освобождаемую условную переменную

47 Посыпкин М.А. (С) 2006 Ожидание на условной переменной в pthread int pthread_cond_wait(pthread_cond_t* cv pthread_mutex_t* m) Освобождает мьютекс и переходит в режим ожидания; cv – указатель на освобождаемую условную переменную; m – указатель на мьютекс, соответствующий критической секции;

48 Посыпкин М.А. (С) 2006 Сигнализация по условной переменной в pthread int pthread_cond_signal(pthread_cond_t* cv); int pthread_cond_broadcast(pthread_cond_t* cv); cv – указатель на освобождаемую условную переменную; m – указатель на мьютекс, соответствующий критической секции;

49 Посыпкин М.А. (С) 2006 Реализация барьерной синхронизации при помощи условных переменных void barrier() { pthread_mutex_lock(&bar); num ++; if(num < N) pthread_cond_wait(&go, &bar); else { num = 0; pthread_cond_broadcast(&go); } pthread_mutex_unlock(&bar); }