精华内容
下载资源
问答
  • (1)编写并调试一个模拟的进程调度程序,采用“最高优先数优先”调度算法五个进程进行调度。 (2)编写并调试一个模拟的进程调度程序,采用“轮转法”调度算法五个进程进行调度。 轮转法可以是简单轮转法、可变...

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

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

    一、设计简单的进程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; 
    }   
    
    

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

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

    展开全文
  • 进程调度

    千次阅读 2019-07-03 14:43:54
    进程调度 CPU调度是操作系统的基本功能。每当CPU空闲的时候,操作系统就会从就绪队列中选择一个程序来执行。进程选择由短期调度程序执行。 CPU调度决策一般发生在如下四种情形。 当一个进程从运行状态切换到等待...

    进程调度

    CPU调度是操作系统的基本功能。每当CPU空闲的时候,操作系统就会从就绪队列中选择一个程序来执行。进程选择由短期调度程序执行。

    CPU调度决策一般发生在如下四种情形。

    1. 当一个进程从运行状态切换到等待状态。
    2. 当一个进程终止。
    3. 当一个进程从运行状态切换到就绪状态。
    4. 当一个进程从等待状态切换到就绪状态。

    1,2两种情形下,操作系统必须选择一个新的进程去执行。当调度只出现1,2两种情形的时候,调度方案是非抢占式的。1是进程需要等待某种事件的发生(例如,等待打印机,等待子进程),主动让出CPU。2是进程终止了,它的所有资源都被操作系统回收,CPU处于空闲状态。也是主动让出了CPU。所以这两种情形下的调度其实是等待进程自动让出CPU的。采用非抢占式调度,一个进程一旦拥有了CPU,那么它会一直使用CPU直到它主动让出CPU为止,主动让出就是1,2两种情形。

    抢占式调度是进程让出CPU不是主动的,自愿的。上面3,4就是。例如一个中断来了,进程就需要从运行状态切换到就绪状态。执行中断程序。进程等到了某个事件的发生,它将会从等待状态切换为就绪状态,然后它就可以试图去抢占CPU。抢占式调度是有代价的。而且代价比较大。

    CPU调度是由内核进行的,这个短期调度程序在进行调度之后,需要切换上下文,切换到用户模式,跳转到用户程序的合适位置来重新启动这个程序。

    对于现在的交互式系统,人们对系统的响应时间和等待时间的要求是很高的。响应时间长了,用户就会觉得很卡。

    先到先服务(first-come,first-served)

    先到先服务很容易理解。先来的程序先执行,执行完毕后让出CPU给接下来到来的程序。这种策略可以使用FIFO的队列来容易实现。这样的调度策略实现简单,但是它的平均等待时间一般是较长的。更为糟糕的是,当正在执行的程序是一个有许多I/O操作的进程,那么这将导致CPU在空闲的时间里无法运行后面等待的进程,造成了CPU空闲。FCFS策略是非抢占式的,一旦CPU分配给某个进程,那么直到该进程结束之前,CPU都是属于该进程的。从CPU利用率这个指标来评估FCFS,它并不是一个很好的调度策略。

    最短作业优先调度(shortest-job-first)

    最短作业调度是将后续具有最短处理时间的进程先放到CPU上运行,如果就绪队列中有同样长度的进程,那么它们之间是采用FCFS调度的。最短下一个CPU区间,需要操作系统知道接下来是那个进程的CPU区间最短。SJF就是调度这个最短CPU区间的进程。SJF算法具有最短的平均等待时间,它是最佳的调度算法。但是SJF面对的难题是恐怖的,那就是操作系统是如何获知后面就绪队列中哪一个进程具有最短的CPU区间。对于一个批处理系统而言,这不是问题,因为用户会设定进程执行时间。但是现代的操作系统是多任务的交互式系统,操作无法获知下一个CPU区间的长度,我们只能去近似SJF,而不能做到SJF。近似的方法就是去估计,预测它的值。可以认为下一个CPU区间的长度和以前的相似。下一个CPU区间通常可以预测为以前CPU区间的测量长度的指数平均。

    SJF算法可以是抢占的,也可以是非抢占的。一般而言,抢占式的SJF算法比非抢占式的SJF算法更好一些,但这需要调度程序优化的非常好,在切换上下文的时候能极快速的做完。抢占式的SJF是指最短剩余时间优先,当正在执行的进程剩余执行时间和就绪队列中进程剩余执行时间相比,其中时间最短将会被优先执行。

    优先权调度(priority-scheduling algorithm)

    SJF算法可以看做是时间优先级的一种优先级调度算法。在现代的操作系统中,每一个进程都会有一个优先权与其相关。具有最高优先级的进程会被分配到CPU。具有相同优先级的进程按照FCFS算法调度。优先权可以通过内部或者外部方式来定义。优先权调度可以是可抢占的或者非抢占的。

    优先权调度算法的一个主要问题是无穷阻塞问题(饥饿)。优先权调度会使得低优先级的进程可能在无穷等待CPU的到来。通常这种情形发生的时候,可能就会导致很严重的后果。老化是一种解决该问题的方案,老化以逐渐增加在系统中等待很长时间的进程的优先级。

    时间片轮转法(round-robin)

    时间片轮转法是专门为分时系统设计的。它是现代的桌面系统,服务器系统广泛采用的一种调度策略。它定义一个较小的时间单元,称为时间片。CPU调度程序为每个进程分配不超过一个时间片间隔的CPU时间。时间片轮转算法的关键在于时间片大小的选择。

    RR算法的性能基本取决于时间片设计的大小是否合理。时间片设计的过大,将会导致响应很慢。这时候的RR算法可能就接近于FCFS算法。同样,如果时间片设计的很小,那么RR算法可以看做是处理器共享的。但是这样会使得每个进程的处理速度都下降到1/n(假设n个进程),上下文切换对于RR算法的影响也是非常大,频发的在进程之间切换可能会导致开销的时间占比很大,相应的进程实际的执行时间就会被压缩。所以时间片的大小选择是RR算法的核心问题。

    多级队列调度(multilevel queue)

    将就绪队列分成多个独立的队列。根据进程的某些属性,将进程永久的分配到某个队列之中。每个队列都有自己的调度算法。同时队列与队列之间有调度,通常采用固定优先级可抢占式调度。

    也可以在不同的队列之间划分时间片,每个队列拥有一定的CPU时间。

    多级反馈队列调度

    对于多级队列调度算法,进程会被永久的分配至某个队列。这样不够灵活。多级反馈队列调度允许进程在队列之间移动。它依据不同CPU区间特点来划分进程。如果进程使用的CPU时间过多,那么它将会被移到更低优先级的队列。目的是将I/O约束和交互式进程留在较高的优先级。以增加系统的响应。当然了,当它在低优先级等待的时间过长了,老化算法就会让它提升优先级。这样,进程的优先级就会是一个动态的变化。

    多级反馈队列调度是现在的大多数操作系统普遍采用的方案。

     

    ____________________________________________________________________________________________________

    操作系统相对而言是公平的,他来维持系统的一个调度,协调各个进程之间的执行。

     

     

     

    展开全文
  • LINUX进程调度

    千次阅读 2012-02-05 21:59:47
    顾名思义,进程调度就是进程进行调度,即负责选择下一个要运行的进程.通过合理的调度,系统资源才能最大限度地发挥作用,多进程才会有并发执行的效果. 二,进度调度的目标和基本工作: 进程调度最终要完成...
    一,进程调度的作用:
    顾名思义,进程调度就是对进程进行调度,即负责选择下一个要运行的进程.通过合理的调度,系统资源才能最大限度地发挥作用,多进程才会有并发执行的效果.

    二,进度调度的目标和基本工作:
    进程调度最终要完成的目标就是为了最大限度的利用处理器时间.
    即,只要有可以执行的进程,那么就总会有进程正在执行.当进程数大于处理器个数时,某一时刻总会有一些进程进程不能执行.这些进程等待运行.在这些等待运行的进程中选择一个合适的来执行,是调度程序所需完成的基本工作.

    三,调度策略
    1,考虑到进程类型时:I/O消耗型进程 pk 处理器消耗型进程.
    I/O消耗型进程:指进程大部分时间用来提交I/O请求或者是等待I/O请求.
    处理器消耗型进程:与I/O消耗型相反,此类进程把时间大多用在执行代码上.
    此时调度策略通常要在两个矛盾的目标中寻找平衡:进程响应时间短(优先I/O消耗型进程)和最大系统利用率(优先处理器消耗型进程).
    linux为了保证交互式应用,所以对进程的响应做了优化,即更倾向于优先调度I/O消耗型进程.
    2,考虑到进程优先级时:
    调度算法中最基本的一类就是基于优先级的调度.调度程序总是选择时间片未用尽而且优先级最高的进程运行.
    linux实现了一种基于动态优先级的调度方法.即:一开始,先设置基本的优先级,然后它允许调度程序根据需要加,减优先级.
    eg:如果一个进程在I/O等待上消耗的时间多于运行时间,则明显属于I/O消耗型进程,那么根据1中的考虑,应该动态提高其优先级.
    linux提供了两组独立的优先级范围:
    1)nice值:范围从-20到+19.默认值是0,值越小,优先级越高.nice值也用来决定分配给进程的时间片的长短.
    2)实时优先级:范围为0到99.注意,任何实时进程的优先级都高于普通的进程.
    3,考虑到进程时间片时:
    时间片是一个数值,它表明进程在被抢占前所能持续运行的时间.调度策略必须规定一个默认的时间片.时间片过长,则会影响系统的交互性.时间片过短,则会明显增大因进程频繁切换所耗费的时间.
    调度程度提供较长的默认时间片给交互式程序.此外,linux调度程序还能根据进程的优先级动态调整分配给它的时间片,从而保证了优先级高的进程,执行的频率高,执行时间长.
    当一个进程的时间片耗尽时,则认为进程到期了,此时不能在运行.除非所有进程都耗尽了他们的时间片,此时系统会给所有进程重新计算时间片.

    四,linux调度算法
    下面为实现调度算法时的一些相关知识点和注意事项.
    1,可执行队列(runqueue)
    调度程序中最基本的数据结构是可执行队列(runqueue),其结构定义于kernel/sched.c中.可执行队列是给定处理器上的可执行进程的链表,每个处理器一个.
    获得可执行队列:
    cpu_rq(processor):    获得相关处理器的可执行队列.
    this_rq():            获得当前处理器的可执行队列.
    task_rq(task):        返回给定任务所在的可执行队列.
    在对可执行队列进行操作前,应该先锁住它.锁住运行队列的最常见情况发生在你想锁住的运行队列上恰巧有一个特定的任务在运行.如下:
    task_rq_lock();
    task_rq_unlock();

    struct runqueue *rq;
    unsigned long flags;

    rq = task_rq_lock(task,&flags); /*获得特定任务所对应的可执行队列*/
    /*对可执行队列rq进行操作*/
    task_rq_unlock(rq,&flags);

    锁住当前可执行队列:
    this_rq_lock();
    rq_unlock();
    注意:为了避免死锁,要锁住多个运行队列的代码必须总是按照同样的顺序获取这些锁.
    比如:给锁编号1,2,3,4,5.每次申请锁的次序都是1,2,3,4,5.在没取得1锁之前不可以申请2锁.(这个属于个人理解,不知道正确与否,如有错误,希望看到错误的大侠们给予指正.)
    2,优先级数组.
    每个可运行队列都有两个优先级数组,一个活跃的,一个过期的.优先级数组定义在kernel/sched.c中.
    优先级数组使得:每个优先级都对应一个队列,这个队列上包含着对应优先级的可执行进程链表.
    优先级数组由结构体prio_array描速.

    struct prio_array{
      int nr_active;    /*任务数目*/
      unsigned long bitmap[BITMAP_SIZE];   /*优先级位图*/
      struct list_head queue[MAX_PRIO];    /*优先级队列*/
    };

    每个优先级数组都要包含一个这样的位图成员,至少为每个优先级准备一位.一开始,所有的位都被置为0,当某个拥有一定优先级的进程开始准备执行时,图中相应的位就会被置为1.这样,查找系统中最高优先级就变成查找位图中被设置的第一个位.次功能可以由函数sched_find_first_bit()完成.
    3,重新计算时间片
    新的linux调度程序减少了对循环的依赖.取而代之的是为每个处理器维护两个优先级数组:活动数组和过期数组.活动数组内的进程都还有时间片剩余,而过期数组中的是时间片已经耗尽的进程.当一个进程的时间片耗尽时,它会被移至过期的数组,但在此之前,时间片已经重新计算好了.这样,当活动数组中的进程都已经消耗完时间片后,只需把活动数组和过期数组的指针互换就可以了,非常简单.
    4,schedule()
    schedule():选定下一个进程并切换到它去执行.当内核代码想要休眠或者有哪个进程被抢占,那么会调用该函数.函数实现如下:
    struct task_struct *prev, *next;
    struct list_head *queue;
    struct prio_array *array;
    int idx;
    
    prev = current;
    array = rq->active;
    idx = sched_find_first_bit(array->bitmap);  /*找到位图中第一个被设置的位*/
    queue = array->queue + idx;  /*最高位对应的进程链表*/
    next = list_entry(queue->next, struct task_struct, run_list);
    可以看到,schedule()首先在活动优先级数组中找到第一个被设置的位.该位对应着优先级最高的可执行进程列表,然后调度程序选择这个级别链表里的头一个进程运行.因为这个动作根本没用到循环来搜索链表里最适宜的进程,所以实际上,不存在任何影响schedule()执行瞬间长短的因素,它所用的时间是恒定的.(非常好)
    相关图如下:
    5,计算优先级和时间片
    前面说到,优先级和时间片可以影响调度程序作出决定.下面看看这些是如何设计的.
    进程拥有一个初始的优先级,即前面所说到的nice值.默认0,-20最高,+19最低.保存在进程task_struct的static_prio域中.起名为静态优先级.即,一开始由用户指定后,就不能改变.调度程序要用到的动态优先级存放在prio域里.
    可以通过effective_prio()函数返回一个进程的动态优先级.实现如下:
    动态优先级 = nice + (-5 到 +5)的进程交互性的奖励或罚分.
    那么这里涉及到一个判断进程的交互性强弱的问题.最明显的标准莫过于进程休眠的时间长短.如果一个进程的大部分时间是在休眠,则它就是I/O消耗型的.反之,如果一个进程执行的时间比休眠的时间长,那么它就是处理器消耗型的.
    为了支持这种机制,linux用task_struct中的sleep_avg域来记录一个进程用于休眠和用于执行的时间.范围从0到MAX_SLEEP_AVG.默认为10ms.当一个进程从休眠状态恢复到执行状态时,sleep_avg会根据它休眠的时间长短而增加.直到达到MAX_SLEEP_AVG为止.相反,进程每运行一个时钟节拍,sleep_avg就做相应的递减,到0为止.
    当一个任务的时间片用完之后,就要根据任务的静态优先级重新计算时间片.task_timeslice()函数为给定任务返回一个新的时间片.时间片的计算只需要把优先级按比例缩放,使其符合时间片的数值范围就可以了.
    调度程序还提供了另外一种机制以支持交互进程:如果一个进程的交互性非常强,那么当它时间片用完后,它会被再放置到活动数组而不是过期数组中.该逻辑在scheduler_tick()中实现:
    struct task_struct *task;
    struct runqueue *rq;

    task = current;
    rq = this_rq();

    if (!--task->time_slice) {
            if (!TASK_INTERACTIVE(task) || EXPIRED_STARVING(rq))
                    enqueue_task(task, rq->expired);
            else
                    enqueue_task(task, rq->active);
    }
    宏TASK_INTERACTIVE()根据进程的nice值来判定它是不是一个交互性特别强的进程(nice值越小,交互性越强).
    宏EXPIRED_STARVING()负责检查过期的数组内的进程是否处于饥饿状态,即是否已经较长时间没有切换数组了.如果有,则将进程放入过期数组中,以防止饥饿加重.
    6,休眠和唤醒
    休眠过程:进程把自己标记成休眠状态,把自己从可执行队列移出,放入等待队列,然后调用schedule()选择和执行一个其他进程.
    唤醒的过程刚好相反,即进程被设置为可执行状态,然后从等待队列中移至可执行队列中.
    等待队列的创建:
    静态:DECLARE_WAITQUEUE()
    动态:init_waitqueue_head()
    睡眠的简单代码如下:
    /* 'q' is the wait queue we wish to sleep on */
    DECLARE_WAITQUEUE(wait, current);

    add_wait_queue(q, &wait);
    while (!condition) {     /* condition is the event that we are waiting for */
            set_current_state(TASK_INTERRUPTIBLE); /* or TASK_UNINTERRUPTIBLE */
            if (signal_pending(current))
                    /* handle signal */
            schedule();
    }
    set_current_state(TASK_RUNNING);
    remove_wait_queue(q, &wait);
    唤醒的操作是通过函数wake_up进行的.它会唤醒指定的等待队列上的所有进程.通常哪段代码促使等待条件达成,它就要负责随后调用的wake_up()函数.
    休眠和唤醒之间的关系如图所示:
    7,负载平衡程序.
    针对对称多处理系统,调度程序通过负载平衡程序来提升整体的调度.负载平衡程序保证了每个处理器对应的可执行队列之间的负载处于均衡状态.注意,这是在SMP的情况下,在单处理器下,不会被调用.
    负载平衡程序由kernel/sched.c中的函数load_balance()来实现.
    load_balance()的调用时刻:  1) schedule().当前可执行队列为空时,调用. 2) 每隔一段时间一调用.
    负载平衡程序所做的工作大体可如下图所示.

    五,用户抢占与内核抢占
    用户抢占时:检查need_resched.如果设置了该位,则重新调度.否则返回执行当前进程.
    用户抢占可在以下情况时发生:
    1,从系统调用返回用户空间时.
    2,从中断处理程序返回用户空间时.
    内核抢占时:检查need_resched和preempt_count.如果need_resched被设置,preempt_count为0,则调用schedule().如果need_resched被设置,preempt_count非0,则返回执行当前进程.
    内核抢占可能会发生在以下情况时:
    1,当中断处理程序正在执行,且返回内核空间之前.
    2,当内核代码再一次具有可抢占性的时候.
    3,内核中的任务显式调用schedule()时.
    4,如果内核中的任务阻塞(这也同样会导致调用schedule()).
    展开全文
  • 进程调度 进程调度的时机 在上篇中说到,进程调度(低级调度),就是按照某种算法从就绪队列中选择一个进程为其分配处理机。我们现在来说说什么时候需要使用到进程调度。 其实,进程调度与切换的时机分为两种情况,...

    进程调度


    进程调度的时机

    在上篇中说到,进程调度(低级调度),就是按照某种算法从就绪队列中选择一个进程为其分配处理机。我们现在来说说什么时候需要使用到进程调度与切换。
    进程调度与切换的时机分为两种情况,一种是当前运行的进程主动放弃处理机,还有一种是当前运行的进程被动放弃处理机。接下来看看它们分别对应什么事件。

    • 当前运行的进程主动放弃处理机
      1. 进程正常终止。
      2. 运行过程中发生异常而终止。(如 内中断)
      3. 进程主动请求阻塞。(如 请求使用打印机)
    • 当前运行的进程被动放弃处理机
      1. 分配给该进程的时间片用完。
      2. 有更紧急的事情要处理。(如 外中断)
      3. 有更高优先级的进程进入就绪队列。

    注意:有的系统只允许进程主动放弃处理机,而在有的系统,进程可以既主动放弃处理机,又可以被剥夺处理机(当有更紧急的任务需要处理时)。

    当然,有时候我们也不能进行进程调度与切换,比如以下的情况。

    • 不能进行进程调度与切换的情况
      1. 在处理中断的过程中。中断处理过程复杂,与硬件密切相关,很难做到在中断处理的过程中进行进程调度与切换。
      2. 在原子操作过程中(原语)。原子操作不可中断,要一气呵成。
      3. 进程在操作系统内核程序临界区中时。 (这个在下面会解释)

    对遗留问题的解释

    在解释上述问题之前,先说说什么是临界资源,什么是临界区。

    • 临界资源:一段时间内只允许一个进程使用的资源。即 各个进程只能互斥的访问临界资源。
    • 临界区:程序中访问临界资源的那段代码

    内核程序临界区一般是用来访问某种内核数据结构(临界资源)的代码。对于就绪队列这种内核临界资源,当有一个进程访问就绪队列时,该进程会给就绪队列上锁,以防其他进程的访问,所以此时我们不能进行进程调度,因为就绪队列被上锁了,进程调度相关进程无法访问该队列。

    所以,进程在操作系统内核程序区时的确不能进行进程调度,但进程处于(普通)临界区时还是可以进行进程调度的,下面对其解释。
    内核程序临界区和普通临界区不一样,普通临界区访问的临界资源不会直接影响到操作系统内核的管理工作,比如进程请求打印机这种临界资源,由于打印机准备需要时间,CPU总不能一直等待打印机准备完毕吧,所以此时需要进行进程调度。


    进程调度的方式

    进程调度的方式分为两种,分别是非剥夺式调度方式和剥夺式调度方式

    • 非剥夺调度方式
      该方式又称非抢占方式。该方式只允许进程主动放弃处理机。在运行过程中即使有更紧迫的任务到达,当前进程依然会继续使用处理机,直到该进程终止或主动要求进入阻塞态。这种方式实现简单,系统开销小,但是无法及时的处理紧急任务,适合于早期批处理系统。

    • 剥夺调度方式
      该方式又称抢占方式。该方式允许进程处理机被剥夺。当有一个进程正在处理机上运行时,如果有一个更重要的进程需要使用处理机,操作系统会立即暂停正在运行的进程,将处理机分配给更重要的那个进程。这种方式实现相对复杂,但是可以优先处理紧急任务,也可以实现让各进程按时间片规划轮流执行相应的功能(通过时钟中断),适合于分时操作系统、实时操作系统。

    以上两种方式类似于银行排队,非剥夺调度方式就是每个人都按照顺序排好,顺序的完成需求,安分守己,而剥夺调度方式就是,当你正在处理需求的时候,来了一个彪形大汉,强制的把你从队头中踢出。

    进程调度的狭义与广义

    • 狭义的进程调度
      狭义的进程调度只是指从就绪队列中选择一个进程,为其分配处理机资源,不包括进程切换。
    • 广义的进程调度
      广义的进程调度包括了选择进程和切换进程两个过程。

    小贴士:进程切换是有代价的,如果过于频繁的进行进程调度、切换,必然会导致整个系统的工作效率降低,使系统大部分时间都花在进程切换上,而使真正用于运行进程的时间减少。


    总结

    在这里插入图片描述

    感谢

    以上内容大部分来自王道操作系统系列视频教学。

    展开全文
  • 进程如何调度

    千次阅读 2017-06-08 22:33:50
    PS:在多进程并发的环境里,虽然从概念...这就涉及到进程管理的一个重要组成部分:进程调度,跟随本篇来一起复习下进程调度吧! 一、进程调度基础 1.1 进程调度定义  进程调度是操作系统进程管理的一个重要组成部
  • Linux进程调度

    千次阅读 2018-02-07 17:33:12
    进程调度算法用来解决以何种次序各就绪进程进行处理机的分配以及按照何种时间比例让进程占用处理机。 一、完全公平调度算法简称CFS Linux为了保证交互式应用和桌面系统的性能,所以进程的响应做出了优化...
  • 进程管理之进程调度

    千次阅读 2019-03-13 19:14:07
    文章目录一、进程调度基础1、进程调度定义2、进程调度目标二、基本调度算法1、先来先服务算法2、时间片轮转算法3、短任务优先算法4、优先级调度算法5、混合调度算法   在多进程并发的环境里,虽然从概念上看,有多...
  • 进程调度算法Linux进程调度算法

    千次阅读 2018-02-06 20:02:27
    这次介绍一下操作系统的进程调度算法 操作系统的调度分为三种:1.远程调度(创建新进程);2.中程调度(交换功能的一部分);3.短程调度(下次执行哪个进程) 这次讲述的就是短程调度,可以简单的看作咱们平时...
  • 进程调度介绍

    千次阅读 2018-04-17 19:00:43
    许多进程调度的处理方式进程和线程都适用。这里首先讨论进程调度问题。 我们可以把调度算法分为两类:非抢占式调度以及抢占式调度。 非抢占式调度算法 这种算法挑选一个进程运行,并一直运行到阻塞(...
  • Linux 进程调度浅析

    千次阅读 2015-04-09 20:30:19
    概述 操作系统要实现多进程,进程调度必不可少。有人说,进程调度是操作系统中最为... 首先,我们需要明确一点:进程调度 TASK_RUNNING 状态的进程进行调度。如果进程不可执行(正在睡眠或其他),那么它跟进程调
  • 进程调度算法

    千次阅读 2018-09-28 21:55:06
    是一种最简单的调度算法,可用于作业调度,也可用于进程调度 优缺点: 先来先服务优缺点 比较有利于长作业(进程),而不利于短作业(进程) 有利于CPU繁忙型作业(进程) ,而不利于I/O繁忙型作业(进程) 用于...
  • 试描述在采用先来先服务调度、短进程优先调度算法时,各个进程的运行过程,并计算这5个进程的平均周转时间。假设忽略进程调度时间。 答:①先来先服务调度算法运行过程如下:按到达先后P1,P2,P3,P4,P5依次...
  • 进程线程调度

    千次阅读 2016-06-15 16:16:24
    本文讲述的是linux和windows中的线程-进程调度基本原理。
  • Linux 进程与进程调度详解

    千次阅读 2015-09-24 15:37:41
    进程调度发生在什么时机呢?这与引起进程调度的原因以及进程调度的方式有关。 引起进程调度的原因有以下几类, (1)正在执行的进程执行完毕。这时,如果不选择新的就绪进程执行,将浪费处理机资源。 (2)执行中进程...
  • 操作系统进程优先级调度实验

    千次阅读 2016-11-08 13:43:19
     用高级语言编写和调试一个进程调度程序,以加深进程的概念及进程调度算法的理解. [准备知识]   一、基本概念 1、进程的概念; 2、进程的状态和进程控制块; 3、进程调度算法 [试验内容]  设计一个有 N个进程...
  • 进程调度与作业调度

    千次阅读 2017-02-12 21:54:25
    进程调度是真正让某个就绪状态的进程到处理机上运行,而作业调度只是使作业具有了竞争处理机的机会。进程调度(又称微观调度、低级调度、短程调度): 是按照某种调度算法从就绪状态的进程中选择一个进程到处理机上...
  • 一、区分: CPU调度 = 短期调度 = 狭义的进程调度 ...在教材中,是在进程调度的讲解中,说“长期调度,中期调度,短期调度都属于进程调度”,而其他资料中,是将cpu调度也就是短期调度叫做进程调度。...
  • Linux进程调度策略

    千次阅读 2018-07-25 16:50:00
    Linux进程调度策略分为以下几种:   #define SCHED_OTHER 0 #define SCHED_FIFO 1 #define SCHED_RR 2 #define SCHED_BATCH 3 #define SCHED_IDLE 5   可以把它们分为两大类: 实时进程 - SCHED_FIFO...
  • Linux进程管理(四)进程调度之抢占式调度 文章目录Linux进程管理(四)进程调度之抢占式调度一、抢占式调度二、设置需要重新调度的标志的时机(TIF_NEED_RESCHED)三、进程抢占的时机3.1 用户态的抢占时机3.2 内核...
  • 进程调度算法设计

    千次阅读 2019-08-06 19:10:29
    【实验目的】 进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用...本实验模拟在单处理器情况下的进程调度,目的是加深对进程调度工作的理解,掌握不...
  • 理解进程调度时机跟踪分析进程调度与进程切换的过程
  • 进程调度算法(进程调度策略)

    千次阅读 2013-08-07 14:23:01
    进程调度算法 调度算法是指:根据系统的资源分配策略所规定的资源分配算法。 一、先来先服务和短作业(进程)优先调度算法  1. 先来先服务调度算法。先来先服务(FCFS)调度算法是一种最简单的调度算法,该...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 349,258
精华内容 139,703
关键字:

对进程进行调度