chap4(33-34).ppt

1、基本分页页面和物理块,1.划分成大小相等的物理块 2.从0开始按顺序编号 3.大小为2n,1. 分成与物理块相等的页面 2.也是从0开始编号 3.最后一页可能不满一页,0 1 2 8 9 10 ,0,页表,0 8,1,1 10,2 2,2,3,页内碎片,3 9,基本分页页表:实现页号和物理块号的映射,1.系统为内存中的每个进程都配备一张页表。 2.页表中记录逻辑页面所存储的物理块号及该页面的存取控制。 3.所有页表都存放在内存的物理块中。 4.系统设置页表寄存器(PTR)记录正在执行进程页表的起始地址和长度； 5.未执行进程的页表始址和长度存在其PCB中。,0 8 1 10 7 3 9,0 2

2、1 1 53 2 19,0 1 7 ,基本分页地址转换机构,内存,逻辑地址A（2进制、16进制）,页内位移,物理地址,根据物理地址到内存中读取数据,读取数据访问内存2次,具有快表的地址变换机构 基本页式管理中，CPU每取一个数据，都要两次访问内存： 第一次访问内存：访问页表（存放在内存中），取得物理块号。 第二次访问内存，从相应的物理地址取出数据。 使CPU的速度降低近1/2。（用时间换空间） 为提高地址变换速度，用联想寄存器构成“快表”。用以存放最近访问过的页表项。,4、3 基本分页存储管理方式,为了提高访问速度： 使用联想寄存器做成快表。 在地址转换过程中： 先从快表中查找页表项，找到后将

3、物理块号送入物理地址寄存器中。 若在快表中没找到，再从慢表中找，找到后将物理块号送入物理地址寄存器中。 同时，将该页表项复制到快表中。,具有快表的地址变换机构,4、3 基本分页存储管理方式,CPU,快表（寄存器）,内存,页表（慢表）,4、址变换过程： 在CPU给有效地址后，由地址变换机构将页号送入快表中，与快表中的表项进行比较，若在快表中，则取出相应的物理块号，并送到物理寄存器中计算物理地址。 若不在快表中，则在内存的表页中查找，若找到，将物理块号送入物理寄存器，同时将该表项调入快表。若快表已满，则找到一个认为不再需要的表项进行对换。,4、3 基本分页存储管理方式,5、在进行地址变换的时候，先

4、从快表中查找页表项，若找不到，再在慢表中查找。 6、由于成本的关系，快表不可能做得很大，通常只有16256个寄存器，即存放16256个页表项。 7、快表中存放的是最近访问的页面对应的页表项。,4、3 基本分页存储管理方式,具有快表的地址变换机构,页表始址,页表长度,=,页号,页内地址,+,输,入,寄,存,器,页号,块号,1,6,6,页内地址,越界,例：设访问内（主）存的时间为200毫微秒，访问高速缓冲存储器的时间为40毫微秒，查快表的命中率可达90%（假定系统同时查找快表和慢表） 分别计算基本地址变换和具有快表的地址变换，CPU读取一个数据的平均时间： 基本地址变换=200*2=400毫微秒

5、快表=（40+200）*0.9+（200+40+200）*0.1=260毫微秒,4、3 基本分页存储管理方式,练习：已知某用户作业划分为5个页面，每个页面的大小为1K，每个页表项需要两个字节，该作业在装入过程中形成如下页表，请将下列操作中的逻辑地址转换成物理地址。,习题1：,4,2,7,3,9,R,W,W,R,E,store R1 , 3015 load R1 , 5110 store R1 , 5122,若某计算机系统1个物理块的大小为1K，每个页表项需要2个字节，请回答： (1)一个物理块中可存储多少个页表项？ (2)若只用1个物理块存储页表，则该系统能够存储的作业最大为多少字节？ 思考：

6、若页表需要的空间超过了1个物理块，该如何处理？,4、3 基本分页存储管理方式,离散分配方式建立页表两级、多级页表,4、3 基本分页存储管理方式,将页表进行分页 并离散地将各个页表页面存放在不同的物理块中,页表,0,1,2,0,1,2,为离散分配的页表再建立一张页表，称为外层页表，在其中记录了每个页表页面存放的物理块号。,4、3 基本分页存储管理方式,页表-0,页表-1,页表-2,外层页表,为了区分，将存放页表的物理块称为页表物理块，存放指令和数据的物理块称为数据物理块。,4、3 基本分页存储管理方式,页表-0,页表-1,页表-2,外层页表,页表物理块,数据物理块,外层页表物理块,为了进行地址映

7、射，需要设置外层页表寄存器，用来存放外层页表的内存起始地址和长度。,4、3 基本分页存储管理方式,页表-0,页表-1,页表-2,外层页表,某操作系统采用基本分页存储管理方式，每个物理块的大小为4MB，每个页表项需要4个字节，若采用二级页表结构，则允许进程的最大长度是多少？,4、3 基本分页存储管理方式,在二级页表结构中, Load r1 1560000,用户作业,1560000,3000,外层页表寄存器,若一个页面的大小为1K，每个页表项需要2个字节， 请将逻辑地址1560000转换成物理地址： （1）1560000在哪个作业页面中？页内位移？ （2）该页面的页表项在哪个页表页面中？在该页表页

8、面中的页内位移是多少？,4、3 基本分页存储管理方式,页号=1560000/1k=1523 页内位移=1560000%1K=448,外层页号=1523/512=2 页内位移=1523%512=499,4、3 基本分页存储管理方式,外层页号P1,外层页内地址P2,页内地址d,如何将一维逻辑地址分解成上面三部分？ 例如：某系统采用两级页表的基本分页系统，一个页面的大小为L，每个页表项需要M个字节，请将逻辑地址A转换成：,转换方法： 每个页面存放的页表项数：N=L/M （1）计算外层页号P1：外层页号是指地址A在外层页表中的页号。 逻辑地址A对应的页号为：K =A/N 第K个页号所在的页表物理块：

9、H=K/N H即为外层页号P1,4、3 基本分页存储管理方式,（2）计算外层页内位移P2： 外层页内位移就是页号K是第H个页表物理块中第几个页表项。 P2=K % N （3）计算页内地址d： 页内地址是指地址A在第K页的页内位移。 dA N,4、3 基本分页存储管理方式,具有两级页表的地址转换机构：,外部页号P1,外部页内地址P2,页内地址d,逻辑地址,起始地址 长度,+,+,b,d,外部页表,第P1个页表物理块,物理地址,4、3 基本分页存储管理方式,外层页表寄存器,存放正在执行进程的页表,基本分页存储管理方式中存储保护的实现： 将逻辑页号与页表寄存器中的页表长度进行比较，以确定逻辑地址是否

10、合法。 将本次操作与该页的存取控制进行比较，以确定本次操作是否合法。,4、3 基本分页存储管理方式,存储管理方式中： 分页存储管理方式的目的：提高内存的利用率 分段存储管理方式的目的：是为了满足用户（程序员）在编程和使用上的多方面要求。 用户的需求： 方便编程 信息共享 信息保护 动态增长 动态链接,4、4 基本分段存储管理方式,分段系统的基本原理 一个作业可划分为若干个分段，每个段定义了一组逻辑信息，分段是用户可见的。 每个段都有自己的名字，通常用段号代替段名，每个段都从0开始编址，段长不固定，由编译系统确定。 每个逻辑地址的访问用二维地址表示：LOAD 1, X|（其中X代表段名（号），Y

11、代表段内位移）,4、4 基本分段存储管理方式,系统使用段表来记录用户作业的每个段在内存的起始地址、段长等信息。 由硬件地址转换机构根据逻辑地址中的段名（号）在段表中查找相应段在内存的起始地址。 根据起始地址与段内位移实现逻辑地址到物理地址的转换。,4、4 基本分段存储管理方式,段表： 内存分配以段为单位，一个作业若干个段可分配在不相邻的区域内，一个段占用一个连续分区。 为使程序正确运行，能从内存中找到每个逻辑段对应的内存地址，应建立段表。 系统为每个在内存的进程建立一个段表，给出逻辑的段号与该段在内存的起始地址之间的对应关系。,4、4 基本分段存储管理方式,段表结构如下： （按照逻辑段号有序）

12、,4、4 基本分段存储管理方式,段表存放在内存中：系统设置段表寄存器，在其中存放正在执行进程的段表的起始地址和长度，而没有执行的进程段表的起始地址和长度存放在其PCB中。,段表中设置段长的目的： 每个段的长度是不同的，用基址加段长可确定该段的合法存储空间。 在地址变换过程中，通过段内位移与段长的比较，来确定访问的段内位移是否合法。 硬件地址变换机构 任务：完成逻辑地址到物理地址的转换。 地址转换过程：例如：LOAD 1,2|100,4、4 基本分段存储管理方式,段表始址,段表长度,+,1k,6k,600,4k,500,8k,200,9200,段号,段长,基址,0,1,2,3,段号 2,位移量

13、100,+,8292,越界,4、4 基本分段存储管理方式,地址变换过程,越界,段长,基址,将下列逻辑地址转换成物理地址,（1）STORE R1，0，70 （2）STORE R1，1，20 （3）LOAD R1，3，20 （4）LOAD R1，3，100 （5）JMP 2，100,分页与分段的主要区别： 相似之处：采用离散分配方式，且都通过硬件地址变换机构来实现逻辑地址到物理地址的变换。 区别： 页是信息的物理单位，分页的目的是为了提高内存的利用率。段是信息的逻辑单位，分段的目的是为了能更好地满足用户的需要。,4、4 基本分段存储管理方式,页的大小固定且由系统决定，而段的长度不固定，决定于用户编

14、写的程序。 分页的逻辑地址空间是一维的，线性的，而分段的作业地址空间是二维的。 信息共享 分段比分页更容易实现信息的共享。 可重入码（纯代码）：允许多个进程同时访问的代码，并且不允许任何进程对它进行修改，在内存中只有一个副本。,4、4 基本分段存储管理方式,例如：某系统中40个用户，每个人有40K的私有数据，并共享一个大小为160K的程序（editor），若该程序为可重入码，计算这40个用户共占用多少内存？ 分页系统实现信息共享：多用户系统中的每个用户，分别在自己的页表中为共享部分代码建立相应页表项（多页则建立多个表项），记录共享代码所在的物理块号。（例如共享程序editor，假定一个页面的大

15、小为4KB）,4、4 基本分段存储管理方式,分页系统中共享editor 的示意图：,进程1,ed1,ed2,ed40,data1,data10,进程2,ed1,ed2,ed40,data1,页表,21,22,59,60,61,70,21,22,60,71,80,主存,ed1,ed2,ed40,data 1,data 10,data 1,data 10,分段系统实现信息共享：只需在每个进程的段表中为共享代码设置一个段表项。 注意：不同的进程可以使用不同的段号共享同一段代码,4、4 基本分段存储管理方式,分段系统中共享 editor 的示意图:,进程1,editor,Data 1,进程2,editor,Data 2,进