1、第3讲 现在的操作系统怎么管理内存？早期的内存管理方案，所有的程序必须全部放入内存，因此应用程序的大小不能超过内存的大小。超过了怎么办？3对换（中级调度）所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存4 对换的单位 进程 页 段 对换空间（在磁盘上）Linux：swap文件系统 Windows：文件形式5内存管理方式 不连续分配方案 不必全部放入内存 不是非要连续存放 分页、分段6不连续方式之分页35 程序的地址空间被等分成 大小相等的片，称为页面，又称为虚页。主存被等分成大小相
2、等的片，称为主存块，又称为实页、页框架。02KB4KB254KB256KB102KB4KB6KB0页1页2页3页主存作业地址空间36 为了实现从地址空间到物理主存的映象，系统建立的 记录页与内存块之间对应关系的地址变换的机构称为 页面映像表，简称页表。3701KB01KB2KB3KB1主存作业2地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作业1地址空间01KB1作业3地址空间0516页号块号02140827作业1页表作业2页表作业3页表osos38 记录页与块之间对应关系的。当CPU给出的虚地址长度为16位，页面大小为1KB时，在分页系统中地址结构的格式如
3、下：p w15 10 9 0页号P页内位移Wmov r1,250012301KB2KB3KB1作业2地址空间391页式地址变换的例 作业2地址空间中，设100号单元处有如下指令：mov r1,2500。当这条指令执行时，如何进行正确的 地址变换。2500 71024 +452 p=7 w=4520000100111000100 000111 0111000100mov r1,250012301KB2KB3KB1作业2地址空间页式地址变换过程页表始址寄存器mov r1,250012301KB2KB3KB1作业2地址空间+021427页表 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0
4、 015 10 9 0页号P页内位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmov r1,2500123第1页页号P页内位移W 15 10 9 00 0 0 1 1 10 1 1 1 0 0 0 1 0 071024+452=762041页式地址变换步骤CPU给出操作数地址(为2500)；由分页机构自动地把逻辑地址分为两部分，得到页 号p和页内相对位移w(p=2，w=452)；根据页表始址寄存器指示的页表始地址，以页号为 索引，找到第2页所对应的块号(为7)；将块号b和页内位移量w拼接在一起，就形成了访问 主存的物理地址 (7*1024+452=
5、7620)1.某页式存储管理系统中，地址寄存器长度为24位，其中页号占14位，那么主存分块大小为多少字节？程序最多占多少页？问题 这种地址映射只能在程序执行的时候做，即动态重定位 每次地址映射的时候都要访问页表42什么是联想存储器 高速、小容量半导体存储部件，又称缓冲存储器快表 在缓冲存储器中存放正在运行的进程当前用到的页号 和对应的块号，又称为快表。高速缓冲存储器 地址变换速度快，但成本较高主存区域 地址变换速度比硬件慢，成本较低43利用快表进行地址映射 a +P w 仅在联想映像不匹配时进行页号 b w首先选择联想存储器所有页表在主存中物理地址pbba+pa44装入一个作业的全部页面才能投
6、入运行。装入一个作业的部分页面即可投入运行。页号 主存块号 中断位 辅存地址中断位I 标识该页是否在主存 若i=1，表示此页不在主存；若i=0，表示该页在主存辅存地址 该页面在辅存的位置45作业2在请求分页系统中的存储映像01KB2KB4KB1作业2地址空间mov r1,2120add r1,3410006251 006802 3KB01KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB102142作业2页表osos作业2 第 1页作业2 第 0页3页号 辅存地址 中断位 块号 0011地址地址地址地址46缺页处理的例 作业2的主存块数为 m2=3，讨论程序执行 “mov r1，
7、2120”指令时的情况。CPU产生的虚地址为2120分页机构得 p=2，w=72查页表。该页中断位i=1发生缺页中断！如主存中有空白块，且nm 则直接调入如主存中无空白块，或n m，则需淘汰该作业在主存中的一页01KB2KB4KB1作业2地址空间mov r1,2120add r1,3410006251 006802 3KB47缺页处理 启动要处理的指令给出虚地址 得到页号该页在主存?有空闲块?缺页中断执行完该指令 准备执行下条指令选一页淘汰 从外存读入所需的页 调整存储分配表和页表 重新启动被中断的指令 调整存储分配表和页表要重写入?该页写入外存YNNY硬件软件YN 在缺页中断处理过程中，操作
8、系统可能的操作是1、修改页表 2、磁盘I/O 3、分配页匡A、仅1、2 B、仅2 C、仅3 D、1、2、348用来选择淘汰哪一页的规则叫做置换策略，或称淘汰算法。如何决定淘汰哪一页？引用位 标识该页最近是否被访问 为“0”该页没有被访问；为“1”该页已被访问改变位 表示该页是否被修改 为“0”该页未被修改；为“1”该页已被修改 页 号 主存块号 中断位 辅存地址 引用位 改变位50最佳算法(OPT算法)当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以 后不再要用的，或者是在最长的时间以后才会用到的那页。先进先出淘汰算法(FIFO算法)什么是先进先出淘汰算法 总是选择在主存中居留时间最长
9、(即最早进入主存)的一页淘汰。先进先出淘汰算法的实现建立一个页面进入主存的先后次序表；建立一个替换指针，指向最早进入主存的页面；当需要置换一页时，选择替换指向的那一页，然后调整替换指 针的内容。51页号表 页面进入主存的先后次序：2451 替换指针 指向最老的一页页号 2 4 5 16 当要调入第6页时：置换第2页将第2页改为6替换指针指向第4页 52在存储分块表中建立次序表 页面进入主存的先后次序：4512 当要调入第6页时：如何处理?512 6710234564251674 2替换指针块号 页号 指针710234566251274 6替换指针 块号 页号 指针53最久未使用淘汰算法(LRU
10、算法)什么是最久未使用淘汰算法 总是选择最长时间未被使用的那一页淘汰。最久未使用淘汰算法的实现用引用位考察页面的使用情况；当访问页面时，将引用位置1，并记时；当要淘汰一页时，选择时间最长的一页淘汰。要精确实现很困难硬件方法：采用计数器软件方法：采用页号栈54软件方法：采用页号栈 页面访问轨迹：451 2 5 64512访问第5页 访问第6页 淘汰第4页 41251256访问4、5、1、2页后栈的内容 访问第5页后，调整栈的内容 访问第6页后，栈的内容 55LRU近似淘汰算法 入口读出替换指针指向的块号移动指针指向下一个存储块 引用位为0?选择该页淘汰，记录该页的页号、块号将该页所在的块号送到替
11、换指针返回置引用位为0YN567102345642514172 4替换指针 块号 页号 引用位 指针60017102345642564072 7替换指针 块号 页号 引用位 指针6011当要调入第6页时，如何处理?49颠簸 颠簸(thrashing)，又称为“抖动”。简单地说，导致系统效率急剧下降的主存和辅存之间的 频繁页面置换现像称为“抖动”。缺页中断率假定程序p共有n页，系统分配m块，有 1mn；若程序p在运行中：成功的访问次数为s，不成功的访 问次数为f；缺页中断率：f=f/(s+f)f=f(r，m，p)；r：置换算法；p：程序特征；m：系统分配的块数 当系统发生抖动是，有效的措施是1、
12、撤销部分进程 2、增加交换区的容量 3、提高用户进程优先级A、仅1 B、仅2 C、仅3 D、仅1、2进程P有5页程序访问页的顺序为：1,2,3,4,1,2,5,1,2,3,4,5；如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；FIFO123412512345页 0123412555344页 112341222533页 21234111255缺 页xxxxxxxxX如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；FIFO123412512345页 0123444512345页 112333451234页 21222345123页 3111234512缺 页
13、xxxxxxxxxx Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。讨论几个问题 最小物理块数的确定最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数 物理块的分配策略物理块的分配策略 固定分配局部置换 可变分配全局置换 可变分配局部置换 物理块分配算法物理块分配算法 平均分配算法 按比例分配算法 考虑优先权的分配算法图4-15两级页表结构 101110780121742n第0页页表
14、1460121023第1页页表114115011023外部页表012345671141151468第n页页表14680121023内存空间页表过大？图4-16具有两级页表的地址变换机构 外部页号P1P2外部页内地址 页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址请求分页系统中，某进程页表如下，页面大小请求分页系统中，某进程页表如下，页面大小4kB4kB，一次访问存储器的时，一次访问存储器的时间为间为100ns100ns，一次快表的访问时间是，一次快表的访问时间是10ns10ns，处理一次缺页的时间是，处理一次缺页的时间是108ns(108ns(含更新含更新TLBTLB和页表的时间
15、和页表的时间)，进程的驻留集大小固定为，进程的驻留集大小固定为2 2，采用最近，采用最近最少使用算法（最少使用算法（LRULRU）和局部淘汰策略。假设）和局部淘汰策略。假设1 1、TLBTLB初始为空；初始为空；2 2 地址转换先访问地址转换先访问TLB,TLBTLB,TLB不命中，再访问页表（忽略访问页表后更新不命中，再访问页表（忽略访问页表后更新TLBTLB的时间）的时间）3 有效位为有效位为0 0表示页不在内存，产生缺页中断，中断处理完后返回产生缺页表示页不在内存，产生缺页中断，中断处理完后返回产生缺页中断的指令重新执行，设有虚地址访问序列：中断的指令重新执行，设有虚地址访问序列：236
16、2H2362H、1565H1565H、25A5H,25A5H,请问请问1、依次访问上述、依次访问上述3个地址，各需要多少时间？个地址，各需要多少时间？2、基于上述访问序列，基于上述访问序列，1565H的物理地址是多少？说明理由的物理地址是多少？说明理由42页模式的定义特征：1.os管理，整个物理内存分系统区和用户区2.内存分为等长页面(frame)：又叫物理页、帧、也框架3.程序分为等长页(page)，又叫逻辑页，页与页面通常等长，4.程序在内存存放时，页内连续、页间不一定连续（即相邻页不一定放在相邻帧中）5.程序不一定完整进入内存（实存虚存）6.地址映射只能采用动态重定位7、页的分配与释放可
17、以用位示图或者链表。算法简单。这种方案，可以解决虚存。解决的实质就是以页为单位部分放入，内存不够的时候换出到辅存。这需要硬件的支持44不连续方式之分段此内容信息工程同学自学57 分段是程序中自然划分的一组逻辑意义完整的信息集合。分段的例：代码分段、数据分段、栈段页。由若干个逻辑分段组成，每个分段有自己的名字，对于一个分段而 言，它是一个连续的地址区。code_addr4KB10代码分段data_addr3KB10数据分段stack_addr2KB10栈段46进程地址空间mm_struct Code SectionData SectionStack图4-17利用段表实现地址映射 作业空间(MAI
18、N)=0030 K(X)=1020 K(D)=2015 K(S)=3010 K30 K20 K15 K10 K40 K80 K段长基址段号(MAIN)=030 K(X)=120 K(D)=215 K(S)=310 K040 K80 K120 K150 K段表内存空间0123120 K150 K58 段 号 s 段 内 位 移 w L B s w B+w第S段段号 段内位移段号 长度 基址取出程序地址(s，w)；用s检索段表；如w0或wL则主存越界；(Bw)即为所需主存地址举例1.若段式存储管理提供用户使用的逻辑地址占24位，其中段内地址占16位，那么用户程序最多分多少段？当把程序转入主存时，每
19、段占用主存的最大连续区域是多少？2.考虑段表如下，计算逻辑地址对应的物理地址（0,430）（2,88）段号基址段长025660012300128211210059 页式系统中用户地址空间一维地址空间段式系统中用户地址空间二维地址空间 分段 页面 信息的逻辑划分 信息的物理划分 段长是可变的 页的大小是固定的 用户可见 用户不可见 w字段的溢出 w字段的溢出自动 将产生越界中断 加入到页号中 l 简单分段：不提供虚存l 请求分段：提供虚存要提供虚存，需要做些什么？请求分段存储管理方式 请求分段中的硬件支持1段表机制段名 段长 段的 基址 存取 方式 访问 字段 A 修改 位 M 存在 位 P 增
20、补位 外存 始址 增补位：这是请求分段式管理中所特有的字段，用于表示本段在运行过程中是否做过动态增长。图4-33请求分段系统的地址变换过程 访问sww段长?符合存取方式?段S在主存?修改访问字段,如写访问,置修改位1形成访问主存地址(A)(主存始址)(位移量w)返回分段越界中断处理分段保护中断处理缺段中断处理是是是否否否图4-32请求分段系统中的中断处理过程 虚段S不在内存阻塞请求进程内存中有合适的空闲区吗？从外存读入段S修改段表及内存空区链唤醒请求进程返回空区容量总和能否满足？空区拼接，以形成一个合适的空区淘汰一个或几个实段，以形成一个合适空区否否是是这种方案，也可以解决虚存。解决的实质就是
21、以段为单位部分放入，内存不够的时候换出到辅存。这需要硬件的支持2005-10-1956段式特性：1.将用户程序空间按逻辑划分为几段（segment），每个段内连续编址，段间是不一定连续编址的2.段模式是以段为单位划分,段内连续存放,段间不一定连续存放（相邻的段不一定放在相邻的区域里）3.段可以全部或者部分放入内存（实存/虚存）4.地址映射只能采用动态重定位5.存储分配方案可以采用动态分区方案。57不连续方式之段页式此内容信息工程同学自学60在段式存储管理中结合分页存储管理技术，在一个分段内 划分页面，就形成了段页式存储管理。code_addr4KB10代码分段data_addr3KB10数据分段stack_addr2KB10栈段6101n段号 页表长度 页表始址 23页号1块号其他0段页表主存段表01块号其他1段页表2页号0图4-23段页式系统中的地址变换机构 段表寄存器段表始址段表长度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度逻辑地址SPW段表012页表1页表2页表3001223051829071421段页式管理有关数据结构例：计算虚地址69732（10000011101000000）的物理地址8位4位12位这种方案，实质是分页方案，不同的是以段为单位分页现在的操作系统可以用分页和分段的技术来提供虚存
