• 用户模式和内核模式，都知道哪些？
• 生产者消费者模型
• 进程和线程区别？进程间通信有几种方式和各自特点？进程间通信的管道实现原理？
• 进程的地址空间，物理内存和虚拟内存，虚拟内存的机制，能否重叠？
• 进程调度的方法
• 锁都了解多少？进程同步中的锁
• 虚拟内存了解多少
• 进程内存分布
• 自旋锁和读写锁的区别
• 页面置换算法，分页算法，LRU的实现

进程

• 进程结构一般由3部分组成：代码段、数据段、和堆栈段
  代码段是用于存放程序代码的数据。
  数据段则存放程序的全局变量、常量和静态变量。
  堆栈段用于函数调用，它存放函数的参数、函数内部定义的局部变量。

• 进程的创建有两种方式：一种由操作系统创建，一种由父进程创建

• linux 进程创建clone、fork与vfork

进程的创建 - fork() 函数

1、fork 函数不需要参数，返回值是一个进程标识符(PID)。对于返回值有以下3种情况

• 对于父进程，fork() 函数返回新创建的子进程的 ID。
• 对于子进程，fork() 函数返回0
• 如果创建出错，则 fork() 函数返回 -1

2、 fork() 函数会创建一个新的进程，并从内核中为此进程分配一个新的可用的进程标识符(PID)，之后，为这个新进程分配进程空间，并将父进程的进程空间中的内容复制到子进程的进程空间中，包括父进程的数据段和堆栈段，并且和父进程共享代码段。这时候，系统中又多了一个进程，这个进程和父进程一模一样，两个进程都要接受系统的调度。由于在复制时复制了父进程的堆栈段，所以两个进程都停留在了 fork() 函数中，等待返回。因此，fork() 函数会返回两个，一次是在父进程中返回，另一次是在子进程中返回，这两次的返回值是不一样的。

• 孤儿进程：是指一个父进程退出后，而它的一个或多个子进程还在运行，那么那些子进程将称为孤儿进程。孤儿进程将被 init 进程（进程号为1）所收养，并由 init 进程对它们完成状态收集工作
• 僵尸进程：是指一个进程使用 fork 创建子进程，如果子进程退出，而父进程并没有调用 wait 或 waitpid 获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中，这种进程称为僵尸进程。当一个进程完成它的工作终止后，它的父进程需要调用 wait() 或者 waitpid() 系统调用取得子进程的终止状态
  一个子进程的进程描述符在子进程退出时不会释放，只有当父进程通过 wait() 或 waitpid() 获取了子进程信息后才会释放。如果子进程退出，而父进程并没有调用 wait() 或 waitpid()，那么子进程的进程描述符仍然保存在系统中，这种进程称之为僵尸进程。
  僵尸进程通过 ps 命令显示出来的状态为 Z（zombie）。
  系统所能使用的进程号是有限的，如果产生大量僵尸进程，将因为没有可用的进程号而导致系统不能产生新的进程。
  要消灭系统中大量的僵尸进程，只需要将其父进程杀死，此时僵尸进程就会变成孤儿进程，从而被 init 所收养，这样 init 就会释放所有的僵尸进程所占有的资源，从而结束僵尸进程。

可以这样理解孤儿进程和僵尸进程的区别：孤儿进程是父进程已退出，而子进程未退出；僵尸进程是父进程未退出，而子进程已退出

• 守护进程：是运行在后台的一种特殊进程, 不受终端控制，Linux系统的大多数服务器就是通过守护进程实现的。一个守护进程的父进程是init进程。

进程间的通信

前四种主要用于同一台机器上的进程间的通信
而套接字则主要用于不同机器之间的网络通信。

• 管道：
  管道本质上也是一种文件，但它又和一般的文件有所不同，可以克服使用文件进行通信的两个问题，这个文件只存在内存中
  1、管道是一种半双工的通信方式，数据只能单向流动；如果要进行双向通信，则需要建立两个管道
  ２、只能用于父子进程或者兄弟进程之间的通信，也就是说管道只能用于具有亲缘关系的进程间通信
  ３、此外，如管道没有名字(无名管道)，管道的缓冲区大小是受限制的；管道所传输的是无格式的字节流等。这就需要管道输入方和输出方事先约定好数据格式
  ４、有名管道(FIFO)：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信

• 消息队列：
  １、它和管道很相似，是一个在系统内核中保存消息的队列，在系统内核中以消息链表的形式出现。
  ２、消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点
  ３、读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

• 共享内存：
  １、顾名思义，共享内存就是允许两个不相关的进程访问同一个逻辑内存。是进程间通信最快的方式
  ２、优点：进程间通信非常方便；数据共享使进程间的数据不用传送，而是直接访问内存，加快了程序效率
  ３、缺点：共享内存没有提供同步机制。这使得使用共享内存进行进程间通信时，往往需要借助其他手段(如信号量)来进行进程间同步工作

• 信号量：
  信号量用于实现进程间的互斥与同步，也可以用在线程上，主要有 POSIX 信号量和SYSTEM V信号量，POSIX 信号量一般用在线程上，SYSTEM V 信号量一般用在进程上，POSIX 信号量的函数一般都在下划线。

• 套接字：用于不同机器之间的网络通信。

进程调度算法

• 先来先服务 first-come first-serverd（FCFS）
  按照请求的顺序进行调度。
  有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

• 短作业优先 shortest job first（SJF）
  按估计运行时间最短的顺序进行调度。
  长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

• 最短剩余时间优先
  按估计剩余时间最短的顺序进行调度。

• 时间片轮转算法
  将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
  时间片轮转算法的效率和时间片的大小有很大关系：因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。而如果时间片过长，那么实时性就不能得到保证。

• 优先级调度算法
  为每个进程分配一个优先级，按优先级进行调度。
  为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

• 多级反馈队列
  一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。
  多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。
  每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
  可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

线程进程的区别体现在几个方面

• 1、拥有资源
  进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
• 2、调度
  线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
• 3、系统开销
  由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
• 4、通信方面
  线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 管道，消息队列，共享内存，信号量、套接字等通信机制。
• 5、创建
  创建进程 fork()
  创建线程 pthread_create()

进程与线程的选择取决以下几点

• 1、需要频繁创建销毁的优先使用线程；因为对进程来说创建和销毁一个进程代价是很大的。
• 2、线程的切换速度快，所以在需要大量计算，切换频繁时用线程，还有耗时的操作使用线程可提高应用程序的响应
• 3、因为对CPU系统的效率使用上线程更占优，所以可能要发展到多机分布的用进程，多核分布用线程；
• 4、并行操作时使用线程，如C/S架构的服务器端并发线程响应用户的请求；
• 5、需要更稳定安全时，适合选择进程；需要速度时，选择线程更好。

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

• 最佳置换算法 OPT, Optimal replacement algorithm
  所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。
  是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。
• 最近最久未使用置换算法 LRU, Least Recently Used
  虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。
  为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。
  因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
• 最近未使用置换算法 NRU, Not Recently Used
  每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：
  R=0，M=0
  R=0，M=1
  R=1，M=0
  R=1，M=1
  当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。
  NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
• 先进先出置换算法 FIFO, First In First Out
  选择换出的页面是最先进入的页面。
  该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。

磁盘调度算法

• 先来先服务 FCFS, First Come First Served
  按照磁盘请求的顺序进行调度。
  优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。
• 最短寻道时间优先 SSTF, Shortest Seek Time First
  优先调度与当前磁头所在磁道距离最近的磁道。
  虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。
• 电梯算法 SCAN
  电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。
  电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。
  因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。