操作系统

常见的操作系统

Windows和Linux，它们的区别在于内核不同

计算机是由各种外部硬件设备组成的，比如内存、cpu、硬盘等，如果每个应用都要和这些硬件设备对接通信协议，那这样太累了，所以这个中间人就由内核来负责，让内核作为应用连接硬件设备的桥梁，应用程序只需关心与内核交互，不用关心硬件的细节。

内核有哪些能力呢？现代操作系统，内核一般会提供 4个基本能力:

  1. 管理进程、线程，决定哪个进程、线程使用 CPU，也就是进程调度的能力;
  2. 管理内存，决定内存的分配和回收，也就是内存管理的能力;
  3. 管理硬件设备，为进程与硬件设备之间提供通信能力，也就是硬件通信能力;。
  4. 提供系统调用，如果应用程序要运行更高权限运行的服务，那么就需要有系统调用，它是用户程序与操。作系统之间的接口。

内核具有很高的权限，可以控制 cpu、内存、硬盘等硬件，而应用程序具有的权限很小，因此大多数操作系统，把内存分成了两个区域:

  1. 内核空间，这个内存空间只有内核程序可以访问；
  2. 用户空间，这个内存空间专门给应用程序使用；

用户空间的代码只能访问一个局部的内存空间，而内核空间的代码可以访问所有内存空间。因此，当程序使用用户空间时，我们常说该程序在用户态执行，而当程序使内核空间时，程序则在内核态执行。

内核程序执行在内核态，用户程序执行在用户态。当应用程序使用系统调用时，会产生一个中断。发生中断后，CPU 会中断当前在执行的用户程序，转而跳转到中断处理程序，也就是开始执行内核程序。内核处理完后，主动触发中断，把CPU 执行权限交回给用户程序，回到用户态继续工作。

操作系统的定义与目标

定义：操作系统是控制管理计算机系统的硬软件，分配调度资源的系统软件。

目标：方便性，有效性（提高系统资源的利用率、提高系统的吞吐量），可扩充性，开放性。

操作系统的基本功能

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

操作系统的特征

最基本的特征，互为存在条件：并发，共享；

（1）并行：指两个或多个事件可以在同一个时刻发生，多核CPU可以实现并行，一个cpu同一时刻只有一个程序在运行；

（2）并发：指两个或多个事件可以在同一个时间间隔发生，用户看起来是每个程序都在运行，实际上是每个程序都交替执行。

（3）共享性：操作系统的中资源可供多个并发的程序共同使用，这种形式称之为资源共享。

互斥共享：当资源被程序占用时，其它想使用的程序只能等待。
同时访问：某种资源并发的被多个程序访问。
虚拟和异步特性前提是具有并发性。

（4）虚拟性：表现为把一个物理实体转变为若干个逻辑实体。

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

操作系统的中断处理

中断机制的作用：为了在多道批处理系统中让用户进行交互；

中断产生：

发生中断时，CPU立马切换到管态，开展管理工作；（管态又叫特权态，系统态或核心态，是操作系统管理的程序执行时，机器所处的状态。）
发生中断后，当前运行的进程回暂停运行，由操作系统内核对中断进行处理；
对于不同的中断信号，会进行不同的处理。
中断的分类：

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

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

进程

进程

进程是一个程序在运行中的实例，是操作系统分配资源的基本单位。一个进程包含了运行的程序代码和它所使用的资源，比如内存、文件、I/O设备等。每个进程都有自己独立的内存空间。进程之间是相互隔离的，通常一个进程的故障不会影响到其他进程。

  • 独立的内存空间
  • 进程间相互隔离，稳定性高
  • 进程切换开销较大，因为需要保存和恢复不同的内存状态

线程

线程是进程中的一个执行单元，一个进程可以包含多个线程。线程之间共享进程的资源（如内存、文件等），但它们有各自的执行栈和程序计数器。相比进程，线程更加轻量级，线程之间的切换成本更低。

  • 线程共享进程的内存和资源
  • 线程切换开销较小，效率高
  • 同一进程中的线程可以同时执行，提高并发能力

进程与线程的区别

  1. 资源独立性：进程拥有独立的资源（如内存），而线程共享进程的资源。
  2. 执行效率：线程的切换速度比进程快，因为线程共享进程的资源。
  3. 稳定性：进程隔离性强，一个进程崩溃不会影响其他进程，而线程间共享资源，可能会导致线程间的互相影响。

进程管理之进程实体

为什么需要进程：

进程是系统进行资源分配和调度的基本单位；
进程作为程序独立运行的载体保障程序正常执行；
进程的存在使得操作系统资源的利用率大幅提升。+
进程控制块（PCB）：用于描述和控制进程运行的通用数据结构,记录进程当前状态和控制进程运行的全部信息，是进程存在的唯一标识。

进程（Process）与线程（Thread）：

线程：操作系统进行运行调度的最小单位。
进程：系统进行资源分配和调度的基本单位。
区别与联系：

一个进程可以有一个或多个线程；
线程包含在进程之中，是进程中实际运行工作的单位；
进程的线程共享进程资源；
一个进程可以并发多个线程，每个线程执行不同的任务。

状态

创建、就绪、运行、阻塞、结束

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

如果有大量处于阻塞状态的进程，进程可能会占用着物理内存空间，显然不是我们所希望的，毕竟物理内存空间是有限的，被阻塞状态的进程占用着物理内存就一种浪费物理内存的行为。所以，在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存。

那么，就需要一个新的状态，来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。这跟阻塞状态是不一样，阻塞状态是等待某个事件的返回。

另外，挂起状态可以分为两种：

  • 阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
  • 就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还包括如下情况：

  • 通过 sleep 让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程。
  • 用户希望挂起一个程序的执行，比如在 Linux 中用 Ctrl+Z 挂起进程；

进程的控制结构

在操作系统中，是用进程控制块（process control block，PCB）数据结构来描述进程的。PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。

进程描述信息：

  • 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
  • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；

进程控制和管理信息：

  • 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
  • 进程优先级：进程抢占 CPU 时的优先级；

资源分配清单：

  • 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

CPU 相关信息：

  • CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。

通常是通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。比如：

  • 将所有处于就绪状态的进程链在一起，称为就绪队列；
  • 把所有因等待某事件而处于等待状态的进程链在一起就组成各种阻塞队列；
  • 另外，对于运行队列在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。

除了链接的组织方式，还有索引方式，它的工作原理：将同一状态的进程组织在一个索引表中，索引表项指向相应的 PCB，不同状态对应不同的索引表。

一般会选择链表，因为可能面临进程创建，销毁等调度导致进程状态发生变化，所以链表能够更加灵活的插入和删除。

进程管理之进程同步

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

产生问题：当两者并发执行时可能出差错，导致预期的结果与真实的结果不相符：当执行生产者+1和消费者-1操作之后，缓冲区的值从10变为了11。

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

这会导致以下的问题，筷子就相当于临界资源：

临界资源指的是一些虽作为共享资源却又无法同时被多个线程共同访问的共享资源。当有进程在使用临界资源时，其他进程必须依据操作系统的同步机制等待占用进程释放该共享资源才可重新竞争使用共享资源。

进程同步的作用：对竞争资源在多进程间进行使用次序的协调，使得并发执行的多个进程之间可以有效使用资源和相互合作。

进程间同步的四原则：

空闲让进：资源无占用，允许使用；
忙则等待：资源被占用，请求进程等待；
有限等待：保证有限等待时间能够使用资源；
让权等待：等待时，进程需要让出CPU。

进程同步的方法

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

fork系统调用是用于创建进程的；
fork创建的进程初始化状态与父进程一样；
系统会为fork的进程分配新的资源
2.共享内存：在某种程度上，多进程是共同使用物理内存的，但是由于操作系统的进程管理，进程间的内存空间是独立的，因此进程默认是不能访问进程空间之外的内存空间的。

共享存储允许不相关的进程访问同一片物理内存；
共享内存是两个进程之间共享和传递数据最快的方式；
共享内存未提供同步机制，需要借助其他机制管理访问；
image-20210826223244411

3.Unix域套接字

域套接字是一种高级的进程间通信的方法，可以用于同一机器进程间通信。

套接字（socket）：为网络通信中使用的术语。

Unix系统提供的域套接字提供了网络套接字类似的功能，如Nfinx、uWSGI等。

服务端和客户端分别使用Unix域套接字的过程：

线程同步的方法

线程同步的方法：

互斥锁：互斥锁是最简单的线程同步的方法，也称为互斥量，处于两态之一的变量：解锁和加锁，两个状态可以保证资源访问的串行。 原子性：指一系列操作不可被中断的特性，要么全部执行完成，要么全部没有执行。

image-20210826220013572

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

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

条件变量：是一种相对比较复杂的线程同步方法，条件变量允许线程睡眠，直到满足某种条件，当满足条件时，可以给该线程信号通知唤醒。

Linux的进程管理

进程的类型：

前台进程：具有终端，可以和用户交互；
后台进程：没有占用终端，基本不和用户交互，优先级比前台进程低（将需要执行的命令以“&”符号结束）；
守护进程：特殊的后台进程，在系统引导时启动，一直运行直到系统关闭（进程名字以“d”结尾的一般都是守护进程），如crond、sshd、httpd、mysqld…
进程的标记：

进程ID：非负整数，进程的唯一标记，每个进程拥有不同的ID；
进程的状态标记：R表示进程处于运行状态，S表示进程处于睡眠状态…

操作Linux进程的相关命令：

ps命令：列出当前的进程，结合-aux可以打印进程的详细信息（ps -aux）；
top命令：查看所有进程的状态；
kill命令：给进程发送信号。

作业管理

3.1 作业管理之进程调度
定义：指计算机通过决策决定哪个就绪进程可以获得CPU使用权。

什么时候需要进程调度？

主动放弃：进程正常终止；运行过程中发生异常而终止；主动阻塞（如等待I/O）；
被动放弃：分给进程的时间片用完；有更高优先级的进程进入就绪队列；有更紧急的事情需要处理（如I/O中断）；
进程调度方式：

非抢占式调度：只能由当前运行的进程主动放弃CPU；

处理器一旦分配给某个进程，就让该进程一直使用下去；
调度程序不以任何原因抢占正在被使用的处理器；
调度程序不以任何原因抢占正在被使用的处理器；
抢占式调度：可由操作系统剥夺当前进程的CPU使用权。

允许调度程序以一定的策略暂停当前运行的进程；
保存好旧进程的上下文信息，分配处理器给新进程；
image-20210826162907842

进程调度的三大机制：

就绪队列的排队机制：为了提高进程调度的效率，将就绪进程按照一定的方式排成队列，以便调度程序可以最快找到就绪进程。

image-20210830141937877

选择运行进程的委派机制：调度程序以一定的策略，选择就绪进程，将CPU资源分配给它。

新老进程的上下文切换机制：保存当前进程的上下文信息，装入被委派执行进程的运行上下文。
image-20210830141949702

进程调度算法：

先来先服务算法：按照在就绪队列中的先后顺序执行。
短进程优先调度算法：优先选择就绪队列中估计运行时间最短的进程，不利于长作业进程的执行。
高优先权优先调度算法：进程附带优先权，优先选择权重高的进程，可以使得紧迫的任务优先处理。
时间片轮转调度算法：按照FIFO的原则排列就绪进程，每次从队列头部取出待执行进程，分配一个时间片执行，是相对公平的调度算法，但是不能保证就是响应用户。
3.2 作业管理之死锁
3.2.1 进程死锁、饥饿、死循环的区别：
死锁：两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。永远在互相等待的进程称为死锁进程。

饥饿：由于长期得不到资源导致进程无法推进；

死循环：代码逻辑BUG。

死锁的产生：竞争资源（共享资源数量不满足各进程需求）、进程调度顺序不当，当调度顺序为A->B->C->D时会产生死锁，但改为A->D->B->C则不会产生。

image-20210826163418015

死锁的四个必要条件：

互斥条件：必须互斥使用资源才会产生死锁；
请求保持条件：进程至少保持一个资源，又提出新的资源请求，新资源被占用，请求被阻塞，被阻塞的进程不释放自己保持的资源；
不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺（包括OS），只能由进程自身释放；
环路等待条件：发生死锁时，必然存在进程-资源环形链,环路等待不一定造成死锁，但是死锁一定有循环等待。
死锁的处理策略：

一.预防死锁的方法：破坏四个必要条件的中一个或多个。

破坏互斥条件：将临界资源改造成共享资源（Spooling池化技术）；（可行性不高，很多时候无法破坏互斥条件）
破坏请求保持条件：系统规定进程运行之前，一次性申请所有需要的资源；（资源利用率低，可能导致别的线程饥饿）
破坏不可剥夺条件：当一个进程请求新的资源得不到满足时，必须释放占有的资源；（实现复杂，剥夺资源可能导致部分工作失效，反复申请和释放造成额外的系统开销）
破坏环路等待条件：可用资源线性排序，申请必须按照需要递增申请；（进程实际使用资源顺序和编号顺序不同，会导致资源浪费）
二.银行家算法：检查当前资源剩余是否可以满足某个进程的最大需求；如果可以，就把该进程加入安全序列，等待进程允许完成，回收所有资源；重复1，2，直到当前没有线程等待资源；

三.死锁的检测和解除：死锁检测算法，资源剥夺法，撤销进程法（终止进程法），进程回退法；

存储管理

存储管理为了确保计算机有足够的内存处理数据；确保程序可以从可用内存中获取一部分内存使用；确保程序可以归还使用后的内存以供其他程序使用。

4.1 存储管理之内存分配与回收
内存分配的过程：单一连续分配（已经过时）、固定分区分配、动态分区分配（根据实际需要，动态的分配内存）。
  动态分区分配算法：

首次适应算法：分配内存时，从开始顺序查找适合内存区，若无合适内存区，则分配失败，每次从头部开始，使得头部地址空间不断被划分；
最佳适应算法：要求空闲区链表按照容量大小排序，遍历以找到最佳适合的空闲区（会留下越来越多的内部碎片）。
快速适应算法：要求有多个空闲区链表，每个空闲区链表存储一种容量的空闲区。
内存回收的过程：

回收区在空闲区下方：不需要新建空闲链表节点；只需要把空闲区1的容量增大即可；
回收区在空闲区上方：将回收区与空闲区合并；新的空闲区使用回收区的地址；
回收区在空闲区中间方：将空闲区1、空闲区2和回收区合并；新的空闲区使用空闲区1的地址；
仅仅剩余回收区：为回收区创建新的空闲节点；插入到相应的空闲区链表中去；
4.2 存储管理之段页式存储管理
页式存储管理：将进程逻辑空间等分成若干大小的页面，相应的把物理内存空间分成与页面大小的物理块，以页面为单位把进程空间装进物理内存中分散的物理块。

页面大小应该适中，过大难以分配，过小内存碎片过多；页面大小通常是512B~8K；

现代计算机系统中，可以支持非常大的逻辑地址空间(232~264)，具有32位逻辑地址空间的分页系统，规定页面大小为4KB，则在每个进程页表中的页表项可达1M(2个20)个，如果每个页表项占用1Byte，故每个进程仅仅页表就要占用1MB的内存空间。

image-20210830150815294

段式存储管理：将进程逻辑空间分成若干段（不等分），段的长度由连续逻辑的长度决定。

页式和者段式存储管理相比：

段式存储和页式存储都离散地管理了进程的逻辑空间；
页是物理单位，段是逻辑单位；
分页是为了合理利用空间，分段是满足用户要求页大小由硬件固定，段长度可动态变化；
页表信息是一维的，段表信息是二维的；
段页式存储管理：现将逻辑空间按照段式管理分成若干段，再将内存空间按照页式管理分成若干页，分页可以有效提高内存利用率，分段可以更好的满足用户需求。

image-20210826165620416

4.3 存储管理之虚拟内存
虚拟内存概述：是操作系统内存管理的关键技术，使得多道程序运行和大程序运行成为现实，把程序使用内存划分，将部分暂时不使用的内存放置在辅存，实际是对物理内存的扩充。
  局部性原理：指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。
  虚拟内存的置换算法：先进先出（FIFO）、最不经常使用（LFU）、最近最少使用（LRU）

虚拟内存的特征：

多次性：无需再作业运行时一次性全部装入内存，而是允许被分成多次调入内存；
对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出；
虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存用来，远大于实际的容量；
4.4 Linux的存储管理
Buddy内存管理算法：经典的内存管理算法，为解决内存外碎片的问题，算法基于计算机处理二进制的优势具有极高的效率。
  Linux交换空间：交换空间（Swap）是磁盘的一个分区，Linux内存满时，会把一些内存交换至Swap空间，Swap空间是初始化系统时配置的。
  Swap空间与虚拟内存的对比：

image-20210830151958862

五、文件管理
5.1 操作系统的文件管理
文件的逻辑结构：

逻辑结构的文件类型：有结构文件（文本文件，文档，媒体文件）、无结构文件（二进制文件、链接库）。
顺序文件：按顺序放在存储介质中的文件，在逻辑文件当中存储效率最高，但不适合存储可变长文件。
索引文件：为解决可变长文件存储而发明，需要配合索引表存储。
辅存的存储空间分配：

辅存的分配方式：连续分配（读取文件容易，速度快）、链接分配（隐式链接和显式链接）、索引分配
辅存的存储空间管理：空闲表、空闲链表、位示图。
目录树：使得任何文件或目录都有唯一的路径。

image-20210830152736217

Linux文件的基本操作：参考链接

image-20210826213430203

img

image-20210826214028660

Linux的文件系统：FAT、NTFS（对FAT进行改进）、EXT2/3/4（扩展文件系统，Linux的文件系统）

设备管理

I/O设备的基本概念：将数据输入输出计算机的外部设备；

广义的IO设备：

按照使用特性分类：存储设备（内存、磁盘、U盘）和交互IO设备（键盘、显示器、鼠标）；
按照信息交换分类：块设备（磁盘、SD卡）和字符设备（打印机、shell终端）；
按照设备共享属性分类：独占设备，共享设备，虚拟设备；
按照传输速率分类：低速设备，高速设备；
IO设备的缓冲区：减少CPU处理IO请求的频率，提高CPU与IO设备之间的并行性。

SPOOLing技术：虚拟设备技术，把同步调用低速设备改为异步调用，在输入、输出之间增加了排队转储环节(输入井、输出井)，SPoOLing负责输入（出）井与低速设备之间的调度，逻辑上，进程直接与高速设备交互，减少了进程的等待时间。

实现支持异步任务的线程池

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

使用线程池的原因：

线程是稀缺资源 ，不应该频繁创建和销毁；
架构解耦，业务创建和业务处理解耦，更加优雅；
线程池是使用线程的最佳实践。
实现线程安全的队列Queue

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

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

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

实现任务处理线程池Pool：存放多个任务处理线程，负责多个线程的启停，管理向线程池的提交任务，下发给线程去执行。
实现的基本过程：基本属性，提交任务（put，batch_put），线程启停（start，join），线程池大小（size）。

实现异步任务处理AsyncTask：给任务添加一个标记，任务完成后，则标记为完成；任务完成时可直接获取任务运行结果；任务未完成时，获取任务结果，会阻塞获取线程。
主要实现的两个函数：设置运行结果（set_result），获取运行结果（get_result)

进程

和线程的区别？

  • 调度：进程是资源管理的基本单位，线程是程序执行的基本单位。
  • 切换：线程上下文切换比进程上下文切换要快得多。
  • 拥有资源： 进程是拥有资源的一个独立单位，线程不拥有系统资源，但是可以访问隶属于进程的资源。
  • 系统开销： 创建或撤销进程时，系统都要为之分配或回收系统资源，如内存空间，I/O设备等，OS所付出的开销显著大于在创建或撤销线程时的开销，进程切换的开销也远大于线程切换的开销。

协程与线程的区别？

  • 线程和进程都是同步机制，而协程是异步机制。
  • 线程是抢占式，而协程是非抢占式的。需要用户释放使用权切换到其他协程，因此同一时间其实只有一个协程拥有运行权，相当于单线程的能力。
  • 一个线程可以有多个协程，一个进程也可以有多个协程。
  • 协程不被操作系统内核管理，而完全是由程序控制。线程是被分割的CPU资源，协程是组织好的代码流程，线程是协程的资源。但协程不会直接使用线程，协程直接利用的是执行器关联任意线程或线程池。
  • 协程能保留上一次调用时的状态。

并发和并行

  • 并发就是在一段时间内，多个任务都会被处理；但在某一时刻，只有一个任务在执行。单核处理器可以做到并发。比如有两个进程A和B，A运行一个时间片之后，切换到B，B运行一个时间片之后又切换到A。因为切换速度足够快，所以宏观上表现为在一段时间内能同时运行多个程序。
  • 并行就是在同一时刻，有多个任务在执行。这个需要多核处理器才能完成，在微观上就能同时执行多条指令，不同的程序被放到不同的处理器上运行，这个是物理上的多个进程同时进行。

进程和线程切换流程

进程切换分为两步：

  1. 切换页表以使用新的地址空间，一旦去切换上下文，处理器中所有已经缓存的内存地址一瞬间都作废了。
  2. 切换内核栈和硬件上下文。

对于linux来说，线程和进程的最大区别就在于地址空间，对于线程切换，第1步是不需要做的，第2步是进程和线程切换都要做的。

因为每个进程都有自己的虚拟地址空间，而线程是共享所在进程的虚拟地址空间的，因此同一个进程中的线程进行线程切换时不涉及虚拟地址空间的转换。

进程通信方式

进程间通信（Inter-Process Communication，IPC）是指在操作系统中不同进程之间交换数据或信息的机制。以下是常见的几种进程间通信方式：

  1. 管道（Pipe）

    • 无名管道（Anonymous Pipe）：用于有亲缘关系的进程之间的单向通信。数据通过管道从一个进程写入，另一个进程读取。通常用于父子进程之间。
    • 命名管道（Named Pipe, FIFO）：允许无亲缘关系的进程之间进行双向通信。命名管道具有一个路径名，任何进程都可以通过路径名访问它。

  2. 消息队列（Message Queue）

    • 消息队列允许进程通过发送和接收消息来进行通信。消息队列克服了管道的同步问题，能够在进程之间传递结构化数据，支持异步通信。

  3. 共享内存（Shared Memory）

    • 共享内存是最快的一种进程间通信方式。多个进程可以共享同一块内存区域，彼此读写数据。由于不涉及内核开销，因此效率较高。不过，多个进程需要通过信号量或互斥锁来同步访问共享的内存区域。

  4. 信号量（Semaphore）

    • 信号量主要用于控制对共享资源的访问，用于解决同步问题。它可以用于进程之间的同步，而不是传递大量数据。常用于协调进程对共享资源的互斥访问。

  5. 信号（Signal）

    • 信号是一种异步通知机制，用于通知进程某个事件的发生。信号不仅可以用于进程控制，还可以传递一些简单的信息（比如，指定的信号编号）。

  6. 套接字（Socket）

    • 套接字常用于网络通信，也可以用于本地进程间通信（通常使用本地域套接字）。通过套接字，进程可以在不同计算机之间或同一台计算机上通信。

  7. 内存映射文件（Memory-Mapped File）

    • 通过将文件映射到内存，可以使多个进程共享该文件的内存区域，从而实现进程间的通信。这种方式允许文件的内容在进程之间共享，而不需要显式的读写操作。

  8. 本地过程调用（Local Procedure Call, LPC）

    • 这种方式常用于操作系统内核与用户进程之间的通信，通过调用的方式，允许进程间快速交换信息。

每种通信方式都有其特定的应用场景，选择适当的IPC机制取决于进程间通信的需求，如数据传输的速度、同步的要求、通信进程的关系等。

IO多路复用

IO多路复用是指内核一旦发现进程指定的一个或者多个IO条件准备读取，它就通知该进程。IO多路复用适用如下场合：

  • 当客户处理多个描述字时（一般是交互式输入和网络套接口），必须使用I/O复用。
  • 当一个客户同时处理多个套接口时，而这种情况是可能的，但很少出现。
  • 如果一个TCP服务器既要处理监听套接口，又要处理已连接套接口，一般也要用到I/O复用。
  • 如果一个服务器即要处理TCP，又要处理UDP，一般要使用I/O复用。
  • 如果一个服务器要处理多个服务或多个协议，一般要使用I/O复用。
  • 与多进程和多线程技术相比，I/O多路复用技术的最大优势是系统开销小，系统不必创建进程/线程，也不必维护这些进程/线程，从而大大减小了系统的开销。

线程同步方式

1、临界区：当多个线程访问一个独占性共享资源时，可以使用临界区对象。拥有临界区的线程可以访问被保护起来的资源或代码段，其他线程若想访问，则被挂起，直到拥有临界区的线程放弃临界区为止，以此达到用原子方式操 作共享资源的目的。

2、事件：事件机制，则允许一个线程在处理完一个任务后，主动唤醒另外一个线程执行任务。

3、互斥量：互斥对象和临界区对象非常相似，只是其允许在进程间使用，而临界区只限制与同一进程的各个线程之间使用，但是更节省资源，更有效率。

4、信号量：当需要一个计数器来限制可以使用某共享资源的线程数目时，可以使用“信号量”对象。

区别：

  • 互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说互斥量可以跨越进程使用，但创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量 。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。
  • 互斥量，信号量，事件都可以被跨越进程使用来进行同步数据操作。

线程分类

线程根据不同的标准可以分为多种类型，常见的分类方式有以下几种：

1. 按线程的使用场景分类

  • 用户级线程（User-Level Thread）：这种线程完全由用户空间的库来管理，操作系统对这些线程的存在不可见。用户级线程的调度和切换不依赖操作系统，因此线程的切换速度较快，但由于操作系统不能感知这些线程，当一个线程发生阻塞时，会导致整个进程阻塞。
  • 内核级线程（Kernel-Level Thread）：由操作系统内核直接支持和管理的线程。操作系统能够直接调度和管理内核级线程，且可以利用多处理器实现真正的并行执行，但内核线程的切换开销较大，因为涉及到系统调用和内核态的操作。
  • 混合级线程（Hybrid Thread）：混合了用户级线程和内核级线程的优点。用户级线程通过轻量级进程（Lightweight Process, LWP）与内核级线程进行映射，操作系统感知多个内核级线程的存在，而用户线程在用户空间调度。

2. 按线程的角色分类

  • 前台线程（Foreground Thread）：通常是为用户提供直接交互的线程，如UI线程，它负责响应用户的操作和界面更新，保持应用的响应性。
  • 后台线程（Background Thread）：用于处理一些耗时任务，如文件操作、网络请求或数据处理等，而不会影响前台线程的运行，通常用于避免阻塞前台线程。

3. 按线程的实现方式分类

  • 单线程（Single Thread）：一个进程中只包含一个线程，这种模型下的进程没有并发性，所有任务都必须顺序执行。它实现简单，但处理复杂任务时效率较低。
  • 多线程（Multi-Threading）：一个进程中包含多个线程，这些线程共享进程的资源，并能够并发执行任务。多线程可以提高程序的效率和响应能力。

4. 按线程的生命周期分类

  • 短期线程（Short-Lived Thread）：生命周期很短，通常用于处理一次性的、短时间的任务，任务完成后即销毁。
  • 长期线程（Long-Lived Thread）：生命周期较长，通常用于处理需要长期运行的任务或后台服务，如守护线程、实时数据处理等。

5. 按调度优先级分类

  • 实时线程（Real-Time Thread）：这类线程具有较高的优先级，通常用于必须严格控制执行时间的任务（如嵌入式系统、音视频处理、工业控制等），操作系统会尽量确保这些线程按时执行。
  • 普通线程（Normal Thread）：执行时没有特别的实时性要求，操作系统调度这类线程时，优先级和其他普通线程相同。

6. 按是否与操作系统交互分类

  • I/O线程（I/O Thread）：专门用于处理I/O操作，如文件读写、网络请求等。这类线程的任务通常涉及与外部设备或网络的交互，容易发生阻塞。
  • 计算线程（Computation Thread）：用于处理纯计算任务，不依赖外部I/O资源的线程。CPU 密集型任务通常在这类线程中运行，注重高效的计算性能。

7. 按操作系统线程模型分类

  • 1:1 线程模型：每一个用户线程都对应一个内核线程。操作系统能够调度和管理每个线程的执行。常见于 Linux、Windows 等操作系统。
  • N:1 线程模型：多个用户线程映射到一个内核线程。所有用户线程的调度在用户空间完成，内核只处理一个线程。这种模型的效率高，但如果内核线程阻塞，则所有用户线程都会阻塞。
  • M:N 线程模型：M 个用户线程映射到 N 个内核线程。这种模型结合了 1:1 和 N:1 模型的优点，支持多线程并发执行且具有较好的调度灵活性。

不同的线程分类方式适用于不同的场景，开发者通常根据需求选择合适的线程模型或框架来实现并发处理。

中断的处理过程

  1. 保护现场：将当前执行程序的相关数据保存在寄存器中，然后入栈。
  2. 开中断：以便执行中断时能响应较高级别的中断请求。
  3. 中断处理
  4. 关中断：保证恢复现场时不被新中断打扰
  5. 恢复现场：从堆栈中按序取出程序数据，恢复中断前的执行状态。

中断和轮询的区别

  • 轮询：CPU对特定设备轮流询问。中断：通过特定事件提醒CPU。
  • 轮询：效率低等待时间长，CPU利用率不高。中断：容易遗漏问题，CPU利用率不高。

什么是临界区，如何解决冲突

每个进程中访问临界资源的那段程序称为临界区，一次仅允许一个进程使用的资源称为临界资源。

解决冲突的办法：

  • 如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入，如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待；
  • 进入临界区的进程要在有限时间内退出。
  • 如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。

死锁及产生的条件

什么是死锁

在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲就是两个或多个进程无限期的阻塞、相互等待的一种状态。

死锁产生的必要条件

  • 互斥条件：一个资源一次只能被一个进程使用
  • 请求与保持条件：一个进程因请求资源而阻塞时，对已获得资源保持不放
  • 不剥夺条件：进程获得的资源，在未完全使用完之前，不能强行剥夺
  • 循环等待条件：若干进程之间形成一种头尾相接的环形等待资源关系

如何处理死锁？

常用的处理死锁的方法有：死锁预防、死锁避免、死锁检测、死锁解除、鸵鸟策略。

死锁预防

基本思想就是确保死锁发生的四个必要条件中至少有一个不成立

  • 破除资源互斥条件
  • 破除“请求与保持”条件：实行资源预分配策略，进程在运行之前，必须一次性获取所有的资源。缺点：在很多情况下，无法预知进程执行前所需的全部资源，因为进程是动态执行的，同时也会降低资源利用率，导致降低了进程的并发性。
  • 破除“不可剥夺”条件：允许进程强行从占有者那里夺取某些资源。当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已经占有的资源会被暂时被释放，或者说被抢占了。
  • 破除“循环等待”条件：实行资源有序分配策略，对所有资源排序编号，按照顺序获取资源，将紧缺的，稀少的采用较大的编号，在申请资源时必须按照编号的顺序进行，一个进程只有获得较小编号的进程才能申请较大编号的进程。

死锁避免

死锁预防通过约束资源请求，防止4个必要条件中至少一个的发生，可以通过直接或间接预防方法，但是都会导致低效的资源使用和低效的进程执行。而死锁避免则允许前三个必要条件，但是通过动态地检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。所谓安全状态是指：如果系统能按某个顺序为每个进程分配资源（不超过其最大值），那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。银行家算法是经典的死锁避免的算法。

死锁检测

死锁预防策略是非常保守的，他们通过限制访问资源和在进程上强加约束来解决死锁的问题。死锁检测则是完全相反，它不限制资源访问或约束进程行为，只要有可能，被请求的资源就被授权给进程。但是操作系统会周期性地执行一个算法检测前面的循环等待的条件。死锁检测算法是通过资源分配图来检测是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有存在环，也就是检测到死锁的发生。

  • 如果进程-资源分配图中无环路，此时系统没有死锁。
  • 如果进程-资源分配图中有环路，且每个资源类中只有一个资源，则系统发生死锁。
  • 如果进程-资源分配图中有环路，且所涉及的资源类有多个资源，则不一定会发生死锁。

死锁解除

死锁解除的常用方法就是终止进程和资源抢占，回滚。所谓进程终止就是简单地终止一个或多个进程以打破循环等待，包括两种方式：终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止；所谓资源抢占就是从一个或者多个死锁进程那里抢占一个或多个资源。

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任何措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

调度算法

进程调度、页面置换、磁盘调度

进程调度方法

  1. 先来先服务：非抢占式的调度算法，按照请求的顺序进行调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。另外，对I/O密集型进程也不利，因为这种进程每次进行I/O操作之后又得重新排队。
  2. 最短作业优先：非抢占式的调度算法，按估计运行时间最短的顺序进行调度。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
  3. 高响应比优先：响应比优先 （*Highest Response Ratio Next, HRRN*）调度算法主要是权衡了短作业和长作业。每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行；
  4. 时间片轮转：将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
  5. 优先级调度：希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（*Highest Priority First，HPF*）调度算法。
  6. 多级反馈队列调度算法：多级反馈队列（*Multilevel Feedback Queue*）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。
  7. 多级队列调度：将进程分为多个不同类型的队列（如系统进程、交互式进程、批处理进程等）。每个队列有不同的调度策略（如 RR、FCFS 等），系统按优先级依次处理各个队列中的进程。

时间片轮转算法的效率和时间片的大小有很大关系：因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。 而如果时间片过长，那么实时性就不能得到保证。

内存页面置换算法

  1. 最佳页面置换算法（OPT）
  2. 先进先出置换算法（FIFO）
  3. 最近最久未使用的置换算法（LRU）
  4. 时钟页面置换算法（Lock）
  5. 最不常用置换算法（LFU）

分页和分段

分页

把内存空间划分为大小相等且固定的块，作为主存的基本单位。因为程序数据存储在不同的页面中，而页面又离散的分布在内存中，因此需要一个页表来记录映射关系，以实现从页号到物理块号的映射。

访问分页系统中内存数据需要两次的内存访问 (一次是从内存中访问页表，从中找到指定的物理块号，加上页内偏移得到实际物理地址；第二次就是根据第一次得到的物理地址访问内存取出数据)。

分段

分页是为了提高内存利用率，而分段是为了满足程序员在编写代码的时候的一些逻辑需求(比如数据共享，数据保护，动态链接等)。

分段内存管理当中，地址是二维的，一维是段号，二维是段内地址；其中每个段的长度是不一样的，而且每个段内部都是从0开始编址的。由于分段管理中，每个段内部是连续内存分配，但是段和段之间是离散分配的，因此也存在一个逻辑地址到物理地址的映射关系，相应的就是段表机制。

分页和分段的区别

  • 分页对程序员是透明的，但是分段需要程序员显式划分每个段。
  • 分页的地址空间是一维地址空间，分段是二维的。
  • 页的大小不可变，段的大小可以动态改变。
  • 分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

交换空间

操作系统把物理内存(physical RAM)分成一块一块的小内存，每一块内存被称为页(page)。当内存资源不足时，Linux把某些页的内容转移至硬盘上的一块空间上，以释放内存空间。硬盘上的那块空间叫做交换空间(swap space),而这一过程被称为交换(swapping)。物理内存和交换空间的总容量就是虚拟内存的可用容量。

用途：

  • 物理内存不足时一些不常用的页可以被交换出去，腾给系统。
  • 程序启动时很多内存页被用来初始化，之后便不再需要，可以交换出去。

虚拟内存

让屋里内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。虚拟内存使用部分加载的技术，让一个进程或者资源的某些页面加载进内存，从而能够加载更多的进程，甚至能加载比内存大的进程，这样看起来好像内存变大了，这部分内存其实包含了磁盘或者硬盘，并且就叫做虚拟内存。

实现方式

虚拟内存中，允许将一个作业分多次调入内存。釆用连续分配方式时，会使相当一部分内存空间都处于暂时或永久的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实需要建立在离散分配的内存管理方式的基础上。虚拟内存的实现有以下三种方式：

  • 请求分页存储管理
  • 请求分段存储管理
  • 请求段页式存储管理

页面替换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

  1. 最优算法
  2. 最近未使用算法
  3. 先进先出
  4. 第二次机会
  5. 时钟算法
  6. 最近最少
  7. 最不经常使用
  8. 老化算法
  9. 工作集算法
  10. 工作集时钟算法
  • 最优算法在当前页面中置换最后要访问的页面。不幸的是，没有办法来判定哪个页面是最后一个要访问的，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准。
  • NRU 算法根据 R 位和 M 位的状态将页面分为四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现，但是性能不是很好。存在更好的算法。
  • FIFO 会跟踪页面加载进入内存中的顺序，并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面，因此这个算法也不是一个很好的选择。
  • 第二次机会算法是对 FIFO 的一个修改，它会在删除页面之前检查这个页面是否仍在使用。如果页面正在使用，就会进行保留。这个改进大大提高了性能。
  • 时钟 算法是第二次机会算法的另外一种实现形式，时钟算法和第二次算法的性能差不多，但是会花费更少的时间来执行算法。
  • LRU 算法是一个非常优秀的算法，但是没有特殊的硬件(TLB)很难实现。如果没有硬件，就不能使用 LRU 算法。
  • NFU 算法是一种近似于 LRU 的算法，它的性能不是非常好。
  • 老化 算法是一种更接近 LRU 算法的实现，并且可以更好的实现，因此是一个很好的选择
  • 最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销，但是它的实现比较复杂。WSClock 是另外一种变体，它不仅能够提供良好的性能，而且可以高效地实现。

什么是缓冲区溢出？有什么危害？

缓冲区溢出是指当计算机向缓冲区填充数据时超出了缓冲区本身的容量，溢出的数据覆盖在合法数据上。

危害有以下两点：

  • 程序崩溃，导致拒绝额服务
  • 跳转并且执行一段恶意代码

造成缓冲区溢出的主要原因是程序中没有仔细检查用户输入。