- 1. 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
- 2. 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)
- 3. 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
- 4. 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
- 5. 5 Các bước nạp chương trình vào bộ nhớ
- 6. 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
- 7. 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,…)
- 8. 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.
- 9. 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
- 10. 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)
- 11. 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
- 12. 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ụ
- 13. 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)
- 14. 14 Các hàng đợi định thời Job queue Ready queue Device queues …
- 15. lập lịch tiến trình Phan Trung Kiên 15
- 16. 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
- 17. 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)
- 18. 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
- 19. 19 Chuyển ngữ cảnh (tt)
- 20. 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.
- 21. trong Linux/Unix root swapper pagedaemon init bash bash bash mkdir grep ls gcc
- 22. 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.
- 23. 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ộ
- 24. 24 Ví dụ tạo process với fork()
include <stdio.h>
include <unistd.h> 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 errorn”); exit(-1); } } - 25. 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,…)
- 26. 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
- 27. 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.
- 28. 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ỉ
- 29. tiếp Phan Trung Kiên 29 (a) Message passing. (b) Shared memory.
- 30. 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
- 31. 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
- 32. 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
- 33. 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
- 34. luồng và đa luồng Phan Trung Kiên 47
- 35. 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
- 36. word processor with three threads mouse Phan Trung Kiên
- 37. 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
- 38. các thread CPU time ba tiến trình single-threaded Phan Trung Kiên
- 39. các thread (tt) CPU hai tiến trình multithreaded time Phan Trung Kiên
- 40. program (Linux)
include <stdio.h> void* thread1(){ int i; for (i = 0; i < 10; i++){ printf(“Thread 1n”); sleep(1); } } void* thread2(){ int i; for (i = 0; i < 10; i++){ printf(“Thread 2n”); 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 - 41. 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
- 42. 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
- 43. 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
- 44. 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
- 45. 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
- 46. đ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
- 47. 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
- 48. 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 Phan Trung Kiên
- 49. 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
- 50. 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
- 51. 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
- 52. Solaris (tt) many-to-many Phan Trung Kiên
- 53. Solaris (tt) Tiến trình trong Solaris LWP1 LWP2 LWP3 … Phan Trung Kiên
- 54. 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
- 55. Java thread Phan Trung Kiên 68
- 56. CPU (CPU Scheduling)
- 57. 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
- 58. 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
- 59. 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
- 60. 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
- 61. 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
- 62. 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
- 63. 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
- 64. 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
- 65. 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
- 66. 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
- 67. 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
- 68. 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 Tải bản FULL (121 trang): https://bit.ly/3dT1NTl Dự phòng: fb.com/TaiHo123doc.net
- 69. 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 Tải bản FULL (121 trang): https://bit.ly/3dT1NTl Dự phòng: fb.com/TaiHo123doc.net
- 70. latency Conflict phase: xem p. 171 83 3139332
|
