操作系统经整理资料-个人终极版

第一章 操作系统引论 P33课后习题 9.OS有几大特征？其最基本的特征是什么？ 答：OS有四个基本特征：并发、共享、虚拟和异步。其中最基本的特征是并发。 并发性是指两个或多个事件在同一时间间隔内发生。 共享是指系统中的资源可供内存中多个并发执行的进程(线程)共同使用。 虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。 异步性是指进程以人们不可预知的速度向前推进。 12. 试在交互性，及时性和可靠性方面，将分时系统与实时系统进行比较. a. 分时系统是一种通用系统，主要用于运行终端用户程序，因而它具有较强的交互能力；而实时系统虽然也有交互能力，但其交互能力不及前。 b. 实时信息系统对实用性的要求与分时系统类似，都是以人所能接收的等待时间来确定；而实时控制系统的及时性则是以控制对象所要求的开始截止时间和完成截止时间来确定的，因此实时系统的及时性要高于分时系统的及时性。 c. 实时系统对系统的可靠性要求要比分时系统对系统的可靠性要求高 操作系统的五大功能： A．处理机管理功能。主要任务是：创建和撤销进程（线程），对诸进程线程的运行进行协调，实现进程（线程）之间的信息交换，以及按照一定的算法把处理机费配给进程（线程）。具有进程控制、进程同步、进程通信、调度功能。 B．存储管理功能。主要任务是：为多道程序的原型提供良好的环境，方便用户使用存储器，提高存储器的利用率以及能从逻辑上扩充内存。具有内存分配、内存保护、地址映射、内存扩充功能。 C．设备管理功能。主要任务是：完成用户进程提出的I/O请求；为用户进程分配器所需的I/O设备；提高CPU和I/O设备的利用率；提高I/O速度；方便用户使用I/O设备。具有缓冲管理、设备分配、设备处理功能。 D．文件管理功能。主要任务是：对用户文件和系统文件进行管理，方便用户使用，并保证文件的安全性。具有文件存储空间的管理、目录管理、文件的读/写管理和保护功能。 E．用户接口。包括命令接口、程序接口、图形接口。 微内核OS结构 特征及应用技术：足够小的内核、基于客户/服务器模式、应用“机制与策略分离“原理、采用面对对象技术。 基本功能：(1) 进程管理(2) 存储器管理(3) 进程通信管理(4) I/O设备管理。 优点：1）提高了系统的可扩展性，2）增强了系统的可靠性，3）可移植性，4）提供而来修分布式系统的支持，5）融入了面对对象技术。 第二章 进程管理 进程的特征与状态 1.进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。 2、结构特征：程序段、数据段和PCB（进程控制块） 具有动态性、并发性、独立性、异步性。 3.基本状态： 1) 就绪状态-等待分配CPU 2) 执行状态-占用CPU执行 3) 阻塞状态-停止执行，等待某个事件的发生 进程的三种基本状态及其转换 进程控制块 1.进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。 2.进程控制块中的信息： 1) 进程标识符-内部标识符、外部标识符 2) 处理机状态 处理机状态信息主要是由处理机的各种寄存器中的组成的。 3) 进程调度信息 4) 进程控制信息 3.进程控制块的组织方式 1) 链接方式 2) 索引方式 课后习题P68 6 试从动态性、并发性和独立性比较进程和程序。 答：动态性：进程是程序的一次执行过程，因此是动态的，动态性还现在进程由创建而产生、由调度而执行、由撤销而消亡，即有一定的生命周期。而程序只是一组指令的有序集合，可永久存储在某种介质上，其本身不具有运动的含义，因此是静态的。 并发性：引入进程的目的就是让多个进程实体可同时存储在内存中并发的执行。而程序（在没为它创建进程时）的并发执行具有不可再现性，因此程序不能正确的并发执行。 独立性：进程是一个独立运行、独立分配资源和独立接受调度的基本单位。而程序不具有PCB，所以不可能在多道程序环境下独立的运行。 18、同步机构应遵循哪些基本原则？ 答：(1) 空闲让进。(2) 忙则等待。 (3) 有限等待。 (4) 让权等待。 22、试写出相应的程序来描述图2－15所示的前趋图。 Var a,b,c,d,e,f,g,h:semaphore:=0,0,0,0,0,0,0,0; Begin Parbegin Begin S1;signal(a);signal(b);end; Begin wait(a);S2;signal(c);signal(d);end; Begin wait(b); S3;signal(e);end; Begin wait(c);S4;signal(f);end; Begin wait(d);S5;signal(g);end; Begin wait(e);S6;signal(h);end; Begin wait(f);wait(g);wait(h);S7;end; Parend; end Var a,b,c,d,e,f,g,h,i,j:semaphore:=0,0,0,0,0,0,0,0,0,0; Begin Parbegin Begin S1;signal(a);signal(b);end; Begin wait(a);S2;signal(c);signal(d);end; Begin wait(b); S3;signal(e); signal(f);end; Begin wait(c);S4;signal(g);end; Begin wait(d);S5;signal(h);end; Begin wait(e);S6;signal(i);end; Begin wait(f);S7;signal(j);end; Begin wait(g);wait(h);wait(i); wait(j);S8;end; Parend; end 26、试修改下面生产者－消费者问题解法中的错误 producer: consumer: begin begin repeat repeat …… wait(mutex)； produce an item in nextp; wait(empty); wait(mutex); nextc:=buffer(out); wait(full); out:=out+1;(out:=(out+1)mod n; buffer(in):=nextp; signal(mutex); signal(mutex); consume item in nextc; until false; unti false; end end 36、为什么要在OS中引入线程？ 答：由于进程是资源的拥有者，所以在创建、撤销、切换操作中需要较大的时空开销，限制了并发程度的进一步提高。为减少进程切换的开销，把进程作为资源分配单位和调度单位这两个属性分开处理，即进程还是作为资源分配的基本单位，但是不作为调度的基本单位（很少调度或切换），把调度执行与切换的责任交给“线程”。这样做的好处不但可以提高系统的并发度，还能适应新的对称多处理机（SMP）环境的运行，充分发挥其性能。 第三章 处理机调度与死锁 调度算法 先来先服务（FCFS）调度算法 适用于作业调度，进程调度（非抢占方式）。 调度方法：后备作业队列、就绪队列按FIFO排列，调度时选择处于队首的作业或进程。 优点：简单、易于实现。 缺点：1）有利于长的作业或进程，不利于短的。 2）有利于CPU繁忙型的作业或进程，不利于I/O繁忙型的作业或进程。 短作业(进程)优先调度算法 既适用于作业调度，又适用于进程调度。 调度方法：从后备作业队列、就绪队列中选择估计运行时间最短的作业或进程。既可用于非抢占方式，也可用于抢占方式。 优点：调度性能较好，系统吞吐量高。 缺点：1）不利于长的作业或进程。 2）不考虑作业或进程的紧迫程度。 3）估计运行时间很难准确获得。 高优先权优先调度算法 既适用于作业调度，又适用于进程调度。 调度方法： 选择具有最高优先权的后备作业或就绪进程。既可用于非抢占方式，也可用于抢占方式。 优点： 既照顾了作业到来的先后，又考虑了要求服务时间的长短，是FCFS和SJF的很好的折衷。 缺点：算法较为复杂；每次调度时，均要重新计算响应比。 时间片轮转法 仅适用于进程调度（抢占方式），主要为分时系统设计。 调度方法： 就绪队列按FIFO排列，调度时选择队首进程。但该进程占用CPU至多执行一个时间片，便放弃CPU。 关键：时间片大小的确定 太大：退化为FCFS 太小：系统效率降低 特点：假设所有进程都是同等重要的。 例如，有5个批处理的作业A，B，C，D，E几乎同时到达一个计算中心，估计的运行时间分另为2，4，6，8，10min，它们的优先权分别为1，2，3，4，5（5为最高优先级）。请用下面的调度算法，分别计算作业的平均周转时间（忽略作业的切换开销）： （1）时间片轮转（时间片为2min） （2）最短作业优先 解：（1）时间片轮转，各作业的执行结束时间分别为2，12，20，26，30，平均周转时间为： T＝（2＋12＋20＋26＋30）/5＝18min （2）最短作业优先，各作业的执行结束时间分别为2，6，12，20，30，平均周转时间为： T＝（2＋6＋12＋20＋30）/5＝14min 课后习题P68 6 试比较FCFS和SPF两种进程调度算法。 答：先来先服务（FCFS）调度算法,适用于作业调度，进程调度（非抢占方式）。其调度方法是后备作业队列、就绪队列按FIFO排列，调度时选择处于队首的作业或进程。优点是简单、易于实现。缺点有：1）有利于长的作业或进程，不利于短的。2）有利于CPU繁忙型的作业或进程，不利于I/O繁忙型的作业或进程。 短作业(进程)优先调度算法,既适用于作业调度，又适用于进程调度。调度方法是从后备作业队列、就绪队列中选择估计运行时间最短的作业或进程。既可用于非抢占方式，也可用于抢占方式。优点是调度性能较好，系统吞吐量高。缺点有：1）不利于长的作业或进程。2）不考虑作业或进程的紧迫程度。3）估计运行时间很难准确获得。 16 何谓死锁?产生死锁的原因和必要条件是什么? 答：死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。 产生死锁的原因：（1）竞争资源。（2) 进程间推进顺序非法。 产生死锁的必要条件：（1）互斥条件；(2) 请求和保持条件；(3) 不剥夺条件；(4) 环路等待条件。 【1.处理死锁的基本方法 预防死锁-通过破除死锁的四个必要条件之一，来防止死锁产生。 避免死锁-仔细地对资源进行动态分配，以避免死锁发生。 与解除死锁-检测系统中是否出现死锁，若出现则解除掉。 2.死锁的检测 (1)保存有关资源的请求和分配信息;(资源分配图) (2)提供算法检测系统是否进入死锁状态;(死锁定理) 死锁的解除 (1) 剥夺资源——从其他进程剥夺足够数量的资源给死锁进程。 (2) 撤消进程——使全部死锁进程都夭折；按某种顺序逐个的撤销进程，直到有足够资源可用，消除死锁状态为止。】 20 在银行家算法中,若出现下述资源分配情况: Process Allocation Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 试问: (1)该状态是否安全? (2)若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它? 解：⑴该状态是安全的，因为存在一个安全序列< P0P3P4P1P2>。下表为该时刻的安全序列表。 资源情况 进程 Work Need Allocation Work+Allocation Finish P0 P3 P4 P1 P2 1 6 2 2 1 6 5 4 1 9 8 7 1 9 9 11 2 9 9 11 0 0 1 2 0 6 5 2 0 6 5 6 1 7 5 0 2 3 5 6 0 0 3 2 0 3 3 3 0 0 1 4 1 0 0 0 1 3 5 4 1 6 5 4 1 9 8 7 1 9 9 11 2 9 9 11 3 12 14 17 true true true true true ⑵若进程P2提出请求Request(1，2，2，2)后，系统不能将资源分配给它，若分配给进程P2，系统还剩的资源情况为（0，4，0，0），此时系统中的资源将无法满足任何一个进程的资源请求，从而导致系统进入不安全状态，容易引起死锁的发生。 第四章 存储器管理 1、基本分页存储管理方式（课件） 基本分段存储管理方式（课件） 如果离散分配的基本单位是页，则称为分页式存储管理； 如果离散分配的基本单位是段，则称为分段式存储管理。 分页和分段的主要区别： (1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。 分段的目的是为了能更好地满足用户的需要。 (2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定， 决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。 (3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名， 又需给出段内地址。 2、页面置换算法 1）最佳置换算法-淘汰未来最长时间不再被访问的页面 其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但无法实现。 缺页率表示“缺页次数 / 内存访问次数”(比率) 2）先进先出(FIFO)页面置换算法-淘汰最先进入内存的页面，即选择在内存中驻留时间 Belady现象：随着分配的主存块数的增加，缺页次数不但没有降低，反而增加了。 原因：该算法没考虑进程实际的运行规律，因为在进程中，有些页面经常被访问，比如全局变量，常用函数，循环语句段等。 3）最近最久未使用(LRU)置换算法——淘汰最近最久没有使用的页面 4）Clock置换算法 5）最少使用(LFU)置换算法 6）页面缓冲算法(PBA) 例如，执行如下访问页号序列后： 1，2，3，4，，1，2，5，1，2，3，4，5 （1）采用先进先出（FIFO）淘汰算法，缺页次数是多少？ （2）采用最近最少使用（LRU）淘汰算法，缺页次数是多少？ （3）若用优化（OPT）算法呢？ 解：（1）先进先出（FIFO）淘汰算法，缺页次数是9次。 1 2 3 4 1 2 5 1 2 3 4 5 3 1 2 3 4 1 2 5 5 5 3 4 4 1 2 3 4 1 2 2 2 5 3 3 1 2 3 4 1 1 1 2 5 5 √ √ √ √ √ √ √ √ √ （2）采用最近最少使用（LRU）淘汰算法，缺页次数是10次。 1 2 3 4 1 2 5 1 2 3 4 5 3 1 2 3 4 1 2 5 1 2 3 4 5 1 2 3 4 1 2 5 1 2 3 4 1 2 3 4 1 2 5 1 2 3 √ √ √ √ √ √ √ √ √ √ （3）优化（OPT）算法，缺页次数是7次。 1 2 3 4 1 2 5 1 2 3 4 5 3 1 1 1 1 1 1 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 4 4 3 4 4 4 5 5 5 5 5 5 √ √ √ √ √ √ √ 3、“抖动”问题 当给进程分配的内存小于所要求的工作集时，由于内存外存之间交换频繁，访问外存时间和输入输出处理时间大大增加，反而造成CPU因等待数据空转，使得整个系统性能大大下降，这就是系统“抖动”问题。 第五章 设备管理 1、I/O控制方式 1）程序I/O方式 2）中断方式 3）DMA方式 4）通道方式 1）程序I/O方式评价 优点:实现简单，控制简单，基本不需额外硬件支持。 缺点:使CPU将大量的时间花费在循环等待上，使CPU效率发挥极差，外设也不能合理利用，整个系统的效率很低。 2）中断驱动I/O控制方式 优点:在外设进行数据处理时，CPU不必等待，可以继续执行该程序或其他程序。支持多道程序和设备并行操作。 缺点:CPU每次处理的数据量少（通常不超过几个字节,由数据寄存器的大小而定），只适于数据传输率较低的设备。设备速度过高的话容易造成中断次数激增导致数据丢失。 3）直接存储器访问DMA I/O控制方式 特点： ① 数据传输的基本单位是数据块； ② 所传送的数据是从设备直接送入内存的，或者相反； ③ 仅在传送数据块的开始和结束时，才需CPU干预，整块数据的传送是在DMA控制器的控制下完成的。 DMA方式的局限性 （1）DMA方式如果一次需要读多个数据块则需要CPU进行多次中断处理。 （2）多个DMA控制器的同时使用会引起内存地址的冲突并使得控制过程进一步复杂。 4）I/O通道控制方式 I/O通道方式是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读(或写)为单位的干预，减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预，同时又可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。 2、磁盘调度 磁盘调度的目标，是使磁盘的平均寻道时间最少（即平均寻道长度最短）。 假设当前系统有磁头正在100磁道，并且某时刻依次提交如下磁道访问请求：55，58，39，18，90，160，150，38，184，请各种不同调度策略下的平均寻道长度。 先来先服务FCFS 最短寻道时间优先SSTF 扫描(SCAN)算法（电梯调度算法） 循环扫描(CSCAN)算法 第六章 文件管理 文件管理的功能是构建一个文件系统，负责管理外存上的文件，提供文件的存取、共享和保护，方便用户使用文件。 1、数据项：基本数据项，组合数据项 记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。 关键字是唯一标识一个记录的数据项。 文件是指由创建者所定义的、具有文件名的一组相关元素的集合。最大的数据单位。 文件的属性可以包括： (1) 文件类型(2) 文件长度 (3) 文件的物理位置(4) 文件的建立时间。 按用途分类 （1）系统文件(2) 用户文件(3) 库文件 按文件中数据的形式分类 （1）源文件(2) 目标文件(3) 可执行文件 按存取控制属性分类 （1）只执行文件(2) 只读文件(3) 读写文件 文件系统的接口 （1）命令接口(2) 程序接口 2、目录管理 对目录管理的要求如下： (1) 实现“按名存取”。 (2) 提高对目录的检索速度。 (3) 文件共享。 (4) 允许文件重名 （1）文件控制块 基本信息类 ① 文件名 ； ② 文件物理位置 ； ③ 文件逻辑结构 ；④ 文件的物理结构 （2）索引结点 查找是按文件名，因此将文件名和文件描述信息分开，分别放在目录项和索引结点中，检索时，只将目录项调入内存，找到后，将该项中的索引结点调入即可。 单级目录 优点是简单且能实现目录管理的基本功能——按名存取，但却存在下述一些缺点：(1) 查找速度慢 (2) 不允许重名 (3) 不便于实现文件共享 两级目录 优点：（1）提高了检索目录的速度 (2) 在不同的用户目录中， 可以使用相同的文件名。 (3) 不同用户还可使用不同的文件名来访问系统中的同一个共享文件 缺点：增加了系统开销。 多级目录结构 相对路径名——从当前目录开始直到数据文件为止所构成的路径名 绝对路径名——从树根开始的路径名称为绝对路径名 算法设计题 1.设公共汽车上，司机和售票员的活动分别是： 司机 售票员 启动车辆 上乘客 正常行车 关车门 到站停车 售票 开车门 下乘客 在汽车不断地到站，停车，行驶过程中，这两个活动有什么同步关系？并用信号灯的P，V操作实现它的同步。 解：设两个信号量stop和run，初值为0，并假设汽车的初始状态为停滞不前状态， 司机：begin 售票员：begin L1：P（run） L2：上乘客 启动车辆 关车门 正常行车 V（run） 到站停车 售票 V（stop） P（stop） Goto L1 开车门 End 下乘客 Goto L2 End 2.桌上有一只盘子，每次只能放入一只水果，爸爸专向盘中放苹果（apple），妈妈专向盘中放桔子（orange），一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子中的苹果。只要盘子空则爸爸或妈妈可向盘中入一只水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出。把爸爸、妈妈、儿子、女儿看做四个进程，用P、V操作进程管理使这四个进程能正确地并发执。 解：设s表示允许向盘子存放水果的信号量，初值为1；sp和so表示盘中是否有苹果或桔子的信号量，初值为0。 爸爸：begin 妈妈：begin 儿子：begin 女儿：begin L1：P（s）； L2：P（s）； L3：P（so）； L4：p（sp）； 放苹果； 放桔子； 拿桔子； 拿苹果； V（sp）； V（so）； V（s）； V（s） Goto L1； Goto L2； 吃桔子； 吃苹果； End； End； Goto L3； Goto L4； End； End � EMBED Unknown ��� wait(full); wait(empty); in:=(in+1)mod n; signal(empty); signal(full); PAGE 1 _1324976073.vsd 就绪 阻塞 执行 时间片完 进程调度 I/O完成 I/O请求