Генерация перестановок частично упорядоченного множества с учётом зависимости в элементах
Abstract
Данная работа посвящена разработке методов, позволяющих существенно сократить количество линейных порядков, необходимых для анализа частично упорядоченных множеств. Такой анализ играет ключевую роль при тестировании многопоточных систем, где важно учитывать все допустимые варианты межпоточного взаимодействия. В настоящее время для тестирования подобных систем применяются как направленные литмус-тесты, специально сконструированные для проверки конкретных эффектов, так и генераторы последовательностей инструкций, порождающие рандомизированные, но простые и удобные для проверки, сценарии исполнения с существенными ограничениями. Применение сложных случайных входных данных затруднено из-за экспоненциального роста числа линейных порядков для анализа. Предлагаемый в данной работе алгоритм позволяет существенно сократить число рассматриваемых линейных порядков за счёт учёта зависимостей между элементами множества при их переупорядочивании. Полученные результаты делают возможным более эффективное тестирование многопоточных систем и расширяют область применения методов анализа частичного порядка.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
