CHƯƠNG 1. Khái niệm hệ phân tán 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 vị 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 Hệ phân tán ngày càng trở nên phổ biến vì những vai trò sử dụng quan trọng của chúng. Trước hết, phải kể đến 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. Thông tin từ hệ thống máy tính của ngân hàng đặt tại trụ sở nước này có thể được sử dụng bởi hệ thống máy tính của ngân hàng đặt tại trụ sở nước khác.
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, các PDA, … Thứ hai, 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ứ ba, 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ứ tư, 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ứ năm, hệ phân tán làm đơn TIEU LUAN MOI download : skknchat@gmail.com 9 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 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 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.
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. 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 qi, 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 Pi gửi cho Pj một thông báo m, m được đưa vào hàng đợi qi,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 Pi 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.
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à đọ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 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. Thực hiện và những tính chất của thực hiện Trong một hệ thống phân tán, các bộ xử lý có thể thực hiện các bước tính một cách đồng thời; tuy nhiên, chúng ta giả thiết bước tính này không ảnh hưởng đến bước tính TIEU LUAN MOI download : skknchat@gmail.
Điều này đúng trong mô hình chuyển thông báo vì một thông báo được gửi đi không thể nhận được bởi thao tác nhận xảy ra đồng thời với thao tác gửi. Trong mô hình bộ nhớ dùng chung, chúng ta giả thiết kiến trúc bộ nhớ dùng chung đảm bảo tuần tự hóa: có thể sắp xếp các thao tác đọc và ghi theo thứ tự hoàn toàn để kết quả của thao tác đọc từ một ô nhớ là giá trị được ghi vào ô nhớ tại lần ghi cuối cùng vào ô nhớ trước thao tác đọc. Trong các phần sau đây, chúng ta sử dụng thuật ngữ bước cho bước nguyên tử và ký hiệu một bước (cùng với định danh của bộ xử lý thực hiện bước tính) là a. Cấu hình c2 được gọi là đến được trực tiếp từ cấu hình c1, ký hiệu là c1 a c2, nếu tồn tại một bước tính a để từ cấu hình c1, thực hiện bước a, ta được cấu hình c2.
Cấu hình c’ được gọi là đến được từ cấu hình c, ký hiệu c c’, nếu tồn tại các cấu hình ci, 0 ≤ i ≤ n, và các bước aj, 0 ≤ j < n, để c = c0 a0 c1 a1 c2 … cn-1an-1 cn = c’. Bước tính a’ được gọi là áp dụng được trên cấu hình c nếu tồn tại cấu hình c’ để c a' c’. Một thực hiện E = (c1, a1, c2, a2, …) là một dãy xen kẽ các cấu hình và bước tính trong đó ci-1 ai-1 ci (i > 1); nói cách khác, cấu hình ci (i > 1) đến được trực tiếp từ cấu hình ci-1 bằng việc áp dụng bước tính ai-1. Ví dụ, trong mô hình với bộ nhớ dùng chung, nếu tại bước ai, bộ xử lý Pj ghi giá trị x vào ô nhớ dùng chung rk, thì chỉ hai thành phần có giá trị khác nhau trong ci và ci+1 là Pj và rk.