Bài giảng Hệ điều hành - Chương 4, Phần 2: Định thời CPU - Trần Thị Như Nguyệt

Chương 4: Định thời CPU - 2 
 Mục tiêu 
 Biết được các khái niệm cơ bản về định thời 
 Biết được các tiêu chuẩn định thời CPU 
 Hiểu được các giải thuật định thời 
 Vận dụng các giải thuật định thời để làm bài tập và 
 mô phỏng 
 2 Định thời CPU 
 Ôn tập chương 4 - 1 
 Các khái niệm cơ bản về định thời 
 Các bộ định thời 
 Các tiêu chuẩn định thời CPU 
 Các giải thuật định thời 
  First-Come, First-Served (FCFS) 
  Shortest Job First (SJF) 
  Shortest Remaining Time First (SRTF) 
  Priority Scheduling 
 3 Định thời CPU 
 Bài tập chương 4 - 1 
 Sử dụng các giải thuật FCFS, SJF, SRTF, 
 Priority để tính các giá trị thời gian đợi, thời gian 
 đáp ứng và thời gian hoàn thành trung bình 
 4 Định thời CPU 
 Nội dung 
 Các khái niệm cơ bản về định thời 
 Các bộ định thời 
 Các tiêu chuẩn định thời CPU 
 Các giải thuật định thời 
  First-Come, First-Served (FCFS) 
  Shortest Job First (SJF) 
  Shortest Remaining Time First (SRTF) 
  Priority Scheduling 
  Round-Robin (RR) 
  Highest Response Ratio Next (HRRN) 
  Multilevel Queue 
  Multilevel Feedback Queue 
 5 Định thời CPU 
 Nội dung 
 Các khái niệm cơ bản về định thời 
 Các bộ định thời 
 Các tiêu chuẩn định thời CPU 
 Các giải thuật định thời 
  First-Come, First-Served (FCFS) 
  Shortest Job First (SJF) 
  Shortest Remaining Time First (SRTF) 
  Priority Scheduling 
  Round-Robin (RR) 
  Highest Response Ratio Next (HRRN) 
  Multilevel Queue 
  Multilevel Feedback Queue 
 6 Định thời CPU 
 Round Robin (RR) 
 Mỗi process nhận được một đơn vị nhỏ thời gian CPU 
 (time slice, quantum time), thông thường từ 10-100 msec 
 để thực thi 
 Sau khoảng thời gian đó, process bị đoạt quyền và trở về 
 cuối hàng đợi ready 
 Nếu có n process trong hàng đợi ready và quantum time = 
 q thì không có process nào phải chờ đợi quá (n -1)q đơn vị 
 thời gian 
 7 Định thời CPU 
 Round Robin (RR) (tt) 
 Hiệu suất: 
  Nếu q lớn: RR FCFS 
  Nếu q nhỏ: q không được quá nhỏ bởi vì phải tốn 
 chi phí chuyển ngữ cảnh 
  Thời gian chờ đợi trung bình của giải thuật RR 
 thường khá lớn nhưng thời gian đáp ứng nhỏ 
 8 Định thời CPU 
 Round Robin (RR) (tt) 
 Ví dụ: Quantum time = 20 
 Process Burst Time
 P1 53
 P2 17
 P3 68
 P4 24
 Gantt Chart for Schedule 
 P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 
 0 20 37 57 77 97 117 121 134 154 162 
 turnaround time trung bình lớn hơn SJF, nhưng đáp ứng tốt hơn 
 9 Định thời CPU 
 Round Robin (RR) (tt) 
 Quantum time = 1: 
  Thời gian turnaround trung bình cao hơn so với SJF nhưng có thời 
 gian đáp ứng trung bình tốt hơn 
  Ưu tiên CPU-bound process 
  I/O-bound 
  CPU-bound 
 10 Định thời CPU 
 Round Robin (RR) (tt) 
 Quantum time và context switch: 
 context 
 quantum 
 Process time = 10 switch 
 12 0 
 10 
 6 1 
 6 10 
 1 9 
 1 2 3 4 5 6 7 8 9 10 
 11 Định thời CPU 
 Round Robin (RR) (tt) 
 Thời gian hoàn thành trung bình (average turnaround time) 
 không chắc sẽ được cải thiện khi quantum lớn 
 12 Định thời CPU 
 Quantum time cho Round Robin 
 Performance tùy thuộc vào kích thước của quantum 
 time (còn gọi là time slice), và hàm phụ thuộc này 
 không đơn giản 
 Time slice ngắn thì đáp ứng nhanh 
  Vấn đề: có nhiều chuyển ngữ cảnh. Phí tổn sẽ cao. 
 Time slice dài hơn thì throughput tốt hơn (do giảm phí 
 tổn - OS overhead) nhưng thời gian đáp ứng lớn 
  Nếu time slice quá lớn, RR trở thành FCFS 
 13 Định thời CPU 
 Quantum time cho Round Robin 
 Quantum time và thời gian cho process switch: 
  Nếu quantum time = 20 ms và thời gian cho process 
 switch = 5 ms, như vậy phí tổn OS overhead chiếm 5/25 
 = 20% 
  Nếu quantum = 500 ms, thì phí tổn chỉ còn 1% 
  Nhưng nếu có nhiều người sử dụng trên hệ thống và thuộc loại 
 “interactive” thì sẽ thấy đáp ứng rất chậm 
  Tùy thuộc vào tập công việc mà lựa chọn quantum time 
  Time slice nên lớn trong tương quan so sánh với thời 
 gian cho process switch 
  Ví dụ với 4.3 BSD UNIX, time slice là 1 giây 
 14 Định thời CPU 
 Quantum time cho Round Robin (tt) 
 RR sử dụng một giả thiết ngầm là tất cả các process 
 đều có tầm quan trọng ngang nhau 
  Không thể sử dụng RR nếu muốn các process khác nhau 
 có độ ưu tiên khác nhau 
 15 Định thời CPU 
 Nhược điểm của Round Robin 
 Các process dạng CPU-bound vẫn còn được 
 “ưu tiên” 
  Ví dụ: 
 Một I/O-bound process sử dụng CPU trong 
 thời gian ngắn hơn quantum time và bị 
 blocked để đợi I/O. 
 Một CPU-bound process chạy hết time slice 
 và lại quay trở về hàng đợi ready queue (ở 
 phía trước các process đã bị blocked) 
 16 Định thời CPU 
 Nội dung 
 Các khái niệm cơ bản về định thời 
 Các bộ định thời 
 Các tiêu chuẩn định thời CPU 
 Các giải thuật định thời 
  First-Come, First-Served (FCFS) 
  Shortest Job First (SJF) 
  Shortest Remaining Time First (SRTF) 
  Priority Scheduling 
  Round-Robin (RR) 
  Highest Response Ratio Next (HRRN) 
  Multilevel Queue 
  Multilevel Feedback Queue 
 17 Định thời CPU 
 Highest Response Ratio Next 
 Chọn process kế tiếp có giá trị RR (Response 
 ratio) lớn nhất 
 Các process ngắn được ưu tiên hơn (vì 
 service time nhỏ) 
 waiting time burst time
 RR 
 burst time
 18 Định thời CPU 
 Highest Response Ratio Next 
 Tại mốc thời gian thứ 9, sau khi P2 thực 
Ví dụ: hiện xong, hàng đợi lúc này có P3, P4 và 
 P5. RR của từng process được tính như 
 sau: 
 RR(P3) = (5+5)/5 = 2 
 RR(P4)= (3+4)/4 = 1.75 
 RR(P5)= (1+2)/2 = 1.5 
 P3 được chọn đưa vào thực thi. 
 Tại mốc thời gian thứ 14, sau khi P3 thực 
 hiện xong, P4 và P5 được tính RR lại như 
 sau: 
 RR(P4) = (8+4)/4 = 3 
 RR(P5) = (6+2)/2 = 4 
 P5 được chọn đưa vào thực thi. Sau đó 
 tới P4. 
 P1 P2 P3 P5 P4 
 2 9 14 16 20 
 19 Định thời CPU 
 Nội dung 
 Các khái niệm cơ bản về định thời 
 Các bộ định thời 
 Các tiêu chuẩn định thời CPU 
 Các giải thuật định thời 
  First-Come, First-Served (FCFS) 
  Shortest Job First (SJF) 
  Shortest Remaining Time First (SRTF) 
  Priority Scheduling 
  Round-Robin (RR) 
  Highest Response Ratio Next (HRRN) 
  Multilevel Queue 
  Multilevel Feedback Queue 
 20 Định thời CPU 
 Multilevel Queue Scheduling 
 Hàng đợi ready được chia thành nhiều hàng 
 đợi riêng biệt theo một số tiêu chuẩn như 
  Đặc điểm và yêu cầu định thời của process 
  Foreground (interactive) và background (batch) 
 process, 
 Process được gán cố định vào một hàng đợi, 
 mỗi hàng đợi sử dụng giải thuật định thời 
 riêng 
 21 Định thời CPU 
 Multilevel Queue Scheduling (tt) 
 Hệ điều hành cần phải định thời cho các hàng 
 đợi. 
  Fixed priority scheduling: phục vụ từ hàng đợi có độ 
 ưu tiên cao đến thâp. Vấn đề: có thể có starvation. 
  Time slice: mỗi hàng đợi được nhận một khoảng thời 
 gian chiếm CPU và phân phối cho các process trong 
 hàng đợi khoảng thời gian đó. Ví dụ: 80% cho hàng đợi 
 foreground định thời bằng RR và 20% cho hàng đợi 
 background định thời bằng giải thuật FCFS 
 22 Định thời CPU 
 Multilevel Queue Scheduling (tt) 
 Ví dụ phân nhóm các quá trình 
 Độ ưu tiên cao nhất 
 System Processes 
 Interactive Processes 
 Batch Processes 
 Student Processes 
 Độ ưu tiên thấp nhất 
 23 Định thời CPU 
 Nội dung 
 Các khái niệm cơ bản về định thời 
 Các bộ định thời 
 Các tiêu chuẩn định thời CPU 
 Các giải thuật định thời 
  First-Come, First-Served (FCFS) 
  Shortest Job First (SJF) 
  Shortest Remaining Time First (SRTF) 
  Priority Scheduling 
  Round-Robin (RR) 
  Highest Response Ratio Next (HRRN) 
  Multilevel Queue 
  Multilevel Feedback Queue 
 24 Định thời CPU 
 Multilevel Feedback Queue 
 Vấn đề của multilevel queue: process không thể 
 chuyển từ hàng đợi này sang hàng đợi khác 
 Khắc phục bằng cách dùng Multilevel Feedback Queue: 
 cho phép process di chuyển một cách thích hợp giữa 
 các hàng đợi khác nhau 
Với Multilevel Feedback Queue, một process đã chờ quá lâu 
ở một hàng đợi có độ ưu tiên thấp có thể được chuyển đến 
hàng đợi có độ ưu tiên cao hơn (cơ chế niên hạn, aging) 
 25 Định thời CPU 
 Multilevel Feedback Queue (tt) 
 Định thời dùng multilevel feedback queue đòi hỏi phải 
 giải quyết các vấn đề sau 
  Số lượng hàng đợi bao nhiêu là thích hợp? 
  Dùng giải thuật định thời nào ở mỗi hàng đợi? 
  Làm sao để xác định thời điểm cần chuyển một 
 process đến hàng đợi cao hơn hoặc thấp hơn? 
  Khi process yêu cầu được xử lý thì đưa vào hàng 
 đợi nào là hợp lý nhất? 
 26 Định thời CPU 
 Multilevel Feedback Queue (tt) 
 Ví dụ: Có 3 hàng đợi 
  Q0 , dùng RR với quantum 8 ms 
  Q1 , dùng RR với quantum 16 ms 
  Q2 , dùng FCFS 
 27 Định thời CPU 
 So sánh các giải thuật 
 Giải thuật định thời nào là tốt nhất? 
 Câu trả lời phụ thuộc các yếu tố sau: 
  Tần xuất tải việc (System workload) 
  Sự hỗ trợ của phần cứng đối với dispatcher 
  Sự tương quan về trọng số của các tiêu chuẩn định thời 
 như response time, hiệu suất CPU, throughput, 
  Phương pháp định lượng so sánh 
 Phụ thuộc theo tiêu chí đánh giá 
 28 Định thời CPU 
 Đọc thêm 
 Policy và Mechanism 
 Định thời trên hệ thống multiprocessor 
 Đánh giá giải thuật định thời CPU 
 Định thời trong một số hệ điều hành thông dụng 
 (Đọc trong tài liệu tham khảo sách gốc tiếng Anh) 
 29 Định thời CPU 
 Tổng kết 
 Các khái niệm cơ bản về định thời 
 Các bộ định thời 
 Các tiêu chuẩn định thời CPU 
 Hai yếu tố của giải thuật định thời 
 30 Định thời CPU 
 Tổng kết (tt) 
 Các giải thuật định thời 
  First-Come, First-Served (FCFS) 
  Shortest Job First (SJF) 
  Shortest Remaining Time First (SRTF) 
  Round-Robin (RR) 
  Priority Scheduling 
  Highest Response Ratio Next (HRRN) 
  Multilevel Queue 
  Multilevel Feedback Queue 
 31 Định thời CPU