Как проверить, какой прогресс гарантирует параллельная программа?
Я работал над несколькими параллельными программами в течение последних нескольких недель, и мне было интересно, есть ли какой-либо инструмент, который может автоматически определять, какой тип условия выполнения гарантирует его работа, то есть, является ли он без ожидания, без блокировки или без препятствий.
Я искал в Интернете и не нашел такого инструмента.
Можно ли сказать, как вывести состояние программы?
Решение
Предположим, что у меня есть программа под названием решение о свободе ожидания который может прочитать параллельную программу, описывающую структуру данных, и определить, свободна ли она от ожидания, то есть «та, которая гарантирует, что любой процесс может выполнить любую операцию за конечное число шагов» Герлихи «Синхронизация без ожидания». Затем, учитывая однопоточных программа P, создайте программу, которую мы будем вводить в решатель ожидания свободы:
class DataStructure:
def operation(this):
P
pass
Сейчас DataStructure.operation завершается за конечное число шагов, если и только если P останавливается.
Это решило бы проблему остановки. Это невозможно, поэтому из-за противоречия мы не должны быть в состоянии создать решающее средство свободы ожидания.
Другие решения
Других решений пока нет …