Лекция 15 Организация параллельных взаимодействующих вычислений

Распараллеливание программ процесс адаптации алгоритмов, записанных в виде программ, для их эффективного исполнения на вычислительной системе параллельной архитектуры (в последнее время, как правило, на многопроцессорной вычислительной системе). Заключается либо в переписывании программ на специальный язык, описывающий параллелизм и понятный трансляторам целевой вычислительной системы, либо к вставке специальной разметки (например, инструкций MPI или OpenMP). Распараллеливание может быть ручным, автоматизированным и полуавтоматизированным. Для оценки эффективности его качества применяются следующие критерии: Ускорение Sp = T1 / Tp, где Tp время исполнения распараллеленной программы на p процессорах, T1 время исполнения исходной программы. В идеальном случае (отсутствие накладных расходов на организацию параллелизма) равна p. Загруженность Sp / p = T1 / pTp, показывающая долю использования процессоров. В идеальном случае равна 1, или 100 %. Эта величина зачастую гораздо более наглядно характеризует эффективность параллелизма в серии испытаний при разных p, чем Sp, особенно на графиках. При распараллеливании важно учитывать не только формальный параллелизм структуры алгоритма, но и то, что обменные операции в параллельных ЭВМ происходят, как правило, значительно медленнее арифметических. (Накладные расходы)

Многопоточность свойство платформы (например, операционной системы, JVM и т. д.) или приложения, состоящее в том, что процесс, порождённый в операционной системе, может состоять из нескольких потоков, выполняющихся «параллельно», то есть без предписанного порядка во времени. При выполнении некоторых задач такое разделение может достичь более эффективного использования ресурсов вычислительной машины. Сутью многопоточности является квазимногозадачность на уровне одного исполняемого процесса, то есть все потоки выполняются в адресном пространстве процесса. Кроме этого, все потоки процесса имеют не только общее адресное пространство, но и общие дескрипторы файлов. Выполняющийся процесс имеет как минимум один (главный) поток.

Многопоточность +- Повышение производительности процесса за счет распараллеливания процессорных вычислений и операций ввода/вывода Меньшие относительно процесса временные затраты на создание потока Упрощение программы за счет использования общего адресного пространства Остановка процесса приводит к остановке всех потоков Нехватка адресного пространства

Многопоточность Типы реализации потоков Поток в пространстве пользователя. Каждый процесс имеет таблицу потоков, аналогичную таблице процессов ядра. Поток в пространстве ядра. Наряду с таблицей процессов в пространстве ядра имеется таблица потоков. «Волокна» (fibers). Несколько потоков режима пользователя, исполняющихся в одном потоке режима ядра. Поток пространства ядра потребляет заметные ресурсы, в первую очередь физическую память и диапазон адресов режима ядра для стека режима ядра. Поэтому было введено понятие «волокна» облегчённого потока, выполняемого исключительно в режиме пользователя. У каждого потока может быть несколько «волокон».

Фоновая задача Это процесс, который работает в фоне, на заднем плане. Оболочка операционной системы, которая выполняет фоновый процесс, не ждёт завершения или окончания процесса, как это происходит с обычными программами. Оболочка может запустить ещё много процессов сразу после запуска одного фонового так, что они будут выполняться одновременно. На самом деле процессы будут выполнятся поочерёдно то один, то другой, но скорость переключения между процессами слишком быстра для человеческого восприятия, поэтому нам кажется, что они выполняются одновременно. Типичными фоновыми процессами, выполняющимися в системе, являются обработчики событий и системные службы. В рамках выделенной оперативной памяти может выполняться любое желаемое количество процессов.

Взаимодействие потоков Мьютекс - это объект синхронизации, который устанавливается в особое сигнальное состояние, когда не занят каким-либо потоком. Только один поток владеет этим объектом в любой момент времени, отсюда и название таких объектов (от английского mutually exclusive access взаимно исключающий доступ) одновременный доступ к общему ресурсу исключается. После всех необходимых действий мьютекс освобождается, предоставляя другим потокам доступ к общему ресурсу Семафоры - представляют собой доступные ресурсы, которые могут быть приобретены несколькими потоками в одно и то же время, пока пул ресурсов не опустеет. Тогда дополнительные потоки должны ждать, пока требуемое количество ресурсов не будет снова доступно. Семафоры очень эффективны, поскольку они позволяют одновременный доступ к ресурсам События. Объект, хранящий в себе 1 бит информации «просигнализирован или нет», над которым определены операции «просигнализировать», «сбросить в непросигнализированное состояние» и «ожидать». Ожидание на просигнализированном событии есть отсутствие операции с немедленным продолжением исполнения потока. Ожидание на непросигнализированном событии приводит к приостановке исполнения потока до тех пор, пока другой поток (или же вторая фаза обработчика прерывания в ядре ОС) не просигнализирует событие. Возможно ожидание нескольких событий в режимах «любого» или «всех». Возможно также создания события, автоматически сбрасываемого в непросигнализированное состояние после пробуждения первого же и единственного ожидающего потока (такой объект используется как основа для реализации объекта «критическая секция»). Активно используются в MS Windows, как в режиме пользователя, так и в режиме ядра. Критические секции обеспечивают синхронизацию подобно мьютексам за исключением того, что объекты, представляющие критические секции, доступны в пределах одного процесса. События, мьютексы и семафоры также можно использовать в однопроцессном приложении, однако реализации критических секций в некоторых ОС (например Windows NT), обеспечивают более быстрый и более эффективный[1][2] механизм взаимно-исключающей синхронизации операции «получить» и «освободить» на критической секции оптимизированы для случая единственного потока (отсутствия конкуренции) с целью избежать любых ведущих в ядро ОС системных вызовов. Подобно мьютексам объект, представляющий критическую секцию, может использоваться только одним потоком в данный момент времени, что делает их крайне полезными при разграничении доступа к общим ресурсам.

Взаимодействие потоков Условные переменные (condvars). Сходны с событиями, но не являются объектами, занимающими память используется только адрес переменной, понятие «содержимое переменной» не существует, в качестве условной переменной может использоваться адрес произвольного объекта. В отличие от событий, установка условной переменной в просигнализированное состояние не влечет за собой никаких последствий в случае, если на данный момент нет потоков, ожидающих на переменной. Установка события в аналогичном случае влечет за собой запоминание состояния «просигнализировано» внутри самого события, после чего следующие потоки, желающие ожидать события, продолжают исполнение немедленно без остановки. Для полноценного использования такого объекта необходима также операция «освободить mutex и ожидать условную переменную атомарно». Активно используются в UNIX-подобных ОС. Дискуссии о преимуществах и недостатках событий и условных переменных являются заметной частью дискуссий о преимуществах и недостатках Windows и UNIX. Порт завершения ввода-вывода (IO completion port, IOCP). Реализованный в ядре ОС и доступный через системные вызовы объект «очередь» с операциями «поместить структуру в хвост очереди» и «взять следующую структуру с головы очереди» последний вызов приостанавливает исполнение потока в случае, если очередь пуста, и до тех пор, пока другой поток не осуществит вызов «поместить». Главнейшей особенностью IOCP является то, что структуры в него могут помещаться не только явным системным вызовом из режима пользователя, но и неявно внутри ядра ОС как результат завершения асинхронной операции ввода-вывода на одной из дескрипторов файлов. Для достижения такого эффекта необходимо использовать системный вызов «связать дескриптор файла с IOCP». В этом случае помещенная в очередь структура содержит в себе код ошибки операции ввода- вывода, а также, для случая успеха этой операции число реально введенных или выведенных байт. Реализация порта завершения также ограничивает число потоков, исполняющихся на одном процессоре/ядре после получения структуры из очереди. Объект специфичен для MS Windows, и позволяет обработку входящих запросов соединения и порций данных в серверном программном обеспечении в архитектуре, где число потоков может быть меньше числа клиентов (нет требования создавать отдельный поток с расходами ресурсов на него для каждого нового клиента).

Hyper-threading (англ. Hyper-threading Гиперпоточность, официальное название Hyper- Threading Technology (HTT)) это торговая марка компании Intel для реализации технологии «одновременной мультипоточности» (англ. Simultaneous multithreading) на микроархитектуре Pentium 4. Расширенная форма суперпоточности (англ. Super-threading), впервые появившаяся в процессорах Intel Xeon и позднее добавленная в процессоры Pentium 4. Эта технология увеличивает производительность процессора при определённых рабочих нагрузках путём предоставления «полезной работы» (англ. useful work) исполнительным устройствам (англ. execution units), которые иначе будут бездействовать; к примеру, в случаях кэш-промаха. Процессоры Pentium 4 с включённым Hyper- threading операционная система определяет как два разных процессора вместо одного. Преимущества Hyper-threading представлены как: улучшенная поддержка многопоточного кода, позволяя запускать потоки одновременно; улучшена реакция и время отклика; увеличено количество пользователей, которое может поддерживать сервер. По словам Intel, первая реализация потребовала всего 5-процентного увеличения площади кристалла, но позволяла увеличить производительность на %. Intel утверждает, что прибавка к скорости составляет 30% по сравнению с идентичным процессорами Pentium 4 без технологии «Simultaneous multithreading». Однако прибавка к производительности изменяется от приложения к приложению: некоторые программы вообще несколько замедляются при включённой технологии Hyper-threading. Это, в первую очередь, связано с «системой повторения» процессоров Pentium 4, занимающей необходимые вычислительные ресурсы, отчего и начинают «голодать» другие потоки.

Многозадачность (англ. multitasking) свойство операционной системы или среды программирования обеспечивать возможность параллельной (или псевдопараллельной) обработки нескольких процессов. Истинная многозадачность операционной системы возможна только в распределенных вычислительных системах.

Многозадачность. Свойства. Примитивные многозадачные среды обеспечивают чистое «разделение ресурсов», когда за каждой задачей закрепляется определённый участок памяти, и задача активизируется в строго определённые интервалы времени. Более развитые многозадачные системы проводят распределение ресурсов динамически, когда задача стартует в памяти или покидает память в зависимости от её приоритета и от стратегии системы. Такая многозадачная среда обладает следующими особенностями: Каждая задача имеет свой приоритет, в соответствии с которым получает процессорное время и память Система организует очереди задач так, чтобы все задачи получили ресурсы, в зависимости от приоритетов и стратегии системы Система организует обработку прерываний, по которым задачи могут активироваться, деактивироваться и удаляться По окончании положенного кванта времени ядро временно переводит задачу из состояния выполнения в состояние готовности, отдавая ресурсы другим задачам. При нехватке памяти страницы не выполняющихся задач могут быть вытеснены на диск (свопинг), а потом через определённое системой время, восстанавливаться в памяти Система обеспечивает защиту адресного пространства задачи от несанкционированного вмешательства других задач Система обеспечивает защиту адресного пространства своего ядра от несанкционированного вмешательства задач Система распознаёт сбои и зависания отдельных задач и прекращает их Система решает конфликты доступа к ресурсам и устройствам, не допуская тупиковых ситуаций общего зависания от ожидания заблокированных ресурсов Система гарантирует каждой задаче, что рано или поздно она будет активирована Система обрабатывает запросы реального времени Система обеспечивает коммуникацию между процессами

Многозадачность. Ключевые моменты Надежность (защита памяти, обработка прерываний, обработка сбоев, предохранение от зависаний и тупиковых ситуаций). Сторожевой таймер. Эффективность. Минимизация затрат на ресурсы. Не мешать процессам, не замедлять работу, не ограничивать резко память.

Типы псевдопараллельной многозадачности Невытесняющая многозадачность Совместная или кооперативная многозадачность Вытесняющая или приоритетная многозадачность (режим реального времени)

Проблемные ситуации в многозадачных системах Голодание (starvation) Гонка (race condition) Инверсия приоритета

Распределённые вычисления Распределённые вычисле́ния (distributed computing, grid computing, volunteer computing) способ решения трудоёмких вычислительных задач с использованием двух и более компьютеров. Распределённые вычисления являются частным случаем параллельных вычислений, то есть одновременного решения различных частей одной вычислительной задачи несколькими процессорами одного или нескольких компьютеров. Поэтому необходимо, чтобы решаемая задача была сегментирована, то есть разделена на подзадачи, которые могут вычисляться параллельно. При этом для распределенных вычислений приходится также учитывать возможное различие в вычислительных ресурсах, которые будут доступны для расчёта различных подзадач. Более того, не все задачи целесообразно разбивать на подзадачи, ввиду сложности этого процесса для некоторых типов задач или вычислений.