Bài giảng Hệ điều hành - Phạm Đăng Hải - Chương 2: Quản lý tiến trình

 3 0 3
P3 2 1 1
P4 0 0 2
Allocation
R0 R1 R2
P0 0 0 0
P1 2 0 2
P2 0 0 1
P3 1 0 0
P4 6 0 2
Request
Thực hiện thuật toán chỉ ra bế tắc
Tiến trình P0 P1 P2 P3 P4
Finish T F F F F
Work (0, 1, 0)
P0 có thể kết thúc nhưng hệ thống đang bế tắc.
Các tiến trình đang chờ đợi lẫn nhau (P1,P2,P3,P4)
197 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Ví dụ minh họa (tiếp)
P2 yêu cầu thêm 1 đơn vị tài nguyên R2
Trạng thái cung cấp tài nguyên tại thời điểm t1
R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 3
P3 2 1 1
P4 0 0 2
Allocation
R0 R1 R2
P0 0 0 0
P1 2 0 2
P2 0 0 1
P3 1 0 0
P4 6 0 2
Request
Thực hiện thuật toán chỉ ra bế tắc
Tiến trình P0 P1 P2 P3 P4
Finish T F F F F
Work (0, 1, 0)
P0 có thể kết thúc nhưng hệ thống đang bế tắc.
Các tiến trình đang chờ đợi lẫn nhau (P1,P2,P3,P4)
197 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Ví dụ minh họa (tiếp)
P2 yêu cầu thêm 1 đơn vị tài nguyên R2
Trạng thái cung cấp tài nguyên tại thời điểm t1
R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 3
P3 2 1 1
P4 0 0 2
Allocation
R0 R1 R2
P0 0 0 0
P1 2 0 2
P2 0 0 1
P3 1 0 0
P4 6 0 2
Request
Thực hiện thuật toán chỉ ra bế tắc
Tiến trình P0 P1 P2 P3 P4
Finish T F F F F
Work (0, 1, 0)
P0 có thể kết thúc nhưng hệ thống đang bế tắc.
Các tiến trình đang chờ đợi lẫn nhau (P1,P2,P3,P4)
197 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Ví dụ minh họa (tiếp)
P2 yêu cầu thêm 1 đơn vị tài nguyên R2
Trạng thái cung cấp tài nguyên tại thời điểm t1
R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 3
P3 2 1 1
P4 0 0 2
Allocation
R0 R1 R2
P0 0 0 0
P1 2 0 2
P2 0 0 1
P3 1 0 0
P4 6 0 2
Request
Thực hiện thuật toán chỉ ra bế tắc
Tiến trình P0 P1 P2 P3 P4
Finish T F F F F
Work (0, 1, 0)
P0 có thể kết thúc nhưng hệ thống đang bế tắc.
Các tiến trình đang chờ đợi lẫn nhau (P1,P2,P3,P4)
197 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Khắc phục bế tắc: Phương pháp kết thúc tiến trình
Nguyên tắc: Hủy bỏ các tiến trình đang trong tình trạng bế tắc và
lấy lại tài nguyên đã cấp cho tiến trình bị hủy bỏ
Hủy bỏ tất cả các tiến trình
Nhanh chóng hủy bỏ bế tắc
Quá tốn kém
Các tiến trình bị hủy bỏ có thể gần kết thúc
Hủy bỏ lần lượt tiến trình cho tới khi bế tắc không xảy ra
Sau khi hủy bỏ, phải kiểm tra xem bế tắc còn tồn tại không
Thuật toán kiểm tra bế tắc có độ phức tạp m ∗ n2
Cần chỉ ra thứ tự tiến trình bị hủy bỏ để phá vỡ bế tắc
Độ ưu tiên của tiến trình.
Tiến trình đã tồn tại bao lâu, còn bao lâu nữa thì kết thúc
Tài nguyên tiến trình đang chiếm giữ, còn cần để kết thúc
. . .
Vấn đề hủy bỏ tiến trình
Tiến trình đang cập nhật file ⇒ File không hoàn chỉnh
Tiến trình sử dụng máy in ⇒ Reset trạng thái máy in
198 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Khắc phục bế tắc: Phương pháp kết thúc tiến trình
Nguyên tắc: Hủy bỏ các tiến trình đang trong tình trạng bế tắc và
lấy lại tài nguyên đã cấp cho tiến trình bị hủy bỏ
Hủy bỏ tất cả các tiến trình
Nhanh chóng hủy bỏ bế tắc
Quá tốn kém
Các tiến trình bị hủy bỏ có thể gần kết thúc
Hủy bỏ lần lượt tiến trình cho tới khi bế tắc không xảy ra
Sau khi hủy bỏ, phải kiểm tra xem bế tắc còn tồn tại không
Thuật toán kiểm tra bế tắc có độ phức tạp m ∗ n2
Cần chỉ ra thứ tự tiến trình bị hủy bỏ để phá vỡ bế tắc
Độ ưu tiên của tiến trình.
Tiến trình đã tồn tại bao lâu, còn bao lâu nữa thì kết thúc
Tài nguyên tiến trình đang chiếm giữ, còn cần để kết thúc
. . .
Vấn đề hủy bỏ tiến trình
Tiến trình đang cập nhật file ⇒ File không hoàn chỉnh
Tiến trình sử dụng máy in ⇒ Reset trạng thái máy in
198 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Khắc phục bế tắc: Phương pháp kết thúc tiến trình
Nguyên tắc: Hủy bỏ các tiến trình đang trong tình trạng bế tắc và
lấy lại tài nguyên đã cấp cho tiến trình bị hủy bỏ
Hủy bỏ tất cả các tiến trình
Nhanh chóng hủy bỏ bế tắc
Quá tốn kém
Các tiến trình bị hủy bỏ có thể gần kết thúc
Hủy bỏ lần lượt tiến trình cho tới khi bế tắc không xảy ra
Sau khi hủy bỏ, phải kiểm tra xem bế tắc còn tồn tại không
Thuật toán kiểm tra bế tắc có độ phức tạp m ∗ n2
Cần chỉ ra thứ tự tiến trình bị hủy bỏ để phá vỡ bế tắc
Độ ưu tiên của tiến trình.
Tiến trình đã tồn tại bao lâu, còn bao lâu nữa thì kết thúc
Tài nguyên tiến trình đang chiếm giữ, còn cần để kết thúc
. . .
Vấn đề hủy bỏ tiến trình
Tiến trình đang cập nhật file ⇒ File không hoàn chỉnh
Tiến trình sử dụng máy in ⇒ Reset trạng thái máy in
198 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Khắc phục bế tắc: Phương pháp kết thúc tiến trình
Nguyên tắc: Hủy bỏ các tiến trình đang trong tình trạng bế tắc và
lấy lại tài nguyên đã cấp cho tiến trình bị hủy bỏ
Hủy bỏ tất cả các tiến trình
Nhanh chóng hủy bỏ bế tắc
Quá tốn kém
Các tiến trình bị hủy bỏ có thể gần kết thúc
Hủy bỏ lần lượt tiến trình cho tới khi bế tắc không xảy ra
Sau khi hủy bỏ, phải kiểm tra xem bế tắc còn tồn tại không
Thuật toán kiểm tra bế tắc có độ phức tạp m ∗ n2
Cần chỉ ra thứ tự tiến trình bị hủy bỏ để phá vỡ bế tắc
Độ ưu tiên của tiến trình.
Tiến trình đã tồn tại bao lâu, còn bao lâu nữa thì kết thúc
Tài nguyên tiến trình đang chiếm giữ, còn cần để kết thúc
. . .
Vấn đề hủy bỏ tiến trình
Tiến trình đang cập nhật file ⇒ File không hoàn chỉnh
Tiến trình sử dụng máy in ⇒ Reset trạng thái máy in
198 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Khắc phục bế tắc: Phương pháp trưng dụng tài nguyên
Nguyên tắc:
Trưng dụng liên tục một vài tài nguyên từ một số tiến trình đang
bế tắc cho các tiến trình khác đến khi bế tắc được hủy bỏ
Các vấn đề cần quan tâm
1 Lựa chọn nạn nhân (victime)
Tài nguyên nào và tiến trình nào được chọn?
Trật tự trưng dụng để chi phí nhỏ nhất?
Lượng tài nguyên nắm giữ, thời gian sử dụng. . .
2 Quay lui (Rollback)
Quay lui tới một trạng thái an toàn trước đó và bắt đầu lại
Yêu cầu lưu giữ thông tin trạng thái của t/trình đang thực hiện
3 Đói tài nguyên (Starvation)
Một tiến trình bị trưng dụng quá nhiều lần ⇒chờ đợi vô hạn
Giải pháp: ghi lại số lần bị trưng dụng
199 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Khắc phục bế tắc: Phương pháp trưng dụng tài nguyên
Nguyên tắc:
Trưng dụng liên tục một vài tài nguyên từ một số tiến trình đang
bế tắc cho các tiến trình khác đến khi bế tắc được hủy bỏ
Các vấn đề cần quan tâm
1 Lựa chọn nạn nhân (victime)
Tài nguyên nào và tiến trình nào được chọn?
Trật tự trưng dụng để chi phí nhỏ nhất?
Lượng tài nguyên nắm giữ, thời gian sử dụng. . .
2 Quay lui (Rollback)
Quay lui tới một trạng thái an toàn trước đó và bắt đầu lại
Yêu cầu lưu giữ thông tin trạng thái của t/trình đang thực hiện
3 Đói tài nguyên (Starvation)
Một tiến trình bị trưng dụng quá nhiều lần ⇒chờ đợi vô hạn
Giải pháp: ghi lại số lần bị trưng dụng
199 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Khắc phục bế tắc: Phương pháp trưng dụng tài nguyên
Nguyên tắc:
Trưng dụng liên tục một vài tài nguyên từ một số tiến trình đang
bế tắc cho các tiến trình khác đến khi bế tắc được hủy bỏ
Các vấn đề cần quan tâm
1 Lựa chọn nạn nhân (victime)
Tài nguyên nào và tiến trình nào được chọn?
Trật tự trưng dụng để chi phí nhỏ nhất?
Lượng tài nguyên nắm giữ, thời gian sử dụng. . .
2 Quay lui (Rollback)
Quay lui tới một trạng thái an toàn trước đó và bắt đầu lại
Yêu cầu lưu giữ thông tin trạng thái của t/trình đang thực hiện
3 Đói tài nguyên (Starvation)
Một tiến trình bị trưng dụng quá nhiều lần ⇒chờ đợi vô hạn
Giải pháp: ghi lại số lần bị trưng dụng
199 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
5.6 Nhận biết và khắc phục
Khắc phục bế tắc: Phương pháp trưng dụng tài nguyên
Nguyên tắc:
Trưng dụng liên tục một vài tài nguyên từ một số tiến trình đang
bế tắc cho các tiến trình khác đến khi bế tắc được hủy bỏ
Các vấn đề cần quan tâm
1 Lựa chọn nạn nhân (victime)
Tài nguyên nào và tiến trình nào được chọn?
Trật tự trưng dụng để chi phí nhỏ nhất?
Lượng tài nguyên nắm giữ, thời gian sử dụng. . .
2 Quay lui (Rollback)
Quay lui tới một trạng thái an toàn trước đó và bắt đầu lại
Yêu cầu lưu giữ thông tin trạng thái của t/trình đang thực hiện
3 Đói tài nguyên (Starvation)
Một tiến trình bị trưng dụng quá nhiều lần ⇒chờ đợi vô hạn
Giải pháp: ghi lại số lần bị trưng dụng
199 / 201
Chương 2: Quản lý tiến trình
5. Bế tắc và xử lý bế tắc
Tổng kết
Bế tắc là tình trạng 2 hay nhiều tiến trình cùng chờ đợi độc
lập một sự kiện chỉ có thể xảy ra bởi sự hoạt động của các
tiến trình đang đợi
Bế tắc xảy ra khi hội đủ 4 điều kiện
Tồn tại tài nguyên găng
Phải chờ đợi trước khi vào đoạn găng
Không tồn tại hệ thống phân phối lại tài nguyên
Tồn tại hiện tượng chờ đợi vòng tròn
Để xử lý bế tắc có 3 lớp thuật toán
Phòng ngừa bế tắc
Tác động vào các điều kiện xảy ra bế tắc
Dự báo và phòng tránh
Ngăn ngừa hệ thống rơi vào tình trạng có thể dẫn đến bế tắc
Nhận biết và khắc phục
Cho phép bế tắc xảy ra, chỉ ra bế tắc và khắc phục sau
200 / 201
Chương 2: Quản lý tiến trình
Kết luận
1 Tiến trình
Khái niệm tiến trình
Điều phối tiến trình (Process
Scheduling)
Thao tác trên tiến trình
Hợp tác tiến trình
Truyền thông liên tiến trình
2 Luồng (Thread)
Giới thiệu
Mô hình đa luồng
Cài đặt luồng
3 Điều phối CPU
Các khái niệm cơ bản
Tiêu chuẩn điều phối
Các thuật toán điều phối CPU
Điều phối đa xử lý
4 Tài nguyên găng và điều độ
tiến trình
Khái niệm tài nguyên găng
Phương pháp khóa trong
Phương pháp kiểm tra và xác
lập
Kỹ thuật đèn báo
Ví dụ về đồng bộ tiến trình
Công cụ điều độ cấp cao
5 Bế tắc và xử lý bế tắc
Khái niệm bế tắc
Điều kiện xảy ra bế tắc
Các phương pháp xử lý bế tắc
Phòng ngừa bế tắc
Phòng tránh bế tắc
Nhận biết và khắc phục
201 / 201