memory.cpp

要求首先采用动态分区方案

// Memory.cpp: implementation of the CMemory class.
//
//////////////////////////////////////////////////////////////////////

#include "Memory.h"
#include<stdio.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CMemory::CMemory()
{
	m_pBlock = new MemBlock(-1,0);//生成一个始址为-1,大小为0的块，仅作头指针
	pMem initBlock = new MemBlock(0,MAX_SIZE);//分配系统的最大内存作为第0个分区
	initBlock->m_nPid = 0;
	m_pBlock->next = initBlock;
	initBlock->prev = m_pBlock;
}

CMemory::~CMemory()
{
	delete m_pBlock;
}

void CMemory::LoadSystem()
{
	pMem block = Split(GetBlock(),SYS_SIZE);
	block->m_nJid = -2;	//OS的作业号
	block->m_bAlloc = true;
}

void CMemory::UnloadSystem()
{
	pMem block = GetBlock();
	block->m_bAlloc = false;
	Compact(block);
}

//将内存块block分割出大小为size的块(同时处理块之间的链接关系)
pMem CMemory::Split(pMem block,int size)
{
	if (block->m_bAlloc)
	{
		printf("Partition is using...\n");
		return NULL;
	}
	pMem temp = block;
	int addr = temp->m_nAddr;
	pMem newBlock = new MemBlock(addr,size);
	newBlock->m_nPid = block->m_nPid;//重置分区号
	block->m_nPid = block->m_nPid + 1;
	newBlock->prev = temp->prev;//重建链接
	temp->prev->next = newBlock;
	newBlock->next = temp;
	temp->prev = newBlock;
	temp->m_nSize -= size;//调整分区
	temp->m_nAddr += size;
	return newBlock;
}

//将内存块block上下文紧缩成一块
pMem CMemory::Compact(pMem block)
{
	if (!block)
	{
		printf("Partition doesn't exist");
		return NULL;
	}
	pMem nextBlock = block->next,prevBlock = block->prev;
	while (true)
	{
		if (nextBlock != NULL)	//如果当前块的下一块存在
		{
			if (!nextBlock->m_bAlloc)	//且下一块未被分配
			{
				block->m_nSize += nextBlock->m_nSize;
				block->next = nextBlock->next;	//重新建立链接
				if (nextBlock->next)
				{
					nextBlock->next->prev = block;
				}
				delete nextBlock;
			}
		}
		if (prevBlock != NULL)	//如果当前块的前一块存在
		{
			if (!prevBlock->m_bAlloc)	//且没有被分配
			{
				if (prevBlock->m_nAddr == -1)	//当前块为第一块可用分区
				{
					break;
				}
				block->m_nSize += prevBlock->m_nSize;
				block->m_nAddr = prevBlock->m_nAddr;//调整地址
				block->prev = prevBlock->prev;//重新建立链接
				prevBlock->prev->next = block;
				delete prevBlock;			
			}
			break;
		}
		break;
	}	
	return block;
}

void CMemory::Print() const
{
	pMem pItem = m_pBlock->next;
	while (pItem)
	{
		pItem->Print();
		pItem = pItem->next;
	}
}

pMem CMemory::GetBlockFromAddr(int addr) const
{
	pMem p1 = m_pBlock,p2 = p1;
	pMem p = NULL;
	while (p1)
	{
		p2 = p1;
		p1 = p1->next;
		if (p1 == NULL)	//搜索至链尾
		{
			break;
		}
		if (p1->m_nAddr == addr)
		{
			p = p1;
			break;
		}
	}
	return p;
}


pMem CMemory::GetBlock() const
{
	return m_pBlock->next;
}
//////////////////////////////////////////////////////////////////////
// CAvail Class
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CAvail::CAvail()
{
	m_pAvail = new Item(-1,0);//产生始址为-1，大小为0的可用块，仅作头指针
// 	pItem initItem = new Item(SYS_ADDR,MAX_SIZE-SYS_SIZE);//初始化为系统段之后的所有分区均可用
// 	m_pAvail->next = initItem;
// 	initItem->prev = m_pAvail;
	//Add(SYS_ADDR,MAX_SIZE-SYS_SIZE);
}

CAvail::~CAvail()
{
	delete m_pAvail;
}


//增加一个分区
void CAvail::Add(int addr,int size)
{
	pItem p1 = m_pAvail,p2=p1;
	pItem p = new Item(addr,size);
	while (p1)
	{
		p2 = p1;
		p1 = p1->next;
		if (p1 == NULL)
		{
			p2->next = p;
			p->prev = p2;
		}
		else
		{
			if (p1->m_nAddr > addr) //在当前块前插入
			{
				p2->next = p;
				p->prev = p2;
				p->next = p1;
				p1->prev = p;
				//插入后，看能否合并相应的分区
				Compact(p);
				break;
			}
		}
	}
}

//移除一个分区
void CAvail::Remove(int addr)
{
	if (addr == -1)
	{
		printf("No such partition...\n");
		return ;
	}
	pItem p1 = m_pAvail,p2 = p1;
	while (p1)
	{
		p2 = p1;
		p1 = p1->next ;
		if (p1 && p1->m_nAddr == addr)
		{
			if (p1->next == NULL)
			{
				p2->next = NULL;
			}
			else
			{
				p1->next->prev = p2;
				p2->next = p1->next;
			}
			delete p1;
			break;
		}
	}
	if(!p1)
	{
		printf("No such partition...\n");
	}
}


void CAvail::Print()
{
	pItem p = m_pAvail->next;
	while (p)
	{
		//printf("ADDR %d SIZE %d\n",p->m_nAddr,p->m_nSize);
		printf("%7d %7d\n",p->m_nAddr,p->m_nSize);
		p = p->next;
	}
}

//////////////////////////////////////////////////////////////////////
// CRequest Class
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CRequest::CRequest()
{
	m_pReq = new ReqItem(-1,0);//建立一个作业号为-1的作业请求,仅作头指针
}

CRequest::~CRequest()
{
	delete m_pReq;
}





//////////////////////////////////////////////////////////////////////
// CFull Class
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CFull::CFull()
{
	m_pFull = new Item(-1,0);
}

CFull::~CFull()
{
	delete m_pFull;
}


void CFull::Add(int addr,int size)
{
	pItem p1 = m_pFull,p2=p1;
	pItem p = new Item(addr,size);
	while (p1)
	{
		p2 = p1;
		p1 = p1->next;
		if (p1 == NULL)
		{
			p2->next = p;
			p->prev = p2;
		}
		else
		{
			if (p1->m_nAddr > addr) //在当前块前插入
			{
				p2->next = p;
				p->prev = p2;
				p->next = p1;
				p1->prev = p;
				break;
			}
		}
	}
}

void CFull::Remove(int addr)
{
	pItem p1 = m_pFull,p2 = p1;
	while (p1)
	{
		p2 = p1;
		p1 = p1->next ;
		if (p1->m_nAddr == addr)
		{
			if (p1->next == NULL)
			{
				p2->next = NULL;
			}
			else
			{
				p1->next->prev = p2;
				p2->next = p1->next;
			}
			delete p1;
			break;
		}
	}
}

void CFull::Print() const
{
	pItem p = m_pFull->next;
	while (p)
	{
		//printf("ADDR %d SIZE %d\n",p->m_nAddr,p->m_nSize);
		printf("%7d %7d\n",p->m_nAddr,p->m_nSize);
		p = p->next;
	}
}


pReqItem CRequest::GetRequst(int jid) const
{
	pReqItem p = m_pReq;
	pReqItem item = NULL;
	while (p)
	{
		p = p->next;
		if (p == NULL)
		{
			printf("No such job...\n");
			break;
		}
		if (p->m_nJid == jid)
		{
			item = p;
			break;
		}
	}
	return item;
}

void CRequest::Append(int id, int size)
{
	pReqItem item = m_pReq,p1=item;
	pReqItem p2 = new ReqItem(id,size);
	while (item)
	{
		p1 = item;
		item = item->next;
	}
	p1->next = p2;
}

void CRequest::Remove(int id)
{
	pReqItem p2 = m_pReq,p1=p2;
	while (p1)
	{
		p1 = p2;
		p2 = p2->next;
		if (p2 && p2->m_nJid == id)
		{
			if (p2->next == NULL) //just a grammar mistake
			{
				p1->next = NULL;
			}
			else
			{
				p1->next = p2->next;
			}
			delete p2;
			break;
		}
		if (!p2)
		{
			printf("No such job...\n");
			break;
		}
	}
}

void CRequest::Print() const
{
	pReqItem p = m_pReq->next;
	while (p)
	{
		p->Print();
		p = p->next;
	}
}



pItem CAvail::GetAvail() const
{
	return m_pAvail;
}

pItem CFull::GetFull() const
{
	return m_pFull;
}

void CAvail::Update(int addr, int size,bool bPlus)
{
	pItem p1 = m_pAvail,p2=p1;
	while (p1)
	{
		p2 = p1;
		p1 = p1->next;
		if (p1 == NULL)
		{
			printf("Failed to update partition....\n");
			break;
		}
		else
		{
			if (p1->m_nAddr == addr) //当前块即为所得
			{
				if (bPlus)			//扩展可用分区
				{
					p1->m_nAddr += size;
					p1->m_nSize -= size;
				}
				else				//削减可用分区
				{
					p1->m_nAddr -= size;
					p1->m_nSize += size;
				}
				break;
			}
		}
	}
}


pItem CAvail::Compact(pItem item)
{
	if (!item)
	{
		printf("No such availabe partition exists...\n");
		return NULL;
	}
	pItem prevItem = item->prev,nextItem = item->next;
	while (true)
	{
		if (nextItem != NULL)	//如果当前块的下一块存在
		{
			if (nextItem->m_nAddr == (item->m_nAddr + item->m_nSize))//且下一块与当前块紧邻
			{
				item->m_nSize += nextItem->m_nSize;
				item->next = nextItem->next;	//重新建立链接
				if (nextItem->next)
				{
					nextItem->next->prev = item;
				}
				delete nextItem;
			}
		}
		if (prevItem != NULL)	//如果当前块的前一块存在
		{
			if (prevItem->m_nAddr ==(item->m_nAddr-prevItem->m_nSize))	//与上一块紧邻
			{
				if (prevItem->m_nAddr == -1)	//当前块为第一块可用分区
				{
					break;
				}
				item->m_nSize += prevItem->m_nSize;
				item->m_nAddr = prevItem->m_nAddr;//调整地址
				item->prev = prevItem->prev;//重新建立链接
				prevItem->prev->next = item;
				delete prevItem;			
			}
			break;
		}
		break;
	}
	return item;
}

pMem CMemory::GetBlockFromPat(int nPar) const
{
	pMem p1 = m_pBlock,p2 = p1;
	pMem p = NULL;
	while (p1)
	{
		p2 = p1;
		p1 = p1->next;
		if (p1 == NULL)	//搜索至链尾
		{
			break;
		}
		if (p1->m_nPid == nPar)
		{
			p = p1;
			break;
		}
	}
	return p;

}