0%

计算机操作系统-进程管理

发表于 更新于 分类于 ，

进程管理

进程与线程

进程

进程是资源分配的基本单位 进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

下图显示了 4 个程序创建了 4 个进程，这 4 个进程可以并发地执行。

image-20201209215006274

线程

线程是独立调度的基本单位。一个进程中可以有多个线程，它们共享进程资源。

QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件

image-20201209215107055

（内核线程）

协程

协程就是用户线程。是编译层面，由编程语言实现的东西，和操作系统无关。对于包含大量I/O的场景，通常的做法是每个I/O连接使用一个线程维护，大部分的线程都处于阻塞状态。这样由于线程很多，对系统内存资源消耗很多，同时线程的频繁切换也会有较大的开销。这时候就提出了协程的概念

协程是用户线程，所有的线程运行在一个线程上，由用户控制协程的调度，内核感知不到协程的存在，因此它只是对线程进行调度。使用协程需要结合异步I/O使用，因为如果某一个协程调用了IO阻塞的操作导致该线程休眠，那么其他的协程也就得不到调用。

区别

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

进程状态的切换

image-20201209221158792
  • 就绪状态（ready）：等待被调度
  • 运行状态（running）
  • 阻塞状态（waiting）：等待资源

应该注意以下内容：

  • 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
  • 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态

交换技术

当多个进程竞争内存资源时，会造成内存资源紧张，并且，如果此时没有就绪进程，处理机会空闲，I/0速度比处理机速度慢得多，可能出现全部进程阻塞等待I/O

针对以上问题，提出了两种解决方法：

  1. 虚拟内存 ： 在内存管理中介绍
  2. 交换技术：换出一部分进程到外存，腾出内存空间

进程调度算法

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

批处理系统

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

  1. 先来先服务 first-come first-serverd（FCFS) : 非抢占式的调度算法，按照请求的顺序进行调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。
  2. 短作业优先 hortest job first（SJF）：非抢占式的调度算法，按估计运行时间最短的顺序进行调度。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
  3. 最短剩余时间优先 shortest remaining time next（SRTN）：最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

交互式系统

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

时间片轮转

将所有就绪进程按 FCFS（先来先服务） 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。时间片轮转算法的效率和时间片的大小有很大关系：

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

优先级制度

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

多级反馈队列

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

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

image-20201209225512870

实时系统

实时系统要求一个请求在一个确定时间内得到响应。分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

同步

临界区

对临界资源进行访问的那段代码称为临界区。为了互斥访问临界资源，每个 进程/ 线程在进入临界区之前，需要先进行检查。

1
2
3
// entry section
// critical section;
// exit section

同步与互斥

互斥是一种特殊的同步。使用基本的锁可以实现同步，但是操作系统需要封装更高级的同步原语来实现更复杂、更实用的功能。信号量（semaphore）和管程（monitor）就是操作系统提供的两种更高级的同步方式，在操作系统（linux）和编程语言都有对应的实现和封装。

  • 同步：多个进程/线程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
  • 互斥：多个进程/线程在同一时刻只有一个进程能进入临界区。

同步的方法

首先区分一个概念，常常说的同步指的是 线程间的同步，也就是可以用信号量，互斥量，管程等，因为这些变量是自己手动定义的，同一个进程中的线程之间的资源是共享的，所以需要使用自定义的变量来完成线程之间的同步或者互斥操作。进程间可能也需要同步，那么进程间的同步是使用IPC机制，即通过进程间的通信实现的，因为进程之间资源不共享，需要经过内核才能完成通信和同步。

信号量

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

  • down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
  • up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断（所谓原语（原子），一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断）如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// P1 P2 互斥地访问临界1区

typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

管程

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。管程有一个重要特性：在一个时刻只能有一个线程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个线程持有。signal() 操作用于唤醒被阻塞的进程。

经典同步问题

生产消费者问题

问题描述：两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息

其实仔细分析，这个题涉及到两个线程同步的问题，即要求 带休眠的功能。如果只使用一个信号量 那么只能表示 空，但是不能体现满的状态，因此需要定义两个信号量。同时 由于 缓冲区属于临界资源，因此访问的时候还需要对缓冲区加锁。

信号量实现

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
#define N 100
typedef int semaphore;
semaphore mutex = 1;  
semaphore empty = N;   // empty大于0时 生产着才能放入 物品  否则休眠
semaphore full = 0;    // full 大于0时 消费者才能取出无 物品 否则休眠

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}
void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

管程实现

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
#define MAX 100
/* 定义管程 PC   C语言中没有管程这个功能，这里只是用C语言逻辑写一下。管程在编译器编译的时候已经使用互斥锁保证了同一时刻只能由一个线程线程运行，即要么是 insert  要么是remove 这也保证了 拿取的过程其实是串行的*/
monitor PC 
{
    int count = 0; 
    /* 我们使用条件变量full 表示被填满的buffer, empty 表示空的buffer */
    conditon full, empty;

    void insert(int item)
    {
        /* 当buffer满的时候,我们在full上将插入操作阻塞 */
        if ( count == MAX ) wait(&full);   // 等待full信号
        insert_item(item);
        count += 1;
        /* 当buffer不空的时候,我们在empty上唤醒取出操作 */
        if ( count == MAX -1 ) signal(&empty);    
    }

    int remove()
    {
        /* 当buffer空的时候,我们在empty上将取出操作阻塞 */
        if( count == 0 ) wait(&empty);    
        remove_item(item);
        count -= 1;
        /* 当buffer不满的时候,我们在full上唤醒插入操作 */
        return item;
        if( count == MAX - 1) signal(&full);  // 发送full信号  此时上面那个full就可以被唤醒了 
    }
}

    void producer()
    {
        int item;
        item = produce_item();
        /*调用管程中的函数 */
        PC.insert(item);
    }
    
    void consumer()
    {
        int item;
        /*调用管程中的函数 */
        item = PC.remove();
        consumer_item();
    }

科学家进餐问题

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

按题目的流程，伪代码表示如下（用一个互斥变量来保护一个筷子，拿筷子即为把该变量置0 这样就实现了题目要求的 一只筷子只能一个人拿，然后按流程组织得到下面初步结果）：

image-20201210213841188

这样存在的问题是 如果这些人 都同时拿起坐边的筷子，然后等右手的筷子，那么就会导致锁死。可以从以下几个思路改进

  1. 方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用
  2. 方法二：仅当哲学家的左右手筷子都拿起时才允许进餐
  3. 方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反

image-20201210215157312方法一 使用一个信号量控制 同时拿起左边筷子的人的数量，初始为4，拿起一个，信号量就减1，这样总能保证有一个人可以拿全两双筷子然后等他吃完释放信号。同时每个筷子用一个互斥变量，保证只有一个人能拿

方法二 利用and 型信号量机制实现 也可以用互斥信号对取左右筷子的操作进行保护，这样四个人取左筷子的流程其实就是串行的了。

读者-写者问题

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

思路：一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

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
typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
    while(TRUE) {
        // 来读数据 读者数 conut + 1 修改count要先对count加锁
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        up(&count_mutex);
         
        read();
        //  读取完毕  将读者数conut - 1  由于又要修改 count 需要将它上锁再修改
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}

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

进程通信

每个进程各自有不同的用户地址空间，任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核，在内核中开辟一块缓冲区，进程1把数据从用户空间拷到内核缓冲区，进程2再从内核缓冲区把数据读走，内核提供的这种机制称为进程间通信（IPC，InterProcess Communication）

进程同步与进程通信很容易混淆，它们的区别在于

  • 进程同步：控制多个进程按一定顺序执行；
  • 进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

管道

管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。管道制存在于内存中，在管道创建时，为缓冲区分配一个页面大小

1
2
#include <unistd.h>
int pipe(int fd[2]);

它具有以下限制：

  • 只支持半双工通信（单向交替传输），且写的时候必须同时在读
  • 只能在父子进程或者兄弟进程中使用
  • 数据一旦被读走，便不在管道中存在，不可反复读取
  • 管道所传送的是无格式字节流，这就要求管道的读出方和写入方必须事先约定好数据的格式，比如多少字节算作一个消息（或命令、或记录）等等

FIFO

1
2
3
#include <sys/stat.h>
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

也称为命名管道，去除了管道只能在父子进程中使用的限制。FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据

消息队列

消息队列是存放在内核中的消息链表，每个消息队列由消息队列标识符表示，消息队列存放在内核中，只有在内核重启 (即，操作系统重启) 或者显示地删除一个消息队列时，该消息队列才会被真正的删除。相比于 FIFO，消息队列具有以下优点：

  • 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
  • 不需要进程自己提供同步方法，消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达；
  • 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收
  • 消息存在于内核，读了之后不会被删除

共享存储

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。需要使用信号量用来同步对共享存储的访问。多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用内存的匿名段。

套接字

与其它通信机制不同的是，它可用于不同机器间的进程通信。

信号量/信号

线程之间的信号量和同一个进程的不同线程之间的信号量不一样 …..