最低松弛度优先LLF（Least Laxity First）算法

大家好，欢迎来到IT知识分享网。

算法介绍：

可抢占调度方式

任务优先级：任务紧急程度越高，赋予该任务的优先级就越高。任务A松弛度：任务A必须完成的时间（任务A的deadline），任务A运行时间，当前时间，

A的松弛度 = A必须完成的时间-A运行需要的时间-当前时间；

实时任务就绪队列：按照松弛度排序，最紧急的任务（松弛度最低的）排在最前面，调度程序选择队列中的队首任务执行。某一任务的松弛度变为0时，立即切换。

选一些任务入队列：所选任务应该满足的条件：任务的开始时间小于等于当前时间

队列中任务的排序（从队首到队尾）：计算每个任务的 T’ = 任务的deadlineTime – 任务完成需要的时间，按照 T’从小到大依次从队首排到队尾。（这个T’是不断变化的，因为，任务完成需要的时间是变化的,某个进程若运行了一段时间，那么任务完成需要的时间等于任务需要的时间减去已经运行的时间）

调度：从上述的队列中选择T’最小的，即选择队首进程运行；切换，切换至T’等于当前时间的进程；队列中，

初始化：当前时间t = 1;选择队列队首进程运行

循环至时间结束

while(t <= MAX_T){

if 找到某个进程的T’ == 当前时间t_now operation

        (终止当前运行进程，切换至该进程) ,t++,continue;

if(当前运行进程运行还没有结束）（继续运行当前进程，当前进程运行时间+1）；

else t++，当前进程出队，continue；

新的进程入队；

更新T’

}

另一种想法—数组模拟

任务task结构体，task存储每个任务的开始时间startTime、结束时间deadlinTime，最完晚开始时间lastStartTime，当前运行时间

所有任务存储到数组中，按照startTime作为第一关键字进行升序排列，再按照lastStartTime作为第二关键字进行升序排列。

设当前时间是t_now;

初始化，找startTime<=t_now的元素序号index，再选择lastStartTime最小的元素，事实上，这就是第一个数组元素进程；

循环，每次循环结束t_now++，终止条件是t_now<t_max

循环体……1st：更新index，从index开始搜，找到第一个startTime小于t_now的元素下标 2nd：0-index之间有无进程lastStartTime等于t_now，有则切换到该进程  3rd : 当前进程是否执行完  4th 更新T’

参考别人的思路，

再次整理思路：任务松弛度 = 必须完成的时间-本身的运行时间-当前时间，式中，本身的运行时间是指任务运行还需要多少时间，本身的运行时间等于必须完成的时间减去任务最迟必须开始运行的时间，假如任务已经被调度执行了一段时间，则其本身运行的时间等于任务的处理总时间减去任务已经运行的时间，

LLF算法实现如下：

进程结构体：

//进程结构体 typedef struct process //进程 { char pname[5]; //进程名 int deadtime; //周期 int servetime; //执行时间 //周期进程某一次执行到停止的剩余需执行时间（考虑到抢占），初始为deadtime int lefttime; int cycle; //执行到的周期数 //进程最近一次的最迟开始执行时间，- currenttime 即为松弛度 int latestarttime; //进程下一次最早开始时间 int arivetime; int k; //k=1，表示进程正在运行，否则为0，表示进程不在执行期间 /* 若存在最小松弛度进程个数多于1个， 则采用最近最久未使用算法 采用一计数器LRU_t */ int LRU_t; }process; 

进程名pname，进程周期deadTime，进程执行时间serveTime；进程周期计数cycle，初始化是1，进程最早开始时间arriveTime和最晚开始时间latestsrtTime；进程抢占，进程某次中断后的剩余执行时间leftTime，用于计算松弛度；进程运行状态k，1表示在运行，0表示没有运行；多进程松弛度相同且同为最小时，按照“最近最久未调度”原则进行调度，计数器LRU_t计算每一个进程在调度时，调度与被调度的情况。初始值是0，调度某一进程时，则该进程以外的其他进程均要在计数器上加1。松弛度相同时，选择计数器LRU_t最大的。运行状态位k，的设置可以输出进程的执行开始时间和结束时间，根据k可以输出进程的执行时间段。多进程松弛度相同且为最小时，选择最近最久未使用算法（从最接近队尾的进程中选择为什么会不符合要求）

循环队列的属性及遍历

队列中的进程以数组的形式存储：

队首front，队尾rear，队空front == rear 队满 （rear+1）%queueSize == front，

松弛度计算：

松弛度 = 任务必须完成的时间 – 任务本身的运行时间 – 当前时间；

松弛度 = 周期*需要执行的次数 – （上一次）执行的剩余时间 – 当前时间

松弛度 = deadTime * cycle – leftTime – currentTime;

（可能被中断过）进程最迟开始执行时间latestsrtTime= deadTime*cycle – leftTime

latestartTime – currentTime <= 0即松弛度是0，抢占当前正在运行的进程

最小松弛度进程

遍历队列中的当前时间下可以运行的进程，最早开始时间arriveTime = dead Time*（cycle-1）小于当前时间，比较各进程松弛度，得出最小松弛度进程

进程的抢占

遍历队列，寻找松弛度是0的进程：存在就让其跳出循环，返回该进程；否则，队首指针下移，直至队尾，遍历完都不存在松弛度为0的进程，则返回当前进程；未考虑多个松弛度都为0的情况

时钟

时钟计时法，即在1ms的时间变化时，都要进行LLF进程的选择。即在当前currentTime下，currentTime初始为0，循环++，直到到达执行总时间MAXTIME.

最低松弛度相同且都是最小时，刚刚执行过的进程，此时不再执行，让给其他具有相同最低松弛度的进程–采用最接近队尾的进程，遍历时，当前队列赋给一临时队列，对临时队列进行遍历，选择最接近队尾的进程。任务：周期，执行时间，A:50ms，10ms；B:20ms，10ms；C：50ms，15ms。第80ms执行后还是在执行完B4后，执行B5，而不是A2.

选择最近最久未使用LRU算法，给每一个进程设置一个计数器

currentTime在边界值时的情况

在currentTime == MAXTIME时，可能存在进程正好要开始执行：100ms时，A进程要开始执行，但是不应该让其开始执行，所以应该做临界处理；同理，可能存在进程正在执行，此时应该输出该进程在没有完成其周期执行时间下的运行时间段

当前时间没有进程运行的情况

加入只有一个进程，周期是20ms，执行时间是10ms，10-20ms、30-40ms、50-60ms时，没有进程运行的情况，即此时最低松弛度的进程为空

参考链接

最低松弛度优先调度算法 – 爱生活，爱编程 – 博客园

 //最低松弛度调度算法LLF #include <stdio.h> #include <iostream> #include <stdlib.h> #include <ctype.h> #include <string.h> #include <math.h> #define queuesize 10 #define MAXTIME 150 //考虑前100ms时间 #define MINLLF 9999 #define PRO_LRU_T 0 using namespace std; //进程结构体 typedef struct process //进程 { char pname[5]; //进程名 int deadtime; //周期 int servetime; //执行时间 //周期进程某一次执行到停止的剩余需执行时间（考虑到抢占），初始为deadtime int lefttime; int cycle; //执行到的周期数 //进程最近一次的最迟开始执行时间，- currenttime 即为松弛度 int latestarttime; //进程下一次最早开始时间 int arivetime; int k; //k=1，表示进程正在运行，否则为0，表示进程不在执行期间 /* 若存在最小松弛度进程个数多于1个， 则采用最近最久未使用算法 采用一计数器LRU_t */ int LRU_t; }process; typedef struct sueue //循环队列 { process* data[queuesize]; int front, rear; } sueue; //初始化n个进程 void Initprocess(process* pro, int n) { int i; process* p = pro; for (i = 0; i < n; i++) { *(p->pname) = '\0'; p->deadtime = 0; p->servetime = 0; p->lefttime = 0; p->cycle = 0; p->latestarttime = 0; p->arivetime = 0; p->k = 0; p->LRU_t = 0; p++; } } //初始化队列（队空） void InitQueue(sueue* que) { que->front = que->rear = 0; } //进程进入循环队列 void enterQueue(sueue* que, process* pro) { //判断循环队列是否已满 if ((que->rear + 1) % queuesize == que->front) printf("队列已满!\n"); else { que->data[que->rear] = pro; //进程放入队尾 que->rear = (que->rear + 1) % queuesize; //队尾指针加1 printf("%s成功入队!\n", pro->pname); //显示进程入队 } } //从当前队列中找到最低松弛度的进程 process* llf(sueue* dui, int currenttime) { sueue* q1 = dui; process* currentpro, * pro; int minllf = MINLLF, llf; int pro_LRU_t = PRO_LRU_T; int front = q1->front, rear = q1->rear; //队首元素？？ //将队首进程赋给当前进程 currentpro = q1->data[front]; if (currenttime <= MAXTIME) { //求最短松弛度currentpro，如果队列中只有一个进程 if (front == rear) { return currentpro; printf("%dms时%s%d进程的松弛度为：%d\n", currenttime, currentpro->pname, currentpro->cycle, llf); } //进程数目多于一个 else { /* 找当前时间下可以开始执行的进程中松弛度最小的， 赋给currentpro. 当最小松弛度的进程多于1个， 我们采用的是最后1个最小松弛度进程? */ do { if (front != rear) { pro = q1->data[front]; if (pro->arivetime <= currenttime && currenttime <= MAXTIME) { //计算松弛度 = 周期*需执行的次数- （上一次）执行的时间 -当前时间 llf = (pro->deadtime) * (pro->cycle) - pro->lefttime - currenttime; printf("%dms时%s%d进程的松弛度为：%d\n", currenttime, pro->pname, pro->cycle, llf); if (minllf >= llf) //比较得出最低松弛度 { if (pro->LRU_t >= pro_LRU_t) { pro_LRU_t = pro->LRU_t; minllf = llf; currentpro = pro; } } } front = (front + 1) % queuesize; } else break; } while (front != rear); //检测队列是否遍历完 } } return currentpro; } //寻找松弛度 <=0 的抢占进程，替代当前最小松弛度进程 process* leastlaxityfirst(sueue* dui, int currenttime) { sueue* q1 = dui; process* pro = NULL, * nextpro; int front = q1->front, rear = q1->rear; /* 当队列不空，寻找当前时刻 是否有松弛度为0（需抢占进程）的进程 */ while (front != rear) { nextpro = q1->data[front]; /* pro->latestarttime初始为： (pro->deadtime)*(pro->cycle) - pro->servetime; pro->latestarttime - currenttime 即为松弛度 pro->latestarttime - currenttime <= 0 , 即松弛度 = 0，抢占，跳出循环 */ if (nextpro->latestarttime <= currenttime) break; else front = (front + 1) % queuesize; } //如果队列空，返回pro if (front == rear) return pro; //队列不空，nextpro为此时抢占正在执行的进程的进程 else return nextpro; } //从队列中读取进程的过程 void LLF_Process(sueue* dui) { int currenttime = 0; sueue* que = dui; int front = que->front; int rear = que->rear; process* currentpro, * pro, * tmppro; //currentpro为当前时间队列中松弛度最低的进程 currentpro = llf(que, currenttime); //在MAXTIME时间内考虑 while (currenttime <= MAXTIME) { /* 最低松弛度进程为空， 即为当前时间没有可运行的进程 */ if (currentpro == NULL) { printf("%dms时无可运行进程!\n", currenttime); break; } else { if ((currentpro->arivetime <= currenttime)) { if (currenttime == MAXTIME) { //当进程正在运行 if (currentpro->k == 1) printf("%d ms: %s%d\n\n", currenttime, currentpro->pname, currentpro->cycle); //当此时没有进程运行 else printf("\n=======执行只考虑前%dms，现时间已到%dms了！======\n", currenttime, currenttime); break; } else if (currenttime != MAXTIME) { if (currentpro->k == 0) { printf("=> %dms时刻%s%d进程开始执行: %d - ", currenttime, currentpro->pname, currentpro->cycle, currenttime); currentpro->k = 1; //表明进程开始运行 do { if (front != rear) { pro = que->data[front]; if (pro != currentpro) pro->LRU_t++; front = (front + 1) % queuesize; } else break; } while (front != rear); } currenttime++; //当前时间增加 currentpro->lefttime--; //运行剩余时间减少 //当剩余运行时间等于0, 即当程序运行结束 if (currentpro->lefttime == 0) { if (currentpro->k == 1) { printf("%d ms: %s%d\n\n", currenttime, currentpro->pname, currentpro->cycle); currentpro->k = 0; //表明进程开始进入不执行状态 } currentpro->cycle++; currentpro->lefttime = currentpro->servetime; currentpro->arivetime = (currentpro->deadtime) * (currentpro->cycle - 1); currentpro->latestarttime = (currentpro->deadtime) * (currentpro->cycle) - (currentpro->servetime); currentpro = llf(que, currenttime); } //当进程未运行完毕。。。（可能被抢占） else { //pro为抢占当前正执行进程的进程 pro = leastlaxityfirst(que, currenttime); if (pro != NULL) { /* 如果当前存在抢占进程， 即pro != currentpro， 则使currentpro进程进入不执行状态 */ if (pro != currentpro) { if (currentpro->k == 1) currentpro->k = 0; printf("%d ms: %s%d\n\n", currenttime, currentpro->pname, currentpro->cycle); printf("%dms时%s%d进程被进程%s%d进程抢占！\n", currenttime, currentpro->pname, currentpro->cycle, pro->pname, pro->cycle); } /* 使currentpro为松弛度最小的进程， 不论是否是抢占程序。 */ currentpro = pro; } } } } //当进程下一次开始时间还没到 else if (currentpro->arivetime >= currenttime) { if (currenttime == MAXTIME) { printf("\n=======执行只考虑前%dms，现时间已到%dms了！======\n", currenttime, currenttime); break; } else { printf("第%dms时没有进程到达!\n"); currenttime++; currentpro = llf(que, currenttime); } } } } } int main() { sueue* dui, * dui2; process* pro, pro2[queuesize], * pro3; int front, rear, ci = 0, pi = 0; int flag = 1, i; char ch, ch2, name[5]; printf("\n*最低松弛调度\n\n"); dui = (sueue*)malloc(sizeof(sueue)); dui->rear = dui->front = 0; dui2 = (sueue*)malloc(sizeof(sueue)); dui2->rear = dui2->front = 0; while (1) { i = 0; InitQueue(dui); Initprocess(pro2, queuesize); printf("请输入周期进程有关的信息:\n"); while (flag) { pro = pro2 + i; printf("\n请输入进程名（长度小于5）:"); gets(name); strcpy(pro->pname, name); printf("\n请输入进程的周期:"); scanf("%d", &(pro->deadtime)); getchar(); printf("\n请输入进程的执行时间:"); scanf("%d", &(pro->servetime)); getchar(); pro->lefttime = pro->servetime; // pro->cycle = 1; //初始时进程从第一周期开始执行 pro->latestarttime = (pro->deadtime) * (pro->cycle) - pro->servetime; //进程下一次最迟开始执行的时间 pro->arivetime = (pro->deadtime) * (pro->cycle - 1); // 进程下一次开始的最早时间 pro->k = 0; enterQueue(dui, pro); //进队列 i++; //进程个数 printf("\n是否继续进程信息的输入(0:结束,1:继续):"); scanf("%d", &flag); getchar(); } dui2 = dui; front = dui2->front; rear = dui2->rear; while (front != rear) { pro3 = dui2->data[front]; ci = pro3->servetime + ci; //各进程执行的时间总和 pi = pro3->deadtime + pi; //各周期总和 front = (front + 1) % queuesize; } //根据实时系统的要求：(ci/pi)<=1 if ((ci / pi) <= 1) { LLF_Process(dui); printf("\n进程运行完毕!\n"); printf("\n"); printf("是否要结束使用(Y/N)?"); scanf("%c", &ch); getchar(); if ('Y' == toupper(ch)) { printf("\n 任意键结束! "); scanf("%c", &ch2); exit(0); } else flag = 1; } else { printf("所输入的进程不满足要求! "); printf("\n是否重新输入(Y/N):\n"); scanf("%c", &ch); getchar(); if ('N' == toupper(ch)) { printf("请按任意键结束\n"); exit(0); } } } return 0; } 

删去注释的代码

//最低松弛度调度算法LLF #include <stdio.h> #include <iostream> #include <stdlib.h> #include <ctype.h> #include <string.h> #include <math.h> #define queuesize 10 #define MAXTIME 150 #define MINLLF 9999 #define PRO_LRU_T 0 using namespace std; typedef struct process { char pname[5]; int deadtime; int servetime; int lefttime;int cycle; int latestarttime; int arivetime;int k; int LRU_t; }process; typedef struct sueue { process* data[queuesize];int front, rear; } sueue; void Initprocess(process* pro, int n) { int i; process* p = pro; for (i = 0; i < n; i++) { *(p->pname) = '\0';p->deadtime = 0;p->servetime = 0; p->lefttime = 0;p->cycle = 0;p->latestarttime = 0; p->arivetime = 0;p->k = 0;p->LRU_t = 0; p++; } } void InitQueue(sueue* que) { que->front = que->rear = 0; } void enterQueue(sueue* que, process* pro) { if ((que->rear + 1) % queuesize == que->front) printf("队列已满!\n"); else { que->data[que->rear] = pro;que->rear = (que->rear + 1) % queuesize; printf("%s成功入队!\n", pro->pname); } } process* llf(sueue* dui, int currenttime) { sueue* q1 = dui;process* currentpro, * pro;int minllf = MINLLF, llf; int pro_LRU_t = PRO_LRU_T;int front = q1->front, rear = q1->rear; currentpro = q1->data[front]; if (currenttime <= MAXTIME) { if (front == rear) { return currentpro; } else { do { if (front != rear) { pro = q1->data[front]; if (pro->arivetime <= currenttime && currenttime <= MAXTIME) { llf = (pro->deadtime) * (pro->cycle) - pro->lefttime - currenttime; printf("%dms时%s%d进程的松弛度为：%d\n", currenttime, pro->pname, pro->cycle, llf); if (minllf >= llf) { if (pro->LRU_t >= pro_LRU_t) { pro_LRU_t = pro->LRU_t;minllf = llf;currentpro = pro; } } } front = (front + 1) % queuesize; } else break; } while (front != rear); } } return currentpro; } process* leastlaxityfirst(sueue* dui, int currenttime) { sueue* q1 = dui;process* pro = NULL, * nextpro; int front = q1->front, rear = q1->rear; while (front != rear) { nextpro = q1->data[front]; if (nextpro->latestarttime <= currenttime) break; else front = (front + 1) % queuesize; } if (front == rear) return pro; else return nextpro; } void LLF_Process(sueue* dui) { int currenttime = 0;sueue* que = dui; int front = que->front;int rear = que->rear; process* currentpro, * pro, * tmppro; currentpro = llf(que, currenttime); while (currenttime <= MAXTIME) { if (currentpro == NULL) { printf("%dms时无可运行进程!\n", currenttime); break; } else { if ((currentpro->arivetime <= currenttime)) { if (currenttime == MAXTIME) { if (currentpro->k == 1) printf("%d ms: %s%d\n\n", currenttime, currentpro->pname, currentpro->cycle); else printf("\n=======执行只考虑前%dms，现时间已到%dms了！======\n", currenttime, currenttime); break; } else if (currenttime != MAXTIME) { if (currentpro->k == 0) { printf("=> %dms时刻%s%d进程开始执行: %d - ", currenttime, currentpro->pname, currentpro->cycle, currenttime); currentpro->k = 1; do { if (front != rear) { pro = que->data[front]; if (pro != currentpro) pro->LRU_t++; front = (front + 1) % queuesize; } else break; } while (front != rear); } currenttime++; currentpro->lefttime--; if (currentpro->lefttime == 0) { if (currentpro->k == 1) { printf("%d ms: %s%d\n\n", currenttime, currentpro->pname, currentpro->cycle);currentpro->k = 0; } currentpro->cycle++;currentpro->lefttime = currentpro->servetime; currentpro->arivetime = (currentpro->deadtime) * (currentpro->cycle - 1); currentpro->latestarttime = (currentpro->deadtime) * (currentpro->cycle) - (currentpro->servetime); currentpro = llf(que, currenttime); } else { pro = leastlaxityfirst(que, currenttime); if (pro != NULL) { if (pro != currentpro) { if (currentpro->k == 1) currentpro->k = 0; printf("%d ms: %s%d\n\n", currenttime, currentpro->pname, currentpro->cycle); printf("%dms时%s%d进程被进程%s%d进程抢占！\n", currenttime, currentpro->pname, currentpro->cycle, pro->pname, pro->cycle); } currentpro = pro; } } } } else if (currentpro->arivetime >= currenttime) { if (currenttime == MAXTIME) { printf("\n=======执行只考虑前%dms，现时间已到%dms了！======\n", currenttime, currenttime); break; } else { printf("第%dms时没有进程到达!\n");currenttime++;currentpro = llf(que, currenttime); } } } } } int main() { sueue* dui, * dui2;process* pro, pro2[queuesize], * pro3; int front, rear, ci = 0, pi = 0,flag = 1, i;char ch, ch2, name[5]; printf("\n*最低松弛调度\n\n"); dui = (sueue*)malloc(sizeof(sueue));dui->rear = dui->front = 0; dui2 = (sueue*)malloc(sizeof(sueue));dui2->rear = dui2->front = 0; while (1) { i = 0; InitQueue(dui);Initprocess(pro2, queuesize); printf("请输入周期进程有关的信息:\n"); while (flag) { pro = pro2 + i; printf("\n请输入进程名（长度小于5）:"); gets(name); strcpy(pro->pname, name); printf("\n请输入进程的周期:"); scanf("%d", &(pro->deadtime)); getchar(); printf("\n请输入进程的执行时间:"); scanf("%d", &(pro->servetime)); getchar(); pro->lefttime = pro->servetime; // pro->cycle = 1; pro->latestarttime = (pro->deadtime) * (pro->cycle) - pro->servetime; pro->arivetime = (pro->deadtime) * (pro->cycle - 1); pro->k = 0; enterQueue(dui, pro); i++; printf("\n是否继续进程信息的输入(0:结束,1:继续):"); scanf("%d", &flag); getchar(); } dui2 = dui; front = dui2->front; rear = dui2->rear; while (front != rear) { pro3 = dui2->data[front]; ci = pro3->servetime + ci; pi = pro3->deadtime + pi; front = (front + 1) % queuesize; } if ((ci / pi) <= 1) { LLF_Process(dui); printf("\n进程运行完毕!\n"); printf("\n"); printf("是否要结束使用(Y/N)?"); scanf("%c", &ch); getchar(); if ('Y' == toupper(ch)) { printf("\n 任意键结束! "); scanf("%c", &ch2); exit(0); } else flag = 1; } else { printf("所输入的进程不满足要求! "); printf("\n是否重新输入(Y/N):\n"); scanf("%c", &ch); getchar(); if ('N' == toupper(ch)) { printf("请按任意键结束\n"); exit(0); } } } return 0; }