Download miễn phí Bài giảng Hệ điều hành - Định thời CPU (CPU Scheduling)
Định thời đa xửlý
(Multiple-Processor Scheduling)
Định thờiCPU sẽphứctạphơnvới nhiềuCPU hiệnhữu.
Thường các CPU và bộnhớ đồng nhất (homogeneous).
Chia tải (load sharing):
• Mỗi CPU có hàng đợi riêng dễdẫn đến tình trạng mất cân bằng tải:
một CPU có hàng đợi rỗng, trong khi CPU khác rất bận.
• Giải pháp dùng hàng đợi chung cho tất cảcác CPU.
Việc định thời (scheduling) và chọn CPU đểphân bổ(dispatch)
có thể được quản lý:
• Đa xửlý đối xứng (Symmetric Multiprocessor): mỗi CPU tự định
thời từhàng đợi chung. Có thểdẫn đến cạnh tranh chọn quá trình.
• Đaxửlý không đốixứng (Asymmetric Multiprocessor): được quản
lý bởi 1 trong các CPU -> Cấu trúc chủ-tớ(Master-Slave). Có thể
dẫn đến bottleneck
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
4.1HỆ ĐIỀU HÀNH
(OPERATING SYSTEM)
Trình bày:Nguyễn Hoàng Việt
Khoa Công Nghệ Thông Tin
Đại Học Cần Thơ
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.2
Chương 4: Định thời CPU
(CPU Scheduling)
Các khái niệm cơ bản
Tiêu chí cho việc định thời
Các giải thuật định thời
Định thời đa xử lý
Định thời thời gian thực
Đánh giá giải thuật
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.3
Các khái niệm cơ bản (1)
Chu kỳ CPU-I/O (CPU-I/O Burst Cycle)
Kỹ thuật đa chương giúp việc sử
dụng CPU đạt hiệu năng cao nhất.
Chu kỳ CPU-I/O
• Sự thực thi của quá trình bao gồm
nhiều chu kỳ CPU-I/O
• Một chu kỳ CPU-I/O bao gồm chu
kỳ thực thi CPU (CPU burst) và chu
kỳ chờ đợi vào/ra (I/O burst).
Sự phân bổ sử dụng CPU
• Chương trình hướng nhập xuất
(I/O-bound) thường có nhiều chu kỳ
CPU ngắn.
• Chương trình hướng xử lý (CPU-
bound) thường có nhiều chu kỳ
CPU dài.
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.4
Các khái niệm cơ bản (2)
Biểu đồ so sánh thời gian sử dụng CPU
Histogram of CPU-burst Times
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.5
Các khái niệm cơ bản (3)
Bộ định thời CPU (CPU Scheduler)
Được thực hiện bởi bộ định thời ngắn kỳ (short-term scheduler),
còn được gọi là bộ định thời (CPU scheduler)
Chọn một trong các quá trình trong hàng đợi sẵn sàng và giao
CPU cho nó thực thi
Quyết định định thời xảy ra khi một quá trình:
• Chuyển từ trạng thái đang chạy sang trạng thái chờ đợi
• Chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng
• Chuyển từ trạng thái chờ đợi sang sẵn sàng
• Kết thúc
Định thời không trưng dụng (nonpreempty): quá trình sẽ giữ
CPU và chỉ giải phóng CPU khi nó cần (trường hợp 1 và 4)
Định thời trưng dụng (preempty): các trường hợp khác
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.6
Các khái niệm cơ bản (4)
Bộ phân phối (Dispatcher)
Có nhiệm vụ trao quyền điều khiển CPU cho quá trình được
chọn bởi bộ định thời CPU
Công việc này bao gồm:
• Chuyển ngữ cảnh
• Chuyển sang chế độ người dùng
• Nhảy tới vị trí của chương trình người dùng để khởi động lại
chương trình đó
Độ trễ phân phối (Dispatch Latency): thời gian dispatcher cần
để ngưng một quá trình và khởi động lại quá trình khác
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.7
Tiêu chí cho việc định thời biểu (1)
Các tiêu chí (Criteria)
Hiệu suất sử dụng CPU: giữ CPU luôn bận nhiều nhất có thể.
Thông lượng (Throughput): số lượng quá trình hoàn thành trên
một đơn vị thời gian.
Thời gian xoay vòng (Turnaround time): tổng thời gian trôi qua
từ khi một quá trình được đưa lên đến khi nó hoàn thành, bao
gồm: thời gian thực thi, thời gian chờ I/O, thời gian trong hàng
đợi sẵn sàng, và các phí tổn khác.
Thời gian chờ đợi (Waiting time): tổng thời gian trong trong
hàng đợi sẵn sàng (ready queue).
Thời gian đáp ứng (Response time): lượng thời gian từ lúc một
yêu cầu được đệ trình cho đến khi tín hiệu trả lời đầu tiên xuất
hiện (dùng cho môi trường chia thời gian).
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.8
Tiêu chí cho việc định thời biểu (2)
Tiêu chí tối ưu hóa
Hiệu suất sử dụng CPU tối đa
Thông lượng tối đa
Thời gian xoay vòng tối thiểu
Thời gian chờ đợi tối thiểu
Thời gian đáp ứng tối thiểu
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.9
Các giải thuật định thời (1)
Giải thuật First-Come, First-Served (FCFS)
P1 P2 P3
24 27 300
Process TG sử dụng CPU
P1 24
P2 3
P3 3
Giả sử các quá trình xuất hiện theo thứ tự P1, P2, P3. Biểu đồ
Gantt cho lịch biểu là:
Thời gian chờ đợi: P1 = 0; P2 = 24; P3 = 27
Thời gian chờ đợi trung bình: (0 + 24 + 27)/3 = 17
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.10
Các giải thuật định thời (2)
Giải thuật First-Come, First-Served (FCFS)
Giả sử các quá trình xuất hiện theo thứ tự P2, P3,,P1. Biểu đồ
Gantt cho lịch biểu là:
Thời gian chờ đợi: P1= 6; P2 = 0; P3 = 3
Thời gian chờ đợi trung bình: (6 + 0 + 3)/3 = 3
Tốt hơn nhiều so với trường hợp trước.
Ö Tránh “tác động nối đuôi”: quá trình ngắn nằm sau quá trình dài.
FCFS là giải thuật định thời không trưng dụng, không thích hợp
cho hệ thống chia thời gian.
P1P3P2
63 300
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.11
Các giải thuật định thời (3)
Giải thuật Shortest-Job-First (SJF)
Kết hợp với mỗi quá trình độ dài thời gian mà nó sẽ sử dụng
CPU lần kế tiếp. Sử dụng các độ dài này để định thời cho quá
trình với thời gian ngắn nhất.
Có hai thể thức thực hiện giải thuật:
• Không trưng dụng: một khi CPU được giao cho một quá trình, nó
không thể bị trưng dụng để giao cho quá trình khác có thời gian
ngắn hơn cho đến khi quá trình này sử dụng CPU xong.
• Trưng dụng: nếu một quá trình mới đến có thời gian sử dụng CPU
ngắn hơn thời gian thực thi còn lại của quá trình đang chạy, thì ưu
tiên giao CPU cho quá trình mới đến. Cách thức này được gọi là
Shortest-Remaining-Time-First (SRTF).
SJF là tối ưu – nó tạo ra thời gian chờ đợi trung bình ngắn
nhất.
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.12
Các giải thuật định thời (4)
Giải thuật Shortest-Job-First (SJF)
Ví dụ về SJF không trưng dụng
Process Thời điểm đến Tg sử dụng CPU
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (không trưng dụng)
Thời gian chờ đợi trung bình = (0 + 6 + 3 + 7)/4 = 4
P1 P3 P2
73 160
P4
8 12
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.13
Các giải thuật định thời (5)
Giải thuật Shortest-Job-First (SJF)
Ví dụ về SJF trưng dụng
Process Thời điểm đến Tg sdụng CPU
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (có trưng dụng)
Thời gian chờ đợi trung bình = (9 + 1 + 0 +2)/4 = 3
P1 P3P2
42 110
P4
5 7
P2 P1
16
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.14
Các giải thuật định thời (6)
Giải thuật Shortest-Job-First (SJF)
Chỉ có thể ước lượng độ dài.
Độ dài ước lượng được tính toán dựa trên chiều dài thời
gian sử dụng CPU lần trước đó, sử dụng công thức trung
bình mũ:
• là thời gian sử dụng CPU thực tế lần thứ n.
• là ước lượng thời gian sử dụng CPU lần thứ n+1
• , là tham số điều khiển trọng số liên quan giữa
lịch sử quá khứ và lịch sử mới đây trong việc ước lượng.
• Định nghĩa:
( ) .1 1 nnn t ταατ −+=+
nt
1+n
Xác định độ dài thời gian sử dụng CPU lần kế tiếp
τ
10, ≤≤αα
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.15
Các giải thuật định thời (7)
Giải thuật Shortest-Job-First (SJF)
Ví dụ về tính trung bình mũ
α =0
• τn+1 = τn
• Không tính đến lịch sử
α =1
• τn+1 = tn
• Chỉ tính đến thời gian sử dụng CPU thực gần nhất
α =1/2, lịch sử quá khứ và gần đây có trọng số tương đương.
Nếu mở rộng công thức, ta có:
τn+1 = α tn+(1 - α) α tn-1 + … +(1 - α )j α tn-j + … +(1 - α )n+1τ0
Vì α và (1- α) nhỏ hơn hay bằng 1, mỗi số hạng tiếp theo có
trong số nhỏ hơn số hạng trước đó.
Nguyễn Hoàng Việt – Khoa Công Nghệ Thông Tin ĐHCT (2007) 4.16
Các giải thuật định thời (8)
Giải t...