›
›

Bài giảng Hệ điều hành - Chương 2: Quản lý tiến trình - Trường Đại học Kinh tế quốc dân

ppt 83 trang Hùng Dũng 05/01/2024 800
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 2: Quản lý tiến trình - Trường Đại học Kinh tế quốc dân", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_he_dieu_hanh_chuong_2_quan_ly_tien_trinh_truong_da.ppt

Nội dung text: Bài giảng Hệ điều hành - Chương 2: Quản lý tiến trình - Trường Đại học Kinh tế quốc dân

  1. Hệ điều hành Chương 2: Quản lý tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 1
  2. Tổng quan • Giới thiệu tổng quan về tiến trình và luồng • Điều phối tiến trình và luồng • Cơ chế thông tin liên lạc giữa các tiến trình • Đồng bộ hoá tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 2
  3. 1. Tổng quan về tiến trình và luồng • Khái niệm tiến trình • Khái niệm luồng • Các trạng thái của tiến trình • Chế độ xử lý của tiến trình • Cấu trúc dữ liệu khối quản lý tiến trình • Thao tác trên tiến trình • Tiến trình và luồng trên LINUX Dang Minh Quan: Institute of IT for Economics-NEU, 2011 3
  4. Khái niệm tiến trình • Chương trình là một thực thể thụ động, chứa đựng các chỉ thị điều khiển máy tính để tiến hành một tác vụ nào đó. • Tiến trình là một chương trình đang xử lý, sở hữu – một con trỏ lệnh, – tập các thanh ghi – các biến. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 4
  5. Khái niệm tiến trình • Tiến trình trong bộ nhớ Dang Minh Quan: Institute of IT for Economics-NEU, 2011 5
  6. Các trạng thái của tiến trình • Khi một tiến trình được chạy, nó sẽ thay đổi trạng thái – new: Tiến trình đang được tạo ra – running: Các lệnh đang được xử lý – waiting: Tiến trình đang đợi một sự kiện nào đó – ready: Tiến trình đang đợi để được gán cho một quá trình xử lý – terminated: Tiến trình kết thúc Dang Minh Quan: Institute of IT for Economics-NEU, 2011 6
  7. Các trạng thái của tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 7
  8. Khối quản lý tiến trình PCB Lưu giữ thông tin của một tiến trình • Trạng thái tiến tình • Bộ đếm chương trình • Các thanh ghi CPU • Thông tin lập lịch CPU • Thông tin quản lý bộ nhớ • Thông tin tài khoản • Thông tin trạng thái I/O Dang Minh Quan: Institute of IT for Economics-NEU, 2011 8
  9. Cấu trúc dữ liệu khối quản lý tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 9
  10. Thao tác trên tiến trình • Hệ￿điều￿hành￿cung￿cấp￿các￿thao￿tác￿chủ￿ yếu￿sau￿đây￿trên￿một￿tiến￿trình : – tạo lập tiến trình (create) – kết thúc tiến trình (destroy) – tạm dừng tiến trình (suspend) – tái kích hoạt tiến trình (resume) – thay đổi độ ưu tiên tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 10
  11. Tạo lập tiến trình (1) • Một tiến trình có thể tạo lập nhiều tiến trình mới bằng cách sử dụng một lời gọi hệ thống tương ứng Dang Minh Quan: Institute of IT for Economics-NEU, 2011 11
  12. Tạo lập tiến trình (2) • định danh cho tiến trình mới phát sinh • đưa tiến trình vào danh sách quản lý của hệ thống • xác định độ ưu tiên cho tiến trình • tạo PCB cho tiến trình • cấp phát các tài nguyên ban đầu cho tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 12
  13. Tạo lập tiến trình (3) • Tiến trình cha tiếp tục xử lý đồng hành với tiến trình con. • Tiến trình cha chờ đến khi một tiến trình con nào đó, hoặc tất cả các tiến trình con kết thúc xử lý. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 13
  14. Tạo lập tiến trình (4) #include #include #include int main() { pid_t pid; pid =fork(); if (pid < 0) { fprintf(stderr, "Fork Failed"); return 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"); } return 0; } Dang Minh Quan: Institute of IT for Economics-NEU, 2011 14
  15. Kết thúc tiến trình • thu hồi các tài nguyên hệ thống đã cấp phát cho tiến trình • hủy tiến trình khỏi tất cả các danh sách quản lý của hệ thống • hủy bỏ PCB của tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 15
  16. Tạm dừng tiến trình - tái kích hoạt tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 16
  17. Sự đa chương (multiprogramming) Dang Minh Quan: Institute of IT for Economics-NEU, 2011 17
  18. Chế độ xử lý của tiến trình • Chế độ không đặc quyền • Chế độ đặc quyền Dang Minh Quan: Institute of IT for Economics-NEU, 2011 18
  19. Cơ chế hoạt động 2 chế độ • Chia sẻ tài nguyên hệ thống đòi hỏi hệ điều hành đảm bảo rằng một chương trình bị lỗi không thể ảnh hưởng tới các chương trình khác. • Cung cấp hỗ trợ cho phần cứng để phân biệt giữa hai phương thức hoạt động. – 1. Chế độ người dùng – chạy chương trình thay mặt cho một người sử dụng. – 2. Monitor mode (chế độ giám sát hoặc chế độ hệ thống) - chạy chương trình thay mặt cho hệ điều hành. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 19
  20. Cơ chế hoạt động 2 chế độ (Cont.) • Bit chế độ thêm vào phần cứng máy tính để chỉ ra chế độ hiện hành: chế độ giám sát (0) hoặc chế độ người dùng (1). • Khi một ngắt hoặc lỗi xảy ra, phần cứng chuyển mạch sang chế độ giám sát. • Các lệnh đặc quyền chỉ được thực hiện trong chế độ giám sát. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 20
  21. Cơ chế hoạt động 2 chế độ (Cont.) • Các lệnh đặc quyền là các lệnh có thể gây hại cho hệ thống – Lệnh chuyển từ chế độ người dùng sang chế độ hạt nhân – Các lệnh điều khiển I/O – Quản lý timer – Quản lý ngắt – . . . Dang Minh Quan: Institute of IT for Economics-NEU, 2011 21
  22. Khái niệm luồng • Một luồng là một đơn vị xử lý cơ bản trong hệ thống. Mỗi luồng xử lý tuần tự đoạn code của nó. • Một luồng phải ở trong 1 tiến trình. • 1 tiến trình có thể có nhiều luồng. • Mỗi luồng xử lý tuần tự đoạn code của nó, sở hữu – một con trỏ lệnh – tập các thanh ghi – vùng nhớ stack riêng Dang Minh Quan: Institute of IT for Economics-NEU, 2011 22
  23. Khái niệm đa luồng Dang Minh Quan: Institute of IT for Economics-NEU, 2011 23
  24. 2. Điều phối tiến trình • Khái niệm chung • Các yêu cầu với quá trình điều phối • Tổ chức điều phối Dang Minh Quan: Institute of IT for Economics-NEU, 2011 24
  25. Khái niệm về điều phối • Bộ điều phối phải lựa chọn tiến trình được xử lý tiếp theo. • Bộ phân phối sẽ chịu trách nhiệm chuyển đổi ngữ cảnh và trao CPU cho tiến trình được chọn bởi bộ điều phối để xử lý. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 25
  26. Đặc điểm tiến trình • Tính hướng xuất / nhập của tiến trình • Tính hướng xử lý của tiến trình • Tiến trình tương tác hay xử lý theo lô • Độ ưu tiên của tiến trình • Thời gian đã sử dụng CPU của tiến trình • Thời gian còn lại tiến trình cần để hoàn tất Dang Minh Quan: Institute of IT for Economics-NEU, 2011 26
  27. Nguyên lý điều phối độc quyền • Cho phép một tiến trình khi nhận được CPU sẽ có quyền độc chiếm CPU đến khi hoàn tất xử lý hoặc tự nguyện giải phóng CPU . • Hoạt động điều phối CPU sẽ xảy ra khi: – Khi tiến trình chuyển từ trạng thái đang xử lý sang trạng thái bị khóa – Khi tiến trình kết thúc Dang Minh Quan: Institute of IT for Economics-NEU, 2011 27
  28. Nguyên lý điều phối không độc quyền • Cho phép tạm dừng hoạt động của một tiến trình đang sẵn sàng xử lý. • Hoạt động điều phối CPU sẽ xảy ra khi: – Khi tiến trình chuyển từ trạng thái đang xử lý sang trạng thái bị khóa – Khi tiến trình chuyển từ trạng thái đang xử lý sang trạng thái ready – Khi tiến trình chuyển từ trạng thái chờ sang trạng thái – Khi tiến trình kết thúc Dang Minh Quan: Institute of IT for Economics-NEU, 2011 28
  29. Các yêu cầu với quá trình điều phối • Sự công bằng • Tính hiệu qủa • Thời gian đáp ứng hợp lý • Thời gian lưu lại trong hệ thống • Thông lượng tối đa Dang Minh Quan: Institute of IT for Economics-NEU, 2011 29
  30. Các danh sách sử dụng trong quá trình điều phối (1) • danh sách sẵn sàng (ready list) – chỉ các tiến trình đ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 – Hệ điều hành chỉ sử dụng một danh sách sẵn sàng cho toàn hệ thống • danh sách chờ đợi(waiting list) – tiến trình sẽ được chuyển sang một danh sách chờ khi xảy ra các sự kiện – mỗi một tài nguyên ( thiết bị ngoại vi ) có một danh sách chờ đợi riêng bao gồm các tiến trình đang chờ được cấp phát tài nguyên đó Dang Minh Quan: Institute of IT for Economics-NEU, 2011 30
  31. Các danh sách sử dụng trong quá trình điều phối (2) Dang Minh Quan: Institute of IT for Economics-NEU, 2011 31
  32. Chuyển đổi giữa các danh sách điều phối Dang Minh Quan: Institute of IT for Economics-NEU, 2011 32
  33. Điều phối tác vụ (job scheduling) • Quyết định lựa chọn tác vụ nào được đưa vào hệ thống và nạp những tiến trình của tác vụ đó vào bộ nhớ chính để thực hiện • Chức năng điều phối tác vụ quyết định mức độ đa chương của hệ thống • Được kích hoạt khi – hệ thống tạo lập một tiến trình – có một tiến trình kết thúc xử lý • Điều phối tác vụ có tần suất hoạt động thấp Dang Minh Quan: Institute of IT for Economics-NEU, 2011 33
  34. Điều phối tiến trình • Chọn một tiến trình ở trạng thái sẵn sàng ( đã được nạp vào bộ nhớ chính, và có đủ tài nguyên để hoạt động ) và cấp phát CPU cho tiến trình đó thực hiện • Có tần suất hoạt động cao, sau mỗi lần xảy ra ngắt Dang Minh Quan: Institute of IT for Economics-NEU, 2011 34
  35. Điều phối trung gian • Kết hợp cả hai cấp độ điều phối tác vụ và tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 35
  36. Chiến lược điều phối FIFO • CPU được cấp phát cho tiến trình đầu tiên trong danh sách sẵn sàng có yêu cầu • Điều phối theo nguyên tắc độc quyền • Có thể xảy ra hiện tượng tích lũy thời gian chờ • Không phù hợp với các hệ phân chia thời gian Dang Minh Quan: Institute of IT for Economics-NEU, 2011 36
  37. Chiến lược điều phối xoay vòng • bộ điều phối lần lượt cấp phát cho từng tiến trình trong danh sách một khoảng thời gian sử dụng CPU gọi là quantum • khi một tiến trình sử dụng CPU đến hết thời gian quantum dành cho nó, hệ điều hành thu hồi CPU và cấp cho tiến trình kế tiếp trong danh sách Dang Minh Quan: Institute of IT for Economics-NEU, 2011 37
  38. Chiến lược điều phối ưu tiên • Mỗi tiến trình được gán cho một độ ưu tiên tương ứng • tiến trình có độ ưu tiên cao nhất sẽ được chọn để cấp phát CPU đầu tiên • Giải thuật điều phối với độ ưu tiên có thể theo nguyên tắc độc quyền hay không độc quyền • Tình trạng ‘đói CPU’ (starvation) là một vấn đề chính yếu Dang Minh Quan: Institute of IT for Economics-NEU, 2011 38
  39. Chiến lược công việc ngắn nhất • Khi CPU được tự do, nó sẽ được cấp phát cho tiến trình yêu cầu ít thời gian nhất để kết thúc- tiến trình ngắn nhất. • Giải thuật này cũng có thể độc quyền hay không độc quyền • Khó khăn thực sự của giải thuật SJF là không thể biết được thời gian yêu cầu xử lý còn lại của tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 39
  40. Chiến lược điều phối với nhiều mức độ ưu tiên (1) • phân lớp các tiến trình tùy theo độ ưu tiên Dang Minh Quan: Institute of IT for Economics-NEU, 2011 40
  41. Chiến lược điều phối với nhiều mức độ ưu tiên (2) • các tiến trình có cùng độ ưu tiên được áp dụng một giải thuật điều phối thích hợp để điều phối • giải thuật điều phối giữa các nhóm, thường là giải thuật không độc quyền Dang Minh Quan: Institute of IT for Economics-NEU, 2011 41
  42. Chiến lược điều phối Xổ số • phát hành một số vé số và phân phối cho các tiến trình trong hệ thống • Khi đến thời điểm ra quyết định điều phối, sẽ tiến hành chọn 1 vé "trúng giải", tiến trình nào sỡ hữu vé này sẽ được nhận CPU Dang Minh Quan: Institute of IT for Economics-NEU, 2011 42
  43. 3. Cơ chế thông tin liên lạc giữa các tiến trình • Nhu cầu liên lạc giữa các tiến trình • Các vấn đề nảy sinh trong việc liên lạc giữa các tiến trình • Các cơ chế liên lạc Dang Minh Quan: Institute of IT for Economics-NEU, 2011 43
  44. Nhu cầu liên lạc giữa các tiến trình • Các tiến trình là những thực thể độc lập , nhưng chúng vẫn có nhu cầu liên lạc với nhau để – Chia sẻ thông tin – Hợp tác hoàn thành tác vụ Dang Minh Quan: Institute of IT for Economics-NEU, 2011 44
  45. Các vấn đề nảy sinh trong việc liên lạc giữa các tiến trình • Liên kết tường minh hay tiềm ẩn (explicit naming/implicit naming) • Liên lạc theo chế độ đồng bộ hay không đồng bộ • Liên lạc giữa các tiến trình trong hệ thống tập trung và hệ thống phân tán Dang Minh Quan: Institute of IT for Economics-NEU, 2011 45
  46. Liên lạc bằng tín hiệu (1) • Tín hiệu là một cơ chế phần mềm tương tự như các ngắt cứng tác động đến các tiến trình. • Một tín hiệu được sử dụng để thông báo cho tiến trình về một sự kiện nào đó xảy ra. • Mỗi tiến trình sở hữu một bảng biễu diễn các tín hiệu khác nhau. • Với mỗi tín hiệu sẽ có tương ứng một trình xử lý tín hiệu. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 46
  47. Liên lạc bằng tín hiệu (2) • Các tín hiệu được gởi đi bởi : – Phần cứng – Hạt nhân hệ điều hành gởi đến một tiến trình – Một tiến trình gởi đến một tiến trình khác – Người dùng Dang Minh Quan: Institute of IT for Economics-NEU, 2011 47
  48. Liên lạc bằng tín hiệu (3) • Khi một tiến trình nhận một tín hiệu, nó có thể xử sự theo một trong các cách sau : – Bỏ qua tín hiệu – Xử lý tín hiệu theo kiểu mặc định – Tiếp nhận tín hiệu và xử lý theo cách đặc biệt của tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 48
  49. Liên lạc bằng tín hiệu (4) • Liên lạc bằng tín hiệu mang tính chất không đồng bộ • Hơn nữa các tiến trình không thể kiểm tra được sự kiện tương ứng với tín hiệu có thật sự xảy ra ? • các tiến trình chỉ có thể thông báo cho nhau về một biến cố nào đó, mà không trao đổi dữ liệu Dang Minh Quan: Institute of IT for Economics-NEU, 2011 49
  50. Liên lạc bằng đường ống (1) • Một pipe là một kênh liên lạc trực tiếp giữa hai tiến trình : dữ liệu xuất của tiến trình này được chuyển đến làm dữ liệu nhập cho tiến trình kia dưới dạng một dòng các byte Dang Minh Quan: Institute of IT for Economics-NEU, 2011 50
  51. Liên lạc bằng đường ống (2) • Tiến trình đọc pipe sẽ bị khóa nếu pipe trống, nó sẽ phải đợi đến khi pipe có dữ liệu để truy xuất. • Tiến trình ghi pipe sẽ bị khóa nếu pipe đầy, nó sẽ phải đợi đến khi pipe có chỗ trống để chứa dữ liệu. • Liên lạc bằng pipe là một cơ chế liên lạc một chiều (unidirectional) • chỉ cho phép kết nối hai tiến trình có quan hệ cha-con, và trên cùng một máy tính. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 51
  52. Liên lạc bằng vùng nhớ chia sẻ(1) • Cho nhiều tiến trình cùng truy xuất đến một vùng nhớ chung gọi là vùng nhớ chia sẻ (shared memory). • Một vùng nhớ chia sẻ tồn tại độc lập với các tiến trình. • Khi một tiến trình muốn truy xuất đến vùng nhớ này, tiến trình phải kết gắn vùng nhớ chung đó vào không gian địa chỉ riêng của từng tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 52
  53. Liên lạc bằng vùng nhớ chia sẻ(2) • phương thức này làm phát sinh các khó khăn trong việc bảo đảm sự toàn vẹn dữ liệu (coherence) • không thể áp dụng hiệu quả trong các hệ phân tán Dang Minh Quan: Institute of IT for Economics-NEU, 2011 53
  54. Liên lạc bằng trao đổi thông điệp • Hệ điều hành cung cấp các hàm IPC chuẩn (Interprocess communication) – Send(message) : gởi một thông điệp – Receive(message) : nhận một thông điệp • Đơn vị truyền thông tin trong cơ chế trao đổi thông điệp là một thông điệp nên các tiến trình có thể trao đổi dữ liệu ở dạng có cấu trúc Dang Minh Quan: Institute of IT for Economics-NEU, 2011 54
  55. Liên lạc bằng socket (1) • Một socket là một thiết bị truyền thông hai chiều tương tự như tập tin • mỗi socket là một thành phần trong một mối nối nào đó giữa các máy trên mạng máy tính và các thao tác đọc/ghi chính là sự trao đổi dữ liệu giữa các ứng dụng trên nhiều máy khác nhau. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 55
  56. Liên lạc bằng socket (2) • Để thực hiện liên lạc bằng socket, cần tiến hành các thao tác :: – Tạo lập hay mở một socket – Gắn kết một socket với một địa chỉ – Liên lạc : có thể liên lạc trong chế độ không nối kết hay có nối kết Dang Minh Quan: Institute of IT for Economics-NEU, 2011 56
  57. Liên lạc bằng socket (3) • Liên lạc trong chế độ không liên kết – hai tiến trình liên lạc với nhau không kết nối trực tiếp – mỗi thông điệp phải kèm theo địa chỉ người nhận. – người gởi không chắc chắn thông điệp của học được gởi đến người nhận, – một thông điệp có thể được gởi nhiều lần, – hai thông điệp được gởi theo một thứ tự nào đó có thể đến tay người nhận theo một thứ tự khác. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 57
  58. Liên lạc bằng socket (4) • Liên lạc trong chế độ nối kết theo mô hình client – server – server sử dụng lời gọi hệ thống listen và accept để nối kết với client – client và server có thể trao đổi thông tin bằng cách sử dụng các primitive send và receive Dang Minh Quan: Institute of IT for Economics-NEU, 2011 58
  59. 4. Đồng bộ hoá tiến trình • Nhu cầu đồng bộ hoá tiến trình • Giải pháp « busy waiting » • Giải pháp « sleep and wakeup » Dang Minh Quan: Institute of IT for Economics-NEU, 2011 59
  60. Yêu cầu độc quyền truy xuất (Mutual exclusion) • Hệ thống có tài nguyên không thể chia sẻ chỉ chấp nhận một tiến trình sử dụng tại một thời điểm • Nếu nhiều tiến trình sử dụng tài nguyên đồng thời, có nguy cơ xảy ra các kết quả không dự đoán được • Cần bảo đảm tiến trình độc quyền truy xuất tài nguyên Dang Minh Quan: Institute of IT for Economics-NEU, 2011 60
  61. Yêu cầu phối hợp (Synchronization) • Mối tương quan về tốc độ thực hiện của hai tiến trình trong hệ thống là không thể biết trước • Như ng có những tình huống các tiến trình cần hợp tác trong việc hoàn thành tác vụ, khi đó cần phải đồng bộ hóa hoạt động của các tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 61
  62. Vấn đề tranh đoạt điều khiển (race condition) (1) • có hai tiến trình P1 và P2 thực hiện công việc kế toán, và cùng chia sẻ biến taikhoan phản ánh thông tin về tài khoản – if (taikhoan - tienrut >=0) – taikhoan = taikhoan - tienrut; – else – error(« khong the rut tien ! »); • Giả sử trong tài khoản hiện còn 800, P1 muốn rút 500 và P2 muốn rút 400 Dang Minh Quan: Institute of IT for Economics-NEU, 2011 62
  63. Vấn đề tranh đoạt điều khiển (race condition) (2) • P1 kiểm tra điều kiện (taikhoan - tienrut >=0) và hết thời gian xử lý, hệ điều hành cấp phát CPU cho P2. • P2 kiểm tra cùng điều kiện trên, nhận được kết quả là 400 (do P1 vẫn chưa rút tiền) và rút 400. Giá trị của taikhoan được cập nhật lại là 400 • Khi P1 được tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện (taikhoan - tienrut >=0) -vì đã kiểm tra trong lượt xử lý trước- mà thực hiện rút tiền. Giá trị của taikhoan sẽ lại được cập nhật thành -100. Tình huống lỗi xảy ra ! Dang Minh Quan: Institute of IT for Economics-NEU, 2011 63
  64. Miền găng (critical section) (1) • Đoạn chương trình trong đó có khả năng xảy ra các mâu thuẫn truy xuất trên tài nguyên chung được gọi là miền găng (critical section). – if (taikhoan - tienrut >=0) – taikhoan = taikhoan - tienrut; Dang Minh Quan: Institute of IT for Economics-NEU, 2011 64
  65. Miền găng (critical section) (2) • Một phương pháp giải quyết tốt bài toán miền găng cần thõa mãn 4 điều kiện – Không có hai tiến trình cùng ở trong miền găng cùng lúc. – Không có giả thiết nào đặt ra cho sự liên hệ về tốc độ của các tiến trình, cũng như về số lượng bộ xử lý trong hệ thống – Một tiến trình tạm dừng bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng – Không có tiến trình nào phải chờ vô hạn để được vào miền găng Dang Minh Quan: Institute of IT for Economics-NEU, 2011 65
  66. Giải pháp « busy waiting » • Sử dụng các biến cờ hiệu • Sử dụng việc kiểm tra luân phiên • Giải pháp của Peterson • Cấm ngắt • Chỉ thị TSL (Test-and-Set) Dang Minh Quan: Institute of IT for Economics-NEU, 2011 66
  67. Sử dụng các biến cờ hiệu while (TRUE) { while (lock == 1); // wait lock = 1; critical-section (); lock = 0; Noncritical-section (); } Dang Minh Quan: Institute of IT for Economics-NEU, 2011 67
  68. Sử dụng việc kiểm tra luân phiên while (TRUE) { while (TRUE) { while (turn != 0); // while (turn != 1); // wait wait critical-section (); critical-section (); turn = 1; turn = 0; Noncritical-section (); Noncritical-section (); } } (a) Cấu trúc tiến trình A (b)￿Cấu￿trúc￿tiến￿trình￿ B￿ Dang Minh Quan: Institute of IT for Economics-NEU, 2011 68
  69. Giải pháp của Peterson while (TRUE) { int j = 1-i; // j là tiến trình còn lại interesse[i]= TRUE; turn = j; while (turn == j && interesse[j]==TRUE); critical-section (); interesse[i] = FALSE; Noncritical-section (); } Dang Minh Quan: Institute of IT for Economics-NEU, 2011 69
  70. Cấm ngắt • cho phép tiến trình cấm tất cả các ngắt trước khi vào miền găng, và phục hồi ngắt khi ra khỏi miền găng. • Khi đó, ngắt đồng hồ cũng không xảy ra, do vậy hệ thống không thể tạm dừng hoạt động của tiến trình đang xử lý để cấp phát CPU cho tiến trình khác Dang Minh Quan: Institute of IT for Economics-NEU, 2011 70
  71. Chỉ thị TSL (Test-and-Set) Test-and-Setlock(boolean target){ Test-and-Setlock = target; target = TRUE; } while (TRUE) { while (Test-and-Setlock(lock)); critical-section (); lock = FALSE; Noncritical-section (); } Dang Minh Quan: Institute of IT for Economics-NEU, 2011 71
  72. Nhận xét • Các giải pháp buộc tiến trình phải liên tục kiểm tra điều kiện để phát hiện thời điểm thích hợp được vào miền găng • Việc kiểm tra như thế tiêu thụ rất nhiều thời gian sử dụng CPU, do vậy tiến trình đang chờ vẫn chiếm dụng CPU Dang Minh Quan: Institute of IT for Economics-NEU, 2011 72
  73. Giải pháp « sleep and wakeup » while (TRUE) { if (busy){ blocked = blocked + 1; sleep(); } else busy = 1; critical-section (); busy = 0; if(blocked){ wakeup(process); blocked = blocked - 1; } Noncritical-section (); } Dang Minh Quan: Institute of IT for Economics-NEU, 2011 73
  74. Semaphore (1) • một semaphore s là một biến có các thuộc tính sau: • Một giá trị nguyên dương e(s) • Một hàng đợi f(s) lưu danh sách các tiến trình đang bị khóa (chờ) trên semaphore s Dang Minh Quan: Institute of IT for Economics-NEU, 2011 74
  75. Semaphore (2) • Chỉ có hai thao tác được định nghĩa trên semaphore – Down(s): giảm giá trị của semaphore s đi 1 đơn vị nếu semaphore có trị e(s) > 0, và tiếp tục xử lý. Ngược lại, nếu e(s) 0 – Up(s): tăng giá trị của semaphore s lên 1 đơn vị. Nếu có một hoặc nhiều tiến trình đang chờ trên semaphore s, bị khóa bởi thao tác Down, thì hệ thống sẽ chọn một trong các tiến trình này để kết thúc thao tác Down và cho tiếp tục xử lý Dang Minh Quan: Institute of IT for Economics-NEU, 2011 75
  76. Tổ chức truy xuất độc quyền với Semaphores – while (TRUE) { – Down(s) – critical-section (); – Up(s) – Noncritical-section (); – } Dang Minh Quan: Institute of IT for Economics-NEU, 2011 76
  77. Tổ chức đồng bộ hóa với Semaphores – P1: – while (TRUE) { – job1(); Up(s); //đánh thức P2 – } – P2: – while (TRUE) { – Down(s); // chờ P1 job2(); – } Dang Minh Quan: Institute of IT for Economics-NEU, 2011 77
  78. Monitors (1) • Monitor là một cấu trúc đặc biệt bao gồm các thủ tục, các biến và cấu trúc dữ liệu có các thuộc tính sau – Các biến và cấu trúc dữ liệu bên trong monitor chỉ có thể được thao tác bởi các thủ tục định nghĩa bên trong monitor đó. (encapsulation). – Tại một thời điểm, chỉ có một tiến trình duy nhất được hoạt động bên trong một monitor (mutual exclusive). Dang Minh Quan: Institute of IT for Economics-NEU, 2011 78
  79. Monitors (2) • Trong một monitor, có thể định nghĩa các biến điều kiện và hai thao tác kèm theo là Wait và Signal như sau : gọi c là biến điều kiện được định nghĩa trong monitor: – Wait(c): chuyển trạng thái tiến trình gọi sang blocked , và đặt tiến trình này vào hàng đợi trên biến điều kiện c. – Signal(c): nếu có một tiến trình đang bị khóa trong hàng đợi của c, tái kích hoạt tiến trình đó, và tiến trình gọi sẽ rời khỏi monitor. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 79
  80. Monitors (3) – monitor condition ; ; procedure Action1(); { } procedure Actionn(); { } end monitor; – Cấu trúc một monitor Dang Minh Quan: Institute of IT for Economics-NEU, 2011 80
  81. Monitors (4) • while (TRUE) { • Noncritical-section (); .Actioni; //critical-section(); Noncritical-section (); • } • Cấu trúc tiến trình Pi trong giải pháp monitor Dang Minh Quan: Institute of IT for Economics-NEU, 2011 81
  82. Trao đổi thông điệp (1) • Send(destination, message): gởi một thông điệp đến một tiến trình hay gởi vào hộp thư • Receive(source,message): nhận một thông điệp thừ một tiến trình hay từ bất kỳ một tiến trình nào, tiến trình gọi sẽ chờ nếu không có thông điệp nào để nhận Dang Minh Quan: Institute of IT for Economics-NEU, 2011 82
  83. Trao đổi thông điệp (2) • while (TRUE) { • Send(process controler, request message); Receive(process controler, accept message); critical-section (); Send(process controler, end message); Noncritical-section (); • } Dang Minh Quan: Institute of IT for Economics-NEU, 2011 83