Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 125-
chơng V. lập lịch quá trình phân tán
Phơng tiện TT và đồng bộ là các thành phần hệ thống thiết yếu hỗ trợ việc thực hiện
đồng thời các QT tơng tác. Trớc khi thực hiện, QT cần phải đợc lên lịch (lập lịch)
và định vị tài nguyên. Mục đích chính của lập lịch là nâng cao độ đo hiệu năng tổng
thể hệ thống, chẳng hạn thời gian hoàn thành QT và tận dụng bộ xử lý. Việc tồn tại các
nút xử lý phức trong hệ phân tán làm nảy sinh vấn đề thách thức cho lập lịch QT trên
các bộ xử lý và ngợc lại. Lập lịch không chỉ đợc thực hiện cục bộ trên mỗi nút mà
trên toàn bộ hệ thống. Các QT phân tán có thể đợc thực hiện trên các nút xử lý từ xa
và có thể di trú từ nút này tới nút khác để phân bố tải nhằm tăng hiệu năng. Mục đích
thứ hai của lập lịch là thẹc hiện trong suốt định vị và hiệu năng bằng lập lịch QT phân
tán.
Vấn đề lập lịch QT (hay công việc) đã đợc khảo sát rộng rãi đối với nghiên cứu điều
hành. Đã có nhiều kết quả lý thuyết về độ phức tạp của lập lịch bộ đa xử lý. Tuy nhiên,
lập lịch QT trong hệ phân tán cần đề cập các chú ý thực tế thờng bị bỏ qua trong
phân tích lập lịch đa xử lý truyền thống. Trong hệ phân tán, tổng phí TT là đáng kể, tác
dụng của hạ tầng cơ sở không thể bỏ qua và tính động của hệ thống phải đợc định
vị. Các thực tế này góp phần tạo thêm sự phức tạp của lập lịch QT phân tán.
Chơng này đa ra mô hình nhằm đạt đợc hiệu quả hạ tầng TT và hệ thống khi lập
lịch. Lập lịch QT phân tán đợc tổ chức thành hai nội dung: lập lịch QT tĩnh, và chia
sẻ và cân bằng tải động. Thi hành thuật toán lập lịch phân tán đòi hỏi thực hiện từ xa
và/hoặc năng lực di trú QT trong hệ thống. Một số vấn đề thi hành thực hiện từ xa và di
trú QT đợc đề cập. Kết thúc chơng giới thiệu hệ thống thời gian thực phân tán, trong
đó lập lịch là khoảng tới hạn thời gian và xứng đáng đợc quan tâm đặc biệt.
5.1. Mô hình hiệu năng hệ thống
Các thuật toán song song và phân tán đợc mô tả nh tập QT phức đợc chi phối bằng
các quy tắc điều chỉnh tơng tác giữa các QT. ánh xạ thuật toán vào một kiến trúc
đợc xem xét nh
bộ phận của thiết kế thuật toán hoặc đợc xem xét một cách riêng
biệt nh bài toán lập lịch đối với một thuật toán cho trớc và một kiến trúc hệ thống

tải không hạn chế các QT độc lập. Nếu QT truyền thông với một QT khác thì chiến
lợc di trú nên chú ý cân bằng các thay đổi trong các nhu cầu truyền thông giữa các
bộ xử lý do thay đổi bộ xử lý và lợi ích từ chia xẻ tải.
Phân hoạch bài toán thành nhiều QT để giải làm thời gian hoàn thành bài toán nhanh
hơn. Tăng tốc đợc coi nh độ đo hiệu năng là mục tiêu đáng quan tâm trong thiết kế
các thuật toán song song và phân tán. Tăng tốc tính toán là một hàm của thiết kế thuật
toán và hiệu quả của thuật toán lập lịch ánh xạ thuật toán vào kiến trúc hệ thống hạ
tầng. Dới đây đa ra một mô hình tăng tốc mô tả và phân tích mối quan hệ giữa thuật
toán, kiến trúc hệ thống và lịch thực hiện. Trong mô hình này, hệ số tăng tốc S là hàm
của thuật toán song song, kiến trúc của hệ thống và lịch thực hiện, đợc biểu diễn theo
công thức:
S = F(thuật toán, hệ thống, lịch).
S có thể đợc viết nh sau:
Trong đó :
+ OSPT (Optimal Sequential Processing Time): thời gian tốt nhất có thể đạt đợc
trên bộ đơn xử lý sử dụng thuật toán tuần tự tốt nhất.
+ CPT (Concurrent Processing Time): thời gian thực sự đạt đợc trên một hệ n-bộ
xử lý cùng với thuật toán đồng thời và một phơng pháp lập lịch cụ thể đang đợc xem
xét.
+ OCPT
ideal
(Optimal Concurrent Processing Time on an ideal system): thời gian
tốt nhất có thể đạt đợc với cũng thuật toán đồng thời đợc xem xét trên một hệ n-bộ
di
iedal
ideal
xSS
CPT
OCPT
x

trong đó:
OSPT
1

=
=
m
i
i
P
RP
và
nOCPT
P
RC
ideal
m
i
i
*
1

=
=

và n là số lợng bộ xử lý. Đại lợng

=
m
i

tuần tự tối u bằng một thuật toán thích hợp thực hiện đồng thời nhng có thể có tổng
nhu cầu xử lý lớn hơn. RP khác với S
d
ở chỗ RP là lợng thời gian hao phí của thuật
toán song song do việc thay đổi thuật toán, trong khi S
d
là lợng thời gian hao phí của
thuật toán song song do việc thi hành thuật toán.
Độ đo đồng thời liên quan RC (Relative Concurency) đo mức độ sử dụng tốt nhất của
hệ n-bộ xử lý. Nó cho thấy bài toán đã cho và thuật toán dành cho bài toán tốt nh thế
nào đối với hệ n-bộ xử lý lý tởng. RC=1 tơng ứng với việc sử dụng các bộ xử lý là
tốt nhất. Một thuật toán đồng thời tốt là thuật toán làm cho RP đạt giá trị nhỏ nhất và
RC đạt giá trị lớn nhất. Biểu thức cuối cùng cho tăng tốc S là:
n
RP
RC
S ì
+
ì=

1
1

Tóm lại, nhân tố tăng tốc S là một hàm của RC (tổn thất lý thuyết khi song song hóa),
RP (lợng bổ sung vào tổng nhu cầu tính toán),

(thiếu hụt song song hóa khi thi hành
trên một máy thực) và n (số bộ xử lý đợc sử dụng).
Số hạng



nh sau:
'
'
)()()',(
),(
schedsyst
iedal
iedaliedal
iedal
iedal
iedal
iedal
OCPT
OCPTYCPT
OCPT
YCPTYXCPT
OCPT
OCPTYXCPT


+=

+

=

=

Tơng tự, chúng ta làm ngợc quá trình phân tích theo giải tích tổn thất hiệu quả lập

thuật toán lập lịch phân tán.
Mô hình tăng tốc chung tích hợp 3 thành phần chính: phát triển thuật toán, kiến trúc hệ
thống và chiến lợc lập lịch, với mục đích làm giảm đến mức tối thiểu tổng thời gian
hoàn thành (makespan) của tập các QT tơng tác. Nếu các QT không bị ràng buộc bởi
quan hệ đi trớc và đợc tự do phân phối lại hoặc đợc di trú dọc theo các bộ xử lý
trong hệ thống thì hiệu năng đợc cải tiến hơn nữa nhờ chia xẻ tải. Điều đó có nghĩa là,
các QT có thể đợc di trú từ những nút có tải lớn tới những nút rỗi (nếu tồn tại các nút
đó). Có thể đợc tiến thêm một bớc xa hơn khi tới chia xẻ tải giữa tất cả các nút sao
cho càng đều càng tốt, bằng phơng pháp tĩnh hoặc động. Phân bố tải tĩnh đợc gọi
chia xẻ tải, và phân bố tải động đợc gọi là cân bằng tải. Lợi ích của phân bố tải là
các bộ xử lý đợc tận dụng triệt để hơn và cải tiến đợc thời gian quay vòng các QT.
Di trú QT rút gọn thời gian xếp hàng, kể cả giá tăng thêm theo tổng phí TT.
Mục đích của chia xẻ tải trong hệ phân tán là làm hoàn toàn rành mạch. Điều đó cũng
phù hợp với bất kỳ việc khởi tạo máy tính gồm nhiều nút xử lý đợc ghép nối lỏng,
luôn có một số nút có tải lớn và một số nút có tải nhỏ, nhng phần lớn các nút là hoàn
toàn không tải. Để tận dụng hơn về năng suất xử lý, các QT có thể đợc gửi tới các bộ
xử lý rỗi theo phơng pháp tĩnh ngay khi chúng vừa xuất hiện (tơng ứng với mô hình
bộ xử lý xâu) hoặc di trú theo phơng pháp động từ những bộ xử lý có tải lớn đến
những bộ xử lý có tải nhỏ (tơng ứng với mô hình trạm làm việc). Thời gian quay vòng
QT cũng đợc cải tiến. Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 129-
Hình 5.3 trình bày hai mô hình hàng đợi đơn giản về môi trờng phân tán theo bộ xử lý
xâu và theo trạm làm việc so sánh với hệ thống các trạm làm việc cô lập với đờng
tham chiếu (baseline). Để rõ ràng, trong các mô hình này chỉ gồm hai nút xử lý. Trong
mô hình bộ xử lý xâu, một QT đợc gửi tới một bộ xử lý phù hợp và ở lại đó trong suốt
thời gian thực hiện nó.
Hiệu năng hệ thống đợc mô tả theo mô hình dòng xếp hàng có thể tính đợc nhờ sử

M/M/2
à
à


à
à
(c) Mô hình
tr
ạm di trú


à

à
(a) Trạm cô
lập M/M/1
Hình 5.3. Mô hình hàng đợi BXL xâu và trạm làm việc

Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 130-
Trong mô hình
trạm làm việc
di trú, các QT
đợc phép dịch
chuyển từ trạm
này tới trạm
khác. Quyết
định di trú QT
vào lúc nào, ở

M/M/1 (không có chia xẻ tải) và M/M/2 (mô hình bộ xử lý xâu lý tởng với tổng phí
TT là không đáng kể). Tỷ lệ di trú QT thay đổi từ 0 đến , tơng ứng với hiệu năng
tiệm cận của M/M/1 và M/M/2.
5.2. Lập lịch quá trình tĩnh
Lập lịch QT tĩnh (lý thuyết lập lịch tiền định) đã đợc nghiên cứu rộng rãi. Bài toán đặt
ra là lập lịch cho một tập thứ tự bộ phận các bài toán trên hệ thống đa xử lý với các bộ
xử lý giống nhau nhằm mục tiêu giảm thiểu toàn bộ thời gian hoàn thiện (makespan).
Có nhiều công trình tổng quan xuất sắc, trong đó có bài viết của Coffman và Graham.
Các nghiên cứu trong lĩnh vực này chỉ ra rằng, tuy có các trờng hợp giới hạn (chẳng
hạn, lập lịch các bài toán có thời gian thực hiện đơn vị hay mô hình song xử lý), bài
toán lập lịch tối u là độ phức tạp NP-đầy đủ. Bởi vậy, hầu hết các nghiên cứu định
hớng sử dụng phơng pháp xấp xỉ hay phơng pháp heuristic nhằm đi tới giải pháp
gần tối u cho vấn đề này. Hệ thống tính toán hạ tầng của bài toán cổ điển với các giả
thiết không có chi phí liên QT đa đến cạnh tranh tryền thông và bộ nhớ. Giả thiết
này có thể hợp lý với kiến trúc đa xử lý nào đó. Tuy nhiên, nó không có giá trị đối với
hệ thống phân tán CTĐ hoặc mạng máy tính, trong đó TTLQT không những không thể
bỏ qua mà còn là một đặc trng quan trọng của hệ thống. Do quá thô bạo khi bỏ qua
chú ý TT, với những hệ thống chi phí TT là không thể bỏ qua đợc, tập trung vào các
tiệm cận heristic tốt nhng dễ dàng thi hành để lập lịch QT trong hệ phân tán.
M/M/1
Thời gian tổng
M/M/2
Tải hệ thống
Hình 5.4. So sánh hiệu năng theo chia xẻ tải
Mô hình trạm
Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 131-
Một thuật toán lập lịch phân tán heuristic tốt là nó phải cân bằng tốt và giảm thiểu sự
chồng chéo trong tính toán và truyền thông. Khảo sát hai bài toán lập lịch đặc biệt, một
là lập lịch tất cả QT trong một bộ xử lý đơn và hai là mỗi bộ xử lý đợc phân công tới

truyền thông
P3
P2P1
F/4 D/6
G/4
E/6
C/4
A/6 B/5
(a) Mô hình QT
đi trớc
Hình 5.5. Mô hình hệ thống truyền thông và quá trình đi trớc
Hà Quang Thụy Bài giảng Hệ điều hành phân tán (Phần 1)
- 132-
truyền thông nội bộ. Mô hình này rất đơn giản, nó giữ truyền thông mà không cần đa
ra chi tiết cấu trúc phần cứng. Giá thành truyền thông giữa hai nhiệm vụ đợc tính
bằng tích đơn vị giá thành truyền thông trong đồ thị hệ thống truyền thông với số đơn
vị TĐ trong đồ thị xử lý u tiên. Ví dụ, nhiệm vụ A và E trong hình 5.5 đợc lập lịch
tơng ứng trên bộ xử lý P1 và P3, giá thành truyền thông là 8 = 2*4. Raywayd Smith
đa ra khảo sát mô hình tơng tự nhng với một số hạn chế trong tất cả các QT có đơn
vị tính toán và thời gian truyền thông. Thậm chí với một giả thiết đơn giản thì việc tìm
giá trị tối thiểu của toàn bộ thời gian hoàn thành là NP-complete. Vì vậy chúng ta sẽ
ứng dụng thuật toán heuristic cho việc tìm kiếm một ánh xạ tốt từ mô hình QT tới mô
hình hệ thống.
Nếu bỏ qua phí tổn đờng truyền, chúng ta xem xét phơng pháp heuristic tham ăn
đơn giản: chiến lợc LS (lập lịch danh sách). Không một bộ xử lý nào đặt ở chế độ
nhàn rỗi nếu còn những tác vụ có thể cần xử lý. Đối với DAG trong hình 5.5 a, kết quả
lập lịch trong hình 5.6 a. Tổng thời gian hoàn thành là 16 đơn vị. Đối với đồ thị QT đi
trớc, khái niệm về đờng tới hạn là rất có ích. Đờng tới hạn là đờng thực hiện dài
nhất trong DAG, nó lại là đờng ngắn nhất của toàn bộ thời gian hoàn tất. Đờng tới
hạn rất quan trọng trong nội dung lập lịch. Nó đợc sử dụng thờng xuyên để phân tích

lịch có tổng thời gian hoàn thành là 28 đơn vị, nh trình bày trong hình 5.6 b Dashed
lines trong hình biểu diễn QT đợi truyền thông (giá thành đơn vị truyền thông đợc
nhân bởi số lợng các đơn vị thông báo).
Chiến lợc ELS không thể đạt tối u. Vấn đề cơ bản là việc quyết định lập lịch đã đợc
thiết lập mà không đợc báo trớc trong việc truyền thông. Thuật toán có thể đợc cải
tiến khi chúng ta trì hoãn quyết định lâu nhất cho đến khi chúng ta biết nhiều hơn về
hệ thống. Theo chiến lợc tham ăn này chúng ta có phơng pháp lập lịch u tiên tác vụ
đầu tiên (ETF), tác vụ sớm nhất phải đợc lập lịch đầu tiên. Sử dụng chiến lợc này
trong cùng một ví dụ, chúng ta sẽ trì hoãn lập lịch tác vụ F bởi tác vụ E sẽ trở thành lập
lịch đầu tiên nếu trì hoãn truyền thông cũng liên quan đến việc tính toán. Lập lịch ETF
trong hình 5.6 c đa ra kết quả tốt hơn là tổng thời gian hoàn thành là 18 đơn vị.
Mô hình QT và hệ thống là khá rõ ràng để mô hình hoá bài toán quá trình lập lịch
trong DAG vào hệ thống với sự trễ truyền thông. Ví dụ chỉ ra rằng một lịch tối u cho
hệ thống này không nhất thiết là lịch tốt cho hệ thống khác đồng thời với cấu trúc
truyền thông khác nhau. Lập lịch tốt hơn có thể đạt đợc nhờ trộn nhau giữa truyền
thông với tính toán và vì vậy che dấu hiệu quả tổng phí truyền thông. Khái niệm đờng
tới hạn có thể đợc dùng để hỗ trợ việc che dấu truyền thông (thu hút tổng phí truyền
thông vào đờng tới hạn). Bất kỳ đờng tính toán ngắn hơn đờng tới hạn đợc thu vào
tổng phí TT nào đó để chập với một tính toán khác mà không ảnh hởng đến tổng thời
gian hoàn thiện.
5.2.2. Mô hình quá trình truyền thông

Mô hình đồ thị đi trớc biểu diễn QT đợc thảo luận trong phần trớc là mô hình tính
toán. Chơng trình đợc biểu diễn bằng DAG là những ứng dụng ngời dùng điển
hình, trong đó ràng buộc đi trớc giữa các bài toán trong chơng trình đợc ngời
dùng chỉ dẫn rõ ràng. Mục tiêu cơ bản của lập lịch là đạt sự đồng thời tối đa việc thực
hiện bài toán trong chơng trình. Giảm tối thiểu truyền thông bài toán đóng vai trò thứ
yếu, mặc dù có ảnh hởng đáng kể tới số hiệu hiệu năng chính: thời gian hoàn thiện
tổng thể.
Lập lịch QT cho những ứng dụng hệ thống theo nhiều bối cảnh rất khác nhau, bởi vì

j
(p
i
) để biểu thị giá thành cho QT j trên p
i
, trong đó p
i
là
bộ xử lý đợc dùng cho QT j. Giá thành truyền thông c
i,j
(p
i
, p
j
) giữa hai QT i và j
dùng cho hai bộ xử lý khác nhau p
i
và p
j
là tỉ lệ với trọng số cung kết nối i với j. Giá
thành truyền thông đợc xem là không đáng kể (giá thành bằng 0) khi i =j. Bài toán
đợc đặt ra là tìm phân công tối u của mô hình m mođun QT tới P bộ xử lý theo mối
quan hệ của hàm đối tợng dới đây đợc gọi là Bài toán định vị mođun.


+=
)(),(
,
)(
),()(),(

thành để chạy trên bộ xử
lý A nhng cần 10 đơn
vị giá thành khi chạy
trên bộ xử lý B. Nhãn
gán trên một cạnh của
đồ thị truyền thông là
giá thành truyền thông
2
12
3
5
3
4
4
6
12
8
1
2
6
11
B
A
4
10


4
3
3

trong vết cắt là tổng giá thành truyền thông và giá thành tính toán.
Việc tính tập cắt giá thành tối thiểu cho mô hình trên là tơng đơng với việc tìm dòng
cực đại (maximum-flow) và cắt tối thiểu (minimum-cut) của mạng hàng hóa. Đồ thị ở
hình 5.8 có thể hiểu nh một mạng với các đờng giao thông (cung) nối các thành phố
(đỉnh) với nhau. Trọng số trên đờng nối là thông lợng của đoạn. Nút A là thành phố
nguồn và nút B là thành phố đích của việc vận chuyển hàng hoá. Khi cho một đồ thị
hàng hoá, vấn đề tối u là tìm ra luồng cực đại từ nguồn tới đích. Fort và Fulkerson
trình bày một thuật toán gán nhãn cho phép tìm một cách hệ thống đ
ờng mở rộng dần
từ nguồn tới đích (thuật toán đợc thấy trong hầu hết các cuốn sách giáo khoa về thụât
toán). Hai ông cũng chứng minh rằng luồng cực đại (maximum fow) cho một mạng
tơng đơng mặt cắt nhỏ nhất (minimum cut) làm tách rời nguồn với đích trong đồ thị.
Thuật toán luồng cực đại và định lý mặt cắt nhỏ nhất của luồng cực đại hoàn toàn phù
hợp với sự tối u hoá bài toán định vị mô - đun (sự lập lịch QT) cho hai bộ xử lý.
Để tổng quát hoá bài toán có nhiều hơn hai bộ xử lý, Stone phác thảo giải pháp cho hệ
thống có 3 bộ xử lý và đề xuất một phơng pháp lặp sử dụng thuật toán cho hai bộ xử
lý để giải quyết những bài toán có n bộ xử lý. Để tìm ra một sự định vị mô-đun của m
QT cho n bộ xử lý, thuật toán mặt cắt nhỏ nhất luồng cực đại có thể áp dụng cho một
bộ xử lý P
i
và một bộ siêu xử lý ảo P bao gồm các bộ xử lý còn lại. Sau khi vài QT đã
đợc lên lịch cho P
i
, thủ tục đợc lặp lại tơng tự trên bộ siêu xử lý cho đến khi tất cả
các QT đợc ấn định.
Bài toán định vị mô-đun là phức tạp vì những mục đích của sự tối u hoá cho việc giảm
chi phí tính toán và truyền tin xuống mức thấp nhất thờng mâu thuẫn (đối lập) với
nhau. Bài toán đủ quan trọng để chứng minh cho những giải pháp mang tính kinh
nghiệm (tự tìm tòi). Một phơng pháp để phân chia sự tối u hoá tính toán và truyền
thông trở thành 2 vấn đề riêng biệt. Trong một mang máy tính nơi chi phí truyền tin có

ớc về thời gian chạy và cách thức truyền thông của quá
trình. Với mô hình QT đi trớc, mục tiêu đầu tiên là tối thiểu hoá thời gian hoàn thiện
toàn bộ, trong khi mô hình QT TT cố gắng tối thiểu hoá tổng chi phí TT, đồng thời tìm
cách thoả mãn những ràng buộc về tính toán. Một mô hình toán học và một thuật toán
tốt là yếu tố cần thiết cho lập lịch. Tuy nhiên, việc tính toán lại tập trung và chỉ xảy ra
tại một thời điểm định trớc.
Biết trớc thông tin về các QT là không thực tế trong hầu hết các ứng dụng phân tán.
Với đòi hỏi kết nối và tính toán không cần thông tin trớc, ta phải dựa trên một chiến
lợc lập lịch linh hoạt, cho phép những quyết định đợc thực hiện tại địa phơng.
Trong phần này, chúng ta sẽ sử dụng mô hình QT không liên kết để thể hiện một số
chiến lợc lập lịch động. Việc sử dụng mô hình không liên kết không có nghĩa là mọi
QT không có liên hệ với nhau, mà đợc hiểu theo nghĩa: chúng ta không biết một QT
này tơng tác với các QT khác nh thế nào. Vì vậy, ta có thể lập lịch với giả sử rằng
chúng không kết nối. Điều này tơng đơng với việc bỏ qua sự phụ thuộc giữa các QT.
Với mô hình này, mục tiêu của việc lập lịch khác so với mục tiêu của mô hình u tiên
và mô hình liên hệ. Mục tiêu lớn nhất có thể thấy đợc trong lập lịch là hớng tới tính
hiệu dụng (utilzation) của hệ thống và tính công bằng (fairness) cho các QT xử lý của
ngời dùng. Tính hiệu dụng của các bộ xử lý có liên quan trực tiếp đến các thớc đo
tốc độ nh khối lợng xử lý và thời gian hoàn thành. Sự công bằng rất khó để định
nghĩa cũng nh ảnh hởng của nó đến hoạt động là không rõ ràng. Có thể nói hiệu
dụng và công bằng là yêu cầu trong lập lịch cho mô hình không liên kết của một hệ
thống phân tán.
Một chiến lợc đơn giản để nâng cao hiệu quả sử dụng của một hệ thống là tránh đợc
nhiều nhất tình trạng bộ xử lý rỗi. Giả sử rằng ta có thể chỉ định một QT điều khiển
chứa đựng thông tin về kích thớc hàng đợi của mỗi bộ xử lý. Các QT đến và ra khỏi