CFS的调度程序

CFS（Completely Fair Scheduler，CFS）

完全公平调度程序 Linux 2623 内核附带了一个模块化调度程序内核和一个被实现为调度模块的完全公平调度程序（Completely Fair Scheduler，CFS）。

Linux 2623 内核的调度程序为其他调度模块并行处理内核打好了基础（这里所说的 “模块化” 并不意味着将调度程序分解为若干可加载的模块，而是指代码本身模块化）。有关调度程序工作原理的更多细节，请参考 developerWorks 文章 “Inside the Linux scheduler”（参见本文末尾 参考资料 小节中的链接）。 最新版调度程序引入的主要特性包括：

模块化调度程序完全公平调度程序（Completely Fair Scheduler，CFS）CFS 组调度 模块化调度程序

调度类的引入显著增强了内核调度程序的可扩展性。这些类（调度程序模块）封装了调度策略。这个调度程序将调度策略模块化，但是与 Pluggable CPU 调度程序框架不同的是，并没有把调度程序本身模块化（后者在内核编译时选择默认调度程序，而通过在启动时向内核传递参数来使用其他 CPU 调度程序）。

CFS

完全公平调度程序（CFS）试图按照对 CPU 时间的 “最大需求（gravest need）” 运行任务；这有助于确保每个进程可以获得对 CPU 的公平共享。如果某个任务休眠时间 “非常短”，那么 CFS 不会将该任务视为休眠任务 — 短暂休眠的进程可能会获得一些额外时间，但是决不会超过它的未休眠时间。

CFS 组调度

考虑一个两用户示例，用户 A 和用户 B 在一台机器上运行作业。用户 A 只有两个作业正在运行，而用户 B 正在运行 48 个作业。组调度使 CFS 能够对用户 A 和用户 B 进行公平调度，而不是对系统中运行的 50 个作业进行公平调度。每个用户各拥有 50% 的 CPU 使用。用户 B 使用自己 50% 的 CPU 分配运行他的 48 个作业，而不会占用属于用户 A 的另外 50% 的 CPU 分配。

CFS 调度模块（在 kernel/sched_fairc 中实现）用于以下调度策略：SCHED_NORMAL、SCHED_BATCH 和 SCHED_IDLE。对于 SCHED_RR 和 SCHED_FIFO 策略，将使用实时调度模块（该模块在 kernel/sched_rtc 中实现）。

鉴于以下原因，需要对策略作出一些更改：

更好地支持服务器和台式机调度。 提供用户要求的新特性。改进启发式（heuristic）处理。vanilla 调度程序使用启发式处理可以更轻易地实现调度。同样，如果启发式处理错误估测了场景，将导致意料之外的行为。

实验三 进程调度

一、实验目的

在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理机数时，就必须依照某种策略来决定那些进程优先占用处理机。本实验模拟在单处理机情况下的处理机调度，帮助学生加深了解处理机调度的工作。

二、实验内容

设计一个时间片轮转调度算法实现处理机调度的程序。

三、实验指导

1实验中使用的数据结构：

1)PCB进程控制块

其中包括参数①进程名name；②要求运行时间runtime；③优先数prior；④状态state；⑤已运行时间runedtime。

2)为简单起见，只设运行队列，就绪链表两种数据结构，进程的调度在这两个队列中切换，如图31所示。

图31PCB链表

2运行结果，包括各个进程的运行顺序，每次占用处理机的运行时间

3每个进程运行时间随机产生，为1~20之间的整数。

4时间片的大小由实验者自己定义，可为3或5。

四、实验要求

1在上机前写出全部源程序；

2能在机器上正确运行程序。

五、程序清单

六、运行结果

七、调试分析及实验心得

我的回答和这位老兄的差不多

例题：有以下的进程需要调度执行(见表2-5)：

表2-5　进程调度

进程名 到达时间 运行时间

P1 00 9

P2 04 4

P3 10 1

P4 55 4

P5 7 2

1)如果用非抢占式短进程优先调度算法，请问这5个进程的平均周转时间是多少

2)如果采用抢占式短进程优先调度算法，请问这5个进程的平均周转时间是多少

A．862；634

B．862；68

C．1062；634

D．1062；68

非抢占式：

进程名 到达时间 运行时间 开始时间 结束时间 周转时间

P1 00 9 00 90 9

P2 04 4 120 160 156

P3 10 1 90 100 9

P4 55 4 160 200 145

P5 7 2 100 120 5

平均周转时间为(9+156+9+145+5)/5=1062

抢占式：

进程名 到达时间 运行时间 开始时间 结束时间 周转时间

Pl 00 9 00 200 20

P2 04 4 04 54 5

P3 10 1 10 20 1

P4 55 4 55 115 6

P5 7 2 70 90 2

平均周转时间为(20+5+1+6+2)/5=68

因此答案选D

这个优先级可以描述为: 优先级 = (作业已等待时间 + 作业的服务时间) / 作业的服务时间

从上式可以看到，作业的服务时间是固定的， 优先级随着已等待时间的提高而变大 。（我这人很公平的，每执行一轮我都看看下一轮谁最应该被执行）

(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。

(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。

(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。

多级反馈队列调度算法体现了计算思维的调度特点，应用了先来先服务原则、应用时间片等做法使得每个申请者都能及时使用资源，是一种很好的协调整体的解决方案。 （我喜欢你，因此把你的事放在第一队列，但我也有其他的事，不能一直帮你做事。帮你做了一段时间就得把你放到第二队列队尾去。等我把所有第一队列的事都做完了，到了第二队列轮到你了再帮你做，这次要比第一队列做的更长一点。如果这段时间内还是做不完，那就得把你放到第三队列的队尾了，依次类推）

注：在队列中是按照先来先服务的原则

进程间通信主要包括管道, 系统IPC(包括消息队列,信号量,共享存储), SOCKET

管道包括三种:

1)普通管道PIPE, 通常有种限制,一是半双工,只能单向传输;二是只能在父子进程间使用

2)流管道s_pipe: 去除了第一种限制,可以双向传输

3)命名管道:name_pipe, 去除了第二种限制,可以在许多并不相关的进程之间进行通讯

系统IPC的三种方式类同,都是使用了内核里的标识符来识别

当没有足够的物理内存的时候，系统通过把进程的一部分转移到硬盘上以设法容纳进程，当再次需要进程中被转移到硬盘中的那一部分时，再返回到物理内存中，这个过程就被称为页面调度。 它使得系统在有限的物理内存环境下也能具备多任务处理的能力 。

1 理想页面置换算法(OPT):

这是一种理想的算法，在实际中不可能实现。

该算法的思想是：发生缺页时，所调出的页应该是以后不再访问的页(永远不会再使用)或最长时间内不再被访问的内存页面(距当前最长时间后再访问的页)予以淘汰。

2先进先出页面置换算法(FIFO)：

即字面意思很好理解，当发生缺页时，把先进来的先淘汰。

思路：选择最先进入内存的页面予以淘汰。

线程的实现可分为两大类，用户级线程（user-levelthread，ULT）和内核级线程（kernel-levelthread，KLT）。后者又称为内核支持的线程或轻量级进程。

>

#include "stdioh"

#include "stdlibh"

#include "stringh"

struct PCB {

char NAME[10]; /进程名/

int ROUND; /进程轮转时间片/

int REACHTIME; /进程到达时间/

int CPUTIME; /进程占用CPU时间/

int COUNT; /计数器/

int NEEDTIME; /进程完成还要的CPU时间/

char STATE; /进程的状态/

struct PCB NEXT; /链指针/

};

struct LINK { /PCB的链结构/

struct PCB RUN; /当前运行进程指针/

struct PCB READY; /就绪队列头指针/

struct PCB TAIL; /就绪队列尾指针/

struct PCB FINISH; /完成队列头指针/

};

void INIT(LINK ); /对PCB的链结构初始化/

void INSERT(LINK ); /将执行了一个单位时间片数且还未完成的进程的PCB插到就绪队列的队尾/

void FIRSTIN(LINK ); /将就绪队列中的第一个进程投入运行/

void PRINT(LINK ); /打印每执行一个时间片后的所有进程的状态/

void PR(PCB ); /打印一个进程的状态/

int CREATE(LINK ,int); /创建新的进程/

void ROUNDSCH(LINK ); /按时间片轮转法调度进程/

void main() {

LINK pcbs;

int i;

INIT(&pcbs);

i=0;

printf("创建5个进程\n\n");

while(i<5) {

if(CREATE(&pcbs,i+1)==1) {

printf("进程已创建\n\n");

i++;

}

else

printf("进程创建失败\n\n");

}

FIRSTIN(&pcbs);

ROUNDSCH(&pcbs);

}

void ROUNDSCH(LINK p) {

PCB pcb;

while(p->RUN!=NULL) {

pcb=(PCB )malloc(sizeof(PCB));

strcpy(pcb->NAME,p->RUN->NAME);

pcb->ROUND=p->RUN->ROUND;

pcb->REACHTIME=p->RUN->REACHTIME;

pcb->CPUTIME=p->RUN->CPUTIME;

pcb->COUNT=p->RUN->COUNT;

pcb->NEEDTIME=p->RUN->NEEDTIME;

pcb->STATE=p->RUN->STATE;

pcb->NEXT=p->RUN->NEXT;

pcb->CPUTIME++;

pcb->NEEDTIME--;

pcb->COUNT++;

if(pcb->NEEDTIME==0) {

pcb->NEXT=p->FINISH->NEXT;

p->FINISH->NEXT=pcb;

pcb->STATE='F';

p->RUN=NULL;

if(p->READY!=p->TAIL)

FIRSTIN(p);

}

else {

p->RUN=pcb;

if(pcb->COUNT==pcb->ROUND) {

pcb->COUNT=0;

if(p->READY!=p->TAIL) {

pcb->STATE='W';

INSERT(p);

FIRSTIN(p);

}

}

}

PRINT(p);

}

}

void INIT(LINK p) {

p->RUN=NULL;

p->TAIL=p->READY=(PCB )malloc(sizeof(PCB));

p->READY->NEXT=NULL;

p->FINISH=(PCB )malloc(sizeof(PCB));

p->FINISH->NEXT=NULL;

}

int CREATE(LINK p,int n) {

PCB pcb,q;

pcb=(PCB )malloc(sizeof(PCB));

flushall();

printf("请输入第%d个进程的名称：\n",n);

gets(pcb->NAME);

printf("请输入第%d个进程的轮转时间片数：\n",n);

scanf("%d",&(pcb->ROUND));

printf("请输入第%d个进程的到达时间：\n",n);

scanf("%d",&(pcb->REACHTIME));

pcb->CPUTIME=0;

pcb->COUNT=0;

printf("请输入第%d个进程需运行的时间片数：\n",n);

scanf("%d",&(pcb->NEEDTIME));

pcb->STATE='W';

pcb->NEXT=NULL;

if(strcmp(pcb->NAME,"")==0||pcb->ROUND<=0||pcb->NEEDTIME<=0) /输入错误/

return 0;

q=p->READY;

while(q->NEXT!=NULL&&q->NEXT->REACHTIME<=pcb->REACHTIME)

q=q->NEXT;

pcb->NEXT=q->NEXT;

q->NEXT=pcb;

if(pcb->NEXT==NULL)

p->TAIL=pcb;

return 1;

}

void FIRSTIN(LINK p) {

PCB q;

q=p->READY->NEXT;

p->READY->NEXT=q->NEXT;

q->NEXT=NULL;

if(p->READY->NEXT==NULL)

p->TAIL=p->READY;

q->STATE='R';

p->RUN=q;

}

void INSERT(LINK p) {

PCB pcb;

pcb=(PCB )malloc(sizeof(PCB));

strcpy(pcb->NAME,p->RUN->NAME);

pcb->ROUND=p->RUN->ROUND;

pcb->REACHTIME=p->RUN->REACHTIME;

pcb->CPUTIME=p->RUN->CPUTIME;

pcb->COUNT=p->RUN->COUNT;

pcb->NEEDTIME=p->RUN->NEEDTIME;

pcb->STATE=p->RUN->STATE;

pcb->NEXT=p->RUN->NEXT;

p->TAIL->NEXT=pcb;

p->TAIL=pcb;

p->RUN=NULL;

pcb->STATE='W';

}

void PRINT(LINK p) {

PCB pcb;

printf("执行一个时间片后的所有进程的状态：\n\n");

if(p->RUN!=NULL)

PR(p->RUN);

if(p->READY!=p->TAIL) {

pcb=p->READY->NEXT;

while(pcb!=NULL) {

PR(pcb);

pcb=pcb->NEXT;

}

}

pcb=p->FINISH->NEXT;

while(pcb!=NULL) {

PR(pcb);

pcb=pcb->NEXT;

}

}

void PR(PCB p) {

printf("进程名：%s\n",p->NAME);

printf("进程轮转时间片：%d\n",p->ROUND);

printf("进程到达时间：%d\n",p->REACHTIME);

printf("进程占用CPU时间：%d\n",p->CPUTIME);

printf("计数器：%d\n",p->COUNT);

printf("进程完成还要的CPU时间：%d\n",p->NEEDTIME);

printf("进程的状态：%c\n\n",p->STATE);

}

#include<stdioh>

struct pcb

{

char name;

int time;

};

void main()

{

int n,i,j,flag=1;

struct pcb a[100];

printf("输入程序个数：");

scanf("%d",&n);

getchar();/接收回车/

for(i=0;i<n;i++)

{

printf("输入程序的名字：如A B C\n");

scanf("%c",&a[i]name);

getchar();/接收回车/

printf("输入占用的时间片：");

scanf("%d",&a[i]time);

getchar();/接收回车/

}

i=0;

while(flag && n>0)

{

if(a[i]time!=0)

{

printf("%c",a[i]name);

a[i]time--;

}

for(j=0;j<n;j++)

if(a[j]time)

{

flag=1;

break;

}

else

flag=0;

i=(++i)%n;

}

}

作业调度程序是管理任务的系统，作业调度程序的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程插入就绪队列，准备执行。

#include “stdioh”

#define running 1 // 用running表示进程处于运行态

#define aready 2 // 用aready表示进程处于就绪态

#define blocking 3 // 用blocking表示进程处于阻塞态

#define sometime 5 // 用sometime表示时间片大小

#define n 10 //假定系统允许进程个数为n

struct

{

int name; //进程标识符

int status; //进程状态

int ax,bx,cx,dx ; //进程现场信息，通用寄存器内容

int pc ; //进程现场信息，程序计数器内容

int psw; //进程现场信息，程序状态字内容

int next; //下一个进程控制块的位置

}pcbarea[n]; //模拟进程控制块区域的数组

int PSW, AX,BX,CX,DX , PC ,TIME ; //模拟寄存器

int run; //定义指向正在运行进程的进程控制块的指针

struct

{

int head;

int tail;

}ready; //定义就绪队列的头指针head和尾指针tail

int pfree; //定义指向空闲进程控制块队列的指针

scheduling( ) //进程调度函数

{

int i;

if (readyhead==-1) //空闲进程控制块队列为空，退出

{

printf(“无就绪进程\n”);

return;

}

i=readyhead; //就绪队列头指针赋给i

readyhead=pcbarea[readyhead]next; //就绪队列头指针后移

if(readyhead==-1) readytail=-1; //就绪队列为空，修正尾指针readytail

pcbarea[i]status=running; //修改进程控制块状态

TIME=sometime; //设置相对时钟寄存器

//恢复该进程现场信息

AX=pcbarea[run]ax;

BX=pcbarea[run]bx;

CX=pcbarea[run]cx;

DX=pcbarea[run]dx;

PC=pcbarea[run]pc;

PSW=pcbarea[run]psw;

run=i;

}//进程调度函数结束

create(int x) //进程创建函数

{

int i;

if(pfree==-1) //空闲进程控制块队列为空

{

printf(“无空闲进程控制块，进程创建失败\n”);

return;

}

i=pfree; //取空闲进程控制块队列的第一个

pfree=pcbarea[pfree]next; // pfree后移

//填写该进程控制块的内容

pcbarea[i]name=x;

pcbarea[i]status=aready;

pcbarea[i]ax=x;

pcbarea[i]bx=x;

pcbarea[i]cx=x;

pcbarea[i]dx=x;

pcbarea[i]pc=x;

pcbarea[i]psw=x;

if (readyhead!=-1) //就绪队列不为空时，挂入就绪队列的方式

{

pcbarea[readytail]next=i;

readytail=i;

pcbarea[readytail]next=-1;

}

else //就绪队列为空时，挂入就绪队列的方式

{

readyhead=i;

readytail=i;

pcbarea[readytail]next=-1;

}

}//进程创建函数结束

main()

{ //系统初始化

int num,i,j;

run=readyhead=readytail =-1;

pfree=0;

for(j=0;j<n-1;j++)

pcbarea[j]next=j+1;

pcbarea[n-1]next=-1;

printf(“输入进程编号（避免编号冲突，以负数输入结束，最多可以创建10个进程）：\n”);

scanf(“%d”,&num);

while(num>=0)

{

create(num) ;

scanf(“%d”,&num) ;

}

scheduling(); //进程调度

if(run!=-1)

{

printf(“进程标识符 进程状态 寄存器内容：ax bx cx dx pc psw:\n”);

printf(“%8d%10d%3d%3d%3d%3d%3d%3d\n”, pcbarea[run]name, pcbarea[run]status, pcbarea[run]ax, pcbarea[run]bx, pcbarea[run]cx, pcbarea[run]dx, pcbarea[run]pc, pcbarea[run]psw);

}

}//main()结束

我用的是vc++60的，你可以试试，有不懂得在和我交流吧

以上就是关于CFS的调度程序全部的内容，包括:CFS的调度程序、如何用C语言编写:设计一个时间片轮转调度算法实现处理机调度的程序、 *** 作系统（一）等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！