搜索
3.3程序装入技术这一节属于补充内容，教材有涉及，但很粗略，对于程序设计中动态链接库、静态链接库理解有重要作用可执行程序的生成步骤图3.10高级程序处理过程源程序目标模块编译库函数装入模块链接编辑执行目标模块内存可执行程序的装入•？如何装入待执行的程序及其所需的数据•？何时将程序的逻辑地址转换为物理地址•3种装入方式：绝对装入、重定位装入和运行时动态装入。绝对装入•程序运行之前，按照程序的逻辑地址，将程序和数据装入内存指定的地方。•实现简单，无须进行逻辑地址到物理地址的变换。绝对装入缺点：•程序每次必须装入同一内存区；•程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址；•程序的修改（增加或删除指令）将引起整个程序中指令地址的变动；•程序中的所有存储引用，例如函数调用或过程调用等，在装入之前都必须转换为物理地址，这不利于存储共享。重定位装入•允许将程序装入与逻辑地址不同的物理内存空间。即程序可以装入到内存的任何位置，其逻辑地址与装入内存后的物理地址无直接关系。•但是，必须进行地址映射，将逻辑地址转换为物理地址。•静态重定位技术：地址映射在程序装入时进行，以后不再更改程序地址。重定位装入•有利于程序代码和数据的共享。因为装入程序时，可以将其中的某些存储引用的逻辑地址映射为内存中已有的共享区的物理地址。•但是，静态重定位不允许程序在内存中移动。这不便于进程交换和紧凑拼接操作，也很难实现多道程序环境下，多个程序同时装入内存的要求。•故，重定位装入方式只适合于单道程序环境。运行时动态装入•指，程序的地址转换不是在装入时进行，而是在程序运行时动态进行。•运行时动态装入需要硬件支持，即重定位寄存器，用于保存程序在内存中的起始地址。•程序被执行时，通过重定位寄存器内的起始物理地址和指令或数据的逻辑地址计算其物理地址。•运行时动态装入有利于多道程序环境下，进程的换进/换出及实现紧凑技术。可执行程序的链接形成•？目标模块如何链接成装入模块呢•静态链接•动态链接：装入时动态链接和运行时动态链接静态链接•指，程序被装入内存之前，必须完全链接成一个装入模块，将其中的存储引用全部转换为相对地址跳转语句。并将多个目标模块链接成为一个模块，使装入模块中的每一条指令具有相对于整个模块的第一条语句的逻辑地址。•静态链接生成的装入模块可以采用重定位装入或运行时动态装入方式。•静态链接需要花费大量的处理机时间。而其中的很多模块将不会运行，浪费存储空间和处理机时间。链接图3.11目标模块链接成装入模块模块1…ifx1thencallmm1elsecallmm2…模块mm1模块mm2(a)目标模块模块1…ifx1thenelse…模块mm1模块mm2(b)装入模块？执行？执行动态链接•指，不用事先链接所有目标模块形成一个完备的装入模块，而是生成一个含有未被链接的外部模块引用的装入模块，这些外部模块可以在装入时链接，或运行时链接。装入时动态链接•指，当系统装入含有未链接的外部模块引用的装入模块时，每当遇到一个外部模块引用，则查找相应的目标模块。将其装入内存，并将模块内的指令地址转换为相对于整个装入模块起始地址的相对地址。•优点：有利于目标模块的更新与升级；有利于代码共享；有利于扩充软件的功能，可以将扩充部分作为动态链接模块。•但是，可能链接一些不会执行的模块，浪费存储空间和处理机时间。运行时动态链接•指，外部模块引用直至程序执行时才装入内存，并链接到装入模块中，进行地址转换。•可以解决静态链接和装入时动态链接都面临的存储空间和处理机时间浪费问题，不需要执行的模块就不会装入内存。•广泛用于事务处理系统，如航空售票系统、银行管理系统等。•操作系统自身的一些特殊处理例程，如错误处理例程，也无需事先全部装入内存。3.4简单存储管理技术简单存储•相对于虚拟存储而言，指为了实现简单，执行之前，操作系统必须将待执行的程序全部装入内存。•然而，现代操作系统大都支持虚拟存储功能，允许进程装入部分程序即可开始执行，其余部分保留在外存。当执行所需的部分不在内存时，中断进程执行，使之阻塞等待，直到相应部分装入内存。？程序在内存中如何组织•连续存储:需要内存中的一块连续的、足够大的分区。•如果内存中没有足够大的连续空闲分区，但存在总量足够的独立小分区，即外零头。系统要么拒绝分配空间，要么采用紧凑技术拼接外零头。•非连续存储：允许进程的程序和数据分别装在内存的不同分区中。•必须登记一个进程分到的所有分区的位置、大小、使用情况（如是否共享等）等信息。•常用的非连续存储技术：分页存储技术、分段存储技术及其结合。图3.12内存的连续存储与非连续存储…OS进程P…基地址(a)连续存储进程P（2）…OS…进程P（1）…进程P（n）…进程的组成基地址长度…P(1)2604200…P(2)1240300……………P(n)6500300…(b)非连续存储连续存储管理•最简单的存储管理技术•要求系统配置专门的硬件实现快速地址转换和存储保护。•处理机硬件基址寄存器(Baseregister)界限寄存器(Boundsregister)连续存储管理•基址寄存器：存放当前执行进程所在分区的物理存储单元的起始地址。•界限寄存器：存放当前执行进程所在分区最后一个物理存储单元的地址，限定进程的执行范围，保护其他进程不被非法访问。•基址寄存器和界限寄存器被多个进程共享，只有当前执行进程才使用它们。•装入时，进程分区的基地址值和分区的最后一个物理存储单元的地址值，分别填入该进程PCB的相应字段中。•当进程被调度执行时，将PCB中对应的进程基地址值写入基址寄存器中，并将进程获得的内存分区最大地址值，填入界限寄存器中。•当进程被交换出/换入内存时，上述两个地址值也会发生改变。地址映射与存储保护•逻辑地址转换成物理地址—取基址寄存器中的值，加上逻辑地址值，生成一个物理地址•地址越界检查—取界限寄存器中的值，与第一步计算的结果进行比较。如果生成的物理地址超出了界限范围，产生一个中断，报告地址越界。否则，继续该指令的执行。程序部分数据部分内存基址寄存器加法器逻辑地址界限寄存器比较器越界中断物理地址图3.13连续存储管理的地址转换和越界检查简单分页存储管理•连续存储：存在外零头，浪费存储空间。“紧凑”需要系统额外开销。•非连续存储：允许将一个进程的程序和数据离散存储在多个独立的分区中，消除了外零头。基本原理•分页存储管理技术是一种特殊的固定分区方法。•系统事先将物理内存划分成许多尺寸相等的页框(PageFrame)，并将进程分割成许多大小相同的页面(Page)，页面与页框大小相同。•分区：进程的逻辑地址空间是连续的、一维的、线性地址，进程的每一条指令和数据的地址相对于第一条语句的地址而定。•分页：进程被分割成许多页面。每个页面内的指令和数据是连续的，它们的地址相对于其所属页的第一条语句的地址，称为页内偏移量。•逻辑地址被分为两部分：页号和页内偏移量页号页内偏移量151090图3.14分页管理的逻辑地址表示•当一个进程被装入物理内存时，系统将为该进程的每个页面分配一个独立的页框。•同一个进程的多个页面不必存放在连续的多个页框中。例如•假设内存能提供16个空闲页框，进程P1被分割成4个页面，装入内存中的0号至3号页框。进程P2被分割成3个页面，装入4号至6号页框。进程P3被装入7号至12号页框，如图3.15(a)所示。•此时，进程P4请求分配5个页框大小的存储空间，但内存只有3个空闲页框。于是，将暂时不运行的P2交换出内存，如图3.15(b)所示。•然后，再将P4装入4、5、6、13、14号页框，如图3.15(c)所示。图3.15进程装入到离散的页框中0123456789101112131415P1.2P1.1P1.0P1.3P2.0P2.1P2.2P3.0P3.1P3.2P3.3P3.4P3.5页框号内存(a)依次装入P1、P2、P3P1P2P3空闲0123456789101112131415P1.2P1.1P1.0P1.3P3.0P3.1P3.2P3.3P3.4P3.5页框号内存(b)换出P2P1空闲P3空闲0123456789101112131415P1.2P1.1P1.0P1.3P4.0P4.1P4.2P3.0P3.1P3.2P3.3P3.4P3.5P4.3P4.4页框号内存(c)装入P4P1P4P3空闲P4数据结构：页表•页表：系统为每个进程建立一张页面映射表。•用于记载进程的各页面到物理内存中页框的映射信息。•进程的每个页面依次对应页表中的一个表项，其中包含相应页在内存中对应的物理页框号和页面存取控制权限等字段。页号页框号00112233进程P1页表页号页框号0-1-2-进程P2页表页号页框号071829310411512进程P3页表页号页框号041526313414进程P4页表图3.16进程P1、P2、P3、P4的页表数据结构：页框表•空闲页框表：登记系统中剩下的空闲页框情况图3.17空闲页框表151413地址变换•硬件机制，实现逻辑地址到物理地址的转换•分页系统中的地址变换过程如下：（1）根据逻辑地址,计算出页号和页内偏移量；（2）用页号检索页表，查找指定页面对应的页框号；（3）根据页框号和页内偏移量，计算出物理地址。页表寄存器•页表寄存器：实现快速地址映射，存储执行进程的页表起始地址。•页表寄存器设置在处理机硬件中。•当进程被创建时，其页表起始地址记载于进程PCB中。•当进程被调度执行时，页表的起始地址将从该进程的PCB中取出，并填入页表寄存器中。•进行地址变换时，处理机从页表寄存器中查找页表的地址。页号偏移量逻辑地址物理地址页框号偏移量页表寄存器页表起始地址内存页框号页表地址转换程序+偏移量图3.18分页系统的地址变换过程页框大页表•大逻辑地址空间，页表非常大，需要占用相当大的内存空间。•比如，32位逻辑地址空间，假设页面大小为4KB（212），则4GB（232）的逻辑地址空间将被划分成220个页面。大页表•若采用一级页表，则其内将包含1兆（220）个页表项。若按字节寻址，一个页表项占4B，则一级页表需要占用4MB（222）内存空间。•不可能将4MB的页表保存在一个连续区中。•那么，如何处理大页表的存储与检索呢？二级页表•将一个大页表全部保存在内存中。•首先，将其分割，并离散地存储在内存的多个页框中。•为之建立二级页表，记录被分割的各个页面存储在哪些页框中，也称为外层页表（OuterPageTable）。•对于4GB的进程，若采用二级页表，则对应的二级页表结构如图：……4GB的用户进程4MB的一级页表4KB的二级页表图3.194GB进程的二级页表结构多级页表•对于某些机器，二级页表也可能非常大。可以采用多级页表，对外层页表再进行分页，将各个页面离散地存储到不相邻接的物理页框中•虽然，对大页表而言，多级页表方法消除了对较大的连续内存空间的需要，但并未解决大页表占用较大的内存空间的问题，建立多及页表反而会增加额外的存储空间。大页表•最好的解决办法是采用虚拟存储技术，内存中仅装入页表的一部分。•即只将当前需要的部分页表项装入内存，其余页表项驻留在磁盘上，需要时再将它们装入内存。•若采用多级页表，对于正在运行的进程，必须将其外层页表调入内存，而内层页表只需调入几页就可以了。反置页表(InvertedPageTable)•一般情况下，系统从进程的角度为每个进程建立一张页表，页表的表项按页号排序。•这种方法可能导致一个大进程的页表太大，占据大量的内存空间。•反置页表：从内存的角度建立页表，整个系统只有一张页表。页表的表项基于内存中的每一个物理页框设置，页表项按页框号的顺序排序。其中还必须包含页框对应的页号及其隶属进程的标识符等信息。反置页表•通常，反置页表需要包含成千上万个表项，利用进程ID和页号检索其中某一个表项的速度很慢。•可以根据进程ID和页号构建Hash表。Hash表的每一项指向反置页表中的某一项。•但是，可能会出现多个逻辑地址被映射到一个Hash表项的情况。需要通过链接指针将多个冲突的映射链接起