第二章_进程与线程

[[toc]]

进程与线程

进程与线程的比较

	进程	线程
映像组成	由程序段，相关数据段和PCB组成	共享其隶属进程的进程映像，仅拥有线程ID，寄存器集合和堆栈等
并发性	在没有引入线程的操作系统中，进程是独立运行的基本单位	线程是独立运行的基本单位,一个进程可以拥有一个或多个线程
资源分配	进程是资源分配和拥有的基本单位	线程自己不拥有系统资源，但它可以访问所属进程所拥有的全部资源
调度	在没有引入线程的操作系统中，进程是独立调度和分配的基本单位	在引入线程后的操作系统，线程是独立调度和分配的基本单位
通信	PV操作；共享存储；消息传递；管道通信	同一进程的各线程直接读写进程数据段，不同进程的线程之间通信属于进程剑通信
目的	更好的使多道程序并发执行，提高资源利用率和系统吞吐量	减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能
地址空间	进程的地址空间之间相互独立	同一进程的各线程间共享进程的地址空间

进程映像是静态的，进程是动态的

PCB

PCB是进程存在的唯一标记！！！

组成：

• 进程描述信息
• 进程控制和管理信息
• 资源分配清单
• 处理机相关信息

进程描述信息	进程控制和管理信息	资源分配清单	处理机相关信息
进程标识符（PID）	进程当前状态	代码段指针	通用寄存器值
用户标识符（UID）	进程优先级	数据段指针	地址寄存器值
	代码运行入口地址	堆栈段指针	控制寄存器值
	程序的外存地址	文件描述符	标记寄存器值
	进入内存时间	键盘	状态字
	处理机占用时间	鼠标
	信号量的使用

进程的状态

从运行态变成阻塞态是主动的

用户级线程和内核支持线程

线程	用户级线程	内核级线程
优点	线程切换不需要转换到内核空间，节省了开销	一个线程被阻塞，内核可以调度该进程中的其他线程；能发挥多处理器优势
缺点	一个线程被阻塞，则同一进程内所有线程都会被阻塞	同一进程中，线程切换时，需要从用户态转到内核态，系统开销大

多线程模型：

• 多对一 > 一个线程阻塞，则整个进程阻塞
• 一对一
• 多对多

进程控制

进程创建

在同一个进程中，线程切换不会引起进程的切换。

当从一个进程中的线程切换到另一个进程中的线程时，才会引起进程的切换。

处理机调度

在多道程序系统中，进程的数量往往多于处理机个数，因此进程争用处理机的情况在所难免。

处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

调度的层次

• 高级调度（作业调度）
• 中级调度（内存调度）
• 低级调度（进程调度）

多道批处理器系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。

引入中级调度的目的是提高内存利用率和系统吞吐量。

进程调度是最基本的，不可或缺。

调度的原则

CPU利用率：

CPU的工作在整个系统工作时间所占的比例。

\[ CPU利用率 = \frac{CPU有效工作时间}{CPU有效工作时间 + CPU空闲等待时间} \]

系统吞吐量： 表示单位时间内CPU完成作业的数量。

周转时间：

\[ 周转时间 = 作业完成时间 - 作业提交时间 \]

平均周转时间：

\[ 平均周转时间 = \frac{作业1的周转时间 + ... + 作业n的周转时间}{n} \]

带权周转时间：

\[ 带权周转时间 = \frac{作业周转时间}{作业实际运行时间} \]

等待时间：

进程处于等待处理器状态的时间之和。

响应时间：

从用户提交请求到系统首次产生响应所用的时间。

不能进行处理机调度的情况

• 在处理中断的过程中
• 进程在操作系统内核临界区中
• 其他需要完全屏蔽中断的原子操作过程中

常用的调度算法

算法	调度方法	特点
先来先服务FCFS	每次选择最先进入的作业或进程	有利于长作业不利于短作业 有利于CPU繁忙型型作业不利于I/O繁忙型作业
短作业优先SJF	选择运行时间最短的	平均等待时间，平均周转时间最少
时间片轮转	所有进程按先来先服务排队	主要适用于分时系统
优先级调度	选择优先级最高的	系统进程> 用户进程 交互性进程> 非交互性进程 I/O型进程>计算型进程
高响应比优先	选择响应比最高的	有利于短作业，长作业不会产出“饥饿”，等待时间越长，优先级越高
多级反馈队列	...	终端型作业：短作业优先 短批处理作业用户：周转时间较短 长批处理作业用户：不会长期得不到处理

响应比：

\[ 响应比R_p = \frac{等待时间 + 要求服务时间}{要求服务时间} \]

同步与互斥

基本概念

我们将一次仅允许一个进程使用的资源称为临界资源

临界区：进程中访问临界资源的那段代码。

do {
    entry section;      //进入区
    critical section;   //临界区
    exit section;       //退出区
    remainder section;  //剩余区
}while(true)

同步： 进程需要协调它们的工作次序而等待，传递信息所产生的制约关系。

互斥： 当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源

同步需要遵循的准则： - 空闲让进 -- 临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。 - 忙则等待 -- 当已有进程进入临界区时，其他试图进入临界区的进程必须等待。 - 有限等待 -- 对已有进程进入临界区，应保证能在有限时间内进入临界区。 - 让权等待 -- 当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

实现临界区互斥的基本方法

软件实现

• 单标记法
• 双标记法先检查
• 双标记法后检查
• 皮特森算法（Peterson）

单标记法

设置一个公用模型变量turn,用于指示被允许进入临界区的进程编号，即若turn = 0,则允许\(p_0\)进程进入临界区。

//p0进程
while(turn != 0);   //进入区
critical section;   //临界区
turn = 1;           //退出区
remainder section;  //剩余区

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

该算法保证每次只允许一个进程进入临界区，但两个进程必须交替进入临界区，若某个进程不再进入临界区，则另一个进程也将无法进入临界区。 违背了空闲让进，容易造成资源利用不充分。

双标记法先检查

思想：

在每个进程访问临界区资源之前，先检查临界资源是否正在被访问，若正在被访问，该进程等待；否则，进程才进入自己的临界区。

设置一个数组flag[2],表示进程是否进入临界区。flag[i]值为FALSE,表示\(P_i\)进程未进入临界区，值为TRUE,表示\(P_i\)进程进入临界区。

//P_i进程
while(flag[j]);     // 1 进入区
flag[i] = TRUE;     // 3 进入区
critical section;   // 临界区
flag[i] = FALSE;    //退出区
remainder section;  //剩余区

// P_j进程
while(flag[i]);     // 2
flag[j] = TRUE;     // 4
critical section;
flag[j] = FALSE;
remainder section;

优点：不用交替进入，可连续使用；

缺点：\(P_i\)和\(P_j\)可能同时进入临界区；

按系列1，2，3，4执行，会同时进入临界区（违背了忙则等待）。

双标记法后检查

和双标记法先检查相比，先将自己的标记设置为TRUE,再检测对方的状态标记，若对方标记为TRUE,则进程等待；否则进入临界区。

//P_i进程
flag[i] = TRUE;     // 先设置自己的标记，进入区
while(flag[j]);     // 检查对方状态，进入区
critical section;   // 临界区
flag[i] = FALSE;    // 退出区
remainder section;  // 剩余区

//P_j进程
flag[j] = TRUE;
while(flag[i]);
critical section;
flag[j] = FALSE;
remainder section;

确保进程可以互斥访问临界区。

但是存在两个进程都进不了临界区的“饥饿”现象。

皮特森算法（Peterson）

为了防止两个进程为进入临界区而无限期等待，又设置了变量turn，每个进程在先设置自己的标记之后再设计turn标记。再同时检测另一个进程状态标记和 允许进入标记，以便保证两个进程同时要求进入临界区，只允许一个进程进入临界区。

//P_i进程
flag[i] = TRUE, turn = j;  // falg[j] = TRUE表示它想要进入临界区，turn = j,表示进程P_j已在临界区
while(flag[j] && turn == j);
critical sections;
flag[i] = FALSE;
remainder section;

// P_j进程
flag[j] = TRUE, turn = i;
while(flag[i] && turn == i);
critical section;
flag[j] = FALSE;
remainder section;

Peterson算法利用turn解决了“饥饿”问题

硬件实现方法

（低级方法）

（1）中断屏蔽方法

关中断
临界区
开中断

效率低

（2）硬件指令方法

由硬件逻辑直接实现，不会被中断

TestAndSet指令，原子操作,即这条指令执行时不允许被中断。

功能：读出指定标志后把该指令设置为真。

Swap指令：

功能：交换两个字（字节）的内容。

小结：

缺点：进程等待进入临界区要耗费处理机时间，不能实现让权等待，会导致“饥饿”现象。

优点：适用于任意数目的进程，而不管是单处理机还是多处理机；简单，容易验证其正确性。

互斥锁

解决临界区最简单的工具就是互斥锁（mutex lock）。一个进程在进入临界区时应获得锁，在退出临界区时释放锁。 函数acquire()获得锁，而函数release()释放锁。

每个锁有一个布尔变量available,表示锁是否可用。

互斥锁通常采用硬件机制实现

缺点：忙等待

信号量

用来解决互斥与同步问题，它只能被两个标准的原语wait(s)和signal(s)访问，也可记为“P操作”或“V操作”。

整型信号量

wait(S){
        while(S <= 0);
        S = S - 1;
}
signal(S){
        S = S + 1;
}

不遵循“让权等待”的准则，而是使进程处于“忙等”的状态。

记录型信号量

除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程。 wait操作请求一个该类资源时，如果s.value < 0,表示该类资源已经分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机。 并插入该类资源的等待队列S.L。

不存在“忙等”现象等进程同步机制。遵循了“让权等待”准则。

利用信号量实现同步

同步就是根据什么次序配合互相完成。

利用信号量实现进程互斥

一般都把初始化信号量设为1.

semaphore S = 1;        // 初始化信号量

P1() {
        ...
        P(S);           // 准备开始访问临界资源，加锁
        进程P1的临界区；
        V(S);           // 访问结束，解锁
        ...
}

P2() {
        ...
        P(S);
        进程P2的临界区
        V(S);
        ...
}

利用信号量实现前驱关系

管程

在信号量机制中，每个要访问临界资源的进程都必须自备同步的PV操作。大量分散的同步操作给系统管理带来了麻烦， 且容易因操作不当而导致系统死锁。

定义

管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

组成： - 管程的名称 - 局部于管程内部的共享数据结构说明 - 对该数据结构进行操作的一组过程 - 对局部于管程内部的共享数据设置初始值的语句

管程很像一个类（class）： - 管程把对共享资源的操作封装起来 - 每次仅允许一个进程进入管程

条件变量

将阻塞原因定义为条件变量。

对条件变量只能进行两种操作： wait和signal

经典同步问题（重点！！！）

1. 生产者-消费者问题

问题描述： 一组生产者进程和一组消费者进程共享一个初始为空，大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区， 否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中 取出消息。

问题分析：

1. 关系分析。生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个互相协作的关系，只有生产者生产之后，消费者才能消费， 它们也是同步关系。

2. 思路。只有生产者和消费者两个进程，它们又是互斥和同步关系，那么需要解决的是互斥和同步PV操作的位置。

3. 信号量设置。信号量mutex作为互斥信号量，用于控制互斥访问访问缓冲区，互斥信号量初始值为1；信号量full用于记录当前缓冲池中的“满”缓冲区数， 初值为0，信号量empty用于记录当前缓冲池中的“空”缓冲区数，初值为n。

semaphore mutex = 1;        // 临界区互斥信号量
semaphore empty = n;        // 空闲缓冲区
semaphore full = 0;         // 缓冲区初始化为空

producer() {                // 生产者进程
    while(1) {
        produce an item in nextp;   // 生产数据
        p(empty);                   // 获取空缓冲区单元
        p(mutex);                   // 进入互斥区
        add nextp to buffer;        // 将数据放入缓冲区
        v(mutex);                   // 离开互斥区，释放互斥信号量
        v(full);                    // 满缓冲区数+1
    }
}

consumer() {                        // 消费者进程
    while(1) {
        p(full);                    // 获取满缓冲区单元
        p(mutex);                   // 进入临界区
        remove an item from buffer; // 从缓冲区取数据
        v(mutex);                   // 离开临界区，释放互斥信号量
        v(empty);                   // 空缓冲区数+1
        consum the item;            // 消费数据
    }
}

2. 读者-写者问题

问题描述： 有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：

1. 允许多个读者可以同时对文件执行读操作；

2. 只允许一个写者往文件中写信息；

3. 任一写者在完成写操作之前不允许其他读者或写者工作；

4. 写者执行写操作之前，应让已有的读者和写者全部退出；

问题分析：

1. 关系分析。读者和写者是互斥的，写者和写者也是互斥的，读者和读者不存在互斥问题。

2. 思路。两个进程，即读者和写者。写者和任何进程都互斥，因此只需要互斥信号量的PV操作即可。读者问题比较复杂，它必须在实现与写者互斥的同时，实现与其他 读者的同步，因此简单的一对PV操作是无法解决问题，这里我们用到一个计数器，用来判断当前是否有读者读文件。当有读者时，写者是无法写文件的，此时读者会 一直占用文件，当没有读者时，写者才可以写文件。同时，这里不同读者对计数器的访问应该也是互斥的。

3. 信号量设置。首先设置信号量count为计数器，用于记录当前读者的数量，初值为0；设置mutex为互斥信号量，用于保护更新count变量的互斥；设置互斥信号量 rw，用于保证读者和写者的互斥访问。

读进程优先：

int count = 0;              // 用于记录当前的读者数量
semaphore mutex = 1;        // 用于保护更新count变量时的互斥
semaphore rw = 1;           // 用于保证读者和写者互斥地访问文件

writer() {                  // 写者进程
    while(1) {
        p(rw);              // 互斥访问共享文件
        writing;
        v(rw);              // 释放共享文件
    }
}

reader() {                  // 读者进程
    while(1) {
        p(mutex);           // 互斥访问count
        if(count == 0)      // 当第一个读进程读共享文件时
          p(rw);            // 阻止写进程写
        count++;            // 读者计数器+1
        v(mutex);           // 释放互斥变量count
        reading;
        p(mutex);           // 互斥访问count
        count--;            // 读者计数器减1
        if(count == 0)      // 当最后一个读进程读完共享文件
            v(rw);          // 允许写进程写
        v(mutex);           // 释放互斥变量count
    }
}

当存在读进程时，写操作被延迟，且只要有一个读进程活跃，随后的读进程都被允许访问文件，这样会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

写进程优先：

有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件中的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下， 才允许读进程再次运行，因此，增加一个信号量并在上面的writer()和reader()函数中各增加一对PV操作。

int count = 0;              // 用于记录当前的读者数量
semaphore mutex = 1;        // 用于保护更新count变量时的互斥
semaphore rw = 1;           // 用于保证读者和写者互斥地访问文件
semaphore w = 1;            // 用于实现“写优先”

writer() {                  // 写者进程
    while(1) {
        p(w);               // 在无写进程请求时进入

        p(rw);              // 互斥访问共享文件
        writing;
        v(rw);              // 释放共享文件

        v(w);               // 恢复对共享文件的访问
    }
}

reader() {                  // 读者进程
    while(1) {
        p(w);               // 在无写进程请求时进入

        p(mutex);           // 互斥访问count
        if(count == 0)      // 当第一个读进程读共享文件时
          p(rw);            // 阻止写进程写
        count++;            // 读者计数器+1
        v(mutex);           // 释放互斥变量count
        
        v(w);               // 恢复对共享文件的访问

        reading;
        p(mutex);           // 互斥访问count
        count--;            // 读者计数器减1
        if(count == 0)      // 当最后一个读进程读完共享文件
            v(rw);          // 允许写进程写
        v(mutex);           // 释放互斥变量count
    }
}

也叫做读写公平法

3. 哲学家进餐问题

问题描述： 一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌子上摆着一根筷子，两根筷子中间是一碗米饭。 只有当哲学家饥饿时，才试图拿起左，右两根筷子（一根一根拿起）。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到两根 筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。

问题分析：

1. 关系分析。5名哲学家与左右邻居对其中间的筷子的访问是互斥关系。
2. 整理思路。显然，这里有5个进程。关键是如何让一名哲学家拿到左右两根筷子而不造成死锁或即饿现象。 解决方法有两个：一是让他们同时拿两根筷子；二是对每名哲学家的动作制定规则，避免饥饿或死锁现象的发生。
3. 信号量设置。定义互斥信号量数组chopstick[5] = {1,1,1,1,1},用于对5个筷子的互斥访问。哲学家按顺序编号0～4，哲学家i左边的筷子编号为i， 右边筷子编号为(i+1)%5。

同时拿筷子：

semaphore chopstick[5] = {1,1,1,1,1};       // 定义信号量数组
pi() {
    do {
        p(chopstick[i]);                    // 取左边筷子
        p(chocktick[(i+1)%5]);              // 取右边筷子
        eat;
        v(chopstick[i]);                    // 放回左边筷子
        v(chopstick[(i+1)%5]);              // 放回右边筷子
        think;
    } while(1);
}

该算法存在以下问题：当5名哲学家都想要进餐并分别拿起左边的筷子时，筷子已被拿完，等他们再想拿右边筷子时，就被完全阻塞， 因此出现了死锁。

为防止死锁发生，可对哲学家进程施加一些限制条件。

• 至多允许4名哲学家同时进餐
• 仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子。
• 对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后拿右边筷子，偶数号哲学家相反。

下面我们采用第二种方法：当一名哲学家左右两边筷子都可用时，才允许他抓起筷子。

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;                            // 设置取筷子信号量
pi() {                                          // i 号哲学家进程
    do {
        p(mutex);                                   // 在取筷子之前获得互斥量
        p(chopstick[i]);                            // 取左边筷子
        p(chopstick[(i+1)%5]);                      // 取右边筷子
        v(mutex);
        eat;
        v(chocktick[i]);
        v(chocktick[(i+1)%5]);
        think;
    }while(1);
}

4. 吸烟者问题

问题描述： 假设一个系统有三个抽烟者进程和一个供应者进程。要卷起并抽掉一根烟，抽烟者需要三种材料：烟草，纸和胶水。 三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限特供三种材料，供应者每次将两种材料放在桌子上， 拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放在桌上， 如此重复。

问题分析：

1. 关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或以上的抽烟者，三个抽烟者对抽烟这个动作互斥。
2. 整理思路。显然这里有4个进程，供应者作为生产者向三个抽烟者提供材料。
3. 信号量设置。信号量offer1,offer2,offer3分别表示烟草和纸的资源，烟草和胶水组合的资源，纸和胶水组合的资源。 信号量finish用于互斥进行抽烟动作。

int num = 0;                    // 存储随机数
semaphore offer1 = 0;           // 烟草和纸组合的资源
semaphore offer2 = 0;           // 烟草和胶水组合的资源
semaphore offer3 = 0;           // 纸和胶水组合的资源
semaphore finish = 0;           // 表示抽烟动作是否完成

process P1() {                  // 供应者
    while(1) {
        num++;
        num = num % 3;
        if(num == 0)
            v(offer1);          // 提供烟草和纸
        else if(num == 1)
            v(offer2);          // 提供烟草和胶水
        else
            v(offer3);          // 提供纸和胶水

        // 任意两种材料放在桌子上。
        p(finish);
    }
}

process P2() {                  // 拥有烟草者
    while(1) {
        p(offe3);
        拿纸和胶水，卷成烟，抽掉；
        v(finish);
    }
}

process P3() {                  // 拥有纸者
    while(1) {
        p(offe2);
        拿烟草和胶水，卷成烟，抽掉；
        v(finish);
    }
}

process P4() {                  // 拥有胶水者
    while(1) {
        p(offe1);
        拿纸和烟草，卷成烟，抽掉；
        v(finish);
    }
}

死锁

定义

指多个进程因竞争资源而造成的一种互相等待，若无外力作用，这些进程都无法向前推进。

死锁产生的原因

• 系统资源的竞争
• 进程推进顺序不当

死锁产出的必要条件

1. 互斥条件： 在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
2. 不剥夺条件： 进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放。
3. 请求与保持条件： 进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞， 但对自己获得的资源保持不放。
4. 循环等待条件： 存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

死锁的处理策略

• n 个进程，每个进程需要m个某类资源，则发生死锁的最大资源数为n(m-1)，不发生死锁的最小资源数为n(m-1) + 1。

死锁预防

需要破坏死锁的4个必要条件中的一个或多个。

避免死锁

在死锁的动态分布过程中，用某种方法防止系统进入不安全状态。

并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态； 只要系统处于安全状态，系统便可以避免进入死锁状态。

死锁一定是不安全状态，不安全状态不一定是死锁状态。

最主要的算法就是：银行家算法

银河家算法的主要数据结构为

数据结构
可利用资源Available
最大需求矩阵Max
分配矩阵Allocation
需求矩阵Need

死锁检测和解除

允许产生死锁，采取某种措施解除死锁。

资源分配图

用圆圈代表一个进程，用框代表一类资源。

从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；

从资源到进程的边称为分配边。表示该类资源已有一个资源分配给了该进程。

p1,p2为进程，R1，R2表示资源

死锁定理

当资源分配图不可完全简化，则为死锁。

简化资源分配图可检测系统状态S是否处于死锁状态。简化方法如下：

1. 在资源分配图中，找出既不阻塞又不孤点的进程 \(P_i\) （即找出一条有向边与它相邻，且该有向边对应的资源的申请数量小于等于系统中已有 的空闲资源数量。）如上图，我们可以找到进程p1,（R1没有资源，R2有一个资源，进程p1也只有一条申请边），消去它所有的请求边和分配边， 使之成为孤立的点。如图（b）

2. 进程 \(P_i\)所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程，重复动作1。

死锁解除

1. 资源剥夺法
2. 撤销进程法
3. 进程回退法