Đồng bộ hóa và không có tranh chấp dữ liệu

Các cơ chế đồng bộ hóa điều phối các luồng đồng thời để dữ liệu chia sẻ được truy cập an toàn, và việc không có tranh chấp dữ liệu là thuộc tính giúp các chương trình đồng thời có thể dự đoán được.

Definition

Đồng bộ hóa là sự phối hợp các hoạt động đồng thời để thực thi thứ tự hoặc loại trừ lẫn nhau trên các tài nguyên chia sẻ, và việc không có tranh chấp dữ liệu là thuộc tính mà không có hai luồng nào truy cập cùng một vị trí bộ nhớ đồng thời với ít nhất một thao tác ghi mà không có sự đồng bộ hóa xen vào.

Scope

Chủ đề này bao gồm các cơ chế và thuộc tính giúp truy cập đồng thời vào trạng thái chia sẻ một cách chính xác: loại trừ lẫn nhau, khóa, semaphore và monitor, biến điều kiện, thuật toán không khóa và không chờ, bộ nhớ giao dịch, quan hệ xảy ra trước và phát hiện tranh chấp dữ liệu. Nó đề cập đến tắc nghẽn, tính nguyên tử và kỷ luật cần thiết để giữ cho các chương trình không có tranh chấp dữ liệu.

Core questions

• Làm thế nào để đạt được loại trừ lẫn nhau và những mối nguy hiểm của nó là gì (tắc nghẽn, đói tài nguyên)?
• Điều gì phân biệt đồng bộ hóa dựa trên khóa với đồng bộ hóa không khóa?
• Quan hệ xảy ra trước định nghĩa tranh chấp dữ liệu như thế nào?
• Làm thế nào để phát hiện tranh chấp dữ liệu tự động?

Key theories

Loại trừ lẫn nhau

Giải pháp của Dijkstra cho vấn đề kiểm soát đồng thời đã thiết lập loại trừ lẫn nhau như một yêu cầu đồng bộ hóa cơ bản, đảm bảo rằng các phần quan trọng không được thực thi đồng thời.

Bộ nhớ giao dịch

Herlihy và Moss đã đề xuất bộ nhớ giao dịch, trong đó các nhóm thao tác bộ nhớ thực thi một cách nguyên tử, cung cấp một giải pháp thay thế có thể kết hợp cho việc khóa chi tiết để xây dựng các cấu trúc dữ liệu đồng thời.

Quan hệ xảy ra trước và phát hiện tranh chấp động

Dựa trên quan hệ xảy ra trước của Lamport, công cụ phát hiện Eraser đã chỉ ra cách tìm tranh chấp dữ liệu một cách động bằng cách kiểm tra một kỷ luật khóa, minh họa việc phát hiện tranh chấp tự động.

Clinical relevance

Đồng bộ hóa chính xác là điều cần thiết cho phần mềm đồng thời và song song đáng tin cậy; tranh chấp dữ liệu gây ra một số lỗi khó nắm bắt nhất trong thực tế. Các công cụ phát hiện tranh chấp, bộ nhớ giao dịch và các mẫu đồng bộ hóa có kỷ luật là những công cụ trung tâm để xây dựng các hệ thống đa luồng đáng tin cậy.

History

Giải pháp loại trừ lẫn nhau của Dijkstra năm 1965 và các semaphore tiếp theo của ông đã đặt nền móng cho đồng bộ hóa, tiếp theo là các monitor của Hoare và Brinch Hansen. Quan hệ xảy ra trước của Lamport năm 1978 là cơ sở cho các định nghĩa tranh chấp hiện đại; Herlihy và Moss đã giới thiệu bộ nhớ giao dịch vào năm 1993, và các công cụ phát hiện tranh chấp động như Eraser (1997) và các công cụ xảy ra trước sau này đã trở thành tiêu chuẩn để gỡ lỗi đồng thời.

Debates

Khóa so với các phương pháp không khóa và giao dịch

Các nhà thiết kế tranh luận về đồng bộ hóa dựa trên khóa truyền thống, đơn giản nhưng dễ bị tắc nghẽn và khả năng kết hợp kém, so với các thuật toán không khóa và bộ nhớ giao dịch, giúp cải thiện khả năng kết hợp và đảm bảo tiến độ với chi phí phức tạp hoặc chi phí chung.

Key figures

• Edsger Dijkstra
• Leslie Lamport
• Maurice Herlihy
• C. A. R. Hoare
• Stefan Savage

Seminal works

• dijkstra1965
• herlihy1993
• savage1997
• lamport1978

Frequently asked questions

Tranh chấp dữ liệu là gì?

Tranh chấp dữ liệu xảy ra khi hai luồng truy cập cùng một vị trí bộ nhớ đồng thời, ít nhất một truy cập là ghi, và các truy cập không được sắp xếp theo đồng bộ hóa, dẫn đến hành vi không xác định hoặc không thể đoán trước trong hầu hết các mô hình bộ nhớ.

Sự khác biệt giữa đồng bộ hóa dựa trên khóa và đồng bộ hóa không khóa là gì?

Đồng bộ hóa dựa trên khóa sử dụng loại trừ lẫn nhau để chỉ một luồng được vào một phần quan trọng tại một thời điểm, trong khi đồng bộ hóa không khóa sử dụng các thao tác nguyên tử để đảm bảo rằng một số luồng luôn tiến triển mà không cần giữ khóa, tránh tắc nghẽn.