intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Hệ điều hành: Chương 5 - Trần Công Án (ĐH Cần Thơ)

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:56

Thêm vào BST
Báo xấu
85
lượt xem 8
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Hệ điều hành - Chương 5: Đồng bộ hóa tiến trình" cung cấp cho người đọc các kiến thức: 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. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Hệ điều hành: Chương 5 - Trần Công Án (ĐH Cần Thơ)

  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ình S 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ặc 6 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ủa P 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 } while (true); ⇒ Không thỏa yêu cầu. 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 flag[i] = false; I Tiến triển: 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2