Nguyên lí hệ điều hành - Tiến trình

TIẾN TRÌNH
ThS. Nguyễn Thị Hải Bình
Khoa CNTT, ĐH Giao thông vận tải
Email: calmseahn@gmail.com
Website: calmseahn.weebly.com
NỘI DUNG
• Tiến trình là gì?
• Trạng thái của tiến trình
• Khối điều khiển tiến trình (PCB)
• Thao tác trên tiến trình
• Điều phối (lập lịch) tiến trình
• Truyền thông liên tiến trình
2
TIẾN TRÌNH LÀ GÌ?
• Tiến trình là chương trình đang được thực hiện
• Được xem là đơn vị làm việc trong các Hệ điều
hành
• Chương trình vs. Tiến trình
• Chương trình
• Thực thể tĩnh
• Không sở hữu tài nguyên cụ thể
• Tiến trình
• Thực thể động
• Được cấp một số tài nguyên (memory, CPU Registers) để chứa
dữ liệu và thực hiện lệnh
3
TIẾN TRÌNH LÀ GÌ?
• Các hoạt động hiện tại của tiến trình được thể hiện 
qua bộ đếm chương trình (program counter) và nội 
dung các thanh ghi (registers) của bộ xử lý
4
PROCESS IN MEMORY
• Text section (Đoạn mã lệnh)
• Chứa mã lệnh của chương trình (compiled 
program code)
• Data section (Đoạn dữ liệu)
• Chứa các biến toàn cục (global variables) và
biến static
• Khởi tạo trước khi thực thi hàm main
• Heap
• Dành cho cấp phát bộ nhớ động (dynamic 
memory allocation)
• Được quản lý thông qua các hàm: new, 
delete, malloc, free, etc.
• Stack
• Dành cho các biến cục bộ (local variables)
Figure credit: Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Ninth Edition ", Chapter 3 5
6Figure credit: https://cg2010studio.wordpress.com/2011/06/26/process-in-memory/
TRẠNG THÁI CỦA TIẾN TRÌNH
• Khi thực hiện, trạng thái của tiến trình thay đổi
• Trạng thái của tiến trình được xác định bằng hoạt
động hiện thời của nó
• Tiến trình có thể nhận 1 trong 5 trạng thái sau:
• New (Khởi tạo) – tiến trình đang được khởi tạo
• Ready (Sẵn sàng) – tiến trình đang chờ được cấp CPU để
thực thi lệnh của mình
• Running (Thực hiện) – các câu lệnh của tiến trình đang
được thực hiện
• Waiting (Chờ đợi) – tiến trình tạm dừng để chờ một tài
nguyên hoặc một sự kiện
• Terminated (Kết thúc) – tiến trình được thực hiện xong
7
8Figure credit: Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Ninth Edition ", Chapter 3
KHỐI ĐIỀU KHIỂN TIẾN TRÌNH
• Process Control Block (PCB)
• Cấu trúc thông tin cho phép xác định duy nhất một
tiến trình
9Figure credit: Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Ninth Edition ", Chapter 3
KHỐI ĐIỀU KHIỂN TIẾN TRÌNH
• Các thông tin trong PCB
• Process state (Trạng thái của tiến trình)
• Program counter (Bộ đếm chương trình)
• CPU registers (Các thanh ghi)
• CPU scheduling information (Thông tin điều phối tiến trình)
• Mức độ ưu tiên của tiến trình, vị trí trong hàng đợi, 
• Memory management information (Thông tin về bộ nhớ của
tiến trình)
• Accounting information (thông tin thống kê): 
• Thời gian sử dụng CPU, giới hạn thời gian
• I/O status information 
• Danh sách các thiết bị vào/ra được cấp phát cho tiến trình, các file 
đang mở
10
11
Figure credit: 
THAO TÁC TRÊN TIẾN TRÌNH
• Tạo mới tiến trình
• Kết thúc tiến trình
12
TẠO MỚI TIẾN TRÌNH
• Khi tiến trình mới được đưa vào hệ thống, Hệ điều
hành tạo ra
• Gán số định danh cho tiến trình được tạo mới và tạo
một ô trong bảng tiến trình
• Tạo không gian nhớ cho tiến trình và PCB
• Khởi tạo PCB
• Liên kết PCB của tiến trình vào các danh sách quản lý
• Tiến trình được tạo ra khi
• Khởi tạo hệ thống (OS is boosted)
• Tiến trình con
• Tiến trình do người dùng tạo ra
13
TIẾN TRÌNH CON
• Một tiến trình có thể tạo ra nhiều tiến trình mới cùng
hoạt động
• Tiến trình tạo: tiến trình cha (parent process)
• Tiến trình được tạo: tiến trình con (children)
• Cây tiến trình (Tree of process)
• Phân phối tài nguyên
• Tiến trình con lấy tài nguyên từ hệ điều hành
• Tiến trình con lấy tài nguyên từ tiến trình cha
• Một phần tài nguyên
• Tất cả tài nguyên
• Thực hiện
• Tiến trình cha tiếp tục thực hiện đồng thời với tiến trình con
• Tiến trình cha đợi tiến trình con kết thúc
14
KẾT THÚC TIẾN TRÌNH
• Kết thúc bình thường: yêu cầu HDH kết thúc mình 
bằng cách gọi lời gọi hệ thống exit()
• Bị kết thúc:
• Bị tiến trình cha kết thúc
• Do các lỗi
• Yêu cầu nhiều bộ nhớ hơn so với số lượng hệ thống có 
thể cung cấp
• Thực hiện lâu hơn thời gian giới hạn
• Do quản trị hệ thống hoặc hệ điều hành kết thúc
15
ĐIỀU PHỐI TIẾN TRÌNH
• Mục tiêu
• Các hàng đợi điều phối (Scheduling queues)
• Bộ điều phối (Scheduler)
16
ĐIỀU PHỐI TIẾN TRÌNH
• Thuật ngữ: Process scheduling
• Còn gọi là lập lịch tiến trình
• Mục tiêu:
• Sử dụng tối đa thời gian CPU
• Người dùng có thể tương tác với tiến trình
• Bộ điều phối tiến trình (Process scheduler) lựa
chọn một tiến trình để thực hiện
• Trong hệ thống một processor
• Chỉ có 1 tiến trình được thực hiện
• Các tiến trình khác phải chờ tới khi CPU tự do
17
CÁC HÀNG ĐỢI ĐIỀU PHỐI
• Các tiến trình chưa được phân phối sử dụng CPU sẽ
được đưa vào hàng đợi điều phối (Scheduling 
• Hệ thống có nhiều hàng đợi dành cho các tiến trình
• Job queue: hàng đợi dành cho tất cả các tiến trình trong
hệ thống
• Ready queue: bao gồm các tiến trình đang ở trạng thái
sẵn sàng
• Device queues: hàng đợi dành cho các tiến trình đang
chờ đợi thiết bị vào/ra
• Mỗi thiết bị có hàng đợi riêng biệt
18
19Figure credit: Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Ninth Edition ", Chapter 3
CÁC HÀNG ĐỢI ĐIỀU PHỐI
• Trong suốt thời gian tồn tại tiến trình di chuyển
giữa các hàng đợi
20
BỘ ĐIỀU PHỐI – SCHEDULER
21
Lựa chọn tiến trình trong các hàng đợi
• Điều phối dài hạn (Job scheduler; Long-term scheduler)
• Điều phối ngắn hạn (CPU scheduler; Short-term scheduler)
BỘ ĐIỀU PHỐI DÀI HẠN
• Thuật ngữ: Job scheduler, long-term scheduler
• Trong hệ thống lô, số lượng tiến trình đưa vào hệ
thống thường nhiều hơn số lượng tiến trình có thể
thực thi ngay lập tức
• Các tiến trình này được lưu trữ tạm thời ở một
thiết bị lưu trữ (mass-storage device), thường là ổ 
đĩa (disk)
• Bộ điều phối dài hạn lựa chọn tiến trình từ nhóm
này để tải vào bộ nhớ
22
BỘ ĐIỀU PHỐI DÀI HẠN
• Bộ điều phối dài hạn kiểm soát mức độ đa chương
trình (số lượng tiến trình trong bộ nhớ)
• Nếu mức độ đa chương trình ổn định, bộ điều phối dài
hạn chỉ được gọi khi có một tiến trình rời hệ thống
• Điều phối không thường xuyên
• Đơn vị giây/phút
• Lựa chọn tiến trình:
• Tiến trình thiên về vào/ra (I/O bound)
• Tiến trình thiên về CPU (CPU bound)
• Cần lựa chọn cả 2 loại tiến trình
• Trong nhiều hệ thống, không có bộ điều phối dài hạn
• Ví dụ: Time-sharing system, như: Unix, Microsoft Windows 
23
BỘ ĐIỀU PHỐI NGẮN HẠN
• Thuật ngữ: CPU scheduler, short-term scheduler
• Lựa chọn một tiến trình từ ready queue và phân
phối CPU cho nó
• Được thực hiện thường xuyên
• Phải thực hiện nhanh
• Thuật toán lựa chọn tiến trình?
24
BỘ ĐIỀU PHỐI TRUNG HẠN
• Thuật ngữ: Medium-term scheduler
• Trong một số hệ chia sẻ thời gian (time-sharing 
systems), có thêm bộ điều phối trung hạn
• Nhiệm vụ
• Đưa một hoặc một số tiến trình ra khỏi bộ nhớ (làm
giảm mức độ đa chương trình)
• Sau đó đưa tiến trình trở lại và tiếp tục thực hiện
• Mục đích
• Giải phóng vùng nhớ, tạo vùng nhớ tự do rộng hơn
25
BỘ ĐIỀU PHỐI TRUNG HẠN
26
CHUYỂN ĐỔI GIỮA CÁC TIẾN TRÌNH
• Thông tin về tiến trình hiện thời (chứa trong PCB) được
gọi là ngữ cảnh (context) của tiến trình
• Việc chuyển giữa tiến trình còn được gọi là chuyển đổi
ngữ cảnh (context switch)
• Xảy ra khi:
• Có ngắt
• Tiến trình gọi lời gọi hệ thống
• Trước khi chuyển sang thực hiện tiến trình khác, ngữ 
cảnh được lưu vào PCB
• Khi được cấp phát CPU thực hiện trở lại, ngữ cảnh 
được khôi phục từ PCB vào các thanh ghi và bảng 
tương ứng
27
28Figure credit: Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Ninth Edition ", Chapter 3
TRUYỀN THÔNG LIÊN TIẾN TRÌNH
• Phân loại tiến trình
• Hợp tác tiến trình
• Hai mô hình của truyền thông liên tiến trình
• Shared memory systems
• Message passing systems
29
PHÂN LOẠI TIẾN TRÌNH
• Tiến trình tuần tự
• Điểm bắt đầu của tiến trình này nằm sau điểm kết thúc
của tiến trình kia
• Tiến trình song song
• Điểm bắt đầu của tiến trình này nằm giữa điểm bắt đầu
và kết thúc của tiến trình kia
• Tiến trình độc lập
• Tiến trình hợp tác
30
HỢP TÁC TIẾN TRÌNH
• Mục đích
• Chia sẻ thông tin
• Tăng tốc độ tính toán
• Module hoá
• Tiện dụng
• Yêu cầu cơ chế:
• Truyền thông giữa các tiến trình
• Đồng bộ hoá hoạt động của các tiến trình
31
HAI MÔ HÌNH CƠ BẢN CỦA TRUYỀN
THÔNG LIÊN TIẾN TRÌNH
• Shared Memory 
• Một vùng nhớ chung được thiết lập cho các tiến trình hợp tác
• Các tiến trình trao đổi thông tin bằng việc đọc (reading) và ghi
(writing) dữ liệu vào vùng nhớ chung
• Nhanh
• Khó set up
• Không dùng được trong hệ đa máy tính (multiple computers)
• Message Passing
• Các tiến trình trao đổi thông tin thông qua hình thức truyền
thông điệp
• Dùng khi chia sẻ lượng thông tin nhỏ, hoặc trên hệ đa MT
• Dễ lập trình hơn Shared Memory
• Chậm vì cần đến lời gọi hệ thống (System calls)
32
33