我电操作系统上机实验题目（5\6）

作者: Your7Maxx | 来源:发表于2020-05-15 14:28 被阅读0次

第五题咕了，文件系统老师进度还没跟上呢。
第六题：

image.png

实验要求很明确了，老师建议选一个较小的角度点进行专题研究。我选择的是进程调度，因为关于进程调度问题产生了很多不同的调度算法，可以针对具体的调度算法，在比较各个调度算法的同时，可以深入理解进程调度的问题，一举两得。

先了解一下进程调度概念产生的背景把：

6.1 背景

在多道程序系统中,往往进程数目多于处理机数目,它们都要使用处理机运行自己的程序,所以处理机成为进程竞争的主要资源。操作系统进程管理的核心任务是为多个进程
合理地分配处理机资源,这就是处理机调度。因为处理机调度是面向进程的,所以又称进程调度。进程调度协调和控制各进程对CPU的使用,按照一定的调度原则和某种调度算法从就绪队列中选择个进程,把CPU分配给该进程运行。在操作系统中,完成进程调度功能的程序称为进程调度程序,实际上也就是处理机分配程序。操作系统中CPU资源管理是多道程序设计面临的挑战，进程调度就是有效地管理CPU资源。

6.2 功能

在系统运行过程中,由于多个进程都需要使用处理机,因此实施处理机分配的进程调度是系统中最频繁的工作。如,当占用处理机的运行态进程因等待某事件发生而主动
放弃处理机转换为等待态,或者进程运行的时间片到或优先级下降而转换为就绪态时,系统就必须将处理机实施再分配,这将引起进程的调度。此外,进程正常结束也将引起进程的调度。因此,进程调度是操作系统核心的重要组成部分。

进程调度的主要功能包括

(1)记录当前进程的情况,如进程名、指令计数器、状态寄存器及所有通用寄存器等现场信息,将这些信息记录在它的进程控制块PCB中。
(2)根据一定的调度算法,从就绪队列中选择一个进程获得处理机。
(3)进程上下文切换。

ps：！进程调度≠作业调度

之前我一直将进程调度和作业调度两个概念混为一谈，其实这两者完全是不同的操作行为，除了不同之外，他们彼此间甚至还相互配合实现一些功能。以下是我对两者的一个理解：
首先作业调度在逻辑上应该在进程调度之前，作业调度按一定的算法从磁盘上的“输入井”中选择资源能得到满足的作业装入内存，使作业有机会去占用处理器执行（注意是有机会）。但是，一个作业能否占用处理器，什么时间能够占用处理器，必须由进程调度来决定。所以，作业调度选中了一个作业且把它装入内存时，就应为该作业创建一个进程，若有多个作业被装入内存，则内存中同时存在多个进程，这些进程的初始状态为就绪状态，然后，由进程调度来选择当前可占用处理器的进程，进程运行中由于某种原因状态发生变化，当它让出处理器时，进程调度就再选另一个作业的进程运行。因此，作业调度与进程调度相互配合才能实现多道作业的并行执行。

6.3 进程调度方式

进程调度方式是指当一个进程在处理机上运行时,若有某个更为紧迫或更为重要的进程需要运行处理应如何分配处理机。进程调度方式通常有两种:剥夺调度和非剥夺调度。

1、可剥夺调度方式

可剥夺调度方式又称可抢占方式,这种方式分为两种情况。一种情况是当进程正占用处理机运行时,如果系统中出现更为“紧迫或重要”的进程,则立即停止正在运行的进程,将其转换为就绪状态,然后把处理机分配给更为“紧迫或重要”的进程。通常,进程的紧迫或重要程度由进程的优先级确定。另一个情况是运行态进程已用完系统规定地使用处理机的时间片，系统将中止该进程的运行，将其转换为就绪状态，然后把处理机分配给下一个就绪进程。这两种情况都是由系统强行“剥夺”运行态进程对处理机的使用权，所以称为可剥夺调度方式。

剥夺原则：

（1）优先级原则：优先级高rank优先级低的
（2）短进程有限原则：到达的进程比正在执行的进程明显短，将剥夺长进程的执行。
（3）时间片原则：每个进程被分配一个同样的时间片，时间片用完之后重新调度。
（4）强制性剥夺：极重要的进程或人工干预，强制引起调度。

2、非剥夺调度方式

顾名思义，与可剥夺调度方式对应，通俗点讲，除非进程自己放弃自己在处理机上的机会，否则系统不能剥夺对其处理机的使用权。但是这种方式虽然减少了系统进程调度的次数，简化了程序的设计，但是系统的性能也随之变差了，特别是可能发生由于一个进程的错误而导致整个系统瘫痪的局面。

6.4进程调度的原则

进程调度的原则包括：
（1）公平性原则：应保证每个进程获得合理的cpu份额，不要导致某些进程长期占用cpu，某些进程长期等待cpu。
（2）有效性原则：cpu资源应得到最大限度到的利用。
（3）友好性原则：响应时间快，与用户交互的时间应尽可能地短
（4）快捷性原则：周转时间短，批处理作业的处理时间尽可能地短。
（5）广泛性原则：吞吐量大，单位时间内完成的作业尽可能的多。

6.5 进程调度算法：

进入到重点动手操作并讨论的算法部分了。
根据老师在课上的教学内容可知，进程调度的算法种类很多，每个算法都有各自的优缺点，很难完全准确的去比较各个算法。这里采用计算平均周转时间和平均带权周转的方式来进行量化比较。
首先说明几个概念：
1、周转时间：作业完成时间−作业提交时间
（特别注意作业提交时间不是作业进内存的时间，而是发出请求，提交就开始计时，如果无法排进内存，那么就等待，等待的这部分时间也要计数）
2、平均周转时间：作业1的周转时间+...+作业n的周转时间/n
3、带权周转时间：作业周转时间/作业实际运行时间
4、平均带权周转时间：作业1的带权周转时间+...+作业n的带权周转时间/n
（老师好像没讲带权周转时间，所以主要还是用平均周转时间来比较）

算法一：先来先服务调度算法（FCFS）

几乎每一种调度的算法，不管是进程调度还是作业调度还是其他什么调度，第一个引进的一般都是FCFS，因为这是最简单的一种调度算法。在进程调度中采用FCFS算法时，则每次调度从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程在运行的过程中不会被抢占，直到运行完成或发生某个事件而阻塞后才放弃处理机。

FCFS算法的流程图（手画的比较丑。）：

image.png

FCFS算法的核心实现代码:

/*FCFS算法核心实现代码*/
void fcfs(){
    int k=0;            //每次选出即将服务的进程 
    int l=0;            //本次服务的进程 
    int Atimer=0;       //周转时间之和
    float timer=0;      //带权周转时间之和 
    //每次开始之前Check数组要全部置0
    memset(Check,0,sizeof(Check));
    k=Select0(Arival,n);
    Start[k]=Arival[k];
    End[k]=Start[k]+Go[k];
    Timer[k]=End[k]-Arival[k];
    DTimer[k]=(float)Timer[k]/Go[k];
    printf("作业  提交时间  运行时间  开始时间  结束时间  周转时间  带权周转时间\n");
    for(int m=0;m<n;m++){
        l=k;
        k=Select0(Arival,n);
        Start[k]=End[l];
        End[k]=Start[k]+Go[k];
        Timer[k]=End[k]-Arival[k];
        DTimer[k]=(float)Timer[k]/Go[k];
        Atimer=Timer[l]+Atimer;
        timer=timer+DTimer[l];
        printf(" %s     %2d        %2d         %2d        %2d        %2d         %.2f\n",name[l],Arival[l],Go[l],Start[l],End[l],Timer[l],DTimer[l]);
    }
    printf("平均周转时间:%.2f\n",(float)Atimer/n);
    printf("平均带权周转时间:%.2f\n",(float)timer/n);
}

算法二：短进程优先调度算法（SPF）

短作业优先调度算法SJF，是指对短作业或短进程优先调度的算法。可分别作用于作业调度和进程调度。短作业优先调度是从后备队列中选择一个或若干个估计运行时间最短的作业，将他们调入内存运行。而短进程（SJF）则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行完成，或发生某事件而被阻塞放弃处理机再重新调度。SPF算法能有效降低进程的平均等待时间，提高系统的吞吐量。

SPF算法的流程图：

image.png

SP(J)F算法的核心实现代码:

/*SP(J)F调度算法*/
void sjf(){
    int k=0;            //每次选出即将服务的进程 
    int l=0;            //本次服务的进程 
    int Atimer=0;       //周转时间之和
    float timer=0;      //带权周转时间之和 
    int localtime=0;    //当前时间 
    //每次开始之前Check数组要全部置0
    memset(Check,0,sizeof(Check));
    Start[k]=Arival[k];
    End[k]=Start[k]+Go[k];
    Timer[k]=End[k]-Arival[k];
    DTimer[k]=(float)Timer[k]/Go[k];
    localtime=End[k];
    Check[k]=1;
    printf("作业  提交时间  运行时间  开始时间  结束时间  周转时间  带权周转时间\n");
    for(int m=0;m<n;m++){
        l=k;
        k=Select1(Go,n,localtime);
        Start[k]=End[l];
        End[k]=Start[k]+Go[k];
        Timer[k]=End[k]-Arival[k];
        DTimer[k]=(float)Timer[k]/Go[k];
        localtime=End[k];
        Atimer=Timer[l]+Atimer;
        timer=timer+DTimer[l];
        printf(" %s     %2d        %2d         %2d        %2d        %2d         %.2f\n",name[l],Arival[l],Go[l],Start[l],End[l],Timer[l],DTimer[l]);
    }
    printf("平均周转时间:%.2f\n",(float)Atimer/n);
    printf("平均带权周转时间:%.2f\n",(float)timer/n);
}

将算法一和二结合起来比较：

#include<stdio.h>
#include<string.h> 
#include <stdlib.h>
#define N 10                //允许最大进程个数
#define M 100               //进程名长度 
int n;                      //进程个数 
char name[N][M];            //进程名 
int Arival[N]={0};          //到达时间 
int Go[N]={0};              //运行时间 
int Start[N]={0};           //开始时间 
int End[N]={0};             //结束时间 
int Timer[N]={0};           //周转时间 
float DTimer[N]={0};        //带权周转时间 
int Check[N]={0};           //判断作业是否完成，完成值为1
/*输入函数*/
void input(){
    //为测试方便，采用输入重定义处理
    //每次读取当前文件夹下in.txt文件
    // 若文件不存在，则手动输入 
    int i;
    FILE *fin;  
    if((fin=fopen("in.txt","rb"))==NULL){
        printf("进程的个数:");
        scanf("%d",&n);
        for(i=0;i<n;i++){
            printf("进程名：");
            scanf("%s",&name[i]);
            printf("第%d个进程的到达时间:",i+1);
            scanf("%d",Arival+i);
            printf("第%d个进程的运行时间:",i+1);
            scanf("%d",Go+i);
        }
    }
    else{
        for(i=0;!feof(fin);i++){
            fscanf(fin,"%s",&name[i]);
            fscanf(fin,"%d",Arival+i);
            fscanf(fin,"%d",Go+i);
        }  
        n=i; 
    } 
}
 /**选出先到达的作业 
 *a[] 到达时间 
 *n 进程个数 
 **/
int Select0(int a[],int n){
    int i=0;
    for(int k=0;k<n;k++){
        if(Check[k]==0){
            i=k;
            break;
        }
    }
    for(int j=0;j<n;j++){
        if(a[i]>a[j]&&Check[j]==0){
            i=j;
        }
    }
    Check[i]=1;
    return i;
}
/*先来先服务调度算法*/
void fcfs(){
    int k=0;            //每次选出即将服务的进程 
    int l=0;            //本次服务的进程 
    int Atimer=0;       //周转时间之和
    float timer=0;      //带权周转时间之和 
    //每次开始之前Check数组要全部置0
    memset(Check,0,sizeof(Check));
    k=Select0(Arival,n);
    Start[k]=Arival[k];
    End[k]=Start[k]+Go[k];
    Timer[k]=End[k]-Arival[k];
    DTimer[k]=(float)Timer[k]/Go[k];
    printf("作业  提交时间  运行时间  开始时间  结束时间  周转时间  带权周转时间\n");
    for(int m=0;m<n;m++){
        l=k;
        k=Select0(Arival,n);
        Start[k]=End[l];
        End[k]=Start[k]+Go[k];
        Timer[k]=End[k]-Arival[k];
        DTimer[k]=(float)Timer[k]/Go[k];
        Atimer=Timer[l]+Atimer;
        timer=timer+DTimer[l];
        printf(" %s     %2d        %2d         %2d        %2d        %2d         %.2f\n",name[l],Arival[l],Go[l],Start[l],End[l],Timer[l],DTimer[l]);
    }
    printf("平均周转时间:%.2f\n",(float)Atimer/n);
    printf("平均带权周转时间:%.2f\n",(float)timer/n);
}
/**选出短作业 
 *a[] 运行时间 
 *n 进程个数 
 *local 当前时间 
 **/
int Select1(int a[],int n,int local){
    int i=0;
    for(int k=0;k<n;k++){
        if(Check[k]==0){
            i=k;
            break;
        }
    }
    for(int j=0;j<n;j++){
        if(a[i]>a[j]&&Check[j]==0&&Arival[j]<=local){
            i=j;
        }
    }
    Check[i]=1;
    return i;
}
/*短作业优先调度算法*/
void sjf(){
    int k=0;            //每次选出即将服务的进程 
    int l=0;            //本次服务的进程 
    int Atimer=0;       //周转时间之和
    float timer=0;      //带权周转时间之和 
    int localtime=0;    //当前时间 
    //每次开始之前Check数组要全部置0
    memset(Check,0,sizeof(Check));
    Start[k]=Arival[k];
    End[k]=Start[k]+Go[k];
    Timer[k]=End[k]-Arival[k];
    DTimer[k]=(float)Timer[k]/Go[k];
    localtime=End[k];
    Check[k]=1;
    printf("作业  提交时间  运行时间  开始时间  结束时间  周转时间  带权周转时间\n");
    for(int m=0;m<n;m++){
        l=k;
        k=Select1(Go,n,localtime);
        Start[k]=End[l];
        End[k]=Start[k]+Go[k];
        Timer[k]=End[k]-Arival[k];
        DTimer[k]=(float)Timer[k]/Go[k];
        localtime=End[k];
        Atimer=Timer[l]+Atimer;
        timer=timer+DTimer[l];
        printf(" %s     %2d        %2d         %2d        %2d        %2d         %.2f\n",name[l],Arival[l],Go[l],Start[l],End[l],Timer[l],DTimer[l]);
    }
    printf("平均周转时间:%.2f\n",(float)Atimer/n);
    printf("平均带权周转时间:%.2f\n",(float)timer/n);
} 
void menu(){
    int choice;
    while(1){
        printf("*******请选择调度算法*******\n\t1、先来先服务\n\t2、短作业优先\n\t0、退出\n请输入：");
        scanf("%d",&choice);
        if(choice==0){
            break;
        }
        else if(choice==1){
            fcfs();
        }
        else if(choice==2){
            sjf(); 
        }
        else{
            printf("输入有误!\n");      
        }
        
    }   
}
int main(){
    input();
    menu();
    return 0;
}

首先设置五个作业的提交时间和所需要的运行时间：

image.png

编译：

gcc -o FCFS_SJFpthread FCFS_SJFpthread.c

发现报错：

image.png

google查看相关的报错信息知道了，是c语言的标准问题，该编译器不是c99标准，不支持for(int ..;;)的代码格式。
两种解决办法：
（1）修改代码：int ..;for(..;;)
（2）指定c99标准：

gcc -o FCFS_SJFpthread FCFS_SJFpthread.c -std=c99

编译成功。
运行：

./FCFS_SJFpthread

运行截图：
1、FCFS:

image.png

2、SPF：

image.png
可以发现SPJ算法的平均周转时间小于FCFS，是吞吐量得到提高。
改变数据再次进行验证测试：

image.png

1、FCFS：

image.png
2、SPF：

image.png

算法三：多级反馈队列调度算法（MLFQ）

为什么不把算法三和上边两个算法在一起比较的原因是算法三我个人认为是所有进程调度算法中最合理有效的一个，它既能使高优先级的作业得到响应又能使短作业（进程）迅速完成，所以想着重分析下。

一、原理：

1、设有N个队列（Q1,Q2....QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，优先级Priority(Q1) > Priority(Q2) > ... > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其他的队列。
2、对于优先级最低的队列来说，里面是遵循时间片轮转法。也就是说，位于队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法，每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列。
3、各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个问题)。

二、流程图：

image.png

三、MLFQ调度算法实现代码：

#include <stdio.h>   
#include <stdlib.h>   
#include <string.h>   
typedef struct node                         /*进程节点信息*/  
{   
char name[20];                             /*进程的名字*/  
int prio;                                  /*进程的优先级*/  
int round;                                 /*分配CPU的时间片*/  
int cputime;                               /*CPU执行时间*/  
int needtime;                            /*进程执行所需要的时间*/  
char state;              /*进程的状态，W——就绪态，R——执行态，F——完成态*/  
int count;                             /*记录执行的次数*/  
struct node *next;                      /*链表指针*/  
}PCB;   
typedef struct Queue                 /*多级就绪队列节点信息*/  
{   
PCB *LinkPCB;                      /*就绪队列中的进程队列指针*/  
int prio;                            /*本就绪队列的优先级*/  
int round;                           /*本就绪队列所分配的时间片*/  
struct Queue *next;                  /*指向下一个就绪队列的链表指针*/  
}ReadyQueue;   
PCB *run=NULL,*finish=NULL;     /*定义三个队列，就绪队列，执行队列和完成队列*/  
ReadyQueue *Head = NULL;                   /*定义第一个就绪队列*/  
int num;                                   /*进程个数*/  
int ReadyNum;                           /*就绪队列个数*/  
void Output();                           /*进程信息输出函数*/  
void InsertFinish(PCB *in);       /*将进程插入到完成队列尾部*/  
void InsertPrio(ReadyQueue *in);     /*创建就绪队列，规定优先数越小，优先级越低*/  
void PrioCreate();                       /*创建就绪队列输入函数*/  
void GetFirst(ReadyQueue *queue);     /*取得某一个就绪队列中的队头进程*/  
void InsertLast(PCB *in,ReadyQueue *queue);   /*将进程插入到就绪队列尾部*/  
void ProcessCreate();                       /*进程创建函数*/  
void RoundRun(ReadyQueue *timechip);     /*时间片轮转调度算法*/  
void MultiDispatch();             /*多级调度算法，每次执行一个时间片*/  
  
int main(void)   
{   
PrioCreate();                         /*创建就绪队列*/  
ProcessCreate();                      /*创建就绪进程队列*/  
MultiDispatch();                      /*算法开始*/  
Output();                             /*输出最终的调度序列*/  
return 0;   
}   
void Output()                        /*进程信息输出函数*/  
{   
ReadyQueue *print = Head;   
PCB *p;   
printf("进程名\t轮数\tcpu时间\t需要时间\t进程状态\n");   
while(print)   
{   
  if(print ->LinkPCB != NULL)   
  {   
   p=print ->LinkPCB;   
   while(p)   
   {   
    printf("%s\t%d\t%d\t%d\t\t%c\n",p->name,p->round-1,p->cputime,p->needtime,p->state);      
    p = p->next;   
   }   
  }   
  print = print->next;   
}   
p = finish;   
while(p!=NULL)   
{   
  printf("%s\t%d\t%d\t%d\t\t%c\n",p->name,p->round-1,p->cputime,p->needtime,p->state);   
  p = p->next;   
}   
p = run;   
while(p!=NULL)   
{   
  printf("%s\t%d\t%d\t%d\t\t%c\n",p->name,p->round-1,p->cputime,p->needtime,p->state,p->count);   
  p = p->next;   
}   
  
  
}   
void InsertFinish(PCB *in)           /*将进程插入到完成队列尾部*/  
{   
PCB *fst;   
fst = finish;   
  
if(finish == NULL)   
{   
  in->next = finish;   
  finish = in;   
}   
else  
{   
  while(fst->next != NULL)   
  {   
   fst = fst->next;   
  }   
  in ->next = fst ->next;   
  fst ->next = in;   
}   
}   
void InsertPrio(ReadyQueue *in)  /*创建就绪队列，规定优先数越小，优先级越低*/  
{   
ReadyQueue *fst,*nxt;   
fst = nxt = Head;   
  
if(Head == NULL)                  /*如果没有队列，则为第一个元素*/  
{   
  in->next = Head;   
  Head = in;   
}   
else                               /*查到合适的位置进行插入*/  
{   
  if(in ->prio >= fst ->prio)     /*比第一个还要大，则插入到队头*/  
  {   
   in->next = Head;   
   Head = in;   
  }   
  else  
  {   
   while(fst->next != NULL)  /*移动指针查找第一个别它小的元素的位置进行插入*/  
   {   
    nxt = fst;   
    fst = fst->next;   
   }   
      
   if(fst ->next == NULL)  /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即可*/  
   {   
    in ->next = fst ->next;   
    fst ->next = in;   
   }   
   else                 /*插入到队列中*/  
   {   
    nxt = in;   
    in ->next = fst;   
   }   
  }   
}   
}   
void PrioCreate()               /*创建就绪队列输入函数*/  
{   
ReadyQueue *tmp;   
int i;   
printf("**********多级反馈队列调度算法**********\n");  
printf("请输入就绪队列的个数：\n");   
scanf("%d",&ReadyNum);   
  
printf("请分别输入每个就绪队列的CPU时间片：\n");   
for(i = 0;i < ReadyNum; i++)   
{   
  if((tmp = (ReadyQueue *)malloc(sizeof(ReadyQueue)))==NULL)   
  {   
   perror("malloc");   
   exit(1);   
  }   
  scanf("%d",&(tmp->round));   /*输入此就绪队列中给每个进程所分配的CPU时间片*/  
  tmp ->prio = 50 - tmp->round;  /*设置其优先级，时间片越高，其优先级越低*/  
  tmp ->LinkPCB = NULL;          /*初始化其连接的进程队列为空*/  
  tmp ->next = NULL;   
  InsertPrio(tmp);            /*按照优先级从高到低，建立多个就绪队列*/  
}   
}   
void GetFirst(ReadyQueue *queue)     /*取得某一个就绪队列中的队头进程*/  
{   
run = queue ->LinkPCB;   
  
if(queue ->LinkPCB != NULL)   
{   
  run ->state = 'R';   
  queue ->LinkPCB = queue ->LinkPCB ->next;   
  run ->next = NULL;   
}   
}   
void InsertLast(PCB *in,ReadyQueue *queue)   /*将进程插入到就绪队列尾部*/  
{   
PCB *fst;   
fst = queue->LinkPCB;   
  
if( queue->LinkPCB == NULL)   
{   
  in->next =  queue->LinkPCB;   
  queue->LinkPCB = in;   
}   
else  
{   
  while(fst->next != NULL)   
  {   
   fst = fst->next;   
  }   
  in ->next = fst ->next;   
  fst ->next = in;   
}   
}   
void ProcessCreate()                  /*进程创建函数*/  
{   
PCB *tmp;   
int i;   
  
printf("请输入进程的个数：\n");   
scanf("%d",&num);   
printf("请输入进程名字和进程所需时间：\n");   
for(i = 0;i < num; i++)   
{   
  if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)   
  {   
   perror("malloc");   
   exit(1);   
  }   
  scanf("%s",tmp->name);   
  getchar();                        /*吸收回车符号*/  
  scanf("%d",&(tmp->needtime));   
  tmp ->cputime = 0;   
  tmp ->state ='W';   
  tmp ->prio = 50 - tmp->needtime;  /*设置其优先级，需要的时间越多，优先级越低*/  
  tmp ->round = Head ->round;   
  tmp ->count = 0;   
  InsertLast(tmp,Head);           /*按照优先级从高到低，插入到就绪队列*/  
}   
}   
void RoundRun(ReadyQueue *timechip)    /*时间片轮转调度算法*/  
{   
  
int flag = 1;   
  
GetFirst(timechip);   
while(run != NULL)   
{   
  while(flag)   
  {   
   run->count++;   
   run->cputime++;   
   run->needtime--;   
   if(run->needtime == 0)            /*进程执行完毕*/  
   {   
    run ->state = 'F';   
    InsertFinish(run);   
    flag = 0;   
   }   
   else if(run->count == timechip ->round)         /*时间片用完*/  
   {   
    run->state = 'W';   
    run->count = 0;                /*计数器清零，为下次做准备*/  
    InsertLast(run,timechip);   
    flag = 0;   
   }   
  }   
  flag = 1;   
  GetFirst(timechip);   
}   
}   
void MultiDispatch()           /*多级调度算法，每次执行一个时间片*/  
{    
int flag = 1;   
int k = 0;   
  
ReadyQueue *point;   
point = Head;   
  
GetFirst(point);   
while(run != NULL)   
{   
  Output();   
  if(Head ->LinkPCB!=NULL)   
   point = Head;   
  while(flag)   
  {   
   run->count++;   
   run->cputime++;   
   run->needtime--;   
   if(run->needtime == 0)          /*进程执行完毕*/  
   {   
    run ->state = 'F';   
    InsertFinish(run);   
    flag = 0;   
   }   
   else if(run->count == run->round)       /*时间片用完*/  
   {   
    run->state = 'W';   
    run->count = 0;                /*计数器清零，为下次做准备*/  
    if(point ->next!=NULL)   
    {   
     run ->round = point->next ->round;/*设置其时间片是下一个就绪队列的时间片*/  
     InsertLast(run,point->next);  /*将进程插入到下一个就绪队列中*/  
     flag = 0;   
    }   
    else  
    {   
     RoundRun(point);       /*如果为最后一个就绪队列就调用时间片轮转算法*/  
     break;   
    }   
   }   
   ++k;   
   if(k == 3)   
   {   
    ProcessCreate();   
   }   
  }   
  flag = 1;   
  if(point ->LinkPCB == NULL)          /*就绪队列指针下移*/  
   point =point->next;   
  if(point ->next ==NULL)   
  {   
   RoundRun(point);   
   break;   
  }   
  GetFirst(point);   
}   
}

四、运行示例：

编译：

gcc -o MLFQpthread MLFQpthread.c

运行：

./MLFQpthread

运行过程：

image.png

笔算演示过程结果：

image.png

由上可得代码有效性。

总结

本次实验是针对进程调度这一块的知识点形成了一份专题报告，报告内容包含背景知识、概念说明、算法实现等等，重点在于对进程调度算法的分析和理解，关于进程调度的算法还有很多，如时间片轮转法、动态优先级法等，本次实验就三个比较典型的进程调度算法进行了总结和分析，并尝试去模拟算法进行实验，分析了各自的平均周转时间和优缺点。同时，也提高了自己代码审计和动手解决问题的能力，并借助搜索引擎如goole、github等，来帮助自己完成专题报告的相应部分，总的来说，是一次很好锻炼自己针对操作系统进程调度专题理解的实践过程。

参考

https://blog.csdn.net/wojiuguowei/article/details/82788535
https://blog.csdn.net/u011240016/article/details/53199183/
https://blog.csdn.net/sj_wl/article/details/80831031
https://blog.csdn.net/yangquanhui1991/article/details/47446151
https://www.cnblogs.com/bajdcc/p/4707746.html
https://blog.csdn.net/qq_41381716/article/details/80854229

我电操作系统上机实验题目（5\6）

6.1 背景

6.2 功能

进程调度的主要功能包括

ps：！进程调度≠作业调度

6.3 进程调度方式

1、可剥夺调度方式

剥夺原则：

2、非剥夺调度方式

6.4进程调度的原则

6.5 进程调度算法：

算法一：先来先服务调度算法（FCFS）

FCFS算法的流程图（手画的比较丑。）：

FCFS算法的核心实现代码:

算法二：短进程优先调度算法（SPF）

SPF算法的流程图：

SP(J)F算法的核心实现代码:

算法三：多级反馈队列调度算法（MLFQ）

一、原理：

二、流程图：

三、MLFQ调度算法实现代码：

四、运行示例：

总结

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读