Операция в программировании

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

Java Advanced

Краткое содержание

Введение Классические задачи многопоточного программирования Атомарные операции Примитивы синхронизации Решения задач многопоточного программирования Заключение

Введение

Часть 1

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

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

Пример

Умножение матриц.

// Матрицы размера 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]; } } }

Пример

Итеративный параллелизм.

// Матрицы размера 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]; } } }

Пример

Обмен сообщениями (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; }

Пример

Обмен сообщениями (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]; } }

Пример

Обмен сообщениями (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; }

Пример

Вычисление интеграла.

Адаптивное вычисление интеграла 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; }

Пример

Рекурсивный параллелизм.

Адаптивное вычисление интеграла 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; }

Основные операции

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

Пример

Поиск максимума (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];? }

Пример

Поиск максимума (2).

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

Свойства планирования

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

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

Часть 2

Задача доступа к общему ресурсу

Несколько потоков обращаются к общему ресурсу

Производитель-потребитель

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

Задача о читателях и писателях

Читать могут много потоков одновременно Писать может только один поток Читать во время записи нельзя

Задача об обедающих философах

5 Философов, 5 тарелок, 5 вилок Философ Думает Ест Что бы есть нужны обе вилки

Задания-работники

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

Атомарные операции

Часть 3

Атомарная операция

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

Виды атомарных операций

Операция чтения get Операция записи set Операции записи и чтения addAndGet, incAndGet, … getAndAdd, getAndInc, … Операция условной записи compareAndSet

Решение задачи доступа к ресурсу

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

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

Часть 4

Критическая секция

Только один поток может выполнять действия в критической секции Именованные критические секции < name: statements >

Решение задачи доступа к ресурсу

Доступ производится в критической секции resource < resource: // Доступ к ресурсу >

Реализации критических секций

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

Блокировка (lock, mutex)

Только один поток может владеть блокировкой Могут быть использованы для передачи событий Операции lock получить блокировку unlock отдать блокировку tryLock попробовать получить блокировку

Решение задачи доступа к ресурсу

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

Семафор

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

Барьер

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

Монитор

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

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

Часть 5

Производитель-потребитель

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

Задания-работники

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

Задача об обедающих философах

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

Задача о читателях и писателях (1)

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

Задача о читателях и писателях (2)

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

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

Задача о читателях и писателях

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

Задача о читателях и писателях

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

Задача о читателях и писателях

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

Заключение

Часть 6

Ссылки

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

Вопросы