Thảo luận Bài 6

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

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)

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 đích:
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 đó.

-Đượ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 người nào đến trước phục vụ trước(FCFS)
*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.
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

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.

+ Khái niệm chung
-Mục đích của đa chương là : tận dụng tối đa CPU
-Điều phối CPU là chức năng cơ bản của Hệ Điều Hành
-Trình Điều phối CPU (CPU Scheduler) chọn tiến trình trong Ready Queue để cấp thời gian CPU(chuyển sang trạng thái Running)
- Công việc của tiền trình là một chuỗi các Khoảng CPU và Khoảng I/O xen kẻ nhau.

+ Hệ điều hành phải có chức năng điều phối CPU vì :
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ânchia, 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 là :
1.Công suất CPU (CPU Utilisation): Thực tế đạt từ 40% - 90% thời gian CPU. CPU càng bậncà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 gianI/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 khicó phản hồi đầu tiên.

+ Mục đích của điều phối CPU là :
-Tối đa công suất và thông suất
- Tối thiểu tổng thời gian, thời gian chờ và thời gian đáp ứng

+ Ý kiến tham khảo của một số nhà phân tích :
Trong hệ tương tác : Tối thiểu độ lệch thời gian đáp ứng quan trọng hơn Tối thiểu thời gian đáp ứng trung bình.

HANDLE ProducerHandle[50 ] ;
HANDLE ConsumerHandle[50 ] ;
DWORD ProducerID[ 50]; // cấp ID cho sản phẩm được tạo mới
DWORD ConsumerID[50 ];
// 1. Tạo các luồng
for ( int i = 0 ; i < 50 ; i ++)
{
ProducerHandle[ i ]=CreateThread(Producer, 4, &ProducerID[i]);
ConsumerHandle[ i ]=CreateThread(Consumer, 0, &ConsumerID[i]));
}
// 2. Đánh thức các luồng
for ( int i = 0 ; i <50 ; i ++)
{
ResumeThread ( ProducerHandle[ i ] );
ResumeThread ( ConsumerHandle[ i ] ); // đối với các tập luồng ConsumerHandle[ i ] này sau khi khởi tạo sẽ chạy ngay
}
// 3. Tạm ngừng
for ( int i = 0 ; i < 50 ; i ++)
{
SuspendThread(ProducerHandle[ i ]);
SuspendThread(ConsumerHandle[ i ]);
}

Admin
Đoạn code trên rất thiết thực ! Tuy cần chú ý mấy điểm sau (những chỗ màu đỏ):
1. Lệnh "DWORD ProducerID[50]" dùng khai báo biến mảng chứa ID của các luồng sản xuất chứ không cấp tại đấy !
2. Trong lập trình Windows, hàm CreateThread có cách gọi với danh sách tham số phức tạp hơn (xem lại mã của ứng dụng Sản xuất-Tiêu thụ trong Bài 5 và Bài 7). Gọi như trên sẽ sai ! Nhưng khi làm bài thi, chấp nhận các em dùng phương án đơn giản như vậy, vì không ai thuộc lòng được tất cả chi tiết (và không cần phải thuộc) !
3. Lệnh "ResumeThread(ConsumerHandle[i])" trong chu trình thứ 2 không cần thiết vì tập luồng tiêu thụ đang vận hành nên không cần phải "đánh thức" chúng !

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.

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

VD: Bán vé ở ga tàu lửa.
Có nhiều cổng bán vé dành cho từng loại khách hàng khác nhau. Nhưng chỉ có 1 cô bán vé và cô này linh hoạt chạy qua lại các cổng để bán vé. Nếu cổng nào có quá nhiều khách mau vé dẫn đến quá tải thì khách cũng không được chuyển sang cổng khác để mua vé

Đ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 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
VD: Lấy lại ví dụ Bán vé ở ga tàu lửa ở trên
Có nhiều cổng bán vé dành cho từng loại khách hàng khác nhau. Nhưng chỉ có 1 cô bán vé và cô này linh hoạt chạy qua lại các cổng để bán vé. Tuy nhiên nếu cổng nào có quá nhiều khách mua vé dẫn đến quá tải thì khách vẫn có thể được điều tiết qua cổng khác để mua vé