《题目二处理机调度实时调度算法EDF和RMS》由会员分享，可在线阅读，更多相关《题目二处理机调度实时调度算法EDF和RMS（21页珍藏版）》请在装配图网上搜索。
1、目录 一.设计目的2二.设计内容2三.设计准备2四.设计过程3五.设计结果并分析12六.系统的结构，原理框图和模块等的详细说明14七.用户使用说明书和参考资料15八.设计体会16一设计目的 深入理解处理机调度算法，了解硬实时概念，掌握最早截止期优先调度算法。EDF(Earliest Deadline First)和速率单调调度算法RMS（Rate Monotonic Scheduling）的可调度条件，并能在可调度情况下给出具体调度结果。二设计内容在Linux环境中采用用户级线程模拟实现EDF和RMS两种实时调度算法。给定一组实时任务，按照EDF算法和RMS算法分别判断是否可调度。在可调度的情
2、况下，创建一组用户级线程，分别代表各个实时任务，并按算法所确定的调度次序安排各个线程运行，运行时在终端上画出其Gantt图。为避免图形绘制冲淡算法，Gantt图可用字符表示。三设计准备（理论、技术） 1.EDF算法和RMS算法的可调度条件及调度原则。（1）EDF为可抢占式调度算法，其调度条件为：sum（ci/ti）1（2）RMS算法为不可抢先调度算法，其调度条件为：sum（ci/ti）n（exp（in（2）/n）-1）2.在linux环境中创建用户级线程的函数。（1）创建用户级线程的库函数为：Int pthread_creat（pthread_t *THREAD，Pthread_attr_t
3、*ATTR，Void *（*START_ROUTINE）（void*），Void *ARG） pthread_creat（tid，NULL，func，arg）；其中第一个参数是pthread_t型的指针，用于保存线程id；第二个参数是pthread_attr_t的指针，用于说明要创建的线程的属性，NULL表示使用缺省参数；第三个参数指明了线程的入口，是一个只有一个（void *）参数的函数；第四个参数是传给线程入口函数的参数。四设计过程（设计思想、代码实现） （1） 实时任务用task数据结构描述，设计四个函数：Select_proc（）用于实现调度算法，被选中任务执行proc（），在没有可执
4、行任务时执行idle（），主函数main（）初始化相关数据，创建实时任务并对任务进行调度。 （2）为模拟调度算法，给每个线程设置一个等待锁，暂不执行的任务等待在相应的锁变量上。主线程按调度算法唤醒一个子线程，被选中线程执行一个时间单位，然后将控制权交给主线程判断是否需要重新调度。（3）实验代码#includemath.h#includesched.h#includepthread.h#includestdio.h#includestdlib.h#includesemaphore.htypedef struct /实时任务描述char task_id;int call_num; /任务发生次数i
5、nt ci; /任务处理时间int ti; /任务发生周期int ci_left;int ti_left; /record the reduction of ti ciint flag; /任务是否活跃,0否，2是int arg; /参数pthread_t th; /任务对应线程task;void proc(int *args);void *idle();int select_proc(int alg);int task_num=0;int idle_num=0;int alg; /所选算法，1 for EDF，2 for RMSint curr_proc=-1;int demo_time=1
6、00; /演示时间task *tasks;pthread_mutex_t proc_wait10; /the biggest number of taskspthread_mutex_t main_wait,idle_wait;float sum=0;pthread_t idle_proc;int main(int argc,char *argv)pthread_mutex_init(& main_wait , NULL);pthread_mutex_lock(& main_wait); /下次执行lock等待pthread_mutex_init(& idle_wait , NULL);pth
7、read_mutex_lock(& idle_wait); /下次执行lock等待printf(Please input number of real time task:n);int c;scanf(%d,& task_num); /任务数tasks=(task *)malloc(task_num *sizeof(task);while(c=getchar()!=n& c!=EOF); /清屏int i;for(i=0 ; itask_num ; i+)pthread_mutex_init(& proc_waiti , NULL);pthread_mutex_lock(& proc_wait
8、i);for(i=0;ir) / 综合EDF和RMS算法任务不可可调度的情况 /不可调度printf(sum=%lfr=%lf),not schedulable!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+)int j;if(curr_proc=select
9、_proc(alg)!=-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;p
10、rintf(%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+
11、;pthread_mutex_unlock(&main_wait); /唤醒主线程;int select_proc(int alg)int j;int temp1,temp2;temp1=10000;temp2=-1;if(alg=2)&(curr_proc!=-1)&(taskscurr_proc.flag!=0)return curr_proc;for(j=0;jtasksj.ci_left)temp1=tasksj.ci_left;temp2=j;case 2: /RMS算法if(temp1tasksj.ti)temp1=tasksj.ti;temp2=j;return temp2; /
12、return the selected thread or task number;五设计结果并分析 六 系统的结构、原理框图和模块等的详细说明 最早截止期优先调度优先选择完成截止期最早的实时任务。对于新到达的实时任务，如果完成截止期先于正在运行任务的完成截止期，则重新分配处理器，即剥夺。最早截止期优先调度结果（EDF算法） Gantt图a1b1a2b1a3b2a4b2a5.0 10 20 30 45 55 60 70 90 100速度单调调度于1973年提出，面向周期性实时任务，属于非剥夺式调度的范畴。速率单调调度将任务的周期作为调度参数，其发生频率越高。则调度级别越高。速率单调调度结果（R
13、MS算法）Gantt图a1b1c1a2b2a3.a4b3c20 20 60 160 180 220 240 300 320 360 460七用户使用说明书和参考资料 参考文献：左万历，周长林，彭涛编著 计算机操作系统教程徐英慧，马忠梅，王磊，王琳编著ARM9嵌入式系统设计-基于S3C2410与Linux（第三版）唐晓军，李晓红，肖鹏编著 Linux系统及编程基础李刚建，段淼，郑琦编著 C语言程序设计教程八设计体会初步了解了EDF和RMS处理机调度算法，EDF为可抢占式调度，同时为动态调度，是指在程序运行过程中按照优先级调度。RMS为不可抢占式调度，同时为静态调度，即在调度之前就按照某种原则确定好了调度优先级。同时对线程的运行原理有了一定的认识，对运用虚拟机编译程序有了一定的掌握，使得对今后的操作系统的学习和操作奠定了一定的基础。操作系统课程设计总结教师评语：成绩： 指导教师： （注：可编辑下载，若有不当之处，请指正，谢谢!）
题目二处理机调度实时调度算法EDF和RMS
