操作系统第三版,课后答案.doc

多道批处理系统：把多个作业同时放入内存，当某个作业因某种原因运行不下去时，系统就转向下一作业运行。特点：1.多个作业同时存在于内存。 2.作业完成顺序与进入顺序无关。 3.作业由系统程序调入内存。分时系统：作业直接进入内存。不允许一个作业长期占有CPU. 多个用户分时使用主机，每一用户分得一个时间片，用完这个时间片后操作系统将处理机分给另一用户，如此循环，每一用户可以周期性地获得CPU使用权，这样每一用户都有一种独占CPU的感觉。 分时系统的特征：多路性、独立性、及时性、交互性。程序的并发执行是指：若干个程序同时在系统中执行，这些程序的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。进程的定义：可并发执行的程序段，在某个数据集合上的一次执行过程。n 进程是程序的一次执行。n 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。n 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 进程与程序的区别与联系：1.进程是动态的概念，程序是静态的概念；进程离开程序就失去了意义。2.程序可永久保存，而进程具有短暂生命周期。3.一个程序可对应于多个进程；4.进程更能真实地描述并发，而程序不能。进程的状态及其转化 ：1.运行：该进程已占有了处理机，其程序正在执行。2.就绪：该进程已准备好，占有了执行所需的除处理机之外的所有资源和条件。3.阻塞：该进程正在等待系统中某事件发生（例如I/O操作的完成）。进程的物理结构：两部分：进程控制块（PCB），进程体（程序部分， 数据部分）PCB:为系统提供控制、管理进程信息的数据结构，是进程在系统中存在的唯一标识。 一个用户进程其实体存在于内存用户工作区。其PCB存放于内存操作系统工作区。PCB内容：进程标识符，处理机状态，进程调度信息，进程控制信息。PCB的组织方式：链接方式，索引方式。资源分配原则：子进程只能占有父进程所拥有的资源，撤消进程时，子孙进程全部随之撤消。进程控制：就是对系统中的所有进程运行实施控制，进程控制一般由原语来实现。内核：通常将一些与硬件密切相关的模块以及运行频率较高的模块放入靠近硬件的软件层次中，常驻内存，并加以特殊保护，称为内核。是硬件的首次延伸。 原语：由若干条机器指令构成，用以完成特定功能的一段程序，执行期间要保证其不可分割性。进程制约：间接制约 由进程相互竞争资源而引起的进程间制约关系。直接制约 由进程相互合作而引起的进程间制约关系。 临界资源： 每次仅允许一个进程使用的资源 临界区：使用临界资源的那段程序。同步机制应遵循的准则：n 空闲让进n 忙则等待n 有限等待n 让权等待计数信号量（S)物理含义： S值0（=n): 表示有n个空闲资源可用； S值=0,则本进程继续。否则该进程被封锁，插入到该信号量的等待队列。V(S) V操作 (1) S值加1； (2) S值0,则本进程继续。否则从该信号量的等待队列中移出一进程插入到就绪队列，本进程继续。进程：是拥有资源的独立单位，是抢占处理机的调度单位。耗费资源较为严重。线程：是进程的一个实体。是被系统独立调度的一个单位。不拥有资源，但可和同一进程的其它线程共享该进程资源。作业调度（高级调度）：决定将在外存上处于后备状态的作业调入内存运行。一般用于批处理系统。进程调度（低级调度）：决定就绪队列中哪个进程获得处理机。中级调度：将暂时不能运行的进程调出内存，以提高系统处理能力。进程调度与作业调度的区别：（1）作业调度决定谁进入内存或获得虚拟处理机，进程调度决定哪个进程获得物理处理机。对于单机多道系统低级调度每次选择一个进程，高级调度每次选择若干个作业。（2）进程调度方式：a.优先占有方式；b.优先剥夺方式。与调度算法与性能有关的术语：1.周转时间 从作业提交到作业完成所用的时间。2.响应时间 从请求信号输入开始到首次响应（显示结果）所用的时间。3.CPU-I/O执行期 一个进程运行期间，CPU 忙和I/O忙的时间。调度算法与方式的选择原则1、面向用户的原则（1） 周转时间短（2） 响应时间快（3） 截止时间保证（4） 优先权原则2、面向系统原则（1）系统吞吐量高（2）处理机利用率高（3）各类资源的平衡利用调度算法：1.先来先服务算法（FCFS)2.短作业（进程）优先算法（SJ(P)F)3.最高优先数第一算法（FPF)4.时间片轮转5.响应比高者优先6.反馈队列算法（低级）死锁产生的原因和必要条件： 1 .原因 （1）系统资源不足 （2）进程推进顺序不当 2.必要条件 （1）互斥条件 （2）请求与保持条件 （3）不剥夺条件 （4）环路条件死锁的对策：1.运行前的预防 （1）预分配所有所需资源 （2）可剥夺资源 （3）按序分配资源2.运行时的避免进程申请资源时，再检查满足其要求时是否安全，安全才分配。死锁定理：当且仅当进程-资源图为不可完全化简时，死锁发生。死锁检测：允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生，一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行检测时机： 当进程等待时检测死锁 （其缺点是系统的开销大） 定时检测 系统资源利用率下降时检测死锁存储管理的目的与功能：存储分配，存储保护，提高内存使用率，内存扩充重定位：逻辑地址转换为物理地址的过程重定位类型： 静态重定位：由重定位装入程序在作业装入时完成。优点：不需要硬件的支持。 缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动。动态重定位：是在程序执行的过程中，每次访问内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的硬件机构来完成的。 优点：（1）程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。（2）一个程序不一定要求占用一个连续的内存空间。（3）可以部分地装入程序运行。（4）便于多个进程共享同一个程序的代码。缺点：（1）需要硬件的支持。（2）实现存储管理的软件算法较为复杂。分区式管理：把整个内存划分为若干区域，操作系统占用一个区域，其它区域供系统中的多个作业共享，这种方法称为分区存储管理。一、 固定式分区：基本思想：系统事先将内存划分为若干大小固定的区域，每个区域可放一道用户作业，运行中区域长度不变。这些内存区域称为分区。管理：系统通过分区说明表进行。 分区说明表内容：分区号、分区大小、分区首址、分区状态优点：实现多道，实现方法简单缺点：空间浪费多，资源利用率很低二、可变式分区1.基本思想：系统在作业提出内存申请时再根据用户请求划分内存分区大小和位置。并使分区的大小刚好与作业的大小相等。2.管理：（1）空白分区说明表 已分配分区说明表 （2）分区链表 空白分区链表 已分配分区链表3空闲区管理算法：（1）首次适应算法（2）最佳适应算法（3）最差适应算法（4）循环首次适应算法三、可重定位分区分配基本思想：在可变式分区分配的基础上，定期或周期性的“紧缩”内存空间。紧缩非常浪费处理机时间.紧缩时机：作业申请内存，且无空白分区可满足要求，但空白分区总长度满足要求时。优点：内存利用率极高。缺点：浪费时间页式存储管理：一、基本思想：1.把作业地址空间分成一些大小相等的片，称为页；同样把存储空间也分成大小相同的片，称为块。2.页面保持逻辑上的连续性（从0开始编制页号，页内地址是相对于0编址），但是所对应的块则不一定连续。3.系统为每个作业设置一张页表以建立作业块-页之间的映射关系二、地址结构地址结构：页式存储管理采用一维地址结构，既地址空间为一连续的线性空间系统在进行地址转换时将逻辑地址划分为页号和页内位移两部分。三、页表1.作用：建立起连续的地址空间与作业所占不连续的存储空间的映射。系统为每个进程建立一个页表，页表的长度和首地址存放在该进程的进程控制块（PCB）中。主要优缺点1.避开紧缩过程，解决了碎片问题。2.页式地址变换，增加成本，降低速度。3.作业运行必须全部装入主存。4 .不易实现共享，不便于动态连接。段式存储管理：一、实现原理1.分段地址空间：按程序自身的逻辑关系划分为若干个程序段，一个段可以定义为一组逻辑信息。每个作业的地址空间由若干个段组成，每个段都是一个具有名字的从“0”开始的连续地址空间。v 段式逻辑地址为二维地址。 名空间段地址格式：段名|访问入口代号v 经编译装配后形成分段系统的逻辑地址结构2.内存划分：内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放3.地址空间与物理空间的映射由段表实现。段表基本内容：段号，段长，内存始址，存取控制，辅存地址等项。二、地址转换关键是将二维的逻辑地址转换为一维的物理地址。三、快表同页地址变换一样，在段地址变换过程中，也有两次访问内存的问题。为了加快访问内存的速度也可采用快速存储器组成快表。四、段的共享 多个作业共享一个段时，内存中只需一个副本。不同作业的不同段号对应同一地址。 共享要求必须是可重入程序。可重入程序：允许多个进程同时访问的代码。共享代码必须完全相同。分段与分页区别：v 段是依据程序的逻辑结构划分的，页是按内存线性空间物理划分的。v 段式技术中程序地址空间是二维的，分页技术中程序地址空间是一维的。v 段是面向用户的，页对用户而言是透明的。v 段长由用户决定，且各段的大小一般不相等，唯一的限制是最大长度。而页长是由系统决定的，各页的长度必须相等。v 段的共享比页的共享更容易，段可实现动态链接。段页式存储管理：基本思想 1.用段式存储管理的基本思想管理地址空间，用页式存储管理的基本思想管理存储空间。地址空间按段式划分（对用户来讲，按段的逻辑关系进行划分）。存储空间按页式存储管理方案（对系统，按页划分每一段）。内存分配以页为单位进行分配。 2.二维地址结构。分段表与页表两级实现地址转换。段表：每一段的页表始址和页表长度页表：逻辑页号与内存块号的对应关系虚拟存储技术：利用软件方法从逻辑上扩充内存的手段。以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术一、依据：局部性原理：程序在执行时，在一较短的时间内，执行仅限于某个部分，其所访问的存储空间也局限于某个区域。主要有时间局部性和空间局部性。二、定义： 利用内外存信息的调入调出功能，把作业的一部分调入内存即可运行，从而实现在逻辑上对内存进行扩充的系统。三、特征：v 1、离散性v 2、多次性v 3、对换性v 4、虚拟性请求页式存储管理：一、基本思想：在页式管理的基础上，不需把作业全部地址空间放入内存，而只把当前所需的放入内存。1.增加页表信息内容中断位：该页是否在主存。修改位：本次在内存期间是否修改过。访问位：本次在内存期间是否访问过。辅存地址2.缺页故障处理当需访问某页时，首先查找页表中断位，看该页是否在内存，如在直接访问，不在则产生缺页信号，处理机执行缺页中断处理程序，将该页调入主存，然后继续执行。页面淘汰：为调入新页面，需将内存中某一页从内存移出。抖动：信息在内、外存之间的频繁移进移出现象。二、页面分配1、根据语言及程序的特点确定最小块数。2、分配与置换策略 固定分配局部置换 可变分配全局置换 可变分配局部置换3、分配算法 平均分配 按比例分配 考虑优先权分配三、页面淘汰算法1.最佳策略（OPT)思想：从内存中移出再也不会用的页面，或最长时间不需访问的页面。2.FIFO算法 （1）思想：把在主存中驻留时间最长的一页淘汰。（2）缺点：Belady异常。即：当分配给进程的物理页面数增加时，缺页次数反而增加。某些常用页面会因在内存时间长而淘汰。3.最近最久未用算法（LRU）思想：选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。缺点：修改记录开销太大。4.LRU近似算法 思想：定期或周期修改访问位，选择未访问页面淘汰。 缺点：周期T难定。四、影响缺页次数的因素(1) 分配给进程的物理块数(2) 页本身的大小(3) 程序的编制方法(4) 页淘汰算法五、主要优缺点优：1.具备了页式管理的全部优点。 2.提供了大量虚存。 3.更有效利用内存。缺：1.系统开销增大。 2.防止抖动，增加了系统复杂性。设备分类：1、 按传输速率分：高速设备、中速设、低速设备；2、 按信息交换的单位分：字符设备、块设备；3、 按资源管理方式分类独占型设备：在任一段时间内最多有一个进程占用它，字符设备及磁带机属独占型设备。即临界资源。共享型设备：多个进程对它的访问可以交叉进行，除磁带机外的块设备属共享设备虚拟设备：在一类设备上模拟另一类设备，常用共享设备模拟独占设备，用高速设备模拟低速设备，被模拟的设备称为虚拟设备二、设备管理基本功能 1. 监视所有设备状态 2.设备分配 3.实现实际的I/O操作（ I/O控制） 4.实现其他功能通道类型：v 字节多路通道v 数组选择通道v 数组多路通道瓶颈：由于设备间处理速度不均衡，而造成的信息在某些设备处的积压现象。在主机I/O系统结构中由于是单通路方式，一个高速控制设备带多个低速I/O设备，因此易在通道处出现瓶颈现象。 解决方法：1.多重通路 2.缓冲技术缓冲：用来匹配不同速度设备之间速度差距的装置。缓冲可分为：单缓冲、双缓冲、多缓冲、缓冲池；DMA控制方式：控制器功能更强，除有中断功能外，还有一个DMA控制机构。在DMA控制器的控制下，设备同主存之间可成批交换数据，不用CPU干预I/O控制方式：一、程序I/O方式二、中断控制方式三、DMA控制方式四、通道控制方式数据结构：系统为每一个设备、控制器、通道都配置了一张控制表，用来记录对这些设备进行管理和控制所需的信息。设备控制表(DCT)：DCB结构包括设备名、设备类型、设备状态、指向控制器的指针、等待队列的指针控制器控制表（COCT)通道控制表(CHCT)系统设备表(SDT)：整个系统一张资源信号量设备分配机制：1.设备的固有属性 独占设备、共享设备、虚拟设备2.分配算法 先来先服务、优先权高者优先3.安全性 单请求方式、多请求方式4.与设备无关性 为了提高系统的可适应性和可扩展性，将物理设备与逻辑设备区分，用户程序只涉及逻辑设备，由系统分配物理设备。通路寻找：设备-控制器-通道磁盘分为两种：软盘与硬盘硬盘又分为两种：固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高移动头磁盘：一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低物理地址形式：磁头号（盘面号）、磁道号（柱面号）、扇区号寻道时间Ts：磁头从当前位置移动到指定磁道所经历的时间。 Ts=磁盘机启动时间+m 磁头移动距离磁盘调四、通道控制方式一、程序I/O方式二、中断控制方式三、DMA控制方式数据结构设备控制表(DCT)队列的指针控制器控制表（COCT)通道控制表(CHCT)系统设备表(SDT)资源信号量设备分配机制：1.设备的固有属性2.分配算法3.安全性4.与设备无关性通路寻找度算法：(1) 先来先服务（FCFS) ：按访问请求到达的先后次序服务 优点：简单，公平；缺点：效率不高，相临两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利（2) 最短寻道时间优先(SSTF) ：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先优点：改善了磁盘平均服务时间；缺点：1.造成某些访问请求长期等待得不到服务2.效率上仍然存在问题(3) 扫描算法（电梯算法、SCAN）：克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向(4)循环扫描算法(C-SCAN)文件：一个具有符号名字的一组相关联元素的有序集合。文件分类：v 按性质分：系统文件、库文件、用户文件v 按保护分：只读文件、读写文件、执行文件、不保护文件v 按信息流向：输入文件、输出文件、输入输出文件v 按保留方式分：临时文件、永久文件、档案文件文件系统：是指一个负责存取和管理文件信息的软件机构。文件的逻辑组织:文件呈现在用户面前的组织方式。用户将按这种形式去存取、检索和加工文件。分为有结构文件（定长记录、不定长记录）、无结构文件一、顺序文件：一系列记录按某种顺序排列所形成的文件。1、顺序存取方法；2、直接存取方法二、索引文件：对于不定长记录，可采用一个映射表（索引表）建立记录号与逻辑地址的映射从而进行直接访问。索引表：索引号、记录长度、逻辑位置。三、索引顺序存取方法程序设计时更经常的访问并不是根据记录号，而是根据某个属性值。这时索引表就应该按照：主属性-逻辑地址 形式构造。文件在物理存储器上的组织形式： 逻辑记录 物理记录 逻辑块 物理块文件存储器通常都是以块为单位分配，并以块为单位传送。每个块称为一个物理记录。一个逻辑记录可占多个物理记录，一个物理记录也可包含多个逻辑记录。文件在逻辑上都可看作是连续的，但在物理介质上存放时则有多种形式。1.连续分配原理：把一个文件逻辑上连续的信息，存放在相邻的物理块中，即文件的物理记录是连续的。文件控制块中记录：文件首物理块号，文件长度。优点：结构简单，存取速度快。缺点：文件不能动态增加；存在块外碎片。2.链接分配原理：把一个文件的物理记录散布在文件存储器中，块中设立指针，指向下一物理记录。文件控制块中记录：文件首物理块号显式链接 隐式链接 优点：文件可动态增长。缺点：只适宜顺序存储；存放连接字破坏了物理块的完整性。3.索引分配原理：把一个文件的物理记录散布在文件存储器中，为每个文件建立一个索引表以建立起逻辑块号和物理块号的映射。文件控制块中记录：索引表地址。优点：文件可动态增长；可方便的进行随机存取。缺点：增加了索引表的空间开销。4.哈希分配原理：把一个文件的物理记录散布在文件存储器中，构造哈希函数，把键值映射为物理块号。优点：文件可动态增长；可方便的进行随机存取。缺点：增加了计算及冲突处理的开销。一、文件控制块（FCB)：文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息。文件控制块是文件存在的标志。内容：