操作系统

操作系统知识点。

进程，线程，协程

简介

进程：

进程是正在执行的程序
系统资源分配的最小单位，每个进程得到一定的资源，比如CPU时间、内存、I/O设备等等来完成任务
进程对应的内存空间中，分为以下数据区：
- BSS(Block Starting Symbol)，存放程序中未初始化的全局变量，属于静态内存分配
- 数据段，存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。
- 代码段，存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，通常属于只读区域；同时也可能也有可能包含一些只读的常数变量，例如字符串常量等
- 堆，存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减 (malloc, free等函数分配/释放内存的位置)
- 栈，用户存放程序临时创建的局部变量。在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。

线程：

线程属于进程，一个进程内可能有一至多个线程。
线程是CPU调度的最小单位，每个线程由独自享有线程ID、程序计数器、寄存器、栈等
每个线程与属于同一进程的其他线程共享进程地址空间、代码段、数据段、堆等资源

协程：

协程属于线程，协程的程序在线程内部运行，但是有自己的寄存器和栈
协程的调度切换完全在用户空间进行，只涉及基本的CPU上下文切换，没有内核切换的开销，非常快
因为只有一个线程，不存在同时写变量冲突，因此不需要多线程的锁机制，执行效率更高

多进程/多线程编程的优点与取舍

为并发而设计，能够响应并提供更多服务。

具体的选择，需要看具体的需求和资源限制

数据共享与同步：多进程在共享上复杂，但在同步上容易；多线程则相反。
内存与CPU：多线程编程，因为它的内存成本较低，而且多线程的上下文切换也比较容易。
可靠性：多进程编程，因为进程之间不容易相互影响

多线程比单线程慢的例子

在一个单核单处理器上：

使用1个线程，循环打印100万个字符
使用100个线程，循环打印100万个字符

这种情况下，使用100个线程会更慢，因为输出字符使用临界区资源，第二种情况在线程抢占资源上会浪费很多时间；而单核线程不用抢占。

进程和线程的生命周期

进程的生命周期：

新建：进程被创建
执行：进程被执行
等待：进程等待某个事件发生，例如I/O完成或其他信号
就绪：进程等待分配CPU
终止：进程完成执行

线程的生命周期：

新建状态（New）：当线程对象对创建后，即进入了新建状态
就绪状态（Runnable）：当调用线程对象的start()方法，线程即进入就绪状态。处于就绪状态的线程，只是说明此线程已经做好了准备，随时等待CPU调度执行，
运行状态（Running）：当CPU开始调度处于就绪状态的线程时，此时线程才得以真正执行，即进入到运行状态。注：就绪状态是进入到运行状态的唯一入口，也就是说，线程要想进入运行状态执行，必须处于就绪状态中
阻塞状态（Blocked）：处于运行状态中的线程由于某种原因，暂时放弃对CPU的使用权，停止执行，此时进入阻塞状态，直到其进入到就绪状态，才有机会再次被CPU调用以进入到运行状态。根据阻塞产生的原因不同，阻塞状态又可以分为三种：
1. 待阻塞：运行状态中的线程执行wait()方法，使本线程进入到等待阻塞状态
2. 同步阻塞 – 线程在获取synchronized同步锁失败(因为锁被其它线程所占用)，它会进入同步阻塞状态
3. 其他阻塞 – 通过调用线程的sleep()或join()或发出了I/O请求时，线程会进入到阻塞状态。当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时，线程重新转入就绪状态
死亡状态（Dead）：线程执行完了或者因异常退出了run()方法，该线程结束生命周期。需要保证在一定的情况下，线程的run()方法能够正常执行完毕；或者，使用标志位 / 抛出中断来退出线程。

补充：触发中断退出线程阻塞状态时，如果有interrupt()发生，系统除了会抛出InterruptedException异常外，还会调用interrupted()函数，调用时能获取到中断状态是true的状态，调用完之后会复位中断状态为false，所以异常抛出之后通过isInterrupted()获取不到中断状态是true的状态，从而不能退出循环，因此在线程未进入阻塞的代码段时是可以通过isInterrupted()来判断中断是否发生来控制循环，在进入阻塞状态后要通过捕获异常来退出循环。

public class ThreadSafe extends Thread {
    public void run() { 
        while (!isInterrupted()) { //非阻塞过程中通过判断中断标志来退出
            try {
                Thread.sleep(5*1000);//阻塞过程捕获中断异常来退出
            } catch(InterruptedException e) {
                e.printStackTrace();
                break;//捕获到异常之后，执行break跳出循环。
            }
        }
    } 
}

进程间通信机制（IPC）

进程间通信有四种基本模式：共享内存、消息传递、套接字、信号量

共享内存：

一块共享内存区域驻留在生成共享内存段进程的地址空间上，所有希望使用这个共享内存段进行通信的进程必须把这个区域放到进程自己的地址空间上。进程在共享区域内读写来交换信息。

采用共享内存能够解决生产者——消费者问题，即：为了允许生产者与消费者进程并发执行，要有一个缓冲区同时被生产者填充，并被消费者使用，这个缓冲区就驻留在两个进程的共享内存区域。有两种缓冲：

无限缓冲：缓冲大小没有限制，生产者一直生产新的项，缓冲为空时消费者要等待
有限缓冲：缓冲大小固定，缓冲为空时消费者要等待，缓冲满时生产者要等待

消息传递：

通过发送和接收消息来传递信息，不必共享内存地址空间。一般实现发送和接收消息操作的方法有：

管道，又可以分为匿名/命名管道：
- 匿名管道：一个管道和两个进程相连，管道的一端连接一个进程的输出。这个进程会向管道中放入信息。管道的另一端连接一个进程的输入，这个进程取出被放入管道的信息。由于匿名管道基于fork机制，因此匿名管道只能用于父子进程之间
- 命名管道：基于文件的路径来识别管道，能让没有亲缘关系的进程也建立连接
消息队列

通信进程交换的消息驻留在临时队列中，本质上消息队列是消息的链表。可以根据定义队列的容量，改变队列的缓存能力。一般来说，消息队列容量比管道大。

套接字(Socket)：

Socket是应用层和传输层之间的一个抽象层，把TCP/IP层的操作抽象成简单接口，供应用层调用。两个进程即便不在同一台计算机，只要有网络连接，也能相互通信。同时Socket的设计也能清楚的将服务器端和客户端区分开。具体工作流程见计算机网络部分。

信号量：

信号量（Semaphore）是一个同步对象，用于保持在0至指定整数最大值之间的一个计数值。当线程需要资源时，会对该信号量对象执行wait()操作，信号量计数值减一；当线程释放资源时，会对该信号量对象执行signal()操作，信号量计数值加一。

多线程模型

两种线程：

用户线程：位于用户层，受内核支持，无须内核管理
内核线程：由操作系统直接支持管理

多线程模型：用于提供线程支持

多对一模型：
- 许多用户级线程映射到一个内核线程，线程管理由线程库在用户空间进行
- 如果一个线程执行阻塞调用，整个进程会被阻塞，因为任意一个时刻，只有一个线程能访问内核
一对一模型：
- 一个线程执行阻塞系统调用时，允许另一个线程继续执行，提供了更好的并发行
- 创建内核开销大
多对多模型：
- 开发人员可创建任意多的用户线程，相应的内核线程能在多处理器上并发执行
- 一个线程执行阻塞系统调用时，内核能调度另一个线程执行

I/O模型

常见I/O模型

阻塞I/O模型(BIO)：

进程发起I/O系统调用后，进程被阻塞，转到内核空间处理，整个I/O处理完毕后返回进程。操作成功则进程获取到数据
进程阻塞挂起不消耗CPU资源，及时响应每个操作
不适用并发量大的应用，因为一个请求I/O会阻塞进程，所以，得为每个请求分配一个处理进程（线程）以及时响应，系统开销大

非阻塞I/O模型(NIO)：

进程发起I/O系统调用后，如果内核缓冲区没有数据，需要到I/O设备中读取，进程返回一个错误而不会被阻塞；一旦内核缓冲区有数据，内核就会把数据返回给进程
不会阻塞在内核的等待数据过程，每次发起的I/O请求可以立即返回，不用阻塞等待。在数据量收发不均，等待时间随机性极强的情况下比较常用
进程重复调用recvfrom，试图获取数据，消耗CPU的资源

I/O多路复用模型(IO multiplexing)：

多个的进程的I/O可以注册到一个复用器（select）上，然后用一个进程调用该select，select会监听所有注册进来的I/O，如果监听的IO在内核缓冲区都没有可读数据，select的调用进程会被阻塞；而当任一IO在内核缓冲区中有可数据时，select调用就会返回。select调用进程可以通知另外的进程（注册进程）再次发起读取IO，读取内核中准备好的数据。
除了select，Linux中还拥有几个调用来实现I/O复用的系统调用，例如poll和epoll
- Select：进程能够监视的文件描述符的数量存在最大限制，注册I/O、阻塞扫描，监听的I/O最大连接数不能多于FD_SIZE；只能无差别轮询所有流；内核需要将消息传递到用户空间，需要内核拷贝动作
- Poll：原理和Select相似，只是使用链表保存文件描述符，没有最大连接数的限制；仍然只能无差别轮询所有流；内核需要将消息传递到用户空间，需要内核拷贝动作
- Epoll ：event poll，会把哪个流发生了怎样的I/O事件通知我们。所以epoll实际上是事件驱动，只有活跃可用的FD才会调用callback函数；没有最大并发连接的限制，只管“活跃”的连接，而跟连接总数无关；内存拷贝，利用mmap()文件映射内存，让内核和用户空间共享一块内存，减少复制开销

异步I/O模型(AIO)：

当进程发起一个I/O操作，进程不被阻塞，继续执行；内核把整个I/O处理完后，会通知进程结果。如果IO操作成功则进程直接获取到数据。
不阻塞，数据一步到位
非常适合高性能高并发应用

I/O种类对比

同步vs异步：线程的执行过程中，产生一个系统调用，如果需要等待该调用返回才能继续线程流则叫做同步，不需要等待结果返回线程流可以继续往下执行的情况叫做异步。

同步：双方的动作是经过双方协调的，步调一致的
异步：双方并不需要协调，都可以随意进行各自的操作。

阻塞vs非阻塞：线程执行过程中，产生一个系统调用后，如果线程流会被这个调用“堵”住，对应的是阻塞，反之为非阻塞。

CPU调度

简介

每当CPU空闲时，操作系统必须从就绪队列选择一个进程执行，进程选择由短期调度程序或者CPU调度程序执行。

多道程序的目标是任何时候都有某些进程都在运行，使得CPU的使用率最大化。很多时候，进程执行到一半需要等待（例如等待I/O完成），这时候CPU就会空闲。因此，当进程必须等待时，操作系统会从该进程拿走CPU使用权，将CPU交给其他进程。

长期/短期调度程序

对于批处理系统，进程更多是被提交到磁盘的缓冲池，保存在这里以便以后执行。

长期调度程序，或作业调度程序，从这个缓冲池里选择进程，装入内存以准备执行。长期调度程序控制着多道程序设计的程度（内存中的进程数量）。短期调度程序，或CPU调度程序，从准备执行的进程中选择进程，为之分配CPU。有的操作系统还有中期调度程序，将进程从内存中移出，之后再被重新调入，从中断处继续执行（交换）。

上下文切换

进程上下文一般是用进程进程控制块(PCB)表示，包括CPU寄存器的值、程序计数器、内存管理信息等等。上下文切换指将一个进程的上下文存储到系统内核中，然后将另一个进程的上下文恢复加载到CPU中。前一个进程的执行将在之后任务重新调度执行的时候再次被加载，并保证任务原来的状态不受影响。

上下文切换保证了多个进程可以共享一个CPU，并且每个任务不会受到其他任务的影响。但它会消耗CPU资源，降低系统的整体性能。

常见CPU调度算法

FCFS：先请求CPU的进程先分配到CPU
- 平均等待时间较长
最短作业优先：CPU优先分配给具有最短CPU区间的进程
- 可证明是最佳，然而需要预知未来，知道下一个CPU区间的长度
优先级调度：每个进程分配优先级，最高优先级的进程分配到CPU
- 低优先级的进程可能会无穷等待(starve)，解决方法是老化(aging)，逐渐增加在系统中等待很长时间的进程优先级
- 轮转法：定义一个较小的时间单元——时间片，每个进程循环分配不超过一个时间片的CPU，执行时间到了就产生操作系统中断，进行上下文切换，把当前进程移到就绪队列的尾部
  - 性能依赖于时间片的大小
- 多级队列调度：就绪队列被分成多个独立队列，每个进程根据自己的属性，比如内存大小、优先级、进程类型等等，被永久分到其中一个队列中，每个队列有自己的调度算法
  - 低调度开销，但不够灵活
- 多级反馈队列调度：允许进程在队列之中移动，例如某些进程使用过多CPU时间，就会转移到低优先级队列；或者等待时间久的进程会转移到高优先级队列

进程/线程同步

锁的种类

互斥锁和条件变量
- 当获取锁后但是条件失败，那么会释放当前锁(另外的线程可以获得锁，以解除死锁)，然后在此阻塞(避免条件判断需要不但轮询浪费CPU时间)。进程将睡眠等待某种条件出现
- 一个线程等待”条件变量的条件成立”而挂起；另一个线程使“条件成立”
读写锁
- 允许多个线程同步访问一个文件内存都用读锁；只要有一个线程申请或拥有写锁，其它线程申请或拥有读锁或者写锁，那么申请写锁的必须等待，或者其它线程申请锁必须等待
自旋锁
- 线程反复检查锁是否可用。一旦获取了自旋锁，线程会一直保持该锁，一直到释放自旋锁。线程在这一过程中保持执行，处于忙等待中
- 避免了进程上下文的调度开销，对于线程只会阻塞很短时间的场合是有效的

信号量与互斥锁

互斥锁（Mutex）是多线程编程中，防止两条线程同时对同一公共资源（比如全局变量）进行读写的机制。

主要区别：

设计理念上，互斥锁管理的是资源的使用权，主要是构造临界区来保护共享资源；而信号量管理的是资源的数量，同时间接在调度线程，服务于多个线程之间的执行顺序
互斥锁只允许一个线程进入临界区，其他试图进入临界区的线程要全部等待直到这个线程执行完毕。这使得互斥锁安全得多，但是会增加线程等待时间。而信号量仅仅限制了共享资源的数量，在这个限制数量内多个线程可以同时访问这些资源，这带来了更多的并发可能性并且加快了程序运行效率，然而不够安全。

虚假唤醒(Spurious Wakeup)

在多核处理器下，当一个线程调用pthread_cond_signal()后，多个调用pthread_cond_wait()或pthread_cond_timedwait()的线程被激活返回。这种效应成为”虚假唤醒”。

通常的解决方法是把条件判断从if改成while，不仅在等待条件变量前检查条件变量是否有效，还在等待条件变量后也检查条件变量是否有效。

死锁

简介

多任务系统下，存在两个以上的进程，其中的每个进程都在等待系统资源，而所需资源本身被自身或其他进程占用。这种状态下，每个进程只能等待其他进程停止运行并释放资源（可能是物理资源或逻辑资源等等）。如果并没有一个进程提前退出，此时这组进程就处于死锁状态。

触发的条件：

互斥：所需的资源非共享，一次只有一个进程能使用这个资源
占有并等待：一个进程占有一个资源，等待另一个资源，等待的资源被其他资源占有
非抢占：资源只能在进程完成任务后自动释放，不能被中途抢占
循环等待：对于一组等待进程{P, P, … P}，会形成循环等待链，即P等待的资源被P占有，P等待的资源被P占有，…，P等待的资源被P占有

预防、检测、解决

死锁预防：修改系统协议

适当多使用共享资源，比如设立只读文件，让多个进程同时访问
规定进程没有资源了才能申请资源，或执行前一次性获得所有资源确保能执行完毕
一个进程占有资源并申请另一个需要等待的资源时，它已有的资源可以被抢占
对资源类型完全排序，要求进程按递增顺序申请资源

死锁检测：

资源分配图算法，检测图中是否有环
银行家算法，动态比较已分配资源/需要资源/系统可用资源，计算剩余资源是否够用

死锁恢复：

进程终止，包括终止所有进程，或一次性终止一个直到打破死锁循环
抢占资源，优先保证让一些进程先执行完毕，打破死锁循环

内存管理

交换(Swap)

内存管理器可以将进程暂时从内存中换出到备份存储（一般是磁盘）上，当需要再次执行时再换入到内存中。

一个交换出的进程可能会换回原有的内存空间，这一限制由地址绑定方式决定。如果绑定在汇编或加载时确定，就必须移动到原有的位置；如果运行时才确定，就可能回到其他物理地址空间上。

连续内存

将内存分为多个固定大小的分区(partition)，每个进程位于一个连续的内存区域中，每个分区只能容纳一个进程。

优点：

实现简单，易于管理
降低逻辑内存到物理内存的映射开销

缺点：

碎片问题，浪费内存空间 (解决：移动空闲空间，合并成一大块)

内存分页

将物理内存分为固定大小的块（帧），将逻辑内存分为同样大小的块（页）。执行进程时，把页通过页表映射，从备份存储中调入到可用的内存帧中。

CPU生成的逻辑地址分为两部分：

页号：页表中的索引
页偏移

页表包含每页所在物理内存的基地址，这些基地址和页偏移的组合就形成了物理地址。

分页不会产生外部碎片（总的可用内存空间够容纳进程，但这些内存空间不连续），更好地利用了内存空间，但仍然有内部碎片（给进程分配的内存可能比所需要的要大）

虚拟内存

简介

计算机系统内存管理的一种技术。它提供了一个抽象的存储资源，它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间）。而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

虚拟内存有着以下好处：

程序不会受到物理内存空间的限制，所以程序员可以在一个理想的巨大的、连续的虚拟地址空间上进行开发
每个程序使用的物理内存较少，因此可以同时运行更多的程序，提高了CPU的利用率
由于内存隔离，增加了安全性

虚拟内存到物理内存的映射

使用内存管理单元将逻辑页面映射到内存的物理页帧：访问内存时，系统判断该虚拟地址映射后的结果是否在物理内存中。如果是，就进行地址转换，访问物理内存；否则，将辅存中的部分程序调度进物理内存，再用进行地址转换和访问。

页错误

操作系统有按需调页机制，程序执行时一部分程序被载入到内存，另一部分在二级存储器上。当程序执行需要到某个特定的页，而这个页面不在内存中时，才把它从其他存储器调入内存。

当进程试图访问尚未调入内存的页时，就会触发页错误。一般的处理流程如下：

先检查进程的内部页表，确定这是不是合法的地址访问，如果不合法进程会被终止
找到一个空闲帧，调度磁盘操作，将需要的页调入
修改页表和进程的内部表，表示该页已经处在内存中
重新执行中断的指令

页置换

当程序运行需要读一个新页面到内存，又没有空闲帧的时候，使用页置换算法选择一个牺牲帧，把这个帧的内容写到磁盘上，修改页表和帧表；再把所需的页面读入腾出来的空闲帧，修改页表和帧表。最后重启用户进程。

常见算法：

FIFO：选择时间上最早调入内存的页进行替换
最优置换：错误率最低，但要预知未来的页面读入情况，理论上很难实现
LRU：选择最长时间没有使用的页进行替换
LFU / MFU：最不经常 / 最经常使用的页被替换

文件系统

存储层次

读写速度从快到慢，容量从小到大：

寄存器
缓存
（主）内存
硬盘
软盘、光盘、U盘….

数据无法长期保留在寄存器、缓存、内存中（断电就消失了）；而且这些存储设备容量很小，扩容成本很高。这些问题带来了多层存储的必要性。

缓存友好的代码

两个局部性原则：

时间局部性：某个内存位置被访问后，在不久之后的将来，这个位置可能还会被访问，因此数据可以缓存在原来的位置
空间局部性：将相关的数据放在彼此接近的地方，例如数组中的数据存储在连续的内存中，利于设计缓存机制访问

缓存替换策略

近期最少使用(LRU)：
- 把CPU近期最少使用的块替换出去。这种替换方法需要随时记录Cache中各块的使用情况，以便确定哪个块是近期最少使用的块。每块也设置一个计数器，被调入或者被替换的块，计数器清零，而其它的计数器则加“1”。访问命中缓存块时，这块的计数器也清零。需要替换时，则选择计数值最大的块被替换。
- 保护了刚调入缓存的新数据块，具有较高的命中率
- 实现以及维护的开销大
随机替换：
- 随机地确定替换的存储块。设置一个随机数产生器，依据所产生的随机数，确定替换块
- 方法简单、易于实现
- 命中率低
先进先出：
- 选择最先调入的缓存块进行替换
- 命中率比随机替换高一些，总体实现也较为简单
- 最先调入并被多次命中的块，很可能被优先替换，因而不符合局部性规律

磁盘调度算法

磁盘队列：I/O对磁盘各个柱面上块的请求访问顺序

FCFS：先来先服务，通常不是最快的
SSTF：优先处理靠近当前磁头位置的请求
SCAN：磁臂从磁盘一端向另一端移动，磁头经过每个柱面时，处理该柱面上的服务请求；到达另一端时，磁头改变移动方向，继续处理
CSCAN：到达另一端时，磁头直接返回到开始，不处理请求
LOOK：磁头只移动到一个方向上最远的请求为止，之后就掉转方向处理
CLOOK：到达最远请求时，磁头直接返回到开始，不处理请求

磁盘分配

连续内存分配每个文件都存储在一组连续的块中。顺序访问和直接访问都很容易实现。但是，很难找到新文件的空间（外部碎片）。此外，文件大小很难扩展。

链式分配磁盘块通过指针连接。这样一来，文件很容易扩展，而且消除了外部碎片。但是，linkded分配不支持直接访问，且指针会占用一些额外的空间。一个可能的节省空间的方法是将几个块组成一个群组，然而这将引入内部碎片。

索引分配每个文件都有一个索引块。第i项指向文件的第i块。在这种情况下，既支持直接访问，也支持顺序访问，而且不存在外部碎片。但是，索引分配浪费一些空间，因为指针和索引块本身都会占用额外的空间。如果块的大小受到限制，可以引入层次索引。

PREVIOUS计算机网络

NEXT数据结构