Thực hành Hệ điều hành - Bài thực hành số 5: Điều phối CPU

Nội dung text: Thực hành Hệ điều hành - Bài thực hành số 5: Điều phối CPU

1. Là gì, tại sao? Điều phối CPU là gì? Tại sao? Đầu tiên là để chia sẻ tài nguyên tốn kém – đa chương Ngày nay có thể thực thi nhiều tác vụ cùng lúc vì processor rất mạnh ĐH KHTN TpHCM 2 TH 106: Hệ điều hành
2. Ví dụ đa chương trình Process A 1 sec start idle; input idle; input stop Process B start idle; input idle; input stop Time = 10 seconds ĐH KHTN TpHCM 4 TH 106: Hệ điều hành
3. Ví dụ đa chương trình (tt) Process A start idle; input idle; input stop A context switch context switch to B to A Process B idle; input idle; input stop B Hiệu suất = 2 cv 11 giây = 0.18 cv/giây Tg chờ trung bình = (0+1)/2 = 0.5 giây ĐH KHTN TpHCM 6 TH 106: Hệ điều hành
4. Chúng ta cần tối ưu hóa những gì? Phần hệ thống: Tận dụng processor: phần trăm sử dụng processor Hiệu suất: số tiến trình hoàn thành trên một đơn vị thời gian Phần người dùng: Turnaround time: khoảng thời gian giữa bắt đầu cv và kết thúc cv (gồm thời gian chờ). Cho cv theo lô, tuần tự Response time: cho những cv tương tác, thời gian từ khi gửi yêu cầu cho đến khi nhận được phản hồi Deadlines: khi thời hạn thực thi của tiến trình được xác định, thì phần trăm hoàn thành đúng thời hạn phải được quan tâm ĐH KHTN TpHCM 8 TH 106: Hệ điều hành
5. Đặc tính của công việc ĐH KHTN TpHCM 10 TH 106: Hệ điều hành
6. Sơ đồ hàng đợi Vào ready queue CPU Thoát Disk 1 disk queue Disk 2 Network network queue I/O other I/O queue ĐH KHTN TpHCM 12 TH 106: Hệ điều hành
7. Đặc tính công việc CPU I/O-bound jobs CV liên tục truy suất I/O Ít dùng đến CPU CPU-bound jobs CV truy suất I/O rất ít Dùng CPU nhiều Disk ĐH KHTN TpHCM 14 TH 106: Hệ điều hành
8. Điều phối Bộ điều phối trao điều khiển CPU cho tiến trình được chọn bởi lập lịch short-term; quá trình này gồm: switching context Chuyển qua user mode Nhảy tới vị trí thích hợp trong chương trình để bắt đầu thực thi nó Độ trễ điều phối – thời gian để bộ điều phối dừng tiến trình này và bắt đầu một tiến trình kia. ĐH KHTN TpHCM 16 TH 106: Hệ điều hành
9. Lập lịch FCFS (tt.) Giả sử tiến trình đến theo thứ tự P2 , P3 , P1 . Gantt chart của lập lịch như sau: P2 P3 P1 0 3 6 30 Thời gian chờ P1 = 6; P2 = 0; P3 = 3 Trung bình thời gian chờ: (6 + 0 + 3)/3 = 3 Tốt hơn nhiều so với trường hợp trước. Convoy effect tiến trình ngắn có thể nằm sau tiến trình dài ĐH KHTN TpHCM 18 TH 106: Hệ điều hành
10. Ví dụ Non-Preemptive SJF Tiến trình Thời điểm đến Thời gian dùng CPU P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (non-preemptive) P1 P3 P2 P4 0 3 7 8 12 16 Trung bình thời gian chờ = (0 + 6 + 3 + 7)/4 = 4 ĐH KHTN TpHCM 20 TH 106: Hệ điều hành
11. Xác định thời gian sử dụng CPU kế tiếp Chỉ có thể ước lượng. Sử dụng thời gian sử dụng CPU ngay trước, dùng qui luật trung bình giảm theo hàm mũ. th 1. tn actual lenght of n CPU burst 2.  n 1 predicted value for the next CPU burst 3. , 0 1 4. Define :  n 1 tn 1  n. ĐH KHTN TpHCM 22 TH 106: Hệ điều hành
12. Điều phối theo độ ưu tiên Một độ ưu tiên (integer) được gán vào mỗi tiến trình CPU được cấp cho tiến trình có độ ưu tiên cao nhất (số nhỏ nhất  độ ưu tiên cao nhất). Preemptive nonpreemptive SJF là một dạng điều phối theo độ ưu tiên (độ ưu tiên: dự đoán thời gian CPU burst kế tiếp). Vấn đề  Starvation – các tiến trình độ ưu tiên thấp có thể không bao giờ thực thi được. Giải pháp  Aging – tiến trình sẽ tăng độ ưu tiên theo thời gian. (sống lâu lên lão làng ) ĐH KHTN TpHCM 24 TH 106: Hệ điều hành
13. Ví dụ: RR với Time Quantum = 20 Tiến trình Thời gian dùng CPU P1 53 P2 17 P3 68 P4 24 Biểu đồ Gantt: P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 Thường là, trung bình turnaround time cao hơn SJF, nhưng sự phản hồi tốt hơn. ĐH KHTN TpHCM 26 TH 106: Hệ điều hành
14. Turnaround Time thay đổi tùy theo Time Quantum ĐH KHTN TpHCM 28 TH 106: Hệ điều hành
15. Điều phối hàng đợi đa cấp ĐH KHTN TpHCM 30 TH 106: Hệ điều hành
16. Multilevel Feedback Queues ĐH KHTN TpHCM 32 TH 106: Hệ điều hành
17. Điều phối trong UNIX truyền thống Multilevel feedback queues 128 Độ ưu tiên khác nhau (0-127) 1 Round Robin queue cho mỗi độ ưu tiên Cứ mỗi sự kiện điều phối, bộ điều phối chọn hàng đợi không rỗng có độ ưu tiên thấp nhất và thực thi công việc theo round- robin Sự kiện điều phối : Clock interrupt (ngắt đồng hồ) Tiến trình gọi một system call Tiến trình ngừng sử dụng CPU,v.d. thực hiện tác vụ I/O ĐH KHTN TpHCM 34 TH 106: Hệ điều hành
18. Tính độ ưu tiên trong UNIX Cứ mỗi 4 ngắt đồng hồ độ ưu tiên được cập nhật: utilizatio n P BASELINE 2NiceFactor 4 Giá trị utilization tăng lên 1 sau mỗi ngắt đồng hồ. niceFactor giúp điều khiển độ ưu tiên. Giá trị có thể gán từ –20 đến +20. Các công việc sử dụng nhiều CPU thì độ ưu tiên sẽ tăng. Các công việc sử dụng ít CPU thì độ ưu tiên sẽ trở về baseline. ĐH KHTN TpHCM 36 TH 106: Hệ điều hành
19. Giảm độ ưu tiên trong UNIX 1 cv trong CPU Load vì vậy = 1. Giả sử niceFactor = 0. Tính utilization tại thời điểm N: 2 +1 second: U U 1 3 0 2 2 2 2 2 +2 seconds U2 U1 U0 U1 U0 3 3 3 3 2 2 2 +N seconds Un Un 1 Un 2 3 3 ĐH KHTN TpHCM 38 TH 106: Hệ điều hành
20. Ví dụ tiến trình định thời Deadline B1 Deadline A1 Deadline C1 A A1 A2 A3 A4 B B1 B2 B3 C C1 C2 C3 0 10 20 30 40 50 60 70 80 90 100 110 ĐH KHTN TpHCM 40 TH 106: Hệ điều hành
21. RMS (rate monotonic scheduling) A A1 A2 A3 A4 B B1 B2 B3 C C1 C2 C3 RMS A1 B1 C1 A2 B2 C2 A3 B3 A4 C3 EDF A1 B1 C1 A2 B2 C2 A3 B3 A4 C3 0 10 20 30 40 50 60 70 80 90 100 110 ĐH KHTN TpHCM 42 TH 106: Hệ điều hành
22.  Liu và Layland chứng minh rằng, trong các hệ thống có m tiến trình định kỳ, nếu thì RMS sẽ điều phối thành công. ĐH KHTN TpHCM 44 TH 106: Hệ điều hành
23. Ưu ái bộ xử lý CPU CPU Truy caäp chaäm Truy caäp nhanh Truy caäp nhanh Maùy tính NUMA – nonuniform memory access ĐH KHTN TpHCM 46 TH 106: Hệ điều hành
24. Multithreaded processor Luoàng 1 C M C M Luoàng 0 C M C M C Thôøi gian ĐH KHTN TpHCM 48 TH 106: Hệ điều hành