Bài giảng Hệ điều hành - Chương 4: Định thời CPU (Phần 2) - 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
Định thời CPU
2
Ô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
Định thời CPU
3
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
Định thời CPU
4
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
Định thời CPU
5
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
Định thời CPU
6
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
Định thời CPU
7
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ỏ
Định thời CPU
8
Round Robin (RR) (tt)
Ví dụ: Quantum time = 20
Process Burst Time
P1
P2
P3
P4
53
17
68
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
Định thời CPU
9
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
I/O-bound
CPU-bound
Định thời CPU
10
Round Robin (RR) (tt)
Quantum time và context switch:
context
switch
quantum
Process time = 10
0
12
10
6
1
1
9
1 2 3 4 5 6 7 8 9 10
Định thời CPU
11
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
Định thời CPU
12
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
Định thời CPU
13
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
Định thời CPU
14
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
Định thời CPU
15
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 Ig 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)
Định thời CPU
16
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
Đị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
Định thời CPU
18
Highest Response Ratio Next
Tại mốc thời gian thứ 9, sau khi P2 thực
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:
Ví dụ:
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.
hứ 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 đó
P1
P2
P3
P5
P4
2
9
14 16
20
Định thời CPU
19
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
Định thời CPU
Tải về để xem bản đầy đủ
31 trang
12720
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 4: Định thời CPU (Phần 2) - Trần Thị Như Nguyệt", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_he_dieu_hanh_chuong_4_dinh_thoi_cpu_phan_2_tran_th.pdf
