写在前面

1、这课好难，考得不太好所以就简单传一下吧，也是一样，无论考研还是找工作都是很重要的一门课，能打好基础就尽量先学学吧！
2、考到现在大火应该都清楚了，收重点 & 明显会出的大题一定要会，其实通过就差不多了
3、本次先放大题整理再放知识点吧，感觉知识点部分帮助不大
4、希望你能顺利通过~

大题部分

知识点部分

一、操作系统概述

一组主管并控制计算机操作、运用和运行硬件、软件资源和提供公共服务来组织用户交互的相互关联的系统软件程序

提供一个让用户与系统交互的操作界面

对计算机资源进行管理的软件

1、特征

1）并发：两个或多个活动在同一给定的时间间隔中进行

• 并行：同一时刻

2）共享：计算机系统中的资源被多个进程所共有

3）异步：进程以不可阈值的速度向前推进

4）虚拟：把一个物理上的实体变为若干个逻辑上的对应物

5）最基本特征：并发、共享（二者互为存在条件）

2、功能

1）处理机管理：进程控制、进程同步、进程通信、死锁处理、处理机调度等。

2）储存器管理：内存分配、地址映射、内存保护与共享和内存扩充等功能。

3）文件管理：文件存储空间的管理、目录管理及文件读写管理和保护等。

4）设备管理：缓冲管理、设备分配、设备处理和虚拟设备等功能。

5）用户接口

3、历程

1）单道批处理阶段

• 优点：缓解人机速度矛盾
• 缺点：系统资源利用率低

2）多道批处理阶段（操作系统正式诞生）

• 优点：多道程序并发执行，资源利用率高
• 缺点：不提供人机交互能力，缺少交互性

3）分时操作系统

• 多个用户分享使用同一台计算机，每个用户分到的时间片固定就是每个用户只能使用计算机固定的时间，因此用电脑的人数越多，响应时间越长（时间片固定的情况下）。

• 优点：提供人机交互

• 缺点：不能优先处理紧急事务

4）实时操作系统

• 硬实时系统：必须在被控制对象规定时间内完成
• 软实时系统：可以松一些
• 优点：可以优先处理紧急任务，从可靠性看实时操作系统更强，从交互性看分时操作系统更强

4、补充概念

1）特权指令：不允许用户程序使用（只允许操作系统使用）e.g.IO指令、中断指令，只能在系统态下执行

2）非特权指令：普通的运算指令

3）内核程序：系统的管理者，可以执行一切指令，运行在核心态

4）应用程序：普通用户程序只能执行非特权指令，运行在用户态

5）访管指令：在用户态使用的，指令含义是用户自愿进入核心态，核心态下可以执行特权指令和非特权指令

5、处理机状态

1）用户态（目态）：CPU只能执行非特权指令

2）核心态（管态、内核态）：可以执行所有指令

• 用户态 -> 核心态：通过中断（硬件完成）
• 核心态 -> 用户态：特权指令psw的标志位，0用户态，1核心态

6、原语

1）处在操作系统的最底层，是最接近硬件的部分

2）程序的运行具有原子性，其操作只能一气呵成

3）运行时间较短，且调用频繁

7、中断、系统调用、体系结构

1）内中断（异常，信号来自内部）

• 自愿中断：指令中断
• 强迫中断：软件中断、硬件中断e.g. 0除以0

2）外中断（中断，信号来自外部）：外设请求、人工干预

3）系统调用：系统给程序员（应用程序）提供的唯一接口，可获得OS的服务，在用户态发生，在核心态处理

4）体系结构：

• 大内核：用户态只负责应用程序部分，其他交由内核态处理
• 微内核：内核态只完成最重要的部分（时钟管理、中断处理、原语），其他由用户态处理

二、进程管理

2.1 进程管理

进程：是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配的基本单位，是操作系统结构的基础，是指计算机中已执行的程序，曾经是分时系统的基本运作单位，现在是线程的容器

1、特性

1）动态性：进程的实质是程序在多道程序系统中的一次执行过程，进程是动态产生，动态消亡的

2）并发性：任何进程都可以同其他进程一起并发执行

3）独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位

4）异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进

5）结构特征

• PCB进程控制：保存进程运行期间相关的数据，是进程存在的唯一标志
• 程序段：能被进程调度到CPU的代码
• 数据的：存放数据

2、状态

1）运行态：进程正在占用CPU

2）就绪态：进程已处于准备运行的状态，即进程获得了除处理机以外的一切所需资源，一旦得到处理机即可运行

3）阻塞态：进程由于等待某一时间不能享用CPU

4）创建状态：进程正在被创建

5）结束状态：进程正在从系统消失

• 就绪态 -> 运行态：处于就绪态的进程被调度以后，获得处理机资源（分派处理机时间片）
• 运行态 -> 就绪态：时间片用完或在可剥夺系统中有更高级的进程进入
• 运行态 -> 阻塞态：进程需要的某一资源还没有准备好
• 阻塞态 -> 就绪态：进程等待的事件到来时

3、线程、进程的区别

1）线程：操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中的一个单一顺序的控制流，一个进程中可以并发多个线程。

2）进程：操作系统进行资源分配的最小单元，是操作系统结构的基础。

4、进程、程序的区别

对比维度	程序（Program）	进程（Process）
基本概念	有序代码的集合	程序的一次执行过程
状态特性	静态的	动态的
存在形式	长久存在，可存放在磁盘中	临时存在，随执行产生和消亡
是否执行	不执行，仅作为代码和数据	正在执行或等待执行
组成内容	程序代码和相关数据	程序、数据以及进程控制块（PCB）
状态变化	无状态变化	具有创建、就绪、运行、阻塞、结束等状态
一对多关系	一个程序可对应多个进程	一个进程只能对应一个程序
多实例情况	同一程序可被多次执行	多个进程可同时运行同一程序
举例说明	浏览器程序	打开的多个浏览器窗口（多个进程）

2.2 处理机调度

1、概念

是对处理机进行分配，即从就绪队列中按照定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行

2、分类

1）高级调度：作业调度

2）中级调度：内存对换

3）低级调度：进程调度

3、调度方式

1）剥夺式（抢占）：强行插队

2）非剥夺式

4、调度准则

1）CPU利用率

2）系统吞吐量

3）周转时间

4）等待时间

5）相应时间

5、算法

1）先来先服务FCFS/FIFO

2）短作业优先

3）优先级调度算法：分剥夺/非剥夺

4）高响应比优先调度算法：有利于短作业又兼顾了长作业等待时间相同时，要求服务时间越短，优先权越高，利于短作业；而对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而获得处理机

5）时间片轮转

6）多级反馈队列调度算

6、计算

1）响应比 = （等待时间 +运行时间）/ 运行时间

2）周转时间 = 等待时间 + 运行时间 or 作业完成时刻 - 作业到达时刻

3）带权周转时间 = 周转时间 / 运行时间

4）平均周转时间 = 作业周转总时间 / 作业个数

2.3 进程同步

1、引入原因

协调进程之间的相互制约关系

2、制约关系

1）同步/直接制约关系：为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系

2）互斥/间接制约关系：当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程推出临界区后，另一进程才允许去访问此临界资源

3、临界

1）临界资源：一次仅允许一个进程使用的资源

2）临界区：在每个进程中访问临界资源的那段程序

3）临界区互斥：

• 原则：

  • 空闲让进：如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入

  • 忙则等待：任何时候，处于临界区内的进程不可多余一个。如已有进程进入自己的临界区，则其他所有试图进入临界区的进程必须等待

  • 有限等待：进入临界区的进程要在有限时间内退出，以便其他进程能及时进入自己的临界区

  • 让权等待：如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象

• 基本方法：信号量，利用PV操作实现互斥（P：使用，V：放回）（均为低级）

  • 对信号量S，如果小于0，则绝对值即等待进程数量；等于0，无可用资源，也无等待进程；大于0，几个可用资源

2.4 死锁

1、产生原因

非剥夺资源的竞争和进程的不恰当推进顺序

2、定义

多个进程因竞争资源而造成的僵局，如果没有外力，这些进程将无法推进

3、解决方法

1）预防死锁：破坏互斥条件、破坏不剥夺条件、破坏请求和保持条件、破坏循环等待条件

2）避免死锁：安全状态、银行家算法

3）检测死锁：利用死锁定理

4）接触死锁：资源剥夺法、撤销进程法、进程回退法

4、计算

进程数小于资源数，则不会发生死锁的公式为：

1）最多申请资源数 = 资源总数 / 进程数 ，可整除的情况下

2）最多申请资源数 = （资源总数 / 进程数）+ 1 ，otherwise

三、内存管理

3.1 内存管理的基本概念

1、主要功能

1）内存空间的分配与回收

2）存储的保护和共享：保证各道作业在各自的存储空间内运行，互不干扰

3）地址转换：在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址

4）内存扩充：利用虚拟内存技术或自动覆盖技术，从逻辑上扩充内存

2、用户程序的主要处理阶段

1）编辑阶段：创建源文件

2）编译阶段：由编译程序将用户源代码编译成若干目标模块，生成目标文件

3）链接阶段：由链接程序将编译后形成的一组目标模块及所需的库函数链接到一起，形成一个完整的装入模块，生成可执行文件

4）装入阶段：由装入程序将装入模块装入内存运行

5）运行阶段：得到结果

3、程序的装入

1）绝对装入

在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对地址的目标代码。即按照物理内存的位置赋予实际的物理地址。

优点：在时间效率上很高。

缺点：

• 由于内存大小限制，能装入内存并发执行的进程数大大减少。

• 编译程序必须知道内存的当前空闲地址部分和其地址，而在多道程序环境下，编译程序根本不可能知道当前空闲地址的部分。因此，绝对装入方式只适用于单道程序环境。

2）静态重定位

静态重定位是在程序装入对目标代码装入内存的过程中完成的，是指在程序开始运行前，程序中指令和数据的各个地址均已完成重定位，即完成虚拟地址到内存地址映射。地址变换通常是在装入时一次完成的，以后不再改变。

优点：不需要硬件支持（这里的硬件，指的是后文提到的重定位寄存器）。（可与动态重定位对比）

缺点：程序在静态重定位之后就不能在内存中搬动了，并且要求程序的存储空间是连续的。（可与动态重定位对比）

3）动态重定位

动态重定位的方式是把地址转换推迟到程序真正要执行时才进行。但这种方式需要硬件支持，也就是重定位寄存器的支持，否则会影响指令的执行速度。

优点：可以解决碎片问题。（因为不需要像静态重定位一样要求整段程序装入，每个模块之间的存储区域不一定需要相联，只需要有自己的重定位寄存器就行）

缺点：需要硬件支持。（对比静态重定位）

4、程序的链接

1）静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开。

2）装入时链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。

3）运行时链接：对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行的链接。其优点是便于修改和更新，便于实现对目标模块的共享。

5、地址空间

1）逻辑地址空间：方便CPU看

2）物理地址空间：给计算机存储底层看

• 计算题：逻辑地址映射到物理地址后，页内偏移量不变

3.2 连续分配管理方式

1、单一连续分配

分配到内存固定的区域（单用户/单任务的操作系统）

2、固定分区分配

分配到内存不同的固定区域，分区可以相等可以不等，但要求一定是固定

3、动态分区分配

1）可变分区存储管理: 按照程序的需要进行动态的划分

2）动态分区的分配策略算法:

• 首次适应: 空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的一个空闲分区。
• 最佳适应: 空闲分区按容量递增的方式形成分区链，找到第一个能满足要求的空闲分区。
• 最坏适应: 空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，即挑选出最大的分区。
• 邻近适应: 由首次适应算法演变而成。不同之处是，分配内存时从上次查找来的位置开始继续查找。

3.3 非连续分配管理方式

1、基本分页式存储管理

将内存空间分为一个个大小相等的分区（比如：每个分区4KB），每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块”。

每个页框有一个编号，即“页框号”页框号从0开始。将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或“页面”。

每个页面也有一个编号，即“页号”，页号也是从0开始。

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。

• 即：页号通过页表找到相应的块号，块号再加页内地址（不变的偏移量）就得到了物理地址

2、基本分段式存储管理

在分段存储管理方式中，作业的地址空间被划分若干个段，每个段定义了一组逻辑信息。其核心运作方式，与分页式存储管理相同

3、分页和分段的区别

对比维度	页 (Page)	段 (Segment)
本质	信息的物理单位	信息的逻辑单位
划分目的	以削减内存零头，提高内存利用率为目的，不是用户需求。	具有相对完整的意义，是为了满足用户的需求。
大小	大小固定，由系统确定。	大小不固定，决定于用户编写的程序。
作业地址	一维	二维

• 最主要区别是增补位

4、碎片

1）外部碎片：没地方存导致无法存储的碎片

2）内部碎片：页分配出去后剩余的部分

3.4 内存扩充

1、覆盖

覆盖的思想：将程序分为多个段（模块），常用的段常驻内存，不常用段在需要时调入内存。(同一程序或进程中)

2、交换

交换的思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存。（进程在内存和磁盘之间动态调度。）(不同进程/作业之间进行)

3、虚拟内存

1）引入原因：在逻辑上扩充内存

2）组成部分：页表机制、中断机制（缺页中断）、地址变换机制、内存与外存

• 主要硬件支持：请求分页机制、缺页中断机制、地址变换机制

3）整体流程：

• CPU需要取地址，首先访问页表（页表包含页号和块号两部分），如果在页表中找到了，那么利用地址变换机制，变成真正的物理地址，计算机通过寻找该物理地址找到自己需要的资源。

• 如果发现页表没有自己想要的页表项，那么会触发缺页中断（缺页中断就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。）从外存调入内存的过程，如果页表满了，需要从满了的页表项中进行替换——替换算法。

4）主要特征：多次性、对换性、虚拟性

5）最大容量：

• 当CPU地址长度能表示的大小远大于外存容量时，为内存容量和外村容量之和
• 当外存容量远大于CPU地址长度能表示的大小时，由CPU字长决定（一般CPU地址长度表示的大小都大于外存容量）

4、页面淘汰（置换）算法

1）先进先出页面淘汰（置换）算法（FIFO）：淘汰最先进入内存的页面（3个内存块都为空3次缺页中断）

• 注：对于FIFO页面淘汰算法，有时增加分配给作业的可用内存块数，它的缺页次数反而上升，通常称为异常现象。

2）最近最久未用页面淘汰（置换）算法（LRU）：总是把最长时间未被访问过的页面淘汰出去（需要寄存器和栈）

3）最近最少用页面淘汰（置换）算法（clock）：总是把当前使用的最少的页面淘汰出去

4）最优（最佳）页面淘汰（置换）算法（OPT）：把以后不再使用的或最长时间内不会用到的页面淘汰出去（理论上，不会实现）

• 注意：页面淘汰是由缺页中断引起的，但缺页中断不见得一定引起页面淘汰

5）局部性原理：在几乎所有程序的执行过程中，在一段时间内，CPU总是集中地访问程序中的某一个部分而不是对程序的所有部分具有平均的访问概率

四、文件系统

4.1 文件与文件系统

1、概念

1）文件：以计算机硬盘为载体的存储在计算机上的信息集合

2）文件系统：操作系统中负责操纵和管理文件的一整套设施，它实现文件的共享和保护，方便用户“按名存取”。

• 文件系统在创建一个文件时，为它建立一个文件目录项（与进程的FCB类似）

3）影响文件安全的主要因素：人为、系统、自然

4）常见的文件存取方法：顺序存取、随机存取

2、功能

文件管理、目录管理、文件空间管理、文件共享和保护、提供方便的接口。

4.2 文件的逻辑结构

1、无结构文件（流式文件）

无结构文件是最简单的文件组织形式。无结构文件将数据按顺序组织成记录并积累保存，它是有序相关信息项的集合，以字节（Byte）为单位。

由于无结构文件没有结构，因而对记录的访问只能通过穷举搜索的方式，故这种文件形式对大多数应用不适用。但字符流的无结构文件管理简单，用户可以方便地对其进行操作。

所以，那些对基本信息单位操作不多的文件较适于采用字符流的无结构方式，如源程序文件、目标代码文件等。

2、有结构文件

1）顺序文件：文件中的记录一个接一个地顺序排列，在访问时需要顺序搜索文件

2）索引文件：通过一个索引表来检索文件，由逻辑文件和索引表构成。索引顺序文件采用稀疏索引，索引项只能确定记录所在的块，不能直接定位到具体记录，因此查完索引表后仍需在块内顺序查找。

• 逻辑索引：目的是加快文件数据的定位，是从用户角度出发的
• 物理索引：目的是管理不连续的物理块，是从系统管理的角度出发的

3）索引顺序文件：以上二者结合

4.3 目录

1、目录和目录结构

1）文件控制块：在文件系统内部给每个文件唯一地设置一个文件控制块，它用于描述和控制文件的数据结构，与文件一一对应

2）目录结构：单级目录、二级目录、树形目录、图形目录

4.4 文件实现

1、文件分配方式

连续分配、链接分配、索引分配，对应的结构是顺序结构、链式结构、索引结构

• 顺序结构不利于文件长度的动态增长
• MS-DOS系统中的磁盘文件物理结构属于链接文件

2、文件存储空间管理

1）空闲表法

2）空闲链表法

3）位示图法：用于磁盘空闲块的分配和回收（外存）

4.5 磁盘管理

1、磁盘地址结构

柱面号、盘面号、扇面号

2、磁盘调度算法

1）先到先服务算法FCFS：可能会随时改变移动臂的运动方向

2）最短查找时间优先算法SSTF：离当前磁头最近的柱面

3）扫描算法/电梯算法：直上直下

4）循环扫描算法

五、设备管理

1、目标

使用方便、与设备无关、效率高、管理统一

2、I/O设备

1）分类：存储设备或输入输出设备、块设备或字符设备、低速中速高速设备

2）IO控制方式

• 程序直接控制方式：这种方式也可以称为查询方式，cpu不断地去查询设备控制器是否将数据放到了数据存储器中，或者从数据存储器存到设备中，当完成IO时cpu才能去干别的事。
• 中断方式：这种方式当cpu发出指令后就可以去干别的事，当设备控制器把数据存在数据存储器后向cpu发出中断请求，然后cpu再来处理这部分数据。
  • 单位：字节
• DMA方式：由DMA控制器直接将IO设备中的数据以数据块为单位直接传输到内存中，当传输结束后才向cpu发起中断。
  • 只能处理连续的数据块，是一种逻辑处理
  • cpu只参与预处理和结束过程，其他部分则由dma控制器完成
  • 以存储器为核心，所以可以dma方式可以和cpu并行工作
• IO通道控制方式：可以传输不连续的数据块，减少了cpu干预。cpu通过对IO通道发出指令，然后让IO通道自己工作，等数据传输完才向cpu发起中断。
  • 以内存为中心实现设备与内存直接交换数据

3、缓冲区

1）引入目的

• 缓和CPU与外设间速度不匹配的矛盾
• 提高CPU与外设之间的并行性
• 减少对CPU的中断次数

2）设置方式

• 单缓冲：当数据到达率与离去率相差很大时，可采用单缓冲方式。
• 双缓冲：当信息输入和输出率相同（或相差不大）时，可利用双缓冲区，实现两者的并行。
• 多缓冲：对于阵发性的输入、输出，为了解决速度不匹配问题，可以设立多个缓冲区。

4、常用设备分配技术

1）根据设备的使用性质

• 独占设备: 不能共享的设备，即:在一段时间内，该设备只允许一个进程独占。如打印机。

• 共享设备: 可由若干个进程同时共享的设备。如磁盘机。

• 虚拟设备: 是利用某种技术把独占设备改造成可由多个进程共享的设备。

2）针对三种设备采用三种分配技术

• 独占分配技术：是把独占设备固定地分配给一个进程，直至该进程完成I/O操作并释放它为止。

• 共享分配技术:通常适用于高速、大容量的直接存取存储设备。由多个进程共享一台设备，每个进程只用其中的一部分。

• 虚拟分配技术:利用共享设备去模拟独占设备，从而使独占设备成为可共享的、快速I/O的设备。实现虚拟分配的最有名的技术是SPOOLing技术，也称作脱机操作。