-
Thông tin
-
Hỏi đáp
Lập lịch CPU | Đại học Giao thông vận tải TP.HCM
Lập lịch CPU | Đại học Giao thông vận tải TP.HCM được biên soạn dưới dạng file PDF cho các bạn sinh viên tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị thật tốt cho các kì thi sắp tới. Mời bạn đọc đón xem!
Môn: Công nghệ phần mềm (CNPM) 2 tài liệu
Trường: Đại học Giao thông vận tải 269 tài liệu
Thông tin:
Tác giả:
Preview text:
TRƯỜNG ĐẠI HỌC GIAO THÔNG VẬN TẢI TP. HỒ CHÍ MINH
KHOA CÔNG NGHỆ THÔNG TIN
BÀI TIỂU LUẬN HỆ ĐIỀU HÀNH
ĐỀ TÀI: LẬP LỊCH CPU
NHÓM HỌC PHẦN: 010412500105
GIẢNG VIÊN HƯỚNG DẪN: VÕ TẤN SANG
NHÓM SINH VIÊN: NHÓM 5
1. TRẦN THỊ NGỌC ÁNH 2. QUANG KIM HẰNG 3. CAO MINH HIẾU
4. NGUYỄN QUYẾT GIANG SƠN 5. NGUYỄN VĂN NHI 6. NGÔ ANH QUÂN
Tp. Hồ Chí Minh, ngày tháng 03 năm 2024 MỤC LỤC
MỤC LỤC ........................................................................................................................ 1
DANH MỤC CÁC TỪ VIẾT TẮT .................................................................................. 2
LỜI MỞ ĐẦU .................................................................................................................. 3
CHƯƠNG 5: LẬP LỊCH CPU ......................................................................................... 4
5.1 Khái Niệm Cơ Bản ..................................................................................................... 4
5.1.1 Cpu-I/O Burst Cycle ............................................................................................ 5
5.1.2 Cpu Scheduler (Bộ Lập Lịch Cpu) ...................................................................... 7
5.1.3 Preemptive And Nonpreemptive Scheduling (Lập Kế Trưng Dụng Và Không
Trưng Dụng) ................................................................................................................. 8
5.1.4 Dispatcher (Phân Phát) ..................................................................................... 10
5.1.4.1 Vai trò của Dispatcher: ................................................................................ 11
5.1.4.2 Cách hoạt động của Dispatcher: .................................................................. 11
5.1.4.3 Ý nghĩa và ứng dụng: .................................................................................. 11
5.1.4.4 Phát triển và công nghệ: .............................................................................. 11
5.2 Tiêu Chí Lập Kế Hoạch ........................................................................................... 12
5.3 Thuật Toán Lập Lịch ................................................................................................ 13
5.3.1 First-Come, First-Served (Fcfs) ........................................................................ 13
5.3.2 Shortest-Job-First (Sjf) ...................................................................................... 15
5.3.3 Round Robin (Rr) ............................................................................................... 18
5.3.4 Lập Lịch Ưu Tiên ............................................................................................... 20
5.3.5 Multilevel Queue Scheduling ............................................................................. 22
5.3.6 Multileveling Feedback Queue Cheduling ........................................................ 23
KẾT LUẬN .................................................................................................................... 25
TÀI LIỆU THAM KHẢO .............................................................................................. 26
PHỤ LỤC ....................................................................................................................... 27 1
DANH MỤC CÁC TỪ VIẾT TẮT 1. FIFO: First-In, First-Out 2. PCB: Process Control Block
3. SRTF: Shortest Remaining Time First
4. FCFS: First-Come, First-Served 5. SJF: Shortest-Job-First 6. RR:Round-Robin 2 LỜI MỞ ĐẦU
Trong môi trường máy tính đa nhiệm hiện đại, việc quản lý và phân phối tài nguyên CPU
không chỉ là một thách thức đầy phức tạp mà còn là một yếu tố quan trọng để đảm bảo
hiệu suất và công bằng trong việc phân chia tài nguyên của hệ thống. Lập lịch CPU -
quyết định xác định tiến trình nào được thực thi và khi nào - là một phần không thể thiếu
trong thiết kế hệ thống điều hành, từ việc đơn giản hóa việc sử dụng một lõi CPU đến
việc quản lý nhiều lõi trong các hệ thống đa nhân.
Bài báo cáo sẽ đi sâu vào khái niệm cơ bản của việc lập lịch CPU, các chu kỳ quan trọng
như CPU-I/O burst, vai trò của CPU scheduler, sự khác biệt giữa lập lịch trưng dụng và
không trưng dụng, cũng như vai trò và cách hoạt động của dispatcher. Chúng ta cũng sẽ
khám phá một loạt các thuật toán lập lịch CPU, từ những thuật toán đơn giản như First-
Come, First-Served (FCFS) cho đến những phương pháp phức tạp như Multilevel
Feedback Queue Scheduling, mỗi cái mang lại một cách tiếp cận khác nhau để quản lý
các tiến trình và tối ưu hóa hiệu suất của hệ thống.
Ngoài ra, chúng ta cũng sẽ tìm hiểu về các tiêu chí đánh giá hiệu suất của các thuật toán
lập lịch, từ thời gian đáp ứng đến thời gian chờ đợi của các tiến trình. Điều này sẽ giúp
ta hiểu rõ hơn về cách các thuật toán lập lịch đóng vai trò quan trọng trong việc tối ưu
hóa sử dụng tài nguyên CPU và giảm thời gian chờ đợi của các tiến trình, đồng thời cải
thiện hiệu suất tổng thể của hệ thống máy tính.
Với sự hiểu biết về các khái niệm cơ bản và tiêu chí đánh giá này, chúng ta sẽ có cái nhìn
tổng quan về cách hoạt động của việc lập lịch CPU và cách áp dụng chúng trong môi
trường máy tính thực tế để đạt được hiệu suất cao nhất. 3
CHƯƠNG 5: LẬP LỊCH CPU
5.1 Khái Niệm Cơ Bản
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, trong một hệ thống đơn bộ xử lý (single-processor system) chỉ có một
tiến trình được thực thi; những tiến trình khác phải chờ cho đến khi bộ xử lý rảnh hoặc tái lập lịch lại.
1. 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
2. Phải có chiến lược định thời CPU, tức như thế nào để đưa một process vào thực thi.
3. Lập lịch CPU là một chức năng cốt lõi của hệ điều hành đa chương trình, giúp tối
ưu hóa sử dụng CPU. Khi chạy nhiều chương trình cùng lúc, CPU có thể được sử
dụng hiệu quả hơn so với chỉ chạy một chương trình.
4. Chu kỳ sử dụng CPU-I/O: Sự thực hiện tiến trình gồm một chu kỳ thực hiện của
CPU và chờ vào-ra, sau khi chu kỳ CPU burst kết thúc, chương trình sẽ chuyển sang chờ I/O.
5. Sự phân phối sử dụng CPU giúp lựa chọn giải thuật lập lịch CPU
Sự thành công của việc lập lịch CPU phụ thuộc vào một thuộc tính quan sát được của
các tiến trình: quá trình thực thi bao gồm một chu kỳ của CPU và thời gian chờ I/O.
Các tiến trình luân phiên giữa hai trạng thái này. Quá trình thực thi bắt đầu với một
CPU burst (chu kỳ thực thi CPU). Sau đó là một I/O burst (chu kỳ chờ I/O), tiếp theo
là một CPU burst khác, sau đó là một I/O burst khác, và cứ như vậy. Cuối cùng, CPU
burst cuối cùng kết thúc với một yêu cầu của hệ thống để kết thúc thực thi. 4
Hình 5.1 Trình tự xen kẽ của các đợt CPU và I/O
5.1.1 Cpu-I/O Burst Cycle
Chu kỳ CPU-I/O burst đóng vai trò quan trọng trong việc quản lý thời gian sử dụng CPU
của một tiến trình trong hệ điều hành. Trong mô hình chu kỳ này, một tiến trình sẽ trải
qua các giai đoạn burst CPU (CPU burst) và burst I/O (I/O burst).
5.1.1.1 Burst CPU (CPU burst):
Burst CPU là thời gian mà một tiến trình sử dụng CPU để thực hiện công việc tính toán của mình.
Trong giai đoạn này, tiến trình thực hiện các thao tác tính toán như thực hiện các phép
toán, thực hiện các hàm logic, và các công việc khác tương tự.
Chiều dài của Burst CPU cho mỗi tiến trình có thể khác nhau tùy thuộc vào loại công
việc mà tiến trình cần thực hiện.
5.1.1.2 Burst I/O (I/O burst): 5
Burst I/O là thời gian mà một tiến trình thực hiện các hoạt động liên quan đến việc giao
tiếp với thiết bị ngoại vi, như việc đọc hoặc ghi dữ liệu từ ổ đĩa cứng, in hoặc ra các
thông điệp trên màn hình.
Trong giai đoạn này, việc sử dụng CPU của tiến trình không cần thiết vì tiến trình đang
chờ dữ liệu từ các thiết bị I/O.
Khi một tiến trình hoặc job được thực thi trên hệ thống, việc lập lịch lựa chọn đúng các
loại burst (CPU hoặc I/O) để thực hiện có ảnh hưởng lớn đến hiệu suất của hệ thống.
Việc chuyển đổi giữa CPU bursts và I/O bursts trong thuật toán lập lịch như Round
Robin, FCFS, hoặc Shortest Job Next giúp cải thiện hiệu suất hệ thống.
Việc lập lịch phân công thời gian sử dụng CPU hiệu quả cho mỗi tiến trình dựa trên các
burst của chúng sẽ giúp tối ưu hóa việc sử dụng tài nguyên hệ thống và giảm thời gian
chờ đợi của các tiến trình. Điều này cũng giúp hệ thống hóa hoạt động ổn định và linh
hoạt hơn trong việc xử lý nhiều tiến trình cùng một lúc
Thời gian của các CPU burst đã được đo lường một cách rộng rãi. Mặc dù chúng thay
đổi rất lớn từ quá trình này sang quá trình khác và từ máy tính này sang máy tính khác,
chúng có xu hướng có một đường cong tần số tương tự như được hiển thị trong hình 5.2:
Hình 5.2 Biểu đồ về khoảng thời gian sử dụng CPU 6
Đường cong này thường được đặc trưng là một phân phối mũ (Trong Lý thuyết xác
suất và thống kê, phân phối mũ là một lớp của các phân bố xác suất liên tục) hoặc siêu
mũ, với một số lượng lớn các CPU burst ngắn và một số lượng nhỏ các CPU burst dài.
Một chương trình I/O-bound (chương trình chờ I/O) thường có nhiều CPU burst ngắn.
Một chương trình CPU-bound (chương trình tập trung vào CPU) có thể có một số lượng
ít các CPU burst dài. Phân phối này có thể quan trọng khi triển khai một thuật toán lập lịch CPU. Giải thích thuật ngữ:
I/O-bound program: Chương trình chờ I/O, là chương trình mà thời gian chờ I/O
chiếm phần lớn thời gian thực thi của nó.
CPU-bound program: Chương trình tập trung vào CPU, là chương trình mà thời
gian thực thi CPU chiếm phần lớn thời gian thực thi của nó.
5.1.2 Cpu Scheduler (Bộ Lập Lịch CPU)
Mỗi khi CPU trở thành trạng thái rảnh rỗi, hệ điều hành phải chọn trong các tiến trình
sẵn sàng thực hiện trong bộ nhớ (ready queue) và phân phối CPU cho một trong số đó.
Tiến trình được thực hiện bởi trình lập lịch ngắn kỳ ( short-term scheduler, CPU scheduler)
Các quyết định lập lịch CPU có thể xảy ra khi một tiến trình:
1. Chuyển từ trạng thái chạy sang trạng thái chờ (vd: I/O request)
2. Chuyển từ trạng thái chạy sang trạng thái sẵn sàng (vd: khi một ngắt xuất hiện)
3.Chuyển từ trạng thái đợi sang trạng thái sẵn sàng (vd: I/O hoàn thành) 4. Kết thúc
Lưu ý rằng hàng đợi sẵn sàng không nhất thiết phải là một hàng đợi theo nguyên tắc
vào trước, ra sau (FIFO). Như chúng ta sẽ thấy khi xem xét các thuật toán lập lịch 7
khác nhau, một hàng đợi sẵn sàng có thể được thực hiện như một hàng đợi FIFO, một
hàng đợi ưu tiên, một cây, hoặc đơn giản là một danh sách liên kết không theo thứ tự.
Tuy nhiên, về mặt khái niệm, tất cả các quá trình trong hàng đợi sẵn sàng đều được
xếp hàng đợi chờ một cơ hội để chạy trên CPU. Các bản ghi trong các hàng đợi thường
là các khối điều khiển quá trình (PCBs) của các quá trình. Giải thích thuật ngữ:
FIFO Queue: Hàng đợi FIFO (First-In, First-Out) là một loại hàng đợi trong đó
phần tử được thêm vào trước sẽ được lấy ra trước.
Process Control Block (PCB): PCB là một cấu trúc dữ liệu chứa thông tin quan
trọng về một tiến trình, bao gồm trạng thái tiến trình, thông tin về bộ nhớ, thanh ghi, v.v.
5.1.3 Preemptive And Nonpreemptive Scheduling (Lập Kế Trưng Dụng Và Không Trưng Dụng)
Lập lịch trưng dụng (preemptive) và không trưng dụng (nonpreemptive) là hai phương
pháp quản lý và quyết định thời điểm lập lịch cho các tiến trình trong hệ thống máy tính.
5.1.3.1 Trưng dụng (Preemptive)
Khi ở trạng thái running, process có thể bị ngắt nửa chừng và chuyển về trạng thái ready
bởi hệ điều hành để chuyển sang thực thi một tiến trình khác có ưu tiên cao hơn.
Chi phí cao hơn non-preemptive nhưng đánh đổi lại bằng thời gian xử lý nhanh chóng
hơn, giảm thời gian đáp ứng của hệ thống và tăng hiệu suất tổng thể vì không có trường
hợp một process độc chiếm CPU quá lâu
Hầu như tất cả các hệ điều hành hiện đại bao gồm Windows, MacOS, Linux và UNIX
đều sử dụng thuật toán lập lịch Preemptive
5.1.3.2 Không trưng dụng (Non-preemptive) 8
Khi ở trạng thái running, process sẽ thực thi cho đến khi kết thúc hoặc bị blocked do yêu cầu I/O
Khi CPU được trao cho quá trình nó không nhường cho đến khi nó kết thúc chu kỳ xử lý của nó
Lập lịch không trưng dụng (Non-preemptive) cho phép tiến trình hoàn thành công việc
của mình mà không bị ngắt giữa chừng, tuy nhiên nó sẽ sử dụng CPU cho đến khi nó
giải phóng CPU bằng cách kết thúc hoặc chuyển sang trạng thái chờ có thể làm tăng thời
gian chờ đợi của các tiến trình ưu tiên cao hơn.
Ví dụ về cơ chế lập lịch không cưỡng đoạt là First-Come First-Served (FCFS), trong đó
tiến trình nào đến trước sẽ được xử lý trước.
Các quyết định lập lịch CPU có thể diễn ra trong bốn trường hợp sau:
1. Khi một tiến trình chuyển từ trạng thái đang chạy sang trạng thái chờ (ví dụ: yêu cầu
I/O, hay chờ kết thúc của một trong những quá trình con)
2. Khi một tiến trình chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng (ví dụ: khi xảy ra ngắt)
3. Khi một tiến trình chuyển từ trạng thái chờ sang trạng thái sẵn sàng (ví dụ: khi hoàn thành I/O)
4. Khi một tiến trình kết thúc
Lập lịch (1) và (4) không được trưng dụng trước (Nonpreemptive):
Không có sự lựa chọn: phải chọn 1 tiến trình mới để thực hiện.
Khi 1 tiến trình được phân phối CPU, nó sẽ sử dụng CPU cho đến khi nó giải phóng
CPU bằng cách kết thúc hoặc chuyển sang trạng thái chờ.
Lập lịch (2) và (3) được ưu tiên trước ( Preemptive): 9
Khi (2): tiến trình giải phóng CPU -> cần phải chọn tiến trình kế tiếp
Khi (3): tiến trình có thể đẩy tiến trình khác để dành quyền điều khiển CPU
Trong các tình huống khác nhau, việc chuyển đổi giữa các trạng thái của tiến trình như
thực thi, chờ đợi, hoặc hoàn thành sẽ dựa vào thuật toán lập lịch được áp dụng. Các thuật
toán lập lịch sẽ quy định cách tiến trình được chuyển đổi giữa các trạng thái này dựa trên
các tiêu chí như ưu tiên, thời gian đợi, và tài nguyên sẵn có. Việc lựa chọn và cài đặt
đúng thuật toán lập lịch sẽ giúp tối ưu hóa hiệu suất và hiệu quả của hệ thống máy tính.
5.1.4 Dispatcher (Phân Phát)
Một thành phần khác liên quan đến chức năng lập lịch CPU là bộ phân phát .
Bộ phân phát là mô-đun cung cấp quyền kiểm soát lõi của CPU cho quy trình
được lựa chọn bởi bộ lập lịch CPU. Bao gồm:
1. Chuyển ngữ cảnh (sử dụng thông tin ngữ cảnh trong PCB)
2. Chuyển chế độ người dùng
3. Nhảy đến vị trí thích hợp trong chương trình ứng dụng để khởi động lại chương
trình (chính là program counter trong PCB)
Hình 5.3 Vai trò của người điều phối 10
Dispatch latency: thời gian mà dispatcher dừng một process và khởi động một process khác
5.1.4.1 Vai trò của Dispatcher:
Dispatcher là thành phần quan trọng của trình điều vận, nhiệm vụ chính của nó là chuyển
đổi quyền điều khiển từ tiến trình này sang tiến trình khác một cách hiệu quả.
Thực hiện việc chọn lựa tiến trình tiếp theo để thực thi dựa trên các tiêu chí như ưu tiên,
thời gian chờ đợi, và tài nguyên cần thiết.
5.1.4.2 Cách hoạt động của Dispatcher:
Khi một tiến trình cần thực thi hoặc bị gián đoạn, Dispatcher sẽ quyết định tiến trình kế
tiếp nào sẽ được thực thi.
Với việc sử dụng các thuật toán lập lịch thông minh, Dispatcher có thể tối ưu hóa việc
chuyển đổi giữa các tiến trình để đảm bảo hiệu suất cao nhất cho hệ thống.
5.1.4.3 Ý nghĩa và ứng dụng:
Dispatcher giúp tối ưu hóa sử dụng tài nguyên hệ thống và cải thiện hiệu suất chung của máy tính.
Trong môi trường đa nhiệm, Dispatcher đóng vai trò quan trọng trong việc quản lý việc
chuyển đổi giữa các tiến trình một cách linh hoạt.
5.1.4.4 Phát triển và công nghệ:
Công nghệ tiến bộ và các thuật toán lập lịch thông minh đang được áp dụng để cải thiện
khả năng quản lý và phân phối các tiến trình.
Việc nâng cao khả năng quyết định và hiệu quả của Dispatcher sẽ tiếp tục đóng vai trò
quan trọng trong những hệ thống máy tính tương lai.
Dispatcher không chỉ là một phần của trình điều vận, mà còn là người quyết định quan
trọng đằng sau việc điều phối các tiến trình và tài nguyên trong hệ thống máy tính. 11
5.2 Tiêu Chí Lập Kế Hoạch
Các giải thuật định thời khác nhau có các thuộc tính khác nhau và có xu hướng thiên vị
cho một loại tiến trình hơn một tiến trình khác. Trong việc chọn giải thuật nào sử dụng
trong trường hợp nào, chúng ta phải xét các thuộc tính của các giải thuật khác nhau.
Nhiều tiêu chuẩn được đề nghị để so sánh các giải thuật lập lịch. Những tiêu chuẩn được
dùng để so sánh có thể tạo sự khác biệt quan trọng trong việc xác định giải thuật tốt nhất. Các tiêu chuẩn gồm: 1.
Thời gian đáp ứng (Response time): khoảng thời gian process nhận yêu cầu đến
khi yêu cầu đầu tiên được đáp ứng (time- sharing, interactive system) → tối thiểu 2.
Thời gian quay vòng (hoàn thành) (Turnaround time): khoảng thời gian từ lúc
một process được nạp vào hệ thống đến khi process đó kết thúc → tối thiểu 3.
Thời gian chờ (Waiting time): tổng thời gian một process đợi trong ready queue → tối thiểu 4.
Tận dụng CPU (processor utilization): định thời sao cho CPU càng bận càng tốt → tối đa 5.
Thông lượng (throughput): số process hoàn tất công việc trong một đơn vị thời gian → tối đa
Đánh giá các yếu tố như CPU utilization, throughput, turnaround time, waiting time và
response time là rất quan trọng trong việc đánh giá hiệu suất của thuật toán lập lịch. Dưới
đây là một số cách tối ưu hóa việc sử dụng CPU và giảm thời gian chờ đợi của các tiến trình: 6.
Tối ưu hóa sử dụng CPU:
Sử dụng thuật toán lập lịch thông minh như Round Robin, Shortest Job Next (SJN) để
phân chia thời gian CPU một cách công bằng giữa các tiến trình. 12
Áp dụng kỹ thuật dùng lịch định thời (deadline scheduling) để ưu tiên các tiến trình có
deadline gần nhất, giúp đảm bảo thời gian hoàn thành các công việc quan trọng.
Phát hiện và ngăn chặn các tiến trình "ăn cắp" tài nguyên CPU quá lâu (tác động đến
CPU utilization) bằng cách thiết lập cơ chế ưu tiên và giới hạn thời gian thực thi. 7.
Giảm thời gian chờ đợi của các tiến trình:
Sử dụng thuật toán lập lịch có khả năng giảm thời gian chờ đợi như SRTF, Priority
Scheduling để ưu tiên các tiến trình quan trọng hoặc có thời gian chờ đợi ngắn nhất.
Áp dụng các chiến lược tối ưu hóa tài nguyên như Preemptive Scheduling để cho phép
các tiến trình ưu tiên cao hơn giành CPU khi cần thiết.
Chia nhỏ các tiến trình lớn thành các phần nhỏ hơn để tăng tính linh hoạt và giảm thời
gian chờ đợi thông qua Parallel Processing.
Bằng cách kết hợp các phương pháp trên và sử dụng các thuật toán lập lịch phù hợp,
chúng ta có thể tối ưu hóa việc sử dụng CPU và giảm thời gian chờ đợi của các tiến trình,
từ đó cải thiện hiệu suất và hiệu quả của hệ thống máy tính.
5.3 Thuật Toán Lập Lịch
5.3.1 First-Come, First-Served (FCFS)
Đây là thuật toán lập lịch đơn giản nhất, và được quản lí bằng hàng đợi FIFO. Khi một
tiến trình vào hàng đợi, PCB của nó được liên kết vào cuối hàng đợi. Quá trình đang
chạy sau đó được loại bỏ khỏi hàng đợi.
Mặt tiêu cực của FCFS là thời gian chờ đợi trung bình thường khá dài. Xem xét một tập
hợp các quá trình với thời gian burst của CPU được cho trong mili giây: 13
Nếu các quá trình đến theo thứ tự P1, P2, P3 và được phục vụ theo thứ tự FCFS, chúng
ta có kết quả như trong biểu đồ Gantt đầu tiên, với thời gian chờ đợi P1 = 0; P2 = 24;
P3 = 27. Như vậy, thời gian chờ đợi trung bình là (0 + 24 + 27) / 3 = 17 ms.
Tuy nhiên, nếu các quá trình đến theo thứ tự P2, P3, P1, kết quả sẽ như trong biểu đồ
Gantt thứ hai, với thời gian chờ đợi P1 = 6; P2 = 0; P3 = 3, trung bình giảm xuống còn (6 + 0 + 3) / 3 = 3 ms.
Trong một hệ thống sử dụng thuật toán FCFS, nếu có một quá trình đòi hỏi nhiều CPU
và nhiều quá trình chỉ đợi I/O, có thể xảy ra hiện tượng "convoy effect". Điều này xảy
ra khi quá trình CPU-bound (có nhu cầu CPU cao) chiếm CPU, khiến các quá trình I/O-
bound (có nhu cầu I/O cao) phải đợi. Khi quá trình CPU-bound kết thúc và chuyển sang
I/O, các quá trình I/O-bound sẽ nhanh chóng hoàn thành và quay lại hàng đợi I/O. Trong
khi đó, CPU lại trống, nhưng quá trình CPU-bound sẽ lấy CPU tiếp, khiến các quá trình
I/O-bound phải đợi lâu hơn. Điều này dẫn đến sử dụng CPU và thiết bị I/O không hiệu
quả, vì CPU thường rảnh rỗi trong khi các thiết bị I/O không được sử dụng.
Thuật toán lập lịch FPFS là không chiếm đoạt, nghĩa là một khi CPU được phân phối
cho một quá trình, nó sẽ giữ cho đến khi nó tự nguyện giải phóng, hoặc bằng cách kết
thúc, hoặc bằng cách yêu cầu I/O. Thuật toán FCFS do đó đặc biệt gây khó khăn cho các
hệ thống tương tác, nơi mỗi quá trình cần được phân chia CPU đều đặn. 14
5.3.2 Shortest-Job-First (SJF)
Thuật toán lập lịch Shortest-Job-First (SJF), một phương pháp được sử dụng trong lập
lịch CPU. Theo cách tiếp cận này, quá trình có thời gian burst ngắn nhất cần để hoàn
thành sẽ được chọn và thực hiện tiếp theo. Nếu hai quá trình có cùng độ dài thời gian
burst, thuật toán FCFS sẽ được sử dụng để phân định. Phương pháp này có thể hiệu quả
hơn so với chỉ sử dụng FCFS vì nó giảm thiểu thời gian chờ đợi cho tất cả các quá trình.
Dưới đây là một ví dụ về cách lập lịch SJF:
Xem xét một tập hợp các quá trình sau, với thời gian burst CPU được cho trong mili giây:
Sử dụng lập lịch SJF, chúng ta sẽ lập lịch các quá trình này theo biểu đồ Gantt sau:
Thời gian chờ đợi là 3 mili giây cho quá trình P1, 16 mili giây cho quá trình P2, 9 mili
giây cho quá trình P3, và 0 mili giây cho quá trình P4. Như vậy, thời gian chờ đợi trung
bình là: (3+16+9+0)/4 = 7ms. Nếu chúng ta sử dụng FCFS thì thời gian chờ đợi trung bình là 10.25ms.
Thuật toán SJF được chứng minh là tối ưu, nó cung cấp thời gian chờ đợi trung bình thấp
nhất cho một tập hợp các quá trình cụ thể. Tuy nhiên nó không thể được triển khai ở cấp
độ lập lịch CPU vì không có cách nào để biết trước được độ dài của burst CPU tiếp 15
theo. Một cách tiếp cận cho vấn đề này là cố gắng ước lượng lập lịch SJF. Chúng ta có
thể không biết chính xác độ dài của burst CPU tiếp theo, nhưng có thể dự đoán giá trị
của nó. Chúng ta kỳ vọng rằng burst CPU tiếp theo sẽ tương tự về độ dài so với những
burst trước đó. Bằng cách tính toán một ước lượng về độ dài của burst CPU tiếp theo,
chúng ta có thể chọn quá trình có burst CPU dự đoán ngắn nhất.
Dự đoán độ dài tiếp theo của burst CPU có thể sử dụng độ dài burst của CPU trước, sử
dụng công thức trung bình mũ: Với:
1. τn là độ dài của burst CPU thứ n
2. τn+1 là giá trị dự đoán của chúng ta cho burst CPU tiếp theo.
3. α, 0 ≤ α ≤ 1. Thông thường ta chọn α=1/2. Nếu ( α = 0 ), điều này có nghĩa là chỉ
thông tin lịch sử được sử dụng để dự đoán, và thông tin gần đây không có tác
động. Nếu ( α = 1 ), chỉ có thông tin gần đây mới được sử dụng để dự đoán, và
lịch sử trước đó được coi là không liên quan.
Biểu đồ dưới thể hiện cách dự đoán bằng công thức trung bình mũ so với độ dài burst
của CPU thật, với α=1/2, τ0 = 10. 16
Hình 5.4 Dự đoán độ dài của chu kỳ CPU tiếp theo
Trung bình mũ được sử dụng để dự đoán độ dài của burst CPU tiếp theo dựa trên các burst trước đó.
Công thức mở rộng cho trung bình mũ là:
τn+1=αtn+(1−α)αtn−1+⋯+(1−α)jαtn−j+⋯+(1−α)n+1τ0.
Trong công thức này, ( α ) là hệ số trọng số giữa 0 và 1, quyết định mức độ ảnh hưởng
của thông tin gần đây so với lịch sử quá khứ.
Thuật toán SJF có thể là preemptive (chiếm đoạt), nơi quá trình đang chạy có thể bị ngắt
nếu có quá trình mới với burst CPU ngắn hơn, hoặc non-preemptive (không chiếm đoạt),
nơi quá trình đang chạy được phép hoàn thành burst CPU của mình.
Tóm lại, thuật toán SJF preemptive có thể cải thiện hiệu suất bằng cách giảm thời gian
chờ đợi, nhưng nó đòi hỏi hệ thống phải có khả năng dự đoán chính xác độ dài của burst 17
CPU tiếp theo. Đây là một phần quan trọng trong việc quản lý hiệu quả các quá trình
trong hệ thống máy tính.
5.3.3 Round Robin (RR)
Thuật toán lập lịch Round-Robin (RR) là một thuật toán lập lịch CPU dựa trên FCFS
nhưng có thêm tính năng chiếm đoạt để chuyển đổi giữa các quá trình. Một đơn vị thời
gian nhỏ, được gọi là lượng tử thời gian hoặc khoảng thời gian, được định nghĩa và lập
lịch CPU phân bổ này cho mỗi quá trình trong một hàng đợi tuần tự. Lập lịch CPU sẽ
chọn quá trình đầu tiên từ hàng đợi sẵn sàng, thiết lập bộ hẹn giờ để ngắt sau một lượng
tử thời gian và phân phối quá trình.
Nếu quá trình có một burst CPU ít hơn một lượng tử thời gian, quá trình đó sẽ tự nguyện
giải phóng CPU. Nếu burst CPU của quá trình hiện tại dài hơn một lượng tử thời gian,
bộ hẹn giờ sẽ hết giờ và gây ra một ngắt, buộc hệ điều hành thực hiện chuyển đổi ngữ
cảnh và quá trình sẽ được đưa vào cuối hàng đợi sẵn sàng. Lập lịch CPU sau đó sẽ chuyển
sang quá trình tiếp theo trong hàng đợi.
Ví dụ, nếu có ba quá trình P1, P2 và P3 với thời gian burst lần lượt là 24, 3 và 3 mili
giây, và lượng tử thời gian là 4 mili giây, lịch trình RR sẽ như sau: P1 chạy 4 mili giây
đầu tiên, sau đó P2 và P3 chạy, và cuối cùng quay trở lại P1 cho đến khi tất cả các quá
trình hoàn thành. Điều này giúp đảm bảo rằng tất cả các quá trình được xử lý công bằng
và không có quá trình nào bị đói CPU.
1. Kích thước lượng tử thời gian quyết định cách thức hoạt động của thuật toán RR.
Nếu lượng tử thời gian rất lớn, thuật toán RR sẽ hoạt động giống như chính sách
FCFS, nghĩa là quá trình nào đến trước sẽ được xử lý trước. 18
2. Nếu lượng tử thời gian rất nhỏ, ví dụ 1 mili giây, thuật toán RR có thể dẫn đến
nhiều chuyển đổi ngữ cảnh, làm chậm việc thực hiện các quá trình.
3. Lượng tử thời gian nên lớn so với thời gian chuyển đổi ngữ cảnh. Nếu thời gian
chuyển đổi ngữ cảnh chiếm khoảng 10% lượng tử thời gian, thì khoảng 10% thời
gian CPU sẽ được dành cho việc chuyển đổi ngữ cảnh.
4. Thời gian hoàn thành cũng phụ thuộc vào kích thước của lượng tử thời gian. Thời
gian hoàn thành trung bình của một tập hợp các quá trình không nhất thiết cải
thiện khi kích thước lượng tử thời gian tăng lên.
5. Thời gian hoàn thành trung bình có thể được cải thiện nếu hầu hết các quá trình
hoàn thành burst CPU tiếp theo trong một lượng tử thời gian duy nhất.
6. Mặc dù lượng tử thời gian nên lớn so với thời gian chuyển đổi ngữ cảnh, nhưng
không nên quá lớn. Nếu lượng tử thời gian quá lớn, lập lịch RR sẽ trở thành chính sách FCFS.
Một quy tắc thông thường là 80% các burst CPU nên ngắn hơn lượng tử thời gian. Điều
này giúp đảm bảo rằng thuật toán RR hoạt động hiệu quả, giảm thiểu thời gian chờ đợi
và tối ưu hóa việc sử dụng CPU. Đây là một phần quan trọng trong việc quản lý hiệu quả
các quá trình trong hệ thống máy tính.
Biểu đồ thanh hình 5.5 minh họa sự tăng số lượng chuyển đổi ngữ cảnh khi lượng tử thời gian giảm:
1. Với thời gian xử lý là 10 và lượng tử thời gian là 12, không có chuyển đổi ngữ cảnh nào.
2. Khi lượng tử thời gian giảm xuống còn 6, số lượng chuyển đổi ngữ cảnh tăng lên 1. 19
3. Với lượng tử thời gian còn nhỏ hơn nữa là 1, số lượng chuyển đổi ngữ cảnh tăng lên đáng kể là 9.
Hình 5.5 Lượng tử thời gian nhỏ hơn làm tăng chuyển đổi ngữ cảnh như thế nào
5.3.4 Lập Lịch Ưu Tiên
Thuật toán lập lịch ưu tiên (Priority Scheduling) trong lập lịch CPU. Đây là một biến thể
của thuật toán SJF, nơi mỗi quá trình được gán một mức độ ưu tiên và CPU được phân
phối cho quá trình có mức độ ưu tiên cao nhất. Các quá trình có mức độ ưu tiên bằng
nhau sẽ được lập lịch theo thứ tự FCFS. Trong SJF, mức độ ưu tiên là nghịch đảo của
burst CPU dự đoán tiếp theo: burst CPU càng lớn, mức độ ưu tiên càng thấp và ngược lại.
Mức độ ưu tiên có thể được xác định một cách nội bộ hoặc bên ngoài. Mức độ ưu tiên
nội bộ sử dụng một số lượng đo lường được để tính toán mức độ ưu tiên của một quá
trình. Ví dụ, giới hạn thời gian, yêu cầu bộ nhớ, số lượng tệp mở, và tỷ lệ trung bình I/O
burst so với CPU burst đã được sử dụng để tính toán mức độ ưu tiên. Mức độ ưu tiên
bên ngoài được thiết lập bởi các tiêu chí bên ngoài hệ thống điều hành, như tầm quan
trọng của quá trình, loại và số lượng tiền được trả cho việc sử dụng máy tính, bộ phận
tài trợ công việc, và các yếu tố khác. 20
Ví dụ, xem xét một tập hợp các quá trình với thời gian burst CPU và mức độ ưu tiên cụ thể.
Sử dụng lập lịch ưu tiên, chúng ta sẽ lập lịch các quá trình này theo biểu đồ Gantt đã cho.
Thời gian chờ trung bình trong ví dụ này là 8.2 mili giây.
Một vấn đề lớn với các thuật toán lập lịch ưu tiên là sự chặn không xác định, hay còn
gọi là đói (starvation). Một quá trình sẵn sàng chạy nhưng đang chờ CPU có thể được
coi là bị chặn. Một thuật toán lập lịch ưu tiên có thể khiến một số quá trình ưu tiên thấp
chờ đợi vô thời hạn. Trong một hệ thống máy tính quá tải, một dòng liên tục của các quá
trình ưu tiên cao có thể ngăn chặn một quá trình ưu tiên thấp từ việc bao giờ nhận được
CPU. Thông thường, một trong hai điều sẽ xảy ra: hoặc quá trình cuối cùng sẽ được chạy
(vào lúc 2 giờ sáng Chủ nhật, khi hệ thống cuối cùng không tải nặng), hoặc hệ thống
máy tính cuối cùng sẽ sụp đổ và mất tất cả các quá trình ưu tiên thấp chưa hoàn thành.
Một giải pháp cho vấn đề chặn không xác định của các quá trình ưu tiên thấp là lão hóa
(aging). Lão hóa bao gồm việc tăng dần mức độ ưu tiên của các quá trình chờ đợi trong
hệ thống trong thời gian dài. Ví dụ, nếu mức độ ưu tiên dao động từ 127 (thấp) đến 0
(cao), chúng ta có thể định kỳ (ví dụ, mỗi giây) tăng mức độ ưu tiên của một quá trình 21
đang chờ đợi lên 1. Cuối cùng, ngay cả một quá trình với mức độ ưu tiên ban đầu là 127
cũng sẽ có mức độ ưu tiên cao nhất trong hệ thống và sẽ được thực thi. Thực tế, mất hơn
2 phút để một quá trình ưu tiên 127 lão hóa thành một quá trình ưu tiên 0.
Chúng ta có thể kết hợp lập lịch ưu tiên với lập lịch Round Robin để xử lý các quá trình
theo mức độ ưu tiên của chúng. Quá trình có mức độ ưu tiên cao nhất sẽ được thực hiện
đến hoàn tất trước tiên. Sau đó, các quá trình có mức độ ưu tiên bằng nhau sẽ được thực
hiện theo cách Round Robin, nghĩa là mỗi quá trình sẽ được cấp CPU trong một lượng
tử thời gian cố định trước khi chuyển sang quá trình tiếp theo có cùng mức độ ưu tiên. Ví dụ:
Quá trình P4 với mức độ ưu tiên cao nhất (1) được thực hiện đầu tiên và hoàn tất từ thời
điểm 0 đến 7. Tiếp theo, quá trình P2 và P3, cùng có mức độ ưu tiên tiếp theo (2), được
thực hiện theo cách Round Robin với lượng tử thời gian là 2 mili giây. Khi quá trình P2
hoàn tất ở thời điểm 16, quá trình P3 trở thành quá trình có mức độ ưu tiên cao nhất và
tiếp tục được thực hiện cho đến khi hoàn tất. Cuối cùng, chỉ còn lại quá trình P1 và P5,
cả hai đều có mức độ ưu tiên bằng nhau (3), và chúng sẽ được thực hiện theo thứ tự
Round Robin cho đến khi hoàn tất.
5.3.5 Multilevel Queue Scheduling 22
Trong lập lịch ưu tiên và vòng quay, các tiến trình có thể được đặt trong một hàng đợi
duy nhất, và lập trình lập lịch sau đó chọn tiến trình có ưu tiên cao nhất để chạy. Tuy
nhiên, việc quản lý hàng đợi có thể tốn thời gian khi phải tìm kiếm tiến trình có ưu tiên
cao nhất. Một phương pháp linh hoạt hơn là sử dụng hàng đợi nhiều cấp, trong đó mỗi
loại tiến trình có thể được đặt trong một hàng đợi riêng biệt. Điều này giúp giảm thiểu
thời gian tìm kiếm tiến trình có ưu tiên cao nhất và tăng tính linh hoạt trong việc lập lịch.
Hãy xem một ví dụ về thuật toán lập lịch hàng đợi nhiều cấp với bốn hàng đợi, được liệt
kê dưới đây theo thứ tự ưu tiên:
1. Tiến trình thời gian thực 2. Tiến trình hệ thống 3. Tiến trình tương tác 4. Tiến trình tổ lệnh
Mỗi hàng đợi có ưu tiên tuyệt đối hơn các hàng đợi ưu tiên thấp hơn. Không có tiến trình
nào trong hàng đợi tổ lệnh, ví dụ, có thể chạy trừ khi các hàng đợi cho tiến trình thời
gian thực, tiến trình hệ thống và tiến trình tương tác đều trống. Nếu một tiến trình tương
tác vào hàng đợi sẵn sàng trong khi một tiến trình tổ lệnh đang chạy, tiến trình tổ lệnh sẽ bị cắt giảm.
Một khả năng khác là phân chia thời gian giữa các hàng đợi. Ở đây, mỗi hàng đợi nhận
một phần nhất định của thời gian CPU, mà nó sau đó có thể lập lịch giữa các tiến trình
khác nhau của nó. Ví dụ, trong ví dụ về hàng đợi chính - nền, hàng đợi chính có thể nhận
được 80% thời gian CPU cho lập lịch RR giữa các tiến trình của mình, trong khi hàng
đợi nền nhận được 20% thời gian CPU để cấp cho các tiến trình của nó theo cơ sở FCFS.
5.3.6 Multileveling Feedback Queue Cheduling 23
Khi sử dụng thuật toán lập lịch hàng đợi nhiều cấp, các tiến trình thường được gán cố
định vào một hàng đợi khi chúng nhập hệ thống. Điều này có nghĩa là các tiến trình
không di chuyển từ một hàng đợi sang hàng đợi khác và không thay đổi tính chất
chính/nền của chúng. Mặc dù cung cấp ưu điểm là giảm thiểu chi phí lập lịch, nhưng
đồng thời cũng làm giảm tính linh hoạt của hệ thống.
Trong khi đó, thuật toán hàng đợi nhiều cấp với phản hồi cho phép các tiến trình di
chuyển giữa các hàng đợi. Các tiến trình được phân loại dựa trên thời gian CPU burst
của chúng và có thể được chuyển đến các hàng đợi khác nhau tùy theo hành vi của chúng.
Điều này giúp tối ưu hóa việc sử dụng tài nguyên và ngăn chặn hiện tượng đói trong lập lịch.
Một ví dụ cụ thể về thuật toán này là việc chia tiến trình thành ba hàng đợi, trong đó mỗi
hàng đợi có một khoảng thời gian lượng tử khác nhau. Các tiến trình được ưu tiên cao
nhất trong hàng đợi có thời gian CPU burst ngắn và sau khi hoàn thành sẽ chuyển sang
hàng đợi có thời gian lượng tử lớn hơn. Như vậy, thuật toán này cung cấp sự linh hoạt
trong việc quản lý các tiến trình và tối ưu hóa hiệu suất của hệ thống. 24 KẾT LUẬN
Việc lập lịch CPU là một yếu tố quan trọng không chỉ trong việc tối ưu hóa sử dụng tài
nguyên mà còn trong việc cải thiện hiệu suất tổng thể của hệ thống. Sự hiểu biết về chu
kỳ CPU-I/O burst, vai trò của CPU scheduler và dispatcher, cùng với việc đánh giá hiệu
suất của các thuật toán lập lịch qua các tiêu chí như thời gian đáp ứng và thời gian chờ
đợi, cho phép chúng ta triển khai các thuật toán một cách hiệu quả. Điều này đảm bảo
rằng hệ thống không chỉ hoạt động ổn định và linh hoạt mà còn đáp ứng được các yêu
cầu ngày càng cao về hiệu suất và độ tin cậy.
Các thuật toán lập lịch như First-Come, First-Served (FCFS), Shortest-Job-First (SJF),
Round Robin (RR), Priority Scheduling, Multilevel Queue Scheduling và Multilevel
Feedback Queue Scheduling, mỗi cái đều có những ưu điểm và hạn chế riêng, phản ánh
sự cân nhắc giữa thời gian chờ đợi và công bằng trong việc phân phối tài nguyên.
Cuối cùng, việc lựa chọn và kết hợp các thuật toán lập lịch phù hợp, tùy thuộc vào nhu
cầu cụ thể của hệ thống và mục tiêu cần đạt được, là chìa khóa để tối ưu hóa hoạt động
của hệ thống máy tính, giảm thời gian chờ đợi của các tiến trình, và cải thiện hiệu suất
và hiệu quả tổng thể. 25
TÀI LIỆU THAM KHẢO 26 PHỤ LỤC 27