Bế tắc trong OperaHệ thống ting: Là gì, Chờ tròn (Ví dụ)

Bế tắc là gì?

bế tắc là tình huống xảy ra trong hệ điều hành khi bất kỳ tiến trình nào đi vào trạng thái chờ vì một tiến trình chờ khác đang giữ tài nguyên được yêu cầu. Bế tắc là một vấn đề phổ biến trong xử lý đa luồng, trong đó một số tiến trình chia sẻ một loại tài nguyên loại trừ lẫn nhau cụ thể được gọi là khóa mềm hoặc phần mềm.

Ví dụ về bế tắc

  • Một ví dụ thực tế là giao thông chỉ đi theo một hướng.
  • Ở đây, một cây cầu được coi là một nguồn tài nguyên.
  • Vì vậy, khi Deadlock xảy ra, có thể dễ dàng giải quyết nếu một xe lùi lại (Ngăn chặn tài nguyên và khôi phục).
  • Có thể phải có nhiều xe phải lùi lại nếu xảy ra tình trạng kẹt xe.
  • Vì vậy, nạn đói là có thể.
Ví dụ về bế tắc
Ví dụ về bế tắc

Thông tư chờ đợi là gì?

Một quy trình đang chờ tài nguyên do quy trình thứ hai nắm giữ, quy trình này cũng đang chờ tài nguyên do quy trình thứ ba nắm giữ, v.v. Điều này sẽ tiếp tục cho đến khi quy trình cuối cùng đang chờ tài nguyên do quy trình đầu tiên nắm giữ. Điều này tạo ra một chuỗi tròn.

Ví dụ: Quy trình A được phân bổ Tài nguyên B vì nó đang yêu cầu Tài nguyên A. Theo cách tương tự, Quy trình B được phân bổ Tài nguyên A và nó đang yêu cầu Tài nguyên B. Điều này tạo ra một vòng chờ vòng tròn.

Ví dụ về chờ vòng tròn

Ví dụ, một máy tính có ba ổ USB và ba tiến trình. Mỗi tiến trình trong ba tiến trình có thể giữ một trong các ổ USB. Vì vậy, khi mỗi tiến trình yêu cầu một ổ đĩa khác, ba tiến trình sẽ có tình huống bế tắc vì mỗi tiến trình sẽ chờ ổ USB được giải phóng, hiện đang được sử dụng. Điều này sẽ dẫn đến một chuỗi tuần hoàn.

Ví dụ về chờ vòng tròn

Ví dụ chờ vòng tròn

Phát hiện bế tắc trong hệ điều hành

Một sự kiện bế tắc có thể được phát hiện bởi trình lập lịch tài nguyên. Trình lập lịch tài nguyên giúp hệ điều hành theo dõi tất cả các tài nguyên được phân bổ cho các quy trình khác nhau. Vì vậy, khi phát hiện ra bế tắc, có thể giải quyết bằng các phương pháp sau:

Phòng ngừa bế tắc trong hệ điều hành

Điều quan trọng là phải ngăn chặn tình trạng bế tắc trước khi nó có thể xảy ra. Hệ thống kiểm tra mọi giao dịch trước khi thực hiện để đảm bảo rằng nó không dẫn đến tình trạng bế tắc. Ngay cả một thay đổi nhỏ xảy ra cũng khiến một hoạt động có thể dẫn đến bế tắc trong tương lai cũng không bao giờ cho phép tiến trình thực hiện.

Đó là một tập hợp các phương pháp để đảm bảo rằng ít nhất một trong các điều kiện không thể đáp ứng được.

Không có hành động phủ đầu

Không có quyền ưu tiên - Một tài nguyên chỉ có thể được giải phóng một cách tự nguyện bởi quá trình đang giữ nó sau khi quá trình đó hoàn thành nhiệm vụ của nó

  • Nếu một tiến trình đang giữ một số tài nguyên yêu cầu một tài nguyên khác không thể được cấp phát ngay cho nó thì trong trường hợp đó, tất cả các tài nguyên sẽ được giải phóng.
  • Tài nguyên được ưu tiên yêu cầu danh sách tài nguyên cho một quy trình đang chờ.
  • Quá trình sẽ chỉ được khởi động lại nếu nó có thể lấy lại tài nguyên cũ và tài nguyên mới mà nó đang yêu cầu.
  • Nếu quy trình đang yêu cầu một số tài nguyên khác, khi nó có sẵn thì tài nguyên đó sẽ được trao cho quy trình yêu cầu.
  • Nếu nó được giữ bởi một quy trình khác đang chờ tài nguyên khác, chúng tôi sẽ giải phóng nó và đưa nó cho quy trình yêu cầu.

Loại trừ lẫn nhau

Loại trừ lẫn nhau là một dạng đầy đủ của Mutex. Nó là một loại semaphore nhị phân đặc biệt được sử dụng để kiểm soát quyền truy cập vào tài nguyên được chia sẻ. Nó bao gồm một cơ chế kế thừa ưu tiên để tránh các vấn đề đảo ngược mức ưu tiên mở rộng. Nó cho phép các nhiệm vụ có mức độ ưu tiên cao hơn hiện tại được giữ ở trạng thái bị chặn trong thời gian ngắn nhất có thể.

Các tài nguyên được chia sẻ như tệp chỉ đọc không bao giờ dẫn đến bế tắc, nhưng các tài nguyên như máy in và ổ băng cần được một quy trình duy nhất truy cập độc quyền.

Giữ và chờ

Trong điều kiện này, các tiến trình phải dừng giữ một hoặc nhiều tài nguyên trong khi đồng thời chờ một hoặc nhiều tài nguyên khác.

Chờ tròn

Nó áp đặt tổng thứ tự của tất cả các loại tài nguyên. Chờ tuần hoàn cũng yêu cầu mọi quy trình đều yêu cầu tài nguyên theo thứ tự liệt kê tăng dần.

Tránh bế tắc Algorithms

Tốt hơn là tránh bế tắc thay vì hành động sau khi bế tắc đã xảy ra. Cần có thêm thông tin, như cách sử dụng tài nguyên. Tránh bế tắc là mô hình đơn giản và hữu ích nhất mà mỗi quy trình khai báo số lượng tài nguyên tối đa của từng loại mà nó có thể cần.

Tránh Algorithms

Thuật toán tránh bế tắc giúp bạn đánh giá trạng thái phân bổ tài nguyên một cách động để không bao giờ xảy ra tình trạng chờ đợi tuần hoàn.

Một phiên bản duy nhất của một loại tài nguyên.

  • Sử dụng biểu đồ phân bổ tài nguyên
  • Chu kỳ là cần thiết và đủ để xảy ra tình trạng bế tắc

Nhiều phiên bản của một loại tài nguyên.

  • Chu kỳ là cần thiết nhưng không bao giờ đủ để dẫn đến bế tắc.
  • Sử dụng thuật toán ngân hàng

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

Sau đây là một số điểm khác biệt quan trọng giữa Deadlock và starvation:

bế tắc Nạn đói
Tình huống bế tắc xảy ra khi một trong các tiến trình bị chặn. Đói là tình huống trong đó tất cả các quy trình có mức độ ưu tiên thấp bị chặn và các quy trình có mức độ ưu tiên cao sẽ thực thi.
Bế tắc là một quá trình vô hạn. Đói là một sự chờ đợi lâu dài nhưng không phải là một quá trình vô tận.
Mỗi bế tắc luôn đi kèm với nạn đói. Không phải mọi nạn đói đều dẫn đến bế tắc.
Bế tắc xảy ra sau đó là loại trừ lẫn nhau, giữ và chờ. Ở đây, việc chiếm quyền trước và chờ tuần hoàn không xảy ra đồng thời. 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.

Ưu điểm của Deadlock

Sau đây là ưu/lợi ích của việc sử dụng phương pháp Deadlock

  • Tình huống này hoạt động tốt đối với các quy trình thực hiện một loạt hoạt động
  • Không cần phải chiếm quyền trước đối với Deadlock.
  • Phương pháp thuận tiện khi áp dụng cho các tài nguyên có trạng thái có thể được lưu và khôi phục dễ dàng
  • Có thể thực thi thông qua kiểm tra thời gian biên dịch
  • Không cần tính toán trong thời gian chạy vì vấn đề đã được giải quyết trong thiết kế hệ thống

Nhược điểm của Deadlock

Sau đây là những nhược điểm/hạn chế của việc sử dụng phương pháp bế tắc

  • Trì hoãn quá trình bắt đầu
  • Các quy trình phải biết nhu cầu tài nguyên trong tương lai
  • Làm trước thường xuyên hơn mức cần thiết
  • Không cho phép yêu cầu tài nguyên gia tăng
  • Tổn thất ưu tiên vốn có.

Tổng kết

  • Định nghĩa bế tắc: Đó là tình huống xảy ra trong OS khi bất kỳ quy trình nào chuyển sang trạng thái chờ vì một quy trình chờ khác đang giữ tài nguyên được yêu cầu
  • Chờ đợi tuần hoàn xảy ra khi một tiến trình đang chờ tài nguyên, được giữ bởi tiến trình thứ hai, cũng đang chờ tài nguyên được giữ bởi tiến trình thứ ba, v.v.
  • Bộ lập lịch tài nguyên có thể phát hiện ra tình trạng bế tắc.
  • Điều quan trọng là phải ngăn chặn tình trạng bế tắc trước khi nó xảy ra.
  • Một tài nguyên chỉ có thể được giải phóng một cách tự nguyện bởi quá trình đang giữ nó sau khi quá trình đó hoàn thành nhiệm vụ của nó.
  • Loại trừ lẫn nhau là một dạng đầy đủ của Mutex. Đây là một loại nhị phân đặc biệt đèn hiệu được sử dụng để kiểm soát quyền truy cập vào tài nguyên được chia sẻ.
  • Giữ và chờ là tình trạng trong đó các tiến trình phải dừng giữ một hoặc nhiều tài nguyên trong khi đồng thời chờ một hoặc nhiều tài nguyên khác.
  • Tránh bế tắc là mô hình đơn giản và hữu ích nhất trong đó mỗi tiến trình khai báo số lượng tài nguyên tối đa của từng loại mà nó có thể cần.
  • Thuật toán tránh bế tắc giúp bạn đánh giá trạng thái phân bổ tài nguyên một cách động để không bao giờ xảy ra tình trạng chờ đợi tuần hoàn.
  • Bế tắc là một quá trình vô hạn, trong khi chết đói là quá trình chờ đợi lâu nhưng không phải là quá trình vô hạn.