---

**🎬 博主名称**：迷途之人不知返

🔥 个人专栏: 《C语言》、《数据结构》、《C++》、《Linux》

🗂️ Gitee仓库: 《C语言》、《数据结构》、《C++》、《Linux》

</> 算法专栏: 《算法精选集》

---

我们将站在操作系统的角度下，解释一些重要的进程状态：运行、阻塞、挂起。

1、运行状态

操作系统的一个重要的任务，就是获取CPU的资源。

而一个CPU，只能对应一个调度队列。(也就是说，计算机有几个CPU，未来操作系统运行时就有几个调度队列)

而这个调度队列，真的就是一个队列(queue)。进程处于调度队列的时候，我们称进程处于运行状态。

这就有点奇怪了：我们之前说task_struct对象是由双链表管理起来的，而现在怎么又说是队列管理的呢？

这时，我们就要搞清楚：内核链表到底是怎么实现的，也就是说，内核中task_struct对象到底是怎么被管理的？我们就需要搞清楚两点：

• 所有变量的地址，在数值上等于最小地址；
• Linux内核中的链表，与我们之前实现的链表的区别。

1.1、变量的地址

我们知道，CPU访问内存的基本单位是字节。而每一个字节都有一个地址来表示。

int a = 4;

&a取出的只有一个地址，而变量a为int类型，占4个字节。a占4个字节，不就应该有4个地址吗？怎么取地址的时候只返回一个地址？

其实，&a返回的地址是a拥有4个地址中数值最小的地址。int说明了a占用内存的大小，也就是偏移量，以后操作系统根据最小地址和偏移量，就能够在内存中读取完整的a变量。

对于内置类型double, float，都是这样的。

int a[10];

&a取出也只有一个地址。我们知道此时的&a取出的是整个数组的地址，而整个数组包含10个int元素，也就应该包含40个地址。道理也是类似的：

• &a返回的是最小地址；
• 数组在内存中是连续存储的；
• int说明了每个元素的大小：4字节；"10"说明了元素个数：10个；总偏移量就是40个字节；
• 以后操作系统根据最小地址和总偏移量，就能够在内存中读取完整的a数组；
• 甚至操作系统能够根据最小地址和特定的偏移量，找到数组中特定位置的元素。

struct Obj
{
	int a;
	int b;
	char c;
	double d;
};

那么对于结构体呢？也是这样的。假设我们用结构体Obj实例化一个对象x，那么&x与&(x.a)一定是一样的：

//test.cpp
#include<cstdio>

struct Obj
{
	int a;
	int b;
	char c;
	double d;
};

int main()
{
	struct Obj x;
	printf("&x: %p, &(x.a): %p\n", &x, &(x.a));
	
	return 0;
}

于是我们就可以得出一个结论，

• C/C++对于任意类型(的变量)，开辟空间的时候，变量的地址在数值上等于开辟的众多地址中数值最小的地址。

1.2、内核的通用链表

以前我们的链表，是这样实现的：

struct Node
{
	int data;
	struct Node *next;
	struct Node *prev;
};

我们实现的链表的特点是：next与prev里保存的指针，指向的是一个完整的节点。

而Linux内核中的链表是这样实现的：

struct list_head
{
	struct list_head *next;
	struct list_head *prev;
}

struct task_struct
{
	pid_t pid;
	// 其他属性...
	struct list_head link;
	// ...
};

内核链表中，每一个task_struct对象中都有一个link，

• link对象中next保存的指针，指向的是下一个task_struct对象的link；
• link对象中prev保存的指针，指向的是上一个task_struct对象的link。

这就是内核通用链表的实现方式。通用链表的特点是：next与prev里保存的指针，指向的不是一个完整的task_struct节点。

1.2.1、通过link求首地址

那么问题来了：既然内核的链表是由task_struct对象的link串联起来的，那么我们如何通过link找到整个task_struct对象呢？

我们可以细化上面的问题：

• 已知结构体内一个变量的地址；
• 已知外部包装的结构体类型；
• 要求计算出结构体对象的起始地址，进而能够访问结构体的其它变量(进程的其他属性)。

再提炼问题的本质：已知结构体内部变量的地址，求这个变量在结构体变量中的偏移量？

我们还是以结构体Obj为例：

struct Obj
{
	int a;
	int b;
	char c;
	double d;
};

比如，我们创建了一个Obj类x变量，我们知道&(x.d)，要求相对于x首地址的偏移量。

我们不妨将0强转成struct Obj*类型的地址，然后通过这个0地址，找到变量d，再取地址，求得偏移量：

地址的本质是一个十六进值数值。我们从0地址处计算出d的地址，d的地址就是从0开始加上d偏移量得来的地址，所以此时d的地址就是偏移量。

写段程序验证一下：

//test.c
#include<stdio.h>

struct Obj
{
	int a;
	int b;
	char c;
	double d;
};

int main()
{
	struct Obj x;
	long long offset = &(((struct Obj*)0)->d);
	printf("%p, %p\n", &x, (long long)&(x.d) - offset); // 转化成相同的进制，结果才是正确的	
	
	return 0;
}

1.2.2、使用通用链表的原因

为什么对于PCB对象，我们不直接使用next, prev指针，直接指向PCB节点本身，而是使用了通用链表的形式呢？

1、通用性

未来不止是进程，内核中的一切对象，都可以用通用链表管理。这样我们就没必要对于一些新的内核对象再去设计另外的数据结构，从而使代码更具通用性。

2、可以选用任意类型的数据结构进行管理

我们当前的示例，只使用了struct list_head link;这么一个链接字段，从而能够让task_struct对象被操作系统以链表的形式管理。

struct task_struct
{
	// ...
	struct list_head link; // 双链表
	struct list_head queue_link; // 队列
	struct list_head hash; // 哈希表
	// ...
};

这就使得task_struct对象既能被双链表管理，也能被队列管理，还能被哈希表管理……也就是说，未来我们想用哪种数据结构管理task_struct对象，我们就添加上对应的链接字段。意味着此时的task_struct对象就可以同时被任意类型的数据结构所管理。

2、阻塞状态

比如，我们使用了scanf函数：

// test1.c
#include <stdio.h>

int main()
{
	int a;
	scanf("%d", &a);
	printf("a: %d\n", a);
	
	return 0;
}

我们运行程序，scanf函数在等待用户输入值。由于scanf函数的作用是提取键盘输入的资源写入到内存，我们就可以说此时键盘在等待获取资源。

键盘在等待资源，那么上面程序对应的进程就处于阻塞状态。

阻塞的本质，是不调度。

对于进程，操作系统有调度队列管理，而对于硬件，操作系统也有一个专门管理硬件的等待队列。假设这个等待队列的链接字段为struct Device *next, *prev;。

操作系统根据程序创建进程，代码直到执行到scanf函数之前，进程都是处于调度队列；代码执行到scanf函数的时候，由于用户没有在键盘上写入数据，键盘就一直等待数据的获取。

操作系统察觉到键盘的等待后，就将进程从调度队列转移到(等待硬件的)等待队列，进程也就处于阻塞状态。理论上进程也包含struct Device *next, *prev;链接字段，那么这个进程也就能从调度队列滑出并进入等待队列。

也就是说，

• 进程处于调度队列，进程就处于运行状态；
• 进程处于等待队列，进程就处于阻塞状态。

3、挂起状态

如果某个计算机使用的是单核单线程CPU，那么理论上一个CPU只能执行一个进程，调度队列中的其它进程就处于所谓的“就绪状态”。

进程进入挂起状态，发生在内存资源严重不足的情况之下。

如图，(内存中载入了操作系统)操作系统创建了一些进程，构建了调度队列。

现在内存的资源严重不足了。假设操作系统认为此时的进程A并没有被CPU执行，只是在调度队列中已就绪等待CPU：

此时操作系统就会，

• 将A指向的代码和数据，拷贝入磁盘上的swap分区；
• 释放内存中A的数据和代码。

我们称此时的A数据和代码进行了换出。

当CPU执行到进程A，操作系统就将swap分区里A的代码和数据，重新加载到内存中与task_struct对象建立联系。我们称此时的A数据和代码进行了换入。

像这样，内存资源严重不足的情况下，操作系统为了保证CPU的正常执行(其实就是“嫌”A代码和数据占位置)，将一部分进程的代码和数据转移到磁盘上的swap分区，相当于进程“失去了代码和数据”，我们就称作进程挂起。

上面的情境中，

• 程序一开始处于调度队列，等待CPU的执行；
• 内存严重不足，操作系统就将等待中的进程挂起。

我们称此时的挂起为运行挂起。

当进程因为硬件等待某种资源(或其他情况)，被操作系统放入与硬件有关的等待队列；而内存资源又严重不足，操作系统就会将等待队列中进程的数据和代码换出，这就是阻塞挂起；等到硬件获取资源准备就绪，进程被重新放回调度队列并被CPU执行，操作系统就会换入代码和数据，从而能够让CPU正常执行进程。

小贴士

---

有人可能会想：既然有swap分区，内存严重不足的时候又将进程代码和数据进行换出和换入，而磁盘又相对便宜，那为什么不将swap分区做得很大，未来有很多代码和数据都可以放入swap分区，不就解决了内存不够的问题？
实际上，swap分区大小，一般是内存的0.5 ~ 1.0倍。如果swap分区变得很大，操作系统的效率就会下降。当swap分区变得很大，计算机为了保证CPU的正常执行，就会依赖swap分区，频繁地进行数据和代码的换出与换入；由于swap分区在磁盘上(外设)，频繁的换出与换入，就是频繁的I/O操作，整个系统的效率就会下降。

由于进程挂起的作用是缓解内存不足的问题，而代码与数据的换出与换入本质上是I/O操作(比较慢的事)。所以我们可以认为，挂起的本质是用时间换空间。