Какая разница между безопасными, регулярными и атомными регистрами?

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

Из Lamport "О межпроцессной коммуникации" :... регулярный регистр является атомарным, если два последовательных чтения, которые перекрывают одну и ту же запись, не могут получить новое, то старое значение....

Предположим, что сначала приходит thread0.write(0) - без перекрытия. В принципе, с помощью определения Lamports можно сказать, что thread1 может читать сначала 1, а затем 0, если оба чтения являются последовательными и перекрываются с thread0.write(1). Но как это возможно?

Ответ 1

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

например.

Thread 1:      wwwww     wwwww
Thread 2:   rrrrr              rrrrr
Thread 3:   rrrrr rrrrr

Первое чтение из потока 2 перекрывается с первой записью из потока 1, в то время как вторая чтение и вторая запись не перекрываются. В потоке 3 оба чтения перекрывают первую запись.

A безопасный регистр безопасен только для чтения, который не перекрывает записи. Если чтение не перекрывает какие-либо записи, оно должно считывать значение, записанное самой последней записью. В противном случае он может вернуть любое значение, которое может иметь регистр. Итак, в потоке 2 второе чтение должно вернуть значение, записанное второй записью, но первое чтение может вернуть любое допустимое значение.

A регулярный регистр добавляет дополнительную гарантию того, что если чтение перекрывается с записью, то оно либо прочитает старое значение, либо новое, но несколько чтений, которые перекрывают запись, не должны соглашаться на котором и значение может показаться "мерцающим" назад и вперед. Это означает, что два чтения из одного потока (например, в потоке 3 выше), которые перекрывают запись, могут появляться "не в порядке": предыдущее чтение возвращает новое значение, а позднее возвращает старое значение.

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

Искусство многопроцессорного программирования от Maurice Herlihy и Nir Shavit дает хорошее описание наряду с примерами и примерами использования.