Hệ phân tán - Chương 6: Đề tài Đồng bộ hóa (Synchronization)

Chương 6 : Đồng bộ hóa (Synchronization) Trong chương này chúng ta sẽ tìm hiểu bằng cách nào các tiến trình đồng bộ hóa được với nhau. Ví dụ, thay vì nhiều tiến trình đồng thời truy nhập vào một tài nguyên chia sẻ thì chúng cấp quyền truy nhập tạm thời cho nhau. Một ví dụ khác, nhiều tiến trình đôi khi cần trả lời cho 1 sự kiện nào đó, nói cách khác, cần xác định thông điệp m1 của tiến trình P được gửi trước hay sau thông điệp m2 cùa tiến trình Q. Đồng bộ hóa trong các hệ thống phân tán thường khó hơn rất nhiều so với đồng bộ hóa trong các hệ đơn hoặc đa xử lý. Vấn đề trong chương này hướng tới đồng hộ hóa dựa trên thời gian hoạt động, tức là thời gian có tính tương quan giữa các tiến trình hơn là thời gian tuyệt đối. Trong nhiều trường hợp, đồng bộ hóa có thể được giải quyết bằng cách một nhóm các tiến trình có thể sử dụng 1 tiến trình được thực thi bằng cách lấy trung bình một vài thuật toán lựa chọn. 6.1 Đồng bộ hóa đồng hồ (Clock Synchronization). Trong một hệ tập trung, thời gian hệ thống là rõ ràng. Khi một tiến trình muốn biết thời gian hệ thống, nó chỉ cần đưa ra 1 lời gọi hệ thống và đợi kernel trả lời. Nếu tiến trình A hỏi thời gian, ngay sau đó tiến trình B hỏi thời gian, thì thời gian mà B nhận được sẽ lớn hơn(đôi khi bằng) so với thời gian mà A nhận được. Chắc chắn không bao giờ có chuyện thời gian B nhận được nhỏ hơn A. Nhưng trong một hệ thống phân tán, đạt được sự thống nhất về thời gian như vậy không hề đơn giản. Hãy lấy 1 ví dụ đơn giản trong chương trình make của Unix. Thông thường thì trong Unix, các chương trình lớn được chia nhỏ ra nhiều file nguồn, để khi có thay đổi trong 1 file nguồn thì chỉ có file đó phải được biên dịch lại mà không phải là tất cả chương trình. Nếu 1 chương trình có 100 files, thì không nhất thiết phải biên dịch lại toàn bộ bởi 1 file bất kì thay đổi với tốc độ cao hơn bất kì 1 người lập trình nào có thể làm việc. Lệnh make làm việc hết sức đơn giản. Khi lập trình viên thay đổi file nguồn và chạy lệnh make thì thời điểm đó được đánh dấu cho tất cả các file nguồn đã bị modify. Nếu file input.c có thời gian là 2151 và file đối tượng tương ứng của nó output.o có thời gian là 2150 thì lệnh make hiểu rằng input.c đã bị thay đổi sau khi output.o được tạo ra. Như vậy cần phải biên dịch lại input.c để cho ra phiên bản output.o mới. Trong trường hợp khác, nếu thời gian của output.o là 2144 còn thời gian của input.c là 2143 thì không cần biên dịch lại file này. Như vậy lệnh make kiểm tra lại toàn bộ file nguồn và chỉ gọi trình biên dịch biên dịch những file cần thiết. Bây giờ hãy tưởng tượng những gì xảy ra trong một hệ phân tán cũng với lệnh make như trên. Nếu hệ thống không đạt được sự thống nhất về thời gian, sự việc sẽ xảy ra như trong sơ đồ sau: File output.o có thời gian là 2144, và gần như ngay sau đó, input.c bị thay đổi nhưng lại được đánh dấu thời gian là 2143 vì đồng hồ trên máy đó chậm hơn 1 chút. Do đó lệnh make sẽ không gọi trình biên dịch. Kết quả là chương trình được biên dịch ra lẫn lộn giữa các đối tượng từ file nguồn cũ và mới. Dẫn đến có lỗi trong chương trình mà lập trình viên không thể kiểm soát hoặc hiểu được. Có rất nhiều trường hợp tương tự mà ở đó việc tính toán thời gian chính xác là cần thiết. Trường hợp trên có thể được giải quyết dễ dàng bằng cách gán tem(filestamp). Thêm nữa, rất nhiều lĩnh vực cần tới việc định thời gian chính xác như môi giới tài chính, kiểm toán... Như vậy hiển nhiên là việc định thời chính xác là cực kì quan trọng. Hãy bắt đầu với một câu hỏi đơn giản: Có thể đồng bộ toàn bộ các đồng hồ trong 1 hệ phân tán không? Câu trả lời cho nó lại cực kì phức tạp. 6.1.1 Đồng hồ vật lý (Physical Clock): Gần như tất cả các máy tính đều có mạch tính thời gian. Mặc dù có thể gọi chúng là clock theo nghĩa rộng của từ này, thì thực sự chúng không hẳn là “đồng hồ” theo cách mà hệ thống sử dụng. Có lẽ từ thích hợp hơn với những mạch này là Timer(mạch định thời). Một mạch định thời sử dụng một tinh thể thạch anh đặc biệt. Khi được đặt vào một điện áp, tinh thể thạch anh này sẽ dao động với một tần số xác định tùy thuộc vào loại tinh thể, hình dáng khi cắt và điện áp đặt vào. Với mỗi tinh thể, có hai thanh ghi tương ứng là counter vả holding. Thanh ghi đếm sẽ giảm đi 1 bit với mỗi dao động của tinh thể. Khi thanh ghi đếm về 0, mạch sẽ gọi 1 ngắt để nạp lại giá trị mới cho thanh ghi đếm từ thanh ghi holding. Như vậy việc lập trình cho một mạch định thời chạy dưới một tần số bất kì là hết sức dễ dàng. Mỗi 1 ngắt trong mạch như vậy gọi là 1 clock tick(nhịp đồng hồ). Khi hệ thống được khởi động, nó thường yêu cầu người dùng nhập ngày tháng và thời gian, rồi chuyển đổi thành số nhịp tương ứng tính từ 1 thời điểm xác định lưu trữ trong bộ nhớ. Hầu hết các máy tính có 1 CMOS RAM chạy pin làm nhiệm vụ back up thời gian để mỗi lần khởi động sau đó không cần phải nhập nữa. Với mỗi nhịp đồng hồ, thủ tục ngắt cộng thêm 1 vào thời gian trong bộ nhớ. Bằng cách này, đồng hồ(của phần mềm) được cập nhật. Với một máy tính đơn lẻ và một đồng hồ đơn lẻ, việc đồng hồ chạy sai hoặc ngừng một thời gian không phải vấn đề gì lớn lắm. Vì tất cả tiến trình trên máy sử dụng chung một đồng hồ nên chúng có sự thống nhất. Khi hệ thống đa xử lý ra đời, mỗi 1 CPU có đồng hồ riêng, tình thế đã thay đổi hoàn toàn. Mặc dù tần số dao động của các tinh thể thường khá là ổn định, nhưng thật khó để cho các tinh thể khác nhau dao động cùng 1 tần số. Trong thực tế, khi một hệ thống có n máy tính, tất cả n tinh thể hầu như dao động với n tần số khác nhau, làm cho đồng hồ(của phần mềm) dần dần cách xa nhau về mặt thời điểm và cho các giá trị khác nhau. Sự sai khác này gọi là clock skew(sự sai lệch đồng hồ). Hậu quả của sự sai lệch này là các chương trình dựa vào thời gian được gán cho file, đối tượng, tiến trình hoặc thông điệp độc lập với máy sinh ra chúng có thể bị lỗi, như ví dụ với lệnh make ở trên. Trong một số hệ thống(ví dụ như các hệ thống thời gian thực), thời gian hiện tại là rất quan trọng. Chính vì thế việc sử dụng các đồng hồ vật lý bên ngoài là cần thiết. Vì các lý do hiệu suất và độ phức tạp, việc phát triển một hệ thống các đồng hồ vật lý như vậy đặt ra 2 vấn đề lớn: (1) Làm sao để đồng bộ chúng với các đồng hồ thực tế trên thế giới, và (2) làm sao để đồng bộ chúng với nhau? Trước khi trả lời các câu hỏi trên, hãy xem xét sơ qua làm sao chúng ta đo được thời gian. Ban đầu, người ta tính thời gian dựa trên sự dịch chuyển của mặt trời trên bầu trời(vốn dĩ do sự tự quay quanh trục của trái đất). Theo đó, khoảng thời gian giữa 2 lần mặt trời xuất hiện liên tiếp ở cùng 1 vị trí được gọi là ngày mặt trời. Mỗi một ngày mặt trời được chia ra làm 86400 giây mặt trời. Như mô tả của hình dưới đây: Vào những năm 40 của thế kỉ trước, người ta phát hiện ra rằng sự quay của trái đất là không ổn định. Theo đó, trái đất đang quay chậm dần đều dưới tác động ma sát của thủy triều và bầu khí quyển. Dựa vào các mẫu vật san hô cổ đại, các nhà địa chất tin rằng 300 triệu năm trước một năm có tới 400 ngày(hơ hơ, thế thì 1 ngày chỉ có vỏn vẹn 22 tiếng). Thực tế thì khoảng thời gian của 1 năm hầu như ko đổi(chính là khoảng thời gian trái đất quay 1 vòng quanh mặt trời); nhưng độ dài của 1 ngày đã bị thay đổi. Thêm nữa, sự bất ổn trong nhân trái đất vốn cấu thành từ kim loại nóng chảy cũng gia tăng độ thiếu tin cậy trong cách tính thời gian này. Người ta đành đo khoảng thời gian của 1 số cực lớn các ngày, lấy trung bình và chia khoảng thời gian trung bình đó ra làm 86400 giây mặt trời. Vào năm 1948, phát minh ra đồng hồ nguyên tử đã làm cho việc đo thời gian chính xác hơn rất nhiều, đồng thời tách khái niệm thời gian ra khỏi sự vận động của trái đất. Đồng hồ nguyên tử hoạt động dựa trên cơ sở đếm số dao động trạng thái của nguyên tử Cesium(Cs) 133(số lần chuyển tiếp giữa hai mức trạng thái năng lượng). Mỗi 1 giây, nguyên tử Cs dao động 9 192 631 770 lần. Hiện tại, một vài phòng thí nghiệm rải rác trên thế giới có đồng hồ Cs 133. Các phòng thí nghiệm này định kì gửi kết quả đến Ủy ban giờ quốc tế(BIH) đặt tại Paris, BIH sẽ lấy trung bình các kết quả này để đưa ra Giờ nguyên tử quốc tế(TAI). Giá trị TAI này là số dao động của đồng hồ Cs 133 tính từ nửa đêm ngày 1 tháng 1 năm 1958 đến nay chia cho 9 192 631 770. Tuy nhiên, vấn đề đặt ra ở đây là TAI tuy chính xác tuyệt đối nhưng lại “trượt pha” so với giờ mặt trời. Hiện tại, cứ 86400 giây TAI lại ít hơn so với ngày mặt trời thực tế là 3 mili giây. Sử dụng TAI đồng nghĩa với việc chúng ta chấp nhận rằng sau mỗi năm, buổi trưa sẽ đến càng lúc càng sớm hơn(12h trưa mà vẫn chưa đứng bóng). (cái ví dụ về Giáo hoàng Gregory hơi chuối củ và quá xa chủ đề, tốt nhất là quên nó đi và công nhận Tanenbaum quá đỉnh ở MIT) BHI giải quyết vấn đề này bằng cách đưa ra khái niệm nhảy giây(leap seconds-cấm nhầm với trò chơi con gái nhá). Tức là khi khoảng cách giữa TAI và thời gian mặt trời đạt tới 800 mili giây, sẽ có 1 bước nhảy như mô tả trong hình sau: Bước nhảy này giúp cho thời gian khoa học vẫn chính xác, nhưng lại không bị lệch đi so với thời gian mặt trời(đại loại như năm nhuận ý ạ). Hệ thống này được gọi là Giờ thống nhất vũ trụ(Universal Coordinate Time)-UTC. UTC là cơ sở cho mọi hệ thống định giờ hiện đại thay thế cho hệ thống giờ thiên văn quốc tế GMT. Hầu hết các công ty điện tử lớn đồng bộ các đồng hồ 60 hoặc 50Hz với giờ UTC, do vậy khi BIH cho thời gian nhảy giây 1 bước, các công ty này chỉ cần nâng tần số lên 61 hoặc 51 Hz. Kể từ khi 1 giây trở nên là 1 khoảng thời gian đáng kể so với hoạt động của 1 máy tính thì hệ điều hành của nó cần duy trì sự chính xác của thời gian qua hàng năm trời. Để làm được điều này, hđh cần có 1 phần mềm đặc biệt chuyên tính toán số giây phải nhảy. Viện thời gian chuẩn quốc gia NIST của Mỹ đã lập ra một trạm phát sóng ngắn, tạm gọi là WWV tại Fort Collins, Colorado để cung cấp thời gian UTC chính xác. WWV phát ra một xung ngắn ứng với mỗi giây UTC. Sai số của xung này tại nguồn là vào khoảng 1 mili giây, nhưng dưới điều kiện bầu khí quyển thì sai số thực tế của nó là 10 mili giây. Một vài quốc gia khác cũng có các trạm phát sóng như vậy. GEOS là một hệ thống vệ tinh địa tĩnh cũng cung cấp dịch vụ tương tự. 6.1.2 Hệ thống định vị toàn cầu GPS: Hãy xem xét một ví dụ cụ thể: hệ thống định vị toàn cầu GPS. GPS sử dụng 29 vệ tinh địa tĩnh ở độ cao xấp xỉ 20 000km trên mỗi vòng quỹ đạo trái đất nhằm xác định chính xác vị trí của một đối tượng. Mỗi vệ tinh có khoảng 4 đồng hồ nguyên tử tường xuyên cập nhật với các trạm mặt đất. Một vệ tinh tiếp tục thông báo vị trí của chúng và gán nhãn thông điệp với thời gian hiện tại(giờ địa phương mà đồng hồ trên vệ tinh thông báo). Điều này cho phép máy nhận thông điệp có thể tính toán chính xác vị trí của nó chỉ với 3 vệ tinh “trên đầu”. Ý tưởng của hệ thống như sau: các vệ tinh địa tĩnh được bố trí trên quỹ đạo 20,000km so với mặt đất; mỗi vệ tinh có từ 1 đến 4 đồng hồ nguyên tử nhằm đảm bảo giờ địa phương của nó luôn chính xác, các đồng hồ này còn luôn được đồng bộ với các trạm đặc biệt trên mặt đất, tóm lại giờ của nó là giờ UTC; một thiết bị GPS khi yêu cầu xác định vị trí sẽ nhận được các thông điệp từ vệ tinh có chứa nhãn thời gian thông báo giờ hiện tại trên vệ tinh và tọa độ của vệ tinh với hệ kinh vĩ tuyến trái đất. Giờ của mỗi vệ tinh giúp thiết bị tính được khoảng cách giữa nó và vệ tinh bằng cách trừ đi giờ hiện tại trên thiết bị và nhân với vận tốc sóng truyền tới(vận tốc ánh sáng). Tọa độ của thiết bị là 1 bộ 3 số có thể được tính dựa vào thông tin nhận về từ ít nhất 3 vệ tinh, theo lý thuyết. 6.1.3 Các giải thuật đồng bộ hóa vật lý (Clock synchronization algorithm). Nếu tất cả các máy tính đều có WWV Receiver thì việc đồng bộ chúng là dễ dàng vì tất cả đều cùng đồng bộ với giờ chuẩn quốc tế UTC.Tuy nhiên khi không có WWV thì việc đồng bộ được thực hiện bằng các giải thuật đồng bộ sau. a. Giải thuật Cristian Giả sử trong hệ phân tán có một máy có WWV (gọi là Time server ) và chúng ta sẽ tiến hành đồng bộ các máy khác với máy này.Trong khoảng thời gian δ/2p mỗi máy sẽ gửi một thông điệp đến máy chủ hỏi thời gian hiện tại. Máy chủ nhanh sẽ phản hồi bằng một thông điệp mang giá trị thời gian C(utc).Bên gửi nhận được phản hồi nó sẽ thiết lập lại clock thành C(uct). Hình . Xác định thời gian trong time server Đánh giá: giải thuật này có 2 vấn đề : - Một là nếu clock bên gửi chạy nhanh thì lúc này C(uct) sẽ nhỏ hơn thời gian hiên tại C của bên gửi..Có thể giải quyết bằng cách thay đổi nhịp ngắt lại nhanh hơn hoặc chậm hơn cho đến lúc khớp nhau. - Hai là sự chênh lệch từ lúc C(uct) được gửi cho đến lúc nhận được có thể gây lỗi.Giải quyết bằng cách ghi nhận khoản thời gian giữa lúc gửi và nhận b. Giải thuật Berkeley. Tư tưởng của giải thuật: Server sẽ chủ động cho các máy khác biết thời gian chuẩn của mình CUTC sau đó sẽ yêu cầu thông tin về thời gian của các client. Client sẽ trả lời khoảng thời gian chênh lệch giữa nó và server. Server sẽ tính khoảng thời gian mà các client so với thời gian chuẩn của server lúc đó và gửi cho các máy khách cách điều chỉnh thời gian cho phù hợp. - Hình . Đồng bộ theo giải thuật Berkeley c. Giải thuật trung bình sử dụng cho các mạng không dây Giải thuật này sử dụng trong giao thức RBS. Giải thuật này thực hiện chia thời gian thành những khoảng đồng bộ cố định. Khoảng thời gian i sẽ bắt đầu từ thời điểm (To + i.R) và chạy đến khi To+(i+1)R với To là thời điểm xác định trước và R là một biến hệ thống . Vào thời điểm bắt đầu của mỗi lần đồng bộ tất cả các máy của mạng sẽ broadcast thời gian của mình . Sau khi broadcast nó sẽ bắt đầu thu thập thời gian mà các máy khác gửi đến trong khoảng thời gian S. Sau đó bỏ đi giá trị lớn nhất và nhỏ nhất rồi tính trung bình của các giá trị thời gian còn lại. 6.2 Đồng hồ logic (Logical Clock) Trong nhiều trường hợp, giữa các tiến trình không nhất thiết phải phù hợp theo thời gian thực tế mà chỉ cần khớp với nhau về thời gian. Do đó người ta đưa ra khái niệm đồng hồ logic. 6.2.1 Nhãn thời gian Lamport (Lamport timestamps). Lamport đã đưa ra mô hình đồng hồ logic đầu tiên cùng với khái niệm nhãn thời gian. a. Xét định nghĩa mối quan hệ “xảy ra trước” (à) Khi có Aà B : A xảy ra trước B thì tất cả các tiến trình trong hệ phân tán thỏa thuận sự kiện A xảy ra trước rồi đến sự kiện B. A và B là hai sự kiện của cùng một tiến trình. Nếu A xảy ra trước B thì AàB là đúng. Nếu A là sự kiện bản tin được gửi bởi một tiến trình nào đó, còn B là sự kiện bản tin đó được nhận bởi một tiến trình khác thì quan hệ Aà B là đúng. Quan hệ xảy ra trước có tính bắc cầu: Aà B , Bà C thì Aà C. b. Tem thời gian (Time Stamps) Để đo thời gian tương ứng với 4 sự kiện x thì ta gán một giá trị C(x) cho sự kiện đó và thỏa mãn các điều kiện sau: Nếu Aà B trong cùng một tiến trình thì C(A) < C(B). Nếu A và B biểu diễn tương ứng việc gửi và nhận một thông điệp thì ta có C(A)< C(B) Với mọi sự kiện phân biệt (không có liên quan) thì C(A)C(B) 6.2.2 Vector thời gian (Vector Timestamps) Giải thuật vector timestamp đưa ra một vetor timestamp VT(a) gán cho sự kiện a có thuộc tính là nếu Vtt(a) < VT(b) thì sự kiện là nguyên nhân của b. Trong vector thời gian mỗi tiến trình Pi lưu giữ một Vi với giá trị N (các tiến trình khác nhau thì N khác nhau) - Vi[i] là số các sự kiện đã xảy ra tại Pi - Nếu Vi[j] = k nghĩa là Pi biết đã có k sự kiện đã xẩy ra tại Pj Yêu cầu: mỗi khi có sự kiện mới xảy ra ở tiến trình Pi thì phải tăng Vi[i] và phải đảm bảo vector này được gửi cùng thông điệp suốt trong quá trình. Nhờ đó bên nhận sẽ biết được đã có bao nhiêu sự kiện xảy ra tại Pi .Quan trọng hơn phía nhận sẽ báo cho biết là đã có bao nhiều sự kiện ở các tiến trình khác đã xảy ra trước khi Pi gửi thông điệp m.Nói cách khác timestamp VT của n nói cho bên nhận biết bao nhiêu sự kiện đã xảy ra trong các tiến trình khác trước m. Luật cập nhật vector - Thiết lập Vi[j] =0 với mọi j,i - Sự kiện xảy ra ở Pi là nguyên nhân tăng Vi[i] - Pi gắn một timestamp t=V[i] vào mọi thông điệp gửi đi - Khi Pi nhân được một thông điệp có t nó sẽ thiết lập Vi[j]=Max(Vi[j] ,t[j]) và tăng Vi[i] 6.3 Loại trừ lẫn nhau Nguyên tắc cơ bản của hệ phân tán là sự đồng thời và cộng tác của những đa tiến trình. Trong nhiều trường hợp , điều này có nghĩa là những tiến trình cần truy cập cùng một lúc cùng một tài nguyên. Để tránh điều này giải pháp là cho phép xử lý truy cập theo kiểu lọai trừ lẫn nhau. Thuật toán Phân tán loại trừ lẫn nhau có thể được phân lớp thành 2 giải pháp khác nhau: giải pháp loại trừ lẫn nhau theo biểu tượng và permission-base solution. A. Phương pháp thứ nhất đạt được bằng cách đưa ra một thông điệp đặc biệt giửa các tiến trình, được gọi là biểu tượng – token. Chỉ có 1 token sẵn sang và ai là người có token này được phép truy cập đến tài nguyên chia sẻ. Phương pháp này có một số đặc tính quan trọng. + Đầu tiên là nó phụ thuộc vào các làm thế nào để tổ chức các tiến trình, những đặc tính này dễ dàng bảo đảm cho mọi tiến trình có một sự thay đổi trong cách truy cập tài nguyên. Nói cách khác, những đặc tính này tránh sự thiếu tài nguyên + Do deadlock ,tiến trình phải đợi những tiến trình khác để được xử lý, có thể tránh deadlock một cách dễ dàng bằng cách đóng góp vào sự đơn giản của các tiến trình. Không may là trở ngại chính của token-base solution lại nghiêm trọng hơn, một chương trình con phức tạp được phân phối cần được chạy để chắc chắn rằng một token mới đựoc tạo ra nhưng cái chính là token đó phải token duy nhất Phương pháp thứ 2: một tiến trình muốn truy cập vào tài nguyên thì phải được sự cho phép của các tiến trình khác. Có nhiều cách để có được sự cho phép và được chỉ ra dưới đây Thuật toán tập trung: Cách dễ hiểu nhất để đạt được sự loại trừ lẫn nhau trong hệ thống phân tán là giả lập cách nó thực hiện trong hệ thống một Bộ xử lý. Một tiến trinh được bầu như một bộ điều phối. Bất cứ lúc nào một tiến trình muốn truy cập những tài nguyên chia sẻ, nó gửi một thông điệp yêu cầu tới bộ điều phối đang thống kê xem loại tài nguyên nào mà tiến trình muốn truy cập và xin phép truy cập. Nếu như không có tiến trình nào đang truy cập tào nguyên, bộ điều phối sẽ gửi lại tiến trình xin phép một thông điệp cho phép truy cập hệ thống Ưu điểm và tính chất: Dễ dàng thấy rằng giải thuật đảm bảo sự loại trừ lẫn nhau: bộ điều phối chỉ để một tiến trình truy cập tài nguyên trong 1 thời điểm. Điều này khá tốt nếu các yêu cầu được chấp nhận theo thứ tự mà chúng được nhận. Không có tiến trình nào phải đượi vô thời hạn. Sự xắp xếp này dễ thực thi và chỉ yêu cầu 3 thông điệp cho mỗi lần sử dụng tài nguyên (gồm: yêu cầu truy nhập tài nguyên, sự cho phép và giải phóng tài nguyên). Điều này tạo ra một giải pháp hấp dẫn cho nhiều tình huống thực tế. Hạn chế: Nếu như bộ điều phối lỗi, hệ thống thực thể có thể sẽ bị down. Nếu các tài nguyên làm trở ngại một cách bình thường sau khi tạo yêu cầu thì chúng không thể phân biệt một bộ điều phối đã chết với một từ chối truy cập trong trường hợp không thông điệp nào quay lại. Trong một hệ thống lớn, một bộ điều phối đơn có thể trở thành một thắt cổ chai Sự đơn giản của giải thuật trong nhiều trường hợp mang lại nhiều trở ngại. Thuật tóan không tập trung Thuật tóan được đề cửa sử dụng trong hệ thống dựa trên DHT. Giải pháp là mở rộng những bộ phân phối tập trung theo cách sau: Mỗi tài nguyên được gán một bản sao n lần. Mỗi bản sao có bộ phân phối của nó để điều khiển việc truy nhập bởi những tiến trình thực thi đồng thời Dù vậy, mỗi khi một tiến trình muốn truy cập tài nguyên nó phải được sự cho phép của m >= n/2 bộ điều phối. Không giống như giải pháp tập trung được đưa ra ở trên(trong trường hợp b của ví dụ), khi một bộ điều phối không đưa ra sự đồng ý để truy cập tài nguyên, nó sẽ cho tiến trình yêu cầu tài nguyên biết Khi một bộ điều phối bị hỏng, nó nhanh chóng được khôi phục nhưng lại không nhớ được số vote mà nó đã có trứoc đó., hay nói cách khác là bộ điều phối tự khởi động lại ở thời điểm bất kỳ mà lỗi xảy ra. Nếu như yêu cầu truy cập tài nguyên bị từ chối thì nó sẽ được trả lại một biến thời gian chờ chọn ngẫu nhiên và cố thực hiện lần sau. Vấn đề của thuật tóan này là nếu có nhiều nút muốn truy cập đến cùng một tài nguyên thì hệ thống nhanh chóng lỗi, hay nói cách khác có có rất nhiều nút hoàn thành việc truy câp nhưng không nút nào có đủ n/2 bầu chọn để rời khỏi tài nguyên không sử dụng. 6.3.4. Thuật tóan phân tán Khi một tiến trình muốn truy cập vào một tài nguyên chia sẻ, nó tạo một thông điệp bao gồm tên của tài nguyên, số xử lý của nó và thời gian(theo logic) hiện tại. Sau đó nó gửi thông điệp này tới các tiến trình khác và chính nó. Việc gửi các thông điệp đi là đáng tin cậy và thông điệp nào bị mất Khi tiến trình nhận một thông điệp yêu cầu từ tiến trình khác, ứng xử của nó phụ thuộc vào trạng thái của nó với tài nguyên được đặt tên trong thông điệp. Có 3 trường hợp khác nhau được phân biệt rõ ràng: Nếu bên nhận đang không hoặc không muốn truy nhập vào tài nguyên, nó sẽ gửi lại thông điệp là OK tới bên gửi Nếu bên nhận vừa truy cập tài nguyên, nó đơn giản là không phản hồi lại thông điệp yêu cầu, thay vào đó, nó xếp hàng thông điệp yêu cầu đó. Nếu bên nhận cũng muốn truy cập tài nguyên nhưng chưa được phép, nó sẽ so sánh nhãn thời gian (timestamp) của thông điệp gửi đến với timestamp chứa trong thông điệp mà nó gửi đi cho những tiến trình khác. Nếu thông điệp đến có timestamp thấp hơn, bên nhận sẽ gửi thông điệp OK, nếu không thì nó không gửi gì cả Sau khi gửi các gói tin yêu cầu cho phép, một tiến trình đợi đến khi các tiến trình khác cho phép và ngay sau khi các tiến trình cho phép, tiến trình này truy cập tài nguyên. Khi nó kết thúc, nó gửi 1 thông điệp OK đến tất cả các tiến trình khác ở trong hàng đợi của nó và xóa nội dung hàng đợi đó Giải thích ví dụ: Tiến trình 0 gửi 1 yêu cầu với timestamp = 8 đến tất cả các tiến trình. Trong cùng thời điểm đó, tiến trình 2 cũng làm tương tự với timestamp = 12. Tiếng trình 1 không muốn truy cập tài nguyên, vì thế nó gửi OK đến cả 2 bên gửi. Cả tiến trình 0 và 2 nhận ra sự xung đột và cùng so sánh timestamp. Tiến trình 2 thua và nó phải gửi thông điệp OK đi. Tiến trình 0truy cập vào tài nguyên và xếp tiến trình 2 vào hàng đợi của nó để xử lý và truy cập tài nguyên. Sau khi kết thúc, nó loại bỏ yêu cầu từ tiến trình 2 khỏi queue của nó và gửi thông điệp OK đến tiến trình 2 và cho phép nó thực hiện. Hạn chế: - Khi tổng số lượng tiến trình trong hệ thống là n thì yêu cầu 2(n-1) thông điệp cho mỗi thực thể . - Nếu bất cứ 1 tiến trình nào lỗi, nó sẽ gây lỗi thông điệp phản hồi yêu cầu và khiến toàn bộ các tiến trình tiến vào vùng giới hạn - Thuật toán này chậm, phức tạp và chi phí đắt và ít mạnh mẽ như thuật tóan tập trung 6.3.5. Giải thuật vòng với thẻ bài (TokenRing Algorithm). Giả thiết tất cả các tiến trình được sắp xếp trên một vòng tròn logic, các tiến trình đều được đánh số và đều biết đến các tiến trình cạnh nó. Hình . Ví dụ theo giải thuật vòng với thẻ bài Bắt đầu quá trình truyền, tiến trình 0 sẽ được trao một thẻ bài. Thẻ bài này có thể lưu hành xung quanh vòng tròn logic. Nó được chuyển từ tiến trình k đến tiến trình (k+1) bằng cách truyền thông điệp điểm – điểm. Khi một tiến trình giành được thể bài từ tiến trình bên cạnh nó sẽ kiểm tra xem có thể vào vùng tới hạn hay không. Nếu không có tiến trình khác trong vùng tới hạn nó sẽ vào vùng tới hạn. Sau khi hoàn thành phần việc của mình nó sẽ nhả thẻ bài ra, thẻ bài có thể di chuyển tự do trong vòng tròn. Nếu 1 tiến trình muốn vào vùng tới hạn thì nó sẽ giữ lấy thẻ bài, nếu không nó sẽ để cho thẻ bài truyền qua. Hạn chế: Vấn đề lớn nhất trong thuật toán truyền thẻ bài là thẻ bài có thẻ bị mất, khi đó chúng ta phải sinh lại thẻ bài bởi vì việc dò tìm lại thẻ bài là rất khó. 6.3.6 So sánh 4 giải thuật 6.4 Định vị các node Khi các node trong mạng tăng, việc quản lý sẽ khó khăn .Việc định vị các node sẽ đóng vai trò quan trọng. Ứng dụng rất nhiều trên thực tế: + Trong mô hình client-server khi server có các bản sao được đặt nhiều nơi trên mạng, khi client gửi request DNS sẽ chọn server gần client nhất để tăng thời gian reply. + Cũng trong mô hịnh này, việc định vị các client của nó là cần thiết khi tinh toán vị trí đặt bản sao của server một cách hiệu quả + Một ví dụ khác, trong thuật toán định tuyến based position, các node trung gian sẽ chuyển thông diệp cho láng giềng gần nhất. Trong bản đồ của mạng rộng khắp, mỗi node sẽ có một vị trí trong không gian m hướng, và khoảng cách giữa hai node trong bản đồ sẽ phản ánh khoảng cách thực. Theo lý thuyết, để xác định vị trí của một node trong không gian m hướng thì cần m+1 thông số khoảng cách( minh họa với trường hợp m=2). Trong hệ thống định vị toàn cầu p(xp,yp) được các định khi giải hệ phương trình. Tuy nhiên do di được tính tương ứng với độ trễ của gói tin khi truyền giữa P và các node (xi,yi) nên khoảng cách này sẽ không đồng nhất khi thực hiện các lần xác định khác nhau , dẫn đến sai khác khi xác định vị trí của P. Cách giải quyết-> tăng số node Sử dụng L node đặc biệt b1,…,bL gọi là landmarks. Vị trí của P sẽ được xác định là các thông số làm tối thiểu hóa hàm Trong đó d(bi,P) là khoảng cách đã được xác định bằng số tỷ lệ với độ trễ khi truyền gói giữa hai điểm p & bi, còn d^(bi,P) là khoảng cách hình học(căn tổng bình phương hiệu các tọa độ). 6.5 Các giải thuật bầu chọn (Election Algorithm). Khi tiến trình điều phối gặp lỗi thì sẽ phải có quá trình bầu chọn để chọn ra một tiến trình khác làm điều phối thay cho nó. 6.5.1 Các giải thuật bầu chọn truyền thống 6.5.1.1 Giải thuật áp đảo (Bully Algorithm) Với giả thiết: Mỗi một tiến trình đều có một ID duy nhất.Tất cả các tiến trình khác đều có thể biết được số ID và địa chỉ của mỗi tiến trình trong hệ thống. Các bước của giải thuật: 1.P gửi thông điệp ELEC đến tất cả các tiến trình có ID cao hơn 2.Nếu không có tiến trình nào phản hồi thì P sẽ trở thành tiến trình điều phối 3.Nếu có một tiến trình có ID cao hơn phản hồi thì nó sẽ đảm nhiệm vai trò điều phối. Hình .Ví dụ theo giải thuật áp đảo 6.5.1.2 Giải thuật vòng (Ring Algorithm) Với giả thiết : Các tiến trình có một ID duy nhất và được sắp xếp trên 1 vòng tròn Logic. Mỗi một tiến trình có thể nhận biết được tiến trình bên cạnh mình. Các bước thuật toán: Một tiến trình bắt đầu gửi thông điệp ELEC tới các nút còn tồn tại gần nhất, quá trình gửi theo 1 hướng nhất định. Thăm dò liên tiếp trên vòng cho đến khi tìm được 1 nút còn tồn tại. Mỗi một tiến trình sẽ gắn ID của mình vào thông điệp gửi. Cuối cùng sẽ chọn ra 1 tiến trình có ID cao nhất trong số các tiến trình còn hoạt động và gửi thông điệp điều phối cho tiến trình đó. 6.5.2 Bầu chọn trong môi trường không dây Các thuật toán bầu chọn truyền thống dựa trên việc thừa nhận những điều kiện không được thỏa mãn trong môi trường không dây, ví dụ như việc thừa nhận các thông điệp được truyền tin cậy và topo mạng không thay đổi ->dẫn đến ra đời thuật toán bầu chọn trong mạng không dây. Trong môi trường không dây, việc bầu chọn được tiến hành một cách chặt chẽ chứ không phải lấy random như trong các thuật toán bầu chọn truyền thống. Để đơn giản, ta tập trung vào mạng adhoc và không quan tâm đến việc các node có thể di chuyển ( ;)) ) Giải thuật: - Đầu tiên một node trong mạng ( gọi là source) sẽ gửi thông điệp bầu chọn( ELECTIONmessage ->MS) đến các node láng giềng trực tiếp với nó( ví dụ như các node trong cùng dải địa chỉ) - Một node khi lần đầu nhận được MS nó sẽ coi node gửi là cha, sau đó nó gửi MS cho các node láng giềng trực tiếp của nó ( trừ node cha). Nếu một node nhận được MS từ một node không phải node cha của nó, nó sẽ nhanh chóng gửi báo nhận. - Thứ tự gửi báo nhận của một node (quan trọng): + R có cha là Q, sau khi nhận MS từ Q nó chuyển tiếp MS cho các láng giềng trực tiếp ( trừ Q) , sau đó đợi báo nhận từ các node đó gửi về rồi mới gửi báo nhận cho Q. + Trường hợp đặc biệt : nếu tất cả các láng giêng của R đều đã có node cha, R sẽ là node lá, nó sẽ nhanh chóng gửi báo nhận cho Q kèm theo các thông tin như thời gian pin và các tài nguyên của nó + Dựa vào thông tin này Q so sánh tài nguyên của nó , R và các node con khác của nó để chọn ra node thích hợp.Sau đó Q gửi tiếp thông tin mà nó đã chọn được lên cho node cha.Quá trình lan truyền đến gốc . Nếu trong mạng có nhiều cuộc bầu chọn được thiết lập, mỗi node sẽ quyết định tham gia vào một cuộc bầu chọn duy nhất.Sau quá trình bầu chọn này sẽ là quá trình bầu chọn giữa các node thắng cuộc, cuối cùng sẽ chọn được một node duy nhất làm node điều phối. 6.5.3 Bầu chọn trong hệ thống rộng khắp Các thuật toán vừa đề cập sử dụng trong các hệ phân tán nhỏ và chỉ chọn một node duy nhất làm node điều phối. Trường hợp có nhiều node được chọn ( như trong trường hợp superpeers trong mạng p2p) -> thuật toán khác. Các điều kiện cần thỏa mãn: Các node bình thường có thể truy cập ít trễ tới superpeers ( normal nodes should have low-latency access to superpeers) Superpeers được phân bố trên toàn mạng. Phải phân chia trước mỗi superpeer sẽ phục vụ bao nhiêu node trong mạng. Mỗi superpeer không nên phục vụ quá một số node nhất định. Rất may những điều kiện này được thỏa mãn trong hầu hết các mạng P2P,gồm cả mạng có cấu trúc và không có cấu trúc. Trong mạng có cấu trúc, mỗi node được gán một id m bit.Ý tưởng cơ bản là sẽ dành k bit đầu để định danh superpeers. Nếu mạng cần N superpeers ta sẽ phải dành log2(N) bit đầu để định danh superpeers. Mộ cách tiếp cận hoàn toàn khác là dựa vào vị trí các node trong không gian m hướng.Giả thiết cần N superpeers, ý tưởng: dưa N thẻ bài rải khắp mạng tới các node ngẫu nhiên.Không node nào được giữ quá 1 thẻ bài.Mỗi thẻ bài có một lực đẩy khiến cho các thẻ bài khác di chuyển.Điều này sẽ khiến chúng cùng di chuyển và trải rộng khắp mạng.Nếu có nhiều lực cùng tác động, hướng di chuyển của thẻ bài sẽ là hướng của lực tổng hợp.Nếu một node giữ thẻ bài vượt quá một lượng thời gian, nó sẽ tự thăng cấp thành superpeers.