2．进程管理

前驱图以及程序顺序执行和并发执行的特点

前驱图

（详见教材）

顺序执行的特点

顺序性
封闭性
- 程序运行时独占全机资源
- 执行结果不受外界因素影响
可再现性
- 执行环境和初始条件相同，程序程序重复执行，最终结果相同。

并发执行的特点

间断性
失去封闭性
不可再现性

（★）重要结论：程序在并发执行时，其计算结果和并发执行速度有关

进程的基本概念和思想

（详见教材）

进程的状态与转换

（详见教材）

进程控制块及其作用

（详见教材）

进程组织

进程控制块（PCB）
程序段
数据段

进程同步（★★★★★★★★）

进程同步的概念和同步原则

概念

（详见教材）

原则（★★★）

空闲让进
- 临界资源空闲，有人需要，给它。
忙则等待
- 临界资源正忙（被进程访问中），其他要使用临界资源的进程需要等待临界资源被释放，才能使用
有限等待
- 对待对临界资源有需求的进程，应该保证其在有限的时间内得到。以免陷入“死等”（“饥饿”）
让权等待
- 自己拿不到临界资源，就放弃处理机。以免陷入“忙等”

临街资源和临界区的概念

（详见教材）

信号量及其应用（★★★★★★）

常见信号量的描述

整型

// P操作（或者称 wait(S) 原语）

wait(S)
{
    while(S <= 0)   // 未遵循“让权等待”。当 S <= 0 时，使得进程一直“忙等”
        ;           // 空操作
    
    S--;
}

// V 操作（或者称 signal(S) 原语）

signal(S)
{
    S++;
}

记录型

// 类型定义

typedef struct{
    int value;
    struct process_control_block *list;
}semaphore;

// P操作（或者称 wait(S) 原语）

wait(semaphore *S)    // 相当于申请资源
{
    S->value--;
    
    if(S->value < 0)
        block(S->list);
}

// V 操作（或者称 signal(S) 原语）

signal(semaphore *S)  // 相当于释放资源
{
    S->value++;
    
    if(S->value <= 0)
        wakeup(S->list);
}

应用

实现同步（★★★）

// P2 的 y 要调用 P1 的 x 的结果，所以需要先执行 P1 的 x 后再执行 P2 的 y

semaphore S = 0;

P1()
{
    ...;
    
    x;               // x 语句
    V(S);            // 通知 P2，x 语句已完成
    
    ...;
}

P2()
{
    ...;
    
    P(S);            // 检查语句 x 是否完成
    y;               // 检查无误，运行 y
    
    ...;
}

实现互斥（★★★）

semaphore S = 1;

P1()
{
    ...;
    
    P(S);            // 准备访问前，对临界资源加锁
    进入 P1 临界区;
    V(S);            // 访问结束，释放临界资源的锁
    
    ...;
}

P2()
{
    ...;
    
    P(S);
    进入 P2 临界区;
    V(S);
    
    ...;
}

实现前驱图关系

总思路
- 进程前半段包含对前驱结点资源的 P 操作（想要前驱完成，才能继续本进程的继续向下运行）
- 进程后半段包含对自身结点资源的 V 操作（释放自身，通知其后继结点，我已完成）

经典进程同步问题（★★★★★★★★）

生产者-消费者问题

// 生产者-消费者模型

// in  输入缓冲区中数据的位置
// out 输出缓冲区中数据的位置
int in = 0, out = 0;

// buffer 缓冲区
item buffer[n];

// mutex 临界区互斥信号量。
// 若为 1，则临界区空闲；
// 若为 0，说明有一个进程在使用，另一个进程并未请求使用；
// 若为 -1，则临界区正被一个进程使用，并且有另一个进程在请求使用这个临界区

// empty 表示还剩下多少空闲缓冲区，初始化为 n。若为 0，则缓冲区已满

// full  表示缓冲区已经使用的个数，初始化为 0。若为缓冲区的最大容量，则缓冲区已满。
semaphore mutex = 1, empty = n, full = 0;

void producer()
{
    do{
        produce an item nextp;
        ...;
        wait(empty);       // 使用 wait(P操作) 检查是否还有空闲缓冲区资源
                           // 总结：要什么临界资源之前，先 P 一下
        wait(mutex);       // 互斥访问请求
        buffer[in] = nextp;// 临界区操作
        in = (in + 1) % n;
        signal(mutex);     // 互斥访问释放
        signal(full);      // 缓冲区已使用个数加 1(注意这里是 full )
                           // 总结：操作完成后，提供什么资源，要 V 一下
    }while(TRUE);
}

void consumer()
{
    do{
        wait(full);         // 使用 wait(P操作) 检查缓冲区是否有资源（注意是检查 full ）
        wait(mutex);
        nextp = buffer[out];
        out = (out + 1) % n;
        signal(mutex);
        signal(empty);      // 缓冲区空闲个数加 1(注意这里是 empty )
        consume the item in nextp;
        ...;
    }while(TRUE);
}

void main()
{
    cobegin
        producer();  consumer();
    coend
}

哲学家进餐问题

// 此法可能导致死锁：每个人都拿起左手边的筷子，每个人都又申请右手边的筷子，此时产生死锁。

semaphore chopstick[5] = {1, 1, 1, 1, 1};

Pi()
{
    do{
        wait(chopstick[i]);
        wait(chopstick[(i + 1) % 5]);
        
        ...;
        
        // eat
        
        ...;
        
        signal(chopstick[i]);
        signal(chopstick[(i + 1) % 5]);
        
        ...;
        
        // think
        
        ...;
        
    }while(TRUE);
}

// 改进方案：仅当一名哲学家左右两边的筷子都可用时，才允许拿筷子

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;                      // 互斥取筷子

Pi()
{
    do{
        wait(mutex);
        wait(chopstick[i]);
        wait(chopstick[(i + 1) % 5]);
        signal(mutex);                    // 注意在此时释放互斥取筷子信号量
        
        ...;
        
        // eat
        
        ...;
        
        signal(chopstick[i]);
        signal(chopstick[(i + 1) % 5]);
        
        ...;
        
        // think
        
        ...;
        
    }while(TRUE);
}

读者-写者问题

// rmutex 信号量用于多个 reader 进程互斥访问 readcount 这个临界资源
// wmutex 信号量用于 reader 和 writer 互斥访问

semaphore rmutex = 1, wmutex = 1;
int readcount = 0;

void reader()
{
    do{
        // 正式读之前，readcount 要增 1
        wait(rmutex);
        if(readcount == 0)
            wait(wmutex);
        readcount ++;
        signal(rmutex);
        
        ...;
        perform read operation;
        ...;
        
        // 读完后，readcount 要减 1
        wait(rmutex);
        readcount--;
        if(readcount == 0)
            signal(wmutex);
        signal(rmutex);
    }while(TRUE);
}

void writer()
{
    do{
        wait(wmutex);
        perform write operation;
        signal(wmutex);
    }while(TRUE);
}

进程通信的基本概念和方法

概念

指进程之间的信息交换

方法

低级

PV 操作

高级

共享存储
- 基于共享数据结构
- 基于共享存储区
管道通信
- 半双工通信（某一时刻只能单向传输）
消息传递
- 直接通信
  - 通过原语，发送端直接到接受端
- 间接通信
  - 通过共享中间实体（称作邮箱）进行消息收发
客户机-服务器系统
- 套接字
- 远程过程调用和远程方法调用

线程的概念和多线程模型

线程概念

（详见教材）

多线程模型

多对一

多个用户级线程映射到一个内核级线程
优点
- 线程管理在用户空间进行，效率较高
缺点
- 一个线程在使用内核服务时被阻塞，整个进程都会被阻塞
- 多个线程不能并行地运行在多处理机上

一对一

一个用户级线程映射到一个内核级线程
优点
- 一个线程被阻塞，允许另一个线程继续执行，并发能力强
缺点
- 这样创建线程，开销较大，影响程序性能

多对多

n 个用户级线程映射到 m 个内核级线程（m ≤ n）
对比前两者，可谓集两者之所长，补两者之所短

3．调度与死锁

调度的概念

（详见教材）

调度队列模型

调度的基本准则与方式

基本准则

CPU 利用率
系统吞吐量
（★★★）周转时间
- \(周转时间 = 作业完成时间- 作业提交时间\)
- \(平均周转时间= \frac{作业1周转时间+\cdots +作业 n周转时间}{n}\)
- \(带权周转时间=\frac{作业周转时间}{作业实际运行时间}\)
- \(平均带权周转时间=\frac{作业1带权周转时间+\cdots +作业 n带权周转时间}{n}\)
等待时间
响应时间

方式

非剥夺调度方式（非抢占式）
剥夺调度方式（抢占式）

（★★★★★）各种调度算法及其评价

（★★★）先来先服务(FCFS)

调度标准：按作业提交时间，从前到后依次分配处理机
评价
- 简单，但效率低；
- 对长作业有利，但对短作业不利（相对 SJF 和高响应比）；
- 有利于 CPU 繁忙型作业，不利于 I/O 繁忙型作业

（★★★）短作业优先(SJF)

调度标准：从后备队列中选择估计运行时间最短的作业
评价
- 平均等待时间、平均周转时间最少
- 必须预知作业的运行时间
- 对长作业不利（可能会导致长作业“饥饿”）
- 未考虑作业的紧迫程度

优先级

调度标准：基于作业的紧迫程度，保证紧迫性作业优先

（★）高响应比优先

调度标准：响应比高的优先运行。其中响应比定义如下
- \(响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}\)
评价
- 作业等待时间相同，要求服务时间越短，响应比越高，有利于短作业
- 要求服务时间相同，作业的响应比由其等待时间确定，等待时间越长，其响应比越高。因而实现了先来先服务
- 对于长作业，作业的响应比随等待时间的增加而提高，等待时间足够长时，响应比便可升到很高，从而也可获得处理机。因此，克服了饥饿状态，兼顾了长作业。

时间片轮转

调度标准：先来先服务，但仅能运行一个时间片。
- 若一个时间片未完成，剥夺该进程处理机，并将这个进程挂到就绪队列末尾，将处理机分配给当前就绪队列的第一个进程。

多级反馈队列

调度标准：时间片轮转和优先级调度
- 多个队列，优先级不同，时间片也不同。
  - 总的来说，优先级越高的队列越先执行，但其时间片越短。
  - 一个时间片未完成，降优先级
  - 一个优先级队列都运行完后，才能运行下一个
  - 若有高优先级来，则抢占资源
评价：
- 融合了前几种算法的优点

死锁

概念

多个进程相互竞争资源，形成一种相互等待的僵局

原因

竞争不可抢占性资源
竞争可消耗资源
进程推进顺序不当

产生死锁的必要条件

互斥

资源使用只能一个一个来

请求和保持

占着已有的，想占还没有的

不可抢占

一个进程占有的，不能被其他进程抢占，而只能由自己释放

循环等待

进程 i 需要的资源被进程 i + 1 占用，而进程 n 需要的资源被进程 0 占用。

死锁处理策略

预防（破环死锁必要条件）

互斥：无法破坏
请求和保持：一次分配所有需要的资源
不可抢占：得不到新的，便先放弃旧的
循环等待：按序分配

预防（防止系统进入不安全的状态）

（★★★★★★）银行家算法

流程简述
- 计算 Need 矩阵
  - 情形1：题设可能已经直接给出
  - 情形2：根据表格提取 Max 矩阵和 Allocation 矩阵。用Max 减掉 Allocation，得到 Need
- 对比 Need 和 Available
  - 找到比 Available 小的行（若没有，则当前状态不安全，赶紧另寻其他安全序列），选择一个其中一行，将这行对应的进程暂时加入到安全序列
- 释放加入安全序列进程对应的资源
  - 将加入安全序列进程对应的 Allocation 行，加到 Available ，更新 Available
  - 并在 Need 矩阵中划掉对应的行
- 从步骤 2 开始向下重复，看能否得到一个安全序列

检测

利用对资源分配图进行化简

解除

通常有以下方法

资源剥夺
撤销进程
进程回退

解题技巧及重要结论

优先级调度算法中优先级设置的一般原则
- 系统 > 用户
- 交互式 > 非交互式（或者说前台 > 后台）
- I/O > 计算
（★★★★★★★★★）有关调度算法的平局周转时间的计算方法
- 依据调度算法画出运行过程中的甘特图，再依据甘特图计算。
  - 注意画甘特图时最好列出下表（特别要标注好，当前时刻未完成的进程的剩余时间），做好判断

时刻	进程名（剩余时间）	进程名（剩余时间）	···

（★★★★★）有关信号量大小的实际意义
- S.value > 0，表示某类资源可用的数量。
- S.value <= 0，表示某类资源已经没有，或者说还有因请求该资源而被阻塞的进程。
- S.value <= 0时的绝对值，表示等待进程数目。
有关信号量的初始值
- 互斥信号量：一般初始化为1
- 同步信号量
  - 若期望的信息未产生，初始化为 0
  - 若期望的消息已存在，初始化为一个非 0 的正整数
（★★★★★）有关死锁极端情况的分析
- 3 个并发进程，都需要 4 个同类资源，必然不会发生死锁的最少资源为？
  - 考虑死锁情况：每个进程分配了 3 个资源，都拿不到第 4 个，形成死锁。此时有 9 个资源
  - 在上述死锁条件下，加一个资源，则必有一个进程可以先拿到 4 个，完成后释放，使得其他进程也能完成。
  - 所以最少 10 个
- 11 个磁带机， X 个进程共享，每个最多请求 3 台，必然不会死锁的 X 的最大值为？
  - 考虑死锁情况：每个进程分配了 2 个资源，都拿不到第 3 个，形成死锁。此时有 2X 个资源
  - 2X + 1 个则不会
  - 2X + 1 = 11，解得 X = 5
- 8 个打印机， K 个进程竞争使用，每个最多请求 3 台，可能发生死锁的 X 的最小值为？
  - 考虑死锁情况：每个进程分配了 2 个资源，都拿不到第 3 个，形成死锁。此时有 2K 个资源
  - 2K = 8，解得 K = 4
- n 台互斥使用的同类设备，三个并发进程，分别需要 3、4、5 台，确保不发生死锁的 n 最小值为？
  - 考虑死锁情况：三个进程分别拿到 2、3、4 个资源，都拿不到它们所期望的最后一个资源，形成死锁。此时有 9 个资源
  - 再加一个，就不会有死锁了。即 10 个满足题意
- 总结：考虑这样一种死锁情况，即每个并发进程分配的资源数为给它所需要资源数减一。若要不死锁，那么在上述已分配资源数之和的基础上加上一即可。

参考资料

计算机操作系统.汤小丹等
2020年操作系统考研复习指导.王道论坛