北林操作系统期末考试.pdf

操作操作系统系统 考试题型 考试题型 n 概念题 概念题 1212 分分 4 4 题题 n 简答题 简答题 3 35 5 分分 5 5 题题 n 计算题 计算题 1 13 3 分分 2 2 题 题 n 选择题 选择题 1515 分分 1515 题题 n 判断题 判断题 1010 分分 1010 题题 n 填空题 填空题 1 15 5 分分 1 15 5 题题 天涯古巷天涯古巷 出品出品 PartI PartI 概念题概念题 n 题型题型1 1 原语原语 原语 是由若干条原语 是由若干条机器指令机器指令构成的用于完成特定功能的一段构成的用于完成特定功能的一段程序程序 n 题型题型2 2 进程 线程进程 线程 进程进程 是是具有具有独立功能独立功能的的程序程序关于某个数据集合关于某个数据集合上的一次运行活动 是上的一次运行活动 是系统进行资源分配和调度的系统进行资源分配和调度的 独立单位独立单位 线程 是线程 是进程的一个实体进程的一个实体 是 是 CPUCPU 调度的基本单位调度的基本单位 不拥有系统资源 它与同属同一个进程的 不拥有系统资源 它与同属同一个进程的其其 他线程共享进程所拥有的全部资源 他线程共享进程所拥有的全部资源 n 题型题型3 3 死锁死锁 死锁 如果一个进程集合中的死锁 如果一个进程集合中的每个进程每个进程都在等待只能由该集合中的其他一个进程才能引发的事件 都在等待只能由该集合中的其他一个进程才能引发的事件 则称这一组进程或系统此时发生了死锁 则称这一组进程或系统此时发生了死锁 n 题型题型4 4 虚拟存储虚拟存储 虚拟存储虚拟存储 利用 利用大容量的外存来扩充内存大容量的外存来扩充内存 产生一个比 产生一个比有限的实际内存空间大得多的 有限的实际内存空间大得多的 逻辑的逻辑的虚拟虚拟 内存空间 简称虚存 内存空间 简称虚存 n 题型题型5 5 地址映射地址映射 地址映射 将用户程序中的地址映射 将用户程序中的逻辑地址逻辑地址转换为转换为运行时由机器直接寻址的运行时由机器直接寻址的物理地址物理地址 n 题型题型6 6 内存交换 颠簸 抖动 内存交换 颠簸 抖动 内存交换 多个程序并发执行 将暂时不能执行的程序送到外存中 从而获内存交换 多个程序并发执行 将暂时不能执行的程序送到外存中 从而获得内存空间来装入新程得内存空间来装入新程 序 或读入达就绪状态的进程 交换单位为整个进程的地址空间 序 或读入达就绪状态的进程 交换单位为整个进程的地址空间 颠簸 抖动 颠簸 抖动 在虚存中 页面在内存与外存之间频繁调度 以至于调度页面所需时间比进程实际在虚存中 页面在内存与外存之间频繁调度 以至于调度页面所需时间比进程实际 运行的时间还多 此时系统效率急剧下降 甚至导致系统崩溃 这种现象称为颠簸运行的时间还多 此时系统效率急剧下降 甚至导致系统崩溃 这种现象称为颠簸 或抖动 或抖动 n 题型题型7 7 文件和目录文件和目录 文件 是指具有符号名的数据信息的集合 文件 是指具有符号名的数据信息的集合 目录 文件系统层次结构的一个非终结节点 一个目录通常包含有许多目录项 每个目录项可以是目录 文件系统层次结构的一个非终结节点 一个目录通常包含有许多目录项 每个目录项可以是 一个文件或目录 文件控制块或目录的有序集合 一个文件或目录 文件控制块或目录的有序集合 n 题型题型8 8 系统态和用户态系统态和用户态 系统态系统态 系统 系统程序工作的状态称为管态或系统态程序工作的状态称为管态或系统态 用户用户态态 用户工作的状态称为算态或用户态 用户工作的状态称为算态或用户态 n 题型题型9 9 系统调用系统调用 系统调用 指系统为用户程序调用操作系统核心实现系统功能的过程 系统调用 指系统为用户程序调用操作系统核心实现系统功能的过程 考试题 考试题 1 1 请简述以下名词的概念 共 请简述以下名词的概念 共 4 4 题 每题题 每题 3 3 分 分 原语原语 文件和目录文件和目录 虚拟存储虚拟存储 地址映射地址映射 2 2 请简述以下名词的概念 共 请简述以下名词的概念 共 4 4 题 每题题 每题 3 3 分 分 进程 进程 线程线程 内存交换 颠簸 抖动 内存交换 颠簸 抖动 系统调用系统调用 死锁死锁 系统态和用户态系统态和用户态 PartII PartII 简答简答题题 n 题型题型1 1 程序 进程 线程的基本概念及区别程序 进程 线程的基本概念及区别 1 1 基本概念 基本概念 进程 具有独立功能的程序关于某个数据集合上的一次运行活动 是系统进行资源分配和调度的独进程 具有独立功能的程序关于某个数据集合上的一次运行活动 是系统进行资源分配和调度的独 立单位 立单位 线程 是进程的一个实体 是线程 是进程的一个实体 是 CPUCPU 调度的基本单位 不拥有系统资源 它与同属同一个进程的其调度的基本单位 不拥有系统资源 它与同属同一个进程的其 他线程共享进程所拥有的全部资源 他线程共享进程所拥有的全部资源 程序 程序是一组指令的有序集合 程序 程序是一组指令的有序集合 2 2 区别 区别 进程与程序的区别 进程与程序的区别 进程进程是是动态动态的 的 程序程序是是静态静态的 的 进程能 进程能真实描述真实描述并发执行并发执行 程序不能 程序不能 进程是暂时的 进程是暂时的 程序是永久的 程序是永久的 进程可以创建其它进程 进程可以创建其它进程 程序不能 程序不能 进程通常不可在计算机之间迁移 程序对应的文件是静态 和可复制的 进程通常不可在计算机之间迁移 程序对应的文件是静态 和可复制的 进程和线程的区别 进程和线程的区别 资源资源分配分配 进程 是资源分配的基本单位 进程 是资源分配的基本单位 线程线程 与资源分配无关 与资源分配无关 只属于某一个进程 并与进程内其他线程一起共享进程的资源 只属于某一个进程 并与进程内其他线程一起共享进程的资源 调度 调度 进程进程 发生调度时 不同的进程拥有不同的虚拟地址空间 发生调度时 不同的进程拥有不同的虚拟地址空间 线程 线程 发生调度时 发生调度时 同一进程内的不同线程共享同一地址空间 同一进程内的不同线程共享同一地址空间 切换切换 进程进程 切换时将涉及到有关资源指针的保存以及地址空间的变化等问题 切换时将涉及到有关资源指针的保存以及地址空间的变化等问题 线程线程 切切换时 由于同一进程内的线程共享资源和地址空间 将不涉及上述内容的保存 换时 由于同一进程内的线程共享资源和地址空间 将不涉及上述内容的保存 故减少了操作系统的开销时间 故减少了操作系统的开销时间 调度与切换调度与切换的完成的完成 进程进程 调度与切换都是由操作系统内核完成 调度与切换都是由操作系统内核完成 线程线程 既可由操作系统内核完成 也可由用户程序进行 既可由操作系统内核完成 也可由用户程序进行 组成 组成 进程进程 包含了包含了 PCBPCB 用户地址空间和堆栈 用户地址空间和堆栈 线程线程 只由相关的堆栈 用户栈和系统栈 寄存器和线程控制表只由相关的堆栈 用户栈和系统栈 寄存器和线程控制表 TCBTCB 组成 组成 n 题型题型2 2 进程的组成 基本状态 三状态模型 五状态模型进程的组成 基本状态 三状态模型 五状态模型 1 1 进程的组成进程的组成 程序 作用 描述进程要完成的功能 程序 作用 描述进程要完成的功能 数据集合 作用 程序在执行时所需要的数据和工作区 数据集合 作用 程序在执行时所需要的数据和工作区 程序控制块 程序控制块 PCBPCB 作用 包含进程的描述信息和控制信息 它是进程存在的唯一标志 作用 包含进程的描述信息和控制信息 它是进程存在的唯一标志 2 2 基本状态 基本状态 运行状态 占用处理机资源 运行状态 占用处理机资源 暂停状态 等待进程调度分配处理机资源 暂停状态 等待进程调度分配处理机资源 3 3 三状态模型三状态模型 就绪态 一个进程已经具备运行条件 当调度给其就绪态 一个进程已经具备运行条件 当调度给其 CPUCPU 时 立即可以运行 时 立即可以运行 运行态 执行状态 运行态 执行状态 阻塞态 指进程因等待某种事件的发生而暂时不能运行的状态 阻塞态 指进程因等待某种事件的发生而暂时不能运行的状态 4 4 五状态模型五状态模型 就绪就绪状态状态 运行运行状态状态 阻塞阻塞状态状态 创建创建 新建 新建 状态状态 退出退出 终止 终止 状态状态 n 题型题型3 3 临界资源 临界区 临界区访问原则临界资源 临界区 临界区访问原则 1 1 临界资源临界资源 一一次仅供一个进程使用的资源 次仅供一个进程使用的资源 2 2 临界区临界区 在进程中涉及到临界资源的程序段 在进程中涉及到临界资源的程序段 3 3 临界区的访问原则 临界区的访问原则 空闲让进 当无进程在临界区时 任何有权使用临界区的进程可进入空闲让进 当无进程在临界区时 任何有权使用临界区的进程可进入 忙则等待 不允许两个以上的进程同时进入临界区忙则等待 不允许两个以上的进程同时进入临界区 多中择一 当没有进程在临界区 而同时有多个进程要求进入临界区 只能让其中之一进多中择一 当没有进程在临界区 而同时有多个进程要求进入临界区 只能让其中之一进 入临界区 其他进程必须等待入临界区 其他进程必须等待 有限等待 任何进入临界区的要求应在有限的时间内得到满足有限等待 任何进入临界区的要求应在有限的时间内得到满足 让权等待 处于等待状态的进程应放弃占用让权等待 处于等待状态的进程应放弃占用 CPUCPU 以使其他进程有机会得到 以使其他进程有机会得到 CPUCPU 使用权使用权 n 题型题型4 4 四种数四种数据传送控制方式的工作过程 设备管理 据传送控制方式的工作过程 设备管理 1 1 程序直接控制方式程序直接控制方式 工作过程 工作过程 外围设备接收到外围设备接收到 CPUCPU 的的 startstart 命令 开始准备接收或发送数据 命令 开始准备接收或发送数据 设备标志位触发器置 设备标志位触发器置 donedone 时 时 CPUCPU 才执行下条指令开始数据传送 才执行下条指令开始数据传送 2 2 中断方式 中断方式 工作过程 工作过程 外围设备接收到外围设备接收到 CPUCPU 的的 startstart 命令 准备数据并将其置入缓冲寄存器 命令 准备数据并将其置入缓冲寄存器 数据缓冲寄存区满后 设备控制器发中断请求 数据缓冲寄存区满后 设备控制器发中断请求 CPUCPU 进行中断处理 进行中断处理 3 3 DMADMA 方式 方式 工作过程 工作过程 DMADMA 控制器接受控制器接受 startstart 命令命令 启动设备准备数据 启动设备准备数据 数据入数据缓冲寄存器 数据入数据缓冲寄存器 缓冲 缓冲寄存器内容入内存 寄存器内容入内存 改变传送 改变传送字节计数器字节计数器和和内存地址寄存器内存地址寄存器内容 内容 发发中断信号 中断信号 停止停止 I OI O 操作操作 4 4 通道控制方式通道控制方式 工作过程 工作过程 CPUCPU 执行用户程序 当遇到 执行用户程序 当遇到 I OI O 请求时 可根据该请求生成通道程序放入内存 请求时 可根据该请求生成通道程序放入内存 并将该通道程序的首地址放入并将该通道程序的首地址放入 CAWCAW 中 之后执行 启动中 之后执行 启动 I OI O 指令 启动通道工作 指令 启动通道工作 通道 接收到通道 接收到 启动启动 I OI O 指令后 从指令后 从 CAWCAW 中取出通道程序的首地址 并根据首地中取出通道程序的首地址 并根据首地 址取出第一条指令放入址取出第一条指令放入 CCWCCW 中 同时向中 同时向 CPUCPU 发回答信号 使发回答信号 使 CPUCPU 可继续执行其他程序 而通道则可继续执行其他程序 而通道则 开始执行通道程序 完成传输工作 开始执行通道程序 完成传输工作 当通道传输完成最后当通道传输完成最后一条指令时 向一条指令时 向 CPUCPU 发发 I OI O 中断 并且通道停止工作 中断 并且通道停止工作 CPUCPU 接收中断信号 接收中断信号 从从 CSWCSW 中取得有关信息 决定下一步做什么 中取得有关信息 决定下一步做什么 n 题型题型5 5 页式 段式 段页式的工作原理及区别页式 段式 段页式的工作原理及区别 1 1 页式管理的工作 页式管理的工作原理原理 把用户程序划分成把用户程序划分成大小相等的页大小相等的页 从 从 0 0 开始编制页号 页内地址是相对于开始编制页号 页内地址是相对于 0 0 编址进程 虚拟编址进程 虚拟 地址为页号地址为页号 P P 与页内地址与页内地址 W W 组成 内存空间也按页的大小划分为大小相等的内存块 以页为单位进组成 内存空间也按页的大小划分为大小相等的内存块 以页为单位进 行分配 并按作业的页数多少来分配 行分配 并按作业的页数多少来分配 逻辑上相邻的页 物理上不一定相邻逻辑上相邻的页 物理上不一定相邻 通过页表把作业的各 通过页表把作业的各 个页面与页框对应起来 个页面与页框对应起来 2 2 段段式管理的工作式管理的工作原理原理 按程序自身的逻辑关系划分按程序自身的逻辑关系划分为若干程序段 每个程序段都有一个段名 且有一个段号 段号为若干程序段 每个程序段都有一个段名 且有一个段号 段号 从从 0 0 开始 每一段也从开始 每一段也从 0 0 开始编址 段内地址是连续的 虚拟地址为段号开始编址 段内地址是连续的 虚拟地址为段号 P P 与段内地址与段内地址 W W 组成 组成 内存空间被动态的划分为内存空间被动态的划分为若干个长度不相同的物理段若干个长度不相同的物理段 以段为单位分配内存 每一个段在内存中 以段为单位分配内存 每一个段在内存中占占 据连续空间据连续空间 内存随机分割 需要多少分配多少 但各段之间可以不连续存放 内存随机分割 需要多少分配多少 但各段之间可以不连续存放 3 3 段页段页式管理的工作式管理的工作原理原理 按程序的逻辑关系划分为段 并有各自的段号按程序的逻辑关系划分为段 并有各自的段号 s s 对于段 对于段 s s 中的程序或数据 则按照一定的大中的程序或数据 则按照一定的大 小将其划分为不同的页 虚拟地址由段号小将其划分为不同的页 虚拟地址由段号 s s 页号 页号 p p 和页内地址 和页内地址 w w 三个部分组成 将存储空间分三个部分组成 将存储空间分 成大小固定的页 一成大小固定的页 一个段中的程序或数据在内存中可以分开存放与不相邻的页 个段中的程序或数据在内存中可以分开存放与不相邻的页 4 4 分页与分段的主要区别 分页与分段的主要区别 透明透明 可见可见 页页 对用户是透明的 对用户是透明的 段段 对用户是可见的 对用户是可见的 大小大小 页页 大小固定不变 由系统决定 大小固定不变 由系统决定 段段 大小是不固定的 它由其完成的功能决定 大小是不固定的 它由其完成的功能决定 空间维度空间维度 页 页 向用户提供的是一维地址空间 其页号和页内偏移是机器硬件的功能 向用户提供的是一维地址空间 其页号和页内偏移是机器硬件的功能 段 向用户提供的是二维地址空间 段 向用户提供的是二维地址空间 保护保护 共享共享 页页 保护和共享受到限制 保护和共享受到限制 段段 是信息是信息的逻辑单位 因此便于存贮保护和信息的共享 的逻辑单位 因此便于存贮保护和信息的共享 n 题型题型6 6 P VP V操作的基本概念及基本工作机制操作的基本概念及基本工作机制 1 1 P P V V 操作的基本概念操作的基本概念 P S P S 表示申请一个资源 表示申请一个资源 P P 操作 操作 1 1 s s 减减 1 1 2 2 若 若 s s 减减 1 1 后仍大于等于后仍大于等于 0 0 则进程继续执行 则进程继续执行 3 3 若结果小于 若结果小于 0 0 则该进程睡眠 进入等待队列 则该进程睡眠 进入等待队列 V S V S 表示释放一个资源 表示释放一个资源 V V 操作 操作 1 1 s s 值加值加 1 1 2 2 若相加结果大于 若相加结果大于 0 0 进程继续执行 进程继续执行 3 3 否则 唤醒一个等待队列中的进程 然后本进程继续执行 否则 唤醒一个等待队列中的进程 然后本进程继续执行 2 2 基本工作机制 基本工作机制 P P V V 操作必须成对出现 有一个操作必须成对出现 有一个 P P 操作就一定有一个操作就一定有一个 V V 操作操作 当为互斥操作时 它们同处于同一进程当为互斥操作时 它们同处于同一进程 当为同步操当为同步操作时 则不在同一进程中出现作时 则不在同一进程中出现 如果如果 P S1 P S1 和和 P S2 P S2 两个操作在一起 那么两个操作在一起 那么 P P 操作的顺序至关重要 一个同步操作的顺序至关重要 一个同步 P P 操作与一个操作与一个 互斥互斥 P P 操作在一起时同步操作在一起时同步 P P 操作在互斥操作在互斥 P P 操作前 而两个操作前 而两个 V V 的顺序的顺序无关紧要无关紧要 n 题型题型7 7 连续 随机 串联的文件保存方式连续 随机 串联的文件保存方式 1 1 连续文件 顺序结构 连续文件 顺序结构 保存方式保存方式 文文件的信息存放在若干连续的物理块中 件的信息存放在若干连续的物理块中 2 2 串联文件 链接结构 串联文件 链接结构 保存方式保存方式 文件的信息存放在若干连续的物理块中 通过指针链接 前一个物理块指向下一个物理块 文件的信息存放在若干连续的物理块中 通过指针链接 前一个物理块指向下一个物理块 3 3 随机文件 索引结构 随机文件 索引结构 保存方式保存方式 一个文件的信息存放在若干不连续物理块中 系统为每个文件一个文件的信息存放在若干不连续物理块中 系统为每个文件建立一个索引表 并将这些块建立一个索引表 并将这些块 的块号存放在索引表中 的块号存放在索引表中 n 题型题型8 8 操作系统的各项基本功能以及操作系统的发展阶段操作系统的各项基本功能以及操作系统的发展阶段 1 1 操作系统的操作系统的基本基本功能功能 处理机管理 处理机管理 完成处理机资源的分配调度等功能 单位可为进程 完成处理机资源的分配调度等功能 单位可为进程 存储管理 存储管理 提高利用率 方便用户使用 提供足够的存储空间 方便进程并发运行 提高利用率 方便用户使用 提供足够的存储空间 方便进程并发运行 设备管理 设备管理 方便设备使用 提高 方便设备使用 提高 CPUCPU 与与 I OI O 设备利用率 设备利用率 文件管理 文件管理 解决软件资源的存储 共享 保密和保护 解决软件资源的存储 共享 保密和保护 用户接口用户接口 提供一个友好的用户访问操作系统的接口 提供一个友好的用户访问操作系统的接口 2 2 操作系统发展史 操作系统发展史 19461946 5050 年代 无操作系统时代 工作环境年代 无操作系统时代 工作环境 是电子管计是电子管计算机算机 5050 6060 年代 单道批处理系统年代 单道批处理系统 6060 年代中年代中 7070 年代 多道批处理系统年代 多道批处理系统 7070 年代中期至今 分时系统年代中期至今 分时系统 个人计算机个人计算机 考试题 考试题 1 1 页式存储与段式存储的区别主要在于哪些方面 页式存储与段式存储的区别主要在于哪些方面 2 2 请给出记录型信号量中对请给出记录型信号量中对 P P V V 操作的定义操作的定义 用伪代码描述 用伪代码描述 3 3 简述 简述四种数据传送控制方式及四种数据传送控制方式及其其设备管理设备管理的工作过程 的工作过程 4 4 简述 简述连续 随机 串联的文件保存方式连续 随机 串联的文件保存方式 5 5 操作系统的操作系统的基本功能基本功能有哪些 有哪些 操作系统的发展阶段操作系统的发展阶段分为哪几阶段 分为哪几阶段 6 6 什么是 什么是临界资源 临界区 临界区访问原则临界资源 临界区 临界区访问原则 7 7 简单说明简单说明程序 进程 线程的基本概念及区别程序 进程 线程的基本概念及区别 8 8 进程的组成 基本状态 三状态模型 五状态模型进程的组成 基本状态 三状态模型 五状态模型 PartIII PartIII 计算题计算题 n 题型题型1 1 多道程序的多道程序的CPUCPU调度算法调度算法 考试题 考试题 1 1 一一个计算机系统 有一台输入机和一台打印机 现有两道程序投入运行 且程序个计算机系统 有一台输入机和一台打印机 现有两道程序投入运行 且程序 A A 先开始做 先开始做 程序程序 B B 后开始运行 程序后开始运行 程序 A A 的运行轨迹为 计算的运行轨迹为 计算 50ms50ms 打印 打印 100ms100ms 再计算 再计算 50ms50ms 打印 打印 100ms100ms 结束 程序结束 程序 B B 的运行轨迹为 计算的运行轨迹为 计算 50ms50ms 输入 输入 80ms80ms 再计算 再计算 100ms100ms 结束 试说明 结束 试说明 1 1 两道程序两道程序 运行时 运行时 CPUCPU 有无空闲等待 若有 在哪段时间内等待 为什么会等待 有无空闲等待 若有 在哪段时间内等待 为什么会等待 2 2 程序程序 A A B B 有无等待有无等待 CPUCPU 的情况 若有 指出发生等待的时刻 的情况 若有 指出发生等待的时刻 答 画出两道程序并发执行图如下 答 画出两道程序并发执行图如下 1 1 两道程序运行期间 两道程序运行期间 C CPUPU 存在空闲等待 时间为存在空闲等待 时间为 100100 至至 150ms150ms 之间之间 见图中有色部分见图中有色部分 2 2 程序程序 A A 无等待现象 但程序无等待现象 但程序 B B 有等待 程序有等待 程序 B B 有等待时间段为有等待时间段为 180ms180ms 至至 200ms200ms 间间 见图中有色见图中有色 部分部分 2 2 在单在单 CPUCPU 和两台和两台 I O I1 I2 I O I1 I2 设备的多道程序设计环境下 同时投入三个作业运行 它们的执设备的多道程序设计环境下 同时投入三个作业运行 它们的执 行轨迹如下 行轨迹如下 Job1Job1 I2 30ms I2 30ms CPU 10ms CPU 10ms I1 30ms I1 30ms CPU 10ms CPU 10ms Job2Job2 I1 20ms I1 20ms CPU 20ms CPU 20ms I2 40ms I2 40ms Job3Job3 CPU 30ms CPU 30ms I1 20ms I1 20ms 如如果果 CPUCPU I1I1 和和 I2I2 都能并行工作 优先级从高到低为都能并行工作 优先级从高到低为 Job1Job1 Job2Job2 和和 Job3Job3 优先级高的作业可以 优先级高的作业可以 抢占优先级低的作业的抢占优先级低的作业的 CPUCPU 试求 试求 1 1 每个作业从投入到完成分别所需的时间 每个作业从投入到完成分别所需的时间 2 2 从作业的投从作业的投 入到完成入到完成 CPUCPU 的利用率 的利用率 3 I O 3 I O 设备利用率 设备利用率 答 画出三个作业并行工作图如下答 画出三个作业并行工作图如下 图中着色部分为作业等待时间图中着色部分为作业等待时间 1 Job1 1 Job1 从投入到运行完成需从投入到运行完成需 80ms80ms Job2Job2 从投入到运行完成需从投入到运行完成需 90ms90ms Job3Job3 从投入到运行完成从投入到运行完成 需需 90ms90ms 2 2 CPUCPU 空闲时间段为 空闲时间段为 60ms60ms 至至 70ms70ms 80ms80ms 至至 90ms90ms 所以 所以 CPUCPU 利用率为利用率为 90 90 20 80 77 78 20 80 77 78 3 3 设备设备 I1I1 空闲时间段为 空闲时间段为 20ms20ms 至至 40ms40ms 故 故 I1I1 的利用率为的利用率为 90 90 20 90 77 78 20 90 77 78 设备 设备 I2I2 空闲空闲 时间段为 时间段为 30ms30ms 至至 50ms50ms 故 故 I2I2 的利用率为的利用率为 90 90 20 90 77 78 20 90 77 78 3 3 假定执行作业假定执行作业 Job1Job1 Job5Job5 作业号即为其到达顺序 依次在时刻 作业号即为其到达顺序 依次在时刻 0 0 按照序号按照序号 1 1 2 2 3 3 4 4 5 5 进入单处理器系统 进入单处理器系统 作业号作业号 执行时间执行时间 ms ms 优先权优先权 Job1 10 Job1 10 3 3 Job2 1 1Job2 1 1 Job3 2 3Job3 2 3 Job4 1 4Job4 1 4 Job5 5 2Job5 5 2 1 1 分别采用先来先服务调度算法 时间片轮转算法 时间片为 分别采用先来先服务调度算法 时间片轮转算法 时间片为 1ms1ms 短作业优先算法及非抢占 短作业优先算法及非抢占 式优先权调度算法 计算出各作业的执行次序 注意 优先权越高 其数值越小 式优先权调度算法 计算出各作业的执行次序 注意 优先权越高 其数值越小 2 2 计算每种情况下作业的平均周转时间和平均带权周转时间 计算每种情况下作业的平均周转时间和平均带权周转时间 答 答 1 1 采用先来先服务调度算法采用先来先服务调度算法 执行次序执行次序 执行时间执行时间 等待时间等待时间 开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 J Job1ob1 J Job2ob2 J Job3ob3 J Job4ob4 J Job5ob5 1010 1 1 2 2 1 1 5 5 0 0 1010 1111 1313 1414 0 0 1010 1111 1313 1414 1010 1111 1313 1414 1919 1010 1111 1313 1414 1919 1 1 1111 6 56 5 1414 3 83 8 作业平均周转时间作业平均周转时间 作业平均带权周转时间作业平均带权周转时间 13 413 4 7 267 26 2 2 采用时间片轮转算法 令时间片 采用时间片轮转算法 令时间片 1 1 各作业执行情况为 各作业执行情况为 12345135151515111111234513515151511111 执行次序执行次序 执行时间执行时间 完成时完成时间间 周转时间周转时间 带权周转时间带权周转时间 J Job1ob1 J Job2ob2 J Job3ob3 J Job4ob4 J Job5ob5 1010 1 1 2 2 1 1 5 5 1919 2 2 7 7 4 4 1414 1919 2 2 7 7 4 4 1414 1 91 9 2 2 3 53 5 4 4 2 82 8 作业平均周转时间作业平均周转时间 作业平均带权周转时间作业平均带权周转时间 9 29 2 2 842 84 3 3 短作业优先算法 短作业优先算法 执行次序执行次序 执行时间执行时间 等待时间等待时间 开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 J Job2ob2 J Job4ob4 J Job3ob3 J Job5ob5 J Job1ob1 1 1 1 1 2 2 5 5 1010 0 0 1 1 2 2 4 4 9 9 0 0 1 1 2 2 4 4 9 9 1 1 2 2 4 4 9 9 1919 1 1 2 2 4 4 9 9 1919 1 1 2 2 2 2 1 81 8 1 91 9 作业平均周转时间作业平均周转时间 作业平均带权周转时间作业平均带权周转时间 7 7 1 741 74 4 4 非抢占式优先权调度算法 非抢占式优先权调度算法 执行次序执行次序 优先数优先数 执行时间执行时间 等待时间等待时间 周转时间周转时间 带权周转时间带权周转时间 J Job2ob2 J Job5ob5 J Job1ob1 J Job3ob3 J Job4ob4 1 1 2 2 3 3 3 3 4 4 1 1 5 5 1010 2 2 1 1 0 0 1 1 6 6 1616 1818 1 1 6 6 1616 1818 1919 1 1 1 21 2 1 61 6 9 9 1919 作业平均周转时间作业平均周转时间 作业平均带权周转时间作业平均带权周转时间 1212 6 366 36 4 4 5 5 个批处理作业个批处理作业 A A 到到 E E 均已到达计算中心 其运行时间分别均已到达计算中心 其运行时间分别 2 2 4 4 6 6 8 8 和和 1010 分分钟 各自的优钟 各自的优 先级分别被规定为先级分别被规定为 1 1 2 2 3 3 4 4 和和 5 5 这里 这里 5 5 为最高级 对于为最高级 对于 1 1 时间片轮转算法 时间片轮转算法 2 2 优先数法 优先数法 3 3 短作业优先算法 短作业优先算法 4 4 先来先服务调度算法 先来先服务调度算法 按到达次序按到达次序 C C D D B B E E A A 在忽略进程切换时间的前提下 计算出平均作业周转时间 在忽略进程切换时间的前提下 计算出平均作业周转时间 对对 1 1 每个作业获得相同的 每个作业获得相同的 2 2 分分 钟长的时间片 对钟长的时间片 对 2 2 到 到 4 4 采用单道运行 直到结束 采用单道运行 直到结束 答 答 1 1 时间片轮转法时间片轮转法 2 2 优先级调度算法优先级调度算法 按次序按次序 A B C D E B C D EC D E D E EA B C D E B C D EC D E D E E 轮转执行 轮转执行 3 SJF 3 SJF 调度算法调度算法 4 FCFS 4 FCFS 调度算法调度算法 5 5 在单道批处理系统中 下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度 在单道批处理系统中 下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度 哪种算法性能较好 请完成下表 哪种算法性能较好 请完成下表 作业作业 提交时间提交时间 运行时间运行时间 开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 1 1 2 2 3 3 10 0010 00 1010 1010 10 2510 25 2 002 00 1 001 00 0 250 25 作业平均周转时间作业平均周转时间 作业平均带权周转时间作业平均带权周转时间 答 答 1 1 FIFOFIFO 算法算法 作业作业 提交时间提交时间 运行时间运行时间 开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 1 1 2 2 3 3 10 0010 00 1010 1010 10 2510 25 2 002 00 1 001 00 0 250 25 10 0010 00 12 0012 00 13 0013 00 12 0012 00 13 0013 00 13 2513 25 2 2 2 502 50 3 3 120 120120 120 170 60170 60 180 25180 25 作业平均周转时间作业平均周转时间 2 61 2 61 作业平均带权周转时间作业平均带权周转时间 3 68 3 68 2 2 HRRFHRRF 算法算法 作业作业 提交时间提交时间 运行时间运行时间 开始时间开始时间 完成时间完成时间 周转时间周转时间 带权周转时间带权周转时间 1 1 2 2 3 3 10 0010 00 1010 1010 10 2510 25 2 002 00 1 001 00 0 250 25 10 0010 00 12 2512 25 12 0012 00 12 0012 00 13 2513 25 1 12 252 25 2 2 3 153 15 2 2 120 120120 120 195 60195 60 120 25120 25 作业平均周转时间作业平均周转时间 2 41 2 41 作业平均带权周转时间作业平均带权周转时间 3 02 3 02 可见可见 HRRFHRRF 比比 FIFOFIFO 要好 要好 6 6 某多道程序设计系统供用户使用的主存为某多道程序设计系统供用户使用的主存为 100K100K 磁带机 磁带机 2 2 台 打印机台 打印机 1 1 台 采用可变分区内存台 采用可变分区内存 管理 采用静态方式分配外围设备 忽略用户作业管理 采用静态方式分配外围设备 忽略用户作业 I OI O 时间 现有作业序列如下 时间 现有作业序列如下 作业调度采用作业调度采用 FCFSFCFS 策略 优先分配主存低地址区且不准移动已在主存的作业 在主存中的各作策略 优先分配主存低地址区且不准移动已在主存的作业 在主存中的各作 业平分业平分 CPUCPU 时间 现求 时间 现求 1 1 作业被调度的先后次序作业被调度的先后次序 2 2 全部作业运行结束的时间全部作业运行结束的时间 3 3 作业平均周作业平均周 转时间为多少转时间为多少 4 4 最大作业周转时间为多少最大作业周转时间为多少 答 答 1 1 作业调度选择的作业次序为 作业作业调度选择的作业次序为 作业 1 1 作业 作业 3 3 作业 作业 4 4 作业 作业 2 2 和作业和作业 5 5 2 2 全部作业运行结束的时间全部作业运行结束的时间 9 309 30 3 3 周转时间 作业周转时间 作业 1 1 为为 3030 分钟 作业分钟 作业 2 2 为为 5555 分钟 作业分钟 作业 3 3 为为 4040 分钟 作业分钟 作业 4 4 为为 4040 分钟和分钟和 作业作业 5 5 为为 5555 分钟 分钟 4 4 平均作平均作业周转时间业周转时间 44 44 分钟 分钟 5 5 最大作业周转时间为最大作业周转时间为 5555 分钟 分钟 分析 本题综合测试了作业调度 进程调度 及对外设的竞争 主存的竞争 分析 本题综合测试了作业调度 进程调度 及对外设的竞争 主存的竞争 8 00 8 00 作业作业 1 1 到达 占有资源并调入主存运行 到达 占有资源并调入主存运行 8 20 8 20 作业作业 2 2 和和 3 3 同时到达 但作业同时到达 但作业 2 2 因分不到打印机 只能在后备队列等待 作业因分不到打印机 只能在后备队列等待 作业 3 3 资源满足 资源满足 可进主存运行 并与作业可进主存运行 并与作业 1 1 平分平分 CPUCPU 时间 时间 8 30 8 30 作业作业 1 1 在在 8 308 30 结束 释放磁带与打印机 但作业结束 释放磁带与打印机 但作业 2 2 仍不能执行 因不能移动而没有仍不能执行 因不能移动而没有 30KB30KB 的空闲区 继续等待 作业的空闲区 继续等待 作业 4 4 在在 8 308 30 到达 并进入主存执行 与作业到达 并进入主存执行 与作业 3 3 分享分享 CPUCPU 8 35 8 35 作作业业 5 5 到达 因分不到磁带机到达 因分不到磁带机 打印机 只能在后备队列等待 打印机 只能在后备队列等待 9 00 9 00 作业作业 3 3 运行结束 释放磁带机 此时作业运行结束 释放磁带机 此时作业 2 2 的主存及打印机均可满足 投入运行 作业的主存及打印机均可满足 投入运行 作业 5 5 到到 达时间晚 只能等待 达时间晚 只能等待 9 10 9 10 作业作业 4 4 运行结束 作业运行结束 作业 5 5 因分不到打印机 只能在后备队列继续等待 因分不到打印机 只能在后备队列继续等待 9 15 9 15 作业作业 2 2 运行结束 作业运行结束 作业 5 5 投入运行 投入运行 9 30 9 30 作业全部执行结束 作业全部执行结束 作业号作业号 进入输入井时间进入输入井时间 运行时间运行时间 主存需求量主存需求量 磁带需求磁带需求 打印机需求打印机需求 1 1 8 008 00 2525 分钟分钟 15K15K 1 1 1 1 2 2 8 208 20 1010 分钟分钟 30K30K 0 0 1 1 3 3 8 208 20 2020 分钟分钟 60K60K 1 1 0 0 4 4 8 308 30 2020 分钟分钟 20K20K 1 1 0 0 5 5 8 358 35 1515 分钟分钟 10K10K 1 1 1 1 n 题型题型2 2 FIFOFIFO LRULRU 考试题 考试题 1 1 在一个请求分页虚拟存储管理系统中 一个程序运行的页面走向是 在一个请求分页虚拟存储管理系统中 一个程序运行的页面走向是 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 61 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 分别使用分别使用 FIFOFIFO 和和 LRULRU 算法 对于分配给程序四个页框的情况 求出缺页中断次数和缺页中断率 算法 对于分配给程序四个页框的情况 求出缺页中断次数和缺页中断率 答 答 FIFOFIFO 1 1 2 2 3 3 4 4 2 2 1 1 5 5 6 6 2 2 1 1 2 2 3 3 7 7 6 6 3 3 2 2 1 1 2 2 3 3 6 6 1 1 2 2 3 3 4 4 4 4 4 4 5 5 6 6 2 2 1 1 1 1 3 3 7 7 6 6 6 6 2 2 1 1 1 1 3 3 3 3 1 1 2 2 3 3 3 3 3 3 4 4 5 5 6 6 2 2 2 2 1 1 3 3 7 7 7 7 6 6 2 2 2 2 1 1 1 1 1 1 2 2 2 2 2 2 3 3 4 4 5 5 6 6 6 6 2 2 1 1 3 3 3 3 7 7 6 6 6 6 2 2 2 2 1 1 1 1 1 1 2 2 3 3 4 4 5 5 5 5 6 6 2 2 1 1 1 1 3 3 7 7 7 7 6 6 6 6 缺页中断次数 缺页中断次数 1414 缺页中断率 缺页中断率 14 2014 20 LRULRU 1 1 2 2 3 3 4 4 2 2 1 1 5 5 6 6 2 2 1 1 2 2 3 3 7 7 6 6 3 3 2 2 1 1 2 2 3 3 6 6 1 1 2 2 3 3 4 4 2 2 1 1 5 5 6 6 2 2 1 1 2 2 3 3 7 7 6 6 3 3 2 2 1 1 2 2 3 3 6 6 1 1 2 2 3 3 4 4 2 2 1 1 5 5 6 6 2 2 1 1 2 2 3 3 7 7 6 6 3 3 2 2 1 1 2 2 3 3 1 1 2 2 3 3 4 4 2 2 1 1 5 5 6 6 6 6 1 1 2 2 3 3 7 7 6 6 3 3 3 3 1 1 2 2 1 1 1 1 3 3 4 4 2 2 1 1 5 5 5 5 6 6 1 1 2 2 2 2 7 7 6 6 6 6 6 6 1 1 缺页中断次数 缺页中断次数 1010 缺页中断率 缺页中断率 10 2010 20 2 2 对下述页面走向 对下述页面走向 7 7 0 0 1 1 2 2 0 0 3 3 0 0 4 4 2 2 3 3 0 0 3 3 2 2 1 1 2 2 0 0 1 1 7 7 0 0 1 1 当内 当内 存块数量为存块数量为 4 4 时 分别利用时 分别利用 LRULRU 和和 FIFOFIFO 置换算法求出缺页次数和缺页率 置换算法求出缺页次数和缺页率 3 3 对下述页面走向 对下述页面走向 1 1 2 2 3 3 4 4 2 2 1 1 5 5 6 6 2 2 1 1 2 2 3 3 7 7 6 6 3 3 2 2 1 1 2 2 3 3 6 6 当内 当内 存块数量为存块数量为 3 3 时 分别利用时 分别利用 LRULRU 和和 FIFIFOFO 置换算法求出缺页次数和缺页率 置换算法求出缺页次数和缺页率 n 题型题型3 3 银行家算法 银行家算法 考试题 考试题 1 1 某系统有某系统有 A A B B C C D D 四类资源可供五个进程四类资源可供五个进程 P1 P2 P3 P4 P5P1 P2 P3 P4 P5 共享 系统对这四类资源的拥共享 系统对这四类资源的拥 有量为 有量为 A A 类类 3 3 个 个 B B 类类 1414 个 个 C C 类类 1212 个 个 D D 类类 1212 个 进程对资源的需求和分配情况如下 个 进程对资源的需求和分配情况如下 进程进程 已占有资源已占有资源 最大需求数最大需求数 A A B B C C D D A A B B C C D D P1P1 0 0 0 0 1 1 2 2 0 0 0 0 1 1 2 2 P2P2 1 1 0 0 0 0 0 0 1 1 7 7 5 5 0 0 P3P3 1 1 3 3 5 5 4 4 2 2 3 3 5 5 6 6 P4P4 0 0 6 6 3 3 2 2 0 0 6 6 5 5 2 2 P5P5 0 0 0 0 1 1 4 4 0 0 6 6 5 5 6 6 按银行家算法回答下列问题 按银行家算法回答下列问题 1 1 现在系统中的各类资源还剩余多少 现在系统中的各类资源还剩余多少 4 4 分 分 2 2 现在系统是否处于安全状态 为什么 现在系统是否处于安全状态 为什么 6 6 分 分 3 3 如果现在进程 如果现在进程 P2P2 提出需要提出需要 A A 类资源类资源 0 0 个 个 B B 类资源类资源 4 4 个 个 C C 类资源类资源 2 2 个和个和 D D 类资源类资源 0 0 个 个 系统能否去满足它的请求 请说明原因 系统能否去满足它的请求 请说明原因 6 6 分分 答 答 1 1 A A 1 1 B B 5 5 C C 2 2 D D 0 0 2 2 needneed 矩阵为 矩阵为 P1P1 0 0 0 0 0 0 0 0 P2P2 0 0 7 7 5 5 0 0 P3P3 1 1 0 0 0 0 2 2 P4P4 0 0 0 0 2 2 0 0 P5P5 0 0 6 6 4 4 2 2 存在安全序列 如存在安全序列 如 P1P1 P3P3 P4P4 P5P5 P2P2 所以安全 所以安全 3 3 能 因为试探分配后 可用资源为 能 因为试探分配后 可用资源为 1 1 1 1 0 0 0 0 可找到安全序列 所以可分配 可找到安全序列 所以可分配 2 2 设系统中有设系统中有 3 3 种类型的资源种类型的资源 A B C A B C 和和 5 5 个进程个进程 P1 P2 P3 P4 P5 P1 P2 P3 P4 P5 A A 资源的数量为资源的数量为 1717 B B 资源的数量为资源的数量为 5