Qu

ả

n lý ti

ế

n trình

T

ừ

Minh Ph

ươ

ng - HVCNBCVT

43

-

Tính công b

ằ

. Nh

ữ

ế

n trình cùng

độ

ư

u tiên ph

ả

đượ

c

đố

i x

ử

nh

ư

nhau, không

ế

n trình nào b

ị

đ

ói

tài

nguyênh

ơ

n nh

ữ

ế

n trình khác.

Trong ph

ầ

n sau, ta s

ẽ

ử

d

ụ

ng nh

ữ

ng tiêu chí trên khi xem xét thu

ậ

t toán

đ

ề

u

độ

c

ụ

th

ể

.

2.3.4. Các thu

ậ

t toán

đ

ề

u

độ

Nhi

ề

u thu

ậ

t toán

đ

ề

u

độ

ế

n trình

đượ

c

đề

xu

ấ

t và s

ử

d

ụ

ng trên th

ự

ct

ế

. Sau

đ

ây là

nh

ữ

ng thu

ậ

t toán tiêu bi

ể

u ho

ặ

c th

ườ

ặ

p nh

ấ

t.

a. Thu

ậ

t toán

đế

ướ

c ph

ụ

c v

ụ

ướ

c

Đế

ướ

c ph

ụ

c v

ụ

ướ

c

(First Come First Served – vi

ế

ắ

t là FCFS) là ph

ươ

ng pháp

đ

ề

u

độ

đơ

ả

n nh

ấ

t, c

ả

v

ề

nguyên t

ắ

c và cách th

ự

c hi

ệ

n. Ti

ế

n trình yêu c

ầ

u CPU tr

ướ

c s

ẽ

đượ

c c

ấ

p CPU tr

ướ

c.

H

ệ

đ

ề

u hành x

ế

ế

n trình s

ẵ

n sàng vào hàng

đợ

i FIFO. Ti

ế

n trình m

ớ

đượ

cx

ế

p vào

cu

ố

i hàng

đợ

i, khi CPU

đượ

c gi

ả

i phóng, h

ệ

đ

ề

u hành s

ẽ

l

ấ

y ti

ế

n trình t

ừ

đầ

u hàng

đợ

i và c

ấ

CPU cho ti

ế

n trình

đ

ó th

ự

c hi

ệ

n.

M

ặ

c dù

đơ

ả

n và

đả

ả

o tính công b

ằ

ng, FCFS có th

ờ

i gian ch

ờ

đợ

i trung bình c

ủ

a

ế

n trình l

ớ

n do ph

ả

i ch

ờ

đợ

ế

n trình có chu k

ỳ

CPU dài trong tr

ườ

ng h

ợ

p nh

ữ

ế

n trình

nh

ư

v

ậ

y n

ằ

ở

đầ

u hàng

đợ

i.

Để

minh h

ọ

a, ta xét ví d

ụ

: cho 3 ti

ế

n trình v

ớ

i th

ứ

ự

xu

ấ

t hi

ệ

và

độ

dài chu k

ỳ

CPU nh

ư

sau:

Ti

ế

n trình

Độ

dài chu k

ỳ

CPU

P1 10

P24

P32

K

ế

t qu

ả

đ

ề

u

độ

theo thu

ậ

t toán FCFS th

ể

hi

ệ

n trên hình sau:

10 14

104

2

P1P2

P3

Th

ờ

i gian ch

ờ

đợ

i c

ủ

a P1, P2, P3 l

ầ

n l

ượ

t là 0, 10, và 14.

Th

ờ

i gian ch

ờ

đợ

i trung bình = (0 + 10 +14)/3 = 8.

Có th

ể

th

ấ

y th

ờ

i gian ch

ờ

đợ

i trung bình nh

ư

v

ậ

y là r

ấ

t l

ớ

n, ch

ẳ

ng h

ạ

n so v

ớ

ườ

ng h

ợ

ế

n trình

đượ

cc

ấ

p CPU theo th

ứ

ự

P3, P2, P1. Khi

đ

óth

ờ

i gian ch

ờ

đợ

i trung bình gi

ả

xu

ố

ng ch

ỉ

còn (6 + 2 + 0)/3 = 2,67.

C

ầ

n l

ư

u ý r

ằ

ng vi

ệ

c t

ă

ng th

ờ

i gian ch

ờ

đợ

i CPU c

ủ

a ti

ế

n trình

ả

nh h

ưở

ấ

t l

ớ

ớ

i hi

ệ

u

su

ấ

t chung c

ủ

a h

ệ

th

ố

ng do nhi

ề

uti

ế

n trình ph

ả

i d

ồ

n l

ạ

i ch

ờ

ộ

ế

n trình trong kho

ả

ng th

ờ

gian quá lâu, d

ẫ

ớ

i tình tr

ạ

ng không ti

ế

n trình nào th

ự

c hi

ệ

đượ

c công vi

ệ

cc

ủ

a mình, k

ể

c

ả

vào ra. K

ế

t qu

ả

là toàn h

ệ

th

ố

ng ph

ả

i d

ừ

ng l

ạ

i ch

ờ

ả

i phóng CPU.

Thu

ậ

t toán FCFS thông th

ườ

ng là thu

ậ

t toán

đ

ề

u

độ

không phân ph

ố

i l

ạ

i. Sau khi ti

ế

trình

đượ

c c

ấ

p CPU, ti

ế

n trình

đ

ó s

ẽ

ử

d

ụ

ng CPU cho

đế

n khi k

ế

t thúc ho

ặ

c ph

ả

i d

ừ

ng l

ạ

để

ch

ờ

k

ế

t qu

ả

vào ra.

Để

có th

ể

ử

d

ụ

đượ

c trong nh

ữ

ng h

ệ

th

ố

ng chia s

ẻ

th

ờ

i gian, thu

ậ

t toán