Bài giảng Nguyên lý hệ điều hành - Nguyễn Hải Châu - Tuần 4: Đồng bộ hóa tiến trình

mutex: 1 (Chưa có tiến trình nào thực hiện đoạn
mã găng)
28
Bài toán vùng đệm có giới hạn
Tiến trình ghi P:
do {
wait(empty);
wait(mutex);
// Ghi một phần tử mới
// vào buffer
signal(mutex);
signal(full);
} while (TRUE);
Tiến trình đọc Q:
do {
wait(full);
wait(mutex);
// Đọc một phần tử ra
// khỏi buffer
signal(mutex);
signal(empty);
} while (TRUE);
29
Bài toán tiến trình đọc - ghi
z Thuật ngữ: the reader-writer problem
z Tình huống: Nhiều tiến trình cùng thao tác trên một cơ
sở dữ liệu trong đó
z Một vài tiến trình chỉ đọc dữ liệu (ký hiệu: reader)
z Một số tiến trình vừa đọc vừa ghi (ký hiệu: writer)
z Khi có đọc/ghi đồng thời của nhiều tiến trình trên cùng
một cơ sở dữ liệu, có 2 bài toán:
z Bài toán 1: reader không phải chờ, trừ khi writer đã được phép
ghi vào CSDL (hay các reader không loại trừ lẫn nhau khi đọc)
z Bài toán 2: Khi writer đã sẵn sàng ghi, nó sẽ được ghi trong 
thời gian sớm nhất (nói cách khác khi writer đã sẵn sàng, 
không cho phép các reader đọc dữ liệu) 30
Bài toán tiến trình đọc-ghi số 1
z Sử dụng các semaphore với giá trị khởi tạo: 
wrt (1), mutex (1)
z Sử dụng biến rcount (khởi tạo 0) để đếm số
lượng reader đang đọc dữ liệu
z wrt: Đảm bảo loại trừ lẫn nhau khi writer ghi
z mutex: Đảm bảo loại trữ lẫn nhau khi cập
nhật biến rcount
631
Bài toán tiến trình đọc-ghi số 1
z Tiến trình writer Pw:
do {
wait(wrt);
// Thao tác ghi đang được
// thực hiện
signal(wrt);
while (TRUE);
z Tiến trình reader Pr:
do {
wait(mutex);
rcount++;
if (rcount==1) wait(wrt);
signal(mutex);
// Thực hiện phép đọc
wait(mutex);
rcount--;
if (rcount==0) signal(wrt);
signal(mutex);
} while (TRUE); 32
Bữa ăn tối của các triết gia
z Thuật ngữ: the dining-
philosophers problem
z Có 5 triết gia, 5 chiếc
đũa, 5 bát cơm và một
âu cơm bố trí như hình
vẽ
z Đây là bài toán cổ điển
và là ví dụ minh họa
cho một lớp nhiều bài
toán tương tranh
(concurrency): Nhiều
tiến trình khai thác
nhiều tài nguyên chung
33
Bữa ăn tối của các triết gia
z Các triết gia chỉ làm 2 việc: Ăn và suy nghĩ
z Suy nghĩ: Không ảnh hưởng đến các triết gia khác, 
đũa, bát và âu cơm
z Để ăn: Mỗi triết gia phải có đủ 2 chiếc đũa gần nhất ở
bên phải và bên trái mình; chỉ được lấy 1 chiếc đũa
một lần và không được phép lấy đũa từ tay triết gia
khác
z Khi ăn xong: Triết gia bỏ cả hai chiếc đũa xuống bàn
và tiếp tục suy nghĩ
34
Giải pháp cho bài toán Bữa ăn...
z Biểu diễn 5 chiếc đũa qua 
mảng semaphore:
semaphore chopstick[5];
các semaphore được khởi tạo
giá trị 1
z Mã lệnh của triết gia như hình
bên
z Mã lệnh này có thể gây bế tắc
(deadlock) nếu cả 5 triết gia
đều lấy được 1 chiếc đũa và
chờ để lấy chiếc còn lại nhưng
không bao giờ lấy được!!
z Mã lệnh của triết gia i:
do {
wait(chopstick[i]);
wait(chopstick[(i+1)%5];
// Ăn...
signal(chopstick[i]);
signal(chopstick[(i+1)%5];
// Suy nghĩ...
} while (TRUE);
35
Một số giải pháp tránh bế tắc
z Chỉ cho phép nhiều nhất 4 triết gia đồng thời
lấy đũa, dẫn đến có ít nhất 1 triết gia lấy
được 2 chiếc đũa
z Chỉ cho phép lấy đũa khi cả hai chiếc đũa
bên phải và bên trái đều nằm trên bàn
z Sử dụng giải pháp bất đối xứng: Triết gia
mang số lẻ lấy chiếc đũa đầu tiên ở bên trái, 
sau đó chiếc đũa ở bên phải; triết gia mang
số chẵn lấy chiếc đũa đầu tiên ở bên phải, 
sau đó lấy chiếc đũa bên trái
36
Hạn chế của semaphore
z Mặc dù semaphore cho ta cơ chế đồng bộ
hóa tiện lợi song sử dụng semaphore không
đúng cách có thể dẫn đến bế tắc hoặc lỗi do 
trình tự thực hiện của các tiến trình
z Trong một số trường hợp: khó phát hiện bế
tắc hoặc lỗi do trình tự thực hiện khi sử dụng
semaphore không đúng cách
z Sử dụng không đúng cách gây ra bởi lỗi lập
trình hoặc do người lập trình không cộng tác
737
Ví dụ hạn chế của semaphore (1)
z Xét ví dụ về đoạn mã găng:
z Mã đúng:
...
wait(mutex);
// Đoạn mã găng
signal(mutex);
...
z Mã sai:
...
signal(mutex);
// Đoạn mã găng
wait(mutex);
...
z Đoạn mã sai này gây ra
vi phạm điều kiện loại
trữ lẫn nhau 38
Ví dụ hạn chế của semaphore (2)
z Xét ví dụ về đoạn mã găng:
z Mã đúng:
...
wait(mutex);
// Đoạn mã găng
signal(mutex);
...
z Mã sai:
...
wait(mutex);
// Đoạn mã găng
wait(mutex);
...
z Đoạn mã sai này gây ra
bế tắc
39
Ví dụ hạn chế của semaphore (3)
z Nếu người lập trình quên các toán tử wait() 
hoặc signal() trong trong các đoạn mã găng, 
hoặc cả hai thì có thể gây ra:
z Bế tắc
z Vi phạm điều kiện loại trừ lẫn nhau
40
z Tiến trình P1
...
wait(S);
wait(Q);
...
signal(S);
signal(Q);
z Tiến trình P2
...
wait(Q);
wait(S);
...
signal(Q);
signal(S);
Ví dụ hạn chế của semaphore (4)
z Hai tiến trình P1 và P2 đồng thời thực hiện sẽ
dẫn tới bế tắc
41
Cơ chế monitor
42
Thông tin tham khảo
z Per Brinch Hansen
(người Đan Mạch) là
người đầu tiên đưa ra
khái niệm và cài đặt
monitor năm 1972
z Monitor được sử dụng 
lần đầu tiên trong ngôn 
ngữ lập trình Concurrent 
Pascal Per Brinch Hansen
(1938-2007)
843
Monitor là gì?
z Thuật ngữ monitor: giám sát
z Định nghĩa không hình thức: Là một loại
construct trong ngôn ngữ bậc cao dùng để
phục vụ các thao tác đồng bộ hóa
z Monitor được nghiên cứu, phát triển để khắc
phục các hạn chế của semaphore như đã
nêu trên
44
Định nghĩa tổng quát
z Monitor là một cách tiếp cận để đồng bộ hóa 
các tác vụ trên máy tính khi phải sử dụng các 
tài nguyên chung. Monitor thường gồm có:
z Tập các procedure thao tác trên tài nguyên chung
z Khóa loại trừ lẫn nhau
z Các biến tương ứng với các tài nguyên chung
z Một số các giả định bất biến nhằm tránh các tình 
huống tương tranh
z Trong bài này: Nghiên cứu một loại cấu trúc 
monitor: Kiểu monitor (monitor type)
45
Monitor type
z Một kiểu (type) hoặc kiểu trừu tượng (abstract 
type) gồm có các dữ liệu private và các phương
thức public
z Monitor type được đặc trưng bởi tập các toán
tử của người sử dụng định nghĩa
z Monitor type có các biến xác định các trạng
thái; mã lệnh của các procedure thao tác trên
các biến này
46
Cấu trúc một monitor type
monitor tên_monitor {
// Khai báo các biến chung
procedure P1(...) { ...
}
procedure P2(...) { ...
}
...
procedure Pn(...) { ...
}
initialization_code (..) { ...
}
}
47
Minh họa cấu trúc monitor
48
Cách sử dụng monitor
z Monitor được cài đặt sao cho chỉ có một tiến
trình được hoạt động trong monitor (loại trừ
lẫn nhau). Người lập trình không cần viết mã
lệnh để đảm bảo điều này
z Monitor như định nghĩa trên chưa đủ mạnh
để xử lý mọi trường hợp đồng bộ hóa. Cần
thêm một số cơ chế “tailor-made” về đồng bộ
hóa
z Các trường hợp đồng bộ hóa “tailor-made”:
sử dụng kiểu condition.
949
Kiểu condition
z Khai báo:
condition x, y; // x, y là các biến kiểu condition
z Sử dụng kiểu condition: Chỉ có 2 toán tử là
wait và signal
z x.wait(): tiến trình gọi đến x.wait() sẽ được chuyển
sang trạng thái chờ (wait hoặc suspend)
z x.signal(): tiến trình gọi đến x.signal() sẽ khôi 
phục việc thực hiện (wakeup) một tiến trình đã gọi
đến x.wait()
50
Monitor có kiểu condition
51
Đặc điểm của x.signal()
z x.signal() chỉ đánh thức duy nhất một tiến
trình đang chờ
z Nếu không có tiến trình chờ, x.signal() không
có tác dụng gì
z x.signal() khác với signal trong semaphore cổ
điển: signal cổ điển luôn làm thay đổi trạng
thái (giá trị) của semaphore
52
Signal wait/continue
z Giả sử có hai tiến trình P và Q:
z Q gọi đến x.wait(), sau đó P gọi đến x.signal()
z Q được phép tiếp tục thực hiện (wakeup)
z Khi đó P phải vào trạng thái wait vì nếu ngược
lại thì P và Q cùng thực hiện trong monitor
z Khả năng xảy ra:
z Signal-and-wait: P chờ đến khi Q rời monitor hoặc
chờ một điều kiện khác (*)
z Signal-and-continue: Q chờ đến khi P rời monitor 
hoặc chờ một điều kiện khác
53
Bài toán Ăn tối.. với monitor
z Giải quyết bài toán Ăn tối của các triết gia với
monitor để không xảy ra bế tắc khi hai triết gia ngồi
cạnh nhau cùng lấy đũa để ăn
z Trạng thái của các triết gia:
enum {thinking, hungry, eating} state[5];
z Triết gia i chỉ có thể ăn nếu cả hai người ngồi cạnh
ông ta không ăn:
(state[(i+4)%5]!=eating) and (state[(i+1)%5]!=eating)
z Khi triết gia i không đủ điều kiện để ăn: cần có biến
condition: condition self[5];
54
Monitor của bài toán Ăn tối... 
monitor dp {
enum {thinking, hungry, eating} state[5];
condition self[5];
void pickup(int i) {
state[i] = hungry;
test(i);
if (state[i] != eating) self[i].wait();
}
}
10
55
Monitor của bài toán Ăn tối...
void putdown(int i) {
state[i] = thinking;
test((i+4)%5);
test((i+1)%5);
}
initialization_code() {
for (int i=0;i<5;i++) state[i] = thinking;
}
56
Monitor của bài toán Ăn tối...
void test(int i) {
if ((state[(i+4)%5] != eating) &&
(state[i] == hungry) &&
(state[(i+1)%5] != eating)) {
state[i] = eating;
self[i].signal();
}
}
57
Đọc thêm ở nhà
z Khái niệm về miền găng (critical region)
z Cơ chế monitor của Java:
public class XYZ {
...
public synchronized void safeMethod() {
...
}
}
z Toán tử wait() và notify() trong java.util.package
(tương tự toán tử wait() và signal())
z Cách cài đặt monitor bằng semaphore 58
Tóm tắt
z Khái niệm đồng bộ hóa
z Khái niệm đoạn mã găng, ba điều kiện của
đoạn mã găng
z Khái niệm semaphore, semaphore nhị phân
z Hiện tượng bế tắc do sử dụng sai semaphore
z Một số bài toán cổ điển trong đồng bộ hóa
z Miền găng
z Cơ chế monitor
59
Bài tập
z Chỉ ra điều kiện nào của đoạn mã găng bị vi 
phạm trong đoạn mã găng sau của Pi:
do {
while (turn != i) ;
CSi;
turn = j;
REMAINi;
} while (1);
60
Bài tập
z Cài đặt giải pháp cho bài toán Bữa ăn tối của 
các triết gia trong Java bằng cách sử dụng 
synchronized, wait() và notify()
z Giải pháp monitor cho bài toán Bữa ăn tối... 
tránh được bế tắc, nhưng có thể xảy ra 
trường hợp tất cả các triết gia đều không 
được ăn. Hãy chỉ ra trường hợp này và tìm 
cách giải quyết bằng cơ chế monitor
z Chú ý: Sinh viên cần làm bài tập để hiểu tốt 
hơn về đồng bộ hóa