C/C++教程

HRRN算法C语言实现

本文主要是介绍HRRN算法C语言实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 刷某客网题,初遇此高响应比优先算法,正在学操作系统任务调度,尝试用C语言写了下,VC环境,验证无误。

综合作业执行时间和作业等待时间,本着“即照顾短作业,又不使长作业等待时间过长”的思想,改进调度性能。

算法思想:

作业完成时间(时刻):作业实际完成的时刻

                      作业完成时间 = 上一个任务完成时间 + 执行时间

作业周转时间(时间段):作业从提交到执行完毕所需要的时间

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

响应比 = 周转时间 / 执行时间

至于响应比为什么要这么算,怎么定义,请大佬告知。

还有剩下所有任务的周转时间和响应比都需要根据当前任务完成而更新。

附上代码:

/*
highest response rrtio next
*/

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 4

/*ERROR MESSAGE*/
#define MERROR_ALLOCATION_ERROR 0

/*TASK_PARAMETER_LOAD_EN*/
#define TASK_PARAMETER_LOAD_EN 0

//RETURN STATUS
#define OK 1
#define ERROR 0;
typedef int Status;

//作业结构体
typedef struct
{
	double subtime;			//提交时间
	double exetime;			//执行时间
	double comptime;			//完成时间
	double turntime;			//周转时间
	double resrate;			//响应比
}Task;

//LinkList Node
typedef struct LNode
{
	Task task;
	struct LNode *next;
}LNode, *LinkList;

//data for initial
double subtime[MAXSIZE] = { 8.0, 8.6, 8.8, 9.0 };
double exetime[MAXSIZE] = { 2.0, 0.6, 0.2, 0.5 };

//error message
void PrintErrMessage ( int err )
{
	switch ( err )
	{
	case MERROR_ALLOCATION_ERROR : printf( "MERROR_ALLOCATION_ERROR!\n"); break;
	default:;
	}
}

//Initial 
Status InitTaskList ( LinkList &L )
{
	LinkList p,q;

	L = ( LinkList )malloc( sizeof(LNode) );			//struct head node
	if ( !L )
	{
		PrintErrMessage( MERROR_ALLOCATION_ERROR );
		return ERROR;
	}
	L->task.subtime = 0;
	L->task.exetime = 0;
	q = L;
	for ( int i = 0; i<MAXSIZE; ++i )
	{
		p = ( LinkList )malloc( sizeof(LNode) );		//正序构建单链表
		p->task.subtime = subtime[i];
		p->task.exetime = exetime[i];
		p->task.comptime = 0;
		p->task.turntime = 0;
		p->task.resrate = 0;
		q->next = p;
		q = p;
	}
	q->next = NULL;
#if	TASK_PARAMETER_LOAD_EN > 0	
#endif
	return OK;
}

//printf
void printfTaskLinkList ( LinkList L)
{
	LinkList p = L->next;
	while( p != NULL )
	{
		printf( "%.2lf %.2lf %.2lf %.2lf %.2lf\n",
			p->task.subtime, p->task.exetime, p->task.comptime, p->task.turntime, p->task.resrate );
		p = p->next;
	}
	printf("\n");
}

//计算完成时间、周转时间、响应比
void CountTime ( LinkList &L )
{
	LinkList p,q,j;
	p = L->next;

	//compute the complete time and turnround time of the first task.
	if ( L->task.subtime==0 )
	{
		
		p->task.comptime = p->task.subtime + p->task.exetime;
		p->task.turntime = p->task.comptime - p->task.subtime;
	}

	//compute the complete time and turnround time of the rest task.
	q = p->next;
	do
	{	
		q->task.comptime = p->task.comptime + q->task.exetime;
		q->task.turntime = q->task.comptime - q->task.subtime;
		q->task.resrate = q->task.turntime / q->task.exetime;
		q = q->next;
	}while( q != NULL );

	
	//check the largest response time node.
	q = p->next;
	j = q->next;easily cause AV error

	while( j != NULL )
	{
		if ( q->task.resrate > j->task.resrate )
		{
			j = j->next;
		}
		else
		{
			q = j;
			j = j->next;
		}
	}
	//move the largest response tine node as the next node to be execute.
	if ( q != p->next )
	{
		j = p->next;
		while( j->next != q ) j = j->next;
		j->next = q->next;
		q->next = p->next;
		p->next = q;
	}

	//PRINT
	printfTaskLinkList( L );

	//ENTER RECURSION
	if ( p->next->next->next !=NULL )/if ( p->next != NULL ) cause AV error.
		CountTime( p );
}




void main()
{
	LinkList LTask;
	InitTaskList( LTask );
	printfTaskLinkList( LTask );
	
	CountTime( LTask );
	printfTaskLinkList( LTask );

}

动态分配内存之后,利用递归计算,有点绕,因为技术水品有限,参考下就好。不过结果是对的。 

结果:以当前任务(第一条任务)计算余下任务响应比并更新 

 

这篇关于HRRN算法C语言实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!