第二章 进程管理
2.1 前驱图和程序执行
前驱图是一个有向无循环图，记为DAG，可用于描述程序/进程之间执行的前后关系。
程序的顺序执行：在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响，一道程序执行完后另一道才开始。
特点：顺序性、封闭性、可再现性（程序的结果与运行时间无关，只与初始条件有关）
程序的并发执行：若干程序同时在系统中执行，这些程序的执行的执行在时间上是重叠的，一个程序的执行尚未结束，另一个程序的执行已经开始。
特点：间断性（程序在并发执行时，由于它们共享资源或为完成某一项任务而合作，致使在并发程序之间存在相互制约的关系）、失去程序的封闭性（程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。）、不可再现性（程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。）
进程
进程的定义：进程就是程序关于某个数据集合的一次执行过程。能够更加真实的描述并发
进程实体：程序段、相关的数据段、进程控制块PCB。
进程是指进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
注：进程与程序的主要区别
1）程序是指令的有序集合，其本身没有任何运行的含义，它是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态概念。
2）程序的存在是永久的，而进程则是有生命期的，它因创建而产生，因调度而执行，因得不到资源而暂停，因撤消而消亡。
3）程序仅是指令的有序集合，而进程则由程序段、相关数据段、进程控制块（PCB）组成。
4）进程与程序之间不是一一对应。
进程=程序+数据+PCB
如果进程中有n个进程，运行进程最多1个，最少0个；就绪进程最多n-1个，最少0个；等待进程最多n个，最少0个
进程的特征：1.结构特征（由程序段、数据段、进程控制块三部分组成）；
2.动态性（进程是程序的执行）；
3.并发性（多个进程可同存于内存中，能在一段时间内同时运行）；
4.独立性（独立运行的基本单位，独立获得资源和调度的基本单位）；
5.异步性（各进程按各自独立的不可预知的速度向前推进）；
进程的三种基本状态
就绪状态：进程已经获得除CPU外的所有资源，得到CPU，就立即可以运行
就绪队列：处于就绪状态进程所在队列
运行状态：正在运行的进程所处的状态
阻塞/等待状态：进程正等待某一事件发生（如等待输入输出完成），这时即使给它CPU也无法运行
阻塞队列：系统根据阻塞原因设置多个队列来管理处于阻塞状态的进程
五状态：创建状态（许可）、终止状态（释放）
七状态：挂起状态（暂时被淘汰出内存的进程）（引入原因：终端用户请求、父进程请求、负荷调节需要、操作系统需要）
对换（主要因素） | 操作系统要求释放更多的主存空间，以调入并执行处于就绪态的进程 |
进程控制块（PCB）：为了描述和控制进程运行系统为每个进程定义的数据结构，记录了OS所需的、用于描述进程当前情况以及控制进程运行的全部信息。
PCB的内容：
- 进程标志符：由系统创建进程时分配给进程的唯一标识号，通常为一整数，称为进程号，用于区分不同的进程。其所属用户通常也为一整数，称为用户号。
- 处理机状态（断点信息）：即处理机中各种寄存器（通用寄存器、PC、PSW等）的内容。
- 进程调度信息：记录了进程调度的相关信息（状态、优先级、事件等）。
- 进程控制信息：记录了系统对进程控制的信息（程序和数据的地址、同步机制、资源清单、链接指针）
进程控制功能包括进程的创建、撤消、阻塞与唤醒等，这些功能一般是由操作系统的内核来完成。
PCB的作用：
1.是OS对并发执行的进程进行控制和管理的根据。
2．也是系统用来感知进程存在的根据，即PCB是进程存在的唯一标志
正是由于建立了PCB，进程才成为了资源分配、CPU调度的单位
进程与PCB是一一对应的；PCB应常驻内存。
PCB表组织方式
系统把所有进程的PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表。
PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度
相同状态的进程组成一个链表，不同状态对应不同的链表
对具有相同状态的进程，分别设置各自的PCB索引表，存放这些进程PCB在PCB表中的地址。
- 链接方式
- 索引方式
2.2进程控制
● 进程控制是对系统中的所有进程实施管理
创建一个新进程、终止一个已完成的进程、终止一个因出现某事件而无法运行下去的进程、负责进程运行中状态的转换
● 进程控制一般由OS内核的原语来实现
原语：一种特殊的功能调用，它可以完成一个特定的功能（特点：不可打断，常驻内存，运行在管态）
常见原语：创建原语Create 终止原语Destory 阻塞原语Block 唤醒原语Wakeup 挂起原语Suspend 激活原语Active
Q：普通的程序可以实现进程控制吗？
A：不能，用户无法访问PCB表；不是原语操作会被打断，被中断后，程序运行状态不稳定
补充内核：
在现代OS中，常把一些功能模块（与硬件紧密相关的、常用设备的驱动程序及运行频率较高的）放在紧靠硬件的软件层次中，加以特殊保护，同时把它们常驻内存，以提高OS的运行效率，这部分功能模块就称OS的内核。内核是基于硬件的第一层软件扩充，它为系统控制和管理进程提供了良好的环境。
进程创建
1.申请空白PCB
2.为新进程分配资源 如内存
3.初始化进程控制块
4.将新进程插入就绪队列
Q：什么事件可以引起创建进程？
A：作业调度，用户登录，提供服务（打印等），应用请求（创建多个子进程，并发执行，提高速度）
进程终止
1.根据被终止进程的标识符，从PCB表中检索出该进程的PCB
2.若被终止进程处于执行状态，应立即终止执行，并置调度标志为真 （CPU空闲）
3.结束该进程所有子孙进程的执行，以防成不可控进程（类似删除文件夹）
4.将进程所拥有的资源交给父进程或系统进程
5.释放PCB
进程终止原因：正常退出、异常退出、外界干预
进程的阻塞与唤醒
阻塞：当一个进程所期待的事件还未出现时，自己调用阻塞原语将自己阻塞 （主动行为）
引起原因：请求系统服务（请求打印机）、启动某种操作（输入未完成时请求）、新数据尚未到达、无新工作可做
唤醒：当被阻塞进程所期待的事件出现时，则由有关进程调用唤醒原语将该进程唤醒
（处于阻塞状态的进程不可能自己唤醒自己，必须由合作进程用唤醒原语唤醒它）
进程的挂起与激活：系统利用对应原语进行
2.3线程
线程引入的原因：应用的需要、开销/性能的考虑
线程的开销较小：（创建一个新线程花费时间少，两个线程切换花费的时间少，线程之间相互通信不用调用内核）
线程：进程中的一个运行实体，是CPU的调度单位，有时将线程称为轻量级进程
线程的内容：程序计数器、寄存器组（不运行时需要保存上下文）、堆栈、子线程、状态（可转换）
线程共享所在进程的地址空间和其它资源，可以创建、撤销另一个线程
线程的分类 用户级线程、内核级线程、混合级线程
2.4进程同步
进程同步是指对多个相关进程在执行次序上进行协调，它的目的是使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性；或系统中诸进程之间在逻辑上的相互制约的关系（直接的-同步；间接的—互斥）。
用来实现同步的机制称为同步机制。如：信号量机制；管程机制。
进程互斥
由于各进程要求使用共享资源（变量、文件等），这些资源需要排他性使用。各进程之间竞争使用这些资源，这一关系称为进程互斥。
临界资源（互斥资源、互斥变量）：系统中某些资源一次只允许一个进程使用
临界区（互斥区）：在进程中涉及到临界资源的程序段叫临界区
使用原则：空闲让进、忙则等待、有限等待、让权等待
- 要进入临界区的若干进程必须满足：
（1）一次只允许一个进程进入临界区
（2）任何时候，处于临界区的进程不得多于一个
（3）进入临界区的进程要在有限的时间内退出
（4）如果不能进入自己的临界区，则应让出处理机资源
- 解决临界区（互斥）问题的方法：P-V操作
进程同步
指系统中多个进程中发生的事件存在某种时序关系，需要共同合作完成一项任务（一个进程需要另一个进程唤醒）
生产者、消费者问题 ★★★
问题描述：1.一个或多个生产者 生产某种类型的数据放置在缓冲区中
2.有消费者从缓冲区中取数据，每次取一项
3.只能有一个生产者或消费者对缓冲区进行操作
要解决的问题：
1.当缓冲区已满时，生产者不会继续向其中添加数据
2.当缓冲区为空时，消费者不会从中移除数据
参考代码：
生产者()
{
i=0;
while(1)
{
//生产产品；
P(mutex);
//往buffer[i]放产品
i=(i+1)%n;
V(mutex);
V(full);
}
}
消费者()
{
while (1)
{
P(full);
P(mutex);
//从Buffer[j]取产品
j=(j+1)%n;
V(mutex);
//消费产品
}
}生产者()
{
i=0;
while(1)
{
//生产产品；
P(mutex);
//往buffer[i]放产品
i=(i+1)%n;
V(mutex);
V(full);
}
}
消费者()
{
while(1)
{
P(full);
P(mutex);
//从Buffer[j]取产品
j=(j+1)%n;
V(mutex);
//消费产品
}
}
因有M个生产者，N个消费者，会对有界缓冲区进行操作，必须互斥使用，需设置一个互斥信号量mutex，初值为1.
<可设置两个同步（资源）信号量：分别代表空缓冲区数目（初值为缓冲区大小）和已用缓冲区数目（初值为0）>
2.5 信号量机制
信号量就是OS提供管理共有资源的有效手段；信号量代表可用资源的实体的数量
整型信号量 未遵循“让权等待”导致“忙等”。
定义为一个整型量，除初始化外，由两个标准原子操作Wait(S)（P操作）和singal(S)（V操作）来访问
P,V操作是原子操作，不可中断！
记录型信号量
记录型信号量机制采取“让权等待”策略，避免了整型信号量出现的“忙等”现象。
实现：一个用于代表资源数目的整型变量value，一个用于链接所有阻塞进程的进程链表queue
P操作：申请资源，减量操作 s.value=s.value-1;当s.value<0时，表示资源分配完，进行自我阻塞
V操作：释放资源，增量操作 s.value=s.value+1;当s.value<=0时，唤醒s.queue中的等待进程
value>0:代表可用资源数量 value<0：代表由于申请资源而阻塞的进程
AND型信号量
将进程在整个运行过程中所需要的所有临界资源，一次性全部分配给进程，待进程使用完后再一起释放。只要有一个资源未能分配给进程，其它所有可能分配的资源也不分配给该进程。从而可避免死锁发生。在wait操作中，增加了一个“AND”条件，故称为AND同步。
信号量集
<一次需要N个某类临界资源时，就要进行N次P操作--低效又可能死锁>
同时需要多个资源、每种占用的数量不同、且可分配的资源还存在一个临界值时的信号量处理，在一次原语操作中完成所有的资源申请。
一般“信号量集”未必成对使用 如：一起申请，但不一起释放
swait(s,d,d)表示每次申请d个资源，少于d个时不分配
经典进程的同步问题
在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中有代表性有：
- 生产者—消费者问题
- 哲学家进餐问题
- 读者—写者问题
2.6管程机制
信号量机制的缺点：进程自备的同步操作，P(S)和V(S)操作大量分散在各个进程中，不易管理，易发生死锁。
解决方法：引入管程：为每个共享资源设立一个“秘书”来管理对它的访问，一切来访者都要通过秘书，而秘书每次仅允许一个来访者（进程）来访问共享资源。这样既便于系统管理共享资源，又能保证进程的互斥访问和同步（封装同步操作，隐蔽细节，简化调用）
管程：由关于共享资源的数据结构及在其上操作的一组过程组成。进程只能通过管程中的过程来间接地访问管程中的数据。
管程解决的问题：互斥、同步
管程是互斥进入的，设置条件变量及等待/唤醒操作已解决同步问题（可让一个进程或管程在条件变量上等待（此时，应释放管程的使用权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒）
管程通常用于管理资源，管程中有进程等待队列和相应的等待和唤醒操作
管程的几点说明：
管程（相当于围墙）把共享变量和对它进行操作的若干过程围起来。
管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量
为了保证管程共享变量的数据完整性，规定管程互斥进入，由编译程序 实现
管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作
2.7进程通信
引入原因：信号量及管程的不足：不适用多处理器的情况（解决进程间同步问题、通信问题）
基本通信方式：消息传递、共享内存、管道
1.程序并发执行为什么会产生间断性?
因为程序在并发执行过程中存在相互制约性
2.程序并发执行为何会失去封闭性和可再现性?
因为程序并发执行时，多个程序共享系统中的各种资源，资源状态需要多个程序来改变，即存在资源共享性使程序失去封闭性；而失去了封闭性导致程序失去可再现性.
3.在操作系统中为什么要引入进程概念?它会产生什么样的影响?
为了使程序在多道程序环境下能并发执行，并能对并发执行的程序加以控制和描述，而引入了进程概念.
影响: 使程序的并发执行得以实行.
4.试从动态性，并发性和独立性上比较进程和程序?
a.动态性是进程最基本的特性，可表现为由创建而产生，由调度而执行，因得不到资源而暂停执行，以及由撤销而消亡，因而进程由一定的生命期；而程序只是一组有序指令的集合，是静态实体.
b.并发性是进程的重要特征，同时也是 OS的重要特征.引入进程的目的正是为了使其程序能和其它进程的程序并发执行，而程序是不能并发执行的.
c.独立性是指进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位.而对于未建立任何进程的程序，都不能作为一个独立的单位参加运行.
5.什么是临界资源和临界区?
a.一次仅允许一个进程使用的资源称为临界资源.
b.在每个进程中，访问临界资源的那段程序称为临界区.
6.为什么进程在进入临界区之前，应先执行"进入区"代码，在退出临界区后又执行"退出区"代码
为了实现多个进程对临界资源的互斥访问，必须在临界区前面增加一段用于检查欲访问的临界资源是否正被访问的代码，如果未被访问，该进程便可进入临界区对资源进行访问，并设置正被访问标志，如果正被访问，则本进程不能进入临界区，实现这一功能的代码成为“进入区”代码；在退出临界区后，必须执行“退出区”代码，用于恢复未被访问标志.
7.在生产者－消费者问题中，如果缺少了signal(full)或 signal(empty),对执行结果会有何影响?
可见，生产者可以不断地往缓冲池送消息，如果缓冲池满，就再也放不进去.而消费者始终因wait(full)操作将消费进程直接送入进程链表进行等待，无法访问缓冲池,造成无限等待.
8.在生产者－消费者问题中，如果将两个 wait 操作即 wait(full)和 wait(mutex)互换位置；或者是将signal(mutex)与signal(full)互换位置结果会如何?
a. wait(full)和wait(mutex)互换位置后，因为 mutex在这儿是全局变量，执行完wait(mutex)，则 mutex赋值为 0，倘若 full 也为0，则该消费者进程就会转入进程链表进行等待，而生产者进程会因全局变量mutex为 0而进行等待，使full 始终为 0，这样就形成了死锁.