Báo cáo Hệ tin học phân tán: Vấn đề bế tắc trong hệ tập trung và hệ phân tán

Chia sẻ: Cá Nhét Xù | Ngày: | Loại File: PPT | Số trang:48

Thêm vào BST

Báo xấu

77
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung bài thuyết trình gồm các nội dung: Giới thiệu, bế tắc trong hệ tập trung, bế tắc trong hệ phân tán, phương pháp Lomet.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo Hệ tin học phân tán: Vấn đề bế tắc trong hệ tập trung và hệ phân tán

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG  ĐỀ TÀI: VẤN ĐỀ BẾ TẮC TRONG HỆ TẬP TRUNG VÀ HỆ PHÂN TÁN GVHD: PGS.TS LÊ VĂN SƠN HV: NGUYỄN VĂN VIỆT ĐỨC LỚP: Khoa học máy ính Khoá 10: 2008 2011
NỘI DUNG BÁO CÁO I. GIỚI THIỆU II. BẾ TẮC TRONG HỆ TẬP TRUNG III.BẾ TẮC TRONG HỆ PHÂN TÁN IV.PHƯƠNG PHÁP LOMET
I. GIỚI THIỆU Hệ tin học phân tán là hệ thống xử lý thông tin: Nhiều bộ xử lý, bộ vi xử lý nằm tại các vị trí khác nhau. Liên kết qua phương tiện viễn thông dưới sự điều khiển thống nhất của một hệ điều hành.
Đa dạng, đa diện, phức tạp về mặt cấu trúc, tập hợp. Gồm các bộ xử lý hoặc bộ vi xử lý với bộ nhớ và đồng hồ nhịp độc lập. Các bộ xử lý không sử dụng chung bộ nhớ và đồng hồ.
* Như vậy, mỗi một hệ xử lý thông tin thành phần của hệ tin học phân tán bao gồm một hay nhiều bộ xử lý và bộ nhớ cục bộ.
Ưu điểm: Tăng tốc độ bình quân trong tính toánxử lý. Cải thiện tình trạng luôn luôn sẵn sàng của các loại tài nguyên. Tăng độ an toàn dữ liệu. Đa dạng hóa các loại hình dịch vụ tin học. Đảm bảo tính vẹn toàn của thông tin.
Các vấn đề cần giải quyết: Yêu cầu truy cập từ xa. Trả lời yêu cầu. Đảm bảo tính đồng bộ, gắn bó dữ liệu và xử lý các bế tắc phát sinh trong quá trình hệ hoạt động.
Tìm hiểu: VẤN ĐỀ BẾ TẮC TRONG HỆ TẬP TRUNG VÀ HỆ PHÂN TÁN. PHƯƠNG PHÁP LOMET SẮP XẾP CÁC GIAO DỊCH.
II. BẾ TẮC TRONG HỆ TẬP TRUNG Hiện tượng bế tắc đều bắt nguồn từ sự xung đột về tài nguyên của hai hoặc nhiều tiến trình đang hoạt động đồng thời trên hệ thống. Tài nguyên ở đây có thể là một ổ đĩa, một record trong cơ sở dữ liệu, hay một không gian địa chỉ trên bộ nhớ chính.
Ví dụ 1: G/s có 2 tiến trình P1 và P2 hoạt động đồng thời trong hệ thống. Tiến trình P1 đang giữ tài nguyên R1 và xin được cấp R2 để tiếp tục hoạt động, trong khi đó tiến trình P2 đang giữ tài nguyên R2 và xin được cấp R1 để tiếp tục hoạt động.
Trong trường hợp này cả P1 và P2 sẽ không tiếp tục hoạt động được. Như vậy, P1 và P2 rơi vào trạng thái bế tắc.
Hình vẽ minh họa:
G/s không gian bộ nhớ còn trống là 200Kb, trong hệ thống có hai tiến trình P1 và P2 yêu cầu được sử dụng bộ nhớ như sau: P1 P2 …. …. Request1 80Kb Request1 70Kb …. …. Request2 30Kb Request2 40Kb …. ….
Ví dụ 2: Bế tắc xảy ra khi cả hai tiến trình cùng yêu cầu thêm bộ nhớ lần thứ hai. Tại thời điểm này, không gian bộ nhớ còn trống là 50Kb, lớn hơn lượng bộ nhớ mà mỗi tiến trình yêu cầu (30Kb và 40Kb), nhưng vì cả hai tiến trình đồng thời yêu cầu thêm bộ nhớ nên hệ thống không thể đáp ứng được, và bế tắc xảy ra.
1. Điều kiện hình thành bế tắc? Loại trừ lẫn nhau hay độc quyền sử dụng: Đối với các tài nguyên không phân chia được thì tại mỗi thời điểm chỉ có một tiến trình sử dụng được tài nguyên. Giữ và đợi: Một tiến trình hiện tại đang chiếm giữ tài nguyên, lại xin cấp phát thêm tài nguyên mới. Không ưu tiên: Không có tài nguyên nào có thể được giải phóng từ một tiến trình đang chiếm giữ nó.
Nhận xét: Sự bế tắc có thể tồn tại với ba điều kiện trên, nhưng cũng có thể không xảy ra với ba điều kiện đó. Để chắc chắn bế tắc xãy ra cần phải có điều kiện thứ tư (Đợi vòng tròn: Mỗi tiến trình đang chiếm giữ tài nguyên mà tiến trình khác đang cần).
Nhận xét: Ba điều kiện đầu là điều kiện cần chứ không phải điều kiện đủ để xảy ra bế tắc. Điều kiện thứ tư là kết quả tất yếu từ ba điều kiện đầu.
2. Các phương pháp sử dụng trong hệ tập trung để xử lý bế tắc a. Phương pháp dự phòng: đơn giản và thường hay sử dụng là phương pháp các nhóm sắp xếp Havender. Các tài nguyên được sắp xếp theo các nhóm con C1, C2, …Cn. Một tiến trình nào đó có thể thu hồi tài nguyên của nhóm Ci với i>1, nếu trước đó nó đã thu hồi tất cả các tài nguyên của nhóm cần thiết cho nó C1, C2, …Ci1.
Như thế, trật tự duy nhất của việc thu hồi các tài nguyên được xác định sẽ tránh được bế tắc. Phương pháp này dẫn đến các tiến trình cần thu hồi trước (tạm ứng) các tài nguyên của chúng và do vậy làm giảm khả năng thực hiện song song của hệ.
b. Phương pháp phát hiện và chữa trị Sử dụng một đồ thị trạng thái định hướng mà các nút là các tài nguyên hay các tiến trình. Các cung tiến trình tiến trình thể hiện các cung cấp đã được thực hiện. Nếu có sự hiện diện của vòng lặp khép kín trong đồ thị này thì đó chính là biểu hiện của tình trạng bế tắc. > Phức tạp, tốn kém.