Линеаризуемость
Линеаризу́емость (англ. linearizability) в многопоточном программировании — это свойство программы, при котором результат любого параллельного выполнения процедур (операций) эквивалентен некоторому последовательному выполнению. Для любого другого потока выполнение линеаризуемой операции является мгновенным: операция либо не начата, либо завершена.
Как было показано, линеаризуемость является локальным и неблокируемым свойством.
Локальность означает, что если доказана линеаризуемость операций для нескольких программ в отдельности
(или для операций работающих с разными объектами одной программы),
то программы вместе (операции вместе) также будут линеаризуемы.
В линеаризуемой программе запущенные операции не требуют для своего завершения запуска других операций.
Это свойство неблокируемости.
Кроме того, линеаризуемость упрощает доказательство свойств программ, которые используют линеаризуемые операции,
так как поведение линеаризуемой программы сводится к последовательным выполнениям.
Свойство линеаризуемости во многом сходно с такими свойствами как сериализуемость (англ. serializability), атомарность, последовательная согласованность (англ. sequential consistency).
В отличие от них, линеаризуемость предполагает наличие спецификации, тогда как эти свойства накладывают ограничения только на саму программу.
В некоторых источниках термин атомарность используется как синоним линеаризуемости, в других же означает самолинеаризуемость.
Часто под неформальным понятием потоковой безопасности (англ. thread-safety) понимают именно линеаризуемость.
Понятие линеаризуемости впервые появилось в статье Херлихи и Винга (Wing) 1987 года как модель консистентности для систем с объектной организацией общей памяти . В отличие от всех остальных систем, здесь программы не могут напрямую использовать общие переменные, а только через специальные функции-методы (операции). Для этих систем линеаризуемость совпадает со строгой консистентностью.
Задача проверки линеаризуемости — это частный случай задачи функционального тестирования , в которой проверяется, удовлетворяет ли программа функциональным требованиям к ней, заданным в виде спецификации. Но в отличие от общего случая, здесь спецификация требуется только для последовательных выполнений.
Источник: Википедия
Связанные понятия
Абстракция в информатике представляет собой технику управления сложностью систем.
Мемоизация (запоминание, от англ. memoization (англ.) в программировании) — сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее...
Задача выполнимости формул в теориях (англ. satisfiability modulo theories, SMT) — это задача разрешимости для логических формул с учётом лежащих в их основе теорий. Примерами таких теорий для SMT-формул являются: теории целых и вещественных чисел, теории списков, массивов, битовых векторов и т. п.
В программировании неизменяемым (англ. immutable) называется объект, состояние которого не может быть изменено после создания.
Подробнее: Неизменяемый объект
Аппликативное программирование — один из видов декларативного программирования, в котором написание программы состоит в систематическом осуществлении применения одного объекта к другому. Результатом такого применения вновь является объект, который может участвовать в применениях как в роли функции, так и в роли аргумента и так далее. Это делает запись программы математически ясной. Тот факт, что функция обозначается выражением, свидетельствует о возможности использования значений-функций — функциональных...
Функциональный объект (англ. function object), также функтор, функционал и функционоид — распространённая в программировании конструкция, позволяющая использовать объект как функцию. Часто используется как callback, делегат.
В информатике
объединение (англ. union) представляет собой значение или структуру данных, которое может иметь несколько различных представлений.
Объе́ктно-ориенти́рованное проектирование (ООП) — часть объектно-ориентированной методологии, которая предоставляет программистам возможность оперировать понятием «объект», помимо понятия «процедура» при разработке кода.
Правило одного определения (One Definition Rule, ODR) — один из основных принципов языка программирования C++. Назначение ODR состоит в том, чтобы в программе не могло появиться два или более конфликтующих между собой определения одной и той же сущности (типа данных, переменной, функции, объекта, шаблона). Если это правило соблюдено, программа ведёт себя так, как будто в ней существует только одно, общее определение любой сущности. Нарушение ODR, если оно не будет обнаружено при компиляции и сборке...
Глобальная переменная в программировании — переменная, областью видимости которой является вся программа, кроме специально затенённых областей. Механизмы взаимодействия с глобальными переменными называют механизмами доступа к глобальному окружению или состоянию (англ. global environment, global state). Глобальные переменные могут использоваться для взаимодействия между процедурами и функциями как альтернатива передачи аргументов и возвращения значений.
Точка следования (англ. sequence point) — в программировании любая точка программы, в которой гарантируется, что все побочные эффекты предыдущих вычислений уже проявились, а побочные эффекты последующих ещё отсутствуют.
Старсет — высокоуровневый язык программирования, разработанный под руководством М. М. Гилулы в Институте программных систем РАН в 1991 году.
Недостижимый код часто относят к одному из типов мёртвого кода, такая терминология обычно применяется при рассмотрении исходного кода программ. Однако в теории компиляторов, эти понятия никак не связаны, мёртвым кодом там называют только достижимый, но не влияющий на вывод программы код.
Переопределение метода (англ. Method overriding) в объектно-ориентированном программировании — одна из возможностей языка программирования, позволяющая подклассу или дочернему классу обеспечивать специфическую реализацию метода, уже реализованного в одном из суперклассов или родительских классов. Реализация метода в подклассе переопределяет (заменяет) его реализацию в суперклассе, описывая метод с тем же названием, что и у метода суперкласса, а также у нового метода подкласса должны быть те же параметры...
Уничтожение данных — последовательность операций, предназначенных для осуществления программными или аппаратными средствами необратимого удаления данных, в том числе остаточной информации.
Атака возврата в библиотеку (англ. Return-to-libc attack) — один из видов компьютерных атак, популярных на x86-совместимых машинах и схожие с ними, связанных с переполнением буфера, когда адрес возврата функции на стеке подменяется адресом иной функции в программе, и в последующую часть стека записываются параметры для вызываемой функции. Эта техника позволяет нападающему выполнить какую-либо существующую функцию без необходимости внедрять вредноносный код в программу.
Граф зависи́мостей — ориентированный граф, отображающий соотношение множества элементов некоторой совокупности в соответствии с выбранным транзитивным отношением над ней.
Модели дискретного выбора — экономические (эконометрические) модели, позволяющие описывать, объяснять и прогнозировать выбор между, двумя или более альтернативами (то есть когда множество альтернатив не более чем счетно). Модели дискретного выбора позволяют на основе некоторых характеристик (атрибутов) экономического субъекта или ситуации оценить вероятность выбора той или иной альтернативы.
Подробнее: Дискретный выбор
Автоматическое планирование и диспетчеризация (англ. Automated planning and scheduling, APS) — область задач искусственного интеллекта, касающаяся выполнения стратегии или последовательности действий, обычно для интеллектуальных агентов, автономных роботов и беспилотных аппаратов. В отличие от классических проблем управления и классификации, решения задач данной области комплексны, неизвестны и должны разрабатываться и оптимизироваться в многомерном пространстве.
Вариативный макрос — возможность препроцессором Си при помощи специального макроса объявлять поддержку различного числа аргументов.
Комбинато́рное программи́рование (англ. function-level programming) — парадигма программирования, использующая принципы комбинáторной логики, то есть не требующая явного упоминания аргументов определяемой функции (программы) и использующая вместо переменных комбинаторы и композиции. Является особой разновидностью функционального программирования, но, в отличие от основного его направления, комбинаторное программирование не использует λ-абстракцию).
Неявная
типизация , латентная типизация или утиная типизация (англ. Duck typing) — в ООП-языках — определение факта реализации определённого интерфейса объектом без явного указания или наследования этого интерфейса, а просто по реализации полного набора его методов.
Состояние (англ. State) — поведенческий шаблон проектирования. Используется в тех случаях, когда во время выполнения программы объект должен менять своё поведение в зависимости от своего состояния.
Каркас ное программирование — это стиль компьютерного программирования, основанный на простых высокоуровневых программных структурах, на так называемых фиктивных кодах. Программа каркасов похожа на псевдокод, но при этом допускает синтаксический анализ, компиляцию и тестирования кода. Фиктивный код код будет вставлен в программу каркаса для симуляции обработки и во избежание сообщений об ошибках при компиляции. Он может включать в себя пустые функциональные выражения, или функции, которые возвращают...
Стратегия (англ. Strategy) — поведенческий шаблон проектирования, предназначенный для определения семейства алгоритмов, инкапсуляции каждого из них и обеспечения их взаимозаменяемости. Это позволяет выбирать алгоритм путём определения соответствующего класса. Шаблон Strategy позволяет менять выбранный алгоритм независимо от объектов-клиентов, которые его используют.
Инверсия управления (англ. Inversion of Control, IoC) — важный принцип объектно-ориентированного программирования, используемый для уменьшения зацепления в компьютерных программах. Также архитектурное решение интеграции, упрощающее расширение возможностей системы, при котором поток управления программы контролируется фреймворком.
Функциональная спецификация в системной инженерии и разработке программного обеспечения — это документ, описывающий требуемые характеристики системы (функциональность). Документация описывает необходимые для пользователя системы входные и выходные параметры (например, программная система).
Стековый язык программирования (англ. stack-oriented programming language) — это язык программирования, в котором для передачи параметров используется машинная модель стека. Этому описанию соответствует несколько языков, в первую очередь Forth и PostScript, а также многие ассемблерные языки (использующие эту модель на низком уровне — Java, C#). При использовании стека в качестве основного канала передачи параметров между словами элементы языка естественным образом образуют фразы (последовательное...
Концептуальное программирование - подход к программированию, описанный Э.Х. Тыугу в одноименной книге . К. программирование предполагает оперирование понятиями (концептами), описанными в терминах предметной области, что позволяет использовать ЭВМ на этапе постановки задачи. Достаточно точное описание задачи позволяет ЭВМ автоматически составлять программы для её решения. Характерными особенностями концептуального программирования являются также использование языка предметной области и использование...
Признаковое описание объекта (англ. feature vector) — это вектор, который составлен из значений, соответствующих некоторому набору признаков для данного объекта. Значения признаков могут быть различного, не обязательно числового, типа. Является одним из самых распространённых в машинном обучении способов ввода данных.
Обобщённый алгебраический тип да́нных (англ. generalized algebraic data type, GADT) — один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа, связанного с ним. Сконструированы под влиянием работ об индуктивных семействах в среде исследователей зависимых типов.
Порождающие шаблоны (англ. Creational patterns) — шаблоны проектирования, которые абстрагируют процесс инстанцирования. Они позволяют сделать систему независимой от способа создания, композиции и представления объектов. Шаблон, порождающий классы, использует наследование, чтобы изменять наследуемый класс, а шаблон, порождающий объекты, делегирует инстанцирование другому объекту.
Язык спецификаций — формальный язык, предназначенный для декларативного описания структуры, связей, свойств данных и способов их преобразований, (в отличие от активных языков) без явного упоминания порядка выполняемых действий и использования конкретных значений данных.
Экранирование символов — замена в тексте управляющих символов на соответствующие текстовые подстановки. Один из видов управляющих последовательностей.
Зако́н Амдала (англ. Amdahl's law, иногда также Закон Амдаля-Уэра) — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения...
В статистике метод оценки с помощью апостериорного максимума (MAP) тесно связан с методом максимального правдоподобия (ML), но дополнительно при оптимизации использует априорное распределение величины, которую оценивает.
Подробнее: Оценка апостериорного максимума
Парсер (англ. parser; от parse – анализ, разбор) или синтаксический анализатор — часть программы, преобразующей входные данные (как правило, текст) в структурированный формат. Парсер выполняет синтаксический анализ текста.
Подробнее: Синтаксический анализатор
Итерация в программировании — в широком смысле — организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя (в отличие от рекурсии). В узком смысле — один шаг итерационного, циклического процесса.
Суперкласс позволяет создавать обобщенный интерфейс, заключающий в себе настраиваемую функциональность за счет использования виртуальных функций.
Взаимодействующие последовательные процессы (англ. communicating sequential processes, CSP) — формальный язык для описания моделей взаимодействия в параллельных системах. Относится к математическим теориям параллелизма, известных как исчисление процессов (или алгебра процессов), основанных на передаче сообщений по каналам. Оказал влияние на разработку языка Оккам, Limbo, Go.
Маршалинг (от англ. marshal — упорядочивать) в информатике — процесс преобразования информации (данных, двоичного представления объекта), хранящейся в оперативной памяти, в формат, пригодный для хранения или передачи. Процесс похож на сериализацию (отличия см. ниже). Обычно применяется тогда, когда информацию (данные, объекты) необходимо передавать между различными частями одной программы или от одной программы к другой.
Динамический язык — язык программирования, который позволяет определять типы данных и осуществлять синтаксический анализ и компиляцию «на лету», на этапе выполнения программы. Динамические языки удобны для быстрой разработки приложений.
Высший тип (top type) в теории типов, часто обозначаемый как просто вершина или «закрепленным» символом (⊤), — универсальный тип, то есть такой тип, который содержит в себе каждый возможный объект в нужной системе типов. Высший тип иногда именуется универсальным супертипом, то есть все остальные типы в любой отдельно взятой системе типов являются подтипами самого верхнего. Это является противоположностью нижайшего типа, или иначе именуемого универсальным подтипом, который представляет собой тип...
В программировании
тип возвращаемого значения (англ. return type) или тип результата (англ. result type) определяет и накладывает ограничения на тип данных, возвращаемых методом или функцией. Во многих языках программирования (особенно это касается языков со статической типизацией, как например, Java, C++ и Си) возвращаемый тип должен быть явно указан при объявлении функции.
Фьютекс (англ. futex, сокращение от англ. fast userspace mutex) — в программировании способ реализации семафоров и мьютексов POSIX в Linux. Впервые введены в ядро Linux с версии 2.5.7 (development); выработана стабильная семантика с 2.5.40; включаются в стабильные версии серии 2.6.x.
Отделение
содержания от представления (или «разделение формы и содержания») это общепринятая идиома, философия дизайна и методология, применяемая в контексте различных издательских технологических дисциплинах, включая информационный поиск, обработку шаблонов, веб-дизайн, веб-программирование, обработку текста, компьютерную вёрстку и разработку управляемую моделями. Это конкретный случай более общей философии разделения ответственности.
Охра́на (охраня́ющее выраже́ние, охранное выражение) — логическое выражение, которое предназначено для ограничения вычислительных процессов и выбора варианта вычислений. Обычно, используется в функциональных языках программирования (например, Haskell, Erlang).