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

2Georgiy Korneev Краткое содержание 1.Исторический экскурс 2.Параллельное исполнение 3.Потоки 4.Блокировки 5.Мониторы и события 6.Модель памяти Java 7.Примеры Java Advanced / Введение в многопоточное программирование

Исторический экскурс Часть 1

4Georgiy Korneev Однозадачные системы Одна задача за раз Пока задача не завершилась – все ждут Память – монопольное использование Ввод-вывод – монопольное использование Пока не завершилась – все ждут Простой ресурсов Большое время отклика Java Advanced / Введение в многопоточное программирование

5Georgiy Korneev Пакетные Набор заданий для исполнения (пакет) Память – разделяемая, изолированная Ввод-вывод – переключение задач Управление заданиями – монитор Псевдопараллельное исполнение Увеличение загрузки ресурсов Большое время отклика 1950-е годы Java Advanced / Введение в многопоточное программирование

6Georgiy Korneev Многозадачные системы Несколько задач конкурируют за процессор Память – разделяемая, изолированная Прерывание – переключение задач Ввод-вывод – разделяемый Параллельное исполнение Уменьшение времени отклика 1960-е годы Java Advanced / Введение в многопоточное программирование

7Georgiy Korneev Многопоточные программы Несколько задач конкурируют за процессор Память – общая Прерывание – переключение потоков Ввод-вывод – разделяемый Параллельное исполнение кода внутри программы Уменьшение времени отклика 1990-е годы Java Advanced / Введение в многопоточное программирование

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

9Georgiy Korneev Почему это важно Вычислительная мощность ядер не растет Растет их количество AzulSystems Vega D 16 процессоров по 54 ядра = 864 ядер 768 GB RAM 1 JVM Java Advanced / Введение в многопоточное программирование

Параллельное исполнение Часть 2

11Georgiy 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]; } Java Advanced / Введение в многопоточное программирование

12Georgiy 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]; } Java Advanced / Введение в многопоточное программирование

13Georgiy 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; } Java Advanced / Введение в многопоточное программирование

14Georgiy 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]; } Java Advanced / Введение в многопоточное программирование

15Georgiy 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; } Java Advanced / Введение в многопоточное программирование

16Georgiy 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; } Java Advanced / Введение в многопоточное программирование

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

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

19Georgiy 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]; } Java Advanced / Введение в многопоточное программирование

20Georgiy Korneev Пример. Поиск максимума (2) Протокол Проверить-Проверить- Установить int max = 0; create worker[i] { if (max < a[i]) { if (max < a[i]) max = a[i]; } Java Advanced / Введение в многопоточное программирование

21Georgiy Korneev Свойства планирования Безопасность Живучесть Справедливость Безусловная (отсутствие условий) Слабая Сильная Java Advanced / Введение в многопоточное программирование

Потоки в Java Часть 3

23Georgiy Korneev Создание потоков Класс Thread – поток Позволяет создавать потоки и производить операции с ними Интерфейс Runnable – сущность, которая может быть запущена public void run(); Java Advanced / Введение в многопоточное программирование

24Georgiy Korneev Создание потока (Runnable) Пример кода // Создание потока Thread t = new Thread(new Runnable() { public void run() { System.out.println("Hello"); } }); // Запуск потока t.start(); Java Advanced / Введение в многопоточное программирование

25Georgiy Korneev Создание потока (Thread) Не рекомендуется использовать Пример кода // Создание потока Thread t = new Thread() { public void run() { System.out.println("Hello"); } }; // Запуск потока t.start(); Java Advanced / Введение в многопоточное программирование

26Georgiy Korneev Состояния потока Состояние потока возвращается методами int getState() boolean isAlive() getState()isAlive() NEW RUNNABLE+ BLOCKED+ WAITING+ TIMED_WAITING+ TERMINATED Java Advanced / Введение в многопоточное программирование

27Georgiy Korneev Свойства потока Основные свойства id – идентификатор потока name – имя потока priority – приоритет daemon – поток-демон Свойства потока не могут изменяться после запуска Java Advanced / Введение в многопоточное программирование

28Georgiy Korneev Взаимодействие потоков Создание потока (конструктор) Запуск потока (start) Ожидание окончания потока (join) Прерывание потока (interrupt) Java Advanced / Введение в многопоточное программирование

29Georgiy Korneev Ожидание окончания потока Методы класса Thread join() – ожидать до завершения join(long millis) – ожидать до завершения или истечения millis миллисекунд join(long millis, long nanos) – ожидать до завершения или истечения millis миллисекунд и nanos наносекунд Все методы ожидания кидают InterruptedExcepton Java Advanced / Введение в многопоточное программирование

30Georgiy Korneev Прерывание потока Методы класса Thread interrupt() – установить флаг прерывания isInterrupted() – проверить флаг прерывания interrupted() – проверить и сбросить флаг прерывания Методы, которые ожидают в процессе выполнения должны бросать InterruptedException Java Advanced / Введение в многопоточное программирование

31Georgiy Korneev Обработка данных в цикле class Worker implements Runnable { public void run() { try { while (!Thread.interrupted()) { // Полезные действия } } catch (InterruptedException e) { } // Исполнение потока прервано // Поток заканчивает работу } Java Advanced / Введение в многопоточное программирование

32Georgiy Korneev Дополнительные методы Приостановка выполнения sleep(time) – приостановить поток на время yield() – позволить выполниться другим потокам Получение текущего потока currentThread() Java Advanced / Введение в многопоточное программирование

Блокировки (синхронизация) Часть 4

34Georgiy Korneev Блокировка (lock, mutex) Только один поток может владеть блокировкой Операции lockполучить блокировку unlockотдать блокировку Java Advanced / Введение в многопоточное программирование

35Georgiy Korneev Блокировки в Java Любой объект может служить блокировкой Снятие блокировки производится автоматически Синтаксис synchronized (o) { // Получение блокировки … } // Снятие блокировки Java Advanced / Введение в многопоточное программирование

36Georgiy Korneev Методы экземпляра Метод экземпляра может быть объявлен синхронизованным public synchronized int getValue() { … } Эквивалентно public int getValue() { synchronized (this) { … } } Java Advanced / Введение в многопоточное программирование

37Georgiy Korneev Методы класса Метод класса может быть объявлен синхронизованным Class Example { public static synchronized int getValue() { … } Эквивалентно public int getValue() { synchronized (Example.class) { … } } Java Advanced / Введение в многопоточное программирование

38Georgiy Korneev Производитель-потребитель Один поток производит данные, второй их потребляет Несколько потоков производят данные и несколько их потребляют Данные могут храниться в очереди (не)ограниченного объема Java Advanced / Введение в многопоточное программирование

39Georgiy Korneev Интерфейс очереди Хранит один элемент class Queue { private Object data; public void set(Object data) { … } public Object get() { … } } Java Advanced / Введение в многопоточное программирование

40Georgiy Korneev Производитель Установка значения public void set(Object data) { while (true) { // Активное ожидание synchronized (this) { if (data == null) { this.data = data; break; } Java Advanced / Введение в многопоточное программирование

41Georgiy Korneev Потребитель Получение значения public Object get() { while (true) { // Активное ожидание synchronized (this) { if (data != null) { Object d = data; data = null; return d; } Java Advanced / Введение в многопоточное программирование

Мониторы и условия Часть 5

43Georgiy Korneev Монитор Любой объект может быть монитором Передача событий wait(time?) – ожидание условия notify() – извещение одного из ждущих потоков notifyAll() – извещение всех ждущих потоков Нужно владеть блокировкой IllegalMonitorStateException Java Advanced / Введение в многопоточное программирование

44Georgiy Korneev Мониторы и блокировки При ожидании монитора блокировка с него снимается При извещении поток не получает управления пока не может получить блокировку обратно Псевдокод monitor.unlock() monitor.await() monitor.lock() Java Advanced / Введение в многопоточное программирование

45Georgiy Korneev Производитель (2) Установка значения public synchronized void set(Object data) throws InterruptedException { while (data != null) { wait(); // Пассивное ожидание } this.data = data; notify(); } Java Advanced / Введение в многопоточное программирование

46Georgiy Korneev Потребитель (2) Получение значения public synchronized Object get() throws InterruptedException { while (data == null) { wait(); // Пассивное ожидание } Object d = data; data = null; notify(); return d; } Java Advanced / Введение в многопоточное программирование

47Georgiy Korneev notify() и notifyAll() События одного вида Может обработать любой ждущий поток notify() Несколько видов событий Побуждение «Не того» потока notifyAll() Более дорогая операция Java Advanced / Введение в многопоточное программирование

48Georgiy Korneev Внезапные пробуждения wait() может завершиться без notify() Проверить наступление события Ожидать всегда в цикле Идиома while (дождался) wait(); Java Advanced / Введение в многопоточное программирование

Модель памяти Java Часть 6

50Georgiy Korneev Основные свойства Атомарность Видимость Упорядоченность Java Advanced / Введение в многопоточное программирование

51Georgiy Korneev Атомарность Атомарная операция выполняется как единое целое Операции над всеми типами кроме long и double являются атомарными Java Advanced / Введение в многопоточное программирование

52Georgiy Korneev Пример int a = 0; long b = 0; // T1 a = 1; b = -1; Возможные значения a 0 1 Возможные значения b 0 0xffffffff x ffffffff … Java Advanced / Введение в многопоточное программирование

53Georgiy Korneev Видимость Изменения произведенные потоком 1 видимы потоком 2 Видимость гарантируется в следующих случаях После изменений поток 1 освободил блокировку, которую захватил поток 2 После изменения поток 1 создал поток 2 Поток 2 дождался окончания потока 1 При неправильной синхронизации изменения могут быть видимы в произвольном порядке Java Advanced / Введение в многопоточное программирование

54Georgiy Korneev Пример int a = 0; int b = 0; // T1 a = 1; b = 2; Возможные значения пары а, b 0, 0 1, 0 1, 2 0, 2 Java Advanced / Введение в многопоточное программирование

55Georgiy Korneev Упорядоченность Программы выполняются как если бы они были написаны последовательно С точки зрения других потоков выполнение программы может производиться в произвольном порядке Java Advanced / Введение в многопоточное программирование

56Georgiy Korneev Пример int a = 0; a = 1; a = 2; Возможные последовательност и значений а 0, 0 0, 1 0, 2 1, 2 2, 0 2, 1 … Java Advanced / Введение в многопоточное программирование

57Georgiy Korneev Volatile-переменные Операции с volatile-переменными всегда атомарны При чтение значения volatile-переменной оно всегда читается из общей памяти При записи значения volatile-переменной оно всегда записывается в общую память Если volatile-ссылка изменилась, то данные доступные по ней могли не измениться Java Advanced / Введение в многопоточное программирование

58Georgiy Korneev Пример 1 List l = null; t1() { List l = new ArrayList(); l.add(new Object()); this.l = l; } Object t2() { while (l != null) { return l.get(0); } Java Advanced / Введение в многопоточное программирование

59Georgiy Korneev Пример 2 public class Singleton { public static volatile Singleton instance; public static Singleton getInstance() { if (instance == null) { synchronized (Singleton.class) { if (instance == null) { instance = new Singleton(); } return instance; } Java Advanced / Введение в многопоточное программирование

60Georgiy Korneev Выводы При отсутствии правильной синхронизации потоки могут увидеть практически что угодно Java Advanced / Введение в многопоточное программирование

Примеры Часть 7

62Georgiy Korneev Барьер public await(Barrier that) { // 0 synchronized (this) { // 1 this.generation++; // 2 this.notify(); // 3 } // 4 synchronized (that) { // 5 while (this.generation > that.generation) { // 6 that.wait(); // unlock 7, await 8, lock 9 } // 10 } // 11 } Java Advanced / Введение в многопоточное программирование

63Georgiy Korneev Диаграмма переходов для барьера Java Advanced / Введение в многопоточное программирование

64Georgiy Korneev Гарантированный deadlock public void run() { // 0 synchronized (o1) { // 1 o1.notifyAll(); // 2 synchronized (o2) { // 3 try { o2.wait(); // unlock 4, await 5, lock 6 } catch (InterruptedException e) {} } // 7 } // 8 } Java Advanced / Введение в многопоточное программирование

65Georgiy Korneev Диаграмма переходов для deadlock Java Advanced / Введение в многопоточное программирование

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

67Georgiy Korneev Ссылки JLS. Threads and Locks // n/html/memory.html n/html/memory.html Threads: Doing Two or More Tasks At Once (Java Tutorial) // ial/threads/index.html ial/threads/index.html Lea D. Concurrent Programming in Java Garg V. Concurrent and Distributed Computing in Java Java Advanced / Введение в многопоточное программирование

68Georgiy Korneev Вопросы Java Advanced / Введение в многопоточное программирование