CHƯƠNG 1. Khái niệm hệ phân tán Hệ phân tán là tập các thiết bị tính toán riêng rẽ có thể giao tiếp với nhau. Đây là một định nghĩa hết sức tổng quát bao trùm một phạm vi rộng các hệ thống máy tính hiện đại ngày nay, từ chíp VLSI đến các bộ đa xử lý, các mạng cục bộ và Internet. Mục đích của xử lý song song là phân bổ một nhiệm vụ lớn cho tất cả các bộ xử lý thực hiện.
Trong khi với hệ phân tán, mỗi bộ xử lý nói chung có chương trình làm việc riêng bán độc lập, nhưng vì các lý do khác nhau như chia sẻ tài nguyên, tính sẵn sàng, khả năng kháng lỗi, nên các bộ xử lý cần phối hợp hành động với nhau. Hiện nay, hệ phân tán có ở khắp nơi, trong các doanh nghiệp, học viện, chính phủ, quốc phòng,.Điển hình, hệ phân tán cung cấp những phương tiện để chia sẻ các tài nguyên như các máy in màu, máy quét, và chia sẻ dữ liệu. Tính toán ngang hàng cũng là một mô hình hệ phân tán, chúng ngày càng càng trở nên phổ biến trong việc cung cấp các tài nguyên và dịch vụ tính toán. Các hệ thống phân tán tham vọng hơn cố gắng cải tiến hiệu năng bằng cách kết hợp giải quyết các bài toán con một cách song song, và tăng tính sẵn sàng trong trường hợp một số thành phần của hệ thống bị lỗi.
Vai trò hệ phân tán Với nhiều ứng dụng nổi bật trong thực tiễn, hệ phân tán đang ngày càng trở nên phổ biến, bởi nó nắm giữ những vai trò quan trọng sau: Trao đổi thông tin: Các hệ phân tán cung cấp khả năng chia sẻ thông tin rộng rãi. Các chi nhánh khác nhau của một ngân hàng tại các vị trí địa lý rất xa nhau có thể trao đổi, chia sẽ thông tin cho nhau. Hệ phân tán cũng cung cấp khả năng chia sẻ thông tin giữa các thiết bị hỗn tạp, một máy tính có thể giao tiếp các thiết bị viễn thông khác như điện thoại cố định, di động, các PDA, … Chia sẻ tài nguyên: Các hệ phân tán cung cấp khả năng chia sẻ tài nguyên cả phần cứng lẫn phần mềm, giúp giảm chi phí hệ thống. Các máy tính kết nối mạng có thể dùng chung máy in, máy quét ảnh, có thể chia sẻ các tệp dữ liệu, các tệp chương trình.
Nâng cao độ tin cậy, tính sẵn sàng thông qua sao lặp: Bằng việc sao lặp, nhân bản, các hệ phân tán cho độ tin cậy và tính sẵn sàng cao. Nếu toàn bộ dữ liệu của một chi nhánh ngân hàng lưu trong máy tính bị mất do sự cố nào đó, người ta có thể khôi phục lại bằng cách sao phần dữ liệu nhân bản đã được lưu tại một nơi khác trên hệ thống máy tính. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Nâng cao hiệu suất thông qua song song hóa: Thông qua song song hóa, các thành phần trong hệ phân tán có thể chia sẻ công việc, thực hiện đồng thời công việc chung, làm tăng hiệu suất hoạt động hệ thống. Đơn giản thiết kế thông qua chuyên dụng hóa: Hệ phân tán làm đơn giản việc thiết kế các hệ thống phức tạp.
Người ta có thể phân một hệ thống phức tạp thành các bộ phận con chuyên dụng thực hiện một số tác vụ chuyên biệt nào đó và hợp tác với nhau để giải quyết nhiệm vụ lớn. Đặc trưng hệ phân tán Một hệ phân tán có thể được mô tả như là một tập các bộ xử lý tự trị liên lạc với nhau qua một mạng truyền thông và có các đặc trưng sau: Không có đồng hồ chung: Không thể đồng bộ hóa đồng hồ của các bộ xử lý khác nhau vì không biết chắc độ trễ truyền thông. Chúng ta có thể dùng khái niệm nhân quả thay cho đồng hộ vật lý để đạt được tính đồng bộ của hệ thống. Không có bộ nhớ toàn cục: Các bộ xử lý không thể biết được trạng thái toàn cục của hệ thống.
Bởi vậy để biết được trạng thái hệ thống, người thiết kế hệ phân tán cần phải xây dựng giải thuật đánh giá các tính chất toàn cục. Không có cơ chế phát hiện sự cố chính xác: Trong hệ phân tán, chúng ta không thể phân biệt được bộ xử lý chậm hay bị sự cố. Khi một bộ xử lý gặp sự cố, các bộ xử lý còn lại vẫn phải tiếp tục làm việc để đạt được kết quả mong muốn. Do đó, cần xây dựng cơ chế phát hiện lỗi và kháng lỗi.
Khoảng cách địa lý: Các bộ xử lý trong một hệ thống phân tán có thể nằm cách xa nhau về mặt địa lý. Cấu hình mạng các trạm làm việc hoặc cụm các trạm làm việc trên mạng LAN đang được quan tâm nhiều hơn khi xây dựng các hệ phân tán cỡ nhỏ. Cấu hình mạng các trạm làm việc đang trở nên phổ biến bởi tận dụng được hạ tầng sẵn có, tiết kiệm chi phí. Động cơ tìm kiếm Google dựa trên kiến trúc mạng các trạm làm việc.
Sự tự trị và tính hỗn tạp: Các bộ xử lý có tốc độ khác nhau và chúng có thể chạy một hệ điều hành khác nhau, nhưng hợp tác với nhau để giải quyết một vấn đề chung. Mô hình truyền thông báo Trong một hệ thống truyền thông báo, các bộ xử lý giao tiếp với nhau bằng cách gửi thông báo qua các kênh truyền thông, mỗi kênh truyền là một kết nối hai chiều giữa hai bộ xử lý. Tô pô của hệ thống được biểu diễn bởi một đồ thị vô hướng, trong đó mỗi nút là một bộ xử lý, mỗi cạnh là một kênh truyền thông giữa các bộ xử lý tương ứng. Giải thuật cho hệ thống truyền thông báo bao gồm một chương trình cục bộ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 cho mỗi bộ xử lý, các chương trình này cung cấp khả năng cho bộ xử lý thực hiện tính toán cục bộ, gửi và nhận các thông báo từ mỗi hàng xóm của nó.
Có thể hình thức hóa như sau: Một hệ thống hay giải thuật bao gồm n bộ xử lý p0, p1,…, pn-1; i là chỉ mục của bộ xử lý pi. Mỗi bộ xử lý pi được coi như một máy trạng thái với tập trạng thái Qi. Bộ xử lý được xác định bởi một nút cụ thể trong đồ thị. Các cạnh liên thuộc với pi trong đồ thị được gắn nhãn bởi các số nguyên từ 1 đến r, trong đó r là bậc của pi.
Mỗi trạng thái của bộ xử lý pi chứa 2r thành phần đặc biệt, outbufi( ) và inbufi( ), với mọi thỏa mãn 1 ≤ ≤ r. Thành phần đặc biệt này là tập các thông báo: outbufi( ) chứa các thông báo mà pi đã gửi tới hàng xóm của nó qua kênh , nhưng chưa đến nơi, và inbufi( ) chứa các thông báo nhận được trên kênh , nhưng chưa xử lý. Tập trạng thái Qi chứa tập con các trạng thái đáng chú ý ban đầu, trạng thái ban đầu của các inbufi( ) phải là rỗng. Trạng thái của bộ xử lý, ngoại trừ các thành phần outbufi( ), bao gồm các trạng thái tới được của pi.
Hàm chuyển của bộ xử lý pi đưa các đầu vào cho trạng thái tới được của pi, tạo ở đầu ra một giá trị cho trạng thái tới được của pi trong đó mỗi inbufi( ) rỗng, hàm chuyển cũng tạo ở đầu ra nhiều nhất một thông báo cho mỗi kênh : thông báo này sẽ được gửi tới hàng xóm trên kênh . Vì vậy, thông báo gửi trước đó bởi pi đang đợi được chuyển không ảnh hưởng đến bước hiện thời của pi; mỗi bước xử lý tất cả các thông báo đang đợi được chuyển tới pi , dẫn đến thay đổi trạng thái và có nhiều nhất một thông báo được gửi tới mỗi hàng xóm. Cấu hình: Cấu hình là một vec tơ C = (q0 ,…, qn-1) trong đó qi là trạng thái của pi. Các trạng thái của các biến outbuf trong một cấu hình mô tả các thông báo chuyển qua các kênh truyền thông.
Cấu hình ban đầu là một vec tơ (q0 ,…, qn-1) sao cho mỗi qi là trạng thái ban đầu của pi. Sự kiện: Với các hệ thống truyền thông báo, chúng ta xem xét hai loại sự kiện, một loại là sự kiện tính, ký hiệu comp(i), biểu diễn một bước tính của bộ xử lý pi, trong đó hàm chuyển của pi được áp dụng cho trạng thái tới được hiện thời. loại còn lại là sự kiện giao, ký hiệu del(i,j,m), biểu diễn sự giao thông báo m từ bộ xử lý pi đến bộ xử lý pj. Thực hiện: Là một chuỗi cấu hình xen kẽ sự kiện mô tả hoạt động của hệ thống, chuỗi này phải thỏa mãn các điều kiện khác nhau.
Có hai loại điều kiện là điều kiện an toàn và điều kiện sống động. Điều kiện an toàn là điều kiện phải đúng với mọi tiền tố hữu hạn của chuỗi mô tả, có nghĩa rằng không có gì xấu xảy ra. Điều kiện sống động là điều kiện phải đúng với một số lần nhất định (có thể vô hạn lần), có nghĩa rằng cuối cùng điều tốt sẽ đến. Bất kỳ chuỗi mô tả nào thỏa mãn mọi điều kiện an toàn đặt ra được gọi là một thực hiện.
Một thực hiện cũng thỏa mãn tất cả các điều kiện sống động đặt ra được gọi là thực hiện thỏa đáng. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 Hệ thống không đồng bộ: Một hệ thống được gọi là không đồng bộ nếu nó không có cận trên đối với thời gian. Đoạn thực hiện trong hệ thống truyền thông báo không đồng bộ là một chuỗi cấu hình xen kẽ sự kiện có dạng: C0, 1, C1, 2, C2, 3,…, trong đó mỗi Ck là một cấu hình và mỗi k là một sự kiện. Nếu hữu hạn thì nó phải kết thúc trong một cấu hình, và những điều kiện sau phải được thỏa mãn: - Nếu k = del(i, j, m), thì m phải là một phần tử của outbufi( ) trong Ck-1, với là nhãn kênh truyền (pi , pj) của bộ xử lý pi.
Sự thay đổi từ cấu hình Ck-1 sang Ck là m được loại bỏ khỏi outbufi( ) trong Ck-1 và được bổ sung vào inbufi(h) trong Ck. Nói cách khác, một thông báo đã được giao nếu và chỉ nếu nó được chuyển từ outbuf của bên gửi sang inbuf của bên nhận. - Nếu k = comp(i), thì sự thay đổi từ cấu hình Ck-1 sang Ck là pi thay đổi trạng thái theo hàm chuyển của nó thực hiện trên trạng thái tới được của pi trong Ck-1, và tập các thông báo xác định bởi hàm chuyển của pi được bổ sung vào các outbufi trong Ck.