OS Note

题录

• 多道批处理系统下的多进程

• 信号量集机制实现程序间的前趋关系

• P、V操作解决司机与售票员的同步问题

• 信号量机制解决水果盘问题

• 信号量机制解决过桥问题

• 信号量机制解决信箱问题

• 信号量机制解决理发师问题

引论

操作系统的目标

方便性（主要目标）： 配置OS后的计算机可使用各种命令操纵计算机，以及编译命令编译源码生成机器代码，使其易用。

有效性（主要、首要目标）：

1. OS提高了系统资源的利用率，如处理机、IO设备等。
2. OS提高了系统吞吐量，更好的组织计算机工作流程。

可扩充性： 体现为更方便的添加以及修改功能和模块。

开放性： 遵循世界标准规范，提高兼容性，形成良好生态。

操作系统的作用

作为用户与计算机硬件系统之间的接口： OS使用户可以通过命令方式、系统调用方式、GUI方式实现与系统的通信。

作为计算机系统资源的管理者： OS管理着硬件资源（IO设备、存储器、处理机等）以及硬件资源的调度。

实现了对计算机资源的抽象： 用户不必对物理接口有所了解，通过OS的I/O软件实现数据输入输出功能，将物理接口抽象为OS模型。

推动操作系统发展的主要动力

不断提高计算机资源利用率： 如批处理系统的出现

方便用户： 如分时交互式系统的出现

期间的不断更新迭代： 8位- 16 - 32 - 64 - …

计算机体系结构的不断发展： 单处理机系统、多处理机系统、分布式系统、计算机网络

不断提出新的应用需求（根本动力）

操作系统的发展过程

未配置OS的计算机系统

人工操作方式

流程：程序员按程序和数据对纸带打孔 -> 纸带送入输入机 -> 启动输入机传入计算机 -> 启动计算机运行 -> 完毕取走结果 -> 下一用户

缺点：用户独占全机，CPU等待人工操作

脱机输入/输出方式

流程：事先将纸带装入纸带输入机 -> 外围机控制纸带上的数据(程序)输入到磁带 -> CPU需要时从磁带上高速地调入内存

优点：

1. 减少了CPU空闲时间
2. 提高了I/O速度

缺点：资源利用率仍然很低

单道批处理系统

过程：

优点：减少了人工操作的时间，提高机器的利用率和系统吞吐量。

缺点：资源利用率低；人机交互性差。

多道批处理系统

宏观上并行

微观上串行

流程：

优点：

1. 硬件资源利用率高
2. 系统吞吐量大

缺点：

1. 平均周转时间长
2. 交互性差

---

例题：

Q: 设某计算机系统有一台输入机，一台打印机。现有两道程序同时投入运行，且程序A先开始运行，程序B后运行。程序A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。程序B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。

试说明:

1. 两道程序运行时，CPU有无空闲等待?若有，在哪段时间内等待?为什么?
2. 程序A、B运行时有无等待?若有，在什么时候会发生等待?为什么?

A:

1. 有，在100-150ms范围等待，此时没有调用CPU的任务执行
2. A无，B有，B在0-50ms内因A占用CPU所以等待，在180-200ms内因A占用CPU所以等待。

---

分时系统

支持多道且联机

流程：

特征：

1. 多路性： 宏观上同时有多个用户在运行。
2. 独立性： 每个用户一个终端，独立操作，互不干扰
3. 及时性： 在很短时间内得到响应，小于2-3秒。
4. 交互性： 在终端上编辑、运行程序，或其它操作。

---

例题：

Q: 在分时系统中，响应时间≈时间片×用户数，因此为改善响应时间，常用的原则是使时间片越小越好。

A: 时间片不是越小越好，时间片越小，进程切换所用的开销就相对越大。

---

实时系统

可靠且时效性强

应用：飞机火车订票系统、导弹制导系统、多媒体系统。

特征：

1. 多路性
2. 独立性
3. 及时性
4. 交互性
5. 可靠性

操作系统的基本特征

并发

计算机系统中同时存在多道运行的进程。

宏观上：多道进程同时执行

微观上：任何时刻仅有一道进程执行，只是基于时间片进行高频的进程切换

区分：并行使指多道程序在同一时刻执行，但需多个硬件支持

共享

系统中的资源不再为某道程序所独占，而是供多道程序共同使用。

共享方式：

• 互斥共享： 在规定时间内仅允许单一进程访问指定资源，其他进程等待。
• 同时共享：
  • 宏观： 在规定时间内允许多个进程访问指定资源。
  • 微观： 多个进程交替访问该资源。

虚拟

将一物理实体通过分时或分空间映射为若干对应逻辑实体。

• 时分复用：为每个程序建立进程，微观上多个进程交替执行，宏观上表现为一个物理处理器同时为多个用户程序服务。一台I/O设备分为多台逻辑上的I/O设备为多个用户服务，宏观上允许用户同时访问该设备，微观上交替为用户服务。

• 空分复用：将程序最需要执行的部分调入内存，执行完毕后换出，换入另一部分执行。

异步

进程在执行中，其执行时间、顺序、向前推进的速度和完成的时间等都是不可预知的。

进程

进程的构成

PCB+程序段+相关数据段

程序与进程区别：

程序是静态的，它以文件的形式存储在磁盘上。

进程是动态的，加载到内存上，是程序的一次动态执行过程。

进程的状态和转换

就绪态

进程创建完成后进入就绪状态，就绪状态的进程已经具备运行的条件，只是此时CPU没有运行这个进程。

运行态

进程在CPU运行。

阻塞态

进程在运行过程中可能申请资源，这个资源可能正在被使用，此时CPU会让这个进程进入阻塞状态。

如果当资源就绪时，此时这个进程就会从阻塞状态变成就绪状态等待CPU调度

创建态

进程正在被创建时，被称为“创建态”，包括分配资源、初始化PCB。

终止态

进程运行结束后，会执行exit系统调用结束进程，此时进程的状态为终止状态，申请的系统资源和PCB被回收。

---

状态转换

进程控制块（PCB）

PCB是进程存在的唯一标志

PCB是OS对并发执行的进程进行控制和管理的根据。

PCB的组织方式

线性方式

每次查找都要扫整张表

链接方式（常见）

索引方式（少见）

处理机的执行状态

处理机状态	访问权限	程序
系统态（核心态、管态）	一切指令，所有R及存储区	OS内核
用户态（目态）	规定指令，指定R及存储区	用户程序

原语

OS内核中由若干条指令构成的用于完成特定功能的“原子操作”过程，作为一个整体且不可分割—要么全部都完成，要么全部都不做。许多系统调用就是原语。

线程

进程与线程关系

一个进程对应了若干个线程，其中包含一个主线程，主线程的生命周期与隶属进程相同，同时存在，同时消失。

线程的构成

线程ID、程序计数器、寄存器集合和堆栈。线程的资源独立拥有，与其他线程并不共享，但所有线程共享隶属进程所有的资源。

主线程与main函数

执行main函数的线程为主线程。

main函数由主线程执行

主线程可创建、控制、管理其他子线程

进程同步

临界资源

系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。

临界区

在进程中涉及到临界资源的程序段叫临界区。

同步机制规则

有空让进：无进程在临界区时，要求进入临界区的进程可进入。

忙则等待：不允许两个以上的进程同时进入临界区（互斥访问）。

有限等待：要求进入临界区的进程不能无限等待，以免陷入“死等（饥饿）”。

让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。

信号量机制

整型信号量

int S;

void wait(S) {	//P(S)
    while (S <= 0) {
        S--;
    }
}

void signal(S) {	//V(S)
    S++;
}

缺陷：只要S <= 0，wait操作就不断地测试(忙等)，因而，未做到“让权等待”。

记录型信号量

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

void wait(semaphore* S) {	//P(S)申请一个资源
    S->value--;
    if (S->value < 0) {
        block(S->list);
    }
}

void signal(semaphore* S) {	//V(S)释放一个资源
    S->value++;
    if (S->value <= 0) {
        wakeup(S->list);
    }
}

S->value > 0表value个资源可用

S->value == 0表无资源可用且无进程等待该资源

S->value < 0表|value|个进程正在等待该资源

AND型信号量

//Pseudocode
void Swait(S1, S2, ..., Sn) {
    while (true) {
        if (S1 >= 1 && ... && Sn >= 1) {
            for (int i = 1; i <= n; i++) {
                Si--;
            }
            break;
        } else {
            //place the process in the waiting queue associated with the first Si found with Si < 1, and set the program count of this process to the beginning of Swait operation
        }
    }
}

void Ssignal(S1, S2, ..., Sn) {
    while (true) {
        for (int i = 1; i <= n; i++) {
            S++;
            //remove all the process waiting in the queue associated with Si into the ready queue
        }
    }
}

---

例题：

Q:请用信号量集机制实现下图程序之间的前趋关系：

A:

//Pseudocode
semaphore a = b = c = d = e = 0;

p1() {p1; signal(a); signal(b);}

p2() {p2; signal(c);}

p3() {wait(a); p3; signal(d);}

p4() {wait(b); p4; signal(e);}

p5() {wait(c); wait(d); wait(e); p5;}

---

例题：

Q:

• 售票员的操作规则：只有司机停车后，售票员才能开门让乘客下车。
• 司机的操作规则：只有售票员关门后，司机才能启动开始行驶汽车。

A:

semaphore close = 0, stop = 0;

void driver() {
    while (true) {
        P(close);
        //启动车辆->正常行驶->到站停车
        V(stop);
    }
}

void busman() {
    while (true) {
        //关门
        V(close);
        //售票
        P(stop);
        //开门->上下乘客
    }
}

---

例题：

Q:假设桌子上有一个盘子，可以放一个水果。父亲总是放苹果到盘子中，而母亲则总是放香蕉到盘子中；一个儿子专等吃盘中的香蕉，一个女儿专等吃盘中的苹果。请P、V操作实现上述问题。

A:

semaphore empty = 1, apple = 0, banana = 0;

void father() {
    while (true) {
        P(empty);
        V(apple);
    }
}

void mother() {
    while (true) {
        P(empty);
        V(banana);
    }
}

void son() {
    while (true) {
        P(banana);
        V(empty);
    }
}

void daughter() {
    while (true) {
        P(apple);
        V(empty);
    }
}

---

例题：

Q:有交通桥如图所示，车流方向如图中箭头所示。

问题如下：

（1）假设桥上每次只能有一辆车行驶，试用信号量的P、V操作实现交通管理。

（2）假设桥上不允许有两个不同方向的车同时行驶，但允许有多个同方向依次行驶通过。试用信号量的P、V操作实现桥上的交通管理。

A:

int countA = 0, countB = 0;
semaphore bridge = 1, mutexA = 1, mutexB = 1;

void PA() {
    P(mutexA);
    if (countA == 0) {
        P(bridge);
    }
    countA++;
    V(mutexA);
    pass();
    P(mutexA);
    countA--;
    if (countA == 0) {
        V(bridge);
    }
    V(mutexA);
}

void PB() {
    P(mutexB);
    if (countB == 0) {
        P(bridge);
    }
    countB++;
    V(mutexB);
    pass();
    P(mutexB);
    countA--;
    if (countB == 0) {
        V(bridge);
    }
    V(mutexB);
}

---

例题：

Q:有A、B 两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中，设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件（0<x<y<n）。辩论者每取出一个邮件，邮件数减1。A、B 两人操作过程：

//Pseudocode
void A() {
    while (true) {
        /*
        从A的信箱中取出一个邮件
        回答问题并提出一个新问题
        将新邮件放入B的信箱
        */
    }
}

void B() {
    while (true) {
        /*
        从B的信箱中取出一个邮件
        回答问题并提出一个新问题
        将新邮件放入A的信箱
        */
    }
}

当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。

当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。

请添加必要的信号量和P、V（或wait, signal）操作，以实现上述过程的

同步，要求写出完整过程，并说明信号量的含义和初值。

A:

semaphore mutexA = 1, mutexB = 1, emptyA = M - x, fullA = x, emptyB = N, fullB = 0;

void A() {
    while (true) {
        P(fullA);
        P(mutexA);
        //从A信箱中取出一个邮件
        V(mutexA);
        V(emptyA);
        //回答问题并提出一个新问题
        P(emptyB);
        P(mutexB);
        //将新邮件放入B信箱
        V(mutexB);
        V(fullB);
    }
}

void B() {
    while (true) {
        P(fullB);
        P(mutexB);
        //从B信箱中取出一个邮件
        V(mutexB);
        V(emptyB);
        //回答问题并提出一个新问题
        P(emptyA);
        P(mutexA);
        //将新邮件放入A信箱
        V(mutexA);
        V(fullA);
    }
}

---

例题：

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

如果没有顾客，理发师便在理发椅上睡觉，顾客到来时被叫醒。

如果顾客来时理发师正在理发，则顾客找空椅子，坐下来等待。没有空椅子顾客就离开。

如何用信号量解决理发师问题？

A:

semaphore mutex = 1, empty = N, full = 0;
Customer* customers = new Customer[N];
int head = 0, tail = 0;

void Tony() {
    while (true) {
        P(full);
        P(mutex);
        Customer customer = customers[head];
        head = (head + 1) % N;
        V(mutex);
        V(empty);
        hairCut(customer);
    }
}

void Customer() {
    if (empty <= 0) {
        return;
    }
    while (true) {
        P(empty);
        P(mutex);
        customers[tail] = *this;
        tail = (tail + 1) % N;
        V(mutex);
        V(full);
    }
}

---

调度

调度层次

调度频率：低级调度 > 中级调度 > 高级调度

高级/长程调度

主要任务：将外存上处于后备队列的作业调入内存，并创建进程，分配资源，放入就绪队列。

分时和实时系统中不设高级调度

中级调度

主要任务：在内存和外存对换区之间按照给定的原则和策略选择进程对换。

常用于分时系统或具有虚拟存储器的系统中

低级/短程调度（最基本）

主要任务：从就绪队列中选择一个进程分配处理机。

调度方式/算法与准则

周转时间 = 到达时间 - 完成时间
带权周转时间 = 周转时间 / 运行时间

面向用户

1. 周转时间短
2. 响应时间快
3. 截止时间保证
4. 优先权

面向系统

1. 系统吞吐量
2. 处理机利用率高
3. 资源平衡利用

抢占与非抢占

设有AB两进程，当前处理机运行进程A。

抢占：B一旦满足条件，停止运行进程A，切换至进程B。

非抢占：直至进程A运行完毕再运行进程B。

FCFS(first-come first-served) [非抢占]

先来先服务，内含队列。
优点：实现、维护简单。
缺点：忽略了系统优先级对短作业不友好。

SJF(short job first)/SPF(short process first) [抢占/非抢占]

短作业/进程优先。

SJF：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。

SPF：从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它。

优点：

1. 降低作业等待时间
2. 提高系统吞吐量
3. 缩短进程周转时间

缺点：

1. 对长作业不友好
2. 不考虑作业的紧迫程度
3. 作业执行时间、剩余时间为估值并不准确

PSA(priority-scheduling algorithm) [抢占/非抢占]

按规则赋予每个作业或进程一个优先级，优先级高的作业/进程优先被调度。

优先级

静态优先级：在进程创建时就固定不变。

动态优先级：随进程运行变化。

HRRN(Highest Response Ratio Next) [抢占/非抢占]

基于优先权大小进行服务。

优先权 = (等待时间 + 要求服务时间) / 要求服务时间

缺点：每次调度前都要进行优先级计算，有性能开销。

RR(Round Robin) [抢占]

• 所有的就绪进程按照FCFS原则，排成一个队列
• 每次调度时将CPU分派给队首进程，让其执行一个时间片
• 在一个时间片结束时，发生时钟中断，当前进程的暂停执行，回到就绪队列的末尾，并通过上下文切换执行当前的队首进程

时间片设计缺陷

过长：退化为FCFS

过短：上下文频繁切换，性能开销增加

死锁

多个进程在运行过程中因争夺资源或彼此通信而造成的一种互相等待的现象，若无外力作用，这些进程都将无法向前推进。

资源分类

按性质：

• 可剥夺资源：如主存、CPU
• 不可剥夺资源：不能强行收回，如读卡机、打印机等

按期限：

• 永久性资源：可再次使用，如所有硬件
• 临时性资源：消耗性的资源，只可使用一次，如消息、信号和缓冲区内的数据

产生原因

竞争资源

进程推进顺序不当

必要条件

1. 互斥条件（资源独占）

   一个资源一次只能被一个进程使用。

2. 请求保持条件（部分分配，占有且等待）

   保留已经得到的资源，还要求其它的资源。

3. 不可剥夺条件（不可抢占）

   资源只能被占有者释放，不能被其它进程强行抢占。

4. 环路等待条件（循环等待）

   系统中的进程形成了环形的资源请求链。

预防

互斥条件

由资源的性质决定，不可轻易破坏，否则即退化为串行执行。

请求保持条件

预先静态分配法（AND信号量），要求进程在运行前一次性分配给它所需的全部资源，不满足则不投入运行。

优点：简单安全易实现；

缺点：降低资源利用率，须预知进程所需全部资源，可能使进程无限延迟。

不可剥夺条件

破坏不可抢占条件只适用于CPU和内存，而且实现复杂，系统代价很高，降低系统吞吐量，必须小心使用。

环路等待条件

有序资源分配方法，将系统中的所有资源都按类型赋予一个编号，要求每一个进程严格按照编号递增的次序请求资源，同类资源一次申请完。

避免

系统的状态分为安全状态和不安全状态，如果一个系统在安全状态，就没有死锁；如果一个系统处于不安全状态，就有可能死锁。

确保系统不进入不安全状态

安全序列

某一时刻，系统能按某种进程序列来为每个进程分配资源，使每个进程都可顺利地完成，则称此时的系统状态为安全状态，称序列(p1,p2,…，pn)为安全序列。

假使不存在安全序列，那么进程等待

银行家算法

优点：提高资源利用率

缺点：

1. 事先确定进程对资源的最大需求实现困难
2. 进程数目随时变化，安全序列不易确定

检测

资源分配图

如果资源分配图中不存在环路，则系统中不存在死锁；反之若存在环路，则不一定存在死锁。

P = {p1，p2，p3}

R = {r1(1), r2(2), r3(1), r4(3)}

E = {(r1,p2), (r2,p2), (r2,p1), (r3,p3), (p1,r1), (p2,r3), (r4,p3)}

简化方法

1. 寻找一个既不阻塞又非孤立的进程结点Pi，若无则算法结束
2. 去除Pi的所有分配边和请求边，使Pi成为一个孤立节点
3. 转步骤1

若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；反之，称该图是不可完全简化的。

死锁定理

S为死锁状态的充分条件是，当且仅当S状态的资源分配图是不可完全简化的。

解除

资源剥夺法

剥夺死锁进程足够数量的资源给其他的死锁进程，以解除死锁状态。

撤消进程法

强制撤消一个/一部分死锁进程，剥夺其进程的资源供其它死锁进程使用。

存储器层次

自上至下价格↓，容量↑，速度↓。

• CPU寄存器
  • 寄存器
• 主存
  • 高速缓存
  • 贮存
  • 磁盘缓存
• 辅存
  • 磁盘
  • 可移动存储介质

程序的装入

编译

链接

静态链接

将库文件直接嵌入可执行文件中。

优点：

1. 不依赖外部库，在没有库文件的系统上仍能运行。
2. 直接调用库代码，不需要间接调用，性能好。

缺点：

1. 若多个程序使用相同库，每个程序都会包含一份库副本，占用额外空间。
2. 库文件有变更需要重新编译链接。

装入时动态链接

在程序装入时进行链接。

优点：

1. 便于修改、更新。
2. 利于实现模块共享。

运行时动态链接

程序运行至所需模块时才进行装入。

优点：

1. 节省内存空间。
2. 利于实现模块共享。

装入

绝对装入（单道）

物理地址 = 逻辑地址

不需要进行地址转换，逻辑地址与物理地址完全相同。

可重定位装入（多道）

物理地址 = 逻辑地址 + 偏移量（装入时确定、一次性）

地址变换在进程装入时一次性完成，不再改变，装入后逻辑地址与物理地址不同。

动态运行时装入

物理地址 = 逻辑地址 + 偏移量（运行时确定、可变）

装入内存后直至程序真正运行时才进行地址变换，需要一个重定位寄存器的支持。

内存分配

单一连续分配

内存区分为OS区和用户区。

用户区内单道执行用户程序（一次装入一个）。

固定分区分配

由于作业大小 <= 分区大小，不可避免地造成内存碎片化。

内存区分为OS区和用户区。

用户区被划分为若干分区，大小可相同可不同，每个分区可装入一道程序。

分区说明表（示例）

分区号	起址	大小	状态
1	20	12	已分配
2	32	32	已分配
3	64	64	未分配
4	128	128	已分配

动态分区分配

根据作业大小动态分配分区。

数据结构

//空闲分区线性表
struct Block {
    bool captured;
    size_t block_num;
    size_t begin;
    size_t size;
};

using Table = std::vector<Block>;

//空闲分区链表
struct Block {
    bool captured;
    size_t size;
};

using List = std::list<Block>;

动态分配算法

template<typename Mission>
struct Job {
    size_t need;
    std::function<Mission> mission;
    
    void loadTo(Block& block) {}
};

首次适应算法

void FF(List& list, Job& job) {
    for (auto& cur : list) {
        if (!cur.captured && cur.size >= job.need) {
            job.loadTo(cur);
            cur.captured = true;
            return;
        }
    }
}

每次都从list头部查找，优先使用用低址内存，导致低址内存过于碎片化。

循环首次适应算法

void NF(List& list, Job& job) {
    static int idx = 0;
    while (true) {
        if (!list[idx].captured && list[idx].size >= job.need) {
            job.loadTo(cur);
            cur.captured = true;
            idx = (idx + 1) % list.size();
            return;
        }
        idx = (idx + 1) % list.size();
    }
}

维护idx，每次从idx开始查找。

最佳适应算法

void BF(List& list, Job& job) {
    Block* dst = nullptr;
    size_t overflow = SIZE_MAX;
    for (int i = 0; i < list.size(); ++i) {
        if (list[i].size >= job.need
            && list[i].size - job.need < overflow) {
            dst = &list[i];
            overflow = list[i].size - job.need;
        }
    }
    if (dst) {
        job.loadTo(*dst);
    } else {
        throw std::exception;
    }
}

优先使用能分配作业的最小分区进行分配。

最坏适应算法

void WF(List& list, Job& job) {
    std::sort(list.begin(), list.end(),
              [](const Block& a, const Block& b) {
                  return a.size > b.size;
              });
    if (job.need <= list[0].size) {
        job.loadTo(list[0]);
    } else {
        throw std::exception;
    }
}

优先使用最大分区分配。

离散分配

分页式存储管理

将内存空间等分成存储块/物理块，称为页框(frame，从0开始编号) 。

在为进程分配内存时，以页为单位，将进程中若干页装入到多个不相邻的块中。

地址结构

• 逻辑地址

页号	页内偏移量
2^p页 => p位	2^dB => d位

• 物理地址

块号	块内偏移量
2^d块 => d位	2^dB => d位

若要访问的目标地址页号不在页表中，触发越界中断。

快表

为提升寻址速度，引入了快表，其原理类似于CPU Cache。

分段式存储管理

进程的逻辑地址空间：分段划分为若干大小不等的段。

每个进程设置一个段表，描述该进程占用的物理分区及逻辑排列顺序，包括段号、段长、基址。

段内连续，段间不一定连续。

地址结构

• 逻辑地址

段号	段内地址
2^s段 => s位	2^wB => w位

若要访问的目标地址段号不在段表中，或者地址越过段长，触发越界中断。

段页式存储管理

分段和分页原理的结合，先将用户程序分成若干个段，并为每一个段赋一个段名，再把每个段分成若干个页。

地址结构

段号 + 段内页号 + 页内偏移量