Thảo luận Bài 6

Phân biệt thuật giải MSQ với thuật giải MFSQ

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

Điều phối tiến trình

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ý.
1. Giới thiệu

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

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

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

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

2. Tổ chức điều phối
2.1. 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 đó.

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.

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.

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

a) Đ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ý

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

Bổ sung so sánh MQS (Multilevel Queue Scheduling ) và MFQS(Multilevel Feedback Queue Scheduling):
Giống nhau:
MQS và MFQS đều điều phối CPU với nhiều hàng chờ.
Khác nhau : MFQS có điều tiết, có phần mềm dẻo hơn MQS

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ý tiếm quyền hoặc không tiếm quyền.

Điều phối có tiếm quyền : Nguyên lý điều phối có tiếm 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 độc 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 tiếm 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 tiếm quyền : Ngược với nguyên lý độc quyền, điều phối theo nguyên lý không tiếm 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 tiếm 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ó tiếm 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ó tiếm 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 tiếm 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 tiếm 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.

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

Năm tiêu chí điều phối CPU.
1. Công suất CPU (CPU Utilisation): Thực tế đạt từ 40% - 90% thời gian CPU. CPU càng bận càng tốt.
2. Thông suất hệ thống (Throughput): Số TT hoàn tất trong 1 đơn vị thời gian, ví dụ: 1 TT / giờ, 10 TT / giây.
3. Tổng thời gian làm việc (Turnaround Time): Kể từ khi bắt đầu đến khi kết thúc tiến trình (Bao gồm tổng thời gian chờ tại Ready Queue, tổng thời gian sử dụng CPU, tổng thời gian I/O, …).
4. Thời gian chờ (Waiting Time): Tổng thời gian chờ tại Ready Queue.
5. Thời gian đáp ứng (Response Time): Thời gian kể từ khi người dùng đặt yêu cầu cho đến khi có phản hồi đầu tiên.

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 qu1 q đơn vị thời gian.
VD: RRs với thời lượng = 20ms(RRS with Time Quantum =20ms)
* Giả sử hàng chờ Ready có các tiến trình sau:
Tiến trình.......... Khoảng CPU
p1...................... 53
p2 ......................17
p3....................... 68
p4 ......................24
* Thời gian chờ trung bình : (0+57+24)+20+(37+40+17)+(57+40))/4=73ms

Tiến trình có khoảng cpu kế tiếp nhỏ hơn thì chạy trước. Nếu bằng nhau thì tiến trình nào vào trước thì chạy trước.
- SJFS có tiếm quyền: Nếu tiến trình có khoảng cpu kế tiếp nhỏ hơn thời gian cpu đang vận hành thỉ sẽ được ưu tiên thay thế. Nếu thời gian xử lý của 1 tiến trình nào đó quá dài thì nó sẽ bị thay thế bởi tiến trình có khoảng cpu nhỏ hơn.
VD: Một người bán hàng bán 5 mặt hàng khác nhau. Có 4 người khách ghé vào mua . Một người mua 2 loại khác nhau những người còn lại mua 1 loại như nhau. Có tiếm quyền thì người bán hàng sẽ bán cho người mua 2 món 1 loại trước, sau đó bán cho những người khác. Sau khi giải quyết xong anh ta sẽ bán tiếp cho người mua 2 loại.
-SJFS không tiếm quyền : Tiến trình nào vào đầu tiên sẽ được xử lý hết, những tiến trình sau thì tiến trình nào có khoảng cpu nhỏ hơn thỉ được chạy kế tiếp. Nếu trường hợp bằng nhau thì ai đến trước được chạy trước
VD: có 4 người đi mua vé xem phim. Nếu người thứ nhất mua 4 loại vé khác nhau, thì người bán sẽ bán hết bốn loại cho anh ta, sau đó sẽ bán cho các người còn lại, những người sau phải chờ cho anh ta mua xong rồi mới tới lượt mua.

PhamThiHoa-I91C đã viết:

LeTanDat (I11C) đã viết:

phamngoctan095 (I11C) đã viết:Chào cả nhà!

Mình thấy 2 dạng bài tập hôm qua mà Thầy giảng trên lớp, nghe Thầy nói là sẽ cho ra 1 trong 2 dạng này chiếm khoảng 20% tổng số điểm của bài thi. Bài tập của Thầy cho hôm qua thì các bạn đã giải đáp cụ thể lắm ròy, zj bạn nào có bài tập dạng tương tự thì post lên để mọi người cùng giải nha!

Mình xem trong thư mục HeDieuHanh\DeCuong có mẫu đề thi của các năm về trước cũng có nhiều bài tập tương tự, nên lấy thử 1 bài trong file "De thi 1 lan 1 HDH 2005-2006 (HK2) - Thay To Tuan.doc" như sau:

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

Tiến trình	Thời điểm đến (ms)	CPU-Burst (ms)
P1	4	46
P2	30	28
P3	51	33

Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phương án):
a. Thể hiện bằng biểu đồ Gantt (1,0 điểm)
b. Tính thời gian chờ trung bình của các tiến trình (1,0 điểm)

Mọi người cùng giải để hiểu thêm nha!

- Biểu đồ Gantt:
| P1 | P1 | P2 | P3 | P1 | P2 | P3 |
4...24...44...64...84...90...98...111
P1= 90-4-46=40
P2=98-30-28=40
P3=111-51-33=27
Thời gian chờ trung bình:
=(40+40+27)/3=35.66 (ms)

Chính xác rồi đó bạn, mình cũng có cách tính ra kết quả giống bạn đó

Bài này sai rồi, ngay sau khi P2 chạy xong thì P1 đang ở thời điểm 44 sẽ được chạy tiếp chứ không phải P3 là 51 đâu.

08H1010052 đã viết:

PhamThiHoa-I91C đã viết:

LeTanDat (I11C) đã viết:

phamngoctan095 (I11C) đã viết:Chào cả nhà!

Mình thấy 2 dạng bài tập hôm qua mà Thầy giảng trên lớp, nghe Thầy nói là sẽ cho ra 1 trong 2 dạng này chiếm khoảng 20% tổng số điểm của bài thi. Bài tập của Thầy cho hôm qua thì các bạn đã giải đáp cụ thể lắm ròy, zj bạn nào có bài tập dạng tương tự thì post lên để mọi người cùng giải nha!

Mình xem trong thư mục HeDieuHanh\DeCuong có mẫu đề thi của các năm về trước cũng có nhiều bài tập tương tự, nên lấy thử 1 bài trong file "De thi 1 lan 1 HDH 2005-2006 (HK2) - Thay To Tuan.doc" như sau:

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

Tiến trình	Thời điểm đến (ms)	CPU-Burst (ms)
P1	4	46
P2	30	28
P3	51	33

Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phương án):
a. Thể hiện bằng biểu đồ Gantt (1,0 điểm)
b. Tính thời gian chờ trung bình của các tiến trình (1,0 điểm)

Mọi người cùng giải để hiểu thêm nha!

- Biểu đồ Gantt:
| P1 | P1 | P2 | P3 | P1 | P2 | P3 |
4...24...44...64...84...90...98...111
P1= 90-4-46=40
P2=98-30-28=40
P3=111-51-33=27
Thời gian chờ trung bình:
=(40+40+27)/3=35.66 (ms)

Chính xác rồi đó bạn, mình cũng có cách tính ra kết quả giống bạn đó

Bài này sai rồi, ngay sau khi P2 chạy xong thì P1 đang ở thời điểm 44 sẽ được chạy tiếp chứ không phải P3 là 51 đâu.

Bài này đúng là giải sai rồi, p2 vào ở thời điểm 44, nó chạy 20ms dừng ở thời điểm 64, lúc này p3 có thể vào nhưng do p1 còn đang chờ, khi nhảy vào thì p3 đứng sau p1, p1 đc chạy trước, khi p1 hoàn thành xong thì p3 mới bắt đầu.
p1: 70-4-46=20
p2: 98-30-28=40
p3: 111-51-33=27
tgian chờ trung bình (20+40+27)/3=29ms
(mọi người thử vẽ lại rồi so sánh kết quả nhe' ^^)

NguyenXuanTri28 đã 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ế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

Tại thời điểm 1 & 4 là Non Preenmptive mà bạn,
hình như bạn đã ghi nhầm

HuynhPhuong (I11C) đã viết:
Bài này sai rồi, ngay sau khi P2 chạy xong thì P1 đang ở thời điểm 44 sẽ được chạy tiếp chứ không phải P3 là 51 đâu.
Bài này đúng là giải sai rồi, p2 vào ở thời điểm 44, nó chạy 20ms dừng ở thời điểm 64, lúc này p3 có thể vào nhưng do p1 còn đang chờ, khi nhảy vào thì p3 đứng sau p1, p1 đc chạy trước, khi p1 hoàn thành xong thì p3 mới bắt đầu.
p1: 70-4-46=20
p2: 98-30-28=40
p3: 111-51-33=27
tgian chờ trung bình (20+40+27)/3=29ms
(mọi người thử vẽ lại rồi so sánh kết quả nhe' ^^)

Hi! Bạn nên đọc những bài trên nha. Bạn nhầm giữa RRS và SJFS ùi
Trích nguyên văn của bạn LeTanDat (I11C)
Đầu tiên là P1 chạy với thời lượng là 20ms đến thời gian 24ms thì dừng nhưng vì chưa có tiến trình nào tới nên P1 được chạy tiếp, đến 44ms thì P2 đến, P1 được đưa xuống cuối hàng chờ, P2 chạy cũng với thời lượng 20ms đến 64ms thì P3 đến, P2 được đưa xuống cuối hàng chờ. Cứ như vậy tiếp tục thực hiện.

namzhou(I11C) đã viết:

HuynhPhuong (I11C) đã viết:
Bài này sai rồi, ngay sau khi P2 chạy xong thì P1 đang ở thời điểm 44 sẽ được chạy tiếp chứ không phải P3 là 51 đâu.
Bài này đúng là giải sai rồi, p2 vào ở thời điểm 44, nó chạy 20ms dừng ở thời điểm 64, lúc này p3 có thể vào nhưng do p1 còn đang chờ, khi nhảy vào thì p3 đứng sau p1, p1 đc chạy trước, khi p1 hoàn thành xong thì p3 mới bắt đầu.
p1: 70-4-46=20
p2: 98-30-28=40
p3: 111-51-33=27
tgian chờ trung bình (20+40+27)/3=29ms
(mọi người thử vẽ lại rồi so sánh kết quả nhe' ^^)

Hi! Bạn nên đọc những bài trên nha. Bạn nhầm giữa RRS và SJFS ùi
Trích nguyên văn của bạn LeTanDat (I11C)
Đầu tiên là P1 chạy với thời lượng là 20ms đến thời gian 24ms thì dừng nhưng vì chưa có tiến trình nào tới nên P1 được chạy tiếp, đến 44ms thì P2 đến, P1 được đưa xuống cuối hàng chờ, P2 chạy cũng với thời lượng 20ms đến 64ms thì P3 đến, P2 được đưa xuống cuối hàng chờ. Cứ như vậy tiếp tục thực hiện.

Thanks bạn

phamdieptuan (I11C) đã viết:

minhgiangbc đã viết:

DangNgocMinh(I11C) đã viết:

chipphonui đã viết:đề. một hệ thống có 3 tiến trình, với thời điểm đến và tg sử dụng CPU như sau;

P1 3 35

P2 10 20

P3 25 15
Hãy dùng thuật giải round robin với thời lượng 10ms để điều phối CPU.
a, thể hiện bằng biểu đồ gant?
b,tính thời gian chờ Tb của các tiến trình?

như cách giải mình post trên sẽ có kết quả:
TGCTB= (35+13+28)/3=25,33 ms

Biểu đồ Gantt

mình cung có kết quả như vậy nhưng cho minh bổ xung thêm cho đầy đủ nhé
A/ biểu đồ Gantt:
với thời luợng 10ms để điều phối CPU nên các tiến trình chỉ có thể dùng 10ms sau đó phải chuỷên qua tiến trình khác.ở đây là các tiến trình p1,p2,p3


B/ thời gian chờ trung bình của các tiến trình:
Theo như công thức:

T(i)= thờiđiểm kết thúc - thời điểm đến - t/g dùng CPU

Thời gian chờ của P1 = 73-3-35=35 -> T1
Thời gian chờ của P2 = 43-10-20=13 -> T2
Thời gian chờ của P3 = 68-25-15=28 -> T3

P(tb) = (T1+T2+T3)/3
Thời gian chờ trung bình: P(tb)= (35+13+28)/3=76/3=25.33 (ms)

các bạn tham khảo và góp ý nhé

Mình đồng ý với kq của bạn đưa ra, và mình xin giải thích thêm về cái biểu đồ Gantt cho các bạn khác dc hiểu rõ hơn:


1. Thời điểm 3: P1 bắt đầu chạy 10 ms
2. Thời điểm 13: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 10)
3. Thời điểm 23: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 13, P3 đang chờ ở thời điểm 25)
4. Thời điểm 33: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 23, P3 đang chờ ở thời điểm 25 )
5. Thời điểm 43: P3 được chạy trước P1 (vì P3 đang chờ trước ở thời điểm 25 còn P1 là 33 )(P2 hết)
6. Thời điểm 53: P1 được tiếm quyền P3 (vì P1 đang chờ ở thời điểm 33 )
6. Thời điểm 63: P3 được tiếm quyền P1 (vì P3 đang chờ ở thời điểm 53 và chạy hết 5s(68s kết thúc))
7. Cuối cùng chỉ còn P1 sẽ chạy hết thời gian còn lại(5s nữa và kết thúc tại 73s).

Quan trọng là làm ra cái biểu đồ này, còn tính tb thì chỉ cần áp dụng công thức thầy cung cấp là dc.
Chúc các bạn thành công!

Mình cũng bổ sung như sau:
Ta có thời điểm đến của p3 là 25.
Biểu đồ Gantt thì có p1=13 , p2=23 đều nhỏ hơn p3=25(theo đề bài) nhưng p1 =13 nhỏ nhất nên nó được chạy trước. tiếp tục đến p2=23 (> p3=25) . sau cùng là p3.

LeTanDat (I11C) đã viết:

HoiHoangHongVu I11C đã viết:

phamdieptuan (I11C) đã viết:

Tạ Hoàng Tân 102C đã viết:

- Biểu đồ Gantt:

|--P1--|--P1--|--P2--|--P1--|--P3--|--P2--|--P3--|
4-----24------44-----64-----70-----90-----98-----111

Bài này bạn sai ở chỗ P2 rồi , vì thời điểm đến của P3 là 51 nên sau đó phải là P3 chứ ko phải P1 .

Sao lại sai chứ
thời điểm đến của P3 là 51 nhưng P1 đang là 44 kìa, nên P1 phải được ưu tiên trước.

đúng rùi. p1 ưu tiên trước. Ai có bài tập về thuật giải SJFS post lên đi.

Mình nghĩ là mấy bạn nhầm rồi thì phải. Trên diễn đàn cũng có mấy bạn thắc mắc nhưng Thầy đã giải đáp:
Admin
- Nhiều bạn lẫn SJFS với RRS. Hai thuật giải này không liên quan gì đến nhau. Do đó, nếu dùng RRS, tiêu chí duy nhất để bị tiếm quyền sử dụng CPU là hết Thời luợng (Time Quantum).
- Với RRS, khi hết thời lượng, tiến trình hiện hành được đưa vào cuối Ready Queue, còn tiến trình ở đầu danh sách trong Ready Queue sẽ được chọn kế tiếp.
- Em thử làm lại bài theo tinh thần đó xem sao !
Đây là bài tập dùng thuật giải RRS chứ không phải SJFS
Mình cũng đã post một số bài tập về thuật giải SJFS rồi.
Mình xin giải thích lại bài này theo cách hiểu của mình.
- Đầu tiên là P1 chạy với thời lượng là 20ms đến thời gian 24ms thì dừng nhưng vì chưa có tiến trình nào tới nên P1 được chạy tiếp, đến 44ms thì P2 đến, P1 được đưa xuống cuối hàng chờ, P2 chạy cũng với thời lượng 20ms đến 64ms thì P3 đến, P2 được đưa xuống cuối hàng chờ. Cứ như vậy tiếp tục thực hiện.

cho mình hỏi vậy vào thời điểm 64ms P3 đến, P2 đưa xuồng cuôi hàng chờ vậy thì tiến trình P3 hay P1 được chạy vào thời điểm này. mình nghĩ mấy bạn hay lộn ở ngay chỗ này nè bản thân mình cũng thế.

Duongthithanhhuynh (I11C) đã viết:

LeTanDat (I11C) đã viết:

HoiHoangHongVu I11C đã viết:

phamdieptuan (I11C) đã viết:

Tạ Hoàng Tân 102C đã viết:

- Biểu đồ Gantt:

|--P1--|--P1--|--P2--|--P1--|--P3--|--P2--|--P3--|
4-----24------44-----64-----70-----90-----98-----111

Bài này bạn sai ở chỗ P2 rồi , vì thời điểm đến của P3 là 51 nên sau đó phải là P3 chứ ko phải P1 .

Sao lại sai chứ
thời điểm đến của P3 là 51 nhưng P1 đang là 44 kìa, nên P1 phải được ưu tiên trước.

đúng rùi. p1 ưu tiên trước. Ai có bài tập về thuật giải SJFS post lên đi.

Mình nghĩ là mấy bạn nhầm rồi thì phải. Trên diễn đàn cũng có mấy bạn thắc mắc nhưng Thầy đã giải đáp:
Admin
- Nhiều bạn lẫn SJFS với RRS. Hai thuật giải này không liên quan gì đến nhau. Do đó, nếu dùng RRS, tiêu chí duy nhất để bị tiếm quyền sử dụng CPU là hết Thời luợng (Time Quantum).
- Với RRS, khi hết thời lượng, tiến trình hiện hành được đưa vào cuối Ready Queue, còn tiến trình ở đầu danh sách trong Ready Queue sẽ được chọn kế tiếp.
- Em thử làm lại bài theo tinh thần đó xem sao !
Đây là bài tập dùng thuật giải RRS chứ không phải SJFS
Mình cũng đã post một số bài tập về thuật giải SJFS rồi.
Mình xin giải thích lại bài này theo cách hiểu của mình.
- Đầu tiên là P1 chạy với thời lượng là 20ms đến thời gian 24ms thì dừng nhưng vì chưa có tiến trình nào tới nên P1 được chạy tiếp, đến 44ms thì P2 đến, P1 được đưa xuống cuối hàng chờ, P2 chạy cũng với thời lượng 20ms đến 64ms thì P3 đến, P2 được đưa xuống cuối hàng chờ. Cứ như vậy tiếp tục thực hiện.

cho mình hỏi vậy vào thời điểm 64ms P3 đến, P2 đưa xuồng cuôi hàng chờ vậy thì tiến trình P3 hay P1 được chạy vào thời điểm này. mình nghĩ mấy bạn hay lộn ở ngay chỗ này nè bản thân mình cũng thế.

Như Thầy đã thông báo là chỉ ra thi thuật giải RRS, nên các bạn hãy tập trung cho RRS.
Tiêu chí duy nhất để bị tiếm quyền sử dụng CPU là hết Thời luợng.Cứ làm theo cách này :
-Giả sử đầu tiên chạy P1->P2->P3, khi P1 chạy hết thời lượng thì đưa P1 ra sau hàng đợi.
-Tiếp theo sẽ là P2->P3->P1, khi P2 chạy hết thời lượng thì đưa P2 ra sau hàng đợi.
-Tiếp theo sẽ là P3->P1->P2, khi P3 chạy hết thời lượng thì đưa P3 ra sau hàng đợi.
-Tiếp theo sẽ là P1->P2->P3. khi P3 chạy hết thời lượng thì làm lại như trên.
Cứ như thế cho đến hết thời lượng của từng tiến trình.
Ta phải để ý từng thời điểm đến của từng tiến trình.
*Mình xin trả lời câu hỏi của bạn Hỳnh là: vì thời điểm đến của P3 là 51ms nên ngay thời điểm 64ms thì P3 đến và chạy sau đó đưa P3 ra sau.....