操作系统进程调度（动态优先级调度算法---ready、waiting、running三态）

运行环境为 Ubuntu，Linux系统，C语言

本算法思想：
首先创建进程的时候，就按照优先级高低把进程插入正确的顺序中。
之后的调度：运行完一个进程时间片，重新衡量它的优先级并插入到合适的地方。

一开始老师给的参考代码是只有ready和running态（最后面也贴出了此代码）；老师做实验让我们加入waiting态，最好的方法应该是要把waiting态单独放在一个队列中，我当时觉得太麻烦了，就想直接放在末尾，奈何我想的太简单了，直接放末尾也超级麻烦，打算后期有时间写一下把waiting态单独放在队列中的代码！！！！！！

要考虑很多东西：
1.如何保证waiting态始终在末尾？答：每次重新衡量running态进程时，必须要绕过waiting态，不管waiting态的优先级多高，放在waiting态前面。
2.如何保证唤醒的进程重新插入队列？答：先把该唤醒进程摘取出来，再按照优先级插入。还要考虑队列中是否只剩下waiting态的进程，专门加一个if条件，还有执行操作。

//三态（ready/running/waiting）

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

#include <memory.h>
#include <unistd.h>
#include <termios.h>
#include <fcntl.h>


typedef struct pcb
{
    int pid;  /*Process ID*/
    int prior; /*进程优先级*/
    char status[10]; /*状态:ready,running,waiting*/
    int time;  //运行需要的时间
    struct pcb *next;
}PCB;


FILE *fp = NULL;


int sort(PCB **pstPCBHead,int *iNumProc);
int printProc(PCB *pstPCBHead);
int kbhit(void);
int insert_waiting(PCB **pstPCBHead);
int insert_ready(PCB **pstPCBHead,PCB **pstPCBNode);



int main()
{
    int iNumProc = 0; //进程的数量
    int i = 0;
    
    PCB *stPCBHead = NULL;  //头进程
    PCB *stPCB = NULL;  //链表指针
    PCB *stPCBFront = NULL; //进程前驱
    PCB *stPCBNode = NULL;
    
    char filename[128];
    
    memset(filename,0x00,sizeof(filename)); //初始化文件内容
    
    //sprintf(filename,"%s/schedule",getenv("HOME")); //filename=/HOME/schedule
    sprintf(filename,"%s", ".\\schedule"); //filename=/HOME/schedule
    
    if( (fp=fopen(filename,"w")) == NULL )
    {
        printf("Create log file failed!\n");
        return -1;
    }
    
    //输入进程的数量
    printf("Please input the number of process\n");
    scanf("%d",&iNumProc);
    
    //进程的数量必须大于0
    while( iNumProc <= 0)
    {
        printf("The number of process cann't be 0");
        printf("Please input the number of process again\n");
        scanf("%d",&iNumProc);      
    }
    
    for(i = 0;i < iNumProc;i++)
    {
        //创建进程结点
        stPCBNode=(PCB *)malloc(sizeof(PCB));
        if( (stPCBNode == NULL) )
        {
            printf("malloc memory failed!\n");
            return -1;
        }
        memset(stPCBNode,0x00,sizeof(PCB));
        
        //初始化进程的信息
        stPCBNode->pid = i;  //进程ID
        
        //输入进程优先级
        printf("Please input the prior of process[%d]\n",i);
        scanf("%d",&stPCBNode->prior);   
        /*进程的优先级必须大于0*/
        while( stPCBNode->prior < 0 )
        {
            printf("Process's prior must greater than 0\n");
            printf("Please input the prior of process[%d]\n",i);
            scanf("%d",&stPCBNode->prior);  
        }
        
        //输入进程运行时间
        printf("Please input the run time of process[%d]\n",i);
        scanf("%d",&stPCBNode->time);          
        /*进程的运行时间必须大于0*/
        while( stPCBNode->time < 0 )
        {
            printf("Process's run time must greater than 0\n");
            printf("Please input the run time of process[%d]\n",i);
            scanf("%d",&stPCBNode->time); 
        }       
        
        //初始化进程的状态为ready
        strcpy(stPCBNode->status,"ready"); 
        stPCBNode->next = NULL; 
        
        //连接新的进程结点
        if(stPCBHead == NULL)
        {
            stPCBHead = stPCBNode; //如果首结点为空,则让Node变成Head
            continue;
        }
        
        stPCB=stPCBHead;       //让stPCB指针指向Head
        stPCBFront=stPCBHead;  //让前驱指针stPCBFront指向Head
        
        while( stPCB != NULL && stPCB->prior >= stPCBNode->prior )  //循环查找该Node的前驱指针(即找到与Node的优先级相差最少,且比Node优先级大)
        {
            stPCBFront = stPCB;   //把该元素先假定为前驱Front
            stPCB = stPCB->next;  //指向下一个链表中的元素
        }
        
        
        if( stPCB == stPCBHead ) //优先级最高,插在最前面
        {
            stPCBNode->next = stPCBHead;  //先插在Head前面
            stPCBHead = stPCBNode;  //再把该节点变成Head
        }
        
        else if( stPCB == NULL ) //stPCB已经走到链表最后了,所以Front是stPCB的前一个,直接把Node插到尾部(Front的后面)
        {
            stPCBFront->next = stPCBNode; //添加到link的尾部
        }
        
        else  //插入到link (stPCB的前面,Front的后面)
        {
            stPCBNode->next = stPCB; 
            stPCBFront->next = stPCBNode;
        }
        
        printf("Create the process [%d] success\n",i);     
    } //for{ }
    
    
    
    fprintf(fp,"Create %d processes success\n",iNumProc);
    printf("In the begin of schedule,these process's queque\n");
    fprintf(fp,"Before Schedule\n");
    printProc(stPCBHead);
    
    sleep(1);
    
    //现在开始调度
    printf("Begin schedule\n");
    fprintf(fp,"Begin schedule\n");
    stPCB = stPCBHead;
    
    while( iNumProc > 0)
    {
        
        /* schedule from first process */
        if ( strcmp(stPCBHead->status, "ready") == 0 )
            strcpy(stPCBHead->status, "running");
        printProc(stPCBHead);
        
        if(strcmp((stPCBHead)->status, "running")==0) {
            stPCBHead->time--;
            stPCBHead->prior--;
        }



        
        //检测是否有按键s按下,如果有则把当前进程变成waiting态
        //while(kbhit() && (getchar() == 's' || getchar() == 'S') ) 
	int k=0;
	if( kbhit() ) k=getchar();

        if(k == 's')  
        { 
            printf("ss\n");
            strcpy(stPCBHead->status,"waiting");
            //printf("有按键按下了\n");
            printf("process %d waiting\n",stPCBHead->pid);
            setbuf(stdin,NULL);
            
            insert_waiting(&stPCBHead);  //直接把waiting进程放在末尾
            //break;
        }

        /* Update the the level of proccess which in ready status */
        for (stPCB=stPCBHead; stPCB != NULL; stPCB=stPCB->next)
        {
            if ( strcmp(stPCB->status, "ready") == 0)
            {
                stPCB->prior++;
            }
        }
        /*再次排序schedule*/
        sort(&stPCBHead,&iNumProc);  //排序link,删除time=0的进程    
        
        //检测是否有按键1-9按下,如果有则把第一个waiting状态的进程变成ready态,排序插入到其前驱的后面
        //while(kbhit() && (getchar() >= 0 && getchar() <= 9) )  
        if(k>='0' && k<='9')
        { 
            PCB *cur = NULL; //waiting态结点
            PCB *fro = NULL; //waiting态结点的前一个
            PCB *p = NULL; 
            printf("有数字按下了\n");
            
            setbuf(stdin,NULL);
            cur = stPCBHead;
            fro = stPCBHead;
            while( cur != NULL )
            {
                if( strcmp(cur->status,"waiting") == 0)
                {
                    strcpy(cur->status,"ready"); 
                    break;              
                } 
                fro = cur;
                cur = cur->next;
            }
            
            if(cur == stPCBHead) 
            {
              stPCBHead = stPCBHead->next;
              cur->next = NULL;
            }
            else {
	       p = cur->next;
	       fro->next = p;
	       cur->next = NULL;
            }

            insert_ready(&stPCBHead,&cur);  //把唤醒的进程重新按优先级顺序插入到队列中
            
        }
        

        //printProc(stPCBHead);
        
    } //while{ }
    
    return 0;
    
} //main{ }




/*============================子函数=================================================*/
int printProc(PCB *pstPCBHead)
{
    PCB *pstPCB = pstPCBHead;
    printf("----------------------------------------------------------------------------\n");
    printf("|  Process's ID  |  Process's prior   |  Process's Status  |  The time left  |  Current Process Addr  |  Next Process Addr |\n");
    printf("----------------------------------------------------------------------------\n");
    
    
    fprintf(fp,"----------------------------------------------------------------------------\n");
    fprintf(fp,"|  Process's ID  |  Process's prior   |  Process's Status  |  The time left  |  Current Process Addr  |  Next Process Addr |\n");
    fprintf(fp,"----------------------------------------------------------------------------\n");
    
    
    while( pstPCB != NULL )
    {
        sleep(1);
        
        printf( "|%10d|%16d|%22s|%15d|%24d|%20d|\n",pstPCB->pid,pstPCB->prior,pstPCB->status,pstPCB->time,(int)pstPCB,(int)pstPCB->next );
        printf( "----------------------------------------------------------------------------\n");
        
        fprintf( fp,"|%10d|%16d|%22s|%15d|%24d|%20d|\n",pstPCB->pid,pstPCB->prior,pstPCB->status,pstPCB->time,(int)pstPCB,(int)pstPCB->next );
        fprintf( fp,"----------------------------------------------------------------------------");
        
        pstPCB = pstPCB->next;
    }
    
    printf("\n\n");
    fprintf(fp,"\n\n");
    
    return 0;
}


int sort(PCB **pstPCBHead, int *iNumProc)
{
    PCB *pstPCB=NULL;
    PCB *pstPCBFront=NULL;
    int flag=0;
    
    pstPCB=(*pstPCBHead);
    pstPCBFront=(*pstPCBHead);
    
    if ( (*pstPCBHead)->time == 0 )
    {
        printf("Proccess [%d] run end!\n", pstPCBFront->pid);
        (*pstPCBHead) = (*pstPCBHead)->next;
        free(pstPCBFront);
        pstPCBFront=NULL;
        (*iNumProc)--;
        //return 0;
    }
    
    if ( (*iNumProc) <= 1 )
    {
        return 0;
    }
    
    if(strcmp((*pstPCBHead)->status,"running")==0)
        strcpy((*pstPCBHead)->status,"ready");
    
    while ( pstPCB != NULL && (*pstPCBHead)->prior <= pstPCB->prior && strcmp(pstPCB->status,"ready") == 0)
    {
        pstPCBFront = pstPCB;
        pstPCB=pstPCB->next;
        flag=1;
    }
    
    if ( pstPCB == NULL && flag==1)
    {
        if(strcmp((*pstPCBHead)->status, "running")==0)
            strcpy((*pstPCBHead)->status, "ready");
        pstPCBFront->next = (*pstPCBHead);
        *pstPCBHead = (*pstPCBHead)->next;
        pstPCBFront->next->next = NULL;
    }
    else if ( flag== 1)
    {
        if(strcmp((*pstPCBHead)->status, "running")==0)
            strcpy((*pstPCBHead)->status, "ready");
        pstPCBFront->next = (*pstPCBHead);
        (*pstPCBHead)= (*pstPCBHead)->next;
        pstPCBFront->next->next=pstPCB;
    }
    
    return 0;
}




//非阻塞检测按键函数
int kbhit(void)
{ 
struct termios oldt, newt;
int ch,oldf; 
tcgetattr(STDIN_FILENO, &oldt);
newt=oldt;
newt.c_lflag &= ~(ICANON | ECHO);
tcsetattr(STDIN_FILENO, TCSANOW, &newt);
oldf=fcntl(STDIN_FILENO, F_GETFL, 0);
fcntl(STDIN_FILENO, F_SETFL, oldf | O_NONBLOCK);

  ch=getchar();
  tcsetattr(STDIN_FILENO, TCSANOW, &oldt);
  fcntl(STDIN_FILENO, F_SETFL, oldf);
  if(ch != EOF) { 
  ungetc(ch, stdin);
  return 1;
  } 
  return 0;
  }


int insert_waiting(PCB **pstPCBHead)
{
    PCB *pstPCB = NULL;
    PCB *pstPCBFront = NULL;
    PCB *p = NULL;
    
    pstPCB = (*pstPCBHead);
    pstPCBFront = (*pstPCBHead);
    

    
    if( strcmp( (*pstPCBHead)->status,"waiting") == 0) {
        while( pstPCB != NULL )  //把指针指到链表最后一个元素
        {
            pstPCBFront = pstPCB;   //把该元素先假定为前驱Front
            pstPCB = pstPCB->next;  //指向下一个链表中的元素
        }
        
        if( pstPCB == NULL) 
        {
            p = *pstPCBHead;
            (*pstPCBHead) = (*pstPCBHead)->next; //该Head的后面一个就是本次称霸的对象(因为本来就是按顺序排列的,老大下了,老二接手)
            pstPCBFront->next = p; //添加到link的尾部
            pstPCBFront = pstPCBFront->next;
            pstPCBFront->next = NULL;
        }
        
    } 
    
    return 0;
}

int insert_ready(PCB **pstPCBHead,PCB **pstPCBNode)
{
    PCB *pstPCB = NULL;
    PCB *pstPCBFront = NULL;
    
    pstPCB = (*pstPCBHead);
    pstPCBFront = (*pstPCBHead);
    
    if( strcmp((*pstPCBNode)->status,"ready") == 0) {
        printf("我正在把数字键唤醒的进程排序到队伍中\n");
 
        if((*pstPCBHead) == NULL) //说明该唤醒进程是最后一个进程
        {
           (*pstPCBHead) = *pstPCBNode;
           (*pstPCBHead)->next = NULL;
        }

       
        
        else 
        {
		while( pstPCB != NULL && pstPCB->prior >= (*pstPCBNode)->prior && strcmp(pstPCB->status,"ready") == 0)  //循环查找该Node的前驱指针(即找到与Node的优先级相差最少,且比Node优先级大)
		{
		    pstPCBFront = pstPCB;   //把该元素先假定为前驱Front
		    pstPCB = pstPCB->next;  //指向下一个链表中的元素
		}
		
		
		if( pstPCB == *pstPCBHead ) //优先级最高,插在最前面
		{
		    (*pstPCBNode)->next = *pstPCBHead;  //先插在Head前面
		    *pstPCBHead = *pstPCBNode;  //再把该节点变成Head
		}
		
		else if( pstPCB == NULL ) //stPCB已经走到链表最后了,所以Front是stPCB的前一个,直接把Node插到尾部(Front的后面)
		{
		    pstPCBFront->next = *pstPCBNode; //添加到link的尾部
		    //pstPCBFront->next->next = NULL;
		}
		
		else  //插入到link (stPCB的前面,Front的后面)
		{
		    (*pstPCBNode)->next = pstPCB; 
		    pstPCBFront->next = *pstPCBNode;
		}  
        } //else   
    } //if(status == ready){}
    
    return 0;
    
}

---

---

---

**

//两态（ready/running）

**

/***************************************************************************
输入进程数。输入每个进程优先级、运行时间，初始化为就绪态。
按照优先级优先算法调度进程运行，每运行一个时间片，运行时间减一、优先级减一。
进程在就绪队列中每等待一个时间片，其优先级加一。
****************************************************************************/

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

typedef struct pcb
{
  int  pid;      /* Process ID */
  int  prior;    /* Priority of Processs*/
  char status[10]; /* value: ready,running */
  int  time;
  struct pcb *next;
} PCB;

FILE *fp=NULL;

int main()
{
  int iNumProc=0;
  int i = 0;
  
  PCB *stPCBHead=NULL;
  PCB *stPCB=NULL;
  PCB *stPCBFront=NULL;
  PCB *stPCBNode=NULL;
  
  char  filename[128];
  
  memset(filename, 0x00, sizeof(filename));
  
  sprintf(filename, "%s/schedule.txt", getenv("HOME"));
  if ( (fp=fopen(filename, "w")) == NULL)
  {
    printf("Create log file failed!\n");
    return -1;
  }
  
  /* Input the number of process */
  printf("Please input the number of process\n");
  scanf("%d", &iNumProc);
  
  /* Process number must great than 0 */
  while ( iNumProc <=0 )
  {
    printf("Ther number of process cann't be 0! \n");
    printf("Please input the number of process again\n");
    scanf("%d", &iNumProc);
  }
  
  for(i=0; i<iNumProc; i++)
  {
    /* Create process's node */
    stPCBNode=(PCB *)malloc(sizeof(PCB));
    if ( stPCBNode == NULL )
    {
      printf("malloc memory failed!\n");
      return -1;
    }
    memset(stPCBNode, 0x00, sizeof(PCB));
    
    /* Init process's information */
    stPCBNode->pid=i;    /* Process ID */
    printf("Please input ther prior of process[%d]\n", i);
    scanf("%d", &stPCBNode->prior);  /* Process's prior */
    
    while ( stPCBNode->prior < 0 )
    {
      printf("Process's prior must great than 0\n");
      printf("Please input ther run time of process[%d]\n", i);
      scanf("%d", &stPCBNode->prior);
    }
    
    printf("Please input ther run time of process[%d][%d]\n", i, __LINE__);
    scanf("%d", &stPCBNode->time);
    
    while ( stPCBNode->time < 0 )
    {
      printf("Process's run time must great than 0\n");
      printf("Please input ther run time of process[%d]\n", i);
      scanf("%d", &stPCBNode->time);
    }
    
    strcpy(stPCBNode->status, "ready");  /* Init the process's status ready */
    stPCBNode->next = NULL;
    
    /* Link the new process's node */
    if ( stPCBHead == NULL )
    {
      stPCBHead = stPCBNode;
      continue;
    }
    
    stPCB=stPCBHead;
    stPCBFront=stPCBHead;
    
    while ( stPCB != NULL && stPCB->prior >= stPCBNode->prior )
    {
      stPCBFront = stPCB;
      stPCB=stPCB->next;
    }
    
    if ( stPCB == stPCBHead )
    {
      stPCBNode->next = stPCBHead;
      stPCBHead=stPCBNode;
    }
    else if ( stPCB == NULL )  
    {
      stPCBFront->next = stPCBNode;    /* Add to the tail of the link */
    }
    else          /* insert into the link */
    {
      stPCBNode->next = stPCB;
      stPCBFront->next=stPCBNode;
    }
    
    printf("Create the process [%d] success\n", i);
  }
  fprintf(fp, "Create %d processes success\n", iNumProc);
  
  
  printf("In the begin of schedule, these process's queque\n");
  fprintf(fp, "Before Schedule\n");
  printProc(stPCBHead);
  
  sleep(1);
  
  /* Now Schedual */ 
  printf("Begin schedule\n");
  fprintf(fp, "Begin schedule\n");
  stPCB=stPCBHead;
  while ( iNumProc > 0 )
  {
    /* schedule from first process */
    if ( strcmp(stPCBHead->status, "ready") == 0 )
      strcpy(stPCBHead->status, "running");
    printProc(stPCBHead);
    
    stPCBHead->time--;
    stPCBHead->prior--;
    
    /* Update the the level of proccess which in ready status */
    for (stPCB=stPCBHead; stPCB != NULL; stPCB=stPCB->next)
    {
      if ( strcmp(stPCB->status, "ready") == 0 )
      {
        stPCB->prior++;
      }
    }
    
    /* sort the schedule again */
    sort(&stPCBHead, &iNumProc); /* Sort the link and delete which the process's time is 0 */
  }
  
  return 0;
}

int printProc(PCB *pstPCBHead)
{
  PCB *pstPCB=pstPCBHead;
  printf("------------------------------------------------------------------------------------------------------------\n");
  printf("| Process's ID   | Process's prior| Process's Stauts |The time left|Current Process Addr|Next Process Addr|\n");
  printf("------------------------------------------------------------------------------------------------------------\n");
  
  
  fprintf(fp, "-----------------------------------------------------------------------------------------------------------\n");
  fprintf(fp, "| Process's ID   | Process's prior| Process's Stauts |The time left|Current Process Addr|Next Process Addr|\n");
  fprintf(fp, "-----------------------------------------------------------------------------------------------------------\n");
  while ( pstPCB != NULL )
  {
    sleep(1);
  
    printf("|%16d|%16d|%18s|%13d|%20d|%17d|\n", pstPCB->pid,pstPCB->prior, pstPCB->status, pstPCB->time, (int)pstPCB, (int)pstPCB->next);
    printf("-----------------------------------------------------------------------------------------------------------\n");
  
    fprintf(fp, "|%16d|%16d|%18s|%13d|%20d|%17d|\n", pstPCB->pid, pstPCB->prior, pstPCB->status, pstPCB->time, (int)pstPCB, (int)pstPCB->next);
    fprintf(fp, "-----------------------------------------------------------------------------------------------------------\n");
    pstPCB=pstPCB->next;
  }
    
  printf("\n\n");
  fprintf(fp, "\n\n");
    
  return 0;
}

int sort(PCB **pstPCBHead, int *iNumProc)
{
  PCB *pstPCB=NULL;
  PCB *pstPCBFront=NULL;
  int flag=0;
  
  pstPCB=(*pstPCBHead)->next;
  pstPCBFront=(*pstPCBHead);
  
  if ( (*pstPCBHead)->time == 0 )
  {
    printf("Proccess [%d] run end!\n", pstPCBFront->pid);
    (*pstPCBHead) = (*pstPCBHead)->next;
    free(pstPCBFront);
    pstPCBFront=NULL;
    (*iNumProc)--;
    return 0;
  }
  
  if ( (*iNumProc) <= 1 )
  {
    return 0;
  }  
  
  while ( pstPCB != NULL && (*pstPCBHead)->prior <= pstPCB->prior )
  {
    pstPCBFront = pstPCB;
    pstPCB=pstPCB->next;
    flag=1;
  }
  
  if ( pstPCB == NULL && flag==1)
  {
    strcpy((*pstPCBHead)->status, "ready");
    pstPCBFront->next = (*pstPCBHead);
    *pstPCBHead = (*pstPCBHead)->next;
    pstPCBFront->next->next = NULL;
  }
  else if ( flag== 1)
  {
    strcpy((*pstPCBHead)->status, "ready");
    pstPCBFront->next = (*pstPCBHead);
    (*pstPCBHead)= (*pstPCBHead)->next;
    pstPCBFront->next->next=pstPCB;
  }
  
  return 0;
}

---

---

---

---

---

---

更新一下另外一种方法

不考虑每次都把他们按照优先级顺序排列，只要保证每次调度运行的进程的优先级最高即可。也就是把sort函数更改为找到优先级最高的ready进程并让它成为队列首部（Head）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <unistd.h>
#include <termios.h>
#include <fcntl.h>

typedef struct pcb {
    int pid;  //Process ID
    int prior; //进程优先级
    char status[10]; //状态:ready,running,waiting
    int time;  //运行需要的时间
    struct pcb *next;
}PCB;

FILE *fp = NULL;

int kbhit(void);
int printProc(PCB *pstPCBHead);
int sched(PCB **pstPCBHead, int *iNumProc);

int main()
{
    int iNumProc = 0; //进程的数量
    int i = 0;    
    PCB *stPCBHead = NULL;  //头进程
    PCB *stPCB = NULL;  //链表指针
    PCB *stPCBFront = NULL; //进程前驱
    PCB *stPCBNode = NULL;    
    char filename[128];
    
    memset(filename,0x00,sizeof(filename)); //初始化文件内容    
    sprintf(filename,"%s/schedule.txt",getenv("HOME")); // "/home/schedule.txt"
    
    if( (fp=fopen(filename,"w")) == NULL ) {
        printf("Create log file failed!\n");
        return -1;
    }
    
    //输入进程的数量
    printf("请输入进程数:\n");
    scanf("%d",&iNumProc);
    
    //进程的数量必须大于0
    while( iNumProc <= 0){
        printf("进程数须为正整数0");
        printf("请重新输入进程数\n");
        scanf("%d",&iNumProc);      
    }
    
    for(i = 0;i < iNumProc;i++) {
        //创建进程结点
        stPCBNode=(PCB *)malloc(sizeof(PCB));
        if( (stPCBNode == NULL) ){
            printf("分配堆内存失败!\n");
            return -1;
        }
        memset(stPCBNode,0x00,sizeof(PCB));
        
        //初始化进程的信息
        stPCBNode->pid = i;  //进程ID
        printf("请输入进程 [%d] 的优先级\n",i);
        scanf("%d",&stPCBNode->prior);   
        while( stPCBNode->prior < 1 ) {
            printf("优先级必须大于0\n");
            printf("请重新输入进度[%d] 的优先级\n",i);
            scanf("%d",&stPCBNode->prior);  
        }
        printf("请输入进程 [%d] 的运行时间\n",i);
        scanf("%d",&stPCBNode->time);          
        while( stPCBNode->time < 1 ) {
            printf("进行运行时间必须大于0\n");
            printf("请重新输入进程 [%d] 的运行时间\n",i);
            scanf("%d",&stPCBNode->time); 
        }
        strcpy(stPCBNode->status,"ready"); //初始状态为ready
        stPCBNode->next = NULL; 
        
        if(stPCBHead == NULL) {
            stPCBHead = stPCBNode; //队列头结点
            continue;
        }
        stPCB=stPCBHead;
        stPCBFront=stPCBHead;        
        while( stPCB != NULL && stPCB->prior >= stPCBNode->prior ) 
        {
            stPCBFront = stPCB;
            stPCB = stPCB->next;
        }        
        if( stPCB == stPCBHead )  {
            stPCBNode->next = stPCBHead;
            stPCBHead = stPCBNode; 
        }        
        else if( stPCB == NULL )
        {
            stPCBFront->next = stPCBNode;
        }        
        else {
            stPCBNode->next = stPCB; 
            stPCBFront->next = stPCBNode;
        }
        
        printf("创建进程 %d 成功\n",i);     
    }

    fprintf(fp,"创建进程 %d 成功\n",iNumProc);
    printf("调度之前，进程队列\n");
    fprintf(fp,"调度之前，进程队列\n");
    printProc(stPCBHead);
    
    sleep(1);
    
    //现在开始调度
    printf("开始调度\n");
    fprintf(fp,"开始调度\n");
    stPCB = stPCBHead;
    
    while( iNumProc > 0)
    {
        int k=0;
        
        //处理器分派给队首进程
        if ( strcmp(stPCBHead->status, "ready") == 0 )
            strcpy(stPCBHead->status, "running");
        printProc(stPCBHead);
        
        //调整队首进程优先级和运行时间
        if(strcmp((stPCBHead)->status, "running")==0) {
            stPCBHead->time--;
            stPCBHead->prior--;
        }
        
        //检测是否有按键s按下,如果有则把当前进程变成waiting态
        if(kbhit()) k=getchar();
        setbuf(stdin,NULL);
        if(k == 's') {
            strcpy(stPCBHead->status,"waiting");         
            printf("进程 %d 等待...\n",stPCBHead->pid);
            if(stPCBHead->next){ //头结点移到队尾
                PCB *t=stPCBHead;
                while(t && t->next) t=t->next;
                t->next=stPCBHead;
                stPCBHead=stPCBHead->next;
                t->next->next=NULL;                
            }
        }
        else if(k>='0' && k<='9'){ //注意：超过10个进程，不能处理
            PCB *t = stPCBHead;
	    k-='0';
            while(t && t->pid!=k) t=t->next;
            if(t && strcmp(t->status, "waiting")==0 ){
                strcpy(t->status, "ready");
                printf("进程 %d 回到就绪队列\n",t->pid);
            }       
        }
        
        // 提升剩余进程优先级 
        for (stPCB=stPCBHead; stPCB != NULL; stPCB=stPCB->next){
            if ( strcmp(stPCB->status, "ready") == 0)
                stPCB->prior++;
        }
        sched(&stPCBHead,&iNumProc); //调度器选择下一进程
    }
    
    return 0;
    
}

//============================子函数==========================
int printProc(PCB *pstPCBHead)
{
    PCB *pstPCB = pstPCBHead;
    printf("---------------------------------------------------------------------\n");
    printf("| 进程ID | 优先级 |  状态  | 剩余时间 | 当前进程地址 | 后继进程地址 |\n");
    printf("---------------------------------------------------------------------\n");    
    fprintf(fp,"--------------------------------------------------------------------\n");
    fprintf(fp,"| 进程ID | 优先级 |  状态 | 剩余时间 | 当前进程地址 | 后继进程地址 |\n");
    fprintf(fp,"--------------------------------------------------------------------\n");
    
    while( pstPCB != NULL ){
        sleep(1);        
        printf( "|%6d  |%6d  |%7s |%8d  |%14p|%14p|\n",pstPCB->pid,pstPCB->prior,pstPCB->status,pstPCB->time,pstPCB,pstPCB->next );
    	printf("---------------------------------------------------------------------\n");
        fprintf( fp,"|%6d  |%6d  |%7s |%8d  |%14p|%14p|\n",pstPCB->pid,pstPCB->prior,pstPCB->status,pstPCB->time,pstPCB,pstPCB->next );
    	fprintf(fp,"---------------------------------------------------------------------\n");
        pstPCB = pstPCB->next;
    }    
    printf("\n\n");
    fprintf(fp,"\n\n");
    
    return 0;
}

//优先级最大的ready进程放在队首
int sched(PCB **pstPCBHead, int *iNumProc)
{
    PCB * p, *q, t;
    
    if ( (*pstPCBHead)->time == 0 ){
        p=(*pstPCBHead);
        printf("进程 %d 运行结束，终止!\n", p->pid);
        (*pstPCBHead) = (*pstPCBHead)->next;
        free(p);
        p=NULL;
        (*iNumProc)--;
        if(*iNumProc==0) return 0;
    }
    
    if(strcmp((*pstPCBHead)->status,"running")==0)
        strcpy((*pstPCBHead)->status,"ready");
    
    p=(*pstPCBHead); //代表优先级最大的ready进程
    q=(*pstPCBHead)->next;
    while(q && strcmp(q->status,"ready")==0){
        if(p->prior<q->prior) p=q;
        q=q->next;
    }
    if(p!=(*pstPCBHead)){
        t=*(*pstPCBHead); //交换结点
        *(*pstPCBHead)=*p;
        *p=t;
        q=(*pstPCBHead)->next;  //交换链接指针
        (*pstPCBHead)->next=p->next;
        p->next=q;
    }    
    return 0;
}

//非阻塞检测按键函数
int kbhit(void)
{ 
    struct termios oldt, newt;
    int ch,oldf; 
    tcgetattr(STDIN_FILENO, &oldt);
    newt=oldt;
    newt.c_lflag &= ~(ICANON | ECHO);
    tcsetattr(STDIN_FILENO, TCSANOW, &newt);
    oldf=fcntl(STDIN_FILENO, F_GETFL, 0);
    fcntl(STDIN_FILENO, F_SETFL, oldf | O_NONBLOCK);

    ch=getchar();
    tcsetattr(STDIN_FILENO, TCSANOW, &oldt);
    fcntl(STDIN_FILENO, F_SETFL, oldf);
    if(ch != EOF) { 
        ungetc(ch, stdin);
        return 1;
    } 
    return 0;
}