操作系统——内存管理(附带Leetcode算法题LRU)
1.内存管理主要用来干什么？
操作系统的内存管理主要负责内存的分配与回收、内存扩充(虚拟技术)、地址转换(逻辑-物理)、内存保护(保证各进程在自己的内存空间运行，不会越界访问).....
2.什么是内存碎片？
内存碎片是内存的申请和释放产生的，内存碎片会导致内存利用率下降。内存碎片分为内部内存碎片和外部内存碎片。
-
内部内存碎片：分配的内存比实际使用的内存大，哪些没有被使用的内存就被称为内部内存碎片。
- 外部内存碎片：内存并没有紧挨着被分配，这些没有被分配的内存区域太小，不能满足任意进程的内存分配请求，这些小片段且不连续的内存空间被称为外部碎片。
3.虚拟内存
3.1传统存储管理方式的缺点？
作业数据必须一次全部调入内存，作业数据在整个运行期间都会常驻内存。
3.2局部性原理
-
时间局部性：现在访问的指令、数据在不久后很可能会被再次访问。
-
空间局部性：现在访问的内存单元周围的内存空间，很可能在不久后会被访问。
3.3什么是虚拟内存？有什么用？
虚拟内存本质上来说只是逻辑存在的，是一个假想出来的内存空间，若内存空间不够，由操作系统负责将内存中暂时不用到的信息换出到外存，在用户看来似乎有一个比实际内存大得多的内存，主要作用是作为进程访问主物理内存的桥梁并简化内存管理。
当访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存(请求调页)，内存空间不够时，将内存中暂时用不到的信息换出到外存(页面置换)。虚拟内存的实现是非连续的分配管理方式。
4.内存空间的分配与回收
4.1连续分配
连续分配管理的方法有单一连续分配、固定分区分配、动态分区分配。
-
单一连续分配：会产生内部内存碎片。
-
固定分区分配：会产生内部内存碎片。
-
动态分区分配：会产生外部内存碎片
4.2非连续分配(离散式的)
非连续分配管理的方法有段式管理、页式管理、段页式管理。
-
段式管理：将物理内存和虚拟内存分为不等长的段，通过段表映射虚拟地址和物理地址。虚拟地址中有两部分为段号和段内偏移量，由段号去段表中查找，找到段号对应的起始地址，然后将起始地址替换虚拟地址的段号部分，得到的起始地址+段内偏移量就为物理地址。分段会产生外部内存碎片。
- 页式管理：将物理内存和虚拟内存分为等长连续的页，可有效避免外部内存碎片的问题，但也可能出现内部内存碎片。分页管理通过多级页表映射虚拟地址和物理地址，虚拟地址中有两部分为页号和页面偏移量，拿着页号去应用程序的页表中查找，找到物理页号，得到的物理页起始地址+页内偏移量就为最终的物理地址。
注意：多级页表属于时间换空间的典型场景，利用增加页表查询的次数减少页表占用的空间！
为了提高虚拟地址到物理地址的转换速度，引入了快表TLB，类似Redis的作用，来做虚拟页号到物理页号的缓存。
4.2.1换页机制
换页机制：有时我们会发现一个有趣的现象，就是我们看起来一个进程运行所需的内存比我们电脑的内存要大，但是这个进程也是能正常运行，这就是换页机制带来的好处，操作系统选择一些不常用的物理页，将它们的内存先放入磁盘，等到需要使用时再从磁盘上加载，换页机制利用磁盘这种较低廉的存储设备扩展物理内存，以时间换空间的做法。
4.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;
}
}
-
段页式管理：结合了段式管理和页式管理，把物理内存先分成若干段，每个段又继续分成若干大小相等的页，先进行段式地址映射，再进行页式地址映射。
4.2.3页面抖动现象？
刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，页面频繁换入换出的现象，称为抖动，主要原因是分配给进程存储数据的物理区域不够。
4.2.4说一下分段机制和分页机制的区别？
分页机制以页面为单位进行内存管理，而分段机制以段为单位进行内存管理；页的大小是固定的、而段的大小是不固定的；所以分段机制会产生外部内存碎片问题，分页机制没有外部内存碎片问题，但由于固定页，所以可能会产生内部内存碎片；页是物理单位、而段是逻辑单位；页表是通过一级页表和二级页表等多级页表来实现多级映射，而段表是单个的。