操作系统计算题总结

1 应用类型知识要点一 进程同步问题应用类型知识要点一 进程同步问题 整形信号量 未遵循 让权等待原则 wait S while S 0 do no op S S 1 signal S S S 1 记录型信号量 执行 wait 操作时 信号量的值加 1 信号量 的值小于 0 时阻塞 执行 signal 操作时 信号量的值减 1 信号 量的值小于等于 0 时唤醒阻塞中的进程 type semaphore record value integer L list of process end procedure wait S var S semaphore begin S value S value 1 if S value 0 then block S L end procedure signal S var S semaphore begin S value S value 1 if S valueSj 专门设置一初值为 0 的信号量 并在 Si 结束之后执行对该信号量的 signal 操作 而在 Sj 开始之前执行对该信 号量的 wait 操作 这样便可保证程序段 Si 执行完后才执行程序段 Sj 利用信号量实现互斥利用信号量实现互斥 主程序子程序 Var mutex semaphore 1 begin parbegin process1 process2 parend end process1 begin repeat wait mutex 临界区临界区 signal mutex until false end process2 begin repeat wait mutex 临界区临界区 signal mutex until false end 1 互斥信号量初值为 1 2 互斥信号量 wait 和 signal 肯定出现在同一进程中 并出现在需要互斥访问数据 临界资 源 前后 S1 S2S3 S4S5 S6 S7 a b c d e fhg 3 生产者生产者 消费者问题消费者问题 主程序 n 为常量 Var buffer array 0 n 1 of item in out integer 0 0 mutex empty full semaphore 1 n 0 begin parbegin producer1 produceri producerM consumer1 consumerj consumerN parend end 生产者子程序消费者子程序 produceri Var nextp item begin repeat Produce an item in nextp wait empty wait mutex buffer in nextp in in 1 mod n signal mutex signal full until false end consumerj Var nextc item begin repeat wait full wait mutex nextc buffer out out out 1 mod n signal mutex signal empty Consume the item in nextc until false end 生产者子程序 基于 AND 信号量 消费者子程序 基于 AND 信号量 produceri begin repeat Produce an item in nextp Swait empty mutex buffer in nextp in in 1 mod n Signal mutex full until false end consumerj begin repeat Swait full mutex nextc buffer out out out 1 mod n Ssignal mutex empty Consume the item in nextc until false end 4 读者读者 写者问题写者问题 读者优先读者优先 主程序 Var readercount integer 0 rcmutex wmutex semaphore 1 1 begin parbegin reader1 readeri readerM writer1 writerj writerN parend end 读者 readeri begin repeat wait rcmutex if readercount 0 then wait wmutex readercount readercount 1 signal rcmutex Perform read operation wait rcmutex readercount readercount 1 if readercount 0 then signal wmutex signal rcmutex until false end 写者 writerj begin repeat wait wmutex Perform write operation signal wmutex until false end readercount 读者数 rcmutex 读者进程中用于 readercount 变量的互斥访问 wmutex 用于读者与写者 写者与写者之间的互斥访问 写者与第一个读者竞争 wmutex 一旦读者获得 wmutex 那么直到所有读者执行结束由最 后一个读者释放 而每个写者执行结束都释放 所以读者优先写者执行 5 读者读者 写者问题写者问题 写者优先写者优先 主程序 Var readercount writercount integer 0 0 rcmutex wcmutex wmutex S semaphore 1 1 1 1 begin parbegin reader1 readeri readerM writer1 writerj writerN parend end 读者 readeri begin repeat wait S wait rcmutex if readercount 0 then wait wmutex readercount readercount 1 signal rcmutex signal S Perform read operation wait rcmutex readercount readercount 1 if readercount 0 then signal wmutex signal rcmutex until false end 写者 writerj begin repeat wait wcmutex if writercount 0 then wait S writercount writercount 1 signal wcmutex wait wmutex Perform write operation signal wmutex wait wcmutex writercount writercount 1 if writercount 0 then signal S signal wcmutex until false end rcmutex 读者进程中用于 readercount 变量的互斥访问 wcmutex 写者进程中用于 writercount 变量的互斥访问 6 wmutex 用于读者与写者 写者与写者之间的互斥访问 读者与第一个写者竞争 S 信号量 一旦读者获得 S 信号量 那么直到所有读者执行结束由 最后一个写者释放 而每个读者执行结束都释放 所以写者优先读者执行 读者读者 写者问题写者问题 限定读者数限定读者数 主程序 Var RN integer 10 rmax wmutex semaphore RN 1 begin parbegin reader1 readeri readerM writer1 writerj writerN parend end 读者 readeri begin repeat Swait rmax 1 1 Swait wmutex 1 0 Perform read operation Ssignal rmax 1 until false end 写者 writerj begin repeat Swait wmutex 1 1 rmax RN 0 Perform write operation Signal wmutex until false end RN 限定最多同时读的读者数 rmax 空位置的数目 即系统还允许执行读操作的读者数 超过这个数目后读者将等待 wmutex 用于读者与写者 写者与写者之间的互斥访问 读者执行 Swait wmutex 1 0 保证无写者 wmutex 值保持不改变 写者执行 Swait wmutex 1 1 rmax RN 0 保证既无写者在写又无读者在读 rmax 值保持不变 Swait rmax 1 1 wmutex 1 0 7 哲学家进餐问题哲学家进餐问题 主程序 Var chopstick array 0 4 of semaphore 1 1 1 1 1 begin parbegin philosopher0 philosopheri philosopher4 parend end 哲学家进餐问题子程序 基于 AND 信号量机制 philosopheri begin repeat Think Swait chopstick i 1 mod 5 chopstick i Eat Ssignal chopstick i 1 mod 5 chopstick i until false end 哲学家进餐问题子程序 限制哲学家同时进餐人数 philosopheri var pmax semaphore 4 begin repeat wait pmax wait chopstick i wait chopstick i 1 mod 5 Eat signal chopstick i 1 mod 5 signal chopstick i signal pmax Think until false end 8 理发师问题描述如下 理发店包含一间接待室和一间工作室 接待室内有理发师问题描述如下 理发店包含一间接待室和一间工作室 接待室内有 n n 1 把椅子 把椅子 而工作室只有一把椅子 如果没有顾客 理发师就去睡觉 如果顾客来时所有的椅子都有而工作室只有一把椅子 如果没有顾客 理发师就去睡觉 如果顾客来时所有的椅子都有 人 那么顾客离去 如果理发师在忙且接待室有空闲的椅子 那么此顾客会坐在其中一把人 那么顾客离去 如果理发师在忙且接待室有空闲的椅子 那么此顾客会坐在其中一把 空闲的椅子上等待 如果理发师在睡觉 则顾客会唤醒他 请采用信号量机制解决该理发空闲的椅子上等待 如果理发师在睡觉 则顾客会唤醒他 请采用信号量机制解决该理发 师问题师问题 可采用伪代码描述可采用伪代码描述 解 要求描述理发师和顾客的行为 因为需要两类进程 Barber 和 Customer 分别描述理发 师和顾客的行为 理发师和顾客之间是同步的关系 理发师和椅子使临界资源 所以顾客 之间是互斥的关系 引入 3 个信号量和一个控制变量 控制变量 waiting 也用于记录等候的顾客数 实际上是 customers 的一份拷贝 之所以 使用 waiting 是因为无法读取信号量的当前值 初值均为 0 信号量 customers 用来记录等候理发的顾客数 不包括正在理发的顾客 并用作阻塞理 发师进程 初值为 0 信号量 barbers 用来记录正在等候顾客的理发师数 为 0 或 1 并用作阻塞顾客进程 初值为 0 信号量 mutex 用于对 waiting 的访问进行互斥 初值为 1 进入理发店的顾客必须先看等候的顾客数 如果少于椅子数 n 他坐下来等 否则他就 离开 PV 操作代码如下 int waiting 0 等候理发的顾客数 还没理发的 0 n semaphore customers 0 barbers 0 mutex 1 barber while TRUE 理完一人 还有顾客吗 P customers 若无顾客 理发师睡眠 P mutex 进程互斥 waiting waiting 1 等候顾客数少一个 V barbers 理发师去为一个顾客理发 V mutex 开放临界区 cut hair 正在理发 非临界区操作 customer 顾客进入理发店 P mutex 进程互斥 if waiting n 还有空位 waiting waiting 1 等候顾客数加 1 V customers 有顾客了 如果理发师在睡则唤醒 V mutex 开放临界区 P barbers 无理发师 顾客坐着养神 get haircut 一个顾客坐下等待理发 else V mutex 顾客已满 离开 9 应用类型知识要点二 分页存储地址结构及地址变换应用类型知识要点二 分页存储地址结构及地址变换 分页存储管理地址结构 由硬件机制决定 31 12 11 0 页 号页内地址 逻辑地址与页号及页内偏移地址之间的换算 PageNo INT Addr PageLength PageOffset Addr mod PageLength 举例 对于 1KB 页面 若给定逻辑地址 2170B 则 PageNo 2 PageOffset 122 地址变换任务 关键在于页号到物理块号之间的转变 地址映射 某虚拟存储器的用户编程空间共 32 个页面 每页 1K 主存为 16K 假定某时刻用户 页表中已调入主存的页面的虚页号和物理页号对照表如图所示 则当虚地址为十六进制 0A5C 时 对应的物理地址是多少 虚页号物理页号 04 110 24 37 解 虚拟地址 0A5C 10 16 5 16 12 16 2 10 页号 INT 2652 1K 2 其物理块号为 4 页内偏移 2652 mod 1K 604 物理地址为 4 1K 604 4700 125C 1016 应用类型知识要点三 分页存储与数据访问时间应用类型知识要点三 分页存储与数据访问时间 假定快表检索时间为 20ns 内存访问时间为 100ns 则若能在快表中找到 CPU 给出的 页号 CPU 存取一个数据将需要 100 20 120ns 若不能在快表中找到 CPU 给出的页号 则为存取一个数据将需要 100 100 20 220ns 进一步说 若假定快表查找命中率为 80 则其有效访问时间为 120 80 220 1 80 140ns 10 应用类型知识要点四 页面置换算法与缺页次数应用类型知识要点四 页面置换算法与缺页次数 最佳置换算法最佳置换算法 OPT 向前看页面引用序列向前看页面引用序列 基本思想 选择永不使用或是在最长时间内不再被访问 即据现在最长时间才会被访问 的页面淘汰出 内存 评价 理想化算法 具有最好性能 对于固定分配方式 本法可保证获得较低的缺页率 但实际上却 难于实现 故主要用于算法评价参照 70120304230321201701 77722222222222222777 0000004440000000000 111333333331111111 某进程分配获得三个物理块 采用预调页策略 区别预调页策略与请求调页策略 前 3 个页面预先装入 第一行为页面访问 引用 序列 第二 三 四行为内存页面分布情况 前三列页面预先装入 缺页中断次数为 6 次 缺页率 30 缺页率 发生缺页次数 页面序列长度 100 先进先出置换算法先进先出置换算法 FIFO 向回看页面分布情况向回看页面分布情况 基本思想 选择最先进入内存即在内存中驻留时间最久的页面换出到外存 进程已调入内存的页面 按进入先后次序链接成一个队列 并设置替换指针以指向最老页面 评价 简单直观 但不符合进程实际运行规律 性能较差 故实际应用极少 70120304230321201701 77722224440000000777 0000333222221111100 111100033333222221 某进程分配获得三个物理块 采用预调页策略 区别预调页策略与请求调页策略 前 3 个页面预先装入 第一行为页面访问 引用 序列 第二 三 四行为内存页面分布情况 前三列页面预先装入 缺页中断次数为 12 次 缺页率 68 缺页率 发生缺页次数 页面序列长度 100 最近最久未使用置换算法最近最久未使用置换算法 LRU 向回看页面引用序列向回看页面引用序列 硬件支持硬件支持 基本思想 以 最近的过去 作为 最近的将来 的近似 选择最近一段时间最长时间未被访问的 页面淘汰出内存 评价 适用于各种类型的程序 性能较好 但需要较多的硬件支持 70120304230321201701 77722224440001111111 0000000033333300000 111333222222222777 某进程分配获得三个物理块 11 采用预调页策略 区别预调页策略与请求调页策略 前 3 个页面预先装入 第一行为页面访问 引用 序列 第二 三 四行为内存页面分布情况 前三列页面预先装入 缺页中断次数为 9 次 缺页率 45 缺页率 发生缺页次数 页面序列长度 100 简单简单 CLOCK 置换算法置换算法 NRU 硬件支持硬件支持 改进型改进型 CLOCK 置换算法置换算法 硬件支持硬件支持 评价 与简单 CLOCK 算法相比 可减少磁盘的 I O 操作次数 但淘汰页的选择可能经历多次扫描 最多最多 3 轮加轮加 1 次次 故实现算法自身的开销增大 最少使用置换算法最少使用置换算法 硬件支持硬件支持 基本思想 为内存各页设置一个以为寄存器用于记录对应被访问频率 选择在最近时期使用最少的 页面作为淘汰页 评价 鉴于仅用一位寄存器有限各位来记录页面使用会导致访问一次与访问多次的等效性 本算法 并不能真实全面地反映页面适用情况 应用类型知识要点五 文件结构与记录检索次数应用类型知识要点五 文件结构与记录检索次数 索引顺序文件组织方式 检索开销 分组大小 两级索引顺序文件组织方式 主文件分组大小 低级索引表分组大小 检索开销 顺序文件 定长记录顺序文件 变长记录顺序文件 1逻辑记录的排序 与关键字次序一致与否 串结构与顺序结构 2顺序文件读写操作 读写指针 RWptr对应记录逻辑地址 定长记录 RWptr recordLength 变长纪录 RWptr currentRecordLength 无法实现随机存取 3顺序文件评析 适于批量存取及磁带介质 交互应用场合单个记录操作低效 索引文件组织及检索机制 主要解决变长记录文件无法实现随机存取问题 记录号本身的物理含义很弱 强调真正具有物理含义的关键字 索引表本身是定长记录顺序文件 索引顺序文件检索效率分析 对于拥有 N 条记录的主数据文件 若基于顺序查找法来检索具有指定关键字的记录 12 不同文件组织方式下的系统检索开销比较 假设不存在查找失败的情况 1顺序文件组织方式 N 1 2 条 顺序查找 2索引文件组织方式 N 1 2 条 顺序查找 3索引顺序文件组织方式 1 分组大小记录 此时检索效率最高 NN 4举例说明 N 10000 基于多级索引的索引顺序文件 分组大小 3 N 建立多级索引以进一步提高检索效率 举例说明 N 10 6 1索引顺序文件组织方式 检索开销 1001 条 分组大小 1000 条记录 2两级索引顺序文件组织方式 主文件分组大小 100 条记录 低级索引表分组大小 100 条记录 检索开销 151 5 条 应用类型知识要点六 文件分配表占用空间应用类型知识要点六 文件分配表占用空间 关键计算盘块总数 实际操作系统按簇分配 这里按盘块分配 磁盘有多少个盘块 FAT 中就有多少个表项 前提是按盘块分配 FAT 表项应足以表示最大的盘块号 文件分配表空间开销计算 设定盘块大小为 1KB 对于 1 2M 的软盘 共有盘块 1 2M 1KB 1 2K 2 2 取取 4 的倍数且较大的那个的倍数且较大的那个 812 故文件分配表表项取 12 位即 1 5B 所以 FAT 共需空间 1 2K 1 5B 1 8KB 对于 200M 的硬盘 共有盘块 200M 1KB 200K 2 2 1620 故文件分配表表项取 20 位即 2 5B 所以 FAT 共需空间 200K 2 5B 500KB 应用类型知识要点七 索引分配与文件最大长度应用类型知识要点七 索引分配与文件最大长度 两级 多级索引分配 基本思想 对于太大的文件和索引块太多时 直接用链接指针来链接索引块的方法显然是低效的 为 此应引入多级索引分配方式 允许文件最大长度 13 两级索引 盘块大小 1KB 盘块号占 4B 则一个索引块可含 1KB 4B 256 个盘块号 于是 两级索引最多可含 256 256 64K 个盘块号 允许文件最大长度为 64MB 混合分配方式 UNIX 系统 4KB 4MB 4GB 4TB 直接寻址 直接地址项存放对应文件数据的盘块的盘块号 盘块大小 4KB 盘块号占 4B 则支持长度在 4KB 10 40KB 以内的文件 一次间接寻址 addr 10 指向对应文件的一级索引块 一级索引块可含 4KB 4B 1K 个盘块号 故支持长度在 4KB 1K 4MB 40KB 以内的文件 多次间接寻址 addr 11 i addr 12 分别指向对应文件的两级索引和三级索引块 所以支持的文件长度可达 4KB 1K 1K 1K 4TB 4KB 1K 1K 4GB 4MB 40KB 应用类型知识要点八文件查找与磁盘启动次数应用类型知识要点八文件查找与磁盘启动次数 假定每次启动磁盘只装入一个目录盘块 盘块大小 1KB 文件目录共 3200 个 FCB 引入索引结点前 FCB 占 64B 每盘块包含 16 个 FCB 文件目录共需占用 200 个盘块 故查找一个文件平 均需启动磁盘 100 5 次 顺序查找 引入索引结点后 FCB 占 16B 文件名和索引结点指针分别占用 14B 和 2B 每盘块包含 64 个目录项 文件 目录共需占用 50 个盘块 故查找一个文件平均需启动磁盘 25 5 1 次 顺序查找 读索引结 点取地址信息只需一次 因为索引结点在外存上是连续存放的 应用类型知识要点九 银行家算法及资源分配管理应用类型知识要点九 银行家算法及资源分配管理 产生死锁的必要条件产生死锁的必要条件 1互斥条件 2请求和保持条件 3不剥夺条件 4环路等待条件 死锁预防死锁预防 要求进程的资源分配是静态的 死锁预防的方法是使四个必要条件中的第 2 3 4 个条件之一不能成立 来避免发生 死锁 至于条件 1 因为它是设备的固有特性所决定的 不仅不能改变 还应加以保证 死锁避免死锁避免 允许进程动态地申请资源 但系统在进行资源分配之前 应首先就资源分配的安全性 进行检查 且仅当确认此次分配不会导致系统进入不安全状态时才可分配 否则予以拒绝 死锁避免基本概念 14 安全状态安全状态 系统可按某种进程序列 称之为安全分配序列 来为每个进程 Pi 分配其 所需资源 直至满足每个进程对资源的最大需求 使每个进程均能顺利完成 不安全状态不安全状态 系统无法找到一个安全分配序列的系统状态 死锁与状态安全性之间的关系死锁与状态安全性之间的关系 1 并非所有不安全状态都是死锁状态 2 当系统进入不安全状态后 便可能可能陷入死锁 3 只要保证系统处于安全状态 便可避免死锁 安全状态及向不安全状态的转换 资源名称资源总数可用资源量可用资源量 磁带机1232 进程最大需求已分配 尚需 已分配 尚需 P1105 5 5 5 P242 2 2 2 P392 7 3 6 T0 时刻存在安全分配序列 若在 T0 时刻应进程请求将所剩磁带机中的 1 台分配给 P3 则系统进入不安全状态 如上图 银行家算法之数据结构 下标 i 对应进程 下标 j 对应资源 可用资源向量 请求向量 m Available j k 表示系统现有 k 个 Rj 类资源 Request j k 表示进程 Pi 请求 k 个 Rj 类资源 i 最大需求矩阵 分配矩阵 需求矩阵 n m Max i j k 表示进程 Pi 最多需要 k 个 Rj 类资源 Allocation i j k 表示进程 Pi 已分配 k 个 Rj 类资源 Need i j k 表示进程 Pi 尚需 k 个 Rj 类资源 工作向量 m Finish 布尔向量 n Work j k 表示系统 可 提供 k 个 Rj 类资源 Finish i 表示进程 Pi 可否拥有足够资源完成运行 银行家算法之主体算法 1 进程 Pi 发出资源请求 Requesti 2 若非 RequestNeed i 出错返回 i 3 若非 RequestAvailable 则应使 Pi 等待并返回 i 4 系统试探性地满足 Pi 请求 并作以下修改 Available Available Requesti Allocation i Allocation i Requesti Need i Need i Requesti 15 5 系统调用安全性算法安全性算法进行资源分配检查 若安全则执行分配 否则恢复试探分配 前状态 并使 Pi 等待 银行家算法之安全性子算法 另 Work Available Finish FALSE 从进程集合中查找一个满足 Finish i FALSE 且 Need i Work 的进程 若找到 则可假定 Pi 能获得所需资源并顺利执行 故有 Work Work Allocation i Finish i TRUE 然后重复执行第 2 步 否则转至第 3 步执行 如果 Finish TRUE 则表示系统处于安全状态 否则系统处于不安全状态 银行家算法应用举例之一银行家算法应用举例之一 无任何进程发出资源申请无任何进程发出资源申请 MAXAllocationNeedWork Allocation Work进程 ABCABCABCABCABC Finish P0753010743745755TRUE 4 P1322200122332532TRUE 1 P29023026007551057TRUE 5 P3222211011532743TRUE 2 P4433002431743745TRUE 3 系统资源总量 Available A B C 10 5 7 T0 时刻 Available A B C 3 3 2 安全分配序列 1 Work Available 3 3 2 可满足 P1 或