操作系统幻灯片

,七. 两级和多级页表,k0,外部页表,页表的页号 块号 0 C0 1 C1,进程的页号 块号,1.两级页表的引入,p,bp,0,b0,1,b1,没装入内存之前的进程、页表、外部页表,页表 *离散存放在内存C0、C1、等块中.,k0,外部页表 *连续存放在内存K0 及后续块中.,页表的页号 块号 0 C0 1 C1 1023 C1023,内存中的进程、页表、外部页表,进程 *离散存放在内存b0、b1、等块中.,b0,b1023,b1024,b2047,b1,设页大小为4KB 页表项大小为4B,七. 两级和多级页表,2.逻辑地址结构,页号P,页内地址d,31,12,11,0,11,0,CPU给出：32位线性地址,进程地址空间分页：,进程页表分页：,设:逻辑地址为32位，页大小为4KB，每个页表项占4B,页表,七. 两级和多级页表,表项序号 块号,b0,0,p,bp,外部页表,表项序号 块号 0 C0 p1 Cp1,bp,Cp1,p,进程,0,页号,LA,p1,0,页表页序号,p2,bp,1023,1024,第p1个页表页,表项 序号,1,1,逻辑地址,0,4K,4K-1,七. 两级和多级页表：,3.地址变换过程：,外部页表,外部页表 寄存器,物理地址,外部页号P1,外部页内地址P2,页内地址d,页表分页,块号,块内地址,外部,块号,页号,块号,页号,外部页表 始址、长度,七. 两级和多级页表地址转换,外部页表,10,物理地址,外部页号P1,外部页内地址P2,页内地址d,块号,块内地址,内存5#块 （页表3#分页）,外部页表 寄存器,0000000011,0000000001,000000001010,16,4.4 基本分页存储管理方式,基本分页总结 优点： 存在页内碎片，但碎片相对较小，内存利用率较高 实现了离散分配，消除了程序移动； 缺点： 需要专门的硬件支持，尤其“快表”； 页面共享实现困难，不支持动态链接。,4.5 基本分段存储管理方式,一. 分段存储管理方式的引入 主要是为了满足用户和程序员的下述需要： （1）方便编程 （2）方便信息共享与信息保护 （3）便于动态链接 （4）便于动态增长,4.5 基本分段存储管理方式,二.分段系统的基本原理,1.作业分段 由编程人员或编译器将程序按信息的逻辑含义分为若干段： 每个段有段名（段号）； 每个段长度可以不同； 每个段在内存中连续存放，但段与段之间不必相邻。,code（0）,data （1）,stack （2）,二.分段系统的基本原理 2.逻辑地址结构,stack (2),code(0),data (1),3k-1,0,8k-1,0,0,15k-1,二维的逻辑地址,mov eax,(1:500),mov指令的地址： 0:1000 操作数的地址： 1:500,二.分段系统的基本原理,（1）每个段在段表中占一个表项； （2）记录段在内存的基址、段长、存取权限等信息。,第1段,第2段,第0段,第1段,第2段,20k,50k,65k,内存空间,段表,3.段表,第0段,进程空间,4.5 基本分段存储管理方式,三. 地址变换机构 段表寄存器 存放段表的起始地址和段表长度； 越界检查 逻辑地址的段号与段表长度比较； 段内地址与段表中保存的段长比较。,4.5 基本分段存储管理方式,越界中断,67060,物理地址,假如一个作业的段表如下。分别说明下面指令执行时，地址转换的情况。 （1）STORE R1,0,70 ； （2）STORE R1, 1,20 （3）LOAD R1,3,100； （4）JMP 2,100,W:可写;R:可读;E:可执行。,(1) 0,70 500+70=570 (2) STORE R1, 1,20 ：存取控制不符，硬件将产生保护性中断信号。 (3) 3,100 ：段内地址超过了段长，产生越界中断信号。 (4)2,100 3000+100=3100,四.分段与分页的区别,（1）页是信息的物理单位，段是信息的逻辑单位； （2）页的大小固定，段的大小可变； （3）分页系统中的逻辑地址空间是一维的，分段系统中的是二维的。,五.段页式存储管理方式 基本思想 结合分页和分段技术，先分段后分页 分页：有效提高内存利用率 分段：很好的满足用户需求 原理 对用户作业先分段，各段再分页； 对内存按页大小分成若干物理块/页框。 地址结构与地址变换 二维的逻辑地址（段号、段内地址） 段内地址可进一步划分为段内页号，页内地址 每个进程一张段表和若干张页表,4.5 基本分段存储管理方式,4.5 基本分段存储管理方式,五.段页式存储管理方式 1.作业分段：按信息的逻辑含义进行，每个段有段名。,2. 段内分页,0,0,1,3,2,1,0,五.段页式存储管理方式,3,2,1,0,Main（0段）,0,15K-1,10000,8K,12K-1,10000,0,1,1808,4095,0段2#页,3. 地址结构,逻辑地址（0,10000),0,10000,0,2,1808,4.5 基本分段存储管理方式,五.段页式存储管理方式,二维地址结构,3. 地址结构,段内分页,五. 段页式存储管理方式： 4.段表及页表,进程地址空间,段表,4,2,1,五. 段页式存储管理方式 5.地址转换机构,段表寄存器,逻辑地址(0,10000),块号,块内地址,物理地址,越界中断,0,2,1808,1808,段表,6,（26384）,访问一个数据需3次访问内存。,五. 段页式存储管理方式 5.地址转换机构,段表寄存器,逻辑地址(0,10000),块号,块内地址,物理地址,越界中断,0,2,1808,1808,段表,6,输入寄存器,快表,五、基本分段存储管理方式,段页式存储管理的优缺点 同时具备分段和分页管理的优点：分散存储，内存利用率较高；便于代码或数据共享，支持动态链接等。 访问效率下降：一次访问转换成了三次访问。,六.DOS的内存管理,地址线为20根，即物理地址为20位； 内存空间不超过1M； 字长为16位； 分段存储管理方式： 每段长度不超过216B； 段表用寄存器的方式来实现： CS代码段内存基址 DS数据段内存基址 SS堆栈段内存基址 DOS规定：段在内存的起始地址的低4位必须为0。,data,stack,的高16位,的高16位,的高16位,六.DOS的内存管理,二维的逻辑地址: seg:off 逻辑地址 seg×24+off 物理地址,六.DOS的内存管理,DOS系统，C语言中地址的两种表达方式： 指针 ：如 char *p; 用两个无符号整数seg:off分别表示段内存基址的高16位，和段内偏移: 如 0X100:0X20 Turbo C中两种方式可以互相转化： p=MK_FP(seg,off); seg=FP_SEG(p); off=FP_OFF(p).,内存,0X1000,p,0X1020,char c=A; char *p; p=,c,0X100:0X20,七、X86保护模式下的三种地址,逻辑地址 -段标识符(16b )和偏移量(32b) 如：CS:EIP；DS:EDI等 线性地址 -一个32位的无符号整数，可以用来表示高达4GB的地址 物理地址 -内存地址，也是32位的,逻辑地址 线性地址 物理地址 如果不分页，那么线性地址就是物理地址,1.段地址转换,每个进程的代码段和数据段均存放在自己的局部空间中，这部分信息通常不允许他人访问，这样可防止一个进程破坏另一个进程的信息。 也有一些段允许被多个进程共享访问（比如OS中的某些资源，像中断处理程序等），称它们为全局段。,每个段必须用一个段描述符（8B）来描述，段描述符中有段在内存的基地址、段长度、段的特权级别和访问权限等信息。段描述符被存放在全局描述符表GDT或局部描述符表LDT中。 整个系统只定义一个GDT，其中存放有允许多个进程共同访问的那些段的描述符。 每个进程的局部空间的段的所有段描述符集中存放在一张表中，这张表为该进程的局部描述符表（LDT），也就是进程的段表。,内存,GDT的起始地址和长度由CPU的寄存器gdtr给出：,段描述符,GDT,GDTR,INDEX,LDTR,15 3 0,2.段描述符 每个段描述符有8个字节，根据S位（第5字节的第4位）的取值将段描述符分成普通的段描述符（包括数据段描述符和代码段描述符）和控制描述符（也叫系统描述符）两类。,3.普通段描述符,G 粒度位，0表示限长以字节为单位，1表示限长以页4KB为单位 X 1表示32位的地址或操作数，0表示16位的地址或操作数,P,访问权限字节,DPL,S 1,ED,E 0,A,W,C,E 1,A,R,E=0数据段,E=1代码段,P 存在位 DPL 特权级别 E 可执行与否 ED 扩充方向，0向上扩充（偏移限长） W 可写与否 R 可读与否 A 段是否被访问过 C 一致性（证实）代码段与否 4.二级分页管理（略）,作业：,P159：5，6，7，12，15，26 补充作业： 1.什么叫重定位？它有哪两种方式？这两种方式有什么区别？ 2.某系统采用动态分区分配方式管理内存，内存空间为640K，高端40K用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列的请求序列：作业1申请130K、作业2申请60K、作业3申请100K、作业2释放60K、作业4申请200K、作业3释放100K、作业1释放130K、作业5申请140K、作业6申请60K、作业7申请50K、作业6释放60K，请分别画图表示出，使用首次适应算法和最佳适应算法进行内存分配和回收后，内存的实际使用情况.,3.请求分页管理系统中，假设某进程的页表内容如下表所示: 页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用LRU置换算法和局部淘汰策略。假设TLB初始为空；地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。,设有虚地址访问序列2362H、1565H、25A5H，请问： （1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。 （2） 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。,