›

Giáo trình Công nghệ thông tin - Chương 2: Quản lí tiến trình

pdf 159 trang huongle 3060
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Công nghệ thông tin - Chương 2: Quản lí tiến trình", để 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:

  • pdfgiao_trinh_cong_nghe_thong_tin_chuong_2_quan_li_tien_trinh.pdf

Nội dung text: Giáo trình Công nghệ thông tin - Chương 2: Quản lí tiến trình

  1. 1. Tiếntrình „ Khái niệmvề tiếntrình „ Lậplịch tiếntrình „ Các thao tác trên tiếntrình „ Hợp tác giữacáctiếntrình „ Luồng „ Truyền thông giữacáctiếntrình 3/12/2008 Nguyên lý Hệ điềuhành 2
  2. 1.1. Khái niệmvề tiếntrình „ Một HĐH thựchiệnnhiềuchương trình ‰ Hệ thống xử lý theo lô: công việc (job) ‰ Hệ thống chia sẻ thời gian: tác vụ(task) „ Ởđây chúng ta dùng tiến trình và công việc với cùng ý nghĩa 3/12/2008 Nguyên lý Hệ điềuhành 3
  3. Tiếntrình „ Chương trình đang đượcthựchiện ‰ Phầnvănbản ‰ Ngănxếp ‰ Phầndữ liệu ‰ Giá trị bộđếmchương trình, thanh ghi „ CPU xử lý tiếntrìnhtuầntự „ Thựcthể hoạt động ‰ vs. chương trình 3/12/2008 Nguyên lý Hệ điềuhành 4
  4. Cấutrúcbộ nhớ tiếntrình Nguyên lý Hệ điềuhành 5
  5. Trạng thái tiếntrình „ Tiến trình thay đổitrạng thái trong khi thựchiện ‰ New ‰ Running ‰ Waiting ‰ Ready ‰ Terminated „ Tạimộtthời điểmchỉ có mộttiếntrìnhở trạng thái running 3/12/2008 Nguyên lý Hệ điềuhành 6
  6. Trạng thái tiếntrình 3/12/2008 Nguyên lý Hệ điềuhành 7
  7. Khối điều khiểntiến trình (PCB) 3/12/2008 Nguyên lý Hệ điềuhành 8
  8. Chuyển đổi CPU giữacáctiếntrình 3/12/2008 Nguyên lý Hệ điềuhành 9
  9. 1.2. Lậplịch tiếntrình „ Mục đích của đachương trình ‰ Tăng tính tậndụng CPU „ Mục đích của phân chia thời gian ‰ Ngườidùngcóthể tương tác vớitiến trình trong lúc nó đang thựcthi ÆXử lý nhiềutiếntrình Æ Lậplịch tiếntrình 3/12/2008 Nguyên lý Hệ điềuhành 10
  10. Các hàng đợilậplịch tiếntrình „ Hàng đợi công việc ‰ Mộttậpcáctiếntrìnhtronghệ thống „ Hàng đợisẵnsàng ‰ Tậpcáctiến trình trong bộ nhớ trong, sẵn sàng và chỉ chờ thựchiện „ Hàng đợithiếtbị ‰ Tậpcáctiếntrìnhchờ mộtthiếtbị vào/ra „ Các tiếntrìnhditrútừ hàng đợinàyđến hàng đợi khác 3/12/2008 Nguyên lý Hệ điềuhành 11
  11. Hàng đợisẵnsàngvàcáchàngđợithiết bị khác nhau 3/12/2008 Nguyên lý Hệ điềuhành 12
  12. Biểudiễnviệclậplịch tiếntrình-Biểu đồ hàng đợi 3/12/2008 Nguyên lý Hệ điềuhành 13
  13. Vòng đờicủamộttiếntrình ‰ Khởitạo: hàng đợisẵnsàng ‰ Các sự kiệncóthể xảyrakhitiếntrìnhđã được gán CPU „ Sinh ra mộtyêucầu I/O, đi vào hàng đợi I/O „ Tạoramộttiến trình con và đợi cho nó kết thúc „ Bị tước quyềnsử dụng CPU ‰ Tiếptụcvònglặp đếnkhikết thúc „ Bị xóa khỏitấtcả các hàng đợi „ PCB và tấtcả các tài nguyên bị thu hồi. 3/12/2008 Nguyên lý Hệ điềuhành 14
  14. Các bộ lậplịch „ Tiếntrìnhlưutrútrongnhiềuloại hàng đợi ‰ Các bộ lậplịch chọncáctiếntrìnhtừ các hàng đợi 3/12/2008 Nguyên lý Hệ điềuhành 15
  15. Các bộ lậplịch (tt) „ Bộ lậplịch dài hạn ‰ Lậplịch công việc – job scheduler ‰ Chọncáctiến trình trong tậptiếntrìnhvàtảinó vào bộ nhớđểthựchiện. „ Bộ lậplịch ngắnhạn(lậplịch CPU) ‰ Chọntrongsố các tiến trình trong hàng đợisẵn sàng để thựchiện. 3/12/2008 Nguyên lý Hệ điềuhành 16
  16. Bộ lậplịch ngắnhạnvs. dàihạn „ Tầnsố thựcthi ‰ Ngắnhạn: „ Thường xuyên „ Đòi hỏithực thi nhanh ‰ Dài hạn: „ Không thường xuyên bằng „ Thể hiệnmức độ “đachương trình” 3/12/2008 Nguyên lý Hệ điềuhành 17
  17. Bộ lậplịch dài hạn „ Hai loạitiếntrình: ‰ GiớihạnI/O ‰ GiớihạnCPU „ Chọnmộtkếthợptốtcáctiếntrìnhgiớihạn vào/ra và các tiến trình giớihạnCPU. „ Mộtsố hệ thống phân chia thời gian không có bộ lậplịch dài hạn (Unix) 3/12/2008 Nguyên lý Hệ điềuhành 18
  18. Bộ lậplịch trung hạn „ Sử dụng trong mộtsố HĐH phân chia thời gian 3/12/2008 Nguyên lý Hệ điềuhành 19
  19. Chuyển đổingữ cảnh „ Chuyển đổiCPU chomộttiếntrìnhkhác ‰ Ngữ cảnh tiếntrình „ Hoạt động chuyển đổingữ cảnh ‰ Kernel lưulạingữ cảnh củatiếntrìnhcũ trong PCB và tảingữ cảnh đượclưucủatiếntrìnhmới đượclậplịch 3/12/2008 Nguyên lý Hệ điềuhành 20
  20. Chuyển đổingữ cảnh (tt) „ Thời gian chuyển đổingữ cảnh: lãng phí ‰ Phụ thuộc vào máy, thông thường từ 1 đến 1000 micro giây ‰ Phụ thuộcvàosự hỗ trợ củaphầncứng ‰ Các kĩ thuậtquảnlýbộ nhớ ‰ Bottleneck Æ sử dụng các cấutrúcmớinhư thread để tránh nút cổ chai này 3/12/2008 Nguyên lý Hệ điềuhành 21
  21. 1.3. Các thao tác trên tiếntrình „ Tạotiếntrình „ Hủytiếntrình 3/12/2008 Nguyên lý Hệ điềuhành 22
  22. Tạotiếntrình „ Mộttiếntrìnhcóthể tạoranhiềutiếntrình con, qua lờigọihệ thống create_process ‰ Tiếntrìnhcha ‰ Tiếntrìnhcon 3/12/2008 Nguyên lý Hệ điềuhành 23
  23. Cây tiếntrình 3/12/2008 Nguyên lý Hệ điềuhành 24
  24. Tạotiến trình(tt) „ Chia sẻ tài nguyên ‰ Tấtcả các tài nguyên ‰ Mộtphần tài nguyên ‰ Không chia sẻ tài nguyên „ Thựcthi ‰ Thựcthiđồng thời ‰ Tiếntrìnhtuầntự 3/12/2008 Nguyên lý Hệ điềuhành 25
  25. Tạotiến trình trong Unix „ Mỗitiến trình có mộtID (PID) „ Gọilờigọihệ thống fork() để tạotiếntrình mới ‰ Tiến trình cha có thểđợihoặcthựchiện đồng thời vớitiếntrìnhcon ‰ Không gian địachỉ củatiến trình con là mộtBẢN SAO của không gian địachỉ tiếntrìnhcha ‰ Mã trả về từ fork() ‰ Tiến trình con có thể gọilờigọihệ thống execlp() để tảimộtchương trình mớivàothựchiện 3/12/2008 Nguyên lý Hệ điềuhành 26
  26. 3/12/2008 Nguyên lý Hệ điềuhành 27
  27. Hủytiếntrình „ Tiếntrìnhthựcthixong ‰ HĐH thựchiệnlệnh exit ‰ (có thể) trả về dữ liệuchotiếntrìnhcha ‰ Hủy các tài nguyên đã được phân phốichotiếntrình „ Tiếntrìnhbị hủybởimộttiến trình khác (tiếntrình cha) ‰ Tiến trình cha cầnbiếtchỉ số củatiếntrìnhcon 3/12/2008 Nguyên lý Hệ điềuhành 28
  28. Hủytiến trình (tt) „ Tiến trình cha dừng sự hoạt động củatiếntrìnhcon vì ‰ Tiến trình con dùng quá tài nguyên cho phép ‰ Nhiệmvụ củatiến trình con không còn quan trọng ‰ Tiến trình cha thoát và HĐH thựcthicơ chế “hủy theo dây chuyền”(cascading termination) „ Không thựchiệncơ chế hủy theo dây chuyền, tiến trình init thành tiếntrìnhcha 3/12/2008 Nguyên lý Hệ điềuhành 29
  29. 1.4. Hợptácgiữacáctiếntrình „ Các tiếntrìnhcộng tác ‰ Tiếntrìnhđộclập „ Không bịảnh hưởng bởitiến trình khác „ Không chia sẻ dữ liệu ‰ Tiếntrìnhhợptác „ Bịảnh hưởng bởitiến trình khác „ Dùng chung dữ liệu „ Cầncáckĩ thuật giao tiếp/ đồng bộ tiếntrình 3/12/2008 Nguyên lý Hệ điềuhành 30
  30. Vì sao hợptáctiến trình? „ Chia sẻ thông tin ‰ Đồng thờitruycập đến tài nguyên chia sẻ „ Tăng tốc độ tính toán ‰ Chia thành các bài toán con, thực thi song song ‰ Chỉ có đượctrongcáchệ thống có nhiều thành phầnxử lý (đaCPU, đa kênh vào/ra) „ Tính module hóa: Chia nhỏ các chứcnăng „ Tiệndụng ‰ Có thể thựchiện nhiều nhiệmvụ tạimộtthời điểm 3/12/2008 Nguyên lý Hệ điềuhành 31
  31. Bài toán “Producer - Consumer” (1) „ Nhà sảnxuất (producer) ‰ Sinh sảnphẩm (thông tin) „ Người tiêu dùng (consumer) ‰ Dùng thông tin do Nhà sảnxuấtsinhra „ Bộđệm chung ‰ Không giớihạn ‰ Giớihạn ‰ Hỗ trợ bởihệđiềuhành(thôngqua IPC) ‰ Do lậptrìnhviêntạorabằng cách sử dụng bộ nhớ chia sẻ 3/12/2008 Nguyên lý Hệ điềuhành 32
  32. BàitoánProducer –Consumer(2) „ Các biếnchiasẻ 3/12/2008 Nguyên lý Hệ điềuhành 33
  33. BàitoánProducer –Consumer (3) „ Mã cho Producer 3/12/2008 Nguyên lý Hệ điềuhành 34
  34. BàitoánProducer –Consumer (4) „ Mã lệnh cho Consumer 3/12/2008 Nguyên lý Hệ điềuhành 35
  35. 1.5. Truyền thông giữacáctiếntrình „ Các tiếntrìnhcóthể giao tiếp thông qua tính năng truyền thông giữacáctiến trình (IPC) của HĐH „ IPC cho phép các tiến trình không gian địa chỉ giao tiếpvàđồng bộ „ Hệ thống truyền thông báo 3/12/2008 Nguyên lý Hệ điềuhành 36
  36. Hệ thống truyền thông báo (1) „ Giao tiếpgiữacáctiếntrìnhngườidùng không cầnchiasẻ dữ liệu mà thông qua việc truyền thông báo „ Hai thao tác chính ‰ Gửi ‰ Nhận 3/12/2008 Nguyên lý Hệ điềuhành 37
  37. Hệ thống truyền thông báo (2) „ Thông báo ‰ Kích thướccốđịnh ‰ Kích thước thay đổi „ Hai tiến trình P & Q truyền thông bằng cách gửivànhận thông báo ‰ Tạo thành mộtkếtnốitruyền thông 3/12/2008 Nguyên lý Hệ điềuhành 38
  38. Hệ thống truyền thông báo (3) „ Các phương pháp để thiếtlập liên kếtvàcác thao tác gửi/nhận ‰ Truyền thông trựctiếp/ gián tiếp ‰ Truyền thông đốixứng/ bất đốixứng ‰ Gửibản sao hay gửi tham chiếu ‰ Các thông điệpkíchthướccốđịnh hoặcthayđổi 3/12/2008 Nguyên lý Hệ điềuhành 39
  39. Định danh Các tiếntrìnhmuốn giao tiếpvới nhau cầncó mộ tcáchthức để tham chiếu đế n nhau! 3/12/2008 Nguyên lý Hệ điềuhành 40
  40. Truyền thông trựctiếp(1) „ Phải khai báo tên củangườinhận/gửitrongkhigiao tiếp ‰ send (P, message) ‰ receive (Q, message) „ Tính chất ‰ Tựđộng thiếtlập liên kếtkhicầngiaotiếp ‰ Mỗi liên kếtcóđúng hai tiếntrình ‰ Có đúng một liên kếtgiữabấtkì2 cặptiếntrình 3/12/2008 Nguyên lý Hệ điềuhành 41
  41. Truyền thông trựctiếp(2) „ Hệ thống vừaxét: đốixứng địachỉ „ Hệ thống bất đốixứng địachỉ ‰ Chỉ có ngườigửi định danh ngườinhận ‰ Ngườinhận không cần định danh ngườigửi „ Send(P, message) „ Receive(id, message) ‰ Thay đổitênmộttiếntrìnhÆ duyệtlạitoànbộ các tiếntrình 3/12/2008 Nguyên lý Hệ điềuhành 42
  42. Truyền thông gián tiếp(1) „ Gửivànhận thông qua hòm thư hoặccổng „ Mỗihòmthư có mộtsốđịnh danh „ Các thao tác gửi/nhận ‰ Send(A, message) – A là hòm thư ‰ Receive(A, message) – nhậnmột thông báo từ hòm thư A 3/12/2008 Nguyên lý Hệ điềuhành 43
  43. Truyền thông gián tiếp(2) „ Tính chất ‰ Mộtliênkết đượcthiếtlậpgiữahaitiếntrìnhchỉ khi cả hai là thành viên củamột hòm thư ‰ Mộtliênkếtcóthể có nhiềuhơn hai tiếntrình ‰ Giữa hai tiếntrìnhcóthể có nhiều liên kết 3/12/2008 Nguyên lý Hệ điềuhành 44
  44. Đồng bộ hóa „ Truyền thông báo có thể là phong tỏa hay không phong tỏa(đồng bộ hoặc không đồng bộ) ‰ Phong tỏagửi ‰ Không phong tỏagửi ‰ Phong tỏanhận ‰ Không phong tỏanhận 3/12/2008 Nguyên lý Hệ điềuhành 45
  45. Lưutrữ bộđệm „ Hàng đợitạm: các cách thiếtkế ‰ Zero capacity ‰ Bounded capacity ‰ Unbounded capacity 3/12/2008 Nguyên lý Hệ điềuhành 46
  46. 1.6. Luồng „ Tạisaođaluồng? ‰ Trình duyệtWeb „ Hiểnthịảnh, hoặcvănbản „ Nhậndữ liệutừ mạng ‰ Trình word „ Hiểnthị vănbản „ Đọckítự từ người dùng „ Thựchiệnkiểmtrangữ pháp và chính tả ngầm 3/12/2008 Nguyên lý Hệ điềuhành 47
  47. Tiếntrìnhđơnluồng và tiếntrìnhđa luồng 3/12/2008 Nguyên lý Hệ điềuhành 48
  48. Tạisaođaluồng? (2) „ Một ứng dụng đơncầnthựchiệnmộtsố nhiệmvụ tương tựđồng thời ‰ Ví dụ: Máy chủ web „ Giải pháp đatiếntrìnhtrước đây ‰ Nặng nề hơn ‰ Lãng phí do các tiếntrìnhcùngthựchiệnmộtsố nhiệmvụ tương tự 3/12/2008 Nguyên lý Hệ điềuhành 49
  49. Lợiích „ Tính đáp ứng „ Chia sẻ tài nguyên „ Kinh tế ‰ Phân phối tài nguyên và bộ nhớ cho tiếntrìnhtốn kém „ Tậndụng các kiếntrúcđaxử lý 3/12/2008 Nguyên lý Hệ điềuhành 50
  50. Luồng mứcngười dùng (User-Thread) „ Quảnlýluồng đượcthựchiệnbởithư viện luồng ở mứcngười dùng „ Examples -POSIX Pthreads -Mach C-threads - Solaris threads 3/12/2008 Nguyên lý Hệ điềuhành 51
  51. Luồng mức nhân „ Hỗ trợ trựctiếpbởihệđiều hành „ Examples - Windows 95/98/NT/2000 - Solaris - Tru64 UNIX -BeOS - Linux 3/12/2008 Nguyên lý Hệ điềuhành 52
  52. Các mô hình đaluồng „ Mô hình Many-to-One „ Mô hình One-to-One „ Mô hình Many-to-Many 3/12/2008 Nguyên lý Hệ điềuhành 53
  53. Mô hình Many-to-One 3/12/2008 Nguyên lý Hệ điềuhành 54
  54. Mô hình One-to-One 3/12/2008 Nguyên lý Hệ điềuhành 55
  55. Mô hình Many-to-Many 3/12/2008 Nguyên lý Hệ điềuhành 56
  56. Pthreads „ Chuẩn Posix (IEEE 1003.1c), API cho việc tạovàđồng bộ tiếntrình „ API xác định giao diệncủathư viện,thựcthi tùy thuộc vào cài đặtthư viện. „ Phổ biến trong dòng hệđiều hành Unix. 3/12/2008 Nguyên lý Hệ điềuhành 57
  57. 3/12/2008 Nguyên lý Hệ điềuhành 58
  58. 2. Lậplịch CPU „ Các khái niệmcơ bản „ Điềukiệnlậplịch „ Các thuậttoánlậplịch 3/12/2008 Nguyên lý Hệ điềuhành 59
  59. 2.1. Các khái niệmcơ bản „ Tậndụng tối đa CPU trong đachương trình „ Chu kỳ của các CPU-I/O burst – Việcthựcthi tiến trình là một chu kì củacácthựcthibởi CPU và chờđợivàora „ Phân phốiCPU burst 3/12/2008 Nguyên lý Hệ điềuhành 60
  60. Luân phiên giữa các CPU và I/O burst 3/12/2008 Nguyên lý Hệ điềuhành 61
  61. Biểu đồ tầnsuấtcủa các CPU burst theo thờigian 3/12/2008 Nguyên lý Hệ điềuhành 62
  62. Bộ lậplịch CPU „ Chọn trong số các tiếntrìnhtrongbộ nhớ trong và ở trạng thái ready để thựchiện (trao quyềnsử dụng CPU cho tiếntrìnhđó) „ Việclậplịch có thểđượcthựchiện trong mộtsố trường hợp 1. Tiếntrìnhtrạng thái running chuyển sang waiting 2. Tiếntrìnhtrạng thái running chuyển sang trạng thái ready 3. Có mộttiếntrìnhở trạng thái waiting chuyển sang trạng thái ready 4. Tiến trình hiệntạikết thúc thựcthi „ Lậplịch trong chỉ trong các trường hợp 1 và 4 gọilàlậplịch không chiếm đoạt (hay còn gọilàcộng tác) „ Các trường hợpcònlạigọilàlậplịch chiếm đoạt 3/12/2008 Nguyên lý Hệ điềuhành 63
  63. Bộđiềuvận „ Bộđiềuvậncónhiệmvụ chuyển điềukhiểnCPU cho tiếntrìnhđượclựachọnbởibộ lậplịch ngắn hạn „ Chứcnăng củabộđiềuvận bao gồm ‰ Chuyển đổingữ cảnh ‰ Chuyển sang user mode ‰ Chuyển điềukhiển đếnmộtvị trí xác định trong chương trình người dùng để khởi động lạichương trình „ Độ trễđiềuvận ‰ Thờigiandừng mộttiếntrìnhđể bắt đầuthựcthitiếntrình khác 3/12/2008 Nguyên lý Hệ điềuhành 64
  64. 2.2. Điềukiệnlậplịch „ Tính tậndụng CPU ‰ Thông thường từ 40-90% „ Thông lượng „ Thời gian quay vòng (turnaround time) „ Thời gian chờ „ Thời gian phản ứng 3/12/2008 Nguyên lý Hệ điềuhành 65
  65. Vấn đề tối ưucácđiềukiện „ Cực đại hóa tính tậndụng CPU „ Cực đại hóa thông lượng „ Cựctiểuhóathời gian quay vòng „ Cựctiểuhóathời gian đợi „ Cựctiểuhóathời gian phản ứng 3/12/2008 Nguyên lý Hệ điềuhành 66
  66. 2.3. Các thuậttoánlậplịch „ Đếntrước–Phụcvụ trước(FCFS) „ Công việcngắnnhấttrước (SJF) „ Lậplịch với độ ưutiên „ Lậplịch Round-Robin(RR) „ Lậplịch đa hàng đợi „ Lậplịch với hàng đợiphảnhồi 3/12/2008 Nguyên lý Hệ điềuhành 67
  67. “Đếntrước–Phụcvụ trước” (FCFS) „ Ba tiếntrìnhđếntheothứ tự là P1, P2, P3 ‰ ThờigianthựchiệncủaP1, P2 vàP3 lầnlượtlà 24, 3 và 3 „ Biểu đồ Gantt trong lậplịch FCFS P1 P2 P3 0 24 27 30 „ Thời gian chờ của P1 = 0; P2= 24; P3 = 27 „ Thời gian chờ trung bình: (0 + 24 + 27)/3= 17 3/12/2008 Nguyên lý Hệ điềuhành 68
  68. “Đếntrước–Phụcvụ trước” (FCFS) (tt) „ Nếucáctiếntrìnhđến theo thứ tự P2, P3, P1 „ Biểu đồ Gantt cho lậplịch P2 P3 P1 0 3 6 30 „ Thời gian chờ của P1 = 6; P2 = 0; P3 = 3 „ Thời gian chờ trung bình: (6 + 0 + 3)/3 = 3 „ Tốthơnnhiềuso vớitrường hợptrên „ Convoy effect 3/12/2008 Nguyên lý Hệ điềuhành 69
  69. Công việcngắnnhấttrước(SJF) „ Liên kếtmỗitiếntrìnhđộ dài của “CPU burst” tiếp theo. Sử dụng độ dài này để lậplịch tiếntrìnhvới thờigianngắnnhất. „ Hai dạng ‰ Không chiếm đoạt–MộtkhiCPU đã đượcgánchotiến trình, CPU không thể bị chiếm đoạtbởimộttiến trình nào khác. ‰ Chiếm đoạt–Nếumộttiếntrìnhmới đếnvới độ dài CPU burst nhỏ hơnthờigianthựcthicònlạicủatiếntrìnhsở hữu CPU, tiếntrìnhmới đượcchiếmhữaCPU –Dạng “Thờigiancònlạingắnnhấttrước” (SRJF) „ SJF tối ưuthờigianchờ 3/12/2008 Nguyên lý Hệ điềuhành 70
  70. SJF không chiếm đoạt: Ví dụ „ SJF (không chiếm đoạt) P1 P3 P2 P4 0 3 7 8 12 16 „ Thời gian chờ trung bình:(0 + 6 + 3 + 7)/4 = 4 3/12/2008 Nguyên lý Hệ điềuhành 71
  71. SJF chiếm đoạt: Ví dụ „ SJF (chiếm đoạt) P1 P2 P3 P2 P4 P1 0 2 4 5 7 11 16 „ Thời gian chờ trung bình= (9 + 1 + 0 + 2)/4=3 3/12/2008 Nguyên lý Hệ điềuhành 72
  72. Xác định độ dài của CPU burst tiếptheo „ Ướclượng độ dài nhờđộdài của các CPU burst trước đó th 1. actual tn = lenght n of CPU burst 2. predicted τ n+1 = value for the next CPU burst 3. α , α≤ 0 ≤ 1 4. Defineτ n=1 = α : tn + 1( −α )τ n . 3/12/2008 Nguyên lý Hệ điềuhành 73
  73. Xác định độ dài của CPU burst tiếptheo 3/12/2008 Nguyên lý Hệ điềuhành 74
  74. Lậplịch với độ ưu tiên „ Mỗitiến trình liên kếtvớimột độ ưutiên(số nguyên) xác định „ CPU được phân phốichotiếntrìnhvới độ ưutiên cao nhất(giátrịđộưutiếnnhỏ nhất) ‰ Chiếm đoạt ‰ Không chiếm đoạt „ SJF là lậplịch với độ ưutiêntrongđó độ ưutiên chính là khoảng CPU burst tiếptheo „ Vấn đề: “Chết đói” – Những tiếntrìnhvới độ ưutiên thấpcóthể sẽ không bao giờđược gán CPU ‰ Giải pháp: các tiếntrìnhtăng độ ưutiêntheothờigian 3/12/2008 Nguyên lý Hệ điềuhành 75
  75. Round Robin (RR) „ Mỗitiếntrìnhđược gán mộtlượng tử thời gian (thường từ 10 – 100 mili giây) „ Hếtlượng tử thời gian, tiếntrìnhhiệntạibị tướcCPU vàđặt vào hàng đợisẵn sàng „ Hiệunăng ‰ FIFO ‰ Q phải đủ lớnso vớithời gian chuyểngiaongữ cảnh 3/12/2008 Nguyên lý Hệ điềuhành 76
  76. Ví dụ: RR vớilượng tử thờigian= 20 Process Burst Time P 53 1 P2 17 P3 68 P4 24 „ Biểu đồ Gantt: P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 RR có thời gian quay vòng trung bình cap hơn SJF nhưng có tính phản ứng tốthơn 3/12/2008 Nguyên lý Hệ điềuhành 77
  77. Thờigianlượng tử và thời gian chuyển đổingữ cảnh 3/12/2008 Nguyên lý Hệ điềuhành 78
  78. Biến đổithời gian quay vòng theo thời gian lượ ng tử 3/12/2008 Nguyên lý Hệ điềuhành 79
  79. Lậplịch vớiHàngđợi nhiềumức „ Sử dụng nhiềuhơnmột hàng đợisẵnsàng ‰ Ví dụ: hàng đợinềntrước(foreground queue) cho các chương trình tương tác, hàng đợinềnsau(background) cho các chương trình duy trì hệ thống, các chương trình theo lô „ Sử dụng các thuậttoánlậplịch khác nhau cho các hàng đợi ‰ Ví dụ: RR cho hàng đợinềntrước, FCFS „ Chia thời gian cho các hàng đợi ‰ Ví dụ: 80% thời gian cho hàng đợinềntrước, 20% cho nền sau 3/12/2008 Nguyên lý Hệ điềuhành 80
  80. Hàng đợi nhiềumức 3/12/2008 Nguyên lý Hệ điềuhành 81
  81. Hàng đợi nhiềumứcphảnhồi „ Không cốđịnh tiến trình trên mộthàngđợi „ Ví dụ: các hàng đợivớicácđộ ưutiênkhác nhau ‰ Các tiếntrìnhgắnvớiVào/Ra ở hàng đợicóđộ ưutiêncao ‰ Chuyểncáctiếntrìnhsử dụng CPU đến các hàng đợicóđộ ưutiênthấp ‰ Chuyểncáctiếntrìnhphải đợilâuđều đặnlên phía trên 3/12/2008 Nguyên lý Hệ điềuhành 82
  82. Lậplịch các luồng trong Java „ JVM sử dụng thuật toán Preemptive, và dựatrênđộ ưutiêntronglậplịch „ Hàng đợiFIFO đượcsử dụng nếucó nhiềuluồng cùng mức ưutiên 3/12/2008 Nguyên lý Hệ điềuhành 83
  83. Lậplịch các luồng trong Java JVM lậplịch khi: 1. Tiếntrìnhđang chạyrakhỏitrạng thái runnable 2. M ộttiếntrìnhcóđộ ưutiêncaohơnvàotr ạng thái runnable 3/12/2008 Nguyên lý Hệ điềuhành 84
  84. Time-Slicing Do JVM không hỗ trợ cắtthời gian (Time- Slicing), hàm yield() có thểđượ cs ử dụng: while (true) { // perform CPU-intensive task . . . Thread.yield(); } Thread.yield()chuyển điềukhiểncho luồng khác 3/12/2008 Nguyên lý Hệ điềuhành 85
  85. Các độ ưu tiên củaluồng Priority Ý nghĩa Thread.MIN_PRIORITY Nhỏ nhất Thread.MAX_PRIORITY Lớnnh ất Thread.NORM_PRIORITY Ngầm định Phương thức setPriority() setPriority(Thread.NORM_PRIORIT Y + 2) 3/12/2008 Nguyên lý Hệ điềuhành 86
  86. Nội dung đãhọc „ Lý do lậplịch „ Các dạng lậplịch ‰ FCFS ‰ SJF ‰ RR ‰ MFQ „ Lậplịch trong Java 3/12/2008 Nguyên lý Hệ điềuhành 87
  87. 3. Đồng bộ hóa tiếntrình „ Nềntảng „ Vấn đề “Đoạntớihạn” „ Giải pháp của Peterson „ Đồng bộ nhờ phầncứng „ Semaphores „ 3 bài toán đồng bộđiểnhình „ Monitors 3/12/2008 Nguyên lý Hệ điềuhành 88
  88. 3.1. Nềntảng „ Truy nhập đồng thời đếndữ liệuchiasẻ có thể gây ra sự không nhất quán về dữ liệu ÆCầncáckĩ thuật để việcthựcthituầntự củacác tiếntrìnhcộng tác „ Vấn đề cộng tác tiếntrình(phần1) ‰ Bài toán “Sảnxuất – Tiêu dùng” ‰ Bộ nhớ chia sẻ (có giớihạn) ‰ Biến count lưusố các items trong buffer 3/12/2008 Nguyên lý Hệ điềuhành 89
  89. Mã nguồn cho Producer và Consumer „ Producer „ Consumer while (true) while (1) { { //produce an item while (count == 0) while (count == BUFFER_SIZE); ; // do nothing // do nothing nextConsumed = buffer[out]; buffer [in] = nextProduced; out = (out + 1) % in = (in + 1) % BUFFER_SIZE; BUFFER_SIZE; count++; count ; /*consume the item in } } 3/12/2008 Nguyên lý Hệ điềuhành 90
  90. Chạy đua „ count++ có thểđượcthựchiệnnhư sau register1 = count register1 = register1 + 1 count = register1 „ count– có thểđượcthựchiệnnhư sau register2 = count register2 = register2 - 1 count = register2 „ Giả sử ban đầu “count = 5”: S0: producer thựcthiregister1 = count {register1 = 5} S1: producer thựcthiregister1 = register1 + 1 {register1 = 6} S2: consumer thựcthiregister2 = count {register2 = 5} S3: consumer thựcthiregister2 = register2 - 1 {register2 = 4} S4: producer thựcthicount = register1 {count = 6 } S5: consumer thựcthicount = register2 {count = 4} 3/12/2008 Nguyên lý Hệ điềuhành 91
  91. Chạy đua „ Chạy đua: Tình huống nhiềutiến trình cùng truy cậpvàxử lý dữ liệudùngchungđồng thời. Giá trị cuốicùngcủadữ liệuphụ thuộcvàotiếntrìnhsẽ kết thúc cuối. „ Để tránh việcchạy đua, các tiếntrìnhđồng thờicần phải được đồng bộ hóa 3/12/2008 Nguyên lý Hệ điềuhành 92
  92. 3.2. Vấn đề đoạntớihạn „ n tiếntrìnhcùngmuốntruycập đếndữ liệuchiasẻ „ Mỗitiếntrìnhcómột đoạnmãgọilà“đoạntớihạn”, trong “đoạntớihạn”dữ liệuchiasẻ mới đượctruy cậptới. „ Vấn đề - đảmbảorằng khi mộttiếntrìnhđang trong đoạntớihạncủa nó, các tiến trình khác không được phép thựcthiđoạntớihạncủa chúng. 3/12/2008 Nguyên lý Hệ điềuhành 93
  93. Giải pháp cho vấn đề “đoạntớihạn” 1. Loạitrừ lẫn nhau. NếutiếntrìnhPi đang trong đoạntớihạn, không tiến trình nào khác được phép ở trong đoạntớihạn. 2. Phát triển. Nếu không tiến trình nào ở trong đoạntớihạnvàcómột số tiếntrìnhmuốnvàođoạntớihạn, việclựachọnmộttiếntrìnhvào đoạ ntớih ạnsẽ không bị trì hoãn mãi. 3. Chờđợicócận. Phảicómộtcậnvề số lầnmàcáctiến trình khác được phép vào đoạntớihạnsaukhimộttiếntrìnhđãyêucầuvào đoạ ntớihạnvàtrướckhiyêucầu đó đượ c đ áp ứng. Giả thiếtrằng mỗitiếntrìnhthựcthivớitốc độ khác không y y Không có giả thiếtvề mốitương quan tốc độ của n tiến trình. 3/12/2008 Nguyên lý Hệ điềuhành 94
  94. 3.3. Giải pháp của Peterson „ Giải pháp đồng bộ cho hai tiếntrình „ Giả sử hai lệnh LOAD và STORE là các lệnh nguyên tử (thao tác không thể phân chia) „ Các tiếntrìnhchiasẻ các biến sau: ‰ int turn; ‰ Boolean flag[2] „ Biến turn cho biếttiếntrìnhnàođượcvàođoạntới hạn. „ Mảng flag chỉ xem liệumộttiếntrìnhcósẵnsàng vào đoạntớihạn hay không. ‰ flag[i] = true là tiếntrìnhPi sẵn sàng vào đoạntớihạn! 3/12/2008 Nguyên lý Hệ điềuhành 95
  95. Thuật toán cho tiến trình P i do { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j); CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION } while (TRUE); 3/12/2008 Nguyên lý Hệ điềuhành 96
  96. 3.4. Đồng bộ hóa nhờ phầncứng „ Nhiềuhệ thống cung cấpsự hỗ trợ củaphầncứng cho vấn đề đoạntớihạn „ Các hệđơnxử lý – có thể bỏ chứcnăng ngắt ‰ Mã đượcthực thi mà không có sự chiếm đoạt ‰ Thông thường không hiệuquả trên các hệ thống đaxử lý „ Các hệđiều hành vớichiếnlược này thường không khả cỡ „ Các máy tính hiện đạicungcấpcáclệnh phầncứng nguyên tử „ Nguyên tử = không phân chia ‰ Kiểmtratừ nhớ và thiếtlậpgiátrị ‰ Tráo đổinội dung của hai từ nhớ 3/12/2008 Nguyên lý Hệ điềuhành 97
  97. Lệnh TestAndSet „ Định nghĩa: boolean TestAndSet (boolean *target) { boolean rv = *target; *target = TRUE; return rv: } 3/12/2008 Nguyên lý Hệ điềuhành 98
  98. Giải pháp dùng TestAndSet „ Biếnchiasẻ lock, đượckhởitạobằng false „ Giải pháp: do { while ( TestAndSet (&lock )) ; /* do nothing // critical section lock = FALSE; // remainder section } while ( TRUE); 3/12/2008 Nguyên lý Hệ điềuhành 99
  99. Lệnh Swap „ Định nghĩa: void Swap (boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp: } 3/12/2008 Nguyên lý Hệ điềuhành 100
  100. Giải pháp dùng Swap „ Biếnchiasẻ lock, đượckhởitạobằng false; mỗitiếntrìnhcómộtbiến Boolean cụcbộ „ Giải pháp: do { key = TRUE; while ( key == TRUE) Swap (&lock, &key ); // critical section lock = FALSE; // remainder section } while ( TRUE); 3/12/2008 Nguyên lý Hệ điềuhành 101
  101. 3.5. Semaphores „ Công cụđồng bộ không đòi hỏi“chờ-bận” „ Semaphore S – biến nguyên „ Hai thao tác “nguyên tử” để sửa đổiS: wait (S) { signal (S) { while S <= S++; 0; } // no-op S ; } 3/12/2008 Nguyên lý Hệ điềuhành 102
  102. Semaphore –Côngcụđồng bộ tổng quát „ Hai loại semaphore ‰ Semaphore đếm „ Giá trị của semaphore là số các tài nguyên available ‰ Semaphore nhị phân „ Semaphore chỉ nhận hai giá trị 0 và 1 „ Còn đượcgọilàmutex lock „ Loạitrừ lẫn nhau dùng semaphore ‰ Semaphore S; // initialized to 1 ‰ wait (S); Critical Section signal (S); 3/12/2008 Nguyên lý Hệ điềuhành 103
  103. Cài đặt Semaphore „ Cần đảmbảorằng không có hai tiếntrìnhnàocó thể cùng thựcthiwait() và signal() trên cùng 1 semaphore tại cùng 1 thời điểm „ Thực thi semaphore bản thân nó cũng là bài toán đoạntớihạn ‰ Mã cho wait() và signal() được đặt trong đoạntớihạn ‰ Có thể cài đặtcơ chế “chờ-bận”hoặc không „ Chờ-bận ‰ Mã nguồn đơngiản ‰ Chấpnhận đượctrongTH đoạntớihạnítkhiđượctruy nhậptới 3/12/2008 Nguyên lý Hệ điềuhành 104
  104. Cài đặt Semaphore không chờ-bận „ Mỗi semaphore liên kếtvớimột hàng đợi. Mỗiphầntử của hàng đợicóhaiphần ‰ Giá trị (kiểu nguyên) ‰ Con trỏđếnbảnghitiếp theo trong danh sách „ Hai thao tác: ‰ Block – đặttiếntrìnhgọi thao tác này vào hàng đợi semaphore. ‰ Wakeup – gỡ bỏ mộttrongsố các tiến trình trong hàng đợivàđặt nó vào hàng đợisẵnsàng 3/12/2008 Nguyên lý Hệ điềuhành 105
  105. Cài đặt Semaphore không chờ-bận „ Implementation of wait: „ Implementation of signal: Wait (S) Signal (S) { { value ; value++; if (value < 0) { if (value <= 0) { //add this process to waiting //remove a process P from //queue //the waiting queue block(); wakeup(P); } } 3/12/2008 Nguyên lý Hệ điềuhành 106
  106. Bế tắcvàChết đói „ Bế tắc – hai hay nhiềutiếntrìnhchờ vô hạntrênmột sự kiệngâyrabởimộttrongcáctiếntrìnhđang chờ „ S và Q là hai semaphores đượckhởitạobằng 1 P0 P1 wait (S); wait (Q); wait (Q); wait (S); . . . . . . signal (S); signal (Q); signal (Q); signal (S); „ Chết đói –bị block vô hạn. Mộttiếntrìnhcóthể bị gỡ khỏihàngđợicủa semaphore. 3/12/2008 Nguyên lý Hệ điềuhành 107
  107. 3.6. Các bài toán đồng bộ kinh điển „ Bộđệmgiớihạn „ Bài toán đọcvàghi „ Bài toán “bữa ăncủacáctriếtgia” 3/12/2008 Nguyên lý Hệ điềuhành 108
  108. Bài toán “Bộđệmgiớihạn” „ N bộđệm, mỗibộđệmcóitem „ Semaphore mutex đượckhởitạobằng 1 „ Semaphore full đượckhởitạobằng 0 „ Semaphore empty đượckhởitạobằng N. 3/12/2008 Nguyên lý Hệ điềuhành 109
  109. Bài toán “Bộđệmgiớihạn” „ Tiến trình “producer” „ Tiến trình “consumer” do { do { wait (full); // produce an item wait (mutex); wait (empty); // remove an item from buffer wait (mutex); signal (mutex); // add the item to the buffer signal (empty); signal (mutex); // consume the removed item signal (full); } while (true); } while (true); 3/12/2008 Nguyên lý Hệ điềuhành 110
  110. Bài toán “Đọc-ghi” „ Mộttậpdữ liệu đượcchiasẻ giữamộtsố tiếntrìnhđồng thời ‰ Reader – chỉđọcdữ liệu; không thựchiệnbấtkìmột thao tác cập nhật. ‰ Writers – có thể vừa đọcvừaghi. „ Vấn đề ‰ Cho phép nhiều reader đọc cùng mộtthời điểm. Chỉ có một writer có thể truy nhập đếndữ liệuchiasẻ tại cùng mộtthời điểm. „ Dữ liệuchiasẻ ‰ Tậpdữ liệu ‰ Semaphore mutex đượckhởitạobằng 1. ‰ Semaphore wrt đượckhởitạobằng 1. ‰ Số nguyên readcount đượckhởitạobằng 0. 3/12/2008 Nguyên lý Hệ điềuhành 111
  111. Bài toán “Đọc-ghi” „ Tiến trình ghi (writer) „ Tiếntrìnhđọc (reader) do { do { wait (wrt) ; wait (mutex) ; readcount ++ ; // writing is performed if (readercount == 1) wait (wrt) ; signal (mutex) signal (wrt) ; } while (true) // reading is performed wait (mutex) ; readcount - - ; if redacount == 0) signal (wrt) ; signal (mutex) ; } while (true) 3/12/2008 Nguyên lý Hệ điềuhành 112
  112. Bài toán “Bữa ăncủacáctriếtgia” „ Dữ liệuchiasẻ ‰ Cơm(tậpdữ liệu) ‰ Semaphore chopstick [5] đượckhởitạobằng 1 3/12/2008 Nguyên lý Hệ điềuhành 113
  113. Bài toán “Bữa ăncủacáctriếtgia” „ Mã lệnh cho Triếtgiathứ I Do { wait ( chopstick[i] ); wait ( chopStick[ (i + 1) % 5] ); // eat signal ( chopstick[i] ); signal (chopstick[ (i + 1) % 5] ); // think } while (true) ; 3/12/2008 Nguyên lý Hệ điềuhành 114
  114. Vấn đề của Semaphores „ Không sử dụng đúng các thao tác trên semaphore ‰ signal (mutex) . wait (mutex) ‰ wait (mutex) wait (mutex) ‰ Bỏ qua wait (mutex) hay signal (mutex) (hoặccả hai) 3/12/2008 Nguyên lý Hệ điềuhành 115
  115. 3.7. Monitors „ Trừutượng mức cao cung cấpphương thứchữuhiệuchođồng bộ tiếntrình „ Chỉ có mộttiếntrìnhchỉ có thể active trong monitor tạimộtthời gian monitor monitor-name { // shared variable declarations procedure P1 ( ) { . } procedure Pn ( ) { } Initialization code ( .) { } } } 3/12/2008 Nguyên lý Hệ điềuhành 116
  116. Monitor 3/12/2008 Nguyên lý Hệ điềuhành 117
  117. Các biến điềukiện „ condition x, y; „ Hai thao tác trên biến điềukiện: ‰ x.wait () –tiếntrìnhgọi thao tác này sẽ bị block. ‰ x.signal () –khôiphụcthựcthicủamột trong số các tiến trình (nếucó) đãgọi thao tác x.wait () 3/12/2008 Nguyên lý Hệ điềuhành 118
  118. Monitor vớicácbiến điềukiện 3/12/2008 Nguyên lý Hệ điềuhành 119
  119. Giải pháp cho bài toán “Bữa ăncủa các triếtgia” monitor DP { enum { THINKING; HUNGRY, void test (int i) { EATING) state [5] ; if ( (state[(i + 4) % 5] != EATING) condition self [5]; && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { void pickup (int i) { state[i] = HUNGRY; state[i] = EATING ; test(i); self[i].signal () ; } if (state[i] != EATING) self [i].wait; } } void putdown (int i) { initialization_code() { state[i] = THINKING; for (int i = 0; i < 5; i++) state[i] = THINKING; // test left and right neighbors test((i + 4) % 5); } test((i + 1) % 5); } } 3/12/2008 Nguyên lý Hệ điềuhành 120
  120. 4. Bế tắc „ Vấn đề “Bế tắc” „ Mô hình hệ thống „ Các đặc điểmcủabế tắc „ Các phương pháp xử lý bế tắc „ Ngănchặnbế tắc „ Tránh bế tắc „ Khôi phụcsaubế tắc 3/12/2008 Nguyên lý Hệ điềuhành 121
  121. 4.1. Vấn đề “Bế tắc” „ Mộttậpcáctiếntrìnhbị block, mỗitiếntrìnhgiữ một tài nguyên và chờ một tài nguyên bị chiếmgiữ bởi mộttiến trình khác trong tập „ Ví dụ ‰ Mộthệ thống có 2 băng từ ‰ P1 và P2 mỗitiến trình giữ mộtbăng từ và đòi hỏibăng từ đượcgiữ bởitiếntrìnhkia. „ Ví dụ ‰ semaphores A và B, đượckhởitạobằng 1 P0 P1 wait (A); wait(B) wait (B); wait(A 3/12/2008 Nguyên lý Hệ điềuhành 122
  122. 4.2. Mô hình hệ thống „ Các kiểu tài nguyên R1, R2, . . ., Rm CPU cycles, memory space, I/O devices „ Mỗi tài nguyên Ri có Wi thể hiện. „ Mỗitiếntrìnhsử dụng tài nguyên như sau: ‰ request ‰ use ‰ release 3/12/2008 Nguyên lý Hệ điềuhành 123
  123. 4.3. Các đặc điểmcủabế tắc „ Bế tắccóthể xảyranếucả bốn điềukiệnsauxảyra đồng thời ‰ Loạitrừ lẫnnhau: chỉ mộttiếntrìnhđượcsử dụng tài nguyên tạimộtthời điểm. ‰ Giữ và chờ: mộttiến trình giữ ít nhấtmột tài nguyên và chờ các tài nguyên khác đang đượcgiữ bởicáctiếntrình khác. ‰ Không chiếm đoạt: một tài nguyên chỉ có thểđượcgiải phóng mộtcáchtự nguyệnbởitiếntrìnhgiữ nó, sau khi tiếntrìnhđó hoàn thành công việccủa nó. ‰ Chờđợi vòng tròn: Mộttậpcáctiếntrìnhđang chờ {P0, P1, , Pn} , trong đó P0 chờ một tài nguyên bị giữ bởi P1, P1 chờ một tài nguyên bị giữ bởi P2, , Pn–1chờ mộttài nguyên đượcgiữ bởi Pn, và Pn đang chờ một tài nguyên P0. 3/12/2008 Nguyên lý Hệ điềuhành 124
  124. Đồ thị phân phối tài nguyên „ Có mộttậpcácđỉnh V và mộttậpcáccạnh E ‰ V được chia thành hai tập: „ P = {P1, P2, , Pn}, tậpchứatấtcả các tiếntrìnhtrong hệ thống. „ R = {R1, R2, , Rm}, tậpchứatấtcả các kiểu tài nguyên trong hệ thống. ‰ Cạnh request – cạnh có hướng P1 → Rj ‰ Cạnh assignment – cạnh có hướng Rj → Pi 3/12/2008 Nguyên lý Hệ điềuhành 125
  125. Đồ thị phân phối tài nguyên „ Tiếntrình „ Kiểu tài nguyên với4 thể hiện „ Pi yêu cầumộtthể hiệncủa Rj Pi Rj „ Pi giữ mộtthể hiệncủa Rj Pi Rj 3/12/2008 Nguyên lý Hệ điềuhành 126
  126. Ví dụ về một đồ thị phân phối tài nguyên 3/12/2008 Nguyên lý Hệ điềuhành 127
  127. Đồ thị phân phối tài nguyên vớimộtbế tắc 3/12/2008 Nguyên lý Hệ điềuhành 128
  128. Đồ thị vớimộtchutrìnhnhưng không có bế tắc 3/12/2008 Nguyên lý Hệ điềuhành 129
  129. Tiên đề „ Nếumột đồ thị không có chu trình ⇒ không có bế tắc. „ Nếu đồ thị có một chu trình ⇒ ‰ Nếumỗi tài nguyên chỉ có mộtthể hiệnthìxuất hiệnbế tắc. ‰ Nếumỗiloại tài nguyên có mộtvàithể hiệnthìcó thể có bế tắc. 3/12/2008 Nguyên lý Hệ điềuhành 130
  130. 4.4. Các phương pháp xử lý bế tắc „ Đảmbảohệ thống sẽ không bao giờ đivào trạng thái bế tắc „ Cho phép hệ thống vào trạng thái bế tắcsau đókhôiphục „ Bỏ qua vấn đề này và xem rằng bế tắc không bao giờ xảy ra trong hệ thống; đượcsử dụng bởihầuhếtcáchệđiều hành, bao gồmcả UNIX. 3/12/2008 Nguyên lý Hệ điềuhành 131
  131. 4.5. Ngănchặnbế tắc „ Ràng buộccáchthứcyêucầu tài nguyên củacác tiếntrình ‰ Loạitrừ lẫnnhau– không cầnthỏamãnvớicáctài nguyên có thể chia sẻ; cầnthỏamãnvới các tài nguyên không thể chia sẻ (ví dụ máy in). ‰ Giữ và chờ –phải đảmbảorằng khi mộttiếntrìnhyêucầu một tài nguyên, nó không đượcgiữ bất kì tài nguyên nào khác. „ Tiến trình phảiyêucầuvàđược phân phốitấtcả các tài nguyên trước khi nó bắt đầuthựcthi „ Cho phép tiếntrìnhyêucầu tài nguyên chỉ khi nó không chiếm hữu tài nguyên nào. „ Tính tậndụng tài nguyên thấp; có thể xảyra“chết đói”. 3/12/2008 Nguyên lý Hệ điềuhành 132
  132. Ngănchặnbế tắc(2) „ Không chiếm đoạt – ‰ Nếumộttiến trình hiện đang giữ mộtsố tài nguyên nào đó và yêu cầu tài nguyên khác (chưathể phân phối cho nó ngay lậptức), tấtcả các tài nguyên đang bị giữ sẽđược giải phóng. ‰ Các tài nguyên bị chiếm đoạt được thêm vào danh sách các tài nguyên mà tiếntrìnhđó đang chờ. ‰ Tiếntrìnhsẽ bắt đầuthựcthilạichỉ khinócóthể lấylạicác tài nguyên cũ cũng như chiếmcả tài nguyên mớimànó đang yêu cầu. „ Chờđợi vòng tròn –ápđặtmộttrìnhtự tổng thể củatấtcả các loại tài nguyên, và ràng buộccáctiến trình yêu cầu tài nguyên theo thứ tự tăng dần. 3/12/2008 Nguyên lý Hệ điềuhành 133
  133. 4.6. Tránh bế tắc „ Yêu cầuhệ thống phảicótrướcmộtsố thông tin (prior information available). ‰ Mô hình đơngiản: mỗitiến trình khai báo số tài nguyên lớn nhấtthuộcmỗiloạimànócần. ‰ Thuật toán tránh bế tắckiểmtratrạng thái phân phốitài nguyên để đảmbảorằng không bao giờ có điềukiện“chờ đợi vòng tròn” xảyra. ‰ Trạng thái phân phối tài nguyên đượcxácđịnh bằng số các tài nguyên rỗi, số tài nguyên đã được phân phốivàsố cực đạiyêucầucủacáctiếntrình. 3/12/2008 Nguyên lý Hệ điềuhành 134
  134. Trạng thái an toàn „ Chừng nào mộttiếntrìnhyêucầumột tài nguyên rỗi, cầnxácđịnh xem việc phân phối đócóđặthệ thống vào trạng thái không an toàn không. „ Hệ thống trong trạng thái an toàn nếutồntạimột“chuỗian toàn”của tấtcả các tiến trình. „ Chuỗi là an toàn đốivớimỗiPi, các tài nguyên mà Pi cần đềucóthể phân phốibởi các tài nguyên đang rỗihoặccáctài nguyên đăng bị chiếmhữubởitấtcả các tiếntrìnhPj (vớij<i). ‰ NếuPi cần tài nguyên không rỗi ngay lậptức, thì Pi có thểđợichođến khi tấtcả các Pj hoàn thành. ‰ Khi Pj đã hoàn thành, Pi có thể chiếmhữu tài nguyên mà nó âần, thực thi và trả lại tài nguyên đã đượcphânphốivàkết thúc. ‰ Khi Pi kếtthức, Pi+1 có thể chiếmhữu tài nguyên mà nó cần. 3/12/2008 Nguyên lý Hệ điềuhành 135
  135. Tiên đề „ Nếumộthệ thống trong trạng thái an toàn ⇒ không có bế tắc „ Nếumộthệ thống ở trong trạng thái không an toàn ⇒ có thể có bế tắc. „ Tránh bế tắc ⇒ đảmbảorằng hệ thống không bao giờ rơivàotrạng thái không an toàn. 3/12/2008 Nguyên lý Hệ điềuhành 136
  136. Trạng thái an toàn, không an toàn và bế tắc 3/12/2008 Nguyên lý Hệ điềuhành 137
  137. Thuậttoánđồ thị phân phối tài nguyên „ Claim Pi → Rj chỉ rằng mộttiếntrìnhPj có thể yêu cầu tài nguyên Rj; đượcbiểudiễnbởi đường đứt quảng. „ Cạnh Claim đượcbiến đổi thành cạnh request nếu mộttiếntrìnhyêucầumột tài nguyên. „ Khi mộttiếntrìnhgiải phóng tài nguyên, cạnh assignment được chuyểnlại thành cạnh claim. „ Các tài nguyên phảicómột độ ưutiêntronghệ thống. 3/12/2008 Nguyên lý Hệ điềuhành 138
  138. Đồ thị phân phối tài nguyên để tránh bế tắc 3/12/2008 Nguyên lý Hệ điềuhành 139
  139. Trạng thái không an toàn trong đồ thị phân phố i tài nguyên 3/12/2008 Nguyên lý Hệ điềuhành 140
  140. Thuật toán Banker „ Các tài nguyên có nhiềuthể hiện. „ Mỗitiếntrìnhkhimớivàohệ thống cầnphảikhai báo số cực đại tài nguyên mà nó cần. „ Khi mộttiếntrìnhyêucầu tài nguyên, hệ thống kiểm tra xem liệuviệcphânphối tài nguyên đócóđảm bảohệ thống trong trạng thái an toàn hay không ‰ Nếu không, tiếntrìnhcóthể phảichờ „ Khi mộttiếntrìnhđã đượcphânphối tài nguyên, nó phảitrả lại các tài nguyên này trong mộtthờigian xác định. 3/12/2008 Nguyên lý Hệ điềuhành 141
  141. Cấutrúcdữ liệuchothuật toán Banker „ Gọi n = số tiến trình, and m = số loại tài nguyên. ‰ Available: vector độ dài m. Nếu available [j] = k, có k thể hiệncủa tài nguyên Rj rỗi. ‰ Max: n x m matrix. Nếu Max [i,j] = k, tiếntrìnhPi có thểđòi hỏi nhiềunhấtlàk thể hiệncủaloại tài nguyên Rj. ‰ Allocation: n x m matrix. Nếu Allocation[i,j] = k , tiếntrình Pi hiện được phân phối k thể hiệncủa Rj. ‰ Need: n x m matrix. Nếu Need[i,j] = k, tiếntrìnhPi có thể cần thêm k thể hiệncủa Rj để hoàn thành nhiệmvụ của nó. Need [i,j] = Max[i,j] – Allocation [i,j]. 3/12/2008 Nguyên lý Hệ điềuhành 142
  142. Thuật toán Safety 1. Gọi Work and Finish là các vectors có độ dài lầnlượtlàm và n. Khởi tạo: Work = Available Finish [i] = false for i - 1,3, , n. 2. Tìm i thỏa mãn hai điềukiện sau: (a) Finish [i] = false (b) Needi ≤ Work Nếu không tìm được i, nhảy đếnbước4. 3. Work = Work + Allocationi Finish[i] = true Nhảy đếnbước2. 4. Nếu Finish [i] == true vớitấtcả i, hệ thống trong trạng thái an toàn. 3/12/2008 Nguyên lý Hệ điềuhành 143
  143. Thuật toán phân phốiyêucầu tài nguyên cho tiếntrìnhPi Request = vector yêu cầucủa P . Nếu Request [j] = k, P cần k thể hiện i i i của Rj. 1. Nếu Requesti ≤ Needi nhảy đếnbước 2. Nếu không, lỗi(tiếntrìnhcần nhiềuhơnsố yêu cầu khai báo ban đầu). 2. Nếu Requesti ≤ Available, nhảy đếnbước 3. Nếu không Pi phảichờ vì tấtcả tài nguyên đều không rỗi. 3. Thử phân phối tài nguyên đượcyêucầuchoPi bằng cách thay đổitrạng thái như sau: Available = Available - Requesti; Allocation i = Allocationi + Requesti; Needi = Needi – Requesti; z Nếu an toàn⇒ tài nguyên được phân phốichoPi. z Nếu không an toàn ⇒ Pi ph ải đợi, trạ ng thái phân phối tài nguyên cũđược khôi phụclại 3/12/2008 Nguyên lý Hệ điềuhành 144
  144. Ví dụ về thuật toán Banker „ 5 tiếntrìnhtừ P0 đến P4 „ 3 loại tài nguyên A (10 thể hiện), B (5 thể hiện), và C (7 thể hiện). „ Hệ thống tạithời điểm T0: Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P 2 0 0 3 2 2 1 P 3 0 2 9 0 2 2 P 2 1 1 2 2 2 3 P 0 0 2 4 3 3 4 3/12/2008 Nguyên lý Hệ điềuhành 145
  145. Ví dụ (Cont.) „ Nội dung củama trận Need. Need được định nghĩalà Max – Allocation. Need A B C P0 7 4 3 P 1 2 2 1 P 6 0 0 2 P 0 1 1 3 P 4 3 1 4 „ Hệ thống trong trạng thái an toàn vì chuỗi thỏamãnđiềukiện an toàn. 3/12/2008 Nguyên lý Hệ điềuhành 146
  146. Ví dụ: P1 yêu cầu (1,0,2) (Cont.) „ Kiểmtrathấy Request ≤ Available (hay, (1,0,2) ≤ (3,3,2) ⇒ true). Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 1 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 „ Thựcthithuật toán safety cho thấychuỗi thỏamãnyêuc ần an toàn. „ Yêu cầu (3,3,0) củaP4 cóthểđược gán hay không? „ Yêu cầu (0,2,0) củaP0 cóthểđược gán hay không? 3/12/2008 Nguyên lý Hệ điềuhành 147
  147. 4.7. Khôi phụcsaubế tắc „ Cho phép trạng thái vào trạng thái bế tắc „ Thuậttoánpháthiệnbế tắc „ Phương pháp khôi phục 3/12/2008 Nguyên lý Hệ điềuhành 148
  148. Mỗiloại tài nguyên có mộtthể hiện „ Duy trì đồ thị wait-for ‰ Các node là các tiến trình. ‰ Pi → Pj nếu Pi đang chờ Pj. „ Định kì thựchiệnthuật toán tìm chu trình trong đồ thị. „ Mộtgiảithuậtkiểm tra chu trình trong đồ thị cần n2 thao tác, ởđây n là sốđỉnh trong đồ thị. 3/12/2008 Nguyên lý Hệ điềuhành 149
  149. Đồ thị phân phối tài nguyên và đồ thị Wait-for Đồ thị phân phối tài nguyên Đồ thị wait-for tương ứng 3/12/2008 Nguyên lý Hệ điềuhành 150
  150. Mỗi tài nguyên có nhiềuhơnmộtthể hiện „ Available: Vector độ dài m chỉ số các trường hợpcònrỗi đối vớimỗi tài nguyên. „ Allocation: Ma trận n x m xác định số tài nguyên củamỗiloại được phân phốichotiếntrình. „ Request: Ma trận n x m chỉ yêu cầuhiệntạicủatiếntrình. Nếu Request [ij] = k, tiếntrìnhPi đang cần thêm k trường hợp tài nguyên Rj. 3/12/2008 Nguyên lý Hệ điềuhành 151
  151. Thuật toán phát hiện 1. Gọi Work and Finish là các vector độ dài m và n t ương ứng. Khởit ạo: (a) Work = Available (b) For i = 1,2, , n, if Allocationi ≠ 0, then Finish[i] = false;otherwise, Finish[i] = true. 2. Tìm mộtchỉ số i thỏamãn: (a) Finish [i] == false (b) Request i ≤ Work Nếu không tồntại i nhảy đếnbước4. 3/12/2008 Nguyên lý Hệ điềuhành 152
  152. Thuật toán phát hiện (Cont.) 3.Work = Work + Allocationi Finish[i] = true go to step 2. 4.If Finish[i] == false, for some i, 1 ≤ i ≤ n, then hệ thống trong trạng thái bế tắc. Hơnn ữ a, if Finish [i] == false, then P i bị bế tắc. Độ phứctạocủathuật toán là O(m x n2). 3/12/2008 Nguyên lý Hệ điềuhành 153
  153. Ví dụ về thuật toán phát hiện „ 5 tiếntrìnhP0 đến P4;baloại tài nguyên: A (7 trường hợp), B (2 trường hợp), and C (6 trường hợp). „ Hệ thống tạithời điểm T0: Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P 2 0 0 2 0 2 1 P 3 0 3 0 0 0 2 P 2 1 1 1 0 0 3 P 0 0 2 0 0 2 4 „ Chuỗi dẫn đến Finish[i] = true vớimọi i. 0 2 3 1 4 3/12/2008 Nguyên lý Hệ điềuhành 154
  154. Ví dụ (Cont.) „ P2 yêu cầu thêm mộtthể hiệncủa C. Request A B C P0 0 0 0 P 2 0 1 1 P 0 0 1 2 P 1 0 0 3 P 0 0 2 4 „ Trạng thái củahệ thống? ‰ Tồntạibế tắc, bao gồmcáctiếntrìnhP1, P2, P3, và P4. 3/12/2008 Nguyên lý Hệ điềuhành 155
  155. Sử dụng thuật toán phát hiện „ Thời điểm, mức độ thường xuyên phụ thuộc vào: ‰ Mức độ thường xuyên củabế tắc? ‰ Bao nhiêu tiếntrìnhcầnphải quay lui? „ Một đốivớimỗi chu trình (các chu trình không giao) „ Nếuthuật toán phát hiện đượcgọi tùy ý, có thể có rấtnhiềuchutrìnhtrongđồ thị tàinguyênvàvìthế chúng ta không thể phát hiệntiếntrìnhnàotrongsố các tiếntrìnhđó gây ra bế tắc. 3/12/2008 Nguyên lý Hệ điềuhành 156
  156. Khôi phụcsaubế tắc: Kếtthúctiếntrình „ Dừng thựcthicủa toàn bộ tiếntrìnhbế tắc. „ Dừng mộttiếntrìnhmộtchođếnkhimất đichutrìnhbế tắc. „ Thứ tự dừng? ‰ Độ ưutiêncủatiến trình. ‰ Tiếntrìnhđã đượcthực thi và còn phảithực thi trong bao lâu. ‰ Các tài nguyên mà tiến trình hiện đang sử dụng. ‰ Các tài nguyên mà tiếntrìnhcần thêm. ‰ Số tiếntrìnhcầnphảikết thúc. ‰ Tiếntrìnhlàtương tác hay batch? 3/12/2008 Nguyên lý Hệ điềuhành 157
  157. Khôi phụcsaubế tắc: chiếm đoạt tài nguyên „ Lựachọnmộtnạnnhân–cựctiểu hóa cost. „ Rollback – trở về trạng thái an toàn, khởi động lạitiến trình cho trạng thái đó. „ Chết đói – mộttiếntrìnhcóthể luôn bị lựachọnlànạn nhân 3/12/2008 Nguyên lý Hệ điềuhành 158
  158. Kếtthúcchương 2 3/12/2008 Nguyên lý Hệ điều hành 159