Локально стабильный предикат — различия между версиями
Rgolchin (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 3 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
[[Категория: Параллельное программирование]] | [[Категория: Параллельное программирование]] | ||
| − | Стабильный предикат называется '''локально стабильным''', если все процессы, участвующие в предикате не меняют свое состояние после того, как предикат удовлетворен. | + | {{Определение |
| + | |definition= | ||
| + | [[Глобальные свойства системы|Стабильный предикат]] называется '''локально стабильным''', если все процессы, участвующие в предикате, не меняют свое ''состояние'' после того, как предикат удовлетворен. | ||
| + | }} | ||
== Примеры == | == Примеры == | ||
| − | * Предикат "процессы <tex>P</tex> и <tex>Q</tex> | + | * Предикат "процессы <tex>P</tex> и <tex>Q</tex> ждут друг друга" локально стабилен, потому что они ничего не делают; |
| − | * Предикат "в системе не более одного токена" стабилен в системе, в которой не появляются новые токены, но не локально стабилен, потому что из-за получения / отправки токена состояние процесса может меняться. | + | * Предикат "в системе не более одного токена" стабилен в системе, в которой не появляются новые токены, но не ''локально'' стабилен, потому что из-за получения / отправки токена состояние процесса может меняться. |
| + | |||
| + | == Поиск == | ||
| + | Находим [[Барьерная синхронизация (3 алгоритма)|барьерно-синхронизированный интервал]] $[F, G]$. | ||
| + | Если предикат выполняется просто в $F$, в $G$ или в обоих, то это ещё ничего не значит — эти срезы могут не быть согласованными. | ||
| + | Однако если предикат выполнялся в $F$, и состояния всех процессов, участвующих в предикате, не поменялись между $F$ и $G$, то мы знаем, что предикат выполнялся на всех срезах между $F$ и $G$, включая обязательно существующий там согласованный. | ||
| + | Это более сильное требование, чем просто "предикат выполнялся в F и в G". | ||
Текущая версия на 11:44, 1 сентября 2022
| Определение: |
| Стабильный предикат называется локально стабильным, если все процессы, участвующие в предикате, не меняют свое состояние после того, как предикат удовлетворен. |
Примеры
- Предикат "процессы и ждут друг друга" локально стабилен, потому что они ничего не делают;
- Предикат "в системе не более одного токена" стабилен в системе, в которой не появляются новые токены, но не локально стабилен, потому что из-за получения / отправки токена состояние процесса может меняться.
Поиск
Находим барьерно-синхронизированный интервал $[F, G]$. Если предикат выполняется просто в $F$, в $G$ или в обоих, то это ещё ничего не значит — эти срезы могут не быть согласованными. Однако если предикат выполнялся в $F$, и состояния всех процессов, участвующих в предикате, не поменялись между $F$ и $G$, то мы знаем, что предикат выполнялся на всех срезах между $F$ и $G$, включая обязательно существующий там согласованный. Это более сильное требование, чем просто "предикат выполнялся в F и в G".
