Giáo trình Hệ điều hành - Chương 3: Tương tranh giữa các Process - Khoa Công nghệ Thông tin - Trường ĐH Bách Khoa TP. HCM

Nội dung text: Giáo trình Hệ điều hành - Chương 3: Tương tranh giữa các Process - Khoa Công nghệ Thông tin - Trường ĐH Bách Khoa TP. HCM

1. Giới thiệu về tương tranh ‰ Phân tích kỹ code của chương trình, ta nhận thấy chúng là danh sách liên tiếp của 2 loại đoạn code : ‰ đoạn code truy xuất các biến cục bộ của chương trình. Đoạn code này thường dài và xuất hiện nhiều. May mắn là chúng ta không cần quan tâm và kiểm soát đoạn code này. ‰ Đoạn code truy xuất tài nguyên dùng chung và có thể tranh chấp với process khác. Đây là đoạn code, mặc dù ít xuất hiện và thường rất ngắn, nhưng dễ gây lỗi trên tài nguyên nên ta gọi nó là 'critical session‘ (viết tắt là CS), chúng ta cần kiểm soát cẩn thận đoạn code CS này. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 3 Giới thiệu về tương tranh đoạn lệnh truy đoạn lệnh truy xuất cục bộ xuất cục bộ critical session 1 resource 1 critical session 2 đoạn lệnh truy đoạn lệnh truy xuất cục bộ xuất cục bộ critical session 2 critical session 1 resource 2 đoạn lệnh truy đoạn lệnh truy xuất cục bộ xuất cục bộ Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 4 2
2. Loại trừ tương hỗ giữa các đoạn CS Mỗi lần muốn vào vùng CS, ta phải gọi hàm In_Control() để kiếm soát việc thi hành vùng CS, khi hoàn thành vùng CS, ta In_Control(); phải gọi hàm Vùng CS truy xuất tài Out_Control() để thông nguyên dùng chung báo cho các process khác đang chờ để chúng kiểm Out_Control(); tra lại việc đi vào. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 7 3.3 Các phương pháp chờ chủ động 1. Phương pháp dựa trên Interrupt ƒ Tính chất cơ bản của CPU là sau khi thi hành 1 lệnh máy, nó sẽ tự động thi hành lệnh máy kế tiếp, mà không để ý bất kỳ thứ gì bên ngoài. ƒ Tuy nhiên, nếu chỉ vậy, CPU sẽ không bao giờ đáp ứng kịp thời 1 sự kiện nào đóxảy ra trong quá trình thi hành chương trình của CPU. Do đó, người ta phải tạo thêm 1 chân nhập có tên là IRQ. Một thiết bị nào đónếu muốn yêu cầu CPU xử lý dùm công việc nào thì hãy tạo tín hiệu (ngắt) gởi về CPU trên chân IRQ. Bình thường, mỗi khi CPU thấy có tín hiệu trên chân IRQ, nó sẽ dừng tạm thời chương trình đang chạy hiện hành, chạy đoạn lệnh qui định trước (trình phục vụ ngắt) để xử lý công việc dùm cho thiết bị yêu cầu. Sau khi hoàn thành trình phục vụ ngắt, CPU sẽ quay về tiếp tục thi hành chương trình từ vị trí ngừng trước đây. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 8 4
3. 3.3 Các phương pháp chờ chủ động 2. Phương pháp dùng biến khóa Mỗi vùng CS được bảo vệ bởi 1 biến khóa, biến này lúc đầu = 0 để xác định rằng chưa process nào thi hành vùng CS. Mỗi lần muốn thi hành vùng CS, process sẽ kiểm tra biến khóa, nếu nó = 0 thì set lên 1 và tiếp tục thi hành vùng CS đến khi hoàn thành sẽ set lại biến khóa = 0. Trường hợp biến khóa = 1 thì phải chờ process khác thi hành xong vùng CS. Bool process_in_CS = 0; In_Control() { for (;;) if (process_in_CS ==0) break; Out_Control() { process_in_CS = 1; process_in_CS = 0; } } Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 11 3.3 Các phương pháp chờ chủ động 2. Phương pháp dùng biến khóa Về ý tưởng thì phương pháp dùng biến khóa giải quyết tốt vấn đề tranh chấp tài nguyên dùng chung, nhưng nếu hiện thực bằng đoạn lệnh C như slide trước thì có thể thất bại trong 1 số tình huống. Giả sử process P1 muốn thi hành vùng CS, nó kiểm tra biến process_in_CS và thấy đang mở (=0). Ngay lúc này, process hết khe thời gian, trình lập lịch dừng nó và chọn process P2 chạy tiếp, nếu P2 cũng muốn thi hành vùng CS, nó kiểm tra biến khóa, lúc này biến khóa vẫn = 0 nên P2 sẽ set lên 1 rồi thi hành vùng CS. Trong lúc thi hành CS, P2 hết khe thời gian và CPU được giao lại P1. P1 chạy tiếp và cũng set biến khóa lên 1 rồi vào vùng CS. Như vậy lúc này 2 process P1 và P2 đang tranh chấp tài nguyên dùng chung! Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 12 6
4. 3.3 Các phương pháp chờ chủ động 4. Phương pháp luân phiên Ý tưởng của phương pháp này là cho các process luân phiên thi hành vùng CS, từng thời điểm chỉ 1 process được thi hành CS. Giả sử có N process cần thi hành CS được đánh số từ 0 đến N-1. Tạo 1 biến "turn" chứa chỉ số process được phép thi hành CS tại từng thời điểm. Lúc đầu turn được set = 0. In_control (int idproc) { while (turn != idproc) ; // chờ đến lượt mình } Out_control (int idproc) { turn = (turn +1)%N; // cho process đi ngay sau mình vào } Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 15 3.3 Các phương pháp chờ chủ động 4. Phương pháp luân phiên Về lý thuyết, phương pháp luân phiên tạo được sự bình đẳng tuyệt đối giữa các process về việc thi hành vùng CS, process nào cũng được thi hành CS với cơ hội ngang nhau, không process nào có thể thi hành CS nhiều lần hơn các process khác. Tuy nhiên trong thực tế, các process thường có độ phức tạp khác nhau, có nhu cầu chạy vùng CS rất khác nhau, process này cần chạy CS nhiều lần, process khác chỉ cần chạy CS ít lần. Như vậy, process cần chạy CS ít lần hơn sẽ ngăn cản process cần chạy CS nhiều lần hơn. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 16 8
5. 3.4 Đồng bộ các process : Bài toán Sản xuất-Tiêu dùng Trong hệ thống có 2 loại phần tử : ƒ Sản xuất chuyên tạo sản phẩm mới và để vào kho chứa. ƒ Tiêu dùng chuyên lấy sản phẩm từ kho chứa ra để sử dụng. Bài toán Sản xuất -Tiêu dùng trên có 2 vấn đề cần giải quyết : ƒ làm sao để phần tử Sản xuất và Tiêu dùng không được tranh chấp nhau khi truy xuất kho chứa sản phẩm. ƒ làm sao để đồng bộ tốc độ thi hành của 2 phần tử để chúng có thể hoạt động tốt theo thời gian, không gây khủng hoảng thừa hay khủng hoảng thiếu. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 19 Ý tưởng giải quyết Bài toán Sản xuất -Tiêu dùng Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 20 10
6. Ý tưởng giải quyết Bài toán Sản xuất -Tiêu dùng Cụ thể nếu Producer kiểm tra kho chứa đầy, tính gọi hàm sleep() để ngủ thì hết khe thời gian chạy. Trình lập lịch sẽ dừng tạm Producer, chọn Consumer chạy. Consumer kiểm tra kho chứa, lấy được sản phẩm và đánh thức Producer dậy. Tuy nhiên việc đánh thức này không có giá trị vì Producer chứa ngủ. Sau đó producer chạy tiếp, nó sẽ gọi sleep() để ngủ và sẽ không bao giờ thức dậy vì consumer không bao giờ đánh thức nó nữa. Riêng Consumer chạy tiếp và theo thời gian, nó sẽ lấy hết sản phẩm trong kho chứa, khi đónósẽ gọi sleep() để ngủ chờ Producer đánh thức nhưng sẽ không bao giờ thức dậy được vì Producer cũng đã và đang ngủ như Consumer. Hiện tượng này được gọi là Deadlock và ta sẽ giới thiệu các phương pháp khác nhau để giải quyết trong chương 4. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 23 3.5 Các phương pháp sleep/wakeup 1. Phương pháp dùng Semaphore Semaphore là đối tượng được cung cấp sẵn bởi hệ thống, đối tượng này gồm : ƒ 1 thuộc tính chứa giá trị nguyên dương, ta gọi là biến semaphore s. ƒ hàm down(s) có chức năng giảm s 1 đơn vị, nếu giảm không được thì phải chờ đến khi có điều kiện giảm được thì làm lại. Thời gian thực hiện hàm down có thể rất dài, nhưng các process khác không thể thấy được trạng thái trung gian của hàm down này. Nói cách khác việc thi hành hàm down có tính nguyên tử, không chia cắt được. ƒ hàm up(s) có chức năng tăng s 1 đơn vị, nếu sau khi tăng mà s = 1 thì phải đánh thức các process đang ngủ vì đã thực hiện down(s) trước đây mà chưa được. Thời gian thực hiện hàm up rất nhanh, việc thi hành hàm up cũng có tính nguyên tử, không chia cắt được. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 24 12
7. 3.5 Các phương pháp sleep/wakeup //dùng Semaphore giải quyết bài toán Sản xuất — Tiêu dùng Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 27 3.5 Các phương pháp sleep/wakeup Phân tích code dùng semaphore để giải quyết đồng thời 2 vấn đề tương tranh và đồng bộ process trong bài toán Sản xuất — Tiêu dùng trong slide trước, ta thấy việc dùng semaphore khá gọn nhẹ và hiệu quả. Tuy nhiên khuyết điểm của việc dùng semaphore là độ an toàn không cao. Cụ thể nếu ta hoán vị 2 lệnh down(&full) và down(&mutex) trong process Consumer thì dễ dẫn đến deadlock vì khi hết sản phẩm trong kho chứa, Consumer tới sẽ khóa kho trước rồi mới kiểm tra kho chứa, lúc này kho chứa rỗng nên Consumer sẽ dừng chờ Producer đánh thức, tuy nhiên Producer sẽ phải ngủ chờ Consumer mở kho chứa → Producer và Consumer đã ngủ chờ nhau và cả 2 sẽ ngủ mãi, đây là hiện tượng deadlock mà ta sẽ trình bày trong chương 4. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 28 14
8. 3.5 Các phương pháp sleep/wakeup //dùng Monitor giải quyết bài toán Sản xuất — Tiêu dùng Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 31 3.5 Các phương pháp sleep/wakeup Code Java dùng Monitor hiện thực bài toán Sản xuất-Tiêu dùng //đặc tả class ứng dụng demo bài toán Sản xuất — Tiêu dùng public class ProducerConsumer { static final int N = 100; //kích thước kho chứa static producer p = new producer(); //đối tượng thread producer static producer c = new consumer(); //đối tượng thread consumer static ourMonitor mon = new ourMonitor(); //đối tượng monitor //điểm nhập ứng dụng demo public static void main(String args[]) { p.start(); //khởi động thread Producer c.start(); //khởi động thread Consumer } //(xem tiếp slide kế) Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 32 16
9. 3.5 Các phương pháp sleep/wakeup Code Java dùng Monitor hiện thực bài toán Sản xuất-Tiêu dùng //class đặc tả Monitor static class our_monitor { private int buffer[] = new int[N]; // kho chứa private int count = 0, lo = 0, hi = 0; //các biến quản lý kho chứa //hàm thêm sản phẩm vào kho chứa public synchronized vois insert (int val) { if (count == N) goto_sleep(); //nếu kho đầy thì ngủ buffer[hi] = val; // để sản phầm vào vị trí hi = (hi+1) % N; //tăng vị trí để sản phẩm count = count +1; //tăng counter sản phẩm if (count == 1) notify(); //đánh thức consumer nếu cần } Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 35 3.5 Các phương pháp sleep/wakeup Code Java dùng Monitor hiện thực bài toán Sản xuất-Tiêu dùng //hàm lấy sản phẩm từ kho chứa public synchronized int remove () { int val; if (count == 0) goto_sleep(); //nếu kho hết thì ngủ val = buffer[lo]; // lấy sản phầm từ vị trí lo = (lo+1) % N; //tăng vị trí lấy sản phẩm count = count - 1; //giảm counter sản phẩm if (count == N-1) notify(); //đánh thức producer nếu cần return val; } private void goto_sleep () { try { wait(); } catch (InterruptedException exc) {} } } Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 36 18
10. 3.5 Các phương pháp sleep/wakeup 3. Phương pháp gởi/nhận thông báo //Code C hiện thực bài toán Sản xuất-Tiêu dùng #define N 100 void Consumer(void) { int item; message m; //gởi n yêu cầu sản xuất tới Producer for (i = 0; i <N; i++) send (producer, &m); while (TRUE) { receive(producer, &m); //chờ nhận sản phầm từ consumer item = extract_item(&m); //rút trích sản phầm mới từ thông báo send(producer, &m); //gởi yêu cầu mới đến producer consume_item(&tiem); //tiêu dùng sản phẩm } } Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 39 3.6 Các bài toán IPC kinh điển 1. Bài toán 5 SV ăn cơm : 1. bàn ăn có 5 chén cơm dành cho 5 SV, đánh số thứ tự từ 0 - 4. 2. do thiếu đủa, chỉ có 5 chiếc được để xen kẻ giữa các chén cơm, đánh số thứ tự từ 0 -4. 3. mỗi SV ăn cơm cần 1 đôi đủa. Vì lịch sự, mỗi SV chỉ được phép lấy 2 chiếc kề chén cơm của mình (chiếc bên trái và chiếc bên phải). Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 40 20
11. 3.6 Các bài toán IPC kinh điển 1. Bài toán 5 SV ăn cơm : Phát họa qui trình ăn cơm cho mỗi SV : #define N 5 void Sinhvien (int i) { while (còn cơm) { think(); //công đoạn 1 take_fork(i); //công đoạn 2, có thể bị kẹt 1 thời gian take_fork((i+1)%N); eat(); put_fork(i); //công đoạn 3 thường rất nhanh put_fork((i+1)%N); } } Qui trình ăn ở trên dễ bị deadlock, thí dụ như 5 SV đều thực hiện lệnh take_fork(i); đồng thời và đều thành công. Bây giờ họ thực hiện tiếp lệnh kế thì tất cả đều bị dừng chờ mãi mãi vì không còn đủa trên bàn. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 43 3.6 Các bài toán IPC kinh điển 1. Bài toán 5 SV ăn cơm : //thuật giải cải tiến để tránh deadlock : #define N 5 void Sinhvien (int i) { while (còn cơm) { think(); //công đoạn 1 L1: take_fork(i); if (!asyn_take_fork((i+1)%5)) { //thất bại put_fork(i); sleep(random()); goto L1; //công đoạn 2 } eat(); //công đoạn 3 } } Qui trình ăn ở trên tránh được deadlock, nhưng còn dựa vào yếu tố ngẫu nhiên nên chưa hiệu quả triệt để. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 44 22
12. 3.6 Các bài toán IPC kinh điển //thuật giải dùng semaphore để giải quyết tranh chấp và đồng bộ : void put_forks (int i) { down(&mutex); //đảm bảo 0 tranh chấp khi lấy đủa state[i] = THINKING; //ghi nhận trạng thái không dùng đủa test(LEFT); //kiểm tra lấy được không ? nếu được đánh thức //SV LEFT dậy để và cơm và gắp thức ăn test(RIGHT); //kiểm tra lấy được không ? nếu được đánh thức //SV RIGHT dậy để và cơm và gắp thức ăn up(&mutex); //đánh thức các SV khác để họ truy xuất đủa } Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 47 3.6 Các bài toán IPC kinh điển 2. Bài toán đọc/ghi database : 1. có nhiều process cần đọc/ghi database. 2. làm sao cho việc đọc/ghi database của các process thỏa các điều kiện sau : ƒ không tranh chấp nhau và không làm hỏng dữ liệu. ƒ việc truy xuất database hiệu quả cao nhất. Cách giải quyết đơn giản nhất : 1. xem toàn bộ database như 1 tài nguyên dùng chung, dùng 1 semaphore nhị phân db để bảo vệ nó. 2. bất kỳ process đọc/ghi database nào cũng phải down(db) trước khi truy xuất database và up(db) sau khi hoàn tất việc truy xuất database. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 48 24
13. 3.6 Các bài toán IPC kinh điển 3. Bài toán ở tiệm hớt tóc : 1. tiệm chỉ có 1 ghế hớt và 1 thợ cắt. 2. tiệm có hàng ghế chờ N ghế. Tìm qui trình làm việc của thợ và khách trong tiệm sao cho các điều kiện sau đây được thỏa : ƒ không tranh chấp nhau về việc ngồi ghế chờ và ghế cắt. ƒ ít tốn năng lượng (ít thao tác thừa) nhất. Phân tích : 1. Tiệm có lúc vắng, lúc nhiều khách. Thợ nên ngủ khi không có khách. Nếu được đánh thức, thợ sẽ mời từng khách đến ghế cắt và cắt tóc cho khách cho đến khi hết khách, thợ lại tiếp tục ngủ. 2. khi đến tiệm, nếu thấy còn ghế chờ, khách sẽ ngồi vào 1 ghế, đánh thức thợ rồi ngủ ngay. Khi nào thợ đánh thức và mời đến ghế cắt thì khách thức dậy và đến ngồi vào ghế cắt rồi ngủ chờ thợ cắt xong, trả tiền và ra về. Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 51 3.6 Các bài toán IPC kinh điển 3. Bài toán ở tiệm hớt tóc : //thuật giải cho thợ dùng semaphore semaphore customers = 0; semaphore barbers = 0; semaphore mutex = 1; int waiting = 0; void Barber (void) { while (còn làm việc) { down(&customers); //nếu 0 có khách, ngủ chờ down(&mutex); //đảm bảo 0 tranh chấp waiting ; //giảm số lượng khách chờ 1 đơn vị up(&barbers); //đánh thức 1 khách và mời họ cắt tóc up(&mutex); //cho phép các process khác truy xuất waiting cut_hair(); //cắt tóc cho khách } } Môn : Hệ điều hành Khoa Công nghệ Thông tin Chương 3 : Tương tranh giữa các process Trường ĐH Bách Khoa Tp.HCM Slide 52 26