Курсовая работа: дз 5. spin. Leader election
Описание
Характеристики курсовой работы
Список файлов
- дз 5. spin. Leader election
- hometask-v2.pml 1,68 Kb
- hometask.pml 1,72 Kb
- Задача.txt 2,96 Kb
Избрание лидера.
Четыре процесса (P1, ..., P4), работающих асинхронно, соединены между собой "в кольцо" однонаправленными каналами передачи сообщений:
P1 -> P2 -> P3 -> P4 -> P1
Процессы умеют посылать числа в канал и читать числа из канала. Канал может хранить не более одного сообщения.
send(m): послать в исходящий канал число, записанное в переменной m. Если в канале уже хранится число, то процесс блокируется до тех пор, пока число не удалится из канала. При успешной посылке канал мгновенно начинает хранить посланное сообщение.
receive(m): прочитать число из входящего канала и записать в переменную m. Если в канале не хранится ни одно число, то процесс блокируется до тех пор, пока в канале не появится число. При успешном прочтении сообщение мгновенно удаляется из канала.
Каждый процесс имеет уникальный идентификатор ID - целое число, вмещающееся в заданное число бит (число бит можно выбрать самому; минимум - 2 бита). Доподлинно известно, что идентификаторы всех процессов попарно различны.
Каждый процесс имеет внутреннюю переменную i для хранения значения, считанного из канала, и внутреннюю переменную leader.
Каждым процессом выполняется такая программа:
leader = ID;
send(ID);
while(true) {
receive(i);
if(i >= leader) send(i);
if(i == leader) break;
if(i > leader) leader = i;
}
if(leader == ID) receive(i);
Свойства, которые требуется проверить для произвольного (каждого допустимого) задания идентификаторов:
1. рано или поздно все процессы завершат выполнение своих программ;
2. по завершении выполнения всех процессов в переменной leader каждого процесса записан идентификатор, максимальный среди всех идентификаторов процессов. (процесс с этим идентификатором объявляется лидером, поэтому система называется "Избрание лидера")