Bài giảng Lập lịch biểu cpu cpu scheduling

CHƯƠNG 4: LẬP LỊCH BIỂU CPU CPU Scheduling 5.2 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 NỘI DUNG „ Các khái niệm cơ sở „ Các tiêu chuẩn lập lịch biểu „ Các thuật toán lập lịch biểu „ Lập lịch biểu đa processors „ Lập lịch biểu thời gian thực (Real-Time Scheduling) „ Các ví dụ HĐH „ Đánh giá thuật toán 5.3 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 CÁC KHÁI NIỆM CƠ SỞ „ Sử dụng CPU cực đại nhận được bởi đa chương „ Chu kỳ CPU-I/O (CPU–I/O Burst Cycle) – sự thực hiện quá trình gồm chu kỳ thực hiện CPU và chờ I/O „ Sự phân tán CPU burst 5.4 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 DÃY LUÂN PHIÊN CÁC CHU KỲ CPU VÀ CHU KỲ I/O 5.5 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 BIỂU ĐỒ THỜI GIAN CHU KỲ CPU 5.6 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 BỘ ĐỊNH THỜI CPU „ Chọn trong các quá trình sẵn sàng một quá trình và cấp CPU cho nó „ Quyết dịnh lập lịch biểu CPU xảy ra khi một quá trình : 1. Chuyển từ trạng thái running sang trạng thái waiting 2. Chuyển từ trạng thái running sang trạng thái ready 3. Chuyển từ trạng thái waiting sang trạng thái ready 4. Kết thúc „ Lập lịch biểu cho 1 và 4 là không trưng dụng (nonpreemptive) „ Lập lịch biểu còn lại là trưng dụng (preemptive) 5.7 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 BỘ ĐIỀU VẬN „ Module điều vận chuyển điều khiển CPU cho quá trình được chọn bởi bộ định thời ngắn hạn, bao gồm: z Chuyển ngữ cảnh z Chuyển sang phương thúc user z Nhảy đến vị trí đúng trong chương trình người dùng để bắt đầu lại chương trình này „ Tiềm ẩn điều vận (Dispatch latency) – thời gian bộ điều vận ngưng một quá trình và khởi động một quá trình khác 5.8 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 CÁC TIÊU CHUẨN LẬP LỊCH BIỂU „ Sự sử dụng CPU: Làm cho CPU bận rộn như có thể „ Năng lực truyền qua (throughput): số quá trình hoàn tất sự thực hiện của chúng trong một đơn vị thời gian „ Thời gian quay vòng (Turnaround time) – lượng thời gian thực hiện một quá trình „ Thời gian chờ (Waiting time) – lượng thời gian một quá trình phải chờ trong hàng đợi ready „ Thời gian đáp ứng (Response time) – lượng thời gian từ khi một yêu cầu được đệ trình đến khi đáp ứng đầu tiên được sinh ra 5.9 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 CÁC TIÊU CHUẨN TỐI ƯU „ Max sự sử dụng CPU „ Max throughput „ Min turnaround time „ Min waiting time „ Min response time 5.10 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 First-Come, First-Served (FCFS) Process Burst Time P1 24 P2 3 P3 3 „ Giả sử các quá trình đến theo thứ tự: P1 , P2 , P3 Biểu đồ Gantt cho lịch biểu: „ Waiting time: đối với P1 = 0; P2 = 24; P3 = 27 „ Waiting time trung bình: (0 + 24 + 27)/3 = 17 P1 P2 P3 24 27 300 5.11 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 FCFS (Cont.) Giả sử các quá trình đến theo thứ tự: P2 , P3 , P1 „ Biểu đồ Gantt cho lịch biểu: „ Waiting time đối với P1 = 6; P2 = 0; P3 = 3 „ Average waiting time: (6 + 0 + 3)/3 = 3 „ Tốt hơn nhiều so với trường hợp trước „ Hiệu ứng đoàn xe: quá trình ngắn đi sau quá trình dài P1P3P2 63 300 5.12 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 Shortest-Job-First (SJF) „ Kết hợp với mỗi quá trình độ dài chu kỳ CPU của nó. Sử dụng các độ dài này để lập lịch biểu quá trình với thời gian ngắn nhất „ Hai sơ đồ: z Không trưng dụng: mỗi khi CPU được gán cho một quá trình, nó không bị trưng dụng đến tận khi hoàn tất chu kỳ CPU của nó z Trưng dụng: Nếu một quá trình mới đến có chu kỳ CPU ngắn hơn thời gian còn lại của quá trình đang thực hiện, trưng dụng CPU của quá trình đang thực hiện, cấp CPU cho quá trình mới đến. Sơ đồ này được biết dưới tên: Shortest-Remaining-Time-First (SRTF) „ SJF là tối ưu với nghĩa nó cho thời gian chờ trung bình cực tiểu đối với tập đã cho các quá trình 5.13 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 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 „ Thời gian chờ trung bình = (0 + 6 + 3 + 7)/4 = 4 VÍ DỤ SJF KHÔNG TRƯNG DỤNG P1 P3 P2 73 160 P4 8 12 5.14 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 VÍ DỤ SJF TRƯNG DỤNG 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 „ Thời gian chờ trung bình = (9 + 1 + 0 +2)/4 = 3 P1 P3P2 42 110 P4 5 7 P2 P1 16 5.15 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 XÁC ĐỊNH ĐỘ DÀI CHU KỲ CPU KẾ TIẾP „ Chỉ có thể ước lượng độ dài „ Sử dụng độ dài cùa các chu kỳ CPU trước đó, ước lượng độ dài chu kỳ CPU kế tiếp theo trung bình mũ: - tn = độ dài chu kỳ CPU thứ n - τn = độ dài ước lượng chu kỳ CPU thứ n - α: 0 ≤ α ≤ 1 - độ dài ước lượng chu kỳ CPU thứ n+1 được xác định: ( ) .1 1 nnn t ταατ −+=+ 5.16 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 TIÊN ĐOÁN ĐỘ DÀI CHU KỲ CPU KẾ TIẾP 5.17 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 VÍ DỤ TRUNG BÌNH MŨ „ α =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ện tại được tính đến „ Triển khai công thức, ta được: τn+1 = α tn+(1 - α)α tn -1 + … +(1 - α )jα tn -j + … +(1 - α )n +1 τ0 5.18 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 LẬP LỊCH BIỂU ƯU TIÊN „ Mỗi quá trình được gán cho một số ưu tiên (một số nguyên) „ CPU được cấp cho quá trình với độ ưu tiên cao nhất (thông thường số ưu tiên nhỏ = độ ưu tiên cao) z Trưng dụng z Không trưng dụng „ SJF là lập lịch biểu ưu tiên trong đó quá trình có chu kỳ CPU tiên đoán ngắn nhất có độ ưu tiên cao nhất „ Vấn đề: Sự chết đói – quá trình có độ ưu tiên thấp nhất có thể không bao giờ được thực hiện „ Giải pháp: tăng độ ưu tiên cho quá trình theo thời gian 5.19 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 Round Robin (RR) „ Mỗi quá trình nhận được một đơn vị thời gian (nhỏ) - time quantum , thông thường 10-100 milliseconds. Sau khoảng thời gian này, quá trình bị lấy lại CPU và được đưa vào cuối hàng đợi sẵn sàng. „ Nếu có n quá trình trong hàng đợi sẵn sàng, time quantum là q, khi đó thời gian chờ của mỗi quá trình không quá (n-1)q. „ Hiệu năng z q lớn⇒ FIFO z q nhỏ⇒ tổng phí chuyển ngữ cảnh cao⇒ q phải đủ lớn 5.20 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 VÍ DỤ RR với Time Quantum = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 „ Biểu đồ Gantt: „ Thông thường, So với SJF, thời gian quay vòng trung bình của RR cao hơn, nhưng thời gian đáp ứng trung bình của RR tốt hơn P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 5.21 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 TIME QUANTUM VÀ THỜI GIAN CHUYỂN NGỮ CẢNH 5.22 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 THỜI GIAN QUAY VÒNG VỚI TIME QUANTUM 5.23 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 HÀNG ĐỢI ĐA MỨC „ Hàng đợi sẵn sàng được phân hoạch thành một các hàng đợi: foreground (interactive) background (batch) „ Mỗi hàng đợi có thuật toán lập lịch biểu riêng của nó z foreground – RR z background – FCFS „ Lập lịch biểu được làm giữa các hàng đợi z Lập lịch biểu ưu tiên cố định (phục vụ tất cả 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ỗi hàng đợi nhận một lượng thời gian CPU nhất định để lập lịch biểu cho các quá trình của nó (ví dụ 80% thời gian cho hàng đợi foreground với RR, 20% cho background với FCFS) 5.24 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 LẬP LỊCH BIỂU HÀNG ĐỢI ĐA MỨC 5.25 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 HÀNG ĐỢI PHẢN HỒI ĐA MỨC „ Mỗi quá trình có thể di chuyển giữa các hàng đợi „ Bộ lập lịch biểu hàng đợi phản hồi đa mức được xác định bởi các tham số sau: z Số hàng đợi z Các thuật toán lập lịch biểu cho mỗ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 đợi một quá trình sẽ được đặt vào khi quá trình cần sự phục vụ 5.26 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 VÍ DỤ HÀNG ĐỢI PHẢN HỒI ĐA MỨC „ 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ập lịch biểu z Một công việc mới được sắp vào hàng đợi Q0, ở đó nó được lập lịch biểu RR với time quantum = 8 miliseconds, nếu quá trình chua kết thúc sau 8 miliseconds, nó được chuyển sang hàng đợi Q1 z Trong Q1 công việc được phục vụ theo RR với time quantum 16 miliseconds. Nếu nó vẫn chua hoàn tất, nó sẽ được chuyển sang Q2 z Trong Q2 quá trình được lập lịch biểu FCFS 5.27 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 CÁC HÀNG ĐỢI PHẢN HỒI ĐA MỨC 5.28 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 LẬP LỊCH BIỂU ĐA Processors „ Phức tạp hơn „ Các processors thuần nhất „ Chia sẻ nạp „ Đa xử lý phi đối xứng – chỉ một processor truy xuất các cấu trúc dữ liệu hệ thống làm giảm nhẹ sự cần thiết chia sẻ dữ liệu 5.29 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 LẬP LỊCH BIỂU THỜI GIAN THỰC „ Các hệ thời gian thực cứng (Hard real-time systems): đòi hỏi hoàn tất một nhiệm vụ khẩn cấp trong một lượng thời gian xác định „ Tính toán thời gian thực mềm (Soft real-time computing): – Đòi hỏi các quá trình khẩn cấp nhận được ưu tiên trên các quá trình khác 5.30 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 CÁC VÍ DỤ HĐH „ Solaris scheduling „ Windows XP scheduling „ Linux scheduling 5.31 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 LẬP LỊCH BIỂU Solaris 2 5.32 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 BẢNG ĐIỀU VẬN Solaris 5.33 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 CÁC ƯU TIÊN Windows XP 5.34 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 LẬP LỊCH BIỂU Linux „ Hai thuật toán: time-sharing và real-time „ Time-sharing z Ừu tiên dựa trên tín dụng: quá trình với tín dụng cao nhất được chọn kế tiếp z Tín dụng bị trừ khi ngắt đồng hồ xảy ra z Khi tín dụng = 0, quá trình khác được chọn z Khi tất cả các quá trình có tín dụng = 0, lập lại tín dụng  Dựa trên các nhân tố bao gồm độ ưu tiên và lịch sử „ Real-time z Real-time mềm z Posix.1b compliant – hai lớp  FCFS và RR Quá trình độ ưu tiên cao nhất luôn chạy đầu tiên 5.35 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 QUAN HỆ GIỮA ĐỘ ƯU TIÊN VÀ ĐỘ DÀI LÁT THỜI GIAN 5.36 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 DANH SÁCH CÁC NHIỆM VỤ ĐƯỢC CHỈ SỐ TƯƠNG ỨNG VỚI ĐỘ ƯU TIÊN 5.37 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 ĐÁNH GIÁ THUẬT TOÁN „ Mô hình quyết định: lấy một khối công việc định trước đặc biệt và xác định hiệu năng của mỗi thuật toán đối với khối công việc „ Mô hình xếp hàng „ Thực thi 5.38 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 5.15 End of Chapter 5 5.40 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 5.08 5.41 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 In-5.7 5.42 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 In-5.8 5.43 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 In-5.9 5.44 Silberschatz, Galvin and Gagne ©2005Operating System Concepts – 7th Edition, Feb 2, 2005 Dispatch Latency