【操作系统概念读书笔记】进程基础知识

We all grow up. Hopefully, we get wiser. Age brings wisdom, and fatherhood changes one’s life completely. — Frank Abagnale

什么是进程

进程的概念

所有的CPU活动称为进程(process)。进程是程序执行的过程，是程序资源管理的最小单位。

在Linux中，没有进程和线程的概念（或者说进程和线程都是任务(task)的子概念），详细见Linux-Kernel Archive: Re: proc fs and shared pids

进程是执行的程序，是活动的实体(active entity)，是可执行程序的语境/上下文(the context of executable, COE)

Both threads and processes are really just one thing: a “context of execution”. Trying to artificially distinguish different cases is just self-limiting.

程序本身不是进程，程序是一个被动的实体(passive entity)，有时又被称为文本段（就是.text section，虽然程序里不止有这一个section）。显然的，进程相对于这没有生气的实体有更多的活动内容（比如堆、栈和.bss section）

既然进程是程序的活动，那么同一个程序就可以有多次活动，而这多次活动都是不同的进程。

同时，既然进程是一种语境/上下文(context)，那么它也可以作为一个环境来执行其他代码。比如python和Java虚拟机。

描述进程的状态

进程的整个运行过程从整体来看是抽象的，但是我们可以取该抽象过程的一个切片来研究，也就是进程的状态。

进程有五种状态，这五种状态随着操作系统的不同而不同：

而为了描述这五种状态，我们可以采用进程控制块（Process Control Block, PCB，或者任务控制块，Task Control Block），它从多种层面描述当前进程的状态：

通过这些描述信息，系统可以轻松地进行中断或系统调用，然后使用PCB的信息恢复如初

比如在Linux中，PCB就使用一个结构体task_struct来表示：

struct task_struct {
#ifdef CONFIG_THREAD_INFO_IN_TASK
	/*
	 * For reasons of header soup (see current_thread_info()), this
	 * must be the first element of task_struct.
	 */
	struct thread_info		thread_info;
#endif
	unsigned int			__state;

#ifdef CONFIG_PREEMPT_RT
	/* saved state for "spinlock sleepers" */
	unsigned int			saved_state;
#endif

	/*
	 * This begins the randomizable portion of task_struct. Only
	 * scheduling-critical items should be added above here.
	 */
	randomized_struct_fields_start

	void				*stack;
	refcount_t			usage;
	/* Per task flags (PF_*), defined further below: */
	unsigned int			flags;
	unsigned int			ptrace;
	// ...
	// 以下省略大概七百行

进程调度（Process Scheduling）

• 多道程序设计的目标是，无论何时都有程序运行，从而最大化CPU的利用率。
• 分时系统的目的是在进程之间快速切换CPU，以便用户在程序运行时能与其交互

为了满足这些需求，我们就需要合理地进行进程调度。

调度队列（Scheduling Queues）

进程调度经常会使用调度队列：

• 进程在进入系统时，会进入作业队列（job queue）
• 驻留在内存中的、就绪的、等待运行的进程保存在就绪队列（ready queue）
• 等待特定I/O设备的进程列表，称为设备队列（device queue）

进程在这些队列和CPU之间轮转，从而实现进程调度：

由此，我们的问题从抽象的调度问题转化为了队列的调度问题。为了合理地安排进程在他们中的轮转，我们需要一个调度器（scheduler）（或者翻译为调度程序，但是我感觉会和程序调度弄混，于是下文采用了调度器这个翻译）

调度器（Scheduler）

调度器分为两种：

• 长期调度器/作业调度器从大容量储存设备（磁盘）的缓冲池中选择进程加到内存（UNIX和Windows的分时系统通常没有长期调度程序，只是简单地把所有新进程放在内存中）
  • 比如批处理系统中，提交的经常多于可以立即执行的，这时候这些进程就会保存到（长期）缓冲池中
  • 长期调度器更类似于做一个长期的规划
  • 长期调度器需要控制多道程序程度(degree of multiprogramming，也就是内存中进程的数量)，当多道程序程度稳定的时候，创建进程的平均速度必须等于进程离开系统的平均速度
  • 长期调度器的执行并不频繁，因此，长期调度器能有更多的时间做选择，也必须认真选择
• 中期调度器/交换区（midium-term scheduler/swapping） 的核心思想是将进程从内存中移出放在交换区中，从而降低多道程序程度，之后再重新将这些进程载入
  • 将进程移出称为换出，将进程重新载入称为换入
  • 只有当内存快爆了（多道程序程度太高）的时候Swapping才比较必要
  • 
• 短期调度器/CPU调度器从准备执行的进程中选择进程，并分配CPU
  • 短期调度器更类似于做一个立即的执行
  • 短期调度器必须快（通常每100ms必须执行一次）

大多数进程可以分为两种：

• I/O密集型（I/O-bound），时间主要花费在I/O上，CPU干的事不多
• CPU密集型（CPU-bound），很少产生I/O请求，但是CPU要进行的计算很多

因此，为了让CPU不闲下来，时时刻刻有事可做，又不能让一个任务堵塞CPU太久，导致其他的任务无法执行，调度器就需要合理地安排这些进程（比如强行中断CPU密集型工作，转换为其他进程）

上下文切换/语境转移（context switch）

因为进程在调度器的控制下在调度队列和CPU间不断轮转，为了在一个进程没有执行完转换为其他进程，在之后再恢复（比如为了防止CPU密集型堵塞CPU）；还有时进程会进行中断或系统调用，CPU需要离开当前进程转而执行中断或系统调用

这时我们就需要在PCB中保存当前进程的上下文/语境（context，包括CPU寄存器、进程状态、空间管理等），切换为下一个进程（或者中断或系统调用）的上下文/语境

这种切换的效率是非常仰仗于硬件支持的，比如有一些硬件会提供多套寄存器，上下文切换只需要简单地转换使用哪套寄存器

同时，更复杂的操作系统的机制也会要求更复杂的上下文切换操作，比如一个有堆机制的操作系统需要保存的上下文肯定比没有堆机制的操作系统多且杂

进程运行控制

操作系统需要为进程的创建和终止提供一套机制

进程创建

进程在它的生存期内可能创建其他进程，其中创建者称为父进程（parent process），被创建者称为子进程（children process），由此构成一个进程的树状结构（继承树）

又因为同一个可执行文件可能有多个活动实体，也就是进程，为了区别这些进程，我们只确定进程的名字是不够的（因为有可能来源于同一个可执行文件），我们还需要给每个进程一个独特的进程标识（process identifie，也就是pid）

下面是一个典型的Linux进程/任务树，其中systemd进程是所有用户经常的根进程/父进程（在传统的UNIX系统中根进程是init，但是Linux后来采用了systemd，很多方面下和init很像，相当于init的升级版）

子进程可能是父进程的复制品，也可能加载另一个程序；它可能和父进程并发执行，也可能父进程等待子进程执行完再执行

当一个子进程创建的时候，可以直接从操作系统获取资源，也可以被限制只使用父进程的资源子集，这时父进程需要进行一定的资源分配。

在Linux下，子进程一般来说会从父进程那里继承权限、调度属性、打开的文件等（因此可以利用文件描述符来实现共享内存）

在Linux下，我们可以调用fork来产生新的进程，新的进程会得到一份父进程的内存地址空间的拷贝（因此可以很轻松地进行父子进程间的通信），然后两者都可以继续执行。

由于fork对父进程返回子进程的pid，对子进程返回0，这种差异导致可以使用分支来区分父子进程执行的任务，比如如下代码：

#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>
int main()
{
	pid t pid;
	/* fork a child process */
	pid = fork();
	if (pid < 0) { /* error occurred */
		fprintf(stderr, "Fork Failed");
		return 1;
	}
	else if (pid == 0) { /* child process */
		execlp("/bin/ls","ls",NULL);
	}
	else { /* parent process */
		/* parent will wait for the child to complete */
		wait(NULL);
		printf("Child Complete");
	}
	return 0;
}

其中子进程使用execlp（exec的变种）来将一个二进制文件载入内存空间，然后执行这个二进制文件的代码。如果子进程没有调用exec函数，那么它执行的代码就一直是父进程的拷贝（但当然可以使用分支来区别父子进程的任务，只是从整体来看，不调用exec，代码段就是一样的）

其中父进程调用wait函数阻塞自己，由wait自动分析是否当前进程的某个子进程已经退出，如果让它找到了这样一个子进程，wait就会收集这个子进程的信息，并把它彻底销毁后返回；如果没有找到这样一个子进程，wait就会一直阻塞在这里，直到有一个出现为止。

如果子进程退出，那么它就会变成一个僵尸进程，它的入口仍然会存在表中（用于确定进程执行的状态），直到父进程调用wait找到它并释放，它才会消失。如果父进程在调用wait前就退出了，在Linux中，这个子进程就变成了孤儿进程，被根进程继承，然后根进程（systemd或者init）会隔一段时间调用wait释放名下的僵尸进程，由此这个孤儿进程就有机会被释放。

而在Windows下，创建一个进程的同时必须指定它需要load的可执行文件（因此Windows API中创建进程的函数CreateProcess有不下十个参数）

#include <stdio.h>
#include <windows.h>
int main(VOID)
{
	STARTUPINFO si;
	PROCESS INFORMATION pi;
	/* allocate memory */
	ZeroMemory(&si, sizeof(si));
	si.cb = sizeof(si);
	ZeroMemory(&pi, sizeof(pi));
	/* create child process */
	if (!CreateProcess(NULL, /* use command line */
		"C:∖∖WINDOWS∖∖system32∖∖mspaint.exe", /* command */
		NULL, /* don’t inherit process handle */
		NULL, /* don’t inherit thread handle */
		FALSE, /* disable handle inheritance */
		0, /* no creation flags */
		NULL, /* use parent’s environment block */
		NULL, /* use parent’s existing directory */
		&si,
		&pi))
	{
		fprintf(stderr, "Create Process Failed");
		return -1;
	}
	/* parent will wait for the child to complete */
	WaitForSingleObject(pi.hProcess, INFINITE);
	printf("Child Complete");
	/* close handles */
	CloseHandle(pi.hProcess);
	CloseHandle(pi.hThread);
}

进程终止

当一个进程执行完了它的任务并执行exit函数，操作系统就会终止它并返回这个进程的状态码给使用wait函数等待子进程的父进程（因此如果没有调用wait，就没有人接收这个状态码，为了保证以后有机会获取状态码，子进程的入口就必须保留，这样子进程就成了僵尸进程），同时子进程的所有资源都会被释放。

除了子进程自己结束自己，在直到子进程“身份”的情况下，其他进程（通常是父进程）也可以通过适当的系统调用结束掉这个进程（比如Windows下的任务管理器）

有些操作系统不允许父进程退出时子进程还未退出，于是会在父进程退出时强行退出子进程，这个现象叫做级联终止（cascading termination）

进程间通信

两个进程可以是合作的进程，也可以是互不相干的。当两个进程进行合作时，就需要有一种进程间通信/交流（InterProcess Communication，简称IPC）的方式。

有两种常用的通信方式：

• 共享内存（shared memory）
• 消息传递（message passing）

共享内存

我们可以把协作的进程看作生产者和消费者，生产者进程生成信息，消费者进程使用信息。

生产者生成的信息可以放在共享内存中的缓冲区中，然后消费者从中获取一项使用。生产者和消费者必须同步，这样消费者才不会使用没有被生产出来的信息

有以下两种缓冲区：

• 有界缓冲区，假如缓冲区满，生产者就必须等待；假如缓冲区空，消费者必须等待
• 无界缓冲区，生产者可以一直创建新信息，而消费者可能需要等待

下面是一个有界缓冲区的代码示例：

item next produced;
while (true) {
	/* produce an item in next produced */
	while (((in + 1) % BUFFER SIZE) == out)
		; /* do nothing */
	buffer[in] = next produced;
	in = (in + 1) % BUFFER SIZE;
}

比如，POSIX系统使用内存映射文件实现共享内存对象

消息传递

可以使用操作系统提供的机制进行消息传递

为了在进程间通信，就必须建立通信链路，而为了建立通信链路，使用消息传递系统的进程必须支持以下原语：

send(message);
receive(message);

命名

为了向一个进程传递消息，我们必须知道这个进程是谁，也就是必须知道它的身份/名称

对称性直接通信

send向指定进程发件，receive从指定进程收件

这时通信链路显式且准确地在两个进程间建立了

非对称性直接通信

send向指定进程发件，receive可以从任意进程收件（发件人名称变成了变量）

以上两种直接通信的方式都丧失了模块化，某种程度上是硬编码的，要更改、维护非常困难。

间接通信

简单来说就是建立一个中间人来派发信件，这个中间人可以是邮箱或者端口

send向邮箱发件，receive可以从邮箱收件

这样两个进程之间可以有多条通信链路，一条链路也可以在多个进程间共享，这样就增加了模块化

这种间接通信依赖于中间人，因此只有两个进程共享邮箱的时候，才能建立通信链路，因此共享链路的意思也就是共享邮箱

问题来了，既然一个邮箱可以被多个进程共享，当多个进程同时向邮箱收件的时候应该怎么办呢？这取决于程序的设置或者操作系统的设置。

邮箱可以是属于进程的，也可以是属于操作系统的。如果邮箱是属于进程的，那就要区分所有者和使用者，确定收发邮件的权利；如果邮箱是属于操作系统的（某种程度上，操作系统也是一个进程），那么操作系统就要提供机制进行收发权利的授权。

比如，mach系统使用端口来进行消息传递，即便是系统调用也使用端口来传递消息（操作系统也可以看作一个进程）

而Windows使用共享内存和消息传递相结合的方式：

• 小消息通过端口传递
• 大消息创建共享内存中的区段对象传递
• 更大的不适合使用区段对象的消息，可以通过API直接访问对方的地址空间

同步

消息传递可以是阻塞/同步的或者非阻塞/异步的：

• 阻塞发送：发送进程阻塞，直到消息被接收
• 非阻塞发送：发送进程一直可以发送
• 阻塞接收：接收进程阻塞，直到有消息被发送
• 非阻塞接收：接收进程一直可以接收（没有消息就收到空消息）

缓存（消息队列）

发送的消息总是会放在（临时）消息队列中，有以下几种队列：

• 零容量，链路中不能有任何消息在等待，因此发送了就必须被接收，发送进程在发送后必须阻塞
• 有限容量，在队列满了后发送进程必须阻塞
• 无限容量，队列不会满，因此发送进程从不阻塞

显然，采取哪种缓存策略和采用哪种同步策略是密切相关的

扫码阅读此文章
点击按钮复制分享信息