TRƯỜNG ĐẠI HỌC SÀI GÒN

CHƯƠNG 2: CPU SHEDULING
GV: LƯƠNG MINH HUẤN


NỘI DUNG
I. Các khái niệm cơ bản
II. Tiêu chuẩn điều phối
III. Các thuật toán điều phối CPU

IV.Điều phối đa xử lý


I. CÁC KHÁI NIỆM CƠ BẢN
➢Hệ thống có một processor => Chỉ có một tiến trình được thực
hiện tại một thời điểm.
➢Tiến trình được thực hiện (chiếm dụng VXL) cho tới khi phải chờ
đợi một thao tác vào ra.
▪ Hệ đơn chương: CPU khơng được sử dụng => lãng phí.
▪ Hệ đa chương: cố gắng sử dụng CPU (đang rảnh rỗi ) cho các tiến
trình khác (đang chờ đợi).
• Cần nhiều tiến trình sẵn sàng trong bộ nhớ tại một thời điểm.
• Khi một tiến trình phải chờ, hệ điều hành lấy lại processor để phân cho
tiến trình khác.


I. CÁC KHÁI NIỆM CƠ BẢN
➢Điều phối processor quan trọng với hệ điều hành đa nhiệm.
▪ Luân chuyển CPU giữa các tiến trình => khai thác hệ thống hiệu quả
hơn.

➢Điều phối processor là nền tảng trong thiết kế hệ điều hành.


I. CÁC KHÁI NIỆM CƠ BẢN
➢Chu kỳ CPU-I/O
▪ CPU burst
▪ I/O burst

➢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


BỘ ĐIỀU PHỐI CPU
➢Lựa chọn một trong số các tiến trình đang sẵn sàng trong bộ nhớ và
cung cấp CPU cho nó.
➢Quyết định điều phối CPU xảy ra khi tiến trình:
▪ Chuyển từ trạng thái thực hiện sang trạng thái chờ đợi (yêu cầu
vào/ra). (Điều phối không trưng dụng - non-preemptive)
▪ Chuyển từ trạng thái thực hiện sang trạng thái sẵn sàng (hết thời gian
sử dụng CPU => ngắt thời gian). (Điều phối trưng dụng – preemptive)
▪ Chuyển từ trạng thái chờ đợi sang trạng thái sẵn sàng (hoàn thành
vào/ra). (Điều phối trưng dụng – preemptive)
▪ Tiến trình kết thúc. (Điều phối không trưng dụng - non-preemptive)


BỘ ĐIỀU PHỐI CPU

➢Điều phối khơng trưng dụng
▪ Tiến trình chiếm CPU cho tới khi giải phóng bởi:
• Kết thúc nhiệm vụ

• Chuyển sang trạng thái chờ đợi

▪ Khơng địi hỏi phần cứng đặc biệt (đồng hồ )
▪ Ví dụ: DOS, Win 3.1, Macintosh


BỘ ĐIỀU PHỐI CPU
➢Điều phối trưng dụng
▪ Tiến trình chỉ được phép thực hiện trong khoảng thời gian
▪ Kết thúc khoảng thời gian được định nghĩa trước, ngắt thời gian xuất
hiện, bộ điều vận (dispatcher ) được kích hoạt để quyết định hồi
phục lại tiến trình hay lựa chọn tiến trình khác
▪ Bảo vệ CPU khỏi các tiến trình “đói-CPU"
▪ Vấn đề dữ liệu dùng chung:
• Tiến trình 1 đang cập nhật DL thì bị mất CPU
• Tiến trình 2, được giao CPU và đọc DL đang cập nhật

▪ Ví dụ: Hệ điều hành đa nhiệm WinNT, UNIX


PHÂN LOẠI CÁC HOẠT ĐỘNG ĐIỀU PHỐI


PHÂN LOẠI CÁC HOẠT ĐỘNG ĐIỀU PHỐI
➢Điều phối dài hạn(long-term scheduling): xác định process mới
(new) nào được tiếp tục vào “sâu hơn” trong hệ thống.

▪ Thường chỉ có trong batch system

➢Điều phố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ỳ ĐIỀU PHỐI
trung hạn có thể là vài phút.

➢Điều phối ngắn hạn(short-term scheduling): xác định process nào
được thực thi tiếp theo.


ĐIỀU PHỐI DÀI HẠN
➢Ảnh hưởng đến độ đa lập trình (degree of multiprogramming: số
quá trình đang ở trong bộ nhớ)
➢Nếu càng nhiều process đang ở trong bộ nhớ thì khả năng mọi
process bị block có xu hướng giảm
▪ Sử dụng CPU hiệu quả hơn
▪ Nhưng mỗi process được phân chia khoảng thời gian sử dụng CPU
nhỏ 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


ĐIỀU PHỐI TRUNG HẠN
➢Quyết định việc đưa process (không phải process ở trạng thái new)
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ộ điều phối dài hạn chấp nhận (admit) 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 (kỹ thuật bộ nhớ ảo)
▪ Nhưng nếu có q 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ớ


ĐIỀU PHỐI NGẮN HẠN
➢Xác định process nào được thực thi tiếp theo, còn gọi là điều phối
CPU
➢Tùy hệ thống (điều phối nonpreemptive, preemptive) mà được
kích hoạt khi có một sự kiện 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)

▪ Signa


II. TIÊU CHUẨN ĐIỀU PHỐI
➢Sử dụng CPU (Lớn nhất)
▪ Mục đích là làm CPU hoạt động nhiều nhất có thể
▪ Sử dụng CPU thay đổi từ 40% (hệ thống tải nhẹ) đến 90% (hệ thống
tải nặng).

➢Thông lượng (throughput) (Lớn nhất)
▪ Số lượng tiến trình hồn thành trong một đơn vị thời gian
• Các tiến trình dài: 1 tiến trình/giờ

• Các tiến trình ngắn: 10 tiến trình/giây


II. TIÊU CHUẨN ĐIỀU PHỐI
➢Thời gian hoàn thành (Nhỏ nhất)
▪ Khoảng thời gian từ thời điểm gửi đến hệ thống tới khi q trình
hồn thành
• Thời gian chờ đợi để đưa tiến trình vào bộ nhớ
• Thời gian chờ đợi trong hàng đợi sẵn sàng
• Thời gian chờ đợi trong hàng đợi thiết bị

• Thời gian thực hiện thực tế


II. TIÊU CHUẨN ĐIỀU PHỐI
➢Thời gian chờ đợi (Nhỏ nhất)
▪ Tổng thời gian chờ trong hàng đợi sẵn sàng (Giải thuật điều phối
CPU khơng ảnh hưởng tới các tiến trình đang thực hiện hay đang đợi
thiết bị vào ra)

➢Thời gian đáp ứng (Nhỏ nhất)
▪ Từ lúc gửi câu hỏi cho tới khi câu trả lời đầu tiên được tạo ra
• Tiến trình có thể tạo kết quả ra từng phần
• Tiến trình vẫn tiếp tục tính tốn kết qủa mới trong khi kết quả cũ được
gửi tới người dung.


II. TIÊU CHUẨN ĐIỀU PHỐI
➢Các giải thuật lập lịch sẽ được đánh giá qua 5 tiêu chuẩn này.
➢Các giải thuật gồm:

▪ First Come, First Served (FCFS) scheduling

▪ Shortest-Job-First scheduling
▪ Priority Scheduling
▪ Round-robin scheduling
▪ Etc.,


TIÊU CHUẨN điều phối TỪ CÁC GĨC NHÌN
➢Hướng đến người sử dụng (user-oriented)
▪ Thời gian hồn thành
• Thời gian từ lúc submission đế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)


TIÊU CHUẨN điều phối TỪ CÁC GĨC NHÌN
➢Hướng đến hệ thống (system-oriented)
▪ Sử dụng CPU
▪ Công bằng (fairness)

▪ Thông lượng: số process hoàn tất trong một đơn vị thời gian


HAI THÀNH PHẦN CỦA CHIẾN LƯỢC ĐIỀU PHỐI
➢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 chuẩn 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)


HAI THÀNH PHẦN CỦA CHIẾN LƯỢC ĐIỀU PHỐI
➢Chế độ quyết định(decision mode)
▪ Định nghĩa thời điểm hàm lựa chọn được 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 CPU


III. CÁC THUẬT TOÁN ĐIỀU PHỐI CPU
➢Đến trước phục vụ trước (FCFS: First Come, First Served).
▪ Ngun tắc:
• Tiến trình được quyền sử dụng CPU theo trình tự xuất hiện

• Tiến trình sở hữu CPU tới khi kết thúc hoặc chờ đợi vào ra

▪ Đặc điểm:
• Đơn giản, dễ thực hiện.
• Tiến trình ngắn phải chờ đợi như tiến trình dài



FCFS
➢Hàm lựa chọn: chọn process ở trong hàng đợi ready lâu nhất
➢Chế độ quyết định: nonpreemptive
▪ Một process sẽ được thực thi cho đến khi nó block hoặc kết thúc

➢FCFS thường được hiện thực bằng một FIFO queue


FCFS
➢Ví dụ:
➢Giả sử các process đến theo thứ tự P1, P2, P3

➢Giản đồ Gantt cho việc điều phối là:

➢Thời gian đợi cho P1= 0, P2= 24, P3= 27

➢Thời gian đợi trung bình: (0 + 24 + 27) / 3 = 17


FCFS
➢Giả sử các process đến theo thứ tự: P2, P3, P1
➢Giản đồ Gantt cho việc điều phối là:

➢Thời gian đợi của P1=6,P2= 0,P3= 3
➢Thời gian đợi trung bình: (6 + 0 + 3) / 3 = 3
▪ Tốt hơn rất nhiều so với trường hợp trước