Nội dung tài liệu Nguyên lý hệ điều hành - Chương 6: Đồng bộ hóa tiến trình, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
1BÀI GIẢNG NGUYÊN LÝ HỆ ĐIỀU HÀNH Chương 6: Đồng bộ hóa tiến trình Phạm Quang Dũng Bộ môn Khoa học máy tính Khoa Công nghệ thông tin Trường Đại học Nông nghiệp Hà Nội Website: fita.hua.edu.vn/pqdung 5.2 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Nội dung Cơ sở Vấn đề đoạn găng Giải pháp của Peterson Phần cứng đồng bộ hóa Kỹ thuật cờ báo [Semaphores] 5.3 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 6.1. Cơ sở Sự truy nhập đồng thời đến dữ liệu chia sẻ có thể gây ra sự mâu thuẫn. Để duy trì tính nhất quán dữ liệu cần có cơ chế đảm bảo thực hiện các tiến trình hợp tác theo thứ tự. Giả sử rằng chúng ta muốn đưa ra một giải pháp cho vấn đề tiến trình sản xuất - tiến trình tiêu thụ mà đều điền vào buffer. Chúng ta có thể làm được bằng cách có một biến nguyên count để theo dõi số phần tử trong buffer. z Khởi tạo count=0. z Nó được tăng bởi tiến trình sản xuất khi thêm vào buffer 1 phần tử. z Nó bị giảm bởi tiến trình tiêu thụ khi lấy khỏi buffer 1 phần tử 5.4 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Producer while [true] { /* produce an item and put in nextProduced */ while [count == BUFFER_SIZE] ; // do nothing buffer [in] = nextProduced; in = [in + 1] % BUFFER_SIZE; count++; } 25.5 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Consumer while [true] { while [count == 0] ; // do nothing nextConsumed = buffer[out]; out = [out + 1] % BUFFER_SIZE; count--; /* consume the item in nextConsumed } 5.6 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Trạng thái tranh đua [Race condition] count++ có thể được thực thi như sau: register1 = count register1 = register1 + 1 count = register1 count-- có thể được thực thi như sau: register2 = count register2 = register2 - 1 count = register2 Xét sự thực hiện đan xen với ban đầu “count = 5”: S0: producer execute register1 = count {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = count {register2 = 5} S3: consumer execute register2 = register2 - 1 {register2 = 4} S4: producer execute count = register1 {count = 6} S5: consumer execute count = register2 {count = 4} 5.7 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 6.2. Vấn đề đoạn găng [Critical-Section] Xét hệ thống gồm n tiến trình {P0, P1, , Pn-1}. Mỗi tiến trình có một đoạn mã, gọi là đoạn găng, mà tại đó tiến trình có thể thay đổi các biến chung, cập nhật bảng, ghi tệp Đặc điểm quan trọng của hệ thống là tại mỗi thời điểm chỉ có 1 tiến trình thực hiện trong đoạn găng của nó. ⇔ sự thực hiện các đoạn găng là loại trừ lẫn nhau theo thời gian. Vấn đề đoạn găng là thiết kế một giao thức mà các tiến trình sử dụng để hợp tác. Mỗi tiến trình phải yêu cầu sự cho phép để bước vào đoạn găng của nó. Đoạn mã thực hiện yêu cầu này được gọi là đoạn vào. Sau đoạn găng có thể có đoạn ra. 5.8 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Cấu trúc tổng quát của tiến trình Pi do { đoạn găng đoạn còn lại } while [TRUE] ; đoạn vào đoạn ra 35.9 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Giải pháp cho vấn đề đoạn găng Một giải pháp cho vấn đề đoạn găng phải thỏa mãn 3 yêu cầu: 1. Loại trừ lẫn nhau: nếu tiến trình Pi đang thực hiện trong đoạn găng của nó thì các tiến trình khác không được thực hiện trong đoạn găng của chúng. 2. Chọn tiến trình tiếp theo được vào đoạn găng: nếu không có tiến trình nào đang trong đoạn găng của nó và một số tiến trình muốn vào đoạn găng của chúng thì chỉ những tiến trình đang không trong đoạn còn lại mới là ứng cử viên. 3. Chờ đợi có hạn: tồn tại giới hạn số lần các tiến trình khác được phép vào đoạn găng của chúng sau khi một tiến trình yêu cầu vào đoạn găng đến trước khi yêu cầu đó được đáp ứng. 5.10 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Các phương pháp xử lý đoạn găng kernel không ưu tiên trước: không cho phép một tiến trình bị ưu tiên trước khi nó đang chạy trong kernel mode; tiến trình đó sẽ chạy cho đến khi nó thoát khỏi kernel mode. z Không gây tình trạng đua tranh trong cấu trúc z Windows 2000/XP, UNIX cũ, Linux trước phiên bản 2.6 kernel có ưu tiên trước: cho phép một tiến trình bị ưu tiên trước khi nó đang chạy trong kernel mode. z Cần thiết kế cẩn thận để tránh tình trạng đua tranh, nhất là với kiến trúc đa xử lý đối xứng [SMP]. Vì sao? z Thích hợp hơn với lập trình thời gian thực, vì nó sẽ cho phép 1 tiến trình thời gian thực ưu tiên trước 1 tiến trình khác đang chạy trong kernel. z Linux 2.6, một số phiên bản thương mại của UNIX [Solaris, IRIX] 5.11 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 6.3. Giải pháp của Peterson Giải pháp cho 2 tiến trình P0, P1 Giả sử các lệnh LOAD và STORE là nguyên tử [atomic]; nghĩa là không thể bị ngắt. Hai tiến trình chia sẻ 2 biến: z int turn; z boolean flag[2] Biến turn bằng 0/1. turn==i thì Pi được phép vào đoạn găng. flag[i]=true cho biết tiến trình Pi sẵn sàng vào đoạn găng. 5.12 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Thuật toán cho tiến trình Pi while [true] { flag[i] = TRUE; turn = j; while [flag[j] && turn == j]; ĐOẠN_GĂNG flag[i] = FALSE; ĐOẠN_CÒN_LẠI } Chứng minh thuật toán trên thỏa mãn cả 3 điều kiện của giải pháp? 45.13 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 6.4. Phần cứng đồng bộ hóa Nhiều HĐH cung cấp sự hỗ trợ phần cứng cho mã đoạn găng Đơn bộ xử lý – có thể vô hiệu các ngắt z Đoạn mã đang chạy thực hiện mà không bị giành ưu tiên z Nói chung rất không hiệu quả với các hệ thống đa bộ xử lý Việc chuyển thông điệp đến tất cả các bộ xử lý tốn rất nhiều thời gian, làm trễ sự vào đoạn găng của các tiến trình Nhiều HĐH hiện đại cung cấp các lệnh phần cứng nguyên tử Nguyên tử = không thể bị ngắt z Hoặc là test từ nhớ [memory word] và set giá trị z Hoặc là hoán đổi [swap] nội dung của 2 từ nhớ 5.14 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Lệnh TestAndSet Định nghĩa: boolean TestAndSet [boolean *target] { boolean rv = *target; *target = TRUE; return rv; } 5.15 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Giải pháp dùng TestAndSet Biến boolean chia sẻ là lock, được khởi tạo là false. Giải pháp cho mỗi tiến trình: while [true] { while [TestAndSet [&lock]] ; /* do nothing // đoạn găng lock = FALSE; // đoạn còn lại } 5.16 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Lệnh Swap Định nghĩa: void Swap [boolean *a, boolean *b] { boolean temp = *a; *a = *b; *b = temp; } 55.17 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành Giải pháp dùng Swap Biến boolean chia sẻ là lock, được khởi tạo là false; Mỗi tiến trình có một biến boolean cục bộ là key. Giải pháp cho mỗi tiến trình: while [true] { key = TRUE; while [key == TRUE] Swap [&lock, &key]; // đoạn găng lock = FALSE; // đoạn còn lại } 5.18 Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành 6.5. Kỹ thuật dùng cờ báo [Semaphore] Công cụ đồng bộ hóa dễ dùng hơn với người lập trình ứng dụng. Semaphore S – biến integer Hai hoạt động nguyên tử chuẩn có thể thay đổi S: z wait[] và signal[], còn được gọi là P[] và V[] wait [S] { while S