吉林大学操作系统上机（实验三：存储管理——动态不等 长存储资源分配算法）

每做一个实验都不禁感叹奇妙非常，以下仅为学习记录，不足出错欢迎指出

实验二 处理机调度——实时调度算法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;  // Ciint 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);
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){case 1:    //EDF算法if(temp1>tasks[j].ti_left){temp1=tasks[j].ti_left;temp2=j;}case 2:    //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）参考博客：显式链接

思考题

• 上述参考算法中，被选中任务每运行一个时间单位即将控制权交给主线程，判断是否需要切换实时任务，这可看作发生一次时钟中断。实际上时钟中断的发生频率远没有这样频繁，因而上述调度会产生较大的开销。改进上述算法，使其只在需要重新调度任务时才返回主控线程。
• 在上述改进的基础上，对一组可调度实时事务，统计对不同调度算法的线程切换次数（不计主线程切换），并将其显示出来

我不会，挖坑挖坑，下周就要交实验报告了嗷嗷嗷嗷！