4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 104: | Строка 104: | ||
Алгоритм требует, чтобы каждый процесс поддерживал собственную очередь запросов, и гарантирует, что очереди запросов разных процессов всегда остаются согласованными. Вначале все очереди запросов содержат по одному сообщению ( | Алгоритм требует, чтобы каждый процесс поддерживал собственную очередь запросов, и гарантирует, что очереди запросов разных процессов всегда остаются согласованными. Вначале все очереди запросов содержат по одному сообщению <math>(T_0, p_0, request) \;</math>, где <math>p_0 \;</math> – процесс, который содержит ресурс, а временная метка <math>T_0 \;</math> меньше исходного значения каждого экземпляра часов. Затем алгоритм работает следующим образом. | ||
1. Когда процесс | 1. Когда процесс <math>p_i \;</math> запрашивает ресурс, он отправляет сообщение с запросом <math>(T_m, p_i, request) \;</math> всем остальным процессам и помещает его в свою очередь запросов. | ||
2. Когда процесс | 2. Когда процесс <math>p_j \;</math> получает сообщение <math>(T_m, p_i, request) \;</math>, он помещает его в свою очередь запросов и направляет уведомление <math>(T_{m'}, p_j, ack) \;</math> процессу <math>p_i \;</math>. | ||
3. Когда процесс | 3. Когда процесс <math>p_i \;</math> освобождает ресурс, он удаляет все экземпляры сообщений <math>( - , p_i, request) \;</math> из своей очереди и отправляет сообщение об освобождении ресурса <math>(T_{m'}, p_i, release) \;</math> всем остальным процессам. | ||
4. Когда процесс | 4. Когда процесс <math>p_j \;</math> получает сообщение об освобождении ресурса от процесса <math>p_i \;</math>, он удаляет все экземпляры сообщений <math>(T_m, p_i, request) \;</math> из своей очереди и отправляет процессу <math>p_i \;</math> уведомление, снабженное временной меткой. | ||
5. Сообщения в очереди отсортированы согласно отношению полного упорядочения | 5. Сообщения в очереди отсортированы согласно отношению полного упорядочения <math>\Rightarrow</math> из определения 4. Процесс <math>p_i \;</math> может использовать ресурс в случае, когда: (а) сообщение <math>(T_m, p_i, request) \;</math> оказывается первым в очереди, и (б) процесс <math>p_i \;</math> получил от всех остальных процессов сообщения с временными метками, большими, чем <math>T_m \;</math> (или равными ей – от любого процесса <math>p_j \;</math>, где <math>p_i \prec p_j \;</math>). | ||
== Применение == | == Применение == |
правок