Bài giảng Kỹ thuật Máy tính - Chương 7: Đồng bộ hóa - Nguyễn Thanh Sơn

Nội dung text: Bài giảng Kỹ thuật Máy tính - Chương 7: Đồng bộ hóa - Nguyễn Thanh Sơn

1. Nội dung  Khái niệm cơ bản  Tranh chấp “Critical section”  Các giải pháp  Sử dụng lệnh máy thông thường  Giải thuật Peterson, và giải thuật bakery  Sử dụng lệnh cấm ngắt hoặc lệnh máy đặc biệt  Semaphore  Monitor BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 2
2. Bài toán đồng bộ (tt.)  Hai lớp bài toán đồng bộ:  Hợp tác (cooperation)  Bài toán producer-consumer: bounded buffer  Tranh giành (contention)  Bài toán loại trừ tương hỗ: đồng bộ nhiều quá trình sử dụng một tài nguyên không chia sẻ đồng thời được (như printer)  Bài toán Dining Philosophers BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 4
3. Bài toán Producer-consumer  Ví dụ Bounded buffer, thêm biến đếm count #define BUFFER_SIZE 10 /* 10 buffers */ typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0, out = 0, count = 0; BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 6
4. Bài toán Producer-consumer (tt.)  Các lệnh tăng/giảm biến count tương đương trong ngôn ngữ máy là: Producer count++: register1 = count register1 = register1 + 1 count = register1 Consumer count : register2 = count register2 = register2 - 1 count = register2 Trong đó, register là thanh ghi của CPU. BK i TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 8
5. Race condition  Race condition: nhiều process truy xuất và thao tác đồng thời lên dữ liệu chia sẻ (như biến count); kết quả cuối cùng của việc truy xuất đồng thời này phụ thuộc thứ tự thực thi của các lệnh thao tác dữ liệu.  Để dữ liệu chia sẻ được nhất quán, cần bảo đảm sao cho các process lần lượt thao tác lên dữ liệu chia sẻ. Do đó, cần có cơ chế đồng bộ hoạt động của các process này. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 10
6. Cấu trúc tổng quát của quá trình trong bài toán loại trừ tương hỗ  Giả sử mỗi process thực thi bình Một số giả định thường (i.e., nonzero speed) và  Có thể có nhiều CPU nhưng không có sự tương quan giữa tốc phần cứng không cho phép độ thực thi của các process nhiều tác vụ truy cập một vị trí  Cấu trúc tổng quát của một trong bộ nhớ cùng lúc process: (simultaneous) do {  Không ràng buộc về thứ tự entry section thực thi của các process critical section  Các process có thể chia sẻ một số biến chung nhằm đồng exit section bộ hoạt động của chúng remainder section  Giải pháp cần phải đặc tả entry } while(1); section và exit section BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 12
7. Phân loại giải pháp cho loại trừ tương hỗ  Giải pháp 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 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 14
8. Giải thuật 1 (Dekker1)  Biến chia sẻ int turn; /* khởi đầu turn = 0 */ if turn = i then (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);  Giải thuật thoả mãn mutual exclusion (1), nhưng không thoả mãn tính chất progress (2) vì tính chất strict alternation của giải thuật BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 16
9. Giải thuật 2 (Dekker2)  Biến chia sẻ boolean flag[ 2 ]; /* khởi đầu flag[ 0 ] = flag[ 1 ] = false */ if flag[ i ] = true then 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 bounded wait(3). Vì sao? Trường hợp sau có thể xảy ra: P0 gán flag[ 0 ] = true P1 gán flag[ 1 ] = true BK P0 và P1 loop mãi mãi trong vòng lặp while TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 18
10. Giải thuật Peterson cho 2 process (tt.) (viết lại) 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 */ favor = 1; favor = 0; while (flag[1] && while (flag[0] && favor == 1); favor == 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); BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 20
11. Giải thuật bakery  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ố:  Neáu i < j thì Pi ñöôïc vaøo tröôùc.  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ố 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 = BK 0, , k TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 22
12. Đánh giá  Các giải pháp dùng lệnh máy thông thường  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 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 slide tiếp theo BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 24
13. 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 đơn nguyên có thể thực hiện hai thao tác 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 exclusion (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, tránh starvation và BK TP.HCM deadlock. Khoa Khoa học & Kỹ thuật Máy tính 26
14. 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, sự chọn lựa process Pj vào CS kế tiếp là tùy ý starvation (bounded wait)  Các processor (ví dụ Pentium) thông thường cung cấp một lệnh máy đơn nguyê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 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 28
15. Giải thuật dùng TestAndSet: thoả mãn 3 yêu cầu do { waiting[ i ] = true; key = true; Biến chia sẻ, while (waiting[ i ] && key) khởi tạo là false key = TestAndSet(lock); waiting[ i ] = false; bool waiting[ n ]; critical section bool lock; 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) BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 30
16. Semaphore Semaphore là công cụ đồng bộ cung cấp bởi OS.  Một thuộc tính của semaphore là trị của nó, ngoài thao tác khởi động biến thì chỉ có thể được truy xuất qua hai tác vụ  wait(S) hay còn gọi là P(S): giảm trị semaphore, nếu trị này âm thì process gọi lệnh bị blocked.  signal(S) hay còn gọi là V(S): tăng trị semaphore, nếu trị này không dương, một process đang blocked bởi gọi lệnh wait() trước đó sẽ được hồi phục để thực thi.  Semaphore giúp process 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.  Nhưng có thể cần busy waiting để hiện thực chính semaphore BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 32
17. 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); } BK } TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 34
18. Ứng dụng semaphore: hiện thực mutex  Dùng cho n process Shared data: semaphore mutex; /* initially mutex.value = 1  Khởi tạo S.value = 1 */ Chỉ một process được thực Process Pi: thi trong CS (mutual exclusion) do { wait(mutex);  Để cho phép k process critical section được thực thi trong CS, signal(mutex); khởi tạo S.value = k remainder section } while (1); BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 36
19. Nhận xét về semaphore  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 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 38
20. Deadlock và starvation  Deadlock: hai hay nhiều process chờ 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.  Ví dụ deadlock: 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. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 40
21. Semaphore và bài toán bounded buffer  Giải thuật cho bài toán bounded buffer  Dữ liệu chia sẻ: semaphore full, empty, mutex;  Khôûi taïo: full = 0; /* số buffers đầy */ empty = n; /* số buffers trống */ mutex = 1; n buffers BK out TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 42
22. Bài toán “Dining Philosophers”  5 triết gia ngồi ăn và suy nghĩ 3 2 3  Mỗi người cần 2 chiếc đũa (chopstick) để ăn 4 2  Trên bàn chỉ có 5 đũa 4 0 1 1  “Dining philosophers” thuộc về lớp các bài toán phân 0 phối tài nguyên giữa các process sao cho không xảy ra deadlock và starvation BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 44
23. 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 đồng thời cầm chiếc đũa bên tay trái rồi lấy đủa tay phải deadlock  Một số giải pháp giải quyết được deadlock  Cho phép nhiều nhất4 triết gia ngồi vào bàn  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? BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 46
24. Bài toán Readers-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. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 48
25. Monitor  Phần tử ngôn ngữ cấp cao  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 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 50
26. Cấu trúc của monitor monitor monitor-name { shared variable declarations procedure body P1 ( ) { . . . } procedure body P2 ( ) { . . . } procedure body Pn ( ) { . . . } { initialization code } } BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 52
27. 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  Lệnh a.signal chuyển một process từ condition queue a operations vào monitor • Khi đó, để bảo đảm mutual initialization exclusion, process gọi a.signal code sẽ bị blocked và được đưa vào urgent queue BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 54
28. Monitor và dining philosophers 3 2 4 1 monitor dp { 0 enum {THINKING, HUNGRY, EATING} state[5]; condition self[5]; BK } TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 56
29. Monitor và 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; } BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 58