Bài giảng Hệ điều hành: Bế tắc - ThS. Nguyễn Thị Hải Bình

Bài giảng "Hệ điều hành: Bế tắc" cung cấp cho người học các kiến thức: Mô hình hệ thống, điều kiện cần để có bế tắc, đồ thị phân phối tài nguyên, giải quyết bế tắc, tránh bế tắc, thuật toán đồ thị cấp phát tài nguyên, phát hiện bế tắc,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Hệ điều hành: Bế tắc - ThS. Nguyễn Thị Hải Bình BẾ TẮC (DEADLOCK) ThS. Nguyễn Thị Hải Bình Khoa CNTT, ĐH Giao thông vận tải Email: calmseahn@gmail.com Website: calmseahn.weebly.com BRIDGE CROSSING EXAMPLE 2 DEADLOCK EXAMPLE Process 1 Process 2 1. Process 1 requests the printer, gets it 2. Process 2 requests the tape unit, gets it 3. Process 1 requests the tape unit, waits 4. Process 2 requests the printer, waits 3 Bế tắc là tình huống xuất hiện khi hai tiến trình phải chờ đợi nhau giải phóng tài nguyên hoặc nhiều tiến trình chờ sử dụng các tài nguyên theo một “vòng tròn” (circular chain). 4 MÔ HÌNH HỆ THỐNG • Xem hệ thống như một tập hợp có giới hạn các tài nguyên • Kiểu tài nguyên (type) • Các tài nguyên được chia thành các kiểu, ví dụ: memory, printers, CPUs, open files, tape drives, CD-ROMS, … • Hệ thống có 2 CPU thì kiểu tài nguyên CPU có 2 đối tượng • Các đối tượng (instances) trong cùng một kiểu tài nguyên có vai trò như nhau • Tiến trình sử dụng tài nguyên theo trình tự • Yêu cầu (Request) • Sử dụng (Use) • Giải phóng (Release) • Một tập hợp các tiến trình ở tình trạng bế tắc khi mỗi tiến trình đều chờ tài nguyên từ một tiến trình khác trong tập hợp 5 ĐIỀU KIỆN CẦN ĐỂ CÓ BẾ TẮC • Bế tắc xuất hiện nếu 4 điều kiện sau đồng thời xuất hiện • Độc quyền truy xuất (Mutal exclusion): ít nhất một tài nguyên bị nắm giữ thuộc kiểu không thể dùng chung • Giữ và chờ (Hold and wait): tồn tại tiến trình đang nắm giữ tài nguyên, đồng thời lại chờ tài nguyên bị giữ bởi tiến trình khác • Không chiếm đoạt (No preemption): hệ thống không thể chiếm tài nguyên của tiến trình • Vòng đợi (Circular wait): Tồn tại tập hợp các tiến trình {P0, P1, …, Pn}, mà P0 chờ P1, P1 chờ P2, …, Pn chờ P0 6 ĐỒ THỊ PHÂN PHỐI TÀI NGUYÊN • Tập đỉnh V • P = {P1, P2, …, Pn} - ứng với các tiến trình • R = {R1, R2, …, Rn} - ứng với các kiểu tài nguyên của hệ thống • Tập cung E • Cung yêu cầu Pi  Rj • Cung phân phối Pi  Rj 7 ĐỒ THỊ PHÂN PHỐI TÀI NGUYÊN • Ví dụ • Tập đỉnh: V = P  R • P = {P1, P2, P3} • R = {R1, R2, R3, R4} • Tập cung • E = {P1  R1, P2  R3, R1  P2, R2  P2, R2  P1, R3  P3} 8 PHÁT HIỆN BẾ TẮC BẰNG ĐTPPTN • Nếu đồ thị không có chu trình, thì không có tiến trình nào bị bế tắc • Nếu đồ thì có chu trình • Nếu mỗi kiểu tài nguyên trong chu trình có đúng một đối tượng, thì các tiến trình trong chu trình rơi vào trạng thái bế tắc • Nếu mỗi kiểu tài nguyên trong chu trình có nhiều hơn một đối tượng, thì bế tắc có thể xảy ra 9 Thêm vào cung P3  R3 10 11 GIẢI QUYẾT BẾ TẮC • Ba giải pháp • Đảm bảo hệ thống không rơi vào trạng thái bế tắc • Sử dụng một trong hai giao thức sau: ngăn chặn bế tắc (deadlock prevention) hoặc tránh bế tắc (deadlock avoidance) • Cho phép hệ thống rơi vào trạng thái bế tắc, sau đó phát hiện (deadlock detection) và khắc phục (recovery) • Bỏ qua mọi vấn đề, xem như bế tắc không bao giờ xuất hiện 12 NGĂN CHẶN BẾ TẮC • Ý tưởng: đảm bảo ít nhất một trong bốn điều kiện cần của bế tắc không xảy ra • Độc quyền truy xuất (Mutal exclusion): ít nhất một tài nguyên bị nắm giữ thuộc kiểu không thể dùng chung • Giữ và chờ (Hold and wait): tồn tại tiến trình đang nắm giữ tài nguyên, đồng thời lại chờ tài nguyên bị giữ bởi tiến trình khác • Không chiếm đoạt (No preemption): hệ thống không thể chiếm tài nguyên của tiến trình • Vòng đợi (Circular wait): Tồn tại tập hợp các tiến trình {P0, P1, …, Pn}, mà P0 chờ P1, P1 chờ P2, …, Pn chờ P0 13 NGĂN CHẶN BẾ TẮC • Điều kiện “độc quyền truy xuất” • Liên quan tới bản chất của tài nguyên • Điều kiện này luôn đúng với các tài nguyên không thể chia sẻ (ví dụ máy in) • Không thể loại bỏ điều kiện này • Điều kiện “giữ và chờ” • Đảm bảo tiến trình không nắm giữ bất kỳ tài nguyên nào khi yêu cầu tài nguyên khác • Giải pháp • Tiến trình yêu cầu tất cả các tài nguyên trước khi thực thi • Trước khi yêu cầu thêm tài nguyên, tiến trình phải giải phóng tất cả tài nguyên đang giữ • “Nạn đói” 14 NGĂN CHẶN BẾ TẮC • Điều kiện “không chiếm đoạt” • Giải pháp 1: Nếu tiến trình phải chờ một tài nguyên, thì hệ thống sẽ thu hồi tất cả tài nguyên mà tiến trình đó đang giữ • Giải pháp 2: • Nếu tiến trình P yêu cầu một tài nguyên, và tài nguyên đó đang bị giữ bởi tiến trình Q. • Nếu Q đang bị phong toả (i.e. đang chờ tài nguyên khác) thì tài nguyên của Q bị chiếm bởi P • Nếu ngược lại thì P phải chờ 15 NGĂN CHẶN BẾ TẮC • Điều kiện “Vòng đợi” • Đánh số tất cả các tài nguyên • Các tiến trình yêu cầu cấp phát tài nguyên theo thứ tự tăng dần • Ưu điểm • Dễ cài đặt • Nhược điểm • Giảm hiệu suất sử dụng của tài nguyên • Giảm thông lượng của hệ thống 16 TRÁNH BẾ TẮC • Ý tưởng • N ...