操作系统 - 掘金

概述

基本特征

并发：在一段时间内能同时运行多个程序。并行指同一时刻能运行多个指令。并行需要硬件支持。
共享：系统中的资源可以被多个并发进程共同使用。分为互斥共享和同时共享。互斥共享的资源成为临界资源。需要使用同步机制实现对临界资源的访问。
虚拟：把一个屋里实体转换为多个逻辑实体。多进程并发使用时分复用技术，虚拟内存使用空分复用技术。
异步：进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进

基本功能

进程管理：进程控制、进程同步、进程通信、死锁处理、处理机调度
内存管理：内存分配、地址映射、内存保护与共享、虚拟内存
文件管理：文件存储空间的管理、目录管理、文件读写管理和保护
设备管理：缓冲管理、设备分配、设备处理、虚拟设备

系统调用 如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。

中断分类

外中断：由CPU执行指令以外的事件殷勤，如I/O完成中断
异常：由CPU执行指令的内部事件引起，如越界
陷入：在用户程序中使用系统调用

进程管理

进程与线程

进程是资源分配的基本单位。进程控制块PCB描述进程的基本信息和运行状态。

线程是独立调度的基本单位。一个进程中可以有多个线程，它们共享进程资源。

比较：

拥有资源：进程是资源分配的基本单位，线程不拥有资源，线程可以访问隶属进程的资源。
调度：线程是独立调度的基本单位。同一进程中，线程的切换不会引起进程切换。
系统开销：创建或撤销进程，系统要为之分配或回收资源，开销大。进程切换时，设计当前线程CPU环境的保存以及新调度进程CPU环境的设置。线程切换时只需要保存和设置少量寄存器内容，开销小。
线程可以直接读写同一进程数据进行通信，进程通信需要借助IPC。

进程状态图

运行态：进程在CPU上运行
就绪态：等待被调度，叶集进程获得了除CPU之外的一切所需资源。
阻塞态：进程等待除CPU之外的资源或等待某一事件而暂停进行，即使CPU空闲也不能运行。

进程调度算法

批处理系统：目标是保证吞吐量和周转时间

先来先服务：按照请求的顺序进行调度，利于长作业不利于短作业
最短作业优先：按估计运行时间最短的顺序调度，长作业可能会饿死
最短剩余时间有限：按估计生于时间最短的顺序调度

交互式系统：有大量的用户交互操作，目标是快速进行响应

时间片轮转：就绪进程按 FCFS 原则排成一个队列，每次调度时，把CPU时间分配给队列首进程，时间片用完，中断并将该进程送往就绪队列末尾。
优先级调度：为每个进程分配一个优先级，按照优先级进行调度。防止低优先级的进程得不到调度，随着时间推移增加等待进程优先级。
多级反馈队列：时间片轮转和优先级调度的结合。

进程同步

进程同步是用于控制多个进程按照一定顺序执行

临界区：对临界资源进行访问的代码称为临界区。为了互斥访问临界资源，在进入临界区之前，需要先进行检查。

同步：多个进程按照一定顺序执行

互斥：多个进程同一时刻只有一个进程能进入临界区。

信号量：整形变量，也就是PV操作。如果信号量只能取0或者1，就成为互斥量，0表示临界区加锁，1表示临界区解锁。

进程同步的几种机制

信号量

PV 操作由P原语和V原语组成。 P(S):将信号量S的值减去1；如果S > 0，则进程继续执行；否则该进程置为等待状态，排入等待队列。 V(S)：将信号量S的值加1；如果S > 0,继续执行，否则释放队列中第一个等待信号量的进程。

管程

将共享变量和对它们的操作几种在一个模块中，并发程序就由这样的模块构成。

生产者消费者问题

使用信号量：使用 empty 和 full 分别记录缓冲区为空或者满的数量，使用 mutex 控制对缓冲区的互斥访问。在生产或消费之前，先判断是否为满或空，如果满或空，则进入睡眠等待；否则加锁进行生产或者消费。

读写者问题

允许多个进程同时读，但是不允许读写或写写同时发生。使用 count 记录读操作的进程数量，一个互斥量 countMutex 对 count 加锁，一个互斥量 data_mutex 对读写的数据加锁。

哲学家进餐问题

为了防止死锁：可以设置条件：

必须同时拿起左右两根筷子
只有两个邻居都不进餐的情况下允许进餐。

进程通信

管道：

普通管道：只支持半双工通信，只能在父子进程中使用
命名管道：通常用于客户端进程和服务器进程之间传递数据，去除了只能在父子进程使用的限制

系统IPC

消息队列：独立于读写进程；避免了FIFO的同步阻塞问题，不需要进程自己提供同步；读进程可以有选择的接收
信号量：用于为多个进程提供对共享数据对象的访问
共享存储：允许多个进程共享一个给定的存储区，不需要数据复制，需要使用信号量进行同步

SOCKET（套接字）：可以用于不同机器间的进程通信。

死锁

在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲就是两个或多个进程无限期的阻塞、相互等待的一种状态。

必要条件

互斥：每个资源要么已经分配给了一个进程，要么就是可用的
占有和等待：已经得到了某个资源的进程可以再请求新的资源
不可抢占：已经分配给一个进程的资源不能强制性的被抢占，它只能被占有它的进程显式地释放
循环等待：有两个或者两个以上的进程组成一条环路，每一个进程都在等待下一个进程所占有的资源

处理方法

鸵鸟策略

解决死锁问题的代价很高，如果发生死锁不会对用户造成多大影响，或者发生死锁概率很低，可以采用鸵鸟策略。

死锁检测与死锁恢复

不试图阻止死锁，当检测到死锁发生时，采取措施进行恢复。

死锁恢复：利用抢占恢复；利用回滚恢复；通过杀死进程恢复

死锁预防

在程序运行之前预防发生死锁，破坏四个必要条件任意一个即可。

死锁避免

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

银行家算法：

查找右边的矩阵是否存在一行小于等于A，如果不存在则会发生死锁，状态不安全
如果存在，则将该进程终止，将其资源加到A中
重复直到所有进程都终止，确认安全

内存管理

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

内存连续分配

在程序装入内存时，根据进程的大小动态建立分区，并使得分区的大小正好适合进程的需要，因此系统中分区的大小和数据是可变的。

首次适应算法：空闲分析以地址递增次序连接，分配时顺序查找，找到大小能满足要求的第一个分区。
最佳适应算法：空闲分区以容量递增形成分区链，找到第一个能满足要求的空闲分区。
最坏适应算法：空闲分区以容量递减次序链接，找到第一个也即最大的空闲分区。

分页存储管理方式

把主存空间划分成大小相等且固定的块，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

页表存储在内存中，用来记录逻辑地址和实际存储地址之间的映射关系，以实现从页号到物理块号的映射。访问分页系统中内存数据需要两次内存访问。首先从内存中访问页表，从中找到指定的物理块号，加上页内偏移得到实际物理地址；然后根据第一次得到的物理地址访问内存取出数据。

如果内存的逻辑地址很大，页表项很多，需要较大的连续内存空间。可以采用多级页表的方法，外层页表一次性调入内存连续存放，内存页表离散存放。

分段存储管理方式

分页是为了提高内存利用率，分段是为了满足程序员编写代码的逻辑需求。分段内存管理中，地址是二维的，一维是段号，一维是段内地址；其中每个段的长度不一样，而且每个段内部都是从0开始编址。

分段管理中，每个段内部是来喜怒内存分配，段和段之间是离散分配的，段表用来保存逻辑地址到物理地址的映射关系。

访问内存时首先根据段号和段表项的长度计算当前访问段在段表中的位置，然后访问段表，得到该段的物理地址，根据该物理地址以及段内偏移量就可以得到需要访问的内存。

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分页和分段比较

段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。
分页是一维地址空间，分段是二维
段的大小不固定，由它所完成的功能决定；页大大小固定，由系统决定
分页用于实现虚拟内存，获得更大地址空间；分段是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

页面置换算法

程序运行过程中，如果要访问的页面不在内存中，发生缺页中断从而将该页调入内存中。此时如果内存已经没有空闲空间，系统必须从内存调出一个页面到磁盘中来腾出空间。

页面置换算法的主要目标是使页面置换频率最低。

OPT

所选择的被换出的页面将是最长时间内不被访问的页面。这是一种理论上的算法，因为无法得知一个页面多长时间不被访问。

LRU 最近最久未使用

LRU将最近最久未使用的页面换出。需要在内存中维护一个所有页面的链表，当页面被访问时，将其移动到链表表头。因为每次访问都需要更新链表，代价高。

FIFO 先进先出

选择换出的页面是最先进入的页面，该算法将那些经常被访问的页面也被换出，缺页率升高。

NRU 最近未使用，时钟算法

页面设置一个访问位，并将页面链接为一个环形队列，页面被访问的时候访问位设置为1。页面置换的时候，如果当前指针所指页面访问为为0，那么置换，否则将其置为0，循环直到遇到一个访问为位0的页面。

磁盘调度算法

读写磁盘块的时间的影响因素主要有旋转时间、寻道时间、数据传输时间。其中寻道时间最长。

FCFS 先来先服务
SSTF 最短寻到时间优先。优先调度与当前磁头所在磁道最近的磁道。可能存在饥饿
SCAN 电梯算法。保持一个方向运行直到没有请求，然后掉头。

Linux 相关

文件类型

普通文件
目录文件（/root）
链接文件：用于不同目录下的文件的共享（快捷方式）
设备文件：用来访问硬件设备
命名管道（FIFO）：特殊类型的文件，用于进程通信

常见目录

/bin: 二进制可执行文件
/etc: 系统管理和配置文件
/home: 用户文件
/usr: 系统应用程序
/proc: 系统内存映射，虚拟文件系统目录
/root: 超级用户的主目录
/dev: 设备文件
/var: 运行时需要改变数据的文件（如日志）

常见命令

目录切换

目录操作

mkdir dirname 创建目录
ls , ll 查看目录信息
find 目录参数 在目录下查找满足的文件
mv 目录名新目录名 修改目录名
mv 目录名新位置 移动
cp -r 目录名目标位置 拷贝目录（-r 递归拷贝）
rm -rf 目录名 删除

文件操作

touch 文件名 新建文件
cat 文件名 查看文件内容
more 文件名 查看，可以显示百分比，回车可以向下一行，空格可以向下一页，q可以退出查看