Đà Nẵng, tháng 7 năm 2009
ĐẠI HỌC ĐÀ NẴNG
*****  *****
TIỂU LUẬN
MÔN HỆ PHÂN TÁN
ĐỀ TÀI: ĐỒNG BỘ TIẾN TRÌNH
Giảng viên giảng dạy : PGS.TS. LÊ VĂN SƠN
Học viên thực hiện : NGUYỄN THỊ THÚY HOÀI
Lớp : Cao học Khoa học máy tính - Khóa 10
Niên khoá : 2008 - 2011
Tiểu luận môn Hệ Phân Tán
LỜI MỞ ĐẦU
Trong thời đại phát triển công nghệ nhanh chóng như hiện nay, Internet đã trở thành
người bạn đồng hành không thể thiếu được của hàng chục triệu người trên thế giới và là
cầu nối giữa các lĩnh vực tri thức với nhau. Internet đã trở thành mạng dữ liệu công cộng
lớn nhất, giúp cho việc trao đổi thông tin trở nên nhanh hơn và thuận tiện hơn so với trước
đây. Chính vì vậy, Internet đã và đang làm thay đổi cuộc sống của con người, làm cải
thiện công việc kinh doanh, giải trí, giáo dục cũng như phương thức liên lạc và Internet
đã đưa xã hội loài người bước vào một kỷ nguyên mới, kỷ nguyên của công nghệ thông tin.
Ngày nay, số lượng người sử dụng Internet ngày càng tăng, dẫn đến lưu lượng thông
tin trên mạng cũng tăng lên đáng kể. Do đó, các vấn đề liên quan đến tốc độ, độ tin cậy
trên đường truyền được nhiều nhà khoa học máy tính đặc biệt quan tâm. Trong đó, các
vấn đề về đồng bộ tiến trình trên mạng là một trong những nội dung nghiên cứu chủ yếu
của môn hệ phân tán
Chính vì những lý do trên mà tiểu luận của em nghiên cứu liên quan về vấn đề đồng bộ
tiến trình. Đồ án được chia làm 3 chương:
Chương 1: Tổng quan về hệ phân tán
Chương 2: Đồng bộ tiến trình
Trong phạm vi đề tài này em chỉ nghiên cứu lý thuyết của vấn đề đồng bộ tiến trình,
chắc chắn trong quá trình làm không tránh phải các thiếu sót, em rất mong các thầy cô chỉ
bảo để đồ án của em có thể hoàn thành tốt đẹp.

SVTH: Nguyễn Thị Thúy Hoài Trang 2
Tiểu luận môn Hệ Phân Tán
MỤC LỤC
CHƯƠNG 1: TỔNG QUAN VỀ HỆ PHÂN TÁN 5
I. Hệ tin học phân tán 5
1. Khái niệm hệ tin học phân tán 5
2. Đặc điểm cơ bản của hệ phân tán 6
3. Các điểm mạnh của hệ tin học phân tán 6
CHƯƠNG 2: ĐỒNG BỘ TIẾN TRÌNH 8
I. Đồng bộ tiến trình 8
1. Bài toán đồng bộ hóa 8
2. Miền găng hay vùng tương trục 9
3. Đồng bộ hóa các tiến trình trong hệ điều hành tập trung 10
a. Loại trừ lẫn nhau (mutual exclusion) 10
b. Đồng bộ hóa 11
c. Tắt nghẽn 11
d. Các semaphore 11
4. Vấn đề đồng bộ hóa các tiến trình trong hệ điều hành phân tán 14
a. Trật tự từng phần 15
b. Giả định các điều kiện chung 16
c. Đồng bộ hóa bằng phương pháp trật tự từng phần 17
II. Công tơ sự kiện 19
1. Các kiến thức liên quan đến công tơ sự kiện 19
2. Chứng minh bài toán dựa trên kiến thức về công tơ sự kiện 19
a. Chứng minh Pi → Ci 20
b. Chứng minh Ci → Pi+N 20
SVTH: Nguyễn Thị Thúy Hoài Trang 3
Tiểu luận môn Hệ Phân Tán
NỘI DUNG TIỂU LUẬN
Đề số 33

Đồng bộ tiến trình.
Trên cơ sở kiến thức về công tơ sự kiện, hãy chứng minh quan hệ sau đây:
Sản xuất thứ i  Tiêu thụ thứ i  Sản xuất thứ (i+N)
Gợi ý: Nhằm giải quyết vấn đề nêu trên, ta thành lập 2 hàm nguyên thuỷ :
Tang(E) - Tăng lên 1 đơn vị cho công tơ đếm
Cho(E,i) - Treo cho đến khi lớn hơn hay bằng i
Phép toán thứ i Tang(E)  Cho(E,i)
SVTH: Nguyễn Thị Thúy Hoài Trang 4
Tiểu luận môn Hệ Phân Tán
NỘI DUNG TRÌNH BÀY
CHƯƠNG 1: TỔNG QUAN VỀ HỆ PHÂN TÁN
I. Hệ tin học phân tán
1. Khái niệm hệ tin học phân tán
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. Trong điều kiện đó, hiện nay đứng trên nhiều phương diện khác nhau
người ta có thể có các định nghĩa khác nhau về hệ tin học phân tán, nhưng phổ biến hơn cả
là định nghĩa được nêu dưới đây.
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ào nhau 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
đó có một (hay nhiều) hệ thống khác nhau trả lời các yêu cầu có liên quan đến phần dữ liệu
của mình. Nói một cách tổng quát trong hệ luôn diễn ra việc thực hiện các công việc do các
hệ thống yêu cầu.
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ư tài nguyên dùng chung.
Việc định nghĩa các tài nguyên của hệ như tài nguyên dùng chung sẽ mang đến cho
người sử dụng những tiện ích và đem lại cho hệ những hiệu năng tốt trong khai thác ứng

dụng.
Năm ưu điểm căn bản của việc sử dụng chung tài nguyên được phản ánh trong bảng
sau:
STT Ưu diểm so với hệ tập trung
1 Tăng tốc độ bình quân trong tính toán – xử lý
2 Cải thiện tình trạng luôn luôn sẵn sàng của các loại tài nguyên
3 Tăng độ an toàn dữ liệu
4 Đa dạng hóa các loại hình dịch vụ tin học
5 Đảm bảo tính vẹn toàn của thông tin
SVTH: Nguyễn Thị Thúy Hoài Trang 5
Tiểu luận môn Hệ Phân Tán
2. Đặc điểm cơ bản của hệ phân tán
STT Tên gọi Thuyết minh
1 Chia sẻ tài nguyên Việc dùng chung tài nguyên trong mạng máy tính là
vấn đề lớn trong hệ phân tán. Một tiến trình trên một
trạm nào đó có thể yêu cầu cung cấp tài nguyên dùng
chung ở một trạm khác
2 Liên lạc Khi hệ thống được mắc nối với nhau, các thực thể của
hệ có thể trao đổi thông tin cho nhau
3 Tin cậy Một tram của hệ bị sự cố không làm cho toàn hệ bị
ảnh hưởng, mà ngược lại, công việc của trạm đó được
phân cho các trạm khác đảm nhiệm. Ngoài ra, trạm bị
sự cố có thể tự động phục hồi lại các trạng thái trước
khi bị sự cố hay trạng thái ban đầu của nó
4 Tăng tốc Đây là một khái niệm mới về phân tán tải. Một tính
toán lớn nào đó, nếu chỉ sử dụng một trạm, thì thời
gian trả kết quả sẽ lớn nhất. Tính toán này được chia
nhỏ và thực hiện song song trên các trạm. Điều này
cũng rất cần thiết đối với những trạm bị quá tải
3. Các điểm mạnh của hệ tin học phân tán

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 này 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.
Cơ chế Client/Server cung cấp kiến trúc phù hợp cho việc dàn trải hệ thống phân tán.
Mô tả nhiều cách truy cập trong các hệ thống phân tán. Các máy mainframe sẽ dùng để lưu
trữ các dữ liệu di sản hoặc đóng vai trò kho dữ liệu (data warehouse). Cơ chế này giúp xây
dựng các trung tâm dữ liệu staging (công bố), phục vụ tốt cho việc truy cập. Người dùng ở
SVTH: Nguyễn Thị Thúy Hoài Trang 6
Tiểu luận môn Hệ Phân Tán
xa có thể truy cập dữ liệu trên hệ staging hay tại các máy chủ cục bộ. Người dùng còn có
thể trao đổi thông tin với nhau bằng thư điện tử và hình thành các nhóm công tác.
Tóm lại, các đặc điểm cơ bản của tất cả các hệ thống tin học phân tán là:
• 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 thong đ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ó bị sự cố và hoạt động của
toàn hệ trở nên kém hiệu quả.
SVTH: Nguyễn Thị Thúy Hoài Trang 7
Tiểu luận môn Hệ Phân Tán
CHƯƠNG 2: ĐỒNG BỘ TIẾN TRÌNH
I. Đồng bộ tiến trình

1. Bài toán đồng bộ hóa
Công việc không thể được tiến hành nếu nó không được bộ xử lý tiếp nhận và thực
hiện: bộ xử lý là một tài nguyên của hệ thống được sử dụng để hoàn thành công việc. Có
thể coi chương trình cần thực hiện như một quá trình (các hệ điều hành khác nhau có thể
sử dụng các thuật ngữ khác nhau cùng nghĩa với thuật ngữ quá trình, mà phổ biến hơn cả là
thuật ngữ tiến trình, bài toán), quá trình là đối tượng được tiếp nhận bởi bộ xử lý (D.L.
Parnar, 1974). Cần phân biệt khái niệm quá trình với khái niệm chương trình: quá trình là
thực hiện một chương trình nào đó kể từ khi bắt đầu đến khi kết thúc. Vì vậy, cùng một lúc
trong chế độ đa người dùng, có 3 người dùng đều gọi chương trình dịch ngôn ngữ C: hệ
thống chỉ có 1 chương trình dịch C, trong khi đó tại thời điểm đang xét có 3 quá trình đang
tồn tại và được điều phối CPU.
Các tiến trình không tồn tại một cách độc lập trong máy tính, chúng hợp tác với nhau
để thực hiện các công việc của người sử dụng và chúng cạnh tranh với nhau để sử dụng
chung các tài nguyên hữu hạn: các bộ xử lý hoặc các file thông tin. Hai đặc trưng hợp tác
và cạnh tranh dẫn tới sự cần thiết của các liên lạc giữa các tiến trình.
Để làm rõ tính quan trọng của việc đồng bộ hóa tiến trình chúng ta xét ví dụ sau: giả sử
rằng chương trình nào đó có biến counter và giá trị của biến counter hiện tại là 5, thủ tục
người sản xuất và người tiêu dùng thực thi đồng hành câu lệnh “counter++” và “counter ”.
Theo sau việc thực thi hai câu lệnh này, giá trị của biến counter có thể là 4, 5 hay 6? Kết
quả chỉ đúng khi biến counter==5, được tạo ra đúng nếu tiến trình người sản xuất và người
tiêu dùng thực thi riêng biệt.
Chúng ta có thể minh hoạ giá trị của counter có thể không đúng như sau. Chú ý, câu
lệnh “counter++” có thể được cài đặt bằng ngôn ngữ máy (trên một máy điển hình) như
sau:
register1 = counter
register1 = register1 + 1
counter = register1
Ở đây register1 là một thanh ghi CPU cục bộ. Tương tự, câu lệnh “counter ”
được cài đặt như sau:
register2 = counter

SVTH: Nguyễn Thị Thúy Hoài Trang 8
Tiểu luận môn Hệ Phân Tán
register2 = register2 - 1
counter = register2
Ở đây register2 là thanh ghi CPU cục bộ. Dù là register1 và register2 có thể dùng cùng
thanh ghi vật lý, nhưng nội dung của thanh ghi sẽ được lưu lại và lấy lại bởi bộ quản lý
ngắt.
Thực thi đồng hành của “counter++” và “counter ” là tương tự như thực thi tuần tự ở
đây các câu lệnh cấp thấp hơn được hiện diện trước bị phủ lắp trong thứ tự bất kỳ (nhưng
thứ tự bên trong mỗi câu lệnh cấp cao được lưu giữ). Một sự phủ lắp là:
T0: producerthựcthi register1 = counter{register1 = 5}
T1: producerthựcthi register1 = register1 + 1 {register1 = 6}
T2: consumerthựcthi register2 = counter{register2 = 5}
T3: consumerthựcthi register2 = register2 – 1{register2 = 4}
T4: producerthựcthi counter = register1{counter = 6}
T5: consumerthựcthi counter = register2{counter = 4}
Chú ý rằng, chúng ta xem xét tình trạng không đúng “counter==4” theo đó có 4 vùng
đệm đầy, nhưng thực tế khi đó có 5 vùng đệm đầy. Nếu chúng đổi ngược lại thứ tự của câu
lệnh T4 và T5, chúng ta sẽ có trạng thái không đúng “counter ==6”.
Chúng ta đi đến trạng thái không đúng này vì chúng ta cho phép cả hai quá trình thao
tác đồng thời trên biến counter. Trường hợp tương tự, ở đây nhiều quá trình truy xuất và
thao tác cùng dữ liệu đồng hành và kết quả của việc thực thi phụ thuộc vào thứ tự xác định
trong đó việc truy xuất xảy ra, được gọi là điều kiện cạnh tranh (race condition). Để ngăn
chặn điều kiện cạnh tranh ở trên, chúng ta cần đảm bảo rằng chỉ một quá trình tại một thời
điểm có thể được thao tác biến counter. Để thực hiện việc đảm bảo như thế, chúng ta yêu
cầu một vài hình thức đồng bộ hoá quá trình. Những trường hợp như thế xảy ra thường
xuyên trong các hệ điều hành khi các phần khác nhau của hệ thống thao tác các tài nguyên
và chúng ta muốn các thay đổi không gây trở ngại một sự thay đổi khác.
2. Miền găng hay vùng tương trục
Xét một hệ thống gồm n quá trình (P

0
, P
1
, … ,P
n-1
). Mỗi quá trình có một phân đoạn
mã, được gọi là miền găng (critical section), trong đó quá trình này có thể thay đổi những
biến dùng chung, cập nhật một bảng, viết đến tập tin Đặc điểm quan trọng của hệ thống là
ở chỗ, khi một quá trình đang thực thi trong vùng tương trục, không có tiến trình nào khác
được phép thực thi trong vùng tương trục của nó. Do đó, việc thực thi của các vùng tương
trục bởi các tiến trình là sự loại trừ hỗ tương. Vấn đề miền găng là thiết kế một giao thức
mà các quá trình có thể dùng để cộng tác. Mỗi tiến trình phải yêu cầu quyền để đi vào vùng
SVTH: Nguyễn Thị Thúy Hoài Trang 9
Tiểu luận môn Hệ Phân Tán
tương trục của nó. Vùng mã thực hiện yêu cầu này là phần đi vào (entry section). Vùng
tương trục có thể được theo sau bởi một phần kết thúc (exit section). Mã còn lại là phần
còn lại (remainder section). Cấu trúc chung của một quá trình điển hình P
i
:
do { entry section
critical section
exit section
remainder section
} while (1);
Một giải pháp đối với vấn đề miền găng phải thoả mãn ba yêu cầu sau:
• Loại trừ hỗ tương (Mutual Exclusion): Nếu quá trình Pi đang thực thi trong miền
găng của nó thì không tiến trình nào khác đang được thực thi trong miền găng đó.
• Progress: nếu không có tiến trình nào đang thực thi trong miền găng và có vài
tiến trình muốn vào miền găng thì chỉ những tiến trình không đang thực thi phần còn
lại mới có thể tham gia vào việc quyết định tiến trình nào sẽ đi vào vùng găng tiếp theo

và chọn lựa này không thể trì hoãn vô hạn định.
• Chờ đợi có giới hạn (bounded wait): giới hạn số lần các tiến trình khác được
phép đi vào miền găng sau khi một tiến trình thực hiện yêu cầu để đi vào miền găng
của nó và trước khi yêu cầu đó được gán.
3. Đồng bộ hóa các tiến trình trong hệ điều hành tập trung
a. Loại trừ lẫn nhau (mutual exclusion)
Các tài nguyên trong hệ thống có thể được phân thành 2 loại:
• Các tài nguyên phân chia được: có thể sử dụng đồng thời bởi nhiều tiến trình
• Các tài nguyên không phân chia được: chỉ có thể được sử dụng bởi một tiến trình
duy nhất tại một thời điểm.
Sự không phân chia được của một tài nguyên là do hai nguyên nhân sau:
• Sự không phân chia được về mặt vật lý. Ví vụ một máy đọc băng giấu đục lỗ
không cho phép đổi băng giữa các ký tự liên tiếp.
• Nếu một tài nguyên được sử dụng đồng thời bởi nhiều tiến trình thì sẽ có nguy cơ
bị chồng chéo, không nhất quán.
Ví dụ xét một vùng nhớ được truy cập bởi nhiều bộ xử lý, nếu một xử lý đọc nội dung
của vùng trong khi một bộ xử lý khác sửa đổi thì kết quả là không lường trước được.
Giả sử trong hệ đăng ký chỗ máy bay, một ghế được biểu diễn bởi nội dung của một ký
SVTH: Nguyễn Thị Thúy Hoài Trang 10
Tiểu luận môn Hệ Phân Tán
tự tại một thời điểm nào đó, hai phòng dịch vụ đăng ký đồng thời cùng một ghế bằng
các thao tác như sau:

Các tài nguyên không phân chia được chủ yếu là các ngoại vi, các file khi viết và các
vùng dữ liệu được cập nhập liên tiếp
Các tài nguyên phân chia được chủ yếu là các đơn vị trung tâm, các file khi chỉ đọc hặc
các vùng nhớ chỉ chứa chương trình và dữ liệu được bảo vệ cấm sửa đổi.
Vấn đề cần giải quyết đối với loại trừ lẫn nhau là đảm bảo cho các tài nguyên không
phân chia được chỉ có thể truy nhập được một tiến trình duy nhất tại một thời điểm.
b. Đồng bộ hóa

Một cách tổng quát, tốc độ tương đối giữa hai tiến trình là không biết trước được vì
chúng phụ thuộc vào tần số của các ngắt của từng tiến trình cũng như vào thời gian làm
việc và tần số gán bộ xử lý cho từng tiến trình.
Chúng ta nói rằng các tiến trình tiến triển không đồng bộ đối với nhau. Tuy nhiên, để
đảm bảo một sự hợp tác nhất định nào đó, các bộ xử lý phải đồng bộ hóa các hoạt động của
chúng tại một số thời điểm, khi một tiến trình chỉ có thể tiếp diễn được nếu một tiến trình
khác hoàn tất một thao tác nhất định nào đó của nó. Do vậy, hệ điều hành phải cung cấp
một cơ chế đồng bộ hóa.
c. Tắt nghẽn
Khi nhiều tiến trình tìm kiếm tài nguyên tại cùng một thời điểm thì hệ có thể đi đến
tình trạng tắt nghẽn nếu các tài nguyên được yêu cầu bởi một tiến trình bị chiếm giữ bởi
một tiến trình khác và ngược lại. Hiện tượng này tương tự với tình huống giao thông xuất
hiện khi hai dòng xe bị tắt nghẽn tại một ngã tư. Dự kiến trước hoặc làm giảm bớt ảnh
hưởng của tắt nghẽn là một chức năng không thể thiếu được của hệ điều hành.
d. Các semaphore
Đóng góp quan trọng nhất cho hệ liên lạc giữa các tiến trình là việc Dijkstra đưa ra
nguyên lý của các semaphore (đèn hiệu) và các toán tử wait và signal liên thuộc.
SVTH: Nguyễn Thị Thúy Hoài Trang 11
Phòng A thấy ghế trống và
hỏi ý kiến khách hàng
.
.
.
Phòng A đăng ký ghế
Phòng B thấy ghế trống và
hỏi ý kiến khách hàng
.
.
.
Phòng B đăng ký ghế

Tiểu luận môn Hệ Phân Tán
Một semaphore là một sô nguyên không âm được khởi động và chỉ có thể được sửa đổi
bởi các toán tử wait và signal theo các quy tắc sau:
signal(S): toán tử signal tăng giá trị của semaphore S lên một đơn vị. Phép tăng là
không phân chia được, điều đó có nghĩa là toán tử signal không thực sự tương đương với
lệnh gán S:=S-1. Giả sử S=3, hai tiến trình A và B đều muốn thực hiện phép toán signal(S)
thì kết quả sẽ cho S=5. Trái lại, nếu hai tiến trình cùng muốn thực hiện S:=S+1 một cách
độc lập thì kết quả sẽ cho S=4 vì gán giá trị 4=3+1 và tương tự B cũng gán giá trị 4=3+1
wait(S): toán tử wait giảm giá trị của semaphore S đi một đơn vị với điều kiện là
kết quả không trở thành âm. Khi phép toán wait của một tiến trình áp dụng lên một
semaphore có giá trị 0 thì tiến trình này phải đợi tiến trình khác làm cho giá trị của
semaphore trở thành 1 bằng phép toán signal. Chỉ khi đó phép toán wait mới được thực
hiện và tiến trình tương ứng mới được tiếp tục trở lại. Phép toán wait cũng là không phân
chia được. Khi có nhiều tiến trình đang đợi thì chỉ một tiến trình duy nhất có thể thực hiện
phép toán wait sau lúc giá trị của semaphore được chuyển thành 1.
Đối với một semaphore, tác động của các phép toán wait và signal là như sau:
wait(S){
while (S≤0);
S++;
}
signal(S){
S++;
}
Giá trị S phụ thuộc vào số các phép toán wait và signal đã được thực hiện
val(sem) = c(sem) + ns(sem) - nw(sem) (1)
Trong đó, val(sem) là giá trị của semaphore
c(sem) là giá trị ban đầu của semaphore
ns(sem) là số các phép signal đã được thực hiện
nw(sem) là số các phép wait thực sự đã được thực hiện
Do định nghĩa val(sem)≥0 nên ta có bất đẳng thức quan trọng

nw(sem)≤ns(sem)+c(sem) (2)
Đẳng thức chỉ xảy ra khi val(sem)=0
Bây giờ chúng ta sẽ xem nguyên lý của các semaphore có thể giúp giải quyết vấn đề
liên lạc của các tiến trình như thế nào?
SVTH: Nguyễn Thị Thúy Hoài Trang 12
Tiểu luận môn Hệ Phân Tán
Loại trừ lẫn nhau: các tài nguyên không phân chia được sẽ được bảo vệ bởi sự truy
nhập đồng thời của nhiều tiến trình bằng cách cấm các tiến trình thực hiện đồng thời các
phần chương trình truy nhập. Các phần này của các chương trình truy nhập được gọi là các
miền găng (critical section). Loại trừ lẫn nhau trong việc sử dụng các tài nguyên có thể
được xem là loại trừ lẫn nhau đối với thực hiện của các miền găng. Việc loại trừ có thể
được thực hiện đơn giản bằng cách bọc mỗi miền găng bởi các phép wait và signal trên
một semaphore duy nhất có giá trị ban đầu là +1. Mỗi miền găng được lập trình dưới dạng:
Wait(mutex)
Miền găng
Signal(mutex)
Trong đó mutex là tên của semaphore
Dễ nhận thấy nếu giá trị ban đầu của mutex là 1 thì loại trừ nhau được đảm bảo, vì
nhiều nhất cũng chỉ có một tiến trình có thể thực hiện wait (mutex) trước khi có một tiến
trình khác thực hiện một phép signal(mutex). Một cách hình thức, theo (2) ta có nw(mutex)
= ns(mutex) +1, như vậy tại một thời điểm chỉ có tối đa một tiến trình có thể khai thác
được miền găng.
Ví dụ xét hai tiến trình A và B thực hiện việc nạp vào và rút ra các phần tử của một
hàng đợi. Để con trỏ của hàng đợi không bị sai lệch, cần phải có giới hạn việc truy nhập
hàng đợi bởi chỉ một tiến trình tại một thời điểm. Việc nạp và rút ra các phần tử được biểu
diễn dưới dạng các miền găng như sau:

Người ta nghi ngờ liệu loại trừ lẫn nhau có thể được giải quyết mà không có sự tham
gia của semaphore và các phép toán liên thuộc wait và signal hay không? Liệu có bảo vệ
một miền găng bằng một biến đơn giản gọi là biến cửa, khi cửa là mở thì việc vào miền

găng là cho phép. Bằng cách như vậy, một miền găng có thể thực hiện như sau:
While cửa đóng do rỗng;
SVTH: Nguyễn Thị Thúy Hoài Trang 13
Chương trình của tiến trình A
Wait (mutex)
Nạp phần tử vào hàng đợi
Signal(mutex)
Chương trình của tiến trình B
Wait (mutex)
rút phần tử vào hàng đợi
Signal(mutex)
Tiểu luận môn Hệ Phân Tán
Cửa: đóng;
Miền găng
Cửa: mở;
Đáng tiếc rằng giải pháp đơn giản này không hoạt động được do sự tách biệt giữa phép
kiểm tra cửa mở ở dòng thứ nhất và phép đóng cửa ở dòng thứ hai. Hai tiến trình thực hiện
song song có thể đều thấy cửa mở ở dòng thứ nhất trước khi một trong hai tiến trình có
thời gian để đóng cửa ở dòng thứ hai. Điều này dẫn tới việc cả hai tiến trình cùng bước vào
miền găng.
Các semaphore tránh được các vấn đề như vậy vì các phép wait và signal là không
phân chia được, tức là không có khả năng hai tiến trình tác động tại cùng một thời điểm lên
cùng một semaphore.
4. Vấn đề đồng bộ hóa các tiến trình trong hệ điều hành phân tán
Trình tự và đồng bộ các tiến trình chỉ ra các vấn đề đồng bộ có thể dẫn đến phải thiết
chế một trật tự tổng quát của các sự kiện diễn ra trong hệ. Cần xác định mối liên hệ trao
đổi thông qua các thông điệp với thời hạn truyền khác nhau, những thông tin tạm thời trao
đổi không có giá trị tuyệt đối và trình tự tổng quát cần phải được thể hiện bằng phương
tiện giải thuật đảm bảo hoạt động nhịp nhàng giữa các tiến trình có liên quan.
Trong tất cả các hệ thống tin học, đồng bộ hóa các tiến trình mang tính cấp thiết về mặt

nguyên lý và kỹ thuật thể hiện ở hai nguyên do cơ bản sau đây:
• 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 tài nguyên với các 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 hoạt độ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ó sự trao đổi thông tin qua
lại với nhau. Trong các hệ thống tập trung điều đó được thực hiện nhờ thuật toán loại bỏ
tương hỗ thông qua các biến cùng tác động trong một vùng nhớ chung. 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.
SVTH: Nguyễn Thị Thúy Hoài Trang 14
Tiểu luận môn Hệ Phân Tán
a. Trật tự từng phần
Chú ý rằng, 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 quan cơ chế loại trừ tương hỗ. Cơ chế này cho phép sắp đặt (xác lập trật tự) hoàn
toàn các sự kiện.
Trong thực tiễn, nói một cách chính xác, có một 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 phải quan tâm giải quyết.
Trong các hệ 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ỉ có thể 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à được gọi là “có trước” hay “ở ngay 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 trong bảng sau đây:

C1: nếu A và B là hai sự kiện của cùng một trạm và nếu A thực hiện trước B thì theo trật tự
cục bộ của trạm ta có: AB.
C2: 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ình vẽ sau đây cho ta một trạm ví dụ về trật tự hóa từng phần của các sự kiện trong
hệ thống.
Theo hình vẽ đó, ta có thể biểu diễn trật tự như sau:
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 A1B2 VÀ B3A4
Chuyển qua
A1A2B2B3B4
B1B2B3A4A5
A1A2B2B3A4A5
SVTH: Nguyễn Thị Thúy Hoài Trang 15
Tiểu luận môn Hệ Phân Tán
Ví dụ về các sự kiện không so sánh B1 và A1, A2, A3; A3 và B2, B3, B4
Ràng buộc C1 thể hiển rằng trật tự có được bởi quan hệ có trước là tương thích với các
trật tự cục bộ được định nghĩa trong từng trạm.
Ràng buộc C2 nói lên nguyên tắc nhân quả.
Quan hệ có trước xác định một trật tự từng phần trên tập hợp các sự kiện của hệ và trật
tự này có thể hiện trong hình vẽ trên.
b. Giả định các điều kiện chung
Các phương pháp được giới thiệu trong chương này sẽ xuất phát từ các giả định với các
điều kiện chung như sau.
Các hệ phân tán được xây dựng trên cơ sở các trạm làm việc được mắc nối với nhau
(nối mạng). Mỗi một trạm có bộ nhớ riêng của mình và tuyệt đối không có bộ nhớ chung.
Chúng ta áp dụng các ký hiệu trong bảng sau:
STT Ký hiệu Thuyết minh

1 H1 Một trạm trong các trạm đều có thể liên lạc với các trạm
còn lại trong hệ
2 H2 Không có lỗi truyền thông tin và không mất thông điệp
3 H3 Trật tự nhận trên trạm j như của dãy các thông điệp cũng
giống như chính tại trạm I là giống với trật tự nơi phát
4 H4 Sự cố hay gián đoạn vật lý tại một trạm nào đó được phát
hiện sẽ lập tức thông báo đến các trạm có ý định liên lạc
đến nó
Sự hoạt động của các mạng vận chuyển thường là tương thích với các giả sử nêu trên
và luôn luôn đòi hỏi một mức độ ổn định nhất định.
SVTH: Nguyễn Thị Thúy Hoài Trang 16
A1
A2
A3
A4
A5
B1
B2
B3
B4
B5
t
Tiểu luận môn Hệ Phân Tán
Trước hết, chúng ta nghiên cứu sự hoạt động của hệ thống không có sự cố, rồi sau đó
chúng ta sẽ chỉ ra hiệu ứng của sự cố hay việc phục hồi lại một trạm. Đó là trường hợp mà
ta nêu lên trong H4 ở trên.
Ngoài ra, chúng ta còn giả sử rằng hiện tượng gây sự cố trên một trạm chỉ làm cho trạm
đó không liên lạc được với mạng mà hoàn toàn không ảnh hưởng đến sự hoạt động của các
trạm còn lại hoặc ít nhất là một nhóm các trạm khác.
c. Đồ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.
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
SVTH: Nguyễn Thị Thúy Hoài Trang 17
Tiểu luận môn Hệ Phân Tá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:
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:
• 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ó.
• 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.
• 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.
• 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
SVTH: Nguyễn Thị Thúy Hoài Trang 18
P
1
C
1
P
2
C
2
P
i
C
i
P
i+N

C
i+1
P
i+N+1
P
i
: Sản xuất thứ i
C
i
: Tiêu thụ thứ i
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 đó, np số lượng thông tin đã sản xuất bởi P mà C không biết
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à đủ.
II. Công tơ sự kiện
1. Các kiến thức liên quan đến công tơ sự kiện
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ơ là biến nguyên không lùi, được kết hợp với một nhóm đặt 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 :
STT Tên hàm Chức năng
1 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.
2 Truy_van (E) Cung cấp giá trị hiện hành của công tơ phối hợp với
E
3 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ó. 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. Trong bài toán người sản xuất, người tiêu thụ ta định nghĩa công tơ sự
kiện như sau:
• Hai công tơ sự kiện NP’ và NC’ được khởi động bằng giá trị 0
• Hai biến nguyên NP và NC khởi gán giá trị 0, là cục bộ đối với người sản xuất P
và người tiêu thụ C
2. Chứng minh bài toán dựa trên kiến thức về công tơ sự kiện
SVTH: Nguyễn Thị Thúy Hoài Trang 19

Tiểu luận môn Hệ Phân Tán
a. Chứng minh P
i
→ C
i
Xét tại trường hợp sản xuất thứ i-1.
Tại trạm sản xuất PS, số lượng sản phẩm được sản xuất là NP=i-1.
Tại trạm tiêu thụ CS, số lượng sản phẩm tiêu thụ giả sử đang là NC=i–m (m>0)
Khi đó các công tơ sự kiện tại trạm sản xuất NC’=i–m, tại trạm tiêu thụ NP’=i-1.
Nếu trạm sản xuất PS tạm ngừng không sản xuất nữa, trạm tiêu thụ CS sẽ tiêu thụ cho
đến sản phẩm thứ i-1, NC=i-1. Lúc này, ta có:
NC = NP’ = i -1
Khi đó, trạm tiêu thụ CS sẽ không tiêu thụ nữa vì điều kiện NP’ – NC > 0 không còn
thỏa mãn. Điều này có nghĩa là tiêu thụ C
i
không thể thực hiện trước sản xuất P
i
.
Trạm PS thực hiện sản xuất thứ i, NP = i. Sau khi sản xuất, trạm PS gửi thông điệp
thông báo cho trạm CS biết đã sản xuất thêm sản phẩm. Khi nhận được thông điệp từ trạm
PS, trạm CS sẽ tăng giá trị của công tơ sự kiện thêm một đơn vị NP’ = NP’ + 1. Khi đó
NP’ = i, NC = i-1 nên điều kiện NP’ – NC > 0 thỏa mãn, và lúc này trạm CS có thể thực
hiện việc tiêu thụ thứ i. Như vậy ta đã chứng minh được sản xuất thứ i có trước tiêu thụ thứ
i hay P
i
→ C
i
b. Chứng minh C
i
→ P

i+N
Xét tại trường hợp tiêu thụ thứ i-1.
Tại trạm tiêu thụ CS, số lượng sản phẩm tiêu thụ là:
NC = i - 1
Tại trạm sản xuất PS, số lượng sản phẩm được sản xuất giả sử đang là:
NP = (i – 1) + m với m ≥ 0
Khi đó các công tơ sự kiện tại trạm sản xuất:
NC’ = i – 1,
Tại trạm tiêu thụ:
NP’ = (i – 1) + m với m≥0
Nếu trạm tiêu thụ CS tạm ngừng không tiêu thụ nữa nữa, trạm tiêu thụ PS sẽ kiểm tra
điều kiện NP – NC’ < N và sản xuất đến sản phẩm thứ (i-1+N), NP=i – 1 + N. Lúc này, tại
trạm sản xuất, giá trị của công tơ sự kiện là: NC’ = i – 1
Khi đó, ta có: NP – NC’ = (i – 1 + N) – (i – 1) = N và không thỏa mãn điều kiện đầu
NP – NC’ < N nên trạm PS không sản xuất nữa. Như vậy, khi trạm CS chưa tiêu thụ sản
phẩm thứ i thì trạm PS không thể sản xuất sản phẩm thứ (i+N), tức là P
i+N
không thể có
trước C
i
. Khi trạm CS tiêu thụ sản phẩm thứ i C
i
, nó sẽ gửi một thông điệp cho trạm PS
SVTH: Nguyễn Thị Thúy Hoài Trang 20
Tiểu luận môn Hệ Phân Tán
thông vừa có một sản phẩm được tiêu thụ. Trạm PS sau khi nhận được thông điệp từ trạm
CS sẽ tăng giá trị của công tơ sự kiện NC’ thêm một đơn vị:
NC’ = NC’ + 1 = (i – 1) + 1 = i
Khi đó, tại trạm sản xuất ta có:
NP – NC’ = (i –1 + N) – i = N –1

điều kiện NP–NC’ < N được thỏa mãn và trạm PS có thể thực hiện sản xuất thứ (i+N).
Như vậy, tiêu thụ thứ i có trước sản xuất thứ i + N.
Như vậy, quan hệ sản xuất và tiêu thụ có quan hệ có trước như sau:
P
i
→ C
i
→ P
i+N
Quan hệ này có thể được biểu diễn như sau:
Thuật toán tại trạm sản xuất PS:
Vòng lặp
Nếu receive(CS)
tang(NC’)
cho(NC’,NP – N + 1)
san_xuat()
send(CS)
NP = NP + 1
Kết thúc vòng lặp
Thuật toán tại trạm tiêu thụ CS:
Vòng lặp
Nếu receive(PS)
tang(NP’)
cho(NP’,NP + 1)
tieu_thu()
send(PS)
NC = NC + 1
Kết thúc vòng lặp
SVTH: Nguyễn Thị Thúy Hoài Trang 21
P

1
C
1
P
2
C
2
P
i
C
i
P
i+N
C
i+1
P
i+N+1
P
i
: Sản xuất
thứ i
C
i
: Tiêu thụ
thứ i
Tiểu luận môn Hệ Phân Tán
SVTH: Nguyễn Thị Thúy Hoài Trang 22
Tiểu luận môn Hệ Phân Tán
KẾT LUẬN
Sau một thời gian tìm hiểu, nghiên cứu và đặc biệt là nhờ sự hướng dẫn, chỉ bảo tận

tình của thầy giáo PGS.TS Lê Văn Sơn nên tiểu luận đã hoàn thành đúng thời hạn. Qua
nghiên cứu đề tài này, kết quả đạt được là bài tiểu luận đã giới thiệu những kiến thức
chung cơ bản về đồng bộ hóa tiến trình. Tuy nhiên, phần lý thuyết và bài tập vẫn còn nhiều
thiếu sót
Trên cơ sở những điều làm được, ta có thể sẽ mở rộng và phát triển theo các hướng sau
đây:
• Nghiên cứu lý thuyết và các vấn đề liên quan đến đồng bộ hóa tiến trình.
• Tiếp tục phát triển và ứng dụng để giải quyết các vấn đề thực tiễn.
SVTH: Nguyễn Thị Thúy Hoài Trang 23
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.
[2] Các tài liệu tham khảo trên internet.
[3] giáo trình hệ điều hành – ThS. Nguyễn Phú Trường, khoa Công nghệ Thông
tin Đại học Cần Thơ
[4] Distributed Systems (Concepts and Design) – George Coulouris, Jean
Dollimore và Tim Kindberg.
[5] Advances in Distributed and Parallel Knowledge Discovery – Hillol
Kargupta và Philip Chan.
SVTH: Nguyễn Thị Thúy Hoài Trang 24