西安电子科技大学 操作系统 考试重点作业讲解(2～4).ppt

作业讲解 2 4 知识点 进程互斥和同步的控制信号量机制信号量是一种数据结构信号量的值与相应资源的使用情况有关信号量的值仅由P V操作改变 知识点 记录型信号量记录型结构 包括两个数据项 typesemaphore recordvalue integer L listofprocess end 知识点 假设定义了一个信号量SS value为资源信号量 其初值为某类资源的数目 S value 0 代表系统当中可用资源的数目 S value 0 其绝对值代表等待使用资源的进程个数 S L是一个阻塞队列 进程无法申请到资源则进入此队列 知识点 定义对信号量的两个原子操作 wait s 和signal s procedurewait S varS semaphore beginS value S value 1 ifS value 0thenblock S L 进程阻塞 即进入S L链表 end 知识点 定义对信号量的两个原子操作 wait s 和signal s proceduresignal S varS semaphore beginS value S value 1 ifS value 0thenwakeup S L 唤醒阻塞队列首进程 将进程从 S L阻塞队列中移出 end 第二章 22 试写出相应的程序来描述图2 17所示的前趋图 P8222 a Vara b c d e f g h semaphore 0 0 0 0 0 0 0 0 beginparbeginbeginS1 signal a signal b end beginwait a S2 signal c signal d end beginwait b S3 signal e end beginwait c S4 signal f end beginwait d S5 signal g end beginwait e S6 signal h end beginwait f wait g wait h S7 end parendend 第二章 26 参看教材P58 59 第二章 3 设公共汽车上有一个司机和一个售票员 其活动如图3所示 为了安全起见 显然要求 1 关车门后方能启动车辆 2 到站停车后方能开车门 亦即 启动车辆 这一活动应当在 关车门 这一活动之后 开车门 这一活动应当在 到站停车 这一活动之后 试用记录型信号量实现司机与售票员之间的同步 并说明各信号量的含义 用记录型信号量解决这一问题 需要定义两个信号量 Start 表示是否允许司机启动车辆 初值为0 Open 表示是否允许售票员开车门 初值为0 semaphorestart 0 semaphoreopen 0 售票员的活动 beginrepeat关车门 Signal start 售票 Wait open 开车门 untilfalseend 司机的活动 beginrepeatWait start 启动车辆 正常行车 到站停车 Signal open untilfalseend 第二章 知识点进程调度算法避免死锁 银行家算法 进程调度算法 先来先服务FCFS短作业优先调度算法时间片轮转调度算法概念周转时间 指作业提交给系统开始 到作业完成为止的这段时间间隔 带权周转时间 周转时间 系统为它提供服务的时间 第三章 1 假定有如下作业 请用FCFS SJF RR q 2 调度算法 分别计算周转时间 平均周转时间 带权周转时间 平均带权周转时间 第三章 FCF和SPF的计算结果如下 第三章 时间片轮转调度算法 执行图如下 BCA 银行家算法 用于避免死锁 基本思想 当有进程申请资源时 只有满足此进程需要不会导致系统进入不安全状态才分配 安全状态 是指系统能按某种进程顺序 如 分别为这n个进程分配所需资源 直到满足每个进程的最大需求 使每个进程都能顺利完成 称序列为安全序列 若系统存在安全序列 则系统当前为安全状态 银行家算法描述 设Requesti是进程Pi的请求向量 如果Requesti j K 表示进程Pi需要K个Rj类型的资源 当Pi发出资源请求后 系统按下述步骤进行检查 如果Requesti j Need i j 请求小于需求 便转向步骤2 否则认为出错 因为它所需要的资源数已超过它所宣布的最大值 如果Requesti j Available j 请求小于库存 便转向步骤 3 否则 表示尚无足够资源 Pi须等待 银行家算法描述 3 系统试探着把资源分配给进程Pi 试分配 并修改下面数据结构中的数值 库存 Available j Available j Requesti j 获取 Allocation i j Allocation i j Requesti j 需求 Need i j Need i j Requesti j 4 系统执行安全性算法 检查此次资源分配后 系统是否处于安全状态 若安全 才正式将资源分配给进程Pi 以完成本次分配 否则 将本次的试探分配作废 恢复原来的资源分配状态 让进程Pi等待 第三章 2 在银行家算法中 若出现下述资源分配情况 P115第22题 第三章 1 该状态是否安全 安全 因为存在安全序列 第三章 2 若进程P2提出请求Request 1 2 2 2 后 系统能否将资源分配给它 分配后系统资源情况如下 此状态不安全 因此不能分配 第四章 知识点基本分页式存储管理地址映射过程基本分段式存储管理地址映射过程页面置换算法 基本分页式存储管理地址映射过程 第四章 1 在采用页式存储管理的系统中 拥有的逻辑地址空间为32页 某作业J的逻辑地址空间为4页 每页2048字节 且已知该作业的页面映像 即页表 如下 试借助地址变换图求出有效逻辑地址4865所对应的物理地址 解答 基本分段式存储管理地址映射过程 段地址变换由硬件地址变换机构完成 第四章作业3 3 对于下表所示的段表 请将逻辑地址 0 137 1 4000 4 230 转换成物理地址 4 Cb 0137 比较 5 1024 137 段表 0 4 物理地址 段表始址寄存器 段表长度寄存器 逻辑地址 b 137 5K 比较 51337 4 Cb 14000 比较 段表 0 4 地址越界 段表始址寄存器 段表长度寄存器 逻辑地址 b 4000 3K 比较 4 Cb 4230 4 4 段表始址寄存器 段表长度寄存器 逻辑地址 地址越界 比较 页面置换算法 在请求分页式存储管理中 当发生缺页中断且无足够的内存空间时 需要置换已有的某些 个 页面 页面置换算法分类 最佳页面算法 OPT 先进先出页面置换算法 FIFO 最近最久未使用页面置换算法 LRU 轮转算法 Clock 第四章作业2 P143页23题 2 某程序在内存中分配四个块 访问页的走向为4 3 2 1 4 3 5 4 3 2 1 5 按LRU Clock OPT算法分别计算缺页次数假设开始时所有页均不在内存 LRU432143543215块1块2块3块4xxxx x xxx共缺页中断8次 LRU Clock432143543215块1块2块3块4xxxx xxxxxx共缺页中断10次 Clock OPT432143543215块1块2块3块4xxxx x x 共缺页中断6次 OPT 第四章作业4 4 某页式虚拟存储管理系统的物理空间共3K 页面大小为1K 一进程按下列地址顺序引用内存单元 3653 3632 1140 3584 2892 3640 0040 2148 1700 2145 3209 0000 1102 1100 如果上述数字均为十进制 而内存中尚未装入任何页