Deadlock Trong Hệ điều Hành? Kiến Thức Cơ Bản - W3seo

Rate this post

Mọi Process đều cần một số tài nguyên để hoàn thành Process thực thi. Tuy nhiên, tài nguyên được cấp theo thứ tự tuần tự.

• Process yêu cầu một số tài nguyên.
• Hệ điều hành cấp tài nguyên nếu nó có sẵn, nếu không, hãy để Process chờ.
• Process sử dụng nó và phát hành khi hoàn thành.

Hướng dẫn khác:

1. Ngăn chặn Deadlock trong hệ điều hành
2. Tìm hiểu về Process trong hệ điều hành
3. Process Synchronization trong hệ điều hành 
4. Giới thiệu thuật toán semaphore trong Hệ điều hành
5. Cơ Chế Interested Variable Trong Hệ Điều Hành
6. Giải pháp Paterson trong Hệ điều hành

Tóm tắt nội dung

Toggle

• Deadlock là gì ?
• Sự khác biệt giữa Starvation và Deadlock
• Các điều kiện cần thiết cho Deadlocks
• Các chiến lược để xử lý Deadlock
  • Deadlock Ignorance
  • Deadlock prevention
  • Deadlock avoidance
  • Deadlock detection và recovery
• Phát Hiện và Phục Hồi Deadlock Trong Hệ Điều Hành
  • Phát Hiện Deadlock
  • Phục Hồi Từ Deadlock
  • Sử Dụng Resource Allocation Graph (RAG) Để Phát Hiện Deadlock
  • Ma Trận Phân Bổ và Yêu Cầu
• Deadlock ảnh hưởng như thế nào đến hiệu suất của hệ thống?
• Những câu hỏi phổ biến về deadlock trong hệ điều hành

Deadlock là gì ?

Deadlock là một tình huống xảy ra trong hệ thống máy tính, khi hai hoặc nhiều tiến trình (process) cùng cố gắng giành quyền truy cập vào tài nguyên chung (shared resource) mà mỗi tiến trình cần để hoàn thành công việc của mình, nhưng không thể hoàn thành nếu thiếu tài nguyên này. Khi đó, các tiến trình sẽ bị kẹt lại (deadlocked), không thể tiếp tục thực hiện công việc và chờ đợi tài nguyên được giải phóng.

Ví dụ, nếu tiến trình A đang giữ khóa (lock) trên tài nguyên X và yêu cầu khóa tài nguyên Y, trong khi tiến trình B đang giữ khóa trên tài nguyên Y và yêu cầu khóa tài nguyên X, thì hai tiến trình này sẽ bị kẹt lại vì không thể giải phóng tài nguyên hiện tại của mình và không thể nhận được tài nguyên mới. Đây là một ví dụ về deadlock trong hệ thống máy tính.

Deadlock là một tình huống trong đó mỗi tiến trình máy tính chờ đợi một tài nguyên đang được gán cho một số tiến trình khác. Trong tình huống này, không có Process nào được thực thi vì tài nguyên mà nó cần, được giữ bởi một số Process khác cũng đang chờ một số tài nguyên khác được giải phóng.

Các bài viết liên quan:

• Tìm hiểu về Process trong hệ điều hành
• Process Synchronization trong hệ điều hành
• Cơ chế Interested Variable trong hệ điều hành
• Cách Nhận Liên kết ngược với Trang Tài nguyên & Liên kết

Giả sử rằng có ba Process P1, P2 và P3. Có ba tài nguyên khác nhau R1, R2 và R3. R1 được gán cho P1, R2 được gán cho P2 và R3 được gán cho P3.

Sau một thời gian, P1 yêu cầu R1 đang được P2 sử dụng. P1 tạm dừng Process thực thi của nó vì nó không thể hoàn thành nếu không có R2. P2 cũng yêu cầu R3 đang được P3 sử dụng. P2 cũng dừng Process thực thi của nó vì nó không thể tiếp tục mà không có R3. P3 cũng yêu cầu R1 đang được P1 sử dụng do đó P3 cũng dừng thực thi.

Trong kịch bản này, một chu trình đang được hình thành giữa ba Process. Không có Process nào đang diễn ra và tất cả đều đang chờ đợi. Máy tính không phản hồi vì tất cả các Process đã bị chặn.

Sự khác biệt giữa Starvation và Deadlock

Deadlock	Starvation
Deadlock là tình huống không có Process nào bị chặn và không có Process nào tiếp diễn	Starvation là tình huống trong đó Process có mức độ ưu tiên thấp bị chặn và Process có mức độ ưu tiên cao vẫn tiếp tục.
Deadlock lại là sự chờ đợi vô hạn	Starvation là một sự chờ đợi lâu dài nhưng không phải là vô hạn.
Mỗi lần Deadlock luôn là một lần Starvation	Mọi Starvation không cần phải Deadlock
Resource được yêu cầu bị chặn bởi Process khác	Resource được yêu cầu liên tục được sử dụng bởi các Process ưu tiên cao hơn.
Deadlock xảy ra khi Mutual exclusion, hold và wait, No preemption và circular wait	Nó xảy ra do mức độ ưu tiên và quản lý tài nguyên không được kiểm soát

Xem thêm Tránh deadlock trong hệ điều hành

Các điều kiện cần thiết cho Deadlocks

1. Mutual Exclusion

Một tài nguyên chỉ có thể được chia sẻ theo cách Mutual Exclusion. Nó ngụ ý, nếu hai tiến trình không thể sử dụng cùng một tài nguyên cùng một lúc.

2. Hold and Wait

Một tiến trình đợi một số tài nguyên trong khi giữ một tài nguyên khác cùng một lúc.

3. No preemption

Process đã từng được lên lịch sẽ được thực hiện cho đến khi hoàn thành. Không có Process nào khác có thể được lên lịch bởi người lập lịch trong thời gian đó.

4. Circular Wait

Tất cả các Process phải chờ tài nguyên theo cách tuần hoàn để Process cuối cùng đang đợi tài nguyên đang được Process đầu tiên nắm giữ.

Các chiến lược để xử lý Deadlock

Deadlock Ignorance

Deadlock không hiểu biết là cách tiếp cận được sử dụng rộng rãi nhất trong số tất cả các cơ chế. Điều này đang được sử dụng bởi nhiều hệ điều hành chủ yếu cho mục đích sử dụng của người dùng cuối. Trong cách tiếp cận này, Hệ điều hành giả định rằng Deadlock không bao giờ xảy ra. Nó chỉ đơn giản là bỏ qua những Deadlock. Cách tiếp cận này phù hợp nhất cho một hệ thống người dùng cuối duy nhất trong đó Người dùng chỉ sử dụng hệ thống để duyệt web và tất cả các nội dung thông thường khác.

Luôn có sự cân bằng giữa tính đúng đắn và hiệu suất. Các hệ điều hành như Windows và Linux chủ yếu tập trung vào hiệu suất. Tuy nhiên, hiệu suất của hệ thống sẽ giảm nếu nó sử dụng cơ chế xử lý deadlock mọi lúc.

Trong các loại hệ thống này, người dùng chỉ cần khởi động lại máy tính trong trường hợp Deadlock. Windows và Linux chủ yếu sử dụng cách tiếp cận này.

Xem thêm Ngăn chặn Deadlock trong hệ điều hành

Deadlock prevention

Deadlock chỉ xảy ra khi Loại trừ lẫn nhau, giữ và chờ, Không ưu tiên và chờ vòng tròn đồng thời. Nếu có thể vi phạm một trong bốn điều kiện bất kỳ lúc nào thì không bao giờ có thể xảy ra Deadlock trong hệ thống.

Ý tưởng đằng sau cách tiếp cận rất đơn giản là chúng ta phải không đạt một trong bốn điều kiện nhưng có thể có một lập luận lớn về việc triển khai vật lý của nó trong hệ thống.

Chúng ta sẽ thảo luận chi tiết về nó sau.

Deadlock avoidance

Trong trường hợp tránh Deadlock, hệ điều hành sẽ kiểm tra xem hệ thống đang ở trạng thái an toàn hay ở trạng thái không an toàn ở mỗi bước mà hệ điều hành thực hiện. Quá trình tiếp tục cho đến khi hệ thống ở trạng thái an toàn. Khi hệ thống chuyển sang trạng thái không an toàn, hệ điều hành phải lùi lại một bước.

Nói cách đơn giản, Hệ điều hành xem xét từng phân bổ để việc phân bổ không gây ra Deadlock trong hệ thống.

Chúng ta sẽ thảo luận chi tiết về cách tránh Deadlock ở phần sau.

Deadlock detection và recovery

Cách tiếp cận này cho phép các quy trình rơi vào tình trạng Deadlock và sau đó kiểm tra định kỳ xem có xảy ra Deadlock trong hệ thống hay không. Nếu nó xảy ra thì nó sẽ áp dụng một số phương pháp khôi phục hệ thống để thoát khỏi Deadlock.

Chúng ta sẽ thảo luận về việc phát hiện và khôi phục deadlock sau chi tiết hơn vì nó là một vấn đề thảo luận.

Xem thêm Phát hiện và phục hồi Deadlock trong hệ điều hành

Phát Hiện và Phục Hồi Deadlock Trong Hệ Điều Hành

Trong lĩnh vực quản lý hệ thống máy tính, việc phát hiện và giải quyết deadlock là một vấn đề quan trọng. Một số hệ điều hành không áp dụng các biện pháp phòng ngừa deadlock mà thay vào đó, chúng chấp nhận khả năng xảy ra deadlock. Khi đó, việc phát hiện và giải quyết deadlock trở thành ưu tiên.

Phát Hiện Deadlock

Hệ điều hành tiến hành kiểm tra định kỳ để xác định sự tồn tại của deadlock. Sử dụng các đồ thị phân bổ tài nguyên, hệ thống có thể phát hiện các chu trình – một dấu hiệu chắc chắn của deadlock. Trong trường hợp của các tài nguyên đơn lẻ không ổn định, sự hình thành chu trình trong đồ thị chắc chắn cho thấy có deadlock. Tuy nhiên, với nhiều loại tài nguyên, việc phát hiện chu trình không đủ, và cần phải áp dụng các thuật toán an toàn để chuyển đổi đồ thị phân bổ thành ma trận phân bổ và yêu cầu.

Phục Hồi Từ Deadlock

Khi deadlock được phát hiện, hệ điều hành có thể áp dụng các biện pháp để phục hồi, bao gồm giải phóng tài nguyên hoặc ngưng tiến trình.

1. Giải Phóng Tài Nguyên: Một phương pháp là giải phóng một số tài nguyên từ tiến trình hiện tại và gán chúng cho tiến trình khác, với hy vọng rằng việc này sẽ giúp tiến trình hoàn thành nhanh hơn và giải phóng tài nguyên. Tuy nhiên, việc lựa chọn tài nguyên nào để giải phóng có thể khó khăn.
2. Khôi Phục Về Trạng Thái An Toàn: Một cách khác là đưa hệ thống trở về trạng thái an toàn trước khi deadlock xảy ra. Điều này đòi hỏi hệ điều hành phải theo dõi và kiểm tra tất cả các trạng thái của hệ thống.
3. Xử Lý Tiến Trình:

• Giết Tiến Trình: Hệ điều hành có thể chọn giết một tiến trình để giải phóng tài nguyên. Quyết định tiến trình nào sẽ bị giết thường dựa trên lượng công việc đã thực hiện.
• Giết Tất Cả Tiến Trình: Trong trường hợp cực kỳ nghiêm trọng, hệ thống có thể chọn giết tất cả các tiến trình. Tuy nhiên, điều này gây ra sự không hiệu quả, vì tất cả các tiến trình sẽ phải bắt đầu lại từ đầu.

Sử Dụng Resource Allocation Graph (RAG) Để Phát Hiện Deadlock

Hệ điều hành có thể sử dụng RAG để phát hiện deadlock. Nếu một chu trình được phát hiện trong đồ thị phân bổ tài nguyên với các phiên bản đơn lẻ của tài nguyên, thì có thể xác định hệ thống đang bị deadlock. Trong trường hợp tài nguyên đa phiên bản, việc phát hiện chu trình không đủ để khẳng định có deadlock.

Ma Trận Phân Bổ và Yêu Cầu

Hệ thống có thể sử dụng ma trận phân bổ và yêu cầu để xác định các tài nguyên hiện tại và yêu cầu của mỗi tiến trình. Ma trận này giúp xác định tài nguyên cần thiết để mỗi tiến trình hoàn thành, từ đó xác định liệu hệ thống có thể đáp ứng nhu cầu của ít nhất một tiến trình hay không.

Tiến trình	R1	R2	R3
P1	0	0	1
P2	1	0	0
P3	0	1	0

Tóm lại, việc phát hiện và phục hồi từ deadlock là một nhiệm vụ quan trọng của hệ điều hành, đòi hỏi phải theo dõi và phân tích liên tục tài nguyên và trạng thái của các tiến trình. Đây là một phần không thể thiếu trong quản lý hệ thống hiệu quả và ổn định.

Deadlock ảnh hưởng như thế nào đến hiệu suất của hệ thống?

Deadlock có thể ảnh hưởng nghiêm trọng đến hiệu suất của hệ thống. Khi deadlock xảy ra, các tiến trình bị mắc kẹt và không thể hoàn thành công việc của mình, dẫn đến sự lãng phí tài nguyên và giảm hiệu suất của hệ thống. Các tài nguyên bị mắc kẹt trong deadlock không thể được sử dụng bởi các tiến trình khác, dẫn đến sự đói tài nguyên và giảm khả năng thực hiện công việc khác.

Ngoài ra, quá trình giải quyết deadlock cũng ảnh hưởng đến hiệu suất của hệ thống. Việc giải quyết deadlock thường đòi hỏi thời gian và tài nguyên để tìm ra các giải pháp phù hợp để giải quyết vấn đề. Trong khi quá trình giải quyết deadlock đang diễn ra, các tiến trình khác có thể phải chờ đợi tài nguyên và làm giảm hiệu suất của hệ thống.

Xem thêm Sử dụng process trong Node.js

Những câu hỏi phổ biến về deadlock trong hệ điều hành

1. Deadlock là gì?

• Deadlock là tình trạng mà hai hoặc nhiều tiến trình hoặc luồng đang chờ đợi tài nguyên mà các tiến trình khác đang sử dụng, trong khi các tiến trình đang giữ các tài nguyên mà các tiến trình khác cần. Kết quả là các tiến trình sẽ bị treo và không thể tiếp tục thực hiện.

2. Deadlock có thể xảy ra khi nào?

• Deadlock có thể xảy ra khi các tiến trình hoặc luồng cùng cạnh tranh sử dụng các tài nguyên hệ thống, và không có cơ chế quản lý tài nguyên đảm bảo rằng các tài nguyên sẽ được sử dụng đúng cách.

3. Các yếu tố gây ra deadlock là gì?

• Các yếu tố gây ra deadlock gồm có: đối tượng tài nguyên bị chiếm giữ, yêu cầu các tài nguyên cùng mức ưu tiên, tiến trình không giải phóng tài nguyên khi đã sử dụng xong, và vòng lặp phụ thuộc tài nguyên.

4. Các phương pháp phát hiện deadlock là gì?

• Các phương pháp phát hiện deadlock gồm có: phát hiện vòng lặp, phát hiện trạng thái an toàn, phát hiện trạng thái không an toàn và phát hiện thông qua giám sát.

5. Các phương pháp khắc phục deadlock là gì?

• Các phương pháp khắc phục deadlock gồm có: giải phóng tài nguyên, khóa đột xuất (preemption), giải quyết bằng giải thuật Banker, và giải quyết bằng giải thuật Wait-Die và giải thuật Wound-Wait.

6. Deadlock có thể ảnh hưởng đến hiệu suất hệ thống như thế nào?

• Deadlock có thể làm giảm hiệu suất của hệ thống vì các tiến trình bị treo và không thể thực hiện, làm cho các tài nguyên bị chiếm giữ và không thể sử dụng được.

7. Làm thế nào để tránh deadlock?

• Để tránh deadlock, có thể sử dụng các kỹ thuật như giải phóng tài nguyên đúng cách, tránh sử dụng các tài nguyên cùng mức ưu tiên, sử dụng các giải thuật quản lý tài nguyên, và sử dụng các giải thuật phân bổ tài nguyên có thể tránh deadlock.

8. Các giải thuật phân bổ tài nguyên để tránh deadlock là gì?

• Giải thuật Banker: xác định trạng thái an toàn của hệ thống trước khi cấp phát tài nguyên cho các tiến trình, tránh các trạng thái không an toàn và đảm bảo không có deadlock xảy ra.
• Giải thuật chia sẻ tài nguyên: cho phép các tiến trình sử dụng chung các tài nguyên mà không gây ra deadlock, ví dụ như sử dụng mutex hay semaphore.
• Giải thuật yêu cầu không trùng khớp: chỉ cho phép các tiến trình yêu cầu tài nguyên mà không trùng khớp với các yêu cầu của các tiến trình khác, tránh các vòng lặp phụ thuộc tài nguyên.

9. Khi nào cần sử dụng khóa đột xuất (preemption) để khắc phục deadlock?

• Khóa đột xuất được sử dụng khi không thể giải phóng tài nguyên, và cần phải lấy tài nguyên của một tiến trình để phục vụ tiến trình khác đang chờ đợi. Tuy nhiên, cần cân nhắc thật kỹ vì khóa đột xuất có thể gây ra tình trạng đói tài nguyên và làm giảm hiệu suất của hệ thống.

10. Làm thế nào để phòng ngừa deadlock?

• Để phòng ngừa deadlock, cần phải thiết kế các giải thuật quản lý tài nguyên và phân bổ tài nguyên sao cho tránh được các trường hợp xảy ra deadlock. Các tiến trình phải được giải phóng tài nguyên khi đã sử dụng xong, và hệ thống cần phải đảm bảo các tiến trình không thể giữ tài nguyên quá lâu. Ngoài ra, cần thiết lập các quy tắc phân bổ tài nguyên sao cho tránh việc các tiến trình cùng cạnh tranh sử dụng các tài nguyên cùng mức ưu tiên.

Hướng dẫn khác:

1. Ngăn chặn Deadlock trong hệ điều hành
2. Tìm hiểu về Process trong hệ điều hành
3. Process Synchronization trong hệ điều hành 
4. Giới thiệu thuật toán semaphore trong Hệ điều hành
5. Cơ Chế Interested Variable Trong Hệ Điều Hành
6. Giải pháp Paterson trong Hệ điều hành