Thảo luận Bài 6: Bài tập dùng SJFS

Giải Bài tập dùng SJFS có tiếm quyền.

Đề thi Tốt nghiệp (3-2012)

Tại thời điểm 10:
P1 phải nhường cho P2 vì
Thời gian sử dụng cpu của:
P1 còn 17ms
P2 là 15ms
=>P2 sẽ được chạy trước
Tại thời điểm 20:
P2 chạy trước P3 vì thời gian sử dụng của P2 bằng P3
Nhưng do P2 tới trước nên P2 sẽ tiếp tục chạy.
Sau khi chạy xong P2
P3 sẽ chạy trước vì thời gian sử dụng cpu P3 < P1

PhamMinhLuan(102C) đã viết:Tại thời điểm 10:
P1 phải nhường cho P2 vì
Thời gian sử dụng cpu của:
P1 còn 17ms
P2 là 15ms
=>P2 sẽ được chạy trước
Tại thời điểm 20:
P2 chạy trước P3 vì thời gian sử dụng của P2 bằng P3
Nhưng do P2 tới trước nên P2 sẽ tiếp tục chạy.
Sau khi chạy xong P2
P3 sẽ chạy trước vì thời gian sử dụng cpu P3 < P1

Vậy là theo mình nghĩ dựa vào thời điểm đầu và thời gian sử dụng CPU để mình vẽ được biểu đồ Gantt hả.Như bạn giải thích ở trên thì nếu thời gian CPU mà nhỏ hơn cái P tiếp theo thì thực hiện tiếp rồi mới tới cái P kế tiếp đúng không.Nhờ bạn giải thích mình đã hiểu hơn về cái biểu đồ Gantt rồi.

Chứ bữa ở lớp thầy cho chép mấy bài tập xong không hiểu gì hết, cứ thấy P1, P2, P3... cứ thích nằm chỗ nào là nằm mà không hiểu, giờ đã hiểu rồi, thanks nhiều nha.

Mình chưa rõ lắm thuật giải Round Robin & SJFS khác nhau ntn nữa.

Thực hiện điều phối theo chiến lược SJFS không độc quyền cho các tiến trình sau:

Tiến trình	Vào hệ thống	Vào RL	CPU lần 1	I/O lần 1	CPU lần 2	I/O lần 2	CPU lần 3
P1	0	0.5	1	R1(4)	3
P2	1	1.5	6	R2(3)	2	R1(4)	1
P3	1	2.5	4	R2(4)	2
P4	2	2.5	3	R1(3)	1	R1(4)	1

Các tài nguyên được xem như chỉ có duy nhất một thể hiện và việc yêu cầu tài nguyên là độc quyền. Chiến lược điều phối được sử dụng cho tài nguyên là FIFO.

a. Trình bày quá trình điều phối

b. Tính thời gian chờ trung bình cho các tiến trình.

Giải:



Trước khi xem bài giả chú thích một chút cho các bạn:

- Trong đề bài có ghi "SJFS không độc quyền" nghĩa là "SJFS có tiếm quyền"




Thời gian chờ trung bình

Ta có thời gian chờ của:

P1 = 0.5 (ms)

P2 = 0.5 + 12 = 12.5 (ms)

P3 = 8.5 + 2 = 10.5 (ms)

P4 = 0.5 (ms)

=> Thời gian chờ trung bình: (P1 + P2 + P3 + P4)/4 = (0.5 + 12.5 + 10.5 + 0.5)/4 = 6 (ms)

TranQuangHien40 đã viết:Mình chưa rõ lắm thuật giải Round Robin & SJFS khác nhau ntn nữa.

- Mình có hiểu một tí về sự khác nhau của Round Robin vs SJFS, chia sẽ với bạn, mong bạn hiểu hơn, sai sót gì mọi người thông cảm và góp ý với nhé

+ SJFS: thực hiện việc điều phối CPU theo hình thức "ăn xem nồi, ngồi xem hướng" tại các thời điểm nó đều xét xem tiến trình nào cần CPU hơn (tiến trình nào còn cần thời lượng sử dụng CPU ít hơn) thì sẽ ưu tiên cấp CPU cho tiến trình đó.

+ Round Robin: cũng điều phối CPU theo hình thức xoay vòng tiến trình + dùng thêm đối tượng gọi là thời lượng điều phối CPU. Các tiến trình sẽ lần lượt được cấp CPU trong một khoảng thời gian = thời lượng điều phối CPU.

Ví dụ: trong một mâm cơm, người mẹ lấy cơm lần lượt cho mấy đứa con cần cơm, SJFS là khi có những đứa phải đi học sớm bà mẹ sẽ ưu tiên lấy cho nó trước, còn Round Robin thì nó phải chờ cho đến lượt của nó....

Admin
- Nêu ví dụ minh hoạ như trên cho SJFS cũng được, nhưng chưa đủ thuyết phục !
- Ví dụ sau "có vẻ" hay hơn: Người mẹ (CPU Scheduler) ưu tiên lấy cơm cho ai ăn ít thời gian nhất (thường là ăn ít cơm nhất, nhưng không phải lúc nào cũng vậy, vì có người ăn và gắp rất "nhanh").

Thầy có thể cho chúng em thêm ví dụ về bài tập SJFS có tiếm quyền và không có tiếm quyền để cùng thảo luận làm cho thật hiểu về SJFS.Cám ơn Thầy.

Admin
Chỉ cần quan tâm đến Preemptive SJFS. Tìm bài tập và lời giải ngay trên Diễn đàn các khoá !

TranQuangHien40 đã viết:Mình chưa rõ lắm thuật giải Round Robin & SJFS khác nhau ntn nữa.

RR tuân thủ theo quy tắc hàng chờ, ai tới trước thì chạy trước, ai tới sau thi ngồi chờ. Nhưng mõi tiến trình chỉ đước chạy trong một khoảng thời gian nhất định đã được quy định sẵn gọi là Quantum, hết thời gian tự động quay về cuối hàng chờ và chờ tới lượt.

SJFS thì khác một chút, cũng là ai tới trước thì được chạy trước, nhưng lúc đang chạy có tiến trình khác nhảy vào thì nó dừng lại và tiến thực hiện tính toán để quyết đinh ai sẽ là người chạy kế tiêp :
nó tính xem là tiến trình đang chạy có khoảng CPU là bao nhiêu, đã chạy được bao nhiêu, và còn lại bao nhiêu? Tương tự như vậy, nó cũng tính cho các tiến trình khác. Sau đó so sánh với các tiến trình khác, nếu tiến trình nào có khoảng CPU còn lại ít hơn thì nó sẽ cho chạy trước.Nếu các tiến trình có khoảng CPU bằng nhau thì thằng nào tới trước sẽ được chạy trước.

Vài dòng ý kiến đóng góp. Nếu có sai xót mong các bạn thông cảm !

PhamMinhLuan(102C) đã viết:Tại thời điểm 10:
P1 phải nhường cho P2 vì
Thời gian sử dụng cpu của:
P1 còn 17ms
P2 là 15ms
=>P2 sẽ được chạy trước
Tại thời điểm 20:
P2 chạy trước P3 vì thời gian sử dụng của P2 bằng P3
Nhưng do P2 tới trước nên P2 sẽ tiếp tục chạy.
Sau khi chạy xong P2
P3 sẽ chạy trước vì thời gian sử dụng cpu P3 < P1

Cảm ơn bạn. Mình hiểu về bài tập rồi. Mong thầy giảng lại về hai bài tập Round-Robin và SJFS có tiếm quyền.

Thưa Thầy cho em hỏi:
- Trong giải thuật Round-Robin thì tiến trình bị tiếm quyền sẽ được đưa xuống cuối hàng chờ hiện hành.
Vậy, Trong giải thuật SJFS thì tiến trình bị tiếm quyền nó sẽ ở đâu trong khi chờ đợi tiến trình khác chạy ?

Em có thắc mắc như vậy mong Thầy giải đáp giúp em.
Cảm ơn Thầy .

Admin
Cũng đưa vào cuối Ready Queue, nhưng với SJFS, thứ tự trong hàng đợi này không quan trọng !

mình ko hiểu vì sao mà từ 0-5 lại ko có tiến trình nào chạy? 2 bài trog sách đều chạy từ 0 mà

DaoQuangTri38(I12A) đã viết:mình ko hiểu vì sao mà từ 0-5 lại ko có tiến trình nào chạy? 2 bài trog sách đều chạy từ 0 mà

Bởi vì thời điểm đến của tiến trình là 5 mà bạn. Còn những bài chạy bắt đầu từ 0 vì thời điểm đến của tiến trình là 0.

đề bài như sau thưa thầy:
TD TT Khoảng CPU
0 p1 7
2 p2 4
4 p3 1
5 p4 4
Đáp án:
P1 p2 p3 p2 p4 p1
0 2 4 5 7 11 16
thừa thầy, đáp án trên có đúng khống thầy ?nếu đúng thì vì sao không cho p2 chạy hết Khoảng CPU .

Admin
- Vì ở thời điểm 4, P3 xuất hiện với khoảng CPU có 1, trong khi P2 còn 2.
- Nên chú ý trình bày Đề cho Chuẩn và Đẹp !
dạ! em se rút kn lần sau ạ.
nếu như thời 2, p3 lúc này chưa xuất hiện. em se cho p2 chạy ở thời điểm 2 , với khoản cpu là 4.
nghĩa là :......p2........
2 . 6
và kết thúc p2 ở đây được không a. khí đó p3 xuất hiện :.........p3..........
6 . . 7

-- P1-- ---P2-- --P3--- ---P4--- -- P1---
0 -----2 -------6 -----7 ----11 ----16