关于操作系统:线程是如何调度的

在操作系统中，线程是如何调度的？或者是线程调度有哪些办法？

最近在补充一些操作系统的常识，线程调度是操作系统无奈回避的问题。对其由浅入深的解决思路大有感触，在此记录。

先到先解决

对于操作系统而言，线程相当于一个个待执行的工作。最常见用于任务调度的是队列，队列是任务调度的最简略模型，听从先到先解决的准则，一个工作解决实现之后，才会解决下一个工作。

相对而言，队列模型是最偏心的，工作的执行程序只与进入队列的工夫相干，同时，因为不存在工作切换等，所以没有额定的逻辑代码开销。

上面是用 js 实现的一个任务调度的队列模型：

// 模仿 sleep
function sleep(ms) {for (let t = Date.now(); Date.now() - t <= ms;);
}

// 调度器对象
class scheduler {constructor() {
        // 队列
        this.queue = []}

    // 压入工作
    pushTask(task) {this.queue.push(task)
    }

    // 获取下一个待执行的工作
    next() {if (this.queue.length > 0) {
            // 获取最先进入的一个
            return this.queue.shift()}
        return undefined
    }

    // 执行
    excute() {
        // 一直的循环执行
        while (true) {const nextTask = this.next()
            if (nextTask) {nextTask()
            } else {sleep(1000)
            }
        }
    }
}

队列模型对于调度器而言是偏心的，调度器平等的解决每一个工作，然而对于工作来说是不偏心的，因为后进入队列的工作须要期待后面的工作执行实现能力执行。对于一个须要执行 1 天的工作，让其期待 10 分钟是能够承受的，然而如果一个须要执行 10 分钟的工作，须要期待一天，就无奈承受，对于这种状况须要思考 短工作优先。

短工作优先

对于操作系统，线程能够看作是一个个用户，用户满意度能够掂量调度零碎的好坏。咱们能够用均匀等待时间来近似掂量用户满意度，均匀等待时间和满意度成反比，均匀等待时间越长，用户满意度越差。

比方一个蕴含三个工作的队列[10, 2, 5]，队列中的每一项代表工作执行工夫。

当工作顺次执行时，那么均匀等待时间为：(0 + 10 + 2) / 3 = 4。

当队列依照工作执行工夫由小到大排列后，即队列变成[2, 5, 10]，那么均匀等待时间为: (0 + 2 + 5) / 3 = 2.33。

从下面两种状况的比照中能够看出，排序后的队列均匀等待时间较短，即用户的满意度较高，也就是短工作优先。

调整前文说的调度器对象，在每次获取下一个可执行工作之前，将所有工作依照执行工夫由小到大排序：

    // 获取下一个待执行的工作
    next() {if (this.queue.length > 0) {
            // 排序
            this.queue.sort((a, b) => a.excuteTime - b.excuteTime)
            // 获取最先进入的一个
            return this.queue.shift()}
        return undefined
    }

在队列模型中退出了短工作优先之后，满足了线程调度满意度，然而该模型还存在问题，即如果有重要工作须要插队应该怎么办？解决此问题就须要用到优先级。

优先级

针对工作插队的状况，能够在原有调度对象上减少优先级，行将其外部的一个队列拆分成多个具备不同优先级的队列，调度器总是先获取高优先级中的工作，当高优先级中不存在工作的时候，才去获取低优先级中的工作。

批改前文的调度器对象：

// 调度器对象
class scheduler {constructor() {
        // 队列
        this.queue = {high: [],
            medium: [],
            low: []}
    }

    // 压入工作
    pushTask(task, priority) {this.queue[priority].push(task)
    }

    // 获取下一个待执行的工作: 依照优先级顺次由高到低取
    next() {function getQueueNext(queue) {if (queue.length > 0) {
                // 排序
                queue.sort((a, b) => a.excuteTime - b.excuteTime)
                // 获取最先进入的一个
                return queue.shift()}
            return undefined
        }

        const priorityMap = Object.keys(this.queue)
        let next
        // 循环执行，当高优先级中没有取到工作，那么就从低优先级中获取
        while (!undefined && priorityMap.length > 0) {const currentPriority = priorityMap.shift()
            next = getQueueNext(this.queue[currentPriority])
        }
        return next
    }

    // 执行
    excute() {
        // 一直的循环执行
        while (true) {const nextTask = this.next()
            if (nextTask) {nextTask()
            } else {sleep(1000)
            }
        }
    }
}

当退出优先级之后，当新的工作须要插队执行的时候，能够将其增加到优先级较高的队列中，这样能够保障在当前任务执行实现后，插队的工作能够被优先执行。

尽管退出优先级之后，能够应答须要插队的状况。然而因为目前调度器都是执行完上一次工作之后才执行下一次工作，当呈现耗时较长的工作执行到一半的时候，进来一个耗时较短的工作须要执行的状况时，便无奈解决。针对这种状况，能够退出抢占机制。

抢占

抢占就是将操作系统的执行能力分时，分成多个执行片段，默认工作只执行一个工夫片段，当一个片段内工作被执行实现，就会执行下一个工作，如果未执行实现，也会执行下一个工作，然而以后未执行实现的工作会被终端，从新进入队列排队，

退出抢占性能之后，操作系统的线程执行就变成了一段段的工夫片段，每一次执行片段完结，调度零碎就会为操作系统调配下一个执行工作。这样就保障不会因为长耗时工作的执行导致短耗时工作无奈及时执行。

通过为队列退出优先级和抢占机制之后，以后线程的调度零碎曾经比较完善成熟。然而在短工作优先一节中提到须要将工作依照耗时长短进行排序，而操作系统是无奈预知线程的执行工夫的？

多级队列

为了解决操作系统无奈预知线程执行工夫的问题，须要优化优先级章节中提到的多优先级队列。

假如咱们的调度零碎中有多级队列，最高优先级的队列用于执行紧急任务，其外部不蕴含抢占机制，其余的队列中蕴含抢占机制，并且，优先级越低的队列执行工夫片段越长。

如一个调度零碎中，蕴含三种优先级队列，从高到低一次为 A,B,C，其中 A 队列为紧急任务队列，不分时执行，B，C 队列为分时队列，B 的分时为 1s，C 的分时为 2s。

当紧急任务须要被调度执行的时候，其会被调度零碎放入 A 队列优先执行。

当一个一般工作被调度执行的时候，其会被放入一般的 B 队列，因为 B 队列是分时执行的，当 1s 的工夫内，该工作没有被执行实现，那么该工作的执行会被中断，同时调度零碎会将该工作放入下一级队列中（C）排队。

当队列的级数越来越多时，能够通过层层筛选将长耗时的工作筛选进去，近似实现短工作优先。