CHƯƠNG 1. GIỚI THIỆU MÔ HÌNH TÁC TỬ DI ĐỘNG TRONG HỆ PHÂN TÁN 1. Khái niệm hệ phân tán. Hiện nay, trên thế giới có khá nhiều những ñịnh nghĩa khác nhau về hệ phân tán.
Ví dụ: một ñịnh nghĩa về hệ phân tán là “tập hợp các máy tính tự trị, ñược kết nối với nhau bởi một mạng máy tính và ñược cài ñặt phần mềm hệ phân tán”. Hoặc chúng ta có thể coi hệ phân tán là “một tập các máy tính ñộc lập, giao tiếp với người dùng như một hệ thống thống nhất toàn vẹn”. Tuy nhiên, khái niệm chính xác và tổng quá nhất về hệ phân tán là: “Hệ phân tán là tập hợp các thiết bị tính riêng rẽ có thể giao tiếp với nhau”. Như vậy, các ñối tượng trong hệ phân tán không nhất thiết phải là máy tính, mà có thể chỉ là các chíp xử lý, các thành phần trong một bộ ña xử lý, các mạng cục bộ và Internet.
Như vậy, mục ñích chính của hệ phân tán là phối hợp hoạt ñộng của nhiều loại thiết bị ñộc lập hoặc bán ñộc lập nhằm chia sẻ tài nguyên, ñảm bảo tính kháng lỗi và tính sẵn sàng cho hệ thống. Bộ nhớ Bộ nhớ Bộ nhớ cục bộ cục bộ cục bộ Bộ xử lý Bộ xử lý Bộ xử lý network Hình 1. Hệ phân tán Ngày nay, hệ phân tán ñược ứng dụng trong rất nhiều lĩnh vực khác nhau, như giáo dục, y tế, quốc phòng. Nhờ ưu ñiểm là khả năng phối hợp các bộ xử lý ñộc lập, hệ phân TIEU LUAN MOI download : skknchat@gmail.com 6 tán có thể ñược sử dụng ñể giải quyết các bài toán phức tạp, mà nếu chỉ sử dụng một máy tính thì không thể thực hiện ñược.
Trên thế giới hiện có khá nhiều dự án ñã sử dụng mô hình tính toán phân tán này. Ví dụ, như dự án SETI@home, với ý tưởng sử dụng thời gian rỗi của các máy tính cá nhân kết nối vào mạng Internet ñể tìm kiếm các nền văn minh ngoài Trái Đất. Đây là một phần của dự án SERENDIP (Search for Extraterrestrial Radio Emissions from Nearby Developed Intelligent Populations) của ñại học California, Berkeley (UC Berkeley), phân tích các kết quả quan sát của ñài thiên văn vô tuyến Arecibo. Ưu, nhược ñiểm của hệ phân tán Hệ phân tán có rất nhiều ưu ñiểm so với các hệ thống tập trung: • Tiết kiệm chi phí: Do có thể sử dụng kết hợp nhiều máy tính trong quá trình lưu trữ và xử lý dữ liệu, nên trong các hệ phân tán không cần phải sử dụng những máy chủ mạnh và tốn kém.
• Tăng tốc ñộ xử lý: Hiệu suất xử lý của hệ phân tán ñược nâng cao nhờ việc kết hợp sức mạnh xử lý của nhiều máy tính lại với nhau, vì vậy thường hệ phân tán có sức mạnh bằng nhiều máy tính cộng lại. • Độ tin cậy cao: Các bộ xử lý trong hệ phân tán làm việc hoàn toàn ñộc lập. Khi có một bộ xử lý bị lỗi hoặc ngừng làm việc, các bộ xử lý khác trong hệ thống vẫn hoạt ñộng bình thường • Khả năng mở rộng: Dễ dàng mở rộng hệ thống chỉ bằng cách thêm các bộ xử lý mới vào. • Khả năng chia sẻ tài nguyên: Các tài nguyên như dữ liệu hoặc các thiết bị ñắt tiền ñược dùng chung, dễ dàng cho nhiều người dùng trong hệ thống cùng truy nhập.
• Khả năng truyền thông tin: Việc trao ñổi thông tin giữa nhiều người dùng trong hệ thống rất dễ dàng. Tuy nhiên, hệ phân tán cũng có một số nhược ñiểm. Các nhược ñiểm này liên quan ñến vấn ñề kỹ thuật, vì vậy có thể khắc phục ñược bằng những công nghệ và thuật toán mới • Nhược ñiểm về phần mềm: Việc thiết kế, xây dựng và cài ñặt phần mềm trong hệ phân tán khá phức tạp. • Nhược ñiểm về truyền thông mạng: Độ trễ hay việc mất mát dữ liệu trong ñường truyền mạng cũng là vấn ñề cần xử lý trong hệ phân tán TIEU LUAN MOI download : skknchat@gmail.com 7 • Tính bảo mật: Nhiều người dùng và bộ xử lý tham gia vào hệ thống nên tính bảo mật không cao 1.
Đặc trưng hệ phân tán Đặc ñiểm của hệ phân tán là phối hợp hoạt ñộng giữa các bộ xử lý bằng việc truyền thông tin (thường là truyền tin qua mạng). Vì vậy, hệ phân tán có một số các ñặng trưng sau ñây: • Có ñộ trễ truyền thông: Phải mất một khoảng thời gian ñể một sự kiện xảy ra trong hệ ảnh hưởng ñến toàn bộ hệ thống • Không có ñồng hồ chung: Do ñộ trễ truyền thông, nên không thể ñồng bộ hóa ñồng hồ của các bộ xử lý khác nhau. Vì vậy, người ta thường dùng khái niệm nhân quả thay cho ñồng hồ vật lý. • Không có bộ nhớ toàn cục: Các bộ xử lý có bộ nhớ cục bộ, nhưng không biết ñược trạng thái toàn cục của hệ thống.
Vì vậy cần có 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.
• 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. Ứng dụng hệ phân tán Hệ phân tán có rất nhiều ứng dụng trong thực tế: • Chia sẻ tải nguyên: Hệ phân tán kết nối các máy tính lại với nhau, vì vậy việc chia sẻ tài nguyên phần cứng và phần mềm trở nên rất dễ dàng. Người sử dụng có thể ngồi ở máy tính này, truy nhập và xử lý dữ liệu trong một máy tính khác cách hàng nghìn cây số. Hiện nay, hệ phân tán còn có thể kết nối các thiết bị ñiện tử di ñộng lại với nhau, tăng khả năng tương tác của người sử dụng.
Các hệ cở sở dữ liệu phân tán ra ñời dựa trên ứng dụng này. Thông tin có thể ñược lưu trữ ở nhiều vị trí khác nhau, tăng ñộ an toàn của thông tin cũng như giảm hiện tượng thắt nút cổ chai trong quá trình truy nhập • Tính toán phân tán: Điển hình của ứng dụng này là mô hình tính toán lưới (Grid Computing). Nhờ sự kết hợp tốc ñộ xử lý của nhiều máy tính với nhau, mô hình TIEU LUAN MOI download : skknchat@gmail.com 8 tính toán phân tán sẽ giúp tăng hiệu suất cũng như giảm chi phí ñầu tư cho toàn bộ hệ thống. Các mô hình xử lý trong hệ phân tán Trong các hệ phân tán hiện nay, tồn tại hai mô hình xử lý và truyền thông tin giữa các bộ xử lý.
Đó là “mô hình truyền thông báo” và “mô hình tác tử di ñộng” Mô hình truyền thông báo là mô hình truyền thống. Trong ñó, mỗi bộ xử lý sẽ cài ñặt một phần mềm phân tác cụ thể. Phần mềm này có trách nhiệm xử lý các sự kiện và giao tiếp với các bộ xử lý khác bằng việc gửi các thông báo qua kênh truyền. Đây chính là mô hình trao ñổi thông tin truyền thống trong các mạng máy tính.
Ngoài ra, hiện nay còn một mô hình mới ñược sử dụng trong các hệ phân tán, “mô hình tác tử di ñộng (mobile agent)”. Điểm ñặc trưng của mô hình này là việc xử lý cũng như trao ñổi thông tin hoàn toàn do các tác tử ñảm nhiệm. Trong ñó, các tác tử là các chương trình tự trị, có khả năng di chuyển giữa các nút ñể tìm kiếm và xử lý thông tin. Như vậy, trong mô hình này các nút chỉ là những “ñiểm dừng” của các tác tử, hoàn toàn không ñóng vai trò gì trong vấn ñề xử lý.
Mô hình tác tử di ñộng có một số ưu ñiểm khác so với mô hình truyền thông báo. Chúng ta sẽ lần lượt nghiên cứu cụ thể về từng mô hình ở phần tiếp theo. Mô hình truyền thông báo Một hệ phân tán có thể ñược mô tả dưới dạng một ñồ thị vô hướng. Trong ñó, các bộ xử lý ñóng vai trò là các nút.
Các kênh truyền giữa các bộ xử lý chính là các liên kết trong ñồ thị [1][22]. Mô hình hệ phân tán TIEU LUAN MOI download : skknchat@gmail.com 9 Như mô hình trên, hệ thống bao gồm 4 bộ xử lý ñược ký hiệu bởi 4 nút p0 ñến p3, và một số liên kết giữa các nút ñóng vai trò là kênh truyền dữ liệu. Lưu ý rằng trong hệ phân tán, các nút không biết ñược cấu hình cũng như trạng thái của toàn hệ thống. Mỗi nút chỉ biết ñược các liên kết kề nó và thường gán nhãn các liên kết theo thứ tự ñể phân biệt.
Bậc của một nút p chính là số liên kết kề với nút ñó, thường ký hiệu là degp Trong mô hình truyền thông báo, các bộ xử lý có nhiệm vụ thực thi các chương trình (theo một giải thuật nào ñó) và 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. Giải thuật cho mô hình truyền thông báo bao gồm một chương trình cục bộ 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ừ các hàng xóm của nó. Tại mỗi bước trong quá trình thực hiện giải thuật phân tán, các bộ xử lý ñều có một trạng thái nhất ñịnh, là trạng thái của các biến trong bộ nhớ mỗi bộ xử lý. Mỗi trạng thái của bộ xử lý pi chứa 2 tập biến ñặc biệt, outbufi( l ) và inbufi( l ), với mọi l thỏa mãn 1 ≤ l ≤ degpi.
Trong ñó, outbufi( l ) chứa các thông báo mà pi ñã gửi tới hàng xóm của nó qua kênh l , nhưng chưa ñến nơi, và inbufi( l ) chứa các thông báo nhận ñược trên kênh l , nhưng chưa xử lý. Tại trạng thái ban ñầu của mỗi bộ xử lý, inbufi( l ) là rỗng. Một số khái niệm thường ñược xử dụng trong mô hình truyền thông báo • Hàm chuyển (Transition function): có thể coi như một bước tính toán tại mỗi bộ xử lý. Hàm chuyển nhận ñầu vào là trạng thái (của bộ xử lý) không bao gồm các outbuf( l ), và ñầu ra là một trạng thái có inbuf( l ) rỗng.
Như vậy các thông báo ñang chờ ñược chuyển ñi không ảnh hưởng ñến quá trình xử lý hiện tại. • 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 bộ xử lý pi.