Tài liệu Bế tắc và xử lý bế tắc trong hệ phân tán

BỘ GIÁO DỤC & ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG --------------------------- TIỂU LUẬN MÔN HỌC Đề tài: BẾ TẮC VÀ XỬ LÝ BẾ TẮC Giáo viên hướng dẫn: PGS.TS. Lê Văn Sơn LỜI MỞ ĐẦU Trong những năm gần đây, các thành tựu mới nhất của hệ thống tin học về phần cứng, phần mềm và các hệ quản trị cơ sở dữ liệu ổn định, tin cậy đã góp phần đáng kể cho sự phát triển của xã hội nói chung và ngành Công nghệ Thông tin nói riêng. Một trong những thành tựu nổi bật đó, phải nói đến các phần mềm cơ sở nhằm vào, trực tiếp và trước hết, tăng khả năng điều hành, khai thác hiệu quả tất cả các tài nguyên của hệ. Sự phát triển của CNTT-TT và đặc biệt là Internet, “thế giới là phẳng”. Do đó, tất cả mọi vấn đề, dù khoảng cách có xa đến đâu đi chăng nữa nhưng nếu chúng ta ngồi trước máy vi tính có nối mạng thì hầu như mọi thứ đang hiện hữu tại máy tính của chúng ta. Chúng ta có thể quản lý nhân sự của một công ty đa quốc gia, chúng ta có thể ngồi ở nhà để đăng ký đặt chỗ vé máy bay, mua một món hàng tại siêu thị… Để có được sự tiện nghi này đối với người sử dụng thì nó đặt ra nhiều vấn đề rất lớn và rất phức tạp cho các nhà nghiên cứu và phát triển các hệ thống này. Các câu hỏi lớn đặt ra một cách cụ thể như: “làm thế nào để đảm bảo rằng không có ít nhất 2 người cùng đăng ký 01 vé máy bay trong hệ thống đăng ký vé? Làm thế nào để biết được có còn một mặt hàng nào đó trong hệ thống siêu thị?”… Hệ tin học phân tán ra đời từ rất sớm, sự phát triển nhanh và mạnh mẽ của công nghệ truyền thông và của mạng Internet, cùng với xu thế toàn cầu hoá trong mọi lĩnh vực, đặc biệt là về thương mại, hệ phân tán đã và đang trở thành một lĩnh vực thu hút được nhiều sự quan tâm của các nhà nghiên cứu lý thuyết lẫn các nhà sản xuất phần mềm hiện nay. Hệ tin học phân tán hay nói ngắn gọn là hệ phân tán (Distributed System) là hệ thống xử lý thông tin bao gồm nhiều bộ xử lý hoặc bộ vi xử lý nằm tại các vị trí khác nhau và được liên kết với nhau thông qua phương tiện viễn thông dưới sự điều khiển thống nhất của một hệ điều hành. Vấn đề quan trọng là để đảm bảo các chức năng, yêu cầu đề ra, hệ phân tán cần phải có các cơ chế kỹ thuật đủ mạnh nhằm đồng bộ hoá hoạt động của các xử lý (tiến trình) và sự trao đổi thông tin với nhau sao cho hệ thống tránh được các trường hợp có thể dẫn đến bế tắc và/hoặc không gắn bó dữ liệu. Được sự phân công của Ban cán sự lớp, nhóm thực hiện đề tài: Trình bày các thuật toán cho phép phát hiện bế tắc; và Theo phương pháp Le Lann, người ta phối hợp một bộ tuần tự cho một tài nguyên găng, ví dụ Sa, Sb, Sc,...Người ta nhóm các bộ tuần tự trên một jeton duy nhất; Hãy chứng minh rằng để triển khai một chiến lược cung cấp không có rủi ro về bế tắc, người ta chỉ cần rút một số cho một tài nguyên cần thiết khi jeton chạy qua (đề 21). Trong phạm vi của tiểu luận này, với những kiến thức đã được học cũng như tự nghiên cứu thêm tài liệu từ các giáo trình, bài giảng và mạng Internet, chúng tôi xin trình bày các nội dung sau: Phần 1: Lý thuyết - Trình bày các khái quát về bế tắc, các thuâ ât toán phát hiên và â ngăn chă ân bế tắc. Phần 2: Bài tập - Trình bày giải pháp kết hợp các bô â tuần tự cho mỗi tài nguyên găng trên mô ât jeton tuần hoàn để ngăn chă ân bế tắc. Mặc dầu đã hết sức cố gắng, nhưng do điều kiện thời gian và khả năng còn nhiều hạn chế, hơn nữa tiểu luận môn học này là một lĩnh vực tri thức rộng lớn, đa dạng và rất phức tạp nên chắc chắn không thể không tránh khỏi những sai sót và khiếm khuyết. Rất mong nhận được sự góp ý, phê bình, đánh giá của Thầy giáo và của các bạn trong lớp để nhóm chúng tôi rút kinh nghiệm và hoàn thiện tốt hơn trong thời gian tới. Chúng tôi xin gửi lời cảm ơn chân thành đến Thầy giáo Lê Văn Sơn đã cung cấp, định hướng và hướng dẫn chúng tôi trong suốt thời gian qua để nhóm chúng tôi hoàn thành tiểu luận này. Tiểu luân môn học: Hê âPhân Tán â Phần 1: GVHD: PGS. TS. Lê Văn Sơn LÝ THUYẾT I. Các tài nguyên Bế tắc có thể xảy ra khi các tiến trình truy xuất độc quyền đến các thiết bị, file, v.v... Để thảo luận bế tắc, chúng ta sẽ tham chiếu đến các đối tượng như tài nguyên. Một tài nguyên có thể là một thiết bị phần cứng hay một phần của thông tin. Một máy tính có thể có nhiều tài nguyên khác nhau có thể được yêu cầu. Tài nguyên có thể phân thành hai loại: có thể thu hồi (preemptable) và không thể thu hồi (nonpreemptable).  Tài nguyên có thể thu hồi: là tài nguyên có thể được lấy ra từ tiến trình sở hữu nó. Bộ nhớ là một ví dụ của tài nguyên có thể thu hồi.  Tài nguyên không thể thu hồi được: là tài nguyên mà không thể lấy ra từ tiến trình hiện đang sở hữu nó bất kể gây ra lỗi tính toán. File, các thiết bị Vào /Ra là các tài nguyên không thể thu hồi được. Nhìn chung, các bế tắc thường xảy ra đối với các tài nguyên không thể thu hồi được. Trình tự của các sự kiện yêu cầu sử dụng tài nguyên là: - Yêu cầu một tài nguyên. - Sử dụng tài nguyên. - Giải phóng tài nguyên. Nếu tài nguyên không có giá trị khi được yêu cầu thì tiến trình yêu cầu bị chặn để chờ. Trong một số hệ điều hành, tiến trình tự động bị chặn khi tài nguyên yêu cầu bị lỗi và đánh thức dậy khi tài nguyên có giá trị. II. Định nghĩa bế tắc Một tập các tiến trình bị bế tắc nếu mỗi tiến trình trong tập tiến trình chờ một sự kiện mà chỉ có tiến trình khác trong tập các tiến trình đó tạo ra. Tất cả các tiến trình đều đang chờ, không một tiến trình nào trong chúng có thể tạo ra bất kỳ một sự kiện nào để có thể đánh thức tiến trình khác trong tập tiến trình, vì vậy tất cả các tiến trình tiếp tục chờ mãi mãi. Trong hầu hết các trường hợp, sự kiện mà tiến trình đang chờ giải phóng vài tài nguyên hiện tại mà tiến trình khác trong tập tiến trình bị chặn đang chiếm giữ. Hay nói cách khác, mỗi thành viên của tập các tiến trình bế tắc đang chờ tài nguyên là sở hữu của một tiến trình bị chặn khác. Không một tiến trình nào có thể chạy thực hiện, không một tiến trình nào có thể giải phóng tài nguyên và cũng không một tiến trình nào có thể thức dậy. Trang 4 Tiểu luân môn học: Hê âPhân Tán â GVHD: PGS. TS. Lê Văn Sơn III. Điều kiện xảy ra bế tắc Cofman, Elphick và Shosani vào năm 1971 đã đưa ra 4 điều kiện cần có thể làm xuất hiện bế tắc: 1. Có sử dụng tài nguyên không thể chia sẻ (Mutual exclusion) Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ một tiến trình, khi tiến trình sử dụng xong tài nguyên này hệ thống mới thu hồi và cấp phát tài nguyên cho hệ thống khác. 2. Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for) Tiến trình được phép giữ và yêu cầu thêm một hoặc nhiều tài nguyên và chờ cung cấp tài nguyên đang bị tiến trình khác chiếm giữ. 3. Không thu hồi được tài nguyên từ tiến trình đang giữ chúng (No preemption) Tài nguyên chỉ tự nguyện giải phóng khi sử dụng xong. Không một tiến trình nào hay hệ điều hành có thể thu hồi tài nguyên từ tiến trình đang chiếm giữ chúng. 4. Tồn tại một chu kỳ chờ trong đồ thị cấp phát tài nguyên (Circular wait) Có ít nhất hai tiến trình chờ đợi lẫn nhau: tiến trình này chờ cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại. Tất cả 4 điều kiện này cần phải ngăn chặn để bế tắc không xảy ra. Khi có đủ 4 điều kiện này thì bế tắc xảy ra. Nếu thiếu 1 trong 4 điều kiện này thì không có bế tắc. IV. Đồ thị cấp phát tài nguyên Có thể sử dụng một đồ thị để mô hình hóa viêc cấp phát tài nguyên. Đồ thị này được gọi là đồ thị định vị tài nguyên (RSG : Resource Allcation Graph): - 2 loại nút: các tiến trình được biểu diễn bằng hình tròn, và mỗi tài nguyên được hiển thị bằng hình vuông. - 2 loại cạnh: + Cạnh yêu cầu: từ tiến trình đến tài nguyên. Chỉ rõ tiến trình yêu cầu tài nguyên và chờ có được tài nguyên đó. + Cạnh chỉ định: từ tài nguyên đến tiến trình. Chỉ rõ tiến trình đang chiếm giữ tài nguyên đó. Khi một yêu cầu được thực hiện, một cạnh yêu cầu được thêm vào. Khi một yêu cầu đươc hình thành cạnh yêu cầu được chuyển sang cạnh chỉ định Khi một tiến trình giải phóng tài nguyên, cạnh chỉ định bị xóa đi Nếu đồ thị không chứa chu kỳ thì bế tắc không xảy ra Nếu đồ thị chứa một chu kỳ thì bế tắc xảy ra. Trang 5 Tiểu luân môn học: Hê âPhân Tán â GVHD: PGS. TS. Lê Văn Sơn P R P đang giữ R P R P yêu cầu R R1 P1 R2 P3 R3 Một tình huống bế tắc R4 R1 Một tình huống không bế tắc P3 P2 R2 P1 P2 R3 R4 Hình 1.1. Đồ thị cấp phát tài nguyên V. Các phương pháp xử lýý bế tắc Chủ yếu có 3 phương pháp tiếp câ ân để xử lý bế tắc: - Sử dụng một giao thức(protocol) để hê â thống không bao giờ xảy ra bế tắc. - Cho phép xảy ra bế tắc và tìm cách sửa chữa bế tắc. - Hoàn toàn bỏỏ qua bế tắc, xem như hê â thống không bao giờ xảy ra bế tắc. VI. Ngăn chặn bế tắc Để bế tắc không xảy ra cần đảm bảo tối thiểu một trong 4 điều kiện cần không xảy ra như sau: 1. Tài nguyên không thể chia sẻ: gần như không thể tránh được điêu kiện này vì bản chất tài nguyên gần như cố định. Tuy nhiên đối với một tài nguyên về kết xuất, người ta có thể dùng các cơ chế spooling để biến đổi thành tài nguyên có thể chia sẻ. 2. Sự chiếm giữ và yêu cầu thêm tài nguyên: phải đảm bảo rằng mỗi khi tiến trình yêu cầu thêm một tài nguyên thì nó không chiếm giữ các tài nguyên khác. Có thể áp đặt một trong hai cơ chế truy xuất sau: - Tiến trình phải yêu cầu tất cả các tài nguyên cần thiết trước khi bắt đầu xử lý: phương pháp này có khó khăn là tiến trình khó có thể ước lượng chính xác tài nguyên cần sử dụng vì có thể nhu cầu phụ thuộc vào quá trình xử lý. Ngoài ra nếu tiến trình chiếm Trang 6 Tiểu luân môn học: Hê âPhân Tán â GVHD: PGS. TS. Lê Văn Sơn giữ sẵn các tài nguyên chưa cần sử dụng ngay thì việc sử dụng tài nguyên sẽ kém hiệu quả. - Khi tiến trình yêu cầu một tài nguyên mới và bị từ chối nó phải giải phóng các tài nguyên đang chiếm giữ, sau đó lại được cấp phát trở lại cùng lần với tài nguyên mới: phương pháp này làm phát sinh các khó khăn trong việc bảo vệ tình toàn vẹn dữ liệu của hệ thống. 3. Thu hồi tài nguyên: cho phép hệ thống được thu hồi tài nguyên từ các tiến trình bị khóa và cấp phát trở lại cho tiến trình khi nó thoát khỏi tình trạng bị khóa. Tuy nhiên với một số loại tài nguyên, việc thu hồi sẽ rất khó khăn vì vi phạm tính toàn vẹn dữ liệu. 4. Tồn tại một chu kỳ: tránh tạo chu kỳ trong đồ thị cấp phát bằng cách cấp phát tài nguyên theo thứ tự phân cấp như sau: Gọi R = { R1, R2, ..., Rn } là tập các loại tài nguyên Các loại tài nguyên được phân thứ tự từ 1 – N, thứ tự có thể là thứ tự logic mà tài nguyên thường yêu cầu. Ký hiệu F(Ri) Các tiến trình khi yêu cầu tài nguyên phải tuân thủ quy định: khi tiến trình đang bị chiếm giữ tài nguyên Ri thì có thể yêu cầu các tài nguyên Rj nếu F(Rj) > F(Ri). VII. Thuật toán phát hiện bế tắc Khi các tài nguyên được sử dụng bởi giao dịch được xác định theo kiểu động trong quá trình thi hành giao dịch, các phương pháp dự phòng bế tắc dựa trên nền tảng các thông điệp không còn phù hợp nữa. Lúc này, ta phải sử dụng các phương pháp phát hiện và chữa trị. Phương pháp được mô tả bởi Menasce sẽ được trình bày. Phương pháp này đặt ra vấn đề sử dụng một đồ thị các tranh chấp mà việc kiểm tra các tranh chấp đó cho phép phát hiện bế tắc. Tương tự như thuật toán vừa nêu, mỗi một trạm quản lý các đối tượng riêng của mình và việc phát hiện chỉ dựa vào thông tin cục bộ. Các trạm khởi sự các giao dịch bị treo được đề phòng phát sinh bế tắc (mà bế tắc này có thể phát hiện tại một trạm nào đó) cần phải đề ra các biện pháp chữa trị cho mình. VII.1. Các định nghĩa Ta cần xác định trong mọi thời điểm giữa hai giao dịch Tj và Tk quan hệ chặn trực tiếp như sau: Tj > Tk Tồn tại ít nhất một tài nguyên bị cài then bởi Tj và yêu cầu bởi Tk nhưng không được đáp ứng. Quan hệ này được biểu hiện bằng một đồ thị gọi là đồ thị các xung đột hữu hiệu. Sự tồn tại một vòng lặp trong đồ thị này báo hiệu cho ta biết sẽ có bế tắc diễn ra. Một Trang 7 Tiểu luân môn học: Hê âPhân Tán â GVHD: PGS. TS. Lê Văn Sơn giao dịch “không bị chặn” có nghĩa là trong đồ thị biểu hiện bằng một nút mà tại đó không có cung nào dẫn đến. Giả sử rằng Tk là một giao dịch bị chặn. tập hợp tất cả các giao dịch mà có thể đạt được bằng cách chạy khắp các cung xuất phát từ Tk, theo chiều ngược lại với hướng của chúng, và gọi là tập hợp các chặn của Tk, ký hiệu là E(Tk). Các giao dịch thuộc vào E(Tk) là các giao dịch có nguồn gốc từ sự chặn của Tk. Tại một thời điểm cho trước, đồ thị các xung đột hữu hiệu sinh ra các quan hệ chặn tồn tại giữa các giao dịch của hệ. Ta ký hiệu B(Tk) là tập hợp các giao dịch bị chặn do Tk, có nghĩa là các giao dịch có thể đạt được bằng cách chạy khắp các xuất phát từ Tk. Ví dụ : Cho đồ thị các xung đột hữu hiệu như sau: T1 T2 T5 T3 Các giao dịch không chặn là T3, T4, T5 Ta có: E(T1) = { T2, T3, T4 T5 } B(T5) = { T1, T2 } T4 Đồ thị các xung đột hữu hiệu chứa vòng lặp nếu và chỉ nếu tồn tại giao dịch Tk mà tập hợp chặn của nó chứa một giao dịch bị chặn bởi Tk:  k: B(Tk)  E(Tk)  {Tồn tại vòng lặp} Nếu ta không muốn duy trì trên mỗi trạm một bản sao của đồ thị tổng quát thì cần phải xây dựng một ảnh cục bộ cho phép đánh giá các điều kiện vừa nêu trên. Đó là điều mà ta thực hiện trong giải thuật sau đây. VII.2. Thuật toán Ta ký hiệu S(Tk) là trạm nguồn của giao dịch Tk. để cho mỗi giao dịch Tk, trạm S(Tk) duy trì các tập hợp B(Tk) và E(Tk). Việc cập nhật E(Tk) cần phải được biểu hiện trên tất cả các trạm nguồn của các giao dịch thuộc B(Tk). Thực tế, giao dịch chặn Tk là phần tử của toàn bộ tập hợp chặn của các giao dịch thuộc B(Tk). Giả sử rằng Tk đã yêu cầu một tài nguyên e của trạm Si nào đó. Trên trạm này, ta thực hiện các phép toán sau đây: Trang 8 Tiểu luân môn học: Hê âPhân Tán â GVHD: PGS. TS. Lê Văn Sơn STT Phép toán Nếu e là có sẵn để dùng, yêu cầu được thoả mãn và ta ghi nhận là Tk 1 đang có tài nguyên. Nếu e đã được cung cấp cho giao dịch Tj thì thông điệp “Tj chặn Tk” 2 được truyền cho trạm S(Tj) và S(Tk). Sau này (j,k) chỉ một thông điệp như vậy. Khi nhận một thông điệp (j,k) trên một trạm S nào đó, ta thực hiện các tác động sau đây: 1. Trên trạm S(Tj) nguồn của giao dịch chặn Tk, ta thêm Tk vào tập hợp B(Tj) và kiểm tra rằng ta không làm phát sinh bế tắc, có nghĩa là: B(Tj)  E(Tj) = Ta gửi tiếp tục thông điệp (l,k) về phía các trạm nguồn của các giao dịch Tl chặn Tj nhằm cho phép các trạm S(Tl) cập nhật các tập hợp BB(Tl) của các giao dịch bị chặn bởi Tl. Song song với tác động trên, các thông điệp (l,k) được gửi về trạm nguồn của các giao dịch Tk để cập nhật tập hợp E(Tk) của các giao dịch chặn Tk. 2. Trên trạm S(Tk) nguồn của giao dịch bị chặn Tk, ta thêm Tj cho tập hợp E(Tk) và kiểm tra không có bế tắc, có nghĩa là: B(TJ)  E(Tk) = Ta gửi tiếp tục thông điệp (j,m) về phía các trạm nguồn của các giao dịch Tm bị chặn bởi Tk nhằm cho phép các trạm S(Tm) cập nhật các tập hợp E(Tm) của các giao dịch chặn Tm. Các khuyến nghị giải phóng dẫn đến thuật toán đối xứng mà ta không có điều kiện giới thiệu ở đây. Ví dụ 2: Hãy xét 3 trạm S 1, S2 và S3. Mỗi trạm Si chứa đối tượng ei và là nguồn của giao dịch Ti: T1 T2 T3 v_loai_tru_th(e1) v_loai_tru_th(e2) v_loai_tru_th(e3) ........... ............... ............... .......... ............... ............... .......... ............... ............... v_loai_tru_th(e2) v_loai_tru_th(e3) v_loai_tru_th(e1) Ta hãy tưởng tượng rằng tại thời điểm mà tất cả các giao dịch đã được thực hiện có kết quả phép toán đầu tiên của then cài. Khi đó chuyển sang thời điểm của phép toán thứ hai, các giao dịch đều bị chặn. Điều đó kéo theo các sự kiện sau đây: Trang 9 Tiểu luân môn học: Hê âPhân Tán â GVHD: PGS. TS. Lê Văn Sơn T1 trên S2 đề nghị cung cấp e2 có trên T2; S2 gửi (2,1) cho S1 và S2, từ đó ta có: E(T1) = {T2} B(T1) = B(T2) = {T1} E(T2) = T2 trên S3 đề nghị cung cấp e3 có trên T3; S3 gửi (3,2) cho S2 và S3, từ đó ta có : B(T3) = {T2} B(T3) = E(T2) = {T3} B(T2) = {T1} S2 gửi (3,1) cho S1 và từ đó sinh ra: E(T1) = {T2, T3} B(T1) = T3 trên S3 đề nghị cung cấp e1 có trên T1; S1 sinh ra T3 trong B(T1) và ta ghi nhận là: E(T1)  B(T1) = {T3} Như vậy, bế tắc được phát hiện trên S1. VIII. Kết luận Hai thuật toán vừa được giới thiệu ở trên xuất phát từ cơ sở cùng một nguyên lý tương tự. Đó là sự thiếu chắc chắn trạng thái các trạm xa phát sinh vấn đề lưu trữ một "giới hạn an toàn" nhất định. Điều đó lại ngăn cản các phép toán không kéo theo bế tắc. Nhưng bản thân hai thuật toán này, khi triển khai lại cho phép sử dụng các kỹ thuật khác nhau. Trong thuật toán dự phòng ta kiểm tra trên trạng thái từng phần một điều kiện mạnh hơn điều kiện tối thiểu. Trong thuật toán phát hiện ta có trong một trạm trạng thái của các trạm khác. Thông thường, mỗi trạm đều nhận các thông tin dư thừa. Trang 10 Tiểu luân môn học: Hê âPhân Tán â Phần 2: GVHD: PGS. TS. Lê Văn Sơn BÀI TÂÂP Theo phương pháp Le Lann, người ta phối hợp một bộ tuần tự cho một tài nguyên găng, ví dụ Sa, Sb, Sc,...Người ta nhóm các bộ tuần tự trên một jeton duy nhất. Bạn hãy chứng minh rằng để triển khai một chiến lược cung cấp không có rủi ro về bế tắc, người ta chỉ cần rút một số cho một tài nguyên cần thiết khi jeton chạy qua. I. Bộ tuần tự Bộ tuần tự là đối tượng đồng bộ cung cấp cho mỗi yêu cầu một số nhằm xác lập trật tự. Để cho 2 yêu cầu kế tiếp nhau thì 2 số liên tục nhau được cung cấp. Giá trị 0 được cấp cho yêu cầu đầu tiên. Một tiến trình muốn nhận giá trị từ bộ tuần tự S thì nó phải gọi thủ tục (hoặc hàm) có tên Phieu(S). Mỗi giá trị chỉ phục vụ cho một và chỉ một sự kiện mà thôi. Giả sử rằng tất cả các sự kiện được đánh số bởi bộ tuần tự duy nhất S. Khi một tiến trình cung cấp cho sự kiện i một số thông qua Phieu(s), ta có thể khẳng định như sau: - Các sự kiện t bao hàm các giá trị nhỏ hơn t đã được diễn ra - Số thứ tự liền kề sau t phải là t+1 Một bộ tuần tự mang 2 đặc tính sau : - Nếu a và b là 2 sự kiện được thực hiện trên cùng hàm Phieu(S), thì ta có a→b hay b→a. - Nếu a thực hiện phép t=Phieu(S) thì giá trị gán cho t là số lượng các phép Phieu(S) đã được thực hiện trước a. Đặc tính thứ nhất thể hiện việc loại trừ tương hỗ trên các phép toán Phieu(S), còn đặc tính thứ hai thể hiện tính liên tục trong khi đánh số có nghĩa là không để lại khoảng trống khi đánh số. Việc triển khai bộ tuần tự trong hệ thống một bộ xử lý hay nhiều bộ xử lý với bộ nhớ chung được tiến hành bằng cách triển khai cơ chế sơ đẳng loại trừ tương hỗ là đủ. Trong các hệ thống phân tán, việc vận dụng nó không hề đơn giản bởi vì có sự hiện diện của các kênh viễn thông sử dụng theo kiểu loại trừ tương hỗ và đặc biệt tồn tại vòng tròn duy nhất hay một kênh lan truyền duy nhất. Việc vận dụng tương đối tổng quát bộ tuần tự S trong hệ phân tán là sự chuyển động giữa các trạm của một đối tượng duy nhất gọi là ấn phong chứa giá trị hiện hành của bộ tuần tự. Khi một trạm có ấn phong, nó có thể thực hiện hàm Phieu(S). Trang 11 Tiểu luân môn học: Hê âPhân Tán â GVHD: PGS. TS. Lê Văn Sơn II. Jeton tuần hoàn Để triển khai một ấn phong có hiệu quả, đầu tiên ta phải xác định hành trình của nó trong mạng máy tính như thế nào. Phương pháp đơn giản nhất là lắp đặt các trạm nằm trên một vòng theo một chiều xác định. Mỗi trạm chỉ được liên hệ với 2 trạm gần nhất. Ta hãy xem xét một mạng được hoàn toàn nối với nhau có nghĩa là một tập hợp gồm N trạm, trong đó một trạm có thể liên lạc với các trạm khác một cách dễ dàng. Một số duy nhất bao gồm từ 0 đến N-1 được phân phối một lần cho toàn bộ trên từng trạm. Trạm i đều có trạm hàng xóm phải hay còn gọi trạm kế tiếp sau mà số trạm của nó là suc[i] và hàng xóm bên trái hay còn gọi là trạm liền kề trước mà số của nó là pred[i]. Sự mô tả này cho ta hình dung một vòng tròn ảo. Khi hoạt động bình thường, N trạm được thể hiện đầy đủ trên vòng tròn, lúc này ta có: suc[i]=i+1 modulo N pred[i]=i-1 modulo N Ấn phong được cụ thể hoá trên một vài cấu hình của các biến trạng thái và quay trên vòng tròn ảo luôn luôn theo một chiều xác định. Để vòng tròn hoạt động tốt thì cần thiết phải xây dựng lại vòng tròn khi một trạm nào đó có sự cố. Trong thuật toán Le Lann, ấn phong được cụ thể hoá bằng một thông điệp đặc biệt và gọi là Jeton tuần hoàn trên vòng tròn. Như thế việc sự cố trên mạng có thể dẫn đến mất jeton. Các biến trạng thái được duy trì trên mỗi trạm cho phép tái sinh jeton trong trườn hợp bị mất. Thuật toán triển khai ý tưởng này là: - Jeton mang giá trị là v. Mỗi một trạm j có một biến trạng thái S[j]. Trước khi phát lại Jeton vào mạng, các tác động như sau được thực hiện: S[j]:=v cho j ≠ 0 v:=v+1 mod K; S[j]:=v cho j=0 - Mỗi một lần chuyển jeton trên trạm j, một đồng hồ bảo vệ được trang bị. Nếu nó được phát động trước khi jeton đến thì j tham chiếu đến biến trạng thái S[i] của trạm liền kề trước i=pred(j) trên vòng tròn. Nếu một trong hai điều kiện sau được kiểm tra: j>i và S[j] ≠ S[i] hay j - Xem thêm -