并发性，是指进程的第一个操作和另一个进程的最后一个操作在时间上是叠加的。并发的进程可能是无关的，也可能是交往的。无关是指，它们在不同的集合变量上操作，所以一个进程的执行与其它并发进程的进展无关，即一个进程不会改变另一个进程的变量值。而交往，是共享某些资源，所以进程的执行会影响另外进程的运行结果。
Bernstein条件
并发进程的无关系是进程执行与时间无关的一个充要条件
设 R(pi)={a1,a2,…an}，表示程序 pi 在执行期间引用的变量集；W(pi)={b1,b2,…bm}，表示程序 pi 在执行期间改变的变量集，若两个程序能满足 Bernstein 条件、即变量集交集之和为空集：
R(p1)&W(p2) U R(p2)&W(p1) U W(p1)&W(p2)={ }
则并发进程的执行与时间无关。
与时间有关的错误
两个交往的并发进程，其中一个进程对另一个进程的影响常常是不可预期的，甚至是无法再现。
下面使用线程来代替进程，来看几个问题
例如：机票问题---结果不唯一
package Os;
public class Customer implements Runnable {
private int tick=60;//余票60
@Override
public void run() {
while (true){
if(tick==0){
System.out.println("票已卖完。。。");
break;
}
try {
Thread.sleep(20);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName()+"买了第====="+tick+" 票，此时还剩余"+(--tick));
}
}
public static void main(String[] args) {
Customer customer=new Customer();
Thread thread=new Thread(customer,"Jos"); // 顾客 jos
Thread thread1=new Thread(customer,"pob"); // 顾客 pob
thread.start();
thread1.start();
}
}
==== result:
pob买了第=====60 票，此时还剩余59
Jos买了第=====59 票，此时还剩余58
Jos买了第=====58 票，此时还剩余57
pob买了第=====58 票，此时还剩余57
pob买了第=====57 票，此时还剩余56
Jos买了第=====56 票，此时还剩余55
pob买了第=====55 票，此时还剩余53
Jos买了第=====55 票，此时还剩余54
Jos买了第=====53 票，此时还剩余52
pob买了第=====53 票，此时还剩余52
pob买了第=====52 票，此时还剩余50
Jos买了第=====52 票，此时还剩余51
Jos买了第=====50 票，此时还剩余49
pob买了第=====50 票，此时还剩余48
Jos买了第=====48 票，此时还剩余47
pob买了第=====48 票，此时还剩余47
Jos买了第=====47 票，此时还剩余46
pob买了第=====47 票，此时还剩余45
pob买了第=====45 票，此时还剩余44
Jos买了第=====44 票，此时还剩余43
Jos买了第=====43 票，此时还剩余42
pob买了第=====43 票，此时还剩余42
pob买了第=====42 票，此时还剩余41
Jos买了第=====41 票，此时还剩余40
pob买了第=====40 票，此时还剩余39
Jos买了第=====40 票，此时还剩余39
Jos买了第=====39 票，此时还剩余38
pob买了第=====38 票，此时还剩余37
pob买了第=====37 票，此时还剩余36
Jos买了第=====37 票，此时还剩余35
Jos买了第=====35 票，此时还剩余34
pob买了第=====35 票，此时还剩余33
pob买了第=====33 票，此时还剩余32
Jos买了第=====32 票，此时还剩余31
pob买了第=====31 票，此时还剩余30
Jos买了第=====31 票，此时还剩余30
Jos买了第=====30 票，此时还剩余29
pob买了第=====30 票，此时还剩余29
pob买了第=====29 票，此时还剩余28
Jos买了第=====28 票，此时还剩余27
pob买了第=====27 票，此时还剩余26
Jos买了第=====26 票，此时还剩余25
Jos买了第=====25 票，此时还剩余24
pob买了第=====24 票，此时还剩余23
pob买了第=====23 票，此时还剩余22
Jos买了第=====23 票，此时还剩余21
Jos买了第=====21 票，此时还剩余20
pob买了第=====20 票，此时还剩余19
pob买了第=====19 票，此时还剩余18
Jos买了第=====19 票，此时还剩余17
pob买了第=====17 票，此时还剩余16
Jos买了第=====17 票，此时还剩余15
pob买了第=====15 票，此时还剩余14
Jos买了第=====15 票，此时还剩余13
pob买了第=====13 票，此时还剩余12
Jos买了第=====13 票，此时还剩余12
pob买了第=====12 票，此时还剩余11
Jos买了第=====12 票，此时还剩余11
Jos买了第=====11 票，此时还剩余10
pob买了第=====10 票，此时还剩余9
Jos买了第=====9 票，此时还剩余7
pob买了第=====9 票，此时还剩余8
pob买了第=====7 票，此时还剩余5
Jos买了第=====7 票，此时还剩余6
pob买了第=====5 票，此时还剩余4
Jos买了第=====5 票，此时还剩余4
Jos买了第=====4 票，此时还剩余3 //
pob买了第=====4 票，此时还剩余3 //
pob买了第=====3 票，此时还剩余2
Jos买了第=====3 票，此时还剩余1
Jos买了第=====1 票，此时还剩余0
pob买了第=====1 票，此时还剩余0
票已卖完。。。
票已卖完。。。
显然出现了把一张票同时卖给两个旅客的情况。
例如：内存管理问题---永远等待
package Os;
import java.util.Random;
public class Booking {
private int collection=50;// 仓库
private int Max=80;
private int Min=10;
private class Borrow implements Runnable{
@Override
public void run() {
while (true){
if((collection-2)>Min){
collection=collection-2;
System.out.println(Thread.currentThread().getName()+"向仓库借了"+2+"的资源，现在还剩下"+collection+"资源");
try {
Thread.sleep(20);
} catch (InterruptedException e) {
e.printStackTrace();
}
}else {
System.out.println("仓库已到下限"+collection);
break;
}
}
}
}
private class Return implements Runnable{
@Override
public void run() {
while (true){
if((collection+2)<Max){
collection=collection+2;
System.out.println(Thread.currentThread().getName()+"向仓库存了"+2+"的资源，现在还剩下"+collection+"资源");
try {
Thread.sleep(20);
} catch (InterruptedException e) {
e.printStackTrace();
}
}else {
System.out.println("仓库已到上限"+collection);
break;
}
}
}
}
public void Store(){
Borrow borrow=new Borrow();
Return R=new Return();
Thread thread1=new Thread(R,"yyf");
Thread thread=new Thread(borrow,"petter");
thread1.start();
thread.start();
// System.out.println("当前资源为"+collection);
}
public static void main(String[] args) {
Booking booking=new Booking();
booking.Store();
}
}
===== RESULT
petter向仓库借了2的资源，现在还剩下50资源
yyf向仓库存了2的资源，现在还剩下50资源
yyf向仓库存了2的资源，现在还剩下50资源
petter向仓库借了2的资源，现在还剩下50资源
yyf向仓库存了2的资源，现在还剩下52资源
petter向仓库借了2的资源，现在还剩下52资源
yyf向仓库存了2的资源，现在还剩下50资源
petter向仓库借了2的资源，现在还剩下50资源
yyf向仓库存了2的资源，现在还剩下50资源
petter向仓库借了2的资源，现在还剩下50资源
yyf向仓库存了2的资源，现在还剩下52资源
petter向仓库借了2的资源，现在还剩下52资源
yyf向仓库存了2的资源，现在还剩下54资源
petter向仓库借了2的资源，现在还剩下52资源
petter向仓库借了2的资源，现在还剩下50资源
yyf向仓库存了2的资源，现在还剩下50资源
yyf向仓库存了2的资源，现在还剩下52资源
petter向仓库借了2的资源，现在还剩下50资源
petter向仓库借了2的资源，现在还剩下48资源
yyf向仓库存了2的资源，现在还剩下50资源
petter向仓库借了2的资源，现在还剩下52资源
yyf向仓库存了2的资源，现在还剩下52资源
petter向仓库借了2的资源，现在还剩下50资源
yyf向仓库存了2的资源，现在还剩下50资源
yyf向仓库存了2的资源，现在还剩下52资源
petter向仓库借了2的资源，现在还剩下50资源
petter向仓库借了2的资源，现在还剩下48资源
yyf向仓库存了2的资源，现在还剩下48资源
yyf向仓库存了2的资源，现在还剩下46资源
petter向仓库借了2的资源，现在还剩下46资源
petter向仓库借了2的资源，现在还剩下44资源
yyf向仓库存了2的资源，现在还剩下44资源
yyf向仓库存了2的资源，现在还剩下46资源
petter向仓库借了2的资源，现在还剩下46资源
petter向仓库借了2的资源，现在还剩下44资源
yyf向仓库存了2的资源，现在还剩下44资源
yyf向仓库存了2的资源，现在还剩下46资源
petter向仓库借了2的资源，现在还剩下44资源
petter向仓库借了2的资源，现在还剩下44资源
yyf向仓库存了2的资源，现在还剩下44资源
petter向仓库借了2的资源，现在还剩下42资源
yyf向仓库存了2的资源，现在还剩下44资源
yyf向仓库存了2的资源，现在还剩下46资源
petter向仓库借了2的资源，现在还剩下44资源
petter向仓库借了2的资源，现在还剩下42资源
yyf向仓库存了2的资源，现在还剩下44资源
petter向仓库借了2的资源，现在还剩下42资源
yyf向仓库存了2的资源，现在还剩下42资源
petter向仓库借了2的资源，现在还剩下44资源
yyf向仓库存了2的资源，现在还剩下44资源
yyf向仓库存了2的资源，现在还剩下46资源
petter向仓库借了2的资源，现在还剩下44资源
...
程序陷入了死循环之中，因为存在还未借出，已经还回来的情况
2、进程的交互
进程存在两种基本关系：竞争和协作
- 竞争：系统中多个进程共有一套系统资源，必然会出现多个进程竞争资源的问题。同时，竞争会出现两个问题：死锁和饥饿：若解决竞争问题，采用进程的互斥
+ 死锁：一组进程如果都获得了部分资源，还想要得到其他进程所占有的资源，最终所有的进程将陷入死锁
+ 饥饿：三个进程p1,p2,p3均要周期性的访问资源R，若p1占有资源，p2,p3等待资源，p1离开临界区时，p3获得资源R。若p3退出资源区后p1又获取到了R。那么p2就得不到资源R，出现了饥饿。 - 协作：某些进程为完成同一任务需要分工协作，进程间的协作可以是双方不知道对方名字的间接协作，例如通过共享访问一个缓冲区进行松散式协作；也可以是双方知道对方名字，直接通过通信进行紧密式协作。
进程的同步，是解决进程间协作挂你的手段。指一个进程的执行依赖于另一个进程的消息，当一个进程没有得到来自于另一个进程的消息时则等待，直到消息到达才被唤醒。特别的，互斥也是同步的一部分
3、临界区管理
3.1、互斥与临界区
上述售票的例子，发生错误，原因就在于两个进程交叉访问了共享变量。我们把并发进程中与共享变量有关的程序称为：临界区，共享变量代表的资源，称为连接资源
对若干个进程共享一个变量的相关的临界区，有三个调度原则：
- 一次至多一个进程能够在它的临界区内；
- 不能让一个进程无限地留在它的临界区内；
- 不能强迫一个进程无限地等待进入它的临界区。特别，进入临界区的任一进程不能妨碍正等待进入的其它进程的进展；
- 我们可把临界区的调度原则总结成四句话：无空等待、有空让进、择一而入、算法可行。
3.2、临界区管理的尝试
Dekker算法
Dekker算法能保证进程互斥的进入临界区，用一个指针turn来表示应该哪一个进入临界区。turn=1代表进程p1进入临界区，若turn=2，则代表进程p2可以进入临界区。其算法程序如下：
turn:integer;
turn := 1;
process P1
begin
while turn = 2 do [ ]；
临界区;
turn = 2；
end;
process P2
begin
while turn = 1 do [ ]；
临界区;
turn = 1；
end;
Java
package Os;
import java.util.Random;
public class Booking {
private int collection=50;// 仓库
private int Max=80;
private int Min=10;
private int turn=1;
private class Borrow implements Runnable{
@Override
public void run() {
while (turn==2){
System.out.println("正在往仓库内存储资源");
try {
Thread.sleep(20);
} catch (InterruptedException e) {
e.printStackTrace();
}
turn=1;
break;
}
if(turn==1){
if((collection-2)>Min){
collection=collection-2;
System.out.println(Thread.currentThread().getName()+"向仓库借了"+2+"的资源，现在还剩下"+collection+"资源");
}else {
System.out.println("仓库已到下限"+collection);
}
}
}
}
private class Return implements Runnable{
@Override
public void run() {
while (turn==1){
System.out.println("正在从仓库内取资源");
try {
Thread.sleep(20);
} catch (InterruptedException e) {
e.printStackTrace();
}
turn=2;
break;
}
if(turn==2){
if((collection+2)<Max){
collection=collection+2;
System.out.println(Thread.currentThread().getName()+"向仓库存了"+2+"的资源，现在还剩下"+collection+"资源");
}else {
System.out.println("仓库已到上限"+collection);
}
}
}
}
public void Store(){
Borrow borrow=new Borrow();
Return R=new Return();
int n=20;
while (n>=1){
Thread thread1=new Thread(R,"return"+n);
Thread thread=new Thread(borrow,"borrow"+n);
thread1.start();
thread.start();
n--;
}
// System.out.println("当前资源为"+collection);
}
public static void main(String[] args) {
Booking booking=new Booking();
booking.Store();
}
}
===RESULT
正在从仓库内取资源
borrow20向仓库借了2的资源，现在还剩下48资源
正在从仓库内取资源
正在从仓库内取资源
borrow19向仓库借了2的资源，现在还剩下46资源
borrow18向仓库借了2的资源，现在还剩下44资源
正在从仓库内取资源
borrow17向仓库借了2的资源，现在还剩下42资源
正在从仓库内取资源
borrow16向仓库借了2的资源，现在还剩下40资源
正在从仓库内取资源
borrow15向仓库借了2的资源，现在还剩下38资源
正在从仓库内取资源
borrow14向仓库借了2的资源，现在还剩下36资源
正在从仓库内取资源
borrow13向仓库借了2的资源，现在还剩下34资源
正在从仓库内取资源
borrow12向仓库借了2的资源，现在还剩下32资源
正在从仓库内取资源
borrow11向仓库借了2的资源，现在还剩下30资源
正在从仓库内取资源
borrow10向仓库借了2的资源，现在还剩下28资源
正在从仓库内取资源
borrow9向仓库借了2的资源，现在还剩下26资源
正在从仓库内取资源
borrow8向仓库借了2的资源，现在还剩下24资源
正在从仓库内取资源
borrow7向仓库借了2的资源，现在还剩下22资源
正在从仓库内取资源
正在从仓库内取资源
borrow6向仓库借了2的资源，现在还剩下20资源
正在从仓库内取资源
borrow5向仓库借了2的资源，现在还剩下18资源
borrow4向仓库借了2的资源，现在还剩下16资源
正在从仓库内取资源
正在从仓库内取资源
borrow3向仓库借了2的资源，现在还剩下14资源
borrow2向仓库借了2的资源，现在还剩下12资源
正在从仓库内取资源
仓库已到下限12
return20向仓库存了2的资源，现在还剩下14资源
return18向仓库存了2的资源，现在还剩下16资源
return19向仓库存了2的资源，现在还剩下18资源
return14向仓库存了2的资源，现在还剩下20资源
return15向仓库存了2的资源，现在还剩下22资源
return16向仓库存了2的资源，现在还剩下24资源
return17向仓库存了2的资源，现在还剩下26资源
return11向仓库存了2的资源，现在还剩下28资源
return12向仓库存了2的资源，现在还剩下30资源
return13向仓库存了2的资源，现在还剩下32资源
return10向仓库存了2的资源，现在还剩下34资源
return8向仓库存了2的资源，现在还剩下36资源
return9向仓库存了2的资源，现在还剩下38资源
return4向仓库存了2的资源，现在还剩下40资源
return6向仓库存了2的资源，现在还剩下42资源
return5向仓库存了2的资源，现在还剩下44资源
return7向仓库存了2的资源，现在还剩下46资源
return1向仓库存了2的资源，现在还剩下48资源
return2向仓库存了2的资源，现在还剩下50资源
return3向仓库存了2的资源，现在还剩下52资源
显然此种方法为，强制两个进程交替执行，使共享资源的使用效率不高；
Peterson算法
为了克服 Dekker 算法中对共享资源必须交替使用的限制，可采用 Peteron 算法来
解决互斥进入临界区的问题。此方法为每个进程设置一个标志，当标志为 true 时表示
该进程要求进入临界区。另外再设置一个指针 turn 以指示可以由哪个进程进入临界区，
当 turn=i 时则可由进程 Pi 进入临界区。Petrson 算法的程序如下
inside1,inside2:boolean;
turn:integer;
turn := 1;
inside1 := false; /* P1 不在其临界区内 */
inside2 := false; /* P2 不在其临界区内 */
process P1
begin
inside1 := true；
turn := 2；
while (inside2 and turn=2)
do begin end；
临界区;
inside1 := false；
end;
process P2
begin
inside2 := true；
turn := 1；
while (inside1 and turn=1)
do begin end；
临界区;
inside2 := false；
end;
3.3、实现临界区管理的硬件设施
以上两个算法，可能出现这两条标志位的指令执行时，出现中断，从而导致执行的不正确。因此引入了一个概念锁，开始时锁是开的，在一个进程进入临界区时便把锁锁上，以防止其他进程进入临界区。知道此进程离开临界区，锁才打开。
关中断
当进入锁测试之前关闭中断，直到完成锁测
试并上锁之后再开中断。在这一短暂的期间，计算机系统不响应中断，因此不会转向调度，也就不会引起进程或线程切换，从而保证了锁测试和上锁操作的连续性和完整性，有效的实现了临界区管理。但关中断时间过长会影响系统效率，关中断方法也不适用于多 CPU 系统。
测试并建立指令
硬件提供的指令TS ：TS(x),若x=true,x:false;return true,否则return false;
对换指令
swap指令，是交换两个子的内容，处理过程描述如下：
swap(a,b):temp:=a; a:b; b:temp;
网友评论