›
›

Bài giảng Hệ điều hành - Chương 4: Đồng bộ hóa tiến trình - Trần Hạnh Nhi

pdf 85 trang huongle 4750
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 4: Đồng bộ hóa tiến trình - Trần Hạnh Nhi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_he_dieu_hanh_chuong_4_dong_bo_hoa_tien_trinh_tran.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 4: Đồng bộ hóa tiến trình - Trần Hạnh Nhi

  1. Bài giảng 4 Đồng bộ hoá tiến trình 10/28/2005 Trần Hạnh Nhi 1
  2. Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 2
  3. Nhiều tiến trình “chung sống hoà bình” trong hệ thống ? ĐỪNG HY VỌNG An toàn khi các tiến trình hoàn toàn độc lập Làm sao có được ?? Thực tế Các tiến trình chia sẻ tài nguyên chung ( file system, CPU ) Concurrent access => bugs. Ví dụ : Dê con qua cầu Xử lý đồng hành = nhức đầu 10/28/2005 Trần Hạnh Nhi 3
  4. Các vấn đề Tranh chấp Nhiều tiến trình truy xuất đồng thời một tài nguyên mang bản chất không chia sẻ được Xảy ra vấn đề tranh đoạt điều khiển (Race Condition) Kết quả ? Khó biết , thường là sai Luôn luôn nguy hiểm ? Không, nhưng đủ để cân nhắc kỹ càng Phối hợp Các tiến trình không biết tương quan xử lý của nhau để điều chỉnh hoạt động nhịp nhàng Cần phối hợp xử lý (Rendez-vous) Kết quả : khó biết, không bảo đảm ăn khớp 10/28/2005 Trần Hạnh Nhi 4
  5. Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 5
  6. Tranh đoạt điều khiển (Race condition) - Ví dụ Đếm số người vào Altavista : dùng 2 threads cập nhật biến đếm hits=> P1 và P2 chia sẻ biến hits hits = 0 P1 P2 hits = hits +1; hits = hits + 1; Kết quả cuối cùng là bao nhiêu ? 10/28/2005 Trần Hạnh Nhi 6
  7. Tranh đoạt điều khiển (Race condition) - Ví dụ hits = 0 P2 time P1 (1) read hits (0) (2)read hits (0) (3) hits = 0 + 1 (4)hits = 0 + 1 hits = 1 10/28/2005 Trần Hạnh Nhi 7
  8. Tranh đoạt điều khiển (Race condition) - Ví dụ hits = 0 P2 time P1 (1) read hits (0) (2) hits = 0 + 1 (3) read hits (1) hits = 2 (4) hits = 1 + 1 10/28/2005 Trần Hạnh Nhi 8
  9. Tranh đoạt điều khiển (Race condition) - Ví dụ (tt) i=0; Thread a: Thread b: while(i -10) i = i +1; i = i - 1; print “A won!”; print “B won!”; Ai thắng ? Có bảo đảm rằng sẽ có người thắng ? Nếu mỗi tiến trình xử lý trên 1 CPU thì sao ? 10/28/2005 Trần Hạnh Nhi 9
  10. Tranh đoạt điều khiển (Race condition)-Nhận xét Kết quả thực hiện tiến trình phụ thuộc vào kết quả điều phối Cùng input, không chắc cùng output Khó debug lỗi sai trong xử lý đồng hành Xử lý Làm lơ Dễ , nhưng có phải là giải pháp Không chia sẻ tài nguyên chung : dùng 2 biến hits1,hits2; xây cầu 2 lane Nên dùng khi có thể, nhưng không bao giờ có thể đảm bảo đủ tài nguyên, và cũng không là giải pháp đúng cho mọi trường hợp Giải pháp tổng quát : có hay không ? Lý do xảy ra Race condition ? Bad interleavings : một tiến trình “xen vào” quá trình truy xuất tài nguyên của một tiến trình khác Giải pháp : bảo đảm tính atomicity cho phép tiến trình hoàn tất trọn vẹn quá trình truy xuất tài nguyên chung trước khi có tiến trình khác can thiệp 10/28/2005 Trần Hạnh Nhi 10
  11. Atomicity : loại bỏ Race Condition hits = 0 P2 time P1 read hits (0) hits = 0 + 1 read hits(1) hits = 1 + 1 hits = 2 10/28/2005 Trần Hạnh Nhi 11
  12. Miền găng (Critical Section) & Khả năng độc quyền (Mutual Exclusion) Miền găng (CS) là đoạn chương trình có khả năng gây ra hiện tượng race condition P1 P2 printf(“Welcome”); printf(“Welcome”); CS hits = hits + 1 hits = hits + 1 CS printf(“Bye”); printf(“Bye”); (Hỗ trợ Atomicity : Cần bảo đảm tính “độc quyền truy xuất” (Mutual Exclusion) cho miền găng (CS) 10/28/2005 Trần Hạnh Nhi 12
  13. Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 13
  14. Phối hợp hoạt động P2 P1 (2) Send(“yêu”); (1) Send(“Anh”); P3 P4 (3) Send(“em”); (4) Send(“Không”); 10/28/2005 Trần Hạnh Nhi 14
  15. Chuyện gì đã xảy ra ? P1 P3 (1) Send(“Anh”); (3) Send(“em”); P2 P4 (2) Send(“yêu”); (4) Send(“Không”); P3 P2 (3) printf(“em”); (2) Send(“yêu”); P4 P1 (4) Send(“Không”); (1)Send(“Anh”);
  16. Phối hợp xử lý P1 P2 Job1; Job2; Làm thế nào bảo đảm trình tự thực hiện Job1 - Job2 ? P1 và P2 thực hiện “hẹn hò” (Rendez-vous) với nhau Hỗ trợ Rendez-vous : Bảo đảm các tiến trình phối hợp với nhau theo 1 trình tự xử lý định trước. 10/28/2005 Trần Hạnh Nhi 16
  17. Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 17
  18. Bài toán đồng bộ hoá (Synchronization) Nhiều tiến trình chia sẻ tài nguyên chung đồng thời : Tranh chấp Race Condition Nhu cầu “độc quyền truy xuất” (Mutual Exclusion) Các tiến trình phối hợp hoạt động : Tương quan diễn tiến xử lý ? Nhucầu“hòhẹn”(Rendez-vous) Thực hiện đồng bộ hoá : Lập trình viên đề xuất chiến lược Các tiến trình liên quan trong bài toán phải tôn trọng các luậtđồng bộ Giải pháp sử dụng các cơ chế đồng bộ : Do lập trình viên /phần cứng / HĐH / NNLT cung cấp 10/28/2005 Trần Hạnh Nhi 18
  19. Mô hình đảm bảo Mutual Exclusion Nhiệm vụ của lập trình viên: Thêm các đoạn code đồng bộ hóa vào chương trình gốc Thêm thế nào : xem mô hình sau Kiểm tra và dành quyền vào CS CS; Từ bỏ quyền sử dụng CS 10/28/2005 Trần Hạnh Nhi 19
  20. Mô hình tổ chức phối hợp giữa hai tiến trình Nhiệm vụ của lập trình viên: Thêm các đoạn code đồng bộ hóa vào 2 chương trình gốc Thêm thế nào : xem mô hình sau P1 P2 Job1; Chờ ; Báo hiệu ; Job2; Nhiều tiến trình hơn thì sao ? Không có mô hình tổng quát Tùy thuộc bạn muốn hẹn hò ra sao ☺ 10/28/2005 Trần Hạnh Nhi 20
  21. Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy wating Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 21
  22. Giải pháp đồng bộ hoá Một phương pháp giải quyết tốt bài toán đồng bộ hoá cần thoả mản 4 điều kiện sau: Mutual Exclusion : Không có hai tiến trình cùng ở trong miền găng cùng lúc. Progess : Một tiến trình tạm dừng bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng Bounded Waiting : Không có tiến trình nào phải chờ vô hạn để được vào miền găng. 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. 10/28/2005 Trần Hạnh Nhi 22
  23. Các giải pháp đồng bộ hoá Nhóm giải pháp Busy Waiting Phần mềm 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 Phần cứng Cấm ngắt Chỉ thị TSL Nhóm giải pháp Sleep & Wakeup Semaphore Monitor Message 10/28/2005 Trần Hạnh Nhi 23
  24. Các giải pháp “Busy waiting” While (chưa có quyền) donothing() ; 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 10/28/2005 Trần Hạnh Nhi 24
  25. Nhóm giải pháp Busy-Waiting Các giải pháp Busy Waiting Các giải pháp phần mềm Giải pháp biến cờ hiệu Giải pháp kiểm tra luân phiên Giải pháp Peterson Phần cứng Cấm ngắt Chỉ thị TSL 10/28/2005 Trần Hạnh Nhi 25
  26. Giải pháp phần mềm 1: Sử dụng biến cờ hiệu int lock = 0 P0 P1 NonCS; NonCS; while (lock == 1); // wait while (lock == 1); // wait lock = 1; lock = 1; CS; CS; lock = 0; lock = 0; NonCS; NonCS; 10/28/2005 Trần Hạnh Nhi 26
  27. Giải pháp phần mềm 1: Tình huống int lock = 0 P0 P1 NonCS; NonCS; while (lock == 1); // wait while (lock == 1); // wait lock = 1; lock = 1; CS; CS; lock = 0; lock = 0; NonCS; NonCS; 10/28/2005 Trần Hạnh Nhi 27
  28. Nhận xét Giải pháp phần mềm 1: Biến cờ hiệu Có thể mở rộng cho N tiến trình Không bảo đảm Mutual Exclusion Nguyên nhân ? while ( lock == 1); // wait CS ! Bị ngắt xử lý lock = 1; Tài nguyên dùng chung Bản thân đoạn code kiểm tra và dành quyền cũng là CS ! 10/28/2005 Trần Hạnh Nhi 28
  29. Giải pháp phần mềm 2 : Kiểm tra luân phiên int turn = 1 P0 P1 NonCS; NonCS; while (turn !=0); // wait while (turn != 1); // wait CS; CS; turn = 1; turn = 0; NonCS; NonCS; 10/28/2005 Trần Hạnh Nhi 29
  30. Giải pháp phần mềm 2 : Tình huống int turn = 1 P0 P1 turn ==1 CS; Wait turn = 0; CS; NonCS turn = 1 NonCS; CS ? (turn ==1) P0 không vào được CS lần 2 khi P1 dừng trong NonCS ! 10/28/2005 Trần Hạnh Nhi 30
  31. Nhận xét Giải pháp 2: Kiểm tra luân phiên Chỉ dành cho 2 tiến trình Bảo đảm Mutual Exclusion Chỉ có 1 biến turn, tại 1 thời điểm chỉ cho 1 tiến trình turn vào CS Không bảo đảm Progress Nguyên nhân ? “Mờ của” cho người = “Đóng cửa” chính mình ! 10/28/2005 Trần Hạnh Nhi 31
  32. Giải pháp phần mềm 3 : Peterson’s Solution Kết hợp ý tưởng của 1 & 2, các tiến trình chia sẻ: int turn; //đến phiên ai int interest[2] = FALSE; //interest[i] = T : Pi muốn vào CS Pi NonCS; j = 1 – i; interest[i] = TRUE; turn = j; while (turn==j && interest[j]==TRUE); CS; interest[i] = FALSE; NonCS; 10/28/2005 Trần Hạnh Nhi 32
  33. Giải pháp phần mềm 3 : Peterson Pj NonCS; i = 1 – j; interest[j] = TRUE; turn = i; while (turn==i && interest[i]==TRUE); CS; interest[j] = FALSE; NonCS; 10/28/2005 Trần Hạnh Nhi 33
  34. Nhận xét giải pháp phần mềm 3: Peterson Là giải pháp phần mềm đáp ứng được cả 3 điều kiện Mutual Exclusion : Pi chỉ có thể vào CS khi: interest[j] == F hay turn == i Nếu cả 2 muốn về thì do turn chỉ có thể nhận giá trị 0 hay 1 nên chỉ có 1 tiến trình vào CS Progress Sử dụng 2 biến interest[i] riêng biệt => trạng thái đối phương không khoá mình được Bounded Wait : interest[i] và turn đều có thay đổi giá trị Không thể mở rộng cho N tiến trình 10/28/2005 Trần Hạnh Nhi 34
  35. Nhận xét chung về các giải pháp phần mềm trong nhóm Busy-Waiting Không cần sự hỗ trợ của hệ thống Dễ sai, Khó mở rộng Giải pháp 1 nếu có thể được hỗ trợ atomicity thì sẽ tốt Nhờ đến phần cứng ? 10/28/2005 Trần Hạnh Nhi 35
  36. Nhóm Busy-Waiting - Các giải pháp phần cứng Các giải pháp Busy Waiting Các giải pháp phần mềm Giải pháp biến cờ hiệu Giải pháp kiểm tra luân phiên Giải pháp Peterson Các giải pháp phần cứng Cấm ngắt Test&Set lock Instruction 10/28/2005 Trần Hạnh Nhi 36
  37. Nhóm Busy-Waiting - Giải pháp phần cứng 1: Cấm ngắt NonCS; Disable Interrupt; CS; Enable Interrupt; NonCS; Disable Interrupt : Cấm mọi ngắt, kể cả ngắt đồng hồ Enable Interrupt : Cho phép ngắt 10/28/2005 Trần Hạnh Nhi 37
  38. Giải pháp phần cứng 1: Cấm ngắt Thiếu thận trọng Nếu tiến trình bị khoá trong CS ? System Halt Cho phép tiến trình sử dụng một lệnh đặc quyền Quá liều ! Máy có N CPUs ? Không bảo đảm được Mutual Exclusion 10/28/2005 Trần Hạnh Nhi 38
  39. Nhóm Busy-Waiting - Giải pháp phần cứng 2: chỉ thị TSL() CPU hỗtrợprimitive Test and Set Lock Trả về giá trị hiện hành của 1 biến, và đặt lại giá trị True cho biến Thực hiện một cách không thể phân chia TSL (boolean &target) { TSL = target; target = TRUE; } 10/28/2005 Trần Hạnh Nhi 39
  40. Aùp dụng TSL int lock = 0 Pi NonCS; while (TSL(lock)); // wait CS; lock = 0; NonCS; 10/28/2005 Trần Hạnh Nhi 40
  41. Nhận xét chung các giải pháp phần cứng trong nhóm Busy- Waiting Cần được sự hỗ trợ của cơ chế phần cứng Không dễ, nhất là trên các máy có nhiều bộ xử lý Dễ mở rộng cho N tiến trình 10/28/2005 Trần Hạnh Nhi 41
  42. Nhận xét chung cho các giải pháp trong nhóm Busy Waiting Sử dụng CPU không hiệu quả Liên tục kiểm tra điều kiện khi chờ vào CS Khắc phục Khoá các tiến trình chưa đủ điều kiện vào CS, nhường CPU cho tiến trình khác Phải nhờ đến Scheduler Wait and See 10/28/2005 Trần Hạnh Nhi 42
  43. Các giải pháp đồng bộ hoá Nhóm giải pháp Busy Waiting Phần mềm 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 Phần cứng Cấm ngắt Chỉ thị TSL Nhóm giải pháp Sleep & Wakeup Semaphore Monitor Message 10/28/2005 Trần Hạnh Nhi 43
  44. 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 CS Khi CS trống, sẽ được đánh thức để vào CS Cần được Hệ điều hành hỗ trợ Vì phải thay đổi trạng thái tiến trình 10/28/2005 Trần Hạnh Nhi 44
  45. Ý tưởng Hệ Điều hành hỗ trợ 2 primitive : Sleep() : Tiến trình gọi sẽ nhận trạng thái Blocked WakeUp(P): Tiến trình P nhận trạng thái Ready Áp dụng Sau khi kiểm tra điều kiện sẽ vào CS hay gọi Sleep() tùy vào kết quả kiểm tra Tiến trình vừa sử dụng xong CS sẽ đánh thức các tiến trình bị Blocked trước đó 10/28/2005 Trần Hạnh Nhi 45
  46. Áp dụng Sleep() and Wakeup() int busy; // busy ==0 : CS trống int blocked; // đếm số tiến trình bị Blocked chờ vào CS if (busy) { blocked = blocked + 1; Sleep(); } else busy = 1; CS; busy = 0; if(blocked) { WakeUp(P); blocked = blocked - 1; } 10/28/2005 Trần Hạnh Nhi 46
  47. Vấn đề với Sleep & WakeUp P1 blocked P1 P2 vĩnh viễn if (busy) { if (busy) { blocked = blocked + 1; blocked = blocked + 1; Sleep(); Sleep(); } } else busy = 1; else busy = 1; WakeUp CS; bị “lạc” CS; busy = 0; busy = 0; if(blocked) { if(blocked) { WakeUp(P); WakeUp(P); blocked = blocked - 1; blocked = blocked - 1; } } Nguyên nhân : Việc kiểm tra điều kiện và động tác từ bỏ CPU có thể bị ngắt quãng Bản thân các biến cờ hiệu không được bảo vệ 10/28/2005 Trần Hạnh Nhi 47
  48. Cài đặt các giải pháp Sleep & WakeUp ? Hệ điều hành cần hỗ trợ các cơ chế cao hơn Dựa trên Sleep&WakeUp Kết hợp các yếu tố kiểm tra Thi hành không thể phân chia Nhóm giải pháp Sleep & Wakeup Semaphore Monitor Message 10/28/2005 Trần Hạnh Nhi 48
  49. Giải pháp Sleep & Wakeup 1: Semaphore Được đề nghị bởi Dijkstra năm 1965 Các đặc tính : Semaphore s; Có 1 giá trị Semaphore s; // s >=0 Chỉ được thao tác bởi 2 primitives : Down(s) Up(s) Các primitive Down và Up được thực hiện không thể phân chia 10/28/2005 Trần Hạnh Nhi 49
  50. Cài đặt Semaphore (Sleep & Wakeup) Giá trị bên trong của semaphore typedef struct { int value; struct process* L; Danh sách các tiến trình đang } Semaphore ; bị block đợi semaphore nhận giá trị dương Semaphore được xem như là một resource Các tiến trình “yêu cầu” semaphore : gọi Down(s) Nếu không hoàn tất được Down(s) : chưa được cấp resource Blocked, được đưa vào s.L Cần có sự hỗ trợ của HĐH Sleep() & Wakeup() 10/28/2005 Trần Hạnh Nhi 50
  51. Cài đặt Semaphore (Sleep & Wakeup) Down (S) Up(S) { { S.value ; S.value ++; if S.value < 0 if S.value ≤ 0 { { Add(P,S.L); Remove(P,S.L); Sleep(); Wakeup(P); } } } } 10/28/2005 Trần Hạnh Nhi 51
  52. Sử dụng Semaphore Tổ chức “độc quyền truy xuất” Pi Down (s) Semaphore s = ?1 CS; Up(s) Tổ chức “hò hẹn” P1 : P2: Semaphore s = ?0 Job1; Down (s); Up(s) Job2; 10/28/2005 Trần Hạnh Nhi 52
  53. Nhận xét Semaphores Là một cơ chế tốt để thực hiện đồng bộ Dễ dùng cho N tiến trình Nhưng ý nghĩa sử dụng không rõ ràng MutualExclusion : Down & Up Rendez-vous : Down & Up Chỉ phân biệt qua mô hình Khó sử dụng đúng Nhầm lẫn 10/28/2005 Trần Hạnh Nhi 53
  54. Giải pháp Sleep & Wakeup 2: Monitor Đề xuất bởi Hoare(1974) & Brinch (1975) Là cơ chế đồng bộ hoá do NNLT cung cấp Hỗ trợ cùng các chức năng như Semaphore Dễ sử dụng và kiểm soát hơn Semaphore Bảo đảm Mutual Exclusion một cách tự động Sử dụng biến điều kiện để thực hiện Synchronization 10/28/2005 Trần Hạnh Nhi 54
  55. Monitor : Ngữ nghĩa và tính chất(1) Monitor M Share variable: i,j; Là một module chương trình định nghĩa Các CTDL, đối tượng dùng chung Các phương thức xử lý các đối tượng này Bảo đảm tính encapsulation Các tiến trình muốn truy xuất dữ liệu MethodA bên trong monitor phải dùng các phương MethodB thức của monitor : MethodC i=0 P1 : M.C() // i=5 prinf(j)i=5 P2: M.B() // printf(j) 10/28/2005 Trần Hạnh Nhi 55
  56. Monitor : Ngữ nghĩa và tính chất(2) Entry queue P6 P7 P8 Share variable: i,j; Tự động bảo đảm Mutual Exclusion Tại 1 thời điểm chỉ có 1 tiến trình được thực hiện các phương thức của Monitor Các tiến trình không thể vào Monitor sẽ được đưa vào Entry queue của Monitor MethodA Ví dụ MethodB P1 : M.A(); i = 0 MethodC P6 : M.B(); printf(i) P7 : M.A(); i=5 P8 : M.C(); P1 10/28/2005 Trần Hạnh Nhi 56
  57. Monitor : Ngữ nghĩa và tính chất(3) Entry queue P6 P7 P8 Share variable: i,j; Hỗ trợ Synchronization với các condition Condition variable: variables C1: P2 P4 P1 Wait(c) : Tiến trình gọi hàm sẽ bị blocked C2: P3 P5 Signal(c): Giải phóng 1 tiến trình đang bị blocked trên biến điều kiện c MethodA C.queue : danhsáchcáctiếntrìnhblocked MethodB trên c i=0; signal(c1)MethodC Trạng thái tiến trình sau khi gọi Signal? P1 Blocked. Nhường quyền vào monitor cho tiến wait(C1); trình được đánh thức i=5 signal(C2 ); Tiếp tục xử lý hết chu kỳ, rồi blocked 10/28/2005 Trần Hạnh Nhi 57
  58. Sử dụng Monitor Tổ chức “độc quyền truy xuất” Monitor M Pi RC; M.AccessMutual(); //CS Function AccessMutual CS; // access RC Tổ chức “hò hẹn” Monitor M Condition c; Function F1 Job1; P1 : P2: Signal(c); M.F1(); M.F2(); Function F2 Wait(c); Job2; 10/28/2005 Trần Hạnh Nhi 58
  59. Giải pháp Sleep & Wakeup 3: Message Được hỗ trợ bởi HĐH Đồng bộ hóa trên môi trường phân tán 2 primitive Send & Receive Cài đặt theo mode blocking 1. Send Request 3. Send Finish Server P 2. Receive Accept 10/28/2005 Trần Hạnh Nhi 59
  60. Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 60
  61. Bàitoánđồngbộkinhđiển1: Producer - Consumer (Bounded-Buffer Problem) Mô tả : 2 tiến trình P và C hoạt động đồng hành P sản xuất hàng và đặt vào Buffer C lấy hàng từ Buffer đi tiêu thụ Buffer có kích thước giới hạn P Tình huống BufferBuffer (N)(N) C P và C đồng thời truy cập Buffer ? P thêm hàng vào Buffer đầy ? C lấy hàng từ Buffer trống ? P không được ghi dữ liệu vào buffer đã đầy (Rendez-vous) C không được đọc dữ liệu từ buffer đang trống (Rendez-vous) P và C không được thao tác trên buffer cùng lúc (Mutual Exclusion) 10/28/2005 Trần Hạnh Nhi 61
  62. Producer – Consummer : Giải pháp Semaphore Các biến dùng chung giữa P và C BufferSize = N; // số chỗ trong bộ đệm semaphore mutex = 1 ; // kiểm soát truy xuất độc quyền semaphore empty = BufferSize; // số chỗ trống semaphore full = 0; // số chỗ đầy int Buffer[BufferSize]; // bộ đệm dùng chung 10/28/2005 Trần Hạnh Nhi 62
  63. Producer – Consummer : Giải pháp Semaphore Producer() Consumer() { { int item; int item; while (TRUE) while (TRUE) { { produce_item(&item); down(&full); down(&empty); down(&mutex); down(&mutex) remove_item(&item,Buffer); enter_item(item,Buffer); up(&mutex); up(&mutex); up(&empty); up(&full); consume_item(item); } } } } 10/28/2005 Trần Hạnh Nhi 63
  64. P&C - Giải pháp Semaphore: Thinking Producer() Consumer() { { int item; int item; while (TRUE) while (TRUE) { { produce_item(&item); down(&mutex); down(&mutex) down(&full); down(&empty); remove_item(&item,Buffer); enter_item(item,Buffer); up(&mutex); up(&mutex); up(&empty); up(&full); consume_item(item); } } } } 10/28/2005 Trần Hạnh Nhi 64
  65. Producer – Consummer : Giải pháp Monitor monitor ProducerConsumer procedure remove(); condition full, empty; { int Buffer[N], count; if (count == 0) procedure enter(); wait(empty) { remove_item(&item,Buffer); if (count == N) count ; wait(full); if (count == N-1) enter_item(item,Buffer); signal(full); count ++; } if (count == 1) count = 0; signal(empty); end monitor; } 10/28/2005 Trần Hạnh Nhi 65
  66. Producer – Consummer : Giải pháp Monitor Producer() Consumer(); { { int item; int item; while (TRUE) while (TRUE) { { produce_item(&item); ProducerConsumer.remove; ProducerConsumer.enter; consume_item(item); } } } } 10/28/2005 Trần Hạnh Nhi 66
  67. Producer – Consummer : Giải pháp Message Producer() Consumer(); { { int item; int item; message m; Coi chừng message m; Deadlock for(0 to N) send(producer, Request); while (TRUE) while (TRUE) { { produce_item(&item); receive(producer, &m); receive(consumer, Request); remove_item(&m,&item); create_message(&m, item); send(producer, Request); send(consumer,&m); consumer_item(item); } } } } 10/28/2005 Trần Hạnh Nhi 67
  68. Bài toán đồng bộ hoá kinh điển 2: Readers & Writers R2 Mô tả : N tiến trình Ws và Rs hoạt động đồng hành R3 Rs và Ws chia sẻ CSDL R1 W cập nhật nội dung CSDL W1 W2 Rs truy cập nội dung CSDL Tình huống Các Rs cùng truy cập CSDL ? Database W đang cập nhật CSDL thì các Rs truy cập CSDL ? Các Rs đang truy cập CSDL thì W muốn cập nhật CSDL ? W không được cập nhật dữ liệu khi có ít nhất một R đang truy xuất CSDL (ME) Rs không được truy cập CSDL khi một W đang cập nhật nội dung CSDL (ME) Tại một thời điểm , chỉ cho phép một W được sửa đổi nội dung CSDL (ME) 10/28/2005 Trần Hạnh Nhi 68
  69. Readers-Writers với “active readers” 10/28/2005 Trần Hạnh Nhi 69
  70. Readers-writers với một “active writer” 10/28/2005 Trần Hạnh Nhi 70
  71. Ưu tiên ai hơn đây ? 10/28/2005 Trần Hạnh Nhi 71
  72. Readers & Writers W độc quyền truy xuất CSDL W hiện tại kết thúc cập nhật CSDL : ai vào ? Cho W khác vào, các Rs phải đợi Ưu tiên Writer, Reader có thể starvation Cho các Rs vào, Ws khác phải đợi Ưu tiên Reader, Writer có thể starvation 10/28/2005 Trần Hạnh Nhi 72
  73. Readers & Writers : Giải pháp Semaphore Các biến dùng chung giữa Rs và Ws semaphore db = 1; // Kiểm tra truy xuất CSDL 10/28/2005 Trần Hạnh Nhi 73
  74. R&W : Giải pháp Semaphore (1) Reader() Writer() { { down(&db); down(&db); read-db(Database); write-db(Database); up(&db); up(&db); } } Chuyện gì xảy ra ? Chỉ có 1 Reader được đọc CSDL tại 1 thời điểm ! 10/28/2005 Trần Hạnh Nhi 74
  75. R&W : Giải pháp Semaphore (2) Reader() Writer() { { rc = rc +1; down(&db); if (rc ==1) write-db(Database); down(&db); up(&db); read-db(Database); } rc = rc – 1; Đúng chưa ? if (rc == 0) up(&db); rc là biến dùng chung giữa các Reader } CS đó 10/28/2005 Trần Hạnh Nhi 75
  76. Readers & Writers : Giải pháp Semaphore Các biến dùng chung giữa Rs và Ws semaphore db = 1; // Kiểm tra truy xuất CSDL Các biến dùng chung giữa Rs int rc; // Số lượng tiến trình Reader semaphore mutex = 1; // Kiểm tra truy xuất rc 10/28/2005 Trần Hạnh Nhi 76
  77. R&W : Giải pháp Semaphore (3) Reader() Writer() { { down(&mutex); down(&db); rc = rc +1; write-db(Database); if (rc ==1) up(&db); down(&db); } up(mutex); read-db(Database); down(mutex); Ai được ưu tiên ? rc = rc – 1; if (rc == 0) up(&db); up(mutex); } 10/28/2005 Trần Hạnh Nhi 77
  78. R&W : Giải pháp Semaphore (Thinking ) Reader() Writer() { { down(&mutex); down(&db); rc = rc +1; write-db(Database); up(mutex); up(&db); if (rc ==1) } down(&db); read-db(Database); down(mutex); ??? hê, hê, hê ☺ rc = rc – 1; up(mutex); if (rc == 0) up(&db); } 10/28/2005 Trần Hạnh Nhi 78
  79. R&W: Giải pháp Monitor monitor ReaderWriter procedure W1(); ? Database; { procedure R1(); } { procedure W (); } { procedure R (); } { } 10/28/2005 Trần Hạnh Nhi 79
  80. monitor ReaderWriter procedure BeginWrite() { condition OKWrite, OKRead; if (busy || rc != 0) int rc = 0; wait(OKWrite); Boolean busy = false; busy = true; } procedure BeginRead() { procedure FinishWrite() if (busy) { wait(OKRead); busy = false; rc++; if (OKRead.Queue) signal(OKRead); signal(OKRead); } else procedure FinishRead() signal(OKWrite); { } rc ; end monitor; if (rc == 0) signal(OKWrite); }
  81. Reader&Writer : Giải pháp Monitor Reader() Writer(); { { RW.BeginRead(); RW.BeginWrite(); Read-db(Database); Write-db(Database); RW.FinishRead(); RW.FinishWrite(); } } 10/28/2005 Trần Hạnh Nhi 81
  82. Bài toán đồng bộ hoá kinh điển 3: Bửa ăn của các Triết gia (Dining Philosophers) Năm triết gia ngồi chung quanh bàn ăn món spaghetti (yum yum) Trên bàn có 5 cái nĩa được đặt giữa 5 cái đĩa (xem hình) Để ăn món spaghetti mỗi người cần có 2 cái nĩa Triết gia thứ i: Thinking Eating Chuyện gì có thể xảy ra ? 10/28/2005 Trần Hạnh Nhi 82
  83. Dining Philosophers : Tình huống nguy hiểm 2 triết gia “giành giật” cùng 1 cái nĩa Tranh chấp Cần đồng bộ hoá hoạt động của các triết gia 10/28/2005 Trần Hạnh Nhi 83
  84. Dining Philosophers : Giải pháp đồng bộ semaphore fork[5] = 1; Philosopher (i) { while(true) { down(fork[i]); down(fork[i+1 mod 5]) eat; up(fork[i]); up(fork[i+1 mod 5]); think; Deadlock } 10/28/2005 Trần Hạnh Nhi 84
  85. Dining Philosophers : Thách thức Cần đồng bộ sao cho: Không có deadlock Không có starvation 10/28/2005 Trần Hạnh Nhi 85