操作系统管理tmp.doc

操作系统复习提纲注：每个知识点后面括号里标明了这个知识点的起始页，并不是说仅仅只看这一页，因为有些知识点可能不只一页，大家在复习时应注意。第一次课程1. CPU的构成与基本工作方式（P18）处理器由运算器、控制器、一系列的寄存器以及高速缓存构成运算器实现指令中的算术和逻辑运算，是计算机计算的核心控制器负责控制程序运行的流程，寄存器是指令在CPU内部作处理的过程中暂存数据、地址以及指令信息的存储设备，在计算机的存储系统中它具有最快的访问速度高速缓存处于CPU和物理内存之间，一般由控制器中的内存管理单元（MMU：Memory Management Unit）管理，访问速度快于内存，低于寄存器利用程序局部性原理使得高速指令处理和低速内存访问得以匹配，从而提高CPU的效率2. 存储器的类型（P37）两类存储器：读写型的存储器和只 读型的存储器 PROM和EPROM3. 存储器的层次结构（P39）存储系统设计三个问题：容量、速 度和成本容量大，每比特价格越低，同时存取速度也越慢解决方案：采用层次化的存储体系结构当沿着层次下降时每比特的价格将下降，容量将增大速度将变慢，处理器的访问频率也将下降4. 缓冲技术（P55）缓冲区是硬件设备之间进行数据传输时，用来暂存数据的一个存储区域缓冲技术三种用途:处理器与主存储器之间处理器和其它外部设备之间设备与设备之间的通信目的：解决部件之间速度不匹配的问题5. 中断的概念（P62）操作系统就是由中断驱动的，中断是实现多道程序的必要条件， 定义：CPU对系统发生的某个事件作出的一种反应，CPU暂停正在执行的程序，保留现场后自动转去执行相应事件的处理程序，处理完成后返回断点，继续执行被打断的程序第二次课程1. 操作系统的定义（P10）操作系统是计算机系统中的一个系统软件是一些程序模块的集合它们能以尽量有效合理方式组织和管理计算机的软硬件资源，合理的组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能，使整个计算机系统能高效的运行。2. 操作系统的特征（P12）并发 共享 随机性3. 历史上的操作系统，以及各个阶段的特点（P20） 随历史线索，本节介绍一些重要的操作系统真空管时代(1946年-1955年)晶体管时代(1955年-1965年)集成电路时代(1965年-1980年)大规模集成电路时代(1980年-至今1、真空管时代:用户独占全机：不出现资源被其他用户占用，资源利用率低；CPU等待用户：计算前，手工装入纸带或卡片；计算完成后，手工卸取纸带或卡片；CPU利用率低。2、22222221 2222222 22222 2. 晶体管时代:利用磁带把若干个作业分类编成作业执行序列，每个批作业由一个专门的监督程序（Monitor）自动依次处理。可使用汇编语言开发。出现批处理操作系统， 这些操作系统由监控程序，特权指令，存储保护和简单的批处理构成；引入了I/O 处理机概念3、出现分时系统,多道程序和SPOOLING技术,第三代计算机实质是批处理系统,小型计算机，电子游戏和UNIX的成功4. 批处理操作系统特点多道和成批处理第三次课程1. 操作系统的设计阶段（P11）功能设计,算法设计,结构设计2. 操作系统的构件内核（P15）程序加载器和 调试器，被设计到机器核心当中，或者固化 在只读存储器里3. 操作系统的构件进程（P40）4. 操作系统的构件线程（P42）第四次课程1. 顺序程序（P7）指令或语句序列，体现了某种算法，所有程序 是顺序的2. 并发程序（P9）在一定时间内物理机器上有两个或两个以上的 程序同处于开始运行但尚未结束的状态，并且 次序不是事先确定的3. 多道程序设计（P15）多道程序设计是指允许多个程序同时进入内存并运行4. 多道程序系统的特点（P18）并行性,制约性,动态性5. 进程基本概念（P21）计算机中的所有程序（软件），按照某种顺序运行，这种运行的过程称之为进程。进程是某个程序在某个数据集合上的运行过程，它有程序、输入、输出和状态。在分时操作系统中，单个CPU被若干进程共享，它使用某种调度算法决定何时停止一个进程的运行，转而为其他进程提供服务。6. 进程同程序的差别（P24）进程是程序的执行，属于动态，程序是静态 的。进程的存在是暂时的，程序的存在是永久的。进程程序数据PCB 一个程序可以对应多个进程一个进程可以包含多个程序7. 进程的状态和转换（P33）运行态：正在占用CPU运行程序阻塞态：等待外部事件发生，无法占用CPU就绪态：可运行，但其他进程正在占用CPU，所有被暂时挂起o运行态变为就绪态强制终止某进程的运行（系统原因）o运行态变为阻塞态运行进程等待外部事件发生（自身原因）o阻塞态变为就绪态外部事件已经发生，可准备运行o就绪态变为运行态停止其他进程运行后，运行该进程占用CPU问题1：为什么不能从阻塞态变为运行态呢 ？问题2：为什么不能从就绪态变为阻塞态呢 ？答案：三种状态的变换体现了OS的资源管理作用进程的核心思想在于运行棗CPU资源的分配8. 进程上下文组成（P52） 进程上下文由进程的用户地址空间内 容、硬件寄存器内容及与该进程相关的核心 数据结构组成。用户级上下文,系统级上下文：寄存器上下文：第五次课程1. 线程的概念（P9） 一个进程内的基本调度单位2. 多线程环境中进程的定义（P19）3. 线程的特性（P22）4. 进程和线程的比较（P27） o进程：资源分配单位（存储器、文件）和CPU调度（分派）单位。又称为任务(task)o线程：作为CPU调度单位，而进程只作为其他资源分配单位。n只拥有必不可少的资源，如：线程状态、寄存器上下文和栈n同样具有就绪、阻塞和执行三种基本状态与进程相对应，线程与资源分配无关，它属于某一个进程，并与进程内的其他线程一起共享进程的资源。再者，当进程发生调度时，不同的进程拥有不同的虚拟地址空间，而同一进程内的不同线程共享同一地址空间，o地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享某进程内的线程在其他进程不可见，o通信：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信需要进程同步和互斥手段的辅助，以保证数据的一致性，o调度：线程上下文切换比进程上下文切换要快得多；o线程只由相关堆栈（系统栈或用户栈）寄存器和线程控制表TCB组成。寄存器可被用来存储线程内的局部变量，但不能存储其他线程的相关变量。o发生进程切换与发生线程切换时相比较：n进程切换时将涉及到有关资源指针的保存以及地址空间的变化等问题。n线程切换时，由于同一进程内的线程共享资源和地址空间，将不涉及资源信息的保存和地址变化问题，从而减少了操作系统的开销时间。o进程的调度与切换都是由操作系统内核完成o而线程则既可由操作系统内核完成，也可由用户程序进行。5. 线程的状态（P39）第六次课程1. 顺序程序设计定义（P5）2. 程序的并发执行的定义（P13）3. 进程间的联系（P16）4. 进程执行的并发性的本质(P14)5. 临界区的定义（P49）6. 互斥的定义（P51）7. 临界区调度原则（P55） n有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入n无空等待：不允许两个以上的进程同时进入互斥区n多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待n有限等待：任何进入互斥区的要求应在有限的时间内得到满足n让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权第七次课程1. 经典问题：生产者消费者问题（P21）2. 简单的睡眠唤醒方法：生产者消费者问题的解法（P42）3. 生产者消费者信号量解法（P49） o互斥关系分析n任何时刻，只能有一个进程在缓冲区中操作n引入互斥信号量（二元信号量）n信号量为0，表明已有进程进入临界区；o同步关系分析n对于“生产者”而言，缓冲区满则应等待n引入同步信号量“empty”，为0表示缓冲区满n对于“消费者”而言，缓冲区空则应等待n引入同步信号量“full”，为0表示缓冲区空define N 100typedef int semphsemph mutex = 1;semph empty = N;semph full = 0;思考1：mutex和empty两个信号量之间有什么区别吗？思考2：多信号量的操作顺序有要求吗？Producer进程int item;While(TRUE)Produce-Item(&item);down(&empty);down(&mutex);Enter-item(item);up(&mutex);up(&full);Comsumer进程int item;While(TRUE)down(&full);down(&mutex);Remove-item(&item)up(&mutex);up(&empty);Consume-item(item);4. 读者写者问题的信号量解法（P54）5. 死锁的定义（P90）6. 形成死锁的四个必要条件（P92）第八次课程1. 计算机的存储体系回顾(P8)2. 内存管理的目的（P13）3. 重定位的概念（P41）4. 分区存储管理的原理（P64）5. 动态分区的概念以及优缺点（P73）第九次课程1. 各种分区分配算法的概念（P4）2. 分区存储管理的主要优缺点(平26)3. 覆盖技术的概念（P34）4. 抖动的概念（P94）第十次课程1. 段式管理的基本思想（P7）2. 局部性原理的概念（P55）3. 虚拟存储器的基本思想（P71）4. 引入虚拟存储技术的好处（P77）第十一次课程1. 衡量调度策略的常用指标（P5）周转时间：是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。吞吐率：是指在给定的时间内，一个计算机系统所完成的总工作量。响应时间：是指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。设备利用率：主要指输入输出设备的使用情况。2. 处理机调度4个级别的概念（P11）3. 作业生命周期状态（P32）4. 各种调度算法的具体调度过程（P61） 1. 先来先服务（FCFS）调度算法例如，三个作业同时到达系统并立即进入调度：作业名 所需CPU时间作业1 28作业2 9作业3 3采用FCFS算法，三个作业的周转时间分别为：28、37和40，因此，平均作业周转时间T = (28+37+40)/3 = 35； 2、轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例，轮转法的基本概念是将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾 3. 多级反馈轮转法，当一个进程在执行完它的时间片之后，或从睡眠中被唤醒以及被创建之后，将进入不同的就绪队列； 4、优先级法，确定优先级的方法可分为：静态法、动态法； 5. 最短作业优先法（shortest job first），最短作业优先法（SJF）就是选择那些估计需要执行时间最短的作业投入执行，为它们创建进程和分配资源。 例如，四个作业同时到达系统并立即进入调度： 作业名 所需CPU时间 作业1 9 作业2 4 作业3 10 作业4 8假设系统中没有其他作业，现实施SJF调度算法，SJF的作业调度顺序为作业2、4、1、3，平均作业周转时间：T = (4+12+21+31)/4 = 17平均带权作业周转时间W=(4/4+12/8+21/9+31/10)/4 = 1.98SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业，例：假如四个就绪作业其到达系统和所需CPU时间如下： 作业名 到达系统时间 CPU时间(毫秒)- Job1 0 8 Job2 1 4 Job3 2 9 Job4 3 5Job1从0开始执行，就绪队列仅一个作业。Job2在时间1到达，Job1剩余时间（7毫秒）大于JOB2所需时间（4毫秒），Job1被剥夺，Job2被调度执行。平均等待时间是（10-1）+（1-1）+（17-2）+（5-3）/4=26/4=6.5毫秒。采用非抢占式SJF调度，那么，平均等待时间是7.75毫秒。 6、最高响应比优先法（HRN）是对FCFS方式和SJF 方式的一种综合平衡。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。作业进入系统后的等待时间与估计运行时间之比称作响应比R。定义如下：R=(W+T)/T=1+W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间 例如，以下四个作业先后到达系统进入调度： 作业名 到达时间 所需CPU时间 作业1 0 20 作业2 5 15 作业3 1 5 作业4 15 10假设实施SJF：SJF的作业调度顺序为作业1、3、4、2，平均作业周转时间T = (20+15+20+45)/4 = 25平均带权作业周转时间W = (20/20+15/5+25/10+45/15)/4 =2.25假设实施FCFS：如果对它们施行FCFS调度算法，平均作业周转时间T = (20+30+30+35)/4 = 38.75平均带权作业周转时间W = (20/20+30/15+30/5+35/10)/4 = 3.13对作业流执行HRRF调度算法：开始只有作业1，被选中执行时间20；作业1执行完毕，响应比依次为1+15/15、1+10/5、1+5/10，作业3被选中，执行时间5；作业3执行完毕，响应比依次为1+20/15、1+10/10，作业2被选中，执行时间15；作业2执行完毕，作业4被选中，执行时间10；平均作业周转时间T = (20+15+35+35)/4 = 26.25平均带权作业周转时间W = (20/20+15/5+35/15+35/10)/4 = 2.42 第十二次课程1. 请求页式管理中的置换算法中的FIFO算法，P35的例子（P35） 下面的例子可以用来说明FIFO算法的正常换页情况和Belady现象。例: 设进程P共有8页，且已在内存中分配有3个页面，程序访问内存的顺序(访问串)为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。这里，这些自然数代表进程P所建的程序和数据的页号。内存中有关进程P所建的程序和数据的各页面变化情况如图所示。 由图可以看出，进程在一个执行过程中，实际上发生了12次缺页。如果设缺页率为缺页次数与访问串的访问次数之比，则该例中的缺页率为12/17=70.5%。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1777222244400000000000333222221111111100033333222如果给进程P分配4个页面，则在其执行过程中内存页面的变化情况如图所示。进程P在拥有4个内存页面时，共发生9次缺页，其缺页率为9/17=52.9% 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 177777333333333222000000444444444411111111000000022222222221111以上是使用FIFO算法正常换页时的例子。下面来看看另外一种访问串时的情况。设进程P可分为5页，访问串为1，2，3，4，1，2，5，1，2，3，4，5。当进程P分得3个页面时，执行过程中内存页面变化如图所示。1 2 3 4 1 2 5 1 2 3 4 5111444555555222111113333332222244由上图可知，进程P在执行过程中共缺页9次，其缺页率为9/12=75%。但是，如果为进程P分配4个内存页面