Các mô hình nhất quán bộ nhớ

Mô hình nhất quán bộ nhớ quy định những giá trị nào mà các thao tác đọc có thể quan sát khi các luồng đồng thời truy cập bộ nhớ chia sẻ, định nghĩa các đảm bảo về thứ tự mà lập trình viên có thể tin cậy.

Definition

Mô hình nhất quán bộ nhớ là một đặc tả hình thức về các giá trị mà các thao tác đọc có thể trả về trong một thực thi đồng thời, cố định các thứ tự truy cập bộ nhớ mà ngôn ngữ, trình biên dịch và phần cứng phải tuân thủ.

Scope

Chủ đề này bao gồm phổ các mô hình nhất quán từ nhất quán tuần tự đến các mô hình lỏng lẻo và yếu, mối quan hệ xảy ra trước (happens-before) và các đảm bảo không có tranh chấp dữ liệu (data-race-free), các thứ tự bộ nhớ phần cứng (như thứ tự lưu trữ toàn bộ), và các mô hình bộ nhớ cấp ngôn ngữ cho C++ và Java. Nó giải quyết lý do tồn tại của các mô hình lỏng lẻo, cách các hàng rào (fences) và các thao tác nguyên tử (atomics) khôi phục thứ tự, và cách suy luận một cách hợp lý về bộ nhớ đồng thời.

Core questions

• Một chương trình có thể quan sát những thứ tự thao tác bộ nhớ nào một cách hợp lệ?
• Tại sao các mô hình bộ nhớ lỏng lẻo tồn tại và chúng cho phép điều gì?
• Đảm bảo không có tranh chấp dữ liệu đơn giản hóa việc suy luận như thế nào?
• Các hàng rào và thao tác nguyên tử thực thi thứ tự như thế nào?

Key theories

Nhất quán tuần tự

Lamport đã định nghĩa nhất quán tuần tự, trong đó một thực thi đa bộ xử lý phải xuất hiện như một sự xen kẽ duy nhất của các thao tác tuân thủ thứ tự chương trình của mỗi bộ xử lý, mô hình cơ sở trực quan mạnh nhất.

Nhất quán lỏng lẻo và đảm bảo SC-for-DRF

Adve và Gharachorloo giải thích các mô hình lỏng lẻo và nguyên tắc rằng các chương trình không có tranh chấp dữ liệu hoạt động như thể nhất quán tuần tự, dung hòa hiệu suất với khả năng lập trình.

Các mô hình bộ nhớ cấp ngôn ngữ

Manson, Pugh và Adve đã hình thức hóa mô hình bộ nhớ Java bằng cách sử dụng mối quan hệ xảy ra trước (happens-before), định nghĩa những tối ưu hóa nào là hợp lệ và những đảm bảo nào mà ngay cả các chương trình có tranh chấp cũng nhận được.

Clinical relevance

Vì các bộ xử lý đa lõi và các trình biên dịch tối ưu hóa sắp xếp lại các thao tác bộ nhớ, các mô hình bộ nhớ ngôn ngữ là cần thiết để viết mã đồng thời chính xác, có thể di động. Chúng cho lập trình viên biết khi nào cần đồng bộ hóa và định nghĩa các đảm bảo mà các thư viện và môi trường chạy có thể cung cấp.

History

Lamport đã hình thức hóa nhất quán tuần tự vào năm 1979. Khi phần cứng áp dụng các thứ tự lỏng lẻo để tăng hiệu suất, hướng dẫn của Adve và Gharachorloo năm 1996 đã hệ thống hóa bối cảnh mô hình nhất quán và khuôn khổ không có tranh chấp dữ liệu. Các nhà thiết kế ngôn ngữ sau đó đã xây dựng các mô hình bộ nhớ vào các đặc tả, với mô hình bộ nhớ Java (2005) và mô hình bộ nhớ C++11 thiết lập phương pháp tiếp cận hiện đại.

Debates

Ngữ nghĩa của các chương trình có tranh chấp

Một câu hỏi khó là nên đưa ra những đảm bảo nào, nếu có, cho các chương trình chứa tranh chấp dữ liệu; các mô hình ngôn ngữ phải ngăn chặn các giá trị 'từ hư không' trong khi vẫn cho phép các tối ưu hóa trình biên dịch và phần cứng mạnh mẽ.

Key figures

• Leslie Lamport
• Sarita Adve
• Kourosh Gharachorloo
• William Pugh
• Jeremy Manson

Seminal works

• lamport1979
• adve1996
• manson2005

Frequently asked questions

Tại sao tất cả các hệ thống không chỉ sử dụng nhất quán tuần tự?

Nhất quán tuần tự cấm nhiều tối ưu hóa trình biên dịch và phần cứng giúp cải thiện hiệu suất, vì vậy hầu hết các hệ thống thực tế áp dụng các mô hình lỏng lẻo và cung cấp các nguyên thủy đồng bộ hóa để khôi phục thứ tự mạnh hơn chỉ khi cần thiết.

Đảm bảo không có tranh chấp dữ liệu là gì?

Theo nhiều mô hình bộ nhớ ngôn ngữ, một chương trình không chứa tranh chấp dữ liệu (tất cả các truy cập xung đột được đồng bộ hóa đúng cách) được đảm bảo hoạt động như thể bộ nhớ nhất quán tuần tự.