21
CHƯƠNG 2. QUẢN LÝ TIẾN TRÌNH
2.1. Khái niệm tiến trình
2.1.1. Tiến trình và các loại tiến trình
a. Tiến trình (process):
Tiến trình là một khái niệm cơ bản trong hệ điều hành. Tiến trình là một chương trình
đang chạy. Mỗi tiến trình có không gian địa chỉ riêng (address space), đó là vùng bộ nhớ dành
riêng cho tiến trình, tiến trình có thể đọc và ghi trong vùng bộ nhớ này. Vùng bộ nhớ này
chứa chương trình, dữ liệu của chương trình và stack.
Trong hệ thống chia xẻ thời gian (timesharing system), hệ điều hành định kỳ ngưng tạm
thời (treo, suspend) một tiến trình đang chạy và cho một tiến trình khác chạy.
Khi tiến trình được chạy lại, tiến trình được khôi phục lại trạng thái giống như trước khi
bị ngưng, do vậy tất cả các thông tin về tiến trình sẽ được cất giữ trước khi bị treo. Các thông
tin này được lưu trong bảng điều hành (operating system table) của hệ điều hành, mỗi mục
trong bảng điều hành chứa thông tin của một tiến trình.
Hàm gọi hệ thống liên quan đến tiến trình về cơ bản gồm có tạo tiến trình và chấm dứt
tiến trình. Một tiến trình có thể tạo những tiến trình khác, các tiến trình này được gọi là tiến
trình con (child process), và ta có một cây tiến trình.
Hình 2.1. Cây tiến trình.
Mỗi người được quyền sử dụng hệ thống sẽ có một số hiệu nhận diện UID (User
Identification), chỉ có người quản trị hệ thống mới được quyền gán UID cho người sử dụng.
Tiến trình khi chạy mang UID của người sử dụng chạy nó. Tiến trình con sẽ có UID giống
như tiến trình cha. Người sử dụng có thể thuộc một nhóm nào đó và cũng có số hiệu nhận
diện nhóm GID (Group Identification).
Trong hệ thống có một UID quan trọng, được gọi là superuser, có quyền cao nhất. Chỉ
có người quản trị hệ thống mới có mật khẩu để trở thành superuser. Superuser có thể vi phạm
bất cứ sự bảo vệ an toàn hệ thống.
b. Các loại tiến trình:
Các tiến trình trong hệ thống có thể chia thành hai loại: tiến trình tuần tự và tiến trình
thác tối đa thời gian xử lý của CPU. Các tiến trình song song xuất hiện trong các hệ điều
hành đa nhiệm đa chương, trên cả hệ thống một CPU và nhiều CPU. Nhưng sự song song
thực, chỉ có ở các hệ thống nhiều CPU, trong hệ thống này mỗi CPU chịu trách nhiệm thực
hiện một tiến trình. Sự song song trên các hệ thống một CPU là sự song song giả, các tiến
trình song song trên hệ thống này thực chất là các tiến trình thay nhau sử dụng CPU, tiến trình
này đang chạy thì có thể dừng lại để nhường CPU cho tiến trình khác chạy và sẽ tiếp tục lại
sau đó khi có được CPU. Đây là trường hợp mà ở trên ta cho rằng: điểm khởi tạo của tiến
trình này nằm ở thân của tiến trình khác.
Hình vẽ sau đây minh họa sự khác nhau, về mặt thực hiện, giữa các tiến trình song
song/ đồng thời trong hệ thống một CPU với các tiến trình song song/ đồng thời trong hệ
thống nhiều CPU.
Trong giáo trình này chúng ta chỉ khảo sát sự hoạt động của các tiến trình song song
(hay đồng thời) trên các hệ thống một CPU.
Đối với người sử dụng thì trong hệ thống chỉ có hai nhóm tiến trình. Thứ nhất, là các
tiến trình của hệ điều hành. Thứ hai, là các tiến trình của chương trình người sử dụng. Các
tiến trình của hệ điều hành hoạt động trong chế độ đặc quyền, nhờ đó mà nó có thể truy xuất
vào các vùng dữ liệu được bảo vệ của hệ thống. Trong khi đó các tiến trình của chương trình
người sử dụng hoạt động trong chế độ không đặc quyền, nên nó không thể truy xuất vào hệ
23
thống, nhờ đó mà hệ điều hành được bảo vệ. Các tiến trình của chương trình người sử dụng có
thể truy xuất vào hệ thống thông qua các tiến trình của hệ điều hành bằng cách thực hiện một
lời gọi hệ thống.
2.1.2. Mô hình tiến trình
Đa số các hệ điều hành đều muốn đưa sự đa chương, đa nhiệm vào hệ thống. Tức là,
trong hệ thống có thể có nhiều chương trình hoạt động đồng thời (concurrence) với nhau. Về
nguyên tắc, để thực hiện được điều này thì hệ thống phải có nhiều CPU, mỗi CPU có nhiệm
vụ thực hiện một chương trình, nhưng mong muốn của hệ điều hành cũng như người sử dụng
là thực hiện sự đa chương trên các hệ thống chỉ có một CPU, và trên thực tế đã xuất hiện
a
P1
P2
P3
t
b
Hình 2.2:
Sự thực hiện đồng thời của các tiế
n trình trong
hệ thống một CPU (a) và hệ thống nhiều CPU (b).
24
Thời điểm Trạng thái các tiến trình
t
1
P
1
: được cấp CPU
t
2
P
1
: bị thu hồi CPU (khi chưa kết thúc)
P
3
: được cấp CPU
t
3
3
ở trên:
Chúng ta đều biết, chức năng cở bản của CPU là thực hiện các chỉ thị máy (machine
instrustion) thường trú trong bộ nhớ chính, các chỉ thị này được cung cấp từ một chương
trình, chương trình bao gồm một dãy tuần tự các chỉ thị. Và theo trên, tiến trình là một bộ
phận của chương trình, nó cũng sở hữu một tập lệnh trong bộ nhớ chính, một con trỏ lệnh,…
Nên xét về bản chất, thì việc chuyển CPU từ tiến trình này sang tiến trình khác thực chất là
việc điều khển CPU để nó thực hiện xen kẽ các chỉ thị bên trong tiến trình. Điều này có thể
thực hiện dễ dàng bằng cách thay đổi hợp lý giá trị của con trỏ lệnh, đó chính là cặp thanh ghi
CS:IP trong các CPU thuộc kiến trúc Intel, để con trỏ lệnh chỉ đến các chỉ thị cần thực hiện
trong các tiến trình. Để thấy rõ hơn điều này ta hãy xem ví dụ sau đây:
Giả sử hệ thống cần thực hiện đồng thời 3 tiến trình P
1
, P
2
, P
3
, bắt đầu từ tiến trình P
1
.
Các chỉ thị của các tiến trình này được nạp vào bộ nhớ tại các địa chỉ như sau:
Tiến trình P
1
: Tiến trình P
2
: Tiến trình P
3
:
a + 0 b + 0 c + 0
P2
P3
t
Hình
2.3: Sự hoạt động “song song” của các tiến trình P
1
, P
2
, P
3.
t
1
t
2
t
3
t
4
t
5
t
6
Để quản lý và điều khiển được một tiến trình, thì hệ điều hành phải biết được vị trí nạp
tiến trình 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ó:
Định vị của tiến trình (process location): định vị của tiến trình phụ thuộc vào chiến
lược quản lý bộ nhớ đang sử dụng. Trong trường hợp đơn giản nhất, tiến trình, hay chính xác
hơn là hình ảnh tiến trình, được lưu giữa tại các khối nhớ liên tục trên bộ nhớ phụ (thường là
đĩa), để tiến trình thực hiện được thì tiến trình phải được nạp vào bộ nhớ chính. Do đó, hệ
điều hành cần phải biết định vị của mỗi tiến trình trên đĩa và cho mỗi tiến trình đó trên bộ nhớ
chính. Trong một số chiến lược quản lý bộ nhớ, hệ điều hành chỉ cần nạp một phần tiến trình
vào bộ nhớ chính, phần còn lại vẫn nằm trên đĩa. Hay tiến trình đang ở trên bộ nhớ chính thì
có một phần bị swap-out ra lại đĩa, phần còn lại vẫn còn nằm ở bộ nhớ chính. Trong các
trường hợp này hệ điều hành phải theo dõi tiến trình để biết phần nào của tiến trình là đang ở
trong bộ nhớ chính, phần nào của tiến trình là còn ở trên đĩa.
Đa số các hệ điều hành hiện nay đều sử dụng chiến lược quản lý bộ nhớ mà trong đó
26
không gian địa chỉ của tiến trình là một tập các block, các block này có thể không liên tiếp
nhau. Tùy theo chiến lược bộ nhớ sử dụng mà các block này có thể có chiều dài cố định
(chiến lược phân phân trang bộ nhớ) hay thay đổi (chiến lược phân đoạn bộ nhớ) hay kết hợp
cả hai. Hệ điều hành cho phép không nạp tất cả các trang (page) và/hoặc các đoạn (segment)
của tiến trình vào bộ nhớ. Do đó, process table phải được duy trì bởi hệ điều hành và phải cho
biết vị trí của mỗi trang/ đoạn tiến trình trên hệ thống. Những điều trên đây sẽ được làm rõ ở
phần chiến lược cấp phát bộ nhớ trong chương Quản lý bộ nhớ của giáo trình này.
Các thuộc tính của tiến trình: Trong các hệ thống đa chương, thông tin về mỗi tiến
trình là rất cần cho công tác quản lý tiến trình của hệ điều hành, các thông tin này có thể
thường trú trong khối quản lý tiến trình. Các hệ điều hành khác nhau sẽ có cách tổ chức PCB
khác nhau, ở đây chúng ta khảo sát một trường hợp chung nhất. Các thông tin trong PCB có
thể được chia thành ba nhóm chính:
Hình 2.4. Ví dụ một PCB.
động, hay nói cách khác là các chỉ thị của tiến trình đang được thực hiện/ xử lý bởi CPU.
Chờ (waitng): Là trạng thái mà tiến trình đang chờ để được cấp phát thêm tài nguyên,
để một sự kiện nào đó xảy ra, hay một quá trình vào/ra kết thúc.
Kết thúc (terminated): Hoàn tất việc thực thi.
Quá trình chuyển trạng thái của các tiến trình trong được mô tả bởi sơ đồ sau:
Hình 2.5. Sơ đồ chuyển trạng thái của tiến trình.
Trong đó:
Admitted: Tiến trình được khởi tạo, được đưa vào hệ thống, được cấp phát đầy đủ tài
nguyên chỉ thiếu CPU.
Scheduler dispatch: Tiến trình được cấp CPU để bắt đầu thực hiện/ xử lý.
Exit: Tiến trình hoàn thành xử lý và kết thúc.
Interrupt: Tiến trình bị bộ điều phối tiến trình thu hồi CPU, do hết thời gian được quyền
sử dụng CPU, để cấp phát cho tiến trình khác.
I/O or event wait: Tiến trình đang chờ một sự kiện nào đó xảy ra hay đang chờ một thao
vào/ra kết thúc hay tài nguyên mà tiến trình yêu cầu chưa được hệ điều hành đáp ứng.
I/O or event completion: Sự kiện mà tiến trình chờ đã xảy ra, thao tác vào/ra mà tiến
trình đợi đã kết thúc, hay tài nguyên mà tiến trình yêu cầu đã được hệ điều hành đáp ứng,
28
Bộ phận điều phối tiến trình thu hồi CPU từ một tiến trình đang thực hiện trong các
trường hợp sau:
- Tiến trình đang thực hiện hết thời gian (time-out) được quyền sử dụng CPU mà bộ
phận điều phối dành cho nó.
- Có một tiến trình mới phát sinh và tiến trình mới này có độ ưu tiên cao hơn tiến trình
hiện tại.
- Có một tiến trình mới phát sinh và tiến trình này mới cần một khoảng thời gian của
CPU nhỏ hơn nhiều so với khoảng thời gian còn lại mà tiến trình hiện tại cần CPU.
Tại một thời điểm xác định trong hệ thống có thể có nhiều tiến trình đang ở trạng thái
ready hoặc waiting nhưng chỉ có một tiến trình ở trạng thái running. Các tiến trình ở trạng thái
- Thu hồi tài nguyên đã cấp phát cho tiến trình.
- Loại bỏ tiến trình ra khỏi danh sách quản lý của hệ thống.
- Huỷ bỏ khối điều khiển tiến trình.
Hầu hết các hệ điều hành đều không cho phép tiến trình con hoạt động khi tiến trình cha
đã kết thúc. Trong những trường hợp như thế hệ điều hành sẽ chủ động việc kết thúc tiến trình
con khi tiến trình cha vừa kết thúc.
2.3.3. Chuyển ngữ cảnh (context switch)
Muốn chuyển quyền sử dụng CPU giữa các tiến trình thì phải thay đổi tiến trình của các
tiến trình. Khi một tiến trình đang ở trạng thái running bị chuyển sang trạng thái khác (ready,
waiting,…) thì hệ điều hành phải tạo ra sự thay đổi trong môi trường làm việc của nó, quá
trình này được gọi là chuyển ngữ cảnh. Sau đây là các bước mà hệ điều hành phải thực hiện
đầy đủ khi thay đổi trạng thái tiến trình:
Hình 2.6. Sơ đồ chuyển ngữ cảnh.
- Lưu (save) ngữ cảnh của CPU, bao gồm thanh ghi bộ đếm chương trình (PC: program
counter) và các thanh ghi khác.
- Cập nhật PCB của tiến trình, sao cho phù hợp với trạng thái mới của tiến trình, bao
gồm trạng thái mới của tiến trình, các thông tin tính toán, vv.
- Di chuyển PCB của tiến trình đến một hàng đợi thích hợp, đế đáp ứng được các yêu
cầu của công tác điều phối tiến trình.
- Chọn một tiến trình khác để cho phép nó thực hiện.
- Cập nhật PCB của tiến trình vừa được chọn thực hiện ở trên, chủ yếu là thay đổi trạng
thái của tiến trình đến trạng thái running.
30
- Cập nhật các thông tin liên quan đến quản lý bộ nhớ. Bước này phụ thuộc vào các yêu
cầu chuyển đổi địa chỉ bộ nhớ đang được sử dụng.
- Khôi phục (Restore) lại ngữ cảnh của CPU và thay đổi giá trị của bộ đếm chương trình
và các thanh ghi khác sao cho phù hợp với tiến trình được chọn ở trên, để tiến trình này có thể
cùng thời điểm. Thí dụ, một người dùng có thể đang soạn thảo, in, và biên dịch cùng một lúc.
2.4.2. Giao tiếp giữa các tiến trình
Thực thi đồng hành của các tiến trình cộng tác yêu cầu các cơ chế cho phép các tiến
trình giao tiếp với các tiến trình khác và đồng bộ hóa các hoạt động của chúng. Đó chính là cơ
chế giao tiếp giữa các tiến trình (Interprocess communication - IPC).
Sau đây chúng ta sẽ tìm hai mô hình giao tiếp giữa các tiến trình là chia sẻ bộ nhớ và
31
truyền thông điệp.
Hình 2.7. Mô hình giao tiếp giữa các tiến trình.
(a) truyền thông điệp. (b) chia sẻ bộ nhớ
2.4.3. Mô hình giao tiếp qua chia sẻ bộ nhớ
Để minh họa khái niệm của các quá trình cộng tác, chúng ta xem xét bài toán người sản
xuất - người tiêu thụ, là mô hình chung cho các tiến trình cộng tác. Tiến trình người sản xuất
cung cấp thông tin được tiêu thụ bởi tiến trình người tiêu thụ. Thí dụ, một chương trình in sản
xuất các ký tự được tiêu thụ bởi trình điều khiển máy in. Một trình biên dịch có thể sản xuất
mã hợp ngữ được tiêu thụ bởi trình hợp ngữ. Sau đó, trình hợp ngữ có sản xuất module đối
tượng, được tiêu thụ bởi bộ nạp.
Để cho phép người sản xuất và người tiêu thụ chạy đồng hành, chúng ta phải có sẵn một
vùng đệm chứa các sản phẩm có thể được điền vào bởi người sản xuất và được lấy đi bởi
người tiêu thụ. Người sản xuất có thể sản xuất một sản phẩm trong khi người tiêu thụ đang
tiêu thụ một sản phẩm khác. Người sản xuất và người tiêu thụ phải được đồng bộ để mà người
tiêu thụ không cố gắng tiêu thụ một sản phẩm mà chưa được sản xuất. Trong trường hợp này,
người tiêu thụ phải chờ cho tới khi các sản phẩm mới được tạo ra.
Nếu độ lớn vùng đệm không bị giới hạn (unbounded-buffer), người tiêu thụ có thể phải
chờ các sản phẩm mới nhưng người sản xuất có thể luôn tạo ra sản phẩm mới. Nhưng với
vùng đệm có kích thước giới hạn (bounded-buffer), người tiêu thụ phải chờ nếu vùng đệm
rỗng, và người sản xuất phải chờ nếu vùng đệm đầy.
Vùng đệm có thể được cung cấp bởi hệ điều hành thông qua việc sử dụng bộ nhớ được
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
/*consume the item in nextConsumed*/
}
2.4.3. Mô hình giao tiếp qua truyền thông điệp
Giao tiếp giữa các tiến trình thông qua việc gửi thông điệp. Để hỗ trợ cơ chế liên lạc
bằng thông điệp, hệ điều hành cung cấp các hàm IPC chuẩn, cơ bản là hai hàm:
Send(message), gửi một thông điệp và Receive(message), nhận một thông điệp.
a. Đặt tên
Các tiến trình muốn giao tiếp phải có cách tham chiếu với nhau. Chúng có thể dùng giao
tiếp trực tiếp hay gián tiếp.
Với giao tiếp trực tiếp, mỗi tiến trình muốn giao tiếp phải đặt tên rõ ràng người gửi và
người nhận của giao tiếp. Trong cơ chế này, các hàm cơ sở send và receive được định nghĩa
như sau:
33
Send(P, message): gửi một thông điệp tới tiến trình P
Receive(Q, message): nhận một thông điệp từ tiến trình Q
Một liên kết giao tiếp trong cơ chế này có những thuộc tính sau:
- Một liên kết được thiết lập tự động giữa mỗi cặp tiến trình muốn giao tiếp.
- Các tiến trình cần biết định danh của nhau khi giao tiếp.
- Một liên kết được nối kết với chính xác hai tiến trình.
- Chính xác một liên kết tồn tại giữa mỗi cặp tiến trình.
Với giao tiếp gián tiếp, một thông điệp được gửi tới và nhận từ các hộp thư (mailboxes),
hay cổng (ports). Một hộp thư có thể được hiển thị trừu tượng như một đối tượng trong đó các
thông điệp có thể được đặt bởi các tiến trình và sau đó các thông điệp này có thể được xóa đi.
Mỗi hộp thư có một định danh duy nhất. Trong cơ chế này, một tiến trình có thể giao tiếp với
một vài tiến trình khác bằng một số hộp thư khác nhau. Hai tiến trình có thể giao tiếp chỉ nếu
chúng chia sẻ cùng một hộp thư. Hàm cơ sở send và receive được định nghĩa như sau:
Send(A, message): gửi một thông điệp tới hộp thư A.
con trỏ thông điệp được giữ) và người gửi có thể tiếp tục thực thi không phải chờ. Tuy nhiên,
liên kết có khả năng chứa giới hạn. Nếu một liên kết đầy, người gửi phải nghẽn cho tới khi
không gian là sẳn dùng trong hàng đợi
- Khả năng chứa không giới hạn (unbounded capacity): Hàng đợi có khả năng có chiều
dài không giới hạn; do đó số lượng thông điệp bất kỳ có thể chờ trong nó. Người gửi không
bao giờ nghẽn.
2.5. Luồng (Thread)
Trong các hệ điều hành cũ, mỗi tiến trình có một không gian địa chỉ riêng và chỉ một
dòng chạy chương trình (tuần tự chạy các lệnh từ lệnh đầu tiên). Tuy nhiên trong nhiều trường
hợp công việc cần có nhiều dòng chạy chương trình chạy “song song” trong cùng một không
gian địa chỉ.
2.5.1 Khái niệm luồng
Mô hình tiến trình dựa trên hai điều: gom nhóm tài nguyên và chạy chương trình. Gom
nhóm tài nguyên là gom các tài nguyên có liên quan đến một công việc lại với nhau như
không gian địa chỉ để nạp chương trình xử lý công việc, các tập tin được mở liên quan đến
công việc … Chạy chương trình là chạy các mã để thực hiện công việc, đó là dòng chạy
chương trình. Dòng chạy chương trình có bộ đếm chương trình, thanh ghi, ngăn xếp, … riêng.
Trong một tiến trình có thể có nhiều dòng chạy chương trình đồng thời, mỗi dòng chạy
chương trình được gọi là luồng.
Các luồng của một tiến trình sẽ dùng chung môi trường của tiến trình, tức là dùng chung
không gian địa chỉ, các tập tin được mở,… của tiến trình.
Hình 2.8. Luồng.
Tiến trình đa luồng (multithreaded process) là tiến trình có nhiều luồng.
Hình (a): Có ba tiến trình, mỗi tiến trình chỉ có một dòng chạy chương trình và có
35
không gian địa chỉ riêng. Hình (b) có một tiến trình, trong tiến trình có ba luồng. Ba luồng này
có cùng không gian địa chỉ, tài nguyên của tiến trình.
Trong tiến trình đa luồng, các luồng chạy được luân phiên chạy (giống như sự luân
có thể có giải thuật lập lịch luồng riêng.
Tuy nhiên cài đặt luồng trong mức người dùng có những điểm hạn chế sau:
Cài đặt các hàm gọi hệ thống blocking (blocking system call) ? Khi một luồng thực hiện
gọi hệ thống (blocking) thì tất cả các luồng trong tiến trình đều bị ngưng. Điều này dẫn đến
phải có các hàm gọi hệ thống không blocking (nonblocking system call), và làm ảnh hưởng
rất nhiều đến các chương trình khác.
Khi một luồng chạy thì các luồng trong tiến trình đó không có cơ hội để chạy trừ khi
luồng đang chạy tự nguyện nhường CPU vì trong một tiến trình không có ngắt thời gian nên
bộ lập lịch luồng không thể chạy được.
b. Cài đặt luồng ở mức nhân
Trong tiến trình không có bảng luồng, kernel sẽ có bảng luồng lưu giữ thông tin của tất
cả các luồng trong hệ thống. Khi một luồng được tạo hay hủy bỏ thì gọi hàm hệ thống, do vậy
thời gian thực hiện chậm.
Khi một luồng thực hiện gọi hệ thống, trong trường hợp blocking thì luồng này sẽ bị
treo, và kernel sẽ cho luồng khác trong cùng tiến trình chạy nếu có, hoặc luồng của tiến trình
khác chạy. Do vậy các luồng không cần thiết phải có những hàm gọi thống không blocking.
Hình 2.10. Luồng ở mức nhân
c. Kết hợp
Kết hợp cách cài đặt luồng trong mức người dùng và mức nhân. Luồng có thể được cài
dặt theo một trong các mô hình sau:
Mô hình many-to-one
Nhiều luồng mức người dùng “chia sẻ” một luồng mức nhân để thực thi. Việc quản lý
luồng được thực hiện thông qua các hàm của một thư viện luồng được gọi ở mức người dùng.
Khi một luồng bị treo thì luồng mức nhân cũng bị treo, do đó mọi luồng khác của tiến
trình cũng sẽ bị treo.
37 Hình 2.11. Mô hình many-to-one.
39
CHƯƠNG 3. LẬP LỊCH CPU
3.1. Các khái niệm cơ bản
3.1.1. Chu kỳ CPU-I/O
Sự thành công của việc lập lịch CPU phụ thuộc vào thuộc tính được xem xét sau đây
của quá trình. Việc thực thi quá trình chứa một chu kỳ (cycle) thực thi CPU và chờ đợi vào/ra.
Các quá trình chuyển đổi giữa hai trạng thái này. Sự thực thi quá trình bắt đầu với một chu kỳ
CPU (CPU burst), theo sau bởi một chu kỳ vào/ra (I/O burst), sau đó một chu kỳ CPU khác,
sau đó lại tới một chu kỳ vào/ra khác khác, Sau cùng, chu kỳ CPU cuối cùng sẽ kết thúc với
một yêu cầu hệ thống để kết thúc việc thực thi, hơn là với một chu kỳ vào/ra khác, được mô tả
như hình 3.1. Một chương trình hướng vào/ra (I/O-bound) thường có nhiều chu kỳ CPU ngắn.
Một chương trình hướng xử lý (CPU-bound) có thể có một nhiều chu kỳ CPU dài. Sự phân bổ
này có thể giúp chúng ta chọn giải thuật lập lịch CPU hợp lý.
Hình 3.1. Sơ đồ thực hiện tiến trình.
3.1.2. Phân loại các hoạt động lập lịch
Lập lịch dài hạn (long-term scheduling): xác định tiến trình nào được chấp nhận vào hệ
40
thống. Quyết định độ-đa-lập-trình (degree of multiprogramming) Nếu càng nhiều tiến trình
được đưa vào hệ thống thì: khả năng các process bị block có xu hướng giảm; sử dụng CPU
hiệu quả hơn; mỗi process được phân chia khoảng thời gian sử dụng CPU thấp hơn.
Thường có xu hướng đưa vào một tập lẫn lộn các tiến trình CPU-bound và tiến trình
I/O-bound.
Hình 3.2. Các hoạt động lập lịch.
Lập lịch trung hạn (medium-term scheduling): xác định process nào được đưa vào
Bộ điều phối sẽ chuyển quyền điều khiển CPU về cho tiến trình được chọn bởi bộ lập
lịch ngắn hạn. Chức năng này thực hiện:
- Chuyển ngữ cảnh (sử dụng thông tin ngữ cảnh trong PCB).
- Chuyển về chế độ người dùng.
- Nhảy đến vị trí thích hợp trong chương trình ứng dụng để khởi động lại chương trình
(chính là program counter trong PCB).
Thời gian để bộ điều phối dừng một tiến trình này và bắt đầu chạy một tiến trình khác
được gọi là thời gian trễ cho việc điều phối (dispatch latency).
3.2. Tiêu chí lập lịch
3.2.1. Tiêu chuẩn lập lịch
Để so sánh và đánh giá các giải thuật lập lịch có thể dựa trên các tiêu chuẩn khác nhau.
Các tiêu chuẩn bao gồm:
Hiệu suất sử dụng CPU (CPU utilization): thời gian vô ích của CPU càng ít càng tốt.
Việc sử dụng CPU có thể từ 0 đến 100%.
Thông lượng (throughput): là số lượng tiến trình được hoàn thành trên một đơn vị thời
gian. gọi là thông lượng Đối với các tiến trình dài, tỉ lệ này có thể là 1 tiến trình trên 1 giờ; đối
với các giao dịch ngắn, thông lượng có thể là 10 tiến trình trên giây.
Thời gian hoàn thành (turnaround time): Thời gian để một tiến trình hoàn tất, kể từ lúc
vào hệ thống đến lúc kết thúc. Thời gian hoàn thành là tổng các thời gian chờ đưa tiến trình
vào bộ nhớ, chờ hàng đợi sẳn sàng, thực thi CPU và thực hiện vào/ra.
Thời gian chờ (waiting time): là tổng thời gian tiến trình chờ trong hàng đợi sẵn sàng.
Thời gian đáp ứng (response time): Thời gian từ lúc có yêu cầu của người dùng đến khi
có đáp ứng đầu tiên.
3.2.2. Mục tiêu điều phối:
Bộ điều phối tiến trình của hệ điều hành phải đạt được các mục tiêu sau đây trong công
tác điều phối:
42
Sự công bằng (Fairness): Các tiến trình đều công bằng với nhau trong việc chia sẻ thời
gian xử lý của CPU, không có tiến trình nào phải chờ đợi vô hạn để được cấp CPU.
2
, P
3
có thời gian xử lý
như sau:
Tiến trình Thời gian xử lý (ms)
P
1
24
P
2
3
P
3
3Giản đồ Gantt cho việc lập lịch là:
43
Thời gian đợi cho P
1
= 0, P
2
= 24, P
3
= 27
Thời gian đợi trung bình: (0 + 24 + 27)/3 = 17
Nếu các tiến trình đến theo thứ tự: P
Thuật toán SJF xác định thứ tự ưu tiên thực hiện tiến trình tựa vào tổng thời gian thực
hiện tiến trình. Tiến trình nào có tổng thời gian thực hiện ngắn sẽ được ưu tiên phục vụ trước.
Ví dụ: cho dãy tiến trình có thời điểm đến và thời gian xử lý như sau:
Tiến trình Thời điểm đến Thời gian xử lý(ms)
P
1
0.0 7
P
2
2.0 4
P
3
4.0 1
P
4
5.0 4
Giản đồ Gantt khi lập lịch theo SJF là:
Thời gian đợi trung bình = (0 + 6 + 3 + 7)/4 = 4
Ưu điểm của thuật toán là thời gian chờ đợi trung bình của các tiến trình ngắn hơn so
với FCFS. SJF nhanh chóng loại bỏ các tiến trình ngắn giảm số lượng các tiến trình trong
hàng đợi.
Nhược điểm chính của thuật toán là chế độ phân phối lại thời gian CPU cũng được áp
44
dụng trong trường hợp ngắt các tiến trình dài đang thực hiện để phục vụ các tiến trình ngắn
hơn mới mất hiện trong hàng đợi. Nếu tiến trình mới xuất hiện có tổng thời gian thực hiện
ngắn nhưng vẫn lớn hơn thời gian cần thiết để thực hiện nốt tiến trình đang thực hiện thì việc
ngắt tiến trình là không hợp lý.
Khó khăn thật sự với thuật toán SJF là làm thế nào để biết chiều dài của yêu cầu CPU
Nếu chọn α = ½ thì có nghĩa là trị đo được t
n
và trị dự đoán τ
n
được xem quan trọng
như nhau.
Hình 3.3. dự đoán thời gian sử dụng CPU.
3.3.3. Công việc còn lại ngắn nhất trước (Shortest Remaining Time First - SRTF)
Tương tự như SJF nhưng trong thuật toán này, độ ưu tiên thực hiện các tiến trình dựa
vào thời gian cần thiết để thực hiện nốt tiền trình (bằng tổng thời gian trừ đi thời gian đã thực
hiện). Như vậy, trong thuật toàn này cần phải thường xuyên cặp nhật thông tin về thời gian đã
thực hiện tiến trình. Đồng thời, chế độ phân bố lại thời CPU cũng phải được áp dụng nếu
không sẽ làm mất tính tưu việt của thuật toán. Đây có thể coi là phiên bản của SJF theo chế độ
không độc quyền.
Ví dụ: cho dãy tiến trình có thời điểm đến và thời gian phục vụ như sau:
Tiến trình Thời điểm đến Thời gian xử lý(ms)
P
1
0.0 7
P
2
2.0 4
P
3
4.0 1
45
P
2
17
P
3
68
P
4
24
Với lượng tử thời gian q = 20 ms
Giản đồ Gantt theo thuật toán RR là:
Ta có thể thấy thuật toán RR thường có thời gian quay vòng cao hơn SJF, nhưng lại có
Copyright: Tài liệu đại học ©