操作系统学习(3) 内存管理

1. Windows下的内存是如何管理的
1). 虚拟内存：
最适合用来管理大型对象或者结构数组
2). 内存映射文件：
最适合用来管理大型数据流（通常来自文件）以及在单个计算机上运行多个进程之间共享数据
3). 内存堆栈：
最适合用来管理大量的小对象

2. Windows消息调度机制是？
消息队列；

3. 分段和分页的区别？
（1）页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。
（2）段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好的满足用户的需要。
（3）页的大小固定且由系统确定(一般为4k)，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。
（4）分页的作业地址空间是一维的，即单一的线性空间，程序员只须利用一个记忆符，即可表示一地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

4. 分段和分页，段页式存储

• 分页存储管理：用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。
• 分段存储管理：将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。
• 段页式存储管理：
  分页系统能有效地提高内存的利用率，而分段系统能反映程序的逻辑结构，便于段的共享与保护，将分页与分段两种存储方式结合起来，就形成了段页式存储管理方式。
  在段页式存储管理系统中，作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每段分成若干个大小相等的页。对于主存空间也分成大小相等的页，主存的分配以页为单位。
  段页式系统中，作业的地址结构包含三部分的内容：段号 页号 页内位移量
  程序员按照分段系统的地址结构将地址分为段号与段内位移量，地址变换机构将段内位移量分解为页号和页内位移量。
  为实现段页式存储管理，系统应为每个进程设置一个段表，包括每段的段号，该段的页表始址和页表长度。每个段有自己的页表，记录段中的每一页的页号和存放在主存中的物理块号。

5. 什么叫做虚拟内存？优缺点？它和主存的关系如何？

• 定义： 具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充得一种存储器系统。大小由计算机的地址空间决定，实际容量是主存与辅存的和。
• 与传统存储器比较虚拟存储器有以下三个主要特征：
  （1）多次性，是指无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行。
  （2）对换性，是指无需在作业运行时一直常驻内存，而是允许在作业的运行过程中，进行换进和换出。
  （3）虚拟性，是指从逻辑上扩充内存的容量，使用户所看到的内存容量，远大于实际的内存容量。
• 关系
  虚拟内存是一些系统页文件，存放在磁盘上，每个系统页文件大小为4K，物理内存也被分页，每个页大小也为4K，这样虚拟页文件和物理内存页就可以对应，实际上虚拟内存就是用于物理内存的临时存放的磁盘空间。页文件就是内存页，物理内存中每页叫物理页，磁盘上的页文件叫虚拟页，物理页+虚拟页就是系统所有使用的页文件的总和。
• 虚拟内存的实现
  虚拟内存的实现建立在离散分配的内存管理方式基础上
  （1）请求分页存储管理。
  （2）请求分段存储管理。
  （3）请求段页式存储管理

6. 页面置换方法详细介绍

• 最佳置换算法（OPT）（理想置换算法）：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面，这样可以保证获得最低的缺页率。
• 先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。
  缺点：对于有些经常被访问的页面如含有全局变量、常用函数、例程等的页面，不能保证这些不被淘汰。
• 最近最久未使用（LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。
• 时钟(CLOCK)置换算法:LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。
  简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。

7. 虚拟地址空间

8. 什么是缓冲区溢出？有什么危害？其原因是什么？
（1）缓冲区溢出是指当计算机向缓冲区内填充数据时超过了缓冲区本身的容量，溢出的数据覆盖在合法数据上。
（2）危害：缓冲区溢出中，最为危险的是堆栈溢出，因为入侵者可以利用堆栈溢出，在函数返回时改变返回程序的地址，让其跳转到任意地址，带来的危害一种是程序崩溃导致拒绝服务，另外一种就是跳转并且执行一段恶意代码，比如得到shell，然后为所欲为。通过往程序的缓冲区写超出其长度的内容，造成缓冲区的溢出，从而破坏程序的堆栈，使程序转而执行其它指令，以达到攻击的目的。
（3）造成缓冲区溢出的主原因是程序中没有仔细检查用户输入的参数。

9. 逻辑地址 Vs 物理地址 Vs 虚拟内存

• 所谓的逻辑地址，是指计算机用户(例如程序开发者)，看到的地址。例如，当创建一个长度为100的整型数组时，操作系统返回一个逻辑上的连续空间：指针指向数组第一个元素的内存地址。由于整型元素的大小为4个字节，故第二个元素的地址时起始地址加4，以此类推。事实上，逻辑地址并不一定是元素存储的真实地址，即数组元素的物理地址(在内存条中所处的位置)，并非是连续的，只是操作系统通过地址映射，将逻辑地址映射成连续的，这样更符合人们的直观思维。
• 另一个重要概念是虚拟内存。操作系统读写内存的速度可以比读写磁盘的速度快几个量级。但是，内存价格也相对较高，不能大规模扩展。于是，操作系统可以通过将部分不太常用的数据移出内存，“存放到价格相对较低的磁盘缓存，以实现内存扩展。操作系统还可以通过算法预测哪部分存储到磁盘缓存的数据需要进行读写，提前把这部分数据读回内存。虚拟内存空间相对磁盘而言要小很多，因此，即使搜索虚拟内存空间也比直接搜索磁盘要快。唯一慢于磁盘的可能是，内存、虚拟内存中都没有所需要的数据，最终还需要从硬盘中直接读取。这就是为什么内存和虚拟内存中需要存储会被重复读写的数据，否则就失去了缓存的意义。现代计算机中有一个专门的转译缓冲区(Translation Lookaside Buffer，TLB)，用来实现虚拟地址到物理地址的快速转换。
• 与内存／虚拟内存相关的还有如下两个概念：
  （1）Resident Set： 当一个进程在运行的时候，操作系统不会一次性加载进程的所有数据到内存，只会加载一部分正在用，以及预期要用的数据。其他数据可能存储在虚拟内存，交换区和硬盘文件系统上。被加载到内存的部分就是resident set。
  （2）Thrashing： 由于resident set包含预期要用的数据，理想情况下，进程运行过程中用到的数据都会逐步加载进resident set。但事实往往并非如此：每当需要的内存页面(page)不在resident set中时，操作系统必须从虚拟内存或硬盘中读数据，这个过程被称为内存页面错误(page faults)。当操作系统需要花费大量时间去处理页面错误的情况就是thrashing。

10. 内部碎片与外部碎片

• 在内存管理中，内部碎片是已经被分配出去的的内存空间大于请求所需的内存空间。
• 外部碎片是指还没有分配出去，但是由于大小太小而无法分配给申请空间的新进程的内存空间空闲块。
• 固定分区存在内部碎片，可变式分区分配会存在外部碎片；
  页式虚拟存储系统存在内部碎片；段式虚拟存储系统，存在外部碎片
• 为了有效的利用内存，使内存产生更少的碎片，要对内存分页，内存以页为单位来使用，最后一页往往装不满，于是形成了内部碎片。
  为了共享要分段，在段的换入换出时形成外部碎片，比如5K的段换出后，有一个4k的段进来放到原来5k的地方，于是形成1k的外部碎片。

11. 虚拟内存机制？mmu？
（一）虚拟内存机制
(1)为什么要有虚拟内存
在早期的计算机中，是没有虚拟内存的概念的。我们要运行一个程序，会把程序全部装入内存，然后运行。
当运行多个程序时，经常会出现以下问题：
1)进程地址空间不隔离，没有权限保护。
由于程序都是直接访问物理内存，所以一个进程可以修改其他进程的内存数据，甚至修改内核地址空间中的数据。
2)内存使用效率低
当内存空间不足时，要将其他程序暂时拷贝到硬盘，然后将新的程序装入内存运行。
由于大量的数据装入装出，内存使用效率会十分低下。
3)程序运行的地址不确定
因为内存地址是随机分配的，所以程序运行的地址也是不确定的。
(2)虚拟地址和物理地址
对于32位系统，寻址指针为4字节，对应的虚拟地址空间为0-2^32，即0-4G。
对于64位系统，寻址指针为8字节，对应的虚拟地址空间为0-2^64，即0-16G。
要注意的是，这个地址空间是虚拟的，并非实际存在的。
Linux内核把虚拟地址空间分为两部分：用户进程空间，内核进程空间。
在缓存原理中，换入/换出的数据以块为最小单位。在内存管理时，==页是地址空间的最小单位。==虚拟页和物理页的大小是一样的，通常为4KB。

• 虚拟页和物理页存在着以下关系：
  虚拟页和磁盘文件映射，然后缓存到物理页。
  根据是否映射，是否缓存，可以将虚拟页的状态分为以下三种：
  1)未映射的页
  即虚拟页没有映射到磁盘文件
  2)未缓存的页
  虚拟页映射到了磁盘文件，但是没有缓存到物理页，也就是内存上。
  3)缓存的页
  虚拟页映射到了磁盘文件，并且缓存到物理页

(3)虚拟地址的工作原理
对于进程来说，使用的都是虚拟地址。每个进程维护一个单独的页表。何为页表？
页表是一种数组结构，存放着各虚拟页的状态，是否映射，是否缓存。
1)数组的索引号，表示虚拟页号
2)数组的值
若为null，表示未映射的页
若非null，第一位表示有效位，为1，表明缓存的页；为0，表明未缓存的页。
其余位表示缓存到的物理页号。

进程执行时，当需要访问虚拟地址中存放的值时，步骤如下：

• 1)CPU会先找到虚拟地址所在的虚拟页(VP3)，根据页表，找出页表中第3条的值。
  判断有效位，为1，DRMA缓存命中，获根据物理页号，找到物理页中的内容，返回。
• 2)若有效位为0，产生缺页异常，调用内核缺页异常处理程序。
  它会选择一个物理页(如PP4)，作为牺牲页，将该页的内容刷新到磁盘文件。然后，把VP3映射的磁盘文件，缓存到该物理页。页表中的第3条，有效位变1，同时，物理页号表号变为PP4。
• 3)缺页异常处理完毕后，返回中断前的指令，重新执行，此时缓存命中，执行1)
• 4)将找到的内容映射到高速缓存，CPU从高速缓存中获取该值，结束。

(4).使用虚拟地址需要注意的问题
1)磁盘和主存传送页的活动叫做页面调度。页面调度会引起磁盘流量，如果程序的局部性不好，会频繁进行页面调度，叫做“缓存颠簸”。
2)一级页表占用的空间是比较大的，根据按需调度的原则，一般使用的是多级页表，即一级页表指向二级页表，这样大大压缩了页表的大小。
(5).地址翻译
地址翻译指的是DRAM缓存命中时，由虚拟地址找到物理地址的过程。该过程是完全由硬件来完成的。

• 1)CPU有一个专门的页表基地址寄存器(PTBR)指向当前页表的基地址，快速定位到该进程的页表。
• 2)根据虚拟页号，找到虚拟地址在页表的值。
• 3)根据值中的物理页号，找到物理地址。

(6).Linux中的虚拟内存机制
Linux把虚拟内存划分成区域area的集合，一个area包括连续的多个页。
请求分页系统中，只需要将当前需要的一部分页面装入内存，而其余部分留在外存，就可以启动程序。在执行的过程中，当所要访问的页面不在内存时，通过调页功能将其调入，同事可以通过置换功能将当前不用的页面换到外存上，以腾出内存空间

• 在Linux中，当发生缺页异常时，步骤如下：
  1)缺页异常程序，检查虚拟地址在哪个area内。
  2)访问的虚拟页若没有读写权限，则触发一个保护异常，终止进程。
  3)选择牺牲页，刷新到磁盘，从磁盘加载缺失的内容到物理页，更新页表。

(7)深入理解

• 1.每个进程的4G内存空间只是虚拟内存空间，每次访问内存空间的某个地址，都需要把地址翻译为实际物理地址
• 2.所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上
• 3.进程要知道哪些内存地址上的数据在物理内存上，哪些不在，还有在物理内存上的哪里，需要页表记录
• 4.页表的每一个表项分为两部分，第一部分记录此页是否在物理内存上，第二部分记录物理内存的地址
• 5.当进程访问某个虚拟地址，去查看页表，如果对应的数据不在物理内存中，，则缺页异常
• 6.缺页异常的处理过程，就是把进程需要的数据从磁盘拷贝到物理内存中，如果内存已经满了 ，没有空地方，那就找一个页进行覆盖，当然如果被覆盖的页曾经被修改过，需要将此页写回磁盘

（二）MMU
从CPU到MMU的地址称为虚拟地址（ Virtual Address，以下简称VA） ，而MMU将这个地址翻译成另一个地址发到CPU芯片的外部地址引脚上，也就是将虚拟地址映射成物理地址

1. 在操作系统初始化或者分配、释放内存时，会执行一些指令在物理内存中填写页表，然后，用指令设置MMU，告诉MMU页表在物理内存中的什么位置。
2. 设置好之后， CPU每次执行访问内存的指令都会自动引发MMU做查表和地址转换的操作，地址转换操作完全由硬件完成，不需要用指令控制MMU去做。

12. 能否实现一个LRU算法
选择最近最长时间未访问过的页面淘汰，认为过去一段时间内未被访问过的页面在最近的将来可能也不会淘汰。
查找快，插入快，删除快，有顺序之分。必须有顺序之分，以区分最近使用的和久未使用的数据；而且我们要在 cache 中查找键是否已存在；如果容量满了要删除最后一个数据；每次访问还要把数据插入到队头。
LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。

13. 海量数据的bitmap使用原理
所谓的BitMap就是用一个bit位来标记某个元素所对应的value，而key即是该元素，由于BitMap使用了bit位来存储数据，因此可以大大节省存储空间。
基本思想：
这此我用一个简单的例子来详细介绍BitMap算法的原理。假设我们要对0-7内的5个元素(4,7,2,5,3)进行排序(这里假设元素没有重复)。我们可以使用BitMap算法达到排序目的。要表示8个数，我们需要8个byte。

• 1.首先我们开辟一个字节(8byte)的空间，将这些空间的所有的byte位都设置为0
• 2.然后便利这5个元素，第一个元素是4，因为下边从0开始，因此我们把第五个字节的值设置为1
• 3.然后再处理剩下的四个元素，最终8个字节的状态如下图
  
• 4.现在我们遍历一次bytes区域，把值为1的byte的位置输出(2,3,4,5,7)，这样便达到了排序的目的

14. memcache了解
分布式内存对象缓存系统，用于动态Web应用以减轻数据库的负载。它通过在内存中缓存数据和对象来减少读取数据库的次数，从而提高了网站访问的速度。存储键值对的HashMap。适合对数据库有高并发读写和海量数据处理的场景。

15. 一般情况下在Linux/windows平台下栈空间的大小
win是编译器决定栈的大小，记录在可执行文件中，默认是1M。linux是os来决定的，在系统环境变量中设置， ulimit -s 命令查看修改，我的是8M

16. 内存泄露与内存溢出的区别

• 定义
  内存泄漏memory leak :是指程序在申请内存后，无法释放已申请的内存空间，一次内存泄漏似乎不会有大的影响，但内存泄漏堆积后的后果就是内存溢出。
  内存溢出 out of memory :指程序申请内存时，没有足够的内存供申请者使用，或者说，给了你一块存储int类型数据的存储空间，但是你却存储long类型的数据，那么结果就是内存不够用，此时就会报错OOM,即所谓的内存溢出。
• 二者关系
  （1）内存泄漏的堆积最终会导致内存溢出
  （2）内存溢出就是你要的内存空间超过了系统实际分配给你的空间，此时系统相当于没法满足你的需求，就会报内存溢出的错误。
  （3）内存泄漏是指你向系统申请分配内存进行使用(new)，可是使用完了以后却不归还(delete)，结果你申请到的那块内存你自己也不能再访问（也许你把它的地址给弄丢了），而系统也不能再次将它分配给需要的程序。
  （4）内存溢出：一个盘子用尽各种方法只能装4个果子，你装了5个，结果掉倒地上不能吃了。这就是溢出。比方说栈，栈满时再做进栈必定产生空间溢出，叫上溢，栈空时再做退栈也产生空间溢出，称为下溢。就是分配的内存不足以放下数据项序列,称为内存溢出。说白了就是我承受不了那么多，那我就报错
• 内存溢出原因：
  （1）内存中加载的数据量过于庞大，如一次从数据库取出过多数据；
  （2）集合类中有对对象的引用，使用完后未清空
  （3）代码中存在死循环或循环产生过多重复的对象实体；
  （4）使用的第三方软件中的BUG；
  （5）启动参数内存值设定的过小
• 内存溢出的解决方案：
  （1）直接增加内存
  （2）检查错误日志，查看“OutOfMemory”错误前是否有其 它异常或错误。
  （3）对代码进行走查和分析，找出可能发生内存溢出的位置。
  （4）使用内存查看工具动态查看内存使用情况

17. 编程时如何定位内存泄漏

• 常见的内存错误：
  （1）内存分配未成功，却使用了它
  （2）内存分配成功，但尚未初始化就引用它
  （3）内存分配成功且初始化，但操作越过了内存的边界
  （4）忘记释放内存，造成内存泄漏
  （5）释放了内存却继续使用它
• 方法
  （1）重载new/delete操作符
  重载new/delete操作符，用list或者map记录对内存的使用情况。new一次，保存一个节点，delete一次，就删除节点。
  最后检测容器里是否还有节点，如果有节点就是有泄漏。也可以记录下哪一行代码分配的内存被泄漏。
  类似的方法：在每次调用new时加个打印，每次调用delete时也加个打印。
  （2）查看进程maps表
  在实际调试过程中，怀疑某处发生了内存泄漏，可以查看该进程的maps表，看进程的堆或mmap段的虚拟地址空间是否持续增加。如果是，说明可能发生了内存泄漏。如果mmap段虚拟地址空间持续增加，还可以看到各个段的虚拟地址空间的大小，从而可以确定是申请了多大的内存。

18. 缓冲区实现，为什么不使用循环队列

• 缓冲区的设计：
  （1）缓冲区是一个先进先出队列。写入模块将信息插入队列；读出模块将信息弹出队列。
  （2）写入模块与读出模块需要进行信息的协调和同步。
  （3）对于多线程和多进程的写入或读出模块，写入模块间以及读出模块间需要进行临界区处理。
• 循环队列实现
  环形队列的特点是，不需要进行动态的内存释放和分配，使用固定大小的内存空间反复使用。在实际的队列插入和弹出操作中，是不断交叉进行的。空队列时头指针和尾指针重合且都为0，当分配一个内存时head（头指针）加1；当释放一个内存时tail（尾指针）加1。这样就实现了先入先出。当入队操作时，head会增加；而出队操作时，tail会增加。入队的速度快的时候，head有可能追上 tail，这个时候说明队列已经满了，不能再进行入队的操作了，需要等待出队 操作腾出队列的空间。当 出队 的操作快，使得 tail 追上 head，这个时候说明队列已空了，不能再进行出队 操作了，需要等待 入队 进来数据。

19. 虚拟内存实现有哪几种方式？有什么意义？
三种：请求分页存储管理；请求分段存储管理；请求段页式存储管理
20. 请求页面置换策略有哪些方式？他们的区别是什么？各自有什么算法解决？
全局和局部；
全局：在整个内存空间置换
局部：在本进程中进行置换
全局：（1）工作集算法（2）缺页率置换算法
局部：（1）最优算法（2）FIFO先进先出算法（3）LRU最近最久未使用（4）时钟算法