2015-06-20 60 views
6

Tôi hiện đang cố gắng hiểu các dấu thời gian của Lamport. Hãy xem xét hai quá trình P1 (sản xuất các sự kiện a1, a2 ...) và P2 (sự kiện sản xuất b1, b2 ...). Hãy để C (e) biểu thị dấu thời gian Lamport được kết hợp với sự kiện e. Tôi tạo ra timestamps cho mỗi sự kiện như mô tả trong Wikipedia article about Lamport timestamps:Đồng hồ logic: Lamport Dấu thời gian

enter image description here

Theo Wikipedia, mối quan hệ sau đây là đúng cho tất cả các sự kiện e1, e2:

Nếu e1 xảy ra trước đây e2, rồi C (e1) < C (e2).

Hãy xem a1b2. Rõ ràng a1 xảy ra trước b2, và kể từ C (a1) = 1C (b2) = 3, mối quan hệ đúng: C (a1) < C (b2).

Vấn đề: Mối quan hệ không đúng với b3a3. Rõ ràng, b3 đã xảy ra trước a3. Tuy nhiên, C (b3) = 4C (a3) ​​= 3. Vì vậy, C (b3) < C (a3) ​​ không không áp dụng.

Tôi đã hiểu nhầm điều gì? Giúp đỡ được nhiều đánh giá cao!

Trả lời

1

Tôi đã phát hiện lỗi của mình.Tôi đã viết:

Nếu e1 xảy ra trước e2, thì C (e1) < C (e2).

Tuy nhiên, Lamport được xác định "đã xảy ra trước" như một phần đặt hàng. Đây là những gì Wikipedia nói về bộ ra lệnh một phần:

một mối quan hệ như vậy được gọi là một trật tự một phần để phản ánh một thực tế rằng không phải mọi cặp yếu tố cần được liên quan: đối với một số cặp, nó có thể là không phải yếu tố đi trước khác trong poset.

Theo định nghĩa Lamport của "xảy ra trước đây", b3a3 không liên quan, do đó b3 không "xảy ra trước khi" a3, do đó equasion nêu trong câu hỏi không phải giữ đúng sự thật.

1

Lamport giả định rằng: chúng tôi không thể sử dụng chung thời gian vật lý để tìm ra thứ tự của bất kỳ cặp sự kiện tùy ý nào xảy ra trong đó. Trong ví dụ được đề xuất, bạn bỏ qua giả định này.

P1P2 tăng đồng hồ độc lập. Khi một sự kiện xảy ra, quá trình khởi tạo gửi giá trị hiện tại của nó tới quá trình đích, nó sẽ kiểm tra xem giá trị nhận được có nhỏ hơn giá trị hiện tại của nó hay không. Nếu có, nó thay đổi giá trị hiện tại của nó thành giá trị nhận được + 1, nếu không nó sẽ loại bỏ giá trị nhận được. Trong trường hợp của bạn, P1P2 không gửi sự kiện của họ a3b3.

3

Có, định nghĩa đó có thể hơi khó hiểu. Đó là chính xác những gì mọi người khác nói cho đến nay, tuy nhiên có thể có một từ mất tích, để hiểu hệ thống tốt hơn. - đồng thời

Nếu bạn xử lý p1p2 đang chạy trên cùng một máy, có thực sự là không quá nhiều nhu cầu sử dụng đồng hồ Lamport (có thể một số trường hợp rất cụ thể). Thay vào đó bạn chỉ có thể sử dụng đồng hồ được cung cấp bởi hệ điều hành của bạn. Nhưng điều gì xảy ra nếu p1p2 có trên các máy tính được phân tách bằng mạng chậm và không đáng tin cậy không?

Lamport giả định, bạn không thể tin tưởng đồng hồ địa phương của mình và bạn không có trạng thái toàn cầu của hệ thống phân phối, trong đó các sự kiện đặt hàng trên 2 máy tính riêng biệt đã xảy ra. Đó là khi bạn gọi những sự kiện đó xảy ra đồng thời.

Khi bạn muốn được gỡ lỗi thực hiện các hệ thống phân phối và bạn sẽ thấy sự kiện a3b3 tự nhiên bạn muốn giả định, a3 xảy ra trước b3. Trong trường hợp cụ thể của bạn, bạn hiện yêu cầu bồi thường, vâng, nhưng đó là sai. Tuy nhiên, vì các sự kiện không liên quan, vì chúng không giao tiếp với nhau, thứ tự thường được giả định là đồng thời và trong trường hợp đó, nó không quan trọng cái nào xảy ra trước hoặc thứ hai, cho toàn bộ việc thực hiện hệ thống.

Kể từ khi máy tính và mạng đang làm việc quá nhanh và vẫn còn rất chính xác, đó là đôi khi rất khó hiểu, chúng ta hãy nhìn vào những điều tương tự hơi khác nhau:

p1p2 hai người sống vài 100 năm trước đây ở hai thung lũng khác nhau. Họ giao tiếp với nhau bằng cách sử dụng pidgins và không bao giờ nói về khi họ đã làm một nhiệm vụ nhất định, chỉ là những gì họ đã làm. Bằng cách này, không ai có thể biết được, nếu a3 xảy ra trước b3 hoặc ngược lại, do đó chúng xảy ra đồng thời. Có thể không phải là không ai, Chúa xem từ trên p1p2 có thể xem được.

Thật không may, khi bạn có một hệ thống phân phối, bạn có thể không được thần và xem p1p2 cùng một lúc, chỉ cần ra khỏi lý do mà các tin nhắn từ p1 có thể mất nhiều thời gian hơn từ p2. Vì vậy, mặc dù hệ thống giám sát của bạn (thần) đã nhận được thông tin của b3 trước khi nó nhận được thông tin về a4 nó không có nghĩa là họ đã xảy ra theo thứ tự đó, có lẽ các gói chứa thông tin về a4 chỉ mất một còn hoặc đường dẫn chậm hơn.

Cuối cùng, có một thứ khác được gọi là vector clocks. Mỗi quá trình có một đồng hồ lamport cho mọi quá trình trong hệ thống. Chìa khóa ở đây là, sự kiện một sẽ chỉ xảy ra trước sự kiện b nếu tất cả đồng hồ Lamport của một là nhỏ hơn hoặc bằng những b. Nếu bạn sẽ thử nó trên ví dụ nhỏ của mình, bạn sẽ thấy rằng không có sự kiện nào xảy ra trước => chúng khác đồng thời.

Các vấn đề liên quan