考虑支持多道程序的两种连续分配方式：

1、固定分区分配：缺乏灵活性，会产生大量的内部碎片，内存的利用率低。

2、动态分区分配：会产生很多外部碎片，虽然可以用“紧凑”处理，但是带价高。

如果允许将一个进程分散装入不相邻分区中，便可充分利用内存，而不需再“紧凑”，产生了非连续分配方式。

连续分配方式：为用户进程分配的必须是一个连续的内存空间。

非连续分配：为用户进程分配的可以是一些分散的内存空间。

非连续分配三种方式：基本分页存储管理、基本分段存储管理、段页式存储管理。

一、基本分页存储管理

1、概念

分页存储管理将内存空间的逻辑地址（相对地址）空间分成若干页，从0开始；

把内存的物理地址（绝对地址）空间分成与内存空间大小相同的若干块，为进程分配内存时，以块为单位。

进程的最后一页经常装不满一块，称为“页内碎片”。

2、如何实现地址的转换

①算出逻辑地址对应的页号（页号 = 逻辑地址/页面长度（取整数部分））

②知道该页号对应页面在内存中的起始地址

③算出逻辑地址在页面内的偏移量（页内偏移量 = 逻辑地址%页面长度（取余数部分））

④物理地址 = 页面始址 + 页内偏移量

如果每个页面大小为2^K  B，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号。

例：假设用32个二进制位表示逻辑地址，页面大小为2^12B = 4096B = 4KB，

逻辑地址2，用二进制表示应该是00000000000000000000000000000010

若0号页在内存中的起始地址为X，则逻辑地址2对应的物理地址应该是X+000000000010。

逻辑地址4097，用二进制表示应该是00000000000000000001000000000001

若1号页在内存中的起始地址为X，则逻辑地址4097对应的物理地址应该是X+000000000001。

（可以这样理解，一个页面大小为4097，逻辑地址正好为一个页面大小，所以也是下一个页面的开始，页面数为1偏移量为0）

3、逻辑地址结构

地址结构包含两个部分，前一部分为页号，后一部分为页内偏移量。

如果有K位表示页内偏移量，则说明该系统中一个页面的大小是2^K个内存单元。

如果有M位表示页号，则说明该系统中，一个进程最多允许有2^M个页面。

4、页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

①一个进程对应一张页表。

②进程的每一页对应一个页表项。

③每个页表项由页号和块号组成。

④页表记录进程页面和实际存放的内存块之间的对应关系。

⑤每个页表项的长度是相同的，页号是隐含的。

为什么页号是隐含的？

例：假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？

答：4GB = 2^32B，4KB = 2^12B

因此会被分为2^32/2^12 = 2^20个内存块，范围应该是0~（2^20）-1

因此至少要20个二进制位才能表示，因此至少需要3个字节才够。

（每个字节8个二进制位，3个字节共24个二进制位）

各页表项会按顺序连续地存放在内存中，

如果该页表在内存中存放的起始地址为X，则M号对应的页表项一定是存放在内存地址为X+3*M。

因此只需要知道页表存放的起始地址和页表项长度，即可找到各页号对应的页表项存放的位置。

本例中一个页表项站3B，如果有n个页面，则该进程的页表总共会占3*n个字节。

二、基本地址变换机构

 步骤：

①根据逻辑地址计算出页号、页内偏移量。

②判断页号是否越界。

③查询页表，找到页号对应的页表项，确定页面存放的内存块号。

④用内存块号和页内偏移量得到物理地址。

⑤访问目标内存单元。

例题：

例：若页面大小L为1K字节，页号2对应的内存块号b = 8，将逻辑地址A=2500转换为物理地址E。

答：1KB = 2^10B，说明页内偏移量占10位。

页号2对应的内存号b=8。

第一步：计算页号、页内偏移量

页号P = A/L = 2500/1024 = 2

页内偏移量W = A%L = 2500%1024 = 452

第二步：求块号

页号为2，对应的内存块号为8。

第三步：求物理地址

E = b*L+W = 8*1024+452 = 8644

三、具有快表的地址变换机构

上面的地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表，可能连续很多次查到的都是同一个页表项，快表可减少访问页表的次数。

快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。

快表存放在更高速的存储器中，页表存放在内存中。

最近使用过的页表项会放入快表。

步骤：

①CPU给出逻辑地址，由硬件算得页号、页内偏移量，将页号与快表中的所有页号比较。

②如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出对应的内存块号，再讲内存块号与页内偏移量拼接成物理地址，最后访问物理地址对应的内存单元，因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。

③如果没有找到页号，则需要访问页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接成物理地址，最后，访问该物理地址对应的内存单元，因此，若快表未命中，则访问需要两次访存。

例题

例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构，访问一次快表耗时1us，访问一次内存耗时100us，若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少？

答：（1+100）*0.9+（1+100+100）*.0.1 = 111us

如果是快表和页表同时查找，应该是（1+100）*0.9+（100+100）*0.1 = 110.9us

若不采用快表机制，则需要100+100 = 200us

四、两个地址变换机构对比

基本分页存储管理的基本概念
基本地址变换机构
具有快表的地址变换机构

以下是基本分页存储管理的基本概念

引入

因为连续分配方式的各种缺点，而产生了非连续分配方式。

知识总览

把“固定分区分配”改造为“非连续分配版本”

基本分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。

分页存储管理的基本概念

简而言之：将内存分为若干大小相等的分区（假设大小为a），每个分区称为==“页框”==。==每个分区有一个编号，从0开始。==将进程分为若干大小为a的部分（最后一部分<=a）。页框不能太大，否则产生过大的内部碎片。（如进程大小为20，a为3，那么进程就分为6个3和1个2，2就是最后一个页框存储的大小，多出来的1就是内部碎片）。

操作系统以页框为单位为各个进程分配内存空间。
进程的页面与内存的页框是一一对应的。

如何实现地址的转换

分页大概是分成这样：

如何计算：
页号=逻辑地址/页面长度。
页内偏移量=逻辑地址%页面长度。

与二进制的联系：（好复杂 我好像没在课上听过）
后k位是余数，是会变的，是页内偏移量。
其余是除数，是不变的，是页号。

逻辑地址结构

感觉就是上面内容的总结。

页表

为了知道进程的每个页面在内存中的存放位置，操作系统要为每个进程建立一张页表。

1. 一个进程对应一张页表
2. 进程的每一页对应一个页表项
3. 每个页表项=页号+块号
4. 页表记录进程页面和实际存放的内存块之间的对应关系
5. 每个页表项的长度相同，页号隐含

关于为什么每个页表项长度相同，页号隐含：

以下是基本地址变换机构

基本地址变换机构

基本地址变换机构也属于基本分页存储管理，它是用于实现逻辑地址到物理地址转换的一组硬件机构。

逻辑地址到物理地址转换的步骤：

文字版步骤：

第二步举个例子：算出的页号P是5，页表长度M是5，说明需要的地址在第五页，而已有的页为0、1、2、3、4这5个，越界。

用一个例题来深刻理解这个知识：

对页表项大小的进一步探讨

简而言之：让一个页表项更大，更方便（？）。

以下是具有快表的地址变换机构

局部性原理

简而言之：如果一个存储单元被访问了，那么跟它同一个“局部”的之后很有可能被访问。

什么是快表TLB

快表，又称为联想寄存器（TLB），是一种访问速度比内存快得多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

流程图：

引入快表之后，地址的变换过程

注意：快表没有命中则要对目标逻辑地址进行两次访存。
（一次找，一次放进快表）

一个例子：

总结

全知识整理目录

 

操作系统整理的目录，包括了整理的所有操作系统的知识。

---

概述

什么是基本地址变换机构？

基本地址变换机构，可以理解为将逻辑地址转变为物理地址的一组硬件机构，这些硬件需要做些什么事情，才能将逻辑地址转换为物理地址。

页表寄存器

基本地址变换机构，可以借助进程的页表将逻辑地址转换为物理地址。

通常情况下，会在系统中设置一个页表寄存器（PTR），存放页表在内存的起始地址F和页表长度M。

 当进程还是未执行的时候，页表的起始地址和页表长度，放在进程控制块当中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

 ps：页面的大小是2的整数幂。

设页面大小为L，逻辑地址A到物理地址E的变换过程是怎么样的呢？

首先根据页号P和页内偏移量W（如果用十进制来计算，那么P=A/L，W=A%L，在实际计算机运行的过程当中，逻辑地址是固定不变的，那么就会让其计算的速度更快）。

比较页号P和页表长度M，若P>=M，则产生越界中断，否则继续执行。（页号是从0开始的，页表长度至少是1，因此P=M时也会发生越界）

页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度，取出该页表项内容b，即为内存块号

计算物理地址E=b*L+W（可以看见，页面大小L是已知的，偏移量W是比较好计算的，只有页表项内容b是不好计算的，也是最容易出错的）

待续。。。