操作系统复习教材

操作系统复习第一章什么是中断Interrupt一种允许其他模块（IO、存储器）中断处理器正常处理过程的机。利用中断功能，处理器可以在IO操作的执行过程中执行其他指令。什么是指令周期InstructionCycle一个单一的指令需要的处理称为一个指令周期。两个步骤：取指阶段、执行阶段什么是中断处理当CPU执行完一条现行指令时，如果外设向CPU发出中断请求，那么CPU在满足响应的情况下，将发出中断响应信号，与此同时关闭中断，表示CPU不在受理另外一个设备的中断。这时，CPU将寻找中断请求源是哪一个设备，并保存CPU自己的程序计数器（PC）的内容。然后，他将转移到处理该中断源的中断服务程序。CPU在保存现场信息，设备服务（如交换数据）以后，将恢复现场信息。在这些动作完成以后，开放中断，并返回到原来被中断的主程序的下一条指令。什么是嵌套中断处理是指中断系统正在执行一个中断服务时，有另一个优先级更高的中断提出中断请求，这时会暂时终止当前正在执行的级别较低的中断源的服务程序，去处理级别更高的中断源，待处理完毕，再返回到被中断了的中断服务程序继续执行，这个过程就是中断嵌套。什么是局部性原理局部性原理（principleoflocality）；概况来说，局部性原理描述了一个进程中程序和数据引用的集簇倾向。空间局部性（spatiallocality）：指执行设计很多簇聚的存储器单元的趋势，这反映了处理器顺序访问指令的倾向，同时，也反应了程序顺序访问数据单元的倾向。时间局部性（temporallocality）：指处理器访问最近使用过的存储器单元的趋势。第二章什么是串行处理SerialProcessing系统（特点）串行处理：没有操作系统特点：程序员直接和硬件打交道如何操作：机器在一个控制台上运行，控制台包括显示灯、触发器、某种类型的输入设备和打印机。用机器代码编写的程序通过输入设备（如卡片阅读机）载入计算机。问题：调度：大多数装置都使用一个硬拷贝的签约表约定机器时间。提前完成任务造成闲置浪费，超时会被强制停止。准备时间：一个程序称为作业，包括往内存中加载编译器和高级语言程序（源程序），保存编译好的程序（目标程序），然后加载目标程序和公用函数并链接在一起。准备时间需要花费大量时间。什么是简单批处理系统SimpleBatchSystems（特点）中心思想：使用一个称为监控程序的软件。计算机操作员将整个批作业放在输入设备上，供监控程序使用。每个程序完成处理后返回到监控程序，同时监控程序自动加载下一个程序。从两个角度分析：监控程序角度：监控程序控制事件的顺序。大部分监控程序必须总是处于主存储器中并且可以执行，成为常驻监控程序。处理器角度：略作业控制语言（JCL）：特殊类型的编程语言其他硬件功能：1）内存保护：当用户程序正在运行时，不能改变包含监控程序的内存区域。2）定时器：防止一个作业独占系统3）特权指令：某些机器级指令被设计成特权指令，只能由监控程序执行。4）中断CPU模式：用户模式：有些内存区域是受保护的，特权指令不允许执行内核模式：可以执行特殊指令，可以访问受保护的区域什么是多道批处理系统MultiprogrammedBatchSystems（特点）背景：IO设备比处理器慢，效率低。方案：扩展内存，存放更多程序。什么是分时系统Time-SharingSystems（特点）思想：Processor’stimeissharedamongmultipleusers/jobs什么是实时系统Real-timeoperatingsystem,RTOS（特点）实时系统能够在指定或者确定的时间内完成系统功能和外部或内部、同步或异步时间做出响应的系统。特点：时间约束性；可预测性；可靠性；与外部环境的交互作用性、什么是操作系统OperatingSystem操作系统是控制应用程序执行的程序，并充当应用程序和计算机硬件之间的接口。多道程序Multiprogramming的概念及其好处多道程序设计技术是在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制下，相互穿插运行。好处：提高cpu利用率操作系统的目标方便：使计算机更易于使用有效：操作系统允许以更有效的方式使用计算机系统资源。扩展的能力：允许在不妨碍服务的前提下有效地开发、测试和引进新的系统功能。第三章进程映像的组成标识符：状态：优先级程序计数器：程序中即将被执行的下一条指令的地址内存指针：上下文数据：进程执行时处理器的寄存器中的数据I/O状态信息审计信息：可包括处理器时间总和、使用的时钟数总和、时间限制、审计号什么是执行模式，为什么需要不同的cpu执行模式用户模式（非特权模式）：内核模式（系统模式、控制模式、特权模式）：某些指令只能在特权模式下运行，包括读取或改变诸如程序状态字之类控制寄存器的指令、原始IO指令和内存管理相关的指令，有部分内存区域仅在特权模式下可以被访问。作用：保护操作系统和重要的操作系统和重要的操作系统数据表不受用户程序的干涉。什么是进程，进程和程序的区别一个正在执行中的程序一个正在计算机上执行的程序实例能分配给处理器并由处理器执行的实体一个具有以下特征的活动单元：一组执行序列的执行、一个当前状、相关的系统资源的集合什么是进程控制块ProcessControlBlock，有什么作用一个数据结构，存放上述列表信息，由操作系统创建和管理作用：是操作系统能够支持多进程和提供多处理的关键工具。因此可以说：进程是由程序代码和相关数据还有进程控制块组成的。进程切换的流程保存处理器上下文，包括程序计数器和其他寄存器更新当前处于运行态的进程的进程控制块吧把进程的进程控制块移到相应的队列选择另一个进程执行更新所选择的进程控制块更新内存管理的数据结构恢复处理器在被选择进程最近一次切换出运行态时的上下文，可以通过载入程序计数器和其他寄存器以前的值来实现。进程切换和模式切换的异同模式切换：如果存在一个未处理的中断：1.把程序计数器置成中断处理器的开始地址。2，把处理器模式从用户模式切换成内核模式，使得中断处理代码可以执行有特权的指令不同：进程状态需要设计到状态变化，发生模式切换可以不改变正处于运行态的进程状态，在这种情况下，保存上下文和以后恢复上下文只需要很少的开销。进程状态变化：两状态、五状态，能画图并描述两状态进程模型进入/——分派（即调度）——>退出————>未运行运行————><——暂停————————/状态变迁图进入分派——————>队列——————>处理器————><________________________|暂停五状态模型背景：两状态是不适用的：存在一些处于非运行状态但已经就绪等待执行的进程，同时存在一些处于阻塞态等待I/O操作结束的进程，使用单个队列，调度器不能只考虑选择队列中最老的进程。运行态Running就绪态Ready阻塞态Blocked新建态New：通常是进程控制块已经创建但还没有加载到主存中的新进程退出态Exit分派允许进入/——————>释放新建————>就绪运行————>退出|<_超时_/|/事件发生|/等待事件|/|/阻塞程序、数据、栈和属性的集合称为进程映像。程序状态字（WSP）这个寄存器里包含有状态信息第四章什么是SMP对称多处理在微操作级别，同一时刻会有多个控制信号产生，可以把取操作和执行操作重叠起来。通过复用处理器提供并行性的手段：对称多处理（SMP）系统、集群系统指令和数据流的不同类型单指令单数据（SISD）流：一个单处理器执行一个单指令流，对保存在一个存储器中的数据进程进行操作。单指令多数据（SIMD）流：一个机器指令控制许多处理部件步伐一致地同时执行。每个处理部件都有一个相关的数据存储空间，因此，每条指令由不同的处理器在不同的数据集合上执行。向量和阵列处理器属于这一类多指令单数据（MISD）流：一系列数据被传送到一组处理器上，每个处理器执行不同的指令序列。这个结构从未实现。多指令多数据（MIMD）流：一组处理器同时在不同的数据集上执行不同的指令序列什么是微内核Microkernel、单体内核monolithickernel，有什么优缺点微内核：微内核是一个小型的操作系统核心，为模块化扩展提供了基础。只提供基本功能。微内核组织结构的优点：一致接口Uniforminterface：进程不需要区分是内核级服务还是用户级服务，因为所有的服务都是通过消息传递提供的。可扩展性Extensibility：允许增加新的服务以及在同一功能区域中提供多个服务灵活性Flexibility：可以删减现有功能可移植性Portability：可靠性Reliability分布式系统支持对面向对象操作系统的支持微内核的潜在缺点：性能问题。单体内核—monolithickernel是一个提供操作系统应该提供的功能的大内核，包括调度、文件系、网络、存储管理等。内核的所有功能成分都能够访问它的内部数据结构和程序。典型情况下，这个大内核是作为一个进程实现的，所有元素都共享相同的地址空间。优点：减少了进程通信和状态切换的系统开销，获得较高的运行效率；缺点：内核比较庞大。进程process和线程thread的概念以及他们之间的关系线程：分派Dispatching（调度执行）的单位通常称为线程或轻量进程（LightWeightProcess，LWP）。而拥有资源所有权的单位称为进程或任务。线程是调度执行单位，进程是资源分配单位。关系：一个进程可能有一个或多个线程线程的实现方法（包括内核级线程如何实现及优缺点，用户级线程）用户级线程User-LevelThreadsULT在纯粹的用户级线程中，线程的管理工作由应用程序完成，内核没有意思到线程的存在。过程：应用程序从单线程开始，该应用程序和它的线程被分配改一个由内核管理的进程。产生新线程通过调用线程库中的派生例程完成。使用用户级线程代替内核级线程的优点：线程管理数据结构在一个进程的用户地址空间中，线程切换不需要内核模式特权，节省了在两种模式间进行切换的开销调用可以是应用程序专用的。调度算法可以去适应应用程序，而不会扰乱底层的操作系统调度器用户级线程可以再任何操作系统中运行。线程库是一组供所有应用程序共享的应用级软件包缺点：在典型的操作系统中，许多系统调用都会引起阻塞。用户级线程执行一个系统调用时，进程中所有线程都会被阻塞在纯粹的用户级线程策略中，一个多线程应用程序不能利用多处理技术。内核级线程Kernel-LevelThreads在纯粹的内核级线程软件中，线程管理工作由内核完成。应用程序没有进行线程管理的代码，只有一个到内核级线程设施的API内核级线程优点：内核可以同时把同一个进程中的多个线程调度到多个处理器中，如果进程中的一个线程被阻塞，内核可以调度同一进程中的另一个线程。内核例程自身也可以使用多线程缺点：同一进程在把控制从一个线程时传送到另一个进程时需要到内核的模式切换，开销大第五章怎样通过硬件、软件方法实现同步Synchronization互斥MutualExclusion硬件：中断禁用InterruptDisabling、专用（特殊）机器指令SpecialMachineInstructions软件：增强互斥的软件算法什么是互斥当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资源什么是竞争条件RaceCondition多个线程或进程在读写一个共享数据时结果一来于他们执行的相对时间什么是临界区criticalsection一段代码，在这段代码中进程将访问共享资源，只能同时有一个进程在这段代码中运行什么是信号量Semaphores（一般信号量、二元信号量、强信号量、弱信号量）一个特殊变量。两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一个位置停止，直到它接收到一个特定的信号。什么是死锁两个或两个以上的进程因每个进程都在等待其他进程完成某些事情而不能继续执行什么是活锁两个或两个以上的进程为了响应其他进程中变化而继续改变自己的状态但不做有用的工作。什么是饥饿一个可运行的进程尽管能继续执行，但被调度器无限期地忽视，而不能被调度执行。怎么用信号量和临界区实现同步互斥并发过程中考虑的四个重点问题操作系统必须能够记住各种活跃进程操作系统必须为每个活跃进程分配和释放各种资源操作系统必须保护每个进程的数据和物理资源，避免其他进程无意的干涉一个进程的功能和输出结果必须与执行速度无关。生产者和消费者模型描述：有一个或多个生产者产生某种类型的数据，并放置在缓冲区中；有一个消费者从缓冲区中取数据，每次取一项。读者写者问题哲学家就餐问题第六章资源的类别（可重用资源、）可重用资源ReusableResources：一次只能供一个进程安全地使用，并且不会由于使用而耗尽的资源。如处理器、IO通道等。可消费资源ConsumableResources：可以创建并且可以销毁的资源。如中断、信号、IO缓冲区的信息。什么是死锁Deadlock、饥饿Starvation死锁可以被定义为一组竞争系统资源或相互通信的进程间相互的“永久”阻塞。死锁发生的四个条件互斥Mutualexclusion。一次只有一个进程可以使用一个资源占有且等待Hold-and-wait。当一个进程在等待分配到的其他资源时，其继续占有已分配得到的资源非抢占Nopreemption。不能强行抢占进程中已经占有的戏院。循环等待Circularwait。存在一个封闭的进程链，使得每个资源至少占有此链中下一个进程所需要的一个资源。解决死锁的三种方法（避免Avoidanc、检测、预防Prevention）的异同之处死锁预防死锁预防策略：试图设计一种系统来排除发生死锁的可能性。实现方式：通过约束资源请求，防止四个死锁条件中至少一个的发生，会导致低效的资源使用和低效的进程执行。死锁避免原理：允许三个必要条件，但通过明智的选择，确保永远不会达到死锁点，比死锁预防允许更多的并发。两种死锁避免方法：进程启动拒绝资源分配拒绝（银行家算法）安全状态：至少有一个进程执行序列不会导致死锁（即所有进程都能运行知道结束）不安全状态：不安全的一个状态。死锁避免的优点：不需要死锁预防中的抢占和重新运行进程，而且限制少。死锁避免使用限制：必须事先声明每个进程请求的最大资源考虑的进程必须是无关的，他们执行的顺序必须没有任何同步要求的限制分配的资源数目必须是固定的在占有资源时，进程不能退出死锁检测死锁检测算法步骤：标记Allocation矩阵中一行全为0的进程初始化一个临时向量W，令W等于Available向量查找下标i,使进程i的请求小于或等于W,标记此进程，并令W=W+这一进程之前所分配的资源。找不到则终止算法。返回步骤3.银行家算法（重点）第七章内存管理的需求Relocation重定位：程序被换出到磁盘，下一次被换入时，不必放在以前的区域，而是可以重定位到内存的不同区域。Protection保护：每个进程都应该受到保护，避免其他进程的干涉。注意：内存保护的需求必须由处理器（硬件）实现，而不是由操作系统满足。Sharing共享：LogicalOrganization逻辑组织PhysicalOrganization物理组织：主存不足时，程序员使用覆盖（overlaying）技术来组织程序和数据，不同的模块被指派到主存中的同一区域，主程序负责在需要时换入或换出程序。什么是内部碎片internalfragmentation、外部碎片externalfragmentation内部碎片：由于被装入的数据块小于分区大小，而导致分区内部有空间浪费，这种现象称为内存碎片。外部碎片：动态分区方法开始时是很好的，但它最终会导致在内存中出现许多小的空洞，这种现象称为外部碎片。逻辑地址、相对地址、物理地址的概念和关系逻辑地址LogicalAddress：是指与当前数据在内存中的物理分配地址无关的访问地址，在执行对内存的访问之前必须把它转换为物理地址相对地址RelativeAddress：是逻辑地址的特例，是相对于某些已知点的存储单元物理地址PhysicalAddress：是数据在主存中的实际位置重定位、覆盖Overlaying、交换swapping的概念重定位：程序被换出到磁盘，下一次被换入时，不必放在以前的区域，而是可以重定位到内存的不同区域。覆盖：主存不足时，程序员使用覆盖（overlaying）技术来组织程序和数据，不同的模块被指派到主存中的同一区域，主程序负责在需要时换入或换出程序。固定分区FixedPartitioning和分页Paging的异同在系统生成阶段，主存被划分为许多静态分区。进程可以装入到大于或等于自身大小的分区中。优点：实现简单。缺点：有内部碎片，对内存使用不充分，活动进程的最大数目是固定的。简单分页：主存被划分成许多大小相等的帧；每个进程被划分成许多大小与帧相等的页；要装入一个进程，需要把进程包含的所有页都装入到主存内不一定连续的某些帧中优点：没有外部碎片缺点：有很少数量的内部碎片动态分区dynamicpartitioning和分段Segmentation的异同1.动态分区：分区是动态创建的，因而使得每个进程可以装入到与自身大小相等的分区中。优点：没有内部碎片缺点：由于需要压缩外部碎片，对内存的使用不充分2.简单分段：每个进程被划分成许多端；要装入一个进程，需要把进程包含的所有段都装入到主存内不一定连续的某些动态分区中。优点：没有内部碎片，相对于动态分区，提高了内存利用率，减少了开销。缺点：存在外部碎片：虚拟内存什么是命中率访问某个特定的存储器层时，CPU找到所需数据的百分比什么是系统抖动系统抖动（thrashing)：处理器大部分时间用于交换块，而不是执行指令。虚拟地址和实地址的概念虚地址指的是存在于虚拟内存中的地址，它有时候在磁盘中有时候在主存中。实地址指的是主存中的地址。取策略和清除策略的概念（预约式清除、请求式清除）读取策略确定一页何时取人主存，常用的两种方法：请求式分页（demandpaging）和预约式分页（prepaging)。请求式分页：只有当访问到某页中的一个单元时，才将该页取人主存。当进程第一次启动时，会出现一阵大量的页错误。预约式分页：读取的页并不是页错误请求的页，一次读取多个连续的页比隔一段时间读取一页更有效。清除策略确定何时将一个被修改过的页写会辅存。请求式清除：只有当一页被选择用于替换时才被写回辅存预约式清除：将这些被修改的多个页在需要用到它们所占据的页帧之前成批地写回辅存。页面替换调度算法、缺页次数、页面替换次数最佳（optimal，OPT）：替换下次访问距当前时间最长的页

2.最近最少使用（leastrecentlyused，LRU）：替换主存中上次使用距当前最远的页先进先出（FIFO）：替换驻留在主存中时间最长的页时钟（Clock）：给每一帧关联一个附加位，成为使用位。效率：OPT>LRU>Clock>FIFO分页系统、分段、分页分段结合的地址转换、TLB、页表、主存、磁盘地址转换，把图画出来并解释过程第九章调度（Scheduling）的标准，如何评价调度的好坏什么是抢占和非抢占（1）Nonpreemptive非抢占：一旦进程处于运行态，它就不断执行直到终止，或者在IO请求或系统调用时阻塞自己。（2）Preemptive抢占：当前正在运行的进程可能被操作系统中断，并转移到就绪态。周转时间Turnaroundtime、归一化周转时间Normalizedturnaroundtime、吞吐率Throughput、可预测性Predictability的概念周转时间：指一个进程从提交到完成之间的时间间隔，包括实际执行时间加上等待资源之间。归一化周转时间：作业的周转时间和与服务为其提供服务的服务时间之比。吞吐率：调度策略应该试图使得每个时间单位完成的进程数目达到最大。可预测性：无论系统非负载如何，一个给定的工作运行的总时间量和总代价是相同的。用户不希望响应时间或周转时间的变化太大。进程的调度，不同的调度算法（画图），计算周转时间，归一化周转时间1.先来先服务（FCFS）：选择在就绪队列中存在时间最长的进程运行。缺点：可能导致处理器和IO设备都没有得到充分利用2.轮转Round-Robin：基于时钟的抢占策略，以一个周期性间隔产生时钟中断，当中断发生时，当前正在运行的进程被置于就绪队列中，然后基于FCFS策略选择下一个。缺点：处理器中断、执行调度和分派函数都需要处理器开销。3.最短进程优先（SPN）：非抢占策略，原则是下一次选择所需处理时间最短的进程。缺点：长进程可能会饿死。4.最短剩余时间（SRT）：增加抢占机制，调度器总是选择预期剩余时间最短的进程。缺点：必须记录过去的服务时间，增加了开销5.HighestResponseRatioNext(HRRN最高响应比优先：长程、中程、短程调度的概念作用Long-TermScheduling长程调度：决定加入到待执行的进程池中Medium-TermScheduling中程调度：决定加入到部分或全部在主存中的进程集合中短程调度：决定哪一个可用进程将被处理器执行第十一章IO的三种模式（可编程IO、）可编程IOProgrammedI/O：处理器代表进程给IO模块发送一个IO命令，该进程进入忙等待，等待操作的完成，然后才可以继续执行中断驱动IOInterrupt-drivenI/O：处理器代表进程向IO模块发出一个IO命令，然后继续执行后续指令，当IO模块完成工作后，处理器被改模块中断。直接存储器访问（DMA）DirectMemoryAccess：一个DMA模块控制主存和IO模块之间的数据交换。为传送一块数据，处理器给DMA模块发请求，只有当整个数据块传送结束后，处理器才被中断。什么是IObuffer，作用是什么在输入请求发出前就开始执行输入传送，并且在输出请求发出一段时间之后才开始执行输出传送，这项技术叫缓冲。预输入，缓输出作用：避免不必要的开销和低效操作，提高系统性