Thảo luận Bài 6

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.

Mô hình là một hệ thống có 3 mức độ ưu tiên từ cao xuống thấp(linux) (ngược lại trong windows), bắt đầu từ tiến trình có độ ưu tiên 0, nếu tiến trình thực hiện xong việc thì sẽ thoát ra khỏi chương trình, nếu chưa xong việc thì sẽ điều chỉnh xuống mức thấp hơn, ở mức cuối cùng thì sẽ được thực hiện dựa vào thuật giải điều phối (FCFS) tiến trình nào đến trước thì sẽ được thực hiện trước.

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

- 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 Hòa Hưng có 2 ô cửa bán vé, những người mua vé xếp hàng vào 2 cửa. cửa 1 là cho những người ưu tiên, cửa 2 là những người bình thường ,chỉ có 1 cô nhân viên bán vé thô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 đó.
MFQS: có điều phối mềm dẻo nếu có sự ưu tiên, đẩy khách hàng từ cửa này sang cửa kia, giúp cho việc bán vé nhanh hơn

TruongThiThuy(113A) đã viết:

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ạn ơi abn5 sao bài này bạn không cho thời gian chờ.Đối với bài giải RRS phải có thời gian chờ mà

Chào bạn,
Đối với bài tập RRS nếu trong đề bài không có thời gian chờ thì ta tự cho thời gian chờ để tính.
Trong bài tập này bạn HaHoangCongTien80 (113A) đang cho thời gian chờ là 10ms đó bạn.
Trong chủ đề Thảo luận Bài 6: RRS mình thấy các ban thảo luận trên đó cũng nhiều lắm đó, bạn vào đó tham khảo xem .

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.

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

Robin: dải ruy băng; Round: vòng tròn ---> cách thức của giải thuật này được ví như một dải ruy băng xoay vòng. Trên dải ruy băng có ghi tên các tiến trình. Nhưng không biết tiến trình nào vào trước, vào sau, chạy trước, chạy sau. Chúng không có thứ tự đầu, cuối hay giữa danh sách. Chỉ biết mỗi tiến trình được cấp một thời lượng CPU (time quantum) như nhau. Sau khoảng thời gian này, nó bị tiếm quyền và phải nhường CPU cho tiến trình khác.
Ví dụ vui: Thời phong kiến có một nhóm các nông dân gởi đơn khiếu nại lên quan về vấn đề nộp thuế ruộng quá nặng. Các người nông dân này, ai cũng sợ phải đứng đầu danh sách kiến nghị lên quan. Họ sợ quan cho rằng kẻ đứng đầu danh sách là kẻ chủ mưu, xách động dân chúng, rồi từ đó bị quan trả thù. Nên họ đã nghĩ ra một cách là làm một "dải ruy băng xoay vòng" rồi ghi tất cả tên nông dân lên đó. Khi làm như vậy thì quan đọc tên nhưng không thể biết ai là người dứng đầu danh sách, vì bản chất của dải ruy băng xoay vòng là không có điểm đầu, điểm cuối.

NguyenVanNgoc65 (113A) đã viết:

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?

Cám ơn bạn!

NguyenVanLam(I13A) đã viết:

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.

Cám ơn bạ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

Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:

TT	Thời điểm đến	CPU
P1	5	25
P2	20	15
P3	30	10

- Dùng g/thuật RRS với thời lượng 10ms để điểu phối CPU, vẽ biểu đồ Grant
- TG chờ trung bình.

Giải:

////////	P1	P1	P2	P1	P3	P2
0         5	15	25	35	40	50	55

Qui trình biểu đồ ( so sánh 3 cột lấy giá trị min cho vào biểu đồ)

P1	P2	P3
5(25)	20(15)	30(10)
15(15)	35(5)	50(0)
25(5)	55(0)
40(0)

- TG trung bì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

P = (P1+P2+P3)/3 = 10 + 20 + 10 = 13,33 ms

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.

ngoài RRS ra chúng ta còn thi những giải thuật nào nữa thế các bạn

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

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

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

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.

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ám ơn bạn!

- 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 tiến trình được thực thi, do đó cần phải giải quyết vấn đề phân chia lựa chọn tiến trình thực thi sao cho có hiệu quả nhất

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.

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


NguyenThiThuThuy (113A)

Tổng số bài gửi: 14
Join date: 17/07/2012
Age: 24

Xem lý lịch thành viên Gửi tin nhắn

Về Đầu Trang

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)

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.

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.