中国科大操作系统复习题解.docx

OS 复习题解姓名：时中 严哲 杜昇第1章 操作系统引论1. 什么是 冯诺依曼计算机工作模型？冯诺依曼计算机工作模型或存储程序工作模型:1) 存储器用来容纳程序和数据；2) 程序由指令组成，并和数据一起存储在计算机内存中;3) 指令按顺序、转跳和循环三种基本方式组织;4) 机器一起动，就能按照程序指定的逻辑顺序把指令从存储器中读出来逐条解释执行，自动完成程序所描述的处理工作;5) 指令指针（CS:IP）指示当前执行指令，执行完成指针会自动调整到下一条指令;6) 当前指令指针指向的内存中程序，被认为拥有机器控制权;7) 任何计算机都拥有自己的一套基本指令系统，高级语言程序最终需经专门的编译程序，翻译为基本机器指令;2. 简述OS的定义、作用和主要功能。1) 定义：是计算机系统的一个系统软件；a) 是一些具有如下功能的程序模块的集合；b) 能有效地组织和管理计算机硬件和软件资源c) 能合理组织计算机的工作流程，控制程序的执行；d) 能透明地向用户提供各种服务功能，使用户能够灵活、方便地使用计算机，使整个 计算机系统能高效地运行。 2）操作系统的作用 a) 作为计算机系统资源的管理者；b) 作为用户与计算机硬件系统之间的接口；c) 用作扩充计算机硬件系统；3）操作系统的功能：处理机管理（进程与线程管理）：主要任务是对内存进行分配、保护和扩充；具体是：a) 进程控制：负责进行的创建、撤销和状态转换b) 进程同步：对并发执行的多进程进行协调c) 进程通信：负责完成进程间的信息交换d) 进程调度：按一定的算法进行CPU分配存储管理：主要任务是对内存进行分配、保护和扩充；具体为：a) 内存分配：按一定的策略为每道程序分配内存b) 内存保护：保证各程序在自己的内存区域内运行不受其它并发执行程序影响。c) 内存扩充：为允许大型作业或多作业并发运行，必须借助虚拟存储技术来获得更大“虚拟”内存设备管理：是OS中最庞杂、最琐碎部分；具体为：a) 设备分配：按一定原则对设备进行分配。为使设备能与主机并行工作，需大量采用缓冲技术和虚拟技术b) 设备传输控制：实现物理设备的I/O操作，包括启动、中断处理和结束处理等操作。文件管理：OS中负责信息管理部分称为文件系统；a) 文件的存储空间管理（分配、回收）b) 目录管理：目录是为方便文件管理而采用的基本数据结构，它能提供“按名存取”功能。c) 文件操作管理：实现文件的基本操作，包括打开、关闭、读、写等。d) 文件保护：提供文件安全保护的有关功能和设施。3. 比较：单道批处理OS、多道批处理OS、分时OS和实时OS的基本特征。单道批处理OS:单道批处理系统l 监督程序l 驻留内存；l 自动加载外部作业，实现系统的自动、不间断连续运行l 但当当前执行程序有I/O服务请求时，CPU仍要空闲特征：自动性、顺序性和单道性 多道批处理OS：多道批处理系统多道程序设计技术 l 用户提交作业先在外存排队，然后由作业调度程序按一定的算法从队列中选择若干作业载入内存，并允许它们并发（交替）执行;l 引入多道程序设计技术后，可带来如下的好处; l 提高系统(CPU、内存和I/O设备)的利用率;l 充分发挥CPU与外设并行工作的能力;l 提高系统的吞吐率 ;l 特征：多道性、无序性和调度性l 优缺点及需要解决的问题 分时OS:分时操作系统形成和发展的动力 :l 实现人机交互；共享或充分利用主机；便于用户上机 分时OS实现要解决的关键问题 :l 及时接受l 多路卡；每个终端配备可暂存用户命令的缓冲区l 及时处理l 所有用户作业要直接进入内存；l 每个用户（作业）应在较短的时间内得到响应处理的“时间片”； 分时系统的实现方法 l 单道分时处理系统 l 具有“前台”和“后台”的分时系统 l 支持多道程序设计的分时系统 特征 ：l 多路性、独立性和交互性；实时OS：实时OS的引入目的（主要应用领域） 1)实时控制 l 实时信息处理要求对信息进行及时处理 2)实时任务的类型l 按是否有周期性划分；l 按截止时间要求严格与否划分（硬、软任务）；3)实时系统的基本特征 l 具有多路性、独立性、交互性、及时性和可靠性等特征. 补充题：试从交互性、及时性和可靠性方面，将分时系统与实时系统进行比较。分时系统和实时系统在交互性、及时性和可靠性方面存在较大差别：（1）从交互性方面来看，分时系统的目的是满足多用户交互的血药，因此，交互性是分时系统的一个关键问题，用户可以通过终端与系统进行人机对话。而实时系统中的交互性仅限于访问系统中的某些专用服务程序，其交互性受到了限制。（2）从及时性方面来看，在分时系统中它指的是系统的响应时间是以人能够接受的等待时间为标准的，一般为2-3秒；而在实时系统中则是以控制过程或信息处理中能够接受的延迟为准，往往是秒级、百毫秒级甚至毫秒级或更低，是实时系统的关键因素之一。（3）从可靠性方面来看，在实时系统中的人任何差错都可能带来巨大的损失，为此，往往需要采取多级容错措施来保证系统和数据的安全可靠。分时系统也有可靠性要求但相对较低。4. 简述目前研究/学习OS的两种主要观点（虚拟观点和资源管理观点）。1) 虚拟观点：l 是对OS一种由顶向下的俯视。l 装有OS的计算机极大地扩展了原有计算机的功能。把包含由各种硬件、复杂底层操作细节隐藏起来，使得用户的操作和使用，由复杂变得简单，由低级操作变为高级操作，把基本功能扩展为多种功能。l 在裸机上装上OS后，对用户来说好像是得到了一个扩展的，使用更方便的计算机。2) 资源观点：l 是目前对OS描述的主要观点，是一种对OS功能位置由底向上的观察的观点。l 把资源分为软、硬件资源，硬件资源又包括CPU,主存、输入输出设备。相应的OS就有处理机管理、内存管理、设备管理，和针对软信息资源文件的磁盘管理/文件管理5. 为什么说OS极大扩展了计算机的功能？装有OS的计算机极大地扩展了原有计算机的功能，原因如下：OS把包含由各种硬件、复杂底层操作细节隐藏起来，使得用户的操作和使用，由复杂变得简单，由低级操作变为高级操作，把基本功能扩展为多种功能。在裸机上装上OS后，对用户来说好像是得到了一个扩展的，使用更方便的计算机。第2章 进程的描述与控制1. 针对：1）单任务OS环境下程序顺序执行，2）多任务OS环境下的多道程序并发执行，试分析它们分别具有哪些特征？为什么？1）单任务OS环境下程序顺序执行:单任务环境下的“可执行”程序n 未执行前的程序是可执行格式的二进制程序文件，通常被持久存储在外存（磁盘）中；n 程序被加载到主存并获得CPU控制权后,将按其中指令所规定的逻辑顺序被依次执行；逻辑顺序结构：顺序、选择、重复（循环）n 通常可采用或引入前驱图节点有向边，来描述程序中不同单元或程序段之间的关系；n 以实模式执行，具有最大的权限，可存取控制所有计算机软硬资源；程序执行具有以下基本特点：n 顺序性n 封闭性n （结果）可再现性。2）多任务OS环境下的多道程序并发执行:多道程序并发执行情况示例本例中，程序片段S1与S2可并发执行并发可有效提高系统的吞吐量多道程序并发执行的特征：n 间断性（切换执行）n 失去封闭性（共享系统的资源）n 结果不可再现性为有效管理和调度多道并发执行程序须引入可完整描述每道执行中程序的数据结构，该思想逐步进化完善进程(process)概念。2. 深入理解进程的概念，试说明进程的基本特征及现代OS中引入进程的意义。提示：进程是现代OS最重要的概念之一，是为了能有效管理（正在被并发执行的）每道程序而必须引入的特别概念，或特别数据结构。进程的基本特征：用户空间是进程的一个最主要特征!n 独立性：每个进程具有自己相对独立的地址空间，除非通过进程通信手段，否则不能相互影响n 结构性进程空间是结构化的、分段组织的；n 动态性是或包含可在其地址空间中活动的执行体对象n 并发性，也称异步性在同一个计算机系统中允许同时存在多个进程，微观上它们可能是交替执行；但宏观上看，则似乎在同时独立运行。操作系统引入进程的意义：n 进程是现代OS最重要的概念之一n 进程的管理、切换及调度，与保护模式密切相关，需要有保护模式知识，才能清晰理解进程的实现机制和实现过程。n 执行进程切换的相关代码，被统称为OS的进程调度模块1）通常被运行在比 “进程”更高的层级上；2）现代OS的调度代码，通常不是一个集中的模块，而是由分散在内核多个位置的若干代码片段构成；3. 在引入进程的OS中，进程与（二进制可执行）程序这两个概念的区别与联系。进程与程序的区别：l 程序是静态的, 是有序代码的集合, 是进程的定义和说明对应着一个持久外存文件，具有外存文件的性质（创建/复制/删除.)。l 进程是动态的、暂时的，是程序的一次执行，通常不能在计算机之间迁移。l 进程与程序的组成不同：进程组成包括代码段、数据段和控制块。l 多进程实体可以同时存放在内存中并发执行，而程序不能正确并发执行。l 进程是一个能够独立运行、独立分配资源的和独立接受调度的基本单位。而程序不能在多道程序环境下独立运行。l 进程与程序不是意义对应的关系。进程与程序密切关联：l 通过多次加载执行，一个程序可对应多个进程；通过调用关系，一个进程可涉及多个程序。4. 理解PCB数据结构中的主要属性域及作用。一个已被挂起的进程，它的PCB是否会被交换到外存？ PCB被保存在系统空间可交换区、系统空间不可交换区，还是进程用户空间？1）PCB数据结构的主要属性域及作用：PCB是操作系统内核中一种数据结构，主要表示进程状态，是在系统空间不可交换区中。PCB主要内容：l 进程描述信息:PID,NAME, USERID,PROCESS GROUP；l 处理器现场保护信息: CPU内部各寄存器；l 进程控制信息:当前状态、优先级、代码执行入口地址、程序外存地址、运行统计信息(执行时间、调度次数、页面调度)；l 资源占用信息列表，打开资源对象句柄表；l 用于进程间同步与通信的相关信息字段；l 指向进程虚空间使用分配描述表指针（PCB-AddressSpace )； （注意，因页目录/页表占空间 较大，虽位于系统空间但不能安排在核心，即PCB，页挂起进程页表可能会被SWAP到外存！)PCB的主要作用：l 与进程有关的信息被集中存储在这个数据结构中，它将程序变成了可并发执行的进程。2）一个已经被挂起的进程，它的PCB会被SWAP交换到外存。5. 什么是进程的运行、就绪、阻塞和挂起状态？试描述进程的五状态、七状态转移变化图。1）进程的状态：运行状态：一个进程已得到CPU，其程序正在CPU上执行；就绪状态：进程已获得除CPU以外的所有必要资源，只要得到CPU便可立即执行；阻塞状态：正在执行的进程因为某种事件（如I/O请求）的发生二暂时无法继续执行，只有等相应的事件完成后才能去竞争CPU；挂起状态：其实质是使进程不能继续执行，及时挂起后的进程处于就绪状态，它也不能参与CPU的竞争。2）进程的五状态转移变化图：3）进程的七状态转移变化图：单挂起：双挂起：6. 请描述实现进程创建和进程结束的内部基本处理流程。进程创建的基本过程： 申请空白PCB（创建内核进程对象） 为新进程分配资源 创建进程地址空间框架； 创建进程打开对象句柄表； 加载并映射新进程映像到进程用户空间，包括分配部分物理内存页； 在进程用户空间中分配进程运行环境控制块(PEB)； 初始化进程PCB和PEB 将新进程状态置为“就绪”，并插入就绪队列。进程的终止/退出（EXIT() 根据被终止进程标识，从PCB队列中检索出该进程PCB，从中读出进程状态； 若被终止进程处于执行状态，应立即中止该进程的执行 修改该进程的状态到终止状态，并立即申请再调度； 若还有子孙进程，还应将它们终止或过继； 释放进程拥有的所有资源； 释放PCB7. 请说明进程与线程的区别与联系。线程拥有独立的用户空间吗？线程可以参与资源分配吗？1）进程与线程的区别与联系：a) 地址空间：不同进程的地址空间相互独立，而同一进程的各线程共享同一地址空间，一个进程中的线程在另一进程中是不可见的。b) 通信关系：进程间通信必须通过OS提供的进程间通信机制，而同一进程的线程间通信可以通过直接读写进程数据段如全局变量进行（仍需要同步互斥机制保证数据访问的一致性）。c) 调度切换：同一进程中的线程上下文切换比进程上下文切换快得多。d) 线程与进程相比的主要优点:n 创建、终止、切换快，系统开销少；n 通信方便n 由于同进程内线程间共享内存和文件资源，故可直接进行不通过内核的通信；n 系统允许的最大线程数限制弱得多；e) 采用多线程的程序设计技术，可以更好提高系统的运行性能（如吞吐量、计算速度和响应时间等）。2）线程没有独立的用户空间，同一进程的多个线程位于同一用户空间：线程在用户空间的相关数据结构n 有自己专有堆栈；n 有自己的运行上下文；n 有自己的线程环境块TEB以及内核数据结构TCBPEB在用户空间的位置是固定的，PEB下方就是TEB，进程中有几个线程就有几个TEB，每个TEB占一个4KB的页面。 3）线程不可以参与资源分配：n 一个进程内可容纳多个线程。进程仍作为参与资源分配的最基本单位，但把线程作为调度的最基本单位，从而达到以小的开销来提高进程内的并发和共享程度的目的。8. 请说明windows系统中与线程描述有关的数据结构，以及线程创建的基本过程。线程的相关数据结构：n 线程的内核数据结构（代表对象）：是ETHREAD，是一种调度对象，它的第一个成份是数据结构KTHREAD，也称为TCB ；n 线程在用户空间的相关数据结构：l 有自己专有堆栈；l 有自己的运行上下文；l 有自己的线程环境块TEB；（PEB在用户空间的位置是固定的，PEB下方就是TEB，进程中有几个线程就有几个TEB，每个TEB占一个4KB的页面。 ）线程的创建：一般首个线程在进程创建的结束阶段被自动创建（由父进程代为创建）；其它线程由进程自己调用系统API函数创建。线程创建的基本过程：n 创建/初始化ETHREAD数据结构，并处理好与EPROCESS的关系。n 为新线程分配堆栈、创建并初始化执行上下文。n 在所属进程的用户空间中，创建并设置新线程TEB。n 进一步设置目标线程的KTHREAD数据结构，包括：n 设定新线程在用户空间执行入口始址。ETHREAD数据结构中有相关成份，用来存放相关地址。n 将其上下文中的断点(返回点)设置成指向内核中的一段程序KiThreadStartup，使得该线程一旦被调度运行时就从这里开始执行。n 将线程对象标插入就绪队列第3章 存储管理1. 说明存储管理的主要功能和目标。内存分配与回收：为每个进程创建执行空间，分配初始所需基本内存，并允许进程在执行中动态申请/释放内存；实现有效的存储保护与共享；主存扩充（扩充主存的大小）引入虚拟存储技术，用外存扩充主存数量，弥补物理内存数量的不足；提高主存的利用率采用合理得当的算法、策略和数据结构；提高计算机资源利用率的根本途径是采用多道程序设计技术，实现并发共享。2. 若采用首次适应策略和FBC进行空闲分区管理的动态分区分配描述算法。若将首次适应策略改为最坏适应策略、最佳适应策略或循环首次适应策略，该如何修改算法？一种典型的动态分区分配算法/采用首次适应算法和FBC结构long get_block(int x, byte * p) /请求大小为X int i; long y; i=1; while ( FBCi.size!=0 & FBCi.size=delt) FBCi.size= y; FBCi.addr= FBCi.addr+x; return x; 最坏适应策略:此处有错，循环结束条件欠妥，最后应该给FBC赋值long get_block(int x, byte * p) /请求大小为X int i,j,max; long y; i=1;j=1; while ( FBCi.size!=0 & FBCi.size=x) availj+=FBCi;i+; min=avail1;for(i=1;i=max)max=availj; if (avali.size =0) p=null; return 0 ; p=availi.addr; y=availi.size-x; if (y=delt) availi.size= y; availi.addr= availi.addr+x; return x; 最佳适应策略: 此处有错，循环结束条件欠妥，最后应该给FBC赋值（懒得改了）long get_block(int x, byte * p) /请求大小为X int i,j,min; long y; i=1;j=1; while ( FBCi.size!=0 & FBCi.size=x) availj+=FBCi;i+; min=avail1;for(i=1;ij;i+)if(availi=delt) availi.size= y; availi.addr= availi.addr+x; return x; 循环首次适应策略:int i ,flag=0; /全局变量long get_block(int x, byte * p) /请求大小为X long y;if(flag=0) i=1;flag=1; while ( FBCi.size!=0 & FBCi.size=delt) FBCi.size= y; FBCi.addr= FBCi.addr+x; return x; 3. 归纳总结页式存储分配与管理的基本特点。页式分配管理的基本思想：n 进程使用线性逻辑地址LA(32位、一维、连续)n OS透明地将线性地址分页，n 即将32位地址划分为两段:p=LA/页大小;d=LA-P*页大小n OS透明地将物理内存也按页大小(4k)划分一系列的页框(frame)，并进行依次编号n OS通过页映射表（页表），将进程地址空间的所有逻辑页，分别映射加载到不同的、不必连续的物理页框中。n 页式分配的特点：l 优点：内存分配适应性更强；没有外碎片；每个进程浪费空间不超过1个页。l 缺点：仍要求程序一次性地全部装入内存。4. 试描述带有快表的页式地址变换机制。由于页表是存放在内存中的，CPU每存取一条指令或一个数据，都要两次访问内存，第一次访问内存中的页表，以得到指令或数据所在页对应的内存块号；第二次才可以根据物理地址存取指令或数据，这使得计算机的处理速度降低了近1/2。为了提高存取速度，可在地址变换机构中增设一个具有并行查找能力的高速缓冲寄存器，又称为“联想寄存器”或“快表”，用以存放当前被频繁访问的页面的也好和对应的页表项。在进行地址转换时，地址变换机构自动将逻辑地址中的页号并行地与快表中的所有也好进行比较，若其中有与此相匹配的页号，便可以直接从快表中读出该页对应的物理块号，并送到物理地址寄存器中。如果在快表中未找到对应的页号，则仍需访问内存中的页表来进行地址转换，同时还必须将得到的页表项与页号一起装入到快表中，若快表已满，则还需根据置换算法淘汰某个快表项，已装入新内容。由于成本的关系，快表通常做得较小。5. 试描述引入目录页的、具有两级页表的页式地址变换机制。针对难以找到大的连续内存空间以存放页表的问题，可利用将页表进行分页的办法，使每个页面的大小与内存物理块的大小相同，离散地存放在不同的物理块中，并为之建立一张页表（外层页表Outer Page Table）。以32位逻辑地址空间为例，家丁页面大小为4kB，若采用1级页表结构，须具有20位页号占1M；在采用两级页表结构时，再对页表进行分页，使每个页表中包含210个页表项，此时逻辑地址结构如下：3122 2112 110P1P2d外层页号外层页内地址页内地址6. 说明段式分配管理的基本数据结构，以及段式系统的地址变换机制。段式分配与管理的基本思想（地址变换机制）：l 按程序中的自然分段特性来划分逻辑空间，形成二维地址空间。例如，序中主程序、子程序、静态变量、堆栈等，都是基于段的。l 逻辑地址形式: (段号s,段内位移d)；低级语言程序中用户可直接给出该形式地址，高级语言程序在编译后也可得到这种形式地址。l 程序加载时，OS为所有的段分配所需内存，每个段被分配在一个连续分区；但进程中的各个段可离散分配到主存的不同分区；l 在为每个段分配物理内存时，采用动态分区管理方法。段式分配管理的相关数据结构l 进程用户空间段描述表段长 | 属性 | 起始逻辑地址|段表项索引号 l 进程段表 (Segment Table,ST)每个进程一张（套），被放置在系统空间l 段长|段属性(保护码)|段基址进程局部描述符表(Local Descriptor Table, LDT)描述可变分区的空闲段表（FBT或FBC）用户空间中的一个逻辑段加载/映射需借助：FBT或FBC7. 什么是局部性原理？试说明虚拟存储管理实现的基本思想、技术优势和特征。1）局部性原理：l 程序在执行过程中的一个较短时期，所执行的指令地址和操作数地址，将局限于一定区域内。l 程序执行活动具有：时间局部性和空间局部性。2）虚拟存储管理实现的基本思想：n 程序装入时,不必将其全部读入内存，只需将当前执行需要的部分页(或段)装入内存，就可让程序开始执行。n 在程序执行过程中，如需访问尚未在内存的逻辑地址单元(缺页或缺段)，则OS通过相应机制将所缺页(段)装入内存-消除缺页(段)故障。n 另一方面，OS还将暂时不用的页(段)调出内存，以腾出更多的可用内存空间。n 从用户的角度看，系统好象提供了比实际内存更大的存储容量这种虚拟扩展的存储体系，常被称为“虚拟存储器”3）技术优势：n 能给用户提供大于实际物理内存的虚拟存储器，允许在较小内存中执行较大进程，并可在有限主存中容纳更多的并发进程。n 与覆盖技术相比，虚拟存储实现对用户透明，不影响用户编程结构，用户可在高达232的虚空间编制程序。4）特征：n 离散性；多次性；对换性；虚拟性；5）实现方式：请求分页；请求分段；请求段页式；8. 与页式系统相比，请求分页系统的页表项扩展了哪些信息域？请简要说明它们的作用。请求分页的虚存系统需对页式系统进行如下几方面的扩充：l 对页表的页表项(PTE)进行扩展，增加一些必要的管理标志位（它们占用PTE原先恒为0的低位段，故并不需要扩大PTE的大小）。 (不需增加新的硬件或设施)l 增加可有效处理缺页(故障) 的相关设施和机制(硬件)l 增强页面调度管理能力（软件扩展）l 选用合适的页面调入策略、页面置换策略和页面置换算法；l 增强对系统及各进程驻留页面集，即“工作集”的有效管理，降低系统缺页率，提高系统性能。(软件扩展)l 支持自动选取/设定工作集大小，及动态维护、修剪工作集。l 增加对物理页框的管理，以支持更有效的页面调度和工作集管理 (软件扩展)l 增加页框状态描述数据库，该库可直接存储在相关页框中。9. 在请求分页系统中，页故障中断有何特点？请描述这类系统的缺页故障处理机制。缺页中断是一种比较特殊的中断，体现在：a) 在指令执行期间产生和处理缺页中断b) 常规外部中断，是在每条指令执行完毕后，检查是否有中断请求到达。c) 一条指令可能产生多次中断。d) 当从中断处理程序返回时，能正确执行原先产生缺页故障的指令。故障处理的基本过程：n 当发生缺页故障时，OS会向外存(页文件或页映射文件)发出读操作调入相关页面；n 页面调入I/O操作是同步的，即线程会进入睡眠等待直到I/O完成（等待事件到来）被唤醒。n 对同一进程的多个线程(并发)，若遇到同位置缺页故障，可串接到同一等待事件中.n 页面调入I/O代码也必须能识别处理调入完成后，相关页表项的情况变换。10.在请求分页系统中，若内存分配有固定/可变两种，置换有全局/局部置换两种，那么，基于分配与置换的组合，可得到哪几种页面置换策略？共有四种，分别为：固定内存分配，全局置换策略：采用该策略是，为进程分配的物理块数目在进程的整个生命周期都固定不变，若进程因调入页面而需要换出某个页面，可以从全局进行置换。虽然比固定内存的局部置换好一些，但是固定的内存限制了整个置换的效果。可变内存分配，全局置换策略：采用该策略时，系统先为每个进程分配一定数目的物理块，当进程发生缺页时，若系统中有空闲的物理块，则为其分配一个物理块并装入缺页；若系统中已没有空闲的物理块，则为其分配一个物理块并装入缺页；若系统中已没有空闲的物理块，则从内存中选择一页换出，再装入缺页，被换出的页可以是系统中任意进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。固定内存分配，局部置换策略：采用该策略是，为进程分配的物理块数目在进程的整个生命周期都固定不变，若进程因调入页面而需要换出某个页面，则只能患处他自己的内存页面。由于进程是动态的，即使在运行之前为它分配了适当数目的内存块，在采用固定分配局部置换策略时，进程在运行过程中仍然可能会因为内存块太少而频繁缺页，或者因为内存块太多而浪费空间。可变内存分配，局部置换策略：采用该策略时，为每个进程分配一定数目的物理块后，若某个进程发生缺页，则只能将自己的某个内存页换出，。如果进程在运行时频繁发生缺页中断，则系统需为该进程分配若干附加的物理块，直至其缺页率减少到适当程度为止；反之，若一个进程的缺页率特别低，则可以适当减少分配给它的物理块，但不应引起其缺页率的明显增加。因此，可变分配局部置换策略可以获得较高的内存空间利用率，同时又能保证每个进程有较低的缺页率。11.简要说明OPT、FIFO、LFU、LRU、CLOCK及改进CLOCK等置换算法的基本思想，若假设系统采用固定分配局部替换的页面调入策略，并假设某进程在创建时，分配到了3个页面框。试针对如下的该进程相关页面引用顺序；7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1分别计算采用OPT、FIFO和LRU三种算法时的缺页率。几种算法的基本思想：最佳算法(optimal, OPT)n 选择未来最长时间不使用页进行置换(最理想算法)；先进先出算法(FIFO)l 选择最先进入驻留集的页面进行置换；最不常用算法(Least Frequently Used, LFU) 选择到至今访问次数最少的页进行置换，要设置一个页面访问计数器。最近最久未使用算法(Least Recently Used, LRU) 选择内存中至今最久未使用页面进行置换；是局部性原理的合理近似，性能接近最佳，但硬件开销较大。时钟算法(clock)v 也称最近未用算法(Not Recently Used,NRU)，是LRU和FIFO的折衷。每页框有个使用位(use bit,ub)，若该页被访问ub=1。所有驻留页面组织为类似时钟的环形缓冲池，置换时采用一个类时钟指针，从当前指针位置开始顺时针搜索检查ub=0的页框，选择首个遇到的ub=0的页框进行置换。改进的时钟算法（结合访问位A和修改位M） 第一轮候选对象：A=0M=0，失败进入下一轮 第二轮候选对象：A=0M0， ，失败进入下一轮 第三轮，先将所有目标驻留页面框的A复位，再从满足A=0M0的候选页面框中，进行一轮选择。70120304230321201701FIFO缺页率15/20777001230422230001270011230423330111270122304230001222701LRU缺页率12/20777012230422033120170012030423032120170120304230321201701OPT缺页率9/20777222222222222227770000004440000000000111333333331111111第4章 进程的同步与通信（共享变量是否一定互斥使用）1. 了解多进程环境下资源的概念、分类和特性。概念：Any entity or any abstract machine component ,if it satisfies following charactics:(满足以下三个特征的任何实体或抽象的计算机元件：)(1) a process must request it from OS （进程需要从操作系统申请它）(2)the process must block its exeution until the entity is allocated to it （资源未分配给进程时，进程处于阻塞状态）(3)the coexisting process will compete for resources if they need resources （当互斥的进程需要资源时，进程之间处于竞争关系）分类：分类一：（1）可分配，用完要归还（可归还）（2）无需分配的抽象资源分类二：（1）可同时共享资源 （2）临界资源特性：有限性：2. 什么是临界区？请说明临界区的代码模式、同步原则。若不同进程访问相同临界资源R1，它们访问临界资源R1的代码一定相同吗？它们控制进入访问临界资源R1代码区的同步代码一定相同吗？临界区定义：每个进程中访问临界资源的那段代码称为临界区（Critical Section）（临界资源是一次仅允许一个进程使用的共享资源）或定义为： a segment of code ,that write a shard device（write a shared device，是写入操作，非读写操作）, which cannot be wxcuted while the other process are in the respond segment of code that acess to the same resources 代码模式: / 进入临界区 EnterCriticalSection(&g_cs); / 对共享资源进行写入(不是读写，)操作 / 离开临界区2. 什么是临界区？每个进程中访问临界资源的那段代码称为临界区（Critical Section）（临界资源是一次仅允许一个进程使用的共享资源）请说明临界区的代码模式、同步原则。 / 临界区结构对象 CRITICAL_SECTION g_cs; / 共享资源 char g_cArray10; UINT ThreadProc10(LPVOID pParam) / 进入临界区 EnterCriticalSection(&g_cs); / 对共享资源进行写入操作 for (int i = 0; i 10; i+) g_cArrayi = a; Sleep(1); / 离开临界区 LeaveCriticalSection(&g_cs); return 0; UINT ThreadProc11(LPVOID pParam) / 进入临界区 EnterCriticalSection(&g_cs); / 对共享资源进行写入操作 for (int i = 0; i 10; i+) g_cArray10 - i - 1 = b; Sleep(1); / 离开临界区 LeaveCriticalSection(&g_cs); return 0; void CSample08View:OnCriticalSection() / 初始化临界区 InitializeCriticalSection(&g_cs); / 启动线程 AfxBeginThread(ThreadProc10, NULL); AfxBeginThread(ThreadProc11, NULL); / 等待计算完毕 Sleep(300); / 报告计算结果 CString sResult = CString(g_cArray); AfxMessageBox(sResult); 进程进入临界区的调度原则是： 1、如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。 2、任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。 3、进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。 4、如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象若不同进程访问相同临界资源R1，它们访问临界资源R1的代码一定相同吗？不一定，例如相同的循环，可以采用i+或者使用i-它们控制进入访问临界资源R1代码区的同步代码一定相同吗？一定相同同步原则：忙碌等待（必须）：对已有进程进入临界区时，其他试图进入临界区的进程立即进入临界区。空闲则入（必须）：当没有进程处于临界区时，可以允许一个请求进入临界区的进程立即进入临界区。有限等待（锦上添花）：对要求访问临界资源的进程，应保证能在有限时间内进入临界区。让权等待（锦上添花）：当进程不能进入临界区时，应释放处理机。3. 请写出利用1）禁止中断结合共享标志变量；2）多个共享标志变量；3）硬件指令TS；4）硬件指令SWAP 等四种技术方案，实现临界区同步的算法，并分别举一例说明它们的应用方法。这些算法都是基于平等竞争的同步实现算法，它们能实现“有限等待”和“让权等待”这两条原则吗？1）禁止中断结合共享标志变量：Enter(lock)Disable interrupt();While(lock )Enable interrupt()Disable interrupt ()Lock=true;Enable interrupt()Exit (lock)Disable interrupt();Lock=false;Enable interrupt();2）多个共享标志变量：Boolean flagNWhile(1)Flagi=true;Turn=j;While(flagj=true& turn=j)null;Flagi=false;3）硬件指令TS:TS 功能描述：Boolean TS（boolean *lock）Boolean old;old=*lock;*lock=true;Return old;应用（算法描述）：Lock=false;While (TS(&lock);Lock=false;进程的其他代码；4）硬件指令SWAP功能描述：Swap(Boolean *a, boolean *b)Boolean temp;Temp=*a;*a=*b;*b=temp;应用（算法描述）Pi/Pj(线程)：有全局变量lock Pi : 有局部变量key例子：P1：While(1)key=true;While(key=true)Swap(&lock,&key)Lock=fa