一、笔记知识点

1、进程和线程的区别

(1) 一个运行的程序至少有一个进程，一个进程至少有一个线程。
（进程有自己独立的地址空间，而线程没有，线程必须依赖于进程而存在，即只能在他所属的进程的地址空间内活动）。
(2) 进程是资源分配的单位，线程是执行的单位。（处理机分配给线程，即真正在处理机上运行的是线程）。
(3) 同一进程的线程除自己私有的少量资源外，要共享所属进程的全部资源。
(4) 线程上下文切换比进程上下文切换要快得多，进程间切换消耗的资源更大。
(5) 同个进程下的线程之间通信更方便，因为它们共享所属进程的信息。而进程的通信则需要借助其他方法才行。

2、进程通信

2.1 对于共享资源的同步与互斥

同步：多个进程因为合作关系产生的制约关系，使进程有一定的先后执行顺序；
互斥：对于一个共享资源来说，多个进程在同一时刻，只有能一个进程能够访问该共享资源。

(1) 临界区

● 临界资源：一次只允许一个进程使用的共享资源(类)。

为了互斥访问临界资源，每个进程或者线程再进入临界区之前，都需要进行检查。

(2) 信号量 + PV操作。

● 信号量：系统中某类资源的数目，其值大于0，表示系统中当前可用资源数目；其值小于0，其绝对值表示系统中因请求该类资源而被封锁的进程数目。
● P操作：请求系统分配一个单位资源；● V操作：释放一个单位资源。

生产者-消费者 问题
#define N 100
typedef int semaphore;
semaphore mutex = 1; # 互斥量，缓冲区是临界资源
semaphore empty = N; # 信号量，表明空缓冲区的数量
semaphore full = 0; # 信号量，表明满缓冲区的数量，当缓冲区有物品就满，没有就空

void producer() {
    while(TRUE) {
        int item = produce_item();
        P(&empty);
        P(&mutex);
        insert_item(item);
        V(&mutex);
        V(&full);
    }
}

void consumer() {
    while(TRUE) {
        P(&full);
        P(&mutex);
        int item = remove_item();
        consume_item(item);
        V(&mutex);
        V(&empty);
    }
}

(3) 管程
管程是一种同步机制，用于协调多个进程或线程对共享资源的访问。它可以看成是一种高级的互斥锁，封装了【共享资源和访问共享资源的方式】，确保在任意时刻只有一个进程或者线程访问该共享资源。Java中的sychronized关键字就是一种基于管程的同步机制。

2.2 高级进程通信方式：共享内存区、消息队列方式、管道文件方式

(1) 共享内存方式：在内存中分配一片空间作为共享内存区。需要进行通信的各个进程把共享内存区映射到自己的地址空间中，之后就可以对共享内存区中的数据直接进行读或写。这种方式的通信效率更高，但需要依靠某种同步机制如信号量来避免同时读写的问题。

(2) 消息队列方式：以消息为单位在进程间进行数据交换。
【同步】：发送进程和接收进程需要同步。在一个进程发送消息之前，接收进程需要准备好接收消息的缓冲区，否则没准备好可能会导致消息丢失或者被覆盖。
【寻址】：有两种方式
 ● 直接通信方式：发送进程直接将消息挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中得到消息。
  对称寻址：进行通信的每一方都必须显式的指明消息接收方或发送方是谁；
  非对称寻址：只有发送方知道接收方的名字，而接收方不必知道发送方的名字。
 ● 间接通信方式 / 信箱通信：发送进程将消息送到称做信箱（有唯一标识）的中间设施中，接收进程从信箱中取得消息。
  公用信箱：由操作系统创建。所有进程都可以向公用信箱发送消息，也可以取出发送给自己的消息。
  共享信箱：由某个进程创建。对它要指明共享属性及共享进程的名字，信箱的创建者和共享者都可从中取走发给自己的消息。
  私有信箱：用户进程为自己创建的信箱。创建者有权从中读取消息，而其他进程只能把消息发送到该信箱中。

(3) 管道文件方式：管道文件也称管道线，它是连接两个命令的一个打开文件。一个命令向该文件中写入数据，另一个命令从该文件中读出数据。读写方式类似于队列。
● 匿名管道：一种半双工的通信方式，数据只能单向流动（如果双方通信，则需要建立起两个管道），而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。它只存在于内存中，没有名字、文件描述符。
● 有名管道：也是半双工的通信方式，但是它允许无亲缘关系进程间的通信（通过提供进程的路径名来实现）。有名管道可以持久化，在文件系统中有对应的名字和文件描述符。

(4) 信号：异步通信方式，用于通知接收进程某个事件已经发生，比如按下ctrl + C就是信号。

2.3 网络系统中的进程通信方式：socket套接字、远程过程调用RPC

(1) socket套接字：可用于不同计算机间的进程通信，相当于端口和端口之间的通信。
一对进程通过网络进行通信要用一对socket，每个进程一个。通常，它采用客户端-服务器结构。服务器通过监听指定的端口，等待即将到来的客户请求。一旦受到客户请求，服务器就接收来自客户socket的连接，形成完全连接。
但这种方式是一种低级通信形式，一个原因是socket只允许在通信线程间交换无结构的字节流，必须有客户端或者服务器对数据加以构造。

(2) 远程过程调用RPC：允许程序调用另外机器上的进程。当机器 A 的一个客户进程或线程调用机器 B 上的一个进程时，A 上的调用进程挂起，被调用进程在 B 上开始执行。调用者以参数形式把信息传送给被调用者（通过 RPC 的超时重传软件），被调用者把进程执行结果回送给调用者。

3、线程的通信

3.1 线程的串行执行

串行访问临界区，可以保证临界资源同一时刻只有一个线程在访问。

3.2 互斥量 Sychronized / Lock

采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。（可以和【条件变量】搭配使用，条件变量是一种附加在互斥锁上的线程同步机制，可以使线程在满足特定条件之前阻塞并释放锁，等到条件满足后再从阻塞态到就绪态，重新竞争锁）

3.3 信号量

为控制具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源，但一般需要限制同一时刻访问此资源的最大线程数目。

3.4 事件触发 wait / notify

在Java中，wait和notify是Object类方法。使用该方法的线程必须持有共享资源，否则会报出IllegalMonitorStateException。wait会将当前线程持有的对象锁释放，并使得线程进入等待池中，直到超时或者被唤醒；notify会将在等待池中需要该对象锁的一个或全部线程移入池锁，等待对象锁释放后，共同竞争该锁。

3.5 信号

信号是以进程为单位的，进程收到信号时，由于线程共享进程的资源，该进程下的所有线程都可以处理该信号。

4、线程的实现方式

以下两种不同的线程实现方式，主要区别在于线程的创建、调度和同步机制等方面。
(1) 用户级线程
● 由用户进程自行实现的多个线程，操作系统并不能知晓用户线程的存在。
● 在用户级线程的实现中，所有的线程都共享同一个进程地址空间(用户线程在操作系统中没有单独的堆栈等资源)，因此线程之间的切换非常快速。
● 同个进程的多个线程没法同时占用cpu，即使是cpu有多核；因此，就线程的同时执行而言，任意给定时刻每个进程只能够有一个线程在运行，而且只有一个处理器内核会被分配给该进程。也就是说，在一个线程被阻塞时，整个进程的执行也会被阻塞，因为操作系统无法将运行权转移到其他线程。

(2) 内核级线程
● 内核线程建立和销毁都是在内核的支持下运行，由操作系统负责管理，通过系统调用完成的。
● 操作系统为每个线程创建上下文。进程的每个线程在资源可用时都可以被指派到处理器内核，这些线程可以在全系统内进行资源的竞争。线程之间的切换需要进行系统调用，会涉及到用户态和内核态之间的切换，因此线程的切换开销比用户级线程要大。
● 在一个线程被阻塞时，其他线程仍然可以继续执行，因为操作系统可以将运行权转移到其他线程。

5、协程

协程图例

(1) 如同一个进程可以拥有多个线程一样：一个线程可以拥有多个协程。
(2) 协程是在用户态执行的。相比于进程和线程切换从“用户态到内核态再到用户态”，协程的切换过程只有用户态，即没有陷入内核态，因此切换效率高。
(3) 协程不是进程也不是线程，而是一个特殊的函数，这个函数可以在某个地方挂起，并且可以重新在挂起处继续运行。所以说，协程与进程、线程相比并不是一个维度的概念。
(4) 一个线程的多个协程的运行是串行的（一个线程内可以有多个函数，但他们执行必须时串行的），即同一个时刻只能由一个协程在运行。如果是多核CPU，多个进程或一个进程内的多个线程是可以并行运行的，但是一个线程内协程却绝对是串行的，无论CPU有多少个核，即无法利用CPU的多核能力。当一个协程运行时，其它协程必须挂起。

6、堆与栈的区别

堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式【区别于JVM内存中的堆和栈】，主要有如下几种区别：
(1) 管理方式不同。栈绝大部分情况由操作系统自动分配释放，无需我们手动控制；堆的申请和释放工作由程序员控制，容易产生内存泄漏；
(2) 分配方式不同。堆都是动态分配的，没有静态分配的堆。一般来说栈有2种分配方式：静态分配和动态分配。静态分配是由操作系统完成的，比如局部变量的分配。动态分配可以由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由操作系统进行释放，无需我们手工实现。
(3) 分配效率不同。栈由操作系统自动分配，会在硬件层级对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是由C/C++提供的库函数或运算符来完成申请与管理，实现机制较为复杂，频繁的内存申请容易产生内存碎片。显然，堆的效率比栈要低得多。
(4) 生长方向不同。堆的生长方向向上，内存地址由低到高；栈的生长方向向下，内存地址由高到低。

Linux内存的逻辑分区

(5) 空间大小不同。每个进程拥有的栈的大小要远远小于堆的大小。理论上，程序员可申请的堆大小为虚拟内存的大小，这个虚拟内存空间可以比物理内存空间大得多，因为不是所有的虚拟地址都需要被映射到物理内存中。当进程需要访问虚拟地址时，操作系统会根据需要将虚拟地址映射到物理内存中的实际地址；
(6) 存放内容不同。栈存放的内容，函数返回地址、相关参数、局部变量和寄存器内容等。堆，一般情况堆顶使用一个字节的空间来存放堆的大小，而堆中具体存放内容是由程序员来填充的。

7、避免僵死进程的方法

(1) 父进程通过wait或waitpid函数等待子进程结束，这样有个问题，就是会导致父进程挂起。
(2) 如果父进程很忙，可以采用异步的方式，注册SIGCHLD信号处理函数，在处理函数中wait回收子进程。或者是注册SIG_IGN告知内核，忽略掉该信号，当然子进程结束后，内核会帮助回收。
(3) 还可以用一些技巧，比如fork两次。子进程退出（此时孙进程就短暂的变成了孤儿进程），然后孙进程就由init进程（进程号为1）接管回收了。

8、线程安全

当多个线程访问某个方法时，不管你通过怎样的调用方式或者说这些线程如何交替的执行，我们在主程序中不需要去做任何的同步，这个类的结果行为都是我们设想的正确行为，那么我们就可以说这个类是线程安全的。

● 怎么做到线程安全？
(1) 栈内的数据是线程安全的。栈是线程私有的，其他线程不能操作也不需要操作（如方法的局部变量）。
(2) 只能读取不能修改的数据是线程安全的。指常量或者只读变量，它们想改也改不了。
(3) 堆内数据加锁后是线程安全的。当多个线程想要操作同一份数据，为了确保数据的安全性(或者说一致性)，需要先获取锁才能操作数据，操作完之后释放锁。没有拿到锁的线程只能等待锁的释放。

9、linux中的锁

(1) 自旋锁：

自旋锁的主要特征是使用者在想要获得临界区执行权限时，如果临界区已经被加锁，那么自旋锁并不会阻塞睡眠，等待系统来主动唤醒，而是原地忙轮询资源是否被释放加锁，自旋就是自我旋转，这个名字还是很形象的。自旋锁有它的优点就是避免了系统的唤醒，自己来执行轮询，如果在临界区的资源代码非常短且是原子的，那么使用起来是非常方便的，避免了各种上下文切换，开销非常小，因此在内核的一些数据结构中自旋锁被广泛的使用。

(2) 信号量：

信号量在创建时需要设置一个初始值，表示同时可以有几个任务可以访问该信号量保护的共享资源，初始值为1就变成互斥锁（Mutex），即同时只能有一个任务可以访问信号量保护的共享资源。一个任务要想访问共享资源，首先必须得到信号量，获取信号量的操作将把信号量的值减1，若当前信号量的值为负数，表明无法获得信号量，该任务必须挂起在该信号量的等待队列等待该信号量可用；若当前信号量的值为非负数，表示可以获得信号量，因而可以立刻访问被该信号量保护的共享资源。当任务访问完被信号量保护的共享资源后，必须释放信号量，释放信号量通过把信号量的值加1实现，如果信号量的值为非正数，表明有任务等待当前信号量，因此它也唤醒所有等待该信号量的任务。

(3) 读写锁：

读写锁也叫共享互斥锁：读模式共享和写模式互斥，本质上这种非常合理，因为在数据没有被写的前提下，多个使用者读取时完全不需要加锁。读写锁有读加锁状态、写加锁状态和不加锁状态三种状态，当读写锁在写加锁模式下，任何试图对这个锁进行加锁的线程都会被阻塞，直到写进程对其解锁。

(4) 条件变量【它常常和互斥锁一起使用】

通常用于解决对线程的同步和互斥问题。它允许线程在等待某个条件时进入阻塞状态，并释放当前和条件变量绑定的锁，等到条件满足时线程会被唤醒，从阻塞态进入就绪态，重新竞争锁。但条件变量本身并不是一种锁，它只是一种线程同步机制，常常附加在互斥锁上，搭配使用，用于等待和唤醒其他线程。
java中的java.util.concurrent.locks.Condition包下提供了条件变量相关的类。

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Example {
    private final Lock lock = new ReentrantLock();
    private final Condition condition = lock.newCondition();
    private volatile boolean resultReady = false;

    public void calculate() {
        lock.lock();
        try {
            // 计算结果
            resultReady = true;
            // 通知等待线程
            condition.signal(); 【通知等待线程】
        } finally {
            lock.unlock();
        }
    }

    public void output() {
        lock.lock();
        try {
            while (!resultReady) {
                // 等待计算线程完成
                condition.await();【阻塞并释放lock锁，等待被唤醒进入就绪态】
            }
            // 输出结果
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            lock.unlock();
        }
    }
}

10、同步与异步、阻塞与非阻塞 （）

同步与异步：主要是从消息通知机制来划分的。
● 同步：需要调用方主动的查询被调用方任务执行结果。调用方要持续查看，或者每隔一定时间去检查一下被调用方的状态，效率低；

● 异步：调用方不需要主动查询，可能不能立刻得到返回消息，后续被调用方执行完毕后可以使用通知、回调等方式通知调用方。

阻塞与非阻塞：主要是从等待消息通知时（无所谓同步还是异步）任务的状态来划分的。
● 阻塞：在等待结果返回的过程中，任务被挂起。
● 非阻塞：在等待任务返回的过程中，任务没有被挂起，还可以处理其他的事情。

以小明下载文件，举例说明，四种概念：

(1) 同步阻塞：小明一直盯着下载进度条，持续等待。
● 同步体现在：主动盯着进度条。
● 阻塞体现在：等待下载完成的过程中，什么都不能做。

(2) 同步非阻塞：小明开始下载后就去干别的，但会每隔一段时间回来瞄一眼进度条。
● 同步体现在：每隔一段时间主动查看进度条。
● 非阻塞体现在：在等待下载完成的过程中，还有干别的任务。

(3) 异步阻塞：下载完成后会有“叮”的一声提示音，但是小明仍然一直等待下载完成。（这看起来很傻）
● 异步体现在：下载完成“叮”的一声通知。
● 阻塞体现在：等待下载完成的过程中，什么都不能做。

(4) 异步非阻塞：仍然是那个下载完成后会有“叮”的一声的提示音的软件，小明在开始下载后，就去干别的了，听到“叮”的一声就知道完成了。
● 异步体现在：下载完成“叮”的一声通知。
● 非阻塞体现在：在等待下载完成的过程中，还有干别的任务。

二、八股文链接

1、操作系统常见面试题总结(上) | JavaGuide(Java面试 + 学习指南)
 ● 操作系统基础：几大功能、用户态和内核态(系统调用、异常、中断；中断向量表、中断处理程序)
 ● 进程和线程：概念、通信方式、状态、PCB、进程调度算法
  进程调度算法：
    ① 先到先服务
    ② 短作业优先(CPU运行时间；实现困难(可以以历史替代后来)；对长作业不友好——“饥饿”现象)
    ③ 最短剩余时间(短作业优先的变形，抢占式)
    ④ 时间片轮转法(基于先到先服务，给每个进程分配相同的时间片，可能要经过几次轮转才能执行完该进程)
    ⑤ 优先级调度(静态/动态；非抢占式/抢占式)
    ⑥ 多级反馈队列调度(抢占式；优先级从高到低设计多个队列，高优先级队列的时间片短；最开始的进程加入第一个队列的队尾，如果在规定时间内没有执行完，则移交到下一个队列的队尾；只有上一个队列执行完毕才能执行当前队列，可能会产生“饥饿”问题，优化点：提升那些在队列中等待了很久的进程优先级)
    ⑦ 高响应比优先法(非抢占式；兼顾短作业核长作业；难以在实时系统实现)
    ⑧ 公平共享法(根据用户持有进程数量分配CPU时间比例)
 ● 僵尸进程、孤儿进程
 ● 死锁：一个进程集合中，每个进程本身自己占有一部分资源，不释放，并且等待该集合中另一个进程占有的资源，从而出现循环等待，无限期僵持下去的局面。
  死锁产生的4个必要条件(同时)：
    ① 互斥条件
    ② 占有且等待条件
    ③ 不可抢占条件
    ④ 循环等待条件
 ● 内存管理
  ……
  页缺失：硬性页缺失(物理内存总没有物理页)、软性页缺失(物理内存中有物理页，但是没有建立虚拟页和物理页的映射)、无效缺页错误
 ● 文件系统
  (1) 作用：存储管理、文件管理、目录管理、共享和保护、用户接口……
  (2) 文件：普通文件、目录文件、特殊文件（也可按其他分类标准分）
  (3) 链接：
    ① inode(文件和目录唯一的索引节点号)；
    ② 硬链接(通过inode建立连接，硬链接和源文件的inode节点号相同，可以认为在文件系统中两者等价，即删除一个对另外一个完全没有影响；只有删除了源文件和所有对应的硬链接文件，文件才会被真正删除；不能对不存在的文件或目录创建硬链接，不能跨文件系统建立硬链接，因为不同文件系统可能会有同名inode节点号，导致冲突和混乱)，通过 ln 命令创建硬链接
    ③ 软链接(软链接和源文件的inode节点号不同，软链接指向一个文件路径；源文件删除后，软链接仍然存在，但是指向一个无效的文件路径，类似于Windows系统的快捷方式；可以对不存在的文件或者目录创建软链接，可以跨文件系统建立软链接)，通过 ln -s 命令创建软链接
 ● 输入/输出管理
  (1) 相关概念：盘片、盘面、磁道、磁头、磁臂、扇区、柱面
    一个磁盘，有多个盘片；
    一个盘片，可以有两个盘面(取决于是否涂上磁性物质)；
    一个盘面，附着一个磁头；
    所有磁头，连接同一个磁臂，磁头“同进退”；
    一个盘面，有若干圈磁道；
    一个磁道，有若干块扇区；
    相对位置相同的所有磁道，共同构成一个柱面；
  ——（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”
参考链接：(39条消息) 5 分钟图解 磁盘的结构（盘片、磁道、扇区、柱面）柱面磁道扇区图解一剑何风情的博客-CSDN博客
  (2) 磁盘存取时间：寻道时间(磁头移到相应的磁道或者柱面) + 旋转延迟时间(扇区转到读/写头下) + 传输时间(信息在盘和内存之间传送)
  (3) 磁盘调度算法【主要考虑寻道时间，因为它远大于另外两部分】：
    ① 先来先服务算法(按照请求到达磁盘调度器的顺序进行处理，由于没有考虑磁头移动的路径和方向，平均寻道时间较长)
    ② 最短寻道时间优先算法 / 最佳服务优先算法(优先选择距离当前磁头位置最近的请求进行服务，可能会导致饥饿问题)
    ③ 扫描算法 SCAN (磁头沿一个方向扫描磁盘，如果有请求就处理，到达边界时换向扫描，循环往复)
    ④ 巡回扫描算法 C-SCAN (SCAN的变体，只朝一个方向扫描，到达磁盘边界后，再次回到磁盘起点，重新开始扫描)
    ⑤ 电梯法 / 巡查法 LOOK (SCAN算法碰到了边界才掉头，有可能磁头移动方向上已经没有请求了，这样就会有很多无用功；改进SCAN算法，如果磁头移动方向已经没有别的请求了，就可以立即改变磁头移动方向，循环往复)
    ⑥ 均衡循环扫描算法 C-LOOK (类似LOOK对SCAN的改进，C-LOOK是对C-SCAN的改进，当磁头方向没有请求了，让磁头立即返回，并且只需要返回到有磁道访问请求的位置)

2、操作系统01-20 | 阿秀的学习笔记 (interviewguide.cn)
 ● 内存覆盖和交换
  覆盖技术：是一项已经成为历史的早期技术
    (1) 早期计算机内存很小，不够使用，所以使用覆盖技术来解决程序大小超出物理内存总和的问题；
    (2) 内存中包含一个固定区和若干个覆盖区，基本思想是：把一个程序划分成多个段，分别存放在两个区中，固定区存放常驻内存的段，而覆盖区存放不常用的段，在需要的时候在调入内存；
    (3) 覆盖技术需要程序员声明覆盖结构，对用户不透明，增加了工作负担。
  交换技术
    (1) 基本思想是：在内存空间紧张时，可以把内存中的某些进程暂时换出外存的对换区挂起，把外存中已经具备运行条件的程序换入内存；
    (2) 磁盘存储通常分为：文件区和对换区。文件区主要用来存放文件，因追求存储空间的利用率，所以采用离散分配方式；而对换区占据磁盘空间一小部分，因追求速度所以采用连续分配的方式。
  两者的区别：覆盖是针对同一个进程或程序的，交换是针对不同的进程或程序的；覆盖技术打破了程序必须全部装入内存才能运行的限制，交换技术打破了进程进入内存就一直会运行到结束的限制。
 ● 操作系统经典问题
  (1) 生产者-消费者问题：缓冲区互斥量mutex、empty信号量(>0才能生产)、full信号量(>0才能消费)
  (2) 哲学家进餐问题：状态数组(互斥量)、允许进餐数组(互斥量)【检查左右两边的人是否在进餐，没有的话说明左右筷子可用，才能进餐】
  (3) 读者-写者问题：读者数量(互斥量)、写者数量(互斥量)、写操作(互斥量)【分成读者优先、写者优先两种情况】

● 写者优先

typedef int semaphore;
semaphore resource_mutex = 1;
semaphore read_mutex = 1;
semaphore write_mutex = 1;
int read_count = 0;
int write_count = 0;

void reader() {
    while(TRUE) {
        down(&read_count_mutex);
        read_count++;
        if(read_count == 1) down(&write_mutex); // 第一个读者需要等待所有写者完成操作
        up(&read_count_mutex);

        // 访问共享资源
        read();

        down(&read_count_mutex);
        read_count--;
        if(read_count == 0) up(&write_mutex); // 最后一个读者离开时，通知所有等待中的写者
        up(&read_count_mutex);
    }
}

void writer() {
    while(TRUE) {
       【注意：比读者优先新增的代码部分1】
        down(&write_count_mutex);
        write_count++;
        if(write_count == 1) down(&read_count_mutex); // 第一个写者需要等待所有读者完成操作
        up(&write_count_mutex);

        down(&write_mutex);
        // 访问共享资源
        write();
        up(&write_mutex);

        【注意：比读者优先新增的代码部分2】
        down(&write_count_mutex);
        write_count--;
        if(write_count == 0) up(&read_count_mutex); // 最后一个写者离开时，通知所有等待中的读者
        up(&write_count_mutex);
    }
}

 ● 终端退出，终端运行的进程会怎么样？
  我们在终端输入命令时，终端会将命令传递给bash进程进行解释执行。bash进程是一个Unix/Linux系统的命令行解释器，终端开启的进程就是bash进程。bash进程会作为终端的子进程运行。当终端关闭的时候，会发送SIGHUP信号给这些bash进程，如果程序没有对SIGHUP信号做特殊处理，那么进程会随着终端的关闭而退出。
 ● 如何让进程后台运行？
  (1) 在命令后面加上“&”，加入后台队列中，在后台运行；
  (2) 使用 ctrl+Z，使得当前进程被挂起，然后使用“jobs”查看作业号，并使用“bg %作业号”来使其在后台运行
  (3) 在命令前使用nohup命令，并在最后加上“&”，可使进程忽略SIGHUP信号，在后台运行；
  (4) 将命令(可以是多条的)用“（）”包裹起来，最后加上“&”，可使进程忽略SIGHUP信号，在后台运行；
  (5) 在命令前使用setsid，并在最后加上“&” ，使得进程变成init进程的子进程，不受SIGHUP信号的影响；
 ● 执行malloc申请内存时，操作系统是怎么做的？
  (1) brk操作：当分配的内存不超过128k时，它将进程数据段的最高地址指针向高地址移动，以扩大运行时堆的大小。
  (2) mmap操作：当分配的内存超过128k时，在进程的栈和堆中间寻找一块空闲的虚拟内存。
  先通过这两个系统调用获取进程的虚拟内存地址，然后在访问这些虚拟内存时，通过缺页中断，让内核分配相应的物理空间，并建立地址映射，这样内存分配才算完成。
 ● 守护进程：在后台运行的一种特殊进程，他会周期性的执行一些任务，如检查日志、清理临时文件等，它会一直运行直到系统关闭。
 ● 中断和异常的区别
  中断：由硬件设备产生，产生的来源在程序指令之外，会发送给CPU，然后CPU发送给内核，由内核处理中断，内核需要根据是异常还是中断调用不用的处理程序。中断不一定是时钟同步的，这意味着终端随时可能会来。
  异常：由程序指令内部产生的，通常是意外的事件，它同样会由CPU发送给内核，由内核处理异常，内核需要根据是异常还是中断调用不用的处理程序。异常是CPU调度指令时产生的，因此它是时钟同步的。
 ● Linux下的内存分布情况

7种不同的内存段

冯诺依曼体系结构图

  (1) 输入设备：键盘
  (2) 输出设备：显示器
  (3) 控制器：CPU（现代计算机中将它和运算器合并，称为中央处理器CPU）
  (4) 运算器：CPU（现代计算机中将它和控制器合并，称为中央处理器CPU）
  (5) 存储器：内存、外存
 ● 什么时候用多进程？什么时候用多线程？
  (1) 当涉及到大量的创建销毁、或者计算操作时，应优先选择【多线程】。因为这涉及到CPU资源的利用，进程的切换要比线程切换开销大得多；
  (2) 当相互协作的关联性比较强时，优先选择【多线程】，因为同属一个进程的多个线程共享资源，并且通讯起来较为方便；
  (3) 当任务扩展到多机分布时，应该用【多进程】；而任务涉及的是单机中的多核分布，应该优先选择【多线程】。
  此外，更常见的是多进程和多线程结合的方式，因为他们两种并不是非此即彼的关系。
 ● 服务器高并发的解决方案有哪些？
  (1) 应用数据和静态资源分离。比如在访问web网页的时候，可以将静态资源放到专门的服务器中，在客户端访问的时候，直接从这个服务器返回，而数据可以通过异步的方式请求到主服务器中，速度更快，无需等到数据装载入页面后再从主服务器返回。
  (2) 利用缓存机制。访问web网页就用到了这种机制，如果客户端判断是同一个请求，会将之前缓存的页面取出，如果说页面过期，或者有数据更新，再从服务器拉取。这样当大量请求过来的时候，就不需要全部去访问服务器，给服务器降低压力。
  (3) 集群和分布式【注意区分】。集群和分布式都是利用多台计算机协同工作。

● 集群：所有的服务器具有相似的功能，请求哪一台都可以，主要起到负载均衡、故障恢复的作用，但是计算机之间的同步和通信的开销大；
● 分布式：将一个大型的计算任务分散到多台计算机上进行处理，每台计算机可以具有不同的功能或者业务模块，处理一个请求可能需要用到多态服务器，通过彼此的协同工作，最终将结果汇总。请求的速度大大加快，但是计算机之间的通讯比较困难，需要设计复杂的协议共同工作。

  (4) 反向代理。在访问服务器的时候，通过一个中间服务器请求资源并返回结果。

三、《操作系统》知识点

第3章-死锁

3.2 死锁的概念

● 概念
● 产生死锁的4个必要条件【同时满足】：互斥、占有且等待、非抢占、循环等待
● 资源分配图(申请边、赋予边；没有环路，一定不会出现死锁，有环路，可能不会产生死锁)

3.3 死锁的预防——静态策略

(1) 破坏互斥条件：资源的固有属性，难以被破坏
(2) 破坏占有且等待条件：① 预分资源策略；② “空手”申请资源策略(仅在它不占有资源时才可以申请资源)
(3) 破坏非抢占条件：隐式抢占方式(等待进程的全部资源可被抢占)、抢占等待者的资源
(4) 破坏循环等待条件：资源有序分配(给各个资源分配一个自然数，只能申请比当前占有资源更大的资源)、“弃大取小”(想要申请某个资源，必须要释放掉数字比它大的那些资源)

3.4 死锁的避免——动态策略，但在可能产生死锁的情况下(不安全状态)，即使资源可用，也不会进行分配，资源利用率下降

● 安全序列：一个进程序列，系统按照次序以此为进程分配资源，能够使得它们依次成功的运行完毕。
● 安全状态：系统存在这样一个安全序列，则系统此时的分配状态时安全的；如果系统不存在这样一个安全序列，则系统是不安全的。
存在安全序列时，一定不会产生死锁，但是系统进入不安全状态，也不一定会产生死锁，但产生死锁时，系统一定是不安全状态。
● 资源分配图算法(新增要求边；环路检测算法，需要次操作，n为进程数量)——针对单体资源类
● 银行家算法——针对多体资源类

银行家算法-思想描述

3.5 死锁的检测与恢复

● 等待图(资源分配图的变形，只保留进程，并把边折叠)——针对单体资源类的死锁检测
假设有p1→p2，说明进程p1需要p2占有的某个资源；如果有环说明检测到了死锁。
● 对多体资源类的死锁检测

对多体资源类的死锁检测

● 死锁检测的时机：① 资源请求时；② 定时检测； ③ CPU资源利用率低
● 死锁恢复：① 抢占资源； ② 回退进程； ③ 杀掉进程(重启系统；仅杀死死锁进程；逐步杀死死锁进程)
● 饥饿：某个或者某些进程永远得不到完成工作的机会，因为他们所需的资源总是被别的进程占有或者抢占。饥饿进程可以在就绪态，而死锁进程一定是在阻塞态。
● 活锁：某个或者某些进程在轮询的等待某个不可能为真的条件为真，导致一直尝试，失败，尝试，失败……这导致CPU资源被耗尽，系统效能大大下降。活锁进程【忙式等待，且占用CPU，不会让出CPU】可以在运行中，且有可能自行解开；而死锁进程【总是让出CPU，造成无限期等待】一定是在阻塞态，不可能自行解开。

第5章-存储管理

5.1 引言

● 程序装入内存：绝对装入、可重定位装入、动态执行时装入(使用对换技术)
● 逻辑地址空间 vs 物理空间(内存空间)
● 重定位：静态重定位、动态重定位(一对寄存器：基址寄存器、限长寄存器)
● 对换技术：要求把进程放置在一片连续的内存区域，也会产生碎片。对换空间在物理内存被充满时使用，内存中不活跃的页就会被移到交换空间去。【PCB会常驻内存，不会被换出到外存】而当系统的负荷没有那么高时，就会暂停交换。

5.2 分区法——程序装入一个一个连续的内存空间中，产生碎片

● 固定分区法(等分、差分；分区说明表)——空间浪费，内部碎片严重；系统生成时指定分区个数，一个分区一个进程，限制了活动的进程数量。
● 动态分区法(内存登记表/链；分裂、合并)——会产生外部碎片
● 分配空闲区算法：最先适应算法(按地址排序)、最佳适应算法(容量从小到大排序)、最坏适应算法(容量从大到小，找最大)、循环适应算法(设立指针从上次找到的可用分区开始找)
● 内部碎片、外部碎片
● 可重定位分区分配(即：动态分区使用紧缩技术，消除外部碎片)
 紧缩的方式：将已经分配的内存块聚集在一起，以空出连续的可用空闲内存块(优化：合并的方向可以往两边靠，空出中间)
 紧缩的时机：释放分区时不邻近空闲区时紧缩、分配分区无可用空间时紧缩

5.3 分页技术——允许程序的存储空间不一定连续，不会产生外部碎片，但会产生内部碎片

● 若干大小相等的页块、若干大小相等的内存块(页框)——两者大小一一对应(相等)，由硬件决定
● 逻辑地址表示

分页技术-逻辑地址表示

● 页表(存在于进程中，一个进程一个页表)：记录页号-物理块号的映射
● 内存块表(存在于系统中，一个系统一个内存块表)：记录内存块的分配/空闲状态，分配给的进程和对应的页号
● 地址映射

分页系统-地址转换硬件支持

两级页表-逻辑地址表示

● 散列页表(逻辑地址表示：页号+页内地址；页号做哈希映射，相同散列值的元素链接形成链表，一个元素包含：页号、内存块、指向下一个的指针；匹配时，根据页号进行匹配)
● 倒置页表(逻辑地址表示：进程号+页号+页内地址；页表总表项≠页号总长度，而是=内存块总长度【当然这说的是没有对换技术，且全部存在内存的的前提下】；页表中检索进程号、页号，匹配上了返回页表的下标【下标即内存块号】，拼接上页内地址，即为实际的物理内存地址)

倒置页表-地址转换

● 页面共享(期望各个进程相同的程序都被映射到同一块内存块，尽管他们的逻辑地址不同；每个进程同时又有自己私有的数据页；分页机制很难实现，因为数据和程序可能在同一个页面，并且倒置页表几乎不能实现这种共享，因为一个物理内存块仅能对应唯一的进程和页号)

5.4 分段技术：

● 段、段号
● 段表 段表基址寄存器、段表长度
● 二维地址结构(分页是一维，也就是说只要给出一个逻辑地址，就可以自动算出页号、页内偏移量两个部分，并且在处理的时候转换成二进制的，后跟真实的页内地址拼接；而段因为有段号的存在，需要显示指明段内地址有多少位，它用十进制转换每个段的完整基址，跟真实的偏移量相加)

段-逻辑地址表示

● 地址转换(注意这里是相加，而分页是拼接)

段-地址转换

● 分段和分页的区别
相似点：可以将整体划分成若干部分，每一部分可以不相邻。都要用地址映射机构将逻辑地址映射为物理地址。
不同点：
(1) 页表的逻辑地址是一维的，段表是二维的
(2) 页是物理存储单位，段是逻辑存储单位
(3) 页的大小是由系统决定的，并且大小一样；段的大小是由用户程序每一逻辑模块决定的，每段大小可以不一样
(4) 分页的数据和代码不分离，难以实现共享和保护；而分段则很容易实现这些功能

● 段的共享（地址覆盖，只要段表项中的段长、段内地址相同即可；把不能共享的放在各自私有的段中
● 段的保护：段表长度以及段长的验证、利用段表在进程中、段表项的存取控制字段、保护环

5.5 段页式技术：在段内按页划分

● 面向用户的地址空间段式划分，面向物理的地址空间页式划分——结合两者的优点
 段式(按照用户逻辑划分；但容易产生大量外部碎片)
            +
 页式(碎片程度少，内存利用率高；但逻辑性差，难以保护和共享数据)
● 逻辑地址结构

段页式-逻辑地址

● 地址转换
 段表基址寄存器 (加段号找到) 段表项(存放页表基址、页表长度) (加页号找到) 页表项(存放了页对应的物理基址，拼接页内地址)

段页式-地址转换

● 缺页中断：该页不在内存中，然后系统进行缺页中断处理；
● 缺段中断：该段的页表不在内存中，然后系统为该段在内存建立页表

5.6 虚拟存储器：操作系统给用户提供一个比真实内存空间大的多的地址空间，实现逻辑存储器与物理存储器分离

● 基于局部性性原理
只把需要的那部分的程序和数据装入内存，其他部分暂且放在外存。待以后实际需要这些内容时，再从外存调入内存(换入)，当然内存中不用的部分也可以从内存中搬移到外存(换出)。
● 虚拟存储器容量受限于：
(1) 地址长度
(2) 外存容量

5.7 请求分页技术：基于分页技术 + 虚拟存储器(对换技术) —— linux系统

● 单纯的分页系统：没有引入虚拟存储器，所有的页虽然不在物理空间中相邻，但需要把所有页放入内存中。
● 页表项：新增标志位(1-在内存中；0-未在内存中)、修改位(在换出时，如果有内存页已修改，需要重新写回外存，否则不用写回)、引用位(记载最近对该页访问过没有，当没有空闲内存块时，置换算法淘汰某页会考虑)
● 缺页中断机构：软硬件相互配合

缺页中断机构

 对换空间：一般占用磁盘上一片连续的空间(因为：这个空间是临时的，速度是关键)，速度比文件系统快。

● 处理缺页中断主要考虑的时间：
(1) 中断处理程序的时间
(2) 从外存调入该页的时间：磁头寻道时间、扇区旋转时间、数据传输时间
(3) 重启指令的时间

5.8 页面置换算法

● 内存块的分配算法：如果有多个进程存在内存中，要决定为每个进程分配多少个内存块
● 页面置换算法：当需要置换页面时(没有空闲内存块 或 第一次访问页面)，要确定必须要淘汰哪个页面
● 抖动：被换出的页很快又被访问，频繁的更换页面，导致系统大部分时间都花费在页面的调度和传输上。系统很忙，但效率很低。
● 页面走向：存储访问序列

(1) 先进先出法 FIFO：先进入的页面先被淘汰
(如果已经在内存的页，再次进入会重新插入队尾)
 可能会产生Belady异常现象，即缺页率随着内存块的增加而增加。一般来说，内存块被分配的越多，缺页数会更少，但是由于FIFO算法的会把在内存中停留最久的页换走，但往往那些常被访问的页在内存中停留最久，导致总是没有把进程所需要的页放入内存，形成异常现象)
(2) 最佳置换算法：淘汰的页面应在将来不被使用，或者在最远的将来才被使用
(要预先知道整个页面走向，较为理想化)
(3) 最近最久未使用置换法：类比于最远的将来，淘汰最近(过去)那个最久没有使用的页面
(需要在每个页面中一个访问字段，用来记录自上次被访问经历的时间t；实现起来需要软硬件的支持)
实现的方法：
① 计数器，给每个页面增加一个时间的字段，淘汰时间最先的页
② 栈，最新访问的页在栈顶，淘汰栈低(由于需要操作栈的底部和中间，需要使用双向链)
(4) 最近未使用置换法：根据引用位、修改位，将页面分成4类，利用循环队列查找，最坏情况是第四轮开始找到

最近未使用-搜索步骤

(5) 第二次机会置换法：基于FIFO，根据引用位(=1)给机会，将该页面重新移入队尾，并把引用位置0
(6) 时钟置换法：第二次机会置换法的变形，将队列改成环形结构，提升了页面在链表中的移动效率
(7) 最少使用置换法：每个页面的引用位会在每个时钟中断累加到每个页面的软件技术器；老化算法(计算右移，加到左边的位置上，右移保证越早访问的作用越小)
(8) 页面缓冲算法：维护空闲页链表、修改页链表，基于FIFO选择淘汰页，但它不会实际从内存中移除，而是先链入表(2选1)的队尾，淘汰的是空闲页链表队首的页；当修改页链表到了一定数量，再一次写回到外存。

5.9 内存块的分配和抖动问题

● 最少内存块数(保证进程正常运行的最少内存块数)、最多内存块数(由可用内存总量决定)
● 内存块置换范围：全局置换(系统整体的存储块可被调度)、局部置换(只有当前进程的内存块集可被调度)
● 内存块分配策略：
 (1) 固定分配策略：分配给进程的内存块数量固定(并不是说均等分配，而是说运行过程中不能动态增加内存块)
 (2) 可变分配策略：分给进程的内存块数随着进程的活动可以改变
● 内存块分配算法：
(1) 等分法
(2) 比例法：根据地址空间划分比例
(3) 优先权法

● 抖动
 原因：进程过多→页面频繁置换→CPU利用率低→引入更多进程→……【恶性循环】
 缓解方法：
 (1) 局部置换：使抖动局限在一个小范围；
 (2) 挂起某些进程；
 (3) 控制缺页率：设置上限或者下限
 (4) 工作集策略
  a) 工作集：一个进程在某一小段时间内访问页面的集合；
  b) 局部性：空间(某一个位置被访问过，它附近的位置也很快要用到)、时间(某条指令或者数据被访问过，段时间内可能又被访问)
  c) 利用工作集控制进程数量：计算当前所有进程的工作集数量D，与当前可用的总内存块m。如果D>m，将其中一个进程挂起，将它的页面全部写回外存，空出新的可用内存块；如果D<m，分配新的进程。

● 利用工作集进行页面置换：找出一个不在工作集的页面，将它淘汰

5.10 请求分段技术：类似请求分页技术(请求分段需要像分区那样紧缩，请求分页因为是内部碎片，不需要紧缩)

● 单纯的分段系统：没有引入虚拟存储器，所有的段虽然可以不在物理空间中相邻，但需要把所有段放入内存中。

5.11 Linux系统的存储管理

● 请求分页(虚拟内存管理机制)技术
● Linux的三级页表结构
● 内存页的分配与释放：数组每一项，记录的是内存页组，包含位图+(双向)链表
● kswap交换守护进程：内存不足时，释放内存页。【无限循环，循环末尾进入睡眠，然后一定会事件后又会被唤醒】系统会设置空闲内存页的上限和下限，当高于上限值不做任何事；当低于上限值，甚至低于下限值，就要进行兑换，以释放空闲内存页。
● 页面淘汰：LRU

另，时钟中断：https://blog.csdn.net/LSG_Down/article/details/81074672/
● 时钟周期（单片机层面）< 机器周期（由若干时钟周期构成，也叫CPU周期，指基本操作，如取地址，需要的最小周期）< 指令周期（由若干机器周期构成，完成一条指令需要的周期）