Tiểu luận Lập trình mạng nâng cao

MỤC LỤC LỜI NÓI ĐẦU .2 A.PHẦN LÝ THUYẾT 4 I. CÁC KHÁI NIỆM CƠ BẢN VÀ KIẾN THỨC CHUNG VỀ HỆ TIN HỌC PHÂN TÁN 4 I.1. Khái niệm .4 I.2. Ưu điểm và hạn chế của hệ phân 4 I.3. Vấn đề về trỏ thông tin .5 I.4. Vấn đề hệ thống nhiều bản sao .6 II. SỰ GẮN BÓ THÔNG TIN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN .6 II.1 Các điều kiện giả định và thực tế .6 II.2 Tác động và giao dịch .7 II.3 Triển khai giao dịch tôn trọng sự gắn bó 8 II.4 Quản lý gắn bó các giao dịch 9 III. CÁC THUẬT TOÁN ĐẢM BẢO SỰ GẮN BÓ DỮ LIỆU TRONG CÁC CƠ SỞ DỮ LIỆU PHÂN TÁN 10 III.1 Thuật toán cung cấp .10 III.2 Kiểu sắp xếp đóng dấu .10 III.2.1 Nguyên lý 11 III.2.2 Triển khai hệ số ổn định 11 III.2.3. Các hành vi ngoài chế độ bình thường .11 III.3. Thuật toán đảm bảo sự gắn bó yếu nhờ bộ tuần tự tuần hoàn .11 III.3.1 Nguyên lý 11 III.3.2 Triển khai hệ số ổn định 12 III.3.3. Các hành vi ngoài chế độ bình thường .12 III.4. Thuật toán đảm bảo sự gắn bó mạnh 12 III.4.1 Nguyên lý 12 III.4.2 Triển khai hệ số ổn định 13 III.4.3 Các hành vi ngoài chế độ bình thường 13 III.4 4 Phân tán biểu hiện trạng thái và chức năng cung cấp 14 B.PHẦN BÀI TẬP 16 I. ĐẶT VẤN ĐỀ .16 I.1 Giới thiệu bài toán .16 I.2 Cơ sở lý thuyết để giải quyết bài toán . .16 II. GIẢI QUYẾT VẤN ĐỀ . .19 II.1 Các trạng thái khác nhau cần xem sét cho mỗi bản sao. 19 II.2 Sơ đồ hoạt động của thuật toán 20 II.3 Đánh giá hàm của số lượng bản sao, số lượng thông điệp cần thiết để thực hiện một cập nhật .21 II.4 Xử lý sự cố trên một trạm 22 C. KẾT LUẬN .24 TÀI LIỆU THAM KHẢO .25 LỜI NÓI ĐẦU Hiện nay, việc nghiên cứu phát triển các giải pháp kỹ thuật cơ sở cho các ứng dụng phân tán đã đạt được những thành công nhất định và thể hiện trong các công bố mới nhất. Tuy nhiên, để có được một giải pháp hữu hiệu đáp ứng các yêu cầu đặt ra của việc gắn bó dữ liệu trong môi trường phân tán như Internet/Intranet, thì đòi hỏi phải tiếp tục nghiên cứu hoàn thiện các giải pháp hiện hành. Vấn đề gắn bó dữ liệu trong các hệ thống phân tán nói chung và các hệ thống thông tin đăng ký trên mạng nói riêng như việc đăng ký các tua du lịch, mua bán trong các giao dịch thương mại điện tử, đăng ký giữ chỗ trong giao thông vận tải, đăng ký dự thi trong các hệ thống thông tin đào tạo, . đã trở thành một lĩnh vực thu hút nhiều sự quan tâm của các nhà nghiên cứu lý thuyết lẫn các nhà sản xuất phần mềm nhằm tìm ra các giải pháp hữu hiệu đảm bảo tính gắn bó thông tin trong các cơ sở dữ liệu truy cập ngẫu nhiên với số lượng truy cập lớn. Việc nghiên cứu, phát triển các phương pháp đảm bảo gắn bó dữ liệu trong môi trường phân tán đến nay đã có một số thành công đáng kể. Trước hết, phải nói đến sự tích hợp hàng loạt các hàm vào các hệ điều hành, hệ quản trị cơ sở dữ liệu, ngôn ngữ lập trình với phương thức riêng rẽ của từng hệ cho phép đảm bảo phần cơ bản của việc gắn bó thông tin nói chung trong quá trình đa truy cập thông qua hệ thống viễn thông. Việc triển khai phương pháp cho phép gắn bó dữ liệu trong môi trường phân tán trong điều kiện lý tưởng (không có bất kỳ sự cố nào) đã được áp dụng và mang lại những hiệu quả nhất định cho các hệ thống đăng ký. Tuy nhiên, trong quá trình triển khai lập trình và vận hành các hệ thống đăng ký, vấn đề gắn bó dữ liệu trong các cơ sở dữ liệu khi hệ thống bị sự cố đang đặt ra như là vấn đề quan trọng và có ý nghĩa sống còn trong việc phát triển toàn hệ nói chung. Với những lý do đó nên trong phạm vi tiểu luận của mình, tôi trình bày được những vấn đề sau: Phần Lý Thuyết  Trình bày các khái niệm cơ bản và kiến thức chung của hệ tin học phân tán.  Sự gắn bó thông tin trong cơ sở dữ liệu phân tán  Thuật toán đảm bảo gắn bó mạnh giữa các CSDL phân tán Phần Bài Tập  Áp dụng thuật toán Mullery đảm bảo gắn bó dữ liệu trong các CSDL phân tán.

doc25 trang | Chia sẻ: lvcdongnoi | Ngày: 01/07/2013 | Lượt xem: 2053 | Lượt tải: 1download
Bạn đang xem nội dung tài liệu Tiểu luận Lập trình mạng nâng cao, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
MỤC LỤC LỜI NÓI ĐẦU...................................................................................................................2 A.PHẦN LÝ THUYẾT......................................................................................................4 I. CÁC KHÁI NIỆM CƠ BẢN VÀ KIẾN THỨC CHUNG VỀ HỆ TIN HỌC PHÂN TÁN..............................................4 I.1. Khái niệm.........................................................................................................4 I.2. Ưu điểm và hạn chế của hệ phân......................................................................4 I.3. Vấn đề về trỏ thông tin.....................................................................................5 I.4. Vấn đề hệ thống nhiều bản sao.........................................................................6 II. SỰ GẮN BÓ THÔNG TIN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN...................6 II.1 Các điều kiện giả định và thực tế.....................................................................6 II.2 Tác động và giao dịch.......................................................................................7 II.3 Triển khai giao dịch tôn trọng sự gắn bó..........................................................8 II.4 Quản lý gắn bó các giao dịch............................................................................9 III. CÁC THUẬT TOÁN ĐẢM BẢO SỰ GẮN BÓ DỮ LIỆU TRONG CÁC CƠ SỞ DỮ LIỆU PHÂN TÁN......................................................10 III.1 Thuật toán cung cấp.......................................................................................10 III.2 Kiểu sắp xếp đóng dấu...................................................................................10 III.2.1 Nguyên lý..............................................................................................11 III.2.2 Triển khai hệ số ổn định........................................................................11 III.2.3. Các hành vi ngoài chế độ bình thường.................................................11 III.3. Thuật toán đảm bảo sự gắn bó yếu nhờ bộ tuần tự tuần hoàn.......................11 III.3.1 Nguyên lý..............................................................................................11 III.3.2 Triển khai hệ số ổn định........................................................................12 III.3.3. Các hành vi ngoài chế độ bình thường.................................................12 III.4. Thuật toán đảm bảo sự gắn bó mạnh............................................................12 III.4.1 Nguyên lý..............................................................................................12 III.4.2 Triển khai hệ số ổn định........................................................................13 III.4.3 Các hành vi ngoài chế độ bình thường..................................................13 III.4 4 Phân tán biểu hiện trạng thái và chức năng cung cấp............................14 B.PHẦN BÀI TẬP............................................................................................................16 I. ĐẶT VẤN ĐỀ………………………………………………………………….16 I.1 Giới thiệu bài toán………………………………………………………...16 I.2 Cơ sở lý thuyết để giải quyết bài toán….………………………………...16 II. GIẢI QUYẾT VẤN ĐỀ...…………………………………………………….19 II.1 Các trạng thái khác nhau cần xem sét cho mỗi bản sao.………………....19 II.2 Sơ đồ hoạt động của thuật toán………………………..………………....20 II.3 Đánh giá hàm của số lượng bản sao, số lượng thông điệp cần thiết để thực hiện một cập nhật……………………………………….21 II.4 Xử lý sự cố trên một trạm………………………………………………..22 C. KẾT LUẬN…………………………………………………………………………...24 TÀI LIỆU THAM KHẢO.................................................................................................25 LỜI NÓI ĐẦU ---—&–--- Hiện nay, việc nghiên cứu phát triển các giải pháp kỹ thuật cơ sở cho các ứng dụng phân tán đã đạt được những thành công nhất định và thể hiện trong các công bố mới nhất. Tuy nhiên, để có được một giải pháp hữu hiệu đáp ứng các yêu cầu đặt ra của việc gắn bó dữ liệu trong môi trường phân tán như Internet/Intranet, thì đòi hỏi phải tiếp tục nghiên cứu hoàn thiện các giải pháp hiện hành. Vấn đề gắn bó dữ liệu trong các hệ thống phân tán nói chung và các hệ thống thông tin đăng ký trên mạng nói riêng như việc đăng ký các tua du lịch, mua bán trong các giao dịch thương mại điện tử, đăng ký giữ chỗ trong giao thông vận tải, đăng ký dự thi trong các hệ thống thông tin đào tạo,... đã trở thành một lĩnh vực thu hút nhiều sự quan tâm của các nhà nghiên cứu lý thuyết lẫn các nhà sản xuất phần mềm nhằm tìm ra các giải pháp hữu hiệu đảm bảo tính gắn bó thông tin trong các cơ sở dữ liệu truy cập ngẫu nhiên với số lượng truy cập lớn. Việc nghiên cứu, phát triển các phương pháp đảm bảo gắn bó dữ liệu trong môi trường phân tán đến nay đã có một số thành công đáng kể. Trước hết, phải nói đến sự tích hợp hàng loạt các hàm vào các hệ điều hành, hệ quản trị cơ sở dữ liệu, ngôn ngữ lập trình với phương thức riêng rẽ của từng hệ cho phép đảm bảo phần cơ bản của việc gắn bó thông tin nói chung trong quá trình đa truy cập thông qua hệ thống viễn thông. Việc triển khai phương pháp cho phép gắn bó dữ liệu trong môi trường phân tán trong điều kiện lý tưởng (không có bất kỳ sự cố nào) đã được áp dụng và mang lại những hiệu quả nhất định cho các hệ thống đăng ký. Tuy nhiên, trong quá trình triển khai lập trình và vận hành các hệ thống đăng ký, vấn đề gắn bó dữ liệu trong các cơ sở dữ liệu khi hệ thống bị sự cố đang đặt ra như là vấn đề quan trọng và có ý nghĩa sống còn trong việc phát triển toàn hệ nói chung. Với những lý do đó nên trong phạm vi tiểu luận của mình, tôi trình bày được những vấn đề sau: Phần Lý Thuyết Trình bày các khái niệm cơ bản và kiến thức chung của hệ tin học phân tán. Sự gắn bó thông tin trong cơ sở dữ liệu phân tán Thuật toán đảm bảo gắn bó mạnh giữa các CSDL phân tán Phần Bài Tập Áp dụng thuật toán Mullery đảm bảo gắn bó dữ liệu trong các CSDL phân tán.          Xin chân thành cảm ơn Thầy Lê Văn Sơn và Thầy Đặng Hùng Vỹ đã trang bị những kiến thức và thông tin về môn học và giới thiệu những tài liệu thiết thực để tôi có thể hoàn thành tiểu luận này. Với kiến thức có hạn nên tiểu luận này không tránh khỏi những sai sót. Rất mong nhận được sự góp ý của Thầy và các anh chị trong lớp. Học viên thực hiện Nguyễn Cao Tài A. LÝ THUYẾT I. CÁC KHÁI NIỆM CƠ BẢN VÀ KIẾN THỨC CHUNG VỀ HỆ TIN HỌC PHÂN TÁN I.1 Khái niệm Hệ tin học phân tán hay nói ngắn gọn là hệ phân tán là hệ thống xử lý thông tin bao gồm nhiều bộ xử lý hoặc bộ vi xử lý nằm tại các vị trí khác nhau và được liên kết với nhau thông qua hệ thống viễn thông dưới sự điều hành thống nhất của một hệ điều hành. Từ định nghĩa này, người ta có thể xem hệ phân tán như là một tập hợp bao 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. Điều này đồng nghĩa với việc 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ệ phân tán bao gồm một hay nhiều bộ xử lý và bộ nhớ cục bộ. Hệ xử lý thông tin thành phần phải được thiết kế sao cho về cấu trúc, số lượng và dung lượng có thể cho phép thực hiện một cách trọn vẹn các chức năng mà nó đảm nhận. Hệ phân tán được xây dựng nhằm mục đích phân tán hoá các quá trình xử lý thông tin và thực hiện công việc đó trên các trạm xa nhau. Đó là những cơ sở căn bản cho việc xây dựng các ứng dụng lớn như thương mại điện tử, giáo dục điện tử, thư viện điện tử số, xây dựng các cơ sở dữ liệu tìm kiếm… Ta có thể nói hệ phân tán bao gồm 4 thực thể như hình vẽ. Hệ thống dữ liệu Hệ thống phần mềm Hệ thống truyền thông Tập hợp phần cứng I.2 Ưu và nhược điểm của hệ phân tán 1) Ưu điểm Chia xẻ tài nguyên: Chia xẻ tài nguyên trong hệ thống phân tán cung cấp một cơ chế để chia xẻ tập tin ở vị trí xa, xử lý thông tin trong một cơ sở dữ liệu phân tán, in ấn tại một vị trí xa, sử dụng những thiết bị ở xa để thực hiện các thao tác… Tăng tốc độ tính toán: Hệ thống phân tán cho phép phân chia việc tính toán trên nhiều vị trí khác nhau để tính toán song song. An toàn: Nếu một vị trí trong hệ thống phân tán bị hỏng, các vị trí khác vẫn tiếp tục làm việc mà không ảnh hưởng đến toàn bộ hệ thống. Thông tin liên lạc với nhau: Có nhiều lúc, chương trình cần chuyển đổi dữ liệu từ vị trí này sang vị trí khác. Khi các vị trí được nối kết với nhau trong một hệ thống mạng, việc trao đổi dữ liệu diễn ra rất dễ. 2) Hạn chế Giá phát triển phần mềm cao: Do các khó khăn khi cài đặt một hệ thống phân tán, giá thành sẽ tăng lên. Dễ mắc lỗi hơn: Vì các trạm trong hệ phân tán làm việc song song, khó có thể đảm bảo thuật toán được thực hiện đúng trên tất cả các trạm. Do vậy mà số lỗi sẽ tăng lên. Khối lượng các xử lý tăng: Hệ thống phân tán cần truyền nhiều thông báo, nhiều tính toán phụ. Do vậy khối lượng xử lý tăng lên so với hệ thống tập trung. I.3 Vấn đề trỏ thông tin Trong hệ phân tán, thời hạn truyền một thông điệp là hiệu số giữa thời điểm nhận và thời điểm truyền. Ta giả sử rằng, thời hạn đó đủ lớn so sánh với hệ tập trung, là địa lượng biến thiên và ở cặp máy này khác với ở cặp máy khác. Từ đó ta có hai hệ quả sau đây: 1) Ở một thời điểm cho trước, một bộ xử lý đang thực hiện trên một máy chỉ có thể biết được trạng thái gần đúng của các máy khác. 2) Trật tự nhận các thông điệp trên các máy nhận có thể không giống trật tự phát của chính các thông điệp đó. Các máy trên mạng có thể bị sự cố và các thông điệp có thể bị mất. Giải pháp cho vấn đề này là máy phát đánh số thứ tự tất cả các gói thông tin gửi đi kèm theo các số đó cho máy nhận. Nếu máy phát không đánh số thì máy nhận sẽ không xác đinh được thứ tự các gói tin. Ta có hệ quả ba là: 3) Hai máy giống nhau chứa thông tin hoàn toàn giống nhau lại không bao giờ giống nhau về mặt trạng thái. Từ những vấn đề nêu trên, ta rút ra các đặc tính tổng quát của hệ phân tán: i) Thời gian truyền thông điệp là một biến với giá trị khác nhau, giá trị này có thể rất lớn. ii) Tần suất xuất hiện các sự cố trong khi vận hành mạng lớn. iii) Việc truy cập tài nguyên, kích hoạt các tiến trình trong mạng không thể thực hiện bởi một thiết bị duy nhất, mà chức năng này phải được phân tán trên nhiều máy trên mạng. I.4 Vấn đề hệ thống nhiều bản sao Trong hệ phân tán, quá trình tổ chức, vận hành các hệ thống cho phép đăng ký từ xa, từng hệ thống cục bộ đều có lưu trữ một bản sao của tất cả các thông tin liên quan đang có ở tất cả các hệ thống cục bộ. Ưu điểm nổi bật của kiểu tổ chức này là: i) Dễ dàng thực hiện việc truy cập thông tin cần thiết cho các yêu cầu ngay tại hệ thống cục bộ của mình ii) Cho kết quả truy cập một cách nhanh chóng. Tuy nhiên, chỉ cho kết qủa tương đối chính xác và phụ thuộc rất nhiều vào phương pháp và thời hạn cập nhật thông tin trong các CSDL cục bộ. Sự tồn tại nhiều bản sao trong một hệ phân tán trên nhiều hệ thống cục bộ khác nhau có thể dẫn đến các hệ quả sau đây: i) Cập nhật thông tin diễn ra do đăng ký gần hay từ xa hoặc sự thay đổi thông tin cục bộ trên một hệ cục bộ nào đó cần phải được tiến hành cho tất cả các hệ thống cục bộ và không được phép bỏ sót hệ thống nào cả. trong khoản thời gian làm tươi, thông tin phải đảm bảo sao cho việc truy vẩn dữ liệu cho kết quả kịp thời hay đặt truy vấn trong trạng thái treo. ii) Cần phải tránh trường hợp các thao tác trên hai bản sao khác nhau nhưng chứa cùng một thông tin được truy cập bởi hai hay nhiều yêu cầu dẫn đến không gắn bó. Hai vấn đề vừa nêu trên xác định về các ràng buộc đối với vấn đề gắn bó dữ liệu. Để đảm bảo sự gắn bó này điều kiện đủ là phải bắt buộc tuân thủ trình tự nào đó cho các bản sao, các cập nhật thông tin. Biện pháp hàng đầu nhằm thực hiện việc loại trừ tương hỗ tổng quát trên tập hợp các bản sao khi đăng ký và thực hiện việc đăng ký trước khi trả lại bình thường. Biện pháp này có mặt hạn chế là không cho phép các chương trình đăng ký thực hiện song song. Tất cả các bản sao đều được khoá chặt trong lúc đăng ký. II. SỰ GẮN BÓ THÔNG TIN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN II.1 Các điều kiện giả định và thực tế Ta có một tập thông tin nào đó có thể được truy cập bởi một tập các tiến trình. Số lượng các thông tin có thể truy cập được và các tiến trình có nhu cầu thông tin là con số cố định. Hệ này phát triển rời rạc theo thời gian giữa các điểm quan sát, ta có thể nhận biết được trạng thái thực của chúng, có nghĩa là các đối tượng và ngữ cảnh thực hiện các tiến trình, hệ kiểu như vậy hoạt động với độ ổn định tuyệt vời. Các điều kiện giả định này so với hệ thực tế có những điểm khác nhau cơ bản sau đây: STT So sánh 1 - Các đối tượng và các tiến trình có thể - Được tạo lập và huỷ bỏ có tính chất động trong suốt quá trình tồn tại của hệ. 2 - Các đối tượng và các tiến trình có thể được phân tán trên các trạm khác nhau liên hệ với nhau qua hệ thống viễn thông. Do vậy, ta không thể xác định trạng thái thời điểm của hệ vì lí do độ trễ đường truyền giữa các trạm và tính không tương thích giữa các điểm quan sát trong trạm đó. 3 - Hệ thống viễn thông và các tiến trình là các đối tượng có thể xảy ra sự cố kỹ thuật. II.2 Tác động và giao dịch Các đối tượng khác nhau của hệ không phải là các đối tượng độc lập nhau, chúng quan hệ với nhau bởi tập hợp các quan hệ gọi là các ràng buộc toàn vẹn. Các ràng buộc này thể hiện sâu sắc các đặc tính riêng biệt của hệ. Trạng thái của hệ thoả mãn một tập các ràng buộc toàn vẹn gọi là trạng thái gắn bó. Các nhà thiết kế và vận hành hệ mong muốn rằng việc thực hiện các tiến trình phải duy trì cho được hệ trong trạng thái gắn bó. Để chính xác hoá đặc tính này, cần phải lưu ý là trạng thái của hệ chỉ được xác định ở mức quan sát cho trước. Ta quan tâm đến hai mức quan sát: STT Mức Giải thích 1 NSD - Tiến trình là một dãy thực hiện các giao dịch Giao dịch đó là chương trình duy nhất được thực hiện từ một trạng thái gắn bó dẫn hệ đến một trạng thái gắn bó khác. 2 Hệ thống - Mỗi giao dịch được cấu tạo từ nột dãy các tác động được thể hiện như sau. Nếu 2 tác động A và B thuộc hai giao dịch khác nhau được thực hiện bởi hai tiến trình thì hiệu ứng tổng quát của chúng sẽ là hiệu ứng của dãy (A;B) hoặc là (B;A) Cho một tập hợp giao dịch M={T1,T2…,Tn} lần lượt được thực hiện bởi các tiến trình độc lập p1,p2…,pn. việc thực hiện tuần tự có nghĩa là thực hiện tất cả các giao dịch của M theo kiểu nối đuôi nhau và tuân thủ một trật tự nào đó. Sự gắn bó của hệ được bảo toàn. Ở mức hệ thống, ta có thể nói rằng các tác động là phần tử nhỏ nhất không thể chia cắt được nữa. Nếu vì lý do hiệu quả, nhiều giao dịch được thực hiện song song thì sự gắn bó không còn đảm bảo được nữa. Một yêu cầu khác nữa rất quan trọng là trong quá trình thực hiện hệ phải đảm bảo cho các tác động không bị ngắt quãng. II.3 Triển khai giao dịch tôn trọng sự gắn bó Cho một tập hợp giao dịch M={T1,T2…,Tn}. Một trật tự hóa của tập hợp các tác động thành phần sẽ tương ứng với việc thực hiện hoàn toàn các giao dịch. Việc thu được một trật tự hóa gắn bó chỉ có thể thành công khi áp dụng các ràng buộc trên trật tự thực hiện các tác động. Nguyên lý của phương pháp là ở chỗ làm chậm một tác động nào đó cho đến thời điểm mà sự thực hiện của nó không còn có nguy cơ phá hủy sự gắn bó của trật tự hóa. Để đảm bảo các giao dịch trên tôn trọng sự gắn bó thông tin thì người ta đưa ra các phương pháp, cơ chế để đảm bảo khi giao dịch vẫn có sự gắn bó thông tin toàn vẹn dữ liệu trên cơ sở dữ liệu phân tán là: Cơ chế then cài. Then cài loại trừ tương hỗ. Then cài lựa chọn đối tượng. Giao dịch hai pha. Bây giờ ta tưởng tượng rằng các đối tượng được phân tán trên nhiều trạm khác nhau và được nối với nhau thông qua hệ thống viễn thông và các tiến trình diễn ra trên các trạm khác nhau. Hệ thống viễn thông cho phép các tiến trình trên các trạm khác nhau có thể trao đổi các thông điệp với nhau. Ta giả định rằng các tiến trình và các phương tiện truyền thông là các đối tượng có thể rơi vào sự cố. Một hệ quản lý tập hợp thông tin phân tán bao gồm: STT Cơ chế 1 - Cơ chế cho phép sắp xếp một cách tổng quát các tác động của cùng một giao dịch, ngay cả khi các tác động này diễn ra trên các trạm khác nhau. 2 - Cơ chế điều khiển các tranh chấp truy cập cục bộ vào các đối tượng đảm bảo tôn trọng tính toàn vẹn của các đối tượng truy cập cục bộ này. 3 - Cơ chế có khả năng xử lý các bế tắc và thiếu thốn vô hạn, hậu quả của việc hủy bỏ các giao dịch. 4 - Cơ chế phục hồi các giao dịch đã hủy bỏ hay xử lý các sự cố. Cơ chế xử lý sự cố STT Phải thực hiện 1 Giao dịch T bắt buộc phải thực hiện một cách trọn vẹn 2 Nếu có sự cố xảy ra thì phải quay lại điểm xuất phát. Muốn thực hiện những điều vừa nêu ở trên, người ta đòi hỏi giao dịch phải có các đặc tính toàn vẹn như sau: STT Phải thực hiện 1 - Nếu một tiến trình bị sự cố trước khi kết thúc T nhưng lại sau các thao tác thay đổi cần thiết của T, trạng thái của hệ là gắn bó. 2 - Nếu một tiến trình bị sự cố trước khi diễn ra các thay đổi của T, trạng thái của hệ là gắn bó. 3 - Nếu một tiến trình bị sự cố giữa các thay đổi của T, trạng thái của hệ là không gắn bó. Nếu dữ liệu được phân tán trên nhiều server, để bảo đảm dữ liệu sẽ được ghi lên đúng đắn lên mọi cơ sở dữ liệu, đòi hỏi phải có các cơ chế bảo vệ dữ liệu. Ví dụ như việc cập nhật bảng cân đối tài khoản khách hàng ở ba cơ sở dữ liệu khác nhau. Nếu có sự cố kết nối xảy ra trong thời gian ghi giao dịch, cơ sở dữ liệu sẽ mất tính đồng bộ. Xử lý giao dịch khắc phục tình trạng này bằng cách giám sát những thay đổi tác động lên các cơ sở dữ liệu liên quan nhằm bảo đảm toàn vẹn dữ liệu một khi có sự cố. II.4 Quản lý gắn bó các giao dịch Bây giờ ta hãy xem xét một hệ, trong đó các đối tượng được phân tán trên nhiều trạm, không có bản sao mỗi đối tượng chỉ tồn tại có một bản duy nhất. Một giao dịch Tj có thể tham chiếu đến các đối tượng nằm trên các trạm khác nhau và do vậy gồm nhiều tác động thực hiện trên nhiều trạm. Như vậy ta phải xác định trên một trạm Si một tiến trình Pji với nhiệm vụ thực hiện các tác động giao dịch Tj trên Si, các tác động được thực hiện trên các trạm khác nhau có thể tiến hành theo kiểu song song. Các phương pháp để quản lý gắn bó các giao dịch như: Phương pháp dự phòng để chống bế tắc, phương pháp dựa vào việc hạn chế các khả năng diễn ra bằng cách phát hiện bế tắc có tính chất động, điều đó dẫn đến hủy bỏ các giao dịch. III. CÁC THUẬT TOÁN ĐẢM BẢO SỰ GẮN BÓ DỮ LIỆU TRONG CÁC CƠ SỞ DỮ LIỆU PHÂN TÁN III.1 Thuật toán cung cấp: Vì sự ổn định và hiệu quả mà ta phải phân tán chức năng cung cấp trên nhiều trạm khác nhau. Sự hoạt động gắng bó với nhau giữa các chương trình cung cấp là rất cần thiết để bảo đảm cho hoạt động cung cấp được hoàn toàn chính xác. Một sự hoạt động gắn bó dữ liệu của các chương trình cung cấp phân tán quản lý trên cùng một tập hợp các tài nguyên chỉ đạt được nếu tuân thủ các nguyên tắc sau: i) Các bộ cung cấp bắt buộc phải thực hiện cùng một giải thuật ii) Các bộ cung cấp đều nhận tất cả các thông điệp phát đi từ các tiến trình iii) Các thông điệp phải được xử lý cùng một trật tự như nhau trong các chương trình cung cấp. Trật tự duy nhất trên tập hợp các thông điệp của hệ, và trật tự được thực hiện thông qua việt hợp lực giữa các tiến trình cung cấp hay tiến trình phát thông điệp III.2 Sắp xếp kiểu đóng dấu 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ồ Logíc cục bộ của chính trạm. III.2.1 Nguyên lý: Tập hợp tất cả các yêu cầu cập nhật được sắp xếp theo cùng một kiểu trên tất cả các trạm nhờ cơ chế dấu. Theo đó mỗi một yêu cầu được phát đi cho tập hợp các trạm, trên mỗi trạm tồn tại một tiến trình server đảm nhận nhiệm vụ tiếp nhận các yêu cầu theo một trật tự về dấu. Điều đó cho phép có một sự gắn bó yếu giữa các bản sao. III.2.2. Triển khi hệ số ổn định: Các giao dịch cần xét ở đây là các khả năng đọc, ghi hay cập nhật. Cập nhật được xác định như một dãy các thao tác đọc rồi ghi, thao tác kiểm tra - đọc tức thì trạng thái hiện hành của bản sao. Mỗi một server tiếp nhận các yêu cầu ghi đến các trạm cục bộ ở thời điểm cho trước. nó tiếp nhận các yêu cầu và tính toán trên cơ sở dấu theo tiêu chí lâu nhất. Điều đó dẫn đến chúng ta cần phải chú ý ở hai trường hợp: Trường hợp 1: Tập hợp các yêu cầu ghi khi chờ chứa các yêu cầu từ tất cả các trạm khác. Trong trường hợp này các yêu cầu đi qua, nếu chúng tồn tại, là mới hơn so với các yêu cầu đã đi qua. Nói cách khác, yêu cầu lâu nhất chính là yêu cầu đang chờ. Trường hợp 2: Tồn tại các trạm mà không có bất kỳ yêu cầu nào được truyền đến. Ta giải quyết bằng cách truyền cho tất cả các trạm một thông điệp yêu cầu và bắt buộc phải xác nhận. Do vậy, sau một khoảng thời gian theo giả thiết về độ ổn định ta sẽ xác nhận: hoặc là các yêu cầu đi qua, hoặc là trả lời các thông điệp yêu cầu. Lúc này, ta nói được các thông điệp đến từ tất cả các trạm. III.2.3. Các hành vi bên ngoài chế độ bình thường: Có hai vấn đề mở rộng hơn đối với thuật toán này là cho phép rút ra hay chèn vào tuỳ ý một trạm nào đó. Điều đó, dẫn đến hai vấn đề sau chúng ta cần phải tôn trọng: Vấn đề 1: Việc đột nhiên biến mất một trạm nào đó pahỉ được các trạm khác nhận biết một cách tự động. Vấn đề 2: Việc phát đi một thông điệp là phép toán không thể chia cắt đi được nữa. Đó là một thông điệp hoặc là tất cả các trạm đều phải nhận được hoặc là không một trạm nào nhận được cả. Vì vậy, nếu điều kiện đầu tiên được khống chế thì điều kiện thứ hai mới được đảm bảo. III.3. Thuật toán đảm bảo sự gắn bó yếu nhờ bộ tuần tự tuần hoàn: III.3.1. Nguyên lý: Trước khi phát một yêu cầu một trạm nào đó cần phải kết hợp với nó một số thứ tự được cấp từ bộ tuần tự tuần hoàn. Các yêu cầu được tiếp nhận tại mỗ trạm theo cùng một trật tự thống nhất. Điều đó giúp ta có được một sự gắn bó yếu. Điều chúng ta cần quan tâm ở đây là cơ chế phân phối các số dựa trên nền tảng tổ chức các trạm theo kiểu vòng tròn ảo. III.3.2. Triển khai hệ số ổn định: Bộ tuần tự cung cấp cho mỗi yêu cầu số sắp tới còn chưa dùng, giả sử dó là T. Khi đến phiên của trạm nhận bộ tuần tự, nó yêu cầu một số lượng n số đúng bằng số lượng các yêu cầu cập nhật đang chờ trên trạm này. Các số này là: T, T + 1, T + 2, ….T + n – 1 Nó tiếp tục chuyển bộ tuần tự cho trạm kế tiếp liền sau nó và số sắp tới chưa dùng đến T + n. Khi một trạm đã có sự cố, nó phát yêu cầu cập nhật cùng vơi số này. Trên mỗi trạm, các cập nhật được thực hiện bằng cách tiếp nhận các yêu cầu cùng các số liên tiếp nhau( theo một trật tự). Để xác định yêu cầu sắp đến cần phải xử lý , mỗi một trạm duy trì một biến số V được phối hợp với yêu cầu xử lý cuối cùng. Các yêu cầu mang các số lớn hơn V + 1 được lưu trữ trong khi chờ xử lý yêu cầu V + 1. III.3.3. Các hành vi ngoài chế độ bình thường: Hiện tại. người ta đã chế tạo thành công và đưa vào sử dụng một cách ổn đọnh trong mạng một số giao thức cho phép tái sinh bộ tuần tự khi bộ này bị mất và đặt cấu hình vòng tròn ảo trở lại theo kiểu tự động. Các giao thức hoạt động trong điều kiện giả định là mạng viễn thông cho phép phát hiện các sự cố của một trạm và cần phải được bổ khuyết một cách đầy đủ nhằm duy trì trật tự toàn phần cần thiết cho việc gắn bó: Vấn đề 1: Việc tái sinh bộ tuần tự cần phải tiến hành song song với việc tính toán số sắp có để dùng. Vấn đề 2: Khi phát hiện có một trạm bị sự cố, ta cần phải xác định các số mà trạm này đã lấy và các số còn chưa sử dụng, rồi gửi các yêu cầu có mang các số này Vấn đề 3: Việc cho một trạm hội nhập vào lại trong vòng tròn cần phải tiến hành song song với việc cập nhật lại các bản sao của nó. Sử dụng các số liên tục cho phép tránh được hiện tượng một vài cập nhật bị mất và các lần mất mà không được phát hiện. Việc triển khai bộ tuần tự tuần hoàn cũng làm cho ta gặp phải một số khó khăn khác. III.3.4. Thuật toán đảm bảo sự gắn bó mạnh: III.3.4.1. Nguyên lý: Tập hợp bao gồm các trạm được tổ chức theo kiểu vòng tròn ảo. các cập nhật được thực hiện theo hai thì: 1. Thống nhất giữa các trạm. 2. Thực hiện cập nhật. Do vậy, thuật toán này đảm bảo sự gắn bó mạnh. Nếu có nhiều yêu cầu cập nhật diễn ra đồng thời thì ta phải có quy tắc để quyết định yêu cầu nào được tiếp nhận và thỏa mãn. Nhằm phục vụ cho ý tưởng đó, ta thường hay sử dụng dấu phối hợp cho mỗi cập nhật và ta xử lý yêu cầu có thời gian lâu nhất. III.3.4.2. Triển khai hệ số ổn định: Trạng thái có thể cảu mỗi trạm là: STT Trạng thái Giải thích 1 Nghỉ ngơi Trạm không thực hiện cập nhật nào cả 2 Hoạt động Trạm đãnhận một yêu cầu cập nhật cục bộ mà yêu cầu này đã được truyền cho trạm khác để kiểm tra. 3 Thụ động Trạm đồng ý cho một cập nhật và chờ trật tự tương ứng. 4 Cập nhật Trạng đang trong tình trạng chuyển của cập nhật , trong khi đó tất cả các yêu cầu khác truyền đến đều được lưu trữ. Chúng sẽ được xử lý khi quay về một trong các trạng thái khác. Lúc khởi sự, tất cả các trạm đều ở trong trạng thái nghỉ ngơi. Trạm khởi sự việc cập nhật , đầu tiên cần phải gửi một yêu cầu cho phép cập nhật, nó chỉ làm được việc đó trong trạng thái nghỉ ngơi. Lúc này nó được nhận dấu và được gửi vào vòng tròn trạm khởi sự chuyển từ trạng thái nghỉ ngơi sang trạng thái hoạt động. Nếu chỉ có một yêu cầu duy nhất được đưa vào vòng tròn, nó đi qua tất cả các trạm để chuyển các trạm từ nghỉ ngơi sang thụ động. khi đó, nó trở về nơi khởi sự thì việc thống nhất coi như hoàn tất. việc cập nhật nói riêng lúc này được gửi đi và mỗi trạm sau khi thực hiện trở về trạng thái nghỉ ngơi. Nếu có nhiều yêu cầu đưa ra đồng thời trong vòng tròn, thì tình hình đó dễ dàng diễn ra xung đột. lúc này, ta phải chọn một yêu cầu có thời gian dấu lâu nhất. Để tiến hành công việc đó, ta nêu bật vai trò của bộ chắn đường cho các trạm khởi sự. Một trạm nào đó trong trạng thái nghỉ ngơi hay thụ động phải chuyển toàn bộ yêu cầu đã đến nó, một trạm trong trạng thái hoạt động chỉ phải chuyển các yêu cầu có thời gian lâu hơn các yêu cầu mà chính nó phát đi, các yêu cầu khác đều bị dừng lại và được lưu trữ. Các yêu cầu bị lưu trữ lại sẽ được gửi tiếp vào vòng tròn, khi trạm lưu trữ chúng hoàn thành công việc cập nhật riêng của mình. III.3.4.3. Hành vi ngoài chế độ bình thường: Các giao thức đặt lại cấu hình vòng tròn theo kiểu tự động được sử dụng nhằm rút ra hay cho vào tùy ý một số trạm nhất định. Các sự cố kỹ thuật là rất khó khăn phát hiện các chiến lược mà ở dó các yêu cầu không được ghi lại khắp nơi trong mạng. III.4 Phân tán biểu hiện trạng thái và chức năng cung cấp Phân tán biểu hiện trạng thái và chức năng cung cấp, có các giải pháp có thể: i) Duy trì tại mỗi trạm một bản sao trạng thái tài nguyên tổng quát ii) Phân tán biểu hiện trang thái trên các trạm, mỗi một trạm chỉ có trạng thái các tài nguyên cục bộ của mình. Các quyết định được đưa ra trên các trạm khác nhau cần phải được phối hợp theo kiểu sao cho dữ liệu của việc cung cấp phải được gắn bó với nhau iii) Nhóm sắp xếp nhằm bảo đảm cho tất cả các yêu cầu tài nguyên xuất phát từ các tiến trình đến được các bộ cung cấp khác nhau theo một trật tự duy nhất được cố định từ trước. Nội dung của các bản sao trên các trạm của hệ có thể phản ảnh như sau: - Tập hợp tất cả các tài nguyên còn chưa được cung cấp - Tập hợp các tài nguyên đã cung cấp - Đối tượng đang chiếm giữ tài nguyên - Kiểu sử dụng - Tập hợp các yêu cầu không được thỏa mãn - Tập hợp các thông điệp dành cho trường hợp đã được sử dụng - Tập hợp các thông điệp dành cho trường hợp thất bại Ngày nay, trong các ứng dụng lớn như thương mại điện tử, giáo dục điện tử,…, bản sao dữ liệu được sử dụng để tăng tính sẵn sàng của dữ liệu. Tuy nhiên, lợi ích sẵn sàng của dữ liệu này chỉ có được khi phải trả giá bằng những thuật toán phức tạp để ẩn đi tính phức tạp trong việc bảo trì nhiều bản sao của đối tượng. Sự khó khăn nằm ở việc phải đảm bảo gắn bó cho các bản sao của đối tượng để tránh bế tắc khi vận hành hệ thống. Các thuật toán giải quyết những vấn đề này được gọi là các thuật toán điều khiển bản sao. Việc quản lý nhiều bản sao của cùng một đối tượng thông tin đang được các nhà chuyên môn tin học quan tâm nghiên cứu ngay trong giai đoạn phân tích, thiết kế và xây dựng hệ điều hành. Ngoài ra, đây còn là một trong những vấn đề có tính chất cơ sở cho các ứng dụng phức tạp. Quản lý nhiều bản sao là giải pháp kỹ thuật bao gồm tập hợp các thông tin được nhân bản từ một đối tượng thông tin và các chương trình quản lý chúng trong môi trường phân tán. Vấn đề truy cập và xử lý thông tin phân tán nói chung, quản lý nhiều bản sao nói riêng được nghiên cứu trong hàng loạt các công trình của Herman, Ellis, Wilms và Le Lann. Nội dung quản lý nhiều bản sao là các giải pháp cho phép tự động hóa các công việc: Kiểm tra tính hợp lệ của việc truy cập thông tin Khôi phục thông tin Cập nhật thông tin An toàn dữ liệu cho các bản sao Sử dụng các bộ nhớ, đĩa Chuyển các bản loại bỏ vào vùng có thể khôi phục Trong các nội dung nêu trên, vấn đề quan trọng nhất là cập nhật tự động thông tin vào các bản sao./. B. BÀI TẬP I. ĐẶT VẤN ĐỀ I.1 Giới thiệu bài toán Trong một hệ thống phân tán giả định có độ ổn định tuyệt vời, ta muốn duy trì một sự gắn bó mạnh giữa các bản sao của một đối tượng được định vị trên các trạm khác nhau. Thuật toán dựa trên các nguyên lý sau đây: Trước khi thực hiện cập nhật, một trạm nào đó cần phải yêu cầu và thống nhất với các trạm khác. Khi đã có được sự thống nhất, thì trạm này tiến hành công việc cập nhật; điều này phải tiến hành trên tất cả các bản sao; đối tượng không thể truy cập chừng nào các bản sao còn chưa cập nhật hết. Các xung đột giữa các trạm được giải quyết bằng một trật tự có hệ số ưu tiên giữa các trạm, được cố định một lần lúc khởi sự cho toàn bộ. Hỏi có bao nhiêu trạng thái khác nhau cần xem xét cho mỗi bản sao. Hãy trình bày sơ đồ hoạt động của thuật toán (đồ thị phát triển). Hãy đánh giá bằng hàm của số lượng bản sao, số lượng các thông điệp cần thiết để thực hiện một thông điệp. Ta phải sửa đổi thuật toán như thế nào để chịu đựng được sự cố trên một trạm (giả sử hệ viễn thông hoạt động tốt). I.2 Cơ sở lý thuyết để giải quyết bài toán Khi nghiên cứu về hệ phân tán chúng ta thấy rằng, thời gian truy cập trung bình vào thông tin trong hệ phân tán có thể được rút ngắn, trong một số trường hợp, nhờ vào phương pháp nhân nhiều bản và được gọi là nhiều bản sao của một đối tượng thông tin. Ta cần phân biệt hai trường hợp khác nhau được thể hiện sau đây: - Trường hợp 1: Bộ nhớ cục bộ (e) Bộ xử lý a) Đa xử lý với bộ nhớ chung: Bộ nhớ chung (e) Hình 6. Đa xử lý với bộ nhớ chung Mỗi một bộ xử lý đều có bộ nhớ cục bộ của mình, hay còn gọi là cache, được dùng để sao chép lại các vùng đang làm việc của bộ nhớ chung. Một chương trình thể hiện thuật toán thay thế đảm nhận nhiệm vụ làm mới các bộ nhớ cục bộ. Trường hợp có nhiều bộ xử lý muốn truy cập vào cùng một đối tượng, ta sử dụng như là sự tham chiếu đến phiên bản của đối tượng tìm thấy trong bộ nhớ chung. Bộ xử lý Bộ nhớ cục bộ (e) Bộ nhớ chung (e) Hệ thống viễn thông Máy client Máy server b) Hệ truy cập từ xa thông qua một máy server duy nhất: Hình 7. Hệ truy cập từ xa thông qua máy server Trong trường hợp này, một đối tượng được đưa vào trên một trạm xác định và được quản lý bởi một server cục bộ trên trạm này. Khi một tiến trình ở xa muốn sử dụng đối tượng, nó phải bắt đầu bằng yêu cầu server cho một bản sao thông qua hệ thống viễn thông. Sau khi sử dụng xong, tiến trình phải gửi lại cho server một phiên bản đã được sửa đổi của đối tượng. Các trường hợp thể hiện trong hình 2.1 và 2.2 xét theo chức năng là giống nhau. Đó là trường hợp một bản duy nhất của đối tượng là một đặc quyền. - Trường hợp 2: Hệ thống viễn thông Tính cân đối giữa các người sử dụng tài nguyên thông tin của mạng. Hình 8. Hệ thống đối xứng Tại đây, tất cả các bản đóng vai trò đối xứng. Công việc được tiến hành theo kiểu này cho phép rút ngắn thời gian truy cập, nếu số lần truy cập để đọc lớn hơn số lần truy cập để cập nhật và vì lý do thuận lợi sử dụng theo nghĩa có sẵn để dùng. Tình hình nêu trên đặt ra cho chúng ta nhiều vấn đề cần phải giải quyết. Đó chính là các lần cập nhật thông tin hay nói một cách tổng quát là cập nhật các bản sao. Từ đó, ta rút ra các đặc điểm quan trọng sau đây : 1) Khi chỉ tồn tại một bản tập trung đặc quyền, ta có thể đặt ra rằng việc thay đổi đối tượng thực hiện trên một trong các bản sao sẽ được sao lại ngay lập tức vào bản chính. Đó chính là trường hợp ghi tức thời và các cập nhập đều gắn bó. Với các phương pháp ghi khác, ngược lại, các thay đổi tương ứng của một bản sao đối tượng cục bộ chỉ được sao lại trên bản chính khi thuật toán thay thế được thực hiện nhằm cung cấp lại các bản ghi bị chiếm bởi bản sao cục bộ đó. 2) Khi không tồn tại bản đặc quyền, ta có thể gặp các trường hợp không gắn bó thông tin. Trường hợp thứ hai làm phát sinh hai yêu cầu mới: a. Toàn bộ giao dịch thay đổi bản sao của đối tượng cần phải chép lại càng sớm càng tốt thay đổi đó trên tất cả các bản sao khác. Trong khi thực hiện giao dịch, không có bất kỳ sao chép nào khác được thực hiện. Sau khi thực hiện xong, tất cả các bản sao hoàn toàn giống nhau. b. Việc cập nhật tức thời (theo hệ tập trung) của tất cả các bản sao là không cần thiết. Trong tất cả các trường hợp, một giao dịch tham chiếu trạng thái một đối tượng thực hiện xuất phát từ một trạm trên bản cục bộ cần phải cung cấp: - Hoặc là một giá trị cập nhật của tất cả các thay đổi diễn ra trước tham chiếu. - Hoặc là một giá trị đã cũ, nhưng lại là giá trị đã được cập nhật ở thời điểm trước đó. Sự tham chiếu không bao giờ phải cung cấp một giá trị xuất phát từ việc thực hiện từng phần của một giao dịch. II. GIẢI QUYẾT VẤN ĐỀ II.1 Các trạng thái khác nhau cần xem xét cho mỗi bản sao Các trạng thái có thể xảy ra trên mỗi bản sao như sau: Stt Trạng thái Giải thích 1 Nghỉ ngơi Trạm không thực hiện cập nhật nào cả 2 Hoạt động Trạm đã nhận một yêu cầu cập nhật cục bộ mà yêu cầu này đã được truyền cho các trạm khác để kiểm tra 3 Thụ động Trạm đồng ý cho một cập nhật và chờ trật tự tương ứng 4 Cập nhật Trạm đang trong tình trạng chuyển của cập nhật, trong khi đó tất cả các yêu cầu khác truyền đến đều được lưu trữ. Chúng sẽ được xử lý khi quay về một trong các trạng thái khác. II.2 Sơ đồ hoạt động của thuật toán Các trạm được tổ chức theo kiểu vòng tròn ảo. Trước khi thực hiện cập nhật, một trạm nào đó cần phải yêu cầu và thống nhất với các trạm khác. Sau khi đã có được sự thống nhất, thì trạm này tiến hành công việc cập nhật. Sơ đồ hoạt động của thuật toán: 1 – Nghỉ ngơi 2 – Nghỉ ngơi 3– Nghỉ ngơi 4– Nghỉ ngơi Yêu cầu Lựa chọn yêu cầu có thời gian dấu dài nhất nếu có nhiều yêu cầu được đưa ra Nghỉ ngơi Hoạt động Thụ động Cập nhật Hình 10. Sơ đồ hoạt động của thuật toán Lúc khởi sự, tất cả các trạm đều ở trong trạng thái nghỉ ngơi. Trạm khởi sự việc cập nhật, đầu tiên cần phải gửi một yêu cầu cho phép cập nhật, nó chỉ làm được việc đó trong trạng thái nghỉ ngơi. Lúc này nó được nhận dấu và được gửi vào vòng tròn trạm khởi sự chuyển từ trạng thái nghỉ ngơi sang trạng thái hoạt động. Nếu chỉ có một yêu cầu duy nhất được đưa vào vòng tròn, nó đi qua tất cả các trạm để chuyển các trạm từ nghỉ ngơi sang thụ động. khi đó, nó trở về nơi khởi sự thì việc thống nhất coi như hoàn tất. việc cập nhật nói riêng lúc này được gửi đi và mỗi trạm sau khi thực hiện trở về trạng thái nghỉ ngơi. Nếu có nhiều yêu cầu đưa ra đồng thời trong vòng tròn, thì tình hình đó dễ dàng diễn ra xung đột. lúc này, ta phải chọn một yêu cầu có thời gian dấu lâu nhất. Để tiến hành công việc đó, ta nêu bật vai trò của bộ chắn đường cho các trạm khởi sự. Một trạm nào đó trong trạng thái nghỉ ngơi hay thụ động phải chuyển toàn bộ yêu cầu đã đến nó, một trạm trong trạng thái hoạt động chỉ phải chuyển các yêu cầu có thời gian lâu hơn các yêu cầu mà chính nó phát đi, các yêu cầu khác đều bị dừng lại và được lưu trữ. Các yêu cầu bị lưu trữ lại sẽ được gửi tiếp vào vòng tròn, khi trạm lưu trữ chúng hoàn thành công việc cập nhật riêng của mình. Hành vi ngoài chế độ bình thường: Các giao thức đặt lại cấu hình vòng tròn theo kiểu tự động được sử dụng nhằm rút ra hay cho vào tùy ý một số trạm nhất định. Các sự cố kỹ thuật là rất khó khăn phát hiện các chiến lược mà ở dó các yêu cầu không được ghi lại khắp nơi trong mạng. II.3 Đánh giá hàm số lượng các bản sao, số lượng thông điệp cần thiết để thực hiện một cập nhật Sơ đồ mô tả cơ cấu tổ chức của hệ thống nhiều bản sao và việc cập nhật các bản sao được thể hiện trong hình 12 sau đây: Hình 11. Sơ đồ mô tả hệ thống nhiều bản sao bij với i = 1..n, j = 1..m, trong đó i chỉ server, j chỉ bản sao, n là số lượng server được mắc nối trong mạng, m là số lượng các đối tượng dữ liệu tk với k = 1..q, trong đó k là trạm, q là số trạm được mắc nối Các ràng buộc trên các bản sao: Trên bản sao của một đối tượng: Nếu ta có n bản sao b1, b2,…, bn của đối tượng b, một trong các ràng buộc toàn vẹn là: b1 = b2 = ... = bn Trên các bản sao của toàn bộ các đối tượng: b11= b21 =... = bn1 b12 = b22 = ... = bn2 ... b1m = b2m = ... = bnm Gọi M là cực đại của các cập nhật có thể diễn ra đồng thời, thì M có thể tính theo công thức M = n x m. II.4 Xử lý sự cố trên một trạm Nếu dữ liệu được phân tán trên nhiều server, để bảo đảm dữ liệu sẽ được ghi lên đúng đắn lên mọi cơ sở dữ liệu, đòi hỏi phải có các cơ chế bảo vệ dữ liệu. Ví dụ như việc cập nhật bảng cân đối tài khoản khách hàng ở ba cơ sở dữ liệu khác nhau. Nếu c ó sự cố kết nối xảy ra trong thời gian ghi giao dịch, cơ sở dữ liệu sẽ mất tính đồng bộ. Xử lý giao dịch khắc phục tình trạng này bằng cách giám sát những thay đổi tác động lên các cơ sở dữ liệu liên quan nhằm bảo đảm toàn vẹn dữ liệu một khi có sự cố. Nếu một tiến trình p bị sự cố trong lúc thực hiện một giao dịch T thì trạng thái của hệ xuất phát từ việc thực hiện từng phần đó chắc chắc sẽ không còn gắn bó. Một cơ chế cho phép duy trì gắn bó trong môi trường phân tán có sự cố phải là: 1) Giao dịch T bắt buộc phải được thực hiện một cách trọn vẹn 2) Nếu có sự cố diễn ra thì bắt buộc nó phải quay trở lại điểm xuất phát. Muốn thế đòi hỏi giao dịch phải có đặc tính toàn vẹn như sau: - Nếu một tiến trình bị sự cố trước khi kết thúc T nhưng lại sau các thao tác thay đổi cần thiết của T, trạng thái của hệ là gắn bó Sau khi cập nhật (thay đổi) Trước khi cập nhật (thay đổi) Gắn bó Không Gắn bó 1 2 3 Hình 12. Ba giai đoạn của một giao dịch - Nếu một tiến trình bị sự cố trước khi diễn ra các thay đổi của T, trạng thái của hệ là gắn bó. - Nếu một tiến trình bị sự cố giữa các thay đổi T, trạng thái của hệ là không gắn bó. Các mô hình và giải thuật nghiên cứu phải đảm bảo các đặc tính toàn vẹn dữ liệu của hệ và tuân thủ theo các giai đoạn thể hiện trong hình vẽ 12. Căn cứ vào nội dung thông tin cần phải đảm bảo sự gắn bó mà ta có thể chọn các thuật toán nhằm đảm bảo tính toàn vẹn dữ liệu. C. KẾT LUẬN Trong quá trình xây dựng các phần mềm cho hệ phân tán hỗ trợ các ứng dụng lớn như thương mại điện tử, chính phủ điện tử,... vấn đề cập nhật thông tin dùng chung trong các bản sao của cùng một đối tượng là một trong những vấn đề quan trọng. Nó không chỉ đảm bảo hệ thống hoạt động với tốc độ bình quân chấp nhận được, ổn định, tin cậy mà quan trọng hơn cả là phải đảm bảo tính gắn bó của dữ liệu trong các bản sao. Mô hình hệ thống quản lý nhiều bản sao giống nhau trên môi trường phân tán và các giải thuật được nghiên cứu đã đáp ứng các yêu cầu của một hệ thống phức tạp với lượng thông tin lớn cần phải xử lý và thể hiện ở các mặt sau đây: · Tự động hóa cập nhật các bản sao · Phát triển giải thuật nhiều bản sao trong môi trường phân tán hiện đại · Làm phong phú khả năng ứng dụng các tác tử di động. · Triển khai kỹ thuật đánh dấu bản điều khiển trong quản lý nhiều bản sao · Bổ sung lý thuyết cập nhật nhiều bản sao Bài tiểu luận đã thể hiện cô đọng bằng những sơ đồ giải thuật và mô hình. TÀI LIỆU THAM KHẢO Hệ phân tán – TS. Lê Văn Sơn, Nhà xuất bản Đại học quốc gia TP. Hồ Chí Minh. Nguyên lý các hệ cơ sở dữ liệu – Sách dịch Jeffery Ullman – Nhà xuất bản thống kê. Distributed Systems (Concepts and Design) – George Coulouris, Jean Dollimore & Tim Kindberg. Tổng kết các công cụ xây dựng HPT: Distributed systems engineering: Introduction for distributed systems: Thuật toán wait-die system: Những example về distributed systems:

Các file đính kèm theo tài liệu này:

  • docLập trình mạng nâng cao.doc