操作系统是硬件之上的第一层软件

操作系统相关概念

操作系统概述

• 管理系统的硬件,软件,数据资源
• 控制程序运行
• 人机之间的交互接口
• 应用软件与硬件之间的接口

工作范围

• 进程管理
• 存储管理
• 文件管理
• 作业管理
• 设备管理

特殊的操作系统

进程管理

进程的概念

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

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

[[进程与线程#_KRPOCESS结构体|PCB详细结构参考]]

进程与程序的区别

进程与程序的区别: 进程是程序的一次执行过程,没有程序就没有进程

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

进程与线程的区别

进程的2个基本属性: 可拥有资源的独立单位;可独立调度和分配资源的基本单位

进程的状态

• 三态模型
• 五态模型

三态模型

• 运行: 当一个进程在CPU上运行时 (单处理机处于运行态的进程只有一个)
• 就绪: 一个进程获得了除CPU外的一切所需资源(不会再被剥夺退回等待状态),一旦得到处理机即可运行
• 阻塞/等待/睡眠: 一个进程正在等待某一事件发生(例如请求I/O等待I/O完成等)而暂时停止运行,此时即使把CPU分配给进程也无法运行,故称进程处于阻塞状态

五态模型

考的多的是这个模型

主要是引入了挂起的概念

为什么要有挂起呢?

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

进程调度

重点考点

进程调度的概念

临界资源: 诸进程间需要互斥方式对其进行共享的资源 (进程中访问临界资源的那段代码称为临界区)

PV操作的概念

PV操作是操作系统提供的具有特定功能的原语,利用PV操作可以实现资源的互斥使用

p.s. 注意,利用PV操作无法提高资源利用率,因为只要使用锁就会降低资源利用率

PV操作由荷兰计算机科学家Edsger Dijkstra提出，通常用于信号量（Semaphore）的实现。PV操作中的”P”和”V”分别代表不同的操作：

下面括号中是荷兰语

1. P操作（Proberen）：

   • P操作的作用是请求资源。如果资源可用，则将其分配给请求的进程；如果资源不可用，则进程将被阻塞，直到资源可用为止。
   • 在信号量的上下文中，P操作通常会将信号量的值减1。如果信号量的值为0，表示没有可用的资源，进程需要等待。

2. V操作（Verhogen）：

   • V操作的作用是释放资源。当进程完成对资源的使用后，会调用V操作来释放资源，并通知其他可能在等待该资源的进程。
   • 在信号量的上下文中，V操作通常会将信号量的值加1。如果有其他进程在等待该信号量，它们将被唤醒并能够继续执行。

信号量(S): 是一种特殊的变量,在代码中是一个全局变量

• 信号量可以表示资源数量;
• 信号量为负数时还可以表示排队进程数

P操作

• S=S-1 => 申请/锁定资源
• S<0 => 检查资源是否足够,注意S=0表示资源依然是足够的

V操作

• S=S+1 => 释放/解锁资源
• S<=0 => 检查是否有进程排队,有人排队就通知

前趋图与PV操作

案例1

以包饺子为案例:

进程D在执行搅拌之前,需要检查前趋活动是否完成(P操作),即A,B,C是否完成;搅拌后需要通过V操作通知后继已经完成搅拌

五个进程需要四个信号量,信号量对应的是界线(前趋图中总共四条线,所以要用到四个信号量)

案例2

下面为看图填空:

最重要的是先根据线数确定要使用多少个信号量

案例3

假设某计算机系统中只有一个CPU、一台输入设备和一台输出设备，若系统中有四个作业T1、T2、T3和T4，系统采用优先级调度，且T1的优先级>T2的优先级>T3的优先级>T4的优先级。每个作业Ti具有三个程序段：输入Ii、计算Ci和输出Pi（i=1，2,3，4），其执行顺序为Ii->Ci->Pi,则前趋图为如下:

死锁

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

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

死锁的四大条件

• 互斥
• 保持和等待
• 不剥夺
• 环路等待 (等待链构成环路)

死锁的预防

• 打破四大条件
• 有序资源分配法
• 静态资源分配

死锁的避免

银行家算法

银行家算法的本质是通过预判资源分配后的系统状态，确保至少存在一个安全序列。它适用于资源分配场景中需要高可靠性的系统（如数据库、操作系统内核），但对实时系统和动态环境适应性较差。

• 优点：严格避免死锁，动态检查资源分配的安全性。
• 缺点：
  • 需要提前知道进程的最大资源需求，现实中难以预知。
  • 资源数量固定，扩展性差。
  • 频繁的安全性检查可能带来性能开销。

流程

1. 初始化：
   • 记录系统的总资源数（如内存、CPU等）。
   • 每个进程声明其最大资源需求（Max）。
   • 跟踪已分配给每个进程的资源（Allocation）。
   • 计算每个进程仍需的资源（Need = Max - Allocation）。
   • 维护当前可用资源数（Available）。
2. 资源请求检查：
   • 当进程请求资源时，系统先检查请求是否合法（即请求量 ≤ 进程的Need，且 ≤ 当前Available资源）。
   • 若合法，系统模拟分配资源，更新Available、Allocation和Need的值。
3. 安全性检查：
   • 检查是否存在一个安全序列，使得所有进程都能按顺序完成。
   • 算法通过尝试找到一个进程，其Need ≤ Available，并假设其完成任务后释放资源，循环此过程直到所有进程被检查。
4. 资源分配决策：
   • 若安全性检查通过，实际分配资源；否则拒绝请求，回滚模拟分配的状态。

举例说明

假设系统有3类资源（A/B/C），总资源数为（10, 5, 7）。
有5个进程（P0-P4），它们的Max和Allocation如下：

当前可用资源 **Available = (3, 3, 2)**。

安全性检查过程：

1. 检查进程P1（Need=(1,2,2) ≤ Available=(3,3,2)）：分配后释放资源，Available变为(5,3,2)。
2. 接着检查P3（Need=(0,1,1) ≤ Available=(5,3,2)）：释放后Available=(7,4,3)。
3. 依此类推，找到安全序列如 <P1 → P3 → P4 → P0 → P2>，系统安全。

死锁资源计算数

系统不可能发生死锁的情况如下:
$$
(每个进程需要的资源数-1)*进程数+1 <= 总资源数
$$
系统必定会发生死锁的情况如下:
$$
每个进程需要的资源数<总资源数
$$

案例1

例：系统有5个进程：A、B、C、D、E。这5个进程都需要4个系统资源。如果系统至少有多少个资源，则不可能发生死锁。

(4-1)*5+1 <= 16

因此至少有16个资源,则不可能发生死锁

案例2

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

不可能发生死锁的条件是:(i-1)*3+1<=8,即i<=7/3+1,即i<=3.33333...

所以可能会发生死锁的最小i值为4

进程资源图

进程资源图是某一个时刻的关于进程和资源关系的静态状况图

• 堵塞节点（Blocking Node）

  是指一个进程在等待某个资源而无法继续执行的状态

• 非堵塞节点（Non-blocking Node）

  非堵塞节点是指一个进程可以继续执行，不需要等待任何资源

• 可化简（Simplifiable）

  可化简状态指的是在资源图中，某些进程和资源的关系可以通过释放资源或调整分配来简化

• 死锁（Deadlock）

  死锁是指两个或多个进程互相等待对方释放资源，导致所有相关进程无法继续执行的状态

案例

先分析资源分配情况

段页式存储

• 页式存储
• 段式存储
• 段页式存储

页式存储

页式存储: 将程序与内存均划分为同样大小的块,以页为单位将程序调入内存

• 优点: 利用率高,碎片小,分配及管理简单
• 缺点: 增加了系统开销,可能产生抖动现象(某个页面经常被调入内存又被淘汰叫抖动)

• 逻辑地址 = 页号 + 页内地址
• 物理地址 = 页帧号 + 页内地址

假设,页式存储系统中,每个页的大小为4KB,逻辑地址为10 1100 1101 1110

首先要确定页内地址的范围,默认内存单元按照字节为单位(题目中没有特意提到),因此4KB的页内地址范围是$0~2^12$,即需要12位二进制来确定页内地址
由页内地址可以得知1100 1101 1110为页内地址,开头的10代表页号

上图中的页表中页号2对应的是编号6,因此物理地址为110 1100 1101 1110

标志位

某些页面可能不在内存之中,访问时触发缺页中断，从磁盘调入内存。这个时候需要依据访问位和修改位来确定淘汰哪些页面

淘汰机制,依赖下面的原则

• 访问位为0,即最近未被访问过

• 如果多个访问位为0,则淘汰修改位为0的内存页

  因为如果淘汰修改位为1的情况,需要同时去修改程序程序文件,即花销成本更高,因此放在最后再执行这种高消耗行为

页面置换算法其实有很多种

• 最优(Optimal,OPT)算法,也称为理想型
• 随机(RAND)算法
• 先进先出(FIFO)算法: 有可能产生”抖动”(很可能每次刚刚淘汰掉的就是接下来要用的)
• 最近最少使用(LRU)算法: 不会”抖动”,LRU的理论依据是”局部性原理“

例题

段式存储

页式存储的问题: 将程序划分为相同页面的大小,划分的过程中有可能刚好把循环条件放到上一个页中,而循环体却在下一个页面中.这种重复的调用的,很可能导致有些页面逻辑上是连续,但是调用的过程却是分散的,极大影响效率

段式存储是按照程序本身来进行划分,因此调用的过程是连续的

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

判断段地址是否合法,看: 段内偏移量不能超过段长.超过段长的访问会产生越界错误

非法判断例题

段页式存储

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

现代主流操作系统如Windows、Linux 和 macOS 都采用了段页式存储

• 优点: 空间浪费小,存储共享容易,存储保护容易,能动态连接
• 缺点: 由于管理软件的增加,复杂性和开销也随之增加,需要的硬件以及占用的内容也有所增加,使得执行速度大大下降

• 段表用于将段号 S 转换为该段的页表基地址。
• 页表用于将段内页号 P 转换为物理页帧号 F。
• 通过两次查表（段表 → 页表），最终获取物理地址

示例地址格式如下:

以该地址格式为例

• 最大段号为: $2^{31-24+1} = 2^{8}$
• 最大页号为: $2^{23-13+1} = 2^{11}$
• 最大页内地址: $2^{12-0+1} = 2^{13}$

例题

磁盘管理

• 磁道是硬盘上同一平面上的同心圆，用于存储数据。
• 扇区是磁道的最小存储单位，通常为512字节或4096字节。
• 柱面是由多个盘面上同一位置的磁道组成的集合。

$$
存取时间 = 寻道时间 + 等待时间
$$

寻道时间是指磁头移动到磁道所需的时间;等待时间为等待读写的扇区转到磁头下方所用的时间

上图为整个磁盘的大致结构

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

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

例题

例题1

结算过程: (10*10ms+100ms+2ms)*100 = 200 ms

例题2

移臂调度算法

• 先来先服务(FCFS)

  

• 最短寻道时间优先(SSTF)

  

• 扫描算法(SCAN)

  也叫电梯算法,是个双向算法

  磁头的行为就像大楼里面的电梯，先处理所有向上的请求，然后再处理相反方向的请求

• 循环扫描算法(CSCAN)

  • 扫描算法（SCAN）：磁头在一个方向上移动，处理所有请求，到达边界后反向移动。
  • 循环扫描算法（C-SCAN）：磁头在一个方向上移动，处理所有请求，到达边界后跳回另一端继续处理。

例题

例题1

例题2

题目中不存在这个图,下面图需要自己思考:

第一空

要注意的是: 处理过程中,磁盘还是在旋转的

R0的读取时间为: 读3ms + 处理3ms

R1的读取时间为: 读(30+3)ms + 处理3ms p.s.这里处理完R0到回到取到R1前是走10个块,即10*3ms =30 ms

R2及以后物理块的读取时间都与R1的读取时间等同

因此第一空总耗时为: 6+36*10 = 366 ms

第二空

由于R0处理完需要6ms,就把R1放到与R0间隔一个的位置上,处理完R1又要处理R2,继续将R2放置到与R1间隔一个的位置上.依次类推就把圆环都填满了

此时发现处理一个物理块只需要3ms+3ms=6 ms,即总耗时=6ms*11=66 ms

I/O管理

分层的目的是为了屏蔽硬件,提供高层抽象,使应用程序无需直接操作硬件

下面的细节仅了解就可以

• 用户级I/O层: 发出I/O调用

  由操作系统提供的系统调用接口和用户态库函数组成

• 设备无关I/O层: 设备名解析,阻塞进程,分配缓冲区

  功能:

  • 设备名解析：将用户提供的文件或设备名称解析为内部设备标识符（如 dev/sda1）。
  • 阻塞进程：如果设备不可用，则阻塞进程，避免 CPU 资源浪费。
  • 分配缓冲区：为 I/O 设备分配适当的缓冲区，减少设备访问次数，提高效率。
  • 统一接口：不同设备（磁盘、网络、打印机等）使用统一的接口，使用户态程序不必关心设备细节。

  实现方式:

  • 使用 设备驱动程序接口（Device Driver Interface, DDI） 与设备驱动层交互。
  • 采用 I/O调度 机制（如磁盘 I/O 调度算法）优化设备访问。
  • 维护设备表，记录每个设备的状态、类型、操作权限等信息。

• 设备驱动程序: 设置寄存器,检查设备状态

  功能:

  • 负责与具体的硬件设备交互，包括设置设备寄存器、检查设备状态、控制数据传输等。
  • 实现特定设备的 I/O 操作，如磁盘读写、网络数据发送/接收等。

  实现方式:

  • 操作系统为每种设备编写专门的 设备驱动程序，如磁盘驱动、显卡驱动、USB驱动等。
  • 设备驱动程序通常作为 内核模块（如 Linux 的 *.ko 模块）加载到内核中。
  • 通过 中断机制 处理异步I/O，减少 CPU 轮询等待的时间。

• 中断处理程序: I/O完成后唤醒设备驱动程序

• 硬件: 完成具体的I/O操作

例题

文件管理

文件相关概念

文件: 具有符号名的,在逻辑上具有完整意义的一组相关信息项的集合

逻辑结构: 有结构的记录式文件,无结构的流式文件

物理结构: 连续结构,链接结构,索引结构,多个物理块的索引表

文件目录:

• 文件目录项/文件的说明/文件控制块FCB
• 基本信息类: 文件名,文件的物理地址,文件长度和文件块数等
• 存储控制信息类: 文件的存储权限: 读写,执行权限等

文件属性包含: 只执行,隐含,只读,读/写,共享,系统

使用信息类: 文件建立日期,最后一次修改/访问日期,当前使用的信息,打开文件的进程数以及在文件上的等待队列等

目录结构

• 一级目录结构: 线性结构,查找速度慢,不允许重名和实现文件共享器
• 二级目录结构: 主文件目录(MFD) + 用户目录(UFD)
• 三级目录结构: 树形目录结构(多级目录结构)

例题

因为目录会指向多个应用程序,因此目录崩溃,对系统的影响相对其他选项较大

树形目录结构

• 绝对路径: 是从盘符开始的路径
• 相对路径: 从当前目录开始的路径
• 全文件名: 绝对路径 + 文件名

位示图

位示图(bitmap)

记录一个磁盘的时候,用比特位来表示一个字空间是否可用(包括空间/占用),类似于飞机座位选择图

物理块的数量应该是总容量除以每个块的大小: 300GB/1MB = 300K

由题可知,32位为一个字,300K个数量,每个物理块用一个位来表示,因此 $300K/32=300 \times 2^{10}/2^5=300 \times 32 = 9600$
所以位示图需要9600个字,才能展示300K个物理块

索引文件

例题

• 磁盘数据块大小 = 1KB
• 每个索引节点有 8 个地址项
• 直接地址索引：5 个（iaddr[0] ~ iaddr[4]）
• 一级间接地址索引：2 个（iaddr[5], iaddr[6]）
• 二级间接地址索引：1 个（iaddr[7]）
• 每个地址项占 4 字节（即 32 位寻址）
• 每个磁盘块存放的地址数 = $\frac{1024 \text{ B}}{4 \text{ B}} = 256$

第二个空计算如下:

1KB*5 + 256*1KB*2 + 256*256*1KB*1 =66,053 kB

作业管理

简单了解即可

作业调度算法

• 先来先服务

• 时间片轮转法

• 短作业优先法

• 最高优先权优先法

• 高响应比优先法
  $$
  响应比 = \frac {作业等待时间+作业执行时间}{作业执行时间}
  $$

例题

此例题在软考中并未出现过

J1先进行,进行到20分钟时,J2进入此时到下一个调度点至少需要等10分钟;进行到25分钟时,J3进入此时到下一个调度点至少需要等5分钟.当J1的30分钟执行完的时候,需要根据J2和J3的响应比来决定调度J2,还是J3

J2等待时间为: $\frac {10+20}{20} = 1.5$

J3等待时间为: $\frac {5+6}{6} \approx 1.8333$

J3响应比更大,所以J3优先