Генерация перестановок частично упорядоченного множества с учётом зависимости в элементах
Аннотация
Данная работа посвящена разработке методов, позволяющих существенно сократить количество линейных порядков, необходимых для анализа частично упорядоченных множеств. Такой анализ играет ключевую роль при тестировании многопоточных систем, где важно учитывать все допустимые варианты межпоточного взаимодействия. В настоящее время для тестирования подобных систем применяются как направленные литмус-тесты, специально сконструированные для проверки конкретных эффектов, так и генераторы последовательностей инструкций, порождающие рандомизированные, но простые и удобные для проверки, сценарии исполнения с существенными ограничениями. Применение сложных случайных входных данных затруднено из-за экспоненциального роста числа линейных порядков для анализа. Предлагаемый в данной работе алгоритм позволяет существенно сократить число рассматриваемых линейных порядков за счёт учёта зависимостей между элементами множества при их переупорядочивании. Полученные результаты делают возможным более эффективное тестирование многопоточных систем и расширяют область применения методов анализа частичного порядка.
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
