操作系统

1 进程和线程

线程是调度的基本单位，而进程则是资源拥有的基本单位。

• 进程（Process） 是指计算机中正在运行的一个程序实例。进程是操作系统分配资源的基本单位，它拥有独立的内存空间和系统资源。每个进程都拥有自己的地址空间、堆、栈以及其他的系统资源。进程之间的通信需要通过进程间通信(IPC)的方式来进行。进程适合处理重量级的任务，但由于进程切换时需要保存和恢复大量的上下文信息，因此进程切换的开销相对较大。
• 线程（Thread） 也被称为轻量级进程，更加轻量。多个线程可以在同一个进程中同时执行，并且共享进程的资源比如内存空间、文件句柄、网络连接等，共享进程的用户地址空间。线程是操作系统调度的基本单位，它是进程的一个执行单元。一个进程可以包含多个线程，这些线程共享进程的地址空间和部分资源（如堆），但每个线程拥有自己独立的栈。线程之间的切换开销相对较小，因为它们共享进程的内存空间，不需要像进程那样在切换时保存和恢复大量的上下文信息。线程适合处理IO密集型任务，可以通过多线程并发执行来提高程序的执行效率。
• 协程：协程是一种用户态的轻量级线程，它完全由程序控制，而不是由操作系统内核来调度。协程拥有自己的寄存器上下文和栈，但它们的栈是独立的，不与其他协程共享。协程之间的切换开销非常小，因为它们只涉及到少量的上下文切换。协程适合处理大量并发的、IO密集型的任务，可以通过协程的异步特性来提高程序的执行效率。

优缺点：

• 进程切换开销大

• 多个线程可以并发处理不同的任务，更有效地利用了多处理器和多核计算机。

• 同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核。

1.1 线程与进程的比较

• 本质区别：进程是操作系统资源分配的基本单位，而线程是CPU任务调度和执行的基本单位

• 在开销方面：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC）、寄存器，线程之间切换的开销小

• 稳定性方面：进程中某个线程如果崩溃了，可能会导致整个进程都崩溃。而进程中的子进程崩溃，并不会影响其他进程。

• 内存分配方面：系统在运行的时候会为每个进程分配不同的内存空间；而对线程而言，除了CPU外，系统不会为线程分配内存（线程所使用的资源来自其所属进程的资源），线程组之间只能共享资源

对于，线程相比进程能减少开销，体现在：

• 线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；

• 线程的终止时间比进程快，因为线程释放的资源相比进程少很多；

• 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享）

• 由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；

2 进程

• 资源所有权

• 可以被调度、执行

2.1 进程控制结构： PCB（进程控制块）

PCB（Process Control Block） 即进程控制块，是操作系统中用来管理和跟踪进程的数据结构，每个进程都对应着一个独立的 PCB。

2.2 进程状态

2.2.1 五状态

NULL -> 创建状态：一个新进程被创建时的第一个状态；创建状态 -> 就绪状态：当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态，这个过程是很快的；就绪态 -> 运行状态：处于就绪状态的进程被操作系统的进程调度器选中后，就分配给 CPU 正式运行该进程；运行状态 -> 结束状态：当进程已经运行完成或出错时，会被操作系统作结束状态处理；运行状态 -> 就绪状态：处于运行状态的进程在运行过程中，由于分配给它的运行时间片用完，操作系统会把该进程变为就绪态，接着从就绪态选中另外一个进程运行；运行状态 -> 阻塞状态：当进程请求某个事件且必须等待时，例如请求 I/O 事件；阻塞状态 -> 就绪状态：当进程要等待的事件完成时，它从阻塞状态变到就绪状态；

2.2.2 七状态

2.3 进程间通信方式

• 管道/匿名管道(Pipes)：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。通信的数据是无格式的流并且大小受限，通信的方式是单向的

• 有名管道(Named Pipes) : 匿名管道由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道。有名管道严格遵循先进先出(First In First Out) 。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。

• 消息队列(Message Queuing)：消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。克服了管道通信的数据是无格式的字节流的问题。

• 共享内存(Shared memory)：使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有用的进程间通信方式。可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问

• 信号量(Semaphores)：保护共享资源，以确保任何时刻只能有一个进程访问共享资源

• 信号(Signal)：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；信号是异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令）

• 套接字(Sockets) : 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程进程间通信IPC (InterProcess Communication) - 简书 (jianshu.com)
  每个进程的用户地址空间都是独立的，一般而言是不能互相访问的，但内核空间是每个进程都共享的，所以进程之间要通信必须通过内核。

2.3.1 管道

• 匿名管道、命名管道

• 单向管道、双向管道

管道，就是内核里面的一串缓存。从管道的一段写入的数据，实际上是缓存在内核中的，另一端读取，也就是从内核中读取这段数据。

管道的通信方式是效率低的，因此管道不适合进程间频繁地交换数据。写入管道的数据在被读取之前处于阻塞状态。

2.3.2 消息队列

消息队列是保存在内核中的消息链表，A 进程要给 B 进程发送消息，A 进程把数据放在对应的消息队列后就可以正常返回了，B 进程需要的时候再去读取数据就可以了。同理，B 进程要给 A 进程发送消息也是如此。

• 消息队列不适合比较大数据的传输

• 消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。

2.3.3 共享内存

现代操作系统，对于内存管理，采用的是虚拟内存技术，也就是每个进程都有自己独立的虚拟内存空间，不同进程的虚拟内存映射到不同的物理内存中。所以，即使进程 A 和 进程 B 的虚拟地址是一样的，其实访问的是不同的物理内存地址。

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。不会发生用户态和内核态之间的消息拷贝过程。

2.3.4 信号量

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。

信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。定义：semphore s

信号量s发送信号：semSignal(s) V(s)

信号量s接收信号：semWait(s) P(s)

进程访问受信号量保护的共享数据：

2.3.5 信号

信号是异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件

信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令）。

信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程

2.3.6 socket

前面提到的管道、消息队列、共享内存、信号量和信号都是在同一台主机上进行进程间通信，那要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。

实际上，Socket 通信不仅可以跨网络与不同主机的进程间通信，还可以在同主机上进程间通信。

5.2 进程间有哪些通信方式？ | 小林coding (xiaolincoding.com)

2.4 进程上下文切换

CPU上下文：CPU寄存器、程序计数器进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。

2.5 僵尸进程、孤儿进程

• 僵尸进程：子进程已经终止，但是其父进程仍在运行，且父进程没有调用 wait()或 waitpid()等系统调用来获取子进程的状态信息，释放子进程占用的资源，导致子进程的 PCB 依然存在于系统中，但无法被进一步使用。这种情况下，子进程被称为“僵尸进程”。避免僵尸进程的产生，父进程需要及时调用 wait()或 waitpid()系统调用来回收子进程。

• 孤儿进程：一个进程的父进程已经终止或者不存在，但是该进程仍在运行。这种情况下，该进程就是孤儿进程。孤儿进程通常是由于父进程意外终止或未及时调用 wait()或 waitpid()等系统调用来回收子进程导致的。为了避免孤儿进程占用系统资源，操作系统会将孤儿进程的父进程设置为 init 进程（进程号为 1），由 init 进程来回收孤儿进程的资源。

3 线程

线程是进程当中的一条执行流程。

同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。

3.1 线程间同步方式

线程同步是两个或多个共享关键资源的线程的并发执行。应该同步线程以避免关键的资源使用冲突。

互斥锁、读写锁、条件变量、自旋锁和信号量

• 互斥锁(Mutex)：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。

• 条件变量（Condition Variables）：条件变量(cond)是在多线程程序中用来实现"等待–》唤醒"逻辑常用的方法。条件变量利用线程间共享的全局变量进行同步的一种机制，主要包括两个动作：一个线程等待"条件变量的条件成立"而挂起；另一个线程使“条件成立”。为了防止竞争，条件变量的使用总是和一个互斥锁结合在一起。线程在改变条件状态前必须首先锁住互斥量，函数pthread_cond_wait把自己放到等待条件的线程列表上，然后对互斥锁解锁(这两个操作是原子操作)。在函数返回时，互斥量再次被锁住。

• 读写锁（Read-Write Lock）：允许多个线程同时读取共享资源，但只有一个线程可以对共享资源进行写操作。

• 信号量(Semaphore)：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。

• 屏障（Barrier）：屏障是一种同步原语，用于等待多个线程到达某个点再一起继续执行。当一个线程到达屏障时，它会停止执行并等待其他线程到达屏障，直到所有线程都到达屏障后，它们才会一起继续执行。比如 Java 中的 CyclicBarrier 是这种机制。

• 事件(Event) :Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

3.2 线程分类

• 用户线程（User Thread）：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理；

• 内核线程（Kernel Thread）：在内核中实现的线程，是由内核管理的线程；

• 轻量级进程（LightWeight Process）：在内核中来支持用户线程；

4 进程调度

4.1 调度原则

• CPU 利用率：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；

• 系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；

• 周转时间：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；（指一个进程从提交到完成之间的时间间隔）

• 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；

• 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

4.2 调度算法

• 先来先服务：非抢占式，不利于短作业

• 时间片轮转RR调度算法：一种抢占式调度算法，分配给每个进程一个时间片，时间片结束之后调度下一个就绪的进程执行。

• 最短进程优先

• 高响应比优先：权衡短作业和长作业，等待时间长会获得高响应比

• 最短剩余时间优先

• 最高优先级调度算法

• 多级反馈队列调度算法

5 并发性：互斥和同步

5.1 同步、互斥

并发	在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的
互斥	多个进程不能访问同一个资源（临界资源）
进程的同步	系统中多个进程相互合作，这些进程中发生的一些事件需要满足某种时序关系，从而共同完成一项任务

6 并发性：死锁和饥饿

6.1 死锁

6.1.1 产生死锁的四个必要条件

• 互斥：资源必须处于非共享模式，即一次只有一个进程可以使用。如果另一进程申请该资源，那么必须等待直到该资源被释放为止。

• 占有并等待：一个进程至少应该占有一个资源，并等待另一资源，而该资源被其他进程所占有。

• 非抢占：资源不能被抢占。只能在持有资源的进程完成任务后，该资源才会被释放。

• 循环等待：有一组等待进程 {P0, P1,..., Pn}， P0 等待的资源被 P1 占有，P1 等待的资源被 P2 占有，……，Pn-1 等待的资源被 Pn 占有，Pn 等待的资源被 P0 占有。

必要条件：发生死锁，上述条件成立

6.1.2 模拟死锁

public class DeadLock {
    private static Object a=new Object();
    private static Object b=new Object();

    public static void main(String[] args){
        new Thread(()->{
            synchronized (a){
                System.out.println(Thread.currentThread()+ "获得资源a");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                System.out.println(Thread.currentThread()+"请求资源b");
                synchronized (b){
                    System.out.println(Thread.currentThread()+ "获得资源b");
                }
            }
        },"线程1").start();
        new Thread(()->{
            synchronized (b){
                System.out.println(Thread.currentThread()+ "获得资源b");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                System.out.println(Thread.currentThread()+"请求资源a");
                synchronized (a){
                    System.out.println(Thread.currentThread()+ "获得资源a");
                }
            }
        },"线程2").start();
    }
}

6.1.3 解决死锁的办法

• 预防 是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间上都不满足。

• 避免则是系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生

• 检测是指系统设有专门的机构，当死锁发生时，该机构能够检测死锁的发生，并精确地确定与死锁有关的进程和资源。

• 解除 是与检测相配套的一种措施，用于将进程从死锁状态下解脱出来。

死锁预防（prevention）

互斥：资源可以共享访问占有且等待：一次性请求所有资源循环等待：定义资源类型的线性顺序在层次分配策略下，所有的资源被分成了多个层次，一个进程得到某一次的一个资源后，它只能再申请较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源不可剥夺：采用剥夺式算法

死锁避免（avoidance）

将系统的状态分为 安全状态 和 不安全状态 ，每当在为申请者分配资源前先测试系统状态，若把系统资源分配给申请者会产生死锁，则拒绝分配，否则接受申请，并为它分配资源。

如果操作系统能够保证所有的进程在有限的时间内得到需要的全部资源，则称系统处于安全状态，否则说系统是不安全的。

银行家算法当一个进程申请使用资源的时候，银行家算法 通过先 试探 分配给该进程资源，然后通过 安全性算法 判断分配后系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待，若能够进入到安全的状态，则就 真的分配资源给该进程。

[!note] 银行家算法

分配给进程资源前，首先判断这个进程的安全性，也就是预执行，判断分配后是否产生死锁现象。如果系统当前资源能满足其执行，则尝试分配，如果不满足则让该进程等待。

系统给不同进程分配了不同资源，当前资源剩余量满足其中某个进程，调度进程执行，执行后释放分配的资源，找到一个调度顺序不发生死锁

死锁检测（detection）

这种方法对资源的分配不加以任何限制，也不采取死锁避免措施，但系统 定时地运行一个 “死锁检测” 的程序，判断系统内是否出现死锁，如果检测到系统发生了死锁，再采取措施去解除它。