循環首次適應演算法

㈠ 循環首次適應演算法實現可變分區的分配和回收，急

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#define getpch(type) (type*)malloc(sizeof(type))
/*/#define NULL 0*/

struct table
{
char name[10];
char state; /* D(分配) or N(空閑)*/
int size; /*分區大小*/
int addr; /*起始地址*/
struct table *next;
struct table *prev;
}*tab=NULL,*p,*current; /*current表示檢索的起始位置*/
typedef struct table TABLE;

UI()
{
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printf(" 循環首次適應演算法 \n");
printf(" \n");
printf(" \n");
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
}

recycle(char n[10])
{
TABLE *pr=NULL;
for(pr=tab;pr!=NULL;pr=pr->next)
{
if(!strcmp(pr->name,n)&&pr->state=='D')
{
if(pr->prev!=NULL&&pr->prev->state=='N') /*回收區的前一分區空閑*/
{
if(pr->next->state=='N') /*回收區的前後分區都空閑*/
{
pr->state='N';
pr->prev->size+=(pr->size+pr->next->size); /*合並分區大小*/
pr->prev->next=pr->next->next; /*刪除回收分區及其後一空閑分區表項*/
if(pr->next->next!=NULL)
pr->next->next->prev=pr->prev;
return 0;
}/*if*/
else /*回收區的前一個分區空閑,合並兩者*/
{
pr->state='N';
pr->prev->size+=pr->size;
pr->next->prev=pr->prev;
pr->prev->next=pr->next;
return 0;
}/*else*/
}/*if*/

/*回收區的後一個分區空閑,合並兩者*/
else if(pr->next!=NULL&&pr->next->state=='N')
{
pr->state='N';
pr->size+=pr->next->size;
if(pr->next->next!=NULL)
{
pr->next->next->prev=pr;
pr->next=pr->next->next;
}
else pr->next=NULL;
return 0;
}/* else if */
}/*if*/
}/*for*/
if(pr==NULL) printf("錯誤!此分區不存在或未分配作業或前後分區都不空閑!\n");
else printf("分區%s回收完畢!\n",pr->name);
return 0;
}/*recycle*/
allocate(int s)
{
TABLE *pt=NULL,*q,*t;
if(tab->next==NULL) current=tab;
t=current->prev;
for(pt=current;pt!=NULL;pt=pt->next)
{
if(pt->size>=s&&pt->state=='N') /*首個合適分區*/
{
pt->state='D';
if(pt->size>s) /*分區大小大於作業大小,分割分區;相等則不分*/
{
q=getpch(TABLE);
printf("請輸入分割出的分區ID:\n");
scanf("%s",q->name);
q->size=pt->size-s; /*分割分區*/
pt->size-=q->size;
q->state='N';
q->addr=pt->addr+pt->size; /*新增分區的起始地址*/
if(pt->next!=NULL)
{
pt->next->prev=q; /*在空閑鏈中插入新的分區*/
q->next=pt->next;
pt->next=q;
q->prev=pt;
current=pt->next; /*設置起始查找位置*/
return 0;
}
pt->next=q;
q->prev=pt;
q->next=NULL;
}
current=pt->next;
return 0;
}/*if*/
}/*for*/
/*從起始位置往後查找不到合適的分區,返回空閑鏈頭*/
for(pt=tab;pt!=current&&pt!=NULL;pt=pt->next)
{
if(pt->size>=s&&pt->state=='N')
{
pt->state='D';
if(pt->size>s)
{
q=getpch(TABLE);
printf("請輸入分割出的分區ID:\n");
scanf("%s",q->name);
q->size=pt->size-s; /*分割分區*/
pt->size-=q->size;
q->state='N';
q->addr=pt->addr+pt->size;
if(pt->next!=NULL)
{
pt->next->prev=q; /*在空閑鏈中插入新的分區*/
q->next=pt->next;
pt->next=q;
q->prev=pt;
current=pt->next;
return 0;
}
pt->next=q;
q->prev=pt;
q->next=NULL;
}
current=pt->next;
return 0;
}/*if*/
}
printf("沒有合適的分區,此次分配失敗!\n");
return 0;
}/*allocate*/
display()
{
TABLE *pt=tab;
if(pt==NULL) return 0;
printf("---------空閑分區情況---------\n");
printf("ID\t狀態\t大小\t起始地址\n");
while(pt!=NULL)
{
printf("%2s\t%3c\t%3d\t%5d\n",pt->name,pt->state,pt->size,pt->addr);
pt=pt->next;
}
return 0;
}/*disptable*/

sort() /*分區按升序排列*/
{
TABLE *first, *second;
if(tab==NULL)
{
p->next=tab;
tab=p;
tab->prev=NULL;
}
else
{
first=tab;
second=first->next;
while(second!=NULL)
{
first=first->next;
second=second->next;
}
first->next=p;
}
}/*sorttable*/

InitTab()
{
int num;
int i,paddr=0;
TABLE *pn; /*指向前一結點*/
pn=NULL;
printf("\t-------Initialize table-------\n\n");
printf("請輸入分區個數:\n");
scanf("%d",&num);
for(i=0;i<num;i++)
{
p=getpch(TABLE);
printf("輸入分區NO.%d的ID:\n",i);
scanf("%s",p->name);
p->state='N';
printf("輸入分區大小:\n");
scanf("%d",&p->size);
p->addr=paddr;
paddr=p->addr+p->size;
p->prev=pn;
pn=p;
p->next=NULL;
sort(); /* 按分區起始地址排序*/
}

}/*InitTab*/

main()
{
int ch=1;
int size;
char name[10],c='y';
UI();
InitTab();
current=tab;
system("cls");
UI();
display();
getch();
while(c!='n'&&c!='N')
{
system("cls");
UI();
printf("選擇你要進行的操作\n1--分配作業\n2--回收分區\n0/其他--退出\n\n");
scanf("%d",&ch);
system("cls");
switch(ch)
{
case 1:
UI();
display();
printf("請輸入作業大小:\n");
scanf("%d",&size);
allocate(size);
break;
case 2:
UI();
display();
printf("請輸入待回收分區的ID:\n");
scanf("%s",name);
recycle(name);
break;
case 0:
default :exit(0);
}
display();
printf("是否繼續?y/n\n");
c=getch();
system("cls");
}

}

㈡ 求用c語言寫出首次適應分配演算法的分配過程~

/********************************
內存管理模擬程序
*******************************/
#include<iostream.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include <time.h>
#include <windows.h>
/*定義宏*/
#define TotalMemSize 1024 /*劃分的物理塊的大小，地址范圍0~1023*/
#define MinSize 2 /*規定的不再分割的剩餘分區的大小*/
#define getpch(type) (type*)malloc(sizeof(type))

/*定義內存塊*/
typedef struct memBlock
{
struct memBlock *next;/*指向下一個塊*/
int stAddr; /*分區塊的初始地址*/
int memSize; /*分區塊的大小*/
int status; /*分區塊的狀態，0：空閑，1：以被分配*/
}MMB;

/*定義全局變數*/
MMB *idleHead=NULL; /*空閑分區鏈表的頭指針*/
MMB *usedHead=NULL; /*分配分區鏈表的頭指針*/
MMB *usedRear=NULL; /*分配分區鏈表的鏈尾指針*/
MMB *np; /*循環首次適應演算法中指向即將被查詢的空閑塊*/

int idleNum=1;/*當前空閑分區的數目*/
int usedNum=0;/*當前已分配分區的數目*/

MMB *memIdle=NULL; /*指向將要插入分配分區鏈表的空閑分區*/
MMB *memUsed=NULL; /*指向將要插入空閑分區鏈表的已分配分區*/

int flag=1;/*標志分配是否成功，1：成功*/

/*函數聲明*/
void textcolor (int color);/*輸出著色*/
void InitMem();/*初始化函數*/
int GetUseSize(float miu,float sigma); /*獲得請求尺寸*/

MMB *SelectUsedMem(int n);/*選擇待釋放的塊*/

void AddToUsed();/*將申請到的空閑分區加到分配分區鏈表中*/
int RequestMemff(int usize); /*請求分配指定大小的內存,首次適應演算法*/
int RequestMemnf(int usize); /*請求分配指定大小的內存,循環首次適應演算法*/

void AddToIdle();/*將被釋放的分配分區加到空閑分區鏈表中(按地址大小）*/
void ReleaseMem(); /*釋放指定的分配內存塊*/

/*主函數*/
void main()
{
int sim_step;
float miu,sigma; /*使隨機生成的請求尺寸符合正態分布的參數*/
int i;
int a;

MMB *p;
/* double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0;
double aveStep=0,aveSize=0,aveRatio=0;
int step=0,usesize=0; */
textcolor(11);
printf("\n\t\t內存管理模擬程序\n\n");
/* InitMem();*/
while(true)
{
double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0;
double aveStep=0,aveSize=0,aveRatio=0;
int step=0,usesize=0;
InitMem();
textcolor(12);
printf("\n\n首次適應演算法： 0");
printf("\n循環首次適應演算法： 1\n");
textcolor(11);
printf("\n請選擇一種演算法：");
scanf("%d",&a);
textcolor(15);
printf("\n輸入一定數量的步數：(sim_step)");
scanf("%d",&sim_step);
printf("\n 輸入使隨機生成的請求尺寸符合正態分布的參數：miu,sigma ");
scanf("%f,%f",&miu,&sigma);
for(i=1;i<=sim_step;i++)
{
textcolor(10);
printf("\n\n#[%d]\n",i);
do{
usesize=GetUseSize(miu,sigma);
while((usesize<0)||(usesize>TotalMemSize))
{
usesize=GetUseSize(miu,sigma);
}
textcolor(13);
printf("\n\n申請的內存尺寸為：%d",usesize);
printf("\n此時可用的空閑分區有 %d 塊情況如下：",idleNum);
p=idleHead;
textcolor(15);
while(p!=NULL)
{
printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize);
p=p->next;
}
TotalSize+=usesize;
if(a==0)
step=RequestMemff(usesize);
else
step=RequestMemnf(usesize);
TotalStep+=step;
n++;
}while(flag==1);
p=usedHead;
while(p!=NULL)
{
TotalUSize+=p->memSize;
printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize);
p=p->next;
}
textcolor(11);
if(TotalUSize!=0)
{
Ratio=TotalUSize/TotalMemSize;
TotalUSize=0;
printf("\n內存利用率NO.%d :%f%c",i,100*Ratio,'%');
}
else
{
Ratio=0;
printf("\n內存利用率NO.%d :%c%c",i,'0','%');
}
TotalRatio+=Ratio;
ReleaseMem();
}
if(n!=0)
{
textcolor(10);
aveStep=TotalStep/n;
aveSize=TotalSize/n;
aveRatio=TotalRatio/sim_step;
printf("\n平均搜索步驟：%f",aveStep);
printf("\n平均請求尺寸：%f",aveSize);
printf("\n平均內存利用率：%f",aveRatio);
}
}
}
// 輸出著色 /////////////////////////////////////////
void textcolor (int color)
{
SetConsoleTextAttribute (GetStdHandle (STD_OUTPUT_HANDLE), color );
}

/******************************
函數名：InitMem()
用途：把內存初始化為一整塊空閑塊
****************************************/
void InitMem()
{
MMB *p;
p=getpch(MMB);
p->memSize=TotalMemSize;
p->stAddr=0;
p->status=0;
p->next=NULL;
idleHead=p;
np=idleHead;
usedHead=NULL;
usedRear=NULL;
idleNum=1;
usedNum=0;
flag=1;
memIdle=NULL;
memUsed=NULL;

}

/******************************
函數名：GetUseSize(float miu,float sigma)
用途：獲得請求尺寸；
參數說明：float miu,float sigma ：正態分布的參數
返回值:申請尺寸的大小；
****************************************************/
int GetUseSize(float miu,float sigma)
{
float r1,r2;
float u,v,w;
float x,y;
do
{
r1=rand()/32767.0;
r2=rand()/32767.0;

u=2*r1-1;
v=2*r2-1;

w=u*u+v*v;
}while(w>1);
x=u*sqrt(((-log(w))/w));
y=v*sqrt(((-log(w))/w));
return miu+sigma*x;
}

/******************************
函數名：*SelectUsedMem(int n)
用途：選擇待釋放的塊(0~n-1)
返回值：指向待釋放的塊的指針；
****************************************************/
MMB *SelectUsedMem(int n)
{
MMB *p;
int i,j;
if(n>0)
{
i = rand()%n ;
textcolor(5);
printf("\n\n當前已分配分區總數為：%d",n);
printf("\n待釋放塊的序號為：%d\n",i );
p=usedHead;
if(p!=NULL)
{
for(j=i;j>0;j--)
p=p->next;
return(p);
}
else
return(NULL);
}
else
{
printf("\n當前沒有可釋放的資源！\n");
}
}
/******************************
函數名：AddToUsed()
用途：將申請到的空閑分區加到分配分區鏈表中
***************************************************************/
void AddToUsed()
{
MMB *p;
memIdle->status=1;
if(usedHead==NULL)
{
usedHead=memIdle;
usedRear=usedHead;

}
else
{
usedRear->next=memIdle;
usedRear=memIdle;
}
usedNum++;
printf("\n當前分配分區共有%d塊！",usedNum);
p=usedHead;
while(p!=NULL)
{
printf("\n始址:%d \t 尺寸：%d",p->stAddr,p->memSize);
p=p->next;
}
}
/******************************
函數名：RequestMemff(int usize)
參數說明：usize：請求尺寸的大小；
用途：請求分配指定大小的內存,首次適應演算法
返回值：搜索步驟
***************************************************************/
int RequestMemff(int usize)
{
MMB *p1,*p2,*s;
int step;
int suc=0;
int size1,size2;

if(idleHead==NULL)
{
flag=0;
textcolor(12);
printf("\n分配失敗！");
return 0;
}
else
{
if((idleHead->memSize)>usize)
{
size1=(idleHead->memSize)-usize;
if(size1<=MinSize)
{
memIdle=idleHead;

idleHead=idleHead->next;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=idleHead->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;

idleHead->memSize=idleHead->memSize-usize;
idleHead->stAddr=idleHead->stAddr+usize;
}
step=1;
flag=1;
textcolor(12);
printf("\n分配成功！");
AddToUsed();

}
else
{
p1=idleHead;
step=1;
p2=p1->next;
while(p2!=NULL)
{
if((p2->memSize)>usize)
{
size2=(p2->memSize)-usize;
if(size2<=MinSize)
{
p1->next=p2->next;
memIdle=p2;
memIdle->next=NULL;
idleNum--;

}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=p2->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
p2->memSize=p2->memSize-usize;
p2->stAddr=p2->stAddr+usize;

}
flag=1;
suc=1;
textcolor(12);
printf("\n分配成功！");
AddToUsed();
p2=NULL;
}
else
{
p1=p1->next;
p2=p2->next;
step++;
}
}
if(suc==0)
{
flag=0;
textcolor(12);
printf("\n分配失敗！");
}
}
}
return step;
}

/******************************
函數名：AddToIdle()
用途：將被釋放的分配分區加到空閑分區鏈表中(按地址遞增順序排列）
***************************************************************/
void AddToIdle()
{
MMB *p1,*p2;
int insert=0;
if((idleHead==NULL))
{
idleHead=memUsed;
idleNum++;
np=idleHead;
}
else
{
int Add=(memUsed->stAddr)+(memUsed->memSize);
if((memUsed->stAddr<idleHead->stAddr)&&(Add!=idleHead->stAddr))
{
memUsed->next=idleHead;
idleHead=memUsed;
idleNum++;
}
else
{

if((memUsed->stAddr<idleHead->stAddr)&&(Add==idleHead->stAddr))
{
idleHead->stAddr=memUsed->stAddr;
idleHead->memSize+=memUsed->memSize;

}
else
{
p1=idleHead;
p2=p1->next;
while(p2!=NULL)
{
if(memUsed->stAddr>p2->stAddr)
{
p1=p1->next;
p2=p2->next;
}
else
{
int Add1=p1->stAddr+p1->memSize;
int Add2=p2->stAddr-memUsed->memSize;
if((Add1==memUsed->stAddr)&&(memUsed->stAddr!=Add2))
{
p1->memSize=p1->memSize+memUsed->memSize;
}
if((Add1!=memUsed->stAddr)&&(memUsed->stAddr==Add2))
{
p2->memSize=p2->memSize+memUsed->memSize;
p2->stAddr=memUsed->stAddr;
}
if((Add1!=memUsed->stAddr)&&(memUsed->stAddr!=Add2))
{
memUsed->next=p2;
p1->next=memUsed;
if(np->stAddr==p2->stAddr)
np=p1->next;
idleNum++;
}
if((Add1==memUsed->stAddr)&&(memUsed->stAddr==Add2))
{
p1->memSize=p1->memSize+memUsed->memSize+p2->memSize;
p1->next=p2->next;
if((np->stAddr)==(p2->stAddr))
np=p1;
idleNum--;
}
p2=NULL;
insert=1;
}
}
if(insert==0)
{
p1->next=memUsed;
idleNum++;
}
}
}
}
}

/******************************
函數名：ReleaseMem()
用途：釋放指定的分配內存塊
***************************************************************/
void ReleaseMem()
{
MMB *q1,*q2;
MMB *s;
if(usedNum==0)
{
printf("\n當前沒有分配分區!");
return;
}
else
{
s=SelectUsedMem(usedNum);
if(s!=NULL)
{

if(s->stAddr==usedHead->stAddr)
{
memUsed=usedHead;
usedHead=usedHead->next;
memUsed->next=NULL;
AddToIdle();
usedNum--;
}
else
{
q1=usedHead;
q2=q1->next;
while(q2!=NULL)
{
if(q2->stAddr!=s->stAddr)
{
q1=q1->next;
q2=q2->next;
}
else
{
q1->next=q2->next;
memUsed=q2;
memUsed->next=NULL;
if(q1->next==NULL)
usedRear=q1;
AddToIdle();
usedNum--;
q2=NULL;
}
}
}
}
}
}

/******************************
函數名：RequestMemnf(int usize)
參數說明：usize：請求尺寸的大小；
用途：請求分配指定大小的內存,循環首次適應演算法
返回值：搜索步驟
***************************************************************/
int RequestMemnf(int usize)
{
MMB *p2,*p,*s;
int step;
int iNum=0;
int suc=0;
int size1,size2,size3;

if(idleHead==NULL)
{
flag=0;
printf("\n分配失敗！");
return 0;
}
else
{
iNum=idleNum;
while(iNum>0)
{
iNum--;
if((np->memSize)>usize)
{
/*指針指向的空閑塊滿足條件,且正好為頭指針*/
if(np->stAddr==idleHead->stAddr)
{
size1=(idleHead->memSize)-usize;
if(size1<=MinSize)
{
memIdle=idleHead;
idleHead=idleHead->next;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=idleHead->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
idleHead->memSize=idleHead->memSize-usize;
idleHead->stAddr=idleHead->stAddr+usize;
}
if((idleHead==NULL)||(idleHead->next==NULL))
np=idleHead;
else
np=idleHead->next;

}
else/*指針指向的空閑塊滿足條件,不為頭指針*/
{
size2=(np->memSize)-usize;
if(size2<=MinSize) /*從空閑鏈表中刪除*/
{
p=idleHead;
while(p->next->stAddr!=np->stAddr)
p=p->next;
p->next=np->next;
memIdle=np;
memIdle->next=NULL;
np=p;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=np->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;

np->memSize=np->memSize-usize;
np->stAddr=np->stAddr+usize;
}
if(np->next==NULL)
np=idleHead;
else
np=np->next;
}
step=1;
flag=1;
suc=1;
textcolor(12);
printf("\n分配成功！");
AddToUsed();
iNum=0;
}
else /*當前指針指向的空閑區不滿足條件*/
{
step=1;
p2=np->next;
if(p2==NULL)
{
np=idleHead;
iNum--;
}
else
{
if((p2->memSize)>usize)
{
size3=(p2->memSize)-usize;
if(size3<=MinSize)
{
np->next=p2->next;
memIdle=p2;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=p2->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
p2->memSize=p2->memSize-usize;
p2->stAddr=p2->stAddr+usize;
}
flag=1;
suc=1;
printf("\n分配成功！");
AddToUsed();
if(p2->next==NULL)
np=idleHead;
else
np=p2->next;
p2=NULL;
iNum=0;
}
else
{
np=np->next;
p2=p2->next;
iNum--;
step++;
}
}
}
// iNum--;
}
if(suc==0)
{
flag=0;
textcolor(12);
printf("\n分配失敗！");
}
}
return step;
}

㈢ 操作系統的主要演算法都有哪些

一、進程(作業)調度演算法
l 先來先服務調度演算法（FCFS）：每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執行。該進程一旦佔有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。特點：利於長進程，而不利於短進程。

l 短進程（作業）優先調度演算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之佔有處理器並執行，直到該進程完成或因發生事件而阻塞，然後退出處理器，再重新調度。

l 時間片輪轉調度演算法 ：系統將所有的就緒進程按進入就緒隊列的先後次序排列。每次調度時把CPU分配給隊首進程，讓其執行一個時間片，當時間片用完，由計時器發出時鍾中斷，調度程序則暫停該進程的執行，使其退出處理器，並將它送到就緒隊列的末尾，等待下一輪調度執行。

l 優先數調度演算法 ：它是從就緒隊列中選擇一個優先權最高的進程，讓其獲得處理器並執行。

l 響應比高者優先調度演算法：它是從就緒隊列中選擇一個響應比最高的進程，讓其獲得處理器執行，直到該進程完成或因等待事件而退出處理器為止。特點：既照顧了短進程，又考慮了進程到達的先後次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的演算法，但每次進行調度時，都需要對各個進程計算響應比。所以系統開銷很大，比較復雜。

l 多級隊列調度演算法

基本概念：

作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)

作業平均周轉時間(T)＝周轉時間/作業個數

作業帶權周轉時間（Wi）＝周轉時間/運行時間

響應比＝（等待時間＋運行時間）/運行時間

二、存儲器連續分配方式中分區分配演算法
n 首次適應分配演算法（FF）：對空閑分區表記錄的要求是按地址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查找空閑分區表，找到第一個能滿足作業長度要求的空閑區，分割這個空閑區，一部分分配給作業，另一部分仍為空閑區。

n 循環首次適應演算法：每次分配均從上次分配的位置之後開始查找。

n 最佳適應分配演算法(BF)：是按作業要求從所有的空閑分區中挑選一個能滿足作業要求的最小空閑區，這樣可保證不去分割一個更大的區域，使裝入大作業時比較容易得到滿足。為實現這種演算法，把空閑區按長度遞增次序登記在空閑區表中，分配時，順序查找。

三、頁面置換演算法
l 最佳置換演算法（OPT) ：選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。

l 先進先出置換演算法（FIFO）：選擇最先進入內存的頁面予以淘汰。

l 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。

l 最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。

四、磁碟調度
n 先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置

n 最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題

n 掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。

n 循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。

㈣ 求助：簡述可變分區存儲管理系統中採用循環首次適應法的分配演算法的思想

首次適應法:
即第一次適應。比如有空閑區按順序如下：
10KB, 20KB, 5KB, 40KB.
如果進程需要15KB的空間，那麼會從第一塊開始匹配，符合空間大小的只有20KB, 40KB，但是由於是首次適應，20KB在40KB前面，故選擇20KB

㈤ 首次適應演算法是什麼

分區分配演算法(Partitioning Placement Algorithm)
最佳適應演算法（Best Fit）：
它從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區，這種方法能使碎片盡量小。為適應此演算法，空閑分區表（空閑區鏈）中的空閑分區要按大小從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區分配。該演算法保留大的空閑區，但造成許多小的空閑區。
首次適應演算法（First Fit）：
從空閑分區表的第一個表目起查找該表，把最先能夠滿足要求的空閑區分配給作業，這種方法目的在於減少查找時間。為適應這種演算法，空閑分區表（空閑區鏈）中的空閑分區要按地址由低到高進行排序。該演算法優先使用低址部分空閑區，在低址空間造成許多小的空閑區，在高地址空間保留大的空閑區。
循環首次適應演算法(Next Fit)：
該演算法是首次適應演算法的變種。在分配內存空間時，不再每次從表頭（鏈首）開始查找，而是從上次找到空閑區的下一個空閑開始查找，直到找到第一個能滿足要求的的空閑區為止，並從中劃出一塊與請求大小相等的內存空間分配給作業。該演算法能使內存中的空閑區分布得較均勻。

㈥ 採用c語言實現首次適應演算法完成主存空間的分配和回收 急

有沒有具體的要求，比方說數據結構方面，我這有一個，你可以參考參考
#include"stdio.h"
#include"stdlib.h"
#define
n
10
/*假定系統允許的最大作業為n，假定模擬實驗中n值為10*/
#define
m
10
/*假定系統允許的空閑區表最大為m，假定模擬實驗中m值為10*/
#define
minisize
100
struct{
float
address;
/*已分分區起始地址*/
float
length;
/*已分分區長度，單位為位元組*/
int
flag;
/*已分配區表登記欄標志，用"0"表示空欄目*/
}used_table[n];
/*已分配區表*/
struct{
float
address;
/*空閑區起始地址*/
float
length;
/*空閑區長度，單位為位元組*/
int
flag;
/*空閑區表登記欄標志，用"0"表示空欄目，用"1"表示未分配*/
}free_table[m];
/*空閑區表*/
void
main(
)
{
int
i,a;
void
allocate(char
str,float
leg);//分配主存空間函數
void
reclaim(char
str);//回收主存函數
float
xk;
char
J;/*空閑分區表初始化：*/
free_table[0].address=10240;
free_table[0].length=102400;
free_table[0].flag=1;
for(i=1;i<m;i++)
free_table[i].flag=0;/*已分配表初始化：*/
for(i=0;i<n;i++)
used_table[i].flag=0;
while(1)
{
printf("\n選擇功能項（0-退出,1-分配主存,2-回收主存,3-顯示主存）\n");
printf("選擇功項(0~3)
:");
scanf("%d",&a);
switch(a)
{
case
0:
exit(0);
/*a=0程序結束*/
case
1:
/*a=1分配主存空間*/printf("輸入作業名J和作業所需長度xk:
");
scanf("%*c%c%f",&J,&xk);
allocate(J,xk);/*分配主存空間*/
break;
case
2:
/*a=2回收主存空間*/printf("輸入要回收分區的作業名");
scanf("%*c%c",&J);reclaim(J);/*回收主存空間*/
break;
case
3:
/*a=3顯示主存情況*//*輸出空閑區表和已分配表的內容*/
printf("輸出空閑區表：\n起始地址
分區長度
標志\n");
for(i=0;i<m;i++)
printf("%6.0f%9.0f%6d\n",free_table[i].address,free_table[i].length,
free_table[i].flag);
printf("
按任意鍵,輸出已分配區表\n");
getchar();
printf("
輸出已分配區表：\n起始地址
分區長度
標志\n");
for(i=0;i<n;i++)
if(used_table[i].flag!=0)
printf("%6.0f%9.0f%6c\n",used_table[i].address,used_table[i].length,
used_table[i].flag);
else
printf("%6.0f%9.0f%6d\n",used_table[i].address,used_table[i].length,
used_table[i].flag);
break;
default:printf("沒有該選項\n");
}/*case*/
}/*while*/
}/*主函數結束*/
int
uflag;//分配表標志
int
fflag;//空閑表標志
float
uend_address;
float
fend_address;
void
allocate(char
str,float
leg)
{
uflag=0;fflag=0;
int
k,i;float
ressize;
for(i=0;i<m;i++)
{
if(free_table[i].flag==1
&&
free_table[i].length>=leg)
{
fflag=1;break;
}
}
if(fflag==0)
printf("沒有滿足條件的空閑區\n");
else
{
ressize=free_table[i].length-leg;
for(k=0;k<n;k++)
{
if(used_table[k].flag==0)
{
if(ressize<minisize)//剩餘塊過小
{
used_table[k].length=free_table[i].length;
used_table[k].address=free_table[i].address;
used_table[k].flag=str;
free_table[i].length=0;
free_table[i].flag=0;
break;
}
else
{
used_table[k].address=free_table[i].address+ressize;
used_table[k].flag=str;
used_table[k].length=leg;
free_table[i].length=ressize;
break;
}
}
}//for結束
}
}
void
reclaim(char
str)
{
uflag=0;fflag=0;
int
k,i;
for(k=0;k<n;k++)
{
if(used_table[k].flag==str)
{
uflag=1;break;
}
}
if(uflag==0)
printf("\n找不到該作業!\n");
else
{
for(i=0;i<m;i++)
{
uend_address=used_table[k].address+used_table[k].length;
fend_address=free_table[i].address+free_table[i].length;
if(used_table[k].address==fend_address)//上鄰
{
fflag=1;
free_table[i].length=free_table[i].length+used_table[k].length;
free_table[i].flag=1;
used_table[k].flag=0;
used_table[k].length=0;
used_table[k].address=0;
printf("\n已回收!\n");
break;
}
else
{
if(free_table[i].address==uend_address)//下鄰
{
fflag=1;
free_table[i].address=used_table[k].address;
free_table[i].length=free_table[i].length+used_table[k].length;
free_table[i].flag=1;
used_table[k].flag=0;
used_table[k].length=0;
used_table[k].address=0;
printf("\n已回收!\n");
break;
}
}
}//for結束
if(fflag==0)
{
i=0;
for(i=0;i<m;i++)
{
if(free_table[i].flag==0)
{
free_table[i].address=used_table[k].address;
free_table[i].length=used_table[k].length;
free_table[i].flag=1;
used_table[k].length=0;
used_table[k].flag=0;
used_table[k].address=0;
break;
}
}
printf("\n已回收!\n");
}
}
}

㈦ 在動態分區分配方式中，可利用哪些分區分

連續分配：首次適應演算法（較快，簡單，碎片多），最大適應分配演算法（以期不留下小碎片），最佳適應分配演算法（慢，復雜，碎片少）。都需要碎片整理。離散分配：分段管理（邏輯性好），分頁管理，段頁式管理.動態分區分配演算法：1.首次適應演算法（FF/firstfit）2.循環首次適應演算法（nextfit）3.最佳適應演算法（bestfit）從最小的分區開始分配4.最壞適應演算法（worstfit）從最大的分區開始分配5.快速適應演算法/分類搜索法(quickfit)將空閑分區根據其容量的大小進行分類

㈧ 首次適應演算法的介紹

首次適應演算法從空閑分區表的第一個表目起查找該表，把最先能夠滿足要求的空閑區分配給作業，這種方法目的在於減少查找時間。為適應這種演算法，空閑分區表(空閑區鏈)中的空閑分區要按地址由低到高進行排序。該演算法優先使用低址部分空閑區，在低址空間造成許多小的空閑區，在高地址空間保留大的空閑區。