########################################
进程管理
########################################

进程的基本概念
****************************************

   ``进程`` 是用来描述 ``程序`` 的执行过程并且能用来共享资源的基本单位。

进程有以下几个特征：

   - 进程可以并发执行
   - 进程是一个独立调度的活动
   - 进程在执行任务时需要分配和释放资源

进程和程序有以下区别：

  - 程序是一个静态概念，是指令的有序集合，没有执行含义；进程是一个动态概念，是程序的执行过程，动态地被创建并消亡。
  - 程序不反应执行过程，因而没有并发特征；进程具有并发特征
  - 不同的进程可以包含同一个程序，只要程序对应的数据集不同即可。

进程的描述
****************************************

进程的状态：

.. mermaid::

   graph TD

      A[创建] -->|许可| B[就绪态]
      B -->|进程调度| C[执行态] -->|释放| D[终止态]
      C -->|时间片完| B
      C -->|IO 请求| E[阻塞态]
      E -->|IO 完成| B

进程互斥
****************************************

使用信号量实现进程互斥
========================================

使用信号量实现进程互斥的基本思路为：

- 进入临界区前执行 P 原语
- 退出临界区后执行 V 原语

伪代码如下：

.. code-block:: cpp

    // 进程A：
    P(sem)
    <S>
    V(sem)

    // 进程B：
    P(sem)
    <S>
    V(sem)

.. seealso::

   - \ ` 用信号量机制来实现多个进程对临界资源的互斥访问 & PV操作  <https://www.iteye.com/blog/wuaner-522048>`_

进程同步
****************************************

进程同步是由于一组异步环境下的进程，各自的执行结果互为对方的执行条件，从而导致进程间需要通过发送消息。

例：
- 进程A为计算进程，其需要等待缓冲区空的时候才可以执行
- 进程B为打印进程，其需要等待缓冲区满的时候才可以执行
设 ``wait()`` 表示等待信号， ``emit`` 表示发送信号，则可表示为：

.. code-block:: none

    // 进程A
    wait(BufEmpty)
    进行计算
    emit(BufFull)

    // 进程B
    wait(BufFull)
    进行打印
    emit(BufEmpty)

以上可以看到：bufFull为进程A的信号，BufEmpty为进程B的信号

使用信号量实现进程同步
========================================

与进程互斥进程间共用信号量不同，进程同步时信号量是私有的，这意味着 ``只有信号量的拥有者才可以调用 V 原语``，其他进程只能调用 P 原语。

同样以上面的例子为例：

.. code-block:: none

    // 进程A
    P(bufEmpty)
    进行计算
    V(BufFull)

    // 进程B
    P(BufFull)
    进行打印
    V(bufEmpty)

.. hint::

    - 进程同步时的信号量又被称为 ``私有信号量``，V 原语只能被一个进程调用，P 原语可以由任意进程调用
    - 进程互斥时的信号量又被称为 ``公有信号量``，P、V 原语可以被任意进程调用

生产者-消费者问题
========================================

生产者-消费者问题需要同时用到进程同步和进程互斥，问题描述如下：

- 设有一有界缓冲区，向缓冲区写入数据者为生产者，向缓冲区读出数据者为消费者
- 生产者要写入缓冲区，则缓冲区至少有一个单元是可写的，写入过程中该单元不可读
- 消费者要读出数据，则缓冲区至少有一个单元是可读的，读出过程中该单元不可写

设信号量 ``readable`` 为生产者的私有信号量，``writable`` 为消费者的私有信号量，``mutex`` 为公有信号量

则：

.. code-block:: none

    // 生产者
    P(writable)
    P(mutex)
    写入缓冲区
    V(mutex)
    V(readable)

    // 消费者
    P(readable)
    P(mutex)
    读出数据
    V(mutex)
    V(writable)

.. note::

    一般情况下，由于 V 原语是释放资源的，所以可以以任意次序出现，但是 P 原语若次序混乱则可能造成进程间的死锁。

进程通信
****************************************

进程间通信一般有以下几种方式：管道、消息队列、信号量、共享内存、套接字、DBus [#]_

.. [#] `进程间的五种通信方式介绍 <https://www.cnblogs.com/zgq0/p/8780893.html>`_

进程调度
****************************************

**先来先服务** （FCFS）

  - 算法思想：
  - 算法规则：等待时间越久的优先服务。
  - 作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度，考虑的是哪个- 进程先进入就绪队列。
  - 是否可抢占？ 非抢占式
  - 优点：公平，算法实现简单
  - 缺点：对于排在长作业后的短作业，用户体验不好。平均带权周转时间大，对于长作业有利，对于短作业不利
  - 是否会导致饥饿？ 不会

**短作业优先**

  - 算法思想：追求更少的平均等待时间
  - 算法规则：短进程/作业优先得到服务
  - 作业/进程调度：
  - 是否可抢占？
     - 非抢占式（SJF）：每次选择当前已到达的并且运行时间最短的作业/进程
     - 抢占式（SRNT最短剩余时间优先算法):

  每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。平均等待时间和平均周转时间优于非抢占式。

  - 优点：最短的平均等待时间，平均周转时间
  - 缺点：对于短作业有利，对于长作业不利
  - 是否会导致饥饿？会，如果源源不断地有短作业进来，可能导致长作业长时间得不到服务，产生饥饿现象，如果一直得不到服务，会导致作业饿死。

**优先级调度算法**

  - 算法思想：根据任务的紧急程度来决定处理顺序
  - 算法规则：根据优先级是否可以发生改变分为静态优先级和动态优先级。

  动态优先级：如果某个进程在就绪队列中等待了很长时间，可以适当提高优先级。

  .. note::

      通常情况下，系统进程优先级高于用户进程，前台进程优先级高于后台进程。操作系统更偏好I/O型进程（或者称为I/O繁忙型进程）


  - 作业/进程调度：均适用。甚至还会用于I/O调度
  - 是否可抢占？ 非抢占式、抢占式均有。
  - 优点：灵活调整偏好程度。适用于实时操作系统
  - 缺点：若源源不断的高优先级进程到来，低优先级进程会导致饥饿。
  - 是否会导致饥饿？会

**多级反馈队列调度算法**

  - 算法思想：对其他算法的权衡
  - 算法规则：

      - 设置多级就绪队列，各个队列的优先级从高到低，时间片从小到大。

      - 新进程到达时先进入第1级队列，按照FCFS原则排队等待被分配时间片。若时间片用完进程还未结束则进程进入下一级队列队尾，如果此时已经在最下级的队列，则重新返回到最下一级队列的队尾。

      - 只有K级队列为空时，才会给K+1级分配时间片。

      - 被抢占处理机的进程重新返回原队列队尾。

  - 作业/进程调度：用于进程调度
  - 是否可抢占？ 抢占式
  - 优点：对各类进程相对公平（FCFS）；每个新到来的进程都可以很快得到相应(RR)；短进程只用较少的时间就可以完成(SPF)；不必实现估计进程的时间；灵活地调整对各种进程的偏好程度
  - 缺点：
  - 是否会导致饥饿？会

线程
****************************************

线程共享的进程环境包括：

   进程代码段、进程的公有资源（如全局变量）、进程打开的文件描述符、消息队列、信号的处理器、进程的当前目录、进程用户ID、进程组ID

线程独占资源：

   线程ID、寄存器组的值、用户栈、内核栈（在一个进程的线程共享堆区（heap））、错误返回码、线程的信号屏蔽码、线程的优先级