counter是什么意思

操作系统（五）--CPU的调度策略

调度

CPU调度就是当前进程需要进⾏IO操作或者时间⽚结束了，如何从就绪队列中选择下⼀个执⾏的过程。

1.1FIFO

先⼊先出，根据队列的前后顺序执⾏。类似于银⾏和⾷堂排队，但是有问题，如果⼀个⼈只是简单的询问这样的算法肯定对他不公平。

1.2Priority（优先级）

给每个进程都设置优先级，根据优先级来选取下⼀个执⾏的进程。对于⼀些时间短的任务可以适当增加它的优先级，但是事先怎么知道它要

执⾏多长时间也是个问题；⽽且如果⼀个⼈询问的时间越来越长怎么办？其实也就是不知道它具体的时间，这样优先级还要可变，对于上述

这些问题如何设计其调度策略呢？

1.3调度算法的优劣

对于银⾏，调度算法设计的⽬标应该是让客户满意，让客户满意就不能让他等太久；对于CPU，就是让进程满意，即不能让进程在就绪队列

⾥⾯很久都没有执⾏。如何能让进程满意？

1）尽快结束任务：周转时间（任务进⼊到结束的时间）短。

2）⽤户操作尽快响应：响应时间（从操作发⽣到响应）短。

3）系统内耗时间少：吞吐量（任务的完成量）⼤。

总原则：系统专注于任务执⾏，⼜能合理调配任务。

1.4冲突

响应时间⼩-》切换次数多-》系统内耗⼤-》吞吐量⼩

因此调度算法需要折中、综合。

1.5前台任务与后台任务

前台任务指的是与⽤户交互的任务，这部分任务要求响应时间⼩。后台任务指的是在CPU的任务，要求周转时间⼩。因此调度算法必须考虑

这点。

1.6IO约束型和CPU约束型

IO约束型的任务指的是经常要进⾏IO操作的任务，这些任务每次使⽤CPU的时间短，但是频率⾼，相应的优先级就得⾼，这样才能实现

CPU与IO的并⾏操作。

CPU约束型的任务指每次使⽤CPU的时间都⽐较长，切换次数少，这样的任务就优先级就相对低⼀些；其实前台任务就属于IO约束型任

务，后台任务属于CPU约束型任务。

2.调度算法

2.1SJF:短作业优先

作业执⾏时间短的放在前⾯先执⾏，这种⽅式可以较好的满⾜周转时间，但是响应时间不好。

2.2RR：按时间⽚来轮转调度

这种⽅式可以较好的满⾜响应时间，但是时间⽚的选取时间要好好考虑。

时间⽚⼤：响应时间太长；时间⽚⼩：吞吐量少，因为内耗⼤了。

折衷：时间⽚10~100ms，切换时间0.1~1ms（1%）

2.3响应时间与周转时间同时存在

直观想法：定义前台任务和后台任务两个队列，因为前台任务更看重响应时间，所以使⽤RR，后台任务更看重周转时间，采⽤SJF，只有

当前台任务没有的时候才调度后台任务，但是这样会有很多问题？⽐如前台任务⼀直存在，那么后台任务是不是永远不执⾏了？执⾏⼀个后

台任务的时间⼀般⽐较长，那么是不是这段时间就不响应前台任务？

对于第⼀个问题，给任务设置优先级，前台任务的优先级⼤于后台任务优先级，⾸先执⾏优先级⾼的任务，随着时间的增长，后台任务优先

级动态升⾼，这样后台任务才有执⾏的机会。

对于第⼆个问题，采⽤时间⽚的⽅式，后台任务执⾏⼀段时间之后就跳到下⼀个任务。

除此之外还有很多其他的问题？例如：

1）我们怎么知道哪些是前台任务，哪些是后台任务，fork时告诉我们吗?

2）gcc就⼀点不需要交互吗?Ctrl+C按键怎么⼯作?

3）word就不会执⾏⼀段批处理吗?Ctrl+F按键?

4）SJF中的短作业优先如何体现?如何判断作业的长度?

3.⼀个schdule()实例

在不同的领域，调度算法各不相同。我们讨论的是在⼀个普通的PC机上的调度。

看⼀下Linux0.11的schedule()函数，进程调度的核⼼就是找到next，并且switch_to(next);

//在kernel/sched.c中

voidSchedule(void)

{

while(1)

{

c=-1;next=0;i=NR_TASKS;

p=&task[NR_TASKS];

while(--i)

{

if((*p->state==TASK_RUNNING&&(*p)->counter>c)

c=(*p)->counter,next=i;

}

if(c)

break;//找到了最⼤的counter

for(p=&LAST_TASK;p>&FIRST_TASK;--p)

(*p)->counter=((*p)->counter>>1)+(*p)->priority;

}

switch_to(next);

}

在Linux中，将PCB做成了⼀个数组，NR_TASKS就是数组的范围。

在schedule中，⾸先将p指向PCB的最后⼀个元素，然后遍历整个数组。如果该进程的state为TASK_RUNNING，TASK_RUNNING表⽰

就绪状态，并且该进程的counter>c，就将该进程的counter赋给c，该进程设置为next。

while(--i)

{

if((*p->state==TASK_RUNNING&&(*p)->counter>c)

c=(*p)->counter,next=i;

}

也就是说经过这个循环之后，c应该是就绪进程队列中中counter最⼤的那个进程，

if(c)

break;

如果c⼤于零，就跳出while(1)，执⾏switch_to(next)，即执⾏counter最⼤的那个进程。如果c⼩于等于0，意思就是所有就绪进程的

counter都是⼩于等于零，那么就调⽤进程0执⾏。在Linux0.11中进程0会调⽤pau()把⾃⼰置为可中断的睡眠状态并再次调⽤

schedule()。

for(p=&LAST_TASK;p>&FIRST_TASK;--p)

(*p)->counter=((*p)->counter>>1)+(*p)->priority;

这个for循环是设置所有进程的counter，这个for循环执⾏的条件是，当就绪队列中所有的进程的counter⼩于等于0才执⾏。

(*p)->counter=((*p)->counter>>1)+(*p)->priority;

这句话的意思是将所有进程（包括不处于就绪状态的进程）的counter除以2+该进程的priority。从上⾯的分析可以看出，调度就是根据

counter来选择的，那这个counter到底是什么呢？

r的作⽤

4.1时间⽚

counter在操作系统⾥⾯本就是时间⽚。

voiddo_timer(...)//在kernel/sched.c中

{

if((--current->counter>0)

return;

current->counter=0;

schedule();

}

这是⼀个时钟中断，就是隔多长时间这个函数执⾏⼀次。学过单⽚机的同学就可以理解成⼀个定时器。

if((--current->counter>0))

return;

如果当前进程的counter⼤于0，就减⼀并且结束函数。如果⼩于等于0，就将当前进程的counter置为0，执⾏schedule函数。

4.2优先级

while(--i)

{

if((*p->state==TASK_RUNNING&&(*p)->counter>c)

c=(*p)->counter,next=i;

}

这个循环就是从就绪队列⾥⾯选择counter最⼤的进程执⾏，毫⽆疑问counter有优先级的含义。

for(p=&LAST_TASK;p>&FIRST_TASK;--p)

(*p)->counter=((*p)->counter>>1)+(*p)->priority;

这个for是设置所有进程的counter，如果当前进程的counter为0，那么⼀次循环之后，当前进程的counter就为priority；但是如果当前进

程不为0呢？换⾔之就是该进程不处于就绪队列呢，那么经过⼀次循环之后该进程的counter肯定⼤于处于就绪队列的进程（当priority相同

时）；也就是说阻塞的进程再就绪以后优先级⾼于⾮阻塞进程；同时进程阻塞的时间越长，该进程的counter越⼤，为什么？

第⼀次执⾏这个for循环时，如果某进程为阻塞状态，那么其counter为priority

第⼆次执⾏这个for循环时，如果该进程为阻塞状态，那么其counter为priority+priority/2

如果该进程⼀直阻塞，那么其counter为p+p/2+p/4+p/8，这样counter⼀直增加，当该进程⼀旦处于就绪状态，它的counter就会变得

很⼤。进程为什么会阻塞，很⼤可能就是进程IO操作，IO操作不正是前台进程的特征吗？也就是说会优先执⾏前台进程。

4.3counter作⽤整理

1）counter保证了响应时间有界。

前⾯说过⼀个进程如果很长时间没有执⾏，它的counter=p+p/2+p/4+p/8+……这个函数收敛，并且⼀定⼩于2p，也就是说每个进程

的时间⽚最长就是2p，如果有n个进程，那么响应时间最⼤也就是2np。

2）后台进程⼀直按照counter轮转，近似于SJF调度

3）每个进程只⽤维护⼀个变量counter，简单、⾼效。