Трассировка многопоточной программы
Могопоточность — наличие в алгоритме нескольких потоков управления, которые выполняются одновременно. При описании таких алгоритмов на Java к примеру, имеется множество разных средств: потоки, асинхронные задачи, пулы потоков. Различают потоки ядра и легковесные потоки. Потоки первого вида реально могут выполняться одновременно в случае наличия достаточного числа ядер процессора (аппаратная многопоточность). А второй вид потоков (т.н. нити) создаются, когда число параллельных задач заведомо превосходит аппаратные возможности и создаётся иллюзия одновременного их выполнения путём переключения контекста с одной нити на другую (программная многопоточность).
Составим таблицу трассировки для программы барьера:
| AX | I | wait | II | AX | |
| ? | 1 | 1 | 0 | ? | первый поток пришёл |
| 2 | 2 | 2 | 1 | второй поток пришёл | |
| 3 | 0 | 2 | 2 | первый сравнил и обнулил | |
| 4 | 0 | 3 | второй сравнил | ||
| 1 | 5 | 0 | 4 | и прыгнул | |
| 1 | 6 | 0 | 8 | первый даёт положительный ответ, что он якобы вышел последним | |
| ? | 0 | 9 | а второй, тем временем обнаруживает, что ждущих потоков не осталось и пропускает цикл ожидания | ||
| 1 | 1 | 10 | 0 | при выходе первый поток даёт отрицательный ответ, что якобы ещё остались потоки в барьере, хотя и это возможно, ведь первый поток заявил, что барьер пуст, и мог повторно в него войти | |
| 2 | 2 | 1 | 11 | 0 | первый опередил второго и занял лидирующую позицию |
| 3 | 1 | ? | второй в замешательстве, считая что он вышел не последним | ||
| 4 | 2 | 1 | первый прыгает, второй приходит и добавляет к счетчику единицу | ||
| 8 | 2 | 2 | 2 | первый ждет второго, который только собирается сравнить свой номер | |
| 9 | 0 | 3 | первый начал вторую итерацию цикла ожидания, второй в предвкушении скорой победы сбрасывает счетчик ожидающих потоков | ||
| 8 | 0 | 4 | одну секундочку, первый поймал сигнал второго, скоро будет развязка | ||
| 9 | 0 | 5 | 1 | второй устанавливает флажок своего первенства | |
| 0 | 10 | 0 | 6 | 1 | первый подтверждает, что выходит следом за вторым |
| 0 | 11 | 0 | ? | опять получается что последний вышел с отрицательным ответом |
Что менять, что не менять первые две строки, результат может быть неверным. С этим нужно что-то делать. Пусть тот поток, который обнулил счетчик потоков, будет ждать тех, кто его ждал. Тогда получится то, что требует контракт барьера.
MOV AX, threads ; количество потоков в аккумулятор LOCK INC wait ; пришедший поток сам себя посчитал LOCK CMPXCHG wait, 0 ; ветка, отделяющая последний поток JNE idle2 ; остальные прыгают отсуда вниз DEC AX ; в аккумуляторе кол-во потоков - 1 idle1: LOCK CMPXCHG wake, 0 ; ждем, пока все потоки не проснутся JNE idle1 MOV AX, 1 ; выход с положительным ответом RET idle2: CMP wait, 0 ; ждем, пока обнулится счетчик потоков JNZ idle2 LOCK INC wake ; сообщаем, что проснулся XOR AX,AX ; выход с отрицательным ответом RET
Сразу возникают подозрения по поводу новой переменной. Обоснуем их используя трассировочную таблицу.
| AX | I | wait | wake | II | AX | |
| 2 | 1 | 0 | 0 | 1 | 2 | оба потока пришли одновременно |
| 2 | 1 | 0 | - | один из них блокирует шину и увеличивает счетчик | ||
| - | 2 | 0 | 2 | другой делает тоже самое | ||
| 3 | 0 | 0 | - | на первом сработало сравнение с обменом | ||
| 4 | 0 | 0 | 3 | а на втором флажок ZF остался установленным | ||
| 1 | 5 | 0 | 0 | 4 | первый подготовился к циклу ожидания | |
| 7 | 0 | 0 | 12 | второй ждать не намерен | ||
| 8 | 0 | 0 | 13 | первый ждет второго | ||
| - | 0 | 1 | 14 | 0 | второй сообщает, что выходит | |
| 7 | 0 | 0 | 15 | 0 | первый реагирует мгновенно | |
| 8 | 0 | 0 | ? | а второй уже вышел с ответом 0 | ||
| 1 | 9 | 0 | 0 | 1 | 2 | второй пришёл раньше первого |
| 1 | 10 | 1 | 0 | 2 | 2 | первый только выходит; ответ 1 – верно |
| ? | 1 | 0 | 3 | 2 | второй уже выяснил, что позади него кто-то есть | |
| 2 | 1 | 1 | 0 | 4 | а вот и он, явился на горизонте | |
| 2 | 2 | 2 | 0 | 12 | сейчас будет котовасия | |
| 3 | 0 | 0 | 13 | первый сбросил счетчик | ||
| 4 | 0 | 0 | 12 | второй принял уведомление | ||
| 1 | 5 | 0 | 0 | 13 | первый собрасля ждать | |
| - | 0 | 1 | 14 | второй сообщает ему, что ждать не надо | ||
| 7 | 0 | 0 | 15 | 0 | первый соглашается с ним | |
| 8 | 0 | 0 | 16 | 0 | второй завершился с ответом 0 | |
| 1 | 9 | 0 | 0 | ? | первый выходит с ответом 1 | |
| 1 | 10 | 0 | 0 | все верно |
Из приведённой таблицы видно, что дополнительная переменная меняется независимо от другой. Её использование кажется избыточным. Однако, дополнительная переменная становится полезной при выполнении трёх и более потоков.
| I | II | III | wait | wake | |
| 1 | 1 | первые два пришли одновременно | |||
| 2 | - | 1 | 1 | третий немного опоздал | |
| - | 2 | - | 2 | 0 | |
| - | - | 2 | 3 | 0 | |
| 3 | - | - | 0 | ||
| 4 | 3 | - | 0 | ||
| 5 | 4 | 3 | 0 | ||
| 7 | 12 | 4 | |||
| 8 | 13 | - | третий по какой-то причине задержался | ||
| 9 | 14 | - | 1 | ||
| 10 | 15 | 12 | 0 | и тут заметна роль новой переменной | |
| ? | 16 | 13 |
Дополнительная переменная нужна в том случае, когда один поток выполняет 14 строку, а другой после него 12 сроку. Первая переменная хранит 0, означающий что барьер открывается, а вторая переменная начинает подсчитывать потоки, которые из него выходят.
Ещё более запутанная ситуация, когда барьер становится открытым, и потоки могут пройти через него дважды. Учитывая то, что любой поток другого процесса может вытеснить данный поток с процессора, и он будет некоторое время бездействовать. При этом неизвестно, в какой момент произойдет задержка.
| I | II | wait | wake | |
| 1 | 1 | 0 | 0 | |
| 2 | - | 1 | ||
| - | 2 | 2 | ||
| 3 | - | 0 | ||
| 4 | 3 | 0 | ||
| 5 | 4 | |||
| - | 12 | 0 | 0 | планировщик задач решил предоставить квант времени другому приложению |
| - | 13 | |||
| - | 14 | 1 | ||
| - | 15 | |||
| - | 16 | |||
| 7 | ? | 0 | первый поток вернулся к работе | |
| 8 | 1 | второй поток пошёл по кругу | ||
| 9 | 2 | 1 | ||
| 10 | 3 | 1 | ||
| ? | 4 | |||
| 1 | 12 | 1 | ||
| 2 | 13 | 2 | ||
| 3 | 12 | 0 | ||
| 4 | 13 | |||
| 5 | 14 | 1 | ||
| 7 | 15 | 0 | ||
| 8 | 16 | |||
| 9 | ? | |||
| 10 | 1 |
Вроде бы всё нормально: оба потока выполнили одинаковое число итераций. Добавим третий поток.
| I | II | III | wait | wake | |
| 1 | 0 | ||||
| 2 | 1 | 1 | |||
| - | 2 | 1 | 2 | ||
| - | - | 2 | 3 | ||
| 3 | - | - | 0 | ||
| 4 | 3 | - | |||
| 5 | 4 | 3 | |||
| 7 | 12 | 4 | 0 | 0 | |
| 8 | 13 | 12 | 0 | ||
| - | 14 | 13 | 1 | ||
| - | 15 | 14 | 2 | ||
| 7 | 16 | 15 | 0 | ||
| 8 | ? | 16 | всё идет по плану | ||
| 9 | 1 | ? | |||
| 10 | 2 | 1 | 1 | ||
| ? | - | 2 | 2 | ||
| 1 | 3 | - | |||
| 2 | 4 | - | 3 | ||
| - | 12 | 3 | 0 | ||
| 3 | 13 | 4 | |||
| 4 | 14 | 5 | 1 | ||
| - | 15 | 7 | 0 | первый поток сделал непредвиденную паузу | |
| - | 16 | 8 | |||
| ? | 9 | ||||
| 1 | 10 | ||||
| 2 | ? | 1 | |||
| 12 | 3 | 1 | первый поток очнулся после спячки | ||
| 4 | 2 | 2 | |||
| 12 | 3 | ||||
| 4 | |||||
| 12 | все потоки кого-то ждут |
Пауза перед циклом ожидания привела к тому, что все три потока попали в этот цикл. Условием завершения цикла является равенство нулю числа ожидающих потоков. Оно становится равным нулю, когда выполняется оператор сравнения с обметом в тетьей строке. Поскольку все потоки попали в цикл, то эта строка не будет выполнена, и программа не завершится, пока пользователь не уничтожит процесс в диспетчере задач.
Сделаем все по умному, и введем новую переменную, чтобы обеспечить повторную используемость барьера. Не совсем надёжно, но для кустарных целей сойдёт.
При написании многопоточных программ следует учитывать, что:
- после каждой строки может быть пауза; перед выполнением следующей инструкции другой поток может выполнить много инструкций;
- следует учитывать возможность выполнения более двух потоков.
Учитывая то, что пауза может произойти в любой момент и количество потоков больше двух, сложность моделирования работы многопоточной программы увеличивается экспоненциально количеству строк кода.
Чем объёмнее многопоточная программа, тем больше вероятность того, что она работает неправильно. Следовательно, необходимо стремится сократить число атомарных операций в каждой подпрограмме.
При этом вероятность проявления ошибки уменьшается пропорционально размеру многопоточной программы. Это значит, что ошибка появится только при выполнении 3000 раз этого кода. Если код увеличить, то ошибок станет больше, и количество итераций следует увеличить вдвое.
Кроме того, исправление многопоточной программы нередко приводит к добавлению строк кода. А известно, что это может привести к новым проблемам. Поэтому лучше исправлять посредством уменьшения размера кода.
Часто исправить многопоточную программу можно только полностью переписав её. Внесение новых изменений в программу может полностью испортить код. Для создания безопасного кода требуется полностью изменить принцип работы программа.
Если программа небольшая, то простого просмотра кода достаточно, чтобы обнаружить критическую точку в алгоритме. Для больших программ потребуется таблица трассировки.
Написание многопоточных программ довольно трудоёмкая задача [1]. Приводит к удивлению тот, факт, что этот процесс ещё не автоматизировали.
Многопоточна программа – такая программа, в которой выполняется параллельно несколько последовательностей инструкций.
Для выполнения многопоточных программ используется несколько арифметико-логических устройств. Следует учитывать, что программа выполняется тогда, когда её предоставлен квант времени для выполнения. Это создает сложность в проверке корректности программы.
Сложность заключается в том, что многопоточная программа выполняется с определенными задержками на каждом потоке.
Если программа небольшая, то проверить все возможные случаи фргментации программы на кванты времени не составит труда.
При увеличчении размера программы сложность её проверки возрастает экспоненциально, поскольку задержка может произойти после любой инструкции и длится неопределенное количество квантов.
Для проверки многопоточной программы применяется тестирование по методу белого
ящика, когда исходный код программы записывается в дизассемблированном виде и нумеруется инструкции. Затем в таблице трассировки с несколькими столбцами для потока инструкций проверяется работа программы. Все варианты задержек перебрать на бумаге нереально, поэтому включается интуитивный подод. Выделяется фрагмент кода, который начинается и заканчивается одной из инструкций:
- запись в общую переменную;
- установка сигнального состояния объекта синхронизации;
- цикл активного ожидания;
- ожидание сигнального состояния объекта синхронизации.
Затем проверяется, что будет если:
- задержка произойдет после первой инструкции, затем после второй и т.д. до предпоследней;
- после первой (второй и т.д.) инструкции и длится один такт, два такта и т.д.
- и так для двух, трёх и т.д. меняется количество потоков.
Вобщем задача заключается в том, чтобы пользователь вводил что-то наподобие юнит-тестов для результатов трассировки. А система проверяла соответствие каждого случая этому требованию.
Как поисходит отладка многопоточных программ на самом деле. В код программы вставляется отладочная информация. При выполнении программы она записывает в текстовый файл журнал своих действий: номер потока и что он сделал. Этот журнал содержит ценную информацию о том, какая последовательность действий дает сбой.
Иными словами, журнал ведётся для того, чтобы несколько рабочих записывали туда свои действия, а потом начальник выяснял, почему результат оказался неправильным. Каждый рабочий по отдельности выполняет свою работу правильно. А если их несколько, то происходит рассогласование.
Задержка между инструкциями равносильно тому, что рабочий отвлекается от своей работы, например ответ на телефонный звонок. При этом неизвестно, после какого действия зазвонит телефон. Другой рабочий может тоже отвлекаться. А рабочих может быть больше двух.
А журнал нужен тогда затем, чтобы выяснить, какая инструкция дала сбой. А затем проинструктировать рабочих ток, чтобы их рассинхронизация не влияла на результат работы.
Никогда не знаеш, когда пронировщик задач вытеснит поток с процессора. Поэтому нужно просчитать все варианты.
А если ипрограмма мальенькая, то можно воспользоваться тестированием по методу чёрного
ящика. Запускается программа несколько тысяч раз. В одном из 5 тысяч итераций планировщик задач создал задержку в критический момент, что завело программу в тупик. Задача в том, чтобы найти все критические места в программе, задержка в которых может нарушить её работу.
Список источников
- Меркульев И.И. Автоматический анализ распараллеливаемости кода / И.И. Меркульев, М.В. Кузнецов . // Новая наука: от идеи к результату — № 5(2) . — ПГУТИ , 2015. — С. 146–152. — URL: https://elibrary.ru/item.asp?i... .