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

,操作系统,基本概念,处理机管理,设备管理,作业管理用户接口,存储管理,文件管理,操作系统定义OS的作用OS特征OS的主要功能OS分类OS结构设计,多道程序设计进程基本概念进程同步互斥进程间通信进程调度死锁,I/O系统I/O控制方式缓冲技术I/O软件组成设备独立性设备分配驱动程序虚设备技术通道技术磁盘调度,文件基本概念文件的逻辑结构文件的物理结构文件目录外存空间管理文件共享与保护数据一致性,用户接口作业基本概念批处理系统作业管理分时系统作业管理,程序的装入与链接存储管理任务动态分区分配交换技术页式存储管理段式存储管理段页式虚拟存储技术,批处理操作系统分时系统实时操作系统个人计算机操作系统网络操作系统分布式操作系统,操作系统定义,OS功能,OS特征,OS分类,硬件运行环境,操作系统设计,并发共享虚拟异步,有效管理合理调度使用方便,吞吐量时间片虚机器,操作系统设计目标操作系统结构设计,CPU状态系统堆栈中断技术时钟通道地址映射存储保护,处理机管理存储管理设备管理文件管理用户接口,操作系统基本概念,第一章引论,1、OS的定义与作用2、三种基本操作系统的基本原理和异同多道程序设计、时间片轮转法、及时性3、OS的特征和功能4、用户接口5、OS的结构设计,进程进程状态及转换进程控制块系统并发度进程控制进程特性可重入程序,共享内存消息缓冲Send/Receive原语管道通信信箱,调度算法选择原则算法：先进先出时间片轮转基于优先数高相应比优先抢占式实时调度技术,进程同步进程互斥临界区进程同步机制信号量P、V操作生产者与消费者问题读者写者问题哲学家进餐问题,死锁的有关结论产生死锁的必要条件死锁预防死锁避免死锁检测解除资源分配图,多道程序设计,进程基本概念,进程同步互斥,进程间通信,进程调度,死锁,顺序环境并发环境与时间有关的错误不可在现性,进程管理,第二章进程管理,1、进程和线程的概念2、进程的基本状态及状态转换的原因3、PCB的作用4、进程控制的原语操作5、进程互斥、临界区、进程同步的基本概念、同步准则6、记录型信号量7、信号量的应用8、经典进程同步问题；生产者与消费者问题9、进程间通信的原理和实现方法信箱,第二章进程管理的典型问题,进程的三种基本状态及其转变原因。进程互斥、临界区三种经典同步问题及其变型同步约束条件的分析，信号量的初值的设定单缓冲区的一个生产者一个消费者同步问题单缓冲区的一个生产者多个消费者同步问题多个生产者多个消费者多个缓冲区的同步问题,第三章处理机调度与死锁,1、处理机调度的基本概念和种类2、选择调度算法的准则，周转时间，带权周转时间，响应时间3、常见调度算法，抢占，响应比4、常见的两种实时调度算法处理死锁的基本方法5、死锁产生的原因，四个必要条件6、死锁的预防7、利用银行家算法避免死锁8、死锁的检测与解除,段式存储管理页式存储管理段页式存储管理,虚拟存储器虚拟存储技术程序局部性原理虚拟页式管理虚拟段式管理页面淘汰算法抖动（颠簸）,用户程序划分逻辑地址内存空间划分内存分配管理考虑硬件支持地址映射过程,装入与链接对换技术覆盖技术,高速缓存内存磁盘系统区用户区,内存管理分配回收存储共享存储保护内存扩充地址映射,存储体系,存储管理任务,存储管理方案,虚拟存储管理,其他,存储管理,第四章存储管理的重点、难点,重定位的基本概念：为什么要引入如何提高内存利用率：离散分配、对换机制、动态链接、虚拟存储器、存储器共享动态分区分配方式：分配、回收算法基本分页存储管理方式：为什么引入；地址变换机构和过程（含具有快表的情况）基本分段存储管理方式：为什么引入；地址变换机构和过程（含具有快表的情况）；信息的共享和保护虚拟存储器的基本概念：为什么要引入；特征；实现虚拟存储的关键技术请求分页系统的基本原理：页表机制；地址变换过程；页面置换算法,第四章的典型问题,存储器管理的基本任务动态重定位的概念、实现方式，什么情况下需要重定位比较连续分配与离散分配基于空闲分区链的内存分配与回收算法的应用实例：首次适应法，循环首次适应法，最佳适应法在某分页系统中，给定内存容量和物理块大小，计算物理块的数量；对给定的进程页表，将给定的逻辑地址，计算出其对应的物理地址并画出地址变换流程图。在某分段系统中对给定的进程段表，将给定的逻辑地址，计算出其对应的物理地址并画出地址变换流程图。请求分页系统过程的各种问题，并用流程图的方式表示地址变换过程对给定的问题，按各种页面置换算法，写页面调入过程，计算和分析缺页率，并对多种算法的性能作比较分析,设备管理重要性设备独立性设备分类设备管理任务设备管理功能,用户进程与设备无关软件设备驱动程序中断处理程序,SPOOLing技术共享打印机,设备管理设备分配回收独占设备分配共享设备分配,基本概念,I/O软件组成,缓冲技术,设备处理,虚设备技术,设备驱动程序,设备管理,磁盘访问时间磁盘调度先来先服务最短寻道时间优先扫描（电梯算法）CSCAN,磁盘存储管理,第五章设备管理的重点、难点,I/O控制方式：四种I/O方式的基本原理；四种I/O方式由低到高效的演变缓冲管理缓冲的概念，为什么引入缓冲单缓冲如何提高I/O速度，它存在哪些不足，双缓冲、循环缓冲又如何提高CPU与I/O设备的并行性缓冲池是为了解决什么问题而引入，引入缓冲池后系统将如何处理I/O设备和CPU间的数据输送缓冲池的工作方式及Getbuf和Putbuf过程设备独立性什么是设备独立性如何实现设备独立性设备驱动程序,第五章设备管理的重点、难点,虚拟设备和SPOOLing技术什么是虚拟设备什么是SPOOLing技术，SPOOLing系统的组成如何利用SPOOLing技术实现共享打印机磁盘调度磁盘调度的目标磁盘访问时间的计算FCFS、SSTF、SCAN、CSCAN等算法的应用及这些调度算法的演变过程，分别解决了哪些问题；各算法的性能比较,第五章设备管理的典型问题,各种I/O控制方式的比较为什么引入缓冲区缓冲如何提高I/O速度为什么引入设备独立性，如何实现什么是虚拟设备，实现虚拟设备的关键技术SPOOLing技术的组成，如何利用SPOOLing技术实现共享打印机设备处理程序的功能和处理过程对各种磁盘调度算法，计算访问次序和平均寻道时间，性能磁盘访问时间的组成和计算,文件控制块文件目录目录文件目录项树型目录结构目录项分解法目录检索,文件文件系统文件分类文件管理功能文件逻辑结构文件物理结构文件存取方式,外存空间管理主要数据结构文件系统使用文件系统安全、保护、保密、可靠性、一致性,系统打开文件表用户打开文件表,物理块磁盘结构磁带,文件目录,文件基本概念,文件系统实现,存储介质,创建、打开、读写、关闭、删除、拷贝、重命名,文件存取控制,文件管理,第六章文件管理的重点、难点,文件的逻辑结构：顺序文件、索引文件和索引顺序文件原理和特征组织方式、访问方法及各种文件形式的比较外存分配方式：连续分配、链接分配和索引分配原理、优缺点显示链接FAT、混合索引分配目录管理：目录管理的要求文件控制块（FCB）索引结点目录结构：单级、两级和多级文件磁盘空间管理空闲表法和空闲链法位示图法：分配和回收的具体计算成组链接法,第六章文件管理的典型问题,画出链接分配方式的链接情况和FAT的链接情况、FAT长度计算等。混合索引分配的的寻址方式、地址转换的计算（另见P350）和索引结点的地址映射图对给定的位示图和文件的分配和回收需求，具体写出分配过程和回收过程。Unix系统的成组链接法目录管理的要求；目前广泛采用的目录结构及其优点说明在树形目录结构中线性检索的过程，并画出相应的流程图文件的共享,第七章操作系统接口,联机命令接口联机命令终端处理程序命令解释程序程序接口系统调用与一般过程调用的区别中断与陷入图形用户接口,期末试题题型及分值,单选题判断题简答题计算题编程题,分值分布：第二章（约占22分）第三章（约占20分）第四章（约占20分）第五章（约占15分）第六章（约占18分）其余章（约占5分）,-,20,-,21,-,22,-,23,司机和售票员之间的同步关系,司机只有在售票员关车门后，才能启动汽车。售票员只有在司机到站停车后，才能开车门。,解：,Semaphoreclose=0，stop=0；driver()/*司机*/while(True)P(close);启动车辆;正常行车;到站停车;V(stop);,Conductor()/*售票员*/while(True)关车门;V(close);售票;P(stop);开车门;上下乘客;,Main()parbegin(driver,conductor);,-,27,练习：过十字路口（单道）。,进程的互斥,P1P2P3P4通过路口；通过路口；通过路口；通过路口；,P2,P3,P4,P1,-,28,分析：进程P1、P2、P3、P4因竞争十字路口这个资源而成为互斥关系。设：信号量m表示十字路口资源，初值为1表示资源可用。intm=1;cobeginp1()/p2()/p3()/p4()coend,进程的互斥,p1()P(m)；通过路口；V(m)；,p2()P(m)；通过路口；V(m)；,p3()P(m)；通过路口；V(m)；,p4()P(m)；通过路口；V(m)；,-,29,在生产者消费者问题中应注意：,()在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现。()对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的进程中，这样保证生产者进程和消费者进程的同步及交替执行。()在每个进程中，多个wait操作顺序不能颠倒，而signal操作的次序是无关紧要的。,-,30,例,一台计算机有10台磁带机被n个进程竞争，每个进程最多需要3台磁带机，那么n最多为_时，系统没有死锁的危险？解：n最大为4。,-,31,例,在银行家算法中，若出现下述的资源分配情况：ProcessMaxAllocationAvailableP0004400321622P127501000P23610101354P309840332P4066100014试问：1）该状态是否安全？2）若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？3）如果系统立即满足P2的上述请求，系统是否立即进入死锁状态？,-,32,解：1）利用安全性算法对上面的状态进行分析（如下表所示），找到了一个安全序列P0，P3，P4，P1，P2或P0，P3，P1，P4，P2，故系统是安全的。,-,33,-,34,2)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）；系统先假定可为P2分配资源，并修改Available，Allocation2和Need2向量：Availabe=（0，4，0，0）Allocation2=（2，5，7，6）Need2=(1,1,3,4)进行安全性检查：此时对所有进程，条件NeediAvailable（0，4，0，0）都不成立，即Available不能满足任何进程的请求，故系统进入不安全状态。因此，当进程P2提出请求Request（1，2，2，2）后，系统不能将资源分配给它。3）系统立即满足进程P2的请求（1，2，2，2）后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源，并未因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。,-,35,例题,对访问串1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大小分别为3、4时，使用FIFO替换算法的缺页次数和缺页率。结果说明了什么？,-,36,先进先出（FIFO）页面置换算法（续）,Referencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)4framesFIFOReplacementBeladysAnomalymoreframeslesspagefaults,9pagefaults,10pagefaults,-,37,一个磁盘系统，平均寻道时间为12ms，转速为10000转/分，每个磁道有18个扇区，每个扇区512个字节。请问要读取一个扇区所花的时间是多少？解：TS=12msTR=1/2r=60100000.5=3msTA=b/rN=(51260)(1851210000)=0.33msTT=TS+TR+TA=12+3+0.33=15.33ms答：读取一个扇区所花的时间是15.33ms。,例,-,38,5.6.2磁盘调度,目标：减少寻道时间1、FCFS（FisrtComeFirstServed）先来先服务特点：公平、简单，寻道时间长，相当于随机访问模式。仅适用于请求磁盘I/O的进程数目较少的场合。2、SSTF（最短寻道优先）最短寻道时间优先SSTF比FCFS有更好的寻道性能贪心的算法饥饿现象不能保证平均寻道时间最短？,-,39,图5-25FCFS调度算法,图5-26SSTF调度算法,-,40,3、SCAN扫描算法（也称为电梯算法）。进程“饥饿现象”SSTF存在。SCAN算法：在移动方向固定的情况下采用了SSTF，以避免饥饿现象存在请求进程等待延迟现象4、循环扫描CSCAN磁头单向移动一个方向读完，不是象SCAN那样回头，而是循环扫描。请求延迟时间：2TT+Smax