Tìm hiểu thuật giải: RRS (Round - Robin Scheduling)

DuongKimLong(I111C) 14/10/2011, 14:13

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

LeTanDat (I11C) 14/10/2011, 14:26

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)

DaoQuangSieu (I11C) 14/10/2011, 14:29

thanhnam06511c đã viết: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 với điều phối không tiếm quyền
Sơ đồ điều phối chỉ tiến hành trong tình huống khi tiến trình chuyển từ Running sang Waiting(chờ I/O, chờ tiến trình con) và khi tiến trình chuyển từ Running sang Ready(do ngắt xảy ra) được gọi là điều phối không tiếm quyền(Non-Preemptive): Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc chuyển sang trạng thái Waiting. Dùng khi máy không có Timer.
Sơ đồ điều phối tiến hành trong cả 4 tình huống được gọi là điều phối có tiếm quyền(Preemptive)

Mình xin bổ sung câu của bạn:
-Điều phối không tiếm quyền là chỉ tiến hành trong tình huống 1 và 4 (tiến trình chuyển từ Running sang Waiting và khi tiến trình kết thúc công việc) chứ không có tiến trình chuyển từ Running sang Ready.
Ví dụ: Khi có nhiều người tới mua vé thì người bán vé sẽ bán cho người nào tới trước. Cho dù người tới sau mua vé ít hơn người tới trước thì vẫn bán cho người tới trước...
-Điều phối có tiếm quyền là tiến hành cả trong 4 tình huống mà bạn đưa ra .
Ví dụ: Cũng giống ví dụ trên nhưng khác ở chỗ. Ai mua ít vé hơn thì ưu tiên cho người đó( A mua 1 vé, B mua 5 vé, C mua 3 vé thì mức độ ưu tiên sẽ là A,C rồi mới tới B).

NguyenNgocMyTien(I11C) 14/10/2011, 14:42

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

nguyenminhlai.(I11C) 14/10/2011, 15:02

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:

a/ Biểu đồ gant:
Thảo luận Bài 6 - Page 3 Gantt-1

b/ Thời gian chờ:
p1 = 73 - 3 - 35 = 35
p2 = 43 - 10 - 20 = 13
p3 = 68 - 25 - 15 = 28
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
= (35 + 13 + 28) / 3= 25,3333 ms

NguyThiGai (I11C) 14/10/2011, 15:07

phamdieptuan (I11C) đã viết:
DangNgocMinh(I11C) đã viết:

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 đồng ý với kq của bạn đưa ra, và mình xin giải thích thêm về cái biểu đồ Gantt cho các bạn khác dc hiểu rõ hơn:

1. Thời điểm 3: P1 bắt đầu chạy 10 ms
2. Thời điểm 13: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 23: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 13, P3 đang chờ ở thời điểm 25)
4. Thời điểm 33: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 23, P3 đang chờ ở thời điểm 25 )
5. Thời điểm 43: P3 được chạy trước P1 (vì P3 đang chờ trước ở thời điểm 25 còn P1 là 33 )(P2 hết)
6. Thời điểm 53: P1 được tiếm quyền P3 (vì P1 đang chờ ở thời điểm 33 )
6. Thời điểm 63: P3 được tiếm quyền P1 (vì P3 đang chờ ở thời điểm 53 và chạy hết 5s(68s kết thúc))
7. Cuối cùng chỉ còn P1 sẽ chạy hết thời gian còn lại(5s nữa và kết thúc tại 73s).

Quan trọng là làm ra cái biểu đồ này, còn tính tb thì chỉ cần áp dụng công thức thầy cung cấp là dc.
Chúc các bạn thành công!

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

NguyenNgocMyTien(I11C) 14/10/2011, 15:21

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...*_~...

phamdieptuan (I11C) 14/10/2011, 15:21

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

NguyenNgocMyTien(I11C) 14/10/2011, 15:32

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

Đáp án của mình giống bạn phamdieptuan (I11C)

phamngoctan095 (I11C) 14/10/2011, 15:46

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

oh, theo mình thấy thì bài này và bài tập về nhà hôm qua Thầy cho trên lớp dùng chung thuật giải RRS. Nên mình đồng tình với kết quả của bạn phamdieptuan (I11C), có lẽ bạn LeTanDat (I11C) đã dùng nhằm thuật giải như hôm qua Thầy có đề cập tới trên lớp hay sao ròy á.

phamdieptuan (I11C) 14/10/2011, 15:50

NguyThiGai (I11C) đã viết:
phamdieptuan (I11C) đã viết:
DangNgocMinh(I11C) đã viết:

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 đồng ý với kq của bạn đưa ra, và mình xin giải thích thêm về cái biểu đồ Gantt cho các bạn khác dc hiểu rõ hơn:

1. Thời điểm 3: P1 bắt đầu chạy 10 ms
2. Thời điểm 13: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 23: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 13, P3 đang chờ ở thời điểm 25)
4. Thời điểm 33: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 23, P3 đang chờ ở thời điểm 25 )
5. Thời điểm 43: P3 được chạy trước P1 (vì P3 đang chờ trước ở thời điểm 25 còn P1 là 33 )(P2 hết)
6. Thời điểm 53: P1 được tiếm quyền P3 (vì P1 đang chờ ở thời điểm 33 )
6. Thời điểm 63: P3 được tiếm quyền P1 (vì P3 đang chờ ở thời điểm 53 và chạy hết 5s(68s kết thúc))
7. Cuối cùng chỉ còn P1 sẽ chạy hết thời gian còn lại(5s nữa và kết thúc tại 73s).

Quan trọng là làm ra cái biểu đồ này, còn tính tb thì chỉ cần áp dụng công thức thầy cung cấp là dc.
Chúc các bạn thành công!
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 đồng ý với đáp án này của bạn.

namzhou(I11C) 14/10/2011, 17:07

DuongTrungTinh(I11C) đã viết:Mình xin giới thiệu 1 phần mềm vẽ biểu đồ Gantt, bản thân mình cũng chưa sử dụng nhưng xin post lên đây cho bạn nào thích tìm tòi học hỏi.

Mindjet MindManager Pro 9.1.157

Mindjet MindManager Pro biến những ý tưởng động não, tư duy chiến lược, và thông tin kinh doanh vào bản thiết kế cho hành động, cho phép các đội, tổ chức để làm việc nhanh hơn, thông minh hơn, và có sự phối hợp lớn hơn.

MindManager thông tin hình ảnh của bản đồ (bản đồ tâm trí) bắt đầu với một chủ đề trung tâm, và sau đó thêm các chi nhánh với những ý tưởng, ghi chú, hình ảnh, nhiệm vụ, siêu liên kết và tập tin đính kèm. Dễ dàng nhập khẩu từ hoặc xuất khẩu cho Microsoft Office. Sử dụng bản đồ MindManager để nắm bắt và tổ chức thông tin, và bạn sẽ nhanh chóng chuyển đổi suy nghĩ và ý tưởng của bạn vào các văn bản điều chỉnh, thuyết trình hấp dẫn và chiến lược chiến thắng. MindManager mang đến cho bạn một cách tốt hơn để động não, tổ chức sự kiện, dự án kế hoạch, và giao tiếp kết quả.

Tính năng

Thông tin hàng đầu Visualizations

Dễ dàng đặt ra, tổ chức và làm việc với những ý tưởng và thông tin trong một loạt các định dạng tương tác trực quan bao gồm các bản đồ thông tin, phác thảo, biểu đồ Gantt, biểu đồ tổ chức, sơ đồ cây và một chế độ động não đặc biệt.

Dự án & Quản lý công tác

Cải thiện dự án quy hoạch do động não và theo dõi chi tiết công việc, tự động tính toán nhiệm vụ tổng kết và tối ưu hóa sử dụng tài nguyên. Xem MindManager, Outlook, nhiệm vụ * SharePoint trong khung nhìn Gantt mới đồng bộ, nhiệm vụ xuất khẩu cho Microsoft Project.

Bản đồ thông tin trình bày

Giới thiệu ý tưởng của bạn và tham gia tăng sử dụng xem trình chiếu tự động MindManager hoặc các trình diễn tùy biến. Với các bài thuyết trình năng động của MindManager, bạn dễ dàng chỉnh mức độ chi tiết trình bày cho mỗi khán giả và sẽ thu hồi quyền quan trọng trong việc trình bày.

Tích hợp và chia sẻ

Tiết kiệm thời gian và hưởng lợi từ việc tích hợp mạnh mẽ. Truy cập và cập nhật Microsoft Office tích hợp các tập tin trong trình duyệt của MindManager. Nhập khẩu từ Microsoft Word và dự án. Xuất khẩu sang dự án, Word hay PowerPoint. Hiển thị năng động Outlook hoặc nội dung Excel. Xuất khẩu các trang web, hình ảnh, tập tin PDF và nhiều hơn nữa. Hoặc, chia sẻ các tập tin được lưu trữ bản đồ tương tác với bất kỳ ai trên web ngay cả khi họ không có MindManager.

Chụp Nội dung & Thêm Bối cảnh

Dễ dàng thêm các siêu liên kết, tập tin đính kèm, ghi chú, hình ảnh, và bảng tính để cung cấp cấp thêm chi tiết. Nhanh chóng kéo và thả nội dung để tổ chức lại nó và cung cấp các cấu trúc. Sử dụng các biểu tượng, thẻ, hình dạng chủ đề, ghi chú, biên giới, màu sắc, chủ đề phân loại và đánh số để cung cấp các bối cảnh khác.

Link Download:
http://www.fshare.vn/file/TQSTHAMSVT/
Mirror: http://www.mediafire.com/?kynmy9duj5p584a
(Nguồn http://www.phimdaily.net)

Trong bộ công cụ Microsoft Office cũng hỗ trợ vẽ biểu đồ Gantt, các bạn có thể tham khảo thêm link dưới, vẽ trên Excel.
http://www.tinhoc365.com/gantt2.html

Mindjet vẽ dc biểu đồ Gantt ah!
Bữa giờ đang dùng thằng này làm mấy cái project
Để nghiên cứu chức năng làm biểu đồ Gantt xem seo
Thanks bạn lol!

buithithudung24 (i11c) 14/10/2011, 17:56

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

KimHue36 (I11C) 14/10/2011, 19:11

HoiHoangHongVu I11C đã viết:
chipphonui đã viết:
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

bạn ơi hình như biểu đồ sai thì phải? mình dùng giải thuật round robin với thời lượng là 10MS mà. rất sory vì mình chưa giải bài này trên máy, mình mới giải trên giấy thui. và thời gian chờ TB là 25.
đây là ý kiến của mình, có gì không phải xin bỏ qua nha.thanks
Hình như bạn bị sai rùi: Mình chỉ giải tren giấy:
Tại thời điểm 3: p1 bắt đầu chạy 10ms.
Tại thời điểm 13: p2 tiếm quyền p1 vì p2 đang chờ ở thời điểm 10
tại thời điểm 23: p1 tiếm quyền p2 vì p1 đang ở thời điểm 13.
tại thời điểm 33: p3 tiếm quyền p1 vì p3 đang ở thời điểm 25.

Tại mình nghĩ có thời điểm đến nên mình mới làm như vậy, còn ví dụ của thầy k có thời điểm đến nên mình chưa có hiểu . nếu các bạn đều ra kết quả giống nhau thì để mình hỏi lại thầy như thế nào.

LeMInhTien(I11C) 14/10/2011, 22:48

Đế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.

tranleanhngoc88(i11c) 14/10/2011, 23:09

* Giống nhau:
- Đều sử dụng nhiều hàng chờ với độ ưu tiên khác nhau.
- Mỗi hàng chờ sử dụng giải thuật riêng
* Khác nhau:
- MQFS: có thể điều tiết tiến trình từ hàng chờ này sang hàng chờ khác.
- MQS: không thể điều tiết tiến trình từ hàng chờ này qua hàng chờ khác, dù có hàng chờ quá tải, còn hàng chờ khác thì trống.

Tranvancanh(I11C) 15/10/2011, 08:54

Các bạn tham khảo bài tập này nhé.
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	5	47
P2	23	15
P3	45	28

Dùng thuật giải Round-Robin với thời lượng bằng 20 ms để điều phối CPU:
a. Thể hiện bằng biểu đồ Gantt (0,5 điểm)
b. Tính thời gian chờ trung bình của các tiến trình (0,5 điểm)
Trả lời:
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:
- Thời gian chờ của các tiến trình:
Thời điểm 5: P1 bắt đầu chạy 20ms
Thời điểm 25 : P2 tiếm quyền P1 (vì P2 đang chờ ở thời điểm 23).
Thời điểm 40 : P1 tiếm quyền lại P2 ( vì P1 đang chờ ở thời điểm 40, P3 đang chờ ở thời điểm 60)(P2 hết).
Thời điểm 60: P3 tiếm quyền P1 ( P3 chờ tại thời điểm 60).
Thời điểm 80: P1 tiếm quyền p3 (P1 đang chờ tại thời điểm 80 và chạy hết 7ms)(87ms kết thúc.)
Cuối cùng chỉ còn P3 chạy hết thời gian còn lại (8ms nữa sẽ kết thúc và dừng lại ở 95ms).
Kết quả:
P1 = 35 ms.
P2 = 2 ms.
P3 = 22 ms.
- Thời gian chờ trung bình = ( 35 + 2 + 22 ) / 3 = 59 / 3 = 19,66 ms

LaVanKhuong (I11C) 15/10/2011, 09:00

Tiếm quyền(Chiếm quyền) có nghĩa là lấy lại CPU kể cả khi tiến trình chưa thưc hiện xong.
Không tiếm quyền có nghĩa là không bắt được tiến trình phải trả CPU khi mà nó chưa kết thúc công việc

câu 4 phân biệt thuật giải(Multilevel Queue Scheduling -MQS) với giải thuật Multilevel Feeback Queue Scheduling- MFQS ), cho ví dụ minh hoa?
Giống :
Mỗi hàng chờ sử dụng giải thuật riêng
Đều sử dụng nhiều hàng chờ với độ ưu tiên khác nhau.
Khác :
MQS: không thể điều tiết tiến trình từ hàng chờ này qua hàng chờ khác, dù có hàng chờ quá tải.
MQFS: có thể điều tiết tiến trình từ hàng chờ này sang hàng chờ khác.

ví dụ về GA HÒA HƯNG mà thầy giảng trên lớp:
Ga Hòa Hưng có 5 cửa bán vé và mọi người xếp hàng mua vé mỗi cửa(tiến trình).Trong đó chỉ có một cô bán vé(Chính lá CPU)
Khách hàng yêu tiên là các khách hàng hệ thống xếp của thứ nhất(người thân của các nhân viên làm việc tại ga)
Khách hàng yêu tiên thấp hơn xếp cửa thứ hai
Khách hàng bình thường và vãng lai cửa thứ ba
Khách hàng mức độ thấp hơn thì cửu thứ tư
Khách hàng mức thấp nhất chính là sinh viên
Mình chỉ ghi được thế này bạn nào thấy thiếu gì có thể bổ xung nhé để có nội dung đầy đủ hơn cám ơn!!! Smile

tranleanhngoc88(i11c) 15/10/2011, 09:46

- Trong các hệ đa chương thực thi nhiều chương trình đồng thời làm tăng hiệu suất hệ thống.
- Tại mỗi thời điểm, chỉ có 1 process được thực thi. Do đó cần phải giải quyết vấn đề phân chia, lực chọn process thực thi sao cho hiệu quả nhất.

minhgiangbc 15/10/2011, 10:36

phamngoctan095 (I11C) đã viết:
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

oh, theo mình thấy thì bài này và bài tập về nhà hôm qua Thầy cho trên lớp dùng chung thuật giải RRS. Nên mình đồng tình với kết quả của bạn phamdieptuan (I11C), có lẽ bạn LeTanDat (I11C) đã dùng nhằm thuật giải như hôm qua Thầy có đề cập tới trên lớp hay sao ròy á.

----------------------------------------------------------------------------------
Mình cũng làm bài giống các bạn,mà mình giải thích cho rõ hơn về thuật giải nhé:

- Thời điểm 4 P1 bắt đầu chạy hết thời luợng 20ms là thời điểm 24
- tại Thời điểm 24 do P2 và P3 chưa tới thời điểm (30và 51) nên P1 chạy tiếp thời lượng 20ms nữa là 44.
- tại Thời điểm 44 lúc này P1 đưa vào hàng chờ ,P2 đã tới thời điểm của nó là 30 ,nên P2 chạy thời lượng 20ms nữa là 64.
- tại Thời điểm 64 lúc này P1 còn (46-20-20)=6 chờ ở tđ 44, P2 còn (28-20)=8 chờ ở tđ 64,P3 thời điểm 51 mới chạy,do thời gian chiếm dung cpu ít nên lúc này P1 được ưu tiên chạy 6 còn lại là 70.
-- tại Thời điểm 70 : P1 đã chạy hết, P2 chờ ở tđ 64, P3 chờ ở tđ 51, nên P3 chạy thời lượng 20ms là 90.
-- tại Thời điểm 90 : P2 chờ ở tđ 64,P3 chờ ở tđ 90,nên P2 chạy 8 còn lại là 98.
--tại Thời điểm 98 : chỉ còn P3.P3 chạy đến hết là 111

Tạ Hoàng Tân 102C 15/10/2011, 13:25

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

phamdieptuan (I11C) 15/10/2011, 15:46

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.

HoiHoangHongVu I11C 15/10/2011, 18:19

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.

DangNgocMinh(I11C) 15/10/2011, 19:58

Bài này mình lấy đề khóa trước các bạn xem cho ý kiến nha

Thảo luận Bài 6 - Page 3 1318683396110783077_574_574

Nguyenminhduc (I11C) 15/10/2011, 19:59

* Giải thuật Multilevel Queue Scheduling:
- Độ ưu tiên cố định.
- Chia làm 2 mức tiến trình:Tiến trình có độ ưu tiên cao và tiến trình có độ ưu tiên thấp
- Tiến trình nào được ưu tiên cao nhất thì được chạy trước.Tiến trình được ưu tiên thấp nhất thì chạy sau cùng.Đang chạy tiến trình mức dưới mà có tiến trình mức cao hơn thì tiến trình mức dưới bị tiếm quyền cho tiến trình có mức ưu tiên cao hơn.
ví dụ:mức tiến trình tương tác(Interactive) chạy ở mặt trước(foreground) và mức tiến trình lô(batch) chạy ở trong hậu trường.
* Giải thuật Multilevel Feedback Queue Scheduling:
- Có thể điều tiết mức ưu tiên của các tiến trình.Những tiến trình hướng CPU được đưa xuống mức dưới,tiến trình hướng I/O được chuyển lên trên.
- Chia làm 2 mức tiến trình:Tiến trình mức trên và tiến trình mức dưới
- Đặc trưng:
+ Số mức(số hàng chờ)
+ Phương thức nâng cấp tiến trình và 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
ví dụ:Trong nhà hàng,khi đang có khách thì người nhân viên phục ưu tiên phục vụ thực khách hơn là những người khác(cấp trên,đồng nghiệp hay cá nhân)

Sponsored content

Thảo luận Bài 6

Tìm hiểu thuật giải: RRS (Round - Robin Scheduling)

Re: Thảo luận Bài 6

Phân biệt điều phối có tiếm quyền và không tiếm quyền !!!

Bài tập về nhà.

Bài tập về nhà

Giải bài tập về nhà với thời lượng 20ms

Re: Thảo luận Bài 6

Re: Thảo luận Bài 6

Re: Thảo luận Bài 6

Re: Thảo luận Bài 6

Re: Thảo luận Bài 6

Re: Thảo luận Bài 6

Giải thích hình cuối cùng của chương 6 "Điều phối hàng chờ nhiều mức có điều tiết"?

Re: Thảo luận Bài 6

Giải thuật điều phối FCFS

Phân biệt giải thuật Multilevel Queue Scheduling (MQS) và Multilevel Queue Scheduling (MFQS)

Re: Thảo luận Bài 6

Re: thế nào là tiếm quyền và không tiếm quyền?ví dụ câu 4 của thầy

Vì sao hệ điều hành phải có chức năng điều phối CPU

Re: Thảo luận Bài 6

Re: Thảo luận Bài 6

Re: Thảo luận Bài 6

Re: Thảo luận Bài 6

Bài tập SJFS

Phân biệt thuật giải Multilevel Queue Scheduling_MQS và thuật giải Multilevel Feedback Queue Scheduling_MFQS.Cho vd minh họa?

Re: Thảo luận Bài 6