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

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

Về Đầu Trang

- Similar topics

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