OS04离散分配方式

2023/2/6第四章存储器管理1第四章存储器管理4.1存储器管理的功能4.2程序的装入与链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6段页式存储管理方式2023/2/6第四章存储器管理24.4基本分页存储管理方式4.4.1分页存储管理基本思想4.4.2页地址映射4.4.3基本页式存储管理方案小结2023/2/6第四章存储器管理34.4.1分页存储管理基本思想分页技术是由曼彻斯特大学提出，并于1960年前后在Atlas计算机上实现分页技术对操作系统的发展产生了深远影响2023/2/6第四章存储器管理4程序地址空间把用户程序按系统规定的逻辑页划分成大小相等的部分，称为页(page)

从0开始编页号，页内地址是相对于0编址010K0124K8K2023/2/6第四章存储器管理5程序地址空间用户程序的划分是由系统自动完成的，对用户是透明的一般一页的大小为2的整数次幂2023/2/6第四章存储器管理6逻辑地址地址的高位部分为页号地址的低位部分为页内地址页号页内地址1231页号P011页内位移量W编号0~1048575相对地址0~40952023/2/6第四章存储器管理7内存地址空间按系统规定的逻辑页大小划分为大小相等的区域，称为块或内存块（物理页面、页框）从0开始编块号主存中块/页框2023/2/6第四章存储器管理8内存分配物理块表：整个系统有一个物理块表，描述物理内存空间的分配使用状况数据结构：位示图、空闲块链表2023/2/6第四章存储器管理9内存分配内存以块为单位进行分配，并按应用程序的页数多少来分配。逻辑上相邻的页，物理上不一定相邻。2023/2/6第四章存储器管理10...01234560123456逻辑地址空间块/页框页号页表主存中块/页框.......2023/2/6第四章存储器管理114.4.2页地址映射1、页表2、页大小的选择3、页地址映射4、分页存储管理中的信息保护5、快表/联想存储器6、两级页表和多级页表2023/2/6第四章存储器管理121、页表若将应用程序的包含页号和页内地址的逻辑地址转换成内存地址，必须要有一个数据结构，用来登记页号和块号的对应关系和有关信息。这样的数据结构称为页表。2023/2/6第四章存储器管理13系统为每个进程在内存建立一个页表页表内容页号：登记程序地址空间的页号块号：登记相应的页所对应的内存块号其它：登记与存储信息保护有关的信息页号块号其它05…165…213…2023/2/6第四章存储器管理14页表的首地址和长度存于该进程的PCB中；占用处理机的当前进程的页表首地址和长度需要放在地址映射机构的页表首址寄存器和页表长度寄存器。2023/2/6第四章存储器管理15例作业1有2页分别装入内存的5、6号块作业2有3页装入内存的2、4、7号块作业3有1页装入内存的8号块2023/2/6第四章存储器管理162、页大小的选择太大：浪费；太小：页表过长。IBMAS/400VAXNS32032：512字节Intel80386Motorola68030：4096字节Windows2000：4096字节WindowsNT随CPU的不同而不同：4～64K页的大小是2K，K:9~16。2023/2/6第四章存储器管理173、页地址映射分页中的地址映射其实与通常的地址映射的概念是一样的，即把程序地址转换成内存地址，这个转换过程是在程序执行过程中完成的，是动态地址映射。在现代计算机系统中，由系统提供的地址映射硬件来完成地址映射工作。2023/2/6第四章存储器管理18MainmemorydiskCPUMMUCPUPackageTheCPUsendsaddressestotheMMUTheMMUsendsphysicaladdressestomemoryMMU2023/2/6第四章存储器管理20例设页长为1K，程序地址字长为16位。作业22023/2/6第四章存储器管理21说明在执行指令MOVr1,[2500]时，地址转换步骤：取出程序地址字2500送虚地址寄存器VR；由MMU硬件分离出页号P和页内地址W；因为页长为1K，所以页内地址占10位（0-9位），页号占6位（10-15位）；硬件取出VR寄存器中的高6位即为页号，低10位即为页内地址。计算可得P=000010(2)，W=0111000100；2023/2/6第四章存储器管理22根据页号P=2，硬件自动查该进程的页表，找到第2页对应的块号为7(000111)，将块号送到内存地址寄存器MR的高6位中。将VR中的W的值0111000100复制到MR的低10位中，从而形成内存地址。系统就以MR中的地址访问内存。2023/2/6第四章存储器管理23例设页长为1K，程序地址字长为16位。置2023/2/6第四章存储器管理24计算时要注意：若给出的地址为16进制，则将其转换为二进制，然后，根据页长及程序地址字的长度，分别取出程序地址的高几位和低几位得到页号及页内地址。如页长为2K，程序地址字为16位，21A4则高5位为页号，低11位为页内地址页号为00100，页内地址为001101001002023/2/6第四章存储器管理25若给出的地址为十进制，则用公式： 程序地址/页长商为页号，余数为页内地址。内存地址=块号*页长+页内地址

如程序地址为8457，

页长为4KB则8457/4096可得：商为2，余数为265。

即P=2，W=2652023/2/6第四章存储器管理264、分页存储管理中的信息保护信息保护从两个方面实现：在分离程序地址的页号和页内地址时判别访问地址是否越界若产生的页号满足下式为合法： 0≤页号<程序地址空间的页数判断由硬件自动做，若不合法，硬件产生越界中断，由操作系统的越界中断处理程序进行处理。2023/2/6第四章存储器管理27信息保护从两个方面实现：判断访问是否越权在页表中增加用于存取控制和存储保护的信息，当要访问某页的某个逻辑地址时系统要根据该页的存取控制和存储保护信息检查访问是否合法。2023/2/6第四章存储器管理285、快表/联想存储器在前述的页地址变换过程中有一个严重的问题——

每一次对内存的访问都要访问页表，页表是放在内存中的，也就是说每一次访问内存的指令至少要访问两次内存，运行速度要下降一半。这一问题是必须解决。2023/2/6第四章存储器管理29解决方法把页表放在一组快速存储器中(Cache)，从而加快访问内存的速度。把这种快速存储器组成的页表称为快表，把存放在内存中的页表称为慢表。快表又叫相联(联想)存储器(associativememory)或TLB

(Translationlookasidebuffers)2023/2/6第四章存储器管理30讨论一个程序可能会很大，如1M，若页长为1K，则该程序有1000个页，则页表就需要1000个表项，当程序更大时，页表会更大，那么应该有一个多大的快速存储器才能满足要求呢？遇到两个问题：可能快速存储器多大都是不够的，因为程序可能会更大。快速存储器是非常昂贵的。

2023/2/6第四章存储器管理31实际上并不需要一个很大的快速存储器，有一个能存放16个页表表目的快速存储器就够了。硬件根据需要将页表中当前需要的少量表目读入快表，其它表目仍留在内存的页表中，当需要时读入新的表目，并淘汰适当的表目。快表表项：页号；内存块号；保护位；修改位；有效位2023/2/6第四章存储器管理32validVirtualpageModifiedProtectionPageframe11401RW311200RX3811301RW2911291

RW621190RX501210RX4518601RW1418611RW752023/2/6第四章存储器管理33p’页表地址越界

L比较p>=Lpp’...快表

b+页号p

页内地址wp’w物理地址页表地址寄存器页表长度寄存器逻辑地址地址映射机制2023/2/6第四章存储器管理34分析当调度合理时，可以达到97％的效率。访问页表的速度大致相当于访问快表的速度，考虑到快表的速度是内存速度的数倍或数十倍，那么相对于真正的访问内存工作来讲，访问快表的时间可以忽略不计。即具有快表的页地址变换不会造成进程运行速度的下降。2023/2/6第四章存储器管理356、两级页表和多级页表页表需要连续空间存储的，但是当页表项很多时，仅采用一级页表需要大片连续空间。可将页表也分页，并对页表所占的空间进行索引形成外层页表。由此构成二级页表。更进一步可形成多级页表。

2023/2/6第四章存储器管理36二级页表结构10781011...64......外部页表1742012n-1n115114...1468...1012102301102301023第0页页表第1页页表第n页页表...…01234561141151468内存空间2023/2/6第四章存储器管理37二级页表的地址映射过程外部页表首址外部页号页表位移页内位移逻辑地址页表地址...外部页表/每进程一个块号...页表块号块内位移++内存地址2023/2/6第四章存储器管理38图:三级页表结构及其地址映射过程逻辑地址2023/2/6第四章存储器管理394.4.3页式存储管理方案小结优点：解决了碎片问题便于管理缺点：不易实现共享不便于动态链接2023/2/6第四章存储器管理404.5基本分段存储管理方式4.5.1分段存储管理基本思想

4.5.2段地址映射4.5.3段式存储管理方案小结2023/2/6第四章存储器管理414.5.1分段存储管理基本思想程序地址空间按程序自身逻辑关系划分为若干个段，每个段都有一个段名和段号；段号从0开始；每段段内从0开始编址，段内地址连续。逻辑地址段号段内地址2023/2/6第四章存储器管理42内存地址空间内存空间被动态的划分为若干个长度不相同的区域，称为物理段；每个物理段由起始地址和长度确定。内存分配以段为单位分配内存，每一个段在内存中占据连续空间；各段之间可以不连续存放。2023/2/6第四章存储器管理43...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N数组[A]12345...2023/2/6第四章存储器管理44操作系统.....B0SA0NY0LX0PM0K逻辑段号01234作业1的地址空间15003200500060008000PKSLN主存K3200P1500L6000N8000S5000段号段长段地址操作系统012342023/2/6第四章存储器管理45内存的分配空闲块管理空闲块表（队列）内存分配算法（三种） 首次最佳最坏与动态分区管理相同2023/2/6第四章存储器管理464.5.2段地址映射1、地址映射数据结构每一进程有个段表，它的每一个段在段表中占用一个表目；段表一般包括有段的首址、段的长度和存取状态等信息。段表首址指针和段表的长度存放在进程PCB中，当前进程的还需装入寄存器。2023/2/6第四章存储器管理474.5.2段地址映射1、地址映射数据结构段号012段首址段长度58K20K100K110K260K140K2023/2/6第四章存储器管理482、段地址映射 段地址映射由硬件地址变换机构完成。2023/2/6第四章存储器管理49说明段地址映射过程为：程序地址送入虚地址寄存器VR中；取出段号S和段内位移W；根据段表首址指针找到段表，查找段号为S的表目，得到该段的首地址；把段首地址与段内位移相加，形成内存地址送入MR中，并以此地址访问内存。2023/2/6第四章存储器管理503、存储保护防止越界访问段号？段内地址？防止越权访问2023/2/6第四章存储器管理514、快表同页地址变换一样，在段地址变换过程中，也有两次访问内存的问题。为了加快访问内存的速度也可采用快速存储器组成快表。

Cl

Cb+段号S

段内地址d比较比较b+d段表S>=Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址Lb...SLb地址越界d>=Ld>=L地址映射及存储保护机制地址越界地址越界比较2023/2/6第四章存储器管理535、分段与分页技术的比较分段与分页主要有以下差别：页大小是系统固定的，段大小通常不固定。分页是出于系统管理的需要，分段是出于用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。2023/2/6第四章存储器管理545、分段与分页技术的比较逻辑地址表示分页是一维的，各个模块在链接时必须组织成同一个地址空间；分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。2023/2/6第四章存储器管理55段的共享比页的共享更容易5、分段与分页技术的比