Bài giảng Hệ điều hành - Chương 3: Đồng bộ và giải quyết tranh chấp (Process synchronization)

Nội dung text: Bài giảng Hệ điều hành - Chương 3: Đồng bộ và giải quyết tranh chấp (Process synchronization)

1. Phân loại giải pháp ❑ Giải pháp phần mềm: dùng lệnh máy thông thường ❑ Giải pháp dùng lệnh cấm ngắt hay lệnh máy đặc biệt – Lệnh Disable interrupt – Lệnh máy đặc biệt như » TestAndSet Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 11
2. Giải pháp phần mềm ❑ Trường hợp 2 process đồng thời: P0 và P1 – Giải thuật 1 và 2 – Giải thuật 3 (Peterson’s algorithm) ❑ Giải thuật cho n process – Bakery algorithm Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 12
3. Giải thuật 1 ❑ Biến chia sẻ int turn; /* khởi đầu turn = 0 */ nếu turn = i thì Pi được phép vào critical section, với i = 0 hay 1 ❑ Process Pi do { while (turn != i); critical section turn = j; remainder section } while (1); ❑ Thoả mãn mutual exclusion (1) ❑ Nhưng không thoả mãn yêu cầu về progress (2) và bounded waiting (3) vì tính chất strict alternation của giải thuật Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 13
4. Giải thuật 1 (tt) Process P0: Process P1: do do while (turn != 0); while (turn != 1); critical section critical section turn := 1; turn := 0; remainder section remainder section while (1); while (1); Ví dụ: P0 có RS (remainder section) rất lớn còn P1 có RS nhỏ. Nếu turn = 0, P0 được vào CS và sau đó thực thi turn = 1 và vào vùng RS. Lúc đó P1 vào CS và sau đó thực thi turn = 0, kế đó P1 vào và xong RS, và đợi vào CS một lần nữa, nhưng vì turn = 0 nên P1 phải chờ P0. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 14
5. Giải thuật 2 ❑ Biến chia sẻ boolean flag[ 2 ]; /* khởi đầu flag[ 0 ] = flag[ 1 ] = false */ Nếu flag[ i ] = true thì Pi “sẵn sàng” vào critical section. ❑ Process Pi do { flag[ i ] = true; /* Pi “sẵn sàng” vào CS */ while ( flag[ j ] ); /* Pi “nhường” Pj */ critical section flag[ i ] = false; remainder section } while (1); ❑ Bảo đảm được mutual exclusion. Chứng minh? ❑ Không thỏa mãn progress. Vì sao? Trường hợp sau có thể xảy ra: P0 gán flag[ 0 ] = true P1 gán flag[ 1 ] = true P0 và P1 loop mãi mãi trong vòng lặp while Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 15
6. Giải thuật 3 (Peterson) ❑ Biến chia sẻ: kết hợp cả giải thuật 1 và 2 ❑ Process Pi , với i = 0 hay 1 do { flag[ i ] = true; /* Process i sẵn sàng */ turn = j; /* Nhường process j */ while (flag[ j ] and turn == j); critical section flag[ i ] = false; remainder section } while (1); ❑ Thoả mãn được cả 3 yêu cầu (chứng minh?) giải quyết bài toán critical section cho 2 process. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 16
7. Giải thuật Peterson-2 process Process P Process P0 1 do { do { /* 0 wants in */ /* 1 wants in */ flag[0] = true; flag[1] = true; /* 0 gives a chance to 1 */ /* 1 gives a chance to 0 */ turn = 1; turn = 0; while (flag[1] && while (flag[0] && turn == 1); turn == 0); critical section critical section /* 0 no longer wants in */ /* 1 no longer wants in */ flag[0] = false; flag[1] = false; remainder section remainder section } while(1); } while(1); Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 17
8. Giải thuật 3: Tính đúng đắn Giải thuật 3 thỏa mutual exclusion, progress, và bounded waiting ❑ Mutual exclusion được bảo đảm bởi vì P0 và P1 đều ở trong CS nếu và chỉ nếu flag[0] = flag[1] = true và turn = i cho mỗi Pi (không thể xảy ra) ❑ Chứng minh thỏa yêu cầu về progress và bounded waiting – Pi không thể vào CS nếu và chỉ nếu bị kẹt tại vòng lặp while() với điều kiện flag[ j ] = true và turn = j . – Nếu Pj không muốn vào CS thì flag[ j ] = false và do đó Pi có thể vào CS. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 18
9. Giải thuật 3: Tính đúng đắn (tt) – Nếu Pj đã bật flag[ j ] = true và đang chờ tại while() thì có chỉ hai trường hợp là turn = i hoặc turn = j – Nếu turn = i thì Pi vào CS. Nếu turn = j thì Pj vào CS nhưng sẽ bật flag[ j ] = false khi thoát ra cho phép Pi vào CS – Nhưng nếu Pj có đủ thời gian bật flag[ j ] = true thì Pj cũng phải gán turn = i – Vì Pi không thay đổi trị của biến turn khi đang kẹt trong vòng lặp while(), Pi sẽ chờ để vào CS nhiều nhất là sau một lần Pj vào CS (bounded waiting) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 19
10. Giải thuật bakery: n process ❑ Trước khi vào CS, process Pi nhận một con số. Process nào giữ con số nhỏ nhất thì được vào CS ❑ Trường hợp Pi và Pj cùng nhận được một chỉ số: – Nếu i < j thì Pi được vào trước. (Đối xứng) ❑ Khi ra khỏi CS, Pi đặt lại số của mình bằng 0 ❑ Cơ chế cấp số cho các process thường tạo các số theo cơ chế tăng dần, ví dụ 1, 2, 3, 3, 3, 3, 4, 5, ❑ Kí hiệu (a,b) < (c,d) nếu a < c hoặc if a = c và b < d max(a0, ,ak) là con số b sao cho b ai với mọi i = 0, , k Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 20
11. Giải thuật bakery: n process (tt) /* shared variable */ boolean choosing[ n ]; /* initially, choosing[ i ] = false */ int num[ n ]; /* initially, num[ i ] = 0 */ do { choosing[ i ] = true; num[ i ] = max(num[0], num[1], , num[n − 1]) + 1; choosing[ i ] = false; for (j = 0; j < n; j++) { while (choosing[ j ]); while ((num[ j ] != 0) && (num[ j ], j) < (num[ i ], i)); } critical section num[ i ] = 0; remainder section } while (1); Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 21
12. Đánh giá ❑ Các giải pháp phần mềm – Các process khi yêu cầu được vào vùng tranh chấp đều phải liên tục kiểm tra điều kiện (busy waiting), tốn nhiều thời gian xử lý của CPU – Nếu thời gian xử lý trong vùng tranh chấp lớn, một giải pháp hiệu quả nên có cơ chế block các process cần đợi. ❑ Các giải pháp dùng lệnh cấm ngắt hay dùng các lệnh máy đặc biệt (xem slide sau) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 22
13. Cấm ngắt ❑ Trong hệ thống uniprocessor: mutual exclusion được bảo Process Pi: đảm. do { – Nhưng nếu system clock được cập nhật do interrupt disable_interrupts(); thì critical section ❑ Trên hệ thống multiprocessor: enable_interrupts(); mutual exclusion không được đảm bảo remainder section – Chỉ cấm ngắt tại CPU thực } while (1); thi lệnh disable interrupts – Các CPU khác vẫn có thể truy cập bộ nhớ chia sẻ Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 23
14. Dùng các lệnh máy đặc biệt ❑ Ý tưởng – Việc truy xuất vào vào một địa chỉ của bộ nhớ vốn đã có tính loại trừ tương hỗ (chỉ có một thao tác truy xuất tại một thời điểm) ❑ Mở rộng – Thiết kế một lệnh máy có thể thực hiện hai thao tác chập (atomic, indivisible) trên cùng một ô nhớ (vd: read và write) – Việc thực thi các lệnh máy như trên luôn bảo đảm mutual exclusive (ngay cả với multiprocessor) ❑ Các lệnh máy đặc biệt có thể đảm bảo mutual exclusion nhưng cần kết hợp với một số cơ chế khác để thoả mãn progress và bounded waiting cũng như tránh starvation và deadlock. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 24
15. Lệnh TestAndSet ❑ Đọc và ghi một biến trong một thao tác atomic (không chia cắt được). boolean TestAndSet(boolean &target) Shared data: { boolean lock = false; boolean rv = target; Process P : target = true; i return rv; } do { while (TestAndSet(lock)); critical section lock = false; remainder section } while (1); Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 25
16. Lệnh TestAndSet (tt) ❑ Mutual exclusion được bảo đảm: nếu Pi vào CS, các process Pj khác đều đang busy waiting ❑ Khi Pi ra khỏi CS, quá trình chọn lựa process Pj vào CS kế tiếp là tùy ý không bảo đảm điều kiện bounded waiting. Do đó có thể xảy ra starvation (bị bỏ đói) ❑ Các processor (ví dụ Pentium) thông thường cung cấp một lệnh đơn là Swap(a, b) có tác dụng hoán chuyển nội dung của a và b. Swap(a, b) cũng có ưu nhược điểm như TestAndSet Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 26
17. Swap và mutual exclusion ❑ Biến chia sẻ lock được khởi ❑ Biến chia sẻ (khởi tạo là false) tạo giá trị false bool lock; ❑ Mỗi process Pi có biến cục bộ bool waiting [n]; key ❑ Process Pi ❑ Process Pi nào thấy giá trị lock = false thì được vào CS. do { – Process Pi sẽ loại trừ các process Pj khác khi thiết lập key = true; lock = true while (key == true) void Swap(boolean &a, Swap(lock, key); boolean &b) { critical section boolean temp = a; lock = false; remainder section a = b; } while (1) b = temp; } Không thỏa mãn bounded waiting Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 27
18. Giải thuật dùng TestAndSet thoả mãn 3 yêu cầu (1) ❑ Cấu trúc dữ liệu dùng chung (khởi tạo là false) bool waiting[ n ]; bool lock; ❑ Mutual exclusion: Pi chỉ có thể vào CS nếu và chỉ nếu hoặc waiting[ i ] = false, hoặc key = false key = false chỉ khi TestAndSet (hay Swap) được thực thi » Process đầu tiên thực thi TestAndSet mới có key == false; các process khác đều phải đợi waiting[ i ] = false chỉ khi process khác rời khỏi CS » Chỉ có một waiting[ i ] có giá trị false ❑ Progress: chứng minh tương tự như mutual exclusion ❑ Bounded waiting: waiting in the cyclic order Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 28
19. Giải thuật dùng TestAndSet thoả mãn 3 yêu cầu (2) do { waiting[ i ] = true; key = true; while (waiting[ i ] && key) key = TestAndSet(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 (1) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 29
20. Semaphore Là công cụ đồng bộ cung cấp bởi OS mà không đòi hỏi busy waiting ❑ Semaphore S là một biến số nguyên, ngoài thao tác khởi động biến thì chỉ có thể được truy xuất qua hai tác vụ có tính đơn nguyên (atomic) và loại trừ (mutual exclusive) wait(S) hay còn gọi là P(S): giảm giá trị semaphore. Kế đó nếu giá trị này âm thì process thực hiện lệnh wait() bị blocked. signal(S) hay còn gọi là V(S): tăng giá trị semaphore. Kế đó nếu giá trị này không dương, một process đang blocked bởi một lệnh wait() sẽ được hồi phục để thực thi. ❑ Tránh busy waiting: khi phải đợi thì process sẽ được đặt vào một blocked queue, trong đó chứa các process đang chờ đợi cùng một sự kiện. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 30
21. Hiện thực semaphore ❑ Định nghĩa semaphore là một record typedef struct { int value; struct process *L; /* process queue */ } semaphore; cùng với các tác vụ lên nó ❑ Giả sử hệ điều hành cung cấp hai tác vụ (system call): block(): tạm treo process nào thực thi lệnh này wakeup(P): hồi phục quá trình thực thi của process P đang blocked Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 31
22. Hiện thực semaphore (tt) ❑ Các tác vụ semaphore được hiện thực như sau void wait(semaphore S) { S.value ; if (S.value < 0) { add this process to S.L; block(); } } void signal(semaphore S) { S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); } } Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 32
23. Hiện thực semaphore (tt) ❑ Khi một process phải chờ trên semaphore S, nó sẽ bị blocked và được đặt trong hàng đợi semaphore – Hàng đợi này là danh sách liên kết các PCB ❑ Tác vụ signal() thường sử dụng cơ chế FIFO khi chọn một process từ hàng đợi và đưa vào hàng đợi ready ❑ block() và wakeup() thay đổi trạng thái của process block: chuyển từ running sang waiting wakeup: chuyển từ waiting sang ready Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 33
24. Hiện thực mutex với semaphore ❑ Dùng cho n process ❑ Shared data: semaphore mutex; ❑ Khởi tạo S.value = 1 /* initially mutex.value = 1 */ Chỉ duy nhất một process được vào CS ❑ Process Pi: (mutual exclusion) do { ❑ Để cho phép k process wait(mutex); vào CS, khởi tạo critical section S.value = k signal(mutex); remainder section } while (1); Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 34
25. Đồng bộ process bằng semaphore ❑ Hai process: P1 và P2 ❑ Để đồng bộ hoạt động theo yêu cầu, P1 phải định nghĩa như sau: ❑ Yêu cầu: lệnh S1 trong P1 cần được thực thi S1; trước lệnh S2 trong P2 signal(synch); ❑ Và P2 định nghĩa như sau: ❑ Định nghĩa semaphore synch để đồng bộ wait(synch); S2; ❑ Khởi động semaphore: synch.value = 0 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 35
26. Nhận xét ❑ Khi S.value 0: số process có thể thực thi wait(S) mà không bị blocked = S.value ❑ Khi S.value < 0: số process đang đợi trên S là S.value ❑ Atomic và mutual exclusion: 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 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 36
27. Nhận xét (tt) ❑ 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. ❑ 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 làm việc trên hệ thống multiprocessor. – Multiprocessor: có thể dùng các giải pháp software (như giải thuật Dekker, Peterson) hoặc giải pháp hardware (TestAndSet, Swap). Vì CS rất nhỏ nên chi phí cho busy waiting sẽ rất thấp. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 37
28. 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 (vd: sự kiện do một trong các process đang đợi tạo ra). ❑ 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); P0 thực thi wait(S), rồi P1 thực thi wait(Q), rồi P0 thực thi wait(Q) bị blocked, P1 thực thi wait(S) bị blocked. ❑ Starvation (indefinite blocking) có thể xảy ra khi process vào hàng đợi và được lấy ra theo cơ chế LIFO. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 38
29. 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. ❑ Có thể hiện thực counting semaphore bằng binary semaphore. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 39
30. Các bài toán đồng bộ ❑ Bài toán bounded buffer – Dữ liệu chia sẻ: semaphore full, empty, mutex; – Khởi tạo: full = 0; /* số buffers đầy */ empty = n; /* số buffers trống */ mutex = 1; n buffers out Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 40
31. Bounded 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); Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 41
32. Bài toán “Dining Philosophers” (1) ❑ 5 triết gia ngồi ăn và suy nghĩ 3 2 – Mỗi người cần 2 chiếc đũa 3 (chopstick) để ăn 4 2 – Trên bàn chỉ có 5 đũa 4 0 1 1 ❑ Bài toán này minh họa sự khó khăn trong việc phân 0 phối tài nguyên giữa các process sao cho không ❑ Dữ liệu chia sẻ: xảy ra deadlock và semaphore chopstick[5]; starvation ❑ Khởi đầu các biến đều là 1 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 42
33. Bài toán “Dining Philosophers” (2) 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); Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 43
34. Bài toán “Dining Philosophers” (3) ❑ 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) – 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? Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 44
35. Bài toán Readers-Writers (1) ❑ Dữ liệu chia sẻ ❑ Reader Process semaphore mutex = 1; semaphore wrt = 1; wait(mutex); int readcount = 0; readcount++; if (readcount == 1) ❑ Writer process wait(wrt); signal(mutex); wait(wrt); reading is performed writing is performed wait(mutex); signal(wrt); readcount ; if (readcount == 0) signal(wrt); signal(mutex); Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 45
36. Bài toán Readers-Writers (2) ❑ 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. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 46
37. 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) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 47
38. 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. Khi một process muốn thực thi các lệnh trong region (tức là S), biểu thức Boolean B được kiểm tra. Nếu B = true, lệnh S được thực thi. Nếu B = false, process bị trì hoãn cho đến khi B = true. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 48