2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3, 4  След.
 
 Задачка для тех, кто думает что научился программировать
Сообщение22.11.2008, 01:10 
Аватара пользователя
Имеем современный компилятор С, 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?
Если (да или нет), то почему?

 
 
 
 
Сообщение22.11.2008, 01:14 
Фома в сообщении #160740 писал(а):
Вопрос, а может ли случится так, что в результате будет, что x =1 и y = 1?
Да. Для процов с некогерентным кэшом. x86[_64] к таковым не относится.

 
 
 
 
Сообщение22.11.2008, 01:46 
Аватара пользователя
Цитата:
Да. Для процов с некогерентным кэшом. x86[_64] к таковым не относится.


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

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

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

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

 
 
 
 
Сообщение22.11.2008, 01:50 
Фома в сообщении #160745 писал(а):
Ну вот, становится интересно. И при чем здесь этот самый кэш? Подробнее можно?
Хмм. я не очень внимательно прочитал Ваш пример и у меня создалась ассоциация с кое-какими экспериментами на предмет нарушения причинно-следственных связей в пределах двух тредов, которые я проводил некоторое время назад. И именно связанные с некогерентностью кэша на архитектуре ppc.

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

 
 
 
 
Сообщение22.11.2008, 02:03 
Аватара пользователя
вздымщик Цыпа писал(а):
И тоже ответ «да» в связи с исполнением инструкций совсем не в том порядке, в котором они представлены в программе. И даже если компайлер их оставит так, то не факт, что проц не переставит так, как ему удобнее.


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

 
 
 
 
Сообщение22.11.2008, 02:12 
Фома в сообщении #160753 писал(а):
Именно так. Не правда ли поучительно?
Ну да. Хотя практических применений таких знаний немного. Разве что при написании каких-нибудь lockless структур.

А вот такой код:
Код:
...
pthread_t t1=pthread_self();
f();
pthread_t t2=pthread_self();
...
Бывает ли, что $t1 \ne t2$ ?;)

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

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

 
 
 
 
Сообщение22.11.2008, 02:26 
Ну просто после вызова функции текущий тред поменялся :)

 
 
 
 
Сообщение22.11.2008, 02:29 
Аватара пользователя
Андрей АK писал(а):
Нифига проц ничего не переставит, ...
Так что не морочте людям ,на собеседованиях, голову


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

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

Код:
a = 1;
b = 1;
x = b;
y = a;


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

 
 
 
 
Сообщение22.11.2008, 02:34 
Аватара пользователя
Фома
Думаю что нет.
Обозначим команды как
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. Если, правильно возьмете к себе?

 
 
 
 
Сообщение22.11.2008, 02:39 
Аватара пользователя
вздымщик Цыпа писал(а):
Ну просто после вызова функции текущий тред поменялся :)


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

 
 
 
 
Сообщение22.11.2008, 02:41 
Pavia в сообщении #160761 писал(а):
Остальные варианты в рассмотрение не буру так как, там вторая команда каждого потока не может выполняется быстрее первой.
В том то и прикол, что может. Процы нонче шибко умные пошли, исполняют несколько команд за раз и расставляют их так, как им хочется. Причем каждый ориентируются только на себя. Команды
Код:
x=0;
++x;
конечно не переставят, но если дело касается разных ячеек памяти, то очень даже переставляют.

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

Фома в сообщении #160762 писал(а):
Теперь понял.
Ну так как Вы оцениваете шансы на такое?

 
 
 
 
Сообщение22.11.2008, 02:45 
Аватара пользователя
Pavia писал(а):
а это противоречит тому, что команды не должны менять свою очередность.

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

 
 
 
 
Сообщение22.11.2008, 02:46 
Аватара пользователя
вздымщик Цыпа писал(а):
Pavia в сообщении #160761 писал(а):
Остальные варианты в рассмотрение не буру так как, там вторая команда каждого потока не может выполняется быстрее первой.
В том то и прикол, что может. Процы нонче шибко умные пошли, исполняют несколько команд за раз и расставляют их так, как им хочется. Причем каждый ориентируются только на себя.

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

 
 
 [ Сообщений: 54 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group