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

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

Thêm vào BST

Báo xấu

64
lượt xem 6
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ộ tiến trình" cung cấp cho người đọc các nội dung: Vấn đề miền tương trục, giải pháp phần mềm, giải pháp phần cứng, Semaphores, các bài toán đồng bộ hóa cổ điển, Monitors. Mời các bạn cùng tham khảo nội dung chi tiết.

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 - Hà Duy An (ĐH Cần Thơ)

Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ Giảng viên: Hà Duy An
1. Vấn đề miền tương trục 2. Giải pháp phần mềm 3. Giải pháp phần cứng 4. Semaphores 5. Các bài toán đồng bộ hóa cổ điển 6. Monitors 10/29/2013 2 Chương 5: Đồng bộ hóa
• Các tiến trình được thực thi đồng thời o Có thể bị ngắt tại bất cứ vị trí nào • Các tiến trình đồng thời truy cập lên dữ liệu chia sẻ → tình trạng không nhất quán dữ liệu (inconsistency). • Việc duy trì sự nhất quán dữ liệu yêu cầu các 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. • Xét trường hợp: Bài toán Người sản xuất – Người tiêu thụ (Producer – Consumer Problem) với vùng đệm có kích thước giới hạn (bounded-buffer). 10/29/2013 4 Chương 5: Đồng bộ hóa
• Dữ liệu chia sẻ: #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; int counter = 0; 10/29/2013 5 Chương 5: Đồng bộ hóa
while (true) { /* produce an item in next produced */ while (counter == BUFFER_SIZE) ; /* do nothing */ buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; counter++; } 10/29/2013 6 Chương 5: Đồng bộ hóa
while (true) { while (counter == 0) ; /* do nothing */ next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; /* consume the item in next consumed */ } 10/29/2013 7 Chương 5: Đồng bộ hóa
• counter++ có thể được cài đặt: register1 = counter register1 = register1 + 1 counter = register1 • Counter-- có thể được cài đặt: register2 = counter register2 = register2 - 1 counter = register2 • Xét sự thực thi đan xen nhau với “count = 5” là giá trị khởi tạo: S0: producer execute register1 = counter {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = counter {register2 = 5} S3: consumer execute register2 = register2 – 1 {register2 = 4} S4: producer execute counter = register1 {counter = 6 } S5: consumer execute counter = register2 {counter = 4} 10/29/2013 8 Chương 5: Đồng bộ hóa
• Nếu cả hai producer và consumer cố gắng cập nhật vùng đệm đồng thời, các phát biểu assembly có thể bị phủ lấp. • Sự phủ lấp phụ thuộc vào cách producer và consumer được định thời. • Tình trạng đua tranh (Race Condition): là tình trạng mà vài 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 tiến trình nào hoàn thành cuối cùng.  Để ngăn chặn tình trạng đua tranh, các tiến trình cạnh tranh phải được đồng bộ hóa. 10/29/2013 9 Chương 5: Đồng bộ hóa
• Xét hệ thống có n tiến trình {p0, p1, … pn-1} • Mỗi tiến trình có một đoạn mã lệnh được gọi là miền tương trục (critical section): o Tiến trình có thể cập nhật các dữ liệu dùng chung o Khi một tiến trình đang trong miền tương trục, thì không tiến trình nào khác được phép thực thi trong miền tương trục của chúng => Vấn đề miền tương trục (critical-section problem): thiết kế giao thức giải quyết vấn đề này 10/29/2013 10 Chương 5: Đồng bộ hóa
• Cấu trúc tổng quát của tiến trình Pi là: • Mỗi tiến trình phải kiểm tra sự hợp lệ trong phần entry section để đi vào miền tương trục, tiếp theo sau khi vào miền tương trục tiến trình sẽ thực hiện thao tác thoát khỏi miền tương trục exit section, và tiếp tục thực thi phần còn lại remainder section 10/29/2013 11 Chương 5: Đồng bộ hóa
Giải pháp cho vấn đề miền tương trục phải thỏa các yêu cầu: 1. Loại trừ hỗ tương (Mutual Exclusion). Nếu tiến trình Pi đang thực thi trong miền tương trục, thì không có tiến trình nào khác có thể thực thi trong 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 vài tiến trình muốn được thực thi trong miền tương trục của chúng, thì việc lựa chọn một tiến trình được vào miền tương trục của nó không thể bị trì hoãn mãi được. 3. Chờ đợi hữu hạn (Bounded Wait). Không có tiến trình nào phải chờ đợi vĩnh viễn để có thể đi vào miền tương trục của nó. • Hai hướng tiếp cận giải quyết vấn đề phụ thuộc vào nhân HĐH: o Non-preemptive kernel: không cho phép tiến trình bị trưng dụng khi nó đang chạy ở chế độ nhân => vấn đề được giải quyết cho các cấu trúc dữ liệu trong nhân o Preemptive kernel: cho phép các tiến trình bị trưng dụng khi đang chạy ở chế độ nhân 10/29/2013 12 Chương 5: Đồng bộ hóa
• Các biến chung: o boolean lock; khởi đầu lock = false; • Tiến trình Pi: do { while (lock) ; lock = true; critical section lock = false; remainder section } while (1); => Không giải quyết được vấn đề 10/29/2013 15 Chương 5: Đồng bộ hóa
• Các biến chung: o int turn; khởi đầu turn = 0 o turn = i ⇒Pi có thể bước vào miền tương trục của nó • Tiến trình Pi do { while (turn != i) ; critical section turn = j; remainder section } while (1); => Không thõa điều kiện 2 10/29/2013 16 Chương 5: Đồng bộ hóa
• Các biến chia sẻ: o boolean flag[2]; khởi đầu flag[0] = flag[1] = false. o flag[i] = true ⇒Pi sẵn sàng bước vào miền tương trục của nó • Tiến trình P1: do { flag[i] := true; while (flag[j]) ; critical section flag [i] = false; remainder section } while (1); => Không thỏa mãn điều kiện 2 10/29/2013 17 Chương 5: Đồng bộ hóa
• Giải quyết được vấn đề miền tương trục (thỏa mãn cả 3 điều kiện) cho 2 tiến trình • Giả sử các lệnh load và store là nguyên tử (không thể bị ngắt) • Hai tiến trình chia sẽ hai biến: o int turn; o Boolean flag[2] • turn – chỉ định tiến trình nào được phép vào miền tương trục • flag – cho biết tiến trình nào đã sẵn sàng vào miền tương trục o flag [i] = true ⇒Pi sẵn sàng bước vào miền tương trục của nó 10/29/2013 18 Chương 5: Đồng bộ hóa
do { flag[i] = true; turn = j; while (flag[j] && turn == j); critical section flag[i] = false; remainder section } while (true); • Nhận xét: 1. Loại trừ hỗ tương được đảm bảo 2. Yêu cầu tiến triển được thỏa mãn 3. Yêu cầu chờ đợi hữu hạn được đáp ứng 10/29/2013 19 Chương 5: Đồng bộ hóa
• Nhiều hệ thống cung cấp phần cứng hỗ trợ đồng bộ hóa • Tất cả các giải pháp này dựa trên ý tưởng bảo vệ miền tương trục bằng "khóa" • Vô hiệu hóa các ngắt: khi một tiến trình bắt đầu thực thi trong miền tương trục thì các ngắt bị vô hiệu hóa đến khi tiến trình thoát khỏi miền tương trục o Cho phép tiến trình người dùng có khả năng vô hiệu các ngắt => có thể tác động xấu đến sự vận hành hệ thống o Không giải quyết được vấn đề trên hệ thống đa xử lý • Các hệ thống máy tính hiện đại cung cấp các thao tác nguyên tử (atomic hardware instructions): o test_and_set o compare_and_swap • Nếu các lệnh có tính chất nguyên tử thực thi cùng lúc thì thứ tự thực hiện của chúng luôn được đảm bảo – một lệnh được hoàn thành trước khi lệnh khác được thực thi o Atomic = non-interruptible 10/29/2013 21 Chương 5: Đồng bộ hóa