#ifndef _OSprocess_H_
#define _OSprocess_H_

enum {READY, RUNNING}; //进程运行状态
enum {RR, SPF}; //算法选择

typedef struct _Pcb
{
int pid; /*进程ID*/
char name[20]; /*进程名*/

int state; /*进程状态*/
int priority; /*进程优先级*/

int tArriving; /*到达时间*/
int tOverall; /*运行时间*/
int tRunning; /*已运行时间*/

}Pcb;

typedef struct _PcbQueue
{
Pcb *block; /*Pcb数据域*/
struct _PcbQueue *next; /*指针域*/
}PcbQueue;

typedef struct _PPQueue
{
PcbQueue *head;
PcbQueue *tail;
}PPQueue;

//typedef struct _GQueues
//{
// PPQueue qFree; /*空余队列*/
// PPQueue qReady; /*就绪队列*/
//}GQueues;

/*分配的最大空余PCB块数*/
#define MAX_PCB_NUM 10
extern Pcb pcbBlock[MAX_PCB_NUM];

#endif

OSPPQueue.h

#ifndef _OSGQueue_H_
#define _OSGQueue_H_

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

#include "OSprocess.h"
#include "OSQueue.h"

/* 初始化PCB块和空余队列 */
int InitGQueues(PPQueue *gq)
{
 gq->tail = gq->head = NULL;

 return 0;
}

/* 分配PCB内存块 */
int allocPcb(PPQueue *gq, int pid, int tServing, int tArriving)
{
 Pcb *Node = (Pcb *)malloc(sizeof(Pcb));

 Node->pid = pid;
 Node->state = 0;
 Node->tArriving = tArriving;
 Node->tOverall = tServing;
 Node->tRunning = 0;

 enQueue(gq,Node);

 return 0;
}

/* RR算法 */
void invokeRR(PPQueue *qReady, PPQueue *qFree)
{
 Pcb *data = (Pcb *)malloc(sizeof(Pcb));
 data = DeQueue(qReady);
 if (data->tRunning == data->tOverall)
 {
  enQueue(qFree,data);
 }
 else
 {
  enQueue(qReady,data);
 }
}
/* SPF算法 */
int invokeSpf(PPQueue *qReady, PPQueue *qFree)
{
 int pid = 0;
 PcbQueue *Node = (PcbQueue *)malloc(sizeof(PcbQueue));
 Pcb *data = (Pcb *)malloc(sizeof(Pcb));

 Node = qReady->head;
 if (Node->block->tArriving == 0)
 {
  ++(Node->block->tRunning);
  pid = Node->block->pid;
  if (Node->block->tRunning == Node->block->tOverall)
  {
   data = DeQueue(qReady);
   enQueue(qFree,data);
  }
 }
 else
 {
  pid = -1;
 }
 while(Node != NULL)
 {
  if (Node->block->tArriving > 0)
  {
   Node->block->tArriving--;
  }
  Node = Node->next;
 }
 return pid;
}

/* 返回执行进程的pid, -1表示无就绪进程 */
int running(PPQueue *qReady, PPQueue *qFree)
{
 int pid = 0;
 PcbQueue *Node = (PcbQueue *)malloc(sizeof(PcbQueue));
 Pcb *data;

 Node = qReady->head;
 if (Node->block->tArriving == 0)
 {
  (Node->block->tRunning)++;
  pid = Node->block->pid;
  invokeRR(qReady,qFree);
 }
 else
 {
  pid = -1;

  if (Node->block->tArriving > 0)
  {
   Node->block->tArriving--;
   data = DeQueue(qReady);
   enQueue(qReady, data);
  }
 }
 return pid;
}

///* 队头进程是否结束，1为运行完毕 */
//int finishReadyHead(GQueues *gq)

#endif

OSQueue.h

#ifndef _OSQueue_H_
#define _OSQueue_H_

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

#include "OSprocess.h"

/* 创建队列 */
PcbQueue *creatPcb(Pcb *block)
{
 PcbQueue *Queue = (PcbQueue *)malloc(sizeof(PcbQueue));
 Queue->block = block;
 Queue->next = NULL;

 return Queue;
}

/* 添加队列 */
void enQueue(PPQueue *gq, Pcb *block)
{
 PcbQueue *Node = (PcbQueue *)malloc(sizeof(PcbQueue));
 Node->block = block;
 Node->next = NULL;

 if(gq->tail == NULL)
 {
  gq->head = gq->tail = Node;
 }
 else
 {
  gq->tail->next = Node;
  gq->tail = Node;
 }
}

/*出队列*/
Pcb *DeQueue(PPQueue *ptr)
{
 PcbQueue *Node;
 if(ptr->tail==NULL)
 {
  return NULL;
 }
 Node = ptr->head;
 if (ptr->head == ptr->tail)
 {
  ptr->head = ptr->tail = NULL;
 }
 else
 {
  ptr->head = ptr->head->next;
 }

 return Node->block;
}
/* 删除队列 */
void freeQueue(PPQueue *gq)
{
 PcbQueue *Node = gq->head;
 PcbQueue *ptr;

 if (Node != NULL)
 {
  ptr = Node->next;
  while(ptr!=NULL)
  {
   free(Node);
   Node = ptr;
   ptr = Node->next;
  }
 }
 free(gq);
}

#endif

OSprocess.h

#ifndef _OSprocess_H_
#define _OSprocess_H_

enum {READY, RUNNING};  //进程运行状态
enum {RR, SPF};    //算法选择

typedef struct _Pcb
{
 int pid;     /*进程ID*/
 char name[20];    /*进程名*/

 int state;     /*进程状态*/
 int priority;    /*进程优先级*/

 int tArriving;    /*到达时间*/
 int tOverall;    /*运行时间*/
 int tRunning;    /*已运行时间*/

}Pcb;

typedef struct _PcbQueue
{
 Pcb *block;     /*Pcb数据域*/
 struct _PcbQueue *next;  /*指针域*/
}PcbQueue;

typedef struct _PPQueue
{
 PcbQueue *head;
 PcbQueue *tail;
}PPQueue;

//typedef struct _GQueues
//{
// PPQueue qFree;   /*空余队列*/
// PPQueue qReady;   /*就绪队列*/
//}GQueues;

/*分配的最大空余PCB块数*/
#define MAX_PCB_NUM 10
extern Pcb pcbBlock[MAX_PCB_NUM];

#endif

OSsort.h

#ifndef _OSsort_H_
#define _OSsort_H_

#include <stdlib.h>

#include "OSsort.h"

/* 比较函数: 若pA > pB, 返回1; 否则返回0*/
int compare(Pcb *pA, Pcb *pB)
{
 return pB->tArriving < pA->tArriving;
}

/* 冒泡排序 */
void BubbleSort(PPQueue *qReady)
{
 PcbQueue *head = qReady->head;
 PcbQueue *next;
 Pcb *temp;

 while (head != qReady->tail)
 {
  next = head->next;
  while(next != NULL)
  {
   if (compare(head->block, next->block))
   {
    temp = head->block;
    head->block = next->block;
    next->block = temp;
   }
   next = next->next;
  }
  head = head->next;
 }
}

#endif

main.c

/*
* 实验1. 进程调度算法的设计
*
* 实验目的：通过对进程调度算法的设计，深入理解进程调度的原理
*
* 实验内容
* 实现短进程优先调度算法（SPF）和时间片轮转调度算法（RR）
*
* 实验要求
* - 进程通过定义一个进程控制块的数据结构（PCB）来表示；
* - 每个进程需要赋予进程ID、进程到达时间、进程需要运行的总时间的属性；
* - 在RR中，以1为时间片单位；
*/

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

#include "OSPPQueue.h"
#include "OSsort.h"

int main()
{
 int i;
 int nProc;
 int tServing, tArriving;

 int nTime = 0;
 int pid = 0;
 int choice;

 PPQueue *qReady = (PPQueue *)malloc(sizeof(PPQueue));
 PPQueue *qFree = (PPQueue *)malloc(sizeof(PPQueue));

 Pcb *data = (Pcb *)malloc(sizeof(Pcb));

 InitGQueues(qReady);
 InitGQueues(qFree);

 printf("Please input the number of processes:  ");
 scanf("%d", &nProc);

 for (i = 0;i < nProc; i++)
 {
  printf("No. %d\n", i);
  printf("\t ServingTime: ");
  scanf("%d", &tServing);
  printf("\t ArrivingTime: ");
  scanf("%d", &tArriving);
  allocPcb(qReady,i,tServing,tArriving);
 }

 do
 {
  printf("Please input the choice[0(RR) | 1(SPF)]: ");
  scanf("%d", &choice);

  if (choice==0)
  {
   while(1)
   {
    printf("nTime = %d\t", nTime++);
    pid = running(qReady, qFree);
    printf("pid = %d\n", pid);
    if (qReady->head==NULL && qReady->tail==NULL)
     break;

   }
  }
  else if (choice == 1)
  {
   /*BubbleSort(qReady);*/
   while(1)
   {
    printf("nTime = %d\t", nTime++);
    pid = invokeSpf(qReady,qFree);
    printf("pid = %d\n", pid);
    if (qReady->head==NULL && qReady->tail==NULL)
     break;
   }
   BubbleSort(qReady);
  }
 } while (choice == 0 && choice == 1);

 freeQueue(qReady);
 freeQueue(qFree);
 qReady = NULL;
 qFree = NULL;

 system("pause");
 return 0;
}