Perbedaan antara Konsistensi Ketat dan Konsistensi Berurutan

8

Saya memahami konsistensi yang ketat dan berurutan secara mandiri dengan cukup baik.

Strict C pada dasarnya menegakkan urutan aktual di mana instruksi dijalankan pada jam global.

Sequential Consistency pada dasarnya memberlakukan pesanan hanya pada satu prosesor.

Saya mengalami kesulitan mengumpulkan beberapa literatur. http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html menjelaskan konsistensi sekuensial yang memungkinkan memori 'lag'. Mungkin perlu waktu untuk menulis untuk menyebar di semua prosesor. Tetapi ketika itu terjadi, itu mencapai mereka semua sekaligus yang baik-baik saja. Dengan demikian, berikut ini valid di bawah Konsistensi Berurutan

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

Yang menjadi perhatian saya sekarang adalah proses-proses berikut, yang merupakan sesuatu seperti algoritma Dekker.

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

Tentunya ini TIDAK mungkin dilakukan di bawah konsistensi Sequential ( http://portal.acm.org/citation.cfm?id=1787234.1787255 hal 2). Tidak ada pesanan total yang dapat memberikan hasil ini.

Tetapi masuk akal dari gagasan bahwa konsistensi berurutan memungkinkan penulisan untuk menyebar secara lambat dan satu utas mungkin tidak memiliki gagasan mengenai apa yang sedang dilakukan prosesor lain.

Apa yang kulewatkan di sini?

pl.programming-languages dc.parallel-comp concurrency jetru
sumber
Saya pikir Anda membingungkan konsistensi berurutan dan konsistensi sebab akibat. SC adalah kondisi yang lebih kuat daripada ungkapan intuitif Anda ... jika saya memahami Anda dengan benar. Eksekusi kedua Anda adalah CC (dan PRAM C) tetapi bukan SC.
Aaron Sterling
Ya mungkin Pertanyaan saya secara khusus mengapa eksekusi kedua TIDAK konsisten secara berurutan? Jika yang pertama adalah, apa alasan khusus yang membuat eksekusi 2 tidak konsisten?
jetru
Terima kasih atas semua jawabannya. Saya juga membaca tentang konsistensi sebab akibat dan mengerti bahwa apa yang saya pikirkan adalah persis seperti itu.
jetru

Jawaban:

8

Anda tidak melewatkan apapun :)

Algoritma Dekker tidak akan konsisten secara berurutan pada multiprosesor berbasis hirarki memori terdistribusi bersama tetapi sangat mungkin karena pembaruan memori menyebar tidak sejalan dengan pembaruan memori (cache) lokal tetapi secara tidak sinkron melalui protokol Cache Coherence seperti MESI (model memori Weaker).

Pada uni-prosesor di mana algoritma Dekker ini tidak terjadi dan itu akan sangat konsisten.

Sai Venkat
sumber
Jadi dengan mempertimbangkan penyebaran pembaruan memori, saya benar-benar bersantai dengan model memori, maka dalam model memori yang saya bayangkan, eksekusi 2 adalah mungkin. Dalam penyimpanan memori yang konsisten secara berurutan, penulisan akan menyebar secara instan. Apakah ini benar?
jetru
1
Ya .. Jika setiap proses hanya melihat eksekusi memori lokal 2 adalah mungkin. Dalam konsistensi berurutan yang tepat, penulisan tidak perlu disebarkan secara instan tetapi ketika lokasi lain merujuk atau memperbarui ke lokasi yang ditulis yang biasanya merupakan kasus.
Sai Venkat
4

Anda sudah memiliki jawaban yang benar. Eksekusi kedua tidak konsisten secara berurutan karena "tidak ada urutan total yang dapat memberikan hasil ini".

Saya kira kebingungan Anda berasal dari ide ini:

gagasan bahwa konsistensi berurutan memungkinkan penulisan untuk menyebar perlahan dan satu utas mungkin tidak memiliki gagasan tentang apa yang sedang diproses prosesor lain.

Ini benar. Propagasi bisa lambat. Konsistensi berurutan memungkinkan satu utas tidak menyadari proses apa yang sedang dilakukan (untuk program apa pun). Namun, konsistensi berurutan tidak memungkinkan setiap utas tidak mengetahui proses apa yang sedang dilakukan (untuk beberapa program, termasuk algoritma Dekker).

Frase di atas "untuk beberapa program" berasal dari pertimbangan ini: bahkan di bawah konsistensi berurutan, jika utas tidak menggunakan memori bersama, tidak ada utas yang mengetahui perilaku utas lainnya.

yhirai
sumber
3

IniMakalah juga dapat membantu dalam memahami, karena judulnya menyarankan tentang perbedaan antara dua konsistensi yang Anda sebutkan. (Namun, sebagian besar tentang implementasi objek bersama SeqCon dan StrictCon dalam penyampaian pesan, yang merupakan salah satu cara untuk berpikir tentang kelambatan yang Anda sebutkan.)

Untuk menjawab pertanyaan spesifik Anda: Konsistensi berurutan menuntut agar semua peristiwa terjadi dalam urutan berurutan dan apa yang terjadi pada satu proses selalu konsisten dengan waktu.

Jadi alasannya 

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

tidak mungkin, adalah harus ada beberapa urutan global, misalnya W1(x,1) R1(y)0 W2(y,1) R2(x)?. Dalam urutan ini bacaan terakhir jelas tidak dapat kembali 0. Urutan ini tidak harus konsisten dengan waktu nyata. Sangat mungkin (konsistensi berurutan) bahwa secara real-time urutan peristiwa adalah W1(x,1) W2(y,1) R1(y)0 R2(x)1. Urutan ini ilegal untuk konsistensi yang ketat (karena R1 (y) tidak mengembalikan nilai dari penulisan sebelumnya).

Martin B.
sumber
Maaf tentang komentar yang terlambat, tetapi mungkinkah W1 (x, 1) W2 (y, 1) R1 (y) 1 R2 (x) 1 terjadi di lingkungan yang konsisten secara berurutan juga? Jika pesanan eksekusi diatur untuk terjadi dalam pesanan ini sebelum terjadi pada waktunya?
William
Eksekusi W1 (x, 1) W2 (y, 1) R1 (y) 1 R2 (x) 1 secara konsisten konsisten, bahkan sangat konsisten, jika saya tidak salah (saya sudah agak lelah hari ini).
Martin B.
Mengenai apa yang Anda maksud persis dengan "perintah eksekusi diatur untuk terjadi", saya tidak yakin saya mengerti.
Martin B.