Việc định thời CPU xảy ra trong những trường hợp nào

Trong bài viết trước mình đã giới thiệu sơ lược điều phối tiến trình trong hệ điều hành, bài viết này sẽ trình bày về chiến lược một hàng đợi nhiều tiến trình chờ phân phối xử lý. Trong chiến lược một hàng đợi này có 4 thuật toán chính FIFO, SJF ,RR, thuật toán ƯU TIÊN

First In First Out (FIFO)

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 đế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) và chi phí thực hiện thấp nhất (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 ba đ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ình dài, ít bị ngắt thì các tiến trình khác phải chờ đợi lâu hơn.

Ví dụ:

Tiến trình	Thời điểm vào	Thời gian xử lí
P1	0	24
P2	1	3
P3	2	3

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

Tiến trình	P1	P2	P3
Thời điểm	0	24	27/30

Thời gian chờ trung bình: (23+25)/3=16.

Round robin (RR)

Giải thuật định thời luân phiên (round-robin scheduling algorithm-RR) được thiết kế đặc biệt cho hệ thống chia sẻ thời gian. Tương tự như định thời FIFO nhưng sự trưng dụng CPU được thêm vào để chuyển CPU giữa các quá trình. Đơn vị thời gian nhỏ được gọi là định mức thời gian (time quantum) hay phần thời gian (time slice) được định nghĩa. Định mức thời gian thường từ 10 đến 100 mili giây. Hàng đợi sẳn sàng được xem như một hàng đợi vòng. Bộ định thời CPU di chuyển vòng quanh hàng đợi sẳn sàng, cấp phát CPU tới mỗi quá trình có khoảng thời gian tối đa bằng một định mức thời gian. Để cài đặt định thời RR, chúng ta quản lý hàng đợi sẳn sàng như một hàng đợi FIFO của các quá trình. Các quá trình mới được thêm vào đuôi hàng đợi. Bộ định thời CPU chọn quá trình đầu tiên từ hàng đợi sẳn sàng, đặt bộ đếm thời gian để ngắt sau 1 định mức thời gian và gởi tới quá trình. Sau đó, một trong hai trường hợp sẽ xảy ra. Quá trình có 1chu kỳ CPU ít hơn 1 định mức thời gian. Trong trường hợp này, quá trình sẽ tự giải phóng. Sau đó, bộ định thời biểu sẽ xử lý quá trình tiếp theo trong hàng đợi sẳn sàng. Ngược lại, nếu chu kỳ CPU của quá trình đang chạy dài hơn 1 định mức thời gian thì độ đếm thời gian sẽ báo và gây ra một ngắt tới hệ điều hành. Chuyển đổi ngữ cảnh sẽ được thực thi và quá trình được đặt trở lại tại đuôi của hàng đợi sẳn sàng. Sau đó, bộ định thời biểu CPU sẽ chọn quá trình tiếp theo trong hàng đợi sẳn sàng.

• Ưu điểm:

• Các quá trình sẽ được luân phiên cho CPU xữ lý nên thời gian chờ đợi sẽ ít.
• Đối với các quá trình liên quan đến nhập xuất, IO, người dùng thì rất hiệu quả.
• Việc cài đặt không quá phức tạp

• Nhược điểm:

• Thời gian chờ đợi trung bình dưới chính sách RR thường là quá dài.
• Nếu thời gian định mức cho việc xữ lý quá lớn thì RR thành FIFO
• Nếu thời gian quá ngắn so với thời gian xữ lý của một tiến trình trong danh sách hàng đợi thì việc chờ đợi và xữ lý luân phiên sẽ nhiều.
• Qui tắc là định mức thời gian nên dài hơn 80% chu kỳ CPU.

Ví dụ:

Tiến trình	thời điểm vào	thời gian xử lý
P1	0	24
P2	1	3
P3	2	3

Quantum = 4

Thì thứ tự cấp processor cho các tiến trình lần lượt là:

Tiến trình	P1	P2	P3	P1	P1	P1	P1	P1
Thời điểm	0	4	7	10	14	18	22	26

Vậy thời gian chờ đợi trung bình sẽ là: (3+5+6)/3 = 4,67 Như vậy RR có thời gian chờ đợi trung bình nhỏ hơn so với FIFO

Shortest Job First (SJF)

Một tiếp cận khác đối với việc định thời CPU là giải thuật định thời công việc ngắn nhất trước (shortest-job-first-SJF). Giải thuật này gán tới mỗi quá trình chiều dài của chu kỳ CPU tiếp theo cho quá trình sau đó. Khi CPU sẵn dùng, nó được gán tới quá trình có chu kỳ CPU kế tiếp ngắn nhất. Nếu hai quá trình có cùng chiều dài chu kỳ CPU kế tiếp, định thời FIFO được dùng. Chú ý rằng thuật ngữ phù hợp hơn là chu kỳ CPU kế tiếp ngắn nhất (shortest next CPU burst) vì định thời được thực hiện bằng cách xem xét chiều dài của chu kỳ CPU kế tiếp của quá trình hơn là toàn bộ chiều dài của nó. Chúng ta dùng thuật ngữ SJF vì hầu hết mọi người và mọi sách tham khảo tới nguyên lý của loại định thời biểu này như SJF.

• Ưu điểm:

• Giải thuật được xem là tối ưu, thời gian chờ đợi trung bình giảm
• Tận dụng hết năng lực của CPU

• Nhược điểm:

• Cài đặt thuật toán phức tạp, tốn nhiều xữ lý cho quá trình quản lý.
• Mặc dù SJF là tối ưu nhưng nó không thể được cài đặt tại cấp định thời CPU ngắn vì không có cách nào để biết chiều dài chu kỳ CPU tiếp theo.
• Giải thuật SJF có thể trưng dụng hoặc không trưng dụng CPU, dẫn tới giải thuật này có nhiều dị bản khác nhau và sẽ tối ưu hay không tối ưu phụ thuộc vào trưng dụng CPU.

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 thuật toán này cần phải thường xuyên cập nhật thông tin về giời gian đã thực hiện của 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ệc của thuật toán.

• Ưu điểm:

• Thời gian chờ đợi, tồn tại trong hệ thống của mỗi tiến trình đều ngắn
• Thuật toán tối ưu nhất

• Nhược điểm:

• Việc cài đặt thuật toán khá phức tạp
• Cần quản lý chặt chẽ việc điều phối các tiến trình
• Quản lý thời gian đến của mỗi tiến trình

Mr.Nara

Định thời CPU (Scheduling)

Hiểu được:

• Tại sao cần phải định thời
• Các tiêu chí định thời
• Một số giải thuật định thời

Một cách phân loại quá trình

• Chu kỳ CPU-I/O
• CPU-bound process có thời gian sử dụng CPU nhiều hơn thời gian sử dụng I/O
• I/O-bound process dùng phần lớn thời gian để đợi I/O

Vấn đề cần giải quyết

Trong các hệ thống multitasking (Đa nhiệm)

• Tại một thời điểm trong bộ nhớ có nhiều process
• 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 loại và lựa chọn process thực thi sao cho được hiệu quả nhất. Cần có chiến lược định thời CPU

Phân loại định thời

• Định thời dài hạn (long-term scheduling): xác định process nào được chấp nhận vào hệ thống.
• Định thời trung hạn (medium-term scheduling): xác định process nào được đưa vào (swap in), đưa ra khỏi (swap out) bộ nhớ chính. Swap in/out có thể tốn đến vài giây thời gian ⇒ chu kỳ định thời trung hạn có thể là vài phút.
• Định thời ngắn hạn (short-term scheduling): xác định process nào được thực thi tiếp theo.

Định thời dài hạn

• Xác định chương trình nào sẽ được đưa vào hệ thống để thực thi
• Quyết định độ-đa-lập-trình (degree of multiprogramming)
• Nếu càng nhiều process được đưa vào hệ thống
  
  • Khả năng mọi process bị block có xu hướng giảm
  • Sử dụng CPU hiệu quả hơn
  • Mỗi process được phân chia khoảng thời gian sử dụng CPU thấp hơn
• Thường có xu hướng đưa vào một tập lẫn lộn các CPU-bound process và I/O-bound process

Định thời trung hạn

• Quyết định việc đưa process vào bộ nhớ chính, hay ra khỏi bộ nhớ chính
• Phụ thuộc vào yêu cầu quản lý việc đa-lập-trình (multiprogramming)
  
  • Cho phép bộ định thời dài hạn chấp nhận nhiều process hơn số lượng process mà có tổng kích thước được chứa vừa trong bộ nhớ chính
  • Nhưng nếu có quá nhiều process thì sẽ làm tăng việc truy xuất đĩa, do đó cần phải lựa chọn độ-đa-lập- trình cho phù hợp
• Được thực hiện bởi phần mềm quản lý bộ nhớ

Định thời ngắn hạn

• Xác định process nào được thực thi tiếp theo, còn gọi là định thời CPU
• Được kích hoạt khi có một sự kiện có thể dẫn đến khả năng chọn một process để thực thi
• Ngắt thời gian (clock interrupt)
  
  • Ngắt ngoại vi (I/O interrupt)
  • Lời gọi hệ thống (operating system call)
  • Signal

Chương này sẽ tập trung vào định thời ngắn hạn.

Tiêu chí định thời

• Độ lợi CPU (CPU utilization)
  
  • Khoảng thời gian CPU bận, từ 0% đến 100%
  • Cần giữ cho CPU càng bận càng tốt
• Thời gian chờ (waiting time)
  
  • Thời gian chờ trong hàng đợi ready
  • Các process nên được chia sẻ việc sử dụng CPU một cách công bằng (fair share)
• Thông năng (throughput)
  
  • Số lượng process hoàn tất trong một đơn vị thời gian
• Thời gian đáp ứng (response time)
  
  • Thời gian từ lúc có yêu cầu của người dùng (user request) đến khi có đáp ứng đầu tiên (lưu ý: đáp ứng đầu tiên, chứ không phải output)
  • Thường là vấn đề với các I/O-bound process
• Thời gian quay vòng (turnaround time)
  • Thời gian để một process hoàn tất, kể từ lúc vào hệ thống (submission) đến lúc kết thúc (termination)
  • Là một trị đặc trưng cần quan tâm với các process thuộc dạng CPU-bound
• Thời gian quay vòng trung bình (average turnaround time)
• Độ lợi CPU – giữ CPU càng bận càng tốt ( Cao nhất)
• Thông năng – số lượng process kết thúc việc thực thi trong một đơn vị thời gian (Nhiều nhất)
• Turnaround time – thời gian kể từ lúc đưa vào (submission) đến lúc kết thúc (Ngắn nhất)
• Thời gian chờ – thời gian một process chờ trong hàng đợi ready (Ngắn nhất)
• Thời gian đáp ứng – thời gian từ khi đưa yêu cầu đến khi có đáp ứng đầu tiên (Nhanh nhất)

Tất cả các tiêu chí không thể được tối ưu đồng thời vì có một số tiêu chí liên quan nhau

Tiêu chí định thời từ các góc nhìn

Hướng đến người sử dụng (user-oriented)

• Thời gian quay vòng
  
  • Thời gian từ lúc nạp process đến lúc process kết thúc
  • Cần quan tâm với các hệ thống xử lý bó (batch system)
• Thời gian đáp ứng
  
  • Cần quan tâm với các hệ thống giao tiếp (interactive system)

Hướng đến hệ thống (system-oriented)

• Độ lợi CPU (ví du.: (1-P) n )
• Công bằng (fairness)
• Thông năng: số process hoàn tất trong một đơn vị thời gian

Hàm lựa chọn (selection function)
Xác định process nào trong ready queue sẽ được thực thi tiếp theo. Thường theo các tiêu chí như

• w = tổng thời gian đợi trong hệ thống
• e = thời gian đã được phục vụ
• s = tổng thời gian thực thi của process (bao gồm cả trị e )

Chế độ quyết định (decision mode)

• Chọn thời điểm hàm lựa chọn định thời thực thi
• Nonpreemptive : Một process sẽ ở trạng thái running cho đến khi nó bị block hoặc nó kết thúc
• Preemptive: Process đang thực thi có thể bị ngắt và chuyển về trạng thái ready, Tránh trường hợp một process độc chiếm (monopolizing) CPU

Nonpreemption và preemption

• Hàm định thời có thể được thực thi khi có quá trình(1) chuyển từ trạng thái running sang waiting(2) chuyển từ trạng thái running sang ready(3) chuyển từ trạng thái waiting, new sang ready

  (4) kết thúc thực thi

• Định thời nonpreemptive : chỉ thực thi hàm định thời trong trường hợp 1 và 4
• Định thời preemptive : ngoài trường hợp 1 và 4 còn thực thi thêm hàm định thời trong trường hợp 2 hoặc 3 (hoặc cả hai)

Hiện thực cơ chế nào khó hơn? Tại sao?

• Preemptive scheduling hiện thực khó hơn: cần phải duy trì sự nhất quán của:
  
  • Dữ liệu được chia sẻ giữa các process, và quan trọng hơn là
  • Các dữ liệu trong kernel (ví dụ các hàng đợi I/O)
• Ví dụ: trường hợp xảy ra preemption khi kernel đang thực thi một lời gọi hệ thống
  
  • Rất nhiều hệ điều hành chờ cho các lời gọi hàm hệ thống kết thúc rồi mới preemption

Dispatcher ( Bộ điều phối )

• Dispatcher sẽ chuyển quyền điều khiển CPU về cho process được chọn bởi bộ định thời ngắn hạn
• Bao gồm:
  
  • Chuyển ngữ cảnh (sử dụng thông tin ngữ cảnh trong PCB)
  • Chuyển về user mode
  • Nhảy đến vị trí thích hợp (chính là program counter trong PCB) trong chương trình ứng dụng để quá trình tiếp tục thực thi
• Công việc này gây ra phí tổn
  
  • Dispatch latency : thời gian dispatcher cần từ lúc dừng một process đến lúc một process khác tiếp tục chạy