Chapter2-进程的描述与控制
资源分配和独立运行的基本单位
前趋图
Pi->Pj 直接前趋，直接后继
初始结点，终止结点
结点的重量->执行时间
程序顺序执行的特征
顺序性，封闭性，可再现性
程序的并发执行
只有不存在前趋关系的程序之间才有可能并发执行
特征：
间断性，失去封闭性，不可再现性（运行环境会受到其它程序的影响）
进程
程序段，相关数据段，PCB->进程实体->简称进程
PCB是进程存在的唯一标志。
但实际上进程是进程实体的运行过程（动态的概念），系统进行资源分配和调度的一个独立单位。
特征：
动态性，并发性，独立性，异步性
进程的状态
就绪态，就绪队列
执行态
阻塞态，正在执行的进程由于发生某事件（I/O阻塞，申请缓冲区失败等），根据阻塞原因不同会设置多个阻塞队列。
创建态，申请空白PCB->填写用于控制和管理进程的信息->分配运行时所必须的资源->转入就绪状态并插入就绪队列
若资源尚未满足就还是处于就绪态
终止态，等待操作系统的善后处理（在操作系统中保留一个记录，用于保存状态码和计时统计数据，供其它进程收集，其它进程完成信息提取后，操作系统就删除该进程）->将PCB清零，并将PCB空间返回系统
pic
用原语实现进程控制。
原语采用关中断和开中断指令来执行。
挂起，激活
静止状态
引起挂起状态的原因（挂起倾向于主动（不想让它执行），阻塞倾向与被动（它没法执行））：
终端用户的需要，父进程请求，负荷调节的需要，操作系统的需要
pic
PCB的作用
1.作为独立运行基本单位的标志
2.能实现间断性运行方式（CPU现场信息）
3.提供进程管理所需的信息（找到响应的程序和数据）
4.提供进程调度所需的信息（处于何种状态）
5.实现与其它进程的同步与通信
PCB中的信息
1.进程标识符
外部标识符（方便用户（进程）对进程的访问），内部标识符（方便系统对进程的使用，序号），
2.处理机状态
也称为处理机的上下文，主要由处理机的各种寄存器中的内容组成
通用寄存器（用户可视寄存器），指令计数器，程序状态字，用户栈指针
3.进程调度信息
进程状态，进程优先级，进程调度所需的其它信息（与调度算法有关，如进程已执行的时间），事件（阻塞原因)
4.进程控制信息
程序和数据的地址，进程同步和通信的机制（消息队列指针，信号量等），资源清单，链接指针（下一个进程的PCB的首地址）
PCB的组织方式
线性方式
链接方式
（执行指针，就绪队列指针，阻塞队列指针，空闲队列指令）
索引方式
（执行指针，就绪表指针->就绪索引表，阻塞表指针）
进程的创建
父进程，子进程，进程家族
子进程可以继承父进程所拥有的资源
子进程被撤销时要归还资源
父进程撤销时其子进程也全部撤销
PCB中设置了家族关系表项
（Windows中不存在这样的层次关系，而是用句柄来指示进程间的控制关系）
引起进程创建的事件
1.用户登录2.作业调度3.提供服务（前三个都是系统内核创建）4.应用请求（由用户程序自己创建）
进程创建原语Create
申请空白PCB-》为新进程分配所需资源-》初始化PCB-》将PCB插入就绪队列。
进程的终止
引起进程终止的事件
1.正常结束
2.异常结束
越界错，保护错，非法指令，特权指令错，运行超时，等待超时，算术运算错，I/O故障
3.外界干预
操作员或操作系统干预，父进程请求，父进程终止
撤销原语
从PCB集合中找到终止进程的PCB-》若进程正在运行则剥夺CPU分配给其它进程-》终止其所有子进程-》归还资源给父进程或系统-》删除PCB
进程的阻塞与唤醒
向系统请求共享资源失败，等待某种操作完成，新数据尚未到达，等待新任务的到达
进程！调用阻塞原语block将自己阻塞
阻塞是进程自身的一种主动行为
有关进程调用唤醒原语wakeup
挂起
OS！调用挂起原语suspend
OS！调用激活原语active
进程的同步
进程间的制约关系
1.间接相互制约关系（共享系统资源）——进程互斥问题（对临界资源的访问需要互斥的进行）
2.直接相互制约关系（相互合作）——进程同步问题
临界资源
进入区->临界区->退出区->剩余区
进程互斥地进入自己的临界区
同步机制应遵循的规则
空闲让进，忙则等待，有限等待，让权等待（当进程不能进入自己的临界区时，应立即释放处理机）
硬件同步机制
1.关中断
简单高效，不适用多处理机，只适用于操作系统内核进程（因为关中断开中断只能在内核态执行）
2.Test-and-Set指令实现互斥
该指令使用硬件实现的，下面只是它的C语言描述
boolean TS(boolean *lock){
boolean old;
old=*lock;
*lock=TURE;
return old;
}
do{
...
while TS(&lock); //当lock为false时，说明空闲，才能跳出这个循
//环，并且被设置为Ture
critical section;
lock=FALSE; //退出区
remainder section;
}while(TRUE);
不满足让权等待
3.Swap指令实现进程互斥
和上一个差不多，弄了个key代替old
void swap(boolean *a,boolean *b)
{
boolean temp;
temp=*a;
*a=*b;
*b=temp;
}
do{
key=TRUE;
do{
swap(&lock,&key);
}while(key!=FALSE);
critical section;
lock=FALSE;
remainder section;
}while(TURE);
不满足让权等待
以上的方法，当资源忙碌时，其它访问进程必须不断进行测试，处于“忙等”状态，不符合让权等待原则。
信号量机制
1.整型信号量 忙等
表示资源数目的整型量S
除了初始化外，仅能通过两个标准的原子操作P，V来访问
wait(S){
while(S<=0);
S--;
}
signal(S){
S++;
}
2.记录型信号量 不用忙等
value表示资源数目，list表示用于链接所有等待访问该资源的进程的链表指针
typedef struct{
int value;
struct process_control_block *list;
}semaphore;
wait(semaphore *S){
S->value--;
if(S->value<0) block(S->list);
//S->value的绝对值表示该信号链表中已阻塞的进程的数目
}
signal(semaphore *S){
S->value++;
if(S->value<=0) wakeup(S->list);
}
可以用记录型信号量实现系统资源的申请和释放，进程互斥，进程同步。
S->value的初值为1则转化为互斥信号量
互斥
semaphore mutex=1;
P1(){
...
P(mutex);
临界区
V(mutex);
...
}
P2(){
...
P(mutex);
临界区
V(mutex);
...
}
对于不同的临界资源需要设置不同的互斥信号量。
同步
设置同步信号量S，初值为0
在前操作后面执行V（S）
在后操作之前执行P（S）
3.AND型信号量
需要获得两个或更多的共享资源
对若干个临界资源的分配采取原子操作方式，要么全给，要么一个也不给
4.信号量集
资源分配下限值ti（Si<ti时就不分配了），资源需求值di
Swait(S1,t1,d1,...,Sn,tn,dn);
Ssignal(S1,d1,...,Sn,dn);
几种特殊情况
Swait(S,d,d)
Swait(S,1,1)记录型信号量 S=1互斥信号量
Swait(S,1,0)相当于一个开关，当S>=1时允许多个进程进入，当S=0时组织任何进程进入
信号量的应用
1.利用信号量实现进程互斥
wait(mutex);
临界区；
signal(mutex);
2利用信号量实现前趋关系
管程机制
信号量机制中，大量的同步操作分散在各个进程中，不仅给系统管理带来麻烦，还会因为同步操作的使用不当造成死锁。
管程：（代表共享资源的数据结构）以及（由对该共享数据结构实施操作的一组过程所组成的资源管理程序）共同构成了一个操作系统的资源管理模块。
确保每次仅有一个进程进入管程，执行这组过程，使用共享资源
特性：模块化，抽象数据类型，信息掩蔽
进程在使用管程时可能会被阻塞或挂起，引入条件变量来指示其被阻塞或挂起的原因
x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件发生变化
x.signal：正在调用管程的进程发现x条件发生了变化，调用x.signal，重新启动一个因x条件而阻塞或挂起的进程（重新启动的这个进程可以等待当且进程完成或阻塞，也可以换当前进程等待）
经典进程同步问题
p60
进程通信
1.共享存储器系统
互斥访问共享空间
（1）基于共享数据结构的通信方式
如生产者-消费者中的有界缓冲区
仅适合传递少量数据，属于低级通信
（2）基于共享存储区的通信方式
向系统申请获得共享存储区中的一个分区，然后附加到自己的地址空间，读写完成后，再归还给共享存储区。高级通信。
2.管道通信系统
pipe文件：连接一个读进程和一个写进程以实现它们之间通信的一个共享文件
字符流
互斥，同步，确定对方是否存在
某一时间段内只能实现单向传输
没写满就不允许读，没读空就不允许写
一旦数据被读出，该数据就被管道抛弃了，这意味着读进程只能有一个。
3.消息传递系统
以格式化的消息为单位
将通信的数据封装在消息中
利用操作系统提供的一组通信命令（原语）
属于高级通信方式
直接通信方式
1）对称寻址方式 显式提供双方的标识符
send(receiver, message);
receive(sender, message);
2）非对称寻址方式
send(P, message);
receive(id, message);接收来自任何进程的消息，id变量作为完成通信后的返回值指示发送方的id或名字
定长消息格式/变长消息格式
单向/双向通信链路（建立连接）
间接通信方式（邮箱）
send(mailbox, message);
receive(mailbox, message);
私用/公用/共享邮箱
直接消息传递系统实例
消息缓冲队列机制
消息缓冲区
typedef struct message_buffer{
int sender;
int size;
char *text;
struct message_buffer *next; //指向下一个消息缓冲区
}
在PCB中增加
struct message_buffer *mq; //消息队列队首指针（放要接收的消息缓冲区）
semaphore mutex; //消息队列互斥信号量
semaphore sm; //消息队列资源信号量
发送原语
void send(receiver, a){ //receiver为接收进程标识符，a为发送区首址
getbuf(a.size, i); //根据a.size申请消息缓冲区
i.sender=a.sender;
i.size=a.size;
copy(i.text, a.text);
i.next=0;
getid(PCBset, receiver.j); //获得接收进程内部的标识符
wait(j.mutex);
insert(&j.mq, i); //挂到消息队列上去
signal(j.mutex);
signal(j.sm); //sm标识队列中有没有消息
}
接收原语
void receive(b){
j=internal name;
wait(j.sm); //没有消息就等着
wait(j.mutex);
remove(j.mq, i);
signal(j.mutex);
b.sender=i.sender;
b.size=i.size;
copy(b.text, i.text);
releasebuf(i); //释放消息缓冲区
}
4.客户机-服务器系统
线程
比进程更小的基本单位
减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。
进程的两个特征
1调度和分配的基本单位
2拥有资源的基本单位
现在将这两个特征分开，作为拥有资源的基本单位的进程不再作为调度和分派的基本单位，因为拥有资源会导致调度和分配开销很大
线程作为调度和分派的基本单位
线程控制块TCB
还可以将一个进程的多个线程分配到不同处理机上
执行状态，就绪状态，阻塞状态
