操作系统教学课件4-第四章-存储管理

第第4 4章章 存储管理存储管理引言引言分区式存储管理分区式存储管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理段页式存储管理段页式存储管理用户编程中的内存管理实例分析用户编程中的内存管理实例分析LINUXLINUX内存管理概述内存管理概述小结小结 1引言引言内存管理的需求内存管理的需求内存管理使用的技术内存管理使用的技术分区式管理：固定式、可变式分区、多重分区分区式管理：固定式、可变式分区、多重分区页式管理、页式管理、段式管理段式管理段页式管理段页式管理操作系统的存储管理机构必须解决以下问题操作系统的存储管理机构必须解决以下问题内存分配内存分配存储保护存储保护地址变换地址变换存储共享存储共享存储扩充存储扩充2同时执行多个任务同时执行多个任务编辑文档运行程序网上浏览CD音乐欣赏3为多个程序安排内存为多个程序安排内存PCB1PCB2PCB3程序1程序2程序3数据程序进程控制块PCB采用内存分配与管理技术：采用内存分配与管理技术：实存管理技术：分区式、分页式、分段式存储管理实存管理技术：分区式、分页式、分段式存储管理虚存管理技术：分页式、分段式、段页式存储管理虚存管理技术：分页式、分段式、段页式存储管理 OS 分配内存程序1程序2程序34分区式存储管理分区式存储管理地址重定位地址重定位静态重定位静态重定位动态重定位动态重定位固定式分区固定式分区可变式分区可变式分区多重分区多重分区覆盖与交换覆盖与交换可变分区分配和释放算法可变分区分配和释放算法 5程序的名字空间、地址空间及存储空间符号符号源程序源程序目标目标代码代码可执行可执行代码代码汇编汇编编译编译连接连接地址重定位地址重定位名字空间名字空间地址空间地址空间存储空间存储空间x=x+1R=XR=R+1X=R0K100100+KR=XR=R+1X=R 6静态重定位示意图静态重定位示意图 LOAD 1,300567801003004001000110013001400 LOAD 1,13005678 某程序的地址空间某程序的地址空间内存内存7动态重定位示意图动态重定位示意图8动态重定位地址越界保护示意图动态重定位地址越界保护示意图9第第4 4章章 存储管理存储管理引言引言分区式存储管理分区式存储管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理段页式存储管理段页式存储管理用户编程中的内存管理实例分析用户编程中的内存管理实例分析LINUXLINUX内存管理概述内存管理概述小结小结 10固定分区分配固定分区分配区号区号大小大小起始地址起始地址标志标志123416K32K64K124K20K36K68K132K已分配已分配已分配已分配已分配已分配未分配未分配操作系统操作系统作业作业A作业作业C作业作业B020K36K68K132K第第1分区分区第第2分区分区第第3分区分区第第4分区分区（未分配）（未分配）（b）内存分配图内存分配图（a）分区说明表分区说明表11可变分区说明表可变分区说明表已分配分区说明已分配分区说明 序号序号P P大小大小起址起址状态状态1 18K8K20K20K已分配已分配2 232K32K28K28K已分配已分配3 3未填表项未填表项4 4120K120K92K92K已分配已分配5 5未填表项未填表项序号序号F大小大小起址起址状态状态132K60K空闲空闲2300K212K空闲空闲3未填表项未填表项4未填表项未填表项5未填表项未填表项空闲分区说明表空闲分区说明表 12可变分区示例可变分区示例13可变分区分配和释放算法可变分区分配和释放算法分配算法一般有：分配算法一般有：最佳适应（最佳适应（Best FitBest Fit）算法，它从全部空闲区中找出能满）算法，它从全部空闲区中找出能满足作业需求的容量最小的空闲区分配之，此法的着眼点是足作业需求的容量最小的空闲区分配之，此法的着眼点是使碎片尽量小。使碎片尽量小。最先适应（最先适应（First FitFirst Fit）算法，它按序查找，把最先找到）算法，它按序查找，把最先找到的满足需求的空闲区分配之，此法的目的在于尽量减少查的满足需求的空闲区分配之，此法的目的在于尽量减少查找时间。找时间。最坏适应（最坏适应（Worst FitWorst Fit）算法）算法,此法的目的在于使剩下的空此法的目的在于使剩下的空区最大，减少空区碎片机会。区最大，减少空区碎片机会。下次适应算法（下次适应算法（Next FitNext Fit），此法将空闲区链成环形链，），此法将空闲区链成环形链，每次分配从上次分配的位置开始查找合适的空闲区。每次分配从上次分配的位置开始查找合适的空闲区。14F=F+1置空闲区号置空闲区号F=1=LocF的起始地址的起始地址置置置置F的状态的状态=未填表项未填表项置置置置P的大小的大小=Xk置置P的始址的始址=Loc置置P的的=已分配已分配本次无法分配本次无法分配=申请分配一个申请分配一个xk大小的分区大小的分区F 已超出最大项号？已超出最大项号？F 的状态的状态=未填表项？未填表项？F的大小的大小 Xk?在已分配表中找一个在已分配表中找一个状态状态=未填表项的序号未填表项的序号P返回序号返回序号P否否是是是是否否否否否否大于大于等于等于F的大小的大小 Xk=新空闲块大小新空闲块大小Loc+Xk=新起始地址新起始地址可变分区的分配算法可变分区的分配算法15回收示意图回收示意图空闲区空闲区F1空闲区空闲区2回收区回收区R空闲区空闲区F1 空闲区空闲区F2程序区程序区回收区回收区R 空闲区空闲区F2程序程序程序程序回收区回收区R 程序区程序区程序区程序区回收区回收区R16可变分区的回收算法可变分区的回收算法=置新空闲分区置新空闲分区的大小的大小=Size始址始址=Loc状态状态=空闲空闲在空闲分区表中置在空闲分区表中置F2为未填表项为未填表项分区分区R与与F1邻接？邻接？分区分区R与与F1邻接？邻接？在空闲分区表中在空闲分区表中找一个未填表项找一个未填表项分区分区R与与F2邻接？邻接？SizeSize+F2的大的大小小已分配区说明表中已分配区说明表中置置R的状态的状态=未填表项未填表项Size分区分区R的大小的大小Loc分区的起始地址分区的起始地址否否是是是是是是否否否否请求回收分区请求回收分区R置空闲分区置空闲分区F F1 1的大小的大小 =Size+F1的大小的大小置空闲分区置空闲分区F2的大小的大小=Size始址始址=Loc返回返回17多重分区多重分区基址寄存器基址寄存器1作业作业1作业作业1OS限长寄存器限长寄存器1基址寄存器基址寄存器2限长寄存器限长寄存器218覆盖技术举例覆盖技术举例A 20KB 50KF 30KC 30KD 20KE 40KRAMA 20K覆盖区覆盖区0 50K覆盖区覆盖区1 40KBCFDE19对换（洋葱皮算法）对换（洋葱皮算法）OS基址寄存器基址寄存器作业作业1限长寄存器限长寄存器作业作业2限长寄存器限长寄存器作业作业3作业作业4限长寄存器限长寄存器20多道程序系统内存布局多道程序系统内存布局21多道程序系统内存布局多道程序系统内存布局22第第4 4章章 存储管理存储管理引言引言分区式存储管理分区式存储管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理段页式存储管理段页式存储管理用户编程中的内存管理实例分析用户编程中的内存管理实例分析LINUXLINUX内存管理概述内存管理概述小结小结 23分页式存储管理分页式存储管理实存管理实存管理分页原理分页原理页表页表地址变换机构地址变换机构虚存管理虚存管理页表的扩充页表的扩充缺页中断处理缺页中断处理页面淘汰算法页面淘汰算法快表快表页面共享页面共享24分页硬件分页硬件页表地址表地址寄存器寄存器CPU25逻辑与物理内存分页模型逻辑与物理内存分页模型260#1#2#3#4#5#6#7#分页举例分页举例内存大小为内存大小为3232字字节，分页大小节，分页大小=4=4字节字节物理页号物理页号字节地址字节地址逻辑字节逻辑字节 内容内容27空白页面分配空白页面分配28分页原理分页原理2500 2048=4528192+452=86440 0 0 0 01 0 0 0 0 0 0 0 0 0 0 页内地址页内地址 页号页号相对页号相对页号P页内地值页内地值D15 10 9 0 =1K29页表项页表项页表项区域页表项区域PCB区域区域OS用户区用户区页号页号物理块号物理块号1025171220某作业页表某作业页表逻辑地址逻辑地址页目目录号号页号号页内偏移量内偏移量Linux的的逻辑地址表示形式地址表示形式系系统数据数据结构与构与页表映射原理表映射原理30两级页表两级页表 31两级两级3232位页式结构地址变换位页式结构地址变换32散列页表散列页表33虚拟存储器与物理存储器示意图虚拟存储器与物理存储器示意图34虚拟虚拟存储存储地址地址空间空间codedataheapstack35利用虚拟存储器共享利用虚拟存储器共享36转换分页存储为连续磁盘空间转换分页存储为连续磁盘空间37有效（虚地址）有效（虚地址）操作系统操作系统物理块号物理块号特征特征页号页号作业作业2页表页表页内位移内位移4528物理地址物理地址物理块号物理块号页表起始地址页表起始地址页表长度页表长度页表始址寄存器页表始址寄存器页号页号页内相对位移页内相对位移内存内存8644外存外存LOAD 1,25004522150地址变换过程地址变换过程38请求分页页表请求分页页表页号页号特征特征内存块号内存块号外存块号外存块号修改位修改位访问位访问位淘汰优先级0 0 0110110 1此页不在内存此页在内存39缺缺页页中中断断处处理理流流程程40页表中的有效位与无效位页表中的有效位与无效位 假假设：地址地址长度度为14位位共共16k内存容量内存容量若若1页=2KB则共有共有8页41页面不在主存时的情况页面不在主存时的情况42缺页处理示意图缺页处理示意图43子进程子进程1 1在修改页面在修改页面C C之前之前Copy-on-write44子进程子进程1 1在修改页面在修改页面C C之后之后45页面替换的需求页面替换的需求46页面替换过程页面替换过程47缺页次数与已分得页块数的关系缺页次数与已分得页块数的关系48工作集工作集49缺页频率与已分得页块数的关系缺页频率与已分得页块数的关系50工作集模式下缺页率的变化过程工作集模式下缺页率的变化过程51页面淘汰算法页面淘汰算法先进先出(FIFO)最近最久未使用淘汰算法(LRU)最近不频繁使用淘汰算法(LFU)最优算法(OPT)以上几种淘汰算法中，FIFO算法最简单，但效率不高，有异常现象。LRU的近似算法和LFU是较为实用的算法，效果较好，实现也不难。OPT算法是一种最佳算法，但并不实用，因为要跟踪各页面方可预测未来。而这种预测往往是很困难的。52F FI IF FO O异异常常现现象象53FIFOFIFO淘汰算法淘汰算法7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0缺缺页次数次数=1454最近最久未用页面淘汰算法最近最久未用页面淘汰算法LRULRU 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0缺缺页次数次数=1255最优（最优（OPTOPT）页面淘汰算法）页面淘汰算法 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0缺缺页次数次数=956快表地址映象快表地址映象57快表快表序号相对页号物理块号访问过特征位0 1 2 3 m-1 58快表地址映象快表地址映象59快表的地址映象操作快表的地址映象操作 60页面共享页面共享共享的例程页面共享的数据页面.共享的例程页面作业作业1页表页表作业作业2页表页表作业作业1页表页表作业作业2页表页表公共页表公共页表61页式环境下的代码共享页式环境下的代码共享 62内存映射文件内存映射文件63在在WindowsWindows中采用内存映射中采用内存映射I/OI/O的共享存储的共享存储64页式存储管理的缺点页式存储管理的缺点共享问题共享问题页内零头页内零头系统抖动系统抖动?65第第4 4章章 存储管理存储管理引言引言分区式存储管理分区式存储管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理段页式存储管理段页式存储管理用户编程中的内存管理实例分析用户编程中的内存管理实例分析LINUXLINUX内存管理概述内存管理概述小结小结 66分段存储管理分段存储管理段式地址结构段式地址结构段号段号s 段内位移段内位移w67段式存储管理硬件段式存储管理硬件68分段举例分段举例69段式地址变换段式地址变换段号段号段内地址段内地址s w长度长度 基址基址段表段表第第s段段b+wllb程序地址程序地址70/80KB空/存储分配与地址变换练习题存储分配与地址变换练习题某一采用分段虚拟存储管理的系统某一采用分段虚拟存储管理的系统,假定假定:(1).(1).系统提供有序对虚拟字节地址系统提供有序对虚拟字节地址v=(s,d),v=(s,d),其其中中s s是被访问的虚地址所在的段号是被访问的虚地址所在的段号,d,d是它在该段是它在该段内的偏移量内的偏移量.(2).(2).段表格式如下段表格式如下:(3).(3).内存物理存内存物理存储的当前分区的当前分区状状态如如图:OSJ1J2J3040K80K100K120K160K240K256K其中其中带斜斜线者者为空空闲区区/40K空区/20K空区/段号段号尺寸尺寸(字节字节)是否在内存是否在内存(y或或n)内存起址内存起址(字节字节)J1J2J3OS71续一续一(4).系统采用最佳适应的空闲区分配算法.现在调度进程要调度一个有下述逻辑结构的进程到内存请完成完成:1.1.填写填写该进程相程相应的段表的段表信息信息.2.2.图示虚示虚拟地址地址v v的再定位的再定位过程程.3.3.分分别求出主程序段与数求出主程序段与数据段中字据段中字节地址地址4K4K所所对应的的物理地址物理地址.4.4.画出本次画出本次调度后的内存度后的内存分区状分区状态图.(注注:本本题目不考目不考虑淘汰其淘汰其它它进程的分段程的分段)0 12k1段子程序段044k0段主程序段06k2段数据段调度度进程依段号从小到大的程依段号从小到大的顺序序为该进程程分配内存分配内存,并并设法将当前段全部装入内存法将当前段全部装入内存.72续二续二段号段号尺寸尺寸(字节字节)是否在内存是否在内存(y或或n)内存起址内存起址(字节字节)044Ky160K1212Ky100K6Ky112K 0 4K有效地址有效地址段表地址寄存器+OSJ1J2J3040K80K100K120K160K240K256K164K0段段1段、段、2段段204K36K空区空区2K空区空区/40KB空区空区/73段式存储管理的缺点段式存储管理的缺点段的大小受限制段的大小受限制申请的段长超出了内存空区总长度申请的段长超出了内存空区总长度?74第第4 4章章 存储管理存储管理引言引言分区式存储管理分区式存储管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理段页式存储管理段页式存储管理用户编程中的内存管理实例分析用户编程中的内存管理实例分析LINUXLINUX内存管理概述内存管理概述小结小结 75段页式管理作业地址空间和地址结构段页式管理作业地址空间和地址结构主程序段主程序段子程序段子程序段数据段数据段04K8K12K15K16K04K8K04K8K12K10K(b)段号段号(s)段内页号段内页号(p)页内地址页内地址(w)(a)76段页式地址映射段页式地址映射77段页式系统中的地址变换机构段页式系统中的地址变换机构段表寄存器段表寄存器段表始址段表始址段表长度段表长度 段超长段超长段号段号s页号页号p页内地址页内地址 块内地址块内地址块号块号页表页表段表段表01230123页表长度页表长度页表始址页表始址b78PentiumPentium计算机逻辑地址到物理地址变换计算机逻辑地址到物理地址变换79Intel PentiumIntel Pentium分段原理分段原理GDTR80段描述符缓冲存储器段描述符缓冲存储器81段表段表0 x00cf9a000000ffff=0000 0000 1100 1111 1001 1010 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111GDDPL82段描述表段描述表83I386-CPUI386-CPU页表地址寄存器页表地址寄存器84奔腾计算机分页结构奔腾计算机分页结构85第第4 4章章 存储管理存储管理引言引言分区式存储管理分区式存储管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理段页式存储管理段页式存储管理用户编程中的内存管理实例分析用户编程中的内存管理实例分析LINUXLINUX内存管理概述内存管理概述小结小结 86用户编程中的内存管理实例分析用户编程中的内存管理实例分析basefree_listprev初始状态初始状态0bpbasefree_list0第一次内存申请之后第一次内存申请之后typedef long Align;typedef long Align;/*/*与长整数边界对与长整数边界对齐齐*/union header union header /*/*块首块首*/struct struct union header*next;union header*next;/*/*下个空块下个空块*/unsigned int size;unsigned int size;/*/*块大小块大小*/s;s;Align x;Align x;/*/*强制块对齐强制块对齐*/;87用户编程中的内存管理实例分析（续）用户编程中的内存管理实例分析（续）通常情况通常情况basefree_listprev0p88Malloc.h分析（一）分析（一）定义存储分配单位headertypedef long Align;/*与长整数边界对齐*/union header /*块首*/struct union header*next;/*下个空块*/unsigned int size;/*块大小*/s;Align x;/*强制块对齐*/;typedef union header Header;nextsize89Malloc.hMalloc.h分析（二）分析（二）定义定义headerheader为自定义类型为自定义类型定义从定义从osos中申请内存的最小量中申请内存的最小量10241024个个headerheader#define NALLOC 1024 /*#define NALLOC 1024 /*请求的最小单位数请求的最小单位数*/说明三个函数说明三个函数static Header*morecore(unsigned int nu);/static Header*morecore(unsigned int nu);/从内存管理中申请。从内存管理中申请。void*Malloc(unsigned int nbytes);void*Malloc(unsigned int nbytes);/从用户区申请。从用户区申请。void Free(void*ap);/void Free(void*ap);/将空区链入用户空区管理链中。将空区链入用户空区管理链中。90Malloc.hMalloc.h分析（三）分析（三）#include#include typedef long Align;typedef long Align;/*for alignment to long boundary*/*for alignment to long boundary*/union header union header/*block header:*/*block header:*/struct struct union header*next;union header*next;/*next block if on Free list*/*next block if on Free list*/unsigned int size;unsigned int size;/*size of this block*/*size of this block*/s;s;Align x;Align x;/*force alignment of blocks*/*force alignment of blocks*/;typedef union header Header;typedef union header Header;#define NALLOC#define NALLOC 1024 1024 /*minimum#units to request*/*minimum#units to request*/static Header*morecore(unsigned int nu);static Header*morecore(unsigned int nu);void*Malloc(unsigned int nbytes);void*Malloc(unsigned int nbytes);void Free(void*ap);void Free(void*ap);91MallocMalloc函数分析（一）函数分析（一）定义空区链基础元素定义空区链基础元素 basebase定义空区链起始搜索指针定义空区链起始搜索指针 free_listfree_list转换申请的字节数转换申请的字节数nbytesnbytes为为nunitsnunits个个headerheader单位单位nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1;nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1;使得当使得当nbytes=nbytes=sizeof(Header)sizeof(Header)时，分到时，分到2 2个个Header,Header,而不而不是是3 3个个HeaderHeader。当。当nbytes=0nbytes=0时，可得到时，可得到1 1个个HeaderHeader。多出一个多出一个headerheader结构，用于记录本块空区的大小和下一块空区的地址。结构，用于记录本块空区的大小和下一块空区的地址。建立空区链建立空区链 basefree_listprev092MallocMalloc函数分析（二）函数分析（二）检索空闲区链表检索空闲区链表利用指针利用指针p p和和prevprev检索。检索。p p为检索指针，为检索指针，prevprev是紧跟其后是紧跟其后的指针。的指针。1 1、找到空块、找到空块大小正好，则返回可用区地址（大小正好，则返回可用区地址（p+1)p+1)空块大于申请量空块大于申请量2 2、没找到合适的空块、没找到合适的空块调用调用morecore(munits)morecore(munits)从系统中要求分配，分配成功，新空块插入链中，继续从系统中要求分配，分配成功，新空块插入链中，继续检索空区链；检索空区链；失败，则返回失败，则返回NULLNULL。p(p+1)Headernunitsppfree_listprev 93Malloc函数分析（三）函数分析（三）#include#include my_malloc.hstatic Header base;/*定义空闲链头，存储块划分的最小单位*/static Header*free_list=NULL;/*定义空闲链查询起始指针free_list*/*Malloc:常用存储区分配函数*/void*Malloc(unsigned int nbytes)Header*p,*prev;/检索指针，p指向最终分配的快首址，prev指向分配位置的前一块。unsigned int nunits;nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1;/计算分配的Header个数 if(prev=free_list)=NULL)/*若为NULL，则为空链，否则free_list为搜索起始的位置*/base.s.next=free_list=prev=&base;base.s.size=0;/*定义空闲链初始结构*/for(p=prev-s.next;prev=p,p=p-s.next)if(p-s.size=nunits)/*够大*/if(p-s.size=nunits)/*正好*/prev-s.next=p-s.next;else /*偏大，切出一部分*/p-s.size-=nunits;/*计算剩余空块大小，首址不变*/p+=p-s.size;/*指出被分配块起始地址,保留低地址部分为空区*/p-s.size=nunits;/*填好被分块的大小*/free_list=prev;/*记录上个位置*/return(void*)(p+1);/*跳过管理块，指向可用位置地址*/if(p=free_list)*搜索一圈了吗？否：比较下一个，是：向系统申请新内存块*/if(p=morecore(nunits)=NULL)return NULL;/*内存无空闲区*/*结束for 无限循环*/*函数结束*/basefree_listprev094morecoremorecore函数分析函数分析static Header*morecore(unsigned int nu)static Header*morecore(unsigned int nu)char*cp;char*cp;Header*up;Header*up;if(nu NALLOC)if(nu s.size=nu;up-s.size=nu;/填好填好headerheader结构中的结构中的sizesize内容为申请的内容为申请的HeaderHeader数目数目Free(up+1);Free(up+1);/将申请到的空区链入空区链中。将申请到的空区链入空区链中。return free_list;return free_list;/返回空区链检索指针返回空区链检索指针free_listfree_list。95Free函数分析函数分析Free(void*ap)Header*bp,*p;bp=(Header*)ap-1;/*指向空区管理块header*/for(p=free_list;!(bpp&bps.next);p=p-s.next)/确定空块的插入位置if(p=p-s.next&(bpp|bps.next)/插入点在链尾端（最大）或者在链头（最小）break;/*插入的空块在空闲连的两端位置*/if(bp+bp-s.size=p-s.next)/*回收区紧挨空闲区低地址部分*/bp-s.size+=p-s.next-s.size;bp-s.next=p-s.next-s.next;elseelsebp-s.next=p-s.next;/bp-s.next=p-s.next;/无论哪种情况跳出for，这个语句都是对的if(p+p-s.size=bp)/回收区紧挨空闲区高地址部分 p-s.size+=bp-s.size;p-s.next=bp-s.next;elsep-s.next=bp;p-s.next=bp;free_list=p;pbpbpppbpfree_listpbpbpbppbppbps.nextbps.nextp=p-s.nextp=p-s.nextpbpbpp&bps.nextbpp&bps.nextpbp96应用应用Malloc和和Free的作业要求的作业要求参考讲义上给出的应用参考讲义上给出的应用p192p192，设计应用，设计应用mallocmalloc和和freefree函数的例子。函数的例子。可以根据讲义上的应用程序可以根据讲义上的应用程序test.ctest.c，对应用内容，对应用内容进行变更。进行变更。97第第4 4章章 存储管理存储管理引言引言分区式存储管理分区式存储管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理段页式存储管理段页式存储管理用户编程中的内存管理实例分析用户编程中的内存管理实例分析LINUXLINUX内存管理概述内存管理概述小结小结 98LinuxLinux的三级分页的三级分页99LINUXLINUX内存管理概述内存管理概述一级页表一级页表二级页表二级页表三级页表三级页表物理页物理页虚拟地址虚拟地址一级页一级页PFNPFNPFN二级页二级页三级页三级页页内位移页内位移PGD图图4.24 三级页表示意图三级页表示意图100LINUXLINUX的三级页表结构的三级页表结构101I386-CPUI386-CPU页表地址寄存器页表地址寄存器102保护模式下保护模式下虚拟地址到虚拟地址到物理地址的物理地址的转换转换103LinuxLinux分页地址映射分页地址映射104Linux Linux 页面共享页面共享105页表项页表项例如：例如：0 x70 x10070 x2007表示为用户页面、可写、且页面在内存表示为用户页面、可写、且页面在内存物理页面基址为物理页面基址为:0 x0、0 x1000、0 x2000106LinuxLinux的进程虚存空间示意图的进程虚存空间示意图逻辑地址逻辑地址0 xFFFFFFFF:0 xC0000000:0 x00000000107填写的目录项个数、填写的目录项个数、4个字节、初值为个字节、初值为01100000000=512+256=7681024-768=256指出指出0号页表号页表pg0的起始地址的起始地址指出指出1号页表号页表pg1的起始地址的起始地址用户虚拟空间地址用户虚拟空间地址 0-3G系统虚拟空间地址系统虚拟空间地址 3G-4G确定页目录程序确定页目录程序（4K4K起始）起始）_PAGE_OFFEST=0 xC0000000=3G=1100 0000 0000 0000 0000 0000 0000 0000108初始页表加载初始页表加载12K12K11000000000000000000000000000000=3G8k12k16k常数常数_PAGE_OFFSET_PAGE_OFFSET为系统空间的虚拟地址与物理地址之间的差距，定义于为系统空间的虚拟地址与物理地址之间的差距，定义于include/asm-i386/page.hinclude/asm-i386/page.h109初始页目录与页表映射初始页目录与页表映射766个空白个空白项254个空白个空白项0 xC00000000 x00000000110段选择器格式段选择器格式/段描述符格式段描述符格式TI=0段描述符在GDT中,TI=1段描述符在LDT中RPL:表示请求者使用处理器的特权级别，0-3级，0级为系统态111GDT/LDTGDT/LDT表分布表分布112进程的虚进程的虚拟管理数拟管理数据结构据结构113虚存数据成员虚存数据成员114进程的进程的AVLAVL树树115vm_area_structvm_area_struct数据结构示意图数据结构示意图Vm_area_structVm_endVm_startVm_flagsVm_inodeVm_opsVm_next虚拟内存操作函数集虚拟内存操作函数集nopage()advise()sync()protect()Open()close()unmap()swapout()swapin()进程的虚拟地址空间进程的虚拟地址空间虚拟内存区域虚拟内存区域116LINUXLINUX物理页块的分配和释放物理页块的分配和释放空闲页链表空闲页链表2n54321 0mem_map_tmem_map_t0mem_map_t16k页面位图128K位32k页面位图64K位位图位图map8k页面位图512K位4k页面位图1M位876543210物理块号物理块号物理内存物理内存4KB4KB4KB4KB4KB456n117位图与空闲区的关系位图与空闲区的关系118Buddy Buddy 分配算法分配算法119Slab Slab 分配算法分配算法120LinuxLinux源代码参考书源代码参考书LinuxLinux 内核源代码情景分析（上、下册）内核源代码情景分析（上、下册）毛德操、胡希明著，浙江大学出版社，毛德操、胡希明著，浙江大学出版社，20012001出版出版 121第第4 4章章 存储管理存储管理引言引言分区式存储管理分区式存储管理分页式存储管理分页式存储管理分段式存储管理分段式存储管理段页式存储管理段页式存储管理用户编程中的内存管理实例分析用户编程中的内存管理实例分析LINUXLINUX内存管理概述内存管理概述小结小结 122小结小结基本概念基本概念重定位重定位地址变换机构地址变换机构虚拟存储器虚拟存储器主要管理技术及其数据结构主要管理技术及其数据结构分区、分页、分段分区、分页、分段存储分配算法存储分配算法淘汰算法淘汰算法存储管理系统调用使用的例子存储管理系统调用使用的例子LinuxLinux中内存管理技术中内存管理技术123练习题练习题一个一个3232位的虚拟存储系统有两级页表，其逻辑地位的虚拟存储系统有两级页表，其逻辑地址中，第址中，第2222到到3131位是第一级页表，位是第一级页表，1212位到位到2121位是位是第二级页表，页内偏移占第二级页表，页内偏移占0 0到到1111位。一个进程的地位。一个进程的地址空间为址空间为4GB4GB，如果从，如果从0XC00000000XC0000000开始映射开始映射4MB4MB大小页表，请问第一级页表所占的大小页表，请问第一级页表所占的4KB4KB空间映空间映射在什么位置，并说明理由。（注意射在什么位置，并说明理由。（注意B B代表字节，代表字节，一个一个3232位地址占位地址占4 4字节）字节）124文件系统的数据成员文件系统的数据成员125同学信箱同学信箱#includemain()intp1,p2;while(p1=fork()=-1);/*创建子进程p1*/if(p1=0)putchar(b);else while(p2=fork()=-1);/*创建子进程p2*/if(p2=0)putchar(c);elseputchar(a);/*执行父进程*/126同学信箱同学信箱make制作工程文件命令，在文件Makefile中说明工程文件的相互关系。例子：all:testtest:test.o my_malloc.o cc test.o my_malloc.o -o testTest.o:test.c my_malloc.hmy_malloc.o:my_malloc.c my_malloc.hclean:rm testrm*.o 1271.在my_malloc.c中，返回语句是这么写的：return(void*)(p+1)-为什么要加一呢？2.在morecore中，Free(up+1)-加一？3.在Free中，bp=(Header*）ap-1-为什么要减一？4.还有在后面的print_list中，if(pfree_list)printf(used!n);-pfree_list?同学信箱同学信箱-续续128print_list(void)print_list(void)Header*p;Header*p;int i=0;int i=0;printf(base:%X,base.next:%X,base.next.next:%X,free:%Xn,printf(base:%X,base.next:%X,base.next.next:%X,free:%Xn,&base,&base,base.s.next,base.s.next-s.next,free_listbase.s.next,base.s.next-s.next,free_list););for(p=&base;p-s.next!=free_list;p=p-s.next)for(p=&base;p-s.next!=free_list;p=p-s.next)i+;i+;printf(block%d,size=%d,i,p-s.size);printf(block%d,size=%d,i,p-s.size);if(p free_list)if(p free_list)printf printf(“used!used!n n”);/);/下次查空区起点下次查空区起点+1+1处，应提示：处，应提示：over!over!elseelseprintf(free!n);printf(free!n);同学信箱同学信箱-续续129130