4.3 基本分页存储管理方式

连续分配方式存在的问题与分页存储管理方式的引入

基本分页存储管理方式

• 一、页面与页表
• 二、地址变换机构
• 三、两级和多级页表

将一个进程的逻辑地址空间分成若干个大小相同的片称为页面或页。

把内存空间分成与页面大小相同的若干个存储块，称为块或页框。

2、地址结构（逻辑地址结构）

3、基本分页管理（简单页式存储管理）方式的实现

• 进程的每一页离散地存储在内存的任一存储块当中，为方便查找，系统为每一进程建立一张页面映像表，简称页表。
• 页表实现了从页号到物理块号的地址映射。

二、地址变换机构

• 为了能将用户地址空间的逻辑地址变换为内存空间的物理地址，在系统中必须设置地址变换机构。
• 地址变换机构实现从逻辑地址到物理地址的转换，由于页内地址与物理地址是一一对应的，因此，地址变换机构的任务是借助于页表，将逻辑地址中的页号转换为内存中的物理块号。
• 通过页表将页号转换成内存的块号

因为一页大小=一块大小

所以逻辑地址中的页内地址是可以直接拿来作为物理地址中的块内地址的。

1、基本的地址变换机构

• 页表的功能可以由一组专门的寄存器来实现，一个页表项用一个寄存器。但寄存器成本高，系统页表可能很大，所以页表大多常驻内存。
• 在系统中只设置一个页表寄存器PTR，在其中存放页表在内存中的起始地址和页表的长度。平时，进程没有执行时，页表的起始地址和页表长度存放在进程的PCB中，当调度到进程时，才将这两个数据装入到页表寄存器中。

整个地址变换过程中，一共访问了两次内存。

• 1、由页号和页表的起始地址去访问页表，这是第一次。（页表存储在内存当中）
• 2、有块号和对应的块内地址在组成完整的物理地址去访问内存中的程序来执行，这是第二次访问内存。

3BADH------> 0011 1|011 1010 1101 页号: 07H----->块号：BH ------> 0000 0101 1011 1010 1101（物理地址寄存区寻址范围为1M）----->05BADH–>访问内存

0AFEH-------> 0000 1|010 1111 1110 页号：01H ----> 块号：9-------> 0100 1010 1111 1110----->4AFEH(物理地址)

第二种计算方法：

1. 操作系统 实验1【短作业优先调度算法（C++实现——FCFS\SJF\HRRN）】
2. 操作系统 实验2【动态高优先权优先调度算法 C++实现】
3. 操作系统 实验3【动态分区存储管理 Python实现】
4. 操作系统 实验4【基本分页存储管理 C++实现】

目录

一、实验目的（目的与任务）

二、实验内容（内容、要求与安排方式）

三、实验代码

①创建表示作业的结构体

②编写建立作业的函数

③编写回收作业、释放内存的函数

④编写显示所有作业占用物理块的函数

⑤编写查看作业情况的函数

⑥编写显示内存块使用情况的函数

实验代码

四、实验结果

五、实验总结

一、实验目的（目的与任务）

熟悉并掌握基本分页存储管理的思想。

熟悉并掌握基本分页存储管理的分配和回收方式，并能够模拟实现。

二、实验内容（内容、要求与安排方式）

用高级语言模拟实现基本分页存储管理，要求：

1. 内存空间的初始化——可以由用户输入初始内存空间各个物理块情况。（用二维矩阵的方式按物理块号，逐行给出每个物理块的状态，1——表示已分配，0——表示未分配，并能够将行标、列标转换为对应的物理块号，以查看或修改每一个块的状态，要求：初始时部分物理块已分配）
2. 基本分页的分配过程：由用户输入作业号和作业的大小（这里的大小是逻辑页面数），实现分配过程：空间充足，分配，修改状态矩阵的相应位置的值（值由0转变为1），并用专门的数据记录下该作业占用的物理块的块号，以备删除作业时回收空间。
3. 作业空间的的回收：用户输入作业号，实现分区回收。（通过相应的数据结构找到该作业占有的物理块号，将块号转变成对应的行标、列标，将对应位置的值由1转变成0就完成了回收）
4. 分区的显示：任何时刻，可以查看当前内存的情况。（显示记录内存情况的矩阵的值）
5. 要求考虑：（1）内存空间不足的情况，要有相应的显示；

      （2）作业不能同名，但是删除后可以再用这个名字；

      （3）作业空间回收是输入作业名，回收相应的空间，如果这个作业名不存在，也要有相应的提示。

三、实验代码

①创建表示作业的结构体

typedef struct Ln

{

    int f;        //作业号

    int n;        //作业页数

    int len;      //作业大小

    char name[8]; //作业名

    int y[100];   //页表，下标表示页号，内容表示作业各页所在物理块

    struct Ln *next;

} Ln, *List;

②编写建立作业的函数

//建立新作业

void Create_Pagi(List &L)

{

    int i, flag;

    int m, k;

    List p;

    List n_node;

    n_node = (List)malloc(sizeof(Ln));

    p = L;

    printf(" 亲，请输入作业号 :");

    scanf("%d", &n_node->f);      //输入作业号

    flag = 0;                     //三次输入错误返回上一层

    while (p != NULL && flag < 3) // 查找作业号是否重复

    {

        if (p->f != n_node->f)

            p = p->next;

        else

        {

            printf("\n 亲，该作业已存在您忘记了吗 , 请重新输入 :");

            scanf("%d", &n_node->f);

            p = L; //p 重新指向头结点

            flag++;

        }

    }

    if (flag < 3)

    {

        printf(" 输入作业名称 :");

        scanf("%s", n_node->name);

        printf(" 输入作业的大小 (单位为K):");

        scanf("%d", &n_node->len); //例如1025，作业页数为1，但K不为0，所以+1=2；

        n_node->n = n_node->len / 1024;

        k = n_node->len % 1024;

        if (k != 0)

            n_node->n = n_node->n + 1;

        printf(" 所需要的页数为 :");

        printf("%d\n", n_node->n);

        printf(" 偏移量为%d", k);

        if (n_node->n > num) //放不进去，失败

        {

            printf("\n 对不起亲，内存物理块不足，新建作业失败 \n\n");

        }

        else

        {

            num -= n_node->n; //更新剩余物理块

            m = 0;

            for (i = 0; i <= max; i++)

                if (S[i] == 0 && m < n_node->n) //

                {

                    S[i] = n_node->f; //作业号

                    n_node->y[m] = i; //页表,下标表示页号，内容表示作业各页所在物理块

                    m++;

                }

            printf("\n");

            printf(" 页号\t\t块号\n");

            for (int i = 0; i < m; i++)

                printf(" %d\t\t%d\n", i, n_node->y[i]);

            int a, b;

            while (1)

            {

                printf(" 请输入页号\n");

                scanf("%d", &a);

                printf(" 请输入页内偏移\n");

                scanf("%d", &b);

                if (a < m)

                {

                    printf(" 物理地址：%d\n", n_node->y[a] * 1024 + b);

                    break;

                }

                else

                {

                    printf(" 越界\n");

                    continue;

                }

            }

            if (L == NULL)

                L = n_node;

            else

            {

                p = L; // 查找最后一个节点

                while (p->next != NULL)

                {

                    p = p->next;

                }

                p->next = n_node;

            }

            n_node->next = NULL;

        }

    }

    else

    {

        printf("\n 亲操作错误次数过多 , 已为您返回主菜单 :");

    }

}

③编写回收作业、释放内存的函数

//回收作业、释放内存

void Revoke_Pagi(List &L)

{

    List p, q;

    int x;

    printf(" 请输入要删除的作业号 :");

    scanf("%d", &x);

    p = L; //查找作业；用 p 记录

    q = p;

    while (p != NULL)

    {

        if (p->f == x) //作业号

        {

            printf(" 亲，该作业已为您删除^o^ ");

            break;

        }

        else

        {

            q = p;

            p = p->next;

        }

    }

    if (p == NULL) //p为空说明不存在此作业

    {

        printf("\n 亲，该作业不存在呢^o^\n");

    }

    else //对该作业进行删除

    {

        for (int i = 0; i < p->n; i++)

            S[p->y[i]] = 0; //内存物理块

        num += p->n;

        if (p->f == q->f) //要删除的是头结点

        {

            L = p->next;

        }

        else

        {

            q->next = p->next;

        }

    }

}

④编写显示所有作业占用物理块的函数

//显示所有作业占用的物理块

void Printf_Pagi(List L)

{

    //int i = 0;

    printf("\n 内存物理块分配情况 :\n");

    List p = L;

    printf(" 该作业信息 :\n");

    printf(" 作业号 \t 作业名称 \t 作业页数 \t 所用物理块 \n");

    while (p != NULL)

    {

        printf(" %d\t\t", p->f);

        printf(" %s\t\t", p->name);

        printf(" %d\t\t", p->n);

        int i;

        for (i = 0; i < p->n; i++)

            printf(" %d", p->y[i]);

        printf("\n");

        p = p->next;

    }

}

⑤编写查看作业情况的函数

//查看作业

void Look_Pagi(List L)

{

    int z;

    printf(" 亲，请输入要查询的作业号： ");

    scanf("%d", &z); //输入查看的作业号

    List p = L;

    while (p != NULL)

    {

        if (p->f == z) //相同直接输出

        {

            printf(" 作业号 \t 作业名称 \t 作业页数 \t 所用物理块 \n");

            printf(" %d\t\t", p->f);

            printf(" %s\t\t", p->name);

            printf(" %d\t\t", p->n);

            int i;

            for (i = 0; i < p->n; i++)

                printf(" #%d", p->y[i]);

            printf("\n");

            break;

        }

        else

            p = p->next;

    }

    if (p == NULL)

        printf(" 要查询的作业不存在 \n");

}

⑥编写显示内存块使用情况的函数

//显示内存块使用情况

void Show_Pagi()

{

    printf(" 内存物理块分配情况 \n");

    for (int i = 0; i <= max; i++)

    {

        printf(" %d\t", S[i]);

        if (i % 10 == 9)

            printf("\n");

    }

}

实验代码

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <bits/stdc++.h>

typedef struct Ln
{
    int f;        //作业号
    int n;        //作业页数
    int len;      //作业大小
    char name[8]; //作业名
    int y[100];   //页表,下标表示页号，内容表示作业各页所在物理块
    struct Ln *next;
} Ln, *List;

int S[100];    //内存物理块，0：未使用，非0：已使用
int max = 99;  //记录内存的物理块数,值为A[100]最大下标
int num = 100; //记录内存未使用物理块数

void Create_Pagi(); //建立分页作业
void Revoke_Pagi(); //回收作业
void Look_Pagi();   //显示所有作业占用的物理块
void Show_Pagi();   // 查看作业
void Pagi();        //分页界面

void Create_Segm(); //创建分段作业
void Show_Segm();   //显示作业信息
void Suggest();     //建议模块
void Dispatch();    //调用模块
void Segme();       //分段界面
void main_s();      //主界面

//建立新作业
void Create_Pagi(List &L)
{
    int i, flag;
    int m, k;
    List p;
    List n_node;
    n_node = (List)malloc(sizeof(Ln));
    p = L;
    printf(" 亲，请输入作业号 :");
    scanf("%d", &n_node->f);      //输入作业号
    flag = 0;                     //三次输入错误返回上一层
    while (p != NULL && flag < 3) // 查找作业号是否重复
    {
        if (p->f != n_node->f)
            p = p->next;
        else
        {
            printf("\n 亲，该作业已存在您忘记了吗 , 请重新输入 :");
            scanf("%d", &n_node->f);
            p = L; //p 重新指向头结点
            flag++;
        }
    }
    if (flag < 3)
    {
        printf(" 输入作业名称 :");
        scanf("%s", n_node->name);
        printf(" 输入作业的大小 (单位为K):");
        scanf("%d", &n_node->len); //例如1025，作业页数为1，但K不为0，所以+1=2；
        n_node->n = n_node->len / 1024;
        k = n_node->len % 1024;
        if (k != 0)
            n_node->n = n_node->n + 1;
        printf(" 所需要的页数为 :");
        printf("%d\n", n_node->n);
        printf(" 偏移量为%d", k);
        if (n_node->n > num) //放不进去，失败
        {
            printf("\n 对不起亲，内存物理块不足，新建作业失败 \n\n");
        }
        else
        {
            num -= n_node->n; //更新剩余物理块
            m = 0;
            for (i = 0; i <= max; i++)
                if (S[i] == 0 && m < n_node->n) //
                {
                    S[i] = n_node->f; //作业号
                    n_node->y[m] = i; //页表,下标表示页号，内容表示作业各页所在物理块
                    m++;
                }
            printf("\n");
            printf(" 页号\t\t块号\n");
            for (int i = 0; i < m; i++)
                printf(" %d\t\t%d\n", i, n_node->y[i]);
            int a, b;
            while (1)
            {
                printf(" 请输入页号\n");
                scanf("%d", &a);
                printf(" 请输入页内偏移\n");
                scanf("%d", &b);
                if (a < m)
                {
                    printf(" 物理地址：%d\n", n_node->y[a] * 1024 + b);
                    break;
                }
                else
                {
                    printf(" 越界\n");
                    continue;
                }
            }
            if (L == NULL)
                L = n_node;
            else
            {
                p = L; // 查找最后一个节点
                while (p->next != NULL)
                {
                    p = p->next;
                }
                p->next = n_node;
            }
            n_node->next = NULL;
        }
    }
    else
    {
        printf("\n 亲操作错误次数过多 , 已为您返回主菜单 :");
    }
}

//回收作业、释放内存
void Revoke_Pagi(List &L)
{
    List p, q;
    int x;
    printf(" 请输入要删除的作业号 :");
    scanf("%d", &x);
    p = L; //查找作业；用 p 记录
    q = p;
    while (p != NULL)
    {
        if (p->f == x) //作业号
        {
            printf(" 亲，该作业已为您删除^o^ ");
            break;
        }
        else
        {
            q = p;
            p = p->next;
        }
    }
    if (p == NULL) //p为空说明不存在此作业
    {
        printf("\n 亲，该作业不存在呢^o^\n");
    }
    else //对该作业进行删除
    {
        for (int i = 0; i < p->n; i++)
            S[p->y[i]] = 0; //内存物理块
        num += p->n;
        if (p->f == q->f) //要删除的是头结点
        {
            L = p->next;
        }
        else
        {
            q->next = p->next;
        }
    }
}

// 显示所有作业占用的物理块
void Printf_Pagi(List L)
{
    //int i = 0;
    printf("\n 内存物理块分配情况 :\n");
    List p = L;
    printf(" 该作业信息 :\n");
    printf(" 作业号 \t 作业名称 \t 作业页数 \t 所用物理块 \n");
    while (p != NULL)
    {
        printf(" %d\t\t", p->f);
        printf(" %s\t\t", p->name);
        printf(" %d\t\t", p->n);
        int i;
        for (i = 0; i < p->n; i++)
            printf(" %d", p->y[i]);
        printf("\n");
        p = p->next;
    }
}

// 查看作业
void Look_Pagi(List L)
{
    int z;
    printf(" 亲，请输入要查询的作业号： ");
    scanf("%d", &z); //输入查看的作业号
    List p = L;
    while (p != NULL)
    {
        if (p->f == z) //相同直接输出
        {
            printf(" 作业号 \t 作业名称 \t 作业页数 \t 所用物理块 \n");
            printf(" %d\t\t", p->f);
            printf(" %s\t\t", p->name);
            printf(" %d\t\t", p->n);
            int i;
            for (i = 0; i < p->n; i++)
                printf(" #%d", p->y[i]);
            printf("\n");
            break;
        }
        else
            p = p->next;
    }
    if (p == NULL)
        printf(" 要查询的作业不存在 \n");
}

// 显示内存块使用情况，不分作业
void Show_Pagi()
{
    printf(" 内存物理块分配情况 \n");
    for (int i = 0; i <= max; i++)
    {
        printf(" %d\t", S[i]);
        if (i % 10 == 9)
            printf("\n");
    }
}

//以上分页代码
/*------------------------------------------------------------------*/
//以下分段代码

using namespace std;

struct seg //定义结构体段seg
{
    long cap; //该段的长度
    long phy; //物理地址
    long rea; //该段实际地址
};

struct Table //定义结构体段表Table
{
    seg s[10];     //段表中每个段的属性
    char name[50]; //段表名
    int flag;      //标记是否被调度内存
    int num;       //作业中包含段数
    long total;    //作业所占用的存储空间
};

Table Ts[10];
long mem = 0;
int Tnum = 0;
long k = 0;
long base = 0;

//创建分段作业
void Create_Segm()
{
    printf("\n");
    printf("请输入要创建的作业名：");
    cin >> Ts[Tnum + 1].name;
    printf("请输入该作业的段数：");
    cin >> Ts[Tnum + 1].num;
    int p = 0;
    for (int i = 1; i <= Ts[Tnum + 1].num; i++)
    {
        printf("请输入该作业第%d段的大小：", i);
        cin >> Ts[Tnum + 1].s[i].cap;  //该作业每段的大小
        Ts[Tnum + 1].s[i].phy = p;     //物理地址赋值给p
        p = p + Ts[Tnum + 1].s[i].cap; //每段的物理地址赋值给加和
    }
    printf("\n");
    Ts[Tnum + 1].flag = 0; //标记是否被调度
    Ts[Tnum + 1].total = p;
    Tnum++;
}

//显示作业信息
void Show_Segm(int i)
{
    printf("\n作业p%d:", i);
    cout << "名字:" << Ts[i].name << endl;
    cout << "该作业所占用的存储空间:" << Ts[i].total << endl;
    if (Ts[i].flag == 0)
        cout << "作业未调用" << endl;
    else
        cout << "作业已调用" << endl;
    cout << "段 号    物理始址    内存始址    长度" << endl;
    for (int j = 1; j <= Ts[i].num; j++)
    {
        cout << setw(3) << j << setw(11) << Ts[i].s[j].phy;
        if (Ts[i].flag == 0)
            cout << setw(11) << " ";
        else
            cout << setw(11) << Ts[i].s[j].rea;
        cout << setw(11) << Ts[i].s[j].cap << endl;
    }
}

//调用作业
void Dispatch()
{
    cout << endl;
    cout << "输入要调度的作业：p";
    int n;
    cin >> n;
    if (n <= 0 || n > Tnum) //排除非正常可能
    {
        cout << "请求的段表不存在!" << endl;
        cout << "请重新";
        Dispatch(); //重新调度
    }
    else if (Ts[n].flag == 1) //已经标记
        cout << "操作失败，该作业已经被调入到内存！" << endl;
    else if (Ts[n].total > mem - k) //存储不足
        cout << "内存空间不足，无法调度！" << endl;
    else
    {
        for (int j = 1; j <= Ts[n].num; j++)
        {
            Ts[n].s[j].rea = Ts[n].s[j].phy + k; //
        }
        k = k + Ts[n].total;
        Ts[n].flag = 1; //标记被访问
        cout << "调度后的结果是：" << endl;
        Show_Segm(n);
    }
}

//建议模块
void Suggest()
{
    printf(" 亲，请输入您宝贵的建议：");
    char s[10000];
    scanf("%s", s);
    printf(" *感谢您的宝贵建议，我们10分钟之内会受理您的建议* \n");
    printf(" *感谢您的本次使用，退出程序请输入【0】,返回主界面输入【1】: ");
    char m;
    cin >> m;
    do
        if (m - '0' == 0)
            exit(0);
        else if (m - '1' == 1)
            main_s();
        else
        {
            printf(" 对不起，输入有误，默认返回主界面呢\n\n");
            main_s();
        }
    while (m != 0);
}

//分页
void Pagi()
{
    memset(S, 0, sizeof(S)); //初始化A
    List L = NULL;
    int i = 0;
    do
    {
        printf("\t\t 欢迎使用基本分页存储管理系统 \n");
        printf("\t\t******************************\n");
        printf("\t\t* 1. 添加作业 *\n");
        printf("\t\t* 2. 回收作业 *\n");
        printf("\t\t* 3. 内存占用情况 *\n");
        printf("\t\t* 4. 查看作业 *\n");
        printf("\t\t* 5. 提出宝贵建议 *\n");
        printf("\t\t* 6. 返回主界面 *\n");
        printf("\t\t* 0. 退出程序 *\n");
        printf("\t\t******************************\n");
        printf(" 请输入您的选择 :");
        scanf("%d", &i);
        switch (i)
        {
        case 1:
            Create_Pagi(L);
            //Printf_Pagi(L);
            break;
        case 2:
            Revoke_Pagi(L);
            Printf_Pagi(L);
            break;
        case 3:
            Show_Pagi();
            break;
        case 4:
            Look_Pagi(L);
            break;
        case 5:
            Suggest();
            break;
        case 6:
            main_s();
            break;
        case 0:
            printf(" 感谢您的使用，祝您生活愉快！");
            exit(0);
        }
    } while (i != 0);
}

//分段
void Segme()
{
    int i;
    printf(" 请输入内存的大小：");
    int m;
    scanf("%d", &m);
    do
    {
        printf("\t\t 欢迎使用基本分段存储管理系统 \n");
        printf("\t\t******************************\n");
        printf("\t\t* 1. 创建作业 *\n");
        printf("\t\t* 2. 显示作业信息 *\n");
        printf("\t\t* 3. 调度作业   *\n");
        printf("\t\t* 4. 提出宝贵建议 *\n");
        printf("\t\t* 5. 返回主界面 *\n");
        printf("\t\t* 0. 退出程序 *\n");
        printf("\t\t******************************\n");
        printf(" 请输入您的选择 :");
        scanf("%d", &i);
        switch (i)
        {
        case 1:
            Create_Segm();
            break;
        case 2:
            for (int j = 1; j < Tnum + 1; j++)
                Show_Segm(j);
            break;
        case 3:
            if (i == 3) //如果输入是3则调度一个作业
                Dispatch();
            else
                cout << " 输入错误!请重新输入!" << endl;
            break;
        case 4:
            Suggest();
            break;
        case 5:
            main_s();
            break;
        case 0:
            printf(" 感谢您的使用，祝您生活愉快！");
            exit(0);
        }
    } while (i != 0);
}

//主界面
void main_s()
{
    printf("\t\t 欢迎来到内存管理系统 \n");
    printf("\t\t**********************\n");
    printf("\t\t* 1.进入分页管理系统 *\n");
    printf("\t\t* 2.进入分段管理系统 *\n");
    printf("\t\t* 3.我要提出宝贵建议 *\n");
    printf("\t\t* 0.退出程序  *\n");
    int m;
    printf(" 亲，请输入您的选择 :");
    scanf("%d", &m);
    do
        if (m >= 0 && m <= 3)
        {
            switch (m)
            {
            case 1:
                Pagi(); //分页
                break;
            case 2:
                Segme(); //分段
                break;
            case 3:
                Suggest();
                break;
            case 0:
                exit(0);
            }
        }
        else
        {
            printf(" 输入有误！请重新输入:");
            scanf("%d", &m);
        }
    while (m != 0);
}

int main()
{
    system("color 3f"); //颜色
    main_s();
    return 0;
}

四、实验结果

五、实验总结

此次试验，收获甚多，使用代码实现了基本分页存储管理。基本分页存储管理的思想是把进程分页，各个页面可离散地放到各个的内存块中。实验中涉及到了连续分配与非连续分配的概念，连续分配：为用户进程分配的必须是一个连续的内存空间；非连续分配：为用户进程分配的可以是一些分散的内存空间。

将内存空间分为一个个大小相等的分区，每个分区就是一个“页框”（页框=页帧=内存块=物理块=物理页面）。每个页框有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页号），页框号从0开始。将进程的逻辑地址空间也分为与页框大小相等的一个个部分， 每个部分称为一个“页”或“页面” 。每个页面也有一个编号， 即“页号”，页号也是从0开始。

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。进程的最后一个页面可能没有一个页框那么大。即，分页存储有可能产生内部碎片，因此页框不能太大，否则可能产生过大的内部碎片造成浪费。

实验中，还有很多不熟练的地方，课下我会好好努力，多加练习。

前言

此篇文章是我在B站学习时所做的笔记，大部分图片都是课件老师的PPT，方便复习用。此篇文章仅供学习参考。

提示：以下是本篇文章正文内容

思考：连续分配方式的缺点

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

1. 固定分区分配：缺乏灵活性，会产生大量的内部碎片，内存的利用率很低。
2. 动态分区分配：会产生很多外部碎片，虽然可以用“紧凑”技术来处理，但是“紧凑”的时间代价很高

造成连续分配方式的 缺点的本质原因 是连续分配方式要求进程占用的必须是一整段连续的内存区域。
解决方法：

基于这一思想，产生了“非连续分配方式”，或者称为“离散分配方式”。

知识总览

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

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

分页存储管理的基本概念

• 将内存空间分为一个个大小相等的分区（比如:每个分区4KB），每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块”。每个页框有一个编号，即“页框号”(或者“内存块号”、“页帧号”、“物理块号”)，页框号 从0开始 。

• 将用户进程的地址空间也分为 与页框大小相等 的一个个区域，称为“页”或“页面”。每个页面也有一个编号，即“页号”，页号也是 从0开始 。
  （注：进程的最后一个页面可能没有一个页框那么大。因此，页框不能太大，否则可能产生过大的内部碎片）
  

• 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。

• 各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。
  

思考：如何实现地址的转换

进程在内存中 连续存放 时，操作系统是如何实现逻辑地址到物理地址的转换的?

方法一

起始位置：100
偏移量：80

方法二

手动计算
如何计算：

• 页号=逻辑地址/页面长度（取除法的整数部分）
• 页内偏移量=逻辑地址%页面长度（取除法的余数部分)
• 页面在内存中的起始位置：操作系统需要用某种数据结构记录进程各个页面的起始位置。
• 页号=80/ 50= 1
• 页内偏移量=80 %50= 30
• 1号页在内存中存放的起始位置 450

为了方便计算页号、页内偏移量，页面大小一般设为2的整数幂

二进制方法

不同页面的区别在于前面20位的不同，如1号页是00000000000000000001，2号页对应的是00000000000000000010…,做题时可以由00000000000000000000判断它的页号是0号页，用逻辑地址（2）%页面长度（4096）得页内偏移量为2，而2这个数字刚好是二进制后面12位转换为十进制后的数

！！！结论：如果每个页面大小为2^kB，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号
因此，如果让每个页面的大小为2的整数幂，计算机就可以很方便地得出一个逻辑地址对应的页号和页内偏移量。

逻辑地址结构

• 地址结构包含两个部分：前一部分为页号，后一部分为页内偏移量W。在上图所示的例子中，地址长度为32位，其中0~11位为“页内偏移量”，或称“页内地址”；12~31位为“页号”。

重点！！！
如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是2K个内存单元
如果有M位表示“页号”，则说明在该系统中，一个进程最多允许有2M个页面

分页存储管理中，如何实现地址转换?

1. 要算出逻辑地址对应的页号
2. 要知道该页号对应页面在内存中的起始地址
3. 要算出逻辑地址在页面内的“偏移量”
4. 物理地址=页面始址＋页内偏移量

注：如果题目中是用十进制数表示逻辑地址，则
页号=逻辑地址/页面长度(取除法的整数部分)
页内偏移量=逻辑地址%页面长度（取除法的余数部分)

页表

• 为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。
• 假设此时我们要访问某个逻辑地址，可以用逻辑地址算出它应该属于哪一页，之后根据页面对应的页号查询页表，就可以知道这个内存内存应该存在哪个页框当中，只要用内存块的块号*每个内存块的大小就可以得到每个内存卡的起始地址
• 知道起始地址，再用逻辑地址的偏移量就可以由物理地址=起始地址+偏移量算出物理地址
  

重要考点例题

知识回顾与重要考点