Ch05 Cpu Scheduling

ĐỊ NH THỜI CPU

Mụ c tiêu ■

Hiể u được ●

Tạ i sao cầ n phả i đị nh thời

●

Các tiêu chí đị nh thời

●

Mộ t số giả i thuậ t đị nh thời

Ghi chú: những slide có dấ u * ở tiêu đề là những slide dùng để diễ n giả i thêm

Định thời CPU

2

Mộ t cách phân loạ i quá trình ■

Chu kỳ CPU-I/O

■

CPU-bound process có thời gian sử dụ ng CPU nhiề u hơn thời gian sử dụ ng I/O

■

I/O-bound process dùng phầ n lớn thời gian để đợi I/O

Định thời CPU

3

Vấ n đề cầ n giả i quyế t ■

Trong các hệ thố ng multitasking ●

Tạ i mộ t thời điể m trong bộ nhớ có nhiề u process

●

Tạ i mỗ i thời điể m chỉ có mộ t process được thực thi

●

Do đó, cầ n phả i giả i quyế t vấ n đề phân loạ i và lự a chọ n process thự c thi sao cho đượ c hiệ u quả nhấ t. Cầ n có chiế n lượ c đị nh thờ i CPU

Định thời CPU

4

Phân loạ i các hoạ t độ ng đị nh thời (1/2) new

Long-term scheduling

suspended ready

Long-term scheduling Medium-term scheduling

ready

Đường gạch rời: chuyển đổi không nhất thiết có

Short-term scheduling running

suspended blocked

Medium-term scheduling blocked Định thời CPU

terminated 5

Phân loạ i các hoạ t độ ng đị nh thời (2/2) ■

Đị nh thời dài hạ n (long-term scheduling): xác đị nh process nào được chấ p nhậ n vào hệ thố ng.

■

Đị nh thời trung hạ n (medium-term scheduling): xác đị nh process nào được đưa vào (swap in), đưa ra khỏ i (swap out) bộ nhớ chính. ●

■

Swap in/out có thể tố n đế n vài giây thời gian ⇒ chu kỳ đị nh thời trung hạ n có thể là vài phút.

Đị nh thời ngắ n hạ n (short-term scheduling): xác đị nh process nào được thực thi tiế p theo.

Định thời CPU

6

Đị nh thời dài hạ n ■

Xác đị nh chương trình nào sẽ được đưa vào hệ thố ng để thực thi

■

Quyế t đị nh độ -đa-lậ p-trình (degree of multiprogramming)

■

Nế u càng nhiề u process được đưa vào hệ thố ng

■

●

Khả năng mọ i process bị block có xu hướng giả m

●

Sử dụ ng CPU hiệ u quả hơn

●

Mỗ i process được phân chia khoả ng thời gian sử dụ ng CPU thấ p hơn

Thường có xu hướng đưa vào mộ t tậ p lẫ n lộ n các CPU-bound process và I/O-bound process

Định thời CPU

7

Đị nh thời trung hạ n ■

Quyế t đị nh việ c đưa process vào bộ nhớ chính, hay ra khỏ i bộ nhớ chính

■

Phụ thuộ c vào yêu cầ u quả n lý việ c đa-lậ p-trình (multiprogramming)

■

●

Cho phép bộ đị nh thời dài hạ n chấ p nhậ n nhiề u process hơn số lượng process mà có tổ ng kích thước được chứa vừa trong bộ nhớ chính

●

Nhưng nế u có quá nhiề u process thì sẽ làm tăng việ c truy xuấ t đĩa, do đó cầ n phả i lựa chọ n độ -đa-lậ p-trình cho phù hợp

Được thực hiệ n bởi phầ n mề m quả n lý bộ nhớ

Định thời CPU

8

Đị nh thời ngắ n hạ n ■

Xác đị nh process nào được thực thi tiế p theo, còn gọ i là đị nh thời CPU

■

Được kích hoạ t khi có mộ t sự kiệ n có thể dẫ n đế n khả năng chọ n mộ t process để thực thi ●

Ngắ t thời gian (clock interrupt)

●

Ngắ t ngoạ i vi (I/O interrupt)

●

Lời gọ i hệ thố ng (operating system call)

●

Signal

Chương này sẽ tậ p trung vào đị nh thời ngắ n hạ n.

Định thời CPU

9

Nộ i dung cầ n quan tâm ■

Đị nh thời trên hệ thố ng có mộ t processor (uniprocessor scheduling): quyế t đị nh việ c sử dụ ng (mộ t) CPU cho mộ t tậ p các process trong hệ thố ng

■

Tiêu chí nào?

Định thời CPU

10

Tiêu chí đị nh thời (1/4) ■

■

Độ lợi CPU (CPU utilization) ●

Khoả ng thời gian CPU bậ n, từ 0% đế n 100%

●

Cầ n giữ cho CPU càng bậ n càng tố t

Thời gian chờ (waiting time) ●

Thời gian chờ trong hàng đợi ready

●

Các process nên được chia sẻ việ c sử dụ ng CPU mộ t cách công bằ ng (fair share)

Định thời CPU

11

Tiêu chí đị nh thời (2/4) ■

Thông năng (throughput) ●

■

Số lượng process hoàn tấ t trong mộ t đơn vị thời gian

Thời gian đáp ứng (response time) ●

Thời gian từ lúc có yêu cầ u củ a người dùng (user request) đế n khi có đáp ứng đầ u tiên (lưu ý: đáp ứng đầ u tiên, chứ không phả i output)

●

Thường là vấ n đề với các I/O-bound process

Định thời CPU

12

Tiêu chí đị nh thời (3/4) ■

■

Thời gian quay vòng (turnaround time) ●

Thời gian để mộ t process hoàn tấ t, kể từ lúc vào hệ thố ng (submission) đế n lúc kế t thúc (termination)

●

Là mộ t trị đặ c trưng cầ n quan tâm với các process thuộ c dạ ng CPU-bound

Thời gian quay vòng trung bình (average turnaround time)

Định thời CPU

13

Tiêu chí đị nh thời (4/4) ■

Độ lợi CPU – giữ CPU càng bậ n càng tố t ●

■

Thông năng – số lượng process kế t thúc việ c thực thi trong mộ t đơn vị thời gian ●

■

Tố i thiể u hóa

Thời gian chờ – thời gian mộ t process chờ trong hàng đợi ready ●

■

Tố i đa hóa

Turnaround time – thời gian kể từ lúc đưa vào (submission) đế n lúc kế t thúc ●

■

Tố i đa hóa

Tố i thiể u hóa

Thời gian đáp ứng – thời gian từ khi đưa yêu cầ u đế n khi có đáp ứng đầ u tiên ●

Tố i thiể u hóa Định thời CPU

14

Có thể làm được? ■

Tấ t cả các tiêu chí không thể được tố i ưu đồ ng thời vì có mộ t số tiêu chí liên quan nhau

Định thời CPU

15

Tiêu chí đị nh thời từ các góc nhìn (1/2) ■

Hướng đế n người sử dụ ng (user-oriented) ●

●

Thời gian quay vòng  Thời

gian từ lúc nạ p process đế n lúc process kế t thúc

 Cầ n

quan tâm với các hệ thố ng xử lý bó (batch system)

Thời gian đáp ứng  Cầ n

quan tâm với các hệ thố ng giao tiế p (interactive system)

Định thời CPU

16

Tiêu chí đị nh thời từ các góc nhìn (2/2) ■

Hướng đế n hệ thố ng (system-oriented) ●

Độ lợi CPU

●

Công bằ ng (fairness)

●

Thông năng: số process hoàn tấ t trong mộ t đơn vị thời gian

Định thời CPU

17

Hai thành phầ n củ a chiế n lược đị nh thời (1/2) ■

Hàm lựa chọ n (selection function) ●

Xác đị nh process nào trong ready queue sẽ được thực thi tiế p theo. Thường theo các tiêu chí như w

= tổ ng thờ i gian đợ i trong hệ thố ng

e

= thờ i gian đã đượ c phụ c vụ

= tổ ng thờ i gian thự c thi củ a process (bao gồ m cả trị e)

s

Định thời CPU

18

Hai thành phầ n củ a chiế n lược đị nh thời (2/2) ■

Chế độ quyế t đị nh (decision mode) ●

Chọ n thời điể m hàm lựa chọ n đị nh thời thực thi

●

Nonpreemptive  Mộ t

process sẽ ở trạ ng thái running cho đế n khi nó bị block hoặ c nó kế t thúc

●

Preemptive  Process

đang thực thi có thể bị ngắ t và chuyể n về trạ ng thái

ready  Tránh

trường hợp mộ t process độ c chiế m (monopolizing) CPU

Định thời CPU

19

Nonpreemption và preemption (1/2) ■

Hàm đị nh thời có thể được thực thi khi có quá trình (1) chuyể n từ trạ ng thá i running sang waiting (2) chuyể n từ trạ ng thá i running sang ready (3) chuyể n từ trạ ng thá i waiting, new sang ready (4) kế t thú c thự c thi

■

Đị nh thờ i nonpreemptive: chỉ thực thi hàm đị nh thời trong trườ ng hợ p 1 và 4

■

Đị nh thờ i preemptive: ngoài trường hợp 1 và 4 còn thực thi thêm hàm đị nh thời trong trường hợp 2 hoặ c 3 (hoặ c cả hai)

Định thời CPU

20

Nonpreemption và preemption (2/2) ■

Hiệ n thực cơ chế nào khó hơn? Tạ i sao?

■

Preemptive scheduling hiệ n thực khó hơn: cầ n phả i duy trì sự nhấ t quán củ a:

■

●

Dữ liệ u được chia sẻ giữa các process, và quan trọ ng hơn là

●

Các dữ liệ u trong kernel (ví dụ các hàng đợi I/O)

Ví dụ : trường hợp xả y ra preemption khi kernel đang thực thi mộ t lời gọ i hệ thố ng ●

Rấ t nhiề u hệ điề u hành chờ cho các lời gọ i hàm hệ thố ng kế t thúc rồ i mới preemption

Định thời CPU

21

Dispatcher ■

Dispatcher sẽ chuyể n quyề n điề u khiể n CPU về cho process được chọ n bởi bộ đị nh thời ngắ n hạ n

■

Bao gồ m:

■

●

Chuyể n ngữ cả nh (sử dụ ng thông tin ngữ cả nh trong PCB)

●

Chuyể n về user mode

●

Nhả y đế n vị trí thích hợp (chính là program counter trong PCB) trong chương trình ứng dụ ng để quá trình tiế p tụ c thực thi

Công việ c này gây ra phí tổ n ●

Dispatch latency: thời gian dispatcher cầ n từ lúc dừng mộ t process đế n lúc mộ t process khác tiế p tụ c chạ y

Định thời CPU

22

Dispatch latency

Conflict phase: xem p. 171 Định thời CPU

23

First Come First Served (FCFS) (1/5) ■

Hàm lựa chọ n: chọ n process đợi trong hàng đợi ready lâu nhấ t

■

Chế độ quyế t đị nh: nonpreemptive ●

■

Mộ t process sẽ được thực thi cho đế n khi nó block hoặ c kế t thúc

FCFS thường được quả n lý bằ ng mộ t FIFO queue

Định thời CPU

24

First Come First Served (FCFS) (2/5) Process P1

Burst time (ms) 24

P2

3

P3

3

■

Giả sử các process đế n theo thứ tự P1 , P2 , P3

■

Giả n đồ Gantt cho việ c đị nh thời là: P1 0

P2 24

P3 27

■

Thời gian đợi cho P1 = 0, P2 = 24, P3 = 27

■

Thời gian đợi trung bình: (0 + 24 + 27) / 3 = 17 Định thời CPU

30

25

First Come First Served (FCFS) (3/5) ■

Thời gian phụ c vụ (khong duoc dinh nghia) trung bình =

■

Thông năng =

■

Thời gian quay vòng = ●

Kiể m tra lạ i: Thời gian đợi = (thời gian quay vòng − thời gian phụ c vụ − dispatch latency khong biet)

P1 0

P2 24

Định thời CPU

P3 27

30

26

First Come First Served (FCFS) (4/5) ■

Giả sử các process đế n theo thứ tự: P2 , P3 , P1

■

Giả n đồ Gantt cho việ c đị nh thời là: P2 0

P3 3

P1 6

30

■

Thời gian đợi cho P1 = 6, P2 = 0, P3 = 3

■

Thời gian đợi trung bình là: (6 + 0 + 3) / 3 = 3 ●

Tố t hơn rấ t nhiề u so với trường hợp trước

Định thời CPU

27

First Come First Served (FCFS) (5/5) ■

FCFS “không công bằ ng” với các process có CPU burst ngắ n. Các process này phả i chờ trong thời gian dài (so với thời gian mà nó cầ n phụ c vụ ) thì mới được sử dụ ng CPU. Điề u này đồ ng nghĩa với việ c FCFS “ưu tiên” các process thuộ c dạ ng CPU bound.

■

Câu hỏ i: Liệ u có xả y ra trường hợp trì hoãn vô hạ n đị nh (starvation hay indefinite blocking) với giả i thuậ t FCFS?

■

FCFS thường được sử dụ ng trong các hệ thố ng bó (batch system)

Định thời CPU

28

Ví dụ thực tế ■

■

Việ c phụ c vụ khách trong nhà hàng ●

Thực khách sẽ đế n và gọ i món ăn cho mình

●

Mỗ i món ăn cầ n thời gian chuẩ n bị khác nhau

Mụ c tiêu: ●

■

Giả m thời gian đợi trung bình củ a các thực khách

Cách làm nào sẽ phù hợp? ●

Thông thường các nhà hàng sẽ phụ c vụ theo kiể u FCFS (!)

Định thời CPU

29

Shortest Job First (SJF) (1/3) Process

■

Thời điể m đế n

P1

0,0

7

P2

2,0

4

P3

4,0

1

P4

5,0

4

Giả n đồ Gantt khi đị nh thời theo SJF P1 0

■

Burst time (ms)

3

P3 7

P2 8

P4 12

16

Thời gian đợi trung bình = (0 + 6 + 3 + 7)/4 = 4 Định thời CPU

30

Shortest Job First (SJF) (2/3) ■

Thời gian phụ c vụ trung bình =

■

Thông năng =

■

Thời gian quay vòng = ●

Kiể m tra lạ i: Thời gian đợi = (thời gian quay vòng − thời gian phụ c vụ − dispatch latency) P1 0

3

P3 7

P2 8

P4 12

Định thời CPU

16

31

Shortest Job First (SJF) (3/3) ■

Đố i với mỗ i process, cầ n biế t độ dài củ a CPU burst tiế p theo

■

Hàm lựa chọ n: chọ n process có độ dài CPU burst nhỏ nhấ t

■

Chứng minh được: SJF tố i ưu trong việ c giả m thời gian đợi trung bình

■

Vấ n đề : Cầ n phả i ước lượng thời gian cầ n CPU tiế p theo củ a process

■

Giả i pháp cho vấ n đề này?

Định thời CPU

32

Dự đoán thời gian sử dụ ng CPU (1/2) (Thời gian sử dụ ng CPU chính là độ dài củ a CPU burst) ■

Trung bình tấ t cả các CPU burst đo được trong quá khứ

■

Giả thiế t: những CPU burst càng mới càng phả n ánh đúng hành vi củ a process trong tương lai

■

Mộ t kỹ thuậ t thường dùng là sử dụ ng trung bình hàm mũ (exponential averaging) ●

τ

n+1

= α tn + (1 − α )τ

●

τ

n+1

= α tn + (1 − α )α tn−1 +…+ (1 − α )jα tn−j +…+ (1 − α )n+1α τ

●

Nế u chọ n α = ½ thì có nghĩa là trị đo được tn và trị dự đoán τ được xem quan trọ ng như nhau.

n

,

0≤ α ≤ 1

Định thời CPU

0 n

33

Dự đoán thời gian sử dụ ng CPU (2/2) Độ dài CPU burst đo được Độ dài CPU burst dự đoán, với α = ½ và τ 0 = 10

Định thời CPU

34

Shortest Job First (SJF) ■

SJF sử dụ ng ưu tiên ngầ m đị nh: công việ c ngắ n nhấ t được ưu tiên trước ●

Những công việ c thuộ c loạ i I/O bound thường có CPU burst ngắ n

■

Process có thời gian thực thi dài có thể bị trì hoãn vô hạ n đị nh nế u các process có thời gian thực thi ngắ n liên tụ c vào

■

Không thích hợp cho môi trường time-sharing khi không dùng preemption ●

Các CPU bound process có “độ ưu tiên” thấ p, nhưng mộ t process không thực hiệ n I/O có thể độ c chiế m CPU nế u nó là process đầ u tiên vào hệ thố ng

Định thời CPU

35

Shortest Remaining Time First (SRTF) (1/4) ■

Chế độ quyế t đị nh củ a SJF: nonpreemptive

■

Phiên bả n preemptive củ a SJF: ●

Nế u mộ t process mới đế n mà có độ dài CPU burst nhỏ hơn thời gian cầ n CPU còn lạ i củ a process đang thực thi, thì thực hiệ n preempt process đang thực thi

●

Cách làm này còn được gọ i là Shortest-Remaining-Time-First (SRTF)

Định thời CPU

36

Shortest Remaining Time First (2/4) (Ví dụ giố ng vd cho SJF) Thời điể m đế n 0,0

Process P1

■

P2

2,0

4

P3

4,0

1

P4

5,0

4

Giả n đồ Gantt khi đị nh thời theo SRTF P1 0

■

Burst time (ms) 7

P2 2

P3 4

P2 5

P4 7

P1 11

16

Thời gian đợi trung bình = (9 + 1 + 0 + 2) / 4 = 3 ●

Tố t hơn giả i thuậ t SJF Định thời CPU

37

Shortest Remaining Time First (3/4) ■

Thời gian phụ c vụ trung bình =

■

Thông năng =

■

Thời gian quay vòng = ●

Kiể m tra lạ i: Thời gian đợi = (thời gian quay vòng − thời gian phụ c vụ − dispatch latency)

P1 0

P2 2

P3 4

P2 5

P4 7

Định thời CPU

P1 11

16

38

Shortest Remaining Time First (4/4) ■

Tránh trường hợp process có thời gian thực thi dài độ c chiế m CPU

■

Cầ n phả i quả n lý thời gian thực thi còn lạ i củ a các process

■

Có thời gian quay vòng tố t hơn SJF

■

Process có thời gian thực thi ngắ n có độ ưu tiên cao

Định thời CPU

39

Priority Scheduling ■

Mỗ i process sẽ được gán mộ t độ ưu tiên

■

CPU sẽ được cấ p cho process có độ ưu tiên cao nhấ t

■

Đị nh thời sử dụ ng độ ưu tiên có thể là ●

Preemptive hoặ c

●

Nonpreemptive

Định thời CPU

40

Gán độ ưu tiên ■

SJF là mộ t giả i thuậ t đị nh thời sử dụ ng độ ưu tiên mà độ ưu tiên là thời-gian-sử-dụ ng-CPU-dự-đoán

■

Gán độ ưu tiên còn dựa vào: ●

Yêu cầ u về bộ nhớ

●

Số lượng file được mở

●

Tỉ lệ thời gian dùng cho I/O trên thời gian sử dụ ng CPU

●

Các yêu cầ u bên ngoài như: số tiề n người dùng trả khi thực thi công việ c

Định thời CPU

41

Priority Scheduling ■

Vấ n đề : trì hoãn vô hạ n đị nh – process có độ ưu tiên thấ p có thể không bao giờ được thực thi

■

Giả i pháp: aging – độ ưu tiên củ a process sẽ tăng theo thời gian

Định thời CPU

42

Round Robin (RR) (1/4) ■

Hàm lựa chọ n: giố ng FCFS

1

2

8

3

7

4 6

5

Định thời CPU

43

Round Robin (2/4) ■

Chế độ quyế t đị nh: preemptive ●

Khoả ng thời gian tố i đa cho phép (thường 10 - 100 ms) được đả m bả o bằ ng việ c sử dụ ng timer interrupt

●

Process đang chạ y khi hế t thời gian sẽ được chuyể n về cuố i củ a hàng đợi ready

Định thời CPU

44

Round Robin (3/4) Process P1

■ ■

P2

17

P3

68

P4

24

Quantum time = 20 ms Giả n đồ Gantt: P1 0

■

Burst time (ms) 53

P2 20

37

P3

P4 57

P1 77

P3 97 117

P4

P1

P3

P3

121 134 154 162

Thường có thời gian quay vòng cao hơn SJF, nhưng lạ i có thời gian đáp ứng tố t hơn

Định thời CPU

45

Round Robin (4/4) ■

Thời gian phụ c vụ trung bình =

■

Thông năng =

■

Thời gian quay vòng = ●

Kiể m tra lạ i: Thời gian đợi = (thời gian quay vòng − thời gian phụ c vụ − dispatch latency)

P1 0

P2 20

37

P3

P4 57

P1 77

P3

P4

P1

P3

P3

97 117 121 134 154 162

Định thời CPU

46

Quantum time và chuyể n ngữ cả nh ■

Quantum time càng nhỏ thì càng có nhiề u lầ n chuyể n ngữ cả nh (context switch) trong khi thực thi. Số lần ngưng/tiếp tục quá trình

Định thời CPU

47

Quantum time và thời gian quay vòng ■

Thời gian quay vòng trung bình không chắ c sẽ được cả i thiệ n khi quantum lớn

Định thời CPU

48

Quantum time cho Round Robin* ■

Khi thực hiệ n process switch thì OS sẽ sử dụ ng CPU chứ không phả i process củ a người dùng (OS overhead ): ●

Dừng thực thi, lưu tấ t cả thông tin, nạ p thông tin củ a process sắ p thực thi

■

Performance tùy thuộ c vào kích thước củ a quantum time (còn gọ i là time slice), và hàm phụ thuộ c này không đơn giả n

■

Time slice ngắ n thì đáp ứng nhanh ●

■

Vấ n đề : có nhiề u chuyể n ngữ cả nh. Phí tổ n sẽ cao.

Time slice dài hơn thì throughput tố t hơn (do giả m phí tổ n OS overhead) nhưng thời gian đáp ứng lớn ●

Nế u time slice quá lớn, RR trở thành FCFS.

Định thời CPU

49

Quantum time cho Round Robin ■

Quantum time và thời gian cho process switch: ●

Nế u quantum time = 20 ms và thời gian cho process switch = 5 ms, như vậ y phí tổ n OS overhead chiế m 5/25 = 20%

●

Nế u quantum = 500 ms, thì phí tổ n chỉ còn ≈ 1%  Nhưng

nế u có nhiề u người sử dụ ng trên hệ thố ng và thuộ c loạ i interactive thì sẽ thấ y đáp ứng rấ t chậ m

■

Tùy thuộ c vào tậ p công việ c mà lựa chọ n quantum time

■

Time slice nên lớn trong tương quan so sánh với thời gian cho process switch ●

Ví dụ với 4.3 BSD UNIX, time slice là 1 giây

Định thời CPU

50

Round Robin ■

Nế u có n process trong hàng đợi ready, và quantum time là q, như vậ y mỗ i process sẽ lấ y 1/n thời gian CPU theo từng khố i có kích thước lớn nhấ t là q ●

■

Sẽ không có process nào chờ lâu hơn (n - 1)q đơn vị thời gian

RR sử dụ ng mộ t giả thiế t ngầ m là tấ t cả các process đề u có tầ m quan trọ ng ngang nhau ●

Không thể sử dụ ng RR nế u muố n các process khác nhau có độ ưu tiên khác nhau

Định thời CPU

51

Round Robin: nhược điể m ■

Các process dạ ng CPU-bound vẫ n còn được “ưu tiên” ●

Ví dụ :  Mộ t

I/O-bound process sử dụ ng CPU trong thời gian ngắ n hơn quantum time và bị blocked để đợi I/O. Và

 Mộ t

CPU-bound process chạ y hế t time slice và liên tụ c quay trở về hàng đợi ready queue, thường ở trước các I/O bound process đã bị blocked.

Định thời CPU

52

Multilevel Queue Scheduling (1/3) Trường hợp các quá trình có thể được phân thành nhóm, ví dụ : interactive và batch. ■

■

Hàng đợi ready sẽ được chia thành nhiề u hàng đợi riêng rẽ . Ví dụ : ●

foreground (cho công việ c cầ n giao tiế p)

●

background (cho công việ c dạ ng bó)

Mỗ i hàng đợi sẽ có giả i thuậ t đị nh thời riêng. Ví dụ : ●

foreground: dùng RR

●

background: dùng FCFS

Định thời CPU

53

Multilevel Queue Scheduling (2/3) ■

Đị nh thời cầ n phả i thực hiệ n giữa các hàng đợi với nhau ●

Theo cách cố đị nh (fixed priority scheduling) – ví dụ : phụ c vụ tấ t cả các process củ a foreground rồ i mới đế n background  Có

●

khả năng xả y ra trì hoãn vô hạ n đị nh (starvation)

Chia thời gian (time slice) – mỗ i hàng đợi sẽ được lấ y mộ t khoả ng sử dụ ng CPU nhấ t đị nh để đị nh thời cho các process củ a mình. Ví dụ :  80%

cho foreground (dùng RR)

 20%

cho background (dùng FCFS)

Định thời CPU

54

Multilevel Queue Scheduling (3/3) ■

Ví dụ phân nhóm các quá trình Độ ưu tiên cao nhất System Processes Interactive Processes Batch Processes Student Processes Độ ưu tiên thấp nhất

Định thời CPU

55

Multilevel Feedback Queue (1/3) ■

Trong hệ thố ng Multilevel Feedback Queue, bộ đị nh thời có thể di chuyể n process giữa các queue tùy theo đặ c tính củ a nó.



Ví dụ : ●

Nế u mộ t process sử dụ ng CPU quá lâu, nó sẽ bị di chuyể n sang mộ t hàng đợi có độ ưu tiên thấ p hơn

●

Nế u mộ t process chờ qua lâu trong mộ t hàng đợi có độ ưu tiên thấ p, nó sẽ được di chuyể n lên hàng đợi có độ ưu tiên cao hơn (aging, giúp tránh starvation)

Định thời CPU

56

Multilevel Feedback Queue (2/3) ■

■

Ví dụ : Có 3 hàng đợi ● Q0 , dùng RR với quantum 8 ms ●

Q1 , dùng RR với quantum 16 ms

●

Q2 , dùng FCFS

Giả i thuậ t ●

Công việ c mới sẽ vào hàng đợi Q0. Khi đế n lượt mình, công việ c sẽ được mộ t khoả ng thời gian là 8 milli giây. Nế u không kế t thúc được trong 8 milli giây, công việ c sẽ được đưa xuố ng hàng đợi Q1

●

Tạ i Q1, tương tự công việ c sau khi chờ sẽ được cho mộ t khoả ng thời gian thực thi là 16 milli giây. Nế u hế t thời gian này vẫ n chưa kế t thúc sẽ bị chuyể n sang Q2 Định thời CPU

57

Multilevel Feedback Queue (3/3) ■

Multilevel Feedback Queue được xác đị nh bởi các thông số ●

Có bao nhiêu hàng đợi?

●

Với mỗ i queue sử dụ ng giả i thuậ t đị nh thời nào?

●

Xác đị nh thời điể m thăng cấ p cho mộ t process?

●

Làm sao để xác đị nh thời điể m giáng cấ p mộ t process?

●

Xác đị nh được hàng đợi nào process sẽ vào khi process đó cầ n thực thi?

Định thời CPU

58

Policy và Mechanism * Rấ t quan trọ ng trong đị nh thời và phân phố i tài nguyên ■

Policy ●

■

Mechanism ●

■

Điề u gì (what) nên (hay cầ n) làm Làm sao (how) để làm điề u đó

Ví dụ ●

Policy: tấ t cả người dùng cầ n được công bằ ng

●

Mechanism: sử dụ ng round robin

●

Policy: công việ c được trả tiề n cao có độ ưu tiên cao

●

Mechanism: sử dụ ng các giả i thuậ t preemptive Định thời CPU

59

Đị nh thời trên hệ thố ng multiprocessor * ■

Nế u có nhiề u CPU thì có thể thực hiệ n việ c chia tả i ●

■

Phức tạ p hơn so với đị nh thời trên mộ t processor

Làm sao để chia tả i? ●

Asymmetric multiprocessor  Mộ t

master processor sẽ thực hiệ n đị nh thời cho tấ t cả các processor còn lạ i

●

Symmetric multiprocessor (SMP)  Hoặ c

mỗ i processor có mộ t hàng đợi ready riêng và bộ đị nh thời riêng

 Hoặ c

có mộ t hàng đợi ready chung cho tấ t cả processors

–

Mộ t processor được chọ n làm scheduler cho các processor khác

–

Hoặ c mỗ i processor có bộ đị nh thời riêng và tự chọ n process từ hàng đợi chung để thực thi Định thời CPU

60

Processor affinity * ■

Khi mộ t process chạ y trên mộ t processor, có mộ t số dữ liệ u được cache trên bộ nhớ cache củ a processor

■

Khi mộ t process được di dời sang mộ t processor khác ●

Cache củ a processor mới phả i được repopulated

●

Cache củ a processor cũ phả i được invalidated

⇒ vấ n đề phí tổ n

Định thời CPU

61

Cân bằ ng tả i * ■

Mộ t processor có quá nhiề u tả i, trong khi những bộ xử lý khác thì lạ i rả nh

■

Cân bằ ng tả i sử dụ ng:

■

●

Push migration: mộ t task đặ c biệ t sẽ đị nh kỳ kiể m tra tả i trên tấ t cả các processors và công việ c sẽ được đẩ y đế n processor rả nh

●

Pull migration: processor rả nh sẽ lấ y công việ c từ processor đang bậ n

●

Mộ t số hệ thố ng (ví dụ Linux) hiệ n thực cả hai

Cầ n phả i có sự cân bằ ng giữa load balancing và processor affinity

Định thời CPU

62

Phương pháp đánh giá giả i thuậ t đị nh thời CPU * ■

■

■

■

Deterministic modeling ● Đị nh nghĩa trước mộ t tậ p tả i (workload) và khả o sát performance củ a các giả i thuậ t trên cùng tậ p tả i đó ● Không tổ ng quát Queuing models ● Sử dụ ng queuing theory để phân tích giả i thuậ t ● Sử dụ ng nhiề u giả thiế t để phụ c vụ việ c phân tích ● Không sát thực tế Mô phỏ ng (simulation) ● Xây dựng bộ mô phỏ ng và chạ y thử  Với tậ p tả i giả (thường được sinh tự độ ng)  Hoặ c tậ p tả i được ghi nhậ n từ thực tế Hiệ n thực ● Viế t mã củ a giả i thuậ t và test nó trong hệ thố ng thực Định thời CPU

63

Tổ ng kế t ■

Sự thực thi củ a mộ t process

■

Bộ đị nh thời chọ n mộ t process từ hàng đợi ready ●

■

Các tiêu chí đị nh thời (thường xung độ t nhau) ●

■

FCFS, SJF, Priority, RR, Multilevel Feedback Queue,…

Đị nh thời trên hệ thố ng multiprocessor (đọ c thêm) ●

■

Độ lợi CPU, thời gian chờ, thời gian đáp ứng, thông năng,…

Các giả i thuậ t đị nh thời ●

■

Dispatcher thực hiệ n switching

Processor affinity và cân bằ ng tả i

Phương pháp đánh giá giả i thuậ t đị nh thời CPU (đọ c thêm) ●

Mô hình, mô phỏ ng, hiệ n thực

Định thời CPU

64

Mộ t số vấ n đề bàn thêm ■

Cách làm tố t nhấ t là adaptive

■

Để thực hiệ n tố i ưu hoàn toàn thì cầ n phả i tiên đoán đúng tương lai (!)

■

●

Thực tế thì đa số các giả i thuậ t lạ i cho kế t quả gán độ ưu tiên cao nhấ t cho các process có nhu cầ u ít nhấ t

●

Vấ n đề đị nh thời có xu hướng chuyể n sang “tweak and see”

Các tiêu chí nào nên tố i ưu? ●

Có rấ t nhiề u, tùy vào hệ thố ng, ngữ cả nh mà chọ n lựa

Định thời CPU

65

Bài tậ p 1 Process P1

Burst Time 10

P2

29

P3

3

P4

7

P5

12

■

Tấ t cả đề u đế n ở thời điể m 0

■

Xét các giả i thuậ t FCFS, SFJ, và RR với quantum time = 10

■

Giả i thuậ t nào cho ●

thời gian đợi trung bình nhỏ nhấ t?

●

thông năng cao nhấ t?

●

thời gian quay vòng trung bình củ a process nhỏ nhấ t? Định thời CPU

66

Bài tậ p 2 ■

FCFS: thời gian đợi trung bình là 28 milli giây, hãy tính các thông số khác

Định thời CPU

67

Bài tậ p 3 ■

SJF (nonpreemptive): thời gian đợi trung bình là 13 milli giây, hãy tính các thông số khác

Định thời CPU

68

Bài tậ p 4 ■

RR: thời gian đợi trung bình là 23 milli giây, hãy tính các thông số khác

Định thời CPU

69