Локально стабильный предикат — различия между версиями
(Новая страница: «Категория: Параллельное программирование Если локально-стабильный предикат истинен, т…») |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 4 промежуточные версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
[[Категория: Параллельное программирование]] | [[Категория: Параллельное программирование]] | ||
| − | + | {{Определение | |
| + | |definition= | ||
| + | [[Глобальные свойства системы|Стабильный предикат]] называется '''локально стабильным''', если все процессы, участвующие в предикате, не меняют свое ''состояние'' после того, как предикат удовлетворен. | ||
| + | }} | ||
| + | == Примеры == | ||
| + | * Предикат "процессы <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".
