1. 操作系统的内存管理主要是做什么?
操作系统的内存管理可以概括为:内存的分配(为用户进程分配用户可操作的区域),内存的回收(当用户进程结束时,需要修改空闲区域的链表或者空闲区域表),其中,空闲区域链表是比较常用的,通常空闲区域的数据要求经常插入和删除,如果使用数组对空闲区域记录进行操作,则会导致大量的数组元素的搬动操作,性能较差
而通常链表则是使用一个双向链表,便于寻址和插入和删除
另外,在进程的运行过程中,其中的内存地址通常是以逻辑地址进行表示的
什么是逻辑地址
它就是一种为了便于进程去执行代码的一种映射机制,它假设进程所分配到的空间是位于内存中的第0个字节开始向后执行的,而实际上进程要操作的是实际的物理地址,因此在对内存做操作的时候,还需要将指令中表达的逻辑地址转换为物理地址
一开始,它采用的技术非常简单,就是在基地址寄存器中,记录当前进程的基地址是多少,然后将逻辑地址+这个基地址,就是实际物理地址了
然而,在后续的离散化存储中,由于不同的进程段具有不同的起始块,因此需要将这些不同的起始块的基地址都记录起来,于是便有了页表的概念
2. 常见的内存管理机制?
内存管理机制可以分成是连续内存管理和离散式内存管理的形式
首先来说说简单的连续内存管理,这种管理方式是为用户进程空间分配一段完整的内存空间,这一段的内存空间是完全连续的,因此在完成关键的逻辑地址到物理地址的转换的时候,只需要知道这段进程在内存中的基地址就可以了
典型的连续内存管理方式有块式管理
然后是比较复杂的离散式内存管理,也叫做非连续内存管理方式
首先我们了解一下为什么需要离散式内存管理,在连续式内存管理中,通常会产生大量的内存碎片,比如说有内部碎片,它指的是一个用户进程有16KB,但是系统分配的最小块是32KB,这样的话就会导致内部有空间是无法使用上的,第二个就是外部碎片,外部碎片是导致连续式内存管理空间利用率低的元凶
这里我给一个内存示意图:
| 内存空间 |
|---|
| 4KB(占用) |
| 4KB(空闲) |
| 4KB(占用) |
| 4KB(空闲) |
| 4KB(占用) |
假设现在有一个8KB的进程想要分配空间,而内存中也确实是有8KB的空余,但是因为不连续,因此就不能分配了
同时,由于交换技术的发展,如果一个进程的占用太大,在换出的时候就涉及到大量的IO问题,在这种情况下,性能下降会非常严重
在这种情况下,如果有办法能够将8KB的进程切一刀,然后分别放到内存空间中,同时在PCB中记录一个列表,存储每个段的实际物理地址,而这种想法就是非连续内存管理的雏形
目前来看,非连续内存管理的方式有页式管理、段式管理、段页式管理
先来讲讲页式管理,页式管理的基本思路是先规定内存中的最小存储单元,通常设定为4KB,4KB也就是2^12B,是2的整数次幂,那么对应的,如果将内存划分为固定大小的很多页,而这些内存就是用来加载进程的
因此进程也必须以一定的方式和大小装载如内存中
在这里,内存因为是加载进程被划分后产生的页,因此称为存储页的页框。
页式管理的基本好处是简单,能够以更小的粒度对内存进行管理,并且离散式的存储方式,能够更加高效的利用内存,但是对于页的大小,如果设计不当将会产生大量的内部碎片,这也是它的一个不足之处
在来说说段式管理,之前说的页式管理,对于进程来说,这些页并没有什么含义,我们知道进程通常由不同的段组成,比如说有主程序段MAIN、子程序段X、数据段D、栈段S等,但是在分页的时候,通常会将这些段分成多段,导致在内存中存储的数据失去了原本的含义,或者说无法辨别页内数据的含义
那么这时候段式管理就可以解决这个问题了,它保留了各个段中的实际含义,在做最关键的寻址的时候,它有一张段表,如下所示
| 段号(索引) | 段的内存起始地址 | 段长 |
|---|---|---|
| 1 | 0x114514 | 200 |
它记录每个段的长度等基本信息,但是我们注意一点:就是段的长度是不定长的,也就是说,有些段可能会很长,有些段可能会很短,这就又造成了内存碎片的问题了,同时还会导致swap的时候,比较耗时
在段式内存管理的情况下,它在程序代码中的逻辑地址描述为<段号,偏移量>
上面简单描述了段式内存管理和页式的内存管理机制
可以简单总结为:段式内存管理能够有效保存进程的各程序段的信息,但是不等长的段还是会使得内存碎片和内存交换性能低下的问题,页式管理则是无法保存进程的各程序段的信息
因此,在这种情况下,我们还有一种段页式的管理机制,这种机制集合了段式内存管理模式和页式内存管理模式
段页式的管理机制就是为每页赋予了他们的段含义,先来看看段页式的逻辑地址是如何表示的
| 段号 | 段内页号 | 页内位移 |
|---|---|---|
它是这样工作的,首先它会先将这一段进程划分为不同的具有逻辑含义的段,然后再把这些段划分为等长的页,如果有多个页的,就为这些页编序号,然后就找到这个数据具体在哪一页了
然后,再根据逻辑地址提供的页内偏移bias,计算出实际的物理地址即可
3. 快表和多级页表
快表在计算机组成原理中称为TLB,它是一种常见的缓存技术,可以看成是一个简易的Cache,它在专门用来加速页的查询,它内容实际上是页表的副本,它的作用是将某一页的物理地址记录下来,避免每一次都去内存中的页表中查询某一页的物理记录。有快表情况下的页查找技术
- 首先根据虚拟地址中的提供的页号查找TLB
- 如果TLB缓冲命中,那么直接返回虚拟页号所对应的物理页号
- 如果TLB缓冲不命中,那么就需要从内存中读取页表,然后通过页表找到对应的物理页号,同时将这个数据缓存到TLB中
- 当快表满了之后,就按照内存淘汰策略淘汰掉这一页
关于多级页表
多级页表是一种套娃的机制,假设在一台32位的机器上,有12位作为页内偏移量,有20位作为页号,那么也就是说,页表的长度可能达到2^20个页,而每个页表项占4B,在这种情况下,一个页表最大需要2^22B,也就是4MB的页表大小,这是相当大的,因此基于此引入了多级页表
由于一个页占4KB,而一个页表项是4B,因此一个表可以存储1024个页表项
那么当映射一个4GB的内存地址空间的时候,就需要4KB+4MB的页表开销
这不是更多了么?
这个问题要从局部性讲起。
所谓局部性原理,就是内存中的数据,在一段时间内只有一部分的数据会被一直访问
那么在采用多级页表的情况下,可以将暂时不用的一级页表项给换到磁盘上,这样的话就可以节约出很多内存了
而单级页表是不能够换出到磁盘的,这是因为单级页表项并没有上级索引,也就是说当它被换入到磁盘中,没有提供上一级的表来查找它在磁盘中的地址
这里可以举个例子,比如说学校,分了三级,分别是年级,班级,学生本人
二级页表,就相当于年级长除了自己的脑子能记录下这些目录项,当东西太多了或者说它都根本记不了这么多的时候,就把信息写入笔记本中
(二级页表),当有人想要这个信息的时候,他去读笔记本,然后记到脑子里面去(一级页表),然后告诉那个人这就是二级页表的优势,提供了一种寻址方案,能够知道下一级的地址
而一级页表,就相当于年级长没有了这本笔记本,他只有一个
脑子(内存)能使了,脑子装不下那么多东西呀,所以它会忘记,忘记就是将这个页表项放到磁盘上了,然后下次 别人问他说,5班在哪?他忘记了,但是因为没有笔记本,因此最终这个信息就丢失掉了
至于优点,也可以举一个例子,假设学校现在要举行会操表演,每个特定的时间段只需要特定的同学出现,并且这些同学都是同一个班级的,这就好像,每个特点的时间段只需要特定的内存页一样,班级你可以理解成一个内存相近的那些页,比如说现在全校(整个内存空间),需要1班的同学进行表演,那么就把1班叫到准备室,
准备室只能容纳两个班级,其他班级的同学全部待在课室,当广播通知中断处理的时候,你们才从课室跑到准备室,暂时没有表演的同学就回到课室去继续等。而且可以看出,从课室跑到表演室也是需要花费一定的时间的,这就是IO的开销
多级页表,能够极大的提高信息的存储量,在Mysql中的B+树也是类似这种机制
4. 分页机制和分段机制的共同点和区别
总结一下,分页机制和分段机制的共同点有
- 首先他们都是非连续式内存分配方式,在内存中的存放都是离散式的
- 分页和分段都是为了减少内存碎片和降低内存换入和换出的开销
不同点
- 分页机制所分出来的页是固定大小的,而分段机制所分出来的段不是固定大小的,由运行时程序决定
- 分页机制分出来的页是没有实际含义的,程序员无法根据某一页来判断里面的内容是什么,分段机制分出来的段是有具体含义的,程序员得到关于段的信息
5. 什么是逻辑地址和物理地址
逻辑地址是程序运行时所界定的地址,在程序运行时,它会假设它占据了从内存的第零个字节开始往后的一段内存空间,而且每一个进程都是如此,但是实际上在操作系统系统的支持下,在没有设定共享内存区域的前提下,每个进程都有自己独立的内存空间。
因此实际上这个逻辑地址就是一个实际物理地址在程序运行时的别名,这个别名要找到真名,必须要通过地址转换机构进行之后才能使用。
物理地址就是物理内存的实际地址,它代表着计算机数据在实际内存中的存储偏移量,是真正的存储单元
6. 什么是CPU寻址?为什么需要虚拟地址空间?
之前提到了什么是逻辑地址和物理地址,那么逻辑地址如何变换成物理地址呢?首先肯定是需要经过运算的,基于运算,肯定离不开CPU,因此也将地址转换的过程称为CPU寻址,具体的转换的方法与具体的内存管理方式有关。
比如说使用页式管理式,根据虚拟地址前x位确定出页号,然后再获取后面的y位,就可以获取到内存偏移量,然后从页表中查询,页表->实际物理页的起始地址,然后将这个起始地址+内存偏移量,就得到实际数据的物理地址了。
那么为什么需要虚拟地址空间呢?
在没有虚拟地址空间的时候,比如说单片机的烧录,单片机是不允许有两个程序同时运行,这就是因为它直接操作的是物理内存,没有做软件上的隔离措施,就会导致两个程序之间的数据互相覆盖。
同时,如果直接操作物理内存的话可能会操作到os的内核数据区,造成更加严重的后果,虽然可以通过在操作内存之前就检查这个物理内存地址是否是合法的地址,但是效率太低了,为什么不在内存分配的环节中,就将进程的内存限定在一定的区域内呢?这就是为什么需要虚拟地址空间了,引入它,首先能够确保它能够不会访问到内核的核心区域,并且能够确保各个进程不会互相窜数据,由操作系统来完成这个内存分配的任务。
同时,对于程序代码的生成是友好的,对于一些汇编代码需要具体的跳转地址的,可以用一个程序生成的虚拟地址作为替代,这样的话就不需要在运行时还进行代码的改动,只需要在内存访问的时候执行地址的转换即可,大大提高了系统的吞吐量
7. 什么是虚拟内存?
虚拟内存技术可以使得一个进程认为它拥有了一块比当前计算机内存空间还要大的内存空间,但是实际上,虚拟内存只是将分配于进程的物理内存划分为一个个离散的单元,将一部分必要的,进程所需要的载入内存,这一部分称为是驻留集,而其他的暂时不需要用到的部分会先暂时存储在外部存储器中。
比如说当使用了虚拟内存的os,进程请求页面的时候发现内存中并没有此内存,那么就会触发缺页中断,阻塞该进程,然后启动磁盘IO,从外存中调入此页,然后执行相关的操作。
虚拟内存有什么用?
它最重要的意义是使得进程具备了比当前硬件所受限的内存容量更大的地址空间,而且这对用户进程来说是无感的,就好像那些存储在外部存储器的内存页面就存在于内存中,当用户进程需要调用的时候,要么直接命中,要么将相关页面调入内存,这对用户是透明的,使得在有限的内存中,能够运行更大的程序。
没有虚拟内存会发生什么?
作业必须一次性地装入内存中,当作业很大的时候,不能全部被装入内存的时候,就会导致作业无法运行,当大量作业要求同时运行的时候,只能使得少数作业先运行,其他作业只能位于后备井中,降低了系统的吞吐量
作业被装入内存中,不会被换出,从而导致了那些处于长期阻塞的进程占用内存空间,使得系统的并发度下降了。
8. 什么是局部性原理?
局部性原理是计算机组成原理中发现的很重要的定义,可以分为时间局部性原理和空间局部性原理:
时间局部性原理就是说在同一时间段内访问的这些数据,在未来可能又会被大量访问
空间局部性原理就是说在一旦程序访问了某些内存单元,那么在未来的一段时间内,这些内存单元附近的数据极有可能被再次访问。
他们在计算机中有什么应用?
比如说有快表,快表的话就是充分利用了时间局部性的作用,当有一个页面被请求的时候,它会将这个页面装入到TLB中,然后当下一次有请求到来到的时候,直接直接从这个更小的存储器取出数据返回,这就好像Redis一样
而内存-磁盘则是充分利用了空间局部性原理,在基于虚拟内存的机制下,它将一部分的数据先载入读取速度更快的内存,然后将大部分的数据都留在外层中,当需要这些数据的时候再从外存中进行读取。
显著的优点:访问的速度接近于内存,每一位的存储成本接近于外存
9. 什么是虚拟存储器?
虚拟存储器的实际上较小的内存存储器+中断处理软件+较大的外存存储器,什么意思呢,就是说,当进程载入系统时,会将一部分数据载入较小的内存存储器,将大部分的数据放在外存存储器中,当进程发现想要的数据不在内存的时候,就要启动中断处理软件,将页面从较大的外存存储器中调入,从而好像该进程有一个比当前计算机内存硬件所限定的内存大小更大的虚拟存储器一样。它的特征可以这样描述:
多次性:所谓多次性就是说无序在作业一开始运行的时候就将数据全部载入到内存中,而是允许被分成多次载入到内存中,对换性:无需在作业运行的时候一直常驻内存,而是允许在作业的运行过程中进行动态的换入和换出,虚拟性:从逻辑上扩充了内存的容量,是用户所看到的内存容量,远大于实际的内存容量。
就绪挂起态和阻塞挂起态的换入/换出内存和虚拟内存的换入/换出内存有什么区别?
就绪挂起态/阻塞挂起态的换入和换出的内存是指将驻留集中的数据全部换出到外存中,当解除挂起的时候,会将驻留集中的元素全部加载到内存中
而虚拟内存的换入/换出的过程是指将部分的内存页换出到外存中。而且进程是运行态的,在进程发起缺页中断的时候,需要的内存页才会从外存中读取出去。
10. 虚拟内存是怎么实现的?
目前来说,虚拟内存的实现方案可以基于现成的内存管理机制进行实现,比如说有请求式分页,请求式分段,请求式段页,目前应用最为广泛的有请求分页式,这种方案中,为了能够淘汰掉一些无用的内存页让那些目前急需的内存页进行加载,就需要给这些页添加一个头,通过读取这个头得到依据。
目前来说,有请求分页式管理,这种管理方式是基于页式管理进行实现的,相比于传统的页式管理,请求分页式的根本不同在于进程在运行的时候不必将所有的内存页加载进去内存,而是在需要某段内存页的时候,请求调页,将内存页从外存中调入内存,在请求分页系统中,每当要访问的页面不在内存的时候,就会产生一个缺页的中断,请求中断处理函数将在外存中的页调入内存中。
一般来说在处理中断的时候需要经过以下的步骤:
- 保存现场,也就是将当前进程的一些状态保存到PCB,比如说什么基地址寄存器,页表寄存器等,把这些东西存储到PCB的头部里面
- 解析中断号,从中断向量表中查看需要调用什么中断函数
- 执行中断处理程序,将页面调入内存
- 恢复进程,将PCB首部的值恢复到寄存器中
- 将进程恢复到就绪态
在指令的执行期间产生和处理中断信号,而非一条指令执行完毕后才处理中断。
虚拟内存的地址转换流程如下:首先是先从当前的页表寄存器中取出来页表的首地址,然后根据虚拟地址计算出来的页号,用页号*页表项的大小,然后用这个数值+页表的首地址,然后就是这一个虚拟地址所对应的物理页的地址(第一次访问内存完毕)
然后拿着这个物理页的地址,拼接虚拟地址的偏移量,就是实际的物理地址,然后用这个物理地址去访问对应的内存(第二次访问内存完毕)
那么这此处的MMU中也引入了TLB,这个TLB存储了对应的页号的信息,它相当于一层缓存,将内存中的页表项的数据存储到了TLB中,这样的话就减少了一次访问内存的时间
然而引入TLB的代价是需要多一层的数据一致性的维护,比如说:当MMU启动数据的查询之后,它会先查询TLB中是否有数据?如果TLB中没有数据,那么就回去查找页表,当页表中也没有数据的时候,就会发起一个缺页的中断,这时候会将寄存器中的值保存到PCB中,然后根据中断号从中断向量表中获取中断处理程序的入口,然后执行中断处理程序,替换通知磁盘读取该页,CPU启动磁盘IO,将这一页读取到内存中,如果内存满了,那么就会执行页面的置换,修改被置换页的驻留位P,修改置换页的驻留位P,访问位A,将该页植入到内存中。恢复PCB,继续执行
如果内存有而TLB中没有会怎么样?会将内存写入到TLB中,如果TLB的空间不足则会执行页面的置换
请求分段式
请求分段式在分段式的基础上进行实现的,其具体的功能点在于添加了调段功能和不用一次性调入所有的段到内存中,其中主要的工作流程也如:根据请求动态调入段进行执行,根据置换功能适当调出段来腾出空间
缺点:由于段的长度是不固定的,因此在调入一个段的时候可能会导致连锁反应,导致多个段被调出,是重量级的操作,而调入页的长度是固定的,因此通常需要置换一个页即可
请求段页式
请求段页式是在段页式的基础上进行实现的,其具体的功能点在于添加了调页/调段的功能,更加综合了,首先是虚拟地址的改动,它的地址改动为了段号+页号+页内偏移地址,它的基本思路是:每个进程一张段表,每一段一张页表,基本的寻址模式是:先通过段号找到对应的段,如果这个段在内存中,那么就不调段,如果段中的页在内存中,那么就不调页,如果这个页已经在内存中了,那么就查询TLB,如果TLB中有这一页,就不需要更新,否则就还是需要更新
虚拟存储管理需要考虑的问题
- 读取策略:某一页什么时候调入到内存中
- 置换策略:选择哪一页换出到内存
- 驻留集管理:给进程分配多少帧,置换时牺牲谁的帧
- 清除策略:何时将脏页写回到磁盘中
- 加载控制:调整系统的并发度,防止抖动
11. 页面置换算法有哪些?
首先第一种是最佳置换算法OPT,这种算法仅在理论上提出,实际上无法做到,其核心的思路就还是淘汰永不使用或者下次访问间距当前时间最长的页面
置换策略:LRU算法,叫做最近最少使用算法,这种算法的目的是从内存中淘汰掉目前驻留集中最少使用次数的页面,实现的思路是为每一页添加上次访问时间戳,它的理论基础是最近使用过的页面很有可能会被再次使用,而过去很久没有使用过的内存在短期内不会再被使用
FIFO算法:将页面按调度内存的时间先后排成一个队列,每次都淘汰队首页,性能比较差的
CLOCK时钟轮转算法,每个页表项设置一个使用位U,某个进程的所有页面排成一个循环缓冲链。
有一个指针从开头开始指向,具体的算法是:置换的时候顺序查找这个链,当U=0 的时候证明这一页在最近没有使用过,那么这时候就把它替换掉,当U=1的时候,就先放过它,但是会将U=0,如果下次到来还是U=0,那么就会替换掉这一页,通常还可以加入一个修改位进行辅助
如果无法替换页怎么办?最终就会导致OOM
如果最近没有使用,而且没有修改,那么也就是说这一页,既不需要刷回数据库,在缓存中也不需要,把它淘汰掉没有任何代价
如果最佳没有使用,但是被修改过了,那么也就是说这一页,需要刷回数据,具有一定的代价,需要将其淘汰掉
如果最近有使用,但是没有被修改过。
如果最近有使用,而且曾经被修改
