1. 操作系统基础知识

操作系统定义：能有效地组织和管理系统中的各种软/硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。

操作系统的作用：通过资源管理提高计算机系统的效率；改善人机界面向用户提供友好的工作环境

操作系统的特征：并发性、共享性、虚拟性、不确定性

操作系统的功能：进程管理、存储管理、文件管理、设备管理、作业管理

操作系统的分类：

• 批处理操作系统：单道批处理和多道批处理（主机与外设可并行)。
• 分时操作系统：一个计算机系统与多个终端设备连接。将CPU的工作时间划分为许多很短的时间片，轮流为各个终端的用户服务。
• 实时操作系统：实时是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。实时系统对交互能力要求不高，但要求可靠性有保障。
• 网络操作系统：是使联网计算机能方便而有效地共享网络资源，为网络用户提供各种服务的软件和有关协议的集合。三种模式：集中模式、客户端/服务器模式、对等模式。
• 分布式操作系统：分布式计算机系统是由多个分散的计算机经连接而成的计算机系统，系统中的计算机无主、次之分，任意两台计算机可以通过通信交换信息。它保持网络系统的全部功能，并具有透明性、可靠性和高性能等特性
• 微型计算机操作系统：简称微机操作系统，常用的有Nindows、Mac OS、 Linux.

嵌入式操作系统主要特点：

• 微型化。从性能和成本角度考虑，希望占用的资源和系统代码量少，如内存少、字长短、运行速度有限、能源少（用微小型电池）。
• 可定制。从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置，以满足不同应用需要。
• 实时性。嵌入式操作系统主要应用于过程控制、数据采集、传输通信、多媒体信息及关键要害领域需要迅速响应的场合，所以对实时性要求较高。
• 可靠性。系统构件、模块和体系结构必须达到应有的可靠性，对关键要害应用还要提供容错和防故障措施。
• 易移植性。为了提高系统的易移植性，通常采用硬件抽象层和板级支撑包的底层设计技术。

2. 进程的组成和状态

进程的组成：进程控制块PCB(唯一标志)、程序(描述进程要什么)、数据(存放进程执行时所需数据)

进程基础的状态是下图中的三态图。需要熟练掌握左图中的进程三态之间的转换。

3. 前趋图

用来表示那些任务可以并行执行，那些任务直接有顺序关系，如下图。

由图可知，ABC可以并行执行，但是必须ABC都执行完后，才能执行D。

这就确定了两点：任务间的并行、任务间的先后顺序。

4. 进程资源图

用来表示进程和资源之间的分配和请求关系，如下图。

P代表进程，R代表资源，R方框中有几个圆球就表示有几个这种资源，在图中R1指向P1,表示R1已经有一个资源分配给了P1，P1指向R2表示P1还需要请求一个R2资源才可以执行

• 阻塞节点：某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程已经被阻塞了无法继续。如上图中P2。
• 非阻塞节点：某进程所请求的资源还有剩余，可以分配给该进程继续执行。如上图P1、P3
• 当所有进程都是阻塞节点时，陷入死锁状态

死锁产生的四个必要条件

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

解决死锁的措施

• 死锁预防：采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一。
• 死锁避免：一般采用银行家算法来避免。银行家算法就是提前计算出一条不会死锁的资源分配方法才分配资源，否则不分配资源。
• 死锁检测：允许死锁产生，但系统定时运行一个检测死锁的程序，若监测到系统中发生死锁，则设法加以解除
• 死锁解除：死锁发生后的解除办法，如强制剥夺资源，撤销进程等
• 死锁资源计算：系统内有n个进程，每个进程都需要R个资源。其发生死锁的最大资源数为n*(R-1)。其不发生死锁的最小资源数为n*(R-1)+1

5. 进程同步与互斥

同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况下停下等待，不存在资源是否单独共享的问题；如自行车和汽车

• 同步信号量：对共享资源的访问控制，初值一般是共享资源的数量

互斥：某资源(即临界资源)在同一时间内只能由一个任务单独使用，使用时需要加锁(互斥信号量)，使用完后解锁才能被其他任务使用；如打印机

• 临界资源：进程间需要以互斥的方式访问的资源
• 临界区：进程中对临界资源实施操作的那段程序。本质是一段程序代码
• 互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1

6. 信号量操作

P操作：申请资源，S=S-1，若S≥0则执行P操作的进程继续执行；若S<0则置该进程为阻塞状态(因为无资源可用), 并将其插入阻塞队列

V操作：释放资源，S=S+1，若S>0则执行V操作的进程继续执行；若S≤0则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续

⚠️ 进程和信号量要分清 前驱图中，两个进程之间的箭头线条才是释放的信号量，且信号量的计数S123与进程的计数P123毫无关系

7. 存储方式

7.1 分页存储

将进程空间分为一个个页，假设每个页大小为nK，同样的将系统的物理空间也分为一个个nK大小的物理块(页帧号)，这样每次将需要运行的逻辑页装入物理块中，运行完再装入其他需要运行的页，就可以分批次运行完进程，而无需将整块逻辑空间全部装入物理内存中

优点

• 利用率高
• 碎片小(只在最后一个页中有)
• 分配及管理简单

缺点

• 增加了系统开销
• 可能产生抖动现象

某计算机系统页面大小为4K，若进程的页面变换表如下所示，逻辑地址为十六进制1D16H。该地址经过变换后，其物理地址应为？
		页号 | 物理块号
			0    1
			1    3
			2    4
			3    6
解： 
	页地址是页号和页内地址组成的，页号在高位，页内地址在低位
	无论是物理地址还是逻辑地址，页内地址是不变的
	页内地址表示页有多大，题目给出页面大小为4K
		4K = 2^12B
	所以页内地址占12位，12位二进制刚好是3位十六进制数，所以页内地址对应的逻辑地址为D16
	那么页号便为1，页号1对应的物理块号为3
	此时就可以得到物理地址为3D16H

7.2 分段存储

将进程空间分位一个个段，每段有段号和段内地址，与页式存储不同的是，每段物理大小不同，分段是根据逻辑整体分段的(这会造成分段大小不一样)。

地址表示：段号，段内地址

段内偏移不能超过该段号对应的段长，否则越界错误

此地址对应的真正内存地址应该是：段号对应的基地址+段内偏移

优点

• 程序逻辑完整
• 修改互不影响

缺点

• 内存利用率低
• 内存碎片浪费大

解析:主要看段长和偏移量的对比结果。在（段号，偏移量）中，偏移量不能超过段长。

7.3 段页式存储

对进程空间先分段后分页

优点

• 空间浪费小
• 存储共享容易
• 能动态连接

缺点

• 由于管理软件的增加，复杂性和开销也增加，执行速度下降

假设段页式存储管理系统中的地址结构如下图所示

从图中可知段号占了10位，页号占了10位，页内地址占了12位

段： 最多有2^10=1024个段

页：每段最大允许2^10=1024个页

页的大小： 2^12=4x2^10=4k 页的大小为4k

8. 文件结构

如图所示，系统中有13个索引节点，0-9为直接索引，即每个索引节点存放的是内容，假设每个物理盘大小为4KB,共可存4KB *10=40KB数据；

10号索引节点为一级间接索引节点，大小为4KB，存放的并非直接数据，而是链接到直接物理盘块的地址，假设每个地址占4B,则共有1024个地址，对应1024个物理盘，可存 1024 *4KB=4096KB数据

二级索引节点类似，直接盘存放一级地址，一级地址再存放物理盘快地址，而后链接到存放数据的物理盘块，容量又扩大了一个数量级，为1024 *1024 *4KB数据。

设文件索引节点中有8个地址项，每个地址项大小为4字节，其中5个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，磁盘索引块和磁盘数据块大小均为1KB,若要访问文件的逻辑块号分别为5和518，则系统应分别采用（？），而且可表示的单个文件最大长度是（？）KB。

解析：依题意，有5个地址项为直接地址索引，所以直接地址索引涉及到的逻辑块号为：0-4.2个地址项为一级间接索引，每个一级间接索引结点对应的逻辑块个数为：1KB/4B=256个。所以一级间接索引涉及到的逻辑块号为：5-516。二级间接索引所对应的逻辑块号即为：517以上。可表示的单个文件长度，首先计算直接地址索引，就是5个数据块，为5KB,而后一级间接地址索引，可表示256个数据块，即256KB,二级间接地址索引可存储1KB/4B=256个一级间接地址索引，每个一级间接地址索引又可存储256KB,因此是256*256KB,全部加起来共5+256*2+256*256=66053.。

9. 设备管理

设备分类如下

• 按数据组织分类：块设备，字符设备
• 资源分配角度分类：独占设备，共享设备，虚拟设备
• 数据传输速率分类：低速设备，中速设备，高速设备

I/O软件(输入输出软件)层次结构

10. 文件目录

相对路径：是从当前路径开始的路径。

绝对路径：是从根目录开始的路径

全文件名=绝对路径+文件名。要注意，绝对路径和相对路径是不加最后的文件名的，只是单纯的路径序列。

操作系统通过文件目录和目录项来组织和管理外存中的信息。

11. 文件位示图

位示图是在外存上建立一张位示图(Bitmap),记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。

某文件管理系统采用位示图(bitmap)记录磁盘的使用情况。如果系统的字长为32位，磁盘物理块的大小为4MB,物理块依次编号为：0、1、2、..,位示图字依次编号为：0、1、2、.，那么16385号物理块的使用情况在位示图中的第（？）个字中描述：如果磁盘的容量为1000GB,那么位示图需要（？）个字来表示。

解析：在位示图中，一个物理块占1个字中的1位，第16385位（从0编号)的话就是16384， 16384/32=512，可知，其在512个字中描述；磁盘容量 1000GB,共1000GB/4MB=250*1024个物理块，需要250Kb表示，即250*1024bit/32bit=8000个字。