一、操作系统概述

1.1 操作系统的定义与目标

定义：操作系统是控制管理计算机系统的硬软件，分配调度资源的系统软件。

目标：方便性，有效性（提高系统资源的利用率、提高系统的吞吐量），可扩充性，开放性。

1.2 操作系统的基本功能

1.统一管理计算机资源：处理器资源，IO设备资源，存储器资源，文件资源

2.实现了对计算机资源的抽象：IO设备管理软件提供读写接口，文件管理软件提供操作文件接口

3.提供了用户与计算机之间的接口：GUI图形用户界面，命令形式，系统调用形式

1.3 操作系统的特征（重点）

最基本的特征，互为存在条件：并发，共享；

1.并发

（1）并行：俩个或多个时间可以在同一个时刻发生，多核cpu可以实现并行

（2）并发：同一个时间间隔发生，每个程序交替执行

2.共享性：操作系统中的资源可以供多个并发的程序共同使用，称为资源共享。

• 互斥共享：当资源被资源占用时，其他想使用的程序只能等待。
• 同时访问：某种资源并发的被多个程序访问

虚拟和异步性的前提是具有并发性

3.虚拟性：表现为把一个物理实体转变为若干个逻辑实体

• 时分复用技术：资源在时间上进行复用，不同程序并发使用，多到程序使用计算机的硬件资源，提高资源的利用率
• 空分复用技术：用来实现虚拟磁盘（物理磁盘虚拟为逻辑磁盘，电脑上的C盘、D盘等）、虚拟内存（在逻辑上扩大程序的存储容量）等提高资源的利用率，提高编程效率。

4.异步性：在多道程序环境下，允许多个进程并发执行，但由于资源等因素的限制，使进程的执行以“停停走走”的方式运行，而且每个进程执行的情况（运行、暂停、速度、完成）也是未知的。

1.4操作系统的中断处理

中断机制的作用：为了在多道批处理系统中让用户进行交互；

中断的产生：

• 发生中断时，cpu立马切换到管态，开展管理工作（管态又叫特权态，系统态或者核心态，是操作系统管理的程序执行时，机器所处的状态）
• 发生中断后，当前运行的进程会暂停运行，由操作系统内核对中断进行处理
• 对于不同的中断信号，会进行不同的处理

中断的分类：

1.内中断（也叫异常、例外、陷入）------信号来源：CPU内部，与当前执行指令有关

2.外中断（中断）---------信号来源：cpu外部，与当前执行指令无关

1.5操作系统的发展与分类（重点）

1. 手工操作阶段：用户独占全机，人机速度矛盾导致资源利用率极低

2. 单道批处理

   引入脱机输入/输出技术（用外围机+磁带完成），并由监督程序负责控制作业的输入、输出

   主要优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升

   缺点：内存中仅仅能有一道程序运行，只有该程序运行结束之后才能调入下一道2程序。cpu有大量的时间是在空闲等待I/0完成，资源利用率依然很低

3. 多道批处理

   主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大。

   缺点：用户相应时间长，没有人机交互功能（用户提交自己的作业之后只能等待计算机处理完成，中间不能控制自己的作业执行，比如无法调试程序/无法在程序运行过程中输入一些参数）

4. 分时操作系统

   计算机以时间片为单位轮流为各个用户/作业服务，各个用户可以通过终端与计算机进行交互。

   主要优点：用户请求可以被及时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。

   主要缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环的为每个用户/作业服务一个时间片，不区分任务的紧急性

5. 实时操作系统

   在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。

   主要优点：能够响应一些紧急的任务某些紧急任务不需要时间片排队

1.6操作系统的主要功能（重点）

1. 处理机管理功能
2. 存储器管理功能
3. 设备管理功能
4. 文件管理功能
5. 接口管理功能

二、进程管理

2.1进程的定义

为什么需要进程：

1. 进程是系统进行资源分配和调度的基本单位
2. 进程作为程序独立运行的载体保障程序正常执行
3. 进程的存在使得操作系统资源的利用率大幅提升

什么是进程：进程是程序的执行过程，是系统进行资源分配和调度的一个独立单位。

进程控制块（PCB）：用于描述和控制进程运行的通用数据结构，记录进程当前状态和控制进程运行的全部信息，是进程存在的唯一标识

进程与线程：

• 线程：操作系统进行运行调度的最小单位。
• 进程：系统进行资源分配和调度的基本单位。

区别与联系：

1. 一个进程可以有一个或多个线程
2. 线程包含在进程之中，是进程中实际运行工作的单位
3. 进程的线程共享进程资源
4. 一个进程可以并发多个线程，每个线程执行不同的任务

2.2进程的五个特性

1. 动态性：进程具有生命周期。它由系统“创建”而诞生，被调度而执行，，因得不到资源而暂停，最后因被“撤销”而消亡
2. 并发性：不同进程的动作在时间上可以重叠，即系统内的多个进程是可以并发执行的。
3. 独立性：进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调动的基本单位。在今天既有进程又有线程的操作系统中，进程是一个能独立运行的基本单位，但不再是一个可执行的实体，系统独立运行的基本单位变成线程了。
4. 异步性：进程按各自独立的、不可预知的速度向前推进。不可预知的原因是并发执行。
5. 结构特性：从结构上看，每个进程都由程序段、数据段和一个PCB三部分组成。

2.3进程的基本状态与转换（重点）

2.3.1 进程的三种基本状态

1. 就绪（ready）状态：当进程已分配到 除CPU外的所有需要的资源，只要再获得处理机（CPU）的资源，便可以立即执行。
2. 执行（running）状态：：当进程已获得处理机资源，其资源正在处理机上执行。
3. 阻塞（Block）状态：正在执行的进程由于等待某个事件发生而无法执行时，便放弃处理机资源而处于阻塞状态。

2.3.2 五状态转换模型

在不少系统中，增加了两种基本状态：（1）新状态：进程刚被创建，并分配资源时；（2）终止状态：在进程结束后不会立即撤销进程，相应的进程会暂时留在系统中，以便收集进程的相关信息。

2.3.3 挂起操作和进程状态的转换

在许多系统中，为了满足系统和用户观察与分析进程的需要，加入挂起这一重要操作。

引入挂起的目的：

1. 终端用户的需要。
2. 父进程的需要
3. 负荷调节的需要
4. OS的需要

状态转换：活动就绪——>禁止就绪；活动阻塞——>禁止就绪；禁止就绪——>活动就绪；禁止阻塞——>活动阻塞

2.4 进程控制块PCB

2.4.1 PCB的定义

• PCB是系统为了描述和控制进程的运行而为进程定义的一种数据结构
• PCB是进程实体的一部分，是进程存在的唯一标志，也是操作系统中最重要的结构体类型的数据结构
• PCB中存放着操作系统所需要的用于描述进程当前情况以及控制进程运行的全部信息

2.4.2 PCB的作用

1. 作为独立运行基本单位的标志
2. 实现间断性运行方式
3. 提供进程管理所需的信息
4. 提供进程调度所需要的信息
5. 实现与其他进程的同步和通信

2.4.3 PCB中的信息

• 进程标识符：系统内用于标识一个进程的唯一编号
• 处理机状态
• 进程调度信息
• 进程控制信息

2.5 线程与进程的比较

从调度的基本单位、并发性、拥有资源等方面对线程和进程进行比较

1. 调度的基本单位

   在传统OS中，进程作为独立调度和分派的基本单位，能够独立运行，其在每次被调度时候，都需要进行上下文切换，开销较大。而在引入线程的OS中，已经把线程作为调度和分派的基本单位，因而线程是能够独立运行的基本单位。在同一个进程中，，线程的切换不会引起进程的切换，但进程的切换必然引起线程的切换。

2. 并发性

   不同的进程之间可以并发执行，而且在一个进程中的多个线程也可以并发执行，还允许一个进程中的所有线程可以并发执行。不同进程中的线程也可以并发执行。

3. 拥有资源

   进程可以拥有资源，并可以作为系统中拥有资源的一个基本单位，然而，线程几乎不拥有资源。

4. 独立性

   在同一个进程中的不同线程之间的独立性，要比不同进程之间的独立性差很多。

5. 系统开销

   创建进程的系统开销远大于创建线程

6. 支持多处理机系统

   对于传统进程，即单线程进程，不管有多少处理机，该进程只能运行在一个处理机上。但对于多线程进程，可以将一个进程中的多个线程分配到多个处理机上，并行运行，加快进程的完成。

三、处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标

1. 高级调度：作业调度，几个作业调入内存，为它们创建进程分配必要的资源（外存——>内存）
2. 低级调度：进程调度，调度的对象是进程或者内核级线程（内存——>处理机）
3. 中级调度：内存调度。暂时不能运行的进程调至外存等待（外存<——>内存）

处理机调度算法的共同目标：1、资源利用率 ：主要是CPU利用率 2、公平性：获得合理的CPU时间

3、平衡性：进程类型，计算型，输入/输出型 4、策略强制执行：系统的安全策略

批处理系统的目标：1、平均周转时间 2、系统吞吐量 3、处理机利用率

分时系统的目标：1、响应速度快 2、均衡性

实时系统的目标：1、截止时间 2、可预测性

3.2 作业与作业调度（重点）

作业：作业是一个比程序更为广泛的概念，他不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存。

作业调度的主要任务：根据作业控制块（JCB）中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后背队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。

3.2.1 先来先服务调度算法（FCFS)

该算法既可用于作业调度，也可用于进程调度，非抢占式。该算法每次调度都是从后背作业中选择一个或者多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。

先来先服务算法比较有利于长作业（进程），而不利于短作业（进程）

3.2.2 短作业优先调度算法(SJF)

为了追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间，每次调度时选择当前已到达且最短的作业/进程优先的到服务，所谓的最短也就是服务时间最短，即可用于作业调度也可用于进程调度。

采用短作业优先不论是平均周转时间还是平均带权周转时间都有明显的改善。所以短作业优先可以有效降低作业的平均等待时间，提高系统吞吐量。

缺点：

1. 该算法对长作业不利。可能产生长作业饥饿
2. 未考虑作业的紧迫程度，因此不能保证紧迫性作业（程序）会被及时处理
3. 由于作业（进程）的长短只是根据用户所提供的的估计执行时间定的，而用户有可能会有意或无意缩短其作业的估计运行时间，致使该算法不一定能做到短作业优先调度。

3.2.3 高优先权优先调度算法(HRRN)

当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。

1. 非抢占式优先权算法：系统一旦吧处理机分配给就绪队列中优先权最高的进程后，该进程就会一直执行下去，直至完成；
2. 抢占式优先权调度算法：在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。这种抢占式的更好地满足紧迫作业的要求。

确定进程优先权的依据：

• 进程类型。通常，系统进程(如接收进程、对换进程、磁盘I/O进程)的优先权高于一般用户进程的优先权。
• 进程对资源的需求。如进程的估计执行时间及内存需要量的多少，对这些要求少的进程应赋予较高的优先权。
• 用户要求。这是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。

高响应比优先调度算法：

在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。

由上式可以看出：
　　(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
　　(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。

(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。
　　简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销

3.2.4 基于时间片的轮转调度算法(RR)

算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到相应

原理：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如：100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。只用于进程调度（只有当作业放入内存建立了相应的进程后，才能被分配处理机时间片），抢占式。

3.2.5 多级反馈队列调度算法

(1)应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。

(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。

(3) 按队列优先级调度，仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程

3.3 实时调度（重点）

实现实时调度的基本条件

1. 提供必要的信息
   • 就绪时间
   • 开始时间和截止时间
   • 处理时间
   • 资源要求
   • 优先级
2. 系统处理能力强

3.3.1 最早截止时间优先算法

该算法是根据任务的开始截止时间来确定任务的优先级。截止时间越早，其优先级越高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序，具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时，总是选择就绪队列的第一个任务，即可用于抢占式调度，也可用于非抢占式调度。

• 非抢占式调度方式用于非周期实时任务

  如下图所示将该算法用于非抢占调度方式之例。该例中具有四个非周期任务，它们先后到达。系统首先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2，故系统在任务1后将调度任务3执行。在此期间又到达作业4，其开始截止时间仍是早于任务2的，故在任务3执行完后，系统又调度任务4执行，最后才调度任务2执行。

• 抢占式调度方式用于周期实时任务

  

为了说明通常的优先级调度不能适用于实时系统，该图特增加了第二和第三行。在第二行中假定任务A具有较高的优先级，所以在t=0 ms时，先调度A1执行，在A1完成后(t = 10 ms)才调度B1执行；在t = 20 ms时，调度A2执行；在t = 30 ms时，A2完成，又调度B1执行；在t = 40 ms时，调度A3执行；在t = 50 ms时，虽然A3已完成，但B1已错过了它的最后期限，这说明了利用通常的优先级调度已经失败。第三行与第二行类似，只是假定任务B具有较高的优先级

3.3.2 最低松弛度优先算法

该算法是根据任务紧急的程度，来确定任务的优先级。任务的紧急程度越高，为该任务所赋予的优先级就越高，使之优先执行。该算法主要用于抢占式调度方式。

假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。由此可得知任务A和B每次必须完成的时间分别为：A1、A2、A3、…和B1、B2、B3、…，见图3-8。为保证不遗漏任何一次截止时间，应采用最低松弛度优先的抢占调度策略

在刚开始时(t1 = 0)，A1必须在20 ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10 ms；B1必须在50 ms时完成，而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2 = 10 ms时，A2的松弛度可按下式算出：

A2的松弛度 = 必须完成时间 - 其本身的运行时间 - 当前时间
  　　= 40 ms-10 ms-10 ms = 20 ms

类似地，可算出B1的松弛度为15 ms，故调度程序应选择B1运行。在t3 = 30 ms时，A2的松弛度已减为0(即40 - 10 - 30)，而B1的松弛度为15 ms(即50 - 5 - 30)，于是调度程序应抢占B1的处理机而调度A2运行。在t4 = 40 ms时，A3的松弛度为10 ms(即60 - 10 - 40)，而B1的松弛度仅为5 ms(即50 - 5 - 40)，故又应重新调度B1执行。在t5 = 45 ms时，B1执行完成，而此时A3的松弛度已减为5 ms(即60 - 10 - 45)，而B2的松弛度为30 ms(即100 - 25 - 45)，于是又应调度A3执行。在t6 = 55 ms时，任务A尚未进入第4周期，而任务B已进入第2周期，故再调度B2执行。在t7 = 70 ms时，A4的松弛度已减至0 ms(即80 - 10 - 70)，而B2的松弛度为20 ms(即100 - 10 - 70)，故此时调度又应抢占B2的处理机而调度A4执行。图3-9示出了具有两个周期性实时任务的调度情况。

3.4 死锁概述

产生死锁的原因：

• 竞争资源。

• 进程间推进顺序非法。进程在运行过程中，请求（wait）和释放（signal）资源的顺序不当。

产生死锁的必要条件：

• 互斥条件

• 请求和保持条件

• 不剥夺条件

• 环路等待条件

处理死锁的基本方法：

• 预防死锁：去破坏产生死锁的四个必要条件中的一个或者几个条件。
• 避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态
• 检测死锁：允许系统发生死锁，然后检测出死锁的发生，并精确确定与死锁有关的进程和资源，采取措施将死锁清除掉
• 解除死锁：撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态。

预防死锁的方法：

1. 破坏“请求和保持”条件：所有进程在开始运行之前，都必须一次性申请所需的全部资源。

   优点：简单、易于实现且安全。

   缺点：资源严重浪费；进程延迟运行

2. 破坏“不可抢占”条件：一个进程申请其他资源而不能满足时，必须释放已有资源。

3. 破坏“环路等待”条件：所有资源按类型进行线性排队。严格依次分配资源。

3.5 银行家算法（重点）

文字太枯燥并且看不明白，去看个视频秒懂。

四、进程同步

4.1 进程同步概念

俩种形式的制约关系：在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使同处于一个系统中的诸进程之间可能存在着俩种形式的制约关系：

1. 间接相互制约关系。同处于一个系统中的进程，通常都共享着某种系统资源，如共享CPU、共享I/O设备等。所谓间接相互制约即源于这种资源共享，例如，有两个进程A和B，如果在A进程提出打印请求时，系统已将惟一的一台打印机分配给了进程B，则此时进程A只能阻塞；一旦进程B将打印机释放，则A进程才能由阻塞改为就绪状态。
2. 直接相互制约关系。这种制约主要源于进程间的合作。例如，有一输入进程A通过单缓冲向进程B提供数据。当该缓冲空时，计算进程因不能获得所需数据而阻塞，而当进程A数据输入输入缓冲区后，便将进程B唤醒；反之，当缓冲区已满时，进程A因不能再向缓冲区投放数据而阻塞，当进程B将缓冲区数据取走后便可唤醒A。

临界区：不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)。显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻该临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源**正被某进程访问，则本进程不能进入临界区。**因此，必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区(entry section)。相应地，在临界区后面也要加上一段称为退出区(exit section)的代码，用于将临界区正被访问的标志恢复为未被访问的标志。

4.2 信号量机制（重点）

4.2.1 整型信号量（了解即可）

最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。很长时间以来，这两个操作一直被分别称为P、V操作。

wait(S)和signal(S)是两个原子操作，因此，它们在执行时是不可中断的。亦即，当一个进程在修改某信号量时，没有其他进程可同时对该信号量进行修改。此外，在wait操作中，对S值的测试和做S:=S-1操作时都不可中断。

4.2.2 记录型信号量（重要）

在整型信号量机制中的wait操作，只要是信号量S≤0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制则是一种不存在“忙等”现象的进程同步机制。用记录型数据结构表表示的信号量。

相应地，wait(S)和signal(S)操作可描述为：

在记录型信号量机制中，S.value的初值表示系统中某类资源的数目，因而又称为资源信号量。对它的每次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，因此描述为S.value-- ；当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个，故S.value++操作表示资源数目加1。若加1后仍是S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。

4.2.3 AND型信号量

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait( Simultaneous wait)定义如下:

1
2
3
4
5
6
7
8
9
10
11
12

Swait(S1，S2，…，Sn)
　　if (Si>=1 and … and Sn>=1) then
　　　for i:=1 to n 　　　Si:=Si-1；
　　else
　　place the process in the waiting queue associated with the first Si found with Si<1，and set the program count of this process to the beginning of Swait operation 
　　endif

Ssignal(S1，S2，…，Sn)
 for i:=1 to n do　　Si:=Si+1；
Remove all the process waiting in the queue associated with Si into the ready queue.
endfor； 

4.3 信号量的应用

1. 利用信号量实现进程互斥

   为了使多个进程能够互斥地访问某个临界资源，只需为该资源设置一个互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。每个欲访问该临界资源的进程在进入临界区之前，都要先对mutex执行wait操作，若该资源此刻未被访问，本次wait操作必然成功，进程便可进入自己的临界区，这时若再有其他进程也欲进入自己的临界区，此时由于对mutex执行wait操作定会失败，因而该进程阻塞，从而保证了该临界资源能被互斥地访问。当访问临界资源的进程退出临界区后，又应对mutex执行signal操作，以便释放该临界资源。

   利用信号量实现进程互斥的进程可描述如下：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   Var mutex: =1； 　　begin 　　parbegin 　　　　process A: begin 　　　　　　　　　　　 repeat 　　　　　　　　　　　 　wait(mutex)； 　　　　　　　　　　　 　critical section 　　　　　　　　　　　 　signal(mutex)； 　　　　　　　　　　　 　remainder section 　　　　　　　　　　　 until false； 　　　　　　　　　　 end process B: begin repeat wait(mutex)； critical section signal(mutex)； remainder section until false； end parend

2. 利用信号量实现前驱关系

   如图：

   

   利用信号量实现此前驱图：

   1 2 3 4 5 6 7 8 9 10 11 12 13

   int a,b,c,d,e,f,g=0,0,0,0,0,0,0； 　　　　p1() { S1； signal(a)； signal(b) ； } 　　　　p2() {wait(a)； S2； signal(c)； signal(d)；} 　　　　p3() { wait(b)； S3； signal(e)；} 　　　　p4() {wait(c)； S4； signal(f)； } 　　　　p5() {wait(d)； S5； signal(g)； } 　　　　p6() {wait(e)； wait(f)； wait(g)； S6；} 　　cobegin p1()； p2()； p3()； p4()； p5()； p6()； 　　coend 注：控制变量可以根据有向边或节点数目定义； 节点入度为0进程可执行。

4.4 经典进程的同步问题

4.4.1 生产者-消费者问题

假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者—消费者问题可描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

int in=0，out=0；
array buffer[0，…，n-1]；
semaphore mutex=1，empty=n，full=0；
//生产者
void producer(){
	do{
		producer an item nextp；
　　　　　　　　　……　　
         wait(empty)； //申请空闲缓冲区
         wait(mutex)；//申请互斥信号量
         buffer[in]=nextp；
         in=(in+1) % n；
         signal(mutex)；//释放互斥信号量
         signal(full)；//释放满缓冲区

	}while(TRUE)
}
//消费者
void consumer(){
	do{
		wait(full)；//申请满缓冲区
        wait(mutex)；//申请互斥信号量
        nextc:=buffer(out)；
        out=(out+1) % n；
        signal(mutex)；//释放互斥信号量
        signal(empty)；//释放空闲缓冲区
		consumer the item in nextc；
		...

	}while(TRUE)
}

在生产者—消费者问题中应注意：
首先，在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现；
其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，wait(empty)在计算进程中，而signal(empty)则在消费进程中，计算进程若因执行wait(empty)而阻塞，则以后将由消费进程将它唤醒；
最后，在每个程序中的多个wait操作顺序不能颠倒，应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁

4.4.2 哲学家进餐问题

放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：

1
2
3
4
5
6
7
8
9
10
11
12

semaphore chopsticks[5]={1,1,1,1,1};
do{
	wait(chopstick[i]);
	wait(chopstick[(i+1)%5]);
	...
	//eat
	...
	signal(chopstick[i]);
	signal(chopstick[(i+1)%5])
	...
	think;
}while(TRUE);

在以上描述中，当哲学家饥饿时，总是先去拿他左边的筷子，即执行wait(chopstick[i])； 成功后，再去拿他右边的筷子，即执行wait(chopstick[(i+1)mod 5])；又成功后便可进餐。进餐完毕，又先放下他左边的筷子，然后再放右边的筷子。虽然，上述解法可保证不会有两个相邻的哲学家同时进餐，但有可能引起死锁。

假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0； 当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法：

1. 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
2. 仅当哲学家 的左右俩只筷子均可用时，才允许他拿起筷子进餐
3. 规定偶数号哲学家先拿他左边的筷子，然后再去那右边的筷子，而奇数号相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。

4.4.3 读者-写者问题

为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当Readcount=0，表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若Wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，也应该为它设置一个互斥信号量rmutex。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

读者—写者问题可描述如下:
　　Var rmutex，wmutex:=1,1；
　　　　Readcount=0；
　　Reader:  begin
　　　　　　　　repeat
　　　　　　　　　wait(rmutex)；
　　　　　　　　　if readcount==0 then wait(wmutex)；
　　　　　　　　　　Readcount:=Readcount+1；
　　　　　　　　　signal(rmutex)；

　　　　　　　 ………..perform read operation；

　　　　　　　　　wait(rmutex)；
　　　　　　　　　readcount:=readcount-1；
　　　　　　　　　if readcount==0 then signal(wmutex)；
　　　　　　　　　signal(rmutex)；
    writer:  begin
            repeat
             wait(wmutex)；
             perform write operation；
             signal(wmutex)；
            until false；
           end
        parend
      end 

请给出一个写者优先的“读者-写者”问题的算法描述。(多个写进程连续写)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Reader：begin
	repeat
	wait(S);
	wait(rmutex);
	if readcount==0 
		then wait(wmutex);
	readcount=readcount+1;
	signal(rmutex);
	signal(S);
	perform read operation;
    wait(rmutex);
    readcount=readcount-1;
    if readcount==0 
    then signal(wmutex); 	
    signal(rmutex);
    until false;
    end;
    
writer：begin
	repeat
	wait(mutex);
	if writecount==0 
		then wait(S);
	writecount=writecount+1;
	signal(mutex);
	wait(wmutex);
	perform write operation;
	signal(wmutex);	
	wait(mutex);
    writecount=writecount-1;
    if writecount==0 
    then signal(S); 	
    signal(mutex);
    until false;
    end;

五、存储器管理

5.1存储器的层次结构

对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。如图4-1所示，在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。其中，寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。

5.2 程序的装入和链接

将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：首先是要编译，由编译程序(Compiler)将用户源代码编译成若干个目标模块(Object Module)；其次是链接，由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module)；最后是装入，由装入程序(Loader)将装入模块装入内存。

5.2.1 三种装入方式

1. 绝对装入方式

   在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。

   绝对装入方式只能**将目标模块装入到内存中事先指定的位置。**在多道程序环境下，编译程序不可能预知所编译的目标模块应放在内存的何处，因此，绝对装入方式只适用于单道程序环境。

2. 可重定位装入方式

   在多道程序环境下，所得到的目标模块的起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。此时应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。

   可重定位装入方式可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境；但这种方式并不允许程序运行时在内存中移动位置。

3. 动态运行时装入方式

   因为，程序在内存中的移动，意味着它的物理位置发生了变化，这时必须对程序和数据的地址(是绝对地址)进行修改后方能运行。然而，实际情况是，在运行过程中它在内存中的位置可能经常要改变，此时就应采用动态运行时装入的方式。

5.2.2 程序的链接

根据链接时间的不同，可把链接分成如下三种：
　　(1) 静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。

(2) 装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。

(3) 运行时动态链接。这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。

5.3 连续分配方式

5.3.1 单一连续分配

这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。

5.3.2 固定分区分配

1. 分区大小相等

   所有的内存分区大小相等。其缺点是缺乏灵活性，即当程序太小时，会造成内存空间的浪费；当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。尽管如此，这种划分方式仍被用于利用一台计算机去控制多个相同对象的场合，因为这些对象所需的内存空间是大小相等的。例如，炉温群控系统，就是利用一台计算机去控制多台相同的冶炼炉。

2. 分区大小不等

   为了克服分区大小相等而缺乏灵活性的这个缺点，可把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。这样，便可根据程序的大小为之分配适当的分区。

   

5.3.3 动态分区分配（重点）

动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三个问题。

1. 分区分配中的数据结构

   • 空闲分区表：在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。

   • 空闲分区链：为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链

     

2. 分区分配算法（重点）

   • 首次适应算法：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。空闲分区以地址递增的次序排序，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个第一个空闲分区。

     优点：倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。

     缺点：低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。

   • 循环首次适应算法：由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。

   • 最佳适应算法：所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。空闲分区按照容量递增次序连接。每次分配内存时顺序查找空闲房分区链（或空闲分区表），找到大小能满足的第一个空闲分区。

     缺点：每次都选最小的分区进行分配，会留下越来越大，很小的，难以利用的内存块。因此这种方法会产生很多外部碎片。

   • 最坏适应算法：最坏适应分配算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业有利，同时最坏适应分配算法查找效率很高。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。但是该算法的缺点也是明显的，它会使存储器中缺乏大的空闲分区。

   • 快速适应算法：又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如2 KB、4 KB、8 KB等，对于其它大小的分区，如7 KB这样的空闲区，既可以放在8 KB的链表中，也可以放在一个特殊的空闲区链表中。

     优点：查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。

     缺点：分区归还主存时算法复杂，系统开销较大。以空间换时间，会造成空间浪费。

5.4 对换

在多道程序的环境下，一反面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但是它却占用大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况；另一方面，却又有着许多作业在外存上等待，因无内存而不能进入内存运行的情况。显然这对系统资源是一种严重的浪费，且使得系统吞吐量下降。为了解决这一问题，在系统中又增设了对换(也称交换)设施。所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换是提高内存利用率的有效措施。

对换分为整体对换（进程对换）和部分对换（页面对换或分段对换）：

• 对换是以整个进程为单位的，便称之为“整体对换”或“进程对换”。被广泛地应用于分时系统中，其目的是用来解决内存紧张问题，并可进一步提高内存的利用率。
• 对换是以“页”或“段”为单位进行的，则分别称之为“页面对换”或“分段对换”，又统称为“部分对换”。对换方法是实现后面要讲到的请求分页和请求分段式存储管理的基础，其目的是为了支持虚拟存储系统。

为了实现进程对换，系统必须能实现三方面的功能：对换空间的管理、进程的换出，以及进程的换入。

• 对换空间的管理：外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。由于通常的文件都是较长久地驻留在外存上，故对文件区管理的主要目标，是提高文件存储空间的利用率，为此，对文件区采取离散分配方式。进程在对换区中驻留的时间是短暂的，对换操作又较频繁，故对对换空间管理的主要目标，是提高进程换入和换出的速度。为此，采取的是连续分配方式，较少考虑外存中的碎片问题。
• 进程的换出：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。
• 进程的换入：系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中**换出时间最久(换出到磁盘上)**的进程作为换入进程，将之换入

5.5 分页存储管理方式（重点）

5.5.1 什么是分页存储

将内存空间分为一个个大小相等的分区（比如：每个分区4KB），每个分区就是一个页框（页框=页帧=内存块=物理块=物理页面），每个页框有一个编号。即**“页框号”（页框号=页帧号=内存块号=物理块号=物理页号），页框号从0开始。**

将进程 的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个**“页”或“页面”。每个页面也有一个编号。即“页号”，页号也是从0开始。**

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面 与内存的页框有一一对应的关系。

各个页面不必连续存放，可以放到不相邻的各个页框中。

5.5.2 页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。页表 通常存在 PCB（进程控制块）中。

• 一个进程对应一张页表
• 进程的每个页面对应一个页表项
• 每个页表项由“页号”和“块号”组成
• 页表记录进程页面和实际存放的内存块之间的映射关系

每个页表项占多少字节？

而页号是不占用字节的。

如何实现地址的转换？如果要访问逻辑地址A，则

1. 确定逻辑地址A对应的页号P
2. 找到P号页面在内存中的起始地址（需要查页表)
3. 确定逻辑地址A的页内偏移量w

逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W

页号=逻辑地址/页面长度（取除法的整数部分）

页内偏移量=逻辑地址%页面长度（取除法的余数部分）

5.5.3 逻辑地址结构

分页存储管理的逻辑地址结构如下所示：

5.5.4 基本地址变换机构（重点）

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的起始地址额页表长度存放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把他们放到页表寄存器中。

5.5.5 具有快表的地址变换机构

为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或称为“快表”。地址变换过程是：在CPU给出有效地址后，由地址变换机构自动地将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在块表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。

5.6 分段存储管理方式

5.6.1 分段存储管理方式的引入

好处：

1. 方便编程
2. 信息共享
3. 信息保护
4. 适应段的动态增长需求
5. 动态连接

5.6.2 分段系统的基本原理

在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段MAIN、子程序段X、数据段D及栈段S等

分段地址中的地址具有如下结构： 2^16 ×2^16

在该地址结构中，允许一个作业最长有 64 K个段，每个段的最大长度为64 KB。

5.6.3 段表

在分段式存储管理系统中，则是为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。为使程序能正常运行，亦即，能从物理内存中找出每个逻辑段所对应的位置，应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度

5.6.4 地址变换机构

5.7 分段和分页的主要区别（重点）

两者都采用离散分配方式，且都要通过地址映射机构来实现地址变换。但在概念上两者完全不同，主要表现在下述三个方面。

1. 页是信息的物理单位，分页是为了实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说分页仅仅是系统管理的需要而不是用户的需要。**段则是信息的逻辑单位，**分段得到目的是为了更好的满足用户的需求。
2. 页的大小固定且由系统来决定，而段的长度却不固定，决定于用户编写的程序。
3. 分页的作业地址空间是一维的。分段的作业地址空间时二维的，既需要给出段名，有需要给出段内地址。

六、虚拟存储器

6.1 虚拟存储器的定义和特征（重要）

定义：

• 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
• 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
• 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到内存

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存

虚拟内存有以下三个特征：

1. **多次性：**无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
2. **对换性：**在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入，换出。
3. **虚拟性：**从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际的容量。

6.2 请求分页存储管理方式

请求分页存储管理与基本分页存储管理的主要区别：

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。操作系统要提供请求调页功能，将缺失页面从外存调入内存。

若内存空间不足，由操作系统负责将内存中暂时用不到的信息换出内存。操作系统要提供页面置换功能，将暂时用不到的页面换出内存。

1.页表机制：

2.缺页中断机构

在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断作为中断，它们同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。但缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的区别，主要表现在下面两个方面：

• 在指令执行期间产生和处理中断信号
• 一条指令在执行期间，可能产生多次缺页中断。

3.地址变换机构

6.3 页面置换算法（重要）

6.3.1 最佳置换算法（OPT）

最佳置换算法：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

6.3.2 先进先出置换算法（FIFO）

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择对头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。

Balady异常——当为进程分配的物理块增大时，缺页次数不减反增现象。

缺点：**只有FIFO算法会产生Balady异常。**另外，FIFO虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能是最经常被访问因此，算法性能差。

6.3.3 最近最久未使用置换算法（LRU）

最近最久未使用置换算法（LRU）：每次淘汰的页面是最近最久未使用的页面。

实现方法：赋予每个页面对应的页表项中用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

在手动做题时，若需要淘汰页面，可以逆向检查此时在内存中几个页面。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。

6.3.4 时钟置换算法（CLOCK）

最佳置换算法性能最好，但无法实现；先进先出置换算法实现简单，但性能差；最近最久未使用置换算法性能好，，是最接近最佳置换算法，但是实现起来需要专门的硬件支持，算法开销大。时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法。

1. 简单的Clock置换算法

   当采用简单Clock算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。

2. 改进型Clock置换算法

   在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。在改进型Clock算法中，除须考虑页面的使用情况外，还须再增加一个因素，即置换代价，这样，选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。由访问位A和修改位M可以组合成下面四种类型的页面：

   ​ 1类(A=0，M=0)：表示该页最近既未被访问，又未被修改，是最佳淘汰页。
   　　2类(A=0，M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
   　　3类(A=1，M=0)：表示该页最近已被访问，但未被修改，该页有可能再被访问。
   　　4类(A=1，M=1)：表示该页最近已被访问且被修改，该页可能再被访问。

   (1) 从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。

   (2) 如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。
   (3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

6.3.5 各算法总结

七、输入输出系统

7.1 I/O系统的层次结构和模型

通常把I/O软件组织分成四个层次，如图所示：

1. 用户层软件：实现与用户交互的接口，用户可之后可直接调用用户层提供的、与I/O操作有关的库函数，对设备进行操作。
2. 设备独立性软件：负责实现与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等，同时为设备管理和数据提供必要的存储空间。
3. 设备驱动程序：与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序。
4. 中断处理程序：用户保存被中断进程的CPU环境，转入相应的中端程序进行处理，产后护理完会后再恢复被中断进程的现场后返回到被中断进程。

7.2 I/O设备和设备控制器

7.2.1 I/O设备的分类

I/O设备的类型繁多，从OS观点看，其重要的性能指标有: 设备使用特性、数据传输速率、数据的传输单位、设备共享属性等。因而可从不同角度对它们进行分类。

• 按使用特性分：1、存储设备 2、输入/输出设备
• 按传输速率分：1、低速设备 2、中速设备 3、高速设备
• 按信息交换分：1、块设备 2、字符设备
• 按设备的共享属性分：1、独占设备 2、共享设备 3、虚拟设备

7.2.2 设备与控制器之间的接口

设备并不是直接CPU进行通信，而是与设备控制器通信，因此，在I/O设备中应含有与设备控制器间的接口，因此，在I/O设备中应含有与设备控制器间的接口，在接口中有三种类型的信号，各对应一条信号线。

1. 数据型号线：用于设备与设备控制器之间传送数据信号
2. 控制信号线：作为由设备控制器向I/O设备发送控制信号时的通路
3. 状态信号线：用于传送指示设备与当前状态的信号。

7.2.3 设备控制器

基本功能：

• 接收和识别命令
• 数据交换
• 标识和报告设备的状态
• 地址识别
• 数据缓冲
• 差错控制

7.3 中断机构和中断处理程序

7.3.1 中断简介

1. 中断和陷入

   中断：CPU对I/O发出的中断信号的一种响应

   陷入：CPU内部事件引发的（上溢或下溢）

2. 中断向量表和中断优先级

   中断向量表：保存中断处理程序的入口地址

   中断优先级：键盘<打印机<磁盘

3. 多中断源的处理方式　　
   屏蔽中断、嵌套中断

7.3.2 中断处理

对于不同的设备，有不同的中断处理程序，该程序首先从设备控制器读出设备状态，以判别本次中断是正常完成中断，还是异常结束中断。若是前者，中断程序便进行结束处理；若还有命令，可再向控制器发送新的命令，进行新一轮的数据传送。若是异常结束中断，则根据发生异常的原因做相应的处理。

7.4 I/O控制方式

7.4.1 程序I/O方式

也称忙等待方式，即在处理机向控制器发出一条I/O指令启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志busy置为1，然后便不断地循环测试busy。当busy=1时，表示输入机尚未输完一个字(符)，处理机应继续对该标志进行测试，直至busy=0，表明输入机已将输入数据送入控制器的数据寄存器中。于是处理机将数据寄存器中的数据取出，送入内存指定单元中，这样便完成了一个字(符)的I/O。接着再去启动读下一个数据，并置busy=1。

7.4.2 中断驱动I/O控制方式

引入中断机构后，当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务。设备控制器于是按照该命令的要求去控制指定I/O设备。此时，CPU与I/O设备并行操作。例如，在输入时，当设备控制器收到CPU发来的读命令后，便去控制相应的输入设备读数据。一旦数据进入数据寄存器，控制器便通过控制线向CPU发送一中断信号，由CPU检查输入过程中是否出错，若无错，便向控制器发送取走数据的信号，然后再通过控制器及数据线将数据写入内存指定单元中。

7.4.3 直接存储器访问(DMA)I/O控制方式

虽然中断驱动I/O比程序I/O方式更有效，但须注意，它仍是以字(节)为单位进行I/O的，每当完成一个字(节)的I/O时，控制器便要向CPU请求一次中断。换言之，采用中断驱动I/O方式时的CPU是以字(节)为单位进行干预的。如果将这种方式用于块设备的I/O，显然是极其低效的。例如，为了从磁盘中读出1 KB的数据块，需要中断CPU 1K次。为了进一步减少CPU对I/O的干预而引入了直接存储器访问方式。

该方式的特点是：

(1) 数据传输的基本单位是数据块，即在CPU与I/O设备之间，每次传送至少一个数据块；

(2) 所传送的数据是从设备直接送入内存的，或者相反；
(3) 仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的。
　　可见，DMA方式较之中断驱动方式，又是成百倍地减少了CPU对I/O的干预，进一步提高了CPU与I/O设备的并行操作程度。

7.4.4 I/O通道控制方式

虽然DMA方式比起中断方式来已经显著地减少了CPU的干预，即已由以字(节)为单位的干预减少到以数据块为单位的干预，但CPU每发出一条I/O指令，也只能去读(或写)一个连续的数据块。而当我们需要一次去读多个数据块且将它们分别传送到不同的内存区域，或者相反时，则须由CPU分别发出多条I/O指令及进行多次中断处理才能完成。

I/O通道方式是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读(或写)为单位的干预减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。同时，又可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。例如，当CPU要完成一组相关的读(或写)操作及有关控制时，只需向I/O通道发送一条I/O指令，以给出其所要执行的通道程序的首址和要访问的I/O设备，通道接到该指令后，通过执行通道程序便可完成CPU指定的I/O任务。

四种控制方式的总结与比较

7.5 设备分配

7.5.1 设备分配中数据结构

1. 设备控制表（DCT）：系统为每一个设备都配置了一张设备控制表，用于记录本设备的情况。
2. 控制器控制表（COCT)：用于记录本控制器情况的控制器控制表
3. 通道控制表（CHCT）：每个通道都配有一张通道控制表
4. 系统设备表（SDT）：这是系统范围的数据结构，其中记录了系统中全部设备的情况。每个设备占一个表目，其中包括有设备类型、设备标识符、设备控制表及设备驱动程序的入口等项

7.5.2 分配设备

1. 首先根据I/O请求中的物理设备名，查找系统设备表(SDT)，从中找出该设备的DCT，再根据DCT中的设备状态字段，可知该设备是否正忙。若忙，便将请求I/O进程的PCB挂在设备队列上；否则，便按照一定的算法来计算本次设备分配的安全性。如果不会导致系统进入不安全状态，便将设备分配给请求进程；否则，仍将其PCB插入设备等待队列。
2. 在系统把设备分配给请求I/O的进程后，再到其DCT中找出与该设备连接的控制器的COCT，从COCT的状态字段中可知该控制器是否忙碌。若忙，便将请求I/O进程的PCB挂在该控制器的等待队列上；否则，便将该控制器分配给进程。
3. 在该COCT中又可找到与该控制器连接的通道的CHCT，再根据CHCT内的状态信息，可知该通道是否忙碌。若忙，便将请求I/O的进程挂在该通道的等待队列上；否则，将该通道分配给进程。只有在设备、 控制器和通道三者都分配成功时，这次的设备分配才算成功。然后，便可启动该I/O设备进行数据传送。

7.6 磁盘调度算法

7.6.1 先来先服务（FCFS）

根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。

7.6.2 最短寻道时间优先(SSTF）

其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。

7.6.3 基于扫描的磁盘调度算法

SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”(Starvation)现象。因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必然优先满足。对SSTF算法略加修改后所形成的SCAN算法，即可防止老进程出现“饥饿”现象。

1. SCAN算法

   该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。

   

2. 循环扫描(CSCAN)算法

   SCAN算法既能获得较好的寻道性能，又能防止“饥饿”现象，故被广泛用于大、中、小型机器和网络中的磁盘调度。但SCAN也存在这样的问题：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该进程必须等待，待磁头继续从里向外，然后再从外向里扫描完所有要访问的磁道后，才处理该进程的请求，致使该进程的请求被大大地推迟。

   为了减少这种延迟，CSCAN算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。