Các câu hỏi và lời giải chương 8

Các câu hỏi và lời giải chương 8

8.1. Phân tích khái niệm tài nguyên hệ thống.
Giải:
- Các tài nguyên hệ thống được chia thành nhiều Loại, mỗi loại có 1 hoặc nhiều Phiên bản (Instances). Các tài nguyên hệ thống này cấp phát cho các tiến trình theo yêu cầu.
- Tài nguyên cùng loại: Giả sử máy có 3 ổ băng từ và có 3 tiến trình đang chạy. Mỗi tiến trình đang giữ 1 ổ băng.
- Tài nguyên khác loại: Giả sử có 1 máy in, 1 ổ băng từ. Tiến trình P1 đang giữ ổ băng, P2 giữ máy in.

8.2. Trình bày thứ tự sử dụng tài nguyên của tiến trình.
Giải:
Thứ tự sử dụng tài nguyên của tiến trình:
1. Yêu cầu (Request): Nếu không được đáp ứng do bị tiến trình khác giữ => tiến trình phải chờ.
2. Sử dụng (Use): Sau khi được cấp phát, tiến trình thao tác với tài nguyên (thực hiện I/O, in ra giấy, ...).
3. Trả lại (Release): Trả tài nguyên cho HĐH quản lý.

8.3. Định nghĩa Deadlock.
Giải:
Deadlock: là tình huống kẹt tiến trình (process) với một tập các process bị blocked, mỗi process giữ tài nguyên và đang chờ tài nguyên mà process khác trong tập đang có.
Ví dụ 1
Giả sử hệ thống có 2 file trên đĩa.
P1 và P2 mỗi process đang mở một file và yêu cầu mở file kia.
Ví dụ 2
Semaphore A và B, khởi tạo bằng 1
P0 P1
wait (A); wait(B)
wait (B); wait(A)

8.4. Nêu 1 ví dụ từ đời thường minh hoạ tình huống Deadlock.
Giải:


8.5. Bốn điều kiện dẫn đến Deadlock là những điều kiện gì?
Giải:
- Mutual exclusion: với mỗi tài nguyên, chỉ có một process sử dụng tại một thời điểm.
- Hold and wait: một process vẫn sở hữu tài nguyên đã được cấp phát trong khi yêu cầu một tài ngyên khác.
- No preemption: một tài nguyên không thể bị đoạt lại từ chính process đang sở hữu tài nguyên đó.
- Circular wait: tồn tại một chu kỳ khép kín các yêu cầu tài nguyên.

8.6. Một hệ thống có 3 loại tài nguyên và 3 tiến trình với trạng thái cấp phát như sau:
Loại tài nguyên Số phiên bản Được các tiến trình yêu cầu Đã cấp cho các tiến trình
Máy in kim 2 P1 P2, P3
Máy in laser 1 P3
Ổ băng từ 2 P2 P1, P3
Hãy thể hiện trạng thái này bằng Đồ thị cấp phát tài nguyên.
Giải:


8.7. Trình bày các phương thức xử trí Deadlock.
Giải:
- Sử dụng quy tắc Ngăn chặn (Prevention) hoặc Tránh (Avoidance) để Deadlock không bao giờ xảy ra.
- Cho phép hệ thống bị Deadlock, sau đó Xác định (Detection) và tìm cách Khắc phục (Recover).
- Không xét vấn đề Deadlock, coi như không bao giờ xảy ra, còn nếu xảy ra thì Khởi động lại hệ thống (Cách này có thể có ý nghĩa thực tế vì không cần đưa vào HĐH các phương tiện xử trí thường trực).

8.8. Trình bày 4 cách ngăn chặn Deadlock.
Giải:
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
- Với Circular Wait: Cấp TN theo một thứ tự nào đấy.

8.9. Thế nào là trạng thái an toàn của hệ thống?
Giải:
- Một trạng thái được gọi là an toàn “safe” nếu tồn tại ít nhất một cách mà trong một khoảng thời gian hữu hạn nào đó, hệ thống có thể cấp phát tài nguyên thỏa mãn cho tất cả process thực thi hoàn tất .
- Khi đó hệ thống tồn tại một Chuỗi an toàn {P1, P2, … , Pn } bao gồm tất cả các tiến trình sao cho với mỗi Pi, các tài nguyên mà nó yêu cầu có thể được đáp ứng bởi số lượng hiện có cộng thêm của tất cả các Pj mà j < i.
- Nếu các TN yêu cầu không có đủ, Pi phải chờ cho đến khi tất cả các Pj trả lại các TN mà chúng chiếm giữ.
- Khi Pi nhận được đủ TN cần thiết, nó sử dụng và trả lại HĐH để Pi+1 có thể vận hành, cứ như thế cho đến Pn
- Khi một process yêu cầu một tài nguyên đang sẵn có, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay.

8.10. Thuật giải tránh Deadlock cho trường hợp mỗi loại tài nguyên chỉ có 1 phiên bản.
Giải:
- Trên RAG, lúc đầu tất cả nhu cầu về tài nguyên của tiến trình phải được khai báo trước bằng các Cung Nhu cầu (Claim edge) Pi • • •> Rj chỉ báo rằng Pi có thể sẽ yêu cầu Rj
- Cung Nhu cầu Pi • • •> Rj được chuyển thành Cung Yêu cầu (Request edge) Pi  Rj khi Pi thực sự bắt đầu cần đến Rj .
- Nếu yêu cầu Pi  Rj được HĐH đáp ứng, cung Pi  Rj chuyển thành Cung Ấn định (Assignment edge) Pi  Rj nối phiên bản duy nhất của Rj với Pi .
- Khi HĐH xét yêu cầu Pi  Rj. Hệ chỉ cấp phát Rj cho Pi nếu Cung Ấn định Pi  Rj không tạo ra vòng tròn đồng hướng trong RAG (xét cả các Cung Nhu cầu).
- Thuật giải có độ phức tạp o(n²) với n là số tiến trình trong hệ.


8.11. Tránh Deadlock bằng Banker’s Algorithm.
Giải:
Là thuật giải tránh Deadlock cho trường hợp mỗi loại tài nguyên có n phiên bản.
- Áp dụng cho hệ thống cấp phát tài nguyên trong đó mỗi loại tài nguyên có thể có nhiều instance.
- Mô phỏng nghiệp vụ ngân hàng (banking)
- Một số giả thiết
Mỗi process phải khai báo số lượng tối đa tài nguyên mỗi loại mà process đó cần để hoàn tất công việc.
Khi process yêu cầu một tài nguyên thì có thể phải đợi mặc dù tài nguyên được yêu cầu đang có sẵn
Khi process đã có được đầy đủ tài nguyên thì phải hoàn trả trong một khoản thời gian hữu hạn nào đó.

8.12. Một hệ thống có 12 ổ băng từ và 3 tiến trình với bảng cấp phát tài nguyên như sau:
Tiến trình Đã được cấp (số ổ băng) Tối đa cần (số ổ băng)
P1 5 10
P2 2 4
P3 2 9
Dùng Thuật giải Nhà băng để xác định trạng thái này có an toàn hay không?
Giải:
Ta có:
Available = 12 – (5 + 2 + 2) = 3
Need = Max – Allocation
P[i] Allocation Max Need Available
P1 5 10 5 3
P2 2 4 2
P3 2 9 7
Xét tại thời điểm Ti
Work >= Need[i] P[i] Allocation[i]
3 2 P2 2
5 5 P1 5
10 7 P3 2
Vậy tồn tại chuổi an toàn < p2, p1, p3 >. Suy ra trạng thái hệ thống ở thời điểm Ti là an toàn.

8.13. Một hệ thống có 5 tiến trình với tình trạng tài nguyên như sau:
Process Allocation Max Available
A B C D A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
Dùng Thuật giải Nhà băng để xác định:
a. Nội dung của ma trận Need.
b. Trạng thái này có an toàn không?
c. Nếu P1 nêu yêu cầu (0, 4, 2, 0), có thể đáp ứng ngay được không?
Giải:
a. Xét tại thời điểm T0 mà 5 tiến trình được cấp phát như đề bài ta có:
Need[i] = Max[i] – Allocation[i]
Process Need
A B C D
P0 0 0 0 0
P1 0 7 5 0
P2 1 0 0 2
P3 0 0 2 0
P4 0 6 4 2
b. Tìm chuỗi an toàn:
Work >= Need[i] P[i] Allocation[i]
A B C D A B C D A B C D
1 5 2 0 0 0 0 0 P0 0 0 1 2
1 5 3 2 1 0 0 2 P2 1 3 5 4
2 8 8 6 0 0 2 0 P3 0 6 3 2
2 14 11 8 0 6 4 2 P4 0 0 1 4
2 14 12 12 0 7 5 0 P1 1 0 0 0
Vậy tại thời điểm T0 tồn tại chuỗi an toàn {P0, P2, P3, P4, P1}. Suy ra, hệ thống tại thời điểm T0 ở trạng thái an toàn.
c. Ta thấy, yêu cầu thêm (0, 4, 2, 0) của P1 thoả điều kiện Request1  Need1, và thoả điều kiện: Request1  Available. Giả sử ta cấp phát theo yêu cầu của P1 thì vẫn tồn tại chuỗi an toàn. Do vậy, ta hoàn toàn có thể cấp phát thêm (0, 4, 2, 0) cho P1 được.


8.14. Một hệ thống có 3 tiến trình và 3 loại tài nguyên với bảng cấp phát tài nguyên như sau:
Loại tài nguyên Số phiên bản Được các tiến trình yêu cầu Đã cấp cho các tiến trình
R1 1 P1 P2
R2 2 P3 P1, P2
R3 1 P2 P3
Có Deadlock hay không? Vì sao?
Giải:

Giải thích: RAG cho trên bi deadlock là do tồn tại các chu trình.