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

2Georgiy Korneev Краткое содержание 1.Введение 2.Классические задачи многопоточного программирования 3.Атомарные операции 4.Примитивы синхронизации 5.Решения задач многопоточного программирования 6.Заключение

Введение Часть 1

4Georgiy Korneev Многопоточное программирование Программа одновременно имеет несколько потоков исполнения Потоки должны взаимодействовать (синхронизироваться) друг с другом

5Georgiy Korneev Пример. Умножение матриц // Матрицы размера n на n double[][] a, b, c; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { c[i][j] = 0; for (int k = 0; k < n; k++) { c[i][j] += a[i][k] * b[k][j]; }

6Georgiy Korneev Пример. Итеративный параллелизм // Матрицы размера n на n double[][] a, b, c; for (int i = 0; i < n; i++) { // Параллельно for (int j = 0; j < n; j++) {// Параллельно c[i][j] = 0; for (int k = 0; k < n; k++) { c[i][j] += a[i][k] * b[k][j]; }

7Georgiy Korneev Пример. Обмен сообщениями (1) Рабочий поток Worker[i] { double[] a;// a[i][*] double[][] b;// b[*][*] double[] c;// c[i][*] receive a, b from coordinator; for (int j = 0; j < n; j++) { c[j] = 0; for (int k = 0; k < n; k++) { c[j] += a[k] * b[k][j]; } send c to coordinator; }

8Georgiy Korneev Пример. Обмен сообщениями (2) Управляющий поток coordinator(int i) { double[][] a, b, c; for (int i = 0; i < n; i++) { send a[i], b to worker[i]; } for (int i = 0; i < n; i++) { receive c[i] from worker[i]; }

9Georgiy Korneev Пример. Обмен сообщениями (3) worker[i] { double[] a; // a[i][*] double[] b; // b[*][i] double[] c; // a[i][*] receive a, b from coordinator; for (int j = 0; j < n; j++) { double s = 0; for (int k = 0; k < n; k++) { s += a[k] * b[k]; } c[(i + j) % n] = s; send b to worker[(i + 1) % n]; receive b from worker[(i + n - 1) % n]; } send c to coordinator; }

10Georgiy Korneev Пример. Вычисление интеграла Адаптивное вычисление интеграла f(x) double integrate(double l, double r) { if (abs(area(l, m) + area(m, r) - area(l, r)) > EPS) { return integrate(l, m) + integrate(m, r); } else { return area(l, m) + area(m, r); } double area(double l, double r) { return (f(l) + f(r)) * (r - l) / 2; }

11Georgiy Korneev Пример. Рекурсивный параллелизм Адаптивное вычисление интеграла f(x) double integrate(double l, double r) { double m = (l + r) / 2; double la = area(l, m); double ra = aread(m, r); if (abs(la + ra - area(l, r)) > EPS) { la = integrate(l, m); // Параллельно ra = integrate(m, r); // Параллельно } return la + ra; }

12Georgiy Korneev Основные операции Создание потока Уничтожение потока Неделимая операция statements Неделимая операция с ожиданием условия await(C) statements

13Georgiy Korneev Пример. Поиск максимума (1) Без синхронизации int max = 0; create worker[i] { if (max < a[i]) max = a[i]; } С синхронизацией int max = 0; create worker[i] { if (max < a[i]) max = a[i]; }

14Georgiy Korneev Пример. Поиск максимума (2) Протокол Проверить-Проверить- Установить int max = 0; create worker[i] { if (max < a[i]) { if (max < a[i]) max = a[i]; }

15Georgiy Korneev Свойства планирования Справедливость Безусловная Слабая Сильная Безопасность Живучесть

Классические задачи многопоточного программирования Часть 2

17Georgiy Korneev Задача доступа к общему ресурсу Несколько потоков обращаются к общему ресурсу

18Georgiy Korneev Производитель-потребитель Один поток производит данные, второй их потребляет Несколько потоков производят данные и несколько их потребляют Данные могут храниться в очереди

19Georgiy Korneev Задача о читателях и писателях Читать могут много потоков одновременно Писать может только один поток Читать во время записи нельзя

20Georgiy Korneev Задача об обедающих философах 5 Философов, 5 тарелок, 5 вилок Философ Думает Ест Что бы есть нужны обе вилки

21Georgiy Korneev Задания-работники Поток-клиент ждет выполнения задания потоком-сервером

Атомарные операции Часть 3

23Georgiy Korneev Атомарная операция Операция выполняемая как единое целое Чтение Запись Неатомарные операции Инкремент Декремент

24Georgiy Korneev Виды атомарных операций Операция чтения get Операция записи set Операции записи и чтения addAndGet, incAndGet, … getAndAdd, getAndInc, … Операция условной записи compareAndSet

25Georgiy Korneev Решение задачи доступа к ресурсу // Получение доступа к ресурсу while(!v.compareAndSet(0, 1)); // Действия с ресурсом // Освобождение ресурса v.set(0);

Примитивы синхронизации Часть 4

27Georgiy Korneev Критическая секция Только один поток может выполнять действия в критической секции Именованные критические секции

28Georgiy Korneev Решение задачи доступа к ресурсу Доступ производится в критической секции resource < resource: // Доступ к ресурсу >

29Georgiy Korneev Реализации критических секций На основе блокировки await(!lock) lock = true; // Вход // Критическая секция lock = false;// Выход На основе атомарных операций while(!lock.compareAndSet(0, 1));// Вход // Критическая секция lock.set(0);// Выход

30Georgiy Korneev Блокировка (lock, mutex) Только один поток может владеть блокировкой Могут быть использованы для передачи событий Операции lockполучить блокировку unlockотдать блокировку tryLockпопробовать получить блокировку

31Georgiy Korneev Решение задачи доступа к ресурсу Доступ ограничен блокировкой lock // Получение блокировки lock.lock(); // Доступ к ресурсу // Освобождение блокировки lock.unlock()

32Georgiy Korneev Семафор Хранит количество разрешений на вход Могут быть использованы для передачи событий Операции acquireполучить разрешение releaseдобавить разрешение tryAcquire попробовать получить разрешение

33Georgiy Korneev Барьер Потоки блокируются пока все потоки не прибудут к барьеру Одноразовый Многоразовый Операции arriveприбытие к барьеру

34Georgiy Korneev Монитор Разделяемые переменные инкапсулированы в мониторе Код в мониторе исполняется не более чем одним потоком Условия Операции с условиями waitожидание условия notifyсообщение об условии одному потоку notifyAllсообщение об условии всем потокам

Решение классических задач параллельного программирования Часть 5

36Georgiy Korneev Производитель-потребитель Решение с помощью разделенных блокировок Производитель empty.lock(); // копирование full.unlock(); Потребитель full.lock(); // копирование empty.unlock();

37Georgiy Korneev Задания-работники Решение с помощью монитора Задание queue.add(task); queue.notify(); task.wait(); Работник while (queue.isEmpty()) queue.wait(); Task t = queue.get(); // Обработка задания t.notify();

38Georgiy Korneev Задача об обедающих философах Решение с помощью асимметрии Все философы кроме одного берут сначала левую, затем правую вилку Оставшийся философ берет сначала правую, затем левую вилку

39Georgiy Korneev Задача о читателях и писателях (1) Решение с помощью блокировки Читатель if (nr++ == 0) busy.lock(); // Чтение if (--nr == 0) busy.unlock(); Писатель busy.lock(); // Запись busy.unlock();

40Georgiy Korneev Задача о читателях и писателях (2) Решение с помощью передачи эстафеты Особенности решения Если есть и писатели и читатели, то вход закрывается Пока есть читатели – разрешать чтение Когда нет читателей – разрешить запись Когда нет ни читателей ни писателей – открыть вход

41Georgiy Korneev Задача о читателях и писателях (3)

42Georgiy Korneev Задача о читателях и писателях Передача эстафеты if (nw == 0 && dr > 0) { dr--; r.unlock(); // Возобновить процесс-читатель else if (nr == 0 && nw == 0 && dw > 0) { dw--; w.unlock(); // Возобновить процесс-писатель } else { e.unlock(); // Открыть вход }

43Georgiy Korneev Задача о читателях и писателях Читатель e.lock(); if (nw > 0) { dr++; e.unlock(); r.lock(); } // Доступ разрешен nr++; // Передача эстафеты // Чтение e.lock(); nr--; // Передача эстафеты

44Georgiy Korneev Задача о читателях и писателях Писатель e.lock(); if (nw > 0 || nr > 0) { dw++; e.unlock(); w.lock(); } nw++; // Передача эстафеты // Запись e.lock(); nw--; // Передача эстафеты

Заключение Часть 6

46Georgiy Korneev Ссылки Эндрюс Г. Основы многопоточного, параллельного и распределенного программирования Lea D. Concurrent Programming in Java

47Georgiy Korneev Вопросы