CHƯƠNG 4: LẬP LỊCH BIỂU CPU CPU Scheduling

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.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
Nội dung trích xuất từ tài liệu:
CHƯƠNG 4: LẬP LỊCH BIỂU CPU CPU SchedulingCHƯƠNG 4: LẬP LỊCH BIỂU CPU CPU Scheduling 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ánOperating System Concepts – 7th Edition, Feb 2, 2005 5.2 Silberschatz, Galvin and Gagne ©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 burstOperating System Concepts – 7th Edition, Feb 2, 2005 5.3 Silberschatz, Galvin and Gagne ©2005 DÃY LUÂN PHIÊN CÁC CHU KỲ CPU VÀ CHU KỲ I/OOperating System Concepts – 7th Edition, Feb 2, 2005 5.4 Silberschatz, Galvin and Gagne ©2005 BIỂU ĐỒ THỜI GIAN CHU KỲ CPUOperating System Concepts – 7th Edition, Feb 2, 2005 5.5 Silberschatz, Galvin and Gagne ©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)Operating System Concepts – 7th Edition, Feb 2, 2005 5.6 Silberschatz, Galvin and Gagne ©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: Chuyển ngữ cảnh Chuyển sang phương thúc user 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ácOperating System Concepts – 7th Edition, Feb 2, 2005 5.7 Silberschatz, Galvin and Gagne ©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 raOperating System Concepts – 7th Edition, Feb 2, 2005 5.8 Silberschatz, Galvin and Gagne ©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 timeOperating System Concepts – 7th Edition, Feb 2, 2005 5.9 Silberschatz, Galvin and Gagne ©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: P1 P2 P3 0 24 27 30 Waiting time: đối với P1 = 0; P2 = 24; P3 = 27 Waiting time trung bình: (0 + 24 + 27)/3 = 17Operating System Concepts – 7th Edition, Feb 2, 2005 5.10 Silberschatz, Galvin and Gagne ©2005 FCFS (Cont.) ...