转载声明:文章来源https://www.cnblogs.com/bajdcc/p/4707746.html
一、数据结构
1.1 事件类型
由于要求是基于事件的进程调度,所以必须创建一个存放事件的队列。
enum EventType{ ARRIVALEVENT, FINISHEVENT, TIMEREVENT }; //事件类型
1.2 任务结构(每一项数据都是输入):
struct Job
{
char name[50]; //作业名
int arriveTime; //作业到达时间
int needTime; //作业所需运行时间
int priority; //作业优先级,数字越小,优先级越高
};
1.3 事件链表结点:
struct Event
{
EventType type; //事件类型
int jobBeginTime; //作业开始时间
bool isFirstExe; //判断是否第一次执行,用于记录作业开始时间
int happenTime; //发生时刻
int remainTime; //剩余运行时间
double hrr; //最高响应比
Job job; //作业
Event *next; //事件指针
};
因为事件为队列存储,因而需要动态增删,所以较佳的数据结构是链表。因为是链表,所以要定义一套操作链表的函数。
二、程序流程图
2.1 非抢占式调度
2.2 抢占式调度
2.3 轮转调度
三、过程定义
3.1 事件队列相关函数/* 作业复制函数 */
void CopyJob( Job *dest, const Job *sour );
/* 事件队列创建函数
* 包含头节点
* 返回头指针 */
Event *CreateEventQueue();
/* 抓取头结点之外的第一个事件
* 作为返回值返回 */
Event *FetchFirstEvent( Event *head );
/* 如果值相同,时间将插在前方 */
void InsertFinishEvent( Event *head, Event *e );
/* 插入到队尾 */
void InsertTail( Event *head, Event *e );
/* 按作业名称删除第一个匹配项,
* 删除成功返回TRUE,不存在该节点返回FALSE
*/
bool DeleteByJobName( Event *head, char *jobName );
/* 删除事件队列 */
void DestroyQueue( Event *head );
一、插入函数(用于插入排序)
1.1 按开始时间插入
void InsertByHappenTime( Event *head, Event *e )
{
if ( head == NULL || e == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
Event *p = head;
while ( ( p->next != NULL ) && ( e->happenTime >= (p->next)->happenTime ) )
{
p = p->next;
}
e->next = p->next;
p->next = e;
}
1.2 按结束时间插入
void InsertFinishEvent( Event *head, Event *e )
{
if ( head == NULL || e == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
Event *p = head;
while ( ( p->next != NULL ) && ( e->happenTime > (p->next)->happenTime ) )
{
p = p->next;
}
e->next = p->next;
p->next = e;
}
1.3 按作业时间插入
void InsertByJobTime( Event *head, Event *e )
{
if ( head == NULL || e == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
Event *p = head;
while ( ( p->next != NULL ) && ( (e->job).needTime >= (p->next)->job.needTime ) )
{
p = p->next;
}
e->next = p->next;
p->next = e;
}
1.4 按剩余时间插入
void InsertByRemainTime( Event *head, Event *e )
{
if ( head == NULL || e == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
Event *p = head;
while ( ( p->next != NULL ) && ( e->remainTime >= p->next->remainTime ) )
{
p = p->next;
}
e->next = p->next;
p->next = e;
}
1.5 按优先级插入
void InsertByPriority( Event *head, Event *e )
{
if ( head == NULL || e == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
Event *p = head;
while ( ( p->next != NULL ) && ( e->job.priority >= p->next->job.priority ) )
{
p = p->next;
}
e->next = p->next;
p->next = e;
}
void InsertByHRR( Event *head, Event *e )
{
if ( head == NULL || e == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
Event *p = head;
while ( ( p->next != NULL ) && ( e->hrr <= p->next->hrr ) )
{
p = p->next;
}
e->next = p->next;
p->next = e;
}
1.6 按最高响应比插入
void SortByHRR( Event *head, int currentTime )
{
Event *addrValue = new Event;
addrValue->next = head->next;
Event *p = addrValue->next;
head->next = NULL; //将节点放置另一个链表中
while ( p != NULL )
{
p->happenTime = currentTime;
p->hrr = 1 + ( p->happenTime - p->job.arriveTime ) / p->job.needTime * 0.1;
p = p->next;
}
while ( p = FetchFirstEvent( addrValue ) )
{
InsertByHRR( head, p );
p = addrValue->next;
}
delete addrValue;
addrValue = NULL;
}
1.7 最高响应比插入排序
void SJF( Event *eventHead )
{
if ( eventHead == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
int currentTime = 0; //当前时间
bool isCpuBusy = false; //CPU忙碌状态
Event *readyQueue = new Event; //包含头结点,就绪队列
readyQueue->next = NULL;
while ( eventHead->next != NULL )
{
Event *firstEvent = FetchFirstEvent( eventHead );
currentTime = firstEvent->happenTime;
if ( firstEvent->type == ARRIVALEVENT )
{
if ( isCpuBusy == true )
{
InsertByJobTime( readyQueue, firstEvent );
}
else
{
isCpuBusy = true;
Event *finishEvent = new Event;
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = currentTime;
finishEvent->happenTime = currentTime + firstEvent->job.needTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(firstEvent->job) );
if ( firstEvent != NULL )
delete firstEvent;//删除正在执行事件节点
firstEvent = NULL;
InsertByHappenTime( eventHead, finishEvent );
}
continue ;
}
if ( firstEvent->type == FINISHEVENT )
{
ShowEvent( firstEvent );
if ( firstEvent != NULL )
delete firstEvent;//删除已执行事件节点
firstEvent = NULL;
isCpuBusy = false;
Event *shortestEvent = FetchFirstEvent( readyQueue );
if ( shortestEvent != NULL )
{
isCpuBusy = true;
Event *finishEvent = new Event();
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = currentTime;
finishEvent->happenTime = currentTime + shortestEvent->job.needTime;
finishEvent->remainTime = shortestEvent->job.needTime;
CopyJob( &(finishEvent->job), &(shortestEvent->job) );
if ( shortestEvent != NULL )
delete shortestEvent;//删除正在执行事件节点
shortestEvent = NULL;
InsertByHappenTime( eventHead, finishEvent );
}
}
}
}
二、调度算法
2.1 最短工作时间优先
void SRTF( Event *eventHead )
{
if ( eventHead == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
int currentTime = 0;
bool isCpuBusy = false;
Event *readyQueue = new Event;
readyQueue->next = NULL;
Event *runEvent = NULL; //正在运行事件节点
while ( eventHead->next != NULL )
{
Event *firstEvent = FetchFirstEvent( eventHead );
int frontTime = currentTime; //上次事件发生时间
currentTime = firstEvent->happenTime;
if ( firstEvent->type == ARRIVALEVENT )
{
if ( isCpuBusy == true )
{
runEvent->happenTime = currentTime;
runEvent->remainTime -= (currentTime - frontTime);//剩余时间 = 运行时间- 已运行时间(本次-上次时间)
if ( firstEvent->remainTime < runEvent->remainTime )
{ //抢断
DeleteByJobName( eventHead, runEvent->job.name ); //删除上次事件的结束事件,PS.若上次事件先插入,将会被删除
InsertByRemainTime( readyQueue, runEvent ); //上次事件加入就绪队列
runEvent = firstEvent; //上次事件已插入继续队列,无须释放空间,更新本次事件
runEvent->isFirstExe = false; //
Event *finishEvent = new Event;
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = runEvent->jobBeginTime;//
finishEvent->happenTime = currentTime + runEvent->remainTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(runEvent->job) );
InsertByHappenTime( eventHead, finishEvent ); //插入结束事件
}
else
{
InsertByRemainTime( readyQueue, firstEvent );//等待,加入就绪事件队列
}
}
if ( isCpuBusy == false )
{
isCpuBusy = true;
firstEvent->isFirstExe = false;
Event *finishEvent = new Event;
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = firstEvent->jobBeginTime; //
finishEvent->isFirstExe = false;
finishEvent->happenTime = currentTime + firstEvent->remainTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(firstEvent->job) );
runEvent = firstEvent;
InsertByHappenTime( eventHead, finishEvent );
}
continue ;
}
if ( firstEvent->type == FINISHEVENT )
{
ShowEvent( firstEvent );
if ( runEvent != NULL ) //删除已运行事件
delete runEvent;
runEvent = NULL;
isCpuBusy = false;
Event *remainTimeEvent = FetchFirstEvent( readyQueue );
if ( remainTimeEvent != NULL )
{
isCpuBusy = true;
if ( remainTimeEvent->isFirstExe ) //在就绪队列中,若作业首次执行,必然是延迟发生的
remainTimeEvent->jobBeginTime = currentTime;
remainTimeEvent->isFirstExe = false;
Event *finishEvent = new Event();
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = remainTimeEvent->jobBeginTime;
finishEvent->happenTime = currentTime + remainTimeEvent->remainTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(remainTimeEvent->job) );
runEvent = remainTimeEvent;
InsertByHappenTime( eventHead, finishEvent );
}
}
}
}
2.2 最短剩余时间优先
void SRTF( Event *eventHead )
{
if ( eventHead == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
int currentTime = 0;
bool isCpuBusy = false;
Event *readyQueue = new Event;
readyQueue->next = NULL;
Event *runEvent = NULL; //正在运行事件节点
while ( eventHead->next != NULL )
{
Event *firstEvent = FetchFirstEvent( eventHead );
int frontTime = currentTime; //上次事件发生时间
currentTime = firstEvent->happenTime;
if ( firstEvent->type == ARRIVALEVENT )
{
if ( isCpuBusy == true )
{
runEvent->happenTime = currentTime;
runEvent->remainTime -= (currentTime - frontTime);//剩余时间 = 运行时间- 已运行时间(本次-上次时间)
if ( firstEvent->remainTime < runEvent->remainTime )
{ //抢断
DeleteByJobName( eventHead, runEvent->job.name ); //删除上次事件的结束事件,PS.若上次事件先插入,将会被删除
InsertByRemainTime( readyQueue, runEvent ); //上次事件加入就绪队列
runEvent = firstEvent; //上次事件已插入继续队列,无须释放空间,更新本次事件
runEvent->isFirstExe = false; //
Event *finishEvent = new Event;
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = runEvent->jobBeginTime;//
finishEvent->happenTime = currentTime + runEvent->remainTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(runEvent->job) );
InsertByHappenTime( eventHead, finishEvent ); //插入结束事件
}
else
{
InsertByRemainTime( readyQueue, firstEvent );//等待,加入就绪事件队列
}
}
if ( isCpuBusy == false )
{
isCpuBusy = true;
firstEvent->isFirstExe = false;
Event *finishEvent = new Event;
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = firstEvent->jobBeginTime; //
finishEvent->isFirstExe = false;
finishEvent->happenTime = currentTime + firstEvent->remainTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(firstEvent->job) );
runEvent = firstEvent;
InsertByHappenTime( eventHead, finishEvent );
}
continue ;
}
if ( firstEvent->type == FINISHEVENT )
{
ShowEvent( firstEvent );
if ( runEvent != NULL ) //删除已运行事件
delete runEvent;
runEvent = NULL;
isCpuBusy = false;
Event *remainTimeEvent = FetchFirstEvent( readyQueue );
if ( remainTimeEvent != NULL )
{
isCpuBusy = true;
if ( remainTimeEvent->isFirstExe ) //在就绪队列中,若作业首次执行,必然是延迟发生的
remainTimeEvent->jobBeginTime = currentTime;
remainTimeEvent->isFirstExe = false;
Event *finishEvent = new Event();
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = remainTimeEvent->jobBeginTime;
finishEvent->happenTime = currentTime + remainTimeEvent->remainTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(remainTimeEvent->job) );
runEvent = remainTimeEvent;
InsertByHappenTime( eventHead, finishEvent );
}
}
}
}
2.3 时间片轮转(时间片大小为1)
void RR( Event *eventHead )
{
if ( eventHead == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
int currentTime = 0;
bool isCpuBusy = false;
Event *readyQueue = new Event;
readyQueue->next = NULL;
while ( eventHead->next != NULL )
{
Event *firstEvent = FetchFirstEvent( eventHead );
if ( firstEvent->happenTime > currentTime )
currentTime = firstEvent->happenTime;
if ( firstEvent->type == ARRIVALEVENT )
{
if ( isCpuBusy )
{
InsertTail( readyQueue, firstEvent );
}
else
{
isCpuBusy = true;
Event *nextEvent = new Event;
nextEvent->jobBeginTime = firstEvent->jobBeginTime;
CopyJob( &(nextEvent->job), &(firstEvent->job) );
if ( firstEvent->remainTime <= TIMER ) //FinishEvent
{
nextEvent->type = FINISHEVENT;
nextEvent->happenTime = currentTime + firstEvent->remainTime;
nextEvent->remainTime = 0;
InsertFinishEvent( eventHead, nextEvent );
}
else //TimerEvent
{
nextEvent->type = TIMEREVENT;
nextEvent->happenTime = currentTime + TIMER;
nextEvent->remainTime = firstEvent->remainTime - TIMER;
InsertByHappenTime( eventHead, nextEvent );
}
if ( firstEvent != NULL )
delete firstEvent;//删除正在执行事件节点
firstEvent = NULL;
}
continue ;
}
if ( firstEvent->type == TIMEREVENT )
{
InsertTail( readyQueue, firstEvent );
}
int isFinish = false;
if ( firstEvent->type == FINISHEVENT )
{
ShowEvent( firstEvent );
if ( firstEvent != NULL )
delete firstEvent;//删除已执行事件节点
firstEvent = NULL;
isFinish = true;
}
while ( firstEvent = FetchFirstEvent( readyQueue ) )
{
if ( isFinish )
isCpuBusy = true, isFinish = false;
Event *nextEvent = new Event;
if ( firstEvent->type == ARRIVALEVENT )
nextEvent->jobBeginTime = currentTime;
else if ( firstEvent->type == TIMEREVENT )
nextEvent->jobBeginTime = firstEvent->jobBeginTime;
CopyJob( &(nextEvent->job), &(firstEvent->job) );
if ( firstEvent->remainTime <= TIMER ) //FinishEvent
{
nextEvent->type = FINISHEVENT;
nextEvent->happenTime = currentTime + firstEvent->remainTime;
nextEvent->remainTime = 0;
InsertFinishEvent( eventHead, nextEvent );
}
else //TimerEvent
{
nextEvent->type = TIMEREVENT;
nextEvent->happenTime = currentTime + TIMER;
nextEvent->remainTime = firstEvent->remainTime - TIMER;
InsertByHappenTime( eventHead, nextEvent );
}
currentTime = nextEvent->happenTime;
if ( firstEvent != NULL )
delete firstEvent;//删除正在执行事件节点
firstEvent = NULL;
}
}
}
2.4 抢占式优先级调度
void Priority( Event *eventHead )
{
if ( eventHead == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
int currentTime = 0;
bool isCpuBusy = false;
Event *readyQueue = new Event;
readyQueue->next = NULL;
Event *runEvent = NULL; //正在运行事件节点
while ( eventHead->next != NULL )
{
Event *firstEvent = FetchFirstEvent( eventHead );
int frontTime = currentTime; //上次事件发生时间
currentTime = firstEvent->happenTime;
if ( firstEvent->type == ARRIVALEVENT )
{
if ( isCpuBusy == true )
{
runEvent->happenTime = currentTime;
runEvent->remainTime -= (currentTime - frontTime);//剩余时间 = 运行时间- 已运行时间(本次-上次时间)
if ( firstEvent->job.priority < runEvent->job.priority )
{ //抢断
DeleteByJobName( eventHead, runEvent->job.name ); //删除上次事件的结束事件,PS.若上次事件先插入,将会被删除
InsertByPriority( readyQueue, runEvent ); //上次事件加入就绪队列
runEvent = firstEvent; //上次事件已插入继续队列,无须释放空间,更新本次事件
runEvent->isFirstExe = false; //
Event *finishEvent = new Event;
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = runEvent->jobBeginTime;//
finishEvent->happenTime = currentTime + runEvent->remainTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(runEvent->job) );
InsertByHappenTime( eventHead, finishEvent ); //插入结束事件
}
else
{
InsertByRemainTime( readyQueue, firstEvent );//等待,加入就绪事件队列
}
}
if ( isCpuBusy == false )
{
isCpuBusy = true;
firstEvent->isFirstExe = false;
Event *finishEvent = new Event;
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = firstEvent->jobBeginTime;
finishEvent->happenTime = currentTime + firstEvent->remainTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(firstEvent->job) );
runEvent = firstEvent;
InsertByHappenTime( eventHead, finishEvent );
}
continue ;
}
if ( firstEvent->type == FINISHEVENT )
{
ShowEvent( firstEvent );
if ( runEvent != NULL ) //删除已运行事件
delete runEvent;
runEvent = NULL;
isCpuBusy = false;
Event *priorityEvent = FetchFirstEvent( readyQueue );
if ( priorityEvent != NULL )
{
isCpuBusy = true;
if ( priorityEvent->isFirstExe ) //在就绪队列中,若作业首次执行,必然是延迟发生的
priorityEvent->jobBeginTime = currentTime;
Event *finishEvent = new Event();
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = priorityEvent->jobBeginTime;
finishEvent->happenTime = currentTime + priorityEvent->remainTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(priorityEvent->job) );
runEvent = priorityEvent;
InsertByHappenTime( eventHead, finishEvent );
}
}
}
}
2.5 最高响应比优先
void HRRF( Event *eventHead )
{
if ( eventHead == NULL )
{
cerr << "At: " << __FILE__ << "\nLine: " << __LINE__ << endl;
throw "Head Point is NULL!\n";
}
int currentTime = 0; //当前时间
bool isCpuBusy = false; //CPU忙碌状态
Event *readyQueue = new Event; //包含头结点,就绪队列
readyQueue->next = NULL;
while ( eventHead->next != NULL )
{
Event *firstEvent = FetchFirstEvent( eventHead );
currentTime = firstEvent->happenTime;
if ( firstEvent->type == ARRIVALEVENT )
{
if ( isCpuBusy == true )
{
InsertTail( readyQueue, firstEvent );
}
else
{
isCpuBusy = true;
Event *finishEvent = new Event;
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = currentTime;
finishEvent->happenTime = currentTime + firstEvent->job.needTime;
finishEvent->remainTime = 0;
CopyJob( &(finishEvent->job), &(firstEvent->job) );
if ( firstEvent != NULL )
delete firstEvent;//删除正在执行事件节点
firstEvent = NULL;
InsertByHappenTime( eventHead, finishEvent );
}
continue ;
}
if ( firstEvent->type == FINISHEVENT )
{
ShowEvent( firstEvent );
if ( firstEvent != NULL )
delete firstEvent;//删除已执行事件节点
firstEvent = NULL;
isCpuBusy = false;
SortByHRR( readyQueue, currentTime );
Event *hrrEvent = FetchFirstEvent( readyQueue );
if ( hrrEvent != NULL )
{
isCpuBusy = true;
Event *finishEvent = new Event();
finishEvent->type = FINISHEVENT;
finishEvent->jobBeginTime = currentTime;
finishEvent->happenTime = currentTime + hrrEvent->job.needTime;
finishEvent->remainTime = hrrEvent->job.needTime;
CopyJob( &(finishEvent->job), &(hrrEvent->job) );
if ( hrrEvent != NULL )
delete hrrEvent;//删除正在执行事件节点
hrrEvent = NULL;
InsertByHappenTime( eventHead, finishEvent );
}
}
}
}
测试数据
运行结果
一、最短作业时间优先
二、最短剩余时间优先
三、最高响应比优先
四、优先级调度
五、时间片轮转
时间片=1
时间片=4
总结与体会
根据流程图,一步一步实现功能,思路清晰,就不会出错。PS:C#程序的可视化及其调度算法采用LINQ实现,将在下章讲解。
专科的前端有前途吗?
刚接触Spring框架,一个Method method直接把我看晕了
非常细致,好评!
热门考点啊,好多公司真题都有这道