Организация вычислений в компонентах. 2 страница

Программа main использует функции, определенные на рис. 78:

Она дважды регистрирует print как callback-функцию, затем выполняет update (устанавливает x = 1), снова регистрирует print и в завершении, снова выполняет update (устанавливает x = 2). Функция print просто выводит на дисплей текущую величину. В процессе работы программы на дисплее появится последовательность 1 1 2 2 2.

Си-программа специфицирует последовательность шагов, в которой каждый шаг изменяет состояние памяти в MPS. В Си-программе состояние представляется значениями переменных.

В программе на рис. 78 состояние памяти включает значение глобальной переменной ‘x’ и список элементов указываемых переменной head (другая глобальная переменная). Сам список представляется как связанный список, в котором каждый элемент является указателем (адресом) функции, которая вызывается при изменении ‘x’. Во время выполнения Си-программы в состояние памяти включается также стек содержащий локальные переменные. Используя EFSM можно смоделировать выполнение простой С-программы, предполагая, что программа имеет фиксированное и ограниченное число переменных. Переменные Си-программы будут переменными EFSM. Состояния EFSM соответствуют места в программе, а переходы – выполнению программы.

На рис. 79 приведена модель функции update из примера на рис. 78. Тип сигнала pure (строгий) означает, что в каждый момент либо сигнал отсутствует (нет события), либо присутствует (есть событие). Такой сигнал не переносит значений, а лишь свидетельствует о присутствии.

Рис. 79. Пример модели Си-программы «шаблон observer»

Автомат переходит из начального состояния Idle, когда вызывается функция update. Вызов сигнализирует о наличии входного аргумента типа int. Когда выполняется этот переход, newx (в стеке) будет присвоено значение аргумента и глобальная переменная ‘x’ получит обновление. После первого перехода EFSM попадает состояние 31 (соответствует оператору element_t* element = head;).

Затем следует безусловный переход в состояние 32 (while(element!= 0)) и устанавливается значение element. Из состояния 32 есть два варианта перехода. Если element = 0, то EFSM перейдет и состояние Idle с выходным значением return (возврат из функции), иначе переход в состояние 33. Переход из состояния 33 в 34 сопровождается вызовом функция listener с аргументом равным переменной newx из стека. Переход из 34 обратно в 32 выполняется после получения сигнала returnFromListener, индицирующего возврат из listener.

При построении модели подобной рис. 79, необходимо решить на каком уровне детализации остановится, решить какие действия считать

атомарными (неделимыми). В приведенном примере строки Си-программы используются в качестве уровня детализации. Но нет гарантии, что строки выполняются как атомарные действия. К тому же точные модели Си-программ часто не являются конечными автоматами. Для кода на рис. 78 модель конечного автомата неприемлема, т.к. она поддерживает регистрацию произвольного числа слушателей. Для функции main из примера модель конечного автомата устраивает, т.к. число регистраций конечно (всего три). Проблема усиливается при добавлении возможностей по одновременному выполнению программ. Поэтому многие разработчики предпочитают работать на верхнем уровне абстракций языков проектирования и не связываться с промежуточными уровнями.

2.5.2. Потоки

Потоки (thread или тред) – императивные программы, которые выполняются одновременно и разделяют (совместно используют) адресное пространство. Одновременность выполнения опирается на механизм прерываний, имеющийся во всех микропроцессорах.

Большинство ОС обеспечивают высокоуровневый механизм противоположно прерываниям для императивных программ с разделяемой памятью. Механизм выступает в форме коллекции процедур, которые программист может использовать. Такие процедуры обычно соответствуют стандартизованным API (application program interface), которые дают возможность писать переносимые программы (работают на различных процессорах и ОС).

Таким API, например, является Pthreads (или POSIX threads), интегрированным во многие современные ОС. Pthreads определяют множество Си-типов, функций и констант. Они стандартизованы IEEE в 1988 для унификации вариантов ОС Unix. В Pthreads поток определяется Си-функцией и создается вызовом функции создания потока.

На рис. 80 показана простая многопоточная Си-программа, использующая Pthreads. printN (строки 3 – 9) – функция, которую поток начинает выполнять при старте, называют стартовой подпрограммой. Стартовая

	1 #include<pthread.h> 2 #include<stdio.h> 3 void* printN(void* arg) { 4 inti; 5 for(i = 0; i < 10; i++) { 6 printf("My ID: %d\n", *(int*)arg); 7 } 8 returnNULL; 9 }

Рис. 80. Простая многопоточная программа на Си, использующая Pthreads

подпрограмма печатает передаваемый аргумент 10 раз и завершается. Функция main создает два потока (строки 14, 15), каждый из которых будет выполнять стартовую подпрограмму. Первый создаваемый поток будет печатать значение 1, а второй – 2. Когда запускаются эта программы, значения 1 и 2 в некотором чередующемся порядке, зависящим от планировщика задач. Обычно повторное выполнение вызовет отличный чередующийся порядок 1 и 2.

Функция pthread_create создает поток и сразу завершается. Стартовая

подпрограмма может не начать выполняться перед выходом из pthread_create. Строки 17 и 18 используют функцию pthread_join для того чтобы главная программа main не завершилась перед завершением работы потоков. Без этих строк запущенная программа не сможет произвести требуемые результаты всеми потоками.

Во встроенных приложениях широко распространено объявление стартовой подпрограммы как бесконечного цикла, т.е из нее невозможно выйти. Например, стартовая подпрограмма может «вечно» выполняться, периодически выполняя вывод информации на дисплей. Если стартовая подпрограмма не возвращается, тогда некоторый другой поток, который вызывает

для нее pthread_join, будет навсегда заблокирован.

Как показано на рис.80 стартовая подпрограмма может иметь аргумент и возвращать значение. Четвертый аргумент pthread_create является адресом аргумента, который передается в стартовую подпрограмму. Важно понимать модель памяти Си, иначе возможны очень тонкие ошибки. Предположим, создается поток внутри следующей функции:

Этот код является некорректным, так как аргумент стартовой подпрограммы задается указателем на переменную в стеке. Во время когда поток обращается к оговоренному адресу памяти, функция createThread с вероятностью может завершиться и адрес памяти может быть перезаписан кем-нибудь следующим, попавшим в эту область стека.

2.5.2.1. Реализация потоков

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

Первый ключевой вопрос как и когда вызывается планировщик.

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

Главный недостаток кооперативной многозадачности состоит в том, что программа может выполняться очень долго без вызовов сервисов, когда бы могли стартовать другие потоки. Для коррекции этого большинство ОС включает подпрограмму обработки прерываний, которая запускается через фиксированный интервал времени. Это подпрограмма обслуживает системные часы, которые обеспечивают прикладные программы механизмом получения текущего времени дня и разрешают периодический вызов планировщика через прерывание таймера. Для ОС с системными часами период вызова обработчика прерываний системных часов является «мигом» (тик). Для версий Linux этот период варьируется от 1 до 10 ms.

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

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

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

2.5.2.2. Взаимное исключение

Поток может быть приостановлен между двумя атомарными операциями для выполнения другого потока и/или обработки прерывания. Это делает максимально трудным рассуждение о взаимодействии между потоками.

Рассмотрим функцию addListene из примера 78. Предположим, что она вызывается больше чем в одном потоке. Что может произойти неправильно. Первое, два потока могут одновременно модифицировать список связей структуры данных, что может привести к искажению данных. На рис. 81 приведены результаты моделирования этого асинхронного взаимодействия потоков. Предположим, например, что поток 1 приостановлен перед выполнением оператора tail->listener = listener. Предположим, что пока поток 1 приостановлен другой поток 2 вызывает addListene.

Когда поток 1 снова получает управление, он начинает выполняться с оператора tail->listener = listener, но значение указателя tail уже изменено потоком 2. Оно больше не является величиной, вычисленной предыдущим оператором tail = tail->next, до приостановки потока 1. Анализ показывает, что это может закончиться случайным указателем на listener (случайное значение после выделения памяти функцией malloc) в элементе списка i+1. Второй слушатель, добавленный в список потоком 2, будет перезаписан потоком 1 и таким образом будет утрачен. Когда вызывается функция update, она пытается выполнить действия со случайным адресом listener?, что может окончиться ошибкой сегментации или еще хуже, выполнением случайного кода.

Рис. 81. Результат одновременного изменения связанного списка двумя потоками

Подобные проблемы известны под названием состояние гонок (состязания). Две одновременных части кода в предыдущем примере состязались за доступ к одному и тому же ресурсу и порядок, в котором они получали доступ, влиял на результат. Не все состязания являются такими плохими с катастрофическими последствиями как в примере. Один из путей предотвращения этого несчастья состоит в использовании замка для взаимного исключения или мутекса (mutex). В Pthreads мутексы реализуются созданием структуры, называемой pthread mutex. Например можно модифицировать функцию addListener следующим образом:

В первой строке создается и инициализируется глобальная переменная lock.

В первой строке функции addListener берет замок. Принцип такой, что только один поток может владеть замком в каждый момент времени. Функция mutex_lock блокирует поток пока вызывающий поток не получит замок. Итак, когда addListener вызывается потоком и начинает выполняться, pthread mutex не возвращает замок, пока им владеет другой поток. Получив замок, вызывающий поток сохраняет его за собой. Функция pthread_mutex_unlock вызывается в конце для освобождения замка. В многопоточном программировании серьезной ошибкой является не освободить замок.

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

Функция update из примера на рис.78 не модифицирует список слушателей, она его только читает. Предположим, что поток A вызывает addListener и откладывается после выполнения оператора tail->next = malloc(sizeof (element_t)). Предположим, что пока A отложен другой поток B вызывает update с кодом:

Что случится при выполнении оператора element = tail->next? В этой точке поток B будет работать со случайным содержимым, полученным от malloc при работе потока A, вызывая функцию отсылаемую указателем element->listener. И снова это приведет к ошибке сегментации или того хуже.

Мутех, добавленный в предыдущем примере, не устраняет этих ошибок. Он не защищает поток A от перевода в состояние отложен. Таким образом, необходимо защитить все возможные доступы к структуре данных с помощью мутексов. Модифицируем update следующим образом:

Это защитит функцию update от чтения списка, пока не закончится его модификация другим потоком.

2.5.2.3. Взаимная блокировка

Большое количество мутексов в программах увеличивает риск взаимной блокировки (deadlock). Взаимоблокировка имеет место, когда некоторые потоки становятся постоянно блокированными пытаясь получить замки. Например, если поток A сохраняет замок 1 и затем блокируется при попытке получить замок 2, которым владеет поток B, затем блокируется B при попытке получить замок 1. От таких «смертельных объятий» не спастись. Программа должна быть прервана.

Предположим что функции addListener и update на рис. 73 защищены мутексом, как и двух предыдущих примерах. Update содержит строку (*(element->listener))(newx), которая вызывает функцию, указанную в элементе списка. Разумно для этой функции получить замок мутекса. Предположим, например, что функции слушателя необходимо обновить дисплей. Дисплей типичный разделяемый ресурс и, следовательно, должен быть защищен собственным замком мутекса. Предположим, что поток A вызывает функцию update, которая достигает оператора (*(element->listener))(newx) и затем блокируется, т.к. функция слушателя пытается получить другой замок, которым владеет B. Предположим затем, что поток B вызывает addListener, что приводит к взаимной блокировке.

Взаимную блокировку трудно преодолеть. В классической статье [27] даются необходимые условия возникновения взаимной блокировки, некоторые из которых могут быть удалены для преодоления взаимной блокировки. Простая техника состоит в использовании только одного замка для всей многопоточной программы. Эта техника, однако, не приводит к высокомодульной программе. Более того она может затруднить удовлетворению ограничениям реального времени, т.к. некоторые разделяемые ресурсы (например дисплей) могут нуждаться в достаточно длительном удержании, что приведет к просрочке времени исполнения другими потоками.

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

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

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

2.5.2.4. Модели непротиворечивости памяти

Еще одна весьма тонкая проблема потоков связана с моделью памяти программы. Некоторые отдельные реализации потоков исходят из определенной модели непротиворечивости (консистентности) памяти, определяющей как переменные, которые читаются и записываются разными потоками, кажутся этим потокам. Интуитивно подразумевается, что чтение переменной должно иметь своим результатом последнее, записанное в переменную значение, но что означает «последняя». Рассмотрим, например, сценарий, где все переменные инициализируются значением 0 и поток A выполняет два оператора:

Тогда как поток B выполняет следующие два оператора:

Интуитивно получаем, что после выполнения потоками этих операций мы должны надеяться, что хотя бы одна из двух переменных w и z имеют значение 1. Такая гарантия относится к последовательной непротиворечивости. Это означает, что результат любого выполнения точно такой же, как если бы операции всех потоков всегда выполнялись в некотором порядке и операции каждого индивидуального потока всегда появлялись в этой последовательности в порядке, определенном в потоке.

Однако последовательная непротиворечивость не гарантируется большинством (или возможно всеми) реализаций Pthreads. Обеспечение такой гарантии весьма трудно для современных процессоров, использующих современные компиляторы. Компилятор, например, свободен в вариантах переупорядочивании команд в каждом из потоков, т.к. не существует зависимости между ними (так это может казаться компилятору). Даже если компилятор не переупорядочивает команды, это может сделать аппаратура. Поэтому для доступа к разделяемым переменным остается лишь использовать взаимоисключающие замки и надеяться, что они реализованы корректно. О проблемах непротиворечивости памяти можно посмотреть в [28], [29].

2.5.2.5. Проблемы с потоками

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

В примере на рис. 73 можно устранить потенциальную взаимоблокировку, использую простой трюк, но он приводит к коварным ошибкам (не возникают при тестировании, не извещаются при наличии). Предположим, функция update модифицирована следующим образом:

voidupdate(intnewx) { x = newx; // копирование списка в headc и tailc pthread_mutex_lock(&lock); element_t* headc = NULL; element_t* tailc = NULL; element_t* element = head; while(element!= 0) { if(headc == NULL) { headc = malloc(sizeof(element_t)); headc->listener = head->listener; headc->next = 0; tailc = headc; } else{ tailc->next = malloc(sizeof(element_t)); tailc = tailc->next; tailc->listener = element->listener; tailc->next = 0; } element = element->next; } pthread_mutex_unlock(&lock); // извещение пользователей с помощью копии списка element = headc; while(element!= 0) { (*(element->listener))(newx); element = element->next; } }

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

Этот код, однако, имеет потенциально серьезную проблему, которая не может быть обнаружена тестированием. Предположим, что поток A вызывает update с аргументом newx = 0, индицирующим, что «все системы в норме». Предположим, что поток A отложен сразу после освобождения замка, но перед выполнением оповещения. Предположим, что пока он отложен поток B вызывает update с аргументом newx = 1, означающим «авария! двигатель в огне!». Предположим, что этот вызов update завершается перед тем как поток A получает шанс на выполнение. Когда поток A получает разрешение на выполнение, он будет оповещать всех слушателей, но неправильным значением! Если один из слушателей обновляет дисплей пилота самолета, дисплей будет показывать, что все нормально, когда фактически двигатель объят пламенем. Нетривиальные многопоточные программы очень трудно понимать. Они могут содержать коварные ошибки, состязания и взаимоблокировку. Проблемы многопоточных программ могут оставаться незамеченными годы даже при интенсивном использовании программ. Эти проблемы очень важны для встроенных систем т.к. оказывают влияние на безопасность и средства существования. Фактически каждая встроенная система включает параллельное программное обеспечение, потому инженеры, проектирующие встроенные системы должны противостоять всевозможным ловушкам.

2.5.3. Процессы и передача сообщений

Процессы есть императивные программы с собственным адресным пространством. Эти программы не могут ссылаться на переменные друг друга и следовательно не имеют проблем потоков. Взаимодействия между программами происходят через механизмы ОС, микроядра или библиотеки.

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

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

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

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

Пример простой программы передачи сообщений приведен на рис. 82.

Эта программа использует шаблон producer/consumer, в которой один поток генерирует последовательность сообщений, а второй поток их потребляет. Такой шаблон может быть использован для реализации рассмотренного ранее шаблона observer без риска взаимной блокировки и без коварных ошибок предыдущих разделов. Функция update всегда выполняться в различных потоках наблюдателей и генерирует сообщения, потребляемые наблюдателями.

1 void* producer(void* arg) { 2 inti; 3 for(i = 0; i < 10; i++) { 4 send(i); 5 } 6 returnNULL; 7 } 8 void* consumer(void* arg) { 9 while(1) { 10 printf("received %d\n", get()); 11 } 12 returnNULL; 13 } 14 intmain(void) { 15 pthread_t threadID1, threadID2; 16 void* exitStatus; 17 pthread_create(&threadID1, NULL, producer, NULL); 18 pthread_create(&threadID2, NULL, consumer, NULL); 19 pthread_join(threadID1, &exitStatus); 20 pthread_join(threadID2, &exitStatus); 21 return0; 22 }

Рис.82. Пример простой программы передачи сообщений

Функция producer (стартовая функция потока-отправителя) в строке 4 вызывает send (должна быть определена) для отправки сообщения в виде целого значения. Функция consumer обеспечивается тем что, get не возвратится пока она реально не получила сообщение. Заметим, что в этом случае consumer никогда не вернется. Эта программа не завершается собственными средствами.

Реализация send и get с использованием Pthreads приведена на рис. 83.

Реализация использует связанный список подобный рис. 78, но нагрузка является целой величиной. Связанный список реализован как неограниченная очередь с дисциплиной FIFO (first-in, first-out), когда новый элемент помещается в tail (хвост), а старые элементы удаляются из head (головная часть).

Рассмотрим первой реализацию send. Она использует мутекс для того чтобы send и get одновременно не модифицировали связанный список. В дополнении она использует переменную условия для взаимодействия с процессом consumer, который изменяет размер очереди. Переменная условия sent объявляется и инициализируется в строке 7. В строке 23 поток producer вызывает функцию pthread_cond_signal, которая «пробуждает» другой поток, блокированный переменной условия, если такой поток существует.

Рис.83. Функции send и get для передачи сообщений

Чтобы увидеть что означает «пробуждает» другого потока, посмотрим на функцию get. В строке 31, если поток вызывающий get обнаружил, что размер очереди равен 0, тогда он вызывает pthread_cond_wait, который будет блокировать поток до тех пор, пока некоторый другой поток не вызовет pthread_cond_signal. (Существуют другие условия, которые заставят вернуться из pthread_cond_wait, так код должен периодически ждать пока не обнаружит отличный от нуля размер очереди).

Критично то, что функции pthread_cond_signal и pthread_cond_wait вызываются, пока владеют замком мутекса. Предположим, что строки 23 и 24 переставлены местами и pthread_cond_signal была вызвана после освобождения замка мутекса. Тогда в этом случае будет возможным вызов pthread_cond_signal пока поток consumer приостановлен (но еще не заблокирован) между строками 30 и 31. В этом случае, когда поток consumer разрешен для работы, будет исполнена строка 31 и наступит блокировка ожидания сигнала. Но сигнал уже был послан и он не может быть послан повторно, так что поток consumer будет постоянно блокироваться.