Как лучше всего протестировать реализацию Mutex?

Question

Какой лучший способ проверить реализацию мьютекса действительно верен? (Необходимо реализовать мьютекс, повторное использование не является жизнеспособным вариантом)

Лучшее, что я придумал, - это наличие множества (N) параллельных потоков, итеративно пытающихся получить доступ к защищенной области (I), что имеет побочный эффект (например, обновление до глобального), так что количество обращений + Количество операций записи может быть подсчитано, чтобы убедиться, что число обновлений для глобального типа точно (N) * (I).

Любые другие предложения?

Answer 1

Формальное доказательство лучше, чем тестирование для такого рода вещей.

Тестирование покажет вам, что - пока вам не повезло - все это работало.Но тест - тупой инструмент;он может не выполнить точную правильную последовательность и вызвать сбой.

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

Тестированиене без стоимости;это показывает, что вы не допустили явных ошибок кодирования.

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

Точно так же вы должны показать, что релиз является атомарным.

Answer 2

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

Answer 3

Я со всеми остальными, что это невероятно трудно доказать окончательно, я понятия не имею, как это сделать - не полезно, я знаю!

Когда вы говорите, что внедрите мьютекс, а повторное использование не является вариантом, это по техническим причинам, например, нет реализации Mutex на используемой платформе / ОС или по какой-то другой причине? Является ли упаковка какой-либо формы уровня ОС «замком» и называется ли это вашей реализацией Mutex как опция, например CriticalSection on windoze, posix Condition Variables? Если вы можете обернуть блокировку ОС более низкого уровня, то ваш шанс сделать это правильно намного выше.

Если вы еще этого не сделали, перейдите и прочитайте Эффективный параллелизм Херба Саттера статей. В них должно быть что-то стоящее для вас.

Во всяком случае, некоторые вещи, которые следует учитывать в ваших тестах:

• Если ваш мьютекс рекурсивный (то есть может ли один и тот же поток заблокировать его несколько раз), то убедитесь, что вы делаете некоторые тесты подсчета ссылок.
• С вашей глобальной переменной, которую вы изменить было бы лучше, если бы это было переменная, которая не может быть записана атомарно. Например, если вы на 8-битной платформе, затем используйте 16 или 32-битная переменная, которая требует написать несколько инструкций по сборке.
• Внимательно изучите листинг сборки. В зависимости от аппаратной платформы сборка не приводит непосредственно к тому, как можно оптимизировать код ...
• Попросите кого-нибудь еще, кто не написал код, также написать несколько тестов.
• тестирование на как можно большем количестве разных машин с разными спецификациями (при условии, что это «общее назначение», а не для конкретной настройки оборудования)

Удачи!

Answer 4

Это напоминает мне этот вопрос о тесте семафора FIFO . В двух словах мой ответ был:

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

Так что ваше предложение кажется разумно лучшим. Если вы хотите повысить свою уверенность, используйте fuzzing для рандомизации планирования и ввода.

Answer 5

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

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

Кстати, если вы не разбираетесь в математике и формальных методах, у вас не будет шансов на самом деле придумать доказательство.