题目二：处理机调度-实时调度算法EDF和RMS

./目录一.设计目的∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙2二.设计容∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙2三.设计准备∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙2四.设计过程∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙3五.设计结果并分析∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙12六.系统的结构,原理框图和模块等的详细说明∙∙∙∙∙∙∙∙∙∙∙∙∙∙14七.用户使用说明书和参考资料∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙15八.设计体会∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙16.一．设计目的深入理解处理机调度算法,了解硬实时概念,掌握最早截止期优先调度算法。EDF<EarliestDeadlineFirst>和速率单调调度算法RMS〔RateMonotonicScheduling的可调度条件,并能在可调度情况下给出具体调度结果。二．设计容在Linux环境中采用用户级线程模拟实现EDF和RMS两种实时调度算法。给定一组实时任务,按照EDF算法和RMS算法分别判断是否可调度。在可调度的情况下,创建一组用户级线程,分别代表各个实时任务,并按算法所确定的调度次序安排各个线程运行,运行时在终端上画出其Gantt图。为避免图形绘制冲淡算法,Gantt图可用字符表示。三．设计准备〔理论、技术1.EDF算法和RMS算法的可调度条件及调度原则。〔1EDF为可抢占式调度算法,其调度条件为：sum〔ci/ti≤1〔2RMS算法为不可抢先调度算法,其调度条件为：sum〔ci/ti≤n〔exp〔in〔2/n-12.在linux环境中创建用户级线程的函数。〔1创建用户级线程的库函数为：Intpthread_creat〔pthread_t*THREAD,Pthread_attr_t*ATTR,Void*〔*START_ROUTINE〔void*,Void*ARGpthread_creat〔tid,NULL,func,arg；其中第一个参数是pthread_t型的指针,用于保存线程id；第二个参数是pthread_attr_t的指针,用于说明要创建的线程的属性,NULL表示使用缺省参数；第三个参数指明了线程的入口,是一个只有一个〔void*参数的函数；第四个参数是传给线程入口函数的参数。四．设计过程〔设计思想、代码实现实时任务用task数据结构描述,设计四个函数：Select_proc〔用于实现调度算法,被选中任务执行proc〔,在没有可执行任务时执行idle〔,主函数main〔初始化相关数据,创建实时任务并对任务进行调度。〔2为模拟调度算法,给每个线程设置一个等待锁,暂不执行的任务等待在相应的锁变量上。主线程按调度算法唤醒一个子线程,被选中线程执行一个时间单位,然后将控制权交给主线程判断是否需要重新调度。〔3实验代码#include"math.h"#include"sched.h"#include"pthread.h"#include"stdio.h"#include"stdlib.h"#include"semaphore.h"typedefstruct{//实时任务描述chartask_id;intcall_num;//任务发生次数intci;//任务处理时间intti;//任务发生周期intci_left;intti_left;//recordthereductionofti\ciintflag;//任务是否活跃,0否,2是intarg;//参数pthread_tth;//任务对应线程}task;voidproc<int*args>;void*idle<>;intselect_proc<intalg>;inttask_num=0;intidle_num=0;intalg;//所选算法,1forEDF,2forRMSintcurr_proc=-1;intdemo_time=100;//演示时间task*tasks;pthread_mutex_tproc_wait[10];//thebiggestnumberoftaskspthread_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<"Pleaseinputnumberofrealtimetask:\n">;intc;scanf<"%d",&task_num>;//任务数tasks=<task*>malloc<task_num*sizeof<task>>;while<<c=getchar<>>!='\n'&&c!=EOF>;//清屏inti;for<i=0;i<task_num;i++>{pthread_mutex_init<&proc_wait[i],NULL>;pthread_mutex_lock<&proc_wait[i]>;}for<i=0;i<task_num;i++>{printf<"Pleasedinputtaskid,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;while<<c=getchar<>>!='\n'&&c!=EOF>;//清屏}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<sum>r>//综合EDF和RMS算法任务不可可调度的情况{//不可调度printf<"<sum=%lf>r=%lf>,notschedulable!\n",sum,r>;exit<2>;}//创建闲逛线程pthread_create<&idle_proc,NULL,<void*>idle,NULL>;for<i=0;i<task_num;i++>//创建实时任务线程pthread_create<&tasks[i].th,NULL,<void*>proc,&tasks[i].arg>;for<i=0;i<demo_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;j<task_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_left>0>{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;j<task_num;j++>{if<tasks[j].flag==2>{switch<alg>{case1://EDF算法if<temp1>tasks[j].ci_left>{temp1=tasks[j].ci_left;temp2=j;}case2://RMS算法if<temp1>tasks[j].ti>{temp1=tasks[j].ti;temp2=j;}}}}returntemp2;//returntheselectedthreadortasknumber};五．设计结果并分析系统的结构、原理框图和模块等的详细说明最早截止期优先调度优先选择完成截止期最早的实时任务。对于新到达的实时任务,如果完成截止期先于正在运行任务的完成截止期,则重新分配处理器,即剥夺。最早截止期优先调度结果〔EDF算法Gantt图a1b1a2b1a3b2a4b2a501020304555607090100速度单调调度于1973年提出,面向周期性实时任务,属于非剥夺式调度的畴。速率单调调度将任务的周期作为调度参数,其发生频率越高。则调度级别越高。速率单调调度结果〔RMS算法Gantt图a1b1c1a2b2a3...a4b3c202060160180220240300320360460七．用户使用说明书和参考资料参考文献：左万历,周长林,涛编著计算机操作系统教程徐英慧,马忠梅,王磊,王琳编著ARM9嵌入