操作系统复习要点

1、操作系统复习要点1、 概述部分操作系统概念、特征、设计目标2、 进程管理部分进程概念、组成、进程状态迁移图及迁移原因，进程间的关系、临机区概念，实现互斥的方法、P/V 操作，引入线程的目的、线程与进程间的关系、死锁特征、资源分配图判定死锁的方法，常用调度算法。3、 内存管理部分作业装入内存的方式，分区内存管理机制中的分区分配方法、特点、快表、分页管理机制原理、实现请求调页的内存管理机制的关键技术4、 文件管理部分文件系统设计目标、管理磁盘空闲空间的方法、目录结构、FCB 等5、 外设管理部分I/0 软件组成，设备驱动程序概念、四种I/O 方式比较及其工作流程，设备管理目标。复习题目概述部分1、

2、 什么是操作系统？操作系统设计目标是什么？由哪些部分组成？各个部分主要解决什么问题？操作系统(operating system)是用户和计算机之间的界面.一方面操作系统管理着所有计算机系统资源, 另一方面操作系统为用户提供了一个抽象概念上的计算机. 在操作系统的帮助下用户使用计算机时, 避免了对计算机系统硬件的直接操作.对计算机系统而言, 操作系统是对所有系统资源进行管理的程序的集合; 对用户而言, 操作系统提供了对系统资源进行有效利用的简单抽象的方法设计目标User goalsoperating system should be convenient to use, easy to lear

3、n, reliable, safe, and fast.System goalsoperating system should be easy to design, implement, and maintain, as well as flexible, reliable, error-free, and efficient.组成Process ManagementMain Memory ManagementSecondary-Storage ManagementI/O System ManagementFile ManagementProtection SystemNetworkingCo

4、mmand-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 .环状

5、核心分为核心,任务,用户几级,如 MINIX.LINUX 也有这种特征,大家也许注意到,LINUX 增加某些种类的服务时不像UNIX, 必须重新启动.这就是这种结构比UNIX 先进的地方.3 .无内核:不区分核心和用户程序的分别,这样省去了状态切换的时间,这种模式适合WEB 服务器 .4 .微内核微内核将许多OS 服务放入分离的进程,如文件系统,设备驱动程序,而进程通过消息传递调用OS 服务 .微内核结构必然是多线程的,第一代微内核,在核心提供了较多的服务,因此被称为'胖微内核',它的典型代表是MACH, 它既是 GNU HURD 也是 APPLE SERVER OS 的核心,

6、可以说 ,蒸蒸日上.第二代为内核只提供最基本的OS 服务,典型的OS 是 QNX,QNX 在理论界很有名 ,被认为是一种先进的OS并发与并行是两个既相似而又不相同的概念：并发性，又称共行性，是指能处理多个同时性活动的能力；并行是指同时发生的两个并发事件，具有并发的含义，而并发则不一定并行，也亦是说并发事件之间不一定要同一时刻发生 进程管理部分：1、 为什么要引入进程？为什么要引入线程？从调度性、并发性、拥有的资源以及系统开销等方面，区别和比较进程和线程？进程两个基本特性：资源分配的独立单位、调度的基本单位引入思想：将进程资源分配和调度分开，引入线程。启动一个新进程必须分配独立地址空间，建立众多

7、的数据表来维护它的代码段、堆栈段，这是一种很“昂贵”的多任务工作方式 。运行于一个进程中的多个线程，彼此之间使用相同的地址空间，共享大部分数据，启动一个线程所花费的空间远远小于启动一个进程所花费的空间。线程间彼此切换所需的时间也远远小于进程间切换所需要的时间时间。创建一个新线程花费时间少（结束亦如此）、两个线程的切换花费时间少同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核适合多处理机系统2、 进程状态迁移图，引起状态迁移的原因和事件？三 五 七 状态 迁移 图无法显示请看 课本 ppt引起状态迁移的原因和事件正在运行的进程运行完毕；运行中的进程要求I/O;执行某种原语操作；一

8、个比正在运行进程优先数更高的进程申请运行（可剥夺调度方式）； 分配给运行进程的时间片已经用完;主动放弃3、 进程组成？PCB 的含义？进程由以下几部分组成（ 1 ）一个可执行程序，包括初始代码和数据（ 2）一个独立的用户空间（ 3）系统资源包括 I/O 设备、文件等（ 4）至少一个执行栈区，包括运行现场信息。PCB ：进程控制块：是进程存在的唯一标志，它是记录进程生存期内状态变化的重要数据结构。包括如下数据：Information associated with each process.Process stateProgram counterCPU registersCPU scheduli

9、ng informationMemory-management informationAccounting informationI/O status information4、 进程之间的关系？什么是临界区？如何实现临界区的互斥访问？进程之间的关系：同步互斥 。 。竞争 协作 ？。在进程中涉及到临界资源的程序段叫临界区如何实现临界区的互斥访问：软件方法：先修改、后检查、后修改者等待turn=j; 描述可进入的进程（同时修改标志时）在进入区先修改后检查，并检查并发修改的先后检查又方flag ,如果不在临界区则自己进入空闲则入否则再检查turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进

10、程进入-先到 先入，后到等待flagi = true; turn = j;while（ flagj && turn =j）；critical sectionflagi=false;remainder section硬件方法：Test-and-Set 指令该指令读出标志后设置为为TRUEboolean TS（boolean *lock） boolean old;old = *lock; *lock = TRUE;return old;while（ TS（&lock） ）;critical sectionlock=false;remainder section5、 P/V

11、操作的含义？信号量的含义？如何定义信号量的初值？如何利用P/V 操作实现多个进程之间的同步和互斥？如利用其实现单缓冲区的读写问题？如何实现生产者消费者等问题？P/V 操作是定义在信号量上的两个操作，是一种卓有成效的进程同步机制，执行P 操作意味着申请分配一个单位的资源，执行V 操作意味着申释放一个单位的资源。信号量表示资源的实体，是一个与队列有关的整型变量。初值公用信号量用来实现进程间的互斥，初值为 1 ， 允许它所联系的一组进程对它执行P/V 操作私用信号量用来实现进程间的同步，初值为 0 或者某个正整数，仅允许拥有它的进程对其执行 P/V 操作。信号量取值为非负值表示当前空闲资源数，若为负

12、值其绝对值表示当前等待临界区的进程数实现互斥为临界资源设置一个互斥信号量mutex,初值为1;在每个进程中，将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P 和 V 原语：遗漏 P 原语则不能保证互斥访问，遗漏V 原语则不能在使用临界资源之后将其释放(给其他等待的进程)P(mutex)CSV(mutex)RS实现同步前趋关系并发执行的进程 P1和P2中，分别有代码 C1和C2,要求C1在C2开始前完成；为每个前趋关系设置一个互斥信号量S12,其初值为0P1P2C1P(s12)V(s12)C2实现单缓冲区的读写问题说明：Mutes、 w 初值为 1 ， readcount

13、 初值为 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 是读者和写着公用的互斥变量，用来互斥读写或者写写

14、同时进行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是

15、"满”数目，初值为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 <- buffer;v(mutex);v(empty);6、 高级通信方式中，理解send()和receive ()的

16、工作过程。发送进程需要发送消息时，执行send 原语，产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy 到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾。发送进程返回到用户态继续执行接受进程在以后某个时刻，接收进程执行到receive 接收原语时，也产生自愿性中断进入操作系统。操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy 到接收进程空间，之后收回缓冲区。完成了消息的接收，接收进程返回到用户态继续进行7、 有哪些常用调度算法？引起进程调度的事件有那些？多级反馈队列调度算法的分析？常用调度算法First-Come,

17、 First-Served (FCFS) SchedulingShortest-Job-First (SJF) SchedulingShortest-Remaining-Time-First (SRTPriority SchedulingRound Robin (RR)Multilevel Queue引起进程调度的事件Switches from running to waiting state.Switches from running to ready state.Switches from waiting to ready.Terminates.多级反馈队列调度算法，是一种考虑较全面灵活的

18、调度算法，它不必事先知道各作业所需执行时间，且它可以满足各种类型进程的需要，因此它是目前公认较好的一种进程调度算法。(1)为提高系统吞吐量和降低作业平均周转时间而照顾短作业。(2)为了得到较好的输入 /输出设备的利用效率和对交互用户的及时响应，而照顾输入/输出型作业。(3)在作业运行过程中，按作业运行情况能动态地考虑作业的性质是输入/输出型作业，还是计算型作业。调度算法的实施过程在采用多级反馈队列调度算法的系统中，调度算法的具体实施过程如下：(1)设置多级就绪队列。系统中有多个就绪进程队列，每个就绪队列对应一个调度级别，各级具有不同的优先级。第 1 级队列的优先级最高，第 2 级队列优先级次之

19、，其余级队列的优先级随级增大而降低。(2)各级就绪队列具有不同大小的时间片。优先级最高的第1级队列中进程的时间片最小，随着队列的级数增大其中进程的优先级降低，但时间片却增大。(3) 一个新进程在系统就绪队列中排队的规则。当一个新进程进入内存后，首先被放到第 1 级就绪队列末尾。该队列中的进程按FCFS 原则分配处理机，并运行相应于该队列的一个时间片。若进程在这个时间片中完成其全部工作，该进程离开就绪队列撤离系统；若进程运行完一个时间片后仍未完成，则该进程被强迫放弃处理机，放入下一级就绪队列的末尾。(4)按队列优先级高到低进行进程调度。每次进程调度都是从第 1级就绪队列开始调度，仅当第 1 级队

20、列空时，调度程序才调度第2 级队列中的进程；依此类推。第 n 级队列中的进程采用时间片轮转方法进行调度。(5)一个进程进入较高优先级队列时可能要重新调度。2.调度算法的性能多级反馈队列调度算法具有较好的性能，能照顾到各种用户的需要。能照顾到短型作业用户的要求终端型用户提交的作业，大都属于交互型作业，因而作业通常较短小。系统只要能使这些作业的进程在第1 级队列所规定的一个时间片内完成，就可使终端型作业用户都感到满意。能照顾到短批处理型作业用户的要求对于极短的批处理型作业，如果仅在第1 级队列中执行一个时间片即可完成，就可获得与终端型作业一样的响应时间。能照顾到长批处理型作业用户的要求对于长作业，

21、它们对应的进程将依次进入第1, 2，直到第n级队列中经调度而得到运行， 最后在第n 级队列中按轮转方式被调度运行。长作业一旦得到运行，它所获得的时间片就比较大。能照顾到输入输出型作业用户的要求照顾输入输出型作业是调度算法的宗旨，其目的是为了充分利用外部设备，以及对终端交互用户及时予以响应，通常输入输出型进程被唤醒可进入最高优先级队列，从而能很快得到处理机。8、 引起死锁的四个特征是什么？如何针对这是个特征克服死锁？资源分配图的方法判定死锁？四个特征Mutual exclusiononly one process at a time can use a resource.Hold and wai

22、ta process holding at least one resource is waiting to acquire additional resources held by other processes.No preemptiona resource can be released only voluntarily by the process holding it, after that process has completed its task.Circular waitthere exists a set P0, P1,，P0 of waiting processes su

23、ch that P0 is waiting for a resource thatis held by P1, P1 is waiting for a resource that is held by P2,-1 is waiting for -a ,resource thatis held by Pn, and P0 is waiting for a resource that is held by P0.Deadlock can arise if four conditions hold simultaneouslyDeadlock PreventionMutual Exclusionno

24、t required for sharable resources; must hold for nonsharable resources.Circular Waitimpose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.Hold and Waitmust guarantee that whenever a process requests a resource, it does n

25、ot hold any other resources.Require process to request and be allocated all its resources before it begins execution, or allowprocess to request resources only when the process has none.Low resource utilization; starvation possibleNo PreemptionIf a process that is holding some resources requests ano

26、ther resource that cannot be immediately allocated to it, then all resources currently being held are released.Preempted resources are added to the list of resources for which the process is waiting.Process will be restarted only when it can regain its old resources, as well as the new ones that it

27、is requesting.资源分配图的方法判定死锁If graph coniaiiis no cycles no deadlock.If graph contains a cycleif only one instance per resource type, then deadlock.if several instances per resource type, possibility of deadlock.后续章节如有需要下回分解pv操作我猜肯定会考添一个 上课讲过的 帮助回忆独木桥问题2. 一条小河上有一座独木桥（如图），规定每次只允许一个人过桥。现河东和河西都有相等的人数在等待过

28、桥，为了使两边的人都有同样的过桥机会，规定某边的一个人过桥后要让另一边的一个人过桥，即两边的人交替过桥。如果把每个过桥者看做一个进程，为保证安全， 可用PV操作来管理。（ 1 ）写出应定义的信号量及其初值。（ 2）假定开始时让河东的一个人先过桥，然后交替过桥。现进程的程序如下。请在空白处填上适当的PV 操作，达到上述管理要求。解答 :独木桥是各进程的共享资源，由于每次只允许一个人过桥，且河两边的人必须交替过桥，因而相互间要互通消息。在本题中应区分“允许河东的人过桥”和“允许河西的人过桥”两个不同的消息。所以，应定义两个信号量SI 和 SZ 分别与两个消息对应。若开始时让河东的一个人先过桥，则信

29、号量S1的初值应为1,而S2的初值应为0。任何一方的人欲过桥前应调用 P 操作来测试允许过桥的消息是否到达，只有在消息到达后才可过桥，过桥后应调用V操作把允许另一方的一个人过桥的消息发送出去。题解（ 1）定义两个信号量S1 和 S2， S1： =1， S2： =0。（ 2）假定开始时让河东的一个人先过桥，则用PV 操作管理时的程序应如下：process E->W；beginP（ S1） ；过桥；V（ S2） ；end；process W->E； beginP（ S2） ；过桥；V（ S1） ；end；内存管理部分1、 程序装入内存有几种方式？什么是可重定位的装入技术？常用程序装入技

30、术：绝对装入技术、可重定位装入技术可重定位装入技术：可执行文件中，列出各个需要重定位的地址单元和相对地址值，装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。2、 在动态分区分配中，有那些分区分配算法？各个是如何实现的？最先适配算法循环最先适配算法最佳适配算法最坏适配算法如何实现请看张老师ppt3、 什么是虚拟存储器？其特征是什么？虚拟存储器容量是如何确定的？虚拟存储器是建立在主存- 辅存物理结构基础之上，由附加硬件装置及操作系统存储管理软件组成的一种存储体系(原谅我吧，这段是我google 的 = =)虚拟存储特征不连续性物理内存分配的不连续，虚拟地址空间使用的不连续部分交

31、换与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的大空间通过物理内存和快速外存相结合，提供大范围的虚拟地址空间总容量不超过物理内存和外存交换区容量虚拟存储器的最大容量是由计算机的地址结构确定的，其实际容量是由内存和硬盘交换区容量之和确定的。4、 请求分页技术中，图示windows 下的两级分页机制？见张老师ppt5、 请求分页机制中，页面置换算法有那些，具体实施页面置换过程？最佳算法(OPT)最近最久未使用算法(LRU)最不常用算法(LFU)轮转算法(clock)先进先出算法(FIFO)具体实现见张老师ppt6、 在交换技术中，进程置换策略是什么？这个还没找到= =7、 什么是

32、快表？其中内容是什么样子的？什么是页表？其结构是如何？联想寄存器器快表为缩短查找时间，可以将页表从内存装入到关联存储器(TLB) ， 按内容查找，即逻辑页号>物理页号系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系，页表放在内存，属于进程的现场信息。页表包含每页所在物理内存的基地址内存部分先发到这，还请大家指正发现这一块理解的东西特别多，如果就看提纲好像没有什么意义。还是要具体的理解那些例子。文件管理部分1、什么是文件？是一组带标识的、在逻辑上有完整意义的信息项的序列。标识是文件名：信息项是构成文件内容的基本单位长度是单个字节或多个字节文件内容由文件建立者和使用者解释

33、2、什么是文件系统？是操作系统中统一管理信息资源的一种软件。3、文件系统设计目标是什么？管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。4、什么是文件的逻辑结构、物理结构？逻辑结构是从用户角度研究文件的组织形式，分为：2无结构文件：构成文件的基本单位是字符，文件是有逻辑意义的、无结构的一串字符的集合2有结构文件：文件是由若干个记录组成，每个记录有一个键，可按键进行查找物理结构是从系统角度来看文件，从文件在物理介质上的存放方式来研究文件。5、文件物理结构有哪些？分为：2连续结构（顺序）文件信息存放在若干连续的物理块中2链接结构文件信息存放在若干不连续的物理块中，各块之

34、间通过指针连接，前一个物理块指向下一个物理块。2索引结构文件信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构-索引表，并将这些块的块号存放在一个索引表中6、 UNIX 系统采用的综合索引方式是如何实现的？有何优点？UNIX 文件系统采用多级索引结构（综合模式）完成的。7、磁盘空闲空间的管理方法？? 空闲块表所有空闲块记录在一个表中? 空闲块链表把所有空闲块链成一个链8、图示成组链接法？并说明其优点。把 n 个空闲块的地址存放在第一个空闲块中，这些块中的前n-1 个确实为空。而最后一块包含另外n 个空闲块的地址，如此继续。优点是大量的空闲块的地址可以很快的被找到。9、什么是目录文

35、件的组成？把所有FCB 组织在一起，就构成了文件目录，即文件控制块的有序集合10、采用目标文件的目的？2 提高查找文件的效率2 使文件的命名更加方便2 是文件分组更加容易11、目录的改进方法及其改进性能比较？采用目录项分解法，把FCB 分成两部分。改进的目的是加快文件检索。性能比较在幻灯片上有。12、常用的目录结构？? 一级目录，简单，易实现。有命名问题和分组问题? 二级目录，有路径，多个用户可以有同名文件，查询效率高。没有分组能力，有系统开销? 树型目录(多级目录)，层次结构清晰，便于管理和保护，有利于文件分类，解决重名问题，提高文件检索速度，能进行存取权限的控制。查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度？其它方法，哈希表，B+树13、 RAID 的概念？关键技术是什么？Redundant Array of Independent (o