operating system

思考以下问题

  1. 为什么要引入进程同步的概念?
  2. 不同的进程之间会存在什么关系?
  3. 当单纯用本文介绍的方法解决这些问题时会遇到什么新的问题吗?

1. 进程同步的基本概念

1.1 临界资源

临界资源时一个时刻只能由一个进程使用的资源。包括

  1. 硬件资源:打印机,磁带机等等。
  2. 软件资源:变量、表格、队列等等。

对临界资源的使用采用互斥方式,也就是说一个进程用完之后才轮到下一个进程用。

1.2 同步

多个进程之间有相互合作关系,进程 I 负责读入数据,进程 C 负责处理数据,进程 P 负责写入数据。这就涉及到了进行执行的先后关系。这叫直接相互制约。

多个进程需要用到统一资源,也就是资源共享,如果进程之间没有直接相互制约,那么谁先用也没有多大关系,但是有了相互制约,情况就不一样了。导致使用资源也有了先后顺序,这叫间接相互制约。

进程同步

例子中的 count 就是临界资源(共享资源)

1.3 互斥

1.4 临界区

进程中访问临界资源的代码段 。同类临界区则是涉及同一临界资源的不同进程中的临界区。

  1. 进入区

    进入临界区前要通过进入区,进入区检查临界资源使用情况的代码段。如果条件不合适,你就去不了临界区了。只能等,这不就是公交站台吗。

  2. 退出区

    执行完临界区的代码后,进入退出区,退出区是负责恢复临界资源访问标志的代码段。

临界资源使用的同步准则有如下四点(熟记)

  1. 空闲让进:(提高效率)
  2. 忙则等待:(解决互斥)
  3. 有限等待:我的忍耐是有限的(以免死等)
  4. 让权等待:放弃占用 CPU(把机会留给更需要的人)

临界资源的状态判断与设置

Pi: repeat                             	Pj: repeat
    while flag do no_op                     while flag do no_op
    flag := true;                      	    flag := true;
    临界区代码                                临界区代码
    flag := false;                          flag := false;
        :                                       :
Until false;                            Until false;			

这个例子中,可能出现 “同时进入” 的问题,因此不符合 “忙则等待” 准则。因为判断 flag 和设置 flag 不是同时发生的,在 Pi 设置 flag 之前 Pj 就进来了。

因此对临界资源状态(是否正在使用)必须判断与设置同时进行,即判断与状态设置(状态改变)为原子操作,否则就会出现问题。

2. 实现临界区互斥的基本方法

2.1 软件实现方法

2.2 硬件实现方法

3. 信号量

信号量(Semaphore)是一种特殊的变量(S),除初始化外,对信号量变量(S)的操作只能由两个标准的原子操作(不可中断)实现,分别是

wait(S):等待操作(也叫 P 操作)

signal(S):发信号操作(也叫 V 操作)

信号量变量是由一个整型数和一个阻塞等待进程链表构成的记录型数据结构

type semaphore = record
	value: integer;
	L: list of process;
end;

所有对同一信号量进行操作且进入等待状态的进程,都自动进入阻塞等待(让权等待)状态,并将其挂在该信号量阻塞等待队列 L 中。

3.1 整型信号量

存在 “忙等” 现象 。

3.2 记录型信号量

  1. P 原子操作(wait)

    procedure wait(s);
    var s: semaphore;
    begin
        s.value := s.value  1;
        if s.value < 0 then block(s.L);
    end;
       
    

    小于 0 表示没有资源了,所以要睡眠等待。

  2. V 原子操作(signal)

    procedure signal(s);
    var s: semaphore;
    begin
        s.value := s.value + 1;
        if s.value <= 0 then wakeup(s.L);
    end;
    

    V 操作就是用完资源归还,value 小于等于 0 说明阻塞队列非空,可以叫醒一个进程。

3.3 利用信号量实现同步

S1 … S7 分别为进程 P1 … P7 的执行部分,它们的执行顺序如下图所示

信号量例题

var a, b, c, d, e, f, g, h: semaphore := 0, 0, 0, 0, 0, 0, 0, 0; //初值为0
P1: begin S1; signal(a); signal(b); end;
P2: begin wait(a); S2; signal(c); end;
P3: begin wait(b); S3; signal(d); end;
P4: begin wait(c); S4; signal(e); signal(f); end;
P5: begin wait(e); S5; signal(g); end;
P6: begin wait(f); wait(d); S6; signal(h);
P7: begin wait(g); wait(h); S7; end;

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

例如前面的银行存款问题,count 是共用变量(即共享资源),采用 mutex 互斥信号量实现互斥访问

var mutex: semaphore := 1;          //定义信号量变量,初值为1

//增加存款进程                //减少存款进程
procedure P1;               procedure P2;        
begin                       begin
    wait(mutex);                wait(mutex);
    count += 300;               count -= 200;
    signal(mutex);              signal(mutex);
end;                        end;

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

3.6 分析进程同步和互斥问题的方法步骤

3.7 and 型信号量机制

将进程运行过程中需要的所有临界资源,一次性地全部分配给进程(要么全部分配,要么一个也不分配)。

进程使用完后再一起释放。

针对死锁问题。

P 原子操作(Swait)

procedure Swait(s1, s2, , sn);
var s1, s2, , sn: semaphore;
begin
    if  (s1 >= 1) and  and (sn >= 1) 
    then {for i := 1 to n do  si := si  1; 
            return true;}
    else  {将程序计数器设置为本函数开始处;
             将进程插入阻塞队列;}
end;

V 原子操作 (Ssignal)

procedure Ssignal(s1, s2, , sn);
var s1, s2, , sn: semaphore;
begin
    for i := 1 to n do  si := si + 1; 
    将与si有关的进程从阻塞队列中唤醒
end;

3.8 一般信号量机制

进程运行需要多个临界资源。

一次需要 N 个同类临界资源。

大于 t 个同类临界资源才准予分配。

P 原子操作 (Swait)

procedure Swait(s1, t1, d1; ; sn, tn, dn);
var s1, s2, , sn: semaphore;
begin
    if  (s1 >= t1) and  and (sn >= tn) 
    then  {for i := 1 to n do  si := si  di; 
              return true; }
    else  {将程序计数器设置为本函数开始处;
             将进程插入阻塞队列; }
end;

V 原子操作(Ssignal)

procedure Ssignal (s1, d1; ; sn, dn);
var s1, s2, , sn: semaphore;
begin
    for i := 1 to n do  si := si + di; 
    将与si有关的进程从阻塞队列中唤醒
end;

一般信号量集特例

Swait(s,d,d) :一个信号量,每次同时分配 d 个同类资源。

Swait(s,1,1) :等效于记录型信号量。也就是互斥信号量。

Swait(s,1,0) :s=1 运行多个进程进入特定区,s=0阻止任何进程进入特定区。

4. 管程

4.1 管程的定义

临界区分散在各个进程之中,不便于管理和控制,而且很多临界区的操作是相同的,重复编写,使进程结构不清晰。如果编程出现差错,不便于检查,且会带来严重后果。

管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作,这组操作能同步进程和改变管程中的数据。

管程实际上是一种能实现进程同步的特殊的子程序(函数、过程、数据)的集合。

管程由以下部分组成

  1. 名称:该管程的标识。
  2. 共享变量说明:局部于管程的变量说明(包括特殊同步变量)。
  3. 一组过程(函数):对该数据结构进行操作的程序段(含有相当于临界区代码段)。
  4. 初始化:对局部于管程的数据设置初始值。

进程访问临界资源,必须经过管程,管程每次只允许一个进程进入,即只要某个进程进入了管程,则要么执行完成,要么因故阻塞,然后下一个进程才可以进入管程。

设置条件变量(相当于互斥信号量)x,当临界资源被占用,执行 x.wait,将进程挂在 x 条件变量的阻塞等待队列中,当临界资源已空闲,执行 x.signal,从 x 条件变量的阻塞等待队列中,唤醒第一个进程。

monitor

4.2 管程的组成

4.3 管程的基本特性

使用临界资源的进程进行调用时非常简单。

进程结构清晰。

易于差错

4.4 进程和管程之间的比较‘

进程定义私有 PCB,管程定义公共数据结构。 进程顺序执行操作,管程实现同步操作。 进程提高系统并发性,管程解决资源互斥访问。 进程调用管程,管程被进程所调用。 进程之间可以并发,管程不能与调用者并发。 进程具有动态性,管程是资源管理模块。

5. 经典同步问题

5.1 生产者-消费者问题

5.2 读者-写者问题

5.3 哲学家进餐问题

5.4 吸烟者问题

6. 本节小结