Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Phần 2) - Trường Đại học Công nghệ thông tin
Giải thuật 3 thỏa mutual exclusion, progress, và bounded waiting
Mutual exclusion được đảm bảo bởi vì
P0 và P1 đều ở trong CS nếu và chỉ nếu flag[0] = flag[1] = true và turn = I cho mỗi Pi (không thể xảy ra)
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Phần 2) - Trường Đại học Công nghệ thông tin", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Phần 2) - Trường Đại học Công nghệ thông tin
HỆ ĐIỀU HÀNH Chương 5 – Đồng bộ (2) 1/17/2018 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 1 Ôn tập chương 5 (1) Khi nào thì xảy ra tranh chấp race condition? Vấn đề Critical Section là gì? Yêu cầu của lời giải cho CS problem? Có mấy loại giải pháp? Kể tên? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 2 Mục tiêu chương 5 (2) Hiểu được nhóm giải pháp Busy waiting bao gồm: Các giải pháp phần mềm Các giải pháp phần cứng 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 3 Nội dung chương 5 (2) Các giải pháp phần mềm Sử dụng giải thuật kiểm tra luân phiên Sử dụng các biến cờ hiệu Giải pháp của Peterson Giải pháp Bakery Các giải pháp phần cứng Cấp ngắt Chỉ thị TSL 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 4 Giải thuật 1 Biến chia sẻ int turn ; /* khởi đầu turn = 0 */ nếu turn = i thì Pi được phép vào critical section, với i = 0 hay 1 Process Pi do { while (turn != i); critical section turn = j; remainder section } while (1); Thỏa mãn Mutual exclusion ( 1) Nhưng không thoả mãn yêu cầu về progress (2) và bounded waiting (3) vì tính chất strict alternation của giải thuật 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 5 Giải thuật 1 (tt) Điều gì xảy ra nếu P 0 có RS (remainder section) rất lớn còn P1 có RS nhỏ? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 6 Process P0: do while (turn != 0); critical section turn := 1; remainder section while (1); Process P1: do while (turn != 1); critical section turn := 0; remainder section while (1); Giải thuật 2 Bi ến chia sẻ boolean flag [ 2 ]; /* khởi đầu flag[ 0 ] = flag[ 1 ] = false */ Nếu flag[ i ] = true thì Pi “sẵn sàng” vào critical section. Process Pi do { flag[ i ] = true; /* Pi “sẵn sàng” vào CS */ while ( flag[ j ] ); /* Pi “nhường” Pj */ critical section flag[ i ] = false; remainder section } while (1); Thỏa mãn Mutual exclusion ( 1) Không thỏa mãn progress. Vì sao? 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 7 Giải thuật 3 (Peterson) Bi ến chia sẻ Kết hợp cả giải thuật 1 và 2 Process Pi, với i = 0 hoặc i = 1 do { flag[ i ] = true; /* Process i sẵn sàng */ turn = j; /* Nhường process j */ while (flag[ j ] and turn == j); critical section flag[ i ] = false; remainder section } while (1); Tho ả mãn được cả 3 yêu cầu ? ⇒ giải quyết bài toán critical section cho 2 process 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 8 Giải thuật 3 (Peterson) cho 2 tiến trình 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 9 Process P0 do { /* 0 wants in */ flag[0] = true; /* 0 gives a chance to 1 */ turn = 1; while (flag[1] &&turn == 1); critical section /* 0 no longer wants in */ flag[0] = false; remainder section } while(1); Process P1 do { /* 1 wants in */ flag[1] = true; /* 1 gives a chance to 0 */ turn = 0; while (flag[0] && turn == 0); critical section /* 1 no longer wants in */ flag[1] = false; remainder section } while(1); Giải thuật 3: Tính đúng đắn Giải thuật 3 thỏa mutual exclusion, progress, và bounded waiting Mutual exclusion được đảm bảo bởi vì P0 và P1 đều ở trong CS nếu và chỉ nếu flag[0] = flag[1] = true và turn = I cho mỗi Pi (không thể xảy ra) Chứng minh thỏa yêu cầu về progress và bounded waiting Pi không thể vào CS nếu và chỉ nếu bị kẹt tại vòng lặp while() với điều kiện flag[j]=true và turn = j Nếu Pj không muốn vào CS thì flag[j] = false và do đó Pi có thể vào CS 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 10 Giải thuật 3: Tính đúng đắn (tt) Nếu Pj đã bật flag[j]=true và đang chờ tại while() thì có chỉ hai trường hợp là turn = i hoặc turn = j Nếu turn = i và Pi vào CS. Nếu turn = j thì Pj vào CS nhưng sẽ bật flag[j]=false khi thoát ra -> cho phếp Pi và CS Nhưng nếu Pj có đủ thời gian bật flag[j]=true thì Pj cũng phải gán turn = i Vì Pi không thay đổi trị của biến turn khi đang kẹt trong vòng lặp while(), Pi sẽ chờ để vào CS nhiều nhất là sau một lần Pj vào CS (bounded waiting) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 11 Giải thuật bakery: n process Trư ớc khi vào CS, process Pi nhận một con số. Process nào giữ con số nhỏ nhất thì được vào CS Trư ờng hợp Pi và Pj cùng nhận được một chỉ số: Nếu i < j thì Pi được vào trước. (Đối xứng) Khi ra khỏi CS, Pi đặt lại số của mình bằng 0 Cơ chế cấp số cho các process thường tạo các số theo cơ chế tăng dần, ví dụ 1, 2, 3, 3, 3, 3, 4, 5, Kí hiệu (a,b) < (c,d) nếu a < c hoặc if a = c và b < d max (a0,,ak) là con số b sao cho b ≥ ai với mọi i = 0,, k 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 12 Giải thuật bakery: n process (tt) 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 13 /* shared variable */ boolean choosing[ n ]; /* initially, choosing[ i ] = false */ int num[ n ]; /* initially, num[ i ] = 0 */ do { choosing[ i ] = true; num[ i ] = max(num[0], num[1],, num[n − 1]) + 1; choosing[ i ] = false; for (j = 0; j < n; j++) { while (choosing[ j ]); while ((num[ j ] != 0) && (num[ j ], j) < (num[ i ], i)); } critical section num[ i ] = 0; remainder section } while (1); Từ software đến hardware Khuyết điểm của các giải pháp software : Các process khi yêu cầu được vào vùng tranh chấp đều phải liên tục kiểm tra điều kiện (busy waiting), tốn nhiều thời gian xử lý của CPU Nếu thời gian xử lý trong vùng tranh chấp lớn, một giải pháp hiệu quả nên có cơ chế block các process cần đợi. Các giải pháp phần cứng: Cấm ngắt (disable interrupts) Dùng các lệnh đặc biệt 1/17/2018 Copyrights 2017 CE-UIT. All Rights Reserved. 14 Cấm ngắt Trong hệ thống uniprocessor: mutual exclusion được đảm bảo Nhưng nếu system clock được cập nhật do interrupt thì Trong hệ thống multiprocessor: mutual exclusion không được đảm bảo Chỉ cấm ngắt tại CPU thực thi lệnh disable_interrupts Các CPU khác vẫn có thể
File đính kèm:
- bai_giang_he_dieu_hanh_chuong_5_dong_bo_phan_2_truong_dai_ho.pdf