Задачка о самонумерации процессоров (теоретическая)

Имеется N процессоров, которые работают с общей памятью. По сигналу RESET процессоры обнуляют все свои регистры и начинают выполнение общей для них программы. Процессоры могут читать содержимое памяти в регистры и записывать обратно. Операции чтения и записи от различных процессоров могут быть выполнены в произвольном порядке. Монопольный захват доступа к памяти для атомарного выполнения операции чтение-модификация-запись невозможен. Могут ли эти процессоры в результате выполнения программы пронумеровать себя числами от 1 до N? Если могут, то как? Если не могут, то почему?

 

Если можно использовать генератор случайных чисел, то

Код (Text):

1. cert = rnd();
2. num = 0;
3.  
4. for(;;) {
5.     sleep(rnd());
6.     m = mem[num];
7.     if(m == 0) {
8.         mem[num] = cert;
9.     } else if(m != cert) {
10.         num++;
11.     }
12. }

mem - общая память, в num будет номер процессора.

 

Stiver
rnd у нас нету, случайный только порядок доступа к памяти от разных процессоров, то есть какой-то процессор может успеть выполнить на несколько инструкций больше чем другой, но вполне может быть, что он не один и есть еще один такой шустрый процессор.

 

Black_mirror

И никакого внутреннего таймера вроде rdtsc тоже нет?

 

Stiver
Тоже нет. Если мы напишем такой цикл:

Код (Text):

1.   mov reg,x
2. m:
3.   mov [mem],reg
4.   not reg
5.   cmp [mem],reg
6.   jnz m; исправлено, было jz m

То выйдем мы из него в случае обнаружения конфликта с другим процессором. Мне кажется что в итоге внутри этого цикла останется только один процессор, правда я пока не могу этого доказать, да и процессор зависший в таком цикле не очень полезен.

 

неа, "процессоры начинают выполнение общей для них программы".

 

t00x
действительно бага, должно быть JNZ M

 

часть решения:

Код (Text):

1. add [0], 1
2. @wait:
3. loop @wait ; достаточно "большой" отрезок времени, чтобы подсчитать количество процессоров
4. mov reg, [0] ; = количество процессоров
5. ; выделяем память с [1] по [reg] для нумерации процессоров.

 

t00x
Не пойдёт, команда Add [0],1 атомарностью не обладает, то есть процессор будет выполнять чтение, потом добавление 1, а потом запись, а в это время другие процессоры тоже могут читать или записывать эту же ячейку.

 

На каком наборе команд основываемся? Какими примитивами можно пользоваться? x86?
Ручные спин-блокировки допустимы?

 

asmfan
Можно считать что это x86, но операции чтение-модификация-запись атомарностью не обладают, то есть
add [mem],1 эквивалентно mov temp,[mem]/add temp,1/mov [mem],temp
xchg reg,[mem] эквивалентно mov temp,[mem]/mov [mem],reg/mov reg,temp
и между чтением и записью памяти может вклиниться произвольное количество операций чтения и записи от других процессоров. И нет никаких lock!

 

Black_mirror

Такой цикл может, но не обязан обнаружить конфликт. Например при поочередном выполнении (для двух процессоров, a и b)

Код (Text):

1. a|  mov reg,x
2. b|  mov reg,x
3. a|m:
4. b|m:
5. a|  mov [mem],reg
6. b|  mov [mem],reg
7. a|  not reg
8. b|  not reg
9. a|  cmp [mem],reg
10. b|  cmp [mem],reg
11. a|  jnz m
12. b|  jnz m

Задача сводится к тому, что процессор должен иметь возможность отличить результат своей работы от других, хотя бы с некоторой ненулевой вероятностью. Если такой возможности нет, то нет и решения.

 

Stiver
Это только если N операций доступа к памяти в сумме занимают меньше времени чем выполнение одной команды, будем считать что оно немного больше.

 

Если число процессоров известно, то можно использовать такой код:

Код (Text):

1.     mov r0,1
2.     mov r1,0
3.     mov [flag],0        
4. wait:
5.     mov [r0],r1          
6.     not r1
7.     cmp [r0],r1
8.     jnz next
9.     add r0,1
10.     cmp r0,N
11.     jz exit
12. next:
13.     cmp [flag],0
14.     jz wait
15. exit:
16.     mov [flag],1
17. ;r0 - номер процессора

А вот если число процессоров изначально неизвестно, смогут ли они определить сколько их?

 

Black_mirror

атомарность и не нужна, нужна достаточно большая задержка, чтобы каждый (все) процессор добавил 1.

#8.

 

Предлагаю ограничиться пока случаем двух процессоров, выполняющих инструкции поочередно. Если решится этот случай, то решится и вся задача.

Black_mirror

Что-то я ничего в этом коде не понимаю А зачем flag нужен, если он всегда 0? И выход получается только по r0==N?

Нее, это уже программирование на киселе немного больше, немного меньше..

 

t00x
Если у нас два процессора, то add [0], 1 они могут выполнить так
a| mov temp_a,[mem]
a| mov [mem],temp_a+1
b| mov temp_b,[mem]
b| mov [mem],temp_b+1
или так
a| mov temp_a,[mem]
b| mov temp_b,[mem]
a| mov [mem],temp_a+1
b| mov [mem],temp_b+1
Сколько процессоров во втором случае они насчитают?

Stiver
Процессоры смогут обнаружить конфликт только в том случае, если один из них может случайно выполнить операцию записи раньше, чем другой выполнит предшествующую операцию чтения:
a| read
a| write
b| read
b| write
А если они друг друга обгоняют не более чем на 1 операцию доступа к памяти, то решения нет.

А алгоритм работает следующим образом:
Изначально все процессоры пытаются изменять содержимое первой ячейки, те процессоры, которые обнаружат что в первой ячейке не то что они записывали, переходят ко второй ячейке. В итоге с первой ячейкой останется работать только один процессор, а N-1 перейдут ко следующей. Со второй ячейкой ситуация аналогична, с ней остайтся работать 1 процессор, а N-2 переходят к третьей. Если процессор добрался до Nой ячейки, это означает что предыдущие N-1 ячеек заняты, поэтому он выходит и устанавливает флаг чтобы остальные тоже вышли из цикла.

 

Black_mirror

Совершенно верно. А поскольку в условии сказано, что Операции чтения и записи от различных процессоров могут быть выполнены в произвольном порядке, то решения нет.

Теперь понятно, я проглядел, что у них flag общий.

 

а что, аппаратную синхронизацию уже отменили?

 

Stiver
Мне намного интереснее случай когда число процессоров неизвестно, а время выполнения команд случайно (это чтобы уйти от варианта когда они синхронно читают и пишут). Смогут ли они подсчитать сколько их? Смогут ли они подсчитать сколько их если можно модифицировать код программы? (Считаем что все инструкции занимают одну ячейку памяти, перед выполнением инструкции её нужно прочитать, но кто-то уже мог успеть заменить её на другую.)

t00x
В этой задаче отменили. Синхронизация только в том, что если мы что-то прочитали из памяти, то значит это что-то туда записал кто-то или оно было в ячейке в момент запуска процессоров.