Thảo luận Bài 6

o Giải thuật MQS (điều phối hàng chờ nhiều mức)
 Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau.
 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 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.
o Giải thuật MFQS ( điều phối hàng chờ nhiều mức có điều tiết)
 Như MQS nhưng cho phép Điều tiết tiến trình sang mức khác.
 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ụ:
Phòng bán vé tàu ở ga Hòa Hưng có 5 của bán vé, và các người mua vé được xếp vào 5 cửa để chờ mua vé.
- Cửa số 1 : dành cho những người hệ thống, làm việc ở ga, gia đình thân nhân của những người làm ở ga.
- Cửa số 2 : dành cho những người thương binh, mất sức lao động, bà mẹ VN anh hùng.
- Cửa số 3 : dành cho những người bình thường và khách vãng lai.
- Cửa số 4 : dành cho những người ưu tiên ở mức độ thấp hơn.
- Cửa số 5 : dành cho học sinh, sinh viên.
Nhiều cửa bán vé ở trên có độ ưu tiên khác nhau, trong đó chỉ có 1 cô bán vé (1 CPU) phải luân chuyển giữa các cửa để phục vụ đủ loại người mua (các tiến trình) bao gồm nhiều mức độ ưu tiên khác nhau như: người hệ thống (gia đình thân nhân của người làm việc tại ga), thương binh – mẹ VN anh hùng – người mất sức lao động, khách vãng lai…
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.

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 (do kết thúc I/O)
4. Khi tiến trình kết thúc công việc.
o 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.
o 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)

1. FCFS (First Come First Served): Đến trước có trước
- Được cấp CPU từ đầu dãy đến cuối dãy theo quy tắc FIFO
2. PS (Priority Scheduling): ưu tiên
- Mỗi tiến trình được cấp một số nguyên dùng ấn định độ ưu tiên (Priority Number)
- CPU luôn dành cho tiến trình có độ ưu tiên cao hơn ( Priority Number càng nhỏ, độ ưu tiên càng cao)
- Với 2 phương án: Tiếm quyền và không tiếm quyền
3. SJFS (Shortest Job - First Served): Nhỏ nhất chạy trước
- Tiến trình nào có khoảng CPU kế tiếp nhỏ hơn thì được chạy trước. Trường hợp = nhau, dùng FCFS
- SJFS không tiếm quyền: 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: tiến trình mới có khoảng CPU kế tiếp nhỏ hơn khoảng CPU còn lại của tiến trình đang vận hành thì được ưu tiên chạy trước.
4. RRS (Round Robin Scheduling)
- Như FCFS nhưng cho phép tiếm quyền khi tiến trình hiện hà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 (10-100ms). Sau thời gian này, nó bị tiếm quyền và đưa vào cuối hàng chờ Ready Queue. Tiến trình đầu tiên trong hàng chờ Ready Queue được phép chạy.
- Nếu có n tiến trình và thời lượng 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. MQS (Multi 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.
6. MFQS (Multi 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

Giải thích sơ đồ:

- Đây là sơ đồ điều phối CPU của thuật giải Multilevel Feedback Queue với ba hàng chờ Ready cho các mức độ khác nhau. Độ 0 là độ cao nhất và độ 2 là thấp nhất theo quan niệm của Linux. Linux quan niệm độ càng nhỏ thì mức ưu tiên càng cao, quan niệm này ngược với quan niệm của Windows vì Windows quan niệm độ càng cao thì mức ưu tiên càng cao.
- Đầu tiên tiến trình được đưa vào hàng chờ thứ nhất theo đường mũi tên đi vào và khi cần thiết nó lại đưa xuống hàng chờ với độ ưu tiên thấp hơn. Xong việc tiến trình được đưa ra khỏi hệ thống theo đường mũi tên ra ngoài.
- Chú ý: theo sơ đồ này chỉ có hạ cấp tiến trình theo đường mũi tên từ trên đi xuống. Ở trên là cao nhất và được dùng thuật giải vòng Robin (Round Robin Scheduling - RRS) với thời lượng Quantum = 8 ms. Sang hàng đợi thứ hai các tiến trình được phục vụ bởi thuật giải vòng Robin với thời lượng Quantum = 16ms. Mức độ 3 là mức thấp nhật với các tiến trình nền, các tiến trình hoạt động trong hậu trường thì đó là các tiến trình Background được phục vụ bởi thuật giải FCFS (First - Come, First - Served Scheduling) tức là đến trước chạy trước.
- Với các tiến trình trong hàng đợi (chú ý trong phần này chỉ có hạ cấp tiến trình mà không có nâng cấp tiến trình) ở cấp độ 0 thuật giải được áp dụng là Round Robin với thời lượng là 8.
- Với các tiến trình trong hàng chờ ở cấp độ 1 thuật giải được áp dụng là Round Robin với thời lượng là 16.
- Với các tiến trình trong hàng chờ ở cấp độ 2 thuật giải được áp dụng là FCFS.
- Như vậy ở đây có sự phối hợp của các thuật giải khác nhau là: MFQS, RRS và FCFS.

3. phân biệt thuật giải MSQS và MQS cho vd minh họa từ đời thường
*giống nhau : cùng có nhiều hàng đợi Ready và mức ưu tiên
*khác nhau:
- MSQS uyển chuyển hơn cho phép có thể điều tiết các tiến trình với mức ưu tiên
khác nhau.
-MQS thì máy móc tiến trình nào với mức ưu tiên trước thì làm trước không thể điều tiết tốt khi có các tiến trình phải cần ưu tiên hon thì không làm được.

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

Phân biệt thuật giải MSQ với thuật giải MFSQ
*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 Hòa Hưng 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.

*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 Hòa Hưng 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.

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.

BuiPhamAnBinh(I12A) đã viết:Tiến trình ++++++ thời điểm đến (ms) ++ CPU-Bust

p1 ............ ........... 5 .............. ............. .. 25

p2 ........... ............ 10 ........... ............ ... 15

p3 ............. ........... 20 .......... ............ ... 10
.

biểu đồ Gantt


RRS với thời lượng = 10 ms

p1((55-5)-25)=25ms
p2((50-10)-15)=25ms
p3((45-20)-10)=15ms
Thời gian chờ TB
(25+25+15)/3 =21.7(ms)


các bạn có phần giải thích nào dể hiểu có thể bổ xung thêm cho bài tập này .thank

Mình xin giải thích như sau có sai chỗ nào mọi người cùng góp ý kiến để cùng nhau hiểu bài nha
-Ban đầu P1 vào chạy được 10ms đầu tiên cpu sử dụng xong còn lại là 25-10=15ms sau đó P2 vào vì nó đang chờ ở thời điểm 10ms P1 đang chờ ở thời điểm 15ms nên p2 được tiếm quyền
-P2 vào chạy được 10ms cpu sử dụng còn lại là 15-10=5ms sau đó P1 nhảy vào tiếm quyền P2 vì P1 đang chờ ở 15ms còn p3 đang chờ ở 20ms
-P1 vào chạy được 10ms cpu sử dụng còn lại là 15-10 =5ms sau đó P3 sẽ tiếm quyền P1 vì P3 đang chờ ở 20ms còn P1 là 35ms P2 là 25ms
-P3 vào chạy 10ms hết cpu chỉ còn lại P1,P2 vì P1 đang chờ ở thời điểm 25ms nên được tiếm quyền P3 chạy 5ms cpu còn lại chạy hết P2 chỉ còn lại P1
-cuối cùng P1 vào chay hết cpu còn lại của mình 5ms

HuynhMinhChanh(i91C) đã viết:Về bài tập chương 6, em nhận thấy, quan trọng nhất trong bài tập đó là vẽ chính xác được Gantt. Như vậy, áp dụng công thức mà thầy cho : (Thời điểm kết thúc - Thời Điểm Đến) - (CPU-Burst) sẽ dễ dàng hơn.

Em mong thầy hướng dẫn cách và kỹ thuật để vẽ Gantt cho chính xác trong bài làm, để có thể đạt được trọn vẹn điểm bài tập trong câu hỏi về chương 6 này.

Cảm ơn thầy,

Hoặc bạn nào có cách vẽ hiệu quả, có thể chỉ lại cho lớp hoặc cho mình biết nhé.

Admin
Buổi học cuối cùng sẽ dành để Ôn tập. Bài này và một số bài khác sẽ được giải lại.

Minh họa như sau:


Mình vẽ Hình minh hoa bang Corel Draw:

Admin
- Hình vẽ đẹp. Cho các bạn biết vẽ bằng công cụ gì ?
- Về phương pháp chọn tiến trình, khi tiến trình hiện hành hết thời lượng: Có gì đó chưa ổn. Các bạn cùng thảo luậ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

- 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 và chiến lược định thời CPU.
- Năm tiêu chí điều phối CPU là những tiêu chí nào?
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.

- Điều phối tiến trình
Trong môi trường đa chương, có thể xảy ra tình huống nhiều tiến trình đồng thời sẵn sàng để xử lý. Mục tiêu của các hệ phân chia thời gian (time-sharing) là chuyển đổi CPU qua lại giữa các tiến trình một cách thường xuyên để nhiều người sử dụng có thể tương tác cùng lúc với từng chương trình trong quá trình xử lý.
Để thực hiện được mục tiêu này, hệ điều hành phải lựa chọn tiến trình được xử lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối thích hợp để thực hiện nhiệm vụ này. Một thành phần khác của hệ điều hành cũng tiềm ẩn trong công tác điều phối là bộ phân phối (dispatcher). Bộ phân phối sẽ chịu trách nhiệm chuyển đổi ngữ cảnh và trao CPU cho tiến trình được chọn bởi bộ điều phối để xử lý.
- 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 đó

Henry Laurence Gantt (sinh 1861 - mất 23 tháng 11 năm 1919) là một kĩ sư cơ khí và cố vấn dự án người Mỹ, nổi tiếng với việc phát triển sơ đồ Gantt năm 1910. Sơ đồ Gantt được sử dụng rộng rãi trong những công trình lớn như đập Hoover hay hệ thống đường quốc lộ liên bang Mỹ và ngày nay vẫn là một công cụ quan trọng trong quản lý dự án.



Tiểu sử
Henry Gantt sinh tại quận Calvert, Maryland, Hoa Kỳ. Ông tốt nghiệp trường McDonogh năm 1878 và trường cao đẳng Johns Hopkins rồi làm thầy giáo và người vẽ đồ án trước khi trở thành kĩ sư cơ khí. Năm 1887 ông cùng Frederick W. Taylor quản lý công ty thép Midvale và công ty thép Bethlehem cho đến năm 1893. Sau này, khi làm cố vấn dự án, ngoài sơ đồ Gantt, ông còn thiết kế hệ thống thưởng năng suất - trong đó nhân viên có năng suất vượt định mức sẽ được thưởng phần trăm. Ngoài ra, ông còn phát triển một số phương pháp đo đạc hiệu suất và năng suất nhân viên.

Đóng góp
Henry Gantt đã có nhiều đóng góp cho môn khoa học quản lý, đáng nói nhất bao gồm:
* Sơ đồ Gantt: Đến ngày nay, sơ đồ Gantt vẫn được coi là một công cụ quản lý quan trọng. Sơ đồ Gantt biểu thị thời gian biểu của dự án dùng để quản lý, lên kế hoạch và kiểm soát tiến độ công việc trong dự án. PERT (Program Evaluation and Review Technique - Phương pháp ước lượng và xem xét chương trình) là một biến thể của sơ đồ Gantt.
* Hiệu suất công nghiệp: Hiệu suất công nghiệp có thể được nâng cao bằng cách phân tích một cách khoa học mọi khía cạnh của công việc. Công tác quản lý công nghiệp là cải tiến hiệu suất bằng cách hạn chế tối đa rủi ro.
* Hệ thống thưởng năng suất: Henry Gantt thưởng phần trăm quản lý viên tương ứng với năng suất vượt định mức nhân viên dưới quyền họ đạt được.
* Trách nhiệm xã hội của doanh nghiệp: Henry Gantt tin rằng doanh nghiệp phải có trách nhiệm với xã hội.

o Giải thuật MQS (điều phối hàng chờ nhiều mức)
 Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau.
 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 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.
o Giải thuật MFQS ( điều phối hàng chờ nhiều mức có điều tiết)
 Như MQS nhưng cho phép Điều tiết tiến trình sang mức khác.
 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ụ:
Phòng bán vé tàu ở ga Hòa Hưng có 5 của bán vé, và các người mua vé được xếp vào 5 cửa để chờ mua vé.
- Cửa số 1 : dành cho những người hệ thống, làm việc ở ga, gia đình thân nhân của những người làm ở ga.
- Cửa số 2 : dành cho những người thương binh, mất sức lao động, bà mẹ VN anh hùng.
- Cửa số 3 : dành cho những người bình thường và khách vãng lai.
- Cửa số 4 : dành cho những người ưu tiên ở mức độ thấp hơn.
- Cửa số 5 : dành cho học sinh, sinh viên.
Nhiều cửa bán vé ở trên có độ ưu tiên khác nhau, trong đó chỉ có 1 cô bán vé (1 CPU) phải luân chuyển giữa các cửa để phục vụ đủ loại người mua (các tiến trình) bao gồm nhiều mức độ ưu tiên khác nhau như: người hệ thống (gia đình thân nhân của người làm việc tại ga), thương binh – mẹ VN anh hùng – người mất sức lao động, khách vãng lai…
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.

.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( do 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 tiếm quyền và điều phối không 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.
• 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, 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.

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

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

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

II.1. Giới thiệu

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Thuật toán điều phối cần xem xét và quyết định thời điểm chuyển đổi CPU giữa các tiến trình. Hệ điều hành có thể thực hiện cơ chế điều phối theo nguyên lý độc quyền hoặc không độc quyền.

Điều phối độc quyền : Nguyên lý điều phối độc quyền cho phép một tiến trình khi nhận được CPU sẽ có quyền độc chiếm CPU đến khi hoàn tất xử lý hoặc tự nguyện giải phóng CPU. Khi đó quyết định điều phối CPU sẽ xảy ra trong các tình huống sau:

Khi tiến trình chuyển từ trạng thái đang xử lý(running) sang trạng thái bị khóa blocked ( ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc…).

Khi tiến trình kết thúc.

Các giải thuật độc quyền thường đơn giản và dễ cài đặt. Tuy nhiên chúng thường không thích hợp với các hệ thống tổng quát nhiều người dùng, vì nếu cho phép một tiến trình có quyền xử lý bao lâu tùy ý, có nghĩa là tiến trình này có thể giữ CPU một thời gian không xác định, có thể ngăn cản những tiến trình còn lại trong hệ thống có một cơ hội để xử lý.

Điều phối không độc quyền : Ngược với nguyên lý độc quyền, điều phối theo nguyên lý không độc quyền cho phép tạm dừng hoạt động của một tiến trình đang sẵn sàng xử lý. Khi một tiến trình nhận được CPU, nó vẫn được sử dụng CPU đến khi hoàn tất hoặc tự nguyện giải phóng CPU, nhưng một tiến trình khác có độ ưu tiên có thể dành quyền sử dụng CPU của tiến trình ban đầu. Như vậy là tiến trình có thể bị tạm dừng hoạt động bất cứ lúc nào mà không được báo trước, để tiến trình khác xử lý. Các quyết định điều phối xảy ra khi :

Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng thái bị khóa blocked ( ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc…).

Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng thái ready ( ví dụ xảy ra một ngắt).

Khi tiến trình chuyển từ trạng thái chờ (blocked) sang trạng thái ready ( ví dụ một thao tác nhập/xuất hoàn tất).

Khi tiến trình kết thúc.

Các thuật toán điều phối theo nguyên tắc không độc quyền ngăn cản được tình trạng một tiến trình độc chiếm CPU, nhưng việc tạm dừng một tiến trình có thể dẫn đến các mâu thuẫn trong truy xuất, đòi hỏi phải sử dụng một phương pháp đồng bộ hóa thích hợp để giải quyết.

Trong các hệ thống sử dụng nguyên lý điều phối độc quyền có thể xảy ra tình trạng các tác vụ cần thời gian xử lý ngắn phải chờ tác vụ xử lý với thời gian rất dài hoàn tất! Nguyên lý điều phối độc quyền thường chỉ thích hợp với các hệ xử lý theo lô.

Đối với các hệ thống tương tác(time sharing), các hệ thời gian thực (real time),cần phải sử dụng nguyên lý điều phối không độc quyền để các tiến trình quan trọng có cơ hội hồi đáp kịp thời. Tuy nhiên thực hiện điều phối theo nguyên lý không độc quyền đòi hỏi những cơ chế phức tạp trong việc phân định độ ưu tiên, và phát sinh thêm chi phí khi chuyển đổi CPU qua lại giữa các tiến trình.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- Khác nhau: Multilevel Feedback Queue Scheduling cho phép điều chuyển (điều tiết) tiến trình từ hàng chờ này sang hàng chờ kia (hạ cấp độ hay nâng cấp độ ưu tiên), nghĩa là mềm dẻo hơn Multilevel Queue Scheduling.

- Ví dụ minh hoạ: Phòng bán vé tàu hoả ga Hòa Hưng có 5 cửa bán vé, và các người mua vé được xếp vào 5 cửa để chờ mua vé.
- Cửa số 1: dành cho những người system
- Cửa số 2: dành cho những người thương binh - mất sức lao động.
- Cửa số 3: dành cho những người bình thường.
- Cửa số 4: dành cho những người ưu tiên ở mức độ thấp hơn.
- và Cửa số 5: dành cho sinh viên - học sinh.

có thể có nhiều cửa bán vé với mức ưu tiên khác nhau, trong khi chỉ có 1 người bán vé (1 CPU) phải luân chuyển giữa các cửa để phục vụ đủ loại người mua vé (các tiến trình) như người system (là người nhà họ hàng của ga Hòa Hưng), người mua bình thường, người mua là thương binh, nguời mất sức lao động,...(chỉ có 1 cô bán vé phải chạy đi chạy lại giữa 5 cửa)

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ý tiếm quyền hoặc không tiếm quyền.

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

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

*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 Hòa Hưng 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.

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

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ý tiếm quyền hoặc không tiếm quyền.

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