BÀI T P CH NG IIẬ ƯƠ
QU N LÍ TI N TRÌNHẢ Ế
1./ Xét t p h p các ti n trình sau:ậ ợ ế
Ti n trìnhếTh i đi mờ ể
vào RL
Th i gianờ
CPU
Đ uộ ư
tiên
P10 10 3
P21 1 1
P32.5 2 3
P43 1 4
P54.5 5 2
Hãy cho bi t k t qu đi u ph i theo các chi n l c ế ế ả ề ố ế ượ
•FCFS
•SJF
•Round Robin v i q = 2ớ
•Đ u tiên đ c quy nộ ư ộ ề
•Đ u tiên không đ c quy nộ ư ộ ề
•tính th i gian ch cho t ng ti n trình và th i gian ch trung bình trong các chi n l c trên.ờ ờ ừ ế ờ ờ ế ượ
Gi iả
a./ FCFS
P1P2P3P4P5
Th i gian ch :ờ ờ
P1: 0
P2: 10 – 1 = 9
P3: 11 – 2.5 = 8.5
P4: 13 – 3 = 10
P5: 14 – 4.5 = 9.5
b./ SJF
P1P2P4P3P5
Th i gian ch :ờ ờ
P1: 0
P2: 10 – 1 = 9
P3: 12 – 2.5 = 9.5
P4: 11 – 3 = 8
P5: 14 – 4.5 = 9.5
⇒
Th i gian ch trung bình = ờ ờ
37 7.45
5=
⇒
Th i gian ch trung bình = ờ ờ
36 7.2
5=
0
10
11
12
14
19
P1P2P3P4P5
0
10
11
13
14
19
P1P2P3P4P5
c./ Round Robin
P1P2P1P3P4P5P1P5P1P5P1
Th i gian ch :ờ ờ
P1: 1 + 5 + 2 + 1 = 9
P2: 2 – 1 = 1
P3: 5 – 2.5 = 2.5
P4: 7 – 3 = 4
P5: 8 + 2 + 2 – 4.5 = 7.5
d./ Đ u tiên đ c quy nộ ư ộ ề
P1P2P5P3P4
Th i gian ch :ờ ờ
P1: 0
P2: 10 – 9 = 1
P3: 16 – 2.5 = 13.5
P4: 18 – 3 = 5
P5: 11 – 4.5 = 6.5
e./ Đ u tiên không đ c quy nộ ư ộ ề
P1P2P1P5P3P1P4
Th i gian ch :ờ ờ
P1: 1 + 7 = 8
P2: 0
P3: 9.5 – 2.5 = 7
P4: 18 – 3 = 15
P5: 0
2./ Cho các ti n trình sau:ế
Ti n trìnhếTh i đi m vào RLờ ể Th i gian CPUờ
P10 8
P20.4 4
P31 1
Hãy cho bi t các k t qu đi u ph i chi n l c FCFS và SJF và th i gian ch c a t ng chi n l cế ế ả ề ố ế ượ ờ ờ ủ ừ ế ượ
19
P1P2P3P4P5
2
12
0
10
14
3
5
7
8
16
17
⇒
Th i gian ch trung bình =ờ ờ
25 5
5=
0
10
11
16
18
19
P1P2P3P4P5
⇒
Th i gian ch trung bình ờ ờ
44 8.8
5
= =
⇒
Th i gian ch trung bình ờ ờ
25 5
5
= =
0
9.5
18
19
P1P2P3P4P5
1
2
4.5
Gi iả
a./ FCFS
P1P2P3
Th i gian chờ ờ
P1: 0
P2: 8 – 0.4 = 7.6
P3: 12 – 1 = 11
b./ SJF
P1P3P2
P1: 0
P2: 9 – 0.4 = 8.6
P3: 8 – 1 = 7
3./ Đi u ph i các ti n trình sau theo chi n l c đi u ph i đ u tiên đ c quy n. ề ố ế ế ượ ề ố ộ ư ộ ề
Ti n trìnhếChi u dài CPU burstềTh i đi m vào RLờ ể Đ u tiênộ ư
P12 0 2
P25 1 3
P33 2 1
P44 3 0
Tính th i gian ch cho t ng ti n trình và th i gian ch trung bình.ờ ờ ừ ế ờ ờ
Gi iả
P1P3P4P2
Th i gian ch :ờ ờ
P1: 0
P2: 9 – 1 = 8
P3: 0
P4: 5 – 3 = 2
Chú ý:
- FCFS vào tr c th c hi n tr c.ướ ự ệ ướ
- SJF ti n trình nào có chi u dài CPU burst ng n thì th c hi n tr c.ế ề ắ ự ệ ướ
P1P2P3
8
13
0
12
⇒
Th i gian ch trung bình ờ ờ
18.6 6.2
3
= =
P1P2P3
8
13
0
9
⇒
Th i gian ch trung bình ờ ờ
15.6 5.2
3
= =
P1P2P3
2
14
0
5
P4
9
⇒
Th i gian ch trung bình ờ ờ
10 2.5
4
= =
- RR m i ti n trình ch đ c th c hi n trong m t th i gian q nh t đ nh, các ti n trình l n l t th c hi nỗ ế ỉ ượ ự ệ ộ ờ ấ ị ế ầ ượ ự ệ
xoay vòng.
- Đi u ph i theo đ u tiên đ c quy n: có đ u tiên nh th c hi n tr c.ề ố ộ ư ộ ề ộ ư ỏ ự ệ ướ
- Đi u ph i u tiên không đ c quy n: gi ng nh trên nh ng n u đang th c hi n mà xu t hi n ti n trìnhề ố ư ộ ề ố ư ư ế ự ệ ấ ệ ế
có đ u tiên nh h n thì ph i d ng đ nh ng cho ti n trình kia th c hi n.ộ ư ỏ ơ ả ừ ể ườ ế ự ệ
BÀI T P CH NG IVẬ ƯƠ
QU N LÍ B NH CHÍNHẢ Ộ Ớ
1./ Trong mô hình c p phát b nh liên t c, có năm phân m nh b nh theo th t v i kích th c là 600KB,ấ ộ ớ ụ ả ộ ớ ứ ự ớ ướ
500KB, 200KB, 300KB. Gi s có 4 ti n trình đang ch c p phát b nh theo th t P1, P2, P3, P4. Kíchả ử ế ờ ấ ộ ớ ứ ự
th c t ng ng c a các ti n trình trên là: 212KB, 417KB, 112KB, 426KB. Hãy c p phát b nh cho các ti nướ ươ ứ ủ ế ấ ộ ớ ế
trình trên theo thu t toán First-fit, Best-first, Worst-fit.ậ
Gi iả
First – fit
P4 chờ
Best – fit
Worst – fit
P4 chờ
2./ (đ ki m tra) Trong mô hình c p phát b nh i liên t c, có 5 phân m nh b nh v i kích th c là 200KB,ề ể ấ ộ ớ ụ ả ộ ớ ớ ướ
400KB, 600KB, 300KB, 500KB. Gi s có 4 ti n trình đang ch c p phát b nh theo th t P1, P2, P3, P4.ả ử ế ờ ấ ộ ớ ứ ự
Kích th c t ng ng các ti n trình trên là: 220KB, 250KB, 550KB, 320KB.ướ ươ ứ ế
Hãy c p phát b nh cho các ti n trình trên theo thu t toán First – fit và Best – fit.ấ ộ ớ ế ậ
Gi iả
First – fit
P3 đang chờ
P1 P3 P2
P4 P2 P3 P1
P1 P3 P2
P1 P2 P4
600KB
426KB 174KB
500KB
200KB 300KB
600KB
212KB 112KB 276KB
500KB
200KB 300KB
600KB
212KB 112KB 276KB
500KB
417KB 83KB
200KB 300KB
417KB 83KB 88KB
112KB 88KB212KB
400KB 600KB 300KB 500KB
220KB 250KB 320KB
200KB
417KB 83KB
Best – fit
Chú ý: - First – fit :tìm vùng nh đ u tiên đ l n đ ch a ti n trìnhớ ầ ủ ớ ể ứ ế
- Best – fit: tìm vùng nh nh nh t mà có th ch a ti n trìnhớ ỏ ấ ể ứ ế
- Worst – fit:tìm vùng nh l n nh t c p cho ti n trình.ớ ớ ấ ấ ế
3./ M t ti n trình đ c n p vào b nh theo mô hình phân trang v i kích th c trang là 1024 byte. B ng trangộ ế ượ ạ ộ ớ ớ ướ ả
nh sau:ư
Hãy chuy n các đ a ch logic sau thành đ a ch v t lý: a) 1251; b) 3249ể ị ỉ ị ỉ ậ
1
5
3
6
Gi iả
a)
a = 1521
p = 1521 div 1024 = 1
d = 1521 mod 1024 = 497
f = 5 (d a vào b ng trang vì p = 1)ự ả
A=5*1024 + 497 = 5617
b)
a = 3249
p = 3249 div 1024 = 3
d = 1521 mod 1024 = 177
f = 6 (d a vào b ng trang vì p = 3)ự ả
A=6*1024 + 177 = 6321
4./ M t ti n trình đ c n p vào b nh theo mô hình phân trang v i kích th c trang là 512byte. B ng trangộ ế ượ ạ ộ ớ ớ ướ ả
nh sau:ư
Hãy chuy n các đ a ch logic sau thành đ a ch v t lý: a) 689; b) 1613ể ị ỉ ị ỉ ậ
2
6
5
3
a)
a = 689
p = 689 div 512 = 1
d = 689 mod 512 = 177
f = 6 (d a vào b ng trang vì p = 1)ự ả
A=6*512 + 177 = 3249
b)
a = 1613
p = 1613 div 512 = 3
d = 1613 mod 512 = 77
f = 3 (d a vào b ng trang vì p = 3)ự ả
A=3*512 + 77 = 1613
Chú ý:
Ta có các công th c sau đây:ứ
P = a div ps
d = a mod ps
T p và b ng trang đ tìm fừ ả ể
A = f*ps + d
P2 P3 P1 P4
200KB
400KB 600KB 300KB
220KB
250KB 320KB
550KB
500KB