操作系统考研综合应用题分析PPT课件

PV原语题 1 利用信号量实现互斥 对每一临界资源 区 设一信号量S 初值 1 此时S相当于此临界资源的使用许可证 进程1 P s 临界区 V s 进程2 P s 临界区 V s 2 在实现互斥时应注意wait mutex 和signal mutex 必须成对地出现 缺wait mutex 将会引起系统混乱 不能保证对临界资源的互斥访问缺signal mutex 将会使该临界资源永久不被释放 3 4 用信号量描述同步 有一个同步条件设一S 初值S 0 S为可用资源个数 实现 A进程已执行过程序段1 B进程才能执行程序段2 设一信号量S 初值为0 A进程程序段1L1 V s B进程L2 P s 程序段2 5 利用信号量实现前驱关系 同步例子 设置一个信号量S 其初值为0 P1 V S P S P2 如此即可实现先执行P1 再执行P2 6 例 在公共汽车上 司机和售票员各司其职 司机 正常行车 到站停车 启动开车 售票员 售票 开车门 关车门 司机和售票员之间应该密切配合 协调一致 以确保行车安全 请用PV操作实现司机和售票员之间的同步 7 司机 while 1 正常行车 到站停车 signal open wait run 启动开车 售票员 While 1 售票 wait open 开车门 关车门 signal run 用2个私有信号量open run分别表示可以开门和可以开车 由于初始状态是汽车行车和售票员售票 所以初值应该都为0 到站后才会有司机发消息让开门 8 例 桌子上有一只盘子 每次只能放一只水果 爸爸专向盘子中放苹果 妈妈专向盘子中放橘子 一个儿子专等吃盘子中的橘子 一个女儿专等吃盘子中的苹果 用PV操作实现他们之间的同步机制 9 semaphoreempty 1 orange 0 apple 0 orange是son的私有信号量 表示盘子中是否放入橘子 empty是father mother的私有信号量 表示盘子是否为空 apple是daughter的私有信号量 表示盘子中是否放入苹果 10 father while 1 P empty 向盘子中放苹果 V apple Daughter while 1 P apple 从盘子中取苹果 V empty Mother while 1 P empty 向盘子中放橘子 V orange son while 1 P orange 从盘子中取橘子 V empty 11 取动物问题 题目 有一只铁笼子 每次只能放入一只动物 猎人向笼中放入老虎 农民向笼中放入猪 动物园等待取笼中的老虎 饭店等待取笼中的猪 试用P V操作写出能同步执行的程序 12 分析 四者之间的关系 1 猎人和农民要互斥使用笼子 所以两者之间是互斥关系 2 猎人放老虎 动物园取老虎 所以两者是同步关系 3 农民房猪 饭店取猪 所以两者也是同步关系 semaphoreS EmptyCage 1 S Tiger 0 S Pig 0 voidhunter 猎人进程 while 1 P S EmptyCage 往笼子里放入一只老虎 V S Tiger voidfarmer 农民进程 while 1 P S EmptyCage 往笼子里放入一只猪 V S Pig voidzoo 动物园进程 while 1 P S Tiger 从笼子里取出一只老虎 V S EmptyCage voidrestaurant 饭店进程 while 1 P S Pig 从笼子里取出一只猪 V S EmptyCage 13 例 三个进程P1 P2 P3互斥使用一个包含N N 0 个单元的缓冲区 P1每次用produce 生成一个正整数并用put 送入缓冲区某一空单元中 P2每次用getodd 从该缓冲区中取出一个奇数并用countodd 统计奇数个数 P3每次用geteven 从该缓冲区中取出一个偶数并用counteven 统计偶数个数 请用信号量机制实现这三个进程的同步与互斥活动 并说明所定义的信号量的含义 要求用伪代码描述 14 semahporeempty N even 0 odd 0 mutex 1 P1 while 1 x produce wait empty wait mutex put x ifx 2 0signal even elsesignal odd signal mutex 15 P2 while 1 wait odd wait mutex getodd countodd signal mutex signal empty P3 while 1 wait even wait mutex geteven counteven signal mutex signal empty 16 例4 一个供应商用汽车给某超市送货 并把汽车上的货物用超市的三轮车运到仓库中 超市的工作人员也用三轮车从仓库中取货去出售 假设共有3辆三轮车 仓库中只能容纳10辆三轮车的货物 且每次从汽车上取货只能供给一辆三轮车 仓库也只能容纳一辆三轮车进入 考虑相关信号量的定义及初值 并写出用P V操作实现向仓库中送货及从仓库中取货的同步算法 17 信号量定义及初始值 S 3 控制三轮车数量 mutex1 1 控制互斥访问汽车 mutex2 1 控制互斥访问仓库 empty 10 仓库容量 full 0 仓库现有库存量 供给超市 18 从汽车到仓库进程 P empty P S P mutex1 从汽车上取货 V mutex1 去仓库 P mutex2 入仓库装货 V mutex2 V S V full 从仓库到超市进程 P full P S P mutex2 从仓库取货 V mutex2 V empty 去超市 V S 19 例5 a b两点之间是一段东西向的单行车道 现要设计一个自动管理系统 管理规则如下 当ab之间有车辆在行驶时同方向的车可以同时驶入ab段 但另一方向的车必须在ab段外等待 当ab之间无车辆在行驶时 到达a点 或b点 的车辆可以进入ab段 但不能从a点和b点同时驶入 当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时 应让另一方向等待的车辆进入ab段行驶 请用信号量为工具 对ab段实现正确管理以保证行驶安全 20 解析 读者 写着问题的变形 我们设置3个信号量S1 S2和Sab 分别用于从a点进入的车互斥访问共享变量ab 用于记录当前ab段上由a点进入的车辆的数量 从b点进入的车互斥访问共享变量ba 用于记录当前ab段上由b点进入的车辆的数量 和a b点的车辆互斥进入ab段 3个信号量的初值分别为1 1和1 两个共享变量ab和ba的初值分别为0 0 21 voidPab while 1 wait S1 if ab 0 wait Sab ab ab 1 signal S1 车辆从a点驶向b点 wait S1 ab ab 1 if ab 0 signal Sab signal S1 voidPba while 1 wait S2 if ba 0 wait Sab ba ba 1 signal S2 车辆从b点驶向a点 wait S2 ba ba 1 if ba 0 signal Sab signal S2 22 已知一个求值公式 A2 3B B 5A 若A B已赋值 试画出该公式求值过程的前趋图 并用信号量解决公式的求解过程 S1 x1 A A S2 x2 3 B S3 x3 5 A S4 x4 x1 x2 S5 x5 B x3 S6 x6 x4 x5 开始 结束 23 structsemaphorea b c d e 0 0 0 0 0 cobegin S1 V a S2 V b S3 V c P a P b S4 V d P c S5 V e P d P e S6 coend a c b d e 24 某寺庙 有小和尚和老和尚若干 有一个水缸 由小和尚提水入缸供老和尚饮用 水缸可以容纳10桶水 水取自同一口井中 由于水井口窄 每次只能容纳一个水桶取水 水桶总数为3个 每次入水 取水仅为一桶 且不可同时进行 试给出有关取水 入水的算法描述 25 应首先考虑清楚本题需要几个进程 从井中取水后向缸中倒水此为连续动作 可算同一进程 从缸中取水为另一进程 在考虑信号量 有关互斥的资源有水井 一次仅一个水桶进出 水缸 一次如水取水时均为一桶 分别为之设置信号量mutex1 mutex2控制互斥 另有同步问题存在 三个水桶无论从井中取水还是入出水缸都是一次一个 应为之设信号量count 抢不到水桶的进程只好等待 还有水缸满时 不可入水 设信号量empty 控制入水量 水缸空时不可出水 设信号量full 控制出水量 26 mutex1 1 mutex2 1 empty 10 full 0 count 3 cobegin小和尚打水 beginL1 P empty P count P mutex1 从井中取水 V mutex1 P mutex2 送入水缸 V mutex2 V count V full GotoL1 end 老和尚取水 beginL2 P full P count P mutex2 从缸中取水 V mutex2 V empty V count GotoL2end coend 27 某工厂有两个生产车间 两个生产车间分别生产A B两种零件 装配车间的任务是把A B两种零件组装成产品 两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1 F2上 F1存放零件A F2存放零件B F1和F2的容量均为可以存放10个零件 装配工人每次从货架上取一个A零件和一个B零件然后组装成产品 请用PV操作进行正确管理 28 该题是生产者消费者的变形 可以认为一个消费者 装配工人 同两个生产者 A B车间 互斥试用两个缓冲区 F1 F2 可设mutex1 mutex2 初值为1 控制进程对F1 F2的互斥操作 另设empty1 empty2 初值均为10 full1 full2 初值均为0 过程如下 29 CobeginA车间 Begin生产一个产品 P empty1 P mutex1 放入F1 V mutex1 V full End 装配工人 BeginP full1 P full2 P mutex1 P mutex2 取A和B V mutex1 V mutex2 V empty1 V empty2 End B车间Begin生产一个产品 P empty2 P mutex2 放入F2 V mutex2 V full2 End 30 例 某银行提供1个服务窗口和10个供顾客等待的坐位 顾客到达银行时 若有空座位 则到取号机上领取一个号 等待叫号 取号机每次仅允许一位顾客使用 当营业员空闲时 通过叫号选取一位顾客 并为其服务 顾客和营业员的活动过程描述如下 CobeginProcess营业员 Process顾客 WhileCTRUE 从取号机获取一个号码 叫号 等待叫号 为顾客服务 获取服务 coend 请添加必要的信号量和P V 或wait signal 操作 实现上述过程中的互斥与同步 要求写出完整的过程 说明信号量的含义并赋初值 31 Semaphoreseets 10 表示空余座位数量的资源信号量 初值为10Semaphoremutex 1 管理取号机的互斥信号量 初值为1 表示取号机空闲Semaphorecustom 0 表示顾客数量的资源信号量 初值为0Process顾客 P seets 找个空座位先P mutex 再看看取号机是否空闲从取号机上取号 V mutex 放开那个取号机 V custom 取到号 告诉营业员有顾客等待叫号 V seets 被叫号 离开座位接受服务 Process营业员 While true P custom 看看有没有等待的顾客叫号 为顾客服务 32 进程调度 33 作业i的周转时间 作业i的完成时间 作业i的提交时间作业i的带权周转时间 作业i的周转时间 作业i的执行时间 调度算法 SJF 34 基于时间片的轮转调度算法 A B C D E A B C D E A B C E A C E C 0 1 2 3 4 9 12 15 17 18 15 3 75 12 4 18 3 6 9 4 5 17 4 25 14 2 4 02 若到达时间为0 1 2 3 4 又如何 35 基于时间片的轮转调度算法 A B A C B D A E C B D A E C E C E C 0 1 3 5 7 11 10 12 17 18 12 3 9 3 16 3 2 8 4 13 3 25 11 6 3 29 36 静态优先权 非抢占式 1为最高优先权 0 4 4 1 4 8 4 1 8 11 10 3 33 11 16 14 2 8 16 18 15 7 5 9 4 2 93 考虑一下抢占式 情况如何 37 高优先权优先调度算法 0 16 16 4 4 8 4 1 1 4 3 1 8 13 11 2 2 16 18 15 7 5 9 8 3 14 静态优先权 抢占式 1为高优先权 A B B B E E E E C C C C C A A A D D B A A C D E A C D 38 高优先权优先调度算法 0 4 4 1 14 18 14 3 5 4 7 6 2 9 14 12 2 4 7 9 6 3 8 4 2 38 高响应比优先 非抢占式 2 1 4 1 5 1 2 3 1 75 2 4 2 25 当前时间 到达时间 服务时间 服务时间 3 5 39 8 0 8 6 9 0 9 6 9 2 10 1 11 3 9 6 3 31 651 01 670 42 01 12 2 9 2 8 8 1 451 88 10 1 高优先权优先调度算法 高响应比优先 抢占式 40 例 A B C资源的数量是10 5 7 在T0时刻 41 1 T0时刻的安全性 Work Available 3 3 2 Finish i false i 0 1 4 332 532 Finish F F F F F P0P1P2P3P4 T 743 T 745 T T T 1047 1057 42 存在一个安全序列 P1 P3 P4 P2 P0 系统是安全的 43 2 P1请求资源 P1发出请求向量Request1 1 0 2 系统按银行家算法进行检查 Request1 1 0 2 Need1 1 2 2 Request1 1 0 2 Available 3 3 2 系统先假定可为P1分配资源 并修改Available Allocation1和Need1向量 由此形成的资源变化情况如图所示 我们再利用安全性算法检查此时系统是否安全 44 230 020 302 资源情况 进程 NeedABC workABC Work AllocationABC AllocationABC P1 finish 532 true true true true true 011 211 532 743 743 431 002 745 745 600 302 1047 1047 743 010 1057 230 302 020 由安全性检查分析得知 可以找到一个安全序列 P1 P3 P4 P2 P0 系统是安全的 可立即将P1所申请的资源分配给它 P3 P4 P2 P0 230 020 302 45 3 P4请求资源 P4发出请求向量Request4 3 3 0 系统按银行家算法进行检查 Request4 3 3 0 Need4 4 3 1 Request4 3 3 0 Available 2 3 0 不成立 让P4等待 46 Requst0 0 2 0 4 P0请求资源 P0发出请求向量Requst0 0 2 0 系统按银行家算法进行检查 Request0 0 2 0 Need0 7 4 3 Request0 0 2 0 Available 2 3 0 系统试为P0分配资源 并修改相应的向量 47 P0请求资源Requst0 0 2 0 时的资源分配表 210 030 723 P0请求Requst0 0 1 0 因Avaliable 2 1 0 已不能满足任何进程需要 故系统进入不安全状态 此时系统不分配资源 48 银行家算法不足 对资源分配过于保守 计算太多 且缺乏实用价值 为什么 进程数动态变化 另外事先也不知道需多少资源 思考 1 不安全状态一定引起死锁吗 2 一台计算机有8台磁带机 它们由N个进程竞争使用 每个进程可能需要3台磁带机 请问N为多少时 系统没有死锁的危险 否 4 49 存储管理 50 例 设某作业占有7个页面 如果在主存中只允许装入4个工作页面 即工作集为4 作业运行时 实际访问页面的顺序是1 2 3 6 4 7 3 2 1 4 7 5 6 5 2 1试用FIFO与LRU页面调度算法 列出各自的页面淘汰顺序和缺页中断次数 以及最后留驻主存4页的顺序 假设开始的4个页面已装入主存 51 1 答 FIFO 中断次数 6最后驻留页面顺序 5 6 2 1 52 答 LRU 中断次数 10最后驻留页面顺序 6 5 2 1 53 例题 请求分页管理系统中 假设某进程的页表内容如下表所示 54 页面大小为4KB 一次内存的访问时间是100ns 一次快表 TLB 的访问时间是10ns 处理一次缺页的平均时间为108ns 已含更新TLB和页表的时间 进程的驻留集大小固定为2 采用最近最少使用置换算法 LRU 和局部淘汰策略 假设 TLB初始为空 地址转换时先访问TLB 若TLB未命中 再访问页表 忽略访问页表之后的TLB更新时间 有效位为0表示页面不在内存 产生缺页中断 缺页中断处理后 返回到产生缺页中断的指令处重新执行 设有虚地址访问序列2362H 1565H 25A5H 请间 1 依次访问上述三个虚地址 各需多少时间 给出计算过程 2 基于上述访问序列 虚地址1565H的物理地址是多少 请说明理由 55 2362H 1565H 25A5H 56 2362H的访问时间 10ns 访问TLB 100ns 访问页表 100ns 访问内存单元 210ns1565H的访问时间 10ns 访问TLB 100ns 访问页表 100000000ns 调页 10ns 访问TLB 100ns 访问内存单元 100000220ns25A5H的访问时间 10ns 访问TLB 100ns 访问内存单元 110ns 57 1565H的物理地址是 101565H 因为2号页面刚被访问 不会被置换 因此用101页框 58 59 设某计算机的逻辑地址空间和物理地址空间均为64KB 按字节编址 若某进程最多需要6页 Page 数据存储空间 页的大小为1KB 操作系统采用固定分配局部置换策略为此进程分配4个页框 PageFrame 60 当给进程执行到时刻260时 要访问逻辑地址为17ACH的数据 请回答下列问题 1 该逻辑地址对应的页号是多少 2 若采用先进先出 FIFO 置换算法 该逻辑地址对应的物理地址是多少 要求给出计算过程 3 若采用时钟 Clock 置换算法 该逻辑地址对应的物理地址是多少 要求给出计算过程 设搜索下一页的指针沿着顺时针方向移动 且当前指向2号页框 示意图如下 61 62 1 逻辑地址对应的页号是5 2 置换的页面为0号 将5号页面装入7号物理框 逻辑地址对应的物理地址是1FCAH 3 置换2号页面 5号页面装入2号页框 逻辑地址对应的物理地址是0BCAH 17ACH 0001 0111 1010 1100B 63 文件管理 64 文件系统设计题1 设计一个简单文件系统directfs 其中inode节点包含10个直接指针 每个指针可以指向一个文件块 文件块大小为4KBytes 直接指针的大小是32位 4bytes directfs文件系统可以支持最大文件是多大 2 设计一个文件系统extentfs 其中inode节点包括一个extent结构 该结构包含一个基地址指针和一个限长值 长度为8位 1个Byte 文件块大小为4Kbytes 请问extentfs支持的文件最大长度是多少 3 设计一个文件系统indirectfs 其中inode节点包含1个直接指针 1个间接指针和一个双重间接指针 每个指针大小是32位 4bytes 文件块大小为4Kbytes 请问indirectfs支持的文件最大长度是多少 65 inode节点包含10个直接指针 每个指针可以指向一大小为4KBytes的文件块 直接指针是32位 4bytes 10 x4KByte 40KByteinode节点包含一个基地址指针和一个限长值 长度为8位 1个Byte 文件块大小为4Kbytes 28 1 x4KByte 255x4KByte 1MByteinode节点包含1个直接指针 1个间接指针和一个双重间接指针 每个指针大小是32位 4bytes 文件块大小为4Kbytes 1 1024 1024x1024 x4KByte 4GB 4100Kbyte 66 设文件索引节点中有6个地址项 其中4个地址项是直接地址索引 1个地址项是一级间接地址索引 1个地址项是二级间接地址索引 每个地址项大小为4字节 若磁盘索引块和磁盘数据块大小均为512字节 请给出每块的表目数和单个文件最大长度是多少 给出计算过程 67 混合索引结构 68 答案 每块的表目个数 512 4 128一级 128 512二级 128 128 512单个文件最大长度 512 4 128 512 128 128 512 69 设备管理 70 假定有一个磁盘组共有100个柱面 每个柱面上有8个磁道 每个磁道被划分成8个扇区 现有一个含有6400个逻辑记录的文件 逻辑记录的大小与扇区大小一致 该文件以顺序结构的形式被存放到磁盘上 柱面 磁道 扇区的编号均从 0 开始 逻辑记录的编号也从 0 开始 文件信息从0柱面 0磁道 0扇区开始存放 请问 1 该文件的第3680个逻辑记录应存放在哪个柱面的第几个磁道的第几个扇区 2 第78柱面的第6磁道的第6扇区中存放了该文件中的第几个逻辑记录 71 1 第3680个逻辑记录存放的位置是 柱面号 INT 3680 64 57磁道号 INT MOD 3