Bài giảng Hệ điều hành - Chương 5: Định thời CPU - Lê Ngọc Minh

 Chương 5
 Định thời CPU
 -6.1-
 Nội dung
‰ Khái niệm cơ bản
‰ Các bộ định thời
 – long-term, mid-term, short-term
‰ CáctiêuchuẩnđịnhthờiCPU
‰ Các giải thuật định thời
 – First-Come, First-Served (FCFS)
 – Round-Robin (RR)
 – Shortest Job First (SJF)
 – Shortest Remaining Time First (SRTF)
 – Highest Response Ratio Next (HRRN)
 – Multilevel Queue 
 – Multilevel Feedback Queue
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.2-
 1
 Khái niệm cơ bản
‰ Trong các hệ thống multi-tasking
 – Thực thi nhiều chương trình đồng thời làm tăng hiệu suất hệ
 thống.
 – Tại mỗi thời điểm, chỉ có một process được thực thi. Do đó, 
 cần phải giải quyết vấn đề phân chia, lựa chọn process thực
 thi sao cho được hiệu quả nhất → chiến lược định thời CPU.
‰ Định thời CPU 
 – Chọn một process (từ ready queue) thực thi.
 – Với một multithreaded kernel, việc định thời CPU là do OS 
 chọn kernel thread được chiếm CPU.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.3-
 Các bộ định thời
 new
 Long-Term Long-Term
 scheduling scheduling
 suspended Medium -Term Short-Term
 ready
 ready scheduling scheduling
 running
 suspended Medium -Term
 blocked
 blocked scheduling terminated
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.4-
 2
 Các hàng đợi định thời
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.5-
 Các bộ định thời
‰ Long-Term Scheduling
 – Xác định chương trình nào được chấp nhận nạp vào hệ thống
 để thực thi
 – Điều khiển mức độ multiprogramming của hệ thống
 – Long term scheduler thường cố gắng duy trì xen lẫn CPU-bound 
 và I/O-bound process
‰ Medium-Term Scheduling 
 – Sự chuyển đổi dựa trên sự cần thiết để quản lý
 multiprogramming
 – Được thực hiện bởi phần quản lý bộ nhớ và được thảo luận ở
 phần quản lý bộ nhớ.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.6-
 3
 Short-Term Scheduling
‰ Xác định process nào trong ready queue sẽ được chiếm CPU 
 để thực thi kế tiếp (do vậy còn được gọi là định thời CPU-
 CPU scheduling)
‰ Short term scheduler còn được gọi với tên khác là dispatcher
‰ Bộ định thời short-term được gọi mỗi khi có một trong các sự
 kiện/interrupt sau xảy ra:
 – clock interrupt
 – I/O interrupt
 – operating system call, trap
 – signal
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.7-
 Các tiêu chuẩn định thời CPU
‰ User-oriented
 – Response Time: khoảng thời gian process nhận yêu cầu đến khi
 yêu cầu đầu tiên được đáp ứng (time-sharing, interactive 
 system) → cực tiểu
 – Turnaround Time: khoảng thời gian từ lúc một process được nạp
 vào hệ thống đến khi process đó kết thúc → cực tiểu
 – Waiting Time: tổng thời gian một process đợi trong ready queue 
 → cực tiểu
‰ System-oriented
 – processor utilization: định thời sao cho CPU càng bận càng tốt →
 cực đại
 – fairness: tất cả process phải được đối xử như nhau
 – throughput: số process hoàn tất công việc trong một đơn vị thời
 gian → cực đại.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.8-
 4
 Hai yếu tố của giải thuật định thời
‰ Hàm chọn lựa (selection function): dùng để chọn process nào trong
 ready queue được thực thi (thường dựa trên độ ưu tiên, yêu cầu về
 tài nguyên, đặc điểm thực thi của process,...), ví dụ
 – w = tổng thời gian đợi trong hệ thống
 – e = thời gian đã được phục vụ
 – s = tổng thời gian thực thi của process (bao gồm cả “e”)
‰ Chế độ quyết định (decision mode): chọn thời điểm thực hiện hàm
 chọn lựa để định thời. Có hai chế độ
 – Nonpreemptive
 ƒ Khi ở trạng thái running, process sẽ thực thi cho đến khi kết
 thúc hoặc bị blocked do yêu cầu I/O
 – Preemptive
 ƒ Process đang thực thi (trạng thái running) có thể bị ngắt nửa
 chừng và chuyển về trạng thái Ready bởi hệ điều hành
 ƒ Chi phí cao hơn non-preemptive nhưng đánh đổi lại bằng
 thời gian đáp ứng tốt hơn vì không có trường hợp một
 process độc chiếm CPU quá lâu.
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.9-
 Khảo sát giải thuật định thời
 load store
 add store CPU burst
 read from file chu kỳ
 CPU-I/O Arrival Service 
 Process
 wait for I/O I/O burst Time Time
 inc store 1 0 3
 CPU burst
 writeto file
 2 2 6
 wait for I/O I/O burst 3 4 4
 load store 4 6 5
 CPU burst
 add store 5 8 2
 read from file
 wait for I/O I/O burst
 ‰ Service time = thời gian process cần CPU trong một chu kỳ
 CPU-I/O 
 ‰ Process có service time lớn là các CPU-bound process
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.10-
 5
 First-Come First-Served (FCFS)
‰ Hàng đợi Ready là một hàng đợi kiểu FIFO 
‰ Selection function: process nào đợi lâu nhất trong ready 
 queue sẽ được chọn thực thi
‰ Decision mode: non-preemptive
 – Process sẽ thực thi đến khi kết thúc hoặc bị blocked do I/O
 0 51015 20
 P1
 P2
 P3
 P4
 P5
‰Process nào không có thực hiện I/O sẽ được độc chiếm CPU.
‰Các process I/O-bound (ít CPU-burst) không được ưu tiên
bằng các process CPU-bound (nhiều CPU-burst)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.11-
 Shortest Job First (SJF)
‰ Selection function: process nào có độ dài CPU burst 
 kế tiếp nhỏ nhất sẽ được chọn thực thi.
‰ Decision mode: non-preemptive
‰ I/O-bound process sẽ được ưu tiên hơn so với CPU-
 bound process
‰ Yêu cầu: phải ước tính được CPU-burst của process
 0510 15 20
 P1
 P2
 P3
 P4
 P5
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.12-
 6
 Ước tính độ dài của CPU Burst
‰ Độ dài của CPU Burst chỉ có thể ước tính xấp xỉ
 dùng phép tính trung bình hàm mũ (exponential 
 average) dựa trên độ dài của CPU-burst trước.
 1. tn = độ dài thực sự của CPU burst thứ n
 2. τn+1: giá trị ước đoán của CPU burst (n + 1)
 3. α, 0 ≤ α ≤ 1
 4. Độ dài ước tính CPU burst thứ n+1 là:
 τ n+1 = αtn + (1− α )τ n
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.13-
 Ước tính độ dài của CPU Burst (t.t)
‰ Khai triển công thức:
 τ n+1 = αtn + (1− α )τ n
 2
 = αtn + ()1− α αtn−1 + ()1− α ατ n−1
 n−1
 (1 )it (1- )n
 = α ∑ − α n−i + α τ 1
 i= 0
 ‰ Giá trị τ1 không ước tính mà thường gán = 0
 ‰ α=0 ⇒τn+1 = τn ⇒ không quan tâm đến “quá khứ”
 ‰ α=1 ⇒τn+1 = tn ⇒ chỉ quan tâm đến “ngày hôm qua”
 ‰ α=1/2
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.14-
 7
 Ví dụ ước tính độ dài CPU Burst
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.15-
 Nhận xét về giải thuật SJF
‰ Có thể xảy ra tình trạng “chết đói” (starvation) đối với
 các process có CPU-burst lớn khi có nhiều process với
 CPU-burst nhỏ đến hệ thống.
‰ Cơ chế non-preemptive không phù hợp cho hệ thống
 time sharing (interractive)
‰ Giải thuật SJF ngầm định ra độ ưu tiên theo burst 
 time 
‰ Các CPU-bound process có độ ưu tiên thấp hơn so 
 với I/O-bound process, nhưng khi một process 
 không thực hiện I/O được thực thi thì nó độc chiếm
 CPU cho đến khi kết thúc
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.16-
 8
 Shortest Remaining Time First
‰ Tương tự như SJF nhưng decision mode là
 preemptive
‰ Yêu cầu: phải ước tính được CPU-burst của process
 0 51015 20
 P1
 P2
 P3
 P4
 P5
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.17-
 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.
‰ 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ỏ
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.18-
 9
 RR với Time Quantum = 1
¾ Thời gian turn-around 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
 9 I/O-bound process thường sử dụng rất ít thời gian của
 CPU, sau đó phải blocked đợi I/O
 9 CPU-bound process tận dụng hết quantum time, sau đó
 quay về ready queue ⇒ được xếp trước các process bị
 blocked
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.19-
 Time Quantum và Context Switch
 C ontext
 Q uantum 
 Process time = 10 Switch
 12 0
 010
 6 1
 0106
 1 10
 012345678910
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.20-
 10
 Quantum và response time
‰ Quantum time phải lớn hơn thời gian dùng để xử lý clock interrupt 
 (timer) và thời gian dispatching 
‰ Nên lớn hơn thời gian tương tác trung bình (typical interaction)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.21-
 Highest Response Ratio Next
 0510 15 20
 P1
 P2
 P3
 P4
 P5
 time spent waiting + expected service time
 RR =
 expected service time
 ‰ 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ỏ)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.22-
 11
 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 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
‰ 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 
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.23-
 Multilevel Queue Scheduling
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.24-
 12
 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ế feedback: 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.
‰ Multilevel Feedback Queue
 – Phân loại processes dựa trên các đặc tính về CPU-burst
 – Sử dụng decision mode preemptive 
 – Sau một khoảng thời gian nào đó, các I/O-bound process 
 và interactive process sẽ ở các hàng đợi có độ ưu tiên cao
 hơn còn CPU-bound process sẽ ở các queue có độ ưu tiên
 thấp hơn .
 – 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)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.25-
 Multilevel Feedback Queue (t.t)
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.26-
 13
 Multilevel Feedback Queue (t.t)
‰ Định thời bằ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?
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.27-
 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:
 – 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
 Khoa Công Nghệ Thông Tin – Đại Học Bách Khoa Tp.HCM -6.28-
 14