Tài liệu Mô phỏng giải thuật phân tán

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ----------------------------------------------- PHẠM TUẤN ANH MÔ PHỎNG GIẢI THUẬT PHÂN TÁN LUẬN VĂN THẠC SỸ KHOA HỌC CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN HÀ NỘI – 2005 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ----------------------------------------------- PHẠM TUẤN ANH MÔ PHỎNG GIẢI THUẬT PHÂN TÁN LUẬN VĂN THẠC SỸ KHOA HỌC CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HÀ QUỐC TRUNG HÀ NỘI - 2005 Chương 1 HỆ PHÂN TÁN 1.1. Hệ phân tán Ngày nay các hệ phân tán xuất hiện trong mọi hoạt động: kinh doanh, nghiên cứu, quản lý và ngay cả tại gia đình. Thông thường chúng cung cấp phương tiện để chia sẻ tài nguyên (như máy in màu hay máy quét) và chia sẻ dữ liệu (không thể thiếu được với nền kinh tế dựa trên thông tin ngày nay). Một hệ thống phân tán bao gồm một tập hợp các bộ xử lý liên kết với nhau thông qua một cấu hình mạng nào đó. Hệ thống có thể là vật lý tức là các máy tính kết nối với nhau thông qua mạng máy tính hay logic tức là tập các tiến trình phần mềm kết nối qua cơ chế truyền thông điệp. Cấu hình mạng có thể là điểm tới điểm hay các kênh truyền thông đại chúng (broadcast). Hệ phân tán khác hệ tập trung ở một số điểm cơ bản sau. • Thiếu nhận biết về trạng thái toàn cục của hệ thống (có thể thu thập thông tin về trạng thái hệ thống nhưng không cập nhật). 12 • Thiếu một khung thời gian toàn cục (các sự kiện không có thứ tự). • Bất định. Cần phân biệt hai mức khác nhau khi xem xét một hệ phân tán: mức bộ xử lý và mức tiến trình. Ở mức của bộ xử lý, các bộ xử lý không có chia sẻ bộ nhớ về mặt vật lý và thiết yếu phải trao đổi thông qua truyền thông điệp. Trên mỗi bộ xử lý có nhiều tiến trình. Các tiến trình trên nhiều bộ xử lý hình thành mức tiến trình trong hệ phân tán. Ở mức tiến trình chúng ta có nhiều lựa chọn trao đổi hơn so với mức bộ xử lý. Các tiến trình có thể trao đổi thông qua chia sẻ bộ nhớ hay truyền thông điệp hoặc phối hợp cả hai. Trong các phần sau chúng ta chỉ xem xét hệ phân tán dưới mức độ tiến trình do mức bộ xử lý có thể xem như mức tiến trình với mỗi tiến trình trên một bộ xử lý. Hệ phân tán được biết đến sớm nhất trong thực tế là mạng máy tính. Dù ban đầu được thực hiện cho mục đích truy cập từ xa và sau này cho thư điện tử mạng máy tính đã phát triển nhanh chóng bao gồm nhiều dịch vụ truyền dữ liệu khác nhau như truyền file hay duy trì các phiên làm việc. Một mạng lưới phức tạp các giao thức đã được thiết kế cho các dịch vụ này bằng cách truyền thông điệp trên nhiều mức độ. Những tiến bộ gần đây trong thiết kế các giao thức còn cho phép tồn tại nhiều dạng truyền thông khác nhau bên cạnh dữ liệu như âm thanh và hình ảnh. Một ví dụ nổi tiếng khác về hệ phân tán nằm trong lĩnh vực xử lý song song với một tập các bộ xử lý cùng phối hợp giải một bài toán. Tính toán song song có rất nhiều ứng dụng trong các lĩnh vực khoa học và kỹ thuật. Thiết kế ban đầu cho các hệ xử lý song song tập trung vào các hệ chia sẻ bộ nhớ (chia sẻ cả không gian nhớ và không gian địa chỉ). Tuy nhiên người ta đã nhanh chóng nhận ra hiệu năng của hệ thống bị giới hạn bởi cơ chế vật lý xác định 13 việc chia sẻ các phần tử nhớ. Mong muốn cung cấp một hiệu năng cao hơn cho các ứng dụng đã dẫn đến sự ra đời của các hệ phân tán với liên kết điểm tới điểm thống trị cho tới ngày nay. Trong các hệ phân tán quan trọng ngày nay còn phải kể đến mạng các máy trạm. Các mạng này có nhiều điểm giống như mạng máy tính ta đã nói ở trên nhưng có phạm vi địa lý hẹp hơn và thường dùng các kết nối đại chúng như môi trường truyền thông chính (các tiến trình trên các bộ xử lý dùng kết nối điểm tới điểm) . Mạng máy trạm cung cấp nhiều dịch vụ hơn mạng máy tính ví dụ như chia sẻ hệ thống file. Từ các ví dụ về các hệ phân tán trong thực tế đã mô tả ở trên có thể thấy rõ kết nối điểm tới điểm thống trị trong hầu hết các trường hợp. Điều này đồng nghĩa với việc truyền thông giữa các điểm mạng đóng vai trò chủ đạo. 1.2. Tính chất của một hệ phân tán 1.2.1. Chia sẻ tài nguyên Tài nguyên là khái niệm để chỉ tất cả những gì có thể sử dụng chung trong hệ phân tán. Tài nguyên có thể bao gồm từ phần cứng như bộ nhớ hay máy in, tới các thực thể lôgic được định nghĩa bởi phần mềm như file, CSDL... Việc chia sẻ tài nguyên đem lại những lợi ích sau: • Các thiết bị phần cứng được chia sẻ tạo thuận lợi cho việc sử dụng và giảm bớt chi phí. • Chia sẻ dữ liệu là một yêu cầu cơ bản của nhiều ứng dụng. • Các nhà phát triển phần mềm có thể cần truy cập công việc lẫn nhau, có thể chia sẻ các công cụ mà chỉ cần một phiên bản của thư viện, trình dịch... 14 • Khi cài đặt một công cụ mới, tất cả các thành viên đều có thể sử dụng tài nguyên mới này. • Các ứng dụng thương mại thường sử dụng một CSDL cho nhiều người truy nhập phân tán. Để việc chia sẻ tài nguyên có hiệu quả, mỗi tài nguyên cần được quả lý bởi một chương trình. Chương trình này cung cấp các giao diện cho phép tài nguyên được truy cập, thay đổi an toàn và thống nhất. Quản trị tài nguyên là một chương trình quản lý một số tài nguyên thuộc một loại nào đó. Mỗi loại tài nguyên cần được quản lý một cách khác nhau. Tuy vậy, cũng có một số yêu cầu chung. Ví dụ như hệ thống đặt tên cho mỗi lớp tài nguyên, việc ánh xạ tên lên địa chỉ vật lý, việc giải quyết các truy nhập đồng thời để đảm bảo tài nguyên có tính thống nhất. Có hai mô hình cho hệ thống các chương trình quản lý tài nguyên: mô hình Client-Server và mô hình hướng đối tượng. • Mô hình Client-Server: Có một số các tiến trình quản lý một loại tài nguyên nhất định, và một số tiến trình khác thực hiện những công việc đòi hỏi phải truy cập các tài nguyên đó. Mô hình này có thể áp dụng vào phạm vi rộng với cả phần cứng và phần mềm. • Mô hình đối tượng: Các tài nguyên chung được nhìn như một đối tượng. Các đối tượng được định danh và có thể dịch chuyển trên mạng. Khi một chương trình cần sử dụng tài nguyên thì chương trình đó gửi một thông báo chứa yêu cầu tới đối tượng. Thông báo này được dịch tới một thủ tục của đối tượng, thực hiện các thao tác cần thiết và một thông báo khác sẽ được gửi lại chương trình chứa kết quả. Một vấn đề của mô hình này là việc mã các 15 thủ tục của đối tượng luôn đi kèm phần dữ liệu của dối tượng, do đó đối tượng không di chuyển được. 1.2.2. Tính mở Tính mở là đặc tính của một hệ thống có thể được mở rộng. Một hệ thống có tính mở đối với phần cứng: ví dụ có thể thêm thiết bị ngoại vi, bộ nhớ trong - hoặc phần mềm: có thể bổ sung một vài tính năng của hệ thông, giao thức trao đổi hoặc một vài dịch vụ chia sẻ tài nguyên. Nói chung, tính mở của hệ phân tán được đánh giá bằng khả năng thêm dịch vụ chia sẻ tài nguyên mà không phải bỏ hoặc thay đổi các dịch vụ sẵn có. Tính mở được thực hiện bằng cách công bố các giao diện cho các nhà phát triển phần mềm. Trong lịch sử, các hệ thống máy tính thường là các hệ thống đóng. UNIX là một ví dụ về hệ thống mở cho các nhà phát triển ứng dụng, cho các nhà sản xuất phần cứng và các nhà quản lý hệ thống, cho các nhà sản xuất phần mềm và người sử dụng. Tính mở trong hệ phân tán đặt nền tảng trên cơ chế chung trao đổi thông tin giữa các tiến trình, các giao diện được công bố để truy nhập tài nguyên. Hệ phân tán mở có thể được cấu thành từ phần cứng và phần mềm không đồng nhất, từ nhiều nhà cung cấp khác nhau. Tuy nhiên các thành phần của hệ thống cần phải được kiểm tra kỹ trước khi đưa vào sử dụng. 1.2.3. Tính tương tranh Khi nhiều chương trình được thực hiện trên một máy tính, chúng ta nói là chúng được thực hiện đồng thời. Nếu máy tính đó chỉ có một bộ vi xử lý, việc thực hiện các tiến trình được tiến hành theo từng phần của các tiến trình. Nếu số lượng bộ vi xử lý nhiều hơn số tiến trình, mỗi mội tiến trình sẽ được 16 thực hiện bằng một bộ vi xử lý và khi đó các tiến trình được thực hiện đồng thời thật sự. Trong hệ phân tán xây dựng trên cơ sở chia sẻ tài nguyên, việc thực hiện đồng thời có thể xảy ra trong các trường hợp sau: • Nhiều người sử dụng cùng gọi nhiều lệnh, tương tác với nhiều ứng dụng. Trường hợp này xảy ra khi có một hay nhiều tiến trình phục vụ cho mỗi người sử dụng. • Nhiều tiến trình phục vụ cùng chạy trả lời các lời gọi khác nhau từ các tiến trình khác nhau. Trường hợp này xảy ra khi tồn tại tiến trình phục vụ cho việc quản lý nhiều tài nguyên sẽ được xếp hàng, có thể sẽ được thực hiện lần lượt, có thể một số sẽ được thực hiện song song bởi nhiều phiên bản của các tiến trình. Khi có nhiều tiến trình truy cập dữ liệu của cùng một tài nguyên, tiến trình quản lý tài nguyên cần phải tiến hành đồng bộ các yêu cầu, đảm bảo chúng không bị mâu thuẫn và vẫn giữ được các lợi thế của tính tương tranh. Tóm lại, tương tranh và thực hiện song song phát sinh một các tự nhiên trong các hệ phân tán, xuất phát từ các hoạt động riêng rẽ của người sử dụng, tính độc lập của tài nguyên, tính phân tán của các tiến trình phục vụ. Điều này cho phép việc xử lý có thể được tiến hành trên các máy tính khác nhau. Truy cập và cập nhật đồng thời tài nguyên phải được đồng bộ. 1.2.4. Khả năng hỗ trợ tải thay đổi Hệ phân tán phải có khả năng làm việc tốt với những qui mô rất khác nhau của tải. Số lượng người truy cập có thể là thay đổi trong phạm vi rất lớn. Hệ phân tán đơn giản nhất cũng phải bao gồm hai máy nối lại với nhau, trong khi có các hệ thống lớn nối nhiều mạng cục bộ với nhau với số lượng hàng 17 nghìn máy. Trong hàng nghìn máy đó, có lúc rất nhiều máy cùng sử dụng một tài nguyên nào đó, có những lúc lại không có máy nào sử dụng tài nguyên đó cả. Các dịch vụ phân tán phải có khả năng hoạt động trong điều kiện khác nhau như vậy. Trong hệ phân tán, những tài nguyên được coi là giới hạn trong các hệ thống tập trung sẽ trở thành vô hạn như: Số bộ vi xử lý, bộ nhơ, các kênh vào ra... Tuy nhiên, một số tài nguyên khác sẽ bị giới hạn nếu trong quá trình thiết kế, tính tương tranh không được quan tâm tới. Khi thiết kế hệ thống phân tán, không một tài nguyên nào được thiết kế để cung cấp trong giới hạn. Khi nhu cầu sử dụng tăng lên, cần phải có khả năng mở rộng hệ thống để đáp ứng nhu cầu mới. Ví dụ: khi số yêu cầu sử dụng file tăng lên, hệ thống cần phải có khả năng thêm một máy phục vụ file mới để giảm bớt tải cho máy phục vụ file cũ. Một vài file có thể bị truy cập một cách thương xuyên thì chúng cần phải được nhân thành nhiều bản, lưu tại nhiều máy khác nhau. 1.2.5. Tính chất chịu lỗi Các hệ thống máy móc đôi khi cũng hỏng hóc. Khi có sự cố xảy ra, hệ thống có thể dừng hoạt động, có thể đưa ra các kết quả không chính xác. Như vậy để có thể hoạt động có hiệu quả, hệ phân tán cần phải có khả năng phát hiện lỗi và xử lý lỗi. Nói chung, khi có lỗi xảy ra, người sử dụng thường không có kiến thức đủ để biết thực sự có chuyện gì xảy ra với hệ thống. Mọi cố gắng của người sử dụng để giải quyết sự cố thường không có kết quả. Như vậy hệ phân tán cần xử lý lỗi sao cho người sử dụng không phải quan tâm đến việc có lỗi hay không có lỗi xảy ra, đồng thời vẫn thu được kết quả đúng chỉ trong trường hợp hệ không tự giải quyết được lỗi thì mới báo cho người sử dụng. 18 Để đạt được mục đích trên, có thể sử dụng phần cứng dự trữ khi có sự cố xảy ra. Ví dụ để đảm bảo dịch vụ thư điện tử vẫn hoạt động bình thường khi máy phục vụ thư điện tử bị lỗi, có thể bố trí một máy khác đưa vào thay thế. Phương pháp này đòi hỏi chi phí đầu tư ban đầu tương đối lớn. Có thể giảm bớt chi phí này bằng cách dùng một máy dự trữ cho nhiều chức năng khác nhau. Một cách khác để đảm bảo tính chịu lỗi cho hệ thống là sử dụng phần mềm phục hồi lại hệ thống. Nếu hệ thống hoặc một phần của hệ thống hoặc một thao tác nào đó bị sự cố, sẽ có phần mềm để loại bỏ những thay đổi do sự có gây ra, khởi động lại thao tác từ điểm chưa có sự cố. Muốn làm như vậy phần mềm này phải theo dõi hệ thống trong suốt thời gian khi chưa xảy ra sự cố. 1.2.6. Tính trong suốt Tính trong suốt là sự che giấu tính phân tán của các thành phần trong hệ phân tán với người sử dụng. Người sử dụng không cần biết các tài nguyên mà mình đang sử dụng nằm ở đâu, phân tán hay tập trung, mà sử dụng như một tài nguyên lôgic duy nhất của hệ phân tán. Có các loại trong suốt sau: • Trong suốt về truy cập: Các đối tượng thông tin có thể truy cập bằng cùng một phương pháp như nhau. • Trong suốt về địa điểm: Tài nguyên có thể được truy cập mà không cần biết vị trí địa lý của chúng. • Trong suốt về tương tranh: Tài nguyên có thể được sử dụng bởi nhiều người sử dụng khác nhau mà người sử dụng không biết 19 được sự tồn tại của người sử dụng khác đang truy cập vào tài nguyên đó. • Trong suốt sao lưu: Một số tài nguên có thể được sao lưu để làm tăng tốc độ phục vụ của hệ thống. Quá trình sao lưu này phải được giấu kín hoàn toàn khỏi sự nhận biết của người sử dụng. • Trong suốt khi có lỗi xảy ra: Khi có lỗi xảy ra trong hệ thống, việc xử lý lỗi cũng cần được che giấu. Người sử dụng chỉ biết là yêu cầu của mình thực hiện được (trong trường hợp hệ phân tán xử lý thành công các sự số) hoặc không xử lý được (nếu hệ phân tán không xử lý được một trong các sự cố). 1.3. Mô hình truyền thông phân tán Môi trường truyền thông giữa các tiến trình được phân thành hai loại: hệ truyền thông điệp và hệ chia sẻ bộ nhớ chung. Trong hệ truyền thông điệp các tiến trình gửi và nhận thông điệp thông qua các kênh tin. Mỗi kênh tin kết nối định hướng hay không định hướng giữa hai tiến trình. Kiểu kết nối giữa các kênh tin hình thành cấu trúc mạng của hệ thống. Như vậy có thể biểu diễn cấu trúc mạng của hệ thống dưới dạng đồ thị với mỗi tiến trình tại một nút và mỗi kênh truyền thông được biểu diễn bằng một cung. Ta có thể hình thức hoá hệ truyền thông điệp dưới dạng toán học như sau. Hệ thống được biểu diễn bằng một đồ thị định hướng liên thông GT = (NT, DT) với tập các nút NT biểu diễn tập các tiến trình, tập các cung định hướng DT biểu diễn các kênh truyền thông định hướng. Mỗi tiến trình tại mỗi nút được mô hình hoá dưới dạng máy trạng thái hữu hạn hay vô hạn. Với một tiến trình t ký hiện Int là tập các cung đi vào t và Outt là tập các cung đi ra khỏi t. Các kênh thuộc tập Int là các kênh từ đó t nhận tin còn các kênh thuộc 20 tập Outt là các kênh mà t gửi tin lên đó. Những gì diễn ra trong hệ thống được mô hình dưới dạng các sự kiện. Có hai dạng sự kiện trong hệ truyền thông điệp: sự kiện tính toán compt (tiến trình t xử lý thông điệp nhận được) và sự kiện gửi thông điệp dels,t,m (tiến trình s gửi thông điệp m tới tiến trình t). Trong hệ chia sẻ bộ nhớ, các tiến trình truyền thông thông qua một vùng nhớ chia sẻ chung chứa tập các biến chia sẻ còn được gọi là các thanh ghi (registers). Các biến này gồm nhiều loại khác nhau. Mỗi loại xác định các toán tử có thể thực hiện trên biến cũng như giá trị mà nó trả về. Loại thông dụng nhất là thanh ghi đọc / ghi với toán tử là các lệnh đọc ghi thông thường. Một số loại khác hỗ trợ các toán tử mạnh hơn như đọc / biến đổi / ghi, kiểm tra / thiết lập, so sánh / tráo đổi… Các thanh ghi còn có thể được phân loại tiếp theo số tiến trình có thể truy cập trong mỗi lần thực hiện của một toán tử. Hệ chia sẻ bộ nhớ được hình thức hoá dưới dạng một tập n các tiến trình và một tập m các thanh ghi. Giống như hệ truyền thông điệp mỗi tiến trình được mô hình hoá dưới dạng máy trạng thái hữu hạn hay vô hạn. Mỗi thanh ghi được xếp vào một loại nhất định phụ thuộc vào giá trị thanh ghi có thể nhận, các toán tử thao tác trên thanh ghi, các giá trị thanh ghi trả về và giá trị mới của thanh ghi sau khi thực hiện toán tử. Sự kiện là sự kiện tính toán của mỗi tiến trình gồm ba loại: tiến trình truy cập thanh ghi để thực hiện một toán tử dựa trên trạng thái hiện tại của tiến trình, toán tử được thực hiện trên thanh ghi, biến đổi trạng thái tiến trình dựa trên trạng thái hiện tại và giá trị trả về từ toán tử thực hiện trên thanh ghi. Trong phần lý thuyết từ đây trở đi ta sẽ chỉ nói về mô hình truyền thông qua việc gửi và nhận thông điệp hay các hệ thống truyền thông điệp. Cách thức chia sẻ một vùng nhớ có những hạn chế về mặt vật lý tác động tới hiệu năng của hệ thống nên sẽ không được nói đến ở đây (như ví dụ về giai đoạn 21 phát triển đầu của xử lý song song sử dụng kỹ thuật chia sẻ bộ nhớ). Mô phỏng hệ chia sẻ bộ nhớ bằng hệ truyền thông điệp có thể thực hiện rất dễ dàng. 1.4. Mô hình đồng bộ và không đồng bộ Quan tâm chính của ta trong phần này là tìm hiểu quan hệ giữa giải thuật phân tán với yếu tố thời gian. Tính toán thực hiện tại mỗi nút của G sẽ được xem xét dưới góc độ các đặc trưng thời gian. Có hai mô hình thời gian: mô hình đồng bộ và mô hình không đồng bộ. 1.4.1. Mô hình không đồng bộ Hệ thống là không đồng bộ nếu không có giới hạn trên cho trước với thời gian truyền thông điệp hay thời gian giữa hai bước tính toán liên tiếp của một tiến trình. Một ví dụ điển hình có thể tìm thấy qua Internet khi thư điện tử (thông điệp) có thể mất nhiều ngày để chuyển tới địa chỉ nhận trong khi thông thường chỉ mất vài giây. Giới hạn trên này biến đổi theo thời gian do đó tốt hơn ta nên thiết kế giải thuật độc lập với các thông số thời gian. Hệ không đồng bộ có hai đặc trưng sau. • Mỗi tiến trình có một thời gian địa phương riêng độc lập với nhau thông qua đồng hồ địa phương. • Độ trễ mỗi thông điệp phải chịu khi truyền giữa các nút lân cận là hữu hạn nhưng bất định. Một điểm quan trọng cần nêu ra đây là các khái niệm sử dụng để mô tả tính toán của một nút trong giải thuật Task_t hoàn toàn phù hợp với các giả thiết của mô hình không đồng bộ vì ngoại trừ thời điểm tính toán lúc đầu tính toán sau đó chỉ có thể diễn ra khi tiến trình nhận được thông điệp. Hơn nữa không có thông tin về thời gian nào được sử dụng trong giải thuật. 22 Dựa trên giải thuật Task_t, tính toán tại một nút trong mô hình không đồng bộ có thể mô tả qua các hành động ban đầu (nếu nút bắt đầu tính toán và gửi thông điệp tự phát) và các hành động khi nhận thông điệp với một số điều kiện nào đó được thoả mãn. Mô tả này được thực hiện trong giải thuật A_Template dưới đây. Giải thuật này là khuôn hình cho tất cả các giải thuật được nghiên cứu dưới mô hình không đồng bộ do đó nó còn được gọi là giải thuật không đồng bộ. Giải thuật mô tả tính toán tại nút ni. N0 thuộc tập N là tập không rỗng các nút có thể gửi tin lúc đầu. Đồ thị được giả định là định hướng. Giải thuật A_Template: Biến: Biến sử dụng bởi ni và giá trị ban đầu. Thông điệp nhận: tini = nil Hành động nếu ni thuộc N0: tính toán gửi thông điệp trên mỗi cung của một tập con (có thể rỗng) của Outi Thông điệp nhận: tini với nguồn(tini) = ck thuộc Ini với 1 ≤ k ≤ |Ini| Hành động khi có Bk: tính toán của Outi gửi tin trên mỗi cung của một tập con (có thể rỗng) Bảng 1.1. Giải thuật A_Template Giải thuật bao gồm một chuỗi các cặp thông điệp nhận / hành động. Mỗi cặp cho một dạng thông điệp cụ thể. Mỗi hành động trong giải thuật được giả thiết là hành động nguyên tử tức là hoàn thành trước khi xuất hiện bất cứ ngắt nào. Thông điệp nhận được ký hiệu bởi tini. Nếu ni thuộc N0 ta có 23 tini = nil do lúc đầu không có thông điệp nào kích hoạt hành động của ni. Khi có một thông điệp tới ta giả định ni biết thông điệp này từ đâu tới qua cung mà nó nhận tin. Mô hình không đồng bộ rất phù hợp với tính chất các hệ phân tán ta đã nhắc đến trong phần một. Tuy nhiên chính tính không đồng bộ lại giải thích cho phần lớn khó khăn gặp phải khi thiết kế giải thuật phân tán cho mô hình không đồng bộ. Vì vậy thông thường người ta dùng các mô hình ít thực tế hơn trong đó các đặc trưng thời gian của G hoàn toàn ở vào thái cực ngược lại. Đó là mô hình đồng bộ. 1.4.2. Mô hình đồng bộ Trong hệ thống đồng bộ tiến trình thực hiện theo nhịp đồng hồ. Quá trình chạy được chia thành các chu kỳ. Trong mỗi chu kỳ mỗi tiến trình có thể gửi thông điệp tới các tiến trình xung quanh, mọi thông điệp đều được nhận và mỗi tiến trình tính toán dựa trên thông điệp vừa nhận được. Mô hình đồng bộ có hai đặc trưng sau: • Mọi nút có một thời gian chung thông qua đồng hồ chung của toàn hệ tạo ra những xung cố định. • Độ trễ mỗi thông điệp phải chịu khi truyền giữa các nút lân cận là khác không nhưng nhỏ hơn độ dài xung của đồng hồ. Độ dài xung sinh ra bởi đồng hồ không nhất thiết phải như nhau do đó có thể lấy độ trễ tin phải chịu khi truyền giữa các nút lân cận là giới hạn dưới cho khoảng thời gian này. Cũng như giải thuật không đồng bộ giải thuật phân tán trong mô hình đồng bộ còn được gọi là giải thuật đồng bộ. Tại xung s = 0 các nút thuộc tập N0 gửi thông điệp lên một số cung đi ra khỏi nút này. Với xung s > 0 mọi 24 thông điệp được gửi tại xung s-1 được giả định là đã nhận được và mọi nút trong N có thể thực hiện tính toán và gửi thông điệp. Có một giả thiết được hiểu ngầm trong phần mô tả trên. Đó là giả thiết tính toán tại mỗi nút trong khoảng đồng hồ chung được xem bằng không. Nếu không có giả thiết này khoảng đồng hồ chung sẽ không đủ cho cả tính toán địa phương tại mỗi nút cũng như truyền thông điệp giữa các nút bởi thời gian truyền thông điệp được lấy gần bằng độ dài xung. Tập N0 có thể gửi thông điệp tại xung s = 0 trong mô hình đồng bộ giống như tập N0 gửi thông điệp tự phát trong mô hình không đồng bộ. Tuy nhiên có một khác biệt căn bản giữa hai mô hình. Trong mô hình đồng bộ các nút có thể thực hiện tính toán mà không cần nhận thông điệp vì mỗi nút được kích hoạt bởi đồng hồ chung không phải bởi thông điệp nhận được. Do đó về mặt nguyên lý giải thuật đồng bộ không cần thông điệp và các nút có thể tiếp tục tính toán ngay cả khi N0 = 0. Điều này không khác gì n nút hoàn toàn độc lập chạy song song với nhau nên để tránh nghiên cứu một hệ thống như vậy ta vẫn cần có ít nhất một thông điệp được gửi đi ban đầu bởi một nút nào đó. Mô hình đồng bộ thoạt nhìn có vẻ không thực tế nhưng đôi khi lại rất có ích khi thiết kế giải thuật phân tán không chỉ vì đơn giản hoá thiết kế mà còn đưa lại một giải thuật không đồng bộ hiệu quả hơn. Có thể thấy mỗi giải thuật không đồng bộ về bản chất là một giải thuật đồng bộ. Một giải thuật thiết kế cho mô hình không đồng bộ cũng hoạt động tốt dưới giả thiết của mô hình đồng bộ với một độ dài xung lựa chọn thích hợp. Điều này xuất hiện do điều kiện truyền thông diễn ra trong mô hình đồng bộ chỉ là một trong vô số các khả năng mà mô hình không đồng bộ cho phép. Dưới đây là giải thuật S_Template mô tả giải thuật đồng bộ sẽ được sử dụng như một khuôn hình cho các giải thuật đồng bộ cụ thể. Với s > 0 và ni 25 thuộc N, TINi(s) là một tập rỗng (nếu s=0) hoặc tập thông điệp nhận được bởi ni trong khoảng s-1 (cũng có thể rỗng). Giải thuật này được thực hiện cho đồ thị định hướng. Giải thuật S_Template: Biến: Biến sử dụng bởi ni và giá trị ban đầu. Thông điệp nhận: s = 0 TINi(0) = 0 Hành động nếu ni thuộc N0: tính toán gửi thông điệp trên mỗi cung của một tập con (có thể rỗng) của Outi Thông điệp nhận: s > 0, TINi(1), …, TINi(s) với nguồn(tin) = ck thuộc Ini với 1 ≤ k ≤ |Ini| cho tin thuộc tập tin nhận được. Hành động: tính toán gửi thông điệp trên mỗi cung của một tập con (có thể rỗng) của Outi Bảng 1.2. Giải thuật S_Template Tương tự như giải thuật A_Template giải thuật S_Template cũng bao gồm một tập các cặp thông điệp nhận / hành động. Thông điệp nhận bây giờ bao gồm cả xung đồng hồ. Những xung này kích hoạt hoạt động của các nút. 26 Tính nguyên tử của các hành động đến từ đặc trưng của mô hình đồng bộ vì không có nút nào thực hiện hơn một hành động trong một chu kỳ. Mỗi nút trong khoảng s có thể truy cập tới mọi thông điệp trong các tập TINi(1), …, TINi(s). 1.5. Thất bại tiến trình Những bài toán phối hợp đòi hỏi các tiến trình đồng thuận trên một tiến trình hành động chung. Những bài toán như vậy rất dễ thực hiện trên những hệ thống đáng tin cậy ta đã nói ở trên. Tuy nhiên trong thực tế hiếm khi các thành phần khác nhau lúc nào cũng chạy đúng. Do đó ta cần khảo sát hệ thống khi có xuất hiện thất bại tiến trình. Khảo sát trong phần này xem xét hệ phân tán dưới mô hình đồng bộ bởi dưới mô hình không đồng bộ người ta đã chứng minh được rằng bài toán đồng thuận là không giải được. Thất bại trên kênh tin sẽ không được xét đến. Mọi kênh được giả định đáng tin cậy cũng như mọi thông điệp đã gửi đều được nhận. Người ta thường xét hai loại thất bại tiến trình: thất bại do bộ vi xử lý và thất bại do mạng. 1.5.1. Thất bại do bộ vi xử lý Thất bại do bộ vi xử lý xuất hiện khi hoạt động của bộ vi xử lý trả lại kết quả không mong đợi. Có ba loại thất bại được xếp tăng dần theo độ khó phát hiện là: thất bại phá huỷ, chậm và byzantine. • Thất bại phá huỷ: Trong mô hình thất bại dừng, hoặc do bộ vi xử lý đang trong thời gian thực hiện một công việc khác và cũng đang tham gia vào một giao thức phân tán, hoặc do bộ vi xử lý có lỗi và không bao giờ trả lời các yêu cầu gửi đến. Trong thất bại phá huỷ tiến trình thực hiện thất bại và ngừng hoạt động nhưng không có các hoạt động lỗi như nhận thông điệp chưa hề được gửi. Mô hình 27 hình thức của hệ đồng bộ khi có sự xuất hiện của thất bại phá huỷ được biến đổi lại như sau. Ta đưa vào tham số sống f là số cực đại tiến trình có thể thất bại. Hệ thống như vậy sẽ được gọi là hệ thống có độ tin cậy f. Như thế sẽ tồn tại một tập F các tiến trình lỗi với nhiều nhất là f tiến trình. Tập F có thể khác nhau trong mỗi lần thực hiện do đó ta không thể biết trước tiến trình nào là tiến trình lỗi. Mỗi chu kỳ của giải thuật chứa chính xác một sự kiện tính toán cho mỗi tiến trình không thuộc F và nhiều nhất một sự kiện tính toán cho mỗi tiến trình thuộc F. Hơn nữa nếu một tiến trình thuộc F không có sự kiện tính toán nào tại một chu kỳ nào đó thì nó cũng không có sự kiện tính toán nào trong các chu kỳ tiếp theo. Trong chu kỳ cuối cùng khi một tiến trình lỗi còn thực hiện tính toán nó nhận được một tập ngẫu nhiên các thông điệp là tập con của tập các thông điệp gửi đến nó. • Thất bại chậm: Thất bại này là do bộ vi xử lý có lỗi hoặc thực hiện các thủ tục chậm. Đôi khi không phải do bộ vi xử lý bị lỗi mà do đang thực hiện, nhưng đã bị đánh dấu lỗi do đó không còn được tham gia vào hệ thống. Rất khó để phát hiện thất bại chậm trong hệ phân tán. • Thất bại byzantine: Trong thất bại byzantine tiến trình lỗi có thể hoạt động tuỳ tiện. Thất bại này nghiêm trọng hơn so với thất bại phá huỷ. Tương tự như mô hình hoá hệ đồng bộ khi có thất bại phá huỷ ta cũng đưa vào tham số f là số cực đại tiến trình có thể thất bại. Trong mỗi lần thực hiện của hệ thống có thất bại byzantine với độ tin cậy f tồn tại một tập F nhiều nhất f tiến trình là các tiến trình lỗi. Tại mỗi bước tính toán của tiến trình lỗi 28 trạng thái tiếp theo của tiến trình cũng như nội dung thông điệp được gửi đến các tiến trình xung quanh hoàn toàn tuỳ tiện, không bị ràng buộc. Do đó một tiến trình lỗi có thể gửi các thông điệp khác nhau tới các tiến trình khác nhau hay thậm chí không gửi thông điệp nào mà lẽ ra nó phải gửi cùng một thông điệp tới mọi tiến trình. Trong một số trường hợp tiến trình nhận có thể phát hiện tiến trình gửi thất bại dựa vào định dạng của thông điệp. Khó khăn chủ yếu nảy sinh khi thông điệp nhận được hợp lệ nhưng thực tế là sai. Một tiến trình byzantine có thể mô phỏng một tiến trình thất bại khi không gửi thông điệp nữa từ một chu kỳ nào đó. 1.5.2. Thất bại do mạng Thất bại do mạng ngăn cản các bộ vi xử lý có thể kết nối với nhau. Thất bại do mạng có thể do mạng không đáng tin cậy, có thể do việc chuyển các message lỗi, có thể là thứ tự của các message đến không đúng thứ tự. Chúng ta cần các giao thức cho phép tạo các liên kết đáng tin cậy mặc dù có thể có nhiều message cùng được gửi trên một đường truyền. Nếu một liên kết bị lỗi có thể gây ra một vài vấn đề như sau: • Các lỗi gây liên kết một chiều: Một thất bại mạng có thể sinh ra một topo kết nối lỗi. Ví dụ như một bộ vi xử lý A có thể gửi một message nhưng bộ vi xử lý B không thể nhận được message. Một bộ vi xử lý C lại có thể nói chuyện với cả bộ vi xử lý A và B. Lỗi này gây ra một lỗi giống như thất bại chậm. • Các lỗi gây ngăn cách mạng: Một lỗi gây ngăn các mạng xuất hiện khi một phần của mạng bị tách ra khỏi phần còn lại. Ví dụ A 29