Thực hành Hệ điều hành - Bài thực hành số 6: Đồng bộ

Nội dung text: Thực hành Hệ điều hành - Bài thực hành số 6: Đồng bộ

1. Từ khóa  Critical section (miền găng): đoạn mã nguồn đọc/ghi dữ liệu lên vùng nhớ chia sẻ  Race condition (tranh đoạt điều khiển): có tiềm năng bị xen kẻ lệnh giữa các tiểu trình khác nhau trong miền găng Kết quả không xác định  Mutual exclusion: cơ chế đồng bộ đảm bảo chỉ có một tiểu trình duy nhất được thực hiện trong miền găng tại một thời điểm  Deadlock: tình trạng các tiểu trình bị khóa mãi mãi  Starvation: đang thực thi nhưng không có tiến triển. ĐH KHTN TpHCM 2 TH 106: Hệ điều hành
2. Miền găng (critical section) . Đoạn mã nguồn truy cập đến vùng nhớ dùng chung gọi là miền găng // bắt đầu miền găng if (taikhoan – tien_rut >= 0) taikhoan = taikhoan – tien_rut; else cout << “Không đủ tiền trong tài khoản”; // kết thúc miền găng ĐH KHTN TpHCM 4 TH 106: Hệ điều hành
3. Giải pháp Giải pháp BUSY WAITING Giải pháp phần mềm .Sử dụng cờ hiệu .Kiểm tra luân phiên .Giải pháp Peterson Giải pháp phần cứng .Vô hiệu hóa ngắt .Chỉ thị TSL (Test-and-Set) Giải pháp “SLEEP and WAKEUP” ĐH KHTN TpHCM 6 TH 106: Hệ điều hành
4. Giải pháp Giải pháp BUSY WAITING Giải pháp phần mềm .Sử dụng cờ hiệu .Kiểm tra luân phiên .Giải pháp Peterson Giải pháp phần cứng .Vô hiệu hóa ngắt .Chỉ thị TSL (Test-and-Set) ĐH KHTN TpHCM 8 TH 106: Hệ điều hành
5. Giải pháp Giải pháp BUSY WAITING Giải pháp phần mềm .Sử dụng cờ hiệu .Kiểm tra luân phiên .Giải pháp Peterson Giải pháp phần cứng .Vô hiệu hóa ngắt .Chỉ thị TSL (Test-and-Set) ĐH KHTN TpHCM 10 TH 106: Hệ điều hành
6. Giải pháp Giải pháp BUSY WAITING Giải pháp phần mềm .Sử dụng cờ hiệu .Kiểm tra luân phiên .Giải pháp Peterson Giải pháp phần cứng .Vô hiệu hóa ngắt .Chỉ thị TSL (Test-and-Set) ĐH KHTN TpHCM 12 TH 106: Hệ điều hành
7. Giải pháp Giải pháp BUSY WAITING Giải pháp phần mềm .Sử dụng cờ hiệu .Kiểm tra luân phiên .Giải pháp Peterson Giải pháp phần cứng .Vô hiệu hóa ngắt .Chỉ thị TSL (Test-and-Set) ĐH KHTN TpHCM 14 TH 106: Hệ điều hành
8. Giải pháp Giải pháp BUSY WAITING Giải pháp phần mềm .Sử dụng cờ hiệu .Kiểm tra luân phiên .Giải pháp Peterson Giải pháp phần cứng .Vô hiệu hóa ngắt .Chỉ thị TSL (Test-and-Set) ĐH KHTN TpHCM 16 TH 106: Hệ điều hành
9. Giải pháp “SLEEP and WAKEUP” Giải pháp Peterson và TSL đều đúng, tuy nhiên chiếm thời gian CPU vì vòng lặp kiểm tra liên tục  giải pháp sleep and wakeup ĐH KHTN TpHCM 18 TH 106: Hệ điều hành
10. Semaphore Dijkstra đề xuất năm 1965 Một semaphore là 1 biến có các thuộc tính sau: Một giá trị nguyên dương e(s) Một hàng đợi f(s) lưu danh sách các tiến trình đang bị khóa Chỉ có hai thao tác được định nghĩa trên semaphore: .Down(s): giảm giá trị của semaphore s đi 1 đơn vị nếu e(s) > 0, và tiếp tục xử lý. Nếu e(s) = 0, tiến trình phải chờ đến khi e(s) >0. .Up(s): tăng giá trị của semaphore s lên 1 đơn vị. hệ thống sẽ chọn một trong các tiến trình bị khóa để cho tiếp tục thực thi. ĐH KHTN TpHCM 20 TH 106: Hệ điều hành
11. #define N 100 /* kích thước buffer */ semaphore mutex = 1; /* điều khiển vào miền găng */ semaphore empty = N; /* đếm số ô rỗng trong buffer*/ semaphore full = 0; /* đếm số ô đã chiếm trong buffer*/ void Producer(void) { int item; while (TRUE) { item = produce_item(); /* sản xuất 1 mẫu tin */ down(&empty); /* giảm ô rỗng */ down(&mutex); /* vào miền găng */ insert_item(item); /* đặt mẫu tin vào buffer */ up(&mutex); /* rời miền găng */ up(&full); /* tăng số ô đã chiếm */ } } ĐH KHTN TpHCM TH 106: Hệ điều hành
12. Buổi ăn tối của các triết gia ĐH KHTN TpHCM 24 TH 106: Hệ điều hành
13. Giải pháp 1* void philosopher(int i) {// mã số triết gia while (TRUE) { think( ); // triết gia đang suy nghĩ down(mutex); take_fork(i); // lấy nĩa bên trái take_fork((i+1) % N); // lấy nĩa bên phải eat(); // ăn spaghetti put_fork(i); // trả lại nĩa bên trái put_fork((i+1) % N); // trả lại nĩa bên phải up(mutex); } } Chỉ một triết gia được ăn tại 1 lúc ĐH KHTN TpHCM 26 TH 106: Hệ điều hành
14. Giải pháp 2 (tt) void take_forks(int i) { down(&mutex); // vào miền găng state[i] = HUNGRY; // lưu trạng thái HUNGRY test(i); // thử lấy hai nĩa up(&mutex); // ra khỏi miền găng down(&s[i]); // khóa nếu không lấy được nĩa } void put_forks(i) { down(&mutex); // vào miền găng state[i] = THINKING; // ăn xong test(LEFT); // kiểm tra thử triết gia trái có thể ăn test(RIGHT); // kiểm tra thử triết gia phải có thể ăn up(&mutex); // thoát khỏi miền găng } ĐH KHTN TpHCM TH 106: Hệ điều hành