进程同步问题

进程同步

进程同步的基本概念

引入进程后,如果不能采取有效措施,对多个进程的运行妥善的管理,必然会因为这些进程对系统资源的无序争夺给系统造成混乱,因此需要引入进程同步机制,在这之前,先介绍几个概念。

进程制约关系

进程制约分为间接相互制约关系和直接相互制约关系。比如打印机这种只能互斥访问的临界资源,各进程之间无形中就形成了这种间接的相互制约的关系。而直接相互制约关系源于进程间为完成同一项任务的相互合作。

临界资源与临界区

临界资源:一次仅能为一个进程所使用的资源 ,比如打印机,磁带机,内存变量等。对于临界资源,各进程访问时是一种排他性的互斥访问。

临界区:进程中访问临界资源的代码段称为临界区。临界资源访问互斥==临界区访问互斥

每个进程在进入临界区之前,应先对欲访问的临界资源进行检查,看他是否正被访问。如果此刻临界资源未被访问,进程便可进入临界区对该资源进行访问,并设置它正在被访问标志;如果此刻该临界资源正被某进程访问,则本进程不能进入临界区。

1
2
3
4
5
6
while(TRUE){
进入区 //检查临界资源使用情况
临界区 !!
退出区 //告诉系统临界资源访问完毕
剩余区
}

同步机制遵循原则

空闲让进 :当无进程处于临界区时,请求进入临界区的进程可立即进入

忙则等待 :当已有进程进入临界区时,其他试图进入临界区进程须等待

有限等待 :对要求访问临界资源进程,保证能在有限时间内进入临界区 ,避免”死等“状态

让权等待 :当进程不能进入临界区时,应立即释放处理机,而不是“空等”时间片转完。

下面将逐个介绍上面的四个原则的实现方式,其中1,2必须实现,3,4锦上添花。

实现进程同步的早期方法

这里不详细说,具体请自行百度。这里仅说一下判断思想:就是牢记 并发执行,所以不一定什么时候时间片就用完了,然后就会切换进程,所以就是看这个过程中有没有漏洞。

  1. 按需访问 违背 忙则等待,让权等待 (×)

  2. 轮询 严格限制了资源访问顺序,违背 让权等待 (×)

  3. 访前先看 违背 空闲让进,让权等待 (×)

  4. Peterson算法,1981

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #define  FALSE  0 
    #define TRUE 1
    #define N 2 // 进程的个数
    int turn; // 轮到谁?
    int interested[N]; // 兴趣数组,初始值均为FALSE

    void enter_region ( int process){ // process = 0 或 1
    int other; // 另外一个进程的进程号
    other = 1 - process;
    interested[process] = TRUE;// 表明本进程感兴趣
    turn = process; // 设置标志位
    while( turn == process && interested[other] == TRUE);
    }
    void leave_region ( int process) {
    interested[process] = FALSE; // 本进程已离开临界区
    }

    任何一条高级语言在执行过程中都可能发生进程切换,所以上面的while判定条件就是出于这方面的考虑。上述函数的用法如下所示,

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    Program P1: 
    Begin
    repeat
    enter_region(0);
    critical section ;
    leave_region(0);
    remainder section ;
    until false
    End
    Program P2:
    Begin
    repeat
    enter_region(1 );
    critical section ;
    leave_region(1);
    remainder section ;
    until false
    End

分析可知,该算法解决了空闲让进,忙则等待,有限等待,但仍没有解决让权等待问题

  1. SWAP指令 这是从硬件层面来实现的互斥,但是还是会出现”忙等“状态,即仍未解决让权等待问题。

信号量机制

1965年,该机制由荷兰学者Dijkstra提出。

整型信号量

该机制引用了一个整型信号量S和两个原子操作(在执行过程中不会被打断的操作)wait() 和 signal(),并且规定: 除初始化外,S只能够由wait/signal访问 。

1
2
3
4
5
6
7
8
int S = 1;
wait(S){ //进入区位置引用,原子操作
while(S<=0);
S--;
}
signal(S){ //退出区位置引用,原子操作
S++;
}

显而易见,上述算法仍未遵循“让权等待”的准则,为了解决这个问题,提出了下面的算法。

记录型信号量

未完待续…

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------