# 操作系统

### 1.概念

操作系统(Operation System OS) 管理和控制计算机硬件与软件资源的计算机程序，直接运行在物理设备上的系统软件，任何其他的引用程序均是在操作系统平台上运行，操作系统是计算机资源的管理者，主要协调如下几个方面：

1. 处理机管理；
2. 存储器管理；
3. 设备管理；
4. 文件管理；

同时操作系统也是用户和硬件设备交互的工具，用户可以通过系统开放的API接口进行与硬件接口交互，具有如下几个场景：

1. 命令行接口，调用CMD命令行查询当前网卡的MAC地址；
2. 程序接口，程序内调用print接口实现显示输出内容在屏幕；

### 2.功能

1. 操作系统管理硬件和软件及数据资源；
2. 控制应用程序运行；
3. 增加用户使用体验（可视化界面）；
4. 作为其他应用软件的平台；

### 3.特征

1. 并发，两个或者多个任务在同一个时间间隔内发生；
2. 共享，系统中的资源可供内存中多个并发执行的进程共同使用；
3. 虚拟，物理设备变为若干个逻辑对应物；
4. 异步，躲到程序环境下，允许多个程序并发执行，程序不是同步执行而是延后执行是进程异步性的体现；





# 基本概念

1. 互斥，进程之间访问临界资源时相互排次的现象；
2. 临界资源，一次仅允许一个进程使用，例如：打印机，IO输入输出设备；
3. 临界区，包含临界资源的代码段；
4. 并发，同一个时间段，多个进程同时从启动到运行完毕，并发的两种关系是同步和互斥；
5. 并行，单核处理器中，进程之间不允许同时执行，多个经常交替执行也有可能重叠执行，进程不需要同一个时刻发生；
6. 同步，进程之间存在依赖关系，一个进程结束结果是另一个进程的输入；
7. 异步，进程之间彼此独立，开启运行时刻不确定不统一，不需要等待其他进程完成或者开始；
8. 多线程，进程并发执行一段代码，实现进程之间切换执行，异步不同等于多线程，多线程是实现异步的一个手段；





# 发展历程

- 手工阶段
- 单道批处理系统
- 多道批处理系统
- 分时操作系统
- 实时操作系统
- 网络操作系统和分布式操作系统

网络操作系统和分布式操作系统的不同，分布式操作系统中多太计算机相互协作完成同一个任务，网络操作系统中每台计算机都是相互独立。





# CPU工作状态

大多数计算机系统将CPU的执行状态分为目态和管态，管态又称特权态，CPU管态状态下可以执行系统的全部指令；目态称为用户态，目态状态下程序仅能执行非特权指令，不能直接使用系统资源，不可以改变CPU的工作状态并且仅能访问属于自己的存储空间。如下几个方法可以将目态转化成为管态：

1. 系统调用，用户态进程通过系统调用申请使用操作系统习惯的服务程序完成工作；
2. 异常，CPU执行用户态程序发送位置异常，此时触发处理异常处理的内核程序，完成目态到管态的切换，例如缺页异常；
3. I/O设备中断，用户态申请IO设备操作并完成后，CPU发出相应的中断信号，此时CPU暂停用户程序代码，将优先执行中断信号对应的处理程序；





# 处理机管理

### 1.进程控制

传统多道程序环境中，一个作业任务运行，必须创建一个或者多个进程并为之分配必要的资源，进程结束后立即销毁进程，及时收回进程占用的各类资源；

### 2.进程同步

通过多个进程协调运行

### 3.进程关系

##### <u>互斥关系</u>

进程（线程）在对临界资源进行访问则属于互斥关系

##### <u>同步关系</u>

相互协作合作完成共同任务的进程，一个进程结束结果是另一个进程的输入。

### 4.进程通讯

多道程序环境下为了加速应用进程的运行时间，系统中建立多个进程并且为一个进程建立若干个线程，进程（线程）相互合作完成一个共同的任务，进程线程中需要交互通讯。

### 5.调度

后备队列中等待的作业或者进程，经过CPU调度后才可以执行。





# 存储器管理

### 1.内存分配

采用静态和动态两种方式实现内存分配，记录内存使用情况，按照一定的算法进行对不在被需要的内存进行收回合并。

### 2.内存保护

确保用户程序仅在自己内存空间运行彼此相互独立

### 3.地址映射

编译后的程序地址分为逻辑地址和物理地址，每个程序不可能均能占据连续的物理内存，所以必须采用地址映射的方式将逻辑地址转换成内存空间的物理地址。

### 4.动态重定位

需要访问的程序数据的逻辑地址动态转换成实际的物理地址，通过重定位寄存器，记录安装程序时所在内存中的首地址，程序执行时通过将相对地址和重定位寄存器中的地址计算，实现动态重定位。

### 5.内存扩充

逻辑上扩充内存容量，实现原理是划取实际内存中的一部分内存，作为映射表，将本需要存在内存中的数据通过映射表存入实际硬盘中，通过映射表中的相对地址去寻找实际的物理地址。





# 设备管理

### 1.缓冲管理

CPU速度非常快，但是IO读写相对缓慢，所以引入缓冲区机制能够有效缓解CPU高速性和IO低速性之间的矛盾。

### 2.设备管理

设置设备控制表，控制器控制表等数据结构，目的获取指定设备当前状态，是否可用，忙绿，进而解决协调进程之间调用冲突。

### 3.设备处理程序

处理CPU和设备管理器之间的通信，通过CPU向设备控制器发送IO命令，设备控制器调用IO设备进行指定的读写操作。





# 文件管理

### 1.文件存储空间管理

文件系统对资源的存储空间实施统一的管理，每个资源文件分配必要的外存空间，提高外存的利用率和文件系统的执行速度。

### 2.目录管理

文件资源的索引，建立目录以及文件对应的路径关系，方便用户查阅资源文件。

### 3.文件读写管理保护

防止未经批准的用户存取文件，不正当行为修改使用文件的行为。





# 进程与线程

对于操作系统而言，一个任务就是一个进程（process），打开电脑记事本就是启动一个记事本进程，进程中的子任务成为线程，事本中的拼写检查是进程启动后建立出来的线程，线程辅助进程运行。

### 1.进程

进程是程序执行的一个实例，进程是操作系统进行资源调度分配的单位，每一个进程拥有独立的地址空间，`进程=程序+数据+PCB`，其中PCB是**进程控制块**保存进程运行时的上下文，PCB是进程存在的唯一标志，进程之间无法直接访问，需要通过管道，文件，套接字等技术才可以实现通讯。

### 2.进程状态

进程的基本五种状态改变


1. 创建状态，进程正在被创建，尚未转到就绪状态，创建过程中需要申请一个空白的PCB并写入一个控制和管理进程的信息，等待系统分配资源，进程进入就绪状态；
2. 就绪状态，进程准备执行的状态，已经获取CPU之外的所有资源，处于进程队列中准备被CPU调度；
3. 执行状态，进程正在被CPU调度执行，如果是单处理机环境下，同一个时刻仅可以执行同一个进程；
4. 阻塞状态，进程中由于调用IO操作导致等待某一个事件而暂停运行，此时进入阻塞状态，IO操作完成后进入就绪状态队列等待被CPU调度；
5. 结束状态，进程开始被销毁消失，正常执行完成和异常中断均可以导致进程被销毁，进程准备销毁时必须处于结束状态，随后操作系统进行处理资源释放和回收等操作；

值得注意的是后备队里存在于外存中，而就绪状态的进程存在于内存中，方便高效地被调度。

### 3.进程同步与互斥

PV操作是实现PV操作是一种实现，PV操作与信号量的处理相关，P代表通过，V代表释放，PV操作操作信号量S，信号量S大于或者等于零，表示可以被进行调用的资源实体数，信号量S小于零时，表示正在等待资源的进程数，所以信号量S是代表资源数。

##### <u>P操作</u>

```javascript
S减1（占用一个资源数）
if（S减1 >= 0）{
// 程序继续执行
}else {
// 该进程进入阻塞队列中等待被调度
}
```

##### <u>V操作</u>

```javascript
S加1（释放一个资源数）
if（S加1 > 0）{
// 代表存在可以使用的资源，该进程继续执行。
}else {
// 从阻塞等待队列中调用一个进程使用，再继续执行该进行。
}
```

值得注意的是PV操作对于每一个进行而言仅能执行一次且必须成对使用

### 4.进程通信

根据交换信息量的多少和效率的高低，将进程通信分为低级通讯和高级通讯模式。

#### <u>低级通信</u>

仅能传递状态和整数（控制信息），具有传输信息量小，效率低，容量固定的特点，实现通讯难度较大。

#### <u>高级通信</u>

提高信号通信的效率，传递大量数据并减轻编程的复杂度，高级通信分为如下三种方式：

1. 共享内存模式，通信进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行写/读操作，实现进程之间的信息交换。进程对共享空间进行写/读操作时，需要同步互斥工具（ PV操作）；


2. 消息传递模式，消息传递模式中，进程间的数据交换是以格式化的消息(Message)为单位，进程通过系统提供的**发送消息**和**接收消息**两个原语进行数据交换，可以分为直接和间接通信方式；

```javascript
类比：
甲给乙写信
直接：甲直接把信交给乙
间接：甲通过邮差把信交给乙
```

3. 共享文件模式，共享缓冲区（pipe管道）连接一个发送进程和一个接收进程，进程向管道内输入发送信息，信息以字节流的形式通过管道传入其他进程没实现进程通信；


### 5.线程

CPU的执行单元，执行流的最小单元，由线程ID，程序计数器，寄存器和堆栈组成，线程是CPU调度的基本单元。线程拥有**线程控制块TCB**保存运行期间线程的数据，TCB是线程存在的唯一标志，线程有以下几个场景解释：

1. 线程属于进程中的一个实体，线程是CPU独立分配的基本单位；
2. 线程不拥有系统资源，但是可以共享进程中所拥有的其他资源；
3. 进程可以创建和撤销一个线程，同一个进程之间可以存在多个进程并发；

### 6.总结

- 进程是资源分配和调度的一个独立单元，线程是CPU调度的基本单元；
- 一个进程中可以包括多个线程，并且线程共享整个进程的资源，一个进程至少包括一个线程；
- 进程的创建调用fork或者vfork，但是线程的创建调用pthread_create，进程结束将拥有线程都销毁，线程的结束不会影响进程其他线程；
- 线程是轻量级的进程，线程创建和销毁所需要的时间比进程小很多；
- 线程中执行都要进行同步和互斥，线程共享同一进程的所有资源；
- 线程和线程之间的资源不会被共享；





# CPU调度

处理机调度线程有三种方法：

1. 高级调度（作业调度），调度处于外存后备队列的进程进入内存执行；
2. 中级调度（内存调度），展示不能运行的进程移入外存后备队列等待，进程状态改为就绪且驻外状态或者挂机状态；
3. 低级调度（进程调度），根据调度算法将内存中的就绪队列中的进程进行处理；

### 1.调度算法

调度算法是系统根据资源分配策略的规则，有的算法用于作业调度，有的适用于进程调度，同样有的算法都将适用。调度算法的考量`周转时间=等待时间+执行时间`，通过周转时间取决于适用算法。

#### <u>先来先服务(FCFS)</u>

先来先服务调度(First Come First Service)，按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度，适用于作业调度，进程调度，算法简单，对长进程有利，短进程吃亏（骂骂咧咧：我这么短也要等这么久！），不利于IO频繁的进程。

#### <u>短作业优先调度(SJF)</u>

短作业优先调度(Shortest Job First)，算法每次从队列中挑选估计执行时间最短的进程交给CPU处理。适用于作业调度和进程调度，具有平均等待时间和平均周转时间最少的优点，对于长作业不利（骂骂咧咧：什么时候可以轮到我！）不能保证紧迫性作业/进程会被及时处理。

#### <u>优先级调度</u>

优先级调度，算法每次从后备队列/就绪队列中选择优先级最高的一个作业/进程，根据新的更高优先级进程能否抢占正在执行的进程，可以将调度分为：

1. 非抢占式优先级调度算法，当队列中进入优先级更高的进程时，不会中断正在执行的进程，而是等待CPU空闲后再调度优先级较高的进程；
2. 抢占式优先权调度算法，当队列中进入优先级更高的进程时，中断正在执行的进程，抢夺CPU资源；

#### <u>高响应比优先调度(HRRN)</u>

高响应比优先调度(Highest Response Ratio Next)，算法是对FCFS调度算法和SJF调度算法的一种综合平衡，CPU对队列中每个进程计算响应比，响应比高的作业优先执行`响应比=作业周转时间/作业执行时间=(等待时间+要求服务时间)/要求服务时间`，但是调度前要进行计算响应比，增加系统开销。

#### <u>时间片轮转调度</u>

算法将所有就绪进程按到达的先后次序排成一个队列，CPU按队列顺序传递时间片，进程享有同样的调度时间，时间片用完则计时器发出中断请求。

#### <u>多级反馈队列调度</u>

将进程分入不同的就绪队列并设置队列调度优先级，通过不同的队列优先级设置不同的时间片，同一队列中采用先来先服务的调度策略，多级反馈队列中后来的进程不一定最后完成！





# 死锁

多个进程竞争临界资源而造成相互等待的僵局，如果没有外部调节，进程无法继续执行，产生死锁的本质是系统提供的资源个数小于进程需求个数，资源使用造成环路必定造成死锁。

```javascript
A同学有纸
B同学有笔

需要完成写字操作

A同学说：“你不给我笔，我就不能写字！”
B同学说：“你不给我纸，我就不能写字！”

相互不肯让出造成僵局
```

产生死锁的必要条件：

1. 互斥条件，涉及的资源是非共享，一次仅能被一个进程使用；
2. 不剥夺条件，进程不会剥夺其他进程正在使用的非共享资源；
3. 占有等待，进程等待其他资源同时，同时占据已分配的资源；
4. 环路条件，存在一种进程循环链，链中每一个进程已获得的资源同时被链中下一个资源所请求；

### 1.预防死锁

设置进程的限制条件，破坏死锁的一些必要条件，使其不能产生死锁。

### 2.避免死锁

动态分配资源的过程，使用银行家算法防止系统进入不安全状态，避免死锁的发生。新进程进入系统，必须说明各类型资源的的最大需求量，数量不能超过系统各个类的资源总数，如果有一个类型系统不能够提供则进程进行等待状态，简而言之，进程申请者可以在一定时间内无条件归还它申请的全部资源，系统才会把资源分配它。

### 3.死锁的检测和解除

如果发生死锁，可以采取资源剥夺法，撤销法，进程回退法进行解除死锁。





# 主存管理

### 1.分区存储管理

分区存储管理中程序的地址空间时一堆线性的连续地址，分区管理即对存储介质的地址进行分区块进行存储文件资源，分区储存管理中的分配策略有：

1. 首次适应法，程序按地址从小到大排序，分配给第一个符合条件的分区，具有保留高地址部分的大空闲区，有利于大型程序作业分配，但是低地址不断被划分，留下许多难以利用的碎片；
2. 循环首次适应法，从上次查找结束为止开始查找第一个合适的分区进行存储，具有空闲空间分区相对均匀和减少查找时间的优点，但是可能导致缺乏大空间区域；
3. 最佳适应算法，空间从小到大排序进程查找，分配第一个符合条件的分区，具有每次分配都是最合适的空间，但是可能导致难以利用的小空闲区域；
4. 最坏适应算法，地址从大到小排序，匹配第一个符合条件的分区；

### 2.页式存储管理

页式存储管理只用给出一个逻辑地址，页面大小固定，`逻辑地址÷页的大小=页号`且余数等于偏移量，所以地址空间用一个逻辑地址表示，地址映射过程中，若发现所要访问的页面不在内存则产生缺页中断，发送中断时操作系统内存没有空闲空间，通过算法决定淘汰页面，`缺页中断率=成功访问次数/总访问次数`，抖动（颠簸）指页面置换过程中，刚进入页面马上要被淘汰，刚淘汰跳出的页面又进行调入。页时存储管理的调度算法有以下几种：

1. 最佳置换算法，最长时间内不会被访问的页面调出；
2. 先进先出置换算法，最早进入内存的页面调出；
3. 最近最久未使用算法等算法，最近最长时间未访问的页面调出，算法为每个页面设置一个访问字段，记录页面距离上次被访问经历的时间，调出页面时选择时间最长的页面；
4. 最不经常使用置换算法，最近应用次数最少的页淘汰；
5. 时钟置换算法(CLOCK)，算法是为每个页面设置一个使用位（1），页面被调用时使用为设置为0，其他页面调用使用位自加，需要页面替换时，淘汰使用位最高的页面；

### 3.段式存储管理

段式存储管理的用户地址是二维的按段进行划分，段式存储管理必须表明（段号和段内偏移量）。

### 4.段页式存储管理

段式存储管理结构中分别划分成为大小相等的页，段页式存储管理也必须给出（段号和偏移量），虽然段大小不固定，但是段内页号和页内偏移可以根据偏移量算出来。

### 5.虚拟存储器

指具有请求调入功能和置换功能并能从逻辑上对内存容量加以扩充的一种存储器系统，实现原理是**局部性原理**CPU访问存储器，无论存取指令还是存取数据，访问的存储单元都趋于聚集在一个较小的连续区域中，表现形式为如下两大特性：

1. 时间局部性，一个数据被访问，近期很有可能再次被访问；
2. 空间局限性，正在访问一个数据的地址，很有可能与将要访问数据的地址相邻；

通过虚拟存储器技术，系统好像为用户提供一个比实际内存大得多的存储器，称为虚拟存储器，具有一下几个特征：

1. 离散性，指内存分配时采用离散分配的方式；
2. 多次性，进程运行时不是一次性加载全部页面，可分为多次载入；
3. 对换性，作业运行时无序常驻内存，可以调入调出；
4. 虚拟性，逻辑上扩充了内存的容量；





# 文件系统

文件分配对应于文件的物理结构规定为文件分配磁盘块，常用的磁盘空间分配方法有三种：

1. 连续分配，文件在磁盘中占有一块连续的外存地址；
2. 链接分配，采取离散分配的方式；
3. 索引分配，每个文件盘块号集中在一起构成索引块（表）；

### 1.磁盘调度算法

#### <u>先来先服务算法</u>

根据进程请求访问磁盘的先后顺序进行调度

#### <u>最短寻找时间优先算法</u>

选择调用请求文件所处磁道距离当前磁道所在位置最近进程

#### <u>扫描算法(电梯算法SCAN)</u>

磁头当前移动方向上选择与当前磁头所在距离最近的请求作为下一次服务的对象

#### <u>循环扫描算法</u>

SCAN算法的基础上规定磁头单向移动来提供服务，磁头到达磁盘端点返回时，直接快速返回起始端。





# IO设备管理

### 1.程序IO方式

计算机从外部设备读取数据到存储器，每次读取一个字数据，CPU需要对外设状态进行循环检查，直到确定该字已经在I/O控制器的数据寄存器中。

### 2.中断驱动I/O控制方式

允许I/O设备主动打断CPU的运行并请求服务，从而使CPU在对I/O控制器发送命令后可以做其他工作，由于数据中每个字在存储器与I/O控制器之间的传输都必须经过CPU发送指令，消耗CPU较多的时间。

### 3.DMA I/O控制方式

I/O设备和内存之间开辟直接的数据交换通路，数据的基本单位是数据块，传送的数据是从设备直接送入内存。

### 4.IO通道控制方法

只在一组数据的传输开始和结束时需要CPU干预，可以实现CPU，通道，I/O设备三者的并行操作，适用于设备与主机进行数据交换是一组数据块的情况。

### 5.缓冲区

缓冲区(buffer)是内存空间的一部分，缓冲区存储空间用来缓冲输入或输出的数据，解除CPU和IO设备两者的制约关系，IO输入数据进入缓冲区时，CPU可以进行其他操作不必进行等待，引入缓冲区的目的有以下几点：

- 缓和CPU与I/O设备间速度不匹配的矛盾；
- 减少对CPU的中断频率，放宽对CPU中断响应时间的限制；
- 解决基本数据单元大小（即 数据粒度）不匹配的问题；
- 提高CPU和I/O设备之间的并行性；

### 6.缓存（cache）和buffer的区别

CPU的Cache即高速缓冲存储器，读写速度极快，几乎接近CPU，缓和内存和CPU之间速度不匹配的问题，buffer用于缓冲写入数据时CPU和IO设备速度不匹配。