题目二：处理机调度—实时调度算法EDF和RMS40703.pdf

《题目二：处理机调度—实时调度算法EDF和RMS40703.pdf》由会员分享，可在线阅读，更多相关《题目二：处理机调度—实时调度算法EDF和RMS40703.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

3、*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（）用于实现调

4、度算法，被选中任务执行 proc（），在没有可执行任务时执行 idle（），主函数 main（）初始化相关数据，创建实时任务并对任务进行调度。（2）为模拟调度算法，给每个线程设置一个等待锁，暂不执行的任务等待在相应的锁变量上。主线程按调度算法唤醒一个子线程，被选中线程执行一个时间单位，然后将控制权交给主线程判断是否需要重新调度。（3）实验代码#includemath.h#includesched.h#includepthread.h#includestdio.h#includestdlib.h#includesemaphore.h typedef struct /实时任务描述 char tas

5、k_id;int call_num;/任务发生次数 int ci;/任务处理时间 int ti;/任务发生周期 int ci_left;int ti_left;/record the reduction of ti ci int 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 RMS int cu

6、rr_proc=-1;int demo_time=100;/演示时间 task*tasks;pthread_mutex_t proc_wait10;/the biggest number of tasks pthread_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(&

7、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;itask_num;i+)pthread_mutex_init(&proc_waiti,NULL);pthread_mutex_lock(&p

8、roc_waiti);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;

10、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+;

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;/r

12、eturn the selected thread or task number;五设计结果并分析 六系统的结构、原理框图和模块等的详细说明 最早截止期优先调度优先选择完成截止期最早的实时任务。对于新到达的实时任务，如果完成截止期先于正在运行任务的完成截止期，则重新分配处理器，即剥夺。最早截止期优先调度结果（EDF 算法）Gantt 图 a1 b1 a2 b1 a3 b2 a4 b2 a5.0 10 20 30 45 55 60 70 90 100 速度单调调度于 1973 年提出，面向周期性实时任务，属于非剥夺式调度的畴。速率单调调度将任务的周期作为调度参数，其发生频率越高。则调度级别越高。

13、速率单调调度结果（RMS 算法）Gantt 图 a1 b1 c1 a2 b2 a3.a4 b3 c2 0 20 60 160 180 220 240 300 320 360 460 七用户使用说明书和参考资料 参考文献：左万历，周长林，涛编著 计算机操作系统教程 徐英慧，马忠梅，王磊，王琳编著 ARM9 嵌入式系统设计-基于 S3C2410 与 Linux（第三版）唐晓军，晓红，肖鹏编著 Linux 系统及编程基础 刚建，段淼，琦编著 C 语言程序设计教程 八设计体会 初步了解了 EDF 和 RMS 处理机调度算法，EDF 为可抢占式调度，同时为动态调度，是指在程序运行过程中按照优先级调度。RMS 为不可抢占式调度，同时为静态调度，即在调度之前就按照某种原则确定好了调度优先级。同时对线程的运行原理有了一定的认识，对运用虚拟机编译程序有了一定的掌握，使得对今后的操作系统的学习和操作奠定了一定的基础。操作系统课程设计总结 教师评语：成绩：指导教师：