// ManegmentOfMemory.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
#include "stdlib.h"
#include "time.h"
#include "ios.h"
#include "iomanip.h"
#define FINISH 0
#define RUN 1
#define WAITE 2
//#define NULL 0

typedef struct memory//內存塊
{
int m_begin;
int m_size;
memory *next;
}memory;

typedef struct mLNode
{
//int m_num;
int m_total;
memory *next;
}mLNode;

typedef struct pcb
{
int p_size;
int status;
int pbegin;
//pcb *next;
}pcb;

/*typedef struct pLNode{
int p_num;
pcb *next;
}pLNode;*/

void DisplaymLNode();
void Displayg_pcb();
bool m_FirstFit();//用最先適用算法來進行內存的分配
bool InitialMemory();
bool InitialProcessing();
bool Getg_pro();//隨機得到進程的數目
bool m_Recycle(pcb *p);//用于對釋放內存的回收
int g_pro;//總的進程數
int g_mem;//總的內存數
unsigned long next = 1;//來產生隨機數
mLNode g_mLNode;//未使用的內存塊鏈表
pcb *g_pcb;//進程鏈表
//pLNode g_pLNode;


void srand(unsigned int seed)
{
next = seed;
}

int rand()
{
next = next * 1103515245 + 12345;
return (unsigned int)(next / 65536)%32768;
}

//初始各個進程，是由隨機函數來進行實現的;并且每個進程的大小限制在10~400之間
bool InitialProcessing()
{

g_pcb = new pcb[g_pro];
int msize;
for(int i=0;i<g_pro;i++)
{
//隨機產生進程所需空間
//srand( g_pcb[i-1].p_size );
while((msize = rand()%700) < 400 || (msize = rand()%700) > 600);
g_pcb[i].p_size = msize;
g_pcb[i].status = WAITE;

}
return true;
}

//初始化未分配出去的內存塊的鏈表
bool InitialMemory()
{
srand( (unsigned)time( NULL ) );
int msize;
while((msize = rand()%2000) < 900 );
g_mem = msize;
g_mLNode.m_total = msize; //開始時內存還沒有分配故總的數目為1且空閑為所剛產生的內存的大小
g_mLNode.next = (memory *)malloc(msize*sizeof(memory)+1);
g_mLNode.next->next = NULL; //剛建立時next應該指向為空
g_mLNode.next->m_begin = 1 ;
g_mLNode.next->m_size = msize;

return true;

}

//隨機產生進程的個數并且控制進程的數目在5~12之間
bool Getg_pro()
{

srand( (unsigned)time( NULL ) );
while((g_pro = rand() % 100) < 5 || (g_pro > 8));
cout <<"本次程序所模擬的進程的個數： "<< g_pro-1 <<endl;
//cout <<"請輸入任意大的一個數來產生隨機數："
cout << "提示：在表示進程狀態時 0---->完 成" <<endl
<< " 1---->正在執行" <<endl
<< " 2---->就 緒" <<endl;
return true;

}


//用最先適用算法來實現內存的分配
bool m_FirstFit()
{

memory *m,*prem;//記錄當前和前一次走過的空閑塊
m = g_mLNode.next ;
prem = m;
for (int i=1 ;i<=g_pro ;i++){
if (g_pcb[i].status == RUN || g_pcb[i].status == FINISH) continue;
while (m!=NULL){
if (m->m_size >= g_pcb[i].p_size ){//滿足進程對內存的需求
if (m->m_size == g_pcb[i].p_size){
g_mLNode.m_total -= g_pcb[i].p_size ;
g_pcb[i].pbegin = m->m_begin ;
prem->next = m->next ;
g_pcb[i].status = RUN;
}
else{
g_mLNode.m_total = g_mLNode.m_total - g_pcb[i].p_size ;
g_pcb[i].pbegin = m->m_begin ;
m->m_begin = m->m_begin + g_pcb[i].p_size;
m->m_size -= g_pcb[i].p_size ;
g_pcb[i].status = RUN;
}
break;//分配成功就跳出來
}
else{
prem = m;
m = m->next ;
}

}
}
return true;
}//m_FirstFit 



//來管理內存的回收以及對上下空閑塊的合并
bool m_Recycle(pcb *p)
{

memory *m,*prem,*mpcb;
mpcb = (memory *)malloc(sizeof(memory)); 
mpcb->next = NULL;
m = g_mLNode.next ;//指向第一個未分配的內存塊
prem = m;
if (p->status == FINISH || p->status == WAITE) return false;
mpcb->m_begin = p->pbegin ;
mpcb->m_size = p->p_size ;
int size = p->p_size ;
int end = mpcb->m_begin + size - 1;//記錄該進程塊的始未地址和大小
p->p_size = 0;
p->pbegin = 0;
p->status = FINISH;//釋放進程所占有的資源
g_mLNode.m_total += size;//更新未分配的內存總數
//回收內存，將釋放內存與其相鄰的空閑塊相合并得到一個新的空閑內存塊，準備將其放入到鏈表中
while ( m!=NULL ){
if (mpcb->m_begin == m->m_begin + m->m_size ){//空閑在左邊
m->m_size = m->m_size +mpcb->m_size ;
mpcb = m;
//prem = m;
//m = m->next ;
break;
}
else if (end == m->m_begin - 1){//空閑塊在右邊
mpcb->m_size += m->m_size ;
//prem = m;
//m = m->next ;
break;
}
else { 
prem = m;
m = m->next ;
}
}//while
m = g_mLNode.next ; prem = m;
while ( m!=NULL && (mpcb->m_begin > m->m_begin) ){
prem = m;
m = m->next ;
}
if (prem == m && m == g_mLNode.next ) 
{
if ( m->m_begin == mpcb->m_begin) g_mLNode.next = mpcb;
else{
g_mLNode.next = mpcb;
mpcb->next = m;
}
}
else {
mpcb->next = m ;
prem->next = mpcb;
}
return true;
}

//顯示各個進程的現況


void Displayg_pcb()
{
cout <<"\n\n" <<endl;

cout << "此進各個進程的狀態為：" << endl;
cout << "進程號\t所需內存\t進程狀態" << endl;
for(int i=1 ;i<g_pro ;i++){
cout << i << "\t" << g_pcb[i].p_size << "\t\t" << g_pcb[i].status << endl;
}
}


void DisplaymLNode()
{

memory *m = g_mLNode.next;
cout <<"內存大小："<< g_mem << endl;
cout <<"剩余內存："<< g_mLNode.m_total <<endl; 
int i=1;
while(m!=NULL)
{
cout <<"第"<<i<<"塊空閑塊 ";
cout <<"起始地址:"<< m->m_begin <<" 大小:"<< m->m_size << endl;//" 末尾地址:"<< m->m_begin + m->m_size -1 <<endl;
m = m->next ; 
i++;
}
}

void main()
{
Getg_pro();//獲取作業數
InitialProcessing();
InitialMemory();
Displayg_pcb();
DisplaymLNode();
m_FirstFit();
Displayg_pcb();
DisplaymLNode();
for (int j=1 ;j<=g_pro ;j++)
{
m_Recycle(&g_pcb[j]);
m_FirstFit();
Displayg_pcb();
DisplaymLNode();
}
}