操作系统课程笔记（孟庆昌第3版）

第一章 绪论

略

第二章 进程和线程

进程概念（PROCESS）

程序的顺序执行和并发执行

程序的两种执行方式：

• 顺序执行
  • 单道批处理系统的执行方式，也用于简单的单片机系统。
• 并发执行
  • 多道程序设计环境的执行方式，具有许多新的特征。
  • 并发执行能够提高资源的利用率。

顺序执行的特征：

• 顺序性
  • 处理机杨哥按照程序所规定的顺序执行。
• 封闭性
  • 程序一旦开执行，其计算结果不受外界的影响，只有本程序才能改变自己。
• 可在线性
  • 程序执行的结果与初始条件有关，而与执行时间和运行速度无关。只要程序初始条件相同，他的执行结果是相同的。

并发执行的特征：

• 失去封闭性
  • 共享资源，收其他程序的控制逻辑的影响。
• 程序与计算不再一一对应
  • 在并发执行过程中，一个共享程序可被多个用户作业调度，形成多个“计算”。
• 并发执行在执行期间互相制约。

进程概念

进程的定义

进程：一个具有一定独立功能的程序在一个数据集上的一次动态执行过程。

进程的根本属性是动态性和并发性。

进程与程序的区别

进程与程序的区别—–举例

Mary正在为女儿按食谱烘制生日蛋糕，她的儿子哭着跑进厨房说他被蜜蜂蛰了，Mary停下来，找出急救手册，为儿子处理蛰伤。

Mary——CPU
做蛋糕的食谱——程序
做蛋糕的各种原料——输入数据
阅读食谱，取来各种原料以及烘制蛋糕的一系列动作的总和—–进程
每个进程都有各自的程序

进程的基本特征

进程的特征：

• 动态性
  • 进程是程序的一次执行过程。
  • 进程具有一定的生命周期。
• 并发性
  • 多个进程实体同存与内存，且能在一段时间内同时运行。
• 调度性
  • 进程是系统中申请资源的单位，也是被调度的单位。
• 异步性
  • 进程可按各自独立的、不可预知的速度向前推进。
• 结构性
  • 进程组成：程序+数据+PCB
• 独立性
  • 各进程的地址空间相互独立。
  • 进程实体是一个能够独立运行、独立被分配资源和独立接受调度的基本单位。

进程的状态和组成

进程的状态及其转换

五种状态

进程的三种基本状态

进程的状态：

• 运行状态
  • 进程正在被执行，占用处理资源；处于此状态的进程数目小于等于CPU数目。
• 就绪状态
  • 进程已获得除处理机外的所需资源，等待分配处理机资源；只要分配CPU就可执行。
• 阻塞状态
  • 进程等待某个事件的发生（如I/O操作或进程同步），在该事件发生前，即使把处理机分配给进程，他也无法运行。
• 创建状态
  • 进程刚创建还不能运行，OS还没有把它加入到可执行进程组中，通常是还没有加载到主存中的新进程。
• 结束状态
  • OS从可执行进程组释放出的进程。
  • 进程结束，回收除PCB之外的其他资源，并让其他进程从PCB中手机有关信息。

进程的状态转换：

• 新建——》就绪（提交admit）
  • 接纳一个新进程，进入就绪状态。
• 就绪——》运行（分派dispath）
  • 从就绪进程表中选择一个进程，进入运行状态。
• 运行——》阻塞（事件等待event wait）
  • 进程要求的事件未出现而进入阻塞。
• 阻塞——》就绪（事件出现event occurs）
  • 进程等待的事件出现。
• 运行——》就绪（超时timeout）
  • 由于用完时间片或高级进程就绪等导致进程暂停运行。
• 运行——》退出（释放release）
  • 由于进程完成或失败而终止进程运行。
  • 分为正常和异常退出。

进程必须经过就绪状态而不能直接从阻塞状态转换到运行状态一，一个状态由运行状态转换成阻塞状态一般由运行进程主动提出的，一个进程由阻塞状态转换成就绪状态一般是由外部事件引起的。

练习↓

进程描述

进程映像

• 一个或一组被执行的程序。
• 与程序关联的局部变量、全局变量等。
• PCB：用于描述进程当前的状态、本身的特性、对资源的占用等。
• 栈：用来保存过程调用和相互传递参数的踪迹。

进程控制块是由OS维护的用来记录进程相关信息的一块内存。

进程控制块组成：

• 进程描述信息
  • 唯一标志对进程的一个标识符或数字。
• 处理器状态信息（现场保护区）
  • 包括处理器寄存器的内容
• 进程控制信息
  • 进程当前状态
  • 调度优先级
  • 通信信息
  • 资源占用信息
  • 进程实体信息
  • 族系关系
  • 其他信息

进程控制块作用：

• 每个进程由唯一的进程控制块。
• OS根据PCB对进程实施控制和管理。
• 进程的动态、并发特性是利用PCB表现出来的。
• PCB是进程存在的唯一标志。

进程队列

进程队列——PCB的组织方式

线性方式

优点：简单，容易实现。

缺点：

• 操作系统预先确定整个系统中同时存在的进程的最大数目，限定了系统同时存在的最大进程数目。
• 在执行CPU调度时，为了选择合理的进程投入运行，经常要对整个PCB表进行扫描，降低了调度效率。

链接方式

链表原理：将同一状态的进程的PCB放在同一个队列中，组成一个链表，多个状态对应多个不同的链表。

各状态的进程形成不同的链表。最常用的是unix系统采用的这种方式↓

索引方式

索引表：同意状态的进程归入一个index表（利用索引表记载不同状态进程的PCB地址），多个状态对应多个不同的index表。

索引表的起始地址放到硬件寄存器中，可快速得到某个索引表地址。

进程管理

进程图

进程图是描述进程族系关系的有向树。

某进程可以动态的创建新进程，前者称作父进程，后者称作子进程。

进程控制的功能

完成进程状态的转换。

原语：为完成某些特定功能而编制的一段系统程序。

也成为“原子操作”要么全完成，要么一个不做。

原语操作代码通常比较短，以尽快开放中断。

进程控制原语

进程阻塞：运行状态->阻塞状态
进程唤醒：阻塞状态->就绪状态
进程调度：就绪状态->运行状态
进程创建：新建进程置为就绪状态
进程撤消：进程终止（消亡）

1、进程创建

进程的创建原因：

• 系统初始化；
• 调度新的批作业；
• 交互式用户登录；
• 操作系统提供服务；
• 现有进程派生新进程。

当一个新进程增加到正在被管理的新进程行列中时，操作系统需要建立用于管理该进程的数据结构，并在主存中给他分配地址空间。

进程创建的过程：

• 申请一个空闲的PCB
• 为新进程分配资源
• 将新进程的PCB初始化
• 将新进程加到就绪队列中

unix系统中的fork（）

进程终止的过程：

• 找到指定进程的PCB
• 终止该进程的运行
• 回收该进程所占用的全部资源
• 终止其所有子孙进程，回收他们所占用的全部资源
• 将被终止进程的PCB从原来队列中摘走

unix系统中的终止原语exit（）

进程阻塞的过程：

• 立即停止当前进程的执行
• 现行进程的CPU现场保存
• 现行状态由“运行”改为“阻塞”转到阻塞队列
• 转到进程调度程序，选出运行进程

unix系统中的阻塞原语sleep（）

唤醒原语执行过程：

• 把阻塞进程从相应的阻塞队列中摘下。
• 将现行状态改为就绪状态，然后把该进程插入就绪队列中。
• 如果被唤醒的进程比当前运行进程的优先级更高，则设置重新调度标志。

unix系统中的wakeup（）

阻塞原语和唤醒原语是一对功能相反的原语，调用前者使自己进入睡眠，调用后者把别人唤醒。通常要成对使用，现有睡眠，后又唤醒。

#include  <stdio.h>
void main(int argc,char *argv[])
{
            int pid; 
            pid = fork( );
             if (pid < 0) {     /* error occurred */
                  fprintf(stderr, "Fork Failed");
                  exit(-1);
             }    
             else if (pid = = 0) {      /* child process */
                 execlp( "/bin/ls", "ls",NULL);
             }
                   else {   /* parent will wait for the child to complete */
                          wait(NULL);
                          printf( "Child Complete" );
                          exit(0);
                   }
}  

↑程序执行说明：

• 主进程在执行fork系统调用前使一个进程，执行fork系统调用后，系统中又增加了一个与原过程环境相同的子进程，他们执行程序中fork语句以后相同的程序。

• 父进程和子进程都有各自的变量pid，但是值不同，pid是fork嗲用后的返回值。父进程的pid大于0，子进程的pid为0.

• 这样父子进程执行同一程序，但执行不同的程序段。

• 父子进程并发执行，执行序列任意。

• 但由于父进程执行的第一条语句是wait(null),它表示父进程将挂起，直到该进程的一个子进程暂停或终止为止，所以，只能子进程执行 execlp语句。

建立子进程的地址空间有两种方式：

• 父进程复制自己的地址空间给子进程
  • 地址空间副本，包括正文字段、数据段……
  • 父进程和子进程通信容易
• 父进程把程序装入子进程的地址空间

线程（THREAD）

线程的引入：

• 拥有资源的独立单元——进程
• 被处理机独立调度和分配的单元——线程

线程概念

现代操作系统中，进程只作为资源拥有者，而调度和运行的属性赋予新的实体——线程。

线程是进程中实施调度和分派CPU的基本单元。

进程把相关资源集中在一起，有存放程序正文和数据以及其他资源的地址空间。

线程基本上不拥有系统资源，只拥有运行中必不可少的一点资源：

• 程序计数器：记录接着要执行哪一条指令
• 寄存器：保存线程当前的工作变量
• 堆栈：记录执行历史

线程必须在某个进程内执行。

一个进程可以包含一个或多个线程。

线程的组成：每个线程都有一个thread结构，即线程控制块，用于保存自己私有的信息，主要由以下几部分组成。↓

线程状态：

• 新建状态
• 就绪状态
• 运行状态
• 阻塞状态
• 终止状态

线程的管理：

• 线程创建
  • 一个线程通过调用线程库中的thread_create创建新线程。
• 线程终止
  • 调用线程库中的thread_exit种植自身。
• 线程等待
  • 调用线程库中的thread_wait等待指定线程终止，调用者阻塞。
• 线程让权
  • 一个线程调用thread_tield自愿放弃CPU，让给另外的线程运行。

线程和进程的关系：

• 一个进程可以有多个线程；一个线程只能在一个进程的地址空间内活动。
• 资源分配给进程，同一进程的所有线程共享进程的所有资源。
• 处理机分配给线程。
• 线程在执行过程中需要协作同步。不同进程的线程间要利用小心通信的办法实现同步。

在用户空间实现线程

用户应用程序建立线程，并负责调度和管理这些线程。OS内核并不知道线程的存在。任何应用程序可以通过使用线程库设计多线程程序。

线程库是用于用户级线程管理的一个例程包，它包含用户创建和销毁线程的代码、在线程间传递消息和数据的代码、调度线程执行的代码以及保存和恢复线程上下文的代码。

OS内核负责所有的线程的创建、调度和管理。应用程序部分没有进行线程管理的代码，只有一个到内核线程设施的应用程序编程接口。

组合方式：

• 一对一模型
  • 
• 多对一模型
  • 
• 多对多模型
  • 

进程的同步和通信

进程的同步和互斥

进程间的相互关系分为3种：

• 互斥
• 同步
• 通信

同步

同步进程通过共享资源来协调活动，在执行时间次序上有一定约束。

同步指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于阻塞状态，获得消息后被唤醒进入就绪态。

互斥

在逻辑上这两个进程本来完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。

他们运行不具有时间次序的特征。

对于互斥进程，单独执行正确，但不能交叉执行，只要互斥进行，先后没有关系；

对同步进程，单独执行会产生错误，必须相互配合，有先后次序关系。

临界资源与临界区

例：2个窗口同时出售同一车次的火车票，若同时修改票数R，则会出现丢失修改的现象。

为避免数据丢失，必须找到某种途径来阻止一个以上的进程同时使用这种资源，即多进程共享这种资源时，必须互斥地使用。

票数R是一种临界资源，对R操作的售票程序是临界区。

临界资源：

• 一次仅允许一个进程使用的资源称为临界资源。
• 宿舍电话、打印机……

临界区：

• 在每个进程中访问临界资源的那段程序叫做临界区。
• 为保证进程互斥的使用了临界资源，一次只允许一个进程进入临界区。

进程互斥进入临界区的模式：

• 进入前要申请
• 获准后方可进入
• 执行后要退出

临界区进入准则：

• 如果若干进程要求进入空闲的临界区，一次仅允许一个进程进入。（空闲则入）
• 任何时候，处于临界区内的进程不可多于一个。（忙则等待）
• 进入临界区的进程要在有限时间内退出。（有限等待）
• 如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。（让权等待）
• 依据准则设计入口区、出口区

互斥实现方式

硬件方法：

• 禁止中断
• 专用机器指令

软件方法：

• 置锁变量法
• 信号量法

用硬件方法解决进程互斥——禁止中断

中断禁止缺点：一旦某个进程关闭中断后，如果不在开放中断，系统可能因此而终止。

用硬件方法解决进程互斥——专用机器指令

TSL指令：Test and Set Lock

软件方法——置锁变量法

为每类临界区设置一把锁，该锁有打开和关闭两状态

进程执行临界区程序的操作步骤：

• 关索
• 执行临界区程序
• 开锁

软件方法——信号量法

对信号量的操作有以下限制：

• 初始化为一个非负值；
• 只能由P和V两个操作来访问。

P操作表示测试，也称wait或DOWN操作。

V操作表示增加，也称signal或UP操作。

信号量

信号量的实现有三种：

• 整形信号量——解决“忙等”问题
• 结构型信号量——解决“忙等”问题
• 二值信号量——结构型信号量的特殊情况

结构性信号量：

结构型信号量一般是由两个成员组成的数据结构。

• 每个信号量s含有一个整数值s.value（计数）
• 还有一个进程等待队列s.list，其中是阻塞在该信号量的各个进程的表示（PCB）

P操作定义（申请资源）

V操作定义（释放资源）

信号量S的物理意义：

• s>0，表示该类可用资源的数量；
• s=0，表示没有该类可用资源；
• s<=0，表示没有该类资源可供分配，请求资源的进程将被阻塞在相应的信号量的等待队列中。s的绝对值 = 该信号量上等待的进程数。

P、V操作的物理意义：

• 没执行一次P操作，就意味着请求分配一个单位的该类资源给执行P操作的进程，S：=S-1。
  • 若无可用资源，进程阻塞等待。
• 每执行一次V操作，意味着进程释放一个单位的该类可用资源，S:=S+1。
  • 若有阻塞等待的进程，则唤醒他，转入就绪队列。

信号量的一般应用

用信号量实现进程互斥

利用信号量实现进程互斥的模式：

为临界资源设置一个互斥信号量mutex，初值为1；在每个进程中将临界区代码置于P和V原语之间。

用信号量实现互斥的准则：

• 互斥信号量mutex的初值一般设为1
  • 它相当于一把锁，最多只允许一个进程进入临界区。
• 必须成对使用PV原语，不能重复或遗漏
  • 遗漏P则不能保证互斥访问，遗漏V则不能在使用临界区资源之后将其释放。
• PV次序不能颠倒
  • 先P进入临界区，后V退出临界区。

用信号量实现进程简单同步

供者和用者的同步关系

• 缓冲区空，则供者把信息传入缓冲区，此时用者不能操作（阻塞）
• 缓冲区满，则用者从缓冲区取数处理，此时供者不能操作（阻塞）

供者和用者要交换两个消息：缓冲区空和缓冲区满的状态。

设置两个信号量：

• S1表示缓冲区是否空(1表示空，0表示不空)
• S2表示缓冲区是否满（1表示满，0表示不满）
• 规定S1和S2的初值分别为1和0

例↓

用PV操作实现同步应注意三点：

• 分析进程间的制约关系，确定信号量种类和个数，说明信号量的含义。
• 确定信号量初值
  • 信号量的初值与相应资源的数量有关，也与PV操作在程序中出现的位置有关。
• 同一信号量的PV操作要“成对”出现
  • 通常出现在不同的进程代码中

经典进程同步问题

生产者-消费者问题

如果一个进程能产生并释放资源，则该进程称作生产者；如果一个进程单纯消耗资源，则该进程称作消费者。

问题表述如下：一组生产者进程和一组消费者进程（设每组有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、消息等）送入缓冲区，消费者进程从中取出产品。假定缓冲区共有N个，把它们设想成一个环形缓冲池。

为了使这两类进程协调工作，防止盲目的生产和消费，他们应满足如下同步条件：

• 任意时间所有生产者存放产品的单元数不能超过缓冲区的总容量N。
• 所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。
• 任何时刻只能有一个进程可对共享缓冲区进行操作。

为了使两类进程实现同步操作，设置三个信号量：

• empty：表示可供使用的空缓冲区数，初值为N。
• full：表示方有产品的缓冲区数，初值为0.
• mutex：互斥信号量，初值为1，保证任何时候只有一个进程使用缓冲区。

读者-写者问题

第一种实现方式：读者优先写者

设置两个信号量、一个计数器：

• wmutex：写互斥信号量，用于保证一个写者与其他读者/写者互斥的访问共享资源，初值为1.
• readcount：读计数器，用于统计数据库中读者数量，使整型变量，初值为0.
• rmutex：互斥信号量，用于读者互斥的访问readcout，初值为1.

第二种实现方式：读者写者俺到达顺序访问数据库

设置三个信号量、一个计数器：

• wmutex：写互斥信号量，用于保证一个写者与其他读者/写者互斥的访问共享资源，初值为1.
• readcount：读计数器，用于统计数据库中读者数量，是整型变量，初值为0。
• rmutex：读互斥信号量，用于读者互斥地访问readcount，初值为1。
• w：互斥信号量，用于控制进程按照进程申请顺序访问，初值为1。

第三种实现方式：写者优先读者

当写者和读者同时等待时，后续写者到达时可以插队到等待的读者之前，只要等待队列中有写者，不管何时到达，都优先于读者被唤醒。

假定一个阅览室可容纳一百人，读者进入和离开阅览室时都必须在阅览室门口的登记表上做标识（进入时登记，离开时去掉登记），而且每次只允许一人登记或去掉登记。
应设置几类进程？
用P、V操作实现同步算法。

答：

每个读者对应一个进程，他们是同类进程。每个读者的动作都包括：

• 申请阅览室的空位；
• 入室前查表、登记；
• 进入室内，阅读书籍；
• 出室时删除登记；
• 阅览室多出一个空位。

信号量：

• S——座位情况，初值100；
• mutex——互斥使用登记表，初值1.

哲学家进餐问题

问题描述：

• 五位哲学家围坐在一张圆桌旁进餐，每人面前有一只碗，各碗之间分别有一根筷子。
• 哲学家先思考，感到饥饿时便试图占用其左右最靠近他的筷子，他可能一根也拿不到。当拿到两根时就进餐，餐毕，放回筷子，继续思考。

答：

简单的解决办法：五根筷子对应信号量数组chopstick[5]，初值为1。第i个哲学家的进餐过程可描述为：

While(true){
		think;
		P(chopstick[i]);
		P(chopstick[(i+1)mod5]);
		eat;
		V(chopstick[i]);
		V(chopstick[(i+1)mod5]);  }

上述算法可保证相邻的两个哲学家不能同时进餐。

但存在死锁隐患：如果五个哲学家同时拿起各自左边的筷子，又试图拿右边的，则产生死锁。

解决死锁的办法：

• 最多只允许4个哲学家同时拿筷子，从而保证有一人能够进餐。
• 仅当某哲学家左右两边的筷子都可用时，才允许他拿筷子。
• 将哲学家编号，要求奇数号的哲学家先拿左边筷子，偶数号哲学家先拿右边筷子。

用第一种方法解决死锁：

• 五根筷子对应信号量数组chopstick[5]，初值为1；
• 将允许同时拿筷子准备进餐的哲学家数量看作一种资源，定义成信号量count，初值为4；
• 哲学家进餐前先执行P(count)，进餐后执行V(count)。

第二种方法解决死锁：

• 必须让哲学家拿起2根筷子的操作是不可分割的，如果不能拿起2根筷子则阻塞等待，直到确定能拿起2根筷子则结束等待。

设信号量和状态变量：

• 对每个哲学家设置信号量S[i]，代表是否能够拿起两根筷子，即是否具备进餐条件，初值都是0。
• 对每个哲学家设一个整型变量state，用于存储状态，则5个哲学家对应一个整型数组state[i]。
  • 每个哲学家都有三种状态：thinking、hungry、eating。
  • 如果当前哲学家是hungry，左邻、右邻都不在eating状态，则当前哲学家i可以转入eating状态，即进行V(S[i])操作。
• 对哲学家状态的测试和改变需要互斥操作，用mutex控制。

c语言描述：

#define  N    5
#define  LEFT  (i-1)%N
#define  RIGHT  (i+1)%N
#define  THINKING  0
#define  HUNGRY   1
#define  EATING   2
  typedef struct{                /* 定义结构型信号量 */
           int value;
           struct PCB *list;
   }semaphore;
   int state[N];
   semaphore mutex=1;     /* 互斥进入临界区  */
   semaphore s[N]=0;        /* 每位哲学家一个信号量，代表是否具备进餐的条件，信号量初值都是0，表示最初都不具备进餐条件，需要测试完才知道是否具备条件 */

打瞌睡的理发师问题

问题描述：

• 理发店有一名理发师、一把理发椅、几把等待座椅。
• 如果没有顾客，理发师就打盹。顾客到来，唤醒理发师。如果顾客到来时理发师正在理发，则顾客坐在椅子上等待；如果座满了，直接离开。
• 用P、V操作协调理发师和顾客的同步行为。

解决办法：

理发师和顾客各对应一类进程。有多种解题思路。

无论哪一种，首先都要弄清楚理发师的工作流程和顾客的行为流程，再根据需求设信号量，同步二者的行为。

第一种思路：

• 设三个信号量，一个计数器：

  • customers：用来记录等候理发的顾客数，初值为0。

  • barbers：用来记录等候顾客的理发师数，初值为0。

  • waiting：整型计数器，表示等候理发的顾客数，初值为0。

  • waiting是customers的副本，但不是信号量，可以在程序

    中对它做增减操作。

  • mutex：用于控制对waiting的互斥操作，初值为1。

  • ```c++
    #define CHAIRS 5
    typedef struct{

         int value;
         struct PCB *list;
    

    } semaphore;

    semaphore customers=0;
    semaphore barbers=0;
    semaphore mutex=1;
    int waiting=0;

      - ![40](/操作系统课程笔记/40.jpg) 
    
    第二种思路：
    
    - 将理发椅（1个bchair）与等待椅（n个wchair）分开看作两种不同的资源，顾客分别申请使用。
    - ![41](/操作系统课程笔记/41.jpg) 
    
    解题：
    
    - 考虑等待的顾客数（坐在凳子上的顾客数），设置一个整型变量waiting，初值为0。当一个顾客到达时waiting加1，当一个顾客开始理发时waiting减1。
    
    - 考虑对waiting的互斥操作，设互斥信号量mutex，初值为1。
    
    - 考虑空凳子数量，设信号量wchair，初值为5。
    
    - 考虑理发椅的数量，设信号量bchair，初值是1。
    
    - 考虑顾客和理发师的同步操作，设ready和finish两个信号量，前者表示顾客是否准备好，后者表示理发师是否完成理发，初值均为0。
    
    - ```c
      typedef struct{
               int value;
               struct PCB *list;
      } semaphore;
      
      int waiting=0;
      semaphore mutex=1;
      semaphore bchair=1;
      semaphore wchair=5;
      semaphore ready=finish=0;
      

5. 

管程

管程的定义

一个管程定义了一个数据结构和一组操作，并发进程可以在这个数据结构上执行这组操作，这组操作能使进程同步和改变管程中的数据。

一个管程由四部分组成：

• 管程名称
• 局部于管程的共享数据的说明
• 对数据进行操作的一组过程
• 对该共享数据赋初值的语句

管程有三个特性：

• 管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问
• 进程要想进入管程，必须调用管程内的某个过程。
• 一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。即管程能有效地实现互斥。

管程的特征：

• 模块化：一个管程是一个基本程序单位，可以单独编译；
• 抽象数据类型：管程是一种特殊的数据类型，不仅有数据，还有对数据进行操作的代码；
• 信息隐藏：管程是半透明的，管程内部的过程（函数）实现了某些功能，这些功能如何实现，外部不可见；
• 封装性：管程中定义的对共享变量的所有操作都局限在管程中，外部只能通过调用管程的某些函数来间接访问这些变量。

管程的缺点：

• 要求编译程序必须能识别管程，并用某种方式实现互斥。
• 编译程序如何知道哪些过程属于管程内部，哪些不属于管程，实现有难度。
• C等多数编程语言都不支持管程。

进程通信

高级通信：能够传送任意数量的数据。

主要方式：

• 共享存储区
• 消息传递
• 管道文件

共享存储器方式：

• 共享存储器方式是在内存中分配一片空间作为共享存储区。需要进行通信的各个进程把共享存储区附加到自己的地址空间中，然后就对可以对共享区中的数据进行读或写。如果不需要，可以取消。
• 需要使用同步互斥工具（如PV操作）对共享空间的读写进行控制。

消息传递方式：

• 消息传递方式以消息（Message）为单位在进程间进行数据交换。
• 进程通过操作系统提供的发送消息（send）和接收消息（receive）两个原语进行数据交换。
• 用消息传递方式解决生产者-消费者问题。

消息传递方式途径：

• 直接通信方式
  • 发送进程直接将消息挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中得到消息。
• 间接通信方式
  • 发送进程将消息送到称做信箱的中间设施上，接收进程从信箱中取得消息，也称为信箱通信方式。
• 广泛应用于计算机网络中，相应的通信系统称为电子邮件系统。

管道文件方式（PIPE文件）：

• 管道文件也称管道线，它是连接两个命令的一个打开文件。一个命令向该文件中写入数据，称做写者；另一个命令从该文件中读出数据，称作读者。
  • $ cat file1 | more
  • 分屏显示文件file1的内容。
• 由系统自动处理二者间的同步、调度和缓冲。
• 为了协调双方的通信，管道机制必须提供以下三方面的能力：同步、互斥、确定对方的存在。

本章小结：

• (1)进程、程序在并发环境的执行过程；
• (2)进程的基本特征——并发性、动态性；
• (3)进程的基本状态：就绪、运行、阻塞；
• (4)进程与程序的区别；
• (5)进程存在的唯一标志：进程控制块PCB；
• (6)PCB的组织方式：线性表、链接表、索引表；
• (7)进程控制原语：创建、阻塞、终止、唤醒；
• (8)进程：资源分配单位；线程：调度基本单位；
• (9)线程实现的方式：用户空间、内核空间、组合；
• (10)进程的同步和互斥；
• (11) 临界资源与临界区，信号量和P、V操作；
• (12)经典进程同步问题：生产者-消费者、读者-写者、哲学家进餐、打瞌睡的理发师；
• (13)高级同步机制——管程：自动互斥、条件变量+原语实现同步；
• (14)高级进程通信方式：共享内存区、消息传递、管道文件。

第三章 死锁

资源

计算机系统中有很多一次只能由一个进程使用的资源：

• 硬件资源：硬件设备
• 软件资源：一组信息（加锁记录、信号量、系统表格等）
• 临界区、临界资源

资源使用模式

1、申请

2、使用

3、释放

申请数量<=可用资源的总量，否则阻塞。

资源分类

按占用方式分类：

• 可剥夺资源：
  • 其他进程可以从拥有资源的进程那里剥夺为及所用，且不会产生不良影响。
  • 例如，内存就是可剥夺资源
• 不可剥夺资源：死锁和不可剥夺资源有关
  • 不能从当前占有他的进程那里强行抢占的资源，必须由拥有者自动释放，否则会引起相关计算的失效。
  • 例如进程A录刻光盘。

死锁概念

死锁定义：

• 所谓死锁，是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。（系统中多个进程无限地等待永远不会发生的状态）

产生死锁的根本原因：

• 资源有限
• 操作不当
  • 程序编写问题
  • 进程推进顺序不对

当计算机系统同时具备下面4个必要条件时，会发生死锁：

• 互斥条件
• 占有且等待条件（请求并保持）
• 不可抢占条件（不可剥夺）
• 循环等待条件（环路等待）
• 只要由一个必要条件不满足，则死锁就可以排除。

死锁的预防——静态策略：

• 破坏死锁的四个必要条件之一。

死锁的避免——动态策略：

• 利用某些协议避免死锁，保证系统不会进入死锁状态。

检测恢复：

• 允许系统进入死锁状态，然后设法发现并恢复它。

综合方式

忽略（鸵鸟策略）：

• 发现死锁较困难，处理死锁代价高，所以忽略。

死锁的预防

破坏互斥条件：

• 有些资源本身要求必须互斥访问，这是资源的固有属性，所以，用否定互斥条件的办法不能预防死锁。

破坏占有且等待条件：

• 一种办法时“空手”申请资源策略：不占有资源的时候，才能申请。
• 一种办法时预分资源策略：静态分配（执行之前申请到全部资源）。
  • 缺点：
    • 很多情况下，进程执行前无法知道所需全部资源；
    2. 资源利用率降低；
    3. 降低了进程的并发性；
    4. 可能出现饥饿现象：无法得到众多进程争用的“紧俏”资源。

破坏不可抢占条件：

• 隐式抢占方式（被抢）：
  • 如果一个进程占有某些资源，它还要申请被别的进程占有的资源，该进程就一定处于等待状态，则进程当前所占有的全部资源可被抢占。
• 抢占等待者的资源（去抢）
  • 进程申请资源，如果没有可用，可以从等待进程那里抢占资源。
• 这些办法常用于资源状态易于保留和恢复的环境中，如CPU寄存器、内存，但不能用于打印机、磁带机等。

破坏循环等待条件：

• 一种方法是实行资源有序分配策略。
  • 设R={r1, r2, …, rm}表示一组资源，定义一对一的函数F：R→N，式中N是一组自然数。
  • 所有进程对资源的申请严格按照序号递增的次序进行。
  • 例如： F（磁带机）= 1，F（磁盘机）= 5，F（打印机）= 12。
• 另一种方法：先弃大，再取小。也就是说
  • 资源利用率和系统吞吐量都有所提高，但也存在两个缺点：
    • 限制了进程对资源的请求，同时给系统中所有资源合理编号也是件难事，并会增加系统开销；
    • 为了遵循按编号申请的次序，暂不使用的资源也需要提前申请，从而增加了进程对资源的占用时间。

死锁的避免

静态策略：死锁预防——破坏产生死锁的必要条件；静态策略的缺点是降低资源利用率和减少系统吞吐量。

动态策略：不限制进程有关申请资源的命令，而是对进程所发出的每个申请资源命令加以检查，根据检查结果决定是否进行资源分配。

关键是确定资源分配的安全性！

安全状态

进程可以按安全序列的顺序一个接一个的完成，即便某个进程Pi因所需的资源量超过系统当前所剩余的资源总量，但可以等待前面所有进程Pj(j<i)运行完毕，释放所占有的资源，从而满足Pi的需求。
存在安全序列，系统处于安全状态，不会死锁。
找不到安全序列，系统处于不安全状态。
系统进入不安全状态，并不意味着此时死锁了。
死锁是不安全状态的特例。

安全状态举例：

• T0时刻系统资源分配情况如下：
  • 系统中共有10台磁带机；
  • 三个进程P1,P2,P3，占有3台、2台、2台；
  • 最大需求是9台、4台和7台。
• 问T0时刻系统是否处于安全状态？
• 思路：如果能找到安全序列，系统就安全。

① 死锁状态是不安全状态。
② 如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。
③ 如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。

资源分配图

资源分配图的构成：

• 该图由结对组成： G = (V, E)。式中，V是顶点的集合，E是边的集合。顶点集合可分为两部分：P={p1, p2, …, pn}，它由系统中所有活动进程组成；R={r1, r2, …, rm}，它由系统中全部资源类型组成。
• 有向边pi →rj称为申请边，而有向边rj →pi称为赋给边。
• 在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。

环路与死锁：

• 如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。
• 如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。

死锁的避免算法：

• 单体资源类：
  • 系统中的资源都只有一个，可用资源分配图算法。
• 多体资源类
  • 系统中的资源都有多个，可用银行家算法。

资源分配图算法

算法描述：设进程Pi申请资源rj，仅当申请边pi——>rj转换为赋给边且不会导致资源分配图中出现环路时，申请才可实现。

银行家算法

银行家算法的设计思想是：当用户申请一组资源时，系统必须做出判断；如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该申请暂不予满足。

银行家算法的优点：

• 允许存在死锁必要条件的前三个，即互斥条件、占有且申请条件、不可抢占条件；
• 限制条件少了，资源利用率提高了。

银行家算法的缺点：

• 要求进程数保持不变，在多道程序系统中难以做到；
• 算法仅保证所有进程在有限的时间内得到满足，不一定能够快速响应(如实时进程)；
• 要寻找安全序列，增加了系统开销。

死锁的检测和恢复

死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外力破坏死锁发生的必要条件，从而使并发进程从死锁状态中解脱出来。

算法：

• 对单体资源类的死锁检测——等待图
• 对多体资源类的死锁检测——检测算法（与安全性算法类似）

对单体资源类的死锁检测

等待图：它是从资源分配图中去掉表示资源类的节点，且把相应边折叠在一起得到的。
检测依据：当且仅当等待图中有环路，系统存在死锁。

对多提资源类的死锁检测

检测算法采用若干随时间变化的数据结构，与银行家算法中所用的结构相似：

• ① Available是一个长度为m的向量

• ② Allocation是一个n×m的矩阵

• ③ Request是一个n×m的矩阵

检测算法只是简单地调查尚待完成的各个进程所有可能的分配序列。

死锁检测的时机

取决两个因素：

• 死锁出现的频繁程度
• 有多少个进程受死锁的影响

检测时机：

• 有资源请求时就检测
• 定时检测
• CPU使用率低于规定下限值时，进行检测
  • 死锁涉及较多进程时，CPU经常闲置

从死锁中恢复

三种恢复方式：

• 通过抢占资源实现恢复
• 通过回退执行实现恢复
• 通过杀掉进程实现恢复

通过抢占资源实现恢复：

• 挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程，直至死锁环路被打破。
• 注意：要防止被挂起的进程长时间得不到资源

通过回退执行实现恢复：

• 让一个或多个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。
• 注意：要求系统保持进程的历史信息，设置还原点。

通过杀掉进程实现恢复：

• 杀掉进程，回收资源：
  • 终止所有的死锁进程。
  • 一次终止一个进程，直至消除死锁环路。
• 终止进程的选择依据：
  • 进程优先级；
  • 已运行时间，剩余时间；
  • 使用资源及资源类型；
  • 还需要多少资源？
  • 进程是交互式的，还是批处理程序？

“饥饿”状态

在某些策略下，系统会出现这样一种情况：在可以预计的时间内，某个或某些进程永远得不到完成工作的机会，因为它们所需的资源总是被别的进程占有或抢占。这种状况称做“饥饿”或者“饿死”（Starvation）。

饥饿不同于死锁：

• 死锁的进程必定处于阻塞状态，而饥饿进程不一定被阻塞，可以在就绪状态；
• 可以利用FCFS资源分配策略来避免饥饿。

处理死锁的综合方式

针对不同资源类采用不同策略：

• 可对换空间：硬盘上用于对换进程的存储块
  • 采用预先一次性分配，破坏占有且等待条件。
• 进程资源：磁带机、文件
  • 进程预先声明需要的数量，采用死锁避免。
• 内存：
  • 利用抢占内存的方式进行死锁预防。
• 内部资源：如I/O通道
  • 通过资源编号预防死锁。

第四章 调度

调度(Scheduling)是多道程序操作系统的基础，是操作系统设计的核心问题。

调度的概念

调度的基本概念

处理器调度：

• 对处理器进行分配，就是从就绪队列中，按照一定的算法（公平、高效）选择一个进程并将处理器分配给它运行，以实现进程并发地执行。

调度的层次

一个作业从提交开始直到完成，一般要经历三级调度：

• 高级调度（作业调度）
• 中级调度（内存调度、进程挂起与对换）
• 低级调度（进程调度）

高级调度（作业调度）：

• 主要任务：按照一定的原则从外存上处于后备状态的作业中挑选一个或多个，给它们分配内存、外设等必要的资源，并建立相应的进程，使它们获得竞争处理器的权利。
• 多道批处理系统中大多配有作业调度，其他系统通常不需要作业调度。
• 调度程序选择不同的作业进行合理搭配，使系统中各部分资源得到均衡使用，提高并行性。
• 作业调度的执行频率较低，通常为几分钟一次。

中级调度（内存调度）：

• 主要任务：在内存使用紧张时，将那些暂时不能运行的进程，调至外存等待，把此时的进程称为挂起状态（suspend）。将当前所需部分换入到内存。
• 提高了内存的利用率和系统吞吐量。

低级调度（进程调度）：

• 主要任务：根据一定的算法，将CPU分派给就绪队列中的一个进程，执行低级调度功能的程序称做进程调度程序。
• 进程调度是操作系统中最基本的一种调度。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。

三级调度的联系

作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起。
作业调度次数少，中级调度次数略少，进程调度频率高。
进程调度是最基本的，不可或缺。

按操作系统的类型分类：

• 批处理调度
• 交互式系统调度
• 实时调度
• 多处理机调度

进程调度时机、切换与过程

进程调度的试时机

调度时机（引起进程调度的原因）：

• （1）当前进程运行结束。
• （2）当前运行进程因某种原因（I/O请求、P操作、阻塞原语等），从运行状态进入阻塞状态。
• （3）执行完系统调用等系统程序后返回用户进程，这时可以看做系统进程执行完毕，从而可以调度一个新的用户进程。
• （4）在采用抢占调度方式的系统中，一个更高优先级的进程要求使用cpu，则使当前运行进程进入就绪队列。
• （5）分时系统中，分配给该进程的时间片用完。

进程调度过程：

• （1）保存运行进程的现场信息。
• （2）在就绪队列中选择一个最有资格运行的进程，使其占用cpu。
• （3）为新选中的进程恢复现场。

进程调度的方式

进程调度方式：

• 指当一个进程正在处理器上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先权更高的进程进入就绪队列，此时应如何分配处理器。

通常由两种进程调度方式：

• 非抢占方式
  • 一旦把CPU分配给一个进程，该进程就会保持CPU直到完成或转到等待状态。
  • 优点是实现简单，系统开销小。
  • 适用于大多数的批处理系统，但不能用于分时系统和大多数实时系统。
• 抢占方式
  • 当一个进程正在 CPU上执行时，若有某个更为重要或紧迫的进程需要使用CPU，则立即暂停正在执行的进程，让出CPU。
  • 抢占必须遵循一定的原则，主要有优先权原则、短进程优先原则、时间片原则。
  • 能防止一个进程长期占用处理机，调度更合理。但开销较大。

调度的基本准则

面向系统准则：

• CPU利用率
• 系统吞吐量：
  • 单位时间内CPU完成作业的数量。长作业消耗处理器的时间长，会降低系统的吞吐量。相反，短作业会提高系统吞吐量。

面向用户的准则：

• 周转时间

  • Ti= tci – tsi
    tsi表示作业i的提交时间
    tci表示作业i的完成时间

    • 平均周转时间
      • 
    • 带权周转时间
      • W=T/R
        T：周转时间
        R：CPU运行时间（在本进程即运行时间）
    • 平均带权周转时间
      • 

  • 周转时间是指作业从提交到作业完成所经历的时间，包括作业等待、在就绪队列中排队、在处理器上运行以及输入/输出操作所花费时间的总和。

• 就绪等待时间

  • 每个作业在就绪队列中的等待时间（等待处理器的时间之和），等待时间越长，用户满意度越低。
  • 处理器调度算法实际上并不影响作业执行或输入\输出操作的时间，只影响作业在就绪队列中等待所花的时间。
  • 衡量一个调度算法优劣常常只简单地考察等待时间。

• 响应时间

  • 用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间。
  • 在交互式系统中，周转时间不是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。
  • 从用户的角度看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。

周转时间=等待时间+完成时间在图上的刻度

周转时间=完成时间-到达时间

典型调度算法

先来先服务法FCFS（非抢占式）

实现思想：排队买票（非抢占式）

• 每次从就绪队列中选择一个最先进入该队列的进程，把CPU分给它，令其运行。该进程一直运行下去，直至完成或由于某些原因而阻塞，才放弃CPU。

FCFS的特点：

• 非抢占式
• 简单，易于理解，容易实现。效率低。
• 有利于长作业（进程）,不利于短作业（进程），
• 有利于CPU繁忙型作业（进程），不利于I/O繁忙型作业（进程）。
• 适用于作业调度、进程调度。通常不单独使用，与其他算法结合起来使用。

短作业优先法SJF（非抢占式）

所谓长短是指作业（进程）要求运行时间的多少。

实现思想：

• 当分配CPU时，选择所需处理时间最短的进程。短进程将越过长进程，跳到队列头。一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。

练习↓

最短剩余时间优先法SRTF（抢占式）

实现思想：

• 当新进程进入就绪队列时，如果它需要的运行时间比当前运行的进程所需的剩余时间还短，则执行切换，当前运行进程被剥夺CPU的控制权，调度新进程运行。

SRTF特点：

• 优点：
  • 保证新的短作业一进入系统就能很快得到服务，平均等待时间短。
• 缺点：
  • 为保存进程断点现场，统计进程剩余时间增加了系统开销。
  • 不利于长作业。
• 适用于作业调度和进程调度。作业调度用的少，进程调度用的多。

高响应比优先法HRRF（非抢占式）

用户给出估计服务时间，为每个作业计算一个响应比：

• 
  • w是作业等待处理机所用的时间
  • s是作业要求的服务时间
• 调度思想：在调度作业时，挑选响应比最高的作业运行。
• 若作业等待时间相同，则要求服务的时间越短，其响应比越高，有利于短作业。
• 当要求服务的时间相同时，作业的响应比由其等待时间决定，等待时间越长，响应比越高，因而它实现的是先来先服务。

HRRF特点：

• 非抢占式
• 优点
  • 是对FCFS和SJF调度算法的综合平衡，同时考虑每个作业的等待时间和估计需要的运行时间。
• 缺点
  • 调度前需要计算作业的响应比，增加系统开销。
• 适用于作业调度和进程调度。作业调度用的多。

优先级法HPF（抢占、非抢占）

实现思想：

• 优先级调度算法是从就绪队列中选出优先级最高的进程，让它在CPU上运行。

确定优先级有静态优先级和动态优先级两种：

• 静态优先级：
  • 静态优先级是在创建进程时就确定下来的，而且在进程的整个运行期间保持不变。
    • 进程类型（系统进程优先级较高）
    • 对资源的需求（对CPU和内存需求较少的进程，优先级较高）
    • 用户要求（紧迫程度和付费多少）
• 动态优先级：
  • 动态优先级随进程的推进而不断改变。
    • 在就绪队列中，随着等待时间延长，进程的优先级提高。（解决饥饿问题）
    • 进程每执行一个时间片，就降低其优先级。（实现负反馈，防止长期占用CPU）

在进程运行过程中，若就绪队列中出现优先级较高的进程可采用两种处理方法：

• 非抢占式优先级法
• 抢占式优先级法

轮转法RR（抢占式）

实现思想：

• 将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。
• 在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
• 进程可以未使用完一个时间片，就让出cpu（如阻塞）。

时间片转轮法主要用于分时系统中的进程调度。时间片是一个小的时间单位，通常时10-100ms。

例题↓

进程周转时间依赖于时间片的大小。

时间片长度变化的影响：

• 过长－>退化为FCFS算法，进程在一个时间片内都执行完。
• 过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。
• 使单个时间片内多数进程能够完成它们的运行工作，平均周转时间会得到改进。

时间片的大小直接影响轮转法的性能，对系统性能影响也很大。

时间片的长短由以下四个因素决定：

• 系统的响应时间
  • 在进程数目一定时，时间片的长短直接正比于系统对响应时间的要求。
• 就绪队列中的进程数目
  • 当系统要求的响应时间一定时，时间片的大小反比于就绪队列中的进程数目。
• 进程的转换时间
  • 若执行进程调度时的转换时间为t，时间片为q，为保证系统开销不大于某个标准，应使比值t/q不大于某一数值，如1/10。
• CPU运行指令速度
  • CPU运行速度快，则时间片可以短些；反之，长些。

多级队列法MQ（抢占式）

实现思想：

• 调度算法把就绪队列划分成几个单独的队列，一般根据进程的某些特性，如占用内存大小、进程优先级和进程类型，永久性地把各个进程分别链入不同的队列中。
• 每个队列都有自己的调度算法。比如前台进程队列可采用轮转法，后台进程队列可采用先来先服务法。
• 队列之间通常采用固定优先级的抢占式调度。

队列之间，采用固定优先级的抢占式调度。

• 

多级反馈队列法MFQ（抢占式）

实现思想：

• ① 系统中设置多个就绪队列，每个队列对应一个优先级，优先级依次递减；
• ② 每个队列都采用时间片轮转法，但时间片都不同，高优先级队列的时间片小，低优先级队列的时间大；
• ③ 新进程进入系统后，先放入第1个队列的末尾，如果在时间片内工作未完成，则转入下一个队列尾，依此类推；
• ④ 系统先运行第1个队列中的进程,若第1队列为空,才运行第2队列，依次类推。

特点：

• 抢占式调度，使用动态优先级机制。
• 是时间片轮转和优先级调度算法的综合和发展。
• 通过动态调整进程优先级和时间片大小，兼顾多方面系统指标。是最通用的CPU调度算法，也最复杂。
• 需要解决“饥饿”问题。

线程调度

多线程系统中，提供了进程和线程两级并行机制。

用户级线程

核心只为进程提供服务，即从就绪队列中挑选一个进程（例如A），为它分配一个时间片，然后由进程A内部的线程调度程序决定让A的哪一个线程（如A1或A2）运行。

最常用的算法是轮转法和优先级法。时钟中断对运行线程不起作用。

核心级线程

由核心调度线程，不同进程的线程之间可能发生切换。

用户及线程调度和核心级线程调度的特点

性能：

• 用户级线程切换可以用机器指令，速度快；核心级线程切换需要全部上下文切换，速度慢。

阻塞：

• 在核心级线程方式下，一个线程因等待I/O而阻塞时，不会挂起整个进程；而用户级方式下会挂起整个进程。

实时调度

实时调度概述

实时调度：满足实时任务各自时间约束条件的调度。

实时任务类型

实时任务的分类：

• 根据对截止时间的要求不同分类：
  • 硬实时任务：指系统必须满足任务对截止时间的要求，否则后果要命。
  • 软实时任务：任务与预期的截止时间相关联，但不是绝对严格。
• 根据任务执行是否呈现周期性来分类
  • 周期性任务：以固定的时间间隔出现的事件，如每周期T出现一次。
  • 非周期性任务：事件的出现无法预计，但规定了必须完成或开始的时间。

实时调度算法

实时调度算法分为静态和动态两种：

• 静态调度：在系统开始运行之前做出调度决策。
• 动态调度：在运行时做出调度决策。

优先级随速率单调的调度算法（Rate Monotonic Scheduling, RMS）：

• RMS是针对可抢占的周期性进程而采用的经典算法，用于满足下述条件的进程：
  • 每个周期性进程必须在其周期内完成
  • 进程间彼此互不依存
  • 每个进程在每次运行时需要相同的CPU时间
  • 非周期性进程都没有截止时间限制
  • 进程抢占瞬间完成，开销可以不计
• 该算法未每个进程分配一个固定的优先级，等于出发事件发生的频度。
• 调度思想：
  • 任务周期最短的进程优先级最高，调度程序总是运行优先级最高的进程，必要时抢占。

最早截止时间优先调度算法(Earliest Deadline First, EDF)

调度思想:

• 每当一个进程需要占用CPU时，要表明自己的存在和截止时间等信息；
• 调度程序把就绪进程按截止时间先后顺序放在一个表格中；
• 调度时，选择表中的第一个进程，其截止时间最近。

多处理器调度

多处理器系统的类型

多处理器系统与单处理器系统相比，在速度、性能、可靠性等方面有很大提高，但结构和管理也变得更复杂。

多处理器系统主要分为三种类型：

• 松散耦合多处理器系统(集群系统)
  • 每台处理器有自己的内存、I/O和OS
• 紧密耦合多处理器系统
  • 一组处理器共享内存，在一个OS的集中控制下工作（如对称多处理器结构）。
• 主从多处理器系统
  • 有一个主处理器Master，多个从处理器 Slaver；操作系统和它的表格只放在主控机上；从机仅执行主控机指派的计算任务；所有的系统调用由主控机完成。

与单处理器调度的区别

注重整体运行效率（而不是个别处理机的利用率）
具有更多样的调度算法
调度单位广泛采用线程

多处理器调度方法

与多处理器调度相关的主要内容：

• 给处理器分配进程：
  • 静态分配：把一个进程固定地分给一个处理器，每个处理器只保持一个就绪队列。调度开销小，但各处理器可能忙闲不均。
  • 动态分配：把系统中所有就绪进程放入一个全局队列，从中选出进程分派到任何可用的处理器上。一个进程在其生命周期内可能在不同时间、不同处理器上执行。
• 在单个处理器上使用多道程序技术
  • 传统的多处理器中没有线程，每个处理器在若干进程之间切换，可获得高利用率和良好性能。
  • 如果一个应用程序由多线程的单个进程实现，则让组成一个应用程序的所有线程同时运行，性能最好。
• 实际分派进程或线程（采用调度算法）
  • 调度算法越简单，开销越小，效率就越高。
  • 一般采用先来先服务和静态优先级算法。

多处理器系统中线程调度通常有四种方式：

• 负载共享
  • 系统维护一个全局就绪线程队列，当某个处理器空闲时，就从该队列中选择一个线程。
• 成组调度
  • 把一组相关线程作为一个单位同时调到一组处理器上运行，所有线程一起开始和结束它们的时间片。
• 专用处理器分配
  • 当一个进程被调度时，它的每个线程被分配到一个处理器上，在该进程完成之前，处理器由相应的线程专用。
• 动态调度
  • 允许在进程执行期间动态改变其线程的数目。

UNIX/Linux进程调度

UNIX进程调度

一般策略：多级反馈队列轮转法

实现思想：

• 系统中的就绪进程按照不同种类分成多个就绪队列，每个队列的优先级不同，每个队列都采用轮转法。
• 核心从最高优先级的就绪进程队列中选择一个进程，分配一个时间片，当时间片用完后，CPU被另外进程抢占，而该进程被送回相同优先级队列的末尾。
• 核心动态调整用户态进程的优先级。

LINUX进程调度

一般策略：抢占式优先级

实现思想：

• 系统为每个进程都计算一个优先级，核心从就绪队列中挑选一个优先级最高的进程，为其分配一个时间片，使其运行。
• 在运行过程中，当前进程的优先级随时间递减，实现负反馈，即经过一段时间后，原来级别较低的进程就相对“提升”了级别。
• 当所有进程的优先级都变为最低时，就重新计算一次所有进程的优先级。

针对不同类别的进程提供了三种不同的调度策略：

• 短实时进程：SCHED_FIFO策略（先来先服务）。
• 长实时进程：SCHED_RR策略（时间片轮转法）。
• 交互式的分时进程：SCHED_OTHER策略，是传统的UNIX调度策略——优先级反馈法。

系统中规定，实时进程的优先级高于其他类型进程的优先级。

多种调度特点↓

中断处理

终端概述

在不同的系统中，中断的分类和处理方式不完全相同，但基本原则相同。中断的典型实例是I/O中断。

中断的概念：

• 中断是指CPU对系统发生的某个事件做出的一种反应，它使CPU暂停正在执行的程序，保留现场后自动执行相应的处理程序，处理该事件后，如被中断进程的优先级最高，则返回断点继续执行被“打断”的程序。

引起中断的事件或发出中断请求的来源称为中断源。中断源向CPU提出的处理请求称为中断请求。发生中断时，被打断程序的暂停点称为断点。

中断最初是作为通道与CPU之间进行通信的工具。

• 为使CPU摆脱繁忙的I/O事务，现代大中型计算机都设置了专门处理I/O操作的机构——通道。
• 它相当于一台小型处理机，接受主机的任务，对外部设备的I/O操作进行控制。
• 当主机委托的I/O任务完成后，通道发出中断信号，请求CPU处理。这使得CPU基本上摆脱了I/O处理工作，提高了CPU和外设工作的并行程度。

终端系统的作用：

• 提高主机的利用率，使高速CPU可以和低速的外部设备并行工作。

• 及时进行事故处理。

• 实现分时操作。

• 实现实时操作。

  • 在实时控制系统中，很多信号是随机产生的，只有通过中断系统才能对它做出及时的处理。

• 方便程序调试。

  • 可人为设置断点，随时中断程序的执行，查看中间结果，了解机器的状态，输入临时命令。

中断类型：

• 按中断事件来源划分：
  • 中断。它是由CPU以外的事件引起的。
  • 异常（Exception）。它是来自CPU内部的事件或程序执行中的事件引起的过程。
• 系统调用也称为陷入。

中断的处理过程

中断的硬件结构↓

中断响应

硬件对中断请求做出反应的过程，称为中断响应。具体动作如下：

• 中止当前程序的执行；
• 保存原程序的断点信息（主要是程序计数器PC和程序状态寄存器PS的内容）；
• 转到相应的处理程序。

中断处理

中断响应之后就进行相应处理。

中断处理过程大致分为四个阶段：

• 保存现场

  • ① 集中式保存：在系统内存区中设置一个中断现场保存栈，所有中断的现场信息统一保存在这个栈中。

  • ② 分散式保存：在每个进程的PCB中设置一个核心栈，一旦其程序被中断，它的中断现场信息就保存在自己的核心栈中。

• 分析原因

  • 确定“中断源”或查证中断发生，识别中断类型（确定是时钟中断还是盘中断）和中断设备号（哪个磁盘引起的中断）。

• 处理中断

  • 调用中断处理程序进行处理

• 中断返回

  • ① 选取可以立即执行的进程。
  • ② 恢复工作现场。

中断优先级和多重中断

中断优先级：

• 硬件设计时，一般把紧迫程度大致相当的中断源归并为一组，称为一个中断级。
• 与某种中断相关的优先权称做它的中断优先级。

中断屏蔽和中断禁止：

• 中断屏蔽是事件提出中断请求后，CPU不予响应。
• 中断禁止是硬件禁止事件提出中断请求。

中断屏蔽的作用：

• ① 延迟或禁止对某些中断的响应。
• ② 协调中断响应与中断处理的关系。
• ③ 防止同类中断的相互干扰。

中断屏蔽的方式：

• 可以用于整级屏蔽，也可用于单个屏蔽。

信号机制

信号机制是在软件层次上对中断控制的模拟。进程之间可以通过信号机制实现某些控制，利用传送信号方式进行简单通信。

信号机制概念

信号的概念：

• 信号（也称软中断）机制是在软件层次上对中断机制的一种模拟，信号的发送者（一个进程）相当于中断源，接收者（另一个进程）相当于CPU。
• 异步进程可以通过彼此发送信号来实现简单通信。
• 系统预先规定若干不同类型的信号，表示发生了不同的事件。
• 

信号与中断机制的异同：

• 相似之处：
  • 信号与中断在概念上是一致的。一个进程接收到一个信号与一个处理器接收到一个中断请求是一样的。
  • 二者都是“异步”的。处理器在处理一段程序时，不知道中断在何时发生，同样一个进程也不知道什么时候会有信号到达。
  • 二者在实现上都采用“向量表”的方式。通过中断向量表，可以找到处理相应中断的入口地址，进而转入中断处理程序。信号也如此。
  • 都有屏蔽手段。在中断机制中对每种中断请求都可进行屏蔽。信号也如此。
• 差别：
  • 中断机制是通过硬件和软件的结合实现的，信号完全由软件实现。
  • 中断向量表在系统空间中，每个中断向量所对应的中断处理程序也在系统空间中。信号的“向量表”在系统空间中，信号处理程序在用户空间中。
  • CPU接到中断请求后，一般会立即做出响应和处理。信号的检测和响应要在特定情况下进行，如退出中断之前。

信号分类

UNIX S_5的信号分类及含义见下表：

信号处理方式

在unix系统中，进程user结构中有一个signal数组，信号的编号对应数组下标，数组元素的值规定了该进程收到信号时采取的动作。如下：

信号的检测和处理

第五章 储存管理器

内存管理

内存管理的基础

内存管理的概念

内存管理就是操作系统对内存的划分和动态分配。

内存管理的功能

内存空间的分配与回收（包括分配与共享）

• 当用户需要内存时，系统为之分配相应的存储空间；不需要时，及时回收，以供其它用户使用。
• 不仅能使多道程序动态地共享主存，提高主存利用率，还能共享主存中某个区域的信息。

地址转换：

• 把逻辑地址转换成相应的物理地址。

储存保护：

• 确保多道程序都在各自分配到存储区域内操作，互不干扰，防止一道程序破坏其它作业或系统文件的信息。

内存空间的“扩充”：

• 利用虚拟存储技术（早期用自动覆盖技术），从逻辑上扩充内存。为用户提供比主存物理空间大得多的地址空间，使用户感觉他的作业是在一个大的存储器中运行。

用户程序的主要处理阶段

在进行具体的内存管理之前，需要了解进程运行的基本原理和要求。
用户程序的主要处理阶段如下图所示。

编译阶段：

• 由编译程序将用户源代码编译成若干个目标模块。

链接阶段：

• 由链接程序将编译后形成的一组目标模块，及所需库函数链接，形成完整的装入模块。
• 程序的链接有以下三种方式：
  • 静态链接
    • 在程序装入之前，先将各目标模块及他们所需的库函数链接成一个完整的可执行程序，以后不再拆开。
  • 装入时动态链接
    • 在装入内存时，边装入边链接。
  • 运行时动态链接
    • 在程序执行中需要该目标模块时才对它进行链接。

装入阶段：

• 
• 
• 用户程序经编译之后的每个目标模块都以0为基地址顺序编址，其余指令中的地址都相对于首地址而编址。这种地址称为相对地址或逻辑地址。
• 内存中各物理存储单元的地址是从统一的基地址开始顺序编址的，这种地址称为绝对地址或物理地址。

程序装入内存有以下三种方式：

• ① 绝对装入方式
  • 编译时，如果知道程序将驻留在内存的某个位置，编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，因为程序中的逻辑地址与实际内存地址完全相同，故不需要对程序和数据的地址进行修改。
  • 绝对装入方式只适用单道程序环境。
  • 程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。
  • 在程序中采用符号地址，编译或汇编时转换为绝对地址。
  • 
• ② 可重定位装入方式
  • 重定位：对目标程序中的指令和数据进行修改，把目标程序中的逻辑地址转换为物理地址。
  • 由装入程序根据内存当时的使用情况，决定将装入模块放在放在内存的什么地方。装入模块内使用的地址都是相对地址。
  • 
• ③ 动态运行时装入方式
  • 为使内存利用率最大，装入内存的程序可以换出到磁盘上，以后再换入内存中，对换前后在内存中的位置可以不同。
  • 程序在内存中位置变了，就需要采用动态的装入方式。
  • 

重定位

把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。又称地址映射。

重定位的类型：

• 静态重定位
  • 当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）作业i在执行前一次变址，直到该作业完成退出内存为止。
  • 
  • 优点
    • 不需硬件地址转换机构，便于实现程序的静态链接。
  • 缺点
    • 一个作业装入内存时，必须分配其要求的全部内存空间，否则不能装入。
    • 需要占用连续的内存空间，程装入内存后不能移动。
    • 不易实现共享。
• 动态重定位
  • 在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。
  • 
  • 优点
    • OS可以将一个程序分散存放于不连续的内存空间，可以移动程序。有利用实现共享。
  • 缺点
    • 需要硬件支持, OS实现较复杂。
  • 动态重定位是虚拟储存的基础
    • 在程序运行之前可以只装入它的部分代码即可运行，然后再运行期间，根据需要动态申请内存。

内存保护

内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。

需要硬件支持实现保护。

硬件支持：

• 基址寄存器（重定位寄存器）：存放用户程序在内存的起始地址。
• 限长寄存器（界地址寄存器）：存放用户程序逻辑地址的最大范围。

实际上，实现动态重定位也需要这对寄存器的支持。

当CPU调度程序选择进程执行时，派遣程序会初始化基址位寄存器和限长寄存器。
每一个地址都需要与寄存器进行核对。
每个逻辑地址值必须小于限长寄存器。

覆盖与交换

基本思想：

• 把处于等待状态（或在CPU调度原则下被剥夺运行权利）的进程从内存移到辅存，把内存空间腾出来，这一过程叫换出；把准备好竞争CPU运行的进程从辅存移到内存，这一过程叫换入。
• 交换技术主要是在不同进程（或作业）之间进行。
• 

连续分配管理方式

区分：连续分配和非连续分配

把内存分为一些大小相等或不等的分区(partition)，每个进程占用一个分区。操作系统占用其中一个分区。

分区法特点：适用与多道程序系统和分时系统。

• 支持多个程序并发执行。
• 难以进行内存分区的共享。

连续分配：使用分区技术（分区法）：

• 固定分区
• 动态分区
• 可重定位分区

固定分区法

基本思想：

• 预先把可分配的主存储器空间分割成若干个连续区域，每个区域是一个分区。
• 内存中分区的个数固定不变
• 各个分区的大小也固定不变
• 每个分区只可装入一个进程

分区大小：

• 等分方式
• 不等分方式

储存分配：

• 对于分区等分方式，进程装入内存很简单。
• 对于分区不等分方式，为进程分配分区的方法有两种。
  • 多个输入队列法
  • 单一输入队列法
    • 
  • 优点：
    • 易于实现，，开销小。
  • 缺点：
    • 分区总数固定，限制了并发执行的程序数目。
    • 小作业不能充分利用分区空间。
    • 内碎片造成浪费。

动态分区法

基本思想：内存不是预先划分好的，而是当进程装入时，根据进程的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间。

系统中分区的大小和数目是可变的。

内存管理：设置内存空闲块表——记录了空闲区起始地址和长度。
内存分配：动态分配。
内存回收：当某一块归还后，前后空间合并，修改内存空闲块表。

数据结构

空闲分区表：

空闲分区链：

分配算法

寻找某个空闲分区，其大小需大于或等于进程的要求。 若等于要求，则从空闲表中取消该项；若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区标记为“空闲”，需更新分区大小和分区地址。

分配算法：

• 最先适应法——首次适应法
  • 空闲表按空闲块地址递增排序。
  • 分配内存时，顺序查找满足大小要求的第一个可用块。
  • 该算法的分配和释放的最初时间性能较好，较大的空闲分区可以被保留在内存高端。
  • 但随着低端分区不断划分而产生较多小分区，每次分配的查找时间开销会增大。
• 循环法——邻近适应法
  • 由首次适应法演变而成，不同之处是，分配内存时从上次查找结束的位置开始继续查找。
  • 该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。
• 最佳适应法
  • 空闲表以空闲块大小为序，按增量形式排列。
  • 接到内存申请时，顺序查找第一个满足大小要求的空闲块。
  • 特点：用最小空间满足要求。
    选择分区时总是寻找其大小最接近所要求的存储区域。
  • 个别来看，碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。
• 最坏适应法——最大适应法
  • 空闲表以空闲块大小为序，按递减形式排列。
  • 接到内存申请时，找到第一个满足要求的分区，即挑选出最大的分区。
  • 较大的空闲分区不被保留。

可重定位分区

可重定位分区是动态分区法的一种。
可重定位分区是借助紧缩技术和动态重定位技术实现的分区分配方法。
重要概念：

• 碎片
• 紧缩
• 动态重定位

碎片问题

经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片。
造成存储资源的浪费

内部碎片与外部碎片：

• 在一个分区内部出现的碎片（即被浪费的空间）称做内部碎片，固定分区法会产生内部碎片。
• 在所有分区之外新增的碎片称做外部碎片，动态分区法会产生外部碎片。

紧缩

移动某些已分配区的内容，使所有进程的分区紧挨在一起，而把空闲区留在另一端。这种技术称为紧缩（或拼凑）。
类似于windows系统中的磁盘整理程序（对外存空间的紧缩）。

什么时候进行紧缩？有两种方案
当进程结束、释放所占用的分区时
在分配进程的分区时进行（当各个空闲区都不能满足该进程的需求时才进行）

可重定位分区法的优缺点

优点：可以消除碎片，能够分配更多的分区，有助于多道程序设计，提高内存的利用率。
缺点：紧缩花费了大量CPU时间；当进程大于整个空闲区时，仍要浪费一定的内存；进程的存储区内可能放有从未使用的信息；进程之间无法对信息共享。

非连续分配管理方式

分 页 技 术

分页技术的引入

在动态分区的存储空间中，存在“碎片”问题。尽管采用“紧凑”技术可以解决这个问题，但要为移动大量信息花去不少的处理机时间，代价较高。

分页技术：允许一个进程的存储空间不必连续，可以分散地放在各个空闲的内存区域中。解决了外部碎片，并提高了内存的利用率。

分页存储管理的基本概念

（1）逻辑空间分页

把进程的逻辑地址空间划分成若干个大小相等的部分，每个部分称为页。
每个页有一个编号。从0开始编制页号。
页内地址是相对于0编址。

（2）内存空间分块

内存按页的大小划分为大小相等的区域，称为内存块（页框）。
每个块有一个编号。从0开始编制块号。

页面（或块）的大小是由硬件（系统）确定的。
一般，页面大小应是2的若干次幂。

（3）内存分配原则

在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不邻接的物理块中。

（4）页表

页表的作用是实现从页号到物理块号的地址映射。
系统为每个进程分配一个页表。在进程控制块（PCB）中存放指向该页表的指针。当调度一个进程运行时，就必须重新加载其各个寄存器，使硬件页表取得正确的值。
通常将页表保存在内存中，由一个页表基址寄存器PTBR指向该页表。整个系统只有一个PTBR。当发生切换时，只需要改变PTBR的指向——使它指向选中进程的页表。

（5）内存块表

整个系统有一个内存块表。每个内存块在内存块表中占一项，表明该块当前空闲还是已分出去了。

（6）逻辑地址表示

CPU运行进程时，读到的是一维的逻辑地址。由系统硬件对这个地址进行计算，表达成数对的形式：（页号，页内地址）

若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号p和页内地址d可按下式求得：

• p = INT[A/L] , d = [A] MOD L

例子↓

例1：设某系统的页面大小为1KB，给定的逻辑地址为3456B，请给出该逻辑地址的页号和页内地址。
解答：
页的大小 L=1KB=1024B
逻辑地址A=3456B
页号p= INT[A/L] = INT[3456/1024]=3
页内地址d = [3456] MOD 1024 =384

分页系统中的地址映射

逻辑地址到物理地址的变换过程：

• 地址变换机构自动地将有效地址分为页号和页内偏移量两部分，再用页号去检索页表。在执行检索之前，先将页号与页表长度比较，如果页号大于或等于页表长度，则表示地址越界并中断。
• 若未越界，则页表起始地址+页号*页表项长度=该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。
• 与此同时，再将有效地址中的页内偏移量送入物理地址寄存器的块内地址字段中。
• 整个地址变换过程均是由硬件自动完成的。

分页存储管理存在的两个主要问题：

• 1.每次访存操作都要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低。
• 2.每个进程引入页表，用于存储映射机制，页表不能太大，否则内存利用率会降低。

采用分页技术不存在外部碎片。每个进程平均有半个页面的内部碎片。

页面尺寸

页面尺寸对系统性能有影响。

• 如果页面太小，会使进程的页面数过多，页表过长，占用大量的内存。也会增加硬件地址转换的开销，降低页面换入/换出的效率。
• 如果页面过大，会使页面碎片增大，降低内存的利用率。

当只考虑进程大小和页表项的大小时，可以计算出一个相对最佳的页面尺寸公式。
设进程的平均大小为s字节，页面尺寸为p字节，每个页表项占e字节，由页表和内部碎片带来的总开销是：es/p + p/2
se /p + p/2对p求导，令其等于0，得到方程：- s *e / p2 + 1/2=0。从方程得到最佳页面尺寸公式：

• p=$(\sqrt{2se})$
• 如果s = 1 MB，e = 8 B，则最佳页面尺寸是4 KB。

随着内存空间的增大，页面尺寸也逐渐增大，但非线性增长。

硬件支持

页表基址寄存器PTBR
快表

内存中放置页表会带来存取速度下降的矛盾。

• 因为存取一个数据（或指令）至少要访问两次内存。
• 这时的存取速度为通常寻址方式速度的1/2。

解决方法：在地址变换机构中增设一个具有并行查找能力的高速缓冲寄存器——快表（Translation Lookaside Buffer, TLB）

• 专用的、高速的、小容量的联想存储器
• 用于存放当前访问的若干页表项
• 存储项数少，一般为64-1024项

在具有快表的机制中，地址变换过程：

• 1.CPU给出有效地址后，由硬件进行地址转换并将页号送入高速缓存寄存器，并将此页号与快表中的所有页号同时比较。
• 2.如果找到匹配的页号，则直接读出对应的内存块号，送到物理地址寄存器。存取数据实现一次访存。
• 3.如果没找到，则访问主存中的页表，读出页表项后，同时放入快表。若快表已满，则按照一定的算法替换其中的旧表项。

有些处理器设计为快表和主存同时查找，若在快表中匹配成功则终止主存的查找。
一般快表的命中率可以达到90%，这样，分页带来的速度损失就降低到10%。
快表的有效性是基于著名的局部性原理。

保护方式

（1）利用页表本身进行保护

• 每个进程有自己的页表，页表的基址信息放在该进程的PCB中。访问内存需要利用页表进行地址转换，使得各进程在自己的存储空间内活动。
• 为了防止进程越界访问，某些系统还提供页表长度寄存器PTLR，记载页表的长度。

（2）设置存取控制位

• 在页表的每个表项中设置存取控制字段。
• 有只读（R）、读写（RW）、读和执行（RX）等。

（3）设置合法标志

• 在页表的每项中设置合法/非法位。
• 设置为“合法”时，表示相应的页在该进程的逻辑地址空间中是合法的页。
• 设置为“非法”时，表示该页不在该进程的逻辑空间内。利用这一位可以捕获非法地址。
• 操作系统为每一页面设置这一位，从而规定允许或禁止对该页的访问。
• 例如，系统的地址空间为14位（0-16383B），程序使用的地址空间是0-10468B。页面大小为2KB。
  在页表中，0~5号页面是合法的，可以进行正常的地址转换。6、7号页面应设置“非法”标志，禁止对这两个空页面进行访问。

页表的构造

页表可以构造成多种形式：

• (1) 多级页表

  • 在逻辑地址空间较小的情况下，每个进程只使用一个页表实现地址转换即可。
  • 例1：逻辑地址空间用32位表示，页面大小为4KB。
    问题1：逻辑地址空间可分成多少页？
    232 / 212 = 220个页面。
  • 
  • 问题2：若页表每项占4B，则页表大小为多少？
    4B* 220 =4MB。
  • 
  • 问题3：页表分成多少页？
    4MB/4KB= 210个页面。
  • 

• (2) 散列页表

  • 处理大于32位地址空间的通用方式。
    需要散列函数。

  • 以页号作为参数，通过散列函数形成散列值。散列页表中记录不同的散列值，一个散列值对应一项。

  • 不同的页号，可能对应相同的散列值。散列表中每一项有一个链表，它把有相同散列值的元素链接起来。

  • 每个链表元素由三部分组成：页号，对应的内存块号，指向链表中下一个元素的指针。

  • 地址转换：以页号p作为散列函数的参数，得到一个散列值，作为检索散列页表的索引。把p与相应链表的第一个元素内表示页号的字段进行比较，匹配则进一步生成物理地址，不匹配则沿着链表指针向下搜索，直至找到匹配的页号。

  • 

• (3) 倒置页表

  • 为了减少页表占用过多的内存空间，可以采用倒置页表。
    普通页表是按照虚拟页号排序的，而倒置页表是按照内存块号排序的。
    普通页表是一个进程对应一个，而倒置页表所有进程对应一个。
  • 系统中只有一个页表，依据内存来设置表项，每个内存块对应唯一的表项，表项按内存块号排序。
  • 每个虚拟地址由三部分组成：进程标识符pid，虚拟页号p，页内地址d。
  • 每个表项包括两部分：进程标识符pid，虚拟页号p 。
  • 地址转换：用pid和p去检索页表，若找到匹配项，则该表项的序号i就是对应的内存块号，进一步生成物理地址；若搜索完整个页表，没有找到匹配项，则说明此页尚未调入内存。
  • 
  • 倒置页表减少了页表占用的内存，却增加了检索页表时所耗费的时间，可能要查找完整个页表才能找到匹配项。为了改善性能，可以跟快表一起使用。

页面共享

共享方法：使这些相关进程的逻辑空间中的页指向相同的内存块，该块中放有共享程序或数据。

图为三个进程共享大小为三个页面的编辑器的情况，每个进程都有自己的私有数据页。

存在问题：作业或进程的逻辑地址空间是连续的，当系统将进程的逻辑地址空间划分成大小相同的页面时，被共享的程序文本不一定刚好在完整的页面中。

分页系统中实现页的共享比较困难.

分 段 技 术

分段存储管理的基本概念

1．分段

• 段是一组逻辑信息的集合。每段都有自己的名字和长度。每段都从0开始编址，并采用一段连续的地址空间。
• 用户程序需要进行编译，编译程序自动为输入的程序构建各个段。

2．程序的地址结构

• 因为整个进程的地址空间分成多个段，所以逻辑地址要用两个成分来表示：段号s和段内地址d。
• 在分段的情况下，进程的逻辑地址空间是二维的。
• 

3．内存分配

• 内存以段为单位进行分配，每段单独占用一块连续的内存分区。各分区的大小由对应段的大小决定。
• 各个段在内存中不必连续，可以离散存放。

4．段表和段表地址寄存器

• 系统为每个进程建立一个段映射表，简称“段表”。每个段在段表中占有一项，段表项中包含段号、段长和段起始地址（又称“基址”）等。
• 系统还要建立一个段表地址寄存器。
  • 存放该段表在内存的起始地址和该段表的长度（有几段，长度就是几）。
• 

地址转换

地址转换过程：

• 1.将段号S与段表长度TL进行比较。若S>=TL，地址越界，发出越界中断信号；否则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。
• 2.检查段内地址W是否超过该段的段长SL。若W>=SL，地址越界；否则将该段的基址d与段内地址相加，得到物理地址。
• 

段的共享和保护

1．段的共享

• 共享是在段一级实现的，任何共享信息可以单独成为一段。
• 

2．段的保护
段的保护措施有三种:

• ① 存取控制

• ② 段表本身可起保护作用

• 表项中设置该段的长度限制。

• 段表地址寄存器中有段表长度的信息。

• ③ 保护环

  • 把系统中所有信息按照其作用和调用关系分成不同的层次（环），低编号的环具有高优先权，操作系统内核位于0环内；重要的实用程序和操作系统服务位于中间环；一般的应用程序（包括用户程序）位于外环上。
  • 一个环内的段可以访问同环内或环号更大的环中的数据段；一个环内的段可以调用同环或环号更小的环中的服务。

分页和分段的主要区别

页是信息的物理单位。
段是信息的逻辑单位。
页的大小是由系统确定的。
段的长度因段而异。
页的地址空间是一维的。
段的地址空间是二维的。
分页系统很难实现过程和数据的分离。
分段系统却可以很容易实现这些功能。
分页有内部碎片。
分段有外部碎片。

段页式技术

分页存储管理能够有效地提高内存利用率，而分段存储管理能够很好地满足用户需要，把这两种技术有机地结合起来，就形成了段页式存储管理系统。

段页式技术的基本原理

1.等分内存
2.进程的地址空间采用分段方式
3.段内分页
4.内存的分配单位是内存块
5.逻辑地址由三部分组成：段号s、页号p和页内地址d

6.段表、页表、段表地址寄存器

• 为实现地址转换，系统为每个进程建立一张段表，为每个分段建立一张页表。
  • 段表至少包括：段号、段长（页表长度）、页表起始地址
  • 页表至少包括：页号、块号
• 系统有一个段表寄存器
  • 段表起始地址
  • 段表长度

面向用户的地址空间是段式划分，面向物理实现的地址空间是页式划分。
用户程序逻辑上分为若干段，每段又分成若干页。
逻辑上连续的段存放在分散的内存块中。

地址转换过程：

• 1.将段号S与段表长度L进行比较。若S>=L，地址越界；否则，将段号S与段表基址B相加，得到访问第S段的入口地址。
• 2.将段号S表项中的页表长度与段号p进行比较。如果p>=页表长度，地址越界；否则将该段的页表基址与页号p相加，得到访问第p页的入口地址。
• 3.读出该页所在的物理块号f，用块号f和页内地址d拼接成访内地址。
• 如果对应的页不在内存，则发生缺页中断。如果该段的页表未在内存中建立起来，则发生缺段中断，由系统为该段在内存建立页表。（虚存管理的思想）
• 进行一次访问实际需要三次访问内存，可以使用快表加快访问速度。

基本分页、分段、段页式技术的主要特点

采用动态重定位：进程中的所有存储器访问都是逻辑地址，这些逻辑地址在运行时动态地被转换为物理地址。
离散分配：一个进程可以被划分成多个页（或段），这些页或段不需要连续地位于主存中。
一次性：作业必须一次性全部装入内存，才能启动运行。
驻留性：作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。

虚拟内存管理

虚拟内存概念

局部性原理

程序的执行过程具有局部性

• 大部分程序结构是顺序的，只有少数部分为转移或过程调用
• 过程调用一般不超过5层
• 程序中存在循环，反复执行
• 对于数组的处理将局限于较小范围
• 基于局部性原理，可以将程序的一部分装入内存，就启动程序运行，其余部分放在外存，当执行的指令不在内存时，由系统自动完成将它们从外存调入内存的工作。
• 好处：
  用户编制程序时不必过多考虑内存容量的限制
  在一定容量的内存中就可同时装入更多的进程

虚拟存储器（虚拟内存）的概念

虚拟存储器：

• 就是用户能作为可编址内存对待的虚拟存储空间，它是操作系统给用户提供的一个比真实内存空间大得多的地址空间。虚拟存储技术建立了“内存+外存”的两级存储器结构，并将二者有机地结合在一起，从而得到一个容量相当于外存，速度接近于内存的存储体系。

“虚拟”：

• 并非实际内存。只是由于系统提供了部分装入、请求调入和置换功能后，用户感觉能使用的内存非常大，实际是对逻辑内存的扩充。

虚拟存储器的特征

① 虚拟扩充

• 扩大逻辑内存的容量，即用户编程时用到的地址空间可以远大于实际内存的容量。

② 部分装入
③ 离散分配
④ 多次对换

• 在一个进程运行期间，它所需要的全部程序和数据分成多次调入内存。而暂时不被使用的部分，可以换出到外存的对换区。

虚拟存储器容量不是无限大的，它主要受两方面的限制:

• 指令中表示地址的字长
  • 如：若CPU的有效地址长度为32位，则程序可以寻址范围是0～ 232-1 ，即虚存容量为 4GB。
• 外存的容量
  • 用户的程序和数据都必须完整地保存在外存中（如硬盘），因为外存容量有限，所以虚拟空间不可能无限大。

虚拟存储技术的实现

虚拟内存的实现主要有三种方式：

• 请求分页存储管理

• 请求分段存储管理

• 请求段页式存储管理

请求分页管理方式

请求分页存储管理的基本思想

基本思想：

当一个进程的部分页面在内存时就可调度它运行；在运行过程中若用到的页面不在内存，则把它们动态换入内存。因为这种页面是根据请求被装入的，所以称之为请求分页存储管理。

为了实现请求分页，系统必须提供一定的硬件支持，包括：

• 一定容量的内存和外存

• 页表机制

• 缺页中断机构

• 地址变换机构

硬件支持及缺页处理

1．页表机制

• 页表项通常包含下列几种信息：
• 
• 禁止缓存位：用于禁止该页被缓存。

2．缺页中断机构

缺页中断处理是由硬件和软件共同实现的。
在硬件中增加了对缺页中断进行响应的机构，一旦发现所访问的页面不在内存中，立即产生中断信号，随后转入缺页中断处理程序进行处理。

请求分页技术的性能

请求分页会对计算机系统产生重要影响。

缺页率

• 缺页中断的概率，用p表示（0≤p≤1），它等于缺页次数与全部访问内存次数之比。

有效存取时间

• 如果不出现缺页中断，有效存取时间等于内存存取时间。内存存取时间ma一般为10~200ns。
• 如果发生缺页中断，则首先必须从外存读入该页，然后才能进行内存存取。
• 有效存取时间= (1-p)×ma + p×缺页中断处理时间
• s、ms、μs、ns之间的进率是1000

在任何情况下，缺页中断处理所花费的时间主要有以下三部分：

• （1）处理缺页中断的时间
• （2）调入该页的时间
• （3）重新启动该进程的时间
• （1）和（3）每项执行的时间约为1~100 μs

调入该页的时间是将页面从盘上读到内存，这个过程花费的时间包括三部分：

• 1.磁盘寻道时间（即磁头从当前磁道移至指定磁道所用的时间），典型寻道时间约为15 ms。
• 2.旋转延迟时间（即磁头从当前位置落到指定扇区开头所用的时间），典型磁盘的旋转延迟时间约为8 ms。
• 3.数据传输时间，典型传输时间是1 ms。

全部换页时间将近25 ms，包括硬件和软件处理的时间。

如果把平均缺页服务时间取为25 ms，内存存取时间取为100 ns，那么

• 有效存取时间= (1- p)×100 + p×25 000 000

                    = 100 + 24 999 900×p
  

• 如果缺页率为千分之一，则有效的存取时间约为多少？

• 答：25000ns。
  由于请求分页使计算机慢了250倍。

• 有效的存取时间直接正比于缺页率。

• 为使存取速度下降在10%以内，缺页率不能超过千万分之四。

页面置换算法

页面置换

请求分页必须解决两个主要问题：

• 内存块的分配
  • 如果有多个进程在内存，必须决定为每个进程分配多少内存块，由内存块分配算法完成。
• 页面置换
  • 当需要置换页面时，必须确定淘汰哪个页面，由页面置换算法完成。

页面置换的应用

• 例如，大多数计算机都有一个或多个内存的高速缓存，用来存放最近访问过的32字节或64字节的内存块。如果高速缓存满了，就必须选择一个数据块移出去，即置换。这个问题的时间规模更短，因为它需要的数据块来自于内存。
• 又如，浏览器会在磁盘的缓存区中保留一些以前访问过的Web页面的副本。如果缓存区满了，就必须挑选一个页面删除，即置换。被删除的页面不必写回到Web服务器中，因为缓存区中的Web页面从来不会被修改。

页面置换过程

• 

置换算法的好坏直接影响系统的性能。

• 若采用的置换算法不合适，可能出现这样的现象：刚被换出的页，很快又被访问，为把它调入而换出另一页，之后又访问刚被换出的页，……如此频繁地更换页面。这种现象称为 “抖动”。

页面走向

• 为评价一个算法的优劣，可将该算法应用于一个特定的存储访问序列上，并计算缺页数量。存储访问序列也叫页面走向。
• 为了减少计算量，对页面走向进行如下简化：
  • 对于给定的页面大小，仅考虑其页号，不关心完整的地址。
  • 如果当前对页面p进行了访问，那么，马上又对该页访问就不会缺页。这样连续出现的同一页号就简化为一个页号。

最佳置换法（OPT）

思想：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。以此保证获得最低的缺页率。

优点：
性能最佳，缺页中断率最低。
缺点：
理想化的算法，无法实现。
因为它需要预先知道一个进程整个运行过程中页面走向的全部情况。
作用：
模拟实验分析或理论分析其他算法的优劣。

先进先出法（FIFO）

思想：为调入新页面而必须预先淘汰某个老页面时，总是淘汰在内存中停留时间最长的一页，即先进入内存的页，先被换出。

优点：
容易理解，实现简单，方便程序设计。
缺点：
性能不好。因为常被访问的页，通常在内存中停留最久。
仅当按线性顺序访问地址空间时，才是最理想的，否则效率不高。
作用：
作为基础算法被应用在其他算法中。

如何记录哪个页面在内存停留时间最久？

• 实现方法
  计时器。在页面上加计时器记录最早进入的页。
  队列。只需把调入内存的页面根据先后次序链接成队列，设置一个指针总是指向队首的页面。

存在Belady异常现象，即缺页率随内存块增加而增加。

最近最少使用置换法(LRU)

思想：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。
理由：认为过去一段时间内未被访问过的页面，在最近的将来可能也不会被访问。

依据程序的局部性原理，利用过去的、已知的页面访问情况，预测将来的情况。

怎样确定每个页面最后的访问时间？

实现方法

• 计数器。
  要求在硬件上有一个64位的计数器C（给CPU增加一个计数器C），每条指令执行完后，C的值自动加1 。
  在每个页表项中，增加一个“使用时间”字段（时间戳）。每一次内存访问后，C的值就被复制到被访问页面的“使用时间”字段中。
  系统始终保留着每个页面最后被访问的“时间”，淘汰该时间值最小的页面，即最近最久未被使用的页面。
• 栈。
  • 用一个栈保留页号，每访问一个页面时，就把它从栈中取出，放入栈顶。要用具有首指针和尾指针的双向链把各个栈单元连起来。

优点：
是与OPT接近的算法，性能较好，应用较多。
缺点：
为确定最后访问以来所经历时间的顺序，通常需要硬件的支持，同时需要一定的软件开销。
作用：
实际应用中，使用的都是简单有效的LRU近似算法。即用软件模拟实现LRU。

三种基本置换算法的比较

理想情况：接近LRU的性能，开销又比较小。

页面分配策略

缺页率与什么有关？
页面置换算法
进程分得的内存块数目

内存块的分配

内存块的分配算法

• 等分法
• 等分内存块
  例：内存块为93，进程数为5

        每个进程分得18块，剩余3块
  

• 比例法
  • 设进程pi的地址空间大小为si，则总地址空间 S=∑si
    若可用块的总数是m，则分给进程pi的块数是ai ≈m . si /S
    例：内存块为62，进程P1的逻辑空间占20页，P2占10页。 P1分得41块，P2分得21块。
• 优先权法
• 根据进程的优先级按比例分配内存块。可加速高优先级进程的执行速度。

内存块的分配策略

• 固定分配策略：分配给进程的内存块数是固定的，且在最初装入时（即进程创建时）确定块数。
• 可变分配策略：允许分给进程的内存块数随进程的活动而改变

页面置换范围

• 全局置换：允许一个进程从全体存储块的集合中选取页面淘汰，尽管该块当前分配给其他进程，还是能强行占用。
• 局部置换：是每个进程只能从分给它的一组内存块中选择页面淘汰。

内存块的分配策略+页面置换范围

• 固定分配+局部置换
  • 主要问题：进程开始前要依据进程类型决定分配多少内存块。多了会影响并发水平，少了会使缺页率过高。
• 可变分配+局部置换
  • 局部置换，但在大尺度上进行可变分配。
• 可变分配+全局置换
  • 主要问题：置换策略的选择，选择哪个进程的页面被调出，较好的选择是页面缓冲算法。
• 不包括“固定分配+全局置换”

抖动

抖动：在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象为“抖动或颠簸（Thrashing）” 。

产生抖动的原因

• 页面淘汰算法不合理
• 分配给进程的内存块数太少

防止抖动的方法

• ① 采用局部置换策略
  一个进程出现抖动，它不能从其他进程那里获取内存块，不会引发其他进程出现抖动，使抖动局限于一个小范围内。
• ② 利用工作集策略防止抖动
• ③ 挂起某些进程
  当出现CPU利用率很低、而磁盘I/O非常繁忙时，可能因为多道程序度太高而造成抖动。挂起一个或几个进程，腾出内存空间供抖动进程使用。
• ④ 采用缺页频度法（Page Fault Frequency, PFF）
  抖动发生时缺页率会很高，通过控制缺页率可防止抖动。

规定一个缺页率，设置上限和下限。缺页率超出上限，就为进程分配内存块；低于下限，就从该进程的驻留集中取走一个内存块。通过直接测量和控制缺页率，避免抖动。

请求分段管理方式

请求分段的基本原理

在段式虚存系统中，一个进程的所有分段的副本都保存在外存上。当它运行时，先把当前运行的一段或几段装入内存，其他段仅在调用时才装入。

• 一般过程：当访问的段不在内存时，便产生缺段中断；操作系统接到中断信号后，进行相应处理，按类似于申请分区的方式，在内存中找一块足够大的分区，用于存放所需分段。

段表机制

• 

• 增补位：请求分段特有的字段，表示本段在运行过程中是否有动态增长。

• 外存基址：本段在外存的起止地址。

• 共享位：表示段的共享方式。

动态链接和链接中断处理

动态链接

• 采用段式虚存系统可以实现程序的动态链接。仅当用到某个分段时才对它进行链接，避免不必要的链接。
• 为了支持动态链接，需要附加间接编址和链接故障指示位两个硬件设施。

直接编址：指令中的地址就是所要存取数据的直接地址。

间接编址：指令中的地址不是所要存取数据的直接地址，而是间接地址——存放直接地址的地址，即它所指向的单元中存放所需数据的地址。

间接字：包括直接地址的字。

链接故障指示位：设在间接字中，用于表示所访问的段是否已链接上，0为链接上，1为没链接上。

链接中断处理：若相应指令采用间接字寻址时，发现链接故障指示位是1，则硬件产生链接中断，转向操作系统的链接故障处理程序去处理。

动态地址转换机构：若要访问的段不在内存，则由动态地址转换机构产生缺段中断，由操作系统进行相应的处理。

链接中断处理

Linux系统的存储管理

Linux的多级页表结构

Linux系统采用虚拟内存管理机制，使用交换和请求分页存储管理技术。

地址码采用32位，每个进程的虚拟存储空间可达4GB，Linux内核将其分成两部分：最高地址的1GB是系统空间，其余是用户空间。

Linux系统中页面大小为4KB。
采用三级页表的方式。

内存页的分配与释放

Linux系统采用位图和链表两种方式来管理内存页。

位图：利用一串二进制位值反映磁盘空间的分配情况，也称位向量（Bit Vector）法。

位示图的优点是在寻找第一个空闲块或几个连续的空闲块时相对简单有效。

• 每个盘块对应一个二进制位，1表示盘块空闲，0表示已分配。
• 设下列盘块是空闲的：2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, 27,…，则位示图向量是：

         0011110011111100011000000111…
  

• 第1个元素（项0）描述孤立出现的单个（20）内存页的信息，第2个元素描述以2个（21）连续内存页为一组的页组信息，依此类推，页组中内存页的数量按2的倍数递增。

• 位图

  • 例，某内存大小为1024KB，内存块大小为4KB，则可以用多少字节构成的位图来记录内存的使用情况？
    1024/4=256个内存块，需要256个二进制位的位图，8位一个字节，则256/8=32个字节。

• 链表：用于记录已分配的内存单元和空闲的内存单元。可采用双向链表将内存单元链接起来，加快查找和处理。

• 数组free_area的每一项描述某内存页组的使用状态信息（即由相邻空闲内存页构成的组）。

• 当分配内存页组时，如果系统中有足够的空闲内存页满足请求，分配程序首先在free_area数组中搜索等于要求数量的最小页组的信息，然后再对应的双向链表中查找。
  如果没有所需数量的内存页组，则继续查找下一个页组，找到的页组大于所需，则把页组分成两部分：满足请求的部分返回给调用者，剩余部分插入空闲页组队列中。

• 当释放一个页组时，页面释放程序会检查其上下，如有邻接的空闲页组，则合并，并修改有关队列。

第六章 文件系统

第七章 输入输出系统