精华内容
下载资源
问答
  • 抢占式的响应比高者进程调度优先算法java
  • 进程的主动调度与抢占式调度

    千次阅读 2020-03-01 21:21:09
    主要描述了主动调度与抢占式调度以及抢占式调度与主动调度的关系,同时讲述了抢占式调度发生的时机以及其真正被调度的时机,同时也简要讲述了进程上下文切换的本质。

    一、主动调度

    调用schedule函数进行主动调度,其具体流程比较简单,需要掌握调度类,调度队列,调度实体以及他们和CPU之间的关系,这些知识在上一篇博文《函数堆栈与进程调度基础》中进行了一定简单的介绍。
    简言之,当调用schedule函数进行主动调度时,首先会调用通过调度类找到下一个要被调度的进程,然后将当前进程切换状态放入对应调度类的调度队列里面,等待再次被唤醒。而对于被调度的这个队列我们就要对其进行上下文切换

    二、进程上下文切换

    上下文切换主要干下面两件事,是通过context_switch函数实现的:

    • 切换进程空间,即虚拟内存
    • 切换寄存器和CPU上下文,即保存寄存器等当前进程相关变量
    static __always_inline struct rq *
    context_switch(struct rq *rq, struct task_struct *prev,
    	       struct task_struct *next, struct rq_flags *rf)
    {//linux-4.13.16\kernel\sched\core.c
    	struct mm_struct *mm, *oldmm;
        ...
    	mm = next->mm;
    	oldmm = prev->active_mm;
        ...
    		switch_mm_irqs_off(oldmm, mm, next);//熟悉吧,对于进程空间的切换
        ...
    	/* Here we just switch the register state and the stack. */
    	switch_to(prev, next, prev);//寄存器和栈空间的切换,即上面说的切换寄存器和保护上下文
    	barrier();//编译器优化指令,保证执行顺序的不变性
    	return finish_task_switch(prev);
    }
    

    关于进程切换的小总结:

    • 在上面switch_mm_irqs_off进行内存切换时,通过将要切换进程的顶级页表项放在CPU的Cr3寄存器中,实现了用户空间的切换。
    • 内核栈的切换其实还是需要上一讲的知识作为铺垫,因为task_struct里面有一个成员变量就指向进程的内核栈,需要注意的是内核栈是位于内核态的直接映射区的。
    • 至于内核栈的栈顶指针,它会在进程切换时将其值加载到cpu对应的TSS(任务状态段)中,CPU有一个寄存器TR(task register)就是指向这个TSS段的,使用时直接通过这个指针就可以得到了。
    • 而用户态的栈顶指针等一些寄存器变量他会保存在我们上一讲刚刚讲过的内核栈中的pt_regs结构体中,这样当执行用户态时就会恢复进程的上下文情况。。。
      到目前为止,若我们了解计算机组成原理的话就会发现似乎还没有提及指令指针寄存器(IP)的变化,那它是怎样变化的哩?
    • 巧妙的IP寄存器的值变迁,太妙了,这方面极客时间刘超老师的《Linux操作系统调度篇》讲的是真的清楚,他总结的进程调度第一原理——“进程切换时都会调用__schedule的机理”,是顺利理解IP寄存器变迁的良药,超级推荐。
      注意:可以使用ps aux命令查看进程运行时间等基本信息。

    三、抢占式调度

    主动调度指是某进程主动调用了schedule函数,那么下面是一些发生抢占式调度的时机:

    • 每当系统触发一个时钟中断时就会调用中断处理函数,里面会尝试进行抢占式调度
    • 当一个由于IO而被挂起的进程由于受到IO来了的信号而被唤醒时就会比较与当前正在运行进程的优先级,若被唤醒的IO进程优先级更高就会触发抢占式中断。
      注意:以上两种所谓的抢占式调度只是将当前进程标记为了应该被抢占,但还未真正的被抢占,因为最终只有调用了__shcedule才可以被抢占
      那么什么时候才会调用__shcedule进行真正的抢占式调度哩,具体会分有用户态抢占和内核态抢占时机?
    1.用户态抢占时机
    • 进程从系统调用返回用户态时侯是触发调用schedule的一个时机
    • 对用户态进程而言,从中断返回的那个时刻,也是一个被抢占的时机
    2.内核态抢占时机
    • 内核定义有一个宏preempt_enable,每当在内核进程进行某些操作之前会先调用该宏判断是否有需要发生抢占的进程(上面对应的发生情况(tick,io线程)会用一个变量做标记),若有的话就会调用shcedule进行调度。
    • 同样和用户态一样,当发生中断返回时也会尝试进行schedule,完成抢占式调度的最后一步。

    四、总结

    一张非常好看的图片,源:趣谈Linux操作系统:抢占式调度是如何发生的?
    调度总结

    展开全文
  • 优质范文 淮海工学院计算机工程学院 实验报告书 课程名 操作系统原理A 题 目 进程调度 班 级 计算机142 学 号 2014122778 姓 名 陈韦迪 评语 评语 成绩 指导教师 批阅时间 年 月 日 . 优质范文 目的与要求 进程是...
  • 进程调度算法包括先来先服务调度算法、最短作业时间优先(抢占式和非抢占式)、最高响应比调度算法4种。(每个人必须做FCFS,然后在后面的三种中任选一种,即每个人必须做2种调度算法的模拟。) [2]. 衡量算法性能的...
  • 前言: 疫情期间里老老实实在家蹲着,这期间主要研究下go 1.14新增的部分。...golang在之前的版本中已经实现了抢占调度,不管是陷入到大量计算还是系统调用,大多可被sysmon扫描到并进行抢占。但有些场景是无法

    转载地址:http://xiaorui.cc/archives/6535

    golang signal retake

    前言:

    疫情期间里老老实实在家蹲着,这期间主要研究下go 1.14新增的部分。go 1.14中比较大的更新有信号的抢占调度、defer内联优化,定时器优化等。前几天刚写完了golang 1.14 timer定时器的优化,有兴趣的朋友可以看看,http://xiaorui.cc/?p=6483

    golang在之前的版本中已经实现了抢占调度,不管是陷入到大量计算还是系统调用,大多可被sysmon扫描到并进行抢占。但有些场景是无法抢占成功的。比如轮询计算 for { i++ } 等,这类操作无法进行newstack、morestack、syscall,所以无法检测stackguard0 = stackpreempt。

    go team已经意识到抢占是个问题,所以在1.14中加入了基于信号的协程调度抢占。原理是这样的,首先注册绑定 SIGURG 信号及处理方法runtime.doSigPreempt,sysmon会间隔性检测超时的p,然后发送信号,m收到信号后休眠执行的goroutine并且进行重新调度。

    该文章后续仍在不断的更新修改中,请移步到原文地址 http://xiaorui.cc/?p=6535

    对比测试:

    // xiaorui.cc
    
    package main
    
    import (
        "runtime"
    )
    
    func main() {
        runtime.GOMAXPROCS(1)
    
        go func() {
            panic("already call")
        }()
    
        for {
        }
    }

    Go

    COPY

    上面的测试思路是先针对GOMAXPROCS的p配置为1,这样就可以规避并发而影响抢占的测试,然后go关键字会把当前传递的函数封装协程结构,扔到runq队列里等待runtime调度,由于是异步执行,所以就执行到for死循环无法退出。

    go1.14是可以执行到panic,而1.13版本一直挂在死循环上。那么在go1.13是如何解决这个问题? 要么并发加大,要么执行一个syscall,要么执行复杂的函数产生morestack扩栈。对比go1.13版,通过strace可以看到go1.14多了一步发送信号中断。这看似就是文章开头讲到的基于信号的抢占式调度了。

    源码分析:

    以前写过文章来分析go sysmon() 的工作,在新版go 1.14里其他功能跟以前一样,只是加入了信号抢占。

    怎么注册的sigurg信号?

    // xiaorui.cc
    
    const sigPreempt = _SIGURG
    
    func initsig(preinit bool) {
        for i := uint32(0); i < _NSIG; i++ {
            fwdSig[i] = getsig(i)
            ,,,
            setsig(i, funcPC(sighandler)) // 注册信号对应的回调方法
        }
    }
    
    func sighandler(sig uint32, info *siginfo, ctxt unsafe.Pointer, gp *g) {
        ,,,
        if sig == sigPreempt {  // 如果是抢占信号
            // Might be a preemption signal.
            doSigPreempt(gp, c)
        }
        ,,,
    }
    
    // 执行抢占
    func doSigPreempt(gp *g, ctxt *sigctxt) {
        if wantAsyncPreempt(gp) && isAsyncSafePoint(gp, ctxt.sigpc(), ctxt.sigsp(), ctxt.siglr()) {
            // Inject a call to asyncPreempt.
            ctxt.pushCall(funcPC(asyncPreempt))  // 执行抢占的关键方法
        }
    
        // Acknowledge the preemption.
        atomic.Xadd(&gp.m.preemptGen, 1)
    }

    Go

    COPY

    go在启动时把所有的信号都注册了一遍,包括可靠的信号。(截图为部分)

    由谁去发起检测抢占?

    go1.14之前的版本是是由sysmon检测抢占,到了go1.14当然也是由sysmon操作。runtime在启动时会创建一个线程来执行sysmon,为什么要独立执行? sysmon是golang的runtime系统检测器,sysmon可进行forcegc、netpoll、retake等操作。拿抢占功能来说,如sysmon放到pmg调度模型里,每个p上面的goroutine恰好阻塞了,那么还怎么执行抢占?

    所以sysmon才要独立绑定运行,就上面的脚本在测试运行的过程中,虽然看似阻塞状态,但进行strace可看到sysmon在不断休眠唤醒操作。sysmon启动后会间隔性的进行监控,最长间隔10ms,最短间隔20us。如果某协程独占P超过10ms,那么就会被抢占!

    sysmon依赖schedwhen和schedtick来记录上次的监控信息,schedwhen记录上次的检测时间,schedtick来区分调度时效。比如sysmon在两次监控检测期间,已经发生了多次runtime.schedule协程调度切换,每次调度时都会更新schedtick值。所以retake发现sysmontick.schedtick值不同时重新记录schedtick。

    runtime/proc.go

    // xiaorui.cc
    
    func main() {
        g := getg()
        ,,,
        if GOARCH != "wasm" {
            systemstack(func() {
                newm(sysmon, nil)
            })
        }
        ,,,
    }
    
    func schedule() {
        ,,,
        execute(gp, inheritTime)
    }
    
    func execute(gp *g, inheritTime bool) {
        if !inheritTime {
            _g_.m.p.ptr().schedtick++
        }
        ,,,
    }
    
    func sysmon(){
        ,,,
             // retake P's blocked in syscalls
             // and preempt long running G's
             if retake(now) != 0 {
                 idle = 0
             } else {
                 idle++
             }
        ,,,
    }
    
    // 记录每次检查的信息
    type sysmontick struct {
        schedtick   uint32
        schedwhen   int64
        syscalltick uint32
        syscallwhen int64
    }
    
    const forcePreemptNS = 10 * 1000 * 1000 // 抢占的时间阈值 10ms
    
    func retake(now int64) uint32 {
        n := 0
        lock(&allpLock)
        for i := 0; i < len(allp); i++ {
            _p_ := allp[i]
            if _p_ == nil {
                continue
            }
            pd := &_p_.sysmontick
            s := _p_.status
            if s == _Prunning || s == _Psyscall {
                // Preempt G if it's running for too long.
                t := int64(_p_.schedtick)
                if int64(pd.schedtick) != t {
                    pd.schedtick = uint32(t)
                    pd.schedwhen = now // 记录当前检测时间
                // 上次时间加10ms小于当前时间,那么说明超过,需进行抢占。
                } else if pd.schedwhen+forcePreemptNS <= now {
                    preemptone(_p_)
                }
            }
    
            // 下面省略掉慢系统调用的抢占描述。
            if s == _Psyscall {
                // 原子更为p状态为空闲状态
                if atomic.Cas(&_p_.status, s, _Pidle) {
                    ,,,
                    handoffp(_p_)  // 强制卸载P, 然后startm来关联
                }
            ,,,
    } 
    
    func preemptone(_p_ *p) bool {
        mp := _p_.m.ptr()
        ,,,
    
        gp.preempt = true
    
        ,,,
        gp.stackguard0 = stackPreempt
    
        // Request an async preemption of this P.
        if preemptMSupported && debug.asyncpreemptoff == 0 {
            _p_.preempt = true
            preemptM(mp)
        }
    
        return true
    }

    Go

    COPY

    发送SIGURG信号?

    signal_unix.go

    // xiaorui.cc
    
    // 给m发送sigurg信号
    func preemptM(mp *m) {
        if !pushCallSupported {
            // This architecture doesn't support ctxt.pushCall
            // yet, so doSigPreempt won't work.
            return
        }
        if GOOS == "darwin" && (GOARCH == "arm" || GOARCH == "arm64") && !iscgo {
            return
        }
        signalM(mp, sigPreempt)
    }

    Go

    COPY

    收到sigurg信号后如何处理 ?

    preemptPark方法会解绑mg的关系,封存当前协程,继而重新调度runtime.schedule()获取可执行的协程,至于被抢占的协程后面会去重启。

    goschedImpl操作就简单的多,把当前协程的状态从_Grunning正在执行改成 _Grunnable可执行,使用globrunqput方法把抢占的协程放到全局队列里,根据pmg的协程调度设计,globalrunq要后于本地runq被调度。

    runtime/preempt.go

    // xiaorui.cc
    
    //go:generate go run mkpreempt.go
    
    // asyncPreempt saves all user registers and calls asyncPreempt2.
    //
    // When stack scanning encounters an asyncPreempt frame, it scans that
    // frame and its parent frame conservatively.
    func asyncPreempt()
    
    //go:nosplit
    func asyncPreempt2() {
        gp := getg()
        gp.asyncSafePoint = true
        if gp.preemptStop {
            mcall(preemptPark)
        } else {
            mcall(gopreempt_m)
        }
        gp.asyncSafePoint = false
    }

    Go

    COPY

    runtime/proc.go

    // xiaorui.cc
    
    // preemptPark parks gp and puts it in _Gpreempted.
    //
    //go:systemstack
    func preemptPark(gp *g) {
        ,,,
        status := readgstatus(gp)
        if status&^_Gscan != _Grunning {
            dumpgstatus(gp)
            throw("bad g status")
        }
        ,,,
        schedule()
    }
    
    func goschedImpl(gp *g) {
        status := readgstatus(gp)
        ,,,
        casgstatus(gp, _Grunning, _Grunnable)
        dropg()
        lock(&sched.lock)
        globrunqput(gp)
        unlock(&sched.lock)
    
        schedule()
    }

    Go

    COPY

    源码解析粗略的分析完了,还有一些细节不好读懂,但信号抢占实现的大方向摸的89不离10了。

    抢占是否影响性能 ?

    抢占分为_Prunning和Psyscall,Psyscall抢占通常是由于阻塞性系统调用引起的,比如磁盘io、cgo。Prunning抢占通常是由于一些类似死循环的计算逻辑引起的。

    过度的发送信号来中断m进行抢占多少会影响性能的,主要是软中断和上下文切换。在平常的业务逻辑下,很难发生协程阻塞调度的问题。😅

    慢系统调度的错误处理?

    EINTR错误通常是由于被信号中断引起的错误,比如在执行epollwait、accept、read&write 等操作时,收到信号,那么该系统调用会被打断中断,然后去执行信号注册的回调方法,完事后会返回eintr错误。

    下面是golang的处理方法,由于golang的netpoll设计使多数的io相关的syscall操作非阻塞化,所以就只有epollwait有该问题。

    // xiaorui.cc
    
    func netpoll(delay int64) gList {
        ,,,
        var events [128]epollevent
    retry:
        n := epollwait(epfd, &events[0], int32(len(events)), waitms)
        if n < 0 {
            if n != -_EINTR {
                println("runtime: epollwait on fd", epfd, "failed with", -n)
                throw("runtime: netpoll failed")
            }
            goto retry
        }
        ,,,
    }
    
    func netpollBreak() {
        for {
            var b byte
            n := write(netpollBreakWr, unsafe.Pointer(&b), 1)
            if n == 1 {
                break
            }
            if n == -_EINTR {
                continue
            }
            ,,,
        }
    }

    Go

    COPY

    通常需要手动来解决EINTR的错误问题,虽然可通过SA_RESTART来重启被中断的系统调用,但不管是syscall兼容和业务上有可能出现偏差。

    // xiaorui.cc
    
    // epoll_wait
    if(  -1 == epoll_wait() )
    {
        if(errno!=EINTR)
        {
              return -1;
        }
    }
    
    // read 
    again:
              if ((n = read(fd, buf, BUFFSIZE)) < 0) {
                 if (errno == EINTR)
                      goto again;
              }

    Go

    COPY

    配置SA_RESTART后,线程被中断后还可继续执行被中断的系统调用。

    // xiaorui.cc
    
    --- SIGINT {si_signo=SIGINT, si_code=SI_KERNEL, si_value={int=0, ptr=0x100000000}} ---
    rt_sigreturn()                          = -1 EINTR (Interrupted system call)
    futex(0x1b97a30, FUTEX_WAIT_PRIVATE, 0, NULL) = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
    --- SIGINT {si_signo=SIGINT, si_code=SI_KERNEL, si_value={int=0, ptr=0x100000000}} ---
    rt_sigreturn()                          = -1 EINTR (Interrupted system call)
    ...

    Bash

    COPY

    信号的原理?

    我们对一个进程发送信号后,内核把信号挂载到目标进程的信号 pending 队列上去,然后进行触发软中断设置目标进程为running状态。当进程被唤醒或者调度后获取CPU后,才会从内核态转到用户态时检测是否有signal等待处理,等进程处理完后会把相应的信号从链表中去掉。

    通过kill -l拿到当前系统支持的信号列表,1-31为不可靠信号,也是非实时信号,信号有可能会丢失,比如发送多次相同的信号,进程只能收到一次。

    // xiaorui.cc
    
    // Print a list of signal names.  These are found in /usr/include/linux/signal.h
    
    kill -l
    
    1) SIGHUP     2) SIGINT     3) SIGQUIT     4) SIGILL     5) SIGTRAP
    6) SIGABRT     7) SIGBUS     8) SIGFPE     9) SIGKILL    10) SIGUSR1
    11) SIGSEGV    12) SIGUSR2    13) SIGPIPE    14) SIGALRM    15) SIGTERM
    16) SIGSTKFLT    17) SIGCHLD    18) SIGCONT    19) SIGSTOP    20) SIGTSTP
    21) SIGTTIN    22) SIGTTOU    23) SIGURG    24) SIGXCPU    25) SIGXFSZ
    26) SIGVTALRM    27) SIGPROF    28) SIGWINCH    29) SIGIO    30) SIGPWR
    31) SIGSYS  

    Bash

    COPY

    在Linux中的posix线程模型中,线程拥有独立的进程号,可以通过getpid()得到线程的进程号,而线程号保存在pthread_t的值中。而主线程的进程号就是整个进程的进程号,因此向主进程发送信号只会将信号发送到主线程中去。如果主线程设置了信号屏蔽,则信号会投递到一个可以处理的线程中去。

    注册的信号处理函数都是线程共享的,一个信号只对应一个处理函数,且最后一次为准。子线程也可更改信号处理函数,且随时都可改。

    多线程下发送及接收信号的问题?

    默认情况下只有主线程才可处理signal,就算指定子线程发送signal,也是主线程接收处理信号。

    那么Golang如何做到给指定子线程发signal且处理的?如何指定给某个线程发送signal? 在glibc下可以使用pthread_kill来给线程发signal,它底层调用的是SYS_tgkill系统调用。

    golang signal

    // xiaorui.cc
    
    #include "pthread_impl.h"
    
    int pthread_kill(pthread_t t, int sig)
    {
    	int r;
    	__lock(t->killlock);
    	r = t->dead ? ESRCH : -__syscall(SYS_tgkill, t->pid, t->tid, sig);
    	__unlock(t->killlock);
    	return r;
    }

    C++

    COPY

    那么在go runtime/sys_linux_amd64.s里找到了SYS_tgkill的汇编实现。os_linux.go中signalM调用的就是tgkill的实现。

    // xiaorui.cc
    #define SYS_tgkill      234
    
    TEXT ·tgkill(SB),NOSPLIT,0
        MOVQ    tgid+0(FP), DI
        MOVQ    tid+8(FP), SI
        MOVQ    sig+16(FP), DX
        MOVLSYS_tgkill, AX
        SYSCALL
        RET

    C++

    COPY

    // xiaorui.cc
    
    func tgkill(tgid, tid, sig int)
    
    // signalM sends a signal to mp.
    func signalM(mp *m, sig int) {
        tgkill(getpid(), int(mp.procid), sig)
    }

    Go

    COPY

    总结:

    随着go版本不断更新,runtime的功能越来越完善。现在看来基于信号的抢占式调度显得很精妙。下一篇文章继续写go1.4 defer的优化,简单说在多场景下编译器消除了deferproc压入和deferreturn插入调用,而是直接调用延迟方法。

    展开全文
  • 绝大多数嵌入式操作系统采用抢占式的调度方式。本文主要讲述采用抢占式方式进行任务调度的嵌入式操作系统的调度策略和原理
  • HY:内核禁止抢占,并不会妨碍进程调度,所以自旋锁(禁止抢占)保护的代码不能睡眠,否则会进行内核进程调度,可能会造成死锁。 抢占:在系统调用到内核态时,也可以发生进程调度。 -------------- 自旋锁是SMP...

    HY:内核禁止抢占,并不会妨碍进程调度,所以自旋锁(禁止抢占)保护的代码不能睡眠,否则会进行内核进程调度,可能会造成死锁。

    内核抢占:在系统调用到内核态时,也可以发生进程调度。

    https://blog.csdn.net/gatieme/article/details/51872618

    schedule函数调用的时机:

    /*
     * __schedule() is the main scheduler function.
     *
     * The main means of driving the scheduler and thus entering this function are:
     *
     *   1. Explicit blocking: mutex, semaphore, waitqueue, etc.
     *
     *   2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
     *      paths. For example, see arch/x86/entry_64.S.
     *
     *      To drive preemption between tasks, the scheduler sets the flag in timer
     *      interrupt handler scheduler_tick().在可抢占时,在时钟中断中设置TIF_NEED_RESCHED 。
     *
     *   3. Wakeups don't really cause entry into schedule(). They add a
     *      task to the run-queue and that's it.Wakeups 并不会引起调度,只是将就绪任务装载到run-queue。
     *
     *      Now, if the new task added to the run-queue preempts the current
     *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
     *      called on the nearest possible occasion:
     *
     *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
     *
     *         - in syscall or exception context, at the next outmost
     *           preempt_enable(). (this might be as soon as the wake_up()'s
     *           spin_unlock()!)
     *
     *         - in IRQ context, return from interrupt-handler to
     *           preemptible context
     *
     *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
     *         then at the next:
     *
     *          - cond_resched() call
     *          - explicit schedule() call
     *          - return from syscall or exception to user-space
     *          - return from interrupt-handler to user-space
     */

    /*
     * __schedule() is the main scheduler function.
     *
     * The main means of driving the scheduler and thus entering this function are:
     *
     *   1. Explicit blocking: mutex, semaphore, waitqueue, etc.
     *
     *   2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
     *      paths. For example, see arch/x86/entry_64.S.
     *
     *      To drive preemption between tasks, the scheduler sets the flag in timer
     *      interrupt handler scheduler_tick().
     *
     *   3. Wakeups don't really cause entry into schedule(). They add a
     *      task to the run-queue and that's it.
     *
     *      Now, if the new task added to the run-queue preempts the current
     *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
     *      called on the nearest possible occasion:
     *
     *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
     *
     *         - in syscall or exception context, at the next outmost
     *           preempt_enable(). (this might be as soon as the wake_up()'s
     *           spin_unlock()!)
     *
     *         - in IRQ context, return from interrupt-handler to
     *           preemptible context
     *
     *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
     *         then at the next:
     *
     *          - cond_resched() call
     *          - explicit schedule() call
     *          - return from syscall or exception to user-space
     *          - return from interrupt-handler to user-space
     */

     

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    抢占式内核与半抢占式内核的不同

        Linux2.4只实现了“有条件抢占式”的调度。它的缺点在于:当进程在内核态时,调度的时机有局限。就是只能在xxx的前夕。例如:当外部来一中断,中断程序过程完后,需要一个用户进程B对此进行进一步的处理(响应IP包数据)。此时进程A正在使用系统调用进入了内核态。那么等到A从系统调用返回之际,内核进行调度,B才有可能运行。假设A的系统调用占用了CPU的时间为T。这个T大于用户要求的响应时间。那这个系统就不够实时。

        为了提高linux的实时性。在linux2.6中引入了“Kernel preemption”(内核抢占调度模式)。并很好的解决了这个问题。一句话就是抢占式内核可以在进程处于内核态时,进行抢占。

    当然抢占式内核在以下几种情况下不可抢占:

    1.当内核运行中断处理程序和异常处理程序时,在linux内核中进程不能抢占中断,在中断例程中不允许进行调度。进程调度函数schedule会对此作出判断,如果是在中断中调用,会打印出出错信息。

    2.当进程在内核态运行临界区的代码时,不可抢占。这些临界区被自旋锁spin_lock保护了起来。【但是当进程使用spin_lock时,自己被锁住并自旋时,这时可以调度。】

    3. 内核正在进行bottom half(中断的底半部)处理时,不可抢占。【不太懂】

    4.内核正在执行调度程序Scheduler时,不可抢占。

    5.内核正在对每一个CPU“私有”数据结构操作(per CPU date structures)时,不可抢占。在SMP中,对于Per-cpu数据结构未用spinlocks保护,因为这些数据结构隐含地被保护了。

    抢占式内核什么时候,什么位置调用schedule函数?

        当中断发生,并完成中断处理时,在返回之前被中断的进程时,可以根据需要进行调度。

    抢占式内核为每一个进程的task_struct结构引入了preempt_count变量,称为内核抢占锁。每当进程进入以上五种状态时,preempt_count加1.表示不可抢占。当退出以上五种状态时,preempt_count减1. 每次进行抢占式调度时,先判断preempt_count与0大小,preempt_count<0,表示可抢占。preempt_count>0表示不可抢占。

    一系统抢占式的调度器函数:preempt_schedule;preempt_schedule_irq。它们都是调用schedule来完成调度的。

    实时操作系统与抢占式内核的关系

    实时操作系统要求就是对来自外部的请求,要求有及时的处理。及时到什么程度就是实时操作系统呢?这个没有一个明确的定义,因为用户对响应时间的要求各不相同。

    我们可以说当在同样的硬件条件下,Linux2.4的实时性不高,或是不如linux2.6的实时性高。那么提高系统的实时性的方法有很多,提高CPU速度,增加CPU核。优化操作系统等。那么 linux在提高系统实时性的重要贡献就是引入了“内核抢占调度模式”。那么我们也可以说linux很好的支持了实时性。
    ————————————————
    版权声明:本文为CSDN博主「鹏鹏~」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/qq_36321889/article/details/100137700

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    抢占的时机

     

    1.用户态的抢占时机

    当该进程进行系统调用从内核态返回到用户态的时候,判断如果该进程有TIF_NEED_RESCHED标签,则进行抢占。

     

    2.内核态的抢占时机

    对内核态的执行中,被抢占的时机一般发生在preempt_enable()中。

    preempt_disable()关闭抢占

    在内核态的执行中,有的操作是不能被中断的,所有在进行这些操作之前,总是先调用preempt_disable()关闭抢占,当再次打开的时候,也就是调用preempt_enable()的时候

    就是一次内核态代码被抢占的机会。

     

    在内核态也会遇到中断的情况,当中断返回的时候,返回的仍然是内核态度。这个时候也是一个执行抢占的时机。

    大家可以看看这张图理解

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    自旋锁是SMP架构中的一种low-level的同步机制。
         当线程A想要获取一把自旋锁而该锁又被其它线程锁持有时,线程A会在一个循环中自旋以检测锁是不是已经可用了。对于自选锁需要注意:

    • 由于自旋时不释放CPU,因而持有自旋锁的线程应该尽快释放自旋锁,否则等待该自旋锁的线程会一直在那里自旋,这就会浪费CPU时间。
    • 持有自旋锁的线程在sleep之前应该释放自旋锁以便其它线程可以获得自旋锁。(在内核编程中,如果持有自旋锁的代码sleep了就可能导致整个系统挂起,最近刚解决了一个内核中的问题就是由于持有自旋锁时sleep了,然后导致所有的核全部挂起(是一个8核的CPU))

    使用任何锁需要消耗系统资源(内存资源和CPU时间),这种资源消耗可以分为两类:

    1. 建立锁所需要的资源
    2. 当线程被阻塞时锁所需要的资源

    Pthreads提供的与Spin Lock锁操作相关的API主要有:

    int pthread_spin_destroy(pthread_spinlock_t *); int pthread_spin_init(pthread_spinlock_t *, int); int pthread_spin_lock(pthread_spinlock_t *); int pthread_spin_trylock(pthread_spinlock_t *); int pthread_spin_unlock(pthread_spinlock_t *);

    1)初始化自旋锁

    pthread_spin_init用来申请使用自旋锁所需要的资源并且将它初始化为非锁定状态。pshared的取值及其含义:

    • PTHREAD_PROCESS_SHARED:该自旋锁可以在多个进程中的线程之间共享。
    • PTHREAD_PROCESS_PRIVATE:仅初始化本自旋锁的线程所在的进程内的线程才能够使用该自旋锁。

    2)获得一个自旋锁

    pthread_spin_lock用来获取(锁定)指定的自旋锁. 如果该自旋锁当前没有被其它线程所持有,则调用该函数的线程获得该自旋锁.否则该函数在获得自旋锁之前不会返回。如果调用该函数的线程在调用该函数时已经持有了该自旋锁,则结果是不确定的。

    3)尝试获取一个自旋锁

    pthread_spin_trylock会尝试获取指定的自旋锁,如果无法获取则理解返回失败。

    4)释放(解锁)一个自旋锁

    pthread_spin_unlock用于释放指定的自旋锁。

    5)销毁一个自旋锁

    pthread_spin_destroy 用来销毁指定的自旋锁并释放所有相关联的资源(所谓的所有指的是由pthread_spin_init自动申请的资源)在调用该函数之后如果没有调用 pthread_spin_init重新初始化自旋锁,则任何尝试使用该锁的调用的结果都是未定义的。如果调用该函数时自旋锁正在被使用或者自旋锁未被初 始化则结果是未定义的。

    互斥量和自旋锁的区别:

    Pthreads提供的Mutex锁操作相关的API主要有:

    pthread_mutex_lock (pthread_mutex_t *mutex); pthread_mutex_trylock (pthread_mutex_t *mutex); pthread_mutex_unlock (pthread_mutex_t *mutex);

    Pthreads提供的与Spin Lock锁操作相关的API主要有:

    pthread_spin_lock (pthread_spinlock_t *lock); pthread_spin_trylock (pthread_spinlock_t *lock); pthread_spin_unlock (pthread_spinlock_t *lock);

           从实现原理上来讲,Mutex属于sleep-waiting类型的 锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。假设线程A想要通过 pthread_mutex_lock操作去得到一个临界区的锁,而此时这个锁正被线程B所持有,那么线程A就会被阻塞(blocking),Core0 会在此时进行上下文切换(Context Switch)将线程A置于等待队列中,此时Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。
           如果大家去查阅Linux glibc中对pthreads API的实现NPTL(Native POSIX Thread Library) 的源码的话(使用”getconf GNU_LIBPTHREAD_VERSION”命令可以得到我们系统中NPTL的版本号),就会发现pthread_mutex_lock()操作如果 没有锁成功的话就会调用system_wait()的系统调用并将当前线程加入该mutex的等待队列里。而spin lock则可以理解为在一个while(1)循环中用内嵌的汇编代码实现的锁操作(印象中看过一篇论文介绍说在linux内核中spin lock操作只需要两条CPU指令,解锁操作只用一条指令就可以完成)。有兴趣的朋友可以参考另一个名为sanos的微内核中pthreds API的实现:mutex.c spinlock.c,尽管与NPTL中的代码实现不尽相同,但是因为它的实现非常简单易懂,对我们理解spin lock和mutex的特性还是很有帮助的。
            对于自旋锁来说,它只需要消耗很少的资源来建立锁;随后当线程被阻塞时,它就会一直重复检查看锁是否可用了,也就是说当自旋锁处于等待状态时它会一直消耗CPU时间。
            对于互斥锁来说,与自旋锁相比它需要消耗大量的系统资源来建立锁;随后当线程被阻塞时,线程的调度状态被修改,并且线程被加入等待线程队列;最后当锁可用 时,在获取锁之前,线程会被从等待队列取出并更改其调度状态;但是在线程被阻塞期间,它不消耗CPU资源。
            因此自旋锁和互斥锁适用于不同的场景。自旋锁适用于那些仅需要阻塞很短时间的场景,而互斥锁适用于那些可能会阻塞很长时间的场景。

    自旋锁与linux内核进程调度关系

      如果临界区可能包含引起睡眠的代码则不能使用自旋锁,否则可能引起死锁。

      那么为什么信号量保护的代码可以睡眠而自旋锁就不能呢?

      先看下自旋锁的实现方法吧,自旋锁的基本形式如下:

      spin_lock(&mr_lock);   //临界区   spin_unlock(&mr_lock);   跟踪一下spin_lock(&mr_lock)的实现   #define spin_lock(lock) _spin_lock(lock)   #define _spin_lock(lock) __LOCK(lock)   #define __LOCK(lock) \   do { preempt_disable(); __acquire(lock); (void)(lock); } while (0)

            注意到“preempt_disable()”,这个调用的功能是“关抢占”(在spin_unlock中会重新开启抢占功能)。从 中可以看出,使用自旋锁保护的区域是工作在非抢占的状态;即使获取不到锁,在“自旋”状态也是禁止抢占的。了解到这,我想咱们应该能够理解为何自旋锁保护 的代码不能睡眠了。试想一下,如果在自旋锁保护的代码中间睡眠,此时发生进程调度,则可能另外一个进程会再次调用spinlock保护的这段代码。而我们 现在知道了即使在获取不到锁的“自旋”状态,也是禁止抢占的,而“自旋”又是动态的,不会再睡眠了,也就是说在这个处理器上不会再有进程调度发生了,那么 死锁自然就发生了。

      咱们可以总结下自旋锁的特点:

      ● 单处理器非抢占内核下:自旋锁会在编译时被忽略;

      ● 单处理器抢占内核下:自旋锁仅仅当作一个设置内核抢占的开关;

      ● 多处理器下:此时才能完全发挥出自旋锁的作用,自旋锁在内核中主要用来防止多处理器中并发访问临界区,防止内核抢占造成的竞争。


    linux抢占发生的时间

      最后在了解下linux抢占发生的时间,抢占分为用户抢占和内核抢占。

      用户抢占在以下情况下产生:

      ● 从系统调用返回用户空间

      ● 从中断处理程序返回用户空间

      内核抢占会发生在:

      ● 当从中断处理程序返回内核空间的时候,且当时内核具有可抢占性;

      ● 当内核代码再一次具有可抢占性的时候。(如:spin_unlock时)

      ● 如果内核中的任务显式的调用schedule()

      ● 如果内核中的任务阻塞。

      基本的进程调度就是发生在时钟中断后,并且发现进程的时间片已经使用完了,则发生进程抢占。通常我们会利用中断处理程序返回内核空间的时候可以进行内 核抢占这个特性来提高一些I/O操作的实时性,如:当I/O事件发生的是时候,对应的中断处理程序被激活,当它发现有进程在等待这个I/O事件的时候,它 会激活等待进程,并且设置当前正在执行进程的need_resched标志,这样在中断处理程序返回的时候,调度程序被激活,原来在等待I/O事件的进程 (很可能)获得执行权,从而保证了对I/O事件的相对快速响应(毫秒级)。可以看出,在I/O事件发生的时候,I/O事件的处理进程会抢占当前进程,系统 的响应速度与调度时间片的长度无关。

    总结:
    (1)Mutex适合对锁操作非常频繁的场景,并且具有更好的适应性。尽管相比spin lock它会花费更多的开销(主要是上下文切换),但是它能适合实际开发中复杂的应用场景,在保证一定性能的前提下提供更大的灵活度。

    (2)spin lock的lock/unlock性能更好(花费更少的cpu指令),但是它只适应用于临界区运行时间很短的场景。而在实际软件开发中,除非程序员对自己 的程序的锁操作行为非常的了解,否则使用spin lock不是一个好主意(通常一个多线程程序中对锁的操作有数以万次,如果失败的锁操作(contended lock requests)过多的话就会浪费很多的时间进行空等待)。

    (3)更保险的方法或许是先(保守的)使用 Mutex,然后如果对性能还有进一步的需求,可以尝试使用spin lock进行调优。毕竟我们的程序不像Linux kernel那样对性能需求那么高(Linux Kernel最常用的锁操作是spin lock和rw lock)。

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    用户抢占(hy:叫进程调度比较好)

    内核即将返回用户空间的时候,如果need resched标志被设置,会导致schedule()被调用,此时就会发生用户抢占。在内核返回用户空间的时候,它知道自己是安全的。所以,内核无论是在从中断处理程序还是在系统调用后返回,都会检查need resched标志。如果它被设置了,那么,内核会选择一个其他(更合适的)进程投入运行。

    简而言之,用户抢占在以下情况时产生:

    1) 从系统调用返回用户空间。

    2) 从中断处理程序返回用户空间。

     

    不可抢占内核的特点

    在不支持内核抢占的内核中,内核代码可以一直执行,到它完成为止。也就是说,调度程序没有办法在一个内核级的任务正在执行的时候重新调度——内核中的各任务是协作方式调度的,不具备抢占性。内核代码一直要执行到完成(返回用户空间)或明显的阻塞为止。

     

    3. 为什么需要内核抢占?

    实现内核的可抢占对Linux具有重要意义。首先,这是将Linux应用于实时系统所必需的。实时系统对响应时间有严格的限定,当一个实时进程被实时设备的硬件中断唤醒后,它应在限定的时间内被调度执行。而Linux不能满足这一要求,因为Linux的内核是不可抢占的,不能确定系统在内核中的停留时间。事实上当内核执行长的系统调用时,实时进程要等到内核中运行的进程退出内核才能被调度,由此产生的响应延迟,在如今的硬件条件下,会长达100ms级。

    禁止内核抢占的情况列出如下:

    1)内核执行中断处理例程时不允许内核抢占,中断返回时再执行内核抢占。

    2)当内核执行软中断或tasklet时,禁止内核抢占,软中断返回时再执行内核抢占。

    3)在临界区禁止内核抢占,临界区保护函数通过抢占计数宏控制抢占,计数大于0,表示禁止内核抢占。

     

    4. 如何支持抢占内核

    为保证Linux内核在以上情况下不会被抢占,抢占式内核使用了一个变量preempt_ count,称为内核抢占锁。这一变量被设置在进程的PCB结构task_struct中。每当内核要进入以上几种状态时,变量preempt_ count就加1,指示内核不允许抢占。每当内核从以上几种状态退出时,变量preempt_ count就减1,同时进行可抢占的判断与调度。

    抢占式Linux内核的修改主要有两点:

    一是对中断的入口代码和返回代码进行修改。在中断的入口内核抢占锁preempt_count1,以禁止内核抢占;在中断的返回处,内核抢占锁preempt_count1,使内核有可能被抢占。

    另一基本修改是重新定义了自旋锁、读、写锁,在锁操作时增加了对preempt count变量的操作。在对这些锁进行加锁操作时preemptcount变量加1,以禁止内核抢占;在释放锁时preemptcount变量减1,并在内核的抢占条件满足且需要重新调度时进行抢占调度。

     

    设置调度的时机(hy这是设置调度的时机,调度的时机见6)

             内核必须知道在什么时候调用schedule()。如果仅靠用户程序代码显式地调用schedule(),它们可能就会永远地执行下去。相反,内核提供了一个need_resched标志来表明是否需要重新执行一次调度。

    1.当前进程用完了它的CPU时间片update_process_times()重新进行计算时钟中断触发schduler_tick()的主要作用就是每一个tick 进程陷入内核后, 他的时间片就递减 当变为0的时候, 会设置TIF_NEED_RESCHED

    2.当一个进程被唤醒,而且它的优先级比当前进程高 try_to_wake_up(),会设置TIF_NEED_RESCHED

     

    6. 调度的时机

    1 中断返回内核空间:检查preempt_count是否为0TIF_NEED_RESCHED是否为1

    2 中断或异常返回到user space:检查TIF_NEED_RESCHED是否为1

    3) 显式或者隐式调preemp_enable()函数:检查preempt_count是否为0TIF_NEED_RESCHED是否为1

    4) 使能软中断:检查preempt_count是否为0TIF_NEED_RESCHED是否为1

    5) 自己主动schedule()

    Question

    FIFO实时进程在运行时候,能加载一个新程序吗,cup一直被该实时进程占据 谁来加载这个新进程。

    如果可以加载 ,而且这个新进程优先级比原来的高,那如何抢占原来的实时进程(时钟中断?

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    Linux进程调度与抢占

    https://www.cnblogs.com/hellokitty2/p/10741600.html

    一、linux内核抢占介绍

    1.抢占发生的必要条件

    a.preempt_count抢占计数必须为0,不为0说明其它地方调用了禁止抢占的函数,比如spin_lock系列函数。
    b.中断必须是使能的状态,因为抢占动作要依赖中断

    preempt_schedule()具体源码实现参考如下:

    asmlinkage __visible void __sched notrace preempt_schedule(void)
    {
        /*
         * If there is a non-zero preempt_count or interrupts are disabled,
         * we do not want to preempt the current task. Just return..
         */
        /*preempt_disable()会增加preempt_count的计数*/
        if (likely(!preemptible()))
            return;
        preempt_schedule_common();
    }
    #define preemptible()    (preempt_count() == 0 && !irqs_disabled())
    ------------------------------------------------------------------------------------
    #ifdef CONFIG_PREEMPT
    /*
     * this is the entry point to schedule() from in-kernel preemption
     * off of preempt_enable. Kernel preemptions off return from interrupt
     * occur there and call schedule directly.
     */
    asmlinkage void __sched notrace preempt_schedule(void)
    {
    	struct thread_info *ti = current_thread_info();
    
    	/*
    	 * If there is a non-zero preempt_count or interrupts are disabled,
    	 * we do not want to preempt the current task. Just return..
    	 */
    	if (likely(ti->preempt_count || irqs_disabled()))
    		return;
    
    #ifdef CONFIG_PREEMPT_LAZY
    	/*
    	 * Check for lazy preemption
    	 */
    	if (ti->preempt_lazy_count && !test_thread_flag(TIF_NEED_RESCHED))
    		return;
    #endif
    
    	do {
    		add_preempt_count_notrace(PREEMPT_ACTIVE);
    		/*
    		 * The add/subtract must not be traced by the function
    		 * tracer. But we still want to account for the
    		 * preempt off latency tracer. Since the _notrace versions
    		 * of add/subtract skip the accounting for latency tracer
    		 * we must force it manually.
    		 */
    		start_critical_timings();
    		__schedule();
    		stop_critical_timings();
    		sub_preempt_count_notrace(PREEMPT_ACTIVE);
    
    		/*
    		 * Check again in case we missed a preemption opportunity
    		 * between schedule and now.
    		 */
    		barrier();
    	} while (need_resched());
    }
    EXPORT_SYMBOL(preempt_schedule);
    

    2.spin_lock系列函数

    a.spin_lock()会调用preempt_disable函数关闭抢占.
    b.spin_lock_irq()会调用spin_lock()函数和local_irq_disable()函数(关闭中断)
    c.spin_lock_irqsave()会调用spin_lock()函数和local_irq_save()函数(关闭中断,同时保存cpu对中断的屏蔽状态,使用spin_lock_irqsave在于你不期望在离开临界区后,改变中断的开启,关闭状态!进入临界区是关闭的,离开后它同样应该是关闭的!)

    spin_lock():

    /*include/linux/spinlock.h*/
    static __always_inline void spin_lock(spinlock_t *lock)
    {
        raw_spin_lock(&lock->rlock);
    }
    #define raw_spin_lock(lock)    _raw_spin_lock(lock)
    
    /*kernel/locking/spinlock.c*/
    void __lockfunc _raw_spin_lock(raw_spinlock_t *lock)
    {
        __raw_spin_lock(lock);
    }
    
    /*include/linux/spinlock_api_smp.h*/
    static inline void __raw_spin_lock(raw_spinlock_t *lock)
    {
        preempt_disable(); /*调用禁止抢占函数*/
        spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
        LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
    }

    spin_unlock():

    /*kernel/locking/spinlock.c*/
    void __lockfunc _raw_spin_unlock(raw_spinlock_t *lock)
    {
        __raw_spin_unlock(lock);
    }
    
    /*include/linux/spinlock_api_smp.h*/
    static inline void __raw_spin_unlock(raw_spinlock_t *lock)
    {
        spin_release(&lock->dep_map, 1, _RET_IP_);
        do_raw_spin_unlock(lock);
        preempt_enable();
    }

    preempt_enable():

    /*include/linux/preempt.h*/
    #define preempt_enable() \
    do { \
        barrier(); \
        if (unlikely(preempt_count_dec_and_test())) \
            /*这里提供了一个抢占点__preempt_schedule(),其它高优先级的进程可直接抢占*/\
            __preempt_schedule(); \
    } while (0)

    由上可知,spin_unlock()系列函数可以直接触发内核抢占,因为它里面提供可抢占点。

     

    3.preempt_disable()和local_irq_disable()的区别

    由抢占发生的必要条件可知两个函数都可以关闭抢占。区别不在于关抢占和关中断函数上,而是在对应的开抢占和开中断的函数上,也就是
    preempt_enable()函数local_irq_enable()函数。preempt_enable()会是能抢占并提供抢占点,而local_irq_enable()仅仅是开中断(是能抢占),
    并没有提供抢占点。

    4.抢占点可能是:时钟tick中断处理返回、中断返回、软中断结束、yield()(进程调用它放弃CPU)等等多种情况。

    5.注意spin_lock系列函数关闭了抢占,但是并没有关闭调度!(spin_lock保护的代码中不能出现睡眠,而且要尽量短,否则可能会死锁)

    6.原子上下文中不可睡眠,可以打开内核中的CONFIG_DEBUG_ATOMIC_SLEEP选项,运行时一旦检测出在原子上下文中可能睡眠就会打印栈回溯信息。

    7.进程的优先级使用nice值表示。

     

    二、进程调度


    1.目前4.14.35内核中只有下列sched_class:

    fair_sched_class: .next = idle_sched_class
    rt_sched_class  : .next = fair_sched_class
    dl_sched_class  : .next = rt_sched_class
    idle_sched_class: .next = NULL
    stop_sched_class: .next = dl_sched_class

    所有的调度类构成一个单链表:

    stop_sched_class --> dl_sched_class --> rt_sched_class --> fair_sched_class --> idle_sched_class --> NULL
    #ifdef CONFIG_SMP
    #define sched_class_highest (&stop_sched_class)
    #else
    #define sched_class_highest (&dl_sched_class)
    #endif
    #define for_each_class(class)   for (class = sched_class_highest; class; class = class->next)

    SCHED_NORMAL:普通的分时进程,使用的fair_sched_class调度类

    SCHED_FIFO:先进先出的实时进程,使用的是rt_sched_class调度类。
    当调用程序把CPU分配给进程的时候,它把该进程描述符保留在运行队列链表的当前位置。使用此调度策略的进程一旦使用CPU则一直运行。如果没有其他可运行的更高优先级实时进程,进程就会继续使用CPU,想用多久就用多久,即使还有其他具有相同优先级的实时进程处于可运行状态。

    http://blog.chinaunix.net/uid-24774106-id-3379478.html

    对于实时进程而言,高优先级的进程存在,低优先级的进程是轮不上的,没机会跑在CPU上,所谓实时进程的调度策略,指的是相同优先级之间的调度策略。如果是FIFO实时进程在占用CPU,除非出现以下事情,否则FIFO一条道跑到黑。
         a)FIFO进程良心发现,调用了系统调用sched_yield 自愿让出CPU
         b) 更高优先级的进程横空出世,抢占FIFO进程的CPU。有些人觉得很奇怪,怎么FIFO占着CPU,为啥还能有更高优先级的进程出现呢。别忘记,我们是多核多CPU ,如果其他CPU上出现了一个比FIFO优先级高的进程,可能会push到FIFO进程所在的CPU上。
         c)FIFO进程停止(TASK_STOPPED or TASK_TRACED状态)或者被杀死(EXIT_ZOMBIE or EXIT_DEAD状态)
         d) FIFO进程执行了阻塞调用并进入睡眠(TASK_INTERRUPTIBLE OR TASK_UNINTERRUPTIBLE)。

    SCHED_RR:时间片轮转的实时进程,使用的rt_sched_class调度类。
    当调度程序把CPU分配给进程的时候,它把该进程的描述符放在运行队列链表的末尾。这种策略保证对所有具有相同优先级的SCHED_RR实时进程
    进行公平分配CPU时间。

    SCHED_BATCH:是SCHED_NORMAL的分化版本,使用的fair_shed_class调度类。
    采用分时策略,根据动态优先级,分配CPU资源。在有实时进程的时候,实时进程优先调度。但针对吞吐量优化,除了不能抢占外与常规进程一
    样,允许任务运行更长时间,更好使用高速缓存,适合于成批处理的工作。

    SCHED_IDLE:优先级最低,在系统空闲时运行,使用的是idle_sched_class调度类,给0号进程使用。

    SCHED_DEADLINE:新支持的实时进程调度策略,使用的是dl_sched_class调度类。
    针对突发型计算,并且对延迟和完成时间敏感的任务使用,基于EDF(earliest deadline first)。

     

    2.调度类struct sched class

    struct sched_class {
        const struct sched_class *next;
    
        void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
        void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
        void (*yield_task) (struct rq *rq);
        bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
    
        void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
    
        /*
         * It is the responsibility of the pick_next_task() method that will
         * return the next task to call put_prev_task() on the @prev task or
         * something equivalent.
         *
         * May return RETRY_TASK when it finds a higher prio class has runnable tasks.
         */
        struct task_struct * (*pick_next_task) (struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
        void (*put_prev_task) (struct rq *rq, struct task_struct *p);
    
    #ifdef CONFIG_SMP
        int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
        void (*migrate_task_rq)(struct task_struct *p);
    
        void (*task_woken)(struct rq *this_rq, struct task_struct *task);
    
        void (*set_cpus_allowed)(struct task_struct *p, const struct cpumask *newmask);
    
        void (*rq_online)(struct rq *rq);
        void (*rq_offline)(struct rq *rq);
    #endif
    
        void (*set_curr_task) (struct rq *rq);
        void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
        void (*task_fork) (struct task_struct *p);
        void (*task_dead) (struct task_struct *p);
    
        /*
         * The switched_from() call is allowed to drop rq->lock, therefore we
         * cannot assume the switched_from/switched_to pair is serliazed by
         * rq->lock. They are however serialized by p->pi_lock.
         */
        void (*switched_from) (struct rq *this_rq, struct task_struct *task);
        void (*switched_to) (struct rq *this_rq, struct task_struct *task);
        void (*prio_changed) (struct rq *this_rq, struct task_struct *task, int oldprio);
    
        unsigned int (*get_rr_interval) (struct rq *rq, struct task_struct *task);
    
        void (*update_curr) (struct rq *rq);
    
    #define TASK_SET_GROUP  0
    #define TASK_MOVE_GROUP    1
    
    #ifdef CONFIG_FAIR_GROUP_SCHED
        void (*task_change_group) (struct task_struct *p, int type);
    #endif
    };

    next: 指向下一个调度类,用于在函数pick_next_task、check_preempt_curr、set_rq_online、set_rq_offline中遍历整个调度类,根据调度
    类的优先级选择调度类。
    优先级为: stop_sched_class-->dl_sched_class-->rt_sched_class-->fair_sched_class-->idle_sched_class
    enqueue_task: 将任务加入到调度类中
    dequeue_task: 将任务从调度类中移除
    yield_task/yield_to_task: 主动放弃CPU
    check_preempt_curr: 检查当前进程是否可被强占
    pick_next_task: 从调度类中选出下一个要运行的进程
    put_prev_task: 将进程放回到调度类中
    select_task_rq: 为进程选择一个合适的cpu的运行队列
    migrate_task_rq: 迁移到另外的cpu运行队列
    pre_schedule: 调度以前调用
    post_schedule: 通知调度器完成切换
    task_woken: 用于进程唤醒
    set_cpus_allowed: 修改进程cpu亲和力
    affinityrq_online: 启动运行队列
    rq_offline:关闭运行队列
    set_curr_task: 当进程改变调度类或者进程组时被调用
    task_tick: 将会引起进程切换,驱动运行running强占,由time_tick调用
    task_fork: 进程创建时调用,不同调度策略的进程初始化不一样
    task_dead: 进程结束时调用
    switched_from/switched_to:进程改变调度器时使用
    prio_changed: 改变进程优先级.

     

    3.调度的触发

    调度的触发主要有两种方式:

    (1)一种是本地定时中断触发调用scheduler_tick()函数,然后使用当前运行进程的调度类中的task_tick.
    (2)另外一种则是主动调用schedule().
    不管是哪一种最终都会调用到__schedule函数,该函数调用pick_netx_task,通过(rq->nr_running==rq->cfs.h_nr_running)判断出如果当前运行队列中的进程都在cfs调度器中,则直接调用cfs的调度类(内核代码里面这一判断使用了likely说明大部分情况都是满足该条件的)。如果运行队列不都在cfs中,则通过优先级stop_sched_class-->dl_sched_class-->rt_sched_class-->fair_sched_class-->idle_sched_class遍历选出下一个需要运行的进程,然后进程任务切换。


    4.发生调度的时机

    处于TASK_RUNNING状态的进程才会被进程调度器选择,其他状态不会进入调度器,系统发生调度的时机如下:
    a.调用cond_resched()时
    b.显式调用schedule()时
    c.从中断上下文返回时
    当内核开启抢占时,会多出几个调度时机:
    d.在系统调用中或者中断下文中调用preemt_enable()时

    5.__schedule()实现
    TODO:分析它


    6.CFS(Completely Fair Scheduler)调度

    该部分代码位于linux/kernel/sched/fair.c中,定义了const struct sched_classfair_sched_class,这个是CFS的调度类定义的对象。其中
    基本包含了CFS调度的所有实现。

    CFS实现三个调度策略:
    SCHED_NORMAL:这个调度策略是被常规任务使用
    SCHED_BATCH:这个策略不像常规的任务那样频繁的抢占,以牺牲交互性为代价下,因而允许任务运行更长的时间以更好的利用缓存,这种策略
    适合批处理。
    SCHED_IDLE:这是nice值甚至比19还弱,但是为了避免陷入优先级导致问题,这个问题将会死锁这个调度器,因而这不是一个真正空闲定时调
    度器。

    CFS调度类fair_sched_class:
    enqueue_task():当任务进入runnable状态,这个回调将把这个任务的调度实体(entity)放入红黑树并且增加nr_running变量的值。
    dequeue_task():当任务不再是runnable状态,这个回调将会把这个任务的调度实体从红黑树中取出,并且减少nr_running变量的值。
    yield_task():除非compat_yield sysctl是打开的,这个回调函数基本上就是一个dequeue后跟一个enqueue,这那种情况下,他将任务的调度
    实体放入红黑树的最右端
    check_preempt_curr():这个回调函数是检查一个任务进入runnable状态是否应该抢占当前运行的任务。
    pick_next_task():这个回调函数选出下一个最合适运行的任务。
    set_curr_task():当任务改变他的调度类或者改变他的任务组,将调用该回调函数。
    task_tick():这个回调函数大多数是被time tick调用。它可能引起进程切换,这就驱动了运行时抢占。

    /*
     * 一个调度实体(红黑树的一个节点),其包含一组或一个指定的进程,包含一个自己的运行队列,
     * 一个父亲指针,一个指向需要调度的队列.
     */
    struct sched_entity {
        /* For load-balancing: */
        struct load_weight        load; /*权重,在数组prio_to_weight[]包含优先级转权重的数值*/
        struct rb_node            run_node; /*实体在红黑树对应的节点信息*/
        struct list_head        group_node; /*实体所在的进程组*/
        unsigned int            on_rq;  /*实体是否处于红黑树运行队列中*/
    
        u64                exec_start; /*开始运行时间*/
        u64                sum_exec_runtime;  /*总运行时间*/
        /*
            虚拟运行时间,在时间中断或者任务状态发生改变时会更新.
            其会不停的增长,增长速度与load权重成反比,load越高,增长速度越慢,就越可能处于红黑树最左边
            被调度。每次时钟中断都会修改其值,具体见calc_delta_fair()函数
        */
        u64                vruntime;
        /*进程在切换进cpu时的sum_exec_runtime值*/
        u64                prev_sum_exec_runtime;
        /*此调度实体中进程移到其他cpu组的数量*/
        u64                nr_migrations;
    
        struct sched_statistics        statistics;
    
    #ifdef CONFIG_FAIR_GROUP_SCHED
        int                depth;
        /*
         父亲调度实体指针,如果是进程则指向其运行队列的调度实体,如果是进程组则指向其上一个进程组的
         调度实体,在set_task_rq函数中设置。
        */
        struct sched_entity        *parent;
        /* rq on which this entity is (to be) queued: */
        struct cfs_rq            *cfs_rq; /*实体所处红黑树运行队列*/
        /* rq "owned" by this entity/group: */
        struct cfs_rq            *my_q; /*实体的红黑树运行队列,如果为NULL表明其是一个进程,若非NULL表明其是调度组*/
    #endif
    
    #ifdef CONFIG_SMP
        /*
         * Per entity load average tracking.
         *
         * Put into separate cache line so it does not
         * collide with read-mostly values above.
         */
        struct sched_avg        avg ____cacheline_aligned_in_smp;
    #endif
    };

    load
    指定了权重, 决定了各个实体占队列总负荷的比重, 计算负荷权重是调度器的一项重任, 因为CFS所需的虚拟时钟的速度最终依赖于负荷, 权
    重通过优先级转换而成,是vruntime计算的关键
    run_node
    调度实体在红黑树对应的结点信息, 使得调度实体可以在红黑树上排序
    sum_exec_runtime
    记录程序运行所消耗的CPU时间, 以用于完全公平调度器CFS
    on_rq
    调度实体是否在就绪队列上接受检查, 表明是否处于CFS红黑树运行队列中,需要明确一个观点就是,CFS运行队列里面包含有一个红黑树,但
    这个红黑树并不是CFS运行队列的全部,因为红黑树仅仅是用于选择出下一个调度程序的算法。很简单的一个例子,普通程序运行时,其并不在
    红黑树中,但是还是处于CFS运行队列中,其on_rq为真。只有准备退出、即将睡眠等待和转为实时进程的进程其CFS运行队列的on_rq为假。
    vruntime
    虚拟运行时间,调度的关键,其计算公式:一次调度间隔的虚拟运行时间 = 实际运行时间 * (NICE_0_LOAD / 权重)。可以看出跟实际运行时
    间和权重有关,红黑树就是以此作为排序的标准,优先级越高的进程在运行时其vruntime增长的越慢,其可运行时间相对就长,而且也越有可
    能处于红黑树的最左结点,调度器每次都选择最左边的结点为下一个调度进程。注意其值为单调递增,在每个调度器的时钟中断时当前进程的
    虚拟运行时间都会累加。单纯的说就是进程们都在比谁的vruntime最小,最小的将被调度。
    cfs_rq
    此调度实体所处于的CFS运行队列
    my_q
    如果此调度实体代表的是一个进程组,那么此调度实体就包含有一个自己的CFS运行队列,其CFS运行队列中存放的是此进程组中的进程,这些
    进程就不会在其他CFS运行队列的红黑树中被包含(包括顶层红黑树也不会包含他们,他们只属于这个进程组的红黑树)。
    sum_exec_runtime
    跟踪运行时间是由update_curr不断累积完成的。内核中许多地方都会调用该函数, 例如, 新进程加入就绪队列时, 或者周期性调度器中. 每次
    调用时, 会计算当前时间和exec_start之间的差值, exec_start则更新到当前时间. 差值则被加到sum_exec_runtime.
    在进程执行期间虚拟时钟上流逝的时间数量由vruntime统计。
    在进程被撤销时, 其当前sum_exec_runtime值保存到prev_sum_exec_runtime, 此后, 进程抢占的时候需要用到该数据, 但是注意, 在prev_sum_exec_runtime
    中保存了sum_exec_runtime的值, 而sum_exec_runtime并不会被重置, 而是持续单调增长。

    每一个进程的task_struct中都嵌入了sched_entry对象,所以进程是可调度的实体,但是可调度的实体不一定是进程,也可能是进程组。


    7.CFS调度总结:

    Tcik中断,主要会更新调度信息,然后调整当前进程在红黑树中的位置。调整完成以后如果当前进程不再是最左边的叶子,就标记为Need_resched
    标志,中断返回时就会调用scheduler()完成切换、否则当前进程继续占用CPU。从这里可以看出CFS抛弃了传统时间片概念。Tick中断只需要更新红黑树。

    红黑树键值即为vruntime,该值通过调用update_curr函数进行更新。这个值为64位的变量,会一直递增,__enqueue_entity中会将vruntime作为键值将
    要入队的实体插入到红黑树中。__pick_first_entity会将红黑树中最左侧即vruntime最小的实体取出。

     

    优秀文章:

    Linux 2.6 Completely Fair Scheduler 内幕: https://www.ibm.com/developerworks/cn/linux/l-completely-fair-scheduler/index.html

     

    https://blog.csdn.net/zhoutaopower/article/details/86290196

    展开全文
  • 进程调度原理

    2016-04-09 23:16:53
     Linux进程调度的目标  1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;  2.加强交互性能:在系统相当的负载下,也要保证系统的响应时间;  3....

    Linux

        Linux进程调度的目标

        1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;

        2.加强交互性能:在系统相当的负载下,也要保证系统的响应时间;

        3.保证公平和避免饥渴;

        4.SMP调度:调度程序必须支持多处理系统;

        5.软实时调度:系统必须有效的调用实时进程,但不保证一定满足其要求;

    Linux进程优先级

      进程提供了两种优先级,一种是普通的进程优先级,第二个是实时优先级。前者适用SCHED_NORMAL调度策略,后者可选SCHED_FIFO或SCHED_RR调度策略。任何时候,实时进程的优先级都高于普通进程,实时进程只会被更高级的实时进程抢占,同级实时进程之间是按照FIFO(一次机会做完)或者RR(多次轮转)规则调度的。

      首先,说下实时进程的调度

      实时进程,只有静态优先级,因为内核不会再根据休眠等因素对其静态优先级做调整,其范围在0~MAX_RT_PRIO-1间。默认MAX_RT_PRIO配置为100,也即,默认的实时优先级范围是0~99。而nice值,影响的是优先级在MAX_RT_PRIO~MAX_RT_PRIO+40范围内的进程。

      不同与普通进程,系统调度时,实时优先级高的进程总是先于优先级低的进程执行。知道实时优先级高的实时进程无法执行。实时进程总是被认为处于活动状态。如果有数个 优先级相同的实时进程,那么系统就会按照进程出现在队列上的顺序选择进程。假设当前CPU运行的实时进程A的优先级为a,而此时有个优先级为b的实时进程B进入可运行状态,那么只要b<a,系统将中断A的执行,而优先执行B,直到B无法执行(无论A,B为何种实时进程)。

       不同调度策略的实时进程只有在相同优先级时才有可比性:

       1. 对于FIFO的进程,意味着只有当前进程执行完毕才会轮到其他进程执行。由此可见相当霸道。

       2. 对于RR的进程。一旦时间片消耗完毕,则会将该进程置于队列的末尾,然后运行其他相同优先级的进程,如果没有其他相同优先级的进程,则该进程会继续执行。

       总而言之,对于实时进程,高优先级的进程就是大爷。它执行到没法执行了,才轮到低优先级的进程执行。等级制度相当森严啊。

      重头戏,说下非实时进程调度

      引子 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    将当前目录下的documents目录打包,但不希望tar占用太多CPU:
     
    nice -19 tar zcf pack.tar.gz documents
     
    这个“-19”中的“-”仅表示参数前缀;所以,如果希望赋予tar进程最高的优先级,则执行:
     
    nice --19 tar zcf pack.tar.gz documents
     
    也可修改已经存在的进程的优先级:
     
    将PID为1799的进程优先级设置为最低:
     
    renice 19 1799
     
    renice命令与nice命令的优先级参数的形式是相反的,直接以优先级值作为参数即可,无“-”前缀说法。

       言归正传

        Linux对普通的进程,根据动态优先级进行调度。而动态优先级是由静态优先级(static_prio)调整而来。Linux下,静态优先级是用户不可见的,隐藏在内核中。而内核提供给用户一个可以影响静态优先级的接口,那就是nice值,两者关系如下:

      static_prio=MAX_RT_PRIO +nice+ 20

      nice值的范围是-20~19,因而静态优先级范围在100~139之间。nice数值越大就使得static_prio越大,最终进程优先级就越低。

      ps -el 命令执行结果:NI列显示的每个进程的nice值,PRI是进程的优先级(如果是实时进程就是静态优先级,如果是非实时进程,就是动态优先级)  

      而进程的时间片就是完全依赖 static_prio 定制的,见下图,摘自《深入理解linux内核》,

      

       我们前面也说了,系统调度时,还会考虑其他因素,因而会计算出一个叫进程动态优先级的东西,根据此来实施调度。因为,不仅要考虑静态优先级,也要考虑进程的属性。例如如果进程属于交互式进程,那么可以适当的调高它的优先级,使得界面反应地更加迅速,从而使用户得到更好的体验。Linux2.6 在这方面有了较大的提高。Linux2.6认为,交互式进程可以从平均睡眠时间这样一个measurement进行判断。进程过去的睡眠时间越多,则越有可能属于交互式进程。则系统调度时,会给该进程更多的奖励(bonus),以便该进程有更多的机会能够执行。奖励(bonus)从0到10不等。

      系统会严格按照动态优先级高低的顺序安排进程执行。动态优先级高的进程进入非运行状态,或者时间片消耗完毕才会轮到动态优先级较低的进程执行。动态优先级的计算主要考虑两个因素:静态优先级,进程的平均睡眠时间也即bonus。计算公式如下,

         dynamic_prio = max (100, min (static_prio - bonus + 5, 139))

      在调度时,Linux2.6 使用了一个小小的trick,就是算法中经典的空间换时间的思想[还没对照源码确认],使得计算最优进程能够在O(1)的时间内完成。

      为什么根据睡眠和运行时间确定奖惩分数是合理的

      睡眠和CPU耗时反应了进程IO密集和CPU密集两大瞬时特点,不同时期,一个进程可能即是CPU密集型也是IO密集型进程。对于表现为IO密集的进程,应该经常运行,但每次时间片不要太长。对于表现为CPU密集的进程,CPU不应该让其经常运行,但每次运行时间片要长。交互进程为例,假如之前其其大部分时间在于等待CPU,这时为了调高相应速度,就需要增加奖励分。另一方面,如果此进程总是耗尽每次分配给它的时间片,为了对其他进程公平,就要增加这个进程的惩罚分数。可以参考CFS的virtutime机制.

    现代方法CFS

      不再单纯依靠进程优先级绝对值,而是参考其绝对值,综合考虑所有进程的时间,给出当前调度时间单位内其应有的权重,也就是,每个进程的权重X单位时间=应获cpu时间,但是这个应得的cpu时间不应太小(假设阈值为1ms),否则会因为切换得不偿失。但是,当进程足够多时候,肯定有很多不同权重的进程获得相同的时间——最低阈值1ms,所以,CFS只是近似完全公平。

        详情参考 《linux内核cfs浅析

    Linux进程状态机

     

      

     

      进程是通过fork系列的系统调用(fork、clone、vfork)来创建的,内核(或内核模块)也可以通过kernel_thread函数创建内核进程。这些创建子进程的函数本质上都完成了相同的功能——将调用进程复制一份,得到子进程。(可以通过选项参数来决定各种资源是共享、还是私有。)
    那么既然调用进程处于TASK_RUNNING状态(否则,它若不是正在运行,又怎么进行调用?),则子进程默认也处于TASK_RUNNING状态。
    另外,在系统调用clone和内核函数kernel_thread也接受CLONE_STOPPED选项,从而将子进程的初始状态置为 TASK_STOPPED。

       进程创建后,状态可能发生一系列的变化,直到进程退出。而尽管进程状态有好几种,但是进程状态的变迁却只有两个方向——从TASK_RUNNING状态变为非TASK_RUNNING状态、或者从非TASK_RUNNING状态变为TASK_RUNNING状态。总之,TASK_RUNNING是必经之路,不可能两个非RUN状态直接转换。

    也就是说,如果给一个TASK_INTERRUPTIBLE状态的进程发送SIGKILL信号,这个进程将先被唤醒(进入TASK_RUNNING状态),然后再响应SIGKILL信号而退出(变为TASK_DEAD状态)。并不会从TASK_INTERRUPTIBLE状态直接退出。

        进程从非TASK_RUNNING状态变为TASK_RUNNING状态,是由别的进程(也可能是中断处理程序)执行唤醒操作来实现的。执行唤醒的进程设置被唤醒进程的状态为TASK_RUNNING,然后将其task_struct结构加入到某个CPU的可执行队列中。于是被唤醒的进程将有机会被调度执行。

       而进程从TASK_RUNNING状态变为非TASK_RUNNING状态,则有两种途径:

      1、响应信号而进入TASK_STOPED状态、或TASK_DEAD状态;
      2、执行系统调用主动进入TASK_INTERRUPTIBLE状态(如nanosleep系统调用)、或TASK_DEAD状态(如exit系统调用);或由于执行系统调用需要的资源得不到满     足,而进入TASK_INTERRUPTIBLE状态或TASK_UNINTERRUPTIBLE状态(如select系统调用)。
      显然,这两种情况都只能发生在进程正在CPU上执行的情况下。

     通过ps命令我们能够查看到系统中存在的进程,以及它们的状态:

    R(TASK_RUNNING),可执行状态。

    只有在该状态的进程才可能在CPU上运行。而同一时刻可能有多个进程处于可执行状态,这些进程的task_struct结构(进程控制块)被放入对应CPU的可执行队列中(一个进程最多只能出现在一个CPU的可执行队列中)。进程调度器的任务就是从各个CPU的可执行队列中分别选择一个进程在该CPU上运行。
    只要可执行队列不为空,其对应的CPU就不能偷懒,就要执行其中某个进程。一般称此时的CPU“忙碌”。对应的,CPU“空闲”就是指其对应的可执行队列为空,以致于CPU无事可做。
    有人问,为什么死循环程序会导致CPU占用高呢?因为死循环程序基本上总是处于TASK_RUNNING状态(进程处于可执行队列中)。除非一些非常极端情况(比如系统内存严重紧缺,导致进程的某些需要使用的页面被换出,并且在页面需要换入时又无法分配到内存……),否则这个进程不会睡眠。所以CPU的可执行队列总是不为空(至少有这么个进程存在),CPU也就不会“空闲”。

    很多操作系统教科书将正在CPU上执行的进程定义为RUNNING状态、而将可执行但是尚未被调度执行的进程定义为READY状态,这两种状态在linux下统一为 TASK_RUNNING状态。

    S(TASK_INTERRUPTIBLE),可中断的睡眠状态。

    处于这个状态的进程因为等待某某事件的发生(比如等待socket连接、等待信号量),而被挂起。这些进程的task_struct结构被放入对应事件的等待队列中。当这些事件发生时(由外部中断触发、或由其他进程触发),对应的等待队列中的一个或多个进程将被唤醒。

    通过ps命令我们会看到,一般情况下,进程列表中的绝大多数进程都处于TASK_INTERRUPTIBLE状态(除非机器的负载很高)。毕竟CPU就这么一两个,进程动辄几十上百个,如果不是绝大多数进程都在睡眠,CPU又怎么响应得过来。

    D(TASK_UNINTERRUPTIBLE),不可中断的睡眠状态。

    与TASK_INTERRUPTIBLE状态类似,进程处于睡眠状态,但是此刻进程是不可中断的。不可中断,指的并不是CPU不响应外部硬件的中断,而是指进程不响应异步信号。
    绝大多数情况下,进程处在睡眠状态时,总是应该能够响应异步信号的。否则你将惊奇的发现,kill -9竟然杀不死一个正在睡眠的进程了!于是我们也很好理解,为什么ps命令看到的进程几乎不会出现TASK_UNINTERRUPTIBLE状态,而总是TASK_INTERRUPTIBLE状态。

    而TASK_UNINTERRUPTIBLE状态存在的意义就在于,内核的某些处理流程是不能被打断的。如果响应异步信号,程序的执行流程中就会被插入一段用于处理异步信号的流程(这个插入的流程可能只存在于内核态,也可能延伸到用户态),于是原有的流程就被中断了(参见《linux异步信号handle浅析》)。
    在进程对某些硬件进行操作时(比如进程调用read系统调用对某个设备文件进行读操作,而read系统调用最终执行到对应设备驱动的代码,并与对应的物理设备进行交互),可能需要使用TASK_UNINTERRUPTIBLE状态对进程进行保护,以避免进程与设备交互的过程被打断,造成设备陷入不可控的状态。(比如read系统调用触发了一次磁盘到用户空间的内存的DMA,如果DMA进行过程中,进程由于响应信号而退出了,那么DMA正在访问的内存可能就要被释放了。)这种情况下的TASK_UNINTERRUPTIBLE状态总是非常短暂的,通过ps命令基本上不可能捕捉到。

    linux系统中也存在容易捕捉的TASK_UNINTERRUPTIBLE状态。执行vfork系统调用后,父进程将进入TASK_UNINTERRUPTIBLE状态,直到子进程调用exit或exec。
    通过下面的代码就能得到处于TASK_UNINTERRUPTIBLE状态的进程:
    #include <unistd.h>
    void main() {
    if (!vfork()) sleep(100);
    }
    编译运行,然后ps一下:
    kouu@kouu-one:~/test$ ps -ax | grep a\.out
    4371 pts/0 D+ 0:00 ./a.out
    4372 pts/0 S+ 0:00 ./a.out
    4374 pts/1 S+ 0:00 grep a.out
    然后我们可以试验一下TASK_UNINTERRUPTIBLE状态的威力。不管kill还是kill -9,这个TASK_UNINTERRUPTIBLE状态的父进程依然屹立不倒。

    T(TASK_STOPPED or TASK_TRACED),暂停状态或跟踪状态。

    向进程发送一个SIGSTOP信号,它就会因响应该信号而进入TASK_STOPPED状态(除非该进程本身处于TASK_UNINTERRUPTIBLE状态而不响应信号)。(SIGSTOP与SIGKILL信号一样,是非常强制的。不允许用户进程通过signal系列的系统调用重新设置对应的信号处理函数。)
    向进程发送一个SIGCONT信号,可以让其从TASK_STOPPED状态恢复到TASK_RUNNING状态。

    当进程正在被跟踪时,它处于TASK_TRACED这个特殊的状态。“正在被跟踪”指的是进程暂停下来,等待跟踪它的进程对它进行操作。比如在gdb中对被跟踪的进程下一个断点,进程在断点处停下来的时候就处于TASK_TRACED状态。而在其他时候,被跟踪的进程还是处于前面提到的那些状态。
    对于进程本身来说,TASK_STOPPED和TASK_TRACED状态很类似,都是表示进程暂停下来。
    而TASK_TRACED状态相当于在TASK_STOPPED之上多了一层保护,处于TASK_TRACED状态的进程不能响应SIGCONT信号而被唤醒。只能等到调试进程通过ptrace系统调用执行PTRACE_CONT、PTRACE_DETACH等操作(通过ptrace系统调用的参数指定操作),或调试进程退出,被调试的进程才能恢复TASK_RUNNING状态。

    Z(TASK_DEAD - EXIT_ZOMBIE),退出状态,进程成为僵尸进程。

    进程在退出的过程中,处于TASK_DEAD状态。

    在这个退出过程中,进程占有的所有资源将被回收,除了task_struct结构(以及少数资源)以外。于是进程就只剩下task_struct这么个空壳,故称为僵尸。
    之所以保留task_struct,是因为task_struct里面保存了进程的退出码、以及一些统计信息。而其父进程很可能会关心这些信息。比如在shell中,$?变量就保存了最后一个退出的前台进程的退出码,而这个退出码往往被作为if语句的判断条件。
    当然,内核也可以将这些信息保存在别的地方,而将task_struct结构释放掉,以节省一些空间。但是使用task_struct结构更为方便,因为在内核中已经建立了从pid到task_struct查找关系,还有进程间的父子关系。释放掉task_struct,则需要建立一些新的数据结构,以便让父进程找到它的子进程的退出信息。

    父进程可以通过wait系列的系统调用(如wait4、waitid)来等待某个或某些子进程的退出,并获取它的退出信息。然后wait系列的系统调用会顺便将子进程的尸体(task_struct)也释放掉。
    子进程在退出的过程中,内核会给其父进程发送一个信号,通知父进程来“收尸”。这个信号默认是SIGCHLD,但是在通过clone系统调用创建子进程时,可以设置这个信号。

    通过下面的代码能够制造一个EXIT_ZOMBIE状态的进程:
    #include <unistd.h>
    void main() {
    if (fork())
    while(1) sleep(100);
    }
    编译运行,然后ps一下:
    kouu@kouu-one:~/test$ ps -ax | grep a\.out
    10410 pts/0 S+ 0:00 ./a.out
    10411 pts/0 Z+ 0:00 [a.out] <defunct>
    10413 pts/1 S+ 0:00 grep a.out

    只要父进程不退出,这个僵尸状态的子进程就一直存在。那么如果父进程退出了呢,谁又来给子进程“收尸”?
    当进程退出的时候,会将它的所有子进程都托管给别的进程(使之成为别的进程的子进程)。托管给谁呢?可能是退出进程所在进程组的下一个进程(如果存在的话),或者是1号进程。所以每个进程、每时每刻都有父进程存在。除非它是1号进程。

    1号进程,pid为1的进程,又称init进程。
    linux系统启动后,第一个被创建的用户态进程就是init进程。它有两项使命:
    1、执行系统初始化脚本,创建一系列的进程(它们都是init进程的子孙);
    2、在一个死循环中等待其子进程的退出事件,并调用waitid系统调用来完成“收尸”工作;
    init进程不会被暂停、也不会被杀死(这是由内核来保证的)。它在等待子进程退出的过程中处于TASK_INTERRUPTIBLE状态,“收尸”过程中则处于TASK_RUNNING状态。

    X(TASK_DEAD - EXIT_DEAD),退出状态,进程即将被销毁。

    而进程在退出过程中也可能不会保留它的task_struct。比如这个进程是多线程程序中被detach过的进程(进程?线程?参见《linux线程浅析》)。或者父进程通过设置SIGCHLD信号的handler为SIG_IGN,显式的忽略了SIGCHLD信号。(这是posix的规定,尽管子进程的退出信号可以被设置为SIGCHLD以外的其他信号。)
    此时,进程将被置于EXIT_DEAD退出状态,这意味着接下来的代码立即就会将该进程彻底释放。所以EXIT_DEAD状态是非常短暂的,几乎不可能通过ps命令捕捉到。

     

    一些重要的杂项

    调度程序的效率
    “优先级”明确了哪个进程应该被调度执行,而调度程序还必须要关心效率问题。调度程序跟内核中的很多过程一样会频繁被执行,如果效率不济就会浪费很多CPU时间,导致系统性能下降。
    在linux 2.4时,可执行状态的进程被挂在一个链表中。每次调度,调度程序需要扫描整个链表,以找出最优的那个进程来运行。复杂度为O(n);
    在linux 2.6早期,可执行状态的进程被挂在N(N=140)个链表中,每一个链表代表一个优先级,系统中支持多少个优先级就有多少个链表。每次调度,调度程序只需要从第一个不为空的链表中取出位于链表头的进程即可。这样就大大提高了调度程序的效率,复杂度为O(1);
    在linux 2.6近期的版本中,可执行状态的进程按照优先级顺序被挂在一个红黑树(可以想象成平衡二叉树)中。每次调度,调度程序需要从树中找出优先级最高的进程。复杂度为O(logN)。

    那么,为什么从linux 2.6早期到近期linux 2.6版本,调度程序选择进程时的复杂度反而增加了呢?
    这是因为,与此同时,调度程序对公平性的实现从上面提到的第一种思路改变为第二种思路(通过动态调整优先级实现)。而O(1)的算法是基于一组数目不大的链表来实现的,按我的理解,这使得优先级的取值范围很小(区分度很低),不能满足公平性的需求。而使用红黑树则对优先级的取值没有限制(可以用32位、64位、或更多位来表示优先级的值),并且O(logN)的复杂度也还是很高效的。

    调度触发的时机
    调度的触发主要有如下几种情况:
    1、当前进程(正在CPU上运行的进程)状态变为非可执行状态。
    进程执行系统调用主动变为非可执行状态。比如执行nanosleep进入睡眠、执行exit退出、等等;
    进程请求的资源得不到满足而被迫进入睡眠状态。比如执行read系统调用时,磁盘高速缓存里没有所需要的数据,从而睡眠等待磁盘IO;
    进程响应信号而变为非可执行状态。比如响应SIGSTOP进入暂停状态、响应SIGKILL退出、等等;

    2、抢占。进程运行时,非预期地被剥夺CPU的使用权。这又分两种情况:进程用完了时间片、或出现了优先级更高的进程。
    优先级更高的进程受正在CPU上运行的进程的影响而被唤醒。如发送信号主动唤醒,或因为释放互斥对象(如释放锁)而被唤醒;
    内核在响应时钟中断的过程中,发现当前进程的时间片用完;
    内核在响应中断的过程中,发现优先级更高的进程所等待的外部资源的变为可用,从而将其唤醒。比如CPU收到网卡中断,内核处理该中断,发现某个socket可读,于是唤醒正在等待读这个socket的进程;再比如内核在处理时钟中断的过程中,触发了定时器,从而唤醒对应的正在nanosleep系统调用中睡眠的进程;

    内核抢占
    理想情况下,只要满足“出现了优先级更高的进程”这个条件,当前进程就应该被立刻抢占。但是,就像多线程程序需要用锁来保护临界区资源一样,内核中也存在很多这样的临界区,不大可能随时随地都能接收抢占。
    linux 2.4时的设计就非常简单,内核不支持抢占。进程运行在内核态时(比如正在执行系统调用、正处于异常处理函数中),是不允许抢占的。必须等到返回用户态时才会触发调度(确切的说,是在返回用户态之前,内核会专门检查一下是否需要调度);
    linux 2.6则实现了内核抢占,但是在很多地方还是为了保护临界区资源而需要临时性的禁用内核抢占。

    也有一些地方是出于效率考虑而禁用抢占,比较典型的是spin_lock。spin_lock是这样一种锁,如果请求加锁得不到满足(锁已被别的进程占有),则当前进程在一个死循环中不断检测锁的状态,直到锁被释放。
    为什么要这样忙等待呢?因为临界区很小,比如只保护“i+=j++;”这么一句。如果因为加锁失败而形成“睡眠-唤醒”这么个过程,就有些得不偿失了。
    那么既然当前进程忙等待(不睡眠),谁又来释放锁呢?其实已得到锁的进程是运行在另一个CPU上的,并且是禁用了内核抢占的。这个进程不会被其他进程抢占,所以等待锁的进程只有可能运行在别的CPU上。(如果只有一个CPU呢?那么就不可能存在等待锁的进程了。)
    而如果不禁用内核抢占呢?那么得到锁的进程将可能被抢占,于是可能很久都不会释放锁。于是,等待锁的进程可能就不知何年何月得偿所望了。

    对于一些实时性要求更高的系统,则不能容忍spin_lock这样的东西。宁可改用更费劲的“睡眠-唤醒”过程,也不能因为禁用抢占而让更高优先级的进程等待。比如,嵌入式实时linux montavista就是这么干的。
    由此可见,实时并不代表高效。很多时候为了实现“实时”,还是需要对性能做一定让步的。

    多处理器下的负载均衡
    前面我们并没有专门讨论多处理器对调度程序的影响,其实也没有什么特别的,就是在同一时刻能有多个进程并行地运行而已。那么,为什么会有“多处理器负载均衡”这个事情呢?
    如果系统中只有一个可执行队列,哪个CPU空闲了就去队列中找一个最合适的进程来执行。这样不是很好很均衡吗?
    的确如此,但是多处理器共用一个可执行队列会有一些问题。显然,每个CPU在执行调度程序时都需要把队列锁起来,这会使得调度程序难以并行,可能导致系统性能下降。而如果每个CPU对应一个可执行队列则不存在这样的问题。
    另外,多个可执行队列还有一个好处。这使得一个进程在一段时间内总是在同一个CPU上执行,那么很可能这个CPU的各级cache中都缓存着这个进程的数据,很有利于系统性能的提升。
    所以,在linux下,每个CPU都有着对应的可执行队列,而一个可执行状态的进程在同一时刻只能处于一个可执行队列中。

    于是,“多处理器负载均衡”这个麻烦事情就来了。内核需要关注各个CPU可执行队列中的进程数目,在数目不均衡时做出适当调整。什么时候需要调整,以多大力度进程调整,这些都是内核需要关心的。当然,尽量不要调整最好,毕竟调整起来又要耗CPU、又要锁可执行队列,代价还是不小的。
    另外,内核还得关心各个CPU的关系。两个CPU之间,可能是相互独立的、可能是共享cache的、甚至可能是由同一个物理CPU通过超线程技术虚拟出来的……CPU之间的关系也是实现负载均衡的重要依据。关系越紧密,进程在它们之间迁移的代价就越小。参见《linux内核SMP负载均衡浅析》。

    优先级继承
    由于互斥,一个进程(设为A)可能因为等待进入临界区而睡眠。直到正在占有相应资源的进程(设为B)退出临界区,进程A才被唤醒。
    可能存在这样的情况:A的优先级非常高,B的优先级非常低。B进入了临界区,但是却被其他优先级较高的进程(设为C)抢占了,而得不到运行,也就无法退出临界区。于是A也就无法被唤醒。
    A有着很高的优先级,但是现在却沦落到跟B一起,被优先级并不太高的C抢占,导致执行被推迟。这种现象就叫做优先级反转。

    出现这种现象是很不合理的。较好的应对措施是:当A开始等待B退出临界区时,B临时得到A的优先级(还是假设A的优先级高于B),以便顺利完成处理过程,退出临界区。之后B的优先级恢复。这就是优先级继承的方法。

    中断处理线程化
    在linux下,中断处理程序运行于一个不可调度的上下文中。从CPU响应硬件中断自动跳转到内核设定的中断处理程序去执行,到中断处理程序退出,整个过程是不能被抢占的。
    一个进程如果被抢占了,可以通过保存在它的进程控制块(task_struct)中的信息,在之后的某个时间恢复它的运行。而中断上下文则没有task_struct,被抢占了就没法恢复了。
    中断处理程序不能被抢占,也就意味着中断处理程序的“优先级”比任何进程都高(必须等中断处理程序完成了,进程才能被执行)。但是在实际的应用场景中,可能某些实时进程应该得到比中断处理程序更高的优先级。
    于是,一些实时性要求更高的系统就给中断处理程序赋予了task_struct以及优先级,使得它们在必要的时候能够被高优先级的进程抢占。但是显然,做这些工作是会给系统造成一定开销的,这也是为了实现“实时”而对性能做出的一种让步。

     

    参考文献:《linux内核设计与实现》

           《现代操作系统》

           《进程调度的红黑树实现分析

         《linux内核SMP负载均衡浅析》(本文未引用可以做拓展参考)

         《linux内核cfs浅析

    转自http://www.cnblogs.com/zhaoyl/archive/2012/09/04/2671156.html

    展开全文
  • 多任务抢占式调度器

    2020-01-15 17:58:49
    以ARM9为平台,介绍一个多任务抢占式调度器。抢占式调度器提供:延时,挂起,恢复任务操作。没有加入信号量邮箱等同步通信机制,只是实现一个基本的任务调度功能。 多任务原理的印象<建立一个属于自己的AVR的...
  • User Preemption User preemption occurs when the kernel is about to return to ...抢占式内核实现的原理是在释放自旋锁时或从中断返回时,如果当前执行进程的 need_resched  被标记,则进行抢占式调度
  • 进程原理(中):进程调度 PS:在多进程并发的环境里,虽然从概念上看,有多个进程在同时执行,但在单个CPU下,在任何时刻只能有一个进程处于执行状态,而其他进程则处于非执行状态。那么问题来了,我们是如何...
  • 1,进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是分配资源的基本单位,线程是进程的一个实体,是CPU调度和分派的基本单位 2,线程不能够独立执行,必须依存在应用程序中,由应用程序提供多个...
  • 抢占式多任务 非抢占式多任务 进程分类 IO消耗型:进程的大部分时间用来提交I/O请求或是等待I/O请求。 处理器消耗型:进程的大部分时间在执行代码 进程优先级 根据进程的价值和其对处理器的时间需求对进程进行...
  • 进程控制原理

    2014-08-24 19:42:11
    进程是一个具有一定独立gongne
  • linux进程管理原理

    千次阅读 2017-08-16 05:09:57
    Linux 是一种动态系统,能够适应不断变化的计算需求。... 在用户空间,进程是由进程标识符(PID)表示的。从用户的角度来看,一个 PID 是一个数字值,可惟一标识一个进程。一个 PID 在进程的整个生命期间不会更
  • 进程调度原理: Linux进程调度的目标  1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;  2.加强交互性能:在系统相当的负载下,也要保证系统的...
  • Linux进程基本原理

    2019-07-13 23:33:00
    主题进程介绍 一进程相关概念 内核的功用:进程管理、文件系统、网络功能、内存管理、驱动程序、安全功能等 在操作系统上会运行多个应用程序,应用程序分配多大的内存都由内核实现 程序文件 ...
  • 轮询任务调度与抢占式任务调度的区别在于抢占式调度中的优先级可以抢占CPU,而轮询的不能。具体而言,轮询调度的原理是每一次把来自用户的请求轮流的分配给内部服务器,从1开始,直到N(内部服务器的个数),然
  • Linux进程调度原理

    2015-03-02 09:55:10
    引荐原文,本文介绍非常不错,虽然文字描述居多,但是,...Linux进程调度的目标  1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;  2.加强交互性能
  • Linux系统的进程调度策略 :SCHED_NORMAL、SCHED_FIFO或SCHED_RR。进程静态优先级、动态优先级以及进程状态之间的转换,以及优先级反转问题的处理方法,深入理解多处理器下资源和效率以及性能平衡的原理
  • Linux进程调用原理

    千次阅读 2015-08-15 22:56:36
    Linux进程调度原理  Linux进程调度的目标  1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;  2.加强交互性能:在系统相当的负载下,也要...
  • 一文搞懂Linux进程调度原理

    千次阅读 2021-02-03 14:40:01
    linux进程相关视频解析: 初识Linux内核,进程通信能这么玩 linux内核,进程调度器的实现,完全公平调度器 CFS Linux进程调度的目标 1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,...
  • 抢占式操作系统中,假设有若干进程,操作系统会根据他们的优先级、饥饿时间(已经多长时间没有使用过 CPU 了),给他们算出一 个总的优先级来。操作系统就会把 CPU 交给总优先级最高的这个进程。当进程执行完毕...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,049
精华内容 5,219
关键字:

抢占式进程的原理