《操作系统实验课：实验二 处理机调度-实时调度算法EDF和RMS》由会员分享，可在线阅读，更多相关《操作系统实验课：实验二 处理机调度-实时调度算法EDF和RMS（24页珍藏版）》请在金锄头文库上搜索。
1、实验二处理机调度实时调度算法EDF和RMS实验目的实验内容实验准备实验设计参考代码实验结果思考题实验目的深入理解处理机调度算法，了解硬实时概念，掌握周期性实时任务调度算法EDF(EarliestDeadlineFirst)和RMS(RateMonotonicScheduling)的可调度条件，并能在可调度情况下给出具体调度结果。实验内容在Linux环境中采用用户级线程模拟实现EDF和RMS两种实时调度算法。给定一组实时任务，按照EDF算法和RMS算法分别判断是否可调度，在可调度的情况下，创建一组用户级线程，分别代表各个实时任务，并按算法确定的调度次序安排各个线程运行，运行时在终端上画出其Gan
2、tt图。为避免图形绘制冲淡算法，Gantt图可用字符表示。实验准备EDF算法和RMS算法的可调度条件及调度原则。在Linux环境中创建用户级线程的函数。EDF算法和RMS算法的可调度条件及调度原则EDF为可抢先式调度算法，其调度条件为sum(Ci/Ti)1；RMS算法为不可抢先调度算法，其调度条件为sum(Ci/Ti)n(exp(ln(2)/n)-1)。在Linux环境中创建用户级线程的函数创建用户级线程的库函数为：intpthread_create(pthread_t*THREAD,pthread_attr_t*ATTR,void*(*START_ROUTINE)(void*),void*A
3、RG)pthread_create(tid,NULL,func,arg)；其中第一个参数是pthread_t型的指针，用于保存线程id；第二个参数是pthread_attr_t的指针，用于说明要创建的线程的属性，NULL表示使用缺省属性；第三个参数指明了线程的入口，是一个只有一个(void*)参数的函数；第四个参数是传给线程入口函数的参数。实验设计实时任务用task数据结构描述，设计四个函数：select_proc()用于实现调度算法，被选中任务执行proc()，在没有可执行任务时执行idle()，主函数mian()初始化相关数据，创建实时任务并对任务进行调度。为模拟调度算法，给每个线程设置一
4、个等待锁，暂不运行的任务等待在相应的锁变量上。主线程按调度算法唤醒一个子线程，被选中线程执行一个时间单位，然后将控制权交给主线程判断是否需要重新调度。参考代码#includemath.h#includesched.h#includepthread.h#includestdlib.h#includesemaphore.htypedefstruct/实时任务描述chartask_id;intcall_num;/任务发生次数intci;/Ciintti;/Tiintci_left;intti_left;intflag;/任务是否活跃，0否，2是intarg;/参数pthread_tth;/任务对应线
5、程task;voidproc(int*args);void*idle();intselect_proc();inttask_num=0;intidle_num=0;intalg;/所选算法，1forEDF，2forRMSintcurr_proc=-1;intdemo_time=100;/演示时间task*tasks;pthread_mutex_tproc_wait100;pthread_mutex_tmain_wait,idle_wait;floatsum=0;pthread_tidle_proc;intmain(intargc,char*argv)pthread_mutex_init(&ma
6、in_wait,NULL);pthread_mutex_lock(&main_wait);/下次执行lock等待pthread_mutex_init(&idle_wait,NULL);pthread_mutex_lock(&idle_wait);/下次执行lock等待printf(Pleaseinputnumberofrealtimetasks:n);scanf(%d,&task_num);tasks=(task*)malloc(task_num*sizeof(task);inti;for(i=0;itask_num;i+)pthread_mutex_init(&proc_waiti,NULL
7、);pthread_mutex_lock(&proc_waiti);for(i=0;ir)/不可调度printf(sum=%lfr=%lf),notschedulable!n,sum,r);exit(2);pthread_create(&idle_proc,NULL,(void*)idle,NULL);/创建闲逛线程for(i=0;itask_num;i+)/创建实时任务线程pthread_create(&tasksi.th,NULL,(void*)proc,&tasksi.arg);for(i=0;idemo_time;i+)intj;if(curr_proc=select_proc(alg
8、)!=-1)/按调度算法选线程pthread_mutex_unlock(&proc_waitcurr_proc);/唤醒pthread_mutex_lock(&main_wait);/主线程等待else/无可运行任务，选择闲逛线程pthread_mutex_unlock(&idle_wait);pthread_mutex_lock(&main_wait);for(j=0;j0)pthread_mutex_lock(&proc_wait*args);/等待被调度if(idle_num!=0)printf(idle(%d),idle_num);idle_num=0;printf(%c%d,task
9、s*args.task_id,tasks*args.call_num);tasks*args.ci_left-;/执行一个时间单位if(tasks*args.ci_left=0)printf(%d),tasks*args.ci);tasks*args.flag=0;tasks*args.call_num+;pthread_mutex_unlock(&main_wait);/唤醒主线程;void*idle()while(1)pthread_mutex_lock(&idle_wait);/等待被调度printf(-);/空耗一个时间单位idle_num+;pthread_mutex_unlock(
10、&main_wait);/唤醒主控线程;intselect_proc(intalg)intj;inttemp1,temp2;temp1=10000;temp2=-1;if(alg=2)&(curr_proc!=-1)&(taskscurr_proc.flag!=0)returncurr_proc;for(j=0;jtasksj.ci_left)temp1=tasksj.ci_left;temp2=j;case2:/RMS算法if(temp1tasksj.ti)temp1=tasksj.ti;temp2=j;returntemp2;实验结果/编译gcc-lpthread-lmtest_sched
11、uler.c-osheduler.out书中例1算法EDF结果书中例2算法RMS结果书中第三章习题27算法EDF结果书中第三章习题27算法RMS结果书中例1算法EDF结果rootlocalhosttest#./scheduler.outPleaseinputnumberofrealtimetasks:2Pleaseinputtaskid,followedbyCiandTi:a,10,20,Pleaseinputtaskid,followedbyCiandTi:b,25,50,Pleaseinputalgorithm,1forEDF,2forRMS:1Pleaseinputdemotime:20
12、0a1a1a1a1a1a1a1a1a1a1(10)b1b1b1b1b1b1b1b1b1b1a2a2a2a2a2a2a2a2a2a2(10)b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1(25)a3a3a3a3a3a3a3a3a3a3(10)b2b2b2b2b2a4a4a4a4a4a4a4a4a4a4(10)b2b2b2b2b2b2b2b2b2b2a5a5a5a5a5a5a5a5a5a5(10)b2b2b2b2b2b2b2b2b2b2(25)a6a6a6a6a6a6a6a6a6a6(10)b3b3b3b3b3b3b3b3b3b3a7a7a7a7a7a7a7a7a7a7(10)b3b
13、3b3b3b3b3b3b3b3b3b3b3b3b3b3(25)a8a8a8a8a8a8a8a8a8a8(10)b4b4b4b4b4a9a9a9a9a9a9a9a9a9a9(10)b4b4b4b4b4b4b4b4b4b4a10a10a10a10a10a10a10a10a10a10(10)b4b4b4b4b4b4b4b4b4b4(25)书中例2算法RMS结果rootlocalhosttest#./scheduler.outPleaseinputnumberofrealtimetasks:3Pleaseinputtaskid,followedbyCiandTi:a,20,100,Pleaseinpu
14、ttaskid,followedbyCiandTi:b,40,150,Pleaseinputtaskid,followedbyCiandTi:c,100,350,Pleaseinputalgorithm,1forEDF,2forRMS:2Pleaseinputdemotime:400ris0.779763a1a1a1a1a1a1a1a1a1a1a1a1a1a1a1a1a1a1a1a1(20)b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1(40)c1c1c1c1c1c1c1c1c1c
15、1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1c1(100)a2a2a2a2a2a2a2a2a2a2a2a2a2a2a2a2a2a2a2a2(20)b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2
16、b2b2b2b2b2(40)a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3(20)-idle(60)a4a4a4a4a4a4a4a4a4a4a4a4a4a4a4a4a4a4a4a4(20)b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3(40)c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2c2书中第三章习题27算法EDF结果rootlocal
17、hosttest#./scheduler.outPleaseinputnumberofrealtimetasks:3Pleaseinputtaskid,followedbyCiandTi:a,10,30,Pleaseinputtaskid,followedbyCiandTi:b,15,40,Pleaseinputtaskid,followedbyCiandTi:c,5,50,Pleaseinputalgorithm,1forEDF,2forRMS:1Pleaseinputdemotime:300c1c1c1c1c1(5)a1a1a1a1a1a1a1a1a1a1(10)b1b1b1b1b1b1b
18、1b1b1b1b1b1b1b1b1(15)a2a2a2a2a2a2a2a2a2a2(10)b2b2b2b2b2b2b2b2b2b2b2b2b2b2b2(15)c2c2c2c2c2(5)a3a3a3a3a3a3a3a3a3a3(10)-idle(10)b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3(15)a4a4a4a4a4a4a4a4a4a4(10)c3c3c3c3c3(5)-idle(10)a5a5a5a5a5a5a5a5a5a5(10)b4b4b4b4b4b4b4b4b4b4b4b4b4b4b4(15)-idle(5)c4c4c4c4c4(5)a6a6a6a6a6a6a6a6
19、a6a6(10)b5b5b5b5b5b5b5b5b5b5b5b5b5b5b5(15)a7a7a7a7a7a7a7a7a7a7(10)-idle(10)c5c5c5c5c5(5)b6b6b6b6b6a8a8a8a8a8a8a8a8a8a8(10)b6b6b6b6b6b6b6b6b6b6(15)-idle(10)a9a9a9a9a9a9a9a9a9a9(10)c6c6c6c6c6(5)b7b7b7b7b7b7b7b7b7b7b7b7b7b7b7(15)a10a10a10a10a10a10a10a10a10a10(10)b8b8b8b8b8b8b8b8b8b8b8b8b8b8b8(15)-书中第三章
20、习题27算法RMS结果rootlocalhosttest#./scheduler.outPleaseinputnumberofrealtimetasks:3Pleaseinputtaskid,followedbyCiandTi:a,10,30,Pleaseinputtaskid,followedbyCiandTi:b,15,40,Pleaseinputtaskid,followedbyCiandTi:c,5,50,Pleaseinputalgorithm,1forEDF,2forRMS:2Pleaseinputdemotime:300ris0.779763(sum=0.808333r=0.779763),notschedulable!思考题上述参考算法中，被选中任务每运行一个时间单位即将控制权交给主线程，判断是否需要切换实时任务，这可看作发生一次时钟中断。实际上时钟中断的发生频率远没有这样频繁，因而上述调度会产生较大的开销。改进上述算法，使其只在需要重新调度任务时才返回主控线程。在上述改进的基础上，对一组可调度实时事务，统计对不同调度算法的线程切换次数（不计主线程切换），并将其显示出来
