说明: 在左边的单处理器系统中,如果一个进程想要运行,那么必须将进程地址空间装载到物理内存中才可以运行。 而右边的是多处理器系统中有多个进程需要进入物理内存执行,这里要解决的问题就是,如何将进程地址空间合理的装载到物理内存中,如何合理的分配使用内存,使得每个进程能正确执行。
这就需要地址重定位来解决这些问题。
为了保证cpu
执行指令时可以正确访问内存单元,需要将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址,这一过程称为地址冲地位。
说明:我们对物理内存有不同的划分,一种是等长的划分,一种是不等长的划分。
0
表示空闲,1
表示占用(或者相反)。对于不等长的划分可以使用下面两种分配结构。
2、空闲区表、已分配区表
表中每一项记录了空闲区(或已分配区)的起始地址、长度、标志
3、空闲块链表这里我们使用空闲区表、已分配区表为例来说明内存分配算法。
first fit
在空闲区表中找到第一个满足进程要求的空闲区next fit
从上次找到的空闲区处接着查找best fit
查找整个空闲区表,找到能够满足进程要求的最小空闲区worst fit
总是分配满足进程要求的最大空闲区当找到满足进程需求的空闲区表后,需要将空闲区分为两部分,一部分供进程使用,另一部分形成新的空闲区。
这是Linux
底层内存管理采用的一种方法
2
的整数次幂进行划分,组成若干空闲块表;查找该链表找到能满足进程需求的最佳匹配块。2^U
s
,
如果满足2^(U-1)<s<=2^U
,则分配整个块
否则,将块划分为两个大小相等的伙伴,大小为2^(U-1)
s
的最小块。说明:从上图中可以看到上面的算法是如何工作的。
特点:一段时间内只有一个进程在内存中,简单、内存利用率低。 这种方案是在早期系统中使用的,有三种不同的布局:
说明: 不同的进程链分排在不同分区位置。缺点是有的进程链很长,一时得不到分区,但是此时可能有些空闲分区根本没有被使用。 于是还有右边这种排队方案,就是只有一个进程链,然后哪个分区空闲了,排在首位的进程就进入执行。早期手机中就是采用这种方法。
碎片问题解决
page
),从零开始编号。
这是逻辑地址空间上的称谓。
page frame
),从零开始编号4K
或4M
说明:逻辑地址分为页号和页内地址(页内偏移),这种划分是系统自动完成的,对用户是透明的。
说明:可以看到连续的进程地址空间映射到页帧中的物理内存是杂乱的。
说明:对于逻辑地址空间和物理内存空间的杂乱的映射,如何进行映射呢?这里我们需要使用页表来记录这种映射。
相关数据结构及地址转换
cpu
取到逻辑地址,自动划分为页号和页内地址;
用页号查页表,得到页框号,再与页内偏移拼接成物理地址。
在这种方案中我们也会遇到碎片问题,这里的碎片是内碎片。比如某个进程需要5
页加一条指令,于是这里我们需要分配6
页给这个进程。说明:和页式类似,逻辑地址分为段号和段内地址。 不同的是段号和段内地址不是自动划分的。看个例子:
说明:同样的,和页式类似,每个段的位置都不一样或不连续。而我们这里使用段表来将逻辑段号和物理内存映射起来。其中段表包含长度和段起始地址。
相关数据结构及地址转换
cpu
取到逻辑地址,用段号查段表,得到该段在内存的起始地址,与段内偏移地址计算出物理地址内存划分:同页式存储管理方案 内存分配:以页为单位进行分配
即如何在一个较小的物理内存空间中运行一个会占用较大地址空间的进程?
overlaying
)swapping
)virtual memory
)这种技术主要用于早期的操作系统,现在使用不多。
I/O
状态的进程
说明:这里给出了两种解决方案,一种是左边的为栈预留一部分空间;一种是右边的让数据区和栈去同向增长,即在一个预留区中增长。
我们将虚拟存储技术和页式存储管理方案结合起来得到了虚拟页式存储管理系统。具体有两种方式,一是请求调页,二是预先调页。以cpu
时间和磁盘换取昂贵内存空间,这是操作系统中的资源转换技术。
通常,页表项是硬件设计的。
32
位虚拟地址空间的页表规模?
页面大小为4k
,页表项大小为4
字节,则一个进程地址空间有2^20
页。这里首先是虚拟地址空间可以达到2^32
字节,这里注意:在二级页表中才可以表示2^32
的地址空间,除以页面大小可以得到有多少个页面。而一个页表项可以表示1k
的页面,于是页表项就要占用1024
页(页表页,就是页表项占用的空间)。
64
位虚拟地址空间
页面大小为4k
,页表项大小为8
字节,则页表规模为32000TB
。这里没说清楚,到底是几级页表中的结果?
说明:这里还是32
位的虚拟地址空间。每个进程有一个页目录,根据页目录得到页表地址,然后从页表中的页表项的页框号找到真正的物理内存地址。32
位的虚拟地址分为页目录偏移、页表偏移和页内偏移。页目录地址保存在一个寄存器中,根据此地址找到页目录起始地址,然后根据月页目录偏移找到对应的页表地址,根据页表偏移找到页表项,从页表项中取得页框号,然后结合页内偏移找到对应的物理内存。对于二级页表,在32
位系统中可以表示4G
的虚拟地址空间。如果需要超过4G
的虚拟地址空间,则二级页表满足不了。
说明:总共有32
位地址。
说明:系统建立一张页表可以节省很大的空间,这被很多64
位系统采用,但是每次进行运行都需要查整张表,这样会耗费很大的资源,于是我们采用了一个哈希表,这样查找更快。
说明:上图是虚拟地址通过页表和物理地址映射的关系。这个过程是有内存管理单元完成的。
cpu
的指令处理速度与内存指令的访问速度差异较大,cpu
的速度得不到充分利用。
那如何加快地址映射速度,以改善系统性能?这里我们利用程序访问的局部性原理:引入快表(TLB
)。TLB
(Translation Look-aside Buffers
)
在cpu
中引入的高速缓存,可以匹配cpu
的处理速度和内存的访问速度。是一种随机存取型存储器,除连线寻址机制外,还有接线逻辑,能按特定的匹配标志在一个存储周期内对所有的字同时进行比较。
说明:首先根据虚拟地址去查TLB
,如果能找到页框号,则直接和偏移结合找到对应的物理内存;如果TLB
中没有页框号,则需要去查页表,之后在找到对应的物理内存;在页表中如果对应的页表项无效,则会出现page fault
的异常,然后由系统处理之后再进行同样的操作。
图中标注的位置都是有内容的,如果访问地址指向没有标注(没有内容)的位置,则就是错误的访问地址。
为什么要锁定页面?
I/O
缓冲区。特别是正在I/O
的内存页面。Windows
中的VirtualLock
和VirtualUnLock
函数。I/O
操作的数量,从而减少了磁盘访问的时间)最佳算法-->先进先出-->第二次机会-->时钟算法-->最近未使用-->最近最少使用-->最不经常使用-->老化算法-->工作集-->工作集时钟
在先进先出算法的基础上进行该机而来的,此算法按照先进先出算法选择某一页面,检查其访问位R
,如果为0
,则置换该页;如果为1
,则给第二次机会,并将访问位置零,并将其从链头取下放到链尾。
在第二次机会算法中当给某个页面第二次机会的时候,将其访问位置零,然后将其挂到链尾,这都是需要开销的,于是我们改进为时钟算法。
说明:其实就是将之前的链表改为了环形链表,当给某个页面第二次机会的时候不需要将其取下然后挂到链尾,只需要移动一下指针即可,这样可以降低开销。
R
,修改位M
。硬件会设置这些位,如果硬件没有这些位,则可用软件模拟。R、M
位置零,R
位被定期清零。R、M
:
* 第一类:无访问,无修改(`00`)
01
)10
)11
)r=0,m=0
)用于置换(本扫描过程中,对使用位不做任何修改)
2、如果第一步失败,则重新扫描,选择第一个(r=0;m=1
)的页框(本次扫描工程中,对每个跳过的页框,将其使用位置为零)
3、如果第二部失败,指针将回到它的最初位置,并且集合中的所有页框的使用位均为零。重复第一步,并且,如果有必要,重复第二步,这样将可以找到置换的页框。
选择最后一次访问时间距离当前时间最长的一页并置换,即置换未使用时间最长的一页
案例
说明:访问第0
页时先将页的第0
行置为1
,然后将第0
列置为0
,
以此类推,在访问完之后将行编号最小的那一页置换出去
我们看到j
中最小的是第1
行,于是将第1
页置换出去。当然这里只有四页。
即Not frequently Used
,选择访问次数最少的页面置换
LRU
(最近最少使用算法)的一种软件解决方案,但是实际上差距有点大。R
LRU
):计数器在加R前先右移一位,R
位加到计数器的最左端。
这样如果R
值为零,则计数器没有影响,如果值为1
,则会变得很大,于是如果一个页面长久不被访问,则计数器值就会越来越小。最后选择值最小的置换出去。
例子:
2 3 2 1 5 2 4 5 3 2 5 2
要求:
计算应用FIFO、LRU、OPT
算法时的缺页次数
应用FIFO、LRU
页面置换算法
可以看到FIFO
发生六次缺页异常,而LRU
发生四次缺页异常。
应用OPT页面置换算法
发生三次缺页异常。
例子:系统给某进程分配m
个页框,初始为空页面访问顺序为
1 2 3 4 1 2 5 1 2 3 4 5
,采用FIFO
算法,计算当m=3
和m=4
时的缺页中断次数。
结论:m=3
时,缺页中断九次;m=4
时,缺页中断十次。注意:FIFO
页面置换算法会产生异常现象(Belady
现象),即:当分配给进程的物理页面数增加时,缺页次数反而增加。
该算法采用了可变分配和局部置换方式,置换算法则采用FIFO。 该算法规定将一个被淘汰的页放入两个链表中的一个, 若页面未被修改,直接放入空闲链表末尾,否则放入已修改页面链表末尾。 这种方式使得已修改和未修改的页面都仍然留在内存中,当进程以后再次访问这些页面时,只需花较小的开销,使这些页面又返回到该进程的驻留集中。 当被修改页面达到一定数量时,才一次性地将他们写回到外存,这样就显著地减少了外存的I/O次数
假设采取FIFO固定分配局部置换,每次缺页都要淘汰该进程最早装入内存的页面,而这里采用可变分配局部置换,即分配进程一个空白块,将原本应该淘汰的最早装入的页面挂在两个队列之一,直到没有空白块或修改页面达到上限才启动磁盘写回外存
缺页越多,系统的性能越差,这称为颠簸(抖动):虚存中,页面在内存与磁盘之间频繁调度,使得调度页面所需的时间比进程实际运行的时间还多,这样导致系统效率急剧下降,这种现象称为颠簸或抖动。
Intel 80x86/Pentium: 4096
或4M
TLB
带来灵活性,但给操作系统带来复杂性。例子:
分配了一个页框,页面大小为128
个整数,矩阵A(128 x 128)
按行存放。
可以看到左边是按列赋值,右边是按行赋值。按列编制就是首先读入第一页(一行,因为矩阵是按行存放的),然后给第0
个位置赋值,每次读入一行,直到将第0
列赋值完,读完之后再给第1
列赋值,这样会产生128*128
次缺页异常;而按行赋值,第一次读入一页,给第0
行的所有元素赋值,这样会产生128
次缺页异常。于是可以看到程序的编制方法对缺页次数是有很大影响的。
说明:可以看到页框数越多那么缺页率越低,但是我们不可能给出所有的页框,于是需要找到一个平衡点W
,超过这个点之后页框数的增加对缺页率的降低有限,这也是工作集算法的出发点。
如果能为进程提供与活跃页面数相等的物理页面数,则可减少缺页中断次数,这是由Denning
提出的。
T
根据一个页面的访问时间是否落在“当前时间 - T
”之前或之中决定其在工作集之外还是之内。
R
位是1
,则将该页面的最后一次访问时间设为当前时间,将R
位清零
2、如果一个页面的R
位为0
,则检查该页面的访问时间是否在“当前时间 - T
”之前,如果是,则该页面是需要被置换的页面;否则,记录当前所有被扫描过页面的最后访问时间里面最小值。扫描下一个页面并重复上述操作。
mmap
)将一个文件(或部分)映射到其虚拟地址空间的一部分,访问这个文件就像访问内存中的一个大数组,而不是对文件进行读写
说明:如图,两个进程共享同一块物理内存,每个页面都被标志成了写时复制。注意:共享的物理内存中每个页面都是只读的。如果每个进程想改变某个页面时,就会与只读标记冲突,而系统在检测出页面是写时复制的,则会在内存中复制一个页面,然后进行写操作。新复制的页面对执行写操作的进程是私有的,对其他共享写时复制页面的进程是不可见的。