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

1 
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 ? 
2 
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 
} 
3 
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 
4 
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 
5 
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 
6 
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() 
7 
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 
8 
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 ? 
9 
Các danh sách tiến trình 
Ready List 
P1 
P4 
P5 
Waiting Lists 
R1 
P7 
P2 
P10 
P3 
P6 
R1 
R1 
10 
Đ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 
11 
Đ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 
12 
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 ? 
13 
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 
14 
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 
15 
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 
16 
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()) 
17 
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 
18 
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 đ ộ 
19 
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 
20 
Các chiến l ư ợc đ iều phối 
 FIFO 
 RR 
 SJF 
 MULTILEVELFEEDBACK 
 LOTTERY 
21 
FIFO – RR -SJF 
FIFO 
RR 
SJF 
add 
run 
run 
add 
22 
Multilevel Feedback 
priority 
23 
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