Bài giảng Hệ điều hành nâng cao - Bài 3: Quản lý tiến trình - Trần Hạnh Nhi

Bài 3 : QUẢN LÝ TIẾN TRÌNH 
Phân chia CPU cho các tiến trình ? 
Tiếp cận 
Mục tiêu ? 
Tổ chức ? 
Chiến lược ? 
Trạng thái tiến trình ? 
Lưu trữ thông tin tiến trình ? 
Các thao tác trên tiến trình ? 
Bảo vệ tiến trình ? 
Trao đổi thông tin giữa các tiến trình ? 
1 
Phân chia CPU ? 
1 CPU vật lý : làm thế nào để tạo ảo giác mỗi tiến trình sở hữu CPU riêng của mình ? 
Dispatcher luân chuyển CPU giữa các tiến trình : 
Ngữ cảnh xử lý riêng biệt cho mỗi tiến trình (PCB) 
Dispatching loop : 
CPU 
while(1) 
{ 
 interrupt P cur 
 save state P cur 
 Scheduler gets P next 
 load state P next 
 jump to it 
} 
2 
Trạng thái tiến trình ? 
ready 
 R s 
 CPU 
running 
 R s 
 CPU 
blocked 
 R s 
 CPU 
Nhận CPU 
Trả CPU 
Chờ R 
Nhận R 
3 
Khối quản lý tiến trình trong mô hình multiprocesses 
pid 
State 
(State, details) 
Context 
(IP, Mem , Files) 
Scheduling statistic 
Relatives 
( Dad, children) 
Process control Block 
PCB 
4 
PCB và TCB trong mô hình multithreads 
pid 
Threads list 
Context 
( Mem , global ressources ) 
Scheduling statistic 
Relatives 
( Dad, children) 
PCB 
tid 
State 
(State, details) 
Context 
(IP, local stack) 
Thread Control Block 
TCB 
5 
Các thao tác trên tiến trình 
Tạo lập tiến trình : 
Cấp phát tài nguyên cho tiến trình con ? 
Hoạt động của cha và con độc lập 
Kết thúc tiến trình : 
Thu hồi tài nguyên ? 
Eùp buộc kết thúc ? 
Thay đổi trạng thái tiến trình : 
Assign(), Block(), Awake(), Resume(), Suspend() 
6 
Trạng thái tiến trình ? 
Có nhu cầu Suspend &Resume : 
Hệ thống quá tải 
Kiểm soát hoạt động của tiến trình con 
7 
An ninh trật tự cho môi trường đa tiến trình ! 
Bảo vệ tiến trình : 
Ngăn cản các tiến trình xâm phạm tài nguyên , can thiệp vàoxử lý của nhau => KGĐC riêng biệt , 2 mode xử lý 
Bảo đảm quyền tiến triển xử lý cho mỗi tiến trình => công bằng trong các chiến lược phân phối tài nguyên . 
Trao đổi thông tin , phối hợp hoạt động ? 
Nhu cầu ? 
Vấn đề ? => Chương kế tiếp 
Giải pháp ? 
8 
Các danh sách tiến trình 
Ready List 
P1 
P4 
P5 
Waiting Lists 
R1 
P7 
P2 
P10 
P3 
P6 
R1 
R1 
9 
Điều phối tiến trình 
Mục tiêu ? 
Các cấp độ điều phối 
Thời điểm ra quyết định điều phối ? 
Đánh giá chiến lược điều phối ? 
Một số chiến lược điều phối 
10 
Điều phối tiến trình 
SCHEDULER 
chọn một tiến trình nhận cpu 
DISPATCHER 
chuyển đổi ngữ cảnh 
11 
Chuyển đổi ngữ cảnh (context switching) 
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 
Chi tiết cụ thể phụ thuộc vào phần cứng 
general-purpose & floating point registers, co-processor state 
Chi phí chuyển đổi ngữ cảnh : 
Giữa các tiến trình ? 
Giữa các tiểu trình ? 
12 
Chuyển đổi ngữ cảnh giữa các tiến trình 
Chuyển đổi mode xử lý 
Chuyển đổi IP và các thanh ghi khác của CPU 
Chuyển đổi không gian địa chỉ 	 
P1 
P2 
Dispatcher 
System call 
User mode 
Kernel mode 
13 
Tiểu trình hạt nhân (Kernel thread) 
Khái niệm tiểu trình được xây dựng bên trong hạt nhân 
Distpatcher làm việc với đơn vị là tiểu trình 
T1 
T2 
Dispatcher 
System call 
User mode 
Kernel mode 
14 
Tiểu trình người dùng (User thread) 
Khái niệm tiểu trình được hỗ trợ bởi một thư viện hoạt động trong user mode 
Distpatcher của hạt nhân làm việc với đơn vị là tiến trình 
ThreadDistpatcher làm việc với đơn vị là tiểu trình 
P -– LWP - T 
Không cần chuyển đổi chế độ xử lý khi chuyển đổi các tiểu trình cùng thuộc 1 tiến trình . 
T1 
Kernel 
T2 
User mode 
Kernel mode 
T3 
LWP1 
LWP2 
P1 
P2 
15 
Lựa chọn tiến trình ? 
Tác vụ của Scheduler 
Mục tiêu ? 
Sử dụng CPU hiệu quả 
Đảm bảo tất cả các tiến trình đều tiến triển xử lý 
Tiêu chuẩn lựa chọn ? 
Tất cả các tiến trình đều như nhau ? 
Đề xuất một độ ưu tiên cho mỗi tiến trình ? 
Thời điểm lựa chọn ? ( Thời điểm kích hoạt Scheduler()) 
16 
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 = T quit -T arrive ): 
 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 
17 
Các cấp độ điều phối 
Longterm scheduling : chọn tiến trình kế tiếp được khởi động (mang vao bộ nhớ và nhận trạng thái ready) 
Mediumterm scheduling : quyết định chuyển tiến trình đang running sang trạng thái blocked. 
Shorterm scheduling : chọn 1 tiến trình ở trạng thái ready để chuyển sang trạng thái running. 
Không có sự phân biệt rõ ràng hoàn toàn giữa 3 cấp độ 
18 
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 chiếm CPU 
Đ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 
19 
Các chiến lược điều phối 
 FIFO 
 RR 
 SJF 
 MULTILEVELFEEDBACK 
 LOTTERY 
20 
FIFO – RR -SJF 
FIFO 
RR 
SJF 
add 
run 
run 
add 
21 
Multilevel Feedback 
priority 
22 
Lottery 
1 
1 
1 
1 
P1 
P2 
P3 
P4 
1 
1 
7 
1 
P1 
P2 
P3 
P4 
P2 có 25 % cơ hội 
P2 có 70 % cơ hội 
23