›

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

pdf 56 trang huongle 17401
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 V: Đồng bộ hóa tiến trình - Trần Công Án", để 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_v_dong_bo_hoa_tien_trinh_tran.pdf

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

  1. CT107. Hệ Điều Hành Chương 5. Đồng Bộ Hóa Tiến Trình Giảng viên: Trần Công Án (tcan@cit.ctu.edu.vn) Bộ môn Mạng máy tính & Truyền thông Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ 2014
  2. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Mục Tiêu Giới thiệu vấn đề miền tương trục và các giải pháp để giải quyết vấn đề miền tương trục, nhằm đảm bảo sự nhất quán của dữ liệu được chia sẻ giữa các tiến trình cạnh tranh trong miền tương trục. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 2
  3. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Nội Dung Giới thiệu (Background) Vấn đề miền tương trục (Critical-section problem) Các giải pháp cho vấn đề miền tương trục Đồng bộ hóa bằng phần mềm (Software Sync.) Đồng bộ hóa bằng phần cứng (Hardware Sync.) Hiệu báo (Semaphores) Các bài toán đồng bộ hóa Monitors TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 3
  4. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Giới thiệu (Background) Cạnh tranh và sự nhất quán dữ liệu Cạnh Tranh Và Sự Nhất Quan Dữ Liệu I Các tiến trình thực thi đồng thời, chia sẻ dữ liệu dùng chung có thể dẫn đến tình trạng không nhất quán (inconsistency) của dữ liệu. I Nhất quán = đúng đắn và chính xác; tùy thuộc vào ngữ cảnh, giao dịch. I Có 2 lý do chính để thực hiện đồng thời (cạnh tranh) các tiến trình: I Tăng hiệu suất sử dụng tài nguyên hệ thống. I Giảm thời gian đáp ứng trung bình của hệ thống. I Việc duy trì sự nhất quán của dữ liệu yêu cầu một cơ chế để đảm bảo sự 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. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 4
  5. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Giới thiệu (Background) Cạnh tranh và sự nhất quán dữ liệu Ví Dụ 1 – Giao Dịch Cạnh Tranh I Cho hai giao dịch: T1 T2 I T1: A mua hàng trị giá 50$ của P R(A) R(A) (50$: A P) → A = A - 50 A = A - 100 I T2: B mua hàng trị giá 100$ của P W(A) W(A) (100$: B P) → R(P) R(P) I Khởi tạo ban đầu: A=500; B=500; P=1000 P = P + 50 P = P + 100 W(P) W(P) I Yêu cầu về tính nhất quán: (A + B + P) không đổi; cụ thể hơn: I giá trị A, B, P sau khi thực hiện T1, T2 là: A=450; B=400; P=1150 I Nhận xét: I Nếu thực hiện tuần tự T1 T2 hoặc T2 T1, dữ liệu sẽ nhất quán. → → I Nếu thực hiện cạnh tranh (đồng thời), dữ liệu sẽ nhất quán??? TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 5
  6. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Giới thiệu (Background) Cạnh tranh và sự nhất quán dữ liệu Ví Dụ 1 – Giao Dịch Cạnh Tranh T1 T2 A/B P T1 T2 A/B P R(A) R(A) A = A - 50 A = A – 50 W(A) 450 R(B) R(B) B = B - 100 B = B - 100 W(B) 400 W(B) 400 W(A) 450 R(P) R(P) P = P + 50 P = P + 50 R(P) W(P) 1050 W(P) 1050 R(P) P = P + 100 P = P + 100 W(P) 1100 W(P) 1150 Schedule 1 Schedule 2 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 6
  7. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Giới thiệu (Background) Cạnh tranh và sự nhất quán dữ liệu Ví Dụ 2 – Bài Toán Nhà SX - Người Tiêu Thụ I Dữ liệu chia sẻ (kho hàng, có giới hạn): #define struct { } item; item buffer[BUFFER_SIZE]; int in_item = 0; int out_item = 0; int counter = 0; TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 7
  8. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Giới thiệu (Background) Cạnh tranh và sự nhất quán dữ liệu Ví Dụ 2 – Bài Toán Nhà SX - Người Tiêu Thụ I Nhà sản xuất (S): while(true){ /* produce an item in next produced*/ while (counter == BUFFER SIZE) ;/* do nothing*/ buffer[in_item] = next_produced; in_item = (in_item + 1) % BUFFER SIZE; counter++; } TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 8
  9. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Giới thiệu (Background) Cạnh tranh và sự nhất quán dữ liệu Ví Dụ 2 – Bài Toán Nhà SX - Người Tiêu Thụ I Người tiêu thụ (T): while(true){ while (counter == 0) ;/* do nothing*/ next_consumed = buffer[out_item]; out_item = (out_item + 1) % BUFFER SIZE; counter ; /* consume the item in next consumed*/ } TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 9
  10. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Giới thiệu (Background) Cạnh tranh và sự nhất quán dữ liệu Ví Dụ 2 – Bài Toán Nhà SX - Người Tiêu Thụ I Dữ liệu chia sẻ giữa producer và consumer: biến counter. I Điều kiện để đảm bảo tính nhất quán của biến counter: các câu lệnh counter++ và counter phải được thực thi một cách “nguyên tử” và “cô lập”. I Nguyên tử: không thể chia nhỏ (hoặc “hoặc tất cả, hoặc không”) I Cô lập: các t/trình không truy xuất các g/trị không nhất quán của nhau I Vấn đề gì có thể xảy ra đối với counter? I counter++ trong ngôn ngữ máy: I counter trong ngôn ngữ máy: register1 = counter register2 = counter register1 = register1 + 1 register2 = register2 - 1 counter = register1 counter = register2 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 10
  11. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Giới thiệu (Background) Cạnh tranh và sự nhất quán dữ liệu Ví Dụ 2 – Bài Toán Nhà SX - Người Tiêu Thụ I Xét một lịch trình thực thi xen kẽ (cạnh tranh) của hai tiến trìnhS và T trong hệ thống, với giá trị counter = 5: S1: register1 = counter (register1 = 5) S2: register1 = register1 + 1 (register1 = 6) P1: register2 = counter (regster2 = 5) P2: register2 = register2 - 1 (register2 = 4) S3: counter = register1 (counter = 6) P3: counter = register2 (counter = 4) giá trị cuối cùng của counter là4 (hoặc6 nếu S3 sau P3), trong ⇒ khi giá trị nhất quán của counter trong trường hợp này là 5. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 11
  12. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Giới thiệu (Background) Tình trạng tranh đua (Race condition) Tình Trạng “Tranh Đua” (Race Condition) I Là tình trạng mà nhiều tiến trình cùng truy cập và thay đổi lên dữ liệu được chia sẻ, và giá trị cuối cùng của dữ liệu chia sẻ phụ thuộc vào quá trình hoàn thành sau cùng. I giá trị củaP trong ví dụ 1 I hoặc giá trị biến counter trong ví dụ 2 I Tình trạng tranh đua có thể dẫn đến tình trạng không nhất quán. I Để ngăn chặn tình trạng tranh đua, các quá trình cạnh tranh cần phải được đồng bộ hóa (synchronize). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 12
  13. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Vấn đề miền tương trục (Critical-section problem) Vấn Đề Miền Tương Trục (CSP) I Xét 1 hệ thống có n tiến trình đang cạnh tranh P0, P1, , Pn−1 { } I Miền tương trục (critical section): là một đoạn mã lệnh của các tiến trình có chứa các hành động truy cập dữ liệu được chia sẻ như: thay đổi các biến dùng chung, cập nhật CSDL, ghi tập tin, . . . Để tránh tình trạng tranh đua, các hệ thống phải đảm bảo khi một tiến⇒ trình đang trong miền tương trục, không có một tiến trình nào khác được phép chạy trong miền tương trục của nó. I Vấn đề miền tương trục (critical-section problem): Thiết kế các giao thức để các tiến trình có thể sử dụng để hợp tác/cạnh tranh với nhau. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 13
  14. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Vấn đề miền tương trục (Critical-section problem) Vấn Đề Miền Tương Trục (CSP) I Cần phải xác định được phần entry section do và exit section. { I Mỗi tiến trình phải xin phép để được vào entry section miền tương trục (đi qua vùng entry critical section section), và sau đó thoát khỏi miền tương trục (đi qua vùng exit section) và thực hiện exit section phần còn lại (remainder section). remainder section I Giải pháp cho vấn đề miền tương trục tương đối phức tạp với với các hệ thống while (true); định thời trưng dụng. } TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 14
  15. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các giải pháp cho vấn đề miền tương trục Yêu Cầu Đối Với Các Giải Pháp Cho CSP I Một giải pháp cho vấn đề miền tương trục phải thỏa 3 yêu cầu: 1. Loại trừ hỗ tương (mutual exclusion): Nếu 1 t/trình đang thực thi trong miền tương trục, không một tiến trình nào khác được đi vào miền tương trục của chúng. 2. Tiến triển (progress): Nếu không có tiến trình nào đang thực thi trong miền tương trục và tồn tại tiến trình đang chờ được thực thi trong miền tương trục của chúng, thì việc lựa chọn cho một quá trình bước vào miền tương trục không thể bị trì hoãn vô hạn. 3. Chờ đợi hữu hạn (bounded wait): Mỗi t/trình chỉ phải chờ để được vào miền tương trục trong một khoảng t/gian có hạn định (không xảy ra tình trạng “chết đói” – starvation). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 15
  16. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các giải pháp cho vấn đề miền tương trục Phân Loại Các Giải Pháp I Các giải pháp phần mềm: dựa trên các giải thuật phần mềm, như: I Cho trường hợp chỉ có 2 tiến trình cạnh tranh: I Giải thuật 1 và 2 I Giải thuật Peterson (Peterson’s algorithm) I Cho trường hợp có n 2 tiến trình cạnh tranh: ≥ I Giải thuật Bakery I Các giải pháp phần cứng: I Lệnh vô hiệu hóa ngắt (disable interrupt) I Lệnh máy đặc biệt: TestAndSet TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 16
  17. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần mềm (Software Sync.) Giải thuật cho trường hợp có 2 tiến trình GT1 – Giải Thuật Chờ Bận 1 (Busy Wait) I Điều khiển cạnh tranh giữa 2 tiến trình Pi và Pj . I Dùng 1 biến khóa chia sẻ để đ/khiển việc vào miền tương trục. I int turn = 0;//initialise turn=0 I turn = i Pi có thể vào miền tương trục. ⇒ I Tổ chức đoạn mã của 1 tiến trình Pi : do{ while (turn != i) ; I Nhận xét: critical section I Loại trừ hỗ tương: turn = j; I Tiến triển: remainder section ⇒ Không thỏa yêu cầu. } while(true); TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 17
  18. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần mềm (Software Sync.) Giải thuật cho trường hợp có 2 tiến trình GT2 – Giải Thuật Chờ Bận 2 (Busy Wait) I Dùng các biến khóa riêng để đ/khiển việc vào miền tương trục. I boolean flag[2]; I Khởi tạo: flag[0] = flag[1] = false I flag[i] = true Pi sẵn sàng vào miền tương trục. ⇒ I Tổ chức đoạn mã của 1 tiến trình Pi : do{ I Nhận xét: flag[i] := true while (flag[j]) ; I Loại trừ hỗ tương: critical section I Tiến triển: flag[i] = false; ⇒ Giống giải thuật 1. remainder section I Tuy nhiên, mức độ cạnh tranh } while(true); cao hơn. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 18
  19. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần mềm (Software Sync.) Giải thuật cho trường hợp có 2 tiến trình Giải Thuật Peterson I Kết hợp cả biến khóa chia sẻ (GT1) và biến khóa riêng (GT2): I int turn; //turn = i: Pi được phép vào miền tương trục. I boolean flag[2]; //flag[i] = true: Pi sẵn sàng vào miền tương trục. I Tổ chức đoạn mã của 1 tiến trình Pi : do{ flag[i] := true turn := j; I Nhận xét: while (flag[j] && turn=j) ; I Loại trừ hỗ tương: critical section Tiến triển: flag[i] = false; I remainder section I Chờ đợi hữu hạn: } while(true); TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 19
  20. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần mềm (Software Sync.) Giải thuật cho trường hợp có n tiến trình Giải Thuật Bakery I Miền tương trục cho n tiến trình: I Mỗi t/trình sẽ nhận được 1 số trước khi vào miền tương trục. I Tiến trình có số nhỏ nhất sẽ có quyền ưu tiên cao nhất. I Nếu hai tiến trình Pi và Pj nhận được cùng một số, nếu i < j thì Pi được phục vụ trước. I Bộ sinh số luôn sinh các số theo thứ tự tăng, ví dụ: 1, 2, 3, 3, 3, 4, . . . I Dữ liệu chia sẻ: boolean choosing[n] int number[n] I Khởi tạo: tất cả các phần tử của choosing = false và number = 0. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 20
  21. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần mềm (Software Sync.) Giải thuật cho trường hợp có n tiến trình Giải Thuật Bakery Cho Tiến Trình Pi do{ choosing[i] = true; number[i] = max(number[0], number[1], , number[n-1]) + 1; choosing[i] = false; for (j = 0; j (number #1, i) < (number #2, j) nếu (number #1 < number #2) hoặc (number #1 = number #2) AND (i < j) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 21
  22. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần cứng (Hardware Sync.) Đồng Bộ Hóa Bằng Phần Cứng I Ý tưởng cơ bản của hầu hết các giải pháp bằng phần cứng là bảo vệ miền tương trục bằng khóa. I Giải pháp đơn giản nhất: vô hiệu hóa các ngắt – cho phép tiến trình người dùng vô hiệu hóa các ngắt khi vào miền tương trục, cho đến khi t/trình ra khỏi miền tương trục. I Không có tiến trình nào khác có thể thực thi khi một tiến trình đã vào miền tương trục tránh tình trạng cạnh tranh. ⇒ I Chỉ có thể áp dụng cho hệ thống không trưng dụng. I Không khả thi cho hệ thống đa xử lý (vô hiệu hóa các ngắt trên hệ thống đa xử lý mất nhiều chi phí hiệu năng giảm). ⇒ TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 22
  23. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần cứng (Hardware Sync.) Đồng Bộ Hóa Bằng Phần Cứng I Các giải pháp khả thi hơn: cung cấp các thao tác nguyên tử từ phần cứng (atomic hardware instructions): I test_and_set I compare_and_swap I Các chỉ thị này được hỗ trợ trong các hệ thống hiện đại, có nhiều bộ xử lý. I Nếu các chỉ thị nguyên tử được thực thi cùng lúc (có thể trên các CPU khác nhau) thì chúng sẽ được thực thi tuần tự (theo một thứ tự bất kỳ). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 23
  24. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần cứng (Hardware Sync.) Chỉ thị test_and_set Chỉ Thị test_and_set I Cho phép đọc và sửa nội dung của một word một cách nguyên tử. I Định nghĩa của chỉ thị test_and_set: boolean test_and_set(boolean *target) { boolean rv = *target; *target = true; return rv; } TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 24
  25. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần cứng (Hardware Sync.) Chỉ thị test_and_set Loại Trừ Hỗ Tương Với test_and_set I Dữ liệu chia sẻ: boolean lock = false; I Tiến trình Pi : do{ while (test_and_set(lock)) ;//do nothing critical section lock = false; remainder section } while(true); I Tính chất: I Loại trừ hỗ tương và tiến triển: I Chờ đợi hữu hạn: TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 25
  26. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần cứng (Hardware Sync.) Chỉ thị compare_and_swap Chỉ Thị compare_and_swap I Dùng để hoán chuyển (swap) hai biến. I Định nghĩa của chỉ thị swap: void swap(boolean &oldValue, boolean expected, boolean newValue) { boolean temp = *oldValue; if (*oldValue == expected) *oldValue = newValue; return temp; } I Chỉ thị được thực thi một cách nguyên tử. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 26
  27. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần cứng (Hardware Sync.) Chỉ thị compare_and_swap Loại Trừ Hỗ Tương Với compare_and_swap I Dữ liệu chia sẻ: boolean lock = false; I Tiến trình Pi : do{ while (compare_and_swap(&lock, false, true) != false); critical section lock = false; remainder section } while(true); I Tính chất: I Loại trừ hỗ tương: I Chờ đợi hữu hạn: TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 27
  28. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Đồng bộ hóa bằng phần cứng (Hardware Sync.) Chờ đợi hữu hạn với test_and_set Chờ Đợi Hữu Hạn Với test_and_set I Dữ liệu chia sẻ: I Tiến trình Pi : boolean lock; do{ boolean waiting[n]; waiting[i] = true; key = true; I Khởi tạo: while (waiting[i] && key) lock = false; key = test_and_set(&lock); waiting[1 n] = false; 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); TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 28
  29. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Hiệu báo (Semaphores) Hiệu Báo (Semaphores) I Semephore là công cụ đồng bộ hóa tránh được chờ đợi bận: I Tiến trình chờ đợi vào miền tương trục sẽ ngủ/nghẽn. I Tiến trình đang ngủ/nghẽn sẽ được đánh thức bởi các tiến trình khác. I Semaphore S: là một biến integer, được truy cập qua 2 thao tác nguyên tử: I wait(S): while(S ≤ 0) ;//do nothing(busy wait) S ; I signal(S): S++ I Ưu điểm: ít phức tạp hơn các giải pháp khác. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 29
  30. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Hiệu báo (Semaphores) Đồng bộ hóa dùng Semaphore Đồng Bộ Hóa Dùng Semaphore I Các loại semaphore: I Dữ liệu chia sẻ: I Semaphore đếm (counting semaphore mutex = 1; semaphore): giá trị semaphore I Tiến trình Pi : không giới hạn. do{ I Semaphore nhị phân (binary wait(mutex); semaphore): có giá trị 0 hoặc critical section 1, còn gọi là mutex lock; cài singal(mutex); đặt đơn giản hơn. remainder section } while(true); TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 30
  31. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Hiệu báo (Semaphores) Đồng bộ hóa dùng Semaphore Đồng Bộ Hóa Dùng Semaphore – Ví Dụ I Có 2 tiến trình: P1 với lệnh S1 và P2 với lệnh S2. I Yêu cầu: S2 phải thực thi sau khi S1 hoàn thành. I Cài đặt: I Sử dụng semaphore flag, khởi tạo với giá trị 0. Tiến trình Pi : Tiến trình P2: . . . . S1; wait(flag); signal(flag); S2 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 31
  32. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Hiệu báo (Semaphores) Semaphore không chờ đợi bận Cài đặt Semaphore Không Chờ Đợi Bận I Thao tác signal(S) và wait(S) không tránh được chờ đợi bận. I Cần một cách tiếp cận khác để tránh tình trạng này: I Cấu trúc dữ liệu semaphore: typedef struct { int value; struct process *L; } semaphore; I Hai thao tác cần được cung cấp bởi HĐH: I block(): ngưng (block) tạm thời tiến trình gọi chỉ thị này. I wakeup(P): khởi động lại tiến trình đang bị ngưng P. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 32
  33. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Hiệu báo (Semaphores) Semaphore không chờ đợi bận Các Thao Tác Semaphore Không Chờ Đợi Bận I Các thao tác semaphore wait(S) và signal(S) được định nghĩa lại như sau: void wait(semaphore S) { void signal(semaphore S) { S.value ; S.value++; if (S.value < 0) { if (S.value ≤ 0) { add this process into remove a process P from S.L; S.L; block(); wakeup( P); }//if }//if }//wait() }//signal() I Giá trị semaphore có thể âm (trong tr/hợp chờ đợi bận thì không). I Giá trị âm thể hiện số lượng tiến trình đang chờ đợi trên semaphore. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 33
  34. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Hiệu báo (Semaphores) Semaphore không chờ đợi bận Cài Đặt wait() Và signal() I Yêu cầu: không thể có nhiều hơn 1 tiến trình thực thi wait() hoặc signal() đồng thời critical-section problem. ⇒ I Hệ thống đơn xử lý: vô hiệu hóa các ngắt khi thực thi wait() và signal(). I Hệ thống đa xử lý: dùng chờ đợi bận (spinlock) hay các lệnh nguyên tử (e.g. compare_and_swap()). Không hoàn toàn loại bỏ được chờ đợi bận: di chuyển chờ đợi bận vào⇒ bên trong chỉ thị wait() và signal() – thường là ngắn – nên thời gian chờ đợi bận được giảm đi. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 34
  35. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Hiệu báo (Semaphores) Khóa chết (deadlock) và chết đói (starvation) Khóa Chết Và Chết Đói I Khóa chết: hai hay nhiều t/trình chờ đợi vô hạn một sự kiện, mà sự kiện đó chỉ có thể tạo ra bởi một trong các t/trình đang chờ đợi khác. I Ví dụ: cho hai semaphore S và Q được khởi tạo bằng 1 P0 P1 wait(S); wait(Q); wait(Q); wait(S); . . . . signal(S); signal(Q); signal(Q); signal(S); I Chết đói: tiến trình bị ngưng (block) không hạn định (không bao giờ được xóa khỏi hàng đợi semaphore). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 35
  36. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Các Bài Toán Đồng Bộ Hóa 1. Bài toán Nhà sản xuất – Người tiêu dùng với vùng đệm giới hạn (Producer–Consummer with Bounded-Buffer). 2. Bài toán Bộ đọc – Bộ ghi (Readers–Writers). 3. Bài toán Các triết gia ăn tối (Dining-Philosophy). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 36
  37. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Bài toán Nhà sản xuất – Người tiêu dùng Bài Toán Nhà Sản Xuất – Người Tiêu Dùng I Hai tiến trình (nhà SX, người TD) chia sẻ chung vùng đệm có kích thước n (xem mô tả trong phần giới thiệu). I Dữ liệu chia sẻ đồng bộ hóa: I Semaphore mutex: dùng để loại trừ hỗ tương, khởi tạo bằng 1. I Semaphore empty và full: dùng để đếm số khe trống và đầy trên bộ đệm, khởi tạo empty = n và full = 0. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 37
  38. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Bài toán Nhà sản xuất – Người tiêu dùng Cấu Trúc Tiến Trình Nhà Sản Xuất do{ produce an item:"next_produced" wait(empty); wait(mutex); add"next_produced" to the buffer signal(mutex); signal(full); } while(true); TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 38
  39. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Bài toán Nhà sản xuất – Người tiêu dùng Cấu Trúc Tiến Trình Người Tiêu Dùng do{ wait(full); wait(mutex); remove an item from the buffer:"next_consumed" signal(mutex); signal(empty); consume the item"next_consumed" } while(true); TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 39
  40. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Bài toán Bộ đọc – Bộ ghi (Readers–Writers Problem) Bài Toán Bộ Đọc – Bộ Ghi I Nhiều tiến trình thực thi đồng thời cạnh tranh một đối tượng dữ liệu (tập tin, mẫu tin): I Bộ đọc (readers): tiến trình chỉ đọc dữ liệu. I Bộ ghi (writers): tiến trình đọc và ghi dữ liệu. I Vấn đề: I Nhiều readers có thể đọc dữ liệu chia sẻ đồng thời. I Chỉ có 1 writer được phép truy cập dữ liệu chia sẻ tại 1 thời điểm. Các bộ đọc, ghi phải loại trừ hỗ tương trên các đối tượng chia sẻ. ⇒ TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 40
  41. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Bài toán Bộ đọc – Bộ ghi (Readers–Writers Problem) Giải Pháp I Dữ liệu chia sẻ: I Đối tượng dữ liệu chia sẻ (tập tin, mẫu tin, . . . ). I Biến read_count: đếm số tiến trình đang đọc, khởi tạo bằng 0. I Semaphore mutex: dùng để loại trừ hỗ tương khi cập nhật biến read_count, khởi tạo bằng 1. I Semaphore rw_mutex: dùng để loại trừ hỗ tương cho các bộ ghi, khởi tạo bằng 1. Semaphore này cũng được sử dụng bởi các bộ đọc đầu tiên vào vùng tương trục và bộ đọc cuối cùng ra khỏi vùng tương trục. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 41
  42. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Bài toán Bộ đọc – Bộ ghi (Readers–Writers Problem) Cấu Trúc Các Tiến Trình Đọc – Ghi ~ Bộ ghi ~ Bộ đọc do{ do{ wait(rw_mutex); wait(mutex); read_count++; writing is performed if (read_count == 1) wait(rw_mutex); signal(rw_mutex); signal(mutex); } while(true); reading is performed wait(mutex); read_count ; if (read_count == 0) signal(rw_mutex); signal(mutex); } while(true); TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 42
  43. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Bài toán Năm triết gia ăn tối Bài Toán Năm Triết Gia Ăn Tối 222 Chapter 5 Process Synchronization I Các triết gia ngồi suy nghĩ, không giao tiếp với các triết gia khác. 2 3 I Khi đói, họ sẽ cố gắng lấy 2 chiếc đũa (lần 3 lượt mỗi chiếc) gần nhất để ăn cơm. 2 4 RICE I Một triết gia không thể lấy đũa đang được 1 4 dùng bởi triết gia khác. 1 0 I Khi có được 2 chiếc đũa, triết gia sẽ ăn và đặt đũa xuống sau khi ăn xong; sau đó suy 0 nghĩ tiếp. Figure 5.13 The situation of the dining philosophers. I Dữ liệu chia sẻ: semaphore chopstick[5], khởi tạo bằng 1. • In applications where it is easy to identify which processes only read shared data and which processes only write shared data. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5.• ĐồngIn applications Bộ Hóa Tiến Trìnhthat have more readers than writers.43 This is because reader– writer locks generally require more overhead to establish than semaphores or mutual-exclusion locks. The increased concurrency of allowing multiple readers compensates for the overhead involved in setting up the reader– writer lock. 5.7.3 The Dining-Philosophers Problem Consider five philosophers who spend their lives thinking and eating. The philosophers share a circular table surrounded by five chairs, each belonging to one philosopher. In the center of the table is a bowl of rice, and the table is laid with five single chopsticks (Figure 5.13). When a philosopher thinks, she does not interact with her colleagues. From time to time, a philosopher gets hungry and tries to pick up the two chopsticks that are closest to her (the chopsticks that are between her and her left andrightneighbors).Aphilosophermaypick up only one chopstick at a time. Obviously, she cannot pick up a chopstick that is already in the hand of a neighbor. When a hungry philosopher has both her chopsticks at the same time, she eats without releasing the chopsticks. When she is finished eating, she puts down both chopsticks and starts thinking again. The dining-philosophers problem is considered a classic synchronization problem neither because of its practical importance nor because computer scientists dislike philosophers but because it is an example of a large class of concurrency-control problems. It is a simple representation of the need to allocate several resources among several processes in a deadlock-free and starvation-free manner. One simple solution is to represent each chopstick with a semaphore. A philosopher tries to grab a chopstick by executing a wait() operation on that semaphore. She releases her chopsticks by executing the signal() operation on the appropriate semaphores. Thus, the shared data are semaphore chopstick[5];
  44. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Bài toán Năm triết gia ăn tối Cấu Trúc Của Tiến Trình Triết Gia i do{ wait(chopstick[i]); wait(chopstick[(i+1) % 5]); eat signal(chopstick[i]); signal(chopstick[(i+1) % 5]); think } while(true); Giải thuật trên còn gặp phải vấn đề gì? TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 44
  45. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Các bài toán đồng bộ hóa Bài toán Năm triết gia ăn tối Ngăn Khóa Chết (Deadlock) I Giải thuật đảm bảo không có trường hợp hai láng giềng ăn cùng lúc (sử dụng cùng đũa). I Tuy nhiên, có thể xảy ra tình trạng khóa chết – 5 triết gia cùng đói và mỗi người lấy được 1 chiếc đũa. I Giải pháp: I Cho phép nhiều nhất 4 triết gia ngồi trên bàn I Chỉ cho phép một triết gia lấy đũa nếu cả 2 đũa đều sẵn sàng. I Dùng giải pháp bất đối xứng: triết gia lẻ luôn lấy đũa trái trước, còn triết gia chẵn thì luôn lấy đũa phải trước. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 45
  46. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Monitors I Là một cấu trúc dữ liệu trừu tượng, được cung cấp bởi các ngôn ngữ lập trình cấp cao, cho phép thực hiện việc đồng bộ hóa một cách dễ dàng, hiệu quả. I Một cấu trúc monitor bao gồm: I Tập hợp các thao tác (hàm) cho phép truy xuất đến các dữ liệu bên trong monitor. I Các biến dữ liệu (biến) cục bộ. I Một đoạn mã khởi tạo (initialization code). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 46
  47. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Cấu Trúc Monitor 226 Chapter 5 Process Synchronization monitor monitor_name { entry queue shared variable declarations shared data procedure P1( ){ } . . procedure Pn( ){ . . . } initialization_code ( ){ operations initialization } code }//monitor Figure 5.16 Schematic view of a monitor. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 47 The only operations that can be invoked on a condition variable are wait() and signal().Theoperation x.wait(); means that the process invoking this operation is suspended until another process invokes x.signal(); The x.signal() operation resumes exactly one suspended process. If no process is suspended, then the signal() operation has no effect; that is, the state of x is the same as if the operation had never been executed (Figure 5.17). Contrast this operation with the signal() operation associated with semaphores, which always affects the state of the semaphore. Now suppose that, when the x.signal() operation is invoked by a process P,thereexistsasuspendedprocessQ associated with condition x.Clearly,ifthe suspended process Q is allowed to resume its execution, the signaling process P must wait. Otherwise, both P and Q would be active simultaneously within the monitor. Note, however, that conceptually both processes can continue with their execution. Two possibilities exist: 1. Signal and wait. P either waits until Q leaves the monitor or waits for another condition. 2. Signal and continue. Q either waits until P leaves the monitor or waits for another condition.
  48. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Đặc Tính Của Monitor I Các biến cục bộ chỉ có thể được truy xuất bởi các thủ tục của monitor. I Tiến trình vào monitor bằng cách gọi một trong các thủ tục đó. I Chỉ có thể có tối đa 1 tiến trình có thể vào monitor tại 1 thời điểm điều kiện loại trừ hỗ tương được đảm bảo. ⇒ TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 48
  49. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Biến Điều Kiện (Condition Variable) I Nhằm cho phép một tiến trình đợi trong monitor, ta dùng các biến điều kiện: condition x, y; I Biến điều kiện là cục bộ (chỉ được truy xuất bên trong monitor). I Hai thao tác trên biến điều kiện: I x.wait(): tiến trình gọi chỉ thị này sẻ bị ngưng cho đến khi x.signal() được gọi. I x.signal(): “đánh thức” một trong các tiến trình đang ngưng do gọi x.wait() (nếu không có tiến trình đang ngưng thì không làm gì cả). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 49
  50. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Biến Điều Kiện (Condition Variable) 5.8 Monitors 227 entry queue shared data queues associated with x x, y conditions y • • • operations initialization code Figure 5.17 Monitor with condition variables. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 50 There are reasonable arguments in favor of adopting either option. On the one hand, since P was already executing in the monitor, the signal-and- continue method seems more reasonable. On the other, if we allow thread P to continue, then by the time Q is resumed, the logical condition for which Q was waiting may no longer hold. A compromise between these two choices was adopted in the language Concurrent Pascal. When thread P executes the signal operation, it immediately leaves the monitor. Hence, Q is immediately resumed. Many programming languages have incorporated the idea of the monitor as described in this section, including Java and C# (pronounced “C-sharp”). Other languages—such as Erlang—provide some type of concurrency support using a similar mechanism. 5.8.2 Dining-Philosophers Solution Using Monitors Next, we illustrate monitor concepts by presenting a deadlock-free solution to the dining-philosophers problem. This solution imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available. To code this solution, we need to distinguish among three states in which we may find a philosopher. For this purpose, we introduce the following data structure: enum THINKING, HUNGRY, EATING state[5]; { } Philosopher i can set the variable state[i] = EATING only if her two neighbors are not eating: (state[(i+4) % 5] != EATING)and(state[(i+1) %5]!=EATING).
  51. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Biến Điều Kiện (Condition Variable) 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 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 51
  52. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Các Tùy Biến Khi Gọi Hàm signal() I Nếu tiến trình P gọi x.signal() trong khi tiến trình Q đang đợi trên biến này (Q gọi x.wait() trước đó), để tránh hai tiến trình thực thi đồng thời trong monitor: I Signal and wait: P chờ cho đến khi Q rời khỏi monitor. I Signal and continue: Q chờ cho đến khi P rời khỏi monitor. I Nhiều ngôn ngữ lập trình cài đặt cơ chế đồng bộ hóa dựa trên ý tưởng monitor (Java, C#) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 52
  53. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Ví Dụ Bài Toán Các Triết Gia Ăn Tối Với Monitor monitor DiningPhilosopiers { enum {thinking, hungry, eating} state[5]; condition self[5];//wait on chopsticki void pickup(int i);//pick up the chopsticki void putdown(int i);//put down the chopsticki void test(int i);//test the availability of the chopsticki void init() { for(int i = 0; i < 5; i++) state[i] = thinking; } } TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 53
  54. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Ví Dụ Bài Toán Các Triết Gia Ăn Tối Với Monitor void test(int i) { if ((state[(i + 4) % 5] != eating) && (state[i] == hungry) && (state[(i+1) % 5] != eating)) { state[i] = eating; self[i].signal(); } } TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 54
  55. [CT107] Ch5. Đồng Bộ Hóa Tiến Trình Monitors Ví Dụ Bài Toán Các Triết Gia Ăn Tối Với Monitor void pickup(int i) { ~ Tiến trình triết gia i: state[i] = hungry; DiningPhilosophiers.pickup(i); test(i); if (state[i] != eating) EAT self[i].wait(); } DiningPhilosophiers.putdown(i); void putdown(int i) { state[i] = thinking; ~ Tính chất: //test right+left neighbors I Loại trừ hỗ tương: test((i+4) % 5); I Tránh deadlock: test((i+1) % 5); } I Tránh chết đói: TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch5. Đồng Bộ Hóa Tiến Trình 55