PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

册尚
5 years ago
Views:

1 操作系统作业讲解赵俊峰

2 进程管理一家快餐店招有 4 种雇员 (1) 开票者, 取顾客的订单 ;(2) 厨师, 准备饭菜 ;(3) 包装员, 把食品塞入袋子 ;(4) 出纳, 一手收钱一手交货每位雇员看作一个在通信的顺序进程他们采用什么形式的进程间通信开票者和厨师之间是管道通信开票者源源不断的把订单给厨师, 一次可能给一张也可能给多张, 厨师一次可能拿走一张订单去做也可能拿走多张去做但不能反向厨师和包装员之间是信箱通信他们之间有个信箱, 可能就是一个小平台, 厨师做好就把菜放上去, 相当于放进信箱, 而包装员可以在任何时候取走那个菜包装员和出纳之间是消息缓冲通信包装员包好了就给出纳发消息, 出纳得到消息就取走包好的饭菜然后出售

3 P,V 操作实现开票者厨师包装员出纳

4 进程管理有五个进程 P1 P2 P3 P4 P5, 它们同时依次进入就绪队列, 它们的优先数和需要的处理器时间如下表忽略进行调度等所花费的时间, 回答下列问题写出采用先来先服务, 非抢占式的优先数调度算法选中进程执行的次序分别计算上述两种算法使各进程在就绪队列中的等待时间以及两种算法下的平均等待时间进程 P1 P2 P3 P4 P5 处理器时间优先数

5 采用先来先服务的调度算法, 执行次序为 :P1 P2 P3 P4 P5 采用非抢占式的优先数调度算法, 执行次序为 :P4 P1 P3 P5 P2 采用先来先服务的调度算法, 各进程在就绪队列中等待时间为 : 进程 : P1 P2 P3 P4 P5 等待时间计算得平均等待时间为 : T1=( ) / 5 = 9.6 ( 机器时间 )

6 采用非抢占式的优先数调度算法, 各进程在就绪队列中的等待时间为 : 进程 : P4 P1 P3 P5 P2 等待时间计算得平均等待时间为 :T2 = ( ) / 5 = 43/5 = 8.6 ( 机器时间 ) 比较两种算法 : 从执行顺序上看, 先来先服务调度算法更注重公平性, 先来的进程先进行操作 ; 非抢占式的优先数调度算法则在进程优先级较大时, 先执行从各进程等待时间上看, 先来先服务调度算法的各进程的等待时间较为平均 ; 非抢占式的优先数调度算法则是优先级高的等待短, 优先级低的等待长这样容易使得优先级低的进程饥饿从平均等待时间上看, 先来先服务调度算法比非抢占式的优先数调度算法的平均等待时间长说明非抢占式的优先数调度算法在节省运行时间上有优势可以让运行时间短的进程优先级高一些, 这样短的先执行, 则平均运行时间会减小

7 存储管理用可变分区方式管理主存时, 假定主存中按地址顺序依次有五个空闲区, 空闲区的大小依次为 32K,10K,5K,228K,100K 现有五个程序 J1,J2,J3,J4 和 J5 它们各需主存 1K,10K,108K,28K,115K 若采用最先适应分配法能把这五个程序按照 J1~J5 的次序全部装入主存吗? 按照什么次序可以使主存空间利用率最高?

8 (1) 不行以下模拟 J1~J5( 1K,10K,108K,28K,115K ) 进入内存情况如下 : 初始空闲分区状态 J1 进入后空闲分区的状态 J2 进入后空闲分区的状态 J3 进入后空闲分区的状态 32K 31K 21K 21K 21K 10K 10K 10K 10K 10K 5K 5K 5K 5K 5K 228K 228K 228K 120K 92K 100K 100K 100K 100K 100K J4 进入后空闲分区的状态没有满足 J5 运行条件的空闲分区以 J1,J2,J3,J5,J4 的次序装入这五个作业可使主存空间利用率最高, 这样可以将五个作业全部装入内存, 使得内存利用率最高初始空闲分区状态 J1 进入后空闲分区的状态 J2 进入后空闲分区的状态 J3 进入后空闲分区的状态 J5 进入后空闲分区的状态 32K 31K 21K 21K 21K 21K 10K 10K 10K 10K 10K 10K 5K 5K 5K 5K 5K 5K 228K 228K 228K 120K 5K 5K 100K 100K 100K 100K 100K 72K J4 进入后空闲分区的状态

9 存储管理有一操作系统采用段式存储管理方案, 用户区内存为 512k, 分配时截取空闲块的前半部分 ( 小地址部分 ) 初始使内存全部空闲系统执行如下申请, 释放操作序列申请 300k, 申请 100k, 释放 300k, 申请 150k, 申请 50k, 释放 100k 若采用首先适应算法, 空闲块表中有哪些空块?( 指出大小, 地址 ) 若采用首佳适应算法, 空闲块表中有哪些空块?( 指出大小, 地址 ) 若随后又申请 80k, 空闲块表中有哪些空块? 指出大小, 地址

10 存储管理首先适应算法 ( 找到符合要求的第一个分区 ) 申请 300k, 申请 100k 释放 300k, 申请 150k 申请 50k, 释放 100k 又申请 80k 150K 150K 150K 300K 150K 50K 50K 80K 100K 100K 312K 232K 112K 112K

11 存储管理首佳适应算法 ( 找到其大小与要求相差最小的分区 ) 申请 300k, 申请 100k 释放 300k, 申请 150k 申请 50k, 释放 100k 又申请 80k 150K 150K 150K 300K 150K 80K 100K 100K 250K 170K 112K 112K 50K 62K 50K 62K

12 存储管理有一个虚拟存储系统分配给某进程 3 页内存, 开始时内存为空, 页面访问序列如下 : 6,5,4,3,2,1,5,4,3,6,5,4, 3,2,1,6,5 若采用 FIFO LRU OPT LFU, 缺页次数为多少?

13 存储管理 FIFO( 先进先出算法 ) FIF O 链尾链首缺页 Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y 缺页次数 17 次

14 存储管理 LRU ( 最近最久未使用算法 ) LRU 链尾链首缺页 Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y 缺页次数 17 次

15 存储管理 LFU ( 最不常用算法 ) LFU 链尾链首缺页 Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y 缺页次数 17 次

16 OPT ( 最佳算法 ) 存储管理 OPT 链尾链首缺页 Y Y Y Y Y Y N N Y Y N N Y Y Y N N 缺页次数 11 次

17 存储管理比较各种存储管理方式的特征 ( 包括主存空间的分配方式是否要有硬件的地址转换机构作支撑适合单道或多道系统等 ) 重定位方式地址转换的实现 ( 操作系统和硬件怎样配合 ) 存储保护的实现 ( 操作系统和硬件各自做些什么工作 )

18 存储管理特征主存分配方式硬件地址转换适合系统其他重定位方式地址转换过程存储保护单一用户存储一次性全部连续不必需单道利用率低, 不灵活动态或静态根据基地址生成物理地址静态由软件完成 ; 动态可由硬件提供基地址寄存器帮助转换无分区管理固定分区管理可变分区管理按照程序提供的内存需求最大值从已划分好的固定区域中分配在装入程序时从空闲区域中划分不必需多道不能充分利用内存, 碎片问题严重, 程序大小受到限制不必需多道简单易行, 利用率较高缺乏扩充性动态或静态动态 ( 拼接时 ) 根据基地址生成物理地址静态由软件完成 ; 动态可由硬件提供基地址寄存器帮助转换根据基地址生成物理地址可由硬件提供基地址寄存器帮助转换通过界限寄存器 [ 硬件 ] 或保护键 [ 软件 ] 的相应判断, 产生越界中断或者保护性中断 [ 硬件 ] 页式存储管理以页面为单位, 按用户程序需求的页数分配, 分配空间不一定连续需要页表始址寄存器和长度寄存器, 也可以增加快表多道有效解决碎片问题, 但有时也会造成空间浪费动态把逻辑地址分为页号和页内地址, 与页表长度寄存器比较, 检查越界, 根据页表始址寄存器得到页表首地址, 根据逻辑页号找到内存块号, 并且与页内地址拼成物理地址可以用快表来实现加速 [ 硬件 ] 保护键 [ 软件 ] 或扩充页表, 增加存取控制项 [ 硬件 ] 段式存储管理以段为单位, 为每一个逻辑段分配连续的内存空间需要段表始址寄存器和长度寄存器, 也可以增加快表多道便于动态分配内存, 管理和申请统一化, 便于共享, 动态链接, 会有碎片问题动态把逻辑地址分为段号和段内地址, 与段表长度寄存器比较, 检查越界, 根据段表始址寄存器得到段表首地址, 根据逻辑段号找到该段起始地址, 并且与段内地址拼成物理地址可以用快表来实现加速 [ 硬件 ] 越界检查 [ 硬件 ] 保护键 [ 软件 ] 或扩充段表, 增加存取控制项 [ 硬件 ] 段页式存储管理以段为单位, 为每一个逻辑段按用户程序需求的页数分配, 分配空间不一定连续需要段表始址寄存器长度寄存器和快表多道方便用户提高利用率, 结合段式与页式的优点动态根据段号查找快表, 如果找到则直接获得物理地址, 否则通过段表始址寄存器查找段表, 根据段号查找页表位置, 根据页号在页表中查找内存块号, 和页内地址拼接成物理地址, 并更新快表 [ 硬件 ] 越界检查 [ 硬件 ] 保护键或扩充段表, 增加存取控制项 [ 硬件 ] 虚拟存储管理虚拟页式存储虚拟段式存储程序运行时不装入全部页面, 根据需求动态装入, 使用页面置换算法来调换内存中的页面程序运行时不全部装入, 根据需求动态装入, 以段为单位进行内外村的交换需要在页式基础上增加页号驻留位内存块号外存地址访问位修改位需要在段式基础上增加特征位存取权限位标志位扩充位多道多道把内存与外存有机结合起来, 扩充了内存的容量, 有可能产生抖动把内存与外存有机结合起来, 扩充了内存的容量, 有可能产生抖动动态动态在地址映射过程中如果访问页面不存在则产生缺页中断 [ 硬件 ], 并根据一定的算法将页面调入内存, 如果内存已满, 需要将某些页面暂时移出内存 [ 软件 ] 在地址映射过程中如果访问段不存在则产生缺段中断 [ 硬件 ], 检察系统是否有足够连续空间, 如有则直接装入, 否则尝试使用紧缩技术获得足够连续空间, 如果还不足则考虑淘汰一些内存中的不常用段 [ 软件 ] 越界检查 [ 硬件 ] 保护键 [ 软件 ] 或扩充段表, 增加存取控制项 [ 硬件 ]

19 文件管理文件系统采用三级索引结构假设一个物理块放 10 个目录项, 一个目录下最多放 40 个文件如果下级文件是目录文件, 则上级目录项指向该目录文件的首地址 ; 如果下级文件是普通文件, 则上级目录项指向该文件的文件控制块又假设索引表放在 FCB 中, 如果要读取 K 的第一块或最后一块, 需要启动硬盘最少几次, 最多几次? 假设 : 普通文件采用 UNIX 的三级索引结构, 即文件控制块中给出 13 个磁盘地址, 前 10 个磁盘地址指出文件前 10 块的物理地址, 第 11 个磁盘地址指向一级索引表, 一级索引表给出 256 个磁盘地址, 即指出该文件第 11 块至第 266 块的物理地址 ; 第 12 个磁盘地址指向二级索引表, 二级索引表中指出 256 个一级索引表的地址 ; 第 13 个磁盘地址指向三级索引表, 三级索引表中指出 256 个二级索引表的地址

20 ROOT A B C D... E F... G \A\D\G\H\K H... I J... K

21 如果要找 \A\D\G\H\K 中的某一块, 首先要找到其 FCB 最好的情况是 : 每次读取目录描述信息的时候都在第一块找到下级目录或文件, 所以要找到该文件至少要读取 A D G H 四个目录项的第一块, 读取 K 的 FCB, 总共 5 次启动硬盘 ; 最坏情况是 : 每次读取目录描述信息的时候都在最后一个块找到下级的目录或文件, 所以要找到该文件, 所以要找到该文件至少要读取 A,D G H 四个目录项的所有四个块, 在读取 K 的 FCB, 总共要 4*4+1=17 次启动硬盘找到 FCB 后在读取某一块, 如果这一块在前 10 块之列, 那么在启动一次硬盘就可以找到这一块, 如果这一块在最后一块, 则可能需要通过三级索引找到这一块, 这总共需要读取三级索引和最后一块共 3+1 次读取硬盘综上, 最好情况下只需要启动 5+1 次硬盘, 最坏情况需要启动 =21 次硬盘

22 死锁在银行家算法中, 若出现下面的资源分配情况 : Process allocation need available P P P P P ) 该状态是否安全? 2) 若进程 P2 提出请求 request(1,2,2,2) 后, 系统能否将资源分配给它

解 Process Allocation Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6

2 2 0 0 1 2 0 0 3 2 1 6 5 4 True P3 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6 True P1 1 9 8 6 1 7 5 0 1 0 0 0

23 解 Process Allocation Need Available P P P P P 进程 Work 系统是安全的 Work+ Need Allocation Allocation Finish P True P True P True P True P True

24 若进程 P2 提出请求 Request(1,2,2,2) Request2(1,2,2,2) Need2(2,3,5,6) Request2(1,2,2,2) Available(1,6,2,2) 假定系统将资源分配给它, 则系统进入不安全状态, 故不能分配资源 Process Allocation Need Available P P P P P

26 死锁一个操作系统有 20 个进程, 竞争使用 65 个同类资源, 申请方式是逐个进行的, 一旦某进程获得它所需要的全部数量, 立即归还所有资源每个进程最多使用 3 个资源若仅考虑这类资源, 该系统有无可能全部死锁, 为什么? 对于此系统, 若只考虑一个资源的分配, 则不会产生死锁, 因为它不足产生死锁的原因, 在这个系统中, 进程所需的资源数少于系统所拥有的资源数 ( 产生死锁的根本原因是因为多道程序所共享的系统资源不足, 且仅当进程提出资源申请时才发生死锁 ) 本题中, 该系统有 65 个同类资源, 而只有 20 个进程, 每个进程最多使用 3 个资源, 这样系统最多使用 60 个资源, 而系统有 65 个资源, 所以不会存在死锁问题

27 死锁假定某计算机系统有 R1 和 R2 两类可再使用资源 ( 其中 R1 由两个单位,R2 有一个单位 ), 它们被进程 P1 和 P2 所共享, 且已知两个进程均以 : - 申请 R1- 申请 R2- 申请 R1- 释放 R1- 释放 R2- 释放 R1- 所示的顺序使用两类资源试求出系统运行过程中可能达到的死锁点画出死锁点的资源分配图

29 作业管理有 5 个批处理的作业 (a,b,c,d,e) 几乎同时到达一个计算中心, 估计运行时间分别为分钟, 它们的优先数分别为 (1 为最低优先级 ) 对下面的每种调度算法, 分别写出作业运行顺序, 并计算作业的平均周转时间和平均带权周转时间最高优先级优先先来先服务 ( 作业到达顺序为 c,d,b,e,a) 短作业优先

30 最高优先级优先作业的平均周转时间 :T = ( )/ 5 = 22; 平均带权周转时间 : W =(10/ /8 + 24/6 + 28/4 + 30/2) / 5 = 5.85 先来先服务作业的平均周转时间 :T =( )/ 5 = 19.2; 平均带权周转时间 : W =(6/6 + 14/8 + 18/4 + 28/ /2) / 5 = 5.01 短作业优先作业的平均周转时间 :T =( )/ 5 = 14; 平均带权周转时间 : W =(2/2 + 6/4 + 12/6 + 20/8 + 30/10)/ 5 = 2

31 作业管理有一个具有两道作业的批处理系统, 作业调度采用短作业优先的调度算法, 进程调度采用以优先数为基础的抢占式调度算法, 有如表所示的作业序列 ( 表中所列的作业优先数即为进程优先数, 数值越小优先级越高 ) 1) 列出所有作业进入内存时间及结束时间 2) 计算平均周转时间作业名到达时间估计运行时间优先数 A B C D 10:00 10:20 10:30 10:50 40 分 30 分 50 分 20 分

32 解答 : 注意区分作业调度和进程调度, 只有调度进入系统的进程方能参与进程调度本题中系统是两道作业系统, 因此每次只能有两个作业进入系统, 本题作业和进程的推进过程为 : 10:00 A 作业到达, 被作业调度程序调度进入系统被进程调度的程序调度开始运行 10:20 A 作业运行 20 分钟, 剩余 20 分钟由于优先级别低, 被进程调度处于就绪状态 B 作业到达, 被作业调度程序调度进入系统由于优先级别高, 被进程调度处于开始运行 10:30A 作业等待 10 分钟, 剩余 20 分钟, 继续等待 B 作业运行 10 分钟, 剩余 20 分钟, 继续运行 C 作业到达, 等待被作业调度程序调度 10:50 A 作业等待 30 分钟, 剩余 20 分钟由于优先级别高, 被进程调度处于开始运行 B 作业运行 30 分钟, 结束运行 C 作业等待 20 分钟, 由于估计运行时间较长, 仍未被调入系统运行 D 作业到达, 由于估计运行时间较短, 被作业调度程序调度进入系统由于优先级别低, 被进程调度程序调度处于就绪状态 11:10 A 作业 40 分钟, 结束运行 C 作业等待 30 分钟, 被进程调度处于开始运行由于优先级别高, 被进程调度处于开始运行 D 作业等待 10 分钟, 由于优先级别低, 被进程调度程序调度处于就绪状态 12:00 C 作业运行 50 分钟, 结束运行 D 作业等待 60 分钟, 被进程调度处于开始运行 12:20 D 作业运行 20 分钟, 结束运行

34 期末考试时间地点 12 月 28 日 ( 周一 ) 晚节理教 102

L12 TLB

L12 TLB Lecture 6: TLB TLBs --- Making Address Translation Fast 问题 : 一次内存引用要访问几次内存? 0 / / 2 / 3 次? 把经常要查的页表项放到 Cache 中, 这种在 Cache 中的页表项组成的页表称为 Translation Lookaside Buffer or TLB( 快表 ) 虚页号分成 tag+index,tag 用于和页表项中的