Giải thuật Banker: Định nghĩa và bài tập có lời giải

Đượ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.

1.Định nghĩa

Giải thuật 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. 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

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

Á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

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)