【OS】第二章 进程

2.1程序的基本概念

程序：一个在时间上按严格次序、顺序执行的操作序列。

程序的顺序执行

概念：一个具有独立功能的程序独占处理机，直至得到最终结果的过程。在计算机系统中只有一个程序在运行，这个程序独占系统中的所有资源，其执行不受外界影响。（通常一个程序可分成若干个程序段，它们必须按照某种先后次序执行，仅当前一操作执行后，才能执行后继操作。）

程序顺序执行的特征

顺序性（一个程序的各个部分的执行严格按照某种先后次序执行）
封闭性（程序在封闭的环境下运行，即程序在运行时独占全部系统资源）
可再现性（只要程序执行时的环境和初始条件相同，当重复执行时，不论它是从头到尾不停顿地执行，还是“走走停停”地执行，都将获得相同的结构）

前驱图

前驱图中的每个结点可以表示一条语句、一个程序段或进程，结点间的有向边表示两个节点之间存在的偏序或前趋关系。

程序的并发执行及特征

程序并发执行特征

1.不可再现性（由于程序的并发执行，打破了由另一程序独占系统资源的封闭性，因而破坏了可再现性）、间断性（程序并发执行时，由于他们共享资源或程序之间相互合作完成一项共同任务，因而使程序之间相互制约）
2.通信性
3.独立性
程序顺序执行，因为某一时段独占全机，所以结果可再现
程序并发执行，若不满足Bernstein条件，则结果不再现
程序不可以并发执行！

2.2进程的基本概念

进程是可并发执行的程序在某个数据集合上的一次计算活动，也是OS进行资源分配和保护的基本单位。
进程是一个既能用来共享资源，又能描述程序并发执行过程的一个基本单位。
进程能描述程序的并发执行状态。
进程是指在系统中能独立运行并作为资源分配的基本单位。
由机器指令、数据、堆栈组成。

进程控制块PCB

概念：系统为了管理进程设置的一个专门的数据结构，存放了用于描述该进程情况和控制进程运行所需的全部信息。
系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。
进程与PCB是一一对应的。
作用：使一个在多道程序环境下不能独立运行的程序（含数据），成为一个独立运行的基本单位。

资源清单：列出除了CPU以外进程所需资源和已经拿到的资源
进程状态：三、五、七

PID（进程控制符），就是各进程的身份标识，程序一运行系统就会自动分配给进程一个唯一的PID。进程中止后PID被系统回收，可能会被继续分配给新运行的程序。
进程控制块PCB的组织方式：链接方式、索引方式

2.3进程控制

一个例子：当某进程在阻塞态（state=2）时等待的事件发生，则内核程序需要①将PCB2的state设为1（代表就绪态）②将PCB2从阻塞队列移动到就绪队列（通过改变PCB2的链接地址）【①和②合在一起称为原子操作】<若在完成①后就进行中断操作的话，就会出现问题。因为PCB2仍在阻塞队列>

原语具有原子性，可用“关中断指令”和“开中断指令”这两个特权指令实现原子性

进程的执行是“异步”的
进程的控制是“原子性”的

进程的三态及其转换

问题：各个状态进程的物理位置？
创建进程的过程在内存完成

由于内存资源有限，多出的进程放入外存的虚拟存储器（虚拟内存）

进程的创建：

一、创建空白PCB
二、分配资源
三、初始化PCB
四、把该进程转入活动就绪态或者静止就绪态并插入到相应队列中

对于处于创建状态的进程，在获得其必须的资源以及对PCB初始化工作完成后，进程状态才由创建态转入就绪态
创建工作没有完成则进程不能被调度执行

进程的终止

进入终止态的进程不能再执行，OS中保留其记录（状态码+计时统计数据），供其它进程收集。一旦其他进程完成了对其信息的提取之后，OS将删除该进程（即将PCB清零，将PCB空间返回系统）
过程：
一、根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
二、若被终止进程正处于执行态，应立即终止该进程的执行
三、若该进程还有子孙进程，子孙进程也要终止。
四、将被终止进程所拥有的的全部资源归还父进程或系统
五、将被终止进程（PCB）从所在队列（或链表）中移除。

引起进程终止的事件：
1.正常结束（到达自然结束点）（exit系统调用）
2.异常结束
a.特权指令错（用户进程试图执行OS特权指令）b.算数运算错（被0除）c.被OS终结d.被其他有终止权的进程终结
3.外界干预（ctrl+Alt+delete）
进程终止——撤销原语

进程的挂起

进程挂起的原因

1.负荷调节的需要【由于不断创建进程，系统资源（尤其主存资源）不满足进程运行的要求，此时必须把某些进程挂起，置于磁盘对冲区，以此节省资源】
2.终端用户的请求【用户在调试程序的过程中，请求挂起其进程，以便检查和维修】
3.父进程请求
4.OS的需求

从创建态——活动就绪态
当前系统的性能和内存容量均允许时，完成对进程创建的必要操作后，进入活动就绪态。
从创建态——静止就绪态
不分配给新建进程所需资源（主要是主存资源），则转化为静止就绪态，将其对换到外存，不参与调度，此时进程创建工作完成。

挂起！=等待

从静止阻塞——>活动阻塞
原因：阻塞原因没有解除+被分配了内存资源

进程的阻塞和唤醒

注意：阻塞原语和唤醒原语成对使用
阻塞原语：运行态——>阻塞态
唤醒原语：阻塞态——>就绪态

进程的切换

含义：进程进/出CPU，不可被中断

进程的特征

一．结构性（程序块、数据块、PCB）
二．动态性：进程是程序在数据集合上的一次执行过程，有生命周期
三．并发性：多个进程实体同存于内存中，能在一段时间内同时运行
四．独立性：是独立运行、独立获取资源、独立接受调度的基本单位
五．异步性：OS提供“进程同步机制”解决异步

因为具有动态性，所以进程可异步、可调用

2.4进程同步

进程同步：多个相关进程在执行次序上的协调
进程互斥：在多道程序环境下，每次只允许一个进程对临界资源进行访问。
临界资源：一次仅提供一个进程使用的资源
临界区：在进程中涉及到临界资源的程序段
相关临界区：多个进程的临界区

直接相互制约（相互合作）

间接相互制约（资源共享）

同步机制应遵循的原则

空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入
忙则等待：不允许两个以上的进程同时进入互斥区（当一个进程正处在某临界区内，任何试图进入其临界区的进程都必须进入代码连续循环，陷入忙等状态。连续测试一个变量直到某个值出现为止，称为忙等。）
有限等待：对要求访问临界资源的进程，应保证有限时间内能进入自己的临界区，以免自己陷入“死等”（死等：进程在有限时间内根本不能进入临界区，而一直在尝试进入，陷入一种无结果的等待状态）
让权等待：处于等待状态的进程应放弃占用CPU，以免其他进程陷入“忙等”

信号量

概念：一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，该特殊变量值就是信号量，用于进程间传递信号的一个整数值
信号量说明 int s/semaphore s;
信号量按用途分为整形信号量 记录型信号量

整型信号量S

概念：定义为一个用于表示资源数目的整形量，其实就是一个变量。（比如系统中只有一台打印机，则设置该资源的信号量为1）

int S=1                //初始化S
void wait(int S)         //申请资源，使用资源 wait原语，相当于“进入区”
{
//若资源数不够，则一直循环等待。弊端：陷入“忙等”状态
	While(S<=0);       //空循环，（可通过记录型信号量来解决该问题）
	S=S-1;		
	//若资源数足够，则占用一个资源
}
/*使用打印机*/          //临界区，访问资源
void signal(int S)         //释放资源，相当于“退出区”
{
	S=S+1；           //使用完资源后，再退出去释放资源
}
1
2
3
4
5
6
7
8
9
10
11
12
13

整型信号量不满足让权等待

记录型信号量

概念：用记录型数据结构表示的信号量，在信号量上定义了三个操作：初始化、P(s)/wait(s)、V(s)/signal(s)

typedef struct{                  //记录型信号量的定义
int value;                  //剩余资源数
struct process*L;//等待队列
}semaphore;

wait(semaphore *S){				//某进程需要使用资源时，通过wait申请
S->value--;
if(S->value<0) block(S->L);
}
//当value<0 则|value|=被阻塞的进程数
signal(semaphore *S){
S->value++;				//进程使用资源后，通过signal原语释放
if(S->value<=0) wakeup(S->L);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

信号量机制实现-------------------------进程互斥

解题思路：
1.分析并发进程的关键活动，划定临界区，不同的临界资源设置不同的互斥信号量
2.设mutex为互斥信号量（取值：-1 0 1），初值为1
3.在进入区P（mutex）————申请资源
4.在退出区V(mutex)——————释放资源
mutex表示“进入临界区的名额”
PV操作成对出现
缺少P则不能保证临界资源的互斥访问
缺少V则导致资源永不被释放，等待进程永不被唤醒
有多少互斥进程就设置多少互斥变量

typedef struct{                  
int value;                  //剩余资源数
struct process*L;//等待队列
}semaphore;

semaphore mutex=1    //信号量机制实现互斥（要自己定义记录性信号量）
1（）{
...
P(mutex);//使用临界资源前需要加锁
  临界区代码段
V(mutex)//使用临界资源后需要解锁
...
}
1
2
3
4
5
6
7
8
9
10
11
12
13

信号量机制实现-------------------------进程同步

进程同步：让本来异步并发的进程相互配合，有序推进
步骤：
1.设置同步信号量S，设为0
2.在“前操作”之后执行V(S) 前操作：资源的产生者
3.在“后操作”之前执行P(S)

一个信号量对应一种资源。

信号量机制实现-------------前驱关系

每个前驱关系都是一个进程同步问题
要为每一对前驱关系各设置一个同步信号量
在“前操作”之后对相应的同步信号量执行V操作
在“后操作”之前对相应的同步信号量执行P操作