操作系统 时间片轮转算法

一、 实验题目： 

进程时间片轮转调度算法 

二、实验原理： 

在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对调度的处理又都可采用不同的调度方式和调度算法。调度算法是指：根据系统的资源分配策略所规定的资源分配算法。 

三、实验目的： 

1、加深对进程概念的理解，明确进程和程序的区别。

 2、深入系统如何组织进程、创建进程。 

3、进一步认识如何实现处理器调度。 

4、通过对进程调度算法的设计，深入理解进程调度的原理。 

5、加深对时间片轮转调度算法的理解。 

四、实验要求： 

用C语言编写程序完成单处理机的进程调度，要求采用时间片轮转调度算法。实验具体要求包括：首先确定作业控制块的内容和组成方式；然后完成作业调度；最后编写主函数，并对所做工作进行测试。

五、运行结果

时间片大小为1时（q=1）：

时间片大小为4时（q=4）：

六、代码

#include"stdafx.h"

#include

#include

#include

#include

#defineOK 0

#defineOVERFLOW 1

char pro[20] ;    //进程 

int processNum;     //进程数 

int timeSlice = 0;   //时间片 

typedefcharQlemTypeChar;

typedefintQlemTypeInt;

typedefintStatus;

typedefstructQNode

{

    QlemTypeChar data;

    QlemTypeInt timeArrive = 0;

    QlemTypeInt timeService = 0;

    QlemTypeInt timeCount = 0;

    QlemTypeInt runCount = 0;

    QlemTypeInt timeFinal = 0;   //完成时间

    QlemTypeInt timeRound = 0;  //周转时间

    float timeRightRound = 0;  //带权周转时间

    QlemTypeChar proState = 'W';     //进程的状态，W——就绪态，R——执行态，F——完成态   

    struct    QNode *next;   //链表指针   

}QNode, *QueuePtr;

typedefstruct{

    QueuePtr front;    //队头指针

    QueuePtr rear;     //队尾指针

}LinkQueue;

Status InitQueue(LinkQueue&Q){

    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));

    if(!Q.front) exit(OVERFLOW);

    Q.front->next = NULL;

    returnOK;

}

Status EnQueue(LinkQueue&Q, QlemTypeChare){

    QueuePtr p;

    p = (QueuePtr)malloc(sizeof(QNode));

    if (!p) exit(OVERFLOW);

p->data = e;

p->next = NULL;

    Q.rear->next = p;

    Q.rear = p;

    returnOK;

}

Status DeQueue(LinkQueue&Q, QlemTypeChar&e){

    QueuePtr p;

    if (Q.front == Q.rear) returnERROR;

    p = Q.front->next;

    e = p->data;

    Q.front->next = p->next;

    if (Q.rear == p) Q.rear = Q.front;

    free(p);

    returnOK;

}

LinkQueue QPro;

QNode qq[10];

void ProGetFirst(){          //取出就绪队列队首进程

    InitQueue(QPro);

    printf("请输入要创建的进程名称:\\n");

    for (int i = 0; i < processNum-1; i++){

        fflush(stdin);

        scanf_s("%c", &pro[i]);

    }

    fflush(stdin);

    for (int i = 0; i        qq[i].data = pro[i];

        EnQueue(QPro, qq[i].data);

    }

}

void scanfData(){

    printf("请输入要创建的进程数目:");

    scanf_s("%d", &processNum);

    processNum++;

    fflush(stdin);

    printf("\\n");

    ProGetFirst();

    printf("创建进程到达时间：\\n");

    int time_Arr[10];

    for (int i = 0; i < processNum-1; i++){

        scanf_s("%d", &time_Arr[i]);

    }

    for (int i =0; i        qq[i].timeArrive = time_Arr[i];

        EnQueue(QPro, qq[i].timeArrive);

    }

    printf("创建进程服务时间：\\n");

    int time_Ser[10];

    for (int i = 0; i < processNum-1; i++){

        scanf_s("%d", &time_Ser[i]);

    }

    for (int i = 0; i        qq[i].timeService = time_Ser[i];

        EnQueue(QPro, qq[i].timeService);

    }

    printf("请输入时间片大小：:");

    scanf_s("%d", &timeSlice);

    printf("\\n");

}

void ProOutPut1(){           //获取进程信息

    printf("进程名\     到达时间\   服务时间\   进程状态\   执行次数\\n");

    for (int i = 0; i < processNum - 1; i++){

            printf("%c\\%d\\%d\\%c\\%d\\n", qq[i].data, qq[i].timeArrive, qq[i].timeService, qq[i].proState, qq[i].runCount);

    }

}

void CalculatetimeFinal(){         //计算完成时间

    int timecou=0;

    int countTemp = 0;

    QlemTypeChar ee;

    for (int i = 0; i < processNum - 1; i++)

    {

        countTemp += qq[i].timeService;

    }

    while (timecou < countTemp){

        for (int i = 0; i < processNum - 1; i++)

        {

            if (qq[i].timeFinal == 0)

            {

                if (qq[i].timeService - qq[i].timeCount >= timeSlice)

                {

                    timecou += timeSlice;

                }

                else

                {

                    timecou += (qq[i].timeService - qq[i].timeCount);

                    //DeQueue(QPro, ee);

                }

                if (timeSlice < qq[i].timeService) //时间片大小< 服务时间

                {

                    int timetemp = timeSlice > qq[i].timeService ? qq[i].timeService : timeSlice;

                    if ((qq[i].timeCount + timetemp) < qq[i].timeService)

                    {

                        if (qq[i].timeService - qq[i].timeCount >= timeSlice)

                        {

                            qq[i].timeCount += timeSlice;

                        }

                        else

                        {

                            qq[i].timeCount += (qq[i].timeService - qq[i].timeCount); 

                        }

                    }

                    else

                    {

                        if (qq[i].timeFinal == 0)   

                        {

                            qq[i].timeFinal = timecou;

                        }

                    }

                }

                else//时间片大小>= 服务时间

                {

                    qq[i].timeFinal = timecou;   //该进程的完成时间=count

                }

            }

        }

    }

    for (int i = 0; i < processNum - 1; ++i)

    {

        qq[i].timeRound = qq[i].timeFinal - qq[i].timeArrive;

        qq[i].timeRightRound = (float)qq[i].timeRound / qq[i].timeService;

    }

}

void ProOutPut2(){           //获取进程处理后的信息

    printf("进程名\   到达时间     服务时间     完成时间     周转时间     带权周转\\n");

    for (int i = 0; i < processNum - 1; i++){

        printf("  %c\\%d\      %d\      %d\      %d\     %.2f\\n", qq[i].data, qq[i].timeArrive, qq[i].timeService, qq[i].timeFinal, qq[i].timeRound, qq[i].timeRightRound);

    }

}

int_tmain(intargc, _TCHAR* argv[])

{

    scanfData();

    ProOutPut1();

    CalculatetimeFinal();

    printf("\\n");

    printf("CPU处理中......\\n");

    printf("完成时间：");

    for (int i = 0; i < processNum - 1; i++){

        printf("%d,", qq[i].timeFinal);

    }

    printf("\\n");

    printf("周转时间：");

    for (int i = 0; i < processNum - 1; i++){

        printf("%d,",qq[i].timeRound);

    }

    printf("\\n");

    printf("带权周转时间：");

    for (int i = 0; i < processNum - 1; i++){

        printf("%.2f,", qq[i].timeRightRound);

    }

    printf("\\n");

    ProOutPut2();

    return 0;

}