从内存管理开始

在接下来的一段时间内,我们假定一个程序在执行时是全部加载到内存中的(包括动态加载和动态链接时加载到内存中的程序)。

逻辑地址空间和物理地址空间

我们将CPU所生成的地址称为逻辑地址, 而内存单元所看到的地址称为物理地址
运行时从虚拟地址到物理地址的映射由称为内存管理单元(MMU)的硬件设备来完成。下图表示了一个简单的由基址寄存器实现的MMU,将CPU产生的逻辑地址加上基址寄存器的值,就生成了物理地址。

通常将逻辑地址的集合称为逻辑地址空间,这些逻辑地址空间所对应的物理地址的集合称为物理地址空间。MMU就是将逻辑地址空间映射到物理地址空间。

交换

在前面假设过,目前进程需要在内存中以便执行。但是进程也可以暂时从内存中交换到备份存储上,当需要再次执行时再调回到内存中。

比如一个进程的时间片用完,内存管理器将刚执行完的程序从内存中换出,然后将另一个进程还如到刚刚释放的内存空间中。
一般交换空间作为磁盘的一整块,而且独立于文件系统,换出的速度因此会很快。在后面会讲到。这种粗暴的交换方式现在用的很少,而且交换所需要的时间也很长。在后面会介绍按需调页等置换算法。

连续内存分配

内存通常分为两个区域,一个用于驻留操作系统,另一个用于用户进程。
通常需要将多个进程同时放到内存中,因为需要考虑如何为进程分配内存空间。当使用连续内存分配时,给每个进程都分配一个连续的内存区域。
这时需要考虑内存映射和内存保护的问题。这里使用基址寄存器和界限地址寄存器来实现。

现在来讨论内存分配。最简单的方法是将内存分为多个固定大小的分区,每个分区只容纳一个进程。
另外还有可变分区的方案,操作系统维护一个表,记录那些内存可用和哪些内存已被占用。一开始,所有内存都可以用于用户进程,因此可以做为一大块可用内存,称为孔。当有新进程需要内存时,为该进程查找足够大的孔。如果找到,可以从改孔为该进程分配所需的内存,孔内未分配的内存可以下次使用。
但是如何为进程分配内存,有许多解决方法,比如首次适应,最佳适应,最差适应等。

  • 首次适应:分配第一个足够大的孔。
  • 最佳适应:分配最小的足够大的孔。
  • 最差适应:分配最大的孔。

碎片问题。内存分配算法可能产生外部碎片问题。随着进程装入和移出内存,空闲内存空间被分为小片段。当所有总的可用内存之和可以满足请求,但是不连续时,就出现了外部碎片问题。
另外还有一个内部碎片问题,就是当给进程分配了一块内存空间,但是可能分配的内存空间由于某些原因比进程需要的要多一点点,比如需要对齐等,就出现了内部碎片的问题。

外部碎片和内部碎片在后来程序在堆上动态分配内存中,也是一个问题。

在解决进程的内存分配的外部碎片问题,一种方案是使用分页。

分页

分页内存管理方案允许进程的物理空间可以是非连续的。分页避免了将不同大小的内存块匹配到交换空间上这样的麻烦。

实现分页的基本方法涉及到将物理内存分为固定大小的块,称为帧,而将逻辑内存也分为同样大小的块,称为页。当需要执行进程时,其页从备份存储中调入到可用的内存帧中。备份存储也分为固定大小的块,其大小与内存帧一样。


由CPU生成的每个地址分为两个部分:页号(p)和页偏移(d)。页号作为页表中的索引。页表包含每页所在物理内存的基地址,这些基地址与页偏移的组合就形成了物理地址。内存的页模型如下图所示。

页表的硬件实现一般是将页表放在内存中,并将页表基址寄存器(PTBT)指向页表。改变页表只要改变这一寄存器就可以,这也大大降低了切换时间。
但是这种方法的问题是访问用户内存位置需要一些时间。如果需要访问位置I,需要先用PTBR中的值再加上页号i的便宜,来查找页表。然后根据所得的帧号,再加上页便宜,就得到了真实物理地址。截止访问内存中所需的位置。采用这种方案,访问一个字节需要两次内存访问,这样访问的速度就会减半。
对这一问题得解决方案是采用小但专用而且快速的硬件缓冲,这种缓冲称为转换表缓冲(TLB).TLB条目由两部分组成:键和值,当关联内存根据给定值查找时,它会同时与所有的键值进行比较,如果找到条目,就返回相应的值。
当页码不在TLB中,就需要访问页表。当得到帧号后,就可以用它来访问内存。同时将页号和帧号添加到TLB中。如果TLB已满,则使用LRU等替换策略替换。

层次页表