ПРИКЛАДНАЯ ИНФОРМАТИКА № 4 (34) 2011 Н. В. Заборовский, аспирант Московского физико-технического института (государственного университета) А. Г. Тормасов, докт. физ.-мат. наук, профессор Московского физико-технического института (государственного университета) Моделирование многопоточного исполнения программы и метод статического анализа кода на предмет состояний гонки Существуют различные методики анализа корректности многопоточных алгоритмов. <...> Статья посвящена рассмотрению данного вопроса в контексте состояний гонки. <...> Предлагаемый автором подход ориентирован на задачи со сложными конструкциями кода. <...> Обнаружить наличие состояния гонки в коде очень непросто, так как о них можно и вовсе не знать, пока они не проявят себя. <...> Процедура обнаружения состояния гонки может быть очень трудоемкой, даже если в наличии есть состояния всех потоков исполнения на момент некорректной ситуации. <...> С Обзор существующих моделей В настоящее время известны многие работы, посвященные моделированию исполнения многопоточных программ. <...> Так, например, в [1] описана процедура построения модели исполнения многопоточного алгоритма на разделяемой памяти с целью определения состояния гонки. <...> В ее основе лежит граф совместного исполнения потоков G: = (V, A), в котором путям соответствуют всевозможные варианты исполнения многопоточного алгоритма. <...> Вершинам графа V соответствует множество состояний общей памяти поИнструментальные средства Эффективные алгоритмы остояние гонки (race condition) — ситуация, когда несколько потоков одновременно обращаются к односле выполнения очередной атомарной инструкции, дугам A — атомарные операции над разделяемыми переменными. <...> Каждому ребру поставлена в соответствие операция (R — чтение, W — запись и Х — другая) и ячейка памяти, над которой производится операция. <...> Также для модели определена функция корректности, отражающая субъективное понятие о корректном или некорректном <...>