操作系统考纲整理

一、操作系统基础知识

1) 操作系统概论

定义： 是指控制和管理整个计算机系统的硬软件资源，合理组织，调度工作和资源分配，并于用户和其他软件提供接口和环境的程序。是计算机系统中最基础的软件
作用和特征： 4大管理功能：处理机，设备，文件，存储器管理；并发，共享，异步，虚拟
分类，发展历程： 手工操作阶段，批处理阶段(单道-多道)，分时操作阶段，实时操作阶段。

2) 操作系统结构

典型操作系统：Linux，Window，IOS
体系结构：

中断和陷入： 中断分为外部中断和内部中断，外部中断即为中断，是CPU外部的事件所导致的(I/O结束中断)。内部中断也称为异常，是由CPU内部的事件所引发的(如整除0,下标越界)，陷入属于内部中断，是用户主动要求进入的。
用户态和核心态：用户态是一般应用程序所在的位置，而系统程序，内核程序运行在核心态。
特权指令和非特权指令：在用户态中，只能执行非特权指令，可以执行访管指令；在内核态中，能执行所有指令(包括特权指令)
操作系统内核功能：时钟管理，中断机制，原语，系统控制的数据结构

3) 操作系统启动和引导

执行流程：1.激活CPU，由CPU去主存地址取指令 2.硬件自检3.加载操作系统硬盘4.读取主引导记录(MBR) 5.扫描活动分区表，读取分区引导记录6.从根目录下找到完整的操作系统程序并执行。
操作系统设计的主要概念：

二、 进程管理

1) 进程/线程基本概念

进程的定义和特征：是一个独立功能的程序在一个数据集合上运行的过程，是系统资源分配和调度的基本单位。它主要由三个部分组成，分为PCB(进程控制块),程序段，数据段。它的两个主要特征：并发和共享。
进程的状态和转换：运行态，就绪态，阻塞态，阻塞态无法直接到运行态。

进程控制块和进程创建，撤销(终止)，阻塞，唤醒：进程控制块PCB。
创建时：1.分配标识号2.分配所需资源3.分配初始化PCB 4.插入就绪队列等待上处理机运行
终止时：1.根据标识符找到对应的PCB 2.读取状态，若处于运行态，结束运行，将资源分配给其他进程，别的状态直接撤销其PCB 3.若该进程有子孙进程，将其子孙进程以同样方式终止 4.将该进程所有资源全都交换回去 5.把相应队列中的PCB删除

进程与程序区别与联系
进程是动态的，是程序的一次执行过程，程序是静态的，是一组有序的指令集合。
进程有一定的生命周期，它也有着三种状态：运行，就绪，阻塞。是短暂会消亡的。程序是一组代码的集合，是永久长期存在的。
一个进程中可有多个程序，一个程序也可构成多个进程。程序不可以创建进程，但进程可以创建程序
进程与程序组成不同，进程是由PCB，数据段，程序段组成的。所以进程其实包括了程序。

线程机制以及线程的实现方式
线程机制： 引入线程是因为更好地使多道程序并发运行，传统上来说，进程为独立调度分配资源的基本单位，而在引入线程的操作系统中，线程是独立调度的基本单位。因为进程的切换会影响线程的切换，线程切换一般不会影响进程的切换。(同一进程内线程的切换不会影响该进程,不同进程中线程的切换会引起进程切换)
一个进程中包含了多个线程，不仅进程可以并发运行，同一进程中的线程，不同进程中的线程都可以并发运行，从而提高了系统的资源利用率，进而提高了多道程序并发运行的效率。
每个进程都有其独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。而线程拥有共享的地址空间和资源，它们可以相互访问。

注：同一进程内的线程共享该进程的所有资源

线程的实现方式
用户级线程

用户级线程是根据程序员编写的线程库得以实现的，实际上，对于OS来说，线程根本不可见。因此用户级线程的控制也是由线程库来实现的。
如下其实while循环就是一个简易的线程库，里面的if语句分别为一个一个的线程。

对于用户级线程来说，线程的切换不需要实现从用户态到核心态的转换。因此效率较高。
但是，在用户级线程中，若有一个线程阻塞，其他进程无法运行，无法并发运行的线程，那还能叫线程嘛？

内核级线程
而内核级线程就是为了解决上面问题而引入的。

如上图所示，很显然，内核级线程是操作系统可见的，因此它们的操作也是由操作系统控制。
而当一个进程阻塞时，操作系统可以调度其他进程上处理机运行，从而实现了线程并发运行。
然而，它的缺点也比较明显，那就是它们之间的线程切换需要从用户态转到核心态运行，而切换有不小的开销。

多线程模型

• 一对一模型
• 多对一模型
• 多对多模型

2) 进程/作业调度

进程调度的时机和方式
时机：主动放弃，被动放弃
方式：剥夺式调度(能由操作系统剥夺当前进程的CPU使用权)和非剥夺式调度方式(只能由当前进程主动放弃CPU)

调度算法的设计准则和衡量指标：
调度算法的设计准则，需要考虑该算法的资源的利用率，实现该算法所调用的资源大小。一个好的调度算法，应该是资源利用率极高，占用系统资源极少，同时又能够避免进程的饥饿现象。
调度算法的衡量指标分别为，CPU利用率，系统吞吐量，周转时间(完成时间-提交时间)，平均周转时间(每个进程周转时间相加)/进程数，带权周转时间，平均带权周转时间。等待时间，响应时间。

设备利用率计算

系统吞吐量

周转时间

典型调度算法：

• FCFS(先来先服务)调度
  顾名思义，先到的作业先被调度，后来的作业排在就绪队列中等待上处理机运行。它有利于CPU繁忙型作业(长作业)，不利于I/O繁忙型作业(短作业)。FCFS是一种相对公平的调度算法。
• 优先级调度
  每一个作业都会被赋予一个优先级(优先级的高低会给出),优先级高的先被调度。
• SJF(短作业优先)调度
  每个到来的作业会按照各个的运行时间排序，运行时间最短的先被调度。它有利于I/O繁忙型作业(短作业)，不利于CPU繁忙型作业(长作业)。有可能导致饥饿。

注意：SJF的原则只有在进程都到达之后才开始，如一开始没有别的进程到达，运行时间再长的进程也要先运行。

• 时间片轮转调度
  类比CPU时间片轮转，为每个不同的作业分配固定大小的时间片，在此算法中，系统会将所有进程都按FCFS策略排成一个就绪队列，一旦时间片用完立刻下处理机换另一个作业运行，而该下处理机的作业重新再插入就绪队列的队尾。因此，时间片轮转调度算法必须设置为抢占式。

• 高响应比优先调度
  响应比的计算=(等待+运行)/运行时间。将响应比最高的作业优先调度运行。

• 多级反馈队列调度
  每个队列实施不同的调度算法。
  多处理机调度：

实时调度：

3) 进程同步

临界资源基本概念和使用原则：
临界资源是指，一次只允许一个进程所访问的共享资源。如打印机就是一种临界资源，当进程A在使用打印机打印时，进程B必须等待而不能使用打印机，否则打印内容将会出现问题。

同步互斥基本概念：
同步互斥是各个进程相互制约的两个状态。
同步是指：进程A的执行必须依靠进程B的结果，因此进程B必须要在进程A前之前完毕。一句话，同步是进程之间工作顺序的反应。
互斥是指：当进程A对临界资源C的访问时，进程B不能对C访问。这就是所谓互斥访问，也就是不能同时访问一个临界资源。
同步机制：16字准则：空闲让进，忙则等待，有限等待，让权等待。

实现同步互斥的软硬件方法：

• 软件实现方法

1. 单标志位
2. 双标志位

• 硬件实现方法

1. 硬件指令

互斥锁
用于解决临界资源互斥访问问题。当一个进程访问临界资源时获得锁，在访问完成后释放锁。

信号量机制
信号量是用于解决临界资源的互斥同步问题的经典方法。它主要有两个不可被中断的原语操作P(wait(s))V(signal(s))组成。
原语指的是完成某些功能不可被分割中断执行的序列。

• 整型信号量
  初值为资源数目的信号量

wait(s){
	while(s<=0);
	s=s-1;
}

signal(s){
	s=s+1;
}

• 记录型信号量(最常用)

typedef struct{
	int value;
	struct process *L;//阻塞队列
}semaphore;

wait(semaphore s){
	s.value--;
	if(s.value<0)
	//add this process to s.L
	block(s.L);
}

signal(semaphore s){
	s.value++;
	if(s.value<=0)
	//remove a process P from s.L
	wakeup(P);
}

管程机制
管程的出现是用于解决信号量同步机制所出现的问题。它将实现进程互斥或同步访问的代码封装到一起。
管程相似于面向对象语言中的类这一概念，它主要由四个部分组成：

1. 管程名(类名)
2. 管程中的各种过程(类中方法)
3. 在其中的共享数据结构说明
4. 对于不同属性数据赋值，初始化(类中对于属性初始化的操作)

准确来说，管程是一种私有的类，它仅能由不同进程通过调用其接口来访问其中的各种过程，且每次只允许一个进程进入管程。

进程通信

通信的分类：

1. 共享存储
   共享存储分为两种：基于数据结构的低级方式共享，基于存储区的高级方式共享。前者因为数据结构的限制，所以限制多多，属于低级。存储区较为灵活，因此属于高级。

2. 消息传递
   分为直接通信和间接通信。
   消息传递就好比寄信。直接就是寄信人直接把信给到收信人手上。而间接就是寄信人通过把信给到邮箱，收信人通过邮箱接受信件。

3. 管道通信
   管道同共享存储区有点类似。但是管道限制比较多，它是一种仅支持半双工通信的通信机制。可以类比生活中的水管，水只能从左往右留或者相反。只有两个及以上的水管能实现全双工通信。
   它允许两个进程以读者-写者方式通信。只要管道非空，读进程就可以读出数据。只要管道不满，写进程就可以往里写入数据。

RPC协议
RPC协议的主要目的是做到不同服务间调用方法像同一服务间调用本地方法一样

4) 死锁

死锁基本概念
不同进程争相竞争资源造成一种僵局(dilemma)，同时阻塞，如无外力作用这些进程都无法向前推进的一种情况。

死锁产生的必要条件

1. 互斥访问条件
2. 不剥夺条件
3. 循环等待
4. 请求和保持条件(吃着碗里看着锅里)

死锁预防

1. 破坏互斥条件
   有些资源只能被互斥使用，因此这方法一般不太可行。
2. 破坏不剥夺条件
   如果要实现破坏不剥夺条件，则会产生以下后果：已经要执行完的进程被剥夺，释放了所有资源供另一个进程使用。下次再执行该进程时，资源需要重新申请，工作需要重新完成。代价比较大，且策略实现复杂。
3. 破坏循环等待条件
   采用顺序资源分配法，为每个资源进程编号，规定每个进程必须按照编号顺序来申请资源。但这毫无疑问的为用户编程增加了负担。
4. 破坏请求和保持条件
   实现此的方法是一次性给于进程所需的所有资源，只要资源不满足就不运行。只要满足就一直占用资源直到运行完毕。这种方法无疑是很浪费系统资源的。

死锁避免
最为常见的方法是银行家算法。
死锁检测和解除
死锁检测：
资源分配图是一种常见的死锁检测方法。
其中一个框表示一种资源，一个圆圈表示一个进程。
其中由资源指向进程的边为分配边，由进程指向资源的边为请求边

死锁定理：
类似于数据结构图中的拓扑排序，通过对资源分配图进行化简，如果该图不可简化，则存在死锁，否则不然。
依次消除与不阻塞进程相连的边，直到无边可消除。
死锁解除：

1. 撤销进程法
2. 资源剥夺法
3. 进程回退法

三、 内存管理

1) 内存管理基本概念

包括对内存的分配，回收，地址转换，和内存保护。

内存分配与回收
用完了一片内存空间，当然需要回收，使用一片内存空间，当然需要合理分配。

内存地址转换
由操作系统负责实现逻辑地址到物理地址的转换。
常见的三种方式：

• 绝对装入
  编译器来进行地址转换
• 可重定位装入
  在装入时进程地址转换
• 动态装入
  在进程投入运行时才进行地址转换

内存保护
内存保护的目的是为了保证内存中的各种进程能够在各自的存储空间独立的运行，不受其他进程的干扰。
常见的保护方法有两种：

1. 分别设置一个上限寄存器和下限寄存器。其实就是数组中的最小下标和最大下标，为了避免越界而存在。
2. 设置一个重定位地址寄存器和一个界地址寄存器寄存器进行计算判断。

2) 连续分区管理方案

外部碎片和内部碎片
内部碎片：是已经分配出去的内存空间有所空闲而导致的碎片
外部碎片：是内存空间中(暂未分配)但是分配不出去的碎片

单一连续分配
内存在此方式下分为系统区和用户区，只支持单用户单进程，这种方式没有外部碎片，有内部碎片。
固定分区分配
固定分区在划分分区时有两种不同的方法，支持多用户多进程，分为分区大小固定和分区大小可变，大小固定不太灵活，而大小可变则较为适中。
动态分区分配
动态分区比固定分区更加灵活，它允许在分配过程中，根据进程的需要动态的为其分配内存。因此，系统中的分区大小和数目都是可变的。

动态分配中，有一个重要的分配策略问题，分为首次适应，临近适应，最佳适应，最坏适应。都是顾名思义，非常好理解。

紧凑技术
是为了解决如下图所示的外部碎片问题的：

所谓紧凑，其实就是把空闲的内存碎片拼凑到一起，组合成一个大小足以存放其他数据的技术。

3) 离散(非连续)分区管理方案

地址转换过程

1. 计算出逻辑地址对应的【页号，页内偏移量】。页号=逻辑地址/页面大小，页内偏移量=逻辑地址%页面大小
2. 查页表找到在内存中的存放位置
3. 物理地址=页面始址+页内偏移量

分页管理方案
所谓分页管理，就是从逻辑上来说将程序划分成一个一个大小相等的页面，每一个页面都对应了一个页表，页表中存放了许多页表项，页表项则是由页号和块号组成的。其中页号是不占用内存空间的。物理上的分页是必须连续的。

分段管理方案
所谓分段管理，就是从逻辑上来说将程序划分成一个一个大小不相等的段，每一个段都对应着一个段表，段表中又有着由段号，段长，基址的段表项。物理上的分段是可以不相邻的。

段页式管理方案
是以上两种管理方案结合的产物，先分大小不固定的段，再分固定大小的页。
以段页式方案访问一个逻辑地址，共需要三次访存：

1. 访问段表
2. 访问页表
3. 访问页表中的目标单元

分页，分段管理方案的区别
分页和分段管理的区别：

• 分页是按固定大小分配的每一页，而分段是大小不相等的一段段组成的
• 分页的地址空间是一维的，分段的地址空间是二维的。
• 分页对用户不可见，分段对用户可见。
• 分段比分页更容易实现数据的扩展和维护。

请求分页和分段，段页式管理方案
请求分页，分段，段页式方案与基本分页，分段，段页式方案的不同之处在于：
当要访问的信息不在内存时，操作系统需要提供请求分页，分段等的策略，用来将缺失的信息从外存调入。
当不要访问的信息在内存时，操作系统需要提供页面置换等策略，用来将不需要的信息从内存换出置外存。(这也就引入了各大页面置换算法)。

当要有需要访问的信息到来时，具体的请求分页流程如下：

1. 检查内存中是否有该信息
2. 若无，产生缺页中断，将页面调入内存，当内存已满时，则需要将不需要的信息调出内存。
3. 若有，正常执行

4) 内存管理方案性能设计

缺页率
当要访问的页面不存在内存中，就会产生一次缺页。
缺页率=(页面置换次数+分配给该进程的物理块数)/要访问的页面总数

抖动
当刚被换入的页面就要被换出，当刚被换出的页面就要被换入这种现象过于频繁时，即为抖动。产生抖动的根本原因是分配给进程的物理块太少，工作集是为了解决此问题而产生的。

工作集理论
工作集是保证分配给进程的进程块数能够满足其所需。

页面置换算法
进程运行时，若所访问的页面不在内存需要调入，但内存已无空间时，就需要从内存中调出一页程序，送入磁盘对换区。
而选择调出页面的算法称为页面置换算法。一个好的算法应该尽量减少换入换出的次数。常见的置换算法：

• 最佳置换算法(OPT)
  它的思想是提前预知后面永不使用的页面或是最长时间内不会被使用的页面，很显然不可能实现，但具有评价其他算法的价值。
  

• 先进先出(FIFO)
  它的思想是换出最先进入的页面，思想简单，但存在Belady异常，这是一种分配的物理块数增多但缺页次数也增加的异常。(这就好比你给了它更多资源但他反而效率更低了)。
  

• 最近最久未使用(LRU)
  它的思想是换出最近最久未被使用的页面。每当访问过一次页面，它就不是未被使用的了。但它的算法空间开销较大。
  

• 时钟(CLOCK)
  它的思想是每次都在访问一个页面后对其访问位置1，直到全为1后，全部置零，从头开始重复操作。

注意：时钟置换算法是在每次访问一个页面后就对访问位置置1，也就是说，就算访问完后没有产生缺页，也要将其访问位置1。

• 改进后的时钟(CLOCK)
  它在时钟的基础上实现了改进，增加了一个修改位，思想是针对优先级来适时淘汰页面。
  
  

四、 文件系统

1) 文件系统基本概念

目录文件和文件目录
目录文件是一种特殊的文件。
而文件目录其实就是我们打开文件管理器的界面。里面可能存有文件夹，也可能存有其他类型各样的文件。

文件存储介质
常见的有磁盘，U盘，光盘，固态硬盘等等。

文件物理结构
文件在磁盘或者其他存储介质中实际存储的形式为物理结构：
连续分配，链接分配，链接分配分为隐式链接，显式链接，索引分配。
连续分配即为线性表，支持顺序，随机访问。
隐式链接即单链表，仅支持顺序访问。
显式链接为支持随机访问的链表，可以类比图的邻接表。
索引分配中有三种不同的分配方案，第一种是单纯的链接，第二种是套娃，索引里面有一层索引，第三种是既有单纯的链接，也有索引里的索引，也就是混合索引分配。

文件逻辑结构
按逻辑结构分为，无结构文件(流式文件)和有结构文件。
其中，有结构文件又可以分为顺序，索引，索引顺序文件。

2) 文件的管理

文件控制块和索引节点
主要由文件控制块(FCB)所控制，索引节点也是其中重要一环。每一个索引节点对应一个文件

文件和目录的操作
增删查改等等，非常简单。

注意：在其中，打开文件并不会直接将文件内容直接读入内存。

常见目录结构

• 单目录
  很明显不支持在一个目录下重名的文件。
• 二级目录
• 树形(多级)目录

3) 磁盘存储管理

文件读写时间
磁盘中文件读写时间，有许多因素控制：磁头寻道时间，读取数据时间，等待时间等待。
其中影响最大的时磁头寻道时间，因此引入了磁盘寻道算法。
磁盘寻道算法

• 先来先服务FCFS
  根据访问磁盘序列的顺序来调整。
• 最短寻道时间优先SSTF
  根据访问磁盘序列的有序顺序来调整，首先找到离当前磁道最近的一个，从它开始，往后也是如此。
• 扫描算法(电梯算法)SCAN
  分为从序号小向序号大走和从序号大向序号小走。在走完一个有序序列后，开始逆序向其他序列移动。
• 循环扫描算法C-SCAN
  分为从序号小向序号大走和从序号大向序号小走。在走完一个有序序列后，开始按原有顺序向其他序列移动。

空闲空间管理
空闲的磁盘空间不可能一个一个遍历的去管理，因此有常见的以下几种方式：

• 空闲表法
  类比顺序表。
• 空闲链表法
  类比链表。
• 位示图法
  用二进制中的1和0表示是否有空闲空间。一个二进制对应一个盘块，(字号，位号),(行号，列号)与盘块号一一对应。

4) 文件性能管理

文件的共享
分为软链接和硬链接两种。
所谓软链接，就是一种快捷方式的链接，删除了此链接，并没有真正删除此链接对应的文件。
硬链接中含有链接计数count变量，用来记录有多少了文件链接至此。只有当所有链接文件都被删除时，硬链接才真正删除消失。

文件的保护
口令保护，加密控制，访问控制等。其中访问控制由系统提供。

五、设备管理

1) I/O设备

设备的控制方式

• 直接控制方式
  由硬件直接控制，直接简单，但缺点在于一时间内只能有一个进程正在运行，CPU存在感太足，效率太低。
• 中断控制方式
  引入中断机制后，进程可以并发的运行，从而提高了CPU的利用率，但仍然不够。
• DMA方式
  DMA方式是由DMA控制器控制操作，只需要CPU在一些必要环节参与，大幅减少了CPU的参与感。
• 通道方式
  通道是一种硬件，一种弱鸡版的CPU，有了它之后，CPU只需要在进程开始执行时发出指令和结束时发出指令即可，也就是进一步减少了CPU的参与感。

I/O软件层次结构

最顶层为用户软件，最底层为硬件

• 设备独立性软件位于用户软件的下一层，为用户软件提供服务(设备独立性为用户软件统一一个接口来进行调用)。
• 设备驱动程序为不同设备提供不同的接口，方便实现它们的各自功能。
• 中断处理程序是为了实现设备中断，从而同硬件进行交互，因此位于硬件上方。

2) 缓冲管理

缓冲的出现主要是为了解决CPU与I/O设备速度之间不匹配所带来的矛盾的。

• 单缓冲
  顾名思义就是一个缓冲区，要么用来输入数据，要么用来输出数据。输入输出无法同时进行。只能单向传输。
  其中输入数据的时间为T(Input),处理时间C(Circulate),传送M(Transmit)。

采用单缓冲策略，处理一块数据的用时为MAX(C,T)+M

• 双缓冲
  不同于单缓冲，它有两个缓冲区，自然可以实现输入输出的同时进行，也就是全双工。可以双向传输。

采用双缓冲策略，处理一块数据的用时为MAX(C+M,T)

• 循环缓冲
  设置一个指针in，指向可以冲入数据的缓冲区，一个指针out，指向可以取出数据的缓冲区。
• 缓冲池

缓冲池比较复杂，一图胜千言：

3) 设备分配及处理技术

设备分配的数据结构
逻辑设备表(LUT),系统设备表(SDT),设备控制表(DCT),控制器控制表(COCT)，通道控制表(CHCT)

设备分配的过程和回收
分配过程如下：

1. 进程提出I/O请求设备
2. 根据该设备所在LUT，找到SDT，尝试分配
3. 根据SDT，找到DCT，尝试分配
4. 根据DCT，找到COCT，尝试分配
5. 根据COCT，找到CHCT，尝试分配

设备分配应该考虑的问题
判断是否有上述中哪一个步骤分配失败，一旦分配失败，下述步骤不再进行。

设备独立性/无关性程序，设备驱动程序，中断程序
设备独立性/无关性顾名思义，设备是什么与其无关，它独立与设备而存在。就好比是一个把所有设备全都统一的接口。
设备驱动程序是每一个外部设备都会有的，一般都是在出厂时就已经被厂家设定完毕，驱动程序是会有区别的。不然为什么每次换新设备插入到电脑上时，你的电脑总会提示你新设备驱动程序安装中呢？
中断程序就是用来进行中断处理。

Spooling技术
在批处理阶段引入的此技术，当时的存储设备为磁带，处理输入输出进程的过程如下图：

Spooling是一种以空间换时间的软件技术。通过在内存中开辟缓冲区来“接受输入输出设备信息的中转站”，在磁盘中开辟输入井和输出井作为“磁带”，输入输出进程用来模拟外围控制机。一图胜千言：