Nguyên lý hệ điều hành - Tuần 4: Phân tích tiến trình và thuật toán lập lịch. Môn Nguyên lý hệ điều hành (UET) | Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội.

lOMoAR cPSD| 58833082
Bài 1: Có 5 tiến trình P1, P2 , P3, P4, P5 với thời gian chạy
CPU (ms), thời gian đến và số hiệu ưu tiên như sau: Thời gian chạy Số hiệu ưu tiên Thời gian đến P1 2 2 0 P2 1 1 1 P3 8 5 3 P4 4 3 4 P5 5 4 5
Với mỗi thuật toán lập lịch sau hãy vẽ biểu đồ Gantt và tính
thời gian chờ trung bình, thời gian phản hồi trung bình, thời
gian hoàn thành trung bình, số lần chuyển trạng thái của CPU a.
Round Robin với quantum = 2 (ms) b. SJF cho phép dừng c.
Lập lịch theo số hiệu ưu tiên cho phép dừng (biết
rằng tiến trình có số hiệu ưu tiên cao hơn sẽ được chạy trước) Bài làm a.
P1 P2 P3 P4 P5 P3 P4 P5 P3 P5 P3
0 2 3 5 7 9 11 13 15 17 18 20 Thời gian chờ
Thời gian phản hồi Thời gian hoàn thành P1 0-0=0 0-0=0 2-0=2 P2 2-1=1 2-1=1 3-1=2 P3 (3-3)+(9-5)+(15-11)+ 3-3=0 20-3=17 (18-17)=9 lOMoAR cPSD| 58833082 P4 (5-4)+(11-7)=5 5-4=1 13-4=9 P5 (7-5)+(13-9)+(17-15) 7-5=2 18-5=13 =8
Thời gian trung bình 23/5=4.6 4/5=0.8 43/5=8.6 (ms)
Số lần chuyển trạng thái của CPU: 10 lần b. P1 P2 P3 P4 P5 P3 0 2 3 4 8 13 20 Thời gian chờ Thời gian phản hồi Thời gian hoàn thành P1 0-0=0 0-0=0 2-0=2 P2 2-1=1 2-1=1 3-1=2 P3 (3-3)+(13-4)=9 3-3=0 20-3=17 P4 4-4=0 4-4=0 8-4=4 P5 8-5=3 8-5=3 13-5=8
Thời gian trung bình 13/5=2.6 4/5=0.8 33/5=6.6 (ms)
Số lần chuyển trạng thái của CPU: 5 lần c. P1 P2 P3 P5 P4 0 2 3 11 16 20 Thời gian chờ
Thời gian phản hồi Thời gian hoàn thành P1 0-0=0 0-0=0 2-0=2 lOMoAR cPSD| 58833082 P2 2-1=1 2-1=1 3-1=2 P3 3-3=0 3-3=0 11-3=8 P4 16-4=12 16-4=12 20-4=16 P5 11-5=6 11-5=6 16-5=11
Thời gian trung bình 19/5=3.8 19/5=3.8 39/5=7.8
Số lần chuyển trạng thái của CPU: 4 lần
Bài 2: Vẽ biểu đồ Gantt và tính thời gian chờ trung bình, thời
gian hoàn thành trung bình, thời gian phản hồi trung bình cho
các tiến trình khi sử dụng thuật toán hàng đợi đa cấp. Hàng đợi Tiến trình
Thời gian chạy Thời gian đến Thuật toán Hàng đợi trước số 1 P1 50 0 RR quantum=20 P2 15 30 P3 45 30 Hàng đợi trước số 2 P4 40 0 SJF cho phép dừng P5 10 120 Hàng đợi sau P6 30 60 FCFS P7 20 130
Biết rằng trình tự ưu tiên các hàng đợi như sau: Hàng đợi
trước số 1, Hàng đợi trước số 2, Hàng đợi sau. Bài làm Biểu đồ Gantt lOMoAR cPSD| 58833082
P1 P1 P2 P3 P1 P3 P4 P5 P4 P6 P7
0 20 40 55 75 85 110 120 130 160 190 210 Thời gian chờ
Thời gian phản hồi Thời gian hoàn thành P1 (0-0)+(75-40)=35 0-0=0 85-0=85 P2 40-30=10 40-30=10 55-30=25 P3 (55-30)+(85-75)=35 55-30=25 110-30=80 P4 (110-0)+(130-120)=1 110-0=110 160-0=160 20 P5 120-120=0 120-120=0 130-120=10 P6 160-60=100 160-60=100 190-60=130 P7 190-130=60 190-130=60 210-130=80
Thời gian trung bình 51.428571 43.571429 81.428571