软考高级之系统架构师系列之操作系统基础

概念

中断

操作系统定义两种程序执行模式（用户模式和内核模式），应用程序在用户模式下使用特权指令引起的中断是访管中断。用户程序执行特权指令时，CPU触发访管中断（Supervisor Call/系统调用），切入内核模式处理。这是操作系统提供用户程序访问内核服务的标准机制。溢出中断由算术溢出触发；外部中断由外设触发；信号中断是进程间通信机制。

接口

操作系统为用户提供两类接口：操作一级的接口和程序控制一级的接口。操作一级的接口包括操作控制命令、菜单命令等；程序控制一级的接口包括系统调用。

链接

分为硬链接和软链接：

• 硬链接：Hard Link，指向i节点的不同目录项；多个文件名指向同一个inode。同一文件系统的i节点是唯一的，因此硬链接不能跨文件系统。不能链接目录。删除源文件后，硬链接仍然有效（直到链接计数为0）；删除最后一个链接才删除文件。
• 软链接：Symbolic Link，即符号链接，是一个特殊文件，包含另一文件的路径名。存储目标路径，可以跨文件系统、链接目录，但会因目标删除而失效。删除源文件后，软链接则失效。软链接的i节点号与源文件不同。

UMA和NUMA

UMA，统一内存访问，Uniform Memory Access，指所有的物理存储器被均匀共享，即处理器访问它们的时间是一样的。UMA亦称作统一寻址技术或统一内存存取架构。这种系统因为高度的资源共享也被称为紧耦合系统（Tightly Coupled System）。

NUMA，非统一内存访问架构，Non-Uniform Memory Access，是一种为多处理器的电脑设计的内存架构，内存访问时间取决于内存相对于处理器的位置。在NUMA下，处理器访问它自己的本地内存的速度比非本地内存（内存位于另一个处理器，或是处理器之间共享的内存）快一些。

进程

组成：进程控制块PCB（唯一标志）、程序（描述进程要做什么）、数据（存放进程是所需要的数据）

临界资源：各进程间需要以互斥方式访问的资源
临界区：每个进程中对临界资源操作的那段程序
互斥信号量：初值为1
同步信号量：初值为共享资源的数量
信号量：是一种特殊的变量

在引入线程的操作系统中，线程是CPU调度的基本单位（轻量级进程），进程是资源分配的基本单位（拥有地址空间、文件句柄等资源）。线程切换开销远小于进程切换。

PCB

进程控制块，其组织方式有：

• 线性表方式：不论进程的状态如何，将所有PCB连续地存放在内存的系统区。适用于系统中进程数目不多的情况
• 索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等
• 链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列等。

状态切换

参考进程、线程和协程的区别与联系。

PV操作

参考PV操作及软考高级试题解析。

死锁

进程死锁的四个必要条件：

• 资源互斥
• 每个进程占用资源并等待其他资源
• 系统不能剥夺进程资源
• 进程资源图是一个环路

不能作为预防死锁措施的是：破坏’互斥’条件。互斥条件（资源本身特性决定）通常不能破坏，因为某些资源（如打印机、互斥锁）天生就是互斥的。预防死锁的另外三个条件（循环等待、不可抢占、请求和保持）都可通过特定策略破坏。

银行家算法是死锁避免的著名算法，其核心数据结构：

• Available（可用资源向量）：当前可用各类资源数量
• Max（最大需求矩阵）：各进程对各类资源的最大需求
• Allocation（已分配矩阵）：各进程已分配的资源
• Need（需求矩阵）：各进程还需多少资源

算法在每次资源分配前检查安全性，确保系统处于安全状态。

在银行家算法中，当进程P1和P3分别申请资源R时，系统如何分配？
解读：银行家算法通过安全性检查来判断是否可以分配资源。如果分配后系统状态是安全的，则允许分配。只有先给P3分配才能使系统进入安全状态，因此只能先给P3分配。

死锁进程计算：n个进程、每个进程都需要R资源

• 发生死锁的最大资源数：n ∗ ( R − 1 ) n*(R-1)n∗(R−1)
• 不发生死锁的最小资源数：n ∗ ( R − 1 ) + 1 n*(R-1)+1n∗(R−1)+1

存储

存取方式

存储器中数据常用的存取方式：

• 顺序存取：存储器的数据以记录的形式进行组织。对数据的访问必须按特定的线性顺序进行。磁带存储器采用顺序存取的方式。
• 直接存取：与顺序存取相似，直接存取也使用一个共享的读写装置对所有的数据进行访问。但是，每个数据块都拥有唯一的地址标识，读写装置可以直接移动到目的数据块的所在位置进行访问。存取时间也是可变的。磁盘存储器采用直接存取的方式。
• 随机存取：存储器的每一个可寻址单元都具有自己唯一的地址和读写装置，系统可以在相同的时间内对任意一个存储单元的数据进行访问，与先前的访问序列无关。主存储器采用随机存取的方式。
• 相联存取：相联存取也是一种随机存取的形式，但是选择某一单元进行读写是取决于其内容而不是其地址。与普通的随机存取方式一样，每个单元都有自己的读写装置，读写时间也是一个常数。使用相联存取方式，可以对所有的存储单元的特定位进行比较，选择符合条件的单元进行访问。为了提高地址映射的速度，Cache采取相联存取的方式。

几个算法：

• LRU算法：最近最少使用，理论依据是局部性原理。要求较多硬件支持，成本高。
• CLOCK算法：LRU近似算法。
• 简单CLOCK算法：循环队列，每页有访问位，淘汰访问位为0的页。
• 改进型CLOCK算法：同时考虑访问位与修改位。

两个局部性：

• 时间局部性：刚被访问的内容，立即又被访问；
• 空间局部性：刚被访问的内容，临近的空间很快被访问。

程序访问具有时间局部性，即最近将要用的信息很可能是正在使用的信息；
程序访问具有空间局部性，即最近将要用的信息很可能与正在使用的信息在存储空间上是相邻的

程序访问局部性是构成层次结构的存储系统的主要依据

分页存储管理

1. 逻辑页分为页号和页内地址，页内地址就是物理偏移地址，页号通过查询页表，得知页号对应的物理块号，块号+偏移地址，得出真正的物理地址
2. 如果该页尚未调入内存，则产生缺页中断，以装入所需的页

分区存储组织，页式存储，段式存储，段页式存储

页面淘汰算法

• 最优（Optimal，OPT）算法
• 随机（RAND）算法
• 先进先出（FIFO）算法：有可能产生抖动与Belady奇异现象。

抖动

如果分配给进程的存储块数量小于进程所需要的最小值，进程的运行将很频繁地产生缺页中断，这种频率非常高的页面置换现象称为抖动。Thrashing，又叫颠簸。
产生原因：进程的内存量不足。因而分配页面太少，总是缺页。
在请求分页存储管理中，可能出现这种情况，即对刚被替换出去的页，立即又要被访问。需要将它调入，因无空闲内存又要替换另一页，而后者又是即将被访问的页，于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，严重导致系统瘫痪，这种现象称为抖动现象。

解决办法

• 使用更好的页替换算法；
• 减少运行的进程数；
• 增大内存

Belady奇异现象

指采用页面置换FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，但缺页率反而提高的异常现象，这是一个违反直觉的现象。

原因：所使用的FIFO算法不够好。

实战

段氏存储管理

某系统采用段氏存储管理方法，进程P的段表如下。逻辑地址（）不能转换为对应的物理地址，原因是（）。

解析：给定段地址( x , y ) (x,y)(x,y)，其中x为段号，y为段内地址。将( x , y ) (x,y)(x,y)转换为物理地址的方法：根据段号查段表，判断段长；如果小于段长，则物理地址=基地址-段内地址y，否则地址越界。

段地址( 0 , 810 ) (0,810)(0,810)中，0段的段长为800，段内地址810大于段长，故地址越界。
段地址( 4 , 120 ) (4,120)(4,120)中，4段的段长为100，段内地址120大于段长，故地址越界。

分页存储管理

某系统采用分页存储管理方法，下图给出进程A和B的页表结构。若物理页的大小为512字节，则进程A逻辑地址1111（十进制）的变量存放在（）号物理内存页中。假设进程A的逻辑页4与进程B的逻辑页5要共享物理页8，则进程A页表的逻辑页4和进程B页表的逻辑页5对应的物理页分别填（）、（）。

答案：4、8、8。

解析：十进制数1111转化为二进制数为：10001010111。物理页的大小为512字节，这说明页内地址为9个二进制位。进程A的逻辑地址中，右边的9位是页内地址，左边的2位是页号，即：10001010111。页号为二进制的10，即十进制的2，对应的物理页号为4。

进程A的逻辑页4与进程B的逻辑页5要共享的物理页8，那应该在进程A页表的逻辑页4对应的物理页处填8，进程B页表的逻辑页5对应的物理页处也填8。

文件管理

记录文件有顺序文件、索引顺序文件、索引文件和直接文件。

位示图法

某文件管理系统在磁盘上建立位示图（bitmap），记录磁盘的使用情况。
若磁盘上物理块的编号依次为：0、1、2、…；系统中的字长为32位，字的编号依次为：0、1、2、…，字中的一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。假设操作系统将2053号物理块分配给某文件，那么该物理块的使用情况在位示图中编号为64，系统应该将该字的位号5的位置“1"
2053号物理块对应字的编号是64号，前面的0-2047位已经占满，因此第64号字的第0位是2048，第1位是2049，第2位是2050，第3位2051，第4位2052，第5位2053。

索引文件

结构示意图

索引文件结构的扩展机制能够极大扩充现有容量，是操作系统中比较特殊的文件结构。

一般的索引文件结构由13个结点组成，其中0-9个结点为直接的物理盘块（直接索引），第10个结点是一级间接索引，第11个结点是二级间接索引，第12个结点是三级间接索引：

如果一个存储结构不使用索引，其存储量就是物理块数*单位大小。如果每个物理块的单位大小为4K，则总空间为52K。

如果引入一级间接索引，索引指向具体的物理块号，

如果一个地址占用4个字节，一个物理盘块有4KB容量，则在第10个物理块中就可以存放1024份地址，则10号物理块可存储1024份容量，即1024X4KB=4MB容量。

如果引入二级间接索引，即索引指向中间索引，中间索引再指向具体的物理块号，

如果一个地址占用4个字节，一个物理盘块有4KB容量，则在第11个物理块中就可以存放1024份地址，每份子地址可以再存储1024份二级地址，则11号物理块可存储1024*1024份容量，就是1024X1024X4KB=4GB的容量。

三级间接索引依次类推。

实战

物理块

某文件系统采用多级索引结构，若磁盘块的大小为4K字节，每个块号需占4字节，采用⼆级索引结构时的文件最大长度可占用（）个物理块，采用⼆级索引结构时的文件最大长度可占用（）个物理块。

解析：每个索引表可以存4K/4=1024个块号，所以一级索引可对应1024个物理块，⼆级索引可对应1024*1024个物理块。以此类推。

二级间接地址索引

现有一个文件系统采用索引结点管理模式，物理块大小为1KB。每个索引结点有32KB的存储空间，每个地址项占4字节，磁盘索引块和磁盘数据块大小均为1KB。其中0-4用直接地址索引，5-6用一级间接地址索引，7用二级间接地址索引，逻辑块号为5和261的物理块号在哪里？
答案：6、7的第一个字块。

解析：
逻辑块号从0开始编码，物理块号从一开始编码，所以逻辑块号5就代表第六块。
每个地址项占4字节，磁盘索引块大小均为1KB，所以一个物理块可以存放256份地址。
1KB=1024字节，1024字节/(4字节/块)=256块。
第261个逻辑块号的物理块号位置：

磁盘

另起一篇操作系统基础之磁盘。

SPOOLing

Simultaneous Peripheral Operations On-line，伪脱机技术，通过磁盘作为输入井/输出井，实现设备与CPU的并行工作。以打印机为例：用户进程将打印数据写入输出井（磁盘），SPOOLer再将数据实际输出到打印机，用户进程无需等待打印完成即可继续执行，实现独占设备到共享设备的转换。

主要用于解决CPU与I/O设备速度不匹配的问题。

作业管理

两种执行方式：

• 联机方式：直接方式，由用户自己按照作业步顺序操作；
• 脱机方式：间接方式，由用户率先编写的作业步依次执行的说明，一次交给操作系统，由系统按照说明依次处理。

作业状态及其转换

一个作业从交给计算机系统到执行结束退出系统，一般都要经历提交、后备、执行和完成四个状态：

• 提交状态：作业由输入设备进入外存储器（也称输入井）的过程称为提交状态。处于提交状态的作业，其信息正在进入系统
• 后备状态：当作业的全部信息进入外存后，系统就为该作业建立一个作业控制块（Job Control Block，JCB）。系统通过JCB感知作业的存在。JCB主要内容包括作业名、作业状态、资源要求、作业控制方式、作业类型及作业优先权等
• 执行状态：一个后备作业被作业调度程序选中而分配必要的资源并进入内存，作业调度程序同时为其建立相应的进程后，该作业就由后备状态变成执行状态
• 完成状态：当作业正常运行结束，它所占用的资源尚未全部被系统回收时的状态为完成状态

任务调度

前驱图

实战

某计算机系统中有一个CPU、一台扫描仪和一台打印机。现有三个图像处理任务，每个任务有三个程序段：扫描S i S_iSi​，图像处理C i C_iCi​和打印P i P_iPi​，i = 1 , 2 , 3 i=1,2,3i=1,2,3。下图为三个任务各程序段并发执行的前驱图，其中，（）可并行执行，（）的直接制约，（）的间接制约。

解析：前趋图是一个有向无循环图，图由结点和结点间的有向边组成，结点代表各程序段的操作，而结点间的有向边表示两程序段操作之间存在的前趋关系（->）。两程序段P i P_iPi​和P j P_jPj​的前趋关系表示成P i − > P j P_i->P_jPi​−>Pj​，其中P i P_iPi​是P j P_jPj​的前趋，P j P_jPj​是P i P_iPi​的后继，其含义是P i P_iPi​执行完毕才能由P j P_jPj​执行。

可见，S1执行完毕后，计算C1与扫描S2可并行执行；C1与S2执行完毕后，打印P1、计算C2与扫描S3可并行执行；P1、C2与S3执行完毕后，打印P2与计算C3可并行执行。

直接制约：
间接制约：

可见：
直接制约：C1和P1受到S1、C2和P2受到S2、C3和P3受到S3
间接制约：S2和S3受到S1、C2和C3受到C1、P2和P3受到P1

参考

• 操作系统-文件系统-磁盘管理