Bài giảng Hệ điều hành - Chương 5, Phần 3: Đồng bộ - Trần Thị Như Nguyệt

re cải tiến, không busy 
 waiting như sau: 
 Hàm wait() và signal() được hiện thực như sau: 
 void wait(semaphore *S) { 
 S.value--; Lập trình thực tế, tùy 
 if (S.value < 0) { từng ngôn ngữ, có thể 
 là: 
 add this process to S.L; S.value hoặc 
 block(); S value 
 } 
 } 
 void signal(semaphore *S) { 
 S.value++; 
 if (S.value <= 0) { 
 remove a process P from S.L; 
 wakeup(P); 
 } 
 } Đồng bộ 
 8 
 Semaphore 
 Hàm wait và signal của Semaphore cải tiến, không busy 
 waiting như sau: 
 Khi hàm wait() được gọi, ngay lập tức giá trị value của 
 Semaphore S bị giảm đi 1. Và nếu giá trị Semaphore S âm, 
 process này sẽ bị đưa vào danh sách L (đưa vào hàng đợi 
 Semaphore) và bị khóa (block) lại. 
 Khi hàm signal() được gọi, ngay lập tức giá trị value của 
 Semaphore S tăng lên 1. Và nếu giá trị Semaphore lớn hơn 
 hoặc bằng 0, một process sẽ được chọn lựa trong danh sách L, 
 tức trong hàng đợi Semaphore và bị đánh thức dậy (wakeup) để 
 ra hàng đợi ready và chờ CPU để thực hiện. 
Lưu ý: Trong hiện thực, các PCB của các process bị block sẽ được 
đưa vào danh sách L. Danh sách L có thể dùng hàng đợi FIFO 
hoặc cấu trúc khác tùy thuộc vào yêu cầu hệ thống. 
 Đồng bộ 
 9 
 Semaphore 
 Hàm wait và signal của Semaphore cải tiến, không busy 
 waiting như sau: 
 Block() và Wakeup() là hai system calls của hệ điều hành. 
  block(): Process này đang thực thi lệnh này sẽ bị khóa lại. 
 Process chuyển từ Running sang Waiting 
  wakeup(P): hồi phục quá trình thực thi của process P đang bị 
 blocked 
 Process P chuyển thừ Waiting sang Ready 
 Đồng bộ 
 10 
 Ví dụ sử dụng semaphore (1) 
Ví dụ 1: Shared data: 
Dùng semaphore giải quyết semaphore mutex; 
n process truy xuất vào CS. (Khởi tạo mutex.value = 1) 
Có hai trường hợp: 
 Process Pi: 
 Chỉduy nhất một process do { 
 được vào CS (mutual wait(mutex); 
 exclusion) critical section 
 Khởi tạo S.value = 1 signal(mutex); 
 remainder section 
 } while (1); 
 Cho phép k process vào CS 
 Khởi tạo S.value = k 
 Đồng bộ 
 11 
 Ví dụ sử dụng semaphore (2) 
Ví dụ 2: Process P1: 
Dùng Semaphore giải quyết S1; 
đồng bộ giữa hai process signal(synch); 
Yêu cầu: 
Cho hai process: P1 và P2 Process P2: 
P1 thực hiện lệnh S1 vàP 2 thực wait(synch); 
hiện lệnh S2. S2; 
Lệnh S2 chỉ được thực thi sau khi 
lệnh S1 được thực thi. 
Khởi tao semaphore tên synch 
và 
 synch.value = 0 
 Đồng bộ 
 12 
 Ví dụ sử dụng semaphore (3) 
Ví dụ 3: Process P1: 
Dùng Semaphore giải quyết A1; 
đồng bộ giữa hai process signal(s1);, 
Yêu cầu: wait(s2); 
Xét 2 tiến trình xử lý đoạn A2; 
chương trình sau: 
 Process P2: 
• Tiến trình P1 {A1, A2} 
• Tiến trình P2 {B1, B2} B1 
Đồng bộ hóa hoạt động của 2 tiến signal(s2); 
trình sao cho cả A1 và B1 đều wait(s1); 
hoàn tất trước khi A2 và B2 bắt B2; 
đầu. 
Khởi tạo 2 Semaphore s1 và s2 
 s1.value = s2.value = 0 
 Đồng bộ 
 13 
 Nhận xét 
 Khi S.value ≥ 0: value chính là số process có thể 
 thực thi wait(S) mà không bị blocked 
 Khi S.value < 0: trị tuyệt đối của value chính là số 
 process đang đợi trên hàng đợi semaphore 
 Đồng bộ 
 14 
 Nhận xét (tt) 
 Việc hiện thực Semaphore phải đảm bảo tính chất Atomic và 
mutual exclusion: tức không được xảy ra trường hợp 2 process 
cùng đang ở trong thân lệnh wait(S) và signal(S) (cùng semaphore 
S) tại một thời điểm (ngay cả với hệ thống multiprocessor) 
⇒ do đó, đoạn mã định nghĩa các lệnh wait(S) và signal(S) cũng 
chính là vùng tranh chấp 
 Giải pháp cho vùng tranh chấp wait(S) và signal(S): 
  Uniprocessor: có thể dùng cơ chế cấm ngắt (disable 
 interrupt). Nhưng phương pháp này không hiệu quả trên hệ 
 thống multiprocessor. 
  Multiprocessor: có thể dùng các giải pháp software (như giải 
 Peterson và Bakery) hoặc giải pháp hardware (TestAndSet, 
 Swap). 
 Vùng tranh chấp của các tác vụ wait(S) và signal(S) thông 
 thường rất nhỏ: khoảng 10 lệnh. 
 Vì CS rất nhỏ nên chi phí cho busy waiting sẽ rất thấp. 
 Đồng bộ 
 15 
 Deadlock và starvation 
 Deadlock: hai hay nhiều process đang chờ đợi vô hạn định một 
 sự kiện không bao giờ xảy ra. 
Ví dụ thường gặp nhất của deadlock là hai (hoặc nhiều) process đang 
chờ đợi qua lại các sự kiện của nhau thì mới được thực thi, nhưng cả hai 
process này đều đã bị block, nên sự kiện này không bao giờ xảy ra và hai 
process sẽ bị block vĩnh viễn. 
Ví dụ: Gọi S và Q là hai biến semaphore được khởi tạo = 1 
 P0 P1 
 wait(S); wait(Q); 
 wait(Q); wait(S); 
 signal(S); signal(Q); 
 signal(Q); signal(S); 
Ví dụ khởi tạo S.value và Q.value bằng 1. P0 đầu tiên thực thi wait(S), rồi 
P1 thực thi wait(Q), rồi P0 thực thi wait(Q) và bịblocked, tiếp theo P1 
thực thi wait(S) bịblocked. 
 Tình huống nà là P0 và P1 bị rơi vào deadlock. 
 Đồng bộ 
 16 
 Deadlock và starvation 
 Starvation (indefinite blocking): Trường hợp một tiến trình có 
 thể không bao giờ được lấy ra khỏi hàng đợi mà nó bị khóa/treo 
 (block) trong hàng đợi đó. 
 Đồng bộ 
 17 
 Các loại semaphore 
 Counting semaphore: một sốnguyên có giá trị 
 không hạn chế. 
 Binary semaphore: có trị là 0 hay 1. Binary 
 semaphore rất dễ hiện thực. 
 Đồng bộ 
 18 
 Các bài toán đồng bộ kinh điển 
Ba bài toán đồng bộ kinh điển: 
 Bounded-Buffer Problem 
 Dining-Philosophers Problem 
 Readers and Writers Problem 
 Đồng bộ 
 19 
 Bài toán Bounded-Buffer 
Producer sản suất một sản phẩm và đặt vào buffers, 
buffers giới hạn chỉ chứa được n sản phẩm. 
Consumer tiêu thụ mỗi lần một sản phẩm, sản phẩm được 
lấy ra từ buffers. 
Khi buffers đã chứa n sản phẩm, Producer không thể đưa 
tiếp sản phẩm vào buffers nữa mà phải chờ đến khi buffers 
có chỗ trống. Khi buffers rỗng, Consumer không thể lấy sản 
phẩm để tiêu thụ mà phải chờ đến khi có ít nhất 1 sản 
phẩm vào buffers. 
 Đồng bộ 
 20 
 Bài toán Bounded-Buffer 
Để hiện thực bài toán trên, các biên chia sẻ giữa Producer và Consumer 
như sau: 
 int n; 
 semaphore mutex = 1; 
 semaphore empty = n; 
 semaphore full = 0; 
. Buffers có n chỗ (n buffer con/vị trí) để chứa sản phẩm 
. Biến semaphore mutex cung cấp khả năng mutual exclusion cho việc truy xuất 
 tới buffers. Biến mutex được khởi tạo bằng 1 (tức value của mutex bằng 1). 
. Biến semaphore empty và full đếm số buffer rỗng và đầy trong buffers. 
. Lúc đầu, toàn bộ buffers chưa có sản phẩm nào được đưa vào: value của empty 
 được khởi tạo bằng n; và value của full được khởi tạo bằng 0 
 n buffers 
 out 
 Đồng bộ 
 21 
 Bài toán bounder buffer 
 producer consumer 
do { do { 
  wait(full) 
 nextp = new_item(); wait(mutex); 
 wait(empty); nextc = get_buffer_item(out); 
 wait(mutex);  
  signal(mutex); 
 insert_to_buffer(nextp); signal(empty); 
 signal(mutex); consume_item(nextc); 
 signal(full);  
} while (1); } while (1); 
 Đồng bộ 
 22 
 Bài toán “Dining Philosophers” 
 Bài toán 5 triết gia ăn tối: 
5 triết gia ngồi vào bàn tròn với một đĩa thức 
ăn ở giữa và chỉ với 5 chiếc đũa đơn được đặt 
như hình. Khi một triết gia suy nghĩ, sẽ không 
tương tác với các triết gia khác. Sau một 
khoảng thời gian, khi triết gia đói, sẽ phải cần 
lấy 2 chiếc đũa gần nhất để ăn. Tại một thời 
điểm, triết gia chỉ có thấy lấy 1 chiếc đũa 
(không thể lấy đũa mà triết gia khác đã cầm). 
Khi triết gia có 2 chiếc đũa, sẽ lập tức ăn và 
chỉ bỏ 2 đũa xuống khi nào ăn xong. Sau đó 
triết gia lại tiếp tục suy nghĩ. 
 Đây là một bài toán kinh điển trong việc 
minh họa sự khó khăn trong việc phân phối tài 
nguyên giữa các process sao cho không xảy ra 
deadlock và starvation 
 Đồng bộ 
 23 
 Bài toán “Dining Philosophers” (tt) 
 Dữ liệu chia sẻ: 
 Semaphore chopstick[5] 
 Khởi tạo các biến đều là 1 
 Đồng bộ 
 24 
Bài toán “Dining Philosophers” (tt) 
 Triết gia thứ i: 
 do { 
 wait(chopstick [ i ]) 
 wait(chopstick [ (i + 1) % 5 ]) 
 eat 
 signal(chopstick [ i ]); 
 signal(chopstick [ (i + 1) % 5 ]); 
 think 
 } while (1); 
 Đồng bộ 
 25 
 Bài toán “Dining Philosophers” (tt) 
 Giải pháp trên có thể gây ra deadlock 
  Khi tất cả triết gia đói bụng cùng lúc và đồng thời cầm 
 chiếc đũa bên tay trái ⇒ deadlock 
 Một số giải pháp khác giải quyết được deadlock 
  Cho phép nhiều nhất 4 triết gia ngồi vào cùng một lúc 
  Cho phép triết gia cầm các đũa chỉ khi cả hai chiếc đũa đều 
 sẵn sàng (nghĩa là tác vụ cầm các đũa phải xảy ra trong 
 CS) 
  Đánh số các triết gia từ 0 tới 4. Triết gia ngồi ở vị trí lẻ 
 cầm đũa bên trá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? 
 Đồng bộ 
 26 
 Bài toán Reader-Writers 
 Có một database hoặc file, nhiều Readers (để đọc) và 
 nhiều Writers (để ghi) dữ liệu vào database. 
 Khi một Writer đang truy cập database/file thì không một 
 quá trình nào khác được truy cập. 
 Nhiều Readers có thể cùng lúc đọc database/file 
 R2 
 R3 
 R1 
 W1 W2 
 Database 
 Đồng bộ 
 27 
 Bài toán Reader-Writers (tt) 
 Bộ đọc trước bộ ghi (first  Reader process 
 reader-writer) wait(mutex); 
 Dữ liệu chia sẻ readcount++; 
 if (readcount == 1) 
 semaphore mutex = 1; wait(wrt); 
 semaphore wrt = 1; signal(mutex); 
 int readcount = 0; ... 
 reading is performed 
 Writer process ... 
 wait(wrt); wait(mutex); 
 ... readcount--; 
 if (readcount == 0) 
 writing is performed signal(wrt); 
 ... signal(mutex); 
 signal(wrt); 
 Đồng bộ 
 28 
 Bài toán Reader-Writers (tt) 
 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. 
 Đồng bộ 
 29 
 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) wait(mutex) signal(mutex) 
 critical section critical section critical section 
 wait(mutex) wait(mutex) signal(mutex) 
 Các trường hợp sử dụng Semaphore có thể gây lỗi 
 Đồng bộ 
 30 
 Monitor 
 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 
 Đồng bộ 
 31 
 Monitor (tt) 
 Là một module phần mềm,  Đặc tính của monitor 
 bao gồm  Local variable chỉ có 
  Một hoặc nhiều thủ tục thể truy xuất bởi các 
 (procedure) thủ tục của monitor 
  Một đoạn code khởi tạo  Process “vào monitor” 
 (initialization code) bằng cách gọi một 
  Các biến dữ liệu cục bộ trong các thủ tục đó 
 (local data variable)  Chỉ có một process có 
 thể vào monitor tại một 
 shared data thời điểm ⇒ mutual 
  entry queue exclusion được bảo 
 operations đảm 
 initialization Mô hình của một monitor 
 code 
 đơn giản Đồng bộ 
 32 
 Cấu trúc của monitor 
monitor monitor-name{ 
 shared variable declarations 
 procedure body P1 () { 
 . . . 
 } 
 procedure body P2 () { 
 . . . 
 } 
 procedure body Pn () { 
 . . . 
 } 
 { 
 initialization code 
 } 
} 
 Đồng bộ 
 33 
 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 
 Đồng bộ 
 34 
 Monitor có condition variable 
 shared data entry queue 
a 
  Các process có thể đợi ở entry 
b 
 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 
 operations  Lệnh a.signal chuyển một 
 process từ condition queue a 
 vào monitor 
 initialization  Khi đó, để bảo đảm mutual 
 code exclusion, process gọi a.signal 
 sẽ bị blocked và được đưa vào 
 urgent queue Đồng bộ 
 35 
 Monitor có condition variable (tt) 
 entry queue 
monitor waiting area entrance 
 MONITOR 
 local data 
 condition c1 
 condition variables 
 c1.wait 
 procedure 1 
 ...
 condition cn 
 ...
 cn.wait procedure k 
 urgent queue initialization code 
 cx.signal exit 
 Đồng bộ 
 36 
 Monitor và dining philosophers 
 3 
Bài toán Dining Philosophers 2 
giải theo dùng Monitor: 
Để tránh deadlock, bài toán 
 4 
đưa thêm ràng buộc: 
Một triết gia chỉ có thể lấy đôi 
đũa để ăn trong trường hợp 2 
 1 
chiếc đũa hai bên đều đang 
 0 
sẵn sàng. 
 Đồng bộ 
 37 
 Cấu trúc một Monitor cho 
 bài toán Dining 
 Philosophers 
 Đồng bộ 
38 
 Dining philosophers (tt) 
enum {thinking, hungry, eating} state[5]; 
condition self[5]; 
 Đồng bộ 
 39 
 Dining philosophers (tt) 
void pickup(int i) { 
 state[ i ] = hungry; 
 test[ i ]; 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  
} 
 Đồng bộ 
 40 
 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; 
 } 
} 
 Đồng bộ 
 41 
 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. 
 Đồng bộ 
 42 
 Câu hỏi ôn tập và bài tập 
 Semaphore là gì? Nêu cách hoạt động của semaphore 
 và ứng dụng vào một bài toán đồng bộ? 
 Monitor là gì? Nêu cách hoạt động của monitor và 
 ứng dụng vào một bài toán đồng bộ? 
 Bài tập về nhà: các bài tập chương 5 trên moodle 
 Đồng bộ 
 43