Thuật giải điều phối SJF. và FCFS

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

Thuật giải điều phối SJF. và FCFS

Bài gửi  HuynhThanhLy(I12A) on 13/3/2012, 15:28

1. FCFS (First Come First Served): Đến trước có trước
- Được cấp CPU từ đầu dãy đến cuối dãy theo quy tắc FIFO

Ví dụ minh họa:
Giả sử một hệ thống có 5 tiến trình đến vào các thời điểm với các tính chất sau:

a) Vẽ 4 biểu đồ Gantt tương ứng với thuật giải điều phối FCFS 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.

Giải:

Ta có DS các TT:


Biểu đồ Gant như sau:


Để tìm thời gian chờ ta xem hình vẽ điều phối các tiến trình theo FCFS


Vậy:
Thời gian chờ:
W = W1+W2+W3 = 3 + 4 + 13 = 20 ms
Thời gian chờ trung bình = 20/5 = 4ms


Giải thích:
P2: chạy từ giây đầu tiên do đến trước (theo FCFS) nên không phải chờ. Thời gian P2 chạy là 1s (0 ->1)
P5: chạy tiếp theo sau P2, cũng không phải chờ vì P2 đã chạy xong ở giây thứ 1. P5 chạy hết từ 1 -> 5
P3: đến từ giây thứ 2, nhưng lúc đó P5 đang chạy nên phải đứng chờ cho P5 chạy hết ( chờ từ 2->5, W1 = 3). Sau giây thứ 5, P3 mới được chạy và chạy trong 2s ( 5->7)
P1: đến từ giây thứ 3, lúc này P5 cũng đang chạy, sau P5 thì P3 đã được ưu tiên đi trước nên P1 tiếp tục chờ (chờ từ 3->7, W2=4). P3 chạy xong, P1 mới được đi. P1 chạy 10s từ (7 -> 17)
P4 chạy sau cùng do đến chậm nhất (giây thứ 4) và cũng phải chờ cho P3 & P1 chạy xong (chờ từ 4 -> 17, W3=13). Rồi P4 chạy tiếp 17->18.
Finish
Vậy thì Tổng thời gian chờ: W = W1 + W2 + W3 = 3 + 4 + 13 = 20s

HuynhThanhLy(I12A)

Tổng số bài gửi : 42
Join date : 17/02/2012
Age : 28
Đến từ : Quảng Ngãi

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