Xem mẫu
- 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ó 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ớ
- Đ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 hoà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 quá trình
hoà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 toá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 hoà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)
nguon tai.lieu . vn
