一、程序的并发:
并发
并发性：指两个或多个事件在同一时间间隔内发生。 程序的并发性是宏观上一段时间内多道程序同时运行。
单处理器的并发性:
每一时刻点只能执行一道程序，进程走走停停。
微观上多道程序交替执行。
(并发：是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，但任一个时刻点上只有一个程序在处理机上运行。)
1.单道程序的顺序执行及特征
（1）程序执行有固定的时序:
输入进程1 -> 计算进程1 - 输出进程1 -输入进程2 -计算进程2 -输出进程2 ......
（2）特征
顺序性、封闭性、可再现性。
2.多道程序的并发执行
（1）
多个程序的并发执行1.png
多个程序的并发执行2.png
（2）特征：
间断性、失去封闭性：主要由共享资源引起、不可再现性。
（3）思考？
有2个循环程序A和B，它们共享一个变量N，程序A每执行一次时，都要做N:=N+1; B则每次要执行Print(N), 然后再做N:=0. 若程序A,B以不同的速度运行有以下三种不同的结果.
N:=N+1在print(N)和N:=0之前，则N值分别为 n+1,n+1,0.
N:=N+1在print(N)和N:=0之后，则N值分别为 n,0，1.
N:=N+1在print(N)和N:=0之间，则N值分别为 n,n+1,0.
但这不是我们要的。
（3）如何保证并发执行的顺序性特征？
答案：引入同步控制机制。
进程的并发执行，协同工作就是进程同步。
3.前驱图 : 必须不存在循环
前趋图是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系。
→={(Pi, Pj)|Pi must complete before Pj may start}, 如果(Pi, Pj)∈→,可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。
每个结点还具有一个权重(Weight)，用于表示该结点所含有的程序量或结点的执行时间。
前趋图.png
对于图 (a)所示的前趋图， 存在下述前趋关系：
P1→P2, P1→P3, P1→P4, P2→P5, P3→P5, P4→P6, P4→P7, P5→P8, P6→P8, P7→P9, P8→P9
或表示为：
P={P1, P2, P3, P4, P5, P6, P7, P8, P9}
→={ (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7),
(P5, P8), (P6, P8), (P7, P9), (P8, P9)}
应当注意，前趋图中必须不存在循环，但在图b中却有着下述的前趋关系：S2→S3, S3→S2
二、进程同步
1.基本概念
（1）同步：
并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序执行有可再现性。
（2）互斥：
两个并行的进程A、B，如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。
互斥是一种特殊的同步。
（3）进程两种形式的制约关系
进程间接制约关系：源于资源共享，需互斥地访问临界资源。
进程直接制约关系：源于相互合作
2.临界资源、临界区
（1）临界资源:
把在一段时间内只允许一个进程访问的资源称为临界资源或独占资源。
打印机等物理设备；软件使用的栈、变量。引起不可再现性是因为临界资源没有互斥访问。
（2）临界区：(critical section)
临界区：进程中访问临界资源的那段代码。
临界区.png
临界区1.png
3.解决同步问题的工具：信号量机制
（1）整型信号量 : PV操作
整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为： wait(S): while S≤0 do no-op S∶=S-1; signal(S): S∶=S+1;
弊端分析：不符合让权等待原则。
PV操作1.png
//semaphore:只是用来记录有多少个线程正在使用他（他并没有互斥的性质，他可以被多个线程拥有)。
//Parbegin 和 Parend中间会来夹着几个进程:process1、process2...，意思是这里面的进程 是可以并发执行的，里面的进程就需自要利用到信号量机制了。
// Begin 、 End :
例1：
设系统中有两个进程P1、P2，P1进程负责计算数据，将结果放入缓冲区Buf，P2进程从缓冲区Buf中取数据输出。试写出两个进程的同步算法。
semaphore be=1,bf=0;
//semaphore只是用来记录有多少个线程正在使用他（他并没有互斥的性质，他可以被多个线程拥有）
Parbegin
//parbegin和parend中间会来夹着几个进程:process1、process2...，意思是这里面的进程 是可以并发执行的，里面的进程就需自要利用到信号量机制了。
P1: Begin
*************************************
Repeate
计算数据Data；
Wait（be）；
Data=>Buf；
Signal（bf）；
Until false；
*********************************** //临界区
End
P2: Begin
*************************************
Repeate
Wait（bf）；
取Data；
Signal(be)；
Until false；
*************************************
End
Parend.
PV操作.png
同步机制应遵循的规则 ：
进程执行结果可再现性的保证：
(1) 空闲让进。进入临界区
(2) 忙则等待。 临界资源
(3) 有限等待。不死等 公平性
(4) 让权等待。不能进入临界区放权 效率
4.改进的信号量机制
(1)记录型信号量
(2)AND型信号量
(3)集合型信号量
6.锁机制
在多线程编程中，操作系统引入了锁机制。通过锁机制，能够保证在多核多线程环境中，在某一个时间点上，只能有一个线程进入临界区代码，从而保证临界区中操作数据的一致性。
大部分同步方案均采用某个物理实体（如锁、信号灯等）实现通信，进程通信原语中关锁（lock）和开锁（unlock）是最简单的原语。在这两个原语中设置一个公共变量x代表某个临界资源的状态。如： x=0，表示资源可用(开锁) x=1，表示资源正在使用。(上锁)
网友评论