存储管理习题PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2013OS复习,1,处理机管理具有哪些功能?它们的主要任务是什么?,内存管理有哪些主要功能?它们的主要任务是什么?,设备管理有哪些主要功能?其主要任务是什么?,文件管理有哪些主要功能?其主要任务是什么?,2,从资源管理的角度出发，简述操作系统的功能。,操作系统的主要功能包括处理机管理、存储管理、设备管理、文件管理和用户接口。,处理机管理（即进程管理）,在多道程序环境下，处理机的分配和运行都是以进程为基本单位的，对处理机的管理可归纳为对进程的管理，它包括进程控制、进程调度、进程同步和进程通信。,存储管理,存储管理的功能是为多道程序的运行提供良好的环境，方便用户使用存储器，并提高存储器的利用率，它主要包括地址重定位、存储分配、存储保护和存储扩充。,设备管理,计算机系统硬件除了CPU和主存，其余几乎都属于外部设备。外部设备种类繁多，物理特性相差甚大，设备管理往往很复杂。设备管理主要包括缓冲管理、设备分配、设备处理、设备独立性和虚拟设备。,文件管理,软件资源的管理称为文件管理，文件管理主要包括目录管理、文件读/写管理、文件存区控制管理。,用户接口,操作系统必须为用户或程序员提供相应的接口，使其通过这些接口达到方便使用计算机的目的。操作系统为用户提供了命令接口和程序接口。,3,什么是进程控制块？试从进程管理、存储管理、设备管理和文件管理的角度分析进程控制块应包含什么内容。,答：进程控制块（PCB）是为了使在多道程序环境下不能独立运行的程序成为能独立运行的进程，而为每个程序所配置的一个数据结构，其中存放了用于描述该进程情况和控制进程运行所需的全部信息。系统根据PCB而感知相应进程的存在，即PCB是进程存在的唯一标志。,PCB中应该包含以下信息：,从进程管理的角度考虑，PCB中应该包含进程标识符、进程状态、CPU状态信息（包括程序计数器、程序状态字、栈指针、通用寄存器等）、进程调度信息（如进程的优先数等）、链接指针（用于将PCB链入各种队列）等项信息。,从存储管理的角度考虑，应保存该进程的程序、数据、堆栈在内存和外存的地址和各部分的长度等信息。,从设备管理角度考虑，应有该进程所需资源和已分配到的资源清单。,从文件管理的角度考虑，PCB中应包含用户文件描述符表，用来登记用户打开的各个文件，并可以通过它找到在内存的相应文件的FCB（如UNIX中的内存索引结点）。,4,试比较进程与程序的异同。,答：进程和程序是紧密相关而又完全不同的概念。,每个进程实体中包含了程序段、数据段这两个部分，因此说进程和程序是紧密相关的。但从结构上看，进程实体中除了程序段和数据段外，还必须包含一个数据结构，即进程控制块PCB。进程是程序的一次执行过程，因此是动态的；动态性还表现在进程由创建产生、由调度而执行、由撤销而消亡，即它具有一定的生命周期。而程序则只是一组指令的有序集合，并可永久地存放在某种介质上，其本身不具有动态的含义，因此是静态的。,多个进程实体可同时存放在内存中并发执行，其实这正是引入进程的目的。而程序的并发执行具有不可再现性，因此程序不能正确地并发执行。,进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。而因程序不具有PCB，所以它是不可能在多道程序环境下独立运行的。,进程和程序不一一对应。同一个程序的多次运行，将形成多个不同的进程；同一个程序的一次执行也可以产生多个进程；而一个进程也可以执行多个程序。,5,进程和线程的主要区别是什么？,答：从调度、并发性、系统开销、拥有资源等方面来比较线程和进程：,调度。在传统的操作系统中，独立调度、分派的基本单位是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位。,并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。,拥有资源。不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。一般地说，线程自己不拥有系统资源（也有一点必不可少的资源），但它可以访问其隶属进程的资源。,系统开销。由于在创建、撤销或切换进程时，系统都要为之分配或回收资源，保存CPU现场。因此，操作系统所付出的开销将显著地大于在创建、撤销或切换线程时的开销。,6,怎样看待操作系统的开销？,答：OS为了管理硬件等资源，必需付出必要的“管理成本”开销，比如进程调度。有时用纯软件方案“成本”太高，不得不加硬件，比如分页内存、虚拟内存、一些CACHE技术等等。当软件和硬件“成本”都太高时，不得不放弃一些好的方法，比如银行家算法。操作系统内核程序本身也是进程，本身就是开销。,7,有5个进程共享同一程序段,而每次最多允许三个进程进入该程序段,若用P、V操作作同步机制,则记录型信号量S的取值范围为(3,-2)。,8,请解释为什么页面大小正好是2的次幂。,Answer:根据页式存储管理的机理，逻辑地址首先被分成页号和页内偏移量，一般需要一次乘除操作和一次加减操作。如果页面长度正好是2的次幂，那么，只需要一次“移位”操作就能取出页号，一次“与”操作就能取出偏移量。效率得到显著提高。,在“按需调页”环境下，请分析顺序查找和二分查找对缺页中断率的影响。,“按需调页”环境里，页内地址是连续的，而页间地址不连续。当页面不在内存时，会引起缺页中断，相对消耗很多的时间。顺序查找一般在当前页进行，此前已驻留内存。只有当跨页面搜索时，才会引起缺页中断；二分查找是跳跃式的，可能会频繁缺页。,9,分页和分段的主要区别是什么？,页是信息的物理单位，页的内容通常无完整意义；而段是信息的逻辑单位，段的内容具有完整的逻辑意义。分页是静态分区技术，而分段是动态分区技术。,页的大小固定且由操作系统决定；而段的长度不固定，决定于用户所写的程序；常由编译器根据信息的性质来划分。分页为省内存，分段为满足编程需要。,分页的作业地址空间是一维线性的；而分段的作业地址空间是二维的。,10,在某简单分页系统中，有2,24,字节的物理内存，256页的逻辑地址空间并且页的大小为2,10,字节，问逻辑地址为多少位？,答：18位,在某段页式系统中，虚地址空间包含了8个段，段长为2,29,字节。硬件把每个段分成大小为256字节的页。问虚地址中有多少位可以用于指定：（a）段号？（b）页号？（c）页内偏移量（d）整个虚地址,答：（a）3（b）2,29,/2,8,2,21,，因此为21位页号（c）8 （d）3218 32,11,在简单页式管理系统中，主存为128KB，分成32块，块号为031；某作业有5页，其页号为04，被分别装入主存的3、12、5、6、9块中。有一逻辑地址为3，476（其中方括号中的第一个元素为页号，第二个元素为页内地址，按十进制计算）。试求出相应的物理地址，并画图说明地址变换过程。,块大小为128KB/32=4KB，因为块与页面大小相等，所以每页为4KB。第3页被装入到主存第5块中，故逻辑地址3，476对应的物理地址为4KB6+476=24576+70=25052。其地址变换过程如下图。,12,13,某虚拟存储器的共有32个逻辑页面，每页1KB，主存16KB.假定某时刻为进程的第0，1，2，3逻辑页分配的物理块号分别为5，10，4，7，试将虚拟地址0A5C和093C变换为物理地址。,分页系统的,逻辑地址=页号+页内偏移量,本题存储器的共有32个逻辑页面，意味着需要5位2进制数。,每页1KB大小，意味着需要10位2进制数。,这样，该系统的 逻辑地址=5位页号+10位页内偏移量,a.将0A5C变换为2进制为:0000,1010,0101,1100,后10位是为内偏移量，故页号是10（十进制2）按题意，第2页对应的物理块号为4，物理地址为二进制的000100，1001011100。十六进制的125C;,b.同理，将093C变换为2进制为:0000,1001,0011,1100，页号也为2，对应的物理块号也为4，此时虚拟地址093C的物理地址为113C.,14,一台机器有48位虚地址和32位物理地址，页面是8K，问在页表中需要多少个页表项？一个倒置的页表需要多少页表项呢？,15,什么是虚拟存储器，它有哪些特征。,答：是用户能作为可编址内存对待的存储空间，在这种计算机系统中虚地址被映象为实地址。简单地说，虚拟存储器是由操作系统提供的一个假想的特大存储器。,具有以下基本特征：,虚拟扩充：不是物理上，而是逻辑上扩充了内存容量；,部分装入：每个作业不是全部一次性而是一部分的装入内存；,离散分配：不必占用连续的内存空间，而是“见缝插针”；,多次对换：所需的全部程序和数据要分成多次调入内存。,16,某计算机采用二级页表的分页存储管理方式，按字节编制，页大小为2,10,字节，页表项大小为2字节，逻辑地址结构为：,逻辑地址空间大小为2,16,页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（）。,A.64 B.128,C.256 D.512,17,现有一分页虚拟存储管理系统，页表保存在快表中，可忽略页表的访问时间。若有一个可用的空页或被置换的页未被修改，则它处理一个缺页中断需要8ms；若被置换的页已被修改，则处理一缺页中断因增加写回外存时间而需要20ms，内存的存取时间为1s。假定70%被置换的页被修改过，为保证有效存取时间不超过2s，可接受的最大缺页中断率是多少？（1ms=1000s）,答：设最大缺页中断率为，则有：,（1-）1s+0.38ms+0.720ms=2s,即：-+2400+14000=1,解得：0.00006,18,某系统使用请求分页存储管理，如果页在内存中，满足一个内存请求需要200ns。如果页不在内存，如有空闲的页框或者没有修改的换出的页，则请求需要7ms。如果替换出的页已经被修改，则需要15ms，如果缺页率是5，并且60的时间用于修改要换出的页，问有效访问时间是多长？假设系统只运行一个进程且页交换时CPU空闲。,解：200ns内得到满足的访问占用全部访问的95。5的访问造成缺页，其中40%的需要7ms。因此，5,402的访问需要7ms。类似地，5,603的访问需要15ms。把所有的时间转换为us，,结果如下：,有效访问时间0.95,0.2 0.02,70000.03,15000,有效访问时间590.19us,ms是毫秒=0.001秒,us是微秒=0.000001秒,ns是纳秒=0.000000001秒,19,一个三级存储系统，Cache命中率为95%,Cache存取要20ns,内存命中率为80%，内存存取时间为60ns,外存存取要12ms。问:此系统的平均存取时间，要求写出计算过程。,答：三级存储为：cache，内存，外存。,这道题给出了CACHE的存取时间为20ns，所以无论CACHE是否命中，都要计入20ns。,每百次访存95次在CACHE,无需访问内存，总计95*20ns,4次在内存,总计4*(20+60)ns,1次在外存,总计(20+60)ns+12ms,上述三项总计相加,除100即可。,20,请求分页管理系统中，假设某进程的页表内容如下表所示：,页面大小为4KB，一次内存访问时间是100ns，一次块表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设TLB初始为空；地址转换时先访问TLB，若TLB未命中再访问页表（忽略访问页表之后的TLB更新时间）；有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回产生缺页中断的指令处重新执行。设又虚地址访问序列2362H、1565H、25A5H，请问：,（1）依次访问上述三个虚地址，各需多少时间？给出计算过程。,（2）基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。,21,（1）因为每页大小为4KB，逻辑地址2362H对应的页号为2，该页在内存，但TLB为空，所以，2362H的访问时间=10ns（访问TLB）+100ns（访问页表）+100ns（访问内存单元）=210ns。,因为逻辑地址1565H对应的页号为1，该页不在内存，出现缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行，需要再访问一次TLB。所以，1565H的访问时间=10ns（访问TLB）+100ns（访问页表）[phone] ns（调页）+10ns（访问TLB）+100ns（访问内存单元）=100 000 220ns。,因为逻辑地址25A5H对应的页号为2，该页在内存，TLB命中，所以，25A5H的访问时间=10ns（访问TLB）+100ns（访问内存单元）=110ns。,（2）1565H对应的物理地址是 101565H；因为2号页刚被访问，不会被置换，因此用101页。,22,某计算机有32位虚地址空间，且页大小为1024字节。每个页表项长4个字节。因为每个页表都必须包含在一页中，所以使用多级页表，问共需要几级？,答：因为一张页表只能包含1024/4=256个页表项。而页的大小为2,10,，所以共需要32-10=22位来表示页号。而每一级页表只能处理22位中的8位，所以共需要3级。有两级页表有2,8,个页,23,在请求分页系统中，常采用哪几种页面置换算法?,最佳置换算法；理论上是最佳的，但不实用。,先进先出算法；缺页率太高，不使用。,最近最久未使用LRU置换算法；最常用的算法,Clock置换算法;LRU的效率不太好，需要硬件支持。Clock是LRU的近似，不需要硬件太多支持。,24,25,高级调度与低级调度的主要任务是什么?为什么要引入中级调度?,作,业调度又称宏观调度或高级调度，其主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存，输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利.,进程调度（又称CPU调度、微观调度、低级调度），其主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它。,为了提高内存利用率和系统吞吐量，引入了中级调度.,26,进程调度中“可抢占”和“非抢占”两种方式，哪一种系统的开销更大？为什么？可抢占式会引起系统的开销更大。,可抢占式调度是严格保证任何时刻，让具有最高优先数（权）的进程占有处理机运行，因此增加了处理机调度的时机，引起为退出处理机的进程保留现场，为占有处理机的进程恢复现场等时间（和空间）开销增大。,27,假定要在一台处理器上执行如下图所示的作业，它们在0时刻以1，2，3，4，5的顺序到达。给出采用下列调度算法时的调度顺序、平均周转时间(turnaround time)和平均响应时间(response time),FCFS,RR(时间片为1，不考虑优先级),非抢占式SJF(shortest job first),非抢占式优先级调度（数字小的优先级大）,作业 执行时间 优先级,1 10 3,2 1 1,3 2 2,4 3 4,5 5 2,28,FCFS,平均响应时间（010111316）/5=10,平均周转时间（1011131621）/5=14.2,29,RR(TQ=1),平均响应时间（01234）/5=2,平均周转时间（21271116）/5=11.4,30,SJF,平均响应时间（110136）/5=4,平均周转时间（2113611）/5=8.4,31,Priority,平均响应时间（801183）/5=6,平均周转时间（1813218）/5=10.2,32,进 程处理器时间优先数,P1 8 3,P2 6 1,P3 22 5,P4 4 4,33,对于能同时支持批处理作业和交互式作业的通用操作系统，试设计一种较合理的进程调度算法。要求能保证交互式作业有合理的响应时间。,解答：,设置两个进程就绪队列Q1，Q2；,Q1专供交互式作业所产生的进程使用；,Q2专供批处理作业所产生的进程使用。,进程调度时优先在Q1中选择，Q1为空时再在Q2中选择；,调度策略：,对Q1中各进程实施时间片轮转法调度；,对Q2中各进程可实施先来先服务调度。,34,一个多级反馈队列的系统中，一个使用CPU较多的进程需要执行50秒。如果第一个队列时间片为5，并且较低一级的时间片是上一级的时间片的2倍，那么这个作业会被中断多少次？当他终止的时候，处于那一级队列？,答：经过三次中断后，在第4个队列中终止运行,35,假设磁盘有200个磁道，磁盘请求队列中是一些随机请求，它们按照到达的次序分别处于55、58、39、18、90、160、150、38、184号磁道上，当前磁头在100号磁道上，并向磁道号增加的方向上移动。请给出按FCFS（先来先服务）、SSTF（最短寻道时间优先）算法进行磁盘调度时满足请求的次序，并计算出它们的平均寻道长度。,36,FCFS,SSTF,被访问的下一个磁道号,移动的磁道数,被访问的下一个磁道号,移动的磁道数,55,45,90,10,58,3,58,32,39,19,55,3,18,21,39,16,90,72,38,1,160,70,18,20,150,10,150,132,38,112,160,10,184,146,184,24,平均寻道长度：55.3,平均寻道长度：27.5,37,为了快速访问，又易于更新，当数据为以下形式时，应选用何种（物理）文件组织方式,（1）不经常更新，经常随即访问。,（2）经常更新，经常按一定顺序访问。,（3）经常更新，经常随即访问。,答：（1）索引物理文件（索引分配）,（2）链接物理文件（链接分配）,（3）没有很合适的。或许应在链接分配的基础上建索引。,38,有一个磁盘组共用10个盘面，每个盘面上有100个磁道，每个磁道有16个扇区，假定以扇区为单位，若使用位示图管理磁盘空间，问位示图需要占多少空间？若空闲表的每个空闲表项占用5个字节，问什么时候空闲表大于位示图？,10*100*16/8=2000B,2000/5=400个,39,根据进程的状态变化，指出其进程调度算法，并标识图中所示的每一个状态变化的原因。,熟练掌握进程同步问题，根据题意确定信号量的初值，并填写算法中空缺的P、V操作。,给出几个作业的提交时间和运行时间，指出按照某种作业调度算法时各个作业的调度次序，并求各个作业的周转时间和平均周转时间。,分页存储管理系统中，根据页面的大小和页表，计算给定逻辑地址的物理地址。,在请求分页存储管理系统中，根据页面走向，某种页面调度算法，补充完整页面调度过程，并计算缺页中断次数。,40,