先进先出算法
// 先进先出Dlg.cpp : implementation file
//
#include "stdafx.h"
#include "先进先出.h"
#include "先进先出Dlg.h"
#include
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About
class CAboutDlg : public CDialog
{
public:
CAboutDlg();
// Dialog Data
//{{AFX_DATA(CAboutDlg)
enum { IDD = IDD_ABOUTBOX };
//}}AFX_DATA
// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CAboutDlg)
protected:
virtual void DoDataExchange(CDataExchange* pDX);
//}}AFX_VIRTUAL
// Implementation
protected:
//{{AFX_MSG(CAboutDlg)
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};
CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{ // DDX/DDV support
//{{AFX_DATA_INIT(CAboutDlg)
//}}AFX_DATA_INIT
}
void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CAboutDlg)
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
//{{AFX_MSG_MAP(CAboutDlg)
// No message handlers
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CMyDlg dialog
CMyDlg::CMyDlg(CWnd* pParent /*=NULL*/)
: CDialog(CMyDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CMyDlg)
m_1 = 0;
m_2 = 0;
m_3 = 0;
m_4 = 0;
m_5 = 0;
m_0 = _T("");
m_6 = 0;
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CMyDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CMyDlg)
DDX_Text(pDX, IDC_EDIT1, m_1);
DDX_Text(pDX, IDC_EDIT2, m_2);
DDX_Text(pDX, IDC_EDIT3, m_3);
DDX_Text(pDX, IDC_EDIT4, m_4);
DDX_Text(pDX, IDC_EDIT5, m_5);
DDX_LBString(pDX, IDC_LIST1, m_0);
DDX_Text(pDX, IDC_EDIT6, m_6);
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CMyDlg, CDialog)
//{{AFX_MSG_MAP(CMyDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
ON_BN_CLICKED(IDC_BUTTON5, OnButton5)
ON_WM_TIMER()
ON_MESSAGE(MY_MSGID, DoFIFO)
ON_MESSAGE(MY_MSGID1, repaint)
ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
ON_LBN_SELCHANGE(IDC_LIST1, OnSelchangeList1)
ON_BN_CLICKED(IDC_BUTTON6, OnButton6)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CMyDlg message handlers
BOOL CMyDlg::OnInitDialog()
{
CDialog::OnInitDialog();
// Add "About..." menu item to system menu.
// IDM_ABOUTBOX must be in the system command range.
ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
ASSERT(IDM_ABOUTBOX
CMenu* pSysMenu = GetSystemMenu(FALSE);
if (pSysMenu != NULL)
{
CString strAboutMenu;
strAboutMenu.LoadString(IDS_ABOUTBOX);
if (!strAboutMenu.IsEmpty())
{
pSysMenu->AppendMenu(MF_SEPARATOR);
pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
}
}
// Set the icon for this dialog. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon
// TODO: Add extra initialization here
return TRUE; // return TRUE unless you set the focus to a control
}
void CMyDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
{
CAboutDlg dlgAbout;
dlgAbout.DoModal();
}
else
{
CDialog::OnSysCommand(nID, lParam);
}
}
// If you add a minimize button to your dialog, you will need the code below
// to draw the icon. For MFC applications using the document/view model,
// this is automatically done for you by the framework.
void CMyDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // device context for painting
SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);
// Center icon in client rectangle
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;
// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CDialog::OnPaint();
}
}
// The system calls this to obtain the cursor to display while the user drags
// the minimized window.
HCURSOR CMyDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}
void CMyDlg::OnButton1() //从文档读数据
{
// TODO: Add your control notification handler code here
ifstream infile;
infile.open("fifo.txt");
CString str;
CListBox *pCtrl = (CListBox *)GetDlgItem( IDC_LIST1) ;
infile>>a[0];
for(int i=1;i
{
infile>>a[i];
str.Format("%d",a[i]);
pCtrl->AddString(str);
pCtrl->SetCurSel(pCtrl->GetCount()-1);
UpdateData(false);
}
infile.close();
j=1;
}
void CMyDlg::OnButton5()
{
// TODO: Add your control notification handler code here
::PostMessage(this->m_hWnd, MY_MSGID, NULL, NULL);
}
unsigned int __cdecl ThreadProc(LPVOID lParam)
{
((CMyDlg*)lParam)->FIFO();
return 0;
}
void CMyDlg::DoFIFO()
{
::AfxBeginThread(ThreadProc, this, NULL, NULL, NULL, NULL);
}
void CMyDlg::repaint()
{
UpdateData(false);
}
void CMyDlg::FIFO()
{
static int memory[3] = {0};
int time[3] = {0};
int i = 0, j = 0;
int m = -1, n = -1;
int max = -1,maxtime = 0;
int count = 0;
CString str1;
for(i = 1; i
{ m_1=a[i];
//找第一个空闲的物理块
for(j=0; j
{
if(memory[j] == 0)
{
m = j;
break;
}
}
//找与进程相同的标号
for(j = 0; j
{
if(memory[j] ==a[i])
{
n = j;
}
}
//找time 值最大的
for(j = 0; j
{
if(time[j]>maxtime)
{
maxtime = time[j];
max = j;
}
}
if(n == -1) //不存在相同进程
{
if(m != -1) //存在空闲物理块
{
memory[m] = a[i];
time[m] = 0;
for(j = 0;j
{
time[j]++;
}
m = -1;
}
else //不存在空闲物理块
{
memory[max] = a[i];
time[max] = 0;
for(j = 0;j
{
time[j]++;
}
max = -1;
maxtime = 0;
count++;
}
}
else //存在相同的进程
{
memory[n] = a[i];
for(j = 0;j
{
time[j]++;
}
n = -1;
}
for(j = 0 ;j
{
if(j==0)
{
m_2=memory[j];
}
if(j==1)
{
m_3=memory[j];
}
if(j==2)
{
m_4=memory[j];
}
::PostMessage(this->m_hWnd, MY_MSGID1, NULL, NULL);//发送消息
Sleep(500);
}
// printf("\n");
}
m_5=count;
::PostMessage(this->m_hWnd, MY_MSGID1, NULL, NULL);
}
void CMyDlg::OnTimer(UINT nIDEvent)
{
// TODO: Add your message handler code here and/or call default
CDialog::OnTimer(nIDEvent);
}
void CMyDlg::OnButton2()
{
// TODO: Add your control notification handler code here
m_1=0;
m_2=0;
m_3=0;
m_4=0;
m_5=0;
UpdateData(false);
}
void CMyDlg::OnSelchangeList1()
{
// TODO: Add your control notification handler code here
}
void CMyDlg::OnButton6() //手动
{
// TODO: Add your control notification handler code here int num=0;
int num1=0;
if(j>9)
AfxMessageBox("over");
else if(j
{
if(m_2==0)
{
m_1=a[j];
m_2=m_1;
j++;
}
else if(m_3==0)
{
m_1=a[j];
m_3=m_1;
j++;
}
else if(m_4==0)
{
m_1=a[j];
m_4=m_1;
j++;
}
else if(m_4!=0)
{
if(m_2==a[j]||m_3==a[j]||m_4==a[j]) {
m_1=a[j];
j++;
num1++;
}
else //无相同进程
{
if((j-m_6)%3==1)
{m_1=a[j];
m_2=a[j];j++;
num++;
}
else if((j-m_6)%3==2) {m_1=a[j];
m_3=a[j];j++;
num++;
}
else if((j-m_6)%3==0) {m_1=a[j];
m_4=a[j];j++;
num++;
}
}
}m_6+=num1;
m_5+=num;
}
UpdateData(false);
}
时间片轮转算法 //有相同进程
// 时间片轮转调度算法
#include
#include
#include
#include
using namespace std;
enum STATUS {RUN,READY,W AIT,FINISH};
struct PCBNode
{
int processID; //进程ID
STATUS status; //进程状态
int priorityNum; //优先数
int reqTime; //总的需要运行时间
int remainTime; //剩下需要运行时间
int arriveTime; //进入就绪队列时间
int startTime; //开始运行时间
int finishTime; //结束运行时间
int totalTime; //周转时间
float weightTotalTime; //带权周转时间
};
struct QueueNode
{
int ID; //进程ID
struct QueueNode * next; //队列中下一个进程指针
};
struct LinkQueue
{
QueueNode *head;//队首
};
void Fcfs(LinkQueue& Q, int& totalTimeSum, int& weightTotalTimeSum,PCBNo de * ProcessTable);
bool RR_Run(LinkQueue& Q,QueueNode* q, QueueNode* p, const int Roun d,int& currentTime,PCBNode * ProcessTable);
//分配时间片给q 所指进程,p 为刚退出的进程
void RoundRobin(LinkQueue& Q,const int Round, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable);
//时间片轮转调度, 调用RR_Run(),时间片大小设为Round
void InitialQueue(LinkQueue& Q,PCBNode * ProcessTable,const int processnum); //初始化就绪队列
void Input(PCBNode * ProcessTable, const int processnum);
//从input.txt 文件输入数据
int main()
{
LinkQueue Q;//就绪队列
Q.head = NULL;
const int processnum = 16;//进程数
const int Round = 1; //时间片大小
int totalTimeSum = 0; //周转时间
int WeightTotalTimeSum = 0;//带权周转时间
PCBNode * ProcessTable=new PCBNode[processnum]; //进程表
Input(ProcessTable, processnum);
InitialQueue(Q, ProcessTable, processnum);
RoundRobin(Q, Round, totalTimeSum,WeightTotalTimeSum,ProcessTable); cout
Input(ProcessTable, processnum);
InitialQueue(Q, ProcessTable, processnum);
Fcfs(Q, totalTimeSum,WeightTotalTimeSum,ProcessTable);
cout
cout
delete [] ProcessTable;
return 0;
}
void RoundRobin(LinkQueue& Q,const int Round, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable)
{
totalTimeSum = 0; //总的周转时间
weightTotalTimeSum = 0;//平均周转时间
int currentTime = 0; //当前时间
QueueNode* p;
QueueNode* q;
QueueNode* r;
bool finish = false;//调用RR_Run()后, 该进程是否已经做完退出
p = Q.head;
q = p-> next;
while (q != NULL)//从队首开始依次分配时间片
do
{
cout
cout ID
cout ID ID].remainTime
finish = RR_Run(Q, q, p, Round, currentTime, ProcessTab le);//分配时间片给q 进程
cout
if (!finish)//若是进程在本时间片内做完, 则跳出do…while循环 {
if (q-> next == NULL)
{
r = Q.head-> next;
}
else
{
r = q-> next;
}
}
else //否则计算周转时间和带权周转时间
{
totalTimeSum += ProcessTable[q-> ID].totalTime;
weightTotalTimeSum += ProcessTable[q-> ID].weightTotalTime;
delete q; //从队列中删除q 进程
q = p;
}
}while (!finish && (ProcessTable[r-> ID].arriveTime > currentTime + Round));
//下一个进程很晚才来, 则继续给当前进程分配时间片
p = q;
q = q-> next;
if (q == NULL && Q.head-> next!=NULL)
{
p = Q.head;
q = p-> next;
}
delete Q.head;
Q.head = NULL;
}
bool RR_Run(LinkQueue& Q,QueueNode* q, QueueNode* p, const int Roun d,int& currentTime,PCBNode * ProcessTable)
{
if (ProcessTable[q-> ID].remainTime
{
ProcessTable[q-> ID].finishTime = currentTime + ProcessTable[q-> ID].remainTime;
ProcessTable[q-> ID].totalTime += ProcessTable[q-> ID].remainTime;
ProcessTable[q-> ID].weightTotalTime = ProcessTable[q-> ID].totalTime/ProcessTable[q-> ID].reqTime;
currentTime = ProcessTable[q-> ID].finishTime;
p-> next = q-> next;
cout
cout ID
return true;
}
else//此时间片内做不完
{
ProcessTable[q-> ID].remainTime = ProcessTable[q-> ID].remainTime - Round;
ProcessTable[q-> ID].totalTime += Round;
currentTime += Round;
return false;
}
}
void Fcfs(LinkQueue& Q, int& totalTimeSum, int& weightTotalTimeSum,PCBNo de * ProcessTable)
{
totalTimeSum = 0;
weightTotalTimeSum = 0;//平均周转时间
QueueNode* p;
QueueNode* q;
p = Q.head-> next;
if (p !=NULL )
{
ProcessTable[p-> ID].startTime = ProcessTable[p-> ID].arriveTime;
ProcessTable[p-> ID].finishTime = ProcessTable[p-> ID].arriveTime + ProcessTable[p-> ID].reqTime;
}
for(q=p-> next; q!=NULL; q=q-> next)
{
if (ProcessTable[q-> ID].arriveTime ID].finishTime) {
ProcessTable[q-> ID].startTime = ProcessTable[p-> ID].finishTime; ProcessTable[q-> ID].finishTime = ProcessTable[p-> ID].finishTime + ProcessTable[q-> ID].reqTime;
}
else//下个进程到达时间较晚
{
ProcessTable[q-> ID].startTime = ProcessTable[q-> ID].arriveTime; ProcessTable[q-> ID].finishTime = ProcessTable[q-> ID].arriveTime + ProcessTable[q-> ID].reqTime;
}
p = q;
}
for(q=Q.head-> next; q!=NULL; q=q-> next)
{
ProcessTable[q-> ID].totalTime = ProcessTable[q-> ID].finishTime - ProcessTable[q-> ID].arriveTime;
ProcessTable[q-> ID].weightTotalTime = ProcessTable[q-> ID].totalTime/ProcessTable[q-> ID].reqTime;
totalTimeSum += ProcessTable[q-> ID].totalTime;
weightTotalTimeSum += ProcessTable[q-> ID].weightTotalTime; }
int t = 0;
for(q=Q.head-> next; q!=NULL; q=q-> next)
{
cout
while ( t ID].finishTime )
{
cout ID
}
if (q-> next != NULL)
{
cout ID
cout ID ID].totalTime
cout ID ID].weightTotalTime
}
else
{
cout ID
cout ID ID].totalTime
cout ID ID].weightTotalTime
}
}
cout
p = Q.head;
for(q=p-> next; q!=NULL; q=q-> next)
{
delete p;
p = q;
}
}
void InitialQueue(LinkQueue& Q, PCBNode * ProcessTable,const int processnu m)
{
//初始化
for (int i=0;i
{
ProcessTable[i].processID=i;
ProcessTable[i].reqTime=ProcessTable[i].remainTime;
ProcessTable[i].finishTime=0;
ProcessTable[i].startTime=0;
ProcessTable[i].status=WAIT;
ProcessTable[i].totalTime=0;
ProcessTable[i].weightTotalTime=0;
}
Q.head = new QueueNode;
Q.head-> next = NULL;
QueueNode * p;
QueueNode * q;
for (i=0;i
{
p = new QueueNode;
p-> ID = i;
p-> next = NULL;
if (i == 0)
{
Q.head-> next = p;
}
else
q-> next = p;
q = p;
}
}
void Input(PCBNode * ProcessTable, const int processnum)
{
FILE *fp; //读入线程的相关内容
if((fp=fopen( "input.txt ", "r "))==NULL)
{
cout
exit(0);
}
for(int i=0;i
{
fscanf(fp, "%d %d %d ",&ProcessTable[i].arriveTime,&ProcessTable[i].remainTime,&ProcessTable[i].priorityNum); }
fclose(fp);
}