›
›

Cơ sở dữ liệu - Chương 4: Lập lịch biểu CPU CPU scheduling

pdf 44 trang vanle 2980
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chương 4: Lập lịch biểu CPU CPU scheduling", để 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:

  • pdfco_so_du_lieu_chuong_4_lap_lich_bieu_cpu_cpu_scheduling.pdf

Nội dung text: Cơ sở dữ liệu - Chương 4: Lập lịch biểu CPU CPU scheduling

  1. CHCHƯƠƯƠNGNG 4:4: LLẬẬPP LLỊỊCHCH BIBIỂỂUU CPUCPU CPUCPU SchedulingScheduling
  2. NNỘỘII DUNGDUNG „ Các khái niệmcơ sở „ Các tiêu chuẩnlậplịch biểu „ Các thuật toán lậplịch biểu „ Lậplịch biểu đa processors „ Lậplịch biểuthờigianthực (Real-Time Scheduling) „ Các ví dụ HĐH „ Đánh giá thuật toán Operating System Concepts – 7th Edition, Feb 2, 2005 5.2 Silberschatz, Galvin and Gagne ©2005
  3. CCÁÁCC KHKHÁÁII NINIỆỆMM CCƠƠ SSỞỞ „ Sử dụng CPU cực đạinhận đượcbởi đachương „ Chu kỳ CPU-I/O (CPU–I/O Burst Cycle) – sự thựchiện quá trình gồmchukỳ thựchiệnCPU vàchờ I/O „ Sự phân tán CPU burst Operating System Concepts – 7th Edition, Feb 2, 2005 5.3 Silberschatz, Galvin and Gagne ©2005
  4. DÃYDÃY LUÂNLUÂN PHIÊNPHIÊN CCÁÁCC CHUCHU KKỲỲ CPUCPU VVÀÀ CHUCHU KKỲỲ I/OI/O Operating System Concepts – 7th Edition, Feb 2, 2005 5.4 Silberschatz, Galvin and Gagne ©2005
  5. BIBIỂỂUU ĐĐỒỒ THTHỜỜII GIANGIAN CHUCHU KKỲỲ CPUCPU Operating System Concepts – 7th Edition, Feb 2, 2005 5.5 Silberschatz, Galvin and Gagne ©2005
  6. BBỘỘ ĐĐỊỊNHNH THTHỜỜII CPUCPU „ Chọn trong các quá trình sẵn sàng một quá trình và cấp CPU cho nó „ Quyếtdịnh lậplịch biểuCPU xảyrakhimột quá trình : 1. Chuyểntừ trạng thái running sang trạng thái waiting 2. Chuyểntừ trạng thái running sang trạng thái ready 3. Chuyểntừ trạng thái waiting sang trạng thái ready 4. Kết thúc „ Lậplịch biểu cho 1 và 4 là không trưng dụng (nonpreemptive) „ Lậplịch biểucònlạilàtrưng dụng (preemptive) Operating System Concepts – 7th Edition, Feb 2, 2005 5.6 Silberschatz, Galvin and Gagne ©2005
  7. BBỘỘ ĐĐIIỀỀUU VVẬẬNN „ Module điềuvậnchuyển điềukhiển CPU cho quá trình đượcchọn bởibộđịnh thờingắnhạn, bao gồm: z Chuyểnngữ cảnh z Chuyển sang phương thúc user z Nhảy đếnvị trí đúng trong chương trình người dùng để bắt đầu lạichương trình này „ Tiềm ẩn điềuvận (Dispatch latency) –thờigianbộđiềuvậnngưng một quá trình và khởi động một quá trình khác Operating System Concepts – 7th Edition, Feb 2, 2005 5.7 Silberschatz, Galvin and Gagne ©2005
  8. CCÁÁCC TIÊUTIÊU CHUCHUẨẨNN LLẬẬPP LLỊỊCHCH BIBIỂỂUU „ Sự sử dụng CPU: Làm cho CPU bậnrộnnhư có thể „ Năng lựctruyền qua (throughput): số quá trình hoàn tấtsự thựchiệncủa chúng trong một đơnvị thờigian „ Thời gian quay vòng (Turnaround time) – lượng thờigian thựchiệnmột quá trình „ Thờigianchờ (Waiting time) – lượng thờigianmột quá trình phảichờ trong hàng đợi ready „ Thờigianđáp ứng (Response time) – lượng thờigiantừ khi mộtyêucầu được đệ trình đếnkhiđáp ứng đầutiên đượcsinhra Operating System Concepts – 7th Edition, Feb 2, 2005 5.8 Silberschatz, Galvin and Gagne ©2005
  9. CCÁÁCC TIÊUTIÊU CHUCHUẨẨNN TTỐỐII ƯƯUU „ Max sự sử dụng CPU „ Max throughput „ Min turnaround time „ Min waiting time „ Min response time Operating System Concepts – 7th Edition, Feb 2, 2005 5.9 Silberschatz, Galvin and Gagne ©2005
  10. FirstFirst Come,Come, FirstFirst ServedServed (FCFS)(FCFS) Process Burst Time P1 24 P2 3 P3 3 „ Giả sử các quá trình đếntheothứ tự: P1 , P2 , P3 Biểu đồ Gantt cho lịch biểu: P1 P2 P3 0 24 27 30 „ Waiting time: đốivới P1 = 0; P2 = 24; P3 = 27 „ Waiting time trung bình: (0 + 24 + 27)/3 = 17 Operating System Concepts – 7th Edition, Feb 2, 2005 5.10 Silberschatz, Galvin and Gagne ©2005
  11. FCFSFCFS (Cont.)(Cont.) Giả sử các quá trình đếntheothứ tự: P2 , P3 , P1 „ Biểu đồ Gantt cho lịch biểu: P2 P3 P1 0 336 0 „ Waiting time đốivới P1 = 6;P2 = 0; P3 = 3 „ Average waiting time: (6 + 0 + 3)/3 = 3 „ Tốthơn nhiềuso vớitrường hợptrước „ Hiệu ứng đoàn xe: quá trình ngắn đi sau quá trình dài Operating System Concepts – 7th Edition, Feb 2, 2005 5.11 Silberschatz, Galvin and Gagne ©2005
  12. ShortestShortest JobJob FirstFirst (SJF)(SJF) „ Kếthợpvớimỗi quá trình độ dài chu kỳ CPU của nó. Sử dụng các độ dài này để lậplịch biểu quá trình vớithờigianngắnnhất „ Hai sơđồ: z Không trưng dụng: mỗikhiCPU đượcgánchomột quá trình, nó không bị trưng dụng đếntận khi hoàn tấtchukỳ CPU của nó z Trưng dụng: Nếumột quá trình mới đếncóchukỳ CPU ngắn hơnthờigiancònlạicủa quá trình đang thựchiện, trưng dụng CPU của quá trình đang thựchiện, cấp CPU cho quá trình mới đến. Sơđồnày đượcbiếtdướitên: Shortest-Remaining-Time-First (SRTF) „ SJF là tối ưuvớinghĩanóchothờigianchờ trung bình cựctiểu đối vớitập đã cho các quá trình Operating System Concepts – 7th Edition, Feb 2, 2005 5.12 Silberschatz, Galvin and Gagne ©2005
  13. VVÍÍ DDỤỤ SJFSJF KHÔNGKHÔNG TRTRƯƯNGNG DDỤỤNGNG Process Arrival Time Burst Time 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 317 8 12 6 „ Thờigianchờ trung bình = (0 + 6 + 3 + 7)/4 = 4 Operating System Concepts – 7th Edition, Feb 2, 2005 5.13 Silberschatz, Galvin and Gagne ©2005
  14. VVÍÍ DDỤỤ SJFSJF TRTRƯƯNGNG DDỤỤNGNG Process Arrival Time Burst Time 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ờ trung bình = (9 + 1 + 0 +2)/4 = 3 Operating System Concepts – 7th Edition, Feb 2, 2005 5.14 Silberschatz, Galvin and Gagne ©2005
  15. XXÁÁCC ĐĐỊỊNHNH ĐĐỘỘ DDÀÀII CHUCHU KKỲỲ CPUCPU KKẾẾ TITIẾẾPP „ Chỉ có thểướclượng độ dài „ Sử dụng độ dài cùa các chu kỳ CPU trước đó, ướclượng độ dài chu kỳ CPU kế tiếptheotrungbìnhmũ: -tn = độ dài chu kỳ CPU thứ n - τn = độ dài ướclượng chu kỳ CPU thứ n - α: 0 ≤α≤ 1 - độ dài ướclượng chu kỳ CPU thứ n+1 đượcxácđịnh: τ n+1 = α tn + ( 1−α )τ n . Operating System Concepts – 7th Edition, Feb 2, 2005 5.15 Silberschatz, Galvin and Gagne ©2005
  16. TIÊNTIÊN ĐĐOOÁÁNN ĐĐỘỘ DDÀÀII CHUCHU KKỲỲ CPUCPU KKẾẾ TITIẾẾPP Operating System Concepts – 7th Edition, Feb 2, 2005 5.16 Silberschatz, Galvin and Gagne ©2005
  17. VVÍÍ DDỤỤ TRUNGTRUNG BÌNHBÌNH MMŨŨ „ α =0 z τn+1 = τn z Lịch sử gần không được tính đến „ α =1 z τn+1 = tn z Chỉ chu kỳ CPU hiệntại được tính đến „ Triển khai công thức, ta được: τn+1 = α tn+(1 - α)α tn -1 + j +(1 - α ) α tn -j + n +1 +(1 - α ) τ0 Operating System Concepts – 7th Edition, Feb 2, 2005 5.17 Silberschatz, Galvin and Gagne ©2005
  18. LLẬẬPP LLỊỊCHCH BIBIỂỂUU ƯƯUU TIÊNTIÊN „ Mỗi quá trình đượcgánchomộtsốưutiên(mộtsố nguyên) „ CPU đượccấpchoquátrìnhvới độ ưutiêncaonhất (thông thường sốưutiênnhỏ = độ ưutiêncao) z Trưng dụng z Không trưng dụng „ SJF là lậplịch biểu ưu tiên trong đóquátrìnhcóchukỳ CPU tiên đoán ngắnnhấtcóđộ ưutiêncaonhất „ Vấn đề: Sự chết đói – quá trình có độ ưutiênthấpnhấtcóthể không bao giờđượcthựchiện „ Giải pháp: tăng độ ưu tiên cho quá trình theo thờigian Operating System Concepts – 7th Edition, Feb 2, 2005 5.18 Silberschatz, Galvin and Gagne ©2005
  19. RoundRound RobinRobin (RR)(RR) „ Mỗi quá trình nhận đượcmột đơnvị thờigian(nhỏ) - time quantum , thông thường 10-100 milliseconds. Sau khoảng thời gian này, quá trình bị lấylạiCPU vàđược đưavàocuốihàng đợisẵn sàng. „ Nếu có n quá trình trong hàng đợisẵn sàng, time quantum là q, khi đóthờigianchờ củamỗi quá trình không quá (n-1)q. „ Hiệunăng z q lớn ⇒ FIFO z q nhỏ ⇒ tổng phí chuyểnngữ cảnh cao ⇒ q phải đủ lớn Operating System Concepts – 7th Edition, Feb 2, 2005 5.19 Silberschatz, Galvin and Gagne ©2005
  20. VVÍÍ DDỤỤ RRRR vvớớii TimeTime QuantumQuantum == 2020 Process Burst Time 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, So vớiSJF, thời gian quay vòng trung bình của RR cao hơn, nhưng thờigianđáp ứng trung bình của RR tốthơn Operating System Concepts – 7th Edition, Feb 2, 2005 5.20 Silberschatz, Galvin and Gagne ©2005
  21. TIMETIME QUANTUMQUANTUM VVÀÀ THTHỜỜII GIANGIAN CHUYCHUYỂỂNN NGNGỮỮ CCẢẢNHNH Operating System Concepts – 7th Edition, Feb 2, 2005 5.21 Silberschatz, Galvin and Gagne ©2005
  22. THTHỜỜII GIANGIAN QUAYQUAY VÒNGVÒNG VVỚỚII TIMETIME QUANTUMQUANTUM Operating System Concepts – 7th Edition, Feb 2, 2005 5.22 Silberschatz, Galvin and Gagne ©2005
  23. HHÀÀNGNG ĐĐỢỢII ĐĐAA MMỨỨCC „ Hàng đợisẵn sàng đượcphânhoạch thành một các hàng đợi: foreground (interactive) background (batch) „ Mỗihàngđợicóthuật toán lậplịch biểuriêngcủanó z foreground – RR z background – FCFS „ Lậplịch biểu được làm giữa các hàng đợi z Lậplịch biểu ưutiêncốđịnh (phụcvụ tấtcả quá trình trong foreground sau đómới đến các quá trình trong background). Có thể gây nên chết đói. z Lát thời gian: mỗihàngđợinhậnmộtlượng thờigianCPU nhất định để lậplịch biểu cho các quá trình củanó(vídụ 80% thời gian cho hàng đợi foreground với RR, 20% cho background với FCFS) Operating System Concepts – 7th Edition, Feb 2, 2005 5.23 Silberschatz, Galvin and Gagne ©2005
  24. LLẬẬPP LLỊỊCHCH BIBIỂỂUU HHÀÀNGNG ĐĐỢỢII ĐĐAA MMỨỨCC Operating System Concepts – 7th Edition, Feb 2, 2005 5.24 Silberschatz, Galvin and Gagne ©2005
  25. HHÀÀNGNG ĐĐỢỢII PHPHẢẢNN HHỒỒII ĐĐAA MMỨỨCC „ Mỗi quá trình có thể di chuyểngiữa các hàng đợi „ Bộ lậplịch biểu hàng đợiphảnhồi đamức đượcxácđịnh bởicác tham số sau: z Số hàng đợi z Các thuật toán lậplịch biểuchomỗi hàng đợi z Phương pháp xác định khi nào nâng cấp quá trình z Phương pháp xác định khi nào hạ cấp quá trình z Phương pháp xác định hàng đợimột quá trình sẽ được đặtvào khi quá trình cầnsự phụcvụ Operating System Concepts – 7th Edition, Feb 2, 2005 5.25 Silberschatz, Galvin and Gagne ©2005
  26. VVÍÍ DDỤỤ HHÀÀNGNG ĐĐỢỢII PHPHẢẢNN HHỒỒII ĐĐAA MMỨỨCC „ Ba hàng đợi: z Q0 – RR với time quantum 8 milliseconds z Q1 – RR với time quantum 16 milliseconds z Q2 –FCFS „ Lậplịch biểu z Một công việcmới đượcsắp vào hàng đợi Q0, ởđónóđược lậplịch biểuRR với time quantum = 8 miliseconds, nếuquá trình chua kết thúc sau 8 miliseconds, nó đượcchuyển sang hàng đợi Q1 z Trong Q1 công việc đượcphụcvụ theo RR với time quantum 16 miliseconds. Nếunóvẫn chua hoàn tất, nó sẽ đượcchuyển sang Q2 z Trong Q2 quá trình đượclậplịch biểuFCFS Operating System Concepts – 7th Edition, Feb 2, 2005 5.26 Silberschatz, Galvin and Gagne ©2005
  27. CCÁÁCC HHÀÀNGNG ĐĐỢỢII PHPHẢẢNN HHỒỒII ĐĐAA MMỨỨCC Operating System Concepts – 7th Edition, Feb 2, 2005 5.27 Silberschatz, Galvin and Gagne ©2005
  28. LLẬẬPP LLỊỊCHCH BIBIỂỂUU ĐĐAA ProcessorsProcessors „ Phứctạphơn „ Các processors thuầnnhất „ Chia sẻ nạp „ Đaxử lý phi đốixứng –chỉ một processor truy xuấtcác cấutrúcdữ liệuhệ thống làm giảmnhẹ sự cầnthiếtchia sẻ dữ liệu Operating System Concepts – 7th Edition, Feb 2, 2005 5.28 Silberschatz, Galvin and Gagne ©2005
  29. LLẬẬPP LLỊỊCHCH BIBIỂỂUU THTHỜỜII GIANGIAN THTHỰỰCC „ Các hệ thờigianthựccứng (Hard real-time systems): đòi hỏi hoàn tấtmộtnhiệmvụ khẩncấp trong một lượng thờigianxácđịnh „ Tính toán thờigianthựcmềm (Soft real-time computing): – Đòi hỏi các quá trình khẩncấpnhận được ưutiêntrêncácquátrìnhkhác Operating System Concepts – 7th Edition, Feb 2, 2005 5.29 Silberschatz, Galvin and Gagne ©2005
  30. CCÁÁCC VVÍÍ DDỤỤ HHĐĐHH „ Solaris scheduling „ Windows XP scheduling „ Linux scheduling Operating System Concepts – 7th Edition, Feb 2, 2005 5.30 Silberschatz, Galvin and Gagne ©2005
  31. LLẬẬPP LLỊỊCHCH BIBIỂỂUU SolarisSolaris 22 Operating System Concepts – 7th Edition, Feb 2, 2005 5.31 Silberschatz, Galvin and Gagne ©2005
  32. BBẢẢNGNG ĐĐIIỀỀUU VVẬẬNN SolarisSolaris Operating System Concepts – 7th Edition, Feb 2, 2005 5.32 Silberschatz, Galvin and Gagne ©2005
  33. CCÁÁCC ƯƯUU TIÊNTIÊN WindowsWindows XPXP Operating System Concepts – 7th Edition, Feb 2, 2005 5.33 Silberschatz, Galvin and Gagne ©2005
  34. LLẬẬPP LLỊỊCHCH BIBIỂỂUU LinuxLinux „ Hai thuật toán: time-sharing và real-time „ Time-sharing z Ừutiêndựatrêntíndụng: quá trình vớitíndụng cao nhất được chọnkế tiếp z Tín dụng bị trừ khi ngắt đồng hồ xảyra z Khi tín dụng = 0, quá trình khác đượcchọn z Khi tấtcả các quá trình có tín dụng = 0, lậplại tín dụng  Dựa trên các nhân tố bao gồm độ ưutiênvàlịch sử „ Real-time z Real-time mềm z Posix.1b compliant – hai lớp  FCFS và RR  Quá trình độ ưutiêncaonhất luôn chạy đầutiên Operating System Concepts – 7th Edition, Feb 2, 2005 5.34 Silberschatz, Galvin and Gagne ©2005
  35. QUAN HỆ GIỮA ĐỘ ƯU TIÊN VÀ ĐỘ DÀI LÁT THỜI GIAN Operating System Concepts – 7th Edition, Feb 2, 2005 5.35 Silberschatz, Galvin and Gagne ©2005
  36. DANHDANH SSÁÁCHCH CCÁÁCC NHINHIỆỆMM VVỤỤ ĐƯĐƯỢỢCC CHCHỈỈ SSỐỐ TTƯƠƯƠNGNG ỨỨNGNG VVỚỚII ĐĐỘỘ ƯƯUU TIÊNTIÊN Operating System Concepts – 7th Edition, Feb 2, 2005 5.36 Silberschatz, Galvin and Gagne ©2005
  37. ĐĐÁÁNHNH GIGIÁÁ THUTHUẬẬTT TOTOÁÁNN „ Mô hình quyết định: lấymộtkhốicôngviệc định trước đặcbiệtvàxác định hiệunăng củamỗithuật toán đốivớikhốicôngviệc „ Mô hình xếp hàng „ Thựcthi Operating System Concepts – 7th Edition, Feb 2, 2005 5.37 Silberschatz, Galvin and Gagne ©2005
  38. 5.155.15 Operating System Concepts – 7th Edition, Feb 2, 2005 5.38 Silberschatz, Galvin and Gagne ©2005
  39. EndEnd ofof ChapterChapter 55
  40. 5.085.08 Operating System Concepts – 7th Edition, Feb 2, 2005 5.40 Silberschatz, Galvin and Gagne ©2005
  41. InIn 5.75.7 Operating System Concepts – 7th Edition, Feb 2, 2005 5.41 Silberschatz, Galvin and Gagne ©2005
  42. InIn 5.85.8 Operating System Concepts – 7th Edition, Feb 2, 2005 5.42 Silberschatz, Galvin and Gagne ©2005
  43. InIn 5.95.9 Operating System Concepts – 7th Edition, Feb 2, 2005 5.43 Silberschatz, Galvin and Gagne ©2005
  44. DispatchDispatch LatencyLatency Operating System Concepts – 7th Edition, Feb 2, 2005 5.44 Silberschatz, Galvin and Gagne ©2005