进程调度、同步、通信
操作系统
计算机基础
发布日期:   2019-05-21
文章字数:   6.7k
阅读时长:   23 分
阅读次数:  

进程的调度、同步、通信

进程的组成
  • PCB(进程控制块): 为了描述控制进程的运行，系统中存放进程的管理和控制信息的数据结构称为进程控制块（Process Control Block）。它是进程实体的一部分，是操作系统中最重要的记录性数据结构。它是进程管理和控制的最重要的数据结构，每一个进程均有一个PCB，在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。PCB是进程存在的唯一标识，所谓的创建进程和撤销进程，都是指对 PCB 的操作。
  • 程序段: 存放执行的代码；
  • 数据段: 存放程序运行过程中处理的各种数据；
进程的特征
  • 动态性：进程是程序的一次执行过程，动态产生、变化和灭亡的。
  • 并发性：内存中各进程可并发执行。
  • 独立性：进程是系统进行资源分配、调度的独立单位。
  • 异步性：个进程以不可预知速度向前推进，导致运行结果的不确定性。
  • 结构性：每个进程都有一个PCB，进程由PCB、程序段、数据段组成。
进程的状态与转换

进程三种基本状态：

  • 运行：占有CPU，并在CPU上运行
  • 就绪：已经具备运行条件，但是没有空闲CPU
  • 阻塞：因等待某一事件而暂时不能运行
    在这里插入图片描述
    注意：
  • 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；
  • 而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态；
  • 进程只能自己阻塞自己，因为只有进程自身才知道何时需要等待某种事件的发生；

线程

概念：
QQ 和浏览器是两个进程，浏览器进程里面有很多线程，线程的并发执行使得在浏览器可以打开一个窗口后继续响应其他事件，QQ可以同时发信息和上传文件。

实现方式：

  1. 用户级线程
    把整个线程包放在用户空间中，内核对线程包一无所知，线程切换可以在用户态下直接完成，无需操作系统干预。在用户看来，是有多个线程，从内核角度考虑，意识不到线程存在。优点：用户线程包可以在不支持线程的操作系统上实现。
  2. 内核级线程
    内核级线程的管理工作由操作系统内核完成。线程调度、切换等工作都由内核负责，因此，内核级线程的切换需要在核心态才能完成。优点：内核线程不需要任何新的、非阻塞系统调用，如果某个进程中的线程引起了页面故障，内核可以很方便检查该进程是否有任何其他可运行的线程。缺点：系统调用代价比较大。
  3. 两者混合
    在同时支持用户级线程和内核级线程的系统中，采用两者组合的方式，将n个用户级线程映射到m个内核级线程上(n >=m)，大大提高了灵活度。在这种方法中，内核只识别内核级线程，并对其进行调度，其中一些内核级线程会被多个用户级线程多路复用，每个内核级线程有一个可以轮流使用的用户及线程集合。
进程与线程的异同

一个线程只能属于一个进程，但一个进程中可以有多个线程，它们共享进程资源。

  1. 拥有资源: 进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源；
  2. 调度: 线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换。
  3. 系统开销: 由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
  4. 通信: 进程间通信 (IPC) 需要进程同步和互斥手段的辅助，以保证数据的一致性。而线程间可以通过直接读/写同一进程中的数据段（如全局变量）来进行通信。

进程调度算法

概念：
操作系统管理了系统的有限资源，当有多个进程或线程同时竞争CPU时，因为资源的有限性，必须按照一定的原则选择进程（请求）来占用资源，只要有两个或更多的进程处于就绪状态，如果只有一个CPU可用，那么就必须选择下一个要运行的进程，这就是调度，其中使用的算法就是调度算法。

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

1. 批处理系统
批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间），有以下三种：

  • 先来先服务 first-come first-serverd（FCFS）
    即按照请求的顺序进行调度，非抢占式。
    分析：有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

  • 短作业优先 shortest job first（SJF）
    按估计运行时间最短的顺序进行调度，非抢占式。
    分析：长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

  • 最短剩余时间优先 shortest remaining time next（SRTN）
    按估计剩余时间最短的顺序进行调度，抢占式。

2. 交互式系统
交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

  • 时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程，抢占式。

时间片轮转算法的效率和时间片的大小有很大关系：

因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
而如果时间片过长，那么实时性就不能得到保证。

  • 优先级调度

为每个进程分配一个优先级，按优先级进行调度，抢占式和非抢占式都有。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

  • 多级反馈队列

如果一个进程需要执行 100 个时间片，采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，优先级从高到低，时间片从小到大，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次，抢占式。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

3. 实时系统
实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

进程同步

同步 互斥概念

进程同步：指相互合作去完成相同的任务的进程间，由同步机构对执行次序进行协调。(在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。)；
进程互斥：指多个进程在对临界资源进行访问的时候，应采用互斥方式；
简单来说，同步：多个进程按一定顺序执行；互斥：多个进程在同一时刻只有一个进程能进入临界区。

信号量

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

  • down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
  • up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。
    down 和 up 操作需要被设计成原语，不可分割，保证一旦一个信号量操作开始，则在该操作完成或阻塞之前，其他进程均不允许访问该信号量，这种原子性对解决同步问题和避免竞争条件是绝对必要的。通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

使用信号量实现生产者-消费者问题

问题描述：
生产者、消费者共享一个初始为空、大小为n的缓冲区；
只有缓冲区没满时，生产者才可以放入物品，否则必须等待；
只有缓冲区不为空，消费者才可以拿走物品，否则必须等待；
缓冲区属于临界资源，各进程必须互斥地访问；

分析：用信号量机制（P、V操作）实现生产者、消费者互斥、同步：

semaphore    mutex  =  1;    //互斥信号量 mutex 来控制对缓冲区的互斥访问
semaphore    empty=  0;    //同步信号量，表示空闲缓冲区的数量，当 empty 不为 0 时，生产者才可以放入物品
semaphore    full  =  0;        //同步信号量，表示产品的数量，当 full 信号量不为 0 时，消费者才可以取走物品
#define N 100                            /*缓冲区的槽数目 */
typedef int semaphore;                
semaphore mutex = 1;                /*控制对临界区的访问*/
semaphore empty = N;                /*计数缓冲区的空槽数目 */
semaphore full = 0;                        /*计数缓冲区的满槽数目，即产品数量 */

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);                    /*将空槽数目减1 */
        down(&mutex);                    /*进入临界区 */
        insert_item(item);                /*将新数据项放到缓冲区中*/
        up(&mutex);                        /*离开临界区*/
        up(&full);                            /*将满槽数目加1*/
    }
}

void consumer() {
    while(TRUE) {
        down(&full);                        /*将满槽数目减1 */
        down(&mutex);                    /*进入临界区 */
        int item = remove_item();    /*从缓冲区中取出数据项 */
        consume_item(item);            /*处理数据项*/
        up(&mutex);                        /*离开临界区*/
        up(&empty);                        /*将空槽数目加1*/
    }
}

注意：不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去，出现“死锁”现象。
因此：实现互斥的down（P）操作一定要在实现同步的down（P）操作之后，up（V）操作不会导致进程阻塞，因此两个V操作顺序可以交换。

生产者消费者问题分析：

  1. 关系分析：找出各个进程，分析它们之间同步、互斥关系；
  2. 根据各进程操作流程确定P、V操作的大致顺序；
  3. 设置信号量，并确定信号量初值；通常互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少。

类似的经典同步问题还有：

1. 读者-写者问题：
允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。
互斥关系：写进程——写进程、写进程——读进程、读进程与读进程不存在互斥问题。

一个整型变量 count 记录在对数据进行读操作的进程数量
一个互斥量 count_mutex 用于对 count 加锁（防止两个读进程并发执行，这样两个进程先后执行down(&data_mutex)，从而使第二个线程阻塞）
一个互斥量 data_mutex 用于对读写的数据加锁，保证对文件的互斥访问。

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
    while(TRUE) {
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        up(&count_mutex);

        read();
        down(&count_mutex);
        count--;        // 访问文件的读进程数-1
        if(count == 0) up(&data_mutex);        // 最后一个进程负责解锁
        up(&count_mutex);
    }
}

void writer() {
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

以上这种算法潜在的问题：只要读进程还在读，写进程就要一直阻塞等待，可能“饿死”。因此，这种算法中，读进程是优先的。

防止写进程饿死的方法:
即在第一个读者到达，且一个写者在等待时，读者在写者之后被挂起，而不是立即允许进入。用这种方式，在一个写者到达时如果有正在工作的读者，那么该写者只要等待这个读者完成，而不用等候其后面到来的读者。但是该方案并发度和效率较低。

图片来自zxzxzx0119的博客

2. 哲学家进餐问题：

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子（一边一根），并且一次只能拿起一根筷子。

下面是一种错误的解法，考虑到如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。


#define N 5           // 哲学家个数
void philosopher(int i)  // 哲学家编号：0 － 4
{
    while(TRUE)
    {
        think();                // 哲学家在思考
        take_fork(i);            // 去拿左边的叉子
        take_fork((i + 1) % N);    // 去拿右边的叉子
        eat();                //　吃饭
        put_fork(i);            // 放下左边的叉子
        put_fork((i + 1) % N);    // 放下右边的叉子
    }
}

为了防止死锁的发生，可以设置两个条件（临界资源）：

  • 必须同时拿起左右两根筷子；
  • 只有在两个邻居都没有进餐的情况下才允许进餐。
    #define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N    // 右邻居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟踪每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥
semaphore s[N];              // 每个哲学家一个信号量

void philosopher(int i) {
while(TRUE) {
think(); // 思考
take_two(i); // 拿起两个筷子
eat();
put_two(i);
}
}

void take_two(int i) {
down(&mutex); // 进入临界区
state[i] = HUNGRY; // 我饿了
test(i); // 试图拿两只筷子
up(&mutex); // 退出临界区
down(&s[i]); // 没有筷子便阻塞
}

void put_two(i) {
down(&mutex);
state[i] = THINKING;
test(LEFT); // 左边的人尝试
test(RIGHT); //右边的人尝试
up(&mutex);
}

void test(i) { // 尝试拿起两把筷子
if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
state[i] = EATING;
up(&s[i]); // 通知第i个人可以吃饭了
}
}


哲学家问题关键在于解决进程死锁；
这些进程之间只存在互斥关系，但是和之前的互斥关系不同的是: 每个进程都需要同时持有两个临界资源，因此有死锁的可能；

#### 管程
管程是一个由过程、变量及数据结构等组成的一个集合，他们组成一个特殊的模块或软件包。

使用用信号量机制实现的生产者消费者问题需要客户端代码做很多控制而且编程麻烦，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

c 语言不支持管程，下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法，客户端代码通过调用这两个方法来解决生产者-消费者问题。
~~~ pascal
monitor ProducerConsumer
    integer i;
    condition c;

    procedure insert();
    begin
        // ...
    end;

    procedure remove();
    begin
        // ...
    end;
end monitor;

管程有基本特性：

  • 每次只能有一个进程使用管程。这一特性使管程能有效完成互斥。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。
  • 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据。

管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。

  • 对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有，比如生产者发现缓冲区已满，它会在某个条件变量上如（full）执行wait操作。
  • signal() 操作用于唤醒被阻塞的进程。

使用管程实现生产者-消费者问题 ：
一次只能有一个管程过程活跃

// 管程
monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

进程的通信

可以参考

进程间通信（IPC，InterProcess Communication）是指在不同进程之间传播或交换信息。

IPC的方式通常有管道（包括无名管道和命名管道）、消息队列、信号量、共享存储、Socket、Streams等。其中 Socket和Streams支持不同主机上的两个进程IPC。

1.管道：

管道，通常指无名管道，是 UNIX 系统IPC最古老的形式。

特点：

  • 它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。

  • 它只能用于父子进程之间的通信。

  • 当一个管道建立时，它会创建两个文件描述符：fd[0]为读而打开，fd[1]为写而打开，要关闭管道只需将这两个文件描述符关闭即可。

    1 #include <unistd.h>
2 int pipe(int fd[2]);    // 返回值：若成功返回0，失败返回-1

    在这里插入图片描述

    2.FIFO：

    FIFO，也称为命名管道，它是一种文件类型，去除了管道只能在父子进程中使用的限制，FIFO可以在无关的进程之间交换数据。

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

3. 消息队列：

消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。

1、特点
消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。

消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。

消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。

4. 信号量：

信号量（semaphore）与已经介绍过的 IPC 结构不同，它是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

特点：

  • 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。

  • 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。

  • 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。

  • 支持信号量组。

5. 共享存储：

特点：

  • 共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。

  • 因为多个进程可以同时操作，所以需要进行同步。

  • 信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

总结：

  1. 管道：速度慢，容量有限，只有父子进程能通讯

  2. FIFO：任何进程间都能通讯，但速度慢

  3. 消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题

  4. 信号量：不能传递复杂消息，只能用来同步

  5. 共享内存：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存

死锁：

可参考书本或者cyc
死锁: 如果一个进程集合里面的每个进程都在等待只能由这个进程集合中的其他一个进程（包括他自身）才能引发的事件，那么该进程集合就是死锁的。

必要条件：

  • 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
  • 占有和等待：已经得到了某个资源的进程可以再请求新的资源。
  • 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
  • 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

死锁发生时，以上四个条件一定是同时满足的，缺一不可。

四种处理死锁策略：

  1. 鸵鸟策略
  2. 检测死锁并恢复
  3. 动态避免死锁
  4. 预防死锁产生
鸵鸟策略

忽略该问题，把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

检测死锁并恢复

系统并不试图阻止死锁的产生，而是允许死锁发生，当检测到死锁发生时，采取措施进行恢复。

  1. 每种类型一个资源的死锁检测
  2. 每种类型多个资源的死锁检测

死锁恢复：

  1. 利用抢占恢复（将某个资源从它的当前所有者那里转移给另一个进程）
  2. 利用回滚恢复（将进程复位到一个更早的状态）
  3. 通过杀死进程恢复（最简单解决死锁方法，可以杀掉环中的一个进程）
死锁避免

安全状态：
如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

单个资源的银行家算法：
该模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

多个资源的银行家算法：

预防死锁产生

破坏死锁产生必要条件，使死锁不会产生。
1. 破坏互斥条件：
将临界资源改造为可共享使用的资源（如SPOOLing技术）
缺点：可行性不高，很多时候无法破坏互斥条件

2. 破坏占有和等待条件：
一种实现方式是规定所有进程在开始执行前请求所需要的全部资源，之后一直保持。
缺点：资源利用率低；可能导致饥饿

3. 破坏不可抢占条件：
一种实现方式是申请的资源得不到满足时，立即释放拥有的所有资源
缺点：实现复杂，反复申请和释放导致系统开销大

4. 破坏环路等待条件：
给资源编号，进程必须按照编号的顺序申请资源
缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦

参考书籍：《现代操作系统》

赏

   转载规则


《进程调度、同步、通信》 由 ForeverSen 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
LeetCode中有关哈希表问题 LeetCode中有关哈希表问题
对LeetCode中几道关于哈希表问题进行总结： 1.两数之和题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是
2019-06-02 LeetCode
哈希表
下一篇 
操作系统基本概念 操作系统基本概念
### 概念、特征、系统调用、中断 操作系统基本概念 操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理的组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境。它是计算机系统的最基本的系统软件。 也是系统软硬
2019-05-16 计算机基础
操作系统
  目录