操作系统原理——第4章

Chapter 4 进程管理

4.1 进程的概念

定义：程序在并发环境下在一个数据集下的一次运行过程。

特征：

• 动态性：是程序的一次执行过程，其动态产生和消亡。
• 并发性：进程可以同其他进程一起向前推进。
• 异步性：进程按照各自速度向前推进。
• 独立性：进程是系统分配资源和调度CPU的单位。

一个程序可能有多个进程对应。

• 进程是动态的，程序是静态的
• 进程是暂存的，程序是长久的

4.2 进程的状态和转换

进程的3个基本运行状态：

• 运行状态：进程占用CPU正在CPU上运行的状态。
• 就绪状态：进程已经可以运行但是还没有获得CPU，暂时还无法运行的状态。
• 阻塞状态：进程因为缺少某个运行所需的必要条件（资源或信号）而进入等待的状态，如IO操作等。

进程状态的改变：

• 运行→阻塞：需要等待信号、服务结束或某个资源时
• 阻塞→就绪：信号到来、服务结束或所需资源有空闲
• 就绪→运行：通过进程调度使得该进程获得了CPU
• 运行→就绪：CPU被抢占

扩展进程状态：

• 新建状态：操作系统创建进程的过程，创建完毕后进入就绪状态。
• 终止状态：进程退出后的状态，虽不能运行但仍保留一些信息。只能由运行状态转换而来。

具有挂起和解挂操作的进程状态：

• 将就绪状态拆分为静止就绪和活跃就绪状态，将阻塞状态拆分为静止阻塞状态和活跃阻塞状态。处于静止状态时表示挂起状态，便于操作系统进行资源调度。
• 运行→静止就绪，活动就绪→静止就绪，活动阻塞→静止阻塞：进程挂起
• 静止就绪→活跃就绪，静止阻塞→活跃阻塞：解挂
• 静止阻塞→静止就绪：期待活动完成

4.3 进程控制块——PCB

进程控制块至少应该包含以下信息：

• 进程ID（PID）：标识进程的编号
• 进程起始地址：进程的可执行映像在内存（物理内存）中的起始地址
• 进程状态：当前状态
• 优先级：进程优先级别，用于进程调度
• CPU现场保护区：发生中断时对CPU状态的拷贝区，便于下一次将进程加载进CPU继续执行
• 进程间通信区：记录进程之间通信的控制信息、信号和信息缓冲区
• 资源列表：进程拥有的资源清单，主要为外设的占用信息
• 文件列表：进程打开的文件列表
• 内存列表：进程占用的内存空间（虚拟空间和物理空间）

创建进程时创建PCB，进程撤销时PCB应该同时撤销。

4.4 Linux进程控制块——task_struct

进程状态：

• TASK_RUNNING：运行态和就绪态。
• TASK_UNINTERRUPTIBLE：不可中断，不可被其他进程通过信号和时钟中断唤醒，只有资源得到满足才会进入就绪状态，一般非常短暂。
• TASK_INTERRUPTIBLE：可以被其他进程通过信号和时钟中断唤醒。
• TASK_ZOMBIE：进程终止执行，释放大部分资源。
• TASK_STOPPED：进程被挂起。

ps命令：可查看当前进程状态
ps aux，输出有多行。其中STAT行表示进程状态，字段含义：

• R：TASK_RUNNING
• S：TASK_INTERRUPTIBLE
• I：空闲
• Z：TASK_ZOMBIE
• D：TASK_UNINTERRUPTIBLE
• T：TASK_STOPPED/TASK_TRACED，停止或被调试

task_struct中的重要字段：

• 进程状态
• 进程调度信息
• 标识符：包含自身的ID（getpid()获取）、父进程ID（getppid()获取）、进程组ID
• 进程通信信息
• 链接信息
• 时间和计时器
• 文件系统
• 虚拟内存信息
• 处理器信息/现场保留区
• 进程链表：struct *next_task, prev_task，所有进程在一个双向链表之中。

4.5 进程基本控制

4.5.1 进程创建

参数：进程标识、优先级、进程起始地址、CPU初始状态、资源清单等
步骤：

• 分配PCB
• 分配并赋值PID
• 分配内存空间
• 初始化PCB（CPU状态、内存、优先级、进程状态、链表队列）
• 插入相应的进程队列
• 调度程序

4.5.2 进程阻塞

当需要等待外设IO操作、等待系统服务完成、等待请求资源、等待其他进程的约束、服务进程没有新任务可做时进行阻塞。
步骤：

• 进程停止运行（需要保存现场等）
• 修改PCB状态
• 插入相应阻塞队列
• 调度程序

4.5.3 进程唤醒

时机与进程阻塞相反。
步骤：

• 修改PCB状态
• 插入相应就绪队列
• 调度程序

4.5.4 进程撤销

终止此进程的运行。
步骤：

• 在队列中查找该进程
• 获取进程状态
• 如果该进程正在运行则立即终止
• 释放进程资源
• 将进程从队列中移除

4.5.5 原语

进程控制涉及底层的操作，为提高系统的稳定性和效率，进程操作由操作系统内核完成，且加以特殊保护。

原语是由若干条指令组成的一段小程序，用于实现某个特定操作，原语具有不可分割性，要么全部运行成功，要么彻底失败，执行过程不可中断。一个操作如果为原语则称该操作具有原子性，称该操作为原子操作。

主要的控制原语除了上述的创建原语、撤销原语、阻塞原语、唤醒原语外还包括挂起原语、激活原语等。

4.6 Windows进程控制

windows创建进程可以使用多个API实现：

• system
• WinExec
• ShellExecute
• CreateProcess，前面3个最终都需要调用CreateProcess

CreateProcess有很多参数，其中包含可执行程序名、程序参数、执行选项等。其执行步骤：

• 创建进程内核对象，创建虚拟地址空间
• 装载exe文件和dll文件到虚拟内存中
• 创建主线程和线程内核对象
• 启动主线程，进入主函数

结束进程：

• ExitProcess
• TerminateProcess

4.7 Linux进程控制

4.7.1 Linux进程分类

用户在Linux中执行一条命令就是创建了一个新的进程。

Linux进程可分为交互式进程、批处理进程、实时进程、守护进程等。

4.7.2 Linux进程创建

Linux中可以使用fork函数创建一个进程。创建出来的进程是一个子进程，创建进程的进程即为父进程。这里的子进程是父进程的复制，父进程和子进程并发运行。

fork函数的返回值是一个整数，表示进程号。在子进程中，该函数返回的值为0，父进程中返回一个大于0的值，如果创建进程错误则返回-1。在fork函数之后可以通过判断fork函数返回值的方法实现父进程和子进程分别执行不同的代码，让二者执行的分支不同。

4.7.3 fork函数实现过程

fork函数的执行流程：

• 分配task_struct结构体
• 拷贝父进程，复制正文段、数据段以及系统数据段（复制父进程task_struct的大部分内容，而修改小部分内容）
• 将新进程的task_struct保存到队列中
• 新进程置于就绪状态

fork函数的特殊机制：写时复制（COW），即父进程的资源被设置为只读，当父进程或子进程试图修改某些内容时，内核才在修改前对部分内容进行拷贝。

fork函数的实际开销主要就在于复制父进程页表以及给子进程创建PCB。

Linux启动的第一个进程是init进程（进程号为1），其余进程均为init的子孙进程。

4.7.5 execve函数创建进程

exec族函数可用于在子进程空间指定要执行的可执行程序。

首先根据文件名找到可执行程序，然后将可执行程序的内容填充入子进程的地址空间中。若exec调用成功则进入新的进程不再返回，若调用失败则继续从调用点向下进行。

除了execve外，还有execl、execlp、execle、execv、execvp等。

4.7.6 Linux进程撤销

exit函数用于终结此进程，终结进程后需要释放资源并向父进程报告。终结该进程后，该进程变成僵尸状态，保留部分PCB信息供wait函数进行收集。

进程结束时可调用schedule函数选择新进程运行。

4.7.7 Linux的wait()函数

wait函数用于进行进程的阻塞，通过wait函数可以阻塞自身，其会监测是否有子进程结束，如果没有则一直阻塞，如果有则停止阻塞，收集该结束的子进程信息并将其彻底终止，返回。wait函数有一个整型参数int& status接收子进程退出时的退出代码。若忽略子进程退出信息则参数填NULL。

sleep函数也可以用于进程阻塞，阻塞当前进程暂停执行多少秒，系统暂停调度该进程。

4.8 线程

4.8.1 线程概念

线程是进程内部的一个相对独立的运行路径，一个进程可以有多个线程。线程是进程内创建的可运行模块，能够执行指定的任务。线程和线程之间可以并发进行。

在具有线程概念的操作系统中，线程是操作系统进行调度的最小单位，如windows系统。

• 线程能够提高系统的并发性能，其并发粒度比进程更细，能够充分发挥CPU的性能。
• 线程的应用成本更低，更灵活。进程为线程提供地址空间和资源，线程与线程之间的通信比进程之间更加灵活。
• 大多数操作系统都采用了线程技术。

下面场景适用多线程：

• 多个功能需要并发
• 需要改善窗口交互性
• 需要改善程序结构
• 多核CPU之间的应用

现代操作系统中，进程=资源集+线程组。

线程的缺点：难以调试，容易造成线程安全问题，并发过程难以控制。

4.8.2 Windows线程

windows中可以通过CreateThread函数创建线程，并为其指定一个任务。

4.9 进程相互制约关系

4.9.1 互斥关系

在进程运行过程中互相排斥地访问一个具有独占性的公共资源，必须协调各个进程对资源的存取顺序，确保没有任何两个或两个以上的进程同时进行资源存取。

将一次只允许一个进程独占访问的资源称为临界资源，访问临界资源的代码段称为临界区。

4.9.2 同步关系

合作进程中某些操作之间需要满足某种先后关系或某个操作能否进行取决于某个前提条件是否满足，否则只能等待。互斥关系是特殊的同步关系。

4.9.3 同步机制

有效的同步机制满足：

• 当进程即将要执行的某个操作的运行条件不满足时，能够让该进程立即暂停执行该操作。
• 当被暂停的操作的运行条件满足时，相应进程能够被尽快唤醒以便继续运行。
• 同步机制在实现上也属于原子操作。

有关于多个进程不能同时访问临界区的问题，在硬件上可以通过中断屏蔽来完成，进入临界区时关中断，离开临界区时开中断。在软件上可以通过锁和信号量来解决。

4.10 锁

4.10.1 临界资源和临界区

4.10.2 锁的概念

锁机制通过设置标志来标识临界区是否可以进入或临界资源是否可用。如果为不可用状态，则程序在临界区之外进行等待，若为可用状态，则进入临界区并将临界资源设置为不可用状态。

上锁操作：检测锁S的状态，如果S=0则返回继续检测，如果S=1则设置S=0
开锁操作：将S设置为1
上锁和开锁都应该是原语。

锁可以保证临界区中最多只能有1个进程能够进入其中，在进入临界区之前执行上锁操作，在退出临界区时执行开锁操作。

设置临界区访问机制的4个原则：

• 忙则等待：临界区忙时其他的进程应该在外面等待
• 空闲让进：没有进程位于临界区时允许其他进程抢占临界区
• 有限等待：进程进入临界区的请求应该在有限时间内得到满足
• 让权等待：等待进程放弃CPU，以让其他进程有机会得到CPU

锁机制满足上面4个原则中的前三个。

4.11 信号量与P-V操作

4.11.1 信号量概念

信号量的核心数据结构是一个二元组（S,Q），其中S是一个初值非负的整型变量，Q是初始为空的队列。S可以表示某一类资源的可用数量，可以指某些条件等。当由于信号量的变化而导致某一个合作进程被阻塞，它将被挂接在队列Q中，而当信号量的变化导致满足了进程的运行条件时该进程将被唤醒，并离开队列Q。

4.11.2 P-V操作的定义

P操作指通过：

• S自减1
• 如果S大于或等于0，则函数返回，且调用者进程继续执行
• 如果S小于0，则函数返回，且调用者进程阻塞并插入到等待队列Q中，并由调度程序调度其他进程执行

S操作指释放：

• S自增1
• 若S大于0，则函数返回，且调用者进程继续执行
• 若S小于或等于0，则函数返回，调用者进程继续执行，并同时从等待队列Q中唤醒某一个等待进程

这两个操作在内核中均使用原语控制。

总结而言，P操作可能会阻塞某一个进程，V操作可能会唤醒某一个进程。对于S的初始值设置要合理。信号量实际上就是可以控制多个进程中最多可以有几个进程同时在临界区中运行。

在关键操作之前执行P操作，在关键操作之后执行V操作。

例题

1. 进程之间的互斥模型

进程之间的互斥模型几乎是必考的题型，需要理解锁与信号量控制进程之间互斥的原理。

技巧：

• 对于那些总量有限制的资源，需要定义两个信号量，一个信号量表示当前该资源剩余量，另一个信号量表示当前该资源最多还能够产生几个。
• 对于那些临界资源，临界区可能修改临界资源的值，需要加锁处理，或者使用一个初值为1的信号量代替锁。

例-1：生产者-消费者模型，一共有10个生产者生产5种资源，一个资源由2个生产者负责。另外有2个消费者，第1个消费者需要资源1、2、3循环进行操作A，第2个消费者需要资源3、4、5循环进行操作B。写出代码，实现10个生产者与2个消费者之间的进程互斥。

semaphore res1 = 0, res2 = 0, res3 = 0, res4 = 0, res5 = 0;
void producer_12(){V(res1);}
void producer_34(){V(res2);}
void producer_56(){V(res3);}
void producer_78(){V(res4);}
void producer_90(){V(res5);}
void consumer_1(){
	P(res1);
	P(res2);
	P(res3);
	A();
	
}
void consumer_2(){
	P(res3);
	P(res4);
	P(res5);
	B();
}
int main(){
	corun{
		producer_12
		producer_12
		producer_34
		producer_34
		producer_56
		producer_56
		producer_78
		producer_78
		producer_90
		producer_90
		consumer_1
		consumer_2
	}
}

例-2 某高速出口设有若干人工服务区和ETC服务区，不断有汽车从高速到达出口，其中货车只能选择人工通道，轿车可以选择人工通道也可以选择ETC通道，一辆轿车到达时优先选择ETC通道，如果ETC通道均在排队则选择人工通道。现设人工通道有1个，ETC通道有1个，要求写出代码，能够实时统计每一个通道前排队的车辆数。

int queuep = 0, queueetc = 0;
semaphore p = 1, etc = 1, mutex_p = 1, mutex_etc = 1;
void car(){
	while(true){
		if(queueetc){
			P(etc);
			P(mutex_etc);
			queueetc++;
			V(mutex_etc);
		}else{
			P(p);
			P(mutex_p);
			queuep++;
			V(mutex_p);
		}
	}
}
void person(){
	while(true){
		if(queuep > 0){
			V(p);
			P(mutex_p);
			queuep--;
			V(mutex_p);
		}
	}
}
void etc(){
	while(true){
		if(queueetc > 0){
			V(etc);
			P(mutex_etc);
			queueetc--;
			V(mutex_etc);
		}
	}
}