Thảo luận Bài 6

1. Công suất CPU (CPU Utilisation): Thực tế đạt từ 40% - 90% thời gian CPU. CPU càng bận càng tốt.
2. Thông suất hệ thống (Throughput): Số TT hoàn tất trong 1 đơn vị thời gian, ví dụ: 1 TT / giờ, 10 TT / giây.
3. Tổng thời gian làm việc (Turnaround Time): Kể từ khi bắt đầu đến khi kết thúc tiến trình (Bao gồm tổng thời gian chờ tại Ready Queue, tổng thời gian sử dụng CPU, tổng thời gian I/O, …).
4. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
5. Thời gian đáp ứng (Response Time): Thời gian kể từ khi người dùng đặt yêu cầu cho đến khi có phản hồi đầu tiên.

câu 4. đề thi khóa trước về vòng Robin bài 6
1 hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng cpu khác nhau
Tiến trình thời điểm đến cpu-bust(ms)
p1 5 25
p2 10 15
p3 20 10


dùng thuật giải Round-Robin với thời lượng10ms để điều phối cpu
a) thể hiện bằng biểu đồ Gantt
b)tính thời gian chờ trung trình của các tiến trình

giải
a ) thể hiện bằng biểu đồ Gantt

b)tính thời gian chờ của các tiến trình
. p1=(55-5)-25=25
.p2=(50-10)-15=25
.p3=(45-20)-10=15
- thời gian chờ trung bình(25+25+15)/3=65/3=21,6 ms
//giải thích: tiến trình cpubus
p1 25
p2 15
p3 10
hangdoi A=null
p1 đến ở thời điểm giây thứ 5,round-robin với thời lượng 10m/s để điều phối cpu
p1 sẽ được cpu sử lý từ giây thứ 5 đến giây thứ 15, ở giây thứ 10 p2 đến ,p1 vẫn đang được cpu xử lý nên p2 sẽ được đưa vào hàng đợi A
hangdoi A=p2
từ giây 15 cpu sẽ ko sử lý p1 nữa p1 sẽ dô hàng đợi và p1 thời gian cpu bus còn 15s, và cpu sử lý p2 từ giây 15 đến giây 25
hangdoi A=p1
ở giây 20 p2 chưa xử lý xong p3 đến p3 sẽ được đưa vào hàng đợi sau p1
đến giây 25 cpu sẽ ko xử lý p2 nữa và cpubus của p2 còn 5s và đưa p2 vào hàng đợi sau p3,
khi đó cpu sẽ sử lý p1 từ giây 25 đến 35 và cpubus của p1 còn 5s, đến giây 35 p1 sẽ được đưa vào hàng đợi sau p2 và cpu sẽ xử lý p3 từ giây 35 đến giây 45 p3 kết thúc, từ giây 45 cpu sẽ xử lý p2 lúc này cpubus của p2 còn 5s nên cpu sẽ xử lý p2 từ giây 45 đến 50 p2 kết thúc, từ giây 50 cpu sẽ xử lý p1, cpu bus của p1 còn 5s nên cpu sẽ xử lý p1 từ giây 50 đến 55 p1 kết thúc
*công thức tính thời gian chờ của các tiến trình
(thời gian kết thúc - thời gian đến)- cpubus của các tiến trình

* Giải thuật Multilevel Queue Scheduling:
- Độ ưu tiên cố định.
- Chia làm 2 mức tiến trình:Tiến trình có độ ưu tiên cao và tiến trình có độ ưu tiên thấp
- Tiến trình nào được ưu tiên cao nhất thì được chạy trước.Tiến trình được ưu tiên thấp nhất thì chạy sau cùng.Đang chạy tiến trình mức dưới mà có tiến trình mức cao hơn thì tiến trình mức dưới bị tiếm quyền cho tiến trình có mức ưu tiên cao hơn.
-Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau.
VD:Mức các tiến trình tương tác chạy ở mặt trước có độ ưu tiên cao nhất và mức các tiến trình lô(batch) vận hành trong hậu trường.
-Mỗi hàng chờ có thuật giải để điều phối riêng.
-Quan hệ giữa các mức:
+ưu tiên cố định:xong hết các tiến trình mức trên rồi chuyển xuống mức dưới.Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mức cao hơn,tiến trình mức dưới sẽ bị tiếm quyền do tiến trình mới có độ ưu tiên cao hơn.
+Phân bổ theo tỉ lệ thời lượng.
* Giải thuật Multilevel Feedback Queue Scheduling:
- Có thể điều tiết mức ưu tiên của các tiến trình.Những tiến trình hướng CPU được đưa xuống mức dưới,tiến trình hướng I/O được chuyển lên trên.
- Chia làm 2 mức tiến trình:Tiến trình mức trên và tiến trình mức dưới
- Như MQS nhưng cho phép điều tiết tiến trình sang mức khác.
VD:Những tiến trình hướng CPU được đưa xuống mức dưới

- Đặc trưng:
+Thuật giải điều phối cho mỗi mức.
+ Phương thức nâng cấp tiến trình và hạ cấp tiến trình
+ Phương thức chọn hàng chờ (chọn mức) cho tiến trình mới
ví dụ:Trong nhà hàng,khi đang có khách thì người nhân viên phục ưu tiên phục vụ thực khách hơn là những người khác(cấp trên,đồng nghiệp hay cá nhân).

Giống nhau:
Thuật giải điều phối hàng chờ nhiều mức (Multilevel Queue Scheduling) và thuật giải điều phối hàng chờ nhiều mức có điều tiết (Multilevel Feedback Queue Scheduling) cùng sử dụng nhiều hàng chờ có độ ưu tiên khác nhau, mỗi hàng chờ có thể sử dụng cách điều phối khác nhau như điều phối theo vòng Robin (Round Robin Scheduling) hay First Come First Served (FCFS)

Khác nhau:
Thuật giải điều phối hàng chờ nhiếu mức có điều tiết (MFQS) có tính mềm dẻo, uyển chuyển hơn, cho phép điều phối tiến trình từ hàng chờ này sang hàng chờ khác (hạ mức độ ưu tiên xuống)

Ví dụ minh họa:
Phòng bán vé tàu hỏa ở ga Hòa Hưng có nhiều cửa bán vé với mức độ ưu tiên khác nhau, có cửa dành cho những người trong hệ thống (công nhân viên phục vụ trong ga), có cửa dành riêng cho thương binh, người tàn tật...Chỉ có 1 cô bán vé (CPU) phải liên tục di chuyển giữa các cửa để phục vụ cho khách mua vé.

* Bốn tình huống ra quyết định của trình điều phối CPU:
- Các tình huống ra quyết định của trình điều phối:
1. Khi tiến trình chuyển từ Running sang Waiting (Chờ I/O. chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra)
3. Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)
4. Khi tiến trình kết thúc công việc.

- Sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4 được gọi là điều phối không tiếm quyền (Non-Preemptive): Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting . Dùng khi máy không có Timer/Counter.(Quá trình running nếu bị ngắt sẽ tiếp tục running sau đó).
- Sơ đồ điều phối tiến hành trong cả 4 tình huống được gọi là điều phối có tiếm quyền (Preemptive).

* Phân biệt điều phối có tiếm quyền và không có tiếm quyền:
Giống nhau:
- Được dùng trong điều phối CPU (chọn tiến trình trong Ready Queue để cấp thời gian CPU (chuyển sang trạng thái Running)).

Khác nhau:
- Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phối CPU không tiếm quyền.

- Non-Preemptive Scheduling: Có nghĩa là khi tiến trình P1 có thời điểm đến trước P2 thì tiến trình P1 được thực hiện hết khoảng thời gian thực hiện, sau đó mới thực hiện tiến trình P2.

- Preemptive Scheduling: Có nghĩa là khi có 3 tiến trình P1, P2, P3 có thời điểm đến theo thứ tự đó thì tiến trình P1 sẽ được thực hiện với một khoảng thời gian cho phép sau đó bị tiến trình P2 hay P3 tiếm quyền. Còn quá trình điều phối kế tiếp như thế nào là tuỳ thuộc vào thuật toán điều phối và độ ưu tiên của tiến trình.