Giáo trình Hệ điều hành - Chương 6: Quản lý quá trình

Nội dung text: Giáo trình Hệ điều hành - Chương 6: Quản lý quá trình

1. 10/01/2017 Chapter 6. Quản lý quá trình Khái niệm cơ bản Định thời CPU Các tác vụ cơ bản: tạo/kết thúc quá trình Sự cộng tác giữa các quá trình Giao tiếp giữa các quá trình 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: job ● Time-shared system: user program, task Quá trình (process) ● một chương trình đang thực thi  Một quá trình được định nghĩa bởi ● Trạng thái CPU (trị của các thanh ghi) ● Không gian địa chỉ (nội dung bộ nhớ) ● Môi trường (environment, xác định thông qua các bảng của hệ điều hành) 2 Khái niệm cơ bản (tt) Trạng thái CPU ● Processor Status Word (PSW) ● Instruction Register (IR) ● Program Counter (PC) ● Stack Pointer (SP) ● Các general purpose register Không gian địa chỉ ● Text (code) ● Data ● Heap ● Stack Môi trường ● Vd: terminal đang dùng, các open file, các kênh giao tiếp với các quá trình khác ● Được liệt kê trong các bảng của hệ điều hành 3 1
2. 10/01/2017 Process control block Hệ điều hành lưu thông tin về quá trình trong process control block (PCB) D.Feitelson 4 Các bước nạp chương trình vào bộ nhớ 5 Từ chương trình đến quá trình Chương trình thực thi có định dạng load module mà trình nạp (loader) “hiểu” được ● Vd định dạng elf trong Linux Layout luận lý của process image Executable binary file Process image (load module) trong main memory start address program program code code data data heap stack 6 2
3. 10/01/2017 Khởi tạo quá trình Các bước hệ điều hành khởi tạo quá trình ● Cấp phát một định danh duy nhất (process number hay process identifier, pid) cho quá trình ● Cấp phát không gian nhớ để nạp quá trình ● Khởi tạo khối dữ liệu Process Control Block (PCB) cho quá 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, ) 7 Các trạng thái của quá trình (1/2) Các trạng thái của quá trình: ● new: quá trình vừa được tạo ● ready: quá trình đã có đủ tài nguyên, chỉ còn cần CPU ● running: các lệnh của quá trình đang được thực thi ● waiting: hay là blocked, quá trình đợi I/O hoàn tất, hay đợi tín hiệu ● terminated: quá trình đã kết thúc 8 Các trạng thái của quá trình (2/2) Chuyển đổi giữa các trạng thái của quá trình terminated new admit dispatch exit ready running interrupt I/O or event I/O or event completion wait waiting 9 3
4. 10/01/2017 Ví dụ về trạng thái quá trình Chuỗi trạng thái của quá /* test.c */ trình test như sau (trường int main(int argc, char argv) { hợp tốt nhất): printf(“Hello world\n"); ● new exit(0); } ● ready ● running Biên dịch chương trình trong Linux gcc test.c –o test ● waiting (do chờ I/O khi gọi printf) Thực thi chương trình test ● ready ./test ● running Trong hệ thống sẽ có một quá trình ● terminated test được tạo ra, thực thi và kết thúc. 10 Process Control Block Đã thấy là mỗi quá 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 PCB thành một linked list) Môi trường 11 Các trường tiêu biểu của PCB Tanenbaum 12 4
5. 10/01/2017 Chuyển ngữ cảnh (1/2) Làm thế nào để chia sẻ CPU giữa các quá trình? Ngữ cảnh (context) của một quá trình là tình trạng hoạt động của quá trình ● Trị của các thanh ghi, trị của program counter, bộ nhớ, Ngữ cảnh của quá trình được lưu trong PCB của nó Chuyển ngữ cảnh (context switch) là công việc ngưng quá trình đang thực thi và chạy một quá trình khác. Khi đó cần: ● lưu ngữ cảnh của quá trình vào PCB của nó ● nạp ngữ cảnh từ PCB của quá trình mới để quá trình mới thực thi 13 Chuyển ngữ cảnh (2/2) 14 Yêu cầu đối với hệ điều hành về quản lý quá trình Hỗ trợ sự thực thi luân phiên giữa nhiều quá trình ● Khi nào chọn và chọn quá trình nào để thực thi có thể tùy thuộc vào tiêu chí 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ý ● Vấn đề deadlock, trì hoãn vô hạn định, Cung cấp cơ chế hỗ trợ user tạo/kết thúc quá trình Cung cấp cơ chế đồng bộ và giao tiếp giữa các quá trình 15 5
6. 10/01/2017 Quản lý quá 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ụ? 16 Định thời quá trình Tại sao phải định thời? ● Multiprogramming  Có nhiều quá trình thực thi luân phiên nhau  Mục tiêu (ví dụ): cực đại hiệu suất sử dụng của CPU ● Time-sharing  User tương tác với quá trình  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) 17 Các hàng đợi định thời Job queue Ready queue Các device queue 18 6
7. 10/01/2017 Thêm medium-term scheduling Đôi khi hệ điều hành (như time-sharing system) có thêm medium-term scheduling Medium-term scheduler ● chuyển quá trình từ bộ nhớ sang đĩa (swap out) ● chuyển quá trình từ đĩa vào bộ nhớ (swap in) memory memory 19 Thêm medium-term scheduling Tùy theo chiến lược sử dụng bộ nhớ, medium-term scheduler có thể quyết định ● swap out quá trình chiếm khối lượng lớn bộ nhớ, hay có độ ưu tiên thấp ● swap in quá trình khi có đủ bộ nhớ 20 Các tác vụ đối với quá trình (1/4) Tạo quá trình mới ● Quá trình có thể tạo một quá 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  Quá trình được tạo là quá trình con của quá trình tạo (quá trình cha). Quan hệ cha-con định nghĩa một cây quá trình. 21 7
8. 10/01/2017 Cây quá trình trong Linux/Unix Ví dụ root pagedaemon swapper init bash bash bash gcc ls mkdir grep 22 Các tác vụ đối với quá trình (2/4) Tạo quá trình mới (tt) ● Chia sẻ tài nguyên của quá trình cha: các khả năng  Quá trình cha và con chia sẻ mọi tài nguyên  Quá trình con chia sẻ một phần tài nguyên của cha  Cha và con không chia sẻ tài nguyên ● Trình tự thực thi: hai khả năng  Quá trình cha và con thực thi đồng thời (concurrently)  Quá trình cha chạy khi quá trình con kết thúc ● Trong Unix, quá trình gọi fork sẽ được tạo một quá trình con  hoàn toàn giống nó vào thời điểm gọi cùng trạng thái CPU, không gian địa chỉ, môi trường  chỉ khác nhau ở process ID và trị trả về từ fork 23 Các tác vụ đối với quá trình (3/4) Tạo quá trình mới (tt) ● Không gian địa chỉ: tùy hệ điều hành  UNIX: Không gian địa chỉ của quá trình con được nhân bản từ không gian địa chỉ của cha vào thời điểm gọi  Windows: phức tạp hơn, Win32 API CreateProcess() cần hơn 10 tham số 24 8
9. 10/01/2017 Về quan hệ cha/con Ví dụ áp dụng fork trong UNIX/Linux ● Quá trình gọi fork() để tạo một quá trình con ● Quá trình con gọi exec() để nạp và thực thi một chương trình trong không gian nhớ của nó ● Quá trình cha làm việc khác hay gọi wait() để đợi con xong đồng bộ 25 Ví dụ tạo process với fork() #include #include int main (int argc, char *argv[]){ int return_code; /* create a new process */ return_code = fork(); if (return_code > 0){ printf(“This is parent process”); wait(NULL); exit(0); } else if (return_code == 0){ printf(“This is child process”); execlp(“/bin/ls”, “ls”, NULL); exit(1); } else { printf(“Fork error\n”); exit(1);} } 26 Các tác vụ đối với quá trình (4/4) Tạo quá trình mới Kết thúc quá trình ● Quá trình tự kết thúc  Quá trình kết thúc khi thực thi lệnh cuối và gọi system routine exit ● Quá trình kết thúc do quá trình khác (có đủ quyền, vd: quá trình cha của nó)  Gọi system routine abort với tham số là pid (process identifier) của quá 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 quá trình kết thúc (vùng nhớ, I/O buffer, ) 27 9
10. 10/01/2017 Cộng tác giữa các quá trình Các quá trình có thể cộng tác (cooperate) để hoàn thành công việc ● Vd Sensor data Sensor Sampler Process data buffer Shared memory Display 28 Cộng tác giữa các quá trình Thiết kế ứng dụng ● Phân chia một ứng dụng lớn thành các process cộng tác nhau kiến trúc client-server Áp dụng cộng tác giữa các quá trình để ● Bài toán producer-consumer ● Modul hóa ● Tăng tốc tính toán  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 Sự cộng tác giữa các quá trình đòi hỏi hệ điều hành cung cấp giải pháp đồng bộ hoạt động (chương 3) và giao tiếp cho các quá trình 29 Bài toán producer-consumer Bài toán tiêu biểu về sự cộng tác giữa các quá 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 dữ liệu được 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 dữ liệu khi buffer đầy 30 10
11. 10/01/2017 Interprocess communication (IPC) IPC là các kỹ thuật cung cấp bởi hệ điều hành nhằm giúp các quá trình giao tiếp với nhau ● Các quá trình có thể trên cùng máy hoặc khác máy Hai kỹ thuật IPC ● Truyền thông điệp (message passing) ● Dùng bộ nhớ chia sẻ (shared memory) 31 Mô hình giao tiếp Truyền thơng điệp Dùng bộ nhớ chia sẻ 3.4 Fig 3.12 Truyền thông điệp Các vấn đề ● Naming  Giao tiếp trực tiếp – send(P, msg): gửi thông điệp đến quá trình P – receive(Q, msg): nhận thông điệp đến từ quá 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/nonblocking send  blocking/nonblocking receive 33 11
12. 10/01/2017 Example of shared memory for IPC POSIX Shared Memory ● Process first creates shared memory segment segment_id = shmget(IPC_PRIVATE, size, S_IRUSR | S_IWUSR); ● Process wanting access to that shared memory must attach to it shared_memory = (char *) shmat(id, NULL, 0); ● Now the process could write to the shared memory sprintf(shared_memory, "Writing to shared memory"); ● When done a process can detach the shared memory from its address space shmdt(shared_memory); 34 Giao tiếp trong hệ thống client-server Socket Remote Procedure Calls (RPC) Remote Method Invocation (RMI) 35 Socket Socket ● Đầu cuối của một kênh giao tiếp, gồm địa chỉ IP và port number ● Vd socket 161.25.19.8:1625 dùng để tham chiếu port 1625 trên máy có địa chỉ IP 161.25.19.8 36 12
13. 10/01/2017 Socket ● (tt) ‘well-known’ port xác định các dịch vụ chuẩn ● Cung cấp cơ chế giao tiếp mức thấp: gửi nhận một chuỗi byte dữ liệu không cấu trúc ● Hai loại giao tiếp qua socket: connectionless và connection- oriented 37 Gửi/nhận qua socket Hàm thư viện Diễn giải socket() Tạo một socket bind() Gán một địa chỉ cục bộ vào socket listen() Thiết lập độ dài queue accept() (server) Chờ kết nối đến từ client connect() (client) kết nối đến một server send() Gửi dữ liệu qua kênh giao tiếp đã thiết lập sendto() Gửi dữ liệu đến một địa chỉ recv() Nhận dữ liệu qua kênh giao tiếp đã thiết lập recvfrom() Nhận dữ liệu đến từ một địa chỉ close() Đóng kết nối 38 Connectionless Transport Service Process A Process B socket() socket() bind() bind() sendto()/ sendto()/ recvfrom() recvfrom() close() close() sendto(socket, buffer, buffer_length, flags, destination_address, addr_len) recvfrom(socket, buffer, buffer_length, flags, from_address, addr_len) 39 13
14. 10/01/2017 Connection-Oriented Transport Service Server (Google) socket() bind() listen() accept() recv() send() close() communication socket() connect() send() recv() close() Client (Firefox) send(socket, buffer, buffer_length, flags) recv(socket, buffer, buffer_length, flags) 40 Remote procedure call Remote procedure call (RPC) ● Cho phép một chương trình gọi một thủ tục nằm trên máy tính ở xa qua mạng Các vấn đề khi hiện thực RPC ● Truyền tham số và kết quả trả về của lời gọi thủ tục ● Chuyển đổi dữ liệu khi truyền trên mạng (data conversion) ● Kết nối client đến server ● Biên dịch chương trình ● Kiểm soát lỗi ● Bảo mật 41 Remote Procedure Call RPC, cho phép một quá trình gọi một thủ tục có thể ở trên một máy khác g D.Feitelson 42 14
15. 10/01/2017 Sơ đồ hoạt động của RPC chờ kết quả trả về (suspended) Client Gọi remote procedure Kết quả trả về Request Reply Server (blocked) Gọi thủ tục cục bộ (blocked) và trả về kết quả t 43 Lưu đồ thực hiện RPC Client Server return reply call request call request return reply Client Stub Server Stub message to parameter message to parameter parameter to message parameter to message TRANSPORT TRANSPORT (OS 1) (OS 2) receive send receive send network 44 Truyền tham số trong RPC (1/2) Marshalling ● qui tắc truyền tham số và chuyển đổi dữ liệu trong RPC bao gồm cả đóng gói dữ liệu thành dạng thức có thể truyền qua mạng máy tính Biểu diễn dữ liệu và kiểm tra kiểu dữ liệu ● Dữ liệu được biểu diễn khác nhau trên các hệ thống khác nhau  ASCII, EBCDIC  Ví dụ biểu diễn 32-bit integer trong máy: – big-endian most significant byte tại high memory address (Motorola) – little-endian least significant byte tại high memory address (Intel x86)  Dạng biểu diễn XDR (External Data Representation): biểu diễn dữ liệu machine-independent 45 15
16. 10/01/2017 Truyền tham số trong RPC (2/2) 46 Thực hiện RPC với dynamic binding Dynamic binding: truy vấn Matchmaker để xác định port number của RPC X 47 Remote method invocation Remote Method Invocation (RMI) ● Cho phép một chương trình Java có thể gọi một phương thức (method) của một đối tượng ở xa, nghĩa là một đối tượng ở tại một máy ảo Java khác 48 16
17. 10/01/2017 Marshalling tham số trong RMI marshalling unmarshalling Phương thức được triệu gọi có dạng sau: boolean someMethod(Object x, Object y) 49 17