精华内容
下载资源
问答
  • 对进程进行调度
    千次阅读
    2018-10-16 20:58:25

    一、进程调度

    1.题目内容

    1.1 设计目的

    进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用CPU的方法。在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。本设计模拟在单处理器情况下的进程调度,目的是加深对进程调度工作的理解,掌握不同调度算法的优缺点。

     

    2.题目要求

    设计程序模拟单处理机系统中的进程调度算法,在短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中选择两种实现。

    每个进程由一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等。

    进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。进程的到达时间为进程输入的时间。

    进程的运行时间以时间片为单位进行计算。

    每个进程的状态可以是就绪W(Wait)、运行R(Run)或完成F(Finish)3中状态之一。

     

    3.设计思想

    短作业优先调度算法思想

    在非抢占式的调度算法中,最先到达的进程最先运行,在进程进行的时候,到达的进程之间就要进行运行时间的比较,运行时间依次从少到多排列,最短运行时间的先运行,每次只能运行一个进程,每当进程运行时,每次到达的新进程都跟等待状态的进程进行比较,进程根据运行时间排序,直到所有进程都到达,所有的进程都运行完结束就打印结果。

     

    4.算法分析

    4.1 程序结构

    在执行主函数的时候,选择短作业优先调度算法或者最高优先级优先算法,利用if语句来判断执行什么函数。

     

    4.1.1 短作业优先调度算法

    调用void input(PCB *a,int n)函数,从键盘输入进程的信息,然后调用void qiushu(PCB *a,int n)函数,在qiushu函数中,依次调用void compare(PCB *a,int n),void run(PCB *a,int n) ,void output(PCB *a,int n) 。

    在void compare(PCB *a,int n)中,

    ①先利用冒泡排序按照提交时间的早晚排序得到a[],先执行最先到达的进程a[0];

    ②在进程执行完之前比较已经到达的进程的运行时间,依次按照运行时间的多少根据从小到大排列得到序列,a[0]完成后执行当前最小运行时间的进程a[1];

    ③再执行②,直到所有进程执行完。

    在void run(PCB *a,int n)中,

    求出运行进程的开始时间,完成时间,周转时间,带权周转时间。

    第一个进程的开始时间为它的提交时间,其他的进程都为上一个进程的完成时间;

    完成时间=开始时间+运行时间;

    周转时间=完成时间-提交时间;

    带权周转时间=周转时间/运行时间。

    在void output(PCB *a,int n)中,

    输出进程的运行顺序以及进程运行的具体信息。

     

     

    4.2 数据结构

    建立结构体来记录进程的基本信息。

    struct PCB{              //定义结构体

    int jcxh;            //进程号

    double tjtime;       //提交时间

    double yxtime;       //运行时间

    double startime;     //开始时间

    double finishtime;   //完成时间

    double zztime;       //周转时间

    double dqzztime;     //带权周转时间

    int prior;           //优先级数

    double RunTime;      //已占用cpu时间

    char state;          //进程状态    

    struct PCB* next;    //创建指针

    };

    PCB a[10]; 最高只能有十个进程

     

     

    5.核心代码

     

    struct PCB{              //定义结构体

    int jcxh;            //进程号

    double tjtime;       //提交时间

    double yxtime;       //运行时间

    double startime;     //开始时间

    double finishtime;   //完成时间

    double zztime;       //周转时间

    double dqzztime;     //带权周转时间

    int prior;           //优先级数

    double RunTime;      //已占用cpu时间

    char state;          //进程状态    

    struct PCB* next;    //创建指针

    };

    PCB a[10];               //最多十个进程数

     

    //排序   

    void compare(PCB *a,int n)   

    {  

    int i,j,m;

    for(i=0;i<n-1;i++)   

    for(j=i+1;j<=n-1;j++)   

    if(a[i].tjtime>a[j].tjtime)   

                 {   

                     PCB b;   

                     b=a[i];   

                     a[i]=a[j];   

                     a[j]=b;   

                 }

    for(m=0;m<n-1;m++)      

    {

    if(m==0)   

    a[m].finishtime=a[m].tjtime+a[m].yxtime;   

    else  

    a[m].finishtime=a[m-1].finishtime+a[m].yxtime;

    int l,q=0;

    for(l=m+1;l<=n-1;l++)   

    {

    if(a[l].tjtime<=a[m].finishtime)              

    q++;   

    }   

    double min=a[m+1].yxtime;   

    int next=m+1;//m+1=n   

    for(int k=m+2;k<=m+q;k++)          

    {  

    if(a[k].yxtime<min)  

    {

    min=a[k].yxtime;              

    next=k;}                             

    }        

    PCB c;               

         c=a[m+1];              

    a[m+1]=a[next];              

    a[next]=c;          

    }   

    }   

    me=a[i].zztime/a[i].yxtime;//求出带权周转时间

    }

    }   

    void output(PCB *a,int n)   

    {

    int i;

    printf("使用短作业算法后进程的运行顺序:");

    for(i=0;i<n;i++)

    {if(i==0)printf("%d",a[i].jcxh);

    else printf("--->%d",a[i].jcxh);

    }

    printf("\n");

    printf("进程名   提交时间   运行时间   开始时间   完成时间   周转时间   带权周转时间\n");

    for(i=0;i<n;i++)

    {

    printf("   %d       %.2lf       %.2lf       %.2lf       %.2lf\t%.2lf\t   %.2lf\n",a[i].jcxh,a[i].tjtime,a[i].yxtime,a[i].startime,a[i].finishtime,a[i].zztime,a[i].dqzztime);

    }

    }            

     

    7.心得体会

    在短作业优先调度算法中,实现并不难。从键盘输入进程信息,再进而比较每个的提交时间,先执行最先来到的进程,再根据运行时间的大小,选择短作业的优先进入cpu。

     

     

     

    更多相关内容
  • 1.编写并调试一个模拟的进程调度程序,采用“最高优先数优先”调度算法五个进程进行调度。 2、用“简单轮转法调度算法”实现第一题
  • 操作系统实验代码
  • (1)编写并调试一个模拟的进程调度程序,采用“最高优先数优先”调度算法五个进程进行调度。 (2)编写并调试一个模拟的进程调度程序,采用“轮转法”调度算法五个进程进行调度。 轮转法可以是简单轮转法、可变...

    实验描述: 用高级语言编写和调试一个进程调度程序,以加深对进程的概念及进程调度算法的理解。

    1. 设计简单的进程PCB 结构,完成进程信息记录;
    2. 设计一个有 N个进程并发执行的进程调度程序(以下三选一)
      (1)编写并调试一个模拟的进程调度程序,采用“最高优先数优先”调度算法对五个进程进行调度。
      (2)编写并调试一个模拟的进程调度程序,采用“轮转法”调度算法对五个进程进行调度。 轮转法可以是简单轮转法、可变时间片轮转法,或多队列轮转法。
      (3)编写并调试一个模拟的进程调度程序,采用“短进程优先”调度算法对五个进程进行调度。
    3. 完成设计的调度算法的测试
      使用下表进程(几乎同时到达)作为测试数据完成设计的调度算法的测试,输出各个进程的周转时间和带权周转时间,计算并输出平均周转时间和平均带权周转时间。
    进程名处理时间优先级
    A32
    B61
    C43
    D54
    E25

    一、设计简单的进程PCB 结构,完成进程信息记录;

    //定义一个结构体:PCB
    typedef struct PCB{   
    	char processName[10]; //进程名
    	float arriveTime; //到达时间  
    	float serviceTime; //服务时间
    	float startTime;   //开始执行时间
    	float finishTime; //结束时间
    	float turnroundTime;   //周转时间
    	float weightedTurnaroundTime; //带权周转时间
    }pcb;
    

    二、进程调度算法描述

      进程调度算法:采用短进程(短作业)优先调度算法。即从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行,短作业优先调度算法从就绪队列中选择一个估计运行时间最短的进程,将处理机分配给它,使之立即执行,直到完成或发生某事件而阻塞时,才释放处理机。

    三、参考代码及测试

    完整代码如下:

    #include <stdlib.h>
    #include <stdio.h>
     
    //定义一个结构体:PCB
    typedef struct PCB{   
    	char processName[10]; //进程名
    	float arriveTime; //到达时间  
    	float serviceTime; //服务时间
    	float startTime;   //开始执行时间
    	float finishTime; //结束时间
    	float turnroundTime;   //周转时间
    	float weightedTurnaroundTime; //带权周转时间
    }pcb; 
     
    //输入进程信息,将N个进程的信息写入PCB型数组
    void input(pcb *p,int N)   
    {
    	int i;   
    	printf("\n"); 
    	printf("请输入进程的名字  到达时间  服务时间:  (例如: A 0 100)\n");
     
    	for(i=0; i <= N-1; i++)   
    	{   
    		printf("请输入进程%d的信息:", i+1);
    		scanf("%s", &p[i].processName);	
    		scanf("%f", &p[i].arriveTime);
    		scanf("%f", &p[i].serviceTime);	 
    	}   
    }
       
    //对服务先后优先级排序
    void sort(pcb *p, int N)   
    {   
    	
    	/*
    	1、对pcb型数组中的元素进行一个简单的排序
    	找到优先级最高的进程
    	并把其他进程也进行简单排序,方便后续工作
    	*/
    	//排序: N次循环,每次找到从i到N-1中优先级最高的进程,放到p[i]
    	for(int i=0;i<=N-1;i++)  
    	{
    		//循环比较剩余的变量    //排序后:从0~N-1  arriveTime增加 , arriveTime相同时, serviceTime短的优先 
    		for(int j=i+1;j<N;j++) 
    		{
    			if(p[i].arriveTime>p[j].arriveTime || (p[i].arriveTime==p[j].arriveTime && p[i].serviceTime>p[j].serviceTime) )   
    			{  
    				//p[j]的优先级高于p[i],因此把p[j]放到p[i]
    				pcb temp;   
    				temp = p[i];   
    				p[i] = p[j];   
    				p[j] = temp;   
                 } 
    		}
    	}
    
    	//2、每个进程运行完成之后,找到当前时刻已经到达的最短进程P[0]优先级最高,
    	for(int m=0; m<N-1; m++)      
    	{
    		if(m == 0)   
    			p[m].finishTime = p[m].arriveTime + p[m].serviceTime;   
    		else
    			p[m].finishTime = ((p[m-1].finishTime >= p[m].arriveTime)? p[m-1].finishTime: p[m].arriveTime) + p[m].serviceTime;
    		//(1)找到p[m].finishTime时刻哪些进程已经到达
    		int i=0;  //i统计 p[m].finishTime时刻有几个进程已经到达
    		//从下一个进程p[m+1]开始寻找
    		for(int n = m+1; n <= N-1; n++)   
    		{
    			if(p[n].arriveTime <= p[m].finishTime)              
    				i++;   
    			else
    				break;
    			    /*由于在第1步已经对进程按照到达时间进行了排序
    			      故:当p[n].arriveTime > p[m].finishTime时,
    				      说明p[n]进程和其后面的其他进程都未到达。
    				i的值为p[m].finishtime时刻已经到达的进程数目。
    			   */
    		}  
    		//(2)找到p[m].finishTime时刻已经到达的最短进程
    		float min = p[m+1].serviceTime;   //next进程服务时间为p[m+1].serviceTime (初值) 
    		int next = m+1;                   //next进程为m+1 (初值) 
    		//p[m+1]至p[m+i]这i个已到达进程中找到最短进程
    		for(int k = m+1; k < m+i; k++)       //k为m+1 ~ m+i-1   
    		{   
    			//min的初值是p[m+1].serviceTime, k+1为m+2 ~m+i 
    			if(p[k+1].serviceTime < min)   
    			{
    				min = p[k+1].serviceTime;              
    				next = k+1;
    			}                              
    		}  
    		//(3)把最短进程放在p[m+1]进程处
    		pcb temp;               
    		temp=p[m+1];              
    		p[m+1]=p[next];              
    		p[next]=temp;           
    	}    
    } 
      
    //运行
    void run(pcb *p, int N)   
    {
    	int k; 
    	//计算各进程的开始时间和结束时间
    	for(k=0; k <= N-1; k++)   
         {            
    		if(k==0) //第1个进程   
    		{     
    			p[k].startTime = p[k].arriveTime; //第1个进程到达之后即可执行   
    			p[k].finishTime = p[k].startTime + p[k].serviceTime; 
    		}    
    		else 
    		{    
    			p[k].startTime = (p[k-1].finishTime >= p[k].arriveTime)? p[k-1].finishTime: p[k].arriveTime;    
    			p[k].finishTime = p[k].startTime + p[k].serviceTime;
    		}    
    	} 
    	//计算各进程的周转时间和带权周转时间
    	for(k=0; k<=N-1; k++)   
    	{        
    		p[k].turnroundTime = p[k].finishTime - p[k].arriveTime;   
    		p[k].weightedTurnaroundTime = p[k].turnroundTime / p[k].serviceTime;   
         }   
    }  
     
    //打印结果
    void Print(pcb *p, int N)   
    {
    	int k;      
    	printf("\n调用最短进程优先算法以后进程运行的顺序是: ");
    	printf("%s",p[0].processName); 
    	for(k=1;k<N;k++)   
    	{
    		printf("-->");		
    		printf("%s", p[k].processName); 
    	}    
    	printf("\n"); 
    	printf("具体进程调度信息:\n");
    	printf("进程名  到达时间  服务时间  开始时间  结束时间  周转时间  带权周转时间\n");
    	for(k=0; k<=N-1; k++)        
    	{	
    		printf("%4s", p[k].processName);
    		printf("%10.3f", p[k].arriveTime);	
    		printf("%10.3f", p[k].serviceTime);
    		printf("%10.3f", p[k].startTime);
    		printf("%10.3f", p[k].finishTime);
    		printf("%10.3f", p[k].turnroundTime);
    		printf("%10.3f\n", p[k].weightedTurnaroundTime);
    	}         
    }  
      
    //短进程优先
    void sjff(pcb *p,int N)   
    {
    	sort(p, N);                 
    	run(p, N);         
    	Print(p, N);  
    	int k;
    	float atTime = 0; // 平均周转时间 
    	float AQTTime = 0; //平均带权周转时间 
    	for(k=0; k<=N-1; k++)    
         {   
    		atTime += p[k].turnroundTime;  
    		AQTTime += p[k].weightedTurnaroundTime;		
         }  
    	atTime = atTime/N; 
    	AQTTime = AQTTime/N;
    	printf("\n调用短进程优先算法的平均周转时间为:");
    	printf("%.3f\n", atTime);
    	printf("调用短进程优先算法的平均带权周转时间为:");
    	printf("%.3f\n", AQTTime);      
    }   
     
    
    int main()   
    { 
    	
    	pcb a[50]; 
    	int N;  //进程数目                    		
    	printf("\n");                          			
    	printf("\n");	
    	printf("输入进程数目:");
    	scanf("%d", &N);                 		
    	input(a, N);  		
    	sjff(a, N);
    	return 0; 
    }   
    
    

    测试结果:
    在这里插入图片描述

      由于数据给出的到达时间几乎相同,不能较好的测试短进程优先,以及在不同到达时间的作业调度情况,那么请看下面的一组测试数据:
    在这里插入图片描述
      再次调试程序,发现我们程序运行结果还是不错的。
    在这里插入图片描述

    展开全文
  • C语言实现:短进程优先-进程调度算法 1. 采用“短进程优先”调度算法五个进程进行调度。每个进程有一个进程控制块( PCB)表示。进程控制块可以包含如下信息:进程名、到达时间、需要运行时间、已用CPU时间、进程...
  • 进程调度算法模拟 专业 XXXXX 学号 XXXXX 姓名 XXX 实验日期 20XX 年 XX 月 XX 日 一实验目的 通过对进程调度算法的模拟加深进程概念和进程调度算法的理解 二实验要求 编写程序实现 5 个进程的调度模拟 要求至少...
  • 随机生成进程信息并进行模拟调度,会显示出相应调度方法下的各个时间片进程调度安排(图表)。共四种调度方法:时间片轮转调度,优先数调度,最短进程优先,最短剩余时间优先。内含实验报告。
  • 编写一个单处理机下的进程调度程序,模拟操作系统进程的调度。 要求: 能够创建指定数量的进程,每个进程由一个进程控制块表示。 实现先来先服务调度算法:进程到达时间可由进程创建时间表示。 实现短作业...
  • 通过对进程调度算法的模拟,进一步理解进程的基本概念,加深进程运行状态和进程调度过程、调度算法的理解。 (1) 用C、C++、Java语言编程实现5个进程采用动态优先权调度算法进行调度的过程。数据如下: 5个进程...
  • 进程调度算法,模拟进程,进行调度算法的运行!
  • 进程调度

    千次阅读 2021-05-13 11:15:39
    首先,在《进程与线程基础》一文中,我们已经了解到: 进程是资源分配的基本单位; 线程是CPU调度的基本单位。 一个单核CPU在某一时刻只能允许一个线程执行,但是现在的计算机总是有一大堆进/线程等待执行。这就...

    更多文章分享在个人微信公众号:极客熊猫
    欢迎扫码关注:
    在这里插入图片描述
    在这里插入图片描述

    调度的概念

    首先,在《进程与线程基础》一文中,我们已经了解到:

    • 进程是资源分配的基本单位;
    • 线程是CPU调度的基本单位。

    一个单核CPU在某一时刻只能允许一个线程执行,但是现在的计算机总是有一大堆进/线程等待执行。这就需要某种规则来决定处理这些进/线程的顺序,这就是调度要研究的问题。

    回忆之前提到的进程状态:

    在这里插入图片描述

    运行态:当前正在占有CPU的进/线程;

    就绪态:具备运行条件,等待系统分配CPU的进/线程;

    阻塞态:不具备运行条件,正在等待某外部事件发生的进/线程。

    所谓进程调度,就是指在处于就绪态的一堆进/线程里,按照一定的调度算法,选出一个进/线程并给它分配CPU时间让它运行,从而实现多进程/多线程的并发执行。

    进程调度与线程调度尽管有些不同,但大部分是相同的,本文仅关注二者共同的部分。

    进程切换的基本流程:

    1. 首先用户态必须切换到内核态;
    2. 保存当前进程的状态,包括在其PCB中保存CPU各寄存器值,以便日后重新执行;
    3. 调度算法选定一个新进程;
    4. 新进程的内存地址空间重新装入MMU(内存管理单元);
    5. 新进程开始执行。

    调度目标

    所有系统

    对于所有系统,都应该有以下调度目标:

    • 公平——给每个进程公平的CPU份额;
    • 策略强制执行——保证规定的调度策略被执行;
    • 平衡——保证系统的所有部分都在忙碌。

    批处理系统

    批处理系统更适合非抢占式调度算法(见下文),应有以下调度目标:

    • 吞吐量——每小时最大作业数;
    • 周转时间——从提交到终止的最短时间;
    • CPU利用率——保持CPU始终忙碌。

    交互式系统

    交互式系统更适合抢占式调度算法(见下文),应有以下调度目标:

    • 响应时间——快速响应请求;
    • 均衡性——满足用户的期望。

    实时系统

    对于实时系统,应有以下调度目标:

    • 满足截止时间——避免丢失数据;
    • 可预测性——如多媒体系统中避免品质降低。

    调度算法

    进程调度的核心自然是调度规则,即各种调度算法。

    计算机都有一个硬件时钟,也叫RTC或CMOS,它独立于操作系统,由主板上一块电池供电的芯片,所以即使计算机断电,RTC也可以维持时间。这个硬件时钟会周期性的发出时钟中断。

    根据如何处理时钟中断,可以把调度算法分为两类:

    • 非抢占式调度算法:发生时钟中断时不调度;
    • 抢占式调度算法:通过时钟中断使CPU控制权返回给调度程序,进而调度其它进程。

    非抢占式调度算法:正在运行的进程只有在该进程执行完成或发生阻塞(如I/O请求)的情况下才会释放CPU;

    抢占式调度算法:分给进程的时间片耗尽之后,无论当前进程有没有执行完成,调度程序均选择其他进程执行。

    非抢占式调度算法

    先来先服务

    先来先服务算法(FCFS):按照进程请求CPU的顺序调度它们。

    意思就是,所有的就绪状态的进程在一个队列中,申请使用CPU的进程按照先来后到的顺序排在队列尾部,每执行完一个进程,系统就从该队列的头部取出第一个进程来执行。

    优点

    • 易于理解且算法实现简单;

    缺点

    • 对短进程不利。排在长进程后面的短进程需要等待很长时间,短进程的响应时间可能会很长。

    最短作业优先

    最短作业优先算法(SJF):每次调度时选择当前已到达的、且运行时间最短的作业。

    优点

    • 对比FCFS,平均等待时间、平均周转时间、平均带权周转时间均有提高;

    缺点

    • 需提前掌握各作业的运行时间;

    • 对长作业不利。因为如果一直有短作业到来,那么长作业永远得不到调度,长作业有可能会饿死,处于一直等待短作业执行完毕的状态。

    周转时间:从进程请求CPU到进程执行完毕为止的统计平均时间。

    非抢占式优先级调度

    优先级调度:每个进程被赋予一个优先级,允许优先级最高的可运行进程先运行。

    对于非抢占式优先级调度,当一个进程到达就绪队列时,比较它的优先级与当前运行进程的优先级。如果新到达进程的优先级高于当前运行进程的优先级,非抢占优先级调度算法只是将新的进程加到就绪队列的头部,而不会进行进程切换。

    缺点

    • 若有源源不断的高优先级进程到来,低优先级进程会导致饥饿。

    抢占式调度算法

    最短剩余时间优先

    最短剩余时间优先(SRTN):当一个新的进程到达时,把它所需要的整个运行时间与当前进程的剩余运行时间作比较。如果新的进程需要的时间更少,则挂起当前进程,运行新的进程,否则新的进程等待。

    优点

    • 可以使新的短进程得到良好的服务。

    缺点

    • 需提前掌握各进程的运行时间;
    • 对长进程不利。

    最短剩余时间优先(SRTN)是最短作业优先的抢占式版本。

    轮转调度

    轮转调度(RR):每个进程被分配一个时间段,称为时间片,即允许该进程在该时间段内运行。如果在时间片结束时该进程还在运行,则剥夺其CPU并分配给另一个进程;如果该进程在时间片结束前阻塞或结束,则立即进行进程切换。

    轮转调度算法对每个进程都一视同仁,就好比大家都排好队,一个一个来,每个人都运行一会儿再接着重新排队等待运行。

    在这里插入图片描述

    优点

    • 易理解且算法易实现;
    • 可以兼顾长进程和短进程。

    缺点

    • 平均等待时间较长,频繁上下文切换比较费时;

    • 时间片的长度选取困难。

    时间片设置的太短会导致过多的进程切换,降低CPU效率;

    时间片设置的太长又可能会引起对短的交互请求的响应时间变长。

    通常时间片设为20-50ms是一个较合理的折中。

    抢占式优先级调度

    优先级调度:每个进程被赋予一个优先级,允许优先级最高的可运行进程先运行。

    优先级调度的问题在于高优先级进程可能无休止地运行下去,对此有两种解决方案:

    • 调度程序可能在每个时钟中断降低当前进程的优先级。如果调整后该进程的优先级低于次高优先级的进程,则进行进程切换。
    • 给每个进程赋予一个允许运行的最大时间片,时间片耗尽,次高优先级的进程就获得运行机会。

    优先级有静态赋予动态赋予两种方式。

    静态赋予即在创建进程时人为确定进程的优先级,并且规定它在进程的整个运行期间保持不变;

    动态赋予即在创建进程时赋予该进程一个初始优先级,然后系统根据进程的执行情况的变化而不断改变其优先级,以便获得更好的调度性能。

    对于抢占式优先级调度,当一个进程到达就绪队列时,比较它的优先级与当前运行进程的优先级。如果新到达进程的优先级高于当前运行进程的优先级,那么抢占式优先级调度算法就会进行进程切换,让新到的高优先级进程运行。

    多级反馈队列

    多级反馈队列:在系统中设置多个就绪队列,并为每个队列赋予不同的优先级,从第一个开始逐个降低。不同队列中的进程所赋予的执行时间也不同,优先级越高,时间片越小。

    • 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程,则调度次优先级队列中的进程;

    • 对于同一个队列中的各个进程,按照时间片轮转调度

    • 当一个进程用完分配的时间片后,它被移到低一级优先级队列。

    彩票调度

    彩票调度:为进程提供各种系统资源(如CPU时间)的彩票。一旦要做出调度决策时,就随机抽取一张彩票,拥有该彩票的进程则获得该资源。

    为了增加重要进程“中彩票”的机率,可以给它们额外的彩票。

    公平分享调度

    公平分享调度:考虑进程的拥有者是谁,保证每个用户公平的分享CPU。

    之前的调度算法都不关注进程所有者是谁。这样做的结果是,如果用户1启动9个进程而用户2启动1个进程,使用轮转或相同优先级调度算法,那么用户1将得到90%的CPU时间,而用户2只得到10%的CPU时间。

    展开全文
  • 编写程序实现5个进程调度模拟,要求至少采用两种不同的调度算法分别进行模拟调度
  • os 作业调度与进程调度算法

    千次阅读 2022-01-18 14:07:35
    os 作业调度算法与进程调度算法

    作业调度

    先来先服务(FCFS)和短作业优先(SJF)调度算法

    先来先服务(first-come first-served,FCFS)调度算法

    FCFS是最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,系统将按照作业到达的先后次序来进行调度,或者说它是优先考虑在系统中等待时间最长的作业,而不管该作业所需执行时间的长短,从后备作业队列中选择几个最先进入该队列的作业,将它们调入内存,为它们分配资源和创建进程。然后把它放入就绪队列。
    当在进程调度中采用 FCFS 算法时,每次调度是从就绪的进程队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后,进程调度程序才将处理机分配给其它进程。
    顺便说明, FCFS 算法在单处理机系统中已很少作为主调度算法,但经常把它与其它调度算法相结合使用,形成一种更为有效的调度算法。例如,可以在系统中按进程的优先级设置多个队列,每个优先级一个队列,其中每一个队列的调度都基于 FCFS 算法。


    短作业优先(short job first,SJF)

    由于在实际情况中,短作业(进程)占有很大比例,为了能使它们能比长作业优先执行,而产生了短作业优先调度算法。
    1)短作业优先算法
    SJF 算法是以作业的长短来计算优先级,作业越短,其优先级越高作业的长短是以作业所要求的运行时间来衡量的。 SJF 算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时,它将从外存的作业后备队列中选择若干个估计运行时间最短的作业,优先将它们调入内存运行,
    2)短作业优先算法的缺点
    SJF 调度算法较之 FCFS 算法有了明显的改进,但仍然存在不容忽视的缺点:
    (1)必须预知作业的运行时间。在采用这种算法时,要先知道每个作业的运行时间。即使是程序员也很难准确估计作业的运行时间,如果估计过低,系统就可能按估计的时间终止作业的运行,但此时作业并未完成,故一般都会偏长估计。
    (2)对长作业非常不利,长作业的周转时间会明显地增长。更严重的是,该算法完全忽视作业的等待时间,可能使作业等待时间过长,出现饥饿现象。
    (3)在采用 SJF 算法时,人-机无法实现交互
    (4)该调度算法完全未考虑作业的紧迫程度,故不能保证紧迫性作业能得到及时处理


    优先级调度算法和高响应比优先调度算法

    优先级调度算法(priority-scheduling algorithm,PSA)

    我们可以这样来看作业的优先级,对于先来先服务调度算法,作业的等待时间就是作业的优先级,等待时间越长,其优先级越高。对于短作业优先调度算法,作业的长短就是作业的优先级,作业所需运行的时间越短,其优先级越高。但上述两种优先级都不能反映作业的紧迫程度。而在优先级调度算法中,则是基于作业的紧迫程度,由外部赋予作业相应的优先级,调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。优先级调度算法可作为作业调度算法,也可作为进程调度算法。当把该算法用于作业调度时,系统是从后备队列中选择若干个优先级最高的作业装入内存。


    高相应比优先调度算法(Highest Response Ratio Next,HRRN)

    在批处理系统中, FCFS 算法所考虑的只是作业的等待时间,而忽视了作业的运行时间。而 SJF 算法正好与之相反,只考虑作业的运行时间,而忽视了作业的等待时间。高响应比优先调度算法则是既考虑了作业的等待时间,又考虑作业运行时间的调度算法,因此既照顾了短作业,又不致使长作业的等待时间过长,从而改善了处理机调度的性能。
    高响应比优先算法是如何实现的呢?如果我们能为每个作业引入一个动态优先级,即优先级是可以改变的,令它随等待时间延长而增加,这将使长作业的优先级在等待期间不断地増加,等到足够的时间后,必然有机会获得处理机。该优先级的变化规律可描述为:
    在这里插入图片描述
    由于等待时间与服务时间之和就是系统对该作业的响应时间,故该优先级又相当于响应比Rp。据此,优先又可表示为:
    在这里插入图片描述
    由上式可以看出:

    • 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而类似SJF算法,有利于短作业。
    • 当要求服务的时间相同时,作业的优先级又决定于其等待时间,因而算法又类似于FCFS算法。
    • 对于长作业的优先级,可以随等待时间的增加而提高,当其等待时间足够长时,也获得处理机。

    因而该算法实现了较好的折中。当然在利用该算法时,每次要进行调度前,都需要先做相应比的计算,显然会增加系统开销。


    进程调度

    进程调度方式:

    • 非抢占方式(Nonpreemptive Mode)
      在采用这种调度方式时,一旦把处理机分配给某进程后,就一直让它运行下去,决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机,直至该进程完成,或发生某事件而被阻塞时,才把处理机分配给其它进程。
      在采用非抢占调度方式时,可能引起进程调度的因素可归结为:
      ①正在执行的进程运行完毕,或因发生某事件而使其无法再继续运行;
      ②正在执行中的进程因提出 I/O 请求而暂停执行;
      ③在进程通信或同步过程中,执行了某种原语操作,如 Block 原语。
      这种调度方式的优点是实现简单,系统开销小,适用于大多数的批处理系统。但它不能用于分时系统和大多数实时系统
    • 抢占方式( Preemptive Mode )
      这种调度方式允许调度程序根据某种原则,去暂停某个正在执行的进程,将己分配给该进程的处理机重新分配给另一进程。在现代 OS 中广泛采用抢占方式,这是因为:对于批处理机系统,可以防止一个长进程长时间地占用处理机,以确保处理机能为所有进程提供更为公平的服务。在分时系统中,只有采用抢占方式才有可能实现人-机交互。在实时系统中,抢占方式能满足实时任务的需求。但抢占方式比较复杂,所需付出的系统开销也较大。
      “抢占”不是一种任意性行为,必须遵循一定的原则。主要原则有:
      优先权原则,指允许优先级高的新到进程抢占当前进程的处理机,即当有新进程到达时,如果它的优先级比正在执行进程的优先级高,则调度程序将剥夺当前进程的运行,将处理机分配给新到的优先权高的进程。
      短进程优先原则,指允许新到的短进程可以抢占当前长进程的处理机,即当新到达的进程比正在执行的进程(尚须运行的时间)明显短时,将处理机分配给新到的短进程。
      时间片原则,即各进程按时间片轮转运行时,当正在执行的进程的一个时间片用完后,便停止该进程的执行而重新进行调度。

    轮转调度算法

    在分时系统中,最简单也是较常用的是基于时间片的轮转( round robin , RR )调度算法。该算法采取了非常公平的处理机分配方式,即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有 n 个进程,则每个进程每次大约都可获得1/n的处理机时间。

    1.轮转法的基本原理

    在轮转( RR )法中,系统根据 FCFS 策略,将所有的就绪进程排成一个就绪队列,并可设置每隔一定时间间隔(如30 ms )即产生一次中断,激活系统中的进程调度程序,完成一次调度,将 CPU 分配给队首进程,令其执行。当该进程的时间片耗尽或运行完毕时,系统再次将 CPU 分配给新的队首进程(或新到达的紧迫进程)。由此,可保证就绪队列中的所有进程在一个确定的时间段内,都能够获得一次 CPU 执行。

    2.进程切换时机

    在 RR 调度算法中,应在何时进行进程的切换,可分为两种情况:
    ①若一个时间片尚未用完,正在运行的进程便已经完成,就立即激活调度程序,将它从就绪队列中删除,再调度就绪队列中队首的进程运行,并启动一个新的时间片。
    ②在一个时间片用完时,计时器中断处理程序被激活。如果进程尚未运行完毕,调度程序将把它送往就绪队列的末尾。

    3.时间片大小的确定

    在轮转算法中,时间片的大小对系统性能有很大的影响。若选择很小的时间片,将有利于短作业,因为它能在该时间片内完成但时间片小,意味着会频繁地执行进程调度和进程上下文的切换,这无疑会增加系统的开销。反之,若时间片选择得太长,且为使每个进程都能在一个时间片内完成, RR 算法便退化为 FCFS 算法,无法满足短作业和交互式用户的需求。一个较为可取的时间片大小是略大于一次典型的交互所需要的时间使大多数交互式进程能在一个时间片内完成,从而可以获得很小的响应时间。图3-2示出了时间片大小对响应时间的影响,其中图( a )是时间片略大于典型交互的时间,而图( b )是时间片小于典型交互的时间。
    在这里插入图片描述
    图3-3示出了时间片分别为 q =1和 q =4时对平均周转时间的影响。
    在这里插入图片描述


    优先级调度算法

    在时间片轮转调度算法中,做了一个隐含的假设,即系统中所有进程的紧迫性是相同的。但实际情况并非如此。为了能满足实际情况的需要,在进程调度算法中引入优先级,而形成优先级调度算法。

    1.优先级调度算法的类型

    优先级进程调度算法,是把处理机分配给就绪队列中优先级最高的进程。这时,又进一步把该算法分成如下两种。
    (1)非抢占式优先级调度算法。该算法规定,一旦把处理机分配给就绪队列中优先级最高的进程后,该进程便一直执行下去直至完成,或者因该进程发生某事件而放弃处理机时,系统方可将处理机重新分配给另一优先级最高的进程。
    (2)抢占式优先级调度算法。把处理机分配给优先级最高的进程,使之执行。但在其执行期间,只要出现了另一个其优先级更高的进程,调度程序就将处理机分配给新到的优先级最高的进程。因此,在采用这种调度算法时,每当系统中出现一个新的就绪进程i时,就将其优先级 Pj 与正在执行的进程 j 的优先级巳进行比较,如果 P i≤ Pj ,原进程 Pj ,便继续执行;但如果是 Pi > Pj ,则立即停止 Pj 的执行,进行进程切换,使 i 进程投入执行。抢占式的优先级调度算法常用于对实时性要求较高的系统中。

    2.优先级的类型

    优先级调度算法的关键在于:应如何确定进程的优先级,以及确定是使用静态优先级还是动态优先级。
    1)静态优先级
    静态优先级是在创建进程时确定的,在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的,例如0~255中的某一整数,又把该整数称为优先数。确定进程优先级大小的依据有如下三个;
    (1)进程类型。通常系统进程(如接收进程、对换进程)的优先级高于一般用户进程的优先级。
    (2)进程对资源的需求对资源要求少的进程应赋予较高的优先级
    (3)用户要求根据进程的紧迫程度及用户所付费用的多少确定优先级
    静态优先级法简单易行,系统开销小,但不够精确,可能会出现优先级低的进程长期没有被调度的情况
    2) 动态优先级
    动态优先级是指在创建进程之初,先赋予其一个优先级,然后其值随进程的推进或等待时间的增加而改变,以便获得更好的调度性能。例如,可以规定在就绪队列中的进程随其等待时间的增长,使其优先级相应提高。若所有的进程都具有相同优先级初值,则最先进入就绪队列的进程会因其优先级变得最高,而优先获得处理机,这相当于 FCFS 算法。若所有的就绪进程具有各不相同的优先级初值,那么对于优先级初值低的进程,在等待了足够的时间后,也可以获得处理机。当采用抢占式调度方式时,若再规定当前进程的优先级随运行时间的推移而下降,则可防止一个长作业长期地垄断处理机。


    多队列调度算法

    如前所述的各种调度算法,尤其在应用于进程调度时,由于系统中仅设置一个进程的就绪队列,即低级调度算法是固定的、单一的,无法满足系统中不同用户对进程调度策略的不同要求,在多处理机系统中,这种单一调度策略实现机制的缺点更显突出,由此,多级队列调度算法能够在一定程度上弥补这一缺点。
    该算法将系统中的进程就绪队列从一个拆分为若干个将不同类型或性质的进程固定分配在不同的就绪队列,不同的就绪队列采用不同的调度算法,一个就绪队列中的进程可以设置不同的优先级,不同的就绪队列本身也可以设置不同的优先级
    多队列调度算法由于设置多个就绪队列,因此对每个就绪队列就可以实施不同的调度算法,因此,系统针对不同用户进程的需求,很容易提供多种调度策略。
    在多处理机系统中,该算法由于安排了多个就绪队列,因此,很方便为每个处理机设置一个单独的就绪队列。这样,不仅对每个处理机的调度可以实施各自不同的调度策略,而且对于一个含有多个线程的进程而言,可以根据其要求将其所有线程分配在一个就绪队列,全部在一个处理机上运行。再者,对于一组需要相互合作的进程或线程而言,也可以将它们分配到一组处理机所对应的多个就绪队列,使得它们能同时获得处理机并行执行。


    多级反馈队列(multileved feedback queue)调度算法

    前面介绍的各种用于进程调度的算法都有一定的局限性。如果未指明进程长度,则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而下述的多级反馈队列调度算法则不必事先知道各种进程所需的执行时间,还可以较好地满足各种类型进程的需要,因而它是目前公认的一种较好的进程调度算法。

    1.调度机制

    多级反馈队列调度算法的调度机制可描述如下:
    (1)设置多个就绪队列。在系统中设置多个就绪队列,并为每个队列赋予不同的优先级。第一个队列的优先级最高,第二个次之,其余队列的优先级逐个降低。该算法为不同队列中的进程所赋予的执行时间片的大小也各不相同,在优先级愈高的队列中,其时间片就愈小。例如第二个队列的时间片要比第一个的时间片长一倍,……,第i+1个队列的时间片要比第 i 个的时间片长一倍。图3-4是多级反馈队列算法的示意图。
    在这里插入图片描述
    (2)每个队列采用FCFS算法。当新进程进入内存后,首先将它放入第一队列的末尾,按 FCFS 原则等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可撤离系统,否则,即它在一个时间片结束时尚未完成,调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,依此类推。当进程最后被降到第 n 队列后,在第 n 队列中便采取按 RR 方式运行
    (3)按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行,仅当第一队列空闲时才调度第二队列中的进程运行:换言之,仅当第1~( i - I )所有队列均空时,才会调度第 i 队列中的进程运行如果处理机正在第 i 队列中为某进程服务时又有新进程进入任一优先级较高的队列,此时须立即把正在运行的进程放回到第 i 队列的末尾,而把处理机分配给新到的高优先级进程

    2.调度算法的性能

    在多级反馈队列调度算法中,如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时,便能较好地满足各种类型用户的需要
    (1)终端型用户。由于终端型用户提交的作业多属于交互型作业,通常较小,系统只要能使这些作业在第一队列规定的时间片内完成,便可使终端型用户感到满意。
    (2)短批处理作业用户。对于这类作业,如果可在第一队列中执行完成,便获得与终端型作业一样的响应时间。对于稍长的短作业,也只需在第二和第三队列各执行一时间片完成,其周转时间仍然较短。
    (3)长批处理作业用户。对于长作业,它将依次在第1,2,…,n 个队列中运行,然后再按轮转方式运行,用户不必担心其作业长期得不到处理。


    基于公平原则的调度算法

    以上介绍的几种调度算法所保证的只是优先运行,如优先级算法是优先级最高的作业优先运行,但并不保证作业占用了多少处理机时间。另外也未考虑到调度的公平性。本小节将介绍两种相对公平的调度算法。

    1.保证调度算法

    保证调度算法是另外一种类型的调度算法,它向用户所做出的保证并不是优先运行,而是明确的性能保证,该算法可以做到调度的公平性。一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有 n 个相同类型的进程同时运行,为公平起见,须保证每个进程都获得相同的处理机时间1/n。在实施公平调度算法时系统中必须具有这样一些功能:
    (1)跟踪计算每个进程自创建以来已经执行的处理时间。
    (2)计算每个进程应获得的处理机时间,即自创建以来的时间除以 n 。
    (3)计算进程获得处理机时间的比率,即进程实际执行的处理时间和应获得的处理机时间之比。
    (4)比较各进程获得处理机时间的比率。如进程 A 的比率最低,为0.5,而进程 B 的比率为0.8,进程 C 的比率为1.2等。
    (5)调度程序应选择比率最小的进程将处理机分配给它,并让该进程一直运行,直到超过最接近它的进程比率为止

    2.公平分享调度算法

    分配给每个进程相同的处理机时间,显然,这对诸进程而言,是体现了一定程度的公平,但如果各个用户所拥有的进程数不同,就会发生对用户的不公平问题。假如系统中仅有两个用户,用户1启动了4个进程,用户2只启动1个进程,采用轮转法让每个进程轮流运行一个时间片时间,对进程而言很公平,但用户1和用户2得到的处理机时间分别为80%和20%,显然对用户2而言就有失公平。在该调度算法中,调度的公平性主要是针对用户而言,使所有用户能获得相同的处理机时间,或所要求的时间比例。然而调度又是以进程为基本单位,为此,必须考虑到每一个用户所拥有的进程数目
    例如:系统中有两个用户,用户1有4个进程 A 、 B 、 C 、 D ,用户2只有1个进程 E 。为保证两个用户能获得相同的处理机时间,则必须执行如下所示的强制调度序列:
    A E B E C E D E A E B E C E D E …
    如果希望用户1所获得的处理机时间是用户2的两倍,则必须执行如下所示的强制调度序列
    A B E C D E A B E C D E A B E C D E …

    展开全文
  • 操作系统-作业调度和进程调度

    千次阅读 2022-04-02 17:27:19
    作业调度的主要任务是: 根据JCB的信息,按照某种规则从作业后备队列中进行挑选,给选中的作业分配内存等资源,并建立响应的进程,使其投入运行。 2:作业调度算法 先到先服务 短作业优先 高优先权优先 高响应...
  • 进程调度算法

    千次阅读 2021-12-11 08:47:56
    进程调度算法也称 CPU 调度算法,当 CPU 空闲时,操作系统就从就绪队列中按照一定的算法选择某个就绪状态的进程,并给其分配 CPU。通常以下几种情况会发生进程的调度: 当进程从运行状态转到等待状态; 当进程从...
  • 操作系统——进程调度

    千次阅读 2021-01-27 11:45:21
    进程调度的目的:在进程间切换CPU,最大化CPU利用率,通过操作系统的调度使得计算机资源分配和使用更加高效。 1. 基本概念 1.1 CPU-I/O执行周期 进程的属性:进程执行包括周期进行CPU执行和I/O等待。据此可以将...
  • 【操作系统】_7种进程调度算法

    千次阅读 2022-04-26 23:43:41
    书中一共描述了七种进程调度算法,为了学到这几种调度算法,后边做了几道练习题。 1. 先来先服务(FCFS)调度算法 先来先服务调度算法是最简单的调度方法。其基本原则是,按照进程进入就绪队列的先后次序进行选择。...
  • 操作系统-进程调度算法模拟程序设计,包括先进先出算法和最近最少使用算法的模拟设计,FIFO
  • 试验一~设计一个有 N个进程共行的进程调度程序
  • 进程调度文档

    2013-05-26 21:30:05
    编写程序模拟实现进程的轮转法调度过程,模拟程序只PCB进行相应的调度...采用轮转法进程调度算法进行调度(调度过程中,假设处于执行状态的进程不会阻塞),且每过t个时间片系统释放资源,唤醒处于阻塞队列队首的进程。
  • 每个进程有一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、...每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB,以便进行检查。
  • Linux的进程调度算法简介

    千次阅读 2021-07-16 09:28:57
      进程调度的研究是整个操作系统理论的核心,在多进程的操作系统中,进程调度是一个全局性的、关键性的问题,它系统的总体设计、系统的实现、功能设置以及各方面的性能都有着决定性的影响。进程运行需要各种各样...
  • 常用的进程调度算法

    千次阅读 2019-12-13 21:40:18
    进程调度是由操作系统的进程调度程序按照某种策略和算法从就绪态进程中为当前空闲的CPU选择要运⾏的新进程,常用的进程调度算法有以下几种: 1. 先来先服务调度算法 从就绪队列的队⾸选择最先到达的进程,为该进程...
  • 作业调度、中级调度、进程调度

    千次阅读 2021-04-11 18:17:20
    作业调度(高级调度):其主要任务是按一定的原则从外存上处于后备状态的...进程调度(低级调度):最容易区分,其主要任务是按照某种方法和策略从就绪队列中选取一个进程,将处理机分配给它,一般操作系统中必须配备
  • 进程调度 进程调度的时机 在上篇中说到,进程调度(低级调度),就是按照某种算法从就绪队列中选择一个进程为其分配处理机。我们现在来说说什么时候需要使用到进程调度。 其实,进程调度与切换的时机分为两种情况,...
  • Linux 进程调度的主要策略

    千次阅读 2021-05-10 03:56:26
    1、Linux 下进程分为5种类别,分别是停止类、截止类、实时类、公平类、空闲类,每种类别都有一个运行队列,每次调度时,就是先按照类别优先级排序,再按照每个类别内的最高优先级任务调度运行。文件:core.c (linux-...
  • linux内核的进程调度—调度策略 (注:下文代码片段均出自linux内核版本4.1.15) 文章目录linux内核的进程调度—调度策略一、调度策略(1-1)stop调度策略(1-2)deadline调度策略(1-3)realtime调度策略(1-4)CFS...
  • 用C、C++、Java语言编程实现5个进程采用动态优先权调度算法进行调度的过程。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 411,187
精华内容 164,474
热门标签
关键字:

对进程进行调度