Thảo luận Bài 6

Tiểu sử
Henry Laurence Gantt (sinh 1861 - mất 23 tháng 11 năm 1919) là một kĩ sư cơ khí và cố vấn dự án người Mỹ, nổi tiếng với việc phát triển sơ đồ Gantt năm 1910. Sơ đồ Gantt được sử dụng rộng rãi trong những công trình lớn như đập Hoover hay hệ thống đường quốc lộ liên bang Mỹ và ngày nay vẫn là một công cụ quan trọng trong quản lý dự án.
Henry Gantt sinh tại quận Calvert, Maryland, Hoa Kỳ. Ông tốt nghiệp trường McDonogh năm 1878 và trường cao đẳng Johns Hopkins rồi làm thầy giáo và người vẽ đồ án trước khi trở thành kĩ sư cơ khí. Năm 1887 ông cùng Frederick W. Taylor quản lý công ty thép Midvale và công ty thép Bethlehem cho đến năm 1893. Sau này, khi làm cố vấn dự án, ngoài sơ đồ Gantt, ông còn thiết kế hệ thống thưởng năng suất - trong đó nhân viên có năng suất vượt định mức sẽ được thưởng phần trăm. Ngoài ra, ông còn phát triển một số phương pháp đo đạc hiệu suất và năng suất nhân viên.


Đóng góp
Henry Gantt đã có nhiều đóng góp cho môn khoa học quản lý, đáng nói nhất bao gồm:
- Sơ đồ Gantt: Đến ngày nay, sơ đồ Gantt vẫn được coi là một công cụ quản lý quan trọng. Sơ đồ Gantt biểu thị thời gian biểu của dự án dùng để quản lý, lên kế hoạch và kiểm soát tiến độ công việc trong dự án. PERT (Program Evaluation and Review Technique - Phương pháp ước lượng và xem xét chương trình) là một biến thể của sơ đồ Gantt.
- Hiệu suất công nghiệp: Hiệu suất công nghiệp có thể được nâng cao bằng cách phân tích một cách khoa học mọi khía cạnh của công việc. Công tác quản lý công nghiệp là cải tiến hiệu suất bằng cách hạn chế tối đa rủi ro.
- Hệ thống thưởng năng suất: Henry Gantt thưởng phần trăm quản lý viên tương ứng với năng suất vượt định mức nhân viên dưới quyền họ đạt được.
- Trách nhiệm xã hội của doanh nghiệp: Henry Gantt tin rằng doanh nghiệp phải có trách nhiệm với xã hội.

Nguồn: http://vi.wikipedia.org/wiki/Henry_Laurence_Gantt

NgoDucTuan (I11C) đã viết:Bạn nào giải và nói chi tiết bài này giúp mình dc ko!

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
a.Thể hiện bằng biểu đồ Gantt
b.Tính thời gian chờ trung bình của các tiến trình

Mình giải như sau:
Biểu đồ Gantt
P1 P1 P2 P1 P3 P2 P3
|----|------|-----|-----|-----|-----|-----|
4 20 40 60 66 86 94 107
Thời gian chờ trung bình của các tiến trình:
P1=16
P2=36
P3=23

HoiHoangHongVu I11C đã viết:

NgoDucTuan (I11C) đã viết:Bạn nào giải và nói chi tiết bài này giúp mình dc ko!

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
a.Thể hiện bằng biểu đồ Gantt
b.Tính thời gian chờ trung bình của các tiến trình

Mình giải như sau:
Biểu đồ Gantt
P1 P1 P2 P1 P3 P2 P3
|----|------|-----|-----|-----|-----|-----|
4 20 40 60 66 86 94 107
Thời gian chờ trung bình của các tiến trình:
P1=16
P2=36
P3=23

Mình giải bài này như sau:

Thời gian chờ TB:(90-4-46) +(98-30-28)+(111-51-33)=32,333ms

4 tình huống ra quyết định của trình điều phối bao gồm :
Khi tiến trình chuyển từ trạng thái Running sang waiting .Đến đây ta nhớ lại về 5 trạng thái của tiến trình ..Một tiến trình đang ở trạng thái running tức là đạng được HDH cấp CPU cho phép xử lý .Tuy nhiên nếu trong quá trình xử lý tiến trình có nhu cầu I/O hay chờ 1 tiến trình con khác thì tiến trình phải chuyển sang trạng thái wating.
Khi tiến trình chuyển từ running sang ready..Tình huống này xảy ra do ngắt.
Khi tiếnt rình chuyển từ waiting sang ready. Tình huống này xảy ra khi yêu cầu I/O đã kết thúc.
Khi tiên trình kết thúc công việc.
Phân biệt điều phối tiếm quyền và điều phối không tiếm quyền :
Điều phối không tiếm quyền : tức là HDH không bắt được tiến trình đang chạy .Vì thế nên tiến trình khi đã chiếm CPU thì sẽ giữ CPU đến khi nào nó thực hiện xong các lệnh của nó..Ngược lại điều phối tiếm quyền sẽ nắm bặt được các tiến trình và theo dõi nó đễ điều phối hợp lý.

Thời điểm Tiến trình Khoảng CPU kế tiếp
0 P1 7
2 P2 4
4 P3 1
5 P4 4
Biểu đồ Gantt



Giải thích :
Gọi khoảng CPU kế tiếp của các tiên trình là t1,t2,t3,t4
- Vào thời điểm ms thứ 0 tiến trình P1 bắt đầu chạy .t1=7.Tiến trình hiện hành là P1
- Vào thời điểm ms thứ 2 tiên trình P2 đến.Lúc này t1 =5,t2=4
Vì t1`>t2 thì P2 sẽ được chạy.Tiến trình hiện hành là P2
- Vào thời điểm ms thứ 4 tiên trình P3 đến .Lúc này t1 =5,t2=2,t3=1
Vì t2`>t3 P3 sẽ được chạy.Tiến trình hiện hành là P3
- Vào thời điểm ms thứ 5 tiên trình P4 đến .Lúc này t1 =5,t2=2,t4=4
Lúc này thì P3 đã kết thúc.
Vì t1`>t4>t2,t4 P2 sẽ được chạy.Tiến trình hiện hành là P2
- Sau khi P2 hoàn tất thì t1 =5 t4=4 .Vì t1>t4 nên P4 được chạy .Tiến trình hiện hành là P4
- Sau khi P4 hoàn tất thì P1 sẽ chạy.

Multilevel Queue Scheduling - MQS
-Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau.
VD:Mức các tiến trình tương tác chạy ở mặt trước có độ ưu tiên cao nhất và mức các tiến trình lô(batch) vận hành trong hậu trường.(Background)
-Mỗi hàng chờ có thuật giải để điều phối riêng.
-Quan hệ giữa các mức:
+ưu tiên cố định:xong hết các tiến trình mức trên rồi chuyển xuống mức dưới.Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mức cao hơn,tiến trình mức dưới sẽ bị tiếm quyền do tiến trình mới có độ ưu tiên cao hơn.
+Phân bổ theo tỉ lệ thời lượng.

Multilevel Feedback Queue Scheduling - MFQS
-Như MSQ nhưng cho phép điều tiết tiến trình sang mức khác.
VD:Những tiến trình hướng CPU được đưa xuống mức dưới
-MFQS đạc trưng bởi các thông số:
+Số mức.
+Thuật giải điều phối cho mỗi mức.
+Phương thức nâng cấp tiến trình.
+Phương thức hạ cấp tiến trình.
+Phương thức chọn hàng chờ cho tiến trình mới.

Ví dụ: Trong sân bay Tân Sơn Nhất có 5 cổng bán vé, và người mua vé phải xếp hàng vào 5 cổng đ1o. Có 5 loại khách với 5 mức ưu tiên khác nhau. Tuy nhiên lại chỉ có 1 cô nhân viên bán vé mà thôi.
+ Cổng 1: dành cho những người trong cùng ngành hàng không hoặc thân nhân của họ.
+ Cổng 2: cho thương binh những người có công với đất nướic..
+ Cổng 3: nhửng người khuyết tật.
+ Cổng 4: cho những người bình thường, khách vảng lai.
+ Cổng 5: cho sinh viên.
Với thuật giải MQS: thì nhân viên bán vé. Nhân viên này sẽ ưu tiên bán cho những người có độ ưu tiên lớn hơn .Hết 1 cổng rồi chuyển sang cổng có độ ưu tiên thấp hơn >tuy nhiên nếu có 1 người nào đó ở cổng có mức ưu tiên cao hơn cổng NV này đang bán thì anh ta sẽ ưu tiên cho người có mức ưu tiên cao hơn.
Với thuật giải MFQS thì để cho hệ thống hoạt động được tốt hơn thì sẽ có thêm sự điều phối hợp lý hơn giữa các hàng chờ. 1 người ở cổng có mức ưu tiên thấp tuy nhiên anh đã chờ quá lâu mà vẫn chưa mua được vé vì vậy chuyển anh ta lên cổng có mức ưu tiên cao để nhanh chóng bán ve cho anh ta (nếu không khách hàng sẽ nổi nóng)

ngocquynh2091(i11C) đã viết:

HoiHoangHongVu I11C đã viết:

NgoDucTuan (I11C) đã viết:Bạn nào giải và nói chi tiết bài này giúp mình dc ko!

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
a.Thể hiện bằng biểu đồ Gantt
b.Tính thời gian chờ trung bình của các tiến trình

Mình giải như sau:
Biểu đồ Gantt
P1 P1 P2 P1 P3 P2 P3
|----|------|-----|-----|-----|-----|-----|
4 20 40 60 66 86 94 107
Thời gian chờ trung bình của các tiến trình:
P1=16
P2=36
P3=23

Mình giải bài này như sau:

Thời gian chờ TB:(90-4-46) +(98-30-28)+(111-51-33)=32,333ms

Hix. Mình có sai xót rùi . Mà hình như bạn cũng bị sai xót luôn. Theo biểu đồ Gantt thì ở thời điểm 64 , do p1 =44 , p2=64 , p3=51(theo đề), như vậy p1 nhỏ nhất nên chạy tiếp.

NguyenNgocMyTien(I11C) đã viết:Một hệ thống có 3 tiến trình, với thời điểm đến và tg sử dụng CPU như sau

Tiến trình	Thời điểm đến	Khoảng CPU
P1	3	35
P2	10	20
P3	25	15

Hãy dùng thuật giải Round Robin (RR) với thời lượng 10ms để điều phối CPU.
a/Thể hiện bằng biểu đồ Gantt?
b/Tính thời gian chờ trung bình của các tiến trình?

Bài làm:

Mình vẽ và làm theo cách hiểu của mình, các bạn tham khảo góp ý giúp mình nhé.

a/ Biểu đồ gant:

- Ở thời điểm 3ms tiến trình P1 vào hệ thống và được sử dụng CPU với thời lượng 10ms.Sau khoảng thời gian 10ms (lúc này là thời điểm 13ms) P1 bị tiếm quyền và được đưa vào cuối hàng chờ Ready.Trong hàng chờ hiện tại có 2 tiến trình P1 và P2( P2 đã vào hàng chờ ở thời điểm 10ms).
- Ở thời điểm 13ms tiến trình P2 đã vào hệ thống và được sử dụng CPU với thời lượng 10ms.Sau khoảng thời gian 10ms (lúc này là thời điểm 23ms) P2 bị tiếm quyền và được đưa vào cuối hàng chờ Ready.
- Ở thời điểm 23ms tiến trình P1 trong hàng chờ Ready vào hệ thống được sử dụng CPU với thời lượng 10ms.Sau khoảng thời gian 10ms (lúc này là thời điểm 33ms) P1 bị tiếm quyền và được đưa vào cuối hàng chờ Ready.Trong hàng chờ hiện tại có 3 tiến trình P1, P2, P3( P3 đã vào hàng chờ ở thời điểm 25ms).
- Ở thời điểm 33ms tiến trình P2 trong hàng chờ vào hệ thống được sử dụng CPU với thời lượng 10ms.Sau khoảng thời gian 10ms (lúc này là thời điểm 43ms) P2 đã sử dụng hết khoảng CPU và thoát ra ngoài.
- Ở thời điểm 43ms tiến trình P3 đã vào hệ thống và được sử dụng CPU với thời lượng 10ms.Sau khoảng thời gian 10ms (lúc này là thời điểm 53ms) P3 bị tiếm quyền và được đưa vào cuối hàng chờ Ready.Trong hàng chờ hiện tại chỉ còn P1 và P3
- Ở thời điểm 53ms tiến trình P1 trong hàng chờ Ready vào hệ thống được sử dụng CPU với thời lượng 10ms.Sau khoảng thời gian 10ms (lúc này là thời điểm 63ms) P1 bị tiếm quyền và được đưa vào cuối hàng chờ Ready.
- Ở thời điểm 63ms tiến trình P3 trong hàng chờ vào hệ thống đã sử dụng hết khoảng CPU và thoát ra ngoài ở thời điểm 68ms.Trong hàng chờ hiện tại chỉ còn tiến trình P1.
- Ở thời điểm 68ms tiến trình P1 trong hàng chờ vào hệ thống đã sử dụng hết khoảng CPU và thoát ra ngoài ở thời điểm 73ms.

b/ Thời gian chờ trung bình = (Thời điểm kết thúc - Thời điểm đến - Thời gian dùng CPU) / Số tiến trình
= ((73-3-35) + (43-10-20) + (68-25-15))/3= 25,3333ms

Cách giải thích của bạn rất dễ hiểu (nhưng đi thi không cần nói rõ vậy đâu bạn hihi tiết kiệm thời gian đó hihi) cảm ơn bạn và tất cả mọi người rất nhiều.

HoiHoangHongVu I11C đã viết:

phamdieptuan (I11C) đã viết:

Tạ Hoàng Tân 102C đã viết:

- Biểu đồ Gantt:

|--P1--|--P1--|--P2--|--P1--|--P3--|--P2--|--P3--|
4-----24------44-----64-----70-----90-----98-----111

Bài này bạn sai ở chỗ P2 rồi , vì thời điểm đến của P3 là 51 nên sau đó phải là P3 chứ ko phải P1 .

Sao lại sai chứ
thời điểm đến của P3 là 51 nhưng P1 đang là 44 kìa, nên P1 phải được ưu tiên trước.

đúng rùi. p1 ưu tiên trước. Ai có bài tập về thuật giải SJFS post lên đi.

chính xác vì p1 nằm ở hàng đợi trước nên nó sẽ vô trước p3

DangNgocMinh(I11C) đã viết:

Duongthithanhhuynh (I11C) đã viết:

HoiHoangHongVu I11C đã viết:

minhgiangbc đã viết:

DangNgocMinh(I11C) đã viết:

chipphonui đã viết:đề. một hệ thống có 3 tiến trình, với thời điểm đến và tg sử dụng CPU như sau;

P1 3 35

P2 10 20

P3 25 15
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU.
a, thể hiện bằng biểu đồ gant?
b,tính thời gian chờ Tb của các tiến trình?

như cách giải mình post trên sẽ có kết quả:
TGCTB= (35+13+28)/3=25,33 ms

Biểu đồ Gantt

mình cung có kết quả như vậy nhưng cho minh bổ xung thêm cho đầy đủ nhé
A/ biểu đồ Gantt:
với thời luợng 10ms để điều phối CPU nên các tiến trình chỉ có thể dùng 10ms sau đó phải chuỷên qua tiến trình khác.ở đây là các tiến trình p1,p2,p3


B/ thời gian chờ trung bình của các tiến trình:
Theo như công thức:

T(i)= thờiđiểm kết thúc - thời điểm đến - t/g dùng CPU

Thời gian chờ của P1 = 73-3-35=35 -> T1
Thời gian chờ của P2 = 43-10-20=13 -> T2
Thời gian chờ của P3 = 68-25-15=28 -> T3

P(tb) = (T1+T2+T3)/3
Thời gian chờ trung bình: P(tb)= (35+13+28)/3=76/3=25.33 (ms)

các bạn tham khảo và góp ý nhé

2 bạn ơi có thể giải thích rõ hơn ko.

Bạn ơi mình cũng ra kết quả thế nhưng cái biểu đồ Gant minh k biết vẽ như thế nào, nhưng nếu như theo cách bạn vẽ có thêm tiến trình P0 thì tổng phải là 4 process chứ, theo mình hiểu là vậy ko biết đúng ko mong thầy và các bạn góp ý.

bạn minhgiangbc chắc quên giải thích hình thực tế đề bài không có P0 thời điểm từ 0->3 không có tiến trình nào chạy cả nên bạn minhgiang có thể giả sử đó là P0 đang chạy và kết thúc ^^

Các bạn có thể giải thích rõ hơn cho mình một chút được không? nếu như xuất phát từ P0 thì thời điểm là 0, từ P1 là 3, nhưng nếu bỏ qua P0 bắt đầu từ P1 thì tại sao thời điểm lại là 3. Các bạn giúp mình với nha.

NguyenNgocMyTien(I11C) đã viết:

NguyThiGai (I11C) đã viết:
Cảm ơn bài viết của hai bạn!
Mình đã hiểu được giải thuật Round Robin. Mình đã vận dụng cách giải của hai bạn để giải bài này với thời lượng 20ms. Các bạn xem giúp mình xem nó có đúng không ha!

1. Thời điểm 3: P1 bắt đầu chạy 20 ms
2. Thời điểm 23: P2 tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 43: P1tiếm quyền P3 (vì P1 đang chờ ở thời điểm 23, P3 đang chờ ở thời điểm 25 và P2 kết thúc)
4. Thời điểm 58: P3 bắt đầu chạy (P1 kết thúc) và kết thúc ở thời điểm 73
Thời gian chờ trung bình = ((58-3-35) + (43-10-20) + (73-25-15))/3= 22ms

Mình cũng thử làm bài này và có kết quả giống như bạn.hihi...
Cảm ơn các bạn đã đưa thêm bài tập lên nhé!
@ nguyenminhlai.(I11C) : bạn nhanh tay thiệt đó nha...*_~...

Cám ơn bạn đã giúp mình, ngồi tới giờ mới hiểu.

Như MQS nhưng cho phép Điều tiết tiến trình sang mức khc, ví dụ: những tiến trình hướng CPU được đưa xuống mức dưới, trong khi tiến trình hướng I/O hoặc chờ lâu được chuyển lên trên.
• MFQS đặc trưng bởi các thông số:
- Số mức ( số hàng chờ )
- Thuật giải điều phối cho mỗi mức
- Phương thức nâng cấp tiến trình
- Phương thức hạ cấp tiến trình
- Phương thức chọn hàng chờ ( chọn mức ) cho tiến trình mới

KimHue36 (I11C) đã viết:

• Biểu đồ Gantt:

https://2img.net/r/ihimg/photo/my-images/703/rrsw.jpg/

• Thời gian chờ TB :

((78-3-35)+(50-10-20)+(40-25-15))/3=20 ms
Mong thầy và các bạn góp ý ! Em cám ơn

KimHue xem lại nha, đáp số và biểu đồ bạn đưa ra chưa chính xác. Bạn xem bài của bạn "minhgiangbc" bạn đó giải tốt lắm.

NguyenHaThanh97 (I11C) đã viết:Có bạn nào biết cách tính thời gian chờ trung bình của thuật toán Round-Robin không?
Ở bài tập trên lớp thầy giảng:
Thời gian chờ trung bình = ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms
Mình không hiểu các số liệu đó ở đâu? Bạn nào biết chỉ mình với.
Cảm ơn các bạn!!!!!!
Chúc mọi người luôn vui vẻ.

Hôm trước thầy có đưa ra công thức bạn ah, đây là công thức thầy đưa hôm trước:
Theo như công thức:

T(i)= thờiđiểm kết thúc - thời điểm đến - t/g dùng CPU

Thời gian chờ của P1: T1=0+57+24=81
Thời gian chờ của P2: T2=20
Thời gian chờ của P3: T3=37+40+17=94
Thời gian chờ của P3: T3=57+40=97

P(tb) = (T1+T2+T3+T4)/4
Thời gian chờ trung bình: P(tb)= (81+20+94+97)/4=73 (ms)

Đó là cách tính chi tiết bạn à, chúc bạn thành công.

Mình có thắc mắc, mong các bạn cùng thảo luận chung nhé! Giả sử các tiến trình không có thời điểm tới thì mình sẽ đặt thời điểm đó được đặt là "0". Nếu vậy thì hình dung là các tiến trình đến cùng một thời điểm, trong thực tế thì khá hiếm và khó xảy ra. Mong các bạn giải thích thêm. Cám ơn.

Mình chưa hiểu cách vẽ biểu đồ này,các bạn giúp mình với.Trong hình này mình thấy đầu tiên là xác định thời điểm 0 2 4 5 ,nhưng sao các số 7 11 16 mình ko hiểu? và để ý thấy rằng thì khoảng CPU kế tiếp bằng bao nhiêu thì dưới biểu đồ thể hiện = 1 đoạn tương tưng.

chipphonui đã viết:đề. một hệ thống có 3 tiến trình, với thời điểm đến và tg sử dụng CPU như sau;

P1 3 35

P2 10 20

P3 25 15
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU.
a, thể hiện bằng biểu đồ gant?
b,tính thời gian chờ Tb của các tiến trình?

Biểu đồ gant:



thời gian chờ Tb:
(35+20+20)/3= 25ms

các bạn tham khảo, bổ sung dùm mình nha. thanks

Sao bạn không vẽ biểu đồ ra, từ biểu đồ bạn mới có cơ sở tính TGTB chứ. Kết quả này cũng sai rồi bạn ơi. KQ đúng là 25,3 ms đó. Thầy đã giải rồi bạn xem tham khảo nhé.
Thân chào!

Chào mọi người..
Mình có cách hiểu về 2 giải thuật FCFS và RRS .. mọi người tham khảo và Thầy xem qua giúp e, có gì sai sửa dùm e, để e học sau này.

FCFS (đến trước - phục vụ trước)

Ta chú ý:

• thời điểm là thời gian bắt đầu 1 tiến trình
  tiến trình có thể không theo thứ tự (đến trước thì phục vụ trước).
  khoảng CPU ngầm hiểu là thời gian thực hiện

-->>> ta lấy thời điểm làm mốc

RRS gần giống FCFS

đến trước cũng phục vụ trước nhưng giới hạn thời lượng CPU - time Quantun (ta có thể hiểu ngầm là thời gian CPU thực hiện tối đa cho 1 tiến trình



Ta chú ý: đến trước phục vụ trước + thực hiện trong time quantum. Như vậy thực hiện P1, P2 .. P4




Thời gian chờ:
P1 = 0 + 57 + 24
P2 = 20
P3 = 37 + 40 +17
P4 = 57+40
Thời gian chờ trung bình = (P1 + P2 + P3 + P4 )/4 = 73ms

HẾT

1


2



có 2 đề này các bạn cùng giải nhé.

phamdieptuan (I11C) đã viết:

DangNgocMinh(I11C) đã viết:

NguyenHaThanh97 (I11C) đã viết:Có bạn nào biết cách tính thời gian chờ trung bình của thuật toán Round-Robin không?
Ở bài tập trên lớp thầy giảng:
Thời gian chờ trung bình = ( (0+57+24) + 20+(37+40+17)+(57+40)) / 4 = 73 ms
Mình không hiểu các số liệu đó ở đâu? Bạn nào biết chỉ mình với.
Cảm ơn các bạn!!!!!!
Chúc mọi người luôn vui vẻ.

theo cách hiểu của mình vì các tiến trình có thời điểm đến như nhau (đều =0) ta có:

• p1:
  0->20 p1 đang chạy nên ko chờ
  20->77 p2 p3 p4 đang chạy nên p1 chờ trong khoản 77-20 = 57
  77->97 p1 đang chạy nên ko chờ
  97->121 p3 p4 đang chạy nên p1 chờ trong khoản 121-97 = 24
  => Tp1=0+57+24
  121->134 p1 đang chạy và kết thúc

• p2:
  0->20 p1 đang chạy nên p2 chờ trong khoản 20-0 = 20
  20->37 p2 đang chạy và kết thúc
  =>Tp2=20

• p3:
  0->37 p1 p2 đang chạy nên p3 chờ trong khoản 37-0=37
  37->57 p3 đang chạy nên không chờ
  57->97 p4 p1 đang chạy nên p3 chờ trong khoản 97-57=40
  97->117 p3 đang chạy nên không chờ
  117->134 p4 p1 đang chạy nên p3 chờ trong khoản 134-117=17
  =>Tp3= 37+40+17
  134->162 p3 chạy và kết thúc

• tương tự ta có
  p4 :
  với Tp4=57+40

TGCTB = ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms

Thời gian chờ trung bình = ( (0+57+24) + 20+(37+40+17)+(57+40)) / 4 = 73 ms

Theo mình nghĩ thì các bạn cứ áp dụng công thức thầy dạy tối qua là tính dc t/g tb
T/g chờ của Ti=(Thời điểm kết thúc - Thời điểm đến - Thời gian chờ của cpu)
bài trên với thời điểm đến là như nhau (=0) nên:
P1 = (134 - 0 - 53 ) = 81ms
P2 = ( 37 - 0 - 17 ) = 20ms
P3 = (162 - 0 - 68 ) = 94ms
P4 = ( 124 - 0 - 24) = 97ms

=>T/g TB = (81 + 20 + 94 + 97) / 4 = 73ms

Ngoài ra nhìn vào biểu Gantt mình có thể hiểu như sau:
+ Khoảng t/g từ 20->77 và từ 97 ->121 là không dành cho tiến trình P1
<=> 0+(77-20)+(121-97) = (0 + 57 + 24)
+ Khoảng t/g từ 0->20 là không dành cho tiến trình P2
<=> (20-0) = 20
+ Khoảng t/g từ 0->37 và từ 57 ->97 và từ 117 -> 134 là không dành cho tiến trình P3
<=> (37-0)+(97-57)+(134 -117) = (37 + 40 + 17)
+ Khoảng t/g từ 0->57 và từ 77 ->117 là không dành cho tiến trình P4
<=> (57-0)+(117-77) = (57 + 40)

Cảm ơn bạn phamdieptuan (I11C), và mình cũng làm giống như bạn.

DoThuyTien16 (I11C) đã viết:Bốn tình huống ra quyết định của trình điều phối.
1. Khi tiến trình chuyển từ Running sang Waiting (chờ I/O, chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready( do ngắt xảy ra).
3. Khi tiến trình chuyển từ Waiting sang Ready( do kết thúc I/O).
4. Khi tiến trình kết thúc công việc.
Phân biệt điều phối tiếm quyền và điều phối không tiếm quyền:
• Điều phối không tiếm quyền( Non - Preemptive): sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4. Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting( cách làm trong Windows 3.1 và Macintosh OS). Dùng khi máy không có Timer.
• Điều phối có tiếm quyền( Preemptive):sơ đồ điều phối tiến hành trong cả 4 tình huống.
• Giống nhau: cùng điều phối CPU( chọn tiến trình trong Ready Queue để cấp thời gian CPU( chuyển sang trạng thái Running)).
• Khác nhau:
 Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non – Preemptive Scheduling thì điều phối CPU không tiếm quyền.
 Non – Preemptive Scheduling: có nghĩa là khi có 1 tiến trình P1, P2, P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình.

Bài này rất hay! Rất chi tiết, cảm ơn bạn rất nhiều!

huyentran_I11C đã viết:Chào mọi người..
Mình có cách hiểu về 2 giải thuật FCFS và RRS .. mọi người tham khảo và Thầy xem qua giúp e, có gì sai sửa dùm e, để e học sau này.

FCFS (đến trước - phục vụ trước)

Ta chú ý:

• thời điểm là thời gian bắt đầu 1 tiến trình
  tiến trình có thể không theo thứ tự (đến trước thì phục vụ trước).
  khoảng CPU ngầm hiểu là thời gian thực hiện

-->>> ta lấy thời điểm làm mốc

RRS gần giống FCFS

đến trước cũng phục vụ trước nhưng giới hạn thời lượng CPU - time Quantun (ta có thể hiểu ngầm là thời gian CPU thực hiện tối đa cho 1 tiến trình



Ta chú ý: đến trước phục vụ trước + thực hiện trong time quantum. Như vậy thực hiện P1, P2 .. P4




Thời gian chờ:
P1 = 0 + 57 + 24
P2 = 20
P3 = 37 + 40 +17
P4 = 57+40
Thời gian chờ trung bình = (P1 + P2 + P3 + P4 )/4 = 73ms

HẾT

Cảm ơn bạn huyentran_I11C đã có lời giải thích thật chi tiết này.
Bạn có thể giúp mình giải quyết bài toán này

Tiến trình	Thời điểm đến	CPU-Brust
P1	3	37
P2	10	20
P3	24	14

Dùng thuật toán RRS với thời lượng 10ms dùng CPU
a) Vẽ biểu đồ Gantt
b) Tính thời gian trung bình

Bạn nào quan tấm làm cho mọi người cùng nhau hiểu nhé
Thansk các bạn nhiều

DangNgocMinh(I11C) đã viết:

chipphonui đã viết:đề. một hệ thống có 3 tiến trình, với thời điểm đến và tg sử dụng CPU như sau;

P1 3 35

P2 10 20

P3 25 15
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU.
a, thể hiện bằng biểu đồ gant?
b,tính thời gian chờ Tb của các tiến trình?

như cách giải mình post trên sẽ có kết quả:
TGCTB= (35+13+28)/3=25,33 ms

Biểu đồ Gantt

Theo Thúy thì từ 23->33 là p3, 33->43 là P1, 43->53 là P2, 53->58 là P3, 58->73 là P1.
=> thời gian chờ trung bình : ((3+20+15)+(13+20)+(23+20))/3=38.3ms

vohongcong(I111C) đã viết:

Mình chưa hiểu cách vẽ biểu đồ này,các bạn giúp mình với.Trong hình này mình thấy đầu tiên là xác định thời điểm 0 2 4 5 ,nhưng sao các số 7 11 16 mình ko hiểu? và để ý thấy rằng thì khoảng CPU kế tiếp bằng bao nhiêu thì dưới biểu đồ thể hiện = 1 đoạn tương tưng.

Mình xin đóng góp ý kiến hi vọng giúp bạn Công hiểu thêm vấn đề này ^^!
Tại thời điểm 0 P1 chạy với khoản CPU là 7 nhưng tới thời điểm 2 thì P1 bị P2 tiếm quyền (lúc này khoản CPU của P1=7-2=5)

Sau khi tiếm quyền P2 chạy tại thời điểm 2 với khoản CPU=4 nhưng tới thời điểm 4 P2 lại bị P3 tiếm quyền (lúc này khoản CPU của P2=4-2=2)

Theo đề bài ta có khoản CPU của P3=1 nên sau khi tiếm quyền P2 thì P3 chạy xong và kết thúc
Đến lúc này có lẽ nhiều bạn thắc mắc tại sao không phải P4 chạy mà là P2 như sơ đồ vì “ nếu tiến trình mới đến có khoản CPU kế tiếp nhỏ hơn so với thòi gian còn lại của tiến trình đang vận hành nó sẽ được ưu tiên thay thế ”
Lúc này ta xét



Do P2 có khoản CPU=2< khoản CPU của P4=4 nên P2 đc ưu tiên thay thế P4
Khi đó tại thời điểm 5 P2 tiếm quyền chạy tiếp với khoản CPU còn lại là và kết thúc
Bây giờ còn lại P1 & P4 theo bảng trên thì khoản CPU của P4 =4 nhỏ hơn P1 nên lúc này P4 chạy từ thời điểm 7->11 và kết thúc
Cuối cung là P1 chạy với khoản CPU=5 còn lại của nó.

NguyenThiThanhThuy(I11C) đã viết:

DangNgocMinh(I11C) đã viết:

chipphonui đã viết:đề. một hệ thống có 3 tiến trình, với thời điểm đến và tg sử dụng CPU như sau;

P1 3 35

P2 10 20

P3 25 15
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU.
a, thể hiện bằng biểu đồ gant?
b,tính thời gian chờ Tb của các tiến trình?

như cách giải mình post trên sẽ có kết quả:
TGCTB= (35+13+28)/3=25,33 ms

Biểu đồ Gantt

Theo Thúy thì từ 23->33 là p3, 33->43 là P1, 43->53 là P2, 53->58 là P3, 58->73 là P1.
=> thời gian chờ trung bình : ((3+20+15)+(13+20)+(23+20))/3=38.3ms

Mình nghĩ bạn Thúy nhầm một tý ở chỗ thời điểm P3, vì theo đề bài thì thời điểm 25 P3 mới bắt đầu chạy nên khi đó tại thời điểm 23 P1 sẽ tiếm quyền P2 chạy còn P3 lúc này chưa xuất hiện