Mục tiêu chính của hệ điều hành là cung cấp giao tiếp thích hợp giữa các tài nguyên phần cứng và phần mềm, đồng thời cung cấp các dịch vụ chung cho các chương trình. Khi một tiến trình của hệ điều hành muốn truy cập bất kỳ tài nguyên nào, trước tiên nó sẽ gửi một yêu cầu đến tài nguyên cụ thể mà nó muốn truy cập, sau đó nó sử dụng tài nguyên đó và cuối cùng giải phóng tài nguyên sau khi sử dụng. Vì giả sử nhiều quy trình đang cố gắng truy cập một tài nguyên cùng một lúc, thì việc cung cấp một tài nguyên cho tất cả các quy trình tại một thời điểm sẽ trở nên khó khăn trong một tình huống như vậy, khái niệm có tên là deadlock phát sinh. Do đó bài viết này mô tả cách deadlock xảy ra và cách khắc phục tình trạng deadlock này.
Bế tắc trong Hệ điều hành là gì?
Định nghĩa: Dead-Lock là một tình huống trong đó hai hoặc nhiều bộ xử lý đang đợi một sự kiện nào đó xảy ra, nhưng những sự kiện đó không xảy ra là một tình trạng bế tắc và các bộ xử lý được cho là đang ở trạng thái bế tắc. Ví dụ: chúng ta hãy giả sử một tình huống thời gian thực, trong đó có hai chiếc ô tô A & B, do hai người lái xe riêng lẻ điều khiển trên đường một chiều. Bây giờ tình huống phát sinh khi người lái xe ô tô A nói rằng anh ta đi về hướng bắc là một hướng chính xác, trong khi người lái xe ô tô B nói rằng anh ta đi về hướng nam là đúng. Nhưng cả hai không lùi lại để cho xe khác tiến lên, điều kiện này được gọi là điều kiện bế tắc.
ví dụ xe hơi
Để hiểu rõ hơn, chúng ta hãy xem xét một ví dụ khác trong đó có hai tài nguyên R1, R2 và hai quá trình P1 và P2, trong đó R1 được gán cho P1 và R2 được gán cho P2. Bây giờ nếu P1 muốn truy cập R2, như chúng ta đã biết R2 do P2 nắm giữ và bây giờ P2 muốn truy cập R1, P1 chỉ thực thi khi nó được truy cập vào R2, còn P2 chỉ thực thi khi nó được truy cập vào R1 trong tình huống này là một trạng thái bế tắc.
ví dụ bộ xử lý
Điều kiện khóa chết
Sau đây là bốn điều kiện deadlock quan trọng xảy ra nếu tất cả các điều kiện xảy ra đồng thời thì sẽ có nhiều khả năng xảy ra deadlock.
Loại trừ lẫn nhau
Nó có nghĩa là bất kỳ tài nguyên nào chúng ta đang sử dụng nó phải được sử dụng theo cách loại trừ lẫn nhau. Trường hợp chỉ có một quy trình sử dụng một tài nguyên tại một thời điểm duy nhất. Ví dụ: quá trình in đang diễn ra và đột nhiên một quá trình khác cố gắng làm gián đoạn quá trình in. Vì vậy, ở đây trong tình huống loại trừ lẫn nhau, chỉ sau khi tác vụ in hoàn thành thì chỉ tác vụ tiếp theo được xử lý. Loại trừ lẫn nhau có thể được loại bỏ bằng cách chia sẻ tài nguyên đồng thời, điều này không thể thực hiện được trên thực tế.
loại trừ lẫn nhau
Không có quyền ưu tiên
Dựa theo phủ đầu dựa trên thuật toán, nếu có một nhiệm vụ ưu tiên đang cố gắng làm gián đoạn tác vụ hiện tại. Thuật toán ưu tiên nó giữ tác vụ hiện tại và trước tiên thực hiện tác vụ ưu tiên và quay trở lại tác vụ đầu tiên của nó. Một tình huống được giải thích theo ví dụ trên trong đó một tiến trình giữ tài nguyên miễn là nó được thực thi, đó là P1 chỉ có thể giải phóng R1 sau khi thực thi, tương tự P2 giải phóng R2 chỉ sau khi thực thi. Nếu không có pre-emption, bế tắc có thể xảy ra.
no-preemption-example
Giữ và đợi
Một quy trình đang giữ một số tài nguyên và đang chờ thêm tài nguyên nhưng những tài nguyên đó được một quy trình khác thu được. Từ ví dụ trên, P1 đang giữ R1 và chờ R2, trong đó R2 được P2 thu nhận và P2 đang giữ R2 và chờ R1, trong đó R1 được P1 mua lại là tình trạng giữ và chờ có thể xảy ra bế tắc trong hệ thống.
ví dụ về giữ và đợi
Chờ vòng tròn
Một tập hợp các quy trình được cho là đang trong tình trạng bế tắc nếu một quy trình đang đợi tài nguyên được cấp phát cho quy trình khác và quy trình đó đang chờ tài nguyên, nó tương tự như ví dụ đã giải thích ở trên, nó ở dạng vòng lặp. Trong đó P1 đang đợi R2 và R2 được cấp phát cho P2 và P2 đang chờ R1 và R1 được cấp phát cho P1 là dạng chờ vòng tròn nếu điều kiện này thỏa mãn deadlock xảy ra.
vòng-đợi-ví dụ
Thuật toán phát hiện khóa chết
Các trường hợp chúng tôi phân bổ tài nguyên cho các quy trình và hệ điều hành kiểm tra lại xem có xảy ra bế tắc trong hệ thống hay không bằng cách sử dụng 2 thuật toán phát hiện bế tắc chính, chúng
- Trường hợp duy nhất
- Nhiều trường hợp của loại tài nguyên
Trường hợp duy nhất
Một trường hợp đơn lẻ là một tình huống trong đó một hệ thống đang có các trường hợp đơn lẻ của tất cả các tài nguyên. Nó còn được gọi là thuật toán chờ đồ thị hoặc đồ thị phân bổ tài nguyên. Biểu đồ phân bổ tài nguyên bao gồm một tập hợp các quy trình và tập hợp các tài nguyên được biểu diễn dưới dạng hai đỉnh khác nhau. Các tài nguyên trong biểu đồ phân bổ tài nguyên được sửa đổi và được biểu diễn dưới dạng biểu đồ chờ. Trong đó biểu đồ chờ đợi chỉ có các quy trình được biểu diễn dưới dạng các đỉnh như được hiển thị bên dưới, trong đó,
- Đồ thị phân bổ tài nguyên: Các quá trình P1, P2, P3 và các tài nguyên R1, R2, R3 được biểu diễn trong đồ thị phân bổ tài nguyên.
- Chờ đồ thị: Chỉ các quá trình P1, P2, P3 được đề cập trong quá trình chờ đồ thị.
- Nếu có một điều kiện chu trình, tức là nếu có một dòng liên tục của một quá trình theo một hướng, điều đó có nghĩa là điều kiện chu trình thoát ra và chờ đợi đồ thị ở trong điều kiện bế tắc.
Ví dụ 1: Ví dụ dưới đây cho thấy không có trạng thái bế tắc vì không có luồng liên tục được quan sát trong thời gian chờ đồ thị.
single-instance-example1
Ví dụ 2: Tình trạng deadlock đã xảy ra do có một dòng chu trình liên tục từ P1 đến P4.
single-instance-example2
Nếu deadlock xảy ra rất thường xuyên trong hệ thống thì thuật toán phát hiện được sử dụng thường xuyên. Nếu có nhiều sử dụng thuật toán phát hiện hơn thì sẽ có nhiều chi phí hơn và thời gian tính toán nhiều hơn. Do đó, để khắc phục điều này, chúng tôi gọi thuật toán sau, với một khoảng thời gian bằng nhau, đây là cách trọng số của đồ thị được sử dụng để phát hiện bế tắc.
Nhiều phiên bản của loại tài nguyên
Nhiều trường hợp của loại tài nguyên là một tình huống trong đó một hệ thống có nhiều trường hợp của tất cả các tài nguyên, nó còn được gọi là thuật toán Bankers. Theo thuật toán Bankers, ngay sau khi quy trình nhận được tất cả các tài nguyên cần thiết, thì nó sẽ giải phóng tài nguyên của nó.
Chúng ta hãy xem xét ví dụ sau, giả sử có 3 quá trình P0, P1, P2 và loại tài nguyên A, B, C trong đó A có thể là CPU , B có thể là máy in và C có thể là bàn phím. Các chữ số “0” trong cột thể hiện sự sẵn có của tài nguyên.
Trường hợp (i): Giả sử nếu chúng ta coi yêu cầu điều kiện là điều kiện “000” có trong P0 và P2, chúng ta nên kiểm tra yêu cầu nào được đáp ứng, các quá trình P0 giải phóng các quá trình sau khi được cấp phát, sau đó các quá trình P2 tiếp theo giải phóng sau khi được cấp phát. Như thế này, theo một trình tự, từng quy trình giải phóng P0, P2, P3, P1, P4 theo một trình tự. Cuối cùng, chúng tôi nhận được các tài nguyên có sẵn như P7, P2, P6. Trình tự khả dụng là điều kiện không có bế tắc.
ngân hàng-thuật toán-example1
Nhà (ii): Giả sử nếu P2 là 001 thay vì 000, bây giờ hãy áp dụng thuật toán của chủ ngân hàng để kiểm tra điều kiện deadlock, trong đó P0 duy nhất được thực thi trong số tất cả 5 quy trình. Do đó P1, P2, P3, P4 ở trạng thái deadlock ngoại trừ P0.
ngân hàng-example2
Các ứng dụng của Deadlock
Các ứng dụng của bế tắc có thể được giải thích bằng một ví dụ thời gian thực về kết quả kiểm tra trực tuyến, trong đó một số sinh viên cố gắng truy cập trang web của trường đại học của họ đúng thời gian phát hành. Người ta có thể quan sát thấy rằng đôi khi trang web không tải cùng một lúc cho nhiều người dùng, đây là một điều kiện bế tắc. Điều này có thể được khắc phục bằng cách sử dụng bất kỳ thuật toán nào.
Ưu điểm
Ưu điểm của deadlock là
- Không có pre-emption được quan sát để tránh bế tắc
- Không chậm trễ trong quá trình
Nhược điểm
Nhược điểm của bế tắc là
- Nguồn lực được sử dụng phải được biết trước
- Quá trình bị tắc nghẽn trong một thời gian dài
- Các khoản lỗ trước khi sử dụng được kế thừa.
Bài viết này tổng quan về cách xảy ra bế tắc khi có hai hoặc nhiều quy trình và ba điều kiện là nguyên nhân gây ra bế tắc và hai loại thuật toán cụ thể là thuật toán chia sẻ tài nguyên phát hiện có tồn tại tình trạng bế tắc và thuật toán của chủ ngân hàng là thuật toán tránh bế tắc. Đây là câu hỏi “Điều gì xảy ra nếu bế tắc bị bỏ qua?”.
