处理机调度和死锁

发表于 | 分类于

概念

在多道程序环境下，进程数目往往多于处理机数目，致使它们竞争使用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。一个作业从提交开始，往往要经历三级调度：高级调度、中级调度、低级调度。

  1. 高级调度：调度对象是作业。
  2. 中级调度：提高内存利用率和系统吞吐量。
  3. 低级调度：它所调度的对象是进程。进程调度是最基本的一种调度。进程调度方式有两种调度方式：非抢占方式和抢占方式（基于优先权，短作业优先，时间片原则）。

作业调度和进程调度的区别

作业调度为进程活动做准备，进程调度使进程活动起来

作业调度次数少，进程调度次数多

有的系统不设作业调度，但进程调度必不可少

进程调度算法

FCFS先来先服务

该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。FCFS 算法比较有利于长作业(进程)，而不利于短作业(进程)。

短作业优先

短作业优先调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

高优先权优先调度算法（动态优先权）

动态优先级调度算法是指在创建进程之初，先赋予其一个优先级，然后其值随着进程的推进或等待时间的增加而改变，以便获得更好的调度性能。例如，可以规定在就绪队列中的进程随其等待的时间的正常，使其优先级相应提高。若所有的进程都具有相同的优先级初值，则最先进入就绪队列的进程会因为其优先级变得最高，而优先获得处理机，这相当于FCFS算法。若所有的就绪进程具有各不相同的优先级初值，那么对于优先级初值低的进程，在等待了足够的时间后，也可以获得处理机。

基于时间片的轮转调度算法

在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片的轮转式进程调度算法。每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。

死锁

产生死锁原因

竞争资源（多个进程竞争共享的资源），进程间推进顺序非法（进程请求和释放的资源顺序不当）

产生死锁的条件

互斥条件，请求和保持条件，不剥夺条件，环路等待条件。

处理死锁的几种条件

预防死锁，避免死锁，检测死锁，解除死锁。

银行家算法

它是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。

安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。（即在分配过程中，不会出现某一进程后续需要的资源量比其他所有进程及当前剩余资源量总和还大的情况）
注：存在安全序列则系统是安全的，如果不存在则系统不安全，但不安全状态不一定引起死锁。

原理过程：系统给当前进程分配资源时，先检查是否安全：在满足当前的进程X资源申请后，是否还能有足够的资源去满足下一个距最大资源需求最近的进程（如某进程最大需要5个单位资源，已拥有1个，还尚需4个），若可以满足，则继续检查下一个距最大资源需求最近的进程，若均能满足所有进程，则表示为安全，可以允许给当前进程X分配其所需的资源申请，否则让该进程X进入等待。
（注：检查过程中，每拟满足一个进程，则进行下个检查时，当前可用资源为回收上一个进程资源的总值，每满足一个进程表示此进程已结束，资源可回收。）

代码实现：

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <iostream>
#include <string.h>
#include <string>
using namespace std;
const int maxnsource = 100;
const int maxnprocess = 50;

int available[maxnsource];//可以使用的资源。
int max[maxnprocess][maxnprocess];//最大需求矩阵。
int allocation[maxnprocess][maxnprocess];//已经分配的矩阵。
int need[maxnprocess][maxnprocess];//还需要的矩阵。
int requestsource[maxnprocess][maxnprocess];//进程请求的矩阵。
int finish[maxnprocess];//进程是否能得到足够的资源使其结束。
int n, m;
int i, j;
int p[maxnsource];//记录进程号

int safe()//判断是否为安全的
{
    int cnt = 0;
    int flag = 0;
    int temp[maxnsource];
    for (i = 0; i < n; i++)
        temp[i] = available[i];
    for (i = 0; i < m; i++)
    {
        if (finish[i] == 0)
        {
            for (j = 0; j < n; j++)
            {
                if (need[i][j] > temp[j])
                    break;
            }
            if (j == n)
            {
                finish[i] = 1;
                for (int k = 0; k < n; k++)
                    temp[k] += allocation[i][k];
                p[cnt++] = i;
                i = -1;//这里不是0,重置之后i++会变为1，就错了。
            }
            else
                continue;
            if (cnt == m)
            {
                cout << "系统是安全的" << endl;
                cout << "安全序列:" << endl;
                for (i = 0; i<cnt; i++)  
                {
                    cout << p[i];
                    if (i != cnt - 1)
                    {
                        cout << "-->";
                    }
                }
                cout << "" << endl;
                return 1;
            }
        }
    }
    cout << "系统是不安全的" << endl;
    return 0;
}


void bank()//银行家算法
{
    int cur;
    while (1)
    {
        cout << "输入要申请资源的进程号" << endl;
        cin >> cur;
        cout<< "输入进程所请求的各资源的数量" << endl;
        for (int i = 0; i < n; i++)
            cin >> requestsource[cur][i];
        for (int i = 0; i < n; i++)
        {
            if (requestsource[cur][i] > need[cur][i])
            {
                cout << "输入的请求数超过进程的需求量!请重新输入!" << endl;
                continue;
            }
            if (requestsource[cur][i] > available[i])
            {
                cout << "输入的请求数超过系统有的资源数!请重新输入!" << endl;
                continue;
            }
        }
        for (int i = 0; i < n; i++)
        {
            available[i] -= requestsource[cur][i];
            allocation[cur][i] += requestsource[cur][i];
            need[cur][i] -= requestsource[cur][i];
        }
        for (int i = 0; i < m; i++)
            finish[i] = 0;
        if (safe())
        {
            cout << "同意分配请求!" << endl;
        }
        else
        {
            cout << "您的请求被拒绝!" << endl;
            for (int i = 0; i < n; i++)
            {
                available[i] += requestsource[cur][i];
                allocation[cur][i] -= requestsource[cur][i];
                need[cur][i] += requestsource[cur][i];
            }
            for (int i = 0; i < m; i++)
                finish[i] = 0;
            string s;
            cout << "是否还想再次请求分配吗?如果想，请输入YES" << endl;
            cin >> s;
            if (s == "YES")
                continue;
            else
                break;
        }
    }
}


int main()
{
    memset(finish, 0, sizeof(finish));
    cout << "输入进程的数量:";
    cin >> m;
    cout << "输入资源的种类:";
    cin >> n;
    cout << "输入每个进程最多所需要的资源数：";
    for (i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> max[i][j];
    cout << "输入每个进程已经分配的资源数：";
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            cin >> allocation[i][j];
            need[i][j] = max[i][j] - allocation[i][j];
            if (need[i][j] < 0)
            {
                cout << "输入的第" << i + 1 << "个进程所拥有的第" << j + 1 << "个资源数 错误,请重新输入:" << endl;
                j--;
                continue;
            }
        }
    }
    cout << "输入各资源现有的资源数：";
    for (i = 0; i < n; i++)
        cin >> available[i];
    /*for (i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            cout << max[i][j] << " ";
        cout << endl;
    }
    for (i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            cout << allocation[i][j] << " ";
        cout << endl;
    }
    for (i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            cout << need[i][j] << " ";
        cout << endl;
    }*/
    safe();
    bank();
    return 0;
}

Java死锁的实例

多个线程同时被阻塞，它们中的一个或者全部都在等待某个资源被释放。由于线程被无限期地阻塞，因此程序不可能正常终止。

在 Java 里面不恰当的使用锁且出现同时要锁多个对象时，会出现死锁情况：

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
import java.util.Date;
 
public class LockTest {
   public static String obj1 = "obj1";
   public static String obj2 = "obj2";
   public static void main(String[] args) {
      LockA la = new LockA();
      new Thread(la).start();
      LockB lb = new LockB();
      new Thread(lb).start();
   }
}
class LockA implements Runnable{
   public void run() {
      try {
         System.out.println(new Date().toString() + " LockA 开始执行");
         while(true){
            synchronized (LockTest.obj1) {
               System.out.println(new Date().toString() + " LockA 锁住 obj1");
               Thread.sleep(3000); // 此处等待是给B能锁住机会
               synchronized (LockTest.obj2) {
                  System.out.println(new Date().toString() + " LockA 锁住 obj2");
                  Thread.sleep(60 * 1000); // 为测试，占用了就不放
               }
            }
         }
      } catch (Exception e) {
         e.printStackTrace();
      }
   }
}
class LockB implements Runnable{
   public void run() {
      try {
         System.out.println(new Date().toString() + " LockB 开始执行");
         while(true){
            synchronized (LockTest.obj2) {
               System.out.println(new Date().toString() + " LockB 锁住 obj2");
               Thread.sleep(3000); // 此处等待是给A能锁住机会
               synchronized (LockTest.obj1) {
                  System.out.println(new Date().toString() + " LockB 锁住 obj1");
                  Thread.sleep(60 * 1000); // 为测试，占用了就不放
               }
            }
         }
      } catch (Exception e) {
         e.printStackTrace();
      }
   }
}

以上代码运行输出结果为：

1
2
3
4
Tue May 05 10:51:06 CST 2015 LockB 开始执行
Tue May 05 10:51:06 CST 2015 LockA 开始执行
Tue May 05 10:51:06 CST 2015 LockB 锁住 obj2
Tue May 05 10:51:06 CST 2015 LockA 锁住 obj1

此时死锁产生。

为了解决这个问题，我们不使用显示的去锁，我们用信号量去控制。

信号量可以控制资源能被多少线程访问，这里我们指定只能被一个线程访问，就做到了类似锁住。而信号量可以指定去获取的超时时间，我们可以根据这个超时时间，去做一个额外处理。

对于无法成功获取的情况，一般就是重复尝试，或指定尝试的次数，也可以马上退出。

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
import java.util.Date;
import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;
 
public class UnLockTest {
   public static String obj1 = "obj1";
   public static final Semaphore a1 = new Semaphore(1);
   public static String obj2 = "obj2";
   public static final Semaphore a2 = new Semaphore(1);
 
   public static void main(String[] args) {
      LockAa la = new LockAa();
      new Thread(la).start();
      LockBb lb = new LockBb();
      new Thread(lb).start();
   }
}
class LockAa implements Runnable {
   public void run() {
      try {
         System.out.println(new Date().toString() + " LockA 开始执行");
         while (true) {
            if (UnLockTest.a1.tryAcquire(1, TimeUnit.SECONDS)) {
               System.out.println(new Date().toString() + " LockA 锁住 obj1");
               if (UnLockTest.a2.tryAcquire(1, TimeUnit.SECONDS)) {
                  System.out.println(new Date().toString() + " LockA 锁住 obj2");
                  Thread.sleep(60 * 1000); // do something
               }else{
                  System.out.println(new Date().toString() + "LockA 锁 obj2 失败");
               }
            }else{
               System.out.println(new Date().toString() + "LockA 锁 obj1 失败");
            }
            UnLockTest.a1.release(); // 释放
            UnLockTest.a2.release();
            Thread.sleep(1000); // 马上进行尝试，现实情况下do something是不确定的
         }
      } catch (Exception e) {
         e.printStackTrace();
      }
   }
}
class LockBb implements Runnable {
   public void run() {
      try {
         System.out.println(new Date().toString() + " LockB 开始执行");
         while (true) {
            if (UnLockTest.a2.tryAcquire(1, TimeUnit.SECONDS)) {
               System.out.println(new Date().toString() + " LockB 锁住 obj2");
               if (UnLockTest.a1.tryAcquire(1, TimeUnit.SECONDS)) {
                  System.out.println(new Date().toString() + " LockB 锁住 obj1");
                  Thread.sleep(60 * 1000); // do something
               }else{
                  System.out.println(new Date().toString() + "LockB 锁 obj1 失败");
               }
            }else{
               System.out.println(new Date().toString() + "LockB 锁 obj2 失败");
            }
            UnLockTest.a1.release(); // 释放
            UnLockTest.a2.release();
            Thread.sleep(10 * 1000); // 这里只是为了演示，所以tryAcquire只用1秒，而且B要给A让出能执行的时间，否则两个永远是死锁
         }
      } catch (Exception e) {
         e.printStackTrace();
      }
   }
}