Giáo trình Hệ điều hành - Chương 5: Đồng bộ hóa quá trình - Nguyễn Phú Trường

hất bại. 
Mặc dù việc xem xét này có thể cho hệ thống nhỏ, tĩnh nhưng nó không phù hợp 
cho một hệ thống lớn hay động. Vấn đề kiểm soát truy xuất có thể được giải quyết chỉ 
bởi một cơ chế bổ sung khác. 
VI Các bài toán đồng bộ hoá nguyên thuỷ 
Trong phần này, chúng ta trình bày một số bài toán đồng bộ hoá như những thí 
dụ về sự phân cấp lớn các vấn đề điều khiển đồng hành. Các vấn đề này được dùng 
cho việc kiểm tra mọi cơ chế đồng bộ hoá được đề nghị gần đây. Semaphore được 
dùng cho việc đồng bộ hoá trong các giải pháp dưới đây. 
VI.1 Bài toán người sản xuất-người tiêu thụ 
Bài toán người sản xuất-người tiêu thụ (Producer-Consumer) thường được 
dùng để hiển thị sức mạnh của các hàm cơ sở đồng bộ hoá. Hai quá trình cùng chia sẻ 
một vùng đệm có kích thước giới hạn n. Biến semaphore mutex cung cấp sự loại trừ 
hỗ tương để truy xuất vùng đệm và được khởi tạo với giá trị 1. Các biến semaphore 
empty và full đếm số khe trống và đầy tương ứng. Biến semaphore empty được khởi 
tạo tới giá trị n; biến semaphore full được khởi tạo tới giá trị 0. 
Mã cho người quá trình sản xuất được hiển thị trong hình V.-18: 
do{ 
 sản xuất sản phẩm trong nextp 
 wait(empty); 
 wait(mutex); 
 thêm nextp tới vùng đệm 
 signal(mutex); 
 signal(full); 
} while (1); 
Hình 0-18 Cấu trúc của quá trình người sản xuất 
Mã cho quá trình người tiêu thụ được hiển thị trong hình dưới đây: 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 
101
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
do{ 
 wait(full); 
 wait(mutex); 
 lấy một sản phẩm từ vùng đệm tới nextc 
 signal(mutex); 
 signal(empty); 
} while (1); 
Hình 0-19 Cấu trúc của quá trình người tiêu thụ 
VI.2 Bài toán bộ đọc-bộ ghi 
Bộ đọc-bộ ghi (Readers-Writers) là một đối tượng dữ liệu (như một tập tin hay 
mẫu tin) được chia sẻ giữa nhiều quá trình đồng hành. Một số trong các quá trình có 
thể chỉ cần đọc nội dung của đối tượng được chia sẻ, ngược lại một vài quá trình khác 
cần cập nhật (nghĩa là đọc và ghi ) trên đối tượng được chia sẻ. Chúng ta phân biệt sự 
khác nhau giữa hai loại quá trình này bằng cách gọi các quá trình chỉ đọc là bộ đọc và 
các quá trình cần cập nhật là bộ ghi. Chú ý, nếu hai bộ đọc truy xuất đối tượng được 
chia sẻ cùng một lúc sẽ không có ảnh hưởng gì. Tuy nhiên, nếu một bộ ghi và vài quá 
trình khác (có thể là bộ đọc hay bộ ghi) truy xuất cùng một lúc có thể dẫn đến sự hỗn 
độn. 
Để đảm bảo những khó khăn này không phát sinh, chúng ta yêu cầu các bộ ghi 
có truy xuất loại trừ lẫn nhau tới đối tượng chia sẻ. Việc đồng bộ hoá này được gọi là 
bài toán bộ đọc-bộ ghi. Bài toán bộ đọc-bộ ghi có một số biến dạng liên quan đến độ 
ưu tiên. Dạng đơn giản nhất là bài toán bộ đọc trước-bộ ghi (first reader-writer). 
Trong dạng này yêu cầu không có bộ đọc nào phải chờ ngoại trừ có một bộ ghi đã 
được cấp quyền sử dụng đối tượng chia sẻ. Nói cách khác, không có bộ đọc nào phải 
chờ các bộ đọc khác để hoàn thành đơn giản vì một bộ ghi đang chờ. Bài toán bộ đọc 
sau-bộ ghi (second readers-writers) yêu cầu một khi bộ ghi đang sẳn sàng, bộ ghi đó 
thực hiện việc ghi của nó sớm nhất có thể. Nói một cách khác, nếu bộ ghi đang chờ 
truy xuất đối tượng, không có bộ đọc nào có thể bắt đầu việc đọc. 
Giải pháp cho bài toán này có thể dẫn đến việc đói tài nguyên. Trong trường 
hợp đầu, các bộ ghi có thể bị đói; trong trường hợp thứ hai các bộ đọc có thể bị đói. 
Trong giải pháp cho bài toán bộ đọc trước-bộ ghi, các quá trình bộ đọc chia sẻ các cấu 
trúc dữ liệu sau: 
 semaphore mutex, wrt; 
 int readcount; 
Biến semaphore mutex và wrt được khởi tạo 1; biến readcount được khởi tạo 
0. Biến semaphore wrt dùng chung cho cả hai quá trình bộ đọc và bộ ghi. Biến 
semaphore mutex được dùng để đảm bảo loại trừ hỗ tương khi biến readcount được 
cập nhật. Biến readcount ghi vết có bao nhiêu quá trình hiện hành đang đọc đối 
tượng. Biến semaphore wrt thực hiện chức năng như một biến semaphore loại trừ hỗ 
tương cho các bộ đọc. Nó cũng được dùng bởi bộ đọc đầu tiên hay bộ đọc cuối cùng 
mà nó đi vào hay thoát khỏi miền tương trục. Nó cũng không được dùng bởi các bộ 
đọc mà nó đi vào hay thoát trong khi các bộ đọc khác đang ở trong miền tương trục. 
Mã cho quá trình bộ viết được hiển thị như hình V.-20: 
 wait(wrt); 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 
102
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
 Thao tác viết được thực hiện 
 signal(wrt); 
Hình 0-20 Cấu trúc của quá trình viết 
Mã của quá trình đọc được hiển thị như hình V.-21: 
 wait(mutex); 
 readcount++; 
 if (readcount == 1) 
 wait(wrt); 
 signal(mutex); 
 Thao tác đọc được thực hiện 
 wait(mutex); 
 readcount--; 
 if (readcount == 0) 
 signal(wrt); 
 signal(mutex); 
Hình 0-21 Cấu trúc của bộ đọc 
Chú ý rằng, nếu bộ viết đang ở trong miền tương trục và n bộ đọc đang chờ thì 
một bộ đọc được xếp hàng trên wrt, và n-1 được xếp hàng trên mutex. Cũng cần chú ý 
thêm, khi một bộ viết thực thi signal(wrt) thì chúng ta có thể thực thi tiếp việc thực thi 
của các quá trình đọc đang chờ hay một quá trình viết đang chờ. Việc chọn lựa này có 
thể được thực hiện bởi bộ định thời biểu. 
VI.3 Bài toán các triết gia ăn tối 
Có năm nhà triết gia, vừa suy nghĩ vừa ăn tối. Các triết gia ngồi trên cùng một 
bàn tròn xung quanh có năm chiếc ghế, mỗi chiếc ghế được ngồi bởi một triết gia. 
Chính giữa bàn là một bát cơm và năm chiếc đũa được hiển thị như hình VI-22: 
VII 
VIII 
IX 
X 
XI 
XII 
Hình 0-22 Tình huống các triết gia ăn tối 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 
103
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
Khi một triết gia suy nghĩ, ông ta không giao tiếp với các triết gia khác. Thỉnh 
thoảng, một triết gia cảm thấy đói và cố gắng chọn hai chiếc đũa gần nhất (hai chiếc 
đũa nằm giữa ông ta với hai láng giềng trái và phải). Một triết gia có thể lấy chỉ một 
chiếc đũa tại một thời điểm. Chú ý, ông ta không thể lấy chiếc đũa mà nó đang được 
dùng bởi người láng giềng. Khi một triết gia đói và có hai chiếc đũa cùng một lúc, 
ông ta ăn mà không đặt đũa xuống. Khi triết gia ăn xong, ông ta đặt đũa xuống và bắt 
đầu suy nghĩ tiếp. 
Bài toán các triết gia ăn tối được xem như một bài toán đồng bộ hoá kinh điển. 
Nó trình bày yêu cầu cấp phát nhiều tài nguyên giữa các quá trình trong cách tránh 
việc khoá chết và đói tài nguyên. 
Một giải pháp đơn giản là thể hiện mỗi chiếc đũa bởi một biến semaphore. 
Một triết gia cố gắng chiếm lấy một chiếc đũa bằng cách thực thi thao tác wait trên 
biến semaphore đó; triết gia đặt hai chiếc đũa xuống bằng cách thực thi thao tác signal 
trên các biến semaphore tương ứng. Do đó, dữ liệu được chia sẻ là: 
 semaphore chopstick[5]; 
ở đây tất cả các phần tử của chopstick được khởi tạo 1. Cấu trúc của philosopher i 
được hiển thị như hình dưới đây: 
do{ 
 wait(chopstick[ i ]); 
 wait(chopstick[ ( i + 1 ) % 5 ]); 
 ăn 
 signal(chopstick[ i ]); 
 signal(chopstick[ ( i + 1 ) % 5 ]); 
 suy nghĩ 
} while (1); 
Hình 0-23 Cấu trúc của triết gia thứ i 
Mặc dù giải pháp này đảm bảo rằng không có hai láng giềng nào đang ăn cùng 
một lúc nhưng nó có khả năng gây ra khoá chết. Giả sử rằng năm triết gia bị đói cùng 
một lúc và mỗi triết gia chiếm lấy chiếc đũa bên trái của ông ta. Bây giờ tất cả các 
phần tử chopstick sẽ là 0. Khi mỗi triết gia cố gắng dành lấy chiếc đũa bên phải, triết 
gia sẽ bị chờ mãi mãi. 
Nhiều giải pháp khả thi đối với vấn đề khoá chết được liệt kê tiếp theo. Giải pháp 
cho vấn đề các triết gia ăn tối mà nó đảm bảo không bị khoá chết. 
• Cho phép nhiều nhất bốn triết gia đang ngồi cùng một lúc trên bàn 
• Cho phép một triết gia lấy chiếc đũa của ông ta chỉ nếu cả hai chiếc đũa là 
sẳn dùng (để làm điều này ông ta phải lấy chúng trong miền tương trục). 
• Dùng một giải pháp bất đối xứng; nghĩa là một triết gia lẽ chọn đũa bên 
trái đầu tiên của ông ta và sau đó đũa bên phải, trái lại một triết gia chẳn 
chọn chiếc đũa bên phải và sau đó chiếc đũa bên phải của ông ta. 
Tóm lại, bất cứ một giải pháp nào thoả mãn đối với bài toán các triết gia ăn tối 
phải đảm bảo dựa trên khả năng một trong những triết gia sẽ đói chết. Giải pháp giải 
quyết việc khoá chết không cần thiết xoá đi khả năng đói tài nguyên. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 
104
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
XIII Tóm tắt 
Một tập hợp các quá trình tuần tự cộng tác chia sẻ dữ liệu, loại trừ hỗ tương 
phải được cung cấp. Một giải pháp đảm bảo rằng vùng tương trục của mã đang sử 
dụng chỉ bởi một quá trình hay một luồng tại một thời điểm. Các giải thuật khác tồn 
tại để giải quyết vấn đề miền tương trục, với giả thuyết rằng chỉ khoá bên trong việc 
lưu trữ là sẳn dùng. 
Sự bất lợi chủ yếu của các giải pháp được mã hoá bởi người dùng là tất cả 
chúng đều yêu cầu sự chờ đợi bận. Semaphore khắc phục sự bất lợi này. Semaphores 
có thể được dùng để giải quyết các vấn đề đồng bộ khác nhau và có thể được cài đặt 
hiệu quả, đặc biệt nếu phần cứng hỗ trợ các thao tác nguyên tử. 
Các bài toán đồng bộ khác (chẳng hạn như bài toán người sản xuất-người tiêu 
dùng, bài toán bộ đọc, bộ ghi và bài toán các triết gia ăn tối) là cực kỳ quan trọng vì 
chúng là thí dụ của phân lớp lớn các vấn đề điều khiển đồng hành. Vấn đề này được 
dùng để kiểm tra gần như mọi cơ chế đồng bộ được đề nghị gần đây. 
Hệ điều hành phải cung cấp phương tiện để đảm bảo chống lại lỗi thời gian. 
Nhiều cấu trúc dữ liệu được đề nghị để giải quyết các vấn đề này. Các vùng tương 
trục có thể được dùng để cài đặt loại trừ hỗ tương và các vấn đề đồng bộ an toàn và 
hiệu quả. Monitors cung cấp cơ chế đồng bộ cho việc chia sẻ các loại dữ liệu trừu 
tượng. Một biến điều kiện cung cấp một phương thức cho một thủ tục monitor khoá 
việc thực thi của nó cho đến khi nó được báo hiệu tiếp tục. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 
105