При участии Тима Перлса, Джошуа Блоха, Джозева Боубира, Дэвида Холмса и Дага Ли Параллельное программирование в java на
 Скачать 4.97 Mb.
|
|
Глава 12 Тестирование параллельных программ Параллельные программы используют принципы проектирования и шаблоны, подобные тем, что используются в последовательных программах. Разница в том, что параллельные программы, в отличие от последовательных, обладают некоторой степенью недетерминированности, что приводит к увеличению количества потенциальных взаимодействий и ситуаций, в которых происходят сбои, и это должно быть проанализировано и предусмотрено. Аналогично, тестирование параллельных программ использует и расширяет идеи, подчерпнутые из тестирования последовательных программ. Те же самые методы, что применяются для проверки корректности и производительности в последовательных программах, могут быть применены к параллельным программам, но с параллельными программами пространство вариантов, которые могут пойти не так, как было запланировано, гораздо больше. Основная проблема при построении тестов для параллельных программ заключается в том, что потенциальные сбои могут быть, с большой вероятностью, редкими, а не детерминированными; тесты, раскрывающие такие сбои, должны быть более обширными и выполняться дольше, чем типичные последовательные тесты. Большинство тестов параллельных классов подпадают под одну или обе классические категории: безопасность и живучесть. В главе 1 мы определили безопасность, как “ничего плохого никогда не случается”, а живость как “что-то хорошее когда-нибудь случается”. Тесты на безопасность, которые проверяют, что поведение класса соответствует его спецификации, обычно принимают форму тестирования инвариантов. Например, в реализации связанного списка, которая кэширует размер списка при каждом его изменении, одним из тестов на безопасность будет сравнение кэшированного количества с фактическим количеством элементов в списке. В однопоточной программе это легко, так как содержимое списка не изменяется при тестировании его свойств. Но в параллельной программе такой тест, вероятно, будет чреват гонками, если вы не сможете наблюдать состояние поля подсчета и подсчитывать элементы в одной атомной операции. Это можно выполнить, заблокировав список для монопольного доступа, и применив какую-то функцию, предоставляемую реализацией, для создания “атомарного моментального снимка” (atomic snapshot) или используя “тестовые точки”, предоставляемые реализацией, которые позволяют тестам утверждать состояние инвариантов (assert invariants) или выполнять тестовый код атомарно. В этой книге мы использовали временные диаграммы, чтобы изобразить “неудачные” взаимодействия, которые могут приводить к сбоям в неправильно построенных классах; тестовые программы пытаются подобрать достаточное пространство состояний, в котором, в конечном итоге, и случается неудача. К сожалению, тестовый код может вводить задержки или артефакты синхронизации, которые могут приводить к маскировке ошибок, которые, в противном случае, могли бы проявляться 126 Свойства живучести представляют тестированию свои собственные вызовы. Тесты на живучесть включают в себя тесты на достижение прогресса и на отсутствие прогресса, которые трудно оценить количественно - как вы можете 126 Ошибки, которые исчезают при добавлении отладки или тестового кода игриво называются Heisenbugs (гейзенбаг). проверить, что метод блокируется, а не просто медленно работает? Аналогично, каким образом проверить, что алгоритм не попадает в состояние взаимоблокировки? Сколько вы должны ожидать, прежде чем объявить, что тест провален? С тестами на живучесть связаны тесты производительности. Производительность можно измерить несколькими способами, в том числе: Пропускная способность: скорость выполнения набора параллельных задач; Отзывчивость: задержка между моментом поступления запроса и выполнением какого-либо действия (также называемая “временем ожидания”, latency); или Масштабируемость: улучшение пропускной способности (или отсутствие такового) по мере увеличения доступности ресурсов (обычно ЦП). 12.1 Тестирование на корректность Разработка модульных тестов для параллельного класса начинается с проведения того же анализа, что и для последовательного класса - определения инвариантов и постусловий, поддающихся механической проверке. Если вам повезёт, многие из них присутствуют в спецификации; в остальное время написание тестов - это приключение по итеративному разбору спецификации. В качестве конкретной иллюстрации мы создадим набор тестовых случаев для ограниченного буфера. В листинге 12.1 показана реализация класса BoundedBuffer , использующая экземпляр Semaphore для реализации требуемого ограничения и блокировки. @ThreadSafe public class BoundedBuffer @GuardedBy("this") private final E[] items; @GuardedBy("this") private int putPosition = 0, takePosition = 0; public BoundedBuffer(int capacity) { availableItems = new Semaphore(0); availableSpaces = new Semaphore(capacity); items = (E[]) new Object[capacity]; } public boolean isEmpty() { return availableItems.availablePermits() == 0; } public boolean isFull() { return availableSpaces.availablePermits() == 0; } public void put(E x) throws InterruptedException { availableSpaces.acquire(); doInsert(x); availableItems.release(); } public E take() throws InterruptedException { availableItems.acquire(); E item = doExtract(); availableSpaces.release(); return item; } private synchronized void doInsert(E x) { int i = putPosition; items[i] = x; putPosition = (++i == items.length)? 0 : i; } private synchronized E doExtract() { int i = takePosition; E x = items[i]; items[i] = null; takePosition = (++i == items.length)? 0 : i; return x; } } Листинг 12.1 Ограниченный буфер с использованием экземпляра Semaphore Класс BoundedBuffer реализует очередь на основе массива фиксированной длины с блокирующими методами put и take , управляемыми парой подсчитывающих семафоров. Семафор availableItems представляет собой количество элементов, которое может быть удалено из буфера, и изначально равен нулю (так как буфер изначально пуст). Аналогично, семафор availableSpaces представляет собой количество элементов, которое может быть добавлено в буфер, и инициализируется размером буфера. Операция take требует, чтобы сначала было получено разрешение от семафора availableItems . Эта операция выполняется немедленно, если буфер не пустой, в противном случае операция блокируется, до появления элементов в буфере. Как только разрешение получено, следующий элемент из буфера удаляется, и освобождается разрешение семафора availableSpaces 127 . Операция put определяется обратным образом, так что при выходе из методов put или take сумма счетчиков обоих семафоров всегда равна значению границы. (На практике, если вам нужен ограниченный буфер, вы должны использовать классы ArrayBlockingQueue или LinkedBlockingQueue , а не писать своё собственное решение, но используемый здесь подход иллюстрирует, как вставки и удаления могут контролироваться и в других структурах данных.) 12.1.1 Простые модульные тесты Самые основные модульные тесты для класса BoundedBuffer похожи на те, что мы используем в последовательном контексте - создаем ограниченный буфер, вызываем его методы и выполняем утверждение постусловий и инвариантов. Некоторые инварианты из тех, что быстрее всего приходят на ум, это то, что только что созданный буфер должен идентифицировать себя и как пустой, и как не полный. Аналогичен, но чуть более сложен, тест на безопасность при вставке N 127 В подсчитывающем семафоре разрешения явно не представляются и не связаны с потоком- владельцем; операция release создает разрешение, а операция acquire использует его. элементов в буфер с емкостью N (который должен успешно завершиться без блокировки), и проверить, что буфер распознает, что он полон (а не является пустым). Тестовые методы JUnit для этих свойств показаны в листинге 12.2. class BoundedBufferTest extends TestCase { void testIsEmptyWhenConstructed() { BoundedBuffer } void testIsFullAfterPuts() throws InterruptedException { BoundedBuffer } } Листинг 12.2 Простой модульный тест для класса BoundedBuffer Эти простые тестовые методы полностью последовательны. Включение набора последовательных тестов в ваш набор тестов часто полезно, так как они могут раскрывать ситуации, когда проблема не связана с проблемами параллелизма, перед началом поиска гонок данных 12.1.2 Тестирование блокирующих операций Для проверки основных свойств параллелизма требуется введение нескольких потоков. Большинство фреймворков для тестирования не очень дружелюбны по отношению к параллелизму: они редко включают средства для создания потоков или мониторинга их состояния, чтобы гарантировать, что не происходит непредвиденного завершения. Если вспомогательный поток, созданный тестовым случаем, натыкается на сбой, фреймворк обычно не знает, с каким тестом связан поток, таким образом, для того, чтобы соотнести информацию об успехе или неудаче, могут потребоваться некоторые дополнительные усилия, для предоставления данных, при возврате к главному, выполняющему тесты, потоку, в удобном для составления отчётов виде. Для соответствия тестов пакету java.util.concurrent , очень важно, чтобы сбои четко соотносились с конкретным тестом. Поэтому, группой экспертов, разрабатывающей JSR 166, был создан базовый класс 128 , предоставивший методы для передачи и формирования отчётов об ошибках, во время выполнения метода tearDown , следуя соглашению, о том, что каждый тест должен ожидать, пока не завершатся все созданные им потоки. Скорее всего, вам нет нужды так глубоко погружаться в вопрос; основное требование заключаются в том, чтобы было ясно, успешно ли были выполнены тесты, и что информация о сбое куда-то отправляется, для использования при диагностике проблемы. Если предполагается, что метод блокируется при определенных условиях, то проверка такого поведения должна завершиться успешно только в том случае, если 128 http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/tck/JSR166TestCase. java поток не выполняется. Проверка того, что метод блокируется, подобна проверке того, что метод бросает исключение; если метод возвращает управление нормально, выполнение теста провалено. Тестирование на предмет того, что метод блокируется, вводит дополнительные сложности: как только метод успешно блокируется, вы должны вынудить его каким-то образом разблокироваться. Очевидным способом сделать это, является использование прерывания - запустить блокирующее действие в отдельном потоке, подождать, пока поток не заблокируется, прервать его, а затем выдвинуть утверждение (assert), что блокирующая операция завершена. Конечно, это требует, чтобы ваши блокирующие методы реагировали на прерывания, раньше возвращая управление или бросая исключение InterruptedException Про часть “ждать, пока поток заблокирован” легче сказать, чем сделать; на практике вы должны принять произвольное решение о том, сколько времени может занять выполнение нескольких инструкций, и ждать дольше. Вы должны быть готовы увеличить это значение, если вы не правы (в этом случае вы увидите ложные сбои в процессе тестирования). В листинге 12.3 демонстрируется подход к тестированию блокирующих операций. В нём создаётся поток “получателя”, который пытается взять элемент из пустого буфера. Если метод take выполняется успешно, то поток регистрирует сбой. Выполняющий тесты поток запускает поток получателя, ожидает долгое время, а затем прерывает его. Если поток получателя корректно заблокирован в операции take , будет брошено исключение InterruptedException , и блок catch , для этого исключения, будет рассматривать его как успешное прохождение теста, и позволит потоку вернуть управление. Затем, основной выполняющий тесты поток пытается выполнить метод join потока получателя и проверяет, что возврат управления из метода join произошёл успешно, путем вызова метода Thread.isAlive ; если поток получателя среагировал на прерывание, выполнение метода join должно завершиться быстро. void testTakeBlocksWhenEmpty() { final BoundedBuffer Thread taker = new Thread() { public void run() { try { int unused = bb.take(); fail(); // if we get here, it’s an error } catch (InterruptedException success) { } }}; try { taker.start(); Thread.sleep(LOCKUP_DETECT_TIMEOUT); taker.interrupt(); taker.join(LOCKUP_DETECT_TIMEOUT); assertFalse(taker.isAlive()); } catch (Exception unexpected) { fail(); } } Листинг 12.3 Тестирование блокировки и отзывчивости на прерывание Ограниченная по времени версия метода join гарантирует, что тест завершится, даже если выполнение метода take каким-то неожиданным образом застопорится. Этот тестовый метод проверяет несколько свойств метода take - не только то, что он блокируется, но и то, что при прерывании он бросает исключение InterruptedException . Это один из тех немногих случаев, при которых уместно явно использовать подкласс класса Thread , вместо использования экземпляра Runnable в пуле: для тестирования надлежащего завершения с использованием метода join . Подобный подход можно также использовать для проверки разблокировки потока получателя, после помещения элемента в очередь основным потоком. Заманчиво использовать метод Thread.getState , для проверки того, что поток фактически заблокирован на условии ожидания, но этот подход не надежен. Нет такого требования, чтобы заблокированный поток всегда входил в состояние WAITING или TIMED_WAITING , так как JVM, вместо этого, может выбрать для реализации блокировки ожидание спина. Точно так же, в связи с тем, что разрешены ложные пробуждения (spurious wakeups) при выполнении методов Object.wait или Condition.await (см. главу 14 ), поток, находящийся в состоянии WAITING или TIMED_WAITING, может временно перейти в состояние RUNNABLE , даже если условие, выполнение которого он ожидает, еще не истинно. Даже игнорируя эти параметры реализации, целевому потоку может потребоваться некоторое время для перехода в заблокированное состояние. Результат, возвращаемый методом Thread.getState , не должен использоваться для управления параллелизмом, и имеет ограниченную полезность для тестирования - его основная утилита является источником отладочной информации. 12.1.3 Тестирование безопасности Тесты, приведённые в листингах 12.2 и 12.3, проверяют важные свойства ограниченного буфера, но вряд ли позволят выявить ошибки, связанные с гонками данных. Чтобы проверить, что параллельный класс работает правильно при непредсказуемом параллельном доступе, нам нужно настроить несколько потоков, выполняющих операции put и take в течение некоторого времени, а затем как-то проверить, что всё прошло так, как было запланировано. Построение тестов для выявления ошибок безопасности в параллельных классах является проблемой “курицы и яйца”: тестовые программы сами по себе являются параллельными программами. Разработка хороших параллельных тестов может оказаться сложнее разработки классов, которые они тестируют. Задача построения эффективных тестов на безопасность, для параллельных классов, заключается в определении легко проверяемых свойств, которые с высокой вероятностью завершатся неудачей, если что-то пойдет не так, и в то же время не позволят коду, выполняющему аудит отказов, искусственно ограничить параллелизм. Лучше всего, если проверка тестируемого свойства не требует синхронизации. Один подход, который хорошо работает с классами, используемыми в шаблоне производитель-потребитель (подобным классу BoundedBuffer ) заключается в том, чтобы проверить, что все, что помещается в очередь или буфер покидает её, и что больше ничего не происходит. Наивная реализация этого подхода будет помещать элемент в “теневой” (shadow) список, когда он помещается в очередь, удалять его из списка, когда он удаляется из очереди, и выдвинет утверждение, что теневой список пуст, когда тест будет завершен. Но такой подход исказит расписание запуска тестовых потоков, поскольку для изменения теневого списка потребуется синхронизация и, возможно, блокировка. Распространение этого подхода на ситуацию с несколькими производителями и потребителями требует использования функции, вычисляющей контрольную сумму, нечувствительную к порядку, в котором элементы объединяются, чтобы после завершения теста можно было объединить несколько контрольных сумм. В противном случае, синхронизация доступа к совместно используемому полю контрольной суммы может стать узким местом параллелизма или исказить время выполнения теста. (Любые коммутативные операции, такие как сложение или XOR, отвечают этим требованиям.) Чтобы убедиться, что ваш тест действительно проверяет то, о чём вы думаете, важно, чтобы сами контрольные суммы не были угадываемыми компилятором. Было бы плохой идеей использовать последовательные целые числа в качестве тестовых данных, потому что тогда результат всегда будет одинаковым, и умный компилятор мог бы просто предварительно вычислить его. Чтобы избежать этой проблемы, тестовые данные должны генерироваться случайным образом, но многие другие эффективные тесты компрометируются плохим выбором генератора случайных чисел (random number generator, RNG). Генерация случайных чисел может создавать связи между классами и артефактами синхронизации, так как большинство классов генераторов случайных чисел потокобезопасны и поэтому обеспечивают дополнительную синхронизацию 129 Предоставление каждому потоку собственного экземпляра RNG, позволяет использовать RNG, не являющиеся потокобезопасными. Вместо использования RNG общего назначения лучше использовать простые псевдослучайные функции. Вам не нужна высококачественная степень случайности; все, что вам нужно, это достаточно случайное значение, чтобы обеспечить изменение чисел от запуска к запуску. Функция xorShift в листинге 12.4, (Marsaglia, 2003) среди самых дешевых функций генерирующих случайные числа среднего качества. Её запуск со значениями, основанными на результатах методов hashCode и nanoTime , делает суммы как неочевидными, так и почти всегда отличными, для каждого последующего запуска. static int xorShift(int y) { y ^= (y << 6); y ^= (y >>> 21); y ^= (y << 7); return y; } |