# 进程概念

# 1. 进程的基本概念

并发特点:运行过程不确定、结果不可再现。因此引入“进程”。

定义:是程序在某个数据集合上的一次运行活动

特征:动态性、并发性、异步性(按照各自速度推进)、独立性(系统分配资源调度CPU的单位)。

# 进程和程序的区别?

动态和静态(指令的有序集合)、暂存(内存)与长存(介质)、一个程序可能对应多个进程。

# 进程的类型

如果按照权限分类,有:

- 系统进程:系统内核相关
- 用户进程:运行于用户态进程

CPU依赖性,有:

  • CPU密集
  • IO密集

# 2. 进程状态

进程有3种状态:

- 运行状态:获得CPU,并且运行
- 就绪状态:具备运行条件,无CPU;一旦获得CPU,即可运行
- 阻塞状态(又称“等待状态”):因为等待某项服务完成或者信号(系统调用、IO操作、合作进程信号),从而不能运行

状态的迁移,如下图所示:

image-20190930155057014

# Linux中的进程状态

基本和上述一样:

  • 可运行态:就绪、运行
  • 阻塞状态
    • 浅度阻塞:能被其他进程信号或者时钟唤醒
    • 深度阻塞:不能......
  • 僵死态:进程终止,释放大部分资源
  • 挂起态:进程被挂起(比如调试)

状态的迁移,如下图所示:

image-20190930155451533

# 3. 进程控制块(PCB)

定义:描述进程状态、资源和相关进程关系的数据结构。进程创建时候会创建PCB,撤销时候也会销毁PCB。

以Linux的PCB为例,task_struct的数据结构如面2张图所示:

image-20190930160905252

# 和进程标识相关的成员变量

LINUX进程的标识:

  • PID
  • PPID:父进程的ID
  • PGID:进程组的ID

Linux进程的用户标识:

  • UID:用户ID
  • GID:用户组ID

# 进程的切换

进程的切换本质是:进程的上下文(Context、进程运行环境、CPU环境)的切换

# 进程控制

# 1. 基本概念

分为4个典型行为:创建进程、进程撤销、进程阻塞、进程唤醒

# 进程创建

功能:创建具有ID的进程

参数:优先级、CPU状态等。

过程:

  1. 创建空白PCB
  2. 获取并赋予标识符ID
  3. 为进程分配空间
  4. 初始化PCB
  5. 插入就绪队列

伪代码如下:

image-20191007165515888

# 进程撤销

功能:撤销指定进程,回收资环,撤销该进程的PCB

撤销时机:正常结束、异常结束、外界干预

过程实现:

  1. 在PCB队列中检索该PCB
  2. 获取进程状态
  3. 若进程处于运行态,立即终止该进程:对于子进程,可以使用递归策略先行撤销
  4. 释放资源
  5. 将进程从PCB移除

# 进程阻塞

功能:停滞进程执行,转变状态为阻塞。

阻塞时机:请求系统服务、新数据未到达、启动某种任务(IO)

参数:阻塞原因。因为不同原因,有不同的阻塞队列和处理策略。

过程实现:

  1. 停滞运行
  2. PCB中状态运行台=>阻塞台
  3. 插入对应阻塞队列
  4. 控制权交给调度模块

# 进程唤醒

功能:唤醒处于阻塞队列中的某个进程

参数:被唤醒的进程id

# 进程控制原语

定义:由若干个指令构成的函数,具有原子性

对于进程控制的所有过程,都必须使用原语实现。

# 2. Linux进程控制

需要用到2个函数:forkexec函数系列。

对于fork来说,就是复制一个一摸一样的子进程,父子进程并发执行,无法确定先后顺序。同时,子进程与父进程的堆栈、代码逻辑和数据完全一致。

#include <iostream>
#include <unistd.h>

using namespace std;

int main() {
  // pid_t:本质是int型
  pid_t pid = fork();
  if (pid == 0) {
    cout << "在子进程中,fork返回: 0" << endl;
  } else if (pid == -1) {
    cout << "创建失败" << endl;
  } else {
    cout << "在父进程中,fork返回子进程: " << pid << endl;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如果想让子进程和父进程拥有不同的功能怎么办?需要使用exec系列的函数。此系列函数一共有6个,但其他5个,均是 execve函数的不同程度的封装。

#include <iostream>
#include <string>
#include <unistd.h>

using namespace std;

int main(int argc, char * main_argv[]) {
  if (argc != 2) {
    cout << "Please give a number as arg1.\n";
    return 1;
  }
  // http://www.man7.org/linux/man-pages/man2/execve.2.html
	// 第2个和第3个参数都应以空指针结束的 char* const 数组
  // 第2个参数,按照惯例,第一个元素是关联的进程名(随便)
  char* const argv[] = {"ps", "ax", NULL}; 
  char* const envp[] = {"PATH=/bin:/usr/bin", NULL};
  
  int arg1 = main_argv[1][0] - '0';
  switch(arg1) {
    case 1: 
      execve("/bin/ps", argv, envp);
  }

  return 1;
}
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

其他5个函数,如下所示:

img

# 线程

# 1. 线程概念

  • 可以由CPU直接运行的实体
  • 1个进程可以创建多个线程
  • 多个线程可以共享CPU,实现并发

# 2. 适用场景

  • 程序多个功能并发进行。比如暴风影音中,并发功能有:视频解码、音频解码、网络接受视频数据。
  • 交互性高的程序。比如大量计算和交互性,采用主从的思路。
  • 改善程序结构
  • 多核CPU上,发挥多核的作用

在linux里面,线程相关操作都放在了pthread.h中,并且编译的时候需要链接静态库。

线程创建函数:int pthread_create(pthread_t *restrict tidp,const pthread_attr_t *restrict_attr,void*(*start_rtn)(void*),void *restrict arg);

返回值:若成功则返回0,否则返回出错编号

参数

  • 第一个参数为指向线程标识符的指针。
  • 第二个参数用来设置线程属性。
  • 第三个参数是线程运行函数的地址。
  • 最后一个参数是运行函数的参数。

示例代码如下:

#include <iostream>
#include <unistd.h>
#include <pthread.h>

using namespace std;

// 传递给线程函数的参数
struct member {
  int num;
  string name;
};

static void *pthread(void *arg) {
  struct member *temp;
  cout << "线程开始运行!" << endl;

  // no2:继续主线程运行
  sleep(2);

  temp = (struct member *)arg;
  cout << temp->num << endl;
  cout << temp->name << endl;

  return NULL;
}

int main(int argc, char *argv[]) {
  pthread_t ph;
  struct member *b;

  b = (struct member *)malloc(sizeof(struct member));
  b->num = 1;
  b->name = "name";
  
  if ((pthread_create(&ph, NULL, pthread, (void*)b)) == -1) {
    cout << "线程创建时失败" << endl;
    return 1;
  }
  // no1:先让线程运行
  sleep(1);
  // no3:
  cout << "主线程继续运行\n";
  // no4: 阻塞主线程,一直等待直到被等待的线程结束与资源回收为止。
  if (pthread_join(ph, NULL)) {
    cout << "线程为退出" << endl;
    return -2;
  }

  return 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
46
47
48
49
50

# 临界区和锁

# 1. 临界资源和临界区

临界资源:一次只允许一个进程独立访问的资源

临界区:进程中访问临界资源的程序段

例如对于下面的程序A和B,i是内存全局变量,A和B中修改了i。如果并发执行,不做任何措施,那么输出结果不确定:

int i;
// 程序A
i = 100;
cout << "i is " << i << endl;
// 程序B
i = 200;
cout << "i is " << i << endl;
1
2
3
4
5
6
7

需要将展示的程序A和B的区域,设置为临界区,不允许多个进程同时进入临界区。

设计临界区访问机制,需要遵循4个原则:

  • 忙则等待
  • 空闲让进
  • 有限等待:进程进入临届区的请求,应该在有限时间内满足
  • 让权等待:等待进程放弃CPU,让其它进程有机会得到CPU。一直询问,浪费资源。

# 2. 锁机制

上锁步骤:

  1. 检测锁S的状态(0或者1)
  2. 如果S=0,返回第1步
  3. 如果S=1,则S=0

开锁步骤:

1. S=1

⚠️:在操作系统中,上锁和开锁都使用原语实现。

锁机制访问临界区的步骤:

  • 初始化锁状态:S=1
  • 进入临界区前:LOCK(S)
  • 离开临界区:UNLOCK(S)

所以之前的程序,可以实现临界区的互斥访问:

int i;

// 程序A
LOCK(S);
i = 100;
cout << "i is " << i << endl;
UNLOCK(S);

// 程序B
LOCK(S);
i = 200;
cout << "i is " << i << endl;
UNLOCK(S);
1
2
3
4
5
6
7
8
9
10
11
12
13

# 同步和PV操作

# 1. 同步和互斥

互斥关系指:多个进程共享独占性资源(临界资源),确保没有任何大于等于2个的进程同时进行存取操作(临界区操作)。

同步关系指:一个进程在执行某个操作,要求另一个进程必须完成另一个操作,否则前面的进程只能等待。互斥关系是一种特殊的同步关系。

# 2. P-V操作

P、V是荷兰语:Passeren是通过,Vrijgeven是释放。

# 信号灯

定义:它是一种进程同步机制。进程在运行过程中,受信号灯状态控制,并能改变信号灯状态。

数据结构

  • 二元矢量(S, q)
  • S信号量:整数,初值为负
  • q:PCB队列,初值为空集合

P操作的伪代码如下:

P(S, q) {
  S = S - 1;
  if (S < 0) {
    // 如果S的值为负数,将此进程加入队列,并且阻塞此进程,转入调度函数
    Insert(Caller, q);
    Block(Caller);
    转入调度函数();
  }
}

main() {
  // ...
  P(S, q); // 进程可能会在P操作处阻塞
  // ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

V操作的伪代码如下:

V(S, q){
  S = S + 1;
  if (S < 0) {
    // 如果S为负数,那么从队列中移出一个进程,并且唤醒被移出的进程
    Remove(q, pid); 
    Wakeup(pid);
  }
}
// 调用V操作,并不会造成阻塞
1
2
3
4
5
6
7
8
9

# 3. P-V解决互斥问题

实现过程:进入临界区前,执行P操作;离开之后,执行V操作。重要的是:S初值要合理

举个例子,假如有a、b、c三个并发线程:

int mutex = 1;
// a
Pa() {
  p(mutex);
  // 临界区
  v(mutex);
}

// b
Pb() {
  p(mutex);
  // 临界区
  v(mutex);
}

// c
Pc() {
  p(mutex);
  // 临界区
  v(mutex);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

假设一种情况如下:

  1. 刚开始进入一个线程,假设是a,那么mutex更新为0,a继续执行;
  2. 假设b跟进、a未出临界区,那么mutex更新为-1,b进入调度队列,并且阻塞,等待唤醒;
  3. c跟进,mutex更新为-2,c进入调度队列,并且阻塞,等待唤醒;
  4. a执行完,根据策略选择唤醒一个线程,假设唤醒b;
  5. b被唤醒,执行完临界区操作,执行v操作,唤醒c。

在上面的第2步中,如果a出了临界区,此时b、c都没运行到临界区,那么也可以走通流程。可以自行模拟。

如果将mutex设置为0,那么会锁死,3个进程都无法进行;如果设置成2,那么无法保证互斥。