操作系统
操作系统基础知识
进程、线程、协程
进程是系统资源分配和调度的最小单位、
线程是操作系统分配和调度的最小单位
线程分成更小的协程，多个协程共享一个线程。
线程切换是一个操作系统层面的行为，要关中断、保存断点、终端服务寻址、开中断执行服务
协程间切换是runtime的 行为
操作系统运行机制
- 时钟管理
- 中断机制
- 外中断：中断信号来源于外部设备（被迫的）
- 内中断：中断信号来源于当前指令（自愿的）：
- 陷入指令（应用程序引发的，cpu产生），比如程序执行到某处需要进行读文件操作，cpu从用户态切换到内核态
- 内存缺页中断
 |
 |
|---|
- 原语（原语的底层实现就是靠开中断和关中断实现的）
- 若干条指令组成
- 完成某个特定功能
- 执行过程不会被中断（具有原子性）
- 系统数据结构
- 进程管理：作业控制快、进程控制块
- 存储器管理：存储器分配与回收
- 设备管理：缓冲区、设备控制快
- 系统调用（应用程序去访问操作系统内核的时候）
- 一套接口的集合
- 应用程序去访问操作系统内核服务的方式
操作系统
PCB:为了描述控制进程的运行，系统中存放进程的管理和控制信息的数据结构称为进程控制块（PCB Process Control Block），它是进程实体的一部分，是操作系统中最重要的记录性数据结构。它是进程管理和控制的最重要的数据结构，每一个进程均有一个PCB，在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。
寄存器里面放的是有些程序运行计算了一半被抢占了，记录执行的位置，下次执行可以接着中间数据往下执行
进程的状态
- 其实是七状态，还有阻塞挂起和就绪挂起
进程间通信
共享存储：共享空间对于多个进程访问是互斥的
管道通信：没写满的时候是不允许读的，没读完也是不允许写的。
消息队列：消息头里包含了传递信息，不会传错给别的进程
信号
套接字 socket
线程
线程的实现方式（用户级线程、内核级线程、组合方式）
多线程模型：多对一、一对多
n个用户级线程映射到内核级线程上
处理机调度（线程调度）
进程同步
- **互斥量(Mutex)**：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
- 信号量(Semaphore) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。
- 事件(Event) :Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。
- 临界区：拥有临界区的线程可以访问被保护资源，其他访问会被挂起。
- 双标志前检查法：先检查其他进程是否想要临界区，再上锁
- 双标志后检查法：先上锁在检查其他进程是否想要临界区
- Peterson算法：双方都争着使用临界区的话，可以尝试让一方主动让对方先使用临界区
进程互斥
临界区冲突
- 空闲让进：一次进一个，进不来的挂起
- 忙则等待：
- 有限等待：有限时间内退出
- 让权等待：进程不能进入自己的临界区，则应该让出CPU，避免出现忙等现象
死锁
- 互斥条件：对必须互斥资源的争抢才会导致死锁
- 不剥夺条件：进程获得的资源在未使用完之前不能由其他进程强行夺走，只能主动释放
- 请求和保持条件：进程已经保持至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求被阻塞，但又对自己的资源保持不放
- 循环等待条件：存在资源的循环等待链
预防死锁
避免死锁（银行家算法）
内存
内存管理
覆盖技术
下图A调用B、C是依次调用的，因此B、C可以共同使用程序X的覆盖区0（图中绿色），从逻辑上看，物理内存是被”拓展“了
交换技术
换入、换出
内存分配
管理方式（单一连续分配、固定分区分配方式)
分页
不同的页面是离散地存放在内存中
页表
每个进程都有自己的页表
问题：
相当于把以前的页表查分成多个页表，并为多个页表加一个目录，叫做”页目录表“
虚拟内存
传统存储
例如，GTA游戏一共60G，电脑是4G的，如果要玩的话需要全部加载到内存中，显然是不够的，但是我在A场景时只用放入A场景的资源就可以了，而这种传统方式会需要整个游戏全部加驻留在内存中。
虚拟内存基于局部性原理
实现虚拟内存的技术
请求分页存储管理
内存有空闲的情况
内存没空闲的情况
请求分段存储管理
请求段页式存储管理
页面替换算法
最佳置换算法（OPT）
先进先出置换算法（FIFO）
最近最久未使用置换算法（LRU）
时钟置换算法（CLOCK）
- 内存块排布类似于循环链表
- 到6页面的时候，由于5个内存块都满了，就需要先箭头转一圈全部置为0，然后替换最开始的位置，后面用到的继续置为1，全为1的时候再转一圈变为0，然后又从队首开始替换。箭头扫描的过程有点像时钟转，故命名为时钟置换算法。
改造型的时钟置换算法
因为之前说到分页存储的时候，再替换过程中如果一个页面被修改过，则需要写入外存中去。这个时候给他加一个标记，被修改过的时候修改位标记为1。
磁盘结构
活动头磁盘、固定头磁盘
写磁盘需要的时间流程（寻道时间、延迟时间、传输时间）
磁盘调度算法
先来先服务
最短寻找时间优先
扫描算法
LOOK调度算法（扫描算法改进）
循环扫描算法（扫描算法改进）主要是各个磁道响应时间比较平均
C-LOOK调度算法
总结
减少磁盘延迟时间的方法
交替编号：在读取连续扇区时，每读完一个扇区需要时间处理读取的内容，由于磁头还没有准备好，可能在处理过程中就错过了连续扇区的内容，这个时候需要再转一圈转到未读的地方，所以一般间隔编号依次交替解决问题
错位命名
IO
select poll epoll
什么是操作系统？请简要概述一下
操作系统是管理计算机硬件和软件资源的计算机程序，提供一个计算机用户与计算机硬件系统之间的接口。
向上对用户程序提供接口，向下接管硬件资源。
操作系统本质上也是一个软件，作为最接近硬件的系统软件，负责处理器管理、存储器管理、设备管理、文件管理和提供用户接口。
操作系统有哪些分类？
操作系统常规可分为批处理操作系统、分时操作系统、实时操作系统。
若一个操作系统兼顾批操作和分时的功能，则称该系统为通用操作系统。
常见的通用操作系统有：Windows、Linux、MacOS等。
什么是内核态和用户态？
为了避免操作系统和关键数据被用户程序破坏，将处理器的执行状态分为内核态和用户态。
内核态是操作系统管理程序执行时所处的状态，能够执行包含特权指令在内的一切指令，能够访问系统内所有的存储空间。
用户态是用户程序执行时处理器所处的状态，不能执行特权指令，只能访问用户地址空间。
用户程序运行在用户态,操作系统内核运行在内核态。
如何实现内核态和用户态的切换？
处理器从用户态切换到内核态的方法有三种：系统调用、异常和外部中断。
系统调用是操作系统的最小功能单位，是操作系统提供的用户接口，系统调用本身是一种软中断。
异常，也叫做内中断，是由错误引起的，如文件损坏、缺页故障等。
外部中断，是通过两根信号线来通知处理器外设的状态变化，是硬中断。
并发和并行的区别
并发（concurrency）：指宏观上看起来两个程序在同时运行，比如说在单核cpu上的多任务。但是从微观上看两个程序的指令是交织着运行的，指令之间交错执行，在单个周期内只运行了一个指令。这种并发并不能提高计算机的性能，只能提高效率（如降低某个进程的相应时间）。
并行（parallelism）：指严格物理意义上的同时运行，比如多核cpu，两个程序分别运行在两个核上，两者之间互不影响，单个周期内每个程序都运行了自己的指令，也就是运行了两条指令。这样说来并行的确提高了计算机的效率。所以现在的cpu都是往多核方面发展。
什么是进程？
进程是操作系统中最重要的抽象概念之一，是资源分配的基本单位，是独立运行的基本单位。
进程的经典定义就是一个执行中程序的实例。系统中的每个程序都运行在某个进程的上下文（context）中。
上下文是由程序正确运行所需的状态组成的。这个状态包括存放在内存中的程序的代码和数据，它的栈、通用目的寄存器的内容、程序计数器、环境变量以及打开文件描述符的集合。
进程一般由以下的部分组成：进程控制块PCB，是进程存在的唯一标志，包含进程标识符PID，进程当前状态，程序和数据地址，进程优先级、CPU现场保护区（用于进程切换），占有的资源清单等。
程序段
数据段
进程的基本操作
以Unix系统举例：
- 进程的创建：fork()。新创建的子进程几乎但不完全与父进程相同。子进程得到与父进程用户级虚拟地址空间相同的(但是独立的)一份副本，包括代码和数据段、堆、共享库以及用户栈。子进程还获得与父进程任何打开文件描述符相同的副本，这就意味着当父进程调用 fork 时，子进程可以读写父进程中打开的任何文件。父进程和新创建的子进程之间最大的区别在于它们有不同的 PID。fork函数是有趣的（也常常令人迷惑）， 因为它只被调用一次，却会返回两次：一次是在调用进程（父进程）中，一次是在新创建的子进程中。在父进程中，fork 返回子进程的 PID。在子进程中，fork 返回 0。因为子进程的 PID 总是为非零，返回值就提供一个明 确的方法来分辨程序是在父进程还是在子进程中执行。
- 复制代码回收子进程：当一个进程由于某种原因终止时，内核并不是立即把它从系统中清除。相反，进程被保持在一种已终止的状态中，直到被它的父进程回收（reaped）。当父进程回收已终止的子进程时，内核将子进程的退出状态传递给父进程，然后抛弃已终止的进程。一个进程可以通过调用 waitpid 函数来等待它的子进程终止或者停止。
1 | pid_t fork(void); |
- 复制代码加载并运行程序：execve 函数在当前进程的上下文中加载并运行一个新程序。
复制代码进程终止：
1 | pid_t waitpid(pid_t pid, int *statusp, int options); |
1 | int execve(const char *filename, const char *argv[], const char *envp[]); |
复制代码
每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程A把数据从用户空间拷到内核缓冲区,进程B再从内核缓冲区把数据读走,内核提供的这种机制称为进程间通信。 不同进程间的通信本质：进程之间可以看到一份公共资源；而提供这份资源的形式或者提供者不同，造成了通信方式不同。 进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。 管道是一种最基本的IPC机制，作用于有血缘关系的进程之间，完成数据传递。调用pipe系统函数即可创建一个管道。有如下特质： 管道的原理: 管道实为内核使用环形队列机制，借助内核缓冲区实现。 管道的局限性： 它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。 特点： 一个信号就是一条小消息，它通知进程系统中发生了一个某种类型的事件。Linux 系统上支持的30 种不同类型的信号。每种信号类型都对应于某种系统事件。低层的硬件异常是由内核异常处理程序处理的，正常情况下，对用户进程而言是不可见的。信号提供了一种机制，通知用户进程发生了这些异常。复制代码进程在运行时有三种基本状态：就绪态、运行态和阻塞态。 2.就绪（ready）态：进程具备运行条件，等待系统分配处理器以便运行的状态。 当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。 3.阻塞（wait）态：又称等待态或睡眠态，指进程不具备运行条件，正在等待某个时间完成的状态。 各状态之间的转换： 2。僵尸进程：进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait 获waitpid 获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中的这些进程是僵尸进程。 线程产生的原因：进程可以使多个程序能并发执行，以提高资源的利用率和系统的吞吐量；但是其具有一些缺点： 引入线程就是为了解决以上进程的不足，线程具有以下的优点： 进程API以Unix系统为例，线程相关的API属于Posix线程(Pthreads)标准接口。
1 | void exit(int status); |
进程如何通过管道进行通信
- 其本质是一个伪文件(实为内核缓冲区)
- 由两个文件描述符引用，一个表示读端，一个表示写端。
- 规定数据从管道的写端流入管道，从读端流出。
- 数据自己读不能自己写。
- 数据一旦被读走，便不在管道中存在，不可反复读取。
- 由于管道采用半双工通信方式。因此，数据只能在一个方向上流动。
- 只能在有公共祖先的进程间使用管道。
进程如何通过共享内存通信？
- 共享内存是最快的一种IPC，因为进程是直接对内存进行操作来实现通信，避免了数据在用户空间和内核空间来回拷贝。
- 因为多个进程可以同时操作，所以需要进行同步处理。
- 信号量和共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。
什么是信号
- 发送信号：内核通过更新目的进程上下文中的某个状态，发送（递送）一个信号给目的进程。发送信号可以有如下两种原因：
- 内核检测到一个系统事件，比如除零错误或者子进程终止。
- —个进程调用了kill 函数， 显式地要求内核发送一个信号给目的进程。一个进程可以发送信号给它自己。
- 接收信号：当目的进程被内核强迫以某种方式对信号的发送做出反应时，它就接收了信号。进程可以忽略这个信号，终止或者通过执行一个称为信号处理程序(signal handler)的用户层函数捕获这个信号。
如何编写正确且安全的信号处理函数
处理程序要尽可能简单。避免麻烦的最好方法是保持处理程序尽可能小和简单。例如，处理程序可能只是简单地设置全局标志并立即返回；所有与接收信号相关的处理都由主程序执行，它周期性地检查(并重置)这个标志。
在处理程序中只调用异步信号安全的函数。所谓异步信号安全的函数(或简称安全的函数)能够被信号处理程序安全地调用，原因有二：要么它是可重入的(例如只访问局部变量），要么它不能被信号处理程序中断。
保存和恢复errno。许多Linux 异步信号安全的函数都会在出错返回时设置errno在处理程序中调用这样的函数可能会干扰主程序中其他依赖于分。解决方法是在进人处理程序时把errno 保存在一个局部变量中，在处理程序返回前恢复它。注意，只有在处理程序要返回时才有此必要。如果处理程序调用_exit终止该进程，那么就不需要这样做了。
阻塞所有的信号，保护对共享全局数据结构的访问。如果处理程序和主程序或其他处理程序共享一个全局数据结构，那么在访问(读或者写)该数据结构时，你的处理程序和主程序应该暂时阻塞所有的信号。这条规则的原因是从主程序访问一个数据结构d 通常需要一系列的指令，如果指令序列被访问d 的处理程序中断，那么处理程序可能会发现d 的状态不一致，得到不可预知的结果。在访问d 时暂时阻塞信号保证了处理程序不会中断该指令序列。
用volatile 声明全局变量。考虑一个处理程序和一个main 函数，它们共享一个全局变量g 。处理程序更新g，main 周期性地读g， 对于一个优化编译器而言，main 中g的值看上去从来没有变化过，因此使用缓存在寄存器中g 的副本来满足对g 的每次引用是很安全的。如果这样，main 函数可能永远都无法看到处理程序更新过的值。可以用volatile 类型限定符来定义一个变量，告诉编译器不要缓存这个变量。例如：volatile 限定符强迫编译器毎次在代码中引用g时，都要从内存中读取g的值。一般来说，和其他所有共享数据结构一样，应该暂时阻塞信号，保护每次对全局变量的访问。
1
void exit(int status);
用sig_atomic_t声明标志。在常见的处理程序设计中，处理程序会写全局标志来记录收到了信号。主程序周期性地读这个标志，响应信号，再清除该标志。对于通过这种方式来共享的标志，C 提供一种整型数据类型sig_atomic_t对它的读和写保证会是原子的（不可中断的）。
信号的一个与直觉不符的方面是未处理的信号是不排队的。因为 pending 位向量中每种类型的信号只对应有一位，所以每种类型最多只能有一个未处理的信号。关键思想是如果存在一个未处理的信号就表明至少有一个信号到达了。
进程调度的时机
- 当前运行的进程运行结束。
- 当前运行的进程由于某种原因阻塞。
- 执行完系统调用等系统程序后返回用户进程。
- 在使用抢占调度的系统中，具有更高优先级的进程就绪时。
- 分时系统中，分给当前进程的时间片用完。
不能进行进程调度的情况
- 在中断处理程序执行时。
- 在操作系统的内核程序临界区内。
- 其它需要完全屏蔽中断的原子操作过程中。
进程调度策略的基本设计指标
- CPU利用率
- 系统吞吐率，即单位时间内CPU完成的作业的数量。
- 响应时间。
- 周转时间。是指作业从提交到完成的时间间隔。从每个作业的角度看，完成每个作业的时间也是很关键
- 平均周转时间
- 带权周转时间
- 平均带权周转时间
进程的状态与状态转换
- 运行（running）态：进程占有处理器正在运行的状态。进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；在多处理机系统中，则有多个进程处于执行状态。
- 就绪→执行 处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。
- 执行→就绪 处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。
- 执行→阻塞 正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。
- 阻塞→就绪 处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。
什么是孤儿进程？僵尸进程?
孤儿进程：父进程退出，子进程还在运行的这些子进程都是孤儿进程，孤儿进程将被init进程（1号进程）所收养，并由init进程对他们完成状态收集工作。
什么是线程？
- 是进程划分的任务，是一个进程内可调度的实体，是CPU调度的基本单位，用于保证程序的实时性，实现进程内部的并发。
- 线程是操作系统可识别的最小执行和调度单位。每个线程都独自占用一个虚拟处理器：独自的寄存器组，指令计数器和处理器状态。
- 每个线程完成不同的任务，但是属于同一个进程的不同线程之间共享同一地址空间（也就是同样的动态内存，映射文件，目标代码等等），打开的文件队列和其他内核资源。
为什么需要线程？
- 进程在同一时刻只能做一个任务，很多时候不能充分利用CPU资源。
- 进程在执行的过程中如果发生阻塞，整个进程就会挂起，即使进程中其它任务不依赖于等待的资源，进程仍会被阻塞。
- 从资源上来讲，开辟一个线程所需要的资源要远小于一个进程。
- 从切换效率上来讲，运行于一个进程中的多个线程，它们之间使用相同的地址空间，而且线程间彼此切换所需时间也远远小于进程间切换所需要的时间（这种时间的差异主要由于缓存的大量未命中导致）。
- 从通信机制上来讲，线程间方便的通信机制。对不同进程来说，它们具有独立的地址空间，要进行数据的传递只能通过进程间通信的方式进行。线程则不然，属于同一个进程的不同线程之间共享同一地址空间，所以一个线程的数据可以被其它线程感知，线程间可以直接读写进程数据段（如全局变量）来进行通信（需要一些同步措施）。
简述线程和进程的区别和联系
- 一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
- 进程在执行过程中拥有独立的地址空间，而多个线程共享进程的地址空间。（资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。）
- 进程是资源分配的最小单位，线程是CPU调度的最小单位。
- 通信：由于同一进程中的多个线程具有相同的地址空间，使它们之间的同步和通信的实现，也变得比较容易。进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信（需要一些同步方法，以保证数据的一致性）。
- 进程编程调试简单可靠性高，但是创建销毁开销大；线程正相反，开销小，切换速度快，但是编程调试相对复杂。
- 进程间不会相互影响；一个进程内某个线程挂掉将导致整个进程挂掉。
- 进程适应于多核、多机分布；线程适用于多核。
多线程模型
- 多对一模型。将多个用户级线程映射到一个内核级线程上。该模型下，线程在用户空间进行管理，效率较高。缺点就是一个线程阻塞，整个进程内的所有线程都会阻塞。几乎没有系统继续使用这个模型。
- 一对一模型。将内核线程与用户线程一一对应。优点是一个线程阻塞时，不会影响到其它线程的执行。该模型具有更好的并发性。缺点是内核线程数量一般有上限，会限制用户线程的数量。更多的内核线程数目也给线程切换带来额外的负担。linux和Windows操作系统家族都是使用一对一模型。
- 多对多模型。将多个用户级线程映射到多个内核级线程上。结合了多对一模型和一对一模型的特点。
如何解决死锁问题？
- 资源一次性分配，这样就不会再有请求了（破坏请求条件）。
- 只要有一个资源得不到分配，也不给这个进程分配其他的资源（破坏占有并等待条件）。
- 可抢占资源：即当进程新的资源未得到满足时，释放已占有的资源，从而破坏不可抢占的条件。
- 资源有序分配法：系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反，从而破坏环路等待的条件
请说一下什么是写时复制？
- 如果有多个进程要读取它们自己的那部门资源的副本，那么复制是不必要的。每个进程只要保存一个指向这个资源的指针就可以了。只要没有进程要去修改自己的“副本”，就存在着这样的幻觉：每个进程好像独占那个资源。从而就避免了复制带来的负担。如果一个进程要修改自己的那份资源“副本”，那么就会复制那份资源，并把复制的那份提供给进程。不过其中的复制对进程来说是透明的。这个进程就可以修改复制后的资源了，同时其他的进程仍然共享那份没有修改过的资源。所以这就是名称的由来：在写入时进行复制。
- 算法的好处就在于它们尽量推迟代价高昂的操作，直到必要的时刻才会去执行。
- 在使用虚拟内存的情况下，写时复制（Copy-On-Write）是以页为基础进行的。所以，只要进程不修改它全部的地址空间，那么就不必复制整个地址空间。在fork()调用结束后，父进程和子进程都相信它们有一个自己的地址空间，但实际上它们共享父进程的原始页，接下来这些页又可以被其他的父进程或子进程共享。