操作系统(整理自老师上课所讲考点及所讲例题).doc

操作系统-整理自老师上课所讲考点及所讲例题第一章 操作系统引论1、操作系统定义：操作系统是控制和管理计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件，或是程序集合，是用户与计算机之间的接口。2、操作系统主要功能：处理机管理功能，处理机管理应具有进程控制、进程同步、进程通信和调度等功能；存储器管理功能，存储器管理应具有内存分配、内存保护、地址映射和内存扩充等功能；设备管理功能，设备管理应具有缓冲管理、设备分配、设备处理等功能；文件管理功能，文件管理应具有文件存储空间的管理、目录管理、文件的读写管理和保护等功能；操作系统与用户之间的接口,通常可分为用户接口和程序接口两大类。3、操作系统基本特性：并发性、共享性、异步性4、操作系统的体系结构：模块化结构、分层式结构、微内核结构（优点：由于独立于服务器实现各种功能，提高了系统的可扩展性；服务器运行在用户态，增强了系统的可靠性；可移植性；提供了对分布式系统的支持）分层式结构与模块化结构的异同点：都是基于模块和分解的思想，前者各模块间是有序的，各层次层次间是单向调用关系，模块间的组织结构和依赖关系更加清楚可靠。5、操作系统的类型：（1）批处理系统（2）分时系统（特征：多路性、独立性、及时性、交互性；优点：响应快、界面友好，多用户、便于普及，便于资源共享）（3）实时系统（优点：相应时间快）-与分时系统的主要区别：交互能力较弱、系统专用，相应时间更严格、及时，可靠性要求更高。第二章 进程管理1、 程序：（1）程序顺序执行时的特征：顺序性、封闭性、可再现性（2）程序并发执行时的特征：间断性、失去封闭型、不可再现性2、进程；（1）定义：进程是程序在一个数据集合上的运行过程，是资源分配和处理机调度的独立单位。（2）特征：结构特征、动态性、并发性、独立性、异步性（3）进程控制块（PCB）：是进程实体（由程序段、相关数据段和PCB三部分构成）的一部分，是操作系统中最重要的记录型数据结构。作用：是使一个在多道程序环境下不能独立运行的程序（或数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。组成部分：进程标识符（能够惟一地表示一个进程）、处理机状态、进程调度信息、进程控制信息。（4）进程与程序的区别：程序是指令和数据的有序集合，是一个静态的概念，进程有自己的生命周期，是一个动态的概念；进程是一个能独立运行的单位，系统中以进程为单位进行资源分配；引入进程后，进程是系统资源调度的端丽单位；同一个程序运行在不同的系统中属于不同的进程，它可以与其它进程同时运行。（5）三种基本状态：就绪状态（当进程已获得除CPU外的所有必要资源后，只要再获得CPU，便可立即执行）、执行状态（进程已获得CPU，其程序正在运行）、阻塞状态（正在执行的进程由于发生某事件而暂时无法继续执行时，便抛弃处理机而处于暂停状态，亦即进程的执行收到阻塞）执行状态阻塞状态就绪状态I/O完成分到CPU时间片到I/O请求3、 原语（1）定义：是由若干条指令组成的，用于完成一定功能的一个过程。（2）特征：原语是原子操作，即一个操作中的动作要么全做，要么全不做。（3）作用：为了实现进程的通信和控制。4、进程同步（1）临界资源：一次仅允许一个进程使用的资源。（2）临界区：每个进程中访问临界资源的代码段。（3）同步机制应遵循的原则：空闲等待、忙则等待、有限等待、让权等待5、管程机制（1）定义：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块。（2）组成部分：管程的名称；局部于管程内部的共享数据结构说明；对该数据结构进行操作的一组过程；对局部于管程内部的共享数据结构设置初始值的语句。6、进程通信类型共享存储器方式、消息传递方式、管道通信（是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件）7、P82-22、24、25、26题第三章 处理机调度与死锁1、处理机调度的层次：（1）高级调度（2）低级调度（3）中级调度2、死锁（1）定义：是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持的状态下，如果没有外力的作用，它们都将无法再向前推进。（2）产生的原因：竞争资源、进程间的推进顺序非法（3）产生死锁的必要条件：互斥条件、请求和保持条件、不剥夺条件、环路等嗲条件。（4）处理死锁的基本方法：预防死锁、避免死锁、检测死锁、解除死锁（5）死锁的检测与解除-资源分配图3、银行家算法：P115-22题第四章 存储器管理1、 程序的执行：装入编译链接执行2、 连续分配方式（1）定义：是指为一个用户分配一个连续的内存空间。（2）分配方式：单一连续分配、固定分区分配、动态分区分配（首次适应算法、最佳适应算法、最坏适应算法）和动态重定位分区分配3、对换技术（1）对换定义：是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存中，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。（2）对换空间的管理（3）进程的唤出与换入4、基本分页存储管理方式（1）页面：是指分页存储管理将一个进程的逻辑地址空间分成若干个大小相等的片，页号从0页开始。（2）物理块：是指把内存空间分成与页面相同大小的若干个存储块，块号也是从0号开始。（3）地址结构：由页号P和位移量W（页内地址）两部分构成若给定一个逻辑地址空间中的地址为A，页面大小为L，则页号P和页内地址d可按下式求得：P = INT【A / L】d = 【A】MOD L（4）页表：系统为进程建立的一张页号到物理块号的地址映射表。页表最少有一个表项物理块号（5）地址变换机构基本任务：借助于页表实现的从用户地址空间中逻辑地址到内存空间中物理地址的转换。基本的地址转换机构：页表的功能可以由一组专门的寄存器来完成，一个表项用一个寄存器。在系统中只设置一个页表寄存器，在其中存放页表在内存的起始和页表的长度（未执行时存放在PCB中，执行时装入寄存器）。为了获得一条指令需要两次访问内存。具有快表的地址变换机构：快表是为了提高地址变换速度，在地址变换机构中增设的一个具有并行查搜能力的特殊的高速缓冲寄存器，用以存放当前访问的哪些页表项。借助于快表可降低一倍数据的有效访问时间。（6）两级和多级页表对于要求连续的内存空间来存放页表的问题，可利用将页表进行分页，并离散地将各个页面分别存放在不同的物理块中的办法来加以解决，同样也要为离散分配的页表再建立一张页表，即外层页表，在每个页表项中记录了页表页面的物理块号。5、基本分段存储管理方式（1）分段存储引入：方便编程、信息共享、信息保护、动态增长、动态链接（2）分段：分段地址中的逻辑地址由段号和段内地址组成。（3）段表：能从物理内存中找出每个逻辑段所对应的位置，像分页系统那样，在系统中为每个进程建立一张段映射表（由段号、断长、基址构成）。（4）地址变换机构：设置了段表寄存器，用于存放段表始址和段表长度。6、分页与分段的主要区别（1）页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。段则是信息的逻辑单位，分段的目的是为了能更好地满足用户的需要。（2）页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现。段的大小不固定，决定于用户所编写的程序。（3）分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址。分段的作业地址空间是二维的，程序员标识一个地址需要给出段名和段内地址。7、段页式存储管理方式（1）基本原理：其地址结构由段号、段内页号及页内地址三部分所组成。（2）地址变换过程：为了获得一条指令需要三次访问内存。8、虚拟存储器（1）定义：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。（2）特征：多次性（是指一个作业被分成多次调入内存运行）、对换性（是指允许作业在运行过程中进行换入换出）、虚拟性（能够从逻辑上扩充内存容量）。9、请求分页存储管理方式（1）页表机制：在页表中增加若干项，供程序换进、换出时参考。请求分页系统中的每个页表项：页号、物理块号、状态位、访问字段、修改位、外存地址。（2）缺页中断机构：在指令执行期间产生和处理中断信号；一条指令在执行期间，可能产生多次缺页中断。（3）调页策略：调入页面的时机（预调页策略，进程首次调入时；请求调页策略，运行中时），确定从何处调入页面（对换区、文件区），页面调入过程（P149）10、页面置换算法：最佳置换（Optimal）、先进先出（FIFO）、最近最久未使用（LRU）Clock置换（简单的Clock、改进的Clock）第五章 设备管理1、 分类问题（1）I/O设备：使用特性（存储设备、输入输出）、传输速率（低、中、高）、信息交换单位（块设备、字符设备）、共享属性（独占、共享、虚拟）（2）设备与控制器间接口：通常，设备不是直接与CPU进行通信，而是与设备控制器通信。该接口三种类型信号：数据、控制、状态（3）设备控制器：主要职责是控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换。由设备控制器与处理机的接口、设备控制器与设备的接口和I/O逻辑三部分组成。2、I/O通道（1）定义：是一种特殊的处理机，具有执行I/O指令的能力，并通过执行I/O程序来控制I/O操作。（2）引入目的：为了建立独立的I/O操作，不仅是数据的传送能独立于CPU，而且也希望有关对I/O操作的组织、管理及其结束处理尽量独立，以保证CPU有更多的时间去进行数据处理。（3）为什么通道是特殊的处理机：一是其指令类型单一，由于通道硬件比较简单，所能执行的命令主要局限于与I/O操作有关的指令；二是通道没有自己的内存，通道与CPU共享内存。3、直接存储器访问（DMA）（1）特点：数据传输的基本单位是数据块，所传送的数据是从设备直接送入内存的，仅在传送数据块结束时才需CPU干预，整块数据的传送是在控制器的控制下完成的。（2）DMA控制器组成：主机与DMA控制器的接口、DMA控制器与块设备的接口、I/O控制逻辑。（2）DMA控制器工作过程：P1704、Spooling技术：P1915、磁盘调度：先来先服务（FCFS）、最短寻道时间优先（SSTF）、扫描（SCAN）第六章 文件管理1、 分类问题（1）文件系统：可把数据组成分为数据项、记录（一组相关数据项的集合）、文件（由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种）三级。（2）文件类型：用途（系统文件、用户文件、库文件）、数据形式（源文件、目标文件、可执行文件）、存取控制（只执行、只读、读写）、组织形式和处理方式（普通、目录、特殊）。（3）文件控制块（FCB）：包含基本信息、存储控制信息和使用信息三类。2、外存分配方式（1）连续分配方式（2）链接分配：隐式分配、显式分配（P216图6-9）（3）FAT技术（图6-10）（4）混合索引分配方式（直接地址、一次简介地址、多次间接地址）3、目录结构（1）单级目录结构（一张目录表）（2）两级目录（主文件目录MFD、用户目录）4、文件存储空间的管理：位示图（P232）、成组链接法（P233）5、文件共享与文件保护（基于索引结点或符号链的共享方式）第七章 操作系统接口（1）命令解释程序接口功能等待用户输入命令；接收并识别命令；执行相应的命令处理程序、处理结果输出到终端显示。（2）系统调用与一般调用的不同运行在不同的系统状态：调用程序用户态；被调用程序系统态通过软中断机制进入：调用过程软中断被调用过程返回问题：被调用过程执行完毕，返回后调用过程需根据算法重新调度。嵌套调用：可嵌套调用，但深度有限。（3）系统调用的参数传递方式（4）系统调用的过程算法：【例1】生产者-消费者问题在多道程序环境下，进程同步是一个十分重要又令人感兴趣的问题，而生产者-消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者-消费者问题，深入地分析和透彻地理解这个例子，对于全面解决操作系统内的同步、互斥问题将有很大帮助。（1）一个生产者，一个消费者，公用一个缓冲区。定义两个同步信号量：empty表示缓冲区是否为空，初值为1。full表示缓冲区中是否为满，初值为0。（2）一个生产者，一个消费者，公用n个环形缓冲区。定义两个同步信号量：empty表示缓冲区是否为空，初值为n。full表示缓冲区中是否为满，初值为0。 设缓冲区的编号为1n，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。（3）一组生产者，一组消费者，公用n个环形缓冲区 在这个问题中，不仅生产者与消费者之间要同步，而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。定义四个信号量：empty表示缓冲区是否为空，初值为n。full表示缓冲区中是否为满，初值为0。mutex1生产者之间的互斥信号量，初值为1。mutex2消费者之间的互斥信号量，初值为1。 设缓冲区的编号为1n，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。【例2】吃水果问题n问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出 四人之间的同步关系，并用PV操作实现四人正确活动的程序。解1：盘子为互斥资源，可以放两个水果，因此设empty初值为2；爸爸放苹果前先看看有无空间，若有，则放入苹果，向女儿发信号V（apple）；妈妈放橘子前先看看盘子有无空间，若有，放入橘子后向儿子发信号V（orange）；女儿先看看有无苹果，若有，则取走苹果后将盘子置空V（empty）；儿子先看看有没有橘子，若有，则取走橘子后将盘子置空。该题是生产者/消费者的变形，有两对生产者和消费者，生产者需指明是给哪个消费者的产品，但消费者取走产品后无须特别通知某个生产者，因为空出的缓冲区可由两个生产者随意争夺。 设信号量mutex初值为1，控制对盘子的互斥访问；apple表示盘子中的苹果数，orange表示盘中橘子个数，初值为0。 爸爸、妈妈、儿子、女儿进程如下：爸爸 妈妈 女儿 儿子 L1：P（empty） L2：P（empty） L3：P（apple） L4：P（orange） P（mutex） P（mutex） P（mutex） P（mutex） 放苹果 放橘子 取苹果 取橘子 V（mutex） V（mutex） V（mutex） V（mutex） V（apple） V（orange） V（empty） V（empty） GOTO L1 GOTO L2 GOTO L3 GOTO L4 解2：四人之间的关系：1爸爸，妈妈要互斥使用盘子，所以两者之间是互斥关系；2爸爸放的苹果，女儿吃，所以两者是同步关系；3妈妈放的桔子，儿子吃，所以两者也是同步关系。S表示盘子是否为空，初始值为1（为空）Sp表示放有苹果的盘子，初始值为0So表示放有桔子的盘子，初始值为0semaphore s,sp,so=1,0,0;father:have an apple;wait(s);put an apple;signal(sp); mother:have an orange;wait(s); put an orange; signal(so); son:wait(sp); get an orange; signal(s); eat an orange;daughter:wait(sp); get an apple; signal(s); eat an apple;【例2】26.在银行家算法中，若出现下述的资源分配情况： Process Allocation Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 6 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6试问： 该状态是否安全？ 若进程P2提出请求Request(1,2,2)之后，系统能否将资源分配给它？参考P110【例3】页面置换算法（置换图、缺页率）参考P150【例4】在基本分页系统中欧中（假定一次访问内存的时间为a）（1）一条指令的执行需要多长时间？（2）若引入块表，命中率为95%，则一条指令执行时间是多少？解：（1）a + 2a + a = 4a（取指令（a）取数据（2a）运行指令（a）（2）a + 95%a + (1-95%)2a + a = 3.05a【例5】在基本分页系统中，已知页面大小为8kb，某程序逻辑空间由4页钩成，页表如下：页号物理块号0 91 62 33 0若物理空间大小为256M，试将下列逻辑地址转换为物理地址（1）19287（2）9EFB HB（3）7ABF HB解：（1）页号=INT【19287 / 8kb】=2页内地址 = 19287%8kb = 2903页号为2对应的物理块号为3物理地址 = 3*8kb + 2903（2）页号为4，发生越界中断（3）0111 1010 1011 11118kb = 2的13次方字节页号为011即十进制3 ，对应物理块号为0物理地址为0001 1010 1011 1111【例6】在基本分页系统中，已知用户作业逻辑空间大小由8页构成，页面大小为4kb，若物理空间大小为512MB，页表由基本页表项构成，求（1）页表大小？（2）若逻辑空间减半，页表如何变化？（3）若物理空间减半，页表如何变化？解：（1）页表大小 = 表项数 * 表项大小（基本页表项只有一项-物理块号）物理块数 = 512 / 4k = 2的17次方（块） = 2的17次方（页表项）物理块号用17位二进制信息表示页表大小 = 8 * 17 / 8 = 17 B（2）页表大小 = 4 * 17 / 8 = 8.5B（3）页表大小 = 8 * 16 / 8 = 16B【例7】已知有4个进程，其到达与服务时间如下：进程名到达时间服务时间A04B25C31D52计算下列调度算法