Chương 10 Lập lịch và tải cho BXL

Các process chỉ thực sự hoạt động khi chúng được sử dụng BXL. Việc phân phối BXL phục vụ các process là bài toán quan trọng và phức tạp của HĐH. Trong chương này chúng ta sẽ xem xét các vấn đề liên quan đến việc phân phối BXL cho các process, việc đó gọi là lập lịch (scheduling) cho BXL.

10.1 Các mức lập lịch

Có thể chia thành 3 mức lập lịch khác nhau:

lập lịch mức cao

lập lịch mức giữa và

lập lịch mức thấp

-Lập lịch mức cao, hay lập lịch cho các task: các công cụ ở mức này xác định bài toán (chương trình) nào được đưa vào hệ thống, nghĩa là tạo ra process tương ứng với chương trình đó.

-Lập lịch mức giữa: mức này xác định các process được sử dụng BXL. Bộ lập lịch ở mức này phản ứng với các thay đổi về tải của hệ thống. Nó sẽ dừng hoặc kịch hoạt các process để đảm bảo hệ thống hoạt động bình thường, đạt các thông số kỹ thuật đề ra.

-Lập lịch mức thấp: công cụ ở mức này xác định ready process nào tiếp theo sẽ được quyền sử dụng BXL, do đó thường được gọi là dispacher.

10.2 Các mục tiêu của việc lập lịch.

Cơ chế lập lịch cần đạt được các mục tiêu sau:

đúng đắn, nghĩa là cơ chế lập lịch cần phục vụ các process “công bằng”, tránh tình huống có process bị rơi vào tình trạng chờ vô hạn.

đảm bảo khả năng thông qua lớn nhất, tức là tiến tới phụ vụ số lượng process nhiều nhất có thể trong một đơn vị thời gian.

thời gian phản ứng chấp nhận được với tất cả các process

tối thiểu chi phí, tài nguyên hệ thống.

-cân đối việc sử dụng tài nguyên, cần cố gắng nang cao hiệu suất sử dụng tài nguyên, theo đó cần ưu tiên process sử dung tài nguyên giá thành thấp.

đảm bảo cân đối giữa thời gian trả lời và hiệu suất sử dụng tài nguyên. Cách tốt nhất để giảm thời gian trả lời là có đủ tài nguyên dự trữ để khi có yêu cầu có thể cấp phát ngay lập tức, nhưng điều đó cũng dẫn tới lãng phí tài nguyên.

ngăn ngừa tình huống chờ vô hạn

-cần quan tâm các process đang sử dụng tài nguyên quan trọng, tránh tình trạng process có mức ưu tiên thấp chiếm tài nguyên mà process mức ưu tiên cao hơn cần. -Nếu tài nguyên đó là không chia sẻ thì HĐH cần tạo điều kiện để process giải phóng tài nguyên nhanh nhất.

-Chúng ta thấy rằng nhiều yêu cầu. muck tiêu trái ngược nhau, do đó việc lập lịch cho process là bài toán phức tạp.

10.3 Tiêu chuẩn lập lịch

Để đạt được các mục tiêu ở trên, cơ chế lạp lịch cần hcú ý các yếu tố sau:

-process có thực hiện yêu cầu thao tác I/O không?

-process có sử dụng BXL hết thời gian lượng tử (quantum) hay không

-yêu cầu về thời gian trả lời hệ thống cần đạt được

-mức ưu tiên của các process

-tần suất ngắt missing page fault

-thời gian tổng công process được sử dụng BXL

10.4 Khoảng thời gian lượng tử, ngắt thời gian

-Như ta đã biết, process chỉ thực sự hoạt động khi nó sử dụng BXL. Nếu process là process hệ thống thì lúc đó HĐH thực sự hoạt động. Để tránh tình trạng độ quyền chiếm giữ BXL, HĐH có các cơ chế cho phép lấy lại quyền kiểm soát BXL.

-HĐH thiết lạp đồng hồ hệ thống , xác định khoảng thời gian gọi là lượng tử theo đó sinh ra các tín hiệu ngắt thời gian. Khi đó BXL chuyển sang phục vụ process tiếp theo. Như thế process có thể chiếm BXL đến khi nó tự giải phóng hoặc khi có ngắt tiếp theo. Khi BXL được giải phóng, HĐH sẽ xác định process nào tiếp theo được chiếm BXL.

-Ngắt thời gian giúp hệ thống đảm bảo thời gian trả lời chấp nhận được với tất cả process, tránh tình trạng chờ vô hạn, đồng thưòi cho phép hệ thống phản ứng với các sự kiện phụ thuộc thời gian.

10.5 Mức ưu tiên

-Trong hệ thống, nói chung các process có vai trò quan trọng khác nhau. Mức độ quan trọng của process được thể hiện qua mức ưu tiên (priority) của nó. Mức ưu tiên của process được gán bởi HĐH, và phụ thuộc kiến trúc của HĐH mà mức ưu tiên đó có thể là động hoặc tĩnh, có thể được gán theo các tiêu chuẩn xác định hoặc ngẫu nhiên (trong trường hợp HĐH không phân biệt được proces nào cần mức ưu tiên cao hơn).

-Trong hệ thống sử dụng mức ưu tiên tĩnh, mức ưu tiên của process được gán ngay khi nó được tạo ra và không thay đổi trong suốt quá trình tồn tại của process. Sơ đồ mức ưu tiên tĩnh dễ dàng thiết kế và cài đặt hơn. Tuy nhiên chúng không có khả năng điều chỉnh để phù hợp với sự thay đổi của môi trường.

-Ngày nay trong HĐH đều sử dụng sơ đồ mức ưu tiên động. Theo đó mức ưu tiên của process có thể thay đổi khác với mức ưu tiên khởi tạo ban đầu. Cơ chế này cho phép hệ thống thích nghi với sự thay đổi của môi trường để đạt chỉ tiêu tốt hơn, tuy nhiên nó cũng khó khăn hơn trong xây dựng và cài đặt.

10.6 Lập lịch theo thời gian kết thúc.

Khi áp dụng sơ đồ này, hệ thống sử dụng tất cả khả năng hiện có để một ứng dụng nào đó có thể kết thúc trong thời hạn định trước. Ví dụ trường hợp điều khiển tên lửa, các kết quả tính toán chỉ có ý nghĩa trước thưòi điểm nào đó. Lập lịch theo cơ chế này vấp phải các khó khăn:

-người dùng cần chỉ rõ các tài nguyên cần thiết phục vụ cho ứng dụng, và điều này không phải luôn dễ dàng thực hiện.

-hệ thống một mặt phải thực hiện ứng dụng đúng hạn, mặt khác không được làm ảnh hưởng “quá nhiều” đến các ứng dụng khác.

-rất có thể xảy ra việc tranh chấp tài nguyên giữa các ứng dụng.

-nếu đồng thưòi có nhiều yêu cầu kết thúc các ứng dụng đúng thưòi hạn thì vấn đề lập lịch có thể rất phức tạp.

-việc phức tạp trong lập lịch thường kéo theo chi phí tài nguyên lớn hơn cho nó và làm ảnh hưởng đến cả hệ thống.

10.7 Lập lịch theo nguyên tắc FIFO.

Có lẽ đây là nguyên tắc lập lịch đơn giản nhất. Theo đó BXL phục vụ cá process theo thứ tự trong danh sách các reađy process.

-Sau khi process được quyền sử dụng BXL, nó được thực hiện đến khi kết thúc. Nguyên tắc FIFO là không hoán đổi, nghĩa là BXL không thực hiện phục vụ quay vòng lần lượt các ready process mà phục vụ từng process đến khi kết thúc.

-Nguyên tắc FIFO có tính xác định cao, có thể dự đoán tương đối chính xác thời gian thực hiện các bài toán. Tuy nhiên vì nó là không hoán đổi nên dễ xảy ra trường hợp bài toán quan trọng hơn phải chờ các bài toán khác, đứng trước trong danh sách kết thúc mới được thực hiện. Vì thế hiện nay nguyên tắc này không được áp dụng đơn thuần mà thường kết hợp với các phương pháp khác trong các biện pháp tổ hợp.

10.8 Nguyên tắc quay vòng (Round robin-RR)

-Trong nguyên tắc này, việc điều hành thực hiện các process thực hiện theo nguyên tắc FIFO nhưng có hoán đổi, nghĩa là mỗi process trong mỗi lần được sử dụng BXL không được vượt quá khaỏng thời gian xác định - được gọi là lượng tử (quantum). Nếu nó không tự giải phóng BXL sau khoảng thời gian đó thì HĐH sẽ lấy lại quyền điều khiển BXL và chuyển sang phục vụ process tiếp theo trong danh sách. Process bị tước quyền được đưa vào cuối danh sách.

-Nguyên tắc quay vòng có hiệu quả trong các hệ thống phân chia thời gian và cần đảm bảo thời gian trả lời chấp nhận được với tất cả các process. Chi phí tài nguyên có thể giảm xuống nhờ cơ chế chuyển đổi ngữ cảnh và dung lượng bộ nhớ đủ lớn để đồng thời nạp nhiều ứng dụng.

10.9 Giá trị của lượng tử

-Trong những nguyên tắc như RR ở trên, việc xác định giá trị của lượng tử có ảnh hưởng đến các chỉ số hoạt động của hệ thống. Giá trị đó là lớn hay nhỏ? cố định hay thay đổi? với các process nó có giá trị như nhau hay khác nhau?

-Nếu giá trị đó quá lớn thì có thể lớn hơn cả thời gian thực hiện ứng dụng, nghĩa là trở thành nguyên tắc FIFO. Và như thế không đảm bảo đa nhiệm tốt. Còn nếu giá trị đó quá nhỏ thì chi phí cho việc chuyển đổi ngữ cảnh chiếm phần lớn thời gian và năng lực tính toán của cả hệ thống, chỉ số hoạt động của hệ thống sẽ quá thấp. Quan hệ giữa giá trị của lượng tử và hiệu suất của hệ thống được biểu diễn qua đồ thị sau

-Có thể thấy rằng giá trị tối ưu không phải cố định, nó thay đổi theo từng hệ thống và theo tải của hệ thống, nó cũng có thể khác nhau với từng process.

10.10 Lập lịch theo nguyên tắc SJF (Shortes Job First)

-Nguyên tắc SJF là nguyên tắc không hoán đổi, theo đó bài toán có thời gian thực hiện ngắn nhất theo dự đoán sẽ được thực hiện trước.

Nguyên tắc này ưu tiên các bài toán nhỏ, vì nói chung việc tạo điều kiện cho các bài toán nhỏ thực hiện và kết thúc dễ dàng hơn. Từ đó hàng đợi các bài toán giảm đi nhanh chóng. Tuy nhiên nguyên tắc này không tính đến mức ưu tiên, độ quan trọng của bài toán.

-Theo nguyên tắc này bài toán nhỏ được thực hiện trước do đó hàng đợi nhanh chóng giảm đi và thời gian chờ trung bình giảm. Tuy nhiên việc xác định chính xác thời gian thực hiện bài toán là việc khó khăn và nhiều trường hợp không thể dự đoán chính xác được.

10.11 Lập lịch theo nguyên tắc SRT

-Nguyên tắc SRT cũng tương tự nguyên tắc SJF, nhưng SRT là có hoán đổi. Theo nguyên tắc này, process được đánh giá là có khoảng thời gian còn lại đến khi kết thúc là ngắn nhất hoặc process mới được tạo sẽ được ưu tiên.

-Process được đưa vào thực hiện sẽ được chạy đến khi nó kết thúc, hoặc khi có một process mới được đưa vào hệ thống mà có thời gian hoạt động nhỏ hơn thời gian còn lại của process đang được thực hiện.

-Để thực hiện nguyên tắc này, chúng ta lại gặp phải vấn đề dự đoán chính xác thời gian còn lại của process. Nguyên tắc này đòi hỏi chi phí tính toán lớn hơn so với nguyên tắc SJF. Cơ chế SRT đòi hỏi luôn phải theo dõi thời gian thực hiện của các bài toán để có thể xử lý các tình huống ngắt. Khi số lượng các process không lớn, process có thể được thực hiện ngay, nhưng nếu số lượng bài toán

-Theo nguyên tắc SRT, hệ thống cần ghi lại thời gian thực hiện của các process và điều này làm tăng chi phí tính toán. Về lý thuyết nguyên tắc SRT đảm bảo thời gian chờ cực tiểu, tuy nhiên do thao tác chuyển đổi ngữ cảnh mà điều đó không phải luôn đúng.

-Giả sử process đang được thực hiện đến lúc gần kết thúc thì xuất hiện process mới có thời gian thực hiện ngắn hơn. Câu hỏi đặt ra là có ngắt process đang thực hiện hay không? vì có thể thời gian thực hiện thao tác chuyển đổi ngữ cảnh còn lớn hơn bản thân thời gian thực hiện process. Để khắc phục nhược điểm này, trong một số hệ thống người ta đặt ra ngưỡng thời gian, theo đó thời gian thực hiện process hiện tại nhỏ hơn ngưỡng đó thì sẽ không thực hiện thao tác chuyển đổi ngữ cảnh.

-Một trường hợp khác cần để ý, đó là khi bài toán mới xuất hiện có thời gian thực hiện dự đoán xấp xỉ thời gian còn lại của bài toán hiện tại, khi đó nếu thực hiện chuyển đổi ngữ cảnh thì chi phí lớn hơn lợi ích thu được.

-Chúng ta phân tích các trường hợp trên với mục đích cho thấy khi thiết kế hệ thống cần phải xem xét kỹ hiệu quả thu được với chi phí bỏ ra.

10.12 Lập lịch theo nguyên tắc HRN

Brinch Hansen đã đề xuất nguyên tắc HRN (Highest response Ratio Next) để khắc phục một số nhược điểm trong nguyên tắc SJF, đặc biệt sự quá ưu tiên các bài toán có thời gian thực hiện ngắn. HRN là nguyên tắc không hoán đổi và mức ưu tiên động, theo đó mức ưu tiene của process phụ thuộc không chỉ thời gian cần thực hiện nó mà còn cả thời gian nó phải chờ được phục vụ. Công thức tính toán như sau

dễ thấy mức ưu tiên càng cao khi thời gian thực hiện càng ngắn hoặc khi thời gian chờ càng lớn.

10.13 Hàng đợi nhiều mức với mối liên hệ ngược (call back)

-Khi process chiếm BXL, nói chung ta khó có thể dự đoán trước về hành vi của nó – thời gian nó cần BXL. Process có thể chỉ cần BXL trong khoảng thời gian ngắn rồi thực hiện yêu cầu vào/ra, hoặc nó cũng có thể cần BXL tính toán trong khoảng thời gian dài nếu HĐH không lấy lại quyền điều khiển. Do đó cơ chế lập lịch cần

+ chú ý đến các bài toán ngắn

+ chú ý các bài toán thường thực hiện thao tác vào/ra để sử dụng thiết bị vào/ra hiệu quả

+ nhanh chóng xác định đặc điểm của bài toán để có thể lập lịch tối ưu.

-Cơ chế hàng đợi nhiều mức với mối liên hệ ngược (hình10.14) là cơ chế cho phép đạt được các yêu cầu trên. Khi process mới được khởi tạo, nó được đưa vào cuối hàng đợi mức trên. Nó dần dịch chuyển lên phía đầu hàng đợi do các process khác lần lượt được sử dụng BXL. Khi process đang chiếm BXL kết thúc, hoặc thực hiện yêu cầu vào/ra, hoặc hết thời gian lượng tử hoặc có ngắt,.. BXL được giải phóng và đến process tiếp theo trong hàng đợi được sử dụng BXL.

Nếu process chưa kết thúc và hết thời gian lượng tử, nó bị tước quyền sử dụng BXL và được đưa vào cuối hàng đợi mức thấp hơn. Nếu nó thực hiện yêu cầu vào/ra thì nó sẽ được chuyển xuống cuối hàng đợi cũng mức. Nó sẽ được quyền sử dụng BXL nếu nó chuyển dịch đến đầu hàng đợi và không còn process nào trong các hàng đợi mức trên. Thường trong hệ thống có một vài hàng đợi mức thấp nhất, và hoạt động theo nguyên tắc quay vòng, theo đó các process được thực hiện quay vòng đến khi nó kết thúc.

Trong nhiều hệ thống, người ta thiết kế để lượng tử đối với hàng đợi mức thấp hơn có giá trị lớn hơn. Nhờ đó process chờ càng lâu thì được chiếm BXL lâu hơn. Process ở đầu hàng đợi chỉ được chiếm BXL nếu tất cả các hàng đợi mức trên là rỗng. Việc thực hiện process có thể bị ngắt nếu xuất hiện process mới thuộc hàng đợi mức trên.

-Đến đây ta phân tích nguyên tắc này, đối chiếu với các yêu cầu trên. Cơ chế cần ưu tiên các process thường xuyên thực hiện thao tác vào/ra để đảm bảo hiệu suất sử dụng thiết bị và thời gian trả lời yêu cầu là ngắn. Lượng tử được chọn đủ để process thực hiện xong tính toán và yêu cầu thao tác vào/ra trước khi kết thúc lượng tử. Process được đưa vào cuối hàng đợi và vẫn được gán mức ưu tiên cao. Process sẽ nhanh chóng dịch chuyển lên đầu hàng đợi mức trên và được phục vụ.

-Còn với các process thực hiện tính toán nhiều, đầu tiên process được đưa vào hàng đợi mức trên. Process nhanh chóng dịch chuyển lên đầu hàng đợi và được phục vụ. Sau khi kết thúc lượng tử, nó được đưa vào hàng đợi mức đưới với mức ưu tiên thấp hơn. Như thế cơ chế này ưu tiên các process thường thực hiện thao tác vào/ra. Sau đó, khi không còn process ở hàngđoịư mức trên, process được phục vụ lần tiếp theo và khi kết thúc lượng tử, nó được chuyển xuống hàng đợi mức thấp hơn. Cuối cùng nó chuyển xuống hàng đợi thấp nhất và được phục vụ quay vòng đến khi kết thúc.

-Cơ chế hàng đợi nhiều mức với liên hệ ngược là cơ chế tốt cho phép phân tách các process theo thời gian sử dụng BXL. Hệ thống có thể ghi lại mức hàng đợi của process, như thế khi process được đưa ngược lại hàng đợi, nó có thể được đưa vào hàng đợi cùng mức.

-Ta có thể thấy rằng nếu process đã nằm ở hàng đợi mức thấp nhất thì hệ thống không thể phản ứng với thay đổi hành vi của process ví dụ như process chuyển từ pha tính toán sang pha thực hiện thao tác vào/ra. Vấn đề có thể được giải quyết nếu hệ thống ghi lại thời gian các lần process chiếm BXL, nhờ đó khi chuyển pha, hệ thống có thể nhanh chóng phát hiện sự kiện đó và đưa process vào hàng đợi thích hợp. Hoặc dùng phương án khác, theo đó mỗi khi process tự giải phóng BXL trước khi hết lượng tử, hệ thống lại tăng mức ưu tiên cho process.

-Cơ chế này là cơ chế thích nghi – có thể phản ứng với các thay đổi trong hành vi của process. Thông thường cơ chế thích nghi đòi hỏi chi phí lớn hơn, nhưng nó giúp hệ thống linh động hơn, tự điều chỉnh hoạt động và lợi ích đạt được nói chung cân bằng được với chi phí.