社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
本文从几个角度入手,描述和学习调度器原理
linux中称为进程控制块(PCB),即包含任务相关的数据结构,包含任务执行过程中的所有信息。
ps: 上图中从运行态进入就绪态,还有可能是 运行态的任务主动放弃cpu
按照是否有优先级,调度算法主要可分为
1、基于优先级的可抢占式调度
如果出现具有更高优先级的任务处于就绪状态,将当前任务停止运行,把cpu的控制权交给高优先级任务。
2、时间片轮转调度
各个任务按照先入先出原则排成一个队列,新任务入队尾,调度时选队首。
3、轮询,直到 ①任务执行完毕 ②任务主动放弃cpu ③ 任务IO操作阻塞
对于协程调度,我们主要关心两个问题:
struct Task
{
char name[256]; // 任务名
char state[256]; // 任务状态
Task *next;
Task *prev;
Task *allnext;
Task *allprev;
Context context; //任务上下文
uvlong alarmtime;
uint id; //任务ID
uchar *stk; //任务栈
uint stksize; //任务栈大小
int exiting;
int alltaskslot;
int system;
int ready;
void (*startfn)(void*); //函数指针,指向本任务的业务函数
void *startarg; //函数参数
void *udata;
};
可以看到,协程的结构体包含的数据,基本与TCB一致。
static void
taskscheduler(void)
{
int i;
Task *t;
taskdebug("scheduler enter");
for(;;){
if(taskcount == 0)
exit(taskexitval);
t = taskrunqueue.head; //调度器从就绪队列里面取出队头
if(t == nil){
fprint(2, "no runnable tasks! %d tasks stalledn", taskcount);
exit(1);
}
deltask(&taskrunqueue, t);//删除取出来的队头
t->ready = 0; //将该任务设置成非就绪
taskrunning = t;
tasknswitch++;
taskdebug("run %d (%s)", t->id, t->name);
contextswitch(&taskschedcontext, &t->context);
//将调度器当前上下文保存在全局taskschedcontext,
然后切换到就绪队列队头任务t的上下文
//print("back in schedulern");
taskrunning = nil;
if(t->exiting){
if(!t->system)
taskcount--;
i = t->alltaskslot;
alltask[i] = alltask[--nalltask];
alltask[i]->alltaskslot = i;
free(t);
}
}
}
以上是一个调度器的实现,画了个图表示调度器一次for循环的运行流程(其中③④⑤⑥⑦具体细节代码可以看调度点那一节)如果要从一个协程切换到另一个协程,执行顺序按上图中的③④⑤⑥⑦①②
上述过程基本表示了协程调度的流程,即每次做协程切换时,都会先切换到调度器,再从调度器切换到下一个协程。
而整个过程对于协程库使用者来说,是透明的,在使用者看来,就是从一个协程切换到了另外一个协程。
在每一个调度点上,任务都会调用contextswitch()函数切换上下文,切换到调度器上,然后调度器再切换到就绪队列下一个任务。
任务执行完以后,切换回调度器,销毁该任务。
void
taskswitch(void)
{
needstack(0);
//保存当前任务上下文,切换至调度器上下文。
contextswitch(&taskrunning->context, &taskschedcontext);
}
void
taskready(Task *t)
{
t->ready = 1;
addtask(&taskrunqueue, t); //将该任务入队尾
}
int
taskyield(void)
{
int n;
n = tasknswitch;
taskready(taskrunning); //将该任务入队尾
taskstate("yield"); //改状态
taskswitch(); //切换上下文
return tasknswitch - n - 1; //判断此时就绪队列中是否只有fdtask一个任务
}
这个协程库没有时间片轮转机制,所以大部分任务可能都会主动调用taskyield主动让出执行权。
整个过程,其实就是前一节图中的③④⑤⑥⑦,所以,taskyield会重新激活taskscheduler()函数,从调度器的contextswitch()的下一行继续执行。
void
fdwait(int fd, int rw)
{
int bits;
if(!startedfdtask){
//确保系统中只有一个fdtask,且是在第一次出现IO操作时创建的。
startedfdtask = 1;
taskcreate(fdtask, 0, 32768);
}
if(npollfd >= MAXFD){
fprint(2, "too many poll file descriptorsn");
abort();
}
taskstate("fdwait for %s", rw=='r' ? "read" : rw=='w' ? "write" : "error");
bits = 0;
switch(rw){
case 'r':
bits |= POLLIN;
break;
case 'w':
bits |= POLLOUT;
break;
}
polltask[npollfd] = taskrunning;
pollfd[npollfd].fd = fd; //将本fd加入到pollfd数组
pollfd[npollfd].events = bits;
pollfd[npollfd].revents = 0;
npollfd++;
taskswitch(); //上下文切换到调度器
}
如果运行态的任务,遇到IO阻塞,会调用void fdwait(int fd, int rw)
函数,这个函数主要调用taskswitch(),即做上下文切换,但是不将此任务加入就绪队列,而是直接加入
pollfd数组,到后面fdtask任务再判断是否将该任务加入就绪队列。(具体见fdwait函数的注释)
从等待态到就绪态的过程:
void
fdtask(void *v)
fdtask任务,用于监听所有处于阻塞状态的pollfd
for(;;){
/* let everyone else run */
while(taskyield() > 0)
;
/* we're the only one runnable - poll for i/o */
调用taskyield,即每次一进fdtask任务,就会做进程切换,将fdtask切换到末尾,然后调度就绪队列头部,如果发现就绪队列中只有fdtask一个任务,跳出while循环,执行poll:
if(poll(pollfd, npollfd, ms) < 0){
if(errno == EINTR)
continue;
fprint(2, "poll: %sn", strerror(errno));
taskexitall(0);
}
pollfd中有读写事件的fd,将fd[i]对应的polltask[i]加入就绪队列,fd[i]与polltask[i]一一对应。
/* wake up the guys who deserve it */
for(i=0; i<npollfd; i++){
while(i < npollfd && pollfd[i].revents){
taskready(polltask[i]); //加入就绪队列
--npollfd;
pollfd[i] = pollfd[npollfd];
polltask[i] = polltask[npollfd];
}
}
taskready(polltask[i]); 加入就绪队列。
等待态并不是一个任务队列,而是一个存多个fd的pollfd数组,然后当有IO操作,会创建一个fdtask任务,加入队尾,用IO复用操作poll或者epoll去轮询这个数组,
当所有的任务都执行完以后,判断出此时就绪队列中只有fdtask一个任务,才将可以进行读写的fd加入到就绪队列队尾,继续以上操作。
再举个例子:
与Reactor模式对比,虽然都是用了IO复用poll/epoll,但是Reactor用的是基于回调的异步方式,而
协程通过就绪队列这一层中间层,不需要注册回调函数,用跟其他普通任务相同的方式处理IO事件。
对使用者来讲,协程这种同步编程方式更加好理解,而且不需要维护各种回调。
通过分析libtask的部分源码,我们已经得知两个问题:1.怎么调度 2.什么时候调度
下面看看golang的协程调度
比如:调度器P1对应的就绪队列中没有就绪任务,M选择P1白白浪费资源,于是会选择就绪任务多的P2、P3等
再比如: 调度器P1对应的就绪队列中的就绪任务已经执行完成了,M会重新选择任务多的P2、P3等
我们分析的libtask,其实就是P与G的关系,M总是1,即并没有考虑多核的情况。
1、P的数量:
2、M的数量:
M与P的数量没有绝对关系,一个M阻塞,P就会去创建或者切换另一个M,所以,即使P的默认数量是1,也有可能会创建很多个M出来。
3、P何时创建:在确定了P的最大数量n后,运行时系统会根据这个数量创建n个P。
4、M何时创建:没有足够的M来关联P并运行其中的可运行的G。比如所有的M此时都阻塞住了,而P中还有很多就绪任务,就会去寻找空闲的M,而没有空闲的,就会去创建新的M。
当M因系统调用而阻塞时(M上运行的G进入了系统调用的时候),M与P会分开,如果此时P的就绪队列中还有任务,
P就会去关联一个空闲的M,或者创建一个M进行关联。(也就是说go不是像libtask一样处理IO阻塞的?不确定。)
后来的G进入哪个P,具体的算法还没有看到
如果一个P的就绪队列所有任务都执行完了,那么P会尝试从其他P的就绪队列中取出一部分到自己的就绪队列中,以保证每个P的就绪队列都有任务可以执行。
上面只是简单的讲了M、P、G的关系,如果还要继续深入,感觉只能看代码细节了
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!