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

目录  一.设计目的2二.设计内容2三.设计准备2四.设计过程3五.设计结果并分析12六.系统的结构，原理框图和模块等的详细说明14七.用户使用说明书和参考资料15八.设计体会16一设计目的  深入理解处理机调度算法，了解硬实时概念，掌握最早截止期优先调度算法。EDF(Earliest Deadline First)和速率单调调度算法RMS（Rate Monotonic Scheduling）的可调度条件，并能在可调度情况下给出具体调度结果。二设计内容在Linux环境中采用用户级线程模拟实现EDF和RMS两种实时调度算法。给定一组实时任务，按照EDF算法和RMS算法分别判断是否可调度。在可调度的情况下，创建一组用户级线程，分别代表各个实时任务，并按算法所确定的调度次序安排各个线程运行，运行时在终端上画出其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 *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（），在没有可执行任务时执行idle（），主函数main（）初始化相关数据，创建实时任务并对任务进行调度。 （2）为模拟调度算法，给每个线程设置一个等待锁，暂不执行的任务等待在相应的锁变量上。主线程按调度算法唤醒一个子线程，被选中线程执行一个时间单位，然后将控制权交给主线程判断是否需要重新调度。（3）实验代码 #include"math.h"#include"sched.h"#include"pthread.h"#include"stdio.h"#include"stdlib.h"#include"semaphore.h"typedef struct                /实时任务描述char task_id;int call_num;                  /任务发生次数int 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=100;              /演示时间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);pthread_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 ; i<task_num ; i+)pthread_mutex_init(& proc_waiti , NULL);pthread_mutex_lock(& proc_waiti);for(i=0;i<task_num;i+)printf("Pleased input task id,followed by Ci and Ti:n");scanf("%c,%d,%d,",&tasksi.task_id,& tasksi.ci,& tasksi.ti);tasksi.ci_left=tasksi.ci; tasksi.ti_left=tasksi.ti;tasksi.flag=2;tasksi.arg=i;tasksi.call_num=1;sum=sum+(float)tasksi.ci / (float)tasksi.ti;while(c=getchar()!='n'&&c!=EOF);  /清屏printf("Please input algorithm,1 for EDF,2 for RMS:");scanf("%d",&alg);printf("Please input demo time:");scanf("%d",& demo_time);double r = 1;             /EDF算法，最早截止期优先调度 if(alg = 2)        /RMS算法，速率单调调度r=(double)task_num)*(exp(log(2)/(double)task_num)-1);printf("r is %lfn",r);if(sum>r) / 综合EDF和RMS算法任务不可可调度的情况             /不可调度printf("(sum=%lf>r=%lf),not schedulable!n",sum,r);exit(2);/创建闲逛线程pthread_create(& idle_proc , NULL , (void*)idle , NULL);for(i=0 ;i<task_num ;i+)    /创建实时任务线程pthread_create(&tasksi.th, NULL, (void*)proc, &tasksi.arg);for(i=0;i<demo_time;i+)int j;if(curr_proc=select_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;j<task_num;j+)    /Ti-,直至为0时开始下一周期if(-tasksj.ti_left=0)tasksj.ti_left=tasksj.ti;tasksj.ci_left=tasksj.ci;pthread_create(&tasksj.th,NULL,(void*)proc,&tasksj.arg);tasksj.flag=2;printf("n");sleep(10);void proc(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);          /唤醒主线程;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;j<task_num;j+)if(tasksj.flag=2)switch(alg)case 1:             /EDF算法if(temp1>tasksj.ci_left)temp1=tasksj.ci_left;temp2=j;case 2:          /RMS算法if(temp1>tasksj.ti)temp1=tasksj.ti;temp2=j;return temp2; /return the selected thread or task number;五设计结果并分析 六 系统的结构、原理框图和模块等的详细说明 最早截止期优先调度优先选择完成截止期最早的实时任务。对于新到达的实时任务，如果完成截止期先于正在运行任务的完成截止期，则重新分配处理器，即剥夺。最早截止期优先调度结果（EDF算法） Gantt图a1b1a2b1a3b2a4b2a5.0 10 20 30 45 55 60 70 90 100速度单调调度于1973年提出，面向周期性实时任务，属于非剥夺式调度的范畴。速率单调调度将任务的周期作为调度参数，其发生频率越高。则调度级别越高。速率单调调度结果（RMS算法）Gantt图a1b1c1a2b2a3.a4b3c20 20 60 160 180 220 240 300 320 360 460七用户使用说明书和参考资料 参考文献：左万历，周长林，彭涛编著 计算机操作系统教程徐英慧，马忠梅，王磊，王琳编著ARM9嵌入式系统设计-基于S3C2410与Linux（第三版）唐晓军，李晓红，肖鹏编著 Linux系统及编程基础李刚建，段淼，郑琦编著 C语言程序设计教程八设计体会初步了解了EDF和RMS处理机调度算法，EDF为可抢占式调度，同时为动态调度，是指在程序运行过程中按照优先级调度。RMS为不可抢占式调度，同时为静态调度，即在调度之前就按照某种原则确定好了调度优先级。同时对线程的运行原理有了一定的认识，对运用虚拟机编译程序有了一定的掌握，使得对今后的操作系统的学习和操作奠定了一定的基础。操作系统课程设计总结教师评语：成绩： 指导教师： （注：可编辑下载，若有不当之处，请指正，谢谢!）