正在上，计算机网络没坚持下来，操作系统一定。
适用计算机操作系统（OS）（第四版）
自己的学习笔记，PPT及图片来源网络及自己老师，侵删。

第二章进程的描述与控制

2.1 前趋图和程序执行

2.1.1 前趋图

前趋图是一个描述程序执行先后顺序的有向无循环图。
初始结点 ：没有前趋的节点。
终止结点 ：没有后继的节点。
重量 ：该节点所含有的程序量或程序的执行时间。
前趋图中不允许有循环存在。

2.1.2 程序顺序执行

仅当前一操作(程序段)执行完后，才能执行后继操作。

顺序执行的特征：
1）顺序性：仅当前一操作(程序段)执行完后，才能执行后继操作。
2) 封闭性：程序运行时，资源的状态只有本程序才能改变，一旦开始执行，其执行结果不受外界的影响。
3) 可再现性 ：只要环境与初始条件相同，重复执行时一定会得到相同的结果。

2.1.3 程序并发执行

并发：占用某一个资源。
并行：竞争不同资源。
并发执行的前趋图：

并发执行时的特征：
1)间断性 ：并发执行的程序之间形成了相互制约的关系，导致并发程序的执行具有“执行——暂停——执行”的活动规律。
2)失去封闭性 ：其中任一程序执行时，其环境都必然会受到其他程序的影响。
3)不可再现性: 由于失去了封闭性，导致其失去了可再现性。

直接制约：由任务本身而决定，无法改变。
间接制约：由外部资源而决定（竞争同一类资源）

2.2 进程的描述

2.2.1 进程的定义和特征

进程 ：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

• 组成：程序段、数据段和进程控制块(PCB)组成了进程实体。

• 程序和数据是进程存在的物理基础，是进程的实体

• 进程控制块是进程的灵魂，是进程存在的唯一标志

• 操作系统为进程创建进程控制块和分配地址空间的过程就是进程创建的过程。

• 进程控制块（PCB）：是操作系统用来记录进程详细状态和相关信息的基本数据结构，包括进程的标识信息、状态信息和控制信息。

  • 标识信息：唯一的标识一个进程。
  • 状态信息：与CPU有关的各种现场信息，以便该进程重新占用CPU后能够继续执行。
  • 控制信息：操作系统对进程进行调度管理时用到的信息。

  PCB是进程的灵魂，是进程存在的唯一标志

• 程序与进程的区别：

  • 程序是静态的，进程是动态的;
  • 进程具有并发特征,而程序没有;
  • 进程是系统分配调度的独立单位，能与其他进程并发执行;
  • 一个程序对应多个进程，一个进程为多个程序服务

• 进程的特征 ：
  1）结构特征 ：PCB。
  2 ）动态性 ：进程实体具有一定的生命周期，进程实质是进程实体的执行过程。
  3 ）并发性 ：指多个进程实体同时存在于内存中，且能在一段时间内同时运行。
  4 ）独立性 ：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。
  5 ）异步性 ：进程是按异步方式运行的。

2.2.2 进程的基本状态及转换

进程的三种基本状态 :
1）就绪 : 万事俱备,只差CPU。
2）执行 ：已经获得CPU，正在执行。
3）阻塞 ：正在执行的进程由于发生某事件，暂时无法继续执行时的状态。

计入两种常见状态 ：创建与终止。

2.2.3 挂起操作与进程状态的转换

挂起 ：因为各种原因，进程由内存转到外存。
激活 ：把正在挂起的进程由外存转入内存。
主要是为了解决内存空间不足的问题。

2.2.4 进程控制块

进程控制块的作用：
是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。

1）作为独立运行基本单位的标志
2）能实现间断性运行方式
3）提供进程管理所需要的信息
4）提供进程调度所需要的信息
5）实现与其它进程的同步与通信

进程控制块中的信息 ：
1 ）进程标识符 ：内部标识符与外部标识符。
2 ）处理机状态 ：通用寄存器、指令计数器、程序状态字PSW、用户栈指针
3）进程的调度信息 ：进程状态、进程优先级、进程调度所需的其它信息、事件
4）进程控制信息 ：程序和数据的地址、进程同步和通讯机制、资源清单、链接指针。

进程控制块的组织方式 ：
1） 线性方式
2）链接方式
3）索引方式

2.3 进程控制

2.3.1 操作系统内核

进程管理中最基本功能是进程控制
进程控制任务：
进程的创建、终止、进程状态的转变等

原语：由若干条指令组成，用于完成一定功能的一个过程。

• 是一个不可分割的基本单位
• 在管态（系统态)下执行，常驻内存。
• 在执行过程中不允许被中断，因此是顺序的而不可能是并发的。

进程的创建 ：
(1) 申请空白PCB。
(2) 为新进程分配资源。
(3) 初始化进程控制块。
(4) 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程， 便将新进程插入就绪队列。

进程的终止 ：
(1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
(2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
(3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。
(4) 将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统。
(5) 将被终止进程(它的PCB)从所在队列(或链表)中移出， 等待其他程序来搜集信息。

2.4 进程同步

2.4.1 进程同步基本概念

两种形式的制约关系 ： 间接相互制约（因为资源不足）与直接相互制约（为了完成某一个任务）。

进程的同步 ：需要相互合作、协同工作的进程之间的相互关系。
进程的互斥 ：当两个或两个以上进程竞争同一临界资源时，进程间的制约关系
临界资源 ：指在一段时间内只允许一个进程访问的资源。

互斥使用资源：

进程的同步、互斥机制──信号量及P.V操作

临界区（互斥区）：

• 一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作.
• 在进程中涉及到临界资源的程序段叫临界区.
• 多个进程的临界区称为相关临界区.

同步机制应遵循的规则 ：
（1）空闲让进。
（2）忙则等待。
（3） 有限等待。
（4） 让权等待。

访问临界资源的循环进程：

while(TURE）
{
进入区
临界区
退出区
剩余区
}

2.4.3 信号量机制

1、整型信号量 :
把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作wait(S)(申请资源，做减操作）和signal(S)（归还资源，做加操作）来访问。这两个操作一直被分别称为P、V操作。

2、记录型信号量 ：采取了“让权等待”的策略，会出现多个进程等待访问同一临界资源的情况。为此，除需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。

描述 ：

typedef struct {int value;struct process_control_block *list;}semaphore

相应地，wait(S)和signal(S)操作可描述为：

wait(semaphore *S) {S->value--;//value做分配一个资源的操作if(S->value < 0) block(S->list);//分配失败，阻塞}

 signal(semaphore *S) {S->value++;if (S->value<=0) wakeup (S->list);//value<=0,说明进程链表中仍有进程被阻塞}

如果S->value的初始值为1，表示只允许一个进程访问临界资源，此时信号量转化为护持信号量，用于进程互斥。

3、AND型信号量 ：一个进程获得两个或更多的共享资源，可能会出现死锁的状态。AND型信号量将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。采取原子操作方式：要么全部分配到进程，要么一个也不分配。
死锁状态：

process A:        	 process B:
wait(Dmutex); 	     wait(Emutex);
wait(Emutex);  	     wait(Dmutex);
process A: wait(Dmutex); //于是Dmutex=0
process B: wait(Emutex); //于是Emutex=0
process A: wait(Emutex); //于是Emutex=-1 A阻塞
process B: wait(Dmutex); //于是Dmutex=-1 B阻塞

AND型P、V操作：

Swait(Sl, S2,…， Sn)
{
while (TRUE)
{if (Si>=1 && ... && Sn>=1)//给予所有需要的资源{for (i =1; i<=n; i++) Si--;break;}else {/*资源没有完全分配，进程被阻塞，所有相关临界资源的计数设置为Swait操作开始之前*/place the process in the waiting queue associated with the first Si found with Si<1, and set the program count of this processto the beginning of Swait operation/*将进程放入与第一个Si＜1的Si相关联的等待队列中，并将此进程的程序计数设置为Swait操作的开始*/}}
}

Ssignal(S1，S2,...,Sn) {while (TRUE) {for (i=l; i<=n; i++) {Si++;Remove all the process waiting in the queue associated with Si into the ready queue/*删除队列中等待的所有进程，将Si关联到就绪队列中*/}}
}

4、信号量集：AND型信号量的拓展，进程对信号量Si的测试值不再是1，而是该资源的分配下限值ti，即要求Si>=ti，否则不分配。

Swait(S1, t1, d1, …, Sn, tn, dn)if Si≥t1 && … && Sn≥tn thenfor i∶=1 to n doSi∶=Si-di;endforelsePlace the executing process in the waiting queue of the first Si with Si＜ti and set its program counter to the beginning of the Swait Operation. endif

 signal(S1, d1, …, Sn, dn)for i∶=1 to n doSi ∶=Si+di;
Remove all the process waiting in the queue 
associated with Si into the ready queueendfor; 

(1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。
(2) Swait(S, 1, 1)。 一般的记录型信号量(S＞1时)或互斥信号量(S=1时)。
(3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

2.4.4 信用量的应用

1、利用信号量实现进程互斥，只需要为该资源设置一互斥信号量，设其初始值为1，然后将临界区CS置于wait(mutex)和signal(mutex)操作之间即可。每个欲访问该临界资源的进程在进入临界区之前，都要先对mutex执行wait操作，若该资源此刻未被访问，本次操作必然成功，进程就可以进入自己的临界区，这时若有其它进程也欲进入自己的临界区，由于对mutex执行wait操作定会失败，因此而阻塞，从而保证对进程的互斥访问，当访问临界区的进程推出临界区后，又应对mutex执行signal操作，释放资源。利用信号量实现两进程互斥的描述如下：

1）设mutex为互斥信号量，其初始值为1，范围（-1、0、1 )

• mutex=1;两个进程皆未进入需要互斥的临界区。
• mutex=0；一个进程进入临界区
• mutex=-1;一个进程在临界区中运行，另外一个进程在阻塞，运行进程退出临界区时需唤醒阻塞进程。

2）代码描述 ：

2、利用信号量实现前趋关系

代码框架：

p1(){S1;singal(a);singal(b);}
p2(){wait(a);S2;singal(c);singal(d);}
p3(){wait(b);S3;singal(e);}
p4(){wait(c);S4;singal(f);}
p5(){wait(d);S5;singal(g);}
p6(){wait(e);wait(f);wait(g);S6;}
main(){semaphore a,b,c,d,e,f,g;a.value=b.value=c.value=O;d.value=e.value=O;f.value=g.value=O;cobeginp1();p2();p3();p4();p5();p6();coend
}

2.5 经典进程同步问题