# 操作系统复习
## cha 1

### os作用

向下：

管理、控制和调度计算机系统软、硬件资源；

对程序的执行进行控制和调度，提高系统效率和资源利用率。

向上：

在裸机基础上形成更易理解和使用的“虚拟机”供应用程序使用；

为普通用户提供友善的运行环境，为开发者提供程序接口。

### os作用

- 处理器管理
- 内存管理
- 设备管理
- 文件管理

### 多道程序操作系统

- 多道程序设计是指允许多个程序同时进入一个计算机系统的内 存并启动进行计算的方法。
- 引入多道程序设计技术的根本目的:提高CPU的利用率

### 三类os

- 批处理
- 分时
- 实时

### 分时os

多个用户分享使用同一台计算机

- 同时性
- 独立性
- 及时性
- 交互作用性

### 实时os

- 及时性 系统能及时响应外部事件的请求，并在规定时间内完成对该事件的处理；
- 高可靠性 系统本身要安全可靠，因为像生产过程的实时控制、航空订票等实时事务系统，信息处理的延误或丢失往往会带来不堪设想的后果。

### 批处理

批处理操作系统的主要特点是：***脱机、多道和成批处理***。

**脱机**是指用户脱机使用计算机，即用户提交作业之后直到获得结果之前几乎不再和计算机打交道。

**多道**是指多道程序运行，即按多道程序设计的调度原则，从一批后备作业中选取多道作业调入内存并组织它们运行；

**成批处理**是指操作员把用户提交的作业组织成一批，由操作系统负责每批作业间的自动调度。

### 操作接口

- CLI(Command Line Interface)
- batch(批处理)
- GUI(Graphic User Interface)

### 程序接口

- system call
- API

### Dual Mode

- user mode
- kernel mode

user mode ----> kernel mode:系统调用，中断 异常

kernel mode ----->user mode:特权指令 将用户进程的psw加载到psw寄存器

### os结构

#### 宏内核

按照功能划分可以相互调用的模块，分别设计、编码、调试 各个模块，最后把所有的模块连接起来构成一个完整的单体 系统。

- 优点

结构紧密，组合方便，执行效率高。

- 缺点

模块独立性差，可靠性低，系统功能增、减十分困难。

#### 微内核

内核仅实现最基础功能

其余功能放在内核外

#### 层次式

将操作系统划分为内核和若干模块， 这些模块按照功能的调用次序排列成 若干层次，各层之间只能存在单向依 赖或单向调用关系，即低层为高层提 供服务，高层可以调用低层功能，反 之则不能。

- 调用关系清晰（高层对低层单向依赖）
- 低层和高层可分别实现（可扩充性）
- 高层错误不会影响到低层（正确性）
- 避免了递归调用
- 可增强系统可维护性
- 部分功能无法很分清谁上谁下，如处理器调度和存储管理
- 降低了系统运行效率

#### 混合内核

混合内核很像微内核结构，只不过 它的组件更多的在内核态中运行， 以获得更快的执行速度

#### 虚拟机

利用多重化和共享技术把一个裸机改变成若干个逻辑 上的对应物。

每台虚拟机包含内核态/用户态、中断、CPU、I/O设 备、内存、外存等全部部件，功能与裸机相同，可以 运行裸机能够运行的任何操作系统，不同虚拟机可以 运行不同操作系统。

### 原语

计算机进程的控制通常由原语完成。所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。

### 内核属性

- 内核由中断驱动
- 内核不可抢占
- 内核可以在屏蔽中断情况下执行
- 内核可使用特权指令

## cha2

### 特权指令

- 具备改变机器状态、修改寄存器内容、启动I/O设备等特权的机器指令，如设置时钟、控制中断屏蔽位、清内存、加载程序状态字等。
- 特权指令仅能由操作系统使用。

### 非特权指令

- 指令系统中除了特权指令之外的指令。
- 非特权指令既可以被操作系统使用，也可以被应用程序使用。

### 中断源

#### 外中断源

- 来自处理器及内存之外的中断信号，用于I/O设备对CPU的中断；如：外部设备中断、时钟中断、键盘中断等。
- 异步中断
- 可屏蔽
- 由现行指令无关的中断信号触发，且中断的发生与CPU处在用户态和内核态无关，通常在两条机器指令之间才可以响应中断。一般来说，中断处理程序提供的服务不是当前进程所需的。

#### 内中断

- 不可屏蔽
- 一般是由处理器正在执行的现行指令而引起的，一条指令执行期间允许且必须响应异常。通常，异常处理程序提供的服务是为当前进程所用的。

##### 访管

系统调用

##### 硬件

掉电 内存奇偶校验错误

##### 程序性异常

非法操作、地址越界、断点、除数为0

### 三态模型

- 运行态
- 就绪态
- 等待态

### PCB

- 进程控制块（Process Control Block, PCB）是操作系统为了管理进程设置的一组专门的数据结构，它是一个既能标识进程的存在，又能刻画进程执行瞬间的诸多特征。
- 系统在创建进程时，为它建立PCB，当进程运行结束被撤销时，回收其所占用的PCB， PCB是系统感知进程存在的唯一标志。
- 操作系统根据PCB对并发执行的进程进行管理和控制，进程借助于PCB才能被调度执行。

### 线程&&进程

进程与线程的联系和区别：

进程是资源分配的基本单位，而线程与资源分配无关。

当进程发生调度时，不同的进程拥有不同的虚拟地址空间，而同一进程内的不同线程共享同一地址空间。

线程只由相关堆栈寄存器和线程控制块组成。

进程切换时涉及到有关资源指针的保存以及地址空间的变化等问题；线程切换时，由于同一进程内的线程共享资源和地址空间，将不涉及资源信息的保存和地址变化问题。而且，进程的调度与切换都是由操作系统内核完成，而线程则既可由操作系统内核完成，也可由用户程序进行。

进程间的关系比较疏远，而线程间的关系则要紧密得多。

进程与程序的区别：

进程更能真实地描述并发，而程序不能

进程是由程序和数据和进程控制块三部分组成的

程序是静态的，进程是动态的

进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的

一个程序可对应多个进程，反之亦然

进程具有创建其他进程的功能，而程序没有

### 处理器层次

#### 高级调度（**作业调度、长程调度）**

按一定的原则从外存上处于后备状态的作业中选择一个或多个，给它们分配内存、I/O设备等必要的资源，并建立相应的进程，以使该作业具有获得竞争处理器的权利，其中作业是用户在一次计算过程中，或一次事务处理中要求计算机所做的全部工作的总和。

#### 中级调度**（交换调度、中程调度）**

为提高内存利用率和系统吞吐量，应使那些暂时不能运行的进程放弃占用内存资源，即调至外存对换区等待；当内存稍有空闲时，可将外存中那些具备运行条件的就绪进程重新调入内存，修改其状态，挂到就绪进程队列等待进程调度。

#### 低级调度**（进程调度、短程调度）**

按照某种策略从就绪队列中选取一个进程，将处理器分配给它。

进程调度是操作系统中最基本的一种调度，在一般操作系统中都必须配置进程调度。

### 周转时间 平均周转时间

周转时间

•一个进程从提交到完成之间的时间间隔，包括实际执行时间和等待资源的时间。

•批处理系统重要指标。

平均

周转/n

带权 权=周转/估计

### 调度算法

- FCFS 先来先搞
- SJF 最短作业
- HRRF 最高响应
- 优先级 看优先级
- RR 时间片轮转
- MLFQ 多队列

## cha3

### 信号量与pv

信号量:非负整数

p:申请

v:释放

### 进程的通信

- 低级进程通信：效率低，主要针对控制信息的传送。典型 实例为信号量机制。

- 高级进程通信：能以较高速率传输大量数据；进程通信实 现细节由操作系统提供，整个通信过程对用户透明，通信 程序编制简单
- - 管道通信机制 管道(Pipeline)是用于连接读进程和写进程以实现它们之间 通信的共享文件(shared file)，是UNIX的传统进程通信方式。管道是单向的，发送进程（即写进程）视管道文件为输出 文件，以字符流的形式把大量数据送入管道；接收进程 （即读进程）是管道文件为输入文件，从管道中接收数据。
- 共享内存通信机制 相互通信的进程间设有公共内存，一组进程向该公共内存中写， 另一组进程从公共内存中读，通过这种方式实现两组进程间的 信息交换。 一个进程首先创建一块内存区作为通信使用，而其余进程则将 这块内存区映射到自己的虚存空间。各进程通过读写自己虚拟 内存空间中对应的共享内存区，实现通信。
- 消息传递通信机制 进程间的数据交换以消息(message)为单位，程序员直接 利用系统提供的一组通信原语来实现通信。
- 直接（同步）通信 \- 一个运行进程可以在任何时刻向另一个运行进 程发送或者请求一条消息；
- 间接（异步）通信 借助于收发双方进程之 外的共享数据结构作为通信中转，该共享的内 存称为信箱（Linux中消息队列 ）。

### 死锁

#### 定义

多个进程因竞争系统资源或互相通信而处于永久等待状态，若无外 力作用，这些进程都将无法向前推进。

#### 产生原因

- 竞争资源
- 进程推进次序不当

#### 必要条件

- 互斥条件 一个时刻，一个资源仅能被一个进程占有。
- 不可剥夺条件 除了资源占有进程主动释放资源，其它进程都不可抢夺其资源
- 占有和等待条件 请求资源未果进程虽阻塞但保持占有资源不放。
- 循环等待条件 Pn等待P1占有的资源，形成一 个进程等待环路。

#### 银行家算法

#### 矩阵含义

- 可利用资源向量Available
- 最大需求矩阵 Max
- 分配矩阵 Allocation
- 需求矩阵 Need

分配，然后找有没有安全序列

## cha4

### 分区分配

- 最先适应
- 下次适应
- 最优适应
- 最坏适应

### 逻辑--->物理

#### 段表

| 段号 | 段长 | 基址 |
| ---- | ---- | ---- |
| | | |

| 段号 | 段内地址 |
| ---- | -------- |
| | |

#### 页

| 页号 | 页内偏移 |
| ---- | -------- |
| | |

### 快表

快表检索时间x ns，内存访问时间 y ns

在快表中找到 为 x+y ns

找不到为 x+y+y ns

### 多级页表

| 页目录位移 | 页表页位移 | 页内位移 |
| ---------- | ---------- | -------- |
| | | |

### **部分装入和部分对换**

#### 部分装入

- 进程运行时，仅加载部分进入内存，而不必全部装入。
- 其余部分暂时存放在swap space

#### 部分换出

- 可以将进程部分对换出内存，用以腾出内存空间。
- 对换出的部分暂时存放在swap space

### 置换算法

- OPT 最佳
- FIFO 先进先出
- LRU 预测
- 2nd chance
- Clock

### 抖动

#### 定义

置换那些必须很快被换回的页面。这种频繁的页面调度活动称为抖动

#### 解决方案

- 基于工作集策略的解决方案
- 基于缺页中断率的解决方案

## cha5

### IO控制方法

- 常见的I/O控制方式有四种：程序直接查询控制方式、中断方式、DMA方式和通道方式。

- - 程序直接查询控制方式：

- - 用户进程直接控制主机和外围设备之间的数据传输。用户进程与外围设备读取数据时，主机向设备控制器发出读指令后进入测试等待状态。在等待时间内，主机重复查询外设的准备状态直至外设准备就绪。外设就绪，数据传送开始，主机从设备控制器读取一个字，再向内存写一个字。如果传送还未结束，再次向设备控制器发出读指令，直到全部数据传输完成再返回现行程序执行。用户进程向外设写数据与读数据基本类似。
- 程序查询方式中，一旦主机启动外设，便不断查询外设的准备情况，终止了原程序的执行，浪费了宝贵的主机时间；另一方面，外设准备就绪后，主机参与数据的传送工作，此时主机也不能执行原程序。可见这种方式中，主机和外设串行工作，使主机不能充分发挥效率。

- - 中断方式：

- - 仅当操作正常或异常结束时才中断CPU。实现了一定程度的并行操作，这叫中断方式。在主机启动外设后，不必查询外设是否就绪，而是继续执行现行程序，对设备是否就绪不加过问。此时主机和外设并行操作。外设准备完毕，将数据传送至设备控制器的寄存器后，外设向主机发出中断请求，主机从设备控制中将数据读入内存指定单元。
- 在中断方式中，外设输入每个数据的过程中，无需主机的干预，因而可使得主机与外设并行工作。仅当输完一个数据时，才需要主机花费时间中断处理。中断方式在一定程度上提高了主机和外设的并行程度，提高计算机系统资源的利用率。

- - DMA（直接内存存取）方式：

- - 在DMA方式中，内存和外设之间有一条数据通路，在内存和外设之间成块传送数据过程中，由DMA控制器取代主机来控制数据传输，直接执行到数传输完成。

- DMA方式的特点：

- - 数据传输的基本单位是数据块，即在主机与外设之间传送一个数据块；
- 传送的数据直接从外设到内存，或者相反；
- 仅在传送一个数据块或多个数据块的开始和结束时才需要主机的干预。

- DMA控制器由三个部分组成：主机与DMA的接口、DMA控制器与设备的接口和I/O逻辑，

- - - 关于DMA控制器中的4类寄存器：

- - 命令/状态寄存器（CR）。用于接收从CPU发出来的I/O命令或有关控制信息，或设备的状态。
- 内存地址寄存器（MAR）。在输入时，存放把数据从设备传送到内存的起始目标地址；在输出时，存放由内存到设备的内存源地址数据
- 寄存器（DR）。用于暂存从设备到内存，或从内存到设备的数据。
- 数据计数器（DC）。存放本次CPU要读写的字节数。

- 工作过程：CPU要从磁盘读数据时，便向磁盘发一条指令。该命令被传送到CR中。同时，将本次数据存放在内存中的起始地址送给MAR，将要读取数据的字节数传送给DC，还要将磁盘中的源地址送给DMA中的I/O逻辑。启动DMA控制器进行数据传送，CPU可以处理其他任务。此后，整个传输过程中均由DMA进行控制。每传送一个字，DC计数器减1，直至DC计数器为0，整个传输过程结束。

- - 通道方式：

- - 通道是独立于CPU的专门实现输入输出工作的处理机。

- 通道与一般处理机的区别：

- - 通道指令单一。通道硬件比较简单，其所能执行的指令主要是与输入输出操作有关的指令。
- 通道没有自己的内存。通道所执行的通道程序是放在计算机内存中的，也就是说通道与CPU共享系统的内存。

- 通道指令通常包括以下信息：

- - 命令码：指出通道命令的操作，常见的操作有读、写、控制、通道转移等
- 内存地址：用于标明交换数据在内存中存放的位置
- 计数：用于表示本条指令所要交换数据的字节数
- 通道程序结束位：用于表示该指令是否是通道程序的最后一条指令
- 记录结束标志位：用于表示本指令与下一通道指令处理的数据是否是同一个记录

- 通道的分类：字节多路通道、数组选择通道、数组多路通道。

### 设计目标与原则

- 设备无关性
- 出错处理
- 同步/异步传输
- 缓冲技术

### IO操作所应执行的步骤

- 应用进程对已打开文件的文件描述符执行读系统调用(库函数)。
- 独立于设备的I/О软件检查参数是否正确,若正确,检查高速缓存中有无要读取的信息块;若有,从缓冲区直接读至用户区,完成IO请求。
- 若数据不在缓冲区,执行物理VO操作,独立于设备的IO软件将设备的逻辑名转换成物理名,检查对设备操作的许可权,将IО请求排队,阻塞应用进程且等待VO操作完成。
- 内核启动设备驱动程序,分配存放读出块的缓冲区,准备接收数据并向设备控制寄存器发送启动命令,或建立DMA传输,启动Io。
- 设备控制器操作设备,执行数据传输。
- 当采用DMA控制器控制数据传输时,一旦传输完成,硬件产生I/О结束中断。
- CPU响应中断,转向磁盘中断处理程序。它检查中断产生原因和设备的执行状态,若设备有错,向设备驱动程序发信号,检查是否能重复执行,如果允许,重发启动设备命令,再次传输;否则,向上层软件报告错误。若设备VО正确完成,将数据传输到指定的用户进程空间,唤醒阻塞进程并将其放入就绪队列;然后,系统检查有无V)请求在排队,若有,再启动设备,继续传输。至此,中断处理完成且返回,将成功或失败的信息逐层向上报告。
- 当应用进程被再次调度执行时,从VO系统调用的断点处恢复执行。

### SPOOLing

#### 概念

操作系统中采用的一项将独占设备改造成共享设备的技术

借助SPLOOLing同时处理多个进程对独占设备的请求，让每个进程都感觉自已拥有设备，我们称这种设备为“虚拟设备”

SPOOLing技术借助于高速随机外存（磁盘）的支持

输入井：模拟脱机输入时的磁盘缓冲区，用于收容I/O设备输入的数据

输出井：模拟脱机输出时的磁盘缓冲区，用于收容用户进程的输出数据

输入缓冲区：用于暂存由输入设备送来的数据，以后再传送到输入井

输出缓冲区：用于暂存从输出井送来的数据，以后再传送给输出设备

#### 实现

- 预输入程序 模拟脱机输入时的外围控制机，将用户要求的数据从输入设备通过输入缓冲区再送到输入井-

- 缓输出程序 模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备上。

#### 优点

- 从对低速I/O设备进行I/O操作变为对对输入井/输出井的操作，提升了I/O速度。
- CPU数据处理与设备I/O操作的并行化，提升了系统资源的使用效率。

### 磁盘

- 磁盘块0是第0号柱面、第0号磁头的第0个扇区

- 先按磁道内扇区顺序，再按柱面内磁头顺序，再按从外到内的柱面顺序进行编号。

某个块号的定位参数为(i, j ,k)，其中i, j, k分别表示该块的柱面号、磁头号和扇区号

x=i\*t\*s + j\*s + k

i=x DIV(t\*s)

j=(x mod(t\*s)) DIV s

k=(x mod (t\*s)) MOD s

### 完成一次IO的平均访问时间

- 寻道时间 ts
- 旋转延迟 tr=1/2*r r为磁盘转速
- 传送时间 tt=b/r*n b为传送字节数 n为一个磁道中的字节数，r为转速

## cha6

### 文件系统

在逻辑文件与物理文件、逻辑地址与物理地址之间实现转换，使得存储空间利用率高、存取速度快。

### FCB

文件由FCB跟文件体组成。

- 操作系统为每个文件建立的唯一数据结构，其中包含了全部文件属性，其目的是为方便操作系统对文件的管理、控制和存取。
- 文件被创建时，系统为其建立一个FCB，用来记录文件的属性信息；每当存取文件时，先找到其FCB，再找到文件首块物理位置或索引表，随后存取文件信息。

### 文件逻辑结构

- 流式文件 每个字节有一个索引
- 记录式文件
- - 纪录式顺序文件 文件记录顺序生成并被顺序访问
- 纪录式索引顺序文件 有索引表

### 文件物理结构

#### 顺序文件

- 文件中逻辑上连续的信息存储在磁盘上也保持连续的结构
- 文件目录记录了文件第一块块号和块数
- 逻辑结构与物理结构相同

- 优点
- - l简单，只需要记录文件的起始块号和长度
- l寻道时间最少
- l支持直接存取

- 缺点
- - 存在外部碎片问题：磁盘空间分割后形成的较小的无法存储文件的连续区，虽可使用紧凑技术，但开销太大
- l必须事先知道文件的长度，且不适合文件的增长。

#### 链接文件

- •通过盘块上的指针实现**同一文件多个离散盘块**的链接；
- •文件目录记录了文件第一块和最后一块的块号；
- •各块之间通过指针连接，前一个盘块指向下一个盘块，当连接指针为0时表示本块是文件的最后一块。
- - 优点
- l消除了外部碎片，外存空间利用率高
- l按需分配，且无需事先知道文件长度
- l支持文件动态增长，方便文件增删改

- - 缺点
- l指针占用盘块额外空间
- l只适合顺序访问，对随机存取极其低效
- l存在断链可能，可靠性较差。

#### 索引文件

- l将文件占用的所有物理块号按逻辑顺序保存在一张索引表中，存有索引表的物理块称为索引块(index block)
- l目录项中指出索引块块号

- 优点 随机访问
- 缺点 索引块占用磁盘空间

- addr[0]-addr[11]直接
- addr[12]一级间接
- addr[13]二级间接
- addr[14]三级间接

x=sizeof(盘块)/sizeof(盘号)

maxsize=12\*sizeof(盘块)+x\*sizeof(盘块)+x\*x\*sizeof(盘块)+x\*x\*x\*sizeof(盘块)

### 打开与关闭文件

#### 打开

- 检索目录
- 对比参数mode给出的方式与活动inode中的文件访问权限对比
- 打开合法时候，为用户打开文件表项喝系统打开文件表项。简历表项与活动inode联系，把文件描述符fd返回

#### 关闭

- 根据fd找到文件表项，在找到系统打开文件表项，释放用户打开文件表项

- 对应的f_count - 1，为0则释放活动inode
- 把活动inode 的i_count - 1 ，为0把内容复制回文件卷上的相应磁盘indoe中，释放改活动inode

### 位示图

- 每个磁盘块用一个位来表示，如果磁盘块空闲，位为1；如果已分配，位为0.

#### 分配

- ) 逐字顺序扫描位示图，找出第一个不为0的字，从中找出第一个值为1的二进制位；
- ) 求对应盘块号：b= n × (值为0的字数) + 该位的字内偏移；
- ) 按盘块号分配盘块，同时修改位示图中相应位为0。

#### 回收

- ) 将回收盘块的盘块号b转换为位示图中的字号i和字内偏移j：i = b DIV n ; j = b MOD n;

- ) 按盘块号回收盘块，同时修改位示图中相应位为1。