进程管理

进程基础

概念

进程(Process)是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

组成

进程控制块PCB(Process Control Block )是进程存在的唯一标志，当进程被创建时，操作系统会为其创建一个PCB,当进程结束时，会回收PCB

PCB包括了进程描述信息，进程控制和管理信息，资源分配清单，处理机相关信息

进程标识符PID(Process ID)是计算机系统用来标识进程的标识符

操作系统对进程进行管理工作所需的信息都存在PCB中

而进程由PCB，程序段，数据段组成，PCB是由操作系统使用，程序段和数据段是给进程自己使用

程序段：指程序在运行过程中需要的指令

数据段：包含运行过程中产生的各种数据

特征

• 动态性 进程是程序的一次执行过程，是动态的产生，变化和消亡
• 并发性 内存中有多个进程实体，各进程可并发执行
• 独立性 进程是能独立运行，独立获得资源，独立接受调度的基本单位
• 异步性 各进程按各自独立的，不可预知的速度向前推进，操作系统要提供进程同步机制
• 结构性 各个进程都会有一个PCB

进程的状态

创建态：进程正在被创建，状态是创建态，这个阶段操作系统会为进程分配资源，初始化PCB

就绪态：当进程创建完成后，就进入就绪态，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行

运行态：如果一个进程此时就在CPU上运行，那么这个进程就处于“运行态”，CPU会执行该进程对应的程序

阻塞态：在进程运行的过程中，可能会请求等待某个事件的发生，在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入阻塞态

终止态：执行exit系统调用，请求操作系统终止该进程，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB

运行态到阻塞态是一种进程自身作出的主动行为

阻塞态到就绪态不是进程自身能控制的，是一种被动行为

在PCB中，有状态字state来记录当前进程的状态

进程的组织

链式方式：通过指针来指向PCB，执行指针指向运行态的程序，就绪队列指针指向在就绪态的PCB

索引方式：通过索引表来记录进程的状态

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程，撤销已有进程，实现进程状态转换等功能

进程的控制通过原语来实现，原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断，可以用“关中断指令”和“开中断指令”这个两个特权指令来实现原子性

CPU执行了关中断指令后，就不会检查中断指令了

进程的创建

在OS中，允许一个进程去创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程叫做子进程

子进程可以继承父进程所拥有的资源，和父进程并发执行，子进程在被创建的时候会被分配虚拟地址空间

导致创建新线程的操作有

• 用户登录
• 作业调度
• 提供服务
• 应用请求

进程的终止

导致终止进程的操作有：

• 正常结束
• 异常结束，比如非法指令，越界错误等
• 外界干预，比如父进程终止

进程的阻塞和唤醒

导致进程阻塞的操作有：

• 向系统请求共享资源失败
• 等待某种操作的完成，比如等待I/O设备
• 新数据还没到达
• 等待新任务的到达

导致进程唤醒的操作即是满足了进程的要求

进程的切换

让两个进程的状态发生改变，让进程在就绪状态和运行状态中切换

就绪→运行：进程被调度

运行→就绪：时间片耗尽或被高优先级进程抢占

进程同步

概念

之前已经提到过操作系统具有异步性，各并发执行的进程以独立的，不可预知的速度向前推进

在管道通信中，读进程和写进程并发地运行，由于并发必然导致异步性，因此写数据和读数据两个操作的执行先后顺序是不确定的，而在实际应用中，又必须按照先写再读的顺序来执行

进程同步，就是要对多个相关进程在执行次序上进行协调，使并发执行的多个进程之间能按照一定的规则共享系统资源，并能很好地相互合作，从而使执行具有可再现性

临界资源：一个时间段只允许一个进程使用的资源称为临界资源，许多物理设备都是临界资源

对于临界资源的访问，必须要互斥的进行。互斥，又称间接制约关系，进程互斥指当一个进程访问临界资源的时候，另一个想要访问该临界资源的进程必须等待

对临界资源的互斥访问，可以在逻辑上划分为以下四个部分

进入区：负责检查是否可以进入临界区，如可进入，则应设置正在访问临界资源的标志（上锁），防止其他进程同时进入临界区

临界区：每个进程中访问临界资源的那段代码叫做临界区

退出区：负责解除正在访问临界资源的标志(解锁)

剩余区：做其他处理

为了实现对临界资源的互斥访问，同时保证系统性能，需要遵循以下原则：

• 空闲让进 当临界区空闲的时候，可以允许一个请求进入临界区的进程立即进入
• 忙则等待 当临界区中有进程时，其他试图进入临界区的进程必须等待
• 有限等待 对请求访问的进程，应保证能在有限的时间内进入临界区
• 让权等待 当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

进程互斥的软件实现方法

单标志法：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予

1
2
3
4
5
6
7
8
9
10
11
12
13

int turn=0;
// 进程0
while(turn!=0);
    critical section;
    turn=1;
    remained section;

// 进程1
while(turn!=1);
    critical section
    turn=0;
    remainder section

turn作为标志位，可以实现同一时刻最多只允许一个进程访问临界区

最大的问题在于，只能轮流访问，如果临界区空闲，但是并不允许其他进程访问，主要问题就是违反了空闲让进原则

双标志先检查法：设置一个布尔数组flag[]，数组中的各个元素用来标记各进程想要进入临界区的意愿

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool flag[2];
flag[0]=false;
flag[1]=false;
// 刚开始设计两个进程都不行进入临界区
//进程0
while(flag[1]==false);
flag[0]=true;
critical section;
flag[0]=false;
remainder section;

//进程1
while(flag[0]==false);
flag[1]=true;
critical section;
flag[1]=false;
remainder section;

双标志先检查法的主要问题是：进入区的检查和上锁两个处理不是一气呵成的，检查之，上锁前可能发生进程切换

双标志后检查法：如果把while和flag的位置交换，就是后检查法

虽然解决了忙则等待的问题，但是如果两个进程同时把flag改为1，就都无法进入临界区了，也是不行的

Peterson算法

结合双标志法和单标志法，结合轮转和表达意愿

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool flag[2];
int turn=0;
// 进程0
flag[0]=true;   // 我要进入
turn=1;        // 进程1先用
while(flag[1]==false&&turn==1);
cirtical section;
flag[0]=false;
remainder section;

//进程1
flag[1]=true;
turn=0;
while(flag[0]==false&&turn==0);
cirtical section;
flag[1]=false;
remainder section;

用软件的方法解决了进程互斥问题，遵循了空闲让进，忙着等待，有限等待三个原则，但是依然没有遵循让权等待的原则

进程互斥的硬件实现方法

1.利用开/关中断

在进入临界区之前关闭中断，中断关闭后即不允许当前进程被被中断，也必然不会发生进程切换，直到进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区

优点：简单，高效

缺点：滥用关中断权利可能会导致严重后果，关中断时间过长，会影响系统效率，不适用于多CPU系统

2.利用Test-and-Set指令实现互斥

借助TSL指令以实现互斥，TS指令用硬件实现，执行的过程不允许被中断

1
2
3
4
5
6
7
8
9
10
11
12
13

//布尔型共享lock表示当前临界区是否被加锁
//true表示已加锁，false表示未加锁
bool TestAndSet(bool *lock){
    bool old;
    old=*lock;
    *lock=true;
    return old;
}
//使用TEL执行实现互斥的算法逻辑
while(TestAndSet(&lock));// 上锁并检查
//临界区
lock=false;   // 解锁
//剩余区

相比软件实现方法，TSL指令把上锁和检查操作用硬件的方式变成了一气呵成的原子操作

优点：实现简单，无需像软件实现方法那样严格检查是否有逻辑漏洞

缺点：不满足让权等待

3.Swap指令

也叫Exchange指令，或者XCHG指令

Swap指令是用硬件实现的，执行过程不允许被中断，只能一气呵成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//Swap指令就是交换两个变量的值
Swap(bool *a,bool *b){
bool temp;
temp=*a;
*a=*b;
*b=temp;
}

//lock表示临界区是否被加锁
bool old=true;
while(old==true)
    Swap(&lock,&old);
//临界区代码段
lock=false;
//剩余区代码段

优缺点和TSL指令一致

信号量机制

回顾之前解决互斥的方法，都无法实现让权等待的问题，Dijkstra提出了一种方案，就也就是信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作

信号量：其实就是一个变量，可以用一个信号量来表示系统中某种资源的数量

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为自己写的函数，名字分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数

wait，signal原语常被简称为P,V操作

整型信号量：用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

1
2
3
4
5
6
7
8
9
10
11
12

int S=1;// 初始化整型信号量
void wait(int S){
while(S<=0);
S--;
}
void signal(int S){
S++;
}
//进程0
wait(S);
//临界区
signal(S)

和双标志先检查法类似，不过将检查和上锁通过原语操作一气呵成，所以避免了并发和异步的问题

缺点：依然不满足让权等待的原则

记录型信号量

即用记录型数据结构表示的信号量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 记录型信号量的定义
typedef struct{
 int value;         //剩余资源数
 struct process *L;  //等待队列
}semaphore

 //某进程需要使用资源时，通过wait原语申请
  void wait (semaphore S){
  S.value--;          // 在等待就将value值-1
  if(S.value<0){
      block(S.L)  //资源数不够就阻塞，并且挂到信号量S的等待队列中去
  }
}

//进程使用完资源后，通过signal原语释放
void signal (semaphore S){
    s.value++;
    if(S.value<=0){
        wakeup(S.L); 
// 释放资源后，若还有别的进程在等待，就使用wakeup原语唤醒一个进程，该进程从阻塞态变为就绪态
    }
}

遵循了让权等待的原则

使用信号量机制实现进程互斥，进程同步，前驱关系

进程互斥

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//设置互斥信号量mutex，初值为1
semaphore mutex=1;
P1(){
P(mutex);
....    
V(mutex):
...
}

P2(){
P(mutex);
....    
V{mutex);
}

对于不同临界资源设置不同的信号量

进程同步

要求让各并发进程按要求有序地推进

分析在什么地方实现同步关系，设置同步信号量S，初始为0

在前操作之后执行V(S),后操作之前执行P(S)

1
2
3
4
5
6
7
8
9
10
11
12
13

P1(){
 代码1；
 代码2；
 V(S);
 代码3;
}

P2(){
 P(S);
 代码4;
 代码5;
 代码6;
}

这样可以保证代码4一定在代码2之后执行

若先执行V(S),则S+1后S=1，此时P(S)可以执行，反之，P(S)在S=0时不能执行，要等V(S)执行后唤醒

前驱关系

有些进程必须等其他进程执行了之后才具备执行条件，所以要为每一对前驱关系各设置一个同步信号量

管程机制

虽然信号量机制是一种方便有效地进程同步机制，但是会产生大量的PV操作，不仅给系统的管理带来了麻烦，而且还会因为同步不当导致系统死锁，为了解决上述问题，所以使用了管程(Monitors)机制

管程的定义

• 系统中各种硬件资源和软件资源都可以用数据结构抽象地描述其资源特性，可以利用共享数据结构抽象地表示系统中的共享资源。

• 将对该共享数据结构实施的特定操作定义为一组过程。

• 对局部于管程的共享数据设置初始值的语句

管程的特征

• 局部于管程的数据只能被局部于管程的过程所访问

• 一个进程只能通过调用管程内的过程才能进入管程访问共享数据

• 每次仅允许一个进程在管程内执行某个内部过程

管程就是面向对象里面封装思想的体现，将复杂的PV操作写进管程里面，从而使主函数变得简洁

经典的进程同步问题

生产者与消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品在缓冲区，而消费者消费一个产品在缓冲区，生产者，消费者共享一个大小为n的缓冲区，缓冲区是临界资源

• 只有缓冲区没满，生产者才能把产品放进去
• 只有缓冲区不空，消费者才能从中取出产品
• 缓冲区必须互斥访问

所以需要有3个PV操作

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

semaphore mutex=1; //互斥信号量，实现对缓冲区的互斥访问 
semaphore empty=n; //同步信号量，表示空闲缓冲区的数量
sempahore full=0   //同步信号量，表示产品的数量
 
 // 可以具象化实现过程，产品等于菜，而空闲缓冲区等于座位，有多少座位就可以上多少道菜，座位和菜是绑定关系，对于生产来说，首先是占一个座位，然后在上面生产出一道菜，对于消费来说，首先是消费了一道菜，然后才会释放一个座位
producer(){
    while(1){
       produce;
       P(empty);  
       P(mutex);
       input;
       V(mutex);
       V(full);
    }
}

comsumer(){
    while(1){
        P(full);
        P(mutex);
        output;
        V(mutex);
        V(empty);
        use;
    }
}

注意：实现互斥的P操作一定要在实现同步的P操作之后

2.管程

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

monitor ProducerConsumer
    condition full,empty;
    int count=0;//产品数
    void insert(Item item){
        if(count==N)
        {
            P(empty);
        }
        count++;
        insert_item(item);
        if(count==1)
            V(full);
    }
Item remove(){
    if(count==0)
        P(full);
    count--;
    if(count==N-1)
        V(empty);
    return remove_item()
}
end monitor;


//生产者
produce(){
    while(1){
        item=生产;
        ProducerConsumer.insert(item);
    }
}

//消费者
produce(){
    while(1){
        item=ProdecuerConsumer.remove();
    }
}

哲学家进餐

该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

首先，有5个哲学家进程，哲学家与左右邻居对其中间筷子的访问是互斥关系，每个哲学家进程需要同时持有两个临界资源才开始吃饭，主要问题在于如何避免死锁

信号量设置，定义互斥信号量数组chopstick[5]={1,1,1,1,1}用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5

为了防止5个哲学家都持有一只筷子而发生死锁，需要对筷子的拿取设置一定的规则

比如最多允许4个哲学家同时进餐，或者仅当哲学家的左右筷子均可用时，才允许拿起筷子进餐

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

// 仅当哲学家的左右筷子均可用时，才允许拿起筷子进餐
semaphore chopstick[5]={1,1,1,1,1}
semaphore mutex=1;
Pi(){
while(1){
    P(mutex);
    P(chopstick[i]);
    P(chopstick[(i+1)%5]);
    V(mutex);
    吃饭...
    V(chopstick[i]);
    V(chopstick[(i+1)%5]);
    思考...
}
}
//最多允许4个哲学家进餐
semaphore chopstick[5]={1,1,1,1,1}
semaphore x=4;

while(1){
    p(x);
    P(chopstick[i]);
    P(chopstick[(i+1)%5]);
    就餐
    V(chopstick[i]);
    V(chopstick[(i+1)%5]);
    V(x);
}

读者-写者问题

一个数据文件或记录可被多个进程共享，我们把只要求读该文件的进程称为”Reader进程”，其他进程则称为”Writer 进程”。

允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱。

但不允许一个 Writer 进程和其他 Reader 进程或 Writer 进程同时访问共享对象。因为这种访问将会引起混乱。

所谓”读者-写者（Reader-Writer Problem）问题”是指保证一个 Writer 进程必须与其他进程互斥地访问共享对象的同步问题。读者-写者问题常被用来测试新同步原语。

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

semaphore rw=1; //实现对共享文件的互斥访问
int count =0;  //记录当前有几个读进程在访问文件
semaphore mutex=1 //保证对count变量的互斥访问
    
    
 writer(){
    while(1){
        P(rw);  //写之前加锁
        Write
        V(rw);  //写完了解锁
    }
}
reader(){
    while(1){
        P(mutex)  //各个读进程互斥访问count
        if(count==0)// 由第一个读进程负责
            P(rw);   //读之前加锁
        count++;
        V(mutex);
        Read
        P(mutex);
        count--;
        if(count==0) //由最后一个读进程负责
            V(rw);    //读完了解锁
        V(mutex);
    }
}

抽烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。 每个抽烟者不停地卷烟并抽掉，但是要卷起并抽掉一支烟，抽烟者需要三种材料：烟草、纸和胶水。 三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。 供应者无限地提供三种材料，供应者每次讲两种材料挡在桌子上，拥有剩下那种材料的卷烟者卷一根烟并抽掉它，并给供应者一个告诉完成信号，供应者就会放另外两种材料在桌上，这种过程一直重复

首先分析同步和互斥的关系，桌子可以抽象为容量为1的缓冲区

将桌子上的两种材料抽象为组合，当桌子上有组合1时，第一个抽烟者取走东西，有组合2时，第二个抽烟者取走东西，有组合3时，第三个抽烟者取走东西，然后都需要发出完成信号，让供应者将下一个组合放到桌上

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

semaphore offer1=0; // 组合1的数量
semaphore offer2=0; // 组合2的数量
semaphore offer3=0; // 组合3的数量 
semaphore finish=0; // 抽烟是否完成
int i=0;            // 用于实现三个抽烟者轮流抽烟
provider(){
    while(1){
        if(i==0){
            put mix1;
            V(offer1);
        }
        else if(i==1)
        {
            put mix2;
            V(offer2);
        }
        else if(i==2)
        {   
            put mix3;
            V(offer3);
        }
        i=(i+1)%3;
        P(finish);
    }
}

smoker1(){
    while(1){
        P(offer1);
        smoke;
        V(finish);
    }
}
smoker2(){
    while(1){
        P(offer2);
        smoke;
        V(finish);
    }
}
smoker3(){
    while(1){
        P(offer3);
        smoke;
        V(finish);
    }
}

进程通信

进程通信就是指进程之间的信息交换

进程是分配系统资源的单位，因此各进程拥有的内存地址空间相互独立

共享存储

在内存中创建一个共享空间，让两个进程都可以访问，并映射到进程的虚拟地址空间，两个进程对共享空间的访问必须是互斥的

共享存储的方式有基于数据结构的共享和基于存储区的共享

• 基于数据结构的共享：只能放特定结构的数组，这种共享方式速度慢，限制多，是一种低级通信方式

• 基于存储区的共享：在内存中画出一块共享存储区，数据的形式，存放的位置都由进程控制，这种方式速度更快，是一种高级通信方式

管道通信

管道是指用于连接读写进程的一个共享文件，其实就是在内存够中开辟一个大小固定的缓冲区

• 管道只能采用半双工通信，如果要双向同时通信，则要使用两个管道
• 各个进程要互斥的访问管道
• 数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走，当读进程被数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞
• 管道允许多个写进程，但读进程最多只能有一个

消息传递

进程间的数据交换以格式化的消息(message)为单位，进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换

一个格式化的消息包括一个消息头和消息尾两个部分

消息头包含：发送进程ID，接收进程ID，消息类型，消息长度等格式化的消息

消息传递的直接通信方式直接将消息挂到接收进程的PCB的消息缓冲队列上，需要指明接收进程的PID

间接通信方式是将消息先发到中间体

线程

概念

线程是一个基本的CPU执行单元，也是程序执行流的最小单位

• 引入线程后，不仅进程之间可以并发，进程内各线程之间也可以并发，从而进一步提高了系统的并发度

• 引入线程后，进程只作为除CPU之外的系统资源的分配单元

• 引入线程后，并发所带来的系统开销减小

属性

• 线程是处理机调度的单位

• 同一线程的不同线程共享进程的资源

• 切换进程内的线程，系统开销很小

实现方式

用户级线程：即由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责

在用户级线程中，线程切换可以在用户态下直接完成

在用户看来是有多个线程，但是在操作系统内核看来，并意识不到线程的存在，用户级线程就从用户视角能看到的线程

优点：在用户空间就可以完成，不需要切换到核心态，系统开销小，效率高

缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高，多个进程不可再多核处理机上并发运行

内核级线程：操作系统内核支持的线程

内核级线程的管理工作由操作系统内核完成

线程调度，切换等工作都由内核负责，因此内核级线程的切换也必须在核心态下才能完成

操作系统会为每个内核级线程建立相应的TCB(线程控制块)，通过TCB对线程进行管理。内核级线程就是从操作系统内核视角看能看到的线程

优点：当一个线程被阻塞后，别的线程还有继续执行，并发能力强

缺点：一个用户进程会占用多个内核级线程，切换状态的成本高，开销大

多线程模型

一对一模型即是内核级线程

多对一模型即是用户级线程

多对多模型：n用户及线程映射到m个内核级线程（n>m），每个用户进程对应m个内核级线程

优点：既克服了多对一模型并发度不高的缺点，有克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

内核级线程才是处理机分配的单位，内核级线程可以运行任意一个有映射关系的用户级线程代码，只有两个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会被阻塞

状态与转换

几乎和进程的状态和转换一致，线程通过线程控制块TCB来操纵线程

多个TCB可以被组织成一张线程表使用

区别

处理机的调度与死锁

调度的层次

调度：当有很多任务要处理，但由于资源有限，这些事情没法同时处理，这就需要去确定某种规则来决定处理这些任务的顺序，这就是调度研究的问题

作业：一个具体的任务

高级调度(作业调度)：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次，作业调入时会建立PCB，调出的时候才撤销PCB

高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度

低级调度(进程调度)：按照某种策略从就绪队列中选取一个进程，将处理机分配给它

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度，频率很高

中级调度(内存调度)：按照某种策略将进程在内存和外存中调出和调入，让进程在挂起和运行状态切换

调度算法的评价指标

• CPU利用率

指CPU忙碌的时间占总时间的比例

• 系统吞吐量

系统吞吐量：指在单位时间内系统所完成的作业数，因此与批处理作业的平均长度有关，如果单纯为了获得高的系统吞吐量，就应尽量多地选择短作业运行

• 周转时间

周转时间：是指作业被提交给系统开始，到作业完成为止的这段时间间隔，包括4部分时间：作业在外存后备队列上等待调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间

计算机系统的管理者总是希望平均周转时间最短，可以把平均周转时间描述为(各作业周转时间之和)/(作业数)

为了进一步反应调度的性能，更清晰地描述各个进程在其周转时间中，等待和执行时间的具体分配情况，往往使用带权周转时间，其值等于作业周转时间和在CPU上执行的时间的比值，带权周转时间必然大于等于1，因为在CPU上执行的时间被包括在了周转时间之内

• 等待时间

即是进程或作业等待被服务时间之和，平均等待时间即各个作业或进程等待时间的平均值

• 响应时间

响应速度：响应速度是选择分时系统中进程调度算法的重要准则，是从通过键盘提交一个请求开始，知道屏幕上显示出处理结果为止的一段时间间隔。

包括三部分时间：一是请求信息从键盘输入开始，直至将其传送到处理机的时间。二是处理机对请求信息进行处理的时间，三是将所形成的响应信息回送到终端显示器的时间

响应比：(等待时间+要求服务时间)/要求服务时间

进程调度

任务

1. 保存处理机的现场信息。如程序计数器，多个通用寄存器中的内容等
2. 按某种算法选取进程
3. 把处理器分配给进程，此时需要将选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复

调度器和调度程序

进程调度的时机有：

• 创建新进程
• 进程退出
• 运行进程阻塞
• I/O中断发生

非抢占式调度策略：只有运行进程阻塞或退出才触发调度程序工作

抢占式调度策略：每个时钟中断或k个时钟中断会触发调度程序工作

不能进行进程调度的情况

• 处理中断的过程中
• 进程在操作系统内核程序临界区中
• 在原语操作中

闲逛进程

当没有其他就绪程序时，运行闲逛进程(idle)

闲逛进程的优先级最低，能耗低

进程调度的方式

非剥夺调度方式(非抢占方式)

只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态

特点：实现简单，系统开销小，只适用于早起的批处理系统

剥夺调度方式(抢占方式)

当一个进程正在处理机上运行时，处理机可以立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程

特点：可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能，适合于分时操作系统，实时操作系统

调度算法

先来先服务算法(FCFS,First Come First Serve)

算法规则：系统按照作业到达的先后次序来进行调度

作用范围：可以用于作业调度和进程调度

算法类型：非抢占式的算法

优点：公平，算法实现简单

缺点：排在长作业后面的短作业需要等待很长时间，带权周转时间很大，FCFS算法对长作业有利，对短作业不利

饥饿：不会导致

短作业优先算法(SJF,Shortest Job First )

算法规则：最短的作业优先得到服务

作用范围：可以用于作业调度和进程调度

算法类型：非抢占式的算法，但是也有抢占式的版本——SRTN

优点：最短的平均等待时间，平均周转时间

缺点：不公平，对短作业有利，对长作业不利

饥饿：会导致饥饿

高响应比优先算法(HRRN,Highest Response Ratio Next)

响应比：(等待时间+要求服务时间)/要求服务时间

算法规则：每次调度时先计算各个进程响应比，选择响应比最高的进程

作用范围：可以用于作业调度和进程调度

算法类型：非抢占式

优点：综合考虑了等待时间和运行时间，如果等待时间相同，则要求服务时间小的进程先运行(SJF)，如果要求服务时间相同，则等待时间长的先运行(FCFS)

饥饿：不会

时间片轮转调度算法(RR，Round-Robin)

算法规则：按照各个进程到达就绪队列的顺序，轮流让各进程执行一个时间片，如果进程未在一个时间片内执行完，就剥夺处理机，并将进程放在就绪队列队尾重新排队

作用范围：仅进程调度

算法类型：可抢占式

优点：公平，响应快

缺点：由于高频率的进程切换，因此有一定的开销，不区分任务的紧急程度

饥饿：不会

优先级调度算法

算法规则：每个进程都有各自的优先级，调度时选择最高的优先级进程

作用范围：可以用于作业调度和进程调度

算法类型：有抢占式和非抢占式

优点：用优先级区分紧急程度，适用于实时操作系统

缺点：若高优先级进程很多，则可能导致饥饿

饥饿：会

优先级可以分为静态优先级和动态优先级，静态优先级创建时确定并保持不变，动态优先级创建时有一个初始值，之后会根据情况动态地调整优先级

多级反馈队列调度算法(multileved feedback queue)

算法规则：

• 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
• 新进程到达时，先进入第一级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进入下一级队列队尾，如果已经在最下级，则重新放回队列队尾
• 只有第k级队列为空，才会为k+1级队头的进程分配时间片

作用范围：进程调度

算法类型：抢占式算法，在k级队列的运行过程中，若更上级的队列中进入了新进程，那么新进程会抢占处理机，原来运行的进程放回k级队尾

优点：

• 对各个进程相对公平(FCFS)
• 每个新到达的进程都可以很快响应(RR)
• 短进程只用较少时间就可完成(SJF)
• 不必实现估计进程的运行时间
• 可以灵活的调整对各类进程的偏好程度

饥饿：会

总结

死锁

概念

死锁：在并发环境下，各进程因争夺资源而造成的一种互相等待对方手里的资源，导致各进程阻塞，都无法向前推进的现象

产生条件：

• 互斥条件：只有对必须互斥使用的资源争抢才会导致死锁
• 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
• 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有
• 循环等待条件：存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被下一个进程所请求

预防死锁

已经知道死锁的产生需要4个条件，那么破坏其中任意一个条件就可以破坏死锁

1. 互斥条件

如果能把互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态

比如SPOOLing技术，将独占设备在逻辑上改造为共享设备

并不是所有的资源都可以改造成可共享使用的资源，并且为了系统安全，很多地方还必须保护这种互斥性，因此，很多情况下都无法破坏互斥条件

2. 不剥夺条件

方案一：当某个进程请求新的资源得不到满足，就必须立刻释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件

方案二：当某个进程需要的资源被其他进程占有的时候，可以由操作系统协助，将想要的资源强行剥夺，这种方式一般要考虑各进程的优先级

缺点：实现复杂，增加系统开销，方案一会导致饥饿

3. 请求和保持条件

采用静态分配方法，即进程在运行时一次申请完它所需要的全部资源，在它的资源未满足前不让它投入运行，一旦投入运行后，这些资源就一直归它所有

缺点：有些资源可能只需要使用很短的时间，但是一直保持所有资源会让资源利用率极低，另外，也有可能导致某些进程保持饥饿

4. 循环等待条件

采用顺序资源分配法，首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求支援，同类资源一次申请完

原理分析：一个进程只有已占有小编号的资源，才有资格去申请更大编号的资源，有大编号资源的进程不可能逆向回来申请小编号资源，从而不会循环等待

缺点：不方便增加新的设备，如果与实际顺序不一样，就会浪费资源

避免死锁——银行家算法

安全序列：就是指系统按照这种序列分配资源，则每个进程都能顺利完成，只要能找出一个安全序列，系统就是安全状态

如果系统在安全状态，就一定不会发生死锁，如果系统进入不安全状态，就可能发生死锁

银行家算法的核心思想是在资源分配之前想判断这次分配是否会导致系统进入不安全状态

具体执行如下：

假设系统中有n个进程，m种资源，每个进程在运行前先声明对各种资源的最大需求数，则可以用一个n×m的矩阵来表示所有进程对各种资源的最大需求数，称为最大需求矩阵Max，同理系统可以用一个n×m的分配矩阵Allocation来表示所有进程的资源分配情况，Max-Allocation=Need矩阵，表示各进程最多还需要多少各类资源

另外，还需要一个长度为m的一维数组Available表示当前系统中还有多少可用资源，某进程Pi向系统申请资源，可用一个长度为m的以为数组Request表示本次申请的各种资源量，算法执行步骤如下

1. 如果某进程的Need数组大于该进程的Request数组，则到第2步，否则则出错
2. 如果某进程的Request数组小于当前的Available数组，则到第3步，否则表示系统尚无足够资源，进程必须等待
3. 系统试探性把资源分配给进程，并修改相应的数据（并非真的分配，修改数据只是为了预判），修改Available，Request，Allocation的值
4. 操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式分配，否则，恢复相应数据

安全性算法步骤：检查当前剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并且把该进程持有的资源全部回收，不断重复上述过程，看最终是否能让所有进程都加入安全序列

死锁的检测和解除

为了能对系统是否发生了死锁进行检测，必须：

• 用某种数据结构来保存资源的请求和分配信息
• 提供一种算法，利用上述信息来检测系统是否死锁

利用资源分配图这一数据结构，包含两种结点，进程结点对应包含一个进程，资源结点对应一类资源，可能有多个 包含两种边，进程结点到资源结点是申请边，资源结点到进程结点是分配边

如果剩余资源数可以满足进程的需求，那么进程不会被阻塞，可以顺利地执行下去，如果这个进程结束后归还资源，那么可以让另外一些进程执行下去

如果按上述过程，最终消除了所有边，那么这个图是可以简化的，并且一定没有发生死锁，如果不能消除，那么一定发生了死锁

检测死锁的算法：

1. 在资源分配图中，找出不阻塞不孤立的进程，消去它所有的请求边和分配边，使之孤立，然后释放资源
2. 释放的资源可以唤醒原来的阻塞进程，然后再重复1过程，直至取去除所有的边

死锁定理：如果某时刻系统的资源分配图是不可简化的，那么此时系统死锁

解除死锁的主要方法：

1. 资源剥夺法。挂起某些死锁进程，并抢占它的资源

2. 撤销进程法，强制撤销进程

3. 进程回退法，将一个或多个进程直接回退到足以避免死锁的地步