进程管理

进程的基本概念

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

进程有以下几个特征：

  • 进程可以并发执行

  • 进程是一个独立调度的活动

  • 进程在执行任务时需要分配和释放资源

进程和程序有以下区别：

  • 程序是一个静态概念，是指令的有序集合，没有执行含义；进程是一个动态概念，是程序的执行过程，动态地被创建并消亡。

  • 程序不反应执行过程，因而没有并发特征；进程具有并发特征

  • 不同的进程可以包含同一个程序，只要程序对应的数据集不同即可。

进程的描述

进程的状态：

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

进程互斥

使用信号量实现进程互斥

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

  • 进入临界区前执行 P 原语

  • 退出临界区后执行 V 原语

伪代码如下：

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

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

参见

进程同步

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

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

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

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

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

使用信号量实现进程同步

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

同样以上面的例子为例：

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

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

提示

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

  • 进程互斥时的信号量又被称为 公有信号量，P、V 原语可以被任意进程调用

生产者-消费者问题

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

  • 设有一有界缓冲区，向缓冲区写入数据者为生产者，向缓冲区读出数据者为消费者

  • 生产者要写入缓冲区，则缓冲区至少有一个单元是可写的，写入过程中该单元不可读

  • 消费者要读出数据，则缓冲区至少有一个单元是可读的，读出过程中该单元不可写

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

则：

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

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

备注

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

进程通信

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

1

进程间的五种通信方式介绍

进程调度

先来先服务 （FCFS）

  • 算法思想：

  • 算法规则：等待时间越久的优先服务。

  • 作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度，考虑的是哪个- 进程先进入就绪队列。

  • 是否可抢占？ 非抢占式

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

  • 缺点：对于排在长作业后的短作业，用户体验不好。平均带权周转时间大，对于长作业有利，对于短作业不利

  • 是否会导致饥饿？ 不会

短作业优先

  • 算法思想：追求更少的平均等待时间

  • 算法规则：短进程/作业优先得到服务

  • 作业/进程调度：

  • 是否可抢占？

    • 非抢占式（SJF）：每次选择当前已到达的并且运行时间最短的作业/进程

    • 抢占式（SRNT最短剩余时间优先算法):

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

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

  • 缺点：对于短作业有利，对于长作业不利

  • 是否会导致饥饿？会，如果源源不断地有短作业进来，可能导致长作业长时间得不到服务，产生饥饿现象，如果一直得不到服务，会导致作业饿死。

优先级调度算法

  • 算法思想：根据任务的紧急程度来决定处理顺序

  • 算法规则：根据优先级是否可以发生改变分为静态优先级和动态优先级。

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

备注

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

  • 作业/进程调度：均适用。甚至还会用于I/O调度

  • 是否可抢占？ 非抢占式、抢占式均有。

  • 优点：灵活调整偏好程度。适用于实时操作系统

  • 缺点：若源源不断的高优先级进程到来，低优先级进程会导致饥饿。

  • 是否会导致饥饿？会

多级反馈队列调度算法

  • 算法思想：对其他算法的权衡

  • 算法规则：

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

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

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

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

  • 作业/进程调度：用于进程调度

  • 是否可抢占？ 抢占式

  • 优点：对各类进程相对公平（FCFS）；每个新到来的进程都可以很快得到相应(RR)；短进程只用较少的时间就可以完成(SPF)；不必实现估计进程的时间；灵活地调整对各种进程的偏好程度

  • 缺点：

  • 是否会导致饥饿？会

线程

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

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

线程独占资源：

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