2024年1月4日 大三上操作系统课程复习

选择 简答 论述

1. U1 P6 分时操作系统 单道批操作系统 多道批操作系统

1. 单道批操作系统：为了实现对作业的连续处理，先将作业录入到磁带上，再由系统中的监督程序控制下，一个接一个地读取进内存并且完成作业，直至磁带上的作业全部完成。由于系统对作业的处理是成批进行，但内存中始终只有一道作业，因此得名单道批操作系统。

I/O操作：读取，输出操作（input/output operation）

2. 多道批操作系统：在单道批操作系统的基础上，如果执行中的作业在进行I/O操作，则CPU会转向运行另一个作业。该系统的目标是尽量让系统的各个部分都在工作中，花费很少时间切换作业，从而达到了系统各部件的并行工作。但是，系统周转时间长，并且不提供人机交互能力，用户既不能了解自己程序的运行情况，也不能控制计算机。

3. 分时操作系统：主机以很短的时间片为单位，将CPU分配给多个终端使用，直到所有作业都被运行完成。若某个作业在属于它的时间片内未被完成，则暂停该作业，轮换到下个作业，等待下一轮继续执行。直到所有作业都被完成。该系统优点是多用户联机，每个用户都感觉自己在独占计算机，并且能够及时响应用户的请求。缺点是不能用于某些对于外部输入信息在规定的时间内作出响应的情况。

2. U1 P13 操作系统的四个基本特征

1. 并发

是指两个以上的事件在同一时间间隔内发生。在操作系统中，并发指的是系统中同时存在多个运行中的程序，因此它应该具有处理和调度多个程序同时运行的能力。并发是通过分时来实现的，指一段时间内，宏观上有多个程序在同时运行，而每一时刻，单处理器环境下实际仅能有一道程序执行，故微观上这些程序还是在分时地交替执行。

并行：和并发相区别，并行是指多个事件在同一时刻发生。并发可以模拟并行的效果，但是不是完全并行。

进程：在系统中能独立运行，并作为资源分配的基本单位，是一个能独立运行的活动实体。

2. 共享

是指系统内的资源能被内存中的多个并发执行的程序共同使用，而不是被其中一个独占。

互斥共享方式：系统内的资源在同一时间段内只能被同一进程使用。其他进程想要使用，必须提出申请。

同时访问方式：系统内的资源在同一时间段内可以被多个进程使用，但是每个时刻只会有一个进程真正使用资源，类似分时操作系统。

3. 虚拟

是指操作系统通过某种方式将实体变为虚拟的，逻辑上的对应物的功能，典型就是各种I/O设备对应的资源。

4. 异步

在多道程序环境下，系统允许多个进程并发执行。但是由于资源是有限的，进程并不会直接进行到结束，而是走走停停得进行。因此，进程的运行速度是无法预知的，这就是进程的异步性。

3. U2 P32 前趋图（大题重点）

前趋图：用于描述程序执行先后顺序的图。它是一个有向无循环图，图中每个节点都可用来表示一个进程或程序段，结点间的有向边则表示两个结点之间存在的前趋关系。

前趋关系：如果p0和p1两个进程之间有p0 -> p1这样的前趋关系，则认为表示p1在开始之前，p0必须完成。

终止结点：没有后继的结点。

初始结点：没有前趋的结点。

重量：每个结点可以有自己的重量，一般可以指该结点进程所含有的程序量或者程序的执行时间。

能够并发执行的程序之间，不可以有前趋关系（如上图的I2，C1）。反之，没有前趋关系的程序之间，可以并发。

4. U2 P34 程序并发执行的几个特征

1. 间断性：由于并发执行的程序互相共享系统资源，以及可以为了同一个任务相互合作，因此这些并发执行的程序有可能形成相互制约的关系。如上面的前趋图，当Ci-1完成计算，并且Ii并没有完成时，Ci就无法继续，必须暂停运行。只有当Ii收到数据时，Ci才能继续。

2. 失去封闭性：由于并发执行中的多个程序共享系统资源，而这些资源的状态也会被这些程序所改变，因此对于它们其中之一来说，程序的执行环境一定会受到影响，也就失去了封闭性。

3. 不可再现性：由于并发执行的程序失去了封闭性，也因此失去了不可再现性。比如说运行在两个线程的程序同时访问一个正在改变的变量，那么取决于这两个线程的速度，每次运行的结果必然不同。

5. U2 P37进程的五种状态及转换原因（大题重点）

PCB：进程控制块，保证每个进程能够独立运行的数据结构。操作系统用一个PCB来描述进程的基本情况和活动过程，进而加以管理和控制。一般情况下，创建进程指的就是创建进程对应的PCB，撤销也是如此。

进程实体（一般意义上的进程）：由PCB，程序段和数据段组成的实体。

进程的三种基本状态：

就绪：指进程已经被分配到了除了CPU以外的所有资源，只要CPU到位马上就能运行。

执行：指进程从就绪状态后，已经被分配了CPU，处于正在运行的状态。

阻塞：指处于执行状态的进程，由于发生了某个事件（比如I/O请求）而暂时中断，无法继续执行的状态。此时操作系统会将处理机分配给别的处于就绪状态的进程。

其他两种状态：

创建：一个进程的创建，会先创建该进程对应的空白PCB并且写入信息，然后为其分配它所需要的资源，最后该进程进入就绪状态并进入就绪队列。如果出于某种原因，该进程所需资源不能被满足，创建仍未完成，也并不能被操作系统调度运行，此时该进程所处的状态就是创建状态。

终止：一个进程的终止，会先由操作系统进行善后处理，然后清空并销毁PCB，此后该进程的状态就是终止状态。处于终止状态的进程无法再次运行，但在操作系统中依然保留一个记录。

6. U2 P45 进程的四个创建步骤

1. 申请空白PCB：为一个新的进程申请一个唯一的数字标识符，并从PCB集合中索取一个空白PCB。
2. 为新进程分配所需资源：其资源一般由操作系统或者父进程分配。新进程也必须在创建之前声明其所需的资源量。
3. 初始化PCB：初始化标识信息（进程标识符，父进程标识符），初始化处理机状态信息（使程序计数器指向程序的入口地址，使栈指针指向栈顶），初始化处理机控制信息（进程状态改变为就绪状态，并且除非用户显式指定，设置进程优先级为最低优先级）
4. 将新进程插入进程就绪队列。

7. U2 P53 信号量：记录型信号量（大题重点）

信号量：一个变量，在操作系统中用以表示某种资源的数量。在其他多线程编程中，也用以表示一个进程或者线程的状态。

线程：进程中的一个执行单元。一个进程下可以有多个线程，与进程不同的是，同类的多个线程共享进程的堆和方法区资源，但每个线程有自己的程序计数器、虚拟机栈和本地方法栈，所以系统在产生一个线程，或是在各个线程之间作切换工作时，负担要比进程小得多，也正因为如此，线程也被称为轻量级进程。多个进程之间的线程也是互相不可见的。

临界资源：一次仅允许一个进程使用的共享资源，比如I/O。

临界区：进程中访问临界资源的代码段。

死等状态：进程在有限的时间内完全不能进入临界区，而一直在尝试进入，进入一种无结果的等待状态。

忙等状态：当有一个进程已经在临界区内，其他进程会通过信号量循环尝试进入临界区，直到信号量允许进程进入的等待状态。这个没有进入临界区的进程会一直在其执行状态中测试信号量。

有限等待：系统对要求进入临界区的进程，应保证在有限时间内它能够成功进入，以免进入死等状态。

让权等待：当进程发现自己不能进入自己的临界区时，应该立即释放处理机（退出执行状态），以免进入忙等状态。

一个记录型信号量，包括一个代表资源数目的整型变量和一个进程链表指针。

c
typedef struct {
	int value; // 可用资源量
	struct process_control_block *list; // 进程链表指针 存储等待资源的进程
} semaphore

相应的，它的wait和signal访问操作如下：

c
wait(semaphore *S) { // wait函数用于请求资源
	S->value--; // 信号量-1 表示当前进程将使用一个资源
	if (S->value < 0) block(S->list); // 如果信号量的值小于0 则阻塞当前进程 将其加入等待链表
}

signal(semaphore *S) { // signal函数用于释放资源
	S->value++; // 信号量+1 表示当前进程释放一个资源
	if (S>value <= 0) wakeup(S->list); // 如果信号量的值小于等于0 则表示等待链表中还有进程在阻塞 唤醒第一个在等待的进程
}

8. U2 P56 利用信号量实现进程的互斥

1. 为某一资源设置一个信号量，初值为1，取值范围为（-1，0，1）。
2. 其余进程在临界区上下，加入wait和signal函数，并且加入一个永不退出的循环，从而实现进程的互斥。

c
semaphore mutex = 1; // 信号量

ProcessA() {
	while(1) {
		wait(mutex);
		// 在这里插入临界区代码
		signal(mutex)；
		// 在这里插入剩余代码
	}
}

ProcessB() {
	while(1) {
		wait(mutex);
		// 在这里插入临界区代码
		signal(mutex)；
		// 在这里插入剩余代码
	}
}

wait和signal必须成对出现，缺少wait会导致系统不能保证对临界资源的互斥访问，缺少signal会导致临界资源永远得不到释放，从而使等待它的进程一直处于阻塞。

9. U2 P60 利用记录型信号量解决生产者-消费者问题（大题重点）

生产者-消费者问题：有一个仓库供消费者和生产者使用，消费者会从仓库中取走商品，而生产者会将生产好的商品放到仓库中。如何保证消费者不会到一个空的仓库中取商品的同时，生产者不会将一个商品放到一个满的仓库中？

假定这个“仓库”（缓冲池）有n个缓冲区，可以利用互斥信号量mutex（参考第7个）实现“生产者”和“消费者”（进程）对缓冲池的互斥使用，利用信号量empty和full表示缓冲池中空缓冲区和满缓冲区的数量。假定进程之间相互等效，只要缓冲池没满，进程就可以将“商品”（消息）送入缓冲池；同理，只要缓冲池没空，进程就可以从其中取走消息。

记录型信号量解决生产者-消费者代码实现如下：

c
int in = 0, out = 0; // 设定缓冲区的写入位置(in)和读取位置(out)
item buffer[n]; // 缓冲池本身 item类型只是指代那个消息的类型
// 这里缓冲池用的是数组 那么每个元素都是指代缓冲池中的缓冲区
semaphore mutex = 1, empty = n, full = 0; 三个信号量
void proceducer() { // 生产者
	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);
}

void main() {
	cobegin // 并发执行开始
		proceducer();
		consumer();
	coend // 并发执行结束
}

10. U2 P64 哲学家进餐问题

哲学家进餐问题：假设有五个笨比哲学家坐在一个圆桌周围，桌子上只有五个碗和五个筷子，他们要么会拿起筷子和饭碗吃饭，要么会坐着进入冥想。假设每位笨比哲学家只会先拿起他身旁的两只筷子，然后吃饭，不拿到两只筷子就不会吃饭，并且不会一直吃饭。那么如何设计一套规则，使得这五个笨比哲学家在遵守这套规则时，能一直持续“要么吃饭，要么冥想”的状态？

死锁：任意n个进程，每个进程都自己持有一些资源，但是仍然需求一些别的进程已经持有的资源。所有进程都在等待其他进程结束释放资源，从而进入互相等待，互相都无法结束的状态。

哲学家进餐问题，想要解决的就是死锁问题，即避免当五个哲学家每个人都持有一个筷子的时候，都在互相等其他人吃完饭放下筷子，最后谁都无法吃饭，从而无法回到冥想状态的情况。这是信号量无法解决的问题，信号量只能确定资源的访问是互斥的。

为了避免死锁 可以使用什么解决方法？

1. 至多只允许有四个笨比哲学家同时拿到他左边的筷子，最终能够保证起码一位笨比哲学家能够吃饭，并且吃完饭放下筷子，从而保证其他更多的笨比哲学家能够吃到饭。
2. 只有笨比哲学家两边的筷子同时可用时，才能拿起筷子。
3. 奇数笨比哲学家先拿左边的筷子，偶数笨比哲学家先拿右边的筷子，只有先拿到第一个筷子之后再去拿第二个筷子。这样将是0，1号哲学家竞争1号筷子，2，3号哲学家竞争2号筷子，最后总会有哲学家能够拿到两只筷子，从而吃饭。

11. U2 P75 线程和进程的区别 TCB

线程：进程中的一个执行单元。一个进程下可以有多个线程，与进程不同的是，同类的多个线程共享进程的堆和方法区资源，但每个线程有自己的程序计数器、虚拟机栈和本地方法栈，所以系统在产生一个线程，或是在各个线程之间作切换工作时，负担要比进程小得多，也正因为如此，线程也被称为轻量级进程。多个进程之间的线程也是互相不可见的。

线程和进程的区别：

1. 线程是操作系统的调度、分派的基本单位，而进程是操作系统分配资源的最小单位。（协程是用户自己调度的更加轻量级的线程，因此它不是操作系统层面上的基本单位）
2. 同一进程下的线程切换比不同进程切换要快得多，同时创建线程和撤销线程也要比创建、撤销进程快得多。
3. 线程的独立性要比进程低得多。
4. 线程自己只持有能够保证基本独立运行的资源，而进程所持有的资源比进程多得多。
5. 支持了多线程的进程可以运行在多处理机上，而单一进程只能运行在一个处理机上。

TCB：线程控制块，它存有以下信息：

1. 线程标识符
2. 一组寄存器，包括程序计数器，状态寄存器，通用寄存器
3. 线程运行状态
4. 优先级
5. 线程专有存储区
6. 信号屏蔽
7. 堆栈指针

12. U3 P86 平均周转时间（大题重点）

作业：用户在一次解决或是一个事务处理过程中要求计算机系统所做的工作的集合，它包括用户程序、所需要的数据集控制命令等。作业是由一系列有序的步骤组成的。在执行一个作业可能会运行多个不同的进程。在多道批处理系统中，作业时用户提交给系统的一想相对独立的工作。

周转时间：从一个作业被提交给系统开始，到该作业完成为止的这一段时间长度。它包括了作业在外存等待调度进入内存的时间、进程在就绪队列等着执行的时间，进程在处理机上执行的时间，进程等着I/O操作完成的时间，其中后三项可能发生多次。

平均周转时间：所有作业周转时间的平均值。

带权周转时间：一个作业的周转时间与操作系统为它提供服务的时间之比。

带权平均周转时间：所有作业的带权周转时间的平均值。

13. U3 P89 先来先服务算法 短作业优先算法（大题重点）

1. 先来先服务算法（FCFS）

顾名思义，先来先服务是指，每次完成一个作业或进程想要从后备作业队列或就绪进程队列寻找下一个执行的作业或进程时，默认按照先后次序进行调度，执行最先来的作业或进程。

2. 短作业优先算法（SJF）

顾名思义，短作业优先是指，每次完成一个作业或进程想要从后备作业队列或就绪进程队列寻找下一个执行的作业或进程时，会优先选择估计运行时间最短的作业或进程，优先运行。

短作业优先算法的缺点如下：

1. 必须预知作业或进程的运行时间。
2. 对长作业或进程极为不利，并且忽视了作业或进程的等待时间。
3. 该算法不考虑作业或进程的紧迫程度，不能保证紧迫性作业能及时运行。

14. U3 P107 死锁

死锁：如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。

不安全区域D具有以下特征：

1. 进入区域D，必然要请求资源1，资源2
2. 离开区域D，必然也要请求资源1，资源2

15. U3 P107 产生死锁的必要条件

1. 资源互斥：使用中和要请求的资源都是互斥的。
2. 请求和保持：进程在已经持有了一些资源的情况下，仍然在请求资源。
3. 不可抢占：进程已经获得的资源在未使用完成前，不能被抢占，只能由进程自己释放。
4. 循环等待：发生死锁时，必然存在一个...->进程->资源->进程->...的循环链。

16. U3 P110 安全状态 安全序列 银行家算法（无大题）

安全序列：如果操作系统能按某种进程推进顺序，从当前分配状况开始，为每个进程分配资源，直至满足该进程对资源的最大需求，从而使每个进程都可以顺利完成，那么这个推进顺序，就是安全序列。

安全状态：如果操作系统能够找到安全序列，那么该系统目前就处于安全状态；反之则处于不安全状态。

银行家算法：在每个进程进入系统前，必须声明自己对资源的最大需求。对于操作系统来说，每次有进程提出资源申请时，必须首先确定有无足够资源分配给该进程，之后计算分配资源后能不能找得到安全序列。如果找得到，就可以分配资源；反之，让进程等待。

17. U4 P129 分区 动态分区分配（图4-9）

分区：对内存中的用户空间进行分配，形成一个个独立的分区，每个分区装入一道作业。

动态分区分配：根据进程的实际需要动态地为其分配内存空间。

空闲分区表：操作系统中用于存储空闲分区的表，主要记录空闲分区的分区号，分区大小，分区始址，状态。

分区号	分区大小（KB）	分区始址（K）	状态
1	50	85	空闲
2	32	155	空闲
3	70	275	空闲

空闲链结构：每个分区的起始结束位置，都有指针指向下一个/上一个分区的结束/起始位置。同时，在起始和结束位置，都存储了该分区的长度和状态。状态为0时为空闲分区，状态为1时为已被分配进程。

分配内存：操作系统应该利用某种分配算法（见18），从空闲分区链/表中找到所需大小的分区。如果请求的分区大小和空闲分区的大小小于一定的值x，则认为该空闲分区多余部分太小，可不再切割，将整个分区分配给请求者。否则，从该空闲分区中按请求的大小划出一块内存空间进行分配，将其始址返回给请求者，其余空间仍留在空闲分区链/表中。

回收内存：如果要回收的分区和已经存在的空闲分区上或下或者上下都相邻，那么两/三个分区可以直接合并；如果要回收的分区不和空闲分区相邻，那么自己作为一个新的空闲分区插入空闲链的合适位置。

18. U4 P130 基于顺序搜索的动态分区分配算法

这些算法都是对空闲分区链上的空闲分区依次进行搜索，只是寻找分区的标准不同。

1. 首次适应算法（FF）：该算法要求空闲分区链以地址递增的次序链接，只要找得到大小符合要求的空闲分区就进行分配。这种分配方式的优点是倾向于优先使用低址部分的内存，而内存要求高的作业就可以使用不优先使用的高址部分的内存；但是缺点就是过于优先使用低址部分的内存，使得低址部分内存容易被分成过于小的分区，这不利于分区分配的同时，搜索的速度也会变慢。
2. 循环首次适应算法（NF）：在首次适应的算法的基础上，为了不再过度使用低址部分内存分区，每次开始查找空闲分区时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个满足要求的内存空间。该算法会使分区分布更加均匀，但是缺少空间大的空闲分区。
3. 最佳适应算法（BF）：该算法要求将所有的空闲分区按空间大小的顺序组成空闲分区链，每次开始寻找分区时，优先寻找能够满足要求的，但是空间最小的空闲分区。该算法有一个难以避免的缺点，即每次分配分区时，切割下来的分区必然是极小的，难以利用。
4. 最坏适应算法（WF）：该算法和最佳适应算法很像，但是寻找目标变成了优先寻找能够满足要求的，但是空间最大的空闲分区，从中切割一部分进行分配。该算法不易产生碎片，并且查找分区的效率高，对中、小作业有利。

19. U4 P140 分页存储的地址变换（图4-15）（大题重点）

为了解决连续分配容易出现大量空间碎片的问题，出现了“允许将一个进程直接分散地装入许多不相邻接地分区中”这种离散分配方式，包括分页存储，分段存储，段页式存储。

分页存储：它会将用户程序的地址空间分为若干个固定大小（通常为1KB）的区域，称为“页/页面”。相应的，内存空间也会被若干个物理块或者页框，大小与页相同。这样用户程序的任意一页都可以装入任意的页框中。

页表：因为用户程序是离散地装入内存，为了保证进程仍然能正常运行，操作系统定义了一张页面映像表，简称页表。用户程序可根据该表，在内存中找到相对应的页。

页号	块号	其他字段...（如是否只读等）
0	2
1	3
2	6
3	8
4	9
...	...

地址变换机构：通过页表，实现用户程序中，逻辑地址到物理地址的变换。该机构由存储着页表始址和页表长度的寄存器和内存中的实际页表组成。

寄存器：中央处理器内，用来暂存指令、数据和地址的电脑储存器。其存贮容量有限，但读写速度非常快，是所有存储器中最快的。

变换过程：

1. 当进程想要访问某个逻辑地址中的数据时，地址变换机构会将其该逻辑地址分为页号和页内地址两部分。
2. 如果页号超过页表长度，则引发越界错误，产生越界中断。
3. 如果页号没有超过页表长度，则得到该页号对应页在页表中的位置：页表始址+页号*页表项长度，获取到页表中存储着的页对应的物理地址。
4. 将获取到的页所对应的物理地址和页内地址组合起来，就得到了进程想要访问的数据在内存中的物理地址。

（页表项长度，指的是页表中，每存储一个页，所占有的内存空间长度）

20. U4 P145 分段存储（大题重点）

分段存储：它会将用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。内存空间分配时，以段为单位，这些段在内存中可以不相互邻接。

分段存储的逻辑地址分为段号和段内地址。

在该地址结构中，允许一个作业最长有64K（2^16 = 65536 = 64 * 1024）个段，每个段的最大长度为64KB（2^16 = 65536 = 64 * 1024）。（1K = 1024）

分段存储和分页存储很像，有段表，有地址变换机构，地址变换机构的运行方式大致相同，只是多加了一个段长度，并且检查段内地址是否超过段长度。

（上图物理地址应为8292）

21. U4 P150 段页式存储

该存储方式是分段式和分页式存储的结合，先分段，后分页。

参照分段式和分页式，段页式存储有段页表和地址变换机构。在采用该存储方式的系统中，用户程序所使用的逻辑地址包括了段号，段内页号，页内地址三部分。

22. U5 P154 局部性原理 虚拟存储器

局部性原理分为以下几部分：

1. 程序执行时，大部分是顺序执行。
2. 过程调用会使程序的执行轨迹从一部分区域转换到另一部分区域，但是该调用的深度一般不超过5。
3. 程序中存在许多循环结构，它们将被多次执行。
4. 程序中包括对数据结构的处理，这些处理一般都局限于很小的范围内。

因此，局部性原理体现在两个方面：

1. 时间局限性：如果一条指令/数据刚被执行/访问，则不久之后该指令/数据可能再次被执行/访问。（对应循环结构）
2. 空间局限性：一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址可能集中在一定的范围内。（对应顺序执行）

虚拟存储器：具有请求调入和置换的功能的，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外村容量之和所决定，运行速度接近内存，但每位的成本接近于外存。

虚拟存储器的三个特征：

1. 多次性：程序和数据不会再作业运行时一次性调入内存，而是允许被分成多次调入内存运行。
2. 对换性：一个作业中的程序和数据，无须在作业运行时一直留在内存中，而是允许在作业运行时，将需要的部分换入，z暂时不需要的部分换出。
3. 虚拟性：虚拟存储器能够在逻辑上扩充内存容量，使用户看到的内存容量远大于实际内存容量，因此可以在小的内存中运行大的作业，或者提高多道程序度。

23. U5 P174 缺页率 缺页中断 （大题重点）

请求分页系统是在分页式存储的基础上，加入了虚拟存储器形成的。它也有页表和地址变换机构，只是加入了利于换入换出的部分。

页表结构：

页号	物理块号	状态位P	访问字段A	修改位M	外存地址

状态位P：指示该页是否调入内存。 访问字段A：该页在过去一段时间内被访问了几次。 修改位M：该页在调入内存后是否被修改过。如果是，那么换出时需要重写该页到外存上；如果否，那么无需再换出，直接在需要换入别的页的时候覆盖该页即可。

地址变换结构：

缺页中断：在请求分页系统中，每当请求的页不在内存中时，就引发缺页中断。它和普通中断有两个不同点：

1. 在指令执行期间产生和处理中断信号。在指令请求别的不在内存的页时，系统直接处理缺页中断信号，调入所需要的页。
2. 一条指令可能在执行期间产生多次中断信号。比如说指令同时访问了多个不在内存中的页。就会产生多次中断信号。

缺页率：一个进程的运行过程中，引发缺页中断的次数比上总的页面访问次数，即为该进程在运行过程中的缺页率。

缺页率会受到以下四种因素的影响。如果：

1. 页面划分越大
2. 进程所分配的物理块数量越多
3. 页面置换算法越优秀
4. 程序编制的局部化程度越高

那么缺页率就越低。

缺页中断处理时间：被换出的页面被修改的概率 * 这种情况下的缺页中断处理时间 + 被换出的页面没被修改的概率 * 这种情况下的缺页中断处理时间。

24. U5 P163 置换算法（大题重点）

1. 最佳置换算法

   该算法倾向于将以后永远不使用或者未来最长的一段时间内不再使用的页换出。但是由于当前无法预知程序中哪一个页是未来最长时间内不再被访问的，所以该算法是无法实现的。但是由于该算法一般情况下是缺页率最低的，所以该算法可以在给定页面号引用串时，与其他算法进行对比，从而评价其他算法。 以上图举例，如果别的算法在给定的顺序中，页面置换次数越接近6次，就越优秀。

2. 先进先出置换算法（FIFO）

   该算法倾向于将最早进来的页面置换出去。

3. 最近最久未使用算法（LRU, Least Recently Used）

   该算法倾向于将内存中最近最久未使用的页面置换出去。即置换出去一个自上次被访问之后所经历时间最长的页面。

   比FIFO改善了一点，但不多，只能改善一点点。

25. U5 P170 抖动 产生抖动的原因 抖动的四个预防方法（大题重点）

抖动：随着系统中运行的进程越来越多，分配给每个进程的物理块就会越来越少，直接提高了进程的缺页率。缺页率越高，置换次数就越高，直到外存一直忙着处理置换页面，再也无法去完成其他任何有效的工作，从而导致处理机的利用率急剧下降到逼近0的现象。

工作集：在某一段时间内，进程实际所要访问的页面的集合。

预防抖动的四个方法：

1. 采取局部置换策略：如果在页面分配和置换策略中，采取的是可变分配方式，那么当某进程发生缺页时，可以限制它只能在分配给自己的内存空间内进行置换，不允许它从其它进程去获得新的物理块。这样可以将抖动造成的影响控制在一个小区域内。但是抖动已经产生的情况下，它还是会有非常多的调换页面的操作，还会长期占用外存读写，因此效果不是很好。
2. 把工作集算法融入到处理机调度中：在调度程序引入新的作业时，必须先检查每个进程在内存中的驻留页面是否足够多。如果是，则引入新的进程。如果不是，则应该首先为已经在内存中的进程分配物理块。
3. 利用L=S准则：L指缺页中断发生的平均时间，S指处理一个缺页中断的平均时间。如果L大于S，那么说明很少发生缺页，外存的能力并没有充分使用；如果L小于S，则说明外存会处理不过来发生的缺页中断。只有L=S时，外存和处理机才能都达到最大利用率。
4. 选择暂停的进程：既然抖动是因为进程多导致的每个进程分配的物理块少，那么暂停一些进程即可解决问题。

26. U6 P205 假脱机（Spooling）系统（大题重点）

1. 假脱机技术：

   假脱机技术是为了缓和高速CPU和低速I/O设备之间的矛盾，同时将一个I/O设备抽象为多个逻辑I/O设备以共享资源的。 假脱机技术是利用专门的外围控制机，先将I/O设备上的数据传到硬盘上，或者相反。这样当CPU需要数据时，就可以直接从硬盘上读取；当CPU需要输出信息时，也可以先输出到硬盘上，无需等待I/O设备就可以去执行下一个任务。外围控制机负责读取硬盘上CPU输出的数据传给I/O设备慢慢输出即可。 当操作系统引入多道程序技术后，外围控制机就可以抽象成一道程序进行控制即可。

2. 假脱机系统的构成：

   1. 输入井和输出井：对应上文的硬盘。它是指硬盘上专门开辟的，用于暂存数据的一块空间。数据在这里以文件的形式存在，所有要输入/输出的文件链接成为一个输入/输出队列。

   2. 输入缓冲区和输出缓冲区：在内存中，缓和磁盘和CPU之间速度差异用的

   3. 输入进程和输出进程：对应上文的外围控制机。输入进程会将用户输入的数据先存放到输入缓冲区，再放到输入井中。当CPU需要输入数据时，直接从输入井读取进内存。这个过程反过来，就是输出进程的工作：CPU到内存到输出井到输出缓冲区到输出设备。

   4. 井管理程序：控制作业和井之间的信息交换。当作业请求I/O设备时，由操作系统调用井管理程序，它会控制从s输入井中读取信息或将信息输出至输出井。

      

3. 假脱机系统的特点：

   1. 提高了I/O设备的速度。这里是相对于CPU来说的，CPU所操作的数据从来自低速I/O设备变成了来自速度更快的磁盘。
   2. 将独占的I/O设备改造为共享设备。在假脱机技术中，每当有进程请求I/O设备时，都会在缓冲区内为其分配一个空闲盘块和一张I/O请求表，而不是真的分配I/O设备给这个进程。
   3. 实现了虚拟设备功能。