吉林⼤学操作系统上机（实验⼆：处理机调度——实时调度算法EDF和RMS）每做⼀个实验都不禁感叹奇妙⾮常，以下仅为学习记录，不⾜出错欢迎指出 实验⼆处理机调度——实时调度算法EDF和RMS
实验⽬的
深⼊理解处理机调度算法，了解硬实时概念，掌握周期性实时任务调度算法EDF(Earliest Deadline First)和RMS(Rate Monotonic Scheduling)的可调度条件，并能在可调度情况下给出具体调度结果。 实验内容
在Linux环境中采⽤⽤户级线程模拟实现EDF和RMS两种实时调度算法。给定⼀组实时任务，按照EDF算法和RMS算法分别判断是否可调度，在可调度的情况下，创建⼀组⽤户级线程，分别代表各个实时任务，并按算法确定的调度次序安排各个线程运⾏，运⾏时在终端上画出其Gantt图。为避免图形绘制冲淡算法，Gantt图可⽤字符表⽰。 实验准备
EDF算法和RMS算法的可调度条件及调度原则。
在Linux环境中创建⽤户级线程的函数。
EDF算法和RMS的可调度条件及调度原则
EDF(Earliest Deadline First)为可抢先式调度算法，其调度条件为sum(Ci/Ti)≤1；
该算法是根据任务的开始截⽌时间来确定任务的优先级。截⽌时间愈早，其优先级愈⾼。 该算法要求在系统中保持⼀个实时任务就绪队列，具有最早截⽌时间的任务排在队列的最前⾯。调度程序在选择任务时，总是选择就绪队列中的第⼀个任务，为之分配处理机，使之投⼊运⾏。最早截⽌时间优先算法既可⽤于抢占式调度，也可⽤于⾮抢占式调度⽅式中。
RMS算法为不可抢先调度算法，其调度条件为sum(Ci/Ti)≤n(exp(ln(2)/n)-1)。任务按单调速率优先级分配（RMPA）的调度算法，称为单调速率调度（RMS）。RMPA是指任务的优先级按任务周期T来分配。它根据任务的执⾏周期的长短来决定调度优先级，那些具有⼩的执⾏周期的任务具有较⾼的优先级，周期长的任务优先级低。
在Linux环境中创建⽤户级线程的函数
创建⽤户级线程的库函数为：
int pthread_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 * (*START_ROUTINE)(void *)指明了线程的⼊⼝，是⼀个只有⼀个(void *)参数的函数；
第四个参数 void * ARG是传给线程⼊⼝函数的参数。
实验设计
实时任务⽤task数据结构描述，设计四个函数：select_proc()⽤于实现调度算法，被选中任务执⾏proc()，在没有可执⾏任务时执⾏
idle()，主函数mian()初始化相关数据，创建实时任务并对任务进⾏调度。
为模拟调度算法，给每个线程设置⼀个等待锁，暂不运⾏的任务等待在相应的锁变量上。主线程按调度算法唤醒⼀个⼦线程，被选中线程执⾏⼀个时间单位，然后将控制权交给主线程判断是否需要重新调度。
实验代码
#include"math.h"
#include"sched.h"
#include"pthread.h"
#include"stdlib.h"
#include"semaphore.h"
#include"stdio.h"
通讯体裁#include<unistd.h>
typedef struct{//实时任务描述
char task_id;
int call_num;//任务发⽣次数
int ci;// Ci
int ti;//Ti
int ci_left;
int ti_left;
int flag;//任务是否活跃，0否，2是
int arg;//参数
pthread_t th;//任务对应线程
}task;
void proc(int* args);
void*idle();
int select_proc();
int task_num =0;
int idle_num =0;
int alg;//所选算法，1 for EDF，2 for RMS
int curr_proc=-1;
int demo_time =100;//演⽰时间
task* tasks;
pthread_mutex_t proc_wait[100];
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(&idle_wait,NULL);
pthread_mutex_lock(&idle_wait);//下次执⾏lock等待
printf("Please input number of real time tasks:\n");
scanf("%d",&task_num);
tasks =(task*)malloc(task_num*sizeof(task));
int i;
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("Please input task id, followed by Ci and Ti:\n"); getchar();
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("Please input algorithm, 1 for EDF, 2 for RMS:"); getchar();
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 %lf\n",r);
}
if(sum>r)
{//不可调度
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(&tasks[i].th,NULL,(void*)proc,&tasks[i].arg);
for(i=0;i<demo_time;i++)
{
int j;
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);
};
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);
ocd>栗东生
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)&&(tasks[curr_proc].flag!=0)) return curr_proc;
for(j=0;j<task_num;j++)
{
if(tasks[j].flag==2)
{
switch(alg)
{
case1://EDF算法
if(temp1>tasks[j].ti_left)
{
temp1=tasks[j].ti_left;
热力迸发temp2=j;
}
case2://RMS算法
if(temp1>tasks[j].ti)
{
temp1=tasks[j].ti;
temp2=j;
}
}
}
}
return temp2;
}
输出：
输出中，上⽅为EDF算法，下⽅为RMS算法，值得注意的就是 gcc -pthread code_9.c -lm -o 09（验
证的时候代码⼀致不给过好像就是这个-lm）
思考题
上述参考算法中，被选中任务每运⾏⼀个时间单位即将控制权交给主线程，判断是否需要切换实时任务，这可看作发⽣⼀次时钟中断。
实际上时钟中断的发⽣频率远没有这样频繁，因⽽上述调度会产⽣较⼤的开销。改进上述算法，使其只在需要重新调度任务时才返回主控线程。
在上述改进的基础上，对⼀组可调度实时事务，统计对不同调度算法的线程切换次数（不计主线程切换），并将其显⽰出来
我不会，挖坑挖坑，下周就要交实验报告了嗷嗷嗷嗷！
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议