Модель исполнения - Execution model

Выполнение программы
Общие понятия
Типы кода
Стратегии компиляции
Заметное время выполнения
Известные компиляторы и инструментальные средства

Язык программирования состоит из грамматики / синтаксиса плюс модель исполнения. Модель выполнения определяет поведение элементов языка. Применяя модель выполнения, можно получить поведение программы, написанной на этом языке программирования. Например, когда программист «читает» код в уме, он проходит через то, что делает каждая строка кода. По сути, они имитируют поведение внутри своего разума. Программист применяет модель выполнения к коду, что приводит к поведению кода.

У каждого языка программирования есть модель выполнения, которая определяет способ, которым единицы работы (обозначенные программой синтаксис ) находятся по расписанию за исполнение. Подробные примеры спецификации моделей исполнения нескольких популярных языков включают Python,[1] модель исполнения языка программирования Unified Parallel C (UPC),[2]обсуждение различных классов модели исполнения, например, для императивных и функциональных языков,[3] и статья, в которой обсуждаются модели выполнения для встроенных языков реального времени.[4]

Детали модели исполнения

Операционная семантика - это один из методов определения модели исполнения языка. Наблюдаемое поведение выполняющейся программы должно соответствовать поведению, производному от операционной семантики (которая определяет модель выполнения языка).

Модель выполнения охватывает такие вещи, как то, что является неделимой единицей работы и каковы ограничения на порядок, в котором эти единицы работы могут иметь место. Например, операция сложения - это неделимая единица работы во многих языках, а в последовательных языках такие единицы работы должны выполняться одна за другой.

Чтобы проиллюстрировать это, рассмотрим Язык программирования C, как описано в книге Керниган и Ричи.[5]В C есть понятие, называемое оператором. Спецификация языка определяет оператор как фрагмент синтаксиса, заканчивающийся знаком «;». Затем в спецификации языка говорится, что «выполнение программы выполняется последовательно одно за другим». Эти слова: «выполнение программы выполняется один оператор за другим, последовательно» - это одна из частей модели выполнения C! Эти слова говорят нам, что операторы являются неделимыми единицами работы и что они выполняются в том же порядке, что и их синтаксическое появление в коде (кроме случаев, когда оператор управления, такой как IF или FOR, изменяет порядок). Утверждая, что «выполнение программы выполняется последовательно одно за другим», модель программирования установила ограничения на порядок выполнения единиц работы.

На самом деле язык C имеет дополнительный уровень к своей модели выполнения, который является порядком приоритета. Порядок приоритета устанавливает правила для порядка операций внутри одного оператора. Порядок приоритета можно рассматривать как указание ограничений на выполнение единиц работы, которые находятся в пределах одного оператора. Так, ";" а «IF» и «WHILE» охватывают ограничения на порядок операторов, в то время как порядок приоритета охватывает ограничения на работу внутри оператора. Следовательно, эти части спецификации языка C также являются частью модели выполнения языка C.

Модели выполнения также могут существовать независимо от языков программирования, примерами которых могут быть: Потоки POSIX библиотека и Hadoop Map-Reduce модель программирования. Реализация модели выполнения может быть через компилятор, или же устный переводчик, и часто включает система времени выполнения.

Реализация модели выполнения контролирует порядок, в котором работа выполняется во время выполнения. Этот порядок может быть выбран заранее, в некоторых ситуациях, или он может быть определен динамически по мере выполнения. Большинство моделей исполнения допускают то и другое в разной степени. Например, язык C фиксирует порядок работы внутри оператора и фиксирует порядок всех операторов, кроме тех, которые включают оператор IF или форму оператора цикла. Следовательно, большая часть порядка выполнения может быть выбрана статически до начала выполнения, но небольшая часть должна выбираться динамически по мере продолжения выполнения.

Статические варианты чаще всего реализуются внутри компилятор, и в этом случае порядок работы представлен порядком, в котором инструкции помещаются в исполняемый двоичный файл. Затем динамический выбор будет реализован внутри языка система времени выполнения. Система времени выполнения может быть библиотекой, которая вызывается инструкциями, вставленными компилятор, или исполняющая система может быть встроена в исполняемый файл напрямую, например, путем вставки инструкций ветвления, которые динамически выбирают, какую работу выполнять следующей.

Однако устный переводчик также может быть сконструирован для любого языка, и в этом случае все решения о порядке выполнения являются динамическими. An устный переводчик можно рассматривать как частный транслятор и реализацию модели выполнения части.


Модель выполнения на языке ассемблера по сравнению с реализацией микроархитектурой

У языков ассемблера также есть модели исполнения, как и у любого другого языка. Такая модель исполнения реализуется микроархитектурой ЦП. Например, и пятиступенчатый конвейер по порядку, и большой ЦП с нарушением порядка реализуют одну и ту же модель выполнения на языке ассемблера. Модель выполнения - это определение поведения, поэтому все реализации, будь то упорядоченные или неупорядоченные, интерпретируемые или JIT и т. Д., Должны давать точно такой же результат, и этот результат определяется моделью выполнения. .

Модели параллельного выполнения

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

Например, распространенной конструкцией синхронизации является блокировка. Рассмотрим одну временную шкалу. На временной шкале есть точка, в которой выполняется синхронизирующая конструкция «получение владения блокировкой». В потоках Posix это будет pthread_mutex_lock (& ​​myMutex). В Java это будет lock.lock (). В обоих случаях временная шкала называется потоком. Модели исполнения C и Java являются последовательными, и они заявляют, что на временной шкале есть действия, которые предшествуют вызову, чтобы «получить право владения блокировкой», и действия, которые выполняются после вызова. Аналогичным образом существует операция «отказаться от владения блокировкой». В C это будет pthread_mutex_unlock (& ​​myMutex). В Java это будет lock.unlock (). Опять же, модели выполнения C и Java определяют, что одна группа операторов выполняется до того, как право владения блокировкой перестанет принадлежать, а другая группа операторов выполняется после того, как владение блокировкой будет отказано.

Теперь рассмотрим случай с двумя временными шкалами, также известными как два потока. Один поток, назовите его потоком A, выполняет некоторые операторы, называя их операторами A-pre-gain-lock. Затем поток A выполняет «получение права владения блокировкой», затем поток A выполняет операторы A-post-gain-lock, которые поступают после того, как A получает право владения блокировкой. Наконец, поток A выполняет «отказ от владения блокировкой». Затем поток A выполняет операторы A-post-giveup-lock.

Второй поток, назовите его потоком B, выполняет некоторые операторы, называя их операторами предварительной блокировки B. Затем поток B выполняет «получение владения блокировкой», затем поток B выполняет операторы B-post-lock, которые появляются после того, как B получает право владения блокировкой.

Теперь мы можем сказать, что это модель параллельного выполнения конструкции синхронизации «получить право владения блокировкой» и «отказаться от владения блокировкой». Модель исполнения такова:

«В случае, если владение блокировкой переходит от потока A к потоку B, операторы A-post-gain-lock предшествуют операторам B-post-gain-lock».

И это все.

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

Обратите внимание, что единственный эффект заключается в том, что операторы A-post-gain-lock предшествуют операторам B-post-gain-lock. Никакого другого эффекта не происходит, и нельзя полагаться на другой относительный порядок. В частности, A-post-give-up-lock и B-post-gain-lock имеют нет относительного порядка определено, что удивляет многих. Но поток A мог быть заменен после отказа от владения, поэтому операторы A-post-give-up-lock могут произойти спустя долгое время после завершения многих операторов B-post-gain-lock. Это одна из возможностей, о которой необходимо подумать при разработке блокировок, и она показывает, почему многопоточное программирование сложно.

Обратите внимание, что в современных параллельных языках гораздо проще использовать модели выполнения. Модель потоков была одной из исходных моделей параллельного выполнения, что может объяснить, почему она сохранилась, несмотря на сложность в использовании.

Смотрите также

Рекомендации

  1. ^ «Документация Python: модель выполнения».
  2. ^ «Возможности языка UPC».
  3. ^ Cardoso, J.M.P .; Диниз, П. (2011). Языки программирования и модели исполнения. Springer США. ISBN  9780387096711.
  4. ^ PELLIZZONI, R .; BETTI, E .; БАК, С .; ЯО, Г .; CRISWELL, J .; КАККАМО, М. и КЕГЛИ, Р. (2011). «Прогнозируемая модель выполнения для встроенных систем на основе COTS» (PDF). Симпозиум по технологиям реального времени и встроенным технологиям и приложениям. IEEE.
  5. ^ Керниган, Брайан В.; Деннис М. Ричи (Февраль 1978 г.). Язык программирования C (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice Hall. ISBN  0-13-110163-3.