Bài giảng chương 3: Quá trình

CHƯƠNG 3: QUÁ TRÌNH 3.2 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 NỘI DUNG „ Khái niệm quá trình „ Lập lịch biểu quá trình „ Các hoạt động trên quá trình „ Hợp tác các quá trình „ Liên lạc giữa các quá trình „ Liên lạc trong các hệ Client-Server 3.3 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 KHÁI NIỆM QUÁ TRÌNH „ HĐH thực hiện nhiều kiểu chương trình: z Hệ thống bó – jobs z Các hệ thống chia sẻ thời gian – các chương trình người dùng/ các nhiệm vụ „ Công việc (job) = quá trình (process) „ Quá trình là một chương trình trong sự thực hiện; sự thực hiện quá trình phải tiến triển theo kiểu cách tuần tự „ Một quá trình bao gồm: z Bộ đếm chương trình z Stack z Phần dữ liệu 3.4 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 Process in Memory 3.5 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 TRẠNG THÁI QUÁ TRÌNH „ Khi quá trình thực hiện nó thay đổi trạng thái z new: Quá trình đang được khởi tạo z running: các chỉ thị đang được thực hiện z waiting: Quá trình đang chờ đợi một biến cố xảy ra z ready: Quá trình đang chờ được cấp processor z terminated: Quá trình kết thúc sự thực hiện 3.6 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 BIỂU ĐỒ TRẠNG THÁI QUÁ TRÌNH 3.7 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 KHỐI ĐIỀU KHIỂN QUÁ TRÌNH Process Control Block (PCB) Thông tin kết hợp với mỗi quá trình „ Trạng thái quá trình „ Bộ đếm chương trình „ Các thanh ghi CPU „ Thông tin lập lịch biểu CPU „ Thông tin quản trị bộ nhớ „ Thông tin kiểm toán „ Thông tin trạng thái I/O 3.8 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 KHỐI ĐIỀU KHIỂN QUÁ TRÌNH (PCB) 3.9 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 SỰ CHUYỂN CPU QUA LẠI GIỮA CÁC QUÁ TRÌNH 3.10 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 CÁC HÀNG ĐỢI LẬP LỊCH BIỂU QUÁ TRÌNH „ Hàng đợi công việc (Job Queue) – tập tất cả các quá trình trong hệ thống „ Hàng đợi sẵn sàng (Ready Queue) – tập các quá trình nằm trong bộ nhớ sẵn sàng và chờ đợi thực hiện „ Các hàng đợi thiết bị (Device Queues) – tập các quá trình chờ đợi một thiết bị I/O „ Các quá trình di trú giữa các hàng đợi 3.11 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 HÀNG ĐỢI SẴN SÀNG & CÁC HÀNG ĐỢI THIẾT BỊ I/O 3.12 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 SƠ ĐỒ LẬP LỊCH BIỂU QUÁ TRÌNH 3.13 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 CÁC BỘ LẬP LỊCH BIỂU „ Bộ lập lịch biểu dài hạn (Long-term scheduler / job scheduler) – chọn các quá trình để chuyển sang hàng đợi sẵn sàng „ Bộ lập lịch biểu ngắn hạn (Short-term scheduler / CPU scheduler) – chọn quá trình sẽ được thực hiện kế tiếp và cấp phát CPU cho nó 3.14 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 BỔ XUNG LẬP LỊCH BIỂU TRUNG HẠN 3.15 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 CÁC BỘ LẬP LỊCH BIỂU (Cont.) „ Bộ lập lịch biểu ngắn hạn được viện dẫn thường xuyên (ms) ⇒ nhanh „ Bộ lập lịch biểu dài hạn được viện dẫn ít thường xuyên (seconds, minutes) ⇒ có thể chậm „ Bộ lập lịch biểu dài hạn điều khiển bậc đa chương „ Các quá trình được phân thành: z Quá trình I/O-bound – tiêu nhiều thời gian cho hoạt động I/O hơn cho tính toán, gồm nhiều CPU bursts ngắn z Quá trình CPU-bound – tiêu nhiều thời gian hơn cho tính toán; gồm một số ít CPU bursts rất dài 3.16 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 CHUYỂN NGỮ CẢNH „ Khi CPU chuyển cho quá trình khác, hệ thống phải lưu lại trạng thái của quá trình cũ và nạp trạng thái của quá trình mới „ Thời gian chuyển ngữ cảnh là một “phí”; hệ thống không làm việc “hữu ích” khi chuyển ngữ cảnh „ Thời gian chuyển ngữ cảnh phụ thuộc vào hỗ trợ phần cứng 3.17 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 TẠO QUÁ TRÌNH „ Quá trình cha tạo ra các quá trình con, các quá trình con lại có thể tạo ra các quá trình con của nó, tạo ra một cây các quá trình „ Chia sẻ tài nguyên z Cha và con chia sẻ tất cả các tài nguyên z Các con chia sẻ một tập con các tài nguyên của cha z Cha và con không chia sẻ tài nguyên „ Sự thực hiện z Cha và các con thực hiện đồng thời z Cha chờ đến tận khi con kết thúc 3.18 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 TẠO QUÁ TRÌNH (Cont.) „ Không gian địa chỉ z Con sao lại của cha z Con có một chương trình được nạp vào trong nó „ Ví dụ: UNIX z Fork: lời gọi hệ thống tạo quá trình mới z Exec: lời gọi hệ thống được dùng sau fork để thay thế không gian bộ nhớ của quá trình với chương trình mới 3.19 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 TẠO QUÁ TRÌNH 3.20 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 CHƯƠNG TRÌNH C PHÂN NHÁNH QUÁ TRÌNH int main() { pid_t pid; /* fork another process */ pid = fork(); if (pid < 0) { /* error occurred */ fprintf(stderr, "Fork Failed"); exit(-1); } else if (pid == 0) { /* child process */ execlp("/bin/ls", "ls", NULL); } else { /* parent process */ /* parent will wait for the child to complete */ wait (NULL); printf ("Child Complete"); exit(0); } } 3.21 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 CÂY QUÁ TRÌNH TRONG Solaris 3.22 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 KẾT THÚC QUÁ TRÌNH „ Quá trình thực hiện xong chỉ thị sau cùng và yêu cầu HĐH xóa nó (exit) z Xuất dữ liệu từ con đến cha (thông qua wait) z Các tài nguyên của quá trình được thu hồi bởi HĐH „ Cha có thể kết thúc sự thực hiện của các quá trình con (abort) z Con vượt quá các tài nguyên được cấp phát z Nhiệm vụ của con không còn được cần thiết nữa z Nếu cha đang thoát Một số HĐH không cho phép con tiếp tục nếu cha kết thúc – Tất cả các con bị kết thúc – Kết thúc hàng loạt (cascading termination) 3.23 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 CÁC QUÁ TRÌNH HỢP TÁC „ Quá trình độc lập không ảnh hưởng và không bị ảnh hưởng bởi sự thực hiện của quá trình khác „ Quá trình hợp tác có thể ảnh hưởng và bị ảnh hưởng bởi sự thực hiện của quá trình khác „ Các lợi thế của sự hợp tác quá trình z Chia sẻ thông tin z Tăng tốc độ tính toán z Module hóa z Tiện lợi 3.24 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 VẤN ĐỀ PRODUCER-CONSUMER „ Kiểu mẫu cho các quá trình hợp tác, quá trình producer sản suất thông tin được tiêu thụ bởi quá trình consumer z Buffer không giới nội (unbounded-buffer) không bị giới hạn về kích cỡ buffer z Buffer giới nội (bounded-buffer) buffer có kích cỡ cố định 3.25 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 BUFFER GIỚI NỘI – GIẢI PHÁP BỘ NHỚ CHIA SẺ „ Dữ liệu chia sẻ #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; „ Giải pháp đúng nhưng chỉ sử dụng được BUFFER_SIZE-1 phần tử 3.26 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 BUFFER GIỚI NỘI – PHƯƠNG PHÁP Insert() while (true) { /* Produce an item */ while (((in = (in + 1) % BUFFER SIZE count) == out) ; /* do nothing -- no free buffers */ buffer[in] = item; in = (in + 1) % BUFFER SIZE; } 3.27 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 BUFFER GIỚI NỘI – PHƯƠNG PHÁP Remove() while (true) { while (in == out) ; // do nothing -- nothing to consume // remove an item from the buffer item = buffer[out]; out = (out + 1) % BUFFER SIZE; return item; } 3.28 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 LIÊN LẠC GIỮA CÁC QUÁ TRÌNH (IPC) „ Cơ chế cho sự liên lạc giữa các quá trình và đồng bộ hóa các hành động của chúng „ Hệ thống thông điệp – các quá trình liên lạc với nhau không sử dụng đến các biến chia sẻ „ IPC cung cấp hai hoạt động: z send(message) – message kích cỡ cố định/thay đổi z receive(message) „ Nếu P và Q muốn liên lạc, chúng cần phải: z Thiết lập một nối kết liên lạc z Trao đổi các thông điệp (messages) dùng send/receive „ Thực thi nối kết liên lạc: z Vật lý (bộ nhớ chia sẻ, hardware bus) z logic (Các tính chất logic) 3.29 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 MỘT SỐ VẤN ĐỀ THỰC THI „ Các nối kết được thiết lập như thế nào? „ Một nối kết có thể kết hợp với hơn hai quá trình? „ Có thể có bao nhiêu nối kết giữa mỗi cặp quá trình liên lạc? „ Khả năng của một nối kết? „ Kích cỡ thông điệp mà nối kết chịu đựng được là cố định / thay đổi? „ Một nối kết là đơn hướng hay lưỡng hướng? 3.30 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 CÁC MÔ HÌNH LIÊN LẠC 3.31 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 LIÊN LẠC TRỰC TIẾP „ Các quá trình phải định tên tường minh mỗi quá trình khác: z send (P, message) – gửi một message cho quá trình P z receive(Q, message) – nhận một message từ quá trình Q „ Các tính chất của một nối kết liên lạc z Các nối kết được thiết lập tự động z Một nối kết được kết hợp với đúng một cặp quá trình liên lạc z Giũa mỗi cặp có đúng một nối kết z Nối kết có thể đơn hướng, nhưng thông thường là lưỡng hướng 3.32 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 LIÊN LẠC GIÁN TIẾP „ Các thông điệp được gửi và nhận từ mailboxes (cũng được tham khảo như các ports) z Mỗi mailbox có một id duy nhất z Các quá trình có thể liên lạc nếu chúng chia sẻ một mailbox „ Các tính chất của nối kết liên lạc z Nối kết chỉ được thiết lập nếu các quá trình chia sẻ một mailbox chung z Một nối kết có thể được kết hợp với nhiều quá trình z Mỗi cặp quá trình có thể chia sẻ một vài nối kết liên lạc z Nối kết có thể đơn hướng hoặc lưỡng hướng 3.33 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 LIÊN LẠC GIÁN TIẾP „ Các hoạt động z Tạo một mailbox mới z Gửi và nhận messages qua mailbox z Phá hủy mailbox „ Các nguyên thủy: send(A, message) – gửi một message đến mailbox A receive(A, message) – nhận một message từ mailbox A 3.34 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 LIÊN LẠC GIÁN TIẾP „ Chia sẻ mailbox z P1, P2, và P3 chia sẻ mailbox A z P1, gủi; P2 và P3 nhận z Ai nhận message? „ Các giải pháp z Cho phép một nối kết kết hợp với nhiều nhất hai quá trình z Chỉ cho phép một quá trình tại một thời điểm thực hiện hoạt động nhận z Cho phép hệ thống chọn tùy ý người nhận. Người gửi báo ai sẽ nhận. 3.35 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 ĐỒNG BỘ HÓA „ Truyền Message có thể là blocking / non-blocking „ Blocking được xét là đồng bộ (synchronous) z Gửi Blocking: người gửi bị ngăn đến tận khi message được nhận z Nhận Blocking: người nhận bị ngăn đến tận khi một message là sẵn có „ Non-blocking được xét là phi đồng bộ (asynchronous) z Gửi Non-blocking: Người gửi gửi message và tiếp tục z Nhận Non-blocking: người nhận nhận một message hợp lệ / vô hiệu 3.36 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 BUFFER „ Hàng đợi các messages gắn với nối kết; được thực thi bởi một trong ba cách 1. Sức chứa Zero – 0 messages Người gửi phải chờ người nhận (hẹ hò) 2. Sức chứa giới nội – n messages Người gửi phải chờ nếu nối kết đầy 3. Sức chứa không giới hạn Người gửi không phải chờ 3.37 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 LIÊN LẠC Client-Server „ Sockets „ Remote Procedure Calls - RPC „ Remote Method Invocation (Java) -RMI 3.38 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 Sockets „ Một socket được định nghĩa như điểm cuối của một liên lạc „ Nối địa chỉ IP và port „ Socket 161.25.19.8:1625 tham khảo port 1625 trên host 161.25.19.8 „ Liên lạc gồm một cặp sockets 3.39 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 LIÊN LẠC Socket 3.40 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 GỌI THỦ TỤC TỪ XA Remote Procedure Calls - RPC „ Remote procedure call (RPC): gọi thủ tục giữ các quá trình trên các hệ thống mạng. „ Stubs – proxy phía client cho thủ tục trên server. „ Stub phía client định vị server và sắp xếp theo thứ tự (marshal) các tham số. „ Stub phía server nhận message này, tháo các tham số được, và thực hiện thủ tục trên server. 3.41 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 SỰ THỰC HIỆN RPC 3.42 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 Remote Method Invocation - RMI „ Remote Method Invocation (RMI) là một cơ chế Java tương tự RPC. „ RMI cho phép một chương trình Java program trên một máy gọi một phương pháp trên một đối tượng ở xa. 3.43 Silberschatz, Galvin and Gagne ©2005Operating System Concepts - 7th Edition, Feb 7, 2006 CÁC THAM SỐ ĐƯỢC SẮP THEO THỨ TỰ End of Chapter 3