置換演算法

1. 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

2. 最佳置換演算法的過程是什麼（os）

演算法是未來最遠的數據置換出去，由於未來不可預測，所有最佳演算法是理論值，實際不可實現，研究它是為了讓實際其他的演算法和它作比較並判斷其性能這個串最佳是要置換8次，再沒有任何演算法小於8次了7 0 12 0 12 0 32 4 32 4 12 5 12 0 13 0 1

3. 操作系統頁面置換演算法：第二次機會演算法是什麼

第二次機會演算法：

與FIFO、OPT、LRU、NRU等同為操作系統中請求分頁式管理方式的頁面置換演算法。

第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，依然和FIFO一樣，選擇最早置入內存的頁面。但是二次機會法還設置了一個訪問狀態位。所以還要檢查頁面的的訪問位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置為1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。

第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。

4. 什麼是lru置換演算法

LRU是Least
Recently
Used的縮寫，即最近最少使用頁面置換演算法，是為虛擬頁式存儲管理服務的。
LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最近最少使用的那個頁面調出內存。這就是LRU演算法的全部內容。
這是一個相當好的演算法，它是理想演算法很好的近似。

5. lru頁面置換演算法是什麼

用雙向鏈表和哈希表來實現。

LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。

反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，只需要在每次調換時，找到最近最少使用的那個頁面調出內存。這就是LRU演算法的全部內容。

一種LRU近似演算法是最近未使用演算法。

它在存儲分塊表的每一表項中增加一個引用位，操作系統定期地將它們置為0。當某一頁被訪問時，由硬體將該位置1。過一段時間後，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在之前最近一段時間里它未被訪問過。

以上內容參考：網路-頁面置換演算法

6. 頁面置換演算法在計算機系統中的作用是什麼

1. 頁面置換演算法是把內存中不用的進程或線程置換出去。

2. 當程序在運行時，不是把程序所需要的所有數據都調入內存，而是根據演算法把需要的調入內存，那肯定存在把內存中的一些進程和線程調出內存。

3. 那調出去是調出去哪些內容，就需要用到頁面置換演算法，所謂頁面就是把內存塊按照一頁一頁的劃分（操作系統可劃分一頁有多少內存塊）

4. 總之，頁面置換就是把內存中不用的給置換成需要的或即將需要的，以節省內存。

7. Linux用的是什麼頁面置換演算法

有可能是你的交換分區的大小不足。可以將交換分區設置稍大一些試試

8. 頁面置換演算法的實驗

#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~

9. c語言編寫頁面置換演算法

//熬夜弄出來的，記得加分哦
#include<stdio.h>
void Print(int bc[],int blockCount)
{
for(int i=0;i<blockCount;i++)
{
printf("%d ",bc[i]);
}
printf("\n");
}

bool Travel(int bc[],int blockCount,int x)
{
bool is_found=false;
int i;
for(i=0;i<blockCount;i++)
{
if(bc[i]==x)
{
is_found=true;
break;
}
}
return is_found;
}

void FIFO(int pc[],int bc[],int pageCount,int blockCount)
{
printf("0：FIFO置換演算法\n");
int i;
if(pageCount<=blockCount)
{
printf("缺頁次數為0\n");
printf("缺頁率為0\n");
}
else
{
int noPage=0;
int p=0;
for(i=0;i<pageCount;i++)
{

//printf("引用頁：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
if(p==blockCount)
{
p=0;
}
bc[p]=pc[i];
p++;

}
noPage++;
//printf("物理塊情況：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("FIFO缺頁次數為:%d\n",noPage);
printf("FIFO缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);
}
}

int FoundMaxNum(int a[],int n)
{
int k,j;
k=a[0];
j=0;
for (int i=0;i<n;i++)
{
if(a[i]>=k)
{
k=a[i];
j=i;
}
}
return j;
}

void LRU(int pc[],int bc[],int pageCount,int blockCount)
{
printf("1：LRU置換演算法\n");
if(pageCount<=blockCount)
{
printf("缺頁次數為0\n");
printf("缺頁率為0\n");
}
else
{
int noPage=0;
int i,j,m;
int bc1[100];
for(i=0;i<blockCount;i++)
{
bc1[i]=0;
}
for(i=0;i<pageCount;i++)
{
// printf("引用頁：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
for(int p=0;p<=i;p++)
{
bc1[p]++;
}
}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
int k=FoundMaxNum(bc1,blockCount);
bc[k]=pc[i];
bc1[k]=1;

}
noPage++;
//printf("物理快情況：\n");
//Print(bc,blockCount);
}
else if(Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
for(j=0;j<=i;j++)
{
bc1[j]++;
}
for(m=0;m<=i;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];

}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
for(m=0;m<blockCount;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];
}
}
//printf("\n");
}
printf("LRU缺頁次數為:%d\n",noPage);
printf("LRU缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);
}
}

void Optiomal(int pc[],int bc[],int pageCount,int blockCount)
{
printf("2：最佳置換演算法\n");
if(pageCount<=blockCount)
{
printf("缺頁次數為0\n");
printf("缺頁率為0\n");
}
else
{
int noPage=0;
int i,j,k;
for(i=0;i<pageCount;i++)
{
// printf("引用頁：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
int max=0;
int blockIndex;;
for(j=0;j<blockCount;j++)
{
for(k=i;k<pageCount;k++)
{
if(bc[j]==pc[k])
{
break;
}
}
if(k>=max)
{
max=k;
blockIndex=j;
}
}
bc[blockIndex]=pc[i];

}
noPage++;
//printf("物理快情況：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("OPT缺頁次數為:%d\n",noPage);
printf("OPT缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);
}
}

int main()
{
int pageCount,blockCount,i,pc[100];
printf("輸入頁面數\n");
scanf("%d",&pageCount);
printf("輸入頁面走向\n");
for(i=0;i<pageCount;i++)
{
scanf("%d",&pc[i]);
}
blockCount=3;//物理塊數
int bc1[100];
printf("\n");
FIFO(pc,bc1,pageCount,blockCount);
int bc2[100];
printf("\n");
LRU(pc,bc2,pageCount,blockCount);
int bc3[100];
printf("\n");
Optiomal(pc,bc3,pageCount,blockCount);
return 0;
}