【原理剖析】9-处理机调度与死锁.md

概述：

  • 处理机的三级调度
  • 作业调度及进程调度的概念
  • 调度算法的评价准则
  • 几种常用的作业调度、进程调度算法
  • 死锁的概念及产生原因
  • 死锁的预防办法
  • 死锁的检测与恢复方法

0x01 分级调度

操作系统的一个非常重要的功能就是管理计算机资源，提高系统的效率。对处理机的管理是操作系统的基本功能之一。在早起的计算机系统中，对 CPU 的管理非常简单，与其他系统资源一样在整个操作系统运行过程中被单独一个作业所独占，不存在处理机分配和调度问题。随着多道程序设计技术和各种类型的操作系统的出现，各种不同的 CPU 管理方式开始使用，为用户提供不同性能的操作系统。

典型的批处理作业，从进入系统并驻留在外部存储的后备队列上开始，直到作业运行完毕，基本都需要经过这样的三级调度：作业调度、对换以及进程调度。

0x02 调度的层次

  1. 作业调度

作业调度又称为高级调度或长调度，用于选择把外部存储中处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源。如何，将新创建的进程排在进程就绪队列中，准备执行。在批处理系统中，作业进入系统后，是先驻留在外部存储上的，因此需要有作业调度的过程，以便将它们分批地装入内存。在分时系统中，为了做到及时响应，用户通过键盘输入的命令或数据等，都是被直接送入内存的，因而无须再配置作业调度机制。同样地，在实时操作系统中，通常也不需要作业调度。

一个作业从提交给计算机系统到执行结束、退出系统，一般要经历提交、后备、执行和完成四种状态，如下：

  • 提交状态：一个作业从输入设备进入外部存储设备的过程称为提交状态，处于提交状态的作业，因信息尚未全部进入系统，所以不能被调度程序选中；
  • 后备状态（收容状态）：输入管理系统不断将作业输入到外部存储对应部分，若一个作业的全部信息都输入到了输入井中，则在它还未被调度执行前，该作业处于后备状态；
  • 执行状态：作业调度程序从后备作业中选取若干个作业到内存投入运行，为被选中作业建立进程并分配必要的资源，这时，这些被选中的作业处于执行状态。从宏观上看，这些作业证处于在执行过程中，从微观上看，在某一时刻，由于处理机总数少于并发执行的进程数，因此，不是所有被选中作业都占有处理机，其中的大部分处于等待资源或就绪状态。哪个作业的那个进程被分配给处理机，这就是进程调度需要完成的任务；
  • 完成状态：当作业运行完毕，当它所占用的资源尚未全部被系统收回时，该作业处于完成状态。在这种状态下，系统需要做部分善后处理工作。
  1. 对换

对换又称交换调度或中级调度，其主要任务是按照给定的原则和策略，将处于外部存储交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外部存储交换区。交换调度主要涉及内存管理与扩充。（这部分将在后面的内存管理中详细讲到）

  1. 进程调度

进程调度又称为低级调度或微观调度，其主要任务是按照某种策略和算法，将处理机分配给一个处于就绪状态的进程。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。进程调度可以分为以下两种方式：

  • 非抢占方式。非抢占方式不允许进程抢占已经分配出去的处理机。采用非抢占调度方式时，可能引起进程调度的原因有正在执行的进程执行完成、因发生某事件而不能机修执行、执行中的进程因提出 I/O 请求而暂停执行、在进程通信或同步过程中执行了某种原语操作等等。非抢占调度方式的优点是实现简单、系统开销小，适用于大部分的批处理系统环境，但是很难满足紧急任务的要求。
  • 抢占方式。抢占调度方式允许调度程序根据某种原则暂停正在执行的进程，将处理机收回，重新分配给另一个进程。抢占的原则有优先级原则、短作业优先原则、时间片原则等。

作业调度和进程调度关系如下图所示：

0x03 调度算法

在操作系统中，调度的实质是一种资源分配，因而调度算法是根据系统的资源分配策略，规定资源分配的算法。现有的各种调度算法中，有的适用于作业调度，有的则适用于进程调度，也有一些两者都适用的算法。

对于不同的系统和调度目标，应采用不同的调度算法。例如，在批处理系统中，考虑作业的平均周转时间，应采用短作业优先的调度算法；在分时系统中，为了保证系统具有合理的响应时间，应采用轮转法进行调度。下面就简单了解一下目前主流的几种调度算法。

0x04 单道批处理系统的调度算法

单道批处理系统中，作业调度的主要任务是解决作业之间的自动接续问题，减少操作员的干预，提高系统资源的利用率，所采用的调度算法比较简单，有如下几种：

  • 先来先服务调度算法：按照作业或进程到达的前后持续进行调度
  • 短作业（进程）优先调度算法：对短作业或短进程优先调度的算法

0x05 多道批处理系统的调度算法

在多道程序设计系统中，由于谋道作业的输入输出操作由通道代行控制，将 CPU 从繁多的 I/O 操作中解脱出来，因此 CPU 可再分配给另一道作业，从而形成了多道作业并发执行的结果，减少了 CPU 对 I/O 的等待时间。但是，由于作业不同，各作业执行时包含的 I/O 操作时间的比例不同。基于这些原因，大多数多道程序系统的调度策略采用：先来先服务、考虑优先级、分时和优先级相结合、综合考虑资源要求等。

  • 先来先服务调度：按照作业或进程进入就绪队列的前后顺序进行调度执行；
  • 基于优先级调度：每一道作业或者进程都设定了一定的优先级别，优先级别可以由用户定义，也可以由系统设定或计算确定。调度时挑选优先级高者，优先级相同时，按进程进入就绪态队列或作业进入后备态队列的先后顺序；
  • 分时和优先级相结合调度：适用于分时操作系统中或者通用操作系统；
  • 综合考虑资源要求调度：综合考虑每一道作业或进程对资源的要求进行调度分配；

0x06 Linux 系统的调度算法

前面讲了基本上所有的调度算法及其优缺点，那么在 Linux 操作系统下是什么样的情况呢。Linux 系统作业调度非常简单，或者说没有作业调度，作业一旦提交就直接进入内存，建立对应的进程，继而进入下一级的调度。交换调度主要涉及系统存储管理的内容（这部分在后面的内存管理中讲述）。

Linux 操作系统中的内核级线程和进程在表示、管理调度方面没有差别，系统也没用专门的线程调度，采用进程调度统一处理进程和内核线程。

Linux 系统的进程调度策略

Linux 系统的调度程序就是内核中的 schedule() 函数，主要任务就是在就绪队列 run_queue 中选出一个进程并投入运行。schedule() 函数需要确定以下部分参数：

  • 进程调试算法 policy
  • 进程过程剩余时间片 counter
  • 进程静态优先级 priority
  • 实时进程优先级 rt_priority
  • 用户可控制 nice 因子

上面参数被存放在进程控制块中相应的调度成员中，Linux 系统提供了三种进程调度算法，这三种算法可以由用户通过宏定义选择，具体可用调度策略如下：

调度策略标志 所代表的调度策略
#define SCHED_OTHER 普通的分时进程
#define SCHED_FIFO 先进先出的实时进程
#define SCHED_RR 基于优先级的轮转算法
#define SCHED_YIELD 不是调度策略，表示进程让出 CPU

Linux 内核将进程分为实时进程和非实时进程（普通进程）两种，实时进程获得 CPU 比普通进程优先，用户可以通过系统调用 sched_setschedule() 函数改变自己的调度策略，通过系统调用 sys_setpriority() 和 sys_nice() 改变其静态优先级。

0x07 死锁问题

计算机系统中有很多资源属于单独的资源，但是在很多进程中都要共享这类资源，这样，若干进程就会相互竞争有限的资源，因获取不到资源而陷入阻塞状态。

系统发送死锁现象不仅浪费大量的系统资源，甚至导致整个系统奔溃，带来严重的后果。所以，对死锁问题再理论上和技术上都必须给予高度重视，采取一些有效的措施来预防、避免死锁的发生。

0x08 死锁的概念

死锁是进程死锁的简称，是由 Dijkstra 于 1965 年研究银行家算法时提出的，也是计算机操作系统乃至并发程序设计中非常重要但又最难处理的问题之一。掌握操作系统中对于死锁的处理方法，对计算机中处理并发程序的竞争问题有很大的帮助。

如下图所示，P1 进程占据资源 R1，P2 进程占据资源 R2，当 P1 进程期望得到资源 R2，而 P2 进程也期望访问资源 R1 时彼此都不能继续执行从而陷入死锁。

简单来说，死锁就是指多个进程在循环等待其他进程占有的资源，因为始终等待不到其他进程释放资源从而进入无限期等待状态；也可以说死锁是进程之间无限期互相等待的事件。

其实，在前面的部分操作实验中，我们已经解决过死锁问题。比如之前的生产者和消费者问题中，要控制两个个进程之间执行的顺序就是为了避免死锁的发生。

0x09 死锁产生的原因及必要条件

从前面的介绍中可以将系统产生死锁的根本原因归结为以下几点：

  • 个进程竞争优先的资源
  • 进程推进顺序不当

而死锁产生的必然条件，换句话说，当系统如果可能发生死锁则一定存在如下情况或者条件：

  • 互斥条件：对于一个排他性资源，同一时刻只能由最多一个进程占有；
  • 占有且申请条件：进程至少占有一个资源，但是又申请新的资源，等待新资源的时候仍然没有释放已占用资源；
  • 不可抢占条件：进程所获得的资源在未使用完毕前不能强行被其他进程夺取；
  • 环路条件：存在一个进程等待序列

0x0a 解决死锁的基本方法

为了保证系统的正常运行，应事先采取措施，预防或避免死锁的发生。在系统已出现死锁后，要及时检测到死锁并解除死锁。目前用于处理死锁问题的方法如下：

  • 死锁的预防：采取某种策略，限制并发进程对资源的请求，从而保证死锁的必要条件在系统执行的任何时间都得不到满足；
  • 死锁的避免：在分配资源时，根据资源的使用情况提前做出预测，给定一个合适、安全的进程推进顺序，从而避免死锁的发生；
  • 死锁的检测：允许系统发生死锁。系统设置专用结构应对死锁的发生。当死锁发生时，能够检测到死锁并找出对应的进程和资源；
  • 死锁的解除：与死锁检测配套措施，用于将进程从死锁状态解救出来。

0x0b 产生死锁实例

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <pthread.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/time.h>
#include <string.h>
#define MAX 10

pthread_t thread[2];  //两个线程

/* 定义两个锁，给两个线程分别使用 */
pthread_mutex_t mutex_0;
pthread_mutex_t mutex_1;

int number=0;
int i;


void *thread1()
{
    /* 首先将自己的线程锁 1 上锁，然后访问共享数据 number ，对其进行 + 1 操作，接着不释放线程锁1 而是尝试去获取 线程锁 2 */
    printf ("thread[1] : I'm thread 1\n");

    pthread_mutex_lock(&mutex_0);
    printf("thread[1]: mutex_0 already lock!\n");
    number++;
    printf("thread[1]: number++-->[%d]\n", number);
    printf("thread[1]: I will deadlock....\n");
    pthread_mutex_lock(&mutex_1);

    /* 会在上一步死锁，线程死等在此处 */
    printf("thread1 :主函数在等我完成任务吗？\n");
    pthread_exit(NULL);
}

void *thread2()
{
    /* 首先将自己的线程锁 2 上锁，确保线程1 在获取线程锁 2 时无限等待（死锁），然后尝试去获取线程锁 1（也被线程 1 上锁，所以还是会无限等待。*/
    printf ("thread[2] : I'm thread 2\n");

    /* 确保线程1 先将锁 1 上锁 */
    sleep(1);

    pthread_mutex_lock(&mutex_1);
    printf("thread[2]: mutex_1 already lock!\n");
    number++;
    printf("thread[2]: number++-->[%d]\n", number);
    printf("thread[2]: I will deadlock....\n");
    pthread_mutex_lock(&mutex_1);

    /* 会在上一步死锁，线程死等在此处 */

    printf("thread2 :主函数在等我完成任务吗？\n");
    pthread_exit(NULL);
}

void thread_create(void)   //创建两个线程
{
    int temp;
    memset(&thread, 0, sizeof(thread));          //comment1
    /*创建线程*/
    if((temp = pthread_create(&thread[0], NULL, thread1, NULL)) != 0)  //comment2
    {
        printf("pthread 1 创建失败!\n");
    }
    else
    {
        printf("pthread 1 被创建\n");
    }

    if((temp = pthread_create(&thread[1], NULL, thread2, NULL)) != 0)  //comment3
    {
        printf("pthread 2 创建失败\n");
    }
    else
    {
        printf("pthread 2 被创建\n");
    }

}

void thread_wait(void)
{
    /*等待线程结束*/
    if(thread[0] !=0)
    {
        pthread_join(thread[0],NULL);
        printf("pthread 1 已经结束\n");
    }
    if(thread[1] !=0)
    {
        //comment5
        pthread_join(thread[1],NULL);
        printf("pthread 2 已经结束\n");
    }
}

int main()
{
        /*用默认属性初始化互斥锁*/
        pthread_mutex_init(&mutex_0,NULL);
        pthread_mutex_init(&mutex_1,NULL);

        printf("我是主函数哦，我正在创建线程\n");
        thread_create();
        printf("我是主函数哦，我正在等待线程完成任务\n");
        thread_wait();

        return 0;
}
A_OS > Linux > Linux操作系统原理剖析
#Linux #内核
【原理剖析】9-处理机调度与死锁.md
https://hodlyounger.github.io/2023/12/27/A_OS/Linux/Linux操作系统原理剖析/【原理剖析】9-处理机调度与死锁/
作者
mingming
发布于
2023年12月27日
许可协议