其实，我只是把
PPTCtrl+C、Ctrl+V 了一下（捂脸）
4.1 并发进程
4.1.1 顺序程序与并发进程
1）顺序程序
- 顺序程序：
指令或语句序列，体现了某种算法，所有程序是顺序的。
- 顺序环境：
在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。
2）顺序程序的特征
- 顺序性执行
- 封闭性，独占资源
- 确定性，即可再现性
3）并发进程
并发环境：在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。
4）并发进程的特征
- 间断性执行，执行–停--执行
- 资源共享，多个进程共享使用系统资源
- 不可再现性，执行结果不确定
- 独立性和制约性
- 程序和进程不再一一对应
4.1.2 与时间有关的错误
4.1.3 进程间的联系
1）间接式与直接式制约：
- 直接式制约：一程序段等待另一程序段的执行结果
- 间接式制约：并发程序段竞争同一资源
2）相交进程与无关进程：
- 相交进程：并发进程在逻辑上有某种联系
- 无关进程：逻辑上无任何联系的并发进程
- 直接作用只发生在相交进程之间；间接作用可以发生在相交进程之间，也可发生在无关进程之间
3）进程的同步与互斥（重要）
- 进程同步（直接作用）：根据一定的时序关系合作完成一项任务
- 并发进程因直接制约而互相等待，彼此相互发送消息进行合作，使得各进程按一定的速度执行
- 进程互斥（间接作用）：各进程竞争使用临界资源
- 临界资源：一次只允许一个进程使用的系统资源
- 进程互斥是进程同步的一种特殊情况
- 互斥：多种同类进程之间，比如：消费者和消费者。间接制约。
- 同步：不同类进程之间，比如：生产者和消费者。直接制约。
4.2 临界区管理
4.2.1 临界区及其使用原则
- 临界区：进程中涉及临近资源的程序段为临界区/互斥区，多个进程的临界区为相关临界区。
- 临界区的使用原则：（选择/填空）
- 有空让进
- 无空等待
- 多中择一
- 有限等待
- 让权等待
- 解决进程互斥的两种做法：
- 由竞争各方平等协商解决，包括硬件、软件两类方法。
- 引入进程管理者来协调竞争各方对互斥资源的使用。
4.2.2 实现临界区管理的软件方法
4.2.3 实现临界区管理的硬件方法
1）测试并建立指令TS
2）交换指令SWAP
3）开关中断指令
4.3 信号量与P、V操作（重中之重）
4.3.1 信号量的定义
1）信号量的提出
2）信号量定义
Struct semaphore
{ int value; //信号量的值
pointer PCBqueue; //信号量队列指针
}
信号量说明：semaphore s
3）信号量的特性
4.3.2 P、V操作的定义
1）什么是P、V操作？、
（1）P、V操作是能对信号量进行处理的唯一两个操作，是不可分割的一段程序，为原语操作（执行过程中不允许被中断）
（2）P操作用于申请信号量管理的资源（如停车场一例中需要进入停车场使用车位的车就应执行P操作）
（3）V操作用于释放资源（如停车场一例中需要开出停车场归还车位的车就应执行V操作）
2）P操作
P(s)
{ s.value = s.value --; //s.value减1
if (s.value < 0)
//该进程被阻塞，进入相应队列，然后转进程调度
{
该进程状态置为等待状态;
将该进程的PCB插入相应的等待队列s.queue的末尾;
}
//若s.value减1后仍大于或等于零，则进程继续执行
}
3）V操作
V(s)
{ s.value = s.value ++; //s.value加1
if (s.value <= 0)
//从队列中唤醒一等待进程，然后继续执行或转进程调度
{
唤醒相应等待队列s.queue中等待的一个进程;
改变其状态为就绪态，并将其插入就绪队列;
}
}
4.3.3 信号量的使用
1）使用注意事项：
必须置一次且只能置一次初值，且初值不能为负数；只能执行P、V操作
2）用信号量及P、V操作解决进程间互斥问题
mutex : semaphore; mutex:= 1;
cobegin
process Pi
begin
…
P(mutex);
临界区；
V(mutex); //P、V一定不是同一个（因为是并发）
…
end;
coend;
3）用信号量及P、V操作解决进程间同步问题
- 生产者-消费者问题
- 问题描述：生产者往缓冲区中放产品，消费者从缓冲区中取产品。
- 生产者P进程不能往“满”的缓冲区中放产品，设置信号量为S1，初值为1，代表缓冲区有1个空闲空间。
- 消费者Q进程不能从“空”的缓冲区中取产品，设置信号量S2 ，初值为0，代表缓冲区有0个产品。
P //生产者进程
while (true) {
生产一个产品;
P(s1) ; //初值为1
送产品到缓冲区;
V(s2);
};
C //消费者进程
while (true) {
P(s2); //初值为0
从缓冲区取产品;
V(s1);
消费产品;
};
4.3.4 信号量及P、V操作的讨论
1）信号量及P、V操作的物理含义
① S>0表示有S个资源可用
② S=0表示无资源可用
③ S<0则| S |表示S等待队列中的进程个数
④ P(S)表示申请一个资源
⑤ V(S)表示释放一个资源
2）P、V操作必须成对出现，有一个P操作就一定有一个V操作
① 当为互斥操作时，它们处于同一进程
② 当为同步操作时，则不在同一进程中出现
③ 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要，一个同步P操作与一个互斥P操作 在一起时，同步P操作在互斥P操作前，而两个V操作无关紧要。
3）信号量及P、V操作优缺点
① 优点：简单且表达能力强，用P、V操作可解决任何同步、互斥问题。
② 缺点：不够安全，P、V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂。
4.3.5 P、V操作经典问题（重中之重）
1）哲学家吃通心面问题
问题描述：5个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。每个哲学家必须直接从自己左边和右边同时获得两把叉子才能吃面。
解决思路：5位哲学家看作5个进程，需要互斥使用5把叉子，这5把叉子是共享资源，用5个信号量表示。
var fork[i]:array[0..4] of semaphore; fork[i] := 1;
cobegin
process Pi // i=0,1,2,3,4,
begin
L1: 思考；
P(fork[i]); //叉子逆时针编号，先拿左边叉子
P(fork[(i+1)mod 5]); //再拿右边叉子
吃通心面;
V(fork[i]); //归还左边叉子
V(fork[(i+1)mod 5]); //归还右边叉子
goto L1;
end;
coend
- 避免死锁：
- 至多允许4个哲学家同时吃
- 奇数号先取左手边的叉子，偶数号先取右手边的叉子
- 每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取
2）生产者消费者问题
问题描述：若干进程通过K个有限共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出。任何时刻只能有一个进程可对共享缓冲区进行操作。且满足条件：① 消费者想接收数据时，有界缓冲区中至少有一个单元是满的；② 生产者想发送数据时，有界缓冲区中至少有一个单元是空的。
解决思路：设置3个信号量
- full表示“满”数目，即产品数，初值为0
- empty表示“空”数目，初值为K；full + empty == K
- mutex用于访问缓冲区时的互斥，初值是1
var B: array[0..k-1] of item; in, out:integer:= 0; //缓冲区读写指针
empty, full, mutex: semaphore; empty:=k; full:=0; mutex:=1;
cobegin
process producer_i
begin
L1:produce a product;
P(empty); P(mutex);
B[in] := product;
In:=(in+1) mod k;
V(mutex); V(full);
Goto L1;
end;
coend
var B: array[0..k-1] of item; in, out:integer:= 0; //缓冲区读写指针
empty, full, mutex: semaphore; empty:=k; full:=0; mutex:=1;
cobegin
process producer_i
begin
L1:produce a product;
P(mutex); P(empty);
B[in] := product;
In:=(in+1) mod k;
V(mutex); V(full);
Goto L1;
end;
coend
3）苹果桔子问题
问题描述：桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果（apple），妈妈专向盘子中放桔于（orange）；一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果
解决思路：生产者消费者问题的变形，有两类生产者和两类消费者，仍然设置3个信号量
- sp表示盘子能放的水果数目，初值为1
- sg1表示盘子里有无桔子，初值为0
- Sg2表示盘子里有无苹果，初值为0
sp, sg1, sg2: semaphore; sp := 1; sg1, := 0; sg2 := 0;
cobegin
process father
begin
L1:削一个苹果；
P(sp); 放苹果;
V(sg2);goto L1;
end;
process mother
begin
L2:剥一个桔子；
P(sp); 放桔子；
V(sg1); goto L2;
end;
process daughter
begin
L4: P(sg2);取苹果；
V(sp); 吃苹果；
goto L4;
end;
process son
begin
L3: P(sg1); 取桔子；
V(sp); 吃桔子；
goto L3;
end;
coend
4）读者和写者问题
问题描述：读者和写者两组并发进程共享一个文件F，要求允许多个读者同时执行读操作，任一写者在完成写操作之前不允许其他读者或写者工作，写者执行写操作前，应让已有的写者和读者全部退出
解决思路：设置2个信号量W和R，1个控制变量rc
- W控制读写进程对文件的互斥访问，初值为1
- R控制各个读进程对rc的互斥访问，初值为1
- rc记录正在读文件的进程数，初值为0
var rc: integer; rc:=0; W，R: semaphore; W := 1; R := 1;
cobegin
procedure read;
begin
P(R);
rc := rc + 1;
if rc=1 then P(W)；
V(R);
读文件；
P(R);
rc := rc - 1;
if rc = 0 then V(W)；
V(R);
end;
coend
5）理发师问题
问题描述：理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉，一个顾客到来时，它必须叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。
该程序中引入3个信号量和1个控制变量：
（1）控制变量waiting用来记录等候理发的顾客数，初值均为0；
（2）信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；
（3）信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0；
（4）信号量mutex用于互斥，初值为1。
4.3.6 Linux 中的信号量机制
4.4 进程间的通信
4.4.1 进程间通信的概念
1）进程间通信：进程之间互相交换信息的工作。
2）进程间的通信根据通信的内容可以划分为两种
- 控制信息的传送：只传递简单的信号，不能传递交换大量信息，如信号量机制及P、V操作（低 级通信原语）控制的进程同步和互斥
- 大批量数据传送：用Send/Receive原语（高级通信原语）
4.4.2 进程间的通信方式
1）主从式（Master-Servant）通信：主进程-从进程
- 主进程可自由地使用从进程的资源或数据
- 从进程的动作受主进程的控制
- 主进程和从进程关系固定
- 典型例子是终端控制进程和终端进程
2）会话式（Dialogue）通信：使用进程-服务进程
- 使用进程调用服务进程提供的服务
- 使用进程在使用服务进程所提供的服务之前，必须得到服务进程的许可
- 服务进程根据使用进程的要求提供服务，但对所提供服务的控制由服务进程自身完成
- 使用进程和服务进程在进行通信时有固定连接关系
3）消息队列或邮箱：发送进程-接收进程
- 消息用于表示所交换的数据，传递大量信息之外，还意味着两个互相通信的进程地位平等
- 缓冲区或邮箱专门存放被传送消息
- 只要存在空缓冲区或邮箱，无论接收进程是否已准备好接收消息，发送进程都将把所要发送的消息送入缓冲区队列或邮箱
- 发送进程相接收进程之间无直接连接关系
4）共享存储区(Shared Memory): 读进程-写进程
- 两个需要互相交换信息的进程通过对同一共享数据区的操作来达到互相通信的目的
- 不要求数据移动
5）上述方式可以分为如下两类：
直接通信：信息直接传递给接收方
- 在发送时，指定接收方的地址或标识，也可以指定多个接收方或广播式地址
- 在接收时，允许接收来自任意发送方的消息，并在读出消息的同时获取发送方的地址
间接通信：借助于收发双方进程之外的共享数据结构作为通信中转
- 如消息队列或是信箱
- 接收方和发送方的数目可以是任意的
4.4.3 进程进程间通信需要考虑的其它特征
1）通信链路特征
（1）链路是
（2）通信链路是否带缓冲区
（3）链路是单向还是双向等
2）数据格式
（1）字节流格式：接收方不保留各次发送之间的分界
（2）报文格式：接收方保留各次发送之间的分界。报文方式还可进一步分成定长报文/不定长报文和可靠报文/不可靠报文
3）收发操作的同步方式
（1）阻塞操作：指操作方要等待操作结束
（2）不阻塞操作：指操作提交后立即返回
4.4.4 Linux中的进程通信机制（不考）
4.5 死锁（重中之重）
4.5.1 死锁的基本概念
1）死锁的定义
操作系统中多道进程的并发执行可以改善系统的资源利用率，但也可能出现若干进程都相互等待对方释放资源才能继续运行，否则就阻塞的情况。
死锁：系统中两个或者多个进程无限期地等待永远不会发生的条件，系统处于停滞状态，这种现象称为进程死锁，这一组进程就称为死锁进程。
3）产生死锁的原因
- 因为系统资源不足：如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的资源而陷入死锁
- 进程运行推进的顺序不合适：如上面打印机和扫描仪申请一例
- 资源分配不当：如上面内存分配一例
4）产生死锁的4个必要条件
① 互斥使用（资源独占）：一个资源每次只能给一个进程使用
② 不可强占（不可剥夺）：资源申请者不能强行地从资源占有者手中夺取资源，资源只能由占有者自愿释放
③ 请求和保持（部分分配，占有申请）：一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）
④ 循环等待：存在一个进程等待队列 {P1 , P2 , … , Pn}，其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路
4.5.2 死锁的预防——解决死锁的静态方法（斩草除根法）
1）基本策略
- 在系统设计时确定资源分配算法，保证不发生死锁
- 通过破坏产生死锁的4个必要条件之一来实现
- 由于系统存在很多独占资源，破坏“互斥使用”这一必要条件不太现实，重点探讨破坏后3种必要条件的方法
2）破坏“不可剥夺”条件
- 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若要再重新申请
3）破坏“请求和保持”条件
- 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配
4）破坏“循环等待”条件
- 采用资源有序分配法，把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配
- 例如，有资源1，2，3，…，m，现有n个进程来竞争这些资源，则须按下图所示递增顺序申请资源
4.5.3 死锁的避免——解决死锁的动态方法（先发制人法）
1）基本策略
- 在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配
- 关键在于区分安全状态与不安全状态，安全状态一定没有死锁发生，因而对进程的申请进行试分配，分配后系统状态为安全状态则满足，否则不满足
2）一个典型的死锁避免算法：银行家算法（重点）
① 银行家拥有一笔周转资金
② 客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款
③ 银行家应谨慎地贷款，防止出现坏账
④ 银行家采用的具体方法是看他是否有足够的剩余资金满足某一个需求的客户，如此反复下去
⑤ 如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准
4.5.4 死锁的检测与解除
1）基本策略
- 允许死锁发生
- 操作系统不断监视系统进展情况，判断死锁是否发生
- 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行
2）死锁的检测
- 检测时机：进程等待时、定时检测、资源利用率下降时
- 检测手段：利用进程-资源分配图
- 方框表示资源类（资源的不同类型）
- 方框中的黑圆点表示资源实例（存在于每个资源类中）
- 圆圈中加进程名表示进程
- 资源实例指向进程的一条有向边来表示分配边
- 进程指向资源类的一条有向边来表示申请边
- 进程-资源分配图中的死锁判断
- 无环路，则此时系统没有发生死锁
- 有环路，且每个资源类中仅有一个资源，则系统中发生了死锁。此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程
- 有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件
- 检测思路：检测“进程-资源分配图”是否可完全简化（能经过一系列简化使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的）
- 检测步骤：
①在图中找一个只有分配边的非孤立进程结点，去掉分配边，将其变为孤立结点；若找不到则转③
②将相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边，转①
③此时若图中有进程不是孤立结点，则此图不可完全简化，满足死锁的充分条件，系统为死锁状态（死锁定理）
3）死锁的解除——以最小的代价恢复系统的运行
- 资源剥夺法：当发现死锁后，从其他进程那里剥夺足够数量的资源给死锁进程，以解除死锁状态
- 撤消进程法：
- 撤消全部死锁进程，使系统恢复到正常状态。最简单但代价太大
- 按照某种顺序逐个撤消死锁进程，直到有足够的资源供其他未被撤消的进程使用，消除死锁状态为止
- 单独使用处理死锁的某种方法（预防、避免、检测与解除）并不能全面解决操作系统中遇到的所有死锁问题。
- 妥善的解决办法是将系统中的资源按层次分为若干类，对每一类资源使用最适合它的办法解决死锁问题。
4.6 管程
1）管程的提出
- 信号量的大量同步操作分散在各个进程中不便于管理和控制，读写和维护都很困难，还有可能导致系统死锁
- Dijkstra于1971年提出把所有进程对某一种临界资源的同步操作都集中起来，构成一个所谓的秘书进程（即管程）
- 凡要访问该临界资源的进程，都需先报告秘书，由秘书来实现诸进程对同一临界资源的互斥使用
2）管程的概念
- 一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据
- 管程用共享数据结构抽象地表示系统中的共享资源，而把对该共享数据结构实施的操作定义为一组过程，集中在一个模块中。操作系统或并发程序就由这样的模块构成，模块之间联系清晰，便于维护和修改，易于保证正确性
4.6.2 管程的特性
- 模块化：管程是一个基本程序单位，可以单独编译
- 抽象数据类型：管程中不仅有数据，而且有对数据的操作
- 信息掩蔽：管程外可以调用管程内部定义的一些函数，但函数的具体实现外部不可见
4.6.3 管程的作用
- 管程相当于围墙，将共享变量和对它进行操作的若干个过程围了起来
- 任何进程要访问临界资源时，都必须进入管程通过调用其内的某个函数进行申请
- 任何进程要归还资源时，也必须进入管程通过调用其内的某个函数进行归还
- 进程必须互斥访问管程，即同一时刻只能有一个进程在调用管程内的某个函数
京公网安备 11010502036488号