操作系统——内存管理(附带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; //mapint 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说一下分段机制和分页机制的区别？

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