精华内容
下载资源
问答
  • 时间片轮转算法实现

    千次阅读 2019-06-16 18:47:55
    时间片轮转算法的进程调度模拟程序 要求以文件的形式给出进程的ID、到达时间和估计运行时间,设计一个模拟单处理机调度的时间片轮转算法,实现处理机的调度,在屏幕上打印每次调度的相关信息,包括:进程占用处理机...

    时间片轮转算法的进程调度模拟程序

    要求以文件的形式给出进程的ID、到达时间和估计运行时间,设计一个模拟单处理机调度的时间片轮转算法,实现处理机的调度,在屏幕上打印每次调度的相关信息,包括:进程占用处理机序列,该进程执行的开始时间、进程运行结束时间、进程的周转时间和带权周转时间等。最后统计出平均周转时间和平均带权周转时间。

    #include<stdio.h>
    #include <stdlib.h>
    #define N 50 //定义进程最大数 
    #define T 1 //时间片 
    struct PCB
    {	int ci;	//进程被调度的次数 
    	int ks;  //进程开始运行的时间 
    	int pn;   //process name进程名字
    	int at;   //arrival time到达时间
    	int st;   //service time服务时间
    	int ct;   //completion time完成时刻
    	int sc;  //sign completion标志是否完成
    	int st1;  //剩余服务时间  
    }process[N];
     
     //定义队列节点 
    typedef struct QNode{ 
    	int data; 
    	struct QNode *next; 
    }QNode,*QueuePtr;
    //定义队列
    typedef struct{
    	QueuePtr front; 
    	QueuePtr rear;
    }LinkQueue;
    int InitQueue(LinkQueue &Q);        //初始化队列 
    int DestroyQueue(LinkQueue &Q);//删除队列
    int EnQueue(LinkQueue &Q,int e); //进入队列
    int DeQueue(LinkQueue &Q,int e);//离开队列
    bool QueueEmpty(LinkQueue &Q);//判读队列是否为空
    int cun(LinkQueue &Q,int e);  //判断队列中是否存在此数 
     
    int RR()
    {
    	LinkQueue Q;//创建队列
    	int i,j,c;
    	int n=0;//记录进程数 
    	char fname[20];
    	FILE *fp; 
    	printf("注意:文件中应包含以下信息:\n");
    	printf("进程ID    到达时间     估计运行时间  \n");
    	printf("请输入进程流文件名:");
    	scanf("%s",&fname);
    	if((fp=fopen(fname,"r"))==NULL){
    		printf("错误,文件打不开,请检查文件名");
    		return 0;
    	}else{
    		while(1){
    			
    			if( feof(fp) ){ 
             		 break ;
         	 	}
         	 	//文件读取结束退出 process[0]不存储PCB,作为辅助 
    			fscanf(fp,"%d %d %d ",&process[n+1].pn,&process[n+1].at,&process[n+1].st); 
    			process[n+1].sc=0;
    			process[n+1].ks=0;
    			process[n+1].ci=0;
    			process[n+1].st1=process[n+1].st;
    			n++;
    			//初始化,剩余服务时间等于服务时间 
    		}
    	}
    	
    	//按照各进程到达时间升序,对进程排序 
    	for(i=1;i<=n;i++)
    	for(j=i+1;j<=n;j++)  
    	{
    		if(process[j].at<process[i].at)
    		{
    			process[0]=process[j];
    			process[j]=process[i];
    			process[i]=process[0];	
    		}
    	}
    //		for(i=1;i<=n;i++) printf("%d\n",process[i].pn);
    	
    	int time=process[1].at;      //当前时间的初值 
    	printf("\n调度过程:\n");
    	printf("\n第几次调度进程 运行的进程 开始运行时间 运行时间 剩余服务时间 结束时间\n");
    	int z=1;   //记录第几次调度进程 
    	InitQueue(Q);
    	EnQueue(Q,1);
     	int yun=0; // 判断进程以那种方式开始 
     	//当队列不为空时 
     	while(QueueEmpty(Q)==false){
     		int i;
     		i=DeQueue(Q,i);
     		//出队 
     		if(process[i].st1<=T){
    		 	process[i].ci++;
    		 	//进程被调度次数+1 
    		 	yun=2;
    		 	time=time+process[i].st1;
    		 	process[i].sc=1;
    		 	int k;
    		 	//如果有就绪进程就加入就绪队列 
    		 	for(k=1;k<=n;k++){
    		 		if(time>=process[k].at&&process[k].sc!=1&&cun(Q,k)==1){
    		 			EnQueue(Q,k);
    				}
    			} 
    		 	process[i].ct=time;
    		 	printf("%8d%12d%15d%11d%11d%11d\n",z++,process[i].pn,time-process[i].st1,process[i].st1,0,time); 
    		 	process[i].st1=0;
    		 }else if(process[i].st1>T)//未完成的进程但其还需服务时间至少大于一个时间片 
    		 	{
    				int j,k; j=i;
    		 		process[i].ci++;
    		 		yun=1;
    		 		time=time+T;
    		 		//如果有就绪进程就加入就绪队列 
    		 		for(k=1;k<=n;k++){
    		 			if(time>=process[k].at&&j!=k&&process[k].sc!=1&&cun(Q,k)==1){
    		 				EnQueue(Q,k);
    					 }
    				 }
    				 //进程因为时间片用完转化为就绪队列 
    				 EnQueue(Q,i);
    				process[i].st1-=T;
    				printf("%8d%12d%15d%11d%11d%11d\n",z++,process[i].pn,time-T,T,process[i].st1,time);
    			} 
    			//计算 进程开始运行时间 
    			if (process[i].ci==1){
    				if(yun==1){
    					process[i].ks=time-T;
    				}
    				if(yun==2){
    					process[i].ks=time-process[i].st1;	
    				}
    			}
    	 }
     printf("\n调度的相关信息:\n");
     printf("\n进程ID 到达时间 服务时间 开始运行时间 结束时间  进程的周转时间  带权周转时间\n");
     	for(i=1;i<=n;i++){
    		printf("%4d%8d%8d%10d%10d%14d            %.2f\n",process[i].pn,process[i].at,process[i].st,process[i].ks,process[i].ct,process[i].ct-process[i].at,(float)(process[i].ct-process[i].at)/process[i].st);
    	} 
    	float temp=0;
    	printf("\n\n平均周转时间:");
    	for(i=1;i<=n;i++){ 
    		temp+=process[i].ct-process[i].at;
    	} 
    	temp=temp/n;
    	printf("%f\n",temp);
    	temp=0;
    	printf("\n平均带权周转时间:");
    	for(i=1;i<=n;i++){ 
    		temp+=(float)(process[i].ct-process[i].at)/process[i].st;
    	} 
    	temp=temp/n;
    	printf("%f",temp);
    
    }
     
    int main()
    {
    	printf("\n\n\t\t\t\t**********时间片轮转调度算法**********\n\n");
    	RR();
    	return 0;
    }
    
    //初始化队列 
    int InitQueue(LinkQueue &Q){
    	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    	if(!Q.front)exit(-1);
    	Q.front->next=NULL;
    	return 1;
    }
    //进队 
    int EnQueue(LinkQueue &Q,int e){
    	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
    	if(!p)
    	exit(-1);
    	p->data=e;
    	p->next=NULL;
    	Q.rear->next=p;
    	Q.rear=p;
    	return 1;
    } 
    //弹出最队尾元素 
    int DeQueue(LinkQueue &Q,int e){
    	QueuePtr p;
    	if(Q.front==Q.rear)
    	return 0;
    	p=Q.front->next;
    	e=p->data;
    	Q.front->next=p->next;
    	if(Q.rear==p)
    	Q.rear=Q.front;
    	free(p);
    	return e;
    }
    //判断队列是否为空 
    bool QueueEmpty(LinkQueue &Q){
    	if(Q.front==Q.rear)
    		return true;
    	else
    		return false;
    }
    //队列存在此数返回0,否则返回1 
    int cun(LinkQueue &Q,int s){
    	int a[100];
    	int i;
    	int sg=1;
    	int n=0;
    	while(QueueEmpty(Q)==false){
    		int i;
     		i=DeQueue(Q,i);
     		a[n]=i;
     		n++;
    	}
    	for(i=0;i<n;i++){
    		EnQueue(Q,a[i]);
    	}
    	for(i=0;i<n;i++){
    		if(a[i] == s){
    			sg=0;
    		}
    	}
    	return sg;
    }
    

    实现步骤

    1. 从文件中读取进程的相关信息,初始化pcb
    2. 初始化化就绪队列,用数据结构队列保存就绪的进程。
    3. 进行时间片轮转调度,过程都在程序里写的很清楚。
    展开全文
  • 【操作系统】时间片轮转调度法

    千次阅读 2020-12-21 10:40:02
    同义词:时间片轮转法一般指时间片轮转调度算法,时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法。每个进程被分配一时间段,称作它的时间片,即该进程允许运行的时间。 中文名 时间片轮转调度算法...

    操作系统——时间片轮转调度法


    同义词:时间片轮转法一般指时间片轮转调度算法,时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法。每个进程被分配一时间段,称作它的时间片,即该进程允许运行的时间。

    中文名时间片轮转调度算法
    释义每个进程被分配一时间段
    定义该进程允许运行的时间
    合理时间时间片设为100毫秒

    在这里插入图片描述

    时间片轮转调度算法含义

    时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法。每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间。如果在时间片结束时进程还在运行,则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束,则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表,当进程用完它的时间片后,它被移到队列的末尾。
    时间片轮转调度中唯一有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间的--保存和装入 寄存器值及内存映像,更新各种表格和队列等。假如 进程切换(process switch) - 有时称为 上下文切换(context switch),需要5毫秒,再假设时间片设为20毫秒,则在做完20毫秒有用的工作之后,CPU将花费5毫秒来进行进程切换。CPU时间的20%被浪费在了管理开销上。
    为了提高CPU效率,我们可以将时间片设为500毫秒。这时浪费的时间只有1%。但考虑在一个分时系统中,如果有十个交互用户几乎同时按下回车键,将发生什么情况?假设所有其他进程都用足它们的时间片的话,最后一个不幸的进程不得不等待5秒钟才获得运行机会。多数用户无法忍受一条简短命令要5秒钟才能做出响应。同样的问题在一台支持多道程序的个人计算机上也会发生。
    结论可以归结如下:时间片设得太短会导致过多的进程切换,降低了CPU效率;而设得太长又可能引起对短的交互请求的响应变差。将时间片设为100毫秒通常是一个比较合理的折中。

    时间片轮转调度算法基本原理

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

    时间片轮转调度算法时间片

    时间片大小的确定
    1.系统对响应时间的要求
    2.就绪队列中进程的数目
    3.系统的处理能力

    时间片轮转调度算法算法

    时间片轮转调度算法多级反馈

    多级反馈队列调度算法
    (1) 设置多个就绪队列,并为各个队列赋予不同的优先级. 第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低.
    该算法赋予各个队列中进程执行时间片的大小也各不相同:
    在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小.
    例如:第二个队列的时间片要比第一个队列的时间片长一倍,……,第i+1个队列的时间片要比第i个队列的时间片长一倍.
    (2) 当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度.当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,如此下去,当一个长作业(进程)从第一队列依次降到第n队列后,在第n队列中便采取按时间片轮转的方式运行.
    (3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行; 仅当第1~(i-1) 队列均空时,才会调度第i队列中的进程运行.如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分配给新到的高优先权进程.?
    性能
    (1)终端型作业用户
    (2) 短批处理作业用户
    (3) 长批处理作业用户
    满足了多数用户的需求

    时间片轮转调度算法优先权

    优先权调度算法
    1,优先权调度算法的类型
    非抢占式优先权算法
    在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成; 或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程.这种调度算法主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中.
    抢占式优先权调度算法
    系统同样把处理机分配给优先权最高的进程,使之执行.但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程.
    这种抢占式的优先权调度算法,能更好地满足紧迫作业的要求,常用于要求比较严格的实时系统中, 以及对性能要求较高的批处理和分时系统中.
    2,优先权的类型
    (1) 静态优先权
    静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变.
    一般地,优先权是利用某一范围内的一个整数来表示的,例如,0~7或0~255中的某一整数, 又把该整数称为优先数.只是具体用法各异:有的系统用"0"表示最高优先权,当数值愈大时,其优先权愈低;而有的系统恰恰相反.
    确定进程优先权的依据有如下三个方面:
    1.进程类型.(系统进程/用户进程)
    2.进程对资源的需求.(需求量的大小)
    3.用户要求.(用户进程紧迫程度)
    (2) 动态优先权
    动态优先权是指在创建进程时所赋予的优先权,可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能.
    例如,我们可以规定,在就绪队列中的进程,随其等待时间的增长,其优先权以速率a提高.若所有的进程都具有相同的优先权初值,则显然是最先进入就绪队列的进程,将因其动态优先权变得最高而优先获得处理机,此即FCFS算法.
    优先权的变化规律可描述为:
    由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比RP.据此,又可表示为:
    3,高响应比优先调度算法
    由上面的式子可以得到以下结论:
    (1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业.
    (2) 当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务.
    (3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高, 从而也可获得处理机.
    该算法照顾了短作业,且不会使长作业长期得不到服务

    时间片轮转调度算法抢占式

    1. 非抢占式调度算法
    为每一个被控对象建立一个实时任务并将它们排列成一轮转队列,调度程序每次选择队列中的第一个任务投入运行.该任务完成后便把它挂在轮转队列的队尾等待下次调度运行.
    2. 非抢占式优先调度算法.
    实时任务到达时,把他们安排在就绪队列的队首,等待当前任务自我终止或运行完成后才能被调度执行.
    3. 抢占式调度算法
    1)基于时钟中断的抢占式优先权调度算法.
    实时任务到达后,如果该任务的优先级别高于当前任务的优先级并不立即抢占当前任务的处理机,而是等到时钟中断到来时,调度程序才剥夺当前任务的执行,将处理机分配给新到的高优先权任务.
    2)立即抢占的优先权调度算法.
    在这种调度策略中,要求操作系统具有快速响应外部时间中断的能力.一旦出现 外部中断,只要当前任务未处于 临界区便立即剥夺当前任务的执行,把处理机分配给请求中断的紧迫任务,实时进程调度,实时进程抢占当前。

    时间片轮转调度算法实时系统

    1 实现实时调度的基本条件
    1-1. 提供必要的信息-就绪时间.
    1-2. 开始截止时间和完成截止时间.
    1-3. 处理时间.
    1-4. 资源要求.
    1-5. 优先级.
    2. 系统处理能力强
    在实时系统中,通常都有着多个实时任务.若处理机的处理能力不够强,则有可能因处理机忙不过来而使某些实时任务不能得到及时处理, 从而导致发生难以预料的后果.假定系统中有m个周期性的硬实时任务,它们的处理时间可表示为Ci,周期时间表示为Pi,则在单处理机情况下,系统可调度必须满足下面的限制条件:
    当系统不可调度时解决的方法是提高系统的处理能力,其途径有二:
    其一仍是采用 单处理机系统,但须增强其处理能力, 以显著地减少对每一个任务的处理时间;
    其二是采用 多处理机系统.假定系统中的处理机数为N,则应将上述的限制条件改为:
    3. 采用抢占式调度机制
    当一个优先权更高的任务到达时,允许将当前任务暂时挂起,而令高优先权任务立即投入运行.采用这种方式去满足那些开始截止时间即将到来的任务.?
    4. 具有快速切换机制
    应具有的能力:
    (1) 对外部中断的快速响应能力.为使在紧迫的外部事件请求中断时系统能及时响应,要求系统具有快速硬件中断机构,还应使禁止中断的时间间隔尽量短,以免耽误时机(其它紧迫任务).?
    (2) 快速的任务分派能力.在完成任务调度后,便应进行任务切换.为了提高分派程序进行任务切换时的速度, 应使系统中的每个运行功能单位适当的小,以减少任务切换的时间开销. 实时调度实例
    一, 最早截止时间优先算法(EDF)
    EDF算法用于非抢占调度方式
    优先级:根据任务的开始截止时间来确定任务的优先级.
    二,最低松弛优先算法(LLF)
    例如:系统中有两个周期性实时任务A和B,任务A要求每20ms执行一次,执行时间为10ms;任务B要求每50ms执行一次,执行时间为25ms.这样可知A和B每次必须完成的时间和开始截止时间如图所示
    优先级:根据任务紧急程度来确定任务优先级
    A和B任务每次必须完成的时间
    A1 (10) A2 (30) A3(50) A4 (70) A5(90) A6 (110) A7(130) A8(150)
    0 、10、 20、 30 、40、 50 、60、 70、 80 、90 、100 、110、 120、130、 140、 150
    B1(25) B2(75) B3(125)
    A和B任务每次必须开始的时间
    时间(ms) A截止时间 B截止时间 调度对象
    0 A1(10) B1(25) A1
    10 A2(20) B1(15) B1
    30 A2(0) B1(15) A2
    40 A3(10) B1(5) B1
    45 A3(5) B2(30) A3
    55 A4(15) B2(20) B2
    70 A4(0) B2(20) A4
    松弛度
    松弛度
    ( 20-10-0 ) ( 50-25-0 )
    (40-10-10 ) ( 50-25-10 )
    (40-10-30) (50-5-30)
    (60-10-40) (50-5-40)
    (60-10-45) (100-25-45)
    (80-10-55) (100-25-55)
    (80-10-70) (100-10-70 )
    3.4.1 多处理器系统 的类型
    (1) 紧密耦合(Tightly Coupted)MPS.
    这通常是通过高速总线或高速 交叉开关,来实现多个处理器之间的互连的.它们共享 主存储器系统和I/O设备,并要求将主存储器划分为若干个能独立访问的存储器模块,以便多个处理机能同时对主存进行访问.系统中的所有资源和进程,都由操作系统实施统一的控制和管理.
    3.4 多处理机系统中的调度
    从处理器之间耦合的紧密程度上划分:
    松散耦合(Loosely Coupled)MPS.
    在松散耦合MPS中,通常是通过通道或 通信线路,来实现多台计算机之间的互连.每台计算机都有自己的 存储器和I/O设备,并配置了OS来管理本地资源和在本地运行的进程.因此,每一台计算机都能独立地工作, 必要时可通过通信线路与其它计算机交换信息,以及协调它们之间的工作.
    根据系统中所用处理器的相同与否划分:
    (1) 对称多处理器系统SMPS. 在系统中所包含的各处理器单元,在功能和结构上都是相同的,当前的绝大多数MPS都属于SMP系统.例如,IBM公司的SR/6000 Model F50, 便是利用4片Power PC处理器构成的.?
    (2) 非对称多处理器系统.在系统中有多种类型的处理单元,它们的功能和结构各不相同,其中只有一个主处理器,有多个从处理器:
    1. 对称多处理器系统中的进程分配方式
    在SMP系统中,所有的处理器都是相同的,因而可把所有的处理器作为一个处理器池(Processor pool),由调度程序或基于处理器的请求,将任何一个进程分配给池中的任何一个处理器去处理.在进行进程分配时,可采用以下两种方式之一.
    1) 静态分配(Static Assigenment)方式
    2) 动态分配(Dynamic Assgement)方式?
    3.4.2 进程分配方式
    静态分配(Static Assigenment)方式
    一个进程从开始执行直到完成,都被固定分配到一个处理器上去执行.
    2) 动态分配(Dynamic Assgement)方式
    系统中设置有公共的就绪队列.分配进程时,可以将进程分配到任何一个处理器上.
    动态分配方式的主要优点是消除了各处理器忙闲不均的现象
    2. 非对称MPS中的进程分配方式?
    对于非对称MPS,其OS大多采用主—从(Master-Slave)式OS,即OS的核心部分驻留在一台主机上(Master),而从机(Slave)上只是用户程序,进程调度只由主机执行.每当从机空闲时,便向主机发送一索求进程的信号,然后,便等待主机为它分配进程.在主机中保持有一个就绪队列,只要就绪队列不空,主机便从其队首摘下一进程分配给请求的从机.从机接收到分配的进程后便运行该进程,该进程结束后从机又向主机发出请求.
    缺点:对主机要求高,出现故障导致整个系统瘫痪
    1. 自调度(Self-Scheduling)方式
    1) 自调度机制?
    在系统中设置有一个公共的进程或线程就绪队列, 所有的处理器在空闲时,都可自己到该队列中取得一进程(或线程)来运行.在自调度方式中,可采用在单处理机环境下所用的调度算法,如先来先服务(FCFS)调度算法,最高优先权优先(FPF)调度算法和抢占式最高优先权优先调度算法等.
    3.4.3 进程(线程)调度方式
    2) 自调度方式的优点?
    1,系统中的公共就绪队列可按照单处理机系统中所采用的各种方式加以组织;其调度算法也可沿用单处理机系统所用的算法,即很容易将单处理机环境下的调度机制移植到多处理机系统中
    2,只要系统中有任务(公共就绪队列不空)就不会出现处理机空闲的情况,也不会发生处理器忙闲不均的现象,因而有利于提高处理器的利用率.
    3)自调度方式的缺点
    3.4.4进程调度过程
    1、进程名:作为进程的标识。
    指针:进程按顺序排成循环链表,用指针指出下一个进程的进程控制块首地址,最后一个进程中的指针指出第一个进程的进程控制块首地址。
    2、要求运行时间:假设进程需要运行的单位时间数。
    已运行时间:假设进程已经运行的单位时间数,初值为0。
    状态:可假设有两种状态,就绪状态和结束状态。进程的初始状态都为就绪状态。
    3、每次运行所设计的处理器调度程序调度进程之前,为每个进程任意确定它的要求运行时间。
    4、此程序是模拟处理器调度,因此,被选中的进程并不实际启动运行,而是执行
    已运行时间+1
    来模拟进程的一次运行,表示进程已经运行过一个单位时间。
    .5、在所设计的程序中应有显示或打印语句,能显示或打印每次被选中的进程名以及运行一次后进程队列的变化。
    6、为进程任意确定要求运行时间,运行所设计的处理器调度程序,显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
    7、设有一个就绪队列,就绪进程按优先数(优先数范围0-100)由小到大排列(优先数越小,级别越高)。当某一进程运行完一个时间片后,其优先级应下调(如优先数加2或3)。
    8、例如一组进程如下表:
    进程名
    A
    B
    C
    D
    E
    F
    G
    H
    J
    K
    L
    M
    到达时间
    0
    1
    2
    3
    6
    8
    12
    12
    12
    18
    25
    25
    服务时间
    6
    4
    10
    5
    1
    2
    5
    10
    4
    3
    15
    8

    时间片轮转调度算法瓶颈问题

    1. 整个系统中只有一个就绪队列供多个处理器共享.
    (2)低效性.
    线程在其生命周期内多次更换处理器使得高速缓存的使用率很低
    (3)线程切换频繁.
    2. 成组调度(Gang Scheduling)方式
    3.专用处理器分配方式
    展开全文
  • Java线程何时放弃CPU时间片

    千次阅读 2020-01-11 11:30:41
    每个线程从启动到结束的过程中可能经历多种状态,多个线程则意味着并发,而并发则涉及CPU的执行时间片。下图是三个线程分配到的CPU执行时间示意图,从启动到结束三个线程除了真正执行阶段,还包含了等待阶段。 执行...

    跟着作者的65节课彻底搞懂Java并发原理专栏,一步步彻底搞懂Java并发原理。

    作者简介:笔名seaboat,擅长工程算法、人工智能算法、自然语言处理、架构、分布式、高并发、大数据和搜索引擎等方面的技术,大多数编程语言都会使用,但更擅长Java、Python和C++。平时喜欢看书、写作和运动,擅长篮球、跑步、游泳、健身和羽毛球等运动项目。崇尚开源,崇尚技术自由,更崇尚思想自由。出版书籍:《Tomcat内核设计剖析》、《图解数据结构与算法》、《人工智能原理科普》。

    线程与CPU执行

    Java中内置支持在一个进程中运行多个线程,线程的执行由JVM进行管理。每个线程从启动到结束的过程中可能经历多种状态,多个线程则意味着并发,而并发则涉及CPU的执行时间片。下图是三个线程分配到的CPU执行时间示意图,从启动到结束三个线程除了真正执行阶段,还包含了等待阶段。

    线程并发执行

    执行时间

    一个线程从启动到结束过程总,有两个时间概念我们要理解。其一是CPU时间,即线程真正执行的时间。其二是总消耗时间,即真正执行的时间加上等待的时间。如下图可以很清晰看到这两者的关系,P1得到了多个CPU执行时间,而总消耗时间则包括P1执行期间CPU分配给其它线程执行的时间,所以总

    展开全文
  • RR、时间片轮转算法

    千次阅读 2018-12-06 20:56:40
    #include&lt;iostream&gt; #include&lt;string&gt; #include&lt;math.h&gt; using namespace std; struct RR{  string name; //进程名  string status;... //到达时间。...
    #include<iostream>
    #include<string>
    #include<math.h>
    using namespace std;
    struct RR{
        string name;       //进程名
        string status;     //进程状态,判断是否完成
        int arrive_time;   //到达时间。用来构造初始的时间片队列
        int server_time;   //服务时间
        int rest_time;    //剩余服务时间,用来判断进程是否服务结束
    };
    const int RR_Size = 5;
    static int number = 1;    //用来输出时指示第i块时间片
    
    int RR_Input(RR process[]) {    //数据的输入,同时返回输入进程的个数
        int count = 0;    //进程个数
        for (int i = 0; i < RR_Size; i++) {
            printf("请输入第%d个进程的名字、到达时间、服务时间\n", i + 1);
            cin >> process[i].name >> process[i].arrive_time >> process[i].server_time;
            while (process[i].arrive_time < 0 || process[i].server_time < 0) {
                if (process[i].arrive_time < 0)
                    printf("到达时间输入有误,请重新输入!\n");
                if (process[i].server_time < 0)
                    printf("服务时间输入有误,请重新输入!\n");
                printf("请输入第%d个进程的名字、到达时间、服务时间\n", i + 1);
                cin >> process[i].name >> process[i].arrive_time >> process[i].server_time;
                if (process[i].arrive_time >= 0 && process[i].server_time >= 0)
                    break;  //满足输入条件则退出循环
            }
            process[i].rest_time = process[i].server_time;
            process[i].status = "就绪";
            if (process[i].name == "0") {
                process[i].status = "完成";
                break;   //退出循环
            }
            count++;
        }
        return count;
    }
    
    void RR_Sort(RR process[], int count) {   //根据到达时间对进程进行排序
        for (int i = 0; i < count - 1; i++) {
            if (process[i].arrive_time > process[i + 1].arrive_time) {
                string tmp; tmp = process[i].name; process[i].name = process[i + 1].name; process[i + 1].name = tmp;
                int swap; swap = process[i].arrive_time; process[i].arrive_time = process[i + 1].arrive_time; process[i + 1].arrive_time = swap;
                int temp; temp = process[i].server_time; process[i].server_time = process[i + 1].server_time; process[i + 1].server_time = temp;
                int num; num = process[i].rest_time; process[i].rest_time = process[i + 1].rest_time; process[i + 1].rest_time = num;
                string change;  change = process[i].status;  process[i].status = process[i + 1].status;  process[i + 1].status = change;
            }
        }
    }
    
    void RR_Print(RR process[], int count) {   //对进程进行打印
        printf("进程名称\t到达时间\t服务时间\t剩余服务时间\t当前状态\n");
        for (int i = 0; i < count; i++) {
            cout << "   " << process[i].name << "\t\t   " << process[i].arrive_time << "\t\t   " << process[i].server_time << "\t\t     " << process[i].rest_time <<
                "\t\t   " << process[i].status << endl;
        }
        printf("***********第%d时间片时间到**************\n", number);  //number为静态变量
        number++;
    }
    
    void RR_Start(RR process[], int Time_length, int count) {   //参数n为时间片大小, count为进程个数
        RR_Sort(process, count);
        for (int i = 0; i < count; i++) {
            if (process[i].status == "完成")   //当次进程已经运行结束,则跳到下一个进程。
                continue;
            if (process[i].status == "就绪") {   //对就绪队列的队首进程进行操作
                process[i].rest_time -= Time_length;
                if (process[i].rest_time <= 0) {   //时间片结束后判断进程是否执行完毕
                    process[i].rest_time = 0;
                    process[i].status = "完成";
                }
                else
                    process[i].status = "运行";
            }
            RR_Print(process, count);
            if (process[i].status != "完成")   //时间片用完,若进程没有结束,则将运行态转换为就绪态。
                process[i].status = "就绪";
        }
    }
    
    
    void RR_Out(RR process[], int count) {   //count为进程个数,这个是整个输出框架。
        int Times = 0;
        int Time_length;      //时间片大小
        printf("请输入时间片的大小:");
        scanf_s("%d", &Time_length);
        for (int i = 0; i < count; i++) {
            //得到需要服务时间的总和,判断需要的时间片数。
            Times += ceil(process[i].server_time / (float)Time_length);  //需要的时间片数,向上取整
        }
        for (int j = 0; j < Times; j++) {
            RR_Start(process, Time_length, count);
        }
    }
    void main() {
        RR process[RR_Size];
        int count = RR_Input(process);
        RR_Out(process, count);
    }

     

    展开全文
  • FreeRTOS专题八:支持时间片

    千次阅读 2019-09-06 12:10:26
    支持时间片
  • 时间片轮转调度算法详细判断流程: 例题: 进程 到达时间 服务时间 P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 时间片为1 先放出来最终的结果 ↑ ↑ ↑ ↑ ↑ ...
  • 时间片轮询法

    千次阅读 2019-07-09 08:20:53
    注: 我看了,网上大多数博客都是用这份代码做讲解,所以我也是用它来说明自己的理解,我是在微信上看到的这篇文章,等我找到原作者,...时间片轮询,这是我们今天要介绍的重点,也是我最近新get到的技能,我们待会...
  • 时间片

    千次阅读 2018-10-24 19:28:12
    时间片是CPU分配给各个线程的时间,因为时间片非常短,所以CPU通过不停的切换线程执行,让我们感觉多个线程是同时执行的,时间片一般是十几毫秒(ms)。...
  • 一 定义时间片轮转算法是将所有的就绪进程按先来先服务的原则,排成一个队列,按时间片轮转。时间片的大小从几ms到几百ms。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的...
  • 时间片轮转调度算法

    千次阅读 2020-06-06 17:34:09
    每次调度时,总是选择就绪队列的队首进程,让其在CPU上运行一个系统预先设置好的时间片。一个时间片内没有完成运行的进程,返回到绪队列末尾重新排队,等待下一次调度。 算法步骤 1. 假设系统中有n个进程,每个...
  • Java线程的CPU时间片

    千次阅读 2018-04-29 10:04:17
    Java中线程会按优先级分配CPU时间片运行,那么线程什么时候放弃CPU的使用权?可以归类成三种情况: 当前运行线程主动放弃CPU,JVM暂时放弃CPU操作(基于时间片轮转调度的JVM操作系统不会让线程永久放弃CPU,或者说...
  • 时间片轮转调度算法 a.在时间片轮转调度算法中,系统根据先来先服务的原则,将所有的就绪进程排成一个就绪队列,并且每隔一段时间产生一次中断,激活系统中的进程调度程序,完成一次处理机调度,把处理机分配给就绪...
  • 关于时间片轮转算法

    千次阅读 2020-09-20 19:03:14
    关于时间片轮转算法时间片轮转算法含义基本原理时间片大小的确定调度方式(可抢夺,抢占)调度时机特点 时间片轮转算法 含义 时间片轮转调度算法是一种最古老,最简单,最公平的且使用最广的算法。每个进程被分配一...
  • 时间片轮转调度算法一、 实验内容二、 实验要求三、 实验过程1、 设计思想2、 数据结构四、 实验代码五、实验结果 一、 实验内容 使用时间片轮转算法模拟实现进程调度功能。 二、 实验要求 1、模拟时间片轮转调度...
  • 单片机程序架构(一)时间片轮询架构

    千次阅读 热门讨论 2021-01-28 16:00:40
    //时间片架构测试 void Task1(void); void Task2(void); void Task3(void); void Task4(void); void Task5(void); void Task6(void); void Task7(void); void Task8(void); void Task9(void); void Task0(void); /...
  • 操作系统【时间片轮转调度算法 课本例题】
  • c语言实现时间片轮询调度

    千次阅读 2019-05-30 23:03:59
    时间片轮询调度法模拟 #include<stdio.h> #define MAX 10 struct task_struct { char name[10]; /进程名称/ int number; /进程编号/ float come_time; /到达时间/ float run_begin_time; /开始运行时间...
  • 总览: 调 度 算 法 : 1.时 间 片 轮 转 调 度 算 法 (RR) 2.优 先 级 调 度 算 法 ...使用时间片轮转调度算法,分析时间片大小分别是2,5时的进程运行情况。 时间片轮转调度算法: 轮流让就绪队列中的进程依次执行一个时
  • 时间片轮转算法

    万次阅读 2018-11-12 21:39:41
    时间片轮转算法:主要用于分时系统中的进程调度。为了实现轮转调度,系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时,进程调度程序总是选出就绪队列的队首进程,...
  • 经典时间片轮转RR算法C语言实现

    千次阅读 热门讨论 2020-04-24 11:13:02
    1.进程的服务时间用完时,无论时间片到没到,时间片都需要置0。 2.进程的服务时间没用完,而且时间片到了,需要把此进程添加到队尾,时间片置0。 进程都运行结束时,调出循环的条件需要注意。 具体可以看注释: #...
  • 时间片轮寻:==2.0 一个定时器的复用:====2.1 时间片轮询架构:====2.2 具体实现:==2.2.1定义 任务结构体2.2.2初始化 任务结构体2.2.3定义 任务清单&任务数目 枚举类型2.2.4编写 定时器中断函数&任务处理...
  • 什么叫时间片

    千次阅读 2020-06-05 09:59:36
    什么叫时间片? 在宏观上:我们可以同时打开多个应用程序,每个程du序并行不悖,同时运行。 但是在微观上:由于只有一个CPU,一次只能处理程序要求的一部分,如何处理公平,一种方法就是引入时间片,每个程序轮流...
  • 本文基于linux-4.5.3对内核公平调度之时间片相关函数主要流程做了详细介绍,其他细节请参考其他书籍或源码。
  • 设计一个按时间片轮转法实现处理器调度的程序。 二、实验内容 (1) 假定系统有五个进程,每一个进程用一个进程控制块PCB来代表。进程控制块的格式为: 进程名 指针 要求运行时间 已运行时间 状态 其中,进程名——...
  • 时间片轮转调度算法模拟C语言

    千次阅读 多人点赞 2020-01-02 14:37:25
    时间片轮转调度算法模拟C语言 本来要做这么一个作业,准备用C语言写,然后参考网上的一些代码,发现很多都有错误,用课本的例子代入都不对,后来我发现是错在对时间片调度算法的理解。所以在别人的基础上写了以下...
  • RR 时间片轮转算法 (java)

    千次阅读 2019-12-16 23:15:07
    操作系统中的 时间片算法 运行结果 流程图 ---------------------java代码------------------------ package operate; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue...
  • 单片机应用程序架构-时间片轮询法

    千次阅读 2019-06-21 15:29:55
    单片机应用程序框架时间片轮询法的学习。 根据所见的,学的,看的。大致分为三类程序结构。 1. 简单的前后台顺序执行程序。 2. 时间片轮询法。 3. 操作系统。 简单的顺序执行的程序,写起来往往很混乱。越复杂的需求...
  • 记录——时间片轮转调度算法模拟程序,用Java实现

    千次阅读 多人点赞 2020-01-04 13:38:29
    1、合理设计PCB结构,设计模拟指令格式,并以文件形式存储,程序能够读取文件并自动生成指令序列。2、根据文件内容,建立模拟进程队列,并能采用时间片轮转调度算法对模拟进程进行调度。
  • CPU时间片轮换机制

    千次阅读 2020-04-21 21:30:20
    1.cpu时间片轮换机制是什么? cpu时间片轮换机制是一种最古老,简单和公平的算法;又称为RR调度。时间片则是分配给每个进程的一个最大时间段。 2.运行机制有哪些? (1)在某个进程的运行时间达到系统所分配的最大...
  • RR时间片轮转法调度C语言实现

    千次阅读 2020-05-18 18:34:11
    在FCFS的基础上,加入时间片的概念,从第一个到达的进程开始,CPU分配其一个时间片的长度,第一个进程放到其余任务后面,然后给第二个进程分配一个时间片,第二个进程放到其余任务后面,依次类推,直到所有进程完成。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 611,974
精华内容 244,789
关键字:

时间片