HRRN算法C语言实现

编程 2023-12-06 17:15:48

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语言实现

 

声明:该文观点仅代表作者本人,必看呐发布平台,仅提供信息存储空间服务。