时间片轮转算法+进程调度模拟程序

一设计要求 ：
    编写一程序，可以创建若干个虚拟进程，并对若干个虚拟进程进行调度，调度策略为时间片轮转。
要求：进程的个数，进程的内容（即进程的功能序列）来源于一个进程序列描述文件，另外调度运行结果输出到一个运行日志文件。
二设计目的：熟悉进程调度、设计内容： 
1.设计PCB适用于轮转法；
2.建立进程队列；
三虚拟程序的描述：
虚拟指令的格式：操作命令 操作时间
● C ： 表示在CPU上计算
● I ： 表示输入
● O ： 表示输出
● W ： 表示等待
● H ： 表示进程结束

操作时间代表该操作命令要执行多长时间。这里假设I/O设备的数量没有限制，I和O设备都只有一类。
I，O，W三条指令实际上是不占有CPU的，执行这三条指令就应该将进程放入对应的等待队列（INPUT等待队列，OUTPUT等待队列 ，WAIT等待队列）。
例如有一虚拟程序p1.prc描述如下：
C 30
O 12
C  9
I 14
H  0
................







程序部分代码如下：
enum InstructionSet {INPUT,OUTPUT,WAIT,HALT,CALC};
//指令类
class CInstruction  
{
friend class COsTestDlg;
friend class PCB;
public:
CInstruction()
{
}

~CInstruction()
{
}

CInstruction(InstructionSet iid,int rt)
{
m_nInstructionID=iid;
m_nRunTime=rt;
}



private:
CInstruction* m_pNextInstruction;//用于链接一个进程的所有指令成为链表（指令序列）
int m_nRunTime;//本指令需要运行的时间长度（定时器时间间隔的个数）
InstructionSet m_nInstructionID;//指令类型标识

};




//进程控制块类
class PCB  
{
friend class COsTestDlg;
public:
PCB()
{
m_nPID=0;
m_csProcessName="";
m_nRemainedTime=0;//
m_pRuningInstruction=NULL;

m_pInstructionList=NULL;
m_pNextPCB=NULL;

}

//构造或创建一个进程
PCB(int pid,CString pname)
{
m_nPID=pid;
m_csProcessName=pname;
m_nRemainedTime=0;//
m_pRuningInstruction=NULL;

m_pInstructionList=NULL;
m_pNextPCB=NULL;

}

~PCB()
{
CInstruction* pTemp;
while(m_pInstructionList)
{
m_pInstructionList=m_pInstructionList->m_pNextInstruction;
pTemp=m_pInstructionList;
delete pTemp;

}
}

//本进程添加一条指令
void AppendInstruction(CInstruction* pInstruction)
{
CInstruction* pTempInstruction;
if(m_pInstructionList==NULL)
{
//empty
m_pInstructionList=pInstruction;
}
else
{
//more than one node
pTempInstruction = m_pInstructionList;
while(pTempInstruction->m_pNextInstruction!=NULL)
pTempInstruction=pTempInstruction->m_pNextInstruction;
pTempInstruction->m_pNextInstruction=pInstruction;
}

}







private:
PCB* m_pNextPCB; //进程队列的指针
int m_nPID; //进程标识符 
CString m_csProcessName; //进程名字
int m_nRemainedTime; //当前运行指令运行还需要的时间
CInstruction* m_pRuningInstruction; //指向正在运行或将要运行的指令
CInstruction* m_pInstructionList; //指向本进程的指令序列（线性表）的第一条指令
};





PCB* m_pReadyPCBs;//就绪队列
PCB* m_pBackupReadyPCBs;//后备就绪队列
PCB* m_pInputWaittingPCBs;//输入等待队列
PCB* m_pOutputWaittingPCBs;//输出等待队列
PCB* m_pPureWaittingPCBs;//其他等待队列
int m_nTimeSlice;//时间片大小（定时器时间间隔的倍数）

void LoadPCBs(CString csFileName);//从文件中加载要试验的进程信息



void RemoveProcess(PCB* pPCB);//删除进程

void DoSchedule();

void RunOneTimeRange(PCB* pPCB,int nTime);//运行一个时间段
void TreadWaittingQueue(PCB* pWaittingPCBs);//处理某个等待队列，适时将完成进程移出到后备就绪队列。
void TreadAllWaittingQueues();



void AppendReadyQueue(PCB* pPCB);//pPCB所指节点添加到就绪队尾
void AppendBackupReadyQueue(PCB* pPCB);//pPCB所指节点添加到后备就绪队尾

void AppendWaitQueue(PCB* pPCB);//pPCB所指节点添加到等待队尾
void AppendInputQueue(PCB* pPCB);//pPCB所指节点添加到Input队尾
void AppendOutputQueue(PCB* pPCB);//pPCB所指节点添加到Output队尾




急用！！谢谢了！

7 个解决方案

#1

嗯，很像 操作系统课程的作业啊。。。

#2

大家帮帮忙！！

#3

#include <stdio.h>
#include <stdlib.h>

struct PCB{
    char p_name[20];
    int p_priority;
    int p_needTime;
    int p_runTime;
    char p_state;
    struct PCB* next;
};

void HighPriority();
void RoundRobin();
void Information();
char Choice();
struct PCB* SortList(PCB* HL);

int main()
{
    Information();
    char choice = Choice();
    switch(choice)
    {
        case '1':
            system("cls");
            HighPriority();
            break;
        case '2':
            system("cls");
            RoundRobin();
            break;
        default:
            break;
    }
    system("pause");
    return 0;
}

void Information()
{
    printf("\n\n");
    printf("              *********************************************             \n");
    printf("                            模拟进程调度算法\n");
    printf("              *********************************************             \n\n\n");    
    printf("                       班级：  2008级软件工程4班\n");
    printf("                       姓名：             ******\n");
    printf("                       学号：       ************\n");
    printf("                       实验日期： 2009年12月20日\n\n\n\n\n\n");
    printf("                            按任意键进入演示程序");
    getchar();
    system("cls");
}
char Choice()
{
    printf("\n\n");
    printf("              *********************************************             \n");
    printf("                              进程调度演示\n");
    printf("              *********************************************             \n\n\n");    
    printf("                        1.演示最高优先数优先算法.\n");
    printf("                        2.演示轮转法算法.\n");
    printf("                        3.退出程序.\n\n");
    printf("                                   选择进程调度方法:");     
    char ch = getchar();
    return ch;
    system("cls");
}
void HighPriority()
{
    struct PCB *processes, *pt;
    //pt作为临时节点来创建链表
    processes = pt = (struct PCB*)malloc(sizeof(struct PCB));    
    for (int i = 0; i != 5; ++i)
    {
        struct PCB *p = (struct PCB*)malloc(sizeof(struct PCB));
        printf("进程号No.%d：\n", i);
        printf("输入进程名：");
        scanf("%s", p->p_name);
        printf("输入进程优先数：");
        scanf("%d", &p->p_priority);
        printf("输入进程运行时间：");
        scanf("%d", &p->p_needTime);
        p->p_runTime = 0;
        p->p_state = 'W';
        p->next = NULL;
        pt->next = p;
        pt = p;
        printf("\n\n");
    }
    getchar();  //接受回车
    //processes作为头结点来存储链表
    processes = processes->next;
    int cases = 0;
    struct PCB *psorted = processes;
    while (1)
    {
        ++cases;
        pt = processes; 
        //对链表按照优先数排序
        //psorted用来存放排序后的链表
        psorted = SortList(psorted);
        printf("The execute number: %d\n\n", cases);
        printf("**** 当前正在运行的进程是：%s\n", psorted->p_name);
        psorted->p_state = 'R';
        printf("qname    state    super    ndtime    runtime\n");
        printf("%s\t%c\t%d\t%d\t%d\t\n\n", psorted->p_name, psorted->p_state, psorted->p_priority, psorted->p_needTime, psorted->p_runTime);
        pt->p_state = 'W';
        psorted->p_runTime++;
        psorted->p_priority--;
        printf("**** 当前就绪状态的队列为：\n\n");
        //pt指向已经排序的队列
        pt = psorted->next;
        while (pt != NULL)
        {
            printf("qname    state    super    ndtime    runtime\n");
            printf("%s\t%c\t%d\t%d\t%d\t\n\n", pt->p_name, pt->p_state, pt->p_priority, pt->p_needTime, pt->p_runTime);
            pt = pt->next;
        }
        //pt指向已经排序的链表，判断链表是否有已用时间啊等于需要时间的
        pt = psorted;
        struct PCB *ap;
        ap = NULL; //ap指向pt的前一个节点
        while (pt != NULL)
        {
            if (pt->p_needTime == pt->p_runTime)
            {
                if (ap == NULL)
                {
                    pt = psorted->next;
                    psorted = pt;
                }
                else
                    ap->next = pt->next;
            }
            ap = pt;
            pt = pt->next;
        }
        if (psorted->next == NULL)
            break;
        getchar();
    }
}
struct PCB* SortList(PCB* HL)
{
    struct PCB* SL;
    SL = (struct PCB*)malloc(sizeof(struct PCB));
    SL = NULL;

    struct PCB* r = HL;
    while (r != NULL)
    {
        struct PCB* t = r->next;
        struct PCB* cp = SL;
        struct PCB* ap = NULL;
        while (cp != NULL)
        {
            if (r->p_priority > cp->p_priority)
                break;
            else
            {
                ap = cp;
                cp = cp->next;
            }
        }
        if (ap == NULL)
        {
            r->next = SL;
            SL = r;
        }
        else
        {
            r->next = cp;
            ap->next = r;
        }
        r = t;
    }
    return SL;
}
//轮转算法
void RoundRobin()
{
    struct PCB *processes, *pt;
    //pt作为临时节点来创建链表
    processes = pt = (struct PCB*)malloc(sizeof(struct PCB));    
    for (int i = 0; i != 5; ++i)
    {
        struct PCB *p = (struct PCB*)malloc(sizeof(struct PCB));
        printf("进程号No.%d：\n", i);
        printf("输入进程名：");
        scanf("%s", p->p_name);
        printf("输入进程运行时间：");
        scanf("%d", &p->p_needTime);
        p->p_runTime = 0;
        p->p_state = 'W';
        p->next = NULL;
        pt->next = p;
        pt = p;
        printf("\n\n");
    }
    getchar();  //接受回车
    //processes作为头结点来存储链表
    processes = processes->next;
    int cases = 0;
    while (1)
    {
        ++cases;
        pt = processes; 
        printf("The execute number: %d\n\n", cases);
        printf("**** 当前正在运行的进程是：%s\n", pt->p_name);
        pt->p_state = 'R';
        printf("qname    state    super    ndtime    runtime\n");
        printf("%s\t%c\t%d\t%d\t%d\t\n\n", pt->p_name, pt->p_state, pt->p_priority, pt->p_needTime, pt->p_runTime);
        pt->p_state = 'W';
        pt->p_runTime++;
        pt->p_priority--;
        printf("**** 当前就绪状态的队列为：\n\n");
        pt = pt->next;
        while (pt != NULL)
        {
            printf("qname    state    super    ndtime    runtime\n");
            printf("%s\t%c\t%d\t%d\t%d\t\n\n", pt->p_name, pt->p_state, pt->p_priority, pt->p_needTime, pt->p_runTime);
            pt = pt->next;
        }
        //检测是否运行时间等于需要时间，是的话从队列里面删除，不是的话加到队列最尾部
        pt = processes;
        if (pt->p_needTime == pt->p_runTime)
        {
            pt->p_state = 'C';
            pt = processes->next;
            processes = pt;
        }
        else
        {
            if (pt ->next != NULL)
            {
                //寻找最后一个节点
                while (pt->next != NULL)
                    pt = pt->next;
                struct PCB* ptem;//临时节点用来帮助把头结点插到尾部
                ptem = processes->next;
                pt->next = processes;
                processes->next = NULL;
                processes = ptem;
            }
        }
        pt = processes;
        if (pt == NULL)
            break;
        getchar();
    }
}

我当初写的，比较简单的。不知道对楼主有帮助没有。

#4

http://www.pudn.com/downloads28/sourcecode/windows/other/detail88635.html
这么经典的作业可以上pudn下一个

#5

以前我曾用图形的方法来演示每种调度算法...

#6

大二上就开操作系统了？

#7

希望大家帮帮忙啊！谢谢了！！