计算机操作系统复习知识点汇总2012

计算机操作系统复习大纲第 10 页 共 10 页第一章1、OS具有哪几个基本特征?它的最基本特征是什么?a. 并发性,共享性,虚拟性,异步性.b. 其中最基本特征是并发和共享. c. 共享又分为：同时共享和互斥共享。2、并行和并发概念并行性：是指两个或多个事件在同一时刻发生。并发性：是指两个或多少个事件在同一时间间隔内发生。3、操作系统的主要功能 处理机管理功能、存储管理功能、设备管理功能、文件管理功能4、操作系统与用户之间的接口 a. 用户接口：它是提供给用户使用的接口，用户可通过该接口取得操作系统的服务 b. 程序接口：它是提供给程序员在编程时使用的接口，是用户程序取得操作系统服务的惟一途径。5、操作系统的基本类型1、 批处理系统（又分为单道批处理系统和多道批处理系统）2、 分时系统3、 实时系统并理解三种基本操作系统的原理第二章进程1、进程的定义、特征，进程实体的组成 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。 进程具有结构特征、动态性、并发性、独立性和异步性。 进程实体由程序段、相关的数据段和进程控制块PCB三部分构成。2、进程的三种基本状态及其转换 掌握进程运行时的三种基本状态：就绪状态、执行状态、阻塞状态，并理解三种状态的含义。 掌握进程三个基本状态转换图 P38，掌握三种状态的变迁方向及变迁原因3、进程控制块（PCB）的作用 1）系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。 2）系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志 3）进程与PCB是一一对应的 4、进程控制块的组织方式 链接方式、索引方式5、进程与程序的区别程序是静态的，进程是动态的; 进程更能真实地描述并发,而程序不能; 进程具有创建其他进程的功能，而程序没有 进程只是一次执行过程，有生命周期；而程序可作为软件资源长期保存，是相对长久的;进程是系统分配调度的独立单位，能与其他进程并发执行;6、原语的定义及与一般过程的区别原语是由若干条指令组成的，用于完成一定功能的一个过程，与一般过程的区别在于：它们是“原子操作”，它是一个不可分割的基本单位，在执行过程中不允许中断。进程互斥与同步的基本概念7、 进程间的两种制约关系：i. 间接相互制约：源于进程对硬件资源的共享ii. 直接相互制约：源于进程间的合作8、 进程互斥与同步的基本概念i. 进程互斥：由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。ii. 进程同步：在并发执行过程中，合作完成同一个任务的多个进程，在执行速度或某些时序点上必须相互协调的合作，这种制约性关系叫作进程同步。（注：掌握进程互斥和同步的概念并能对生活中的这两种现象能进行分析和判断。 ）9、临界资源和临界区的概念 临界资源：是指每次仅允许一个进程访问的资源。 临界区：每个进程中访问临界资源的那段程序称为临界区（Critical Section）。不论是硬件临界资源，还是软件临界资源，多个进程共享这类资源时必须保证进程互斥地进入自己的临界区，即可实现进程对临界资源的互斥访问。10、同步机制应遵循的规则空闲让进、忙则等待、有限等待、让权等待11、 常用的几种信号量机制整型信号量、记录型信息量、AND型信息量、信号量集。12、 记录型 掌握记录型信号量的原理，并能对简单的进程同步、互斥问题、前趋图中的前趋关系用记录型信息量机制去实现（如作业题和书P54）。 掌握记录型信号量中的整型变量value的含义：如S.value0 表示有S个资源可用；S.value=0 表示无资源可用；S.value0 则|S|表示S等待队列中的进程个数进程通信10、进程通信的类型高级通信机制可归结为三类：共享存储器系统、消息传递系统以及管道通信系统。消息传递通信又可分为：直接通信（即消息缓冲队列通信）和间接通信（即信箱通信）。信箱分为：私用信箱、公用信箱、共享信箱。第三章1、高级调度与低级调度的区别 高级调度又称为作业调度，调度对象是作业，作业调度往往发生于一个（批）作业运行完毕，退出系统，而需要重新调入一个（批）作业进入内存时，故作业调度的周期长；低级调度又称为进程调度，调度物件为进程（或内核级线程），进程调度的运行频率最高，是最基本的一种调度，多道批处理、分时、实时三类OS中必须配置这种调度。2、进程调度方式 （1）非抢占方式（2）抢占方式3、调度算法1、 先来先服务FCFS2、 短作业（进程）优先SJF（SPF）3、 高优先权优先4、 高响应比优先调度算法（HRN）。5、 时间片轮转1) 要求：掌握算法思想。并能对前4种算法根据算法思想计算周转时间、平均周转时间、带权周转时间、平均带权周转时间，如：看作业题） 周转时间= 完成时间到达时间=等待时间+服务时间 响应比(等待时间要求服务时间)/要求服务时间响应时间/要求服务时间2) 掌握先来先服务、短作业（进程）优先、高响应优先调度算法三种算法性能评价：先来先服务算法即适合于作业调度也适用于进程调度，且算法较为简单，比较适合长作业（或长进程）不适合短作业（或进程）。短作业（进程）优先算法，能有效降低作业的平均等待时间，提高系统吞吐量。但该算法与用户做出的估计运行时间有很大的关系，对长作业（进程）不利，有利于短作业（进程）。高响应比优先调度算法，即照顾了短作业又考虑了长作业到达的先后次序，它不会使长作业长期得不到服务。死锁4、死锁的概念？产生死锁的原因和必要条件是什么？a.死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进；b.产生死锁的原因有二，一是竞争资源，二是进程推进顺序非法；c.产生死锁的必要条件是: 互斥条件，请求和保持条件，不剥夺条件和环路等待条件。互斥条件 ：一个资源一次只能被一个进程使用。请求和保持条件：保留已经得到的资源，还要求其它的资源。不剥夺条件：资源只能被占有者释放，不能被其它进程强行抢占。环路等待条件：系统中的进程形成了环形的资源请求链。5、处理死锁的基本方法（）预防死锁破坏产生死锁的四个必要条件中的一个或几个条件（）避免死锁在资源动态分配时，常用银行家算法来防止系统进入不安全状态。（）检测死锁（）解除死锁6、预防死锁的方法a.摒弃请求和保持条件b.摒弃不剥夺条件c.摒弃环路等待条件7、银行家算法 要求掌握能够根据安全性检测算法，通过查找安全序列来判断某个时刻系统是否处于安全状态。能利用银行家算法来计算：当某进程提出资源请求时，系统是否分配。（看书P110和作业题）8、死锁检测 掌握死锁定理的概念：当且仅当一组进程某个状态S的资源分配图是不可完全简化的，则说明S状态为死锁状态。 知道在进行死锁的检测常用的工具是资源分配图，并通过对资源分配图的化简判断一组进程是否处于安全状态。第四章程序的装入和链接、重定位i. 地址重定位的概念：即用户作业空间中的逻辑地址转换成物理空间中的物理地址。ii. 重定位的类型 ：分为静态重定位和动态重定位iii. 两种重定位的区别名称地址转换时刻谁来完成任务完成的结果静态重定位在程序运行之前由软件完成转换工作原来的指令地址被修改动态重定位推迟到指令执行时进行由一套硬件提供的地址转换机构完成执照形成的地址去执行这条指令，并不修改该指令连续内存分配方式 1、 单一连续分配2、 固定分区分配3、 动态分区分配1） 理解每种内存分配方式的思想及优缺点。2） 掌握动态分区常用的分区分配算法：首次适应、循环首次适应、最佳适应算法、最差适应算法，并掌握每种算法的分配思想基本分页存储管理方式（重点考查）1、分页的基本原理 分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，将这些页面装入到内存一些不连续的内存块中。当将一个进程的所有页面一次全部装入到内存的是基本分页；若按进程的运行情况分多次部分装入到内存的是请求式分页。由于进程的最后一页经常装不满一块而形成不可利用的碎片，称为“页内碎片”。系统为每个进程建立一张页面映像表，简称页表。页表的作用是实现从页号到物理块号的地址映射。2、分页系统的地址变换机构掌握：能根据给定的逻辑地址和页表内容转换出物理地址（注意在进行地址变换前要注意判断页号是否越界），并能掌握地址变换机构图P132。看作业题。基本分段存储管理方式1、分段存储管理方式的引入原因引入分段存储管理方式，主要是为了满足用户和程序员的一些需要：方便编程、信息共享、信息保护、动态增长、动态链接2、分段系统的基本原理在分段存储管理方式中，作业的地址空间被划分为若干个（二维）段，每个段定义了一组逻辑信息，逻辑地址由段号和段内地址组成。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址（又称为“基址”）。段表是用于实现从逻辑段到物理内存区的映射。将一个作业的这些段装入到内存一些不连续的区域中（在分段中一个作业获得的地址空间是不连续的，但是每个段获得的空间是连续的）。当将一个作业的所有段一次全部装入到内存的是基本分段；若按作业的运行情况分多次部分装入到内存的是请求式分段。在分段中会出现“碎片”。3、分段系统的地址变换机构掌握：能根据给定的逻辑地址和段表内容转换出物理地址（注意在进行地址变换前要注意判断段号和段地位移量是否越界。看作业题）。4、分段和分页的主要区别 a. 分页和分段都采用离散分配的方式，且都要通过地址映射机构来实现地址变换，这是它们的共同点；b. 对于它们的不同点有三，第一，从功能上看，页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率，即满足系统管理的需要，而不是用户的需要；而段是信息的逻辑单位，它含有一组其意义相对完整的信息，目的是为了能更好地满足用户的需要；c. 页的大小固定且由系统确定，而段的长度却不固定，决定于用户所编写的程序；d. 分页的作业地址空间是一维的，而分段的作业地址空间是二维的.请求分页存储管理方式、虚拟存储器的特征 虚拟存储器具有多次性，对换性和虚拟性三大主要特征；2、缺页中断常规中断的不同之处：在指令执行期间产生和处理；一条指令在执行期间，可能产生多次缺页中断。3、页面置换算法1、 先进先出FIFO2、 最佳置换算法OPT3、 最近最久未使用（LRU）置换算法4、 Clock置换算法5、 最少使用（LFU）置换算法1）要求：掌握算法思想、名称缩写。并能对前3种算法根据算法思想计算缺页中断次数和缺页中断率，参考书P150页和作业题。）2）掌握先进先出FIFO、最佳置换算法OPT、最近最久未使用（LRU）置换算法的性能评价 先进先出：实现简单；性能最差，与进程实际的运行不相适应，且有可能会出现Belady现象（即在未给进程或作业分配它所要求的全部页面时，有时会出现分配给作业的内存块数增多，缺页次数反而会增多的奇怪现象） 最佳置换算法OPT：理论上，性能最佳；实际上，无法实现；通常只用在研究其它算法时，做参考评价。 最近最久未使用（LRU）置换算法：性能较好；实现复杂，需要硬件支持。第五章、设备按使用特性、传输速率、信息变换、共享属性如何分类按传输速率分类：低速设备（键盘、鼠标、语音的输入输出设备）；中速设备（行式打印机、激光打印机）；高速设备（磁带机、磁盘机、光盘机）。按信息交换的单位分类：块设备（磁盘）；字符设备（交互式终端、打印机）按设备的共享属性分类：独占设备；共享设备（磁盘）；虚拟设备、I/O通道的概念及类型I/O通道是一种特殊的处理机，它具有执行I/O指令的能力，并通过执行通道（I/O）程序来控制I/O操作。通道与普通处理机的区别：1）没有自己的内存，且与主机共享主机内存2)执行的指令单一，主要执行与I/O有关的指令。通道分为：字节多路通道（主要连接低速字符设备）；数组选择通道（主要连接高速块设备）；数组多路通道（主要连接中高速块设备）3、输入输出控制方式（思想以及实现过程）1、 程序I/O方式2、 中断驱动I/O方式3、 DMA控制方式4、 I/O通道控制方式、DMA方式与中断控制方式的区别：相同点是都是以块为单位进行传输。区别是：1）CPU处理中断的时间：l 中断控制方式：是在数据缓冲寄存器满之后要求CPU进行中断处理l DMA方式：是在所要求转送的数据块全部传送结束时要求CPU进行中断处理。这就大大减少了CPU进行中断处理的次数。2）数据传送的完成者：l 中断控制方式：是在中断处理时由CPU控制完成的，l DMA方式：是DMA控制器完成的。6 常用的缓冲技术有：1）单缓冲 2）双缓冲 3）循环缓冲 4)缓冲池7、SPOLLing系统的定义、组成、特点 SPOOLing系统是对脱机I/O工作的模拟，其必须有高速随机外存（通常采用磁盘）的支持。SPOOLing系统主要有以下四个部分：（1）输入井和输出井，为磁盘上开辟的两大存储空间，分别模拟脱机输入/出时的磁盘，并用于收容I/O设备输入的数据和用户程序的输出数据；（2）输入缓冲区和输出缓冲区，在内存中开辟，分别用于暂存由输入设备和输出井送来的数据；（3）输入进程SPi和输出进程SPo，分别模拟脱机输入/出时的外围控制机，用于控制I/O过程；（4）I/O请求队列，由系统为各个I/O请求进程建立的I/O请求表构成的队列。SPOLLing系统的特点：提高了I/O的速度；将独占设备改造为共享设备；实现了虚拟设备功能。8、设备分配中的数据结构有：设备控制表DCT、控制器控制表COCT、通道控制表CHCT、系统控制表SDT。9、磁盘的类型和访问时间组成 磁盘分为两类：固定头磁盘（一般为大容量磁盘）和移动头磁盘（一般为中小型容量磁盘）。磁盘访问时间=寻道时间+旋转延迟时间+数据传输时间10、磁盘磁盘调度算法1、 先来先服务FCFS2、 最短寻道时间优先SSTF3、 扫描（Scan）算法（又称为“电梯调度算法“）4、 循环扫描（CScan）算法1）要求：掌握算法思想、名称缩写。并能根据算法思想计算碰头的寻道轨迹，寻道距离和寻道时间，参考书P194页和作业题。）2）掌握算法性能评价l 先来先服务FCFS：公平、简单；平均寻道时间可能较长，l 最短寻道时间优先SSTF：平均寻道时间比FCFS算法短，但可能会出现“饥饿现象”和“磁臂粘着”现象。l 扫描（Scan）算法：消除了“饥饿”现象，但可能会出现“磁臂粘着”现象。l 循环扫描（CScan）算法：改进了对于边缘区磁道访问的不公平，但可能会出现“磁臂粘着”现象。l 5.N-Step-Scan和FSCAN算法：可避免出现“磁臂粘着”现象。第六章、文件的定义文件是指由创建者所定义的、具有文件名的一组相关信息的集合。按文件的逻辑结构可分为有结构构文件和无结构文件。、文件类型按用途、文件中数据的形式、存取控制属性、组织形式和处理方式如何划分？ 按用途分类：系统文件、用户文件、库文件 按文件中数据的形式分类：源文件、目标文件、可执行文件 按存取控制属性分类：只执行文件、只读文件、读写文件按组织形式和处理方式划分：普通文件、目录文件、特殊文件（目录文件：由文件的目录信息构成的文件特殊文件：被视为文件的设备称为设备文件，也叫特殊文件。）、逻辑结构文件按不同方式组织形成哪几种文件？顺序文件、索引文件、索引顺序文件、顺序文件的适用场合、优缺点最佳适用场合是在对诸记录进行批量存取时。批量存取时对顺序文件的存取速率是所有逻辑文件中最高的；只有顺序文件能存储在磁带上，并能有效地工作。在顺序文件中如果想增加或删除一个记录都比较困难。5、外存分配方式1. 连续分配2. 链接分配3. 索引分配要求：掌握三种分配方式如何实现对一个文件分配外存空间，及三种方式的优缺点。1） 连续分配：要求为每一个文件分配一组相邻接的盘块；应在文件的目录项中记录第一个记录所在的盘块号和文件长度；（优点：(1)顺序访问容易；(2)顺序访问速度快；(3)所需的磁盘寻道次数和寻道时间最少。缺点： (1)要求有连续的存储空间（有外碎片问题）；(2)必须事先知道文件的长度,文件不能动态增长(3)不利于文件插入和删除。2） 链接分配：一个文件的信息存放在若干不连续的物理块中，各块之间通过链接指针连接，由前一个物理块指向下一个物理块，将同属于一个文件的多个离散的盘块链接成一个链表，由次所形成的物理文件称为链接文件。链接方式又可分为隐式链接和显式链接。优点：（1）提高了磁盘空间利用率,不存在 外部碎片问题；（2）有利于文件插入和删除；（3）有利于文件动态扩充。 缺点：只适合顺序存取，不适于随机存取；（2）不可靠，如指针出错；（3）需更多的寻道次数和寻道时间； 3） 索引分配：一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构索引表，将这些分配给文件的所有物理块号的块号都存放在该索引表中，并在文件目录项中填上指向该索引表的指针。相应的文件结构称为“索引结构”，相应的物理文件称为“索引文件”。分类：单级索引分配、多级索引分配、混合索引分配。优点：（1）即能顺序存取,又能随机存取；（2）满足了文件动态增长、插入删除的要求；（3）也能充分利用外存空间。缺点：需更多的寻道次数和寻道时间。6、对目录管理的要求有哪些？ 有以下要求：a) 实现“按名存取” b) 提高对目录的检索速度 c)文件共享 d) 允许文件重名7、目录的三种结构单级目录结构、 双级目录结构、 树型目录结构。1）单级目录结构：在整个文件系统中建立一张目录表，每个文件占一个目录项。优点：简单，能实现目录管理的基本功能-按名存取。缺点：查找速度慢；不允许重名；不便于文件共享。2）双级目录结构：为每个用户建立一个单独的目录UFD；系统中再建立一个主文件目录MFD，在主文件目录中，每个目录文件都占用一个目录项。优点：检索速度较快；不同的用户目录中文件可以同名；不同用户可以共享文件。3） 树型目录结构：若在两级目录结构中，进一步允许用户创建自己的子目录并相应地组织自己的文件，便可将两级目录变为三级文件目录。依次类推，可进一步形成四级、五级文件目录。把三级及以上文件目录结构称树型目录结构。树型目录具有检索效率高、允许重名、便于实现文件共享等一系列优点。8、文件存储空间常用的管理方法1空闲表法和空闲链表法（分为：空闲盘块链和空闲盘区链）；2位示图法；3成组链接法9、 位示图的概念：是利用二进制的一位来表示磁盘中一个盘块的使用情况。由所有盘块对应的位构成一个集合，称为位示图。利用位示图的行号和列号计算盘块号的公式盘块号=n*（i-1）+j利用盘块号计算行号和列号的公式为： i=（块号-1）/n +1 j=(块号-1) mod n+1 其中：i为行号，j为列号，n为每行的位数，所有值从1形如编号。10、 常用的两种文件共享方式基于索引结点的共享方式、利用符号链实现文件共享11、 文件的访问控制方式有：访问控制矩阵、访问控制表、访问权限表、口令、密码