Thảo luận Bài 6
+88
dongocthien (I11C)
lengocthuthao89 (i11c)
PhamThiHoa-I91C
TranTrungKien (I11C)
TrinhThiPhuongThaoI11C
HoangThanhChuong (I11C)
nguyenduc_gia.18(I11c)
doanhongdao030(I11C)
HuynhVanNhut (I11C)
TranQuyThanh (I11C)
LeMinhDuc (I11C)
TranHaDucHuy (I11c)
PhamDuyPhuong87(I11C)
TrinhThiOanh (I11C)
LeThiThuyDuong (I11C)
nguyenhoangthinh (I11C)
TranVuThuyVan_(I11C)
tranvanhai_21(I11c)
nguyenquoctruong (I11C)
lamhuubinh(I91C)
NguyenThiThanhThuy(I11C)
NguyenCongVinh(102C)
hoangdung_I91C
huyentran_I11C
08H1010052
vohongcong(I111C)
HoangNgocQuynh(I11C)
LE DUY NHAT AN (I91C)
NguyenDoTu (I11C)
LyHuynhThanhYen (I11C)
chauthanhvy146(I11C)
ThanhThao04(I11C)
BuiHoangTuan.131.I11C
ngocquynh2091(i11C)
BuiHuuThanhLuan(I11C)
NguyenTrongHuy(I11C)
NguyenThiMinhHuong(I11C)
DaoVanHoang (I11C)
PhamAnhKhoa(I11C)
AnhDuong
XuanThai_I11C
nguyenthithuylinh (I11C)
Duongthithanhhuynh (I11C)
Nguyenminhduc (I11C)
Tạ Hoàng Tân 102C
LaVanKhuong (I11C)
Tranvancanh(I11C)
tranleanhngoc88(i11c)
LeMInhTien(I11C)
buithithudung24 (i11c)
namzhou(I11C)
NguyThiGai (I11C)
DaoQuangSieu (I11C)
DuongKimLong(I111C)
LeTanDat (I11C)
phamngoctan095 (I11C)
TRANTHINHPHAT (I11C)
DuongTrungTinh(I11C)
NgoDucTuan (I11C)
thanhnam06511c
NgoThiCamNhung47 (I11C)
TranTrungTinh(I11C)
VoMinhHoang (I11C)
HoiHoangHongVu I11C
nguyenminhlai.(I11C)
minhgiangbc
DoThiNgocNuong (I11C)
phamdieptuan (I11C)
hongthuanphong (I11C)
NgoLeYen48(I11C)
DangNgocMinh(I11C)
dangminhthinh2107
NguyenNgocMyTien(I11C)
tranvantoan83(I11c)
NguyenHaThanh97 (I11C)
nguyenvanlinheban (I11C)
chipphonui
TranThanhHoang(I91C)
caotanthanh(i11c)
KimHue36 (I11C)
NguyenThanhTam (I11C)
nguyenthingocloan (I11C)
DoThuyTien16 (I11C)
NguyenDinhHop (I11C)
tranphanhieu36_i11c
NguyenXuanTri28
hoangquocduy.i11c
Admin
92 posters
Trang 7 trong tổng số 8 trang
Trang 7 trong tổng số 8 trang • 
1, 2, 3, 4, 5, 6, 7, 8
Trình bày 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ều phối không tiếm quyền
TranHaDucHuy (I11c) 26/10/2011, 01:06
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
* 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
TranHaDucHuy (I11c)- Tổng số bài gửi : 10
Join date : 02/09/2011
Các thuật giải căn bản trong điều phối CPU
LeMinhDuc (I11C) 26/10/2011, 22:56
1. Trình bày thuật giải điều phối FCFS.
Đến trước - Phục vụ trước (First-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.
2. Trình bày thuật giải điều phối PS.
- Mỗi tiến trình được cấp một số nguyên (Priority Number) dùng để ấn định Độ ưu tiên.
- CPU luôn dành cho tiến trình với độ ưu tiên cao hơn (Priority Number nhỏ hơn Độ ưu tiên cao hơn ) với 2 phương án:
Có tiếm quyền ( Preemptive )
Không tiếm quyền ( Non-Preemptive )
- SJFS là trường hợp đặc biệt của PS với độ ưu tiên:
P= ( Khoảng CPU kế tiếp )
3. Trình bày thuật giải điều phối SJFS.
Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)
- Đúng hơn phải được gọi là Shortest-Next-CPU-Burst, nghĩa là tiến trình có Khoảng CPU kế tiếp nhỏ hơn thì được chạy trước. Trong trường hợp bằng nhau, dùng thuật giải FCFS.
- Là giải thuật khá tối ưu, nhưng phải biết cách ước đoán khoảng CPU kế tiếp.
- SJFS không tiếm quyền (Non-Preemptive SJFS): Tiến trình hiện thời được thực hiện đến hết khoảng CPU của nó.
- SJFS có tiếm quyền (Preemptive SJFS): Tiến trình mới có Next CPU Burst nhỏ hơn khoảng thời gian CPU còn lại của tiến trình đang vận hành sẽ được chọn thay thế (Shortest Remaining First).
4. Trình bày thuật giải điều phối RRS.
- 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 quá q đơn vị thời gian.
5. Trình bày thuật giải điều phối MQS.
- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
- Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
Phân bổ theo tỉ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.
Đến trước - Phục vụ trước (First-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.
2. Trình bày thuật giải điều phối PS.
- Mỗi tiến trình được cấp một số nguyên (Priority Number) dùng để ấn định Độ ưu tiên.
- CPU luôn dành cho tiến trình với độ ưu tiên cao hơn (Priority Number nhỏ hơn Độ ưu tiên cao hơn ) với 2 phương án:
Có tiếm quyền ( Preemptive )
Không tiếm quyền ( Non-Preemptive )
- SJFS là trường hợp đặc biệt của PS với độ ưu tiên:
P= ( Khoảng CPU kế tiếp )
3. Trình bày thuật giải điều phối SJFS.
Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)
- Đúng hơn phải được gọi là Shortest-Next-CPU-Burst, nghĩa là tiến trình có Khoảng CPU kế tiếp nhỏ hơn thì được chạy trước. Trong trường hợp bằng nhau, dùng thuật giải FCFS.
- Là giải thuật khá tối ưu, nhưng phải biết cách ước đoán khoảng CPU kế tiếp.
- SJFS không tiếm quyền (Non-Preemptive SJFS): Tiến trình hiện thời được thực hiện đến hết khoảng CPU của nó.
- SJFS có tiếm quyền (Preemptive SJFS): Tiến trình mới có Next CPU Burst nhỏ hơn khoảng thời gian CPU còn lại của tiến trình đang vận hành sẽ được chọn thay thế (Shortest Remaining First).
4. Trình bày thuật giải điều phối RRS.
- 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 quá q đơn vị thời gian.
5. Trình bày thuật giải điều phối MQS.
- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
- Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
Phân bổ theo tỉ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.
LeMinhDuc (I11C)- Tổng số bài gửi : 39
Join date : 26/08/2011
Re: Thảo luận Bài 6
nguyenhoangthinh (I11C) 27/10/2011, 11:58
DuongTrungTinh(I11C) đã viết:nguyenhoangthinh (I11C) đã viết:Bài tập về 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:Dùng thuật giải Round-Robin với thời lượng 10 ms để điều phối CPU:
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)
Trả lời:
a. Thể hiện bằng biểu đồ Gantt:
Ở bài này,các bạn cần chú ý ở ms thứ 23 và 33.Tại thời điểm này tiến trình nào sẽ được sử dụng CPU ???
-ms 23 : nếu không chú ý chúng ta thường cho tiến trình P3 chạy, nhưng theo đề bài thì ms thứ 25 P3 mới được sử dụng CPU, do đó P3 chạy ở đây là sai, mà phải là tiến trình P1 (theo thuật toán FCFS : vào trước phục vụ trước).
-Còn ở ms 33 : sau khi P1 chạy xong thời lượng 10ms và đến ms thứ 33 thì P3 được chay (do ta nghĩ P3 được sử dụng CPU ở ms 25), nếu như vậy cũng là sai, mà ở đây tiến trình P2 sẽ được chạy tiếp theo (cũng theo thuật toán FCFS).
Điều cần lưu ý : Tiến trình nào vào trước sẽ được phục vụ trước, và khi 1 tiến trình nào đó kết thúc thì tiến trình tiếp theo nếu chưa đến thời điểm sử dụng CPU thì sẽ được thay thế bởii 1 tiến trinh khác có thời điểm đến đầu tiên(chạy vòng).
Một ít chia sẻ , có gì sai sót mong các bạn góp ý thêm !!!
Xin cám ơn bạn Thịnh đã giải thích cho mình và các bạn cùng hiểu.Mình cũng xin chia sẻ thêm ở ms thứ 23 tạo sao P1 được chạy? Đó là do P1 đang chờ ở thời điểm ms 13 còn P3 đang chờ ở thời điểm ms 25 nên P1 sẽ phải tiếp tục chạy tiếp. Còn ở thời điểm ms 33 (phần mình tô màu xanh lá) Vì sao P2 được chạy? Vì P2 đang chờ ở thời điểm ms 23 còn P3 đang chờ ở thời điểm ms 25 nên P2 sẽ được chạy.
Mình chỉ giải thích cho rõ hơn ý của bạn Thịnh thôi, có gì sai xin Thầy và các bạn góp ý.
Các bạn có thể xem thêm phần giải thích của thầy qua link này:
https://hedieuhanh.forumvi.com/t3768-topic
Admin
- Nhiều bạn lẫn SJFS với RRS. Hai thuật giải này không liên quan gì đến nhau. Do đó, nếu dùng RRS, tiêu chí duy nhất để bị tiếm quyền sử dụng CPU là hết Thời luợng (Time Quantum).
- Với RRS, khi hết thời lượng, tiến trình hiện hành được đưa vào cuối Ready Queue, còn tiến trình ở đầu danh sách trong Ready Queue sẽ được chọn kế tiếp.
Ở bài tập này, có 3 tiến trình : P1, P2, P3 và chạy theo thứ tự : P1 -> P2 -> P3 .
-Sau khi P1 chạy hết thời lượng 10ms (tức ms thứ 13) thì P1 được đưa vào cuối Ready Queue,và P2 sẽ trở thành tiến trình ở đầu danh sách trong Ready Queue, vậy lúc này thứ tự sẽ là : P2 -> P3 -> P1, do đó P2 sẽ chạy tiếp theo ở ms 13,và sau khi chạy xong ở ms 23 thì P2 sẽ lại được đưa vào cuối Ready Queue,lúc này P3 trở thành đầu => thứ tự : P3 -> P1 -> P2.
-Theo như thứ tự thì P3 sẽ chạy tiếp theo tại thời điểm này (tức ms 23 ), nhưng do ms 25 P3 mới được sử sụng CPU nên P3 sẽ bị đưa vào cuối Ready Queue,vậy nên P1 sẽ trở thành đầu => thứ tự là : P1 -> P2 - > P3 . Do đó, lúc này P1 sẽ được chạy tiếp theo sau P2 ở ms 23.
Và cứ như vậy,khi hết thời lượng, tiến trình hiện hành được đưa vào cuối Ready Queue, còn tiến trình ở đầu danh sách trong Ready Queue sẽ được chọn kế tiếp
nguyenhoangthinh (I11C)- Tổng số bài gửi : 34
Join date : 25/08/2011
Re: Thảo luận Bài 6
tranvanhai_21(I11c) 27/10/2011, 14:37
[quote="LeTanDat (I11C)"]
| 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)
[/quote
cam on cac ban bai viet kha chi tiet minh khong hieu luc Thay giang tren lop cho lam nhung ngam cuu bai ban viet minh da hieu ra.
- Biểu đồ Gantt: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: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!
| 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)
[/quote
cam on cac ban bai viet kha chi tiet minh khong hieu luc Thay giang tren lop cho lam nhung ngam cuu bai ban viet minh da hieu ra.
tranvanhai_21(I11c)- Tổng số bài gửi : 47
Join date : 25/08/2011
Age : 40
Đến từ : Đồng Nai
Re: Thảo luận Bài 6
08H1010052 27/10/2011, 15:54
Bạn phamdieptuan (I11C) giải thích rất rõ ràng dễ hiểu, các bạn nên tham khảo bài này. Thân chào, cám ơn bạn Tuan. Chúc các bạn học tốt.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?
như cách giải mình post trên sẽ có kết quả:
TGCTB= (35+13+28)/3=25,33 msBiể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 đồ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!
Admin
Làm gì có P0 mà lại thấy trong bỉểu đồ Gantt ? Sao chưa ai "thắc mắc" nhỉ ?
08H1010052- Tổng số bài gửi : 52
Join date : 02/07/2010
Năm tiêu chí điều phối CPU
TranQuyThanh (I11C) 28/10/2011, 09:41
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.
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.
TranQuyThanh (I11C)- Tổng số bài gửi : 53
Join date : 30/08/2011
Trình bày thuật giải điều phối MQS
TranQuyThanh (I11C) 28/10/2011, 09:45
- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
- Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
Phân bổ theo tỉ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.
- Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
Phân bổ theo tỉ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.
TranQuyThanh (I11C)- Tổng số bài gửi : 53
Join date : 30/08/2011
Biểu đồ Gantt không có P0
NguyThiGai (I11C) 28/10/2011, 11:07
Có bạn Duongthithanhhuynh (I11C) đó Thầy.
Admin
Làm gì có P0 mà lại thấy trong bỉểu đồ Gantt ? Sao chưa ai "thắc mắc" nhỉ ?
Em cảm ơn Thầy! Em hiểu hơn rồi. Lúc trước, em nghĩ có P0 hay không cũng vậy. Nếu thời gian đó không có tiến trình nào chạy thì giả sử cho P0 chạy. Chỉ cần tính từ tiến trình P1 là được
Đúng là "không Thầy đố mày làm nên" !!!!
NguyThiGai (I11C)- Tổng số bài gửi : 28
Join date : 26/08/2011
Age : 37
Thảo luận bài 6
HuynhVanNhut (I11C) 28/10/2011, 15:28
Các thuật toán lập lịch
1. First Come First Served (FCFS)
Trong thuật toán này, độ ưu tiên phục vụ tiến trình căn cứ vào thời điểm hình thành tiến trình. Hàng đợi các tiến trình được tổ chức theo kiểu FIFO. Mọi tiến trình đều được phục vụ theo trình tự xuất hiện cho dến khi kết thúc hoặc bị ngắt.
Ưu điểm của thuật toán này là giờ CPU không bị phân phối lại (không bị ngắt )chi phí tổ chức thực hiện rất thấp (vì không phải thay đổi thứ tự ưu tiên phục vụ, thứ tự ưu tiên là thứ tự của tiến trình trong hàng đợi)
Nhược điểm của thuật toán là thời gian trung bình chờ phục vụ của các tiến trình là như nhau ( không kể tiến trình ngắn hay dài), do đó dẫn tới 3 nhược điểm sau:
- thời gian chờ trung bình sẽ tăng vô hạn khi hệ thống tiếp cận tới hạn khả năng phục vụ của mình.
- nếu độ phát tán thời gian thực hiện tiến trình tăng thì thời gian chờ đợi trung bình cũng tăng theo.
- khi có tiến trìn dài, ít bị ngắt thì các tiến trình khác phải chờ đợi lâu hơn.
2. Shortest Job First (SJF)
thuật toán SJC xác định thứ tự ưu tiên thực hiện tiến trình dựa vào tổng thời gian thực hiện tiến trình. Tiến trình nào có tổng thời gian thực hiện ngắn sẽ được ưu tiên phục vụ trước.
Ưu điểm của thuật toán là thời giàn chờ đợi trung bình của các tiến trình ngắn hơn so với SCFS. SJF nhanh chóng loại bỏ các tiến trình ngắn, giảm số lượng các tiến trình trong hàng đợi.
Nhược điểm chính của thuật toán là chế độ phân phối lại giờ CPU cũng được áp dụng trong trường hợp ngắt các tiến trình dài đang thực hiện để phục vụ các tiến trình ngắn hơn mới xuất hiện trong hàng đợi. Nếu tiến trình mới xuất hiện có tổng thời gian thực hiện ngắn nhưng vẫn lớn hơn thời gian cần thiết để thực hiện nốt tiến trình đang thực hiện thì việc ngắt tiến trình là không hợp lý.
3. Shortest Remain Time (SRT)
Tương tư như SJF nhưng trong thuật toán này, độ ưu tiên thực hiện các tiến trình dựa vào thời gian cần thiết để thực hiện nốt tiến trình (bằng tổng thời gian trừ đi thời gian đã thực hiện). Như vậy trong thật toán này cần phải thường xuyên cập nhật thông tin về thời gian đã thực hiện tiến trình. Đồng thời, chế độ phân bổ lại giờ CPU cũng phải được áp dụng nếu không sẽ làm mất tính ưu việt của thuật toán.
4. Round Robin (RR)
- Trong thuật toán này, hệ thông quy định một lượng tử thời gain (time quantum) khoảng từ 10-100 mili giây (ms).
- Mỗi tiến trình trong hàng đợi lần lượt được phân phối một lượng tử thời gian để thực hiện. Sau khoảng thời gian đó, nếu tiến trình chưa kết thúc hoặc không rời và trạng thái đợi thì nó được chuyển về cuối hàng đợi.
- Hàng đợi các tiến trình được tổ chức theo kiểu vòng tròn và các tiến trình luôn luôn đảm bảo được phục vụ. khi có tiến trình mới phát sinh, nó sẽ được đưa vào hàng đợi vòng tròn và được đặt ở vị trí phục vụ ngay. Các tiến trình dù ngắn hay dài đều có độ ưu tiên phục vụ như nhau.
- Trên thực tế, để đảm bảo độ ưu tiên cho các tiến trình dài, hệ thống sẽ phân chia các tiến trình thành m lớp. Số lần đươc phục vụ và thời gian một lần phục vụ tiến trình tại mỗi lớp khác nhau (giả sử ở lớp thứ i, tiến trình được phục vụ ki lần và mỗi lần với thời gian qi).
- Nếu sau khoảng thời gian đã được phân phối mà tiến trình chưa kết thúc hoặc không bị ngắt thì nó sẽ được chuyển sang lớp thứ i + 1 ( với ki+1 và qi +1 lớn hơn .). Lượng tử thời gian sẽ tăng dần cho đến khi tiến trình rơi vào lớp ngoài cùng (lớp m). Ở đó nó sẽ được phục vụ với lượng tử qm không đổi. Như vậy thứ tự ưu tiên của các tiến trình sẽ tăng dần theo thời gian xếp hàng đợi.
- Ưu điểm của phương pháp phục vụ đồng mức theo lớp sẽ cho phép hệ thông ưu tiên những tiến trình ngắn (vì nó kết thúc sớm) nhưng nó không gây tổn hại lớn cho các tiến trình dài.
- Nhược điểm là do phải thường xuyên phân phối lại giờ CPU nên thời gian chờ đợi trung bình của Round Robin có thể lớn hơn so với FCFS.
1. First Come First Served (FCFS)
Trong thuật toán này, độ ưu tiên phục vụ tiến trình căn cứ vào thời điểm hình thành tiến trình. Hàng đợi các tiến trình được tổ chức theo kiểu FIFO. Mọi tiến trình đều được phục vụ theo trình tự xuất hiện cho dến khi kết thúc hoặc bị ngắt.
Ưu điểm của thuật toán này là giờ CPU không bị phân phối lại (không bị ngắt )chi phí tổ chức thực hiện rất thấp (vì không phải thay đổi thứ tự ưu tiên phục vụ, thứ tự ưu tiên là thứ tự của tiến trình trong hàng đợi)
Nhược điểm của thuật toán là thời gian trung bình chờ phục vụ của các tiến trình là như nhau ( không kể tiến trình ngắn hay dài), do đó dẫn tới 3 nhược điểm sau:
- thời gian chờ trung bình sẽ tăng vô hạn khi hệ thống tiếp cận tới hạn khả năng phục vụ của mình.
- nếu độ phát tán thời gian thực hiện tiến trình tăng thì thời gian chờ đợi trung bình cũng tăng theo.
- khi có tiến trìn dài, ít bị ngắt thì các tiến trình khác phải chờ đợi lâu hơn.
2. Shortest Job First (SJF)
thuật toán SJC xác định thứ tự ưu tiên thực hiện tiến trình dựa vào tổng thời gian thực hiện tiến trình. Tiến trình nào có tổng thời gian thực hiện ngắn sẽ được ưu tiên phục vụ trước.
Ưu điểm của thuật toán là thời giàn chờ đợi trung bình của các tiến trình ngắn hơn so với SCFS. SJF nhanh chóng loại bỏ các tiến trình ngắn, giảm số lượng các tiến trình trong hàng đợi.
Nhược điểm chính của thuật toán là chế độ phân phối lại giờ CPU cũng được áp dụng trong trường hợp ngắt các tiến trình dài đang thực hiện để phục vụ các tiến trình ngắn hơn mới xuất hiện trong hàng đợi. Nếu tiến trình mới xuất hiện có tổng thời gian thực hiện ngắn nhưng vẫn lớn hơn thời gian cần thiết để thực hiện nốt tiến trình đang thực hiện thì việc ngắt tiến trình là không hợp lý.
3. Shortest Remain Time (SRT)
Tương tư như SJF nhưng trong thuật toán này, độ ưu tiên thực hiện các tiến trình dựa vào thời gian cần thiết để thực hiện nốt tiến trình (bằng tổng thời gian trừ đi thời gian đã thực hiện). Như vậy trong thật toán này cần phải thường xuyên cập nhật thông tin về thời gian đã thực hiện tiến trình. Đồng thời, chế độ phân bổ lại giờ CPU cũng phải được áp dụng nếu không sẽ làm mất tính ưu việt của thuật toán.
4. Round Robin (RR)
- Trong thuật toán này, hệ thông quy định một lượng tử thời gain (time quantum) khoảng từ 10-100 mili giây (ms).
- Mỗi tiến trình trong hàng đợi lần lượt được phân phối một lượng tử thời gian để thực hiện. Sau khoảng thời gian đó, nếu tiến trình chưa kết thúc hoặc không rời và trạng thái đợi thì nó được chuyển về cuối hàng đợi.
- Hàng đợi các tiến trình được tổ chức theo kiểu vòng tròn và các tiến trình luôn luôn đảm bảo được phục vụ. khi có tiến trình mới phát sinh, nó sẽ được đưa vào hàng đợi vòng tròn và được đặt ở vị trí phục vụ ngay. Các tiến trình dù ngắn hay dài đều có độ ưu tiên phục vụ như nhau.
- Trên thực tế, để đảm bảo độ ưu tiên cho các tiến trình dài, hệ thống sẽ phân chia các tiến trình thành m lớp. Số lần đươc phục vụ và thời gian một lần phục vụ tiến trình tại mỗi lớp khác nhau (giả sử ở lớp thứ i, tiến trình được phục vụ ki lần và mỗi lần với thời gian qi).
- Nếu sau khoảng thời gian đã được phân phối mà tiến trình chưa kết thúc hoặc không bị ngắt thì nó sẽ được chuyển sang lớp thứ i + 1 ( với ki+1 và qi +1 lớn hơn .). Lượng tử thời gian sẽ tăng dần cho đến khi tiến trình rơi vào lớp ngoài cùng (lớp m). Ở đó nó sẽ được phục vụ với lượng tử qm không đổi. Như vậy thứ tự ưu tiên của các tiến trình sẽ tăng dần theo thời gian xếp hàng đợi.
- Ưu điểm của phương pháp phục vụ đồng mức theo lớp sẽ cho phép hệ thông ưu tiên những tiến trình ngắn (vì nó kết thúc sớm) nhưng nó không gây tổn hại lớn cho các tiến trình dài.
- Nhược điểm là do phải thường xuyên phân phối lại giờ CPU nên thời gian chờ đợi trung bình của Round Robin có thể lớn hơn so với FCFS.
HuynhVanNhut (I11C)- Tổng số bài gửi : 12
Join date : 07/09/2011
thanks bạn nhiều nha, mình đang học quản lý dự án phần mềm, đang cần phần mềm này để vẽ sơ đồ Gantt.
doanhongdao030(I11C) 28/10/2011, 15:45
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
doanhongdao030(I11C)- Tổng số bài gửi : 17
Join date : 01/09/2011
Thảo luận bài 6
HuynhVanNhut (I11C) 28/10/2011, 16:29
Bốn tình huống ra quyết định của trình điều phối. Phân biệt điều phối không tiếm quyền và có tiếm quyền?
- 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 không tiếm quyền (Non- Preemptive)và có tiếm quyền (Preemptive)
Giống nhau: cùng điều phối CPU (chọn tiến trình trong Ready Queue để cấp thời gian CPU(chuyển sang trạng thái Running)).
Khác nhau: Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phố CPU không tiếm quyền.
Non Preemptive Scheduling: có nghĩa là khi có 1 tiến trình P1,P2 xuất hiện thì nó sẽ thực hiện xong tiến trình P1, sau đó mới thực hiện tiến trình P2 (cách làm trong Windows 3.1 và Macintosh OS)
Preemptive Scheduling: có nghĩa là khi có 1 tiến trình P1,P2,P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình
- 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 không tiếm quyền (Non- Preemptive)và có tiếm quyền (Preemptive)
Giống nhau: cùng điều phối CPU (chọn tiến trình trong Ready Queue để cấp thời gian CPU(chuyển sang trạng thái Running)).
Khác nhau: Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phố CPU không tiếm quyền.
Non Preemptive Scheduling: có nghĩa là khi có 1 tiến trình P1,P2 xuất hiện thì nó sẽ thực hiện xong tiến trình P1, sau đó mới thực hiện tiến trình P2 (cách làm trong Windows 3.1 và Macintosh OS)
Preemptive Scheduling: có nghĩa là khi có 1 tiến trình P1,P2,P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2, sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình
HuynhVanNhut (I11C)- Tổng số bài gửi : 12
Join date : 07/09/2011
Re: Thảo luận Bài 6
nguyenduc_gia.18(I11c) 2/11/2011, 00:59
minh đồng ý vói bạn,mình ghi tuần này thi mình coi kĩ để khoi rótphamngoctan095 (I11C) đã viết:phamdieptuan (I11C) đã viết:LeTanDat (I11C) đã viết:- Biểu đồ Gantt: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: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!
| 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 á.
nguyenduc_gia.18(I11c)- Tổng số bài gửi : 22
Join date : 07/09/2011
Re: Thảo luận Bài 6
hoangdung_I91C 3/11/2011, 08:40
Cảm ơn bạn, sau một thời gian tìm hiểu, thì mình cũng có cách giải giống bạn, ngày trước mình hiểu bị sai vì quên mất RB phải kết hợp với FCFS mới đúng! Cảm ơn bạn, lời giải của bạn theo mình là chính xác.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 msBiể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é
hoangdung_I91C- Tổng số bài gửi : 34
Join date : 07/06/2010
Vòng Round Robin (RR)
HoangThanhChuong (I11C) 3/11/2011, 14:55
Round Robin (RR)
Chế độ quyết định: preemptive
Khoảng thời gian tối đa cho phép (thường 10 - 100 ms) được đảm bảo bằng việc sử dụng timer interrupt
Process đang chạy hết thời gian sẽ được chuyển về cuối của hàng đợi ready
Chiến lược phân phối xoay vòng (RR: Round Robin):
Ready list được thiết kết theo dạng danh sách nối vòng. Tiến trình được bộ điều phối chọn để cấp processor cũng là tiến trình ở đầu ready list, nhưng sau một khoảng thời gian nhất định nào đó thì bộ điều phối lại thu hồi lại processor của tiến trình vừa được cấp processor và chuyển processor cho tiến trình kế tiếp (bây giờ đã trở thành tiến trình đầu tiên) trong ready list, tiến trình vừa bị thu hồi processor được đưa vào lại cuối ready list. Rõ ràng đây là chiến lược điều phối không độc quyền.
Khoảng khoản thời gian mà mỗi tiến trình được sở hữu processor để hoạt động là bằng nhau, và thường được gọi là Quantum.
Ví dụ: Nếu hệ điều hành cần cấp processor cho 3 tiến trình P1, P2, P3 với thời điểm vào ready list và khoảng thời gian mỗi tiến trình cần processor được mô tả trong bảng sau:
Tiến trình thời điểm vào t/g xử lý
P1 0 24
P2 1
P3 2 33 Quantum = 4
Thì thứ tự cấp processor cho các tiến trình lần lượt là:
Tiến trình: P1 P2 P3 P1 P1 P1 P1 P1
Thời điểm: 0 4 7 10 14 18 22 26
Vậy thời gian chờ đợi trung bình sẽ là: (0 + 6 + 3 + 5)/3 = 4.46
Như vậy RR có thời gian chờ đợi trung bình nhỏ hơn so với FIFO
Trong chiến lược này, vấn đề đặt ra đối với công tác thiết kế là: nên chon quantum bằng bao nhiêu là thích hợp, nếu quantum nhỏ thì hệ thống phải tốn nhiều thời gian cho việc cập nhật ready list và chuyển trạng thái tiến trình, dẫn đến vi phạm mục tiêu: khai thác tối đa thời gian xử lý của processor. Nếu quantum lớn thì thời gian chờ đợi trung bình và thời gian hồi đáp sẽ tăng lên, dẫn đến tính tương tác của hệ thống bị giảm xuống.
Chế độ quyết định: preemptive
Khoảng thời gian tối đa cho phép (thường 10 - 100 ms) được đảm bảo bằng việc sử dụng timer interrupt
Process đang chạy hết thời gian sẽ được chuyển về cuối của hàng đợi ready
Chiến lược phân phối xoay vòng (RR: Round Robin):
Ready list được thiết kết theo dạng danh sách nối vòng. Tiến trình được bộ điều phối chọn để cấp processor cũng là tiến trình ở đầu ready list, nhưng sau một khoảng thời gian nhất định nào đó thì bộ điều phối lại thu hồi lại processor của tiến trình vừa được cấp processor và chuyển processor cho tiến trình kế tiếp (bây giờ đã trở thành tiến trình đầu tiên) trong ready list, tiến trình vừa bị thu hồi processor được đưa vào lại cuối ready list. Rõ ràng đây là chiến lược điều phối không độc quyền.
Khoảng khoản thời gian mà mỗi tiến trình được sở hữu processor để hoạt động là bằng nhau, và thường được gọi là Quantum.
Ví dụ: Nếu hệ điều hành cần cấp processor cho 3 tiến trình P1, P2, P3 với thời điểm vào ready list và khoảng thời gian mỗi tiến trình cần processor được mô tả trong bảng sau:
Tiến trình thời điểm vào t/g xử lý
P1 0 24
P2 1
P3 2 33 Quantum = 4
Thì thứ tự cấp processor cho các tiến trình lần lượt là:
Tiến trình: P1 P2 P3 P1 P1 P1 P1 P1
Thời điểm: 0 4 7 10 14 18 22 26
Vậy thời gian chờ đợi trung bình sẽ là: (0 + 6 + 3 + 5)/3 = 4.46
Như vậy RR có thời gian chờ đợi trung bình nhỏ hơn so với FIFO
Trong chiến lược này, vấn đề đặt ra đối với công tác thiết kế là: nên chon quantum bằng bao nhiêu là thích hợp, nếu quantum nhỏ thì hệ thống phải tốn nhiều thời gian cho việc cập nhật ready list và chuyển trạng thái tiến trình, dẫn đến vi phạm mục tiêu: khai thác tối đa thời gian xử lý của processor. Nếu quantum lớn thì thời gian chờ đợi trung bình và thời gian hồi đáp sẽ tăng lên, dẫn đến tính tương tác của hệ thống bị giảm xuống.
Chế độ quyết định: preemptive
Khoảng thời gian tối đa cho phép (thường 10 - 100 ms) được đảm bảo bằng việc sử dụng timer interrupt
Process đang chạy hết thời gian sẽ được chuyển về cuối của hàng đợi ready
Chiến lược phân phối xoay vòng (RR: Round Robin):
Ready list được thiết kết theo dạng danh sách nối vòng. Tiến trình được bộ điều phối chọn để cấp processor cũng là tiến trình ở đầu ready list, nhưng sau một khoảng thời gian nhất định nào đó thì bộ điều phối lại thu hồi lại processor của tiến trình vừa được cấp processor và chuyển processor cho tiến trình kế tiếp (bây giờ đã trở thành tiến trình đầu tiên) trong ready list, tiến trình vừa bị thu hồi processor được đưa vào lại cuối ready list. Rõ ràng đây là chiến lược điều phối không độc quyền.
Khoảng khoản thời gian mà mỗi tiến trình được sở hữu processor để hoạt động là bằng nhau, và thường được gọi là Quantum.
Ví dụ: Nếu hệ điều hành cần cấp processor cho 3 tiến trình P1, P2, P3 với thời điểm vào ready list và khoảng thời gian mỗi tiến trình cần processor được mô tả trong bảng sau:
Tiến trình thời điểm vào t/g xử lý
P1 0 24
P2 1
P3 2 33 Quantum = 4
Thì thứ tự cấp processor cho các tiến trình lần lượt là:
Tiến trình: P1 P2 P3 P1 P1 P1 P1 P1
Thời điểm: 0 4 7 10 14 18 22 26
Vậy thời gian chờ đợi trung bình sẽ là: (0 + 6 + 3 + 5)/3 = 4.46
Như vậy RR có thời gian chờ đợi trung bình nhỏ hơn so với FIFO
Trong chiến lược này, vấn đề đặt ra đối với công tác thiết kế là: nên chon quantum bằng bao nhiêu là thích hợp, nếu quantum nhỏ thì hệ thống phải tốn nhiều thời gian cho việc cập nhật ready list và chuyển trạng thái tiến trình, dẫn đến vi phạm mục tiêu: khai thác tối đa thời gian xử lý của processor. Nếu quantum lớn thì thời gian chờ đợi trung bình và thời gian hồi đáp sẽ tăng lên, dẫn đến tính tương tác của hệ thống bị giảm xuống.
Chế độ quyết định: preemptive
Khoảng thời gian tối đa cho phép (thường 10 - 100 ms) được đảm bảo bằng việc sử dụng timer interrupt
Process đang chạy hết thời gian sẽ được chuyển về cuối của hàng đợi ready
Chiến lược phân phối xoay vòng (RR: Round Robin):
Ready list được thiết kết theo dạng danh sách nối vòng. Tiến trình được bộ điều phối chọn để cấp processor cũng là tiến trình ở đầu ready list, nhưng sau một khoảng thời gian nhất định nào đó thì bộ điều phối lại thu hồi lại processor của tiến trình vừa được cấp processor và chuyển processor cho tiến trình kế tiếp (bây giờ đã trở thành tiến trình đầu tiên) trong ready list, tiến trình vừa bị thu hồi processor được đưa vào lại cuối ready list. Rõ ràng đây là chiến lược điều phối không độc quyền.
Khoảng khoản thời gian mà mỗi tiến trình được sở hữu processor để hoạt động là bằng nhau, và thường được gọi là Quantum.
Ví dụ: Nếu hệ điều hành cần cấp processor cho 3 tiến trình P1, P2, P3 với thời điểm vào ready list và khoảng thời gian mỗi tiến trình cần processor được mô tả trong bảng sau:
Tiến trình thời điểm vào t/g xử lý
P1 0 24
P2 1
P3 2 33 Quantum = 4
Thì thứ tự cấp processor cho các tiến trình lần lượt là:
Tiến trình: P1 P2 P3 P1 P1 P1 P1 P1
Thời điểm: 0 4 7 10 14 18 22 26
Vậy thời gian chờ đợi trung bình sẽ là: (0 + 6 + 3 + 5)/3 = 4.46
Như vậy RR có thời gian chờ đợi trung bình nhỏ hơn so với FIFO
Trong chiến lược này, vấn đề đặt ra đối với công tác thiết kế là: nên chon quantum bằng bao nhiêu là thích hợp, nếu quantum nhỏ thì hệ thống phải tốn nhiều thời gian cho việc cập nhật ready list và chuyển trạng thái tiến trình, dẫn đến vi phạm mục tiêu: khai thác tối đa thời gian xử lý của processor. Nếu quantum lớn thì thời gian chờ đợi trung bình và thời gian hồi đáp sẽ tăng lên, dẫn đến tính tương tác của hệ thống bị giảm xuống.
HoangThanhChuong (I11C)- Tổng số bài gửi : 15
Join date : 25/08/2011
Vì sao hệ điều hành phải có chức năng điều phối CPU? Năm tiêu chí điều phối CPU
TrinhThiPhuongThaoI11C 3/11/2011, 23:09
Vì sao hệ điều hành phải có chức năng điều phối CPU?
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ó một process được thực thi. Do đó, cần phải giải quyết vấn đề phân chia, lựa chọn process thực thi sao cho được hiệu quả nhất chiến lược định thời CPU.
Năm tiêu chí điều phối CPU?
a. 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.
b. 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.
c. 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, …).
d. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
e. 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.
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ó một process được thực thi. Do đó, cần phải giải quyết vấn đề phân chia, lựa chọn process thực thi sao cho được hiệu quả nhất chiến lược định thời CPU.
Năm tiêu chí điều phối CPU?
a. 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.
b. 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.
c. 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, …).
d. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
e. 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.
TrinhThiPhuongThaoI11C- Tổng số bài gửi : 19
Join date : 29/08/2011
Re: Thảo luận Bài 6
LeTanDat (I11C) 6/11/2011, 21:01
Mình nghĩ là mấy bạn nhầm rồi thì phải. Trên diễn đàn cũng có mấy bạn thắc mắc nhưng Thầy đã giải đáp:HoiHoangHongVu I11C đã viết:đú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.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.
Admin
- Nhiều bạn lẫn SJFS với RRS. Hai thuật giải này không liên quan gì đến nhau. Do đó, nếu dùng RRS, tiêu chí duy nhất để bị tiếm quyền sử dụng CPU là hết Thời luợng (Time Quantum).
- Với RRS, khi hết thời lượng, tiến trình hiện hành được đưa vào cuối Ready Queue, còn tiến trình ở đầu danh sách trong Ready Queue sẽ được chọn kế tiếp.
- Em thử làm lại bài theo tinh thần đó xem sao !
Đây là bài tập dùng thuật giải RRS chứ không phải SJFS
Mình cũng đã post một số bài tập về thuật giải SJFS rồi.
Mình xin giải thích lại bài này theo cách hiểu của mình.
- Đầu tiên là P1 chạy với thời lượng là 20ms đến thời gian 24ms thì dừng nhưng vì chưa có tiến trình nào tới nên P1 được chạy tiếp, đến 44ms thì P2 đến, P1 được đưa xuống cuối hàng chờ, P2 chạy cũng với thời lượng 20ms đến 64ms thì P3 đến, P2 được đưa xuống cuối hàng chờ. Cứ như vậy tiếp tục thực hiện.
LeTanDat (I11C)- Tổng số bài gửi : 24
Join date : 30/08/2011
Re: Thảo luận Bài 6
TranTrungKien (I11C) 7/11/2011, 14:50
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)
+ Không 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.
+ Có tiếm 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
TranTrungKien (I11C)- Tổng số bài gửi : 8
Join date : 29/08/2011
Re: Thảo luận Bài 6
PhamThiHoa-I91C 8/11/2011, 15:02
Sao cách giải của bạn đơn giản quá vậy, mình đi học mà còn không hiểu ý của bạn nữa màdangminhthinh2107 đã viết:P1: 53NguyenHaThanh97 (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ẻ.
P2: 17
P3: 68
P4: 24
Thoi luong 20ms
ban ap dung theo cong thuc
Ti =Thoi diem ket thuc - thoi gian den -thoi gian dung cpu
dau tien la P1 (0,57,24)
0= Thoi diem ket thuc (20) - thoi gian den (0) - thoi gian dung cpu(20)
57 = 97 - 20 -20
24 = 134 - 97 -13
ban ap dung tuong tu cho P2,P3 & P4
Theo cach hieu cua minh la nhu vay, mong cac ban dong gop them y kien
PhamThiHoa-I91C- Tổng số bài gửi : 29
Join date : 16/09/2011
Re: Thảo luận Bài 6
PhamThiHoa-I91C 8/11/2011, 15:33
Theo mình thì các bạn chỉ cần áp dụng công thức bạn Tuấn đưa ra (áp dụng cho cả sjfs và rrs) là:
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)
là tính ra được rồi, các bạn không cần phải tính tùm lum như vậy thì sẽ dễ bị sai hơn, mình cũng bị hoài vậy đó, cho nên mình cứ áp dụng công thức của thầy rồi nếu không yên tâm thì có thể test lại theo nhiều cách để cho chính xác, chúc các bạn thi tốt
[/quote]
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)
là tính ra được rồi, các bạn không cần phải tính tùm lum như vậy thì sẽ dễ bị sai hơn, mình cũng bị hoài vậy đó, cho nên mình cứ áp dụng công thức của thầy rồi nếu không yên tâm thì có thể test lại theo nhiều cách để cho chính xác, chúc các bạn thi tốt
[/quote]
PhamThiHoa-I91C- Tổng số bài gửi : 29
Join date : 16/09/2011
Vẽ biểu đồ Gantt cho thuật giải RR
PhamThiHoa-I91C 8/11/2011, 17:22
Cái quan trọng hơn tất cả là biểu đồ Gantt các bạn ạ, còn việc tính thời gian chạy trung bình thì chỉ cần chúng ta áp dụng công thức tính của thầy là được rồi. Ở đây mình thấy bạn Tuấn giải thích rất rõ về cách xây dựng biểu đồ gantt, mình thì cũng có một cách theo cách hiểu của mình mà mình thấy cũng vẽ đúng mong các bạn góp ý nhé :
Giải thích biểu đồ Gantt:
Chúng ta có 3 tiến trình, từ thời điểm 0-> không có tiến trình nào thực hiện
1. Tại thời điểm chưa tiến trình nào đến thì độ ưu tiên sẽ dành cho tiền trình đến trước
- Từ 0->3 chưa có tiến trình nào đến
- Từ T=3 có P1 đến thực hiện được 10ms thời gian chiếm CPU còn lại là 35-10=25
- Từ T=13 thì có P2 đến (vì thời gian đến của P2 là 10) thực hiện được 10ms còn lại là :20-10=10
- Từ T=23 thì không có tiền trình nào tới nhưng lại có tiến trình P1 đang trong hàng đợi vậy P1 sẽ thực hiện được 10ms nữa =>P1 còn lại là 25-10=15
2. Tất cả các tiền trình đã đến thì được ưu tiên cho tiến trình có thời gian chờ nhiều nhất
- Từ T=33 thì tất cả các tiến trình đều đến do đó ở đây ta sẽ tính thời gian chờ của các tiến trình
P1: vừa mới thực hiện 10ms nên thời gian chờ là 0
P2: 23->33=10
P3: 25->33=8
=>P2 thực hiện 10ms=>còn lại là 0=>kết thúc tiến trình P2
- Từ T=43 thời gian chờ của
P1:33->43=10
P3:25->43=18
=>P3 thực hiện 10ms=>còn lại là 5
-Từ T=53 thời gian chờ của các tiền trình là:
P1:33->53=20
P3:mơi thực hiện xong
=>P1 thực hiện 10ms=>còn lại là 5
-Từ T=63 thời gian chờ các tiền trình là
P1:mới thực hiện xong
P3:53->63=10
=>P3 thực hiện 5ms=> kết thúc tiên trình
=>còn lại P1 thực hiện 5ms nưa->kết thúc tiến trình P1=> xây dừng được biểu đồ Gantt
Giải thích biểu đồ Gantt:
Chúng ta có 3 tiến trình, từ thời điểm 0-> không có tiến trình nào thực hiện
1. Tại thời điểm chưa tiến trình nào đến thì độ ưu tiên sẽ dành cho tiền trình đến trước
- Từ 0->3 chưa có tiến trình nào đến
- Từ T=3 có P1 đến thực hiện được 10ms thời gian chiếm CPU còn lại là 35-10=25
- Từ T=13 thì có P2 đến (vì thời gian đến của P2 là 10) thực hiện được 10ms còn lại là :20-10=10
- Từ T=23 thì không có tiền trình nào tới nhưng lại có tiến trình P1 đang trong hàng đợi vậy P1 sẽ thực hiện được 10ms nữa =>P1 còn lại là 25-10=15
2. Tất cả các tiền trình đã đến thì được ưu tiên cho tiến trình có thời gian chờ nhiều nhất
- Từ T=33 thì tất cả các tiến trình đều đến do đó ở đây ta sẽ tính thời gian chờ của các tiến trình
P1: vừa mới thực hiện 10ms nên thời gian chờ là 0
P2: 23->33=10
P3: 25->33=8
=>P2 thực hiện 10ms=>còn lại là 0=>kết thúc tiến trình P2
- Từ T=43 thời gian chờ của
P1:33->43=10
P3:25->43=18
=>P3 thực hiện 10ms=>còn lại là 5
-Từ T=53 thời gian chờ của các tiền trình là:
P1:33->53=20
P3:mơi thực hiện xong
=>P1 thực hiện 10ms=>còn lại là 5
-Từ T=63 thời gian chờ các tiền trình là
P1:mới thực hiện xong
P3:53->63=10
=>P3 thực hiện 5ms=> kết thúc tiên trình
=>còn lại P1 thực hiện 5ms nưa->kết thúc tiến trình P1=> xây dừng được biểu đồ Gantt
PhamThiHoa-I91C- Tổng số bài gửi : 29
Join date : 16/09/2011
Re: Thảo luận Bài 6
PhamThiHoa-I91C 8/11/2011, 17:28
Chính xác rồi đó bạn, mình cũng có cách tính ra kết quả giống bạn đóLeTanDat (I11C) đã viết:- Biểu đồ Gantt: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: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!
| 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)
PhamThiHoa-I91C- Tổng số bài gửi : 29
Join date : 16/09/2011
Re: Thảo luận Bài 6
PhamThiHoa-I91C 8/11/2011, 18:22
Mình sẽ góp ý giải thích biểu đồ Gantt như thế này nhé các bạn:DuongTrungTinh(I11C) đã viết:Bài giải của bạn chính xác, nhưng bạn cần giải thích rõ ràng hơn cho các bạn chưa hiểu để hiểu rõ vấn đề và cùng nhau qua được môn này nhéNgoLeYen48(I11C) đã viết:Đề: một hệ thống có 4 tiến trình, với thời điểm đến và tg sử dụng CPU như sau;
P1 4 20
P2 9 16
P3 15 24
P4 31 11
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU và dùng thuật giải SJFS có tiếm quyền.
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?
SJFS:
như cách giải mình post trên sẽ có kết quả:
TGCTB= (51+24+0+18)/4=23,25 ms
RRS:
như cách giải mình post trên sẽ có kết quả:
TGCTB= (10+25+36+29)/4= 25 ms.
Các bạn tham khảo và góp ý giúp nhé.
Thanks!.Thanks bạn!
Thuật giải SJFS:
-Tại thời điểm T=4 thì có P1 đến thực hiện được 5ms thì có P2 đến
=>P1: còn lại là 20-5=15
- Tại thời điểm T=9 có P2 đến thực hiện được 6ms thì có P3 đến
=>p2: còn lại là:16-6=10
-Tại thời điểm T=15 có P3 đến thực hiện được 16ms đến thời điểm T=31
=>P3: còn lai:24-16=8
- Tại thời điểm T=31 ta so sánh xem có tiến trình nào chiếm CPU ít hơn thì ta chọn vậy ta sẽ chọn P3 tiếp tục vì P nhỏ nhất
=>P3: còn lại:8-8=0 kết thúc
-Tại thời điểm T=39 thì tất cả các tiến trình điều đến, do đó ta sẽ chọn tiến trình có chiếm CPU nhỏ vậy P còn lại là 10 nhỏ nhất nên P2 được chọn
=>P2: còn lại :8-8=>kết thúc tiến trình
- Tại thời điểm T=49 thì có P4 đến vì P4=11, còn P1=15
=>P4:còn lại 11-11=> kết thúc tiến trình
- Còn lại P1 => kết thúc
PhamThiHoa-I91C- Tổng số bài gửi : 29
Join date : 16/09/2011
Vì sao hệ điều hành phải có chức năng điều phối CPU?
TranQuyThanh (I11C) 9/11/2011, 12:06
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ó một process được thực thi. Do đó, cần phải giải quyết vấn đề phân chia, lựa chọn process thực thi sao cho được hiệu quả nhất ® chiến lược định thời CPU.
Tại mỗi thời điểm, chỉ có một process được thực thi. Do đó, cần phải giải quyết vấn đề phân chia, lựa chọn process thực thi sao cho được hiệu quả nhất ® chiến lược định thời CPU.
TranQuyThanh (I11C)- Tổng số bài gửi : 53
Join date : 30/08/2011
Các đặc điểm của tiến trình
lengocthuthao89 (i11c) 9/11/2011, 12:32
Các đặc điểm của tiến trình
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ý.
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ý.
lengocthuthao89 (i11c)- Tổng số bài gửi : 50
Join date : 13/09/2011
Bốn tình huống ra quyết định của trình điều phối và phân biệt Điều phối không tiếm quyền(Non - Preemtive)và Điều phối có tiếm quyền (Preemtive)
lengocthuthao89 (i11c) 9/11/2011, 12:37
A. 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.
* Sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4 đượ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 khi 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).
B. Phân biệt điều phối có tiếm quyền và không có tiếm quyền:
- Giống nhau: cùng điều phối CPU (chọn tiến trình trong Ready Queue để cấp thời gian CPU (chuyển sang trạng thái Running)).
- Khác nhau: Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phối CPU không tiếm quyền.
- Non-Preemptive Scheduling: Có nghĩa là khi có 1 tiến trình P1,P2 xuất hiện thì nó sẽ thực hiện xong tiến trình P1 , sau đó mới thực hiện tiến trình P2 (cách làm trong Windows 3.1 và Macintosh OS)
- Preemptive Scheduling : có nghĩa là khi có 1 tiến trình P1,P2,P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình.
C. Chủ ý: Trong 4 tình huống ra quyết định của trình điều phổi CPU ở trên thì 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 kết thúc công việc.) là tình huống mà điều phổi không tiếm quyền(Không dùng CPU) vì lúc này chương trình tự nguyện trá CPU.Còn tình huống(Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra) vá Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)) là tình huống mad điều phổi có tiếm quyền.Đây là mô hình hiện đại nhằm giúp CPU hoạt động hết hiệu suất của mình để làm giám thiếu tối đa thời gian chờ nhằm đáp ứng được hiệu quả công việc cao hơn.
* 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.
* Sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4 đượ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 khi 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).
B. Phân biệt điều phối có tiếm quyền và không có tiếm quyền:
- Giống nhau: cùng điều phối CPU (chọn tiến trình trong Ready Queue để cấp thời gian CPU (chuyển sang trạng thái Running)).
- Khác nhau: Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phối CPU không tiếm quyền.
- Non-Preemptive Scheduling: Có nghĩa là khi có 1 tiến trình P1,P2 xuất hiện thì nó sẽ thực hiện xong tiến trình P1 , sau đó mới thực hiện tiến trình P2 (cách làm trong Windows 3.1 và Macintosh OS)
- Preemptive Scheduling : có nghĩa là khi có 1 tiến trình P1,P2,P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình.
C. Chủ ý: Trong 4 tình huống ra quyết định của trình điều phổi CPU ở trên thì 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 kết thúc công việc.) là tình huống mà điều phổi không tiếm quyền(Không dùng CPU) vì lúc này chương trình tự nguyện trá CPU.Còn tình huống(Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra) vá Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)) là tình huống mad điều phổi có tiếm quyền.Đây là mô hình hiện đại nhằm giúp CPU hoạt động hết hiệu suất của mình để làm giám thiếu tối đa thời gian chờ nhằm đáp ứng được hiệu quả công việc cao hơn.
lengocthuthao89 (i11c)- Tổng số bài gửi : 50
Join date : 13/09/2011
Trang 7 trong tổng số 8 trang • 1, 2, 3, 4, 5, 6, 7, 8
Similar topics» Thảo luận Bài 7
» Thảo luận Bài 8
» Thảo luận Bài 7
» Thảo luận về đề thi HK1
» [Đề thi giữa kỳ] I22B ( 8-4-2013 )
» Thảo luận Bài 8
» Thảo luận Bài 7
» Thảo luận về đề thi HK1
» [Đề thi giữa kỳ] I22B ( 8-4-2013 )
Trang 7 trong tổng số 8 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết