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

Black_mirror

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

 

Stiver
Я думаю нужно немного изменить условие:
Количество процессоров неизвестно, но не больше N и нужно пронумеровать хотя бы часть из них.

 

Т.е. задача в том, чтобы войти в мьютекс, организованный сугубо программным методом? (Без инструкции xchg?). Тогда можно так: входим в мьютекс, ищем ненумерованную область памяти (допустим память обнулена), нумеруем ее и выходим из мьютекса. Программный мьютекс можно организовать с помощьюалгоритма Петерсона.

 

Я так понял из статьи, что каждый процессор там должен знать свой номер для выполнения алгоритма. Но если он знает свой номер, тогда и нумеровать некого.

 

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

 

При инициализации каждый проц обращается к девайсине (счетчик, мк, ..) которая и выдает ему уник номер. В идеале (мои фантазии к х86 не относящиеся) такое обращение должно происходить при каждой загрузке команды для получения рабочего и после выполнения для холостого уникального последовательного номера (для моих глюков это важно).

 

_basmp_
С большой вероятностью пронумеровать их можно, а вот со 100%й нет.

 

Black_mirror

Почему? По запросу на чтение девайсина выдает значение и сразу вычисляет следующее (вроде бы даже 53 позволяет нечто подобное). Два проца не могут читать одновременно из одной ячейки и даже просто одновременно занимать одну и ту же шину, те относительно шины и конкретной ячейки памяти они строго последовательны. Те любое кол-во процов инициализующееся по одной и той-же проге будет получать разные и последовательные номера в пределах разрядности девайсового счетчика.

 

_basmp_
У нас нет никаких девайсов, у нас есть только процессоры, они могут читать и записывать память, но захватить её не могут. То есть есть вероятность, что 2 или более процессора некоторое время выполняются программу синхронно, и нужно как-то их друг от друга отделить, вернее определить момент когда у них всех будет разное состояние.

 

Black_mirror
ну хорошо. все равно разделить их можно на доступе к одному и тому-же ресурсу. скажем все идут одну и ту-же процедуру инициализации. В ней сперва отключаем кэш, а затем пишем по какому-нибудь определенному адресу. После записи сразу-же читаем из rdtsc. На процедуре записи в ячейку процы 100% разделятся в тактах.

 

ну попробуй так: проц дошёл до ячейки памяти, взял себе номер. задал вопрос сколько процов уже с этим номером, ждёт ответ\ты, сравнивает с 1.
следующий дошёл спросил "сколько вас с этим номером", пересчитал ответы, если больше одного, "идите в баню, вас много", поставил флаг какой нить, значащий что номер присваивать низзя.