Thảo luận Bài 6

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

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

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 do vay nen can co chiến lược định thờ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ố tiến trình (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.

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

1. Trình bày thuật giải điều phối FCFS.
Đến trước - Phục vụ trước (First-Come, First-Served Scheduling - FCFS)
- Đơn giản, dễ thực hiện.
- Các tiến trình trong Ready Queue được cấp CPU từ đầu dãy đến cuối dãy theo quy tắc FIFO (First-In, First-Out).
- Thời gian chờ trung bình khá lớn. (Vd: nộp bài kiểm tra cho Thầy: thì lần lượt nhóm từng 5 người lên theo thứ tự trên bảng -> 5 tiếp người tiếp theo sẽ chờ trong khoảng thời gian hơi lâu)
* Quy tắc FIFO (First-In, First-Out):
- Nguyên tắc :
+ Processor được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu, là tiến trình được đưa vào hệ thống sớm nhất.
+ FIFO được sử dụng trong điều phối độc quyền nên khi tiến trình được cấp processor nó sẽ sở hữu processor cho đến khi kết thúc xử lý hay phải đợi một thao tác vào/ra hoàn thành, khi đó tiến trình chủ động trả lại processor cho hệ thống.
VD: Việc phục vụ khách trong nhà hàng. Thực khách sẽ đến và gọi món ăn cho mình. Mỗi món ăn cần thời gian chuẩn bị khác nhau

2. Trình bày thuật giải điều phối PS.
- Mỗi tiến trình được cấp một số nguyên (Priority Number) dùng để ấn định Độ ưu tiên.
- CPU luôn dành cho tiến trình với độ ưu tiên cao hơn (Priority Number nhỏ hơn  Độ ưu tiên cao hơn ) với 2 phương án:
Có tiếm quyền ( Preemptive )
Không tiếm quyền ( Non-Preemptive )
- SJFS là trường hợp đặc biệt của PS với độ ưu tiên:
P= ( Khoảng CPU kế tiếp )

3. Trình bày thuật giải điều phối SJFS.
Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)
- Đúng hơn phải được gọi là Shortest-Next-CPU-Burst, nghĩa là tiến trình có Khoảng CPU kế tiếp nhỏ hơn thì được chạy trước. Trong trường hợp bằng nhau, dùng thuật giải FCFS.
- Là giải thuật khá tối ưu, nhưng phải biết cách ước đoán khoảng CPU kế tiếp.
- SJFS không tiếm quyền (Non-Preemptive SJFS): Tiến trình hiện thời được thực hiện đến hết khoảng CPU của nó.
- SJFS có tiếm quyền (Preemptive SJFS): Tiến trình mới có Next CPU Burst nhỏ hơn khoảng thời gian CPU còn lại của tiến trình đang vận hành sẽ được chọn thay thế (Shortest Remaining First).

4. Trình bày thuật giải điều phối RRS.
- Như điều phối kiểu FCFS nhưng cho phép tiếm quyền khi tiến trình đang chạy bị hết thời lượng.
- Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum), thường từ 10-100 mili giây. Sau khoảng thời gian này, nó bị tiếm quyền và được đưa vào cuối hàng chờ Ready. Tiến trình đầu tiên trong hàng chờ Ready được chọn kế tiếp.
- Nếu có n tiến trình và thời lượng là q , mỗi tiến trình nhận 1/n thời gian CPU bao gồm các đoạn không quá q đơn vị thời gian.

5. Trình bày thuật giải điều phối MQS.
- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau, ví dụ: Mức các tiến trình tương tác (Interactive) chạy ở mặt trước ( Foreground ) có độ ưu tiên cao nhất và Mức các tiến trình lô ( Batch ) vận hành trong hậu trường (Background ) .
- Mỗi hàng chờ có thuật giải điều phối riêng, ví dụ: Foreground dùng RRS, Background dùng FCFS.
- Quan hệ giữa các mức:
Ưu tiên cố định: Xong hết các tiến trình mức trên rồi mới chuyển xuống mức dưới. Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mới mức cao hơn, tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình mới có độ ưu tiên cao hơn ( Hệ Solaris 2 dùng cách này ) .
Phân bổ theo tỉ lệ thời lượng: ví dụ: 80% thời lượng CPU dành cho Foreground, 20 % cho Background.

6. Trình bày thuật giải điều phối MFQS.
- Như MQS nhưng cho phép Điều tiết tiến trình sang mức khác, ví dụ: những tiến trình hướng CPU được đưa xuống mức dưới, trong khi tiến trình hướng I/O hoặc chờ lâu được chuyển lên trên.
- MFQS đặc trưng bởi các thông số:
+ Số mức (số hàng chờ)
+ Thuật giải điều phối cho mỗi mức
+ Phương thức nâng cấp tiến trình
+ Phương thức hạ cấp tiến trình
+ Phương thức chọn hàng chờ (chọn mức) cho tiến trình mới

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

Ví dụ: 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 nhà ga có 3 cửa bán vé, những người mua vé xếp hàng vào 3 cửa. Có 3 loại khách hàng với 3 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.

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 đó. không có sự chia độ ưu tiên

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.

Chú ý nguyên tắc chung: Độ ưu tiên hạ từ trên xuống, không co sự ưu tiên từ mức dưới đi ngược lên trên


Admin
Không phải vậy ! Nói chung, vừa có thể Hạ cấp và Nâng cấp tiến trình ! (tuỳ từng hệ thống cụ thể)

LuongHueChanh_I12A đã viết:
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 do vay nen can co chiến lược định thời CPU.

Mình xin bổ sung thêm:

* Ý tưởng của hệ thống đa chương
- Tại một thời điểm trong bộ nhớ có nhiều process
- Mỗi thời điểm chỉ có 1 process được thực thi
- Một process được thực thi cho đến khi yêu cầu I/O hoàn thành=> lúc chờ I/O CPU sẽ rảnh
- Cố gắng tận dụng thời gian rảnh của CPU để phục vụ process khác
- 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. => Cần có chiến lược định thời CPU

*Phân loại các hoạt động định thời



- Định thời dài hạn (long-term): process nào được chấp nhận vào hệ thống. Còn gọi là Job scheduling.
- Định thời trung hạn (medium-term): process nào được đưa vào (swap in), đưa ra (swap out) khỏi bộ nhớ chính.
- Định thời ngắn hạn (short-term): process nào được thực thi tiếp theo.

* Định thời trên hệ thống có một processor (uniprocessor scheduling): HĐH sẽ quyết định việc sử dụng CPU cho process nào trong 1 loạt các process trong hệ thống
Vậy phải định thời theo tiêu chuẩn nào ?

- Sự tận dụng CPU (CPU utilization)
+ Khoảng thời gian CPU bận
+ Cần giữ cho CPU càng bận càng tốt

- Thông lượng (throughput)
+ Số lượng process hoàn thành trong một đơn vị thời gian

- Thời gian chờ (waiting time)
+ Thời gian chờ trong hàng đợi ready
+ Các process nên được chia sẻ việc sử dụng CPU một cách công bằng (fair share)

- Thời gian đáp ứng (response time)
+ Thời gian từ lúc có yêu cầu của người dùng (user request) đến khi có đáp ứng đầu tiên (lưu ý: đáp ứng đầu tiên)
+ Thường là vấn đề với các I/O-bound process

- Thời gian hoàn thành (turnaround time)
+ Thời gian để hoàn thành một process (kể từ lúc nạp vào hệ thống – submission đến lúc kết thúc – termination)
+ Là tổng thời gian chờ đưa vào bộ nhớ+chờ ở ready queue+thực thi CPU+thực hiện I/O

* Tối ưu tiêu chuẩn định thời:
- Hướng đến người sử dụng (user-oriented)
+ Tối thiểu thời gian hoàn thành(turnaround time): Thời gian từ lúc nạp process đến lúc process kết thúc. Cần quan tâm với các hệ thống xử lý bó (batch system).
+ Tối thiểu thời gian đáp ứng (response time): Cần quan tâm với các hệ thống giao tiếp (interactive system).

- Hướng đến hệ thống (system-oriented)
+ Tối đa sự tận dụng CPU (CPU utilization): Định thời sao cho CPU càng bận càng tốt.
+ Fairness: Các process có thời gian chờ đợi công bằng trong ready queue.
+ Tối đa throughput: Số process hoàn thành trong một đơn vị thời gian=>cực đại.

* Điều phối hàng chờ nhiều mức (Multilevel Queue Scheduling - MQS)
- Hàng chờ Ready được phân cấp thành nhiều mức có độ ưu tiên khác nhau. VD:Mức các tiến trình tương tác chạy ở mặt trước có độ ưu tiên cao nhất và mức các tiến trình lô(batch) vận hành trong hậu trường.
- Mỗi hàng chờ có thuật giải để điều phối riêng.
- Quan hệ giữa các mức:
+ Ưu tiên cố định:xong hết các tiến trình mức trên rồi chuyển xuống mức dưới.Đang chạy tiến trình mức dưới mà xuất hiện tiến trình mức cao hơn,tiến trình mức dưới sẽ bị tiếm quyền do tiến trình mới có độ ưu tiên cao hơn.
+ Phân bổ theo tỉ lệ thời lượng.

* Điều phối hàng chờ nhiều mức có điều tiết (Multilevel Feedback Queue Scheduling - MFQS)
- Như MSQ nhưng cho phép điều tiết tiến trình sang mức khác. VD:Những tiến trình hướng CPU được đưa xuống mức dưới.
- MFQS đặc trưng bởi các thông số:
+ Số mức (số hàng chờ)
+ Thuật giải điều phối cho mỗi mức.
+ Phương thức nâng cấp tiến trình.
+ Phương thức hạ cấp tiến trình.
+ Phương thức chọn hàng chờ (chọn mức) cho tiến trình mới.
ví dụ: trong lớp học thì bàn 1 được ưu tiên. Khi cần gọi lên để làm bài ( nếu làm không được ) thì thầy sẽ chuyển sang bàn thứ 2 để gọi lên.


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

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

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

Ví dụ: Trong ga 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.
+ 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.

BAI 6: THAO LUAN BAI 6
huynhthao.hc11th2a Today at 11:19

I. Điều phối tiến trình (CPU Scheduler).

1. Giới thiệu.

HDH đơn chương
HDH đa chương
Cấp phát CPU cho tiến trình
Bảo vệ hoạt động của các tiến trình
Cấp phát TN
Thu hồi CPU và TN
Thông tin giữa các tiến trình
Tổ chức điều phối của HDH→2 modules : điều phối và phân phối

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

Các danh sách sử dụng trong điều phối

Ready list : các TT đợi cấp phát CPU.
Waiting list : các TT Blocked
DS tiến trình đợi cấp phát tài nguyên

Các cấp độ điều phối
Phân loại TT
TT hướng I/O : thời gian hoạt động chủ yếu là I/O.
TT hướng xử lý : thời gian hoạt động chủ yếu là xử lý.
Điều phối tác vụ : chọn tác vụ (nhiều tiến trình).
Điều phối TT : chọn TT (*).
Điều phối trung gian : chọn tác vụ + chọn TT.
3. CT điều phối (Scheduler) và phân phối (Dispatcher)
CT điều phối
Chức năng
Tạo và quản lý các DS điều phối
Đưa ra các quyết định điều phối (chuyển trạng thái TT)
QĐ cấp phát và thu hồi TN
Đáp ứng các yêu cầu của HT
...
ĐK kích hoạt
Tạo, chuyển trạng thái và kết thúc TT
TT yêu cầu TN
Giải phóng TN
Yêu cầu của HT
CT phân phối
Chức năng
Chuyển ngữ cảnh
Thu hồi và cấp CPU cho TT
...
ĐK kích hoạt
TT chuyển trạng thái
...
4. Chiến lược điều phối TT – thuật toán lập lịch – giải thuật điều phối.
Mục đích
Sử dụng tối đa công suất CPU
Đáp ứng tối đa các tác vụ trong 1 đơn vị thời gian
Tối thiểu thời gian đợi của TT
Tối thiểu thời gian đáp yêu cầu của TT
Đánh giá
Thời gian chờ của TT(*)
Thời gian hoạt động của TT
Hiệu suất sử dụng CPU
...

Ngắn hơn-Chạy trước (Shortest-Job-First Scheduling-SJFS)
* SJFS không tiếm quyền (Non-Preemptive SJFS): Tiến trình hiện thời được thực hiện đến hết khoảng CPU của nó. (Có nghĩa là ko được ngắt CPU khi 1 tiến trình đang chạy).

Ví dụ: Ở lớp I12A, bình thường 18h vô lớp thì ai đến sớm thì có quyền ngồi chỗ tốt mà mình chọn ( thông thường bạn nào cận thì thường đi sớm để được ngồi bàn 1)
ví dụ 2: Thầy chọn 5 bạn để giải bài tập thì bạn nào lên trước thì được ưu tiên làm trước, và khi nào bạn 1 làm xong thì bạn thứ 2 mới được làm.


* SJFS có tiếm quyền (Preemptive SJFS): Tiến trình mới có Next CPU Burst nhỏ hơn khoảng thời CPU còn lại của tiến trình đang vận hành sẽ được chọn thay thế (Shortest - Remaining - First).

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

Bạn nào có ví dụ nào hay hay post lên cho bạn bè tham khảo nha ! thanks

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

Sơ đồ Gantt là một trong những công cụ cổ điển nhất mà vẫn được sử dụng phổ biến trong quản lý tiến độ thực hiện dự án. Sơ đồ này được xây dựng vào năm 1915 bởi Henry L. Gantt, một trong những nhà tiên phong về lĩnh vực quản lý khoa học.

Trong sơ đồ Gantt, các công tác được biểu diễn trên trục tung bằng thanh ngang, thời gian tương ứng được thể hiện trên trục hoành.

Mình xin giới thiệu 1 phần mềm vẽ biểu đồ Gantt, bản thân mình cũng chưa sử dụng nhưng xin post lên đây cho bạn nào thích tìm tòi học hỏi.

Mindjet MindManager Pro 9.1.157

Mindjet MindManager Pro biến những ý tưởng động não, tư duy chiến lược, và thông tin kinh doanh vào bản thiết kế cho hành động, cho phép các đội, tổ chức để làm việc nhanh hơn, thông minh hơn, và có sự phối hợp lớn hơn.

MindManager thông tin hình ảnh của bản đồ (bản đồ tâm trí) bắt đầu với một chủ đề trung tâm, và sau đó thêm các chi nhánh với những ý tưởng, ghi chú, hình ảnh, nhiệm vụ, siêu liên kết và tập tin đính kèm. Dễ dàng nhập khẩu từ hoặc xuất khẩu cho Microsoft Office. Sử dụng bản đồ MindManager để nắm bắt và tổ chức thông tin, và bạn sẽ nhanh chóng chuyển đổi suy nghĩ và ý tưởng của bạn vào các văn bản điều chỉnh, thuyết trình hấp dẫn và chiến lược chiến thắng. MindManager mang đến cho bạn một cách tốt hơn để động não, tổ chức sự kiện, dự án kế hoạch, và giao tiếp kết quả.

Tính năng

Thông tin hàng đầu Visualizations

Dễ dàng đặt ra, tổ chức và làm việc với những ý tưởng và thông tin trong một loạt các định dạng tương tác trực quan bao gồm các bản đồ thông tin, phác thảo, biểu đồ Gantt, biểu đồ tổ chức, sơ đồ cây và một chế độ động não đặc biệt.

Dự án & Quản lý công tác

Cải thiện dự án quy hoạch do động não và theo dõi chi tiết công việc, tự động tính toán nhiệm vụ tổng kết và tối ưu hóa sử dụng tài nguyên. Xem MindManager, Outlook, nhiệm vụ * SharePoint trong khung nhìn Gantt mới đồng bộ, nhiệm vụ xuất khẩu cho Microsoft Project.

Bản đồ thông tin trình bày

Giới thiệu ý tưởng của bạn và tham gia tăng sử dụng xem trình chiếu tự động MindManager hoặc các trình diễn tùy biến. Với các bài thuyết trình năng động của MindManager, bạn dễ dàng chỉnh mức độ chi tiết trình bày cho mỗi khán giả và sẽ thu hồi quyền quan trọng trong việc trình bày.

Tích hợp và chia sẻ

Tiết kiệm thời gian và hưởng lợi từ việc tích hợp mạnh mẽ. Truy cập và cập nhật Microsoft Office tích hợp các tập tin trong trình duyệt của MindManager. Nhập khẩu từ Microsoft Word và dự án. Xuất khẩu sang dự án, Word hay PowerPoint. Hiển thị năng động Outlook hoặc nội dung Excel. Xuất khẩu các trang web, hình ảnh, tập tin PDF và nhiều hơn nữa. Hoặc, chia sẻ các tập tin được lưu trữ bản đồ tương tác với bất kỳ ai trên web ngay cả khi họ không có MindManager.

Chụp Nội dung & Thêm Bối cảnh

Dễ dàng thêm các siêu liên kết, tập tin đính kèm, ghi chú, hình ảnh, và bảng tính để cung cấp cấp thêm chi tiết. Nhanh chóng kéo và thả nội dung để tổ chức lại nó và cung cấp các cấu trúc. Sử dụng các biểu tượng, thẻ, hình dạng chủ đề, ghi chú, biên giới, màu sắc, chủ đề phân loại và đánh số để cung cấp các bối cảnh khác.




Link Download:
http://www.fshare.vn/file/TQSTHAMSVT/
Mirror: http://www.mediafire.com/?kynmy9duj5p584a
(Nguồn http://www.phimdaily.net)

Trong bộ công cụ Microsoft Office cũng hỗ trợ vẽ biểu đồ Gantt, các bạn có thể tham khảo thêm link dưới, vẽ trên Excel.
http://www.tinhoc365.com/gantt2.html

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

Giả sử một hệ thống có 3 tiến trình với tính chất như sau:
Tiến trình Thời điểm đến (giây thứ) Khoảng CPU (số giây)
P1 0 5
P2 1 2
P3 2 2
Dùng thuật giải FCFS để đ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.

Chào bạn LePhucHiep(102C) bạn ví dụ bài tập và bài giải khá công phu nhưng bạn có thể giải thích rõ hơn được không ,bài giải chưa cụ thể lắm, cám ơn
Chúc bạn học tốt môn hệ điều hành của thầy

Trình bày 4 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ều phối không tiếm quyề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.
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

Các thuật giải căn bản trong điều phối 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.

**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ì thế phả có chức năng điều phối CPU --> 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.

Chào bạn hoanghaiyen mình giải thích bài giải nhé
(FCFS - First come,First Served Scheduling)
Bạn cứ nhớ FCFS đến trước phục vụ trước
Tại thời điểm 0 tiến trình P1 được thực hiện là 5 ms tức là P1 ko chờ nên thời gian chờ của P1 =0(tại thời điểm P1 =0)
Tại thời điểm 1 tiến trình P2 được thực hiện là 2ms nhưng do phải chờ P1 thực hiện xong là 5ms rồi P2 mới thực hiện là 5-1=4 (tại thời điểm P2=1)
Tại thời điểm 2 tiến trình P3 được thực hiện là 2ms nhưng do phải chờ P1 và P2 thực hiện xong là 5+2= 7 ms rồi P3 mới thực hiện là 7-2=5 (tại thời điểm P3=2)
Thời gian chờ là (0 + 4 + 5) =9
Thời gian chờ trung bình của 3 tiến trình là 9 : 3 = 3 m/s
Không biết bạn đã nắm rõ chưa. Mong thầy và các bạn góp ý

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

Phân biệt điều phối có tiếm quyền (Preemtive Scheduling) và không tiếm quyền (Non-Preemtive Scheduling).
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.