Tiểu luận Hệ tin học phân tán - Đề tài "Vấn đề bế tắc trong hệ tập trung và hệ phân tán" - Trường Đại học Đà Nẵng - Năm 2009 - Nguyên Văn Việt Đức (Bản PowerPoint)

Nội dung text: Tiểu luận Hệ tin học phân tán - Đề tài "Vấn đề bế tắc trong hệ tập trung và hệ phân tán" - Trường Đại học Đà Nẵng - Năm 2009 - Nguyên Văn Việt Đức (Bản PowerPoint)

1. 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
2. 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
3. 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.
4. - Đ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ồ.
5. * 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ộ.
6. Ưu điểm: - Tăng tốc độ bình quân trong tính toán-xử 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. Hình vẽ minh họa:
13. 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 . .
14. 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.
15. 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ó.
16. 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).
17. 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.
18. 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, Ci-1.
19. 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ệ.
20. 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.
21. III. BẾ TẮC TRONG HỆ PHÂN TÁN 1. Một số khái niệm: - Giao dịch: là phép toán hợp thành một lô gích hoàn chỉnh mà việc triển khai nó có thể dẫn đến thực hiện một tiến trình duy nhất hay nhiều tiến trình được định vị trên các trạm khác nhau.
22. - Một tiến trình nào đó cần sử dụng tài nguyên để phát triển công việc của mình phải yêu cầu bộ cung cấp một cách hợp thức bằng cách gửi thông điệp yêu cầu .
23. - Bế tắc (khoá tương hỗ): là sự kẹt chéo lẫn nhau có tính chất sống còn của các tiến trình. Bế tắc diễn ra khi hai tiến trình đang sử dụng hai tài nguyên lại phát yêu cầu về nhu cầu sử dụng tài nguyên mà tiến trình kia còn đang sử dụng.
24. Ví dụ 1: Có 4 tài nguyên T1, T2, T3 và T4 và có 3 nhu cầu tài nguyên là Tr1, Tr2 và Tr3. Cả ba tiến trình này đang ở trong tình trạng bế tắc. Tiến trình Tr2 chờ tài nguyên T3 do Tr3 đang chiếm giữ.Tiến trình Tr3 chờ tài nguyên T2 được giải phóng bởi Tr1 và Tr3.Thêm vào đó, tiến trình chờ tiền trình Tr2 giải phóng T1.
25. T1 T3 Tr1 Tr2 Tr3 T2 T4 Hình 2.1. Đồ thị cung cấp tài nguyên bị bế tắc
26. -> Cả ba tiến trình này đang ở trong tình trạng bế tắc. Tiến trình Tr2 chờ tài nguyên T3 do Tr3 đang chiếm giữ.Tiến trình Tr3 chờ tài nguyên T2 được giải phóng bởi Tr1 và Tr2.Thêm vào đó, tiến trình chờ tiền trình Tr2 giải phóng T1.
27. Lúc này, ta thấy có hai chu trình kín trong đồ thị là: Tr1–T1–Tr2–T3–Tr3–T2–Tr1 Và Tr3–T2–Tr2–T3–Tr3
28. 3. Thuật toán dự phòng bế tắc Lomet Ví dụ 1: Hãy đánh giá 3 giao dịch T1, T2 và T3 sử dụng 3 tài nguyên e1, e2 và e3 của 3 trạm S1, S2, S3. Ta ký hiệu a_loai_tru_th() là phép toán thông điệp.
29. Giao dịch T1 Giao dịch T2 Giao dịch T3 t11: a_loai_tru_th(e1, e2) t21: a_loai_tru_th(e2, e3) t31: a_loai_tru_th(e3, e1) t12: v_loai_tru_th(e1) t22: v_loai_tru_th(e2) t32: v_loai_tru_th(e3) . . . t13: v_loai_tru_th(e2) t23: v_loai_tru_th(e3) t33: v_loai_tru_th(e1)
30. - Giả sử rằng các lệnh thực hiện theo trình tự t11, t21, t31, t12, t22, t32, vào thời điểm t sau khi thực hiện các lệnh này, đồ thị G có thể biểu diễn như sau. Bế tắc không tránh khỏi được
31. - Giả sử rằng các tài nguyên e1,e2,e3 được bố trí trên các trạm tương ứng S1, S2, S3. Nếu trạm Si chỉ nhận các thông cáo tương ứng với tài nguyên mà nó quản lý, thì nó duy trì đồ thị Gi hình ảnh thu nhỏ của G cho các giao dịch đã phát thông báo, như vậy sau khi thực hiện t32 ta có kết quả sau:
32. Thông qua ba đồ thị trên đây, ta không phát hiện mạch khép kín dẫn đến tình trạng bế tắc. Nhưng, nếu ở hệ tập trung hay trạng thái không phải từng phần, ta có đồ thị sau đây:
33. Thuật toán: Nội dung thuật toán được trình bày trong báo cáo [Trang 13]. Ý tưởng thuật toán được triễn khai:
34. Thuật toán: Ta sẽ thay thế vào điều kiện cung cấp trong đồ thị G không vòng lặp một điều kiện khác mạnh hơn, nhưng được kiểm tra bằng các thông tin cục bộ trên từng trạm. Thêm vào cho từng đồ thị G’i hình ảnh thu nhỏ cho Si của đồ thị của một quan hệ trật tự toàn bộ chặt chẽ được xác định trên các tập hợp giao dịch. Quan hệ trật tự này có thể được nhờ phương tiện dấu. Điều kiện cung cấp tài nguyên là duy trì tình trạng không vòng lặp cho các đồ thị Gi. Căn cứ theo cấu trúc, điều kiện này có thể được kiểm tra cục bộ trên từng trạm. Ta sẽ chỉ ra G có được tình trạng không vòng lặp như thế nào. Để làm việc đó, ta bắt đầu chỉ ra sự tồn tại của vòng trong G kéo theo sự tồn tại của vòng trong ít nhất một G’i .
35. Minh họa thuật toán bằng ví du sau: Ví dụ 2: Xem lại ví dụ 1. Khi T1 thực hiện t12: v-loai-tru-th(e1), yêu cầu này vào xung đột với thông cáo a-loai-tru-th(e1) thực hiện bởi T3. Như thế, cung T1-T3 được thành lập trong G. Lúc này, yêu cầu vẫn được chấp nhận vì T1>>T3.
36. Các đồ thị G’i trên ba trạm sẽ như sau: Yêu cầu t22: v-loai-tru-th(e2) kéo theo trên trạm S2 sự tạo nên cung T2-T1 bị loại bỏ; bởi vì nó sinh ra vòng lặp trên S2. Yêu cầu t32: v-loai-tru-th(e3) bị từ chối bởi vì nó tạo ra vòng lặp trên S3. Nếu trật tự theo dạng T1,T2, T3 thì yêu cầu vừa nêu có thể được chấp nhận
37. Nhận xét: - Tương tự như các nhóm sắp xếp, chỉ khác nhau có một điều là nó tránh được sự thiếu thốn vô hạn, bởi vì trật tự tổng quát được triển khai cho các giao dịch chứ không phải cho các tài nguyên. - Một giao dịch trở nên rất cần thiết là giao dịch có thời gian chờ đợi dài nhất sau một khoảng thời gian xác định, nó đã trở thành giao dịch được ưu tiên nhất trên tất cả các trạm mà nó đã gởi thông điệp.
38. IV. PHƯƠNG PHÁP LOMET (BÀI TẬP) Đề bài: Dùng phương pháp sắp xếp các giao dịch của Lomet hãy xác định cho trạm i thuật toán cập nhật đồ thị cục bộ khi nhận thông điệp mới có đóng dấu H(ANj) đến từ trạm j. Ta cần phải đảm bảo rằng một thông điệp ANk nào đó như H(ANj)>H(ANk) được xếp trước ANj ngay cả khi nó chỉ đến trạm i sau ANj. Ngoài ra, ta còn giả sử rằng mỗi trạm j có thể gửi cho chính trạm i nhiều thông điệp AN'j, AN''j, AN'''j, liên quan đến các giao dịch khác nhau.
39. CÁC VẤN ĐỀ CẦN GIẢI QUYẾT 1. Trước khi có thông điệp gửi tới từ trạm j, tại trạm i i lúc này duy trì đồ thị cục bộ với nhiệm vụ hình thành trật tự cho các giao dịch. - Các giao dịch trên trạm i tại thời điểm trước khi có thông điệp H(ANj) được sắp xếp trong hàng đợi, tiêu chí sắp xếp là dấu của các thông điệp.
40. - Trạm phát được gắn một giá trị gọi là dấu. Giá trị này có tính chất thời điểm cho trạm phát thông tin và dựa vào đồng hồ lô gích cục bộ của chính trạm đó. - Các đồng hồ được lấy thông qua hội thoại giữa các trạm. Trạm i của mạng có thể gửi cho các trạm khác thông điệp có dạng (T,Hi,i) trong đó Hi là dấu của thông điệp tức là đồng hồ lô gích của nó và T có thể nhận một trong ba giá trị REQ, REL và ACQ.
41. Trong đó: REQ : được phát đi cho tất cả các trạm khi trạm i muốn vào trong đoạn găng REL: được phát đi cho tất cả các trạm khi trạm i đã rời khỏi đoạn găng ACQ: được gửi bởi trạm j cho trạm i khi trạm j đã nhận được từ trạm i thông điệp REQ
42. Giả sử rằng, tại thời điểm thông cáo của trạm j gửi tới, đồng hồ thời gian lôgich của trạm i sẽ thực hiện phép toán: Nếu Hi thì Hi:= Hj+1; Kết thúc nếu và thông điệp H(ANj) được xếp vào hàng đợi.
43. 2. Giữa giao dịch Ti và Tj hình thành quan hệ: Xét xem có vòng lặp trong G không: Ti1: phát thông báo a_loaitru_th(ei, ej) Ti2 : v_loaitru_th(ej) Tj1: a_loaitru_th(ej, ei) Tj2 : v_loaitru_th(ei)
44. Vậy giữa giao dịch Ti1 và Tj2 hình thành một cung trong G, sau khi xảy ra việc này ta phân giải đồ thị G’i trên trạm i như sau : Nếu đã hình thành cung Ti -> Tj thì các yêu cầu khác tạo nên các cung giữa các cặp giao dịch khác sẽ bị từ chối.
45. 3. Để đảm bảo rằng một thông điệp ANk nào đó như H(ANj)>H(ANk) được xếp trước ANj ngay cả khi nó chỉ đến đến trạm i sau ANj. Ngoài ra, ta còn giả sử rằng mỗi trạm j có thể gửi cho chính trạm i nhiều thông điệp AN'j, AN''j, AN'''j, liên quan đến các giao dịch khác nhau: Do sử dụng đồng hồ lô gích và mỗi Gi là hình ảnh thu nhỏ của G nên mặc dù thông điệp ANk đã phát đi và được đóng dấu H(ANk), nhưng còn lang thang trên đường và đến trạm i sau thì trạm i vẫn có hình ảnh về thông điệp của ANk. Vì vậy trạm i vẫn sắp xếp ANk vào hàng đợi dựa trên dấu H(ANk).
46. Để đảm bảo được như vậy thì phải đảm tính gắn bó dữ liệu mạnh. Tại mọi lúc mọi nơi thì hình ảnh thu nhỏ của G trên i là tức thời, nếu không đảm bảo được tính gắn bó mạnh thì thông điệp ANk sẽ đến sau ANj hoặc mất thông điệp mặc dù ANk phát thông điệp trước.
47. CHÂN THÀNH CẢM ƠN THẦY VÀ ANH (CHỊ) ĐÃ LẮNG NGHE!