PROCESS VÀ ĐỒNG BỘ CÁC PROCESS
I. PROCESS VÀ CÁC KHÁI NIỆM LIÊN QUAN
1) Khái niệm process:
Một process là một chương trình đang được thực hiện. Nó đang được thể hiện bởi giá trị chứa trong bộ đếm chương trình (program counter) và giá trị chứa trong các thanh ghi (registers) của CPU. Một process có stack để chứa các dữ liệu tạm thời như: các tham số của các thủ tục con (subroutine), các giá trị tạm thời, các giá trị trả về. Có phần dữ liệu (data section) để chứa các biến toàn cục (global variables), biến cục bộ (local variable)… Còn đoạn mã của nó thì đang được nạp trong bộ nhớ thực và đang được CPU thực hiện từng lệnh . Có danh sách các tài nguyên cần thiết cho hoạt động sống của process.
Một chương trình không phải là một process. Một chương trình là một thực thể thụ động được chứa trong file trên đĩa. Chương trình chỉ trở thành process khi nó được hệ điều hành nạp vào bộ nhớ và được CPU thực hiện. Còn process là một thực thể hoạt động, nó được thanh ghi PC (hay còn gọi là bộ đếm chương trình - program counter) cho biết chỉ thị tiếp theo mà CPU phải thực hiện.
Nhiều process có thể là sự thực thi từ cùng một chương trình. Chẳng hạn, nhiều users có thể cùng gọi để thực thi một chương trình soạn thảo văn bản. Khi đó mỗi sự thực thi như vậy là một process riêng biệt.
2) Các trạng thái của process:
Trong quá trình sống của process, nó có sự thay đổi trạng thái (state).
Trạng thái của một process tại một thời điểm được xác định bởi hoạt động hiện thời của process tại thời điểm đó.
Tại một thời điểm, một process có thể ở một trong các trạng thái sau đây:
- New: process vừa được tạo ra.
- Ready: sẵn sàng thực hiện nếu được phép (nghĩa là process đang chờ được cấp phát CPU để thực thi).
- Running: process đang sử dụng CPU, nó đang chạy
- Blocked: process đang bị chặn do chờ một biến cố nào đó hay do chờ cấp phát tài nguyên.
- Terminated: process hoàn tất, nó kết thúc thực thi.
Chú ý: Tại một thời điểm, trên một CPU chỉ có một process ở trạng thái running trên một bộ xử lý bất kỳ. Trong khi đó, nhiều process khác có thể ở trạng thái ready hay blocked trên CPU đó.
Giải thích các đường chuyển tiếp trong sơ đồ 3 trạng thái như sau:
(1) process vừa mới tạo được đưa vào hệ thống.
(2) Hệ thống cấp phát cho process một khoảng thời gian sử dụng CPU.
(3) Process keát thuùc.
(4) Process yêu cầu một tài nguyên nhưng chưa được đáp ứng vì tài nguyên chưa sẵn sàng để cấp phát tại thời điểm đó, hoặc process đang chờ một sự kiện hay đang chờ một thao tác nhập xuất.
(5) Process phải trả CPU lại cho hệ thống để trở về trạng thái sẵn sàng, lúc này hệ thống chọn một process khác để cho thực thi.
(6) Process đã sử dụng tài nguyên mà nó chờ, sự kiện mà process chờ đã xảy ra, thao tác nhập xuất mà process đợi đã hoàn tất.
Blocked
Terminated
Running New
Ready
1 5 3
2
4 6
3) Khối quản lý process:
Hệ điều hành quản lý các process thông qua các khối quản lý process (PCB -Process Control Block). PCB được lưu trong vùng nhớ, nó chứa các thông tin mô tả hoạt động của process. Các thông tin chủ yếu bao gồm:
Định danh của process: giúp phân biệt các process với nhau.
Trạng thái của process: xác định các hoạt động hiện hành của process.
Ngữ cảnh của process: bao gồm các mô tả về các tài nguyên mà process đang dùng, đã dùng hoặc sẽ dùng trong quá trình hoạt động của process.
Bao goàm:
- Trạng thái CPU: nội dung của thanh ghi PC, thanhh ghi IP, nội dung của các thanh ghi khác phải được lưu giữ. Các thông tin này đặc biệt quan trọng nhất là khi process bị ngắt, nhờ các thông tin này mà nó có thể phục hồi trở lại đúng ngay tại lệnh tiếp theo sau lệnh mà trước khi nó bị ngắt.
- Bộ xử lý: dùng cho máy có cấu hình nhiều CPU. Thông tin này xác định số hiệu CPU mà process đang sử dụng.
- Bộ nhớ chính: danh sách các khối nhớ được cấp phát cho process.
- Tài nguyên đang sử dụng: danh sách các tài nguyên hệ thống mà process đang sử dụng.
- Tài nguyên tạo lập: danh sách các tài nguyên mà process đang tạo lập.
Thông tin giao tiếp: phản ánh các thông tin về quan hệ của process với các process trong hệ thống. Bao gồm:
- Process cha: cho biếtt process nào tạo lập ra process này.
- Process con: các process con được tạo ra từ process này.
- Độ ưu tiên: giúp cho hệ điều hành có thông tin trong việc lựa chọn process được cấp CPU.
Thông tin thống kê: đây là những thông tin thống kê về hoạt động của process như thời gian đã sử dụng CPU, thời gian chờ. Các thông tin này có ích cho việc đánh giá tình hình hệ thống và dự đoán các tình huống tương lai.
4) Thao tác trên process:
Hệ điều hành cung cấp các thao tác chủ yếu sau đây trên các process:
- tạo process (create).
- keát thuùc process (destroy).
- đình hoãn process (suspend).
- tái kích hoạt process (resume).
- Thay đổi độ ưu tiên (priority).
⌦ Tạo lập process:
Trong quá trình xử lý, một process có thể tạo một process mới bằng cách gọi một lời gọi hệ thống tương ứng để tảo ra process con. Các process con đến lượt nó lại có thể tạo các process mới. Các công việc mà hệ điều hành cần phải thực hiện khi tạo một process mới là:
- Định danh cho process mới phát sinh.
- Đưa process mới vào danh sách quản lý của hệ thống.
- Xác lập độ ưu tiên cho process.
- Tạo PCB (khối quản lý tiến trình) cho process.
- Cấp phát tài nguyên ban đầu cho process.
Khi một process tạo một process mới, process con có thể được hệ điều hành trực tiếp cấp phát tài nguyên hoặc được process cha cho thừa hưởng một số tài nguyên ban đầu.
Khi một process tạo một process mới, process ban đầu có thể xử lý theo một trong hai khả năng sau đây:
- Process cha có thể xử lý đồng hành với process con.
- Process cha chờ đến khi một process con nào đó, hoặc tất cả các process con keát thuùc.
⌦ Keát thuùc process:
Một process kết thúc xử lý của nó khi nó hoàn tất chỉ thị cuối cùng và gọi một lời gọi hệ thống để yêu cầu hủy bỏ nó. Đôi khi process cũng có thể yêu cầu hệ điều hành kết thúc xử lý một process khác. Hoặc hệ thống có thể kết thúc một process đang thực thi. Khi một process kết thúc, hệ điều hành thực hiện các coõng vieọc sau:
- Thu hồi các tài nguyên đã cấp phát cho process.
- Hủy process khỏi danh sách quản lý của hệ thống.
- Huûy PCB cuûa process.
Hầu hết các hệ điều hành không cho phép các process con tồn tại khi nó kết thúc process cha. Lúc đó hệ điều hành phải thực hiện một loạt các thao tác kết thúc các process con.
⌦ Đình hoãn và tái kích hoạt process:
Một process có thể bị đình hoãn do vài nguyên nhân sau đây: Hệ thống xử lý yếu, có lỗi, lúc đó process phải bị đình hoãn và sẽ được phục hồi sau khi sữa được lỗi. Người dùng nghi ngờ kết quả xử lý nên đình hoãn process cho tới khi biết chắc dược kết quả là đúng hay sai. Tải (load) của hệ thống bị dao động, vài process bị đình hoãn và sẽ được phục hồi vấn đề tải được giải quyết.
Do đó để giảm không gian bộ nhớ bị chiếm dụng bởi các process, người ta có ý tưởng đưa các process không thực hiện ra ngoài bộ nhớ phụ. Đưa một process ra ngoài bộ nhớ phụ nghĩa là đưa toàn bộ thông tin hiện hành của process ra bộ nhớ phụ. Khi nào cần thiết thì sử dụng lại các thông tin đó để phục hồi (resume) process hoạt động trở lại.
⌦ Độ ưu tiên của các process:
Độ ưu tiên (priority) của một process là một giá trị giúp phân định tầm quan trọng của một process trong hệ thống. Nó có thể phát sinh một cách tự động bởi hệ thống hoặc được gán tường minh bởi người dùng
- Độ ưu tiên tĩnh: là độ ưu tiên được gán sẵn cho process, nó không thay đổi. Cơ chế của độ ưu tiên tĩnh thì dễ thực hiện nhưng đôi khi không hợp lý vì môi trường của hệ thống thường có sự thay đổi.
- Độ ưu tiên động: là độ ưu tiên thay đổi theo thời gian và theo môi trường xử lý của process. Process được khởi động với một độ ưu tiên ban đầu, sau đó hệ thống có thể sửa đổi giá trị độ ưu tiên của process trong từng giai đoạn thực hiện của process sao cho phù hợp với tình hình cuỷa heọ thoỏng.
5) Khái niệm thread:
a) Chuyển ngữ cảnh (context switch):
Ngữ cảnh (context) của một process bao gồm các tài nguyên mà process đang dùng. Chẳng hạn muốn chuyển quyền sử dụng CPU đến một process khác thì phải lưu lại trạng thái của process cũ và nạp lại trạng thái đã lưu của process mới, các tài nguyên khác cũng vậy. Thao tác này gọi là chuyển ngữ cảnh. Chi phí chuyển đổi ngữ cảnh thì tốn.
b) Thread (tieồu trỡnh):
Trong hệ thống việc chuyển ngữ cảnh giữa các process là tốn kém. Do trong hầu hết các hệ điều hành, mỗi process có một không gian địa chỉ và một dòng xử lý riêng cùng với các tài nguyên liên quan.
Thread là một phần công việc trong một process, một process gồm một hay nhiều thread. Các thread trong cùng một process có thể được xử lý lần lượt hay đồng thời và cùng chia sẻ không gian địa chỉ, các tài nguyên của process
chứa chúng. Mỗi thread cũng có một đoạn mã riêng, con trỏ lệnh riêng, tập các thanh ghi và vùng stack riêng.
Ưu điểm của thread trong một process là chúng cùng hoạt động trong một môi trường ngữ cảnh nên việc chuyển đổi qua lại giữa chúng là dễ dàng, làm giảm chi phí chuyển đổi ngữ cảnh.
6) Cấp phát tài nguyên cho process:
Khi có nhiều process cùng thực hiện đồng thời trong hệ thống, hệ điều hành phải cấp phát tài nguyên cho các process. Do các tài nguyên trong hệ thống thường rất giới hạn và không thể chia sẻ, nên hiếm khi thỏa mãn được các yêu cầu tài nguyên một cách triệt để. Vì vậy cần có một chiến lược cấp phát, chia sẻ tài nguyên cho các process một cách có hiệu quả, hạn chế tối đa sự tranh chấp tài nguyên giữa các process làm tê liệt hệ thống.
Hệ điều hành quản lý nhiều loại tài nguyên khác nhau. Mỗi loại tài nguyên có các đặc điểm khác nhau. Mỗi loại tài nguyên được hệ điều hành quản lý thông qua các cấu trúc dữ liệu của tài nguyên.
Thông tin cơ bản trong cấu trúc dữ liệu tài nguyên gồm:
- Định danh tài nguyên.
- Trạng thái tài nguyên; phần nào của tài nguyên đã được cấp phát và cấp phát cho process nào. Phần nào còn có thể sử dụng được.
- Hàng đợi trên tài nguyên: là danh sách có thứ tự các process đang chờ được sử dụng tài nguyên.
- Bộ cấp phát: thực chất là một đoạn code đảm nhiệm việc cấp phát tài nguyên. Các đoạn mã này là giải thuật cấp phát tài nguyên.
Các mục tiêu của kỹ thuật cấp phát:
- Bảo đảm được số lượng hợp lệ các process truy xuất đồng thời tài nguyên dạng không chia sẻ được (non-sharable).
- Cấp phát tài nguyên cho các process với thời gian trì hoãn (delay time) chấp nhận được.
- Tối ưu hóa sử dụng tài nguyên.
II. ẹIEÀU PHOÁI PROCESS:
1) Bài toán miền găng:
a) Vấn đề loại trừ tương hỗ (mutual exclusion):
Các tài nguyên trong hệ thống được phân chia thành 2 loại. Loại tài nguyên có thể chia sẻ (sharable) thì cho phép nhiều process đồng thời truy xuất.
Loại tài nguyên không thể chia sẻ (non-sharable) thì chỉ chấp nhận một hoặc vài process sử dụng tại một thời điểm.
Nếu nhiều process muốn sử dụng đồng thời tài nguyên dạng không chia sẻ thì sẽ có nguy cơ tranh chấp gữa các process hoặc xảy ra các kết quả không dự đoán được do hoạt động của các process trên tài nguyên ảnh hưởng lẫn nhau.
Cho nên hệ thống phải kiểm soát sao cho tại một thời điểm chỉ có một (hoặc vài) process được quyền truy xuất tài nguyên dạng không chia sẻ.
b) Bài toán Miền Găng (critical section):
Tài nguyên gây tranh chấp giữa các process được gọi là critical resource.
Đoạn chương trình có chứa mã lệnh truy xuất critical resource được gọi là Miền Gaêng (critical section).
Nguyên lý: khi có một process vào critical section thì các process khác không được vào critical setion.
Khi chuẩn bị vào critical section thì phải kiểm tra hay xin phép. Khi ra khỏi thì phải thông báo. (Giống như phất cờ hiệu vậy)
c) Giải quyết vấn đề:
Có các cách giải quyết cho vấn đề bài toán Miền Găng như sau:
- Giải pháp phần mềm: giải thuật Dekker, Peterson.
- Giải pháp phần cứng: có hỗ trợ về phần cứng.
- Giải pháp của hệ điều hành và ngôn ngữ lập trình: dùng semaphore.
Một phương pháp tốt giải quyết bài toán Miền Găng cần phải thỏa các ủieàu kieọn sau:
- Chỉ có một process được vào critical section.
- Mọi process tạm dừng bên ngoài critical section phải không ảnh hưởng đến các process khác đi vào critical section.
- Không được cho một process có yêu cầu critical section phải chờ vô hạn (không có deadlock-tắc nghẽn hay starvation-chờ vô hạn).
- Khi không có process nào ở trong critical section thì nếu có một process yêu cầu critical section thì nó phải được đáp ứng ngay lập tức.
- Một process chỉ có thể ở trong critical section với thời gian hữu hạn.
- Không được quy định gì về tốc độ thực hiện.
Một ví dụ về giải thuật loại trừ tương hỗ bằng phương pháp sử dụng cờ hiệu:
Dùng một biến chung gọi là lock như một ống khóa cửa cho critical resource. Biến này được khởi động bằng 0. Một process muốn vào critical section thì phải kiểm tra giá trị của biến lock. Nếu:
lock=0 thì process đặt lại lock=1 rồi đi vào critical resource.
lock=1 thì process phải chờ bên ngoài critical section cho đến khi nào lock=0.
…
while(lock=1) do-nothing;
lock=1;
critical-section();
lock=0;
non-critical-section();
… Nhận xét:
Giải quyết được loại trừ tương hỗ nhưng không triệt để vì giải pháp này có thể vi phạm điều kiện thứ nhất: hai process có thể ở trong critical section tại cùng một thời điểm. Đó là trường hợp có 2 process cùng chờ đợi tại vòng while và cùng thoát khỏi vòng while cùng lúc để nhảy vào tranh chaáp critical section.
Nếu một process bị lỗi trong vùng critical section thì các process khác muốn vào critical section sẽ phải chờ mãi mãi.
Khi một process đang chờ tại vòng while thì nó không làm gì cả nhưng vẫn phải chiếm dụng CPU, nên sử dụng CPU không hiệu quả (hiện tượng busy waiting).
2) ẹieàu phoỏi CPU:
a) Khái niệm điều phối CPU:
Trong hệ thống phân chia thời gian (time-sharing), nhiều process được thực hiện đồng thời. Phải có sự chuyển đổi (switching) CPU qua lại giữa các process để đảm bảo sự thực hiện đồng thời của các process.
Điều phối CPU (scheduling) là xác định khi nào gán CPU cho một process và gán CPU cho process nào. Đây là vấn đề quan trọng vì CPU là tài nguyên quan trọng nhất của hệ thống
b) Muùc tieõu cuỷa ủieàu phoỏi CPU:
Các hệ điều hành xây dựng nhiều chiến lược điều phối khác nhau để thực hiện việc điều phối. Nhưng tựu chung, cần đạt được những mục tiêu sau:
- Công bằng (fairness): các process chia sẻ CPU một cách công bằng, không có một process nào phải chờ CPU vô hạn.
- Tính hiệu quả (efficiency): Làm cho CPU càng bận rộn càng tốt (as busy as possible).
- Hiệu suất cao (throughput): tăng số process thực hiện trong một đơn vị thời gian nhưng phải hợp lý tránh quá tải cho hệ thống.
- Thời gian thực hiện: thời gian thực hiện của 1 process là chấp nhận được.
Bao gồm thời gian chờ đợi (chờ nạp vào ready list, chờ CPU, I/O…) và thời gian thực sự được thực thi.
- Ưu tiên cho các process quan trọng.
c) Các đặc điểm của process:
Nếu phân loại process theo thời gian sử dụng CPU, có 2 loại:
- I/O-bound process: là loại process sử dụng CPU rất ít. Chủ yếu là nó thực hiện các thao tác nhập xuất. Hoạt động của các process loại này thường bao gồm nhiều lượt sử dụng CPU, nhưng mỗi lượt chỉ trong thời gian khá ngắn.
- CPU-bound process: là loại process có khuynh hướng sử dụng CPU trong suốt thời gian dành cho nó. Hoạt động của các process loại này thường bao gồm một số ít lượt sử dụng CPU, nhưng mỗi lượt trong một thời gian khá dài.
Nếu phân loại process theo mức độ độc quyền sử dụng CPU, có 2 loại:
- Non-preemptive process: khi process loại này nhận được CPU thì nó sẽ có quyền độc chiếm CPU cho đến khi hoàn tất xử lý hoặc nó tự nguyện giải phóng CPU. Không thể lấy CPU lại khi process này đang chiếm giữ CPU.
- Preemptive process: Là loại process có thể lấy lại CPU từ nó khi nó đang chiếm giữ CPU. Khi có được CPU, process loại này có thể bị một process khác có độ ưu tiên cao hơn giành lấy CPU bất cứ lúc nào.
3) Tổ chức điều phối CPU:
Hệ điều hành sử dụng hai loại hàng đợi để thực hiện việc điều phối: hàng đợi để các process chờ được cấp phát CPU gọi là ready queue và hàng đợi để các process chờ được sử dụng tài nguyên gọi là waiting queue. Hệ điều hành sử dụng một ready queue cho toàn hệ thống. Mỗi tài nguyên có một waiting queue riêng.
Cách thức hoạt động:
Các process đang thường trú trong bộ nhớ chính và ở trạng thái sẵn sàng tiếp nhận CPU để hoạt động sẽ được đưa vào ready queue.
Bộ điều phối sẽ chọn và cấp CPU cho một process trong ready queue.
Process được cấp CPU sẽ thực hiện xử lý.
Trong thời gian này, process có thể có yêu cầu tài nguyên mà hệ thống chưa thể đáp ứng được. Khi đó process sẽ được đưa vào waiting queue của tài nguyên tương ứng. Mặt khác, process có thể bị buộc dừng xử lý. Khi đó process được đưa trở lại vào ready queue.