Bài giảng Nguyên lý hệ điều hành: Chương 2 - GV. Đặng Quang Hiển

Chia sẻ: Nguyễn Hà | Ngày: | Loại File: PDF | Số trang:118

0
148
lượt xem
34
download

Bài giảng Nguyên lý hệ điều hành: Chương 2 - GV. Đặng Quang Hiển

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 2 Quản lý tiến trình thuộc bài giảng nguyên lý hệ điều hành, cùng nắm kiến thức trong chương này thông qua việc tìm hiểu các nội dung sau: các mô hình xử lý đồng hành, tổ chức và quản lý tiến trình, điều phối tiến trình, tài nguyên găng và đoạn găng, các giải pháp về đồng bộ hóa, bế tắc và chống bế tắc.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Nguyên lý hệ điều hành: Chương 2 - GV. Đặng Quang Hiển

  1. NGUYÊN LÝ HỆ ĐIỀU HÀNH (3 Tín chỉ) GV: Đỗ Công Đức Khoa khoa học máy tính
  2. Chương 2: QUẢN LÝ TIẾN TRÌNH 2.1. Các mô hình xử lý đồng hành 2.2. Tổ chức và quản lý tiến trình 2.3. Điều phối tiến trình 2.4. Tài nguyên găng và đoạn găng 2.5. Các giải pháp về đồng bộ hóa 2.6. Bế tắc và chống bế tắc 6/28/2014 Chương 2. Quản lý tiến trình 2
  3. CÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.1 Nhu cầu xử lý đồng hành (1/2) Đa số các HĐH hiện nay đều cho phép người dùng xử lý nhiều tác vụ đồng thời cùng một lúc trên máy tính để:  Tăng hiệu suất sử dụng CPU: các công việc phải trải qua nhiều chu kỳ xử lý (xử dụng CPU) và chu kỳ nhập xuất (IO) xen kẽ nhau CPU IO CPU IO CPU Nếu chỉ có 1 tiến trình duy nhất trong hệ thống, thì vào các chu kỳ IO của tác vụ, CPU sẽ hoàn toàn nhàn rỗi. Ý tưởng tăng cường số lượng tác vụ trong hệ thống là để tận dụng CPU: nếu tác vụ 1 xử lý IO, thì có thể sử dụng CPU để thực hiện tác vụ 2 Tác vụ 1 CPU IO CPU IO CPU IO Tác vụ 2 CPU IO CPU IO CPU 6/28/2014 Chương 2. Quản lý tiến trình 3
  4. CÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.1 Nhu cầu xử lý đồng hành (2/2)  Tăng tốc độ xử lý: xử lý song song nếu được xây dựng thành nhiều modul hoạt động đồng thời thì sẽ tiết kiệm được thời gian xử lý -Ví dụ: Tính giá trị của biểu thức a*b + c*d Nếu tiến hành song song tính a*b và c*d thì giải quyết bài toán nhanh hơn tính tuần tự a*b, c*d và sau đó mới tính tổng Trong các trường hợp đó, cần có một mô hình xử lý đồng hành thích hợp. Trên máy tính có cấu hình nhiều CPU, hỗ trợ xử lý song song (multiprocessing) thật sự, điều này sẽ giúp tăng hiệu quả thi hành của hệ thống đáng kể 6/28/2014 Chương 2. Quản lý tiến trình 4
  5. CÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.2 Tiến trình và mô hình đa tiến trình (1/2)  Sự đa chương của máy tính là sự thực hiện nhiều tác vụ đồng thời. Để thực hiện điều này HĐH xử lý mô hình song song giả lập. Nghĩa là chuyển đổi bộ xử lý qua lại giữa các tiến trình trong khoảng 1% hoặc 1/10 mili giây để duy trì hoạt động của chương trình.  Để hoàn thành tác vụ của mình, một tiến trình có thể cần đến một số tài nguyên như CPU, bộ nhớ chính, các tập tin và thiết bị  Phân biệt chương trình và tiến trình: chương trình là một thực thể thụ động, khi thi hành thì thực thi các tác vụ, chỉ thị thì chương trình chuyển thành tiến trình là một thực thể hoạt động, xác định chỉ thị tiếp theo thi hành và cung cấp các tài nguyên cho tiến trình 6/28/2014 Chương 2. Quản lý tiến trình 5
  6. CÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.2 Tiến trình và mô hình đa tiến trình (2/2)  Trong thực tế, chỉ có một bộ xử lý thật sự, được chuyển đổi qua lại giữa các tiến trình. Sự chuyển đổi nhanh chóng này được gọi là sự đa chương. HĐH chịu trách nhiệm sử dụng một thuật toán điều phối để quyết định thời điểm cần dừng hoạt động của tiến trình đang xử lý để phục vụ một tiến trình khác và lựa chọn tiến trình tiếp theo sẽ được phục vụ. Bộ phận thực hiện chức năng này của HĐH được gọi là bộ điều phối Một con trỏ lệnh Tiến trình A 4 con trỏ lệnh D B C B C A C B D A D Thời gian (a) (b) (c) 6/28/2014 Chương 2. Quản lý tiến trình 6
  7. CÁC MÔ HÌNH XỬ LÝ ĐỒNG HÀNH 2.1.3 Tiểu trình và mô hình đa tiểu trình  Mỗi tiến trình có một không gian địa chỉ và chỉ có một dòng xử lý, nhưng người sử dụng mong muốn có nhiều dòng xử lý cùng chia sẻ một không gian địa chỉ và các dòng xử lý này hoạt động song song.  HĐH cung cấp một cơ chế xử lý mới cho phép có nhiều dòng xử lý trong cùng một tiến trình và gọi là tiểu trình  Tiểu trình là một đơn vị xử lý cơ bản, mỗi tiểu trình xử lý tuần tự đoạn code, sở hữu một con trỏ lệnh, tập các thanh ghi, stack riêng. Các tiểu trình chia sẻ CPU với nhau giống như cách chia sẻ giữa các tiến trình. Một tiến trình có thể sở hữu nhiều tiểu trình  Tiến trình là một chương trình hoạt động và cần có nhiều tiến trình được lưu trữ trong bộ nhớ tại một thời đểm và điều phối qua lại giữa các tiến trình làm cho sự đa chương của HĐH tăng lên. 6/28/2014 Chương 2. Quản lý tiến trình 7
  8. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH  Trong môi trường đa chương, một CPU có thể chuyển từ chương trình này sang chương trình khác, thực hiện mỗi chương trình trong khoảng 1% hoặc 1/10 mili giây. Thực chất tại một thời điểm, CPU chỉ thực hiện được một chương trình. Nhưng xét trong khoảng thời gian phần trăm giây thì CPU có thể thực hiện được nhiều công việc  Tiến trình là một dãy các trạng thái của hệ thống tính toán và việc chuyển từ trạng thái này sang trạng thái khác S0 S1 S2 S3 S4 S5 S6 S7 …. Sn-1 Sn Sn+1 …. Các trạng thái này nhất thiết không phải liên tiếp. Chương trình nào thì tạo ra tiến trình đó, gồm tiến trình của hệ thống và tiến trình của người sử dụng 6/28/2014 Chương 2. Quản lý tiến trình 8
  9. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.1 Các loại tiến trình:2 loại là tuần tự và song song  Tiến trình tuần tự: Là các tiến trình mà điểm khởi tạo của nó là điểm kết thúc của tiến trình trước đó.  Tiến trình song song: Hai tiến trình gọi là song song nếu thời điểm bắt đầu của của tiến trình này nằm giữa thời điểm bắt đầu và kết thúc của chương trình kia Tiến trình 1 Bắt đầu Kết thúc Tiến trình 2 Bắt đầu 6/28/2014 Chương 2. Quản lý tiến trình 9
  10. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.1 Các loại tiến trình:2 loại là tuần tự và song song Tiến trình song song khi thực hiện thì có thể thực hiện song song vật lý và song song đan xen. + Tiến trình song song độc lập: Không có quan hệ thông tin với nhau + Tiến trình song song có quan hệ thông tin: trong quá trình hoạt động các tiến trình thường trao đổi thông tin với nhau + Tiến trình song song phân cấp: trong khi hoạt động nó sản sinh ra một tiến trình nữa và hoạt động song song chính nó. Tiến trình khởi tạo là tiến trình cha, tiến trình được tạo ra gọi là tiến trình con + Tiến trình song song đồng mức: sử dụng chung tài nguyên theo nguyên tắc lần lược, mỗi tiến trình sau một khoảng thời gian chiếm giữ tài nguyên phải tự động trả lại tài nguyên cho tiến trình kia 6/28/2014 Chương 2. Quản lý tiến trình 10
  11. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH P1 P1 P2 P2 P3 Time P3 Time a. Trong hệ thống uniprocessor b. Trong hệ thống multiprocessor Khảo sát hoạt động của tiến trình song hệ thống uniprocessor. Đối với người sử dụng thì trong hệ thống chỉ có hai nhóm tiến trình + Thứ nhất là các tiến trình của HĐH. + Thứ hai là các tiến trình của chương trình người sử dụng. Các tiến trình của HĐH hoạt động trong chế độ độc quyền, nhờ đó mà nó có thể truy xuất vào các vùng dữ liệu được bảo vệ của hệ thống. Tiến trình của chương trình người sử dụng hoạt động trong chế độ không độc quyền, nên nó không thể truy xuất vào hệ thống, nhờ đó mà HĐH được bảo vệ. Các tiến trình của chương trình người sử dụng truy xuất vào hệ thống thông qua HĐH bằng lời gọi hệ thống 6/28/2014 Chương 2. Quản lý tiến trình 11
  12. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.2 Các mô hình tiến trình (1/4) Về nguyên tắc thì mỗi processor có nhiệm vụ thực hiện một chương trình. Người sử dụng thì muốn sự đa chương, đa nhiệm nhưng chỉ thực hiện trên một processor. Để thực hiện, HĐH đã sử dụng mô hình tiến trình tạo ra sự song song giả hay tạo ra các processor logic từ processor vật lý. Các processor logic có thể hoạt động song song với nhau, mỗi processor logic chịu trách nhiệm thực hiện một tiến trình. Mỗi chương trình chia thành nhiều tiến trình, khởi tạo và đưa vào hệ thống, cấp phát đầy đủ tài nguyên cho tiến trình, đưa các tiến trình sang trạng thái sẵn sàng. HĐH cấp processor cho tiến trình để hoạt động, sau một khoảng thời gian thu hồi processor để cấp cho một tiến trình và như thế cho đến khi tất cả các tiến trình mà HĐH khởi tạo đều hoạt động và kết thúc được 6/28/2014 Chương 2. Quản lý tiến trình 12
  13. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.2 Các mô hình tiến trình (2/4) Giả sử trong hệ thống có 3 tiến trình sẵn sàng P1, P2, P3 quá trình chuyển: P1 Thời điểm Trạng thái các tiến trình P2 t1 P1: được cấp processor P3 t2 P1: bị thu hồi processor Time P3: được cấp processor t1 t2 t3 t4 t5 t6 t3 P3: bị thu hồi processor P1: được cấp processor t4 P1: kết thúc và trả lại P2: được cấp processor t5 P2: kết thúc và trả lại P3: được cấp processor t6 P3: kết thúc và trả lại 6/28/2014 Chương 2. Quản lý tiến trình 13
  14. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.2 Các mô hình tiến trình (3/4) Processor là thực hiện chỉ thị của máy thường trú trong bộ nhớ chính việc chuyển processor từ tiến trình này sang tiến trình khác là việc điều khiển processor để nó thực hiện xen kẽ các chỉ thị bên trong tiến trình Điều này có thể thực hiện dễ dàng bằng cách thay đổi hợp lý giá trị của con trỏ lệnh, đó chính là cặp thanh ghi CS:IP trong các processor Giả sử hệ thống cần thực hiện đồng thời 3 tiến trình P1, P2, P3, bắt đầu từ tiến trình P1. Các chỉ thị của các tiến trình này được nạp vào bộ nhớ tại các địa chỉ Tiến trình P1: Tiến trình P2: Tiến trình P3: a+0 b+0 c+0 a+1 b+2 c+1 a+3 b+3 c+4 a+5 c+6 6/28/2014 Chương 2. Quản lý tiến trình 14
  15. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.2 Các mô hình tiến trình (4/4) Processor thực hiện xen kẽ các chỉ thị của 3 tiến trình P1,P2,P3 từ lệnh đầu tiên đến lệnh cuối cùng, cho đến khi tất cả các chỉ thị của 3 tiến trình đều thực hiện. Nhưng khoảng thời gian từ khi con trỏ lệnh =a+0 đến khi =a+1, hay từ khi =b+0 đến khi =b+2… là rất nhỏ, nên hệ thống có “cảm giác” 3 tiến trình P1, P2, P3 hoạt động đồng thời Mô hình thực hiện đồng thời của tiến trình uniprocessor có 2 thuận lợi: -Tiết kiệm được bộ nhớ: vì nó chỉ nạp các tiến trình cần thiết sau đó mới nạp các tiến trình khác khi có yêu cầu -Cho phép các chương trình hoạt động song song nên tốc độ của hệ thống tăng lên và khai thác tối đa thời gian xử lý processor. HĐH có một cơ chế thích hợp để chọn điểm dừng, thu hồi processor để chuyển cho tiến trình sẵn sàng tiếp theo khác…. 6/28/2014 Chương 2. Quản lý tiến trình 15
  16. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trình  Tiến trình 2 trạng thái: Not Running và Running Dispatch Enter Not Running Exit Running Pause Sơ đồ chuyển tiến trình 2 trạng thái Khi HĐH tạo ra một tiến trình mới, đưa tiến trình đó vào hệ thống ở trạng thái Not Running, chờ chuyển sang trạng thái Running. Khi đang thực hiện bị ngắt thì bộ điều phối thu hồi lại processor và chọn một tiến trình ở trạng thái Not Running để cấp processor cho nó và chuyển nó sang trạng thái Running. Tiến trình bị thu hồi processor sẽ được chuyển về lại trạng thái Not Running 6/28/2014 Chương 2. Quản lý tiến trình 16
  17. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trình  Tiến trình 2 trạng thái: Not Running và Running Queue Enter Dispatch Processor Exit Pause Sơ đồ chuyển tiến trình vào hàng đợi Tại một thời điểm xác định chỉ duy nhất một tiến trình ở trạng thái Runnig, nhưng có nhiều tiến trình ở trạng thái Not Running, các tiến trình ở trạng thái Not Running được chứa trong một hàng đợi (Queue). Tiến trình đang ở trạng thái Running bị chuyển sang trạng thái Not Running sẽ được đưa vào hàng đợi 6/28/2014 Chương 2. Quản lý tiến trình 17
  18. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trình  Tiến trình 3 trạng thái: Ready, Running, Blocked - Ready: trang thái sẵn sàng chờ cấp phát Processor để thực hiên - Running: là tiến trình đang sở hữu Processor để hoạt động - Blocked: tiến trình đang chờ cấp phát thêm tài nguyên để một sự kiện nhập xuất nào đó xảy ra hoặc kết thúc New 1. Tiến trình được khởi tạo, 2 1 đượcTiến vào hệ thống, được 2. đưa trình được cấp 4 Ready Running 3. Tiến trình bị tài đầu phối processorđầy hoàn nguyên lý cấpTiến trình đủbắt thành xửchỉ 4. phát để bộ điều thực và Tiến lý thukết thúc hiện/xử trình đang chờhết thời 3 thiếu processor 5. hồi processor, do một sự 6. Sự nào đó quyền hay dụng kiện được tiến trình đang gian kiện màxảy ra sử chờ đã Blocked Exit 6 5 xảy mộtthao tác nhập/xuất tiến chờ ra, thao tác phát cho kết processor, để cấp nhập/xuất mà Sơ đồ chuyển tiến trình 3 trạng thái tiến trình đợi đã kết thúc thúc trình khác 6/28/2014 Chương 2. Quản lý tiến trình 18
  19. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trình  Tiến trình 3 trạng thái: Ready, Running, Blocked Ready Queue Admit Dispatch Release Processor Time-out Event Event Wait Occurs Blocked Queue Sơ đồ chuyển tiến trình vào hàng đợi Tại một thời điểm xác định trong hệ thống có thể có nhiều tiến trình đang ở trạng thái Ready hoặc Blocked nhưng chỉ có một tiến trình ở trạng thái Running. Các tiến trình ở trạng thái Ready và Blocked được chứa trong các hàng đợi (Queue) riêng. Các tiến trình đang chạy vì 1 lý do nào đó có thể chuyển sang Blocked 6/28/2014 Chương 2. Quản lý tiến trình 19
  20. TỔ CHỨC VÀ QUẢN LÝ TIẾN TRÌNH 2.2.3 Các trạng thái của tiến trình  Tiến trình 4 trạng thái: Ready,Running,Blocked,Suspend Suspend là trạng thái của một tiến trình khi nó đang được lưu trữ trên bộ nhớ phụ, là các tiến trình đang ở trong trạng thái blocked hoặc ready bị HĐH chuyển ra đĩa để thu hồi lại không gian nhớ đã cấp hoặc thu hồi lại tài nguyên đã cấp để cấp cho một tiến trình khác đang rất cần được nạp vào bộ nhớ tại thời điểm hiện tại New Ready Running Activate End Suspend Blocked Suspend 6/28/2014 Chương 2. Quản lý tiến trình 20

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản