Lời mở đầu
Hệ tin học phân tán là hệ thống rất đa dạng, đa diện, phức tạp về mặt cấu
trúc, là vùng tri thức hiện đại đang được các chuyên gia công nghệ thông tin đặc
biệt quan tâm và đổi mới rất nhanh chóng.
Một trong những tư tưởng lớn của các hệ phân tán là phân tán hóa các quá
trình xử lý thông tin và thực hiện các công việc đó trên các trạm xa nhau. Đó là
cơ sở để xây dựng các hệ ứng dụng lớn như thương mại điện tử, giáo dục điện
tử, chính phủ điện tử.
Phân tán hóa các quá trình xử lý, tạo nên ưu thế của hệ có thể đáp ứng
việc giải quyết các bài toán lớn, một cách nhanh chóng. Nhưng cũng tạo tính
phức tạp, nan giải trong các yêu cầu thiết lập hệ. Việc hợp lực của các thành
viên trong hệ, dẫn đến hàng loạt các vấn đề như: định danh, cấp phát tài nguyên
dùng chung (đảm bảo tránh tương tranh), giải quyết sự cố tạo nên tính tin cậy
của hệ. Để đảm bảo tính gắn bó của hệ, yêu cầu đặt ra trước hết là đồng bộ hóa
các tiến trình. Với hệ phân tán (không có bộ nhớ chung, bộ tạo xung đồng hồ
chung), khả năng gắn bó và việc đồng bộ hóa cho hệ chỉ dựa trên phương tiện
duy nhất là truyền thông điệp, nên lời giải cho yêu cầu đồng bộ hóa thường chỉ
dừng lại ở mức chấp nhận được đối với mỗi hệ .
Trong phạm vi của tiểu luận này tôi chỉ đề cập đến một khía cạnh nhỏ
trong hệ tin học phân tán đó là “Trật tự từng phần và vấn đề đồng bộ hóa các
tiến trình”,
Để hoàn thành tiểu luận này, tôi xin chân thành cám ơn sự chỉ bảo tận
tình của Thầy giáo: PGS.TS.Lê Văn Sơn và các bạn học viên trong lớp . Tuy
nhiên chắc hẳn vẫn còn nhiều thiếu sót, kính mong sự góp ý của thầy giáo và
các bạn .
Tiểu luận môn: Hệ phân tán
PHẦN A. CƠ SỞ LÝ THUYẾT
CHƯƠNG 1. GIỚI THIỆU VỀ HỆ TIN HỌC PHÂN TÁN
1.1. Hệ Phân tán
Hệ tin học phân tán hay nói ngắn gọn là hệ phân tán (Distributed System)
là hệ thống xử lý thông tin bao gồm nhiều bộ xử lý hoặc vi xử lý nằm tại các vị

trí khác nhau và được liên kết với nhau thông qua phương tiện viễn thông dưới
sự điều khiển thống nhất của một hệ điều hành.
Hệ tin học phân tán thực hiện hàng loạt các chức năng phức tạp, nhưng cơ
bản nhất là đảm bảo cung cấp cho người sử dụng khả năng truy cập có kết quả
đến các loại tài nguyên vốn có và rất đa dạng của hệ thống như là những tài
nguyên dung chung
Hệ thống tính toán phân tán đã tạo được bước ngoặc vĩ đại so với các hệ
tập trung, và hệ khách chủ (Client/Server). Việc tính toán phân tán về cơ bản
cũng giống như việc tính toán của hệ khách chủ trên phạm vi rộng lớn. Dữ liệu
được chứa trên nhiều máy chủ ở tại nhiều vị trí địa lý khác nhau kết nối nhau
thông qua mạng diện rộng WAN hình thành các nơi làm việc, các phòng ban,
các chi nhánh của một cơ quan.
Tính toán phân tán hình thành từ tính toán tập trung và Client/Server. Các
mạng được xây dựng dựa trên kỹ thuật Web (ví dụ như: Internet; intranet…) là
các mạng phân tán. Hệ thống cơ sở dữ liệu back-end có thể được nối kết với các
server Web để lấy được các thông tin động. Kỹ thuật Web này đã mở ra hướng
mới cho hệ phân tán. Các trình duyệt Web giúp cho khách hàng trên toàn cầu kết
nối với hệ thống Web chủ, mà không bị khống chế bởi bất kỳ hệ điều hành nào
đang chạy trong máy của khách hàng.
1.2. Các điểm mạnh trong hệ tin học phân tán
- Đặc điểm cơ bản của hệ tin học phân tán
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 2
Tiểu luận môn: Hệ phân tán
• Thời hạn truyền thông tin trong hệ không giống nhau, các thông điệp có
thể bị mất trong quá trình chuyển tải, các thông điệp có thể được truyền
kép và hệ thống có thể rơi vào sự cố.
• Một (hay nhiều) máy tính cấu thành của hệ phân tán có thể bị sự cố và
hoạt động của toàn hệ trở nên kém hiệu quả.
- Cơ chế tính toán phân tán hỗ trợ truy cập các dữ liệu được lưu ở nhiều nơi.
- Nhờ cơ chế nhân bản nên người dùng chỉ cần truy cập cục bộ cũng lấy được

các thông tin từ các trung tâm chính ở rất xa.
- Hệ thống khắc phục được các hiểm họa địa phương. Vì nếu chúng ta không
truy cập dữ liệu được tại vị trí này, chúng ta có thể thử ở nơi khác.
- Dữ liệu phân tán đòi hỏi phải được nhân bản và đồng bộ hóa cao thông qua
các mối liên kết mạng, điều này làm cho việc quản trị và giám sát phức tạp hơn.
Một số nhà quản trị cho rằng, ở hệ thống như thế này sẽ gây khó khăn trong vấn
đề bảo mật và điều khiển.
- Hệ phân tán được xây dựng trên giao thức TCP/IP và các kỹ thuật Web
cùng với các ứng dụng trung gian (middleware) thúc đẩy việc tính toán phân tán.
Quả thật đây là một đổi thay mang tính cách mạng. Nhiệm vụ trước mắt là làm
thế nào để chuyển tiếp sang hệ này một cách khoa học.
1.3. Xử lý Phân tán
Có hai khái niệm xử lý phân tán và có liên quan với nhau. Khái niệm thứ
nhất liên quan đến việc tính toán trên hệ Client/Server. Trong đó ứng dụng được
chia ra thành hai phần, phần của server và phần của client và được vận hành ở
hai nơi. Trong tính toán phân tán này cho phép truy cập trực tiếp dữ liệu trên đĩa
và xử lý các thông tin trên đĩa cho các client.
Khái niệm thứ hai là việc thực hiện các tác vụ xử lý phức tạp trên nhiều hệ
thống. Không gian nhớ và bộ xử lý của nhiều máy cùng hoạt động chia nhau tác
vụ xử lý. Máy trung tâm sẽ giám sát và quản lý các tiến trình này. Có trường hợp
thông qua Internet, hàng nghìn máy cùng xử lý một tác vụ.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 3
Tiểu luận môn: Hệ phân tán
1.4. Các Mô hình ứng dụng Phân tán
Có một số mô hình trong xây dựng ứng dụng phân tán, và cung cấp các
giao tiếp giữa các client, các server, các thành phần chương trình gồm:
- RPC (remote procedure call) Giao thức truyền thông theo phiên giữa các
máy được kết nối giữa các mạng. RPC thường được sử dụng trong các thao tác
cần thời gian thực, hướng kết nối.
- Messaging services Dịch vụ thông điệp còn gọi là dịch vụ MOM (message-

oriented middleware)-cung cấp một phương thức trao đổi thông tin giữa các ứng
dụng và các thành phần dùng hàng đợi và cách chuyển thông điệp theo từng
bước (store-and-forward). Cách này không phù hợp với truyền thông trong thời
gian thực.
- ORB (object-request broker) Một tác nhân kiểm soát truyền thông, cho
phép các đối tượng được phép truyền thông lên mạng. Ví dụ một đối tượng đang
chạy trên client nào đó nếu muốn gửi một thông điệp cho một đối tượng khác
đang chạy trên server, ta có thể gửi thông điệp từ giao diện ORB của client đến
cho giao diện ORB của server.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 4
Tiểu luận môn: Hệ phân tán
CHƯƠNG 2. MỘT SỐ PHƯƠNG PHÁP ĐỒNG BỘ HÓA
Ngày nay, công nghệ thông tin nhìn chung phát triển rất mạnh mẽ. Từ các
quốc gia có nền kinh tế kém phát triển đến các cường quốc kinh tế cũng đều có
nhu cầu rất lớn về xử lý thông tin. Nhu cầu thu thập thông tin có thể xuất phát từ
nhiều nguồn khác nhau và ở cách xa nhau. Vấn đề đặt ra là làm thế nào chúng ta
có thể xử lý thông tin ở cách xa nhau một cách nhanh nhất và hiệu quả nhất giữa
các hệ thống tin học, mà không xảy ra tranh chấp trong việc thu thập và xử lý
thông tin giữa các hệ thống tin học ở khắp nơi trên thế giới.
Để giải quyết vấn đề này thì việc thiết kế các chiến lược đồng bộ hóa các
tiến trình trong các hệ thống tin học là rất cần thiết và được quan tâm chú ý rất
nhiều. Tính cấp thiết về mặt nguyên lý và kỹ thuật của vấn đề đồng bộ hóa các
tiến trình này thể hiện ở hai nguyên lý cơ bản sau :
- Nhìn chung, các tiến trình kể cả các tiến trình xuất phát từ các ứng dụng
độc lập muốn truy cập vào các tài nguyên với số lượng vốn rất hạn chế hay truy
cập vào thông tin dùng chung cùng một lúc. Trường hợp này gọi là truy cập
tương tranh. Vì vậy, tương tranh là nguyên nhân chính của các xung đột giữa
các tiến trình muốn truy cập vào tài nguyên dùng chung.
- Các tiến trình của cùng một hệ ứng dụng hoạt động theo kiểu hợp lực để
giải quyết các bài toán đặt ra và cho kết quả nhanh chóng nhất. Điều này cho

phép tăng hiệu năng sử dụng thiết bị và hiệu quả hoạt động của chương trình. Vì
vậy hợp lực là nguyên nhân chính của sự tác động tương hỗ được lập trình giữa
các tiến trình nhằm cho phép chúng tham gia vào các hành động chung.
Sự tương tranh và hợp lực giữa các tiến trình đòi hỏi phải có trao đổi thông
tin qua lại với nhau. Trong hệ tin học phân tán, các thông tin cần trao đổi thông
qua các kênh thuộc hệ thống viễn thông.
Có nhiều phương pháp đồng bộ hóa tiến trình. Dưới đây sẽ giới thiệu một
số các phương pháp đồng bộ hóa các tiến trình để thực hiện việc truy xuất các
miền găng.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 5
Tiểu luận môn: Hệ phân tán
2.1. Đồng bộ hóa bằng phương pháp kiểm tra luân phiên
Đây là một giải pháp đề nghị cho hai tiến trình. Hai tiến trình này sử dụng
chung biến turn (phản ánh phiên tiến trình nào được vào miền găng), được khởi
động với giá trị 0. Nếu turn = 0, tiến trình A được vào miền găng. Nếu turn = 1,
tiến trình A đi vào một vòng lặp chờ đến khi turn nhận giá trị 0. Khi tiến trình A
rời khỏi miền găng, nó đặt giá trị turn về 1 để cho phép tiến trình B đi vào miền
găng.
(a) Cấu trúc tiến trình A
while (TRUE) {
while (turn != 0); // wait
critical-section ();
turn = 1;
Noncritical-section ();
}
(b) Cấu trúc tiến trình B
while (TRUE) {
while (turn != 1); // wait
critical-section ();
turn = 0;

Noncritical-section ();
}
Giải pháp này dựa trên việc thực hiện sự kiểm tra nghiêm nghặt đến lượt
tiến trình nào được vào miền găng. Do đó nó có thể ngăn chặn được tình trạng
hai tiến trình cùng vào miền găng, nhưng lại có thể vi phạm điều kiện thứ ba:
một tiến trình có thể bị ngăn chặn vào miền găng bởi một tiến trình khác không
ở trong miền găng. Giả sử tiến trình B ra khỏi miền găng rất nhanh chóng. Cả
hai tiến trình đều ở ngoài miền găng, và turn = 0. Tiến trình A vào miền găng và
ra khỏi nhanh chóng, đặt lại giá trị của turn là 1, rồi lại xử lý đoạn lệnh ngoài
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 6
Tiểu luận môn: Hệ phân tán
miền găng lần nữa. Sau đó, tiến trình A lại kết thúc nhanh chóng đoạn lệnh
ngoài miền găng của nó và muốn vào miền găng một lần nữa. Tuy nhiên lúc này
B vẫn còn mãi xử lý đoạn lệnh ngoài miền găng của mình, và turn lại mang giá
trị 1 ! Như vậy, giải pháp này không có giá trị khi có sự khác biệt lớn về tốc độ
thực hiện của hai tiến trình.
2.2. Đồng bộ hóa bằng giải pháp phần cứng thông qua chỉ thị TSL (Test-
and-Set-Lock)
Đây là một giải pháp đòi hỏi sự trợ giúp của cơ chế phần cứng. Nhiều máy
tính cung cấp một chỉ thị đặc biệt cho phép kiểm tra và cập nhật nội dung một
vùng nhớ trong một thao tác không thể phân chia, gọi là chỉ thị Test-and-Set
Lock (TSL) và được định nghĩa như sau:
Test-and-Setlock(boolean target)
{
Test-and-Setlock = target;
target = TRUE;
}
Nếu có hai chỉ thị TSL xử lý đồng thời (trên hai bộ xử lý khác nhau), chúng
sẽ được xử lý tuần tự . Có thể cài đặt giải pháp truy xuất độc quyền với TSL
bằng cách sử dụng thêm một biến lock, được khởi gán là FALSE. Tiến trình

phải kiểm tra giá trị của biến lock trước khi vào miền găng, nếu lock = FALSE,
tiến trình có thể vào miền găng.
while (TRUE) {
while (Test-and-Setlock(lock));
critical-section ();
lock = FALSE;
Noncritical-section ();
}
Cũng giống như các giải pháp phần cứng khác, chỉ thị TSL giảm nhẹ công
việc lập trình để giải quyết vấn đề, nhưng lại không dễ dàng để cài đặt chỉ thị
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 7
Tiểu luận môn: Hệ phân tán
TSL sao cho được xử lý một cách không thể phân chia, nhất là trên máy với cấu
hình nhiều bộ xử lý.
Tất cả các giải pháp trên đây đều phải thực hiện một vòng lặp để kiểm tra
liệu nó có được phép vào miền găng, nếu điều kiện chưa cho phép, tiến trình
phải chờ tiếp tục trong vòng lặp kiểm tra này. Các giải pháp buộc tiến trình phải
liên tục kiểm tra điều kiện để phát hiện thời điểm thích hợp được vào miền găng
như thế được gọi các giải pháp « busy waiting ». Lưu ý rằng việc kiểm tra như
thế tiêu thụ rất nhiều thời gian sử dụng CPU, do vậy tiến trình đang chờ vẫn
chiếm dụng CPU.
2.3. Đồng bộ hóa bằng phương pháp trao đổi thông điệp
Phương pháp này dựa trên cơ sở trao đổi thông điệp với hai primitive Gui
và Nhan để thực hiện sự đồng bộ hóa:
+ Gui(destination, message): gởi một thông điệp đến một tiến trình hay
gởi vào hộp thư.
+ Nhan(source,message): nhận một thông điệp từ một tiến trình hay từ bất
kỳ một tiến trình nào, tiến trình gọi sẽ chờ nếu không có thông điệp nào để nhận.
Có nhiều cách thức để thực hiện việc truy xuất độc quyền bằng cơ chế trao
đổi thông điệp. Đây là một mô hình đơn giản: một tiến trình kiểm soát việc sử

dụng tài nguyên và nhiều tiến trình khác yêu cầu tài nguyên này. Tiến trình có
yêu cầu tài nguyên sẽ gởi một thông điệp đến tiến trình kiểm soát và sau đó
chuyển sang trạng thái blocked cho đến khi nhận được một thông điệp chấp
nhận cho truy xuất từ tiến trình kiểm soát tài nguyên. Khi sử dụng xong tài
nguyên , tiến trình gởi một thông điệp khác đến tiến trình kiểm soát để báo kết
thúc truy xuất. Về phần tiến trình kiểm soát , khi nhận được thông điệp yêu cầu
tài nguyên, nó sẽ chờ đến khi tài nguyên sẵn sàng để cấp phát thì gởi một thông
điệp đến tiến trình đang bị khóa trên tài nguyên đó để đánh thức tiến trình này.
while (TRUE) {
Gui(process controler, request message);
Nhan(process controler, accept message);
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 8
Tiểu luận môn: Hệ phân tán
critical-section ();
Gui(process controler, end message);
Noncritical-section ();
}
Trong những hệ thống phân tán mà mỗi bộ xử lý sở hữu một bộ nhớ riêng
biệt và liên lạc thông qua mạng, cơ chế trao đổi thông điệp tỏ ra hữu hiệu và
được dùng nhiều để giải quyết bài toán đồng bộ hóa.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 9
Tiểu luận môn: Hệ phân tán
CHƯƠNG 3. ĐỒNG BỘ HÓA BẰNG PHƯƠNG PHÁP TRẬT TỰ
Trong mô hình đồng bộ hoá bằng phương pháp trật tự. Có 2 phương pháp
mà ta đặc biệt chú ý quan tâm và nghiên cứu kỹ chúng là:
+ Đồng bộ hóa bằng phương pháp trật tự từng phần
+ Đồng bộ hóa bằng phương pháp trật tự tổng quát chặt chẽ
3.1. Đồng bộ hóa bằng phương pháp trật tự từng phần
Trong các hệ thống tin học tập trung vấn đề đồng bộ hóa được giải quyết
thông qua cơ chế loại trừ tương hỗ. Cơ chế này cho phép xác lập trật tự hoàn

toàn các sự kiện. Trong thực tiễn, có một số hệ thống vấn đề về đồng bộ hóa chỉ
đòi hỏi trật tự từng phần. Chính vì vậy trật tự hóa từng phần giữa các sự kiện mà
các tiến trình của nó cần phải đồng bộ là vấn đề cần quan tâm giải quyết.
Trong các hệ thống phân tán, việc đồng bộ hóa chỉ đặt ra duy nhất vấn đề
thiết lập một trật tự giữa các sự kiện. Giữa các trạm khác nhau, trật tự đó chỉ thể
hiện được thông qua việc trao đổi các thông điệp với nhau.
Giả sử rằng ta có thể xác định một trật tự giữa các sự kiện của hệ phân tán
nhờ vào quan hệ được ký hiệu là  và gọi là “có trước”. Quan hệ này tối thiểu
phải thỏa mãn được các ràng buộc thể hiện qua hai cách:
+ Nếu A và B là hai sự kiện của cùng một trạm và nếu A được thực hiện
trước B thì theo trật tự cục bộ của trạm ta có: A  B.
+ Nếu A là phát thông điệp bởi một trạm nào đó và nếu B là thu của thông
điệp này thì ta có A B.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 10
Tiểu luận môn: Hệ phân tán
Trật tự từng phần của các sự kiện
A1A2A3A4A5
B1B2B3B4B5
Trao đổi thông điệp
A2B2 và B3A4
Chuyển qua
A1A2B2B3B4 B5
B1B2B3A4A5
A1A2B2B3A4A5
Xét mô hình quen thuộc trong phần nguyên lý hệ điều hành là người sản
xuất-người tiêu thụ, trong đó khả năng tiêu thụ là nguyên nhân chính hạn chế số
lượng hàng hóa sản xuất ra để nó không vượt quá số lượng tiêu thụ một giá trị
lớn hơn N. Người sản xuất P và người tiêu thụ C là hai người nằm trên hai trạm
cách xa nhau.
Giả sử rằng NP là số lượng sản xuất ra và NC là số lượng tiêu thụ tại thời

điểm khởi sự. C chỉ tiêu thụ được một sản phẩm, nếu sản xuất sản phẩm đó đã
diễn ra, có nghĩa là, nếu
NP – NC > 0
Tương tự, P chỉ sản xuất một thông tin, nếu
NP – NC < N
Hai quan hệ này thể hiện các điều kiện của việc đồng bộ hóa và có thể mô
tả trong hình sau:
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 11
t
A1
A2
A3
A4
A5
B1
B2
B3
B4
B5
Ví dụ: Mô tả trật tự từng phần
P
i+N
P
i+N+1
P
1
C
1
P
2

C
2
P
i
C
i
C
i+1
P
i
: Sản xuất thứ i
C
i
: Tiêu thụ thứ i
Hình 2: Quan hệ có trước trong mô hình
người sản xuất- người tiêu thụ
Tiểu luận môn: Hệ phân tán
Trong hệ thống tin học phân tán, người ta có thể vận dụng hợp lực này theo
kiểu như sau:
1. Ta đưa vào
STT Diễn giải
1 Trên trạm P một biến NP thể hiện số lượng chính xác sản
xuất đã có.
2 Trên trạm C một biến NC thể hiện số lượng chính xác tiêu
thụ đã thực hiện.
2. Ta đưa vào
STT Diễn giải
1 Trên trạm P một biến NC’ ảnh của NC mà P gia tăng mỗi
một lần nó nhận được thông điệp từ C báo cho nó biết là
tiêu thụ mới đã diễn ra.

2 Trên trạm C một biến NP’ ảnh của NP mà C gia tăng mỗi
một lần nó nhận thông điệp từ P báo cho nó biết một sản
xuất mới đã diễn ra.
Ta sẽ chứng minh rằng một sự đồng bộ hóa chính xác được đảm bảo bằng
việc xác nhận trên mỗi trạm các điều kiện sau đây:
1/ Trên trạm sản xuất:
NP’ – NC > 0
2/ Trên trạm tiêu thụ:
NP – NC’ < N
Ta có thể viết:
NP = NP’ + np, với np > 0
trong đó, np số lượng thông tin đã sản xuất bởi P mà C không biết,
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 12
Tiểu luận môn: Hệ phân tán
NC = NC’ + nc, với nc > 0
trong đó, nc số lượng thông tin đã tiêu thụ bởi C mà P không biết.
Ta có thể khái quát hóa phương pháp này cho điều kiện đồng bộ hóa bằng công
thức:
∑
C
i
X
i
> K (theo i)
trong đó, C
i
và K là các hằng số. Ta hoàn toàn có khả năng và điều kiện mạnh
hơn bằng cách thay thế tất cả các X
i
mà hệ số của nó là đại lượng dương bằng

các ảnh của nó X’
i
, nếu và chỉ nếu các X
i
là các biến không lùi.
Vì nguyên nhân xa cách giữa người sản xuất và người tiêu thụ mà trật tự
tổng quát này không cần thiết và chỉ cần sủ dụng để đồng bộ hóa các bản sao các
biến trạng thái gần đúng là đủ.
Trong hệ thống người sản xuất - người tiêu thụ, nếu N = 1, thì có sự liên
kết chặt chẽ giữa hai tiến trình cho phép xác định một trật tự chặt chẽ giữa các
sự kiện.
Cơ chế đồng bộ ở đây là dùng các công tơ sự kiện phù hợp với từng vấn đề
đặt ra. Mỗi một công tơ, biến nguyên không lùi, được kết hợp với một nhóm đặc
biệt các sự kiện.
Trên một công tơ sự kiện nào đó có phối hợp với nhóm E nào đó, được xác
định bởi ba hàm nguyên thủy:
+ Tang_len(E) : Tăng nội dung công tơ lên 1 đơn vị, cũng có nghĩa là
một sự kiện nhóm E đến.
+ Truy_van(E) : Cung cấp giá trị hiện hành của công tơ phối hợp với E
+ Cho(E,n) : Treo tiến trình gọi chừng nào giá trị công tơ còn nhỏ
hơn n.
Mỗi công tơ được khởi động ngay khi thành lập nó.
Với bài toán người sản xuất - người tiêu thụ, cần định nghĩa:
• Hai công tơ sự kiện NP’ và NC’, được khởi động bằng giá trị 0.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 13
Tiểu luận môn: Hệ phân tán
• Hai biến nguyên NP và NC, khởi sự là 0, là cục bộ đối với tiến trình người
sản xuất P và người tiêu thụ C.
Các tiến trình có thể viết như sau:
Người sản xuất

Vòng lặp
cho(NC’, NP-N+1)
{Chuyển khi NP - NC’ < N}
san_xuat
tang(NP’)
NP:=NP+1
Kết thúc vòng lặp
Người tiêu thụ
Vòng lặp
cho(NP’, NC+1)
{Chuyển khi NP’ - NC > 0}
tieu_thu
tang(NC’)
NC:=NC+1
Kết thúc vòng lặp
Việc triển khai các công tơ sự kiện có thể được thực hiện bằng cách giao
cho bộ xử lý duy nhất đảm trách việc điều khiển toàn bộ công việc này.
3.2. Đồng bộ hóa bằng phương pháp trật tự tổng quát chặt chẽ
Phương pháp này được áp dụng trong một số trường hợp cần phải sắp xếp
toàn bộ theo kiểu chặt chẽ các sự kiện của hệ. Nguyên lý của phương pháp này
được khái quát như sau:
Một tiến trình nào đó gửi thông điệp để yêu cầu sử dụng tài nguyên, một
tiến trình sử dụng xong tài nguyên nào đó truyền một thông tin giải phóng khi
nó ngừng chiếm dụng.
Trong các hệ phân tán, chương trình cung cấp nằm trên một trạm và các
tiến trình đề nghị lại ở trên các trạm khác, các yêu cầu và khuyến nghị giải
phóng được truyền cho các chương trình cung cấp thông qua hình thức thông
điệp, chuyển theo các kênh của hệ thống viễn thông. Chính vì vậy nhu cầu sắp
xếp các yêu cầu này theo một trật tự nhất định nào đó luôn luôn được đặt ra.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 14

Tiểu luận môn: Hệ phân tán
Nếu chỉ có một thông điệp đến chương trình cung cấp thì trật tự đến thể
hiện một trật tự chặt chẽ. Ngược lại nếu có nhiều thông điệp đến cùng một lúc
thì việc sắp xếp chúng phải theo kiểu loại trừ trương hỗ trong hàng đợi cục bộ
của trạm có chứa chương trình cung cấp. Điều đó cũng cho phép ta có được một
trật tự chặt chẽ.
Trật tự có được tại trạm cung cấp có thể không giống như trật tự phát, nếu
thời gian truyền không được cố định. Trường hợp này khá phổ biến trong mạng
máy tính. Nhưng nếu ta muốn xử lý các thông điệp theo trình tự không tính tới
thời gian truyền, thì cần phải tính đến một trật tự tổng quát của các lần truyền
thông điệp từ các trạm khác nhau. Những cơ chế thể hiện chức năng này được
mô tả sau đây:
Giải thuật được trình bày ở đây là giải thuật Lamport nhằm cho phép ghi lại
các sự kiện của hệ tin học phân tán.
Mỗi trạm S đều có trang bị công tơ với các giá trị nguyên gọi là H
s
. Đó
chính là đồng hồ logic tăng lên giữa hai sự kiện kế tiếp. Trạm E phát thông điệp
ghi dấu e của mình dựa trên giá trị hiện hành của H
e
. Khi nhận được thông điệp,
trạm nhận R cập nhật đồng hồ H
r
riêng của mình bằng giải thuật sau đây:
Nếu H
r
thì
H
r
:= e+1

Kết thúc nếu
Sự kiện “nhận thông điệp” lúc này được ghi nhận bằng giá trị của H
r
.
Thuật toán này đảm bảo rằng thời gian nhận thông điệp là sau thời gian phát nó
đi. Thời gian này cho phép xác định một quan hệ trật tự toàn bộ mà ta đã ký hiệu
 và cho phép kiểm tra được các điều kiện trong C
1
và C
2
.
Một sự kiện a sinh ra trong trạm i và được đánh dấu bởi đồng hồ cục bộ gọi
là H
i
(a). Nếu a và b đều là hai sự kiện trên hai trạm i và j, ta luôn luôn có quan
hệ xác định như sau:
a  b ⇔ H
i
(a) < H
i
(b)
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 15
Tiểu luận môn: Hệ phân tán
Đó là trật tự không chặt chẽ do hai sự kiện trên hai trạm khác nhau có thể
đến cùng một thời điểm giống nhau. Ta có thể mở rộng quan hệ  thành quan
hệ trật tự chặt chẽ ⇒ bằng cách kết hợp một số khác cố định cho mỗi trạm và
bằng cách đánh dấu thời gian cho mỗi sự kiện a của trạm i bằng cặp (H
i
(a),i).
Theo định nghĩa ta có:

a ⇒ b ⇒ (H
i
(a) < H
i
(b))
hay
(H
i
(a) = H
i
(b) và i<j)
3.3. Kết Luận
Trong hệ thống tin học phân tán các thành phần trạng thái của hệ được biết
một cách không chắc chắn, vì thời gian truyền thông tin trên đường truyền
không cố định, thời gian trễ trong quá trình truyền giữa các trạm cũng khác
nhau, nên độ rủi ro về mất thông tin trên hệ phân tán khá cao. Vì vậy việc thiết
kế một hệ thống phân tán hiệu quả là một vấn đề khó, cần phải quan tâm đến
nhiều khía cạnh khác nhau. Trong số đó vấn đề về đồng bộ hóa giữa các tiến
trình trong hệ là hết sức quan trọng và cần đặc biệt chú ý đến. Nếu xây dựng giải
pháp đồng bộ hóa giữa các tiến trình tốt thì việc trao đổi dữ liệu giữa các trạm
trong hệ cũng thông suốt và vấn đề treo hệ thống là ít xảy ra. Đảm bảo thông
suốt về mặt dữ liệu và đáp ứng thời gian thực về mặt truyền thông.
Có nhiều giải pháp đồng bộ hóa, trong đó đồng bộ hóa bằng phương pháp
trật tự được ứng dụng nhiều trong các hệ tin học phân tán, được triển khai trên
nền tảng đánh số sự kiện thông qua các công tơ sự kiện, giúp quản lý dễ dàng
việc truy xuất tài nguyên dùng chung.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 16
Tiểu luận môn: Hệ phân tán
PHẦN B. BÀI TẬP
1.1. Phát biểu bài toán

Một nhóm tình báo được tổ chức phân cấp theo cấu trúc hình cây: mỗi
thành viên chỉ có thể giao tiếp với cấp trên và các cấp dưới trực tiếp theo
phương thức truyền thông báo. Lãnh đạo cao nhất của nhóm là L, tương ứng
với nút gốc của cây. Các thành viên không có một cấp dưới nào được gọi là
những lính chiến (tương ứng với các nút lá). Tất cả những thành viên khác được
gọi là những sĩ quan (tương ứng với các nút trong). Giả sử tổng số thành viên
của nhóm tình báo là n > 1.
Giải thuật:
Một giải thuật phân tán không đồng bộ khởi đầu từ L cho phép L biết
được số lượng sĩ quan và số lượng lính chiến của nhóm. Một giải thuật phân tán
khởi đầu từ nút gốc có nghĩa là nút gốc thực hiện đầu tiên, các nút khác chỉ bắt
đầu thực hiện sau khi nhận được thông báo từ đâu đó gửi đến.
Mỗi thành viên i bất kỳ trong nhóm sẽ lưu trữ hai biến thông tin:
officer
i
= 0 và soldier
i
= 0 tương ứng với số sĩ quan và số lính chiến dưới
quyền của thành viên thứ i. Các giá trị này đều được khởi tạo = 0
Bước 0: L sẽ gửi một thông báo REQUEST tới tất cả các cấp dưới trực
tiếp của L.
Bước 1: Một thành viên bất kỳ i khi nhận được thông báo REQUEST:
- Nếu thành viên đó có các cấp dưới trực tiếp:
o officer
i
= 1
o soldier
i
= 0
o C huyển tiếp thông báo đó cho các cấp dưới trực tiếp của nó .

- Nếu thành viên đó không có cấp dưới trực tiếp:
o officer
i
= officer
i
+ 1
o soldier
i
= 0
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 17
Tiểu luận môn: Hệ phân tán
o G ửi ngược trở lên cho cấp trên trực tiếp của nó (chính là
thành viên vừa gửi thông báo) một thông báo RESPONE(0,1)
tương ứng officer
i
=0 và soldier
i
=1
o Kết thúc
Bước 2: Một thành viên i bất kỳ (bao gồm cả L) khi nhận được thông báo
RESPONE(x,y) từ các thành viên cấp dưới trực tiếp của nó:
- T iến hành tính toán:
o officer
i
= officer
i
+ x
o soldier
i
= soldier

i
+ y
- Chờ cho tới khi nhận được đủ thông báo RESPONE từ các t hành
viên cấp dưới trực tiếp của nó (có thể bằng cách so sánh với số lượng
các thành viên cấp dưới hoặc đặt một giá trị thời gian time out nào đó)
- Sau khi tập hợp đủ các thông báo RESPONE từ các thành viên cấp
dưới trực tiếp, thành viên i sẽ
o Nếu có cấp trên trực tiếp:
 Gửi ngược trở lên cho cấp trên trực tiếp của nó thông
báo RESPONE(officer
i
, soldier
i
) chứa số sĩ quan và lính
chiến mà thành viên thứ i đã tổng hợp được.
o Kết thúc
Bước 1 và bước 2 được lặp lại cho tới khi các thành viên (bao gồm cả L) đều
vào trạng thái kết thúc. Khi đó các giá trị officer
L
và soldier
L
tại L chính là các
thông tin mà L cần biết.
1.2. Kết luận quan trọng về hệ phân tán
Hệ phân tán là lĩnh vực kiến thức tiên tiến nhằm trợ giúp cho các chuyên
viên công nghệ thông tin trong công tác nghiên cứu, phân tích và thiết kế các hệ
thống tin học
Hệ tin học phân tán là hệ thống xử lý thông tin bao gồm nhiều bộ xử lý
(hay bộ vi xử lý) phân bổ tại các vị trí khác nhau và đựợc nối ghép với nhau
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 18

Tiểu luận môn: Hệ phân tán
thông qua các phương tiện truyền tin và được điều khiển bởi một hệ điều hành
duy nhất.
Thành phần của hệ phân tán bao gồm các hệ thống cục bộ (mạng hay máy
đơn), trong đó một (hay nhiều) hệ thống phát các yêu cầu thông tin còn các hệ
thống khác trả lời các yêu cầu có liên quan đến phần dữ liệu của mình
Thời hạn truyền thông tin trong hệ không giống nhau, các thông điệp có thể
bị mất trong quá trình chuyển tải, các thông điệp có thể được truyền kép và hệ
thống có thể rơi vào sự cố bất cứ lúc nào.
Một (hay nhiều) máy tính cấu thành hệ phân tán có thể bị sự cố và hoạt
động của toàn hệ trở nên bị đình trệ hoặc kém hiệu quả.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 19
Tiểu luận môn: Hệ phân tán
TÀI LIỆU THAM KHẢO

[1] Hệ tin học 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, 2002.
[2] Các tài liệu tham khảo trên internet.
[3] Distributed Systems, George Coulouris, Jean Dollimore - Tim Kindberg,
pearson education, 2005.
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 20
Tiểu luận môn: Hệ phân tán
MỤC LỤC
PHẦN A. CƠ SỞ LÝ THUYẾT 2
CHƯƠNG 1. GIỚI THIỆU VỀ HỆ TIN HỌC PHÂN TÁN 2
1.1. Hệ Phân tán 2
1.2. Các điểm mạnh trong hệ tin học phân tán 2
1.3. Xử lý Phân tán 3
1.4. Các Mô hình ứng dụng Phân tán 4
CHƯƠNG 2. MỘT SỐ PHƯƠNG PHÁP ĐỒNG BỘ HÓA 5

2.1. Đồng bộ hóa bằng phương pháp kiểm tra luân phiên 6
2.2. Đồng bộ hóa bằng giải pháp phần cứng thông qua chỉ thị TSL (Test-and-Set-Lock). 7
2.3. Đồng bộ hóa bằng phương pháp trao đổi thông điệp 8
CHƯƠNG 3. ĐỒNG BỘ HÓA BẰNG PHƯƠNG PHÁP TRẬT TỰ 10
3.1. Đồng bộ hóa bằng phương pháp trật tự từng phần 10
3.2. Đồng bộ hóa bằng phương pháp trật tự tổng quát chặt chẽ 14
3.3. Kết Luận 16
PHẦN B. BÀI TẬP 17
1.1. Phát biểu bài toán 17
1.2. Kết luận quan trọng về hệ phân tán 18
TÀI LIỆU THAM KHẢO 20
Học viên: Nguyễn Thị Hạnh – KHMT 2008 – 2011 Trang 21