Bài giảng Nguyên lý hệ điều hành - Nguyễn Hải Châu - Tuần 2: Tiến trình

11
Nguyên lý hệ điều hành
Nguyễn Hải Châu
Khoa Công nghệ thông tin
Trường Đại học Công nghệ
2
Khái niệm tiến trình
3
Tiến trình là gì?
z Thuật ngữ: Process 
(tiến trình/quá trình)
z Là một chương trình 
đang được thực hiện
z Được xem là đơn vị
làm việc trong các HĐH
z Có hai loại tiến trình:
z Tiến trình của HĐH
z Tiến trình của NSD
4
Tiến trình gồm có…
z Đoạn mã lệnh (code, có sách gọi là text)
z Đoạn dữ liệu
z Đoạn ngăn xếp và heap (stack/heap)
z Các hoạt động hiện tại được thể hiện qua 
con đếm lệnh (IP) và nội dung các thanh ghi
(registers) của bộ xử lý
z Chú ý:
z Tiến trình là thực thể chủ động
z Chương trình là thực thể bị động
5
Trạng thái tiến trình
terminatednew
ready running
waiting
admitted exit
I/O hoặc sự kiện
đã hoàn tất
Bị ngắt
(Interrupt)
Chờ I/O hoặc
sự kiện
Lập lịch
6
Khối điều khiển tiến trình
z Thuật ngữ: Process 
Control Block (PCB)
z Các thông tin:
z Trạng thái tiến trình
z Con đếm
z Các thanh ghi
z Thông tin về lập lịch
z Thông tin về bộ nhớ
z Thông tin accounting
z Thông tin vào/ra
Số hiệu tiến trình (Process 
number)
Con đếm (program counter)
Các thanh ghi (registers)
Giới hạn bộ nhớ
Danh sách các tệp đang mở
…..
Con trỏ Trạng thái tiến trình
27
Lập lịch tiến trình
8
Tại sao phải lập lịch?
z Số lượng NSD, số lượng tiến trình luôn lớn
hơn số lượng CPU của máy tính rất nhiều
z Tại một thời điểm, chỉ có duy nhất một tiến
trình được thực hiện trên một CPU
z Vấn đề: 
z Số lượng yêu cầu sử dụng nhiều hơn số lượng tài
nguyên đang có (CPU)
z Do đó cần lập lịch để phân phối thời gian sử dụng
CPU cho các tiến trình của NSD và hệ thống
9
Hàng chờ lập lịch
z Thuật ngữ: Queue
z Các tiến trình chưa được phân phối sử dụng
CPU sẽ được đưa vào hàng chờ (queue)
z Có thể có nhiều hàng chờ trong hệ thống: 
Hàng chờ sử dụng CPU, hàng chờ sử dụng
máy in, hàng chờ sử dụng ổ đĩa CD…
z Trong suốt thời gian tồn tại, tiến trình phải di
chuyển giữa các hàng chờ
10
Hàng chờ lập lịch tiến trình
Hàng chờ sẵn
sàng thực hiện
Hàng chờ vào/ra Yêu cầu vào/ra
Hết thời gian
sử dụng CPU
Tạo một tiến
trình con
Chờ ngắt
CPU
Vào/ra
Tiến trình con 
thực hiện
Ngắt xuất hiện
11
Phân loại các bộ lập lịch
z Bộ lập lịch dài hạn (long-term scheduler)
z Thường dùng trong các hệ xử lý theo lô
z Đưa tiến trình từ spool vào bộ nhớ trong
z Bộ lập lịch ngắn hạn (short-term scheduler)
z Còn gọi là bộ lập lịch CPU
z Lựa chọn tiến trình tiếp theo được sử dụng CPU
z Bộ lập lịch trung hạn (medium-term scheduler)
z Hay còn gọi là swapping (tráo đổi)
z Di chuyển tiến trình đang trong trạng thái chờ giữa
bộ nhớ trong và bộ nhớ ngoài 12
Minh họa bộ lập lịch trung hạn
CPU
Hàng chờ vào/ra
Hàng chờ sẵn
sàng thực hiện
Các tiến trình
đang thực hiện
dở bị swap out
Vào/ra
swap outswap in
313
Hàng chờ lập lịch tiến trình
Hàng chờ sẵn
sàng thực hiện
Hàng chờ vào/ra Yêu cầu vào/ra
Hết thời gian
sử dụng CPU
Tạo một tiến
trình con
Chờ ngắt
CPU
Vào/ra
Tiến trình con 
thực hiện
Ngắt xuất hiện
Các tiến trình đang thực
hiện dở bị swap out
swap outswap in
14
Chuyển trạng thái
z Thuật ngữ: Context switch
z Xảy ra khi một tiến trình A bị ngắt ra khỏi
CPU, tiến trình B bắt đầu được sử dụng CPU
z Cách thực hiện:
z Nhân HĐH ghi lại toàn bộ trạng thái của A, lấy từ
PCB (khối điều khiển tiến trình) của A
z Đưa A vào hàng chờ
z Nhân HĐH nạp trạng thái của B lấy từ PCB của B
z Thực hiện B
15
Chuyển trạng thái
z Việc chuyển trạng thái, nói chung, là lãng phí
thời gian của CPU
z Do đó việc chuyển trạng thái cần được thực
hiện càng nhanh càng tốt
z Thông thường thời gian chuyển trạng thái
mất khoảng 1-1000 micro giây
16
Các thao tác với
tiến trình
17
Tạo tiến trình
z HĐH cung cấp hàm create-process để tạo
một tiến trình mới
z Tiến trình gọi đến hàm create-process là tiến
trình cha (parent process)
z Tiến trình được tạo ra sau khi thực hiện hàm
create-process là tiến trình con (child process)
z Sau khi tiến trình con được tạo, tiến trình cha 
có thể:
z Chờ tiến trình con kết thúc rồi tiếp tục thực hiện
z Thực hiện “song song” với tiến trình con
18
Cây tiến trình
z Tiến trình cha có thể có
nhiều tiến trình con
z Mỗi tiến trình con chỉ có
một tiến trình cha
z Các tiến trình con có
thể tạo ra các tiến trình
con khác…
P1
P11 P12
P121 P122P111
P1111 P1112
419
Minh họa tiến trình cha và con
create-process
Gọi exit để kết thúc
Tiến trình
cha gọi
Tiến trình con
Có thể gọi hoặc
không gọi wait để
chờ/không chờ
tiến trình con kết thúc
20
Kết thúc tiến trình
z Một tiến trình kết thúc khi:
z Thực hiện xong và gọi hàm hệ thống exit (kết
thúc bình thường)
z Gọi đến hàm abort hoặc kill (kết thúc bất thường
khi có lỗi hoặc có sự kiện)
z Bị hệ thống hoặc tiến trình cha áp dụng hàm
abort hoặc kill do:
z Sử dụng quá quota tài nguyên
z Tiến trình con không còn cần thiết
z Khi tiến trình cha đã kết thúc (trong một số HĐH)
21
Minh họa tiến trình trong UNIX
#include 
main()
{
int pid=fork(); /* Tạo tiến trình mới bằng hàm fork() */
if (pid<0) { perror(“Cannot create process”); return(-1); }
else if (pid==0) { /* Tiến trình con */
execlp();
}
else { /* Tiến trình cha */
wait(NULL); /* Nếu không có lệnh này tiến trình cha thực hiện
“song song” với tiến trình con */
printf(“Child completed\n”);
return(0);
}
} 22
Hợp tác giữa các tiến trình
z Các tiến trình có thể hoạt động độc lập hoặc
hợp tác với nhau
z Các tiến trình cần hợp tác khi:
z Sử dụng chung thông tin
z Thực hiện một số nhiệm vụ chung
z Tăng tốc độ tính toán
z …
z Để hợp tác các tiến trình, cần có các cơ chế
truyền thông/liên lạc giữa các tiến trình
(Interprocess communication – IPC)
23
Truyền thông giữa các
tiến trình (IPC)
24
Các hệ thống truyền thông điệp
z Cho phép các tiến trình truyền thông với
nhau qua các toán tử send và receive
z Các tiến trình cần có tên để tham chiếu
z Cần có một kết nối (logic) giữa tiến trình P và
Q để truyền thông điệp
z Một số loại truyền thông:
z Trực tiếp hoặc gián tiếp
z Đối xứng hoặc không đối xứng
z Sử dụng vùng đệm tự động hoặc không tự động
525
Truyền thông trực tiếp
z Hai toán tử
z send(P, msg): Gửi msg đến tiến trình P
z receive(Q, msg): Nhận msg từ tiến trình Q
z Cải tiến:
z send(P, msg): Gửi msg đến tiến trình P
z receive(id, msg): Nhận msg từ bất kỳ tiến trình
nào
26
Minh họa truyền thông trực tiếp
z Mỗi kết nối được thiết
lập cho một cặp tiến
trình duy nhất
z Mỗi tiến trình chỉ cần
biết tên/số hiệu của tiến
trình kia là truyền thông
được
z Tồn tại duy nhất một
kết nối giữa một cặp
tiến trình
P1
P2
P3
P6
P5 P4
27
Truyền thông gián tiếp
z Các thông điệp được gửi và nhận qua các
hộp thư (mailbox) hoặc qua các cổng (port)
z Hai toán tử:
z send(A, msg): Gửi msg đến hộp thư A
z receive(B, msg): Nhận msg từ hộp thư B
z Minh họa: Topo mạng hình sao
28
Minh họa truyền thông gián tiếp
z Hai tiến trình có kết nối
nếu sử dụng chung một
hộp thư
z Một kết nối có thể sử
dụng cho nhiều tiến
trình (>=2)
z Nhiều kết nối có thể tồn
tại giữa một cặp tiến
trình (nếu sử dụng các
hộp thư khác nhau)
P1
P2
P3
P6
P5 P4
Hộp
thư
A Hộp
thư
B
29
Vấn đề đồng bộ hóa
z Thuật ngữ: Synchronization
z Liên quan tới phương thức cài đặt các toán
tử send và receive:
z Phương thức có chờ (blocking)
z Phương thức không chờ (non-blocking)
30
Các phương thức send/receive
Tiến trình nhận trả
lại kết quả là msg
(nếu nhận được) 
hoặc báo lỗi (nếu
chưa nhận được)
Tiến trình truyền không
phải chờ msg đến đích
để tiếp tục thực hiện
Non-blocking
Tiến trình nhận
tạm dừng thực
hiện cho đến khi
msg được chuyển
tới
Tiến trình truyền thông
điệp chờ đến khi msg
được nhận hoặc msg
được phân phát đến
hộp thư
Blocking
receive(Q, msg)send(P, msg)
631
Vấn đề sử dụng vùng đệm
z Các thông điệp nằm trong hàng chờ tạm thời
z Cỡ của hàng chờ:
z Chứa được 0 thông điệp: send blocking
z Chứa được n thông điệp: send non-blocking cho
đến khi hàng chờ có n thông điệp, sau đó send 
blocking
z Vô hạn: send non-blocking
32
Luồng (thread)
z Sinh viên tự tìm hiểu trong giáo trình trang
33
Tóm tắt
z Khái niệm tiến trình
z Các trạng thái, chuyển trạng thái tiến trình
z Khối điều khiển tiến trình
z Lập lịch tiến trình, các loại bộ lập lịch
z Truyền thông giữa các tiến trình
z Gián tiếp, trực tiếp
z Blocking và non-blocking (đồng bộ hóa)
z Vấn đề sử dụng vùng đệm (buffer)
34
Bài tập
z Viết chương trình C trong Linux/Unix tạo ra
16 tiến trình con. Tiến trình cha chờ cho 16 
tiến trình con này kết thúc rồi mới kết thúc
bằng hàm exit. Sử dụng các hàm fork và
wait để thực hiện yêu cầu.
z Hãy tìm một số ví dụ thực tế minh họa cho
các khái niệm lập lịch/hàng chờ trong tình
huống có nhiều người sử dụng và ít tài
nguyên.
35
Bài tập
z Hãy viết chương trình minh họa cho các cơ
chế truyền thông non-blocking, blocking
z Hãy viết chương trình minh họa các cơ chế
truyền thông điệp sử dụng buffer có độ dài n
trong hai trường hợp: n>0 và n=0
z Chú ý: Để làm hai bài tập trên cần sử dụng
hai tiến trình; có thể thực hiện bài tập với
UNIX/Linux hoặc Windows