计算机操作系统笔记（4）--进程管理之进程同步

目的及要求

理解临界资源和临界区的概念

熟练掌握利用信号量机制解决进程同步问题

进程同步的主要任务

对多个相关进程在执行次序上进行协调，使并发执行的诸进进程之间能有效地共享资源和相互合作，从而使用程序的执行好具有可再现性。

一 进程的同步基本概念

①进程间两种形式的制约关系

1)间接相互制约关系：源于资源共享

2)直接相互制约关系：源于进程合作

②临界资源

临界资源（Critical Resource）：是指一段时间内只允许一个进程访问的资源。也称为独点资源。（重点3）

临界区（Critical Section）：是指每个进程中访问临界资源的那段代码。

③临界区

访问临界区的程序设计为：

1)对欲访问的临界资源进行检查

2)若此该未该访问，设正在访问的标志………………进入区

3)访问临界资源………………………………………………临界区

4)将正访问的标志恢复为未被访问的标志…………退出区

5)其余部分……………………………………………………剩余区

进程互斥：两进程不能同时进入同一临界区

代码实现

Repeat
    entry section
        critical section
    exit section
    remainder section
until false
           

④同步机制应遵循的规则

1)空闲让进

2)忙则等待

3)有限等待

4)让权等待

二 信号量机制（重点、难点）

1965年荷兰Dijkstra提出的信号量（Semaphores）是一种卓有成效的进程同步工具，在长期的应用 中，得到了很大的发展，从整型信号量经过记录型信号量，时而发展为“信号量集”机制。

1)信号量就是OS提供的管理公有资源的有效手段。

2)信号量代表可用资源实体的数量。

①整型信号量

定义：把整型信号量定义为一个用于表示资源数目的整型量S，除初始化外，仅能通过两个原子操作

wait(S)

，

signal(S)

来访问。

1)P操作 wait(S)：P(S)

While S<=0 do no-op; S:=S-1;

2)V操作 signal(S)：V(S)

S:=S+1

P、V操作是原子操作，不可中断。

整型信号量未遵循“让权等待”原则，导致忙等。

②记录型信号量

引入整型变量value（代表资源数目）、进程链表L（链接所有等待进程）

记录型数据结构

type semaphore=record
        value: integer;//资源数目
        L: list of process;//进程链表
    end;
           

定义记录型的信号量S

S:semaphore;

1)Wait操作（P操作）

a.申请资源，减量操作。

S.value:=S.value-1

b.当

S.value<0时，表示资源分配完，进行自我阻塞。

wait(S)
        begin
            S.value:=S.value-;
            if S.value< then
                block(S, L)
        end
           

2)Signal操作（V操作）

a.释放资源，增量操作。

S.value:=S.value+1

b.当

S.value<=0

时，唤醒

S.L

链表中的等待进程。

signal(S)
        begin
            S.value:=S.value+;
            if S.value<= then
                wakeup(S, L)
        end
           

正确使用时能实现同步和互斥。

value>0：代表可用资源的数量。

value<0：代表由于申请资源而阻塞的进程数量。

③AND型信号量

假设有两个进程A和B，共享数据D和E，为其分别设置互斥信号量Dmutex和Emutex，初值均为1。

Process A:
    //进入区
    wait(Dmutex);//a
    wait(Emutex);//b

    //临界区
    使用D和E

    //退出区
    Signal(Dmutex);
    Signal(Emutex);
           

Process B:
    //进入区
    wait(Emutex);//c
    wait(Dmutex);//d

    //临界区
    使用D和E

    //退出区
    Signal(Dmutex);
    Signal(Emutex);
           

执行a，于是Dmutex=0

执行c，于是Emutex=0

执行b，于是Emutex=-1，导致A阻塞

执行d，于是Dmutex=-1，导致B阻塞

共享的资源越多，死锁的可能越大。

AND同步机制的基本思想

将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给它。即对临界资源的分配采取原子操作。称为同时wait操作，即

Swait()

。

Swait(S1, S2, ..., Sn)
    if Si>= and ... and Sn>= then
        for i:= to n do
            Si:=Si-;
        endfor
    else
        Place the process in the waiting queue associated with the first Si found with Si<, and set the progress count of this process to the beginning or Swait operation
    endif
           

Ssignal(S1, S2, ..., Sn)
    for i:= to n do
        Si:=Si+;
        Remove all the process waiting in the queue associated with Si into the ready queue
    endfor
           

④信号量集

记录型信号量机制

1)每次只能获得或释放一个单位的资源，低效

2)每次分配前必须测试资源数量，看其是否大于其下界值

对AND信号量机制加以扩充

S为信号量；t为下限值；d为需求值

Swait(S1, t1, d1, ..., Sn, tn, dn)
    if Si>=t1 and ... and Sn>=tn then
        for i:= to n do
            Si:=Si-di;
        endfor
    else
        Place the excuting process in the waiting queue of the first Si<ti and set its program counter to the beginning of the Swait Operation
    endif
           

Ssignal(S1, d1, ..., Sn, dn)
    for i:= to n do
        Si:=Si+di;
        Remove all the process waiting in the queue associated with Si into the ready queue
    endfor
           

一般信号量集的几种特殊情况

1)Swait(S, d, d)：只有一个信号量S，允许每次申请d个资源，若现有资源数少于d，不予分配。（使用相对较少）

2)Swait(S, 1, 1)：蜕化为一个记录型信号量（S>1时）或互斥信号量（S=1时）。

3)Swait(S, 1, 0)：当S>=1时，允许多个进程进入某特定区，当S变为0时，阻止任何进程进入特定区，相关于可控开关。

三 信号量的应用

①利用信号量实现进程互斥

为使多个进程互斥的访问某临界资源，须为该资源设置一个互斥信号量mutex，并设其初始值为1（用来实现互斥关系的信号量初值一定为1），然后将各进程访问资源的临界区CS置于wai(mutex)和signal(mutex)之间即可。

Var mutex: semaphore := ;//mutex=1表示互斥信号量
    begin
    parbegin //表示process 1和process 2是可以并发执行的
        process ://进程1
            begin
                repeat
                    wait(mutex);//进入区
                    critical section//CS临界区
                    signal(nutex);//退出区
                    remainder section//RS剩余区
                until false;
            end

        process ://进程2
            begin
                repeat
                    wait(mutex);//进入区
                    critical section//CS临界区
                    signal(nutex);//退出区
                    remainder section//RS剩余区
                until false;
            end
    parend
           

若process 1先执行了wait(nutex)，当process 2执行wait(nutex)时会被block；当process 1执行到signal(nutex)后，就会调用wakeup唤醒process 2开始执行，反之亦然。

wait(nutex)和signal(nutex)必须成对出现。

②利用信号量实现前驱关系

设有两个并发执行的进程P1和P2，P1中有语句S1，P2中有语句S2，希望在S1执行后再执行S2。

使进程P1和P2共享一个公用信号量S，并赋予其初值为0（用来实现前驱关系的信号量初值一定是0）。

进程P1: S1;
    signal(S)
进程P2: wait(S);
    S2;
           

实现以下前驱关系

Var a, b, c, d, e, f, g: semaphore := , , , , , , ;
begin
    parbegin
        begin S1; signal(a); signal(b); end;
        begin wait(a); S2; signal(c); signal(d); end;
        begin wait(b); S3; signal(e); end;
        begin wait(c); S4; signal(f); end;
        begin wait(d); S5; signal(g); end;
        begin wait(f); wait(g); wait(e); S6; end;
    parend
edn
           

③利用记录型信号量实现同步

P1，P2两个进程因合作完成一项任务而共用一个变量x，进程P2将处理结果送入x，进程P1将x的结果打印。

即

P2：x=处理结果；

P1：Print(x);

如何实现该合作关系？

Var empty: semaphore := ;//变量x可赋值使用，即P1的print(x)已完成
Var full: semaphore := ;//变量x已赋值，即P2可print(x)
begin
    parbegin
        P1:
            begin
                repeat
                    ...
                    wait(full);//进入区
                    print(x);//临界区
                    signal(empty);//退出区
                    ...
                until false;
            end

        P2:
            begin
                repeat
                    ...
                    wait(empty);//进入区
                    x:=处理结果;//临界区
                    signal(full);//退出区
                    ...
                until false;
            end
    parend
end