Được gọi là giải thuật Banker là vì thuật toán có thể được sử dụng trong các hệ thống ngân hàng để đảm bảo rằng ngân hàng sẽ không chi tiền đến mức mà nó không thể đáp ứng được nhu cầu của tất cả các khách hàng.
Xem thêm:
Bài tập Round Robin có lời giải | Nguyên lý hệ điều hành
50 câu trắc nghiệm nguyên lý hệ điều hành có đáp án | Ehou
1. Thuật toán Banker là gì ?
Thuật toán Banker là một giải thuật để quản lý bộ nhớ trong một hệ thống điều hành để đảm bảo rằng không có quá nhiều bộ nhớ được yêu cầu bởi các tiến trình cùng lúc mà không có đủ bộ nhớ để cung cấp cho chúng. Giải thuật Banker được sử dụng để tránh tình trạng “deadlock” trong hệ thống điều hành, trong đó các tiến trình không thể tiếp tục vì không có đủ tài nguyên để hoàn thành công việc của chúng.
2. Cách giải thuật Banker hoạt động
Giải thuật bắt đầu bằng việc thống kê xem mỗi tiến trình sẽ còn cần thêm bao nhiêu đơn vị tài nguyên và hiện tại vốn hệ thống còn bao nhiêu. Mọi tiến trình đều chưa biết là có kết thúc được hay không.
Bước tiếp theo là kiểm tra và đánh giá. Với mỗi tiến trình chưa biết có kết thúc được hay không, nếu lượng tài nguyên cần thiết cho nó để kết thúc không vượt quá vốn tài nguyên còn lại của hệ thống thì tiến trình này chắc chắn kết thúc được. Khi kết thúc các tài nguyên mà tiến trình đã nhận sẽ được trả về cho hệ thống.
3. Ưu và nhược điểm của giải thuật
- Giải thuật đơn giản, dễ cài đặt,
- Cần phải có dữ liệu vào maxi cho mỗi tiến trình. Dữ liệu này do người dùng cung cấp và thông thường là đáng tin cậy (vì lợi ích của chính mình người dùng không khai báo tăng hay giảm số lượng thiết bị yêu cầu),
- Việc đánh giá kiểm tra bế tắc quá chặt: luôn luôn giả thiết là tiến trình sẽ cần đúng số lượng tài nguyên tối đa,
- Với mỗi loại tài nguyên cần một thủ tục kiểm tra riêng, mỗi lần phân phối tài nguyên lại phải kiểm tra đánh giá toàn bộ các tiến trình.
Dưới đây là một ví dụ về cách sử dụng giải thuật Banker để giải quyết một bài toán về quản lý tài nguyên
4. Bài tập giải thuật nhà băng có lời giải
Câu 1: Có 4 tiến trình P1, P2, P3, P4 và 4 tài nguyên R1, R2, R3, R4 với khả năng phục vụ là
10,9,9,5. Số lượng đơn vị tài nguyên cần thiết và đã cung cấp cho các tiến trình được cho theo các bảng sau
Cần thiết |
Đã cung cấp |
Áp dụng thuật toán nhà quản lý nhà băng, kiểm tra hệ thống an toàn hay bế tắc ?
Giải
| R1 | R2 | R3 | R4 | |
| P1 | 4 | 1 | 4 | 2 |
| P2 | 2 | 2 | 4 | 2 |
| P3 | 3 | 4 | 4 | 2 |
| P4 | 2 | 2 | 3 | 3 |
Còn cần (Cần thiết – đã cung cấp)
Số tài nguyên còn lại mỗi loại (R1,R2,R3,R4) = (2,3,4,3)
Vòng 1:
+ Chọn P2(2,2,4,2) do thoả mãn số tài nguyên còn lại (2,3,4,3)
Thực hiện P2 rồi giải phóng các tài nguyên => Số tài nguyên còn lại (3,5,5,4)
+ Chọn P3(3,4,4,2) do thoả mãn số tài nguyên còn lại (3,5,5,4)
Thực hiện P3 rồi giải phóng các tài nguyên => Số tài nguyên còn lại (7,5,8,5)
+ Chọn P4(2,2,3,3) do thoả mãn số tài nguyên còn lại (7,5,8,5)
Thực hiện P4 rồi giải phóng các tài nguyên => Số tài nguyên còn lại (8,8,9,5)
+Vòng 2:
+Chọn P1(4,1,4,2) do thoả mãn tài nguyên còn lại (8,8,9,5)
Thực hiện P1 rồi giải phóng các tài nguyên => Số tài nguyên còn lại (10,9,9,5)
Vậy hệ thống an toàn với giải pháp là (P2,P3,P4,P1)
Giải thuật Banker là một phương pháp quan trọng trong quản lý tài nguyên và ngăn chặn tình trạng deadlock trong các hệ điều hành. Bằng cách đảm bảo hệ thống luôn ở trạng thái an toàn trước khi cấp phát tài nguyên, giải thuật này giúp tránh việc nhiều tiến trình rơi vào trạng thái chờ vĩnh viễn. Cảm ơn bạn đã tham khảo nguyên lý hệ điều hành trên ttnguyen.net.
Bài viết liên quan:
