操作系统——内存管理(附带Leetcode算法题LRU)

目录

1.内存管理主要用来干什么？

2.什么是内存碎片？

3.虚拟内存

3.1传统存储管理方式的缺点？

3.2局部性原理

3.3什么是虚拟内存？有什么用？

3.3.1段式分配

3.3.2页式分配

3.3.2.1换页机制

3.3.2.2页面置换算法

3.3.2.3页面抖动现象？

3.3.3段页式管理

3.3.4说一下分段机制和分页机制的区别？

4.连续内存分配方式

1.内存管理主要用来干什么？

操作系统的内存管理主要负责内存的分配与回收、内存扩充(虚拟技术)、地址转换(逻辑-物理)、内存保护(保证各进程在自己的内存空间运行，不会越界访问).....

2.什么是内存碎片？

内存碎片是内存的申请和释放产生的，内存碎片会导致内存利用率下降。内存碎片分为内部内存碎片和外部内存碎片。

内部内存碎片：分配的内存比实际使用的内存大，哪些没有被使用的内存就被称为内部内存碎片。

 外部内存碎片：内存并没有紧挨着被分配，这些没有被分配的内存区域太小，不能满足任意进程的内存分配请求，这些小片段且不连续的内存空间被称为外部碎片。

3.虚拟内存 3.1传统存储管理方式的缺点？

作业数据必须一次全部调入内存，作业数据在整个运行期间都会常驻内存。

3.2局部性原理

时间局部性：现在访问的指令、数据在不久后很可能会被再次访问。

空间局部性：现在访问的内存单元周围的内存空间，很可能在不久后会被访问。

3.3什么是虚拟内存？有什么用？

虚拟内存就是进程和实际物理内存的中间层，虚拟内存本质上来说只是逻辑存在的，是一个假想出来的内存空间，主要作用是作为进程访问主物理内存的桥梁并简化内存管理。

为了防止多进程运行时造成的物理内存地址的冲突，引入了虚拟内存。每个进程都有自己的虚拟内存，使得进程以为自己独占了全部物理内存，其实进程访问的都是虚拟内存中的地址，虚拟地址由MMU地址翻译转换为物理内存地址。

        MMU的主要机制有三种：分段机制、分页机制、段页机制。

        因为每一个进程都有虚拟内存，那么实际的物理内存空间肯定比所有进程的虚拟内存空间小，所以并不是所有的虚拟内存都会分配物理内存，当进程对某块虚拟内存进行读写时，如果发现虚拟内存没有映射到物理内存，就会发生缺页中断，才会真正的分配物理内存，使用分段和分页机制管理虚拟地址到物理内存地址的映射关系

        非连续分配管理的方法有段式管理、页式管理、段页式管理。

3.3.1段式分配

段式管理：将物理内存和虚拟内存分为不等长的段，通过段表映射虚拟地址和物理地址。虚拟地址中有两部分为段号和段内偏移量，由段号去段表中查找，找到段号对应的起始地址，然后将起始地址替换虚拟地址的段号部分，得到的起始地址+段内偏移量就为物理地址。分段会产生外部内存碎片。

3.3.2页式分配

页式管理：将物理内存和虚拟内存分为等长连续的页，可有效避免外部内存碎片的问题，但也可能出现内部内存碎片。分页管理通过多级页表映射虚拟地址和物理地址，虚拟地址中有两部分为页号和页面偏移量，拿着页去应用程序的页表中查找，找到物理页号，得到的物理页起始地址+页内偏移量就为最终的物理地址。  

注意：多级页表属于时间换空间的典型场景，利用增加页表查询的次数减少页表占用的空间！

        为了提高虚拟地址到物理地址的转换速度，引入了快表TLB，类似Redis的作用，来做虚拟页号到物理页号的缓存。

3.3.2.1换页机制

换页机制：有时我们会发现一个有趣的现象，就是我们看起来一个进程运行所需的内存比我们电脑的内存要大，但是这个进程也是能正常运行，这就是换页机制带来的好处，操作系统选择一些不常用的物理页，将它们的内存先放入磁盘，等到需要使用时再从磁盘上加载，换页机制利用磁盘这种较低廉的存储设备扩展物理内存，以时间换空间的做法。

当访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存(请求调页)，内存空间不够时，将内存中暂时用不到的信息换出到外存(页面置换)。虚拟内存的实现是非连续的分配管理方式。

3.3.2.2页面置换算法

页面置换算法：常见的有先进先出页面置换算法、最近最久未使用页面置换算法(LRU)、最近最少使用页面置换算法(LFU)。

class LRUCache { static class Node{ int key; int value; Node preNode; Node nextNode; public Node(int key,int value){ this.key = key; this.value = value; } } //自定义结点 HashMap<Integer,Node> map; //map int size; //map中存储的元素个数 int capacity; //最大容量 Node dummyHead; //虚拟头结点 Node dummyTail; //虚拟尾结点 public LRUCache(int capacity) { this.capacity = capacity; this.size = 0; dummyHead = new Node(-1,-1); dummyTail = new Node(-1,-1); map = new HashMap<>(); dummyHead.nextNode = dummyTail; dummyTail.preNode = dummyHead; } public int get(int key) { Node node = map.get(key); if(node==null){ //说明没有这个键 return -1; } //将这个结点移动到首部 moveNodeToHead(node); return node.value; } public void put(int key, int value) { Node node = map.get(key); if(node==null){ //如果不存在，则证明要添加 //创建结点 Node curNode = new Node(key,value); //添加进map中 map.put(key,curNode); //添加到头部，因为也算是访问了 addNodeToHead(curNode); this.size++; if(this.size>capacity){ //删除最久没被访问的结点 Node tailNode = removeTailNode(); map.remove(tailNode.key); this.size--; } }else{ //如果存在，则证明只需要修改元素值，以及移动到头部即可 node.value = value; moveNodeToHead(node); } } private Node removeTailNode() { //删除尾部的结点并且返回 Node resultNode = dummyTail.preNode; moveNode(resultNode); return resultNode; } private void addNodeToHead(Node node) { //将结点添加到头部 node.preNode = dummyHead; node.nextNode = dummyHead.nextNode; dummyHead.nextNode.preNode = node; dummyHead.nextNode = node; } private void moveNodeToHead(Node node) { //失去前后的联系 moveNode(node); //移动到头部 addNodeToHead(node); } private void moveNode(Node node){ //删除结点 node.preNode.nextNode = node.nextNode; node.nextNode.preNode = node.preNode; } } 3.3.2.3页面抖动现象？

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，页面频繁换入换出的现象，称为抖动，主要原因是分配给进程存储数据的物理区域不够。

3.3.3段页式管理

段页式管理：结合了段式管理和页式管理，把物理内存先分成若干段，每个段又继续分成若干大小相等的页，先进行段式地址映射，再进行页式地址映射。

3.3.4说一下分段机制和分页机制的区别？

分页机制以页面为单位进行内存管理，而分段机制以段为单位进行内存管理；页的大小是固定的、而段的大小是不固定的；所以分段机制会产生外部内存碎片问题，分页机制没有外部内存碎片问题，但由于固定页，所以可能会产生内部内存碎片；页是物理单位、而段是逻辑单位；页表是通过一级页表和二级页表等多级页表来实现多级映射，而段表是单个的。

4.连续内存分配方式

连续分配管理的方法有单一连续分配、固定分区分配、动态分区分配。

单一连续分配：会产生内部内存碎片。

固定分区分配：会产生内部内存碎片。

动态分区分配：会产生外部内存碎片