Bài giảng Hệ điều hành - Quản lý tiến trình

Môn học: Hệ điều hành
 1
• Phân biệt tiến trình và tiểu trình
• So sánh các thuật toán điều phối tiến trình
 2
3
• Tiến trình là một chương trình đang được thực thi
• Một tiến trình cần sử dụng các tài nguyên: CPU, bộ nhớ, 
 tập tin, thiết bị nhập xuất để hoàn tất công việc của nó
 4
• Tạo tiến trình
 – Khởi động hệ thống
 – Người dùng kích hoạt một chương trình
 – Một tiến trình tạo một tiến trình khác
 • Unix/ Linux: exec(), fork()
 • Windows: CreateProcess()
 – Cây tiến trình
 • Unix/ Linux: các tiến trình cha,
 con có mối quan hệ chặt chẽ
 • Windows: các tiến trình cha,
 con độc lập với nhau
 5
• Dừng tiến trình
 – Xử lý xong lệnh cuối cùng hay gọi lệnh kết thúc
 • Unix/ Linux: exit()
 • Windows: ExitProcess()
 – Một tiến trình yêu cầu dừng một tiến trình khác
 • Unix/ Linux: kill()
 • Windows: TerminateProcess()
 Điều gì xảy ra nếu tiến trình “nạn nhân” vẫn chưa 
 muốn “chết”?
 – Do lỗi chương trình
 6
 Nhận CPU
 running
 ready
  R
 R s
 s Trả CPU  CPU
 CPU
 blocked Chờ resource
 Nhận
 resource  Rs
  CPU
 CPU-bound
 process
 IO-bound
 7
 process
Vào Thoát
 ready queue CPU
 Disk 1
 disk queue
 Disk 2
 Network network queue
 I/O other I/O queue
 8
• Định danh (Process ID) pid
• Trạng thái tiến trình State
• Ngữ cảnh tiến trình
 (State, details)
 – Trạng thái CPU
 – Bộ xử lý (cho máy nhiều CPU) Context
 – Bộ nhớ chính
 (IP, Mem, Files)
 – Tài nguyên sử dụng /tạo lập
• Thông tin giao tiếp Relatives
 – Tiến trình cha, tiến trình con ( Dad, children)
 – Độ ưu tiên
 Scheduling statistic
• Thông tin thống kê
 Process control Block – PCB
 9
 Excel
Visual C++
 CDplayer
 Winword
 10
Tiến trình 1 Tiến trình 2 Tiến trình 3
 Điều phối 
 như thế nào 
 ???
 CPU
 Hệ
 điều 
 hành
 11
• Mục tiêu điều phối
• Lựa chọn tiến trình
 – Tiêu chuẩn lựa chọn
 – Thời điểm lựa chọn
• Chuyển đổi giữa các tiến trình
• Các chiến lược điều phối
 – FCFS  Multiple Queues
 – Round Robin  Guaranteed Scheduling
 – Priority  Lottery Scheduling
 – SJF  Fair-Share Scheduling
 12
• Mục tiêu chung
 – Công bằng sử dụng CPU
 – Cân bằng sử dụng các thành phần của hệ thống
• Hệ thống theo lô
 – Tối ưu throughput
 – Giảm thiểu turnaround time: Tquit – Tarrive 
 – Tận dụng CPU
• Hệ thống tương tác
 – Giảm thiểu thời gian chờ (Tối ưu thời gian hồi đáp): Tin ReadyQueue
 – Cân đối mong muốn của người dùng
• Hệ thống thời gian thực
 – Thời hạn hoàn thành công việc
 13
• Tiêu chí lựa chọn
 – Chọn tiến trình vào RQ trước
 – Chọn tiến trình có độ ưu tiên cao hơn
• Thời điểm lựa chọn
 – Điều phối độc quyền (non-preemptive scheduling): một khi tiến 
 trình đang ở trạng thái Running, nó sẽ tiếp tục sử dụng CPU cho 
 đến khi kết thúc hoặc bị block vì I/O hay các dịch vụ của hệ thống 
 (độc chiếm CPU)
 • P cur kết thúc
 • P cur : running ->blocked
 – Điều phối không độc quyền (preemptive scheduling): ngoài thời 
 điểm lựa chọn như điều phối độc quyền, tiến trình đang sử dụng 
 CPU có thể bị ngắt (chuyển sang trạng thái Ready) khi hết thời 
 gian qui định hoặc có tiến trình có độ ưu tiên hơn vào 
 ReadyQueue
 14
 Q : blocked• / new -> ready
Context switching – Nhiệm vụ của Dispatcher
 15
• Bản thân HĐH cũng là 1 phần mềm, nghĩa là cũng sử 
 dụng CPU để có thể chạy được.
• Câu hỏi: Khi tiến trình A đang chiếm CPU, làm thế nào 
 HĐH có thể thu hồi CPU lại được ? (vì lúc này HĐH không 
 giữ CPU)
 – Ép buộc tiến trình thỉnh thoảng trả CPU lại cho HĐH ? Có khả thi ?
 – Máy tính phải có 2 CPU, 1 dành riêng cho HĐH ?
 – HĐH sử dụng ngắt đồng hồ (ngắt điều phối) để kiểm soát hệ 
 thống
 • Mỗi khi có ngắt đồng hồ, HĐH kiểm tra xem có cần thu hồi CPU từ 1 
 tiến trình nào đó lại hay không ?
 • HĐH chỉ thu hồi CPU khi có ngắt đồng hồ phát sinh.
 • Khoảng thời gian giữa 2 lần ngắt điều phối gọi là chu kỳ đồng hồ (tối 
 thiểu là 18.2 lần / giây)
 16
• FCFS
• Round Robin
• Priority
• SJF
• Multiple Queues
• Guaranteed Scheduling
• Lottery Scheduling
• Fair-Share Scheduling
 17
• Tiêu chí lựa chọn tiến trình
 – Thứ tự vào hàng đợi Ready Queue
• Thời điểm lựa chọn tiến trình
 – Độc quyền Ready Queue
 C B A CPU
 Ready Queue
 C B CPU
 Ready Queue
 C CPU
 18
 P TarriveRQ CPU burst P TT WT
P1 0 24 P1 24 0
P2 1 3 P2 27-1 24-1
P3 2 3 P3 30-2 27-2
 AvgWT = (23+25)/3 = 16
 P1 P2 P3
 0 24 27
 0:00 P1 vào RQ 0:24 P1 kết thúc
 P1 dùng CPU P2 dùng CPU
 0:01 P2 vào RQ 0:27 P2 kết thúc
 0:02 P3 vào RQ P3 dùng CPU
 19
• Đơn giản, dễ cài đặt
• Chịu đựng hiện tượng tích lũy thời gian chờ
 – Tiến trình có thời gian xử lý ngắn đợi tiến trình có 
 thời gian xử lý dài
 – Ưu tiên tiến trình cpu-bounded
• Có thể xảy ra tình trạng độc chiếm CPU
• Không phù hợp với hệ thống tương tác người 
 dùng
 20
• Mỗi tiến trình chỉ sử dụng một lượng q cho mỗi lần sử dụng CPU
• Tiêu chí lựa chọn tiến trình
 – Thứ tự vào hàng đợi Ready Queue Quantum/
• Thời điểm lựa chọn tiến trình Time slice
 – Không độc quyền (không có độ ưu tiên)
 Ready Queue
 C B A CPU A chỉ chiếm CPU trong q ms
 Ready Queue
 B được giao quyền sử dụng CPU
 A C B CPU trong q ms kế tiếp
 Ready Queue
 C được giao quyền sử dụng CPU
 B A C CPU trong q ms kế tiếp
 21
 P TarriveRQ CPU burst P TT WT
P1 0 24 P1 30 0+(10-4)
P2 1 3 P2 7-1 4-1
P3 2 3 P3 10-2 7-2
 AvgWT = (6+3+5)/3 = 4.66
 P1 P2 P3 P1 P1 P1 P1 P1
 0 4 7 10 14 18 22 26 30
 0:00 P1 vào, P1 dùng CPU 0:07 P2 dừng, P3 dùng CPU
 0:01 P2 vào (đợi) 0:10 P3 dừng, P1 dùng CPU
 0:02 P3 vào (đợi) 0:14 P1 vẫn chiếm CPU
  22
 0:04 P1 hết lượt, P2 dùng CPU
 . Tranh chấp vị trí trong RQ:
 P TarriveRQ CPU burst
 “Chung thủy” 
P1 0 24 1. P : running -> ready
 2. P : blocked -> ready
P2 4 3 3. P: new ->ready
 . Không phải luôn luôn có thứ tự điều 
P3 12 3 phối P1 P2 P3 P4 P1 P2 P3 P4...
 P1 P1 P2 P1 P3 P1 P1 P1
 0 4 8 11 15 18 22 26 30
RQ 0:04 P1 P2 “Chung thủy”
 0:00 P1 0:8 P2 P1
 0:04 0:11 P1
 0:15 P3 P1
 ? 0:04 P2 P1 “Có mới nới cũ”
 23
 0:18 P1
• Loại bỏ hiện tượng độc chiếm CPU
• Phù hợp với hệ thống tương tác người dùng
• Hiệu quả ? Phụ thuộc vào việc lựa chọn 
 quantum q
 – q quá lớn => FCFS (giảm tính tương tác)
 – q quá nhỏ => chủ yếu thực hiện chuyển đổi ngữ 
 cảnh (context switching)
 – Thường q = 10-100 milliseconds
 24
• Một độ ưu tiên (integer) được gán vào mỗi tiến trình
• Phân biệt tiến trình quan trọng với tiến trình bình thường
• Tiêu chí lựa chọn tiến trình
 – Tiến trình có độ ưu tiên cao nhất
• Thời điểm lựa chọn tiến trình
 – Độc quyền
 – Không độc quyền (có độ ưu tiên)
 25
 P TRQ Priority CPU burst P TT WT
P1 0 2 24 P1 30 0+(7-1)
P2 1 0 3 P2 4-1 0
P3 2 1 3 P3 7-2 4-2
 AvgWT = (6+0+2)/3 = 2.66
 P1 P2 P2 P3 P1
 0 1 2 4 7 30
 0:00 P1 vào, P1 dùng CPU 0:4 P2 kết thúc, P3 dùng CPU
 0:01 P2 vào (độ ưu tiên cao hơn P1) 0:7 P3 dừng, P1 dùng CPU
 P2 dành quyền dùng CPU 0:30 P1 dừng
 0:02 P3 vào (độ ưu tiên thấp hơn P2)
 26
 P3 không dành được quyền dùng CPU 
• Cách tính độ ưu tiên ?
 – Hệ thống gán
 – Người dùng gán
• Tính chất độ ưu tiên
 – Tĩnh
 • Vấn đề Starvation: các tiến trình độ ưu tiên thấp có thể 
 không bao giờ thực thi được
 • Giải pháp Aging – tăng độ ưu tiên cho tiến trình chờ lâu 
 trong hệ thống (sống lâu lên lão làng)
 – Động
 27
 Ready Queue
 P2
 (cần 3 chu kỳ)
 P1 CPU
 (cần 5 chu kỳ)
 P3
 (cần 7 chu kỳ)
 Là một dạng độ ưu tiên đặc biệt với độ ưu tiên
 pi = thời_gian_còn_lại(Processi)
 Có thể cài đặt độc quyền hoặc không độc quyền
 28
 P TarriveRQ CPU burst P TT WT
P1 0 24 P1 30 0+(7-1)
P2 1 3 P2 4-1 0
P3 2 3 P3 7-2 4-2
 AvgWT = (6+0+2)/3 = 2.66
 P1 P2 P3 P1
 0 1 4 7 30
 0:00 P1 vào, P1 dùng CPU 0:4 P2 kết thúc, P3 dùng CPU
 0:01 P2 vào (độ ưu tiên cao hơn P1) 0:7 P3 dừng, P1 dùng CPU
 P2 dành quyền dùng CPU 0:30 P1 dừng
 29
• Tối ưu thời gian chờ
• Làm sao biết được thời gian còn lại cần thực thi 
 của một tiến trình
 – Không khả thi ?
 – Ước lượng – sử dụng thời gian sử dụng CPU ngay 
 trước, dùng qui luật trung bình giảm theo hàm mũ.
 n 1 t n 1 n
 length of the nth predicted value for 
 0<= α <=1 th
 CPU burst the n CPU burst
 most recent relative weight past history
 information 30
• =0
 – n+1 = n
 – Không xét các giá trị thực đã dùng CPU.
• =1
 – n+1 = tn
 – Chỉ dùng giá trị thực mới dùng CPU.
• Nếu mở rộng công thức, ta được:
 • n+1 = tn+(1 - ) tn -1 + 
 j 
 • +(1 - ) tn -1 + 
 n=1 
 • +(1 - ) tn 0
• Vì và (1 - ) nhỏ hơn hay bằng 1,mỗi giá trị kế tiếp sẽ 
 nhỏ dần.
• Thực hiện điều phối theo chiến lược FCFS, 
 RR với q = 4 và SJF
• Tính WT
 P TarriveRL CPU burst
 P1 0 20
 P2 1 5
 P3 2 3
 P4 12 6
 32
 P TarriveRL CPU1 IO1 IO1 CPU2 IO2 IO2
 burst R T burst R T
 P1 0 5 R1 2 2 R2 2
 P2 2 1 R1 10 1 R1 4
 P3 10 8 R2 1 0 Null 0
CPU P1 P2 P1 P3 P2 P3 P1 P3
 0 2 3 6 10 13 14 15 17 21
R1 P2 P1 P2
 3 13 15 19
 R2 P1 P3
 17 19 21 22
 33
 Độ ưu tiên • Tổ chức n RQ ứng với 
 1 nhiều mức ưu tiên
 • Mỗi RQi có thể áp dụng 
 một chiến lược điều phối 
CPU
 2 riêng
 • Điều phối giữa các RQ:
 – Điều phối theo độ ưu tiên 
  của RQ
 Có thể xảy ra starvation
 n Giải pháp Aging :
 • Chờ lâu quá : chuyển lên RQ
 với độ ưu tiên cao hơn
 Kết hợp • Chiếm CPU lâu quá : chuyển 
 xuống RQ với độ ưu tiên 
 nhiều chiến lược thấp hơn
 – Time slice – mỗi hàng đợi 
 nhận chiếm CPU một khoảng 
 thời gian
 34
35
• Ba hàng đợi: 
 – Q0 – time quantum 8 mili giây
 – Q1 – time quantum 16 mili giây
 – Q2 – FCFS
• Lập lịch
 – Một việc mới vào queue Q0 nó 
 được điều phối theo FCFS. Khi nó 
 nhận CPU, chỉ dùng trong 8 mili 
 giây. Nếu chưa hoàn tất trong 8 
 mili giây, công việc chuyển sang 
 queue Q1.
 – Tại Q1 cv được điều phối theo 
 FCFS và nhận CPU thêm 16 mili 
 giây. Nếu vẫn chưa hoàn tất, nó 
 sẽ bị đẩy qua queue Q2.
 36
Vừa tìm hiểu
 37
• Đơn giản
 – Viết chương trình theo kiểu bấm giờ bằng cách mỗi lần nhấn 
 một phím thì sẽ in ra số nhịp đã trôi qua từ khi chương trình bắt 
 đầu chạy, với mỗi nhịp bằng 1 giây, chương trình sẽ kết thúc khi 
 nhấn ESC.
• Phức tạp hơn
 – Viết chương trình hiển thị 10 ký tự trên màn hình, mỗi ký tự di 
 chuyển ngẫu nhiên, liên tục với tốc độ tùy ý. Khi di chuyển nếu 
 chạm biên màn hình thì ký tự sẽ xuất hiện lại tại giữa màn hình. 
 Chương trình kết thúc khi người dùng nhấn phím bất kỳ.
• Bài toán thực tế:
 – Ứng dụng web phục vụ cùng lúc nhiều yêu cầu người dùng
 38
• Các tiến trình độc lập, không có sự liên lạc với nhau
 Excel
 winword
 Visual C
 CDplayer
 OS
• Muốn trao đổi thông tin với nhau, các chương trình cần 
 được xây dựng theo mô hình liên lạc đa tiến trình (IPC –
 Inter-Process Communication) Phức tạp, chi phí cao
 39
40
• Tiểu trình là một dòng xử lý trong một tiến trình
• Mỗi tiến trình luôn có một tiểu trình chính (dòng 
 xử lý cho hàm main())
• Ngoài tiểu trình chính, tiến trình còn có thể có 
 nhiều tiểu trình con khác
• Các tiểu trình của một tiến trình
 – Chia sẻ không gian vùng code và data
 – Có vùng stack riêng
 41
• TCB thường chứa các thông tin riêng của mỗi tiểu trình
 – ID của tiểu trình
 – Không gian lưu các thanh ghi
 – Con trỏ tới vị trí xác định trong ngăn xếp
 – Trạng thái của tiểu trình
• Thông tin chia sẻ giữa các tiểu trình trong một tiến trình
 – Các biến toàn cục
 – Các tài nguyên sử dụng như tập tin,
 – Các tiến trình con
 – Thông tin thống kê
 – 
 42
PC Mã hàm thread_create()
SP
 PCBs
 TCBs
 thread_create()
 new_thread_starts_here
 stacks
 43
• Quản lý tiểu trình mức người dùng  Quản lý tiểu trình mức hệ thống 
• 3 thư viện chính hỗ trợ:  Hệ điều hành hỗ trợ:
 • POSIX Pthreads  Windows XP/2000
 • Win32 threads  Solaris
 • Java threads  Linux
 44
 Mac OS X 
45
• Tại sao không dùng nhiều tiến trình để thay thế cho việc 
 dùng nhiều tiểu trình ?
 – Các tác vụ điều hành tiểu trình (tạo, kết thúc, điều phối, chuyển 
 đổi,) ít tốn chi phí thực hiện hơn so với tiến trình
 – Liên lạc giữa các tiểu trình thông qua chia sẻ bộ nhớ, không cần 
 sự can thiệp của kernel 
 46
Quản lý tiểu trình mức người dùng Quản lý tiểu trình mức hệ thống
 47
• Tự tìm hiểu
 (Modern Operating System - Tanenbaum)
 – Guaranteed Scheduling
 – Lottery Scheduling
 – Fair-Share Scheduling
• Tham khảo thêm
 – Tổ chức, quản lý tiến trình của hệ điều hành Windows
 – Tổ chức, quản lý tiến trình của hệ điều hành 
 Unix/Linux
 48