Thuật toán đa luồng đáng chú ý là khó thiết kế/gỡ lỗi/chứng minh. Thuật toán của Dekker là một ví dụ điển hình về mức độ khó có thể thiết kế một thuật toán đồng bộ chính xác. Hệ điều hành hiện đại của Tanenbaum được làm đầy với các ví dụ trong phần IPC của nó. Có ai có một tài liệu tham khảo tốt (sách, bài viết) cho điều này? Cảm ơn!Xác minh tính chính xác của các thuật toán đa luồng
@Chỉ trong trường hợp: I is. Nhưng từ những gì tôi học được, làm như vậy cho một thuật toán không tầm thường là một nỗi đau lớn. Tôi để cái thứ đó cho những người trí tuệ hơn. Tôi đã học được những gì tôi biết từ Thiết kế Chương trình Song song: Một Tổ chức (1988) bởi KM Chandy, J Misra
Không thể chứng minh được điều gì mà không xây dựng theo người quản lý, điều đầu tiên bạn muốn làm là làm quen với mô hình bộ nhớ của nền tảng đích của bạn; Cả Java và x86 đều có các mô hình bộ nhớ rắn và tiêu chuẩn hóa - tôi không chắc về CLR, nhưng nếu mọi thứ khác thất bại, bạn sẽ xây dựng dựa trên mô hình bộ nhớ của kiến trúc CPU mục tiêu của bạn. Ngoại lệ cho quy tắc này là nếu bạn dự định sử dụng ngôn ngữ không cho phép bất kỳ trạng thái có thể thay đổi được chia sẻ nào - tôi đã nghe Erlang giống như vậy.
Vấn đề đồng thời đầu tiên được chia sẻ trạng thái có thể thay đổi.
Điều đó có thể được cố định bởi:
Prob thứ hai lem đồng thời là ấn phẩm an toàn. Làm thế nào để bạn làm cho dữ liệu có sẵn cho các chủ đề khác? Làm thế nào để bạn thực hiện một bàn giao? Bạn sẽ là giải pháp cho vấn đề này trong mô hình bộ nhớ, và (hy vọng) trong API. Java, ví dụ, có nhiều cách để xuất bản trạng thái và gói java.util.concurrent chứa các công cụ được thiết kế đặc biệt để xử lý giao tiếp giữa các luồng.
Vấn đề đồng thời thứ ba (và khó khăn hơn) đang bị khóa. Việc khóa trật tự không được quản lý là nguồn gốc của khóa chết. Bạn có thể chứng minh về mặt phân tích, xây dựng dựa trên người mẫu guarentees bộ nhớ, có hay không có khóa chết trong mã của bạn. Tuy nhiên, bạn cần phải thiết kế và viết mã của bạn với ý nghĩ đó, nếu không sự phức tạp của mã có thể nhanh chóng làm cho một phân tích như vậy không thể thực hiện trong thực tế.
Sau đó, một khi bạn có, hoặc trước khi bạn thực hiện, chứng minh việc sử dụng đồng thời chính xác, bạn sẽ phải chứng minh tính đúng đắn của luồng đơn. Tập hợp các lỗi có thể xảy ra trong một cơ sở mã đồng thời tương đương với tập hợp các lỗi chương trình đơn luồng, cộng với tất cả các lỗi đồng thời có thể xảy ra.
Câu trả lời ngắn gọn: thật khó.
Có một số công việc thực sự tốt trong DEC SRC Modula-3 và thông tin từ cuối những năm 1980.
ví dụ:
Thread synchronization: A formal specification (1991) bởi AD Birrell, JV Guttag, JJ Horning, Lập trình với Modula-3 R Levin Hệ thống , chương 5
Extended static checking (1998) David L. Detlefs, David L. Detlefs, K. Rustan, K. Rustan, M. Leino, M. Leino, Greg Nelson, Greg Nelson, James B. Saxe, James B. Saxe
Một số ý tưởng hay từ Modula - - 3 đang biến nó thành thế giới Java, ví dụ: JML, mặc dù "JML hiện bị giới hạn ở đặc điểm tuần tự", theo số intro.
Liên kết gatekeeper.dec.com bị hỏng, nhưng báo cáo SRC DEC về kiểm tra tĩnh mở rộng có sẵn tại http://research.microsoft.com/en-us/um/people/leino/papers/src-159.pdf . Tôi đồng ý ESC thực sự là một công việc tốt. –
Tôi không có bất kỳ tham chiếu cụ thể nào, nhưng bạn có thể muốn xem xét lý thuyết Owicki-Gries (nếu bạn thích định lý) hoặc lý thuyết/đại số xử lý (có sẵn nhiều công cụ kiểm tra mô hình khác nhau) .
The Pi-Calculus, A Theory of Mobile Processes là một nơi tốt để bắt đầu.
"Nguyên tắc đồng thời lập trình và phân phối", M. Ben-Ari
ISBN-13: 978-0-321-31283-9
Họ có ở trên sổ sách săn trực tuyến cho việc đọc:
http://my.safaribooksonline.com/9780321312839
Đó là khá nhiều chính xác những gì tôi đang tìm kiếm. Cảm ơn! – Leandro
@Leandro: Nếu đó là "khá chính xác" những gì bạn đang tìm kiếm, thì bạn có thể 'chấp nhận' câu trả lời. –
Hãy thử xây dựng. – GEOCHET