1. 操作系统简介

  1. 操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机系统的内核与基石；
  2. 操作系统本质上是运行在计算机上的软件程序
  3. 操作系统为用户提供一个与系统交互的操作界面
  4. 操作系统分内核与外壳（我们可以把外壳理解成围绕着内核的应用程序，而内核就是能操作硬件的程序）。

2. 进程与线程

1.进程与线程的区别

进程是资源分配的基本单位，创建、撤销进程时系统都要为之分配或回收资源，如内存空间、I/O设备等，所付出的开销大于创建，撤销一个线程所付出的开销。
当进程进行切换时，涉及到CPU环境的保存和新调度进程CPU环境的加载，而线程的切换只涉及到少量寄存器内容，开销较小

2.进程间的通信

管道/匿名管道(pipe)
  • 管道为半双工，若需要双向通信，则需要建立两个管道
  • 只能用于父子或兄弟进程
  • 单独的文件系统
  • 添加时从文件尾添加，读取从头部读取

管道实质：内核缓冲区，以先进先出的规则（循环队列）存取数据。

管道局限：

  • 数据单向传输
  • 没有名字，只支持具有亲缘关系的进程之间
  • 无规定格式的字节流，需要双方自己协定
  • 缓冲区大小有限

有名管道（FIFO）
  • 解决匿名管道只能与亲缘关系进程通信的不足。
  • 有名管道以文件的形式存在于文件系统中，即使进程间不存在亲缘关系，通过路径名就可以使用有名管道相互通信。
  • 匿名管道和有名管道严格遵循FIFO，即不支持lseek()文件定位、定位读写等操作。
  • 命名管道是一个设备文件，只要双方能够访问该文件，即能够通信。

阻塞问题：如果写入管道的数据超过其最大值，写操作将阻塞，如果管道中没有数据，读操作将阻塞。

消息队列

相比于FIFO，消息队列有以下优点：

  • 消息队列可以独立于读写进程存在，避免了FIFO管道同步打开和关闭的操作。
  • 避免了FIFO的同步阻塞问题，不需要进程提供同步方法。
  • 读进程可以通过消息类型筛选消息，而不像有名管道严格遵守先进先出

共享内存（Share Memory）

多个进程可共同读写内存，如果某个进程向共享内存写入数据，所做的改动将立即影响到可以访问同一段共享内存的任何其他进程，是效率最高的IPC。

由于多个进程共享，故需要进行进程同步与互斥。

信号量（semaphore）

主要用于控制多个进程对共享资源的访问，本质上是一个计数器

信号量的操作：

  1. 创建信号量，并为其赋初值。
  2. 挂起一个信号量，值减一，若小于等于零则阻塞。简称P操作。
  3. 挂出一个信号量，值加一，若加一后值大于0则唤起阻塞进程，简称V操作。

信号量的操作应该为原子操作（与普通整型变量不同的原因），由内核维护。

信号量和互斥量的区别：

  • 互斥量用于线程访问资源的互斥，信号量用于进程的同步互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。 同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。
    大多数情况下，同步已实现了互斥
  • 互斥量只能为0和1，而信号量为非负整数（即互斥量只能控制单个资源的多线程互斥，而同步能控制同类资源的多线程互斥和同步）
  • 互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程（生产者）释放，另一个线程（消费者）得到。

套接字（Socket）

image.png
可用于跨网络的C/S通信，套接字支持TCP/IP协议的基本通信单元。

套接字的3个特性：

  1. 套接字的域：
    • AF_INET：使用IP地址和端口号来指定网络上的某个特定服务。
    • AF_UNIX：指域为文件系统，为文件的读取，地址为文件名。
  2. 端口号：
    端口号是一个16位无符号整数
  3. 协议类型：
    1. 流套接字：基于TCP/IP，提供有序、可靠的双向字节流传输。
    2. 数据报套接字：基于UDP/IP，不可靠但速度较快。
    3. 原始套接字：始套接字允许对较低层次的协议直接访问，比如IP、 ICMP协议

原始套接字与标准套接字的区别在于： 原始套接字可以读写内核没有处理的IP数据包 流套接字只能读取TCP协议的数据 数据报套接字只能读取UDP协议的数据。 因此，如果要访问其他协议发送数据必须使用原始套接字。

3.进程间的同步方式

  1. 互斥量：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
  2. 信号量：允许同一时刻有限数量的线程同时访问资源。比如说java并发包下的Semaphore,可以控制对互斥资源的访问线程数。
  3. 事件：通过通知操作的方式来保持线程同步，比如Java中的Wait方法、Notify方法。

4.进程的调度算法

批处理系统
  1. 先来先服务（FCFS）：非抢占式调度算法，为最先进入队列的进程分配资源。
  2. 最短时间优先（SJF）：非抢占式调度算法，根据运行时间最短的顺序进行调度，可能出现长作业一直等待的情况。
  3. 最短剩余时间（SRTN）：抢占式调度算法，根据剩余运行时间的顺序进行调度，当一个作业到达时与当前作业的剩余时间进行比较再决定资源的分配。

交互式系统
  1. 时间片轮转：每个进程为其分配一个时间片，进程在时间片内得到处理器资源（时间片太小导致进程切换频繁，浪费系统资源，过长则实时性不能得到保证）。
  2. 优先级调度：为每个进程分配一个优先级，按优先级进行调度。
  3. 多级反馈队列：时间片和优先级调度相结合。

5.内存管理机制

连续分配管理
  1. 块式管理：过去操作系统的内存管理模式，每个块中只有一个进程。

非连续分配管理

image.png

6.分页和分段的区别

页和分段系统有许多相似之处,但在概念上两者完全不同,主要表现在：

  1. 页是信息的物理单位,分页是为实现离散分配方式,以消减内存的外零头,提高内存的利用率；或者说,分页仅仅是由于系统管理的需要,而不是用户的需要.
    段是信息的逻辑单位,它含有一组其意义相对完整的信息.分段的目的是为了能更好的满足用户的需要.
  2. 页的大小固定且由系统确定,把逻辑地址划分为页号和页内地址两部分,是由机器硬件实现的,因而一个系统只能有一种大小的页面.
    段的长度却不固定,决定于用户所编写的程序,通常由编辑程序在对源程序进行编辑时,根据信息的性质来划分.
  3. 分页的作业地址空间是维一的,即单一的线性空间,程序员只须利用一个记忆符,即可表示一地址.
    分段的作业地址空间是二维的,程序员在标识一个地址时,既需给出段名,又需给出段内地址.

7.快表和多级页表

  • 快表：引入块表是为了加速虚拟地址到物理地址的转换。快表可以理解为一个高速缓存，其中的内容为页表的一部分。普通页表地址转换时需要访问两次主存，而当需要访问的页在快表中时，只需要使用快表中的内容，再访问 一次内存就可以得到物理地址了。这样提高了地址转换的效率。
    使用快表之后的地址转换流程是这样的：
    1. 根据虚拟地址中的页号查快表；
    2. 如果该页在快表中，直接从快表中读取相应的物理地址；
    3. 如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；
    4. 当快表填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。
  • 多级页表：避免把全部页表放在内存中占用过多空间，特别是那些不需要使用的页表没有必要保留在内存中，多级页表属于时间换空间。

8.用户态切换到内核态的方式

  • 系统调用：程序的执行一般是在用户态下进行，当程序需要使用操作系统提供的服务时，比如打开某一设备、创建文件、读写文件等，就需要向操作系统发出调用服务的请求，即系统调用。
  • 异常：当CPU在执行运行在用户态下的程序时，发生了某些不可知的异常，这时会触发当前运行进程切换到处理异常的内核相关程序中，也就是转到了内核态，比如缺页异常。
  • 外围设备的中断：当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

9.死锁

  1. 必要条件
    • 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
    • 占有和等待：已经得到了某个资源的进程可以再请求新的资源。
    • 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
    • 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
  2. 处理方法
    • 鸵鸟策略
    • 死锁检测和恢复
    • 死锁预防
    • 死锁避免

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测与死锁恢复

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

1. 每种类型一个资源的死锁检测

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

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

2. 每种类型多个资源的死锁检测

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

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

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

  1. 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
  2. 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
  3. 如果没有这样一个进程，算法终止。

3. 死锁恢复

  • 利用抢占恢复
  • 利用回滚恢复
  • 通过杀死进程恢复

死锁预防

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

1. 破坏互斥条件

例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。

2. 破坏占有和等待条件

一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。

3. 破坏不可抢占条件

4. 破坏环路等待

给资源统一编号，进程只能按编号顺序来请求资源。

死锁避免

在程序运行时避免发生死锁。

1.安全状态

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

安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

2. 单个资源的银行家算法

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

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

3. 多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

  • 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
  • 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
  • 重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。