[toc]

引用来源

操作系统

操作系统概述

  • 无操作系统：人工操作，用户独占，CPU等待人工操作，资源利用率很低。
  • 批处理系统：批量输入任务，无需等待人工操作，资源利用率提升，提出多道程序设计。
  • 分时系统：人-机交互，多用户共享，资源利用率提升，及时调试程序。
  • 关于多道程序设计：是指在计算机内存中同时存放多个程序，多道程序在计算机的管理程序之下相互穿插运行。

操作系统的定义与目标
  定义：管理硬件，提供用户交互的软件系统。
  目标：方便性，有效性（提高系统资源的利用率、提高系统的吞吐量），可扩充性，开放性。

操作系统的基本功能

统一管理计算机资源：处理器资源，IO设备资源，存储器资源，文件资源…
  实现了对计算机资源的抽象：IO设备管理软件提供读写接口，文件管理软件提供操作文件接口…
  提供了用户与计算机之间的接口：图像窗口形式，命令形式，系统调用形式…

中断的分类：

  • 内中断（也叫“异常”、“例外”、“陷入”）------- 信号来源：CPU内部，与当前执行指令有关；
  • 外中断（中断）----------信号来源：CPU外部，与当前执行指令无关。

外中断的处理过程：

  1. 每执行完一个指令后，CPU都需要检查当前是否有外部中断信号；
  2. 如果检查到外部中断信号，则需要保护被中断进程的CPU环境（如程序状态字PSW，程序计数器PC、各种通用寄存器）把他们存储在PCB（进程控制块中）；
  3. 根据中断信号类型转入相应的中断处理程序；
  4. 恢复原进程的CPU环境并退出中断，返回原进程继续执行。

操作系统的基本特性

a.并发性
   并行：指两个或多个事件可以在同一个时刻发生；
   并发：指两个或多个事件可以在同一个时间间隔发生。

b.共享性：操作系统的中资源可供多个并发的程序共同使用，这种形式称之为资源共享。
   互斥共享：当资源被程序占用时，其它想使用的程序只能等待。
   同时访问：某种资源并发的被多个程序访问。

c.虚拟性：表现为把一个物理实体转变为若干个逻辑实体。
   时分复用技术：资源在时间上进行复用，不同程序并发使用，多道程序分时使用计算机的硬件资源，提高资源的利用率。
   空分复用技术：用来实现虚拟磁盘（物理磁盘虚拟为逻辑磁盘，电脑上的C盘、D盘等）、虚拟内存（在逻辑上扩大程序的存储容量）等，提高资源的利用率，提高编程效率。
  d.异步性：在多道程序环境下，允许多个进程并发执行，但由于资源等因素的限制，使进程的执行以“停停走走”的方式运行，而且每个进程执行的情况（运行、暂停、速度、完成）也是未知的。

  • 并发

  • 共享

  • 异步

  • 虚拟

进程管理

进程实体
  a.为什么需要进程：
   ·进程是系统进行资源分配和调度的基本单位；
   ·进程作为程序独立运行的载体保障程序正常执行；
   ·进程的存在使得操作系统资源的利用率大幅提升。
  b.进程控制块（PCB）：用于描述和控制进程运行的通用数据结构,记录进程当前状态和控制进程运行的全部信息,是进程存在的唯一标识。
  c.进程（Process）与线程（Thread）：
   线程：操作系统进行运行调度的最小单位。
   进程：系统进行资源分配和调度的基本单位。
   区别与联系：一个进程可以有一个或多个线程；线程包含在进程之中，是进程中实际运行工作的单位；进程的线程共享进程资源；一个进程可以并发多个线程，每个线程执行不同的任务。

进程的五状态模型

就绪状态：其它资源（进程控制块、内存、栈空间、堆空间等）都准备好、只差CPU的状态。
  执行状态：进程获得CPU，其程序正在执行。
  阻塞状态：进程因某种原因放弃CPU的状态。
  创建状态：创建进程时拥有PCB但其它资源尚未就绪。
  终止状态：进程结束由系统清理或者归还PCB的状态。

  1. 就绪
  2. 执行
  3. 阻塞
  4. 创建
  5. 终止

进程同步

a.生产者-消费者问题：有一群生产者进程在生产产品，并将这些产品提供给消费者进程进行消费，生产者进程和消费者进程可以并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程需要将所生产的产品放到缓冲区中（+1操作），消费者进程可以从缓冲区取走产品消费（-1操作）。

​ b.哲学家进餐问题：有5个哲学家，他们的生活方式是交替的思考和进餐，哲学家们共同使用一张圆桌，分别坐在5张椅子上，圆桌上有5只碗和5只筷子。平时哲学家们只进行思考，饥饿时则试图取靠近他们的左右两只筷子，只有两只筷子都被拿到的时候才能进餐，否则等待，进餐完毕后，放下左右筷子进行思考。

c.进程同步的作用：对竞争资源在多进程间进行使用次序的协调，使得并发执行的多个进程之间可以有效使用资源和相互合作。
  d.进程间同步的四原则：
   空闲让进：资源无占用，允许使用；
   忙则等待：资源被占用，请求进程等待；
   有限等待：保证有限等待时间能够使用资源；
   让权等待：等待时，进程需要让出CPU。
  e.进程同步的方法（重要，后面详细讲解）：消息队列，共享存储，信号量。
  f.线程同步的方法（重要，后面详细讲解）：互斥量，读写锁，自旋锁，条件变量。

作业管理

进程调度
  定义：指计算机通过决策决定哪个就绪进程可以获得CPU使用权。
  方法：
   非抢占式调度：处理器一旦分配给某个进程，就让该进程一直使用下去，直到进程完成工作或IO阻塞才会让出处理器。
   抢占式调度：允许调度程序以一定的策略暂停当前运行地进程。

步骤：
   保留旧进程的运行信息，请出旧进程（收拾包袱）；
   选择新进程，准备运行环境并分配CPU。

a.三个重要的机制：
   就绪队列的排队机制：为了提高进程调度的效率，将就绪进程按照一定的方式排成队列，以便调度程序可以最快找到就绪进程。
   选择运行进程的委派机制：调度程序以一定的策略，选择就绪进程，将CPU资源分配给它。
   新老进程的上下文切换机制：保存当前进程的上下文信息，装入被委派执行进程的运行上下文。
  b.进程调度算法
   先来先服务算法：按照在就绪队列中的先后顺序执行。
   短进程优先调度算法：优先选择就绪队列中估计运行时间最短的进程，不利于长作业进程的执行。
   高优先权优先调度算法：进程附带优先权，优先选择权重高的进程，可以使得紧迫的任务优先处理。
   时间片轮转调度算法：按照FIFO的原则排列就绪进程，每次从队列头部取出待执行进程，分配一个时间片执行，是相对公平的调度算法，但是不能保证就是响应用户。
 2.死锁：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。 此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
  a.死锁的产生：竞争资源（共享资源数量不满足各进程需求）、进程调度顺序不当.

死锁的四个必要条件：
   互斥条件：进程对资源的使用是排他性使用，某资源只能由一个进程使用，其它进程需要使用只能等待。
   请求保持条件：进程至少保持一个资源，又提出新的资源请求，新资源被占用，请求被阻塞，被阻塞的进程不释放自己保持的资源。
   不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺（包括OS），只能由进程自身释放。
   环路等待条件：发生死锁时，必然存在进程-资源环形链.
  c.死锁的处理
   预防死锁的方法：破坏四个必要条件的中一个或多个。
    破坏请求保持条件：系统规定进程运行之前，一次性申请所有需要的资源。
    破坏不可剥夺条件：当一个进程请求新的资源得不到满足时，必须释放占有的资源。
    破坏环路等待条件：可用资源线性排序，申请必须按照需要递增申请。
  银行家算法：客户申请的贷款是有限的，每次申请需要申明最大资金量，银行家在能够满足贷款时，都应该给用户贷款，客户在使用贷款后，能够及时归还贷款。

存储管理

内存分配与回收
  内存分配的过程：单一连续分配、固定分区分配、动态分区分配（根据实际需要，动态的分配内存）。
  动态分区分配算法：
   首次适应算法：分配内存时，从开始顺序查找适合内存区，若无合适内存区，则分配失败。
   最佳适应算法：要求空闲区链表按照容量大小排序，遍历以找到最佳适合的空闲区。
   快速适应算法：要求有多个空闲区链表，每个空闲区链表存储一种容量的空闲区。
  内存回收的过程：

2.段页式存储管理
  页式存储管理：将进程逻辑空间等分成若干大小的页面，相应的把物理内存空间分成与页面大小的物理块，以页面为单位把进程空间装进物理内存中分散的物理块。
  段式存储管理：将进程逻辑空间分成若干段（不等分），段的长度由连续逻辑的长度决定。
  两者相比：

段页式存储管理：现将逻辑空间按照段式管理分成若干段，再将内存空间按照页式管理分成若干页，分页可以有效提高内存利用率，分段可以更好的满足用户需求。

三者分配内存之后的对比：

3.虚拟内存
  概述：实际是对物理内存的扩充，速度接近于内存，成本接近于辅存。
  局部性原理：指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。
  虚拟内存的置换算法：先进先出（FIFO）、最不经常使用（LFU）、最近最少使用（LRU）
 4.Linux的存储管理
  Buddy内存管理算法：为解决内存外碎片的问题，算法基于计算机处理二进制的优势具有极高的效率。
  Linux交换空间：交换空间（Swap)是磁盘的一个分区，Linux内存满时，会把一些内存交换至Swap空间，Swap空间是初始化系统时配置的。
  Swap空间与虚拟内存的对比：

文件管理

1.文件管理概述
  a.文件的逻辑结构：
   逻辑结构的文件类型：有结构文件（文本文件，文档，媒体文件）、无结构文件（二进制文件、链接库）。
   顺序文件：按顺序放在存储介质中的文件，在逻辑文件当中存储效率最高，但不适合存储可变长文件。
   索引文件：为解决可变长文件存储而发明，需要配合索引表存储。
  b.辅存的存储空间分配：
   辅存的分配方式：连续分配（读取文件容易，速度快）、链接分配（隐式链接和显式链接）、索引分配
   辅存的存储空间管理：
  c.目录管理：
   目录树：使得任何文件或目录都有唯一的路径。
 2.Linux文件的基本操作
  a.Linux目录：Linux一切皆文件。

设备管理

1.广义的IO设备：
   按照使用特性分类：存储设备（内存、磁盘、U盘）和交互IO设备（键盘、显示器、鼠标）
   按照信息交换分类：块设备（磁盘、SD卡）和字符设备（打印机、shell终端）
   按照设备共享属性分类：独占设备，共享设备，虚拟设备
   按照传输速率分类：低速设备，高速设备
  2.IO设备的缓冲区：减少CPU处理IO请求的频率，提高CPU与IO设备之间的并行性。
  3.SPOOLing技术：虚拟设备技术，利用高速共享设备将低速的独享设备模拟为高速的共享设备，逻辑上，系统为每一个用户都分配了一台独立的高速独享设备。

线程同步的方法

1.互斥锁
  互斥锁是最简单的线程同步的方法，也称为互斥量，处于两态之一的变量：解锁和加锁，两个状态可以保证资源访问的串行。

原子性：指一系列操作不可被中断的特性，要么全部执行完成，要么全部没有执行。

​ 2.自旋锁
  自旋锁是一种多线程同步的变量，使用自旋锁的线程会反复检查锁变量是否可用，自旋锁不会让出CPU，是一种忙等待状态，即死循环等待锁被释放。
  特点：避免了进程或者线程上下文切换的开销，但是不适合在单核CPU使用。

3.读写锁
  是一种特殊的自旋锁，允许多个读操作同时访问资源以提高读性能，但是对写操作是互斥的，即对多读少写的操作效率提升很显著。

4.条件变量
  是一种相对比较复杂的线程同步方法，条件变量允许线程睡眠，直到满足某种条件，当满足条件时，可以给该线程信号通知唤醒。
  例如，在生产者-消费者问题当中，规定当缓冲区小于等于时，不允许消费者消费，消费者必须等待；缓冲区满时，不允许生产者往缓冲区生产，生产者必须等待；即当生产者生产一个产品时，唤醒可能等待的消费者，当消费者消费一个产品时，唤醒可能等待的生产者。

进程同步

1.使用fork系统调用创建进程
  使用fork系统调用无参数，fork会返回两次，分别返回子进程id和0，返回子进程id的是父进程，返回0的是子进程。

2.共享内存
  在某种程度上，多进程是共同使用物理内存的，但是由于操作系统的进程管理，进程间的内存空间是独立的，因此进程默认是不能访问进程空间之外的内存空间的。
  共享存储允许不相关的进程访问同一片物理内存，共享内存是两个进程之间共享和传递数据最快的方式，但是共享内存未提供同步机制，所以需要借助其它机制管理访问。即共享内存是高性能后台开发中最常用的进程同步方式。
 3.Unix域套接字
  域套接字是一种高级的进程间通信的方法，可以用于同一机器进程间通信。
  套接字（socket）：为网络通信中使用的术语。
  Unix系统提供的域套接字提供了网络套接字类似的功能，如Nfinx、uWSGI等。
  服务端和客户端分别使用Unix域套接字的过程：

线程池

线程池：线程池是存放多个线程的容器，CPU调度线程执行后不会销毁线程，将线程放回线程池重新利用。

使用线程池的原因：
  1.线程是稀缺资源 ，不应该频繁创建和销毁；
  2.架构解耦，业务创建和业务处理解耦，更加优雅；
  3.线程池是使用线程的最佳实践。

1.实现线程安全的队列Queue
 队列：用于存放多个元素，是存放各种元素的“池”。
 实现的基本功能：获取当前队列元素数量，往队列放入元素，往队列取出元素。
 注意：队列可能有多个线程同时操作，因此需要保证线程安全，如下两种情况：

实现基本任务对象Task
 任务处理逻辑：
  实现的基本功能：任务参数，任务唯一标记（UUID），任务具体的执行逻辑

实现任务处理线程ProcessThread
 任务处理线程需要不断地从任务队列里取任务执行，任务处理线程需要有一个标记，标记线程什么时候应该停止。
 实现的基本功能：基本属性（任务队列、标记），线程执行的逻辑（run），线程停止（stop）。

经典问题

哲学家就餐

  • 5 个⽼⼤哥哲学家，闲着没事做，围绕着⼀张圆桌吃⾯；
  • 巧就巧在，这个桌⼦只有 5 ⽀叉⼦，每两个哲学家之间放⼀⽀叉⼦；
  • 哲学家围在⼀起先思考，思考中途饿了就会想进餐；
  • 吃完后，会把两⽀叉⼦放回原处，继续思考；

让偶数编号的哲学家「先拿左边的叉⼦后拿右边的叉⼦」，奇数编号的哲学家「先拿右边的叉⼦后拿左
边的叉⼦

另外⼀种可⾏的解决⽅案，我们⽤⼀个数组 state 来记录每⼀位哲学家在进程、思考还是饥
饿状态（正在试图拿叉⼦）。

那么，⼀个哲学家只有在两个邻居都没有进餐时，才可以进⼊进餐状态。
第 i 个哲学家的左邻右舍，则由宏 LEFT 和 RIGHT 定义：
LEFT : ( i + 5 - 1 ) % 5
RIGHT : ( i + 1 ) % 5
⽐如 i 为 2，则 LEFT 为 1， RIGHT 为 3。

读者-写者问题

它为数据库访问建⽴了⼀个模型。 读者只会读取数据，不会修改数据，⽽写者即可以读也可以修改数据。 读者-写者的问题描述：

  • 「读-读」允许：同⼀时刻，允许多个读者同时读
  • 「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
  • 「写-写」互斥：没有其他写者时，写者才能写

方案1

使⽤信号量的⽅式来尝试解决：

  • 信号量 wMutex ：控制写操作的互斥信号量，初始值为 1 ；
  • 读者计数 rCount ：正在进⾏读操作的读者个数，初始化为 0；
  • 信号量 rCountMutex ：控制对 rCount 读者计数器的互斥修改，初始值为 1；

上⾯的这种实现，是读者优先的策略，因为只要有读者正在读的状态，后来的读者都可以直接进⼊，如果 读者持续不断进⼊，则写者会处于饥饿状态。

⽅案⼆

那既然有读者优先策略，⾃然也有写者优先策略：

  • 只要有写者准备要写⼊，写者应尽快执⾏写操作，后来的读者就必须阻塞；

  • 如果有写者持续不断写⼊，则读者就处于饥饿；

    在⽅案⼀的基础上新增如下变量：

    • 信号量 rMutex ：控制读者进⼊的互斥信号量，初始值为 1；
    • 信号量 wDataMutex ：控制写者写操作的互斥信号量，初始值为 1；
    • 写者计数 wCount ：记录写者数量，初始值为 0；
    • 信号量 wCountMutex ：控制 wCount 互斥修改，初始值为 1；

公平的策略

公平策略：

  • 优先级相同；
  • 写者、读者互斥访问；
  • 只能⼀个写者访问临界区；
  • 可以有多个读者同时访问临界资源；

对⽐⽅案⼀的读者优先策略，可以发现，读者优先中只要后续有读者到达，读者就可以进⼊读者队列， ⽽ 写者必须等待，直到没有读者到达。 没有读者到达会导致读者队列为空，即 rCount==0 ，此时写者才可以进⼊临界区执⾏写操作。

⽽这⾥ flag 的作⽤就是阻⽌读者的这种特殊权限（特殊权限是只要读者到达，就可以进⼊读者队列）。 ⽐如：开始来了⼀些读者读数据，它们全部进⼊读者队列，此时来了⼀个写者，执⾏ P(falg) 操作，使得 后续到来的读者都阻塞在 flag 上，不能进⼊读者队列，这会使得读者队列逐渐为空，即 rCount 减为 0。 这个写者也不能⽴⻢开始写（因为此时读者队列不为空），会阻塞在信号量 wDataMutex 上，读者队列 中的读者全部读取结束后，最后⼀个读者进程执⾏ V(wDataMutex) ，唤醒刚才的写者，写者则继续开始 进⾏写操作。