CPU Scheduling

CPU Scheduling

CPU调度程序

基本概念：

  • 多道程序设计的目的将CPU 的利用率最大化。
  • 多个进程同时存在于内存（并发），当一个进程暂不使用CPU时，系统调度另一 个进程占用CPU。

CPU-burst Durrations(CPU突发事件持续时间)

如图：横轴为突发时间持续时间，纵轴为发生的频率

我们将时间位于 0 - 8ms 中的进程称为 CPU-bound program 也可以被称为短进程 ，大于 8ms的进程称为 I/O-bound program 也可以被称为长进程，从频率长看大多数进程属于短进程

CPU调度程序

Whenever the CPU becomes idle(闲置), the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the CPU scheduler.

存在两种调度方法：

  • 非抢占调度（Nonpreemptive scheduling）：一旦某个进程得到CPU，就会一直占用到终止或等待状态。
  • 抢占调度 (preemptive scheduling)：调度程序被动被动离开CPU如：时间片到期

CPU调度准则

调度算法的衡量

  • CPU利用率：CPU的忙碌程度
  • 响应时间：从提交任务到第一次响应的时间，针对交互式系统
  • 等待时间：进程累积在就绪队列中等待的时间
  • 周转时间：从提交到完成的时间
  • 呑吐率：每个时钟单位处理的任务数
  • 公平性：以合理的方式让各个进程共享CPU

假设作业 i 提交给系统的时刻是ts，完成的时刻是tf， 所需运行时间为 tk，那么：

单个作业的周转时间 ti：完成时间 - 开始时间
$$
ti = tf - ts
$$
平均作业周转时间 T：n为操作系统的进程数，将每个进程的周转时间累加后在平均
$$
T = \sum_{i=1}^n ti \times 1 / n
$$

调度算法

先来先服务(FCFS）

  • First-Come, First-Served (FCFS)

    • 早期系统里，FCFS意味着一个程序会一直运行到结束(尽管其中会出 现等待I/O的情况)

    • 非抢占式

    • 如今，当一个程序阻塞时会让出CPU

      假设当前就绪队列中依次存在 p1 p2 p3 p4 四个进程，p1 开始运行，运行过程中调用IO设备，此时将让出CPU进入等待状态，位于就绪队列队头的 p2 被调度器从就绪队列中取出进入运行状态，一段时间后 p1 完成IO操作要返回就绪队列，要注意的是，p1入队(从队尾入队)

      第二种排列方式比第一种要好，平均周转时间缩短为18

    • 优点：简单易行
      缺点：需要控制进程先到的顺序才能时平均周转时间减少

时间片轮转(ROUND ROBIN)

  • 时间片轮转(ROUND ROBIN)

    • 每个进程都可以得到相同的CPU时间(CPU时间片, time slice)，当时间片到达，进程将被剥夺CPU并加入就绪队列的尾部 。（分时系统）
    • 抢占式调度算法
    • n个就绪队列中的进程和时间片q：
      每个进程获得1/n的CPU时间，大约是q个时间单位
      没有进程等待时间会超过 (n-1)q
    • 例题：

    等待时间分别是：

    P1=(68-20)+(112-88)+(145-132)=85 P2=(20-0)+(88-40)+(132-108)=92
    P3=(40-0)+(108-60)=88 dP4=(60-0)=60

    • 平均等待时间 = (85+92+88+60)/4=81.25
    • 平均周转时间 = (153+145+112+68)/4=119.5
    • RR算法分析
      • 时间片（time slice）取选
        • 取值太小：进程切换开销显著增大(不能小于进程切换的时间)
        • 取值较大：响应速度下降（取值无穷大将退化成FCFS）
        • 一般时间片的选取范围为 10ms~100ms
        • 上下文切换的时间大概为 0.1ms~1ms （1%的CPU时间开销）
      • RR算法优缺点
        • 公平算法(+)
        • 对长作业带来额外的切换开销(-)

最短作业优先(SJF)

  • SJF(Shortest Job First)：下一次调度总是选择所需要 CPU时间最短的那个作业（进程）。

    在FCFS算法中，我们提及到，如果我们知道每个作业所需的运行时长，并按照时长从低到高的顺序依次服务，这样求出的平均周转时间是很低的，这也就是SJF算法的由来

  • SJF是一个非抢占式的算法，当人也可以改造为一个抢占式SRTF

    以上图举例：当0时刻P1到达，1时刻 P2 到达，此时 P1 的剩余时间就变为 7 P2 剩余时间少于 P1 故优先运行 P2，依次类推直至进程全部运行完成

  • SJF/SRTF算法分析

    • 该算法总是将短进程移到长进程之前执行，因此平均等待时间 最小，该算法被证明是最优的。
    • 饥饿现象：长进程可能长时间无法获得CPU
    • 该算法需要事先知道进程所需的CPU时间，预测一个进程的CPU时间并非易事

  • 优缺点

    • 优化了响应时间(+)
    • 难以预测作业CPU时间(-)
    • 不公平算法(-)

优先级调度(PRIORITY)

  • 优先级通常为固定区间的数字，如[0, 10]：

    • 数字大小与优先级高低的关系在不同系统中实现不一样，以 Linux为例，0为最高优先级。
    • 调度策略：下一次调度总是选择优先级最高的进程。
    • SJF是优先级调度的一个特例。
    • 优先级调度可以是抢占式，也可以是非抢占式。

  • 优先级的定义

    • 静态优先级
      • 优先级保持不变，但会出现不公平(饥饿)现象
    • 动态优先级（退化Aging）
      • 根据进程占用CPU时间：当进程占有CPU时间愈长，则慢慢降低它的优先级
      • 根据进程等待CPU时间：当进程在就绪队列中等待时间愈长，则慢慢提升它的优先级

  • 优先级调度(PRIORITY)

    • 优先级通常为固定区间的数字，如[0, 10]：
      • 数字大小与优先级高低的关系在不同系统中实现不一样，以 Linux为例，0为最高优先级。
      • 调度策略：下一次调度总是选择优先级最高的进程。
      • SJF是优先级调度的一个特例。
      • 优先级调度可以是抢占式，也可以是非抢占式。
    • 优先级的定义
      • 静态优先级
        • 优先级保持不变，但会出现不公平(饥饿)现象
      • 动态优先级（退化Aging）
        • 根据进程占用CPU时间：当进程占有CPU时间愈长，则慢慢降低它的优先级
        • 根据进程等待CPU时间：当进程在就绪队列中等待时间愈长，则慢慢提升它的优先级

    在linux中每个线程中存在一个控制该线程属性的结构体，struct pthread_attr_t，也就是pthread_create函数的第二个参数的所指值，线程属性在使用时要使用pthread_attr_init初始化，使用完之后pthread_attr_destory销毁

1
2
3
4
5
6
7
8
int pthread_attr_init(pthread_attr_t *attr);
int pthread_attr_destroy(pthread_attr_t *attr);   
/*pthread_attr_init之后，pthread_t结构所包含的内容就是操作系统实现
支持的线程所有属性的默认值。
如果pthread_attr_init实现时为属性对象分配了动态内存空间，
pthread_attr_destroy还会用无效的值初始化属性对象，因此如果经
pthread_attr_destroy去除初始化之后的pthread_attr_t结构被
pthread_create函数调用，将会导致其返回错误。*/

线程属性其结构体为：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct
{
       int                           detachstate;    线程的分离状态
       int                           schedpolicy;   *线程调度策略 
       struct sched_param      schedparam;           线程的调度参数
       int                          inheritsched;    线程的继承性
       int                          scope;          *线程的作用域
       size_t                       guardsize;       线程栈末尾的警戒缓冲区大小
       int                          stackaddr_set;   
       void *                     stackaddr;         线程栈的位置
       size_t                      stacksize;        线程栈的大小
}pthread_attr_t;

分离状态：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
我们已经在前面已经知道，在默认情况下线程是非分离状态的，这种情况   
下，原有的线程等待创建的线程结束。只有当pthread_join() 函数返回       
时，创建的线程才算终止，才能释放自己占用的系统资源。   

分离线程没有被其他的线程所等待，自己运行结束了，线程也就终止了，
马上释放系统资源。

通俗的说也就是：我们知道一般我们要等待(pthread_join)一个线程的结束，
主要是想知道它的结束状态，否则等待一般是没有什么意义的！但是if有一
些线程的终止态我们压根就不想知道，那么就可以使用“分离”属性，那么我
们就无须等待管理，只要线程自己结束了，自己释放src就可以咯！这样更
方便！

#include <pthread.h>
int pthread_attr_getdetachstate(const pthread_attr_t * attr, int * detachstate);
int pthread_attr_setdetachstate(pthread_attr_t * attr, int detachstate);
参数：attr:线程属性变量
        detachstate:分离状态属性   
若成功返回0，若失败返回-1。

设置的时候可以有两种选择：
<1>.detachstate参数为：PTHREAD_CREATE_DETACHED     分离状态启动
<2>.detachstate参数为：PTHREAD_CREATE_JOINABLE    正常启动线程

线程的作用域：

1
2
3
4
5
6
7
8
9
10
11
12
13
函数pthread_attr_setscope和pthread_attr_getscope分别
用来设置和得到线程的作用域。       
#include <pthread.h>   
int    pthread_attr_getscope( const pthread_attr_t * attr, int * scope );
int pthread_attr_setscope( pthread_attr_t*, int scope );
参数：
        attr               线程属性变量
        scope         线程的作用域       
若成功返回0，若失败返回-1。

作用域控制线程是否在进程内或在系统级上竞争资源，可能的值是
PTHREAD_SCOPE_PROCESS  （进程内竞争资源）
PTHREAD_SCOPE_SYSTEM   （系统级竞争资源）linux中默认，这是由linux的线程模型为1：1模型决定的·

调度策略及优先级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
        函数pthread_attr_setschedpolicy和pthread_attr_getschedpolicy分别用
        来设置和得到线程的调度策略。

        int pthread_attr_getschedpolicy(const pthread_attr_t *, int * policy)
        int pthread_attr_setschedpolicy(pthread_attr_*, int policy)
        参数：
                attr            线程属性变量
                policy        调度策略   
        若成功返回0，若失败返回-1。

        所谓调度策略也就是我们之前在OS中所学过的那些调度算法：
        SCHED_FIFO    ：先进先出
        SCHED_RR       ：轮转法
        SCHED_OTHER    ：其他方法

        SCHED_OTHER是不支持优先级使用的,而SCHED_FIFO和SCHED_RR
        支持优先级的使用,他们分别为1和99,数值越大优先级越高.

        注意：
                > 此处的SCHED_FIFO是允许被高优先级抢占的！
                > 也就是有高优先级的必须先运行
                > SCHED_RR是设置一个时间片
                > 当有SCHED_FIFO或SCHED_RR策赂的线程在一个条件变量
                上等持或等持加锁同一个互斥量时，它们将以优先级顺序被唤
                醒。即，如果一个低优先级的SCHED_FIFO线程和一个高优先
                织的SCHED_FIFO线程都在等待锁相同的互斥且，则当互斥量
                被解锁时，高优先级线程将总是被首先解除阻塞。

<2>.调度参数：

        函数pthread_attr_getschedparam 和pthread_attr_setschedparam分别
        用来设置和得到线程的调度参数。

        int pthread_attr_getschedparam(const pthread_attr_t *,struct
        sched_param *);
        int pthread_attr_setschedparam(pthread_attr_t *,const struct
        sched_param *);
        参数：
                attr            线程变量属性
                param        sched_parm 结构体
        若成功返回0，若失败返回-1。

        /usr/include /bits/sched.h
        struct sched_param
        {
               int sched_priority;    //!> 参数的本质就是优先级
        };
        注意：大的权值对应高的优先级!
        系统支持的最大和最小的优先级值可以用函数：
        sched_get_priority_max和sched_get_priority_min得到！

        #include <pthread.h>
        int sched_get_priority_max( int policy );
        int sched_get_priority_min( int policy );
        参数：max_：    系统支持的优先级的最小值
                min_ ：    系统支持的优先级的最大值

        使用：max_ = sched_get_priority_max( policy );
                min_ = sched_get_priority_min( policy );
                注意参数是policy调用策略，也就是说对于不同的策略的值是不
                一样的！


        policy = SCHED_OTHER
        max_priority = 0
        min_priority = 0

        Show SCHED_FIFO of priority
        max_priority = 99
        min_priority = 1

        Show SCHED_RR of priority
        max_priority = 99
        min_priority = 1

调度策略可以分为两种

  • normal scheduling：对应的调度策略schedpolicy的取值为SCHED_OTHER SCHED_IDLE SCHED_TATCH，此状态下对应的优先级schedparam均为0

  • real scheduling：对应的调度策略schedpolicy取值为SCHED_FIFO SCHED_RR，此状态下对应的优先级schedparam位于 1 - 99之间，数值越低意味着优先级越低

    我们自己创建进程的调度策略大多均为SCHED_OTHER模式，这种也遵循时间片轮转的策略，但要注意它位于normal，一旦由real sheduling的进程normal sheduling要让出CPU

    在linux终端中查看进程的优先级

    方法一：

top命令，注意观察 PR 和 NI(nice)友好值

PR值越小所代表的优先级越高(与线程属性中的优先级相反)，NI的取值范围(-20，19)，当取值为 0 意味着这是一个普通线程，PR = 20 + NI(PR值在normal进程中范围为(0 , 39)，NI值仅对normal有效)，当PR值为负数或者rt)时，意味着该线程为实时线程。对于real scheduling 线程 PR = -1 - priority_value(优先级)

方法二：

chrt命令 -p + pid

1
2
3
#:/mnt/c/Users/satellite$sudo chrt -p 7
pid 7's current scheduling policy: SCHED_OTHER
pid 7's current scheduling priority: 0     //优先级

chrt命令也可以用来设置调度策略

参考：https://www.bilibili.com/video/BV1bf4y147PZ
https://www.jianshu.com/p/7bf93be5a1b0