OS Chapter 9
2015-11-05 09:56:33 0 举报AI智能生成
登录查看完整内容
第九章介绍了操作系统的基础知识。首先，我们了解了操作系统的定义和功能，它是计算机系统中的核心程序，负责管理和控制计算机硬件、软件资源，为用户和其他应用程序提供服务。接着，我们学习了操作系统的分类，包括单用户、多用户、分布式操作系统等。此外，我们还探讨了操作系统的主要组成部分，如处理器管理、内存管理、文件系统管理、设备管理和用户接口。在这一章中，我们还简要介绍了一些著名的操作系统，如Windows、Linux和macOS。最后，我们讨论了操作系统的发展趋势，如云计算、物联网和人工智能等技术对操作系统的影响。总之，第九章为我们提供了一个全面的操作系统概述，为后续章节的学习奠定了基础。
作者其他创作
大纲/内容
OS\u00A0Chapter 9: \u00A0Virtual Memory
Background
Only part of the program needs to be in memory for executionLogical address space can therefore be much larger than physical address spaceAllows address spaces to be shared by several processesMore programs running concurrently
Consider ability to execute partially-loaded program
Program no longer constrained by limits of physical memory
Virtual memory can be implemented via
Demand paging\u00A0Demand segmentation
Demand Paging
Could bring entire process into memory at load time
Or bring a page into memory only when it is needed
Less memory needed
Faster response
Lazy swapper – never swaps a page into memory unless page will be needed
Swapper that deals with pages is a pager
Valid-Invalid Bit
Initially valid–invalid bit is set to i on all entries
page fault
concept
pure
This scheme is pure demand paging: never bring a page into memory until it is required.
Performance of Demand Paging
Effective Access Time (EAT)\t\tEAT = (1 – p) x memory access\u00A0+ p (page fault overhead\u00A0+ swap page out\u00A0\u00A0+ swap page in\u00A0+ restart overhead )
EAT = (1-p) x memory access + p x page fault time
example
Memory access time = 200 nanosecondsAverage page-fault service time = 8 milliseconds
Page Replacement
Find the location of the desired page on disk
Find a free frame:
\t- Write victim frame to disk if dirty
Bring \u00A0the desired page into the (newly) free frame; update the page and frame tables
Continue the process by restarting the instruction that caused the trap
Note now potentially 2 page transfers for page fault – increasing EAT
Algorithms
Frame-allocation algorithm determines\u00A0How many frames to give each processWhich frames to replace
Page-replacement algorithmWant lowest page-fault rate on both first access and re-access
First-In-First-Out (FIFO) Algorithm
Belady’s Anomaly
Adding more frames can cause more page faults!
frame变多，page fault变多，frame3 ： 9次，frame 4 \u00A0：10次
Optimal Algorithm
Replace page that will not be used for longest period of time
Least Recently Used (LRU) Algorithm
Use past knowledge rather than futureReplace page that has not been used in the most amount of timeAssociate time of last use with each page
12 faults – better than FIFO but worse than OPTGenerally good algorithm and frequently usedBut how to implement?
implementation
Counter implementation
Stack implementation
Keep a stack of page numbers in a double link form
Page referenced:move it to the topBut each update more expensiveNo search for replacement
LRU and OPT are cases of stack algorithms that don’t have Belady’s Anomaly
LRU Approximation Algorithms
LRU needs special hardware and still slow
Reference bit
Second-chance algorithm
都有可能退化成FIFO，∴會遇到Belady異常情況
Counting Algorithms
keep a counter of the number of references that have been made to each page
LFU (Least Frequently Used) Algorithm
replaces page with smallest count\u000B
MFU (Most Frequently Used) \u00A0Algorithm
based on the argument that the page with the smallest count was probably just brought in and has yet to be used
Allocation of Frames
Each process needs minimum number of frames
Two major allocation schemes
fixed allocation
equal allocation
proportional allocation
Allocate according to the size of process
按比例的分配
priority allocation
Use a proportional allocation scheme using priorities rather than size
If process Pi generates a page fault
select for replacement one of its frames
select for replacement a frame from a process with lower priority number
Global vs. Local Allocation
Global replacement\u00A0
process selects a replacement frame from the set of all frames; one process can take a frame from another
But then process execution time can vary greatly
But greater throughput so more common
Local replacement\u00A0
each process selects from only its own set of allocated frames
More consistent per-process performance
But possibly underutilized memory
Thrashing
a process is busy swapping pages in and out
Page fault to get page
Replace existing frame
But quickly need replaced frame back
Low CPU utilizationOperating system thinking that it needs to increase the degree of multiprogrammingAnother process added to the system
solution
working set model\u00A0
page fault frequency
More direct approach than WSS
Establish “acceptable” page-fault frequency rate and use local replacement policy
Memory-Mapped Files
Each file access requires a system call and disk access
Allocating Kernel Memory
Treated differently from user memory
Often allocated from a free-memory pool
Kernel requests memory for structures of varying sizes
Some kernel memory needs to be contiguous
Buddy System
Allocates memory from fixed-size segment consisting of physically-contiguous pages
Advantage – quickly coalesce unused chunks into larger chunkDisadvantage - fragmentation
Slab Allocation
Other Considerations
prepaging
To reduce the large number of page faults that occurs at process startup
0
Page Size
TLB Reach\u00A0
program structure
0 条评论
回复 删除
下一页
