Bài giảng chương 2: Quản lý tiến trình
RR: thời gian đợi trung bình là 23 milli giây, hãy tính các thông số khác
Bạn đang xem trước 20 trang tài liệu Bài giảng chương 2: Quản lý tiến trình, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
HỆ ĐIỀU HÀNH
Phan Trung Kiên
Bộ môn Kỹ thuật máy tính và Mạng
CHƯƠNG 2. QUẢN LÝ TIẾN TRÌNH
Phan Trung Kiên 2
Nội dung
2.1. Tiến trình
2.2. Luồng
2.3. Định thời CPU
2.4. Đồng bộ hoá (Synchronization)
2.5. Deadlock (bế tắc)
Phan Trung Kiên 3
2.1. Tiến trình
2.1.1. Khái niệm cơ bản
2.1.2. Định thời tiến trình
2.1.3. Các tác vụ cơ bản: tạo/kết thúc tiến trình
2.1.4. Sự cộng tác giữa các tiến trình
2.1.5. Giao tiếp giữa các tiến trình
Phan Trung Kiên 4
2.1.1. Khái niệm cơ bản
Hệ thống máy tính thực thi nhiều chương trình khác nhau
Batch system: jobs
Time-shared systems: user programs, tasks
Job process
Tiến trình (process)
một chương trình đang thực thi
Một tiến trình bao gồm
Text section (program code), data section (chứa global variables)
Hoạt động hiện thời: program counter (PC), process status word
(PSW), stack pointer (SP), memory management registers
Phan Trung Kiên 5
Các bước nạp chương trình vào bộ nhớ
Phan Trung Kiên 6
Từ chương trình đến tiến trình
program
code
data
Executable binary file
(load module)
program
code
data
stack
Process image in
main memory
Dùng load module để biểu diễn chương trình thực thi được
Layout logic của process image
start address
Phan Trung Kiên 7
Khởi tạo tiến trình
Các bước hệ điều hành khởi tạo tiến trình
Cấp phát một định danh duy nhất (process number hay
process identifier, pid) cho tiến trình
Cấp phát không gian nhớ để nạp tiến trình
Khởi tạo khối dữ liệu Process Control Block (PCB)
cho tiến trình
PCB là nơi hệ điều hành lưu các thông tin về tiến trình
Thiết lập các mối liên hệ cần thiết (vd: sắp PCB vào
hàng đợi định thời,…)
Phan Trung Kiên 8
Các trạng thái của tiến trình
Các trạng thái của tiến trình (process states):
new: tiến trình vừa được tạo
ready: tiến trình đã có đủ tài nguyên, chỉ còn cần CPU
running: các lệnh của tiến trình đang được thực thi
waiting: hay là blocked, tiến trình đợi I/O hoàn tất, tiệp
nhận một tín hiệu.
terminated: tiến trình đã kết thúc.
Phan Trung Kiên 9
Các trạng thái của tiến trình (tt)
ready running
dispatch
interrupt
I/O or event
completion
I/O or
event wait
new
terminated
waiting
admit exit
Chuyển đổi giữa các trạng thái của tiến trình
Phan Trung Kiên 10
Process control block
Đã thấy là mỗi tiến trình trong hệ thống đều được cấp
phát một Process Control Block (PCB)
PCB là một trong các cấu trúc dữ liệu
quan trọng nhất của hệ điều hành
Ví dụ layout của một PCB:
(trường pointer dùng để liên kết
các PCBs thành một linked list)
Phan Trung Kiên 11
Yêu cầu đối với hệ điều hành về quản lý tiến trình
Hỗ trợ sự thực thi luân phiên giữa nhiều tiến trình
Hiệu suất sử dụng CPU
Thời gian đáp ứng
Phân phối tài nguyên hệ thống hợp lý
tránh deadlock, trì hoãn vô hạn định,…
Cung cấp cơ chế giao tiếp và đồng bộ hoạt động
các tiến trình
Cung cấp cơ chế hỗ trợ user tạo/kết thúc tiến trình
Phan Trung Kiên 12
running
ready
waiting
Quản lý các tiến trình: các hàng đợi
7
11 4 2 17
19 11
process number
các PCB
Có gì sai trong ví dụ?
Ví dụ
Phan Trung Kiên 13
2.1.2. Định thời tiến trình
Tại sao phải định thời?
Multiprogramming
Có nhiều tiến trình phải thực thi luân phiên nhau
Mục tiêu: cực đại hiệu suất sử dụng của CPU
Time-sharing
Cho phép users tương tác với tiến trình đang thực thi
Mục tiêu: tối thiểu thời gian đáp ứng
Một số khái niệm cơ bản
Các bộ định thời (scheduler)
Các hàng đợi định thời (scheduling queue)
Phan Trung Kiên 14
Các hàng đợi định thời
Job queue
Ready queue
Device queues
…
Mô hình của lập lịch tiến trình
Phan Trung Kiên 15
Bộ lập lịch
Bộ lập lịch dài hạn (Long-term scheduler - Lập lịc
công việc): lựa chọn các chương trình để đưa vào
hàng đợi ready .
Bộ lập lịch ngắn hạn (Short-term scheduler – lập
lịch CPU): chọn một tiến trình đã sẵn sàng để
chuyển giao cho CPU thực thi.
Phan Trung Kiên 16
Phan Trung Kiên 17
Phương án trung hạn
Đôi khi hệ điều hành (như time-sharing system) có thêm phương
án trung hạn (medium-term scheduling) để điều chỉnh mức độ
multiprogramming của hệ thống
Medium-term scheduler
– chuyển tiến trình từ bộ nhớ sang đĩa (swap out)
– chuyển tiến trình từ đĩa vào bộ nhớ (swap in)
Phan Trung Kiên 18
Chuyển ngữ cảnh (context switch)
Ngữ cảnh (context) của một tiến trình là trạng thái của tiến trình
Ngữ cảnh của tiến trình được biểu diễn trong PCB của nó
Chuyển ngữ cảnh (context switch) là công việc giao CPU cho tiến
trình khác. Khi đó cần:
– lưu ngữ cảnh của tiến trình cũ vào PCB của nó
– nạp ngữ cảnh từ PCB của tiến trình mới để tiến trình mới thực thi
Phan Trung Kiên 19
Chuyển ngữ cảnh (tt)
Phan Trung Kiên 20
2.1.3. Các tác vụ đối với tiến trình
Tạo tiến trình mới (process creation)
Một tiến trình có thể tạo tiến trình mới thông qua một
system call (vd: hàm fork trong Unix)
Ví dụ: (Unix) Khi user đăng nhập hệ thống, một command
interpreter (shell) sẽ được tạo ra cho user
tiến trình được tạo là tiến trình con của tiến trình tạo
(tiến trình cha). Quan hệ cha-con định nghĩa một cây
tiến trình.
Cây tiến trình trong Linux/Unix
root
swapper pagedaemon init
bash bash bash
mkdir grep ls gcc
Phan Trung Kiên 22
Các tác vụ đối với tiến trình
Tạo tiến trình mới
Chia sẻ tài nguyên của tiến trình cha
tiến trình cha và con chia sẻ mọi tài nguyên
tiến trình con chia sẻ một phần tài nguyên của cha
Trình tự thực thi
tiến trình cha và con thực thi đồng thời (concurrently)
tiến trình cha đợi đến khi các tiến trình con kết thúc.
Phan Trung Kiên 23
Về quan hệ cha/con
Không gian địa chỉ (address space)
Không gian địa chỉ của tiến trình con được nhân bản từ cha
Không gian địa chỉ của tiến trình con được khởi tạo từ template.
Ví dụ trong UNIX/Linux
System call fork() tạo một tiến trình mới
System call exec() dùng sau fork() để nạp một chương trình mới
vào không gian nhớ của tiến trình mới
đồng bộ
Phan Trung Kiên 24
Ví dụ tạo process với fork()
#include
#include
int main (int argc, char *argv[]){
int pid;
/* create a new process */
pid = fork();
if (pid > 0){
printf(“This is parent process”);
wait(NULL);
exit(0);
}
else if (pid == 0)
{
printf(“This is child process”);
execlp(“/bin/ls”, “ls”, NULL);
exit(0);
}
else {
printf(“Fork error\n”);
exit(-1);
}
}
Phan Trung Kiên 25
Các tác vụ đối với tiến trình (tt)
Kết thúc tiến trình
Tiến trình tự kết thúc
Tiến trình kết thúc khi thực thi lệnh cuối và gọi system routine exit
tiến trình kết thúc do tiến trình khác (có đủ quyền, vd: tiến trình
cha của nó)
Gọi system routine abort với tham số là pid (process identifier) của tiến
trình cần được kết thúc
Hệ điều hành thu hồi tất cả các tài nguyên của tiến trình kết thúc
(vùng nhớ, I/O buffer,…)
Phan Trung Kiên 26
2.1.4. Cộng tác giữa các tiến trình
Trong tiến trình thực thi, các tiến trình có thể cộng tác
(cooperate) để hoàn thành công việc
Các tiến trình cộng tác để
Chia sẻ dữ liệu (information sharing)
Tăng tốc tính toán (computational speedup)
Nếu hệ thống có nhiều CPU, chia công việc tính toán thành nhiều công
việc tính toán nhỏ chạy song song
Thực hiện một công việc chung
Xây dựng một phần mềm phức tạp bằng cách chia thành các
module/process hợp tác nhau
Sự cộng tác giữa các tiến trình yêu cầu hệ điều hành hỗ
trợ cơ chế giao tiếp và cơ chế đồng bộ hoạt động của các
tiến trình
Phan Trung Kiên 27
Bài toán producer-consumer
Ví dụ cộng tác giữa các tiến trình: bài toán
producer-consumer
Producer tạo ra các dữ liệu và consumer tiêu thụ, sử
dụng các dữ liệu đó. Sự trao đổi thông tin thực hiện
qua buffer
unbounded buffer: kích thước buffer vô hạn (không thực tế).
bounded buffer: kích thước buffer có hạn.
Producer và consumer phải hoạt động đồng bộ vì
Consumer không được tiêu thụ khi producer chưa sản xuất
Producer không được tạo thêm sản phẩm khi buffer đầy.
Phan Trung Kiên 28
2.1.5. Giao tiếp giữa các tiến trình
Interprocess communication (IPC): là cơ chế cung
cấp bởi hệ điều hành nhằm giúp các tiến trình
giao tiếp với nhau
và đồng bộ hoạt động
mà không cần chia sẻ không gian địa chỉ
Mô hình giao tiếp
Phan Trung Kiên 29
(a) Message passing. (b) Shared memory.
Phan Trung Kiên 30
Message passing system
Làm thế nào để các tiến trình giao tiếp nhau? Các vấn đề:
Naming
Giao tiếp trực tiếp
send(P, msg): gửi thông điệp đến tiến trình P
receive(Q, msg): nhận thông điệp đến từ tiến trình Q
Giao tiếp gián tiếp: thông qua mailbox hay port
send(A, msg): gửi thông điệp đến mailbox A
receive(B, msg): nhận thông điệp từ mailbox B
Synchronization: blocking send, nonblocking send, blocking receive, nonblocking
receive
Buffering: dùng queue để tạm chứa các message
Zero capacity (no buffering)
Bounded capacity: độ dài của queue là giới hạn
Unbounded capacity: độ dài của queue là không giới hạn
44
2.2 Luồng (Thread)
2.2.1. Tổng quan
2.2.2. Các mô hình đa luồng
2.2.3. Pthreads (POSIX thread)
2.2.4. Multithreading trong Solaris 2
2.2.5. Multithreading với Java
Phan Trung Kiên
45
2.2.1 Tổng quan
Khái niệm tiến trình truyền thống: tiến trình gồm
Không gian địa chỉ (text section, data section)
Một luồng thực thi duy nhất (single thread of
execution)
program counter
các register
stack
Các tài nguyên khác (các open file, các tiến trình
con,…)
Phan Trung Kiên
46
Mở rộng khái niệm tiến trình
Mở rộng khái niệm tiến trình truyền thống bằng cách
hiện thực nhiều luồng thực thi trong cùng một môi
trường của tiến trình.
Tiến trình gồm
Không gian địa chỉ (text section, data section)
Một hay nhiều luồng thực thi (thread of execution), mỗi luồng
thực thi (thread) có riêng
program counter
các register
stack
Các tài nguyên khác (các open file, các tiến trình con,…)
Phan Trung Kiên
Tiến trình đơn luồng và đa luồng
Phan Trung Kiên 47
48
Tiến trình đa luồng
Các thread trong cùng một process chia sẻ code
section, data section và tài nguyên khác (các file
đang mở,...) của process.
Tiến trình đa luồng (multithreaded process) là
tiến trình có nhiều luồng.
Phan Trung Kiên
49
Sử dụng thread
A word processor with three threads
mouse
Phan Trung Kiên
50
Process & thread information
Per process items
Address space
Open files
Child processes
Signals & handlers
Accounting info
Global variables
Per thread items
Program counter
Registers
Stack & stack pointer
State
Per thread items
Program counter
Registers
Stack & stack pointer
State
Per thread items
Program counter
Registers
Stack & stack pointer
State
(Tiến trình gồm ba thread)
Phan Trung Kiên
51
Multiplexing CPU giữa các thread
CPU
time
ba tiến trình
single-threaded
Phan Trung Kiên
52
Multiplexing CPU giữa các thread (tt)
CPU
hai tiến trình
multithreaded
time
Phan Trung Kiên
53
Ví dụ Pthread program (Linux)
#include
void* thread1(){
int i;
for (i = 0; i < 10; i++){
printf(“Thread 1\n”); sleep(1);
}
}
void* thread2(){
int i;
for (i = 0; i < 10; i++){
printf(“Thread 2\n”); sleep(1);
}
int main(){
pthread_t th1, th2;
pthread_create(&th1, NULL, thread1, NULL);
pthread_create(&th2, NULL, thread2, NULL);
sleep(20);
return 0;
}
Static Data
Heap
thread1
stack
thread2
stack
Text
PC1
PC2
SP1
SP2
Sơ đồ bộ nhớ
Phan Trung Kiên
54
Ưu điểm của thread
Tính đáp ứng (responsiveness) cao cho các ứng dụng
tương tác multithreaded
Chia sẻ tài nguyên (resource sharing): vd memory
Tiết kiệm chi phí hệ thống (economy)
Chi phí tạo/quản lý thread nhỏ hơn so với tiến trình
Chi phí chuyển ngữ cảnh giữa các thread nhỏ hơn so với tiến
trình
Tận dụng kiến trúc đa xử lý (multiprocessor)
Mỗi thread chạy trên một processor riêng, do đó tăng mức độ
song song của chương trình.
Phan Trung Kiên
55
Thư viện luồng
Một thư viện thread (thread library, run-time
system) được hiện thực trong không gian ứng
dụng để hổ trợ các tác vụ lên thread
Thư viện thread cung cấp các hàm khởi tạo, định thời
và quản lý thread như
thread_create
thread_exit
thread_wait
thread_yield
Thư viện thread dùng Thread Control Block (TCB) để
lưu trạng thái của user thread (program counter, các
register, stack)
Phan Trung Kiên
56
User thread
thread library thread library thread library
user
thread
kernel
Ví dụ: hệ điều hành truyền thống chỉ cung cấp
một “kernel thread” duy nhất (biểu diễn bởi một
PCB) cho mỗi process.
Blocking problem: Khi một thread trở nên blocked thì
kernel thread cũng trở nên blocked, do đó mọi thread
khác của process cũng sẽ trở nên blocked.
PCB PCB PCB
Phan Trung Kiên
57
Kernel thread
Cơ chế multithreading được hệ điều hành trực tiếp hỗ trợ
Kernel quản lý cả process và các thread
Việc định thời CPU được kernel thực hiện trên thread
Phan Trung Kiên
58
Kernel thread (tt)
Cơ chế multithreading được hỗ trợ bởi kernel
Khởi tạo và quản lý các thread chậm hơn
Tận dụng được lợi thế của kiến trúc multiprocessor
Thread bị blocked không kéo theo các thread khác bị blocked.
Một số hệ thống multithreading (multitasking)
Windows 9x/NT/200x
Solaris
Linux
Phan Trung Kiên
59
Các mô hình đa luồng
Thread có thể hiện thực theo một trong các mô
hình sau
Mô hình many-to-one
Mô hình one-to-one
Mô hình many-to-many
Phan Trung Kiên
60
Mô hình many-to-one
Nhiều user-level thread “chia
sẻ” một kernel thread để thực
thi
Việc quản lý thread được thực
hiện thông qua các hàm của một
thread library được gọi ở user
level.
Blocking problem: Khi một
thread trở nên blocked thì
kernel thread cũng trở nên
blocked, do đó mọi thread khác
của process cũng sẽ trở nên
blocked.
Có thể được hiện thực đối với
hầu hết các hệ điều hành.
kernel thread
Phan Trung Kiên
61
Mô hình one-to-one
Mỗi user-level thread
thực thi thông qua một
kernel thread riêng của
nó
Mỗi khi một user thread
được tạo ra thì cũng cần
tạo một kernel thread
tương ứng
Hệ điều hành phải có cơ
chế cung cấp được nhiều
kernel thread cho một
tiến trình
Ví dụ: Windows
NT/2000
kernel thread
Phan Trung Kiên
62
Mô hình many-to-many
Nhiều user-level thread
được phân chia thực thi
(multiplexed) trên một số
kernel thread.
Tránh được một số khuyết
điểm của hai mô hình
many-to-one và one-to-one
Ví dụ
Solaris 2
Windows NT/2000 với
package ThreadFiber kernel thread
Phan Trung Kiên
63
2.2.3. Pthreads
Chuẩn POSIX (IEEE 1003.1c) cung cấp các API hỗ trợ
tạo thread và đồng bộ thread (synchronization)
Phổ biến trong các hệ thống UNIX/Linux
Là một thư viện hỗ trợ user-level thread
Tham khảo thêm ví dụ về lập trình thư viện Pthread với
ngôn ngữ C trong hệ thống Unix-like, trang 140,
“Operating System Concepts”, Silberschatz et al, 6th Ed,
2003.
Biên dịch và thực thi chương trình multithreaded C trong
Linux
$ gcc source_file.c -lpthread –o output_file
$ ./output_file
Phan Trung Kiên
64
2.2.4. Thread trong Solaris
User-level threads
Pthread và UI-thread
Lightweight process (LWP)
Mỗi process chứa ít nhất một LWP
Thư viện thread có nhiệm vụ phân định user thread vào các
LWP
User-level thread được gắn với LWP thì mới được thực thi.
Thư viện thread chịu trách nhiệm điều chỉnh số lượng LWP
Kernel-level thread
Mỗi LWP tương ứng với một kernel-level thread
Ngoài ra, hệ thống còn có một số kernel threads dành cho một
số công việc ở kernel (các thread này không có LWP tương
ứng)
Đối tượng được định thời trong hệ thống là các kernel thread Phan Trung Kiên
65
2.2.4. Thread trong Solaris (tt)
many-to-many
Phan Trung Kiên
66
2.2.4. Thread trong Solaris (tt)
Tiến trình trong Solaris
LWP1 LWP2 LWP3
…
Phan Trung Kiên
67
2.2.5. Thread trong Java
Hỗ trợ tạo và quản lý thread ở mức ngôn ngữ lập trình
(language-level)
Tất cả chương trình Java chứa ít nhất là một thread
Các thread của Java được quản lý bởi JVM
Hai phương pháp tạo Java Threads
1. extend Thread class và override method run()
2. Hiện thực (implementing) Runnable interface
Phan Trung Kiên
Trạng thái của Java thread
Phan Trung Kiên 68
2.3. ĐỊNH THỜI CPU
(CPU Scheduling)
Phan Trung Kiên
Nội dung
2.3.1. Các khái niệm cơ bản
2.3.2. Tiêu chí lập lịch
2.3.3. Các thuật toán lập lịch
2.3.4. Lập lịch trên hệ thống nhiều CPU
70
Phan Trung Kiên
2.3.1. Các khái niệm cơ bản
Chu kỳ CPU-I/O
CPU-bound process có thời
gian sử dụng CPU nhiều
hơn thời gian sử dụng I/O
I/O-bound process dùng
phần lớn thời gian để đợi
I/O
71
Phan Trung Kiên
Các khái niệm cơ bản
Trong các hệ thống multitasking
Tại một thời điểm trong bộ nhớ có nhiều process
Tại mỗi thời điểm chỉ có một process được thực thi
Do đó, cần phải giải quyết vấn đề phân chia, lựa chọn
process thực thi sao cho được hiệu quả nhất. Cần có
chiến lược lập lịch CPU
72
Phan Trung Kiên
Phân loại các hoạt động lập lịch
ready
running
suspended
ready
suspended
blocked
new
terminated blocked
Long-term
scheduling
Long-term
scheduling
Medium-term
scheduling
Medium-term
scheduling
Short-term
scheduling
Đường gạch rời:
chuyển đổi không nhất thiết có
73
Phan Trung Kiên
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 process nào được chấp nhận vào hệ thống
Lập lịch trung hạn (medium-term scheduling):
xác định process nào được đưa vào (swap in),
đưa ra khỏi (swap out) bộ nhớ chính
Lập lịch ngắn hạn (short-term scheduling): xác
định process nào được thực thi tiếp theo
74
Phan Trung Kiên
Lập lịch dài hạn
Xác định chương trình nào sẽ được đưa vào hệ
thống để thực thi
Quyết định độ-đa-lập-trình (degree of
multiprogramming)
Nếu càng nhiều process được đưa vào hệ thống
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
CPU-bound process và I/O-bound process
75
Phan Trung Kiên
Lập lịch trung hạn
Quyết định việc đưa process vào bộ nhớ chính,
hay ra khỏi bộ nhớ chính
Phụ thuộc vào yêu cầu quản lý việc đa-lập-trình
(multiprogramming)
Cho phép bộ lập lịch dài hạn chấp nhận nhiều process
hơn số lượng process mà có tổng kích thước được chứa
vừa trong bộ nhớ chính
Nhưng nếu có quá nhiều process thì sẽ làm tăng việc
truy xuất đĩa, do đó cần phải lựa chọn độ-đa-lập-trình
cho phù hợp
Được thực hiện bởi phần mềm quản lý bộ nhớ
76
Phan Trung Kiên
Lập lịch ngắn hạn
Xác định process nào được thực thi tiếp theo, còn
gọi là lập lịch CPU
Được kích hoạt khi có một sự kiện có thể dẫn đến
khả năng chọn một process để thực thi
Ngắt thời gian (clock interrupt)
Ngắt ngoại vi (I/O interrupt)
Lời gọi hệ thống (operating system call)
Signal
77
Phan Trung Kiên
Nội dung cần quan tâm
Chương này sẽ tập trung vào lập lịch ngắn hạn.
Lập lịch trên hệ thống có một processor
(uniprocessor scheduling): quyết định việc sử
dụng (một) CPU cho một tập các process trong hệ
thống
78
Phan Trung Kiên
Hai thành phần của chiến lược lập lịch
Hàm lựa chọn (selection function)
Xác định process nào trong ready queue sẽ được thực
thi tiếp theo. Thường theo các tiêu chí như
w = tổng thời gian đợi trong hệ thống
e = thời gian đã được phục vụ
s = tổng thời gian thực thi của process (bao gồm cả trị e)
79
Phan Trung Kiên
Hai thành phần của chiến lược lập lịch
Chế độ quyết định (decision mode)
Chọn thời điểm hàm lựa chọn lập lịch thực thi
Nonpreemptive (độc quyền)
Một process sẽ ở trạng thái running cho đến khi nó bị block
hoặc nó kết thúc
Preemptive (không độc quyền)
Process đang thực thi có thể bị ngắt và chuyển về trạng thái
ready
Tránh trường hợp một process độc chiếm CPU
80
Phan Trung Kiên
Nonpreemptive và preemptive
Hàm lập lịch có thể được thực thi khi có quá trình
(1) chuyển từ trạng thái running sang waiting
(2) chuyển từ trạng thái running sang ready
(3) chuyển từ trạng thái waiting, new sang ready
(4) kết thúc thực thi
Định thời nonpreemptive: chỉ thực thi hàm lập
lịch trong trường hợp 1 và 4
Định thời preemptive: ngoài trường hợp 1 và 4
còn thực thi thêm hàm lập lịch trong trường hợp 2
hoặc 3 (hoặc cả hai)
81
Phan Trung Kiên
Dispatcher
Dispatcher sẽ chuyển quyền điều khiển CPU về cho process
được chọn bởi bộ lập lịch ngắn hạn
Bao gồm:
Chuyển ngữ cảnh (sử dụng thông tin ngữ cảnh trong PCB)
Chuyển về user mode
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)
Công việc này gây ra phí tổn
Dispatch latency: thời gian mà dispatcher dừng một process và khởi
động một process khác
82
Phan Trung Kiên
Dispatch latency
Conflict phase: xem p. 171
83
Phan Trung Kiên
2.3.2. Tiêu chí lập lịch
Độ lợi CPU (CPU utilization)
Khoảng thời gian CPU bận, từ 0% đến 100%
Cần giữ cho CPU càng bận càng tốt
Thời gian chờ (waiting time)
Thời gian chờ trong hàng đợi ready
Các process nên được chia sẻ việc sử dụng CPU một
cách công bằng (fair share)
84
Phan Trung Kiên
2.3.2. Tiêu chí lập lịch
Thông năng (throughput)
Số lượng process hoàn tất trong một đơn vị thời gian
Thời gian đáp ứng (response time)
Thời gian từ lúc có yêu cầu của người dùng (user
request) đến khi có đáp ứng đầu tiên (lưu ý: đáp ứng
đầu tiên, chứ không phải output)
Thường là vấn đề với các I/O-bound process
85
Phan Trung Kiên
2.3.2. Tiêu chí lập lịch
Thời gian quay vòng (turnaround time)
Thời gian để một process hoàn tất, kể từ lúc vào hệ
thống (submission) đến lúc kết thúc (termination)
Là một trị đặc trưng cần quan tâm với các process
thuộc dạng CPU-bound
Thời gian quay vòng trung bình (average
turnaround time)
86
Phan Trung Kiên
2.3.2. Tiêu chí lập lịch
Độ lợi CPU – giữ CPU càng bận càng tốt
Tối đa hóa
Thông năng – số lượng process kết thúc việc thực thi trong một
đơn vị thời gian
Tối đa hóa
Turnaround time – thời gian kể từ lúc bắt đầu đưa vào
(submission) đến lúc kết thúc
Tối thiểu hóa
Thời gian chờ – thời gian một process chờ trong hàng đợi ready
Tối thiểu hóa
Thời gian đáp ứng – thời gian từ khi đưa yêu cầu đến khi có đáp
ứng đầu tiên
Tối thiểu hóa
87
Phan Trung Kiên
Có thể làm được?
Tất cả các tiêu chí không thể được tối ưu đồng
thời vì có một số tiêu chí liên quan nhau
88
Phan Trung Kiên
Tiêu chí lập lịch từ các góc nhìn
Hướng đến người sử dụng (user-oriented)
Thời gian quay vòng (turnaround time)
Thời gian từ lúc nạp process đến lúc process kết thúc
Cần quan tâm với các hệ thống xử lý bó (batch system)
Thời gian đáp ứng (response time)
Cần quan tâm với các hệ thống giao tiếp (interactive system)
89
Phan Trung Kiên
Tiêu chí lập lịch từ các góc nhìn
Hướng đến hệ thống (system-oriented)
Độ lợi CPU (CPU utilization)
Công bằng (fairness)
Thông năng (throughput): số process hoàn tất trong
một đơn vị thời gian
90
Phan Trung Kiên
2.3.3 Các thuật toán lập lịch
First Come First Served (FCFS)
Hàm lựa chọn: chọn process đợi trong hàng đợi ready
lâu nhất
Chế độ quyết định: nonpreemptive
Một process sẽ được thực thi cho đến khi nó bị block hoặc
kết thúc
FCFS thường được quản lý bằng một FIFO queue
91
Phan Trung Kiên
First Come First Served (FCFS)
Process Burst time (ms)
P1 24
P2 3
P3 3
Giả sử các process đến theo thứ tự P1 , P2 , P3
Giản đồ Gantt cho việc lập lịch là:
Thời gian đợi cho P1 = 0, P2 = 24, P3 = 27
Thời gian đợi trung bình: (0 + 24 + 27)/3 = 17
P1 P2 P3
24 27 30 0
92
Phan Trung Kiên
First Come First Served (FCFS)
Thời gian phục vụ trung bình =
Thông năng =
Thời gian quay vòng =
Kiểm tra lại: Thời gian đợi = (thời gian quay vòng
thời gian phục vụ dispatch latency)
P1 P2 P3
24 27 30 0
93
Phan Trung Kiên
First Come First Served (FCFS)
Giả sử các process đến theo thứ tự:
P2 , P3 , P1
Giản đồ Gantt cho việc lập lịch là:
Thời gian đợi cho P1 = 6, P2 = 0, P3 = 3
Thời gian đợi trung bình là: (6 + 0 + 3)/3 = 3
Tốt hơn rất nhiều so với trường hợp trước
P1 P3 P2
6 3 30 0
94
Phan Trung Kiên
First Come First Served (FCFS)
FCFS không công bằng với các process có CPU burst
ngắn. Các process này phải chờ trong thời gian dài (so
với thời gian mà nó cần phục vụ) thì mới được sử dụng
CPU. Điều này đồng nghĩa với việc FCFS “ưu tiên” các
process thuộc dạng CPU bound.
Câu hỏi: Liệu có xảy ra trường hợp trì hoãn vô hạn định
(starvation hay indefinite blocking) với giải thuật FCFS?
FCFS thường được sử dụng trong các hệ thống bó (batch
system)
95
Phan Trung Kiên
Ví dụ thực tế
Việc phục vụ khách trong nhà hàng
Thực khách sẽ đến và gọi món ăn cho mình
Mỗi món ăn cần thời gian chuẩn bị khác nhau
Mục tiêu:
Giảm thời gian đợi trung bình của các thực khách
Cách làm nào sẽ phù hợp?
Thông thường các nhà hàng sẽ phục vụ theo kiểu
FCFS (!)
96
Phan Trung Kiên
Shortest Job First (SJF)
Process Thời điểm đến Burst time (ms)
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
Giản đồ Gantt khi lập lịch theo SJF
Thời gian đợi trung bình = (0 + 6 + 3 + 7)/4 = 4
P1 P3 P2
7 3 16 0
P4
8 12
97
Phan Trung Kiên
Shortest Job First (SJF)
Thời gian phục vụ trung bình =
Thông năng =
Thời gian quay vòng =
Kiểm tra lại: Thời gian đợi = (thời gian quay vòng
thời gian phục vụ dispatch latency)
P1 P3 P2
7 3 16 0
P4
8 12
98
Phan Trung Kiên
Shortest Job First (SJF)
Tương ứng với mỗi process cần có độ dài của
CPU burst tiếp theo
Hàm lựa chọn: chọn process có độ dài CPU burst
nhỏ nhất
Chứng minh được: SJF tối ưu trong việc giảm
thời gian đợi trung bình
Nhược điểm: Cần phải ước lượng thời gian cần
CPU tiếp theo của process
Giải pháp cho vấn đề này?
99
Phan Trung Kiên
Dự đoán thời gian sử dụng CPU
(Thời gian sử dụng CPU chính là độ dài của CPU burst)
Trung bình tất cả các CPU burst đo được trong quá khứ
Nhưng thông thường những CPU burst càng mới càng phản ánh
đúng hành vi của process trong tương lai
Một kỹ thuật thường dùng là sử dụng trung bình hàm mũ
(exponential averaging)
τn+1 = a tn + (1 - a) τn , 0 a 1
τn+1 = a tn + (1- a) a tn-1 +…+ (1- a)
jaτn-j +…+ (1- a)
n+1aτ0
Nếu chọn a = ½ thì có nghĩa là trị đo được tn và trị dự đoán τn
được xem quan trọng như nhau.
100
Phan Trung Kiên
Dự đoán thời gian sử dụng CPU
Độ dài CPU burst
đo được
Độ dài CPU burst dự đoán,
với a = ½ và 0 = 10
101
Phan Trung Kiên
Shortest Job First (SJF)
SJF sử dụng ưu tiên ngầm định: công việc ngắn nhất được ưu
tiên trước
Những công việc thuộc loại I/O bound thường có CPU burst
ngắn
Process có thời gian thực thi dài có thể bị trì hoãn vô hạn định
nếu các process có thời gian thực thi ngắn liên tục vào
Không thích hợp cho môi trường time-sharing khi không
dùng preemption
Dù các CPU bound process có “độ ưu tiên” thấp
Nhưng một process không thực hiện I/O có thể độc chiếm hệ
thống nếu nó là process đầu tiên vào hệ thống
102
Phan Trung Kiên
Shortest Job First (SJF)
Chế độ quyết định: nonpreemptive
Phiên bản preemptive của SJF:
Nếu một process mới đến mà có độ dài CPU burst nhỏ
hơn thời gian cần CPU còn lại của process đang thực
thi, thì thực hiện preempt process đang thực thi
Cách làm này còn được gọi là
Shortest-Remaining-Time-First (SRTF)
103
Phan Trung Kiên
Shortest Remaining Time First (SRTF)
Process Thời điểm đến Burst time (ms)
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
Giản đồ Gantt khi lập lịch theo SRTF
Thời gian đợi trung bình = (9 + 1 + 0 + 2)/4 = 3
Tốt hơn giải thuật nonpreemptive SJF
P1 P3 P2
4 2 11 0
P4
5 7
P2 P1
16
104
Phan Trung Kiên
Shortest Remaining Time First (SRTF)
Thời gian phục vụ trung bình =
Thông năng =
Thời gian quay vòng =
Kiểm tra lại: Thời gian đợi = (thời gian quay vòng
thời gian phục vụ dispatch latency)
P1 P3 P2
4 2 11 0
P4
5 7
P2 P1
16
105
Phan Trung Kiên
Shortest Remaining Time First (SRTF)
Tránh trường hợp các process có thời gian thực
thi dài độc chiếm CPU
Cần phải quản lý thời gian thực thi còn lại của các
process
Có thời gian quay vòng tốt hơn SJF
Process có thời gian thực thi ngắn có độ ưu tiên
cao
106
Phan Trung Kiên
Lập lịch ưu tiên (Priority Scheduling)
Mỗi process sẽ được gán một độ ưu tiên
CPU sẽ được cấp cho process có độ ưu tiên cao
nhất
Lập lịch sử dụng độ ưu tiên có thể:
Preemptive hoặc
Nonpreemptive
107
Phan Trung Kiên
Gán độ ưu tiên
SJF là một giải thuật lập lịch sử dụng độ ưu tiên
với độ ưu tiên là thời-gian-sử-dụng-CPU-dự-đoán
Gán độ ưu tiên còn dựa vào:
Yêu cầu về bộ nhớ
Số lượng file được mở
Tỉ lệ thời gian dùng cho I/O trên thời gian sử dụng
CPU
Các yêu cầu bên ngoài ví dụ như: số tiền người
dùng trả khi thực thi công việc
108
Phan Trung Kiên
Lập lịch ưu tiên
Vấn đề: trì hoãn vô hạn định – process có độ ưu
tiên thấp có thể không bao giờ được thực thi
Giải pháp: aging – độ ưu tiên của process sẽ tăng
theo thời gian
109
Phan Trung Kiên
Round Robin (RR)*
Hàm lựa chọn: giống FCFS
2 1
3
4
5 6
7
8
110
Phan Trung Kiên
Round Robin (RR)*
Chế độ quyết định: preemptive
Khoảng thời gian tối đa cho phép (thường 10 - 100 ms)
được đảm bảo bằng việc sử dụng timer interrupt
Process đang chạy hết thời gian sẽ được chuyển về
cuối của hàng đợi ready
111
Phan Trung Kiên
Round Robin (RR)*
Process Burst time (ms)
P1 53
P2 17
P3 68
P4 24
Quantum time = 20 ms
Giản đồ Gantt:
Thường có thời gian quay vòng cao hơn SJF, nhưng lại có
thời gian đáp ứng tốt hơn
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
112
Phan Trung Kiên
Round Robin (RR)*
Thời gian phục vụ trung bình =
Thông năng =
Thời gian quay vòng =
Kiểm tra lại: Thời gian đợi = (thời gian quay vòng
thời gian phục vụ dispatch latency)
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
113
Phan Trung Kiên
Quantum time cho Round Robin
114
Phan Trung Kiên
Quantum time và chuyển ngữ
cảnh Quantum time càng nhỏ thì càng có nhiều lần
chuyển ngữ cảnh (context switch)
Số lần ngưng/tiếp
tục quá trình
115
Phan Trung Kiên
Thời gian quay vòng và quantum
time Thời gian quay vòng trung bình (average
turnaround time) không chắc sẽ được cải thiện khi
quantum lớn
116
Phan Trung Kiên
Quantum time cho Round Robin
Khi thực hiện process switch thì OS sẽ sử dụng CPU chứ không
phải process của người dùng (OS overhead)
Dừng thực thi, lưu tất cả thông tin, nạp thông tin của process sắp thực thi
Performance tùy thuộc vào kích thước của quantum time (còn gọi
là time slice), và hàm phụ thuộc này không đơn giản
Time slice ngắn thì đáp ứng nhanh
Vấn đề: có nhiều chuyển ngữ cảnh. Phí tổn sẽ cao.
Time slice dài hơn thì throughput tốt hơn (do giảm phí tổn OS
overhead) nhưng thời gian đáp ứng lớn
Nếu time slice quá lớn, RR trở thành FCFS.
117
Phan Trung Kiên
Quantum time cho Round Robin
Quantum time và thời gian cho process switch:
Nếu quantum time = 20 ms và thời gian cho process switch = 5
ms, như vậy phí tổn OS overhead chiếm 5/25 = 20%
Nếu quantum = 500 ms, thì phí tổn chỉ còn 1%
Nhưng nếu có nhiều người sử dụng trên hệ thống và thuộc loại interactive
thì sẽ thấy đáp ứng rất chậm
Tùy thuộc vào tập công việc mà lựa chọn quantum time
Time slice nên lớn trong tương quan so sánh với thời gian cho
process switch
Ví dụ với 4.3 BSD UNIX, time slice là 1 giây
118
Phan Trung Kiên
Round Robin
Nếu có n process trong hàng đợi ready, và
quantum time là q, như vậy mỗi process sẽ lấy 1/n
thời gian CPU theo từng khối có kích thước lớn
nhất là q
Sẽ không có process nào chờ lâu hơn (n - 1)q đơn vị
thời gian
RR sử dụng một giả thiết ngầm là tất cả các
process đều có tầm quan trọng ngang nhau
Không thể sử dụng RR nếu muốn các process khác
nhau có độ ưu tiên khác nhau
119
Phan Trung Kiên
Round Robin: nhược điểm
Các process dạng CPU-bound vẫn còn được “ưu
tiên”
Ví dụ:
Một I/O-bound process sử dụng CPU trong thời gian ngắn
hơn quantum time và bị blocked để đợi I/O. Và
Một CPU-bound process chạy hết time slice và lại quay trở
về hàng đợi ready queue (ở phía trước các process đã bị
blocked)
120
Phan Trung Kiên
Multilevel Queue Scheduling*
Trường hợp các quá trình có thể được phân thành
nhóm
(ví dụ: interactive và batch)
Hàng đợi ready sẽ được chia thành nhiều hàng đợi
riêng rẽ. Ví dụ:
foreground (cho công việc cần giao tiếp - interactive)
background (cho công việc dạng bó - batch)
Mỗi hàng đợi sẽ có giải thuật lập lịch riêng. Ví
dụ:
foreground: dùng RR
background: dùng FCFS
121
Phan Trung Kiên
Multilevel Queue Scheduling*
Lập lịch cần phải thực hiện giữa các hàng đợi với
nhau
Theo cách cố định (fixed priority scheduling) – ví dụ:
phục vụ tất cả các process của foreground rồi mới đến
background
Có khả năng xảy ra trì hoãn vô hạn định (starvation)
Chia thời gian (time slice) – mỗi hàng đợi sẽ được lấy
một khoảng sử dụng CPU nhất định để lập lịch cho các
process của mình. Ví dụ:
80% cho foreground (dùng RR)
20% cho background (dùng FCFS)
122
Phan Trung Kiên
Multilevel Queue Scheduling*
Ví dụ phân nhóm các quá trình
System Processes
Interactive Processes
Batch Processes
Student Processes
Độ ưu tiên thấp nhất
Độ ưu tiên cao nhất
123
Phan Trung Kiên
Multilevel Feedback Queue*
Process có thể di chuyển giữa các queue tùy theo
đặc tính của nó.
Ví dụ:
Nếu một process sử dụng CPU quá lâu, nó sẽ bị di
chuyển sang một hàng đợi có độ ưu tiên thấp hơn
Nếu một process chờ qua lâu trong một hàng đợi có độ
ưu tiên thấp, nó sẽ được di chuyển lên hàng đợi có độ
ưu tiên cao hơn (aging, giúp tránh starvation)
124
Phan Trung Kiên
Multilevel Feedback Queue*
Ví dụ: Có 3 hàng đợi
Q0 , dùng RR với quantum 8 ms
Q1 , dùng RR với quantum 16 ms
Q2 , dùng FCFS
Giải thuật
Công việc mới sẽ vào hàng đợi Q0.
Khi đến lượt mình, công việc sẽ
được một khoảng thời gian là 8 milli
giây. Nếu không kết thúc được trong
8 milli giây, công việc sẽ được đưa
xuống hàng đợi Q1
Tại Q1, tương tự công việc sau khi
chờ sẽ được cho một khoảng thời
gian thực thi là 16 milli giây. Nếu hết
thời gian này vẫn chưa kết thúc sẽ bị
chuyển sang Q2
125
Phan Trung Kiên
Multilevel Feedback Queue
Multilevel Feedback Queue được xác định bởi các
thông số
Có bao nhiêu hàng đợi?
Với mỗi queue sử dụng giải thuật lập lịch nào?
Xác lập lịch điểm thăng cấp cho một process?
Làm sao để xác lập lịch điểm giáng cấp một process?
Xác định được hàng đợi nào process sẽ vào khi process
đó cần thực thi?
126
Phan Trung Kiên
Policy và Mechanism
Rất quan trọng trong lập lịch và phân phối tài nguyên
Policy – chính sách
Điều gì (what) nên (hay cần) làm
Mechanism – kỹ thuật
Làm sao (how) để làm điều đó
Ví dụ
Policy: tất cả người dùng cần được công bằng
Mechanism: sử dụng round robin
Policy: công việc được trả tiền cao có độ ưu tiên cao
Mechanism: sử dụng các giải thuật có preemptive
127
Phan Trung Kiên
2.3.4. Lập lịch trên hệ thống nhiều CPU
Nếu có nhiều CPU thì có thể thực hiện việc chia tải
Phức tạp hơn so với lập lịch trên một processor
Làm sao để chia tải?
Asymmetric multiprocessor
Một master processor sẽ thực hiện lập lịch cho tất cả các processor còn lại
Symmetric multiprocessor (SMP)
Hoặc mỗi processor có một hàng đợi ready riêng và bộ lập lịch riêng
Hoặc có một hàng đợi ready chung cho tất cả processors
Một processor được chọn làm scheduler cho các processor khác
Hoặc mỗi processor có bộ lập lịch riêng và tự chọn process từ hàng đợi chung
để thực thi
128
Phan Trung Kiên
Processor affinity
Khi một process chạy trên một processor, có một
số dữ liệu được cache trên bộ nhớ cache của
processor
Khi một process được di dời sang một processor
khác
Cache của processor mới phải được repopulated
Cache của processor cũ phải được invalidated
vấn đề phí tổn
Processor affinity: liên kết với bộ xử lý
129
Phan Trung Kiên
Cân bằng tải
Một processor có quá nhiều tải, trong khi những
bộ xử lý khác thì lại rảnh
Cân bằng tải sử dụng:
Push migration: một task đặc biệt sẽ định kỳ kiểm tra
tải trên tất cả các processors và công việc sẽ được đẩy
đến processor rảnh
Pull migration: processor rảnh sẽ lấy công việc từ
processor đang bận
Một số hệ thống (ví dụ Linux) hiện thực cả hai
Cần phải có sự cân bằng giữa load balancing và
processor affinity
130
Phan Trung Kiên
Bài tập (1)
Process Burst Time
P1 10
P2 29
P3 3
P4 7
P5 12
Tất cả đều đến ở thời điểm 0
Xét các giải thuật FCFS, SFJ, và RR với quantum time = 10
Giải thuật nào cho
Thời gian đợi trung bình nhỏ nhất?
Thông năng cao nhất?
Thời gian quay vòng trung bình của process nhỏ nhất?
131
Phan Trung Kiên
Bài tập (2)
FCFS: thời gian đợi trung bình là 28 milli giây,
hãy tính các thông số khác
132
Phan Trung Kiên
Bài tập (3)
SJF (nonpreemptive): thời gian đợi trung bình là
13 milli giây, hãy tính các thông số khác
133
Phan Trung Kiên
Bài tập (4)
RR: thời gian đợi trung bình là 23 milli giây, hãy
tính các thông số khác
134
Các file đính kèm theo tài liệu này:
- sinhvienit_net_hdh_chuong_2_1021.pdf