Cơ sở dữ liệu - Chương V - Phần II: Đồng bộ và giải quyết tranh chấp (process synchronization)

Nội dung text: Cơ sở dữ liệu - Chương V - Phần II: Đồng bộ và giải quyết tranh chấp (process synchronization)

1. Chương V - Phần II Đồng Bộ và Giải Quyết Tranh Chấp (Process Synchronization) 1
2. Nội dung  Đặt vấn đề (tại sao phải đồng bộ và giải quyết tranh chấp ?)  Vấn đề Critical section  Các giải pháp phần mềm ‟ Giải thuật Peterson, và giải thuật bakery  Đồng bộ bằng hardware  Semaphore  Các bài toán đồng bộ  Critical region  Monitor Khoa KTMT 2
3. Đặt vấn đề „ Khảo sát các process/thread thực thi đồng thời và chia sẻ dữ liệu (qua shared memory, file).  Nếu không có sự kiểm soát khi truy cập các dữ liệu chia sẻ thì có thể đưa đến ra trường hợp không nhất quán dữ liệu (data inconsistency).  Để duy trì sự nhất quán dữ liệu, hệ thống cần có cơ chế bảo đảm sự thực thi có trật tự của các process đồng thời. Q L p R Khoa KTMT 3
4. Bài toán Producer-Consumer Producer-Consumer .P khơng được ghi dữ liệu vào buffer đã đầy .C khơng được đọc dữ liệu từ buffer đang trống .P và C khơng được thao tác trên buffer cùng lúc Giới hạn, không giới hạn ??? P Buffer (N) C Khoa KTMT 4
5. Đặt vấn đề  Xét bài toán Producer-Consumer với bounded buffer  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; Khoa KTMT 5
6. Bounded buffer (tt)  Quá trình Producer item nextProduced; while(1) { while (count == BUFFER_SIZE); /* do nothing */ buffer[in] = nextProduced; count++; biến count được chia sẻ in = (in + 1) % BUFFER_SIZE; giữa producer và consumer }  Quá trình Consumer item nextConsumed; while(1) { while (count == 0); /* do nothing */ nextConsumed = buffer[out] ; count ; out = (out + 1) % BUFFER_SIZE; } Khoa KTMT 6
7. Bounded buffer (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 đó, các registeri là các thanh ghi của CPU. Khoa KTMT 7
8. Bounded buffer (tt) „ Mã máy của các lệnh tăng và giảm biến count có thể bị thực thi xen kẽ  Giả sử count đang bằng 5. Chuỗi thực thi sau có thể xảy ra: „ 0: producer register1 := count {register1 = 5} 1: producer register1 := register1 + 1 {register1 = 6} 2: consumer register2 := count {register2 = 5} 3: consumer register2 := register2 - 1 {register2 = 4} 4: producer count := register1 {count = 6} 5: consumer count := register2 {count = 4} Các lệnh count++, count phải là đơn nguyên (atomic), nghĩa là thực hiện như một lệnh đơn, không bị ngắt nửa chừng. Khoa KTMT 8
9. Bounded buffer (tt)  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 tại mỗi thời điểm chỉ có một process được 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. Khoa KTMT 9
10. Vấn đề Critical Section  Giả sử có n process cùng truy xuất đồng thời dữ liệu chia sẻ  Cấu trúc của mỗi process Pi - Mỗi process có đoạn code như sau : Do { entry section /* vào critical section */ critical section /* truy xuất dữ liệu chia xẻ */ exit section /* rời critical section */ remainder section /* làm những việc khác */ } While (1)  Trong mỗi process có những đoạn code có chứa các thao tác lên dữ liệu chia sẻ. Đoạn code này được gọi là vùng tranh chấp (critical section, CS). Khoa KTMT 10
11. Vấn đề Critical Section  Vấn đề Critical Section: phải bảo đảm sự loại trừ tương hỗ (MUTual EXclusion, mutex), tức là khi một process đang thực thi trong vùng tranh chấp, không có process nào khác đồng thời thực thi các lệnh trong vùng tranh chấp. Khoa KTMT 11
12. Yêu cầu của lời giải cho Critical Section Problem „ Lời giải phải thỏa bốn tính chất: (1) Độc quyền truy xuất (Mutual exclusion): Khi một process P đang thực thi trong vùng tranh chấp (CS) của nó thì không có process Q nào khác đang thực thi trong CS của Q. (2) Progress: Một tiến trình tạm dừng bên ngoài miền găng (CS) không được ngăn cản các tiến trình khác vào miền găng (CS) và việc lựa chọn P nào vào CS phải có hạn định „ (3) Chờ đợi giới hạn (Bounded waiting): Mỗi process chỉ phải chờ để được vào vùng tranh chấp trong một khoảng thời gian có hạn định nào đó. Không xảy ra tình trạng đói tài nguyên (starvation). (4)Không có giả thiết nào đặt ra cho sự liên hệ về tốc độ của các tiến trình, cũng như về số lượng bộ xử lý trong hệ thống Khoa KTMT 12
13. Phân loại giải pháp  Nhĩm giải pháp Busy Waiting – Sử dụng các biến cờ hiệu – Sử dụng việc kiểm tra luân phiên – Giải pháp của Peterson – Cấm ngắt – Chỉ thị TSL  Nhĩm giải pháp Sleep & Wakeup – Semaphore – Monitor – Message Khoa KTMT 13
14. Các giải pháp “Busy waiting” While (chưa cĩ quyền) do nothing() ; CS; Từ bỏ quyền sử dụng CS . Tiếp tục tiêu thụ CPU trong khi chờ đợi vào miền găng . Khơng địi hỏi sự trợ giúp của Hệ điều hành Khoa KTMT 14
15. Các giải pháp “Sleep & Wake up” if (chưa cĩ quyền) Sleep() ; CS; Wakeup( somebody); . Từ bỏ CPU khi chưa được vào miền găng . Cần được Hệ điều hành hỗ trợ Khoa KTMT 15
16. Các giải pháp “Busy waiting” 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 KTMT 16
17. 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ỏ??? P0 (I/O) P1 P0 ? Hệ Thống bị treo Khoa KTMT 17
18. 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? Khoa KTMT 18
19. 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 KTMT 19
20. 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] && turn == 1); while (flag[0] && 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 KTMT 20
21. 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 KTMT 21
22. 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 KTMT 22
23. 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 KTMT 23
24. 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; // khơng chiếm quyền vào vùng CS remainder section } while (1); Khoa KTMT 24
25. Từ software đến hardware  Khuyết điểm của các giải pháp software ‟ 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 phần cứng (hardware) ‟ Cấm ngắt (disable interrupts) ‟ Dùng các lệnh đặc biệt Khoa KTMT 25
26. 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ì sao? 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 KTMT 26
27. 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 KTMT 27
28. 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 KTMT 28
29. 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 key; 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 KTMT 29
30. 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 KTMT 30
31. 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 KTMT 31
32. Các giải pháp “Sleep & Wake up” int busy; // =1 nếu CS đang bị chiếm Int blocked; // số P đang bị khóa do { if (busy==1){ blocked = blocked +1; sleep(); Trường hợp: } -A vào CS else -B kích hoạt và tăng blocked busy =1; -A kích hoạt lại CS; -B kích hoạt lại -????? busy = 0; if(blocked !=0){ wakeup(process); blocked = blocked -1; } RS; } while(1); Khoa KTMT 32
33. 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 exclusion) „ wait(S) hay còn gọi là P(S): giảm giá trị semaphore (S=S-1) . 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 (S=S+1) . 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 KTMT 33
34. Semaphore  P(S) hay wait(S) sử dụng để giành tài nguyên và giảm biến đếm S=S-1  V(S) hay signal(S) sẽ giải phóng tài nguyên và tăng biến đếm S= S+1  Nếu P được thực hiện trên biến đếm <= 0 , tiến trình phải đợi V hay chờ đợi sự giải phóng tài nguyên Khoa KTMT 34
35. Hiện thực semaphore  Định nghĩa semaphore là một record typedef struct { int value; struct process *L;/* process queue */ } semaphore;  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 KTMT 35
36. 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 KTMT 36
37. 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 KTMT 37
38. Ví dụ sử dụng semaphore 1 : 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 KTMT 38
39. Ví dụ sử dụng semaphore 2 :Đồ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 KTMT 39
40. 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 KTMT 40
41. 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 KTMT 41
42. 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) Một tiến trình có thể không bao giờ được lấy ra khỏi hàng đợi mà nó bị treo trong hàng đợi đó. Khoa KTMT 42
43. 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 KTMT 43
44. Các bài toán đồng bộ (kinh điển)  Bounded Buffer Problem  Readers and Writers Problem  Dining-Philosophers Problem Khoa KTMT 44
45. 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 KTMT 45
46. Bounded buffer producer consumer do { do { wait(full) nextp = new_item(); wait(mutex);//2 wait(empty); nextc = get_buffer_item(out); wait(mutex);//1 signal(mutex);//4 insert_to_buffer(nextp); signal(empty); signal(mutex);//3 consume_item(nextc); signal(full); } while (1); } while (1); Khoa KTMT 46
47. Bài toán “Dining Philosophers” (1)  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  Bài toán này minh họa sự 0 khó khăn trong việc phân phối tài nguyên giữa các  Dữ liệu chia sẻ: process sao cho không semaphore chopstick[5]; xảy ra deadlock và starvation  Khởi đầu các biến đều là 1 Khoa KTMT 47
48. 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 KTMT 48
49. 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 KTMT 49
50. 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. R2 R3 R1 W1 W2 Database Khoa KTMT 50
51. Bài toán Readers-Writers (2)  Bộ đọc trước bộ ghi (first  Reader Process reader-writer)  Dữ liệu chia sẻ wait(mutex); semaphore mutex = 1; readcount++; semaphore wrt = 1; if (readcount == 1) int readcount = 0; wait(wrt); signal(mutex);  Writer process reading is performed wait(wrt); wait(mutex); writing is performed readcount ; if (readcount == 0) signal(wrt); signal(wrt); signal(mutex); Khoa KTMT 51
52. 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. Khoa KTMT 52
53. 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 KTMT 53
54. 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. Khoa KTMT 54
55. CR và bài toán bounded buffer Dữ liệu chia sẽ: Producer region buffer when (count 0){ nextc = pool[out]; out = (out + 1) % n; count ; } Khoa KTMT 55
56. 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 Khoa KTMT 56
57. Monitor (2)  Là một module phần  Đặc tính của monitor mềm, bao gồm ‟ Local variable chỉ có thể ‟ Một hoặc nhiều thủ tục truy xuất bởi các thủ tục (procedure) của monitor ‟ Một đoạn code khởi tạo ‟ Process “vào monitor” bằng (initialization code) cách gọi một trong các thủ ‟ Các biến dữ liệu cục bộ tục đó (local data variable) ‟ Chỉ có một process có thể vào monitor tại một thời điểm mutual exclusion shared data được bảo đảm entry queue operations initialization Mô hình của một monitor code đơn giản Khoa KTMT 57
58. Cấu trúc của monitor monitor monitor-name { shared variable declarations procedure body P1 ( ) { . . . } procedure body P2 ( ) { . . . } procedure body Pn ( ) { . . . } { initialization code } } Khoa KTMT 58
59. 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 Khoa KTMT 59
60. 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 operations process từ condition queue a 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 Khoa KTMT 60
61. 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 Khoa KTMT 61
62. Monitor và dining philosophers 3 2 4 1 0 monitor dp { enum {thinking, hungry, eating} state[5]; condition self[5]; Khoa KTMT 62
63. 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 } Khoa KTMT 63
64. 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; } } Khoa KTMT 64
65. 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. Khoa KTMT 65
66. 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 ? Khoa KTMT 66
67. 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 ? Khoa KTMT 67
68. 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 Khoa KTMT 68
69. 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 . Khoa KTMT 69
70. 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. Khoa KTMT 70
71. 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 ? Khoa KTMT 71
72. 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 ? Khoa KTMT 72
73. 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. Khoa KTMT 73