精华内容
下载资源
问答
  • 2020-05-10 12:00:28

    运行环境为 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;
    }
    
    






    更新一下另外一种方法

    //三态2(ready/running/waiting)

    不考虑每次都把他们按照优先级顺序排列,只要保证每次调度运行的进程的优先级最高即可。也就是把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;
    }
    
    
    更多相关内容
  • 使用动态优先权和时间片轮转的进程调度算法的模拟使用动态优先权和时间片轮转的进程调度算法的模拟使用动态优先权和时间片轮转的进程调度算法的模拟使用动态优先权和时间片轮转的进程调度算法的模拟使用动态优先权和...
  • “最高优先数优先”调度算法的基本思想是把CPU分配给就绪队列中优先数最高的进程。 (1). 静态优先数是在创建进程时确定的,并在整个进程运行期间不再改变。 (2). 动态优先数是指进程的优先数在创建进程时可以给定...
  • 操作系统中的非抢占式优先级进程调度算法及验证
  • 调度方案综述进程调度问题概述在多道程序环境下,进程的数目往往多于处理机数目。这就要求系统能按照某种算法,...好的进程调度算法将有效的提高系统中各种资源利用率,减少处理机的空闲时间,避免部分作业长期得不...

    调度方案综述

    进程调度问题概述

    在多道程序环境下,进程的数目往往多于处理机数目。这就要求系统能按照某种算法,动态的把处理机分配给就绪队列中的进程,使之执行。因此,处理机调度是操作系统设计的中心问题之一。进程调度问题的核心就是采用什么样的算法把处理机分配给进程。进程调度算法也是在任何操作系统中必须配置的一级调度。好的进程调度算法将有效的提高系统中各种资源利用率,减少处理机的空闲时间,避免部分作业长期得不到处理机响应等情况的发生。

    动态优先级进程调度算法介绍

    动态优先权调度算法,以就绪队列中各个进程的优先权作为进程调度的依据。各个进程的优先权在创建进程时所赋予,随着进程的推进或其等待时间的增加而改变。进程的优先权利用某一范围内的整数来表示。有的系统数值越小优先权越高,如Unix系统,有的系统则反之。采用该算法时,每次总是在就绪队列中选择一个优先权最高的进程进行调度,并将处理机分配给该进程。动态优先权调度算法又分为抢占式和非抢占式两种。本文采用 C 语言对非抢占式动态优先权调度算法进行了设计和实现。

    数据结构设计

    进程控制块 PCB

    typedef struct pcb {

    unsigned int id; // 进程 ID 号

    unsigned int static_priority; // 静态优先数

    unsigned int dynamic_priority; // 动态优先数

    int state; // 进程状态标识符

    } pcb;

    在 PCB 中,我们将优先级分为两部分,静态优先级和动态优先级。静态优先级在进程创建时则确定,而动态优先级则在进程的运行或等待过程中发生改变。在下文中,我们将静态优先级和动态优先级之和统称为优先级。

    为避免违背系统、用户目的,我们规定动态优先数不能为负数,即动态优先数最小为 0,以免过多地降低进程总体优先级,导致重要进程等待时间过长。

    进程有三种状态,分别为就绪态、阻塞态和完成态,通过常量体现在state属性上。

    就绪队列

    typedef struct sub_queue {

    struct sub_queue* previous; // 指向前驱任务

    struct sub_queue* next; // 指向后继任务

    int pid; // 当前任务 PID

    } sub_queue;

    typedef struct ready_queue {

    int max_priority; // 系统最高优先数

    sub_queue sub_queue_array[MAX_PRIO + 1]; // 就绪队列数组

    int priority_bit_map[MAX_PRIO + 1]; // 优先级位图

    } ready_queue;

    我们定义就绪队列为 ready_queue 结构体,其由系统最高优先数、255个子就绪队列、优先级位图三部分组成;每个子就绪队列为 sub_queue 结构体,其由前驱任务指针、后继任务指针、当前任务PID指针组成。

    其中的 sub_queue_array 存储了255个优先级的子就绪队列,其下标即为优先级,从 1 至 255 级,sub_queue_array[0] 存储了系统中的进程数量 n_proc 值。优先级位图 priority_bit_map 则存储了该下标优先级是否有进程,如有则为 1,反之为0值。

    子就绪队列 sub_queue_array 的下标为 0 元素内容为当前系统进程数量,其余下标 n > 1 的元素内容为,优先级为n的就绪进程链表。例如优先级为3的就绪进程则有 prc_e、prc_g 和 prc_k 三个。

    ee6a44578b89ac6b21de072e0c55a53c.png

    上图代表系统中某个优先级的就绪队列。可以看到,子就绪队列是一个双向链表,任务 1,任务 2 都包含一个双向链表,就绪的任务与任务之间也是用双链表连接在一起。需要注意的是,任务 2 和优先级的头节点也是相连的。

    如果一个优先级对应的子就绪队列中有多个任务,系统调度时总会选择链表头节点指向的第一个任务作为最高优先级任务先去运行,如上图中最高优先级的就是 task_a 任务。

    在这里,我们的子就绪队列采用了双向链表,而不是采用了传统的单向链表,目的是加快任务插入到尾部的速度。

    程序算法设计

    算法设计思路

    优先数增减原则

    参考 Linux 的实现方式,经过简化,我们规定优先数改变的原则如下:

    进程每运行一个时间片,动态优先数减 3

    其次,PCB 的数据结构及操作采用数组方式,将系统的 N 个进程 PCB 信息保存到一个长度为 N 的 pcbs 数组中。

    系统初始条件

    若系统中有若干个进程,每个进程产生时间,优先级各不相同。

    利用进程控制块 PCB 来描述各个进程,进程控制块PCB包括以下字段:

    进程标识数 ID

    静态优先数 STATIC_PRIORITY,规定优先数越大的进程,其优先级越高

    动态优先数 DYNAMIC_PRIORITY,规定优先数越大的进程,其优先级越高

    进程状态 STATE ,包括三种状态:就绪态、阻塞态、完成态

    CPU 处理进程是从就绪队列中选择当前各进程中优先权最大的进程开始的。由于采用的是非抢占式调度算法,则当前进程执行完一个时间片之后有以下几种情况:

    当前进程结束则退出系统,否则排到就绪队列尾或进入阻塞队列尾。

    考虑阻塞队列中的进程是否能移入就绪队列中,若有则移入。

    若就绪队列中有进程存在,则按优先权原则选择进程执行,否则 CPU 处于等待状态。

    进程调度算法实现

    执行进程优先级的选取

    // 在优先级位图中,选择优先级最高的子就绪队列

    int current_priority = -1;

    for (int j = ready_queue.highest_priority; j > 0; --j)

    if (ready_queue.priority_bit_map[j] == 1) {

    current_priority = j;

    break;

    }

    if (currrent_prioriy == -1)

    processor_wait();

    优先级位图 priority_bit_map 存储了该下标优先级是否有进程,如有则为 1,反之为 0 值。虽然系统也可以通过子队列数组 sub_queue_array 逐个查询链表头为空,但效率较低,且必须顺序查询,不可随机进行。在下述“执行进程的选取与运行”中,若子就绪队列为空,则置对应位为 0;在有新进程进入就绪队列时,应维护对应优先数位图值相匹配。

    执行进程的选取与运行

    我们来看一下,执行进程的选取与运行流程图,本部分流程图是上文全局流程图中“处理进程”的子流程。

    5974e202f9567b4b35bb5bc7309c65c7.png

    具体代码实现思路如下:

    crt_static_prio = pcbs[current_task_pid].static_priority;

    crt_dynamic_prio = pcbs[current_task_pid].dynamic_priority;

    // 判断当前进程优先级和当前系统优先级是否相等

    if (crt_static_prio + crt_dynamic_prio == current_priority) {

    // 如程优先级和系统优先级相等,则继续运行当前进程,减少调度开销

    run(current_task_pid);

    } else {

    // 获取子就绪队列中,排在第一位的进程ID

    new_task_pid = ready_queue.sub_queue_array[current_priority].next.pid;

    // 在就绪队列中删除该进程

    ready_queue.sub_queue_array[current_priority].delete_first_node();

    // 更新优先级位图信息

    if (ready_queue.sub_queue_array[current_priority].next == null) {

    // 如该优先级子就绪队列无进程,则置相应位为0

    priority_bit_map[current_priority] = 0;

    }

    //交由处理机处理该进程

    run(new_task_pid);

    }

    在这里需要明确的是,run 函数在结束前,需要完成对该任务状态标识符 state 的修改。例如任务执行结束,则置为 PROCESS_STATE_COMPLETE 状态。

    按规定原则修改 PCB 内容

    我们来看一下,修改 PCB 内容流程图,本部分流程图是上文全局流程图中“修改进程状态”的子流程。

    c3f9d2ed11cb769c5b151f233a1e2635.png

    // 若该进程动态优先级 <= 3 则直接置为0

    if (pcbs[current_task_pid].dynamic_priority <= 3)

    pcbs[current_task_pid].dynamic_priority = 0;

    else

    pcbs[current_task_pid].dynamic_priority -= 3;

    // 修改该进程 PCB 的进程状态标识符

    pcbs[current_task_pid].state = PROCESS_STATE_RUN;

    按规定原则修改就绪队列

    在该进程用完时间片后,有多种情况:

    进程执行完毕,删除pcbs中的进程控制块,处理机继续执行下一进程;

    进程变为阻塞状态,进入阻塞队列,处理机继续执行下一进程;

    进程还需下一时间片,则优先级按规则调整,处理机继续执行下一进程;

    处理机继续执行下一进程,但就绪队列为空,处理机空闲等待。

    // 进程执行完毕

    if (pcbs[current_task_pid].state == PROCESS_STATE_COMPLETE) {

    delete_pcb(current_task_pid);

    }

    // 进程为阻塞状态

    if (pcbs[current_task_pid].state == PROCESS_STATE_WAIT) {

    insert_into_wait_queue(current_task_pid);

    }

    // 进程为就绪状态,还需下一时间片

    if (pcbs[current_task_pid].state == PROCESS_STATE_READY) {

    // 获取当前任务进程修改后的优先数

    new_priority = get_priority(current_task_pid);

    // 插入到该优先级子就绪队列的末尾

    ready_queue.sub_queue_array[new_priority].add_to_last();

    }

    进程调度模拟结果

    实例的就绪进程集参数如下表所示,其中 id 为进程标识号,static_priority 为进程静态优先级,dynamic_priority 为进程动态优先级,state 为进程状态,time_slice 为该进程需要的时间片数。

    | process_name | id | static_prioriy | dynamic_priority | state | time_slice |

    | :----: | :----:| :----:| :----:| :----:| :----:|

    | proc_a | 1 | 10 | 0 | ready | 5 |

    | proc_b | 2 | 10 | 5 | ready | 5 |

    | proc_c | 3 | 30 | 5 | ready | 5 |

    | proc_d | 4 | 10 | 20 | ready | 5 |

    下面,我们来模拟该实例的运行过程。

    714ba21679b713956e78cc8786f962f0.png

    从表中我们可以看到:

    在时间片 3 时,进程 C 的动态优先级为 2,小于等于 3,因此其动态优先级直接置为 0,静态优先级不改变,则后续该进程优先级保持为 30,这样的机制可以保证系统进程或用户重要进程不被过多降低优先级,保证其优先、及时地被执行;

    在时间片 9 时,进程 D 的优先级和进程 B 相等,在这种情况下,系统优先选择不改变当前进程的方式继续执行,这样的机制可以降低进程调度的开销;

    在时间片 11 时,进程 B 的情况与第 1 条一致;

    在时间片 13 时,由于进程 A 的初始动态优先级即为 0,因此在后续执行过程中该进程的优先级一直保持为静态优先级。

    结束语

    本文使用 C 语言对动态优先权的进程调度算法进行了设计和模拟实现。程序可实现动态的进行各个进程相关信息的录入,如 STATIC_PRIORITY、DYNAMIC_PRIORITY、STATE 等信息。并充分考虑了进程在执行过程中可能发生的多种情况,更好的体现了进程的就绪态、执行态、阻塞态三者之间的关系以及相互的转换。程序的运行过程清晰的体现了动态优先权的调度算法的执行过程,有利于加深对算法的理解和掌握。由于抢占式调度算法与硬件密切相关,由软件实现较困难,所以本方案实现的是非抢占式的动态优先权进程调度算法,抢占式的动态优先权进程调度算法的模拟实现有待于进一步研究。

    版权信息

    原创文章

    展开全文
  • python实现进程调度

    2019-12-29 14:45:18
    python模拟实现进程调度算法,先来先服务,短作业优先,静态高优先级优先,动态优先级优先,时间片轮转法
  • 输入因素(例如选择的调度算法进程的长度和进程的频率)将影响性能因素,例如CPU利用率,平均作业等待时间,平均作业响应时间和平均作业周转时间。 根据应用的不同,某些因素的重要性可能比其他因素更重。 例如,...
  • 进程优先级调度算法

    2018-06-22 18:49:01
    《计算机与操作系统(第四版)》进程优先级调度算法 1.时间片轮转调度算法 2.多级反馈队列调度算法 3.高响应比优先调度算法
  • C++实现优先进程调度算法源代码+实验报告:计算机操作系统课程综合性实验报告-进程调度算法程序设计。
  • 1.编写程序模拟动态优先级进程调度算法,初始设置模拟5个进程调度,假设每个进程可有四种状态,分别为ready, running, waiting及terminated状态,并假定初始状态为ready状态。 2、在优先级调度算法中,各个进程的...

    java语言实现的时间片轮转调度算法和动态优先级调度算法


    贪方便用java实现老师的作业,虽然写的乱七八糟的,但是也想发出来给人看看,评论喷我吧!。

    一、代码:

    作业要求是:时间片轮转调度
    1.编写程序模拟动态优先级进程调度算法,初始设置模拟5个进程调度,假设每个进程可有四种状态,分别为ready, running, waiting及terminated状态,并假定初始状态为ready状态。
    2、在优先级调度算法中,各个进程的优先数的初始值由随机函数给定,范围为4050的整数,每个进程所需的CPU运行时间亦由随机函数给定,范围为13的整数。每次进程调度时,从就绪队列中选择优先级最高的进程执行,进程每执行一次,该进程的优先数减3,占用的CPU时间加1,进程还需要的时间片数减1。
    3、在时间片轮转调度算法中,采用固定时间片2,即每执行一次进程,该进程的执行时间片数为已执行了2个单位(cputime+2),而进程尚须执行的时间(neededtime-2),进程已经执行的次数count+1,而进程的轮转次数round+1;

    //程序调用
    import java.util.Scanner;
    
    public class Client {
    	
    	private static Scanner str = new Scanner(System.in);
    	
    	//程序入口函数
    	public static void main(String[] args) {
    		menuChose();
    		int choose = str.nextInt();
    		switch (choose) {
    		case 1:
    			RunPriority();
    			break;
    		case 2:
    			roundCal();
    			break;
    		case 3:
    			break;
    		case 0:
    			System.out.println("程序结束运行");
    			break;
    		default:
    			break;
    		}
    	}
    	
    	public static void menuChose(){
    		System.out.println("CHOOSE THE ALGORITHM");
    		System.out.println("1   PRIORITY");
    		System.out.println("2   ROUNDBIN");
    		System.out.println("3   FIFS");
    		System.out.println("0 exit");
    	}
    	
    	public static void RunPriority(){
    		
    		PriorityCal pcb = new PriorityCal();
    		System.out.println("Priority scheduling,input name and needtime:");
    		pcb.input();
    		System.out.println("ready process queue");
    		pcb.showProcess();
    		System.out.println();
    		for(int i = 0;i<10;i++){
    			System.out.println("cputime="+(i+1));
    			pcb.judgeProcess();
    		}
    		System.out.println("all process have finished!");
    	}
    	
    	public static void roundCal(){
    		RoundCal cal = new RoundCal();
    		System.out.println("Priority scheduling,input name and needtime:");
    		cal.input();
    		System.out.println("ready process queue");
    		cal.showProcess();
    		int result = 0;
    		int num = 2;
    		for (int i = 1; i <= 10; i++) {
    			System.out.println("cputime="+(i*num));
    			if(result<3){
    				cal.roundTime(result);
    			}else{
    				result = 0;
    				cal.roundTime(result);	
    			}
    			result++;
    		}
    	}
    
    package demo;
    
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Random;
    import java.util.Scanner;
    
    public class PriorityCal {
    	
    	Scanner str= new Scanner(System.in);
    	
    	private List<ProcessObj>processList = new LinkedList<ProcessObj>();
    	private List<String> listStateCode = new LinkedList<String>();
        private Random rand = new Random();
    	
        //初始化状态码
    	public void initStateCode(){
    		listStateCode.add("ready");
    		listStateCode.add("running");
    		listStateCode.add("waiting");
    		listStateCode.add("terminated");
    	}
    	
    	//输入进程块
    	public void input(){
    		for(int i =0 ;i<5;i++){
    			System.out.println("输入第"+(i+1)+"进程的信息:");
    			ProcessObj obj = new ProcessObj();
    			obj.setName(str.next());
    			obj.setNeedtime(str.nextInt());
    			initStateCode();
    			obj.setState(listStateCode.get(0));
    			int value = rand.nextInt(11)+40;
    			obj.setPriority(value);	
    			processList.add(obj);
    			//System.out.println(obj.getName()+"\t"+obj.getNeedtime()+"\t"+obj.getPriority()+"\t"+obj.getState()+"\t"+obj.getCuptime());
    		}
    		
    	}
    	
    	//程序进程优先级运行
    	public int priorControl(){
    		/*
    		 * 读取prior数值最大的对象进cup调度
    		 */
    		int max = 0;
    		int i =0 ;
    		while(i<processList.size()){
    			if(!("terminated".equals(processList.get(i).getState()))){
    				int index = processList.get(max).getPriority()>=processList.get(i).getPriority()?max:i;
    				i= i+1;
    				max = index;
    			}else{
    				i=i+1;
    			}
    		}
    		return max;
    	}
    	
    	public void showProcess()
    	{
    		System.out.println("name  cuptime  needtime priority state");
    		for (ProcessObj obj : processList) {
    			System.out.println(obj.getName()+"\t"+obj.getCuptime()+"\t"+
    					obj.getNeedtime()+"\t"+obj.getPriority()+"\t"+obj.getState()
    					);
    		}
    	}
    	
    	public void judgeProcess(){
    		/*
    		 * 优先级-3 needtime-1 cputime+1 先到先运行策略
    		 * 可有四种状态,分别为ready, running, waiting及terminated状态,并假定初始状态为ready状态。
    		 * 运行时为 running needtime为0时 为 terminated
    		 */
    		
    		int maxPrior = priorControl();
    		ProcessObj tmp = processList.get(maxPrior);
    		
    		if(tmp.getNeedtime()>0){
    			tmp.setState(listStateCode.get(1));
    			int needtime = tmp.getNeedtime()-1;
    			int cputime = tmp.getCuptime()+1;
    			int priortime = tmp.getPriority()-3;
    			tmp.setCuptime(cputime);
    			tmp.setNeedtime(needtime);
    			tmp.setPriority(priortime);
    			processList.set(maxPrior, tmp);
    			showProcess();
    		}
    		
    		tmp.setState(listStateCode.get(2));
    		processList.set(maxPrior, tmp);
    		
    		if(tmp.getNeedtime()==0){
    			tmp.setState(listStateCode.get(3));
    			processList.set(maxPrior, tmp);
    		}
    	}
    	
    }
    
    package demo;
    
    public class ProcessObj {
    	private String name ;
    	private int cuptime = 0;
    	private int needtime;
    	private int priority;
    	private String state;
    	public ProcessObj(String name, int cuptime, int needtime, int priority,
    			String state) {
    		super();
    		this.name = name;
    		this.cuptime = cuptime;
    		this.needtime = needtime;
    		this.priority = priority;
    		this.state = state;
    	}
    	public ProcessObj() {
    		super();
    	}
    	public String getName() {
    		return name;
    	}
    	public void setName(String name) {
    		this.name = name;
    	}
    	public int getCuptime() {
    		return cuptime;
    	}
    	public void setCuptime(int cuptime) {
    		this.cuptime = cuptime;
    	}
    	public int getNeedtime() {
    		return needtime;
    	}
    	public void setNeedtime(int needtime) {
    		this.needtime = needtime;
    	}
    	public int getPriority() {
    		return priority;
    	}
    	public void setPriority(int priority) {
    		this.priority = priority;
    	}
    	public String getState() {
    		return state;
    	}
    	public void setState(String state) {
    		this.state = state;
    	}
    	
    }
    
    package demo;
    
    public class ReProcessObj {
    	
    	private String name ;
    	private int needtime;
    	private int cputime=0;
    	private String state;
    	private int round = 0;
    	private int count = 0;
    	
    	public String getName() {
    		return name;
    	}
    	public void setName(String name) {
    		this.name = name;
    	}
    	public int getNeedtime() {
    		return needtime;
    	}
    	public void setNeedtime(int needtime) {
    		this.needtime = needtime;
    	}
    	public int getCputime() {
    		return cputime;
    	}
    	public void setCputime(int cputime) {
    		this.cputime = cputime;
    	}
    	public String getState() {
    		return state;
    	}
    	public void setState(String state) {
    		this.state = state;
    	}
    	public int getRound() {
    		return round;
    	}
    	public void setRound(int round) {
    		this.round = round;
    	}
    	public int getCount() {
    		return count;
    	}
    	public void setCount(int count) {
    		this.count = count;
    	}
    	
    	public ReProcessObj(String name, int needtime, int cputime, String state, int round, int count) {
    		super();
    		this.name = name;
    		this.needtime = needtime;
    		this.cputime = cputime;
    		this.state = state;
    		this.round = round;
    		this.count = count;
    	}
    	
    	public ReProcessObj() {
    		super();
    	}
    	
    	@Override
    	public String toString() {
    		return  name + "\t" + cputime + "\t" + needtime + "\t" + round
    				+ "\t" + count + "\t" + state;
    		
    	}
    }
    
    
    package demo;
    
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Random;
    import java.util.Scanner;
    
    public class RoundCal {
    	private Scanner str= new Scanner(System.in);
    	private static int NUM = 3;
    	private  int cycle = 0;
    	
    	private List<ReProcessObj>processList = new LinkedList<ReProcessObj>();
    	private List<String> listStateCode = new LinkedList<String>();
        private Random rand = new Random();
        
        //初始化状态码
       	public void initStateCode(){
       		listStateCode.add("ready");
       		listStateCode.add("running");
       		listStateCode.add("waiting");
       		listStateCode.add("terminated");
       	}
       	
       	//输入进程块
       	public void input(){
       		for(int i =0 ;i<NUM;i++){
       			System.out.println("输入第"+(i+1)+"进程的信息:");
       			ReProcessObj obj = new ReProcessObj();
       			obj.setName(str.next());
       			int value = rand.nextInt(10)+1;
       			obj.setNeedtime(value);
       			initStateCode();
       			obj.setState(listStateCode.get(0));
       			processList.add(obj);
       			//System.out.println(obj.toString());
       		}		
       	}
       	
       	public void roundTime(int i){
       		
       		ReProcessObj obj = processList.get(i);
       		if(obj.getNeedtime()!=0){
       			int value = (obj.getNeedtime()-2)>0?(obj.getNeedtime()-2):0;
       	   		obj.setNeedtime(value);
       	   		obj.setCount((obj.getCount()+1));
       	   		obj.setRound((obj.getRound()+1));
       	   		obj.setCputime((obj.getCputime()+2));
       	   		obj.setState(listStateCode.get(1));
       	   		processList.set(i, obj);
       			showProcess();
       			if(obj.getNeedtime()==0){
       				obj.setState(listStateCode.get(3));
       			}else{
       				obj.setState(listStateCode.get(0));
       			}
    	   		processList.set(i, obj);
       			return;
       		}
       		
    		if(obj.getNeedtime()==0){
       			obj.setRound((obj.getRound()+1));
       			processList.set(i, obj);
       			showProcess();
       	   		}
       		
       	}
       	
       	public void showProcess()
    	{
    		System.out.println("name  cuptime  needtime  round  count  state");
    		for (ReProcessObj obj : processList) {
    			System.out.println(obj.toString());
    		}
    	}
    }
    

    二、程序运行演示

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    总结

    敲了一个下午终于完成了,还是有点高兴的。尝试了下用c++完成,不过是真的很难。指针和引用做着做着完全蒙了!希望看到的能指点下。
    展开全文
  • 动态优先级编程算法代码matlab 该项目已作为的任务完成。 请参阅和以获取原始作业。 我曾尝试在Markdown上复制论文,但它并不完美。 纸张的实际Word Doc也已在此处签入。 编译和用法 请运行“ make clean && make”...
  • 本文件包含完整的大作业完整的资源,包含c++源代码,可运行,有调度视频,有实验报告。
  • 一个最基本的实现..很多内容没有考虑,大家可以在这个基础上再添加自己需要的操作
  • 采用动态优先数。即进程的优先数在创建进程时可以给定一个初始值,并且可以按一定原则修改优先数:在进程获得一次CPU后就将其优先数...“最高优先数优先”调度算法的基本思想是把CPU分配给就绪队列中优先数最高的进程
  • 进程调度中采 用 FCFS 算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机, 使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机,特点是:算法比较 简单,可以...

    当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队 列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采 用 FCFS 算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机, 使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机,特点是:算法比较 简单,可以实现基本上的公平。

    2.短作业(进程)优先调度算法

    短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们 调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程, 将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重 新调度。该算法未照顾紧迫型作业。

    二 高优先权优先调度算法

    为了照顾紧迫型作业,使之在进入系统后便获得优先处理,引入了最高优先权优先(FPF)调度 算法。当把该算法用于作业调度时,系统将从后备队列中选择若干个优先权最高的作业装入内存。 当用于进程调度时,该算法是把处理机分配给就绪队列中优先权最高的进程。

    1.非抢占式优先权算法

    在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下 去,直至完成;或因发生某事件使该进程放弃处理机时。这种调度算法主要用于批处理系统中; 也可用于某些对实时性要求不严的实时系统中。

    2.抢占式优先权调度算法

    在这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只 要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程) 的执行,重新将处理机分配给新到的优先权最高的进程。显然,这种抢占式的优先权调度算法能 更好地满足紧迫作业的要求,故而常用于要求比较严格的实时系统中,以及对性能要求较高的批 处理和分时系统中。

    3.高响应比优先调度算法

    在批处理系统中,短作业优先算法是一种比较好的算法,其主要的不足之处是长作业的运行 得不到保证。如果我们能为每个作业引入前面所述的动态优先权,并使作业的优先级随着等待时 间的增加而以速率 a 提高,则长作业在等待一定的时间后,必然有机会分配到处理机。该优先权的 变化规律可描述为:

    558463291c017c8a32d4294c45953f50.png
    • (1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业。

    • (2) 当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务。

    • (3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高,从而也可获得处理机。简言之,该算法既照顾了短作业,又考虑了作业到达的先后次序,不会使长作业长期得不到服务。因此,该算法实现了一种较好的折衷。当然,在 利用该算法时,每要进行调度之前,都须先做响应比的计算,这会增加系统开销。

    三 基于时间片的轮转调度算法

    1.时间片轮转法

    在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度 时,把 CPU 分配给队首进程,并令其执行一个时间片。时间片的大小从几 ms 到几百 ms。当执行 的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行, 并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执 行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处 理机执行时间。

    原文 https://juejin.im/post/5ce4218e6fb9a07ee27aeafc

    e3a95d85fddb2d226290d0ff65ee01f8.png

    目前100000+人已关注加入我们

    99d63779cc84dec822ee725cfe721782.gif ce2c731608b1340f3aef8067043cff13.gif 3f7a94212406eba06c4af35b1d7d8eb6.gif e03ce54788f08319ec5ce46dcb48f14b.gif 85747d2d706146e035aaf509ce109da9.gif 4f22677c4b5496203263c57b78347f36.gif 4a5d3f7f4e30da1c4cb7eeecda621885.gif 4c30d099582aa6f4aaf08f2314d3820a.gif

    4b71ad9ab5fa984376adf217aec6e764.gif 9871ad4160d768a5b0ff1e8594cfc405.gif b22692f6494c99e5a9b1fe6ec958db59.gif 1ee6271e781404053feb76904cffef8e.gif 8471701d73ef62975cca407cb14aca15.gif c397e05065b1d1b9a0d7ebdedbc95322.gif 317de3011dccbc8c44f1d96744f546ab.gif 85747d2d706146e035aaf509ce109da9.gif

    展开全文
  • 试验名称:进程调度模拟算法 ...调度算法:采用最高优先数优先的调度算法。每个进程由一个进程控制块(PCB)表示。进程控制块可以包含以下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间,进程状态等。
  • 参考文章: ... 一、实验目的 在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态。...本实验模拟在单处理机情况下的进程调度,帮助学生加深了解进程调度的工作。 二、实验内容 设计一个按优先级.
  • 本实验可加深对进程调度算法的理解。(2)按照实验题目要求独立地、正确地完成实验内容(编写、调试算法程序,提交程序清单及相关实验数据与运行结果,完成个人实验报告)。(3)2020年6月5日以前提交本...
  • 模拟进程调度中的高优先级优先调度算法
  • 时间片轮转发加优先级进程调度算法如下: #include <stdio.h> struct PCB { int ID; int Alltime; int Cputime; int Priority; int starte; }; int maxpriorityxiabiao(PCB pcb[],int n) { int ...
  • 操作系统动态优先级调度算法C语言实现

    万次阅读 多人点赞 2018-05-27 10:48:53
    动态优先级算法 动态优先数是指在进程创建时先确定一个初始优先数, 以后在进程运行中随着进程特性的改变不断修改优先数,这样,由于开始优先数很低而得不到CPU的进程,就能因为等待时间的增长而优先数变为最高而...
  • 主要介绍了Python实现调度算法代码详解,具有一定参考价值,需要的朋友可以了解下。
  • 操作系统实验课程中进程优先级调度算法利用C语言实现程序
  • 操作系统实验--根据优先级模拟进程调度
  • 动态设置进程优先级,并设有延时函数 while(head!=NULL) { Output(&head); DeleteQueue(&head,&curr); curr.runtime--; curr.privilege++; if(curr.runtime!=0) { InsertQueue(&head,curr); } ...
  • 动态优先级算法(java实现)

    千次阅读 2019-11-02 14:13:53
    最近在学操作系统,老师的第一个实验要求——实现动态优先级进程调度算法。在度娘上也搜到了些,借鉴了一位大佬的设计思想,用java实现了简单的一个进程调度算法。 实验要求 1. 采用最高优先数的调度算法(即把处理...
  • 动态优先权进程调度算法

    千次阅读 2019-11-13 14:57:46
    动态优先权算法2.1菜单2.2加一个时间片的各个PCB的分配子函数2.2.1赋予各个PCB新的状态2.2.2运行状态的PCB P经历了一个时间片的分配状况 题目 代码 1.结构体及其操作 1.0结构体 typedef struct PCB* PCBPtr; ...
  • 算法流程图 六.运行结果 七.实验小结 一、实验目的 在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态。 当就绪进程个数大于处理器数时,就必须依照某种策略来决定哪些进程优先占用处理器。 本...
  • 实用标准文案 优 先 级 调 度 算 法 实 验 报 告 院系 * 学院 班级 * 姓名 * 学号 * 精彩文档 实用标准文案 一实验题目 优先级调度算法 二实验目的 进程调度是处理机管理的核心内容 本实验要求用高级语言编写 模拟...
  • 基于动态优先级进程调度算法 假定系统中有5个进程,每一个进程用一个进程控制块PCB来代表,进程控制块的格式为: 其中, 进程名——作为进程的标识,假设五个进程的进程名分别为P1,P2,P3,P4,P5。 指针——...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,819
精华内容 21,927
关键字:

动态优先级进程调度算法