【操作系统】一、进程和线程的调度

首先明确一个概念，Linux系统中甚至没有真正的线程。不过，可以认为Linux是系统的线程是内核线程，所以调度是基于线程的。

一个进程由于其运行空间的不同, 从而有内核线程和用户进程的区分, 内核线程运行在内核空间, 之所以称之为线程是因为它没有虚拟地址空间, 只能访问内核的代码和数据, 而用户进程则运行在用户空间, 但是可以通过中断, 系统调用等方式从用户态陷入内核态。

用户进程运行在用户空间上, 而一些通过共享资源实现的一组进程我们称之为线程组, Linux下内核其实本质上没有线程的概念, Linux下线程其实上是与其他进程共享某些资源的进程而已。但是我们习惯上还是称他们为线程或者轻量级进程。

因此, Linux上进程分3种，内核线程（或者叫核心进程）、用户进程、用户线程, 当然如果更严谨的，也可以认为用户进程和用户线程都是用户进程。

Linux中，进程和线程都被维护为一个task_struct结构，线程和进程被同等对待来进行调度。

Linux将线程区分为3类：

（1）实时先入先出。

（2）实时轮转。

（3）分时。

实时先入先出有最高的优先级，不会被其他线程抢占，除非是另外一个刚刚准备好的且优先级更高的实时先入先出线程。

实时轮转线程与实时先入先出类似，不过有一个轮转体系，即分配一个时间片，时间到了就可以被抢占。时间片消耗完就进入实时轮转线程列表的末尾。其实，这两种都不是真的实时，因为执行的最后期限无法确定，只是比分时线程有更高的优先级。

实时线程的优先级从0-99,0是实时线程的最高优先级，99是实时线程的最低优先级。

传统的非实时线程，优先级从100-139。Linux系统根据非实时线程的优先级分配时间量。

Linux使用一个重要的结构，调度队列。每个CPU有自己的调度队列，包括两个数组：活动的和过期失效的。每个数组包括了140个链表头，对应140个优先级的链表。

调度器从正在活动数组中选择一个优先级最高的任务，如果时间片耗尽失效，就加入到过期失效数组中。如果进程在时间片内被阻塞，那么在时间片失效之前，等待的事件发生就可以继续运行，放回到正在活动的数组中。如果活动数组没有任务了，调度器交换指针，使得活动数组和失效数组调换。

不同的优先级被赋予不同的时间片长度，优先级越高的进程，时间片越长。

Linux采用静态优先级与动态优先级结合的方式。Linux采用了奖惩机制，目的在于奖励互动进程以及惩罚占用CPU的进程。一个进程初始被赋予了一个优先级，耗尽和阻塞会改变nice值，活动与过期进程转换时，动态改变进程优先级。

另外，对于多核处理器，运行队列数据结构与某一个处理器相对应，调度器尽量进行亲和调度，即将之前在某个处理器上运行过的任务再次调入该处理器。

调度器只考虑可以运行的任务，不可运行的任务和正在等待各种I/O操作的或内核事件的任务被放入等待队列中。每一种等待某种事件的任务组成一个等待队列。等待队列的头部包含一个指向任务链表的指针及一个自旋锁。

参考：

https://www.cnblogs.com/lustar/p/7716165.html