Thảo luận Bài 6

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 ý.

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 ^^

VoMinhHoang (I11C) đã viết:- Giống nhau: Thuật giải Multilevel Queue Scheduling (Điều phối hàng chờ nhiều mức) và Multilevel Feedback Queue Scheduling (Điều phối hàng chờ nhiều mức có điều tiết) cùng sử dụng nhiều mức hàng chờ với độ ưu tiên khác nhau, mỗi hàng chờ có thể sử dụng thuật giải riêng, ví dụ Round-Robin (RRS) hoặc FCFS.

- Khác nhau: Multilevel Feedback Queue Scheduling cho phép điều chuyển (điều tiết) tiến trình từ hàng chờ này sang hàng chờ kia (hạ cấp độ hay nâng cấp độ ưu tiên), nghĩa là mềm dẻo hơn Multilevel Queue Scheduling.

- Ví dụ minh hoạ: Phòng bán vé tàu hoả ga Hòa Hưng có 5 cửa bán vé, và các người mua vé được xếp vào 5 cửa để chờ mua vé.
- Cửa số 1: dành cho những người system
- Cửa số 2: dành cho những người thương binh - mất sức lao động.
- Cửa số 3: dành cho những người bình thường.
- Cửa số 4: dành cho những người ưu tiên ở mức độ thấp hơn.
- và Cửa số 5: dành cho sinh viên - học sinh.

có thể có nhiều cửa bán vé với mức ưu tiên khác nhau, trong khi chỉ có 1 người bán vé (1 CPU) phải luân chuyển giữa các cửa để phục vụ đủ loại người mua vé (các tiến trình) như người system (là người nhà họ hàng của ga Hòa Hưng), người mua bình thường, người mua là thương binh, nguời mất sức lao động,...(chỉ có 1 cô bán vé phải chạy đi chạy lại giữa 5 cửa)

Ví dụ Minh họa:

Việc phục vụ khách trong nhà hàng
Thực khách sẽ đến và gọi món ăn, nước uống.
Mỗi thức ăn và nước uống đều có thời gian chuẩn bị là khác nhau.
Thời gian trung bình đợi của thực khách là khác nhau
- Nếu khách hàng quen thân hoặc đặc bàn trước chúng ta sẽ ưu tiên trước(lập lịch với mức độ ưu tiên)
- Còn lại thường thì các nhà hàng sẽ phục vụ theo kiểu FCFS đến trước phục vụ trước

phamdieptuan (I11C) đã viết:

LeTanDat (I11C) đã viết:

phamngoctan095 (I11C) đã viết:Chào cả nhà!

Mình thấy 2 dạng bài tập hôm qua mà Thầy giảng trên lớp, nghe Thầy nói là sẽ cho ra 1 trong 2 dạng này chiếm khoảng 20% tổng số điểm của bài thi. Bài tập của Thầy cho hôm qua thì các bạn đã giải đáp cụ thể lắm ròy, zj bạn nào có bài tập dạng tương tự thì post lên để mọi người cùng giải nha!

Mình xem trong thư mục HeDieuHanh\DeCuong có mẫu đề thi của các năm về trước cũng có nhiều bài tập tương tự, nên lấy thử 1 bài trong file "De thi 1 lan 1 HDH 2005-2006 (HK2) - Thay To Tuan.doc" như sau:

Câu 3 (2 điểm)
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 (có thể có 2 phương án):
a. Thể hiện bằng biểu đồ Gantt (1,0 điểm)
b. Tính thời gian chờ trung bình của các tiến trình (1,0 điểm)

Mọi người cùng giải để hiểu thêm nha!

- Biểu đồ Gantt:
| P1 | P1 | P2 | P3 | P1 | P2 | P3 |
4...24...44...64...84...90...98...111
P1= 90-4-46=40
P2=98-30-28=40
P3=111-51-33=27
Thời gian chờ trung bình:
=(40+40+27)/3=35.66 (ms)

Theo mình thì có đáp án khác:
- Biểu đồ Gantt:

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

Thời gian chờ trung bình:
T(tb) = ((70 - 4 - 46) + (98 - 30 - 28) + (111 - 51 - 33))/3 = 29ms

Theo mình thấy thì cách giải trên cũng đúng vì tại thời điểm 64ms thì P1 đang chờ ở 44ms mà P3 thì 51ms nên thằng P1 sẽ vào trước thằng P3. Ko biết cách nghĩ của mình như vậy thì có đúng ko nữa mong các bạn góp ý và chỉ giáo thêm. thanks!

Sơ đồ Gantt là một trong những công cụ cổ điển nhất mà vẫn được sử dụng phổ biến trong quản lý tiến độ thực hiện dự án. Sơ đồ này được xây dựng vào năm 1915 bởi Henry L. Gantt, một trong những nhà tiên phong về lĩnh vực quản lý khoa học.

Trong sơ đồ Gantt, các công tác được biểu diễn trên trục tung bằng thanh ngang, thời gian tương ứng được thể hiện trên trục hoành.

Ví dụ: Một nhà máy thép đang cố gắng tránh chi phí cho việc lắp đặt một thiết bị kiểm soát ô nhiễm không khí. Tuy nhiên để bảo vệ môi trường địa phương, các cơ quan có chức năng đã buộc nhà máy phải lắp hệ thống lọc không khí trong vòng 16 tuần. Nhà máy đã bị cảnh báo sẽ buộc phải đóng cửa nếu thiết bị này không được lắp đặt trong thời hạn cho phép. Do đó để đảm bảo hoạt động của nhà máy, ông giám đốc muốn hệ thống này phải được lắp đặt đúng thời hạn. Những công việc của dự án lắp đặt thiết bị lọc không khí này được trình bày Hinh1

Sơ đồ thanh ngang theo phương thức triển khai sớm

Sơ đồ thanh ngang theo phương thức triển khai chậm

Ưu nhược điểm của sơ đồ thanh ngang:

Ưu điểm

Dễ xây dựng và làm cho người đọc dễ nhận biết công việc và thời gian thực hiện của các công tác

Thấy rõ tổng thời gian thực hiện các công việc

Nhược điểm

Không thể hiện được mối quan hệ giữa các công tác, không ghi rõ quy trình công nghệ. Trong dự án có nhiều công tác thì điều này thể hiện rất rõ nét

Chỉ phù hợp áp dụng cho những dự án có quy mô nhỏ, không phức tạp

buithithudung24 (i11c) đã viết:Ban đầu tất cả đều được ưu tiên mức hệ thống nhưng sau thì 1 số bị đưa xuống phía dưới, bản thân hàng đợi đó có thể bị đưa tiếp xuống dưới hạ thấp tiến trình từ mức trên xuống dưới,không có chuyện nâng cấp ở đây.
Thuật giải ở độ 0: Round_Robin (8ms)
Thuật giải ở độ 1: Round_Robin (16ms)
Thuật giải ở độ 2: FCFS

Theo mình hiểu thì vẫn có thể nâng cấp lên nếu các tiến trình cho thuật giải thấp nhất quá nhiều. Hệ thống sẽ linh hoạt chuyển đổi nếu các mức ưu tiên cao hơn đã giải quyết hết các tiến trình của nó. Vd:

Độ 0: 2 co tiến trình

Độ 1: 0 co tiến trình

Độ 2: 10 co tiến trình

Thì tiến trình ở độ 2 có thể được điều phối lên độ 1 để giải quyết. Tuy nhiên cụ thể đưa lên bao nhiêu tiến trình và đưa như thế nào nếu cả độ 0 & 1 đều không có tiến trình nào. Có bạn nào có thể giải thích câu hỏi của mình được không. Cảm ơn.

Ví dụ về thuật giải Preemptive SJFS

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 CPU-Burst
P1 0 30
P2 15 13
P3 20 6

Bài toán sử dụng thuật giải Preemptive SJFS để đ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

GIẢI :

a/ Biểu đồ Gannt

...P1...........P2.............P3.................P2.....................P1.......
|-------|----------|------------|-------------|-----------------|
0........15...........20...............26................34.....................49

b/ Thời gian chờ trung bình:
P1: 0+34-15=19
P2:0+26-20=6
P3=0

t=(19+6+0)/3=25/3 (ms)

HoiHoangHongVu I11C đã viết: Ví dụ về thuật giải Preemptive SJFS

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 CPU-Burst
P1 0 30
P2 15 13
P3 20 6

Bài toán sử dụng thuật giải Preemptive SJFS để đ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

GIẢI :

a/ Biểu đồ Gannt

...P1...........P2.............P3.................P2.....................P1.......
|-------|----------|------------|-------------|-----------------|
0........15...........20...............26................34.....................49

b/ Thời gian chờ trung bình:
P1: 0+34-15=19
P2:0+26-20=6
P3=0

t=(19+6+0)/3=25/3 (ms)

Mình giải bài này theo cách không tiếm quyền như sau:
a/ Biểu đồ Gannt

.................P1..............P3.........P2....
|---------------------|------|---------|
0............................30......36..........49

b/ Thời gian chờ trung bình:
T(tb)=(0 + 21 + 10)/3 = 10.333ms

Theo mình hiểu là vậy ko biết đúng ko mong thầy và các bạn góp ý.

Câu 4:So sánh MQS (Multilevel Queue Scheduling)với MFQS(Multilevel Feedback Queue Scheduling)
-Multilevel Queue Scheduling:
+ Được chia thành nhiều queue riêng biệt
• Foreground(Chứa các interactive process)
• Background(Chứa các backprocess)
+ Mỗi hàng chờ có thuật giải điều phối riêng
• Foreground: RR
• Background:FCFS
+ Quan hệ giữa các mức
• lập lịch với mức độ ưu tiên
• Phân chia thời gian: mỗi queue nhận được một lượng thời gian CPU nào đó mà có thể lập lịch các tiến trình của nó
+ Tiến trình trong queue có mức độ ưu tiên thấp hơn chỉ có thể chạy khi các queue có mức ưu tiên thấp hơn rỗng
+ Tiến trình có mức ưu tiên cao hơn khi vào ready queue không ảnh hưởng đến tiến trình đang chạy có mức ưu tiên thấp hơn.
Ví dụ:
Việc phục vụ khách trong nhà hàng
+ Thực khách sẽ đến và gọi món ăn, nước uống.
+ Mỗi thức ăn và nước uống đều có thời gian chuẩn bị là khác nhau.
+ Thời gian trung bình đợi của thực khách là khác nhau
• Nếu khách hàng quen thân hoặc đặc bàn trước chúng ta sẽ ưu tiên trước(lập lịch với mức độ ưu tiên)
• Còn lại thường thì các nhà hàng sẽ phục vụ theo kiểu FCFS đến trước phục vụ trước
*Multilevel Feedback Queue Scheduling
+ Điều tiết tiến trình có thể di chuyển giữa các queue khác nhau
+ Đa mức hàng đợi đặc trưng bởi các thông số sau:
- Số lượng hàng chờ
- Giải thuật lập lịch cho mỗi hàng chờ
- Phương pháp sử dụng để xác định khi nào thì tăng, giảm mức ưu tiên của một tiến trình
- Phương pháp được sử dụng để xác định hàng chờ nào mà tiến rình sẽ đến khi nó cần được phục vụ.

Giống nhau:
Thuật giải Multilevel Queue Scheduling (Điều phối hàng chờ nhiều mức) và Multilevel FeedBack Queue Scheduling (Điều phối hàng chờ nhiều mức có điều tiết) cùng sử dụng nhiều hàng chờ với độ ưu tiên khác nhau, mỗi hàng chờ có thể sử dụng thuật giải riêng, ví dụ như Round - Robin(RRS) hoặc FCFS.

Khác nhau:
Multilevel FeedBack Queue Scheduling cho phép điều chuyển (điều tiết) tiến trình từ hàng chờ này sang hàng chờ kia (hạ cấp độ hay nâng cấp độ ưu tiên), nghĩa là mềm dẻo hơn Multilevel Queue Scheduling.

Như chúng ta đã biết ngoài công cụ Microsoft Project và công cụ Mindjet MindManager Pro 9.1.157 có thể dùng để vẽ biểu đồ Gantt. Hôm nay, mình xin giới thiệu cách vẽ biểu đồ Gantt trong Excel.
Biểu đồ Gantt là loại biểu đồ được sử dụng rộng rãi trong quản lý dự án nó biểu diễn thời gian thực hiện nhiệm vụ trong dự án, giúp cho các nhà quản lý dự án theo dõi và quản lý công việc trơn tru hơn.
Nhìn vào biểu đồ gantt người quản lý dự án, cũng như các thành viên thực hiện dự án biết được:
•Trình tự thực hiện mỗi nhiệm vụ.
•Tiến độ dự án biết được mình đã làm được gì và tiếp tục phải thực hiện công việc đó thế nào, bởi vì mỗi công việc được giao phải hoàn thành trong thời gian đã định.
•Thấy sự phụ thuộc lẫn nhau giữa các công việc.
http://www.tinhoc365.com/images/stories/gantt2.png (hình minh họa)
Mặc dù Excel không có sẵn chức năng tạo biểu đồ Gantt như các phẩm phần mềm khác, nhưng chúng ta vẫn có thể sử dụng Excel tạo ra công cụ quản lý dự án này.
http://www.tinhoc365.com/gantt2.html (video hướng dẫn)
Vì còn thiếu kiến thức và thiếu sót nên monng mọi người góp ý. Thanks!

nguyenvanlinheban (I11C) đã viết:

- Có 3 hàng chờ Ready với độ ưu tiên khác nhau. Hoạt động các tiến trình ở 2 mức trên (Mức 1: Độ 0 và Mức 2: Độ 1) được điều phối bằng thuật giải RRS (Round Robin Scheduling) với thời lượng tương ứng là 8 và 16 ms. Mức 3 (độ ưu tiên thấp nhất) dùng thuật giải FCFS (First-come, first-served Scheduling)(đến trước chạy trước, không có tiếm quyền).
- Đầu tiên, tiến trình mới được đưa vào hàng chờ Mức 1 (Độ 0 là độ ưu tiên cao nhất).
- Hệ điều hành có thể "Hạ cấp" tiến trình bằng cách đưa xuống mức dưới, khi tiến trình đó ảnh hưởng đến hiệu năng toàn hệ (ví dụ, quá "Hướng CPU").
- Theo sơ đồ, có sự "Nâng cấp" tiến trình từ Mức 3 (Độ 2) lên Mức 2 (Độ 1), khi một tiến trình cần được ưu tiên hơn nữa (ví dụ, khi nó làm việc lâu mà vẫn chưa xong hoặc trước đó quá "Hướng I/O" mà bây giờ cần CPU để nhanh chóng hoàn tất công việc).

Hôm đó mình có chép lại lời thầy giảng, nên xin trích tại : Đây là hệ thống phục vụ các tiến trình; tiến trình có độ ưu tiên cao nhất được xếp vào hàng đợi đầu tiên. Tiến trình khi vào đều được xếp vào hàng đợi đầu tiên sau đó mới di chuyển xuống các mức ưu tiên thấp hơn (có xảy ra hạ cấp tiến trình từ mức trên xuống mức dưới), xong việc ra khỏi tiến trình.

Các Bạn ơi. Có ai hiểu hơn về cách tinh thời gian trung bình của Điều Phối Theo Vòng Robin ko vậy.
Như Slide của thầy. Mình coi mình không hiểu được cách tính TGTB

Tiến Trình Khoảng CPU
P1 53
P2 17
P3 68
P4 24
TTGTB ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms

Bạn nào hiểu cố gắng nói giúp mình đươc ko .Cảm ơn các bạn

NguyenTrongHuy(I11C) đã viết:Các Bạn ơi. Có ai hiểu hơn về cách tinh thời gian trung bình của Điều Phối Theo Vòng Robin ko vậy.
Như Slide của thầy. Mình coi mình không hiểu được cách tính TGTB

Tiến Trình Khoảng CPU
P1 53
P2 17
P3 68
P4 24
TTGTB ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms

Bạn nào hiểu cố gắng nói giúp mình đươc ko .Cảm ơn các bạn

Trước tiên bạn phải hiểu đuợc cách vẽ biểu đồ grant:
thời gian chiếm dụng cpu là 20ms nên các tiến trình chỉ đuợc sử dụng 20 ms rùi chuyển qua tiến trình khác.ở đây các tiến trình thực hiện lần luợt từ từ p1->p4


bạn có thể làm theo công thức
Thời gian chờ = thời điểm tiến trình thực hiện xong - thời điểm - khoảng CPU.

P1= 134 - 53 = 81(ms)
P2= 37 - 17 = 20(ms)
P3= 162 - 68 = 94(ms)
P4 = 121 - 24 = 97(ms)
- Thời gian chờ TB
(81 + 20 +94 + 97)/4 = 73(ms)

hay bạn có thể coi cách giải thich của bạn
DangNgocMinh(I11C) đã viết:


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
[img][/img]

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é

Mình cũng giải ra kết quả như các bạn.
Trong quá trình giải. mình gặp vấn để ở thời điểm P3 được cấp CPU( rất dễ lộn với P1) và trong quá trình tham khảo diễn đàn mình cũng gặp một chủ đề về vấn đề này: https://hedieuhanh.forumvi.com/t1703-topic
mình nghĩ nhiều bạn cũng sẽ vấp phải vấn đề này, mình xin giải thích thêm để các bạn hiểu rõ.

Theo đề ta có thời điểm P3 vào là 25.
Thời điểm thứ 23 ta co hàng đợi là P1 - P2 nên P1 được thực hiện trước và P3 cũng bắt đầu vào từ thời điểm tứ 25 nên ta có hàng đợi P2 - P3.
Thời điểm thứ 33 hàng đợi P2 - P3 - P1 nên thực hiện P2.
Thời điểm thứ 43 hàng đợi P3 - P1 nên P3 thực hiện trước.

Theo đề ta có thời điểm P3 vào là 25.
Thời điểm thứ 23 ta co hàng đợi là P1 - P2 nên P1 được thực hiện trước và P3 cũng bắt đầu vào từ thời điểm tứ 25 nên ta có hàng đợi P2 - P3.
Thời điểm thứ 33 hàng đợi P2 - P3 - P1 nên thực hiện P2.
Thời điểm thứ 43 hàng đợi P3 - P1 nên P3 thực hiện trước.

Mình cũng xin góp ý chút: (BuiHuuThanhLuan)
Theo như biểu đồ Gantt và đề bài:
Ta có thời điểm đến của p3 là 25.
Biểu đồ Gantt thì có p1=13 , p2=23 đều nhỏ hơn p3=25(theo đề bài) nhưng p1 =13 nhỏ nhất nên nó được chạy trước. tiếp tục đến p2=23 (> p3=25) . sau cùng là p3.
Đó là theo cách mình hiểu. Sai xót gì mong mọi người bỏ qua

minhgiangbc đã viết:

NguyenTrongHuy(I11C) đã viết:Các Bạn ơi. Có ai hiểu hơn về cách tinh thời gian trung bình của Điều Phối Theo Vòng Robin ko vậy.
Như Slide của thầy. Mình coi mình không hiểu được cách tính TGTB

Tiến Trình Khoảng CPU
P1 53
P2 17
P3 68
P4 24
TTGTB ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms

Bạn nào hiểu cố gắng nói giúp mình đươc ko .Cảm ơn các bạn

Trước tiên bạn phải hiểu đuợc cách vẽ biểu đồ grant:
thời gian chiếm dụng cpu là 20ms nên các tiến trình chỉ đuợc sử dụng 20 ms rùi chuyển qua tiến trình khác.ở đây các tiến trình thực hiện lần luợt từ từ p1->p4


bạn có thể làm theo công thức
Thời gian chờ = thời điểm tiến trình thực hiện xong - thời điểm - khoảng CPU.

P1= 134 - 53 = 81(ms)
P2= 37 - 17 = 20(ms)
P3= 162 - 68 = 94(ms)
P4 = 121 - 24 = 97(ms)
- Thời gian chờ TB
(81 + 20 +94 + 97)/4 = 73(ms)

hay bạn có thể coi cách giải thich của bạn
DangNgocMinh(I11C) đã viết:


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
[img][/img]

Cảm ơn các bạn nhiều lắm, mình đã hiểu hơn về vấn đề này.

Thuật toán điều phối cần xem xét và quyết định thời điểm chuyển đổi CPU giữa các tiến trình. Hệ điều hành có thể thực hiện cơ chế điều phối theo nguyên lý tiếm quyền hoặc không tiếm quyền.

Điều phối có tiếm quyền : Nguyên lý điều phối có tiếm quyền cho phép một tiến trình khi nhận được CPU sẽ có quyền độc chiếm CPU đến khi hoàn tất xử lý hoặc tự nguyện giải phóng CPU. Khi độc quyết định điều phối CPU sẽ xảy ra trong các tình huống sau:

Khi tiến trình chuyển từ trạng thái đang xử lý(running) sang trạng thái bị khóa blocked ( ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc).

Khi tiến trình kết thúc.

Các giải thuật tiếm quyền thường đơn giản và dễ cài đặt. Tuy nhiên chúng thường không thích hợp với các hệ thống tổng quát nhiều người dùng, vì nếu cho phép một tiến trình có quyền xử lý bao lâu tùy ý, có nghĩa là tiến trình này có thể giữ CPU một thời gian không xác định, có thể ngăn cản những tiến trình còn lại trong hệ thống có một cơ hội để xử lý.

Điều phối không tiếm quyền : Ngược với nguyên lý độc quyền, điều phối theo nguyên lý không tiếm quyền cho phép tạm dừng hoạt động của một tiến trình đang sẵn sàng xử lý. Khi một tiến trình nhận được CPU, nó vẫn được sử dụng CPU đến khi hoàn tất hoặc tự nguyện giải phóng CPU, nhưng một tiến trình khác có độ ưu tiên có thể dành quyền sử dụng CPU của tiến trình ban đầu. Như vậy là tiến trình có thể bị tạm dừng hoạt động bất cứ lúc nào mà không được báo trước, để tiến trình khác xử lý. Các quyết định điều phối xảy ra khi :

Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng thái bị khóa blocked ( ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc).

Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng thái ready ( ví dụ xảy ra một ngắt).

Khi tiến trình chuyển từ trạng thái chờ (blocked) sang trạng thái ready ( ví dụ một thao tác nhập/xuất hoàn tất).

Khi tiến trình kết thúc.

Các thuật toán điều phối theo nguyên tắc không tiếm quyền ngăn cản được tình trạng một tiến trình độc chiếm CPU, nhưng việc tạm dừng một tiến trình có thể dẫn đến các mâu thuẫn trong truy xuất, đòi hỏi phải sử dụng một phương pháp đồng bộ hóa thích hợp để giải quyết.

Trong các hệ thống sử dụng nguyên lý điều phối có tiếm quyền có thể xảy ra tình trạng các tác vụ cần thời gian xử lý ngắn phải chờ tác vụ xử lý với thời gian rất dài hoàn tất! Nguyên lý điều phối có tiếm quyền thường chỉ thích hợp với các hệ xử lý theo lô.

Đối với các hệ thống tương tác(time sharing), các hệ thời gian thực (real time),cần phải sử dụng nguyên lý điều phối không tiếm quyền để các tiến trình quan trọng có cơ hội hồi đáp kịp thời. Tuy nhiên thực hiện điều phối theo nguyên lý không tiếm quyền đòi hỏi những cơ chế phức tạp trong việc phân định độ ưu tiên, và phát sinh thêm chi phí khi chuyển đổi CPU qua lại giữa các tiến trình.

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

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

Cám ơn bạn nhiều, bài giải thích của bạn rất chi tiết và dễ hiểu.

NguyenXuanTri28 đã viết:Bốn tình huống ra quyết định của trình điều phối CPU:
* Các 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 (khi 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 có tiếm quyền(Preemptive Scheduling) và điều phối không tiếm quyền (Non-Preemptive Scheduling)
+ Có tiếm quyền: Điều phối chỉ xảy ra ở thời điểm 1 va 4, không xảy ra điều phối ở thời điểm 2 và 3. 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. Trên HĐH hiện đại đa số có tiếm quyền.
+ Không tiếng quyền: Xảy ra trong cả 4 tình huống. Có thể bắt được tiến đang chạy, không cho độc chiếm CPU

Bạn "NguyenXuanTri28" đã nhầm lẫn giữa điều phối có tiếm quyền và không tiếm quyền rùi kìa.
mình đính chỉnh lại nge.
Đ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 .
Đ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.

DuongKimLong(I111C) đã viết:Tìm hiểu thuật giải: RRS (Round - Robin Scheduling)

1/Hiểu rõ hơn về thuật toán: RRS(Round – Robin Scheduling)
- Mỗi tiến trình sử dụng một lượng nhỏ thời gian cảu CPU(Time quantium –thời gian định lượng q, thường từ 10-100ms. Sau đó được đưa vào cuối ready queue.
- Ready queue được thực hiện theo FIFO(First-In, First-Out)(FIFS)
- Nếu tiến trình có thời gian sử dụng CPU >q, thì bộ định thời gian (timer) sẽ tự nguyện nhường CPU khi kết thúc.Trình lập lịch sẽ chọn

Nguyên tắc: Danh sách sẵn sàng được xử lý như một danh sách vòng, bộ điều phối lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là quantum.
Đây là một giải thuật điều phối không độc quyền: khi một tiến trình sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp trong danh sách. Nếu tiến trình bị khóa hay kết thúc trước khi sử dụng hết thời gian quantum, hệ điều hành cũng lập tức cấp phát CPU cho tiến trình khác. Khi tiến trình tiêu thụ hết thời gian CPU dành cho nó mà chưa hoàn tất, tiến trình được đưa trở lại vào cuối danh sách sẵn sàng để đợi được cấp CPU trong lượt kế tiếp.
Ví dụ:
------>A--------------B--------------C---------------A---------->CPU-------------->
|-----------------------<-----------------------<-----------------------|
ready list
Hình minh hoạ: Điều phối Round Robin
(Tiến trình)__(Thời điểm vào RL)___(Thời gian xử lý)
P1_______________0_______________24
P2_______________1_______________3
P3_______________2_______________3

Nếu sử dụng quantum là 4 milisecondes, thứ tự cấp phát CPU sẽ là :
P1 _ P2 _ P3 ___ P1 ____P1___ P1 ___P1____ P1
0___4____7____10____14____18____22___26 30
Thời gian chờ đợi trung bình sẽ là (0+6+3+5)/3 = 4.66 milisecondes.
Nếu có n tiến trình trong danh sách sẵn sàng và sử dụng quantum q, thì mỗi tiến trình sẽ được cấp phát CPU 1/n trong từng khoảng thời gian q. Mỗi tiến trình sẽ không phải đợi quá (n-1)q đơn vị thời gian trước khi nhận được CPU cho lượt kế tiếp.
* Nhận xét: Vấn đề đáng quan tâm đối với giải thuật RR là độ dài của quantum. Nếu thời lượng quantum quá bé sẽ phát sinh quá nhiều sự chuyển đổi giữa các tiến trình và khiến cho việc sử dụng CPU kém hiệu qủa. Nhưng nếu sử dụng quantum quá lớn sẽ làm tăng thời gian hồi đáp và giảm khả năng tương tác của hệ thống.

LeMInhTien(I11C) đã viết:Đến trước - phục vụ trước (Frist-Come, First-Served Scheduling - FCFS)
- Đơn giản, dễ thực hiện.
- Các tiến trình trong Ready Queue được cấp CPU từ đầu dãy đến cuối dãy theo quy tắc FIFO (First-In, First-Out)
- Thời gian chờ trung bình khá lớn.

Chiến lược FIFO
Nguyên tắc: CPU được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình được đưa vào hệ thống sớm nhất. Đây là thuật toán điều phối theo nguyên tắc độc quyền.
Một khi CPU được cấp phát cho tiến trình, CPU chỉ được tiến trình tự nguyện giải phóng khi kết thúc xử lý hay khi có một yêu cầu nhập / xuất.
A .......... B ........... C -------->CPU------------->
ready list
Hình minh hoạ: Điều phối FIFO
Ví dụ :
Tiến trình------Thời điểm vào RL------Thời gian xử lý
P1 ----------------- 0 ----------------- 24
P2 ----------------- 1 ----------------- 3
P3 ----------------- 2 ----------------- 3
Thứ tự cấp phát CPU cho các tiến trình là :
P1-----------P2-----------P3
0-----------24-----------27 30
Thời gian chờ đợi được xử lý là 0 đối với P1, (24 -1) với P2 và (24+3-2) với P3.
Thời gian chờ trung bình là ( 0+23+25)/3 = 16 milisecondes.
* Nhận xét: Thời gian chờ trung bình không đạt cực tiểu, và biến đổi đáng kể đối với các giá trị về thời gian yêu cầu xử lý và thứ tự khác nhau của các tiến trình trong danh sách sẵn sàng. Có thể xảy ra hiện tượng tích lũy thời gian chờ, khi các tất cả các tiến trình (có thể có yêu cầu thời gian ngắn) phải chờ đợi một tiến trình có yêu cầu thời gian dài kết thúc xử lý.
Giải thuật này đặc biệt không phù hợp với các hệ phân chia thời gian, trong các hệ này, cần cho phép mỗi tiến trình được cấp phát CPU đều đặn trong từng khoảng thời gian.

minhgiangbc đã viết:

NguyenTrongHuy(I11C) đã viết:Các Bạn ơi. Có ai hiểu hơn về cách tinh thời gian trung bình của Điều Phối Theo Vòng Robin ko vậy.
Như Slide của thầy. Mình coi mình không hiểu được cách tính TGTB

Tiến Trình Khoảng CPU
P1 53
P2 17
P3 68
P4 24
TTGTB ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms

Bạn nào hiểu cố gắng nói giúp mình đươc ko .Cảm ơn các bạn

Trước tiên bạn phải hiểu đuợc cách vẽ biểu đồ grant:
thời gian chiếm dụng cpu là 20ms nên các tiến trình chỉ đuợc sử dụng 20 ms rùi chuyển qua tiến trình khác.ở đây các tiến trình thực hiện lần luợt từ từ p1->p4


bạn có thể làm theo công thức
Thời gian chờ = thời điểm tiến trình thực hiện xong - thời điểm - khoảng CPU.

P1= 134 - 53 = 81(ms)
P2= 37 - 17 = 20(ms)
P3= 162 - 68 = 94(ms)
P4 = 121 - 24 = 97(ms)
- Thời gian chờ TB
(81 + 20 +94 + 97)/4 = 73(ms)

hay bạn có thể coi cách giải thich của bạn
DangNgocMinh(I11C) đã viết:


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
[img][/img]

Thank bạn rất rất nhiều .mình hiểu rỏ rùi. ,thank bạn lần nữa nhé

nguyenthingocloan (I11C) đã viết:SJFS có tiếm quyền
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 5
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.
Trả lời:
a)Biểu đồ Gantt:






Giải thích:
Đầu tiên ta vẽ các thời điểm đến:0,2,4,5.
Sai khi chon xong thì khoảng CPU của các tiến trình là:
P1=7-2=5.
P2=4-2=2.
P3=1-1=0 //tiến trình P3 đã thực hiện xong.
P4=4.
==>Các tiến trình còn lại lần lượt là:P2,P4,P1.
b)ta có:
P1=11-2=9ms.
P2=5-4=1ms.
P3=0 ms.//Không có thời gian chờ
P4=7-5=2ms .
Thời gian chờ trung bình =(9+1+0+2)/4=3ms.

Biểu đồ Gaintt: 0 2 4 5 7 11 16

P1

P2

P3

P2

P4

P1

Bài này áp dụng công thức thầy ghi như sau:
Thời gian chờ của P=(thời điểm kết thúc - thời điểm đến - thời gian dùng CPU)
Áp dụng công thức kết hợp với từng thời điểm trên ta có:
P1=16-0-7=9
P2=7-2-4=1
P3=5-4-1=0
P4=11-5-4=2
=> Thời gian chờ trung bình = (9+1+0+2)/4=3ms
biểu đồ gaint mình cũng vẽ chưa được,hjxhjx.Bạn nào chỉ mình zới.