CHƯƠNG 1. Khái niệm hệ phân tán Có rất nhiều khái niệm khác nhau về hệ phân tán. Một cách tổng quan, 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. Đây là một khái niệm 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 ngày nay, từ các bộ chíp VLSI đến các bộ đa xử lý, các mạng cục bộ, và Internet.
Nếu nhƣ hệ song song phối hợp nhiều bộ xử lý nhằm giải quyết một vấn đề cho trƣớc một cách nhanh nhất thì hệ phân tán bao gồm một tập các bộ xử lý có chƣơng trình làm việc riêng bán độc lập, vì những lý do gì đó, ví dụ chia sẻ tài nguyên, tăng tính sẵn sàng, khứ lỗi, các bộ xử lý cần phối hợp hành động với nhau. Ta có thể thấy các hệ phân tán ở khắp mọi nơi. Điển hình, các hệ phân tán đƣợc sử dụng để chia sẻ tài nguyên và chia sẻ dữ liệu. Các máy tính kết nối mạng với nhau có thể dùng chung máy in, máy quét, chia sẻ các tệp tài liệu, chƣơng trình… Tính toán ngang hàng là một kiểu thực hiện của hệ phân tán ngày càng trở nên phổ biến cho việc cung cấp các thiết bị và dịch vụ tính toán.
Các hệ phân tán nhiều tham vọng hơn cho hiệu năng hoạt động cao bằng cách kết hợp giải các bài toán con một cách song song, đồng thời tăng tính sẵn sàng của hệ thống trong trƣờng hợp một số thiết bị gặp lỗi. Vai trò của hệ phân tán Ngày nay hệ phân tán đang trở nên phổ biến vì những vai trò ứng dụng quan trọng của chúng. Trƣớc hết, phải kể đến đó là vai trò trao đổi thông tin. Các hệ phân tán cho khả năng chia sẻ thông tin rộng rãi và tức thời.
Lấy ví dụ, thông tin từ hệ thống máy tính đặt tại Sở giao dịch chứng khoán TPHCM có thể đƣợc sử dụng bởi hệ thống máy tính đặt tại trụ sở của các công ty chứng khoán thành viên hay cũng có thể chia sẻ đến tận các nhà đầu tƣ. Các thông tin chứng khoán cũng luôn yêu cầu phải có tính chính xác cũng nhƣ tức thời rất cao, và hệ phân tán cũng có thể cung cấp những khả năng đảm bảo đƣợc điều này. Hệ phân tán cũng cho 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ể "nói chuyện" với các máy tính khác loại, các điện thoại cố định, di động, 9 TIEU LUAN MOI download : skknchat@gmail.com các PDA, … Các hệ phân tán cho khả năng chia sẻ tài nguyên cả phần cứng lẫn phần mềm.
Các máy tính kết nối mạng có thể dùng chung máy in, có thể chia sẻ các tệp dữ liệu, các tệp chƣơng trình. Thứ hai, bằng việc sao lặp, nhân bản, các hệ phân tán cho độ tin cậy 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 đột nhiên biến mất, ngƣời ta có thể khôi phục lại bằng cách sao phần nhân bản đã đƣợc lƣu tại một nơi khác trên hệ thống máy tính của ngân hàng. Thứ ba, thông qua song song hóa, các thực thể 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, do vậy làm tăng hiệu suất hoạt động của hệ thống.
Thứ tư, 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 thƣờng phân một hệ thống phức tạp thành các hệ thống con chuyên dụng và hợp tác với nhau. Làm nhƣ vậy, không những việc thiết kế đơn giản mà việc thực hiện cũng đơn giản. Các ƣu điểm của hệ phân tán so với máy tính cá nhân và so với hệ tập trung đƣợc chỉ ra ngắn gọn trong các bảng sau.
Ưu điểm của hệ phân tán so với máy tính cá nhân. Ưu điểm Mô tả Chia sẻ dữ liệu Cho phép nhiều người dung cùng truy cập vào một cơ sở dữ liệu chung Chia sẻ thiết bị Cho phép nhiều người dung dung chung các thiết bị đắt tiền như máy in màu, máy quét,. Truyền thông Giúp truyền thông giữa người với người dễ dàng hơn, ví dụ bằng thư điện tử Mềm dẻo Phân công việc cho bất kỳ máy nào sẵn sàng 10 TIEU LUAN MOI download : skknchat@gmail. Ưu điểm của hệ phân tán so với hệ tập trung.
Ưu điểm Mô tả Hiệu năng Máy tính đa bộ xử lý có hiệu năng cao hơn máy tính mainframe Tốc độ Tổng năng lực tính toán của một hệ phân tán có thể cao hơn máy tính mainframe Phân tán Một số ứng dụng chạy trên nhiều máy tính xa nhau về mặt không gian Tính tin cậy Khi một máy gặp lỗi, toàn bộ hệ thống vẫn có thể làm việc Mở rộng Năng lực tính toán có thể được nâng lên nhờ them các bộ xử lý bình thường Mặc dù các hệ phân tán có những hạn chế nhƣ hiện tại có ít phần mềm cho chúng, đòi hỏi an ninh và tính bảo mật cao nhƣng những ƣu điểm lớn kể trên làm cho vai trò của các hệ phân tán ngày càng trở nên quan trọng. Đặc trưng của các hệ phân tán Ba đặc trƣng, và cũng là những khó khăn điển hình khi thiết kế, của hệ phân tán là: không đồng bộ, thiếu thông tin toàn cục, và không có cơ chế phát hiện sự cố chính xác. Một hệ phân tán không có đồng hồ chung. Ta cũng 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.
Để đạt đƣợc tính đồng bộ, ta không thể dùng đồng hồ vật lý mà phải vận dụng các khái niệm và giải thuật nhân quả. Tƣơng tự, một hệ phân tán không có bộ nhớ toàn cục chung. Các bộ xử lý không thể biết đƣợc trạng thái toàn cục của hệ thống. "Hiểu biết" của mỗi bộ xử lý chỉ có tính cục bộ.
Do vậy, ngƣời thiết kế hệ phân tán, cụ thể là ngƣời xây dựng giải thuật phân tán phải xây dựng cơ chế đánh giá các tính toàn cục. Ngoài ra, chúng ta không có cơ chế phát hiện sự cố chính xác trong hệ phân tán vì 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 11 TIEU LUAN MOI download : skknchat@gmail.com phải tiếp tục làm việc để đạt đƣợc kết quả nhƣ mong muốn. Những đặc trƣng này thực sự là những khó khăn khi thiết kế các hệ phân tán.
Mô hình hóa các hệ phân tán Trong một hệ phân tán, mỗi thực thể (máy tính, bộ xử lý, tiến trình) chạy một chƣơng trình riêng bao gồm tập các lệnh. Khi thực hiện lệnh, thực thể thay đổi trạng thái cục bộ của nó. Ta có thể mô hình hóa sự thay đổi này bằng cách xem mỗi thực thể là một máy trạng thái. Một hệ phân tán đƣợc mô hình hóa bằng tập n máy trạng thái.
Ký hiệu máy thứ i là Pi. Truyền thông giữa các thực thể có thể thực hiện bằng cách chuyển thông báo hay sử dụng bộ nhớ dùng chung. Truyền thông bằng cách ghi vào và đọc ra từ bộ nhớ dùng chung thƣờng hạn chế hệ thống với các thực thể gần nhau về mặt địa lý, ví nhƣ hệ thống đa bộ xử lý hay các máy tính đa nhiệm. Truyền thông theo cách chuyển thông báo không có giới hạn nhƣ vậy, có thể thực hiện trong cả hệ thống mà các thực thể rất xa nhau về mặt địa lý nhƣ các mạng máy tính.
dƣới đây là minh họa mô hình tổng quát của các hệ thống phân tán. Mô hình tổng quát hệ thống phân tán. Tùy theo phƣơng pháp truyền thông đƣợc sử dụng, ta có mô hình chuyển thông báo hay mô hình với bộ nhớ dùng chung. 12 TIEU LUAN MOI download : skknchat@gmail.
Mô hình chuyển thông báo Trong mô hình chuyển thông báo, các láng giềng trao đổi thông tin cho nhau bằng cách gửi và nhận thông báo. Liên kết giữa các thực thể có thể đơn hoặc lƣỡng hƣớng. Liên kết đơn hƣớng từ thực thể Pi đến thực thể Pj đƣợc sử dụng để chuyển thông báo từ Pi đến Pj. Ta có thể trừu tƣợng hóa liên kết đơn hƣớng trên bằng hàng đợi FIFO q i, j chứa tất cả các thông báo đƣợc Pi gửi cho Pj nhƣng Pj chƣa nhận đƣợc.
Mỗi khi P i gửi cho Pj một thông báo m, m đƣợc đƣa vào hàng đợi q i,j. Pj có thể nhận m khi nó trên đỉnh hàng đợi qi,j. Liên kết lƣỡng hƣớng giữa Pi và Pj có thể đƣợc mô hình hóa bằng hai hàng đợi: qi,j cho hƣớng từ Pi đến Pj và qj,i cho hƣớng từ Pj đến Pi. Trạng thái của hệ thống phân tán chuyển thông báo tại một thời điểm cụ thể đƣợc xác định bởi trạng thái của các bộ xử lý và nội dung của các hàng đợi chứa thông báo tại thời điểm đó.
Cấu hình hệ thống (hay cấu hình) đƣợc dùng để chỉ trạng thái này. Một cấu hình đƣợc ký hiệu c = (s1, s2, …, sn, q1,2 q1,3, …, qi,j, …., qn, n-1), trong đó si, 1 ≤ i ≤ n , là trạng thái của P i và qi, j, i j, là hàng đợi chứa thông báo Pi gửi cho Pj nhƣng Pj chƣa nhận đƣợc. Sau đây là minh họa mô hình chuyển thông báo. Mô hình chuyển thông báo.
Mô hình với bộ nhớ dùng chung Trong mô hình với bộ nhớ dùng chung, các bộ xử lý trao đổi thông tin cho nhau bằng cách sử dụng chung các ô nhớ. Các bộ xử lý có thể ghi vào một tập các ô nhớ và 13 TIEU LUAN MOI download : skknchat@gmail.com đọc ra từ một tập các ô nhớ khác. Cấu hình hệ thống bao gồm trạng thái của các bộ xử lý và nội dung của các ô nhớ dùng chung. Một cấu hình của hệ thống gồm n bộ xử lý và m ô nhớ dùng chung đƣợc ký hiệu c = (s1, s2, …, sn,, r1, r2, …, rm), trong đó si, 1 ≤ i ≤ n, là trạng thái của Pi, rj, 1 ≤ j ≤ m, là nội dung của ô nhớ dùng chung thứ j.
Mô hình với bộ nhớ dùng chung. Mô hình xen kẽ Mô hình xen kẽ đƣợc sử dụng để lý giải hành vi của hệ thống phân tán. Trong mô hình này, tại mỗi thời điểm có duy nhất một bộ xử lý thực hiện một bƣớc tính (còn gọi là bƣớc nguyên tử). Mỗi bƣớc nguyên tử bao gồm một số phép tính bên trong bộ xử lý, hay còn gọi là sự kiện tính, và một phép giao, hay còn gọi là sự kiện giao - một phép gửi hoặc nhận trong hệ thống chuyển thông báo hay một phép ghi hoặc đọc trong hệ thống sử dụng bộ nhớ dùng chung.