›
›

Bài giảng Hệ điều hành - Chương 4: Định thời CPU - Hà Duy An

pdf 44 trang huongle 8251
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 4: Định thời CPU - Hà Duy An", để 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_4_dinh_thoi_cpu_ha_duy_an.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 4: Định thời CPU - Hà Duy An

  1. Khoa Cơng Nghệ Thơng Tin & Truyền Thơng ĐạihọcCầnThơ Giảng viên: Hà Duy An 9/19/2013 1 Chương 4: Định thời CPU
  2. 1. Các khái niệm 2. Các giảithuật định thời 3. Định thờitronghệ thống cĩ nhiềubộ xử lý 4. Đánh giá giảithuật 9/19/20132 Chương 4: Định thời CPU
  3. • Kỹ thuật đachương giúp việcsử dụng CPU đạthiệuquả cao nhất. • Chu kỳ CPU-I/O o Sự thựcthicủatiếntrìnhbaogồm nhiềuchukỳ CPU-I/O o Mộtchukỳ CPU-I/O bao gồmchukỳ thực thi CPU (CPU burst) và theo sau bởichukỳ chờđợi vào/ra (I/O burst). => Việc phân phối chu kỳ CPU-I/O là một đặt điểmquantrọng để chọnlựagiảithuật định thời phù hợp 9/19/20134 Chương 4: Định thời CPU
  4. 9/19/20135 Chương 4: Định thời CPU
  5. • Bộđịnh thờiCPUhay bộđịnh thờingắnkỳ (Short-term scheduler) chọnmột trong các tiếntrìnhtronghàngđợisẵnsàngvà cấpphátCPUchonĩthựcthi o Hàng đợicĩthểđượcsắpxếp theo nhiều cách • Quyết định định thờixảy ra khi mộttiến trình: 1. Chuyểntừ trạng thái đang chạysangtrạng thái chờđợi 2. Chuyểntừ trạng thái đang chạysangtrạng thái sẵnsàng 3. Chuyểntừ trạng thái chờđợisangsẵnsàng 4. Kết thúc • Định thời khơng trưng dụng (nonpreemptive): tiếntrìnhsẽ giữ CPU và chỉ giải phĩng CPU khi nĩ cần(trường hợp 1 và 4) • Định thờitrưng dụng (preempty): các trường hợp 2 và 3; Vấn đề: o Tiếntrìnhđang cậpnhậtdữ liệuchiasẽ chung? o Tiếntrìnhđang xử lý trong chếđộnhân (kernel mode)? o Khơng thể bỏ qua tấtcả các ngắt? 9/19/20136 Chương 4: Định thời CPU
  6. • Bộđiềuphối (Dispatcher): Cĩ nhiệmvụ trao quyền điều khiểnCPUchotiếntrình đượcchọnbởibộđịnh thờiCPU, cơng việcnàybaogồm: o Chuyểnngữ cảnh o Chuyểnsangchếđộngười dùng o Nhảytớivị trí thích hợp trong chương trình người dùng để khởi động lạichương trình đĩ • Bộđiềuphốicần nhanh nhấtcĩthể. • Độ trễđiềuphối (Dispatch Latency): thời gian Dispatcher cần để ngưng mộttiến trình và khởi động mộttiến trình khác 9/19/20137 Chương 4: Định thời CPU
  7. 1. Hiệusuấtsử dụng CPU:giữ CPU luơn bận nhiềunhấtcĩthể. 2. Thơng lượng (Throughput): số lượng tiếntrìnhhồnthànhtrên một đơnvị thờigian. 3. Thời gian xoay vịng (Turnaround time): là khoảng thờigiantừ khi mộttiếntrìnhđượckhởitạo đến khi nĩ hồn thành. Nĩ là tổng các khoảng thờigianchờđợi để đưavàobộ nhớ,chờ trong hàng đợisẵnsàng,thờigianthựcthitrênCPUvàthựchiện các xử lý I/O. 4. Thờigianchờđợi (Waiting time): tổng thời gian trong trong hàng đợisẵn sàng (ready queue). 5. Thờigianđáp ứng (Response time): lượng thờigiantừ lúc một yêu cầu được đệ trình cho đến khi tín hiệutrả lời đầu tiên xuấthiện (dùng cho mơi trường chia thờigian). 9/19/20138 Chương 4: Định thời CPU
  8. • Việc đánh giá giảithuật định thời đượckiểm tra thơng qua khả năng tối ưu hĩa các tiêu chí đinh thờicủa nĩ: o Hiệusuấtsử dụng CPU tối đa o Thơng lượng tối đa o Thời gian xoay vịng tốithiểu o Thờigianchờđợitốithiểu o Thờigianđáp ứng tốithiểu 9/19/20139 Chương 4: Định thời CPU
  9. 1. First-Come, First-Served 2. Shortest-Job-First 3. Priority 4. Round-Robin 5. Hàng đợi đacấp 6. Hàng đợiphảnhồi đacấp 9/19/201311 Chương 4: Định thời CPU
  10. Tiến Trình TG sử dụng CPU P1 24 P2 3 P3 3 • Giả sử các tiến trình xuấthiệntheothứ tự P1,P2,P3.Biểu đồ Gantt cho lịch biểulà: P1 P2 P3 0 24 27 30 • Thờigianchờđợi: P1 =0;P2 = 24; P3 =27 • Thờigianchờđợi trung bình: (0 + 24 + 27)/3 = 17 9/19/201312 Chương 4: Định thời CPU
  11. • Giả sử các tiến trình xuấthiệntheothứ tự P2,P3,P1.Biểu đồ Gantt cho lịch biểulà: P2 P3 P1 0 3306 • Thờigianchờđợi: P1=6;P2 =0;P3 =3 • Thờigianchờđợi trung bình: (6 + 0 + 3)/3 = 3 • Tốthơn nhiềusovớitrường hợptrước. • Tác động nối đuơi: tiến trình ngắnnằmsautiến trình dài. • FCFS là giảithuật định thời khơng trưng dụng, khơng thích hợp cho hệ thống chia thờigian. 9/19/201313 Chương 4: Định thời CPU
  12. • Kếthợpvớimỗitiếntrìnhđộ dài thờigianmànĩsẽ sử dụng CPU lầnkế tiếp. Khi CPU rãnh, nĩ sẽđượccấpchotiếntrình cĩ thờigiansử dụng CPU lầnkế tiếpngắnnhất. • Cĩ hai cách thứcthựchiệngiảithuật: o Khơng trưng dụng:một khi CPU đượcgiaochomộttiến trình, nĩ khơng thể bị trưng dụng để giao cho tiến trình khác cĩ thời gian ngắnhơnchođến khi tiến trình này sử dụng CPU xong. o Trưng dụng:nếumộttiếntrìnhmới đếncĩthờigiansử dụng CPU ngắnhơnthờigianthựcthicịn lại củatiếntrìnhđang chạy, thì ưutiêngiaoCPUchotiếntrìnhmới đến. Cách thứcnàyđược gọilàShortest-Remaining-Time-First(SRTF). • SJF là tối ưu–nĩtạorathờigianchờđợi trung bình ngắn nhất. 9/19/201314 Chương 4: Định thời CPU
  13. Tiếntrình TGđếnTGsử dụng CPU P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (khơng trưng dụng) P1 P3 P2 P4 0 3167 8 12 • Thờigianchờđợi trung bình = (0 + 6 + 3 + 7)/4 = 4 9/19/201315 Chương 4: Định thời CPU
  14. Tiếntrình TGđếnTGsử dụng CPU P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 • SJF (trưng dụng) P1 P2 P3 P2 P4 P1 0 2 4 5 7 11 16 • Thờigianchờđợi trung bình = (9 + 1 + 0 +2)/4 = 3 • Bài Tập 9/19/201316 Chương 4: Định thời CPU
  15. • Chỉ cĩ thểướclượng độ dài – cĩ thể tương tự như lầnsử dụng trước đĩ. • Độ dài ướclượng được tính tốn dựatrênchiềudàithờigian sử dụng CPU lầntrước đĩ, sử dụng cơng thức trung bình mũ: 1. tn thời gian sử dụng CPU thực tế lần thứ n 2.  n 1 ước lượng thời gian sử dụng CPU lần thứ n 1 3. , 0 1 4. Định nghĩa :  n 1 tn (1 ) n • Thơng thường α =½ 9/19/201317 Chương 4: Định thời CPU
  16. 9/19/201318 Chương 4: Định thời CPU
  17. • α =0 o τn+1 = τn o Khơng tính đếnthờigiansử dụng CPU gầnnhất • α =1 o τn+1 =tn o Chỉ tính đếnthờigiansử dụng CPU thựcgầnnhất • α =1/2, lịch sử quá khứ và gần đây cĩ trọng số tương đương. • Nếumở rộng cơng thức, ta cĩ: j+1 n+1 τn+1 = α tn+(1 - α) α tn-1 + +(1 - α ) α tn-j + +(1 - α ) τ0 • Vì α và (1- α)nhỏ hơnhaybằng 1, mỗisố hạng tiếptheocĩ trọng số nhỏ hơnsố hạng trước đĩ. 9/19/201319 Chương 4: Định thời CPU
  18. • Mộtchỉ sốưu tiên được gán cho mỗitiếntrình • CPU sẽđượccấpchotiếntrìnhcĩđộ ưu tiên cao nhất, nghĩa là chỉ sốưu tiên nhỏ nhất (smallest integer ≡ highest priority). • Cĩ thể trưng dụng hoặc khơng trưng dụng • SJF là mộttrường hợpcủa định thời ưu tiên, trong đĩ độ ưu tiên là thờigianước tính sử dụng CPU lầnkế tiếp. • Vấn đề đĩi CPU (starvation): các tiếntrìnhcĩđộ ưutiênthấp cĩ khả năng khơng bao giờđượcthực thi. • Giải pháp: đặtthờihạn(aging) – khi thờigiantrơiđi, độ ưu tiên củatiếntrìnhcàngtăng theo. 9/19/201320 Chương 4: Định thời CPU
  19. ProcessA arri Burst TimeT Priority P1 10 3 P2 11 P3 24 P4 15 P5 52 • Priority scheduling Gantt Chart P2 P5 P1 P3 P4 0 1 6 16 18 19 • Average waiting time = 8.2 msec 9/19/201321 Chương 4: Định thời CPU
  20. • MỗitiếntrìnhđượcCPUphụcvụ trong một đơnvị thờigiannhỏ, gọilà định mứcthời gian (time quantum), thường là 10-100 milliseconds. • Sau khoảng thờigiannày,CPUbị trưng dụng và giao cho tiếntrình khác, tiếntrìnhbị ngưng và chuyển vào hàng đợisẵnsàng. • Nếucĩntiếntrình đang nằm trong hàng đợisẵnsàngvà định mức thờigianlàq,thìmỗitiếntrìnhsẽ nhận được1/ntổng thờigiancủa CPU, thờigianphụcvụ củaCPUchonĩtối đalàq.Sẽ khơng cĩ tiến trình nào phảichờđợi quá lượng thời gian là (n-1)q. • Bộđiếmthờigian(Timer)sẽ phát ra các ngắt (interrupt) sau mỗi định mứcthờigianđể định thờichotiếntrìnhtiếptheo • Hiệunăng: o qlớn ⇒ FCFS (FIFO) o qnhỏ⇒ qphải đủ lớndotaphải quan tâm đếnviệc chuyển đổingữ cảnh, nếu khơng, thờigianlãngphísẽ rất cao. o qthường 10-100 ms, context switch < 10 μsec 9/19/201322 Chương 4: Định thời CPU
  21. 9/19/201323 Chương 4: Định thời CPU
  22. 80% of CPU bursts should be shorter than q 9/19/201324 Chương 4: Định thời CPU
  23. Process TG sử 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 thường, RR cĩ thờigianchờđợi trung bình lớnhơn SJF, nhưng đảmbảothờigianđáp ứng tốthơn. 9/19/201325 Chương 4: Định thời CPU
  24. • Hàng đợi sẵn sàng được chia thành nhiều hàng đợi, tiến trình được gán cố định vào một hàng đợi, vd: o foreground (interactive): cần thời gian đáp ứng nhanh hơn -> ưu tiên hơn; o background (batch): cĩ thể đáp ứng chậm hơn -> ít ưu tiên hơn. • Mỗi hàng đợi cĩ giải thuật lập lịch biểu riêng: o foreground – RR o background – FCFS • Thực hiện định thời giữa các hàng đợi, 2 khả năng: o Định thời với độ ưu tiên cố định (nghĩa là, phục vụ tất cả tiến trình trong foreground trước rồi đến background). Cĩ khả năng dẫn đến việc đĩi CPU. o Phân chia thời gian (time slice) – mỗi hàng đợi nhận được một khoảng thời gian phục vụ nào đĩ của CPU để định thời cho các tiến trình nằm trong đĩ; VD 80% cho foreground với RR và 20% cho background với FCFS 9/19/201326 Chương 4: Định thời CPU
  25. 9/19/201327 Chương 4: Định thời CPU
  26. • Mộttiếntrìnhcĩthể di chuyểngiữa các hàng đợi khác nhau. • Cơ chếđịnh thờihạncĩthểđược cài đặt theo cách: o Nếutiến trình dùng quá nhiềuthờigianCPU,nĩsẽđượcdichuyểnvào hàng đợicĩđộ ưu tiên thấphơn; o Nếutiếntrìnhđãchờ quá lâu trong 1 hàng đợivới độ ưu tiên thấp, nĩ sẽđược chuyển sang hàng đợicĩđộ ưu tiên cao hơn=>aging • Bộđịnh thời đacấpcĩphảnhồi được định nghĩabằng những tham số sau: o Số lượng hàng đợi o Giảithuật định thờichotừng hàng đợi o Phương thức dùng để quyết định khi nào thì nâng cấpmộttiếntrình. o Phương thức dùng để quyết định khi nào thì hạ cấpmộttiếntrình o Phương thức dùng để quyết định là nên đặttiếntrìnhvàohàngđợinào khi tiến trình này cần đượcphụcvụ. 9/19/201328 Chương 4: Định thời CPU
  27. • Cĩ3hàngđợi: o Q0: định mứcthờigianlà8 milliseconds o Q1: định mứcthờigianlà 16 milliseconds o Q2:FCFS • Định thời: o Một cơng việcmớisẽ bướcvào Q0 mà ở đĩnĩsẽđượcphụcvụ theo kiểu FCFS. Khi đạt được CPU, cơng việcsẽ nhận đượcthời gian 8 milliseconds. Nếu nĩ khơng hồn thành trong vịng 8 milliseconds, cơng việcsẽđược chuyển sang Q1. o Tại Q1 cơng việcsẽ lại đượcphụcvụ theo kiểu FCFS và nhận được thêm 16 milliseconds. Nếunĩvẫnchưa hồn thành, nĩ sẽ bị tước CPU và chuyển qua Q2. 9/19/201329 Chương 4: Định thời CPU
  28. • Định thờiCPUsẽ phứctạphơnvới nhiềuCPUhiệnhữu. • Các bộ xử lý giống nhau trong cùng mộthệ thống đaxử lý. • Việc định thờicĩthể thựchiện: o Đaxử lý bất đốixứng (Asymmetric Multiprocessor): chỉ một CPU truy cập đến các cấutrúcdữ liệu dùng chung => giảmviệc bảovệ các dữ liệu dùng chung o Đaxử lý đốixứng (Symmetric Multiprocessor): mỗiCPUtự định thờitừ hàng đợi chung, hay cĩ riêng mộthàngđợichomỗi CPU => đang đượcsử dụng phổ biến ngày nay • Thực thi mộttiến trình trên cùng mộtbộ xử lý trong suốttiến trình thực thi củatiến trình – processor affinity o Soft affinity o Hard affinity 9/19/201331 Chương 4: Định thời CPU
  29. Note that memory-placement algorithms can also consider affinity 9/19/201332 Chương 4: Định thời CPU
  30. • Đốivớihệ thống SMP cầngiữ tải cân bằng giữa các CPU nhằm nâng cao hiệuquả hoạt động củahệ thống • Cân bằng tải (load balancing) đượcthựchiệnbằng cách cố gắng phân phối các cơng việc cho các CPU bằng nhau: o Push migration – định kỳ kiểmtratảitrênmỗiCPU,nếuCPU nào bị quá tảithì"đẩy"bớt cơng việc cho CPU khác o Pull migration – các CPU rãnh "kéo" các cơng việc đang chờ trên một CPU khác về thựcthi 9/19/201333 Chương 4: Định thời CPU
  31. • Nhiều lõi vi xử lý được đặttrêncùngmộtbộ xử lý => vi xử lý đa nhân • Nhanh hơn và tiêu tốnítnăng lượng hơn • Hỗ trợđaluồng trên mỗi nhân o Mộtluồng cĩ thểđượcthực thi trong khi luồng khác đang truy xuấtbộ nhớ. 9/19/201334 Chương 4: Định thời CPU
  32. 9/19/201335 Chương 4: Định thời CPU
  33. 1. Mơ hình xác định 2. Mơ hình hàng đợi 3. Mơ phỏng 4. Cài đặt
  34. • Cách đánh giá và chọngiảithuật thích hợp cho mộthệđiều hành? • Xác định các tiêu chí, đánh giá giảithuậtdựa trên các tiêu chí đĩ • Deterministic modeling –mơhìnhxácđịnh o Đánh giá dựatrênsự phân tích o Dựavàotảicơngviệc(workload)đượcxácđịnh trướcvàtính tốn hiệunăng củamỗigiảithuật. • Cho các tiếntrìnhđến vào cùng mộtthời điểm: 9/19/201337 Chương 4: Định thời CPU
  35. • V ớimỗigiảithuật tính thờigianchờ trung bình • Đơngiản, nhanh chĩng, nhưng yêu cầuphảicĩcácsố liệu đầu vào chính xác, và chỉđúng cho những dữ liệu đầuvàonhưđãcho o FCFS: 28ms o Non-preemptive SJF: 13ms o RR: 23ms 9/19/201338 Chương 4: Định thời CPU
  36. • Xác định sự phân phối các tiếntrìnhđến và chu kỳ CPU-I/O theo xác xuất, là điềucĩthể xác định được trong thưctế. o Thơng thường phân phốitheohàmmũ o Từ hai phân phốitrêntacĩthể tính trung bình thơng lượng, hiệu năng tậndụng CPU, thờigianchờ, • Hệ thống máy tính đượcmơtả như mộtmạng các server cĩ các hàng đợi riêng (CPU là mộtservervớihàngđợisẵn sàng). o Biếttốc độ đếnvàtốc độ phụcvụ (dựavàosự phân bổ chu kỳ CPU-I/O) => cĩ thể tính khả năng sử dụng, chiều dài hàng đợi trung bình, thờigianchờ trung bình. 9/19/201339 Chương 4: Định thời CPU
  37. • Luật Little – khi hệ thống trong trạng thái ổn định, số lượng các tiến trình rờikhỏihàngđợisẽ bằng vớisố lượng các tiến trình vào hàng đợi: n =  x W • Trong đĩ: o n: chiều dài hàng đợi trung bình o λ:tốc độ đến trung bình cho các tiếntrìnhmới(vd4tiến trình/giây) o W: thờigianchờ trung bình trong hàng đợi • VD: trung bình cĩ 7 tiếntrìnhđếnmỗi giây, và thơng thường cĩ 14 tiến trình trong hệ thống, thì thờigianchờ trung bình của mỗitiến trình là: 2s 9/19/201340 Chương 4: Định thời CPU
  38. • Mơ hình hàng đợicĩđộ chính xác giớihạn • Mơ phỏng cho kếtquả chính xác hơn: o Dùng phầnmềmmơphỏng hệ thống máy tính o Clock là mộtbiến o Khi thựcthimơphỏng, các thống kê hiệunăng củacácgiảithuật sẽđược ghi nhậnvàlàcơ sở cho vịêc so sánh các giảithuật. o Dữ liệu dùng để thựchiệnmơphỏng: • Bộ sinh số ngẫu nhiên theo xác xuất o Phân phối theo mơ hình tốn học hay theo kinh nghiệm • Các sự kiệndược ghi lại trong hệ thống thực 9/19/201341 Chương 4: Định thời CPU
  39. 9/19/201342 Chương 4: Định thời CPU
  40. • Kể cả mơ phỏng cũng cho kếtquả giớihạn • Cài đặtvàkiểm tra các giảithuật định thờitrênhệ thống thật sẽ cho độ chính xác cao nhất o Chi phí cao, rủi ro cao o Mơi trường đadạng • Hầuhết các bộđịnh thờicĩthểđượcsửa đổi để phù hợpvới từng hệ thống => kếtquả khơng chính xác trong các tình huống tổng quát khác. 9/19/201343 Chương 4: Định thời CPU