Hệ thống câu hỏi chương 6

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 có tiếm(chiếm) quyến (Preemtive) với trình điều phối không tiếm quyền (Non - Preemtive)
câu 2: Trình bày giải thuật điều phối ngắn hơn chạy trước (SJFS) (có tiếm quyền)
câu 3: Trình bày giải giải thuật điều phối vòng Robin (RR)
câu 4: Phân biệt thuật giải MQS - MFQS và cho ví dụ minh họa
Mọi người cùng nghiên cứu và trả lời

Phân biệt thuật giải Multilevel Queue Scheduling với Multilevel Feedback Queue Scheduling. Cho các ví dụ minh hoạ:

- 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ả 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 mua bình thường, người mua là thương binh, nguời mất sức lao động,...

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

- 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

Dùng giải thuật Round - Robin với thời lượng 10ms để đ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

Giải
BIỂU ĐỒ GANTT:
- Điểm lưu ý khi vẽ:
+ Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum) là số q ms nào đó.
+ Hết thời gian q, thì tiến trình hiện tại sẽ bị tiến trình khác tiếm quyền nếu tiến trình mới này có thời điểm đến = hoặc < thời điểm đang xét. Đồng thời tiến trình cũ sẽ được đưa vào hàng đợi Ready
+ Tiến trình đầu tiên trong hàng đợi sẽ được chọn để tiếm quyền kế tiếp
- Vẽ biểu đồ:

- Giải thích:
(lưu ý với thuật toán này mình nhớ xem xét thời điểm đề cho là thời điểm đến của các tiến trình)
Theo đề bài này thì CPU bắt đầu cấp phát cho 3 tiến trình P1, P2, P3 là thời điểm 3 và hàng đợi Ready là P1 P2 P3
+ Tại thời điểm 3, P1 đứng đầu hàng đợi Ready, như vậy P1 được chọn cho vận hành
+ Vì q=10ms nên tại thời điểm 13, P1 tạm dừng vận hành và bị đẩy về cuối hành đợi Ready P2 P3 P1.
Như vậy P2 lúc này đứng đầu hàng đợi và xét lại thì thấy thời điểm đến của P2 là 10 < 13, nên P2 được phép tiếm quyền kế tiếp để vận hành
+ Vì q=10ms nên đến thời điềm 23, P2 phải tạm dừng cho tiến trình khác vận hành và P2 bị đẩy về cuối hàng đợi P3 P1 P2.
Lúc này ta thấy P3 đứng đầu hàng đợi nhưng thời điểm đến của P3 là 24 > 23 (là thời điểm đang xét) nghĩa là tại thời điểm này P3 chưa có nhu cầu để vận hành, nên P3 sẽ hok tiếm quyền P2. P3 sẽ bị đẩy về cuối hàng đợi. Hàng đợi lúc này là P1 P2 P3. Do P1 được đẩy lên đầu nên P1 được phép tiếm quyền kế tiếp tại thời điểm 23 này.
+ Cứ sau 10ms, ta lại xét để cho vận hành tiến trình kế tiếp là tiến trình nào.
Tại thời điểm 33, P1 tạm dừng và bị đẩy về cuối hàng đợi Ready P2 P3 P1 P2 đứng đầu hàng đợi sẽ lên tiếm quyền kế tiếp.
+ Tại thời điểm 43, sau khi P2 vận hành 10ms thì lúc này P2 cũng vừa vận hành xong. Vì vậy P2 sẽ không nằm trong hàng đợi Ready. Ta có hàng đợi là P3 P1 Ta thấy lúc này P3 mới bắt đầu vận hành vì nó đã có nhu cầu vận hành từ lúc thời điểm 24
+ Thời điểm 53, P3 tạm dừng và đưa vào cuối hàng đợi P1 P3.
Đồng thời P1 sẽ được ưu tiên lên tiếm quyền tiếp tục vận hành
+Thời điểm 63, P1 tạm dừng, P3 lên tiếm quyền và nó chỉ cần thêm 4ms nữa là P3 vận hành xong tiến trình của nó. Lúc này nó cũng hok còn nằm trong hàng đợi. Hàng đợi chỉ còn có P1
+ Do đó tại thời điểm 67, P1 được vận hành và nó vận hành hết 7ms nữa là thời gian còn lại cần cho P1
Dựa vào biểu đồ Gantt ta tính thời gian chờ trung bình

THỜI GIAN CHỜ TRUNG BÌNH
Ttb = (T1 + T2 +...+ Tn)/n
(thời gian chờ của mỗi tiến trình = tổng thời gian tiến trình đó bị gián đoạn)

T1 = (23 - 13) + (53 - 33) + (67 - 63) = 34
T2 = (13 -10) + (33- 23) = 13
T3 = (43- 24) + (63 - 53) = 29

===> Ttb = (34 + 13 + 29) / 3 = 25.33 ms

Mấy bạn xem rồi góp í heng

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

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.

Năm tiêu chí điều phối CPU :
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.

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

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

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.

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

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 , tương đương Độ ư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 )

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.

BuiThiLanChi (102C) đã viết:

Dùng giải thuật Round - Robin với thời lượng 10ms để đ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

Giải
BIỂU ĐỒ GANTT:
- Điểm lưu ý khi vẽ:
+ Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum) là số q ms nào đó.
+ Hết thời gian q, thì tiến trình hiện tại sẽ bị tiến trình khác tiếm quyền nếu tiến trình mới này có thời điểm đến = hoặc < thời điểm đang xét. Đồng thời tiến trình cũ sẽ được đưa vào hàng đợi Ready
+ Tiến trình đầu tiên trong hàng đợi sẽ được chọn để tiếm quyền kế tiếp
- Vẽ biểu đồ:

- Giải thích:
(lưu ý với thuật toán này mình nhớ xem xét thời điểm đề cho là thời điểm đến của các tiến trình)
Theo đề bài này thì CPU bắt đầu cấp phát cho 3 tiến trình P1, P2, P3 là thời điểm 3 và hàng đợi Ready là P1 P2 P3
+ Tại thời điểm 3, P1 đứng đầu hàng đợi Ready, như vậy P1 được chọn cho vận hành
+ Vì q=10ms nên tại thời điểm 13, P1 tạm dừng vận hành và bị đẩy về cuối hành đợi Ready P2 P3 P1.
Như vậy P2 lúc này đứng đầu hàng đợi và xét lại thì thấy thời điểm đến của P2 là 10 < 13, nên P2 được phép tiếm quyền kế tiếp để vận hành
+ Vì q=10ms nên đến thời điềm 23, P2 phải tạm dừng cho tiến trình khác vận hành và P2 bị đẩy về cuối hàng đợi P3 P1 P2.
Lúc này ta thấy P3 đứng đầu hàng đợi nhưng thời điểm đến của P3 là 24 > 23 (là thời điểm đang xét) nghĩa là tại thời điểm này P3 chưa có nhu cầu để vận hành, nên P3 sẽ hok tiếm quyền P2. P3 sẽ bị đẩy về cuối hàng đợi. Hàng đợi lúc này là P1 P2 P3. Do P1 được đẩy lên đầu nên P1 được phép tiếm quyền kế tiếp tại thời điểm 23 này.
+ Cứ sau 10ms, ta lại xét để cho vận hành tiến trình kế tiếp là tiến trình nào.
Tại thời điểm 33, P1 tạm dừng và bị đẩy về cuối hàng đợi Ready P2 P3 P1 P2 đứng đầu hàng đợi sẽ lên tiếm quyền kế tiếp.
+ Tại thời điểm 43, sau khi P2 vận hành 10ms thì lúc này P2 cũng vừa vận hành xong. Vì vậy P2 sẽ không nằm trong hàng đợi Ready. Ta có hàng đợi là P3 P1 Ta thấy lúc này P3 mới bắt đầu vận hành vì nó đã có nhu cầu vận hành từ lúc thời điểm 24
+ Thời điểm 53, P3 tạm dừng và đưa vào cuối hàng đợi P1 P3.
Đồng thời P1 sẽ được ưu tiên lên tiếm quyền tiếp tục vận hành
+Thời điểm 63, P1 tạm dừng, P3 lên tiếm quyền và nó chỉ cần thêm 4ms nữa là P3 vận hành xong tiến trình của nó. Lúc này nó cũng hok còn nằm trong hàng đợi. Hàng đợi chỉ còn có P1
+ Do đó tại thời điểm 67, P1 được vận hành và nó vận hành hết 7ms nữa là thời gian còn lại cần cho P1
Dựa vào biểu đồ Gantt ta tính thời gian chờ trung bình

THỜI GIAN CHỜ TRUNG BÌNH
Ttb = (T1 + T2 +...+ Tn)/n
(thời gian chờ của mỗi tiến trình = tổng thời gian tiến trình đó bị gián đoạn)

T1 = (23 - 13) + (53 - 33) + (67 - 63) = 34
T2 = (13 -10) + (33- 23) = 13
T3 = (43- 24) + (63 - 53) = 29

===> Ttb = (34 + 13 + 29) / 3 = 25.33 ms

Mấy bạn xem rồi góp í heng

Mong thầy xem lại giúp tụi em bài này . Mình thấy hình như có vấn đề

mình đi làm hoài không có thời gian xem bài nhưng đọc bài các bạn chia sẽ mình đã hiểu thêm tí.cảm ơn các bạn đã post bài lên nha!
chúc các bạn học tốt.