笔记主要来自西安电子科技大学出版的《计算机操作系统》一书，侵删
第二章进程的描述与控制
2.1（前驱图和程序执行）
前驱图：一个有向无循环图，结点是进程/程序段/一条语句，边是两个结点之间的偏序或前驱关系。（知道前驱图所描述的程序执行步骤即可）
程序的顺序执行：
- 特征：顺序性、封闭性、可再现性
程序并发执行：多个程序在同一时间间隔内交替执行
- 特点：间断性、失去封闭性、不可再现性。
2.2（进程的描述）
进程的不同定义：
- 定义1：程序的一次执行过程。
- 定义2：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。（获取CPU的使用权）
- 定义3：由程序段、相关数据段、PCB组成的进程实体，简称进程。（结构特征）
进程的特征：动态性、并发性、独立性、异步性。
进程的基本状态：
-
三基本状态：就绪状态、执行状态、阻塞状态。（常加入 创建状态 和 终止状态 以增强管理的灵活性）
三基本状态的转换：
三基本状态的转换 - 挂起状态：进程被挂起->进入静止状态（一般是负荷调节或其他进程/用户/操作系统的需要）
-
引入挂起原语操作后三个进程状态的转换
不允许CPU一直空闲，CPU一空闲就要调用准备就绪的进程。
图片.png
进程管理中的数据结构：一般分四类（内存表、设备表、文件表、进程表）
PCB（进程控制模块）：用于进程管理的进程表，是进程存在的唯一信息。（进程管理一般就是对一堆PCB进行增删查改等操作） - 包括的信息：进程标识符、处理机状态、进程调度信息、进程控制信息
- 组织方式：
线性方式：系统中的所有PCB都组织在一张线性表上。
链接方式：把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列。
索引方式：根据所有进程状态的不同，建立几张索引表。
2.3（进程控制）
进程控制一般由OS的内核中的原语来实现的。
进程控制包括：创建新进程、终止已完成的进程、将异常进程置于阻塞状态。
处理机的两种状态：核心态（系统态，高执行权）、用户态（低执行权）。
OS内核：基于硬件的第一次软件扩充，常驻内存。
原语：由若干指令组成，用于完成一定功能的一个过程。（不可分割）
（为什么、怎么做格式）
进程的创建：
- 进程图：描述进程间关系的一棵有向树
- 引起创建进程的事件：用户登录、作业调度、提供服务、应用请求
- 进程的创建：申请空白PCB、为新进程分配其运行所需的资源、初始化PCB、新进程插入就绪队列
进程的终止：
- 引起进程终止的事件：正常结束、异常结束、外界干预
- *终止过程：调用终止原语
若处于执行状态，则终止该进程的执行，置调度标志为真
终止进程，包括其子孙进程
归还资源给父进程或系统
将被终止进程（PCB）从所在队列或链表中移出
进程的阻塞与唤醒：
- *引起事件：请求资源失败、等待某操作完成、新数据未到达、等待新任务到达。
**阻塞过程：调用阻塞原语block
停止执行，将现行状态有“执行”改为“阻塞”，并插入阻塞队列 - *唤醒过程：调用唤醒原语wakeup
将事件从阻塞队列中移出，将现行状态由“阻塞”改为“就绪”，将该PCB插入到就绪队列中
进程的挂起与激活：
- *挂起过程：调用阻塞原语suspend（内存->外存）
就绪状态->静止就绪，阻塞状态->静止阻塞 - *激活过程：调用阻塞原语active（外存->内存）
静止就绪->就绪状态，静止阻塞->活动阻塞
2.4进程同步
进程同步作用：保证多个进程能够有条不紊地进行。
进程同步是指某些进程之间在逻辑上的相互制约的关系
两种形式的相互制约关系
- 间接形式的制约关系（共享资源）
*临界资源互斥访问，由系统实施分配，不允许用户进程直接使用 - 直接相互制约关系（相互合作）
临界资源：一次仅允许一个进程访问的资源
临界区：进程中访问临界资源的那段代码
while(TRUE)
{
进入区->检查是否被访问
临界区
退出区->恢复为未访问的标志
剩余区
}
同步机制遵循的规则：
- 空闲让进
- 忙则等待
- 有限等待（以免陷入“死锁”）
- 让权等待（及时释放处理机，以免进入：死等状态）
信号量机制：
- 整形信号量（信号量类型，是一个数据类型，代表资源的数量的一个整数）
有P操作（wait操作，申请一个资源）、V操作（signal操作，释放一个资源），两者成对出现
（整形信号量的P、V操作未实现“让权等待”原则，是缺点，实际少用）
P操作
wait(S){
while(S<=0);
S--;
}
V操作
signal(S){
S++;
}
- 记录型信号量（在整形信号量的基础上增加一个进程表指针list，用于链接所有等待的进程）
//数据项描述：
typedef struct{
int value;
int struct process_control_block *list;
}semaphore;
//wait(S)和signal(S)操作描述：
wait(semaphore *S){
S->value--;
if(S->value < 0) block(S->list);//阻塞原语
}
signal(semaphore *S){
S->value++;
if(S->value <= 0) wakeup(S->list);//唤醒原语
}
S->value > 0 时S->value描述可用资源数
S->value < 0 时S->value描述阻塞资源数
S->value = 0 时可用、阻塞资源数均为0
S->value初值为1，则变为互斥信号量
- AND型信号量（与整形和记录型相比，性能稍逊）
（当一个进程需要获得两个或更多的共享资源时，用互斥实现容易引发死锁，因此要用AND型信号量解决）
基本思想：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。
Swait(S1,S2,...,Sn){
while(TRUE){
if(Si >= 1 && ... && Sn >= 1){
for(i = 1;i <= n;i++) Si--;
break;
}
else{
//阻塞该进程，将该进程涉及的信号量恢复为该进程开始前的状态
}
}
}
Ssignal(S1,S2,...,Sn){
while(TRUE){
for(i = 1;i <= n;i++){
Si++;
//将与Si信号量有关的阻塞进程全部变为就绪状态
}
}
}
- 信号量集
每次Swait/Ssignal操作可以对某类资源进行多个单位的申请或释放（对AND信号量机制加以扩充）
规定资源的分配下限值ti和对该资源的需求值di，当才时分配资源，每次分配进行Si=Si-di操作
//对应的Swait和Ssignal格式：
Swait(S1,t1,d1,...,Sn,tn,dn);
Ssignal(S1,d1,...,Sn,dn);
//一般信号量集的几种特殊情况：
Swait(S,d,d) //信号量集中只有一个信号量S，允许每次申请d个资源，当现有资源数少于d时，不予分配
Swait(S,1,1) //蜕化为一般的记录型信号量（S>1）或互斥信号量（S=1）
Swait(S,1,0) //当S >= 1时允许多个进程进入某特定区，当S = 0时阻止任何进程进入特定区
信号量的应用：
- 利用信号量实现进程互斥（类似于竞争/间接制约）
P、V成对出现在同一进程中
每个临界资源设置互斥信号量mutex，初值为1，将临界区置于wait(mutex)和signal(mutex)间操作 - 利用信号量实现进程同步（类似于合作/直接制约）
P、V成对出现在不同进程中 - 利用信号量实现前驱关系
有几个前驱设几个进程，前驱结点有多少P，后继结点就有多少V
解决进程同步问题的一般步骤：（可以在书上P65-P72找例子辅助理解）
- 并发的进程是什么（父给苹果/桔子，儿吃苹果，女儿吃桔）
- 找到制约关系->定义信号量以及初始值（盘不满父才放，盘不空且有苹果儿才吃，盘不空且有桔女儿才吃->s（盘剩余容量），s0（苹果数），s1（桔子数），若有要求三个进程互斥可再加mutex（每个进程都PV））
- 描述并发进程的活动（P、V操作描述）
管程机制：（和信号量有同等的表达能力，但性能稍逊）
定义：一组相关的数据结构和过程一并称为管程
（任一时刻管程中只能有一个活跃进程，自动实现临界区的互斥）
引入目的：使并发编程更容易、保证正确性（使用信号量机制很容易产生死锁等问题）
相关的大致实现：管程引入了条件变量（condition）以及两个相关操作wait和signal使得进程在无法继续运行时阻塞
声明条件变量：condition x,y,...
执行x.wait操作 ：引起进程阻塞，排在等待x的队列中
执行x.signal操作：唤醒等待x队列中的队首进程
条件变量与信号量机制不同，不是计数器
2.5经典进程同步问题
用哪种的P操作就用哪种的V操作对应好
生产者-消费者问题
用记录型信号量要注意不能改变P操作的顺序（先empty再mutex），V操作的顺序随意
用AND有效可以解决死锁问题
哲学家进餐问题
①用非AND信号量解决（最多4人同时拿筷子/只有左右筷子可用才能进餐/奇数位先拿左边的筷子偶数位先拿右边的筷子）
②用记录型信号量模拟AND信号量解决（用锁人代替锁筷子）
③用AND信号量解决
读者-写者问题1（实现读写互斥、写写互斥、读读同时）：
用记录型信号量解决
设置两个互斥信号量rmutex、wmutex，另设一整型变量readcount
wmutex负责实现读写互斥（顺便实现了写写互斥）
readcount表示读者数，由0变1时要P(wmutex)（第一个读者），由1变0要V(wmutex)（最后一个读者），其它情况不用处理
rmutex负责实现多个读者改变readcount时的互斥进行
用信号量集机制解决
设置两个信号量L、mx，另设一整形变量RN；初值L=RN表示最多允许RN个读者同时读
Swait(L,1,1)与Ssignal(L,1)负责读者的人数限制工作
Swait(mx,1,0)负责实现读与写互斥（申请到mx至少为1即目前无写者）
Swait(mx,1,1;L,RN,0)负责写与写、写与读互斥（该语句表示仅当无writer在写又无reader在读才通过）
写者最后要Ssignal(mx,1)释放资源
读者-写者问题2（在1的基础上加上写者的优先级）：
在读者-写者问题1中的记录型解决方案中，
读者访问开始后要等到其后续的所有读者访问完才能释放资源给写者，
若读者源源不断进入会导致写者迟迟不能访问临界资源的情况出现，
现在要求写者排队要访问临界资源时后续的读者不能“插队”，
就好像给写者加上一定的“优先级”（其实算不上优先级，只是确保多并发过程中不被插队而已）
做法：
在问题1的基础上再设置信号量S
对于读者，在第一次对rmutex的PV操作外加一层对S的PV操作（贴合的一层）
对于写者，在对wmutex的PV操作外加一层对S的PV操作（贴合的一层）
解释：
这样当前一批读者都进行完第一次对rmutex的PV操作后，让出空闲的S给某个写者去P
当前一批读者继续后面的资源访问时，后一批读/写者会由于第一次PV操作中P不到S而等待（S给某个写者P掉了）
最后当前一批读者都访问完资源后V出wmutex，写者再去P掉wmutex开始访问临界资源（此前一直在等待wmutex）
当写者访问完临界资源后，V出S和wmutex，后一批读/写者才能有机会访问临界区
还有关于写者的绝对优先级问题，即当写者需要访问临界资源时其它的所有读者都要停下它们当前的进程（无论执行哪一步）
这个问题的解法略
2.6进程通信
进程通信：进程间的信息交换
进程的互斥与同步是低级进程通信：效率低、通信对用户不透明
高级进程通信：效率高、通信对用户透明
进程通信的四个类型：共享存储器系统、管道通信系统、消息传递系统、客户-服务器系统
- 共享存储器系统：
基于共享存储数据结构的通信方式：就像生产者消费者中的缓存区，系统只提供了一共享存储器，使用于少量通信（低效、不透明）
基于共享存储区的通信方式：系统提供了共享存储区，通信时向系统申请分区再进行读写（高效、速度快） - 管道通信系统：
管道：连接一个读进程和一个写进程之间通信的共享文件
功能：大量的数据发收
提供三方面的协调能力：同步、互斥、确定对方是否存在 - 消息传递系统（目前的主要通信方式）：
信息单位：报文
分为两类：直接通信方式、间接通信方式
特点：具有透明性、属于高级通信方式 - 客户机-服务器系统：
当前网络环境的主流通信方式
三种实现方法：嵌套字、远程过程调用、远程方法调用
消息传递通信的实现方式：
- 直接传递系统
原语：send(receiver, message);receive(sender, message);
消息格式：消息头（含控制信息）、消息内容、定长消息、变长消息
进程同步方式：发送接收进程阻塞、发送不阻接收阻、发送接收都不阻塞
通信链路：显式建立（进程做）、隐式建立（系统做）
链路类型：点对点链路和多点链路（连接方式）、单/双向（通信方式）、有/无容量（容量） - 间接传递系统（信箱通信）
原语：Send(mailbox, message);Receive(mailbox, message);
信息的创建与撤销：信箱名+属性（信箱类型）+共享者名字
信箱类型：公、私、共享
发送-接收进程间的关系：一对一、一对多、多对一、多对多
优点：读/写时间上的随机性
消息传递系统实例：
数据结构：
//消息缓冲区
typedef struct message_buffer{
int sender; //发送者进程标识符
int size; //消息长度
int *text; //消息正文
struct message_buffer *next; //指向下一个消息缓冲区的指针
}
//PCB有关数据项
typedef struct processcontrol_block{
...
struct message_buffer *mq; //消息队列首地址
semaphore mutex; //消息队列互斥信号量
semaphore sm; //消息队列资源信号量
...
}PCB;
*原语部分
//发送原语
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); //将发送区a中的信息复制到消息缓冲区i中
i.next = 0;
getid(PCBset, receiver.j); //获得接收进程内部的标识符
wait(j.mutex);
insert(&j.mq, i); //将消息缓冲区插入消息队列
signal(j.mutex);
signal(j.sm);
}
//接收原语
void receive(b){
j = internal name; //j为接收进程内部的标识符
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); //将消息缓冲区i中的信息复制到接收区b
releasebuf(i); //释放消息缓冲区
}
2.7线程的基本概念
引入线程，进程是资源分配独立单位，线程是系统独立调度和分派的基本单位
线程的实现：
用户级线程不依赖内核，内核级线程依赖内核
切换速度：用户级线程>内核级线程>进程
后略
