Задачка для тех, кто думает что научился программировать

[Фома]

Имеем современный компилятор С, C++, Java, С#, Delphi...

Далее пишу на псевдокоде, более похожем на С, но это не суть важно.

int x, y, a, b;   
x = y = a = b = 0;

Теперь запускаем два не синхронизированных потока (thread'a).
Код первого:

x = b;
a = 1;

Код второго:

y = a;
b = 1;

Потоки завершают свою работу и затем печатаем значения x и y.

Вопрос, а может ли случится так, что в результате будет, что x =1 и y = 1?
Если (да или нет), то почему?

[вздымщик Цыпа]

Фома в сообщении #160740 писал(а):

Вопрос, а может ли случится так, что в результате будет, что x =1 и y = 1?

Да. Для процов с некогерентным кэшом. x86[_64] к таковым не относится.

[Фома]

Цитата:

Да. Для процов с некогерентным кэшом. x86[_64] к таковым не относится.

Ну вот, становится интересно. И при чем здесь этот самый кэш? Подробнее можно?

З.Ы. Этот ворос я задаю на собеседованиях всегда, после того как мне говорят, что знакомы с multithreading'ом. За несколько лет, правильно обосновать ответ, сумел только один.

Добавлено спустя 27 минут 9 секунд:

Если кто думает, что это задачка из разряда программисты шутят, то обратите внимание Во что верит Dell

[вздымщик Цыпа]

Фома в сообщении #160745 писал(а):

Ну вот, становится интересно. И при чем здесь этот самый кэш? Подробнее можно?

Хмм. я не очень внимательно прочитал Ваш пример и у меня создалась ассоциация с кое-какими экспериментами на предмет нарушения причинно-следственных связей в пределах двух тредов, которые я проводил некоторое время назад. И именно связанные с некогерентностью кэша на архитектуре ppc.

Ну да, тут другое. И тоже ответ «да» в связи с исполнением инструкций совсем не в том порядке, в котором они представлены в программе. И даже если компайлер их оставит так, то не факт, что проц не переставит так, как ему удобнее.

[Фома]

вздымщик Цыпа писал(а):

И тоже ответ «да» в связи с исполнением инструкций совсем не в том порядке, в котором они представлены в программе. И даже если компайлер их оставит так, то не факт, что проц не переставит так, как ему удобнее.

Именно так. Не правда ли поучительно? И что характерно, это может сделать именно проц.

[вздымщик Цыпа]

Фома в сообщении #160753 писал(а):

Именно так. Не правда ли поучительно?

Ну да. Хотя практических применений таких знаний немного. Разве что при написании каких-нибудь lockless структур.

А вот такой код:

...
pthread_t t1=pthread_self();
f();
pthread_t t2=pthread_self();
...

Бывает ли, что $t1 \ne t2$ ?;)

[Андрей АK]

Нифига проц ничего не переставит, вернее как бы не переставлял x =1 и y = 1 не получится.
Для этого ему придётся одну из инструкций выполнить ДВАЖДЫ - а это уже не перестановки а ошибки.
И даже если поменяет местами две операции, то в этом месте он поток не прервёт.
Поэтому - ответ НЕТ.
Так что не морочте людям ,на собеседованиях, голову

[Фома]

К сожалению, Ваш пример слишком С-специфичен, а на этом языке я не пишу уже 10 лет (хотя до этого писал те же 10), посему не понял постановки. Извиняйте подзабыл. Сейчас пишу только С#. Чуток объясните.

[вздымщик Цыпа]

Ну просто после вызова функции текущий тред поменялся

[Фома]

Андрей АK писал(а):

Нифига проц ничего не переставит, ...
Так что не морочте людям ,на собеседованиях, голову

Прежде, чем начинать хамить, пойдите лучше почитайте букварь.

Вот Вам, вполне валидная последовательность выполнения инструкций:

a = 1;
b = 1;
x = b;
y = a;

И где здесь повторения?

[Pavia]

Фома
Думаю что нет.
Обозначим команды как
1)x = b;
2)a = 1;
3)y = a;
4)b = 1;

Тогда возможны следующие случаи
а) 1)2)3)4) x=0 y=1
б) 1)3)2)4) x=0 y=0
в) 3)1)2)4) x=0 y=0
г) 3)1)4)2) x=0 y=0
д) 3)4)1)2) x=1 y=0
е) 1)3)4)2) x=0 y=0

Остальные варианты в рассмотрение не буру так как, там вторая команда каждого потока не может выполняется быстрее первой. те 2) не может выполниться раньше 1) и 4) не может выполниться раньше чем 3).
А вообще проверку можно сделать и короче. Случай x,y возможен тогда и только тогда когда вначале идет 3)4) или 4)3)а затем 1)2) или 2)1), а это противоречит тому, что команды не должны менять свою очередность.

PS. Если, правильно возьмете к себе?

[Фома]

вздымщик Цыпа писал(а):

Ну просто после вызова функции текущий тред поменялся

Теперь понял. Не понимал, что такое pthread_self()

[вздымщик Цыпа]

Pavia в сообщении #160761 писал(а):

Остальные варианты в рассмотрение не буру так как, там вторая команда каждого потока не может выполняется быстрее первой.

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

x=0;
++x;

конечно не переставят, но если дело касается разных ячеек памяти, то очень даже переставляют.

Добавлено спустя 1 минуту:

Фома в сообщении #160762 писал(а):

Теперь понял.

Ну так как Вы оцениваете шансы на такое?

[Фома]

Pavia писал(а):

а это противоречит тому, что команды не должны менять свою очередность.

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

[Pavia]

вздымщик Цыпа писал(а):

Pavia в сообщении #160761 писал(а):

Остальные варианты в рассмотрение не буру так как, там вторая команда каждого потока не может выполняется быстрее первой.

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

Неверно. Есть строгие правила MEMORY ORDERING которые не позволяют в мульти процессорных системах переставлять обращения к памяти как заточиться. Возьмите маны и почитайте.