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

Đề K48

Đề chẵn
1. Trình bày nguyên lý và so sánh các mô hình di trú mã.
2. Trình bày về các khái niệm name, address, identifier, namespace.
3. Giải thích các tính chất ACID (Automic, Consistent, Isolated, Durable) của các giao tác phân tán
Đề lẻ
1 Trình bày phương pháp triệu gọi đối tượng từ xa (roi) sử dụng trong hệ phân tán
2 Phân giải tên là gì và nó đuợc thực hiện thế nào
3 So sánh mô hình nhất quán chặt và mô hình nhất quán tuần tự trong hệ phân tán

GỢI Ý:

câu 1 Đề chẵn K48 : Trình bày nguyên lý và so sánh các mô hình di trú mã. ( đã có trong đề K47 )

Câu 2 để chẵn K48 : Trình bày về các khái niệm name, address, identifier, namespace.

Có rất nhiều từ dùng để xác định một thực thể đó là: tên (name), địa chỉ (address), định danh (identifier), tên thân thiện (Human-friendly name).
•   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.
•   Địa chỉ (address): khi truy cập đến thực thể ta sử dụng điểm truy cập (access point). Các điểm truy cập này cũng phải được đặt tên và tên đó chính là địa chỉ của nó. Như vậy địa chỉ của thực thể chính là tên của điểm truy cập thực thể tương ứng.
•   Đị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
Không gian tên (Name Space ) :Tập hợp tất cả các từ dùng để xác định thực thể gọi là không gian tênNếu xét về mặt hình học thì đây là một đồ thị có hướng, gồm các nút và các cung, gọi là đồ thị tên (naming graph). Đồ thị có cấu trúc: Mỗi nút lá miêu tả một một thực thể. Mỗi nút directory gắn với nhiều nút khác; lưu trữ trong bảng directory, bảng này là tập các cặp (label,indetifier).
Tên thân thiện (Human-friendly name): là các tên được đặt một cách dễ hiểu, thân thuộc với con người

Giao tác là gì? Giao tác phân tán là gì, để làm gì?so sánh các giao tác phân tán

Giao tác là một đơn vị công việc( bao gồm nhiều lệnh ) riêng lẻ, hay còn gọi là một nguyên tử công việc . Mỗi giao dịch có nhiều bước ( nhiều lệnh ) mỗi lệnh phải thành công thì giao tác mới thành công
Giao tác có 4 tính chất đó là :
Tính nguyên tử (atomic ) : mọi giao tác không thể phân chia nhỏ thành các giao tác nhỏ hơn. Nếu giao tác không thành công thì hệ thống sẽ trở lại trạng thái trước khi giao tác bắt đầu.
Tính nhất quán ( consistent ) : giao tác không xâm phạm các bất biến của hệ thống. Có nghĩa là trước khi giao tác thực thi các bất biến hệ thống như thế nào thì sau giao tác các bất biến đó vẫn giữ nguyên. ví dụ trong ngân hàng , khi có một giao dịch nội bộ thì sau giao dịch đó tổng số tiền trong ngân hàng vẫn giữ nguyên. Tuy nhiên trong quá trình giao dịch thì số tiền đó có thể bị thay đổi , nhưng nó lại ẩn nếu đứng ở ngoài giao dich. — ( tương tự như giao tác )
Tính cô lập ( isolated ) : các giao tác đồng thời không gây trở ngại cho nhau . Nghĩa là các giao tác cùng chạy mỗi thời gian thì ko gây ra ảnh hưởng cho nhau , ko thay đổi giao tác khác
Tính lâu bền (Durable): khi giao tác đã cam kết thì các thay đổi đối với nó không phải là tạm thời mà là kéo dài . Ví dụ khi một giao tác cam kết , thì trong trường hợp mất điện nó ko bị mất đi mà khi có điện thì nó sẽ dc khôi phục lại

Giao tác phân tán là giao tác thực hiện đc trên nhiều cơ sở dữ liệu và nhiều câu lệnh có thể thực thi trên cùng một cơ sở dữ liệu trong cùng một thời điểm

So sánh các giao tác : Có 3 loại giao tác là Limition of Flat Transaction ( giao tác phẳng ),Nested Transaction ( giao tác lồng ) ,Distributed Transaction ( giao tác phân tán )

a.   Giao tác phẳng: Là loại giao tác đơn giản và được dùng nhiều nhất thỏa mãn 4 tính chất nguyên tử, nhất quán, độc lập, và bền bỉ như kể trên.
+Ưu điểm: Đơn giản và được dùng nhiều nhất.
+Nhược điểm: Chính bản thân tính chất nguyên tử khiến cho giao tác phẳng không cho phép một phần kết quả được hoàn thiện độc lập hoặc là bị bỏ qua. Giảm hiệu năng của hệ thống.
b.   Giao tác lồng: Giao tác lồng có cấu trúc là một tập hợp các giao tác con được phân cấp. Giao tác trên cùng là giao tác cha nó có thể được thực thi song song với các giao tác khác và được chia nhỏ hơn, các giao tác nhỏ hơn này cũng có thể được thực hiện song song và lại được chia tiếp.
+Ưu điểm: Giao tác lồng có thể thực hiện tính chất chồng sâu giúp nâng cao hiệu quả của hệ thống.
+Nhược điểm:
Tuy nhiên nó cũng có nhược điểm nhỏ nhưng rất quan trọng là nếu tính huống sảy ra như sau các giao tác con được diễn ra song song , một trong các giao tác con đó đưa ra kết quả trước cho giao tác trên cùng, sau khi tính toán giao tác trên cùng hủy bỏ và đưa trạng thái hệ thống về thời điểm ban đầu trước khi giao tác lồng thực hiện. Vì vậy các giao tác con còn lại sẽ bị dừng và không được hoàn thành.
Tính chất bền bỉ của giao tác lồng chỉ được áp dụng cho tầng trên cùng cũng là một hạn chế.
c.   Giao tác phân tán: Giao tác phân tán bản chất là một giao tác phẳng có cách hoạt động hợp lý, giao tác mà không thể phân chia được và được thực hiện trên dữ liệu phân tán.
+Nhược điểm: Bản chất là giao tác phẳng nên nó cũng có một số yếu điểm giao tác phẳng.
+Ưu điểm: Là một sự lựa chọn thích hợp cho hệ phân tán.

Câu hỏi 2: Trình bày nguyên lý điều khiển tương tranh và so sánh 2 loại điều khiển tương tranh bi quan và lạc quan?
1.   Nguyên lý điều khiển tương tranh:
+Là quá trình điều khiển giúp cho nhiều giao tác diễn ra đồng thời mà không sảy ra tranh chấp.
+Có 2 loại điều khiển:
(1)   Điều khiển bi quan.
(2)   Điều  khiển lạc quan.
2.   So sánh
a.   Điều khiển bi quan:
+ Là phương pháp điều khiển với quan điểm “Nếu một sự kiện có khả năng sai thì nó sẽ sai”. Vì vậy để thực hiện phương pháp này người ta thực hiện đồng bộ bằng tem thời gian trước khi tiến hành thực hiện giao tác.
+Ưu điểm: Với phương pháp này đảm bảo độ tin cậy cao, thích hợp với hệ thống tải lớn.
+Nhược điểm: Sẽ tạo ra thời gian trễ(deadlock) vì các tiến trình phải chờ đợi, làm hiệu quả của hệ thống không cao.
b.   Điều khiển lạc quan:
+Là  phương pháp điều khiển với quan điểm “Nói chung tất cả mọi sự kiện đều đúng”. Với phương pháp này người ta thực hiện đồng bộ sau khi thực hiện thành công giao tác.
+Ưu điểm: Giải phóng thời gian trễ (deadlock), các tiến trình được xử lý luôn không phải chờ, làm nâng cao hiệu năng của hệ thống.
+Nhược điểm: Đôi khi gây ra lỗi giao tác phải thực hiện lại, với hệ thống tải lớn thì phương pháp này là không thích hợp.

Các mô hình nhất quán

Nhất quán cuối cùng (eventual consistency)
ĐN : Là mô hình nhất quán mà khi 1 dữ liệu có nhiều bản sao thì khi thực hiện cập nhật thì tất cả các bản sao phải giống nhau (cùng được cập nhật).
Ưu điểm :
đảm bảo khả năng trong suốt caoà    o   Thực hiện tốt
o   Rẻ, dễ thực hiện.
Nhược điểm
o   Yêu cầu các client thực hiện cập nhật thường xuyên
o   Khi các client di chuyển khó thực hiện
o   Thường chỉ áp dụng cho những hệ thống có ít người cập nhật

Nhất quán đọc đều (monotonic – read consistency)
ĐN : “Là mô hình nhất quán mà khi 1 tiến trình đọc giá trị 1 mục dữ liệu x, phải đảm bảo rằng thao tác đọc trên x luôn trả về cùng 1 giá trị hay là 1 giá trị gần đấy nhất”
Nói cách khác, nếu 1 tiến trình nhận được giá trị của x ở thời điểm t thì tại thời điểm sau t, nó sẽ không nhận được giá trị cũ hơn của x tại thời điểm t.
Ví dụ : hệ thống CSDL mail. Thư điện tử có thể thêm vào mailbox ở bất cứ đâu. Một người đọc thư điện tử ở A (coi như không xóa thư). Khi người đó đến B và mở mailbox thì những thư trong mailbox ở A cũng phải nằm ở trong maibox khi được mở tại B.

Nhất quán ghi đều (monotonic – write consistency)
   ĐN : Là mô hình nhất quán mà 1 tiến trình ghi lên 1 mục dữ liệu x được hoàn thành trước khi bất kỳ quá trình ghi nào khác trên x bởi cùng 1 tiến trình.
Mô hình này tương tự như nhất quán FIFO trong mô hình hướng dữ liệu, tuy nhiên nó chỉ liên quan đến 1 tiến trình chứ không phải nhiều tiến trình đang cùng thực hiện.
Nói cách khác, với mô hình này, khi 1 tiến trình ghi thực hiện, nó phải đảm bảo rằng mọi tiến trình ghi trước nó (về mặt thời gian) phải được hoàn thành. Mô hình nhất quán này được áp dụng trong những hệ thống mà quá trình ghi có thể bị thay thế và việc thực hiện tuần tự quá trình ghi không được đảm bảo. (vd : việc cập nhật lên 1 bản sao của thư viện, mọi bản cập nhật trước đó phải được thực hiện trước)

Nhất quán đọc kết quả ghi (Read – your – write consistency)
    ĐN : “Tác động của một thao tác ghi của một tiến trình lên mục dữ liệu x sẽ luôn được nhìn thấy bởi một thao tác đọc lần lượt trên x của cùng tiến trình đó”
Nói cách khác, 1 quá trình ghi luôn hoàn thành trước khi trước khi 1 quá trình đọc của cùng tiến trình thực hiện bất kể việc đọc diễn ra ở đâu.
Ưu điểm : Đảm bảo người dùng luôn nhận được kết quả mới nhất
Nhược điểm : Khi thực hiện ghi (cập nhật), có thể người dùng không thể truy cập được dữ liệu (vd:việc thay đổi password của 1 tài khoản thư viện) hay khi bộ đệm ko có hiệu lực (truy cập Web)

Nhất quán ghi theo sau đọc (write – follow – read consistency)
ĐN : “Tác động bởi một thao tác ghi của một tiến trình lên mục dữ liệu x theo sau 1 quá trình đọc trước đó của cùng 1 tiến trình được đảm bảo xảy ra trên giá trị mới nhất đã được đọc”
Nói cách khác, một quá trình ghi của 1 tiến trình trên mục dữ liệu x sẽ được thực hiện trên 1 bản sao của x được cập nhật với giá trị đọc gần nhất bởi tiến trình đó.
Ưu nhược điểm : bó tay, chả biết nói thế nào
Gớm: Khó hiểu và trừu tượng thì vô đối  confused confused confused

* Những người dùng chỉ đọc bài báo (article) không cần bất cứ mô hình nhất quán hướng client cụ thể nào cả.

Câu hỏi : Nguyên lý nhất quán và nhân bản? Phân tích (so sánh)  các mô hình nhất quán lấy dữ liệu làm chung tâm?

Trả lời
1.   Nguyên lý nhất quán và nhân bản:
Trong hệ phân tán có 2 lý do để sử dụng bản sao:
+Thứ nhất dùng bản sao để tăng độ tin cậy và tính sẵn sàng của hệ thống.
+Thứ 2 dùng bản sao để tăng hiệu năng  của hệ thống.
Tuy nhiên việc sử dụng bản sao cũng phải trả giá, đó là tính nhất quán dữ liệu của hệ thống bị suy giảm. Do sử dụng bản sao nên có thể xảy ra trường hợp có sự thay đổi trên một dữ liệu mà không cập nhật trên các bản sao của nó. Điều này gây ra các sai sót trong hệ thống. Nguyên lý nhất quán và nhân bản được đưa ra cung cấp:
(1)   Các mô hình nhất quán.
(2)   Các giao thức phân phối .
(3)   Các giao giao thức nhất quán.
+ Có một mâu thuẫn là tính nhất quán càng cao thì hiệu năng của hệ thống càng thấp vì vậy khi thiết kế hệ phân tán cần cân nhắc kỹ.

2.   Phân tích ưu nhược điểm của các mô hình nhất quán lấy dữ liệu làm trung tâm:
+ Các mô hình nhất quán lấy dữ liệu làm trung tâm:
(1)   Mô hình nhất quán chặt.
(2)   Mô hình nhất quán tuần tự.
(3)   Mô hình nhất quán tuyến tính.
(4)   Mô hình nhất quán nhân quả.
(5)   Mô hình nhất quán FIFO.
(6)   Mô hình nhất quán yếu.
(7)   Mô hình nhất quán đi ra.
(8)   Mô hình nhất quán đi vào.
+ Phân tích các mô hình trên:
(1)   Mô hình nhất quán chặt:
+Là một mô hình nghiêm ngặt phải thỏa mãn đ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 đó. Để đảm bảo điều kiện này người ta phải làm sáng tỏ khái niệm thao tác ghi gần nhất tức là phải đưa ra định nghĩa về thời gian tuyệt đối. Thời gian tuyệt đối này phải bao quát tổng thể hệ thống.
+Ưu điểm: Mô hình đưa ra đảm bảo cho tính nhất quán lý tưởng, và dễ hiểu.
+Nhược điểm: Mô hình trên dựa vào khái niệm thời gian tuyệt đối cho toàn bộ hệ thống phân tán là không thể thực hiện được. Vì tất cả các quá trình đọc ghi được phân tán trên rất nhiều máy khác nhau có vị trí địa lý khác nhau mặt khác lại có sự trễ trên đường truyền…Vì vậy đây chỉ là mô hình nguyên lý không thể thực hiện với hệ phân tán thực tế.
(2)   Mô hình nhất quán tuần tự:
+ Mô hình tuần tự có điều kiện cần phải thỏa mãn như sau: “kết quả của bất kỳ sự thực thi nào cũng phải giống nhau, như thể tất cả các hành động đọc, ghi dữ liệu là của mọi tiến trình và được thực thi theo một thứ tự nào đó. Hành động đọc ghi của mỗi tiến trình riêng biệt xuất hiện trong thứ tự đó là do chương trình của chính nó quyết định.” . Có nghĩa là khi mà các tiến trình được diễn ra đồng thời trên các máy khác nhau mà có sự xen ngang của hành động đọc ghi dữ liệu thì tất cả các tiến trình đều nhìn thấy hành động đó.
+Ưu điểm: Trong điều kiện của mô hình không nhắc đến khái niệm  trước sau về thời gian tuyệt đối khắc phục được nhược điểm không thể thực thi của mô hình nhất quán chặt chẽ.
+Nhược điểm: Chính vì sự định nghĩa thứ tự của các hành động đọc ghi của mỗi tiến trình chưa có khái niệm tem thời gian nên nó không thật sự chặt chẽ, nên mô hình nhất quán này hơi yếu.
(3)   Mô hình nhất quán  tuyến tính:
+Là mô hình thỏa mãn điều kiện sau: “ kết quả của bất kỳ sự thực thi nào cũng phải giông nhau như thể tất cả các hành động đọc, ghi dữ liệu là của mọi tiến trình và được thực thi theo một thứ tự nào đó. Hành động đọc ghi của mỗi tiến trình riêng biệt xuất hiện trong thứ tự đó là do chương trình của chính nó quyết định. Đồng thời quy định nếu Tsop1(x) < Tsop2(y) (Tsop1(x): là tem thời gian của hành động ghi học đọc trên dữ liệu x) thì op1(x) sẽ đứng trước op2(y) trong thứ tự”. Trong nhất quán tuyến tính thì việc lưu trữ dữ liệu cũng phải đảm bảo tính tuyến tính tuần tự.
+Ưu điểm: Việc sử dụng tem thời gian làm cho thứ tự xếp đặt tương đối chăt chẽ, và mô hình này được đánh giá mạnh hơn mô hình nhất quán tuần tự.
+Nhược điểm: Mô hình này tính nhất quán mạnh nhưng hiệu năng hệ thống lại không cao.
(Ưu điểm nhược điểm ở đây em bịa đấy, cao thủ nào hiểu sâu fix hộ cái).

Cam kết 3 pha:
– Thêm trạng thái PRECOMMIT
:
+ Khi tiến trình điều phối nhận được thông báo VOTE_COMMIT từ tất cả các tiến trình thành viên nó sẽ phát thông báo PREPARE_COMMIT tới tất cả các thành viên.
+ Các tiến trình thành viên ở trạng thái READY, khi nhận được thông báo PREPARE_COMMIT thì đáp ứng lại thông báo READY_COMMIT tới tiến trình điều phối.
+ Khi nhận được phản hòi READY_COMMIT từ tất cả thành viên trong nhóm, tiến trình điều phối sẽ phát thông báo GLOBAL_COMMIT và bước vào trạng thái COMMIT

– Khi tiến trình điều phối ở trạng thái PRECOMMIT, nếu thời gian timeout đã hết mà còn thành viên nào đó chưa phản hồi thì nó vẫn chuyển sang trạng thái COMMIT bởi vì nó đã chắc chắn được rằng thành viên đó đã đáp ứng bằng thông điệp VOTE_COMMIT trước khi bị lỗi. Và cuối cùng thì khi tiến trình thành viên lỗi được khôi phục nó cũng bước vào trạng thái COMMIT.
– Trạng thái PRECOMMIT còn đảm bảo một tiến trình thành viên luôn quyết định được bước chuyển của nó một cách an toàn
+ Khi tham vấn thành viên Q, Q chỉ ở trạng thái INIT khi và chỉ khi không có thành viên nào khác nằm ở trạng thái PRECOMMIT.
+ Nếu tất cả các thành viên P tham vấn đều ở trạng thái READY thì giao tác bị loại bỏ.
+ Khi P là một tiến trình lỗi được khôi phục lại, nếu tồn tại tiến trình thành viên khác ơ trạng thái READY thì trạng thái của P chỉ có thể là INIT, ABORT hoặc PRECOMMIT.
+ Nếu tồn tại một thành viên ở trạng thái PRECOMMIT thì các thành viên khác khi được khôi phục lại sẽ nằm ở một trong 3 trạng thái READY, PRECOMMIT và COMMIT

*Chú ý : cam kết 3 pha chỉ được đề cập nhiều trong lý thuyết còn thực tế cam kết 2 pha vẫn được sử dụng rộng rãi hơn. Cam kết 3 pha chỉ cho thấy khả năng chịu lỗi của hệ phân tán

Đề 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