操作系统第七版重点总结.doc

第一章 绪论1、OS简介 OS作为用户/计算机接口（用户观点）；OS作为资源管理者（系统观点）。 管理的对象CPU管理：完成处理机资源的分配、调度、进程管理存储管理：存储分配与回收、存储保护、内存扩充(虚拟存储)。提高利用率、提供足够的存储空间、方便进程并发运行。文件管理：如何存放信息，以提高空间利用率和读写性能。目录管理、文件的读写管理和存取控制：设备管理：方便的设备使用、提高CPU与I/O设备利用率。设备分配与回收、缓冲区管理。2、OS定义操作系统是计算机系统中的一个系统软件，是一些程序模块的集合它们能以尽量有效、合理的方式组织和管理计算机的软、硬件资源，合理的组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能，使得用户能够灵活、方便、有效的使用计算机，使整个计算机系统能高效地运行。是计算机与用户之间的接口。3、OS的分类和发展 (1)单道批处理系统 作业：程序+数据+作业说明书。 (2)多道程序系统：两个或多个作业同时进入主存；切换运行；宏观上并行，微观串行。特征：调度性（作业调度，进程调度）、无序性、多道性。优点：资源利用率高，系统吞吐量大。缺点：周转时间长，无交能力 (3)分时系统(UNIX)：满足用户与系统交互的需要，允许多用户通过终端同时访问系统，共享计算机资源。特征：多路性、独立性、及时性、交互性。分时系统需要解决的问题：1存储管理：虚拟存储器。2文件系统，磁盘管理。3CPU调度。4 进程同步和通信的机制。实现的关键问题：及时接受、及时响应 (4)实时系统：实时系统必须具有在一个事先定义好的时间限制内。 硬实时系统：保证关键任务按时完成，任务完成具有严格的时间限制。工业过程控制、机器人等领域。硬实时系统功能少。软实时系统：关键实时任务的优先级要高于其它任务优先级，且在完成之前能保持其优先级。多媒体、高级科学研究、海底探险、星际漫游。 (5)多处理器操作系统：有多个处理器（多重处理），它们共享总线、时钟、内存和外部设备。并行系统，紧耦合系统。优点：增加计算吞吐量、经济、增加可靠性非对称式：主处理器只有一个，运行OS；管理整个系统的资源，为从处理器分配任务；从处理器可有多个，执行应用程序或I/O处理。对称式：每个处理器都运行同一个OS的副本，它们之间可以相互通信。任务负载较为平均，性能调节容易“傻瓜式”。 (6)网络操作系统：NOS是在通常操作系统功能的基础上提供网络通信和网络服务功能的操作系统。网络操作系统为网上计算机进行方便而有效的网络资源共享，提供网络用户所需各种服务的软件和相关规程的集合。 (7)分布式操作系统分布式系统：将大量的计算机组织在一起，不共享主存和时钟的一组处理器。通过网络进行连接。使用协议通信。分布式操作系统：所有系统任务可在系统中任何处理机上运行，自动实现全系统范围内的任务分配并自动调度各处理机的工作负载。向用户提供对各种系统资源的访问，加快计算速度，增强功能，提高数据的可靠性，加强可靠性。4、研究操作系统的几种观点：作为软件来看的观点、资源管理的观点（是资源管理器）、进程的观点、虚机器观点(为硬件平台扩充功能)、服务提供者观点。5、现在OS的特征：任务共发性、资源共享性、虚拟性（分时系统一台处理机虚拟为若干台、虚拟存储、设备、通道、文件、用户组、网络等）、异步性。第二章 计算机系统结构1、中断：CPU对系统中或系统外发生的某个事件作出的一种反应。如外部设备完成数据传输，实时设备出现异常等。 硬件出发；软件触发：1）错误；2）系统调用；3）监控程序调用。2、引入中断的目的：中断机制是操作系统得以正常工作的最重要的手段，有人把操作系统称为是由“中断驱动”或者 “（中断）事件驱动”。它可以解决：主机与外设的并行工作问题、提高可靠性、实现实时控制、中断是实现多道程序的必要条件。3、特权指令和非特权指令特权指令：只能由操作系统程序使用的指令，如启动I/O设备、设置时钟、控制中断屏蔽位、清内存、加载PSW等（能引起损害的机器指令）。可能导致危害的指令。如果在用户模式下执行，将会不执行或看做非法指令及陷阱。非特权指令：用户程序系统所使用的指令。4、双重操作模式：为了确保OS和所有其它程序和数据不受任何故障程序影响，CPU至少需要两重独立的操作模式：系统模式（特权状态、系统态、管态）：操作系统管理程序运行时的状态，较高的特权级别。当CPU处于系统模式时，程序可以执行特权指令，访问所有资源，并可以改变处理器状态。用户模式（用户态、目态、常态）：用户程序运行时的状态，较低的特权级别。当CPU处于用户状态时，程序只能执行非特权指令。CPU状态转换：目态 管态：通过中断（系统调用、中断事件）。管态 目态：设置PSW(修改程序状态字)。 5、系统调用： 用户请求OS执行含有特权指令的任务6、I/O保护： 所有I/O指令都是特权指令；用户只能通过OS进行I/O及系统调用；确保用户程序不能获得管理模式7、CUP保护 定时器中断响应：进入OS。设置定时器是特权指令。第三章 操作系统结构1、用户与OS的两种接口：(1)命令接口联机接口（交互式）:使用系统提供的操作命令，交互地控制程序执行和管理计算机系统。如系统管理、环境设置、权限管理、文件管理等。脱机接口：以作业说明书的方式提交给系统（批的方式）；执行过程中，用户无法干涉。 (2) 程序接口（系统调用）：系统调用是操作系统提供给编程人员的唯一接口，编程人员利用系统调用，完成与机器硬件部分相关的工作。用户就可以在程序中调用操作系统所提供的一些子功能。2、命令解释系统（外壳，shell)：是OS的重要组件之一，是用户和OS的接口。作用：读入用户的输入或者文件中的命令，并运行它（们）；通常转换为一个或者多个系统调用。3、系统调用(system call)：OS核心中都有一组实现系统功能的过程（子程序），系统调用就是对上述过程的调用。是进程与OS之间的接口/程序接口。编程人员利用系统调用，向OS提出服务请求，由OS代为完成。系统调用运行于核心态；而普通的函数调用由函数库或用户自己提供，运行于用户态。实现过程：陷入指令陷入处理机构保护现场寻找子程序入口调用子程序恢复现场返回。4、陷入：是指CPU内部事件产生的中断，它包括程序运算引起的各种错误，如地址非法，效验错，页面失效，存取控制错，从用户态到核心态的切换等都是陷入的例子。5、陷入指令(访管指令)：由于系统调用引起处理机中断的指令。6、陷入与中断的区别：相同点：它们都是由相同的硬件机构处理的事件；不同点：陷入通常由处理机正在执行的现行指令引起，而中断则是由与现行指令无关 的中断源引起；陷入处理程序提供的服务为当前进程所用，而中断处理程序提供的服务则不是为了当前进程的；中断只能在指令之间被响应，而陷入可以在一条指令执行中被响应；陷入处理程序在各自的堆栈上进行，中断处理程序则在系统堆栈环境中进行7、虚拟机：通过某种技术，使物理计算机作为共享资源从而创建虚拟机。利用CPU调度、虚拟内存技术，OS能创建一种幻觉，从而使进程认为有自己的处理器和自己的内存。每台虚拟机都与裸机相同，所以每台虚拟机可以运行一台裸机所能够运行的任何类型的操作系统。不同的虚拟机可以运行不同的操作系统。8、操作系统的结构： (1)整体或模块结构整个系统按功能进行设计和模块划分。系统是一个单一的、庞大的的软件系统。由众多服务过程（模块）组成，可以随意调用其他模块中的服务过程。优点：具有一定灵活性，模块之间转接的灵活性使运行中的高效率；结构紧密,接口简单直接；缺点：功能划分和模块接口难保正确和合理；模块之间的依赖关系（功能调用关系）复杂（调用深度和方向）。 (2)分层结构：从资源管理观点出发，将OS划分为若干层次。在某一层次上代码只能调用低层次上的代码，使模块间的调用变为有序性。有利于系统的维护性和可靠性。优点：功能明确，调用关系清晰（高层对低层单向依赖），有利于保证设计和实现的正确性；低层和高层可分别实现（便于扩充）；高层错误不会影响到低层。缺点：效率低；层次之间的调用开销。 (3) 微内核结构(客户服务器结构)：只给内核分配一些最基本的功能，运行在内核模式。 (如：内存、进程间通信、基本调度等)。其它的OS服务都是由运行在用户模式下的进程完成，可作为独立的应用进程，称为服务进程。微内核提供客户程序和运行在用户空间的各种服务之间的通信能力。 (4)虚拟机结构：使用虚拟机的好处：通过完成保护系统资源，虚拟机提供了一个安全层，每个虚拟机完全与其它虚拟机隔开，从而使系统资源被完全保护；虚拟机允许进行系统开发而不必中断正常的系统操作：系统程序员有自己的虚拟机，系统开发可在虚拟机而不是真实的物理机器上进行。9、现代操作系统的特征：并发、共享、虚拟、异步性。10、保护机制必须：区分授权使用和非授权使用、指定要施加的控制、提供加强控制的手段第四章 进程管理1、程序顺序执行的特点：顺序性：按照程序结构所指定的次序（可能有分支或循环）封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定,不受外界影响。可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系。执行结果的确定性：程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同。2、程序并发执行的特点：间断(异步)性：“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系； 失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。 失去可再现性：失去封闭性 失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。并发程序执行的结果与其执行的相对速度有关，是不确定的。3、进程定义：一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。简言之，进程是程序的一次执行活动。进程 = 代码段 + 数据段 + PCB4、进程特性：动态性：进程对应程序的执行；进程是动态产生，动态消亡的；进程在其生命周期内，在三种基本状态之间转换。独立性：各进程的地址空间相互独立，除非采用进程间通信手段；并发性：任何进程都可以同其他进程一起向前推进。异步性：每个进程都以其相对独立的不可预知的速度向前推进。5、进程与程序的区别：进程是动态的，程序是静态的：程序是有序代码的集合；通常对应着文件、静态和可以复制。进程是程序的执行。进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和PCB(进程控制块)。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。6、进程的状态及转换条件：挂起（Suspend）：把一个进程从内存转到外存。激活（Activate）：把一个进程从外存转到内存。NuLL新建：创建执行一个程序的新进程新建就绪：OS准备好了接纳一个进程，进程进入内存。就绪运行：OS调度程序选择一个新的进程运行（占据CPU）。运行就绪：运行进程用完了时间片；运行进程被中断（剥夺），因为一高优先级进程处于就绪状态。运行阻塞：当一进程等待某一事件的发生时，如：OS尚未完成系统服务调用、对一资源的访问尚不能进行、初始化I/O 且必须等待结果、等待某一进程提供输入 (IPC)。阻塞就绪：当进程所等待的事件发生时。就绪退出：父进程可以中止一个子进程；如果一个父进程终止，与该父进程相关的所有子进程都被终止。阻塞退出：父进程可以中止一个子进程。7、进程控制块PCB：进程标识信息、CPU寄存器、进程控制信息。第五章 进程同步1、进程的同步（直接制约）：指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。2、进程的互斥（间接制约）：由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。3、一些相关概念：互斥：指多个进程不能同时使用同一个资源； 死锁：指多个进程互不相让，都得不到足够的资源； 饥饿：指一个进程一直得不到资源（其他进程可能轮流占用资源）； 临界资源：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量； 临界区：进程中访问临界资源的一段代码。4、使用临界区应遵循的准则：有空让进：当无进程在临界区时，任何有权使用临界区的进程可进入；无空等待：不允许两个以上的进程同时进入临界区；多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待；有限等待：任何进入临界区的要求应在有限的时间内得到满足；让权等待：处于等待状态的进程应放弃占用CPU；平等竞争：任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定。5、互斥的实现硬件方法：（1）中断禁用 (关中断, Interrupt Disabling)如果进程访问临界资源时(执行临界区代码)不被中断, 就可以利用它来保证互斥地访问。过程:关中断原语;临界区开中断原语其余部分（2）专门的机器指令：设计一些机器指令，用于保证两个动作的原子性 ，如在一个指令周期中实现测试和修改。6、信号量：初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”）若为非负值：表示当前的空闲资源数（s.count= 0 :可用的资源数)若为负值：其绝对值表示当前等待临界区的进程数(|s.count|为等待的进程数) 操作：操作系统对信号量只能通过初始化和两个标准的原语来访问。对信号量的操作只有三种原子操作:初始化: 通常将信号量的值初始化为非负整数P操作(wait操作）：使信号量的值减1(申请一个单位的资源 (s.count-)如果使信号量的值变成负数, 则执行P操作的进程被阻塞(当s.count 0时, 资源已分配完毕, 进程自己阻塞在S的队列上-让权等待)V操作(signal操作）：使信号量的值加1(释放一个单位资源 (s.count+)如果信号量的值不是正数, 则使一个因执行v操作被阻塞的进程解除阻塞(若s.count = 0, 则唤醒一个等待进程)。第六章 死锁1、定义：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程。2、产生原因：资源不足导致的资源竞争：多个进程所共享的资源不足，引起它们对资源的竞争而产生死锁。并发执行的顺序不当。进程运行过程中，请求和释放资源的顺序不当，而导致进程死锁. 如P,V操作的顺序不当。3、四个必要条件：互斥条件：指进程对所分配到的资源进行排它性使用, 即在一段时间内某资源只能由一个进程占有。如果此时还有其它进程申请该资源,则它只能阻塞, 直至占有该资源的进程释放。占有且等待（请求和保持条件）：进程已经保持了至少一个资源, 但又提出了新的资源要求, 而该资源又已被其它进程占有, 此时请求进程阻塞, 但又对已经获得的其它资源保持不放。非抢占（非剥夺）条件：进程已获得的资源, 在未使用完之前, 不能被剥夺, 只能在使用完时由自己释放。循环等待条件：在发生死锁时, 必然存在一个进程-资源的封闭的环形链. 即进程集合P0, P1, P2, , Pn中的P0正在等待一个P1占用的资源; P1正在等待P2占用的资源, , Pn正在等待已被P0占用的资源。4、处理方法：预防死锁：通过限制如何申请资源的方法来确保至少有一个条件不成立。避免死锁：根据有关进程申请资源和使用资源的额外信息，确定对于一个申请，进程是否应该等待。检测死锁和恢复：通过算法来检测并恢复忽视此问题：认为死锁不可能在系统内发生。如Unix采用这种方法。5、死锁避免：不需象死锁预防那样，事先采取限制措施破坏产生死锁的必要条件; 在资源的动态分配过程中, 采用某种策略防止系统进入不安全状态, 从而避免发生死锁。 定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。6、安全状态：系统能按某种顺序, 如, 为每个进程分配所需资源, 直到最大需求, 使每个进程都可顺序完成, 称系统处于安全状态。只要系统处于安全状态, 必定不会进入死锁状态；死锁状态是不安全状态。不安全状态不一定是死锁状态（不安全状态可能导致死锁）。7、银行家算法：Availablej: 尚未分配的资源j的数量；Maxi, j（ClaimI,j): 进程i 对资源j 的最大需求量；Allocationi, j: 进程i获得的资源j的数量；Needi, j: 进程i尚需的资源j的数量。8、死锁恢复方法：进程终止：终止所有的死锁进程OS中常用方法；一次只终止一个进程直到取消死锁循环为止基于某种最小代价原则。资源抢占：逐步从进程中强占资源给其它进程使用，直到死锁环被打破为止。9、资源分配图： (1)表示方法：圆圈代表进程，方块代表一类资源。方框中的点：由于一种类型的资源可能有多个，可用方框中的一个点代表一类资源中的一个资源分配边：从资源节点(圆圈)到进程节点(方块)的有向弧表示资源已经分配给进程；请求边：从进程到资源的有向弧表示进程当前正处于阻塞状态，等待资源变为可用。 (2) 有向图形成环路则形成死锁。(3)化简方法：假设某个RAG中存在一个进程Pi，此刻Pi是非封锁进程，那么可以进行如下化简：当Pi有请求边时，首先将其请求边变成分配边(即满足Pi的资源请求)，而一旦Pi的所有资源请求都得到满足，Pi就能在有限的时间内运行结束，并释放其所占用的全部资源，此时Pi只有分配边，删去这些分配边（实际上相当于消去了Pi的所有请求边和分配边），使Pi成为孤立结点。（反复进行） 系统中某个时刻S为死锁状态的充要条件是S时刻系统的资源分配图是不可完全简化的。 在经过一系列的简化后，若能消去图中的所有边，使所有的进程都成为孤立结点，则称该图是可完全简化的；反之的是不可完全简化的。第七章 CPU调度1、处理器调度类型：长程调度（高级调度）：从外存的后备队列中选择一个或者多个作业调入内存，并为它们创建进程，分配必要的资源。创建就绪/挂起；创建就绪。中程调度（中级调度）：将进程的部分或全部加载到内存中，提高内存利用率。进程状态变化（通过执行挂起和激活操作）：就绪/挂起就绪；阻塞/挂起阻塞。短程调度（低级调度、进程调度、分派程序dispather )：选择哪个进程在处理机上执行，执行最频繁）。进程状态：就绪运行。2、非抢占调度（NonPreemptive）：就绪进程不可以从运行进程手中抢占CPU。一旦进程处于运行状态，它就不断执行直到终止或者为等待I/O或请求某些操作系统服务而阻塞自己，才把CPU让给别人。抢占调度（Preemptive）：就绪进程可以从运行进程手中抢占CPU。允许调度程序根据某种策略中止当前运行进程的执行，将其转移到就绪状态，并选择另一个进程投入运行。3、调度程序的功能： 保存现场：记录放弃CPU的进程A的现场信息（如PC, 通用寄存器的内容等）。选择进程：当进程出让CPU或调度程序剥夺执行状态进程占用的CPU时，选择适当的进程B分派CPU。完成上下文切换：用户态执行进程A代码，进入OS内核（通过时钟中断或系统调用）；保存进程A的上下文，载入进程B的上下文（CPU寄存器和一些表格的当前指针）；用户态执行进程B代码。4、调度准则：面向用户的准则：响应时间 (min)；周转时间（结束时间-进入系统时间）(min)；优先级。面向系统的准则吞吐量(max)；CPU利用率(max)；公平；资源的平衡使用；系统开销(min)。5、调度算法：算法比较项目FCFSRRSJF优先权HRRFMFQ选择依据maxw常量mins见正文max(w+s)/s)见正文调度方式非抢占式抢占式（按时间片）非抢占式抢占式（进程到达时）非抢占式抢占式（按时间片）吞吐量不突出如果时间片太小，可能很低高高高不突出响应时间可能很高，特别在进程执行时间有很大变化时对于短进程提供良好的响应时间对于短作业（进程）提供良好的响应时间提供良好的响应时间提供良好的响应时间不突出开销最小低可能高可能高可能高可能高对进程的影响不利于短作业（进程）和I/O繁忙型作业（进程）公平对待不利于长作业（进程）不利于长进程良好的均衡可能偏爱I/O繁忙型作业（进程）“饥饿”问题无无可能可能无可能第八章 线程1、引入线程的原因：进程时空开销大、通信代价大、不能很好的利用多处理器系统、不适合并行计算和分布并行计算的要求。2、线程定义：进程中的一个实体CPU调度和分派的基本单位与同进程内的其它线程共享进程所拥有的资源：线程必须在某个进程内执行，它所需的其它资源，如代码段、数据段、打开的文件和信号等，都由它所属进程拥有。只拥有运行所必须的资源: 如PC、寄存器、 栈优点：并发程度高、响应度高；易于调度，开销小；资源共享；多处理器体系结构的利用。3、进程和线程的区别：一个进程可以有多个线程，但至少有一个线程；而一个线程只能在一个进程的地址空间内活动。每当创建一个进程时，至少要同时为该进程创建一个线程，否则该进程无法被调度执行。地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享某进程内的线程在其他进程不可见。通信：进程间通信采用IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信；所有线程可共享进程的主存，不需要特殊的通信机制。调度：线程上下文切换比进程上下文切换要快得多。OS中引入进程目的：使多个程序并发执行，以便改善资源使用率和提高系统效率。OS中引入线程目的：减少程序并发执行时所付出的时空开销，并发性更好。4、用户级线程（ULT，User Level Thread）用户线程的维护由应用进程通过线程库来完成；线程库：应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程，无需内核支持。特点：内核不了解用户线程的存在；用户线程切换不需要内核特权；速度快。线程的创建和调度由应用软件内部进行，无需用户态/核心态切换，所以速度特别快。优点：线程切换不调用核心；调度是应用程序特定的：可以选择最好的算法；ULT可运行在任何操作系统上（只需要线程库）。5、内核线程(KLT，kernel-level thread) 有关线程的所有管理工作都在OS内核完成，应用程序部分没有线程管理的代码，只有一个到内核线程的API线程切换由内核完成；内核维护进程和线程的上下文信息；优点：一个线程发起系统调用而阻塞，不会影响其它线程的运行，内核可以继续调度调度同一个进程中的另一个线程；内核可以将同一进程中的多个线程调度到多个处理器上。缺点： 由于有内核的参与，需要额外开销； 线程之间的切换需要内核的模式切换。6、多线程模型：多对一模型：将多个用户级线程映射到一个内核线程。一对一模型：将每个用户线程映射到一个内核线程。一个线程阻塞时，另一个线程可以继续执行。多对多模型：可以创建任意多的必要用户线程，且相应内核线程能在多处理器系统中并发执行；一个线程阻塞时，另一个线程可以继续执行。7、线程池：在进程建立时就创建若干线程，将这些线程放在一个“池”中等待工作。当服务器接收到一个请求时，就唤醒池中一个线程，并将要处理的请求传递给它；一旦线程完成了任务，它会返回到池中再等待其它的工作；如果池中没有可用的线程，服务器就会一直等待，指导有空闲线程为止。优点：用现有线程处理请求通常臂等待创建新线程快；线程池限定了任何时候可存在线程的数量。第九章 内存管理1、地址重定位：将逻辑地址转变为物理地址的过程。（1）静态地址重定位：在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址都改成实际的物理内存地址。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。程序的存储空间只能是连续的一片区域不能再移动。（2）动态地址重定位：在程序运行过程中要访问内存数据时再进行地址变换，即在逐条指令执行时完成地址映射。OS可以将一个程序分散存放于不连续的内存空间，可以移动程序。2、覆盖与交换：（1）覆盖： 原理：在任何时候只在内存中保留所需的指令和数据；当需要其它指令时，它们会装入到刚刚不再需要的指令所占用的内存空间。 特点：覆盖不需要OS提供特殊的支持，但程序员必须适当地设计和编写覆盖结构。（2）交换： 原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入）。交换单位为整个进程的地址空间。 与覆盖的比较：与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构。交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段。3、连续内存分配固定分区：把内存分为一些大小相等或不等的分区(partition)，每个应用进程占用一个或几个分区。操作系统占用其中一个分区分区的划分原则一般由系统操作员或操作系统决定，分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变特点：适用于多道程序系统和分时系统、支持多个程序并发执行、难以进行内存分区的共享。 问题：可能存在内碎片和外碎片。 分区大小相等和分区大小不相等两种情况。4、连续内存分配可变分区：内存不是预先划分好的，而是当进程装入时，根据进程的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则，令其等待主存空间。评价：没有内碎片；在开始时是很好的，但最后，导致在存储器中出现很多空洞外部碎片；解决方法：压缩。压缩（compaction）：OS不时地移动进程，将它们放在一起，并且使所有空闲空间连成一片。压缩非常费时，浪费了处理器的时间。压缩需要动态重定位的能力，即必须能够将程序从主存的一块区域移动到另一块区域，而不会使程序中的存储器访问无效。 分配算法：首次适配法（分区按起始地址递增的顺序排列）、最佳匹配法（按空闲区大小从小到大的顺序排列）、最差匹配法（按空闲区大小从大到小的顺序排列）、临近匹配法（到最后分区时再回到开头）。5、紧缩（compaction）：移动内存内容，以便所有空闲空间合并成一整块。条件：允许进行动态重定位可以首先移动程序和数据，然后再根据新基地址的值来改变基地址寄存器。实现：一种简单的方法是将所有进程移动到内存的一端，而将所有的空闲区(孔)移动内存的另一端，以生成一个大的空闲块。开销：开销大。6、分页管理：多级页表组织：有一个页目录，每项指向一个页表。如果页目录的长度为X，且一个页表的最大长度为Y，一个进程可以有XY个页。在两级页表时，指令所给出的地址分为三部分：页表号、页号、偏移地址。 两级页表：page numberpage offsetpip2d1010127、段式内存管理 将进程的地址空间按内容或函数关系划分为若干个段(segment) ，每个段定义一组逻辑上完整的程序或数据，如一个进程可以被划分为主程序段、子程序段、数据段、堆栈段等。 程序加载时，分配时以段为单位分配其所需的所有段的内存（内存分区） 每个段是一个首地址为0的，连续的一维线性空间，段长可以动态增长。段的大小不需要相等； 段式虚地址空间的访问有2部分：段名和段内地址。 当一个进程被调入时，它的所有段都被装入到存储器的可用区域中，并建立一个段表； 这些段不必连续；物理内存的管理采用动态分区。需要CPU的硬件支持。 然后通过地址映射机构将段式虚地址转换为实际的内存物理地址。 页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。与动态分区不同：一个程序可以占据多个分区，这些分区不要求连续。 段表：段基址+段长度。一个nm位的地址：n位段号，m位偏移量。以段号为索引，查找段表，并将偏移量与段长比较，物理地址=起始地址+偏移量。8、段式与页式的比较u 分页是出于系统管理的需要，分段是出于用户应用的需要。u 一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。u 页大小是系统固定的，而段大小则通常不固定。u 逻辑地址表示：u 分页是一维的，各个模块在链接时必须组织成同一个地址空间；u 分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。u 通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。9、段页式用户的地址空间由程序员划分成许多段，每个段又划分成许多固定大小的页，页的大小等于主存中帧的大小。逻辑地址的组成：段号、页号、页内偏移地址，程序员可见的仍是段号和段内偏移量。从系统角度看，段偏移量是指定段中的一个页号和页内偏移量。地址变换：先查段表，再查该段的页表。第十章 虚拟内存1、局部性原理：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。2、虚拟内存：将内存看成一个巨大的、统一的存储数组；总容量不超过物理内存和外存交换区容量之和。3、页表的改变：P：表示该页是否在内存中。如果在主存，则页表中还包括该页的帧号。M：修改位，表示相应页的内容从上次装入主存到现在是否已经改变。还有其它一些用于保护和共享的位。4、缺页中断：在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断(page Fault)。5、Belady异常：有些情况下，页故障率（缺页率）可能会随着所分配的帧数的增加而增加。6、最佳算法（OPT）：选择替换下次访问距当前时间最长的那些页。无Belady。7、先进先出（FIFO）：替换驻留在主存中时间最长的页。有Belady。8、最近最久未使用（LRU）：替换主存中上次使用距离当前最远的页，向后看。无Belady。9、系统颠簸：刚刚被淘汰出去的页很快又被访问，需要重新调入；但是，调入不久又再次被淘汰出去。如此反复，使得整个系统的页面替换非常频繁，使大部分机器时间都用在来回进行的页面调度上，这种局面称为系统颠簸。产生原因：如果CPU利用率太低，调度程序就会增加多道程序度，将新进程引入系统中。新进程启动运行，导致缺页，从其他进程中取帧，进行换入换出。10、请求段式管理： 原理：一个进程只有部分分段放在内存就可运行。程序运行时，先把当前需要的一段或者几段装入内存，其它段仅仅在调用时才装入。11、虚拟段页式：是虚拟页式和虚拟段式存储管理的结合，由于开销比较大，一般只用于大型机系统中。存储管理的分配单位是：段，页。逻辑地址的组成：段号，页号，页内偏移地址，程序员可见的仍是段号和段内相对地址。地址变换：先查段表，再查该段的页表。缺段中断和缺页中断。第十一章 文件管理1、文件系统：文件系统，就负责信息的组织、存储和访问。文件系统的功能就是提供高效、快速和方便的信息存储和访问功能。2、文件：记录在外存上的相关信息的具有名称的集合。（文件是具有符号名的数据项的集合）。文件名是文件的标识符号。文件包括两部分，文件体：文件本身的信息；文件说明：文件存储和管理信息。域：基本数据单元。包含：值和长度（可变长度/固定长度）。域长度可变，域数据可变（记录有一个长度域）。记录：一组相关的域。如：一个雇员记录：名字、职工号、工作单位等。3、文件管理系统:文件系统是操作系统中管理文件的机构，提供文件存储和访问功能。目录:目录是由文件说明索引组成的用于文件检索的特殊文件。所有文件的信息都保存在目录中。4、顺序文件 (sequential file)：可按关键字域的某种顺序排列。所有记录都既有相同的长度，是一种常用的文件组织。应用：顺序文件通常用于批处理中，涉及到对所有记录的处理（如关于记帐或工资单的应用）；顺序文件通常是最佳的。（折半查找等）；访问大型顺序文件时性能差；查询或更新记录的交互式应用，顺序文件性能很差-顺序搜索。5、索引顺序文件：在顺序文件的基于关键字排序基础上，另外建立索引(index)文件和备份文件(overflow file)。索引文件用于加快顺序文件的检索速度，备份文件，相当于顺序文件中的日志文件，可以根据它前面记录的指针进行定位。建立索引的方法：将顺序文件中的记录按照某种标准分组，如可将打头字母相同的记录分为一组，可按每小时或固定长度的时间将记录分组等。一级索引：索引文件中的记录由关键字域和指向主文件的指针组成。在查找时，首先搜索索引，查找关键字值等于目标关键字或者位于目标关键字值之前且最大的索引，然后在该索引的指针所指的主文件中的位置处开始搜索。6、文件存取方法：（1）顺序存取法: 按照文件信息的逻辑顺序(记录的排列顺序)依次存取。如：为了存取记录Ri ,必须先通过记录R1 R2 Ri-1 。（2）随机存取法(直接存取）:可以按任意的次序对文件进行读写操作,如可根据记录的编号来直接存取文件中的任意一个记录 （3）索引存取：对文件中的记录按某个数据项的值进行排列，从而可以根据键值来快速存取。7、文件目录内容：一个计算机系统中有许多文件，为了有效利用存储空间及迅速准确的完成由文件名到文件物理块的转换，实现按名存取，须将文件名及其结构信息等按一定的组织结构排列，以方便文件的搜索。 为了对文件进行控制和管理，在文件系统内部，给每个文件唯一地设置一个文件控制块（FCB）。文件目录：为了加快对文件的检索，一般将文件控制块集中在一起进行管理。这种文件控制块的有序集合称为文件目录。文件控制块就是其中的目录项。完全由目录项构成的文件成为目录文件。目录是由文件说明索引组成的用于文件检索的特殊文件。目录内容：包括有关文件的信息：属性、位置和所有权等。文件目录提供的最基本的功能：将文件名转换成该文件在外存的物理位置，实现文件名与磁盘块之间的映射8、目录基本操作u 搜索文件：通过查找目录结构，实现特定文件的按名查找u 创建文件：建立新文件，将相应控制块加到目录中去u 删除文件：当一个文件不再需要时，从目录中删除u 列出目录：u 重命名文件u 跟踪文件系统9、目录的组织结构：（1）单级目录结构：（2）两级目录结构：（3）树状目录结构：（4）无环图目录：u 树形结构禁止共享文件和目录。无环图目录结构则是在树型目录的基础上，进一步允许多个目录项指向同一个数据文件或者目录文件，实现了多个用户或者多个目录对目录或者数据文件的共享允许目录含有共享子目录和文件。u 同一个文件或子目录可能出现在两个不同目录中。它们通过指针与文件相连，即它允许一个文件或者目录在多个父目录中占有项目。u UNIX的目录结构即属于无循环图结构。10、路径：路径名：任何文件可以按照根目录或主目录向下到各个分支最后达到该文件的路径来定位。这一系列目录名和最后达到的文件名自身组成了该文件的路径名。多个文件可以同名，只要保证它们的路径名是唯一的即可。工作目录（working directory）：对交互用户或进程而言，总有一个当前路径与之相关联，称作工作目录，文件通常按照相对于工作目录的方式被访问。当交互式用户登录时，或者当创建一个进程时，默认的工作目录是用户目录。系统将当前工作目录中的内容复制到内存缓冲区中，在访问文件时先访问内存中的工作目录。当要访问的文件不在当前目录中时，再访问外存中的目录，提高了查找速度。绝对路径：从根目录开始指定的目录。相对路径：从当前工作目录开始。11、文件存取控制矩阵：12、文件存取控制表：以文件为单位，把用户按某种关系划分为若干组，同时规定每组的存取权限。实现时，该表放在文件说明中，打开文件时，被复制了内存中；效率高。第十二章 文件系统实现1、文件系统的层次结构：2、文件分配方法：（1）连续分配u 连续分配：创建文件时，分配一组连续的块；FAT中每个文件只要一项，说明起始块和文件的长度。对顺序文件有利。u 优点:u 简单。适用于一次性写入的操作 u 支持顺序存取和随机存取，顺序存取速度快 u 所需的磁盘寻道次数和寻道时间最少（因为由于空间的连续性，当访问下一个磁盘块时，一般无需移动磁头，当需要磁头移动，只需要移动一个磁道。u 缺点:u 文件不能动态增长（可能文件末尾处的空块已经分配给别的文件）u 不利于文件插入和删除u 外部碎片问题（反复增删文件后），使得很难找到空间大小足够的连续块。进行紧缩u 在创建文件时声明文件的大小。（2）链式分配u 链式分配：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。FAT中每个文件同样只需要一项，包括文件名、起始块号和最后块号。任何一个自由块都可以加入到链中。 u 优点：u 提高了磁盘空间利用率,不存在外部碎片问题u 有利于文件插入和删除u 有利于文件动态扩充u 缺点：u 存取速度慢，一般仅适于对信息的顺序存取，不适于随机存取:查找某一个块必须从头开始沿指针进行。u 可靠性问题，如指针出错；更多的寻道次数和寻道时间u 链接指针占用一定的空间，将多个块组成簇（cluster），按簇进行分配而不是按块进行分配（增加了磁盘碎片）。（3）索引分配u 索引分配：每个文件在FAT中有一个一级索引，索引包含分配给文件的每个分区的入口。文件的索引保存在一个单独的块中。FAT中该文件的入口指向这一块。u 优点：u 保持了链接结构的优点,又解决了其缺点：按块分配可以消除外部碎片，按大小可变的分区分配可以提高局部性。索引分配支持顺序访问文件和直接访问文件，是普遍采用的一种方式。u 满足了文件动态增长、插入删除的要求（只要有空闲块）u 也能充分利用外存空间u 缺点：u 较多的寻道次数和寻道时间.u 索引表本身带来了系统开销， 如：内外存空间，存取时间多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中。3、Unix的索引节点：为了加速对文件目录的查找，在Unix系统中，将文件名和其它文件说明信息分开，由文件说明形成一个称为索引节点的数据结构，而相应的文件目录项只由文件名和对应的索引节点号组成。u 文件分配以块为基础。按照需要动态进行，不是预定义的。u 文件在磁盘中的块不一定是连续的。u Unix系统为了访问文件，采用索引的方法，索引的一部分保存在该文件的索引节点中。Unix中通过为每个文件创建一个i节点的方法，巧妙：i节点中包含39个字节的地址信息，这个地址信息被组织成13个3字节的地址或指针。前10个表目是直接索引，指向文件最初的10个数据块。当文件大小小于10块时，可以直接定位到这10个块；第11个表目是一级索引表，指向磁盘中包含下一部分索引的块。第12个表目是二级索引表，第13个表目是三级索引表；u 例题：文件系统采用多级索引结构来搜索文件文件内容。设块长为512字节，每个块号长3字节。如果不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。u （512/3=170)u 一级索引：170块u 二级索引块），289005121450K字节u 三级索引：1701701704913000（块）， 4913000 5122456500K字节4、磁盘存储空间管理方法：（1）位图：使用一个向量，向量中的每位（bit）对应于磁盘中的每一个块（b