1程序顺序执行时的特征
(1) 顺序性
处理机的操作严格按程序规定顺序执行
(2) 封闭性
程序一旦开始执行，其计算结果不受外界因素影响。
(3) 可再现性
程序执行只要初始条件一样，不论如何停顿，重复执行多少次结果都一样。
2并发程序执行时的特征
(1) 间断性(运行时）
相互制约导致并发程序具有“执行——暂停——执行”这种间断性的活动规律。
(2) 失去封闭性
共享资源，资源状态由多道程序改变，程序运行失去封闭性。即程序运行受其他程序的影响
(3) 结果不可再现性
结果不确定，程序执行将没有任何意义
3进程
进程实体：程序段 + 数据段 + 控制块PCB（并发时用于程序控制和资源管理的各种信息）
进程 是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
进程的特征
结构性特征，进程的根本——PCB
动态性
进程实质上是进程实体的一次有生命期的执行过程。程序只是静态的一 组有序指令。
进程最基本特征
并发性
多个进程实体同存于内存中，在一段时间内同时运行。
有PCB的程序才能并发。
独立性
异步性
4进程与程序区别
动与静：
进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。
永久与暂时：
进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。
结构：
进程的组成包括程序、数据和进程控制块（进程各种控制信息）。
进程与程序的对应关系：
都可1对n。通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
5进程的状态转化
(1)就绪状态(Ready)
进程获得除CPU之外的所有必需资源，一旦得到CPU控制权，可立即运行。
(2)运行状态(Running)
进程已获得所有运行必需的资源，正在处理机上执行。
(3)阻塞状态(Blocked)
正在执行的进程由于发生某事件（请求I/O、申请缓冲、时间片到）而暂时无法执行时，便放弃CPU后暂停
6PCB的重要性
进程控制块是进程存在的唯一标志
进程管理和控制的最重要的数据结构
内部信息
（1）进程标识符信息
（2）处理机状态信息
（3）进程调度信息
（4）进程控制信息
7PCB的组织方式
（1）链接方式
同一状态的PCB，依靠链接指针链接成队列。就绪队列；若干个阻塞队列；
空白队列（PCB区的空PCB块）
（2）索引方式
同状态的PCB同样集中记录，但以索引表的方式记录PCB的地址。用专门 的单元记录各索引表的首地址。
8进程控制的基本过程：
进程的创建
进程的终止
进程的阻塞与唤醒
进程的挂起和激活
9进程创建过程
(1) 申请空白PCB
(2) 为新进程分配资源
(3) 初始化进程控制块
(4) 将新进程插入就绪队列
（原语是由若干指令构成的原子操作过程，作为整体实现功能，不可被打断）
OS通过调用进程创建原语Creat()创建新进程。
其他各控制工作也都是由OS内核以“原语”的方式实现，以保证不被打断。
10引起进程终止的事件
正常结束
异常结束
内存越界错误
保护错（权限错，如修改只读文件等）
非法指令（不存在的指令，程序异常转向而把数据当指令）
特权指令错（用户态程序试图执行只有OS可执行的指令）
运行超时、运算错、i/o故障等
外界干预
操作员或操作系统干预（死锁时，可人为结束）
父进程请求终止子进程
父进程终止，子孙进程也跟着终止
11进程终止过程
(1) 根据进程标示符，检索出该进程PCB，读其状态。
(2) 归还全部资源至其父进程或系统。
(3) 将该进程PCB从所在队列或链表中移出。
12引起进程阻塞和唤醒的事件
（1）请求系统服务的满足情况
（2）启动某种需等待（I/O）操作
（3）合作需要的新数据尚未到达
（4）执行某功能的进程暂时无新工作可做(如发送数据进程)
13进程阻塞和唤醒过程
（1）将PCB中的状态改为阻塞
（2）该PCB加入到阻塞队列中
（3）转进程调度，将处理机分配给另一进程
（4）进行进程切换，即根据两切换进程的PCB，保护与重新设置处理机状态。
14进程的挂起与激活
（1）检查被挂起进程的状态，活动就绪则改为静止就绪，活动阻塞则改为静止阻塞
（2）将该PCB复制到内存（方便检查）/外存（对换）指定区域
（3）若挂起的进程是执行态，则需重新进行进程调度。
15进程间两种制约关系：
（1）间接相互制约关系：主要源于资源共享,表现为
进程A—打印机资源—进程B（互斥）
（2）直接相互制约关系：主要源于进程合作，表现为
进程A写缓冲—进程B读缓冲（有序）
16进程同步的主要任务：
使并发执行的诸进程之间能有效地【共享资源和相互合作】，从而使程序的执行具有可再现性。
临界资源：一次仅允许一个进程使用的资源。
临界区：每个进程中访问临界资源的那段代码叫临界区。
【互斥】：在操作系统中，当一个进程进入临界区使用临界资源时，另一个进程必须等待，直到占用临界资源的进程退出临界区，我们称进程之间的这种相互制约关系为“互斥”。
【同步】：多个相互合作的进程，在一些关键点上可能需要互相等待或互相交换信息，这种相互制约关系称为进程同步关系。可理解为“有序”。
17同步机制应遵循的规则
（1）空闲让进：资源使用最基本原则
（2）忙则等待：保证互斥
（3）有限等待：合适时被唤醒防止死等
（4）让权等待：能主动释放CPU防止忙等
18信号量机制
1） 整型信号量
信号量定义为一个整型量；
根据初始情况赋相应的值；
仅能通过两个原子操作来访问。
【P操作】 wait(S):
While S<=0 do no-op;
S:=S-1;
【V操作】 signal(S):
S:=S+1;
当≥0，代表可供并发进程使用的资源实体数
当<0，表示正在等待使用该资源的进程数。
实现多个进程互斥
P(mutex);
{S.value = S.value – 1;
if S.value < 0 then block(S,L)
}
critical section操作共享资源R
V(mutex);
{S.value = S.value + 1;
if S.value <= 0 then wakeup(S,L)
}
互斥信号量注意点：
1）互斥信号量mutex初值为1；
2）每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间
3）必须成对使用P和V原语（在同一进程中），不能次序错误、重复或遗漏
实现有序
并发执行的进程P1和P2中，分别有代码C1和C2，要求C1要在C2开始前完成；
P1 ： C1 ；signal(S)；
P2 ： wait(S)；C2 ；
控制同步顺序的注意点
1）信号量值为0的点是限制的关键所在；
2）成对使用P和V原语（在有先后关系的两个进程中），不能次序错误、重复或遗漏，否则同步顺序出错
例题：设有一供者和一用者，如何用信号量来控制二者对缓冲区的同步使用
供者：
…
P(s1);
将数据送入缓冲区；
V(s2);
用者：
P(s2);
从缓冲区取数来用；
V(s1);
进程同步的应用举例
1.
生产者—消费者问题
1）多个生产者和消费者对n个缓冲区的使用。
2）无论生产者、消费者使用缓冲池时应保证互斥使用（互斥信号量mutex ）
3）生产者和消费者间交叉有序：
有序的控制最根源在产品数量上。
设置两个信号量：
分别针对生产者、消费者设置不同的信号量，empty和full分别表示缓冲池中空缓冲池和满缓冲池（即产品）的数量。
buffer: array [ 0, …, n-1] of item;
in, out: integer :=0, 0;
//不使用Counter变量，而是用信号量
Var mutex, empty, full: semaphore :=1, n, 0;
【producer】 :
repeat
…
produce an item in nexp;
【wait(empty);】
【wait(mutex);】
buffer(in):=nexp;
in:=(in+1) mod n;
【signal(mutex);】
【signal(full);】
until false;
【consumer】 :
repeat
【wait(full);】
【wait(mutex);】
nextc:=buffer(out);
out:=(out+1) mod n;
【signal(mutex);】
【signal(empty);】
consume the item in nexc;
until false;
2.
哲学家进餐问题
五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。
（可见：相邻两位不能同时进餐；最多只能有两人同时进餐。）
筷子是临界资源，在一段时间内只允许一个哲学家使用。为实现对筷子的互斥使用，用一个信号量表示一只筷子，五个信号量构成信号量数组。
Var chopstick: array [0, …, 4] of semaphore;
所有信号量均被初始化为1。
第i 位哲学家的活动可描述为：
repeat
【wait(chopstick[ i ]);】//当哲学家饥饿时，总是先拿左边的筷子，再拿右边的筷子。
【wait(chopstick[ ( i +1) mod 5] );】
…
eat;
…
【signal(chopstick[ i ]);】//当哲学家进餐毕，先放下左边的筷子，再放下右边的筷子。
【signal(chopstick[ ( i +1) mod 5] );】
…
think;
until false;
死锁问题：假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0，当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限等待。
解决方法：
1）数量控制：至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕后释放出他用过的两只筷子，从而使更多的哲学家能够进餐。—限制并发执行的进程数
2）一刀切：仅当哲学家的左右两只筷子均可用时，才允许他拿起筷子进餐。—采用AND信号量。
3）IF编程控制：规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；偶数号哲学家则相反。保证总会有一个哲学家能同时获得两只筷子而进餐
if I mod 2=0
…
else
…
3.
读者——写者问题
一个数据文件被多个进程共享。Reader进程只要求读文件，Writer进程要求写入内容。
合理的同步关系是：
多个读进程可同时读；
Writer进程与任何其他进程（包括Reader进程或其他Writer进程）不允许同时访问文件。
Writer :
repeat
【wait(wmutex);】
写入文件；
【signal(wmutex);】
until false;
Reader :
begin
repeat
【wait(rmutex);】
if Readcount=0 then 【wait(wmutex);】
Readcount :=Readcount +1;
【signal(rmutex);】
perform read operation;
【wait(rmutex);】
Readcount :=Readcount -1;
if Readcount=0 then 【signal(wmutex);】
【signal(rmutex);】
until false;
end
管程(monitor)机制
1.管程的组成
1）一组局部变量
2）对局部变量操作的一组过程
3）对局部变量进行初始化的语句。
2.管程特点
1）任何进程只能通过调用管程提供的过程入口才能进入管程访问共享数据；
2）任何时刻，仅允许一个进程在管程中执行某个内部过程。
3.管程的缺点
1）大多数常用的编程语言中没有实现管程，如果某种语言本身不支持管程，那么加入管程是很困难的。
2）虽然大多数编程语言也没有实现信号量，但可将P、V操作作为一个独立的子例程或操作系统的管理程序调用加入。
进程通信
高级通信机制可归结为四大类
1.共享存储器系统（操作存储区方式）
1）基于共享数据结构的通信方式（低级）
2）基于共享存储区的通信方式（高级）
2.消息传递系统（发–收方式）
最广泛使用的一种，进程间的数据交换，以格式化的消息为单位。屏蔽底层复杂操作。
3.管道通信（中间文件方式）
所谓“管道”，是指用于连接一读进程和一写进程以实现通信的一个共享文件，又名pipe文件。向共享文件输入的写进程以字符流形式将大量的数据送入管道；而接收管道输出的读进程则从管道中接收(读)数据。
4.Client-Server system
一个套接字就是一个通信标识类型的数据结构，包含了通信目的的地址，端口号，传输层协议、进程所在的网络地址，以及针对C\S程序提供的不同系统调用（API函数）等。系统中所有的连接都持有唯一的一对套接字及端口连接，从而方便地区分来自不同应用程序进程或网络连接的通信，确保通信双方间逻辑链路的唯一性。
消息传递通信的实现方法
1）直接通信方式
2）信箱消息的发送和接收
线程（TCB）
进程内的一条执行路径
多线程系统中，同一个进程中的多个线程
共享进程资源
可并发执行
线程的创建
利用线程创建函数(或系统调用)，提供相应参数。线程创建函数执行完后，返回一个线程标识符供以后使用。
线程的终止
不立即释放资源，只有当进程中的其它线程执行分离函数后，资源才分离出来能被其它线程利用。 被终止而未释放资源的线程仍可被需要它的线程调用，使其重新恢复运行。
【线程与进程的比较】
1）调度：线程作为CPU调度的基本单位，而进程只作为其它资源分配单位。
2）并发性：进程之间可以并发，实质上是不同进程中的两个线程并发。一个进程的多个线程之间亦可并发。
3）拥有资源：进程间资源相互独立；同一进程的各线程间共享。某进程内的线程在其它进程不可见
4）系统开销：线程上下文切换在同进程环境下上下文切换要快得多。因为同进程内线程间共享内存地址和打开的文件资源；