Tham khảo cách giải Định thời CPU qua các thuật giải

Cách giải bài tập định thời CPU
Đề toán :


Process__Arrival Time_______Service Time
1___________0________________3
2___________2________________7
3___________4________________3
4___________6________________5
5___________8________________2


*Tiền hành công các móc thời gian lại để bắt đầu tình bước đi

AT(Arival Time)=2+4+6+8=20
ST(Service Time)=3+7+3+5+2=20

Biểu đồ:

|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
0____________5___________10____________15_________ __20

Cách tìm : FCFS (First Come-First Serve)

Cái này không cần phải suy nghĩ nhiều cho mệt.Cái nào đến trước xử lý trước.FCFS này dựa vào khoảng thời gian của Service Time thôi.Như vậy ta có biểu đồ sau :

|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
0_______3_________________10______13__________18__ __20
____P1___________P2___________P3________P4________ P5

Đoạn (0-3) là P1
(3-10) là P2
(10-13) là P3
(13-18) là P4
(18-20) là P5 :smiles (54):

Cách tìm : SJF (Sortest Job First)

Cái này bắt đầu việc so sánh giữa AT và ST rồi đó .CÁch giải là cái nào thời gian xử lý ngắn hơn được quyền xử lý trước thôi.Dựa vào dâu để biết thời gian ngắn hơn ???

Ta có :

Process__Arrival Time_______Service Time
1___________0________________3
2___________2________________7

Như vậy Process 1 thời gian từ 0-3=3
2 // 2-7=5 ->>Process 1 ngắn hơn nên được quyền xử lý trước, nhưng không ưu tiên

Bắt đầu vào cách tính : Ờ đây chúng ta chỉ đi được từng đoạn một trong biểu đồ thời gian thôi :

*Process 1 (P1) sẽ đi một bước , sau khi đi xong nó sẽ so sánh với Process kế tiềp là Process 2 (P2) >> vẫn chưa đủ cho P2 vào nên nó đi tiếp bước thứ 2.Lúc này P2 đã được phép vào >Nhưng ở đây nó sẽ so sánh tiếp thời gian nào ngắn hơn giữa P1 và P2 .Ta thấy P1 có thời gian ngắn hơn (giải thích ở trên) nên nó đai tiếp bước thứ 3.Vậy là P1 đã xử lý xong.

*Process 2 (P2) : P2 được quyền đi tiếp bước 4 lúc này P3 được vào nhưng do không có quyền ưu tiên nên P2 đi hết các các còn lại cùa nó.Vậy là tiền trình đã đi được 10 bước.Lúc này thì tất cả các Process đều được vào rồi >> nó sẽ so sánh xem thời gian của P nào có thời gian ngắn nhất nó sẽ thực hiện trước .Như vậy các bạn sẽ thấy rằng 2, 3, 5 .Các tiền trình được phép đi tiếp theo là P5, P3 , P4

Biểu đồ :

|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
0_______3________________10____12______15_________ __20

(0-3) : P1
(3-10) : P2
(10-12)5
(12-15)3
(15-20)4

Xong !!!:smiles:


Cách tìm : SRTF (Sortest Remaining Time First)

Cách tìm này cũng giống như tìm SJF nhưng ở đây chúng ta chú ý một chút là thời gian ngắn xử lý trước có ưu tiên.:smiles (148):


Process__Arrival Time_______Service Time
1___________0________________3
2___________2________________7
3___________4________________3
4___________6________________5
5___________8________________2


Chúng ta vào cách tính như sau:

Ban đầu P1 sẽ đi bước 1, sau khi đi xong P1 sẽ so sánh số bước đi (đồng nghĩa với thời gian đã xử lý) với P2 , ta thấy vẫn chưa đủ số bước đi để P2 vào nên P1 đi tiếp thêm bước 2, nó sẽ quay lại so sánh tiếp số bước của P2.Lúc này P2 đã được phép .Nhưng nó sẽ so sánh tiếp thời gian xử lý của P1 và P2 cái nào ngắn hơn .Ta sẽ thấy rằng P1 chỉ còn xử lý thêm 1 bước trong khi đó P2 còn đến 5 bước .Vậy P1 sẽ được quyền đi thêm bước 3 do quy định thời gian ngắn xử lý trước. Xong P1 .

Sau khi P1 đi xong bước 3 thì P2 sẽ quay lại đi một bước .Lúc này đã đi được 4 bước rồi ! P2 sẽ so sánh thời gian chờ của các hành còn lại. Các bạn sẽ thấy P3 được quyền vào xử lý , lúc này nó sẽ so sánh tiếp Service Time .ST nào ngắn hơn sẽ được quyền xử lý trước theo quy luật đã nói ở trên.
P2 còn 6 bước
P3 có 3 bước , vậy P3 được quyền xử lý hết.Dựa vào quy luật thời gian ngắn xử lý trước có ưu tiên .Xong P3 !

P3 đã đi thêm 3 bước nữa vậy số bước đi hiện giờ là 7
Lúc này P4 được vào xử lý.nó được quyền đi thêm một bước.Khi đi xong nó sẽ so sánh với thời gian chờ kế tiếp lẫn thời gian xử lý, bạn thấy P5 được có 2, còn P4 thì còn 4.Nên P5 được phép vào xử lý hết 2 bước của nó.Xong P5 !

Lúc này tất cả các P đều vào xử lý , nó sẽ dựa vào thời gian xử lý để xác định P nào được vào xử lý tiếp theo.Các bạn quay lại tính sẽ thấy :
P2 còn 6 ;
P4 còn 4 ;
Như vậy quá trình sẽ xử lý P4 rồi đến P2

Ta có biểu đồ sau :


|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
0_______3_ 4______ 7__8___10_________14______________20
____P1___P2___P3___P4__P5______P4___________P5____ __

Giải thuật định thời CPU phần cuối cùng ( RR với Time Quantum=1)

Mình sẽ lấy bài mẫu trong slide Thầy đưa để giải thích giải thuật, các bạn có thể lấy ra coi song song 2 cái.

Process----- Arrival Time( AT )---------Service Time ( ST )
1-----------------0------------------------- 3
2----------------- 2----------------- ------- 6
3----------------- 4----------------- ------- 4
4----------------- 6----------------- ------- 5
5----------------- 8----------------- ------- 2

Mình sẽ nói theo giọng văn của mình coi như AT là thời điểm còn ST là số bước. Giải thuật này sẽ theo quy luật đúng thời điểm của ai thì cho phép người đó vào và chỉ đi được 1 bước vì theo đề Time Quantum=1 (nhìn trên hình ta có 5 thời điểm lần lượt cho P1, P2, P3, P4, P5)

Đầu tiên thằng P1 bước vào trước. Ta để ý thấy tại thời điểm 2 thằng P2 mới xuất hiện nên P1 được bước 2 bước ( vậy P1 còn 1 bước nữa là kết thúc )
---0--------------5-------------10-------------15-------------20
__-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.1)
P1 >>>>>

Tại thời điểm 2: Thằng P2 xuất hiện, ta hình dung vị trí như vầy P2..P1; P2 sẽ bước 1 bước rồi đến P1 bước tiếp một bước ( đến lúc này P1 đi ra vì đã hoàn thành số bước là 3)
---0--------------5-------------10-------------15-------------20
__-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.2)
P1 >>>>>--->>
P2 ------>>

Tại thời điểm 4: Thằng P3 xuất hiện, ta hình dung vị trí là P2 .. P3 ( quan sát (h.2)ta thấy P2 mới chỉ đứng ở thời điểm 3, và P3 ở thời điểm 4 nên mới có vị trí đó; chú ý P1 đã hết số bước nên ko tham gia nữa). Tới lúc này P2 sẽ bước 1 bước và P3 bước một bước.
---0--------------5-------------10-------------15-------------20
__-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.3)
P1 >>>>>--->>
P2 ------>>---->>
P3 --------------->>

Tiếp tục tại thời điểm 6: P4 xuất hiện, ta hình dung vị trí là P2 ..P4.. P3 ( Ta có thể quan sát (h.3),P2 lúc đó mới đứng ở thời điểm 5, tại thời điểm 6 P4 mới vào nên có vị trí đó ). Như trentheo trình tự: P2 bước 1, P4 bước 1, P3 bước 1. Chú ý lúc này P4 sẽ đứng ở thời điểm 8.
---0--------------5-------------10-------------15-------------20
__-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.4)
P1 >>>>>--->>
P2 ------->>--->>--->>
P3 --------------->>------->>
P4---------------------->>

Vào thời điểm 8: P5 xuất hiện nên nó sẽ đứng trước P4 chứ không đứng trước P3 ( vì P3 đang đứng ở thời điểm 9 ). Ta hình dung vị trí là P2..P5..P4.. P3. Như trên P2 bước 1, P5 bước 1, P4 bước 1, P3 bước 1.
---0--------------5-------------10-------------15-------------20
__-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.5)
P1 >>>>>--->>
P2 ------->>--->>--->>------->>
P3 --------------->>------->>--------->>
P4 --------------------->>---------->>
P5 ------------------------------>>

Vì tất cả thành viên đã tham gia nên ta cứ đọc theo trình tự như trên ( từ -> P2 ->P3 -> [P4-> P5 )để kết thúc số bước của từng thành viên ( cứ >> là 1 bước ta quan sát hình sẽ biết được các thành viên còn bao nhiêu bước). Thôi ghi ra luôn ^_^: Lúc này P2 đã đi được 4 bước ( P2 còn 2 bước ), P3 đi được 3 bước ( P3 còn 1 bước ), P4 đi được 2 bước( P4 còn 3 bước ), P5 đi được 1 bước ( P5 còn 1 bước ). Ta cứ tuân theo trình tự đọc đó là ta có kết quả
---0--------------5-------------10-------------15-------------20
__-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.6)
P1 >>>>>--->>
P2 ------->>--->>--->>------->>--------->>--------->>
P3 --------------->>------->>--------->>--------->>
P4 --------------------->>---------->>--------->>------>>>>>
P5 ------------------------------>>--------->>

Chú ý phần cuối cùng ta thấy P4 đi tới 2 bước vì trong quá trình đọc mấy thành viên khác đã hoàn thành số bước của mình (không tham gia nữa). Lúc này P4 còn tới 2 bước lựng nên bước nốt 2 bước còn lại để kết thúc.

Bài này các bạn đọc tham khảo, nếu có gì sai sót thì bổ sung để hoàn thiện giải thuật này nhé. Hy vọng có thể giúp các bạn một chút trong giải thuật này. Thân!
Tài liệu trên internet.