Tiểu luận Hệ Tin Học Phân Tán
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 giới hạn của một báo cáo tiểu luận kết thúc môn học, nội dung của bản báo
cáo sẽ được trình bày theo chủ đề trong phần “ Đề tài tiểu luận và bài tập môn Hệ Tin
Học Phân Tán” của PGS TS. Lê Văn Sơn, bao gồm :
Phần I lí thuyết : MÔ HÌNH CLIENT/SERVER .
Phần II chương trình: VIẾT CHƯƠNG TRÌNH MÔ PHỎNG
QUÁ TRÌNH ĐỒNG BỘ CỦA BÃI ĐẬU XE Ô TÔ CÓ n CỔNG ( n ≥ 2).
Được sự giúp đỡ tận tình của Thầy giáo hướng dẫn và các bạn đồng nghiệp, tôi đã
hoàn thành được những nhiệm vụ cơ bản đề ra. Tuy nhiên, với thời gian và kiến thức có
hạn, bản báo cáo này chắn chắn còn nhiều khiếm khuyết, tôi rất mong nhận được góp ý
chân thành của Thầy giáo và các bạn đồng nghiệp.
Nguyễn Thị Mai – Khoa học máy tính K10
- 1 -
Tiểu luận Hệ Tin Học Phân Tán
PHẦN I LÝ THUYẾT

thức đón nhận dữ liệu từ người sử dụng. Để tiến hành thực hiện giao diện này thuộc về
phần Logic trình bày.
Logic trình bày ( Presentation Logic ) : Thành phần này là cầu nối giữa người dùng
và ứng dụng như cung cấp chức năng của ứng dụng cho người dùng và nhận những lệnh
Nguyễn Thị Mai – Khoa học máy tính K10
- 2 -
Tiểu luận Hệ Tin Học Phân Tán
từ người dùng cho ứng dụng. Vì thành phần này đảm đương trách nhiệm hiển thị, định
dạng các thành phần giao tiếp với người dùng như định dạng màn hình, quản lí các hộp
thoại, các cửa sổ, đọc ghi các thông tin trên màn hình, điều khiển bàn phím, chuột,
hoặc các cơ chế trợ giúp theo ngữ cảnh, kiểm tra quyền truy cập cho nên thành phần này
được thiết kế sao cho càng thân thiện với người dùng càng tốt.
Logic ứng dụng ( Application Logic ) : Thành phần này đóng vai trò quan trọng, là
phần lõi của một chương trình. Nó đảm đương việc thực thi ứng dụng, cung cấp tất cả các
chức năng có thể có của chương trình cho thành phần logic trình bày ở trên như đáp ứng
các yêu cầu từ người dùng, quản lí các cơ sở dữ liệu, Thông thường nó gồm hai phần :
Thao tác dữ liệu ( Data Processing logic ) và Xử lí dữ liệu (Database Processing).

Mô hình Client/Server
Như vậy, một hệ thống tổ chức theo mô hình Client/Server gồm ba thành phần :
Client, Server và mạng. Mỗi thành phần đều có yêu cầu về phần cứng và phần mềm.
I.1.1. CLIENT :
Yêu cầu tối thiểu của Client là có khả năng phát ra yêu cầu tới Server và hiển thị kết
quả trả về từ Server. Nó có thể là các trạm làm việc, máy tính để bàn ( Desktop) hoặc
minicomputer. Client có thể chạy bất cứ hệ điều hành nào cũng như phần mềm nào,
không phụ thuộc vào hệ điều hành mạng. Dĩ nhiên ta đã tính tới khả năng giao tiếp với
Nguyễn Thị Mai – Khoa học máy tính K10
- 3 -
Mạng
Clien

và các cơ chế toàn vẹn dữ liệu.
Compute Server : Tương tác dữ liệu, Server này hoạt động dựa trên Compute Server
và Data Server. Khi nó yêu cầu thao tác dữ liệu, Compute Server chuyển giao tác vụ và
Data Server xử lí dữ liệu.
Communication Server : Đảm đương chức năng cầu nối với một Server khác ở xa
hoặc mạng khác.
I.1.3. MẠNG:
Mạng là yếu tố quan trọng của mô hình Client/Server. Trước hết nó là nền tảng trên
đó ta triển khai mô hình Mạng đảm bảo cho việc giao tiếp giữa Client và Server thông
Nguyễn Thị Mai – Khoa học máy tính K10
- 4 -
Tiểu luận Hệ Tin Học Phân Tán
qua các hoạt động truyền thông. Mạng cũng là môi trường đảm bảo sự phân tán chức
năng đến Client.
Phần cứng yêu cầu của mạng là mạng máy tính thực sự, cung cấp khả năng giao tiếp
với nhau giữa các thành phần trong mạng. Các thành phần cụ thể như cáp, card mạng, các
thiết bị liên kết Client với Server ( router, gateway, bridge ).
Phần mềm mạng đảm bảo duy trì các hoạt động truyền thông trên mạng. Hệ điều
hành mạng chịu trách nhiệm quản lí các vấn đề liên quan đến việc truy xuất trên mạng
của Server. Mỗi một hệ điều hành mạng có các qui tắc giao tiếp khác nhau giữa Client và
Server. Các qui tắc này được gọi là giao thức.
I.1.3.1 GIAO THỨC
Để máy tính có thể liên lạc với nhau qua mạng, chúng phải sử dụng cùng 1 ngôn ngữ
hay còn gọi là giao thức (Protocol). Giao thức là một hệ luật chuẩn cho phép các máy
tính trong mạng liên lạc với nhau
- TCP/IP là viết tắt của Transmission Control Protocol (Giao thức Điều Khiển
Truyền Thông) / Internet Protocol (Giao thức Internet).
- TCP/IP không chỉ gồm 2 giao thức mà thực tế nó là tập hợp của nhiều giao
thức. Chúng ta gọi đó là 1 Hệ Giao Thức hay Bộ Giao Thức (Suite Of Protocols).
- Để cho các máy tính trao đổi dữ liệu với nhau TCP/IP sử dụng mô hình

trường hợp truyền dữ liệu bị hỏng.
+ IGMP (Internet Group Management Protocol): Có chức năng điều khiển truyền đa
hướng (Multicast)
I 1.3.1.3 Tầng Giao Vận (Transport Layer):
Có trách nhiệm thiết lập phiên truyền thông giữa các máy tính và quy định cách
truyền dữ liệu. 2 giao thức chính trong tầng này gồm:
+ UDP (User Datagram Protocol): Còn gọi là Giao Thức Gói Người Dùng. UDP
cung cấp các kênh truyền thông phi kết nối nên nó không đảm bảo truyền dữ liệu 1 cách
tin cậy. Các ứng dụng dùng UDP thường chỉ truyền những gói có kích thước nhỏ, độ tin
cậy dữ liệu phụ thuộc vào từng ứng dụng
+ TCP (Transmission Control Protocol): Ngược lại với UDP, TCP cung cấp các kênh
truyền thông hướng kết nối và đảm bảo truyền dữ liệu 1 cách tin cậy. TCP thường truyền
các gói tin có kích thước lớn và yêu cầu phía nhận xác nhận về các gói tin đã nhận.
I 1.3.1.4 Tầng Ứng Dụng (Application Layer):
Gồm nhiều giao thức cung cấp cho các ứng dụng người dùng. Được sử dụng để định
dạng và trao đổi thông tin người dùng. 1 số giao thức thông dụng trong tầng này là:
+ DHCP (Dynamic Host Configuration Protocol): Giao Thức Cấu Hình Trạm Động
+ DNS (Domain Name System): Hệ Thống Tên Miền
+ SNMP (Simple Network Management Protocol): Giao Thức Quản Lý Mạng Đơn
Giản
+ FTP (File Transfer Protocol): Giao Thức Truyền Tập Tin
+ TFTP (Trivial File Transfer Protocol): Giao Thức Truyền Tập Tin Bình Thường
+ SMTP (Simple Mail Transfer Protocol): Giao Thức Truyền Thư Đơn Giản
+ TELNET
Bảng sau mô tả khái quát về Bộ giao thức TCP/IP
Nguyễn Thị Mai – Khoa học máy tính K10
- 6 -
Tiểu luận Hệ Tin Học Phân Tán
I.2. PHÂN LOẠI ỨNG DỤNG CLIENT/SERVER
Đối với các ứng dụng Client/Server tuỳ thuộc vào yêu cầu của nó mà giao nhiệm vụ

Như vậy chi phí cũng giảm đáng kể.
Client/Server mở ra khả năng sử dụng tài nguyên dùng chung trên mạng như phần
mềm, máy in đĩa cứng, Các tài nguyên này trước đây chỉ nằm trên một hệ thống do đó
chỉ được khai thác trực tiếp với Host đó. Nay nó được phân phát cho các nhiệm vụ, các
trạm làm việc cũng như các Server khác trong cùng hệ thống.
Client/Server cho phép phối hợp quản lý tập trung và không tập trung. Các chức
năng có thể được phân tán trên các nút khác nhau, do đó làm tăng tính an toàn của hệ
thống cũng như khả năng quá tải tập trung trên một Server.
Client/Server cho phép dùng giao diện đồ hoạ trên các trạm giúp cho việc sử dụng dễ
dàng hơn, các ứng dụng được phát triển nhanh, dễ được người dùng chấp nhận.
Client/Server cũng chú ý và khuyến khích các hệ thống mở. Client và Server có thể
chạy trên các cấu hình cứng và mềm khác nhau, giải phóng sự phụ thuộc của người sử
dụng vào một cấu hình cụ thể, một nhà cung cấp cụ thể.
I.3.2. NHƯỢC ĐIỂM
Bên cạnh những ưu điểm trên, Client/Server cũng thể hiện những nhược điểm của
chính nó :
Khi ứng dụng chủ yếu đặt ở Server, Server có nhiều nguy cơ tắc nghẽn, xung đột. Do
đó đòi hỏi các chiến lược phân chia tài nguyên, phân phối nhiệm vụ cũng như đáp ứng
các nhu cầu một cách có hiệu quả.
Đối với các ứng dụng phân tán, khi phân chia nhiệm vụ phức tạp hơn nhiều so với
các ứng dụng không phân tán.
Môi trường có nhiều người sử dụng đòi hỏi các cơ chế bảo mật dữ liệu. Cần phải có
hiểu biết và phương pháp kỹ thuật mới có thể giải quyết vấn đề một cách tối ưu.
I.4 MỘT SỐ ỨNG DỤNG: Kiến trúc Client-Server của BOINC
Công nghệ Client-Server đề cập đến mô hình client-server mà Boinc hoạt động dựa
trên nó. Framework của Boinc bao gồm 2 lớp hoạt động theo kiển trúc Client-Server.
Một khi phần mềm Boinc server được cài đặt trên 1 máy, nó sẽ bắt đầu gửi các task đến
Nguyễn Thị Mai – Khoa học máy tính K10
- 8 -
Tiểu luận Hệ Tin Học Phân Tán

được gọi là workunit. Một kết quả (result) là 1 thể hiện (instance) của workunit, thậm chí
ngay cả khi workunit chưa hoàn thành. Một project không nhất thiết phải tạo ra các result
mà chính server đã tạo ra các result 1 cách tự động tương ứng với các workunit.
Một chương trình CGI lập lịch xử lý các yêu cầu từ phía client, nhận các workunit đã
hoàn thành và gửi đi các công việc mới. (cgi)
Một chương trình CGI xử lý việc upload file. (file_upload_handler)
Bộ lập lịch không lấy các result (workunit chưa hoàn thành – Thực chất các result là
đã được tạo ngay từ lần đầu tiên các workunit được tạo ra và được lưu sẵn trong CSDL.
Tuy nhiên chỉ khi nào workunit tương ứng xử lý xong, gửi lên server thì result tương ứng
đó mới được đánh dấu là đã hoàn thành. Do đó khái niệm result ở đây có thể coi là
workunit chưa hoàn thành) sẵn có một cách trực tiếp từ CSDL. Thay vào đó, có 1 chương
trình ngầm feeder sẽ nạp các task(thực chất 1 workunit được chia thành các task, mỗi task
sẽ có tương ứng 1 result tương ứng để « đặt chỗ » sẵn trong CSDL, task nào hoàn thành,
upload lên server thì result tương ứng sẽ được đánh dấu là hoàn thành) từ CSDL và lưu
chúng trong các khối nhớ để cho bộ lập lịch đọc ra. Feeder sẽ định kì làm rỗng các «khe
» trong khối nhớ sau khi các task được gửi đến client.
Nguyễn Thị Mai – Khoa học máy tính K10
- 9 -
Tiểu luận Hệ Tin Học Phân Tán
Khi tất cả các result của 1 workunit đã thực hiện xong và được gửi trả về cho server,
thành phần validator sẽ so sánh chúng. Thành phần validator có thể có các thành phần
code do người phát triển project đặt ra để thực hiện sự so sánh mờ (so sánh tương đồi, ví
dụ như trừ cho nhau hay dùng 1 hàm đánh giá ) giữa các kết quả, hoặc nó có thể chỉ là so
sánh các bit. Nếu các kết quả khớp với nhau, workunit sẽ được đánh dấu là hợp lệ, người
tình nguyện sẽ được « gán » credit và 1 kết quả (result) thích hợp sẽ được chọn cho
workunit đó.
Tiếp đó, deamon assimilator (đồng hoá, xử lý kết quả) xử lý các result hợp lệ, sử
dụng các code chuyên dụng của dự án. Ví dụ : một vài dự án có thể phân tích các file và
lưu trữ thông tin vào trong CSDL, mặt khác có thể đơn giản chỉ là copy file sang 1 chỗ
khác. Một bộ đồng hoá cũng có thể sinh ra các workunit mới dựa trên các kết quả hay dữ

nắm được trạng thái hiện hành của bãi.
* Tình huống thứ hai :
Nguyễn Thị Mai – Khoa học máy tính K10
- 11 -
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
B
V
B
V

VT
Tiểu luận Hệ Tin Học Phân Tán
Nếu ta có bãi để xe với nhiều cổng vào và tại mỗi cổng vào có một người bảo vệ thì
mỗi người bảo vệ chỉ có thể được biết trạng thái với độ trễ nhất định và điều đó dẫn đến
tính huống thứ hai. Đó là tình huống với nhiều trung tâm ra quyết định như trong hình vẽ
III.1 ở trên.
Trên thực tế, một người bảo vệ nào đó tin rằng không còn chỗ trống nữa, trong khi
một người bảo vệ khác lại vừa mới cho ra khỏi bãi một số xe mà anh ta chưa kịp báo cho
các người bảo vệ khác. Cũng có thể diễn ra trường hợp là cùng một lúc các người bảo vệ
giải quyết các xe vào cùng một vị trí trong bãi do vì họ thiếu thông tin.
Như vậy, các người bảo vệ phải hợp lực với nhau để phân phối chính xác các chỗ trong
bãi, đặc biệt là số lượng chỗ còn trống càng ít thì vai trò của hợp lực càng quan trọng.
Sự hoạt động gắn bó với nhau giữa các chương trình cung cấp là rất cần thiết để đảm
bảo cho hoạt động cung cấp được hoàn toàn chính xác.
II.1.1 VÍ DỤ VỀ KHÔNG GẮN BÓ:
Để thấy được tầm quan trọng mang tính quyết định của trình tự xử lý thông điệp đối
với yêu cầu gắn bó của hệ, ta hãy tiếp tục xem xét một trường hợp về không gắn bó của
bài toán bãi để xe : giả sử rằng ở thời điểm cho trước ta có 4 người bảo vệ và có 100 chỗ
còn trống. Tất cả các NBV để có thông tin đó, trạng thái của hệ lúc này là gắn bó. Ba
trong số họ phát đi thông tin cho ở Bảng II-1 sau:
Bảng II-1
Stt ký hiệu thông tin phát đi
1 M1 Thêm 20 chỗ trống
2 M2 có 10 chỗ bị chiếm
3 M3 Dành 10% chỗ trống để
quét dọn bãi
Bảng II-2: cho thấy, nếu ta không có ràng buộc nào đối với trình tự xử lý các thông
điệp nhận được của các người bảo vệ thì mỗi NBV sẽ có thông tin về số lượng chỗ trống
khác nhau. Để bảo đảm các bản cập nhật giống nhau thì trình tự cập nhật nhất thiết phải
giống nhau trên tất cả các trạm.

98
100
99 101
Tiểu luận Hệ Tin Học Phân Tán
II.1.2 QUI TẮC CHO CÁC THUẬT TOÁN CUNG CẤP TRONG HỆ
PHÂN TÁN:
Một sự hoạt động gắn bó của các chương trình cung cấp phân tán quản lý trên cùng
một tập hợp các tài nguyên chỉ đạt được nếu tuân thủ các qui tắc sau:
Stt Qui tắc
1 Các bộ cung cấp bắt buộc phải thực hiện cùng một giải thuật
2 Các bộ cung cấp đều nhận tất cả các thông điệp phát đi từ các tiến trình
3 Các thông điệp phải được xử lý cùng một trật tự như nhau trong các chương
trình cung cấp.
Qui tắc cuối, nhấn mạnh đến sự thiết yếu phải có một trật tự duy nhất trên tập hợp
các thông điệp của hệ. Trật tự này có thể được thực hiện thông qua việc hợp lực của các
tiến trình cung cấp. Ở phần sau chúng ta nghiên cứu một số phương pháp sắp xếp nhằm
xác lập một trật tự đảm bảo cho yêu cầu đồng bộ hóa.
II.2 VẤN ĐỀ ĐỒNG BỘ GIỮA CÁC TIẾN TRÌNH:
Trong các hệ 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 hệ phân tán, việc đồng bộ hóa chủ yếu yêu cầu 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ự đó có thể thể hiện thông qua việc trao đổi các
thông điệp với nhau.
Một tiến trình nào đó cần sử dụng tài nguyên để phát triển công việc của mình, phải
yêu cầu bộ cung cấp một cách hợp thức bằng cách gửi thông điệp yêu cầu. Như thế, một
tiến trình có nhu cầu tài nguyên sẽ bị treo chừng nào tài nguyên đó còn chưa được giải
phóng hay chưa được cung cấp cho nó.
II.2.1 MIỀN GĂNG:
 Miền găng: đoạn chương trình mà truy cập vào tài nguyên dùng chung.
 Vấn đề miền găng: các sự truy cập chồng lên nhau có thể dẫn đến các kết quả khác

d
+ thời gian thi hành trung bình E của một miền găng).
 Hoạt động với tải
 Với tải thấp, một số miền găng được thi hành. Khi một tiến trình muốn đi vào
miền găng, nó thường sẽ được cấp quyền ngay lập tức sau khi thi hành thuật toán
loại trừ tương hỗ. Đối với trường hợp hợp tải cao hoặc nặng, luôn luôn có các yêu
cầu miền găng phải chờ đợi. Ngay khi một trạm kết thúc miền găng của mình, nó
sẽ có thể cố gắng khởi tạo miền găng khác.
 Nếu gọi E là thời gian trung bình thi hành một miền găng, và T là độ trễ thông điệp
trung bình, thì trong hầu hết các thuật toán, thời gian cho trường hợp tốt nhất có cận
trên là (2T + E). Điều này cho phép trao đổi thông điệp vòng tròn cộng với sự thi
hành miền găng. Thời gian cho trường hợp xấu nhất là rất nhiều.
Nguyễn Thị Mai – Khoa học máy tính K10
- 14 -
3
.
a
P
(a
→
c) - bắc cầu -
•
b
Q
•
c
2
.
a
P

(nhân-quả)
3. Nếu A→B và B→C, thì A→C. (bắc cầu)
Nguyễn Thị Mai – Khoa học máy tính K10
- 15 -
Tiểu luận Hệ Tin Học Phân Tán
Sơ đồ của “ có trước ”:
 a → b có nghĩa: chúng ta có thể đi từ a đến b theo sơ đồ bằng cách di chuyển về
phía trước theo thời gian dọc theo các đường tiến trình và thông điệp, ví dụ p1 →
r4
 Chúng ta nói rằng a tác động nhân quả đến b
 Hai sự kiện là hợp lực nếu chúng có tác động nhân quả với nhau, ví dụ p3 và q3 là
hợp lực.
 Cho dù q3 xảy ra tại thời điểm vật lý sớm hơn p3 , tiến trình P không biết tiến
trình Q đã làm gì tại thời điểm q3 cho đến khi nó nhận được thông điệp tại thời
điểm p4.
• GẮN THỜI GIAN LOGIC VỚI CÁC SỰ KIỆN
 Các đồng hồ lôgic: gán một số cho mỗi sự kiện cục bộ.
 Hệ thống các đồng hồ lôgic phải chính xác :
 Để thực thi các đồng hồ thỏa mãn Điều kiện Đồng hồ, ta có thể áp dụng thuật toán
đóng dấu thời gian .
Nguyễn Thị Mai – Khoa học máy tính K10
- 16 -
p2
p1
p3
p4
q1
q2
q3
q4

, j) từ P
j
được gọi là có trước sự kiện phát
(n, T
n
, k) từ P
k
nếu :
Nếu T
m
< T
n
, hoặc
Nếu T
m
= T
n
và j < k
Hình sau minhhọa cho dạng thông điệp với trật tự ⇒
• GIẢI THUẬT ĐÓNG DẤU THỜI GIAN CỦA LAMPORRT
 Đồng hồ lôgic cho phép đóng dấu thời gian, nhằm xác lập trật tự cho từng sự kiện
trong hệ phân tán để với mỗi cặp sự kiện A và B ta có: nếu A có trước B (A → B)
thì đồng hồ lôgic của A nhỏ hơn đồng hồ lôgic của B.
Nguyễn Thị Mai – Khoa học máy tính K10
- 17 -
P1 P2 P3 P4
0 0 0 0
(a,1,1)
(b,1,4)
3

II.2.5.1 THUẬT TOÁN LAMPORT:
Thuật toán này được Lamport (1978) đưa ra, nó sử dụng cơ chế đóng dấu thời gian
cho việc đồng bộ các đồng hồ lôgic.
 Các giả định:
 Chúng ra giả định mô hình mạng kết nối hoàn toàn trong đó các tiến trình liên lạc
thông qua các kênh FIFO tin cậy. Tức là, các thông điệp không thể sắp xếp lại
theo trật tự khác.
 Các giả định được thực thi một cách dễ dàng ở tầng giao vận.
 Các kiểu thông điệp:
 (REQ, C
i
, i) : Một yêu cầu cho việc truy cập vào miền găng CS của tiến trình Pi.
Yêu cầu này được phát đi cho tất các các tiến trình khác.
 (REP, C
i
, i) : Hồi âm từ tiến trình Pi cho tiến trình Pj khi Pi nhận được yêu cầu từ
Pj.
Nguyễn Thị Mai – Khoa học máy tính K10
- 18 -
•
a
C
i
C
i
+1
•
a
C
i

C
i
(a) = C
j
(b) và i < j
Tiểu luận Hệ Tin Học Phân Tán
 (REL, C
i
, i) : Thông điệp giải phóng từ Pi thông báo cho biết nó đã rời khỏi CS.
Thông điệp này được gửi cho tất cả các tiến trình khác.
 Các biến tiến trình:
 C
i
: Đồng hồ cục bộ của Pi, khởi tạo từ 0.
 q
i
: Hàng đợi [0 … n-1] chứa các thông điệp.
 Thuật toán:
 Khi một tiến trình tại trạm S
i
muốn thi hành đoạn găng: nó sẽ gửi thông điệp
REQ có đánh dấu thời gian cho tất cả các trạm trong hệ thống kể cả trạm S
i
.
 Mỗi trạm, S
i
, duy trì một hàng đợi chứa các thông điệp yêu cầu được sắp xếp
theo trật tự các dấu thời gian; các đồng hồ logic và quan hệ trật tự toàn bộ được
sử dụng để gắn các dấu thời gian.
 Khi một trạm nhận được yêu cầu, nó sẽ đưa thông điệp đó vào hàng đợi yêu cầu

state := wanted; //Chuẩn bị vào
Multicast request to all processes; request processing deferred here
T := request’s timestamp; // Thiết lập thời gian
Wait until (number of replies received = (N – 1));
state := held; // đã vào đoạn găng
On receipt of a request <Ti, pi> at pj (i ≠ j)//Nhận được yêu cầu tại thời điểm j

if (state = held or (state = wanted and (T, pj) < (Ti, pi)))
then
queue request from pi without replying; // đưa vào hàng đợi
else
reply immediately to pi; // gởi lại
end if
To exit the critical section // thoát khỏi vùng găng
state := released;
reply to any queued requests; //gởi lại
Nguyễn Thị Mai – Khoa học máy tính K10
- 20 -
N-1
TRẠM S
i
TRẠM S
1
REQ
TĐ2
…
TRẠM S
2
REQ
TĐ2

hàng
đợi
TRẠM S
i
TRẠM S
1
REQ
TĐ2
…
TRẠM S
2
REQ
TĐ2
…
………. TRẠM S
n
REQ
TĐ2
…
REQ
(wanted)
REL
+
-
REP
Nếu TT:

Wanted(T)
Held
HEL

8. Và một số website khác
Nguyễn Thị Mai – Khoa học máy tính K10
- 21 -
Tiểu luận Hệ Tin Học Phân Tán
MỤC LỤC
LỜI MỞ ĐẦU 1
I. Phần lý thuyết mô hình CLIENT / SERVER 2
I.1. Nguyên tắc hoạt động CLIENT/SERVER 2
I.1.1. CLIENT 3
I.1.2. SERVER 4
I.1.3. MẠNG 4
I.1.3. GIAO THỨC 5
I.2. Phân loại ứng dụng CLIENT/SERVER 7
I.2.1. HOST BASE PROCESSING 7
I.2.2. CLIENT BASE PROCESSING 7
I.2.3. COOPERATIVE PROCESSING 8
I.3 Ưu nhược điểm của mô hình CLIENT/SERVER 8
I.3.1. Ưu điểm 8
I.3.2. Nhược điểm 8
I.3 Ứng dụng minh hoạ 8
II. PHẦN CHƯƠNG TRÌNH 11
II.1 BÀI TOÁN BÃI ĐẬU XE Ô TÔ 11
II.1.1 Ví dụ về không gắn bó 12
II.1.2 Quy tắc cho các thuật toán cung cấp trong hệ phân tán 13
II.2 VẤN ĐỀ ĐỒNG BỘ GIỮA CÁC TIẾN TRÌNH 13
II.2.1 Miền găng 13
II.2.2 Phân tích các thuật toán truy cập loại trừ tương hỗ 14
II.2.3 Sắp xếp kiểu đóng dấu 15
II.2.3.1 Các khái niệm 15
II.2.4 Đồng hồ theo trật tự tổng quát chặt chẽ (LAMPORRT) 17