NGUYÊN LÝ HỆ ĐIỀU HÀNH
(3 Tín chỉ)
GV: Đỗ Công Đức
Khoa khoa học máy tính
Chương 2: QUẢN LÝ TIẾN TRÌNH
2.1. Các mô hình xử lý đồng hành
2.2. Tổ chức và quản lý tiến trình
2.3. Điều phối tiến trình
2.4. Tài nguyên găng và đoạn găng
2.5. Các giải pháp về đồng bộ hóa
2.6. Bế tắc và chống bế tắc
6/28/2014
Chương 2. Quản lý tiến trình
2
CÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH
2.1.1 Nhu cầu xử lý đồng hành (1/2)
Đa số các HĐH hiện nay đều cho phép người dùng xử lý nhiều tác vụ
đồng thời cùng một lúc trên máy tính để:
Tăng hiệu suất sử dụng CPU: các công việc phải trải qua nhiều chu
kỳ xử lý (xử dụng CPU) và chu kỳ nhập xuất (IO) xen kẽ nhau
CPU
IO
IO
CPU
Chương 2. Quản lý tiến trình
3
CÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH
2.1.1 Nhu cầu xử lý đồng hành (2/2)
Tăng tốc độ xử lý: xử lý song song nếu được xây dựng thành nhiều
modul hoạt động đồng thời thì sẽ tiết kiệm được thời gian xử lý
-Ví dụ: Tính giá trị của biểu thức a*b + c*d
Nếu tiến hành song song tính a*b và c*d thì giải quyết bài toán nhanh
hơn tính tuần tự a*b, c*d và sau đó mới tính tổng
Trong các trường hợp đó, cần có một mô hình xử lý đồng hành thích
hợp. Trên máy tính có cấu hình nhiều CPU, hỗ trợ xử lý song song
(multiprocessing) thật sự, điều này sẽ giúp tăng hiệu quả thi hành của
hệ thống đáng kể
6/28/2014
Chương 2. Quản lý tiến trình
4
CÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH
Tiến trình
4 con trỏ lệnh
B
C
A
B
C
D
D
(a)
6/28/2014
(b)
Chương 2. Quản lý tiến trình
D
C
B
A
Thời gian
(c)
6
S0
S1
S2
S3
S4
S5
S6 S7
…. Sn-1
Sn
Sn+1
….
Các trạng thái này nhất thiết không phải liên tiếp. Chương trình nào
thì tạo ra tiến trình đó, gồm tiến trình của hệ thống và tiến trình của
người sử dụng
6/28/2014
Chương 2. Quản lý tiến trình
+ Tiến trình song song có quan hệ thông tin: trong quá trình hoạt
động các tiến trình thường trao đổi thông tin với nhau
+ Tiến trình song song phân cấp: trong khi hoạt động nó sản sinh ra
một tiến trình nữa và hoạt động song song chính nó. Tiến trình khởi
tạo là tiến trình cha, tiến trình được tạo ra gọi là tiến trình con
+ Tiến trình song song đồng mức: sử dụng chung tài nguyên theo
nguyên tắc lần lược, mỗi tiến trình sau một khoảng thời gian chiếm
giữ tài nguyên phải tự động trả lại tài nguyên cho tiến trình kia
6/28/2014
Chương 2. Quản lý tiến trình
10
TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH
P1
P2
Time
P3
a. Trong hệ thống uniprocessor
P1
P2
Time
P3
b. Trong hệ thống multiprocessor
Khảo sát hoạt động của tiến trình song hệ thống uniprocessor. Đối với
người sử dụng thì trong hệ thống chỉ có hai nhóm tiến trình
Chương 2. Quản lý tiến trình
12
TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH
2.2.2 Các mô hình tiến trình (2/4)
P1
P2
P3
t1
t2
t3
t4
6/28/2014
t5
t6
Giả sử trong hệ thống có 3 tiến trình
sẵn sàng P1, P2, P3 quá trình chuyển:
Thời điểm Trạng thái các tiến trình
t1
P1: được cấp processor
Tiến trình P1:
Tiến trình P2:
Tiến trình P3:
a+0
b+0
c+0
a+1
b+2
c+1
a+3
b+3
c+4
a+5
c+6
6/28/2014
Chương 2. Quản lý tiến trình
14
TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH
2.2.2 Các mô hình tiến trình (4/4)
Processor thực hiện xen kẽ các chỉ thị của 3 tiến trình P1,P2,P3 từ
lệnh đầu tiên đến lệnh cuối cùng, cho đến khi tất cả các chỉ thị của 3
tiến trình đều thực hiện. Nhưng khoảng thời gian từ khi con trỏ lệnh
=a+0 đến khi =a+1, hay từ khi =b+0 đến khi =b+2… là rất nhỏ, nên hệ
thống có “cảm giác” 3 tiến trình P1, P2, P3 hoạt động đồng thời
Mô hình thực hiện đồng thời của tiến trình uniprocessor có 2 thuận lợi:
-Tiết kiệm được bộ nhớ: vì nó chỉ nạp các tiến trình cần thiết sau đó
thực hiện bị ngắt thì bộ điều phối thu hồi lại processor và chọn một
tiến trình ở trạng thái Not Running để cấp processor cho nó và chuyển
nó sang trạng thái Running. Tiến trình bị thu hồi processor sẽ được
chuyển về lại trạng thái Not Running
6/28/2014
Chương 2. Quản lý tiến trình
16
TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH
2.2.3 Các trạng thái của tiến trình
Tiến trình 2 trạng thái: Not Running và Running
Queue
Dispatch Processor
Enter
Exit
Pause
Sơ đồ chuyển tiến trình vào hàng đợi
Tại một thời điểm xác định chỉ duy nhất một tiến trình ở trạng thái
Runnig, nhưng có nhiều tiến trình ở trạng thái Not Running, các tiến
trình ở trạng thái Not Running được chứa trong một hàng đợi (Queue).
Tiến trình đang ở trạng thái Running bị chuyển sang trạng thái Not
Running sẽ được đưa vào hàng đợi
6/28/2014
đầu
thực
cấp
pháttrình
đầyđểđủ
tài
nguyên
chỉ
Ready
Running
4. Tiến
Tiến
trình
bịbắt
bộthành
điều xử
phối
3 và
kết
thúc
hiện/xử
lý
thiếu
processor
5.
trình
đang chờ
mộtthời
sự
thuTiến
tác nhập/xuất
nhập/xuất
kết
processor,
để tác
cấp
phát cho tiến
thúc
trìnhtrình
khácđợi đã kết thúc
Sơ đồ chuyển tiến trình 3 trạng thái tiến
6/28/2014
Chương 2. Quản lý tiến trình
18
TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH
2.2.3 Các trạng thái của tiến trình
Tiến trình 3 trạng thái: Ready, Running, Blocked
Ready Queue
Dispatch
Admit
Release
Processor
Time-out
Running
Activate
End
Suspend
Blocked
Suspend
6/28/2014
Chương 2. Quản lý tiến trình
20
TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH
2.2.3 Các trạng thái của tiến trình
Tổ chức Queue để lưu các tiến trình chưa hoạt động là cần thiết,
nhưng tồn tại quá nhiều tiến trình trong Queue, sẽ lãng phí không
đủ bộ nhớ để nạp các tiến trình khác.
Các tiến trình trong Queue đang chiếm giữ tài nguyên của hệ thống,
mà những tài nguyên này các tiến trình khác đang cần, rõ ràng sử
dụng tài nguyên không hợp lý, làm cho hệ thống thiếu tài nguyên
trầm trọng và có thể làm cho hệ thống bế tắc. HĐH thiết kế thêm
trạng thái Suspend. Trạng thái này rất cần thiết cho các hệ thống sử
dụng kỹ thuật Swap trong việc cấp phát bộ nhớ cho các tiến trình
6/28/2014
Blocked
suspend
Blocked
Activate
6/28/2014
Chương 2. Quản lý tiến trình
22
TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH
2.2.3 Các trạng thái của tiến trình
Trạng thái Blocked-suspend: tiến trình đang bị chứa trên bộ nhớ phụ
(đĩa) và đang đợi một sự kiện nào đó
Trạng thái Ready-suspend: tiến trình đang bị chứa trên bộ nhớ phụ
nhưng sẵn sàng thực hiện ngay sau khi được nạp vào bộ nhớ chính
Blocked sang Blocked-suspend: Nếu không còn tiến trình ready
trong bộ nhớ chính và bộ nhớ chính không còn không gian nhớ trống
thì phải có ít nhất một tiến trình blocked bị chuyển ra ngoài, blockedsuspend, để dành bộ nhớ cho một tiến trình không bị khoá (not
blocked) khác.
6/28/2014
Chương 2. Quản lý tiến trình
23
trong bộ nhớ chính, phải biết được các thuộc tính của tiến trình cần
thiết cho việc quản lý tiến trình của nó để quản lý và điều khiển.
Các bảng thông tin cho I/O table, file table, Memory table cũng tương
tự như Process table để quản lý và điều khiển chúng.
6/28/2014
Chương 2. Quản lý tiến trình
25
Copyright: Tài liệu đại học ©