# 目录

  * [CPU](#cpu)
    * [程序执行过程](#程序执行过程)
    * [高速缓存 读写缓冲区](#高速缓存-读写缓冲区)
  * [内存管理和虚拟内存](#内存管理和虚拟内存)
    * [分页](#分页)
    * [虚拟内存](#虚拟内存)
    * [页表和页面置换算法](#页表和页面置换算法)
    * [中断和缺页中断](#中断和缺页中断)
    * [分页和分段](#分页和分段)
  * [进程与线程](#进程与线程)
    * [进程](#进程)
    * [多进程](#多进程)
    * [线程](#线程)
    * [多线程](#多线程)
    * [线程通信和进程通信](#线程通信和进程通信)
    * [进程调度](#进程调度)
    * [死锁](#死锁)
  * [IO和磁盘](#io和磁盘)
    * [磁盘和寻址](#磁盘和寻址)
    * [IO设备](#io设备)
    * [文件系统](#文件系统)



---
title: 操作系统学习总结
date: 2018-07-09 22:33:03
tags:
	- 操作系统
categories:
	- 后端
	- 技术总结
---
这部分内容主要是基于一些关于操作系统基础的学习总结，内容不全面，只讲述了其中的一小部分，后续会再补充，如有错误，还请见谅。
操作系统
<!-- more -->


## CPU
cpu是中央处理器，他是计算机的核心。
cpu通过和寄存器，高速缓存，以及内存交互来执行程序。

主板分为南桥和北桥，北桥主要是内存总线，通往内存。
而南桥主要是慢速设备的IO总线，包括硬盘，网卡等IO设备。

32位cpu最多寻址4g内存，而64位cpu目前来说没有上限。

### 程序执行过程
cpu发出指令，将硬盘上的一段程序读入内存，由于cpu和硬盘的速度差距更大，一般使用中断，dma等方式来将硬盘数据载入内存。
然后cpu通过寄存器以及指令集执行指令，cpu读取内存上的代码，内存上的方法执行是一个栈调用的过程。

### 高速缓存 读写缓冲区
为了弥补cpu和内存的速度差，cpu配有多级缓存。

一般有一级缓存和二级缓存，缓存根据局部性原理把经常使用的代码加载如缓存，能比直接访问内存快上几百倍。

同样的，内存和硬盘间的速度差距也很大，需要通过读写缓冲区来进行速度匹配，内存写入磁盘时先写入缓冲区，读数据时从缓冲区读取硬盘准备好的数据。


## 内存管理和虚拟内存

由于程序的大小越来越大，而计算机想要支持多道程序，当一个程序遇到IO操作时转而去执行另一个程序，这就要求内存中装有多个程序的代码了。

然而程序的内存消耗与日俱增，同时装载多个程序越来越困难，所以人们提出了，只在程序需要使用到的时候再把他装入内存，平时把代码放在硬盘中即可。

### 分页

由于内存需要装载硬盘中的数据，所以需要约定一个存储单元，操作系统把它叫做页，一个页一般长度是8kb或者16kb。内存从硬盘读取数据时读取的是一个页或多个页。

### 虚拟内存


由于这些代码持久化在硬盘中，占用了一部分空间，并且需要运行时会加载到内存中，所以这部分的空间一般也成为虚拟内存的空间（大小）。

### 页表和页面置换算法

为了知道每个程序对应的代码存在硬盘中的位置，操作系统需要维护一个程序到页面的映射表，cpu要内存加载一个页面时，首先要访问页表，来得知页面在硬盘中的位置，然后让内存去该位置把对应的页面调入内存中。

为了提升页面调入的效率，也使用了多种的页面置换算法，比如lru最近最久未使用，fifo先进先出，时钟法，多级队列法等。

当然，为了进一步提高效率，还会使用多级页表的方式，不过一般需要硬件维护一个页表映射页面的快速转换结构，以便能迅速地完成页面解析和调度。

### 中断和缺页中断

计算机提供一系列中断指令与硬件进行交互，操作系统可以使用这些中断去控制硬件，比如使用中断通知cpu硬盘的IO操作已经准备好，键盘通过一次又一次的中断来输入字符。

中断一般适用于快速返回的字符设备，比如鼠标键盘，而硬盘这类耗时IO操作，使用中断后cpu仍然需要等待硬盘把数据装入内存。是非常缓慢的。

于是才会使用DMA来完成IO操作，DMA额外提供一个处理器去处理IO操作，当硬盘数据加载到内存中后再去通知CPU操作已完成。

    缺页中断就是因为内存中没有cpu需要访问的页面，必须根据页表到硬盘中获取页面，并根据置换算法进行页面调度。如果找不到对应页面，则程序执行会报错。

### 分页和分段

分页是上述所说的，通过内存和硬盘的约定，将调度单元设定为一个页面。

    分段则不同，分段并不是物理意义上的分段，而是逻辑上把代码使用到的空间划分成多个部分，比如受保护部分，公开部分，核心部分等，这样可以更好地描述每个段的代码信息，为使用者提供便利，为了支持程序员的这种需求，操作系统加入了分段的概念，将代码对应的一段虚拟内存划分为不同的逻辑段。
    
    同时为了根据不同段来以不同方式访问内存，操作系统需要另外维护一个段表，以用于段的映射。

由于分段只是逻辑上的概念，所以底层的内存分页仍然是必不可少的，因此在逻辑段的基础上，物理上又会划分为多个页，一个段中可能包含了多个页面。

因此，完善的虚拟内存管理器需要支持段页表，先映射段，再映射页面。

## 进程与线程

### 进程
进程是资源分配的资本单位，操作系统为进程开辟一段内存空间，内存空间从高位向低位，包括函数调用栈，变量以及其他区域。cpu根据这些信息配合寄存器进行函数调用和程序执行。

### 多进程
由于计算机是分时系统，所以多进程的使用不可避免，操作系统需要进行进程的切换，方法是内存指针指向新位置，保存原来的进程信息，同时刷新寄存器等数据。然后开始执行新的进程.

一般操作系统会使用pcb结构来记录进程的信息和上下文。通过他和cpu配合来完成进程切换。

### 线程
线程是系统调度的基本单位，没有线程以前，一般会使用多进程模型，一个程序往往需要多个进程配合使用，但是多进程之间并没有共享内存，导致进程间通信非常麻烦。

比如文本输入工具，一边键入文字一边需要保存数据，如果是单进程执行，则每次输入都触发IO操作，非常费时，如果一个进程负责输入展示一个进程负责输入保存，确实速度很快，但是两个进程没办法共享数据。除非使用额外的通讯手段。
### 多线程

而多线程就好办了，多线程都是基于进程产生的，线程被创建后只需要分配少量空间支持堆栈操作即可，同时线程还共享进程中的内存，所以一般使用进程分配资源，线程进行调度的方式。

    操作系统对线程的支持：
    一般情况下操作系统都支持线程，并且可以创建内核级线程，内核可以识别线程并且为其分配空间，进行线程调度。
    但是内核级线程实现比较复杂，使用起来也不甚方便。
    
    所以往往开发人员会使用用户级线程，用户级线程比如Java的多线程，通过简单的api实现，当需要操作系统支持时，才使用底层调用api接口进行内核级的系统调用。
    
    但是一般情况下用户级线程是不被内核识别的，也就是说，用户级线程会被内核认为是一个进程，从而执行进程的调度。这样的话就没有意义了。
    
    所以一般情况下用户级线程会映射到对应的内核级线程中，内核为进程创建一定数量的内核级线程以供使用。Java中的线程基本上都是使用这种方式实现的。

### 线程通信和进程通信

线程通信一般只需要使用共享内存的方式即可实现。

而进程通信则需要额外的通信机制。

> 1 信号量，一般多进程间的同步使用信号量来完成，系统为临界区添加支持并发量为n的信号量,多进程访问临界区资源时，首先需要执行p操作来减少信号量，如果信号量等于0则操作失败，并且挂起进程，否则成功进入临界区执行。
> 
> 当进程退出临界区时，执行v操作，将信号量加一，并唤醒挂起的进程进行操作。
> 
> 2 管程，管程是对信号量的一个包装，避免使用信号量时出错。
> 
> 3 管道，直接连接两个进程，一个进程写入管道，另一个进程可以读取管道，但是他不支持全双工，并且只能在父子进程间使用，所以局限性比较大
> 
> 4 消息队列
> 
> 操作系统维护一个消息队列，进程将消息写入队列中，其他进程轮询消息队列看是否有自己的消息，增加了轮询的开销，但是提高了消息的可靠性和易用性，同时支持了订阅消息。
> 
> 5 socket
> 
> socket一般用于不同主机上的进程通信，双方通过ip和port的方式寻址到对方主机并找到监听该端口的进程，为了完成通信，他们先建立tcp连接，在此基础上交换数据，也就完成了进程间的通信。

### 进程调度

不小心把这茬忘了，进程调度算法有几种，fifo先来先服务，短作业优先，时间片轮转，优先级调度，多级反馈队列等。
基本上可以通过名字知道算法的大概实现。

### 死锁

死锁的必要条件：
    
    1互斥：资源必须是互斥的，只能给一个进程使用
    
    2占有和等待：占有资源时可以请求其他资源
    
    3不可抢占：资源占有时不会被抢
    
    4环路等待：有两个以上的进程组成一个环路，每个进程都在等待下一个进程的资源释放。

死锁的处理方法：

1鸵鸟

2死锁预防

在程序运行之前预防发生死锁。

    （一）破坏互斥条件
    
    例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
    
    这样子就破坏了互斥条件，转而使用单个队列串行执行操作。
    
    （二）破坏占有和等待条件
    
    一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
    
    分配了全部资源就不需要去等待其他资源。
    
    （三）破坏不可抢占条件
    
    允许抢占式调度。
    
    （四）破坏环路等待
    
    给资源统一编号，进程只能按编号顺序来请求资源。
    
    按正确顺序请求资源，就不会发生死锁。
3死锁避免

==银行家算法用于在程序运行时避免发生死锁。==

银行家算法用于在程序运行时判断资源的分配情况是否是安全状态，如果某一步骤使程序可能发生死锁，银行家算法会拒绝该操作执行，从而避免进入不安全状态。

（一）安全状态

[![](https://github.com/CyC2018/Interview-Notebook/raw/master/pics/ed523051-608f-4c3f-b343-383e2d194470.png)](https://github.com/CyC2018/Interview-Notebook/blob/master/pics/ed523051-608f-4c3f-b343-383e2d194470.png)

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

（二）单个资源的银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

[![](https://github.com/CyC2018/Interview-Notebook/raw/master/pics/d160ec2e-cfe2-4640-bda7-62f53e58b8c0.png)](https://github.com/CyC2018/Interview-Notebook/blob/master/pics/d160ec2e-cfe2-4640-bda7-62f53e58b8c0.png)

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

4死锁检测和恢复

==银行家算法检测程序并且阻止死锁发生，而死锁检测和恢复则
不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。==

（一）每种类型一个资源的死锁检测

[![](https://github.com/CyC2018/Interview-Notebook/raw/master/pics/b1fa0453-a4b0-4eae-a352-48acca8fff74.png)](https://github.com/CyC2018/Interview-Notebook/blob/master/pics/b1fa0453-a4b0-4eae-a352-48acca8fff74.png)

上图为==资源分配图==，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

如果有环则说明有死锁。

（二）每种类型多个资源的死锁检测

[![](https://github.com/CyC2018/Interview-Notebook/raw/master/pics/e1eda3d5-5ec8-4708-8e25-1a04c5e11f48.png)](https://github.com/CyC2018/Interview-Notebook/blob/master/pics/e1eda3d5-5ec8-4708-8e25-1a04c5e11f48.png)

==资源分配矩阵==
    
上图中，有三个进程四个资源，每个数据代表的含义如下：

*   E 向量：资源总量
*   A 向量：资源剩余量
*   C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
*   R 矩阵：每个进程请求的资源数量

如果存在请求数量无法被满足时，就会出现死锁。

==（三）死锁恢复==

利用抢占恢复，允许其他进程抢占资源。

利用回滚恢复，回滚进程操作，释放其资源。

通过杀死进程恢复，杀死进程后释放资源。

## IO和磁盘

磁盘是块设备，键盘是字符设备，网卡是网络设备。他们都接在IO总线上，属于慢速设备。

### 磁盘和寻址

磁盘的结构比较复杂，主要通过扇区，盘面和磁头位置决定当前访问的磁盘位置。

cpu为了能够访问磁盘内容，首先要把磁盘的内容载入内存中，于是要和内存约定统一的寻址单元，cpu指定一个起始位置，访问该位置以后的n个存储单元，一般存储单元是一个页，16K或者8K。

这一操作中，指向起始位置需要随机寻址，而接下来的访问操作是顺序访问，磁盘的随机读写和顺序读写的速度差距是很大的。所以一般会通过缓冲区来缓存IO数据。

    磁盘内部一般也会分为很多部分，比如操作系统会将磁盘做一个分区，使用磁盘的一些位置存储元数据信息，以保证磁盘能够支持操作系统以及文件系统。
    
    一般在物理分区的起始位置会有一个引导区和分区表,BIOS自动将磁盘中引导区的内核程序载入内存，此时操作系统才开始运行，并且根据分区表操作系统可以知道每个分区的起始位置在哪。

读写一个磁盘块的时间的影响因素有：

旋转时间（主轴旋转磁盘，使得磁头移动到适当的扇区上）
寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
实际的数据传输时间
其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

1. 先来先服务
FCFS, First Come First Served

按照磁盘请求的顺序进行调度。

优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

2. 最短寻道时间优先
SSTF, Shortest Seek Time First

优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两边的磁道请求更容易出现饥饿现象。

3. 电梯算法
SCAN

电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

### IO设备

除了硬盘以外，还有键盘，网卡等IO设备，这些设备需要操作系统通过驱动程序来进行交互，驱动程序用于适配这些设备。

为了执行IO操作，内核一般要为IO设备提供一个缓存区，比如网卡的IO操作，会为socket提供一个缓存区，当多个socket使用一个缓冲区进行通信，就是复用了缓冲区，也就是IO复用的一种方式。

同时，内核还会维护一个IO请求的列表，当IO请求就绪时，让几个线程去执行IO操作，实现了线程的复用。

### 文件系统

文件系统是基于底层存储建立的一个树形文件结构。比较经典的是Linux的文件系统，首先在硬盘的超级块中安装文件系统，磁盘引导时会加载文件系统的信息。

linux使用inode来标识任意一个文件。inode存储除了文件名以外的文件信息，包括创建时间，权限，以及一个指向磁盘存储位置的指针，那里才是真正存放数据的地方。

一个目录也是一个inode节点。

详细阐述一次文件访问的过程：
    
    首先用户ls查看目录。由于一个目录也是一个文件，所以相当于是看目录文件下有哪些东西。
    
    实际上目录文件是一个特殊的inode节点，它不需要存储实际数据，而只是维护一个文件名到inode的映射表。
    
    于是我们ls到另一个目录。同理他也是一个inode。我们在这个inode下执行vi操作打开某个文件，于是linux通过inode中的映射表找到了我们请求访问的文件名对应的inode。
    
    然后寻道到对应的磁盘位置，读取内容到缓冲区，通过系统调用把内容读到内存中，最后进行访问。


