精华内容
下载资源
问答
  • C语言 操作系统 请求分页 OPT FIFO LRU算法
  • FIFO 请求分页式存储管理 henbucuode daima
  • 操作系统实现请求分页存储管理页面Optimal、FIFO、LRU调度算法论文
  • FIFO先进先出页面置换实现请求分页

    千次阅读 2016-11-26 11:48:35
    FIFO页面淘汰算法,实现请求分页。基本分页是实存管理方式,请求分页是虚存管理方式。虚存是是指具有请求调入功能和置换功能, 能从逻辑上对内存容量加以扩充的一种存储器系统。它避免了一次性将程序全部调入内存,...

    如我在上一篇博文动态分区算法实现中讲到的,這次实现的是离散分配方式里的请求分页算法,涉及到虚拟存储。

    我一开始在做這个实验的时候有点无从下手,动态分区好理解吧,你需要多少地,我就给你划分多少地,地不要了,我就回收。但这个请求分页,是个什么鬼?分页就分页吧,把实存平均分,把辅存平均分,每个进程配一个页表,记录一个用到哪一个页对应哪一个块,对应什么就分什么呗,這个页面置换是干什么用的?被困于动态分区的简单思维里,我陷入迷茫之中,眼神中略带倦意。于是,我好好地了解了一下请求分页的原理。

    我之前的理解,实际上是基本分页方式,是要将程序全部装入内存中。程序不必连续存放。

    一个逻辑地址的组成是页号和页内地址,页号为逻辑地址除页面大小后取整,页内地址为逻辑地址mod页面大小后的值。逻辑地址转换为物理地址的过程就是,将进程中的页号取出,在页表中查询到页号对应的物理块号,用物理块号替代原先的也号,页内地址原位copy。

    基本分页的流程就清楚了,进程的页表中记录着所有的页号,对应的块号也一查就出来了,实现so easy。

    于是问题来着,基本分页与请求分页的区别呢?


    基本分页是实存管理方式,请求分页是虚存管理方式。虚存是是指具有请求调入功能和置换功能, 能从逻辑上对内存容量加以扩充的一种存储器系统。它避免了一次性将程序全部调入内存,并且一直滞留在内存。比如说,在看高清电影的时候,电脑内存大小实际上是小于电影大小的,如果没有虚存,电影会看不了,有了虚存,电影即将播放与正在播放的部分会调入内存,而剩余部分存在辅存,电影這时候就可以正常播放。


    涉及到了虚存,就涉及到了程序部分存入内存,就涉及到了如果一个需要访问的一个页面如果恰好不在内存装入的那部分,怎么办?页表中查询不到该页号对应的物理块号,也就无法访问到相应的内容。這时候,就产生了缺页中断,调用页面置换,将需要访问的页面调入内存,页表记录下该页表信息,再进行物理地址的访问。


    所以,虚拟存储的方式导致了基本分页与请求分页的不同,部分装入会产生缺页,由此衍生页面置换算法等等。

     


    页面置换算法包括:最佳置换算法,FIFO先进先出算法,LRU最近最久未使用置换算法,clock置换算法(最近未使用算法),改进型clock算法,LFU最少使用置换算法,页面缓冲算法。


    此次实验实现的是FIFO先进先出算法。

    首先,设置数据结构,设置两种结点,一个结点记录页面所有信息,一个只记录页面id号。设置数组page,记录所有页面id,存在于辅存中的块号,是否调入内存中,对应的内存的物理块号(如果不在内存中,则此项为0)。设置链表,采用队列方式,记录内存中的页号,方便实现先进先出,移动结点。

    输入一个进程的所有页面信息,储存在数组中后,根据其中是否调入内存的标志,创建初始队列,先后顺序记录下这些页面号。对于每一个逻辑地址,首先判断是否超出页面逻辑地址上限。将其对应的页号查询page,若不在内存,缺页中断,调用FIFO算法,替代链表中第一位的页面,并插入到队尾,将page数组中相应数据改变,最后计算物理地址。


    代码如下:

    
    
    #include
        
         
    #include
         
          
    
    #define N 64
    struct
    {
    	int lNumber; //页号 
    	int pNumber; //物理块号 
    	int dNumber; //在磁盘上的位置 
    	int write; //修改标志 
    	int flag; //存在标志 
    }page[N];
    
    struct node {
    	int id;
    	struct node * link;
    	node(void) {};
    	node(int a) { id = a; };
    }*start,*first=NULL;
    int PageNumber;
    int BlockNumer;
    
    void init()
    {
    	printf("输入页表信息,创建页表(若输入为-1,则结束输入):\n");
    	int n,i=0;
    	printf("输入第0页的辅存地址:");
    	scanf("%d", &n);
    	while (n != -1)
    	{
    		page[i].lNumber = i;
    		page[i].dNumber = n;
    		page[i].flag = 0;
    		i++;
    		printf("\n输入第%d页的辅存地址:",i);
    		scanf("%d", &n);	
    	}
    	PageNumber = i;
    	printf("输入主存块号,块号要小于%d:", PageNumber);
    	scanf("%d", &n);
    	i = 0;
    	while (n != -1)
    	{
    		if (i < 4)
    		{
    			page[i].pNumber = n;
    			page[i].flag = 1;
    		}
    		scanf("%d", &n);
    		i++;
    	}
    	if (i < 4)
    		BlockNumer = i;
    	else
    		BlockNumer = 4;
    	for (i = 0; i < PageNumber; i++)
    	{
    		printf("\n当前表的内容为:\n");
    		printf("page[%d].lNumber=%d\t\tpage[%d].pNumber=%d\t\tpage[%d].flag=%d\n", i, page[i].lNumber, i, page[i].pNumber, i, page[i].flag);
    	}
    
    	for (i = 0; i < BlockNumer; i++)
    	{
    		if (start == NULL)
    			first=start = new node(i);
    		else {
    			first->link = new node(i);
    			first = first->link;
    		}
    		first->link = NULL;
    	}
    }
    
    int found(int P)
    {
    	int a=0;
    	node * part;
    	part = start;
    	while (part != NULL)
    	{
    		if (part->id == P)
    			a = 1;
    	    part = part->link;
    	}
    	return a;
    }
    
    void FIFO(int P)
    {
    	printf("访问的%d页不存在,发生缺页中断\n",P);
    	int before;
    	node *end = first = start;
    	while (end->link != NULL)
    		end = end->link;
    	start = start->link;
    	before = first->id;
    	first->id = P;
    	first->link = NULL;
    	end->link = first;
    	page[P].pNumber = page[before].pNumber;
    	page[P].flag = 1;
    	page[before].flag = 0;
    	page[before].pNumber = 0;
    	printf("淘汰主存块%d中的页%d,从磁盘第%d块中调入页%d\n", page[P].pNumber, before, page[P].dNumber, P);
    }
    
    
    
    int main()
    {
    	init();
    	int swrite, address,is_found;
    	int P;
    	int Ad;
    	int judge = 1;
    	while (judge == 1)
    	{
    		printf("输入指令性质(1-修改,0-不修改)和逻辑地址:");
    		scanf("%d", &swrite);
    		scanf("%d", &address);
    		if (address >= PageNumber * 1024)
    			printf("地址超出范围\n");
    		else
    		{
    			P = address / 1024;
    			Ad = address - P * 1024;
    			is_found = found(P);
    			while (is_found == 0)
    			{
    				FIFO(P);
    				is_found = found(P);
    			}
    			page[P].write = swrite;
    			printf("逻辑地址:%d  对应的物理地址为:%d \n", address, 1024 * page[P].pNumber + Ad);
    		}
    		printf("是否继续(继续1,否0):");
    		scanf("%d", &judge);
    	}
        return 0;
    }
    
    
         
        
    实验结果为:

    展开全文
  • 目的:(1)通过编写程序实现请求分页存储管理页面Optimal、FIFO、LRU调度算法,使学生掌握虚拟存储管理中有关缺页处理方法等内容,巩固有关虚拟存储管理的教学内容。 (2)了解Windows2000/XP中内存管理机制,掌握...
  • 操作系统 请求分页式存储管理 实验要求 通过编写分页式存储管理的模拟程序,加深对页式存储管理方式的理解,熟悉逻辑地址到物理地址的转换过程,掌握虚拟存储管理中的页面调度算法,认识分页式虚拟存储系统中缺页...

    操作系统 请求分页式存储管理

    实验要求
    通过编写分页式存储管理的模拟程序,加深对页式存储管理方式的理解,熟悉逻辑地址到物理地址的转换过程,掌握虚拟存储管理中的页面调度算法,认识分页式虚拟存储系统中缺页中断的处理过程。

    实验内容

    1. 设计一个分页式虚拟存储系统,用程序模拟实现,假设页面大小为1K,每个进程分配三个块。
    2. 页面调度分别采用FIFO调度算法和LRU算法(堆栈法)。(选中页面直接交换。)
    3. 假设当前作业的页表如下:
      在这里插入图片描述
    4. 假设逻辑指令格式为:
      操作符 页号1 页内地址1 页号2 页内地址2
      例如: 表示将页面1内地址为011单元的内容和页面2中地址为051的单元的内容相加,
      如:(1011H)+(1200H)。
      现有指令序列如下:
      在这里插入图片描述
    5. 编写模拟程序,执行上述指令,若当前页面不在内存,则使用页面调度算法,交换相应页。
    6. 要求每执行上述指令流中的一条逻辑指令,输出相应的物理指令,若页表有修改,则显示修改后的页表。

    FIFO
    内存块按照分配顺序依次放入队列中,每次需要置换时,都将队列第一个内存块取出,分配给一个页表项,原本的数据写入磁盘,然后将该内存块放回队列末尾。

    LRU
    为每个内存块设置一个上次使用时间,初始为1,每次访问一个内存块时,被访问的内存块的上次使用时间重置为1,其他内存块加1,当需要置换时,选择上次使用时间最大的内存块分配给新的数据,原来的数据写入磁盘,然后该内存块的上次使用时间重置,其他内存块的上次使用时间加1。

    //LogicInstruction.h
    #pragma once
    #include <iostream>
    
    using namespace std;
    
    class LogicInstruction
    {
    	char op;//运算符
    	int pageNo1;//左操作数页号
    	string addr1;//左操作数逻辑地址
    	int pageNo2;//右操作数页号
    	string addr2;//右操作数逻辑地址
    public:
    	LogicInstruction(char op, int pageNo1, string addr1, int pageNo2, string addr2);
    	char getOp()const;
    	int getPageNo1()const;
    	string getAddr1()const;
    	int getPageNo2()const;
    	string getAddr2()const;
    };
    
    //LogicInstruction.cpp
    #include "LogicInstruction.h"
    
    LogicInstruction::LogicInstruction(char op, int pageNo1, string addr1, int pageNo2, string addr2)
    {
    	this->op = op;
    	this->pageNo1 = pageNo1;
    	this->addr1 = addr1;
    	this->pageNo2 = pageNo2;
    	this->addr2 = addr2;
    }
    
    char LogicInstruction::getOp()const
    {
    	return this->op;
    }
    
    int LogicInstruction::getPageNo1()const
    {
    	return this->pageNo1;
    }
    
    string LogicInstruction::getAddr1()const
    {
    	return this->addr1;
    }
    
    int LogicInstruction::getPageNo2()const
    {
    	return this->pageNo2;
    }
    
    string LogicInstruction::getAddr2()const
    {
    	return this->addr2;
    }
    
    //MemoryBlock.h
    #pragma once
    #include <iostream>
    
    using namespace std;
    
    class MemoryBlock
    {
    	int blockNo;//内存块号
    	int lastUsed;//上次使用时间
    public:
    	MemoryBlock(int blockNo, int lastUsed = 1);
    	void increase();
    	void init();
    	int getBlockNo()const;
    	int getLastUsed()const;
    };
    
    //MemoryBlock.cpp
    #include "MemoryBlock.h"
    
    /// <summary>
    /// 构造函数
    /// </summary>
    /// <param name="blockNo">内存块号</param>
    /// <param name="lastUsed">上次使用时间,默认为1</param>
    MemoryBlock::MemoryBlock(int blockNo, int lastUsed)
    {
    	this->blockNo = blockNo;
    	this->lastUsed = lastUsed;
    }
    
    /// <summary>
    /// 上次使用时间+1
    /// </summary>
    void MemoryBlock::increase()
    {
    	this->lastUsed++;
    }
    
    /// <summary>
    /// 上次使用时间重置
    /// </summary>
    void MemoryBlock::init()
    {
    	this->lastUsed = 1;
    }
    
    int MemoryBlock::getBlockNo()const
    {
    	return this->blockNo;
    }
    
    int MemoryBlock::getLastUsed()const
    {
    	return this->lastUsed;
    }
    
    //PageTableEntry.h
    #pragma once
    #include <iostream>
    
    using namespace std;
    
    class PageTableEntry
    {
    	int access;//标志位,标志是否在内存中
    	int bolckNo;//分配到的内存块号
    	int modify;//修改位
    	string diskPos;//在磁盘中的地址
    public:
    	PageTableEntry(int access, int blockNo, int modify, string diskPos);
    	int getAccess()const;
    	int getBlockNo()const;
    	int getModify()const;
    	string getDiskPos()const;
    	void setAccess(int access);
    	void setBlockNo(int blockNo);
    	void setModify(int modify);
    	void setDiskPos(string diskPos);
    };
    
    //PageTableEntry.cpp
    #include "PageTableEntry.h"
    
    PageTableEntry::PageTableEntry(int access, int blockNo, int modify, string diskPos)
    {
    	this->access = access;
    	this->bolckNo = blockNo;
    	this->modify = modify;
    	this->diskPos = diskPos;
    }
    
    int PageTableEntry::getAccess()const
    {
    	return this->access;
    }
    
    int PageTableEntry::getBlockNo()const
    {
    	return this->bolckNo;
    }
    
    string PageTableEntry::getDiskPos()const
    {
    	return this->diskPos;
    }
    
    int PageTableEntry::getModify()const
    {
    	return this->modify;
    }
    
    void PageTableEntry::setAccess(int access)
    {
    	this->access = access;
    }
    
    void PageTableEntry::setBlockNo(int blockNo)
    
    {
    	this->bolckNo = blockNo;
    }
    
    void PageTableEntry::setDiskPos(string diskPos)
    {
    	this->diskPos = diskPos;
    }
    
    void PageTableEntry::setModify(int modify)
    {
    	this->modify = modify;
    }
    
    //RequestPagingStorageManagement.h
    #pragma once
    #include <iostream>
    #include <vector>
    #include <queue>
    #include <string>
    #include "PageTableEntry.h"
    #include "MemoryBlock.h"
    #include "LogicInstruction.h"
    
    using namespace std;
    
    enum class PageReplacementAlgorithm
    {
    	FIFO, LRU
    };
    
    class RequestPagingStorageManagement
    {
    	static void FIFO(vector<PageTableEntry>& pageTable, queue<MemoryBlock>& blocks, int pageNo);
    	static void LRU(vector<PageTableEntry>& pageTable, queue<MemoryBlock>& blocks, int pageNo);
    	static MemoryBlock* findBlock(int blockNo, queue<MemoryBlock>& blocks);
    	static void increase(queue<MemoryBlock>& blocks);
    	static int findPageTableEntryByBlockNo(int blockNo, vector<PageTableEntry>& pageTable);
    	static MemoryBlock* findLeastRecentlyUsed(queue<MemoryBlock>& blocks, vector<PageTableEntry>& pageTable);
    	static void modifyData(PageTableEntry& cur, PageTableEntry& old);
    	static void printPageTable(vector<PageTableEntry> pageTable);
    	static string calculatePhysicalAddress(vector<PageTableEntry>& pageTable, int pageNo, string addr, queue<MemoryBlock>& blocks, PageReplacementAlgorithm PRA);
    public:
    	static void requestPagingStorageManage(vector<PageTableEntry> pageTable, queue<MemoryBlock> blocks, queue<LogicInstruction> ops, PageReplacementAlgorithm PRA);
    };
    
    //RequestPagingStorageManagement.cpp
    #include "RequestPagingStorageManagement.h"
    
    /// <summary>
    /// 打印页表
    /// </summary>
    /// <param name="pageTable">要打印的页表</param>
    void RequestPagingStorageManagement::printPageTable(vector<PageTableEntry> pageTable)
    {
    	cout << "页号" << "\t标志" << "\t主存块号" << "\t修改标志" << "\t磁盘位置" << endl;
    	for (int i = 0; i < pageTable.size(); i++)
    	{
    		cout << i << "\t" << pageTable[i].getAccess() << "\t" << pageTable[i].getBlockNo() << "\t\t" << pageTable[i].getModify() << "\t\t" << pageTable[i].getDiskPos() << endl;
    	}
    }
    
    /// <summary>
    /// 修改新页表项与老页表项的数据
    /// </summary>
    /// <param name="cur">新页表项</param>
    /// <param name="old">老页表项</param>
    void RequestPagingStorageManagement::modifyData(PageTableEntry& cur, PageTableEntry& old)
    {
    	cur.setBlockNo(old.getBlockNo());//老页表项的内存块分给新页表项
    	cur.setAccess(1);//设置标志位
    	cur.setModify(0);
    	old.setAccess(0);
    	old.setDiskPos(cur.getDiskPos());//为简便起见,直接交换磁盘空间
    	cur.setDiskPos("");
    }
    
    /// <summary>
    /// FIFO调度策略
    /// </summary>
    /// <param name="pageTable">页表</param>
    /// <param name="blocks">所有内存块</param>
    /// <param name="pageNo">页号</param>
    void RequestPagingStorageManagement::FIFO(vector<PageTableEntry>& pageTable, queue<MemoryBlock>& blocks, int pageNo)
    {
    	PageTableEntry& cur = pageTable[pageNo];//当前要使用的页号,即在磁盘中将要换到内存中的页表项
    	int index = findPageTableEntryByBlockNo(blocks.front().getBlockNo(), pageTable);//找到要被换到磁盘中的页表项的索引
    	PageTableEntry& old = pageTable[index];//要被换到磁盘中的页表项
    	cout << pageNo << "号与" << index << "号交换,";
    	modifyData(cur, old);//修改页表项数据
    	MemoryBlock& t = blocks.front();//第一个内存块换到最后
    	blocks.pop();
    	blocks.push(t);
    }
    
    /// <summary>
    /// LRU调度策略
    /// </summary>
    /// <param name="pageTable">页表</param>
    /// <param name="blocks">所有内存块</param>
    /// <param name="pageNo">页号</param>
    void RequestPagingStorageManagement::LRU(vector<PageTableEntry>& pageTable, queue<MemoryBlock>& blocks, int pageNo)
    {
    	PageTableEntry& cur = pageTable[pageNo];//当前要使用的页号,即在磁盘中将要换到内存中的页表项
    	MemoryBlock* p = findLeastRecentlyUsed(blocks, pageTable);//寻找最近最久未使用的内存块
    	int index = findPageTableEntryByBlockNo(p->getBlockNo(), pageTable);//找到内存号对应的页表项的索引
    	PageTableEntry& old = pageTable[index];//将被换到磁盘的页表项
    	cout << pageNo << "号与" << index << "号交换,";
    	modifyData(cur, old);//修改页表项数据
    	p->init();
    }
    
    /// <summary>
    /// 寻找占用该内存块号的页表项的索引
    /// </summary>
    /// <param name="blockNo">内存块号</param>
    /// <param name="pageTable">页表</param>
    /// <returns>对应页表项的索引</returns>
    int RequestPagingStorageManagement::findPageTableEntryByBlockNo(int blockNo, vector<PageTableEntry>& pageTable)
    {
    	for (int i = 0; i < pageTable.size(); i++)
    	{
    		if (pageTable[i].getBlockNo() == blockNo && pageTable[i].getAccess() == 1)
    		{//必须是正在内存中的页表项
    			return i;
    		}
    	}
    	return -1;
    }
    
    /// <summary>
    /// 寻找最近最久未使用的页表项占有的内存块
    /// </summary>
    /// <param name="blocks">内存块</param>
    /// <param name="pageTable">页表</param>
    /// <returns>对应的内存块的指针</returns>
    MemoryBlock* RequestPagingStorageManagement::findLeastRecentlyUsed(queue<MemoryBlock>& blocks, vector<PageTableEntry>& pageTable)
    {
    	MemoryBlock* max = &blocks.front();
    	int size = blocks.size();
    	for (int i = 0; i < size; i++)
    	{
    		MemoryBlock* mb = &blocks.front();
    		if (mb->getLastUsed() > max->getLastUsed() && pageTable[findPageTableEntryByBlockNo(mb->getBlockNo(), pageTable)].getAccess() == 1)
    		{//寻找lastUsed最大的内存块 并且 当前内存块已经分配
    			max = mb;
    		}
    		blocks.pop();
    		blocks.push(*mb);
    	}
    	//因为pop会直接析构该元素,所以此时的指针只是副本,需要重新寻找真正的在blocks中的地址
    	max = findBlock(max->getBlockNo(), blocks);//根据当前找到的最大值的内存块号寻找在blocks中的地址
    	return max;
    }
    
    /// <summary>
    /// 根据内存块号寻找对应内存块
    /// </summary>
    /// <param name="blockNo">内存块号</param>
    /// <param name="blocks">所以内存块</param>
    /// <returns>对应内存块的指针,未找到返回NULL</returns>
    MemoryBlock* RequestPagingStorageManagement::findBlock(int blockNo, queue<MemoryBlock>& blocks)
    {
    	int size = blocks.size();
    	MemoryBlock* p = NULL;
    	bool flag = false;//标志是否找到
    	for (int i = 0; i < size; i++)
    	{
    		flag = false;
    		MemoryBlock& mb = blocks.front();
    		if (mb.getBlockNo() == blockNo)
    		{
    			flag = true;
    		}
    		blocks.pop();//pop之后会调用析构函数,需要在push之后再用指针接收
    		blocks.push(mb);
    		if (flag)
    		{
    			p = &blocks.back();
    		}
    	}
    	return p;
    }
    
    /// <summary>
    /// 将所以内存块的lastUsed+1
    /// </summary>
    /// <param name="blocks">内存块</param>
    void RequestPagingStorageManagement::increase(queue<MemoryBlock>& blocks)
    {
    	int size = blocks.size();
    	MemoryBlock* p = NULL;
    	for (int i = 0; i < size; i++)
    	{
    		p = &blocks.front();
    		p->increase();
    		blocks.pop();
    		blocks.push(*p);
    	}
    }
    
    /// <summary>
    /// 计算物理地址
    /// </summary>
    /// <param name="pageTable">页表</param>
    /// <param name="pageNo">页号</param>
    /// <param name="addr">逻辑地址</param>
    /// <param name="blocks">所有内存块</param>
    /// <param name="PRA">页面置换策略</param>
    /// <returns>逻辑地址对应的物理地址</returns>
    string RequestPagingStorageManagement::calculatePhysicalAddress(vector<PageTableEntry>& pageTable, int pageNo, string addr, queue<MemoryBlock>& blocks, PageReplacementAlgorithm PRA)
    {
    	PageTableEntry cur = pageTable[pageNo];
    	string phyAddr;
    	MemoryBlock* p = NULL;
    	if (cur.getAccess() == 1)//当前页表项在内存中
    	{
    		phyAddr = to_string(cur.getBlockNo()) + addr + "H";//计算物理地址
    		MemoryBlock* p = findBlock(cur.getBlockNo(), blocks);
    		increase(blocks);//所有内存块上次访问时间+1
    		p->init();//当前页表项上次使用时间重置
    	}
    	else//当前页表项不在内存中
    	{
    		switch (PRA)
    		{
    		case PageReplacementAlgorithm::FIFO:
    			cout << "使用FIFO策略进行置换,";
    			FIFO(pageTable, blocks, pageNo);//使用FIFO策略
    			cout << "置换后的页表:" << endl;
    			printPageTable(pageTable);
    			phyAddr = calculatePhysicalAddress(pageTable, pageNo, addr, blocks, PRA);//计算物理地址
    			break;
    		case PageReplacementAlgorithm::LRU:
    			cout << "使用LRU策略进行置换,";
    			LRU(pageTable, blocks, pageNo);//使用LRU策略
    			cout << "置换后的页表:" << endl;
    			printPageTable(pageTable);
    			phyAddr = calculatePhysicalAddress(pageTable, pageNo, addr, blocks, PRA);//计算物理地址
    			break;
    		default:
    			cout << "ERROR" << endl;
    			break;
    		}
    	}
    	return phyAddr;
    }
    
    /// <summary>
    /// 请求分页式存储管理
    /// </summary>
    /// <param name="pageTable">页表</param>
    /// <param name="blocks">所有内存块</param>
    /// <param name="ops">所有逻辑指令</param>
    /// <param name="PRA">页面置换策略</param>
    void RequestPagingStorageManagement::requestPagingStorageManage(vector<PageTableEntry> pageTable, queue<MemoryBlock> blocks, queue<LogicInstruction> ops, PageReplacementAlgorithm PRA)
    {
    	cout << "初始页表为:" << endl;
    	printPageTable(pageTable);
    	cout << "------------------------------------------" << endl;
    	LogicInstruction cur = ops.front();
    	while (!ops.empty())//执行所有指令
    	{
    		cur = ops.front();
    		ops.pop();
    		cout << "执行指令 " << cur.getOp() << " " << cur.getPageNo1() << " " << cur.getAddr1() << " " << cur.getPageNo2() << " " << cur.getAddr2() << endl;
    		string leftAddr = calculatePhysicalAddress(pageTable, cur.getPageNo1(), cur.getAddr1(), blocks, PRA);//计算左操作数物理地址
    		string rightAddr = calculatePhysicalAddress(pageTable, cur.getPageNo2(), cur.getAddr2(), blocks, PRA);//计算右操作数物理地址
    		cout << "执行结果(" << leftAddr << ")" << cur.getOp() << "(" << rightAddr << ")" << endl;
    		cout << "------------------------------------------" << endl;
    	}
    	cout << "最终页表为:" << endl;
    	printPageTable(pageTable);
    	cout << "------------------------------------------" << endl;
    }
    
    	vector<PageTableEntry> pageTable;
    	pageTable.push_back(PageTableEntry(1, 3, 1, ""));
    	pageTable.push_back(PageTableEntry(1, 4, 1, ""));
    	pageTable.push_back(PageTableEntry(1, 5, 1, ""));
    	pageTable.push_back(PageTableEntry(0, 0, 1, "030"));
    	pageTable.push_back(PageTableEntry(0, 0, 1, "025"));
    	pageTable.push_back(PageTableEntry(0, 0, 1, "026"));
    	queue<MemoryBlock> blocks;
    	blocks.push(MemoryBlock(3, 1));
    	blocks.push(MemoryBlock(4, 2));
    	blocks.push(MemoryBlock(5, 3));
    	queue<LogicInstruction> ops;
    	ops.push(LogicInstruction('+', 0, "030", 2, "003"));
    	ops.push(LogicInstruction('-', 1, "050", 2, "005"));
    	ops.push(LogicInstruction('*', 2, "001", 5, "004"));
    	ops.push(LogicInstruction('/', 3, "007", 1, "031"));
    	PageReplacementAlgorithm PRA1 = PageReplacementAlgorithm::FIFO;
    	PageReplacementAlgorithm PRA2 = PageReplacementAlgorithm::LRU;
    	cout << "********************FIFO********************" << endl;
    	RequestPagingStorageManagement::requestPagingStorageManage(pageTable, blocks, ops, PRA1);
    	cout << "********************LRU********************" << endl;
    	RequestPagingStorageManagement::requestPagingStorageManage(pageTable, blocks, ops, PRA2);
    
    

    结果

    FIFO
    假设初始内存分配顺序为345,每次按先入先出的顺序置换页面,所以置换时也是一次按照345的顺序换出相应的数据
    LRU
    最近最久未使用,假设345内存块的上次使用的时间为123,所以5号内存块是最久未使用的,所以第一个换出的应该是5号内存块的数据
    
    ********************FIFO********************
    初始页表为:
    页号    标志    主存块号        修改标志        磁盘位置
    0       1       3               1
    1       1       4               1
    2       1       5               1
    3       0       0               1               030
    4       0       0               1               025
    5       0       0               1               026
    ------------------------------------------
    执行指令 + 0 030 2 003
    执行结果(3030H)+(5003H)
    ------------------------------------------
    执行指令 - 1 050 2 005
    执行结果(4050H)-(5005H)
    ------------------------------------------
    执行指令 * 2 001 5 004
    使用FIFO策略进行置换,5号与0号交换,置换后的页表:
    页号    标志    主存块号        修改标志        磁盘位置
    0       0       3               1               026
    1       1       4               1
    2       1       5               1
    3       0       0               1               030
    4       0       0               1               025
    5       1       3               0
    执行结果(5001H)*(3004H)
    ------------------------------------------
    执行指令 / 3 007 1 031
    使用FIFO策略进行置换,3号与1号交换,置换后的页表:
    页号    标志    主存块号        修改标志        磁盘位置
    0       0       3               1               026
    1       0       4               1               030
    2       1       5               1
    3       1       4               0
    4       0       0               1               025
    5       1       3               0
    使用FIFO策略进行置换,1号与2号交换,置换后的页表:
    页号    标志    主存块号        修改标志        磁盘位置
    0       0       3               1               026
    1       1       5               0
    2       0       5               1               030
    3       1       4               0
    4       0       0               1               025
    5       1       3               0
    执行结果(4007H)/(5031H)
    ------------------------------------------
    最终页表为:
    页号    标志    主存块号        修改标志        磁盘位置
    0       0       3               1               026
    1       1       5               0
    2       0       5               1               030
    3       1       4               0
    4       0       0               1               025
    5       1       3               0
    ------------------------------------------
    ********************LRU********************
    初始页表为:
    页号    标志    主存块号        修改标志        磁盘位置
    0       1       3               1
    1       1       4               1
    2       1       5               1
    3       0       0               1               030
    4       0       0               1               025
    5       0       0               1               026
    ------------------------------------------
    执行指令 + 0 030 2 003
    执行结果(3030H)+(5003H)
    ------------------------------------------
    执行指令 - 1 050 2 005
    执行结果(4050H)-(5005H)
    ------------------------------------------
    执行指令 * 2 001 5 004
    使用LRU策略进行置换,5号与2号交换,置换后的页表:
    页号    标志    主存块号        修改标志        磁盘位置
    0       1       3               1
    1       1       4               1
    2       0       5               1               026
    3       0       0               1               030
    4       0       0               1               025
    5       1       5               0
    执行结果(5001H)*(5004H)
    ------------------------------------------
    执行指令 / 3 007 1 031
    使用LRU策略进行置换,3号与1号交换,置换后的页表:
    页号    标志    主存块号        修改标志        磁盘位置
    0       1       3               1
    1       0       4               1               030
    2       0       5               1               026
    3       1       4               0
    4       0       0               1               025
    5       1       5               0
    使用LRU策略进行置换,1号与0号交换,置换后的页表:
    页号    标志    主存块号        修改标志        磁盘位置
    0       0       3               1               030
    1       1       3               0
    2       0       5               1               026
    3       1       4               0
    4       0       0               1               025
    5       1       5               0
    执行结果(4007H)/(3031H)
    ------------------------------------------
    最终页表为:
    页号    标志    主存块号        修改标志        磁盘位置
    0       0       3               1               030
    1       1       3               0
    2       0       5               1               026
    3       1       4               0
    4       0       0               1               025
    5       1       5               0
    ------------------------------------------
    请按任意键继续. . .
    
    
    
    展开全文
  • 写了八个页面替换的算法,算是比较全了,包括MFC,clock,FIFO,LRU等算法,并且用模块化的思路,输出也用表格
  • 操作系统实验-请求分页存储管理页面Optimal、FIFO、LRU调度算法,相关细节介绍如题,很是全面的东东,直接可用。Donald_Tyr发布,必属精品! QQ:3729734 E_mail:i.d.card@msn.com BLOG:http://di-bar.f31.net
  • 题目描述:请求分页系统中的置换算法 1.通过如下方法产生一指令序列,共 320 条指令。 A. 在[1,32k-2]的指令地址之间随机选取一起点M,访问 M; B. 顺序访问M+1; C. 在[0,M-1]中随机选取M1,访问 M1; D. 顺序...

    背景

    1. 先进先出(FIFO)页面置换算法
      该算法总是淘汰最新进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。
    2. 最近最久未使用(LRU)页面置换算法
      最近最久未使用(LRU)页面置换算法,是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似, 因此,LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当需淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最久未使用的页面予以淘汰。
    3. 最佳(Optimal)页面置换算法
      该算法选择的被淘汰页面,将是以后永远不使用的,或许是在最长(未来)时间内不再被访问的页面。采用该算法,通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但可以利用该算法去评价其他算法。

    题目描述:请求分页系统中的置换算法

    1.通过如下方法产生一指令序列,共 320 条指令。

    • A. 在[1,32k-2]的指令地址之间随机选取一起点M,访问 M;
    • B. 顺序访问M+1;
    • C. 在[0,M-1]中随机选取M1,访问 M1;
    • D. 顺序访问M1+1;
    • E. 在[M1+2,32k-2]中随机选取M2,访问 M2;
    • F. 顺序访问M2+1;
    • G. 重复 A—F,直到执行 320 次指令。
    • H.指令序列变换成页地址流设:(1)页面大小为 1K;(2)用户虚存容量为 32K。

    2. 计算并输出下述各种算法在不同内存页块(页块个数范围:8-32)下的命中率。

    • A. 先进先出(FIFO)页面置换算法
    • B. 最近最久未使用(LRU)页面置换算法
    • C. 最佳(Optimal)页面置换算法

    提示:

    • A.命中率=1-页面失效次数/页地址流长度
    • B.本实验中,页地址流长度为 320,页面失效次数为每次访问相应指令时,该指令所对应的页不在内存的次数。

    算法设计

    整体设计

    设置全局变量保存指令的个数和指令数组,在make_instruct()函数中生成随机数填充这个数组。
    内存这里用链表来组织,表示如下:

    struct node {
        int instruct = 0;
        int time = 0;
        node* next = NULL;
    };
    

    instruct表示指令号,time在不同算法中有具体含义。
    三种算法对于三个函数,每个函数都是如:double f(int a);的格式,其中参数表示当前内存块大小(8-32),返回值是命中率。
    主函数只需对不同的内存块大小调用三个函数并输出结果即可。

    产生指令序列

    首先写一个函数生成给定范围内的一个随机数,由于需要连续获得多个随机数,这里先在main函数srand一个种子,然后不断调用函数即可。

    srand((unsigned int)time(NULL));
    int rand(int min, int max)//产生指定范围[min,max]的随机数。
    {
        return rand() % (max - min + 1) + min;
    }
    

    构造指令序列,只需要简单的按照题目要求一步步做并且循环即可,注意这里只在循环开始处有一次判断,而每次循环会产生6个指令,所以这里将指令数组开大了一点,省去了多次判断。
    const int instruct_num = 320; int instruct_arr[instruct_num + 6];
    另外,为了输出结果的美观用cout << setw(8)设置输出的宽度以对齐。

    
    void make_instruct() {//产生指令序列
        int n = 0;
        while (n < instruct_num) {
            int M = rand(1,30);
            instruct_arr[n++] = M;
            instruct_arr[n++] = M + 1;
            int M1 = rand(0, M - 1);
            instruct_arr[n++] = M1;
            instruct_arr[n++] = M1 + 1;
            int M2 = rand(M1 + 2, 30);
            instruct_arr[n++] = M2;
            instruct_arr[n++] = M2 + 1;
        }
    }
    

    先进先出(FIFO)

    这是最基础的,以下的算法都继承这种思想,只是用于淘汰的策略有所变化。
    首先新建两个节点HeadTailHead为头节点,其数据域Head->instruct表示当前内存中实际有多少被占用,其next指向第一块被占用的内存。Tail为尾指针,指向内存的尾部。
    算法首先是一层循环,遍历所有的(320个)指令。对于每个指令判断是否在内存中,若在则hit置为1。如果在内存中则不做任何操作,不在则要让failure_times加一,然后判断内存是否被占满,若未被占满则直接加入链表,若被占用则要淘汰当前队列中的一个指令,并将当前指令插入内存的合适位置。
    这里用到的淘汰算法:先进先出,即找到最先进来的即可,这里我是每次插入到链表尾,故链表头是最先进来的,所以每次都删除链表头后面的第一个指令并将新指令加到链表尾即可,注意每次更新Tail的位置。

    最近最久未使用(LRU)

    这里只介绍与FIFO不同之处。

    • 设立一个变量clock表示时钟,初始值为999,主循环一次clock就减1.
    • 如果当前指令在内存中则将其时间刷新为当前的时钟。
    • 淘汰算法:遍历内存队列找到time最大的,将其替换为新的节点即可,新加入的节点time为当前时钟clock

    最佳(Optimal)

    • 淘汰算法:每次遍历内存队列,对于每个指令,再次遍历全部指令集,找到将来还要多久这条指令会再被执行(下一个出现的位置减去当前位置)。

    代码实现

    #include <iostream>
    #include <time.h>
    #include <iomanip>
    using namespace std;
    
    const int instruct_num = 320;
    int instruct_arr[instruct_num + 6];
    struct node {
        int instruct = 0;
        int time = 0;
        node* next = NULL;
    };
    int rand(int min, int max)//产生指定范围[min,max]的随机数。
    {
        return rand() % (max - min + 1) + min;
    }
    void make_instruct() {//产生指令序列
        int n = 0;
        while (n < instruct_num) {
            int M = rand(1,30);
            instruct_arr[n++] = M;
            instruct_arr[n++] = M + 1;
            int M1 = rand(0, M - 1);
            instruct_arr[n++] = M1;
            instruct_arr[n++] = M1 + 1;
            int M2 = rand(M1 + 2, 30);
            instruct_arr[n++] = M2;
            instruct_arr[n++] = M2 + 1;
        }
    }
    double C_FIFO(int block_size) {
        int failure_times = 0;
        node* Head = new node;
        node* Tail = Head;
        for (int i = 0; i < instruct_num; i++) {
            int cur_instruct = instruct_arr[i];
            int hit = 0;
           
            for (node* p = Head->next; p != NULL; p = p->next)
                if (p->instruct == cur_instruct)
                    hit = 1;
    
            if (!hit){
                failure_times++;
                if (Head->instruct >= block_size) //内存已满
                    Head->next = Head->next->next;                       
                else 
                    Head->instruct++;             
                
                Tail->next = new node;
                Tail = Tail->next;
                Tail->instruct = cur_instruct;
                Tail->next = NULL;
            }
        }
    
        return 1.0 - (double)failure_times / instruct_num;
    }
    double C_LRU(int block_size) {
        int failure_times = 0;
        node* Head = new node;
        node* Tail = Head;
        int clock = 999;
    
        for (int i = 0; i < instruct_num; i++) {
            clock--;
            int cur_instruct = instruct_arr[i];
            int hit = 0;
            for (node* p = Head->next; p != NULL; p = p->next)
                if (p->instruct == cur_instruct) {
                    hit = 1;
                    p->time = clock;//刷新时钟
                }
           
            if (!hit) {
                failure_times++;
                if (Head->instruct >= block_size) { //内存已满
                    node* t = new node; t->time = -1;
                    for (node* p = Head->next; p != NULL; p = p->next)//遍历找到最久未使用的
                        if (p->time > t->time)
                            t = p;
                    
                    t->instruct = cur_instruct;
                    t->time = clock;
          
                }
                else {
                    Head->instruct++;
                    Tail->next = new node;
                    Tail = Tail->next;
                    Tail->instruct = cur_instruct;
                    Tail->time = clock;
                    Tail->next = NULL;
                }
            }
        }
        return 1.0 - (double)failure_times / instruct_num;
    }
    double C_Optimal(int block_size) {
        int failure_times = 0;
        node* Head = new node;
        node* Tail = Head;
        for (int i = 0; i < instruct_num; i++) {
            int cur_instruct = instruct_arr[i];
            int hit = 0;
    
            for (node* p = Head->next; p != NULL; p = p->next)
                if (p->instruct == cur_instruct)
                    hit = 1;
    
            if (!hit) {
                failure_times++;
                if (Head->instruct >= block_size) { //内存已满
                    //找到每个请求还有多久会被用到
                    for (node* p = Head->next; p != NULL; p = p->next) {
                        p->time = 999;
                        for (int j = i + 1; j < instruct_num; j++)
                            if (p->instruct == instruct_arr[i]) {
                                p->time = j - i;
                                break;
                            }                 
                    }
                    //找到最久不被用到的淘汰
                    node* t = new node; t->time = -1;
                    for (node* p = Head->next; p != NULL; p = p->next)//遍历找到最久未使用的
                        if (p->time > t->time)
                            t = p;
    
                    t->instruct = cur_instruct;
    
                }
                else {
                    Head->instruct++;
                    Tail->next = new node;
                    Tail = Tail->next;
                    Tail->instruct = cur_instruct;
                    Tail->next = NULL;
                }        
            }
        }
        return 1.0 - (double)failure_times / instruct_num;;
    }
    int main()
    {
        srand((unsigned int)time(NULL));
        make_instruct();
        
        cout << "指令序列为:" << endl;
        int i = 0;
        while (i++ < instruct_num) {
            cout << instruct_arr[i] << "\t";
            if (i % 20 == 0)cout << endl;
        }cout << endl << endl;
    
        cout << "SIZE\t\t" << "FIFO\t\t" << "LRU\t\t" << "Optimal" << endl;
        for (int disk_block_size = 8; disk_block_size <= 32; disk_block_size++) {
    
            cout << disk_block_size << "\t";
            cout << setw(8) << C_FIFO(disk_block_size) << "\t";
            cout << setw(8) << C_LRU(disk_block_size) << "\t";
            cout << setw(8) << C_Optimal(disk_block_size) << "\t";
            cout << endl;
    
        }
    }
    

    运行结果

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 内存给进程分配物理块,页面需放入物理块中。当要访问的页面在物理块中,表示命中;否则,需要将物理块中的某页面置换出来,将...FIFO:先进先出 页面置换算法 当物理块已满,而当前访问的页面不在物理块中,则将...

    内存给进程分配物理块,页面需放入物理块中。当要访问的页面在物理块中,表示命中;否则,需要将物理块中的某页面置换出来,将当前页面放进去即置换。

    缺页率=(页面置换次数+物理块数)/访问的页面总数

    一般我们将内存中的初始物理块置为0,将页面依次累加放入,即将物理块数合并进页面置换次数中。

    FIFO:先进先出 页面置换算法   

             当物理块已满,而当前访问的页面不在物理块中,则将最先进入物理块的页面置换出来。

             小窍门:新加入的页面永远放最上面,从下面出的永远是最先加入的页面。

    LRU:最近最少使用页面置换算法(节省容量不大的内存为最多的进程提供资源)

              当物理块已满,而当前访问的页面不在物理块中,则比较分析此时物理块中的页面,在访问队列中的位置离当前页面越近表示最近被访问过,越远表示最近最少使用,就将那个页面置换掉,此时要访问的页面替补上。

    ORT:最优/最佳置换算法(未来最长时间不会被使用)

              当物理块已满,而当前访问的页面不在物理块中,则比较分析此时物理块中的页面,在访问队列中的位置离当前页面越远表示接下来最长时间不会被使用,就将那个页面置换掉,此时要访问的页面替补上。最后一个页面要替换就直接替换页面在前面序列中离它最近的即可。

     

    展开全文
  • FIFO先进先出算法 算法原理: 要淘汰内存某页时,选择 最先进入内存的页 淘汰。 例:已知 进程页面走向如下: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 供该进程使用的内存块数为3, 采用 请求...
  • 请求分页存储系统

    2012-01-07 21:08:24
    操作系统请求分页存储系统课程设计、含OPT FIFO LRU CLOCK算法源代码、可运行、、
  • 请求分页存储管理系统采用java编写,含有详细的报告
  • 模拟仿真请求分页调度算法OPT、FIFO、LRU、LFU、CLOCK等模拟页面调度算法,并提供性能比较分析功能。
  • 操作系统请求分页

    2017-12-04 21:27:41
    为了简单起见。页面淘汰算法采用 FIFO页面淘汰算法,并且在淘汰一页时,判断它是否被改写过,如果被修改过,将它写回到辅存。
  • 模拟仿真请求分页调度算法OPT、FIFO、LRU、LFU、CLOCK等模拟页面调度算法,并提供性能比较分析功能。用MFC界面实现
  • C++编写的请求分页储存管理的页置换算法模拟程序,模拟OPT,FIFO和LRU算法。可以输入序列也可以随机生成访问序列。可以输出整个调度的流程(表),缺页次数和缺页率。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,663
精华内容 2,665
关键字:

请求分页fifo