操作系统复习要点.doc

操作系统复习要点1、 概述部分操作系统概念、特征、设计目标2、 进程管理部分进程概念、组成、进程状态迁移图及迁移原因，进程间的关系、临机区概念，实现互斥的方法、P/V操作，引入线程的目的、线程与进程间的关系、死锁特征、资源分配图判定死锁的方法，常用调度算法。 3、 内存管理部分作业装入内存的方式，分区内存管理机制中的分区分配方法、特点、快表、分页管理机制原理、实现请求调页的内存管理机制的关键技术4、 文件管理部分文件系统设计目标、管理磁盘空闲空间的方法、目录结构、FCB等5、 外设管理部分I/0软件组成，设备驱动程序概念、四种I/O方式比较及其工作流程，设备管理目标。复习题目概述部分1、 什么是操作系统？操作系统设计目标是什么？由哪些部分组成？各个部分主要解决什么问题？操作系统(operating system)是用户和计算机之间的界面. 一方面操作系统管理着所有计算机系统资源, 另一方面操作系统为用户提供了一个抽象概念上的计算机. 在操作系统的帮助下, 用户使用计算机时, 避免了对计算机系统硬件的直接操作. 对计算机系统而言, 操作系统是对所有系统资源进行管理的程序的集合; 对用户而言, 操作系统提供了对系统资源进行有效利用的简单抽象的方法设计目标User goals operating system should be convenient to use, easy to learn, reliable, safe, and fast.System goals operating system should be easy to design, implement, and maintain, as well as flexible, reliable, error-free, and efficient.组成Process Management Main Memory ManagementSecondary-Storage ManagementI/O System ManagementFile ManagementProtection SystemNetworkingCommand-Interpreter System各部分主要解决问题见课本 ppt2、 操作系统内核技术的发展？什么是微内核？并发和并行的区别？发展Batch Systems（作业批处理）Time-Sharing Systems（分时系统）Personal-Computer Systems（PC系统）Parallel Systems （并行系统）Distributed Systems （分布系统）Real -Time Systems （实时系统）一般来说OS的核心有以下几种: 1.单块核心(MONOLITHIC KERNEL)将所有OS功能放入核心.UNIX就是这种结构.2.环状核心分为核心,任务,用户几级,如MINIX.LINUX 也有这种特征,大家也许注意到,LINUX增加某些种类的服务时不像UNIX,必须重新启动.这就是这种结构比UNIX先进的地方.3.无内核:不区分核心和用户程序的分别,这样省去了状态切换的时间,这种模式适合WEB服务器.4.微内核 微内核将许多OS服务放入分离的进程,如文件系统,设备驱动程序,而进程通过消息传递调用OS服务.微内核结构必然是多线程的,第一代微内核,在核心提供了较多的服务,因此被称为胖微内核,它的典型代表是MACH,它既是GNU HURD也是APPLE SERVER OS 的核心,可以说,蒸蒸日上.第二代为内核只提供最基本的OS服务,典型的OS是QNX,QNX在理论界很有名,被认为是一种先进的OS并发与并行是两个既相似而又不相同的概念：并发性，又称共行性，是指能处理多个同时性活动的能力；并行是指同时发生的两个并发事件，具有并发的含义，而并发则不一定并行，也亦是说并发事件之间不一定要同一时刻发生进程管理部分：1、 为什么要引入进程？为什么要引入线程？从调度性、并发性、拥有的资源以及系统开销等方面，区别和比较进程和线程？进程两个基本特性：资源分配的独立单位、调度的基本单位引入思想：将进程资源分配和调度分开，引入线程。启动一个新进程必须分配独立地址空间，建立众多的数据表来维护它的代码段、堆栈段，这是一种很“昂贵”的多任务工作方式 。运行于一个进程中的多个线程，彼此之间使用相同的地址空间，共享大部分数据，启动一个线程所花费的空间远远小于启动一个进程所花费的空间。线程间彼此切换所需的时间也远远小于进程间切换所需要的时间时间。创建一个新线程花费时间少（结束亦如此）、两个线程的切换花费时间少同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核适合多处理机系统2、 进程状态迁移图，引起状态迁移的原因和事件？三 五 七 状态 迁移 图无法显示 请看 课本 ppt引起状态迁移的原因和事件正在运行的进程运行完毕；运行中的进程要求I/O；执行某种原语操作；一个比正在运行进程优先数更高的进程申请运行（可剥夺调度方式）；分配给运行进程的时间片已经用完;主动放弃3、 进程组成？PCB的含义？进程由以下几部分组成（1）一个可执行程序，包括初始代码和数据（2）一个独立的用户空间（3）系统资源 包括I/O设备、文件等（4）至少一个执行栈区，包括运行现场信息。PCB ：进程控制块：是进程存在的唯一标志，它是记录进程生存期内状态变化的重要数据结构。包括如下数据：Information associated with each process.Process stateProgram counterCPU registersCPU scheduling informationMemory-management informationAccounting informationI/O status information4、 进程之间的关系？什么是临界区？如何实现临界区的互斥访问？进程之间的关系：同步 互斥 。竞争 协作 ？。在进程中涉及到临界资源的程序段叫临界区如何实现临界区的互斥访问：软件方法：先修改、后检查、后修改者等待turn=j;描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后检查对方flag，如果不在临界区则自己进入空闲则入否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入先到先入，后到等待flagi = true; turn = j;while( flagj & turn =j)；critical sectionflagi=false;remainder section硬件方法：Test-and-Set指令 该指令读出标志后设置为为TRUE boolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old;while( TS(&lock) );critical sectionlock=false;remainder section5、 P/V操作的含义？信号量的含义？如何定义信号量的初值？如何利用P/V操作实现多个进程之间的同步和互斥？如利用其实现单缓冲区的读写问题？如何实现生产者消费者等问题？P/V操作 是定义在信号量上的两个操作，是一种卓有成效的进程同步机制，执行P操作意味着申请分配一个单位的资源，执行V操作意味着申释放一个单位的资源。信号量表示资源的实体，是一个与队列有关的整型变量。初值公用信号量用来实现进程间的互斥，初值为1，允许它所联系的一组进程对它执行P/V操作私用信号量用来实现进程间的同步，初值为0或者某个正整数，仅允许拥有它的进程对其执行P/V操作。信号量取值为非负值表示当前空闲资源数，若为负值其绝对值表示当前等待临界区的进程数实现互斥为临界资源设置一个互斥信号量mutex，初值为1；在每个进程中，将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语： 遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）P(mutex)CSV(mutex)RS实现同步前趋关系 并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为每个前趋关系设置一个互斥信号量S12，其初值为0P1 P2C1 P(s12) V(s12) C2 实现单缓冲区的读写问题说明：Mutes、w初值为1，readcount初值为0Readcount用来记录当前有多少个读者在访问数据Mutex用来保证读者之间互斥地修改readcount。W是读者和写着公用的互斥变量，用来互斥读写同时进行1读者优先读者： while (true) P(mutex); readcount +; if (readcount=1) P (w); V(mutex); 读 P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;写者： while (true) P(w); 写 V(w); ;2写者优先说明Readcount用来记录当前有多少个读者在访问数据W是读者和写着公用的互斥变量，用来互斥读写或者写写同时进行w初值为1，readcount初值为n读者： while (true) P(w); P (readcount); V(w); 读 V(readcount); ;写者：while (true) P(w); for i:=1 to n do P(readcount); 写 for i:=1 to n do V(readcount); V(w); ;/code实现生产者消费者等问题问题描述: 若干进程通过有限的共享缓冲区交换数据。其中，生产者进程不断写入，而消费者进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。解决:full是“满”数目，初值为0，empty是“空”数目，初值为N。实际上，full和empty是同一个含义：full + empty = Nmutex用于访问缓冲区时的互斥，初值是1每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥 否则可能死锁实现Producerp(empty);p(mutex);one unit-buffer;v(mutex);v(full);Consumerp(full);p(mutex);one unit W；begin P（S1）；过桥；V（S2）；end；process W-E；begin P（S2）；过桥；V（S1）；end；内存管理部分1、 程序装入内存有几种方式？什么是可重定位的装入技术？常用程序装入技术：绝对装入技术、可重定位装入技术可重定位装入技术：可执行文件中，列出各个需要重定位的地址单元和相对地址值，装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。2、 在动态分区分配中，有那些分区分配算法？各个是如何实现的？最先适配算法循环最先适配算法最佳适配算法最坏适配算法如何实现请看张老师ppt3、 什么是虚拟存储器？其特征是什么？虚拟存储器容量是如何确定的？虚拟存储器是建立在主存 - 辅存物理结构基础之上，由附加硬件装置及操作系统存储管理软件组成的一种存储体系（原谅我吧，这段是我google的= =）虚拟存储特征不连续性物理内存分配的不连续，虚拟地址空间使用的不连续部分交换与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的大空间通过物理内存和快速外存相结合，提供大范围的虚拟地址空间总容量不超过物理内存和外存交换区容量虚拟存储器的最大容量是由计算机的地址结构确定的，其实际容量是由内存和硬盘交换区容量之和确定的。4、 请求分页技术中，图示windows下的两级分页机制？见张老师ppt5、 请求分页机制中，页面置换算法有那些，具体实施页面置换过程？最佳算法（OPT）最近最久未使用算法(LRU)最不常用算法(LFU)轮转算法(clock)先进先出算法(FIFO)具体实现见张老师ppt6、 在交换技术中，进程置换策略是什么？这个还没找到= =7、 什么是快表？其中内容是什么样子的？什么是页表？其结构是如何？联想寄存器器快表为缩短查找时间，可以将页表从内存装入到关联存储器(TLB)，按内容查找，即逻辑页号物理页号系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系，页表放在内存，属于进程的现场信息。页表包含每页所在物理内存的基地址内存部分先发到这，还请大家指正发现这一块理解的东西特别多，如果就看提纲好像没有什么意义。还是要具体的理解那些例子。文件管理部分1、什么是文件？是一组带标识的、在逻辑上有完整意义的信息项的序列。标识是文件名：信息项是构成文件内容的基本单位长度是单个字节或多个字节文件内容由文件建立者和使用者解释2、什么是文件系统？是操作系统中统一管理信息资源的一种软件。3、 文件系统设计目标是什么？管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。4、什么是文件的逻辑结构、物理结构？逻辑结构是从用户角度研究文件的组织形式，分为：无结构文件：构成文件的基本单位是字符，文件是有逻辑意义的、无结构的一串字符的集合有结构文件：文件是由若干个记录组成，每个记录有一个键，可按键进行查找物理结构是从系统角度来看文件，从文件在物理介质上的存放方式来研究文件。5、文件物理结构有哪些？分为：连续结构（顺序）文件信息存放在若干连续的物理块中链接结构文件信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。索引结构文件信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构-索引表，并将这些块的块号存放在一个索引表中6、UNIX系统采用的综合索引方式是如何实现的？有何优点？UNIX文件系统采用多级索引结构(综合模式)完成的。7、磁盘空闲空间的管理方法？空闲块表所有空闲块记录在一个表中空闲块链表把所有空闲块链成一个链8、图示成组链接法？并说明其优点。把n个空闲块的地址存放在第一个空闲块中，这些块中的前n-1个确实为空。而最后一块包含另外n个空闲块的地址，如此继续。优点是大量的空闲块的地址可以很快的被找到。9、什么是目录文件的组成？把所有FCB组织在一起，就构成了文件目录，即文件控制块的有序集合10、采用目标文件的目的？ 提高查找文件的效率 使文件的命名更加方便 是文件分组更加容易11、目录的改进方法及其改进性能比较？采用目录项分解法，把FCB分成两部分。改进的目的是加快文件检索。性能比较在幻灯片上有。12、常用的目录结构？一级目录，简单，易实现。有命名问题和分组问题二级目录，有路径，多个用户可以有同名文件，查询效率高。没有分组能力，有系统开销树型目录（多级目录），层次结构清晰，便于管理和保护，有利于文件分类，解决重名问题，提高文件检索速度，能进行存取权限的控制。查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度其它方法，哈希表，B+树13、RAID的概念？关键技术是什么？Redundant Array of Independent (or Inexpensive) Disks, a category of disk drives that employ two or more drives in combination for fault tolerance and performance.。技术关键是并行交叉存取14、文件操作中,open函数实现过程及其完成的内容？执行过程：1) 根据文件路径名查目录，找到FCB主部；2) 根据打开方式、共享说明和用户身份检查访问合法性；3) 根据文件号查系统打开文件表，看文件是否已被打开；是共享计数加1，否则将外存中的FCB主部等信息填入系统打开文件表空表项，共享计数置为1；4) 在用户打开文件表中取一空表项，填写打开方式等，并指向系统打开文件表对应表项。5) 返回信息fd：文件描述符，是一个非负整数，用于以后读写文件。15、 影响磁盘访问的因素有那些？列举几种磁盘调度算法。影响因素