资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,操作,系统,基本概念,处理机管理,设备管理,作业管理,用户接口,存储管理,文件管理,操作系统定义,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,系统的成组链接法,目录管理的要求,；目前广泛采用的目录结构及其优点,说明在树形目录结构中线性检索的过程，并画出相应的流程图,文件的共享,第七章 操作系统接口,联机命令接口,联机命令,终端处理程序,命令解释程序,程序接口,系统调用,与一般过程调用的区别,中断与陷入,图形用户接口,期末试题题型及分值,单选题（每小题,1,分，共,20,分）,判断题（每小题,2,分，共,20,分）,填空题（每空,1,分，共,15,分）,解析题（,5,小题，共,45,分）,分值分布：,第一章、七章（约占,5,分）,第二章（约占,22,分）,第三章（约占,20,分）,第四章（约占,20,分）,第五章（约占,15,分）,第六章（约占,18,分）,司机和售票员之间的同步关系,司机只有在售票员关车门后，才能启动汽车。,售票员只有在司机到站停车后，才能开车门。,解：,Semaphore close=0,，,stop=0,；,driver( )/*,司机*,/,while(True,) ,P(close,);,启动车辆,;,正常行车,;,到站停车,;,V(stop,);,Conductor( )/*,售票员,*,/,while(True,),关车门,;,V(close,);,售票,;,P(stop,);,开车门,;,上下乘客,;,Main( ),parbegin(driver,conductor,);,一个生产者一个消费者,n,个缓冲区,中科院软件所,1996,年试题,由于只有一个生产者和一个消费者，不会发生几个生产者和消费者同时存取同一缓冲单元的情况，故无须设置互斥信号量。,假定系统有,3,个并发进程,get,、,copy,和,put,共享缓冲器,B1,和,B2,。进程,get,负责从输入设备上读信息，每读出一条记录后放到,B1,中。进程,copy,从缓冲器,B1,中取出一条记录拷贝后存入,B2,。进程,put,取出,B2,中的记录打印输出。,B1,和,B2,每次只能存放一条记录。要求,3,个进程协调完成任务，使打印出来的与读入的记录个数、次序完全一样。请用记录型信号量写出并发程序。（北大,1990,年试题）,解：,设置,4,个信号量，其中,empty1,对应空闲的缓冲区,1,，其初值为,1,；,full1,对应缓冲区,1,中的记录，其初值为,0,；,empty2,对应空闲的缓冲区,2,，其初值为,1,；,full2,对应缓冲区,2,中的记录，其初值为,0,。相应进程描述为：,get( ),while(1),从输入设备读入一条记录,;,P(empty1);,将记录存入缓冲区,1,；,V(full1);,copy( ),while(1),P(full1);,从缓冲区,1,中取出一条记录,;,V(empty1);,P(empty2);,将取出的记录存入缓冲区,2,；,V(full2);,put( ),while(1),P(full2);,从缓冲区,2,中取出一条记录,;,V(empty2);,将取出的记录打印出来；,Main( ),parbegin(get,copy,put,);,例,一台计算机有,10,台磁带机被,n,个进程竞争，每个进程最多需要,3,台磁带机，那么,n,最多为,_,时，系统没有死锁的危险？,解：,n,最大为,4,。,例,在银行家算法中，若出现下述的资源分配情况：,ProcessMax AllocationAvailable,P00 0 4 40 0 3 21 6 2 2,P12 7 5 01 0 0 0,P23 6 10,10,1 3 5 4,P30 9 8 40 3 3 2,P40 6 6 100 0 1 4,试问：,1,）该状态是否安全？,2,）若进程,P2,提出请求,Request,（,1,，,2,，,2,，,2,）后，系统能否将资源分配给它？,3,）如果系统立即满足,P2,的上述请求，系统是否立即进入死锁状态？,解：,1,）利用安全性算法对上面的状态进行分析（如下表所示），找到了一个安全序列,P0,，,P3,，,P4,，,P1,，,P2,或,P0,，,P3,，,P1,，,P4,，,P2,，故系统是安全的。,资源情况,进程,Work,Need,Allocation,Work+Allocation,Finish,A B C D,A B C D,A B C D,A B C D,P0,1 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,P4,1 9 8 6,0 6 5 6,0 0 1 4,1 9 9 10,True,P1,1 9 9 10,1 7 5 0,1 0 0 0,2 9 9 10,True,P2,2 9 9 10,2 3 5 6,1 3 5 4,3 12 14,14,True,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),进行安全性检查：此时对所有进程，条件,Needi, Available,（,0,，,4,，,0,，,0,）都不成立，即,Available,不能满足任何进程的请求，故系统进入不安全状态。因此，当进程,P2,提出请求,Request,（,1,，,2,，,2,，,2,）后，系统不能将资源分配给它。,3,）,系统立即满足进程,P2,的请求（,1,，,2,，,2,，,2,）后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源，并未因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。,例,2,：已知某分页系统，主存容量为,64K,，页面大小为,1K,，对一个,4,页大的作业，其,0,、,1,、,2,、,3,页分别被分配到主存的,2,、,4,、,6,、,7,块中。,（,1,）将十进制的逻辑地址,1023,、,2500,、,3500,、,4500,转换成物理地址？,（,2,）以十进制的逻辑地址,1023,为例画出,地址变换过程图,？,答,：,逻辑地址,1023,：,1023/1K,，得页号为,0,，页内地址为,1023,，查页表找到对应的物理块号为,2,，故物理地址为,2,1K+1023=3071,逻辑地址,2500,：,2500/1K,，得页号为,2,，页内地址为,452,，查页表找到对应的物理块号为,6,，故物理地址为,6,1K+452=6596,逻辑地址,3500,：,3500/1K,，得页号为,3,，页内地址为,428,，查页表找到对应的物理块号为,7,，故物理地址为,7,1K+428=7596,逻辑地址,4500,：,4500/1K,，得页号为,4,，页内地址为,404,，因页号不小于页表长度，故产生,越界中断,。,（,2,）,地址变换过程图,例题,对访问串,1,，,2,，,3,，,4,，,1,，,2,，,5,，,1,，,2,，,3,，,4,，,5,，指出在驻留集大小分别为,3,、,4,时，使用,FIFO,替换算法的缺页次数和缺页率。结果说明了什么？,先进先出（,FIFO,）页面置换算法（续）,Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5,3 frames (3 pages can be in memory at a time per process),4 frames,FIFO Replacement ,Beladys Anomaly,more frames, less page faults,1,2,3,1,2,3,4,1,2,5,3,4,9 page faults,10 page faults,1,2,3,1,2,3,5,1,2,4,5,4,4,3,例,一台计算机有四个页框，装入时间、上次引用时间、它们的,R,（读）与,M,（修改）位如下表所示（时间单位：嘀嗒），请问,NRU,、,FIFO,、,LRU,算法将替换哪一页？,页,装入时间,上次引用时间,R,M,0,126,279,0,0,1,230,260,1,0,2,120,272,1,1,3,160,280,1,1,小结,方法功能,单一,连续区,分区式,页式,段式,段页式,固定,可变,静态,动态,适用环境,单道,多道,多道,多道,多道,虚拟空间,一维,一维,一维,二维,二维,重定位方式,静态,静态 动态,动态,动态,动态,分配方式,静态连续区,静态 动态连续区,静态或动态页为单位非连续,动态段为单位非连续,动态分配页为单位非连续,释放,执行完后全部释放,执行完后全部释放,分区释放,执行完后释放,淘汰与执行完后释放,淘汰与执行完后释放,淘汰与执行完后释放,保护,越界保护,越界保护与保护键,越界保护与控制权保护,越界保护与控制权保护,越界保护与控制权保护,内存扩充,覆盖与交换,覆盖与交换,覆盖交换,虚拟存储,虚拟存储,虚拟存储,共享,不能,不能,较难,方便,方便,硬件支持,保护用寄存器,保护用寄存器，重定位机构,地址变换机构，中断机构，保护机构,段式地址变换机构，保护与中断机构，动态连接机构,段式地址变换机构，保护与中断机构，动态连接机构,一个磁盘系统，平均寻道时间为,12ms,，,转速为,10000,转,/,分，每个磁道有,18,个扇区，每个扇区,512,个字节。请问要读取一个扇区所花的时间是多少？,解：,T,S,= 12ms,T,R,= 1/2r = 60100000.5 = 3ms,T,A,=,b/rN,= (51260)(1851210000)= 0.33ms,T,T,= T,S,+ T,R,+ T,A,=12 + 3 + 0.33 = 15.33ms,答：读取一个扇区所花的时间是,15.33ms,。,例,5.6.2,磁盘调度,目标：减少寻道时间,1,、,FCFS,（,Fisrt,Come First Served,）先来先服务,特点：公平、简单，寻道时间长，相当于随机访问模式。,仅适用于请求磁盘,I/O,的进程数目较少的场合。,2,、,SSTF,（最短寻道优先）最短寻道时间优先,SSTF,比,FCFS,有更好的寻道性能,贪心的算法,饥饿现象,不能保证平均寻道时间最短 ？,图,5-25 FCFS,调度算法,图,5-26 SSTF,调度算法,3,、,SCAN,扫描算法（也称为电梯算法）。,进程“饥饿现象”,SSTF,存在。,SCAN,算法：,在移动方向固定的情况下采用了,SSTF,，以避免饥饿现象,存在请求进程等待延迟现象,4,、循环扫描,CSCAN,磁头单向移动,一个方向读完，不是象,SCAN,那样回头，而是循环扫描。,请求延迟时间：,2T,T+Smax,图,5-27 SCAN,调度算法示例,图,5-28 CSCAN,调度算法示例,例,假定盘块的大小为,1KB,硬盘的大小为,500MB,采用显示链接分配方式时,其,FAT,需占用多少存储空间（,FAT,表项占,2.5,个字节）,?,如果文件,A,占用硬盘的,11, 12 , 16, 14,四个盘块,试画出文件,A,中各盘块在,FAT,表中的链接情况,.,解：,此时硬盘共有,500M/1K=500K,个盘块，,FAT,表项共有,500K* 2.5B=1250KB,FAT,FCB,图,混合索引方式,例,存放在某个磁盘上的文件系统，对于采用混合索引分配方式，其,FCB,中共有,13,项地址项，第,0,9,个地址项为直接地址，第,10,个地址项为一次间接地址，第,11,个地址项为二次间接地址，第,12,个地址项为三次间接地址。如果每个盘块的大小为,512,字节，若盘块号需要,3,个字节来描述，而每个盘块最多存放,170,个盘块地址：,(1),该文件系统允许的最大长度是多少？,(2),将文件的字节偏移量,5000,、,15000,、,150000,转换为物理块号和块内偏移量。,(3),假设某文件的索引结点已在内存中，但其他信息均在外存，为了访问该文件中某个位置的内容，最多需要几次访问磁盘？,文件的最大长度为：,10+170+170,2,+170,3,=4942080,块,=2471040KB,5000/512,得商,9,，余数为,392,。即逻辑块号为,9,，块内偏移为,392,。故可直接从该文件的,FCB,的第,9,个地址处得到物理盘块号，块内偏移为,392,。,15000/512,得商为,29,，余数为,152,。即逻辑块号为,29,，块内偏移为,152,。由于,102910+170,而,29-10-19,，故可从,FCB,的第,10,个地址项，即一次间址项中得到一次间址块；并从一次间址块的,19,项中获得对应的物理盘块号，块内偏移为,152,。,(3),由于文件的索引结点已在内存，为了访问文件中的某个位置的内容，最少需要,1,次访问磁盘（即通过直接地址直接读文件盘块），最多需要,4,次访问磁盘（第一次是读三次间址块，第二次读二次间址块，第三次读一次间址块，第四次是读文件盘块）,例,有一个计算机系统利用下图所示的位示图（行号、列号都从,0,开始编号）来管理空闲盘块。如果盘块从,1,开始编号，每个盘块的大小为,1KB,。,（,1,）现要从文件分配两盘块，试具体说明分配过程。,（,2,）若要释放磁盘的第,300,块，应如何处理？,解,（,1,）分配过程,线形检索得：,i1=2,，,j1=2,；,i2=3,，,j2=6,。,计算空闲盘块号：,b1=i116+j1+1=216+2+1=35,b2=i216+j2+1=316+6+1=55,修改位示图：,令,map2,，,2=map3,，,6=1,，并将对应块,35,，,55,分配出去。,解,（,2,）释放过程,计算出第,300,块所对应的二进制行号,i,和,j,i=,（,300-1,）,/16=18,j=,（,300-1,）,% 16=11,修改位示图：,令,map18,，,11=0,。,例,用户与,OS,之间的接口有哪些方式？它们在什么情况下使用的？,解答：用户与操作系统之间的接口有以下方式：命令接口、程序接口、图形用户接口。,命令接口是用户在终端输入命令与系统交互或者是用户通过提交作业控制说明书来控制系统运行。这种方式要求用户记忆所以的命令，有较强的英语应用能力。,程序接口是通过系统调用来实现的，这种接口主要提供给程序员使用，在,OS,的外层软件或用户程序中，凡是与资源有关的操作都必须通过该接口向操作系统提出服务请求，并由,OS,代为完成。,图形化用户接口直观、方便、易学，更适合于普通用户使用。,
展开阅读全文