计算机操作系统(6) 并发程序设计
2023-08-09 14:53:19 # NJU # 计算机操作系统

第六章 并发程序设计

6.1 并发进程

6.1.1 顺序程序设计

  • 一个进程在处理器上的顺序执行是严格按序的, 一个进程只有当一个操作结束后, 才能开始后继操作
  • 顺序程序设计是把一个程序设计成一个顺序执行的程序模块, 顺序的含义不但指一个程序模块内部, 也指两个程序模块之间

顺序程序设计特点

  • 程序执行的顺序性
  • 程序环境的封闭性
  • 执行结果的确定性
  • 计算过程的可再现性

6.1.2 进程的并发性

  • 进程的并发性(Concurrency)是指一组进程的执行在时间上是重叠的
  • 例如：有两个进程 A(a1、a2、a3) 和 B(b1、b2、b3) 并发执行, 若允许进程交叉执行, 如执行操作序列为 a1, b1, a2, b2, a3, b3 或 a1, a2, b1, b2, b3, a3 等, 则说进程 A 和 B 的执行是并发的
  • 从宏观上看, 并发性反映一个时间段中几个进程都在同一处理器上, 处于运行还未运行结束状态
  • 从微观上看, 任一时刻仅有一个进程在处理器上运行

并发程序设计

  • 使一个程序分成若干个可同时执行的程序模块的方法称并发程序设计(concurrent programming), 每个程序模块和它执行时所处理的数据就组成一个进程

进程的并发性

image-20221205105242312

  • 由于程序是按照 while(TRUE) {input, process, output} 串行地输入 - 处理 - 输出来编制的, 所以该程序只能顺序地执行, 这时系统的效率相当低
  • 如果把求解这个问题的程序分成三部分：
    • i: while(TRUE) {input, send}
    • p: while(TRUE) {receive, process, send}
    • o: while(TRUE) {receive, output}

image-20221205105403896

  • 每一部分是一个小程序, 它们可并发执行, 并会产生制约关系, 其中 send 和 receive 操作用于小程序之间通过通信机制解决制约关系, 以便协调一致地工作

并发进程的分类

  • 并发进程分类：无关的, 交互的
  • 无关的并发进程：一个进程的执行与其他并发进程的进展无关
    • 并发进程的无关性是进程的执行与时间无关的一个充分条件, 又称为Bernstein条件
  • 交互的并发进程: 不满足Bernstein条件, 一个进程的执行可能影响其他并发进程的结果

Bernstein条件

image-20221205105705207

  • 没有读写冲突与写写冲突

举例: 有如下分属四个进程中的四条语句：

  • S1: a := x + y
  • S2: b := z + 1
  • S3: c := a – b
  • S4: w := c + 1

于是有:

R(S1)={x, y}, R(S2)={z}, R(S3)={a, b}, R(S4)={c}；

W(S1)={a}, W(S2)={b}, W(S3)={c}, W(S4)={w}

S1和S2可并发执行, 满足Bernstein条件

其他语句并发执行可能会产生与时间有关的错误

与时间有关的错误

  • 对于一组交互的并发进程, 执行的相对速度无法相互控制, 各种与时间有关的错误就可能出现
  • 与时间有关错误的表现形式：
    • 结果不唯一
    • 永远等待

并发是开放的: 每执行完一条机器指令都有被抢占的风险

顺序是封闭的

机票问题

image-20221205110025898

  • 此时出现把同一张票卖给两个旅客的情况, 两个旅客可能各自都买到一张同天同次航班的机票, 可是, Aj 的值实际上只减去 1, 造成余票数不正确。特别是, 当某次航班只有一张余票时, 可能把一张票同时售给两位旅客

主存管理问题

image-20221206175155957

  • 由于 borrow 和 return 共享代表主存物理资源的临界变量 X, 对并发执行不加限制会导致错误, 例如, 一个进程调用borrow申请主存, 在执行比较 B 和 X 大小的指令后, 发现 B > X, 但在执行 {进程进入等待主存资源队列} 前, 另一个进程调用 return 抢先执行, 归还所借全部主存资源；这时, 由于前一个进程还未成为等待者, return中的 {释放等主存资源进程} 相当于空操作, 以后当调用 borrow 的应用进程被置成 {等主存资源} 时, 可能己经没有其他进程再来归还主存, 从而, 申请资源的进程处于永远等待状态

6.1.3 进程的交互: 竞争与协作

  • 进程之间存在两种基本关系：竞争关系和协作关系
  • 第一种是竞争关系, 一个进程的执行可能影响到同其竞争资源的其他进程, 如果两个进程要访问同一资源, 那么, 一个进程通过操作系统分配得到该资源, 另一个将不得不等待
  • 第二种是协作关系, 某些进程为完成同一任务需要分工协作, 由于合作的每一个进程都是独立地以不可预知的速度推进, 这就需要相互协作的进程在某些协调点上协调各自的工作。当合作进程中的一个到达协调点后, 在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己, 直到其他合作进程发来协调信号或消息后方被唤醒并继续执行

竞争关系带来的问题

  • 资源竞争的两个控制问题：
  • 一个是死锁 (Deadlock) 问题: 一组进程如果都获得了部分资源, 还想要得到其他进程所占有的资源, 最终所有的进程将陷入死锁
  • 一个是饥饿 (Starvation) 问题: 一个进程由于其他进程总是优先于它而被无限期拖延
  • 操作系统需要保证诸进程能互斥地访问临界资源, 既要解决饥饿问题, 又要解决死锁问题

竞争关系: 死锁

  • 死锁 : 一组进程因争夺资源陷入永远等待的状态
  • P0 和 P1 两个进程, 均需要使用 S 和 Q 两类资源, 每类资源数为1

image-20221207221321962

竞争关系: 进程的互斥

  • 进程的互斥(mutual exclusion) 是解决进程间竞争关系(间接制约关系)的手段。进程互斥指若干个进程要使用同一共享资源时, 任何时刻最多允许一个进程去使用, 其他要使用该资源的进程必须等待, 直到占有资源的进程释放该资源

协作关系: 进程的同步

  • 进程的同步(Synchronization) 是解决进程间协作关系(直接制约关系)的手段。进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于另一个协作进程的消息或信号, 当一个进程没有得到来自于另一个进程的消息或信号时则需等待, 直到消息或信号到达才被唤醒

进程的交互: 竞争与协作

  • 进程互斥关系是一种特殊的进程同步关系, 即逐次使用互斥共享资源, 是对进程使用资源次序上的一种协调

6.2 临界区管理

6.2.1 互斥与临界区

互斥与临界区

  • 并发进程中与共享变量有关的程序段叫“临界区”(critical section), 共享变量代表的资源叫“临界资源”
  • 与同一变量有关的临界区分散在各进程的程序段中, 而各进程的执行速度不可预见
  • 竞争条件(race condition)
  • 如果保证进程在临界区执行时, 不让另一个进程进入临界区, 即各进程对共享变量的访问是互斥的, 就不会造成与时间有关的错误

image-20221207224320111

临界区调度原则

  • 临界区调度原则(Dijkstra, 1965)：
    • 一次至多一个进程能够进入临界区内执行
    • 如果已有进程在临界区, 其他试图进入的进程应等待
    • 进入临界区内的进程应在有限时间内退出, 以便让等待进程中的一个进入

6.2.2 临界区管理的尝试

尝试一

image-20230202161342205

  • 存在的问题: 两个进程可能都进去

尝试二

image-20230202161443892

  • 存在的问题: 两个进程都进不去

实现临界区的软件算法: Peterson算法

image-20230202161817788

  • 下面这种方案也可以实现, 但是不满足通用性的要求
    • P0 和 P1 使用临界区的次序变成了完全一比一的交替方式

image-20221207233038513

  • P0中执行了turn=1, 暂时进不去, 等P1中执行turn=0, P0可以进去, P0使用完临界区, 退出临界区的时候, 将turn=0(好像是多余的), 此时P1还是进不去, 要等P0执行turn=1, 使得P1有机会进入临界区
  • 之后, P1退出临界区的时候, turn=1, P0暂时进不去, 等在P1中执行turn=0, P0可以再次进入临界区
  • 因此, P0和P1使用临界区的次序变成了完全一比一的交替方式, 这只能是临界区互斥使用的一个特例, 不能满足临界区互斥使用的完全随机性

6.2.3 实现临界区管理的硬件设施

关中断

  • 实现互斥的最简单方法
  • 关中断适用场合
  • 关中断方法的缺点

测试并建立指令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// TS指令的处理过程
bool TS(bool &x) {
    if(x) {
        x = false;
        return true;
    }
    else {
        return false;
    }
}

// TS指令实现进程互斥
bool s = true;
cobegin
process Pi() { //i=1，2，...，n
    while(!TS(s)); //上锁
    {临界区};
    s = true; //开锁
}
coend

对换指令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SWAP(bool &a，bool &b) {
    bool temp = a;
    a = b;
    b = temp;
}

//对换指令实现进程互斥
bool lock = false;
cobegin
Process Pi( ){ //i=1，2，...，n
    bool keyi = true;
    do {
        SWAP(keyi，lock);
    } while (keyi); //上锁
    {临界区};
    SWAP(keyi，lock); //开锁
}
coend

6.3 信号量与PV操作

6.3.1 信号量与PV操作的问题背景

并发程序设计的基本概念

image-20230202170410386

  • 临界资源：并发进程之间需要互斥使用的共享资源, 称为临界资源
    • 举例: 火车上的卫生间就是一种互斥使用的共享资源
    • 使用共享变量代表共享资源
    • 并发进程中与共享变量有关的程序段叫“临界区”(critical section)
    • 临界区：并发进程之间控制共享资源使用的程序段
  • 并发进程之间的关系

image-20230202170853336

“忙式等待”方法解决临界区调度问题的缺点

  • 临界区管理的简单方法（忙式等待/反复测试）
    1. 关中断
    2. 测试并建立指令
    3. 对换指令
    4. Peterson算法
  • 存在的问题
    1. 对不能进入临界区的进程, 采用忙式等待测试法, 浪费CPU时间
    2. 将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性, 加重用户编程负担
  • 通用的解决方案：信号量与PV操作

操作系统中“并发问题”解决方案的知识框架

image-20221207234329963

6.3.2 信号量与PV操作的基本原理

  • 前面方法解决临界区调度问题的缺点:
    1. 对不能进入临界区的进程, 采用忙式等待测试法, 浪费CPU时间
    2. 将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性, 加重用户编程负担
  • 1965年E.W.Dijkstra提出了新的同步工具—信号量和P、V操作原语(荷兰语中“检测(Proberen)”和“增量(Verhogen)”的头字母)
  • 一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值, 这种特殊变量就是信号量(semaphore), 复杂的进程协作需求都可以通过适当的信号结构得到满足

信号量与PV操作的数据结构与原语操作

设s为一个记录型数据结构, 一个分量为整型量value, 另一个为信号量队列queue, P和V操作原语定义

  • P(s): 将信号量 s 减 1, 若结果 < 0, 则调用 P(s) 的进程被置成等待信号量 s 的状态(阻塞态)
  • V(s): 将信号量 s 加 1, 若结果 <= 0, 则释放(唤醒)一个等待信号量 s 的进程, 使其转换为就绪态
  • 原语: CPU处于内核态, 在关中断环境下执行的一段指令序列
    • 原子性：不被中断, 确保安全且完整执行这段指令序列

强调：对于信号量, 只允许使用P, V原语操作访问信号量, 不能直接对信号量的整型值做读写操作, 也不能对信号量的队列做任何其他操作

image-20221208001244075

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct semaphore {
    int value;	// 信号量值
    struct pcb* list;	// 信号量队列指针
}
void P(semaphore s) { // also named wait
    s.value--;
    if (s.value < 0) {
        sleep(s.list); // 若信号量值小于0, 执行 P 操作的进程调用 sleep 阻塞自己, 被置成等待信号量 s 状态并移入 s 信号量队列, 转向进程调度程序
    }
}
void V(semaphore s) { // also named signal
	s.value++;
    if (s.value <= 0) {
        wakeup(s.list); // 若信号量值小于等于0, 调用 wakeup 从信号量 s 队列中释放一个等待信号量 s 的进程并转换成就绪态, 进程继续执行
	}
}

PV操作与进程状态转换模型

image-20230202171833199

PV操作与进程状态队列模型

image-20221208001550844

强调: 不同的进程因为请求不同资源, 将进入不同信号量的等待队列, 分为不同的等待队列进行管理

信号量与PV操作的推论

  • 推论1：若信号量 s 为正值, 则该值等于在封锁进程之前对信号量 s 可施行的 P 操作次数、亦等于 s 所代表的实际还可以使用的物理资源数
  • 推论2：若信号量 s 为负值, 则其绝对值等于登记排列在该信号量 s 队列之中等待的进程个数、亦即恰好等于对信号量 s 实施 P 操作而被封锁起来并进入信号量 s 队列的进程数
  • 推论3：通常, P 操作意味着请求一个资源, V 操作意味着释放一个资源。在一定条件下, P 操作代表阻塞进程操作, 而 V 操作代表唤醒被阻塞进程的操作

6.3.3 信号量的应用

信号量程序设计的一般结构

1
2
3
4
5
6
7
8
9
10
semaphore s = 1;
cobegin
    Process Pi { /* i=1，…，n */
        ...
        P(s);
        /* critical region 临界区*/
        V(s); 
        ...
    };
coend
  • 在表达纯粹互斥关系时信号量初值为 1, 且同一个信号量的PV操作处于同一侧进程中。但这种情形不适用于同步关系

信号量与PV操作控制并发进程之间的临界资源

image-20221208142449148

互斥问题: 飞机票问题

image-20221208145047961

  • 上面代码有缺陷: 将不同航班剩余票数合并为同一个信号量, 效率很低

  • 改进

image-20221208145205395

互斥问题: 哲学家就餐问题

有五个哲学家围坐在一圆桌旁, 桌中央有一盘通心面, 每人面前有一只空盘子, 每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面, 每个哲学家必须获得两把叉子, 且每人只能直接从自己左边或右边去取叉子

  • 哲学家顺时针编号

image-20221208145438484

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
semaphore fork[5];
for (int i=0;i<5;i++) {
    fork[i]=1;
}
// cobegin 并发开始
process philosopher_i() { //i=0，1，2，3，4
    while(true) {
        think();
        P(fork[i]); //先取右手的叉子
        P(fork[(i+1)%5]); //再取左手的叉子
        eat();
        V(fork[i]);
        V(fork[(i+1)%5]);
    }
}
// coend
  • 问题: 两个 P 操作之间存在缝隙, 如果哲学家进程均在取到第一个叉子后被中断, 会产生死锁
有若干种办法可避免这类死锁
  • 至多允许四个哲学家同时取叉子(C.A.R. Hoare方案)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
semaphore fork[5];
for (int i=0;i<5;i++) {
    fork[i]= 1;
}
semaphore room=4; //增加一个侍者, 设想有两个房间1号房间是会议室, 2号房间是餐厅
// cobegin
process philosopher_i(){ /*i=0, 1, 2, 3, 4 */
    while(true) {
        think();
        P(room); //控制最多允许4位哲学家进入2号房间餐厅取叉子
        P(fork[i];
        P(fork[(i+1) % 5]);
        eat();
        V(fork[i]);
        V(fork([i+1] % 5);
        V(room);
    }
}
// coend
  • 奇数号先取左手边的叉子, 偶数号先取右手边的叉子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void philosopher (int i) { 
    if (i % 2 == 0) {
        P(fork[i]); //偶数哲学家先右手
        P(fork[(i+1) % 5]); //后左手
        eat();
        V(fork[i]);
        V(fork[(i+1) % 5]);
    }
    else {
        P(fork[(i+1) % 5]); //奇数哲学家, 先左手
        P(fork[i]); //后右手
        eat();
        V(fork[(i+1) % 5]);
        V(fork[i]);
    }
}
  • 每个哲学家取到手边的两把叉子才吃, 否则一把叉子也不取(第五版教材, Page 188, AND型信号量)

同步问题: 生产者-消费者问题

有 n 个生产者和 m 个消费者, 连接在一个有 k 个单位缓冲区的有界缓冲上。其中, 生产者进程 Producer_i 和消费者进程 Consumer_j 都是并发进程, 只要缓冲区未满, 生产者 Producer_i 生产的产品就可投入缓冲区；只要缓冲区不空, 消费者进程 Consumer_j 就可从缓冲区取走并消耗产品

可能情形

  • n = 1, m = 1, k = 1

image-20230202194743796

  • n = 1, m = 1, k > 1

image-20230202194823170

  • n > 1, m > 1, k > 1

image-20230202194839839

同步问题: 苹果-橘子问题

image-20221208153217954

image-20221208153248165

信号量-前驱关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Semaphore s1=0; /*表示进程P1是否已经执行完成*/
Semaphore s2=0; /*表示进程P2是否已经执行完成*/
Semaphore s3=0; /*表示进程P3是否已经执行完成*/
Semaphore s4=0; /*表示进程P4是否已经执行完成*/
Semaphore s5=0; /*表示进程P5是否已经执行完成*/
main () {
cobegin
    P1();
    P2();
    P3();
    P4();
    P5();
    p6();
coend
}
image-20230710162452442 image-20230202210826126

读者/写者问题

读者与写者问题(reader-writer problem) (Courtois, 1971)也是一个经典的并发程序设计问题。有两组并发进程：读者和写者, 共享一个文件 F, 要求：

  1. 允许多个读者可同时对文件执行读操作
  2. 只允许一个写者往文件中写信息
  3. 任意写者在完成写操作之前不允许其他读者或写者工作
  4. 写者执行写操作前, 应让已有的写者和读者全部退出

使用PV操作求解该问题

读者优先

  • rmutex 控制对 read_count 的互斥访问；
  • 读者需要对互斥信号量 rmutex 进行排队；
  • 只有第一个读者需要对 wmutex 排队，后来的读者不需要对 wmutex 排队，可以插队到写者前面；
  • 为了保证读时不被打断，读时用 wmutex 信号量阻塞写者；当前所有读者读完后，写者才开始写。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
semaphore rmutex = 1; // 控制对 read_count 的互斥访问
semaphore wmutex = 1; // 控制对文件内容的互斥写
int read_count = 0;

// 读者进程
process reader_i() {
    while(true) {
        P(rmutex);
        if(read_count == 0)
            P(wmutex);
        read_count++;
        V(rmutex);
        
        read();
        
        P(rmutex);
        read_count--;
        if(read_count == 0)
            V(wmutex);
        V(rmutex);
    }
}

// 写者进程
process writer_i() {
    while(true) {
        P(wmutex);
        write();
        V(wmutex);
    }
}

写者优先

  • 后来的写者可以插队到先来的、还未开始读的读者前面；
  • 互斥变量 z 保证了每次最多只有一个读者在互斥变量 rmutex 排队；
  • “第一个”写者到来时，写者可以立刻对 rmutex 排队，且此时最多只有一个读者在 rmutex 排队；
  • “后来的”写者到来时，不用对 rmutex 排队，直接等前面的写者写完后继续写；
  • “最后一个”写者离开时，开放 rmutex 使得读者可以开始读；
  • 写者使用 rmutex 阻塞读者。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
semaphore x = 1, y = 1, z = 1; // read_count, write_count互斥
semaphore rmutex = 1, wmutex = 1; // 读锁、写锁
int read_count = 0, write_count = 0;

// 读者进程
process reader_i() {
    while(true) {
    	P(z);
        P(rmutex);
        P(x);
        if(read_count == 0)
            P(wmutex);
        read_count++;
        V(x);
        V(rmutex);
        V(z);

        read();

        P(x);
        read_count--;
        if(read_count == 0)
            V(wmutex);
        V(x);
    }
}

// 写者进程
process writer_i() {
    while(true) {
    	P(y);
        if(write_count == 0)
            P(rmutex);
        write_count++;
        V(y);

        P(wmutex);
        write();
        V(wmutex);

        P(y);
        write_count--;
        if(write_count == 0)
            V(rmutex);
        V(y);
    }
}

读写公平

  • 只比读者优先增加了一个互斥信号量 S；
  • 所有读者和写者一起对互斥信号量 S 排队，这样后来的读者无法插队到先来的写者前面；
  • 其他性质与读者优先相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
semaphore rmutex = 1; // 控制对 read_count 的互斥访问
semaphore wmutex = 1; // 控制对文件内容的互斥写
semaphore s = 1;
int read_count = 0;

// 读者进程
process reader_i() {
    while(true) {
        P(s);
        P(rmutex);
        if(read_count == 0)
            P(wmutex);
        read_count++;
        V(rmutex);
        V(s);
        
        read();
        
        P(rmutex);
        read_count--;
        if(read_count == 0)
            V(wmutex);
        V(rmutex);
    }
}

// 写者进程
process writer_i() {
    while(true) {
        P(s);
        P(wmutex);
        write();
        V(wmutex);
        V(s);
    }
}

image-20230202211221247

睡眠的理发师问题

理发店里有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子

如果没有顾客, 理发师便在理发椅上睡觉, 一个顾客到来时, 它必须叫醒理发师, 如果理发师正在理发时又有顾客来到, 如果有空椅子可坐, 就坐下来等待, 否则就离开

使用PV操作求解该问题

image-20230202211603175

农夫猎人问题

有一个铁笼子, 每次只能放入一个动物。猎手向笼中放入老虎, 农夫向笼中放入羊；动物园等待取笼中的老虎, 饭店等待取笼中的羊。请用P、V操作原语写出同步执行的程序

image-20230202211938726

银行业务问题

某大型银行办理人民币储蓄业务, 由 n 个储蓄员负责。每个顾客进入银行后先至取号机取一个号, 并且在等待区找到空沙发坐下等着叫号。取号机给出的号码依次递增, 并假定有足够多的空沙发容纳顾客。当一个储蓄员空闲下来, 就叫下一个号。

请用信号量和 PV 操作正确编写储蓄员进程和顾客进程的程序

image-20230202223152625

缓冲区管理

有 n 个进程将字符逐个读入到一个容量为 80 的缓冲区中(n > 1), 当缓冲区满后, 由输出进程 Q 负责一次性取走这 80 个字符。这种过程循环往复, 请用信号量和P、V操作写出 n 个读入进程(P1, P2, …Pn)和输出进程 Q 能正确工作的动作序列

image-20230202224056349

售票问题

汽车司机与售票员之间必须协同工作, 一方面只有售票员把车门关好了司机才能开车, 因此, 售票员关好门应通知司机开车, 然后售票员进行售票。另一方面, 只有当汽车已经停下, 售票员才能开门上下客, 故司机停车后应该通知售票员。假定某辆公共汽车上有一名司机与两名售票员, 汽车当前正在始发站停车上客, 试用信号量与P、V操作写出他们的同步算法

image-20230203124338266

吸烟者问题

一个经典同步问题：吸烟者问题(patil, 1971)。三个吸烟者在一个房间内, 还有一个香烟供应者。为了制造并抽掉香烟, 每个吸烟者需要三样东西：烟草、纸和火柴, 供应者有丰富货物提供。三个吸烟者中, 第一个有自己的烟草, 第二个有自己的纸, 第三个有自己的火柴。供应者随机地将两样东西放在桌子上, 允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者, 供应者再把两样东西放在桌子上, 唤醒另一个吸烟者。试用信号量和P、V操作求解该问题

image-20230203124508358

6.4 管程

6.4.1 管程和条件变量

为什么要引入管程？

  • 把分散在各进程中的临界区集中起来进行管理
  • 防止进程有意或无意的违法同步操作
  • 便于用高级语言来书写程序

管程定义和属性

  • 管程的定义
    • 管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块
  • 管程的属性
    • 共享性、安全性、互斥性

管程的形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type <管程名> = monitor {
    <局部变量说明>;
    <条件变量说明>;
    <初始化语句>;
    define <管程内定义的, 管程外可调用的过程或函数名列表>;
    use <管程外定义的, 管程内将调用的过程或函数名列表>;
    
    <过程名/函数名>(<形式参数表>) {
    	<过程/函数体>;
    }
    ...
    <过程名/函数名>(<形式参数表>) {
    	<过程/函数体>;
    }
}

管程的结构

image-20230203142923995

管程的条件变量

  • 条件变量: 是出现在管程内的一种数据结构, 且只有在管程中才能被访问, 它对管程内的所有过程是全局的, 只能通过两个原语操作来控制它
    • wait(): 阻塞调用进程并释放管程, 直到另一个进程在该条件变量上执行signal()
    • signal():
      • 如果存在其他进程由于对条件变量执行 wait() 而被阻塞, 便释放之
      • 如果没有进程在等待, 那么, 信号不被保存, 并不是立即退出管程等待队列，而是进入 next 信号量，以保证多个进程都可以正常退出。

管程问题讨论

  • 使用 signal 释放等待进程时, 可能出现两个进程同时停留在管程内。解决方法：
    • 执行 signal 的进程等待, 直到被释放进程退出管程或等待另一个条件变量
    • 被释放进程等待, 直到执行 signal 的进程退出管程或等待另一个条件
  • 霍尔(Hoare, 1974)采用第一种办法
  • 汉森(Hansen)选择两者的折衷, 规定管程中的过程所执行的signal操作是过程体的最后一个操作

6.4.2 管程的实现(Hoare方法)

  • 霍尔方法使用 P 和 V 操作原语来实现对管程中过程的互斥调用, 及实现对共享资源互斥使用的管理
  • 不要求 signal 操作是过程体的最后一个操作, 且 wait 和 signal 操作可被设计成可以中断的过程
  • 使用 signal() 释放一个等待进程时，霍尔管程让执行 signal() 的进程等待，直到被释放进程退出管程或等待另一个条件
  • 霍尔管程基于 PV 操作原语实现：
    • wait() 和 signal() 可以是程序过程
    • 可以用语言机制实现霍尔管程

Hoare管程数据结构

mutex

  • 对每个管程, 使用用于管程中过程互斥调用的信号量 mutex (初值为1)
  • 进程调用管程中的任何过程时, 应执行P(mutex)；进程退出管程时, 需要判断是否有进程在 next 信号量等待, 如果有(即 next_count > 0), 则通过 V(next) 唤醒一个发出 signal 的进程, 否则应执行 V(mutex) 开放管程, 以便让其他调用者进入
  • 为了使进程在等待资源期间, 其他进程能进入管程, 故在 wait 操作中也必须执行 V(mutex), 否则会妨碍其他进程进入管程, 导致无法释放资源

next, next-count

  • 对每个管程, 引入信号量 next(初值为0), 凡发出 signal 操作的进程应该用 P(next) 阻塞自己, 直到被释放进程退出管程或产生其他等待条件
  • 进程在退出管程的过程前, 须检查是否有别的进程在信号量 next 上等待, 若有, 则用 V(next) 唤醒它。next-count(初值为0), 用来记录在 next 上等待的进程个数

x-sem, x-count

  • 引入信号量 x-sem(初值为0), 申请资源得不到满足时, 执行 P(x-sem) 阻塞。由于释放资源时, 需要知道是否有别的进程在等待资源, 用计数器 x-count(初值为0) 记录等待资源的进程数
  • 执行 signal 操作时, 应让等待资源的诸进程中的某个进程立即恢复运行, 而不让其他进程抢先进入管程, 这可以用 V(x-sem) 来实现

image-20230203153058116

6.4.3 管程求解进程的同步与互斥问题

读者写者问题

image-20230203152456907

image-20230203152512970

哲学家就餐问题

image-20230203153252412

1
2
3
4
5
6
7
8
9
10
cobegin
process philosopher_i() {
	while(true) {
    	thinking();
        dining_philosopers.pickup(i);
        eating();
        dining_philosophers.putdown(i);
    }
}
coend

生产者-消费者问题

image-20230203153221933

苹果-橘子问题

image-20230203153239345

6.5 进程通信

6.5.1 进程通信(消息传递)

  • 当进程互相交互时, 必须满足两个基本要求：同步和通信
    • 为实施互斥, 进程间需要同步
    • 为了协作, 进程间需要交换信息
  • 消息传递提供了这些功能, 最典型的消息传递原语
    • send 发送消息的原语
    • receive 接收消息的原语

进程直接通信

  • 对称直接寻址, 发送进程和接收进程必须命名对方以便通信, 原语 send() 和 receive() 定义如下：
    • send(P, messsage) 发送消息到进程P
    • receive(Q, message) 接收来自进程Q的消息
  • 非对称直接寻址, 只要发送者命名接收者, 而接收者不需要命名发送者, send() 和 receive() 定义如下：
    • send(P, messsage) 发送消息到进程P
    • receive(id, message) 接收来自任何进程的消息, 变量id置成与其通信的进程名称

image-20230203155706290

消息格式

image-20230203161752192

进程间接通信

  • 消息不是直接从发送者发送到接收者, 而是发送到由临时保存这些消息的队列组成的一个共享数据结构, 这些队列通常成为信箱(mailbox)
  • 一个进程给合适的信箱发送消息, 另一进程从信箱中获得消息

  • 间接通信的 send() 和 receive() 定义如下：

    • send(A, message)：把一封信件(消息)传送到信箱 A
    • receive(A, message)：从信箱 A 接收一封信件(消息)

  • 信箱可以分成信箱头和信箱体两部分, 信箱头指出信箱容量、信件格式、存放信件位置的指针等；信箱体用来存放信件, 信箱体分成若干个区, 每个区可容纳一封信

  • “发送”和“接收”两条原语的功能为：
    • 发送信件：如果指定的信箱未满, 则将信件送入信箱中由指针所指示的位置, 并释放等待该信箱中信件的等待者；否则, 发送信件者被置成等待信箱状态
    • 接收信件：如果指定信箱中有信, 则取出一封信件, 并释放等待信箱的等待者, 否则, 接收信件者被置成等待信箱中信件的状态

send/receive原语的算法描述

image-20230203162732043

消息传递求解生产者消费者问题

image-20230203162507141

有关消息传递的若干问题

  • 关于信箱容量问题
  • 关于多进程与信箱相连的信件接收问题
  • 关于信箱的所有权问题
    • 信箱为操作系统所有是指由操作系统统一设置信箱, 归系统所有, 供相互通信的进程共享, 消息缓冲机制就是一个著名的例子
  • 关于信件的格式问题和其他有关问题
  • 关于通信进程的同步问题

消息缓冲是在1973年由P.B.Hansan提出的一种进程间高级通信设施, 并在RC4000系统中实现

消息缓冲通信的基本思想是：由操作系统统一管理一组用于通信的消息缓冲存储区, 每一个消息缓冲存储区可存放一个消息(信件)。当一个进程要发送消息时, 先在自己的消息发送区里生成待发送的消息, 包括：接收进程名、消息长度、消息正文等。然后, 向系统申请一个消息缓冲区, 把消息从发送区复制到消息缓冲区中, 注意在复制过程中系统会将接收进程名换成发送进程名, 以便接收者识别。随后该消息缓冲区被挂到接收消息的进程的消息队列上, 供接收者在需要时从消息队列中摘下并复制到消息接收区去使用, 同时释放消息缓冲区。

消息缓冲通信

消息缓冲通信涉及的数据结构：

  • sender：发送消息的进程名或标识符
  • size：发送的消息长度
  • text：发送的消息正文
  • next-ptr：指向下一个消息缓冲区的指针

在进程的PCB中涉及通信的数据结构：

  • mptr：消息队列队首指针
  • mutex：消息队列互斥信号量, 初值为1
  • sm：表示接收进程消息队列上消息的个数, 初值为0, 是控制收发进程同步的信号量

发送原语和接收原语的实现如下：

  • 发送原语Send：申请一个消息缓冲区, 把发送区内容复制到这个缓冲区中；找到接收进程的PCB, 执行互斥操作 P(mutex)；把缓冲区挂到接收进程消息队列的尾部, 执行V(sm)、即消息数加1；执行V(mutex)
  • 接收原语Receive：执行P(sm)查看有否信件；执行互斥操作P(mutex), 从消息队列中摘下第一个消息, 执行V(mutex)；把消息缓冲区内容复制到接收区, 释放消息缓冲区

image-20230203163117130

管道和套接字

  • 管道(pipeline)是Unix和C的传统通信方式
  • 套接字(socket)起源于Unix BSD版本, 目前已经被Unix和Windows操作系统广泛采用, 并支持TCP/IP协议, 即支持本机的进程间通信, 也支持网络级的进程间通信
  • 管道和套接字都是基于信箱的消息传递方式的一种变体, 它们与传统的信箱方式等价, 区别在于没有预先设定消息的边界。换言之, 如果一个进程发送10条100字节的消息, 而另一个进程接收1000个字节, 那么接收者将一次获得10条消息

6.5.2 高级进程通信机制

基于流的进程通信

  • 多个进程使用一个共享的消息缓冲区(可称为管道、多路转换器、套接字)

  • 一些进程往消息缓冲区写入字符流(send/write)

  • 一些进程从消息缓冲区读出字符流(receive/read)
  • 信息交换单位基于字符流, 长度任意

基于字符流的进程通信规约

image-20230203163500686

远程过程调用RPC

  • 采用客户/服务器计算模式
  • 服务器进程提供一系列过程/服务, 供客户进程调用

  • 客户进程通过调用服务器进程提供的过程/服务获得鼓舞

  • 考虑到客户计算机和服务器计算机的硬件异构型, 外部数据表示 XDR 被引入来转换每台计算机的特殊数据格式为标准数据格式

基于RPC/XDR的高级通信规约

image-20230203163812713

远程过程调用(RPC, Remote Procedure Call)

image-20230203163945300

RPC执行步骤

  1. 客户进程以普通方式调用客户存根
  2. 客户存根组织RPC消息并执行Send, 激活内核程序
  3. 内核把消息通过网络发送到远地内核
  4. 远地内核把消息送到服务器存根
  5. 服务器存根取出消息中参数后调用服务器过程
  6. 服务器过程执行完后把结果返回至服务器存根
  7. 服务器存根进程将它打包并激活内核程序
  8. 服务器内核把消息通过网络发送至客户机内核
  9. 客户内核把消息交给客户存根
  10. 客户存根从消息中取出结果返回给客户进程
  11. 客户进程获得控制权并得到了过程调用的结果

6.6 死锁

6.6.1 死锁的产生

若干死锁的例子

进程推进顺序不当产生死锁

image-20230203165502862

PV操作使用不当产生死锁

image-20230203165733619

资源分配不当引起死锁

  • 若系统中有 m 个资源被 n 个进程共享, 每个进程都要求 K 个资源, 而 m < nk 时, 即资源数小于进程所要求的总数时, 如果分配不当就可能引起死锁

对临时性资源使用不加限制引起死锁

  • 进程通信使用的信件是一种临时性资源, 如果对信件的发送和接收不加限制, 可能引起死锁
  • 进程 P1 等待进程 P3 的信件 S3 来到后再向进程 P2 发送信件 S1；P2 又要等待 P1 的信件 S1 来到后再向 P3 发送信件 S2；而 P3 也要等待 P2 的信件 S2 来到后才能发出信件 S3。这种情况下形成了循环等待, 产生死锁

死锁定义

  • 操作系统中的死锁指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件, 则称一组进程或系统此时发生死锁。
  • 例如, n个进程P1, P2, …, Pn, Pi因为申请不到资源 Rj 而处于等待状态, 而 Rj 又被 Pi+1 占有, Pn 欲申请的资源被 P1 占有, 此时这 n 个进程的等待状态永远不能结束, 则说这 n 个进程处于死锁状态

产生死锁因素

  • 不仅与系统拥有的资源数量有关, 而且与资源分配策略, 进程对资源的使用要求以及并发进程的推进顺序有关

6.6.2 死锁的防止

系统形成死锁的四个必要条件

  • 互斥条件(mutual exclusion)：系统中存在临界资源, 进程应互斥地使用这些资源
  • 占有和等待条件(hold and wait)：进程请求资源得不到满足而等待时, 不释放已占有的资源
  • 不剥夺条件(no preemption)：已被占用的资源只能由属主释放, 不允许被其它进程剥夺
  • 循环等待条件(circular wait)：存在循环等待链, 其中, 每个进程都在链中等待下一个进程所持有的资源, 造成这组进程永远等待

破坏条件

破坏第一个条件

  • 使资源可同时访问而不是互斥使用
  • 可再入程序、只读数据文件、时钟、磁盘等软硬件资源均可用这种办法管理, 但有许多资源如可写文件、磁带机等由于特殊性质决定只能互斥占有, 而不能被同时访问, 所以这种做法许多场合行不通。(有些资源具有天生的互斥性)

破坏第二个条件

  • 静态分配
  • 进程在执行中不再申请资源, 就不会出现占有某些资源再等待另一些资源的情况
  • 实现简单, 被许多操作系统采用, 但会严重地降低资源利用率, 因为在每个进程占有的资源中, 有些资源在运行后期使用, 甚至有些资源在例外情况下才被使用, 可能造成进程占有一些几乎不用的资源, 而使其他想用这些资源的进程产生等待

破坏第三个条件

  • 采用剥夺式调度方法
  • 当进程在申请资源未获准许的情况下, 如主动释放资源(一种剥夺式), 然后才去等待

破坏第四个条件

  • 上述死锁防止办法造成资源利用率和吞吐率低。介绍两种比较实用的死锁防止方法

采用层次分配策略(破坏条件2和4)

  • 资源被分成多个层次
  • 当进程得到某一层的一个资源后, 它只能再申请较高层次的资源
  • 当进程要释放某层的一个资源时, 必须先释放占有的较高层次的资源
  • 当进程得到某一层的一个资源后, 它想申请该层的另一个资源时, 必须先释放该层中的已占资源

层次策略的变种按序分配策略

  • 把系统的所有资源排一个顺序, 例如, 系统若共有 n 个进程, 共有 m 个资源, 用 ri 表示第 i 个资源, 于是这 m 个资源是：r1, r2…, rm
  • 规定如果进程不得在占用资源 ri(1<=i<=m) 后再申请 rj(j<i)。不难证明, 按这种策略分配资源时系统不会发生死锁

6.6.3 死锁的避免

  • 银行家算法
    • 银行家拥有一笔周转资金
    • 客户要求分期贷款, 如果客户能够得到各期贷款, 就一定能够归还贷款, 否则就一定不能归还贷款
    • 银行家应谨慎的贷款, 防止出现坏帐
  • 用银行家算法避免死锁
    • 操作系统(银行家)
    • 操作系统管理的资源(周转资金)
    • 进程(要求贷款的客户)

银行家算法的数据结构

一个系统有 n 个进程和 m 种不同类型的资源, 定义包含以下向量和矩阵的数据结构:

  • 系统每类资源总数—该 m 个元素的向量为系统中每类资源的数量
    • Resource = (R1, R2 , …, Rm)

  • 每类资源未分配数量—该 m 个元素的向量为系统中每类资源尚可供分配的数量

    • Available = (V1, V2 , …, Vm)

  • 最大需求矩阵—每个进程对每类资源的最大需求量, Cij表示进程 Pi 需 Rj 类资源最大数

image-20230203171542152

  • 分配矩阵—表示进程当前已分得的资源数, Aij 表示进程 Pi 已分到 Rj 类资源的个数

image-20230203171616097

银行家算法中下列关系式确保成立

image-20230203171718724

一种死锁避免策略

image-20230203171817254

系统安全性定义

在时刻 T0 系统是安全的, 仅当存在一个进程序列P1, …, Pn , 对进程Pk满足公式

image-20230203171853323

实例说明系统所处的安全或不安全状态

  • 如果系统中共有五个进程和 A、B、C 三类资源
  • A类资源共有10个, B类资源共有5个, C类资源共有7个
  • 在时刻T0, 系统目前资源分配情况如下
  • 资源总数[10 5 7]

image-20230203171944508

可以断言目前系统处于安全状态, 因为, 序列{P1, P3, P4, P2, P0}能满足安全性条件

image-20230203172228269

银行家算法的基本思想

  • 系统中的所有进程进入进程集合
  • 在安全状态下系统收到进程的资源请求后, 先把资源试探性分配给它
  • 系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较, 在进程集合中找到剩余资源能满足最大需求量的进程, 从而, 保证这个进程运行完毕并归还全部资源
  • 把这个进程从集合中去掉, 系统的剩余资源更多了, 反复执行上述步骤。//进程退出系统, 资源回收
  • 最后, 检查进程集合, 若为空表明本次申请可行, 系统处于安全状态, 可实施本次分配; 否则, 有进程执行不完, 系统处于不安全状态, 本次资源分配暂不实施, 让申请进程等待。

6.6.4 死锁的检测和解除

资源分配图和死锁定理

  • 解决死锁问题的一条途径是死锁检测和解除，这种方法对资源的分配不加任何限制，也不采取死锁避免措施，但系统定时地运行一个“死锁检测”程序，判断系统内是否已出现死锁，如果检测到系统已发生了死锁，再采取措施解除它

进程-资源分配图

  • 约定 Pi->Rj 为请求边，表示进程 Pi 申请资源类 Rj 中的一个资源得不到满足而处于等待 Rj 类资源的状态，该有向边从进程开始指到方框的边缘，表示进程 Pi 申请 Rj 类中的一个资源。
  • Rj->Pi 为分配边，表示 Rj 类中的一个资源已被进程 Pi 占用，由于已把一个具体的资源分给了进程 Pi，故该有向边从方框内的某个黑圆点出发指向进程。

image-20230203173105215

image-20230203173204493

简化进程-资源分配图检测系统是否处于死锁状态

  • 如果进程-资源分配图中无环路，则此时系统没有发生死锁
  • 如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程

  • 如果进程-资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件

  • 如果能在进程-资源分配图中消去此进程的所有请求边和分配边，成为孤立结点。经一系列简化，使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的

  • 系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。该充分条件称为死锁定理

死锁的检测和解除方法

  • 借助于死锁的安全性测试算法来实现。死锁检测算法与死锁避免算法是类似的，不同在于前者考虑了检查每个进程还需要的所有资源能否满足要求；而后者则仅要根据进程的当前申请资源量来判断系统是否进入了不安全状态

image-20230203173634312

死锁的解除

  • 结束所有进程的执行，重新启动操作系统。方法简单，但以前工作全部作废，损失很大。
  • 撤销陷于死锁的所有进程，解除死锁继续运行。
  • 逐个撤销陷于死锁的进程，回收其资源重新分派，直至死锁解除。
  • 剥夺陷于死锁的进程占用的资源，但并不撤销它，直至死锁解除。可仿照撤销陷于死锁进程的条件来选择剥夺资源的进程
  • 根据系统保存的检查点，让所有进程回退，直到足以解除死锁，这种措施要求系统建立保存检查点、回退及重启机制
  • 当检测到死锁时，如果存在某些未卷入死锁的进程，而随着这些进程执行到结束，有可能释放足够的资源来解除死锁
Prev
2023-08-09 14:53:19 # NJU # 计算机操作系统
Next