选择题
判断题
考试不考判断题，仅记录相关知识点
应该是错误的。Spooling实质是将独占设备转化为共享设备的技术
对一个具有三级索引表的文件，存取一个记录通常需要4次访问磁盘。x
答案解析：三级索引需要访问4次磁盘，3次磁盘索引块，1次读取数据。
知识点
计算机操作系统概述
试述操作系统中三个最基础的抽象，并回答为什么要引入它们？
- 进程抽象、虚存抽象、文件抽象
- 防止硬件资源被应用程序滥用
- 屏蔽复杂的硬件资源操作细节，为应用程序提供使用硬 件资源的简单且一致的方法
操作系统是计算机系统最基础的系统软件，管理软硬件资源、控制程序执行，改善人机界面，合理组织计算机工作流程，为用户使用计算机提供良好运行环境。
操作系统的组成
- 进程调度子系统
- 进程通信子系统
- 内存管理子系统
- 设备管理子系统
- 文件管理子系统
- 网络通信子系统
- 作业控制子系统
操作系统的分类
- 多道批处理操作系统
- 脱机控制方式
- 分时操作系统
- 交互式操作系统
- 实时操作系统
- 多道批处理操作系统
多道程序设计
- 定义：让多个程序同时进入计算机的主存储器进行计算
- 目的：解决CPU速度与I/O速度不匹配的矛盾
- 特点：
- CPU与外部设备充分并行
- 外部设备之间充分并行
- 发挥CPU的使用效率
- 提高单位时间的算题量
- 但是单道程序运行时间会增加
操作系统内核结构
- 单内核：内核各部件杂然混居的形态。Linux, Windows
- 微内核：结构性部件和功能性部件分离。将大部分功能模块置于用户态
- 混合内核：微内核与单内核折中。
- 外内核
试述系统调用的实现原理，陷阱机制和绘制系统调用的处理过程，并阐述系统调用的处理逻辑。
定义：操作系统实现的完成某种特定功能的过程，为所有运行程序提供访问操作系统的接口
系统调用的实现
- 编写系统调用服务例程
- 设计系统调用入口地址表，每个入口地址都指向一个系统调用的服务例程，有些还包含系统调用自带参数的个数
- 陷阱处理机制，需要开辟现场保护区，以保存发生系统调用时应用程序的处理器现场。
- 陷阱机制：操作系统实现系统调用功能的机制称为系统陷阱或系统异常处理机制，由于系统调用而引起处理器中断的机器指令称为陷入指令(trap)，它是非特权指令，在用户态下执行时会产生CPU 模式切换，即由用户态转换到内核态。每个系统调用都事先规定编号，称为功能号，执行陷入指令时，必须通过某种方式指明对应系统调用的功能号，大多数情况，还应附带有传递给相应服务例程的参数。
- 系统调用的处理过程：
- 应用程序执行系统调用，产生中断转向内核态，进入陷阱处理程序
- 将按功能号来查询入口地址表，并转至对应服务例程执行
- 完成后退出中断，返回应用程序断点继续运行。
处理器管理
进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动；是操作系统进行资源分配和调度的一个独立单位。
进程实体
- 操作系统管理的数据结构
- 内存代码
- 内存数据
- 通用寄存器信息
- 程序状态字信息
进程映像的组成部分
- 进程控制块：保存进程的标识信息、状态信息和控制信息
- 进程程序块: 进程执行的程序空间
- 进程数据块: 进程处理的数据空间，包括数据、处理函数的用户栈和可修改的程序
- 核心栈: 进程在内核模式下运行时使用的堆栈，中断或系统过程使用
共享的代码称为可再入程序，是纯代码的。
结合进程状态转换模型，解释操作系统是中断驱动的
中断是激活操作系统的唯一方式
中断系统：计算机系统中响应和处理中断的系统
中断响应由硬件子系统完成
中断处理由软件子系统完成
中断处理过程
- 发现中断源。硬件发现中断/异常事件，并由CPU响应中断/异常请求。当发现多个中断源时，将根据预定的中断优先级先后响应中断请求。
- 保存现场。暂停当前程序运行，将现场信息（PSW）保存至核心栈。
- 转向中断/异常时间处理程序执行。
恢复现场。恢复原运行程序的PSW，重新返回中断点以便执行后续指令。
进程三态模型
进程五态模型
进程控制块PCB是用于记录和刻画进程状态及环境信息的数据结构
标识信息
现场信息
控制信息
进程控制与管理原语
进程创建
进程撤销
进程阻塞
进程唤醒
进程挂起
进程激活
多线程程序设计优点
快速线程切换
减少系统管理开销
线程通信易于实现
并行程度提高
节省内存空间
内核级线程KLT：线程管理的所有工作由OS内核来做
用户级线程ULT：用户空间运行的线程库，提供多线程应用程序的开发和运行支撑环境
Jacketing技术
解决ULT中，一个线程阻塞导致整个进程阻塞的问题
把阻塞式系统调用改造成非阻塞式的
当线程陷入系统调用时，执行jacketing程序
由jacketing 程序来检查资源使用情况，以决定是否执行进程切换或传递控制权给另一个线程
用户级线程和内核级线程
- ULT适用于解决逻辑并行性问题
- KLT适用于解决物理并行性问题
- 多线程实现的混合策略：单应用的多个ULT可以映射成一些KLT，通过调整KLT数目，可以达到较好的并行效果
多线程混合策略下的线程状态
KLT三态，系统调度负责
ULT三态，用户调度负责
活跃态ULT代表绑定KLT的三态
活跃态ULT运行时可激活用户调度
非阻塞系统调用可使用Jacketing启动用户调度，调整活跃态ULT
处理器调度的层次
- 高级调度：决定能否加入到执行的进程池中
- 中级调度：决定主存中的可用进程集合
- 低级调度：决定哪个可用进程占用处理器执行
进程调度算法
先来先服务 FCFS（非抢占式）
- 按照进程进入系统的时间顺序排
- 多用于高级调度
- 以计算为主的进程过于优越，长时间占有CPU
- 一个短进程不得不等待很长时间
最短进程优先 SPN（非抢占式）
- 优先处理计算时间短的进程
- 对长进程不公平，导致长进程饿死
最短剩余时间优先 SRT（抢占式）
- 总是选择预期剩余时间更短的进程
- 当一个新进程加入就绪队列，他可能比当前运行的进程具有更短的剩余时间，只要该新进就绪，调度器就可能抢占当前正在运行的进程
最高响应比优先HRRN（非抢占式）
- 选择响应比最高的
- 改善对长进程极端不公平的问题
- 时间片轮转调度算法RR（抢占式）
- 基于先来先服务的，但是每个选程占有 CPU 运 行必须受到时间片的限制，一旦进程运行时间超过了该时间片就得让出 CPU
多级反馈调度MLFQ（抢占式）
建立多个不同优先级的就绪进程队列
多个就绪进程队列之间按照优先数调度
高优先级的就绪进程, 分配的时间片短
单个就绪进程队列中的进程的优先数和时间片相同，按照先来先服务算法调度
优点：优先级可变、适应性强
缺点：长进程最终会进入最低优先级队列，可能会一直等待
解决方法：对低优先级队列中等待时间足够长的进程提升优先级
当一个进程第一次进入系统时，它被放置在RQ0，当它第一次被抢占后并返回就绪状态时，它被放置在RQ1。在随后的时间里，每当它被抢占时，它被降级到下一个低优先级队列中。一个短进程很快会执行完，不会在就绪队列中降很多级。
Unix SVR4调度算法
实时优先级层次：优先数和时间片都是固定的，在抢占点执行抢占
分时优先级层次：优先数和时间片是可变的，从0优先数的100ms到59优先数的10ms
存储管理
虚存分页的原理，并画出流程图
分页存储器将主存划分成多个大小相等的页架
受页架尺寸限制，程序的逻辑地址也自然分成页
不同的页可以放在不同页架中，不需要连续
页表用于维系进程的主存完整性，记录虚拟页面和页框的对应关系
存储管理的基本模式
- 单连续存储管理：一维逻辑地址空间的程序占用一个主存固定分区或可变分区
- 段式存储管理：段式二维逻辑地址空间的程序占用多个主存可变分区
- 页式存储管理：一维逻辑地址空间的程序占用多个主存页框(页架)区
- 段页式存储管理：段式二维逻辑地址空间的程序占用多个主存页框(页架)区
地址转换：又称重定位，即把逻辑地址转换成绝对地址
- 静态重定位：在程序装入内存时进行地址转换
- 由装入程序执行，早期小型OS使用
- 动态重定位：在CPU执行程序时进行地址转换
- 从效率出发，依赖硬件地址转换机构
- 静态重定位：在程序装入内存时进行地址转换
主存扩充：把磁盘作为主存扩充，只把部分进程或进程的部分内容装入内存
- 对换技术：把部分不运行的进程调出
- 虚拟技术：只调入进程的部分内容
虚拟存储器的基本思想
- 存储管理把进程全部信息放在辅存中，执行时先将其中一部分装入主存，以后根据执行行为随用随调入
- 如主存中没有足够的空闲空间，存储管理需要根据执行行为把主存中暂时不用的信息调出到辅存上去
可变分区内存分配
最先适应分配算法(First fit)
邻近适应分配算法(Next fit)
最优适应分配算法(Best fit)：最容易产生外零头
最坏适应分配算法(Worst fit)
程序移动技术 （浮动技术）
解决内存外零头
需要动态重定位
页的共享
- 数据共享：不同进程可以使用不同页号共享数据页
- 程序共享：不同进程必须使用相同页号共享代码页（现代操作系统都不需要相同页号共享代码页了）
抖动：如果一块正好将要被用到之前扔出，操作系统有不得不很快把它取回来，太多的这类操作会导致一种称为系统抖动的情况。在处理缺页中断期间，处理器的大部分时间都用于交换块，而不是用户进程的执行指令
页式虚拟存储管理
基本思想：把进程全部页面装入虚拟存储器，执行时先把部分页面装入实际内存，然后，根据执行行为，动态调入不在主存的页，同时进行必要的页面调出
页表项
- 每页的虚拟地址、实际地址
- 主存驻留标志、写回标志、保护标志、引用标志、可移动标志
页面调度
- 最佳算法OPT/Belady：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页。只可模拟，不可实现。
- 先进先出FIFO：总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页(常驻的除外)
- 最近最少使用LRU：淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可能马上还要被使用到。实现代价大
- 最不常用LFU：淘汰最近一段时间内访问次数较少的页面，对OPT的模拟性比LRU更好
- 时钟CLOCK：
- 页面调入主存时，其引用标志位置1
- 访问主存页面时，其引用标志位置1
- 淘汰页面时，从指针当前指向的页面开始扫描循环队列把所遇到的引用标志位是1的页面的引用标志位清0，并跳过
- 把所遇到的引用标志位是0的页面淘汰，指针推进一步
- 局部最佳页面替换算法MIN：不论发生缺页与否，算法在每一步要考虑引用串，如果该页面在时间间隔(t, t+τ)内未被再次引用，那么就移出；否则，该页被保留在进程驻留集中
- 工作集替换算法：工作集模型用来对局部最佳页面替换算法进行模拟实现，不向前查看页面引用串，而是基于程序局部性原理向后看
多级页表
反置页表
基本思想：
- 针对内存中的每个页框建立一个页表，按照块号排序
- 表项包含：正在访问该页框的进程标识、页号及特征位，和哈希链指针等
- 用来完成内存页框到访问进程页号的对应，即物理地址到逻辑地址的转换
地址转换过程
- MMU通过哈希表把进程标识和虚页号转换成一个哈希值，指向IPT的一个表目
- MMU遍历哈希链找到所需进程的虚页号，该项的索引就是页框号，通过拼接位移便可生成物理地址
- 若遍历整个反置页表中未能找到匹配页表项，说明该页不在内存，产生缺页中断，请求操作系统调入
段式存储管理
基本思想
- 段式存储管理基于可变分区存储管理实现，一个进程要占用多个分区
- 硬件需要增加一组用户可见的段地址寄存器（代码段、数据段、堆栈段，附加段），供地址转换使用
- 存储管理需要增加设置一个段表，每个段占用一个段表项，包括：段始址、段限长，以及存储保护、可移动、可扩充等标志位
地址转换流程
段式虚拟存储管理
- 基本思想：把进程的所有分段都存放在辅存中，进程运行时先把当前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把它们动态装入。段式虚拟存储管理中段的调进调出是由OS自动实现的，对用户透明
段页式存储管理
设备管理
IO软件的四个层次
- 用户空间的IO软件
- SPOOLing
- 独立于设备的IO软件
- 设备驱动程序
- 中断处理程序
- 用户空间的IO软件
设备分类
- 字符设备：以字符为单位进行信息交换，例如鼠标、显示器
- 块设备：以固定大小的数据块为单位进行信息交换，例如磁盘
总线：
- I/O和CPU速度、各设备I/O速度不匹配
- 使主机和设备充分并行，提高系统效率
设备独立性
- 设备独立性：用户通常不指定物理设备，而是指定逻辑设备，使得用户进程和物理设备分离开来，再通过其它途径建立逻辑设备和物理设备之间的映射
设备分配方式
- 独占型外围设备：一次只能由一个进程独占使用
- 分配方式
- 静态分配：进程运行前申请
- 实现简单，能够防止系统发生死锁，但会降低设备利用率
- 动态分配：进程随用随申请
- 提高设备利用率
- 静态分配：进程运行前申请
虚拟设备：使用一类物理设备模拟另一类物理设备
SPOOLing系统：用高速的磁盘设备来模拟慢速的字符设备，缩短进程在内存中的驻留时间
预输入程序：预先把数据从输入设备传送到磁盘输入井
缓输出程序：把数据从磁盘输出井传送到输出设备
井管理程序：控制作进程和井之间的数据交换
磁盘调度策略
文件管理
文件系统面向用户的功能：
- 文件的按名存取
- 文件的共享和保护
- 文件的操作和使用
逻辑文件，又称为文件的逻辑结构
- 独立于物理环境的，用户概念中的抽象信息组织方式
- 用户能观察到的，并加以处理的数据集合
- 文件的逻辑结构分为两种形式
- 一种是流式文件
- 一种是记录式文件
- 独立于物理环境的，用户概念中的抽象信息组织方式
文件的物理结构和组织是指文件在物理存储空间中的存放方法和组织关系
- 顺序文件
连接文件（输入井、输出井）
直接文件（散列文件）
- 索引文件
文件系统调用
文件创建
int create(const char *pathname, mode_t mode);
- 参数：文件名、模式（存取权限）
- 返回值：成功返回文件描述符，失败返回-1
- 实现步骤：
- 为新文件分配索引节点和活动索引节点，并把索引节点编号与文件分量名组成新目录项，记到目录中。
- 在新文件所对应的活动索引节点中置初值，如置存取权限i_mode，连接计数i_nlink等。
- 分配用户打开文件表项和系统打开文件表项，置表项初值，读写位移f_offset清“0”。
- 把各表项及文件对应的活动索引节点用指针连接起来
- 把文件描述字返回给调用者。
文件删除
int unlink(const char *pathname);
- 参数：文件名
- 返回值：成功返回0，失败返回-1
- 实现步骤：
- 把指定文件从所在的目录文件中除去
- 将inode中的i_nlink减1
- 如果没有连接用户(i_nlink 为“0”)，还要把文件占用的存储空间释放。
文件打开
int open(const char *pathname, mode_t mode);
- 参数：文件名、模式（存取权限）
- 返回值：成功返回文件描述符，失败返回-1
- 实现步骤：
- 检索目录，如果inode还未被复制到内存，把它的inode复制到活动inode表。
- 根据参数mode核对权限，如果非法，则这次打开失败。
- 当“打开”合法时，为文件分配用户打开文件表项和系统打开文件表项，并为表项设置初值。
- 通过指针建立这些表项与活动索引节点间的联系。
- 把文件描述字，即用户打开文件表中相应文件表项的序号返回给调用者。
文件关闭
int close(int fd);
- 参数：文件描述符
- 返回值：成功返回0，失败返回-1
- 实现步骤：
- 根据fd找到用户打开文件表项，再找到系统打开文件表项。释放用户打开文件表项。
- 把对应系统打开文件表项中的f_count减“1”，如果非“0”，说明还有进程共享这一表项，不用释放直接返回；否则释放表项。
- 把活动索引节点中的i_count减“1”，若不为“0”，表明还有用户进程正在使用该文件，不用释放而直接返回，否则在把该活动索引节点中的内容复制回文件卷上的相应索引节点中后，释放该活动索引节点。
文件读取
size_t read (int fd, void buf, size_t *cnt);
- 参数：文件描述符、读取数据缓冲区、缓冲区大小
- 返回值：实际读取字节数
- 实现步骤：
- 系统根据f_flag中的信息，检查读操作合法性
- 再根据当前位移量f_offset值，要求读出的字节数，及活动索引节点中i_data[15]指出的文件物理块存放地址，把相应的物理块读到缓冲区中，然后再送到bufp指向的用户主存区中。
文件写入
size_t write (int fd, void buf, size_t *cnt);
- 参数：文件描述符、写入数据缓冲区、写入数据长度
- 返回值：实际写入的数据
- 实现步骤：
- 系统根据f_flag中的信息，检查写操作合法性
- 再根据当前位移量f_offset值，要求写入的字节数，及活动索引节点中i_data[15]指出的文件物理块存放地址，把数据缓冲区的数据写入到文件中。
移动位移
off_t lseek(int fd, off_t offset, int whence);
- 参数：文件描述符、偏移量、位置
- 返回值：成功返回当前位置到开始的长度，失败返回-1
- 实现步骤：
- 找到系统打开文件表项，修改f_offset的值
文件链接
int link(const char *oldpath, const char *newpath);
- 参数：原始文件名、新的硬链接名
- 返回值：成功返回0，失败返回-1
- 实现步骤：
- 检索目录找到oldnamep所指向文件的索引节点inode编号。
- 再次检索目录找到newnamep所指文件的父目录文件，并把已存在文件的索引节点inode编号与别名构成一个目录项，记入到该目录中去。
- 把已存在文件索引节点inode的连接计数i_nlink加“1”。
文件系统的磁盘结构
- 引导块
- 超级块：占用1#号块，存放文件系统结构和管理信息（位示图）
- 索引节点区
- 数据区
文件系统数据结构
虚拟文件系统
并发程序设计
并行和并发
- 并行性是指两个或多个事件在同一时刻发生（多核）
- 并发性是指两个或多个事件在同一时刻间隔内发生
n个进程共享m个同类资源，若每个进程都需要用该类资源，而且各进程对该类资源的最大需求量之和小于m+n。则该系统不会因竞争该类资源而阻塞。
并发程序设计的特性
- 并行性
- 共享性
- 交往性
进程间关系：竞争和协作
Bernstein条件
- R(pi)={ai1,ai2,…ain}，程序pi在执行期间引用的变量集
- W(pi)={bi1,bi2,…bim}，程序pi在执行期间改变的变量集
- 若两个进程的程序p1和p2能满足Bernstein条件，即满足：
((R(p1)∩W(p2))∪(R(p2)∩W(p1))∪(W(p1)∩W(p2))= 空集
则并发进程的执行与时间无关
临界资源：互斥共享变量所代表的资源。即一次只能被一个进程使用的资源
临界区指并发进程中与互斥共享变量相关的程序段
Peterson算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18bool inside[2];
inside[0] = inside[1] = false;
enum {0, 1} turn;
cobegin
process P0() {
inside[0] = true;
turn = 1;
while (inside[1] && turn == 1);
{临界区}
inside[0] = false;
}
process P1() {
inside[1] = true;
turn = 0;
while (inside[0] && turn == 0);
{临界区}
inside[1] = false;
}实现临界区管理的硬件设施
- 关中断
- 测试并建立指令
- 对换指令
PV操作数据结构及操作伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16typedef struct semaphore {
int value;
struct pcb* list;
}
void P(semaphore s) {
s.value--;
if (value < 0) {
sleep(s.list);
}
}
void V(semaphore s) {
s.value++;
if (s.value <= 0) {
wakeup(s.list);
}
}为什么要引入管程？
- 把分散在各进程中的临界区集中起来进行管理
- 防止进程有意或无意的违法同步操作
- 便于用高级语言来书写程序
- 进程直接通信
- 对称直接寻址，发送进程和接收进程必须命名对方以便通信
- 非对称直接寻址，只要发送者命名接收者，而接收者不需要命名发送者
- 进程间接通信
- 消息不是直接从发送者发送到接收者，而是发送到由临时保存这些消息的队列组成的一个共享数据结构，这些队列通常成为信箱(mailbox)
- 一个进程给合适的信箱发送消息，另一进程从信箱中获得消息
- 高级通信机制
- 管道/多路转接器/套接字
- 远程过程调用RPC
- 死锁形成的四个必要条件
- 互斥条件(mutual exclusion)：系统中存在临界资源，进程应互斥地使用这些资源
- 占有和等待条件(hold and wait)：进程请求资源得不到满足而等待时，不释放已占有的资源
- 静态分配
- 不剥夺条件(no preemption)：已被占用的资源只能由属主释放，不允许被其它进程剥夺
- 剥夺式调度方法
- 循环等待条件(circular wait)：存在循环等待链，其中，每个进程都在链中等待下一个进程所持有的资源，造成这组进程永远等待
- 死锁防止（破坏循环等待条件）
- 层次分配策略
- 一个进程得到某一层的一个资源后，它只能再申请在较高层的资源
- 当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源
- 当一个进程获得了某一层的一个资源后，它想再申请该层中的另一个资源，那么，必须先释放该层中的已占资源
- 按序分配策略
- 把系统的所有资源排一个顺序，每个进程只能按序上锁
- 层次分配策略
- 死锁避免：银行家算法
- 死锁检测和解除
- 资源分配图
- 死锁定理：系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。
计算题
- 假定系统中有五个进程｛P0, P1, P2, P3, P4｝和三类资源｛A, B, C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。
| 资源情况 | Max | Allocation | Need | Available |
|---|---|---|---|---|
| 进程 | A B C | A B C | A B C | A B C |
| P0 | 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2 |
| P1 | 3 2 2 | 2 0 0 | 1 2 2 | |
| P2 | 9 0 2 | 3 0 2 | 6 0 0 | |
| P3 | 2 2 2 | 2 1 1 | 0 1 1 | |
| P4 | 4 3 3 | 0 0 2 | 4 3 1 |
（1）利用下表来对T0 时刻系统是否为安全状态进行分析。检验T0 时刻系统是否为安全状态，若是在安全状态，请给出一个安全序列。
| 资源情况 | Work | Need | Allocation | Work+ Allocation | Finish |
|---|---|---|---|---|---|
| 进程 | A B C | A B C | A B C | A B C | |
（2）在T0时刻如果进程P1发出请求向量Request1(1，0，2)，是否能实现安全分配？为什么？(画表进行分析)
答：
（1）
| 资源情况 进程 | Work | Need | Allocation | Work+ Allocation | Finish |
|---|---|---|---|---|---|
| A B C | A B C | A B C | A B C | ||
| P1 | 3 3 2 | 1 2 2 | 2 0 0 | 5 3 2 | true |
| P3 | 5 3 2 | 0 1 1 | 2 1 1 | 7 4 3 | true |
| P4 | 7 4 3 | 4 3 1 | 0 0 2 | 7 4 5 | true |
| P2 | 7 4 5 | 6 0 0 | 3 0 2 | 10 4 7 | true |
| P0 | 10 4 7 | 7 4 3 | 0 1 0 | 10 5 7 | true |
答：在T0时刻存在着一个安全序列{P1，P3，P4 ，P2 ，P0}，故系统是安全的。
（2）P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：
① Request1(1，0，2)≤Need1(1，2，2)
② Request1(1，0，2)≤Available1(3，3，2)
③ 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-15所示。
| 资源情况 进程 | Max | Allocation | Need | Available |
|---|---|---|---|---|
| A B C | A B C | A B C | A B C | |
| P0 | 7 5 3 | 0 1 0 | 7 4 3 | 2 3 0 |
| P1 | 3 2 2 | 3 0 2 | 0 2 0 | |
| P2 | 9 0 2 | 3 0 2 | 6 0 0 | |
| P3 | 2 2 2 | 2 1 1 | 0 1 1 | |
| P4 | 4 3 3 | 0 0 2 | 4 3 1 |
④ 再利用安全性算法检查此时系统是否安全。
因为分配后能存在这样的一个安全序列{P1，P3，P4，P0，P2} 所以，这次分配是安全的。
| 资源情况 进程 | Work | Need | Allocation | Work+ Allocation | Finish |
|---|---|---|---|---|---|
| A B C | A B C | A B C | A B C | ||
| P1 | 2 3 0 | 0 2 0 | 3 0 2 | 5 3 2 | true |
| P3 | 5 3 2 | 0 1 1 | 2 1 1 | 7 4 3 | true |
| P4 | 7 4 3 | 4 3 1 | 0 0 2 | 7 4 5 | true |
| P0 | 7 4 5 | 7 4 3 | 0 1 0 | 7 5 5 | true |
| P2 | 7 5 5 | 6 0 0 | 3 0 2 | 10 5 7 | true |
假定系统中有五个进程｛P1, P2, P3, P4, P5｝和三类资源｛A, B, C｝，各种资源的数量分别为17、5、20，在T0时刻的资源分配情况如图所示。
| 资源情况 | Max | Allocation | Need | Available（Work） |
| ———— | ————— | ————— | ————- | ————————- |
| 进程 | A B C | A B C | A B C | A B C |
| P1 | 5 5 9 | 2 1 2 | 3 4 7 | 2 3 3 |
| P2 | 5 3 6 | 4 0 2 | 1 3 4 | |
| P3 | 4 0 11 | 4 0 5 | 0 0 6 | |
| P4 | 4 2 5 | 2 0 4 | 2 2 1 | |
| P5 | 4 2 4 | 3 1 4 | 1 1 0 | |
（1）利用下表来对T0 时刻系统是否为安全状态进行分析。检验T0 时刻系统是否为安全状态，若是在安全状态，请给出一个安全序列。 （本问5分）
| 资源情况 进程 | Work | Need | Allocation | Work+ Allocation | Finish |
|---|---|---|---|---|---|
| A B C | A B C | A B C | A B C | ||
（2）在T0时刻如果进程P1发出请求向量Request1(1，2，3)，是否能实现安全分配？为什么？(画表进行分析) （本问10分）
参考答案：
（1） （本问5分）
| 资源情况 进程 | Work | Need | Allocation | Work+ Allocation | Finish |
|---|---|---|---|---|---|
| A B C | A B C | A B C | A B C | ||
| P4 | 2 3 3 | 2 2 1 | 2 0 4 | 4 3 7 | True |
| P5 | 4 3 7 | 1 1 0 | 3 1 4 | 7 4 11 | True |
| P1 | 7 4 11 | 3 4 7 | 2 1 2 | 9 5 13 | True |
| P2 | 9 5 13 | 1 3 4 | 4 0 2 | 13 5 15 | True |
| P3 | 13 5 15 | 0 0 6 | 4 0 5 | 17 5 20 | True |
答：在T0时刻存在着一个安全序列{P4，P5，P1 ，P2 ，P3}，故系统是安全的。
（2）P1请求资源：P1发出请求向量Request1(1，2，3)，系统按银行家算法进行检查：
① Request1(1，2，3)≤Need1(2，2，1)
② Request1(1，2，3)≤Available(2，3，3)
③ 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如下图所示。
| 资源情况 进程 | Max | Allocation | Need | Available（Work） |
|---|---|---|---|---|
| A B C | A B C | A B C | A B C | |
| P1 | 5 5 9 | 3 3 5 | 2 2 4 | 1 1 0 |
| P2 | 5 3 6 | 4 0 2 | 1 3 4 | |
| P3 | 4 0 11 | 4 0 5 | 0 0 6 | |
| P4 | 4 2 5 | 2 0 4 | 2 2 1 | |
| P5 | 4 2 4 | 3 1 4 | 1 1 0 |
④ 再利用安全性算法检查此时系统是否安全。
因为分配后能存在这样的一个安全序列{P5，P1，P2，P3，P4} 所以，这次分配是安全的。
| 资源情况 进程 | Work | Need | Allocation | Work+ Allocation | Finish |
|---|---|---|---|---|---|
| A B C | A B C | A B C | A B C | ||
| P5 | 1 1 0 | 1 1 0 | 3 1 4 | 4 2 4 | true |
| P1 | 4 2 4 | 2 2 4 | 3 3 5 | 7 5 9 | true |
| P2 | 7 5 9 | 1 3 4 | 4 0 2 | 11 5 11 | true |
| P3 | 11 5 11 | 0 0 6 | 4 0 5 | 15 5 16 | true |
| P4 | 15 5 16 | 2 2 1 | 2 0 4 | 17 5 20 | true |
某请求分页系统的局部页面置换策略如下：
系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。
假设不考虑其它进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的 <虚拟页号，访问时刻> 是：<1, 1>、<3, 2>、<0, 4>、<0, 6>、<1, 11>、<0, 13>、<2, 14>。请回答下列问题。
（1）访问 <0, 4> 时，对应的页框号是什么？说明理由。
（2）访问 <1, 11> 时，对应的页框号是什么？说明理由。
（3）访问 <2, 14> 时，对应的页框号是什么？说明理由。
（4）该策略是否适合于时间局部性好的程序？说明理由。
答案：
（1）页框号是21。
由于初始时进程驻留集为空，目前系统空闲页框链表中页框号依次为32、15、21、41。因此，访问<1, 1>时，将1号页装入32号页框，访问<3, 2>时，将3号页装入15号页框，访问<0, 4>时，将0号页装入21号页框。
（2）页框号是32。
因为访问 <1, 1> 时，1号页被装入32号页框，但在10时刻进行第2轮扫描时，1号页所在的32号页框由于在本轮未被访问而被系统收回，访问 <1, 11> 时，1号页所在的32号页框仍在空闲页框链表中，因此重新被放回进程的驻留集中。
（3）页框号是41。
因为2号页是首次访问，14时刻系统空闲页框链表中页框号依次为41、15，因此将取出链首的41号页框装入2号页。
（4）该策略适合于时间局部性好的程序。
因为置换时，选择的是最近未被访问的页面淘汰，根据局部性原理，这样的页面在最近的将来仍可能不被访问。而且即使刚被淘汰的页面又被访问，如果该页还在空闲页框链表中，只需重新将其放回进程的驻留集中即可。
