Bản thảo giáo trình thực hành PLC - Chương 4: Định thời CPU
Luật Little – khi hệ thống trong trạng thái ổn định, số lượng
các tiến trình rời khỏi hàng đợi sẽ bằng với số lượng các tiến
trình vào hàng đợi:
n = x W
• Trong đó:
o n: chiều dài hàng đợi trung bình
o λ: tốc độ đến trung bình cho các tiến trình mới (vd 4 tiến
trình/giây)
o W: thời gian chờ trung bình trong hàng đợi
• VD: trung bình có 7 tiến trình đến mỗi giây, và thông thường
có 14 tiến trình trong hệ thống, thì thời gian chờ trung bình của
mỗi tiến trình là: 2s
44 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1012 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bản thảo giáo trình thực hành PLC - Chương 4: Định thời CPU, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Khoa Công Nghệ Thông Tin & Truyền Thông
Đại học Cần Thơ
Giảng viên: Hà Duy An
9/19/2013 Chương 4: Định thời CPU1
1. Các khái niệm
2. Các giải thuật định thời
3. Định thời trong hệ thống có nhiều bộ xử lý
4. Đánh giá giải thuật
9/19/2013 Chương 4: Định thời CPU2
• Kỹ thuật đa chương giúp việc sử dụng
CPU đạt hiệu quả cao nhất.
• Chu kỳ CPU-I/O
o Sự thực thi của tiến trình bao gồm
nhiều chu kỳ CPU-I/O
o Một chu kỳ CPU-I/O bao gồm chu kỳ
thực thi CPU (CPU burst) và theo sau
bởi chu kỳ chờ đợi vào/ra (I/O burst).
=> Việc phân phối chu kỳ CPU-I/O là một
đặt điểm quan trọng để chọn lựa giải thuật
định thời phù hợp
9/19/2013 Chương 4: Định thời CPU4
9/19/2013 Chương 4: Định thời CPU5
• Bộ định thời CPU hay bộ định thời ngắn kỳ (Short-term
scheduler) chọn một trong các tiến trình trong hàng đợi sẵn sàng và
cấp phát CPU cho nó thực thi
o Hàng đợi có thể được sắp xếp theo nhiều cách
• Quyết định định thời xảy ra khi một tiến trình:
1. Chuyển từ trạng thái đang chạy sang trạng thái chờ đợi
2. Chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng
3. Chuyển từ trạng thái chờ đợi sang sẵn sàng
4. Kết thúc
• Định thời không trưng dụng (nonpreemptive): tiến trình sẽ giữ
CPU và chỉ giải phóng CPU khi nó cần (trường hợp 1 và 4)
• Định thời trưng dụng (preempty): các trường hợp 2 và 3; Vấn đề:
o Tiến trình đang cập nhật dữ liệu chia sẽ chung?
o Tiến trình đang xử lý trong chế độ nhân (kernel mode)?
o Không thể bỏ qua tất cả các ngắt?
9/19/2013 Chương 4: Định thời CPU6
• Bộ điều phối (Dispatcher): Có nhiệm vụ trao quyền điều
khiển CPU cho tiến trình được chọn bởi bộ định thời CPU,
công việc này bao gồm:
o Chuyển ngữ cảnh
o Chuyển sang chế độ người dùng
o Nhảy tới vị trí thích hợp trong chương trình người dùng để khởi
động lại chương trình đó
• Bộ điều phối cần nhanh nhất có thể.
• Độ trễ điều phối (Dispatch Latency): thời gian Dispatcher cần
để ngưng một tiến trình và khởi động một tiến trình khác
9/19/2013 Chương 4: Định thời CPU7
1. Hiệu suất sử dụng CPU: giữ CPU luôn bận nhiều nhất có thể.
2. Thông lượng (Throughput): số lượng tiến trình hoàn thành trên
một đơn vị thời gian.
3. Thời gian xoay vòng (Turnaround time): là khoảng thời gian từ
khi một tiến trình được khởi tạo đến khi nó hoàn thành. Nó là tổng
các khoảng thời gian chờ đợi để đưa vào bộ nhớ, chờ trong hàng
đợi sẵn sàng, thời gian thực thi trên CPU và thực hiện các xử lý
I/O.
4. Thời gian chờ đợi (Waiting time): tổng thời gian trong trong hàng
đợi sẵn sàng (ready queue).
5. Thời gian đáp ứng (Response time): lượng thời gian từ lúc một
yêu cầu được đệ trình cho đến khi tín hiệu trả lời đầu tiên xuất hiện
(dùng cho môi trường chia thời gian).
9/19/2013 Chương 4: Định thời CPU8
• Việc đánh giá giải thuật định thời được kiểm tra thông qua khả
năng tối ưu hóa các tiêu chí đinh thời của nó:
o Hiệu suất sử dụng CPU tối đa
o Thông lượng tối đa
o Thời gian xoay vòng tối thiểu
o Thời gian chờ đợi tối thiểu
o Thời gian đáp ứng tối thiểu
9/19/2013 Chương 4: Định thời CPU9
1. First-Come, First-Served
2. Shortest-Job-First
3. Priority
4. Round-Robin
5. Hàng đợi đa cấp
6. Hàng đợi phản hồi đa cấp
9/19/2013 Chương 4: Định thời CPU11
Tiến Trình TG sử dụng CPU
P1 24
P2 3
P3 3
• Giả sử các tiến trình xuất hiện theo thứ tự P1, P2, P3. Biểu đồ
Gantt cho lịch biểu là:
• Thời gian chờ đợi: P1 = 0; P2 = 24; P3 = 27
• Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17
P1 P2 P3
24 27 300
9/19/2013 Chương 4: Định thời CPU12
• Giả sử các tiến trình xuất hiện theo thứ tự P2, P3, P1. Biểu đồ
Gantt cho lịch biểu là:
• Thời gian chờ đợi: P1= 6; P2 = 0; P3 = 3
• Thời gian chờ đợi trung bình: (6 + 0 + 3)/3 = 3
• Tốt hơn nhiều so với trường hợp trước.
• Tác động nối đuôi: tiến trình ngắn nằm sau tiến trình dài.
• FCFS là giải thuật định thời không trưng dụng, không thích
hợp cho hệ thống chia thời gian.
P1P3P2
63 300
9/19/2013 Chương 4: Định thời CPU13
• Kết hợp với mỗi tiến trình độ dài thời gian mà nó sẽ sử dụng
CPU lần kế tiếp. Khi CPU rãnh, nó sẽ được cấp cho tiến trình
có thời gian sử dụng CPU lần kế tiếp ngắn nhất.
• Có hai cách thức thực hiện giải thuật:
o Không trưng dụng: một khi CPU được giao cho một tiến trình,
nó không thể bị trưng dụng để giao cho tiến trình khác có thời
gian ngắn hơn cho đến khi tiến trình này sử dụng CPU xong.
o Trưng dụng: nếu một tiến trình mới đến có thời gian sử dụng
CPU ngắn hơn thời gian thực thi còn lại của tiến trình đang chạy,
thì ưu tiên giao CPU cho tiến trình mới đến. Cách thức này được
gọi là Shortest-Remaining-Time-First (SRTF).
• SJF là tối ưu – nó tạo ra thời gian chờ đợi trung bình ngắn
nhất.
9/19/2013 Chương 4: Định thời CPU14
Tiến trình TG đến TG sử dụng CPU
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
• SJF (không trưng dụng)
• Thời gian chờ đợi trung bình = (0 + 6 + 3 + 7)/4 = 4
P1 P3 P2
73 160
P4
8 12
9/19/2013 Chương 4: Định thời CPU15
Tiến trình TG đến TG sử dụng CPU
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
• SJF (trưng dụng)
• Thời gian chờ đợi trung bình = (9 + 1 + 0 +2)/4 = 3
• Bài Tập
P1 P3P2
42 110
P4
5 7
P2 P1
16
9/19/2013 Chương 4: Định thời CPU16
• Chỉ có thể ước lượng độ dài – có thể tương tự như lần sử dụng
trước đó.
• Độ dài ước lượng được tính toán dựa trên chiều dài thời gian
sử dụng CPU lần trước đó, sử dụng công thức trung bình mũ:
• Thông thường α = ½
nnn
n
n
t
t
)1(
1
1
:nghóa Ñònh4.
10 , 3.
1n thöù laàn CPU duïng söû gian thôøi löôïng öôùc 2.
n thöùlaàn teáthöïcCPUduïngsöûgianthôøi 1.
9/19/2013 Chương 4: Định thời CPU17
9/19/2013 Chương 4: Định thời CPU18
• α =0
o τn+1 = τn
o Không tính đến thời gian sử dụng CPU gần nhất
• α =1
o τn+1 = tn
o Chỉ tính đến thời gian sử dụng CPU thực gần nhất
• α =1/2, lịch sử quá khứ và gần đây có trọng số tương đương.
• Nếu mở rộng công thức, ta có:
τn+1 = α tn+(1 - α) α tn-1 + +(1 - α )j+1 α tn-j + +(1 - α )n+1τ0
• Vì α và (1- α) nhỏ hơn hay bằng 1, mỗi số hạng tiếp theo có
trọng số nhỏ hơn số hạng trước đó.
9/19/2013 Chương 4: Định thời CPU19
• Một chỉ số ưu tiên được gán cho mỗi tiến trình
• CPU sẽ được cấp cho tiến trình có độ ưu tiên cao nhất, nghĩa
là chỉ số ưu tiên nhỏ nhất (smallest integer ≡ highest priority).
• Có thể trưng dụng hoặc không trưng dụng
• SJF là một trường hợp của định thời ưu tiên, trong đó độ ưu
tiên là thời gian ước tính sử dụng CPU lần kế tiếp.
• Vấn đề đói CPU (starvation): các tiến trình có độ ưu tiên thấp
có khả năng không bao giờ được thực thi.
• Giải pháp: đặt thời hạn (aging) – khi thời gian trôi đi, độ ưu
tiên của tiến trình càng tăng theo.
9/19/2013 Chương 4: Định thời CPU20
ProcessAarri Burst TimeT Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
• Priority scheduling Gantt Chart
• Average waiting time = 8.2 msec
9/19/2013 Chương 4: Định thời CPU21
P2 P3P5
1 180 16
P4
196
P1
• Mỗi tiến trình được CPU phục vụ trong một đơn vị thời gian nhỏ,
gọi là định mức thời gian (time quantum), thường là 10-100
milliseconds.
• Sau khoảng thời gian này, CPU bị trưng dụng và giao cho tiến trình
khác, tiến trình bị ngưng và chuyển vào hàng đợi sẵn sàng.
• Nếu có n tiến trình đang nằm trong hàng đợi sẵn sàng và định mức
thời gian là q, thì mỗi tiến trình sẽ nhận được 1/n tổng thời gian của
CPU, thời gian phục vụ của CPU cho nó tối đa là q. Sẽ không có
tiến trình nào phải chờ đợi quá lượng thời gian là (n-1)q.
• Bộ điếm thời gian (Timer) sẽ phát ra các ngắt (interrupt) sau mỗi
định mức thời gian để định thời cho tiến trình tiếp theo
• Hiệu năng:
o q lớn⇒ FCFS (FIFO)
o q nhỏ⇒ q phải đủ lớn do ta phải quan tâm đến việc chuyển đổi ngữ
cảnh, nếu không, thời gian lãng phí sẽ rất cao.
o q thường 10-100 ms, context switch < 10 μsec
9/19/2013 Chương 4: Định thời CPU22
9/19/2013 Chương 4: Định thời CPU23
9/19/2013 Chương 4: Định thời CPU24
80% of CPU bursts should
be shorter than q
Process TG sử dụng CPU
P1 53
P2 17
P3 68
P4 24
• Biểu đồ Gantt:
• Thông thường, RR có thời gian chờ đợi trung bình lớn hơn
SJF, nhưng đảm bảo thời gian đáp ứng tốt hơn.
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
9/19/2013 Chương 4: Định thời CPU25
• Hàng đợi sẵn sàng được chia thành nhiều hàng đợi, tiến trình được
gán cố định vào một hàng đợi, vd:
o foreground (interactive): cần thời gian đáp ứng nhanh hơn -> ưu tiên
hơn;
o background (batch): có thể đáp ứng chậm hơn -> ít ưu tiên hơn.
• Mỗi hàng đợi có giải thuật lập lịch biểu riêng:
o foreground – RR
o background – FCFS
• Thực hiện định thời giữa các hàng đợi, 2 khả năng:
o Định thời với độ ưu tiên cố định (nghĩa là, phục vụ tất cả tiến trình
trong foreground trước rồi đến background). Có khả năng dẫn đến việc
đói CPU.
o Phân chia thời gian (time slice) – mỗi hàng đợi nhận được một khoảng
thời gian phục vụ nào đó của CPU để định thời cho các tiến trình nằm
trong đó; VD 80% cho foreground với RR và 20% cho background với
FCFS
9/19/2013 Chương 4: Định thời CPU26
9/19/2013 Chương 4: Định thời CPU27
• Một tiến trình có thể di chuyển giữa các hàng đợi khác nhau.
• Cơ chế định thời hạn có thể được cài đặt theo cách:
o Nếu tiến trình dùng quá nhiều thời gian CPU, nó sẽ được di chuyển vào
hàng đợi có độ ưu tiên thấp hơn;
o Nếu tiến trình đã chờ quá lâu trong 1 hàng đợi với độ ưu tiên thấp, nó
sẽ được chuyển sang hàng đợi có độ ưu tiên cao hơn => aging
• Bộ định thời đa cấp có phản hồi được định nghĩa bằng những tham
số sau:
o Số lượng hàng đợi
o Giải thuật định thời cho từng hàng đợi
o Phương thức dùng để quyết định khi nào thì nâng cấp một tiến trình.
o Phương thức dùng để quyết định khi nào thì hạ cấp một tiến trình
o Phương thức dùng để quyết định là nên đặt tiến trình vào hàng đợi nào
khi tiến trình này cần được phục vụ.
9/19/2013 Chương 4: Định thời CPU28
• Có 3 hàng đợi:
o Q0: định mức thời gian là 8
milliseconds
o Q1: định mức thời gian là
16 milliseconds
o Q2: FCFS
• Định thời:
9/19/2013 Chương 4: Định thời CPU29
o Một công việc mới sẽ bước vào Q0 mà ở đó nó sẽ được phục vụ theo
kiểu FCFS. Khi đạt được CPU, công việc sẽ nhận được thời gian 8
milliseconds. Nếu nó không hoàn thành trong vòng 8 milliseconds,
công việc sẽ được chuyển sang Q1.
o Tại Q1 công việc sẽ lại được phục vụ theo kiểu FCFS và nhận được
thêm 16 milliseconds. Nếu nó vẫn chưa hoàn thành, nó sẽ bị tước
CPU và chuyển qua Q2.
• Định thời CPU sẽ phức tạp hơn với nhiều CPU hiện hữu.
• Các bộ xử lý giống nhau trong cùng một hệ thống đa xử lý.
• Việc định thời có thể thực hiện:
o Đa xử lý bất đối xứng (Asymmetric Multiprocessor): chỉ một
CPU truy cập đến các cấu trúc dữ liệu dùng chung => giảm việc
bảo vệ các dữ liệu dùng chung
o Đa xử lý đối xứng (Symmetric Multiprocessor): mỗi CPU tự
định thời từ hàng đợi chung, hay có riêng một hàng đợi cho mỗi
CPU => đang được sử dụng phổ biến ngày nay
• Thực thi một tiến trình trên cùng một bộ xử lý trong suốt tiến
trình thực thi của tiến trình – processor affinity
o Soft affinity
o Hard affinity
9/19/2013 Chương 4: Định thời CPU31
9/19/2013 Chương 4: Định thời CPU32
Note that memory-placement algorithms can also
consider affinity
• Đối với hệ thống SMP cần giữ tải cân bằng giữa các CPU
nhằm nâng cao hiệu quả hoạt động của hệ thống
• Cân bằng tải (load balancing) được thực hiện bằng cách cố
gắng phân phối các công việc cho các CPU bằng nhau:
o Push migration – định kỳ kiểm tra tải trên mỗi CPU, nếu CPU
nào bị quá tải thì "đẩy"bớt công việc cho CPU khác
o Pull migration – các CPU rãnh "kéo" các công việc đang chờ
trên một CPU khác về thực thi
9/19/2013 Chương 4: Định thời CPU33
• Nhiều lõi vi xử lý được đặt trên cùng một bộ xử lý => vi xử lý
đa nhân
• Nhanh hơn và tiêu tốn ít năng lượng hơn
• Hỗ trợ đa luồng trên mỗi nhân
o Một luồng có thể được thực thi trong khi luồng khác đang truy
xuất bộ nhớ.
9/19/2013 Chương 4: Định thời CPU34
9/19/2013 Chương 4: Định thời CPU35
1. Mô hình xác định
2. Mô hình hàng đợi
3. Mô phỏng
4. Cài đặt
• Cách đánh giá và chọn giải thuật thích hợp cho một hệ điều
hành?
• Xác định các tiêu chí, đánh giá giải thuật dựa trên các tiêu chí
đó
• Deterministic modeling – mô hình xác định
o Đánh giá dựa trên sự phân tích
o Dựa vào tải công việc (workload) được xác định trước và tính
toán hiệu năng của mỗi giải thuật.
• Cho các tiến trình đến
vào cùng một thời điểm:
9/19/2013 Chương 4: Định thời CPU37
• Với mỗi giải thuật tính thời gian chờ trung bình
• Đơn giản, nhanh chóng, nhưng yêu cầu phải có các số liệu đầu vào chính
xác, và chỉ đúng cho những dữ liệu đầu vào như đã cho
o FCFS: 28ms
o Non-preemptive SJF: 13ms
o RR: 23ms
9/19/2013 Chương 4: Định thời CPU38
• Xác định sự phân phối các tiến trình đến và chu kỳ CPU-I/O
theo xác xuất, là điều có thể xác định được trong thưc tế.
o Thông thường phân phối theo hàm mũ
o Từ hai phân phối trên ta có thể tính trung bình thông lượng, hiệu
năng tận dụng CPU, thời gian chờ,
• Hệ thống máy tính được mô tả như một mạng các server có
các hàng đợi riêng (CPU là một server với hàng đợi sẵn sàng).
o Biết tốc độ đến và tốc độ phục vụ (dựa vào sự phân bổ chu kỳ
CPU-I/O) => có thể tính khả năng sử dụng, chiều dài hàng đợi
trung bình, thời gian chờ trung bình.
9/19/2013 Chương 4: Định thời CPU39
• Luật Little – khi hệ thống trong trạng thái ổn định, số lượng
các tiến trình rời khỏi hàng đợi sẽ bằng với số lượng các tiến
trình vào hàng đợi:
n = xW
• Trong đó:
o n: chiều dài hàng đợi trung bình
o λ: tốc độ đến trung bình cho các tiến trình mới (vd 4 tiến
trình/giây)
o W: thời gian chờ trung bình trong hàng đợi
• VD: trung bình có 7 tiến trình đến mỗi giây, và thông thường
có 14 tiến trình trong hệ thống, thì thời gian chờ trung bình của
mỗi tiến trình là: 2s
9/19/2013 Chương 4: Định thời CPU40
• Mô hình hàng đợi có độ chính xác giới hạn
• Mô phỏng cho kết quả chính xác hơn:
o Dùng phần mềm mô phỏng hệ thống máy tính
o Clock là một biến
o Khi thực thi mô phỏng, các thống kê hiệu năng của các giải thuật
sẽ được ghi nhận và là cơ sở cho vịêc so sánh các giải thuật.
o Dữ liệu dùng để thực hiện mô phỏng:
• Bộ sinh số ngẫu nhiên theo xác xuất
o Phân phối theo mô hình toán học hay theo kinh nghiệm
• Các sự kiện dược ghi lại trong hệ thống thực
9/19/2013 Chương 4: Định thời CPU41
9/19/2013 Chương 4: Định thời CPU42
• Kể cả mô phỏng cũng cho kết quả giới hạn
• Cài đặt và kiểm tra các giải thuật định thời trên hệ thống thật
sẽ cho độ chính xác cao nhất
o Chi phí cao, rủi ro cao
o Môi trường đa dạng
• Hầu hết các bộ định thời có thể được sửa đổi để phù hợp với
từng hệ thống => kết quả không chính xác trong các tình
huống tổng quát khác.
9/19/2013 Chương 4: Định thời CPU43
Các file đính kèm theo tài liệu này:
- bai_giang_he_dieu_hanh_ha_duy_an_chuong_4_cpu_scheduller_5063.pdf