页面算法

① 最佳页面置换算法的介绍

最佳页面置换算法是Belady于1966年提出的一种理论上的算法。是一种保证最少的缺页率的理想化算法。

② 页面淘汰算法

LRU（2个块）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 3 3 2 2 5 5 2 2 2 2 7 7 3 3 1 1 3 3
2 2 4 4 1 1 6 6 1 1 3 3 6 6 2 2 2 2 6
缺页中断18次

LRU（4个块）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 5 3 3 3 3 3 3 3 3 3
4 4 4 4 6 6 6 6 6 7 7 7 7 1 1 1 1
缺页中断次数10次

FIFO（2个块）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 3 3 6 6 2 2 2 3 3
2 2 4 4 1 1 6 6 1 1 2 7 7 3 3 1 1 1 6
缺页中断次数18次

FIFO（4个块）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 5 5 5 5 5 3 3 3 3 3 1 1 1 1
2 2 2 2 2 2 6 6 6 6 6 7 7 7 7 7 7 3 7
3 3 3 3 3 3 2 2 2 2 2 6 6 6 6 6 6 6
4 4 4 4 4 4 1 1 1 1 1 1 2 2 2 2 2
缺页中断次数：14次

③ 操作系统题：页面置换算法 OPT FIFO LRU

fifo就是先进先出，可以想象成队列
lru是最久未使用，当需要替换页面的时候，向前面看，最久没使用的那个被替换
opt是替换页面的时候，优先替换后面最迟出现的。
不懂再问。。

④ 页面置换算法

淘汰顺序：1，2，6，4，7
页面置换次数：9次

⑤ 页面置换算法的实验

#include <stdio.h>
#define PROCESS_NAME_LEN 32 /*进程名称的最大长度*/
#define MIN_SLICE 10 /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE 1024 /*默认内存的大小*/
#define DEFAULT_MEM_START 0 /*默认内存的起始位置*/

/* 内存分配算法 */
#define MA_FF 1
#define MA_BF 2
#define MA_WF 3

int mem_size=DEFAULT_MEM_SIZE; /*内存大小*/
int ma_algorithm = MA_FF; /*当前分配算法*/
static int pid = 0; /*初始pid*/
int flag = 0; /*设置内存大小标志*/

struct free_block_type
{
int size;
int start_addr;
struct free_block_type *next;
};
struct free_block_type *free_block;

struct allocated_block
{
int pid;
int size;
int start_addr;
char process_name[PROCESS_NAME_LEN];
struct allocated_block *next;
};
struct allocated_block *allocated_block_head;

/*初始化空闲块，默认为一块，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size)
{

struct free_block_type *fb;

fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
if(fb==NULL)
{
printf("No mem\n");
return NULL;
}
fb->size = mem_size;
fb->start_addr = DEFAULT_MEM_START;
fb->next = NULL;
return fb;
}

void display_menu()
{
printf("\n");
printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
printf("2 - Select memory allocation algorithm\n");
printf("3 - New process \n");
printf("4 - Terminate a process \n");
printf("5 - Display memory usage \n");
printf("0 - Exit\n");
}

/*设置内存的大小*/
int set_mem_size()
{
int size;
if(flag!=0)
{ /*防止重复设置*/
printf("Cannot set memory size again\n");
return 0;
}
printf("Total memory size =");
scanf("%d", &size);
if(size>0)
{
mem_size = size;
free_block->size = mem_size;
}
flag=1;
return 1;
}
/*Best-fit使用最小的能够放下将要存放数据的块，First-first使用第一个能够放下将要存放数据的块，Worst-fit使用最大的能够放下将要存放数据的块。*/
/* 设置当前的分配算法 */
/*分区分配算法(Partitioning Placement Algorithm)
*/
void set_algorithm()
{
int algorithm;
printf("\t1 - First Fit\n");/*首次适应算法(FF)：。 */
printf("\t2 - Best Fit\n");/*最佳适应算法(BF)： */

printf("\t3 - Worst Fit\n");
scanf("%d", &algorithm);
if(algorithm>=1 && algorithm <=3) ma_algorithm=algorithm;
/*按指定算法重新排列空闲区链表*/
rearrange(ma_algorithm);
}

void swap(int* data_1,int* data_2)
{
int temp;
temp=*data_1;
*data_1=*data_2;
*data_2=temp;
}

void rearrange_FF()
{
struct free_block_type *tmp, *work;
printf("Rearrange free blocks for FF \n");
tmp = free_block;
while(tmp!=NULL)
{
work = tmp->next;
while(work!=NULL)
{
if( work->start_addr < tmp->start_addr)
{ /*地址递增*/
swap(&work->start_addr, &tmp->start_addr);
swap(&work->size, &tmp->size);
}
else
{
work=work->next;
}
}
tmp=tmp->next;
}
}
/*按BF算法重新整理内存空闲块链表(未完成)
void rearrange_BF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for BF\n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}

}

*/
/*按WF算法重新整理内存空闲块链表(未完成)
void rearrange_WF()
{
struct free_block_type *tmp,*work;
printf("Rearrange free blocks for WF \n");
tmp=free_block;
while(tmp!=NULL)
{
work=tmp->next;
while(work!=NULL)
{

}
}
}
*/

/*按指定的算法整理内存空闲块链表*/
int rearrange(int algorithm)
{
switch(algorithm)
{
case MA_FF: rearrange_FF(); break;
/*case MA_BF: rearrange_BF(); break; */
/*case MA_WF: rearrange_WF(); break; */
}
}

/*创建新的进程，主要是获取内存的申请数量*/
int new_process()
{
struct allocated_block *ab;
int size;
int ret;
ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
if(!ab)
exit(-5);
ab->next = NULL;
pid++;
sprintf(ab->process_name, "PROCESS-%02d", pid);
ab->pid = pid;

printf("Memory for %s:", ab->process_name);
scanf("%d", &size);
if(size>0) ab->size=size;
ret = allocate_mem(ab); /* 从空闲区分配内存，ret==1表示分配ok*/
/*如果此时allocated_block_head尚未赋值，则赋值*/
if((ret==1) &&(allocated_block_head == NULL))
{
allocated_block_head=ab;
return 1;
}
/*分配成功，将该已分配块的描述插入已分配链表*/
else if (ret==1)
{
ab->next=allocated_block_head;
allocated_block_head=ab;
return 2;
}
else if(ret==-1)
{ /*分配不成功*/
printf("Allocation fail\n");
free(ab);
return -1;
}
return 3;
}

/*分配内存模块*/
int allocate_mem(struct allocated_block *ab)
{
struct free_block_type *fbt,*pre,*r;
int request_size=ab->size;
fbt=pre=free_block;
while(fbt!=NULL)
{
if(fbt->size>=request_size)
{
if(fbt->size-request_size>=MIN_SLICE)
{
fbt->size=fbt->size-request_size;
}
/*分配后空闲空间足够大，则分割*/

else
{
r=fbt;
pre->next=fbt->next;
free(r);
/*分割后空闲区成为小碎片，一起分配*/

return 1;
}
}
pre = fbt;
fbt = fbt->next;
}

return -1;
}

/*将ab所表示的已分配区归还，并进行可能的合并*/
int free_mem(struct allocated_block *ab)
{
int algorithm = ma_algorithm;
struct free_block_type *fbt, *pre, *work;

fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
if(!fbt)
return -1;
fbt->size = ab->size;
fbt->start_addr = ab->start_addr;
/*插入到空闲区链表的头部并将空闲区按地址递增的次序排列*/
fbt->next = free_block;
free_block=fbt;
rearrange(MA_FF);
fbt=free_block;
while(fbt!=NULL)
{
work = fbt->next;
if(work!=NULL)
{
/*如果当前空闲区与后面的空闲区相连，则合并*/
if(fbt->start_addr+fbt->size == work->start_addr)
{
fbt->size += work->size;
fbt->next = work->next;
free(work);
continue;
}
}
fbt = fbt->next;
}
rearrange(algorithm); /*重新按当前的算法排列空闲区*/
return 1;
}

/*?释放ab数据结构节点*/
int dispose(struct allocated_block *free_ab)
{
struct allocated_block *pre, *ab;

if(free_ab == allocated_block_head)
{ /*如果要释放第一个节点*/
allocated_block_head = allocated_block_head->next;
free(free_ab);
return 1;
}
pre = allocated_block_head;
ab = allocated_block_head->next;

while(ab!=free_ab)
{
pre = ab;
ab = ab->next;
}
pre->next = ab->next;
free(ab);
return 2;
}
/*查找要删除的进程*/
struct allocated_block* find_process(int pid)
{
struct allocated_block *temp;
temp=allocated_block_head;
while(temp!=NULL)
{
if(temp->pid==pid)
{
return temp;
}
temp=temp->next;
}
}

/*删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点*/
void kill_process()
{
struct allocated_block *ab;
int pid;
printf("Kill Process, pid=");
scanf("%d", &pid);
ab=find_process(pid);
if(ab!=NULL)
{
free_mem(ab); /*释放ab所表示的分配区*/
dispose(ab); /*释放ab数据结构节点*/

}
}

/* 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况 */

int display_mem_usage()
{
struct free_block_type *fbt=free_block;
struct allocated_block *ab=allocated_block_head;
if(fbt==NULL) return(-1);
printf("----------------------------------------------------------\n");

/* 显示空闲区 */
printf("Free Memory:\n");
printf("%20s %20s\n", " start_addr", " size");
while(fbt!=NULL)
{
printf("%20d %20d\n", fbt->start_addr, fbt->size);
fbt=fbt->next;
}
/* 显示已分配区 */
printf("\nUsed Memory:\n");
printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
while(ab!=NULL)
{
printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
ab=ab->next;
}
printf("----------------------------------------------------------\n");
return 0;
}

**********************************************************************
楼主啊，小女子给你的是残缺版滴，要是你给我分，我就把剩下滴给你,上次在北京大学贴吧都被人骗了，世道炎凉啊O(∩_∩)O~

⑥ jsp页面算法求指导

将表格当前列的数值放入<input>中，然后循环这个input里面的数值

比如你“账户累计余额”这里，你将所有这列的数值设置在<input name="total">，将“实际所得”这列数值设置在<input name="shiji" />；将<转出数量>设置在<input name="zhuan">

---------------------------------------------------------------------------------------------------

根据你的需求，我简单写一下。

--------------------------------------------------------------------------------------------------

⑦ 页面置换算法的介绍

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

⑧ 页面置换算法模拟

#include <iostream>
#include <deque>
#include <ctime>
using namespace std;

typedef struct
{
int id; //页面ID
int stayTime; //内存中驻留时间
int unUseTime; //已经多久未被使用
}CPage;
deque<int> RunQueue;
deque<CPage> interPage; //内存中的四个页面
deque<CPage> exterPage; //外存中的N个页面
int presentSeat; //目前运行到了队列的第几个？
int lackNum[3] ={0};
int getRandNum(int range) //返回[0,range)范围内的整数
{
return static_cast<int>(rand()%range);
}
int findPageIdByCmdId(int cmdId) //通过强制转换成整数的形式判断指令属于哪个页面
{
return static_cast<int>(cmdId/10);
}
void InitDevice() //初始化运行队列 按照25% 50% 25%的标准生成
{
srand(static_cast<int>(time(NULL)));
int t_cmdNum = getRandNum(320); //随机选择第一条指令
RunQueue.push_back(t_cmdNum); //将其插入队列
if(t_cmdNum < 319)
RunQueue.push_back(t_cmdNum+1); //顺序执行下一条指令

while(RunQueue.size() <= 320)
{
t_cmdNum = getRandNum(t_cmdNum); //跳转到m1属于[0,m-1]
RunQueue.push_back(t_cmdNum); //将m1插入队列
if(t_cmdNum < 319)
RunQueue.push_back(t_cmdNum+1); //将m1+1插入队列
int temp = 320 - (t_cmdNum + 2);
t_cmdNum = t_cmdNum+2+getRandNum(temp);//跳转到m2属于[m+2,319]
RunQueue.push_back(t_cmdNum); //插入队列
if(t_cmdNum < 319)
RunQueue.push_back(t_cmdNum+1); //将m2+1插入队列
}
while(RunQueue.size() > 320)
RunQueue.pop_back();
}
void InitMemoryQueue() //初始化运行标志、内存外存页面队列
{
presentSeat = 0;
exterPage.clear();
interPage.clear();
for(int i=0;i<32;i++)
{
CPage temp;
temp.id = i;
temp.stayTime = 0;
temp.unUseTime = 0;
exterPage.push_back(temp);
}
}
int searchStatusOfPage(int t_PageId,bool sign) //分别在内外存中查找页面 存在返回位置 不存在返回-1
{
if(sign)
for(unsigned i=0;i<interPage.size();i++)
{
if(t_PageId == interPage[i].id)
return i;
} //这里的括号不能删除，否则if else的匹配会出问题
else
for(unsigned j=0;j<exterPage.size();j++)
if(t_PageId == exterPage[j].id)
return j;
return -1;
}
int searchNextStatusOfInterPage(int start, int id) //OPT算法中查找内存页面中的页面下次需要用到它的时候的队列下标
{ //找到就返回下标 没找到就返回-1
for(int i=start;i < 320;i++)
if(static_cast<int>(RunQueue[i]/10) == id)
return i;
return -1;
}
int findLongestStayTimePage() //FIFO算法中查找在内存中呆了最久的页面
{
int max = 0;
for(unsigned i=1;i<interPage.size();i++)
if(interPage[i].stayTime>interPage[max].stayTime)
max = i;
return max;
}
int findLongestUnUseTimePage() //LRU算法中查找最久未使用的页面
{
int max = 0;
for(unsigned j=0;j<interPage.size();j++)
if(interPage[j].unUseTime>interPage[max].unUseTime)
max = j;
return max;
}
int findNeedLongestTimePage() //OPT算法中查找最长时间不会用到的页面
{
deque<int> temp;
for(unsigned i=0;i < interPage.size();i++)
{
int it = searchNextStatusOfInterPage(presentSeat,interPage[i].id);
if(it == -1)
return i;
temp.push_back(it);
}
int max = -1,status = 0;
for(unsigned j=1;j < temp.size();j++)
{
if(max < temp[j])
{
max = temp[j];
status = j;
}
}
return status; //返回需要最长时间才执行的页面在内存中的位置
}
void directFlod(int t_PageId) //当内存空间还有剩余时直接调入
{
int status = searchStatusOfPage(t_PageId,false);
if(status == -1) return;
interPage.push_back(exterPage[status]); //先插入节点到内存，再从外存中将其删除
exterPage.erase(exterPage.begin()+status);
}
bool Manage(int count,int t_PageId) //当内存已经满了需要按照三种算法调度时
{
int status = searchStatusOfPage(t_PageId,false); //获取执行页面在外存中的索引地址
if(status == -1)
return false;
int targetStatus = 0;
if(count == 0)
targetStatus = findNeedLongestTimePage();
else if(count == 1)
targetStatus = findLongestStayTimePage();
else if(count == 2)
targetStatus = findLongestUnUseTimePage();
interPage[targetStatus].stayTime = 0;
interPage[targetStatus].unUseTime = 0;
swap(exterPage[status],interPage[targetStatus]);
return true;
}
void Run(int count) //运行，通过count来决定使用什么算法
{
while(presentSeat < 320)
{
for(unsigned i=0;i<interPage.size();i++)
{
interPage[i].stayTime++;
interPage[i].unUseTime++;
}
int t_PageId = findPageIdByCmdId(RunQueue[presentSeat++]),status = -1; //找到当前将要执行的指令的页面号
if((status =searchStatusOfPage(t_PageId,true)) != -1)
{
interPage[status].unUseTime = 0;
continue;
}
lackNum[count]++;
if(interPage.size()<4)
directFlod(t_PageId);
else
Manage(count,t_PageId);
}
}
void main(void) //主函数
{
InitDevice();
int count = 0;
while(count<3)
{
InitMemoryQueue();
Run(count);
cout<<(double)lackNum[count++]/320*100<<"%"<<endl;
}
}

参考资料：http://..com/question/41040745.html

希望采纳

⑨ 哪种页页面置换算法可以保证最少缺页率

<pre t="code" l="cpp">(1) FIFO
1 2 3 4 1 2 5 1 2 3 4 5
----------------------------------------
1 2 3 4 1 2 5 5 5 3 4 4
1 2 3 4 1 2 2 2 5 3 3 该行是怎么算出来的？
1 2 3 4 1 1 1 2 5 5 该行是怎么算出来的？
----------------------------------------
缺页中断次数=9
FIFO是这样的：3个内存块构成一个队列，前3个页面依次入队（3个缺页），内存中为3-2-1；
接着要访问4号页面，内存中没有（1个缺页），按FIFO，1号页面淘汰，内存中为4-3-2；
接着要访问1号页面，内存中没有（1个缺页），按FIFO，2号页面淘汰，内存中为1-4-3；
接着要访问2号页面，内存中没有（1个缺页），按FIFO，3号页面淘汰，内存中为2-1-4；
接着要访问5号页面，内存中没有（1个缺页），按FIFO，4号页面淘汰，内存中为5-2-1；
接着要访问1号页面，内存中有（命中），内存中为5-2-1；
接着要访问2号页面，内存中有（命中），内存中为5-2-1；
接着要访问3号页面，内存中没有（1个缺页），按FIFO，1号页面淘汰，内存中为3-5-2；
接着要访问4号页面，内存中没有（1个缺页），按FIFO，2号页面淘汰，内存中为4-3-5；
接着要访问5号页面，内存中有（命中），内存中为4-3-5；
缺页中断次数=9 （12次访问，只有三次命中）
LRU不同于FIFO的地方是，FIFO是先进先出，LRU是最近最少用，如果1个页面使用了，要调整内存中页面的顺序，如上面的FIFO中：
接着要访问1号页面，内存中有（命中），内存中为5-2-1；
在LRU中，则为
接着要访问1号页面，内存中有（命中），内存中为1-5-2；

⑩ LRU页面置换算法的实现

我会。就是最近未使用的算法吧。例如一个三道程序，等待进入的是1，2，3，4，4，2，5，6，3，4，2，1。先分别把1，2，3导入，然后导入4，置换的是1，因为他离导入时间最远。然后又是4，不需要置换，然后是2，也不需要，因为内存中有，到5的时候，因为3最远，所以置换3，依次类推，还有不懂联系我吧。QQ：243926566