惠州学院2013操作系统复习整理.doc

操作系统复习课.by fain7第一章l 操作系统的目标-有效性、方便性、可扩充性、开放性l OS的发展过程-几类典型操作系统(多道批处理、分时、实时)，每类操作系统的原理、特征及优缺点多道批处理系统.原理：20世纪60年代中期引入多道程序设计技术，由此形成了多道批处理系统。在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。优缺点：（1）资源利用率高（2）系统吞吐量大（3）平均周转时间长（4）无交互能力分时系统.原理：分时系统是指在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。特征（优缺点）：（1）多路性（2）独立性（3）及时性（4）交互性实时系统.原理：实时系统是指系统能及时（或即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。需求：实时控制，实时信息处理。特征（优缺点）：（1）多路性（2）独立性（3）及时性（4）交互性（5）可靠性l OS的主要功能-资源管理器和用户接口主要功能：处理机管理（进程控制、进程同步、进程通信、调度），存储器管理（内存分配、内存保护、地址映射、内存扩充），设备管理（缓冲管理、设备分配、设备处理），文件管理（文件存储空间的管理、目录管理、文件的读/写管理和保护）。操作系统和用户之间的接口：用户接口：联机用户接口，脱机用户接口、图形用户接口程序接口：该接口是为用户程序在执行中访问系统资源而设置的，它是由一组系统调用组成。第二章l 什么是程序的并发执行，如何用前驱图描述程序(段)间的并发执行程序并发执行：若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。（前驱图为平行四边形状）l 进程的概念，进程实体的组成，进程与程序(作业)的区别进程是操作系统结构的基础；是一个正在执行的程序；计算机中正在运行的程序实例；可以分配给处理器并由处理器执行的一个实体。（最基本的特征：动态性；重要特征：并发性；另外还有独立性和异步性）进程实体：由程序段、相关的数据段和PCB三个部分便构成了进程实体。进程的实质是进程实体的一次执行过程。进程和程序区别：（1）进程是一个动态概念，强调执行的过程，每个进程中包含了程序段和数据段两个部分，以及进程控制块PCB；而程序是一个静态概念，程序是指令的有序集合，无执行含义；（2）进程具有并行特征（独立性，异步性），程序则没有；（3）一个进程可以执行多个程序（如Linux中通过exec调用），同一程序的多次执行将产生多个不同的进程。同一个程序的一次执行也可产生多个进程（如在程序中多次调用Linux中的fork）。进程和作业的区别在于：一个进程是一个程序对某个数据集的执行过程，是分配资源的基本单位。作业是用户需要计算机完成某项任务，而要求计算机所做工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完成四个阶段。而进程是已提交完毕的程序所执行过程的描述，是资源分配的基本单位。其主要区别关系如下：（1）作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行；而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中；（2）一个作业可由多个进程组成。且必须至少由一个进程组成，但反过来不成立；（3）作业的概念主要用在批处理系统中，像UNIX这样的分时系统中，则没有作业的概念；而进程的概念则用在几乎所有的多道程序系统中。l 进程的3种基本状态，状态间的转换已及引起状态转换的原因(基本的进程状态转换图)就绪(Ready)状态：当进程已分配到除CPU以外的所有必要的资源，只要获得处理机便可立即执行，这时的进程状态称为就绪状态。通过进程调度变为执行状态。执行（Running）状态：当进程已获得处理机，其程序正在处理机上执行，此时的进程状态称为执行状态。时间片用完后变为就绪状态。阻塞(Blocked)状态：正在执行的进程，由于等待某个事件发生而无法执行时，便放弃处理机而处于阻塞状态。引起进程阻塞的事件可有多种，例如，等待I/O完成、申请缓冲区不能满足、等待信件(信号)等。l 什么是进程间的两种相互制约关系-同步、互斥进程同步（直接相互制约关系）：它主要源于进程合作，是进程间共同完成一项任务时直接发生相互作用的关系。为进程之间的直接制约关系。在多道环境下，这种进程间在执行次序上的协调是必不可少的。进程互斥（间接相互制约关系）：它主要源于资源共享，是进程之间的间接制约关系。在多道系统中，每次只允许一个进程访问的资源称为临界资源，进程互斥就是保证每次只有一个进程使用临界资源。l 什么是信号量、什么是P操作、什么是V操作(P、V操作的处理流程，以记录型信号量为例)信号量是Dijkstra提出的用于解决进程同步的有效工具。信号量是一个数据结构以及对其的操作。除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。两个语句在执行到一半的时候不能被中断。每次wait操作，意味着进程请求一个单位的该类资源，使系统可供分配的该类资源数减少一个。每次signal操作，表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个。l 用信号量和P.V操作机制实现互斥和同步的方法，信号量取值的含义利用信号量和P.V操作实现进程互斥时：（1）每个程序中用户实现互斥的P,V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。（2）P,V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。（3）互斥信号量得初值一般为1。其中信号量S用于互斥，初值为1。利用信号量和PV操作实现进程同步：PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。使用PV操作实现进程同步时应该注意的是：（1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，那些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置那些信号量。（2） 信号量的初值与相应资源的数量有关，也与P,V操作在程序代码中出现的位置有关。（3）同一信号量的P,V操作要成对出现，但他们分别在不同的进程代码中。l 用P、V操作实现相互合作的几个进程间的同步、共享临界资源的进程互斥(问题如经典的进程同步问题)进程同步：把异步环境下的一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。先私有，后公有。用wait（消息名）表示进程等待合作进程发来的消息.功能：等待到消息名为true的进程继续执行。用signal（消息名）表示向合作进程发送消息功能：发送消息名，并将其值置为true。利用过程wait和signal描述计算进程Pc和打印进程Pp的同步关系（1） 设消息名Bufempty表示buf为空，消息名Buffull表示Buf中装满了数据。（2） 初始化Bufempty=true，Buffull=false.。（3） 描述：Pc ：A：wait(Bufempty) 计算 Buf -计算结果 Bufempty -false signal(Buffull) Goto APp ：B：wait(Bufful) 打印Buf中的数据 清除Buf中的数据 Bufful -false signal(Bufempty) Goto Bl 什么是进程的(高级)通信，类型，各类的原理高级通信（进程通信）：用户直接利用该操作系统所提供的一组通信命令高效的传送大量数据的一种通信方式。1) 共享存储器系统：相互通信的进程共享数据结构或存储区，通过这些进行通信。基于共享数据结构的通信方式，基于共享存储区的通信方式2) 消息传递系统：程序员直接利用操作系统提供的一组通信命令，不仅实现大量数据的传递，而且还隐藏了通信的实现细节。数据交换是以格式化的消息为单位的（报文）。（分为直接和间接通信两种方式）3）管道通信：用于连接一个读进程和一个写进程的共享文件，pipe文件。管道机制提供的能力：互斥，同步，确定存在才通信。第三章l 对于本章内的基本调度算法：算法思想、就绪队列的组织、是抢占还是非抢占FCFS算法思想：当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。FCFS是非抢占式的调度算法。短作业（进程）优先调度算法思想：短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先（SPF）调度算法则是从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。短作业调度算法是非抢占式的调度算法。非抢占式优先权调度算法和抢占式优先权调度算法思想：非抢占式优先权调度算法：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成，或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一个优先权最高的进程。抢占式优先权调度算法：系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。l 典型的动态优先权调度算法-高响应比优先度调度算法；典型的实时调度算法-最低松弛度优先调度算法；静态优先权和动态优先权算法思想：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的。高响应比优先调度算法思想：为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然会分配到处理机。该优先权的变化规律可描述为：优先权=（等待时间+要求服务时间）/ 要求服务时间基于时间片的轮转调度算法思想：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。旧队首进程使用完时间片后就到就绪队列的末尾，然后处理机分配给新的队首进程。多级反馈队列调度算法思想： 设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之。时间片越来越大。当一个新进程进入内存后，首先将它放入第一个队列的末尾，按FCFS原则排队等待调度。如果一个时间片后进程尚未完成，调度程序便将该进程转入第二个队列的末尾，再同样地按FCFS原则等待调度执行。当一个长作业从第一个队列一次降到第n个队列后，在第n队列中便采取按时间片轮转的方式运行。仅当第一队列空闲时，调度程序才调度第二队列中的进程运行。l 时间片轮转法中，时间片取值的影响时间片取值的影响：如果选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁地发生中断、进程上下文的切换，从而增加系统的开销；反之，如果选择太长的时间片，使得每个进程都能在一个时间片内完成，时间片轮转算法便退化为FCFS算法，无法满足交互式用户的需求。如何确定时间片的大小：时间片应略大于一次典型的交互需要的时间。这样可使大多数进程在一个时间片内完成。一般应考虑三个因素：系统对响应时间的要求、就绪队列中进程的数目和系统的处理能力。l 什么是死锁，死锁产生的原因和必要条件死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。产生死锁的原因：竞争资源、进程间推进顺序非法。产生死锁的必要条件：互斥条件，请求和保持条件，不剥夺条件、环路等待条件。l 处理死锁的四种基本方法-基本思想预防死锁：设置限制条件去破坏四个必要条件中的一个或多个。避免死锁：资源的动态分配过程中，防止系统进入不安全状态。检测死锁，解除死锁：检测与解除互相配套。l 避免死锁的银行家算法，数据结构，算法思想银行家算法中的数据结构： 可利用资源向量 Available； 最大需求矩阵Max； 分配矩阵 Allocation； 需求矩阵 Need。【三个矩阵间存在下述关系：Needpi,j = Maxi,j Allocationi,j】银行家算法思想：（1）如果Request ij = Needi,j，便转向步骤（2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Request ij = Availablej，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的值：Availablej:=Availablej Request ij;Allocationi,j:=Allocationi,j + Request ij;Needi,j:=Needi,j Request ij;（4）系统执行安全性算法，检查此次算法分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。安全性算法：（1）设置两个向量：工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，它包含有m个元素，在执行安全算法开始时，work:=Available。Finish，它表示系统是否有足够的资源分配给进程，是指运行完成。开始时先做Finishi :=false；当有足够资源分配给进程时，再令Finishi:=true。（2）从进程集合中找到一个能满足下述条件的进程：1）Finishi=false；2）Needi,jTL，表示段号太大，访问越界，产生越界中断信号；若未越界，则根据段表始址和段号，计算出对于段表项的位置，从中读出该段在内存的起始地址，若段内地址d超过该段段长SL，即SSL，同样发出越界中断信号；若未越界，则将该段的基址与段内地址d相加，得到物理地址。存储分配和存储回收过程；以段为单位分配内存，每段分配一个连续的内存区。由于各段长度不等，所以这些存储区的大小不一。而且，同一进程所包含的各段之间不要求连续。段式管理的内存分配和释放是动态进行的，与分区式管理一样可以采用最先适应法、最佳适应法、最坏适应法等进行空闲区分配。内存回收法也同分区式管理。当内存中没有足够的空闲区时，需要淘汰算法。存储共享和保护：在多道环境下，由于进程的并发执行，一段程序为多个进程共享时，有可能出现多次同时重复执行该段程序的情况。这就要求它在执行过程中，该段程序的指令和数据不能被修改。共享段进行内外存交换时，应该设置一个共享位。1）地址越界保护法； 2）存取方式控制保护法段页式存储管理方式：基本思想：段式管理和页式管理的结合。段式管理为用户提供了一个二维的虚地址空间，反映了程序的逻辑结构，有利于段的动态增长以及共享和内存保护等，这大大方便了用户。而分页管理系统则有效地克服了碎片，提高了存储器的利用率。从存储管理的目的来讲，主要是方便用户的程序设计和提高内存的利用率。使用的数据结构：段表S，页表P，段号，页号，页内相对地址D。逻辑地址格式，地址变换的时间、方法：设置快速联想寄存器。它用于存放当前最常用的段号、页号和对应的内存页面与其它控制用栏目。存储分配和存储回收过程；类似分页存储存储共享和保护：类似分段存储第五章l OS在设备管理中引入的相关技术-中断技术、DMA技术、通道技术、总线技术、缓冲技术、虚拟设备技术(Spooling技术)-了解组成和工作原理中断技术。组成：CPU，I/O控制器。（主要工作：进行进程上下文的切换，对处理中断信号源进行测试，读取设备状态和修改进程状态等）工作原理：唤醒被阻塞的驱动程序进程 - 对被中断进程的CPU环境进行保护 - 分析中断原因，转入相应的中断处理程序 - 中断处理 - 回复被中断进程的现场。DMA技术。组成：CPU，内存，DMA控制器（主机与DMA控制器的接口；DMA控制器域块设备的接口；I/O控制逻辑；命令/状态寄存器CR；内存地址寄存器MAR；数据寄存器DR；数据计数器DC）工作原理：当处理器需要读/写一整块数据时，给DMA控制单元发送一条命令，包含：一次读或写的指令、I/O设备的地址、开始读或写的主存地址、需要传送的数据长度等；处理器发送完命令后就可处理其它事情；DMA控制器自己独立管理整块数据的传送；当这个过程完成后，它会向处理器发一个中断请求。处理器只在一块数据开始传送和传送结束时关注一下I/O操作即可。通道技术。组成：每条通道指令包含的信息是：操作码、内存地址、计数、程序结束位、记录结束位。（字节多路通道，数组选择通道，数组多路通道）工作原理：把DMA方式中CPU以数据块为单位对读/写任务的干预，减少为以一次读/写任务及有关的控制和管理为单位的干预。 同时，又可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。缓冲技术。组成：单缓冲（不能同时输出和提取），双缓冲（一个输出，一个提取），循环缓冲（多个缓冲区，多个缓冲指针），缓冲池（收容输入，提取输入，收容输出，提取输出）工作原理：在CPU与外设之间建立缓冲区，用于暂存CPU与外设间交换的数据，从而缓冲CPU与外设间速度不匹配的矛盾。Spooling技术。组成：1）在磁盘上开辟输入井和输出井；2） 在内存中开辟输入缓冲区和输出缓冲区；3）OS要有相关的管理进程：SPi，模拟脱机输入；SPo模拟脱机输出。假脱机操作（spooling）：用专门的外围控制器机，将I/O设备数据传送到高速磁盘，或者相反，外围操作与CPU处理同时进行。将一台物理I/O设备虚拟成多台逻辑I/O设备。工作原理：在多道环境下，可以用OS的一道管理程序实现从I/O设备输入数据并存放到磁盘上，模拟脱机输入；用OS的另一道管理程序将磁盘上的数据输出到I/O设备上，模拟脱机输出；这种假脱机I/O操作称为Spooling技术（是一种虚拟设备技术、一种资源转换技术）。l 什么是磁盘调度，磁盘调度的目标，磁盘调度算法(FCFS、SSTF、SCAN)的原理磁盘调度：当有多个进程同时要求访问磁盘时，安排对磁道访问请求的执行顺序。磁盘调度的目标是使磁盘的平均寻道时间最少。先来先服务FCFS：根据进程请求访问磁盘的先后次序进行调度。最短寻道时间优先SSFT：要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。扫描算法SCAN：不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。循环扫描算法CSCAN：自里向外访问，访问最外磁道后立即返回最里磁道。第六章l 什么是文件的逻辑结构，有哪几种(记录式和流式)，结构如何文件的逻辑结构：这是用用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。记录式文件的逻辑结构：1、有结构文件：记录的长度可分为定长和不定长两类：定长记录；变长记录。根据用户和系统管理上的需要，可采用多种方式来组织这些记录，形成下述的几种文件：顺序文件；索引文件；索引顺序文件。2、无结构文件：流式文件，其长度以字节为单位。l 什么是文件的物理结构，文件的物理结构(外存分配方式)有哪几种(顺序、链接、索引)，每一种文件物理结构的实现方法，需要用到的数据结构，目录中如何记录文件地址文件的物理结构（文件的存储结构），是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。外存的分配方式：连续分配：实现方式：为每个文件分配一组位置相邻接的盘块(物理地址连续的外存空间)，文件中的逻辑页被顺序地存放到相邻的物理盘块中。这保证了文件中的逻辑顺序与文件占用盘块顺序的一致性。这样物理结构的文件称为顺序文件。每个文件都从分配给它的一个盘块的第一个字节开始存放。记录文件地址：在文件的目录中，存放该文件的第一个记录所在的盘块号和文件的长度(共占多少块)链接分配：实现方式：为每个文件分配一组位置离散的盘块，每个盘块中存放文件的一个逻辑页。通过在每个盘块上设置一个指针，将属于同一个文件的盘块顺序地链接在一起，链接的顺序和文件的逻辑顺序一致。这样物理结构的文件称为链接文件。链接方式有隐式链接和显式链接两种。记录文件地址：显示链接：每个文件的第一个盘块的编号存放在文件目录中；文件的其他盘块的编号存放在FAT中；隐式链接：目录和FAT一起记录了哪些盘块分给了这个文件以及这些盘块中内容的逻辑顺序。索引分配：实现方式：为每个文件分配一组位置离散的盘块，为每个文件建立一个物理结构的索引表，记录分配给该文件的物理盘块，以及这些盘块和文件逻辑顺序的对应关系。建立一个文件时，要初始化它的索引表，并将索引表的地址放到文件的目录中。打开一个文件时，文件的索引表也被同时读入内存。记录文件地址：单级索引：每个文件一张索引表，这张索引表放在一个盘块中。多级索引：对于一个长文件的索引表(内容同上，但单个盘块放不下)，可以将它存放在若干个离散的盘块中。再为这些索引块建立一个索引表，存放在一个盘块中，这样就形成了一个文件的两级索引。混合索引：文件系统混合使用多种分配方式。文件的目录中可以存放不同形式的地址信息：直接地址，文件数据的盘块号；一次间接地址，文件索引块的盘块号；二次间接地址，文件二级索引块的盘块号。l 单级、两级和多级(树型)目录结构的构成，逐步能实现的功能(特点)单级目录结构：构成：为整个文件系统建立一张目录表，每个文件占一个目录项。功能：单级目录的优点是简单且能实现目录管理的基本功能-按名存取。缺点：(1)查找速度慢；(2)不允许重名；(3)不便于实现文件共享。两级目录结构：构成：系统给每一个用户建立一张独立的用户目录表(UFD)，用来存放该用户所有文件的FCB， UFD的结构与单级目录表相似，它以一个目录文件的形式存在磁盘上；整个文件系统有一张主目录表(MFD)，其中的每一个表目(一行)用来存放一个UFD文件的名字、大小、存放位置等信息(目录文件的FCB)。这样就形成了两级目录。优缺点：解决了文件的重名问题和文件共享问题，提高搜索速度，查找时间降低。妨碍了用户间的文件共享，增加了系统开销多级目录结构：构成：将两级目录的这种层次结构推广，就形成多级目录。在多级目录结构中，MFD演变为文件系统的根目录，在根目录中可以存放一般文件的FCB，也可以存放目录文件的FCB；每一个目录文件对应一张目录表，其中既可以存放一般文件的FCB，也可以存放目录文件的FCB。优缺点：层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；提高文件检索速度；能进行存取权限的控制。查找一个文件按路径名逐层检查，由于目录文件和普通文件都放在外存，多次访盘，影响速度。l 磁盘空间的组织管理方法-空白文件目录、空闲链表、位示图、成组链-每种方法的数据结构，存储分配和回收的方法空闲表法：为每个文件分配一块连续的存储空间按，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。空闲链表法：1）、空闲块链法：将磁盘上所有的空闲块拉成一条链，在链首设一个分配指针，在链尾设一个回收指针。空闲块的分配与回收分别在链的首尾进行。2）.空闲区链法：将磁盘上所有的空闲区拉成一条链，空闲区中要记录本区包含的空闲块数。存储空间的分配与回收与内存的动态分区分配类似。位示图法：空闲块的组织：在内存中划出连续若干个字，为每一个文件存储器建立一张位示图。磁盘的每一个物理块都