Bài tập giải thuật RRS

NguyenHoangThien(I22B) 27/3/2013, 15:04

Thảo luận Bài 6 - Page 5 8593800395_e118bf9d02_b

Trả lời:
a. Biểu đồ Gantt
Thảo luận Bài 6 - Page 5 8594900088_7e934a2f64_b

b. Thời gian chờ trung bình
( 35 + 2 + 22 ) / 3 = 59 / 3 = 19,66 ms

PhamPhuKhanh52(I22B) 27/3/2013, 15:20

chiến lược điều phối FIFO
Nguyên tắc: Process được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình được đưa vào hệ thống sớm nhất.
FIFO được sử dụng trong điều phối độc quyền nên khi tiến trình được cấp processor nó sẽ sở hữu processsor cho đến khi kết thúc xử lý hay phải đợi 1 thao tác khác. khi đó tiến trình chủ động trả processor lại cho hệ thống.
Khuyết điềm của điều phối kiểu FIFO này là:
Thời gian chờ rất lớn nên không phù hợp với hệ thống chia sẽ thời gian.
khả năng tương tác kém khi áp dụng lên các hệ thống uniprocessor.
Nếu các tiến trình ở đầu ready list cần nhiều thời gian của processor thì các tiến trình ở cuối ready list sẽ phải chờ rất lâu mới được cấp processor.

MaiXuanSon (I22B) 27/3/2013, 15:29

VoMinhDien(I22B) đã viết:Các ví dụ minh họa về thuật giải:
Thuật giải FCFS : Xếp hàng chờ khám bệnh, người nào đến trước thì được khám trước, đến sau thì khám sau.
Thuật giải SJFS (không tiếm quyền): Xếp hàng đợi mua vé tàu ở ga Hòa Hưng, Anh A đến trước mua 7 vé, sau khi mua được 2 vé thì anh B xuất hiện (Anh B dự định mua 4 vé) nhưng quầy vé sẽ vẫn tiếp tục bán cho anh A hết 7 vé rồi mới bán 4 vé cho anh B...
Thuật giải SJFS (có tiếm quyền): Giống như ví dụ trên như khi bán được 2 vé cho anh A thì anh B xuất hiện mua 4 vé thì lúc này quầy bán vé sẽ dừng lại, anh A qua bên phòng đợi bên cạnh chờ, quầy bán vé sẽ bán cho anh B nhưng khi bán anh B được 1 vé thi anh C xuất hiện mua 1 vé thì quầy lại tiếp tục dừng bán vé cho anh B và Anh B qua phòng chờ. Quầy bán vé bán 1 vé cho anh C rồi quầy sẽ xem xét anh B còn mua 3 vé, anh A còn mua 5 vé thì quầy sẽ phụ vụ anh B. Sau khi bán hết cho anh B quầy lại tiếp tục phục vụ trở lại anh A số vé còn lại.
Thuật giải vòng Robin: Trong nhà hàng chỉ có 1 anh bồi bàn và anh bồi bàn đó sẽ phụ vụ cho mỗi bàn trong nhà hàng là 20ms, chạy qua lại giữa các bàn nên mỗi bàn có cảm giác là mình được anh bồi bàn phục vụ riêng cho mình.
Thuật giải MQS : Tai một nhà ga có 5 cỏng bán vé. Cổng 1 chỉ ưu tiên bán vé cho những người làm trong nhà ga. Cổng 2 bán chỉ ưu tiên bán vé cho người có công cách mạng. Cổng 3 ưu tiên bán cho người già yếu, bệnh tật. Cổng 4 bán cho những người khác. Cổng 5 bán cho sinh viên. Nếu người nào mua vé thì ra ngoài theo cổng đó luôn.
Thuật giải MFQS :Nhà ga có 3 cổng , cổng 0 bắt buộc tất cả mọi người mua vé phải đi qua, nếu mua vé xong thì sẽ ra ngoài theo cổng đó, nếu quá đông thì những người chưa mua được vé sẽ đẩy xuống cổng 1 và xong thì sẽ ra theo cổng đó. Nếu vẫn chưa mua được thì sẽ đẩy xuống cổng 2 và xong thì ra ngoài. Tuy nhiên vẫn có trường hợp nâng cấp đưa người mua vé cổng 2 trở về cổng 1 mua vé nhưng tuyệt đối không có việc nâng cấp đưa người mua vé từ cổng 1 trở lại cổng 0.

Ví dụ rõ ràng, thanks bạn Điền.

NguyenMinhTam(I22B) 27/3/2013, 21:59

[quote="MaiXuanSon (I22B)"]

VoMinhDien(I22B) đã viết:Các ví dụ minh họa về thuật giải:
Thuật giải FCFS : Xếp hàng chờ khám bệnh, người nào đến trước thì được khám trước, đến sau thì khám sau.
Thuật giải SJFS (không tiếm quyền): Xếp hàng đợi mua vé tàu ở ga Hòa Hưng, Anh A đến trước mua 7 vé, sau khi mua được 2 vé thì anh B xuất hiện (Anh B dự định mua 4 vé) nhưng quầy vé sẽ vẫn tiếp tục bán cho anh A hết 7 vé rồi mới bán 4 vé cho anh B...
Thuật giải SJFS (có tiếm quyền): Giống như ví dụ trên như khi bán được 2 vé cho anh A thì anh B xuất hiện mua 4 vé thì lúc này quầy bán vé sẽ dừng lại, anh A qua bên phòng đợi bên cạnh chờ, quầy bán vé sẽ bán cho anh B nhưng khi bán anh B được 1 vé thi anh C xuất hiện mua 1 vé thì quầy lại tiếp tục dừng bán vé cho anh B và Anh B qua phòng chờ. Quầy bán vé bán 1 vé cho anh C rồi quầy sẽ xem xét anh B còn mua 3 vé, anh A còn mua 5 vé thì quầy sẽ phụ vụ anh B. Sau khi bán hết cho anh B quầy lại tiếp tục phục vụ trở lại anh A số vé còn lại.
Thuật giải vòng Robin: Trong nhà hàng chỉ có 1 anh bồi bàn và anh bồi bàn đó sẽ phụ vụ cho mỗi bàn trong nhà hàng là 20ms, chạy qua lại giữa các bàn nên mỗi bàn có cảm giác là mình được anh bồi bàn phục vụ riêng cho mình.
Thuật giải MQS : Tai một nhà ga có 5 cỏng bán vé. Cổng 1 chỉ ưu tiên bán vé cho những người làm trong nhà ga. Cổng 2 bán chỉ ưu tiên bán vé cho người có công cách mạng. Cổng 3 ưu tiên bán cho người già yếu, bệnh tật. Cổng 4 bán cho những người khác. Cổng 5 bán cho sinh viên. Nếu người nào mua vé thì ra ngoài theo cổng đó luôn.
Thuật giải MFQS :Nhà ga có 3 cổng , cổng 0 bắt buộc tất cả mọi người mua vé phải đi qua, nếu mua vé xong thì sẽ ra ngoài theo cổng đó, nếu quá đông thì những người chưa mua được vé sẽ đẩy xuống cổng 1 và xong thì sẽ ra theo cổng đó. Nếu vẫn chưa mua được thì sẽ đẩy xuống cổng 2 và xong thì ra ngoài. Tuy nhiên vẫn có trường hợp nâng cấp đưa người mua vé cổng 2 trở về cổng 1 mua vé nhưng tuyệt đối không có việc nâng cấp đưa người mua vé từ cổng 1 trở lại cổng 0.

oi. thank ban h minh hiu hon ve phan nay roi,nhung phan ve bieu do grantt minh van mo ho lam

HuynhDucQuang(I22B) 28/3/2013, 00:08

NguyenMinhTam(I22B) đã viết:chao ban.minh van chua hiu cach ve so do grantt lam.ban co the huong dan lai giup minh duoc khong

Ở đây mình chỉ trình bày theo phương pháp vòng robin thôi nha.
Những thứ bán cần để ý khi vẽ:
1. Thời điểm đến của tiến trình.
2. Thời lượng tối đa cấp CPU.
3. Thời điểm kết thúc của tiến trình.

VD: có 3 tiến trình P1, P2, P3 với thời lượnh = 10ms

TT	T đến	khoảng CPU
P1	5	15
P2	8	20
P3	15	15

Đi theo thứ tự nhé.
T=0 không có tiến trình => không cần quan tâm
T=5 P1 xuất hiện => vẽ mốc P1 = 5. P1 cần chạy 15ms => chạy đến mốc 20ms sẽ ngừng. Nhưng đề bài chỉ cấp thời lượng mỗi tiến trình 10ms => P1 chạy đến mốc 15ms phải ngừng và đưa vào hàng đợi Ready (lúc nào phải lưu lại nó đã chạy được 10ms còn lại 5ms)
T=8 P2 xuất hiện => nhưng P1 đanh chạy nên P2 đưa vào hàng đợi.
T=15 Mốc P1 ngừng, và P2 đang ở trong hàng đợi sẽ được chạy. Cùng lúc này P3 xuất hiện nhưng P2 được phép chạy nên P3 đưa vào hàng đợi. P2 cần chạy 20 nhưng đề bài chỉ cấp CPU trong 10ms => P2 chỉ chạy đến mốc 25ms sẽ ngừng và quây vào hành đợi và ghi nhận thời gian còn lại phải chạy là 10ms.
T=25 P2 ngừng, P3 chạy. P3 cần chạy 15 nhưng đề chỉ cấp CPU cho 10ms => P3 chạy đến mốc 35ms rồi ngừng, quây vào hàng đơij với thời gian chưa chạy là 5ms.
T=35 P3 ngừng, P1 chạy thêm 5ms vì ban đầu đã chạy 10ms rồi => chạy đến mốc 40ms ngừng. P1 hoàn tất công việc trả CPU lại cho HĐH.
T=40 P1 kết thúc, P2 chạy thêm 10ms (ban đầu đã chạy được 10ms) => p2 kết thúc tại mốc 50ms.
T=50 P2 kết thúc, P3 chạy thêm 5ms => Chạy đến mốc 55ms.
T=55 P3 kết thúc.

Những mốc thời gian như là T mà Tiến trình bắt đầu và T mà tiến trình kết thúc phải vẽ ra. Những cái T mình liệt kê ở trên phải được vẽ đầy đủ.

Hy vọng cái này có thể giúp được bạn.
Chúc 1 ngày vui vẻ.

NguyenCaoDuong(I22B) 28/3/2013, 01:28

HuynhDucQuang(I22B) đã viết:
NguyenMinhTam(I22B) đã viết:chao ban.minh van chua hiu cach ve so do grantt lam.ban co the huong dan lai giup minh duoc khong

Ở đây mình chỉ trình bày theo phương pháp vòng robin thôi nha.
Những thứ bán cần để ý khi vẽ:
1. Thời điểm đến của tiến trình.
2. Thời lượng tối đa cấp CPU.
3. Thời điểm kết thúc của tiến trình.

VD: có 3 tiến trình P1, P2, P3 với thời lượnh = 10ms
TT T đến khoảng CPU
P1 5 15
P2 8 20
P3 15 15

Đi theo thứ tự nhé.
T=0 không có tiến trình => không cần quan tâm
T=5 P1 xuất hiện => vẽ mốc P1 = 5. P1 cần chạy 15ms => chạy đến mốc 20ms sẽ ngừng. Nhưng đề bài chỉ cấp thời lượng mỗi tiến trình 10ms => P1 chạy đến mốc 15ms phải ngừng và đưa vào hàng đợi Ready (lúc nào phải lưu lại nó đã chạy được 10ms còn lại 5ms)
T=8 P2 xuất hiện => nhưng P1 đanh chạy nên P2 đưa vào hàng đợi.
T=15 Mốc P1 ngừng, và P2 đang ở trong hàng đợi sẽ được chạy. Cùng lúc này P3 xuất hiện nhưng P2 được phép chạy nên P3 đưa vào hàng đợi. P2 cần chạy 20 nhưng đề bài chỉ cấp CPU trong 10ms => P2 chỉ chạy đến mốc 25ms sẽ ngừng và quây vào hành đợi và ghi nhận thời gian còn lại phải chạy là 10ms.
T=25 P2 ngừng, P3 chạy. P3 cần chạy 15 nhưng đề chỉ cấp CPU cho 10ms => P3 chạy đến mốc 35ms rồi ngừng, quây vào hàng đơij với thời gian chưa chạy là 5ms.
T=35 P3 ngừng, P1 chạy thêm 5ms vì ban đầu đã chạy 10ms rồi => chạy đến mốc 40ms ngừng. P1 hoàn tất công việc trả CPU lại cho HĐH.
T=40 P1 kết thúc, P2 chạy thêm 10ms (ban đầu đã chạy được 10ms) => p2 kết thúc tại mốc 50ms.
T=50 P2 kết thúc, P3 chạy thêm 5ms => Chạy đến mốc 55ms.
T=55 P3 kết thúc.

Những mốc thời gian như là T mà Tiến trình bắt đầu và T mà tiến trình kết thúc phải vẽ ra. Những cái T mình liệt kê ở trên phải được vẽ đầy đủ.

Hy vọng cái này có thể giúp được bạn.
Chúc 1 ngày vui vẻ.

Bạn nói rõ cái này dùm mình voi "T=8 P2 xuất hiện => nhưng P1 đanh chạy nên P2 đưa vào hàng đợi."
Còn cái hình đây, ban xem coi co' đúng không?
|....p1....|...p2...|...p3...|...p1...|...p2...|...p3...|
5.........15.......25.......35........40........50.......55

PhamQuocCuong (I22A) 28/3/2013, 08:22

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. (Vd: nộp bài kiểm tra cho Thầy: thì lần lượt nhóm từng 5 người lên theo thứ tự trên bảng -> 5 tiếp người tiếp theo sẽ chờ trong khoảng thời gian hơi lâu)
* Quy tắc FIFO (First-In, First-Out):
- Nguyên tắc :
+ Processor được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình được đưa vào hệ thống sớm nhất.
+ FIFO được sử dụng trong điều phối độc quyền nên khi tiến trình được cấp processor nó sẽ sở hữu processor cho đến khi kết thúc xử lý hay phải đợi một thao tác vào/ra hoàn thành, khi đó tiến trình chủ động trả lại processor cho hệ thống.
VD: Việc phục vụ khách trong nhà hàng. Thực khách sẽ đến và gọi món ăn cho mình. Mỗi món ăn cần thời gian chuẩn bị khác nhau

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.

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

HuynhDucQuang(I22B) 28/3/2013, 12:00

NguyenCaoDuong(I22B) đã viết:
HuynhDucQuang(I22B) đã viết:
NguyenMinhTam(I22B) đã viết:chao ban.minh van chua hiu cach ve so do grantt lam.ban co the huong dan lai giup minh duoc khong

Ở đây mình chỉ trình bày theo phương pháp vòng robin thôi nha.
Những thứ bán cần để ý khi vẽ:
1. Thời điểm đến của tiến trình.
2. Thời lượng tối đa cấp CPU.
3. Thời điểm kết thúc của tiến trình.

VD: có 3 tiến trình P1, P2, P3 với thời lượnh = 10ms
TT T đến khoảng CPU
P1 5 15
P2 8 20
P3 15 15

Đi theo thứ tự nhé.
T=0 không có tiến trình => không cần quan tâm
T=5 P1 xuất hiện => vẽ mốc P1 = 5. P1 cần chạy 15ms => chạy đến mốc 20ms sẽ ngừng. Nhưng đề bài chỉ cấp thời lượng mỗi tiến trình 10ms => P1 chạy đến mốc 15ms phải ngừng và đưa vào hàng đợi Ready (lúc nào phải lưu lại nó đã chạy được 10ms còn lại 5ms)
T=8 P2 xuất hiện => nhưng P1 đanh chạy nên P2 đưa vào hàng đợi.
T=15 Mốc P1 ngừng, và P2 đang ở trong hàng đợi sẽ được chạy. Cùng lúc này P3 xuất hiện nhưng P2 được phép chạy nên P3 đưa vào hàng đợi. P2 cần chạy 20 nhưng đề bài chỉ cấp CPU trong 10ms => P2 chỉ chạy đến mốc 25ms sẽ ngừng và quây vào hành đợi và ghi nhận thời gian còn lại phải chạy là 10ms.
T=25 P2 ngừng, P3 chạy. P3 cần chạy 15 nhưng đề chỉ cấp CPU cho 10ms => P3 chạy đến mốc 35ms rồi ngừng, quây vào hàng đơij với thời gian chưa chạy là 5ms.
T=35 P3 ngừng, P1 chạy thêm 5ms vì ban đầu đã chạy 10ms rồi => chạy đến mốc 40ms ngừng. P1 hoàn tất công việc trả CPU lại cho HĐH.
T=40 P1 kết thúc, P2 chạy thêm 10ms (ban đầu đã chạy được 10ms) => p2 kết thúc tại mốc 50ms.
T=50 P2 kết thúc, P3 chạy thêm 5ms => Chạy đến mốc 55ms.
T=55 P3 kết thúc.

Những mốc thời gian như là T mà Tiến trình bắt đầu và T mà tiến trình kết thúc phải vẽ ra. Những cái T mình liệt kê ở trên phải được vẽ đầy đủ.

Hy vọng cái này có thể giúp được bạn.
Chúc 1 ngày vui vẻ.

Bạn nói rõ cái này dùm mình voi "T=8 P2 xuất hiện => nhưng P1 đanh chạy nên P2 đưa vào hàng đợi."
Còn cái hình đây, ban xem coi co' đúng không?
|....p1....|...p2...|...p3...|...p1...|...p2...|...p3...|
5.........15.......25.......35........40........50.......55

Bạn vẽ hình đúng rồi, nhưng mình phải vẽ thêm những mốc mà các tiến trình xuất hiện nữa. Hình này cần vẽm thêm mốc T=8 nữa là hoàn hảo.
|....p1....|...p2...|...p3...|...p1...|...p2...|...p3...|
5..8......15.......25.......35........40........50.......55
T=8 thì P2 xuất hiện, nhưng P1 đang chạy nên nó phải đọi P1 chạy xonh thì nó mới chạy. Chỉ vậy thôi. Có lẻ do cách mình dùng từ không chính xác nên bạn hiểu lầm. P2 không phải đưa vào hàng đợi mà vẫn tiếp tục nằm trong hàng đợi và đợi P1 chạy xong mới được vận hành. Giả sử P1 chạy xong trước mốc 8ms thì lúc đó P2 sẽ không cần đợi, CPU chỉ cấp cho mỗi một tiến trình ở mỗi 1 thời điểm.

NguyenCaoDuong(I22B) 28/3/2013, 13:35

HuynhDucQuang(I22B) đã viết:
NguyenCaoDuong(I22B) đã viết:
HuynhDucQuang(I22B) đã viết:
NguyenMinhTam(I22B) đã viết:chao ban.minh van chua hiu cach ve so do grantt lam.ban co the huong dan lai giup minh duoc khong

Ở đây mình chỉ trình bày theo phương pháp vòng robin thôi nha.
Những thứ bán cần để ý khi vẽ:
1. Thời điểm đến của tiến trình.
2. Thời lượng tối đa cấp CPU.
3. Thời điểm kết thúc của tiến trình.

VD: có 3 tiến trình P1, P2, P3 với thời lượnh = 10ms
TT T đến khoảng CPU
P1 5 15
P2 8 20
P3 15 15

Đi theo thứ tự nhé.
T=0 không có tiến trình => không cần quan tâm
T=5 P1 xuất hiện => vẽ mốc P1 = 5. P1 cần chạy 15ms => chạy đến mốc 20ms sẽ ngừng. Nhưng đề bài chỉ cấp thời lượng mỗi tiến trình 10ms => P1 chạy đến mốc 15ms phải ngừng và đưa vào hàng đợi Ready (lúc nào phải lưu lại nó đã chạy được 10ms còn lại 5ms)
T=8 P2 xuất hiện => nhưng P1 đanh chạy nên P2 đưa vào hàng đợi.
T=15 Mốc P1 ngừng, và P2 đang ở trong hàng đợi sẽ được chạy. Cùng lúc này P3 xuất hiện nhưng P2 được phép chạy nên P3 đưa vào hàng đợi. P2 cần chạy 20 nhưng đề bài chỉ cấp CPU trong 10ms => P2 chỉ chạy đến mốc 25ms sẽ ngừng và quây vào hành đợi và ghi nhận thời gian còn lại phải chạy là 10ms.
T=25 P2 ngừng, P3 chạy. P3 cần chạy 15 nhưng đề chỉ cấp CPU cho 10ms => P3 chạy đến mốc 35ms rồi ngừng, quây vào hàng đơij với thời gian chưa chạy là 5ms.
T=35 P3 ngừng, P1 chạy thêm 5ms vì ban đầu đã chạy 10ms rồi => chạy đến mốc 40ms ngừng. P1 hoàn tất công việc trả CPU lại cho HĐH.
T=40 P1 kết thúc, P2 chạy thêm 10ms (ban đầu đã chạy được 10ms) => p2 kết thúc tại mốc 50ms.
T=50 P2 kết thúc, P3 chạy thêm 5ms => Chạy đến mốc 55ms.
T=55 P3 kết thúc.

Những mốc thời gian như là T mà Tiến trình bắt đầu và T mà tiến trình kết thúc phải vẽ ra. Những cái T mình liệt kê ở trên phải được vẽ đầy đủ.

Hy vọng cái này có thể giúp được bạn.
Chúc 1 ngày vui vẻ.

Bạn nói rõ cái này dùm mình voi "T=8 P2 xuất hiện => nhưng P1 đanh chạy nên P2 đưa vào hàng đợi."
Còn cái hình đây, ban xem coi co' đúng không?
|....p1....|...p2...|...p3...|...p1...|...p2...|...p3...|
5.........15.......25.......35........40........50.......55
Bạn vẽ hình đúng rồi, nhưng mình phải vẽ thêm những mốc mà các tiến trình xuất hiện nữa. Hình này cần vẽm thêm mốc T=8 nữa là hoàn hảo.
|....p1....|...p2...|...p3...|...p1...|...p2...|...p3...|
5..8......15.......25.......35........40........50.......55
T=8 thì P2 xuất hiện, nhưng P1 đang chạy nên nó phải đọi P1 chạy xonh thì nó mới chạy. Chỉ vậy thôi. Có lẻ do cách mình dùng từ không chính xác nên bạn hiểu lầm. P2 không phải đưa vào hàng đợi mà vẫn tiếp tục nằm trong hàng đợi và đợi P1 chạy xong mới được vận hành. Giả sử P1 chạy xong trước mốc 8ms thì lúc đó P2 sẽ không cần đợi, CPU chỉ cấp cho mỗi một tiến trình ở mỗi 1 thời điểm.

Thank bạn nhiều nha, mình cũng hiểu vậy đó. Sau khi p2 thuc hien duoc 10ms thì sau khoảng thoi gian này nó bị tiếm quyền và đưa vào cuối hàng đợi Ready. Neu được tính thời gian chờ trung bình luôn là bài này hoàn chỉnh rồi...

VoMinhThang(I22B) 28/3/2013, 13:42

HuynhDucQuang(I22B) đã viết:
NguyenCaoDuong(I22B) đã viết:
HuynhDucQuang(I22B) đã viết:
NguyenMinhTam(I22B) đã viết:chao ban.minh van chua hiu cach ve so do grantt lam.ban co the huong dan lai giup minh duoc khong

Ở đây mình chỉ trình bày theo phương pháp vòng robin thôi nha.
Những thứ bán cần để ý khi vẽ:
1. Thời điểm đến của tiến trình.
2. Thời lượng tối đa cấp CPU.
3. Thời điểm kết thúc của tiến trình.

VD: có 3 tiến trình P1, P2, P3 với thời lượnh = 10ms
TT T đến khoảng CPU
P1 5 15
P2 8 20
P3 15 15

Đi theo thứ tự nhé.
T=0 không có tiến trình => không cần quan tâm
T=5 P1 xuất hiện => vẽ mốc P1 = 5. P1 cần chạy 15ms => chạy đến mốc 20ms sẽ ngừng. Nhưng đề bài chỉ cấp thời lượng mỗi tiến trình 10ms => P1 chạy đến mốc 15ms phải ngừng và đưa vào hàng đợi Ready (lúc nào phải lưu lại nó đã chạy được 10ms còn lại 5ms)
T=8 P2 xuất hiện => nhưng P1 đanh chạy nên P2 đưa vào hàng đợi.
T=15 Mốc P1 ngừng, và P2 đang ở trong hàng đợi sẽ được chạy. Cùng lúc này P3 xuất hiện nhưng P2 được phép chạy nên P3 đưa vào hàng đợi. P2 cần chạy 20 nhưng đề bài chỉ cấp CPU trong 10ms => P2 chỉ chạy đến mốc 25ms sẽ ngừng và quây vào hành đợi và ghi nhận thời gian còn lại phải chạy là 10ms.
T=25 P2 ngừng, P3 chạy. P3 cần chạy 15 nhưng đề chỉ cấp CPU cho 10ms => P3 chạy đến mốc 35ms rồi ngừng, quây vào hàng đơij với thời gian chưa chạy là 5ms.
T=35 P3 ngừng, P1 chạy thêm 5ms vì ban đầu đã chạy 10ms rồi => chạy đến mốc 40ms ngừng. P1 hoàn tất công việc trả CPU lại cho HĐH.
T=40 P1 kết thúc, P2 chạy thêm 10ms (ban đầu đã chạy được 10ms) => p2 kết thúc tại mốc 50ms.
T=50 P2 kết thúc, P3 chạy thêm 5ms => Chạy đến mốc 55ms.
T=55 P3 kết thúc.

Những mốc thời gian như là T mà Tiến trình bắt đầu và T mà tiến trình kết thúc phải vẽ ra. Những cái T mình liệt kê ở trên phải được vẽ đầy đủ.

Hy vọng cái này có thể giúp được bạn.
Chúc 1 ngày vui vẻ.

Bạn nói rõ cái này dùm mình voi "T=8 P2 xuất hiện => nhưng P1 đanh chạy nên P2 đưa vào hàng đợi."
Còn cái hình đây, ban xem coi co' đúng không?
|....p1....|...p2...|...p3...|...p1...|...p2...|...p3...|
5.........15.......25.......35........40........50.......55
Bạn vẽ hình đúng rồi, nhưng mình phải vẽ thêm những mốc mà các tiến trình xuất hiện nữa. Hình này cần vẽm thêm mốc T=8 nữa là hoàn hảo.
|....p1....|...p2...|...p3...|...p1...|...p2...|...p3...|
5..8......15.......25.......35........40........50.......55
T=8 thì P2 xuất hiện, nhưng P1 đang chạy nên nó phải đọi P1 chạy xonh thì nó mới chạy. Chỉ vậy thôi. Có lẻ do cách mình dùng từ không chính xác nên bạn hiểu lầm. P2 không phải đưa vào hàng đợi mà vẫn tiếp tục nằm trong hàng đợi và đợi P1 chạy xong mới được vận hành. Giả sử P1 chạy xong trước mốc 8ms thì lúc đó P2 sẽ không cần đợi, CPU chỉ cấp cho mỗi một tiến trình ở mỗi 1 thời điểm.

chính xác

VoMinhThang(I22B) 28/3/2013, 13:47

NguyenThanhTung(I22B) đã viết: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ý.

1. Giới thiệu

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

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

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.

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

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

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.

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.

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

Bạn phải cho ví dụ cụ thể chứ, như vậy "hàn lâm" quá Question

TruongTranThanhTu(I22B) 28/3/2013, 13:50

Multilevel Queue Scheduling:
Được chia thành nhiều queue riêng biệt
Foreground(Chứa các interactive process)
Background(Chứa các backprocess)
Mỗi hàng chờ có thuật giải điều phối riêng
Foreground: RR
Background:FCFS
Quan hệ giữa các mức
Lập lịch với mức độ ưu tiên
Phân chia thời gian: mỗi queue nhận được một lượng thời gian CPU nào đó mà có thể lập lịch các tiến trình của nó
Tiến trình trong queue có mức độ ưu tiên thấp hơn chỉ có thể chạy khi các queue có mức ưu tiên thấp hơn rỗng
Tiến trình có mức ưu tiên cao hơn khi vào ready queue không ảnh hưởng đến tiến trình đang chạy có mức ưu tiên thấp hơn.

Multilevel Feedback Queue Scheduling
Điều tiết tiến trình có thể di chuyển giữa các queue khác nhau
Đa mức hàng đợi đặc trưng bởi các thông số sau:
Số lượng hàng chờ
Giải thuật lập lịch cho mỗi hàng chờ
Phương pháp sử dụng để xác định khi nào thì tăng, giảm mức ưu tiên của một tiến trình
Phương pháp được sử dụng để xác định hàng chờ nào mà tiến rình sẽ đến khi nó cần được phục vụ.

TruongTranThanhTu(I22B) 28/3/2013, 13:57

1. 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.
2. Biểu đồ Gantt có ý nghĩa: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ợ: theo 2 cách chính. Đầu tiên, chúng cung cấp 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 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: 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 đ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 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.

TruongTranThanhTu(I22B) 28/3/2013, 14:05

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.

VoMinhThang(I22B) 28/3/2013, 14:12

NguyenHoangKimVu (I11C) đã viết:
NguyenCaoTri (I22B) đã viết:Một hệ thống có 5 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 FJFS (có tiếm quyền) để điều phối CPU:
a. Thể hiện bằng biểu đồ Gantt.
b. Tính thời gian chờ trung bình của các tiến trình.

T1=(12-2) + (1-1) = 10
T2= 0
T3 = (5-4) + (2-2) = 1
T4 = 0
T5= 6-5= 1

Ttb= (10 +0 +1 +0 +1)/5 = 12/5 =2,4ms

Mong Thầy và các bạn cho ý kiến
P5 chạy tới ms thứ 11 là hết CPU Burst rồi bạn (vì CPU Burst = 5). P1 sẽ chạy tiếp từ ms thứ 11 đến 20.
Biểu đồ lúc đó sẽ thế này.

Thời gian chờ của từng tiến trình thì mình tính như vầy
Thời gian chờ = Thời điểm kết thúc - Thời điểm bắt đầu - CPU Burst
T1 = 20 - 1 - 10 = 9
T2 = 3 - 2 - 1 = 0
T3 = 6 - 3 - 2 = 1
T4 = 5 - 4 - 1 = 0
T5 = 11 - 6 -5 = 1
=> Ttb = (9 + 0 + 1 + 0 + 1)/5 = 2,2 ms

bài sủa của bạn KIMVU hoàn toàn giống với kq của mình, thank cat

dangvannhan(I22A) 28/3/2013, 14:13

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.

VoMinhThang(I22B) 28/3/2013, 15:18

Chia sẻ với các bạn giải thuật Preemptive SJF
(cũng nhờ clip này mà mình hiểu rõ hơn quá trình đang xử lý)

VoMinhThang(I22B) 28/3/2013, 15:23

Chia sẻ với các bạn clip (REVOLUTION OPERATING SYSTEM)
(có thuyết minh)

P/S: Mình đã xem 5 lần rồi mà vẫn không chán

TruongNhuNgoc (I22A) 28/3/2013, 22:10

Có phải Localhost là:
Địa chỉ của một máy chủ (Server) cho phép các máy trong mạng LAN có thể truy xuất thông tin theo một phương thức nào đó.
Thông thường localhost hiểu là một Server trên máy của mình dùng vào một số mục đích nhất định nào đó.

TruongNhuNgoc (I22A) 28/3/2013, 22:10

Câu 1: Trình bài mô hình chuyển trạng thái của tiến trình.

Câu 2: Gỉa sử hệ thống có 2 loại tài nguyên R1 & R2. Tại thời điểm Ti, 2 tiến trình R1 & R2 đang vận hành với tình trạng sữ dụng tài nguyên như sau:
https://2img.net/r/ihimg/photo/my-images/46/89616027.jpg/
a. Giải thích đồ thị trên.
b. Lúc P1 bắt đầu cần đến R2, có nên đáp ứng yêu cầu này? Tại sao?

Câu 3: Sử dụng Visual C++ 6.0 để lập trình đánh thức (ResumeThread) tất cả các luồng sản xuất. Biết rằng, mục quản (Handle) của chúng lưu trong mảng khai báo bằng lệnh:
HANDLE ProducerHandles[50]

Câu 4: Một hệ thống có 3 tiến trình với thời gian đến và thời gian sử dụng CPU
Tiến trình Thời gian (ms) CPUBurst (ms)
P1 - 5 - 25
P2 - 20 - 15
P3 - 30 - 10

Dùng giải thuật Round – Robin với thời lượng 10ms để điều phối CPU.
a. Thể hiện biểu đồ Gantt.
b. Tính thời gian chờ trung bình của tiến trình.

Câu 5: Một hệ thống có 8 máy đọc hình và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti, thể hiện bằng các vecto Allocation = (2,2,2) và Max = (5,4,5).
Dùng thuật giải nhà băng để:
a. Chứng minh trạng thái này an toàn.
b. Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy của P2 ?

damvanhau(I22A) 28/3/2013, 22:22

NguyenHoangKimVu (I11C) đã viết:Ở một công ty, các nhân viên lần lượt được phân công đi công tác ở Đà Nẵng, Long An, Cần Thơ.
Có tiếm quyền : Anh A được công ty cấp ô tô cho đi công tác ở Đà Nẵng. Và anh ta lấy xe đi luôn, không có cách nào để công ty điều xe về ngay lập tức để cho người khác đi công tác.
Không tiếm quyền : Cũng anh A được công ty cấp ô tô cho đi công tác ở Đà Nẵng. Đi giữa đường thì anh A ghé vào quán nghĩ ngơi. Ngay lúc đó, công ty có lệnh điều xe về chở anh B đi công tác ở Long An. Xe lập tức quay về và chở anh B đi Long An. Giữa đường, anh B cũng ghé vào quán nghỉ ngơi. Và lúc đó, công ty lại có lệnh điều xe về chở anh C đi công tác ở Cần Thơ. Cứ thế xe được điều động cho 3 anh đi công tác !

Ví dụ cho bị ngược rồi

NguyenThiBichTram (I22A) 28/3/2013, 22:31

Là địa chỉ IP của Server của bạn
Khi bạn cho Server chạy trên máy của bạn, thì các file nằm trong một thư mục nhất định (như \htdocs cho Server Apache). Thư mục ấy có địa chỉ là :http://127.0.0.1, hay http://localhost (cái này thuộc ... công ước quốc tế rồi).
Thí dụ file của bạn là myfile.html, thì bạn gõ URL trên trình duyệt là : http://localhost/myfile.html
Muốn upload lên Server Internet bạn phải xin một space disk gọi là hosting space, có IP riêng, tên miền riêng, (xin ở Hosting hay ISP) và với những chi tiết này, dùng software FTP để chuyển file lên. Không thể chuyển thẳng từ Server của bạn tới Server của Internet được bằng PHP đâu, ít khi được cho phép. Có vài ISP cho phép chuyển bằng trình duyệt tại vì khi logon bạn đã đưa ra User ID và PW.

phanthanhcan(I22A) 28/3/2013, 22:50

ví dụ:
tại ngã tư, cảnh sát giao thông (CSGT) là CPU, hai làn đường D1 D2 là hai tiến trình. Thời gian dừng đèn đỏ là 20 giây, đèn xạnh là 20 giây.

Không tiếm trình : mọi người đi theo hiệu lệnh của CSGT, thời gian chờ đèn tín hiệu là 20 giây.

Có tiếm trình: vào buổi sáng, có những lúc làn đường D1 có số người đông gấp 2 lần D2.

Thì khi đó CSGT (là cpu) sẽ điều chỉnh thời gian đèn xanh của làn D1 tăng lên 30 giây, và giảm đèn xanh của D2 còn 10 giây.

vậy đường d1 chiếm đường d2 hết 10 giây.
vì vậy con đường D1 đảm bảo được lưu thông, luôn được thông thoáng.

NgT.KimHuyen(I22A) 28/3/2013, 22:53

HoangThanhThien(I22B) đã viết:
TruongMinhTriet(I22B) đã viết:Cách 1: Dùng giải thuật RRS

Thời gian trung bình: ((0+35)+(10+25)+25)/4 = 23,75 (ms)

Cách này do e tự nghỉ ra không bít có đúng hay không nữa: e kết hợp giữa SJFS có tiến quyền với RRS.

Thời gian trung bình: (0 + 20 + 10 + 25 + 0)/4 = 13,75 (ms)

Không bít cách e hiểu và làm có đúng hay không mong thầy có e ý kiến để sửa sai, e xin cảm ơn.

kết hợp luôn à

học chung bạn Triết 2 năm rồi, làm đề tài cũng chung nên h quen cách nì của bạn ấy lun ớ..chuyên gia sáng tạo mấy cái mới hót hót mà chưa ai nghĩ ra ^^

Sponsored content

Thảo luận Bài 6

Bài tập giải thuật RRS

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

thảo luận bài 6

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

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

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

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

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

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

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

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

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

So sánh MQS (Multilevel Queue Scheduling) và MFQS (Multilevel Feedback Queue Scheduling)

Ý nghĩa của biểu đồ Gantt

Chức năng điều phối CPU - Năm tiêu chí điều phối CPU

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

Các thuật giải căn bản trong điều phối CPU

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

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

Localhost là gì ?

Đề thi mẫu

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

Re: Localhost là gì ?

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

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

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