Bài giảng Hệ điều hành nâng cao - Trần Hạnh Nhi - Chương 1: Tổ chức hệ điều hành

trình
 Tiểu trình : 1 dòng xử 
lý
 Tiến trình : 
 1 không gian địa chỉ
 1 hoặc nhiều tiểu trình
 Các tiến trình là độc 
lập
 Các tiểu trình trong 
cùng 1 
tiến trình không có sự 
bảo vệ 
lẫn nhau (cần thiết ? ).
P1
int a;
T1 T2 T
3
Simpo PDF Merge and Split Unregistered Version - 
11
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
T1 T2
HDH
System call
User mode
Kernel mode
Simpo PDF Merge and Split Unregistered Version - 
12
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
T1
Kernel
T2
User 
mode
Kernel 
mode
T3
LWP1 LWP2
P1 P2
Simpo PDF Merge and Split Unregistered Version - 
1Bà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 ?
Simpo PDF Merge and Split Unregistered Version - 
2Phâ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 Pcur
save state Pcur
Scheduler gets Pnext
load state Pnext
jump to it
}
Simpo PDF Merge and Split Unregistered Version - 
3Trạng thái tiến trình ?
ready
 Rs
 CPU
running
 Rs

CPU
blocked
 Rs
 CPU
Nhận CPU
Trả CPU
Chờ R
Nhận R
Simpo PDF Merge and Split Unregistered Version - 
4Khố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
Simpo PDF Merge and Split Unregistered Version - 
5PCB 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
Simpo PDF Merge and Split Unregistered Version - 
6Cá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()
Simpo PDF Merge and Split Unregistered Version - 
7Trạ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
Simpo PDF Merge and Split Unregistered Version - 
8An 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 ? 
Simpo PDF Merge and Split Unregistered Version - 
9Các danh sách tiến trình
Ready List P1 P4 P5
Waiting Lists
R1 P7P2
P10P3
P6
R1
R1
Simpo PDF Merge and Split Unregistered Version - 
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
Simpo PDF Merge and Split Unregistered Version - 
11
Điều phối tiến trình
SCHEDULER
chọn một tiến trình 
nhận cpu
DISPATCH
ER
chuyển đổi ngữ 
cảnh
Simpo PDF Merge and Split Unregistered Version - 
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 ?
Simpo PDF Merge and Split Unregistered Version - 
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
Simpo PDF Merge and Split Unregistered Version - 
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
Simpo PDF Merge and Split Unregistered Version - 
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
Simpo PDF Merge and Split Unregistered Version - 
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())
Simpo PDF Merge and Split Unregistered Version - 
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 = 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
Simpo PDF Merge and Split Unregistered Version - 
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
Simpo PDF Merge and Split Unregistered Version - 
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
Simpo PDF Merge and Split Unregistered Version - 
20
Các chiến lược điều phối
 FIFO
 RR
 SJF
 MULTILEVELFEEDBACK
 LOTTERY
Simpo PDF Merge and Split Unregistered Version - 
21
FIFO – RR -SJF
 FIFO
 RR
 SJF
addrun
run
add
Simpo PDF Merge and Split Unregistered Version - 
22
Multilevel Feedback
priority
Simpo PDF Merge and Split Unregistered Version - 
23
Lottery
1 11 1
P1 P2 P3 P4
1 17 1
P1 P2 P3 P4
P2 có 25 % cơ hội
P2 có 70 % cơ hội
Simpo PDF Merge and Split Unregistered Version - 
1BÀI 4 : LIÊN LẠC GIỮA CÁC TIẾN 
TRÌNH 
& VẤN ĐỀ ĐỒNG BỘ HOÁ
CƠ CHẾ ?
VẤN ĐỀ 
?
TRAO ĐỔI THÔNG TIN GIỮA CÁC TIẾN TRÌNH
GỈAI 
PHÁP ?
Simpo PDF Merge and Split Unregistered Version - 
2Nhu Cầu Liên Lạc
Q
Lp
 Chia sẻ thông tin
R
 Phối hợp tăng tốc độ xử lý 
Q
L
p
JOB
Simpo PDF Merge and Split Unregistered Version - 
3Các Cơ Chế Liên Lạc
 Signal
Không truyền được dữ liệu
 Pipe
 Truyền dữ liệu không cấu trúc
 Shared Memory
Broadcast
 Mâu thuẫn truy xuất => nhu cầu đồng bộ hoá
 Message
Liên lạc trên môi trường phân tán
 Socket
Liên lạc trên nhiều môi trường khác biệt
Simpo PDF Merge and Split Unregistered Version - 
4Race condition
hits = 0 + 1
read hits (0)
hits = 0 + 1
read hits (0)
P1 P2
hits = 1
hits = 0
time
 Kết quả cuối cùng không dự đoán được !
 P1 và P2 chia sẻ biến chung hits
Simpo PDF Merge and Split Unregistered Version - 
5Miền găng (critical section)
hits = 0 + 1
read hits (0)
hits = 0 + 1
read hits (0)
P1 P2
CSCS
CS là đoạn chương trình có khả năng gây ra hiện
tượng race condition
Simpo PDF Merge and Split Unregistered Version - 
6Giải pháp tổng quát
Bảo đảm tính “độc quyền truy xuất” miền găng
tại một thời điểm
hits = hits + 1
P1 P2
hits = 2
hits = 0
time
hits = hits + 1
Simpo PDF Merge and Split Unregistered Version - 
7Mô hình đảm bảo độc quyền truy xuất
Kiểm tra và dành quyền vào CS
CS;
Từ bỏ quyền sử dụng CS
Simpo PDF Merge and Split Unregistered Version - 
8Rendez-Vous
Làm thế nào bảo đảm trình tự thực hiện Job1 -
Job2 ?
P1 P2
Job1;
Job2;
Simpo PDF Merge and Split Unregistered Version - 
9Giải pháp
Hai tiến trình cần trao đổi thông tin về diễn tiến
xử lý
P1 P2
Job1;
Job2;
Simpo PDF Merge and Split Unregistered Version - 
10
Mô hình tổ chức phối hợp hoạt động giữa hài 
tiến trình
P1 P2
Job1; Chờ ;Báo 
hiệu ; Job2;
Simpo PDF Merge and Split Unregistered Version - 
11
Bài toán đồng bộ hoá
 Nhiều tiến trình chia sẻ tài nguyên
chung đồng thời :
 Tranh chấp ?
 Nhu cầu “độc quyền truy xuất” (mutual
exclusion)
 Các tiến trình phối hợp hoạt động :
 Tương quan diễn tiến xử lý ?
 Nhu cầu “hò hẹn” (rendez-vous)
Simpo PDF Merge and Split Unregistered Version -