›
›

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

pdf 57 trang ngocly 180
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 3: Tiến trình và luồng - Hà Duy An", để 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:

  • pdfbai_giang_he_dieu_hanh_chuong_3_tien_trinh_va_luong_ha_duy_a.pdf

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

  1. Khoa Công Nghệ Thông Tin & Truyền Thông ĐạihọcCầnThơ Giảng viên: Hà Duy An
  2. 1. Các khái niệm 2. Định thờibiểutiếntrình 3. Các thao tác vớitiếntrình 4. Giao tiếpgiữacáctiếntrình 8/22/2013 3 Chương 3: Tiến Trình
  3. • Hệđiềuhànhcóthể thực thi nhiềudạng chương trình: o Hệ thống bó (batch system) – jobs o Hệ thống chia thờigian–chương trình người dùng (user program) hay tác vụ (task) • Tiếntrình-làmộtchương trình đang thựcthi.Sự thựcthicủa tiến trình diễn ra theo cách thứctuầntự. • Mộttiến trình bao gồm: o Mã chương chương trình (program code hay text section) o Bộđếmchương trình (program counter) o Ngănxếp (stack) – chứa các dữ liệutạmthời • Các tham số củahàm,địachỉ trở về,biếncụcbộ o Phầndữ liệu (data section) - chứa các biếntoàncục o Heap – bộ nhớđộng, đượccấp phát trong suốtthờigianthựcthi 8/22/2013 5 Chương 3: Tiến Trình
  4. • Chương trình là mộtthựcthể bị động lưutrữ trên đĩa, tiếntrình là thựcthể chủđộng o Chương trình trở thành tiến trình nó đượcnạpvàotrongbộ nhớđểthựcthi o Chương trình có thểđượckích hoạt qua thao tác nhấpchuột, nhậptênvàoCLI, o Mộtchương trình có thể có vài tiếntrình 8/22/2013 6 Chương 3: Tiến Trình
  5. • Tiếntrìnhcóthể có các trạng thái sau: o new: quá trình đang đượckhởitạo. o running: các chỉ thị của quá trình đang đượcthực thi. o waiting: quá trình đang chờđợimộtsự kiệnnào đóxảy ra (hoàn thành xuất/nhập, chờđợimột tín hiệu). o ready: quá trình đang đợi để đượcsử dụng CPU. o terminated: quá trình đãkết thúc. 8/22/2013 7 Chương 3: Tiến Trình
  6. 8/22/2013 8 Chương 3: Tiến Trình
  7. • Thông tin kếthợpvớimỗi quá trình: o Trạng thái của quá trình o Bộđếmchương trình o Các thanh ghi o Thông tin vềđịnh thờisử dụng CPU o Thông tin về quảnlýbộ nhớ o Thông tin về chi phí o Thông tin về trạng thái nhập/xuất 8/22/2013 9 Chương 3: Tiến Trình
  8. 8/22/2013 10 Chương 3: Tiến Trình
  9. • Nhằmtối ưu hóa việcsử dụng CPU, các tiến thay phiên nhau sử dụng CPU • Bộđịnh thờitiếntrình(Process scheduler) chọnlựamộttiến trình có thể thựcthiđể cấp phát CPU cho tiếntrìnhđó • Các hàng đợi định thời: o Hàng đợicôngviệc (Job queue): tậphợptấtcả các quá trình trong hệ thống. o Hàng đợisẵn sàng (Readyqueue): tậphợptấtcả các quá trình đang nằm trong bộ nhớ,sẵnsàngvàđang chờđểthựcthi. o Hàng đợithiếtbị (Device queue): tậphợp các quá trình đang đợisử dụng mộtthiếtbị xuất/nhập. • Quá trình có thể di chuyểngiữa các hàng đợi khác nhau 8/22/2013 12 Chương 3: Tiến Trình
  10. 8/22/2013 13 Chương 3: Tiến Trình
  11. 8/22/2013 14 Chương 3: Tiến Trình
  12. • Bộđịnh thờidàikỳ (Long-term scheduler/job scheduler) – chọn quá trình nào sẽđược đặt vào hàng đợisẵnsàng(nạpvàobộ nhớ). • Bộđịnh thờingắnkỳ (Short-term scheduler/CPU scheduler) –chọn ra quá trình sẽđượcthựcthikế tiếpvàcấpCPUchonó. • Bộđịnh thờingắnkỳđượcgọirấtthường xuyên (milliseconds) => cầnphải nhanh • Bộđịnh thờidàikỳđượcgọi không thường xuyên hơn (seconds, minutes) => có thể chậm • Bộđịnh thờidàikỳ khống chế mức độ đachương củahệ thống • Các tiếntrìnhcóthể là: o Tiếntrìnhhướng xử lý: cần nhiều tính toán hơnnhậpxuất o Tiếntrìnhhướng nhậpxuất: cần nhiềunhậpxuấthơn tính toán • Bộđịnh thờidàikỳ cố gắng điều hòa giữa các tiến trình này 8/22/2013 15 Chương 3: Tiến Trình
  13. • Bộđịnh thời trung kỳ (Medium-term scheduling) – làm giảm mức độ đachương củahệ thống o Di chuyển các tiến tình ra khỏibộ nhớ,lưutrữ trên đĩa, sau đó mang vào bộ nhớđểtiếptụcthựcthi:swapping 8/22/2013 16 Chương 3: Tiến Trình
  14. • Chuyểnngữ cảnh (context switch): Khi CPU chuyểnsangphụcvụ tiến trình khác, hệ thống phảighilạitrạng thái củatiếntrìnhcũ và nạptrạng thái đượclưutrước đócủatiếntrìnhmới • “Ngữ cảnh”củamộttiếntrìnhđượcxácđịnh thông qua các thông tin trong PCB • Thờigianchuyểnngữ cảnh là mộtphítổn, vì hệ thống không làm gì hữu ích khi thựchiện chuyểnngữ cảnh o HĐH và PCB càng phứctạp=>thời gian chuyểnngũ cảnh càng dài • Thờigianchuyểnngữ cảnh phụ thuộc nhiềuvàosự hỗ trợ củaphần cứng o Vài hệ thống cung cấpnhiềutổ hợp các thanh ghi trên mỗiCPU=> nhiều“ngữ cảnh” đượcnạp vào cùng lúc 8/22/2013 17 Chương 3: Tiến Trình
  15. • Quá trình cha tạoraquátrìnhcon,đếnlượt quá trình con này lạitạoranhững quá trình khác, tạo nên cây quá trình. • Thông thường các tiếntrìnhđượcxácđịnh và quảnlý thông qua PID (Process identifier) • Chia sẻ tài nguyên – có nhiềulựachọn: o Quátrìnhchavàconchiasẻ tấtcả tài nguyên. o Quá trình con chia sẻ mộtphần tài nguyên của quá trình cha. o Quá trình cha và con không chia sẻ tài nguyên nào cả. • Thựcthi: o Quátrìnhchavàconthựcthiđồng thời. o Quá trình cha đợi đến khi quá trình con hoàn thành. 8/22/2013 19 Chương 3: Tiến Trình
  16. init pid = 1 login kthreadd sshd pid = 8415 pid = 2 pid = 3028 bash khelper pdflush sshd pid = 8416 pid = 6 pid = 200 pid = 3610 tcsch ps emacs pid = 4005 pid = 9298 pid = 9204 8/22/2013 20 Chương 3: Tiến Trình
  17. • Không gian địachỉ: o Quá trình con sao chép không gian địachỉ của quá trình cha (cùng chương trình và dữ liệu). o Quá trình con tự nạpchương trình riêng của nó. • Hệ thống UNIX o fork() –là lờigọihệ thống dùng tạo quá trình mới o exec() –là lờigọihệ thống đượcsử dụng sau fork() để thay thế không gian địachỉ của quá trình bằng mộtchương trình mới 8/22/2013 21 Chương 3: Tiến Trình
  18. 8/22/2013 22 Chương 3: Tiến Trình
  19. 8/22/2013 23 Chương 3: Tiến Trình
  20. • Quá trình thựchiệncâulệnh cuốicùngvàyêucầuHĐH xóa nó (dùng exit). o Xuấtdữ liệutừ quá trình con lên quá trình cha (wait()). pid_t pid; int status; pid=wait(&status); o Tài nguyên của quá trình bị thu hồilạibởihệđiều hành. • Quátrìnhchacóthể kết thúc sự thựcthicủa quá trình con (abort()). o Quá trình con đãvượt quá số tài nguyên đượccấp. o Công việc giao cho quá trình con nay không còn cầnthiếtnữa. o Quá trình cha đang thoát. • Vài hệđiều hành không cho phép quá trình con tiếptụcthực thi khi quá trình cha kết thúc => Sự kết thúc hàng loạt các quá trình con (cascading termination) • Nếutiếntrìnhchachưagọiwait()=>tiếntrìnhconvừakếtthúctrở thành một zombie • Nếutiếntrìnhchakết thúc trước=>tiếntrìnhconmồ coi (orphan) 8/22/2013 24 Chương 3: Tiến Trình
  21. • Nếu các trình duyệtwebthựcthidạng đơntiến trình => nếu một web site bị lỗi, toàn bộ trình duyệtbị treo hay đổ vỡ • Google Chrome Brower thựcthidạng đatiến trình, phân ra làm 3 nhóm: o Browser: tiến trình quảnlýgiaodiệnngười dùng, xuât/nhập đĩa và mạng o Renderer:xử lý hiểnthị các trang web (HTML, JavaScript, ) mỗitiếntrìnhchomộttrangweb o Plug-in:mộttiếntrìnhchomỗiloại plug-in 8/22/2013 26 Chương 3: Tiến Trình
  22. • Các tiến trình trong hệ thống có thểđộclậphayhợptác • Tiếntrìnhđộclậpkhôngthể gây ảnh hưởng hay bịảnh hưởng bởi các tiến trình khác • Tiếntrìnhhợp tác có thể gây ảnh hưởng hay bịảnh hưởng bởicác tiến trình khác • Mục đích hợptácgiữa các tiến trình: o Chia sẽ thông tin o Tăng tốc độ tính toán o Module hóa o Tiệnlợi • Tiếntrìnhhợptáccầntraođổi thông tin vớinhau(IPC- Interprocess communication) • 2môhìnhIPC: o Shared memory o Message passing 8/22/2013 27 Chương 3: Tiến Trình
  23. 8/22/2013 28 Chương 3: Tiến Trình
  24. • Bài toán điển hình minh họa cho sự hợptácgiữa các tiếntrình –tiếntrìnhNhàsảnxuấtsinhradữ liệu đượcsử dụng bởitiến trình Người tiêu thụ • Giảiquyếtbàitoánvớicơ chế bộ nhớ chia sẽ -2tiến trình sử dụng một vùng nhớ dùng chung (buffer), tiếntrìnhNgườisản xuất ghi dữ liệu lên buffer, tiếntrìnhNgườitiêuthụ lấydữ liệu từ buffer • 2loại buffer: o unbounded-buffer: kích thước không giớihạn o bounded-buffer: kích thướcgiớihạn 8/22/2013 29 Chương 3: Tiến Trình
  25. • Dữ liệuchiasẽ: #define BUFFER_SIZE 10 typedef struct { . . . } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; 8/22/2013 30 Chương 3: Tiến Trình
  26. item next_produced; while (true) { /* produce an item in next produced */ while (((in + 1) % BUFFER_SIZE) == out) ; /* do nothing */ buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; } 8/22/2013 31 Chương 3: Tiến Trình
  27. item next_consumed; while(true){ while(in == out); /* do nothing */ next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; /* consume the item in next consumed */ } 8/22/2013 32 Chương 3: Tiến Trình
  28. • Cung cấpcơ chế giao tiếpgiữa các tiến trình không cầndụng bộ nhớ chia sẽ => hữuíchtrongmôitrường phân tán, các tiến trình giao tiếpvới nhau qua mạng • Cần hai thao tác: o send(message)–kíchthước thông điệpcốđịnh hay biến đổi o receive(message) • Tiến trình P và Q nếumuốngiaotiếpvới nhau: o Tạomột communication link o Trao đổi thông điệp thông qua send/receive • Phương thức cài đặt communication link (mứcluận lý): o Trựctiếp-giántiếp o Đồng bộ -bất đồng bộ o KiểuBuffer 8/22/2013 33 Chương 3: Tiến Trình
  29. • Tạo communication link như thế nào? • Có thể dùng một communication link cho nhiềutiến trình? • Có bao nhiêu liên kếtcóthể tạogiữahaitiến trình? • Khả năng củamột liên kết? • Kích thướccủa thông điệpcốđịnh hay thay đổi? • Liên kếtlàmộthướng hay 2 hướng? 8/22/2013 34 Chương 3: Tiến Trình
  30. • Các tiến trình phảixácđịnh rõ ràng tên củatiến trình nhậnhay gửidữ liệu khác o send(P, message) –gửimột thông điệp đếntiếntrìnhP o receive(Q, message)–nhậnmột thông điệptừ tiếntrình Q • Các thuộc tính của communication link: o Các liên kết đượctạoratựđộng o Mộtliênkếttương ứng chỉ có 2 tiếntrìnhthựchiệngiaotiếptrên nó o Giữamỗicặptiếntrìnhchỉ tồntại duy nhấtmột liên kết o Liên kếtcóthể là mộthướng, nhưng thường là hai hướng. 8/22/2013 35 Chương 3: Tiến Trình
  31. • Các thông điệpgửi đếnvànhậntừ các mailbox hay port o Mỗi mailbox có mộtsố nhậndạng duy nhất o Các tiếntrìnhcóthể giao tiếpvới nhau khi chúng chia sẽ cùng một mailbox • Các thuộc tính của communication link: o Liên kết đượctạo ra khi các tiếntrìnhchiasẽ cùng một mailbox o Một liên kếtcóthể liên kếtvới nhiềutiếntrình o Mỗicặptiếntrìnhcóthể cùng chia sẽ vài cummunication link o Liên kếtcóthể mộthayhaihướng 8/22/2013 36 Chương 3: Tiến Trình
  32. • HĐH cung cấpcơ chế: o Tạomột mailbox o Gửivànhận thông điệp thông qua mailbox o Hủymột mailbox • Phương thứcgửivànhậnmột thông điệp: o send(A, message) –gửimột thông điệp đến mailbox A o receive(A, message) –nhậnmột thông điệptừ mailbox A 8/22/2013 37 Chương 3: Tiến Trình
  33. • Chia sẽ mailbox: o P1, P2, và P3 chia sẽ cùng một mailbox A o P1 gửi; P2 hay P3 nhận??? • Giải pháp: o Một liên kếtchỉ tương ứng với2tiếntrình o Chỉ mộttiếntrìnhtạimộtthời điểmthựchiệnthaotácnhận o HĐHchỉđịnh tiếntrìnhnhận, và thông báo cho tiếntrìnhgửi biếtngườinhận 8/22/2013 38 Chương 3: Tiến Trình
  34. • Truyền thông điệpcóthể nghẽn (blocking) hay không nghẽn (non-blocking) • Blocking – đồng bộ (synchronous) o Blocking send: tiếntrìnhgửichờ cho đếnkhithôngđiệp được nhận o Blocking receive : tiếntrìnhnhậnchờ cho đến khi thông điệpsẳn sàng • Non-blocking –bất đồng bộ (asynchronous) o Non-blocking send: gửi thông điệpvàtiếptụcthựchiện công việc khác o Non-blocking receive: nhậnmột thông điệp hay null 8/22/2013 39 Chương 3: Tiến Trình
  35. • Các thông điệpnằm trong hàng đợitạmthời (buffer), 3 cách cài đặt: o Zero capacity – không có thông điệpnàonằm trong hàng đợi (sender chờ cho đến khi thông điệp đượcnhận) o Boundedcapacity–kíchthước buffer là giớihạn (sender phải chờ khi buffer đầy) o Unbounded capacity – kích thước buffer không giớihạn 8/22/2013 40 Chương 3: Tiến Trình
  36. 8/22/201341 Chương 3: Tiến Trình
  37. 1. Giớithiệuvề Luồng (Thread) 2. Lập trình trên vi xử lý đa nhân 3. Mô hình đaluồng 8/22/2013 42 Chương 3: Tiến Trình
  38. 8/22/201343 Chương 3: Tiến Trình
  39. • Hầuhết các chương trình ứng dụng hiện đạilàđaluồng (Multithread) • Một ứng dụng có nhiềutácvụ => mỗitácvụđược cài đặtnhư mộtluồng: o Cậpnhậthiểnthị o Lấydữ liệu o Kiểmtrachínhtả o Trả lời các kếtnốimạng, . • Tạomộttiến trình cần nhiều chi phí hơntạoramộtluồng • Việclậptrìnhđơngiảnhơn, hiệuquả hơn • Nhân của nhiềuHĐH ngày nay là đaluồng 8/22/2013 44 Chương 3: Tiến Trình
  40. 8/22/2013 45 Chương 3: Tiến Trình
  41. 8/22/2013 46 Chương 3: Tiến Trình
  42. • Tăng khả năng đáp ứng • Chia sẽ tài nguyên dễ dàng • Ít hao tốn tài nguyên hệ thống hơn • Tậndụng đượckhả năng trên các hệ thống có nhiềubộ xử lý 8/22/2013 47 Chương 3: Tiến Trình
  43. 8/22/201348 Chương 3: Tiến Trình
  44. • Các hệ thống Multicore hay Multiprocessor giúp tăng năng lực xử lý cho hệ thống, đồng thời phát sinh ra nhiềuvấn đề trong việcthiếtkế và phát triểnchương trình: o Phân chia tác vụ o Cân bằng o Phân chia và chia sẽ dữ liệu o Kiểmlỗi • Song song (Parallelism) khác với đồng thời (Concurrency) • Hai kiểu song song: o Dữ liệu – phân phốidữ liệu cùng kiểu, tác vụ xử lý giống nhau o Tác vụ -tácvụ xử lý khác nhau, dữ liệucóthể giống hoặc khác nhau 8/22/2013 49 Chương 3: Tiến Trình
  45. • Xử lý đồng thờitrênhệ thống đơn nhân: • Xử lý song song trên hệ thống đa nhân: 8/22/2013 50 Chương 3: Tiến Trình
  46. 8/22/201351 Chương 3: Tiến Trình
  47. • User threads – cài đặtluồng ở mứcngười dùng • Kernel threads – đượchỗ trợ bởi nhân (kernel) • Hầunhư tấtcả các hệđiềuhànhđamục đích hiệnnayđiềuhỗ trợ kernel threads (Windows, Linux, MacOS X, and Solaris) • Liên hệ giữa User threads và kernel threads: o Many to One o One to One o Many to Many 8/22/2013 52 Chương 3: Tiến Trình
  48. • Nhiều user thread – một kernel thread • Vấn đề: o Mộtluồng nghẽn=>toàntiến trình nghẽn o Chỉ mộtluồng có thể chạy ở mứcnhântạimộtthời điểm nhất định => không hiệuquả trên hệ thống multicore o Rấtíthệ thống dùng mô hình này 8/22/2013 53 Chương 3: Tiến Trình
  49. • Mỗi user thread – một kernel thread • Hiệuquả hơntrênhệ thống multicore • Vấn đề: o Số lượng luồng trên mỗitiếntrìnhcầngiớihạn vì chi phí tạo kernel thread đắthơn user thread • Các hệ thống dùng mô hình này: Windows NT/XP/2000, Linux, solaris 9. 8/22/2013 54 Chương 3: Tiến Trình
  50. • Nhiềuuserthread-số lượng kernel thread bằng hay ít hơn • HĐHtạo môt số lượng kernel thread đủ dùng 8/22/2013 55 Chương 3: Tiến Trình
  51. • Thread library cung cấpAPIcholập trình viên tạovàquảnlý luồng • Có 2 cách cài đặt: o Mứcngười dùng o Mức nhân – đượchỗ trợ bởiHĐH • Các thread library được dùng phổ biến: POSIX Pthreads, Windows, Java 8/22/2013 56 Chương 3: Tiến Trình