实验二处理机调度

实验二处理机调度——实时调度算法EDF和RMS•实验目的•实验内容•实验准备•实验设计•参考代码•实验结果•思考题实验目的•深入理解处理机调度算法，了解硬实时概念，掌握周期性实时任务调度算法EDF(EarliestDeadlineFirst)和RMS(RateMonotonicScheduling)的可调度条件，并能在可调度情况下给出具体调度结果。实验内容•在Linux环境中采用用户级线程模拟实现EDF和RMS两种实时调度算法。给定一组实时任务，按照EDF算法和RMS算法分别判断是否可调度，在可调度的情况下，创建一组用户级线程，分别代表各个实时任务，并按算法确定的调度次序安排各个线程运行，运行时在终端上画出其Gantt图。为避免图形绘制冲淡算法，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*ARG)•pthread_create(tid,NULL,func,arg)；•其中第一个参数是pthread_t型的指针，用于保存线程id；第二个参数是pthread_attr_t的指针，用于说明要创建的线程的属性，NULL表示使用缺省属性；第三个参数指明了线程的入口，是一个只有一个(void*)参数的函数；第四个参数是传给线程入口函数的参数。实验设计•实时任务用task数据结构描述，设计四个函数：select_proc()用于实现调度算法，被选中任务执行proc()，在没有可执行任务时执行idle()，主函数mian()初始化相关数据，创建实时任务并对任务进行调度。•为模拟调度算法，给每个线程设置一个等待锁，暂不运行的任务等待在相应的锁变量上。主线程按调度算法唤醒一个子线程，被选中线程执行一个时间单位，然后将控制权交给主线程判断是否需要重新调度。参考代码#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;//任务对应线程}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_wait[100];pthread_mutex_tmain_wait,idle_wait;floatsum=0;pthread_tidle_proc;intmain(intargc,char**argv){pthread_mutex_init(&main_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_wait[i],NULL);pthread_mutex_lock(&proc_wait[i]);}for(i=0;itask_num;i++){printf(Pleaseinputtaskid,followedbyCiandTi:\n);scanf(%c,%d,%d,,&tasks[i].task_id,&tasks[i].ci,&tasks[i].ti);tasks[i].ci_left=tasks[i].ci;tasks[i].ti_left=tasks[i].ti;tasks[i].flag=2;tasks[i].arg=i;tasks[i].call_num=1;sum=sum+(float)tasks[i].ci/(float)tasks[i].ti;}printf(Pleaseinputalgorithm,1forEDF,2forRMS:);scanf(%d,&alg);printf(Pleaseinputdemotime:);scanf(%d,&demo_time);doubler=1;//EDF算法if(alg==2){//RMS算法r=((double)task_num)*(exp(log(2)/(double)task_num)-1);printf(ris%lf\n,r);}if(sumr){//不可调度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(&tasks[i].th,NULL,(void*)proc,&tasks[i].arg);for(i=0;idemo_time;i++){intj;if((curr_proc=select_proc(alg))!=-1){//按调度算法选线程pthread_mutex_unlock(&proc_wait[curr_proc]);//唤醒pthread_mutex_lock(&main_wait);//主线程等待}else{//无可运行任务，选择闲逛线程pthread_mutex_unlock(&idle_wait);pthread_mutex_lock(&main_wait);}for(j=0;jtask_num;j++){//Ti--，为0时开始下一周期if(--tasks[j].ti_left==0){tasks[j].ti_left=tasks[j].ti;tasks[j].ci_left=tasks[j].ci;pthread_create(&tasks[j].th,NULL,(void*)proc,&tasks[j].arg);tasks[j].flag=2;}}}printf(\n);sleep(10);};voidproc(int*args){while(tasks[*args].ci_left0){pthread_mutex_lock(&proc_wait[*args]);//等待被调度if(idle_num!=0){printf(idle(%d),idle_num);idle_num=0;}printf(%c%d,tasks[*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(&main_wait);//唤醒主控线程}};intselect_proc(intalg){intj;inttemp1,temp2;temp1=10000;temp2=-1;if((alg==2)&&(curr_proc!=-1)&&(tasks[curr_proc].flag!=0))returncurr_proc;for(j=0;jtask_num;j++){if(tasks[j].flag==2){switch(alg){case1://EDF算法if(temp1tasks[j].ci_left){temp1=tasks[j].ci_left;temp2=j;}case2://RMS算法if(temp1tasks[j].ti){temp1=tasks[j].ti;temp2=j;}}}}returntemp2;}实验结果•//编译•gcc-lpthread-lmtest_scheduler.c-osheduler.out•书中例1算法EDF结果•书中例2算法RMS结果•书中第三章习题27算法EDF结果•书中第三章习题27算法RMS结果书中例1算法EDF结果[root@localhosttest]#./scheduler.outPleaseinputnumberofrealtimetasks:2Pleaseinputtaskid,followedbyCiandTi:a,10,20,Pleaseinputtaskid,followedbyCiandTi:b,25,50,Pleaseinputalgorithm,1forEDF,2forRMS:1Pleaseinputdemotime:200a1a1a1a1a1a1a1a1a1a1(10)b1b1b1b1b1b1b1b1b1b1a2a2a2a2a2a2a2a2a2a2(10)b1b1b1b1b1b1b1b1b1b1b1b1b1b1b1(25)a3a3a3a3a3a3a3a3a3a3(10)b2b2b2b2b2a4a4a4a4a4a4a4a4a4a4(10)b2b2b2b2b2b2b2b2b2b2a5a5a5a5a5a5a5a5a5a5(10)b2b2b2b2b2b2b2b2b2b2(25)a6a6a6a6a6a6a6a6a6a6(10)b3b3b3b3b3b3b3b3b3b3a7a7a7a7a7a7a7a7a7a7(10)b3b3b3b3b3b3b3b3b3b3b3b3b3b3b3(25)a8a8a8a8a8a8a8a8a8a8(10)b4b4b4b4b4a9a9a9a9a9a9a9a9a9a9(10)b4b4b4b4b4b4b4b4b4b4a10a10a10a10a10a10a10a10a10a10(10)b4b4b4b4b4b4b4b4b4b4(25)书中例2算法RMS结果[root@localhosttest]#./scheduler.outPleaseinputnumberofrealtimetasks:3Pleaseinputtaskid,followedbyCiandTi:a,20,100,Pleaseinputtaskid,followedbyCiandTi:b,40,150,Pleaseinputtaskid,followedbyCiandTi:c,100,350,Pleaseinputalgorithm,1