❮
❯
TOC
KINA

KINA-0

Start having fun with KINA right now!
分类 软考高级

计算机公共基础知识（2）：操作系统

作者

考点：

  • 计算机系统概述
  • 操作系统 ⭐️⭐️⭐️⭐️
    • 操作系统概述
    • 进程管理
    • 存储管理
    • 磁盘管理
  • ⽂件系统 ⭐️⭐️
    • ⽂件系统概述
    • 索引⽂件
    • 位示图
  • 系统性能 ⭐️
    • 性能指标
    • 性能设计
    • 性能评估

操作系统 lite

1 操作系统概述

软件分层（从外到内）：

  1. 应用程序
  2. 语言处理程序
  3. 操作系统
  4. 计算机硬件（裸机）

操作系统（Operating System，OS）是最接近硬件的软件。

作⽤：

  • 管理系统的硬件、软件、数据资源
  • 控制程序运⾏
  • ⼈机之间的接⼝
  • 应⽤软件与硬件之间的接⼝

特殊的操作系统（详见嵌入式系统篇）：

分类 说明
批处理操作系统 单道批：⼀次⼀个作业⼊内存，作业由程序、数据、作业说明书组成
多道批：⼀次多个作业⼊内存，特点：多道、宏观上并⾏微观上串⾏
分时操作系统 采⽤时间⽚轮转的⽅式为多个⽤户提供服务，每个⽤户感觉独占系统
特点：多路性、独⽴性、交互性和及时性
【实时操作系统】 实时控制系统和实时信息系统
交互能⼒要求不⾼，可靠性要求⾼（规定时间内响应并处理）
⽹络操作系统 ⽅便有效共享⽹络资源，提供服务软件和有关协议的集合（常作为服务器）
主要的⽹络操作系统：Unix、Linux和Windows Server系统
分布式操作系统 任意两台计算机可以通过通信交换信息。是⽹络操作系统的更⾼级形式，具有透明性、可靠性和⾼性能等特性
微机操作系统 Windows：Microsoft开发的图形⽤户界⾯、多任务、多线程操作系统
Linux：免费使⽤和⾃由传播的类Unix操作系统，多⽤户、多任务、多线程和多CPU的操作系统
【嵌⼊式操作系统】 运⾏在智能芯⽚环境中
特点：微型化、可定制（针对硬件变化配置）、实时性、可靠性、易移植性（HAL和BSP⽀持）

2 进程管理

2.1 进程的基本概念

进程（Process）是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

组成：

  1. 程序块
  2. 进程控制块（Process Control Block，PCB）：进程存在的唯一标志，内容包含进程标识符、状态、位置信息、控制信息、队列指针（链接同一状态的进程）、优先级、现场保护区等。
  3. 数据块

进程与程序：

  • 进程是程序的一次执行过程，没有程序就没有进程。
  • 程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡
  • 进程是系统进行资源分配和调度的独立单位，而程序不是。

进程与线程（Thread）：

  • 一个进程可包含多个线程
  • 线程可共享的内容：内存地址空间、代码、数据（全局变量）、文件等
  • 线程不可共享的内容：程序计数器、寄存器、栈

进程与线程

2.2 进程的状态

操作系统三态模型及考虑挂起的模型为非抢占式；PCB组织方式任意）如下图所示

相关概念：

  • 就绪队列、阻塞队列
  • 挂起：进入磁盘区

进程状态

2.3 进程的同步与互斥

进程的同步与互斥相关概念：

  • 互斥（Mutual Exclusion）：同类资源（临界资源）的竞争关系（间接制约关系）
  • 同步（Synchronization）：速度有差异，在⼀定情况停下等待，进程间的协作关系（先后顺序）（直接制约关系）
  • 临界资源（Critical Resource）：各进程间需要互斥⽅式对其进⾏共享的资源，如打印机、磁带机、缓冲区等
  • 临界区（Critical Section）：每个进程中访问临界资源的代码称为临界区
  • 信号量（Semaphore）：⼀种特殊的全局变量
    • 为正数时，记录资源数量（最大值即为能进入互斥段的最大进程数）
    • 为负数时，表示排队进程数（最小值即为阻塞队列中的最大进程数）
    • 互斥量（Mutex）：一种特殊的二值信号量，只能取0或1

2.4 PV操作

PV操作一定成对出现，定义及每一步的意义如下：

  • P操作（Passeren）
    1. 对信号量减1：资源数量减1，即申请并占用资源（加锁）
    2. 判断信号量是否小于0：检查资源是否充足
      • 若是（表示资源不足），则当前进程进入阻塞队列
      • 否则继续执行后续代码
  • V操作（Verhoog）
    1. 对信号量加1：资源数量加1，即释放资源（解锁）
    2. 判断信号量是否小于等于0：检查是否有进程在阻塞队列里排队（“小于等于”：S < 0 ⇒ S' < 1 (S' = S + 1)，即S' <= 0）
      • 若是（说明有进程在阻塞队列里），则唤醒阻塞进程；无论如何都继续执行后续代码

PV操作

2.3 互斥模型示例

多个进程共享一台打印机问题，如下所示：

使用打印机;
后续代码;

为保证互斥，添加PV操作：定义互斥信号量S（初值为1），用之前加锁，用之后解锁。如下所示：

int S = 1;

P(S);
使用打印机;
V(S);
后续代码;

2.4 同步模型示例

生产者消费者问题（Producer-consumer Problem）：根据缓冲区大小分为单缓冲区情况和多缓冲区情况。如下所示：

生产者消费者问题

未使用PV操作：

生产者 {
    生产一个产品;
    送产品到缓冲区;
}

消费者 {
    从缓冲区取产品;
    消费产品;
}

使用PV操作（设置同步信号量S1、S2）：

int S1 = 1;     // 空间资源（单缓冲区情况初始为1，m缓冲区则为m）
int S2 = 0;     // 产品资源（初始情况缓冲区无产品）

生产者 {
    生产一个产品;
    P(S1);
    送产品到缓冲区;
    V(S2);
}

消费者 {
    P(S2);
    从缓冲区取产品;
    V(S1);
    消费产品;
}

为保证缓冲区每时刻只有1位能访问，追加互斥信号量S0：

int S1 = 1;
int S2 = 0;
int S0 = 1;     // 缓冲区访问权（每时刻只有1位能访问）

生产者 {
    生产一个产品;
    P(S1);
    P(S0);
    送产品到缓冲区;
    V(S0);
    V(S2);
}

消费者 {
    P(S2);
    P(S0);
    从缓冲区取产品;
    V(S0);
    V(S1);
    消费产品;
}

2.5 前趋图

前趋图（Precedence Graph）是一个有向无环图（DAG），以图的形式表示进程的关系。在前趋图中，1个箭头表示1个前趋关系，例如A有箭头指向D，则记录为(A, D)。前趋进程完成后通知所有后继进程；后继进程开始前要检查前趋进程是否已全部完成。没有前趋进程的结点称为起始进程，没有后继进程的结点称为终结进程。

由于前趋图中的前趋关系（箭头）表示一种工序制约关系，因此属于同步模型。添加PV操作的技巧：

  • 实现并发的信号量初值⼀般为0，1条边对应1个信号量，注意信号量变量名的具体命名方式
  • 并发图中某活动有后继就有V操作（释放资源并通知后继活动）、有前趋就有P操作（检查资源是否⾜够），所操作的信号量即为该入/出边所对应的信号量。

【例】下图以包饺子的过程（A：绞肉；B：切葱末；C：切姜末；D：搅拌；E：包饺子）为例，分别以伪代码和图示来表示：

前趋图

2.6 死锁

进程管理是操作系统的核⼼，但如果设计不当，就会出现死锁（Deadlock）的问题。如果⼀个进程在等待⼀件不可能发⽣的事，则进程就死锁。⽽如果⼀个或多个进程产⽣死锁，就会造成系统死锁。对于某一进程序列，如果可以一直进行到底则称为安全的，如果中途某一进程无法被满足需求而死锁则称为不安全的。

2.6.1 死锁的条件与对策

4个必要条件：

  1. 互斥
  2. 保持和等待
  3. 不剥夺
  4. 环路等待

相关对策：

  • 死锁的预防：打破四大条件
  • 死锁的避免：有序资源分配法、银行家算法

死锁的计算公式：假设有m个共享资源，n个进程，每个进程所需的最⼤资源数为w，则

  • 当m > n * (w - 1)时，不会死锁
  • 当m <= n * (w - 1)时，可能死锁

2.6.2 银行家算法

银⾏家算法（Banker's Algorithm）：分配资源的规则——

  1. 当⼀个进程对资源的最⼤需求量不超过系统中的资源数时可以接纳该进程。
  2. 进程可以分期请求资源，但请求的总数不能超过最⼤需求量。
  3. 当系统现有的资源不能满⾜进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间⾥得到资源。

核心要点：

  • 时刻注意系统重剩余资源数
  • 当前被分配资源的进程应能被彻底满足需求，否则死锁
  • 当某进程彻底满足了需求后，即刻释放全部资源

【例】假设系统中有三类互斥资源R1、R2、R3，可用资源分别是9、8、5。在T0时刻系统中有P1、P2、P3、P4和P5五个进程，这些进程对资源的最大需求量和已分配资源数的进程资源表如下所示。如果进程按（?）序列执行，则系统状态是安全的。
A. P1 → P2 → P4 → P5 → P3
B. P2 → P4 → P5 → P1 → P3
C. P2 → P1 → P4 → P5 → P3
D. P4 → P2 → P5 → P1 → P3
进程资源表
【解】首先计算剩余资源数：R1 = 9 - (1 + 2 + 2 + 1 + 1) = 2、R2 = 8 - (2 + 1 + 1 + 2 + 1) = 1、R3 = 5 - (1 + 1 + 3) = 0，以及P1~P5进程的还需资源数（三元组对应(R1, R2, R3)）：P1: (5, 3, 1)、P2: (0, 1, 0)、P3: (6, 0, 1)、P4: (0, 0, 1)、P5: (2, 3, 1)。根据各选项顺次分配、回收资源即可，出现死锁则不安全。答案为B。

3 存储管理

存储管理的主要目的是解决多个用户使用主存的问题。常用方法有页式存储、段式存储、段⻚式存储，其中前两种考察较多。

3.1 页式存储

⻚式存储（分页存储）：将程序与内存均划分为同等⼤⼩的块，以⻚为单位将程序调⼊内存

  • 优点：利⽤率⾼，碎⽚⼩，分配及管理简单
  • 缺点：增加了系统开销；可能产⽣抖动现象

逻辑地址与物理地址：

  • 逻辑地址：页号, 页内地址，高级程序语言使用
  • 物理地址：页帧号, 页内地址，内存中使用
  • 页号、页帧号均位于地址的第1位（十六进制）
    • 【例】设每个页的大小为4KB，有逻辑地址10 1100 1101 1110（第1部分10为页号），则其所对应的物理地址为110 1100 1101 1110（第1部分110为页帧号）

地址重定位：将程序中的虚拟地址（逻辑地址）变换成内存的真实地址（物理地址）的过程

页式存储

页面淘汰算法：按顺序（优先级）判定是否淘汰（离开内存）：

  1. 淘汰状态位为1的页面
  2. 淘汰访问位为0的页面
  3. 淘汰修改位为0的页面

页面淘汰

3.2 段式存储

段式存储：按⽤户作业中的⾃然段来划分逻辑空间，然后调⼊内存，段的⻓度可以不⼀样。

  • 优点：多道程序共享内存，各段程序修改互不影响
  • 缺点：内存利⽤率低，内存碎⽚浪费⼤

逻辑段地址：段号, 段内偏移量

段式存储

【例】如图所示，(0, 25K)是合法段地址，(0, 35K)是非法段地址（逻辑地址到物理地址转换时地址越界）

3.3 段⻚式存储

段⻚式存储：段式与⻚式的综合体。先分段，再分⻚。1个程序有若⼲个段，每个段中可以有若⼲⻚，每个⻚的⼤⼩相同，但每个段的⼤⼩不同。

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

地址构造：段号, 页号, 页内地址

段⻚式存储

3.4 快表

快表是一块小容量的相联存储器（Associative Memory），由高速缓存器组成，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。

快表：将页表存于Cache上；慢表：将页表存于内存上。

3.5 虚拟内存

在前述的存储管理方案中，必须为每个作业分配足够的空间，以便装入全部信息。当主存空间不能满足作业要求时，作业无法装入主存执行。如果一个作业只部分装入主存便可开始启动运行.其余部分暂时留在磁盘上，在需要时再装入主存，这样可以有效地利用主存空间。从用户角度看，该系统所具有的主存容量将比实际主存容量大得多，人们把这样的存储器称为虚拟存储器。

4 文件系统 ⭐️⭐️

操作系统为了实现“按名存取”，必须为每个文件设置用于描述和控制文件的数据结构，专门用于文件的检索，因此至少要包括文件名和存放文件的物理地址，该数据结构称为文件控制块（File Control Block，FCB），文件控制块的有序集合称为文件目录（或称系统目录文件）。若操作系统正在将修改后的系统目录文件写回磁盘时系统发生崩溃，则对系统的影响相对较大。

4.1 索引⽂件结构

文件在逻辑上一定是连续的，在物理上可以是分散的。

索引文件结构的基本框架如下图所示（注：最末端表示实际文件，框中数字为逻辑块号；索引节点的框中数字为物理块号！）：

索引文件结构

索引结点对应的索引⽅式⼀般题⼲会给出，没有给出的默认按照如图所示⽅式理解，下述的⽂件⼤⼩依图给出计算过程。

  • 直接索引范围 ：索引块数量 * 索引块大小
  • 一级间接索引范围 ：(数据块大小 / 地址项大小) * 索引块大小
  • 二级间接索引范围 ：(数据块大小 / 地址项大小)^2 * 索引块大小
  • 三级间接索引范围 ：(数据块大小 / 地址项大小)^3 * 索引块大小

磁盘数据块 = 物理盘块（索引节点）

例：1KB / 4B = 256

4.2 位示图

文件空间管理方式：空闲区表法（空闲文件目录）、空闲链表法、位示图法、成组链接法

位示图（Bitmap）如下所示：

位示图

  • 每1个bit位（物理块）表示1个磁盘的占⽤情况，0表示空闲，1表示占⽤。物理块数计算式：
物理块数 = 磁盘容量 / 物理块大小
  • 字的⻓度与具体机器字⻓有关（如图所示的机器字⻓为16位，则每个字可以表示16个磁盘块的占⽤情况）。位示图的大小（字数）计算式：
位示图的大小 = 物理块数 / 机器字长 = 磁盘容量 / 物理块大小 / 机器字长
  • 注意其中磁盘序号、字的序号、对应位号都是从0开始

4.3 树形目录结构

树形目录结构（多级目录结构）在Windows和Unix系统中均十分常见。

  • 绝对路径：从盘符开始
  • 相对路径：从当前目录开始

树形目录结构

文件属性：

  • R：只读文件属性
  • A：存档属性
  • S：系统文件
  • H：隐藏文件

文件名的组成：

  • 驱动器号
  • 路径
  • 主文件名
  • 扩展名

【例】如图所示，若当前目录为D1，要求F2的路径，则：绝对路径为/D1/W2/F2，相对路径为W2/F2

5 设备管理

5.1 数据传输控制方式

设备输入/输出（I/O）管理的方式（从上往下CPU的工作量越来越少，效率从上往下越来越高）：

  1. 程序控制方式【CPU与I/O串行工作】： 分为无条件传送（默认）和程序查询方式。
    • 程序查询方式：CPU必须不停的测试I/O设备的状态端口。
    • 特点：方法简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率。（一直等待响应）
  2. 程序中断方式【CPU与I/O并行工作】：打断点，使用栈保存现场，调取中断向量表，由此作为入口进行I/O操作（如下图所示）。
    • 特点：与程序控制方式相比，中断方式因为CPU无需等待而能对突发事件做出快速响应。
  3. DMA（Direct Memory Access，直接内存存取）【CPU与I/O并行工作】：为了在【主存】与【外设】之间实现高速、批量数据交换而设置，由DMAC（DMA控制器）进行处理。
    • 过程：DMAC向总线裁决逻辑提出总线请求，CPU执行完当前总线周期即可释放总线控制权。此时DMA响应，通过DMAC通知I/O接口开始DMA传输。
    • 特点：比程序控制方式与中断方式都高效。
  4. 通道方式【CPU与I/O并行工作】：主机中有专门的通道处理器，CPU干预更少，有对应的通道程序和通道状态字保存在内存中，CPU向通道处理器发出启动指令即可不管，通道处理器执行通道程序控制设备传输完所有数据之后发起一个中断交给CPU处理，设备挂接在通道上。【纯硬件方式】
  5. I/O处理机（Input/Output Processor，IOP）【CPU与I/O并行工作】：独立系统，有自己的内存、指令熊、中断，专用于大型高效系统的输入输出设备控制，利用共享存储器等与主机交换信息。输入输出处理机中可能有多个通道连接设备。【纯硬件方式】

程序中断方式

5.2 I/O管理软件

层次如下所示，I/O请求逐层从上到下，I/O应答逐层从下到上：

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

5.3 SPOOLing技术

SPOOLing（Simultaneous Peripheral Operation On-Line，外部设备联机并行操作）是关于慢速字符设备如何与计算机主机交换信息的一种技术。经常用于虚拟输入输出设备，俗称"假脱机技术"。

组成：

  1. 输入井、输出井：在磁盘上开辟的两个存储区域，用于存放I/O设备输入的数据和用户程序向设备输出的数据
  2. 输入缓存区、输出缓冲区：在内存中开辟的两个缓冲区。输入缓冲区用户暂存输入设备送来的数据，再送入输入井；输出缓冲区暂存从输出井送来的数据，再传送到输出设备
  3. 输入进程、输出进程：负责传输输入输出的数据

核心操作：先将数据放入磁盘缓冲区，再放入设备区（在磁盘上开辟相应的区域，故缓冲区在外存）

示例：将一台独享打印机改造为可供多个用户共享的打印机。

特点：

  • 提高了I/O速度，通过对输入井和输出井的操作，缓和了主机和外设速度不匹配的矛盾
  • 设备没有直接和用户进程关联
  • 实现虚拟设备，多个进程同时使用一个逻辑设备，每个进程都认为自己独占了设备

发表评论