计算机操作系统内存管理是十分重要的,因为其中涉及到很多设计很多算法。《深入理解计算机系统》这本书曾提到过,现在操作系统存储的设计就是“带着镣铐跳舞”,造成计算机一种一种容量多,速度快的假象。包括现在很多系统比如数据库系统的设计和操作系统做法相似。所以在学习操作系统之余我来介绍并总结一些操作系统的内存管理。
首先我们看一下计算机的存储层次结构
按照金字塔结构可以分为四种类型: 寄存器,快速缓存,主存和外存。而
寄存器和L1缓存
都在Processor内部。在金字塔中,越往下价格越低速度越慢但容量越大。
简言之就这两个空间分别是程序员能够观测到的存储空间和真实的物理空间。
需求:
为了满足需求的目标:
操作系统在内存中的位置有以下三种可能
此时整个内存只有两个程序,即用户程序和操作系统。
操作系统所占的空间是固定的,则用户程序空间也是固定的,因此可以将用户程序永远加载到同一个地址,即用户程序永远从同一个地方开始运行。这种情况下,用户程序地址可以在运行之前就可以计算出来。
我们通过加载器计算程序运行之前的物理地址静态翻译。此时既不需要额外实现地址独立和地址保护。因为用户不需要知道物理内存的相关知识,而且也没有其它用户程序。
此时用户的程序空间需要通过分区来分给多个不同的程序了。每个应用程序占用一个或几个分区,这种分配支持多个程序并发执行,但难以进行内存分区的共享。
其中分区有两种方法:
顾名思义就是把内存划分为若干个固定大小的连续分区,这几个分区或者大小相等以适合多个相同程序并发,或者大小不等的分区以适合不同大小的程序。
这种分配方法优点很明显,在于非常容易实现,开销小。
缺点就是会产生很多内部碎片(也就是未被利用的存储空间),固定的分区总数也限制了并发执行的程序数目。我们简单介绍下静态分配的几种方法。
此时分区的边界可以移动,但也产生了分区与分区之间狭小的外部碎片。
在可变分区中,知道内存的空闲空间大小就十分重要了。OS通过跟踪内存使用计算出内存有多少空闲。跟踪的方法有两种:
也就是所谓的bitmap
,用每一位来存放某种状态。将内存每一个分配单元赋予一个判断的用于判断状态的字位,字位取值位0
表示单元闲置;字位为1
表示单元被占用
特点
将分配单元按照是否闲置链接,P代表这个空间被占用,H代表这个这是一片闲置空间。为了方便遍历查询,每个程序空间的结点接着一个空闲空间的结点每个链表结点还有一个起始地址,与分配单元的大小,用代码表示为
enum Status{P=0,H=1};struct LinkNode{ enum Status status; struct LinkNode *begin_address; size_t size; struct LinkNode *next;};
特点
1. 空间成本:取决于程序数量
2. 时间成本:链表不停的遍历速度很慢,同时还要进行链表的插入和删除修改。
3. 有一定的容错能力,可以通过程序空间结点和空闲空间结点相互验证。
OS通过上面两种跟踪方法知道内存空闲容量,而现在操作系统一般都以链表的形式进行内存空闲容量跟踪。如果有新的程序需要读入内存,可变分区就要对空闲的分区进行内存分配。 内存分配使用两张表:已分配分区表和未分配分区表。用C++描述如下:
struct FreeBlock { int id; int address; unsigned length; };
struct AllocatedBlock { int id; int address; int pid; unsigned length; };
然后OS用双向链表将所有未分配分区表进行串联
struct{ FreeBlock data; Node* prior; Node* next;}Node;
未分配分区表在整个系统空间上的结构如下:
这里我们介绍四种基于顺序搜索的寻找空闲存储空间的算法:
系统中空闲分区表如下按照地址递增次序排列,现有三个作业分配申请内存空间100K
,30K
,7K
。
1 | 32K | 20K | 未分配 |
---|---|---|---|
2 | 8K | 52K | 未分配 |
3 | 120K | 60K | 未分配 |
4 | 331K | 180K | 未分配 |
100K
,从低地址到高地址找到3号分区,分配完后3号分区起始地址变为100K+60K=160K
,剩余空间为120K-100K=20K
30K
,从低地址到高地址找到1号分区,分配完后1号分区起始地址变为20K+30K=50K
,剩余空间为32K-30K=2K
7K
,从低地址到高地址找到2号分区,分配完后2号分区起始地址变为52K+7K=59K
,剩余空间为8K-7K=1K
100K
,找到3号分区,分配完后3号分区起始地址变为100K+60K=160K
,剩余空间为120K-100K=20K
30K
,从3号分区后继续出发,找到4号分区,分配完后4号分区起始地址变为180K+30K=210K
,剩余空间为331K-30K=301K
7K
,从4号分区后继续出发,找到1号分区,分配完后1号分区起始地址变为20K+7K=27K
,剩余空间为32K-7K=25K
100K
,找到最适合的3号分区,分配完后3号分区起始地址变为100K+60K=160K
,剩余空间为120K-100K=20K
30K
,找到最适合的1号分区,分配完后1号分区起始地址变为20K+30K=50K
,剩余空间为32K-30K=2K
7K
,找到最适合的2号分区,分配完后1号分区起始地址变为52K+7K=59K
,剩余空间为8K-7K=1K
100K
,找到4号分区,分配完后3号分区起始地址变为180K+60K=240K
,剩余空间为331K-100K=231K
30K
,此时被分配过的4号分区依然容量最大,于是还是找到4号分区,分配完后4号分区起始地址变为240+30K=250K
,剩余空间为231K-30K=201K
7K
,此时被分配过的4号分区依然容量最大,找到4号分区,分配完后4号分区起始地址变为250+7K=257K
,剩余空间为201K-7K=194K
基于顺序搜索的分配算法实际上只适合小型的操作系统,大中型系统使用了是比较复杂的索引搜索的动态分配算法。
用iPad
画了一个简单的示意图如下:
内存分配实际上是操作系统非常重要的一环,如果仅限于理论而不写代码实践则容易迷惘,很多具体的实现与都比较困难。如上面的基于顺序搜索的最佳适应算法,比如几个分区的表示方法,都用到了数据结构和算法的知识。如果能用C或者C++完成上述几个算法和操作的具体实现,相信一定会大有脾益的。