Bài giảng Kiến trúc máy tính và hệ điều hành - Chương 6: Tổ chức và hoạt động của hệ điều hành

Nội dung text: Bài giảng Kiến trúc máy tính và hệ điều hành - Chương 6: Tổ chức và hoạt động của hệ điều hành

1. Chương 6 TỔ CHỨC VÀ HOẠT ĐỘNG CỦA HỆ ĐIỀU HÀNH 1 1
2. Nội dung 1. Tiến trình và tiểu trình. 2. Lập lịch tiến trình. 3. Quản lý bộ nhớ. 4. Bộ nhớ ảo. 2
3. Tiến trình  Tiến trình (process): Là một chương trình đang thực thi  Một tiến trình bao gồm Text section (program code), data section (chứa global variables)  Hoạt động hiện thời: program counter (PC), process status word (PSW), stack pointer (SP), memory management registers 3
4. Tiến trình Các bước nạp chương trình vào bộ nhớ 4
5. Tiến trình  Các bước hệ điều hành khởi tạo tiến trình:  Cấp phát một định danh duy nhất (process number hay process identifier, pid) cho quá trình  Cấp phát khơng gian nhớ để nạp quá trình  Khơi tạo khởi dữ liệu Process Control Block (PCB) cho quá trình PCB là nơi hệ điều hành lưu các thơng tin về quá trình  Thiết lập các mối liên hệ cần thiết (vd: sắp PCB vào hàng đợi định thời, ) 5
6. Tiến trình  new: tiến trình vừa được tạo  ready: tiến trình đã cĩ đủ tài nguyên, chỉ cịn cần CPU  running: các lệnh của tiến trình đang được thực thi  waiting: hay là blocked, tiến trình đợi I/O hồn tất, tín hiệu.  terminated: tiến trình đã kết thúc. 6
7. Tiến trình Chuyển đổi giữa các trạng thái của tiến trình terminated new admit dispatch exit ready running interrupt I/O or event I/O or completion event wait waiting 7
8. Tiến trình  Mỗi tiến trình trong hệ thống đều được cấp phát một Process Control Block (PCB)  PCB là một trong các cấu trúc dữ liệu quan trọng nhất của hệ điều hành Ví dụ layout của một PCB: (trường pointer dùng để liên kết các PCBs thành một linked list) 8
9. Tiến trình Chuyển ngữ cảnh (Context switch)  Ngữ cảnh (context) của một tiến trình là trạng thái của tiến trình  Ngữ cảnh của tiến trình được biểu diễn trong PCB của nĩ  Chuyển ngữ cảnh (context switch) là cơng việc giao CPU cho tiến trình khác. Khi đĩ cần:  Lưu ngữ cảnh của tiến trình cũ vào PCB của nĩ  Nạp ngữ cảnh từ PCB của tiến trình mới để tiến trình mới thực thi 9
10. Tiến trình 10
11. Tiến trình Yêu cầu đối với hệ điều hành về quản lý tiến trình  Hỗ trợ sự thực thi luân phiên giữa nhiều tiến trình  Hiệu suất sử dụng CPU  Thời gian đáp ứng  Phân phối tài nguyên hệ thống hợp lý  Tránh deadlock, trì hỗn vơ hạn định,  Cung cấp cơ chế giao tiếp và đồng bộ hoạt động các tiến trình  Cung cấp cơ chế hỗ trợ user tạo/kết thúc tiến trình 11
12. Tiến trình Yêu cầu đối với hệ điều hành về quản lý tiến trình  Hỗ trợ sự thực thi luân phiên giữa nhiều tiến trình  Hiệu suất sử dụng CPU  Thời gian đáp ứng  Phân phối tài nguyên hệ thống hợp lý  Tránh deadlock, trì hỗn vơ hạn định,  Cung cấp cơ chế giao tiếp và đồng bộ hoạt động các tiến trình  Cung cấp cơ chế hỗ trợ user tạo/kết thúc tiến trình 12
13. Tiểu trình  Khái niệm tiến trình truyền thống. Tiến trình gồm:  Khơng gian địa chỉ (text section, data section)  Một luồng thực thi duy nhất (single thread of execution)  Program counter  Các register  Stack  Các tài nguyên khác (các open file, các tiến trình con, ) 13
14. Tiểu trình  Mở rộng khái niệm tiến trình truyền thống bằng cách hiện thực nhiều luồng thực thi trong cùng một mơi trường của tiến trình. Tiến trình gồm:  Khơng gian địa chỉ (text section, data section)  Một hay nhiều luồng thực thi (thread of execution), mỗi luồng thực thi (thread) cĩ riêng:  Program counter  Các register  Stack  Các tài nguyên khác (các open file, các tiến trình con, ) 14
15. Tiểu trình  Các tiểu trình trong cùng một tiến trình chia sẻ code section, data section và tài nguyên khác (các file đang mở, ) của tiến trình.  Tiến trình đa luồng (multithreaded process) là tiến trình cĩ nhiều tiểu trình. 15
16. Tiểu trình Ưu điểm của đa tiểu trình  Tính đáp ứng (responsiveness) cao cho các ứng dụng tương tác multithreaded.  Chia sẻ tài nguyên (resource sharing).  Tiết kiệm chi phí hệ thống (lợi ích kinh tế)  Chi phí tạo/quản lý tiến trình nhỏ.  Chi phí chuyển ngữ cảnh giữa các thread nhỏ.  Tận dụng kiên trúc đa xử lý (multiprocessor)  Mỗi tiến trình chạy trên một processor riêng, do đĩ tăng mức độ song song của chương trình. 16
17. Tiểu trình User Thread  Một thư viện tiểu trình (thread library, run-time system) được hiện thực trong user space để hỗ trợ các tác vụ lên thread  Thư viện thread cung cấp các hàm khởi tạo, định thời và quản lý thread như  thread_create,  thread_exit,  thread_wait,  thread_yield.  Thư viện tiểu trình dùng Thread Control Block (TCB) để lưu trạng thái của user thread (program counter, các register, stack)  Kernel khơng biết sự cĩ mặt của user thread 17
18. Tiểu trình User Thread  Một thư viện tiểu trình (thread library, run-time system) được hiện thực trong user space để hỗ trợ các tác vụ lên thread  Thư viện thread cung cấp các hàm khởi tạo, định thời và quản lý thread như  thread_create,  thread_exit,  thread_wait,  thread_yield.  Thư viện tiểu trình dùng Thread Control Block (TCB) để lưu trạng thái của user thread (program counter, các register, stack)  Kernel khơng biết sự cĩ mặt của user thread 18
19. Tiểu trình Kernel Thread  Cơ chế multithreading được hệ điều hành trực tiếp hỗ trợ:  Kernel quản lý cả process và các thread  Việc định thời CPU được kernel thực hiện trên thread 19
20. Tiểu trình Kernel Thread  Cơ chế multithreading được hỗ trợ bởi kernel  Khởi tạo và quản lý các thread chậm hơn  Tận dụng được lợi thế của kiến trúc multiprocessor  Thread bị blocked khơng kéo theo các thread khác bị blocked.  Một số hệ thống multithreading (multitasking)  Windows 9x/NT/2000/XP/7/10  Solaris  Linux 20
21. Tiểu trình  Mộ số mơ hình hiện thực thread Mơ hình many-to-one Mơ hình one-to-one Mơ hình many-to-many 21
22. Tiểu trình Mơ hình many – to – one  Nhiều user-level thread “chia sẻ” một kernel thread để thực thi  Việc quản lý thread được thực hiện thơng qua các hàm của một thread library được gọi ở user level.  Blocking problem: Khi một thread trở nên blocked thì kernel thread cũng trở nên blocked, do đĩ mỗi thread khác của process cũng sẽ trở nên blocked.  Cĩ thể được hiện thực đối với hầu hết các hệ điều hành. kernel thread 22
23. Tiểu trình Mơ hình one – to – one  Mỗi user-level thread thực thi thơng qua một kernel thread riêng của nĩ  Mỗi khi một user thread được tạo ra thì cũng cần tạo một kernel thread tương ứng  Hệ điều hành phải cĩ cơ chế cung cấp được nhiều kernel thread cho một tiến trình kernel thread 23
24. Tiểu trình Mơ hình many – to – many  Nhiều user-level thread được phân chia thực thi (multiplexed) trên một số kernel thread.  Tránh được một số khuyết điểm của hai mơ hình many- to-one và one-to-one  Ví dụ  Solaris 2  Windows NT/2000 với package ThreadFiber kernel thread 24
25. Lập lịch tiến trình  Tại sao phải lập lịch?  Multiprogramming  Cĩ nhiều tiến trình phải thực thi luân phiên nhau,  Mục tiêu: cực đại hiệu suất sử dụng của CPU.  Time-sharing  Cho phép users tương tác với tiến trình đang thực thi,  Mục tiêu: tối thiểu thời gian đáp ứng  Một số khái niệm cơ bản  Các bộ định thời (scheduler)  Các hàng đợi định thời (scheduling queue) 25
26. Lập lịch tiến trình Các hàng đợi định thời  Job queue  Ready queue  Device queues  26
27. Lập lịch tiến trình Thêm medium-term scheduling  Đơi khi hệ điều hành (như time-sharing system) cĩ thêm medium-term scheduling để điều chỉnh mức độ multiprogramming của hệ thống.  Medium-term scheduler  Chuyển tiến trình từ bộ nhớ sang đĩa (swap out)  Chuyển tiến trình từ đĩa vào bộ nhớ (swap in) 27
28. Lập lịch tiến trình Một số khái niệm cơ bản  Chu kỳ CPU-I/O: gồm chu kỳ thực thi CPU (CPU burst) và chu kỳ chờ đợi vào ra (I/O burst).  CPU-bound process cĩ thời gian sử dụng CPU nhiều hơn thời gian sử dụng I/O.  I/O-bound process dùng phần lớn thời gian để đợi I/O. 28
29. Lập lịch tiến trình  Trong các hệ thống multitasking  Tại một thời điểm trong bộ nhớ cĩ nhiều process  Tại mỗi thời điểm chỉ cĩ một process được thực thi  Do đĩ, cần phải giải quyết vấn đề phân chia, lựa chọn process thực thi sao cho được hiệu quả nhất. Cần cĩ chiến lược lập lịch cho các tiến trình. 29
30. Thao tác trên 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 (change priority)
31. Tạo lập tiến trình  Đị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.
32. 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
33. Cấp phát tài nguyên cho tiến trình Khối quản lý tài nguyên Các mục tiêu của kỹ thuật cấp phát :  Bảo đảm một số lượng hợp lệ các tiến trình truy xuất đồng thời đến các tài nguyên khơng chia sẻ được.  Cấp phát tài nguyên cho tiến trình cĩ yêu cầu trong một khoảng thời gian trì hỗn cĩ thể chấp nhận được.  Tối ưu hĩa sự sử dụng tài nguyên.
34. Điều phối tiến trình Hệ điều hành điều phối tiến trình thơng qua bộ điều phối (scheduler) và bộ phân phối (dispatcher). Bộ điều phối sử dụng một giải thuật thích hợp để lựa chọn tiến trình được xử lý tiếp theo. Bộ phân phối chịu trách nhiệm cập nhật ngữ cảnh của tiến trình bị tạm ngưng và trao CPU cho tiến trình được chọn bởi bộ điều phối để tiến trình thực thi. Mục tiêu điều phối  Sự cơng bằng ( Fairness)  Tính hiệu qủa (Efficiency)  Thời gian đáp ứng hợp lý (Response time)  Thời gian lưu lại trong hệ thống (TurnaroundTime)  Thơng lượng tối đa (Throughput )
35. Các đặc điểm của tiến trình  Tính hướng xuất / nhập của tiến trình ( I/O- boundedness):  Nhiều lượt sử dụng CPU, mỗi lượt dùng thời gian ngắn.  Tính hướng xử lý của tiến trình ( CPU-boundedness):  Ít lượt sử dụng CPU, mỗi lượt dùng thời gian dài.  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 để hồn tất
36. Các nguyên lý điều phối  Điều phối độc quyền (preemptive)  Độc chiếm CPU  Khơng thích hợp với các hệ thống nhiều người dùng  Điều phối khơng độc quyền (nopreemptive)  Tránh được tình trạng một tiến trình độc chiếm CPU  cĩ thể dẫn đến các mâu thuẫn trong truy xuất -> cần phương pháp đồng bộ hĩa thích hợp để giải quyết.  phức tạp trong việc phân định độ ưu tiên  phát sinh thêm chi phí khi chuyển đổi CPU qua lại giữa các tiến trình
37. Thời điểm thực hiện điều phối running -> blocked Ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc running -> ready Ví dụ xảy ra một ngắt. blocked -> ready Ví dụ một thao tác nhập/xuất hồn tất. Tiến trình kết thúc. Tiến trình cĩ độ ưu tiên cao hơn xuất hiện chỉ áp dụng đối với điều phối khơng độc quyền
38. Tổ chức điều phối - Các danh sách điều phối  Danh sách tác vụ (job list)  Danh sách sẵn sàng (ready list)  Danh sách chờ đợi (waiting list) ds sẵn sàng CPU Yêu cầu I/O ds đợi tài nguyên tài nguyên Hết thời gian Ngắt xảy ra Đợi 1 ngắt
39. Các loại điều phối  Điều phối tác vụ (job scheduling)  Chọn tác vụ nào được đưa vào bộ nhớ chính để thực hiện  Quyết định mức độ đa chương  Tần suất hoạt động thấp  Điều phối tiến trình (process scheduling)  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 ) để cấp phát CPU cho tiến trình đĩ thực hiện  Cĩ tần suất hoạt động cao (1 lần/100 ms).  Sử dụng các thuật tốn tốt nhất
40. Các thuật tốn điều phối  Thuật tốn FIFO  Thuật tốn phân phối xoay vịng (Round Robin)  Thuật tốn độ ưu tiên  Thuật tốn cơng việc ngắn nhất (Shortest-job-first SJF)  Thuật tốn nhiều mức độ ưu tiên  Chiến lược điều phối xổ số (Lottery)
41. Thuật tốn FIFO Điều phối theo nguyên tắc độc quyền Tiến trình Thời điểm vào RL Thời gian xử lý P1 P2 P3 P1 0 24 0 24 27 P2 1 3 30 P3 2 3 Thời gian chờ đợi được xử lý là 0 đối với P1, (24 -1) với P2 và (27-2) với P3. Thời gian chờ trung bình là ( 0+23+25)/3 = 16 miliseconds.
42. Thuật tốn phân phối xoay vịng (Round Robin) Tiến trình Thời điểm vào RL Thời gian xử lý P1 0 24 P2 1 3 P3 2 3 P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30 quantum là 4 miliseconds, Thời gian chờ đợi trung bình sẽ là (6+3+5)/3 = 4.66 milisecondes.
43. Thuật tốn độ ưu tiên Độ ưu tiên P2 > P3> P1 Tiến Thời điểm Độ ưu Thời gian Thuật giải độ ưu tiên độc quyền trình vào RL tiên xử lý P1 P2 P3 P1 0 3 24 0 24 27 P2 1 1 3 30 P3 2 2 3 Thời gian chờ đợi trung bình sẽ là (0+23+25)/3 =16 milisecondes Thuật giải độ ưu tiên khơng độc quyền P1 P2 P3 P1 0 1 4 7 30 Thời gian chờ đợi trung bình sẽ là (6+0+2)/3 = 2.7 milisecondes
44. Thuật tốn cơng việc ngắn nhất (Shortest-job-first SJF) t: thời gian xử lý mà tiến trình cịn yêu cầu Độ ưu tiên p = 1/t Thuật giải SJF độc quyền Tiến Thời điểm Thời gian P1 P4 P3 P2 trình vào RL xử lý 0 6 8 12 P1 0 6 20 P2 1 8 Thời gian chờ đợi trung bình sẽ là (0+11+6+3)/4 P3 2 4 = 5 milisecondes P4 3 2 Thuật giải SJF khơng độc quyền P1 P4 P1 P3 P2 0 3 5 8 12 20 Thời gian chờ đợi trung bình sẽ là (2+11+6+0)/4 = 4.75 milisecondes
45. Thuật tốn nhiều mức độ ưu tiên  Danh sách sẵn sàng được chia thành nhiều danh sách.  Mỗi danh sách gồm các tiến trình cĩ cùng độ ưu tiên và được áp dụng một giải thuật điều phối riêng
46. Điều phối theo nhiều mức ưu tiên xoay vịng (Multilevel Feedback)
47. Chiến lược điều phối xổ số (Lottery)  Mỗi tiến trình được cấp một “vé số”.  HĐH 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.  Là giải thuật độc quyền.  Đơn giản, chi phí thấp, bảo đảm tính cơng bằng cho các tiến trình.
48. Bộ nhớ thực  Khái niệm  Quản lý bộ nhớ là cơng việc của hệ điều hành với sự hỗ trợ của phần cứng nhằm phân phối, sắp xếp các process trong bộ nhớ sao cho hiệu quả.  Mục tiêu cần đạt được là nạp càng nhiều process vào bộ nhớ càng tốt (gia tăng mức độ đa chương trình) 48
49. Bộ nhớ thực  Khái niệm  Các yêu cầu đối với việc quản lý bộ nhớ  Cấp phát bộ nhớ cho các process  Tái định vị (relocation): khi swapping,  Bảo vệ: phải kiểm tra truy xuất bộ nhớ cĩ hợp lệ khơng.  Chia sẻ: cho phép các process chia sẻ vùng nhớ chung.  Kết gắn địa chỉ nhớ luận lý của user vào địa chỉ thực. 49
50. Bộ nhớ thực  Địa chỉ nhớ  Địa chỉ vật lý (physical address - địa chỉ thực): một vị trí thực trong bộ nhớ chính.  Địa chỉ luận lý (logical address): một vị trí nhớ được diễn tả trong một chương trình  Trình biên dịch (compiler) tạo ra mã lệnh chương trình trong đĩ mỗi tham chiếu bộ nhớ đều là địa chỉ luận lý  Địa chỉ tương đối (relative address): kiểu địa chỉ luận lý trong đĩ các địa chỉ được biểu diễn tương đối so với một vị trí xác định nào đĩ trong chương trình. Ví dụ: 12 byte so với vị trí bắt đầu chương trình,  Địa chỉ tuyệt đối (absolute address): địa chỉ tương đương với địa chỉ thực 50
51. Bộ nhớ thực  Địa chỉ nhớ  Khi một lệnh được thực thi, các tham chiếu đến địa chỉ luận lý phải được chuyển đổi thành địa chỉ thực.  Thao tác chuyển đổi thường cĩ sự hỗ trợ của phần cứng để đạt hiệu suất cao 51
52. Bộ nhớ thực  Chuyển đổi địa chỉ  Là quá trình ánh xạ một địa chỉ từ khơng gian địa chỉ nay sang khơng gian địa chỉ khác.  Biểu diễn địa chỉ nhớ Trong source code: symbolic (các biến, hằng, pointer, ) Thời điểm biên dịch: thường là địa chỉ tương đối Ví dụ: a ở vị trí 14 bytes so với vị trí bắt đầu của module. Thời điểm linking/loading: cĩ thể là địa chỉ thực. Ví dụ: dữ liệu nằm tại địa chỉ bộ nhớ thực 1212 52
53. Bộ nhớ thực  Chuyển đổi địa chỉ  Địa chỉ lệnh (instruction) và dữ liệu (data) được chuyển đổi thành địa chỉ thực cĩ thể xảy ra tại ba thời điểm khác nhau  Compile time: nếu biết trước địa chỉ bộ nhớ của chương trình thì cĩ thể gán địa chỉ tuyệt đối lúc biên dịch. – Khuyết điểm: phải biên dịch lại nếu thay đổi địa chỉ nạp chương trình  Load time: tại thời điểm biên dịch, nếu chưa biết tiến trình sẽ nằm ở đâu trong bộ nhớ thì compiler phải sinh mã địa chỉ tương đối. Vào thời điểm loading, loader phải chuyển đổi địa chỉ tương đố thành địa chỉ thực dựa trên một địa chỉ nền (base address). – Địa chỉ thực được tính tốn vào thời điểm nạp chương trình phải tiến hành reload nếu địa chỉ nền thay đổi. 53
54. Bộ nhớ thực  Chuyển đổi địa chỉ  Execution time: khi trong quá trình thực thi, process cĩ thể được di chuyển từ segment nay sang segment khác trong bộ nhớ thì quá trình chuyển đổi địa chỉ được trì hỗn đến thời điểm thực thi – CPU tạo ra địa chỉ luận lý cho process – Phần cứng cần hỗ trợ cho việc ánh xạ địa chỉ. Ví dụ: trường hợp địa chỉ luận lý là tương đối thì cĩ thể dùng thanh ghi base và limit, – Sử dụng trong đa số các Hệ điều hành đa dụng (general-purpose) trong đĩ cĩ các cơ chế swapping, paging, segmentation. 54
55. Bộ nhớ thực  Cơ chế Overlay  Tại mỗi thời điểm, chỉ giữ lại trong bộ nhớ những lệnh hoặc dữ liệu cần thiết, giải phĩng các lệnh/dữ liệu chưa hoặc khơng cần dùng đến.  Cơ chế này rất hữu dụng khi kích thước một process lớn hơn khơng gian bộ nhớ cấp cho process đĩ.  Cơ chế này được điều khiển bởi người sử dụng (thơng qua sự hỗ trợ của các thư viện lập trình) chứ khơng cần sự hỗ trợ của hệ điều hành 55
56. Bộ nhớ thực  Cơ chế Swapping  Một process cĩ thể tạm thời bị swap ra khỏi bộ nhớ chính và lưu trên một hệ thống lưu trữ phụ. Sau đĩ, process cĩ thể được nạp lại vào bộ nhớ để tiếp tục quá trình thực thi. Ví dụ Round-robin: swap out P1 (vừa dùng hết quantum của nĩ), swap in P2 , thực thi P3 , Roll out, roll in: dùng trong cơ chế điều phối theo độ ưu tiên (priority-based scheduling)  Process cĩ độ ưu tiên thấp hơn sẽ bị swap out nhường chỗ cho process cĩ độ ưu tiên cao hơn mới đến được nạp vào bộ nhớ để thực thi 56
57. Bộ nhớ thực  Phân mảnh  Phân mảnh ngoại (external fragmentation)  Kích thước bộ nhớ cịn trống đủ để đáp ứng một yêu cầu, nhưng bộ nhớ này khơng liên tục cĩ thể dùng cơ chế kết khối (compaction) để gom lại thành vùng nhớ liên tuc.  Phân mảnh nội (internal fragmentation)  Kích thước vùng nhớ được cấp phát cĩ thể hơi lớn hơn vùng nhớ yêu cầu.  Phân mảnh nội xảy ra khi bộ nhớ thực được chia thành các khối kích thước cố định và các process được cấp phát theo đơn vị khối. Ví dụ: cơ chế phân trang (paging). 57
58. Bộ nhớ thực  Phân vùng  Khi khởi động hệ thống, bộ nhớ chính được chia thành nhiều phần rời nhau gọi là các partition, cĩ kích thước bằng nhau hoặc khác nhau 58
59. Bộ nhớ thực Phân vùng – vùng cố định  Process nào cĩ kích thước nhỏ hơn hoặc bằng kích thước partition thì cĩ thể được nạp vào partition đĩ.  Nếu chương trình cĩ kích thước lớn hơn partition thì phải dùng cơ chế overlay.  Khơng hiệu quả do bị phân mảnh nội: một chương trình dù lớn hay nhỏ đều được cấp phát trọn một partition 59
60. Bộ nhớ thực  Phân vùng cố định - Chiến lược sắp xếp  Partition cĩ kích thước bằng nhau  Cịn partition trống process mới được nạp vào partition đĩ  Khơng cịn partition trống, nhưng đĩ cĩ process đang bị blocked swap process đĩ ra bộ nhớ phụ nhường chỗ cho process mới  Partition cĩ kích thước khơng bằng nhau:  Giải pháp 1 – Gán mỗi process vào partition nhỏ nhất phù hợp với nĩ – Cĩ hàng đợi cho mỗi partition – Giảm thiểu phân mảnh nội  Giải pháp 2 – Chỉ cĩ một hàng đợi chung cho mọi partition – Khi cần nạp một process vào bộ nhớ chính chọn partition nhỏ nhất cịn trống 60
61. Bộ nhớ thực  Phân vùng – vùng động  Số lượng partition khơng cố định và partition cĩ thể cĩ kích thước khác nhau  Mỗi process được cấp phát chính xác dung lượng bộ nhớ cần thiết  Gây ra hiện tượng phân mảnh ngồi 61
62. Bộ nhớ thực  Phân vùng động - Chiến lược sắp xếp  Dùng để quyết định cấp phát khối bộ nhớ trống nào cho một process  Mục tiêu: giảm chi phí kết khối (compaction)  Các chiến lược placement:  Best-fit: chọn khối nhớ trống nhỏ nhất  First-fit: chọn khối nhớ trống phù hợp đầu tiên kể từ đầu bộ nhớ  Next-fit: chọn khối nhớ trống phù hợp đầu tiên kể từ vị trí cấp phát cuối cùng  Worst-fit: chọn khối nhớ trống lớn nhất 62
63. Bộ nhớ ảo Khái niệm  Bộ nhớ ảo (virtual memory) Cơ chế được hiện thực trong hệ điều hành để cho phép thực thi một tiến trình mà chỉ cần giữ trong bộ nhớ chính một phần của khơng gian địa chỉ luận lý của nĩ, cịn phần cịn lại được giữ trên bộ nhớ phụ (đĩa cứng).  Ưu điểm của bộ nhớ ảo Số lượng process trong bộ nhớ nhiều hơn Một process cĩ thể thực thi ngay cả khi kích thước của nĩ lớn hơn bộ nhớ thực 63
64. Bộ nhớ ảo Khái niệm  Thơng thường phần khơng gian địa chỉ luận lý của tiến trình, nếu chưa cần nạp vào bộ nhớ chính sẽ được giữ ở một vùng đặc biệt trên đĩa gọi là khơng gian tráo đổi (swap space). Ví dụ:  swap partition trong Linux  file pagefile.sys trong Windows 2K 64
65. Bộ nhớ ảo Hiện thực bộ nhớ ảo  Phần cứng quản lý bộ nhớ phải hỗ trợ phân trang và/hoặc phân đoạn  Hệ điều hành phải quản lý sự di chuyển của trang/đoạn giữa bộ nhớ chính và bộ nhớ thứ cấp 65
66. Bộ nhớ ảo Cơ chế phân trang  Cho phép khơng gian địa chỉ thực (physical address space) của một process cĩ thể khơng liên tục nhau.  Bộ nhớ thực được chia thành các khối cố định và cĩ kích thước bằng nhau gọi là frame.  Thơng thường kích thước của frame là lũy thừa của 2, từ khoảng 512 byte đến 16MB.  Bộ nhớ luận lý (logical memory) hay khơng gian địa chỉ luận lý là tập mọi địa chỉ luận lý mà một chương trình bất kỳ cĩ thể sinh ra.  Bộ nhớ luận lý cũng được chia thành các khối cố định cĩ cùng kích thước gọi là trang nhớ (page). 66
67. Bộ nhớ ảo Cơ chế phân trang  Frame và trang nhớ cĩ kích thước bằng nhau.  Hệ điều hành phải thiết lập một bảng phân trang (page table) để ánh xạ địa chỉ luận lý thành địa chỉ thực  Mỗi process cĩ một bảng phân trang, được quản lý bằng một con trỏ lưu giữ trong PCB. Cơng việc thiết lập bằng phân trang cho process là một phần của chuyển ngữ cảnh  Cơ chế phân trang khiến bộ nhớ bị phân mảnh nội, tuy nhiên lại khắc phục được phân mảnh ngoại. 67
68. Bộ nhớ ảo Cơ chế phân đoạn  Mơt chương trình cấu thành từ nhiều đoạn (segment). Mỗi đoạn là một đơn vị luận lý của chương trình, như:  Main program, procedure, function  Local variables, global variables, common block, stack, symbol table, arrays,  Thơng thường, một chương trình được biên dịch. Trình biên dịch sẽ tự động xây dựng các đoạn.  Trình Loader sẽ gán mỗi đoạn một số định danh riêng 68
69. Bộ nhớ ảo Phần cứng hỗ trợ bộ nhớ ảo  Mỗi mục của bảng phân trang cĩ thêm các bit trạng thái đặc biệt:  Present bit = 1 trang hợp lệ, đang trong bộ nhớ = 0 trang khơng hợp lệ/khơng trong bộ nhớ  Modified bit: cho biết trang cĩ thay đổi kể từ khi được nạp vào bộ nhớ hay khơng 69
70. Bộ nhớ ảo Hiện thực bộ nhớ ảo  Demand paging: các trang của tiến trình chỉ được nạp vào bộ nhớ chính khi được yêu cầu.  Khi cĩ tham chiếu đến một trang khơng cĩ trong bộ nhớ chính (present bit = 0) thì phần cứng sẽ gây ra một ngắt (page-fault trap) kích khởi page-fault service routine (PFSR) của hệ điều hành. 70
71. Bộ nhớ ảo Hiện thực bộ nhớ ảo  Bộ PFSR cĩ nhiệm vụ: 1. Chuyển tiến trình về trạng thái blocked 2. Phát ra một yêu cầu đọc đĩa để nạp trang được tham chiếu vào một frame trong; trong khi đợi I/O, một tiến trình khác được cấp CPU để thực thi 3. Sau khi I/O hồn tất, đĩa gây ra một ngắt đến hệ điều hành; PFSR cấp nhật page table và chuyển tiến trình về trạng thái ready. 71
72. Bộ nhớ ảo Chiến lược sắp đặt  Là tập các trang được tham chiếu gần nhau  Một tiến trình gồm nhiều trang, và trong quá trình thực thi, tiến trình sẽ chuyển từ trang này sang trang khác 72
73. Bộ nhớ ảo Giải thuật thay trang OPT - Optimal  Thay thế trang nhớ sẽ được tham chiếu trễ nhất trong tương lai  Ví dụ: một process cĩ 5 trang, và được cấp 3 frame 73
74. Bộ nhớ ảo Giải thuật thay trang Least Recently Used (LRU)  Thay thế trang nhớ khơng được tham chiếu lâu nhất  Ví dụ: một process cĩ 5 trang, và được cấp 3 frame 74
75. Bộ nhớ ảo Giải thuật thay trang FIFO  Xem các frame được cấp phát cho process như circular buffer  Khi bộ đệm đầy, trang nhớ cũ nhất sẽ được thay thế: FIFO  Một trang nhớ hay được dùng sẽ thường là trang cũ nhất hay bị thay thế bởi giải thuật FIFO  Đơn giản: cần một con trỏ xoay vịng các frame của process 75
76. Bộ nhớ ảo Giải thuật thay trang Clock Ví dụ: một process cĩ 5 trang, và được cấp 3 frame 76
77. Bộ nhớ ảo Giải thuật thay trang Clock 77
78. Bộ nhớ ảo Chiến lược cấp phát frame  Hệ điều hành phải quyết định cấp cho mỗi process bao nhiêu frame.  Cấp ít frame: nhiều page fault  Cấp nhiều frame: giảm mức độ multiprogramming 78
79. Bộ nhớ ảo Chiến lược cấp phát frame  Chiến lược cấp phát tĩnh (fixed-allocation)  Số frame cấp cho mỗi process khơng đổi, được xác định vào thời điểm loading và cĩ thể tùy thuộc vào từng ứng dụng (kích thước của nĩ, )  Chiến lược cấp phát động (variable-allocation)  Số frame cấp cho mỗi process cĩ thể thay đổi trong khi nĩ chạy – Nếu tỷ lệ page-fault cao cấp thêm frame – Nếu tỷ lệ page-fault thấp giảm bớt frame  Hệ điều hành phải mất chi phí để ước định các process 79
80. Bộ nhớ ảo Chiến lược cấp phát frame  Cấp phát bằng nhau:  Khơng quan tâm đến các yếu tố khác nhau của process  Ví dụ, cĩ 100 frame và 5 process mỗi process được 20 frame  Cấp phát theo tỉ lệ:  Dựa vào kích thước process 80
81. Bộ nhớ ảo Thrashing  Là hiện tượng các trang nhớ của một process bị hốn chuyển vào/ra liên tục  Nếu một process khơng cĩ đủ số frame cần thiết thì tỉ số page faults/sec rất cao. Điều này khiến giảm hiệu suất CPU rất nhiều.  Ví dụ: một vịng lặp N lần, mỗi lần tham chiếu đến địa chỉ nằm trong 4 trang nhớ trong khi process chỉ được cấp 3 frames 81