Diferença entre consistência estrita e consistência sequencial

8

Entendo consistência estrita e seqüencial de forma independente bastante bem.

C estrito basicamente impõe a ordem real na qual as instruções foram executadas no relógio global.

Consistência sequencial basicamente impõe o pedido apenas em um processador.

Estou tendo problemas para montar alguma literatura. http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html descreve a consistência sequencial como permitindo o 'atraso' da memória. Pode levar algum tempo para uma gravação se propagar por todos os processadores. Mas quando isso acontece, atinge todos eles ao mesmo tempo, o que é bom. Portanto, o seguinte é válido em Consistência sequencial

P1:  W(x)1
-----------------------
P2:        R(x)0 R(x)1

O que me preocupa agora são os seguintes processos, que são algo como o algoritmo de Dekker.

P1:  W(x)1  R(y)0
-----------------
P2:  W(y)1  R(x)0

Isso NÃO deve ser possível com consistência sequencial ( http://portal.acm.org/citation.cfm?id=1787234.1787255 pág 2). Não há um pedido total que possa dar esse resultado.

Mas faz sentido a ideia de que a consistência seqüencial permite que as gravações se propaguem lentamente e um encadeamento pode não ter idéia do que outros processadores estão fazendo.

O que estou perdendo aqui?

pl.programming-languages dc.parallel-comp concurrency jetru
fonte
Eu acho que você está confundindo consistência seqüencial e causal. SC é uma condição mais forte do que seu fraseado intuitivo ... se estou entendendo corretamente. Sua segunda execução é CC (e PRAM C), mas não SC.
Aaron Sterling
Sim, talvez. Minha pergunta é especificamente por que a segunda execução NÃO é sequencialmente consistente? Se o primeiro for, qual é o raciocínio especial que torna a execução 2 inconsistente?
jetru
Obrigado por todas as respostas. Eu também li sobre consistência causal e entendi que o que eu estava pensando era exatamente isso.
jetru

Respostas:

8

Você não está perdendo nada :)

O algoritmo de Dekker não será sequencialmente consistente no multiprocessador baseado em hierarquia de memória compartilhada, mas é muito possível, pois as atualizações de memória se propagam não acompanhando a atualização da memória local (cache), mas de forma assíncrona por meio de protocolos de coerência de cache como o MESI (modelo de memória mais fraca).

Em um uni-processador no qual o algoritmo de Dekker não é esse o caso, será estritamente consistente.

Sai Venkat
fonte
Portanto, considerando a propagação de atualizações de memória, estou relaxando o modelo de memória, portanto, no meu modelo de memória imaginado, a execução 2 é possível. Em um armazenamento de memória adequadamente sequencialmente consistente, as gravações se propagam instantaneamente. Isto está certo?
jetru
1
Sim. Se todo processo observar apenas sua memória local, é possível executar 2. Em uma consistência adequadamente seqüencial, as gravações não precisam se propagar instantaneamente, mas quando outro local se refere ou atualiza para o local gravado, o que normalmente ocorre.
Sai Venkat
4

Você já tem a resposta correta. A segunda execução não é sequencialmente consistente porque "não existe uma ordem total que possa fornecer esse resultado".

Eu acho que sua confusão vem dessa idéia:

a idéia de que a consistência sequencial permite que as gravações se propaguem lentamente e um encadeamento pode não ter idéia do que outros processadores estão fazendo.

Isto está correto. A propagação pode ser lenta. A consistência sequencial permite que um encadeamento não esteja ciente do que outros processos estão fazendo (para quaisquer programas). No entanto, a consistência sequencial não permite que cada thread não esteja ciente do que outros processos estão fazendo (para alguns programas, incluindo o algoritmo de Dekker).

A frase acima "para alguns programas" vem dessa consideração: mesmo com consistência sequencial, se os threads não usarem memória compartilhada, nenhum thread está ciente do comportamento de outro thread.

yhirai
fonte
3

Este documento também pode ajudar na compreensão, pois o título sugere a diferença entre as duas consistências mencionadas. (No entanto, é em grande parte sobre a implementação de objetos compartilhados SeqCon e StrictCon na passagem de mensagens, que é uma maneira de pensar sobre o atraso que você mencionou.)

Para responder sua pergunta específica: A consistência seqüencial exige que todos os eventos ocorram em alguma ordem sequencial e que o que acontece em um processo seja sempre consistente com o tempo.

Então, a razão pela qual 

P1:  W1(x,1)  R2(y)0
-------------------
P2:  W2(y,1)  R2(x)0

não é possível, é que deve haver alguma sequência global, por exemplo W1(x,1) R1(y)0 W2(y,1) R2(x)?. Nesta sequência, a última leitura claramente não pode retornar 0. Essa sequência não precisa ser consistente com o tempo real. É inteiramente possível (consistência sequencial) que em tempo real a sequência de eventos foi W1(x,1) W2(y,1) R1(y)0 R2(x)1. Essa sequência é ilegal por consistência estrita (como R1 (y) não retornou o valor da gravação anterior).

Martin B.
fonte
Desculpe pelo comentário tardio, mas será possível que W1 (x, 1) W2 (y, 1) R1 (y) 1 R2 (x) 1 também ocorra em um ambiente sequencialmente consistente? Se a ordem de execução está planejada para acontecer nessa ordem antes que aconteça a tempo?
William
A execução W1 (x, 1) W2 (y, 1) R1 (y) 1 R2 (x) 1 é sequencialmente consistente, até estritamente consistente, se não me engano (já estou um pouco cansado hoje).
Martin B.
Quanto ao que você quer dizer exatamente com "ordem de execução está planejada para acontecer", não sei se entendi.
Martin B.