操作系统期末复习笔记（持续更新..）

一、操作系统的基本概念

1.1 操作系统概念

控制和管理整个计算机系统的硬件与软件资源。合理地组织、调度计算机的工作与资源。为用户和其他软件提供方便接口与环境的程序集合。

1.2 操作系统的特征

特征：并发，共享，虚拟，异步

并发：两个或多个事件在同一时间间隔内发生。使得系统具有处理和调度多个程序同时执行的能力。操作系统的并发是通过分时实现的。注意：并发是指在一个时间段，并行是指在同一个时段。并行是指系统具有同时执行或操作（硬件支持：多流水线或者多处理机）。对于单机处理来说，并行宏观上程序是同时在运行的，微观上程序是交替执行的，多道程序轮流占有CPU，交替执行。

重要考点：单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行。多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行。

共享：互斥共享方式。例如打印机、磁带，同一时刻只能供一个进程对资源进行访问。这种资源称作：临界资源或者独占资源。

同时访问方式：一段时间内允许多个进程对资源进行访问。典型代表：磁盘设备，重入码编写的文件。

虚拟：一个物理上的实体变为若干逻辑上的对应物，这种技术被称为虚拟技术。虚拟处理器：采用多道程序并发的方式，让每个终端用户感觉到有多个处理器。时分复用技术。

虚拟存储器：将物理存储变为虚拟存储器，逻辑上扩充存储器用量。空分复用技术。

也可以将一台IO设备虚拟为多台逻辑上的IO设备，并允许每个用户占用一台逻辑上的IO设备。

异步：多道程序走走停停，进程以不可预知的速度向前进。

1.3 操作系统的运行环境

程序运行：程序运行的过程是执行CPU一条条的机器指令的过程。

操作系统的运行机制：

CPU执行的两种性质程序，操作系统内核程序，用户自编程序。

内核：

时钟管理：操作系统为用户提供标准时间，根据时钟对进程进行管理，实现进程切换。

中断机制：初衷是为了提高多道程序运行环境中的CPU利用率。保护和回复中断线程的信息，转移控制权到相关程序。

原语：处于系统的最底层，最接近硬件。运行具有原子性，只能一气呵成。系统控制的数据结构及处理。

中断与异常：

为了进行核心态和用户态两种状态的切换，引入了中断机制。核心态可以执行用户态无法执行的特权指令。访管指令是在用户态使用，将用户态转换为核心态，所以访管指令不是特权指令。

中断是让操作系统内核夺回CPU使用权的唯一途径。

中断（外中断）：来自于CPU指令之外的事件发生。I/O中断：输入输出已经完成。时钟中断：固定时间片已到，让处理机处理。

异常（内中断）：源自于CPU执行指令内部的事件。非法操作码，除零，地址越界，算术溢出。陷入指令：用户自行设置，执行陷入后，用户态转换为核心态。异常不能被屏蔽。

系统调用：用户在程序中调用操作系统提供的一些子功能。设备功能：完成设备的请求或者释放，设备启动等功能。文件管理：完成文件的读、写、创建以及删除功能。进程控制：完成进程的创建、撤销、阻塞以及唤醒功能。进程通信：完成进程之间的消息传递和信号传递功能。内存管理：完成内存的分配、回收以及获取作业占有内存区大小及始址等功能。

用户态与内核态：处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令。

处于用户态时，说明此时正在执行的时应用程序，此时只能运行非特权指令。

cpu中有一个寄存器叫程序状态字寄存器（psw），其中有个二进制位，1表示内核态，0表示用户态。

别名：内核态=核心态=管态。用户态=目态。

内核态->用户态。执行一条特权指令——修改psw的标志位为用户态，意味着操作系统主动让出CPU使用权。

用户态->内核态。由中断引发，硬件自动完成变态过程，触发中断信号意味着操作系统强行夺回CPU使用权。

1.4 大内核与微内核

大内核：将操作系统的主要功能模块进行集中，从而用以提供高性能的系统服务。优点：各个管理模块间共享信息，能够有效利用相互间的有效特性，有巨大性能优势。缺点：层次交互关系复杂，层次接口难定义，层次间界限模糊。

微内核：计算机体系结构发展，操作系统提供服务越来越多，接口形式越来越复杂。将内核中最基本的功能保留在内核，将不需要在核心态执行的功能转移到用户态执行，降低内核设计的复杂性。优点：有效分离内核与服务、服务与服务、使得它们间的接口更清晰，维护代价大大降低。各部分可以独立的优化和演进。缺点：性能问题，需要频繁的在用户态和内核态之间切换。

二、进程

2.1 进程的概念和特征

进程的概念：

进程是程序一次执行过程。进程是一次程序及其数据在处理机上顺序执行时发生的活动。进程时具有独立功能的程序在一个数据集合上运行的过程，是资源分配和调度的独立单位。是为了更好描述和控制程序的并发执行，实现操作系统的并发性和共享性。

进程控制块PCB：为了更好的描述进程的基本情况和运行状态，进而控制和管理进程。PCB是进程存在的唯一标志。

进程的特征：

动态性、并发性、独立性、异步性、结构性。

动态性：进程具有生命周期，有创建、活动、暂停、终止等过程。

并发性：多个进程同时存在于内存中，使得程序与程序之间可以并发执行。

独立性：进程能独立获得资源和接受调度。

异步性：进程相互制约，以不可预知的速度向前推进。操作系统中配置有相应的进程同步机制。

结构性：每个进程都配置一个PCB用于描述。

2.2 进程的状态与转换

状态：创建态、就绪态、运行态、阻塞态、结束态。

创建态：进程正在被创建，尚未进入就绪态。

就绪态：进程已处于准备运行状态。

运行态：进程在处理机上运行。

阻塞态：又称等待态，进程正在等待某个时间而暂停运行。

结束态：进程正在从系统中消失（正常结束或异常终止）

相互转换：

就绪态->运行态：处于就绪态的进程获得处理机进入运行态。

运行态->就绪态：处于运行态的进程时间片用完后，让出处理机进入就绪态。

运行态->阻塞态：进程请求除处理机外的其他资源，此时运行态进入阻塞态。

阻塞态->就绪态：进程获得所等待的资源，如IO资源，或中断结束。

2.3 进程控制

进程的创建：

分配进程标识号，申请PCB（PCB有限）。为进程分配资源，为程序和数据以及用户栈分配必要的内存空间。初始化PCB，包括初始化标志信息、初始化处理机状态信息、初始化处理机控制信息、设置进程的优先级。若进程就绪队列可以接纳新进程，进程就进入就绪态。

进程的终止：

结束分类：正常结束：进程的任务已经完成并且准备退出运行。异常结束：进程正在运行，出现了某些异常事件，导致程序无法继续运行。外界干预：进程应外界请求终止运行。

结束过程：根据被终止进程的标识符，检索PCB，读取进程状态。若进程处于运行态，终止运行，剥夺处理机。终止进程之下的子进程。该进程拥有的全部资源还给父进程或者操作系统。将PCB从队列中删除。

进程的阻塞和唤醒：

阻塞原语执行过程：找到要被阻塞进程标识号对应的PCB。若该进程处于运行态，保护其现场，将其状态转换为阻塞态，停止运行。将PCB插入相应时间的等待队列。

唤醒原语的执行过程：找到等待队列中进程相应的PCB。将其从等待队列中移除，置其状态为就绪态。将PCB插入就绪队列，等待调度程序调度。

进程切换：

进程切换是在内核态下完成的。

过程：保存处理机上下文，包括程序计数器和其它寄存器。更新PCB信息。把进程的PCB移入相应的队列，如就绪、阻塞等队列。选择另一个进程执行，更新其PCB。更新内存管理的数据结构。恢复处理机上下文。

进程的组织：

进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位，由以下三部分组成：

进程控制块：

进程描述信息：进程标识符：标志进程。用户标识符：标识进程归属的用户，主要为了共享和保护服务。

进程控制和管理信息：进程当前状态：描述进程状态信息。进程优先级：描述进程抢占处理机的优先级。代码运行入口地址。程序外存地址。进入内存时间。处理机占用时间。信号量使用。

资源分配清单：

用以说明有关内存地址空间或者虚拟地址空间状况，所打开的文件的列表和所使用的输入/输出设备信息。代码段指针、数据段指针、堆栈段指针、文件描述符、键盘、鼠标。

处理机相关信息：

处理机中各寄存器的值。通用寄存器，地址寄存器，控制寄存器，标志寄存器值，状态字。

程序段：能被进程调度程序调度到CPU执行的程序代码段。

数据段：进程对应的程序加工处理的原始数据或者程序执行时产生的中间或最终结果。

进程的组织方式：

链接方式：按照进程状态将PCB分为多个队列，操作系统由指向各个队列的指针。

索引方式：根据进程状态不同，建立几张索引表。操作系统持有指向各个索引表的指针。

2.4 进程的通信

共享存储：通信进程之间存在一块可以被直接访问的共享空间。

低级方式：基于数据结构共享。

高级方式：基于存储区共享。

消息传递：进程间的数据交换是已格式化的消息为单位的，进程通过系统提供的发送消息和接收消息的两个原语进行数据交换。

直接通信方式：发送进程直接发消息给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。

间接通信方式：发送进程把消息发给某个中间实体，接收进程从中间实体获得消息。

通道通信：发送进程以字符流形式将大量数据送入写管道，接收进程从管道中接收数据。当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。

通道通信是半双工通信，不可以同时读和写。要求互斥和同步，确定对方存在。

三、线程

线程的基本概念：

减少程序在并发执行时付出的时空开销，提高操作系统的并发性能。

引入线程后，进程只作为系统资源的分配单元，线程作为处理机的分配单元。

线程与进程的比较：

调度：进程是独立调度的基本单位，线程是资源的基本单位。不同线程切换回引起进程切换。

拥有资源：进程是资源分配的基本单位。

并发性：引入线程后，进程可以并发执行，多个线程间也可以并发执行，提高系统吞吐量。

系统开销：同一进程的线程切换要比进程切换开销小。

地址空间和其它资源：进程的地址空间相互独立，同一进程的各线程之间共享进程资源，某进程的线程对其它进程不可见。

通信方面：进程间通信需要进程同步和互斥手段的辅助，保证数据的一致性。线程间可以直接读/写进程程序段来通信。

线程属性：不拥有系统资源，拥有唯一标识符和线程控制块。不同线程可以执行相同的程序，同一服务程序被不同用户调用时，操作系统为其创建不同线程。同一进程的线程共享该进程全部资源。线程时处理机的独立调度单位。线程也有生命周期，如阻塞、就绪、、运行等状态。多CPU计算机中，各个线程可占用不同的CPU。每个线程都有一个线程ID、线程控制块（TCB）。切换同进程中的线程开销小，切换进程开销大。由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预。

（持续更新中...）

——————————————————————————————————————

一、文件系统专题

题1：【2012统考真题】某文件系统空间的最大容量为 4TB （ 1TB=2^40 B ），以磁盘块为基本分配单位。磁盘块大小为 1KB 。文件控制块（ FCB ）包含一个 512B 的索引表区。请回答下列问题。

1 ）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？

2 ）假设索引表区采用如下结构：第 0 ～ 7 字节采用 < 起始块号，块数 > 格式表示文件创建时预分配的连续存储空间，其中起始块号占 6B ，块数占 2B ；剩余 504 字节采用直接索引结构，一个索引项占 6B ，则可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。

解答：（1）总容量是2^42B，磁盘块大小是2^10B，所以一共有2^32个磁盘块。每个磁盘块都可以用一个32位的二进制数表示（比如0000 0000 0000 0000 0000 0000 0000 0010 代表第2个磁盘块）。问：块号占多少字节？因为每个字节8位，所以是32/8=4B，所以占4字节。（可以用4个字节来代表一个磁盘块）

现在有一个512B的索引表区，用512B/4B=128，求得有128个索引表项，（因为4个字节代表一个磁盘块，4字节等于1个索引表项）每个索引表项代表一个磁盘块，每个磁盘块大小1KB，所以单个文件最大长度位128x1KB=128KB。

（2）6B=48位。2B=16位，16位表示的是连续的内存块数=2^16，又因为每个内存块是1KB=2^10B，所以预分配的连续内存空间是2^26B。

因为1个索引项占6B，所以504字节=84个索引项。由第1问推理可知，1个索引项=1个磁盘块，84x1KB=84KB。

由题目第2问开头可知，索引表表示的空间大小可以=预分配的存储空间+直接索引的存储空间。所以可支持的单个文件的最大长度是2^26B+84KB。

在第2问的框架下，索引表结构是不变，即前8字节表示预分配的空间，所以只能在这里作文章。因为根据第1问可知，该系统容量为2^32个磁盘块的大小。所以我们可以让表示连续分配块数占32位，即4字节，这样最大能分配大小为4TB的连续块作为预分配空间。起始块号也占4字节，刚好能寻址完全2^32块磁盘块。很完美的分配方法。

题2：【2016 统考真题】某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。
1）假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中dir, dir1是目录，file1, file2是用户文件。请给出所有目录文件的内容。
2）若FAT的每个表项仅存放簇号，占2B，则FAT的最大长度为多少字节?该文件系统支持的文件长度最大是多少?
3）系统通过目录文件和FAT实现对文件的按名存取，说明file1的106，108两个簇号分别存放在FAT的哪个表项中

4）假设仅FAT和dir目录文件已读入内存，若需将文件dir / dir1 / file1的第5000个字节读入内存，则要访问哪几个簇?

解答：（1）可以这么看，题目中只有2个目录，分别为dir和dir1。dir的目录项是dir1（不用去考虑下一级），dir1的目录项是file1和file2。由定义：目录文件的每个目录项包括文件名和文件的第一个簇号，所以dir的目录名为：dir1 48。dir1的目录名为：file1 100 file2 200。

（2）2B=16位，任何1个簇能用16位二进制数组成的簇号表示，所以一共能表示2^16个簇，又因为1个表项对应1个簇，所以一共有2^16个表项，因为一个表项大小2B，所以FAT的最大长度=表项的数量x表项大小=2^16x2为2^17B=128KB。

最大文件长度=簇的数量x每个簇的大小。已知有2^16个簇，题目中知道每个簇的大小为4KB=2^12B。所以所能表示的文件最大大小为：2^28B=256MB。

（3）由第1问可知，dri1目录文件的第1个目录项为file1 100，这里的100是file1的第1个簇号，它需要通过指针与后面2个簇号106和108连接。file1的目录项首先会指向第1个簇号对应在FAT中的表项（如下图），也就是第100表项，因为在FAT表中每个表项的构成结构是：表项+下一簇号，所以100簇号对应的下一个簇号是106，通过106簇号可以找到表项106，108簇号存储在106表项中。由此可以找到file1文件中的所有簇号。所以答案是：file1的簇号106存放在FAT的100号表项中，簇号108存放在FAT的106号表项中。

（4）由题目知道，dir目录已经读入内存，接下来需要将dir1读入内存，所以需要访问簇号为48的簇。下面需要把file1读入内存，因为每个簇的大小为4KB=4096B，系统知道file1的目录项最大只能访问到4096个字节，所以它会到FAT的第100表项去找，所以会访问簇号为106的簇（这个簇是第2个簇，对应的内存是第4097~8192个字节，第5000个字节在这个范围内）。