Bài giảng Hệ điều hành - Chương 5: Đồng bộ tiến trình - Hà Duy An

Nội dung text: Bài giảng Hệ điều hành - Chương 5: Đồng bộ tiến trình - Hà Duy An

1. Khoa Công Nghệ Thông Tin & Truyền Thông ĐạihọcCầnThơ Giảng viên: Hà Duy An
2. 1. Vấn đề miềntương trục 2. Giải pháp phầnmềm 3. Giải pháp phầncứng 4. Semaphores 5. Các bài toán đồng bộ hóa cổđiển 6. Monitors 10/29/20132 Chương 5: Đồng bộ hóa
3. • Các tiếntrìnhđượcthựcthiđồng thời o Có thể bị ngắttạibấtcứ vị trí nào • Các tiếntrìnhđồng thờitruycậplêndữ liệuchiasẻ→tình trạng không nhất quán dữ liệu (inconsistency). • Việc duy trì sự nhấtquándữ liệuyêucầu các cơ chếđểđảm bảosự thực thi một cách có thứ tự của các tiến trình có hợp tác với nhau. • Xét trường hợp: Bài toán Ngườisảnxuất–Ngườitiêuthụ (Producer – Consumer Problem) với vùng đệmcókíchthước giớihạn (bounded-buffer). 10/29/20134 Chương 5: Đồng bộ hóa
4. • Dữ liệuchiasẻ: #define BUFFER_SIZE 10 typedef struct { } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0; 10/29/20135 Chương 5: Đồng bộ hóa
5. while (true) { /* produce an item in next produced */ while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; counter++; } 10/29/20136 Chương 5: Đồng bộ hóa
6. while (true) { while (counter == 0) ; /* do nothing */ next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter ; /* consume the item in next consumed */ } 10/29/20137 Chương 5: Đồng bộ hóa
7. • counter++ có thể được cài đặt: register1 = counter register1 = register1 + 1 counter = register1 • Counter có thể được cài đặt: register2 = counter register2 = register2 - 1 counter = register2 • Xét sự thực thi đan xen nhau với “count = 5” là giá trị khởi tạo: S0: producer execute register1 = counter {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = counter {register2 = 5} S3: consumer execute register2 = register2 – 1 {register2 = 4} S4: producer execute counter = register1 {counter = 6 } S5: consumer execute counter = register2 {counter = 4} 10/29/20138 Chương 5: Đồng bộ hóa
8. • Nếucả hai producer và consumer cố gắng cậpnhật vùng đệm đồng thời, các phát biểu assembly có thể bị phủ lấp. • Sự phủ lấpphụ thuộc vào cách producer và consumer được định thời. • Tình trạng đua tranh (Race Condition): là tình trạng mà vài tiến trình cùng truy cậpvàthayđổilêndữ liệu đượcchiasẻ và giá trị cuối cùng củadữ liệuchiasẻ phụ thuộcvàotiếntrình nào hoàn thành cuối cùng. Để ngănchặn tình trạng đua tranh, các tiếntrìnhcạnh tranh phải được đồng bộ hóa. 10/29/20139 Chương 5: Đồng bộ hóa
9. • Xét hệ thống có n tiến trình {p0,p1, pn-1} • Mỗitiến trình có một đoạnmãlệnh đượcgọilàmiềntương trục (critical section): o Tiếntrìnhcóthể cậpnhật các dữ liệu dùng chung o Khi mộttiếntrìnhđang trong miềntương trục, thì không tiến trình nào khác đượcphépthực thi trong miềntương trụccủa chúng => Vấn đề miềntương trục (critical-section problem): thiếtkế giao thứcgiải quyếtvấn đề này 10/29/201310 Chương 5: Đồng bộ hóa
10. • Cấutrúctổng quát củatiến trình Pi là: • Mỗitiếntrìnhphảikiểm tra sự hợplệ trong phần entry section để đivào miềntương trục,tiếp theo sau khi vào miềntương trục tiến trình sẽ thựchiện thao tác thoát khỏimiền tương trục exit section,và tiếptụcthựcthiphầncòn lại remainder section 10/29/201311 Chương 5: Đồng bộ hóa
11. Giải pháp cho vấn đề miềntương trụcphảithỏa các yêu cầu: 1. Loạitrừ hỗ tương (Mutual Exclusion). NếutiếntrìnhPi đang thực thi trong miềntương trục, thì không có tiến trình nào khác có thể thực thi trong miềntương trụccủa chúng. 2. Tiếntriển (Progress). Nếu không có tiến trình nào đang thựcthi trong miềntương trụcvàtồntạivàitiếntrìnhmuốn đượcthựcthi trong miềntương trụccủa chúng, thì việclựachọnmộttiếntrình đượcvàomiềntương trụccủa nó không thể bị trì hoãn mãi được. 3. Chờđợihữuhạn(BoundedWait).Không có tiến trình nào phải chờđợivĩnh viễn để có thểđivàomiềntương trụccủa nó. • Hai hướng tiếpcậngiải quyếtvấn đề phụ thuộc vào nhân HĐH: o Non-preemptive kernel: không cho phép tiếntrìnhbị trưng dụng khi nó đang chạy ở chếđộnhân => vấn đề đượcgiảiquyết cho các cấutrúc dữ liệu trong nhân o Preemptive kernel: cho phép các tiếntrìnhbị trưng dụng khi đang chạy ở chếđộnhân 10/29/201312 Chương 5: Đồng bộ hóa
12. • Các biến chung: o boolean lock; khởi đầu lock = false; • Tiến trình Pi: do { while (lock) ; lock = true; critical section lock = false; remainder section } while (1); => Không giải quyết đượcvấn đề 10/29/201315 Chương 5: Đồng bộ hóa
13. • Các biến chung: o int turn; khởi đầu turn = 0 o turn = i ⇒Pi có thể bướcvàomiềntương trụccủanó • Tiến trình Pi do { while (turn != i) ; critical section turn = j; remainder section } while (1); => Không thõa điềukiện2 10/29/201316 Chương 5: Đồng bộ hóa
14. • Các biếnchiasẻ: o boolean flag[2]; khởi đầu flag[0] = flag[1] = false. o flag[i] = true ⇒Pi sẵnsàngbướcvàomiềntương trụccủanó • TiếntrìnhP1: do { flag[i] := true; while (flag[j]) ; critical section flag [i] = false; remainder section } while (1); => Không thỏamãnđiềukiện2 10/29/201317 Chương 5: Đồng bộ hóa
15. • Giải quyết đượcvấn đề miềntương trục(thỏamãncả 3 điều kiện) cho 2tiếntrình • Giả sử các lệnh load và store là nguyên tử (không thể bị ngắt) • Hai tiến trình chia sẽ hai biến: o int turn; o Boolean flag[2] • turn –chỉđịnh tiến trình nào được phép vào miềntương trục • flag – cho biếttiến trình nào đãsẵnsàngvàomiềntương trục o flag [i] = true ⇒Pi sẵnsàngbướcvàomiềntương trụccủanó 10/29/201318 Chương 5: Đồng bộ hóa
16. do { flag[i] = true; turn = j; while (flag[j] && turn == j); critical section flag[i] = false; remainder section } while (true); • Nhậnxét: 1. Loạitrừ hỗ tương được đảmbảo 2. Yêu cầutiếntriển đượcthỏamãn 3. Yêu cầuchờđợihữuhạn được đáp ứng 10/29/201319 Chương 5: Đồng bộ hóa
17. • Nhiềuhệ thống cung cấpphầncứng hỗ trợđồng bộ hóa • Tấtcả các giảiphápnàydựatrênýtưởng bảovệ miềntương trụcbằng "khóa" • Vô hiệuhóacácngắt: khi mộttiếntrìnhbắt đầuthựcthitrongmiềntương trục thì các ngắtbị vô hiệu hóa đếnkhitiến trình thoát khỏimiềntương trục o Cho phép tiến trình người dùng có khả năng vô hiệu các ngắt=>cóthể tác động xấu đếnsự vậnhànhhệ thống o Không giải quyết đượcvấn đề trên hệ thống đaxử lý • Các hệ thống máy tính hiện đạicungcấp các thao tác nguyên tử (atomic hardware instructions): o test_and_set o compare_and_swap • Nếu các lệnh có tính chất nguyên tử thực thi cùng lúc thì thứ tự thựchiện của chúng luôn được đảmbảo–mộtlệnh được hoàn thành trướckhilệnh khác đượcthựcthi o Atomic = non-interruptible 10/29/201321 Chương 5: Đồng bộ hóa
18. • Lệnh test_and_set đọcvàsửa đổinội dung củamột word một cách nguyên tử: boolean test_and_set(boolean *target) { boolean rv = *target; *target = true; return rv; } 10/29/201322 Chương 5: Đồng bộ hóa
19. • Dữ liệuchiasẻ: boolean lock = false; • Tiến trình Pi: do { while (Test_And_Set(lock)) ; /* do nothing */ /* critical section */ lock = false; /* remainder section */ } while(1); =>không thỏa mãn yêu cầu chờ đợi hữu hạn 10/29/201323 Chương 5: Đồng bộ hóa
20. • Tựđộng hoán chuyển (swap) hai biến: int compare_and_swap(int *value,int expected,int new value){ int temp = *value; if (*value == expected) *value = new value; return temp; } 10/29/201324 Chương 5: Đồng bộ hóa
21. • Dữ liệuchiasẻ (khởitạolàfalse): boolean lock; • Tiến trình Pi do { while (compare_and_swap(&lock, 0, 1) != 0) ; /* do nothing */ /* critical section */ lock = 0; /* remainder section */ } while (true); =>không thỏa mãn yêu cầu chờ đợi hữu hạn 10/29/201325 Chương 5: Đồng bộ hóa
22. • Dữ liệuchiasẻ (khởitạo false): boolean lock; boolean waiting[n]; • TiếntrìnhPi: do { waiting[i] = true; key = true; while (waiting[i] && key) key = test_and_set(&lock); waiting[i] = false; /* critical section */ j = (i + 1) % n; while ((j != i) && !waiting[j]) j = (j + 1) % n; if (j == i) lock = false; else waiting[j] = false; /* remainder section */ } while (true); => Thỏa tất cả các yêu cầu cho vấn đề miền tương trục 10/29/201326 Chương 5: Đồng bộ hóa
23. • Các giải pháp với test_and_set và compare_and_swap thì phứctạpvàngườilập trình ứng dụng thường không thể truy cập đến các lệnh này • Ngườithiếtkế HĐHxâydựng các công cụ phầnmềm để giải quyếtvấn đề này • Công cụđơngiảnnhấtlàMuxtex lock • Mutex lock có mộtbiến boolean => miềntương trụccósẵn sàng hay không? • Bảovệ miềntương trụcvới2hàm: o Acquire():yêucầu khóa trước khi vào miềntương trục o Release():giải phóng khóa trước khi rờikhỏimiềntương trục • Hai hàm acquire và release phải đượcgọivàthực thi một cách nguyên tử o Thường được cài đặtbằng các thao tác nguyên tửđượccungcấpbởiphầncứng (hardware atomic instructions) như: test_and_set hay compare_and_swap • Muxtex lock đòi hỏitiếntrìnhchờđợibận (busy waiting) khi miềntương trục không sẵnsàng • Muxtex lock còn đượcgọilàspinlock 10/29/201327 Chương 5: Đồng bộ hóa
24. acquire() { while (!available) ; /* busy wait */ available = false;; } release() { available = true; } do { acquire lock critical section release lock remainder section } while (true); 10/29/201328 Chương 5: Đồng bộ hóa
25. • Các giải pháp chờđợibậnlàmhaophíthờigiancủa CPU. Semaphore là công cụđồng bộ hóa không gây ra tình trạng chờđợibận. • Semaphore cho phép tiếntrìnhchờđợivàomiềntương trụcsẽ ngủ/nghẽn (sleep/blocked) và sẽđược đánh thức (wakeup) bởimộttiến trình khác. • Ít phứctạphơn • Semaphore S: là mộtbiếninteger,chỉ có thểđượctruycập thông qua hai thao tác nguyên tử: wait (S) { while (S <= 0) ; // busy wait S ; } signal (S) { S++; } 10/29/201330 Chương 5: Đồng bộ hóa
26. • Semaphore đếm – giá trị củaintegercủabiếnsemaphorecómột miền giá trị không giớihạn • Semaphore nhị phân:chỉ có giá trị 0hay1=>giống như mutex lock • Semaphore đếm S có thểđượcdùngđể cài đặtnhư là một semaphore nhị phân • Xét tiếntrìnhP1 và P2 yêu cầulệnh S1 thựcthitrước S2 P1: S1; signal(synch); P2: wait(synch); S2; 10/29/201331 Chương 5: Đồng bộ hóa
27. • Định nghĩamột semaphore như là mộtcấutrúcgồmcó: o Một giá trị integer o Một danh sách các tiếntrìnhđang đợitrênnó typedef struct { int value; struct process *L; } semaphore; • Giả sử ta đã có hai thao tác được cung cấpbởihệđiềuhành như những lờigọihệ thống cơ bản: block() –ngưng tạmthờitiếntrìnhgọi thao tác này. wakeup(P) khởi động lạitiếntrìnhPđãgọi thao tác block() trước đó. 10/29/201332 Chương 5: Đồng bộ hóa
28. • Yêu cầu: không có bấtkỳ 2tiến trình nào có thể thực thi cùng lúc hai thao tác wait() và signal() => critical-section problem • Cài đặt wait() và signal(): o Hệ thống đơnxử lý: vô hiệu hóa các ngắt o Hệ thống đaxử lý: • Dùng busy waiting (các lệnh nguyên tử hay spinlock) • Khônghoàntoànloạibỏđược busy waiting tuy nhiên mã lệnh của wait() và signal() là ngắn=>giảmbớtthời gian tiến trình phải dùng cho busy waiting 10/29/201333 Chương 5: Đồng bộ hóa
29. wait(semaphore *S) { S->value ; if (S->value list; block(); } } signal(semaphore *S) { S->value++; if (S->value list; wakeup(P); } } 10/29/201334 Chương 5: Đồng bộ hóa
30. • Khóa chết–haihoặc nhiềutiếntrìnhđang chờđợivôhạnmột sự kiệnnào đó, mà sự kiện đóchỉ có thểđượctạorabởimột trong các tiếntrìnhđang chờđợi khác. • Giả sử có 2 semaphore S và Q có giá trị 1 P0 P1 wait (S); wait (Q); wait (Q); wait (S); signal (S); signal (Q); signal (Q); signal (S); • Sựđói CPU –bị nghẽn (block) không hạn định. Mộttiếntrình có thể không bao giờđược xóa khỏihàngđợi trong semaphore. 10/29/201335 Chương 5: Đồng bộ hóa
31. 1. Vùng đệm có kích thước giới hạn 2. Bộ đọc –bộ ghi 3. Các triết gia ăn tối
32. • Vùng đệmcókíchthướcgiớihạn–Bounded-Buffer • Hai tiến trình producer và consumer chia sẻ vùng đệmcókích thướcn. • Dữ liệuchiasẻ: o Semaphore mutex: dùng cho loạitrừ hỗ tương, khởitạo1. o Các Semaphore empty và full:dùngđể đếmsố khe trống và đầy. Khởitạo empty = n và full = 0. 10/29/201337 Chương 5: Đồng bộ hóa
33. • Tiến trình Producer: do { /* produce an item in next_produced */ wait(empty); wait(mutex); /* add next produced to the buffer */ signal(mutex); signal(full); } while (true); 10/29/201338 Chương 5: Đồng bộ hóa
34. • Tiến trình Consumer: do { wait(full); wait(mutex); /* remove an item from buffer to next_consumed */ signal(mutex); signal(empty); /* consume the item in next consumed */ } while (true); 10/29/201339 Chương 5: Đồng bộ hóa
35. • Mộttậpdữ liệu(dataset)đượcchiasẻ giữa nhiềutiếntrình thựcthiđồng thời. o Readers: tiếntrìnhchỉđọc, không cậpnhậtdữ liệu o Writers: tiếntrìnhthựcthicả hai thao tác đọcvàghidữ liệu • Vấn đề: o Các reader có thểđọcdữ liệuchiasẽđồng thời o Tạimộtthời điểmchỉ một writer đượcphéptruycậpdữ liệuchia sẽ • Các biếnthể: o Bộđọctrướcbộ ghi: không bộđọcnàophảichờ,trừ khi bộ ghi đang cậpnhậtdữ liệu=>bộ ghi có thể bịđói o Bộ ghi trướcbộđọc: khi bộđọc đãsẳnsàng,nósẽ ghi sớmnhất có thể => bộđọccóthể bịđói 10/29/201340 Chương 5: Đồng bộ hóa
36. • Dữ liệuchiasẻ: o Biến read_count: ghi vếtsố tiếntrìnhđang đọc đốitượng. Khởi tạo 0. o Semaphore mutex:dùngcholoạitrừ hỗ tương khi cậpnhậtbiến readcount.Khởitạo 1. o Semaphore rw_mutex:dùngloạitrừ hỗ tương cho các bộ ghi. Khởi tạorw_mutex=1. Semaphore này cũng được dùng để ngăncấm các bộ ghi truy cậpvàođốitượng chia sẻ khi nó đang được đọc. 10/29/201341 Chương 5: Đồng bộ hóa
37. do { wait(rw_mutex); /* writing is performed */ signal(rw_mutex); } while (true); 10/29/201342 Chương 5: Đồng bộ hóa
38. do { wait(mutex); read_count++; if (read_count == 1) wait(rw_mutex); signal(mutex); /* reading is performed */ wait(mutex); read_count ; if (read_count == 0) signal(rw_mutex); signal(mutex); } while (true); 10/29/201343 Chương 5: Đồng bộ hóa
39. • Nămtriếtgiangồitrênbàntròn,giữa là bát cơmvà5chiếc đũanhư hình, vừa ănvừa suy nghĩ. • Khi suy nghĩ,triết gia không giao tiếp với các triết gia khác. • Khi đói, ông ta cố gắng chọn2chiếc đũagầnnhất(giữa ông ta và 2 láng giềng). Ông ta chỉ có thể lấy được1 chiếc đũatạimỗithời điểm, và không thể lấy được đũa đang được dùng bởi láng giềng. • Khi có 2 chiếc đũa, triết gia ăn và chỉ đặt đũa xuống khi ăn xong, sau đó suy nghĩ tiếp. • Dữ liệu chia sẻ: semaphore chopstick[5]; Khởi đầu, các giá trị là 1. 10/29/201344 Chương 5: Đồng bộ hóa
40. • Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) // eat signal(chopstick[i]); signal(chopstick[(i+1) % 5]); // think } while (TRUE); 10/29/201345 Chương 5: Đồng bộ hóa
41. • Giảithuậtbảo đảm không có 2 láng giềng ăn cùng lúc, nhưng có thể gây khóa chết (tình huống5triết gia cùng đói và mỗi người cùng lấy đũa bên trái) và đói tài nguyên. • Các giải pháp khả dụng: o Cho phép nhiềunhất4triết gia cùng ngồitrênbàn. o Cho phép mộttriếtgialấy đũachỉ nếucả hai chiếc đũa đềusẵn dùng. o Dùng giải pháp bất đốixứng. Ví dụ triếtgialẻ lấy đũatráitrước, rồi đến đũaphải, trong khi triếtgiachẵnthaotácngượclại. 10/29/201346 Chương 5: Đồng bộ hóa
42. • Sử dụng không đúng: o signal(mutex) . wait(mutex) o wait(mutex) wait(mutex) o Thiếu wait(mutex) hoặc signal(mutex) hay cả hai • Khóa chếtvàđối tài nguyên 10/29/201348 Chương 5: Đồng bộ hóa
43. • Monitor là mộtcấutrúccủangônngữ lập trình (programming language construct), cung cấpcơ chếđồng bộ hóa ở mức ngôn ngữ cấp cao (high- level language synchronization construct) giúp thuậntiệnvàhiệuquảđể đồng bộ hóa các tiếntrình • Abstract data type (ADT): monitor monitor‐name kiểudữ liệutrừutượng: dữ liệu { đượcbaobọcbởi các hàm bên // shared variable declarations ngoài, và chỉ các hàm này được phép truy cập đến các dữ liệu procedure P1 ( ) { . } đó=>monitor type là một . ADT . • Chỉ mộttiếntrìnhcó thể thưc . thi bên trong monitor tạimột procedure Pn ( ) { } thời điểm=>chỉ mộthàmbên trong monitor đượcthựcthitại initialization_code ( ) { } mộtthời điểm } 10/29/201349 Chương 5: Đồng bộ hóa
44. 10/29/201350 Chương 5: Đồng bộ hóa
45. • Condition x, y; • Hai thao tác trên biến điềukiện: o x.wait () –ngưng tạmthờitiếntrìnhgọi thao tác này cho đến khi x.signal () o x.signal () –phụchồilạitiếntrìnhđãgọi x.wait () • Nếu không có bấtkỳ tiến trình nào chờ trên biến điềukiện x hàm signal() không gây bấtcứảnh hưởng nào 10/29/201351 Chương 5: Đồng bộ hóa
46. 10/29/201352 Chương 5: Đồng bộ hóa
47. • Giả sử tiếntrìnhP gọi x.signal() khi tiếntrìnhQ đang chờ trên biến điềukiệnx,để tránh hai tiếntrìnhthực thi cùng lúc trong monitor, một trong hai lựachọnsauđây có thểđược dùng: 1. Signal and wait:Pchờ cho đếnkhiQrờikhỏi monitor hoặcchờ một điềukiện khác 2. Signal and continue:Qchờ cho đếnkhiPrờikhỏi monitor hoặcchờ một điềukiện khác • Lựachọnthứ 2 đượcsử dụng kèm theo với điềukiệnPphảilập tứcthoátrakhỏi monitor đượcsử dụng trong ngôn ngữ Concurrent Pascal • Nhiều ngôn ngữ lập trình cài đặtcơ chếđồng bộ xác vớiýtưởng monitor nhưđãmôtả (bao gồm C# và Java) • Mộtsố ngôn ngữ lập trình khác (như Erlang) cung cấp các cơ chế tương tự 10/29/201353 Chương 5: Đồng bộ hóa
48. monitor ProducerConsumer • Dùng ngôn ngữ Pascal condition full, empty; được đơngiản hóa (Pidgin integer count; Pascal) minh họasử dụng procedure insert(item: integer); Monitor giảiquyết bài toán begin Producer-Consumer if count = N then wait(full); insert_item(item) ; count := count + 1 ; if count = 1 then signal( empty) end; function remove: integer; begin if count = 0 then wait(empty); remove = remove_item; count := count ‐ 1 ; if count = N‐ 1 then signal(full) end; count := 0; end monitor; 10/29/201354 Chương 5: Đồng bộ hóa
49. procedure producer; procedure consumer; begin begin while true do while true do begin begin item = producer_item; item = ProducerConsumer.remove; ProducerConsumer.insert(item) consume_item(item) end end end; end; 10/29/201355 Chương 5: Đồng bộ hóa