程序设计
一、数据结构
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 );
3.2 进程调度相关函数
/* 插入函数 */void InsertByHappenTime( Event *head, Event *e );void InsertByJobTime( Event *head, Event *e );void InsertByPriority( Event *head, Event *e );void InsertByRemainTime( Event *head, Event *e );void InsertByHRR( Event *head, Event *e );/* 排序函数 */void SortByHRR( Event *head, int currentTime );/* 调度函数 */void SJF ( Event *eventHead );void SRTF( Event *eventHead );void HRRF( Event *eventHead );void Priority(Event *eventHead); //抢占式优先级调度void RR ( Event *eventHead ); //时间片大小为1
程序实现
一、插入函数（用于插入排序）
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;} 1.6 按最高响应比插入
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.7 最高响应比插入排序
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;} 二、调度算法
2.1 最短工作时间优先
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.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 ); } } }} 测试数据
| 进程 | 到达时间 | 服务时间 | 优先级 |
| A | 0 | 3 | 5 |
| B | 2 | 6 | 2 |
| C | 4 | 4 | 3 |
| D | 6 | 5 | 4 |
| E | 8 | 2 | 1 |
运行结果
一、最短作业时间优先
二、最短剩余时间优先
三、最高响应比优先
四、优先级调度
五、时间片轮转
时间片=1
时间片=4
总结与体会
根据流程图，一步一步实现功能，思路清晰，就不会出错。PS：C#程序的可视化及其调度算法采用LINQ实现，将在下章讲解。