Đề thi Hệ Phân Tán K47

Đề k47
Đề chẵn
Cau 1: Trình bày ngắn gọn về nguyên lý và so sánh các middleware truyền thông sử dụng trong HPT
Cau 2: Tem thời gian là gì và nó được sử dụng để đồng bộ hóa như thế nào trong HPT
Cau 3: So sánh phương pháp phục hồi lùi và phục hồi tiến trong HPT
Đề lẻ
Cau 1: Trình bày ngắn gọn về nguyên lý và so sánh các mô hình di trú mã trong HPT
Cau 2: Phân giải tên là gì? Nó được sử dụng như thế nào trong HPT.
Cau 3: So sánh các mô hình nhất quán chặt và nhất quán tuần tự trong HPT

Câu 1 đề K47 ( đề chẵn ):
Như chúng ta đã biết, mạng máy tính hiện nay được xây dựng dựa theo mô hình phân tầng OSI, gồm bảy tầng với các nhiệm vụ chức năng khác nhau.
Trong hệ phân tán, người ta gộp tầng thứ năm và thứ sáu (tầng phiên và tầng trình diễn) thành một tầng mới gọi là tầng middle ware. Vì vậy ta cũng phải xây dựng các giao thức tương ứng cho tầng middleware này.
Có 4 mô hình dịch vụ middleware phổ dụng mà ta sẽ xét lần lượt sau đây:
–   Gọi thủ tục từ xa RPC (Remote Procedure Call).
–   Triệu gọi đối tượng từ xa (Remote Object Invocation)
–   Middleware hướng thông điệp (Message – oriented Middleware)
–   Middleware hướng dòng (Stream – oriented Middleware)
So sánh:
+Giống nhau : đều là các middleware được sử dụng với mục đích tăng tính mềm dẻo, trong suốt và hiệu quả cho hệ thống, tạo giao diện và cung cấp dịch vụ tốt cho tầng vận chuyển phía dưới.
+Khác nhau:
1.rpc:Được sử dụng rộng rãi nhất ưu điểm là đơn giản, hướng tới sự trong suốt về truy cập. Tuy nhiên những tham chiếu thông qua việc gọi thủ tục từ xa là hạn chế.
2.roi:Bản chất là một rpc nhưng điều đặc biệt là nó hướng tới đối tượng phân tán. Điểm khác biệt chính với rpc là roi cung cấp các thủ tục rmi cho phép tham chiếu đối tượng trong toàn hệ thống thông qua các tham số thích hợp. Roi đảm bảo tính trong suốt cao hơn rpc.
3.Hướng thông điệp: Là mô hình mức cao hơn rpc, roi trong vấn đề giải quyết đồng bộ. Nó cung cấp các ứng dụng truyền thông vừa kiên trì vừa bất đồng bộ mà rpc,roi không đáp ứng được vì đòi hỏi tích hợp rất nhiều dữ liệu liên quan đến hệ thống thông tin.
4.Hướng dòng: Là một mô hình khác biệt so với 3 mô hình trên, hướng tới các dòng dữ liệu có mối quan hệ mật thiết về thời gian. Trong các ứng dụng đa phương tiện truyền thông hướng dòng sẽ ưu tiên được lựa chọn với việc đảm bảo chất lượng dịch vụ đặc thù của các dòng audio video.

Câu 2 Đề chẵn  K47

Tem thời gian là 1 phần dùng để đồng bộ đồng hồ logic (nghĩa là đồng bộ giữa các sự kiện với nhau).

a. Tem thời gian Lamport
Để đo thời gian tương ứng với 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)
Ví dụ : trong sách, trang 257, nói đơn giản là : khi gửi thông điệp thì bên gửi gửi kèm theo nhãn thời gian của nó, nếu tại nơi nhận thời gian trên nhãn thông điệp lớn hơn thời gian tại nơi nhận thì chỉnh lại thời điểm nhận đó là (thời gian gửi+1) (ít nhất) để đảm bảo yêu cầu của thuật toán.

b. Tem thời gian Vector :
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 VT(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 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 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
– Pi gắn một timestamp t=V 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
Ví dụ : không thấy có big grin big grin big grin

Vẫn là câu 2 đề chẵn K47:

5.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:
B trong cùng một tiến trình thì C(A)èNếu 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)

5.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 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 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
– Pi gắn một timestamp t=V 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

 

 

Câu 3 đề chẵn K47

Phục hồi là các phương pháp đưa trạng thái bị lỗi sang trạng thái lành (fault free). Có hai cách tiếp cận cho phục hồi lỗi: phục hồi lùi (back forward) và phục hồi tiến (forward recovery).
Phục hồi lùi: khi thực hiện phục hồi lùi sẽ thực hiện phục hồi trạng thái lành của hệ thống trước khi có lỗi và cho hệ thống chạy lại từ điểm đó. Để có thể thực hiện được điều này phải sử dụng các điểm checkpoint. Tại các điểm này sẽ sao lưu trạng thái hiện hành của hệ thống để khi khôi phục sẽ cho chạy ở điểm checkpoint gần nhất. Việc thực hiện theo phương pháp này là rất tốn kém.
Phục hồi tiến: chuyển hệ thống từ trạng thái lỗi sang trạng thái mới với các thông tin để tiếp tục thực hiện

Câu 1 đề lẻ K47 (  Trình bày ngắn gọn về nguyên lý và so sánh các mô hình di trú mã trong HPT)

Di trú mã thực chất là di trú tiến trình để tăng hiệu năng và  độ linh hoạt của hệ thống.
Một tiến trình bao gồm :
– phần mã ( code segment ) : chứa các tập lệnh tiến trình đang thực hiện
– phần tài nguyên ( source segment ) : chứa tất cả các tham chiếu tài nguyên bên ngoài mà tiến trình đang cần.

Tham khảo hình vẽ của khóa K47
ĐN về di trú strong và weak (nói thế cho dễ viết) trong vở, không nói lại nữa. Đặc điểm
– Di trú weak dễ thực hiện, dùng cho những tiến trình bình thường
– Di trú strong yêu cầu di chuyển cả execution –> khó và phức tạp. Di trú strong dùng cho những tiến trình “không thể dừng” (vd: hệ thống D’Agents – ai thích thì đọc sách)

2 loại này lại chia ra là khởi tạo phía gửi (initiated-sender) và khởi tạo phía nhận (initiated-receiver). Bản thân tên cũng là tính chất của nó rồi, 1 bên là việc bắt đầu tiến trình di trú là do phía gửi (upload, search) còn 1 bên là do phía nhận (applet).
– Khởi tạo phía nhận : đơn giản hơn
– Khởi tạo phía gửi : cần thực hiện liên kết giữa nơi gửi-nhận –> vấn đề đảm bảo đường truyền và bảo mật cao hơn.

Từ đây chia nhỏ làm 2 loại nữa (giữa target process-seprate process và migrate process-clone process tương tự nên chỉ nói 1 cái)
– Migrate : là thực sự di trú 1 tiến trình đến 1 máy khác để thực hiện (máy gửi không thực hiện tiến trình nữa)
– Clone : sao chép code, segement, execution đến 1 máy khác và tạo 1 bản sao của tiến trình, tiến trình giữa 2 máy chạy song song với nhau, thường dùng để tăng tính trong suốt của hệ phân tán.

Cau 2 Đề lẻ K47 : Phân giải tên là gì? Nó được sử dụng như thế nào trong HPT.

mệt quá đi ăn cơm tí nữa chơi gái về pọt tiếp ( Nhắn anh em chia mỗi ng một chương tự nghĩ câu hỏi rồi post lên cho đội support trả lời )

Để hiểu về phân giải tên cần hiểu 2 khái niêm sau :
Tên (name): là xâu các bit hoặc kí tự dùng để tham chiếu đến một thực thể trong hệ phân tán.
Định danh (Identifiers): đây cũng là một kiểu tên đặc biệt. Việc định danh một tên phải thỏa mãn ba tính chất sau:
–   Mỗi thực thể chỉ được tham chiếu bởi duy nhất một định danh ID
–   Mỗi ID tham chiếu tới một thực thể.
–   ID đó không được gán cho một thực thể khác.

Quá trình tìm kiếm tên trong không gian tên được gọi là phân giải tên (name resolution). Quá trình phân giải tên trả về định danh một nút.

Trông hệ phân tán thì người ta sử dụng 3 kĩ thuật tìm kiếm tên là :
1. Closure machanism
2. Linking
3.Mounting
Và có 2 phương pháp chính để phân giải tên là :
1. Cách 1: phân giải tên tương tác (interactive name sesolution),việc phân giải tên thực hiện bằng cách truyền và nhận qua lại giữa client và các name server ở các mức khác nhau. Theo cách này thì các server không trao đổi trực tiếp với nhau, mỗi server chỉ phân giải nhãn tương ứng với lớp để xác định địa chỉ của server tiếp theo, kết quả trả lại cho client là địa chỉ của name server tiếp theo, và việc liên kết với server tiếp theo là do client đảm nhiệm. ( hình vẽ xem trong chương 4 bản dịch của K48 )
2.Cách 2: phân giải tên đệ quy (recursive name resolution), theo cách này thì mỗi name server sẽ gửi kết quả đến name server tiếp theo mà nó tìm thấy. Và cứ như vậy cho đến khi hoàn thành phân giải toàn bộ đường dẫn.
( hình vẽ xem trong chương 4 bản dịch của K48 )

Cau 3 Đề lẻ K 47: So sánh các mô hình nhất quán chặt và nhất quán tuần tự trong HPT

Mô hình nhất quát chặt là mô hình thỏa mãn các điều kiện sau :
– Thao tác đọc bất kì trên mục dữ liệu  x đều trả về một giá trị tương ứng với kết quả của thao tác ghi gần nhất trên x
(Sử dụng khái niệm thời gian tuyệt đối, nó là tổng thể cho cả hệ thống để xác định đúng khái niệm gần nhất)

Mô hình nhất quán tuần tự là mô hình thỏa mãn các điều kiện sau :
– Kết quả của sự thực thi bất kì là như nhau nếu thao tác đọc và ghi do các tiến trình  thực hiện trên mục dữ liệu một cách tuần tự và các thao tác mỗi tiến trình phải xuất hiện trong chuổi thao tác này phải theo thứ tự đã được chỉ ra trong chương trình của nó
( Các tiến trình chạy đông thời trên các máy khác nhau thì cho phép sự đan xen của các thao tác tuy nhiên tất cả các tiến trình phải nhận biết dc sự đan xen của các thao tác đó là như nhau )

So sánh :
– Giống nhau : Đều là sự thỏa thuận giữa các tiến trình và việc lưu trữ dữ liệu , các tiến trình phải chấp nhận theo một quy luật.
– Khác nhau :
+ 1. Nhất quán tuần tự thì các quy tắc rằng buôc lỏng lẻo hơn so với nhất quán chặt chẽ –> lập trình viên dễ sử dụng hơn, quản lý tốt hơn
+ 2. Nhất quán chặt chẽ ko thực tế , còn nhất quán tuần tự thì được áp dụng nhiều nơi
+ 3. Nhất quán chặt chẽ sử dụng kiểu thời gian tuyệt đối cho sự truy cập các tiến trình và các thao tác của từng tiến trình, nhất quán tuần tự chỉ sử dụng thứ tự đã báo trước của dữ liệu và các thao tác tiến trình dc chỉ trong chương trình

Leave a Reply