Thảo luận Bài 6

Trang 2 trong tổng số 8 trang Previous  1, 2, 3, 4, 5, 6, 7, 8  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

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

Bài gửi  phamdieptuan (I11C) on 14/10/2011, 08:22

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

Like a Star @ heaven 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 sửa bởi phamdieptuan (I11C) ngày 14/10/2011, 08:52; sửa lần 1.

phamdieptuan (I11C)

Tổng số bài gửi : 21
Join date : 26/08/2011
Age : 29
Đến từ : Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  DoThiNgocNuong (I11C) on 14/10/2011, 08:31

NguyenNgocMyTien(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ẻ.
Số liệu trên biểu đồ Gantt đó bạn.các số trong dấu () là thời gian chờ còn số 4 là số tiến trình.

Bạn Tiên ơi, nếu bạn hiểu về các con số này thì bạn vui lòng giải thích rõ hơn được không. Vì cách tính thời gian chờ trung bình của thuật toán này mfinh không hiểu lắm. Thanks bạn. Cool

DoThiNgocNuong (I11C)

Tổng số bài gửi : 17
Join date : 27/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  minhgiangbc on 14/10/2011, 08:32

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é bom


Được sửa bởi minhgiangbc ngày 14/10/2011, 08:43; sửa lần 1.

minhgiangbc

Tổng số bài gửi : 24
Join date : 16/09/2011
Age : 29
Đến từ : lâm đồng

Xem lý lịch thành viên

Về Đầu Trang Go down

Cảm ơn lý giải của bạn

Bài gửi  nguyenminhlai.(I11C) on 14/10/2011, 08:42

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

Like a Star @ heaven TGCTB = ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms


Mình cũng định hỏi giống bạn Thanh vì chổ này cùng cũng không hiểu mấy.Cảm ơn bạn bạn giả thích dậy làm mình hiểu ra.

nguyenminhlai.(I11C)

Tổng số bài gửi : 24
Join date : 26/08/2011
Age : 28
Đến từ : Quảng Nam

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  HoiHoangHongVu I11C on 14/10/2011, 08:57

chipphonui đã viết:
KimHue36 (I11C) đã viết:
  • Biểu đồ Gantt:

http://imageshack.us/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.

HoiHoangHongVu I11C

Tổng số bài gửi : 37
Join date : 26/08/2011
Đến từ : Biên Hòa - Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  HoiHoangHongVu I11C on 14/10/2011, 09:02

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é bom
2 bạn ơi có thể giải thích rõ hơn ko.

HoiHoangHongVu I11C

Tổng số bài gửi : 37
Join date : 26/08/2011
Đến từ : Biên Hòa - Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

Phân biệt thuật giải Multilevel Queue Scheduling với Multilevel Feedback Queue Scheduling. Cho các ví dụ minh hoạ.

Bài gửi  VoMinhHoang (I11C) on 14/10/2011, 09:27

- 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)
avatar
VoMinhHoang (I11C)

Tổng số bài gửi : 26
Join date : 08/09/2011
Age : 31
Đến từ : Tp Tan An - Long An

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  phamdieptuan (I11C) on 14/10/2011, 09:56

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é bom

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!




phamdieptuan (I11C)

Tổng số bài gửi : 21
Join date : 26/08/2011
Age : 29
Đến từ : Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  HoiHoangHongVu I11C on 14/10/2011, 10:05


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!



[/quote]

Bạn ơi giải thích dùm mình mấy cái dòng máu đỏ.

HoiHoangHongVu I11C

Tổng số bài gửi : 37
Join date : 26/08/2011
Đến từ : Biên Hòa - Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  TranTrungTinh(I11C) on 14/10/2011, 10:09

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ẻ.
Mình có một cách tính thời gian chờ trung bình rất đơn giản.
Thời gian chờ = thời điểm tiến trình thực hiện xong - thời điểm - khoảng CPU.
Bài tập trên lớp của thầy mình tính thời gian chờ là:
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)

TranTrungTinh(I11C)

Tổng số bài gửi : 28
Join date : 30/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

bai tap

Bài gửi  NgoThiCamNhung47 (I11C) on 14/10/2011, 10:10




NgoThiCamNhung47 (I11C)

Tổng số bài gửi : 5
Join date : 26/08/2011
Age : 28

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  phamdieptuan (I11C) on 14/10/2011, 10:26

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



Bạn ơi giải thích dùm mình mấy cái dòng máu đỏ.


+P2 hết tại 43 do nó chạy từ 13->23(dc 10s) thì khi từ 33->43(dc 10s nữa) theo đề nó cần 20s => cung cấp đủ 20s cho P2 rùi ->kết thúc tiến trình P2
+ P3 từ 43->53(10s) mà nó cần 15s(theo đề) thì chỉ cần chạy thêm 5s nữa thôi->kết thúc tiến trình P3 tại giây 38
+ Tương tự cho P1 từ 3->13(10s) và 23->33(10s) và 53->63(10s) mà nó cần 35s(theo đề) thì chỉ cần chạy thêm 5s nữa thôi -> kết thúc tại giây 73




phamdieptuan (I11C)

Tổng số bài gửi : 21
Join date : 26/08/2011
Age : 29
Đến từ : Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  TranTrungTinh(I11C) on 14/10/2011, 10:30

KimHue36 (I11C) đã viết:
  • Biểu đồ Gantt:

http://imageshack.us/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ài tập của bạn giải hình như chưa đúng thì phải. Đây là bài giải của mình các bạn cho ý kiến nha!
|- P1- | - P2 - | - P1 - | - P2 - | - P3 - | - P1 - | - P3 - | - P1 - |
3-----13-----23-----33-----43-------53------63------68------73
Thời gian chờ:
P1=73 - 3 - 35 = 35(ms)
P2=43 - 10 - 20 = 13(ms)
P3=68 - 25 - 15 = 28(ms)
Thời gian chờ trung bình:
(35 + 13 + 28)/3 = 25.33(ms)

TranTrungTinh(I11C)

Tổng số bài gửi : 28
Join date : 30/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  HoiHoangHongVu I11C on 14/10/2011, 10:41

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



Bạn ơi giải thích dùm mình mấy cái dòng máu đỏ.


+P2 hết tại 43 do nó chạy từ 13->23(dc 10s) thì khi từ 33->43(dc 10s nữa) theo đề nó cần 20s => cung cấp đủ 20s cho P2 rùi ->kết thúc tiến trình P2
+ P3 từ 43->53(10s) mà nó cần 15s(theo đề) thì chỉ cần chạy thêm 5s nữa thôi->kết thúc tiến trình P3 tại giây 38
+ Tương tự cho P1 từ 3->13(10s) và 23->33(10s) và 53->63(10s) mà nó cần 35s(theo đề) thì chỉ cần chạy thêm 5s nữa thôi -> kết thúc tại giây 73



Cám ơn bạn rất nhiều . giờ mình hiểu rùi. thanks bạn

HoiHoangHongVu I11C

Tổng số bài gửi : 37
Join date : 26/08/2011
Đến từ : Biên Hòa - Đồng Nai

Xem lý lịch thành viên

Về Đầu Trang Go down

Câu 3: Giải bài tập điều phối CPU dùng thuật giả theo vòng Robin(Roud Robin Scheduling-RRS)

Bài gửi  thanhnam06511c on 14/10/2011, 11:26

Như điều phối kiểu FCFS nhưng cho phép tiếm quyền khi tiến trình đang chạy bị hết thời lượng
Mỗi tiến trình được cấp 1 thời lượng CPU(Time Quantum), thường từ 10-100 mili giây. Sau khoảng thời gian này, nó bị tiếm quyền và được đưa vào cuối hàng chờ Ready. Tiến trình đầu tiên trong hàng chờ Ready được chọn kế tiếp.
Nếu có n tiến trình và thời lượng là q, mỗi tiến trình nhận 1/n thời gian CPU bao gồm các đoạn không qu1 q đơn vị thời gian.
VD: RRs với thời lượng = 20ms(RRS with Time Quantum =20ms)
* Giả sử hàng chờ Ready có các tiến trình sau:
Tiến trình
Khoảng CPU
p1
53
p2
17
p3
68
p4
24
* Thời gian chờ trung bình : (0+57+24)+20+(37+40+17)+(57+40))/4=73ms


thanhnam06511c

Tổng số bài gửi : 16
Join date : 31/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

Ý nghĩa khi vẽ 1 biểu đồ Gantt

Bài gửi  thanhnam06511c on 14/10/2011, 11:30

1. Biểu đồ Gantt là gì?

Biểu đồ Gantt là đồ thị với những thanh nằm ngang để chỉ hoạt động ngược lại với ngày. Đây là công cụ để đo lường tiến độ thực hiện dự án so với kế hoạch đề ra.

Cách vẽ một biểu đồ Gantt:

* Vẽ đường thời gian của dự án/ chương trình từ đầu cho đến cuối dự án trên trục toạ độ (trục tung- nằm ngang);
* Trên trục hoành (ngược lại với trục tung) thể hiện các hoạt động cần được hoàn thành trong suốt dự án/ chương trình;
* Vẽ một thanh nằm ngang ở mỗi mức độ của hoạt động để chỉ khoảng thời gian thực hiện mỗi công việc.

TIP Đối với khoảng thời gian dự kiến thực hiện hoạt động có thể sử dụng một công thức để tính thời gian dự kiến:

Trong đó:
PT là thời gian dài nhất hoạt động có thể diễn ra
ET là thời gian ước tính cho hoạt động thực hiện
OT là thời gian ít nhất khi hoạt động diễn ra
ST là thời gian dự kiến và sử dụng ST trên biểu đồ

2. Tại sao biểu đồ Gantt có ý nghĩa?

Biểu đồ Gantt là một cách đơn giản và dễ hiểu để giám sát tiến độ của các hoạt động khi thực hiện dự án/ chương trình

3. Biểu đồ Gantt hỗ trợ như thế nào?

Biểu đồ Gantt hỗ trợ bạn theo 2 cách chính. Đầu tiên, chúng cung cấp cho bạn hình ảnh trực quan về các hoạt động và thời gian thực hiện. Thứ hai, chúng cho phép bạn truyền đạt động tin bằng một cách dễ dàng với các đồng nghiệp khác trong nhóm về trạng thái của dự án/ chương trình.

4. Biểu đồ Gantt được áp dụng ở đâu?

Biểu đồ Gantt được sử dụng cho bất kỳ dự án/ chương trình để xác định tiến độ và làm rõ mục tiêu. Chúng giúp liên kết giữa mọi người/ nguồn lực trong dự án cùng với nhiều hoạt động trong đó.

5. Biểu đồ Gantt có ý nghĩa khi nào?

Khi bạn đang quản lý một chương trình/ dự án có nhiều hoạt động phức tạp, biểu đồ Gantt được khuyên dùng, đặc biệt nếu bạn yêu cầu lao động đầu vào từ các nguồn khác nhau để hoàn thành các công việc này. Nó giúp bạn nắm rõ được mối quan hệ giữa các công việc, ví dụ khi các công việc thực hiện liên tiếp nhau, hoặc có thể được thực hiện song song.

6. Biểu đồ Gantt đem lại lợi ích cho ai?

Biểu đồ Gantt có lợi cho cả những người quản lý chương trình/ dự án và tất cả những ai tham gia thực hiện công việc trong dự án.

thanhnam06511c

Tổng số bài gửi : 16
Join date : 31/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

4 tình huống ra quyết định của trình điều phối. 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

Bài gửi  thanhnam06511c on 14/10/2011, 11:45

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)

thanhnam06511c

Tổng số bài gửi : 16
Join date : 31/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  NgoDucTuan (I11C) on 14/10/2011, 11:48

phamdieptuan (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?
Cảm ơn các bạn

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é bom

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!



avatar
NgoDucTuan (I11C)

Tổng số bài gửi : 52
Join date : 31/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  NguyenHaThanh97 (I11C) on 14/10/2011, 11:53

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

Like a Star @ heaven TGCTB = ((0+57+24)+20+(37+40+17)+(57+40)) / 4 = 73 ms

Cảm ơn bạn nhiều!!!!

NguyenHaThanh97 (I11C)

Tổng số bài gửi : 22
Join date : 25/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

Phần mềm vẽ biểu đồ Gantt

Bài gửi  DuongTrungTinh(I11C) on 14/10/2011, 11:54

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

DuongTrungTinh(I11C)

Tổng số bài gửi : 31
Join date : 26/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

Năm tiêu chí điều phối CPU

Bài gửi  TRANTHINHPHAT (I11C) on 14/10/2011, 13:15

Năm tiêu chí điều phối CPU là ?

1. Công suất CPU (CPU Utilisation): Thực tế đạt từ 40% - 90% thời gian CPU. CPU càng bận càng tốt.
2. Thông suất hệ thống (Throughput): Số TT hoàn tất trong 1 đơn vị thời gian, ví dụ: 1 TT / giờ, 10 TT / giây.
3. Tổng thời gian làm việc (Turnaround Time): Kể từ khi bắt đầu đến khi kết thúc tiến trình (Bao gồm tổng thời gian chờ tại Ready Queue, tổng thời gian sử dụng CPU, tổng thời gian I/O, …).
4. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
5. Thời gian đáp ứng (Response Time): Thời gian kể từ khi người dùng đặt yêu cầu cho đến khi có phản hồi đầu tiên.

TRANTHINHPHAT (I11C)

Tổng số bài gửi : 52
Join date : 29/08/2011
Age : 27
Đến từ : THU DAU MOT, BINH DUONG

Xem lý lịch thành viên

Về Đầu Trang Go down

Điều phối tiến trình là gì?

Bài gửi  TRANTHINHPHAT (I11C) on 14/10/2011, 13:18

II. Điều phối tiến trình

Trong môi trường đa chương, có thể xảy ra tình huống nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu của các hệ phân chia thời gian (time-sharing) là chuyển đổi CPU qua lại giữa các tiến trình một cách thường xuyên để nhiều người sử dụng có thể tương tác cùng lúc với từng chương trình trong quá trình xử lý.

Để thực hiện được mục tiêu này, hệ điều hành phải lựa chọn tiến trình được xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối thích hợp để thực hiện nhiệm vụ này. Một thành phần khác của hệ điều hành cũng tiềm ẩn trong công tác điều phối là bộ phân phối (dispatcher). Bộ phân phối sẽ chịu trách nhiệm chuyển đổi ngữ cảnh và trao CPU cho tiến trình được chọn bởi bộ điều phối để xử lý.

II.1. Giới thiệu

II.1.1. Mục tiêu điều phối

Bộ điều phối không cung cấp cơ chế, mà đưa ra các quyết định. Các hệ điều hành xây dựng nhiều chiến lược khác nhau để thực hiện việc điều phối, nhưng tựu chung cần đạt được các mục tiêu sau :

a) Sự công bằng ( Fairness) :

Các tiến trình chia sẻ CPU một cách công bằng, không có tiến trình nào phải chờ đợi vô hạn để được cấp phát CPU

b) Tính hiệu qủa (Efficiency) :

Hệ thống phải tận dụng được CPU 100% thời gian.

c) Thời gian đáp ứng hợp lý (Response time) :

Cực tiểu hoá thời gian hồi đáp cho các tương tác của người sử dụng

d) Thời gian lưu lại trong hệ thống ( Turnaround Time) :

Cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô.

e) Thông lượng tối đa (Throughput ) :

Cực đại hóa số công việc được xử lý trong một đơn vị thời gian.

Tuy nhiên thường không thể thỏa mãn tất cả các mục tiêu kể trên vì bản thân chúng có sự mâu thuẫn với nhau mà chỉ có thể dung hòa chúng ở mức độ nào đó.

II.1.2. Các đặc điểm của tiến trình

Điều phối hoạt động của các tiến trình là một vấn đề rất phức tạp, đòi hỏi hệ điều hành khi giải quyết phải xem xét nhiều yếu tố khác nhau để có thể đạt được những mục tiêu đề ra. Một số đặc tính của tiến trình cần được quan tâm như tiêu chuẩn điều phối :

a) Tính hướng xuất / nhập của tiến trình ( I/O-boundedness):

Khi một tiến trình nhận được CPU, chủ yếu nó chỉ sử dụng CPU đến khi phát sinh một yêu cầu nhập xuất ? Hoạt động của các tiến trình như thế thường bao gồm nhiều lượt sử dụng CPU , mỗi lượt trong một thời gian khá ngắn.

b) Tính hướng xử lý của tiến trình ( CPU-boundedness):

Khi một tiến trình nhận được CPU, nó có khuynh hướng sử dụng CPU đến khi hết thời gian dành cho nó ? Hoạt động của các tiến trình như thế thường bao gồm một số ít lượt sử dụng CPU , nhưng mỗi lượt trong một thời gian đủ dài.

c) Tiến trình tương tác hay xử lý theo lô :

Người sử dụng theo kiểu tương tác thường yêu cầu được hồi đáp tức thời đối với các yêu cầu của họ, trong khi các tiến trình của tác vụ được xử lý theo lô nói chung có thể trì hoãn trong một thời gian chấp nhận được.

d) Độ ưu tiên của tiến trình :

Các tiến trình có thể được phân cấp theo một số tiêu chuẩn đánh giá nào đó, một cách hợp lý, các tiến trình quan trọng hơn ( có độ ưu tiên cao hơn) cần được ưu tiên hơn.

e) Thời gian đã sử dụng CPU của tiến trình :

Một số quan điểm ưu tiên chọn những tiến trình đã sử dụng CPU nhiều thời gian nhất vì hy vọng chúng sẽ cần ít thời gian nhất để hoàn tất và rời khỏi hệ thống . Tuy nhiên cũng có quan điểm cho rằng các tiến trình nhận được CPU trong ít thời gian là những tiến trình đã phải chờ lâu nhất, do vậy ưu tiên chọn chúng.

f) Thời gian còn lại tiến trình cần để hoàn tất :

Có thể giảm thiểu thời gian chờ đợi trung bình của các tiến trình bằng cách cho các tiến trình cần ít thời gian nhất để hoàn tất được thực hiện trước. Tuy nhiên đáng tiếc là rất hiếm khi biết được tiến trình cần bao nhiêu thời gian nữa để kết thúc xử lý.

II.1.3. Điều phối không độc quyền và điều phối độc quyền (preemptive/nopreemptive)

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ý độc quyền hoặc không độc quyền.

Điều phối độc quyền : Nguyên lý điều phối độc 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 đó 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 độc 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 độc quyền : Ngược với nguyên lý độc quyền, điều phối theo nguyên lý không độc 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 độc 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 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 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 độc 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 độc 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.

II.2. Tổ chức điều phối

II.2.1. Các danh sách sử dụng trong quá trình điều phối.

Hệ điều hành sử dụng hai loại danh sách để thực hiện điều phối các tiến trình là danh sách sẵn sàng (ready list) và danh sách chờ đợi(waiting list).

Khi một tiến trình bắt đầu đi vào hệ thống, nó được chèn vào danh sách các tác vụ (job list). Danh sách này bao gồm tất cả các tiến trình của hệ thống. Nhưng chỉ các tiến trình đang thường trú trong bộ nhớ chính và ở trạng thái sẵn sàng tiếp nhận CPU để hoạt động mới được đưa vào danh sách sẵn sàng.

Bộ điều phối sẽ chọn một tiến trình trong danh sách sẵn sàng và cấp CPU cho tiến trình đó. Tiến trình được cấp CPU sẽ thực hiện xử lý, và có thể chuyển sang trạng thái chờ khi xảy ra các sự kiện như đợi một thao tác nhập/xuất hoàn tất, yêu cầu tài nguyên chưa được thỏa mãn, được yêu cầu tạm dừng ...Khi đó tiến trình sẽ được chuyển sang một danh sách chờ đợi.

Hệ điều hành chỉ sử dụng một danh sách sẵn sàng cho toàn hệ thống, nhưng mỗi một tài nguyên ( thiết bị ngoại vi ) có một danh sách chờ đợi riêng bao gồm các tiến trình đang chờ được cấp phát tài nguyên đó.

Hình 2.9 Các danh sách điều phối

Quá trình xử lý của một tiến trình trải qua những chu kỳ chuyển đổi qua lại giữa danh sách sẵn sàng và danh sách chờ đợi. Sơ đồ dưới đây mô tả sự điều phối các tiến trình dựa trên các danh sách của hệ thống.

Thoạt đầu tiến trình mới được đặt trong danh sách các tiến trình sẵn sàng (ready list), nó sẽ đợi trong danh sách này cho đến khi được chọn để cấp phát CPU và bắt đầu xử lý. Sau đó có thể xảy ra một trong các tình huống sau :

Tiến trình phát sinh một yêu cầu một tài nguyên mà hệ thống chưa thể đáp ứng, khi đó tiến trình sẽ được chuyển sang danh sách các tiến trình đang chờ tài nguyên tương ứng.

Tiến trình có thể bị bắt buộc tạm dừng xử lý do một ngắt xảy ra, khi đó tiến trình được đưa trở lại vào danh sách sẵn sàng để chờ được cấp CPU cho lượt tiếp theo.

Hình 2.10 Sơ đồ chuyển đổi giữa các danh sách điều phối

Trong trường hợp đầu tiên, tiến trình cuối cùng sẽ chuyển từ trạng thái blocked sang trạng thái ready và lại được đưa trở vào danh sách sẵn sàng. Tiến trình lặp lại chu kỳ này cho đến khi hoàn tất tác vụ thì được hệ thống hủy bỏ khỏi mọi danh sách điều phối.

II.2.2. Các cấp độ điều phối

Thực ra công việc điều phối được hệ điều hành thực hiện ở hai mức độ : điều phối tác vụ (job scheduling) và điều phối tiến trình ( process scheduling).

a) Điều phối tác vụ

Quyết định lựa chọn tác vụ nào được đưa vào hệ thống, và nạp những tiến trình của tác vụ đó vào bộ nhớ chính để thực hiện. Chức năng điều phối tác vụ quyết định mức độ đa chương của hệ thống ( số lượng tiến trình trong bộ nhớ chính). Khi hệ thống tạo lập một tiến trình, hay có một tiến trình kết thúc xử lý thì chức năng điều phối tác vụ mới được kích hoạt. Vì mức độ đa chương tương đối ổn định nên chức năng điều phối tác vụ có tần suất hoạt động thấp .

Để hệ thống hoạt động tốt, bộ điều phối tác vụ cần biệt tính chất của tiến trình là hướng nhập xuất (I/O bounded) hay hướng xử lý ( CPU bounded). Một tiến trình được gọi là hướng nhập xuất nếu nó chủ yếu nó chỉ sử dụng CPU để thực hiện các thao tác nhập xuất. Ngược lại một tiến trình được gọi là hướng xử lý nếu nó chủ yếu nó chỉ sử dụng CPU để thực hiện các thao tác tính toán. Để cân bằng hoạt động của CPU và các thiết bị ngoại vi, bộ điều phối tác vụ nên lựa chọn các tiến trình để nạp vào bộ nhớ sao cho hệ thống là sự pha trộn hợp lý giữa các tiến trình hướng nhập xuất và các tiến trình hướng xử lý

b) Điều phối tiến trình

Chọn một tiến trình ở trạng thái sẵn sàng ( đã được nạp vào bộ nhớ chính, và có đủ tài nguyên để hoạt động ) và cấp phát CPU cho tiến trình đó thực hiện. Bộ điều phối tiến trình có tần suất hoạt động cao, sau mỗi lần xảy ra ngắt ( do đồng hồ báo giờ, do các thiết bị ngoại vi...), thường là 1 lần trong khoảng 100ms. Do vậy để nâng cao hiệu suất của hệ thống, cần phải tăng tốc độ xử lý của bộ điều phối tiến trình. Chức năng điều phối tiến trình là một trong chức năng cơ bản, quan trọng nhất của hệ điều hành.

Trong nhiều hệ điều hành, có thể không có bộ điều phối tác vụ hoặc tách biệt rất ít đối với bộ điều phối tiến trình. Một vài hệ điều hành lại đưa ra một cấp độ điều phối trung gian kết hợp cả hai cấp độ điều phối tác vụ và tiến trình


TRANTHINHPHAT (I11C)

Tổng số bài gửi : 52
Join date : 29/08/2011
Age : 27
Đến từ : THU DAU MOT, BINH DUONG

Xem lý lịch thành viên

Về Đầu Trang Go down

Bài tập làm thêm

Bài gửi  phamngoctan095 (I11C) on 14/10/2011, 13:56

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!

phamngoctan095 (I11C)

Tổng số bài gửi : 12
Join date : 26/08/2011
Age : 29
Đến từ : Miền Tây

Xem lý lịch thành viên

Về Đầu Trang Go down

Bài tập SJFC

Bài gửi  LeTanDat (I11C) on 14/10/2011, 13:59

Đây là vài bài tập và bài giải thuật giải SJFC có tiếm quyền . Các bạn tham khảo cho ý kiến nha!

http://www.mediafire.com/?bx7zkjkdzmsh4zq


Được sửa bởi LeTanDat (I11C) ngày 14/10/2011, 14:14; sửa lần 1.

LeTanDat (I11C)

Tổng số bài gửi : 24
Join date : 30/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

Phân biệt Thuật Giải Multilevel Queue Scheduling với Multilevel FeedBack Queue Scheduling

Bài gửi  DuongKimLong(I111C) on 14/10/2011, 14:12


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:
Multi

DuongKimLong(I111C)

Tổng số bài gửi : 29
Join date : 26/08/2011

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  Sponsored content


Sponsored content


Về Đầu Trang Go down

Trang 2 trong tổng số 8 trang Previous  1, 2, 3, 4, 5, 6, 7, 8  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết