pcblist.cpp

进程管理 用链表实现的 有三种算法实现的

#include "stdafx.h"
#include "PCBList.h"
#include <iostream.h>
#include <iomanip.h>
#include "PCB.h"
PCBList::PCBList()
{
	len = 0;
	headPCB = 0;
	tailPCB = 0;
}
PCBList::~PCBList(){}
bool PCBList::IsEmpty()//判断是否为空
{
	bool result = false;
	if(len == 0)
		result = true;
	return result;
}
bool PCBList::IsOnlyOne()//判断是否只有一个进程
{
	bool result = false;
	if(len == 1)
		result = true;
	return result;
}
bool PCBList::InsertHeadPCB(PCB *pcb)//插入第一个进程
{
	pcb->nextPCB = 0;
	pcb->prePCB = 0;
	bool result = false;
	if(IsEmpty() == true)
	{
		result = true;
		headPCB = pcb;
		tailPCB = pcb;
		headPCB->nextPCB = 0;
		tailPCB->prePCB = 0;
	}
	return result;
}
bool PCBList::InsertAfterHead(PCB *pcb)//在第一个进程的后面添加一个进程
{
	pcb->nextPCB = 0;
	pcb->prePCB = 0;
	bool result = false;
	if(IsOnlyOne() == true)
	{
		result = true;
		headPCB->prePCB = 0;
		headPCB->nextPCB = pcb;
		pcb->nextPCB = 0;
		pcb->prePCB = headPCB;
		tailPCB = pcb;
	}
	else if(IsEmpty() == false)
	{
		result = true;
		headPCB->nextPCB->prePCB = pcb;
		pcb->prePCB = headPCB;
		pcb->nextPCB = headPCB->nextPCB;
		headPCB->nextPCB = pcb;
	}
	return result;
}
bool PCBList::InsertAfterTail(PCB *pcb)//在最后一个进程的后面添加一个进程
{
	pcb->nextPCB = 0;
	pcb->prePCB = 0;
	bool result = false;
	if(IsEmpty() == false)
	{
		result = true;
		tailPCB->nextPCB = pcb;
		pcb->prePCB = tailPCB;
		tailPCB = pcb;
		tailPCB->nextPCB = 0;
		headPCB->prePCB = 0;
	}
	return result;
}
bool PCBList::InsertBeforeHead(PCB *pcb)//在第一个进程前插入一个进程
{
	pcb->nextPCB = 0;
	pcb->prePCB = 0;
	bool result = false;
	if(IsEmpty() == false)
	{
		result = true;
		headPCB->prePCB = pcb;
		pcb->nextPCB = headPCB;
		headPCB = pcb;
		headPCB->prePCB = 0;
		tailPCB->nextPCB = 0;
	}
	return result;
}
bool PCBList::InsertBeforeTail(PCB *pcb)//在最后一个进程的前面插入一个进程
{
	pcb->nextPCB = 0;
	pcb->prePCB = 0;
	bool result = false;
	if(IsOnlyOne() == true)
	{
		result = true;
		tailPCB->prePCB = pcb;
		tailPCB->nextPCB = 0;
		pcb->nextPCB = tailPCB;
		pcb->prePCB = 0;
		headPCB = pcb;
	}
	else if(IsEmpty() == false)
	{
		result = true;
		tailPCB->prePCB->nextPCB = pcb;
		pcb->nextPCB = tailPCB;
		pcb->prePCB = tailPCB->prePCB;
		tailPCB->prePCB = pcb;
	}
	return result;
}
//向PCBList中插入一个进程,在tempPCB前或者后插入该进程
//优先级相等的情况下,PCBList按照提交时间排序
bool PCBList::InsertPCB(PCB *tempPCB, PCB *pcb)
{
	pcb->nextPCB = 0;
	pcb->prePCB = 0;
	bool result = false;
	PCB *curPCB = tempPCB;
	while(tempPCB != 0 && tempPCB->priority == pcb->priority)
	{
		if(tempPCB->submitTime > pcb->submitTime)
		{
			if(tempPCB == headPCB)
			{
				result = InsertBeforeHead(pcb);
			}
			else if(tempPCB == tailPCB)
			{
				result = InsertBeforeTail(pcb);
			}
			else
			{
				result = true;
				tempPCB->prePCB->nextPCB = pcb;
				pcb->prePCB = tempPCB->prePCB;
				pcb->nextPCB = tempPCB;
				tempPCB->prePCB = pcb;
			}
			break;
		}
		curPCB = tempPCB;
		tempPCB = tempPCB->nextPCB;
	}
	if(result == false && curPCB != 0)
	{
		if(curPCB == tailPCB)
		{
			result = InsertAfterTail(pcb);
		}
		else
		{
			result = true;
			curPCB->nextPCB->prePCB = pcb;
			pcb->nextPCB = curPCB->nextPCB;
			pcb->prePCB = curPCB;
			curPCB->nextPCB = pcb;
		}
	}
	return result;
}
//向PCBList中插入一个进程
//先按优先级插入PCBList然后按照提交时间插入PCBList,PCBList按照优先级,提交时间排序
bool PCBList::InsertPCB(PCB *pcb)
{
	pcb->nextPCB = 0;
	pcb->prePCB = 0;
	bool result = InsertHeadPCB(pcb);
	if(result == false)
	{
		PCB *tempPCB = headPCB;
		while(tempPCB != 0 && result == false)
		{
			if(pcb->priority < tempPCB->priority)
			{
				if(tempPCB == headPCB)
				{
					result = InsertBeforeHead(pcb);
				}
				else if(tempPCB == tailPCB)
				{
					result = InsertBeforeTail(pcb);
				}
				else
				{
					result = true;
					tempPCB->prePCB->nextPCB = pcb;
					tempPCB->prePCB = pcb;
					pcb->nextPCB = tempPCB;
					pcb->prePCB = pcb->prePCB;
				}
			}
			else if(pcb->priority == tempPCB->priority)
			{
				result = InsertPCB(tempPCB, pcb);
			}
			tempPCB = tempPCB->nextPCB;
		}
	}
	if(result == false)
	{
		result = InsertAfterTail(pcb);
	}
	len++;
	return result;
}
void PCBList::PrintTitle()//打印标题
{
		cout << setiosflags(ios::left)  
		<< "调度顺序(A)"  << "  " << "进程名称(B)"	
		<< "  " << "状态(C)" << "  " << "进程提交时刻(D)"  
		<< "  " << "进程优先级(E)" << "  " << "进程需要运行时间(F)" 
		<< "  " << "进程开始执行时间(G)" << "  " << "进程分配到的时间(H)"  
		<< "  " << "进程实际运行时间(I)" << "  " << "进程剩余运行时间(J)" 
		<< "  " << "进程完成时间(K)"  << "  " << "周转时间(L)"
		<< "  " << "带权周转时间(M)" << endl;
		cout << setiosflags(ios::left)  << setw(4) << "A" << setw(6) << "B"
		<< setw(8) << "C" << setw(6) << "D" << setw(6) << "E"
		<< setw(6) << "F" << setw(6) << "G" << setw(6) << "H"
		<< setw(6) << "I" << setw(6) << "J" << setw(6) << "K"
		<< setw(6) << "L" << setw(6) << "M" << endl;
}
void PCBList::DeletePCB(PCB *pcb)//从一个PCB链(len >= 2)中删除一个PCB
{
	if(pcb == headPCB)
	{
		if(IsOnlyOne() == false)
		{
			headPCB->nextPCB->prePCB = 0;
			headPCB = headPCB->nextPCB;
		}
		else
		{
			headPCB = 0;
			tailPCB = 0;
		}
	}
	else if(pcb == tailPCB)
	{
		tailPCB->prePCB->nextPCB = 0;
		tailPCB = tailPCB->prePCB;
	}
	else
	{
		pcb->prePCB->nextPCB = pcb->nextPCB;
		pcb->nextPCB->prePCB = pcb->prePCB;
	}
	len--;
}
void PCBList::BackPCBList()//返回原始数据
{
	PCB *p = this->headPCB;
	while(p != 0)
	{
		p->remainTime = p->runTime;
		p->state = 0;
		p = p->nextPCB;
	}
}
int PCBList::GetShortSubmitTime()//得到最短的提交时间
{
	int shortSubmitTime = 10000;
	if(IsEmpty() == true)
		return 0;
	PCB *tempPCB = headPCB;
	while(tempPCB != 0)
	{
		if(shortSubmitTime >= tempPCB->submitTime)
			shortSubmitTime = tempPCB->submitTime;
		tempPCB = tempPCB->nextPCB;
	}
	return shortSubmitTime;
}
//得到就绪的工作——提交的时间小于等于当前时间
PCB* PCBList::GetReadyPCB(int &curTime, PCBList *readyPCBList)
{
	if(curTime < this->GetShortSubmitTime() && readyPCBList->IsEmpty() == true)
		curTime = this->GetShortSubmitTime();
	PCB *readyPCB = 0;
	if(IsEmpty() == true)
		return 0;
	PCB *tempPCB = headPCB;
	while(tempPCB != 0)
	{
		if(curTime >= tempPCB->submitTime)
		{
			readyPCB = tempPCB;
			return readyPCB;
		}
		tempPCB = tempPCB->nextPCB;
	}
	return readyPCB;
}
//得到优先级最高的进程并且删除掉该优先级最高的进程
PCB* PCBList::GetMostPriorityPCB()
{
	PCB *mostPriorityPCB = headPCB;
	if(IsEmpty() == true)
		return 0;
	if(len == 1)
	{
		headPCB = 0;
		tailPCB = 0;
		len--;
		return mostPriorityPCB;
	}
	PCB *tempPCB = headPCB;
	while(tempPCB->nextPCB != 0)
	{
		if(mostPriorityPCB->priority > tempPCB->nextPCB->priority)
			mostPriorityPCB = tempPCB->nextPCB;
		tempPCB = tempPCB->nextPCB;
	}
	DeletePCB(mostPriorityPCB);
	return mostPriorityPCB;
}
void PCBList::Print()
{
	PrintTitle();
	PCB *tempPCB = headPCB;
	int i = 0;
	while(tempPCB != 0)
	{
		i++;
		tempPCB->PrintDetail(i);
		tempPCB= tempPCB->nextPCB;
	}
}