Bài giảng Hệ điều hành (Operating Systems) - Hà Lê Hoài Trung - Chương 5: Phần 2 Đồng bộ và giải quyết tranh chấp (Process Synchronization)

i trước, sau đó 
mới đến đũa bên phải, trong khi đó triết gia ở vị trí 
chẵn cầm đũa bên phải trước, sau đó mới đến đũa 
bên trái 
 Starvation? 
50 Khoa KTMT 
Bài toán Readers-Writers (1) 
Readers - Writers 
 W khơng được cập nhật dữ liệu khi cĩ 
 một R đang truy xuất CSDL . 
 Tại một thời điểm , chỉ cho phép một W được 
 sửa đổi nội dung CSDL. 
Database 
R1 
R2 
R3 
W1 W2 
51 Khoa KTMT 
Bài toán Readers-Writers (2) 
 Bộ đọc trước bộ ghi (first 
reader-writer) 
 Dữ liệu chia sẻ 
 semaphore mutex = 1; 
 semaphore wrt = 1; 
 int readcount = 0; 
 Writer process 
 wait(wrt); 
 ... 
 writing is performed 
 ... 
 signal(wrt); 
 Reader Process 
 wait(mutex); 
 readcount++; 
 if (readcount == 1) 
 wait(wrt); 
 signal(mutex); 
 ... 
 reading is performed 
 ... 
 wait(mutex); 
 readcount--; 
 if (readcount == 0) 
 signal(wrt); 
 signal(mutex); 
52 Khoa KTMT 
Bài toán Readers-Writers (3) 
 mutex: “bảo vệ” biến readcount 
 wrt 
‟ Bảo đảm mutual exclusion đối với các writer 
‟ Được sử dụng bởi reader đầu tiên hoặc cuối cùng 
vào hay ra khỏi vùng tranh chấp. 
 Nếu một writer đang ở trong CS và có n reader 
đang đợi thì một reader được xếp trong hàng 
đợi của wrt và n 1 reader kia trong hàng đợi 
của mutex 
 Khi writer thực thi signal(wrt), hệ thống có thể 
phục hồi thực thi của một trong các reader đang 
đợi hoặc writer đang đợi. 
53 Khoa KTMT 
Các vấn đề với semaphore 
 Semaphore cung cấp một công cụ mạnh mẽ để bảo 
đảm mutual exclusion và phối hợp đồng bộ các process 
 Tuy nhiên, nếu các tác vụ wait(S) và signal(S) nằm rải 
rác ở rất nhiều processes khó nắm bắt được hiệu ứng 
của các tác vụ này. Nếu không sử dụng đúng có thể 
xảy ra tình trạng deadlock hoặc starvation. 
 Một process bị “die” có thể kéo theo các process khác 
cùng sử dụng biến semaphore. 
signal(mutex) 
… 
critical section 
… 
wait(mutex) 
wait(mutex) 
… 
critical section 
… 
wait(mutex) 
signal(mutex) 
… 
critical section 
… 
signal(mutex) 
54 Khoa KTMT 
Critical Region (CR) 
 Là một cấu trúc ngôn ngữ cấp cao (high-level language construct, 
được dịch sang mã máy bởi một compiler), thuận tiện hơn cho người 
lập trình. 
 Một biến chia sẻ v kiểu dữ liệu T, khai báo như sau 
 v: shared T; 
 Biến chia sẻ v chỉ có thể được truy xuất qua phát biểu sau 
 region v when B do S; /* B là một biểu thức Boolean */ 
„ Ý nghĩa: trong khi S được thực thi, không có quá trình khác có thể 
truy xuất biến v. 
55 Khoa KTMT 
CR và bài toán bounded buffer 
Dữ liệu chia sẽ: 
struct buffer 
{ 
 int pool[n]; 
 int count, 
 in, 
 out; 
} 
region buffer when (count < n) { 
 pool[in] = nextp; 
 in = (in + 1) % n; 
 count++; 
} 
Producer 
region buffer when (count > 0){ 
 nextc = pool[out]; 
 out = (out + 1) % n; 
 count--; 
} 
Consumer 
56 Khoa KTMT 
Monitor (1) 
 Cũng là một cấu trúc ngôn ngữ cấp cao tương tự CR, có 
chức năng như semaphore nhưng dễ điều khiển hơn 
 Xuất hiện trong nhiều ngôn ngữ lập trình đồng thời như 
‟ Concurrent Pascal, Modula-3, Java,… 
 Có thể hiện thực bằng semaphore 
57 Khoa KTMT 
Monitor (2) 
 Là một module phần 
mềm, bao gồm 
‟ Một hoặc nhiều thủ tục 
(procedure) 
‟ Một đoạn code khởi tạo 
(initialization code) 
‟ Các biến dữ liệu cục bộ 
(local data variable) 
 Đặc tính của monitor 
‟ Local variable chỉ có thể 
truy xuất bởi các thủ tục 
của monitor 
‟ Process “vào monitor” bằng 
cách gọi một trong các thủ 
tục đó 
‟ Chỉ có một process có thể 
vào monitor tại một thời 
điểm mutual exclusion 
được bảo đảm 
shared data 
entry queue … 
operations 
initialization 
code 
Mô hình của một monitor 
đơn giản 
58 Khoa KTMT 
Cấu trúc của monitor 
 monitor monitor-name 
 { 
 shared variable declarations 
 procedure body P1 (…) { 
 . . . 
 } 
 procedure body P2 (…) { 
 . . . 
 } 
 procedure body Pn (…) { 
 . . . 
 } 
 { 
 initialization code 
 } 
 } 
59 Khoa KTMT 
Condition variable 
 Nhằm cho phép một process đợi “trong monitor”, phải 
khai báo biến điều kiện (condition variable) 
 condition a, b; 
 Các biến điều kiện đều cục bộ và chỉ được truy cập bên 
trong monitor. 
 Chỉ có thể thao tác lên biến điều kiện bằng hai thủ tục: 
‟ a.wait: process gọi tác vụ này sẽ bị “block trên biến điều kiện” a 
 process này chỉ có thể tiếp tục thực thi khi có process khác 
thực hiện tác vụ a.signal 
‟ a.signal: phục hồi quá trình thực thi của process bị block trên 
biến điều kiện a. 
 Nếu có nhiều process: chỉ chọn một 
 Nếu không có process: không có tác dụng 
60 Khoa KTMT 
Monitor có condition variable 
 Các process có thể đợi ở entry 
queue hoặc đợi ở các condition 
queue (a, b,…) 
 Khi thực hiện lệnh a.wait, 
process sẽ được chuyển vào 
condition queue a 
 Lệnh a.signal chuyển một 
process từ condition queue a 
vào monitor 
„ Khi đó, để bảo đảm mutual 
exclusion, process gọi a.signal 
sẽ bị blocked và được đưa vào 
urgent queue 
entry queue shared data 
... 
operations 
initialization 
code 
a 
b 
61 Khoa KTMT 
Monitor có condition variable (tt) 
local data 
condition variables 
procedure 1 
procedure k 
initialization code 
.
.
.
monitor waiting area entrance 
entry queue 
c1.wait 
condition c1 
condition cn 
cn.wait 
urgent queue 
cx.signal 
.
.
.
MONITOR 
exit 
62 Khoa KTMT 
Monitor và dining philosophers 
 monitor dp 
 { 
 enum {thinking, hungry, eating} state[5]; 
 condition self[5]; 
0 
1 
2 3 
4 
63 Khoa KTMT 
Dining philosophers (tt) 
 void pickup(int i) { 
 state[ i ] = hungry; 
 test( i ); 
 if (state[ i ] != eating) 
 self[ i ].wait(); 
 } 
 void putdown(int i) { 
 state[ i ] = thinking; 
 // test left and right neighbors 
 test((i + 4) % 5); // left neighbor 
 test((i + 1) % 5); // right … 
 } 
64 Khoa KTMT 
Dining philosophers (tt) 
 void test(int i) { 
 if ( (state[(i + 4) % 5] != eating) && 
 (state[ i ] == hungry) && 
 (state[(i + 1) % 5] != eating) ) { 
 state[ i ] = eating; 
 self[ i ].signal(); 
 } 
 void init() { 
 for (int i = 0; i < 5; i++) 
 state[ i ] = thinking; 
 } 
 } 
65 Khoa KTMT 
Dining philosophers (tt) 
 Trước khi ăn, mỗi triết gia phải gọi hàm pickup(), ăn 
xong rồi thì phải gọi hàm putdown() 
 dp.pickup(i); 
 ăn 
 dp.putdown(i); 
 Giải thuật không deadlock nhưng có thể gây 
starvation. 
66 Khoa KTMT 
Bài Tập 
Bài 1. Xét giải pháp đồng bộ hoá sau : 
while (TRUE) { 
int j = 1-i; 
flag[i]= TRUE; turn = j; 
while (turn == j && flag[j]==TRUE); 
critical-section (); 
flag[j] = FALSE; 
 Noncritical-section (); 
} 
 Đây có phải là một giải pháp bảo đảm 3 điều kiện không ? 
67 Khoa KTMT 
Bài tập 
Bài 1 : Xét giải pháp phần mềm do Dekker đề nghị để tổ chức truy xất độc 
quyền cho hai tiến trình . Hai tiến trình P0, P1 chia sẻ các biến sau : 
var flag : array [0..1] of boolean; (khởi động là false) 
 turn : 0..1; 
Cấu trúc một tiến trình Pi ( i =0 hay 1, và j là tiến trình còn lại ) như 
sau : 
repeat 
flag[i] := true; 
while flag[j] do 
if turn = j then 
 begin flag[i]:= false; 
 while turn = j do ; 
 flag[i]:= true; 
 end; 
 critical_section(); 
turn:= j; 
flag[i]:= false; 
non_critical_section(); 
until false; 
Giải pháp này có phải là một giải pháp đúng thỏa mãn 4 yêu cầu 
không ? 
68 Khoa KTMT 
Bài tập 
Giả sử một máy tính không có chỉ thị TSL, nhưng có chỉ thị Swap có khả năng 
hoán đổi nội dung của hai từ nhớ chỉ bằng một thao tác không thể phân 
chia : 
procedure Swap() var a,b: boolean); 
var temp : boolean; 
begin 
 temp := a; 
 a:= b; 
 b:= temp; 
end; 
Sử dụng chỉ thị này có thể tổ chức truy xuất độc quyền không ? Nếu có, xây 
dựng cấu trúc chương trình tương ứng 
69 Khoa KTMT 
Bài tập – semanphore 
Xét hai tiến trình xử lý đoạn chương trình sau : 
process P1 { A1 ; A2 } process P2 { B1 ; B2 } 
Đồng bộ hoá hoạt động của hai tiến trình này sao cho cả A1 và 
B1 đều hoàn tất trước khi A2 hay B2 bắt đầu . 
70 Khoa KTMT 
Bài tập – semanphore 
Sử dụng semaphore để viết lại chương trình sau theo mơ hình xử lý 
đồng hành: 
 A = x1 + x2; B = A*x3; C= A + x4; D= B + C; E = D*x5 + C; 
Giả sử cĩ 5 process mỗi process sẽ thực hiện 1 biểu thức. 
71 Khoa KTMT 
Bài tập – semanphore 
 Xét hai tiến trình sau : 
process A { while (TRUE) na = na +1; } 
 process B { while (TRUE) nb = nb +1; } 
‟ Đồng bộ hoá xử lý của hai tiến trình trên, sử dụng hai 
semaphore tổng quát, sao cho tại bất kỳ thời điểm nào cũng có 
nb < na <= nb +10 
‟ Nếu giảm điều kiện chỉ là na <= nb +10, giải pháp của bạn sẽ 
được sửa chữa như thế nào ? 
72 Khoa KTMT 
Bài tập – semanphore 
Một biến X được chia sẻ bởi hai tiến trình cùng thực hiện đoạn 
code sau : 
do 
 X = X +1; 
 if ( X == 20) X = 0; 
while ( TRUE ); 
Bắt đầu với giá trị X = 0, chứng tỏ rằng giá trị X có thể vượt quá 
20. Cần sửa chữa đoạn chương trình trên như thế nào để bảo 
đảm X không vượt quá 20 ? 
73 Khoa KTMT 
Bài tập – semanphore 
Tổng quát hoá câu hỏi 8) cho các tiến trình xử lý đoạn chương 
trình sau : 
process P1 { for ( i = 1; i <= 100; i ++) Ai } 
process P2 { for ( j = 1; j <= 100; j ++) Bj } 
Đồng bộ hoá hoạt động của hai tiến trình này sao cho cả với k 
bất kỳ ( 2 k 100), Ak chỉ có thể bắt đầu khi B(k-1) đã kết thúc, 
và Bk chỉ có thể bắt đầu khi A(k-1) đã kết thúc.