操作系统讲稿习题.ppt

作业分析 3 27 假设有四个作业 它们的提交时间和需要的计算时间如下表所示 这些作业在一台处理机上按单道方式运行 若采用下列三种作业调度算法 1 先来先服务 2 短作业优先 3 非抢占式的静态优先级调度算法 数值大者优先级最高 请分别给出这些作业的执行顺序和每个作业的周转时间 3 27作业 2 短作业优先分析 短作业优先执行顺序 J1 J4 J3 J2 3 非抢占式的静态优先级调度算法分析 静态优先级执行顺序 J1 J4 J2 J3 响应比高者优先调度算法分析 3 29 假设有四个作业 它们的提交时间和需要的计算时间如下表所示 这些作业在一台处理机上按单道方式运行 如采用响应比高者优先调度算法 请给出这些作业的执行顺序 响应比高者优先调度算法分析 第1道先调度 响应比Rp 1 等待时间 计算时间 3 44作业 3 44 设存在三个过程get copy和put分别对缓冲区S和T进行操作 其中put负责将数据块存入缓冲区S copy负责从缓冲区S读出数据并复制到缓冲区T中 get负责从缓冲区T中读出数据并打印 如下图所示 请用P V操作描述上述三个过程 putcopyget 缓冲区S 缓冲区T 解法 一 用二值信号量 wait sem 当sem为True 1 时 继续 并在后继处理中需要将True改为False 当sem为False 0 时 阻塞signal sem 当sem为False 0 时 改为True并唤醒一个阻塞者putcopyget 缓冲区S 缓冲区T 解法 一 用二值信号量 定义6个信号量 bufS或bufT仅为一个单元时 去掉互斥信号量semaphoremutexS mutexT True 同步信号量semaphoreemptyS emptyT True semaphorefullS fullT False 解法 一 用二值信号量 Put procedure BeginA producedata wait emptyS emptyS False wait mutexS mutex False putdatatobufs signal mutexS signal fullS gotoA end 解法 一 用二值信号量 Copy procedure bufSbufTBeginB wait fullS fullS False wait mutexS mutexS False wait emptyT emptyT False wait mutexT mutexT False copybufStobufT 解法 一 用二值信号量 bufSbufT copybufStobufT clearbufS signal mutexS signal mutexT signal emptyS signal fullT gotoB end 解法 一 用二值信号量 Copy procedure bufStempbufbufTBeginC wait fullS fullS False wait mutexS mutexS False copybufStotempbuf clearbufS signal mutexS signal emptyS 解法 一 用二值信号量 bufStempbufbufTwait emptyT emptyT False wait mutexT mutexT False copytempbuftobufT signal mutexT signal fullT gotoC end 解法 一 用二值信号量 Get procedure BeginD wait fullT fullT False wait mutexT mutexT False getdatafrombufT clearbufT signal mutexT signal emptyT printdata gotoD end 解法 二 用一般信号量 wait sem sem value 0继续 0继续 唤醒一个阻塞者 解法 二 用一般信号量 定义6个信号量 bufS或bufT仅为一个单元时 去掉互斥信号量semaphoremutexS mutexT 1 同步信号量semaphoreemptyS emptyT 1 semaphorefullS fullT 0 解法 二 用一般信号量 Put procedure BeginA producedata wait emptyS 去掉 emptyS False wait mutexS 去掉 mutex False putdatatobufS signal mutexS signal fullS gotoA end 解法 二 用一般信号量 Copy procedure bufSbufTBeginB wait fullS 去掉 fullS False wait mutexS 去掉 mutexS False wait emptyT 去掉 emptyT False wait mutexT 去掉 mutexT False copybufStobufT 解法 二 用一般信号量 bufSbufT copybufStobufT clearbufS signal mutexS signal mutexT signal emptyS signal fullT gotoB end 解法 二 用一般信号量 Copy procedure bufStempbufbufTBeginC wait fullS 去掉 fullS False wait mutexS 去掉 mutexS False copybufStotempbuf clearbufS signal mutexS signal emptyS 解法 二 用一般信号量 Get procedure BeginD wait fullT 去掉 fullT False wait mutexT 去掉 mutexT False getdatafrombufT clearbufT signal mutexT signal emptyT printdata gotoD end 3 46作业 3 46 A B两人共同使用一个报箱 该报箱每次仅能容纳一份报纸 A订阅 生活报 B订阅 晚报 分别由投递员C和D投递 请用P V操作描述他们的同步程序 报箱PC投PA取PD投PB取 生活报 晚报 3 46作业 信号量 samephoreempty 1 报箱有空位置samephorefullA 0 报箱中有 生活报 samephorefullB 0 报箱中有 晚报 3 46作业P V操作描述的同步模型 PC 投递员C投递 生活报 BeginC wait empty put 生活报 intomailbox signal fullA gotoC end 3 46作业P V操作描述的同步模型 PD 投递员D投递 晚报 BeginD wait empty put 晚报 intomailbox signal fullB gotoD end 3 46作业P V操作描述的同步模型 PA A取 生活报 BeginA wait fullA get 生活报 frommailbox signal empty gotoA end 3 46作业P V操作描述的同步模型 PB B取 晚报 BeginB wait fullB get 晚报 frommailbox signal empty gotoB end 3 52作业 3 52 一个系统中存在5个进程和4种共享资源 资源的当前分配和需求情况如下表所示 1 试问该状态是否安全 2 若进程P2提出资源请求 1 2 2 2 后 系统能否将资源分配给它 分析 已知Max n m Allocation n m Need n m 1 执行安全性检测算法 判是否存在一个执行进程序列 3 52作业 判得不存在一个执行进程序列 故该状态不安全 3 52作业 2 若进程P2提出资源请求Request2 1 2 2 2 后 系统能否将资源分配给它 答 Need 2 1 7 5 0 Available 1 6 2 2 Request2 4 Need 2 4 将出错返回不作资源分配 4 1MEM作业 4 1存储管理的目的是什么 存储管理主要讨论内存管理 目的 为用户提供方便 用户按程序逻辑编址 通过OS地址变换得到物理地址 安全内存共享 多道程序共享MEM资源互不干扰影响 和充分大 采用虚拟存储技术实现足够大 存储空间 有效地分配内存来保证有适当数目的就绪进程 可以占用这些可用的处理机时间 涉及 主存的分配与回收 地址映射 存储信息的保护和向用户提供虚拟存储等方面的问题 4 1MEM作业 4 2简单分页与虚拟内存分页有什么区别 页式管理的基本原理是 将内存分成若干块 每块所含的内存单元数目相等 一般等于2的整数次幂 内存块称为一个内存页 每页依次编号 程序的地址空间也分成若干大小相等的片 称为页面 又称为虚页 程序页面散列存放到内存页中 为了实现从程序地址空间到物理主存的映象 系统为各个进程建立记录页与内存块之间对应关系的地址变换的机构 称为页面映像表 简称页表 4 1MEM作业 4 2简单分页与虚拟内存分页有什么区别 区别 简单分页 程序一次性装入内存页中 物理块不足 则该作业必须等待 虚拟内存分页 需要内存时再请求 或置换后 调入方式 通常只将当前要用到的一部分放在主存中 内存空间再利用 逻辑上扩充了内存 但换入换出 磁盘空间需要化出代价 4 4MEM作业 某操作系统采用可变分区分配存储管理方法 用户区为512K 且初始地址为0 用空闲分区表管理空闲分区 若分配时采用分配空闲区低地址部分的方案 且初始时用户区的512K空间空闲 对下述申请序列 申请300K 申请100K 释放300K 申请150K 申请30K 申请40K 申请60K 释放30K 试回答 1 采用首次适应算法 空闲区中有那些空块 2 采用最佳适应算法 空闲区中有那些空块 3 如再申请100K 针对 1 和 2 各有什么结果 4 4作业 4 4作业 4 4作业 4 5MEM作业 在一个分页存储管理系统中 逻辑地址长度为16位 页面大小为4096字节 现有一逻辑地址为2F6AH 且第0 1 2页依次存放在物理块5 10 11中 问相应的物理地址为多少 0010111101101010因页面大小为4096 则页内位移占11位2F6A页号为2 对应11 B 块 BF6AH 页式地址变换过程 1512110 页号P 页内位移W 页表始址寄存器 0 5 1 10 2 11 页表 1512110 页号P 页内位移W 2F6AH 0 1KB 主存 2KB 3KB 4KB 5KB 11KB 第2页 11 4096 3946 49002 程序地址 BF6AH 4 7MEM作业 考虑页面走向 4 3 2 1 4 3 5 4 3 2 1 5 当内存块数量分别为3和4时 试问LRU FIFO OPT三种置换算法的缺页次数各是多少 假设所有内存块起始为空 3 52作业 考虑页面走向 内存块数量M 3 1 LRU 缺页次数 10 3 52作业 考虑页面走向 内存块数量M 3 2 FIFO 缺页次数 9 3 52作业 考虑页面走向 内存块数量M 3 3 OPT 缺页次数 7 12 3 52作业 考虑页面走向 内存块数量M 4 1 LRU 缺页次数 8 3 52作业 考虑页面走向 内存块数量M 4 1 FIFO 缺页次数 10 3 52作业 考虑页面走向 内存块数量M 4 1 OPT 缺页次数 6 或 5 1设备管理的任务和功能是什么 设备管理的任务 1 监视设备状态 设备控制器记录状态信息 2 制定设备分配策略 3 设备分配 分配通道 控制器 设备 回收 4 计算机和外部设备的数据传送控制方式 5 设备控制与驱动 启动设备I O操作 中断处理 6 实现其他功能 设备独立性 设备无关性 缓冲区管理 Spooling技术 1 基本任务 按用户要求控制I O设备工作 2 设备分配 按一定算法把I O设备分配给请求的进程 3 提高并行操作程度 充分有效地使用I O设备 设备管理功能 1 设备分配 由设备分配程序 将I O通路上 通道 控制器 设备分配给请求的进程 2 设备控制 由设备处理程序 对I O请求构成通道程序 启动通道 响应和处理通道中断请求 3 实现其他功能 缓冲区的管理 设备独立性等 5 1设备管理的任务和功能是什么 设备管理的任务 功能 1 基本任务 按用户要求控制I O设备工作 2 设备分配 按一定算法把I O设备分配给请求的进程 3 提高并行操作程度 充分有效地使用I O设备实现其他功能 1 监视设备状态 设备控制器记录状态信息 2 制定设备分配策略 3 设备分配 分配通道 控制器 设备 建I O通路与回收 4 计算机和外部设备的数据传送控制方式 5 设备控制与驱动 按用户要求控制I O 启动设备I O 中断处理 6 实现其他功能 设备独立性 设备无关性 缓冲区管理 Spooling技术 细化 5 10缓冲技术的作用是什么 缓冲区按组织方式可分为几种 缓冲技术的作用 1 缓和CPU和输入 输出设备速度不匹配的情况 2 提高CPU 通道和I O设备的并行程度 提高系统的处理能力和设备的利用率 3 缓冲技术的引入还可以减少对CPU的中断次数 放宽CPU对中断响应时间的限制 5 10缓冲技术的作用是什么 缓冲区按组织方式可分为几种 缓冲区按组织方式可分为 1 功能分 输入缓冲 输出缓冲 2 使用方式分 专用缓冲区 通用缓冲区 3 组织方式分为单缓冲 双缓冲 循环 环形 缓冲和缓冲池缓冲池中4种工作缓冲区 用于收容输入数据的工作缓冲区hin 用于提取输入数据的工作缓冲区sin 用于收容输出数据的工作缓冲区hout 用于提取输出数据的工作缓冲区sout 5 11I O控制可用哪几种方式实现 各有什么优缺点 I O控制实现方式有4种 程序控制输入 输出方式又称为 状态驱动输入 输出方式或应答输入 输出方式 中断控制方式 直接存储器访问方式 通道控制方式程序控制输入 输出方式 优点 控制简单 不需要多少硬件支持缺点 CPU与外设串行 效率低 5 11I O控制可用哪几种方式实现 各有什么优缺点 中断控制方式优点 CPU与外设并行 提高CPU的利用率缺点 频繁中断服务化时间 使CPU效率降低 配置中断技术 需硬件支持 直接存储器访问方式优点 数据传输不需CPU干预 数据块单位缺点 1 DMA控制器硬件支持 2 CPU对DMA初始化 浪费CPU时间 3 若众多外设采用DMA方式 不断窃取周期 使CPU长时间被挂起 降低CPU效率 5 11I O控制可用哪几种方式实现 各有什么优缺点 通道控制方式优点 一个通道独立于CPU 控制多台设备与内存数据交换 减轻了CPU的工作负担 提高并行工作程度缺点 配置通道 需硬件支持 5 14描述中断控制时的CPU动作过程 置 中断允许位 操作系统作 应急事件 CPU适时响应中断 设备控制器数据寄存器已满 控制器向CPU发中断请求 设备独立I O 补充题 缓冲池中三个队列与收容输入 提取输入 收容输出 提取输出4个处理过程 缓冲池的工作过程 缓冲池 出 缓冲池管理的基本操作 两个基本操作 考虑队列的互斥问题 Getbuf type 过程 从type所指定的队列的队首摘下一个缓冲区Putbuf type number 过程 将由参数number所指示的缓冲区挂在type队列上 voidGetbuf type wait RS type wait MS type B number Take buf type signal MS type Getbuf操作 同步 互斥 程序 voidGet buf type voidPutbuf type number wait MS type Add buf type number signal MS type signal RS type 互斥 Putbuf操作 同步 hout process 分配一空闲队列中缓冲 buffer getbuf emq 装入输出数据 形成hout inputdataintothebutter 将该hout挂入outq putbuf outq buffer 收容输出过程 习题6 6 1何谓文件和文件系统 文件是指具有符号名的信息项的集合 或是具有符号名的关联信息单位 记录 的集合 文件系统是指负责管理和存取文件的程序模块 它是由管理文件所需的数据结构 相应的管理软件及访问文件的一组操作组成的 6 4什么是文件的物理结构 物理结构分为哪几类 各有何特点 文件的物理结构 文件存储器上的文件称为物理文件 文件物理结构就是文件存储结构 物理结构分为 堆文件 连续文件 链接文件 索引文件 直接文件与哈希 HASH 文件 堆 pile 亦称串 特点 最简单的文件组织形式 记录与关键字无关 检索堆结构文件费时 6 4什么是文件的物理结构 物理结构分为哪几类 各有何特点 连续文件特点 顺序存取 亦可随机存取两个优点 管理简单 存取速度快多个缺点 不灵活 要求在文件创建时 事先给出文件的最大长度 影响文件的扩展 修改记录 增加记录 删除记录开销大 当文件被删除时 文件存贮空间可能出现许多小而无法利用的碎块 6 4什么是文件的物理结构 物理结构分为哪几类 各有何特点 隐式链接文件特点 优点 存储空间利用率高 增 删记录方便缺点 采用随机存取方式将是低效的显式链接文件特点 增加链接用表 需要占用物理块 若访问大文件时 可能多次访问该表 使速度降低 可顺序 可随机存取 6 4什么是文件的物理结构 物理结构分为哪几类 各有何特点 索引结构文件优点 可散列存贮 能方便地实现文件的扩展 方便记录插入和删除 顺序 随机存取记录 缺点 增加索引表占用的空间和读写索引表的时间 6 5假设 磁盘组共n 为200 个柱面 编号顺序为0 1 n 1 共有磁头m 为12 个 编号顺序为0 1 m 1 每个磁道内共有k 为10 个扇区从0开始编号 试问 1 柱面号为185 磁头号为12 改为11 道内块号为5的磁盘块的物理块号是多少 2 物理块号是1200 其对应的柱面号 磁头号 扇区号是多少 1 柱面号为185 磁头号为12 改为11 道内块号为5的磁盘块的物理块号是多少 已知 t磁头数 12 s扇区数 磁道 10i 185 j 11 k 5所求 物理块号b k s j i t k s j s t i 5 10 11 10 12 185 5 110 22200 22315 2 物理块号是1200 其对应的柱面号 磁头号 扇区号是多少 已知 t磁头数 12 s扇区数 磁道 10D表示柱面上磁盘块数 s t 10 12 120则 i表示P对应的柱面号 P D 取整 1200 120 10N表示P所在柱面中物理块顺序号 P D 取余 1200 120 0j表示磁头号 N s 取整 0 10 0k表示扇区号 道内扇区号 N s 取余 0 10 0 习题6 6 1 何谓记录的成组与分解 记录的成组 若干个逻辑记录合成一组存入一个物理块的工作 记录的分解 从一组逻辑记录中把一个逻辑记录分离出来的操作 习题6 6 2 设某逻辑记录长度为144BS 共100个记录 盘块大小512BS 磁盘物理文件结构采用显式链接 若记录可以跨块 请问 此文件共需要多少个盘块 各盘块利用率 分析 磁盘物理文件结构采用显式链接 说明每物理块可存放512BS记录信息 若记录可以跨块说明记录信息应放满512BS后 再存放到下一个物理块中 该文件总长度 144 100 BS 该文件需物理块数 144 100 512 1 29其中前28块利用率 100 第29块利用率 14400 28 512 512 12 5 6 10设某分解目录的文件系统中 磁盘块大小为512BS 文件控制块占64BS 其中文件名占8BS 文件号占2BS 假定某目录文件共有254个文件控制块 试分别分析采用分解目录方法前后 查找该目录文件的某个文件控制块的平均访问磁盘次数 分析 未分解目录文件系统中 一个目录项 长度64BS 文件名 ID号 分解目录 一个符号目录项 文件名 文件长度 8 2 长度10BS 一个基本目录项 64 8 56BS 分析 未分解目录文件系统中 一个目录项长度64BS每个磁盘块可存放目录数 512 64 8254 8 31 6目录文件共有254文件控制块 需磁盘块数 31 1 32查找该目录文件的某个文件控制块的平均访问磁盘次数 1 32 2 16 5 分析 分解目录文件系统中 一个目录项长度10BS每个磁盘块可存放目录数 512 10 51254 51 4 50目录文件共有254文件控制块 需磁盘块数 4 1 5查找该目录文件的某个文件控制块的平均访问磁盘次数 1 5 2 3 6 13设某系统磁盘共有500块 块号为 0 1 499 若采用字长为16位的字构造位示图 如下图6 52所示 试问 1 位示图共需要多少个字 2 第i字第j位对应的块号是多少 3 若要为某文