Deadlock
Deadlock (Khóa chết) là trạng thái xảy ra trong môi trường đa nhiệm (muti-threading) khi hai hoặc nhiều tiến trình đi vào vòng lặp chờ tài nguyên mãi mãi.
Ví dụ
Thread 1 | Thread 2 |
---|---|
Muốn lấy tài nguyên A và B | Muốn lấy tài nguyên A và B |
Chiếm tài nguyên A, chờ Thread 2 bắt đầu chạy cho tới khi Thread 2 đợi tài nguyên A giải phóng | |
Chiếm tài nguyên B | |
Đợi tài nguyên A giải phóng | |
Đợi tài nguyên B giải phóng | |
Deadlock |
Đối phó với deadlock
Điều kiện xảy ra deadlock
Có bốn điều kiện cần thiết để deadlock có thể xảy ra.
- Điều kiện loại trừ tương hỗ (Mutual exclusion): Một tài nguyên không thể sử dụng bởi nhiều hơn một tiến trình tại một thời điểm
- Điều kiện giữ và chờ (Hold and wait): Một quá trình đang giữ ít nhất một tài nguyên và đợi thêm tài nguyên do quá trình khác đang giữ
- Điều kiện không ưu tiên (No preemption): Các tài nguyên không thể bị đòi lại, chúng chỉ có thể được giải phóng bởi chính tiến trình chiếm giữ chúng
- Điều kiện chu trình chờ (Circular wait): Các tiến trình giữ tài nguyên và chờ các tài nguyên bị giữ bởi tiến trình khác, tạo thành một chu trình. Ví dụ: Tiến trình 1, chiếm A1, chờ A2. Tiến trình 2 chiếm A2, chờ A3,... Tiến trình N chiếm An, chờ A1
Các cách đối phó với deadlock
- Ngăn chặn deadlock: ngăn chặn ít nhất 1 trong 4 điều kiện để xảy ra deadlock nêu trên. Chẳng hạn: cho phép chia sẻ tài nguyên, cho phép trưng dụng,...
- Phòng tránh deadlock: dự đoán trước deadlock có xảy ra hay không trước khi tiến hành phân phối tài nguyên cho tiến trình. Ví dụ: giải thuật nhà băng (Banker's algorithm).
- Phát hiện và khắc phục deadlock: nếu không thể phòng tránh hay ngăn chặn deadlock, cứ để deadlock xảy ra và ta sẽ phát hiện và đi khắc phục chúng. Phuơng pháp này phù hợp với hệ thống ít xảy ra deadlock và hậu quả của deadlock là ít nghiêm trọng.
Tham khảo
Liên kết ngoài
Bài viết
- "Distributed Deadlock Detection Lưu trữ 2015-11-02 tại Wayback Machine" by JoAnne L. Holliday and Amr El Abbadi
- "Deadlock detection in distributed databases" by Edgar Knapp
- "Advanced Synchronization in Java Threads" by Scott Oaks and Henry Wong
Bản in
- "Deadlock Detection in Distributed Object Systems" by Nima Kaveh and Wolfgang Emmerich
- "Confirmation of Deadlock Potentials Detected by Runtime Analysis" by Saddek Bensalem, Jean-Claude Fernandez, Klaus Havelund and Laurent Mounier
- Coffman, E.G., M.J. Elphick, and A. Shoshani, System Deadlocks, ACM Computing Surveys, 3, 2, 67-78 (1971).
- Eliminating Receive Livelock in an Interrupt-driven Kernel by Jeffrey C. Mogul, K. K. Ramakrishnan
- Havender, J. W., "Avoiding deadlock in multitasking systems", IBM Systems Journal, Volume 7, Number 2, Page 74 (1968)
Chung
🔥 Top keywords: Đài Truyền hình Kỹ thuật số VTCTrang ChínhGiỗ Tổ Hùng VươngTrương Mỹ LanĐặc biệt:Tìm kiếmHùng VươngVương Đình HuệUEFA Champions LeagueKuwaitChiến dịch Điện Biên PhủFacebookĐài Truyền hình Việt NamTrần Cẩm TúĐội tuyển bóng đá quốc gia KuwaitGoogle DịchViệt NamCúp bóng đá U-23 châu ÁCúp bóng đá U-23 châu Á 2024Real Madrid CFBảng xếp hạng bóng đá nam FIFACleopatra VIITô LâmTim CookNguyễn Phú TrọngHồ Chí MinhHai Bà TrưngManchester City F.C.VnExpressChủ tịch nước Cộng hòa xã hội chủ nghĩa Việt NamNguyễn Ngọc ThắngĐền HùngCúp bóng đá trong nhà châu Á 2024Võ Văn ThưởngOne PieceLịch sử Việt NamCuộc đua xe đạp toàn quốc tranh Cúp truyền hình Thành phố Hồ Chí Minh 2024Phạm Minh ChínhTikTokĐinh Tiên Hoàng