《操作系统课件os5》由会员分享，可在线阅读，更多相关《操作系统课件os5（59页珍藏版）》请在金锄头文库上搜索。
1、存储器管理 尽管最近存储器的容量在不断扩大。但软件的种类、功能等所需的空间也在急剧膨胀，存储空间仍然是宝贵资源。 本章主要讨论内存管理：内存分配、分页存储管理与分段存储管理方法等。第5章5.1 程序的装入和链接在多道程序的环境下，把一个用户的源程序变成可以的内存执行的程序，需要如下步骤：编译：通过编译程序把用户的源代码编译成若干个目标模块(Object Module)。链接：把目标代码和所需的库函数连接起来形成可装入的模块(Load Module)。装入：由装入程序把装入模块装入到内存。源代码库可装入模块目标模块编译链接装入内存一、程序的装入如果程序为多个模块，则需要进行链接；单个目标模块无须
2、进行链接。在Unix/Linux链接有多种方式。单模块的装入方式单模块的装入方式：绝对装入方式：按模块中的地址，将程序和数据装入到内存对应位置。可重定位方式：在装入程序时，根据当时内存的实际使用情况，重新调整装入的内存位置，把程序装入到内存的适当地方。1、Absolute Loading Mode(ALM)绝对装入方式绝对装入方式：在编译时，已经知道程序要驻留在内存的位置，如地址1024开始，则编译程序直接产生从该地址向上开展的目标代码，目标代码中全部采用绝对地址。Jump kLoad mkmJump 1424Load 2224142422241024汇编/编译Jump 1424Load 22
3、24142422241024装入2、Relocatable Loading Mode-RLMALM存在问题存在问题：多道程序环境下，无法预先知道程序的装入位置。重定位装入重定位装入：在程序装入时，把目标程序中的指令和数据的相对地址(有效地址)修改成装入位置处内存的物理地址。静态重定位静态重定位：地址变换只是在装入时一次性完成，以后不在改变。Jump kLoad mkmJump 400Load 120040012000汇编/编译Jump 1400Load 2200140022001000作业空间内存空间装入3、Dynamic Run-Time Loading可重定位装入方式存在问题可重定位装入方
4、式存在问题：虽然可以把程序装入到内存的任意位置，但不允许程序在内存中移动位置。如果程序在内存中移动，就必须对程序中的地址进行修改才能正常运行。动态运行时装入程序动态运行时装入程序：把装入模块装入内存时，不把程序中的地址转换成实际的物理地址，而是在运行时才进行地址转换。Jump kLoad mkmJump 400Load 120040012000汇编编译Jump 400Load 1200140022001000作业空间内存空间装入4001000+1200运行时 二、程序的链接链接的主要功能：把经汇编、编译所得到的一组目标模块和所需的库函数目标模块一起，装配成一个完整的装入模块。有三种链接方法：静
5、态链接装入时动态链接运行时动态链接1、静态链接将几个模块链接装配成一个模块需要解决两个问题：修改相对地址：编译产生的目标模块起始地址为0，除第一块外，其余的相对地址全部要修改。模块ACall BReturn模块BCall CReturn模块CReturn0L-10M-10N-1模块AJSR “L”Return模块BJSR “L+M”Return模块CReturn0L-1LL+M-1L+ML+M+N-1变换外部调用符号：把外部调用符号变换成相对地址形成可执行文件。静态链接静态链接：进行事先链接，以后不再拆开的链接方式。可执行文件2、装入时动态链接优点：便于软件的版本修改和更新：只要对需要修改的模
6、块修改后编译即可，保证所有的软件同步升级。便于实现目标模块的共享：实现多个模块共享一个模块、而不要每个程序都含有该模块的拷贝。模块ACall BReturn模块BCall CReturn模块CReturn模块AJSR “L”Return模块BJSR “L+M”Return模块CReturn0L-1LL+M-1L+ML+M+N-10L-10M-10N-1装入过程装入过程独立目标模块独立目标模块在内存中在内存中3、运行时动态链接装入链接的问题：程序运行期间、整个模块的结构不变静态结构。在运行期间有些模块(如错误处理)可能不用、但一直占据内存。运行时链接：在运行期间需要一个模块才装载一个模块。模块A
7、Call BReturn模块BCall CReturn模块CReturn模块AJSR “L”Return模块BJSR “L+M”Return模块CReturn0L-1LL+M-1L+ML+M+N-10L-10M-10N-1独立目标模块独立目标模块在内存中在内存中运行时装入运行时装入运行时装入运行时装入4、Linux的静态和共享函数库Linux生成目标代码： gcc -c 源程序文件名将生成一个与源程序同名的.o目标代码文件。直接用目标代码文件生成可运行文件 gcc o可执行文件名 目标代码文件 目标代码文件 源程序文件生成一个可执行文件。Linux C有两种风格的函数库：静态函数库共享函数库静
8、态函数库的维护生成一个静态函数库ar r libtools.a m1.o m2.o m3.o ar -Linux的归档命令。r表示生成一个名字为libtools.a的静态函数库。 如果该函数库不存在，创建函数库。 如果函数库存在，库中没有指定的目标模块，则把目标模块追加到函数库中；如果函数库中有同名的目标模块存在，替换成当前的目标模块。注意：函数库名一定是以“lib”开头，后缀为“.a”ar 的其他参数： t-显示在函数库中的所有目标模块 tv-显示库中目标模块的详细信息。使用自己的静态函数库使用自己的静态函数库使用自己创建的静态函数库：gcc -o可执行文件名可执行文件名 静态函数库名静态函
9、数库名 源程序源程序 目标模块目标模块说明：在编译、连接时把静态函数库作为一个参数加到命令行中即可。例如： gcc omax1 libtools.a m1.o m2.o m3.o 在链接时也可以使用如下参数：gcc -L函数库位置函数库位置 -l函数库名函数库名 源程序源程序 目标模块目标模块其中：-L 指出函数库在什么路径。如:-L.表示当前目录。默认的路径“/usr/lib”可以不给出。-l 给出函数库名，但不要前缀和后缀。如:-ltools表示使用函数库libtools.a使用自己的共享函数库使用自己的共享函数库生成自己的共享函数库：生成共享函数库和生成一个程序一样简单。gcc m1.o
10、 m2.o mn.o shared -o共享函数库名参数： -shared 要求gcc输出生成一个共享函数库 共享函数库名-前缀为“lib”，后缀为“.so”使用共享函数库链接方法同上。如果在同一位置静态函数库和共享函数库都可用，默认链接共享函数库，要用静态函数库时使用链接参数“-static”。使用自己的共享函数库使用自己的共享函数库检查共享函数库的使用ldd 可执行文件名例如：ldd mmm1 libttl.so = not found libc.so.6=/lib/linc.so.6(0x40001c000) /lib/ld-linux.so.2=/lib/ld-linux.so.2(0
11、x4000000)这说明确实正在使用共享库，但没有找到。/lib/ld-linux.so.2帮助其它共享库装载/动态链接的动态装载器。 指定动态装载器的查找路径方法：在文件“/etc/ld.so.conf”设定。在环境变量LD_LIBRARY_PASTH中设定。 在“/etc/ld.so.conf”设定要求：具有root权限。步骤：用vi编辑/文件，把共享函数库的路径加入到该文件中。退回到系统根目录运行/sbin/ldconfig,用文件/的内容更新缓存文件/etc/ld.so.cache(真正起作用的文件)。这时可以运行在共享库在指定路径的程序。注意：无论何时，任何一个配置目录中的共享文件发
12、生变化，都必须运行/sbin/ldconfig来更新缓存文件/etc/ld.so.cache。使用变量LD_LIBRARY_PATH如果没有root权限，则可以使用LD_LIBRARY_PATH环境变量进行设置。设置：export LD_LIBRARY_PATH=“$LD_LIBRARY_PATH:.”可以用set命令检查以下该命令是否起作用。5.2 连续分配存储管理方式连续分配存储管理有两种方式：单一连续分配方式：在内存中仅驻留一道程序，整个用户区为一个用户独占。适用于：单用户、单任务OS。分区式分配方式：可以分固定分区和动态分区。固定分区式：把内存用户区划分成若干个固定大小的区域，每个区域
13、驻留一道程序。动态分区：根据用户程序大小、动态地对内存进行划分。特点：内存划分成多少分区是可变的。一、单一连续分配方式内存划分：系统区：仅给操作系统使用(可以放在低端或高端)，由于中断向量驻留在低端、一般放在低端。用户区：提供给用户使用的区域。CPUsize划出分区整块分配修改有关数据NYNYNm.size空闲分区大小u.size请求分区大小size不可在分割大小按分区分配算法内存的回收当一个进程运行结束，要释放内存，操作回收内存，并把它插入到空闲区链表中。根据回收区的位置，有四种情况需要处理：空闲区回收区回收区空闲区空闲区回收区空闲区回收区情况1情况2情况3情况4四、动态重定位分区分配紧凑：
14、把空闲区合并成一个连续区域。动态重定位：程序中的相对地址变换是在程序执行期间进行的。8K12K6K18K44K紧凑0Load 250010036525002500相对地址10000重定位寄存器10000Load 25001010036512500+处理机存储器动态重定位分配算法动态重定位分配算法原理：在动态分区分配算法中，当找不到足够大的空闲分区来满足请求的空间时进行“紧凑”。请求分配分区检索空闲分区链找到按动态分区分配方式进行分配空闲分区总和进行“紧凑”返回分区号及首址无法分配返回yNYN五、伙伴系统伙伴系统伙伴系统：内存的有效分区尺寸为2k,LkU；2L=最小的分区尺寸，2U=最大的分区尺
15、寸1MBA：请求100K128KB：请求240K256K128KC：请求64K256K128K64KD：请求256K256K128K64K256K释放A256K128K64K256K释放D256K128K64KE：请求75K256K128K64K释放C256K128K5.3 对换对换：把内存中暂时不能运行的进程或暂时不用的程序和数据，换到外存，以腾出足够的内存空间，把具备运行条件的进程或进程需要的程序和数据换到内存。进程对换：以整个进程为单位进行的对换分时系统。部分对换：以“页”为单位的对换页面对换；以“段”为单位的对换分段对换。两者称部分对换。进程对换时系统必备的功能：对换空间管理；进程的换
16、出；进程的换入。1、对换空间的管理具有对换功能OS外存划分：文件区和对换区。文件区：用于长期保存文件离散分配方式。目标提高存储利用率。对换区：用于短时间存放内存换出的进程，要求较高的换进、换出速度采用连续分配。对换区管理的记录方式：空闲分区表和空闲分区链与内存管理类似。以磁盘块为单位。对换区的分配与回收与动态内存分配算法相同：First Fit、Next Fit、Best Fit。2、进程的换出实质实质：把活动阻塞、就绪状态的进程转挂起状态。 选择被换出的进程实施换出换出进程考虑的因素：处于阻塞或睡眠状态的、优先级最低的进程。无阻塞：选择优先级低的就绪进程。考虑优先级低产生“换进、由换出”，兼
17、顾在内存驻留时间。非共享的程序和数据段。如果是共享的，只能那些引用数-1后为零才能被换出。换出操作：申请对换空间，等申请成功继续。把程序、数据写入交换区，检查写入的正确性。释放进程所占的内存空间。修改被换出的进程的控制块、修改内存分配表。3、进程的换入实质：把挂起状态-活动就绪或阻塞。进程换入考虑的因素：有足够的内存空间“就绪挂起”优先于“阻塞挂起”同一队列中，优先级高、挂起时间长的优先换入。换入操作：多个进程依次换入。申请内存空间，如果申请成功继续。把挂起进程换入。修改进程PCB和内存分配链(表)。如果内存申请失败，首先实施进程换出。分页、分段存储管理方式分页、分段存储管理方式内存分区管理存
18、在问题：固定分区方式：将产生大量的内部“碎块”；动态分区方式：将产生大量的外部“碎块”，而进行“紧凑”则需要额外的开销。思路：把用户的程序空间划分成若干块，它们可以离散分配到内存中非连续的存储区域中。充分利用内存。分类：按程序分块的大小是否固定分为分页存储、分段存储、段页式存储。5.4 分页存储管理方式实现方法实现方法：把用户程序的地址空间划分成若干固定大小的区域(fixed size chunk)，把它们叫“页”（一般1页为1KB）。把内存空间划分成若干和“页”大小相同的物理块，这些物理块叫“页框”(frame)。内存分配内存分配：把用户程序的任一页分配到内存中的任一帧，从而实现非连续的、离
19、散的内存分配。问题问题：如何管理、如何进行地址变换。一、分页存储管理基本方法程序A0页1页2页3页4页5页n页进程A页表00页号 块号1124354859012345678内存9程序B0页1页2页3页4页5页m页进程B页表02页号 块号132637自由页框表块号页表作用：实现页号到物理块号的映射。返回分页存储管理方式的地址结构分页存储管理方式的地址结构地址组成：页号P+(页内地址)位移量d例如：32位地址，011为位移量(4KB/页)，1231为页号，最大可以有1M页。页号P和页内地址d的确定：设逻辑地址空间中的地址为A，页面大小为L:P= INT A / L d= A mod L地址结构地址
20、结构：页号P位移量d12 11031页面大小的确定分页系统中，页面的大小是有硬件的地址结构所决定的。机器确定、页面大小便确定。影响因素：页面内部碎块、内存的利用率页面页表、占用内存页面页面的换出换入效率。计算机类型页面大小(B)IBM AS/400VAXIntel 80386Motorola 6803051251240964096常见机型页面常见机型页面二、地址变换机构分页存储系统中，地址变换机构的任务：把逻辑地址中的页号转换为内存中物理块的块号。注意：页面大小与页框大小一致，无须进行页内地址转换。实现转换：借助于页表。页表的实现：寄存器：变换速度快、成本高，适应小型系统。页表驻留在内存：速度
21、较低、成本低，适应大系统。页表页表驻留在内存的变换机构在系统中设置一个页表寄存器(PTRpage table register)：存放页表在 内存的起始地址和页表的长度；非执行状态该数据保存在进程的PCB中。页表寄存器页表始址 页表长度逻辑地址页号=2 页内地址=12800页号 块号112435+4内存页表越界中断物理地址128具有快表的地址变换机构页表存放在内存时CPU存取数据，访问两次内存：第一次：访问内存页表，找到物理块号+页内地址，形成物理地址。第二次：访问内存，读/写数据。具有快表：在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲存储器联想存储器/快表。工作原理：CPU给出有效
22、地址；如果地址“快表”中，直接读出对应的物理块号，送往物理地址寄存器；再访问内存。如果快表没有对应的地址，从内存“页表”读取地址送往物理地址寄存器，访问内存；把页表项存入快表或把老的页表项换出。不设联想存储器：访问时间延长一倍。具有快表的地址变换机构（续）页表寄存器页表始址 页表长度逻辑地址页号页内地址00页号 块号112435+4内存页表(慢表)越界中断物理地址页号 块号24输入寄存器快表三、两级、多级页表一级页表存在问题：支持的逻辑空间越大，页表就越大，页表所占用的内存空间就越大。如：设32位逻辑空间，页面大小为212B，需要220个表项，每个表项4B，则需要4M的连续内存空间。从两个方面
23、解决：离散分配页表；部分页表驻留在外存：需要时调入内存。1、两级页表实质：把大的页表再进行分页存放，实现存放页表的页面离散存放。外部页表：存放每个页表的物理块号。逻辑地址结构：p1p2d外层页号外层页内地址页内地址3122 2112 110逻辑地址外部页表寄存器+外部页表+页表物理地址101110781742012n外部页表135211212240第0页页表第1页页表12111212第n页页表内存空间01201201201234521121224012111212优点优点：可以把暂时不用的页表存放在外存。但不能没有减少存储空间。2、多级页表结构32位机器用两级页表结构合适。64位用两级将产生非
24、常大的外层页表：如：页面大小为212B,页表大小为210项，则外部页表：242项=4096G个表项。多级页表实质：对大的外部页表进行分页分成若干级外部页表，实现存放外部页表的页面离散存放。第一级第二级第三级页内偏移量外部页表寄存器PFNPFNPFNPFNPage Frame Number四、反置页表(Inverted Page table)分页系统中为每个进程配置一张页表进程配置一张页表，进程的逻辑空间每一页在页表中一个表项页表非常庞大。反置页表反置页表：为每一物理块(页框)分配一个表项，按物理块号排序，表项的内容是页号及所属的进程标识符。反置页表的优缺点：页表的大小与物理空间有关。但只包含调
25、入内存的页面，没有包括未调入内存的进程页面。利用进程ID和页号检索很费时，要通过Hash表进行检索。CPUpidpdiidd第i帧物理地址逻辑地址页表反置页表地址转换过程物理帧号PID页号外部页表5.5 分段存储管理分段存储管理方式引入的目的：物理分页逻辑分段。方便编程：用户把作业分成若干逻辑段，每段有自己的名字和长度，逻辑地址由段名和段内偏移量决定。分段共享：分页实现程序、函数困难。分段保护：便于对信息的逻辑单位进行保护。动态链接：动态链接是以段为单位调入内存。动态增长：实际使用中，数据段的长度不能预先确定，需要动态增加。一、分段系统的基本原理分段：把作业的地址空间划分若干段，每一定义一组逻
26、辑信息：段名、段的长度。段名：用段号来替代。段的长度：由相应的逻辑信息组的(不等)长度决定。逻辑地址：Segment NumberOffset3116 15064K个段64KB长度段表：系统为每段分配一段连续区域，而进程中的各段则离散存放在不同的分区中。段表：记录逻辑段与内存物理位置的对应映射关系。段号段长基址030K40K120K80K215K120K段表(MAIN)=0(x)=1(D)=2内存空间作业空间015K(MAIN)=007K(X)=108K(D)=240K80K120K段表还有：外存基址，状态地址变换机构：段表始址 段表长度段表寄存器2段号段内偏移量100+段号段长基址01K6K
27、16004K25008K32009200段表+越界中断+8292物理地址012内存空间8K为提高数据存取速度，减少内存访问次数，分段存储管理方式增设一个联想存储器。分页与分段的区别分块方式使用碎片长度目的分页存储管理物理分块，系统决定对程序员是不可见，使用简单每个进程只有一个内部碎片，大小不超过1页固定提高内存的利用率分段存储管理逻辑分块，大小与信息块有关，由编译系统划分对程序员可见，使用方便，但难度大每个进程有多个外部碎片不确定便于信息保护与共享，方便用户二、共享与保护可重入代码：纯代码，允许多个进程同时访问同一代码，可重入代码不允许用户对代码进行修改。分页：(p161)实现代码共享、保护比
28、较困难。要求每个进程的每个页表项都指向共享页。分段：实现代码共享、保护简单。只要每个进程的段表项指向共享段就可以实现。三、段页式存储方式基本原理：先把用户的程序分为若干个段，再把每个段划分成若干页。主程序段04K8K12K16K子程序段04K8K数据段04K8K12K段号段内页号页内地址逻辑地址：段页式存储管理的地址转换:段号=3页号=2d逻辑地址段表始址 段表长度段表寄存器+越界中断段号段长页表始址页表长度状态0123页号页框号外存地址状态012+物理地址段表页表采用段页式存储管理方式,访问数据需要三次访存.5.6 Linux存储管理Linux存储管理的特点:“按需分页”的段页式存储管理技术
29、：运行时需要的内容按页调入内存，不执行的内容仍然存放在交换区。高速缓存：缓冲区缓存(Buffer Cache)以块设备标识符和块号作为索引，快速查找数据块，块设备只能通过缓冲区缓存进行存取。页缓存(Page Cache)为加快磁盘文件存取，对于磁盘文件，Linux每次装入一页文件，并将读取的页面存储到页缓存中。交换缓存(Swap cache)交换文件只保存被修改过的页面，如果页面调到内存后未被修改，下次不要在写入交换文件中。硬件缓存(Hardware Cache)CPU常用一个硬件高速缓存，它保存页表的内容，CPU可以直接得到页表的内容，进行地址交换。-快表。Linux中的页表结构：采用三级页
30、表来描述逻辑地址，每一页表项包含下一级页表的页帧号，通过三级转换成物理地址。页表寄存器页表始址 页表长度第一级+第二级第一级页表第二级页表+第三级第三级页表+页内偏移量页帧号偏移量物理地址多级页表的映射过程Linux中页帧的分配与回收数据结构：所有的物理页帧都用数据结构mem_map来进行描述，mem_map则是通过mem_map_t的结构组成链表，在链表中的每个节点描述一个物理页：内容：count记录此页帧的用户数。age描述该页帧的年龄。map_nr描述对应的物理页帧号(PFN)页面的分配采用链表和位图相结合的方法。如图所示，用数组free_area来保存空闲的物理页帧。页帧面分配：在Li
31、nux中页块的分配与回收采用Buddy算法。页块的分配由_get_free_pages()函数和宏定义_get_free_pages()来完成。算法：在free_area数组中，查找大于等于所需的空闲页块。如果空闲页块正好等于所需的大小，则将其从free_area中删除。如果空闲页块大于所需的大小，则将起一分为二，并把该空闲块的后半部分插入到free_area中，如此继续，页帧块回收：页块分配会导致内存碎片，回收要进行重新组合；调用函数free_pages()函数来完成。算法：检查回收块前后是否有空闲块，如果有则进行合并。把空闲块加入到free_area()。Free_area数组结构5640123450mapmapmapmap012345678910内存空间Free_area数组mem_map_t空闲页框List双向链表
