Bài giảng Hệ điều hành - Chương 4: Quản lý tiến trình - Trần Trung Dũng

Nội dung text: Bài giảng Hệ điều hành - Chương 4: Quản lý tiến trình - Trần Trung Dũng

1. MỤC TIÊU Mô hình Tiến trình Trạng thái tiến trình Thông tin quản lý tiến trình Quá trình điều phối tiến trình Các thuật toán điều phối 2
2. ĐA NHIỆM VÀ ĐA CHƯƠNG ??? Vì sao muốn xử lý đồng thời nhiều công việc trên máy tính ? Job : kq = a*b + c*d; Xứ lý tuần tự Xửù lý đồng hành CPU #1 CPU #1 CPU #2 x = a * b 1 x = a * b y = c * d y = c *d 2 kq = x+y kq = x+y 3 4 → Xử lý đồng thời để tăng tốc độ xử lý
3. XỬ LÝ ĐỒNG HÀNH, NHỮNG KHÓ KHĂN ? Excel - Tài nguyên giới hạn, ứng Visual C++ dụng “vô hạn” CDplayer Winword - Nhiều hoạt động đan xen ??? Phân chia tài nguyên ? ??? Chia sẻ tài nguyên ? ??? Bảo vệ? HĐH : “Giải quyết nhiều công việc đồng thời, đâu có dễ6!”
4. GIẢI PHÁP CPU 8
5. HAI PHẦN CỦA TIẾN TRÌNH Dòng xử lý int a; int a; Không gian địa chỉ 10
6. KHỐI QUẢN LÝ TIẾN TRÌNH Định danh (Process ID) pid Trạng thái tiến trình State Ngữ cảnh tiến trình  Trạng thái CPU (State, details)  Bộ xử lý (cho máy nhiều CPU)  Bộ nhớ chính Context  ử ụ ạ ậ Tài nguyên s d ng/t o l p (IP, Mem, Files ) Thông tin giao tiếp  Tiến trình cha, tiến trình con Relatives  Độ ưu tiêên ( Dad, children) Thông tin thống kê  Thời gian sử dụng CPU Scheduling statistic  Thời gian chờ Process control Block12 PCB
7. CÁC THAO TÁC TRÊN TIẾN TRÌNH Tạo lập tiến trình Kết thúc tiến trình Thay đổi trạng thái tiến trình :  Assign()  Block()  Awake()  Suspend()  Resume() 14
8. KẾT THÚC TIẾN TRÌNH Tình huống :  Tiến trình xử lý xong lệnh cuối cùng hay gọi exit ()  Kết thúc Batch job , Halt instruction  User logs off  Do lỗi chương trình Một tiến trình có thể kết thúc 1 tiến trình khác nếu có ID (định danh) của tiến trình kia.  Ví dụ: kill –-s SIGKILL 1234: huỷ tiến trình có ID là 1234 16
9. VÍ DỤ MÔ HÌNH ĐA TIẾN TRÌNH Giờ thi lý thuyết môn Hệ Điều hành  Mỗi sinh viên là một tiến trình : Cùng làm bài => Hoạt động đồng hành Có bài thi , bút, giấy riêng => Tài nguyên riêng biệt Độc lập => Không trao đổi (về nguyên tắc) Thực hành môn Hệ Điều hành  2 sinh viên/nhóm  Hợp tác đồng hành  Nhu cầu trao đổi  Dùng tài nguyên chung 18
10. VÍ DỤ MÔ HÌNH ĐA TIỂU TRÌNH Thực hành môn Hệ Điều hành  Mỗi nhóm 2 sinh viên là một tiến trình :  Mỗi sinh viên là một tiểu trình Cùng làm bài => Hoạt động đồng hành Cóù bài thực hành chung => Tài nguyên chung Trao đổi với nhau 20
11. TIỂU TRÌNH HẠT NHÂN (KERNEL THREAD) T1 T2 User mode System call Kernel mode Kernel Thread Khái niệm tiểu trình được xây dựng bên trong hạt nhân Đơn vị xử lý là tiểu trình Ví dụ :  Windows 95/98/NT/2000 22  Solaris, Tru64 UNIX, BeOS, Linux
12. CÁC DANH SÁCH TIẾN TRÌNH Ready List P1 P4 P5 Waiting Lists R1 P2 P7 R2 P3 P10 R3 P6 24
13. DISPATCHER - NHIỆM VỤ Nhiệm vụ của Dispatcher: Chuyển đổi ngữ cảnh Xét ví dụ  Tiến trình A đang dùng CPU 1 chút thì bị HĐH thu hồi CPU  HĐH cấp CPU cho B dùng 1 chút, HĐH thu hồi lại CPU.  HĐH cấp CPU trở lại cho A. → Giá trị các thanh ghi giữa những lần chuyển đổi CPU ? Kịch bản :  Lưu ngữ cảnh tiến trình hiện hành  Nạp ngữ cảnh tiến trình được chọn kế tiếp 26
14. DISPATCHER - THẢO LUẬN Bản thân HĐH cũng là 1 phần mềm, nghĩa là cũng sử dụng CPU để có thể chạy được. Câu hỏi: Khi tiến trình A đang chiếm CPU, làm thế nào HĐH có thể thu hồi CPU lại được ? (vì lúc này HĐH không giữ CPU)  Ép buộc NSD thỉnh thoảng trả CPU lại cho HĐH ? Có khả thi ?  Máy tính phải có 2 CPU, 1 dành riêng cho HĐH ? ➔ HĐH sử dụng ngắt đồng hồ (ngắt điều phối) để kiểm soát hệ thống ➔ Mỗi khi có ngắt đồng hồ, HĐH kiểm tra xem có cần thu hồi CPU từ 1 tiến trình nào đó lại hay không ? ➔ HĐH chỉ thu hồi CPU khi có ngắt đồng hồ phát sinh. ➔ Khoảng thời gian giữa 2 lần ngắt điều phối gọi là chu kỳ đồng hồ 28 (tối thiểu là 18.2 lần / giây)
15. MỤC TIÊU ĐIỀU PHỐI Hiệu qủa (Efficiency)   Thời gian  Đáùp ứng (Response time)  Hoàn tất (Turnaround Time = Tquit -Tarrive):  Chờ (Waiting Time = T in Ready ) :   Thông lượng (Throughput = # jobs/s )  Hiệu suất Tài nguyên  Chi phí chuyển đổi Công bằng ( Fairness): Tất cả các tiến trình đều có cơ hội nhận CPU 30
16. THỜI ĐIỂM RA QUYẾT ĐỊNH ĐIỀU PHỐI Điều phối độc quyền (non-preemptive scheduling): tiến trình được chọn có quyền độc chiếm CPU  Các thời điểm kích hoạt Scheduler P cur kết thúc P cur : running ->blocked Điều phối không độc quyền (preemptive scheduling): tiến trình được chọn có thể bị cướp CPU bởi tiến trình có độ ưu tiên cao hơn  Các thời điểm kích hoạt Scheduler P cur kết thúc P cur : Running -> Blocked Q : Blocked / New -> Ready 32
17. CÁC CHIẾN LƯỢC ĐIỀU PHỐI ▪ FIFO (FCFS) ▪ Xoay vịng (Round Robin) ▪ Theo độ ưu tiên ▪ Cơng việc ngắn nhất (SJF) ▪ Nhiều mức độ ưu tiên 34
18. MINH HỌA FCFS P TarriveRL CPU burst P TT WT P1 0 24 P1 24 0 P2 1 3 P2 27-1 24-1 P3 2 3 P3 30-2 27-2 AvgWT = (23+25)/3 = 16 P1 P2 P3 0 24 27 0: P1 vào RL 24: P1 kết thúc P1 dùng CPU P2 dùng CPU 1: P2 vào RL 27: P2 kết thúc 36 2: P3 vào RL P3 dùng CPU
19. ĐIỀU PHỐI XOAY VÒNG ROUND ROBIN (RR) ▪ Điều phối theo nguyên tắc FCFS ▪ Mỗi tiến trình chỉ sử dụng một lượng q cho mỗi lần sử dụng CPU Quantum/ Time slice Ready List C B A CPU A chỉ chiếm CPU trong q ms Ready List A C B B được giao quyền sử dụng CPU CPU trong q ms kế tiếp Ready List B A C C được giao quyền sử dụng CPU CPU trong q ms kế tiếp 38
20. MINH HỌA RR, Q=4 P TarriveRL CPU burst ▪ Tranh chấp vị trí trong RL : “Chung thủy” P1 0 24 1. P : running -> ready 2. P : blocked -> ready P2 4 3 3. P: new ->ready P3 12 3 ▪ Không phải luôn luôn có thứ tự điều phối P1 P2 P3 P4 P1 P2 P3 P4 P1 P1 P2 P1 P3 P1 P1 P1 0 4 8 11 15 18 22 26 30 RL 0:04 P2 P1 “Có mới nới 0:00 P1 cũ” 0:8 P2 P1 0:04 0:11 P140 “õChung thủy” 0:15 P3 P1 0:04 P1 P2 ? 0:18 P1
21. ROUND ROBIN – NHẬN XÉT Bao lâu ? Sử dụng cơ chế không độc quyền Mỗi tiến trình không phải đợi quá lâu Loại bỏ hiện tượng độc chiếm CPU Hiệu quả ?  Phụ thuộc vào việc chọn lựa quantum q q quáù lớn ??? Giảm tíùnh tương q quá nhỏ ??? tác Tăng chi phí chuyển đổi ngữ cảnh Trường hợp xấu nhất của RR ? 42
22. ĐIỀU PHỐI VỚI ĐỘ ƯU TIÊN Cách tính độ ưu tiên?  Hệ thống gán: CPU times,  Người dùng gán tường minh Tính chất độ ưu tiên :  Tĩnh  Động 44
23. BIỂU ĐỒ PHÂN BỐ ĐỘ ƯU TIÊN CỦA WINNT realtime time-critical 31 realtime highest (+2) realtime above normal (+1) levels 16-31 24 normal (0) below normal (-1) lowest (-2) realtime idle 16 high dynamic time-critical 15 13 normal dynamic 8 idle levels 1-15 4 dynamic idle 1 46 system idle 0
24. ĐỘ ƯU TIÊN – KHÔNG ĐỘC QUYỀN P TRL Priority CPU burst P TT WT P1 0 0 24 P1 30 0+(7-1) P2 1 2 3 P2 4-1 0 P3 2 1 3 P3 7-2 4-2 AvgWT = (6+0+2)/3 = 2.66 P1 P2 P2 P3 P1 0 1 2 4 7 30 0: P1 vào, P1 dùng CPU 4: P2 kết thúc, P3 dùng CPU 1: P2 vào (độ ưu tiên cao hơn P1) 7: P3 dừng, P1 dùng CPU P2 dành quyền dùng CPU 30: P1 dừng 48 2: P3 vào (độ ưu tiên thấp hơn P2) P3 khơng dành được quyền dùng CPU
25. SHORTEST JOB FIRST (SJF) Ready List P2 (cần 3 chu kỳ) P1 CPU (cần 5 chu kỳ) P3 (cần 7 chu kỳ) Là một dạng độ ưu tiên đặc biệt với độ ưu tiên pi = thời_gian_cịn_lại(Processi) 50 ➔ Cĩ thể cài đặt độc quyền hoặc khơng độc quyền
26. MINH HỌA SJF (ĐỘC QUYỀN)(2) P TarriveRL CPU burst P TT WT P1 0 24 P1 24 0 P2 1 3 P2 29-1 26-1 P3 1 2 P3 26-1 24-1 AvgWT = (24+22)/3 = 15.33 P1 P3 P2 0 24 26 29 0:00 P1 vào, P1 dùng CPU 0:24 P1 kết thúc, P3 dùng CPU 0:01 P2 vào 0:26 P3 dừng, P2 dùng CPU 52 0:01 P3 vào 0:29 P2 dừng
27. MINH HỌA SJF (KHÔNGĐỘC QUYỀN) (2) P TarriveRL CPU burst P TT WT P1 0 24 P1 33 0+(10-1) P2 1 5 P2 5 0 P3 3 4 P3 7 6-3 AvgWT = (9+0+3)/3 = 4 P1 P2 P2 P3 P1 0 1 3 6 10 33 0:00 P1 vào, P1 dùng CPU 0:6 P2 kết thúc, P3 dùng CPU 0:01 P2 vào (độ ưu tiên cao hơn P1) 0:10 P3 dừng, P1 dùng CPU P2 dành quyền dùng CPU 0:33 P1 dừng 54 0:03 P3 vào (độ ưu tiên < P2) P2 dành quyền dùng CPU
28. ĐIỀU PHỐI VỚI NHIỀU MỨC ƯU TIÊN Tổ chức N RL Độ ưu tiên ứng với nhiều 1 mức ưu tiên Mỗi RLi áp dụng CPU một chiến lược 2 điều phối thích hợp Giữa các RL áp n dụng điều phối theo độ ưu tiên :  RLi rỗng mới điều Kết hợp phối RLi +1 nhiều chiến lược 56
29. Bài tập: Hãy điều phối CPU: SJF khơng độc quyền. R1,R2: FIFO Tiến Thời điểm IO lần 1 IO lần 2 trình vào Ready CPU1 CPU2 list Thời Thiết Thời Thiết gian bị gian bị P1 0 8 5 R1 1 0 Null P2 2 1 8 R2 2 5 R1 P3 10 6 5 R1 2 3 R2 P4 11 3 20 R2 0 0 Null 58