Thảo luận Bài 6

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

Mình thắc nắc là biểu đồ Gantt không có P0? Bạn nào biết thì chỉ giúp nhé. Thanks. 

Sơ đồ Gantt đượ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. Đây là một trong những công cụ cổ điển nhất nhưng vẫn được sử dụng phổ biến trong quản lý tiến độ thực hiện dự án (việc thực hiện một đề tài NCKH cũng có thể xem là một dự án). Nó biểu diễn thời gian thực hiện các nhiệm vụ trong dự án, giúp cho các nhà quản lý dự án theo dõi và quản lý công việc chơn chu hơn.

Nhìn vào biểu đồ Gantt, người quản lý dự án, cũng như các thành viên thực hiện dự án biết được:

• Trình tự thực hiện mỗi nhiệm vụ;

• Tiến độ dự án: biết được mình đã làm được gì và tiếp tục phải thực hiện công việc đó thế nào, bởi vì mỗi công việc được giao phải hoàn thành trong thời gian đã định;

• Thấy sự phụ thuộc lẫn nhau giữa các công việc.

Trong sơ đồ Gantt:

• Các công tác được biểu diễn trên trục tung.

• Thời gian tương ứng được thể hiện trên trục hoành – đó là những đoạn thẳng nằm ngang có độ dài nhất định chỉ thời điểm bắt đầu, thời gian thực hiện, thời điểm kết thúc.


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ử[sửa | sửa mã nguồn]
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[sửa | sửa mã nguồn]
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.

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 :
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
Tính hiệu qủa (Efficiency) :

Hệ thống phải tận dụng được CPU 100% thời gian.
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
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ô.
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á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 :
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.
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.
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.
Độ ư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.
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.
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ý.
Đ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.
Tổ chức điều phối
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.
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).
Đ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ý
Đ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

Hình 2.11 Cấp độ điều phối trung gian


Các chiến lược điều phối
Chiến lược FIFO

Nguyên tắc : CPU đượ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. Đây là thuật toán điều phối theo nguyên tắc độc quyền. Một khi CPU được cấp phát cho tiến trình, CPU chỉ được tiến trình tự nguyện giải phóng khi kết thúc xử lý hay khi có một yêu cầu nhập/xuất.

Hình 2.12 Điều phối FIFO

Ví dụ :

Thứ tự cấp phát CPU cho các tiến trình là :

thời gian chờ đợi được xử lý là 0 đối với P1, (24 -1) với P2 và (24+3-2) với P3. Thời gian chờ trung bình là ( 0+23+25)/3 = 16 milisecondes.

Thảo luận : Thời gian chờ trung bình không đạt cực tiểu, và biến đổi đáng kể đối với các giá trị về thời gian yêu cầu xử lý và thứ tự khác nhau của các tiến trình trong danh sách sẵn sàng. Có thể xảy ra hiện tượng tích lũy thời gian chờ, khi các tất cả các tiến trình (có thể có yêu cầu thời gian ngắn) phải chờ đợi một tiến trình có yêu cầu thời gian dài kết thúc xử lý.

Giải thuật này đặc biệt không phù hợp với các hệ phân chia thời gian, trong các hệ này, cần cho phép mỗi tiến trình được cấp phát CPU đều đặn trong từng khoảng thời gian.
Chiến lược phân phối xoay vòng (Round Robin)

Nguyên tắc : Danh sách sẵn sàng được xử lý như một danh sách vòng, bộ điều phối lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là quantum. Đây là một giải thuật điều phối không độc quyền : khi một tiến trình sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp trong danh sách. Nếu tiến trình bị khóa hay kết thúc trước khi sử dụng hết thời gian quantum, hệ điều hành cũng lập tức cấp phát CPU cho tiến trình khác. Khi tiến trình tiêu thụ hết thời gian CPU dành cho nó mà chưa hoàn tất, tiến trình được đưa trở lại vào cuối danh sách sẵn sàng để đợi được cấp CPU trong lượt kế tiếp.

Ví dụ :

Hình 2.13 Điều phối Round Robin

Nếu sử dụng quantum là 4 milisecondes, thứ tự cấp phát CPU sẽ là :

Thời gian chờ đợi trung bình sẽ là (0+6+3+5)/3 = 4.66 milisecondes.

Nếu có n tiến trìh trong danh sách sẵn sàng và sử dụng quantum q, thì mỗi tiến trình sẽ được cấp phát CPU 1/n trong từng khoảng thời gian q. Mỗi tiến trình sẽ không phải đợi quá (n-1)q đơn vị thời gian trước khi nhận được CPU cho lượt kế tiếp.

Thảo luận :

Vấn đề đáng quan tâm đối với giải thuật RR là độ dài của quantum. Nếu thời lượng quantum quá bé sẽ phát sinh quá nhiều sự chuyển đổi giữa các tiến trình và khiến cho việc sử dụng CPU kém hiệu qủa. Nhưng nếu sử dụng quantum quá lớn sẽ làm tăng. Điều phối với độ ưu tiên

Nguyên tắc : Mỗi tiến trình được gán cho một độ ưu tiên tương ứng, tiến trình có độ ưu tiên cao nhất sẽ được chọn để cấp phát CPU đầu tiên. Độ ưu tiên có thể được định nghĩa nội tại hay nhờ vào các yếu tố bên ngoài. Độ ưu tiên nội tại sử dụng các đại lượng có thể đo lường để tính toán độ ưu tiên của tiến trình, ví dụ các giới hạn thời gian, nhu cầu bộ nhớ…Độ ưu tiên cũng có thể được gán từ bên ngoài dựa vào các tiêu chuẩn do hệ điều hành như tầm quan trọng của tiến trình, loại người sử dụng sỡ hữu tiến trình…

Giải thuật điều phối với độ ưu tiên có thể theo nguyên tắc độc quyền hay không độc quyền. Khi một tiến trình được đưa vào danh sách các tiến trình sẵn sàng, độ ưu tiên của nó được so sánh với độ ưu tiên của tiến trình hiện hành đang xử lý. Giải thuật điều phối với độ ưu tiên và không độc quyền sẽ thu hồi CPU từ tiến trình hiện hành để cấp phát cho tiến trình mới nếu độ ưu tiên của tiến trình này cao hơn tiến trình hiện hành. Một giải thuật độc quyền sẽ chỉ đơn giản chèn tiến trình mới vào danh sách sẵn sàng, và tiến trình hiện hành vẫn tiếp tục xử lý hết thời gian dành cho nó.

Ví dụ : (độ ưu tiên 1 > độ ưu tiên 2> độ ưu tiên 3)

Sử dụng thuật giải độc quyền, thứ tự cấp phát CPU như sau :

Sử dụng thuật giải không độc quyền, thứ tự cấp phát CPU như sau :


Thảo luận : Tình trạng ‘đói CPU’ (starvation) là một vấn đề chính yếu của các giải thuật sử dụng độ ưu tiên. Các giải thuật này có thể để các tiến trình có độ ưu tiên thấp chờ đọi CPU vô hạn ! Để ngăn cản các tiến trình có độ ưu tiên cao chiếm dụng CPU vô thời hạn, bộ điều phối sẽ giảm dần độ ưu tiên của các tiến trình này sau mỗi ngắt đồng hồ. Nếu độ ưu tiên của tiến trình này giảm xuống thấp hơn tiến trình có độ ưu tiên cao thứ nhì, sẽ xảy ra sự chuyển đổi quyền sử dụng CPU.Quá trình này gọi là sự ‘lão hóa’ (aging) tiến trình.
Chiến lược công việc ngắn nhất (Shortest-job-first SJF)

Nguyên tắc : Đây là một trường hợp đặc biệt của giải thuật điều phối với độ ưu tiên. Trong giải thuật này, độ ưu tiên p được gán cho mỗi tiến trình là nghịch đảo của thời gian xử lý t mà tiến trình yêu cầu : p = 1/t. Khi CPU được tự do, nó sẽ được cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết thúc- tiến trình ngắn nhất. Giải thuật này cũng có thể độc quyền hay không độc quyền. Sự chọn lựa xảy ra khi có một tiến trình mới được đưa vào danh sách sẵn sàng trong khi một tiến trình khác đang xử lý. Tiến trình mới có thể sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lý. Giải thuật SJF không độc quyền sẽ dừng hoạt động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lý.

Ví dụ :

Sử dụng thuật giải SJF độc quyền, thứ tự cấp phát CPU như sau:

Sử dụng thuật giải SJF không độc quyền, thứ tự cấp phát CPU như sau:


Thảo luận : Giải thuật này cho phép đạt được thời gian chờ trung bình cực tiểu. Khó khăn thực sự của giải thuật SJF là không thể biết được thời gian yêu cầu xử lý còn lại của tiến trình ? Chỉ có thể dự đoán giá trị này theo cách tiếp cận sau : gọi tn là độ dài của thời gian xử lý lần thứ n, τ n+1 là giá trị dự đoán cho lần xử lý tiếp theo. Với hy vọng giá trị dự đoán sẽ gần giống với các giá trị trước đó, có thể sử dụng công thức:

τ n+1 = α tn + (1-α )τ n

Trong công thức này,tn chứa đựng thông tin gần nhất ; τ n chứa đựng các thông tin quá khứ được tích lũy. Tham số α ( 0 ≤ α ≤ 1) kiểm soát trọng số của hiện tại gần hay quá khứ ảnh hưởng đến công thức dự đóan.

Các tình huống ra quyết định của trình điều phối:
1. Khi tiến trình Running sang Waiting.
- Khi tiến trình cần thực hiện nhập xuất thì trình điều phối sẽ tìm kiếm một tiến trình khác để câp CPU. Trong trường hợp này tiến trình tự ngừng sử dụng CPU => điều phối không tiếm quyền.
2. Khi tiến trình chuyển từ Running sang Ready.
- Khi thời gian thực hiện của tiến trình vượt quá thời gian quy định (vì hệ điều hành chia thời gian) thì HĐH sẽ ngừng cấp CPU và đưa tiến trình vào Ready để cấp CPU cho một tiến trình khác. Trường hợp này có sự can thiệp của HĐH để lấy CPU => điều phối có tiếm quyền.
3. Khi tiến trình chuyền từ Waiting sang Ready.
- Sau khi quá trình nhập xuất đã xong, tiến trình lại được đưa vào hàng chờ. Lúc này HĐH sẽ kiểm tra xem có thể tiếp tục đưa tiến trình chờ đó chạy tiếp hay không? Nếu có sẽ cấp CPU cho tiến trình này tiếp tục làm việc. Trường hợp này có sự can thiệp của HĐH => điều phối có tiếm quyền.
4. Khi tiến trình kết thúc công việc.
- Sau khi tiến trình hoàn tất công việc thì tự trả CPU lại cho HĐH, HĐH sẽ tìm một tiến trình thích hợp khác để cấp CPU. Trong trường hợp này tiến trình tự ngừng sử dụng CPU => điều phối không tiếm quyền.

- Điều phối không tiếm quyền là khi tiến trình giữ CPU cho đến khi kết thúc hoặc chuyển sang trạng thái waiting mà không có sự can thiệp thu hồi CPU của HĐH.
- Điều phối có tiếm quyền là khi HĐH can thiệp để thu hồi CPU để cấp cho một tiến trình khác hoạt động.

Với tư cách là một ngành khoa học, quản lý dự án phát triển từ những ứng dụng trong các lĩnh vực khác nhau như xây dựng, kỹ thuật và quốc phòng. Ở Hoa Kỳ, hai ông tổ của quản lý dự án là Henry Gantt, được gọi là cha đẻ của kỹ thuật lập kế hoạch và kiểm soát, người đã cống hiến hiểu biết tuyệt vời của mình bằng việc sử dụng biểu đồ Gantt như là một công cụ quản lý dự án, và Henri Fayol người tìm ra 5 chức năng của quản lý, là cơ sở cho những kiến thức cốt lõi liên quan đến quản lý dự án và quản lý chương trình.

Cả hai ông Gantt và Fayol đều được biết đến như là những học trò, theo trường phái lý thuyết quản lý theo khoa học, của Frederick Winslow Taylor. Thuyết Taylor là nguyên mẫu đầu tiên cho các công cụ quản lý dự án hiện đại, bao gồm cả cấu trúc phân chia công việc (WBS) và phân bổ nguồn lực.

Những năm 1950, đánh dấu sự bắt đầu của kỷ nguyên quản lý dự án hiện đại. Quản lý dự án đã được chính thức công nhận là một ngành khoa học phát sinh từ ngành khoa học quản lý. Một lần nữa, tại Hoa Kỳ, trước những năm 1950, các dự án đã được quản lý trên một nền tảng đặc biệt bằng cách sử dụng chủ yếu là biểu đồ Gantt (Gantt Charts), cùng các kỹ thuật và các công cụ phi chính thức. Tại thời điểm đó, hai mô hình toán học để lập tiến độ của dự án đã được phát triển. "Phương pháp Đường găng" (tiếng Anh là Critical Path Method, viết tắt là CPM) phát triển ở liên doanh giữa công ty Dupont và công ty Remington Rand để quản lý các dự án bảo vệ thực vật và hóa dầu. Và "Kỹ thuật đánh giá và xem xét chương trình (dự án)" (tiếng Anh là Program Evaluation and Review Technique hay viết tắt là PERT), được phát triển bởi hãng Booz-Allen & Hamilton thuộc thành phần của Hải quân Hoa Kỳ (hợp tác cùng với công ty Lockheed) trong chương trình chế tạo tên lửa Polaris trang bị cho tàu ngầm. Những thuật toán này đã lan rộng một cách nhanh chóng sang nhiều doanh nghiệp tư nhân.

Năm 1969, viện Quản lý Dự án (PMI) đã được thành lập để phục vụ cho lợi ích của kỹ nghệ quản lý dự án. Những tiền đề của viện Quản lý dự án (PMI) là những công cụ và kỹ thuật quản lý dự án được chia sẻ bằng nhau giữa các ứng dụng phổ biến trong những dự án từ ngành công nghiệp phần mềm cho tới ngành công nghiệp xây dựng. Trong năm 1981, ban giám đốc viện Quản lý dự án (PMI) đã cho phép phát triển hệ lý thuyết, tạo thành cuốn sách Hướng dẫn về những kiến thức cốt lõi trong Quản lý dự án (PMBOK Guide). Cuốn sách này chứa các tiêu chuẩn và nguyên tắc chỉ đạo về thực hành được sử dụng rộng rãi trong toàn bộ giới quản lý dự án chuyên nghiệp.

1/ Thuật giải FCFS - First Come First Served (Đến trước phục vụ trước)
- Đơn giản, dễ thực hiện.
- Các tiến trình được cấp CPU từ đầu dãy tới cuối dãy trong hàng đợi Ready Queue hoạt động theo nguyên tắc FIFO (First In First Out).
- Thời gian chờ trung bình khá lớn.
Ví dụ minh hoạ: Bạn cứ hình dung hàng đợi mua vé xem phim, từng người sẽ xếp hàng chờ mua vé theo nguyên tắc ai đến trước thì được mua trước, ai đến sau thì phải đợi người đến trước mua vé xong mới được mua.

2/ Thuật giải SJFS - Shorted Job First Scheduling (Ngắn hơn chạy trước)
- Trong thuật giải này, nếu như tiến trình nào có khoảng CPU kế tiếp nhỏ hơn thì sẽ ưu tiên chạy trước, nếu như những tiến trình nào có khoảng CPU bằng nhau thì sẽ hoạt động theo nguyên tắc FIFO (First In First Out)
- Giải thuật khá tối ưu do giải thuật biết cách ước đoán khoảng CPU kế tiếp.
- SJSF không tiếm quyền (Non - Preemptive SJSF): tiến trình sẽ chạy hết khoảng CPU của nó mà không bị tiếm quyền giữa chừng.
- SJSF tiếm quyền (Preemptive SJSF): Tiến trình đến sau nếu có khoảng CPU kế tiếp (Next CPU Burst) nhỏ hơn khoảng CPU còn lại của các tiến trình trước nó thì sẽ ưu tiên chạy trước (Shorted Remaining First).
Ví dụ minh hoạ: Trong một nhà ga, có một vị khách A đến trước mua 9 vé (Next CPU Burst) cùng lúc, trong khi người bán vé đang bán cho vị khách A được 2 vé thì có vị khách B đến sau mua 7 vé, do số vé của vị khách B nhỏ hơn vị khách A nên người bán vé chủ động bán vé cho vị khách B, do đó vị khách A sẽ chờ, trong khi bán cho vị khách B được 3 vé, thì lại có vị khách C lại mua số lượng 3 vé, do số vé của vị khách C nhỏ hơn số vé còn lại của vị khách A (còn lại 7 vé) lẫn vị khách B (còn lại 4 vé) nên vị khách B sẽ cùng vị khách A chờ cho người bán vé bán cho vị khách C, tương tự như vậy với các vị khách đến sau. Tuy nhiên nếu như số lượng vé của người đến sau bằng với số lượng vé hoặc bằng số lượng vé của các người đi mua trước thì người bán vé sẽ phục vụ ai đến trước mua trước.

3/ Điều phối theo vòng Robin (RRS - Round Robin Scheduling)
- Đây chính là kĩ thuật chia thời gian , kiểu điều phối tương tự kiểu FCFS, các tiến trình vẫn theo nguyên tắc đến trước thì được phục vụ trước, tuy nhiên mỗi tiến trình chỉ vận hành trong một khoảng thời gian nhất định mà hệ điều hành cấp trong khoảng 10 - 100ms. Do vậy, sau khoảng thời gian này, tiến trình đang vận hành sẽ bị tiếm quyền và đưa vào cuối hàng chờ Ready, tiến trình kế tiếp nó được dịch lên đầu tiên và vận hành.
Ví dụ minh hoạ: Trong một cửa hàng Game có một máy chơi game, các Gamer nếu muốn chơi game sẽ mua các thẻ để chơi game với thời gian chơi khác nhau ví dụ như thẻ game 10 phút thẻ game 30 phút, thẻ game 120 phút. Tuy nhiên chủ hàng (CPU) quy định mỗi người chỉ được ngồi chơi trên máy trong khoảng 20 phút, sau khoảng thời gian này, dù người chơi vẫn còn thời gian chơi trên thẻ thì cũng phải nhường máy cho người kế tiếp chơi và ra cuối hàng đợi, dĩ nhiên nếu có người chơi chơi với thẻ game thời gian 10 phút, thì người đến sau sẽ được chơi sớm hơn 10 phút, tương tự cho các người chơi đang xếp hàng sau.

4/ Điều phối hàng chờ nhiều mức (MQS - Multilevel Queue Scheduling)
- Trong điều phối này thì hàng chờ Ready sẽ được phân cấp thành nhiều mức với các độ ưu tiên khác nhau.
- Độ ưu tiên của các tiến trình: Tiến trình hệ thống > Tiến trình tương tác > Tiến trình tương tác có sửa > Tiến trình lô (Batch) - Tiến trình sinh viên.
. Các hàng chờ sẽ có thuật giản điều phối riêng. Mức tiến trình tương tác (Interactive) chạy ở mặt trước (Foreground) sẽ có độ ưu tiên cao nhật trong khi các mức tiến trình lô (Batch) vận hành trong mặt chìm (Background).
- Quan hệ tương tác giữa các mức:
a/ Ưu tiên cố định: Các tiến trình sẽ luôn chạy với nguyên tắc nếu ưu tiên cao thì được chạy trước, các tiến trình sẽ chạy mức cao rồi xuống mức dưới, tuy nhiện nếu đang chạy mức dước mà nếu như có tiến trình mức cao hơn xuất hiện thì tiến trình mức dưới sẽ bị tiếm quyền cho tiến trình ở mức cao hơn.
Ví dụ minh hoạ: Trong một khu tị nạn phân phát thức ăn cho người nghèo khó, có 5 cửa phân phát thức ăn với 5 độ ưu tiên khác nhau. Cửa 1 với độ ưu tiên cao nhất dành cho họ hàng, thân nhân với người phát thức ăn. Cửa 2 với độ ưu tiên thứ nhì dành cho những người có công với đất nước, những người lính, thương binh. Cửa 3 dành cho những người già. Cửa thứ 4 dành cho phụ nữ. Cửa 5 dành cho thanh niên, nam giới. Với 5 cửa này người phân phát thức ăn sẽ cung cấp thức ăn theo độ ưu tiên, tại một thời điểm chỉ phục vụ 1 cửa, phục vụ cửa độ ưu tiên cao hơn sẽ tới độ thấp hơn, tuy nhiên nếu như người phát thức ăn đang phục vụ cung cấp thức ăn cho thanh niên, trong khi đó cửa 1 có người xuất hiện thì người phát thức ăn sẽ quay lại cửa 1 phục vụ tiếp, cứ như vậy tiếp tục.
b/ Phân bổ theo tỉ lệ thời lượng: CPU sẽ dành một khoảng thời gian đa số cho Foreground ví dụ khoảng 80%, cho Background 20%.

5/ Điều phối hàng chờ nhiều mức có điều tiết
- Hoạt động như MQS tuy nhiên trình điều phối này có thể linh động điều tiết tiến trình sang các mức khác, ví dụ như những tiến trình CPU sẽ đôi lúc hướng mức dưới và những tiến trình hướng I/O đôi lúc lại hướng lên trên.
- Các thông số đặc trưng:
a/ Số mức (số hàng chờ).
b/ Thuật giải điều phối cho mỗi mức.
c/ Phương thức nâng cấp tiến trình.
d/ Phương thức hạ cấp tiến trình.
e/ Phương thức chọn hàng chờ (chọn mức) cho tiến trình mới.
Ví dụ minh hoạ: Cùng với ví dụ phát thức ăn trong khu tị nạn trên, một số thanh niên ở cửa số 5 có thể được ưu tiên chuyển lên cửa 2 do có thể thân nhân có công với đất nước, trong khi có thể một số người già ở cửa 3 nhường cho một số phụ nữ yếu ở cửa 4 đi lên

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.

Admin đã viết: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.

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

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.

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.

1. First Come First Served (FCFS)
Trong thuật toán này, độ ưu tiên phục vụ tiến trình căn cứ vào thời điểm hình thành tiến trình. Hàng đợi các tiến trình được tổ chức theo kiểu FIFO. Mọi tiến trình đều được phục vụ theo trình tự xuất hiện cho dến khi kết thúc hoặc bị ngắt.
Ưu điểm của thuật toán này là giờ CPU không bị phân phối lại (không bị ngắt )chi phí tổ chức thực hiện rất thấp (vì không phải thay đổi thứ tự ưu tiên phục vụ, thứ tự ưu tiên là thứ tự của tiến trình trong hàng đợi)
Nhược điểm của thuật toán là thời gian trung bình chờ phục vụ của các tiến trình là như nhau ( không kể tiến trình ngắn hay dài), do đó dẫn tới 3 nhược điểm sau:
- thời gian chờ trung bình sẽ tăng vô hạn khi hệ thống tiếp cận tới hạn khả năng phục vụ của mình.
- nếu độ phát tán thời gian thực hiện tiến trình tăng thì thời gian chờ đợi trung bình cũng tăng theo.
- khi có tiến trìn dài, ít bị ngắt thì các tiến trình khác phải chờ đợi lâu hơn.
2. Shortest Job First (SJF)
thuật toán SJC xác định thứ tự ưu tiên thực hiện tiến trình dựa vào tổng thời gian thực hiện tiến trình. Tiến trình nào có tổng thời gian thực hiện ngắn sẽ được ưu tiên phục vụ trước.
Ưu điểm của thuật toán là thời giàn chờ đợi trung bình của các tiến trình ngắn hơn so với SCFS. SJF nhanh chóng loại bỏ các tiến trình ngắn, giảm số lượng các tiến trình trong hàng đợi.
Nhược điểm chính của thuật toán là chế độ phân phối lại giờ CPU cũng được áp dụng trong trường hợp ngắt các tiến trình dài đang thực hiện để phục vụ các tiến trình ngắn hơn mới xuất hiện trong hàng đợi. Nếu tiến trình mới xuất hiện có tổng thời gian thực hiện ngắn nhưng vẫn lớn hơn thời gian cần thiết để thực hiện nốt tiến trình đang thực hiện thì việc ngắt tiến trình là không hợp lý.
3. Shortest Remain Time (SRT)
Tương tư như SJF nhưng trong thuật toán này, độ ưu tiên thực hiện các tiến trình dựa vào thời gian cần thiết để thực hiện nốt tiến trình (bằng tổng thời gian trừ đi thời gian đã thực hiện). Như vậy trong thật toán này cần phải thường xuyên cập nhật thông tin về thời gian đã thực hiện tiến trình. Đồng thời, chế độ phân bổ lại giờ CPU cũng phải được áp dụng nếu không sẽ làm mất tính ưu việt của thuật toán.
4. Round Robin (RR)
- Trong thuật toán này, hệ thông quy định một lượng tử thời gain (time quantum) khoảng từ 10-100 mili giây (ms).
- Mỗi tiến trình trong hàng đợi lần lượt được phân phối một lượng tử thời gian để thực hiện. Sau khoảng thời gian đó, nếu tiến trình chưa kết thúc hoặc không rời và trạng thái đợi thì nó được chuyển về cuối hàng đợi.
- Hàng đợi các tiến trình được tổ chức theo kiểu vòng tròn và các tiến trình luôn luôn đảm bảo được phục vụ. khi có tiến trình mới phát sinh, nó sẽ được đưa vào hàng đợi vòng tròn và được đặt ở vị trí phục vụ ngay. Các tiến trình dù ngắn hay dài đều có độ ưu tiên phục vụ như nhau.
- Trên thực tế, để đảm bảo độ ưu tiên cho các tiến trình dài, hệ thống sẽ phân chia các tiến trình thành m lớp. Số lần đươc phục vụ và thời gian một lần phục vụ tiến trình tại mỗi lớp khác nhau (giả sử ở lớp thứ i, tiến trình được phục vụ ki lần và mỗi lần với thời gian qi).
- Nếu sau khoảng thời gian đã được phân phối mà tiến trình chưa kết thúc hoặc không bị ngắt thì nó sẽ được chuyển sang lớp thứ i + 1 ( với ki+1 và qi +1 lớn hơn .). Lượng tử thời gian sẽ tăng dần cho đến khi tiến trình rơi vào lớp ngoài cùng (lớp m). Ở đó nó sẽ được phục vụ với lượng tử qm không đổi. Như vậy thứ tự ưu tiên của các tiến trình sẽ tăng dần theo thời gian xếp hàng đợi.
- Ưu điểm của phương pháp phục vụ đồng mức theo lớp sẽ cho phép hệ thông ưu tiên những tiến trình ngắn (vì nó kết thúc sớm) nhưng nó không gây tổn hại lớn cho các tiến trình dài.
- Nhược điểm là do phải thường xuyên phân phối lại giờ CPU nên thời gian chờ đợi trung bình của Round Robin có thể lớn hơn so với FCFS.

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

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.
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.
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.
Sơ đồ ngang Gantt, còn gọi là Sơ đồ Gantt hay biểu đồ Gantt, (tiếng Anh là: Gantt chart), là một dạng thể hiện tiến độ dự án cổ điển nhất, được Henry Gantt phát minh ra vào năm 1910. Tuy là cổ điển nhưng do tính chất đơn giản dễ hiểu của nó mà hiện nay sơ đồ ngang Gantt vẫn được dùng phổ biến trong quản lý dự án, thậm chí còn được cải tiến, dùng trong phần mềm quản lý dự án hiện đại như; Microsoft Project, để chuyển đổi việc thể hiện các dạng tiến độ phức tạp như sơ đồ mạng (dự án).

Bài 1. Xét tập các tiến trình sau (với thời gian yêu cầu CPU và độ ưu tiên kèm theo) :

Giả sử các tiến trình cùng được đưa vào hệ thống tại thời điểm 0
a)Cho biết kết quả điều phối hoạt động của các tiến trình trên theo thuật toán FIFO; SJF; điều phối theo độ ưu tiên độc quyền (độ ưu tiên 1 > 2 > ...); và RR (quantum=2).
b)Cho biết thời gian lưu lại trong hệ thống (turnaround time) của từng tiến trình trong từng thuật toán điều phối ở câu a.
c)Cho biết thời gian chờ trong hệ thống (waiting time) của từng tiến trình trong từng thuật toán điều phối ở câu a.
d)Thuật toán điều phối nào trong các thuật toán ở câu a cho thời gian chờ trung bình là cực tiểu ?
Bài 2. Giả sử có các tiến trình sau trong hệ thống :

Sử dụng nguyên tắc điều phối độc quyền và các thông tin có được tại thời điểm ra quyết định để trả lời các câu hỏi sau đây :
a)Cho biết thời gian lưu lại trung bình trong hệ thống (turnaround time) của các tiến trình trong thuật toán điều phối FIFO.
b)Cho biết thời gian lưu lại trung bình trong hệ thống (turnaround time) của các tiến trình trong thuật toán điều phối SJF.
c)Thuật toán SJF dự định cải tiến sự thực hiện của hệ thống , nhưng lưu ý chúng ta phải chọn điều phối P1 tại thời điểm 0 vì không biết rằng sẽ có hai tiến trình ngắn hơn vào hệ thống sau đó . Thử tính thời gian lưu lại trung bình trong ệ thống nếu để CPU nhàn rỗi trong 1 đơn vị thời gian đầu tiên và sau đó sử dụng SJF để điều phối. Lưu ý P1 và P2 sẽ phải chờ trong suốt thời gian nhàn rỗi này, do vậy thời gian chờ của chúng tăng lên. Thuật toán điều phối này được biết đến như điều phối dựa trên thông tin về tương lai.
Bài 3. Phân biệt sự khác nhau trong cách tiếp cận để ưu tiên cho tiến trình ngắn trong các thuật toán điều phối sau :
a) FIFO.
b)RR
c)Điều phối với độ ưu tiên đa cấp
Bài 4. Cho biết hai ưu điểm chính của mô hình đa tiểu trình so với đa tiến trình. Mô tả một ứng dụng thích hợp vớ mô hình đa tiểu trình và một ứng dụng khác không thích hợp.
Bài 5. Mô tả các xử lý hệ điều hành phải thực hiện khi chuyển đổi ngữ cảnh giữa :
a)các tiến trình
b)các tiểu trình
Bài 6. Xác định thời lượng quantum q là một nhiệm vụ khó khăn. Giả sử chi phí trung bình cho một lần chuyển đổi ngữ cảnh là s, và thời gian trung bình một tiến trình hướng nhập xuất sử dụng CPU trước khi phát sinh một yêu cầu nhập xuất là t ( t>>s). Thảo luận các tác động đến sự thực hiện của hệ thống khi chọn q theo các quy tắc sau :
a)q bất định
b)q lớn hơn 0 1 ít
c)q = s
d)s < q < t
e)q = t
f)q > t
Bài 7. Giả sử một hệ điều hành áp dụng giải thuật điều phối multilevel feedback với 5 mức ưu tiên (giảm dần). Thời lượng quantum dành cho hàng đợi cấp 1 là 0,5s. Mỗi hàng đợi cấp thấp hơn sẽ có thời lượng quantum dài gấp đôi hàng đợi ứng với mức ưu tiên cao hơn nó. Một tiến trình khi vào hệ thống sẽ được đưa vào hàng đợi mức cao nhất, và chuyển dần xuống các hàng đợi bên dưới sau mỗi lượt sử dụng CPU. Một tiến trình chỉ có thể bị thu hồi CPU khi đã sử dụng hết thời lượng quantum dành cho nó. Hệ thống có thể thực hiện các tác vụ xử lý theo lô hoặc tương tác, và mỗi tác vụ lại có thể hướng xử lý hay hướng nhập xuất.
a)Giải thích tại sao hệ thống này hoạt động không hiệu quả ?
b)Cần phải thay đổi (tối thiểu) như thế nào để hệ thống điều phối các tác vụ với những bản chất khác biệt như thế tốt hơn ?
Trước tiên là phần lý thuyết của phần này nhé. Phần điều phối tiến trình chúng ta có 4 cách là FIFO , RR , SJF, và độ ưu tiên. Với những bài toán của điều phối tiến trình chúng ta sẽ phải tính một trong những thông số sau :
Thời gian xử lý,Thời gian xử lý trung bình
Thời gian đợi,Thời gian đợi trung bình
Thời gian lưu lại trong hệ thống
================================================== =========
1.Điều phối FIFO
CPU đượ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. Đây là thuật toán điều phối theo nguyên tắc độc quyền. Một khi CPU được cấp phát cho tiến trình, CPU chỉ được tiến trình tự nguyện giải phóng khi kết thúc xử lý hay khi có một yêu cầu nhập/xuất.


*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi : P1=0; P2=24-1 =23 ; P3 = 24+3-2 = 25
*Thời gian đợi trung bình: (0+23+25)/3 = 16
* Thời gian lưu lại trong hệ thống : P1=24 ; P2=3; P3=3
* Thời gian lưu lại trung bình : (24+3+3)/3 =10

2.Chiến lược điều phối xoay vòng :
Danh sách sẵn sàng được xử lý như một danh sách vòng, bộ điều phối lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là quantum. Đây là một giải thuật điều phối không độc quyền : khi một tiến trình sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp trong danh sách. Nếu tiến trình bị khóa hay kết thúc trước khi sử dụng hết thời gian quantum, hệ điều hành cũng lập tức cấp phát CPU cho tiến trình khác. Khi tiến trình tiêu thụ hết thời gian CPU dành cho nó mà chưa hoàn tất, tiến trình được đưa trở lại vào cuối danh sách sẵn sàng để đợi được cấp CPU trong lượt kế tiếp.



*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi :
P1=0
P2=4-1=3
P3=4+3-2=5
P1'=4+3+3-3=6
đến lúc này p1 sẽ được xử lý liên tục nên không phải tính thời gian chờ của p1'' p1'''...
*Thời gian đợi trung bình: (0+3+5+6)/3=4.66
* Thời gian lưu lại trong hệ thống :
P1: vòng 1 =4 vòng 2=20 khoảng cách 2 vòng là 6 => thời gian lưu lại của P1 =4+20+6 =30
P2=3
P3=3
* Thời gian lưu lại trung bình : (30+3+3)/3=12

3.Điều phối với độ ưu tiên
Mỗi tiến trình được gán cho một độ ưu tiên tương ứng, tiến trình có độ ưu tiên cao nhất sẽ được chọn để cấp phát CPU đầu tiên. Độ ưu tiên có thể được định nghĩa nội tại hay nhờ vào các yếu tố bên ngoài. Độ ưu tiên nội tại sử dụng các đại lượng có thể đo lường để tính toán độ ưu tiên của tiến trình, ví dụ các giới hạn thời gian, nhu cầu bộ nhớ…Độ ưu tiên cũng có thể được gán từ bên ngoài dựa vào các tiêu chuẩn do hệ điều hành như tầm quan trọng của tiến trình, loại người sử dụng sỡ hữu tiến trình… Giải thuật điều phối với độ ưu tiên có thể theo nguyên tắc độc quyền hay không độc quyền. Khi một tiến trình được đưa vào danh sách các tiến trình sẵn sàng, độ ưu tiên của nó được so sánh với độ ưu tiên của tiến trình hiện hành đang xử lý. Giải thuật điều phốivới độ ưu tiên và không độc quyền sẽ thu hồi CPU từ tiến trình hiện hành để cấp phát cho tiến trình mới nếu độ ưu tiên của tiến trình này cao hơn tiến trình hiện hành. Một giải thuật độc quyền sẽ chỉ đơn giản chèn tiến trình mới vào danh sách sẵn sàng, và tiến trình hiện hành vẫn tiếp tục xử lý hết thời gian dành cho nó.


* Trường hợp độc quyền
*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi : P1=0;P2=23;P3=25
*Thời gian đợi trung bình: (0+23+25)/3=16
* Thời gian lưu lại trong hệ thống : P1=24; P2=3;P3=3
* Thời gian lưu lại trung bình: ( 24+3+3)/3=10

*Trường hợp không độc quyền:
*Thời gian xử lý : P1=24,P2=3,P3=3
* Thời gian xử lý trung bình : (24+3+3)/3=10
*Thời gian đợi :

P1=0
P2=0+1-1=0
P3=0+1+3-2=2
P1'=0+1+3+3-3=4
*Thời gian đợi trung bình: (0+0+2+4)/3=2
* Thời gian lưu lại trong hệ thống :
P1 Vòng 1 = 1 vòng 2= 23 khoảng cách giữa 2 vòng =6 => thời gian lưu lại của p1= 1+23+6=30
p2=3
p3=3

* Thời gian lưu lại trung bình : (30+3+3)/3=12

4.Chiến lược công việc ngắn nhất (Shortest-job-first SJF)
Đây là một trường hợp đặc biệt của giải thuật điều phối với độ ưu tiên. Trong giải thuật này, độ ưu tiên p được gán cho mỗi tiến trình là nghịch đảo của thời gian xử lý t mà tiến trình yêu cầu : p = 1/t. Khi CPU được tự do, nó sẽ được cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết thúc- tiến trình ngắn nhất. Giải thuật này cũng có thể độc quyền hay không độc quyền. Sự chọn lựa xảy ra khi có một tiến trình mới được đưa vào danh sách sẵn sàng trong khi một tiến trình khác đang xử lý. Tiến trình mới có thể sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) ngắn hơn thời gian còn lại mà tiến trình hiện hành cần xử lý. Giải thuật SJF không độc quyền sẽ dừng hoạt động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến trình hiện hành tiếp tục xử lý.



* Trường hợp độc quyền

*Thời gian xử lý : P1=6,P2=8,P3=4;P4=2
* Thời gian xử lý trung bình : (6+8+4+2)/4=5
*Thời gian đợi : P1=0 p4=5 ; p3=6; p2=9
*Thời gian đợi trung bình: (0+5+6+9)/4=5
* Thời gian lưu lại trong hệ thống : P1=6; P4=2;P3=4;P2=8
* Thời gian lưu lại trung bình: ( 6+2+4+/4=5

*Trường hợp không độc quyền:
*Thời gian xử lý : P1=6,P2=8,P3=4;P4=2
* Thời gian xử lý trung bình : (6+8+4+2)/4=5
*Thời gian đợi :
P1=0
P4=2
P1'=3
P3=5
P2=8
*Thời gian đợi trung bình: (0+2+3+5+/4=4.5
* Thời gian lưu lại trong hệ thống :
P1 Vòng 1 = 3 vòng 2= 3 khoảng cách giữa 2 vòng =2 => thời gian lưu lại của p1= 3+3+2=8
P4=2
p3=4
P2=8
* Thời gian lưu lại trung bình : (8+2+4+/4=5

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

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

Chào mọi người, mình có một vài thắc mắc như thế này trong bài tập Biểu đồ Gantt. Tại sao khi đến thời điểm thứ 33, chúng ta không cho chạy P3 mà lại cho chạy P2, mình chưa hiểu lắm vấn để này, mong mọi người giúp mình giải đáp. Cảm ơn mọi người.

Mình có tự đặt ra bài tập riêng để làm, mong mọi người xem xét coi đã đúng chưa và xin ý kiến. Cảm ơn mọi người.

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.

Phân biệt thuật giải MQS với thuật giải MFQS

-Multilevel Queue Scheduling:
+ Đượ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 FCFS đến trước phục vụ trước.

*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ụ.
- 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.
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ếm 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ó nghĩa là vào trước thì ra trước
* nonprecinptive (không dừng process đang thực thi  chỉ dưng khi bi kết thúc hoặc bị chặn chờ thiết bị I/O)
Sử dụng tính chất nonprocinptive : nghĩa là các process thực thi hết thời gian của mình và các process khac xuất hiện thì phại đợi
VD:  biểu diễn điều phối

1. 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  chiến lược định thời CPU.

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

Tham khảo nhé

dangthituyetnhungTH08a1 đã viết: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ếm 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

Bổ sung thêm:
Các tình huống ra quyết định của trình điều phối:
1. Khi tiến trình Running sang Waiting.
- Khi tiến trình cần thực hiện nhập xuất thì trình điều phối sẽ tìm kiếm một tiến trình khác để câp CPU. Trong trường hợp này tiến trình tự ngừng sử dụng CPU => điều phối không tiếm quyền.
2. Khi tiến trình chuyển từ Running sang Ready.
- Khi thời gian thực hiện của tiến trình vượt quá thời gian quy định (vì hệ điều hành chia thời gian) thì HĐH sẽ ngừng cấp CPU và đưa tiến trình vào Ready để cấp CPU cho một tiến trình khác. Trường hợp này có sự can thiệp của HĐH để lấy CPU => điều phối có tiếm quyền.
3. Khi tiến trình chuyền từ Waiting sang Ready.
- Sau khi quá trình nhập xuất đã xong, tiến trình lại được đưa vào hàng chờ. Lúc này HĐH sẽ kiểm tra xem có thể tiếp tục đưa tiến trình chờ đó chạy tiếp hay không? Nếu có sẽ cấp CPU cho tiến trình này tiếp tục làm việc. Trường hợp này có sự can thiệp của HĐH => điều phối có tiếm quyền.
4. Khi tiến trình kết thúc công việc.
- Sau khi tiến trình hoàn tất công việc thì tự trả CPU lại cho HĐH, HĐH sẽ tìm một tiến trình thích hợp khác để cấp CPU. Trong trường hợp này tiến trình tự ngừng sử dụng CPU => điều phối không tiếm quyền.

- Điều phối không tiếm quyền là khi tiến trình giữ CPU cho đến khi kết thúc hoặc chuyển sang trạng thái waiting mà không có sự can thiệp thu hồi CPU của HĐH.
- Điều phối có tiếm quyền là khi HĐH can thiệp để thu hồi CPU để cấp cho một tiến trình khác hoạt động.