Thảo luận Bài 6

Thảo luận những vấn đề liên quan đến Bài 6.

4 tính huống:
- Khi tiến trình chuyển từ Running sang Waiting (Chờ I/O, chờ tiến trình con).
- Khi tiến trình chuyển từ Running sang Ready ( do ngắt xảy ra).
- Khi tiến trình chuyển từ Waiting sang Ready ( khi kết thúc I/O).
- Khi tiến trình kết thúc công việc.

Phân biệt điều khối có tiếm quyền (Preemptive) và điều phối không tiếm quyền (Non- Preemptive):
- Giống nhau: Được dùng trong đ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:
+ Điều phối không tiếm quyền: Có nghĩa là khi tiến trình P1 có thời điểm đến trước P2 thì tiến trình P1 được thực hiện hết khoảng thời gian thực hiện, sau đó mới thực hiện tiến trình P2.
+ Điều phối có tiếm quyền: Có nghĩa là khi có 3 tiến trình P1, P2, P3 có thời điểm đến theo thứ tự đó thì tiến trình P1 sẽ được thực hiện với một khoảng thời gian cho phép sau đó bị tiến trình P2 hay P3 tiếm quyền. Còn quá trình điều phối kế tiếp như thế nào là tuỳ thuộc vào thuật toán điều phối và độ ưu tiên của tiến trình.

Câu 1: Trình bày 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 có tiếm quyền với điều phối không tiếm quyền.
Câu 2: Giải bài tập điều phối CPU với thuật giải SJFS có tiếm quyền.
Câu 3: Giải bài tập điều phối CPU với thuật giải Round Robin Scheduling-RRS.
Thảo luận: +Tìm hiểu về Henry Laurence Gantt.
................+Sử dụng Visual C++ 6.0 để lập trình đánh thức (Resume Thread) tất cả các luồng sản xuất. Biết rằng mục quản (HANDLE) của chúng ta lưu trong mảng khai báo bằng lệnh:

a) Thuật giải MQS ( Multilevel Queue Scheduling )
- 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.




b) Thuật giải MFQS ( Multilevel Feedback Queue Scheduling )
- 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

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



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

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


- 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

*Multilevel Queue Scheduling - MQS

-Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau.
VD:Mức các tiến trình tương tác chạy ở mặt trước 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.
-Mỗi hàng chờ có thuật giải để điều phối riêng.
-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 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ức cao hơn,tiến trình mức dưới sẽ bị tiếm quyền do tiến trình mới có độ ưu tiên cao hơn.
+Phân bổ theo tỉ lệ thời lượng.

* Multilevel Feedback Queue Scheduling - MFQS

-Như MSQ nhưng cho phép điều tiết tiến trình sang mức khác.
VD:Những tiến trình hướng CPU được đưa xuống mức dưới
-MFQS đạc trưng bởi các thông số:
+Số mức.
+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ờ cho tiến trình mới.

Ví dụ: Trong ga tàu có 5 ô cửa bán vé, những người mua vé xếp hàng vào 5 cửa. Có 5 loại khách hàng với 5 loại ưu tiên khác nhau. Chỉ có 1 cô nhân viên bán vé thôi.
+ cửa 1: cửa hệ thống: cho những người trong ngành hoặc thân nhân của những người trong ngành đường sắt.
+ cửa 2: cho thương binh, Mẹ VNAH.
+ cửa 3: cho những người bình thường, khách vảng lai.
+ cửa 4: khách có độ ưu tiên thấp hơn.
+ cửa 5: cho Sinh viên.
Với MQS: chỉ 1 cô bán vé chạy từ cửa này sang cửa kia, cửa nào có khách thì chạy sang cửa đó.
Với MFQS: có điều phối nếu có sự ưu tiên, đẩy bớt tiến trình từ cửa này sang cửa kia, giúp cho hoạt động được tốt hơn.
ĐỘ ƯU TIÊN HẠ TỪ TRÊN XUỐNG, KHÔNG CÓ SỰ ƯU TIÊN TỪ MỨC DƯỚI ĐI NGƯỢC LÊN MỨC TRÊN.

Admin
Nhấn mạnh như trên là Sai, vì trong trường hợp chung, MFQS cho phép đưa tiến trình từ mức này sang mức kia, không nhất thiết phải Hạ cấp hay Nâng cấp ! Sơ đồ cuối Bài 6 chỉ phản ánh 1 trường hợp riêng.

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



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

Điều phối hàng chờ nhiều mức (Multilevel Queue Scheduling - 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.
Điều phối hàng chờ nhiều mức có điều tiết ( Multilevel Feedback Queue Scheduling - MFQS )
• Như MQS nhưng cho phép Điều tiết tiến trình sang mức khc, 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

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

*Multilevel Queue Scheduling - MQS

-Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau.
VD:Mức các tiến trình tương tác chạy ở mặt trước 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.
-Mỗi hàng chờ có thuật giải để điều phối riêng.
-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 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ức cao hơn,tiến trình mức dưới sẽ bị tiếm quyền do tiến trình mới có độ ưu tiên cao hơn.
+Phân bổ theo tỉ lệ thời lượng.

* Multilevel Feedback Queue Scheduling - MFQS

-Như MSQ nhưng cho phép điều tiết tiến trình sang mức khác.
VD:Những tiến trình hướng CPU được đưa xuống mức dưới
-MFQS đạc trưng bởi các thông số:
+Số mức.
+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ờ cho tiến trình mới.

Ví dụ: Trong ga tàu có 5 ô cửa bán vé, những người mua vé xếp hàng vào 5 cửa. Có 5 loại khách hàng với 5 loại ưu tiên khác nhau. Chỉ có 1 cô nhân viên bán vé thôi.
+ cửa 1: cửa hệ thống: cho những người trong ngành hoặc thân nhân của những người trong ngành đường sắt.
+ cửa 2: cho thương binh, Mẹ VNAH.
+ cửa 3: cho những người bình thường, khách vảng lai.
+ cửa 4: khách có độ ưu tiên thấp hơn.
+ cửa 5: cho Sinh viên.
Với MQS: chỉ 1 cô bán vé chạy từ cửa này sang cửa kia, cửa nào có khách thì chạy sang cửa đó.
Với MFQS: có điều phối nếu có sự ưu tiên, đẩy bớt tiến trình từ cửa này sang cửa kia, giúp cho hoạt động được tốt hơn.
ĐỘ ƯU TIÊN HẠ TỪ TRÊN XUỐNG, KHÔNG CÓ SỰ ƯU TIÊN TỪ MỨC DƯỚI ĐI NGƯỢC LÊN MỨC TRÊN.

ví dụ về MQS
ga tàu có 2 cửa bán vé cửa sô 1 dành cho những người có công như thương bệnh binh, bà mẹ việt nam anh hùng. cửa số 2 dành cho những người bình thường như sinh viên, học sinh. lúc đó có 2 cô bán vé cho hai cửa bán vé này, nhưng một cô có việc phải về. cô còn lại ở lại bán vé nhưng cô này luôn bán vé ưu tiên cho cửa số 1 hơn là cửa số 2, mỗi lần không có khách ở ô cửa số 1 cô ta lại chạy sang cửa số 2 để bán, nhưng khi cửa số 1 có khách thì cô ta ngay lập tức qua ô cửa số 1 để bán vé cho dù ô cửa số 2 khách đang đông và đang chờ.
ví dụ về MFQS
cũng hai ô cửa bán vé trên, nhưng xảy ra trường hợp tại ô cửa số 2 một vị khách có việc gấp cần được mua vé thì vị khách này sẽ được chuyển qua ô cửa số 1 để được mua vé

Câu 1: 4 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 và điều phối có tiếm quyền

Bốn 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 và điều phối có tiếm quyền

- Điều phối Không tiếm quyền (Non-Preemptive): sơ đồ điều phối chỉ tiến hành trong tình huống 1 và 4. Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting (cách làm trong Windows 3.1 và Macintosh OS). Dùng khi máy không có Timer.

- Điều phối Có tiếm quyền (Preemptive): sơ đồ điều phối tiến hành trong cả 4 tình huống được

Câu 3: Bài tập Điều phối CPU với thuật giải Round-Robin Scheduling (RRS)
Đề bài: một hệ thống có 3 tiến trình với thời điểm đến và sử dụng CPU như sau:



- Dùng thuật giải Round Robin vời thời lượng là 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 ?
Giải:



b. Tình thời gian chờ trung bình của tiến trình:
+ Thời gian chờ của các tiến trình:
- P1=(40-5)-25=35-25 =10 (ms)
- P2=(55-20)-15=35-15=20 (ms)
- P3=(50-30)-10=20-10=10 (ms)
+ Thời gian chờ trung bình của tiến trình:
(P1+P2+P3)/3=(10+20+10)/3=40/3=13.3(ms)

Giống nhau:
Thuật giải điều phối hàng chờ nhiều mức (Multilevel Queue Scheduling) và thuật giải điều phối hàng chờ nhiều mức có điều tiết (Multilevel Feedback Queue Scheduling) cùng sử dụng nhiều hàng chờ có độ ưu tiên khác nhau, mỗi hàng chờ có thể sử dụng cách điều phối khác nhau như điều phối theo vòng Robin (Round Robin Scheduling) hay First Come First Served (FCFS)

Khác nhau:
Thuật giải điều phối hàng chờ nhiếu mức có điều tiết (MFQS) có tính mềm dẻo, uyển chuyển hơn, cho phép điều phối tiến trình từ hàng chờ này sang hàng chờ khác (hạ mức độ ưu tiên xuống)

Ví dụ minh họa:
Phòng bán vé tàu hỏa có nhiều cửa bán vé với mức độ ưu tiên khác nhau, có cửa dành cho những người trong hệ thống (công nhân viên phục vụ trong ga), có cửa dành riêng cho thương binh, người tàn tật...Chỉ có 1 cô bán vé (CPU) phải liên tục di chuyển giữa các cửa để phục vụ cho khách mua vé.
- Với trường hợp MQS thì khách mua vé thuộc loại nào thì đứng yên ở cứa đó chờ tới lượt để được mua vé.
- Với trường hợp MFQS thì người xếp hàng mua vé có thể được chuyển sang cửa khác mua vé (nếu cửa đang đứng quá đông), để đảm bảo chất lượng phục vụ là tốt nhất.

HaHoangCongTien80 (113A) đã viết:Câu 3: Bài tập Điều phối CPU với thuật giải Round-Robin Scheduling (RRS)
Đề bài: một hệ thống có 3 tiến trình với thời điểm đến và sử dụng CPU như sau:
a) Thể hiện biểu đồ Gantt ?
b) Tình thời gian chờ trung bình của tiến trình ?
Giải:



b. Tình thời gian chờ trung bình của tiến trình:
+ Thời gian chờ của các tiến trình: - P1=(40-5)-25=35-25=10 (ms)
- P1=(40-5)-25=35-25 =10 (ms)
- P2=(55-20)-15=35-15=20 (ms)
- P3=(50-30)-10=20-10=10 (ms)
+ Thời gian chờ trung bình của tiến trình:
(P1+P2+P3)/3=(10+20+10)/3=40/3=13.3(ms)

bài này ko hiểu cho lắm có ai giải thích tường tận từng dòng không...nhất là biểu đồ gantt???và cách vẽ

MaiTrieuHung16 (113A) đã viết:Câu 1: Trình bày 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 có tiếm quyền với điều phối không tiếm quyền.
Câu 2: Giải bài tập điều phối CPU với thuật giải SJFS có tiếm quyền.
Câu 3: Giải bài tập điều phối CPU với thuật giải Round Robin Scheduling-RRS.
Thảo luận: +Tìm hiểu về Henry Laurence Gantt.
................+Sử dụng Visual C++ 6.0 để lập trình đánh thức (Resume Thread) tất cả các luồng sản xuất. Biết rằng mục quản (HANDLE) của chúng ta lưu trong mảng khai báo bằng lệnh:

HANDLE ProducerHandles [50]

Bổ sung:
Câu 4: Phân biệt thuật giải MQS và thuật giải MFQS? Cho ví dụ minh họa? Giải thích sư đồđiều phối hàng đợi có nhiều mức?

VuMinhTan (113A) đã viết:

HaHoangCongTien80 (113A) đã viết:Câu 3: Bài tập Điều phối CPU với thuật giải Round-Robin Scheduling (RRS)
Đề bài: một hệ thống có 3 tiến trình với thời điểm đến và sử dụng CPU như sau:
a) Thể hiện biểu đồ Gantt ?
b) Tình thời gian chờ trung bình của tiến trình ?
Giải:



b. Tình thời gian chờ trung bình của tiến trình:
+ Thời gian chờ của các tiến trình: - P1=(40-5)-25=35-25=10 (ms)
- P1=(40-5)-25=35-25 =10 (ms)
- P2=(55-20)-15=35-15=20 (ms)
- P3=(50-30)-10=20-10=10 (ms)
+ Thời gian chờ trung bình của tiến trình:
(P1+P2+P3)/3=(10+20+10)/3=40/3=13.3(ms)

bài này ko hiểu cho lắm có ai giải thích tường tận từng dòng không...nhất là biểu đồ gantt???và cách vẽ

bài này bạn muốn hiểu rõ phải vẽ thêm 1 cái hàng đợi gọi là Ready Queue

MaiTrieuHung16 (113A) đã viết:Câu 1: Trình bày 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 có tiếm quyền với điều phối không tiếm quyền.
Câu 2: Giải bài tập điều phối CPU với thuật giải SJFS có tiếm quyền.
Câu 3: Giải bài tập điều phối CPU với thuật giải Round Robin Scheduling-RRS.
Thảo luận: +Tìm hiểu về Henry Laurence Gantt.
................+Sử dụng Visual C++ 6.0 để lập trình đánh thức (Resume Thread) tất cả các luồng sản xuất. Biết rằng mục quản (HANDLE) của chúng ta lưu trong mảng khai báo bằng lệnh:

HANDLE ProducerHandles [50]

câu 4 : Phân biệt thuật giải MQS (Multilevel Queue Schediling) với thuật giải MFQS (Multilevel Feeback Queue Schediling) . Cho các ví dụ minh họa . Giải thích sơ đồ điều phối hàng chờ nhiều mức có điều tiết.

[quote="VuMinhTan (113A)"]

HaHoangCongTien80 (113A) đã viết:Câu 3: Bài tập Điều phối CPU với thuật giải Round-Robin Scheduling (RRS)
Đề bài: một hệ thống có 3 tiến trình với thời điểm đến và sử dụng CPU như sau:
a) Thể hiện biểu đồ Gantt ?
b) Tình thời gian chờ trung bình của tiến trình ?
Giải:



b. Tình thời gian chờ trung bình của tiến trình:
+ Thời gian chờ của các tiến trình: - P1=(40-5)-25=35-25=10 (ms)
- P1=(40-5)-25=35-25 =10 (ms)
- P2=(55-20)-15=35-15=20 (ms)
- P3=(50-30)-10=20-10=10 (ms)
+ Thời gian chờ trung bình của tiến trình:
(P1+P2+P3)/3=(10+20+10)/3=40/3=13.3(ms)

Theo mình hiểu thì:
Theo bảng thông tin ta có 3 tiến trình P1,P2,P3 lần lượt có thời điểm đến và thời gian sử dụng CPU.
Khi vẽ biểu đồ Gantt: ta bắt đầu từ thời điểm 0.
Ta xét trên bảng thông tin thì thấy P1 có thời điểm đến là 5 vậy P1 sẽ được dùng CPU trước.Vì thế P1 sẽ bắt đầu từ 5 chạy đến 15 (vì theo qui định thời lượng dùng CPU chi là 10ms).Và số CPU-Burst của P1 chỉ còn 15 (25-10=15).
Tiếp đến tại vị trí 15 ta hãy xét trên bảng thông tin xem có tiến trình nào có thời điểm đến tại mức 15 không.Nhận thấy rằng không có tiến trình nào cả cho nên P1 chạy tiếp đến mức 25 (15+10(thời lượng qui định)).Và số CPU-Burst của P1 chỉ còn 5 (15-10=5).
Tiếp đến tại vị trí 25 ta hãy xét trên bảng thông tin xem có tiến trình nào có thời điểm đến tại mức 25 không.Nhận thấy rằng có P2 có thời điểm đến là 20,như vậy P2 đã chờ.Ta có ready queue:P2.Do P2 đã chờ nên P1 bị ngắt và P2 được sử dụng CPU.Cho nên từ mức 25->35 là của P2 .Và số CPU-Burst của P2 chỉ còn 5 (15-10=5).Còn P1 thì được xếp và ready queue:P2-P1.
Tiếp đến tại vị trí 35 ta hãy xét trên bảng thông tin xem có tiến trình nào có thời điểm đến tại mức 35 không.Ta thấy có P3 đã có thời điểm đến 30 và nó đã chờ,cho nên Ready Queue:P2-P1-P3.Do P1 đã chờ trước nên được sử dụng CPU tại mức 35->40 (vì P1 lúc này số CPU-Burst của P1 chỉ còn 5 ),P2 bị ngắt đưa vào Ready Queue .Và Ready Queue:P2-P1-P3-P2.
Tiếp đến vị trí 40 do P3 đã chờ trước nên P3 được dùng CPU tại 40->50 .Và Ready Queue:P2-P1-P3-P2.
Cuối cùng là P2 từ 50->55 (vì số CPU-Burst của P2 còn 5).Xong!!!

xin mọi người bổ sung...

Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)
* 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ó. (Có nghĩa là ko được ngắt CPU khi 1 tiến trình đang chạy).

Ví dụ: Ở lớp 113A, bình thường 18h vô lớp thì ai đến sớm thì có quyền ngồi chỗ tốt mà mình chọn ( thông thường bạn nào cận thì thường đi sớm để được ngồi bàn 1)

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

Ví dụ: Ở quán nhậu khi chúng ta tới đó ăn và kêu 10 món (đi đông nên kêu nhiều), bồi bàn tới ghi sổ và đưa cho anh đầu bếp làm 10 món. Đang làm được 4 món thì có thực khách bàn B gọi 7 món nhậu thì người đầu bếp chuyển sang làm thức ăn cho thực khách bàn B. Trong khi đang làm được 3 món ăn cho bàn B thì lại có thêm thực khách bàn C kêu 4 món thì anh đầu bếp sẽ quay sang làm 4 món cho bàn C. Trong khi làm được 2 món cho bàn C thì thực khách bàn D gọi 1 món thì anh đầu bếp quay sang làm 1 món cho thực khách bàn D.

Giống nhau:

Được dùng trong đ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 tiến trình P1 có thời điểm đến trước P2 thì tiến trình P1 được thực hiện hết khoảng thời gian thực hiện, sau đó mới thực hiện tiến trình P2.

- Preemptive Scheduling: Có nghĩa là khi có 3 tiến trình P1, P2, P3 có thời điểm đến theo thứ tự đó thì tiến trình P1 sẽ được thực hiện với một khoảng thời gian cho phép sau đó bị tiến trình P2 hay P3 tiếm quyền. Còn quá trình điều phối kế tiếp như thế nào là tuỳ thuộc vào thuật toán điều phối và độ ưu tiên của tiến trình.

Bốn tình huống ra quyết định của trình điều phối CPU:
* Các tình huống ra quyết định của trình điều phối:
1. Khi tiến trình chuyển từ Running sang Waiting (Chờ I/O. chờ tiến trình con)
2. Khi tiến trình chuyển từ Running sang Ready (do ngắt xảy ra)
3. Khi tiến trình chuyển từ Waiting sang Ready (khi kết thúc I/O)
4. Khi tiến trình kết thúc công việc.
Phân biệt điều phối có tiếm quyền(Preemptive Scheduling) và điều phối không tiếm quyền (Non-Preemptive Scheduling)
+ Có tiếm quyền: Điều phối chỉ xảy ra ở thời điểm 1 va 4, không xảy ra điều phối ở thời điểm 2 và 3. Tiến trình giữ CPU cho đến khi kết thúc bình thường hoặc khi chuyển sang trạng thái Waiting (cách làm trong Windows 3.1 và Macintosh OS). Dùng khi máy không có Timer. Trên HĐH hiện đại đa số có tiếm quyền.
+ Không tiếng quyền: Xảy ra trong cả 4 tình huống. Có thể bắt được tiến đang chạy, không cho độc chiếm CPU

* Bốn 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/Counter.(Quá trình running nếu bị ngắt sẽ tiếp tục running sau đó).
- 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).

* 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 dùng trong đ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 tiến trình P1 có thời điểm đến trước P2 thì tiến trình P1 được thực hiện hết khoảng thời gian thực hiện, sau đó mới thực hiện tiến trình P2.

- Preemptive Scheduling: Có nghĩa là khi có 3 tiến trình P1, P2, P3 có thời điểm đến theo thứ tự đó thì tiến trình P1 sẽ được thực hiện với một khoảng thời gian cho phép sau đó bị tiến trình P2 hay P3 tiếm quyền. Còn quá trình điều phối kế tiếp như thế nào là tuỳ thuộc vào thuật toán điều phối và độ ưu tiên của tiến trình.

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

* Điều phối hàng chờ nhiều mức (Multilevel Queue Scheduling - MQS)
- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau. VD:Mức các tiến trình tương tác chạy ở mặt trước 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.
- Mỗi hàng chờ có thuật giải để điều phối riêng.
- 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 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ức cao hơn,tiến trình mức dưới sẽ bị tiếm quyền do tiến trình mới có độ ưu tiên cao hơn.
+ Phân bổ theo tỉ lệ thời lượng.

* Điều phối hàng chờ nhiều mức có điều tiết (Multilevel Feedback Queue Scheduling - MFQS)
- Như MSQ nhưng cho phép điều tiết tiến trình sang mức khác. VD:Những tiến trình hướng CPU được đưa xuống mức dưới.
- 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.
ví dụ: trong lớp học thì bàn 1 được ưu tiên. Khi cần gọi lên để làm bài ( nếu làm không được ) thì thầy sẽ chuyển sang bàn thứ 2 để gọi lên.


So sánh sự giống nhau và khác nhau giữa giải thuật MQS và MFQS:

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

* Khác nhau: Multilevel Feedback Queue Scheduling cho phép điều chuyển (điều tiết) tiến trình từ hàng chờ này sang hàng chờ kia (hạ cấp độ hay nâng cấp độ ưu tiên), nghĩa là mềm dẻo hơn Multilevel Queue Scheduling.
- Và đối với MQS thì khi các tiến trình được xếp vào hàng đợi thì không thay đổi được vị trí còn MFQS thì tiến trình có thể di chuyển từ mức này sang mức khác và ngược lại.

Ví dụ: Trong ga tàu có 5 ô cửa bán vé, những người mua vé xếp hàng vào 5 cửa. Có 5 loại khách hàng với 5 loại ưu tiên khác nhau. Chỉ có 1 cô nhân viên bán vé thôi.
+ Cửa 1: cửa hệ thống: cho những người trong ngành hoặc thân nhân của những người trong ngành đường sắt.
+ Cửa 2: cho thương binh.
+ Cửa 3: cho những người bình thường, khách vãng lai.
+ Cửa 4: khách có độ ưu tiên thấp hơn.
+ Cửa 5: cho Sinh viên.
Với MQS: chỉ 1 cô bán vé chạy từ cửa này sang cửa kia, cửa nào có khách thì chạy sang cửa đó.
Với MFQS: có điều phối nếu có sự ưu tiên, đẩy bớt tiến trình từ cửa này sang cửa kia, giúp cho hoạt động được tốt hơn.