Словарь
Словарь
Активная блокировка (Spin Lock)
Булева переменная, используемая в конъюнкции с активным ожиданием для защиты критической секции. Стремясь войти в критическую секцию, процесс зацикливается до тех пор, пока блокировка не будет освобождена.
Активное (занятое) ожидание (Busy Waiting)
Реализация синхронизации, в которой процесс многократно выполняет цикл, ожидая, что некоторое булево условие в станет истинным. Обычно это программируется как while (! В) skip;. Если процесс находится в состоянии занятого ожидания, говорят также, что он зациклен (spinning).
Алгоритм "зонд-эхо" (Probe/Echo Algorithm)
Парадигма взаимодействия процессов в распределенных программах. Зонд используется для рассылки информации от одного процесса всем остальным, а эхо — для сбора информации.
Алгоритм передачи маркера (Token-Passing Algorithm)
Схема взаимодействия процессов в распределенной программе, использующая маркеры для передачи разрешения или сбора информации о глобальном состоянии.
Алгоритм пульсации (Heartbeat Algorithm)
Парадигма взаимодействия процессов в распределенных программах. Каждый процесс периодически выполняет три фазы: 1) передает сообщения другим процессам, 2) принимает сообщения от других процессов, 3) выполняет вычисления с локальными данными и данными, полученными в сообщениях.
Алгоритм рассылки (Broadcast Algorithm)
Метод распространения информации или принятия решений в распределенной программе. Для принятия решения каждый процесс отправляет запросы и подтверждения всем остальным процессам и обслуживает упорядоченную очередь сообщений, по которой определяется наиболее давний запрос.
Балансировка нагрузки (Load Balancing)
Назначение каждому процессу (и процессору) в параллельной программе приблизительно одинакового количества работы.
Барьер (Barrier)
Точка синхронизации, которую должны достичь все процессы перед тем, как некоторым из них будет разрешено дальнейшее выполнение.
Безусловное неделимое действие (Unconditional Atomic Action)
Неделимое действие, не имеющее условия задержки. Программируется как <S;> и может быть реализовано одной машинной командой.
Словарь 493
Переключение контекста (Context Switch)
Переключение процессора с выполнения одного процесса на выполнение другого. Оно называется переключением контекста, поскольку состояние каждого процесса называется его контекстом. Переключение контекста выполняется в ядре программой, которая называется диспетчером или планировщиком.
Покрывающее условие (Covering Condition)
Механизм синхронизации, используемый с мониторами. Процесс передает сигнал условной переменной, когда можно продолжить выполнение ожидающих процессов. Условие, связанное с этой переменной, "покрывает" настоящие условия, которых ожидают процессы.
Постусловие (Postcondition)
Условие, истинное после выполнения оператора.
Поток (Thread)
Последовательная программа, которая имеет свой собственный поток управления (контекст) и может выполняться одновременно с другими потоками. Потоки соревнуются за время одного и того же процессора или выполняются параллельно на разных процессорах.
Предусловие (Precondition)
Условие, истинное перед выполнением оператора.
Программа, параллельная по данным (Data Parallel Program)
Программа, в которой все процессы выполняют (обычно одновременно) одни и те же действия над разными частями разделяемых данных.
Программа, параллельная по задачам (Task Parallel Program)
Программа, в которой каждый процесс выполняет отдельную задачу и, следовательно, является отдельной последовательной программой.
Программа типа "клиент-сервер" (Client/Server Program)
Схема взаимодействия процессов в распределенной программе. Процесс-сервер управляет ресурсом и реализует операции над этим ресурсом. Клиент посылает запрос на сервер, активизируя одну из операций сервера.
Процесс-фильтр (Filter Process)
Процесс, который получает (считывает) данные из одного или нескольких входных каналов, вычисляет функцию и отправляет (записывает) результаты в один или несколько выходных каналов. Процесс-фильтр является одновременно производителем и потребителем и может использоваться в конвейере.
Распределенная программа (Distributed Program)
Программа, в которой процессы взаимодействуют с помощью передачи сообщений, удаленного вызова процедур или рандеву. Обычно процессы выполняются на разных процессорах.
Распределенная разделяемая память (Distributed Shared Memory — DSM)
Программная реализация разделяемого адресного пространства на мультипроцессоре с распределенной памятью или на сети процессоров.
494 Словарь
Рекурсивный параллелизм (Recursive Parallelism)
Тип параллелизма, возникающего в результате совершения параллельных рекурсивных вызовов. Часто это происходит при распараллеливании последовательных программ, использующих парадигму "разделяй и властвуй" для решения все уменьшающихся задач.
Свойство безопасности (Safety Property)
Свойство программы, утверждающее, что ничего опасного не произойдет, т.е. что программа никогда не достигнет опасного состояния. Частичная корректность, взаимное исключение и отсутствие взаимных блокировок — типичные примеры свойства безопасности.
Свойство живучести (Liveness Property)
Свойство программы, утверждающее, что нечто надлежащее в конце концов произойдет, т.е. программа в конце концов достигнет "хорошего" состояния. Примерами данного свойства являются завершение и возможный вход в критическую секцию.
Свойство "не более одного" (At-Most-Once Property)
Свойство оператора присваивания х = е, в котором либо а) х не читается другим процессом, а е содержит не более одной ссылки на переменную, изменяемую другим процессом, либо б) х не изменяется другими процессами, а е не содержит ссылок на переменные, изменяемые другими процессами.
Такой оператор присваивания выполняется неделимым образом.
Симметричный мультипроцессор (Symmetric Multiprocessor — SMP)
Архитектура мультипроцессоров с разделяемой памятью, в которой все процессоры идентичны, и каждый получает доступ к любому слову памяти за одно и то же время.
Синхронизация (Synchronization)
Взаимодействие между процессами, управляющее порядком их выполнения; см. также Взаимное исключение и Условная синхронизация.
Синхронная параллельная программа (Parallel Program)
Программа, в которой каждый процесс выполняется на своем собственном процессоре, т.е. процессы выполняются параллельно. (Вместе с тем, этот термин иногда употребляется по отношению к любой "многопроцессной" программе.)
Состояние гонок (Race Condition)
Ситуация в параллельной программе с разделяемыми переменными, когда один процесс записывает в переменную, которая должна читаться в другом процессе, но продолжает выполнение ("вырывается вперед") и вновь изменяет эту переменную до того, как второй процесс увидит результат первого изменения. Обычно это приводит к некорректно синхронизированной программе.
Состояние программы (State of a Program)
Значения всех переменных программы в некоторый момент времени.
Справедливость (Fairness)
Свойство диспетчера или алгоритма, гарантирующее, что каждый отложенный процесс получит шанс на продолжение: см. также Стратегия планирования.
Словарь 495
Стратегия планирования (Scheduling Policy)
Алгоритм, по которому определяется очередность действий, т.е. порядок выполнения процессов. Стратегия планирования бывает: а) безусловно справедливой, если безусловные неделимые действия в конце концов выполняются; б) справедливой в слабом смысле, если условные неделимые действия в конце концов выполняются после того, как условие задержки стало и остается истинным, в) справедливой в сильном смысле, если условные неделимые действия в конце концов выполняются в ситуации, в которой условие задержки бывает истинным бесконечно часто.
Схема доказательства (Proof Outline)
Программа с добавленными утверждениями, достаточными для того, чтобы убедить читателя в ее корректности. В полной схеме доказательства утверждение ставится до и после каждого оператора.
Тройка (Triple)
Формула логики программирования вида { Р } S { Q }, где Р и Q — предикаты, as — список операторов. Интерпретация тройки следующая: если выполнение S начинается в состоянии, удовлетворяющем Р, и заканчивается, то заключительное состояние удовлетворяет Q.
Ускорение (Speedup)
Отношение т;/Тр, где т,— время выполнения последовательной программы на одном процессоре, тр — параллельной программы на р процессорах.
Условная синхронизация (Condition Synchronization)
Тип синхронизации, при котором выполнение процесса приостанавливается до тех пор, пока не станет истинным некоторое булево условие в. Обычно это реализуется с помощью ожидания одним процессом события, о котором сигнализирует другой процесс.
Условное неделимое действие (Conditional Atomic Action)
Неделимое действие, которое должно быть отложено, пока некоторое булево условие в не станет истинным. Обычно оно программируется как <awai t (В) S; >.
Утверждение (Assertion)
Предикат, характеризующий состояние программы. Утверждение, помещенное перед оператором в программе, определяет, что этот предикат должен быть истинным каждый раз, когда программа готова к выполнению этого оператора.
Частичная корректность (Partial Correctness)
Свойство программы вычислять желаемый результат при условии, что она завершается.
Ядро (Kernel)
Набор структур данных и примитивных операций (непрерываемых процедур), который управляет процессами, распределяет их между процессорами и реализует взаимодействие высокого уровня и синхронизацию операций типа семафоров или обмен сообщениями.
