đói là gì?

Question

Trong các hệ thống đa nhiệm, một số điều kiện bất thường ngăn cản tiến trình thực hiện các quy trình hoặc luồng. Tôi sẽ đề cập đến cả hai quy trình và chủ đề đơn giản là "quy trình". Hai trong số các điều kiện này được gọi là khóa chết và khóa trực tiếp.

Tên cũ đề cập đến các quy trình đang chặn lẫn nhau, do đó ngăn không cho thực thi. Cái sau đề cập đến các quá trình ngăn cản lẫn nhau từ tiến trình, nhưng không thực sự chặn việc thực hiện. Ví dụ, họ có thể liên tục gây ra cho nhau để rollback giao dịch, không bao giờ có thể hoàn thành chúng. Một điều kiện khác được gọi là nạn đói tài nguyên, trong đó một hoặc nhiều tài nguyên hữu hạn, cần thiết cho tiến trình của các quy trình, đã bị chúng cạn kiệt và không thể phục hồi trừ khi tiến trình xử lý. Đây cũng là trường hợp đặc biệt của khóa trực tiếp.

Tôi muốn biết nếu có bất kỳ định nghĩa nào khác, đặc biệt là một định nghĩa học thuật, cho "đói" không giới hạn ở "nạn đói tài nguyên". Tài liệu tham khảo được đặc biệt chào đón.

Và, không, đây không phải là bài tập về nhà. :-)

Answer 1

Tôi sẽ không nói rằng nạn đói tài nguyên là trường hợp đặc biệt của livelock.Thông thường:

• Trong livelock, không có luồng nào tiến bộ nhưng vẫn tiếp tục thực thi. (Trong bế tắc, họ thậm chí không tiếp tục thi hành)

• Khi chết đói, một số chủ đề DO thực hiện tiến trình và một số luồng không thực thi.

Giải thích tốt: http://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html. Nhưng tôi hiểu việc lựa chọn thuật ngữ có thể khác nhau.

Khi nói đến nạn đói, định nghĩa tôi nghe là:

Giả sử chúng ta có thể xác định một con đường vô hạn thực hiện (interlace) phù hợp với các giả định (ngữ nghĩa semaphore, hành vi scheduler OS ...) sao cho thread T bị đình chỉ chờ đợi một số tài nguyên và không bao giờ tiếp tục, ngay cả khi nó có thể vô hạn nhiều lần. Sau đó T được gọi là đói.

Nhưng thực tế không khớp với điều đó. Giả sử hai luồng thực thi phần critial trong một vòng lặp vô hạn. Mã đồng bộ của bạn cho phép chuỗi đầu tiên vào phần critial một lần mỗi giờ. Có đói không? Cả hai chủ đề đều được phép tiến bộ, nhưng chủ đề đầu tiên làm chậm công việc của nó.

Nguồn chết đói đơn giản nhất là các ẩn dụ yếu. Nếu bạn đang sử dụng một đồng bộ nguyên thủy (hoặc xây dựng của riêng bạn) mà cư xử tương tự, sau đó đói sẽ kết quả.

vấn đề cổ điển nơi đói nổi tiếng:

• Độc giả-tác giả vấn đề. Nó có thể đồng bộ hóa các chủ đề như vậy (1) độc giả sẽ có thể chết đói những nhà văn (2) các tác giả sẽ có thể chết đói độc giả (3) không có nạn đói sẽ xảy ra (Xem http://en.wikipedia.org/wiki/Readers-writers_problem)

• triết gia ăn (http://en.wikipedia.org/wiki/Dining_philosophers_problem)

Để biết thêm chi tiết, tôi hết lòng khuyên The Little Book of Semaphores (miễn phí): http://www.greenteapress.com/semaphores/.

Bạn đang hỏi liệu mọi nạn đói có phải là do chờ đợi một số tài nguyên hay không. Tôi muốn nói - vâng.

Một thread có thể bị đình chỉ:

(1) trên một số cuộc gọi hệ thống chặn - chờ đợi vào/mua lại một mutex, semaphore, biến có điều kiện; write(), poll(), v.v.

(2) về một số thao tác không chặn - như thực hiện tính toán.

Đói trên (1) đang bị đói trên tài nguyên (mutexes, buffer, v.v.).

Bắt đầu trên (2) đang bị lỗi trên CPU - bạn có thể coi đó là tài nguyên. Nếu nó xảy ra, vấn đề là với lịch trình.

HTH

Answer 2

Công việc cũng là một loại tài nguyên. Khi phân phối công việc trong thiết lập của người tiêu dùng sản xuất không công bằng (hoặc lý tưởng), một số chủ đề có thể không có đủ các mục công việc để giữ cho chúng luôn bận rộn.

Answer 3

Hãy tưởng tượng bạn đang ở trong hàng đợi để mua thực phẩm tại một nhà hàng, nơi phụ nữ mang thai được ưu tiên. Và chỉ có một bó toàn bộ phụ nữ mang thai đến mọi lúc.

Bạn sẽ sớm bị đói. ;)

Bây giờ hãy tưởng tượng bạn là một quá trình ưu tiên thấp và phụ nữ mang thai là những ưu tiên cao hơn. =)

Answer 4

Khu vực khác nơi đói hoặc "chặn không xác định" thường xuất hiện là khi nói về các thuật toán Lập lịch ưu tiên. Thuật toán lập lịch ưu tiên có khả năng để lại một số quy trình ưu tiên thấp chờ đợi vô thời hạn. Một luồng ổn định các quy trình ưu tiên cao hơn có thể ngăn chặn quá trình ưu tiên thấp từ khi chạy.

Trong trường hợp có lịch trình ưu tiên, giải pháp là "lão hóa". Lão hóa là kỹ thuật dần dần tăng mức ưu tiên của các quy trình chờ đợi trong hệ thống trong một thời gian dài.

Answer 5

Quá trình đói chỉ đơn giản là khi quá trình hoặc dịch vụ không được phân phát, ngay cả khi không có bế tắc trên hệ thống.

Đây là ví dụ mà tôi vừa tạo cho mục đích làm rõ.

Hãy tưởng tượng một thuật toán kiểm soát máy tính truy cập vào WAN hoặc một cái gì đó tương tự. Thuật toán này có thể có một chính sách cho biết "Cung cấp quyền truy cập ưu tiên cho những máy tính sẽ sử dụng ít băng thông hơn", điều đó có vẻ như một chính sách phù hợp, nhưng sau đó điều gì sẽ xảy ra khi một máy tính muốn truy cập mạng để tải lên ftp gửi vài GB ở đâu đó. Với chính sách này một mình, máy tính đó sẽ chết đói vì thuật toán sẽ không bao giờ chọn máy tính đó, vì sẽ luôn có các máy tính khác yêu cầu sử dụng băng thông nhỏ hơn.

Điều đó được gọi là đói.

Answer 6

Ví dụ về khóa đói trong java.Đó là tất cả về ưu tiên luồng. Không chắc chắn nếu ví dụ là tốt, nhưng bạn có thể có một cái nhìn here.

Answer 7

Quy trình không nhận được tài nguyên hoặc tài nguyên trong thời gian dài hơn. Đây không phải là bế tắc, bởi vì một tiến trình chạy không có vấn đề gì. Lão hóa có thể được sử dụng để giải quyết vấn đề này, một yếu tố lão hóa được sử dụng cho mỗi yêu cầu.