Bài Giảng Hệ Điều Hành-Chương 4 : LẬP LỊCH BIỂU CPU CPU

Chia sẻ: Nguyen Van Nghia | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

175
lượt xem 37
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài Giảng Hệ Điều Hành-Chương 4 : LẬP LỊCH BIỂU CPU CPU

CHƯƠNG 4: LẬP LỊCH BIỂU CPU 4: 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án Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.2
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 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.3
DÃY LUÂN PHIÊN CÁC CHU KỲ CPU VÀ CHU KỲ I/O Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.4
BIỂU ĐỒ THỜI GIAN CHU KỲ CPU Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.5
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) Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.6
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ác Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.7
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 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.8
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 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.9
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 = 17 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.10
FCFS (Cont.) Giả sử các quá trình đến theo thứ tự: P2 , P3 , P1 Biểu đồ Gantt cho lịch biểu: P2 P3 P1 0 3 6 30 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 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.11
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ơ đồ: 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ó 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 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.12
VÍ DỤ SJF KHÔNG TRƯNG DỤNG SJF 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 3 7 8 12 16 Thời gian chờ trung bình = (0 + 6 + 3 + 7)/4 = 4 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.13
VÍ DỤ SJF TRƯNG DỤNG SJF 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 11 16 0 2 4 5 7 Thời gian chờ trung bình = (9 + 1 + 0 +2)/4 = 3 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.14
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: τ n +1 = α tn + (1 − α )τ n . Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.15
TIÊN ĐOÁN ĐỘ DÀI CHU KỲ CPU KẾ TIẾP Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.16
VÍ DỤ TRUNG BÌNH MŨ α =0 τn+1 = τn Lịch sử gần không được tính đến α =1 τn+1 = tn 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 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.17
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) Trưng dụng 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 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.18
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 q lớn ⇒ FIFO q nhỏ ⇒ tổng phí chuyển ngữ cảnh cao ⇒ q phải đủ lớn Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.19
VÍ DỤ RR với Time Quantum = 20 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ớ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 Silberschatz, Galvin and Gagne ©2005 Operating System Concepts – 7th Edition, Feb 2, 2005 5.20