OS复习笔记ch7-1

存储的基本管理需求

重定位

重定位(Relocation)：需要解决可执行文件中地址（指令和数据）和内存地址的对应。

一般有两种比较常见的重定位方式：

静态重定位(static relocation)：当程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。
- 缺乏保护，可能会被其他程序非法访问
- 运行时无法再次定位：无法移动、对换
动态重定位(Dynamic Relocation)：在程序运行过程中要访问内存时再进行地址变换
- 需要硬件支持
- 需要OS参与

重定位是一个比较有意思的话题，在操作系统和计算机组成原理，甚至编译原理、汇编原理都会提到。简单地说，就是把我们代码中数据和指令的相对地址重新定位到实际内存地址，后面也会涉及到。

保护

即：未经许可，进程不能访问其他进程的内存位置（范围保护）

不过，在编译时不可能检查绝对地址，只能在运行时检查。

原因很简单，因为编译的时候我们拿不到实际的绝对地址，只有在实际运行的时候才会有，一般编译是得到机器代码，链接是得到逻辑地址，装入的时候才会确定实际的物理地址。

共享

即：允许多个进程访问同一内存区域(代码、数据)
举一个很简单的例子，绝大多数OS都有的剪贴板。当你复制了一份内容，你可以粘贴到微信，也可以粘贴到WPS甚至任何可以读取它的进程。

逻辑组织

逻辑组织可以看成是一种线性组织，一般是程序员自己为了模块化编程的需要组织起来的，所以称之为“逻辑”组织。有以下几个特点

有一些模块可以修改，有些不能(类似int和const int)
不同模块提供的保护不同（类似private和protected）
进程之间共享模块（类似公共的函数/数据区）
分段存储有助于逻辑组织（比如常见的代码段、数据段等）

物理组织

物理组织的话至少就有两个层次：主存和辅存。之前学习过组原的朋友都知道，主存一般指的内存，而辅存指的是外存。
如果OS的物理组织不好，程序、数据可用内存不足，搞不好就会卡死，甚至蓝屏。
对于后端程序员来说由于内存不可见，编程的时候粗心可能就会导致服务器内存泄漏，最后宕机。

内存划分

固定分区

等大分区：
内存被切成一个个相同大小的块

程序太大，无合适分区（一份米饭男生不够吃）
内存利用率不高（同样一份米饭女生吃不完）
内碎片问题严重（每个分区利用不全，产生内部碎片）

不等分区：
小程序放入小分区，减少内碎片；大程序放入大分区，避免无法分配。
在算法实现上变得更加复杂，需要选择合适的放置算法。此外，还有一些遗留问题：

活动进程的数目受限于系统
大量小进程无法有效利用空间

动态分区

按需分配，整体上提高了利用率

根据程序的运行的情况动态分区，每段内存按照程序需求的
分区与分区之间的外碎片的数量很多，虽然每一个占用空间不多，浪费也不少
→这时候就有了压缩技术，把已分配的分区向一个方向移动，将外碎片压缩。为了提高效率，还可以在分区的起始和截止地方存储分区的信息

然后，让我们来了解一下动态分区的放置算法

最佳适配算法

时间效率低下，由于要维护地址空间链表（B+树），每次放置之后由于需要再次排序导致复杂度高。并且由于像41KB这种不好分配的内存，可能会导致碎片更碎。

首次适配算法

每次从头开始寻找第一个足够大的分区，前端重复搜索，后端空闲较多
循环首次适配算法

每次从上次放置位置往后扫描第一个满足的内存分区，最大的分区容易被分割，需要压缩来获得新的大分区。
4. 最坏适应算法(worst-fit)：找到最大的空闲分区
基本不留下小空闲分区，但较大的空闲分区不被保留。
5. 快速适应算法(quick-fit)：为常用长度的空闲区建立单独的空闲区链表
可快速找到所需的空闲区，但是归还时合并复杂