Bài giảng Giới thiệu khoa học máy tính - Chương 3: Hệ điều hành - Nguyễn Thanh Trung

Nội dung text: Bài giảng Giới thiệu khoa học máy tính - Chương 3: Hệ điều hành - Nguyễn Thanh Trung

1. GIỚI THIỆU KHOA HỌC MÁY TÍNH CHƯƠNG 3 – HỆ ĐIỀU HÀNH NGUYỄN THANH TRUNG 1
2. Mục tiêu ◼ Giới thiệu tổng quan về hệ điều hành gồm: HĐH là gì, chức năng của HĐH, phân loại và những HĐH phổ biến, ◼ Trình bày những kiến thức cơ bản về nguyên lý hoạt động cũng cấu trúc bên trong của HĐH. ◼ Giúp sinh viên biết được tầm quan trọng của HĐH cũng như việc lựa chọn HĐH cho phù hợp với mục tiêu sử dụng. 2
3. Bố cục ◼ 3.1. Lịch sử các hệ điều hành ◼ 3.2. Tổ chức và hoạt động ◼ 3.3. Cơ chế bảo vệ thơng tin của HĐH 3
4. Tài liệu tham khảo ◼ Chương 3, Computer Science ◼ Chương 3, bài giảng Giới thiệu Khoa học Máy tính. ◼ Tham khảo Bài giảng Hệ điều hành, Đại học Khoa học Tự nhiên (ebook) 4
5. 3.1. Tổng quan hệ điều hành ◼ Khái niệm ◼ Lịch sử phát triển ◼ Chức năng ◼ Phân loại 5
6. 3.1.1 Khái niệm ◼ Hệ điều hành là một chương trình chạy trên máy tính, dùng để điều hành, quản lý các thiết bị phần cứng và các tài nguyên phần mềm trên máy tính. ◼ Đĩng vai trị trung gian trong việc giao tiếp giữa người sử dụng và phần cứng máy tính, cung cấp một mơi trường cho phép người sử dụng phát triển và thực hiện các ứng dụng của họ một cách dễ dàng. 6
7. 3.1.2.Lịch sử Hệ điều hành Theo các giai đoạn phát triển ◼ Thế hệ I: Chưa cĩ HĐH, thao tác bằng tay trên bảng điều khiển. ◼ Thế hệ II: Hệ thống xử lý theo lơ, gồm thực hiện các yêu cầu trên băng từ 1 cách tuần tự. ◼ Thế hệ III: Hệ điều hành đầu tiên gồm nhiều dịng lệnh hợp ngữ; HĐH đa chương (bộ nhớ chia thành nhiều phần chứa các cơng việc khác nhau); HĐH chia sẻ thời gian trên máy mainframe, mini, ◼ Thế hệ IV: Với sự ra đời máy tính cá nhân, nhiều HĐH: HĐH đa nhiệm, HĐH Mạng, HĐH phân tán ra đời 7
8. 3.1.3.Chức năng Quản lý chia sẻ tài nguyên ◼ Tài nguyên của hệ thống (CPU, bộ nhớ, thiết bị ngoại vi, ) hệ điều hành cần phải cĩ cơ chế và chiến lược thích hợp để quản lý việc phân phối tài nguyên. ◼ Ngồi yêu cầu dùng chung tài nguyên để tiết kiệm chi phí, người sử dụng cịn cần phải chia sẻ thơng tin (tài nguyên phần mềm) lẫn nhau, khi đĩ hệ điều hành cần đảm bảo việc truy xuất đến các tài nguyên này là hợp lệ, khơng xảy ra tranh chấp, thiếu nhất quán 8
9. Giả lập máy tính mở rộng ◼ Hệ điều hành làm ẩn đi các chi tiết phần cứng, người sử dụng được cung cấp 1 giao diện đơn giản, dễ hiểu và khơng phụ thuộc vào thiết bị cụ thể. ◼ Thực tế, ta cĩ thể xem Hệ điều hành như là 1 hệ thống bao gồm nhiều máy tính trừu tượng xếp thành nhiều lớp chồng lên nhau, máy tính mức dưới phục vụ cho máy tính mức trên. Lớp trên cùng là giao diện trực quan nhất để chúng ta điều khiển. ◼ Ngồi ra cĩ thể chia theo 4 chức năng sau : Quản lý tiến trình (process management), Quản lý bộ nhớ (memory management) Quản lý hệ thống lưu trữ (storage management) Giao tiếp với người dùng (user interaction) 9
10. Một số nhiệm vụ cụ thể ◼ Điều khiển và quản lý trực tiếp các phần cứng như bo mạch chủ, bo mạch đồ họa và bo mạch âm thanh, ◼ Thực hiện một số thao tác cơ bản trong máy tính như các thao tác đọc, viết tập tin, quản lý hệ thống tập tin (file system) và các kho dữ liệu. ◼ Cung ứng một hệ thống giao diện sơ khai cho các ứng dụng thường là thơng qua một hệ thống thư viện các hàm chuẩn để điều hành các phần cứng mà từ đĩ các ứng dụng cĩ thể gọi tới. ◼ Cung ứng một hệ thống lệnh cơ bản để điều hành máy. Các lệnh này gọi là lệnh hệ thống (system command). ◼ Ngồi ra cũng cung cấp các dịch vụ cơ bản cho các phần mềm ứng dụng 10
11. 3.1.4.Phân loại các HĐH Theo loại máy tính ◼ Hệ điều hành dành cho máy MainFrame ◼ Hệ điều hành dành cho máy Server ◼ Hệ điều hành dành cho máy nhiều CPU ◼ Hệ điều hành dành cho máy tính cá nhân (PC) ◼ Hệ điều hành dành cho máy PDA (Embedded OS - hệ điều hành nhúng) ◼ Hệ điều hành dành cho máy chuyên biệt ◼ Hệ điều hành dành cho thẻ chíp (SmartCard) 11
12. Dưới gĩc độ số chương trình được sử dụng cùng lúc ◼ Hệ điều hành đơn nhiệm ◼ Hệ điều hành đa nhiệm Dưới gĩc độ người dùng (truy xuất tài nguyên cùng lúc) ◼ Một người dùng ◼ Nhiều người dùng 12
13. Dưới gĩc độ hình thức xử lý ◼ Hệ thống xử lý theo lơ ◼ Hệ thống chia sẻ ◼ Hệ thống song song ◼ Hệ thống phân tán ◼ Hệ thống xử lý thời gian thực 13
14. 3.2.TỔ CHỨC VÀ HOẠT ĐỘNG ◼ Cấu trúc HĐH ◼ Phân chia thời gian ◼ Phân phối tài nguyên ◼ Các kiến trúc HĐH 14
15. Kiến trúc phân lớp của HĐH ◼ Phân loại phần mềm ◼ Phần mềm hệ thống ◼ Phần mềm ứng dụng ◼ Hệ điều hành ◼ Shell ◼ Kernel Kernel Shell User 15
16. shell ◼ GUI (Graphical User Interface) EX: Windows Manager ◼ Thơng dịch dịng lệnh 16
17. Kernel ◼ File Manager ◼ Device Driver ◼ Memory Manager ◼ Schedule ◼ Dispatcher 17
18. 3.2.1.Cấu trúc HĐH ◼ Đơn vị xử lý câu lệnh (Command Processor) ◼ Bộ lập lịch (Scheduler) ◼ Đơn vị quản lý tập tin, ql tài nguyên ◼ Đơn vị ql bộ nhớ ◼ Bộ điều phối (Dispatcher) 18
19. Đơn vị xử lý câu lệnh ◼ Giúp HĐH giao tiếp với người dùng ◼ Thơng qua các thiết bị nhập/xuất ◼ Khi nhận lệnh hợp lệ và tìm thấy yêu cầu xử lý của chương trình → yêu cầu bộ lập lịch sắp xếp các câu lệnh. 19
20. Đơn vị quản lý tập tin và đơn vị quản lý bộ nhớ ◼ Trước khi chương trình được bộ lập lịch chia lịch thực hiện thì bộ lập lịch cũng liên lạc với 2 dịch vụ khác đĩ là đơn vị quản lý tập tin và đơn vị quản lý bộ nhớ. ◼ đơn vị quản lý tập tin: Cung cấp thơng tin liên quan đến dữ liệu trong khối lưu trữ; bảo vệ tập tin trong khối lưu trữ tránh việc truy cập bất hợp pháp. ◼ đơn vị quản lý bộ nhớ: Phân chia việc sử dụng bộ nhớ chính, cấp phát/thu hồi vùng nhớ. 20
21. Đơn vị quản lý tài nguyên ◼ Quản lý, phân phối các tài nguyên. ◼ Phối hợp với Bộ lập lịch phân chia tài nguyên cho các tiến trình để tránh việc tranh chấp tài nguyên ◼ VD: Nếu 1 tiến trình xử lý cần 1 tài nguyên mà khơng thể cung cấp được thì đơn vị quản lý tài nguyên sẽ thơng báo cho Bộ lập lịch biết. Cịn ngược lại thì nĩ sẽ cấp tài nguyên cho tiến trình này → tiến trình được lập lịch và thực hiện. 21
22. Bộ lập lịch ◼ Sắp xếp việc thực hiện các chương trình (tiến trình). ◼ Vd: đối với hệ thống xử lý theo lơ thì chương trình sẽ được đưa vào hàng đợi theo độ ưu tiên của chương trình. ◼ Đối với hệ thống đa nhiệm thì nĩ yêu cầu chương trình phối hợp với các họat động khác cùng phân chia thời gian. ◼ Các họat động khác cùng phân chia thời gian này thực chất là các tiến trình. 22
23. bộ điều phối (dispatcher) ◼ Điều phối các tiến trình: Lựa chọn các tiến trình đang quan tâm trong số các tiến trình đã được lập lịch Bộ điều phối Đơn vị ql bộ nhớ Đơn vị ql tập tin, tài nguyên Bộ lập lịch Đơn vị xử lý câu lệnh 23
24. 3.2.2. Các nguyên lý cơ bản của phân chia thời gian ◼ Điều khiển ngắt ◼ Cấp phát thời gian: Cho 2 tiến trình được lập lịch là A và B, giả sử A thực hiện được 1 khoảng thời gian thì bị ngắt bởi bộ điều phối → thực hiện B, sau 1 khoảng thời gian B bị ngắt → thực hiện A, . Như vậy, bằng cách điều khiển ngắt mà bộ điều phối cĩ thể cho phép thực hiện xoay vịng nhiều tiến trình trong 1 khoảng thời gian gọi là kỹ thuật xoay vịng. 24
25. ◼ VD1: trong 1 máy tính thực hiện xoay vịng khoảng 50 tiến trình, khoảng thời gian thực hiện mỗi tiến trình khoảng 10 – 100 miligiây → cảm giác nhiều tiến trình được thực hiện đồng thời. ◼ VD2: Một máy tính đa người dùng, thì HĐH tạo ra mỗi người dùng 1 máy ảo được tạo ra theo cách phân chia thời gian như vậy. Ngồi ra các tiến trình cĩ thể cĩ sự ưu tiên khác nhau. 25
26. 3.2.3.Phân phối tài nguyên a. Điều phối tài nguyên ◼ Tài nguyên cĩ 2 loại: phân chia được và khơng phân chia được. (VD) ◼ Nguyên tắc: ◼ Tạo Bộ phân phối và thu hồi các tài nguyên ◼ Các ttiến trình trong mơi trường đa xử lý khơng được phép liên lạc trực tiếp với các ngoại vi mà phải thơng qua HĐH ◼ Gán cờ hiệu cho tài nguyên (0/1) 26
27. b. Deadlock ◼ Deadlock là gì? Đợi 1 sự kiện khơng bao giờ xảy ra. ◼ Ví dụ: ◼ Phân tích: Deadlock xuất hiện khi thoả cả 3 đk sau: 1. Cĩ sự cạnh tranh ở các tài nguyên khơng thể chia. 2. Những tài nguyên bị yêu cầu trên từng phần cơ bản; để kết thúc và nhận lại 1 số tài nguyên từ 1 tiến trình thì phải cung cấp cho nĩ 1 số tài nguyên khác. 3. Một lần 1 tài nguyên bị phân chia, nĩ khơng thể yêu cầu sử dụng lại. 27
28. Xử lý Deadlock ◼ Bỏ đi 1 tiến trình nào đĩ gây ra vấn đề trên. ◼ Chuyển các tài nguyên khơng phân chia → cĩ thể phân chia. VD: kỹ thuật Spooling khi in dữ liệu. 28
29. 3.3. Quản lý tiến trình Các máy tính ngày nay đều cĩ khả năng xử lý đồng thời nhiều chương trình, nhưng thiết bị phần cứng chỉ cĩ 1 cho nên HĐH thiết kế mơ hình song song giả lập để xử lý 1 lúc nhiều chương trình → mỗi chương trình này → Tiến trình. 29
30. Tiến trình (Process) ◼ Là ctrình đang xử lý ◼ Sở hữu 1 con trỏ lệnh, tập các thanh ghi, và các biến. ◼ Cần 1 số tài nguyên: CPU, memory, các tập tin, và thiết bị xuất/nhập. ◼ Khác với chương trình-xem như thực thể thụ động thì tiến trình xem như thực thể tích cực, cĩ thể tương tác, thay đổi trạng thái 30
31. Các trạng thái của ttrình ◼ Khởi tạo: ttrình được tạo lập ◼ Ready: ttrình chờ được cấp phát tài nguyên để xử lý ◼ Running: các lệnh của ttrình đang được xử lý. ◼ Blocked: ttrình chờ cấp phát tài nguyên, hay chờ 1 sự kiện xảy ra. ◼ Kết thúc: ttrình hồn tất xử lý. 31
32. Chuyển trạng thái của ttrình Khởi tạo Kết thúc (1) (5) (3) Ready Running (2) (6) (4) Blocked 32
33. Chuyển đổi trạng thái của ttrình ◼ (1): ttrình mới tạo được đưa vào hệ thống. ◼ (2): Bộ điều phối cấp phát cho ttrình 1 khoảng thời gian sử dụng CPU. ◼ (3): ttrình kết thúc. ◼ (4): ttrình yêu tài nguyên nhưng chưa được đáp ứng; hoặc phải chờ 1 sự kiện hay thao tác xuất/nhập. ◼ (5): Bộ điều phối chọn ttrình khác để cho xử lý. ◼ (6): tài nguyên yêu cầu đã sẵn sàng; hoặc sự kiện hay tao tác xuất/nhập đã hồn tất. 33
34. Điều phối tiến trình ◼ Chia sẻ thời gian – để chuyển đổi CPU qua lại giữa các ttrình. ◼ Bộ phân phối (dispatcher) ◼ Lựa chọn ttrình để xử lý tiếp theo. ◼ Chuyển ngữ cảnh (context). ◼ Mục tiêu điều phối (scheduling) ◼ Sự cơng bằng (fairness) ◼ Hiệu quả (efficiency) ◼ Thời gian đáp ứng hợp lý (response time) ◼ Thời gian lưu lại hệ thống (turnaround time) ◼ Thơng lượng tối đa (throughput) 34
35. Cơ chế điều phối của HĐH ◼ Điều phối độc quyền (preemptive) ◼ Ttrình nhận được CPU sẽ cĩ quyền độc chiếm CPU đến khi hồn tất xử lý hoặc tự nguyện giải phĩng CPU. ◼ Quyết định điều phối xảy ra khi: ◼ Ttrình chuyển từ tthái running sang blocked ◼ Ttrình kết thúc 35
36. Cơ chế điều phối của HĐH (tt) ◼ Điều phối khơng độc quyền (non-preemptive) ◼ Ttrình nhận được CPU vẫn được sử dụng CPU đến khi hồn tất xử lý hoặc tự nguyện giải phĩng CPU. ◼ Nhưng ttrình khác cĩ độ ưu tiên cĩ thể dành quyền sử dụng CPU. ◼ Quyết định điều phối xảy ra khi: ◼ Ttrình chuyển từ tthái running sang blocked ◼ Ttrình chuyền từ running sang ready ◼ Ttrình chuyền từ blocked sang ready ◼ Ttrình kết thúc 36
37. Interval timer/ interrupting clock ◼ HĐH sử dụng một bộ đếm thời gian / đồng hồ ngắt giờ ◼ Khoảng thời gian t thích hợp ứng với 1 lượt cấp phát CPU cho 1 ttrình. ◼ Sau khoảng thời gian t xảy ra ngắt báo hiệu hết thời gian xử lý của ttrình hiện hành. Khi đĩ, HĐH được kích hoạt, và bộ điều phối sẽ quyết định ttrình nào sẽ được cấp phát CPU trong lượt kế tiếp. 37
38. Độ ưu tiên của tiến trình ◼ Được gán bởi hệ thống hay gán tường minh bởi user. ◼ Độ ưu tiên tĩnh: khơng thay đổi bất kể sự biến động của mơi trường. ◼ Độ ưu tiên động: thay đổi theo thời gian và mơi trường xử lý 38
39. Tổ chức điều phối ◼ Danh sách sẵn sàng (ready list) chứa các ttrình đã được nạp vào bộ nhớ chính và ở trạng thái sẵn sàng (ready) tiếp nhận CPU. ◼ Danh sách chờ đợi (waiting list): chứa các ttrình chờ đợi 1 thao tác xuất nhập hồn tất, yêu cầu tài nguyên chưa được thoả mãn, yêu cầu tạm dừng ◼ Mỗi tài nguyên (tbị ngoại vi) cĩ danh sách chờ đợi riêng bao gồm các ttrình đang chờ được cấp tài nguyên đĩ. 39
40. Các danh sách điều phối head PCB2 PCB5 Ready list trail head PCB1 Resource 1 trail head PCB8 PCB8 Resource 2 trail 40
41. Sơ đồ chuyển đổi giữa các danh sách điều phối Ready list CPU I/O Waiting list Yêu cầu hết Ngắt Đợi 1 ngắt 41
42. Các cấp độ điều phối ◼ Điều phối theo tác vụ (job scheduling) ◼ Quyết định lựa chọn tác vụ nào đưa vào hệ thống và nạp những ttrình của tác vụ đĩ vào bộ nhớ chính. ◼ Tạo lập 1 ttrình hay cĩ 1 ttrình kết thúc: kích hoạt chức năng điều phối tác vụ mới. ◼ Chức năng điều phối tác vụ cĩ tần xuất hoạt động thấp do tính đa chương tương đối ổn định. ◼ Cần phân biệt ttrình theo hướng xuất/nhập hay hướng xử lý. ◼ Cân bằng hoạt động CPU và tbị ngoại vi: pha trộn hợp lý giữa các ttrình hướng xuất/nhập và hướng xử lý. 42
43. Các cấp độ điều phối (tt) ◼ Điều phối theo tiến trình (process scheduling) ◼ Quyết định chọn 1 ttrình ở trạng thái sẵn sàng. ◼ Cĩ tần xuất hoạt động cao do bị ngắt (đồng hồ, tbị ngoại vi ) ◼ Cấp độ điều phối trung gian: Kết hợp 2 cấp độ điều phối theo tác vụ và theo tiến trình 43
44. Các chiến lược điều phối ◼ Chiến lược FIFO ◼ Chiến lược phân phối xoay vịng (round robin) ◼ Chiến lược điều phối theo độ ưu tiên ◼ Chiến lược theo cơng việc ngắn nhất (shortest-Job- First) SJF ◼ Chiến lược điều phối theo nhiều mức độ ưu tiên 44
45. Khối điều khiển tiến trình ◼ Process Control Block –PCB ◼ HĐH quản lý tiến trình thơng qua PCB ◼ PCB là 1 cấu trúc gồm nhiều trường: ◼ Định danh tiến trình: Pid ◼ Trạng thái tiến trình: ◼ Ngữ cảnh ◼ Thơng tin giao tiếp ◼ Thơng tin thống kê 45
46. Khối điều khiển ttrình Định danh ttrình pid status Trạng thái ttrình Waiting/waiting list CPU-state-res Processor Ngữ cảnh của ttrình Main store Unit 1 Unit 2 Resource RCB 1 RCB 2 Created resource RCB 1 RCB 2 Parent PCB Thơng tin giao tiếp Progency PCB 1 PCB 2 Priority Thơng tin thống kê CPU time 46
47. Giải thích ◼ Định danh tiến trình giúp phân biệt các tiến trình khác nhau. ◼ Trạng thái tiến trình là tình trạng hiện tại của tiến trình. ◼ Ngữ cảnh tiến trình chứa các thơng tin về tài nguyên của tiến trình gồm: ◼ Trạng thái CPU: Registers, IP ◼ CPU trong trường hợp máy cĩ nhiều CPU ◼ Memory ◼ Tài nguyên sử dụng: danh sách các tài nguyên hệ thống mà tiến trình sử dụng ◼ Tài nguyên tạo lập: danh sách các tài nguyên được tiến trình tạo lập 47
48. ◼ Thơng tin giao tiếp: Thơng tin về quan hệ giữa tiến trình này vơí các tiến trình khác ◼ Tiến trình cha: Tạo ra tiến trình này ◼ Tiến trình con: Do nĩ tạo ra ◼ Độ ưu tiên: Để bộ điều phối xác định chế độ ưu tiên ◼ Thơng tin thống kê: Thơng tin thống kê hoạt động của tiến tình (thời gian sử dụng CPU, thời gian chờ, ) 48
49. Tiểu trình (thread) & Tiến trình (Process) ◼ Một tiến trình: Cĩ Khơng gian địa chỉ riêng, chỉ 1 dịng xử lý ◼ Các tiến trình độc lập liên lạc với nhau thơng qua cơ chế do HĐH cung cấp. Mong muốn nhiều dịng xử lý chia sẻ 1 khơng gian địa chỉ và các dịng xử lý hoạt động song song →Tiểu trình: • 1 đơn vị xử lý cơ bản • Sở hữu 1 con trỏ lệnh, tập các thanh ghi, 1 vùng nhớ stack riêng • Cĩ các trạng thái như tiến trình thật. • Các tiểu trình trong cùng tiến trình chia sẻ khơng gian địa chỉ chung 49
50. Phân bổ thơng tin lưu trữ ◼ Tiến trình ◼ Khơng gian địa chỉ ◼ Tài nguyên tồn cục ◼ Các thơng tin thống kê ◼ Tiểu trình ◼ Con trỏ lệnh + các thanh ghi, stack ◼ Tài nguyên cục bộ 50
51. 3.4. Một số Kiến trúc Hệ điều hành ◼ Đơn giản (Monolithic) ◼ Hạt nhân (Kernel) ◼ Phân lớp (Layered) ◼ Máy ảo (Virtual Machine) ◼ Hướng đối tượng (OOOS) ◼ Exokernel 51
52. Monolithic ◼ OS = Thư viện tiện ích ◼ Có thể tổ chức thành nhiều module : CPU scheduling, Mem Management, Device management . nhưng chỉ có 1 trong những module này hoạt động tại một thời điểm ◼ Đơn nhiệm ◼ Quyền điều khiển được chuyển đổi thông qua lời gọi hàm Khi tầm vóc phát triển hệ thống trở nên thiếu tin cậy. ◼ Ví dụ : MS-DOS, Ultrix (mature Unix) 52
53. Monolithic 53
54. Kernel ◼ OS = Kernel + System processes ◼ Kernel được bảo vệ ◼ Đa nhiệm ◼ Kernel chịu trách nhiệm phân chia thời gian sử dụng CPU, Giao tiếp giữa các tiến trình Chỉ có 2 mức kernel/non-kernel =>kernel lớn, thiếu tin cậy như trước Định nghĩa cứng các giao tiếp với ứng dụng trong kernel ◼ Ví dụ : Windows NT 54
55. Kernel 55
56. Layered ◼ OS = các lớp trừu tượng hoá một tác vụ quản lý ◼ Lớp trên được sử dụng các hàm xử lýù tài nguyên thuộc tác vụ do lớp dưới cung cấp Khó xác định được các lớp xử lý rạch ròi, thứ tự lớp ? Xếp lớp theo hàm xử lý , thay vì tác vụ ◼ Ví dụ : THE , MULTICS 56
57. Layered 57
58. Virtual Machine ◼ OS = Virtualizing kernel + virtual machines ◼ Virtual machine = physical hardware ◼ Virtualizing kernel tạo ra nhiều VM trên 1 máy tính. ◼ Process interface = hardware interface Ưu điểm : Môi trường thuận lợi cho sự tương thích (compatibility) Tăng tính an toàn hệ thống do cung cấp các VM độc lập. Dễ phát triển các HĐH đơn nhiệm cho mỗi VM Khuyết điểm: Phức tạp cho việc giả lặp (transput, add translation ) ◼ Ví dụ : CMS(conversational Monitor System) trên VM/370 (hỗ trợ hardware) 58
59. Virtual Machine 59
60. ◼Nĩi thêm về các chiến lược điều phối tiến trình (đọc thêm) 60
61. Chiến lược FIFO ◼ CPU cấp cho tiến trình đầu tiên trong ready list. Tiến trình Thời điểm vào Thời gian xử lý P1 0 24 P2 1 3 P3 2 3 P1 P2 P3 0 24 27 30 Thời gian chờ để được xử lý: P1 -> 0; P2-> 24 -1 = 23 ; P3=24 + 3 -2 Thời gian chờ trung bình: (0+23+25)/3 = 16 ms 61
62. Chiến lược FIFO (tt) ◼ Thảo luận: ◼ Thời gian chờ trung bình khơng đạt cực tiểu ◼ Cĩ thể xảy ra hiện tượng tích luỹ thời gian chờ ◼ Khơng phù hợp với HĐH phân chia theo thời gian 62
63. Chiến lược round robin ◼ Bộ điều phối lần lượt cấp phát cho từng tiến trình trong ready list 1 khoảng thời gian sử dụng CPU là quantum. ◼ Hết thời gian quantum mà ttrình chưa hồn tất, ttrình đưa trở lại vào cuối ready list. 63
64. Chiến lược round robin (tt) Tiến trình Thời điểm vào Thời gian xử lý P1 0 24 P2 1 3 P3 2 3 Quantum= 4ms P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30 ◼ Thời gian chời trung bình: (0+6+3+5)/3=4,66ms 64
65. Chiến lược round robin (tt) ◼ n ttrình trong ready list; Quantum q ◼ Mỗi ttrình khơng đợi quá (n-1)q đvị thời gian để đến lượt nhận CPU. ◼ Thao luận: ◼ Độ dài quantum ? ◼ bé: phát sinh nhiều chuyển đổi giữa các ttrình ◼ Lớn: tăng thời gian phản hồi, giảm khả năng tương tác. 65
66. Chiến lược điều phối theo độ ưu tiên ◼ Gán độ ưu tiên cho mỗi ttrình ◼ Ttrình cĩ độ ưu tiên cao nhất sẽ được chọn. ◼ Độ ưu tiên xác định ◼ đ/nghĩa nội tại (e.g. giới hạn thời gian, nhu cầu bộ nhớ, ) ◼ nhờ yếu tố bên ngồi ( e.g. tầm quan trọng của ttrình, loại user sỡ hữu ttrình) ◼ Cĩ thể hoạt động theo nguyên tắc độc quyền hay khơng độc quyền. 66
67. Chiến lược điều phối theo độ ưu tiên (tt) ◼ Khi ttrình được đưa vào ready list ◼ Trong chế độ khơng độc quyền: so sánh độ ưu tiên với ttrình đang được xử lý hiện hành nếu độ ưu tiên cao hơn -> cấp phát CPU cho ttrình mới. ◼ Trong chế độ độc quyền: chèn ttrình mới vào ready list. Tiến trình độ ưu tiên Thời gian xử lý P1 3 24 P2 1 3 P3 2 3 P2 P3 P1 Giải thuật độ quyền 0 4 7 30 67
68. Chiến lược điều phối theo độ ưu tiên (tt) ◼ Thảo luận: ◼ Trình trạng đĩi CPU (starvation): ttrình cĩ độ ưu tiên thấp chờ đợi vơ thời hạn. ◼ Khắc phục giảm độ ưu tiên của các ttrình cĩ độ ưu tiên cao sau mỗi ngắt đồng hồ. độ ưu tiên của ttrình giảm xuống thấp hơn ttrình cĩ độ ưu tiên cao thứ nhì -> chuyển đổi quyền sử dụng CPU ( “lão hố” (aging) ttrình). 68
69. Chiến lược theo cơng việc ngắn nhất (shortest-Job-First) SJF ◼ Giải thuật đặc biệt của giải thuật điều phối theo độ ưu tiên ◼ Độ ưu tiên p =1/t; t: thời gian xử lý yêu cầu ◼ Giải thuật này cĩ thể độc quyền hay khơng độc quyền. ◼ Khơng độc quyền: dừng ttrình hiện hành, khi cĩ 1 ttrình mới cĩ độ ưu tiên cao hơn vào ready list. ◼ Độc quyền: ttrình hiện hành tiếp tục xử lý. 69
70. Chiến lược theo cơng việc ngắn nhất (shortest-Job-First) SJF (tt) Tiến trình Thời gian xử lý P1 6 P2 8 P3 7 P4 3 SJF độc quyền: P4 ->P1->P3->P2 Thời gian chờ tbình: (3+16+9+0)/3 =7ms ◼ Thảo luận ◼ Thời gian chờ trung bình đạt cực tiểu ◼ Làm sao biết thời gian yêu cầu cịn lại xử lý ? 70
71. Chiến lược theo cơng việc ngắn nhất (shortest-Job-First) SJF (tt) ◼ Dự đốn thời gian xử lý cịn lại:  n+1 = tn + (1+ ) n 0 1 71
72. Chiến lược điều phối theo nhiều mức độ ưu tiên ◼ Phân lớp các ttrình tuỳ theo độ ưu tiên của chúng. -> cách thức điều phối thích hợp cho từng nhĩm. ◼ Ready list được phân thành các list riêng biệt theo cấp độ ưu tiên. ◼ Ttrình trong list ở cấp độ ưu tiên i chỉ được cấp phát CPU khi các list ở cấp ưu tiên lớn hơn i đã trống. 72
73. Chiến lược điều phối theo nhiều mức độ ưu tiên (tt) ◼ 1 ttrình gán vĩnh viễn cho 1 list ở cấp ưu tiên i; ttrình khơng chuyển giữa các lists => Giảm chi điều phối, thiếu linh động và cĩ thể dẫn đến “đĩi CPU”. ◼ Xây dựng giải thuật điều phối nhiều cấp ưu tiên và xoay vịng. ◼ 1 ttrình từ list cĩ độ ưu tiên cao xuống list cĩ độ ưu tiên thấp hơn sau mỗi lần sử dụng CPU. 1 ttrình từ list cĩ độ ưu tiên thấp -> cao hơn. ◼ Các tham số liên quan. 73
74. Tĩm tắt chương & câu hỏi ◼ Chức năng ? ◼ (Cấu trúc) Các thành phần chính ? ◼ Việc điều phối tiến trình ? Các chiến lược ? 74
75. Các chủ đề thảo luận thêm ◼ - Cơ chế quản lý bộ nhớ của Hệ điều hành. ◼ - Cơ chế quản lý nhập xuất của HĐH. 75