启蒙篇

CPU执行程序的基本原理？

我们以“3+2”这条指令的执行过程为例：

先将这条指令从磁盘中读到内存中，“3”、“2”、“+”分别在内存中的不同地址上存储。

CPU先发出一个地址信号，通过地址总线找到“3”这条数据所在内存中某一行的地址，然后再根据这个地址中的八位数据分别对应的八条数据总线，将数据传入CPU的某个寄存器中（假设传入到“R₀”寄存器中）

同理，“2”这条数据也是经过以上过程传入到“R₁”寄存器中的。

但如果是指令（例如“+”），则不会被读入CPU的寄存器中，他会事先被CPU中的ALU（算数逻辑运行单元，是执行各种指令操作的一个元件）所识别读入进去，等待另一条数据读入寄存器后，再做加法运算。

运行结束后，会产生一个“5”的数据，它存储到“R₂”的寄存器中。

“5”如果要进入到内存存储，则是数据进入CPU的逆过程，此处不再赘述。

通过以上的例子，我们需要注意：

• 程序最终是一条一条的被读入寄存器内执行的。也就是说，一个程序执行的路线为：磁盘->内存->CPU->内存。（CPU中寄存器的个数是非常有限的，一般只有几十个，而且这几十个寄存器又是按照功能分类的，分为通用寄存器和特殊寄存器，特殊寄存器只能被一些特殊的指令去访问，普通寄存器什么指令都可以访问。既能够访问通用寄存器，也可以访问特殊寄存器那一部分程序就形成了一种状态——内核态，其他那一部分代码就形成了用户态，操作系统处于两种状态之间。）

• 内存卡是一个临时保存程序的一个中介;磁盘是一个永久保存程序的介质。

• 地址总线的选中原理：译码器原理

• 了解四大类存储器的速度和所处位置：

  位置：

  ​ 寄存器：在CPU的内部；

  ​ cache（缓存）：在CPU的内部；

  ​ 内存：CPU的外部；

  ​ 磁盘：CPU的外部；

  速度（速度越快，成本越高）：

  ​ 寄存器 > cache （cache的数据仍然要装到寄存器中）> 内存 > 磁盘（越靠近CPU的速度越快）

相似概念的区分和总结

CPU位数：实际上就是CPU内寄存器的位数，CPU位数越大，一次性能够处理的数据也就越多。

OS位数：OS位数会受到CPU位数的限制，也就是OS位数只能小于或等于CPU的位数。例：32位CPU只能安装32位以下的操作系统。（硬件限制软件）
数据总线数：常见的为8位的，主要影响数据向CPU寄存器中的传输次数。例如：CPU为32位，数据总线数为8位，则需要传4次才可以把这个CPU中的一个寄存器存满。

物理地址总线数：物理地址可以存放地址的总位数，相当于物理地址位数。他可以限制可访问内存大小。

可访问内存大小（三方面的最小值）：

​ 物理地址总线数可以限制它（硬件限制），例如：32位的物理地址位数->可访问内存大小就是2³²B。

​ 内存卡大小也可以限制它（根据实际情况限制），内存卡买小了，物理地址总线数够了也没用！

​ OS位数也可以限制它（软件限制），即使物理总线数够了，但是还是OS说用多少就用多少！

​ 逻辑地址位数：等价于操作系统的位数。逻辑地址位数是由操作系统中所能运行的最大程序决定的，而操作系统本身就是这个最大程序。

​ 虚拟内存理论大小：等价于逻辑地址位数。

​ 虚拟内存实际大小：可访问内存大小+磁盘大小 >= 虚拟内存实际大小 <= 虚拟内存理论大小

内存管理逻辑图

基础篇

程序的基础知识

编译

将源代码编译成汇编代码或机器代码，编译后产生的目标模块，都有自己的地址，这个地址为逻辑地址（相对地址）。在目标模块中指令中出现的地址都是逻辑地址。

链接

各个模块需要合并为一个模块，先将地址重新按照一定的顺序进行编码，编码时，还要给后面的模块进行地址上的偏移。

经过编译链接后就会形成可执行文件。

通过安装这个可执行文件，可以把这个程序存放在磁盘中。

装入

装入介绍

当程序从磁盘中装入到内存中时，会出现如下问题：CPU认为是从内存的起始地址开始的，而程序却认为是从程序的起始地址开始的，这样便造成了一种地址上的错位。

（因为程序有多个，所以程序上的地址为相对自己的地址，称为相对地址；而内存只有一个，所以地址是绝对的，称为绝对地址。）

（注：内存上的地址为物理地址（绝对地址），而程序上的地址为逻辑地址（相对地址），问题是由物理地址与逻辑地址之间的错位造成的。）

所以，如果随意的装入程序，CPU可能无法正常运行每一条程序。

下面，提供了三种解决此问题的方案：绝对装入、静态重定位装入、动态重定位装入。

绝对装入

装入前，就确定好程序的装入位置，修改好编译连接后的逻辑地址，使得逻辑地址与物理地址对齐（不错位）。

事先在编译链接后就确定好逻辑地址的开始位置，然后装入后只能装在指定的内存位置。（程序员事先肯定知道要装入到内存的哪个地址）

静态重定位装入

装入时，由装入程序（操作系统的一部分）对逻辑地址进行一次性的修改，从而避免错位。

在程序从磁盘装入到内存的过程中，一边装入，一边修改程序的逻辑地址。此时，装入程序起到了至关重要的作用。（程序员事先不知道要装入到哪里）

重定位：如果我今天装完了一个程序A，它在内存的起始位置为1000，等到今天程序A 运行结束后，明天我又想装入程序A，但此时他只能装在内存地址500的地方，这时，装入程序就会重新定位程序A的地址，将其装入500的位置。

静态：一旦装入后就不能随便在内存中移动。如果我今天装完了一个程序A，它在内存的起始位置为1000，这时，程序A还没有运行结束，我想让程序A向上移动100个地址，这时，就会发生错位，除非将程序A结束后，重新装入才可以。

动态重定位装入

程序运行时，利用重定位寄存器的弥补作用，让CPU以为逻辑地址与物理地址是对齐的（不错位）。

弥补作用（加法）：程序从磁盘中原原本本的装入到内存中，然后重定位寄存器读取装入程序在内存中的入口地址（在程序的PCB中读取），将这个入口地址存入重定位寄存器中，然后把程序的地址和程序中的指定地址全部加上重定位寄存器中的数值，此时就起到了一个让CPU以为对齐的效果（实际上是没有对齐的，只是数值上的累加）。

如果此时装入后额的程序要在内存中移动，只需要让重定位寄存器读取程序PCB中的内存入口地址，将其存入到重定位寄存器中，再执行上述操作即可。

内存保护

操作系统必须要在内存中事先内存保护（越界保护）这一功能。在之前，进程间通信中我们知道，由于进程间是相互独立的，它们分配的内存也是相互独立的，因此需要进程间的通信。其实这就是一种进程保护，让各个进程之间的内存独立，不能直接的互相访问。

内存保护是由操作系统（实现更新任务）和相关硬件（实现具体实施任务）共同实现的。

有两种实现内存保护的方法，两者的实现原理是一样的，每次进程切换时，都要进行寄存器的更新（由进程档案袋PCB中的信息进行更新）：

上、下限寄存器

​ 在程序读入内存时，事先在上下限寄存器中，给该程序固定一个可访问内存地址的上限地址及下限地 址（程序在进入内存时，都有一个PCB，PCB中存放着该程序的内存地址的范围，寄存器就是由PCB确定的），在该程序访问内存地址之前，首先要CPU读一下上下限寄存器，如果不在上下限范围内，则提示程序越界。

基址寄存器（重定位寄存器）、限长寄存器

​ 重定位寄存器记录了程序在内存中的起始地址，限长寄存器记录了程序在内存中有多长。

（起始位置+长度=终点位置）

扩充内存的方法

覆盖技术

将程序各个子程序设计成层次分明的模块，每设计每一个层次就将用户区分一个区，主程序为固定区，一直在这个区内运行，其他程序为覆盖区，只能在固定的区域运行，每当有一个同层次的程序运行时，会自动覆盖之前运行的程序。

特点：

• 用在同一个程序（进程）中。
• 覆盖技术实现了小内存运行大程序，但并不是万能的。
• 对程序员要求极高。

对换技术

内存中同一时刻会有许多进程，有不同的运行状态，特别是阻塞状态，在内存中及占用位置但是迟迟不运行，在此刻，磁盘中有需要进入内存的进程，因为内存空间的不足进不来，此时就需要用到对换技术。

操作系统首先把进程中阻塞的进程装入磁盘中的“对换区”，再将磁盘中已经准备好的进程换入到内存中。

对换区：在具有对换功能的操作系统中，通常把磁盘分为文件区和兑换区两个部分。文件区是用来存储用户文件的区域，对它的主要目标是提高文件存储空间的利用率，它是采用离散分配的方式。而对换区只占用磁盘空间的小部分，用来存放从内存中换出的进程，对它的主要目标是提高进程换入和换出的速度，它采用连续分配的方式。

特点：

• 对换通常在内存紧张时发生。
• 交换技术主要用在不同进程（程序）间。
• 覆盖技术已经过时了，对换技术仍然存在。
• 对I/O速度要求非常高。

虚拟内存技术

连续存储分配

单一连续分配（单道程序）

内存中分为两个部分，一个部分为系统区，另一个部分为用户区。

单一：在用户区中，只能装一个程序。

连续：程序中有很多模块，这些模块挨着摆放到用户区的内存。

特点：

• 单用户单任务
• 内存的利用率极低（因为有内部碎片）：例如：QQ分配到用户区，QQ占了20M，而用户区有30M，此时还剩10M，这10M就形成了内部碎片，没有程序进行使用。（内部碎片：剩余的空间属于这个程序，但是它没有去使用）
• 通常采用绝对装入方式：事先修改逻辑地址为物理地址。

固定分区分配（多道程序）

第一阶段：用户区由操作系统分为大小相等的几个区域，此时内存的利用率会非常低。

第二阶段：用户区由操作系统根据使用情况分为大小不等的几个区域，提高了内存利用率。

特点：

• 每个分区只能装入一道程序。（单一连续分配是整个用户区只能装入一道程序）
• 分区大小很讲究，太小装不进程序，太大内存利用率低。
• 有内部碎片。
• 通常采用静态重定位装入方式。

分区说明表：只有设计到多道程序的内存分配才需要，单道程序不需要。操作系统运行时就已经被建立，是被固定的，它是一种操作系统的数据结构，通过查询分区说明表，操作系统就可以知道那一块是空的，以便于给程序分配内存。

• 分区号：每个分区的编号
• 区块大小：每个分区在内存中的大小
• 起始位置：每个分区在内存中的起始位置
• 状态：是否已经被使用

动态分区分配（多道程序）

解决固定分区分配分区大小很讲究的问题。

实现的方式为：随着程序进入内存进行分区，程序有多大，就分多大。当内存被分配完或内存被分配的最后一个空间不足以装入一个程序时，程序只能等待有适合大小的内存区被其他进程使用完后释放，如果释放的内存区比该程序大，则会产生外部碎片，但是当有其他与这个外部碎片相邻的内存区被释放时，可以进行内存的合并，但这种几率不是很多。

特点：

• 动态分区——分区说明表：随着进程的进入和退出，是不断的在变化的，这一点与固定分区不同。
• 内存的合并，减少外部碎片。
• 紧凑技术：利用动态重定位，将不相邻的外部碎片或空间内存进行合并。
• 动态分区算法：首次适应算法、最佳适应算法、最坏适应算法、临近适应算法

分配算法

• 首次适应算法

  按照空闲分区的地址进行排序，地址靠前的排在前面，地址靠后的排在后面。分配时，从头开始依次扫描，直到找到第一个合适的为止，将程序分配给它。

• 最佳适应算法

  按照空闲分区的大小进行排序，小的排在前面，大的排在后面。分配时，从头开始依次扫描，直到找到第一个合适的为止，将程序分配给它。这样程序总是能够找到满足要求、空闲分区较小的空闲分区分配给程序，避免了大材小用。

• 最坏适应算法

  与最佳适应算法相反

• 循环首次适应算法（临近适应算法）

  首次适应算法的概率，从上次分配空闲分区的位置开始查，这样就减少了查找已分配分区的时间，提高了查找的效率。

非连续存储分配

基本分页存储管理

引入分页的原因

在之前对多道程序进行内存分配时的两种方法都会产生碎片：固定分区分配会产生内部碎片，动态分区分配会产生外部碎片，虽然这些产生的碎片会很小，但是积少成多，总和也是一个不小的浪费。

处理这些碎片的方式可以使用之前的“紧凑”的方法，但是会付出很大的开销。

其实含有一种处理方法，就是将要装入的进程分成一页一页的页面，就可以将这些很小的页面转入到与之对应的碎片之中，这样就可以很好地把这些碎片利用起来。

之后，我们也可以想到，既然程序可以切块，那么内存也可以切块。所以我们可以这样做：将程序切成大小相等的若干个页面，并且将内存也切成与程序对应的大小相等的若干个块。

如何分页

通过之前讲解的为什么要分页我们已经知道，分页就是将内存和程序分为大小相等的块。一般是将内存分为每个4KB大小的块，也将程序切为每个4KB大小的块，这样就可以将程序中的某个4KB大小的块装入到内存中4KB大小的块中了。如果程序不能被4KB整除，程序的最后一块必然会小于4KB，这块程序装入到内存时，将会造成内存的浪费，但这个浪费相对于内存大小来说是微不足道的。同样，磁盘也想这样来分块。

这个被切成的块，在各个存储器中叫法不同：

• 在内存中切的一块叫做一个页框（物理块）。
• 程序中被切的一块叫做页面，页面装在页框中。
• 磁盘中被切的一块叫做磁盘块。

分的块的大小最好为2ⁿ。