进程
一般来说Linux系统中的进程具备下列进程四要素：
（1）有一段程序供其执行，就好像一场戏有个剧本一样。不一定是进程所专有，可以与其他进程共用。
（2）有起码的”私有财产“，这就是进程专用的系统堆栈空间。
（3）有“户口”，这就是在内核中的一个task_struct数据结构，也称为“进程控制块（PCB）”，有了这个数据结构，进程才能成为内核调度的一个基本单位接受内核的调度。
（4）有独立的存储空间，意味着有专有的用户空间；也意味着除前述的系统空间堆栈外还有其专用的用户空间堆栈
如果只具备前面三条，那就称为“线程”。如果完全没有用户空间，就称为“内核线程”；如果共享用户空间就称为“用户线程”。“内核线程”和“用户线程”统称”线程“。
进程模型
在图2-1a中，一台多道（CPU在进程间快速的切换）程序计算机的内存中有四道程序。图2-1b中，这四道程序被抽象为4个各自拥有自己控制流程（即每个程序自己的逻辑程序计数器）的进程，并且每个程序都独立的运行。实际只有一个物理程序计数器，所以在每个程序运行时，它的逻辑程序计数器被装入实际的程序计数器中。当该程序执行结束（或暂定执行）时，物理程序计数器被保存在内存中该进程的逻辑程序计数器中。
进程的创建
4种主要事件会导致进程的创建：
（1）系统初始化。
（2）正在运行的程序执行了创建进程的系统调用。
（3）用户请求创建一个新的进程。
（4）一个批处理作业的初始化。
守护进程（daemon）：停留在后台，等待请求唤醒的进程。
前台进程：同用户交互的进程。
在UNIX系统中，只有一个系统调用可以用来创建新进程：fork。这个系统调用会创建一个与调用进程相同的副本。在调用了fork后，父进程和子进程拥有相同的内存映像、同样的环境字符串和同样的打开文件。
在Windows中，一个Win32函数调用CreateProcess，既处理进程的创建，也负责把正确的程序装入新的进程。
在Unix和Windows中，进程创建之后，父进程和子进程有各自不同的地址空间。在Unix中，虽然子进程的初始地址是父进程的一个副本，但是这里涉及到两个不同的地址空间，不可写的内存区是共享的（写时复制共享）。在Windows中，从一开始父进程的地址空间和子进程的地址空间就是不同的。
进程的终止
进程终止通常由下列条件引起：
- 正常退出（自愿的）。
- 出错退出（自愿的）。
- 严重错误（非自愿）。
- 被其他进程杀死（非自愿）。
进程的层次结构
在Unix中，进程和它的所有子进程以及后裔共同组成一个进程组（树的概念），当用户从键盘发出一个信号时，该信号被送给当前与键盘相关的进程组中的所有成员（当前窗口创建的所有活动进程）。
在Windows中，没有进程层级的概念，所有的进程都是地位相同的。
进程的状态
进程的三种状态：
- 运行态（该时刻进程实际占用CPU）。
- 就绪态（可运行，但因为其他进程正在运行而暂时停止）。
- 阻塞态（除非某种外部事件发生，否则进程不能运行）。
进程的实现
为了实现进程模型，操作系统维护着一张表格（一个结构数组），即进程表。每个进程占用一个进程表项（进程控制块），该表项包含了进程状态的重要信息。
线程
线程的使用
经典的线程模型
POSIX线程
在用户空间和在内核中实现线程
参考链接：线程的3种实现方式—内核级线程, 用户级线程和混合型线程
进程间通信
竞争条件
两个或多个进程读写某些共享数据，最后的结果取决于进程运行的精准时序，称为竞争条件。
临界区
互斥：阻止多个进程同时读写共享的数据。
临界区或临界区域：对共享内存进行访问的程序片段。
避免竞争条件的解决方案，需要满足以下四个条件：
（1）任何两个进程不能同时处于其临界区。
（2）不应该对CPU的速度和数量做任何假设。
（3）临界区外运行的进程不得阻塞其他进程。
（4）不得使进程无限期等待进入临界区。
忙等待的互斥
屏蔽中断
进程在刚刚进入临界区后立即屏蔽所有中断，就要离开之前再打开中断。
弊端：把屏蔽中断的权力交给用户是不明智的；屏蔽中断只对当前CPU有效。、
锁变量
一个进程想进入临界区时，首先测试这把锁（读锁值），若锁值为0，将锁值设置为1并进入临界区；若这把锁的值已经是1了，则进程将等待直到其值变为0。
弊端：一个进程读锁值时为0，恰好在它将其值设置为1之前，另一个进程被调度执行，并将锁变量置为1，当第一个进程再次执行时，它也将该锁值置为1，此时两个进程进入临界区。
严格轮换法
忙等待：连续测试一个变量知道某个值出现为止。
自旋锁：用于忙等待的锁。
弊端：违反了上述条件（3）。
Peterson解法
弊端：需要忙等待。
TSL指令
需要硬件支持，执行TSL的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。
弊端：需要忙等待。
睡眠与唤醒
优先级反转问题：一台计算机有两个进程，H优先级较高，L优先级较低。调度规则规定，只要H处于就绪态它就可以运行。在某一时刻。L处于临界区中，此时H变道就绪态，准备运行。现在H开始忙等待，但由于当H就绪时L不会被调度，也就无法离开临界区，所以H将永远忙等待下去。
生产者-消费者问题（有界缓冲区问题）
由于未对count的访问加以限制，所以可能会出现竞争条件。当缓冲区为空，消费者刚刚读取count的值发现为0.此时调度程序决定暂停消费者并启动生产者。生产者想缓冲区加入一个数据项，count加一。现在count的值变为1了。它推断刚才由于count为0，所以消费者此时一定在睡眠，于是生产者调用wakeup来唤醒消费者。但是，消费者此时在逻辑上并未睡眠，所以wakeup信号丢失。当消费者下次运行时，它将测试先前读到的count值，发现它为0，于是睡眠。当生产者填满整个缓冲区后，也会睡眠。这样两个进程都会永远睡眠下去。
信号量
down操作：检查信号量是否大于0，若该值大于0，则将其减1并继续；若该值为0，则进程将睡眠，而且此时down操作并未结束。
up操作：信号量的值增1和唤醒一个进程。
down操作和up操作均作为一个单一的，不可分割的原子操作完成。
互斥量
当一个线程或进程需要访问临界区时，它调用mutex_lock。如果该互斥量当前是解锁的（临界区可用），则调用成功，调用线程可以自由进入临界区。若该互斥量已经加锁，调用线程被阻塞，直到临界区中的线程完成并调用mutex_unlock。如果多个线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。
只有一个缓冲区的生产者-消费者模型：
管程
管程是一个编程语言概念，一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或者软件包。
管程一个很重要的特性：任一时刻管程中只能有一个活跃的进程，这一特性使管程能有效的完成互斥（引入条件变量以及wait和signal两个操作）。
消息传递
屏障
避免锁：读-复制-更新
调度
简介
1. 进程行为
- 计算密集型：较长时间的CPU集中使用和较小频度的I/O等待
- I/O密集型：较短时间的CPU集中使用和较高频度的I/O等待
2. 何时调度
- 非抢占式调度算法：挑选一个进程，然后让该进程运行直至被阻塞（阻塞在I/O上或者等待另一个进程），或者直到该进程自动释放CPU。
- 抢占式调度算法：挑选一个进程，并且让该进程运行某个固定时段的最大值。如果在该时段结束时，该进程仍在运行，它就被挂起，而调度程序挑选另一个进程运行（如果存在一个就绪进程）。
抢占式调度算法需要在时间间隔末端发生时钟中断，如果没有可用的时钟，那么非抢占式调度算法就是唯一的选择。
3. 调度算法分类
不同的环境需要不同的调度算法。三种环境划分：
- 批处理：非抢占式调度算法
- 交互式：抢占式
- 实时
4. 调度算法的目标
批处理系统中的调度
（1）先来先服务
易于理解并且便于在程序中运用。
（2）最短作业优先
适用于运行时间可以预知的非抢占式批处理调度算法。
（3）最短剩余时间优先
最短作业优点的抢占式版本。
交互式系统中的调度
（1）轮转调度
进程切换（上下文切换）：需要1ms，包括切换内存映像、清除和重新调入高速缓存等。
时间片设置得太长（长于平均的CPU突发时间）可能引起对短的交互请求的响应时间变长，设置得太短又会导致过多的进程切换，降低CPU效率。将时间片设为20~50ms通常是一个比较合理的折中。
（2）优先级调度
为了防止高优先级进程无休止地运行下去，调度进程可能在每个时钟滴答（每个时钟中断）降低当前进程的优先级。另一个可能的做法是，给每个进程赋予一个允许运行的最大时间片，当用完这个时间片时，次高优先级的进程便会获得运行机会。
、
（3）多级队列
最高优先级类的进程运行一个时间片，次高优先级进程运行两个时间片，再次一级运行4个时间片，以此类推。当一个进程用完分配的时间片后，会被移到下一优先级类，即随着进程优先级不断降低，它的运行频度逐渐放慢。
（4）最短进程优先
根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。
（5）保证调度
向用户作出明确的性能保证。例如：若有用户同时有n个用户登录，则用户将获得CPU处理能力的1/n。
为了实现这个目标，系统需要跟踪各个进程自创建以来已使用了多少CPU时间，然后计算各个进程应获得的CPU时间。
（6）彩票调度
为进程提供各种系统资源（如CPU时间）的彩票，当需要作出调度决策时，就随机抽出一张彩票，拥有该彩票的进程获得资源。如果给三个进程分别分配10、25、50张彩票，那么它们会自动地按照大致2：4：5的比例划分CPU的使用。
（7）公平分享调度
以用户为基本单位分配CPU，不论这些用户本身有几个进程。
实时系统中的调度
实时系统通常可以分为硬实时和软实时，前者的含义是必须满足绝对的截止时间，后者的含义是虽然不需要偶尔错失截止时间，但是可以容忍。
实时系统中的事件可以按照响应方式进一步分类为周期性事件或非周期性事件。一个周期事件可以被调度的条件是处理该事件的CPU时间小于该事件的周期。
策略和机制
将调度机制与调度策略分离，使得调度算法可以从用户进程接收有关的调度决策信息（调度算法参数化）。
线程调度
用户级线程和内核级线程之间的差别在于性能，用户级线程的线程切换需要少量的机器指令，而内核级线程需要完整的上下文切换，修改内存映像，使高速缓存失效，这导致了若干数量级的延迟。另一方面，使用内核级线程时，一旦线程阻塞在I/O上就不需要像在用户级线程中那样将整个进程挂起。