Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 48-
chơng III. Quá Trình đồng thời và lập trình
Trong HĐH phân tán, hai phần tử thiết yếu là QT và luồng (thread). Quản lý QT đợc
phân lớp triển khai theo ba khu vực (cũng là ba chức năng liên quan đến quản lý QT
trong hệ phân tán):
+ Truyền thông QT,
+ Đồng bộ hoá QT,
+ Lập lịch QT.
Ba chức năng này thuộc vào một thể thống nhất và không tách rời nhau.
Các chức năng truyền thông và đồng bộ có mối quan hệ mật thiết cả về khái niệm và
lẫn khi thi hành. Các khái niệm và việc thi hành phối hợp đợc trình bày trong hai
chơng III và IV.
Lập lịch QT liên quan đến trình tự thực hiện các QT để đạt đợc hiệu suất tốt nhất cho
hệ thống. Trình tự thực hiện QT tuỳ thuộc vào đồng bộ QT trong khi hiệu suất lại phụ
thuộc vào năng lực lớn mạnh của kĩ thuật truyền tin cơ sở và thời gian trễ trong quá
trình truyền tin. Do đặc thù khá riêng biệt nên lập lịch QT đợc trình bày trong chơng
V. Dù cho truyền thông QT, đồng bộ QT và lập lịch QT có những đặc điểm chung nh
trong HĐH tập trung, song nhằm mục đích định hớng hệ phân tán cho nên trình bày
quản lí QT có trong ba chơng III, IV và V .
Trớc hết bắt đầu với các định nghĩa và các đặc điểm của điều khiển QT.
3.1. Khái niệm QT và luồng
QT là đối tợng trong HĐH, biểu thị việc thực hiện một chơng trình trong một phiên
làm việc: QT là một đơn vị tính toán cơ sở trong hệ thống.
Một số điểm phân biệt hai khái niệm chơng trình và QT: Chơng trình liên quan đến
bài toán cần giải quyết (các tham số hình thức), tên chơng trình, độ dài, ngôn ngữ
nguồn . QT là một lần sử dụng chơng trình đã có để giải quyết bài toán trong một
tình huống cụ thể (tham số đã đợc cụ thể). QT có trạng thái quá trình, bao gồm trạng
thái phân bố các thành phần của QT trong bộ nhớ trong ...
QT đợc gọi là đơn nếu các lệnh (thành phần con) trong nó đợc thực hiện một cách
tuần tự. Thuật ngữ đồng thời liên quan đến việc mô tả sự thực hiện đồng thời các QT

QT đơn Các QT đa luồng Th viện hỗ trợ thời gian chạy của luồng
PCB Luồng
PCB TCB TCB TCB

L L L
PCB TCB TCB TCB

L L L
Hình 3.3. Quá trình và luồng
Hình 3.2. Trạng thái của QT
1. QT kết khối để nhập dữ liệu
2. Bộ lập lịch chọn QT khác
3. QT đợc chọn
4. Nhập dữ liệu xong
Kết khối

Luồng có nhiều ứng dụng trong HĐH phân tán. Chúng thờng đợc dùng khi thi hành
một QT phục vụ cung cấp các dịch vụ tơng tự hoặc có quan hệ tới các QT đa khách,
chẳng hạn nh phục vụ trạm cuối hoặc phục vụ file.
Khi một yêu cầu phục vụ (serving request) từ QT khách tới một QT phục vụ đơn luồng,
thì QT phục vụ này tự tạm ngừng (có thể quan niệm phục vụ này nh một tài nguyên
đợc điều khiển bởi một semaphore nhị phân) để chờ đợi hoàn thiện các điều kiện
hoặc thao tác nào đó từ trớc. Tuy nhiên, việc tạm ngng phục vụ lại kết khối các yêu
cầu khách mới đợc đa tới phục vụ. Để tăng thông lợng hệ thống, đa bản sao của
cùng một phục vụ đợc khởi tạo cho các yêu cầu khác nhau tới cùng một phục vụ một
cách đồng thời. Do các luồng phục vụ này có mã lệnh tơng tự nhau và bắt buộc phải
tơng tác nhau qua thông tin toàn cục đợc chia xẻ, vì vậy chúng đợc nhóm trong
một không gian điạ chỉ, và nh vậy là đã khởi tạo tính đa luồng trong một phục vụ đơn.
QT khách cũng đợc điều khiển theo cách hoàn toàn tơng tự. Một QT khách yêu cầu
tạo ra nhu cầu đồng thời tới các phục vụ và bỏ qua việc bị kết khối bởi bất kỳ từ các
yêu cầu dịch vụ này.
Hình 3.4 mô tả ba ứng dụng luồng trong hệ phân tán.
Phục vụ trạm cuối (phức hợp và tập trung dữ liệu) trong hình 3.4a:
Chức năng tập hợp dữ liệu đa thành phần từ nhiều trạm cuối vào bộ đệm chung và gửi
dữ liệu phức trong một bộ đệm chung tới một máy tính (hay mạng). Nếu không dùng
đa luồng, phục vụ trạm cuối cần bầu cử trạm cuối đa vào bằng cách sử dụng dịch vụ
nguyên thuỷ không kết khối. Theo quan niệm, sẽ đơn giản hơn nếu thiết kế phục vụ
thành đa luồng, mỗi từ chúng đáp ứng một input riêng. Mã lệnh của các luồng này là
đồng nhất nên đợc chia xẻ nh mã thực hiện lại mà mỗi luồng có stack cục bộ riêng
của mình. Việc truy nhập vào buffer cùng đợc chia xẻ bởi các luồng cần loại trừ ràng
buộc. Việc loại trừ ràng buộc có thể đạt đợc bằng cách sử dụng phơng pháp đồng bộ
bộ nhớ chia xẻ nh semaphore hay bộ kiểm tra, vì tất cả các luồng chia xẻ một vùng
địa chỉ. Hơn nữa đồng bộ luồng có thể hiệu quả hơn nhiều vì QT đồng bộ chỉ gọi phần
cục bộ và có thể tránh đ
ợc việc gọi nhân trong một số trờng hợp. Các luồng trong ví
Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)

Luồng
Luồng
Bộ đẹm
Đọc
Yêu cầu
Chính
Ghi
Luồng
Luồng
Những luồng tĩnh đồng nhất
Yêu cầu đồng thời và
dị bộ
Những luồng
độngđồng thời
Hình 3.4. Các ứng dụng luồng
c) Phục vụ
Khách
a) Phục vụ trạm cuối b) Phục vụ File
Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 52-
3.1.2 Thi hành luồng trong không gian ngời dùng
Hỗ trợ luồng nh một gói thêm vào đã đợc thực hiện trên nhiều hệ thống bao gồm gói
luồng DCE từ Tổ chức phần mềm mã mở OSF và gói QT nhẹ (LWP: Light Weight
Process) từ Sun. Vấn đề thi hành cốt lõi là nắm giữ đợc các lời gọi hệ thống đang kết
khối từ một luồng và lập lịch luồng để thực hiện trong một QT. Trong thi hành luồng
trong không gian ngời dùng (chơng trình ngời dùng), một QT đợc ấn định chia xẻ
thời gian bộ xử lí nh thờng đợc làm trong bất cứ HĐH nào. Khoảng thời gian đợc
ấn định này là đa thành phần giữa các luồng đang tồn tại. Các luồng chạy dựa trên th
viện hỗ trợ thời gian chạy luồng. Trách nhiệm của một thủ tục thời gian chạy luồng là
thực hiện việc chuyển ngữ cảnh từ luồng này sang luồng khác. Mỗi lời gọi hệ thống kết

gọi hệ thống thì nó có thể bị kết khối mà không kết khối các luồng khác thuộc cùng
QT và mỗi luồng có thể hoàn thành một chu trình của bộ xử lí với cùng cơ sở của các
QT. Tuy nhiên, sự trừu tợng hai mức tinh vi đối với đồng thời trở nên mờ nhạt hơn và
lợi thế tải chuyển ngữ cảnh luồng của QT nhẹ không còn nữa. Tính cơ động và hai mức
trừu tợng đồng thời đôi khi nảy sinh thêm bất lợi khác.
Giống nh các khái niệm mô hình Client/Server và RPC, luồng là khái niệm thiết kế hệ
thống cơ bản. Việc lựa chọn thi hành luồng trong không gian nhân hay trong không
gian ngời dùng là một nhân tố thiết kế hệ thống khó tính. Cách kết hợp thi hành luồng
cả không gian ngời dùng và không gian nhân nh trong Suns Solaris hội tụ đợc các
Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 53-
lợi điểm của hai hớng tiếp cận trên. Phần dới đây minh họa việc kết hợp hỗ trợ nhân
đa luồng nh vậy.
Nhân truyền thống là những luồng đơn. Thờng thì chỉ có một bộ xử lí và cấu trúc của
nhận là rất gọn. Vì vậy, đòi hỏi dịch vụ nhân chạy trong một luồng đơn không cần tính
sự u tiên. Không đồng bộ là điều cần thiết trong thao tác nhân. Gần đây, hai khuynh
hớng quan trọng đã đợc nảy sinh cho những hệ thống hiện đại. Thứ nhất, máy tính
đơn với nhiều bộ xử lý đã trở nên thông dụng. Thứ hai là sự phức tạp về nhu cầu phần
mềm đòi hỏi phải tạo ra nhiều dịch vụ mới trong nhân. Nhân đa luồng hỗ trợ cho
những dịch vụ nhân đồng thời đã đợc khẳng định.
Thao tác nội tại của nhân và những dịch vụ mà nhân cung cấp tới ứng dụng của ngời
dùng có thể đợc thi hành nh luồng. Luồng trong không gian nhân đã đợc phức hợp
trong một hệ đa bộ xử lý hạ tầng. Việc thực hiện luồng là song song thực sự và có thể
định u tiên. Sự đồng bộ giữa những luồng trong nhân trở nên cần thiết và có thể thực
hiện đợc bằng cách dùng bộ nhớ chia xẻ. Để kết hợp chặt chẽ luồng trong không gian
ngời dùng và luồng trong không gian nhân trong cùng một hệ thống, Solaris giới
thiệu một khái niệm luồng mức trung gian và gọi là QT nhẹ LWP. LWP đợc QT
ngời sử dụng tạo ra và đợc chơng trình con (trong th viện) thời gian chạy luồng
quản lý. Chúng đợc nhân tổ chức nh là đơn vị cơ sở cho việc lập lịch. Luồng ngời
dùng, không thể đợc nhân nhận biết, cũng đợc tạo ra và quản lý bởi bó luồng. LWP

Mô hình đồ thị

Đoạn 3.1 mô tả các khái niệm QT và luồng. Trong đoạn này, chúng ta quan tâm đến
việc làm thế nào để chúng có thể đặt cùng với nhau. Các QT có quan hệ với nhau bởi
điều đó cần thiết cho:
- tính đồng bộ
: việc chạy một vài QT phải đợc tiếp nối theo một trình tự nào đó.
Một ví dụ về sự đồng bộ là mối quan hệ đi trớc (tiền tố: predecence) giữa hai QT. Mối
quan hệ đi trớc giữa hai QT quy định rằng một QT chỉ đợc thực hiện khi mà những
QT "đi trớc" nó đã đợc thực hiện.
- hoặc/và vấn đề truyền thông
: Trong nhiều trờng hợp thì mối quan hệ đi trớc
hoặc thứ tự của các QT là không nhất thiết đối với việc các QT CTĐ cho nhau.
Hình 3.6 sử dụng mô hình đồ thị để biểu thị hai cái nhìn khác nhau về sự tác động giữa
các QT. Đồ thị QT đồng bộ theo mô hình đồ thị có hớng không chu trình thể hiện
trực tiếp mối quan hệ đi trớc và thứ tự trong tập các QT. Những cạnh vô hớng trong
đồ thị QT dị bộ thể hiện đờng truyền thông và sự phụ thuộc giữa các QT.
Các đồ thị trong hình 3.6 cha cho biết cụ thể thực sự mô phỏng tác động trong một hệ
phức tạp. Tuy nhiên, chúng vẫn đợc sử dụng để xây dựng mô hình các QT và bộ xử lý
trong hệ thống phân tán:
- Đồ thị QT đồng bộ đợc sử dụng để đánh giá tổng thời gian của một tập hợp
các QT,
- Đồ thị truyền thông dị bộ có thể đợc sử dụng để nghiên cứu phân bố các bộ xử
lí nhằm tối u hoá tổng chi phí về thời gian truyền thông giữa bộ xử lí.
Kênh truyền
thông
Đồ thị QT đồng bộ
Ngang hàng

Clien/Server

Mô hình không gian - thời gian

Mô hình đồ thị QT đồng bộ và dị bộ thích hợp cho việc đánh giá hệ thống nhng lại
thiếu chi tiết và đầy đủ để thể hiện đợc sự tơng tác giữa các QT. Hình 3.7 trình bày
mô hình không gian - thời gian là cách thể hiện tốt hơn việc truyền thông và quan hệ đi
trớc. Sự tồn tại của đờng truyền thông và quan hệ đi trớc giữa các sự kiện và việc
truyền thông thực sự đợc thể hiện tờng minh trong mô hình. Quan hệ đi trớc hoặc
là đờng truyền thông tin đợc nhận biết dễ dàng trong mô hình không gian - thời
gian. Mô hình QT này có nhiều thông tin để đánh giá sự tơng tác giữa các QT hơn là
thông tin để đánh giá về sự hoạt động chung toàn hệ thống.
P
1

P
2

P
3

P
Sự kiện
Không gian
Các QT
Truyền thông
Hình 3.7. Mô hình không gian thời gian cho sự tác động của các QT
Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 56-
Nh vậy, mỗi mô hình (đồ thị, không gian - thời gian) có tác dụng riêng và tùy thuộc
vào mục đích đánh giá để chọn mô hình.
Khi các QT đợc thể hiện bằng đồ thị đi trớc hoặc đồ thị truyền thông, sự tơng tác

cung cấp dịch vụ
đợc gọi là phục
vụ. Đối với mỗi
tơng tác, một
QT chỉ có thể là
khách hoặc phục
vụ. Tuy nhiên,
trong nhiều
trờng hợp, QT
có thể đóng vai
trò cả khách lẫn
phục vụ.
Tơng tác giữa khách và phục vụ thông qua dãy yêu cầu và trả lời. QT khách yêu cầu
dịch vụ từ phục vụ và tự khoá bản thân lại. Phục vụ nhận đợc yêu cầu từ khách, thực
hiện thao tác cần thiết và sau đó gửi TĐ trả lời cho khách. Khi có kết quả trả lời từ
phục vụ, khách lại bắt đầu tiếp tục thực hiện. Điều cơ bản ở đây là đồng bộ hỏi - đáp
để trao đổi thông tin.

Server

Khách
Truyền thông lôgic
Yêu cầu

Trả lời
Truyền thông thực sự

Yêu cầu

Trả lời

chỉ có dịch vụ hệ thống và dịch vụ gia tăng giá trị là có thể nhìn thấy (có thể sử dụng)
đợc từ phía ngời dùng.
Đối với ngời sử dụng thì chơng trình là một tập hợp của những (QT) khách và phục
vụ. Nếu chúng ta thi hành dịch vụ hệ thống nh là QT phục vụ và tách nó ra khỏi nhân
với mọi trờng hợp có thể đợc thì kích thớc của nhân sẽ đợc giảm một cách đáng
kể. Rõ ràng là nếu nh kích thớc của nhân đợc giảm xuống thì tính khả chuyển theo
nền phần cứng khác nhau là dễ dàng hơn. Một kết quả tự nhiên là sử dụng mô hình
Client/Server là QT chỉ cần một kiểu lời gọi hệ thống đến nhân đơn, chính là lời gọi
gửi và nhận yêu cầu. Vì vậy, nhân không cần thiết phải phân tích cú pháp lời gọi hệ
thống và xác định cái gì cần phải làm. Thay vào đó, trách nhiệm của QT phục vụ là
thông dịch thông điệp theo hiểu biết nhiều nhất của nhân về cấu trúc của TĐ. Giao
diện giữa QT và nhân trở nên đơn giản và đồng nhất.
Nhiều phục vụ có thể cùng tồn tại nhằm cung cấp cùng một dịch vụ. Chúng cần đợc
định danh hoặc theo tên hoặc theo chức năng mà chúng cần thực hiện. Đòi hỏi này
phục vụ việc định vị các phục vụ. Những phục vụ, đợc gọi là những phục vụ ràng
buộc hay phục vụ đại lý, chúng ràng buộc QT khách với những QT phục vụ đợc chọn
thành cặp, đôi khi chúng cũng cần đợc định vị. Cuối cùng, cần hạn chế một cách tối
thiểu các phục vụ mà hoàn toàn đã biết tên hoặc địa chỉ. Khi có yêu cầu từ phía khách,
phục vụ ràng buộc có thể chọn phục vụ nào thích hợp nhất cho khách đó hoặc là một
phục vụ nào đó làm cân bằng tải đối với các phục vụ. Nh một sự lựa chọn, cũng có
thể thực hiện việc xác nhận của khách cho phục vụ. Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 58-
3.4 Các dịch vụ thời gian
Mô hình không gian - thời gian tờng minh tơng tác giữa các QT, các sự kiện là đợc
ghi nhận chi tiết theo đồng hồ của riêng QT đó. Trong thực tế thì đồng hồ thờng đợc
sử dụng để thể hiện thời gian (một độ đo tơng đối về thời gian so với một điểm thời
gian làm mốc) và bộ đếm thời gian (một độ đo tuyệt đối cho khoảng thời gian) đợc

cần một thuật toán về đồng bộ đồng hồ. Hình 3.10 thể hiện kỹ thuật dịch vụ thời gian
gần giống với dịch vụ thời gian phân tán DTC (distributed time service) có trong DCE.
Bộ ghi nhận thời gian (TC) trong mỗi máy khách yêu cầu dịch vụ thời gian tới một
hoặc nhiều phục vụ thời gian (TS). Phục vụ thời gian lu giữ những thông tin thời gian
mới nhất và có thể truy cập đến nguồn thời gian thực toàn cầu. Phục vụ thời gian có thể
trao đổi thông tin thời gian, vì vậy dịch vụ thời gian cua nó có thể thích hợp với những
khách của nó. Tồn tại hai vấn đề cần quan tâm trong thực tế trong thi hành dịch vụ thời
gian, đó là độ trễ trong việc ghi nhận thông tin về thời gian phải đợc bù vào và sự
khác nhau giữa các nguồn thời gian phải đợc định cỡ.
Phần bù độ trễ

Hình 3.10 mô tả ba kiểu của truy cập thời gian: Phục vụ thời gian đến nguồn thời gian
toàn cầu, khách đến phục vụ thời gian và phục vụ thời gian lẫn nhau. Nhiều nguồn hệ
thống thời gian toàn cầu UTC (Universal Coordination Time) chuẩn có sẵn đối với
Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 59-
máy tính và những ứng dụng gắn chặt tới thời gian khác. Viện tiêu chuẩn và Công
nghệ quốc gia NIST của Mỹ cung cấp cách truy nhập với độ chính xác lên tới một
miligiây.
Dịch vụ thời gian máy tính tự động ACTS (Automated Computer Time Service) cung
cấp những dịch vụ modem tới thời gian NIST thông qua đờng điện thoại. ACTS đợc
thiết kế cho những ứng dụng chỉ yêu cầu những dịch vụ thời gian không thờng xuyên
:
QT quay số modem là quá chậm đối với việc đồng bộ những hoạt động phần cứng.
Đối với những truy nhập mang tính thờng xuyên
, NIST thực hiện một trạm phát sóng
ngắn WWV thực hiện việc tán phát những tín hiệu UTC. Độ trễ thời gian của TĐ có
thể đợc tính toán một cách chính xác nếu nh khoảng cách từ trạm phát sóng và
khoảng cách đến điểm truyền thông tin là đợc biết. Tuy nhiên, điều không may là
sóng radio lại rất nhạy cảm với môi trờng.

s
- t
p
. Công thức tính sự bù đó dựa trên giả thiết là QT giao thông trên
mạng (network trafic) là đối xứng.
Nếu đồng hồ ở máy khách nhanh hơn UTC mới thì nó sẽ đợc làm chậm lại bằng phần
mềm. Đồng hồ thời gian không thể quay lại đợc vì điều đó phủ nhận thời gian của các
sự kiên trớc đó. Vấn đề đồng hồ chậm hơn thì không đáng ngại nhng tốt nhất là tăng
Ghi chép thời gian khách
TS TS
TS
Nguồn UTC
ngoài
Hình 3.10. Một kiến trúc dịch vụ thời gian phân tán
TS
TS
Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 60-
tốc độ đồng hồ để nó đạt đợc cùng với UTC một cách từ từ. Ví dụ một sự tăng đột
ngột đồng hồ có thể loại bỏ QT đang đợi hoặc là nguyên nhân làm nảy sinh vấn đề hết
thời gian (time - out).
Truy cập UTC từ một khách tới một phục vụ thời gian là một mô hình dịch vụ kéo
(một kiểu dịch vụ bị động). Một phục vụ thời gian cần phải đóng vai trò chủ động
trong việc TĐ UTC đến những khách của nó. Mô hình dịch vụ đẩy (dịch vụ thời gian
tích cực) cho u điểm là duy trì đợc mức độ cao tính nhất quán của đồng hồ. Kiểu đẩy
giống nh sóng radio hoặc là TĐ vệ tinh những UTC mong đợi, cái mà mọi khách
đang chờ đón trả lời. Tuy nhiên, khách lại không có cách nào để xác định đợc độ trễ
của mạng. Điều trở ngại này làm cho giải pháp này chỉ thích hợp với những hệ thống
có phần cứng đa tán phát, nơi mà độ trễ CTĐ có thể ngắn hơn và có thể dự đoán đợc
trớc. Cả hai chế độ kéo và đẩy có thể cùng áp dụng trong việc truyền thông giữa các

chắn.
Việc xác định tính không chính xác giúp khách quyết định đợc UTC có đáp ứng đợc
độ chính xác cho ứng dụng đó hay không. Trung bình của UTC trong khoảng thời gian
có thể đợc sửa lại nh nh trong hình 3.11. Những khoảng không kế tiếp có thể bị bỏ
Loại bỏ
UTC1

UTC2

UTC3

UTC4

UTC5
UTC mới
Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 61-
đi. Những phần giao gồm nhiều UTC nhất thì đợc xác nhận. Điểm UTC mới đợc xác
định ở chính giữa đoạn giao đó.
Thậm chí ngay khi đã có phục vụ thời gian nhất quán, thì tính toán UTC của khách vẫn
không nhất quán do độ trễ truyền thông trên mạng không dự đoán đợc. Vấn đề không
nhất quán của khách có thể đợc giải quyết nếu khách theo chiến lợc nh phục vụ
thời gian là kết nối tới nhiều phục vụ thời gian và định cỡ UTC.
Đồng hồ vật lý đóng vai trò quan trọng trong việc phát triển phần mềm phân tán bởi vì
có rất nhiều giao thức phần mềm dựa vào time-out để nắm giữ loại trừ. Nếu khởi tạo
time-out bởi một QT đợc đặt dới sự kiểm tra của một QT khác đặt trên một máy
khác, hai đồng hồ vật lý phải đồng bộ có thể chấp nhận đợc đối với cả hai QT. Tem
thời gian vật lý đợc dùng để khử thông điệp bội (ngăn ngừa phát lại) và kiểm tra sự
mãn hạn quyền hạn đối với điều khiển truy nhập.
3.4.2 Đồng hồ logic

đo tơng đối đối với đồng hồ logic). Một QT tơng tác với một QT khác qua cặp hai
phép toán gửi (send) và nhận (receive) từ quá trình P
i
đến QT P
j
. Việc gửi đi phải đợc
thực hiện trớc việc nhận đợc. Do vậy, giữa sự kiện gửi
từ QT P
i
và sự kiện nhận tại
QT P
j
phải đảm bảo tính chất là C
i
(gửi) < C
j
(nhận) do QT nhận không thể hoàn thành
đợc trớc khi sự kiện gửi cha đợc thực hiện. Đồng hồ logic C dựa trên quan hệ xảy
ra trớc đợc tổng kết theo hai quy tắc sau:
1. Nếu a b trong cùng một QT thì C(a) < C(b).
2. Nếu a là sự kiện gửi một TĐ của QT P
i
và b là sự kiện nhận cũng TĐ đó của
QT P
j
thì C
i
(a) < C
j
(b).