Bài tập tham khảo về điều phối CPU?

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Bài tập tham khảo về điều phối CPU?

Bài gửi  lamtienkhoa(102c) on 28/4/2012, 10:24

Mình có một số bì tập tham khảo về Điều phối CPU (Xin Thầy và các bạn sửa chữa các sai sót) xin post len mọi người cùng tham khảo.
Bài 1 : Giả sử một hệ thống có 5 tiến trình cùng đến vào 1 thời điểm với tính chất sau:
Tiến trình Độ ưu tiên Khoảng CPU (số giây)
P1 3 10
P2 1 1
P3 3 2
P4 4 1
P5 2 5
a) Vẽ 4 biểu đồ Gantt tương ứng với các thuật giải điều phối SJFS (có tiếm quyền) và RRS (với thời lượng = 1).
b) Tính thời gian chờ trung bình của các tiến trình cho mỗi thuật giải.
c) Thuật giải nào tốt nhất về phương diện thời gian chờ trung bình?

Giải đáp: Theo đề bài, các tiến trình có độ ưu tiên (Priority Scheduling- PS ), thì tiến trình nào có độ ưu tiên nhỏ nhất sẽ được chạy trước. Và SJFS là dạng đặc biệt của PS với độ ưu tiên là khoảngCPU kế tiếp.Vậy ta có
biểu đồ 1: Điều phối theo độ ưu tiên:Theo độ ưu tiên và chạy hết khoảng CPU
P2 P5 P3 P1 P4
0 1 6 8 18 19
*Thời gian chờ trung bình: 8 + 0 + 6 + 18 + 1 = 33/5 = 6.6

biểu đồ 2: Điều phối SJFS không tiếm quyền: đến trước phục vụ trước và khoảng CPU ngắn nhất.P2 và P4 đến cùng thời điểm( đề bài) cùng khoảng CPU nhưng P2 ưu tiên. P3 va P5 cùng độ ưu tiên 3, nhưng P3 chạy trước vi khoảng CPU ngắn hơn
P2 P4 P3 P5 P1
0 1 2 4 9
*Thời gian chờ trung bình: 9 + 0 + 2 + 1 + 4 = 16/5 = 1.2

biểu đồ 3: Điều phối SJFS có tiếm quyền: giống như biểu đồ 2, chắc tại P2 và P4 có dạng đặc biệt. ( sai?, đúng?)

biểu đồ 4: Điều phối RSS: Như điều phối kiểu FCFS nhưng cho phép tiếm quyền khi tiến trình đang chạy bị hết thời lượng. (theo đề bài thời lượng 1 giây)

P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19
*thời gian chờ trung bình: (0+4+2+1+1+1) + 1 + (2+3) + 3 + (4+2+1+1+1) = 27/5 = 5.4 (a.Tri sua)
Như vậy: SJFS ngắn nhất = 1.2

Bài 2 : Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:

Tiến trình Thời điểm đến (ms) CPU-Burst (ms)
P1 4 46
P2 30 28
P3 51 33
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phươn án):
a. Thể hiện bằng biểu đồ Gantt (1,0 điểm)
b. Tính thời gian chờ trung bình của các tiến trình (1,0 điểm).

Bài giải:
Nhận xét: p1 chạy hết thời lượng 20ms, nhưng p2 chưa xuất hiện, chạy thêm nửa chừng 10 ( tức thời điểm 30) p2 yêu cầu nhưng vẫn phải chờ p1 chạy hết 20ms, lúc đó p2 mới được chạy.Khi p2 chạy được 11 ms (tức thời điểm 51 ) p3 yêu cầu,nhưng phải chờ p2, nên sắp vào hàng chờ sau p1. p2 xong tới p1 chạy
P1 P1 P2 P1 P3 P2 P3
0 4 24 44 64 70 90 98 111
*Thời gian chờ trung bình: (0+20) + (10+6+20) + (19 + 8 ) = 83/3 = 27.7

Bài 3 :Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:

Tiến trình Thời điểm đến (ms) CPU-Burst (ms)
P0 6 26
P1 17 45
P2 48 29
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phươn án):
a. Thể hiện bằng biểu đồ Gantt (1,0 điểm)
b. Tính thời gian chờ trung bình của các tiến trình (1,0 điểm)
Giải đáp:
P0 P1 P1 P2 P1 P2
0 6 26 46 66 86 91 100
Thời gian chờ trung bình: 0 + (9+20) + (18+5) = 52/3 = 17.3

Có ý kiến khác:

Tiến trình Độ ưu tiên Khoảng CPU (số giây)
P2 1 1
P5 2 5
P1 3 10
P3 3 2
P4 4 1
Biểu đồ 1:
Thứ tự thực hiện các tiến trình theo độ ưu tiên:
P2 P5 P1 P3 P4
0 1 6 17 18 19

Thời gian:
6 + 0 + 17 + 18 + 1 = 42 / 5 = 8.4

lamtienkhoa(102c)

Tổng số bài gửi : 43
Join date : 28/02/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết