存储管理_lecture6.ppt

,单击此处编辑母版文本样式,第二级,*,*,单击此处编辑母版标题样式,操作系统存储管理,张其亮,1,summary,存储器,程序链接、装入方式,存储管理方式,虚拟存储技术,2,你知道有哪些存储设备？,3,memory,存储器,4,question,程序从编写到运行要经过哪些环节？,5,cc,6,name space,f.c,void main(),int i;,i=2;,f.o,7,Space changes,8,link,链接,静态链接方式(Static Linking),装入时动态链接(Loadtime Dynamic Linking),运行时动态链接(Run-time Dynamic Linking),9,Static Linking,在程序运行之前将各个目标模块及所需的库函数，链接成一个完整的装入模块（可执行文件），运行时直接装入内存。,静态链接方式,10,Static Linking,对相对地址进行修改,变换外部调用符号,11,Dynamic Linking,在装入时动态链接方式中，用户源程序经编译后所得到的目标模块，是在装入内存时边装入边链接的。即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，将它装入内存并修改目标模块中的相对地址。,(1)便于修改和更新。,(2)便于实现对目标模块的共享。,装入时动态链接,优点,：,12,Dynamic Linking,这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。,运行时动态链接,扩展,13,Static lib,14,Dynamic lib,15,Load,1、绝对装入方式：编译程序产生绝对地址目标代码，绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入程序装入内存后不需对地址进行修改。,程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。通常是在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址,2、可重定位方式：由装入程序根据内存当时的实际使用情况，将装入模块装入到内存中的适当地方。,在程序运行之前执行的,3、动态运行时装入方式。,程序执行期间执行的,程序装入,16,load,绝对装入程序按照模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中逻辑地址与实际内存地址完全相同，不需对程序和数据的地址进行修改。,绝对装入方式,17,load,1,、可重定位装入时，模块装入内存时会使装入模块中的所有逻辑地址与实际内存的物理地址不同。,2,、通常是在装入时对目标程序中指令和数据的地址进行修改，称为重定位。由于可重定位装入时地址变换是在装入时一次完成的，以后不再改变，称为静态重定位。,可重定位装入方式,18,load,程序在运行过程中在内存中的位置可能会经常改变，故引入动态运行时装入方式。,动态运行时装入方式,动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。,重定位寄存器支持,19,example,b,c,哪一种是可重定位方式？哪种是动态运行时方式？,20,memory,存储管理方式,1,单一连续区管理,2,分区管理,3,分页管理,4,分段管理,5,段页式管理,21,memory,一般由单道系统采用，整个内存空间的用户区可看成是单一连续存储管理方式,。,单一连续区管理,22,part,把主存的用户区划分成若干区域，每个分区给一个用户程序使用，程序一次性装入。,分区管理,固定分区管理,动态分区管理,23,part,固定分区管理,24,part,固定分区管理,Free Space,程序2,程序3,程序1,0k,4k,16k,64k,128k,1每个分区只能容纳一个程序,2固定分区容易造成内碎片,占用分区之内未被利用的空间,25,part,固定分区分配方法,分区表,回收：状态,1-0,26,part,动态分区管理,对主存空间事先不划分，而是当作业装入时，根据作业的大小，,在空闲区域划出一个 连续的区域,5,可用,270,30,4,可用,210,40,3,可用,132,24,2,可用,44,64,1,状态,始址,大小,序号,0,0,N+2,N+2,后向指针,N个字节可用,前向指针,如何分配？,空闲分区表,空闲分区链,27,example,OS区,Job1,Job2,Job3,Job4,Job5,Job6,Job7,OS区,Job1,Job2,Job3,Job4,Job5,自由链,头指针,Job7,Job6,example,28,example,外碎片,动态分区分配算法,29,FF,按始地址升序排列，分配内存时，从链首开始查找，找到找到一个能满足要求的空闲分区为止。,首次适应算法,30,FB,按分区大小递增的顺序排列。分配内存时 总是能把满足要求、又是最小的空闲分区分配给程序，避免“大材 小用”。,缺点：容易产生碎片,最佳适应算法,31,FW,按分区大小递减的顺序排列。,最差适应算法,32,others,循环首次适应算法。,快速适应算法：将空闲分区按大小进行分类。（伙伴算法）,33,example,某时刻系统中有三个空闲区其大小和首址为：(35KB，100KB)、,(12KB，156KB)、(28KB，200KB),有一作业系列：,(JOB1，12KB),(JOB2，30KB),(JOB3，28KB),采用哪种算法最合适？,34,example,35,part,检查回收的分区是否与空白区邻接，如有则加以合并，使之成为一个连续的大空白区；,修改可用表或自由链。,空闲释放区与空闲区相邻有四种情况：,上空闲区f1,回收区r,下空闲区f2,上空闲区f1,回收区r,回收区r,下空闲区f2,回收区r,动态分区回收,36,example,紧凑技术,37,reload,38,program,动态重定位分配,39,protect,How to protect the memory?,界限寄存器方式,基址限长寄存器法,40,protect,界限寄存器方式,寄存器上界,寄存器下界,41,example,例：有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1200。,下界寄存器：500,上界寄存器：1500,逻辑地址装入内存的首地 物理地址,1、500500 1000 500 1000 1500,2、345500 845 500 845 1500,3、1200500 1700 500 1700 1500,42,protect,基址限长寄存器,43,example,例：有一程序装入内存的首地址是,500,，末地址是,1500,，访问内存的逻,辑地址是,500,、,345,、,1200,。,基址寄存器：,500,限长寄存器：,1000,判别式：逻辑地址,限长寄存器,1,、,500 1000 ,2,、,345 1000 ,3,、,1200 1000 ,44,questions,分区管理有哪些缺点？,造成原因是什么？,缺点：碎片问题，造成内存浪费,原因：连续存储,45,page,分区存储管理中作业占用的分区必须是一个连续的存储区域，容,易产生碎片问题。故提出离散存储管理。,纯分页管理,请求分页管理,46,纯分页管理,Divide virtual memory into small pages,Divide physical memory into small blocks,Page size=block size,47,example,实现了离散存储，还会产生碎片吗？,48,example,页内碎片，较小,49,Page Structure,页面大小固定，,e.g,2k,4k,2,的整数次幂,页号,d,页内偏移,p,虚拟地址,页号p=虚拟地址/页面大小取整,页内偏移d虚拟地址页面大小,例如，设某系统的页面大小为1KB，A=3456B，,则P=3，d=384。,50,page,块内偏移地址d=页内偏移地址d,绝对地址块号B块大小块内偏移地址,物理地址,块号,d,块内偏移,p,51,page,页表,页号,块号,0,2,1,3,2,8,页表占据内存,52,example,53,page,页表始址 页表长度,2 452,+,页号 块号,0 2,1 4,2 8,.,.,.,.,.,8 452,逻辑地址 2500,越界中断,页表寄存器,物理地址：8*1024+452=8644,地址转换,页大小,1K,54,example,有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址3412,B,转换成内存地址。,虚地址 3412,PINT 3412/2048 1,D,3412 mod 20481364,物理地址：,9*2048+1364=19796,55,example,example,2：,在32位计算机系统中，页大小位4k。程序页表如下：,有一个逻辑地址28A6H，其对应的物理地址是多少？(16进制表示),页号,块号,0,2,1,4,2,3,56,page,快表,在页式存储技术中，在执行一条访问内存指令时，实际上要访问多少次内存？,1,2,思想：,增加一个具有并行查找能力的高速缓冲存储器,-,快表,并行查找，快表找到后结束，快表找不到继续查页表,57,page,页表始址,页表长度,页表寄存器,页表,块号,页号,5,3,3,2,7,1,2,0,3,1250,物理地址,2,1250,逻辑地址,越界中断,快表,块号,页号,20,5,11,4,5,3,2,0,联想寄存器,58,page,需要页表：,2,20,=1M,个页表项，假设一个页表项占,4B,页表大小：4B*1M=4M,由于页表必须放在内存中，所以系统多个进程的页表将占据庞大的内存空间。而实际上，不是每个进程都有4G，即1M个页表项中，大部分处于空闲状态，因此采用这种分页结构实际上是对内存不必要的浪费！,x,86的分页管理,Normally 4KB Pages,以,32,位地址空间为例,如何解决？,59,page,采用离散分配方式来解决难以找到一块,连续的大内存空间的问题；,只将当前需要的部分页表项调入内存，,其余的页表项仍驻留在磁盘上，需要时再调入。,多级页表,60,page,61,page,62,page,简单分页把作业地址空间划分成若干页面后，需要把所有的页面装入主存中。,换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行.,请求分页方式中对于当前不使用的页面放在外存，当要访问的页面不在主存时，作业通过,缺页中断,向系统发出调页请求，由系统把所需的页面从外存调入内存,请求分页管理,63,page,64,page,状态位：该页是否在主存,修改位：该页装入主存后是否被修改过,内存中的每一个页面在外存都有一份副本，若无修改，则不必写回外存。,访问字段,：该页被访问的次数或最近有多长时间未被访问等,外存地址：该页在外存的存放位置,主存块号,状态位,修改位,访问字段,外存地址,页号,页表,65,page,程序访问的页面不在内存，发出缺页中断，中断程序保留CPU环境，分析中断原因，转入缺页中断处理程序。缺页中断处理程序查页表得到该页在外存的位置：,如果此时内存能容纳新页将之调入，修改页表。,若内存已满，则进行页面置换，选中一页换出内存，如果该页未修改过，不必将该页写回磁盘，如果修改过，必须写回磁盘，然后调用缺页中断程序。并修改页表相应位。,页面调入过程,66,page,Questions,：,选择哪些页面调出内存？,67,page,好的页面算法要有较低的页面转换频率,先进先出（FIFO）,最近很久未使用算法（LRU）,最佳置换算法（Optimal）,简单Clock 置换,改进的Clock置换,页面调度算法,68,FIFO,example,：,内存有三个物理块,-all initially free,string:A B C A B D A D B C B,FIFO,总是淘汰最先进入内存的页面,69,FIFO,FIFO,缺页？,缺页？,？,70,FIFO,抖动现象,71,LRU,根据页面的使用情况进行决策。赋予每个页面一个访问字段 t，t记录一个页面自上次访问以来所经历的时间，淘汰时选择t值最大的，即为最近最久未使用的。,LRU,example,：,内存有三个物理块,-all initially free,string:A B C A B D A D B C B,72,LRU,用一个栈来保存当前使用的各个页面的页面号，当进程访问某页时，便将该页的页面号从栈中移出，压入栈底。栈顶始终是最新访问的页面。,用堆栈来处理,LRU,73,Optimal,淘汰的页面是以后不会使用的或最长时间不会被访问的。由于人们无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不被访问的，因此，该算法很难实现。,最佳置换算法,example,：,内存有三个物理块,-all initially free,string:A B C A B D A D B C B,74,CLOCK,Clock,75,EXAMPLE,Clock,76,Improved,CLOCK,Improved Clock,!,自学,77,example,练习：,在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5当分配给该作业的内存块分别为3、4个时，试分别计算采用下述页面淘汰算法时的缺页率（假设最初主存中没有页面），并比较所得结果。,FIFO,LRU,Clock,78,segment,问题的提出：前面介绍的几种存储管理技术中，提供给用户的逻辑地址空间是一维线形的，与内存的物理组织基本相同，但用户编写的程序逻辑结构却不是这样。,分段管理,主程序段,子程序段,1,子程序段,2,数据段,79,segment,一维空间在分页时并不能保持原来的结构。,页是存放信息的物理单位，并无完整意义。,段却是信息的逻辑单位，有利于信息共享。,动态链接以段为单位,。,分段存储管理,分段存储管理的引入,80,segment,按照作业的逻辑结构划分地址空间，,每个段都从0开始编址。,作业装入主存后，每个段占用一个连续的存储区域，而各段之间可以不连续。,思想：,81,segment,记录段的起始地址和段的长度，可通过段表从物理内存中找出每个逻辑段的位置。,段号s 段内位移w,31 16 15 0,地址结构,地址空间是二维的,段表,段号,段长 段基址,82,segment,内存,段表始址,段表寄存器,段表,段号段长内存始址,01k6k,16404k,250010k,330012k,10340,2 100,100,物理地址,逻辑地址,段号s,位移量w,12345,10k,10340,段表长度,越界,越界,地址变换,83,segment,段表放在内存中，要访问一个数据，须访问多少次内存？,84,difference,页是信息的物理单位，分页仅仅是由于系统管理的需要，实现离散,分配，减少碎片，而不是用户的需要；而段是信息的逻辑单位，它含有一组具有相对完整意义的信息，是处于用户的需要。,页的大小固定且由系统确定，把逻辑地址分为页号和页内地址两部,分功能，由机器硬件实现；而段的长度却不固定，由用户在编程时确定，或由编译程序在对源程序进行编译时，根据信息的性质来划分。,分页的作业地址空间是一维的，即单一的线性地址空间，程序员只,需用一个记忆符即可表示一个地址；而分段的作业地址空间则是二维的。,1,2,3,85,segment,由于段是信息的逻辑单位，因而分段系统易于实现共享和保护，这也是分段系统的突出优点之一。,举例：,假定一个多用户系统可容纳40个用户，某应用程序包括160KB的Text Editor代码区和40KB的数据区(共200K)，则需8M内存支持；若代码是可重入的(Re entrant)，则代码去可共享，因而其所需内存空间为1760KB(=160+40 x40)。,在分页系统中，假定每个页面大小4K，那么代码区占40个页面，数据区占10个页面。为了实现共享，每个进程的页表中都建立40个页表项使用相同的物理块号(代码区)，另外建立10个数据区的页表项,在分段系统中，实现共享则容易得多，,如图所示,。,段共享,86,segment,ed1,ed2,ed40,data1,data10,进程,1,ed1,ed2,ed40,data1,data10,进程,2,21,22,60,61,70,页表,21,22,60,71,80,ed1,ed2,ed40,data1,data10,主存,data1,data10,21,22,60,61,70,71,80,editor,data1,进程,1,editor,data2,进程,2,160,40,段长,段表,80,240,基址,160,40,80,380,80,240,380,editor,data1,data2,分页系统中共享,editor,的示意图,分段系统中共享,editor,的示意图,87,example,段号 段长 段起始地址,0,200 500,1,400 1000,2,100 1400,3,900 2000,虚地址：（0，100），（1，500），（4，470），（2，250）完成实地址转换？,举例,88,segment-page,分段能保持原来的逻辑结构，分页能减小碎片，提出了段页式存储管理，结合两者的优缺点。,把作业空间分段，然后在段中进行分页,0,16K,分段MAIN,（主程序）,0,10K,分段X,（子程序）,0,8K,分段A,（数组）,0,300,分段X,（工作区）,4K,8K,4K,4K,8K,段页式存储管理,89,segment-page,段号 页号 页内位移,地址结构,需要段表,+,页表的支持,参考分段管理和分页管理,90,段页式存储管理,段表始址 段表长度,+,段超长,段表地址寄存器,+,段号 段内页号 页内位移,段号 页表长度,页表始址,.,0,1,.,2,.,段表,页号 块号,0 2,1 7,.,.,.,.,.,.,0段页表,块号 偏移地址,物理地址,逻辑地址,地址变换,91,segment,程序运行之前，只需要先调入若干个分段，当程序执行发现所需的段不在内存时，请求OS调入所需要的段。,请求分段存储管理,参考请求分页 管理，自学！,92,question,在段页式存储管理中，为了获得一条指令或数据，需要访问内存多少次？,？,问题,93,virtual memory,虚拟存储器,内存有,1G,，,操作系统占,200M,，程序,1,占,500M,，程序,2,有,400M,，能调入内存运行吗？,94,virtual memory,1,、虚拟内存使用请求分页技术,2,、将部分程序放在外存，用时调入,3,、用户感觉不到，认为程序只要能运,行，说明内存能容纳它,4,、虚拟的，而非物理上扩充了内存,95,End,Thanks,96,Practice,1.,在可变分区存储管理中的紧凑技术优点在于（）,A,、增加主存容量,B,、缩短访问周期,C,、加速地址转换,D,、集中空闲区,2.,以下存储管理技术中，支持虚拟存储器的技术是（）,A,动态分区法,B,可重定位分区法,C,请求分页技术,D,对换技术,3.,在段式存储管理中，一个段是一个（）区域。,A,定长的连续,B,不定长的连续,C,定长的不连续,D,不定长的不连续,97,4.,存储管理中，页面抖动是指（）。,A,使用机器时，屏幕闪烁的现象,B,被调出的页面又立刻被调入所形成的频繁调入调出现象,C,系统盘有问题，致使系统不稳定的现象,D,由于主存分配不当，偶然造成主存不够的现象,5.,系统“抖动”现象的发生是由（）引起的。,A,置换算法选择不当,B,交换的信息量过大,C,内存容量不足,D,请求页式管理方法,6.,在分区存储管理方法下,导致碎片的原因是,(),。,A.,重定位,B.,分区的个数固定,C.,分区的大小固定,D.,作业连续存储,98,7.,在页式存储管理系统中，整个系统的页表,个数是（）个。,A 1 B 2 C,与页面数相同,D,和装入主存的进程个数相同,8.,采用段式存储管理时,一个程序如何分段是在,(),决定的,.,A.,分配主存时,B.,用户编程时,C.,装作业时,D.,程序执行时,9.,能够装入内存任何位置的代码程序必须是,(),。,A.,可重入的,B.,可重定位,C.,可动态链接,D.,可静态链接,99,10.,在下列有关请求分页管理的叙述中，正确的是（）。,A.,程序和数据是在开始执行前一次性装入的,B.,产生缺页中段一定要淘汰一个页面,C.,一个被淘汰的页面一定要写回外存,D.,在页表中要有“访问位”和“改变位”等信息,11.,采用（）不会产生内部碎片。,A.,分页式存储管理,B.,分段式存储管理,C.,固定分区式存储管理,D.,段页式存储管理,12.,当程序经过编译或者汇编以后，形成了一种由机器指令组成的集,合，被称为,(),。,A,源程序,B,目标程序,C,可执行程序,D,非执行程序,100,13.经过（），目标程序可以不经过任何改动而装入物理内存单元,A 静态重定位 B 动态重定位,C 编译或汇编 D 存储扩充,14.以下存储管理技术中，支持虚拟存储器的技术是（）,A 动态分区法 B 可重定位分区法,C 请求分页技术 D 对换技术,15.段页式管理每取一次数据，要访问（）次内存,A 1 B 2 C 3 D 4,16.若处理器有32 位地址，则它的虚拟地址空间为（）字节,A 2GB B 4GB C 100KB D 640KB,101,17.可由CPU 调用执行的程序所对应的地址空间为(),A 符号名空间 B 虚拟地址空间,C 相对地址空间 D 物理地址空间,18.动态分区分配按照进程的需求量分配内存分区，所以（）。,A 分区的长度是固定的 B 分区的个数是确定的,C 分区的长度和个数都是确定的,D 分区的长度不是预先固定的，分区的个数是不确定的,102,19.在一个支持虚拟分页并采用请求分页的存储管理的系统中,有一用户程序,它访问其地址空间的字地址序列是:70,115,225,322,66,160,488,33,166,250,366,404。问:,若分配给该作业的内存大小为300字,初始为空,页大小为100字,试按 FIFO、LRU页面淘汰算法,分别计算缺页率.,103,20.考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：,（1）逻辑地址需要多少位表示？（二进制）,（2）绝对地址需要多少位表示？（二进制）,104,21.,某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为64KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：,页号 物理块号,0 5,1 10,2 4,3 7,.,则逻辑地址0A5C(H)所对应的物理地址是什么？,105,22.现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下：,段号 主存起始地址 段长度,0 120 40,1 760 30,2 480 20,3 370 20,计算逻辑地址（2，15），（0，60），（3，18）的绝对地址是多少？注：括号中第一个元素为段号，第二个元素为段内地址。,106,