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

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

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

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

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

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

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

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

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

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

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

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

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

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

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void addListener(notifyProcedure* listener) {

pthread_mutex_lock(&lock);

if (head == 0) {

...

} else {

...

}

pthread_mutex_unlock(&lock);

}

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

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

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

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

element_t* element = head;

while (element != 0) {

(*(element->listener))(newx);

element = element->next;

}

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

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

void update(int newx) {

x = newx;

// оповещение слушателей.

pthread_mutex_lock(&lock);

element_t* element = head;

while (element != 0) {

(*(element->listener))(newx);

element = element->next;

}

pthread_mutex_unlock(&lock);

}

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