首页 / 更多教程 / 25 实战页式内存管理 中
25 实战页式内存管理 中
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了25 实战页式内存管理 中，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含13003字，纯文字阅读大概需要19分钟。
内容图文
参考
https://blog.51cto.com/13475106/category6.html及狄泰软件相关课程
实战页式内存管理中
课程设计目标
1.处理运行结束的任务
2.实现FIFO页面交换的算法
3.实现LRU页面交换算法
目标一
1.将任务结构从任务表中移除
2.回收任务所使用的页框
3.释放任务结构所占的内存
目标二-实现FIFO页交换算法
原理:利用队列(Qt)记录页框使用的时间，页框是在队列中排序的，在交换时将最先进入队列的页框移除
过程:申请队列，页请求时请求成功，将对应的页框号加入到队列尾部，在进行页请求时，没有空余的页框，需要进行页交换，将头部的队列页框移出队列
代码实现
#include <QtCore/QCoreApplication>
#include <QList>
#include <QQueue>
#include <iostream>
#include <ctime>
using namespace std;
#define PAGE_NUM (0xFF + 1)
#define FRAME_NUM (0x04)
#define FP_NONE (-1)
struct FrameItem
{
int pid; // the task which use the frame
int pnum; // the page which the frame hold
int ticks; // the ticks to mark the usage frequency
FrameItem()
{
pid = FP_NONE;
pnum = FP_NONE;
ticks = 0xFF;
}
};
class PageTable
{
int m_pt[PAGE_NUM];
public:
PageTable()
{
for(int i=0; i<PAGE_NUM; i++)
{
m_pt[i] = FP_NONE;
}
}
int& operator[] (int i)
{
if( (0 <= i) && (i < length()) )
{
return m_pt[i];
}
else
{
QCoreApplication::exit(-1);
return m_pt[0]; // for avoid warning
}
}
int length()
{
return PAGE_NUM;
}
};
class PCB
{
int m_pid; // task id
PageTable m_pageTable; // page table for the task
int* m_pageSerial; // simulate the page serial access
int m_pageSerialCount; // page access count
int m_next; // the next page index to access
public:
PCB(int pid)
{
m_pid = pid;
m_pageSerialCount = qrand() % 5 + 5;
m_pageSerial = new int[m_pageSerialCount];
for(int i=0; i<m_pageSerialCount; i++)
{
m_pageSerial[i] = qrand() % 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()
{
QString s = "";
for(int i=0; i<m_pageSerialCount; i++)
{
s += QString::number(m_pageSerial[i]) + " ";
}
cout << ("Task" + QString::number(m_pid) + " : " + s).toStdString() << endl;
}
~PCB()
{
delete[] m_pageSerial;
}
};
FrameItem FrameTable[FRAME_NUM];
QList<PCB*> TaskTable;
QQueue<int> MoveOut;
int GetFrameItem();
void AccessPage(PCB& pcb);
int RequestPage(int pid, int page);
int SwapPage();
void ClearFrameItem(PCB& pcb);
void ClearFrameItem(int frame);
int Random();
int FIFO();
int LRU();
void PrintLog(QString log);
void PrintPageMap(int pid, int page, int frame);
void PrintFatalError(QString s, int pid, int page);
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" + QString::number(pid) + " for Page" + QString::number(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" + QString::number(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" + QString::number(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" + QString::number(frame));
FrameTable[frame].pid = pid;
FrameTable[frame].pnum = page;
FrameTable[frame].ticks = 0xFF;
MoveOut.enqueue(frame);//将页框号进行插入
return frame;
}
void ClearFrameItem(int frame)
{
FrameTable[frame].pid = FP_NONE;
FrameTable[frame].pnum = FP_NONE;
for(int i=0, f=0; (i<TaskTable.count()) && !f; i++)
{
PageTable& pt = TaskTable[i]->getPageTable();
for(int j=0; j<pt.length(); j++)
{
if( pt[j] == frame )
{
pt[j] = FP_NONE;
f = 1;
break;
}
}
}
}
int Random()
{
// just random select
int obj = qrand() % FRAME_NUM;
PrintLog("Random select a frame to swap page content out: Frame" + QString::number(obj));
PrintLog("Write the selected page content back to disk.");
ClearFrameItem(obj);
return obj;
}
int FIFO()//FIFO的实现
{
// select the first page in memory to move out
int obj = MoveOut.dequeue();//出队列的操作
PrintLog("Select a frame to swap page content out: Frame" + QString::number(obj));
PrintLog("Write the selected page content back to disk.");
ClearFrameItem(obj);
return obj;
}
int LRU()
{
int obj = 0;
int ticks = FrameTable[obj].ticks;
QString s = "";
for(int i=0; i<FRAME_NUM; i++)
{
s += "Frame" + QString::number(i) + " : " + QString::number(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" + QString::number(obj));
PrintLog("Write the selected page content back to disk.");
return obj;
}
int SwapPage()
{
return FIFO();
}
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(QString log)
{
cout << log.toStdString() << endl;
}
void PrintPageMap(int pid, int page, int frame)
{
QString s = "Task" + QString::number(pid) + " : ";
s += "Page" + QString::number(page) + " ==> Frame" + QString::number(frame);
cout << s.toStdString() << endl;
}
void PrintFatalError(QString s, int pid, int page)
{
s += " Task" + QString::number(pid) + ": Page" + QString::number(page);
cout << s.toStdString() << endl;
QCoreApplication::exit(-2);
}
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
int index = 0;
qsrand(time(NULL));
TaskTable.append(new PCB(1));
PrintLog("Task Page Serial:");
for(int i=0; i<TaskTable.count(); i++)
{
TaskTable[i]->printPageSerial();
}
PrintLog("==== Running ====");
while( true )
{
if( TaskTable[index]->running() )
{
AccessPage(*TaskTable[index]);
}
index = (index + 1) % TaskTable.count();
cin.get();
}
return a.exec();
}
实现结果
从实验结果可以看到，随机生成了页面，在进行页请求交换是，是按照队列将队列头部进行移出的
目标三-实现LRU页交换算法
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
代码实现
#include <QtCore/QCoreApplication>
#include <QList>
#include <QQueue>
#include <iostream>
#include <ctime>
using namespace std;
#define PAGE_NUM (0xFF + 1)
#define FRAME_NUM (0x04)
#define FP_NONE (-1)
struct FrameItem
{
int pid; // the task which use the frame
int pnum; // the page which the frame hold
int ticks; // the ticks to mark the usage frequency
FrameItem()
{
pid = FP_NONE;
pnum = FP_NONE;
ticks = 0xFF;
}
};
class PageTable
{
int m_pt[PAGE_NUM];
public:
PageTable()
{
for(int i=0; i<PAGE_NUM; i++)
{
m_pt[i] = FP_NONE;
}
}
int& operator[] (int i)
{
if( (0 <= i) && (i < length()) )
{
return m_pt[i];
}
else
{
QCoreApplication::exit(-1);
return m_pt[0]; // for avoid warning
}
}
int length()
{
return PAGE_NUM;
}
};
class PCB
{
int m_pid; // task id
PageTable m_pageTable; // page table for the task
int* m_pageSerial; // simulate the page serial access
int m_pageSerialCount; // page access count
int m_next; // the next page index to access
public:
PCB(int pid)
{
m_pid = pid;
m_pageSerialCount = qrand() % 5 + 5;
m_pageSerial = new int[m_pageSerialCount];
for(int i=0; i<m_pageSerialCount; i++)
{
m_pageSerial[i] = qrand() % 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()
{
QString s = "";
for(int i=0; i<m_pageSerialCount; i++)
{
s += QString::number(m_pageSerial[i]) + " ";
}
cout << ("Task" + QString::number(m_pid) + " : " + s).toStdString() << endl;
}
~PCB()
{
delete[] m_pageSerial;
}
};
FrameItem FrameTable[FRAME_NUM];
QList<PCB*> TaskTable;
QQueue<int> MoveOut;
int GetFrameItem();
void AccessPage(PCB& pcb);
int RequestPage(int pid, int page);
int SwapPage();
void ClearFrameItem(PCB& pcb);
void ClearFrameItem(int frame);
int Random();
int FIFO();
int LRU();
void PrintLog(QString log);
void PrintPageMap(int pid, int page, int frame);
void PrintFatalError(QString s, int pid, int page);
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" + QString::number(pid) + " for Page" + QString::number(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" + QString::number(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" + QString::number(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" + QString::number(frame));
FrameTable[frame].pid = pid;
FrameTable[frame].pnum = page;
FrameTable[frame].ticks = 0xFF;
MoveOut.enqueue(frame);
return frame;
}
void ClearFrameItem(int frame)
{
FrameTable[frame].pid = FP_NONE;
FrameTable[frame].pnum = FP_NONE;
for(int i=0, f=0; (i<TaskTable.count()) && !f; i++)
{
PageTable& pt = TaskTable[i]->getPageTable();
for(int j=0; j<pt.length(); j++)
{
if( pt[j] == frame )
{
pt[j] = FP_NONE;
f = 1;
break;
}
}
}
}
int Random()
{
// just random select
int obj = qrand() % FRAME_NUM;
PrintLog("Random select a frame to swap page content out: Frame" + QString::number(obj));
PrintLog("Write the selected page content back to disk.");
ClearFrameItem(obj);
return obj;
}
int FIFO()
{
// select the first page in memory to move out
int obj = MoveOut.dequeue();
PrintLog("Select a frame to swap page content out: Frame" + QString::number(obj));
PrintLog("Write the selected page content back to disk.");
ClearFrameItem(obj);
return obj;
}
int LRU()
{
int obj = 0;
int ticks = FrameTable[obj].ticks;
QString s = "";
for(int i=0; i<FRAME_NUM; i++)
{
s += "Frame" + QString::number(i) + " : " + QString::number(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" + QString::number(obj));
PrintLog("Write the selected page content back to disk.");
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(QString log)
{
cout << log.toStdString() << endl;
}
void PrintPageMap(int pid, int page, int frame)
{
QString s = "Task" + QString::number(pid) + " : ";
s += "Page" + QString::number(page) + " ==> Frame" + QString::number(frame);
cout << s.toStdString() << endl;
}
void PrintFatalError(QString s, int pid, int page)
{
s += " Task" + QString::number(pid) + ": Page" + QString::number(page);
cout << s.toStdString() << endl;
QCoreApplication::exit(-2);
}
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
int index = 0;
qsrand(time(NULL));
TaskTable.append(new PCB(1));
TaskTable.append(new PCB(2));
PrintLog("Task Page Serial:");
for(int i=0; i<TaskTable.count(); i++)
{
TaskTable[i]->printPageSerial();
}
PrintLog("==== Running ====");
while( true )
{
for(int i=0; i<FRAME_NUM; i++)
{
FrameTable[i].ticks--;
}
if( TaskTable.count() > 0 )
{
if( TaskTable[index]->running() )
{
AccessPage(*TaskTable[index]);
}
else
{
PrintLog("Task" + QString::number(TaskTable[index]->getPID()) + " is finished!");
PCB* pcb = TaskTable[index];
TaskTable.removeAt(index);
ClearFrameItem(*pcb);
delete pcb;
}
}
if( TaskTable.count() > 0 )
{
index = (index + 1) % TaskTable.count();
}
cin.get();
}
return a.exec();
}
运行结果
由实验结果可以得知，在进行页交换时，将页框访问次数最少的页框进行了移除
小结
1.在实验上，页框表，页表和任务结构是相互关联的关系
2.页框分配和页框回收时需要斩断页框表和页表的双向关联
3.任务结构是任务的内在表示，包含了私有的页表
4.FIFO和LRU页交换算法都是从概率的角度选择页面移除
内容总结
以上是互联网集市为您收集整理的25 实战页式内存管理 中全部内容，希望文章能够帮你解决25 实战页式内存管理 中所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】