页式存储管理

页式存储管理

段式内存管理

这里的 ，段， 具体指什么？
一段连续的内存空间

为什么会有段式内存管理?

• 程序的各个部分相对独立 （如： 数据段， 代码段)
• 早期 x86 处理器无法通过一个寄存器访问所有内存单元
• 解决早期程序运行时的重定位问题

段式内存管理的应用

• 在 x86 系列的处理器中， 硬件对段式内存管理进行了直接支持
• 另外， 段式内存管理也可使用纯软件实现
• 核心： 段首地址 + 段内偏移地址 = 内存单元地址

段式内存管理在 C 语言中的体现（纯软件实现）

• 数组的本质： 一片连续的内存 （段)
• 数组名 (array) : 数组的起始内存地址 （段地址)
• 数组元素的访问： array[i] 等价于*(array + i)
• 第 i 个元素的地址: array(段地址) + i(偏移地址)

问 题
应用程序规模越来越大， 导致多数时候无法全部加载进入内存， 如何解决？

可行的解决方案 ： 按段加载 （ 局部性原理)

• 只将当前程序运行需要的段加载进内存
• 当某个段不再需要使用， 立即从内存中移除

按段加载可能带来的问题

• 段的大小不确定， 可能大于实际的物理内存
• 段加载时需要具体的长度信息， 导致效率不高

页式管理

更进一步的解决方案： 内存分页

• 页指的是固定大小的内存片 (4KB )
• 每一个内存段由多个页组成
• 页是进行内存管理的基本单位（加载页， 换出页)

虚拟内存空间（逻辑地址）：程序执行时内部所使用的内存空间（独立于其它程序)

物理内存空间（物理地址）：物理机器所配置的实际内存空间（所有程序共享)

逻辑地址需要进行转换才能得到对应的物理地址

页式内存管理中的地址
地址 = 页号 + 页内偏移

• 逻辑地址 = 逻辑页号 + 页内偏移
• 物理地址 = 物理页号 + 页内偏移
• 地址转换时仅变更页号即可， 页内偏移不变

页请求
访问一个逻辑地址时， 对应的页不在内存中
从外存中将目标页加到内存中
之后更新页表

页交换
页请求时发现物理内存不足， 需要将暂时不用的页移除
首先， 决定并选择需要移除的页
将选中页中的所有数据写入外存
更新页表， 重纖行页请求

操作系统如何管理实际物理内存

页框与页面 (Frame and Page)

• 页框 (Frame) : 物理内存空间中的页（物理页)
• 页面 (Page) : 逻辑内存空间中的页（逻辑页)

页框用于存储页面内容， 而页面内容来源于逻辑内存空间。

操作系统必须知道物理内存的使用情况

• 建立结构对物理内存进行管理 (FrameTable)
• 结构记录包括： 页框是否可用， 被谁使用， 等
• 为具体的应用程序分配页表

任务表：操作系统实现多任务（App) 的关键数据结构，用于记录各个任务的上下文信息。

页表与不同任务 (App) 有怎样的关系？

• 每个任务都有专属的页表
• 页表是任务上下文的一部分

页表对于任务 (App) 的意义是什么?

• 页表机制能够保证任务无法意外的访问或破坏其它任务的内存
• 页表是虚拟内存空间与物理内存空间的“分界线”
• 因为页表的存在， 各个任务才具备相同且独立的内存空间
• 页表是虚拟内存通往物理内存的”唯一通道“

任务只能在页表机制下间接访问分配的物理内存， 因此无法对其它内存进行访问,

页交换替换算法

FIFO页交换算法：将最先进入内存的页移出

LRU页交换算法：将当前使用最少的页从内存中移出

访问计数的更新方式

• 每个时间周期 (Interval) 将所有页框的访问计数减1
• 当某个页面被访问时（RW) 将访问计数加 1
• 访问计数最小的页面是最近未被使用的页

页表具体是如何构成的？

• 页表的本质是一个映射表
• 虚拟内存空间中的每一页映射到一个页框
• 页表可以看作做一维整型数组（单级页表)

单级页表和二级页表

• 每个任务 (App) 都有页表
• 单级页表大小固定 （占用固定内存)
• 根据程序运行的局部性原理: NULL
  多数情况下， 页表为稀疏状态
  单级页表会浪费大量内存资源

二级页表

• 把页号分为两段： 页目录 + 二级页号
• 如果下级页表的所有表项为空， 那么页目录为空

假设当前需要访问虚拟页为 0x52，则: 页目录为 0x5,
二级页号为 0x2。 所以： 对应的页框号为 0x31。

页式内存管理C++实现

结构

• 页框表是全局唯一的，用于记录内存页的使用情况
• 页表是任务私有的，用于记录虚拟页到内存页的映射关系
• 每一个任务需要一个结构体进行表示

函数操作

• 页框分配操作：int GetFrameItem();
• 页请求操作：int RequestPage(int pid, int page);
• 页交换操作：int SwapPage();

如何模拟不同任务

• 不同任务的虚拟页访问顺序不同
• 因此，可以随机产生页面访问序列

#include <iostream>
#include <string>
#include <exception>
#include <vector>
#include <queue>
#include <ctime>

using namespace std;

#define PAGE_NUM		(0xFF + 1)		//虚拟内存0~255
#define PAGE_DIR_NUM	(0xF+1)			//二级页表页目录
#define PAGE_SUB_NUM	(0xF+1)			/
#define FRAME_NUM		(0x04)			//物理内存0~4
#define FP_NONE			(-1)			//空页值记为-1

//页框表是全局唯一的,用于记录内存页的使用情况
struct FrameItem
{
    int pid;						//哪一个任务使用了当前页框
    int pnum;						//当前页框所保存哪一页的内容
    int ticks;						//LRU所需的页框使用频率度量

    FrameItem()
    {
        pid = FP_NONE;
        pnum = FP_NONE;
        ticks = 0xFF;
    }

};
FrameItem FrameTable[FRAME_NUM];


//页表是任务私有的,用于记录虚拟页到内存页的映射关系
class PageTable
{
    int* m_pt[PAGE_DIR_NUM];
public:
    PageTable()
    {
        for (int i = 0; i < PAGE_DIR_NUM; i++) {
            m_pt[i] = NULL;
        }
    }

    int& operator[] (int i) 
    {
        if ((0 <= i) && (i < length()))
        {
            int dir = ((i & 0xF0) >> 4);
            int spn = (i & 0x0F);

            if (m_pt[dir] == NULL)
            {
                m_pt[dir] = new int[PAGE_SUB_NUM];

                for (int k = 0; k < PAGE_SUB_NUM; k++) {
                    m_pt[dir][k] = FP_NONE;
                }
            }

            return m_pt[dir][spn];

        }
        else exit(-1);
    }

    int length()
	{
        return PAGE_NUM;
    }

    ~PageTable()
    {
        for (int i = 0; i < PAGE_DIR_NUM; i++)
            delete[] m_pt[i];
    }

};

class PCB
{
    int m_pid;						//任务id
    PageTable m_pageTable;			//此任务的页表

    //任务执行本质就是对不同虚拟页访问
    int* m_pageSerial;				//随机数组模拟随机访问的页面
    int m_pageSerialCount;			//当前任务从执行到结束需要访问多少页
    int m_next;						//下一次要访问的页面的页号
public:
    PCB(int pid)
    {
        m_pid = pid;
        m_pageSerialCount = rand() % 20 + 5;
        m_pageSerial = new int[m_pageSerialCount];

        for (int i = 0; i < m_pageSerialCount; i++) {
            m_pageSerial[i] = rand() % 8;
        }
        m_next = 0;
    }

    int getPID()
	{
        return m_pid;
    }

    PageTable& getPageTable()
	{
        return m_pageTable;
    }

    int getNextPage()
	{
        int ret = m_next++;
        if (ret < m_pageSerialCount)
        {
            ret = m_pageSerial[ret];
        }
        else
        {
            ret = FP_NONE;
        }
        return ret;
    }

    bool running()
	{
        return (m_next < m_pageSerialCount);
    }

    //打印任务的所有访问页面号
    void printPageSerial()
	{
        string s = "";
        for (int i = 0; i < m_pageSerialCount; i++)
        {
            s += to_string(m_pageSerial[i]) + " ";
        }
        cout << "Task" + to_string(m_pid) + " : " + s << endl;
    }

    ~PCB()
    {
        delete[] m_pageSerial;
    }

};
//任务表
vector<PCB*> TaskTable;
queue<int>moveOut;

int GetFrameItem();
void AccessPage(PCB& pcb);
int RequestPage(int pid, int page);
int SwapPage();
void PrintLog(string log);
void PrintPageMap(int pid, int page, int frame);
void PrintFatalError(string s, int pid, int page);
void ClearFrameItem(PCB& pcb);
void ClearFrameItem(int frame);
int GetFrameItem()
{
    int ret = FP_NONE;

    for (int i = 0; i < FRAME_NUM; i++)
    {
        if (FrameTable[i].pid == FP_NONE)
        {
            ret = i;
            break;
        }
    }
    
    return ret;
}

//页访问
void AccessPage(PCB& pcb)
{
    int pid = pcb.getPID();
    PageTable& pageTable = pcb.getPageTable();
    int page = pcb.getNextPage();

    if (page != FP_NONE)								//要访问下一页号不是空,说明任务尚未结束
    {
        PrintLog("Access Task" + to_string(pid) + "for Page" + to_string(page));
        if (pageTable[page] != FP_NONE)					//映射存在,虚拟页的内存存在于物理内存
        {
            PrintLog("Find target page in page table.");
            PrintPageMap(pid, page, pageTable[page]);
        }
        else                                            //映射不存在,虚拟页在物理内存尚未导入 
        {
            PrintLog("Target page is NOT found, need to request page...");
            pageTable[page] = RequestPage(pid, page);

            if (pageTable[page] != FP_NONE)				//成功请求到页	
            {
                PrintPageMap(pid, page, pageTable[page]);
            }
            else                                        //映射失败
            {
                PrintFatalError("Can NOT request page from disk",pid,page);
            }
        }

        FrameTable[pageTable[page]].ticks++;

    }
    else
    {
        PrintLog("Task" + to_string(pid) + " is finished!");
    }


}

int RequestPage(int pid, int page)
{
    int frame = GetFrameItem();
    if (frame != FP_NONE)
    {
        PrintLog("Get a frame to hold page content: Frame" + to_string(frame));
    }
    else
    {
        PrintLog("No free frame to allocate, need to swap page out.");

        frame = SwapPage();

        if (frame != FP_NONE)					//页交换成功
        {
            PrintLog("Succeed to swap lazy page out.");
        }
        else
        {
            PrintFatalError("Failed to swap page out.", pid, FP_NONE);
        }
    }

    PrintLog("Load content from disk to frame" + to_string(frame));

    FrameTable[frame].pid = pid;
    FrameTable[frame].pnum = page;
    FrameTable[frame].ticks = 0xFF;

    moveOut.push(frame);

    return frame;
}

void ClearFrameItem(int frame)
{
    FrameTable[frame].pid = FP_NONE;
    FrameTable[frame].pnum = FP_NONE;

    for (int i = 0, flag = 0; i < (int)TaskTable.size() && !flag; i++) {
        PageTable& pt = TaskTable[i]->getPageTable();

        for (int j = 0; j < pt.length(); j++) {
            if (pt[j] == frame) {
                pt[j] = FP_NONE;
                flag = 1;
                break;
            }
        }
    }
    return ;
}

int Random()
{
    int obj = rand() % FRAME_NUM;

    PrintLog("Ramdom to swap page content out: Frame" + to_string(obj));
    PrintLog("Write the selected page content back to disk.");

    ClearFrameItem(obj);

    return obj;
}

int FIFO()
{
    int obj = moveOut.front();
    moveOut.pop();

    PrintLog("FIFO: Select a frame to swap page content out: Frame" + to_string(obj));
    PrintLog("Write the selected page content back to disk.");

    ClearFrameItem(obj);

    return obj;
}

int LRU()
{
    int obj = 0;
    int ticks = FrameTable[obj].ticks;
    string s = "";

    for (int i = 0; i < FRAME_NUM; i++)
    {
        s += "Frame" + to_string(i) + " : " + to_string(FrameTable[i].ticks) + "    ";

        if (ticks > FrameTable[i].ticks)
        {
            ticks = FrameTable[i].ticks;
            obj = i;
        }
    }

    PrintLog(s);
    PrintLog("Select the LRU frame page to swap content out: Frame" + to_string(obj));
    PrintLog("Write the selected page content back to disk.");

    ClearFrameItem(obj);

    return obj;	
}

int SwapPage()
{
    return LRU();
}

//任务结束应要清除相应的页框
void ClearFrameItem(PCB& pcb)
{
    for (int i = 0; i < FRAME_NUM; i++)
    {
        if (FrameTable[i].pid == pcb.getPID())
        {
            FrameTable[i].pid = FP_NONE;
            FrameTable[i].pnum = FP_NONE;
        }
    }
}

void PrintLog(string log)
{
    cout << log << endl;
}

//虚拟内存页映射到物理内存页框
void PrintPageMap(int pid, int page, int frame)
{
    string s = "Task" + to_string(pid) + " : ";

    s += "Page" + to_string(page) + " ===> Frame" + to_string(frame);

    cout << s << endl;
}

//任务某一虚拟页发生严重错误
void PrintFatalError(string s, int pid, int page)
{
    s += "Task" + to_string(pid) + " : Page" + to_string(page);

    cout << s << endl;

    exit(-2);
}

int main() {
    int index = 0;

    srand(time(NULL));

    TaskTable.push_back(new PCB(1));
    TaskTable.push_back(new PCB(2));

    for (int i = 0; i < (int)TaskTable.size(); i++)
    {
        TaskTable[i]->printPageSerial();
    }

    PCB p(3);
    PageTable& pt = p.getPageTable();
    

    PrintLog("========Running=========");

    while (true)
    {
        for (int i = 0; i < FRAME_NUM; i++)
        {
            FrameTable[i].ticks--;
        }

        if (TaskTable.size() > 0)
        {
            if (TaskTable[index]->running())
            {
                AccessPage(*TaskTable[index]);
            }
            else
            {
                PrintLog("Task" + to_string(TaskTable[index]->getPID()) + "is finished!");

                PCB * pcb = TaskTable[index];

                TaskTable.erase(TaskTable.begin() + index);

                ClearFrameItem(*pcb);

                delete pcb;
            }
        }

        if (TaskTable.size() > 0)
        {
            index = (index + 1) % TaskTable.size();
        }		

        cin.get();
    }

    return 0;
}