操作系统
- 什么是进程和线程？区别?协程呢？
进程与线程
进程就是运行中的程序，每个进程都有自己的独立地址空间，是系统资源分配的基本单位。线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位，同一个进程内多个线程之间可以共享进程拥有的资源，但每个线程都有自己的计数器，寄存器和栈，这样可以确保线程是相对独立的。
进程和线程区别
①进程是资源分配最小单位，线程是程序执行的最小单位；
②进程有自己独立的地址空间，线程不拥有系统资源，只拥有计数器，寄存器等少量资源，但是可以访问隶属于进程的资源。
③创建和切换一个线程的开销比进程开销小。因为创建或撤销进程时，系统都要为之分配或回收系统资源，如内存空间，I/O设备等，OS所付出的开销显著大于在创建或撤销线程时的开销，线程只需维护少量寄存器和程序计数器，因此开销很小。进程切换时，需要切换虚拟地址空间，切换内核栈和硬件上下文，CPU高速缓存失效、页表切换，开销很大；线程切换时只需保存和设置少量寄存器内容，因此开销很小。
④线程之间通信更方便，同一个进程下，线程共享全局变量，静态变量等数据，进程之间的通信需要以通信的方式（IPC）进行；（但多线程程序处理好同步与互斥是个难点）
协程
协程是一种用户态的轻量级线程，协程的调度完全由用户控制。协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。
[一个进程可以创建多少线程，和什么有关？]
理论上，32位系统一个进程可用虚拟空间是2G，默认情况下，线程的栈的大小是1MB，所以理论上最多只能创建2048个线程。如果要创建多于2048的话，必须修改编译器的设置。
因此，一个进程可以创建的线程数由可用虚拟空间和线程的栈的大小共同决定，只要虚拟空间足够，那么新线程的建立就会成功。如果需要创建超过2K以上的线程，减小你线程栈的大小就可以实现了，虽然在一般情况下，你不需要那么多的线程。过多的线程将会导致大量的时间浪费在线程切换上，给程序运行效率带来负面影响。
进程与线程的切换流程？
进程切换分两步：
1、切换页表以使用新的地址空间，一旦去切换上下文，处理器中所有已经缓存的内存地址一瞬间都作废了。
2、切换内核栈和硬件上下文。
对于linux来说，线程和进程的最大区别就在于地址空间，对于线程切换，第1步是不需要做的，第2步是进程和线程切换都要做的。
因为每个进程都有自己的虚拟地址空间，而线程是共享所在进程的虚拟地址空间的，因此同一个进程中的线程进行线程切换时不涉及虚拟地址空间的转换。
- 进程间通信方式IPC
管道：管道分为匿名管道和命名管道。
匿名管道是特殊文件只存在于内存，shell 命令中的「|」竖线就是匿名管道。匿名管道是只能用于存在父子关系的进程间通信。
命名管道允许没有亲缘关系进程间的通信，因为使用命名管道的前提，需要在文件系统创建一个类型为 p 的设备文件，那么毫无关系的进程就可以通过这个设备文件进行通信，通信数据都遵循先进先出原则。
管道通信的方式是单向的，，如果要双向通信，需要创建两个管道。
消息队列克服了管道通信的数据是无格式的字节流的问题，消息队列实际上是保存在内核的「消息链表」，消息队列的消息体是可以用户自定义的数据类型。消息队列通信的速度不是最及时的，每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。另一个问题是消息队列不适合比较大数据的传输，因为在内核中每个消息体都有一个最大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限
共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问，不需要陷入内核态，大大提高了通信的速度。但是共享内存通信，带来新的问题，多进程竞争同个共享资源会造成数据的错乱。
信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
信号：用于通知接收进程某个事件已经发生，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令）。
如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，
进程间同步的方式有哪些？
[1. 临界区]
对临界资源进行访问的那段代码称为临界区。
为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。
// entry section
// critical section;
// exit section
[2. 同步与互斥]
- 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
- 互斥：多个进程在同一时刻只有一个进程能进入临界区。
[3. 信号量]
信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。
- down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
- up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。
down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。
如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。
4、管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。
管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。
进程有哪些状态？
- 用户态和核心态
详见：https://cloud.tencent.com/developer/article/1720767?from=information.detail.linux%E5%86%85%E6%A0%B8%E6%80%81%E5%92%8C%E7%94%A8%E6%88%B7%E6%80%81%E7%9A%84%E5%8C%BA%E5%88%AB
根据进程访问资源的特点，把进程在系统上的运行分为两个级别：用户态(user mode) : 用户态运行的进程或可以直接读取用户程序的数据。内核态(kernel mode):可以简单的理解系统态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。运行在用户态的程序不能直接访问操作系统内核数据结构和程序。内核态和用户态之间的转换方式主要包括：系统调用，异常和中断。 -
操作系统分配的进程空间是怎样的？线程能共享哪些？
image.png
- 死锁条件，解决方式。
条件
互斥条件：该资源任意一个时刻只由一个线程占用。
请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件:线程已获得的资源在末使用完之前不能被其他线程强行剥夺，只有自己使用完毕后才释放资源。
循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
解决
破坏互斥条件 ：这个条件没有办法破坏，因为用锁本来就是想让他们互斥的（临界资源需要互斥访问）。
破坏请求与保持条件 ：一次性申请所有的资源。
破坏不剥夺条件 ：占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源。
破坏循环等待条件 ：靠按序申请资源来预防。按某一顺序申请资源，释放资源则反序释放。破坏循环等待条件。 -
页面置换算法有哪些，FIFO为什么不好？如何改进?LRU思想，手写LRU。
先来先服务 first-come first-serverd（FCFS）：非抢占式的调度算法，按照请求的顺序进行调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。
短作业优先(SJF)的调度算法 : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
高响应比优先调度算法(Highest Response Ratio Next, HRRN：权衡了短作业和长作业。每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行。
响应比优先级公式.png
时间片轮转调度(Round Robin, RR)算法 : 每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；
最高优先级调度算法：前面的「时间片轮转算法」做了个假设，即让所有的进程同等重要，也不偏袒谁，大家的运行时间都一样。但是，对于多用户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。进程的优先级可以分为，静态优先级或动态优先级。
多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展：「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；工作流程如下：
多级反馈队列.png
- 操作系统内存管理方式，分页分段以及段页式的优缺点？
操作系统的内存管理主要负责内存的分配与回收（malloc 函数：申请内存，free 函数：释放内存），另外地址转换也就是将逻辑地址转换成相应的物理地址等功能也是操作系统内存管理做的事情。
块式管理 ： 远古时代的计算机操系统的内存管理方式。将内存分为几个固定大小的块，每个块中只包含一个进程。如果程序运行需要内存的话，操作系统就分配给它一块，如果程序运行只需要很小的空间的话，分配的这块内存很大一部分几乎被浪费了。这些在每个块中未被利用的空间，我们称之为碎片。
分段：程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段的形式把这些段分离出来。分段机制下的虚拟地址由两部分组成，段选择子和段内偏移量。虚拟地址是通过段表与物理地址进行映射的，分段机制会把程序的虚拟地址分成 4 个段，每个段在段表中有一个项，在这一项找到段的基地址，再加上偏移量，于是就能找到物理内存中的地址。分段的好处就是能产生连续的内存空间，但是会出现内存碎片和内存交换的空间太大，内存交换的效率低的问题。
分页：是把整个虚拟和物理内存空间切成一段段连续并且尺寸固定的内存空间，叫页（Page），在 Linux 下，每一页的大小为 4KB。虚拟地址与物理地址之间通过页表来映射，在分页机制下，虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址。当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。
简单的分页有空间上的缺陷，要解决这个的问题，就需要采用的是一种叫作多级页表（Multi-Level Page Table）的解决方案。如果使用了二级分页，一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，也就是带来了时间上的开销。 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB（Translation Lookaside Buffer） ，通常称为页表缓存、转址旁路缓存、快表等。
段页式内存管理：段页式管理机制结合了段式管理和页式管理的优点。简单来说段页式管理机制就是把主存先分成若干段，每个段又分成若干页，也就是说 段页式管理机制 中段与段之间以及段的内部的都是离散的。先将程序划分为多个有逻辑意义的段，也就是分段机制；接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；这样，地址结构就由段号、段内页号和页内位移三部分组成。
８．为什么需要虚拟地址空间？
没有虚拟地址空间的时候，程序都是直接访问和操作的都是物理内存，如果直接把物理地址暴露出来的话会带来严重问题，比如可能对操作系统造成伤害以及给同时运行多个程序造成困难。
通过虚拟地址访问内存有以下优势：
程序可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的大内存缓冲区。
程序可以使用一系列虚拟地址来访问大于可用物理内存的内存缓冲区。当物理内存的供应量变小时，内存管理器会将物理内存页（通常大小为 4 KB）保存到磁盘文件。数据或代码页会根据需要在物理内存与磁盘之间移动。
不同进程使用的虚拟地址彼此隔离。一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。
9．分页机制和分段机制有哪些共同点和区别呢？
共同点 ：
分页机制和分段机制都是为了提高内存利用率，减少内存碎片。
页和段都是离散存储的，所以两者都是离散分配内存的方式。但是，每个页和段中的内存是连续的。
区别 ：
页的大小是固定的，由操作系统决定；而段的大小不固定，取决于当前运行的程序。
分页仅仅是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，在程序中可以体现为代码段，数据段，能够更好满足用户的需要。
10．什么是虚拟内存？
虚拟内存是计算机系统内存管理的一种技术，虚拟内存使得应用程序认为它独自拥有一个连续完整的地址空间，而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使用虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如 RAM）的使用也更有效率。
11．局部性原理？
局部性原理表现在以下两个方面：
时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。
时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构，利用局部性原理实现髙速缓存。
