›

Bài giảng Hệ điều hành - Chương IV: Định thời CPU - Trần Công Án

pdf 58 trang huongle 6010
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương IV: Định thời CPU - Trần Công Án", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_he_dieu_hanh_chuong_iv_dinh_thoi_cpu_tran_cong_an.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương IV: Định thời CPU - Trần Công Án

  1. CT107. Hệ Điều Hành Chương 4. Định Thời CPU Giảng viên: Trần Công Án (tcan@cit.ctu.edu.vn) Bộ môn Mạng máy tính & Truyền thông Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ 2014
  2. [CT107] Ch4. Định thời CPU Mục Tiêu Giới thiệu về tác vụ định thời cho CPU (CPU scheduling) trong các hệ điều hành đa chương, bao gồm: I các tiêu chí cho việc định thời CPU I các giải thuật định thời CPU I các tiêu chí để lựa chọn 1 giải thuật định thời cho 1 hệ thống TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 2
  3. [CT107] Ch4. Định thời CPU Nội Dung TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 3
  4. [CT107] Ch4. Định thời CPU Các khái niệm cơ bản Các Khái Niệm Cơ Bản I Định thời biểu CPU là một chức năng cơ bản và quan trọng của các HĐH đa chương. I Chức năng: phân bổ thời gian/thời điểm sử dụng CPU cho các tiến trình trong hệ thống, nhằm: I tăng hiệu năng (CPU utilisation) sử dụng CPU I giảm thời gian đáp ứng (response time) của hệ thống I Ý tưởng cơ bản: phân bố thời gian rãnh rỗi của CPU (khi chờ đợi tiến trình đang thực thi thực hiện các thao tác nhập xuất) cho các tiến trình khác trong hệ thống. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 4
  5. [CT107] Ch4. Định thời CPU Các khái niệm cơ bản Chu Kỳ CPU–I/O (CPU–I/O Burst) I Chu kỳ CPU–I/O: I Sự thực thi của tiến trình bao gồm nhiều chu kỳ CPU–I/O. I Một chu kỳ CPU–I/O bao gồm chu kỳ thực thi CPU (CPU burst) và chu kỳ chờ đợi vào/ra (I/O burst). I Sự phân bổ sử dụng CPU: I Chương trình hướng nhập xuất (I/O-bound) thường có nhiều chu kỳ CPU ngắn. I Chương trình hướng xử lý (CPU-bound) thường có nhiều chu kỳ CPU dài. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 5
  6. [CT107] Ch4. Định thời CPU Các khái niệm cơ bản Ví Dụ Về Chu Kỳ CPU–I/O ••• load store add store CPU burst read from file wait for I/O I/O burst store increment index CPU burst write to file wait for I/O I/O burst load store add store CPU burst read from file wait for I/O I/O burst ••• TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 6
  7. [CT107] Ch4. Định thời CPU Các khái niệm cơ bản Ví Dụ Về Phân Bổ Sử Dụng CPU 160 140 120 100 80 frequency 60 40 20 0 8 16 24 32 40 burst duration (milliseconds) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 7
  8. [CT107] Ch4. Định thời CPU Các khái niệm cơ bản Bộ Định Thời CPU (CPU Scheduler) I Còn gọi là bộ định thời ngắn kỳ, chọn một trong các tiến trình trong hàng đợi sẵn sàng và cấp phát CPU cho nó thực thi. I Quyết định định thời xảy ra khi một tiến trình: 1. chuyển từ trạng thái đang chạy sang trạng thái chờ đợi 2. chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng 3. chuyển từ trạng thái chờ đợi sang trạng thái sẵn sàng 4. kết thúc TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 8
  9. [CT107] Ch4. Định thời CPU Các khái niệm cơ bản Định Thời Trưng Dụng & Không Trưng Dụng I Định thời không trưng dụng (nonpreemptive scheduling): I Tiến trình được phân CPU có quyền sử dụng CPU đến khi sử dụng xong (k/thúc hoặc chuyển sang trạng thái chờ, như trường hợp 1 và 4). I Định thời trưng dụng (preemptive scheduling): I Bộ định thời có thể thu hồi CPU của tiến trình bất kỳ lúc nào để phân cho tiến trình khác (trường hợp 2 và 3). I Phức tạp hơn định thời không trưng dụng vì nó phải giải quyết: I sự cạnh tranh dữ liệu giữa các tiến trình. I sự trưng dụng khi tiến trình đang thực thi trong chế độ kernel. I dàn xếp giữa sự trưng dụng và xử lý các ngắt của hệ thống. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 9
  10. [CT107] Ch4. Định thời CPU Các khái niệm cơ bản Bộ Điều Phối (Dispatcher) I Có nhiệm vụ thực thi việc trao quyền sử dụng CPU cho tiến trình được cấp phát CPU bởi bộ định thời. I Bao gồm các tác vụ: I Chuyển ngữ cảnh I Chuyển sang chế độ người dùng I Nhảy tới vị trí thích hợp trong chương trình người dùng để khởi động lại chương trình đó. I Độ trễ điều phối (dispatcher latency): thời gian dispatcher cần để ngưng một tiến trình và khởi động một tiến trình khác. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 10
  11. [CT107] Ch4. Định thời CPU Tiêu chí cho việc định thời Tiêu Chí Cho Việc Định Thời 1. Hiệu suất sử dụng CPU: tỷ lệ giữa thời gian CPU được sử dụng trên tổng thời gian hoạt động của hệ thống. 2. Thời gian đáp ứng (response time): lượng thời gian từ lúc một yêu cầu được đệ trình cho đến khi bắt đầu được đáp ứng. 3. Thời gian chờ đợi (waiting time): tổng thời gian 1 tiến trình nằm trong hàng đợi sẵn sàng (ready queue). 4. Thời gian xoay vòng (turnaround time): tổng thời gian để thực thi một t/trình, bao gồm các khoảng t/gian: thực thi, chờ I/O, chờ trong ready queue (= t/điểm kết thúc – t/điểm bắt đầu vào ready queue). 5. Thông lượng (throughput): số lượng tiến trình hoàn thành trên một đơn vị thời gian. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 11
  12. [CT107] Ch4. Định thời CPU Tiêu chí cho việc định thời Tối Ưu Hóa Các Tiêu Chí Các giải thuật định thời được đánh giá thông qua khả năng tối ưu hóa các tiêu chí định thời của nó: 1. Hiệu suất sử dụng CPU: càng lớn càng tốt 2. Thông lượng: càng lớn càng tốt 3. Thời gian xoay vòng: càng nhỏ càng tốt 4. Thời gian chờ đợi: càng nhỏ càng tốt 5. Thời gian đáp ứng: càng nhỏ càng tốt TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 12
  13. [CT107] Ch4. Định thời CPU Các giải thuật định thời Các Giải Thuật Định Thời 1. First-come, first-served (FCFS): đến trước được phục vụ trước. 2. Shortest-job-rirst (SJF): công việc ngắn nhất trước. 3. Priority: dựa trên độ ưu tiên. 4. Round-robin (RR): xoay vòng. 5. Multilevel scheduling: hàng đợi đa cấp. 6. Multilevel feedback-queue scheduling: hàng đợi phản hồi đa cấp. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 13
  14. [CT107] Ch4. Định thời CPU Các giải thuật định thời First-come, first-served First-Come, First Served (FCFS) I Là giải thuật định thời đơn giản nhất, dựa trên nguyên tắc đến trước, được phục vụ trước. I Cài đặt: phương pháp đơn giản nhất là dùng hàng đợi FIFO. I Ưu điểm: cài đặt dễ dàng, đơn giản và dễ hiểu. I Nhược điểm: I Thời gian chờ đợi trung bình thường là dài. I Không thích hợp cho hệ thống phân chia thời gian do đây là giải thuật định thời không trưng dụng (nonpreemptive). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 14
  15. [CT107] Ch4. Định thời CPU Các giải thuật định thời First-come, first-served FCFS – Ví Dụ 1 I Cho các tiến trình với thời gian thực thi và thứ tự xuất hiện như sau: Process TG sử dụng CPU Thứ tự xuất hiện P1 24 1 P2 3 2 P3 3 3 I Biểu đồ Grant cho lịch biểu: P1 P2 P3 0 24 27 30 I Thời gian chờ đợi: P1 = 0; P2 = 24; P3 = 27 I Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 15
  16. [CT107] Ch4. Định thời CPU Các giải thuật định thời First-come, first-served FCFS – Ví Dụ 2 I Giả sử các tiến trình trong ví dụ 1 xuất hiện theo thứ tự P2, P3, P1; biểu đồ Grant của lịch biểu là: P2 P3 P1 0 3 6 30 I Thời gian chờ đợi: P1 = 6, P2 = 0, P3 = 1 I Thời gian chờ đợi trung bình: (6 + 0 + 3)/3 = 3 ⇒ tốt hơn nhiều so với ví dụ 1 (17) I Tình trạng thời gian chờ đợi dài do tiến trình ngắn nằm sau tiến trình dài được gọi là “hiệu ứng nối đuôi” (convoy effect). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 16
  17. [CT107] Ch4. Định thời CPU Các giải thuật định thời Shortest-job-first Shortest-Job-First (SJF) I Ý tưởng cơ bản: phân phối CPU cho tiến trình nào có thời gian thực thi CPU (CPU burst) kế tiếp nhỏ nhất (shortest-next-CPU-burst alg.) I Mỗi tiến trình sẽ được gán 1 độ dài thời gian của lần sử dụng CPU kế tiếp (dự đoán). I Có 2 cách tiếp cận cho việc phân bổ CPU: I Không trưng dụng: tiến trình được giao CPU sẽ chiếm giữ CPU đến khi nó thực thi xong CPU burst. I Trưng dụng: nếu 1 tiến trình mới đến có CPU burst ngắn hơn thời gian thực thi còn lại của tiến trình đang thực thi, CPU sẽ được lấy lại để giao cho tiến trình mới (shortest-remaining-time-first algorithm, SRTF) I SJF cho thời gian chờ đợi trung bình tối ưu (ngắn nhất). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 17
  18. [CT107] Ch4. Định thời CPU Các giải thuật định thời Shortest-job-first SJF Không Trưng Dụng – Ví Dụ Process TG sử dụng CPU kế ếp Thời gian xuất hiện P1 7 0 P2 4 2 P3 1 4 P4 4 5 I Biểu đồ Grant cho lịch biểu: P1 P3 P2 P4 0 7 8 12 16 I Thời gian chờ đợi trung bình: (0 + 6 + 3 + 7)/4 = 4 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 18
  19. [CT107] Ch4. Định thời CPU Các giải thuật định thời Shortest-job-first SJF Trưng Dụng – Ví Dụ Process TG sử dụng CPU kế ếp Thời gian xuất hiện P1 7 0 P2 4 2 P3 1 4 P4 4 5 I Biểu đồ Grant cho lịch biểu: P1 P2 P3 P2 P4 P1 0 2 4 5 7 11 16 I Thời gian chờ đợi trung bình: (9 + 1 + 0 + 2)/4 = 3 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 19
  20. [CT107] Ch4. Định thời CPU Các giải thuật định thời Shortest-job-first Thời Gian Sử Dụng CPU Lần Kế Tiếp I Chỉ có thể ước lượng, dựa vào lịch sử của những lần sử dụng CPU trước đó. I Thời gian sử dụng CPU kế tiếp (công thức trung bình mũ): τn+1 = αtn + (1 − α)τn I τn+1: ước lượng thời gian sử dụng CPU lần n + 1 I tn: thời gian sử dụng CPU thực tế lần thứ n I α ∈ [0, 1]: hệ số trung bình mũ, dùng để điều chỉnh trọng số cho các giá trị lịch sử (thông thường được gán giá trị 1/2) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 20
  21. [CT107] Ch4. Định thời CPU Các giải thuật định thời Shortest-job-first Thời Gian Sử Dụng CPU Lần Kế Tiếp I Ví dụ: ước lượng thời gian sử dụng CPU lần kế tiếp, với α = 1/2, τ0 = 10 12 τ i 10 8 ti 6 4 2 time CPU burst (ti) 6464131313 τ "guess" ( i) 108 66591112 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 21
  22. [CT107] Ch4. Định thời CPU Các giải thuật định thời Shortest-job-first Tùy Biến Hệ Số Trung Bình Mũ I α = 0 ⇒ τn+1 = τn = = τ0 ⇒ không tính đến lịch sử: tình trạng/sự thực thi “hiện thời” được coi như nhất thời, không có ý nghĩa. I α = 1 ⇒ τn+1 = tn ⇒ chỉ tính đến thời gian sử dụng CPU thực tế gần nhất. I α = 1/2: các giá trị lịch sử thực tế và dự đoán có trọng số tương đương. I Nếu mở rộng công thức, ta có: j n+1 τn+1 = αtn + (1 − α)αtn−1 + + (1 − α) αtn−j + (1 − α) τ0 I Vì α và (1 − α) ≤ 1, trọng số của giá trị lịch sử càng xa thì càng nhỏ. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 22
  23. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật định thời có ưu tiên Giải Thuật Định Thời Có Ưu Tiên (Priority) I Ý tưởng: I Mỗi tiến trình sẽ được gán một chỉ số ưu tiên (priority number, int) . I CPU sẽ được cấp phát cho tiến trình có chỉ số ưu tiên cao nhất, thông thường là nhỏ nhất. I SJF là trường hợp đặc biệt của giải thuật này, trong đó thời gian thực thi CPU kế tiếp đóng vai trò là chỉ số ưu tiên. I Có thể cài đặt theo phương pháp trưng dụng hay không trưng dụng. I Có thể xảy ra tình trạng “chết đói” (starvation): các tiến trình độ ưu tiên thấp không bao giờ được thực thi. ⇒ Giải pháp: dùng sự “lão hóa” (aging) – các tiến trình đang chờ đợi trong hệ thống sẽ được tăng dần độ ưu tiên theo thời gian chờ đợi. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 23
  24. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật định thời có ưu tiên Ví Dụ Process Thời điểm xuất hiện Độ ưu ên Thời gian xử lý P1 0 3 24 P2 1 1 3 P3 2 2 3 I Không trưng dụng: T/gian chờ đợi trung bình = (0 + 23 + 25)/3 = 16 Biểu đồ Grant: P1 P2 P3 0 24 27 30 I Trưng dụng: T/gian chờ đợi trung bình = (6 + 0 + 2)/3 = 2.7 Biểu đồ Grant: P1 P2 P3 P1 0 1 4 7 30 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 24
  25. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR) Giải Thuật Định Thời Luân Phiên I Bộ điều phối cấp phát xoay vòng cho mỗi tiến trình trong hàng đợi sẵn sàng một đơn vị thời gian, gọi là định mức thời gian (time quantum, thường khoảng 10–100ms). I Sau khi sử dụng hết t/gian được cấp, CPU bị thu hồi để cấp cho tiến trình khác, tiến trình bị thu hồi CPU sẽ chuyển vào hàng đợi sẵn sàng. I Bộ đếm thời gian (timer) sẽ phát ra các ngắt sau mỗi định mức thời gian để xoay vòng cấp phát CPU. I Nếu hàng đợi sẵn sàng có n tiến trình, định mức thời gian là q: I mỗi tiến trình sẽ nhận được 1/n tổng thời gian CPU, trong đó thời gian mỗi lần sử dụng tối đa là q I không có tiến trình nào chờ đợi quá lượng thời gian (n − 1) × q TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 25
  26. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR) Các Tùy Biến & Hiệu Năng I q lớn: RR trở thành giải thuật FCFS (FIFO) I q nhỏ: q phải đủ lớn so với thời gian chuyển ngữ cảnh, nếu không, hao phí chuyển ngữ cảnh sẽ rất cao. process time 10 quantum context switches 12 0 010 61 016 0 19 012345678910 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 26
  27. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR) Các Tùy Biến & Hiệu Năng process time 12.5 P1 6 12.0 P2 3 P3 1 11.5 P4 7 11.0 10.5 10.0 9.5 average turnaround time 9.0 1 234567 time quantum TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 27
  28. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật định thời luân phiên (Round-Robin, RR) Ví Dụ Process Thời gian sử dụng CPU P1 53 P2 17 P3 68 P4 24 I Với time quantum = 20 I Biểu đồ Grant: P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 I Thông thường, RR có thời gian chờ đợi trung bình lớn hơn SJF, nhưng đảm bảo thời gian đáp ứng tốt hơn. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 28
  29. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật hàng đợi đa cấp (Multilevel Queue) Giải Thuật Hàng Đợi Đa Cấp I Chia hàng đợi s/sàng ra thành nhiều hàng đợi với độ ưu tiên khác nhau, ví dụ: I foreground: tương tác, cần ưu tiên cao hơn. I background: bó, cần ít ưu tiên hơn. I Các tiến trình sẽ được phân phối vào các hàng đợi dựa trên các đặc tính như loại tiến trình (foreground/background), độ ưu tiên, . . . I Mỗi hàng đợi sẽ được áp dụng một giải thuật định thời riêng, tùy vào tính chất của hàng đợi; ví dụ: I foreground (tương tác): cần thời gian đáp ứng nhanh hơn ⇒ RR I background (bó): có thể đáp ứng chậm hơn ⇒ FCFS TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 29
  30. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật hàng đợi đa cấp (Multilevel Queue) Chiến Lược Định Thời Giữa Các Hàng Đợi I Định thời với độ ưu tiên cố định: I Phục vụ tất cả các t/trình trong hàng đợi ưu tiên cao (vd: foreground) rồi mới đến hàng đợi có độ ưu tiên thấp hơn (vd: background). I Có khả năng dẫn đến tình trạng “chết đói” (starvation) CPU. I Định thời với phân chia thời gian (time-slice): I Mỗi hàng đợi sẽ nhận được một khoảng thời gian nào đó của CPU để định thời cho các tiến trình nằm trong đó. I Ví dụ: 80% cho foreground với RR, và 20% cho background với FCFS. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 30
  31. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật hàng đợi đa cấp (Multilevel Queue) Ví Dụ Hàng Đợi Đa Cấp highest priority system processes interactive processes interactive editing processes batch processes student processes lowest priority TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 31
  32. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật hàng đợi phản hồi đa cấp (Multilevel Feedback Queue) Giải Thuật Hàng Đợi Phản Hồi Đa Cấp I Hàng đợi sẵn sàng cũng tổ chức giống như trong giải thuật Hàng đợi đa cấp. I Một tiến trình có thể di chuyển giữa các hàng đợi khác nhau. I Cơ chế định thời có thể được cài đặt theo cách: I Nếu tiến trình dùng quá nhiều thời gian CPU, nó sẽ được di chuyển vào hàng đợi có độ ưu tiên thấp hơn. I Nếu tiến trình đã chờ quá lâu trong 1 hàng đợi với độ ưu tiên thấp, nó sẽ được chuyển sang hàng đợi có độ ưu tiên cao hơn (cơ chế “sự lão hóa”). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 32
  33. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật hàng đợi phản hồi đa cấp (Multilevel Feedback Queue) Tham Số Của Bộ Định Thời I Bộ định thời đa cấp có phản hồi có thể được định nghĩa bằng những tham số sau: I Số lượng hàng đợi I Giải thuật định thời cho từng hàng đợi I Phương thức dùng để quyết định khi nào thì nâng cấp một tiến trình. I Phương thức dùng để quyết định khi nào thì hạ cấp một tiến trình I Phương thức dùng để quyết định là nên đặt tiến trình vào hàng đợi nào khi tiến trình này cần được phục vụ. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 33
  34. [CT107] Ch4. Định thời CPU Các giải thuật định thời Giải thuật hàng đợi phản hồi đa cấp (Multilevel Feedback Queue) Ví Dụ Về Hàng Đợi Phản Hồi Đa Cấp I Các hàng đợi: I Q0: FCFS + quantum-time 8ms quantum 8 I Q1: FCFS + quantum-time 16ms I Q2: original FCFS quantum 16 I Định thời: I Một tiến trình mới P sẽ được phân vào Q0 với giải thuật định thời FCFS. Khi có được CPU, nó sẽ FCFS được sử dụng tối đa 8ms. I Nếu sau 8ms, P chưa hoàn thành thì CPU sẽ bị thu hồi để phân phối cho tiến trình khác và P sẽ được chuyển sang Q1. I Tại Q1, việc định thời diễn ra tương tự, với quantum-time là 16ms. Nếu P vẫn chưa hoàn thành thì nó sẽ được chuyển sang Q2 với giải thuật FCFS. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 34
  35. [CT107] Ch4. Định thời CPU Các giải thuật định thời Chính sách, cơ chế & định thời Chính Sách, Cơ Chế & Định Thời I Chính sách (policy) và cơ chế (mechanism) có liên hệ mật thiết đến sự lựa chọn giải thuật định thời. I Policy: Cần làm điều gì (what)? I Mechanism: Làm sao (how) để làm điều đó? I Ví dụ: I Policy: tất cả các người dùng cần được công bằng. ⇒ Mechanism: sử dụng Robin-round. I Policy: Các tiến trình người dùng trả tiền có độ ưu tiên cao hơn các tiến trình người dùng miễn phí. ⇒ Mechanism: sử dụng các giải thuật trưng dụng (preemptive). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 35
  36. [CT107] Ch4. Định thời CPU Định thời đa xử lý Định Thời Đa Xử Lý (Multi-Processor) I Hệ thống đa xử lý cho phép cân bằng tải (load sharing) nhưng giải thuật định thời CPU sẽ phức tạp hơn. I Các CPU trong hệ thống đa xử lý thường đồng nhất (homogeneous). I Định thời đa xử lý đối xứng (symmetric multi-processing): I Mỗi CPU sẽ tự định thời. I Hàng đợi sẵn sàng có thể dùng chung hay riêng. I Cần quản lý sự cạnh tranh giữa các CPU khi chọn tiến trình và khi cập nhật cấu trúc dữ liệu hệ thống. I Là hệ thống hiện tại được dùng rộng rãi. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 36
  37. [CT107] Ch4. Định thời CPU Định thời đa xử lý Định Thời Đa Xử Lý (Multi-Processor) I Định thời đa xử lý bất đối xứng (asymmetric multi-processing): I Việc định thời được thực hiện bởi 1 CPU (master). I Master CPU sẽ quản lý cấu trúc dữ liệu dùng chung ⇒ giảm nhu cầu quản lý chia sẻ dữ liệu. I Có thể dẫn đến bottle-neck tại master CPU. I Ít được dùng hơn định thời đối xứng. I Có thể dùng chiến lược “bám CPU” (processor affinity) – một tiến trình sẽ được thực thi trên cùng 1 CPU trong suốt sự thực thi – để tránh tổn phí di dời tiến trình sang CPU khác. I Soft-affinity và hard-affinity. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 37
  38. [CT107] Ch4. Định thời CPU Định thời thời gian thực Định Thời Thời Gian Thực I Hệ thống thời gian thực cứng: I Phải biết chính xác thời gian mà chức năng hệ điều hành cần cho mỗi thao tác. I Chỉ được thực hiện với các phần mềm có mục đích chuyên biệt trên nền phần cứng tận hiến. I Hệ thống thời gian thực mềm: I Hệ thống phải có định thời trưng dụng. I Quá trình thời thực phải có độ ưu tiên cao nhất và không giảm, chấp nhận tình trạng không công bằng và đói tài nguyên. I Độ trễ điều phối phải nhỏ, bảo đảm đáp ứng nhanh cho tiến trình thời thực. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 38
  39. [CT107] Ch4. Định thời CPU Định thời thời gian thực Độ Trễ Điều Phối Độ Trễ Điều Phối (Dispatch Latency) event response to event I Là khoảng thời gian cần thiết để bộ định response interval process made thời chuẩn bị cho sự interrupt available phục vụ 1 tiến trình. processing I Giảm độ trễ điều phối: dispatch latency real-time I đưa điểm trưng process dụng vào lời gọi execution hệ thống dài conflicts dispatch I cho phép trưng dụng nhân time TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 39
  40. [CT107] Ch4. Định thời CPU Đánh giá giải thuật Đánh Giá Giải Thuật Phương pháp đánh giá và chọn giải thuật định thời thích hợp cho hệ thống. 1. Mô hình xác định (deterministic modeling) 2. Mô hình hàng đợi (queueing model) 3. Mô phỏng (simulation) 4. Cài đặt thực nghiệm (implementation) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 40
  41. [CT107] Ch4. Định thời CPU Đánh giá giải thuật Mô hình xác định (Deterministic) Mô Hình Xác Định I Dựa vào tải công việc (workload) được xác định trước và tính toán hiệu năng của mỗi giải thuật (như thời gian chờ trung bình, . . . ). I Ưu điểm: Đơn giản, nhanh. I Khó khăn: đòi hỏi tập hợp thông tin chính xác thông tin đầu vào ⇒ khó thực hiện trong thực tế. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 41
  42. [CT107] Ch4. Định thời CPU Đánh giá giải thuật Mô hình hàng đợi (Queuing) Mô Hình Hàng Đợi I Dựa vào sự phân bổ thời gian thực thi CPU và I/O (CPU, I/O burst) và thời gian đến (arrival-time). I Thường phân phối theo 1 hàm nào đó (thường là hàm mũ – exponential distribution). I Dựa vào các phân phối trên, ta có thể tính hiệu năng của mỗi giải thuật (hiệu năng CPU, t/gian chờ trung bình, chiều dài hàng đợi trung bình) I Chiều dài hàng đợi trung bình (công thức Little): n = λ × W I λ: tỉ lệ đến trung bình của các tiến trình mới (tiến trình/s) I W : thời gian chờ trung bình trong hàng đợi. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 42
  43. [CT107] Ch4. Định thời CPU Đánh giá giải thuật Mô phỏng (Simulation) Mô Phỏng performance simulation statistics for FCFS FCFS • • • CPU 10 I/O 213 actual CPU 12 performance process I/O 112 simulation statistics execution CPU 2 for SJF I/O 147 SJF CPU 173 • • • trace tape performance simulation statistics for RR (q 14) RR (q 14) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 43
  44. [CT107] Ch4. Định thời CPU Đánh giá giải thuật Cài đặt thực nghiệm (Implementation) Cài Đặt Thực Nghiệm I Cài đặt giải thuật vào hệ điều hành thật cùng với các phương tiện đo lường. I Thực thi các tiến trình và đo lường hiệu năng của giải thuật trên hệ thống thật. I Ưu điểm: Độ chính xác cao. I Khó khăn: I Đòi hỏi chi phí cao I Người dùng có thể phản ứng với sự thay đổi liên tục của hệ thống. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 44
  45. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định Thời Trong Một Số HĐH 1. Windows 7 2. Linux 3. Solaris TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 45
  46. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Windows Định Thời Trong Windows I Đơn vị cấp phát CPU trong các HĐH hiện nay là luồng (thread) thay vì tiến trình. I HĐH Windows dùng giải thuật định thời dựa trên độ ưu tiên (32 mức) và định mức thời gian (RR), sử dụng chiến lược trưng dụng. I Mỗi độ ưu tiên sẽ có 1 hàng đợi riêng. I Một luồng được chọn thực thi bởi bộ điều phối sẽ t/thi cho đến khi: I bị trưng dụng bởi luồng có mức ưu tiên cao hơn, hoặc I kết thúc (terminate), hoặc I hết định mức thời gian (time quantum), hoặc I thực hiện lời gọi I/O. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 46
  47. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Windows Định Thời Trong Windows I Độ và nhóm ưu tiên của các luồng được chia như sau: real- above below idle high normal time normal normal priority time-critical 31 15 15 15 15 15 highest 26 15 12 10 8 6 above normal 25 14 11 9 7 5 normal 24 13 10 8 6 4 below normal 23 12 9 7 5 3 lowest 22 11 8 6 4 2 idle 16 1 1 1 1 1 I Ngoài ra, một số cơ chế để nâng/hạ độ ưu tiên cho cá luồng cũng được sử dụng (tương tự ý tưởng của g/thuật hàng đợi phản hồi đa cấp) TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 47
  48. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Windows Chọn Lựa Tiến Trình Trong Windows I Bộ định thời duyệt qua các hàng đợi theo độ ưu tiên từ cao đến thấp. I Nếu không có tiến trình nào sẵn sàng, bộ định thời khởi động 1 tiến trình đặc biệt gọi là idle process. I Độ ưu tiên của t/trình bị trưng dụng có thể bị thay đổi. I Nếu sử dụng hết time quantum: độ ưu tiên giảm, nhưng không dưới mức “normal”. I Chuyển từ trạng thái chờ (waiting): độ ưu tiên tăng, mức độ tăng phụ thuộc vào t/trình đã chờ cái gì: đĩa – tăng nhiều, I/O – tăng ít hơn. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 48
  49. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Linux Định Thời Trong Linux I Giải thuật định thời chính cho Linux từ kernel 2.6.23 là giải thuật Completely Fair Scheduler (CFS), dựa trên sự ưu tiên có thay đổi. I Tiêu chí: I Giải thuật định thời phải nhanh, O(1) ⇒ hỗ trợ tốt cho các hệ SMP. I Cho hiệu năng tốt đối với các interactive processes. I Công bằng (fairness) I Tối ưu cho trường hợp thông dụng nhất là hệ thống có 1 đến 2 t/trình, nhưng phải scale cho trường hợp có nhiều t/trình hoặc nhiều CPU. I Dùng k/niệm tác vụ (task) để chỉ tiến trình (process) và luồng (thread). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 49
  50. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Linux Định Thời Trong Linux I Các t/vụ được phân chia thành 2 nhóm chính: default scheduling class và real-time scheduling class. I Default scheduling class: định thời bằng giải thuật CFS (trưng dụng), trong đó tỷ lệ sử dụng CPU được tính dựa trên nhiều tham số của t/vụ như nice value (nicer thread, lower priority), virtual run time,. . . I Real-time scheduling class: các t/vụ được gán độ ưu tiên cố định dựa vào nice value của các luồng. time quantum 200 ms 10 ms real-me normal priority 0 99 100 139 higher lower TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 50
  51. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Linux Chọn Lựa Tiến Trình Trong Linux I Bộ định thời duy trì 2 hàng đợi: 1. Active queue: chứa các t/vụ sẵn sàng thực thi và còn time slice. 2. Expired queue: chứa các t/vụ sẵn sàng thực thi nhưng hết time slice. I Các t/vụ trong cùng hàng đợi được sắp xếp dựa vào độ ưu tiên. I Bộ định thời sẽ lựa t/vụ có độ ưu tiên cao nhất trong active queue. I Nếu một t/vụ bị trưng dụng CPU, nó sẽ trở lại active queue với độ ưu tiên không đổi. I Nếu một tác vụ hết time quantum, độ ưu tiên của nó sẽ được tính lại và được đưa vào expired queue. I Nếu active queue rỗng: swap(expired queue, active queue). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 51
  52. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Solaris Định Thời Trong Solaris I Sử dụng định thời dựa trên độ ưu tiên. I Bộ định thời sử dụng 6 hàng đợi: Time-sharing (TS), Interactive (IA), Real time (RT), System (SYS), Fair share (FSS), Fixed priority (FP). I Mỗi hàng đợi có độ ưu tiên khác nhau và g/thuật định thời khác nhau. I Độ ưu tiên của luồng ảnh hưởng đến time slice dành cho luồng và có thể bị thay đổi (hàng đợi phản hồi đa cấp). I Tính tương tác của luồng (interactive/CPU-bound) cũng ảnh hưởng đến độ ưu tiên. I Độ ưu tiên của các luồng có giá trị từ 0 (lowest) đến 160 (highest). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 52
  53. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Solaris Định Thời Trong Solaris global scheduling priority order 169 highest first ∗ Real-time class: interrupt threads 160 159 I độ ưu tiên cao nhất I đảm bảo t/gian đáp ứng realtime (RT) threads I một ít kernel process được phân vào h/đợi này ∗ System class: 100 99 I kernel process được phân vào h/đợi này system (SYS) threads I độ ưu tiên được gán cố định 60 ∗ Time-sharing: độ ưu tiên có thể thay đổi. 59 fair share (FSS) threads ∗ Fixed-priority: độ ưu tiên không thay đổi. fixed priority (FX) threads timeshare (TS) threads ∗ Fair-share: chia sẻ CPU, không ưu tiên. interactive (IA) threads lowest 0 last TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 53
  54. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Solaris Real-Time Scheduling I Dùng giải thuật FCFS hoặcRR. I Sử dụng định thời trưng dụng: tiến trình ưu tiên cao có thể trưng dụng CPU của tiến trình ưu tiên thấp. I Có rất ít tiến trình được vào hàng đợi này. TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 54
  55. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Solaris Time-Sharing Scheduling I Sử dụng g/thuật hàng đợi phản hồi đa cấp, với độ ưu tiên thay đổi: I Mỗi hàng đợi có một độ ưu tiên khác nhau. I Time slice phụ thuộc vào độ ưu tiên (higher priority, smaller time slice) I Solaris sử dụng một bảng điều phối để điều khiển việc định thời: I Nếu một luồng s/dụng hết time quantum (CPU-intensive process), độ ưu tiên của nó sẽ giảm ⇒ tăng thông lượng (throughput). I Nếu một luồng trở lại từ t/thái waiting (e.g. chờ I/O), độ ưu tiên của nó sẽ tăng ⇒ giảm t/gian đáp ứng (response time). I Chiến lược định thời này giúp các interactive process (như quản lý giao diện đồ họa) có độ ưu tiên cao (giảm t/gian đáp ứng). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 55
  56. [CT107] Ch4. Định thời CPU Định thời trong một số hệ điều hành Định thời trong Solaris Bảng Điều Phối (Solaris Dispatching Table) time return time quantum from priority quantum expired sleep 0 200 0 50 I time quantum: t/gian cấp 5 200 0 50 phát cho t/trình tương ứng 10 160 0 51 với độ ưu tiên (tỷ lệ nghịch) 15 160 5 51 20 120 10 52 I time quantum expired: độ 25 120 15 52 ưu tiên gán lại cho t/trình 30 80 20 53 sau khi s/dụng hết time 35 80 25 54 quantum 40 40 30 55 I return from sleep: độ ưu 45 40 35 56 tiên gán cho t/trình trở về 50 40 40 58 từ t/thái waiting 55 40 45 58 59 20 49 59 TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 56
  57. [CT107] Ch4. Định thời CPU Tổng Kết Tổng Kết I Sự thực thi của một t/trình: chu kỳ CPU–I/O (CPU–I/O burst). I Bộ định thời (scheduler): chọn 1 tiến trình từ hàng đợi sẵn sàng. I Bộ điều điều phối (dispatcher): thực hiện switching. I Các tiêu chí định thời (có thể xung đột nhau): hiệu suất s/dụng CPU, thông lượng, t/gian xoay vòng, t/gian chờ đợi, t/gian đáp ứng. I Các giải thuật định thời: FCFS, SJF, Priority, Robin-round, Multilevel [feedback-queue] scheduling. I Định thời trên hệ thống đa xử lý (multi-processor): đối xứng, bất đối xứng. I Định thời thời gian thực, độ trễ điều phối (đọc thêm). I Đánh giá g/thuật định thời: mô hình xác định (deterministic), mô hình hàng đợi (queuing), mô phỏng (simulation), cài đặt thực nghiệm (implementation). TS. Trần Công Án (Khoa CNTT&TT) [CT107] Ch4. Định thời CPU 57