CHƯƠNG
CHƯƠNG
4: L
4: L
Ậ
Ậ
P L
P L
Ị
Ị
CH BI
CH BI
Ể
Ể
U CPU
U CPU
CPU
CPU
Scheduling
Scheduling
5.2
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
N
N
Ộ
Ộ
I DUNG
I DUNG

gồmchukỳ thựchiệnCPU vàchờ I/O
 Sự phân tán CPU burst
5.4
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
DÃY LUÂN PHIÊN C
DÃY LUÂN PHIÊN C
Á
Á
C CHU K
C CHU K
Ỳ
Ỳ
CPU V
CPU V
À
À
CHU
CHU
K
K
Ỳ
Ỳ
I/O
I/O
5.5
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7

Đ
Ị
Ị
NH TH
NH TH
Ờ
Ờ
I CPU
I CPU
 Chọn trong các quá trình sẵn sàng một quá trình và cấp CPU cho
nó
 Quyếtdịnh lậplịch biểuCPU xảyrakhimột quá trình :
1. Chuyểntừ trạng thái running sang trạng thái waiting
2. Chuyểntừ trạng thái running sang trạng thái ready
3. Chuyểntừ trạng thái waiting sang trạng thái ready
4. Kết thúc
 Lậplịch biểu cho 1 và 4 là không trưng dụng (nonpreemptive)
 Lậplịch biểucònlạilàtrưng dụng (preemptive)
5.7
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
B
B
Ộ
Ộ
ĐI
ĐI
Ề

Ậ
Ậ
P L
P L
Ị
Ị
CH BI
CH BI
Ể
Ể
U
U
 Sự sử dụng CPU: Làm cho CPU bậnrộnnhư có thể
 Năng lựctruyền qua (throughput): số quá trình hoàn tấtsự
thựchiệncủa chúng trong một đơnvị thờigian
 Thời gian quay vòng (Turnaround time) – lượng thờigian
thựchiệnmột quá trình
 Thờigianchờ (Waiting time) – lượng thờigianmột quá
trình phảichờ trong hàng đợi ready
 Thờigianđáp ứng (Response time) – lượng thờigiantừ
khi mộtyêucầu được đệ trình đếnkhiđáp ứng đầutiên
đượcsinhra
5.9
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
C
C
Á

Served (FCFS)
Process Burst Time
P
1
24
P
2
3
P
3
3
 Giả sử các quá trình đếntheothứ tự: P
1
, P
2
, P
3
Biểu đồ Gantt cho lịch biểu:
 Waiting time: đốivới P
1
= 0; P
2
= 24; P
3
= 27
 Waiting time trung bình: (0 + 24 + 27)/3 = 17
P
1
P
2

P
1
P
3
P
2
63300
5.12
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
Shortest
Shortest
-
-
Job
Job
-
-
First (SJF)
First (SJF)
 Kếthợpvớimỗi quá trình độ dài chu kỳ CPU của nó. Sử dụng các
độ dài này để lậplịch biểu quá trình vớithờigianngắnnhất
 Hai sơđồ:
z Không trưng dụng: mỗikhiCPU đượcgánchomột quá trình,
nó không bị trưng dụng đếntận khi hoàn tấtchukỳ CPU của
nó
z Trưng dụng: Nếumột quá trình mới đếncóchukỳ CPU ngắn
hơnthờigiancònlạicủa quá trình đang thựchiện, trưng dụng

D
Ụ
Ụ
SJF KHÔNG TRƯNG D
SJF KHÔNG TRƯNG D
Ụ
Ụ
NG
NG
P
1
P
3
P
2
73160
P
4
8 12
5.14
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
V
V
Í
Í
D
D

11
0
P
4
5 7
P
2
P
1
16
5.15
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
X
X
Á
Á
C Đ
C Đ
Ị
Ị
NH Đ
NH Đ
Ộ
Ộ
D
D
À

t
τ
α
α
τ
−
+
=
+
5.16
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
TIÊN ĐO
TIÊN ĐO
Á
Á
N Đ
N Đ
Ộ
Ộ
D
D
À
À
I CHU K
I CHU K
Ỳ
Ỳ

= τ
n
z Lịch sử gần không được tính đến
 α =1
z τ
n+1
= t
n
z Chỉ chu kỳ CPU hiệntại được tính đến
 Triển khai công thức, ta được:
τ
n+1
= α t
n
+(1 - α)α t
n -1
+ …
+(1 - α )
j
α t
n -j
+ …
+(1 - α )
n +1
τ
0
5.18
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th

Round Robin (RR)
Round Robin (RR)
 Mỗi quá trình nhận đượcmột đơnvị thờigian(nhỏ) - time
quantum , thông thường 10-100 milliseconds. Sau khoảng thời
gian này, quá trình bị lấylạiCPU vàđược đưavàocuốihàng
đợisẵn sàng.
 Nếu có n quá trình trong hàng đợisẵn sàng, time quantum là q,
khi đóthờigianchờ củamỗi quá trình không quá (n-1)q.
 Hiệunăng
z q lớn ⇒ FIFO
z q nhỏ ⇒ tổng phí chuyểnngữ cảnh cao ⇒ q phải đủ lớn
5.20
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
V
V
Í
Í
D
D
Ụ
Ụ
RR
RR
v
v
ớ
ớ

P
3
P
4
P
1
P
3
P
3
0 20 37 57 77 97 117 121 134 154 162
5.21
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
TIME QUANTUM V
TIME QUANTUM V
À
À
TH
TH
Ờ
Ờ
I GIAN CHUY
I GIAN CHUY
Ể
Ể
N
N

H
H
À
À
NG Đ
NG Đ
Ợ
Ợ
I ĐA M
I ĐA M
Ứ
Ứ
C
C
 Hàng đợisẵn sàng đượcphânhoạch thành một các hàng đợi:
foreground (interactive)
background (batch)
 Mỗihàngđợicóthuật toán lậplịch biểuriêngcủanó
z foreground – RR
z background – FCFS
 Lậplịch biểu được làm giữa các hàng đợi
z Lậplịch biểu ưutiêncốđịnh (phụcvụ tấtcả quá trình trong
foreground sau đómới đến các quá trình trong background).
Có thể gây nên chết đói.
z Lát thời gian: mỗihàngđợinhậnmộtlượng thờigianCPU nhất
định để lậplịch biểu cho các quá trình củanó(vídụ 80% thời
gian cho hàng đợi foreground với RR, 20% cho background với
FCFS)
5.24
Silberschatz, Galvin and Gagne ©2005

Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 2, 2005
H
H
À
À
NG Đ
NG Đ
Ợ
Ợ
I PH
I PH
Ả
Ả
N H
N H
Ồ
Ồ
I ĐA M
I ĐA M
Ứ
Ứ
C
C
 Mỗi quá trình có thể di chuyểngiữa các hàng đợi
 Bộ lậplịch biểu hàng đợiphảnhồi đamức đượcxácđịnh bởicác
tham số sau:
z Số hàng đợi