- QUẢN LÝ TIẾN TRÌNH Phan Trung Kiên Bộ môn Kỹ thuật máy tính và Mạng Nội dung2.1. - Deadlock (bế tắc) Phan Trung Kiên 2 2.1. - Tiến trình 2.1.1. - Đị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 3 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 4Các bước nạp chương trình vào bộ nhớ Phan Trung Kiên 5 Từ chương trình đến tiến trình Dùng load module để biểu diễn chương trình thực thi được Layout logic của process image Process image in main memory Executable binary file (load module) start address program program code code data data stack Phan Trung Kiên 6 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 7 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 8 Các trạng thái của tiến trình (tt) Chuyển đổi giữa các trạng thái của tiến trình terminated new admit dispatch exit ready running interrupt I/O or event I/O or completion event wait waiting Phan Trung Kiên 9 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 10 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 11 Quản lý các tiến trình: các hàng đợi Ví dụ các PCB running 7 process number ready 11 4 2 17 waiting 19 11 Có gì sai trong ví dụ? Phan Trung Kiên 12 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 13 Các hàng đợi định thời Job queue Ready queue Device queues. - Phan Trung Kiên 14Mô 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 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 17 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. - 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 18Chuyển ngữ cảnh (tt) Phan Trung Kiên 19 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. - Quan hệ cha-con định nghĩa một cây tiến trình. - Phan Trung Kiên 20 Cây tiến trình trong Linux/Unix rootpagedaemon swapper init bash bash bash gcc ls mkdir grep 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 22 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 23 Ví dụ tạo process với fork()#include #include int main (int argc, char *argv. - Phan Trung Kiên 24 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 25 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. - 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 26 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 đó. - Phan Trung Kiên 27 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ỉ Phan Trung Kiên 28 Mô hình giao tiếp(a) Message passing. - Phan Trung Kiên 29 Message passing system Làm thế nào để các tiến trình giao tiếp nhau? Các vấn đề. - 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 Phan Trung Kiên 30 2.2 Luồng (Thread) 2.2.1. - Multithreading với Java Phan Trung 44 Kiên 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 45 Kiên 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 46 KiênTiến trình đơn luồng và đa luồng Phan Trung Kiên 47 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 48 Kiên Sử dụng threadmouse A word processor with three threads Phan Trung 49 Kiên Process & thread information Per process items Address space Open files Child processes Signals & handlers Accounting info Global variablesPer thread items Per thread items Per thread itemsProgram counter Program counter Program counterRegisters Registers RegistersStack & stack pointer Stack & stack pointer Stack & stack pointerState State State(Tiến trình gồm ba thread) Phan Trung 50 Kiên Multiplexing CPU giữa các thread time CPUba tiến trìnhsingle-threaded Phan Trung 51 Kiên Multiplexing CPU giữa các thread (tt) time CPUhai tiến trìnhmultithreaded Phan Trung 52 Kiên Ví dụ Pthread program (Linux)#include Static Datavoid* thread1. - Sơ đồ bộ nhớ} Phan Trung 53 Kiên Ư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. - Phan Trung 54 Kiên 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 55 Kiên User thread 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. - user thread thread library thread library thread library PCB PCB PCB kernel Phan Trung 56 Kiên 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 57 Kiên 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 58 Kiên 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 59 Kiên 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. - 60 Phan Trung Kiên 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ơ kernel thread chế cung cấp được nhiều 61 Phan Trung Kiên 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 62 Phan Trung Kiên 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 63 Kiên 2.2.4. - 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) Phan Trung 64 Kiên Đối tượng được định thời trong hệ thống là các kernel thread2.2.4. - Thread trong Solaris (tt) many-to-many Phan Trung 65 Kiên2.2.4. - Thread trong Solaris (tt) LWP1 LWP2 LWP3 Tiến trình trong Solaris Phan Trung 66 Kiên 2.2.5. - Hiện thực (implementing) Runnable interface Phan Trung 67 KiênTrạng thái của Java thread Phan Trung Kiên 682.3. - Lập lịch trên hệ thống nhiều CPU Phan Trung Kiên 70 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 Phan Trung Kiên 71 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 Phan Trung Kiên 72 Phân loại các hoạt động lập lịch newLong-term Long-termscheduling scheduling Đường gạch rời: chuyển đổi không nhất thiết có Medium-term suspended scheduling Short-term ready ready scheduling running Medium-term schedulingsuspended blocked terminated blocked Phan Trung Kiên 73 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 Phan Trung Kiên 74 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 Phan Trung Kiên 75 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ớ Phan Trung Kiên 76 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. - Signal Phan Trung Kiên 77 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 Phan Trung Kiên 78 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) Phan Trung Kiên 79 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. - 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 Phan Trung Kiên 80 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 Tải bản FULL (121 trang): https://bit.ly/3dT1NTl Dự phòng: fb.com/TaiHo123doc.net Đị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) Phan Trung Kiên 81 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: Tải bản FULL (121 trang): https://bit.ly/3dT1NTl Dự phòng: fb.com/TaiHo123doc.net 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 Phan Trung Kiên 82 Dispatch latency 3139332Conflict phase: xem p. - 171 Phan Trung Kiên 83
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt