allocationdoc.cpp

操作系统内存管理模拟

// AllocationDoc.cpp : implementation of the CAllocationDoc class
//

#include "stdafx.h"
#include "Allocation.h"

#include "AllocationDoc.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAllocationDoc

IMPLEMENT_DYNCREATE(CAllocationDoc, CDocument)

BEGIN_MESSAGE_MAP(CAllocationDoc, CDocument)
//{{AFX_MSG_MAP(CAllocationDoc)
// NOTE - the ClassWizard will add and remove mapping macros here.
// DO NOT EDIT what you see in these blocks of generated code!
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAllocationDoc construction/destruction

CAllocationDoc::CAllocationDoc()
{
	// TODO: add one-time construction code here
	for(int i = 0;i<10;i++)
	{
		information[i] = "";
	}
}

CAllocationDoc::~CAllocationDoc()
{
}

BOOL CAllocationDoc::OnNewDocument()//进行初始化工作
{
	if (!CDocument::OnNewDocument())
		return FALSE;
	
	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)
	
	for(int i = 0;i<8;i++)
		for(int j = 0;j<8;j++)
			m_clrGrid[i][j] = RGB(255,255,255);
		
		m_clrCurrentColor = RGB(255,0,0);
		
		for(int k = 0;k<100;k++)
		{
			jobarray[k] = NULL;
		}
		for(k = 0;k<100;k++)
		{
			joblist[k] = 0;
		}
		for(k = 0;k<100;k++)
		{
			jobsize[k] = 0;
		}
		jobcount = 0;
		
		pnode = q = Initialize(640);
		p = NULL;
		
		return TRUE;
}

/////////////////////////////////////////////////////////////////////////////
// CAllocationDoc serialization

void CAllocationDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CAllocationDoc diagnostics

#ifdef _DEBUG
void CAllocationDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CAllocationDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CAllocationDoc commands

COLORREF CAllocationDoc::GetCurrentColor()
{
	return m_clrCurrentColor;
}

COLORREF CAllocationDoc::GetSquare(int i,int j)
{
	ASSERT(i>=0 && i<=7 && j>=0 && j<=7);
	return m_clrGrid[i][j];
}

void CAllocationDoc::Setsquare(int i,int j,COLORREF color)
{
	ASSERT(i>=0 && i<=7 && j>=0 && j<=7);
	m_clrGrid[i][j] = color;
	SetModifiedFlag(TRUE);
}

Space CAllocationDoc::Startnode()
{
	return q;
}

Space CAllocationDoc::Pnode()
{
	return p;
}

Space CAllocationDoc::Node()
{
	return pnode;
}

Space CAllocationDoc::Initialize(int size)//生成第一个大小为内存总大小的节点
{
	Space p = (Space)malloc(sizeof(MYWORD)*size);
	p->nextlink = p;
	p->prelink = p;
	p->size = size;
	p->tag = 0;
	p->uplink = p;
	return p;
}

Space CAllocationDoc::Foot(Space p)//指向某空闲块的底部
{
	Space q = p+p->size-1;
	return q;
}

Space CAllocationDoc::Allocation(Space pnode,int n,int jobnumber)//分配内存
{
	for(Space p=pnode;p&&p->size<n&&p->nextlink!=pnode;p=p->nextlink);
	if(!p || p->size<n)//若遍历过一遍仍未找到，则分配失败
	{
		::AfxMessageBox("分配失败,没有足够的空间可用于分配");
		return NULL;
	}
	else
	{
		Space f = Foot(p);
		Space next = p->nextlink;
		Space pre = p->prelink;
		if(p->size-n<10)//若申请分配的大小与该空闲块大小一样，则整体分配 
		{
			if(next==p)
			{
				next = NULL;
				//pnode = NULL;
			}
			else 
			{
				next->prelink = p->prelink;
				p->prelink->nextlink = next;
				p->tag = 1;
				f->tag = 1;
				pnode = next;
			}
			joblist[jobcount] = jobnumber;
			jobarray[jobcount] = p;
			jobsize[jobcount] = p->size;
			if(jobcount <= 10)
			{
				information[jobcount] = jobnumber + "allocate" + p->size;
			}
			else
			{
			}
			jobcount++;
		}
		else//部分分配
		{
			if(n%10 != 0)
			{
				n = (n/10+1)*10;
			}
			f->tag = 1;
			p->size -= n;
			f->uplink = Foot(p)+1;
			f = Foot(p);
			f->tag = 0;
			f->uplink = p;
			pnode = p->nextlink;
			p = f+1;
			p->tag = 1;
			p->size = n;
			joblist[jobcount] = jobnumber;
			jobarray[jobcount] = p;
			jobsize[jobcount] = p->size;
			jobcount++;
		}
		return p;
	}	
}

void CAllocationDoc::Free(int jobnumber)//释放内存空间
{
	Space p;
	int flag = 0;
	for(int i = 0;i<jobcount;i++)
	{
		if(joblist[i] == jobnumber)
		{
			p = jobarray[i];
			flag = 1;
			break;
		}
	}
	if(flag == 0)
	{
		::AfxMessageBox("未找到该作业号");
		return;
	}
	
	
	for(int k = i+1;k<jobcount;k++)
	{
		jobarray[k-1] = jobarray[k];
		joblist[k-1] = joblist[k];
		jobsize[k-1] = jobsize[k];
	}
	jobcount--;
	
	Space second;
	Space first;
	int signal = 0;
	int sign = 0;
	
	if((p+p->size) >= q+640)
	{
		second = q;
		signal = 1;
	}
	else
	{
		second = p+p->size;
	}
	
	if(p == q)
	{
		first = q+640-1;
		sign = 1;
	}
	else
	{
		first = p-1;
	}
		
	if((p-1)->tag == 1 && (p+p->size)->tag == 1)//两头均已分配
	{
		p->tag = 0;
		Foot(p)->uplink = p;
		Foot(p)->tag = 0;
		if(!pnode)
		{
			pnode = p->prelink = p->nextlink = p;
		}
		else
		{
			Space q = pnode->prelink;
			p->nextlink = pnode;
			p->prelink = q;
			q->nextlink = pnode->prelink = p;
			pnode = p;
		}
		return;
	}
	
	if(first->tag == 0 && second->tag == 1)//前面空闲,后面已分配
	{
		Space tail;
		Space head;
		if(first == q+640-1)
		{
			tail = (first->uplink)->nextlink;
			head = first->uplink;
			head->nextlink = p;
			p->prelink = head;
			p->nextlink = tail;
			tail->prelink = p;
			(first->uplink)->size += p->size;
		}
		else
		{
			(first->uplink)->size += p->size;
		}
		
		
		Space f;
		if(first != q+640-1)
		{
			f = p+p->size-1;
			f->uplink = first->uplink;
			f->tag = 0;
		}
		else
		{
			(p+p->size-1)->uplink = p;
		}
		
		if(second == q)
		{
			(p+p->size-1)->tag = 0;
		}
		else
		{
			p->tag = 0;
		}
		
		if(p == q)
		{
			pnode = p;
		}
		else
		{
			pnode = first->uplink;
		}
		
		return;
	}
		
	if(first->tag == 1 && second->tag == 0)//前面已分配,后面空闲
	{
		Space tail;
		
		if(second != Startnode())
		{
			tail = second->nextlink;
		}
		else
		{
			tail = second;
		}
		
		Space head;
		
		if(second != Startnode())
		{
			head = second->prelink;
		}
		else
		{
			head = second->prelink;
		}
		
		p->tag = 0;
		p->prelink = head;
		head->nextlink = p;
		p->nextlink = tail;
		tail->prelink = p;
		
		if(second != q)
		{
			p->size += second->size;
			Foot(second)->uplink = p;
		}
		else
		{
			(p+p->size-1)->uplink = p;
		}
		
		if(second == q)
		{
			p->tag = 0;
		}
		else
		{
			p->tag = 0;
		}
		
		pnode = p;
		
		return;
	}
	
	if(first->tag == 0 && second->tag == 0)//两头均为空闲
	{
		Space tail;
		if(second != q)
		{
			tail = second->nextlink;
		}
		else
		{
			tail = second;
		}
		
		Space head;
		if(first != q+640-1)
		{
			head = (first->uplink)->prelink;
		}
		else
		{
			head = first->uplink;
		}
		
		if(first == q+640-1)
		{
			head->nextlink = p;
			p->prelink = head;
			p->nextlink = second->nextlink;
			(second->nextlink)->prelink = p;
			p->size += second->size;
			p->tag = 0;
			first->uplink = p;
			first->tag = 0;
			pnode = p;
		}
		else if(second == q)
		{
			(first->uplink)->nextlink = tail;
			tail->prelink = first->uplink;
			(first->uplink)->prelink = head;
			head->nextlink = first->uplink;
			(first->uplink)->size += p->size;
			(p+p->size-1)->uplink = first->uplink;
			(p+p->size-1)->tag = 0;
			pnode = first->uplink;
		}
		else
		{
			(first->uplink)->nextlink = second->nextlink;
			(second->nextlink)->prelink = first->uplink;
			(first->uplink)->size += p->size + second->size;
			(second+second->size-1)->uplink = first->uplink;
			pnode = first->uplink;
		}
		
		return;
	}
}

int CAllocationDoc::getJoblist(int i)
{
	return joblist[i];
}

Space CAllocationDoc::getJobarray(int i)
{
	return jobarray[i];
}

int CAllocationDoc::getJobcount()
{
	return jobcount;
}

int CAllocationDoc::getJobsize(int i)
{
	return jobsize[i];
}