操作系统

1. 操作系统相关概念

1. 操作系统的作用

作用：

1. 管理系统的硬件、软件、数据资源
2. 控制程序运行
3. 人机之间的接口
4. 应用软件与硬件之间的接口

任务：

1. 进程管理
2. 存储管理
3. 文件管理
4. 作业管理
5. 设备管理

例题1

2. 特殊的操作系统

分类	特点
批处理操作系统	单道批：一次一个作业入内存，作业由程序、数据、作业说明书组成。 多道批：一次多个作业入内存，特点：多道、宏观上并行，微观上串行。
分时操作系统	采用时间片轮转的方式为多个用户提供服务，每个用户感觉独占系统。特点：多路性、独立性、交互性和及时性。
实时操作系统	分为实时操作系统和实时信息系统，特点：交互能力要求不高，可靠性要求高(规定时间内响应并处理)
网络操作系统	方便有效共享网络资源，提供服务软禁啊和有关协议的集合。主要的网络操作系统由：Unix、Linux 和 Windows Server 系统。
分布式操作系统	任意两台计算机可以通过通信交换信息。是网络操作系统的更高级形式，具有透明性、可靠性和高性能的特点。
微机操作系统	Windows：微软开发的图形用户界面，多任务、多线程的操作系统。 Linux：免费使用和自由传播的类 Unix 操作系统，多用户、多任务、多线程和多 CPU 的操作系统。
嵌入式操作系统	运行在智能芯片的环境上。特点：微型化、可定制(针对硬件变化配置)、实时性、可靠性、易移植性(HAL 和 BSP 支持)。

2. 进程管理

1. 进程的概念

1. 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的最小单位。由程序块、进程控制块 PCB 和数据块三部分组成。

PCB 是进程存在的唯一标志。内容包括进程标识符、状态、位置信息、控制信息、队列指针(链接同一状态的进程)、优先级、现场保护区等。

2. 进程是程序的一次执行过程，没有程序就没有进程。

3. 程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡；进程是程序进行资源分配和调度的独立单位，而程序不是。

4. 进程的两个基本属性：可拥有资源的独立单位；可独立调度和分配资源的基本单位。

1. 线程的概念

一个进程中可以包含多个线程，且线程之间可以共享一些资源，例如内存地址空间、代码、数据、文件等。但是程序计数器、寄存器、栈不可被共享。

2. 进程的状态

1. 运行：进程在 CPU 中运行时。
2. 就绪：一个进程获得了除 CPU 外当一切所需资源，一旦得到 CPU 即可转入运行状态。
3. 阻塞(等待)：阻塞也称为等待或睡眠状态，一个进程正在等待某个事件的发生而暂时停止运行，此时即使把 CPU 分配给这个进程也无法运行。

三态模型

五态模型

挂起的原因：

1. 进程过多，主存资源不够，此时必须将某些进程挂起，放到磁盘对换区，暂时不参与调度，以平衡系统负载。
2. 系统出现故障，或者是用户调试程序，也可能需要将进程挂起检查问题。

例题1

3. 进程的调度(重点)

1. PV 操作的概念

1. 进程的同步与互斥

同步：进程之间的速度有所差异，在一定情况下需要停下等待。直接制约关系

互斥：多个进程都使用临界资源时，会出现进程互斥。间接制约关系

Alt text

PV 操作可以控制程序进程的并发 ，解决进程同步问题。

PV 操作可以拆分为 P 和 V 操作，也可以分为 P(s)和 V(s)操作。其中 s 表示信号量。

信号量：一种特殊的变量，也可表示资源数量。当其为负数时，还可表示为排队进程数。

P 操作步骤：

1. S = S -1：用于申请/锁定资源
2. 判断 S < 0，false 时继续执行，true 时进入阻塞进程队列，表示资源不足。

S 操作步骤：

1. S = S + 1：用于释放/解锁资源
2. 判断 S <= 0，false 时继续执行，true 时从阻塞进程队列中取出进程并唤醒。

信号量与PV操作的过程

例题 1：PV 操作时操作系统提供的具有特定功能的原语，利用 PV 操作可以：

1. 保证系统不发生死锁。 错误，PV 操作是一个加锁和解锁的过程，所以不可能不发生死锁
2. 实现资源的互斥使用。 正确，PV 操作保证资源的互斥访问
3. 提高资源利用率。错误，阻塞会降低资源利用率
4. 推迟进程使用共享资源的时间。共享资源不需要 PV 操作，临界资源才需要

例题 2：假设系统中有 n 个进程共享 3 台扫描仪，并采用 PV 操作实现进程同步和互斥。若系统信号量 S 当前为-1，进程 P1 和 P2 分别执行了一次 P(s)操作，则当前系统信号量为多少？

1. P(s)为 S = S - 1
2. 当前信号量 S = -1 -1 -1 = -3

2. 信号量与 PV 操作

1. PV操作与互斥模型

针对临界资源的使用，先使用P(s)锁定资源，确保同一时刻只有一个使用该资源，再使用V(s)释放资源。

S初始值对应资源的个数。

P和V操作在一个进程中成对出现。

2. PV操作与同步模型

P和V操作在多个进程之间成对出现。

3. 互斥和同步模型结合

单缓冲区生产者、消费者问题。

缓冲区是一个临界资源。

互斥和同步模型

例题：

PV操作例题

答案

3. 前趋图与 PV 操作(重要)

前趋图是节点与节点之间有明显的逻辑先后关系的图。箭头符号→表示"必须完成后才能开始"的约束关系。箭头流出的为前趋， 箭头流入的为后继。

信号量与进程无关。

1. 后继执行P(s)操作，检查前趋是否完成，前趋完成执行V(s)。

例题：

例题

1. 依据下面的图，可以推出是s1为p1～p2的信号量，则a为两个V操作，符合的答案只有V(s1) V(s2)，则s2为p1～p3的信号量。

2. 因为P4为P(s3)，则s3为p2～p4的信号量，则b答案为V(s3)。

3. c答案为p(s2)，由p4为p(s3)，e为v操作，且不可能为v(s3)，则e为v(s5)，s5为p4～p5的信号量，则s4为p3～p5的信号量。d答案为v(s4)。

4. e答案为v(s5),f答案为p(s4)和p(s5)。

4. 死锁资源数计算

所谓的死锁，值两个以上的进程互相都要求使用对方已经占有的资源导致无法继续运行下去的现象。

1. 死锁的四大基本条件
   1. 互斥
   2. 保存和等待
   3. 不剥夺
   4. 环路等待

如何避免死锁？

1. 预防：打破四大基本条件：有序资源分配法、静态资源分配
2. 避免：银行家算法
3. 检测与解除：人为检测，认为解除死锁
4. 鸵鸟策略：不予理会

进程管理时操作系统的核心，如果操作不当，就会出现死锁。如果进程在等待一件不可能发生的事，则进程就死锁了。如果多个进程发生死锁，就会造成系统死锁。

系统不可能发生死锁的最小资源数：(w - 1) * m + 1 <= n，其中w为进程所需资源数，m为进程数，n为所需最小资源数。例如：系统有5个进程A、B、C、D、E，每个进程都需4个系统资源，系统至少有多少个资源，则不可能发生死锁？

1. n < 4是，一定会发生死锁，此时一个进程都执行不完整。
2. n >=4时，可能不会发生死锁，但也有可能发生死锁，系统可能会将资源分配到别的进程中，导致一个进程执行不完。
3. n >= 15 + 1时，不会发生死锁，此时无论如何分配，最少都会有一个进程执行完成，如何将其资源释放到其他进程中。

例题：某计算机系统中互斥资源R的可用数为8，系统中有3个进程P1、P2、P3竞争R，且每个进程都需要i个R，该系统可能会发生死锁的最小i值为？

1. i = 1时，三个进程一共需要3个R，完成满足，不会发生死锁。
2. i = 2时，三个进程一共需要6个R，完成满足，不会发生死锁。
3. i = 3时，三个进程最少需要7个R，完成满足，不会发生死锁。
4. i = 4时，三个进程最少需要10个R，可能会发生死锁。

公式计算：(i - 1) * 3 + 1 <= 8，i<=3.33333，则可以证明i <= 3时不可能发生死锁，可能会发生死锁的i值最小为4。

5. 进程资源图

进程资源图是表示资源调度的一种方式。

进程资源图

例题

1. 先将资源列出来，R1为2 R2为3。
2. 找出进程消耗的资源，R1被P1、P3占用，剩余为0。R2被P2、P3占用，剩余1个资源。
3. P1需要向R2申请一个资源，此时R2刚好有一个，所以P1为非阻塞。
4. P2需要向R1申请一个资源，但是R1没有多远资源，P2阻塞。

6. 段页式存储

1. 页式存储

页式存储：将程序与内存划分为同样大小的块，以页为单位将程序调入内存。

页式存储

Alt text

优点：利用率高、碎片小、分配和管理接单

缺点：增加系统开销，可能会产生抖动现象

断页式存储

某些页码不在内存中，则称为断页式存储。

如何将不在内存中的页调入内存，采用以下方式将之前的页面进行淘汰：

1. 访问位为0：优先淘汰访问位为0的页
2. 若访问位为0有多个，则优先淘汰修改位为0的页

页式存储组织

页码置换算法

1. 最优算法OPT -- 理想型：通过算法计算出哪些页码应该被优先淘汰
2. 随机算法：随机淘汰一些页码，稳定性非常差
3. 先进先出算法FIFO：可能会产生一些抖动
4. 最近最少使用算法LRU：理论依据是局部性原理，不会产生抖动

例题

2. 段式存储

段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段段长度可以不一样。

逻辑地址(段号，段内偏移量)

偏移量不得超过段长！

优点：多道程序共享内存，各段程序修改互不影响 缺点：内存利用率低，内存碎片浪费大

段式存储 v

例题

3. 段页式存储

段页式存储：段式与页式的综合体。先分段，再分页。一个程序有若干个段，每个段中有若干个页，每个页大小相同，但是每个段的大小不同。

段页式存储

例题：段页式存储的地址结构如下图，则系统最多也多少个段？每个段最多有多少个页？每页大小为多少？

段页式存储地址结构

1. 最多有$2^8 = 256$个段
2. 每个段最多有$2^11 = 2048$个页
3. 每页大小为$2^13 = 8K$

7. 磁盘管理

1. 磁盘 由磁道、扇区、0磁道组成。
2. 存取时间 = 寻道时间 + 等待时间。寻道时间是指磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间。

磁盘结构

读取磁盘数据的时间应该包括以下三部分：

1. 找磁道的时间
2. 找块(扇区)的时间，即旋转延迟时间
3. 传输时间

例题：某磁盘头从一个磁道转移到另外一个磁道需要10ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均移动距离为10个磁道，每块的旋转延迟时间及传输时间为100ms和2ms，则读取100块的文件需要多少ms的时间？

1. (10ms * 10 + 100ms + 2ms) * 100 = 20200ms

1. 先来先服务算法

先来先服务

2. 最短寻道优先算法

最短寻道优先

例题：假设磁盘块与缓冲区大小相同，每个盘块读入缓冲区的时间为15us，由缓冲区送至用户区的时间为5us，在用户区内系统对每块数据的处理时间为1us，若用户需要将10个磁盘块Doc1文件逐块从磁盘读入缓冲区，并送至用户区进行处理，那么采用单缓冲区需要花费的时间为多少？采用双缓冲区需要花费的时间为多少？

1. 单缓冲区时
   1. 缓冲区的特点为一个时刻只允许一个数据块占用。
   2. 拆分为两个步骤：首先数据传入15us+缓冲区送至用户区5us = 20us，然后用户处理1us，但是用户处理可以跟读入缓冲区并行，则时间为:21(建立流水线) + 20 * 9(每隔20us完成一个) = 201us;

单缓冲区

2. 双缓冲区时：
   1. 21(建立流水线) + 15 * 9(其余每隔15us完成一个) = 156us;

双缓冲区

例题2：最短寻道

最短寻道

例题3：

未优化时：

1. 磁道均分为11个物理块，则每个读取时间为33ms / 11 = 3ms
2. R0读取+处理时间为：3ms + 3ms = 6ms
3. R1读取+处理时间为：33ms + 3ms = 36ms
4. R2～R10均和R1一致，则完成时间为6 + 360 = 366ms；

未优化

优化时：

1. 读取+处理时间为6ms，则读完R0时，最好下一个是读取R1，R1放置于原R2位置，则旋转两圈即可完成处理。
2. 时间为：(3 + 3) * 11 = 66ms

优化

8. I/O管理软件

1. 硬件：完成具体的I/O操作
2. 中断处理程序：I/O完成后唤醒设备驱动程序
3. 设备驱动程序：设置寄存器，检查设备状态
4. 设备无关I/O层：设备名解析、阻塞进程、分配缓冲区
5. 用户级I/O层：发出I/O调用

I/O管理软件层次

9. 文件管理

1. 文件相关概念

1. 文件：具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。

2. 逻辑结构：有结构的记录式文件、无结构的流式文件。

3. 物理结构：连续结构、链式结构、索引结构、多个物理块的索引表。

4. 文件目录：

   1. 文件目录项/文件的说明/文件控制块FCB

   基本信息类：文件名、文件的物理地址、文件长度和文件块数等。

   存储控制信息类：文件的存储权限：读写、执行等。

   使用信息类：文件等见鹿日期、最后一次修改/访问日期、当前使用的信息、打开文件的进程数以及在文件上的等待队列。

5. 目录结构

   1. 一级目录结构：线性结构，查找速度慢，不允许重名和实现文件共享。
   2. 二级目录结构：主文件目录(MFD)+用户目录(UFD)
   3. 三级目录结构：树形目录结构(多级目录结构)

2. 树形目录结构(绝对路径与相对路径)

绝对路径：是从盘符开始的路径 相对路径：从当前目录的下一级目录开始 全文件名：绝对路径 + 文件名

3. 位示图

位式图：区分磁盘中空间可用和不可用

计算位式图

1. 计算存储个数：$300GB / 1MB = 300 * 2^{10个}$

2. 计算字$300 * 2^{10} / 32 = 300 * 32 = 9600$

4. 索引文件

文件索引结构

例题

10. 作业管理

作业管理

算法：

1. 先来先服务
2. 时间片轮转法
3. 短作业优先发
4. 最高优先权优先法
5. 高响应比优先法：响应比 = (作业等待时间+作业执行时间) / 作业执行时间

例题