汤子瀛-计算机操作系统第三版期末总复习课件

1、汤子瀛-计算机操作系统第三版期末总复习操作操作系统系统基本概念基本概念处理机管理处理机管理设备管理设备管理作业管理作业管理用户接口用户接口存储管理存储管理操作系统定义操作系统定义OS的作用的作用OS特征特征OS的主要功能的主要功能OS目标目标OS分类分类多道程序设计多道程序设计进程基本概念进程基本概念进程同步互斥进程同步互斥进程间通信进程间通信进程调度进程调度死锁死锁I/O系统系统I/O控制方式控制方式缓冲技术缓冲技术I/O软件组成软件组成设备独立性设备独立性设备分配设备分配驱动程序驱动程序虚设备技术虚设备技术磁盘调度磁盘调度文件基本概念文件基本概念文件的逻辑结构文件的逻辑结构文件的物理结构文

2、件的物理结构外存空间管理外存空间管理文件共享与保护文件共享与保护数据一致性数据一致性用户接口用户接口作业基本概念作业基本概念批处理系统作业管理批处理系统作业管理分时系统作业管理分时系统作业管理程序的装入与链接程序的装入与链接存储管理任务存储管理任务动态分区分配动态分区分配交换技术交换技术页式存储管理页式存储管理段式存储管理段式存储管理虚拟存储技术虚拟存储技术汤子瀛-计算机操作系统第三版期末总复习批处理操作系统批处理操作系统分时系统分时系统实时操作系统实时操作系统个人计算机操作系统个人计算机操作系统网络操作系统网络操作系统分布式操作系统分布式操作系统操作系统定义操作系统定义OS功能功能OS特征特

3、征OS分类分类硬件运行环境硬件运行环境操作系统设计操作系统设计并发并发共享共享虚拟虚拟异步异步有效管理有效管理合理调度合理调度使用方便使用方便吞吐量吞吐量时间片时间片虚机器虚机器操作系统设计目标操作系统设计目标操作系统结构设计操作系统结构设计CPU状态状态系统堆栈系统堆栈中断技术中断技术时钟时钟通道通道地址映射地址映射存储保护存储保护处理机管理处理机管理存储管理存储管理设备管理设备管理文件管理文件管理用户接口用户接口操作系操作系统基本统基本概念概念汤子瀛-计算机操作系统第三版期末总复习进程进程进程状态及转换进程状态及转换进程控制块进程控制块系统并发度系统并发度进程控制进程控制进程特性进程特性可

4、重入程序可重入程序共享内存共享内存消息缓冲消息缓冲Send/Receive原语原语管道通信管道通信信箱信箱调度算法选择原则调度算法选择原则算法：算法：先进先出先进先出时间片轮转时间片轮转基于优先数基于优先数高相应比优先高相应比优先抢占式抢占式实时调度技术实时调度技术进程同步进程同步进程互斥进程互斥临界区临界区进程同步机制进程同步机制信号量信号量P、V操作操作生产者与消费者问题生产者与消费者问题读者写者问题读者写者问题哲学家进餐问题哲学家进餐问题死锁的有关结论死锁的有关结论产生死锁的产生死锁的必要条件必要条件死锁预防死锁预防死锁避免死锁避免死锁检测解除死锁检测解除资源分配图资源分配图多道程序设计

5、多道程序设计进程基本概念进程基本概念进程同步互斥进程同步互斥进程间通信进程间通信进程调度进程调度死锁死锁顺序环境顺序环境并发环境并发环境与时间有关的错误与时间有关的错误不可在现性不可在现性进程进程管理管理汤子瀛-计算机操作系统第三版期末总复习一、生产者消费者问题n同步关系： PCn互斥关系：互斥访问BUF设：生产进程资源私用量e：BUF中空的buf数 消费进程资源私用量f：BUF中产品数目 pc公用信号量m： 互斥访问BUF设：指针i指向首空buf j指针指向首产品初值 en f0 m1 ij0 ij BUF空 （i+1）mod nj BUF满0123n-1e +f=nij汤子瀛-计算机操作系

6、统第三版期末总复习p进程产品buf（i）i（i+1）mod n V（f）生产一件产品P（e）P（m）v（m）c进程V（m）消费产品P（f）P（m）从buf（j）中取出产品j（j+1）mod nv（e）汤子瀛-计算机操作系统第三版期末总复习下述两段执行序列是否正确？请分析可能出现的问题，并说明理由。 wait (mutex)；“临界段代码”；wait (mutex)；“临界段代码”；（没有对信号量的访问）解答：错误（1）分析: 将signal (mutex)误写成wait (mutex). （2）后果: 进程使用临界资源完毕后将无法释放资源, 若该资源紧张则可能导致死锁, 违背了空闲让进的原则.

7、 （2）错误（1）分析: wait操作和signal操作缺失. （2）后果: 进程将自由进入临界区使用临界资源，将导致资源被破坏的严重后果（2）汤子瀛-计算机操作系统第三版期末总复习n1.假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10，5，7，在T0时刻的资源分配情况： 资源 情况进程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 03 3 2P13 2 22 0 0P29 0 23 0 2P32 2 22 1 1P44 3 30 0 27 4 3 2 2 0 00 1 14 3

8、1汤子瀛-计算机操作系统第三版期末总复习2.P1请求资源Request1（1，0，2），系统按银行家算法进行检查： Request1（1，0，2）=Need1(1,2,2)Request1（1，0，2）= Available 1(3,3,2) 资源 情况进程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 02 3 0P13 2 23 0 2P29 0 23 0 2P32 2 22 1 1P44 3 30 0 27 4 30 2 0 0 00 1 14 3 1汤子瀛-计算机操作系统第三版期末总复习存在安全序列P1,P3,P4,P2

9、,P0,因此，系统是安全的，可用立即将P1所申请的资源分配给他。 资源 情况进程WorkNeedAllocationWork+AllocationFinish A B CA B CA B CA B CPPPPP汤子瀛-计算机操作系统第三版期末总复习（3）P4请求资源，Request4（3，3，0），系统按银行家算法进行检查： Request4（3，3，0）= Available 4(2,3,0),让P4等待。（4）P0请求资源，Request0（0，2，0），系统按银行家算法进行检查： Request0（0，2，0）=Need0(7,4,3) Request0（0，2，0）= Availabl

10、e 0(2,3,0) 系统暂时先假定可为P0分配资源，并修改数据。 MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 3 02 1 0P13 2 23 0 2P29 0 23 0 2P32 2 22 1 1P44 3 30 0 27 2 30 2 0 0 00 1 14 3 1汤子瀛-计算机操作系统第三版期末总复习n2.某系统中四个进程的到达时间和要求服务时间如下表，请采用SPF（不抢占）调度算法进行分析，求进程执行序列和平均周转时间。要求有分析过程。 汤子瀛-计算机操作系统第三版期末总复习n3.考虑一个有150个存储器单元的系统，如

11、下分配给三个进程：n进程 最大需求已分配nn1 7045n2 6040n3 6015n使用银行家算法，以确定下面的任何一个请求是否安全：na第4个进程到达，最多需要60个存储单元，最初需要25个单元；nb第4个进程到达，最多需要60个存储单元，最初需要35个单元；n如果安全给出安全序列；若不安全给出结果分配简表。汤子瀛-计算机操作系统第三版期末总复习汤子瀛-计算机操作系统第三版期末总复习第四章第四章 存储管理存储管理汤子瀛-计算机操作系统第三版期末总复习段式存储管理段式存储管理页式存储管理页式存储管理段页式存储管理段页式存储管理虚拟存储器虚拟存储器虚拟存储技术虚拟存储技术程序局部性原理程序局部

12、性原理虚拟页式管理虚拟页式管理虚拟段式管理虚拟段式管理页面淘汰算法页面淘汰算法用户程序划分用户程序划分逻辑地址逻辑地址内存空间划分内存空间划分内存分配内存分配管理考虑管理考虑硬件支持硬件支持地址映射过程地址映射过程装入与链接装入与链接对换技术对换技术高速缓存高速缓存内存内存磁盘磁盘系统区系统区用户区用户区内存管理分配回收内存管理分配回收存储共享存储共享存储保护存储保护内存扩充内存扩充地址映射地址映射存储体系存储体系存储管理任务存储管理任务存储管理方案存储管理方案虚拟存储管理虚拟存储管理其他其他存储存储管理管理汤子瀛-计算机操作系统第三版期末总复习n1、在一个请求分页系统中，假如系统分配给一个作

13、业的物理块数为 4，且此作业的页面走向为：2，3，2，1，5，2，4，5，3，2，5，2。试用FIFO（先进先出）和OPT（最佳）两种算法分别计算出程序访问过程中所发生的缺页次数（假设开始执行时主存中没有页面，凡第一次用到的页面都产生一次缺页中断。要求列表计算）。LRU?3 ?页面置换次数页面置换次数汤子瀛-计算机操作系统第三版期末总复习汤子瀛-计算机操作系统第三版期末总复习 例例2 2：已知某分页系统，主存容量为：已知某分页系统，主存容量为64K64K，页面大，页面大小为小为1K1K，对一个，对一个4 4页大的作业，其页大的作业，其0 0、1 1、2 2、3 3页页分别被分配到主存的分别被分

14、配到主存的2 2、4 4、6 6、7 7块中。块中。 （1 1）将十进制的逻辑地址）将十进制的逻辑地址10231023、25002500、35003500、45004500转换成物理地址？转换成物理地址？ （2 2）以十进制的逻辑地址）以十进制的逻辑地址10231023为例画出为例画出地址变地址变换过程图换过程图？汤子瀛-计算机操作系统第三版期末总复习 答答：逻辑地址逻辑地址10231023：1023/1K1023/1K，得页号为，得页号为0 0，页内地址，页内地址为为10231023，查页表找到对应的物理块号为，查页表找到对应的物理块号为2 2，故物理地，故物理地址为址为2 21K+1023

15、=30711K+1023=3071 逻辑地址逻辑地址25002500：2500/1K2500/1K，得页号为，得页号为2 2，页内地址，页内地址为为452452，查页表找到对应的物理块号为，查页表找到对应的物理块号为6 6，故物理地，故物理地址为址为6 61K+452=65961K+452=6596 逻辑地址逻辑地址35003500：3500/1K3500/1K，得页号为，得页号为3 3，页内地址，页内地址为为428428，查页表找到对应的物理块号为，查页表找到对应的物理块号为7 7，故物理地，故物理地址为址为7 71K+428=75961K+428=7596 逻辑地址逻辑地址45004500

16、：4500/1K4500/1K，得页号为，得页号为4 4，页内地址，页内地址为为404404，因页号不小于页表长度，故产生，因页号不小于页表长度，故产生越界中断越界中断。汤子瀛-计算机操作系统第三版期末总复习 （2）地址变换过程图地址变换过程图汤子瀛-计算机操作系统第三版期末总复习小小结结 方法方法功能功能单一单一连续区连续区分区式分区式页式页式段式段式段页式段页式固定固定可变可变静态静态动态动态适用环适用环境境单道单道多道多道多道多道多道多道多道多道虚拟空虚拟空间间一维一维一维一维一维一维二维二维二维二维重定位重定位方式方式静态静态静态静态 动态动态动态动态动态动态动态动态分配方分配方式式静

17、态连续静态连续区区静态静态 动态连续区动态连续区静态或动态页静态或动态页为单位非连续为单位非连续动态段为单位动态段为单位非连续非连续动态分配页为动态分配页为单位非连续单位非连续释放释放执行完后执行完后全部释放全部释放执行完后全执行完后全部释放部释放分区分区释放释放执行执行完后完后释放释放淘汰与执淘汰与执行完后释行完后释放放淘汰与执行完淘汰与执行完后释放后释放淘汰与执行淘汰与执行完后释放完后释放保护保护越界保护越界保护越界保护与保护键越界保护与保护键越界保护与控越界保护与控制权保护制权保护越界保护与控越界保护与控制权保护制权保护越界保护与越界保护与控制权保护控制权保护内存扩内存扩充充覆盖与交覆盖

18、与交换换覆盖与交换覆盖与交换覆盖覆盖交换交换虚拟存虚拟存储储虚拟存储虚拟存储虚拟存储虚拟存储共享共享不能不能不能不能较难较难方便方便方便方便硬件支硬件支持持保护用寄保护用寄存器存器保护用寄存器，重保护用寄存器，重定位机构定位机构地址变换机构，地址变换机构，中断机构，保护中断机构，保护机构机构段式地址变换机构，段式地址变换机构，保护与中断机构，保护与中断机构，动态连接机构动态连接机构段式地址变换机段式地址变换机构，保护与中断构，保护与中断机构，动态连接机构，动态连接机构机构汤子瀛-计算机操作系统第三版期末总复习设备管理重要性设备管理重要性设备独立性设备独立性设备分类设备分类设备管理任务设备管理任

19、务I/O通道通道DMA控制方式控制方式用户进程用户进程与设备无关软件与设备无关软件设备驱动程序设备驱动程序中断处理程序中断处理程序SPOOLing技术技术共享打印机共享打印机设备管理设备管理设备分配回收设备分配回收独占设备分配独占设备分配共享设备分配共享设备分配 基本概念基本概念I/O软件组成软件组成缓冲技术缓冲技术设备处理设备处理虚设备技术虚设备技术设备驱动程序设备驱动程序设备设备管理管理磁盘访问时间磁盘访问时间磁盘调度磁盘调度l先来先服务先来先服务l最短寻道时间优先最短寻道时间优先l扫描（电梯算法）扫描（电梯算法）lCSCAN磁盘存储管理磁盘存储管理汤子瀛-计算机操作系统第三版期末总复习第

20、五章设备管理的重点、难点第五章设备管理的重点、难点n 设备管理的主要任务设备管理的主要任务n 什么叫通道技术什么叫通道技术n 如何解决因通道不足而产生的瓶颈问题如何解决因通道不足而产生的瓶颈问题n I/O I/O 控制方式：四种控制方式：四种I/O I/O 方式的基本原理方式的基本原理；I/O I/O 方式由低方式由低到高效的演变的推动因素是什么？到高效的演变的推动因素是什么？n缓冲的概念，为什么引入缓冲缓冲的概念，为什么引入缓冲n中断处理程序的处理过程中断处理程序的处理过程n 设备分配方式设备分配方式汤子瀛-计算机操作系统第三版期末总复习第五章设备管理的重点、难点第五章设备管理的重点、难点虚

21、拟设备和虚拟设备和SPOOLing SPOOLing 技术技术n什么是虚拟设备什么是虚拟设备n什么是什么是SPOOLingSPOOLing技术，技术，SPOOLingSPOOLing系统的组成系统的组成n如何利用如何利用SPOOLingSPOOLing技术实现共享打印机技术实现共享打印机磁盘调度磁盘调度n磁盘调度的磁盘调度的目标目标n磁盘访问时间磁盘访问时间的计算的计算nFCFSFCFS、SSTFSSTF、SCANSCAN、CSCAN CSCAN 等算法的应用等算法的应用及这些调度算法及这些调度算法的演变过程，分别解决了哪些问题；各算法的性能比较的演变过程，分别解决了哪些问题；各算法的性能比较

22、汤子瀛-计算机操作系统第三版期末总复习一个磁盘系统，平均寻道时间为一个磁盘系统，平均寻道时间为12ms，转速为，转速为10000转转/分，每个磁道有分，每个磁道有18个扇区，每个扇区个扇区，每个扇区512个字节。个字节。请问要读取一个扇区所花的时间是多少？请问要读取一个扇区所花的时间是多少？ 解：解： TS = 12msTR = 1/2r = 60100000.5 = 3ms TA=b/rN = (51260)(1851210000)= 0.33ms TT = TS + TR + TA =12 + 3 + 0.33 = 15.33ms答：读取一个扇区所花的时间是答：读取一个扇区所花的时间是15

23、.33ms。 例例汤子瀛-计算机操作系统第三版期末总复习 磁盘调度磁盘调度 目标：减少寻道时间目标：减少寻道时间1 1、FCFSFCFS（Fisrt Come First ServedFisrt Come First Served）先来先服务）先来先服务n特点：公平、简单，寻道时间长，相当于随机特点：公平、简单，寻道时间长，相当于随机访问模式。访问模式。n仅适用于请求磁盘仅适用于请求磁盘I/OI/O的进程数目较少的场合。的进程数目较少的场合。2 2、SSTFSSTF（最短寻道优先）最短寻道时间优先（最短寻道优先）最短寻道时间优先nSSTFSSTF比比FCFSFCFS有更好的寻道性能有更好的寻道

24、性能n贪心的算法贪心的算法n饥饿现象饥饿现象n不能保证平均寻道时间最短不能保证平均寻道时间最短 ？汤子瀛-计算机操作系统第三版期末总复习3 3、SCAN SCAN 扫描算法（也称为电梯算法）。扫描算法（也称为电梯算法）。n进程进程“饥饿现象饥饿现象”SSTFSSTF存在。存在。nSCANSCAN算法：算法：n在移动方向固定的情况下采用了在移动方向固定的情况下采用了SSTFSSTF，以避，以避免饥饿现象免饥饿现象 4 4、循环扫描、循环扫描CSCANCSCANn磁头单向移动磁头单向移动n一个方向读完，不是象一个方向读完，不是象SCANSCAN那样回头，而是循那样回头，而是循环扫描。环扫描。汤子瀛

25、-计算机操作系统第三版期末总复习例n假设一个活动头磁盘有200道, 编号从0-199. 当前磁头正在143道上服务, 并且刚刚完成了125道的请求。现有如下访盘请求序列(磁道号): 86, 147, 91, 177, 94, 150, 102, 175, 130n 试给出采用下列算法后磁头移动的顺序和移动总量(总磁道数).n (1) 先来先服务(FCFS)磁盘调度算法. (2) 最短寻道时间优先(SSTF)磁盘调度算法.n(3) 扫描法(SCAN)磁盘调度算法.(假设沿磁头移动方向不再有访问请求时, 磁头沿相反方向移动)汤子瀛-计算机操作系统第三版期末总复习n答、n（1）磁道访问顺序为：86，

26、147，91，177，94，150，102，175，130n磁头移动的总磁道数 = 57+61+56+86+83+56+48+73+45 = 565 （3分）n （2）当前磁头在143道上：n 磁道访问顺序为：147，150，130，102，94，91，86，175，177n 磁头移动的总磁道数 = 4+3+20+28+8+3+5+89+2 = 162（3分）n（3）当前磁头在143道上，并且刚刚完成125道的请求n 磁道访问顺序为：147，150，175，177，130，102，94，91，86n 磁头移动的总磁道数 = 4+3+25+2+47+28+8+3+5 = 125（4分）汤子瀛-计

27、算机操作系统第三版期末总复习例n若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。n（1）先来先服务算法；（2）最短寻道时间优先算法。n（3）扫描算法（当前磁头移动的方向为磁道递增）汤子瀛-计算机操作系统第三版期末总复习n解：（1）磁道访问顺序为：20，44，40，4，80，12，76n寻道时间 =（20+24+4+36+76+68+64）*3=292*3=876（3分）n（2）磁道访问顺序为：40，44，20，12，4，76，80n寻

28、道时间 =（0+4+24+8+8+72+4）*3=120*3=360（3分）n（3）磁道访问顺序为：40，44，76，80，20，12，4n寻道时间 =（0+4+32+4+60+8+8）*3=116*3=348（4分）汤子瀛-计算机操作系统第三版期末总复习磁盘访问时间由哪几部分组成？每部分时间应如何计算？n解：磁盘访问时间由下述部分组成：n（1）寻道时间Ts ：指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和，即Ts=mn+s 。（2分）n（2）旋转延迟时间Tr：这是指定扇区移动到磁头下面所经历的时间。（2分）n（3）传输时间Tt：从磁盘读出或写入b个字节数据所经历的时间。n其中，r为磁盘每秒钟的转数；N为一条磁道上的字节数。（3分）n因此，访问时间Ta表示为： （3分）汤子瀛-计算机操作系统第三版期末总复习文件控制块文件控制块文件目录文件目录目录文件目录文件目录项目录项树型目录结构树型目录结构目录项分解法目录项分解法目录检索目录检索文件文件文件系统文件系统文件分类文件分类文件管理功能文件管理功能文件逻辑结构文件逻辑结构文件物理结构文件物理结构文件存取方式文件存取方式外存空间管理外存空间管理