计算机操作系统期末复习.ppt

考试总分平时成绩(20%)期中(20%)+期末（60%）题型：名词解释(3分515分)简答题(5分420分)判断题（2分1020分）应用题（35分，共4题）,第一部分 概述（1，2章）,1、计算机系统的四大构成部件。2、处理器寄存器分类及常用寄存器功能PC，IR，MAR，MBR，I/OAR，I/OBR等,3、指令执行步骤：取指阶段-执行阶段4、指令的动作Processor-memory：transfer data between processor and memoryProcessor-I/O：data transferred to or from a peripheral deviceData processing：arithmetic or logic operation on dataControl：alter sequence of execution5、什么是中断？中断处理过程及如何处理多中断CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程。即在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。,6、存储器层次7、高速缓冲存储原理利用程序局部性原理，在处理器访问主存时，首先查看所要访问的数据是否在Cache中，如果在，则从Cache中传递给处理器；如果不在，再从主存中将所需数据读取到Cache中，然后传给处理器。,8、操作系统的定义。是管理系统资源、控制程序执行，改善人机界面，提供各种服务，合理组织计算机工作流程和为用户有效使用计算机提供良好运行环境的一种系统软件。9、OS的主要功能：处理机管理，用于分配和控制处理机；存储器管理，主要负责内存的分配与回收；I/O设备管理，负责I/O设备的分配与操纵；文件管理，负责文件的存取、共享和保护。,10、操作系统的目标：方便、有效、扩展能力11、操作系统的基本特征-并发性-共享性-虚拟性-异步性,12、了解操作系统的发展串行处理：没有OS，完全人工操作简单批处理（单道）：自动作业序列，由Monitor控制执行多道程序批处理：多个程序同时进入主存运行，进一步提高了资源利用率分时系统：多个交互作业，利用分时技术，多个用户分享处理器时间实时系统：用于专用系统，进行实时控制与实时信息处理;强调即时响应和高可靠性，以在规定时间内完成对事件的处理为特征.,13、了解几个主要操作系统的发展过程及特点如：UNIX，Linux，Windows等14、操作系统内核的定义内核：提供支持系统运行的基本功能和基本操作的一组程序模块。微内核(MicorKernel):具有尽量少的必须功能的内核。在微内核操作系统中，内核是指精心设计的、能实现现代OS最基本的核心功能的部分。,15、OS发展中5个重要的理论进展进程存储器管理信息保护和安全调度和资源管理系统结构,16、现代操作系统的特征微内核体系结构多线程对称多处理分布式操作系统面向对象设计,第二部分 进程（3，4，5，6章）,1、什么是进程(Process)？PCB的作用。进程是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。每一个进程有一个进程控制块PCB，其作用是用于记录和刻画进程状态及有关信息的数据结构，是操作系统掌握进程的唯一资料结构。进程控制块中，分进程标识符、进程状态信息和进程控制信息三类。,2、处理器有2种状态（模式）：管态（核心态）和目态（用户态）。3、进程切换与模式切换的区别。进程切换是让处于运行态的进程中断运行，让出处理器，这时要做一次进程上下文切换、即保存老进程状态而装入被保护了的新进程的状态，以便新进程运行。进程切换首先要产生中断，因为进程切换必须在核心态发生。需要操作系统占有CPU。模式切换，当发生系统调用或中断时，会暂时中断正在执行的用户进程，把处理器状态从用户状态切换到内核状态，去执行操作系统例行程序以获得服务，这就是一次模式切换，内核在被中断了的进程的上下文中对这个中断事件作处理，即使该中断可能不是此进程引起的。进程切换首先会进行模式切换。模式切换不一定导致进程切换。,4、线程是“进程”中某个单一顺序的控制流。也被称为轻量进程。在有线程的系统中，进程是系统进行保护和资源分配的单位，线程是调度的单位。,5、程序、进程与线程的区别。程序是一段静态的代码；可以脱离机器长期保存；进程是程序的一次执行过程，是动态的，有生命周期。一个程序可以对应多个进程，但一个进程只能对应一个程序。进程和程序的关系犹如演出和剧本的关系。早期以进程为资源分配和系统调度的基本单位；由于进程与进程之间切换开销大，从而引入了线程。一个进程可以包含多个线程，在有线程的系统中，进程是系统进行保护和资源分配的单位，线程是调度的单位。,6、掌握进程的五态模型及其转换条件。,7、掌握进程的七态模型及其转换条件。,进程为什么要被挂起？,8、线程的两种实现方式：ULT、KLT9、SMP,10、并发进程,无关进程：操作的变量集合没有交集交互进程：共享某些变量。,并发进程间的关系,竞争:无关进程之间竞争资源。(进程互斥)协作:交互进程需协调工作。(进程同步),进程同步（Synchronization）指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。进程互斥（Mutual Exclusion）指若干进程要使用同一共享资源时，任何时刻最多允许一个进程使用，其他进程必须等待，直到占有资源的进程释放该资源。,11、临界资源：一次仅允许一个进程使用的资源 什么是临界区：在每个进程中访问临界资源的那段程序 进入临界区的准则：空闲让进、忙则等待、有限等待、让权等待,12、信号量（Semaphores）信号量是一种数据结构，其中包含了一个整数和一个队列。整数用于收发信号，队列用于维护等待该信号的进程。公用信号量：联系一组并发进程，相关的进程均可在此信号量上执行P和V操作。初值常常为1，用于实现进程互斥私有信号量：联系一组并发进程，仅允许此信号量拥有的进程执行P操作，而其他相关进程可在其上施行V操作。初值常常为0或正整数，多用于并发进程同步。,13、信号量操作,semWait(s)，即P(s),将信号量s减去1，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。semSignal(s),即V(s)，将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。,若信号量s为正值，则该值s所代表的实际还可以使用的物理资源数若信号量s为负值，则其绝对值等于登记排列在该信号量s队列之中等待的进程个数,14、掌握用PV操作解决进程间的互斥与同步。生产者-消费者问题读者-写者问题哲学家就餐问题其他问题,练习：用P、V操作表示的生产者与消费者问题算法流程如图所示。图中的s为互斥信号量，表示使用有界缓冲区的信号量，初值为1；n和m为同步信号量，其中n表示有界缓冲区的大小，即可以存放产品的最大数n，初值为k；m表示有界缓冲区中已经存放的产品个数m，初值为0。(1)若缓冲区无界，下图可以简化吗？(2)若可以，如何简化，给出简化后的P、V操作流程图？(3)如果交换生产者的两个P操作，结果如何？,缓冲区无界，表示缓冲区无限大。因此可简化如下：,15、什么是管程？管程有什么特点？如何利用管程实现进程的互斥与同步一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据。特点：共享；安全；互斥,16、管程中的条件变量与P、V操作中信号量的区别?条件变量也是一种信号量，但它并不是P、V操作中所论述纯粹的计数信号量，不能像信号量那样积累供以后使用，仅仅起到维护等待进程队列的作用，当在一个条件变量上不存在等待条件变量的进程时，signal 操作发出的信号丢失，等于做了一次空操作。,17、进程通信。进程之间互相交换信息的工作称为进程通信。通信方式：信号（signal）通信机制;共享存储区(shared memory)通信机制：由信号量及其原语操作控制共享文件(shared file)通信机制：由管道提供消息传递(message passing)通信机制：由信箱和发信/收信原语提供包括寻址方式：直接寻址（direct addressing）和简介寻址（indirect addressing）消息格式：Header,body,18、死锁(Deadlock)：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。死锁产生的必要条件：互斥条件、部分分配(占用并等待)条件、非剥夺条件、循环等待条件解决死锁的方法：死锁预防（prevention）、死锁避免（avoidance）、死锁检测（detection）和恢复。,第三部分 内存（7、8章）,1、内存管理的功能主存空间分配与回收地址转换存储保护与共享主存空间共享,2、概念：逻辑地址（相对地址），Logical Address物理地址（绝对地址），Physical Address重定位(Relocation)静态重定位动态重定位碎片(Fragmentation)：分为内部碎片和外部碎片内部碎片：已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；外部碎片：还没有被分配出去（不属于任何进程），但由于太小而无法进行分配的内存空间。,3、连续存储空间管理（分区管理）的基本思想。给内存中的每一个作业划分一块适当大小的存储区(分区)，连续存储各作业的程序和数据，每个分区只能存储一个作业。该作业也只能在其所在分区中运行。,4、固定分区的基本思想静态地把可分配的主存储器空间分割成若干个连续区域，每个区域的位置固定，但大小可以相同也可以不同，每个分区在任何时刻只装入一道程序执行。,固定分区,5、可变分区（动态分区）,又称变长分区或动态分区模式，是按作业的实际大小来划分分区，分区的大小、位置和数量都可变,实现多个作业对内存的共享，进一步提高内存资源利用率。,最先适应分配算法(first fit)下次适应分配算法(next fit)最优适应分配算法(best fit)最坏适应分配算法(worst fit)快速适应算法(quick fit),6、分页存储管理基本思想将内存分成大小相等位置固定的小区域(块，页框)，将作业的地址空间也分成若干个大小相等的片断(页)，页的大小与块的大小相同，每页装入一块。,作业表,页表,内存,绝对地址的计算公式“块号块长页内相对地址”。,7、分段存储管理基本思想将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。,8、分段与分页有什么不同？页是信息的物理单位；段是信息的逻辑单位。页的大小固定而且由系统确定，硬件实现；段的长度不固定，决定于用户编写的程序。分页的程序地址空间是一维的；分段的程序地址空间是二维的。9、理解如何实现虚拟存储(virtual memory)？作业投入运行时，只将其中当前使用部分先装入主存储器，其余暂时不用的部分先存放在作为主存扩充的辅助存储器中，待用到这些信息时，再由系统自动把它们装入到主存储器中。,10、掌握分页、分段、段页结合的相对地址与绝对地址之间的转换机制。11、掌握分页虚拟存储管理中的页面淘汰算法：OPT、LRU、FIFO、Clock，并计算缺页（Page Fault）中断率。,12、理解反置页表IPTIPT 为内存中的个物理帧建立一个页表并按照帧号排序，该表的每个表项包含正在访问该帧的进程标识、页号及特征位，和哈希链指针等，用来完成内存帧到访问进程的页号，即物理地址到逻辑地址的转换。13、理解快表（转移后备缓冲器,相联存储器）14、理解分页虚拟存储管理中的读取策略和清除策略15、淘汰一个页面时的替换范围（Replacement scope）,16、抖动(Trashing):在内存管理的页面置换算法中，一些块在需要之前刚刚被淘汰，很快又要将其换进主存，使得处理器的大部分时间都用于交换而不是执行指令。,第四部分 调度（9章）,1、调度类型及其含义长程调度(long-term):又称为作业调度或高级调度，决定哪些作业可参与竞争处理器和其他资源,用来控制多道程序系统的并发程度，进程越多则各进程对处理器的使用百分比越小；中程调度(mid-term):决定哪些进程可以参与竞争处理器，用以实现进程的活动状态与挂起态之间的转换，主要是为了提高内存的利用率和系统吞吐量；短程调度(short-term):决定下一个使用处理器的进程。,2、短程调度算法FCFS,非剥夺SPN，非剥夺SRT，剥夺HRRN，非剥夺 Feedback，剥夺,第五部分 设备管理与文件（11、12章）,1、设备管理的作用方便用户使用；提高外围设备的利用率。,2、设备管理的功能分配设备：按设备的不同类型和操作系统选用的算法分配。包括分配相应的通道、设备控制器以及对未分配到的任务或怍业进行排队等；控制和实现真正的输入输出操作。包括通道程序控制、启动设备、及时响应及处理中断讯号等；对输入输出缓冲区进行管理。例如逻辑名的管理，多个缓冲区的分时以及串并行操作，同类多个外部设备的均衡工作，避免“忙的忙”和“闲的闲”；在一些较大系统中实现虚拟设备技术,3、理解设备控制器。I/O 设备通常包括一个机械部件（设备本身）和一个电子部件（设备控制器）。操作系统和设备控制器打交道。,4、I/O控制方式（CPU和设备之间传输数据的控制方式）可编程方式（程序控制方法）耗费大量的CPU时间、无法检测设备错误、只能串行工作。中断方式并行操作的设备数受到中断处理时间的限制。CPU 仍需花较多的时间处理中断。中断次数增多时易导致数据丢失。DMA方式要求CPU执行设备驱动程序启动设备，给出存放数据的内存地址及操作方式和传送长度等。只能传送一个数据块，且必须连续存放。通道方式给CPU发出I/O启动命令后，由通道指令完成启动设备等工作。可传送不连续的数据块。,Programmed I/O,Interrupt-driven I/O,数据传输单位数据块数据传输途径设备内存CPU干预限于数据块传送开始与结束,List the techniques of performing I/O.可编程I/O(询问方式或程序直接控制方式)：处理器发出I/O请求后，进行忙测试，而且参与数据传输，浪费了处理器的宝贵时间。中断方式：处理器发出I/O请求后，转去执行其他任务。I/O控制器缓冲满后，以中断方式通知处理器，在处理器控制下将数据传送至内存。DMA方式：处理器发出I/O请求后，转去执行其他任务，在DMA控制器的控制下，I/O设备直接与主存交换数据而不占用CPU，一块数据传送结束后以中断方式通知处理器。通道方式：是DMA的扩展，进一步减少了处理器的干预，即把对一个数据块的读(或写)为单位的干预减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。,5、I/O设计的目标：提高I/O效率、通用性6、缓冲机制目的：解决快速CPU与满速I/O设备速度匹配问题，减少对处理器的中断频率，放宽处理器对中断的响应时间。技术：单缓冲、双缓冲、循环缓冲、缓冲池,单缓冲,系统对每一整块数据处理时间为max(C,T)+M,双缓冲,系统对每一整块数据处理时间为max(C+M,T),7、设备分配所用数据结构,8、设备独立性：用户使用逻辑设备，由操作系统实现逻辑设备到物理设备的转换。用户编程时不再考虑具体的物理设备。,9、SPOOLING技术：利用一台高速共享设备（磁盘）将一台独占设备模拟成多台可并行操作的虚拟设备，以联机的方式得到脱机的效果。提高了进程访问低速设备速率独占设备成为虚拟设备独占设备成为共享设备,10、磁盘的组成 硬盘是由一组盘片构成的，除了最上面和最下面那个盘片的外面不能存放数据外，其余盘片都可以进行双面存取。磁头：硬盘中最昂贵的部件，直接进行读写操作。有几个盘面就有几个磁头。磁道：当磁盘旋转时，磁头若保持在一个位置上，则每个磁头都会在磁盘表面划出一个圆形轨迹，这些圆形轨迹就叫做磁道。磁盘上的信息是沿着这样的轨道存放的。,扇区(块)：磁盘上的每个磁道被等分为若干个弧段，这些弧段便是磁盘的扇区，每个扇区可以存放512个字节的信息，磁盘驱动器在向磁盘读取和写入数据时，要以扇区为单位。柱面：硬盘通常由重叠的一组盘片构成，每个盘面都被划分为数目相等的磁道，并从外缘的“0”开始编号，具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面。磁盘的柱面数与一个盘面上的磁道数是相等的。由于每个盘面都有自己的磁头，因此，盘面数等于总的磁头数。所谓硬盘的CHS,即Cylinder（柱面）、Head（磁头）、Sector（扇区,文件的信息通常不是记录在同一盘面的各个磁道上，而是记录在同一柱面的不同磁道上，这样可使移动臂的移动次数减少，缩短存取信息的时间。为了访问磁盘上的一个物理记录，必须给出三个参数：柱面号、磁头号、块号(扇区)。,11、寻道时间(Seek Time)、旋转延迟(Rotational delay)12、移臂调度算法,FIFOSSTF最短服务时间优先算法SCAN扫描算法：来回服务，一直到磁道末尾改进算法：LOOK,也称电梯调度：来回服务，一直到最边的请求C-SCAN循环扫描算法：单向服务会计算移臂顺序和移臂总量。,13、磁盘驱动调度算法分为两部分：移臂调度：控制的是寻道操作的先后次序；旋转调度：控制的是哪个扇区先被访问的问题。磁盘工作时，应先完成“移臂调度”，然后再进行“旋转调度”。旋转调度应以尽量减少旋转延迟时间为目标，进行优化。,14、RAID把多个小型廉价的磁盘驱动器合并成一个阵列,加进冗余技术来达到大型昂贵的驱动器所无法达到的性能。理解RAID0-RAID6的不同。15、什么是磁盘高速缓冲（Disk Cache）,16、文件系统所谓文件系统，是指操作系统中涉及到文件管理的那部分软件、管理时用到的数据结构及其被管理的文件。文件系统的功能从用户的角度看，文件系统的主要功能是实现“按名存取”。从系统的角度看，文件系统是对文件存储器的存储空间进行组织、分配、回收，负责文件的存储并对存入的文件实施保护、检索的系统。,文件的逻辑结构：用户概念中的信息组织方式。,堆顺序文件索引文件索引顺序文件直接或散列文件,17、什么是文件的逻辑结构、物理结构？分别都有哪些类型？,文件的物理结构：逻辑文件在物理存储空间中的存放方法和组织关系,顺序文件：连续分配连接文件：链式分配索引文件：索引分配,18、文件的存取方法：顺序存取、直接存取、索引存取19、FCB：文件控制块FCB是系统为管理文件而设置的一个数据结构。FCB是文件存在的标志,它记录了系统管理文件所需要的全部信息20、文件目录（File Directory）：所有FCB的集合。文件目录的作用是：实现文件的“按名存取”。,21、索引节点(i-node)为了提高文件检索速度，把文件名与文件描述信息分开，使文件描述信息单独形成一个称为索引结点的数据结构，简称为i-node。22、文件分配表FAT(File Allocation Table)用来记录文件所在位置的表格，它对于硬盘的使用是非常重要的。,23、空闲空间管理位表（位示图法）空闲链表法索引法（空闲表）空闲块列表,24、什么是记录成组？作用是什么,List the techniques of managing the free disk space.位表（位示图法）：以位示图中的0或1来表示磁盘某个盘快的空闲与否。空闲链表法：把所有空闲分区用链表连接起来，每个空闲分区结点记录该分区的起始盘块、空闲盘块数以及下一个空闲分区的地址。索引法（空闲表）：用一个索引表来记录所有空闲盘块。空闲块列表：每个块关联一个顺序号，所有空闲块的顺序号记录在磁盘中。由于空闲块列表太大，无法保存在主存中，可采用栈或队列，将该表的一部分保存在主存中。减少磁盘I/O次数。,