操作系统复习【面试】

• 前言
• 推荐
• 操作系统复习
• • 第一章 操作系统引论 1
  • • 1.3 操作系统的基本特性 14
    • • 1.3.1 并发
      • 1.3.2 共享
      • 1.3.3 虚拟
      • 1.3.4 异步
    • 1.4 操作系统的主要功能 17
    • • 1.4.1 处理机管理功能
      • 1.4.2 存储器管理功能
      • 1.4.3 设备管理功能
      • 1.4.4 文件管理功能
      • 1.4.5 操作系统和用户之间的接口
  • 第二章 进程的描述与控制 35
  • • 2.2 进程的描述 46
    • • 2.2.1进程的定义和特征
      • 2.2.2 进程的基本状态及转换
      • 2.2.3 挂起操作和进程状态的转换
    • 2.4 进程同步 52
    • • 2.4.1 进程同步的基本概念
      • 2.4.2 硬件同步机制
      • 2.4.3 信号量机制
      • 2.4.5 管程机制
    • 2.6 进程的通信 73
    • • 2.6.1 进程通信的类型
      • 2.6.2消息传递通信的实现方式
    • 2.7 线程的基本概念 81
    • • 2.7.1 线程的引入
      • 2.7.2 线程和进程的比较
    • 2.7.3 线程的状态和线程控制块
  • 第三章 处理机调度与死锁 92
  • • 3.2 作业与作业调度 95
    • • 3.2.3 先来先服务(FCFS)和短作业优先(SJF)调度算法
      • 3.2.4 优先级调度算法和高相应比优先调度算法
    • 3.3 进程调度 98
    • • 3.3.2 轮转调度算法
      • 3.3.3 优先级调度算法
      • 3.3.4 多队列调度算法
      • 3.3.5 多级反馈队列(multileved feedback queue)调度算法
    • 3.5 死锁概述 112
    • • 3.5.2 计算机系统中的死锁
      • 3.5.3 死锁的定义、必要条件和处理方法
    • 3.6 预防死锁 116
    • • 3.6.1 破坏“请求和保持”条件
      • 3.6.2 破坏“不可抢占”条件
      • 3.6.3 破坏“循环等待”条件
    • 3.7 避免死锁 119
    • • 3.7.1 系统安全状态
      • 3.7.2 利用银行家算法避免死锁
    • 3.8.死锁的检测与解除
  • 第四章 存储器管理 129
  • • 4.3 连续分配存储管理方式135
    • • 4.3.4 基于顺序搜索的动态分区分配算法
      • 4.3.5 基于索引搜索的动态分区分配算法
    • 4.5 分页存储管理方式 147
    • 4.6 分段存储管理方式 155
  • 第五章 虚拟存储器 164
  • • 5.1 虚拟存储器概述 164
    • • 5.1.2虚拟存储器的定义和特征
    • 5.2 请求分页存储管理方式 168
    • • 5.2.2 请求分页中的内存分配
    • 5.3 页面置换算法 174
    • • 5.3.1 最佳置换算法和先进先出置换算法
      • 5.3.2 最近最久未使用和最少使用置换算法
      • 5.3.3 Clock 置换算法
      • 5.3.4 页面缓冲算法 PBA
    • 5.5 请求分段存储管理方式 185
  • 第六章 输入输出系统 191
  • • 6.4 设备驱动程序
    • 6.4.3 对I/O设备的控制方式
    • 6.8 磁盘存储器的性能与调度 230
    • • 6.8.2 早期的磁盘调度算法
      • 6.8.3 基于扫描的磁盘调度算法
  • 第七章 文件管理 237
  • • 7.2 文件的逻辑结构
    • • 7.2.1 文件逻辑结构的类型
      • 7.2.2 顺序文件
      • 7.2.3 记录寻址
      • 7.2.4 索引文件
      • 7.2.5 索引顺序文件
      • 7.2.6 直接文件和哈希文件
    • 7.3 文件目录
    • • 7.3.1文件控制块和索引结点
      • 7.3.2 简单的 目录结构
      • 7.3.3 多级目录结构(树型目录)
      • 7.3.4 目录查询技术
  • 第八章 磁盘存储器的管理 268
  • • 8.1 外存的组织方式
    • • 8.1.1 连续组织方式
      • 8.1.2 链接组织方式
      • 8.1.3 FAT技术
      • 8.1.4 NTFS的文件组织方式
      • 8.1.5 索引组织方式
    • 8.2 文件存储空间的管理
    • • 8.2.1 空闲表法和空闲链表法
      • 8.2.2 位示图
      • 8.2.3 成组链接法
    • 8.3 提高磁盘I/O速度的途径
    • • 8.3.1 磁盘高速缓存(Disk Cache)
      • 8.3.2 提高磁盘I/O速度的其他方法
      • 8.3.3 磁盘冗余阵列
  • 第九章 操作系统接口 298
  • • 9.4 系统调用的概念和类型 315
    • • 9.4.1 系统调用的基本概念
• 最后

前言

2022-11-20 17:03:25

以下内容源自计算机操作系统（第四版）
仅供学习交流使用

推荐

计算机操作系统（第四版）

操作系统复习

第一章 操作系统引论 1

1.3 操作系统的基本特性 14

1.3.1 并发

1.并发与并行

并行：指两个或多个事件在同一时刻发生
并发：指两个或多个事件在同一时间间隔内发生
宏观上，有多个程序在同时运行
微观上，分时交替运行

2.引入进程

1.3.2 共享

1. 互斥共享方式

2. 同时访问方式

1.3.3 虚拟

1. 时分复用技术

2. 空分复用技术

1.3.4 异步

1.4 操作系统的主要功能 17

引入OS的主要目的是：
为多道程序的运行提供良好的运行环境，以保证多道程序能有条不紊地、高效地运行
能最大程度地提高系统中各种资源的利用率
方便用户使用

基本功能：
处理机管理
存储器管理
设备管理
文件管理
为了方便用户使用OS，还需向用户提供方便的用户接口。

1.4.1 处理机管理功能

主要功能：
创建和撤销进程
对进程进行协调
实现进程之间的信息交换
按照一定算法把处理机分配给进程

1.进程控制
多道程序环境下，作业并发执行 ----- 必须为每道作业创建一个或多个进程，并为之分配资源

当进程运行结束时 ---- 立即撤销该进程 ---- 以便及时回收该进程所占用的各类资源，供其它进程使用

进程控制的主要功能： 为作业创建进程、撤销已结束的进程， 以及控制进程在运行过程中的状态转换

2.进程同步
进程同步的主要任务是对多个进程（含线程）的运行进行协调 ----- 使多个进程能有条不絮地运行

常用的协调方式有两种：

进程互斥方式 ---- 对临界资源访问时，应采用互斥方式 ----- 每一个临界资源配置一把锁W
进程同步方式 ---- 在相互合作去完成共同任务的诸进程间，由同步机构对它们的执行次序加以协调 ---- 信号量机制

3.进程通信
当有一组相互合作的进程去完成一个共同任务时，在它们之间往往需要交换信息。

进程通信的任务是实现相互合作的进程之间的信息交换。

当相互合作的进程处于同一计算机系统时，通常在它们之间采用直接通信方式，即由源进程利用发送命令直接将信息挂到目标进程的消息队列上，以后由目标进程利用接收命令从其消息队列中取出信息。

4.调度
调度包括作业调度和进程调度两步。

作业调度： 后备队列 ----- 一定算法 ----- 选择若干个作业 ----- 分配运行所需资源 ----- 调入内存 ---- 建立进程 ---- 使成为就绪进程并插入就绪队列

进程调度： 进程就绪队列 ---- 一定算法 ---- 选一个进程 ----- 分配处理机 ---- 设置运行现场，投入执行

1.4.2 存储器管理功能

主要任务：
为多道程序的运行提供良好环境
提高存储器利用率
方便用户使用
逻辑上扩充内存

主要功能：
内存分配与回收
内存保护
地址映射
内存扩充

1.内存分配

主要任务：
1） 为每道程序分配内存空间，使其各得其所
2） 提高存储器利用率，尽量减少不可用的内存空间（碎片）
3） 允许正在运行的程序申请附加的内存空间，以适应程序和数据动态增长的需要。

实现内存分配时，有两种方式：
1） 静态分配方式。 每个作业的内存空间是在作业装入时确定的，在作业装入后的整个运行期间不允许该作业再申请新的内存空间，也不允许作业在内存中“移动”。

2） 动态分配方式。 每个作业要求的基本内存空间虽然也是在装入时确定，但允许作业在运行过程中继续申请新的附加内存空间，以适应程序和数据的动态增长，也允许作业在内存中“移动”。

2.内存保护

主要任务：
1） 确保每道用户程序都仅在自己的内存空间内运行，彼此互不干扰
2） 绝不允许用户程序访问操作系统的程序和数据，也不允许用户程序转移到非共享的其他用户程序中去执行

为确保每道程序都只在自己的内存区中运行 ---- 设置内存保护机制
一种比较简单的内存保护机制是设置两个界限寄存器，分别用于存放正在执行程序的上界和下界。
在程序运行时，系统须对每条指令所要访问的地址进行检查，如果发生越界，便发出越界中断请求，以停止程序的执行。

3.地址映射

在多道程序环境下，每道程序经编译和链接后所形成的可装入程序其地址都是从开始的（逻辑地址），各程序的地址空间的逻辑地址与其在内存空间中的物理地址并不相一致。

地址映射：将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址（在硬件的支持下完成）

4.内存扩充

借助虚拟存储技术，从逻辑上扩充内存容量。

为实现扩充，系统必须设置内存扩充机制（包含少量硬件），实现下述功能：
1） 请求调入功能，系统允许在仅装入部分用户程序和数据的情况下，便能启动该程序运行。在程序运行过程中，若发现要继续运行时所需的程序和数据尚未装入内存，可向OS发出请求，由OS从磁盘中将所需部分调入内存。

2）置换功能，若发现在内存中已无足够的空间来装入需要调入的程序和数据时，系统应能将内存的一部分暂时不用的程序和数据调至硬盘上，以腾出内存空间，然后将所需部分装入内存。

1.4.3 设备管理功能

1.4.4 文件管理功能

1.4.5 操作系统和用户之间的接口

第二章 进程的描述与控制 35

2.2 进程的描述 46

什么是进程 进程和程序 进程的状态

2.2.1进程的定义和特征

1. 进程的定义
程序的并发执行 —— 间断性 + 失去封闭性 + 不可再现性 ——决定了通常的程序是不能参与并发执行的

为了能使程序并发执行，并且可以对并发执行的程序加以控制和描述 —— 进程

为了使参与并发执行的每个程序（含数据）都能独立地运行，在操作系统中必须为之配置一个专门的数据结构，称为进程控制块（PCB，Process Control Block）。

系统利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程。

进程实体（进程映像） = 程序段 + 相关的数据段 + PCB

一般情况下，把进程实体就简称为进程；创建进程，实质上是创建进程实体中的PCB；撤销进程，实质上是撤销进程实体中的PCB。

进程的定义：
1） 进程是程序的一次执行
2） 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
3） 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

一个比喻

我们写好的⼀⾏⾏代码，为了让其⼯作起来，我们还得把它送进城（进程）⾥，那既然进了城
⾥，那肯定不能胡作⾮为了。城⾥⼈有城⾥⼈的规矩，城中有个专⻔管辖你们的城管（操作系
统），⼈家让你休息就休息，让你⼯作就⼯作，毕竟摊位不多，每个⼈都要占这个摊位来⼯作，
城⾥要⼯作的⼈多着去了。所以城管为了公平起⻅，它使⽤⼀种策略（调度）⽅式，给每个⼈
⼀个固定的⼯作时间（时间⽚），时间到了就会通知你去休息⽽换另外⼀个⼈上场⼯作。
另外，在休息时候你也不能偷懒，要记住⼯作到哪了，不然下次到你⼯作了，你忘记⼯作到哪
了，那还怎么继续？有的⼈，可能还进⼊了县城（线程）⼯作，这⾥相对轻松⼀些，在休息的
时候，要记住的东⻄相对较少，⽽且还能共享城⾥的资源。

2. 进程特征

进程和程序是两个截然不同的概念，除了进程具有程序所没有的PCB结构外，还具有下面一些特征：
1） 动态性：
进程的实质是进程实体的执行过程
它由创建而产生，由调度而执行，由撤销而消亡
进程实体有一定的生命期，而程序则只是一组有序指令的集合，并存在于某种介质上，其本身不具有活动的含义，因而是静态的。

2） 并发性：
多个程序实体同存在于内存中，且能在一段时间内同时运行。

3） 独立性：
进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。
凡未建立PCB的程序都不能作为一个独立的单位参与运行。

4） 异步性：
进程是按照异步方式运行的，即按各自独立的、不可预知的速度向前推进。正是源于此因，才导致了传统意义上的程序若参与并发执行，会产生其结果的不可再现性。为使进程在并发运行时虽具有异步性，但仍能保证进程并发执行的结果是可再现的，在OS中引入了进程的概念，并且配置相应的进程同步机制。

2.2.2 进程的基本状态及转换

1. 进程三种基本状态

三种基本状态：
1）就绪（Ready）状态： 处于准备好运行的状态，即进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。

2）执行（Running）状态： 已获得CPU，其程序正在执行的状态

3）阻塞（Block）状态： 正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行时的状态。OS会把处理机分配给另一个就绪进程，而让受阻进程处于暂停状态。

2. 三种基本状态的转换

3. 创建状态和终止状态

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

2.4 进程同步 52

进程同步的方法

为保证多个进程能有条不紊低运行，在多道程序系统中，必须引入进程同步机制——硬件同步机制、信号量机制、管程机制

2.4.1 进程同步的基本概念

主要任务：对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。

1. 两种形式的制约

两种形式的制约 —— 对于同处于一个系统中的多个进程

1）间接相互制约关系——互斥

2）直接相互制约关系——同步

2.临界资源

许多硬件资源如打印机、磁带机等，都属于临界资源，诸进程间应采取互斥方式，实现对这种资源的共享访问。

3. 临界区
临界区 —— 每个进程中访问临界资源的那段代码

4. 同步机制四条准则
同步机制四条准则：
空闲让进
忙则等待
有限等待
让权等待

2.4.2 硬件同步机制

1. 关中断
关中断 —— 最简单的方法之一
进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断 —— 计算机系统不响应中断，保证锁测试和关锁操作的连续性和完整性

缺点：
1）滥用关中断权力可能导致严重后果
2）关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力
3）关中断方法也不适用于多CPU系统，因为在一个处理器上关中断并不能防止进程在其他处理器上执行相同的临界段代码

2. 利用 Test-and-Set指令实现互斥

利用 Test-and-Set指令实现互斥 —— 硬件指令 —— 一条原语

boolean TS(boolean *lock)
{boolean old;old = *lock;*lock = TRUE;       //TRUE表示资源正被使用，FLASE表示资源空闲return old;
}

用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock，表示该资源的状态，初始值为FALSE，表示资源空闲。

在进入临界区之前，首先用TS指令测试lock，如果值为FALSE，则表示没有进程在临界区内，可以进入，并将lock置为TRUE，等效于关闭了临界资源，使任何进程都不能进入临界区。

do{while TS(&lock);critical section;   // 临界区lock = FALSE;remainder section;
}while(TRUE);

3. 利用Swap指令实现进程互斥
利用Swap指令实现进程互斥 —— 对换指令 —— 用于交换两个字的内容
用对换指令可以简单有效地实现互斥，方法是为每个临界资源设置一个全局的布尔变量lock，其初值为false，在每个进程中再利用一个全局布尔变量key。

do{key = TRUE;do{swap(&lock,&key);}while(key != FALSE);临界区操作;lock = FALSE;剩余区;
}while(TRUE);

2.4.3 信号量机制

整型信号量 —— 记录型信号量 —— “信号量集”机制

1. 整型信号量

整型量S —— 表示资源数目（除初始化外，仅能通过P、V操作）
wait(S)、signal(S) —— 两个标准的原子操作，分别称为P、V操作

wait(S){while(S <= 0);    /*do no-op*/  即什么都不做S--;
}signal(S){S++;
}

P、V操作是两个原子操作，因此在执行时不可中断，亦即，当一个进程在修改某信号量时，没有其他进程可同时对该信号量进行修改。

整型信号量中的wait操作，只要是信号量S<=0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。

2. 记录型信号量

记录型信号量 —— 一种不存在“忙等”现象的进程同步机制
为了防止采取“让权等待”的策略后，会出现的多个进程等待访问同一临界资源的情况，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针list，用于链接上述的所有等待进程。记录型信号量是由于采用了记录型数据结构而得名的。

//数据结构
typedef struct{int value;struct process_control_block *list;
}semaphore;wait(semaphore S){S->value--;if(S->value < 0) block(S->list);   
}signal(semaphoree S){S->value++;if(S->value <= 0) wakeup(S->list);  //value <= 0 说明还有等待进程 

wait()中当S-value < 0时，进程调用block原语进行自我阻塞，放弃处理机，并插入到信号量链表S->list中，此时S->value的绝对值表示在该信号量链表中已阻塞进程的数目。

signal()中当释放一个资源后S->value <= 0，则表示在该信号量链表中仍有等待资源的进程被阻塞，应调用wakeup原语，将S->list链表中第一个等待进程唤醒。

如果S->value初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。

3. AND型信号量
AND信号量 —— 一个进程往往需要获得两个或更多的共享资源

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给它。
也就是说，对若干个临界资源的分配采取原子操作方式：要么把它所请求的资源全部分配给进程，要么一个也不分配。

Swait(S1,S2,...,Sn)
{while(TRUE){if(S1>=1 && ... && Sn>=1){for(i=1; i<=n; i++) Si--;break;}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(将此进程放到第一个Si<1的等待队列，并将程序指针指向该进程的Swait操作开始处)}}
}Ssignal()
{while(TRUE){for(i=1; i<=n; i++){Si++;Remove all the process waiting in the queue associatedwith Si into the ready queue(将所有与Si相关的等待队列中的进程移动到准备队列)}
}		

4. 信号量集
前面所述的记录型信号量机制中，wait(S) 和 signal(S)操作仅能对信号量施以加1或减1操作，意味着每次只能对某类临界资源进行一个单位的申请或释放。

如果一次需要N个资源，便要进行N次wait操作，这显然是低效的而且会增加死锁的概率。此外，在有些情况下，为确保系统的安全性，当所申请某类资源数量低于某一下限值时，还必须进行管制，不予以分配。

因此，当进程申请某类临界资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配。

可以对AND信号量机制加以扩充，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放。

进程对信号量Si的测试值不再是1，而是该资源的分配下限ti，要求Si > ti，否则不予以分配。一旦允许分配，进程对该资源的需求值为di。

Swait(S1,t1,d1,…,Sn,tn,dn)；
（将上述比较改成Si > ti ； 资源分配改成 Si = Si - di）
Ssignal(S1,d1,…,Sn,dn)
(将上述资源的释放改成Si = Si + di)

一般“信号量集”还有以下几种特殊情况：

1）Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予以分配。

2）Swait(S,1,1)。
S>1 —— 一般的记录型信号量
S=1 —— 互斥信号量

3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S>=1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

2.4.5 管程机制

2.6 进程的通信 73

进程通信是指进程之间的信息交换。

进程的互斥与同步——低级进程通信

2.6.1 进程通信的类型

高级通信机制可归纳为四类：
共享存储器系统
消息传递系统
管道通信系统
客户机—服务器系统

1.共享存储器系统
Shared-Memory System
两种类型：

2. 管道（pipe）通信系统
管道（pipe）通信系统
管道 —— 指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。

向管道提供输入的发送进程（写进程）以字符流形式将大量的数据送入管道；而接收管道输出的接收进程（读进程）则从管道中接收数据。
这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其他操作系统中。

为了协调双方的通信，管道机制必须提供以下三方面的协调能力：
1）互斥，当一个进程正在对pipe执行读/写操作时，其他（另一个）进程必须等待。
2）同步，当写（输入）进程把一定数据写入pipe，便去睡眠等待，直到读（输出）进程取走数据后再把它唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后才将之唤醒。
3）确定对方是否存在，只有确定了对方已存在时才能进行通信。
3. 消息传递系统 Message passing system —— 高级通信方式
在此机制中，进程不必借助任何共享存储区或数据结构，而是以格式化的消息为单位，将通信的数据封装在消息中，并利用操作系统提供的一组通信命令（原语），在进程间进行消息传递，完成数据间的数据交换。

该方式隐藏了通信实现细节，使通信过程对用户透明化，降低了通信程序设计的复杂性和错误率，成为当前应用最为广泛的一类进程通信间通信的机制。
例如：计算机网络中的报文；微内核操作系统中的微内核与服务器的通信；
这机制很好地支持多处理机系统、分布式系统和计算机网络，因此成为这些领域最主要的通信工具。

根据实现方式不同，分成两类：

4. 客户机—服务器系统 client-Server system
客户机—服务器系统 client-Server system
客户机-服务器系统的通信机制，在网络环境的各种应用领域已成为当前主流的通信实现机制，其主要的实现方法分为三类：
套接字、远程过程调用和远程方法调用

套接字 —— 一个通信标识类型的数据结构，包含了通信目的的地址、通信使用的端口号、通信网络的传输层协议、进程所在的网络地址，以及针对客户或服务器程序提供的不同系统调用（或API函数）等，是进程通信和网络通信的基本构件。

套接字优势：不仅适用于同一台计算机内部的进程通信，也适用于网络环境中不同计算机间的进程通信。由于每个套接字拥有唯一的套接字号，这样系统中所有的连接都持有唯一的一对套接字及端口连接，对于来自不同应用程序进程或网络连接的通信，能够方便地加以区分，确保了通信双方之间逻辑链路的唯一性，便于实现数据传输的并发服务，而隐藏了通信设施及实现细节，采用统一的接口进行处理。

远程过程调用和远程方法调用
远程过程调用RPC（Remote Process Call） —— 一个通信协议，用于通过网络连接的系统。该协议允许运行于一台主机系统上的进程调用另一台主机系统上的进程

2.6.2消息传递通信的实现方式

消息传递通信的实现方式
1. 直接消息传递系统
直接消息传递系统—— 利用OS所提供的发送命令（原语）

直接通信原语
1）对称寻址方式 —— 要求发送进程和接收进程都必须以显式方式提供对方的标识符。
系统提供以下两条通信命令：
send(receiver,message);
receive(sender,message);

不足：一旦改变进程的名称，则可能需要检查所有其他进程的定义，有关对该进程旧名称的所有引用都必须查找到，以便将其修改为新名称，显然，这样的方式不利于实现进程定义的模块化。

2）非对称寻址方式 —— 接收进程可能需要与多个发送进程通信，无法事先指定发送进程。因此，在接受进程的原语中，不需要命名发送进程，只填写表示源进程的参数，即完成通信后的返回值，而发送进程仍需要命名接收进程。
send(receiver,message);
receive(id,message); 接收来自任何进程的消息，id变量可设置为进行通信的发送方进程id或名字。

消息格式
比较短的定长消息格式 —— 减少对消息的处理和存储开销
变长的消息格式 —— 处理、存储方面付出更多的开销，方便用户

进程的同步方式
在完成消息的发送或接收后，存在三种情况：
1）发送进程阻塞，接收进程阻塞 —— 这种情况主要用于进程之间紧密同步，发送进程和接收进程之间无缓冲时。
2）发送进程不阻塞，接收进程阻塞 —— 发送进程不阻塞，因而它可以尽快地把一个或多个消息发送给多个目标；而接收进程平时处于阻塞状态，直到发送进程发来消息时才被唤醒
3）发送进程不阻塞，接收进程不阻塞 —— 发送进程和接收进程都在忙于自己的事情，仅当发生某事件使它无法继续运行时，才把自己阻塞起来等待

通信链路
通信双方建立链路，两种方式：

1）由发送进程在通信之前用显式的“建立连接”命令（原语）请求系统为之建立一条通信链路，在链路使用完成后拆除链路 —— 主要用于计算机网络

2）发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令（原语），系统会自动地为之建立一条链路 —— 主要用于单机系统中

根据通信方式的不同，把链路分成两种：
1）单向通信链路
2）双向通信链路
2. 信箱通信
间接通信方式 —— 信箱通信
进程之间的通信，需要通过某种中间实体来完成，该实体建立在随机存储器的公用缓冲区上，用来暂存发送进程发送给目标进程的消息；接收进程可以从该实体中取出发送进程发送给自己的消息，通常把这种中间实体称为邮箱，每个邮箱都有唯一的标识符。消息在邮箱中可以安全地保存，只允许核准的目标用户随时读取。既可实现实时通信，又可实现非实时通信。

信箱的结构 —— 一种数据结构，两个部分
1）信箱头，用以存放有关信箱的描述信息 —— 信箱标识符、信箱的拥有者、信箱口令、信箱的空格数等
2）信箱体 —— 由若干个可以存放消息的信箱格组成，信箱格的数目以及每格的大小是在创建信箱时确定的

信箱通信原语
1）邮箱的创建和撤销
进程可利用邮箱创建原语来建立一个新邮箱，创建者进程应给出邮箱名字、邮箱属性（公用、私用或共享）；对于共享邮箱，还应给出共享者的名字，当进程不再需要读邮箱时，可用邮箱撤销原语将之撤销。
2）消息的发送和接收。当进程之间要利用邮箱进行通信时，必须使用共享邮箱，并利用系统提供的通信原语进行通信。
Send（mailbox，message）;
Receive（mailbox，message）;

信箱的类型
1）私用邮箱。用户进程可为自己建立一个新邮箱，并作为该进程的一部分。邮箱的拥有者有权从邮箱中读取消息，其他用户则只能将自己构成的消息发送到该邮箱中，可采用单向通信链路的邮箱来实现。当拥有该邮箱的进程结束时，邮箱也随之消失。

2）公用邮箱。由操作系统创建，并提供给系统种的所有核准进程使用。核准用户既可把消息发到该邮箱，也可从邮箱读取给自己的消息，应采用双向通信链路的邮箱来实现。在系统运行期间始终存在。

3）共享邮箱。由某进程创建，在创建时或创建后指明它是可共享的，同时须指出共享进程的名字。邮箱的拥有者和共享者都有权从邮箱中取走发送给自己的消息。

发送进程和接收进程存在以下四种关系：
1）一对一
2）多对一
3）一对多
4）多对多

2.7 线程的基本概念 81

什么是线程
线程与进程

2.7.1 线程的引入

引入进程，是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量。引入线程，则是为了减少程序在并发执行时所付出的时空开销，使 OS 具有更好的并发性。

1.进程的两个基本属性
1）进程是一个可拥有资源的独立单位。
2）进程同时又是一个可独立调度和分派的基本单位。
程序并发执行所需付出的时空开销。
由于进程是一个资源的拥有者，因而在创建、撤消和切换中，系统必须为之付出较大的时空开销，因此限制了系统中设置进程的数量。
线程
设法将进程的上述两个属性分开，由 OS 分开处理，亦即对于作为调度和分派的基本单位，不同时作为拥有资源的单位；而对于拥有资源的基本单位，又不对之进行频繁的切换。正是在这种思想的指导下，形成了线程的概念。

2.7.2 线程和进程的比较

线程又称为轻型进程或进程元，传统进程称为重型进程。

1.调度的基本单位
在传统的 OS 中，作为拥有资源的基本单位和独立调度、分派的基本单位都是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位。
在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。
2.并发性
在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行。
3.拥有资源
不论是传统的 OS，还是引入了线程的 OS，进程都可以拥有资源，并作为系统中拥有资源的一个基本单位。线程本身并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源，例如线程控制块等。
允许一个进程中的多个线程贡献该进程所拥有的资源，这主要表现在：属于同一进程的所有线程都具有相同的地址空间。
4.独立性
在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。因为进程之间是为了防止彼此干扰和破坏；而同一进程中的不同线程往往是为了提高并发性以及进行相互之间的合作而创建的。
5.系统开销
进程的创建、撤销和切换所付出的开销都明显大于线程的创建、撤销和切换的开销。
6.支持多处理机系统
对于单线程进程，不管多少处理机，同一时刻该进程只能运行在一个处理机上。对于多线程进程，就可以将一个进程中的多个线程分配到多个处理机上并行执行。

2.7.3 线程的状态和线程控制块

线程的状态
创建、就绪、运行、阻塞、终止

第三章 处理机调度与死锁 92

3.2 作业与作业调度 95

3.2.3 先来先服务(FCFS)和短作业优先(SJF)调度算法

1先来先服务调度算法

FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业。

2短作业优先调度算法

SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。

3.2.4 优先级调度算法和高相应比优先调度算法

1优先级调度算法(priority-scheduling algorithm, PSA)

在优先级调度算法中，是基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的，这样就可以保证紧迫性作业优先运行。

2高相应比优先调度算法(Highest Response Ratio Next, HRRN)

高相应比优先调度算法是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机制调度的性能。

该优先级可表示为：

3.3 进程调度 98

3.3.2 轮转调度算法

3.3.3 优先级调度算法

3.3.4 多队列调度算法

3.3.5 多级反馈队列(multileved feedback queue)调度算法

3.5 死锁概述 112

死锁的四个必要条件

3.5.2 计算机系统中的死锁

死锁的起因，通常是源于多个进程对资源的争夺，不仅对不可抢占资源进行争夺时会引起死锁，而且对可消耗资源进行争夺时，也会引起死锁。

1竞争不可抢占性资源引起死锁

2竞争可消耗资源引起死锁

3进程推进顺序不当引起死锁

3.5.3 死锁的定义、必要条件和处理方法

1死锁的定义

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

2产生死锁的必要条件

(1) 互斥条件

(2) 请求和保持条件

(3) 不可抢占条件

(4) 循环等待条件

3处理死锁的方法

(1) 预防死锁

(2) 避免死锁

(3) 检测死锁

(4) 解除死锁

3.6 预防死锁 116

破坏四个必要条件

3.6.1 破坏“请求和保持”条件

为了能破坏“请求和保持”条件，系统必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源。该保证可通过如下两个不同的协议实现：

1第一种协议

该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。

2第二种协议

该协议是对第一种协议的改进，它运行一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。

3.6.2 破坏“不可抢占”条件

为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。

3.6.3 破坏“循环等待”条件

一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。在对系统所有资源类型进行线性排序后，便可采用这样的预防协议：规定每个进程必须按序号递增的顺序请求资源。

3.7 避免死锁 119

银行家算法

3.7.1 系统安全状态

在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。

1安全状态

在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，才可将资源分配给进程，否则，令进程等待。

2由安全状态向不安全状态的转换

如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。

在建立了系统安全状态的概念后便可知道避免死锁的基本思想，就是确保系统始终处于安全状态。一个系统开始是处于安全状态的，当有进程请求一个可用资源时，系统需对该进程的请求进行计算，若将资源分配给进程后系统仍处于安全状态，才将该资源分配给进程。

3.7.2 利用银行家算法避免死锁

1银行家算法中的数据结构

为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

(1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。

(2) 最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

(3) 分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。

(4) 需求矩阵Need。这也是一个n×m矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个方能完成其任务。

上述三个矩阵间存在下述关系：

Need[i,j]=Max[i,j]-Allocation[i,j]

2银行家算法

设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1) 如果Requesti[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

(2) 如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。

(3) 系统试探着把资源分配给进程Pi，并修改数据结构中的数值。

(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

3安全性算法

系统所执行的安全性算法可描述如下：

(1) 设置两个向量：①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available；②Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true。

(2) 从进程集合中找到一个能满足下述条件的进程：

①Finish[i]=false;

②Need[i,j]≤Work[j];

若找到，执行步骤(3)，否则，执行步骤(4)。

(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j] = Work[j] + Allocation[i,j];

Finish[i] = true;

go to step 2;

(4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

3.8.死锁的检测与解除

1资源分配图(Resource Allocation Gragh)
2死锁定理

第四章 存储器管理 129

4.3 连续分配存储管理方式135

4.3.4 基于顺序搜索的动态分区分配算法

顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。
碎片：内存空间不断被划分，会留下许多难以利用的、很小的空闲分区。

1.首次适应（first fit，FF）算法
要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止，缺点是低址部分会不断被划分，形成碎片。
2.循环首次适应（next fit，NF）算法
在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。实现可通过设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式。缺点缺乏大的空闲分区。
3.最佳适应（best fit，BF）算法
总是把能满足要求、又是最小的空闲分区分配给作业，为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。缺点产生许多碎片。
4.最坏适应（worst fit，WF）算法
在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，分割一部分空间给作业使用。要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求即可。缺点缺乏大的空闲分区。

4.3.5 基于索引搜索的动态分区分配算法

1.快速适应算法
又称为分类搜索法。是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。
该算法仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。在分配过程中，不会对任何分区产生分割。
2.伙伴系统
规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂（k 为整数，l≤k≤m）。通常 2^m是整个可分配内存的大小。
对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。
当需要为进程分配一个长度为 n 的存储空间时，首先计算一个 i 值，使 2^(i-1) < n ≤ 2^i，然后在空闲分区大小为 2^i 的空闲分区链表中查找。若找到则直接分配。否则，则在分区大小为 2^(i+1) 的空闲分区链表中寻找。若存在 2^(i+1) 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为 2^i 的空闲分区链表中。若仍然找不到，依次类推去寻找更高1次幂的分区。
与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为 2^{i的空闲分区时，若事先已存在回收块所对应的2}i伙伴块的空闲分区时，则应将其与伙伴分区合并为大小为2^{(i+1)的空闲分区，若事先已存在新合并空闲块对应的2}(i+1)伙伴块的空闲分区时，依次类推合并。
对于一个大小为2^k，地址为x的内存块，其伙伴块的地址则用buddy k (x)表示，其通式为：

if(x MOD 2^(k+1) == 0) {
buddy k (x) = x + 2^k;
}
else if(x MOD 2^(k+1) == 2^k) {
buddy k (x) = x - 2^k;
}

3.哈希算法
构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。

4.5 分页存储管理方式 147

4.6 分段存储管理方式 155

第五章 虚拟存储器 164

5.1 虚拟存储器概述 164

什么是虚拟内存

5.1.2虚拟存储器的定义和特征

1.虚拟存储器的定义
所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。
2.虚拟存储器的特征
1）多次性。是指一个作业中的程序和数据无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。
2）对换性。是指一个作业中的程序和数据，无须在运行时一直常驻内存，而是允许在作业的运行过程中进行换进、换出。
3）虚拟性。是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。就可以在小的内存中运行大的作业，或者能提高多道程序度。
虚拟性是以多次性和对换性为基础的，而多次性和对换性是必须建立在离散分配的基础上。

5.2 请求分页存储管理方式 168

5.2.2 请求分页中的内存分配

1.最小物理块数的确定
这里所说的最小物理块数，是指能保证进程正常运行所需的最小物理块数。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。
2.内存分配策略
在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。
1）固定分配局部置换。
所谓固定分配，是指为每个进程分配一定数目的物理块，在整个运行期间都不再改变。所谓局部置换，是指如果进程在运行中发现缺页，则只能从分配给该进程的 n 个页面中选出一个页换出，然后再调入一页，以保证分配给该进程的内存空间不变。实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。
2）可变分配全局置换。
所谓可变分配，是指先为系统中的每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。所谓全局置换，是指当进程发现缺页时，则将 OS 所保留的空闲物理块(一般组织为一个空闲物理块队列)取出一块分配给该进程，或者以所有物理块为标的，选择一块换出，然后将所缺之页调入。
在采用这种策略时，凡产生缺页(中断)的进程，都将获得新的物理块，仅当空闲物理队列中的物理块用完时，OS 才能从内存中选择一页调出，而被选择调出的页所属的进程拥有的物理块就会减少，导致其缺页率增加。
3）可变分配局部置换。
该策略为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数，但不应引起其缺页率的明显增加。
3.物理块分配算法
在采用固定分配策略时，如何分配物理块采用以下算法：
1）平均分配算法。
2）按比例分配算法，即根据进程的大小按比例分配物理块的算法。
3）考虑优先权的分配算法。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权进行分配。

5.3 页面置换算法 174

5.3.1 最佳置换算法和先进先出置换算法

最佳置换算法是一种理想化的算法，通常使用最佳置换算法作为标准，来评价其它算法的优劣。先进先出置换算法是最直观的算法，由于与通常页面的使用规律不服，可能是性能最差的算法，故实际应用极少。

1.最佳(Optimal)置换算法
其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问(即下一次访问时间最晚)的页面。采用最佳置换算法，通常可保证获得最低的缺页率。

假定系统为某进程分配了三个物理块，并考虑有以下的页面好引用串：

7,0,1,2,0,3,0,4，2,3,0,3,2,1,2,0,1,7,0,1

置换图如下：
每次把最长（未来）时间内不在访问的页面置换出

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 70 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 01 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
+ + + +       +     +     +       +

置换次数是6次，前三次不是置换，只是缺页
缺页中断次数9，缺页率9/20
2.先进先出(FIFO)页面置换算法
总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
FIFO 置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。

假定系统为某进程分配了三个物理块，并考虑有以下的页面好引用串：

7,0,1,2,0,3,0,4，2,3,0,3,2,1,2,0,1,7,0,1

置换图如下：
置换出最先进入内存的页面，置入放在最底了，这样最顶就是最先进入内存
当不需要置换时，保持不变。

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
7 7 7 0 0 1 2 3 0 4 2 2 2 3 0 0 0 1 2 70 0 1 1 2 3 0 4 2 3 3 3 0 1 1 1 2 7 01 2 2 3 0 4 2 3 0 0 0 1 2 2 2 7 0 1
+ + + +   + + + + + +     + +     + + +

置换次数是12次，前三次不是置换，只是缺页
缺页中断次数15，缺页率15/20

5.3.2 最近最久未使用和最少使用置换算法

1.LRU(Least Recently Used) 置换算法的描述
最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。即选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。
最佳置换算法是从“向后看”的观点出发的，即它是依据以后各页的使用情况；而 LRU 算法则是“向前看”的，即根据各页以前的使用情况来判断，而页面过去和未来的走向之间并无必然的联系。

2.LRU 置换算法的硬件支持
1）寄存器。
为每个在内存中的页面配置一个移位寄存器，可表示为
R=R_n-1R_n-2R_n-3…R₂R₁R₀
当进程访问某物理块时，要将相应寄存器的 Rn－1 位置成 1。此时，定时信号将每隔一定时间(例如 100 ms)将寄存器右移一位。如果我们把 n 位寄存器的数看做是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
2）栈。
可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。

假定系统为某进程分配了三个物理块，并考虑有以下的页面好引用串：

7,0,1,2,0,3,0,4，2,3,0,3,2,1,2,0,1,7,0,1

置换图如下：
置换出最进未使用入的页面，置入放在最底了，这样最顶就是最近最久未使用的页面
当不需要置换是，也需把新页面放在最底，保证了最底层是最近最久使用的页面。

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
7 7 7 0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 70 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 01 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
+ + + +   +   + + + +     +   +   +

置换次数是9次，前三次不是置换，只是缺页
缺页中断次数12，缺页率12/20

3.最少使用 LFU 置换算法
该算法用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置 1，再每隔一定时间(例如 100 ms)右移一次。LFU 置换算法的页面访问图与 LRU 置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现 LRU 算法，又可实现 LFU 算法。但 LRU 算法是根据将 n 位看作一个整数找到最近最久未使用的页面，而 LFU 算法的在最近一段时间使用最少的页面将是∑Ri 最小的页。
应该指出，LFU 算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，在该时间间隔内，对某页访问一次和访问 1000 次是完全等效的。

5.3.3 Clock 置换算法

虽然 LRU 算法是较好的一种算法，但由于它要求有较多的硬件支持，故在实际应用中，大多采用 LRU 的近似算法。Clock 算法就是用得较多的一种 LRU 近似算法。

1.简单的 Clock 置换算法。
只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置 1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是 0，就选择该页换出；若为 1，则重新将它置 0，暂不换出，而给该页第二次驻留内存的机会，再按照 FIFO 算法检查下一个页面。该算法是循环地检查各页面的使用情况的。又把该算法称为最近未用算法 NRU。
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)：表示该页最近已被访问且被修改，该页可能再被访问。
在内存中的每个页必定是这四类页面之一，在进行页面置换时，与简单 Clock 算法差别在于该算法须同时检查访问位与修改位，以确定该页是四类页面中的哪一种。其执行过程可分成以下三步：
1）从指针所指示的当前位置开始，扫描循环队列，寻找 A=0 且 M=0 的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。
2）如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找 A=0 且 M=1 的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置 0。
3）如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并已将所有的访问位复 0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。
该算法与简单 Clock 算法比较，可减少磁盘的 I/O 操作次数。但为了找到一个可置换的页，可能须经过几轮扫描。换言之，实现该算法本身的开销将有所增加。

5.3.4 页面缓冲算法 PBA

1.影响页面换进换出效率的若干因素
1）页面置换算法。
2）写回磁盘的频率。对于已经被修改过的页面，在将其换出时，应当写回磁盘。
但如果在系统中已建立了一个已修改换出页面的链表，则对每一个要被换出的页面(已修改)，系统可暂不把它们写回磁盘，而是将它们挂在已修改换出页面的链表上，仅当被换出页面数目达到一定值时，例如64个页面，再将它们一起写回到磁盘上，这样就显著减少了磁盘 I/O的操作次数。或者说，减少已修改页面换出的开销。
3）读入内存的频率。在设置了已修改换出页面链表后，在该链表上就暂时有一批装有数据的页面，如果有进程在这批数据还未写回磁盘时需要再次访问这些页面时，就不需从外存上调入，而直接从已修改换出页面链表中获取，这样也可以减少将页面从磁盘读入内存的频率，减少页面换出的开销。
2.页面缓冲算法 PBA
PBA 算法特点：① 显著地降低了页面换进、换出的频率。② 正是由于换入换出的开销大幅度减小，才能使其可采用一种较简单的置换策略，如先进先出(FIFO)算法。
介绍VAX/VMS操作系统所使用的页面缓冲算法。在该系统中内存分配策略上采用了可变分配和局部置换方式，同时在内存中设置了两个链表：
1）空闲页面链表。
实际上是一个空闲物理块链表。当进程需要读入一个页面时，便可利用空闲物理块链表中的第一个物理块来装入该页。当有一个未被修改的页要换出时，而是把它们所在的物理块挂在空闲链表表尾。
2）修改页面链表。
是由已修改的页面所形成的链表。当进程需要将一个已修改的页面换出时，系统并不立即把它换出到外存上，而是将它所在的物理块挂在修改页面链表的末尾。当达到一定数量时，再将它们一起写回磁盘。

5.5 请求分段存储管理方式 185

第六章 输入输出系统 191

6.4 设备驱动程序

6.4.3 对I/O设备的控制方式

1. 使用轮询的可编程I/O方式
处理机对 I/O 设备的控制采取轮询的可编程I/O方式，即在处理机向控制器发出一条 I/O 指令启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志 busy 置为 1，然后便不断地循环测试 busy。当 busy=1 时，表示输入机尚未输完一个字(符)，处理机应继续对该标志进行测试，直至 busy=0，表明输入机已将输入数据送入控制器的数据寄存器中。于是处理机将数据寄存器中的数据取出，送入内存指定单元中，这样便完成了一个字(符)的 I/O。接着再去启动读下一个数据，并置 busy=1。
2. 使用中断的可编程I/O方式
采用中断的可编程I/O方式，即当某进程要启动某个 I/O 设备工作时，便由 CPU 向相应的设备控制器发出一条 I/O 命令，然后立即返回继续执行原来的任务。设备控制器于是按照该命令的要求去控制指定 I/O 设备。此时，CPU 与 I/O 设备并行操作。一旦数据进入数据寄存器，控制器便通过控制线向 CPU 发送一中断信号，由 CPU 检查输入过程中是否出错，若无错，便向控制器发送取走数据的信号，然后再通过控制器及数据线将数据写入内存指定单元中。
适用于低速流设备，如键盘，鼠标。
3. 直接存储器(DMA)访问方式
中断驱动 I/O 比程序 I/O 方式更有效，但须注意，它仍是以字(节)为单位进行 I/O 的，每当完成一个字(节)的 I/O 时，控制器便要向 CPU 请求一次中断。换言之，采用中断驱动 I/O 方式时的 CPU 是以字(节)为单位进行干预的。
从而引入直接存储器访问方式，其特点如下：
1）数据传输的基本单位是数据块，即在 CPU 与 I/O 设备之间，每次传送至少一个数据块；
2）所传送的数据是从设备直接送入内存的，或者相反；
3）仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送是在控制器的控制下完成的。
4. I/O通道控制方式
I/O 通道方式是 DMA 方式的发展，它可进一步减少 CPU 的干预，即把对一个数据块的读(或写)为单位的干预减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。同时，又可实现 CPU、通道和 I/O 设备三者的并行操作。而通道能与 I/O 设备并行是因为 I/O 通道实际上是一种特殊的处理机，它具有执行 I/O 指令的能力，并通过执行通道 I/O 程序来控制 I/O 操作。增设 I/O 通道的主要目的是为了建立独立的 I/O 操作，或者说是使一些原来由 CPU 处理的 I/O 任务转由通道来承担。

6.8 磁盘存储器的性能与调度 230

调度算法

6.8.2 早期的磁盘调度算法

由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。

1. 先来先服务 FCFS
根据进程请求访问磁盘的先后次序进行调度。
优点：简单, 公平；
缺点：效率低, 相临两次请求可能会造成最内到最外的柱面寻道, 使磁头反复移动, 增加了平均寻道时间
设磁盘访问序列: 80, 55, 58, 39, 18, 90,160,150, 38,184

2. 最短寻道时间优先
该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。

优点：磁盘的平均寻道时间最小
缺点：进程"饥饿"现象, 有时会造成与当前磁道距离远的访问请求长期等待得不到服务(不公平)

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

1. 扫描(SCAN)算法
SSTF算法可能导致优先级低(即不断出现的新进程所要访问的磁道与当前磁头的位置时钟较劲，使原本较远的进程一直得不到满足)的进程发生“饥饿”现象。
扫描算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN 算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内且距离最近者。
由于在这种算法中磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度算法。

2. 循环扫描(CSCAN)算法
循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

3. NStepSCAN 和 FSCAN 调度算法
1）NStepSCAN算法。
在 SSTF、 SCAN 及 CSCAN 几种调度算法中，都可能会出现磁臂停留在某处不动的情况。例如，有一个或几个进程对某一磁道有较高的访问频率，即这个(些)进程反复请求对某一磁道的 I/O 操作，从而垄断了整个磁盘设备。我们把这一现象称为“磁臂粘着”。
NStepSCAN 算法是将磁盘请求队列分成若干个长度为 N 的子队列，磁盘调度将按 FCFS 算法依次处理这些子队列。而每处理一个队列时又是按 SCAN 算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘 I/O 请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。当 N 值取得很大时，会使 N 步扫描法的性能接近于 SCAN 算法的性能；当 N=1 时，N 步 SCAN 算法便蜕化为 FCFS 算法。
2）FSCAN 算法。
FSCAN 算法实质上是 N 步 SCAN 算法的简化，即 FSCAN 只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘 I/O 的进程形成的队列，由磁盘调度按 SCAN 算法进行处理。在扫描期间，将新出现的所有请求磁盘 I/O 的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。

第七章 文件管理 237

7.2 文件的逻辑结构

7.2.1 文件逻辑结构的类型

7.2.2 顺序文件

7.2.3 记录寻址

7.2.4 索引文件

7.2.5 索引顺序文件

7.2.6 直接文件和哈希文件

7.3 文件目录

7.3.1文件控制块和索引结点

7.3.2 简单的 目录结构

7.3.3 多级目录结构(树型目录)

7.3.4 目录查询技术

第八章 磁盘存储器的管理 268

8.1 外存的组织方式

8.1.1 连续组织方式

8.1.2 链接组织方式

8.1.3 FAT技术

8.1.4 NTFS的文件组织方式

8.1.5 索引组织方式

8.2 文件存储空间的管理

8.2.1 空闲表法和空闲链表法

8.2.2 位示图

8.2.3 成组链接法

8.3 提高磁盘I/O速度的途径

8.3.1 磁盘高速缓存(Disk Cache)

8.3.2 提高磁盘I/O速度的其他方法

8.3.3 磁盘冗余阵列

第九章 操作系统接口 298

9.4 系统调用的概念和类型 315

9.4.1 系统调用的基本概念

1.系统态和用户态

在计算机系统中设置了两种状态：系统态(或称为核心态)和用户态。在实际运行过程中，处理机会在系统态和用户态间切换。相应地，现代多数OS将CPU的指令集分为特权指令和非特权指令两类。

(1) 特权指令。特权指令是指在系统态运行的指令，它对内存空间的访问范围基本不受限制，不仅能访问用户空间，也能访问系统空间。

(2) 非特权指令。非特权指令是在用户态运行的指令。应用程序所使用的都是非特权指令，它只能完成一般性的操作和任务，不能对系统中的硬件和软件直接进行访问，对内存的访问范围也局限于用户空间。

2.系统调用

在OS中提供系统调用的目的，是使应用程序可以通过它直接调用OS中的相关过程，取得相应的服务。系统调用在本质上是应用程序请求OS内核完成某功能时的一种调用，但它是一种特殊的过程调用，它与一般的过程调用有下述几方面的明显差别：

(1) 运行在不同的系统状态。

(2) 状态的转换。

(3) 返回问题。

(4) 嵌套调用。

3.中断机制

系统调用是通过中断机制实现的，并且一个操作系统的所有系统调用，都通过同一个中断入口来实现。如MS-DOS提供了INT 21H，应用程序通过该中断获取操作系统的服务。

对于拥有保护机制的OS来说，中断机制本身也是受保护的，在IBM PC上，Intel提供了多达255个中断号，但只有授权给应用程序保护等级的终端号，才是可以被应用程序调用的。对于未被授权的中断号，如果应用程序进行调用，同样会引起保护异常，而导致自己被操作系统停止。如Linux仅仅给应用程序授权了4个中断号：3，4，5以及80h。前三个中断号是提供给应用程序调试所使用的，而80h正是系统调用(system call)的中断号。

最后

2022-11-20 20:18:32

这篇博客能写好的原因是：站在巨人的肩膀上

这篇博客要写好的目的是：做别人的肩膀

开源：为爱发电

学习：为我而行