【优选】操作系统期末复习PPT文档.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 操作系统引论,基本知识点,操作系统的定义、特点、功能,操作系统的基本类型及其特点,1.1 OS,的目标和作用,什么是操作系统？,操作系统是一组控制和管理计算机,硬件和软件资源,，,合理地对各类作业进行调度，,以及,方便用户使用,的程序的集合。,1.2,操作系统的发展过程,单道批处理系统,多道批处理系统,分时系统,实时系统,网络操作系统,分布式操作系统,1.2,操作系统的发展过程,操作系统的类型,一 单道批处理系统,在系统运行过程中，内存中只有一个用户作业存在,;,把一批作业脱机输入到磁带,/,磁盘上,;,系统配上监督程序，使这批作业一个个自动处理,;,处理机使用权在监督程序和用户作业间切换。,二 多道批处理系统,内存中允许多道程序存在,;,存在作业后备队列和作业调度程序,;,有,I/O,操作或完成作业时，调入另一个作业。,假脱机工作方式：,SPOOLING,系统,;,优点：资源利用率高、系统吞吐量大、系统切换开销小。,缺点：无交互能力、作业平均周转时间长。,三 分时系统,为满足人机交互能力的需求、共享主机,;,分时服务：时间片,分时系统特征：多路性、交互性、独占性、及时性。,四 实时系统,系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。,实时系统的类型：实时控制系统、实时信息处理系统。,假脱机工作方式：SPOOLING系统;,高级通信：进程间利用通信命令，传送大量数据的方式。,装入模块中为相对地址，复制到内存中为绝对地址。,重复扫描，从第步开始。,为每个用户建立一个单独的目录，系统在建立一个主文件目录。,3 基本分页存储管理方式,购票;,带权周转时间周转时间/服务时间,整个文件系统只建立一张目录表，每个文件占一个目录项。,用一位二进制位来表示磁盘中一个盘块的使用情况。,分页系统中不易实现共享和动态链接，分段则容易实现。,优点：资源利用率高、系统吞吐量大、系统切换开销小。,使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行具有可再现性。,查找01页面，A复位为0，未找到，下一步；,3 处理死锁的基本方法,记录为单位，定长记录、变长记录,根据进程请求访问磁盘的先后次序进行调度。,低级调度(进程调度)：决定就绪队列中那个进程获得处理机。,五 网络操作系统,高效可靠的网络通信能力，网络的连接,结构：,C/S,，,Peer to Peer,六 分布式操作系统,处理上的分布。,1.3,操作系统的特性,并发性,并行性和并发性区别,共享性,互斥共享方式、同时访问方式,1.3,操作系统的特性,虚拟性,指通过某种技术把一个物理设备变为若干个逻辑上的对应物。,虚拟对象类型,虚拟机：分时系统,虚拟内存：虚存管理技术,虚拟设备：,SPOOLING,技术,1.3,操作系统的特性,异步性,进程以人们不可预知的速度向前推进，但结果要保证是固定的。,原因：多道环境的复杂性。,1.4,操作系统的主要功能,处理机管理进程管理和调度,存储器管理物理内存的管理,设备管理外设的管理,文件管理外存空间的管理,用户接口方便用户使用,第二章 进程管理,基本知识点,程序的定义及特征，进程与程序的异同,进程的状态及引起状态转换的典型原因,临界资源的定义及操作原则,同步与互斥的概念，用信号量描述进程同步,经典进程同步算法的理解,2.1,进程的基本概念,1,前趋图,描述程序或程序段之间执行的前后关系。,2,进程的定义,进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动,;,是系统进行资源分配和调度的一个独立单位。,3,进程的特征,结构特征：程序段、数据段和,PCB,动态性,;,并发性,;,独立性,;,异步性,4,与程序的区别,进程是动态的,;,程序是静态的。,5,进程的基本状态及相互转换,就绪状态,执行状态,阻塞状态,6,挂起状态,增加了两个挂起状态：,挂起就绪、挂起阻塞,2.2,进程控制,1,引起进程创建的事件,用户登录,作业调度,提供服务,应用请求,2.3,进程同步,1,主要任务,使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行具有可再现性。,2,两种形式的制约关系,间接相互制约关系：源于进程对临界资源的共享,即,进程互斥,。,直接相互制约关系：源于进程间的合作，,即,进程同步,。,3,临界区,进程中访问临界资源的代码段。,4,同步应遵循的原则,空闲让进、,忙则等待、,有限等待、,让权等待。,5,信号量机制,信号量：仅能被两个原语操作,P/V,修改的整型变量。,类型,整型；,记录型：二元组,(S,Q),，,Q,初始状态为空的队列。,AND,型：一次需要多个共享资源。,信号量集：一次需要,N,个多类共享资源。,2.4,经典进程同步问题,1,生产者消费者问题,生产者与消费者互斥访问公用数据缓冲区。生产,“,数据,”,，消费,“,数据,”,。,2,读者写者问题,数据文件被多个进程共享并互斥访问。,允许多个读进程同时访问，但不允许一个写进程和其它读进程、写进程同时访问。,2.6,进程通信,1,进程通信类型,低级通信：利用信号量机制实现进程间的数据传递。,高级通信：进程间利用通信命令，传送大量数据的方式。,2,消息传递系统方式,直接通信方式：源进程直接把消息发送给目标进程。,间接通信方式：进程间通过一个共享数据结构，以消息暂存方式实现通信。,2.7,线程,1,线程的定义,线程是进程中可独立执行的子任务，是系统独立调度和分派的基本单位。,2,线程与进程的比较,拥有资源：线程几乎不占资源，进程是资源分配的基本单位。,调度：进程不再是调度的基本单位。,并发性：进程、线程之间都可以并发执行。,系统开销：线程开销小。,信号量例题,1,某车站售票厅，任何时刻最多可容纳,20,名购票者进入，当售票厅中少于,20,名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，则：,1,用,PV,操作管理这些并发进程时，应如何定义信号量，写出信号量的初值以及信号量各种取值的含义。,2,根据所定义的信号量，把应执行的,PV,操作填入下列代码中：,COBEGIN PROCESS PI(I=1,2,.),Begin,_;,进入售票厅,;,购票,;,退出,;,_;,End;,COEND,3,若欲购票者最多为,n,个人，写出信号量可能的最大值和最小值。,解,定义一信号量，初值为,20,。,意义：,表示可继续进入售票厅的人数；,表示售票厅已有,20,名顾客；,P3-P0-P2-P4,第四章存储器管理,基本知识点,分区存储管理的各种实现策略；,页式、段式存储管理方法及地址变换过程；,段页式存储管理思想及相关概念；,虚拟存储器的各种实现方法；,页面置换算法及缺页率,4.1,程序的装入和链接,1,从源程序到程序执行，通常需要经历三步：,编译,：由编译程序将源代码编译成若干个目标模块,;,链接,：由链接程序将一组目标模块，以及它们所需的库函数链接在一起，形成装入模块,;,装入,：由装入程序将装入模块复制到内存中。,通常链接和装入是一体的。,2,装入方式,绝对装入方式,装入模块中为绝对地址，直接装入。,可重定位装入方式（静态重定位）,装入模块中为相对地址，复制到内存中为绝对地址。,动态运行时装入方式（动态重定位）,复制到内存中依然为相对地址。,4.2,连续分配方式,分配方式,单一连续分配,分区分配,固定分区分配,动态分区分配,可重定位分区分配,1,单一连续分配,方法：,把内存分为系统区和用户区，系统区供,OS,使用，通常放在低址部分,;,系统区以外全部内存空间是用户区。,特点：,只能用于单用户、单任务,OS,。,实例：,MS-DOS,2,固定分区分配,方法,分区大小相等或不相等。,内存分配管理,分区按大小排队，建立一张分区使用表。由内存分配程序检索该表，找到符合要求的分区。,2,固定分区分配,特点,存在大的碎片，主存利用率低。,3,动态分区分配,方法,位置和大小都不固定，应作业的要求而设置。,数据结构的两种形式、,空闲分区表,空闲分区链,3,动态分区分配,存储分配算法,首次适应算法：分区按地址排序,循环首次适应算法,最佳适应算法：分区按容量排序,特点,产生小的碎片。,4,可重定位分区分配,利用拼接技术，对程序进行动态重定位，更好的利用内存小的碎片。,实现方法,由重定位寄存器实现，存放程序的起始地址。,4.3,基本分页存储管理方式,1,页表,页表存放在内存系统区的一个连续空间中，记录了每个页面对应的物理块号。,0,2,1,4,2,7,页号 块号,页表,2,地址变换机构,逻辑地址,给定一个逻辑地址,A,，已知页面大小为,L,，则其对应的页号和页内偏移为：,页号,P=INTA/L,页内地址,d=A MOD L,页号,p,位移量,w,2,地址变换机构,物理地址,地址变换过程,当进程要访问某个逻辑地址时，由分页地址变换机构转换成页号和页内地址,;,通过页号查找页表，如合法，则找到相应的物理块号,;,将块号加上页内偏移,(,块内偏移,),，即是物理地址。,块号,b,块内位移,d,2,地址变换机构,例题在一个页式存储管理系统中，页表内容如下表所示：,若页的大小为,4K,试求逻辑地址,0,转换成的物理地址。,页号,块号,0,2,1,1,2,6,3,3,4,7,解：转换成的物理地址为,8192,。,4.4,基本分段存储管理方式,1,基本原理,作业逻辑地址空间按意义分段，每个段存放在一个连续的内存分区中。,整个作业的逻辑地址为二维的，由段号段内地址组成。,2,段表,记录了逻辑段与内存位置的对应关系，包括段号、段基地址、段长等。,段号,段长,基址,0,30k,40k,1,20k,80k,2,15k,120k,3,10k,150k,3,地址变换机构,利用段表实现地址映射。,例某段表的内容如下：,段号 段首址 段长度,0 120K 40K,1 760K 30K,2 480K 20K,3 370K 20K,一逻辑地址为（,2,，,154,），它对应的物理地址为（）,4,分段与分页的区别,页是信息的物理单位，段是信息的逻辑单位,;,页的大小固定，段的大小动态变化,;,分页系统中逻辑地址是一维的，分段系统中是二维的,;,分页系统中不易实现共享和动态链接，分段则容易实现。,4.4.3,段页式存储管理方式,1,基本原理,分段和分页的结合,;,对内存进行分页，对用户作业进行分段，对各段再进行分页。,2,地址结构,地址结构由三部分组成：,段号段内页号页内地址。,地址变换,利用段表和页表实现地址映射。,4.4.3,段页式存储管理方式,优点,同时具备分段和分页管理的优点：分散存储，内存利用率高；,便于代码或数据共享；,支持动态链接等。,缺点,访问效率下降，一次数据访问需要三次访问内存。,4.5,虚拟存储器,局部性原理,时间局部性：,指令的重复执行循环；,空间局部性：,顺序访问相邻的存储单元顺序执行、数据访问。,2,虚拟存储器定义,指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。,3,实现方法,必须建立在离散分配的内存管理技术基础上。,分页请求系统,基本分页系统请求分页功能页面置换功能,分段请求系统,基本分段系统请求分段功能分段置换功能,4,特征,多次性,一个作业被分成多次调入内存运行,对换性,允许在作业的运行过程中进行换入、换出,虚拟性,能从逻辑上扩充内存容量。,虚拟性以多次性和对换性为基础,。,4.6,请求分页管理方式,物理块的分配策略,固定分配局部置换,进程占据的内存块数不变，但很难确定进程所需块数。,可变分配全局置换,空闲块由,OS,管理。,可变分配局部置换,当进程缺页率较高或较低时，由,OS,对其分配的物理块加以调整。,4.7,页面置换算法,最佳置换算法,选择以后永远不用或最长时间不用的页淘汰出去。,特点：,理论上性能最佳，实际上无法实现。,常用作研究其它算法的参考评价。,先进先出算法,选择最先进入系统的页淘汰出去。,特点,简单，与实际进程运行不相适应。,存在一种,Belady,现象。,最近最久未使用,LRU,算法,选择最近最久未被访问的页淘汰出去。,特点,性能好，实现复杂。,需要硬件支持，每页配置一个移位寄存器、或栈，增加系统开销。,4 CLOCK,算法，或,NRU,算法,每页设置一个访问位，内存中所有页链接成一个循环队列；,循环检查各页使用情况，访问位为,0,，选择该页淘汰；,访问位为,1,，复位访问位，继续查询。,5,改进的,CLOCK,算法,访问位,A,，修改位,M,共同表示一个页面状态。,三轮扫描：,查找,00,页面，未找到，下一步；,查找,01,页面，,A,复位为,0,，未找到，下一步；,重复扫描，从第步开始。,6,页面缓冲置换算法,消除频繁的磁盘,I/0,，设置两个链表，将页面链接起来：,空闲页面链表：不需写回磁盘，装入新页面时，在该表中选择一个页使用；,已修改链表：该链页数达到一定数目时，集中写到磁盘上。,、假设某程序的页面访问序列为,1,、,2,、,3,、,4,、,5,、,2,、,3,、,1,、,2,、,3,、,4,、,5,且开始执行时主存没有页面，,则在分配给该程序的物理块数是,3,且采用,FIFO,方式时缺页次数（）；,在分配给程序的物理块数是,4,且采用,FIFO,方式时，缺页次数是（）；,在分配给程序的物理块数是,3,且采用,LRU,方时，缺页次数是（）。,在分配给程序的物理块数是,4,且采用,LRU,方式时，缺页次数是（）。,第五章设备管理,基本知识点,设备分类,I/O,控制方式,SPOOLING,系统,缓冲区的概念和功能,磁盘调度算法,5.1 I/O,系统,I/O,设备类型,按传输速率分：低速、中速、高速,按信息交换单位分：块、字符设备,按共享属性分：独占、共享、虚拟设备,设备与控制器之间的接口,数据、控制、状态信号线,通道的类型,字节多路通道：多路分时复用,数组选择通道：独占使用，成组传送,数组多路通道：上两种技术的结合,解决单通道的瓶颈问题：增加设备到主机间的通路。,5.2 I/O,控制方式,程序,I/O,方式：忙等待,中断驱动方式：设备与,CPU,并行工作，以字节为单位交换数据。,DMA,控制方式：以块为单位传送数据,通道控制方式：以多个块为单位传送数据,5.3,缓冲管理,引入缓冲的原因,缓和,CPU,和,I/O,速度不匹配的矛盾,减少对,CPU,的中断频率，放宽对,CPU,中断响应时间的限制,提高,CPU,与,I/O,设备之间的并行性,缓冲技术的发展,单缓冲,双缓冲,循环缓冲,缓冲池：把专用循环缓冲变为公用缓冲区，以提高内存利用率,5.4,设备分配,1,设备独立性,应用程序独立于具体使用的物理设备。,易于实现,I/O,重定向：更换,I/O,操作的设备而不修改程序。,2 SPOOLING,技术,定义,将一台物理,I/O,设备虚拟为多台逻辑设备，从而允许多个用户共享使用一台物理设备。,即利用高速的共享设备,(,磁盘,),实现低速独占设备的共享技术。,又称为：假脱机操作。,2 SPOOLING,技术,组成：三个部分,输入井和输出井,输入进程和输出进程,输入缓冲区和输出缓冲区,5.6,磁盘存储管理,1,磁盘访问时间,寻道时间,旋转延迟时间,传输时间,数据存储在磁盘上的会影响,I,O,服务的总时间。假设每磁道划分成,10,个物理块，每块存放,1,个逻辑记录。逻辑记录,R1,，,R2,，,，,R10,存放在同一个磁道上，记录的安排顺序如下表所示：逻辑块,R1 R2 R3 R4 R5 R6 R7 R8 R9 R10,假定磁盘的旋转速度为,20ms,周，磁头当前处在,R1,的开始处。若系统顺序处理这些记录，使用单缓冲区，每个记录处理时间为,4ms,，则处理这,10,个记录的最长时间为（,1,）；若对信息存储进行优化分布后，处理,10,个记录的最少时间为（,2,）。（,1,）,A,180ms B,200ms C,204ms D,220ms,（,2,）,A,40ms B,60ms C,100ms D,160ms,解,从磁盘的转速：,20ms/,圈，可知：读取一条记录需要,2ms,。处理一条记录的前提，须将其读出来。所以处理第一条记录时，先将其读取出来，再进行处理，所以处理,R1,所需时间为,2ms+4ms,。当,R1,处理完时，磁头已经转到了,R4,的位置，此时要将其调整到,R2,的位置，需要经过,R5,，,R6,，,R7,，,R8,，,R9,，,R10,，,R1,，这样要耗,16ms,的时间，再加上读取,R2,需要,2ms,以及处理数据的,4ms,，,R2,的总处理时间应为,22ms,。所以,2+4+(16+2+4)*9=204ms,。优化后的排列顺序应为：,R1,，,R8,，,R5,，,R2,，,R9,，,R6,，,R3,，,R10,，,R7,，,R4,，这样的排列顺序刚好是处理完,R1,，磁头就到了,R2,的位置，直接读取,R2,，处理,R2,，处理完,R2,，磁头又到了,R3,的位置，依此类推，每条记录的读取及处理时间为：,2ms+4ms=6ms,，所以总时间为：,(2+4)*10=60ms,。,2,磁盘调度,先来先服务,FCFS,根据进程请求访问磁盘的先后次序进行调度。,优点：公平、简单,缺点：没有对寻道做优化，平均寻道时间可能较长。,最短寻道时间优先,SSTF,选择要求访问的磁道与当前磁头所在的磁道距离最近的进程请求，使每次的寻道时间最短。,特点,不能保证平均寻道时间最短，可能导致,“,饥饿,”,现象。,扫描算法,磁头每次做单向移动，直到达边缘为止，再做反向移动。,待访问的磁道只能在此次移动的前方，且距离最近的请求。,又称为,“,电梯调度算法,”,。,特点,消除了饥饿现象。,循环扫描算法,规定磁头只做单方向移动，不再反向移动扫描。,特点,改进了对于边缘区磁道访问的不公平。,N-STEP-SCAN,磁臂粘着,一个或几个进程对某一磁道有较高的访问频率时，造成磁头的,“,不移动,”,现象。,解决方法,把磁盘访问请求排成长度为,N,的多个队列。,多个队列之间按,FCFS,处理，一个队列之间按,SCAN,处理。,FSCAN,对,N,步扫描的简化。,只排成两个队列：当前队列、等待队列。,第六章文件管理,基本知识点,文件系统的基本概念,文件的逻辑结构,文件的物理结构,目录管理,文件存储空间的管理,6.1,文件和文件系统,文件类型,有结构文件,记录为单位，定长记录、变长记录,无结构文件,大量的源程序、可执行文件、库函数等，以字节为基本访问单位。,6.1,文件和文件系统,文件操作,打开文件：填写打开文件表中的表目、编号。,关闭文件：释放打开文件表的空间。,6.2,文件的逻辑结构,类型,顺序文件,索引文件,索引顺序文件,直接文件和哈希文件,顺序文件,特点,适用于批量存取、能适用于磁带存储。,单个或少量数据查找效率低。,索引文件,利用定长记录的顺序文件访问变长记录文件。,索引表本身是一个定长记录的顺序文件，记录键值、长度、指针。,索引顺序文件,顺序文件和索引文件的结合，最常见的一种逻辑文件形式。,主顺序文件的所有记录分组；,索引文件只记录每个分组的第一个记录指针。,直接文件和哈希文件,直接文件,记录键值,记录物理地址,哈希文件,利用哈希函数实现地址转换。,6.3,外存分配方式,类型,连续分配,链接分配,索引分配,连续分配,为每一个文件分配一组相邻接的盘块，物理上形成顺序文件结构。,外存上容易出现,“,碎片,”,，用,“,紧凑,”,方法解决。,特点,顺序访问容易、速度快。,要求有连续的存储空间，必须事先知道文件的长度。,链接分配,离散分配方式，消除了,“,碎片,”,，有利于文件的增删改。,分类,隐式链接,显式链接,隐式链接,在文件的每个目录项中，都含有指向链接文件第一个盘块和最后一个盘块的指针。,只适合于顺序访问。,显示链接,把用于链接文件各物理块的指针，显式地存放在内存的一张,“,文件分配表,”,FAT,中。,在文件目录中记录第一个盘块号。,FCB-FAT,索引分配,单级索引分配,每个文件分配一个索引块。,多级索引分配,当文件较大时，需要很多个索引块，可以为各索引块建立一个索引块。,混合索引分配,6.4,目录管理,要求,实现按名存取,提高对目录的检索带速度,文件共享,允许文件重名,目录结构,单级目录结构,整个文件系统只建立一张目录表，每个文件占一个目录项。,缺点：,查找速度慢；,不允许重名；,不便于文件共享。,目录结构,两级目录结构,为每个用户建立一个单独的目录，系统在建立一个主文件目录。,特点,检索较快；不同的用户目录中文件可重名；,不同用户可以用不同的文件名共享同一文件。,目录结构,多级目录结构树型目录结构,路径名,绝对路径,相对路径,当前目录：消除使用全文件名访问文件的麻烦。,6.5,文件存储空间的管理,方法,空闲表,空闲链表法,位示图,成组链接法,空闲表法,连续分配方法。,空闲表组织方式,按地址排序，记录序号、空闲区起始盘块号、盘块数等。,空闲表法,存储空间的分配,首次适应算法,循环首次适应算法,空间的回收,考虑邻接的前后空闲区拼接合并。,空闲链表法,离散分配方法。,两种形式的链表,空闲盘块链：分配、回收一个盘块。,空闲盘区链：与内存的动态分区管理类似。,位示图法,用一位二进制位来表示磁盘中一个盘块的使用情况。,盘块的分配,顺序找描位示图，找到一个或一组值为,0,的位；,将找到的位转换成与之相对应的盘块号：,b=n(i-1)+j,修改位示图,2 两种形式的制约关系,（1）A180ms B200ms C204ms D220ms（2）A40ms B60ms C100ms D160ms,合理地对各类作业进行调度，,低级调度(进程调度)：决定就绪队列中那个进程获得处理机。,(4)系统执行安全性算法，检查此次分配后，系统是否安全。,(1)如果RequestijNeedi,j,转(2)，否则出错。,记录了逻辑段与内存位置的对应关系，包括段号、段基地址、段长等。,当前目录：消除使用全文件名访问文件的麻烦。,不同的用户目录中文件可重名；,系统配上监督程序，使这批作业一个个自动处理;,桌上有一空盘，只允许放入一个水果。,操作系统的定义、特点、功能,死锁的概念、产生的原因和必要条件,0 0 2,具有最短平均等待时间的算法是哪个？,访问效率下降，一次数据访问需要三次访问内存。,位示图法,盘块的回收,将回收的盘块号转换成位示图中的行号和列号,i=(b-1)DIV n+1,，,j=(b-1)MOD n+1,修改位示图,位示图法,特点,从位示图中很容易找到一个或一组邻接的空闲盘块；,位示图占用空间小，可常驻内存。,成组链接法,空闲盘块的组织,空闲盘块号栈,课程结束，谢谢大家！,谢谢观看,