Bài giảng Hệ điều hành: Chương 4 - Trường ĐH Công nghệ thông tin

Đ ị n h t h ờ i C P U l à h o ạ t đ ộ n g q u a n t r ọ n g c ủ a t h à n h p h ầ n q u ả n l ý t i ế n t r ì n h v à c ó ả n h h ư ở n g r ấ t l ớ n đ ế n h i ệ u s u ấ t m á y t í n h c ũ n g n h ư t r ả i n g h i ệ m c ủ a n g ư ờ i d ù n g . Tr o n g c h ư ơ n g n à y, n g ư ờ i h ọ c đ ư ợ c t r ì n h b à y v ề m ụ c đ í c h v à c á c t i ê u c h u ẩ n đ ị n h t h ờ i , c ũ n g n h ư c á c c h i ế n l ư ợ c đ ị n h t h ờ i C P U c ơ b ả n .

Trình bày: ... Trình bày: ...

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

1

MỤC TIÊU

1. Biết được các khái niệm cơ bản về định thời

2. Biết được các tiêu chuẩn định thời CPU

3. Hiểu được các giải thuật định thời

4. Vận dụng các giải thuật định thời để làm bài tập

và mô phỏng

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

2

NỘI DUNG

1. Các khái niệm cơ bản về định thời

2. Các loại định thời

3. Các tiêu chuẩn định thời CPU

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

• First-Come, First-Served (FCFS) • Shortest Job First (SJF) • Shortest Remaining Time First (SRTF) • Priority Scheduling

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

3

CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỊNH THỜI

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

4

• Trong các hệ thống đa nhiệm (multitasking), đơn vị xử lý

• Cho phép thực thi đồng thời nhiều chương trình để làm tăng hiệu suất hệ

thống (Cho phép nhiều chương trình được nạp vào bộ nhớ).

• Tại mỗi thời điểm, chỉ có một tiến trình được thực thi.

• Cần phải giải quyết vấn đề phân chia, lựa chọn tiến trình thực thi để đạt được

hiệu quả cao nhất.

• Cần có những phương pháp chọn lựa phù hợp.

Định thời là chiến lược lựa chọn tiến trình phù hợp để được thực thi sao cho đạt được hiệu quả cao nhất.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

5

Chu kỳ CPU-I/O

• Service time là thời gian một

tiến trình cần CPU trong một chu kỳ

CPU - I/O (hay còn gọi là

).

• Tiến trình có service time

lớn được gọi là các

(CPU-bound process).

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

6

Tiến trình hướng CPU (CPU-bound)

#include

int main() {

• Tiến trình yêu cầu thời gian thực thi trên

long long start = 1, end = 1000000,

CPU nhiều.

total = 0;

• Thời gian hoàn thành chương trình phụ

for (long long i = start; i <= end; i++){

thuộc vào tốc độ thực thi của CPU.

total += i;

}

printf("Sum of numbers from %lld to %lld is %lld\n", start, end, total);

return 0;

}

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

7

#include

int main(){

Tiến trình hướng I/O (I/O-bound)

FILE *fp;

char filename[] = "example.txt";

int total = 0, ch;

• Tiến trình yêu cầu thời gian trên ngoại vi nhiều

thực thi

fp = fopen(filename, "r"); if (fp == NULL){

hơn.

printf("Failed to open file %s\n", filename); return 1;

• Thời gian hoàn thành chương trình phụ thuộc chu kỳ đợi cho

} while ((ch = fgetc(fp)) != EOF){

các thao tác nhập/xuất.

total++;

} fclose(fp); printf("Total number of characters in file %s is %d\n", filename, total); return 0;

}

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

8

CÁC LOẠI ĐỊNH THỜI

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

9

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

10

CÁC LOẠI ĐỊNH THỜI

2.1. Định thời dài (Long-term scheduling)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

11

▪ Xác định chương trình nào

được chấp nhận nạp vào hệ

thống

để

thực

thi.

 Điều khiển mức độ đa

chương của hệ thống.

▪ Định thời dài thường cố gắng

duy trì xen lẫn giữa tiến trình

hướng

CPU

(CPU-bound

process) và tiến trình hướng I/O

(I/O-bound process).

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

12

CÁC LOẠI ĐỊNH THỜI

2.2. Định thời vừa (Medium-term scheduling)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

13

▪ Định thời vừa quyết định tiến trình

nào được đưa vào (swap in) và

đưa ra khỏi

(swap out) bộ nhớ

chính trong quá trình thực thi của

hệ thống.

▪ Được thực hiện bởi

thành phần

quản lý bộ nhớ (và sẽ được thảo

luận ở chương về quản lý bộ nhớ).

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

14

CÁC LOẠI ĐỊNH THỜI

2.3. Định thời ngắn (Short-term scheduling)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

15

▪ Còn được gọi

là

).

(

▪ Xác định tiến trình nào trong

(

) sẽ

được chiếm CPU để thực thi kế

tiếp.

▪ Đối với hệ thống hỗ trợ nhân đa

luồng (multithreaded kernel), việc

định thời CPU là do OS chọn

kernel thread được chiếm CPU.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

16

• Bộ định thời ngắn được gọi

khi có một

trong các sự

kiện/interrupt sau xảy ra:

• 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)

• Tín hiệu đồng bộ hóa (Sẽ trao đổi

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

17

sau ở Chương 5)

Bộ định thời ngắn (Short-term scheduler

• Bộ định thời sẽ chuyển quyền điều khiển CPU về cho tiến trình được chọn.

• Quá trình chuyển đổi bao gồm:

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

• Chuyển chế độ người dùng.

• Nhảy đến vị trí thích hợp trong chương trình ứng dụng để khởi động lại chương trình (sử dụng

thông tin địa chỉ tại program counter trong PCB).

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

: thời gian mà bộ định thời dừng một tiến trình và khởi động một tiến trình

khác.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

18

CÁC TIÊU CHUẨN ĐỊNH THỜI CPU

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

19

Hướng người dùng (user-oriented)

(

): khoảng thời gian từ lúc tiến trình gửi

yêu cầu thực thi đến khi yêu cầu được đáp ứng lần đầu tiên (trong các hệ

thống time-sharing, interactive system) →

(

): khoảng thời gian từ lúc một tiến

trình được nạp vào hệ thống đến khi tiến trình đó kết thúc →

(

): tổng thời gian một tiến trình đợi trong ready

queue →

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

20

Cách xác định các thông số định thời

F

R

P

P

P

0

t

Giả sử :

• Quá trình thực thi một tiến trình P gồm nhiều

Gọi 𝑅, 𝐹, và 𝑊 lần lượt là thời gian đáp ứng, thời gian hoàn thành và thời gian đợi của tiến trình P. Khi đó:

phần.

• 𝑟 là thời điểm xuất hiện của P trong hệ thống

(Arrival Time/Release Time).

𝑹 = 𝒕𝟎 − 𝒓 𝑭 = 𝒇 − 𝒓

•

𝑾 = 𝒇 − 𝒓 − 𝑬

𝑡(cid:2868) là thời điểm P được thực thi lần đầu tiên. • 𝑓 là thời điểm tiến trình P hoàn thành việc thực

thi (Finishing Time).

Trong đó 𝑬 là thời gian yêu cầu của P để thực thi trên CPU (hay CPU Burst)

𝑬 = 𝑬𝟏 + 𝑬𝟐 + 𝑬𝟑

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

21

Hướng hệ thống (System oriented)

(

): định thời sao cho CPU

càng bận càng tốt →

(

): tất cả tiến trình phải được

(

): số tiến trình hoàn tất công việc trong một đơn

vị thời gian →

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

22

CÁC GIẢI THUẬT ĐỊNH THỜI

4.1. Giải thuật định thời

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

23

Một giải thuật định thời thông thường bao gồm hai yếu tố:

(

): mô tả cách thức (căn cứ)

để chọn tiến trình nào trong ready queue được thực thi (Các

hàm chọn lựa thường được xây dựng dựa trên độ ưu tiên, yêu

cầu về tài nguyên, đặc điểm thực thi của tiến trình,…).

(

): quyết định thời điểm thực

hiện hàm chọn lựa để định thời.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

24

Các chế độ quyết định

Có hai chế độ quyết định thường được áp dụng:

• Khi ở trạng thái running, tiến trình sẽ thực thi cho đến khi kết thúc hoặc bị ngắt

(blocked) do yêu cầu I/O.

• Tiến trình đang thực thi (ở trạng thái running) có thể bị ngắt giữa chừng và chuyển

về trạng thái ready.

• Chi phí cao hơn chế độ không trưng dụng nhưng đánh đổi lại bằng thời gian đáp

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

25

ứng tốt hơn vì không có trường hợp một tiến trình độc chiếm CPU quá lâu.

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

 (1) và (4) không cần lựa chọn loại định • Hàm chọn lựa được thực thi vào các thời

thời, (2) và (3) cần. điểm sau:

• Việc thực thi hàm chọn lựa trong trường (1) Có tiến trình chuyển từ trạng thái

hợp (1) và (4) không phụ thuộc vào loại running sang waiting.

giải thuật định thời và thường áp dụng (2) Có tiến trình chuyển từ trạng thái

chế độ không trưng dụng. running sang ready.

• Ngược lại, trường hợp (2) và (3) phụ (3) Có tiến trình chuyển từ trạng thái

thuộc vào loại giải thuật định thời và waiting, new sang ready.

thường áp dụng chế độ trưng dụng. (4) Kết thúc thực thi của một tiến trình.

 Thực hiện theo cơ chế nào khó hơn?

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

26

Tại sao?

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

• First-Come, First-Served (FCFS)

• Shortest Job First (SJF)

• Shortest Remaining Time First (SRTF)

• Round-Robin (RR)

• Priority Scheduling

• Highest Response Ratio Next (HRRN)

• Multilevel Queue

• Multilevel Feedback Queue

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

27

CÁC GIẢI THUẬT ĐỊNH THỜI

4.2. First-Come, First-Served (FCFS)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

28

• Hàm lựa chọn:

• Tiến trình nào yêu cầu CPU trước sẽ được cấp phát CPU trước.

• Chế độ quyết định: không trưng dụng (non-preemptive).

• Hiện thực: sử dụng hàng đợi FIFO (FIFO queues)

• Tiến trình sẽ thực thi đến khi kết thúc hoặc bị blocked do I/O.

• Tiến trình mới xuất hiện được thêm vào cuối hàng đợi.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

29

• Tiến trình được lựa chọn để xử lý được lấy từ đầu của hạng đợi.

Process Arrival Time Burst Time

P1 0 12

P2 2 7

P3 5 8

P4 9 3

Giản đồ Gantt

P1

P2

P3

P4

P5

P5 12 6

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

30

0 12 19 27 30 36

• Thời gian đáp ứng:

Process Arrival Time Burst Time

• P1 = 0, P2 = 10, P3 = 14,

P1 0 12

P2 2 7

P4 = 18, P5 = 18

P3 5 8

• Thời gian đáp ứng trung bình:

P4 9 3

(0 + 10 + 14 + 18 + 18)/5 = 12

Giản đồ Gantt

P5 12 6

P1 P2 P3 P4 P5

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

31

0 12 19 27 30 36

• Thời gian chờ:

Process Arrival Time Burst Time

• P1 = 0, P2 = 10, P3 = 14,

P1 0 12

P2 2 7

P4 = 18, P5 = 18

P3 5 8

• Thời gian chờ trung bình:

P4 9 3

(0 + 10 + 14 + 18 + 18)/5 = 12

Giản đồ Gantt

P5 12 6

P1 P2 P3 P4 P5

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

32

0 12 19 27 30 36

• Thời gian hoàn thành:

Process Arrival Time Burst Time

• P1 = 12, P2 = 17, P3 = 22,

P1 0 12

P2 2 7

P4 = 21, P5 = 24

P3 5 8

• Thời gian hoàn thành trung bình:

P4 9 3

(12 + 17 + 22 + 21 + 24)/5 = 19.2

Giản đồ Gantt

P5 12 6

P1 P2 P3 P4 P5

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

33

0 12 19 27 30 36

CÁC GIẢI THUẬT ĐỊNH THỜI

4.3. Shortest-Job-First (SJF)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

34

• Hàm chọn lựa: tiến trình có thời gian yêu cầu thực thi (CPU

burst) ngắn nhất sẽ được chọn.

▪ Khi CPU trống, HĐH sẽ chọn tiến trình có CPU Burst ngắn nhất để

được thực thi tiếp theo.

▪ Giải thuật này sử dụng chiều dài thời gian thực thi của tiến trình làm

căn cứ để chọn lựa.

• SJF có thể được hiện thực với cả hai chiến lược: trưng dụng

và không trưng dụng.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

35

• SJF ở chế độ không trưng dụng:

• Hàm chọn lựa được thực thi khi CPU trống.

• Khi tiến trình được cấp CPU thì sẽ thực thi cho đến khi kết thúc.

• Khi một tiến trình kết thúc, một tiến trình khác có thời gian thực thi ngắn

nhất sẽ được chọn.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

36

Process Arrival Time Burst Time

• Thời gian đáp ứng:

P1 0 12

• P1 = 0, P2 = 19, P3 = 23, P4 = 3,

P2 2 7

P5 = 3

P3 5 8

• Thời gian đáp ứng trung bình:

P4 9 3

(0 + 19 + 23 + 3 + 3)/5 = 9.6

Giản đồ Gantt

P5 12 6

P1 P4 P5 P2 P3

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

37

0 12 15 21 28 36

Process Arrival Time Burst Time

• Thời gian chờ:

P1 0 12

• P1 = 0, P2 = 19, P3 = 23, P4 = 3,

P2 2 7

P5 = 3

P3 5 8

• Thời

gian

chờ trung

bình:

P4 9 3

(0 + 19 + 23 + 3 + 3)/5 = 9.6

Giản đồ Gantt

P5 12 6

P1 P4 P5 P2 P3

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

38

0 12 15 21 28 36

• Thời gian hoàn thành:

Process Arrival Time Burst Time

• P1 = 12, P2 = 26, P3 = 31, P4 =

P1 0 12

P2 2 7

6, P5 = 9

P3 5 8

• Thời gian hoàn thành trung bình:

P4 9 3

(12 + 26 + 31 + 6 + 9)/5 = 16.8

Giản đồ Gantt

P5 12 6

P1 P4 P5 P2 P3

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

39

0 12 15 21 28 36

• Hàm chọn lựa được thực thi khi có tiến trình mới xuất hiện hoặc có tiến trình kết thúc.

• Khi có tiến trình mới xuất hiện với CPU-burst nhỏ hơn thời gian yêu cầu còn lại

(remaining time) của tiến trình đang thực thi, tiến trình mới sẽ được chọn và tiến

trình đang thực thi sẽ bị dừng lại.

• Khi một tiến trình kết thúc, một tiến trình khác có CPU-burst (hoặc thời gian yêu cầu

còn lại) nhỏ nhất sẽ được chọn tiếp theo.

• SJF ở chế độ trưng dụng còn được gọi là

SJF là tối ưu về thời gian đợi: có thời gian chờ đợi trung bình ngắn nhất với một tập tiến trình cho trước.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

40

.

SJF trưng dụng

• Thời gian đáp ứng:

Process Arrival Time Burst Time

• P1 = 0, P2 = 0, P3 = 13, P4 = 0,

P1 0 12

P2 2 7

P5 = 0

P3 5 8

• Thời gian đáp ứng trung bình:

P4 9 3

(0 + 0 + 13 + 0 + 0)/5 = 2.6

Giản đồ Gantt

P5 12 6

P1 P2 P4 P5 P3 P1

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

41

0 2 9 12 18 26 36

SJF trưng dụng

• Thời gian chờ:

Process Arrival Time Burst Time

• P1 = 24, P2 = 0, P3 = 13, P4 = 0,

P1 0 12

P2 2 7

P5 = 0

P3 5 8

• Thời

gian

chờ trung

bình:

P4 9 3

(24 + 0 + 13 + 0 + 0)/5 = 7.4

Giản đồ Gantt

P5 12 6

P1 P2 P4 P5 P3 P1

0 2 18 9 26 36

42

12 Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

SJF trưng dụng

• Thời gian hoàn thành:

Process Arrival Time Burst Time

• P1 = 36, P2 = 7, P3 = 21, P4 = 3,

P1 0 12

P2 2 7

P5 = 6

P3 5 8

• Thời gian hoàn thành trung bình:

P4 9 3

(36 + 7 + 21 + 3 + 6)/5 = 14.6

Giản đồ Gantt

P5 12 6

P1 P2 P4 P5 P3 P1

0 2 18 9 26 36

43

12 Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

Nhận xét về giải thuật SJF

• Có thể xảy ra tình trạng “đói” tài nguyên ( ) đối với các tiến trình có CPU-burst

lớn nếu có nhiều tiến trình với CPU-burst nhỏ (liên tục) xuất hiện trong hệ thống.

• Cơ chế không trưng dụng không phù hợp cho hệ thống time sharing (interactive).

• Giải thuật SJF ngầm định rằng độ ưu tiên được xác định dựa theo độ dài CPU-burst.

 Các tiến trình hướng CPU (CPU-bound) có độ ưu tiên thấp hơn so với tiến trình hướng

I/O (I/O-bound).

 Tuy nhiên, khi một tiến trình hướng CPU được thực thi thì nó độc chiếm CPU cho đến khi

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

44

kết thúc.

Nhận xét về giải thuật SJF

• Ưu điểm: SJF tối ưu trong việc giảm thời gian đợi trung bình.

• Hạn chế: Cần phải ước lượng thời gian cần CPU tiếp theo của tiến trình.

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

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

45

Nhận xét về giải thuật SJF

• 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ứ.

• Nhưng thông thường những CPU Burst càng mới càng phản ánh đúng hành trình của tiến trình

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):

𝜏(cid:3041)(cid:2878)(cid:2869) = 𝛼𝑡(cid:3041) + 1 − 𝛼 𝜏(cid:3041), 0 ≤ 𝛼 ≤ 1

𝜏(cid:3041)(cid:2878)(cid:2869) = 𝛼𝑡(cid:3041) + 1 − 𝛼 𝛼𝑡(cid:3041)(cid:2879)(cid:2869) + ⋯ + 1 − 𝛼 (cid:3037)𝛼𝑡(cid:3041)(cid:2879)(cid:3037) + ⋯ + 1 − 𝛼 (cid:3041)(cid:2878)(cid:2869)𝜏(cid:2868), 0 ≤ 𝛼 ≤ 1

Nếu chọn 𝛼 = ½ thì có nghĩa là trị đo được 𝑡(cid:3041) và trị dự đoán 𝜏(cid:3041) được xem quan trọng

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

46

như nhau.

Dự đoán thời gian sử dụng CPU

Độ dài CPU burst đo được

Độ dài CPU Burst dự đoán với

và (cid:2868) = 10

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

47

CÁC GIẢI THUẬT ĐỊNH THỜI

4.4. Định thời theo độ ưu tiên - Priority Scheduling

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

48

• Mỗi tiến trình sẽ được gán một độ ưu tiên (thường biểu diễn bởi một con

số).

• CPU sẽ được cấp cho tiến trình có độ ưu tiên cao nhất theo các giá trị số

được gán (có thể theo thứ tự tăng dần hay giảm dần).

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

• Preemptive

• Non-preemptive

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

49

Cách gán độ ưu tiên cho tiến trình

• SJF là một giải thuật định thời sử dụng độ ưu tiên được xác định dựa vào

thời gian sử dụng CPU (giá trị được ước lượng).

• Ngoài ra, việc gán độ ưu tiên còn có thể 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.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

50

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

Hạn chế của định thời theo độ ưu tiên

• Vấn đề trì hoãn vô hạn định: tiến trình có độ ưu tiên thấp có thể không

bao giờ được thực thi (do có những tiến trình độ ưu tiên cao hơn liên tục

xuất hiện).

• Giải pháp: làm mới (aging) – độ ưu tiên của tiến trình sẽ tăng theo thời

gian.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

51

• Thời gian chờ?

Process Priority

Arrival Time Burst Time

• Thời gian đáp ứng?

P1 0 12 2

• Thời gian hoàn thành?

P2 2 7 1

P3 5 8 5

P4 9 3 4

Giản đồ Gantt (Non-preemptive)

P5 12 6 3

P1 P2 P5 P4 P3

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

52

0 12 19 25 28 36

• Các khái niệm cơ bản về định thời

• Các bộ định thời

• Các tiêu chuẩn định thời CPU

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

• First-Come, First-Served (FCFS)

• Shortest Job First (SJF)

• Shortest Remaining Time First (SRTF)

• Priority Scheduling

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

53

• Sử dụng các giải thuật FCFS, SJF, SRTF, Priority để tính các

giá trị thời gian đợi, thời gian đáp ứng và thời gian hoàn thành

trung bình

Process

Arrival Time

Burst Time

Priority

P1

0

4

3

P2

5

1

2

P3

3

8

1

P4

10

2

4

P5

8

7

3

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

54

• Sử dụng các giải thuật FCFS, SJF, SRTF, Priority để tính các

giá trị thời gian đợi, thời gian đáp ứng và thời gian hoàn thành

trung bình

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

55

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

56

Đ ị n h t h ờ i C P U l à h o ạ t đ ộ n g q u a n t r ọ n g c ủ a t h à n h p h ầ n q u ả n l ý t i ế n t r ì n h v à c ó ả n h h ư ở n g r ấ t l ớ n đ ế n h i ệ u s u ấ t m á y t í n h c ũ n g n h ư t r ả i n g h i ệ m c ủ a n g ư ờ i d ù n g . Tr o n g c h ư ơ n g n à y, n g ư ờ i h ọ c đ ư ợ c t r ì n h b à y v ề m ụ c đ í c h v à c á c t i ê u c h u ẩ n đ ị n h t h ờ i , c ũ n g n h ư c á c c h i ế n l ư ợ c đ ị n h t h ờ i C P U c ơ b ả n .

Trình bày: ... Trình bày: ...

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

1

NỘI DUNG

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

• Round Robin

• Highest Response Ratio Next (HRRN)

• Multilevel Queue

• Multilevel Feedback Queue

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

2

CÁC GIẢI THUẬT ĐỊNH THỜI

4.5. Round Robin (RR)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

3

• Mỗi tiến trình nhận được một đơn vị thời gian CPU (

,

) để thực thi. Thông thường khoảng thời gian này nhỏ, từ 10-100

ms.

• Sau khoảng thời gian đó, tiến trình bị đoạt quyền và trở về cuối ready

queue.

• Gọi

là số lượng tiến trình trong ready queue và

là khoảng thời gian

đơn vị mà CPU được cấp phát cho tiến trình (quantum time), khi đó,

không có tiến trình nào phải chờ đợi quá

đơn vị thời gian.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

4

Process Burst Time

• Thời gian đáp ứng:

Arrival Time

• P1 = 0, P2 = 2, P3 = 7, P4 = 10,

P1 0 12

P5 = 10

P2 2 7

P3 5 8

• Thời gian đáp ứng trung bình: 5.8

P4 9 3

Giản đồ Gantt (q = 4)

P5 12 6

P1 P2 P1 P3 P2 P4 P5 P1 P3 P5

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

5

0 4 8 12 16 19 22 26 30 34 36

Process Burst Time

• Thời gian chờ:

Arrival Time

• P1 = 4 + 14, P2 = 2 + 8, P3 = 7 +

P1 0 12

14, P4 = 10, P5 = 10 + 8

P2 2 7

P3 5 8

• Thời gian chờ trung bình: 15.4

P4 9 3

Giản đồ Gantt (q = 4)

P5 12 6

P1 P2 P1 P3 P2 P4 P5 P1 P3 P5

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

6

0 4 8 12 16 19 22 26 30 34 36

Process Burst Time

• Thời gian hoàn thành:

Arrival Time

• P1 = 40, P2 = 17, P3 = 29, P4 =

P1 0 12

13, P5 = 24

P2 2 7

P3 5 8

• Thời gian hoàn thành trung bình:

P4 9 3

22.6

Giản đồ Gantt (q = 4)

P5 12 6

P1 P2 P1 P3 P2 P4 P5 P1 P3 P5

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

7

0 4 8 12 16 19 22 26 30 34 36

Nhận xét về giải thuật Round Robin

• Nếu q lớn: RR => FCFS. • Nếu q nhỏ: phải tốn chi phí chuyển ngữ cảnh giữa các tiến trình => q không nên

quá nhỏ.

• Ưu tiên tiến trình hướng CPU (CPU-bound process). • RR sử dụng một giả thiết ngầm là tất cả các tiến trình đều có tầm quan

trọng ngang nhau.

• Ưu điểm: Thời gian đáp ứng nhỏ. • Hạn chế: Thời gian chờ đợi trung bình và thời gian hoàn thành trung bình của

giải thuật RR thường khá lớn.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

8

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

Context switch

Process time = 10

Quantum

0

12

10

6

1

10

6

1

9

1

2

3

4

5

6

7

8

9

10

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

9

Quantum time và Thời gian hoàn thành

• Thời gian hoàn thành trung

bình không chắc sẽ được

cải thiện khi quantum lớn

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

10

Quantum time và Thời gian đáp ứng

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

11

Quantum time và hiệu suất hệ thống

• Hiệu suất hệ thống: tùy thuộc vào kích

• Khi

thực hiện chuyển ngữ

thước của

cảnh,

sẽ sử

dụng CPU, không phải

• Nếu quantum time ngắn: thời gian đáp ứng

.

nhanh, nhưng phí tổn hệ thống lớn do số lần

• Phí

tổn hệ

thống

(OS

chuyển ngữ cảnh tang.

Overhead): thời gian OS sử

• Nếu quantum time dài: hiệu quả sử dụng

dụng CPU để thực hiện

CPU tốt hơn, nhưng thời gian đáp ứng cũng

chuyển ngữ cảnh.

lớn.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

12

.

Cách chọn quantum time

• Quantum time và thời gian cho chuyển ngữ cảnh:

▪ Nếu quantum time là 20 ms và thời gian chuyển ngữ cảnh là 5 ms, như vậy

OS overhead chiếm 5/25 = 20%.

▪ Nếu quantum là 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.

▪ Quantum time nên lớn trong tương quan so sánh với thời gian cho chuyển

ngữ cảnh.

• Ví dụ với 4.3 BSD UNIX, quantum time là 1s.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

13

CÁC GIẢI THUẬT ĐỊNH THỜI

4.6. Highest Response Ratio Next (HRRN)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

14

• Chọn tiến trình kế tiếp có giá trị

lớn nhất.

• Các tiến trình ngắn được ưu tiên hơn (vì

nhỏ).

• Câu hỏi thảo luận:

• So sánh với cơ chế Aging?

• Ưu điểm và hạn chế của hướng tiếp cận này?

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

15

CÁC GIẢI THUẬT ĐỊNH THỜI

4.7. Multilevel Queue

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

16

• Ready queue được chia thành nhiều hàng đợi riêng biệt theo

một số tiêu chuẩn sau:

▪ Đặc điểm và yêu cầu định thời của tiến trình

▪ Phân loại tiến trình: Foreground (interactive) và background,…

• Tiến trình được gán cố định vào một hàng đợi, mỗi hàng đợi sử

dụng giải thuật định thời riêng.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

17

Việc định thời giữa các hạng đợi

• Hệ điều hành cần phải định thời cho các hàng đợi:

: phục vụ từ hàng đợi có độ ưu tiên cao đến

thâp  Có thể phát sinh vấn đề đói tài nguyên (

).

: mỗi hàng đợi được nhận một khoảng thời gian chiếm CPU

và phân phối cho các tiến trình trong hàng đợi khoảng thời gian đó. Ví

dụ: 80% cho hàng đợi foreground định thời bằng RR và 20% cho hàng

đợi background định thời bằng giải thuật FCFS.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

18

Ví dụ phân chia hạng đợi và tiến trình

Độ ưu tiên cao nhất

System Processes

Interactive Processes

Batch Processes

Student Processes

Độ ưu tiên thấp nhất

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

19

Hệ chế của Multilevel Queue

• Tiến trình không thể chuyển từ hàng đợi này sang hàng đợi

khác

 Có thể làm giảm hiệu suất hệ thống trong trường hợp một hàng đợi có

nhiều tiến trình trong khi các hàng đợi khác lại trống.

 Khắc phục bằng cơ chế feedback: cho phép tiến trình di chuyển một

cách thích hợp giữa các hàng đợi khác nhau.

 Giải thuật: Multilevel Feedback Queue

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

20

CÁC GIẢI THUẬT ĐỊNH THỜI

4.8. Multilevel Feedback Queue

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

21

▪ Phân loại tiến trình dựa trên các đặc tính về

.

▪ Sử dụng chế độ

(preemptive).

▪ Sau một khoảng thời gian nào đó, các tiến trình hướng I/O và tiến trình

interactive sẽ ở các hàng đợi có độ ưu tiên cao hơn còn các tiến trình

hướng CPU sẽ ở các hàng đợi có độ ưu tiên thấp hơn.

▪ Một tiến trình đã chờ quá lâu ở một hàng đợi có độ ưu tiên thấp có thể

được chuyển đến hàng đợi có độ ưu tiên cao hơn (cơ chế aging).

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

22

Ví dụ về Multilevel Feedback Queue

• 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

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

23

Các vấn đề với Multilevel Feedback Queue

• Định thời dùng multilevel

feedback queue đòi hỏi phải giải

quyết các vấn đề sau:

▪ Số lượng hàng đợi bao nhiêu là thích hợp?

▪ Dùng giải thuật định thời nào ở mỗi hàng đợi?

▪ Làm sao để xác định thời điểm cần chuyển một tiến trình đến hàng đợi

cao hơn hoặc thấp hơn?

▪ Khi tiến trình yêu cầu được xử lý thì đưa vào hàng đợi nào là hợp lý

nhất?

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

24

CÁC GIẢI THUẬT ĐỊNH THỜI

4.9. So sánh các giải thuật

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

25

• Giải thuật định thời nào là tốt nhất?

• Câu trả lời phụ thuộc các yếu tố sau:

▪ Tần suất tải việc (System workload)

▪ Sự hỗ trợ của phần cứng đối với dispatcher

▪ Sự tương quan về trọng số của các tiêu chuẩn định thời như response

time, hiệu suất CPU, throughput,…

▪ Phương pháp định lượng so sánh

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

26

• Tại sao phải định thời? Nêu các bộ định thời và mô tả về

chúng?

• Các tiêu chuẩn định thời CPU?

• Có bao nhiêu giải thuật định thời? Kể tên?

• Mô tả và nêu ưu điểm, nhược điểm của từng giải thuật định

thời? FCFS, SJF, SRTF, RR, Priority Scheduling, HRRN, MQ,

MFQ.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

27

Sử dụng các giải thuật FCFS, SJF, SRTF, Priority -Pre, RR (10) để tính các giá trị

thời gian đợi, thời gian đáp ứng và thời gian hoàn thành trung bình và vẽ giản đồ

Gantt.

Với RR, điều gì sẽ xảy ra khi P5 vào tại thời điểm P1 vừa hết quantum time?

Process

Arrival

Burst

Priority

P1

0

20

20

P2

25

25

30

P3

20

25

15

P4

35

15

35

P5

10

35

5

P6

15

50

10

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

28

Cho 5 tiến trình với thời gian vào và thời gian cần CPU tương ứng như bảng sau:

Process

Arrival

Burst

P1

0

10

P2

2

29

P3

4

3

P4

5

7

P5

7

12

Vẽ giản đồ Gantt và tính thời gian đợi trung bình, thời gian đáp ứng trung bình và

thời gian hoàn thành trung bình cho các giải thuật sau:

a. FCFS

b. SJF preemptive

c. RR với quantum time = 10 Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

29

Xét tập các tiến trình sau (với thời gian vào hệ thống, thời gian yêu cầu CPU và độ

ưu tiên kèm theo) :

Process

Arrival 0

Burst 10

Priority 3

P1

1

3

2

P2

2

2

1

P3

3

1

2

P4

4

5

4

P5

Vẽ giản đồ Gantt và tính thời gian đợi trung bình, thời gian đáp ứng trung bình và

thời gian hoàn thành trung bình cho các giải thuật sau:

a. SJF Preemptive

b. RR với quantum time = 2

c. Điều phối theo độ ưu tiên độc quyền (độ ưu tiên 1 > 2 > ...) Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

30

Vẽ giản đồ Gantt và tính thời gian đợi trung bình, thời gian đáp ứng trung bình và

thời gian hoàn thành trung bình cho các giải thuật sau:

a. FCFS, SJF

b. RR với quantum time = 10

Process

Burst Time

Arrival Time

P1

10

5

P2

29

2

P3

3

0

P4

7

1

P5

12

7

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

31

Cho 4 tiến trình với thời gian vào hệ thống (arrival time) và burst time tương ứng

như sau:

Process

Arrival Time

CPU Burst Time

P1

0

12

P2

2

7

P3

3

5

P4

5

9

Vẽ giản đồ Gantt và tính thời gian đợi trung bình, thời gian đáp ứng trung bình và

thời gian hoàn thành trung bình cho các giải thuật sau:

a. Shortest Remaining Time First (SRTF)

b. Round Robin (RR) với quantum = 4

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

32

Cho 5 tiến trình P1, P2, P3, P4, P5 với thời gian vào Ready List và thời gian cần

CPU tương tứng như bảng sau:

Process

Arrival Time

CPU Burst Time

P1

0

8

P2

2

19

P3

4

3

P4

5

6

P5

7

12

Vẽ giản đồ Gantt và tính thời gian đợi trung bình, thời gian đáp ứng trung bình và

thời gian hoàn thành trung bình cho các giải thuật sau:

a. FCFS

b. SJF preemptive

c. RR với quantum time = 6

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

33

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

34

Đ ịn h t hời C P U l à h oạt đ ộn g q u a n t rọn g của t h à n h p hần q uản lý t iến t r ì n h v à c ó ản h hư ởn g rất lớn đ ến h iệu s uất m á y t í n h cũn g n hư t rải n g h iệm của n gư ời d ù n g . Tr o n g c hư ơn g n à y, n gư ời học đ ư ợc t r ì n h b à y về mục đí c h v à c á c t i ê u c h uẩn đ ịn h t hời , cũn g n hư c á c c h iến lư ợc đ ịn h t hời C P U cơ bản .

Trình bày: ... Trình bày: ...

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

1

NỘI DUNG

5. Định thời tiểu trình (Thread scheduling)

6. Định thời đa bộ xử lý (Multiple-processor scheduling)

7. Định thời theo thời gian thực (Real-time CPU scheduling)

8. Định thời trên một số hệ điều hành

• Linux • Windows • Solaris

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

2

ĐỊNH THỜI TIỂU TRÌNH

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

05.

3

• Trên các hệ điều hành hiện đại có hỗ trợ tiểu trình,

,

không phải tiến trình.

• Có sự phân biệt giữa tiểu trình người dùng và tiểu trình hạt nhân khi định thời:

được định thời thông qua

các thư viện quản lý tiểu trình:

• Phạm vi định thời là bên trong tiến trình

được định thời trên tất cả các CPU khả dụng. Phạm vi định thời là toàn hệ thống (system- contention scope - SCS).

(process-contention scope - PCS).

• Thường được thực hiện bằng cách

thiết

lập độ ưu tiên (bởi người

lập

trình).

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

4

ĐỊNH THỜI ĐA BỘ XỬ LÝ

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

06.

5

• Định thời CPU trở nên phức tạp hơn khi hệ thống có nhiều bộ xử lý.

• Khái niệm đa bộ xử lý có thể là một trong các dạng sau:

• CPU có nhiều lõi vật lý (Multicore CPUs)

• CPU có nhiều luồng xử lý trên một lõi (Multithreaded cores)

• Hệ thống NUMA (non-uniform memory access)

• Đa xử lý không đồng nhất (Heterogeneous multiprocessing)

• Có hai cách tiếp cận phổ biến:

(asymmetric

multiprocessing) và

(symmetric multiprocessing - SMP).

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

6

ĐỊNH THỜI ĐA BỘ XỬ LÝ

6.1. Đa xử lý bất đối xứng

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

06.

7

• Tất cả các thao tác lập lịch, xử lý I/O được thực hiện bởi một

bộ xử lý – master server.

• Các bộ xử lý còn lại chỉ thực thi user code.

• Ưu điểm: đơn giản, chỉ một bộ xử lý truy xuất dữ liệu hệ thống,

không cần chia sẻ dữ liệu.

• Nhược điểm: master server có thể bị nghẽn cổ chai

(bottleneck), làm giảm hiệu năng của hệ thống.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

8

ĐỊNH THỜI ĐA BỘ XỬ LÝ

6.2. Đa xử lý đối xứng

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

06.

9

• Mỗi bộ xử lý tự định thời cho chính nó.

• Hai hướng tiếp cận để tổ chức các tiểu trình cần định thời:

▪ Tất cả tiểu trình nằm trong cùng một ready queue (a)

▪ Mỗi bộ xử lý tự tổ chức hàng đợi của riêng nó (b)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

10

• Tất cả tiểu trình nằm trong cùng một ready queue:

• Tiểu trình có thể không được bộ xử lý nào chọn ?

• Xuất hiện vùng tranh chấp: Nhiều bộ xử lý có thể chọn định thời cùng

một tiểu trình => Cần có cơ chế kiểm tra và khóa (lock) việc truy xuất

tiểu trình => Hiệu năng hệ thống có thể giảm do nghẽn cổ chai.

• Mỗi bộ xử lý tự tổ chức hàng đợi của riêng nó:

• Hiệu năng không bị ảnh hưởng do các vấn đề khi dùng chung một

hàng đợi => Hướng tiếp cận phổ biến trên các hệ thống SMP.

• Vấn đề: Khối lượng công việc của các bộ xử lý khác nhau?

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

11

Cân bằng tải (Load balancing)

• Một bộ xử lý có quá nhiều tải, trong khi các bộ xử lý khác rỗi => Cần đảm

bảo các bộ xử lý đều được sử dụng hiệu quả.

• Mục tiêu của cân bằng tải là phân phối khối lượng công việc (workload)

đều nhau cho các CPU.

• Có hai cách cân bằng tải:

▪ Push migration: Một tác vụ đặc biệt sẽ kiểm tra định kỳ tải của từng CPU. Nếu tình

trạng quá tải xuất hiện, hệ thống sẽ di chuyển (đẩy) tác vụ từ CPU bị quá tải sang các

CPU khác.

▪ Pull migration: CPU rỗi kéo (pull) tác vụ đang chờ từ CPU bận.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

12

Processor affinity

• Khi một tác vụ chạy trên một bộ xử lý, bộ nhớ đệm (cache) của bộ xử lý

đó lưu trữ dữ liệu được truy xuất bởi tác vụ => tác vụ có tính liên kết với

bộ xử lý (processor affinity).

• Cân bằng tải sẽ ảnh hưởng đến processor affinity, cụ thể là khi một tác vụ

được dời sang bộ xử lý khác:

• Cache của bộ xử lý mới phải nạp lại (repopulate)

• Cache của bộ xử lý cũ phải được giải phóng (invalidate)

à Phí tổn

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

13

Processor affinity

• Có 2 dạng liên kết:

• Liên kết mềm (Soft affinity): Hệ thống sẽ cố giữ tác vụ chỉ chạy trên

bộ xử lý đó (nhưng không đảm bảo).

• Liên kết cứng (Hard affinity): Cho phép tiến trình chọn một tập các bộ

xử lý mà nó có thể chạy trên đó.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

14

Processor affinity

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

15

ĐỊNH THỜI THEO THỜI GIAN THỰC (ĐỌC THÊM)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

07.

16

• Có nhiều thách thức do yêu cầu về tính chất thời gian thực.

• Có 2 dạng hệ thống thời gian thực:

• Soft real-time systems: Các tác vụ quan trọng sẽ được cấp độ ưu

tiên lớn nhất, nhưng không đảm bảo bất cứ điều gì khác.

• Hard real-time systems: Tác vụ phải hoàn thành trong deadline của

nó.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

17

Định thời theo thời gian thực dựa trên độ ưu tiên

• Hệ thống thời gian thực phải phản hồi ngay lập tức yêu cầu CPU của một

tiến trình => Bộ định thời phải hỗ trợ định thời theo độ ưu tiên với chế độ

trưng dụng.

• Tiến trình có thêm một đặc trưng mới: tính chu kỳ - yêu cầu CPU trong một

khoảng thời gian cố định.

• Khi một tiến trình có chu kỳ yêu cầu CPU, nó có thời gian xử lý C, thời gian

deadline d (thời gian nó sẽ được phục vụ bởi CPU) và thời gian chu kỳ T.

• 0 ≤ C ≤ d ≤ T

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

18

Mô hình tác vụ trọng thời gian thực

Periodic tasks

Aperiodic tasks

Sporadic tasks

Self-Study

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

19

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

• Tác vụ chu kỳ - Periodic Tasks

• Tác vụ phi chu kỳ - Aperiodic Task

• Rate Monotonic - RM

• Total Bandwidth Server – TBS

• Earliest Deadline First - EDF

• Enhanced Virtual Release Advancing TBS

• Constant Bandwidth Server

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

20

Định thời Rate Monotonic

• Độ ưu tiên được gán dựa trên nghịch đảo của chu kỳ => Chu kỳ ngắn thì

độ ưu tiên cao và ngược lại.

• Tần suất của tác vụ là 1/p.

• P1 được gán độ ưu tiên cao hơn P2.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

21

Định thời EDF

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

22

Định thời Total Bandwidth Server (TBS)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

23

• Global Scheduling

• Partition Scheduling

• Partition EDF

• Semi-Partition Scheduling

• • • •

Global EDF PFAIR – Proportionate Fairness RUN – Reduce to Uniprocessor Local Assignment Algorithm (Duy D. et. al)

• Semi Partition Reservation

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

24

ĐỊNH THỜI TRÊN MỘT SỐ HỆ ĐIỀU HÀNH

8.1. Định thời trên Linux

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

08.

25

• Nhân Linux 2.5 trở về trước sử dụng các phiên bản định thời UNIX tiêu

chuẩn.

• Không hỗ trợ tốt các hệ thống nhiều bộ xử lý.

• Hiệu năng kém nếu có số lượng lớn các tiến trình trong hệ thống.

• Nhân Linux 2.5 sử dụng bộ định thời O(1):

• Chạy với thời gian hằng số.

• Định thời theo độ ưu tiên với chế độ trưng dụng.

• Có hai khoảng ưu tiên: time-sharing và real-time.

• Giá trị số nhỏ hơn biểu diễn độ ưu tiên lớn hơn.

• Hoạt động tốt với các hệ thống SMP nhưng đáp ứng kém với các tiến trình interactive.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

26

Bộ định thời CFS

• Nhân Linux từ 2.6.23 sử dụng bộ định thời CFS (Completely

Fair Scheduler)

• Định thời theo lớp:

• Mỗi lớp được gán một độ ưu tiên cụ thể.

• Bộ định thời chọn tác vụ có độ ưu tiên cao nhất trong lớp có độ ưu tiên cao nhất.

• Thời gian sử dụng CPU của mỗi tác vụ không dựa trên quantum time cố định mà

dựa trên tỷ lệ giờ CPU.

• Nhân Linux cài đặt sẵn 2 lớp: default và real-time. Các lớp khác có thể được thêm

vào.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

27

Bộ định thời CFS

• Thời gian sử dụng CPU:

• Được tính dựa trên giá trị nice được gán cho mỗi tác vụ, có giá trị từ -20 đến 19.

• Giá trị thấp hơn có độ ưu tiên cao hơn.

• Target latency – khoảng thời gian mà một tiến trình cần được chạy ít nhất một lần.

• Target latency có thể tăng lên nếu số lượng tiến trình tăng lên.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

28

Bộ định thời CFS

• CFS xác định tác vụ được thực thi kế tiếp qua virtual run time:

• Mỗi tác vụ có giá trị virtual run time riêng, được kết hợp với một hệ số đặc biệt dựa

trên độ ưu tiên.

• Các tiến trình có độ ưu tiên bình thường có virtual run time tương đương với thời gian

chạy thực tế.

• Chọn tiến trình có virtual run time nhỏ nhất để thực thi tiếp.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

29

Bộ định thời Real-time

• Định thời real-time dựa trên tiêu chuẩn POSIX.

• Các tác vụ real-time có độ ưu tiên tĩnh.

• Độ ưu tiên được chia thành 2 phần: real-time (từ 0 đến 99) và

normal (từ 100 đến 139).

• Giá trị nice -20 tương ứng với độ ưu tiên 100, +19 tương ứng

với độ ưu tiên 139.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

30

Định thời trên Android

• Sử dụng bộ định thời của Linux.

• Độ ưu tiên được phân chia theo nhóm của các tiến trình.

• Để thu hồi tài nguyên, Android có thể

hủy (kill) các tiến trình dựa trên độ

ưu tiên của chúng.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

31

ĐỊNH THỜI TRÊN MỘT SỐ HỆ ĐIỀU HÀNH

8.2. Định thời trên Windows

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

08.

32

• Định thời theo độ ưu tiên với chế độ trưng dụng.

• Tác vụ có độ ưu tiên cao nhất luôn được chạy tiếp.

• Tiến trình sẽ được thực thi cho đến khi (1) block bởi system call, (2) hết

quantum time, (3) bị thay thế bởi một tiến trình khác có độ ưu tiên cao

hơn.

• Sử dụng 32 độ ưu tiên, được chia thành 2 lớp: variable (1-15) và real-time

(16-31). Độ ưu tiên 0 dành cho quản lý bộ nhớ.

• Mỗi độ ưu tiên có hàng đợi riêng.

•

Idle thread được chạy nếu không có bất cứ tác vụ nào trong hàng đợi.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

33

• Các hàm thư viện Windows API cung cấp cho tiến trình các lớp

ưu tiên sau:

• REALTIME_PRIORITY_CLASS, HIGH_PRIORITY_CLASS,

ABOVE_NORMAL_PRIORITY_CLASS,NORMAL_PRIORITY_CLASS,

BELOW_NORMAL_PRIORITY_CLASS, IDLE_PRIORITY_CLASS.

• Tiến trình có thể có các độ ưu tiên tương đối sau:

• TIME_CRITICAL, HIGHEST, ABOVE_NORMAL,

,

BELOW_NORMAL, LOWEST, IDLE

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

34

• Lớp ưu tiên và độ ưu tiên tương đối có thể kết hợp để xác định

giá trị ưu tiên.

• Độ ưu tiên cơ sở (lúc khởi tạo) là

bên trong lớp.

• Khi hết quantum, độ ưu tiên có thể giảm nhưng không nhỏ hơn

độ ưu tiên cơ sở.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

35

• Các độ ưu tiên trên Windows

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

36

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

37

• Windows 7 có thêm user-mode scheduling (UMS):

• Ứng dụng tạo và quản lý tiểu trình độc lập với nhân.

• Hiệu quả hơn trong trường hợp có nhiều tiểu trình.

• Định thời UMS được thực hiện với sự hỗ trợ của các thư viện như C++

Concurrent Runtime (ConcRT).

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

38

ĐỊNH THỜI TRÊN MỘT SỐ HỆ ĐIỀU HÀNH

8.3. Định thời trên Solaris (đọc thêm)

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

08.

39

• Định thời theo độ ưu tiên

• Có 6 lớp, mỗi lớp có độ ưu tiên khác nhau và giải thuật định thời khác

nhau:

• Time sharing (TS) – mặc định • Interactive (IA) • Real time (RT)

• System (SYS) • Fair Share (FSS) • Fixed priority (FP)

• Lớp TS sử dụng giải thuật định thời MFQ.

• Độ ưu tiên càng lớn thì time slice càng nhỏ.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

40

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

41

• Bộ định thời chuyển đổi độ ưu tiên theo lớp thành độ ưu tiên

toàn cục:

▪ Tác vụ có độ ưu tiên cao nhất được chọn chạy tiếp.

▪ Tiến trình sẽ được thực thi cho đến khi (1) block, (2) hết quantum time,

(3) bị thay thế bởi một tiến trình khác có độ ưu tiên cao hơn.

▪ Nếu có nhiều tiến trình có cùng độ ưu tiên, bộ định thời sẽ sử dụng

hàng đợi round-robin.

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

42

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

43

• Định thời tiểu trình (Thread scheduling)

• Định thời đa bộ xử lý (Multiple-processor scheduling)

• Định thời theo thời gian thực (Real-time CPU scheduling)

• Định thời trên một số hệ điều hành

▪ Linux

▪ Windows

▪ Solaris

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

44

• Định thời tiểu trình như thế nào?

• Có các cách tiếp cận nào để thực hiện định thời đa bộ xử lý?

Ưu nhược điểm của từng cách tiếp cận?

• Cân bằng tải là gì? Tại sao phải cân bằng tải?

• Định thời theo thời gian thực như thế nào?

• Mô tả CFS?

• Trình bày đặc điểm của bộ định thời trên Windows?

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM

45

Thực hiện bởi Trường Đại học Công nghệ Thông tin, ĐHQG-HCM.

46