Trang
Lời mở đầu
Môn học “Hệ tin học phân tán” là môn học cơ sở nhằm đặt nền móng
và kiến thức cơ bản cho công việc nghiên cứu và phát triển về sau. Nhằm
nghiên cứu sâu hơn về môn học tôi chọn đề tài “Điều khiển tải” để nghiên
cứu và làm tiểu luận cho môn học này.
Điều khiển tải là một trong những vấn đề được quan tâm đặc biệt
trong quá trình nghiên cứu hệ phân tán. Bởi đây là vấn đề có ảnh hưởng
lớn đến hoạt động và năng suất của hệ và cũng chưa có những thuật toán
hay giải pháp tối ưu để thực hiện. Vì thế, nó là mảnh đất màu mỡ cho việc
nghiên cứu. Tuy nhiên, trong phạm vi tiểu luận này tôi chỉ tham vọng được
bổ sung kiến thức để phục vụ cho quá trình nghiên cứu về sau.
Tiểu luận được chia làm 2 phần như sau:
Phần I:Lý thuyết về điều khiển tải
Phần này trình bày các khái niệm cơ bản về tải, điều khiển tải, các thuật
toán sử dụng trong điều khiển tải và một số giải pháp đang được sử dụng
phổ biến hiện nay.
Phần II:Bài tập
Phân tích một mô hình và lập trình mô phỏng để giải quyết những
vấn đề thường gặp trong điều khiển tải.
Tiểu luận Hệ tin học phân tán - Đề tài Điều khiển tải
1
Trang
PHẦN I LÝ THUYẾT VỀ ĐIỀU KHIỂN TẢI
1. Định nghĩa về tải
Tải là thuật ngữ chỉ tập hợp các yêu cầu phục tùng các qui tắc của một
bộ cung cấp.
Các tham số đặt trưng của tải là:
- Số lượng các yêu cầu được cung cấp tài nguyên;
- Bản chất của các yêu cầu;
- Phân tán theo thời gian và các yêu cầu tạo ra nó.

S
1
S
2
S
2
S
n
S
n
T
Bộ điều
khiển tải
2
Trang
Trình tự làm việc như sau: Đầu tiên, yêu cầu tài nguyên được hình
thành bởi một đề nghị phục vụ nào đó cho một Server xác định trong số
các Server có khả năng phục vụ. Bộ điều khiển tải có chức năng cung
cấp thông tin kịp thời và tương đối chính xác về khả năng các Server
chấp nhận hay không chấp nhận các yêu cầu.
Trong khi vận hành hệ, bộ điều khiển tải chỉ biết được giá trị gần đúng
của tải này, đó là nguyên nhân cơ bản của hai vấn đề khó khăn sau
đây:
1. Nếu tải vượt quá mức cho phép, bộ điều khiển tải có thể quyết
định sai là ném các yêu cầu ra ngoài tầm phục vụ. Điều đó có thể
dẫn đến việc sử dụng dưới mức giới hạn cho phép của các tài
nguyên được điều khiển bởi các Server.
2. Nếu tải còn dưới mức cho phép, bộ điều khiển tải chấp nhận một
yêu cầu; nếu các Server không có bộ điều khiển tải riêng của
mình. Điều đó dẫn đến sử dụng quá mức giới hạn của các tài

điều khiển, chủ yếu được rút ra từ các tầng giao vận. Có hai công nghệ
chúng ta cần lưu ý là điều khiển tổng quát và phân phối tải thích nghi.
Để nắm rõ hơn về các phương pháp điều khiển tải dưới đây chúng ta
xét các ví dụ trong các trường hợp điều khiển tải như sau:
3.1. Ví dụ về điều khiển tải tổng quát
Trong ví dụ này chúng ta xét cho trường hợp sử dụng phương pháp
này để mô phỏng cho mạng máy tính quốc gia về thí nghiệm vật lý để
từ đây ta rút ra những kinh nghiệm cần thiết cho việc triển khai bộ phân
phối tải một cách hiệu quả nhất.
Một vấn đề quan trọng nảy sinh mà ta cần quan tâm giải quyết là giới
hạn các gói thông tin lưu thông trong mạng. Khi tăng số lượng các gói
thông tin có nghĩa là tăng tải cho đường truyền dẫn đến lưu lượng
thông tin trên đường truyền giảm mạnh rồi đến mục lúc sẽ dừng hẳn
lại.
Hình 2. Sự quá tải trong mạng giao vận
Tiểu luận Hệ tin học phân tán - Đề tài Điều khiển tải
Lưu lượng
(gói/giây)
36 10872
4
Trang
Phương pháp điều khiển này thể hiện việc duy trì số lượng toàn bộ các
gói luận chuyển phải nhỏ hơn hay bằng một giá trị tối ưu T nào đó. Số
lượng này phát huy tác dụng trong toàn mạng và được gọi là “cái cho đi
qua” của chính mạng đó.
Một gói đầy đủ tham gia vào quá trình tuần hoàn cần phải là vật mang
một cái “cho đi qua” về phía đầu bên kia của mạng. Mỗi nút mạng được
coi là một thiết bị đầu cuối và được phép tự động lưu trữ bất kỳ từ các
cái “cho đi qua” có sẵn nhằm có thể tiếp nhận các gói mới. Nó truyền
tiếp các cái “cho đi qua” về các nút khác theo số dôi ra. Nếu một nút

Bảng này cho ta biết lần lượt các con đường cần đi qua để đến nút đích
trong thời hạn ngắn nhất và giá trị cụ thể của thời hạn này.
Ta ký hiệu {D
j
} là tập hợp các đích của mạng (j=1 m) và {L
j
} là tập hợp
các đường xuất phát từ nút (i=1 n).
Các bảng cần duy trì trong mỗi nút mạng như sau:
TD(j,i) Thời hạn để đến được D
j
xuất phát từ L
i
TR(j) Số hiệu của đường truyền tối ưu được đánh giá để
đến được D
j
(theo VD(j))
Hàm tối
ưu
VD(j)=min TD(j,i) với i=1 n
Hình dưới đây cho phép ta hình dung về bảng chọn đường thích nghi.
Trong ví dụ này, ta sử dụng một nút có 3 đường ra (n=3) và có thể gửi
đến năm nút nhận (m=5).
L1 L2 L3
D
1
0.2 0.1 0.4 L
2
0.1
D

Trang
Hình 4. Mô hình chọn đường thích nghi
Tại thời điểm cho trước, các nút mạng A,B,C lần lượt có các véc tơ VA,
VB, VC. Véc tơ VA cung cấp các thời hạn đánh giá cho các con đường AB,
AC, …AX. Theo chu kỳ cứ 2/3 giây trong mạng ARPANET mỗi nút đều
tính lại Véc tơ. Đó chính là thời hạn của mình và truyền giá trị đó cho các
bút lân cận để cập nhật các bảng thời hạn của chúng.
Ví dụ:
Khi A nhận được từ B và C các giá trị VB và VC, nó tính toán lại các thời
hạn để cho các đích truy cập thông qua B và C. Đó chính là thời hạn mới
để cho đích X là tối thiểu của AB + BX và AC + CX.
Ta lưu ý rằng các thời hạn được tính toán tương ứng với các tình hình
trước vài giây so với thời điểm hiện hành vì lý do cập nhật. Điều đó có thể
dẫn đến biến động tải trong các nút. Để điều khiển các gói tin, thời hạn của
đường đi ngắn nhất là đường xiên có nghĩa là tại đó ta phải thêm một số
gia.
• Cơ chế tiền tố của hệ DCS
Cơ chế này được sử dụng trong hệ DCS để cung cấp các tài nguyên như
các bộ xử lý chức năng hay các tập tin. Tài nguyên của hệ DCS được
quản lý bởi một Server. Các tài nguyên cùng loại được nhóm lại và quản lý
bởi một nhóm các Server. Nhóm này được định danh bởi một tên tổng quát
như đã trình bày ở trên. Một yêu cầu về tài nguyên được thể hiện bằng
cách gửi thông điệp, nhờ đó mà tất cả các Server liên quan đều có thể
nhận biết, thông thường thông qua tên tổng quát.
Việc cấp phát tài nguyên hoạt động theo hệ tiền tố. Khi hệ nhận được yêu
cầu về sử dụng tài nguyên, một Server sẽ trả lời bằng cách cho “phần trị “
cho việc phục vụ của nó phụ thuộc vào phần tải thiết bị được quản lý. Như
Tiểu luận Hệ tin học phân tán - Đề tài Điều khiển tải
B
B

có thể truy cập vào bộ nhớ chung. Việc thực hiện một tiến trình được tiến
hành trên một trong các bộ xử lý thuộc vào một phân tử cho trước. Một
phân tử có thể thực hiện nhiều tiến trình cùng một lúc.
Cơ chế mà ta sẽ giới thiệu liền sau đây nhằm phục vụ cho việc cung cấp
một phân tử để thực hiện một tiến trình trong điều kiện tuân thủ tính cân
bằng tải giữa các phân tử với nhau. Cách đo tải được xác định bởi số
lượng các bộ xử lý có trong một phân tử. Khi tạo ra một tiến trình thì có
một yêu cầu được đăng ký vào trong bộ nhớ chung. Tất cả các phân tử
đều được biết đến khi có một yêu cầu diễn ra. Trong một phân tử, một bộ
xử lý tự do chờ một thời gian thích hợp với số lượng các bộ xử lý bị bận
trong phân tử này trước khi có ý định rút yêu cầu. Việc rút các yêu cầu
được tiến hành theo kiểu loại trừ tương hỗ.
Bộ xử lý nhận yêu cầu là bộ xử lý có thời gian chờ ít nhất. Do vậy, nó
thuộc về phần tử mà tải của phần tử này là ít nhất. Các bộ xử lý khác
thấy rằng yêu cầu đã bị xóa và chỉ cố gắng đáp ứng các yêu cầu mới mà
thôi. Thời gian chờ của một bộ xử lý được chọn rất bé để không làm tăng
thời gian thực hiện của tiến trình.
4. Kết luận
Để chọn lựa phương án triển khai giải quyết vấn đề tải trong hệ phân
tán, người ta quan tâm hàng đầu đến độ tin cậy, ổn định và chi phí thực
Tiểu luận Hệ tin học phân tán - Đề tài Điều khiển tải
8
Trang
hiện của chúng. Tuyệt đại bộ phận các giải thuật đã được nghiên cứu
cho vấn đề tải, đến nay vẫn còn là các giải thuật tương đối chính xác có
nghĩa là chưa có giải thuật nào đạt đến độ hoàn hảo như mong muốn.
Như vậy, trong truờng hợp chọn đường theo kiểu thích nghi như mạng
APARNET hay Internet là giải pháp chấp nhận được.
Để cung cấp các bộ xử lý với các tải tương đối đồng đều, người ta đã
đề ra chiến lược phân nhóm theo các phần tử như trong hệ MCS.

Các thao tác cập nhật và tra cứu cơ sở dữ liệu để đơn giản ta qui về bài
toán truy xuất giá trị tồn kho và thao tác nhập kho. Giả sử bảng mô tả kho
có các nội dung sau:
Tên trường Mô tả
MaMH Mã mặt hàng
Soluong Số lượng mặt hàng
3. Chương trình mô phỏng
Theo yêu cầu của bài toán ta chỉ mô phỏng chương trình tại trại đáp ứng
truy vấn tại nơi chứa cơ sở dữ liệu mà thôi.
3.1. Mô phỏng việc tra cứu thông tin
Thủ tục tra cứu nhận một yêu cầu truy vấn là tra cứu thông tin tại trạm
thông qua một câu truy vấn có gắn theo 3 ký tự đầu tiên làm mã trạm.
Khi nhận được câu truy vấn bộ đáp ứng truy vấn sẽ cắt phần đầu của
câu truy vấn để kiểm tra giá trị của trạm. Nếu đúng thì thực hiện câu
truy vấn nếu không sẽ trả về giá trị Null.
Tên thủ tục Tracuu(QueryMessage)
{
// Kiểm tra thông tin
// Cắt lấy đoạn thông tin đầu để xác định trạm cần
truy vấn
Prefix=Cat_chuoi(QueryMessage)
If (Prefix=Mã trạm)
{
Gia_tri_ton_kho=Thuc_hien_cau_lenh(Select)
}
Else //Khong phai tram nay
{
Tracuu=null
Exit
}

}
Else //Khong phai tram nay
{
Capnhat=False
}
}
Tiểu luận Hệ tin học phân tán - Đề tài Điều khiển tải
11
Trang
TÀI LIỆU THAM KHẢO

[1] Hệ phân tán – TS. Lê Văn Sơn, Nhà xuất bản Đại học quốc gia TP.
Hồ Chí Minh.
[2] Distributed Systems (Concepts and Design) – George Coulouris,
Jean Dollimore và Tim Kindberg.
Tiểu luận Hệ tin học phân tán - Đề tài Điều khiển tải
12
Trang
MỤC LỤC

Lời mở đầu 1
PHẦN I LÝ THUYẾT VỀ ĐIỀU KHIỂN TẢI 2
1. Định nghĩa về tải 2
2. Giới thiệu về điều khiển tải 2
2.1. Điều khiển tải tổng quát 2
2.2. Điều khiển phân tán tải 3
3. Triển khai quá trình điều khiển 4
3.1. Ví dụ về điều khiển tải tổng quát 4
3.2. Ví dụ về điều khiển tải thích nghi 5
4. Kết luận 8