Bài giảng Hệ điều hành - Chương III: Tiến trình và luồng - Hà Duy An

Khoa Công Nghệ Thông Tin & Truyền Thông Đại học Cần Thơ Giảng viên: Hà Duy An 1. Các khái niệm 2. Định thời biểu tiến trình 3. Các thao tác với tiến trình 4. Giao tiếp giữa các tiến trình 8/22/2013 Chương 3: Tiến Trình3 • Hệ điều hành có thể thực thi nhiều dạng chương trình: o Hệ thống bó (batch system) – jobs o Hệ thống chia thời gian – chương trình người dùng (user program) hay tác vụ (task) • Tiến trình - là một chương trình đang thực thi. Sự thực thi của tiến trình diễn ra theo cách thức tuần tự. • Một tiến trình bao gồm: o Mã chương chương trình (program code hay text section) o Bộ đếm chương trình (program counter) o Ngăn xếp (stack) – chứa các dữ liệu tạm thời • Các tham số của hàm, địa chỉ trở về, biến cục bộ o Phần dữ liệu (data section) - chứa các biến toàn cục o Heap – bộ nhớ động, được cấp phát trong suốt thời gian thực thi 8/22/2013 Chương 3: Tiến Trình5 • Chương trình là một thực thể bị động lưu trữ trên đĩa, tiến trình là thực thể chủ động o Chương trình trở thành tiến trình nó được nạp vào trong bộ nhớ để thực thi o Chương trình có thể được kích hoạt qua thao tác nhấp chuột, nhập tên vào CLI, o Một chương trình có thể có vài tiến trình 8/22/2013 Chương 3: Tiến Trình6 • Tiến trình có thể có các trạng thái sau: o new: quá trình đang được khởi tạo. o running: các chỉ thị của quá trình đang được thực thi. o waiting: quá trình đang chờ đợi một sự kiện nào đó xảy ra (hoàn thành xuất/nhập, chờ đợi một tín hiệu). o ready: quá trình đang đợi để được sử dụng CPU. o terminated: quá trình đã kết thúc. 8/22/2013 Chương 3: Tiến Trình7 8/22/2013 Chương 3: Tiến Trình8 • Thông tin kết hợp với mỗi quá trình: o Trạng thái của quá trình o Bộ đếm chương trình o Các thanh ghi o Thông tin về định thời sử dụng CPU o Thông tin về quản lý bộ nhớ o Thông tin về chi phí o Thông tin về trạng thái nhập/xuất 8/22/2013 Chương 3: Tiến Trình9 8/22/2013 Chương 3: Tiến Trình10 • Nhằm tối ưu hóa việc sử dụng CPU, các tiến thay phiên nhau sử dụng CPU • Bộ định thời tiến trình (Process scheduler) chọn lựa một tiến trình có thể thực thi để cấp phát CPU cho tiến trình đó • Các hàng đợi định thời: o Hàng đợi công việc (Job queue): tập hợp tất cả các quá trình trong hệ thống. o Hàng đợi sẵn sàng (Readyqueue): tập hợp tất cả các quá trình đang nằm trong bộ nhớ, sẵn sàng và đang chờ để thực thi. o Hàng đợi thiết bị (Device queue): tập hợp các quá trình đang đợi sử dụng một thiết bị xuất/nhập. • Quá trình có thể di chuyển giữa các hàng đợi khác nhau 8/22/2013 Chương 3: Tiến Trình12 8/22/2013 Chương 3: Tiến Trình13 8/22/2013 Chương 3: Tiến Trình14 • Bộ định thời dài kỳ (Long-term scheduler/job scheduler) – chọn quá trình nào sẽ được đặt vào hàng đợi sẵn sàng (nạp vào bộ nhớ). • Bộ định thời ngắn kỳ (Short-term scheduler/CPU scheduler) –chọn ra quá trình sẽ được thực thi kế tiếp và cấp CPU cho nó. • Bộ định thời ngắn kỳ được gọi rất thường xuyên (milliseconds) => cần phải nhanh • Bộ định thời dài kỳ được gọi không thường xuyên hơn (seconds, minutes) => có thể chậm • Bộ định thời dài kỳ khống chế mức độ đa chương của hệ thống • Các tiến trình có thể là: o Tiến trình hướng xử lý: cần nhiều tính toán hơn nhập xuất o Tiến trình hướng nhập xuất: cần nhiều nhập xuất hơn tính toán • Bộ định thời dài kỳ cố gắng điều hòa giữa các tiến trình này 8/22/2013 Chương 3: Tiến Trình15 • Bộ định thời trung kỳ (Medium-term scheduling) – làm giảm mức độ đa chương của hệ thống o Di chuyển các tiến tình ra khỏi bộ nhớ, lưu trữ trên đĩa, sau đó mang vào bộ nhớ để tiếp tục thực thi: swapping 8/22/2013 Chương 3: Tiến Trình16 • Chuyển ngữ cảnh (context switch): Khi CPU chuyển sang phục vụ tiến trình khác, hệ thống phải ghi lại trạng thái của tiến trình cũ và nạp trạng thái được lưu trước đó của tiến trình mới • “Ngữ cảnh” của một tiến trình được xác định thông qua các thông tin trong PCB • Thời gian chuyển ngữ cảnh là một phí tổn, vì hệ thống không làm gì hữu ích khi thực hiện chuyển ngữ cảnh o HĐH và PCB càng phức tạp => thời gian chuyển ngũ cảnh càng dài • Thời gian chuyển ngữ cảnh phụ thuộc nhiều vào sự hỗ trợ của phần cứng o Vài hệ thống cung cấp nhiều tổ hợp các thanh ghi trên mỗi CPU=> nhiều “ngữ cảnh” được nạp vào cùng lúc 8/22/2013 Chương 3: Tiến Trình17 • Quá trình cha tạo ra quá trình con, đến lượt quá trình con này lại tạo ra những quá trình khác, tạo nên cây quá trình. • Thông thường các tiến trình được xác định và quản lý thông qua PID (Process identifier) • Chia sẻ tài nguyên – có nhiều lựa chọn: o Quá trình cha và con chia sẻ tất cả tài nguyên. o Quá trình con chia sẻ một phần tài nguyên của quá trình cha. o Quá trình cha và con không chia sẻ tài nguyên nào cả. • Thực thi: o Quá trình cha và con thực thi đồng thời. o Quá trình cha đợi đến khi quá trình con hoàn thành. 8/22/2013 Chương 3: Tiến Trình19 8/22/2013 Chương 3: Tiến Trình20 init pid = 1 sshd pid = 3028 login pid = 8415 kthreaddpid = 2 sshd pid = 3610 pdflush pid = 200 khelper pid = 6 tcsch pid = 4005emacspid = 9204 bash pid = 8416 ps pid = 9298 • Không gian địa chỉ: o Quá trình con sao chép không gian địa chỉ của quá trình cha (cùng chương trình và dữ liệu). o Quá trình con tự nạp chương trình riêng của nó. • Hệ thống UNIX o fork() –là lời gọi hệ thống dùng tạo quá trình mới o exec() –là lời gọi hệ thống được sử dụng sau fork() để thay thế không gian địa chỉ của quá trình bằng một chương trình mới 8/22/2013 Chương 3: Tiến Trình21 8/22/2013 Chương 3: Tiến Trình22 8/22/2013 Chương 3: Tiến Trình23 • Quá trình thực hiện câu lệnh cuối cùng và yêu cầu HĐH xóa nó (dùng exit). o Xuất dữ liệu từ quá trình con lên quá trình cha (wait()). pid_t pid; int status; pid=wait(&status); o Tài nguyên của quá trình bị thu hồi lại bởi hệ điều hành. • Quá trình cha có thể kết thúc sự thực thi của quá trình con (abort()). o Quá trình con đã vượt quá số tài nguyên được cấp. o Công việc giao cho quá trình con nay không còn cần thiết nữa. o Quá trình cha đang thoát. • Vài hệ điều hành không cho phép quá trình con tiếp tục thực thi khi quá trình cha kết thúc => Sự kết thúc hàng loạt các quá trình con (cascading termination) • Nếu tiến trình cha chưa gọi wait() => tiến trình con vừa kết thúc trở thành một zombie • Nếu tiến trình cha kết thúc trước => tiến trình con mồ coi (orphan) 8/22/2013 Chương 3: Tiến Trình24 • Nếu các trình duyệt web thực thi dạng đơn tiến trình => nếu một web site bị lỗi, toàn bộ trình duyệt bị treo hay đổ vỡ • Google Chrome Brower thực thi dạng đa tiến trình, phân ra làm 3 nhóm: o Browser: tiến trình quản lý giao diện người dùng, xuât/nhập đĩa và mạng o Renderer: xử lý hiển thị các trang web (HTML, JavaScript, ) mỗi tiến trình cho một trang web o Plug-in: một tiến trình cho mỗi loại plug-in 8/22/2013 Chương 3: Tiến Trình26 • Các tiến trình trong hệ thống có thể độc lập hay hợp tác • Tiến trình độc lập không thể gây ảnh hưởng hay bị ảnh hưởng bởi các tiến trình khác • Tiến trình hợp tác có thể gây ảnh hưởng hay bị ảnh hưởng bởi các tiến trình khác • Mục đích hợp tác giữa các tiến trình: o Chia sẽ thông tin o Tăng tốc độ tính toán o Module hóa o Tiện lợi • Tiến trình hợp tác cần trao đổi thông tin với nhau (IPC- Interprocess communication) • 2 mô hình IPC: o Shared memory o Message passing 8/22/2013 Chương 3: Tiến Trình27 8/22/2013 Chương 3: Tiến Trình28 • Bài toán điển hình minh họa cho sự hợp tác giữa các tiến trình – tiến trình Nhà sản xuất sinh ra dữ liệu được sử dụng bởi tiến trình Người tiêu thụ • Giải quyết bài toán với cơ chế bộ nhớ chia sẽ - 2 tiến trình sử dụng một vùng nhớ dùng chung (buffer), tiến trình Người sản xuất ghi dữ liệu lên buffer, tiến trình Người tiêu thụ lấy dữ liệu từ buffer • 2 loại buffer: o unbounded-buffer: kích thước không giới hạn o bounded-buffer: kích thước giới hạn 8/22/2013 Chương 3: Tiến Trình29 • Dữ liệu chia sẽ: #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; 8/22/2013 Chương 3: Tiến Trình30 item next_produced; while (true) { /* produce an item in next produced */ while (((in + 1) % BUFFER_SIZE) == out) ; /* do nothing */ buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; } 8/22/2013 Chương 3: Tiến Trình31 item next_consumed; while(true){ while(in == out); /* do nothing */ next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; /* consume the item in next consumed */ } 8/22/2013 Chương 3: Tiến Trình32 • Cung cấp cơ chế giao tiếp giữa các tiến trình không cần dụng bộ nhớ chia sẽ => hữu ích trong môi trường phân tán, các tiến trình giao tiếp với nhau qua mạng • Cần hai thao tác: o send(message) – kích thước thông điệp cố định hay biến đổi o receive(message) • Tiến trình P và Q nếu muốn giao tiếp với nhau: o Tạo một communication link o Trao đổi thông điệp thông qua send/receive • Phương thức cài đặt communication link (mức luận lý): o Trực tiếp - gián tiếp o Đồng bộ - bất đồng bộ o Kiểu Buffer 8/22/2013 Chương 3: Tiến Trình33 • Tạo communication link như thế nào? • Có thể dùng một communication link cho nhiều tiến trình? • Có bao nhiêu liên kết có thể tạo giữa hai tiến trình? • Khả năng của một liên kết? • Kích thước của thông điệp cố định hay thay đổi? • Liên kết là một hướng hay 2 hướng? 8/22/2013 Chương 3: Tiến Trình34 • Các tiến trình phải xác định rõ ràng tên của tiến trình nhận hay gửi dữ liệu khác o send(P, message) – gửi một thông điệp đến tiến trình P o receive(Q, message)– nhận một thông điệp từ tiến trình Q • Các thuộc tính của communication link: o Các liên kết được tạo ra tự động o Một liên kết tương ứng chỉ có 2 tiến trình thực hiện giao tiếp trên nó o Giữa mỗi cặp tiến trình chỉ tồn tại duy nhất một liên kết o Liên kết có thể là một hướng, nhưng thường là hai hướng. 8/22/2013 Chương 3: Tiến Trình35 • Các thông điệp gửi đến và nhận từ các mailbox hay port o Mỗi mailbox có một số nhận dạng duy nhất o Các tiến trình có thể giao tiếp với nhau khi chúng chia sẽ cùng một mailbox • Các thuộc tính của communication link: o Liên kết được tạo ra khi các tiến trình chia sẽ cùng một mailbox o Một liên kết có thể liên kết với nhiều tiến trình o Mỗi cặp tiến trình có thể cùng chia sẽ vài cummunication link o Liên kết có thể một hay hai hướng 8/22/2013 Chương 3: Tiến Trình36 • HĐH cung cấp cơ chế: o Tạo một mailbox o Gửi và nhận thông điệp thông qua mailbox o Hủy một mailbox • Phương thức gửi và nhận một thông điệp: o send(A, message) – gửi một thông điệp đến mailbox A o receive(A, message) – nhận một thông điệp từ mailbox A 8/22/2013 Chương 3: Tiến Trình37 • Chia sẽ mailbox: o P1, P2, và P3 chia sẽ cùng một mailbox A o P1 gửi; P2 hay P3 nhận??? • Giải pháp: o Một liên kết chỉ tương ứng với 2 tiến trình o Chỉ một tiến trình tại một thời điểm thực hiện thao tác nhận o HĐH chỉ định tiến trình nhận, và thông báo cho tiến trình gửi biết người nhận 8/22/2013 Chương 3: Tiến Trình38 • Truyền thông điệp có thể nghẽn (blocking) hay không nghẽn (non-blocking) • Blocking – đồng bộ (synchronous) o Blocking send: tiến trình gửi chờ cho đến khi thông điệp được nhận o Blocking receive : tiến trình nhận chờ cho đến khi thông điệp sẳn sàng • Non-blocking – bất đồng bộ (asynchronous) o Non-blocking send: gửi thông điệp và tiếp tục thực hiện công việc khác o Non-blocking receive: nhận một thông điệp hay null 8/22/2013 Chương 3: Tiến Trình39 • Các thông điệp nằm trong hàng đợi tạm thời (buffer), 3 cách cài đặt: o Zero capacity – không có thông điệp nào nằm trong hàng đợi (sender chờ cho đến khi thông điệp được nhận) o Bounded capacity – kích thước buffer là giới hạn (sender phải chờ khi buffer đầy) o Unbounded capacity – kích thước buffer không giới hạn 8/22/2013 Chương 3: Tiến Trình40 8/22/2013 Chương 3: Tiến Trình41 1. Giới thiệu về Luồng (Thread) 2. Lập trình trên vi xử lý đa nhân 3. Mô hình đa luồng 8/22/2013 Chương 3: Tiến Trình42 8/22/2013 Chương 3: Tiến Trình43 • Hầu hết các chương trình ứng dụng hiện đại là đa luồng (Multithread) • Một ứng dụng có nhiều tác vụ => mỗi tác vụ được cài đặt như một luồng: o Cập nhật hiển thị o Lấy dữ liệu o Kiểm tra chính tả o Trả lời các kết nối mạng,. • Tạo một tiến trình cần nhiều chi phí hơn tạo ra một luồng • Việc lập trình đơn giản hơn, hiệu quả hơn • Nhân của nhiều HĐH ngày nay là đa luồng 8/22/2013 Chương 3: Tiến Trình44 8/22/2013 Chương 3: Tiến Trình45 8/22/2013 Chương 3: Tiến Trình46 • Tăng khả năng đáp ứng • Chia sẽ tài nguyên dễ dàng • Ít hao tốn tài nguyên hệ thống hơn • Tận dụng được khả năng trên các hệ thống có nhiều bộ xử lý 8/22/2013 Chương 3: Tiến Trình47 8/22/2013 Chương 3: Tiến Trình48 • Các hệ thống Multicore hay Multiprocessor giúp tăng năng lực xử lý cho hệ thống, đồng thời phát sinh ra nhiều vấn đề trong việc thiết kế và phát triển chương trình: o Phân chia tác vụ o Cân bằng o Phân chia và chia sẽ dữ liệu o Kiểm lỗi • Song song (Parallelism) khác với đồng thời (Concurrency) • Hai kiểu song song: o Dữ liệu – phân phối dữ liệu cùng kiểu, tác vụ xử lý giống nhau o Tác vụ - tác vụ xử lý khác nhau, dữ liệu có thể giống hoặc khác nhau 8/22/2013 Chương 3: Tiến Trình49 • Xử lý đồng thời trên hệ thống đơn nhân: • Xử lý song song trên hệ thống đa nhân: 8/22/2013 Chương 3: Tiến Trình50 8/22/2013 Chương 3: Tiến Trình51 • User threads – cài đặt luồng ở mức người dùng • Kernel threads – được hỗ trợ bởi nhân (kernel) • Hầu như tất cả các hệ điều hành đa mục đích hiện nay điều hỗ trợ kernel threads (Windows, Linux, MacOS X, and Solaris) • Liên hệ giữa User threads và kernel threads: o Many to One o One to One o Many to Many 8/22/2013 Chương 3: Tiến Trình52 • Nhiều user thread – một kernel thread • Vấn đề: o Một luồng nghẽn => toàn tiến trình nghẽn 8/22/2013 Chương 3: Tiến Trình53 o Chỉ một luồng có thể chạy ở mức nhân tại một thời điểm nhất định => không hiệu quả trên hệ thống multicore o Rất ít hệ thống dùng mô hình này • Mỗi user thread – một kernel thread • Hiệu quả hơn trên hệ thống multicore • Vấn đề: o Số lượng luồng trên mỗi tiến trình cần giới hạn vì chi phí tạo kernel thread đắt hơn user thread • Các hệ thống dùng mô hình này: Windows NT/XP/2000, Linux, solaris 9. 8/22/2013 Chương 3: Tiến Trình54 • Nhiều user thread - số lượng kernel thread bằng hay ít hơn • HĐH tạo môt số lượng kernel thread đủ dùng 8/22/2013 Chương 3: Tiến Trình55 • Thread library cung cấp API cho lập trình viên tạo và quản lý luồng • Có 2 cách cài đặt: o Mức người dùng o Mức nhân – được hỗ trợ bởi HĐH • Các thread library được dùng phổ biến: POSIX Pthreads, Windows, Java 8/22/2013 Chương 3: Tiến Trình56