1、操作系统发展过程
无操作系统的计算机系统 概念：硬件直接运行程序 应用场景：早期简单嵌入式设备，如电子计算器 单道批处理系统 概念：一批作业脱机输入磁带，按序处理 应用场景：早期科学计算中心，管理员按序处理作业 多道批处理系统 概念：内存同时存多专业，共享资源交替 应用场景：大型数据处理中心，银行批处理业务 分时系统 概念：多用户分时共享计算机，轮流使用 CPU 应用场景！：学习计算机实验，远程登录系统 实时系统 概念：及时响应外部事件，按时完成处理 应用场景：飞机飞行控制系统，视频会议系统
2、操作系统的基本特征
并发（Concurrent） 含义：多事件同时间间隔发生，宏观是同时，微观是交替 作用：提高资源利用率与系统吞吐量 共享（Sharing） 含义：系统资源供多进程共用 作用：提高资源利用率，帮助进程协同 虚拟（Virtual） 含义：物理实体变多个逻辑对应物 作用：提供方便灵活方式，提高资源利用率与灵活性 异步性（Asynchronism） 含义：进程并发执行，走走停停 作用：系统协调管理，确保稳定正确
3、操作系统的主要功能
处理机管理：分配。调度处理机、让多个程序高效运行 存储器管理：合理分配内存、保障程序运行空间 设备管理：控制、管理各类设备，方便用户使用 用户接口：提供交互界面，方便用户操作和使用系统
4、进程同步的基本概念
含义：多个进程并发时，按规则协作以正确执行 目的：防竞争条件，保证协作顺利 机制：信号量、管程、消息传递等，协调进程对资源访问与协作 信号量：是一种用于实现进程同步和互斥的整形变量，通过P（等待）V（释放）操作来控制进程对资源的访问。 管程：高级同步机制，将共享资源以及操作封装在一个模块中，进程通过调用管程中的过程来访问共享资源，内部自动实现同步与互斥。 消息传递：通过发送与接受消息来进行通信和同步，发送时等待接收方响应，以此实现协调
临界区
- 不论是 硬件临界值 还是 软件临界资源，多个进程必须 互斥 地对它进行访问
- 在每个进程中访问临界资源的那段代码成为临界区（Critical Section）
- 每个进程进入临界区之前应先对 欲访问的临界资源进行检查，看是否正在访问。如果刺客该临界资源未被访问，该进程可进入临界区，并设置它正在访问的标志，在临界区 之前 执行的这段代码成为 进入区（Entry Section）
- 在临界区 之后 也要加上一段代码，用于将临界区访问的标志变成未被访问的标志，成为 退出区（Exit Section）
执行流程如图：
5、进程的基本状态及转换
练习 1.0
处于执行状态中的进程若同时发生了下列两种情况:(a)对某信号量执行 P 操作后,其结果为负。(b)时间片到了中断发生。则该进程将由执行状态变迁为( A )状态。 A.阻塞 B.就绪 C.阻塞或就绪 D.不定
在多进程系统中，为了保证共享变量的完整性，各进程应互斥进入临界区，所谓临界区是指（D） A. 一个缓冲区 B. 一段数据区 C. 同步机制 D. 一段程序
练习题 2.0
一个数据采集处理系统有两个进程 A，B。进程 A 负责数据采集，并把采集到的数据存入缓冲区 H 中，供进程 B 做数据处理。系统规定：仅当进程 B 取走了 H 中的数据后进程 A 才能在 H 中存入新的数据。为使进程能正确地并发执行，现用 PV 操作进行管理，回答下列问题：
S1，初始值为 1，用于进程 B 通知进程 A 数据已经被取走==
==定义一个信号量 S2，初始值为 0，用于通知进程B取走数据==
（2）在如下程序的方框位置填上合适的 P 操作或 V 操作，使它们能正确地并发执行。
①处填 P(S1) ②处填 V(S2) ③处填 P(S2) ④处填 V(S1)
练习题 3.0
某自动流水线由生产进程 A、检验进程 B 和包装进程 C 三部分组成。进程 A 每生产一件物品就将其放入检验箱内。进程 B 对待检物品进行检验，若合格，则将其放入包装箱内，否则丢入废物箱。进程 C 将对合格产品进行包装。假如检验箱和包装箱每次都只能存放一件物品，现采用 PV 操作进行管理，为使流水线能正确协调工作，请完善如下程序。
S1,S2,S3,S4 : 1.semaphore ; S1 := S2 := 1; S3 := S4 := 0; cobegin process A begin L1: 生产一件物品; 2.P(S1) ; 物品存检验箱; 3.V(S3) ; goto L1 end; process B begin L2: 4.P(S3) ; 从检验箱取物品; 5.V(S1) ; 检验; if 合格 then begin 6.P(S2) ; 物品存包装箱; end 7.P(S4) ; else 丢弃; goto L2 end; process C begin L3 8.P(S4) ; 从包箱取物品; 9.V(S2) ; 包装; goto L3 end; coend;
## 练习题4.0
补充1：**什么是进程？简述进程与程序的主要区别**
==**答案**：它是程序在计算机中动态的一次执行过程，含程序，数据、进程控制块（PCB）。是资源分配和调度的基本单位，具有并发性、动态性、独立性、异步性等特征。==
==**与程序的区别：**==
==状态：程序静态，进程动态是动态的==
==资源：程序不占资源，进程运行时分配==
==对应：一程序可对多进程，一进程某时只对一程序==
补充2：
设公共汽车上有一位司机和一位售票员，它们的活动如下：
司机： 售票员：
启动车辆 售票
正常行车 开车门
到站停车 关车门
请分析司机与售票员之间的同步关系，如何用PV操作实现。
**==答案**：定义两个信号量：
`S1` 初始值为 `0`，用于表示售票员是否关好车门，`0` 表示未关好，`1` 表示已关好；
`S2` 初始值为 `1`，用于表示司机是否到站停车，`0` 表示未停车，`1` 表示已停车。==
==**司机**==begin 定义信号量 S1 = 1; // 允许售票员开始工作 定义信号量 S2 = 0; // 售票员等待停车通知
plain L1: P(S1); // 等待售票员关好车门 启动车辆; 正常行车; 到站停车; V(S2); // 通知售票员车辆已到站停车 goto L1; end;
**==售票员==**begin 定义信号量 S1 = 1; // 允许售票员开始工作 定义信号量 S2 = 0; // 售票员等待停车通知
plain L2: P(S2); // 等待司机到站停车通知 开车门; 售票; 关车门; V(S1); // 通知司机车门已关好 goto L2; end;
## 练习题5.0
1. **先来先服务（FCFS）算法**
- **周转时间**：完成时间 - 到达时间
- **平均周转时间**：所有进程周转时间之和 / 进程个数
- **带权周转时间**：周转时间 / 服务时间
- **平均带权周转时间**：所有进程带权周转时间之和 / 进程个数
2. **短作业优先（SJF）算法**
- **选择规则**：选择当前已到达且服务时间最短的作业（进程）执行
- **周转时间**：完成时间 - 到达时间
- **平均周转时间**：所有进程周转时间之和 / 进程个数
- **带权周转时间**：周转时间 / 服务时间
- **平均带权周转时间**：所有进程带权周转时间之和 / 进程个数
## 练习题6.0
## 练习题7.0
---
## 练习题8.0
## 练习题9.0
## 练习题10
## 练习题11
要根据响应比来计算优先，
公式为：（当前时间 - 到达时间 + 服务时间）/ 服务时间
## 练习题12
## 6、死锁
### 死锁的定义
**定义**：多个进程因为相互竞争资源而陷入一种相互等待的状态，导致这些进程无法执行，也无法释放资源，形成一种僵局
**产生的必要条件：**
**互斥条件**：至少有一个资源是不能共享的，即每次只能一个进程使用（==进行排它性使用）==
**占用并等待（请求和保持条件）**：一个进程已占有某些资源，而且正在其他资源，但这些资源已被其他进程占有
**不可剥夺**：已分配资源不能被剥夺。只能由进程自行释放
**循环等待**：存在一个进程循环等待其他进程的资源，形成环路
处理死锁方法：
**预防死锁**：通过破坏其他一个必要条件来避免
**避免死锁**：通过动态分配资源，确保系统始终处于安全状态，例：银行家算法
**检测和接解除死锁**：监控系统资源分配情况，检测死锁并采取措施，例：中止进程、回滚操作
**忽略死锁**：某些情况下，死锁发生概率很小，可以不做处理，交由用户自行解决
**安全状态**
**概念**：指系统能按某种进程顺序（P1、P2.....Pn），来为每个进程Pn分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都能顺利完成。如果系统无法找到这样一个==安全序列==，则称系统处于==不安全状态==。
# 公式
### 一、进程调度算法
1. **先来先服务（FCFS）算法**
- **周转时间**：完成时间 - 到达时间
- **平均周转时间**：所有进程周转时间之和 / 进程个数
- **带权周转时间**：周转时间 / 服务时间
- **平均带权周转时间**：所有进程带权周转时间之和 / 进程个数
2. **短作业优先（SJF）算法**
- **选择规则**：选择当前已到达且服务时间最短的作业（进程）执行
- **周转时间**：完成时间 - 到达时间
- **平均周转时间**：所有进程周转时间之和 / 进程个数
- **带权周转时间**：周转时间 / 服务时间
- **平均带权周转时间**：所有进程带权周转时间之和 / 进程个数
3. **高响应比优先（HRRN）算法**
- 等待时间：系统当前开始时间 - 进程到达时间
- **响应比**：（等待时间 + 要求服务时间）/ 要求服务时间
- **选择规则**：每次选择响应比最高的作业（进程）执行
- **周转时间**：完成时间 - 到达时间
- **平均周转时间**：所有进程周转时间之和 / 进程个数
- **带权周转时间**：周转时间 / 服务时间
- **平均带权周转时间**：所有进程带权周转时间之和 / 进程个数
4. **时间片轮转（RR）算法**
- **周转时间**：完成时间 - 到达时间
- **平均周转时间**：所有进程周转时间之和 / 进程个数
- **带权周转时间**：周转时间 / 服务时间
- **平均带权周转时间**：所有进程带权周转时间之和 / 进程个数
- **执行规则**：每个进程被分配一个时间片，轮流执行，时间片用完后，无论是否完成，都切换到下一个进程
### 二、页面置换算法
1. **最佳置换（OPT）算法**
- **预知未来页面的使用情况，从而选择在未来最长时间内不会被使用的页面进行置换。**
- **缺页次数**：统计在内存中不存在所需页面而需要从外存调入的次数
- **缺页率**：缺页次数 / 页面访问序列长度
- **置换规则**：选择未来最长时间内不会被访问的页面进行置换（实际难以实现，用于理论比较）
2. **先进先出（FIFO）算法**
- **是指先进入内存的页面先被替换出去。**
- **缺页次数**：统计在内存中不存在所需页面而需要从外存调入的次数
- **缺页率**：缺页次数 / 页面访问序列长度
- **置换规则**：选择最先进入内存的页面进行置换
3. **最近最久未使用（LRU）算法**
- **淘汰最近最少使用的页面。**
- **缺页次数**：统计在内存中不存在所需页面而需要从外存调入的次数
- **缺页率**：缺页次数 / 页面访问序列长度
- **置换规则**：选择最近最久未被使用的页面进行置换
### 三、磁盘调度算法
1. **先来先服务（FCFS）算法**
- **寻道时间**：磁头移动到指定磁道所需的时间，根据磁头移动的磁道数计算
- **总寻道时间**：所有寻道时间之和
- **平均寻道长度**：总寻道长度 / 磁盘请求个数
- **处理规则**：按照磁盘请求的到达顺序依次处理
2. **最短寻道时间优先（SSTF）算法**
- **寻道时间**：磁头移动到指定磁道所需的时间，根据磁头移动的磁道数计算
- **总寻道时间**：所有寻道时间之和
- **平均寻道长度**：总寻道长度 / 磁盘请求个数
- **处理规则**：选择与当前磁头位置距离最近的磁道请求进行处理
3. **扫描（SCAN）算法（电梯算法）**
- **寻道时间**：磁头移动到指定磁道所需的时间，根据磁头移动的磁道数计算
- **总寻道时间**：所有寻道时间之和
- **平均寻道长度**：总寻道长度 / 磁盘请求个数
- **处理规则**：磁头沿着一个方向移动，处理沿途的磁盘请求，直到到达一端，然后改变方向继续处理
4. **循环扫描（CSCAN）算法**
- **寻道时间**：磁头移动到指定磁道所需的时间，根据磁头移动的磁道数计算
- **总寻道时间**：所有寻道时间之和
- **平均寻道长度**：总寻道长度 / 磁盘请求个数
- **处理规则**：磁头沿着一个方向移动，处理沿途的磁盘请求，到达一端后，立即回到起始端，然后再沿相同方向处理
### 四、Cache 相关
1. **Cache 命中率计算**：Cache 命中次数 / 访问总次数
2. **平均访问时间**：命中率 ×Cache 访问时间 +(1 - 命中率)× 主存访问时间
### 五、虚拟存储器相关（以页式为例）
1. **用户作业最多页数**：虚拟地址空间大小 / 页面大小
2. **主存空间划分的块数**：主存容量 / 页面大小
3. **页号**：INT (逻辑地址 / 页面大小)
4. **页内地址**：逻辑地址 MOD 页面大小
5. **物理地址**：块号 × 页面大小 + 页内地址
6. 页内偏移：逻辑地址 MOD 页面大小
If you enjoyed this, leave a comment~