1 进程模型

进程是对正在运行程序的一个抽象。一个进程就是一个正在执行程序的实例，包括程序计数器，寄存器和变量。每个进程都拥有它自己的虚拟CPU，实际上真正的CPU在进程之间来回切换。对于单核CPU，或者多核CPU的一个核，在同一时刻只能运行一个进程。单个处理器可以被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。

1.1 进程的状态

进程的基本状态有以下三个：

• 运行态：该时刻进程正在占用CPU
• 就绪态：进程可运行，但因为其他进程正在运行而停止
• 阻塞态：除非某种外部事件发生，否则进程不能运行

进程的状态与转换

如上图，进程在这三个状态之间可以有四种可能的转换关系:

1. 进程为等待输入而阻塞
2. 调度程序选择另一个进程
3. 调度程序选择这个程序
4. 出现有效输入

1.2 进程的实现模型

操作系统维护了一个进程列表，进程表里的每一项都是当前启动的进程对应的进程控制块（PCB）。PCB中包含了进程状态的重要信息：程序计数器PC，堆栈指针，内存分配状况，打开的文件状态，账号信息，调度信息等等。

PCB中的一些字段

2. 线程

2.1 线程的实现模型

线程是一种轻量级的进程。

• 多个线程拥有共享同一个地址空间和所有可用数据的能力。
• 线程比进程更容易创建和销毁。
• 在大量计算和大量I/O处理过程中，多个线程能够加快程序执行速度。

进程模型基于两种独立的概念：资源管理与执行调度。引入了线程模型，将资源管理与执行调度这两个功能区分开来：进程用于把所需资源集中到一起，而线程则是在CPU上被调度执行的实体。

2.2 线程的三种实现

操作系统将运行环境区分为用户空间和内核。因此线程可以被创建到不同运行环境：

2.2.1 在用户空间中实现

把整个线程包放在用户空间中，内核对线程包一无所知。从内核角度考虑，就是单进程单线程。线程在一个运行时系统的顶部运行，这个运行时系统是一个管理线程的过程的集合。每个进程有其专用线程表（thread table）。

• 优点：用户线程包可以在不支持线程的操作系统上实现。不需要陷进，不需要上下文切换，不需要对内存高速缓存进行刷新，使得线程调度非常快。允许每个进程有自己定制的调度算法。
• 问题：如何实现阻塞系统调用，使用阻塞调用会阻塞其他的线程。页面故障问题，如果某个调用跳转到了一条不在内存的指令上，就会发生页面故障，内核由于不知道线程的存在，通常会把整个进程阻塞到I/O完成。如果一个线程开始运行，那么该进程中的其他线程就不能运行，除非第一个线程自动放弃CPU。

2.2.2 在内核中实现线程

此时不需要运行时系统，内核中有用来记录系统中所有线程的线程表。当一个线程阻塞时，内核根据其选择，可以运行同一个进程中的另一个线程或者运行另一个进程中的线程。

• 优点：内核很容在线程阻塞时切换到另一个线程执行。内核线程不需要任何新的、非阻塞系统调用。
• 问题：在内核中创建或销毁线程的代价比较大。进程创建问题，一个多线程进程创建新进程出现的问题。当信号到达时，应该由哪一个线程处理。

2.2.3 混合实现

使用内核线程，然后将用户级线程与某些或者全部内核线程多路复用起来。内核只识别内核线程，并对其进行调度。一些内核线程会被多个用户级线程多路复用。这一模型能够带来最大的灵活度。

3. 进程间通信

进程间通信（Inter Process Communication，IPC）简要的说有三个问题：

1. 一个进程如何把信息传递给另一个。
2. 确保两个或更多的进程在关键活动中不会出现交叉。
3. 保证进程以正确的顺序执行。

3.1 竞争条件与临界区

在一些操作系统中，协作的进程可能共享一些彼此都能读写的公用存储区。两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件（race condition）。我们把对共享内存进行访问的程序片段称作临界区（critical region/section）。

3.2 互斥

互斥（mutual exclusion）：即以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。

实现忙等待的互斥（即CPU轮询等待）：

• 屏蔽中断 ： 不适合多核CPU
• 锁变量：无效
• 严格轮换法：无效

• Peterson解法：

  
  
  完成互斥的Peterson解法

• TSL指令：test and set lock，是CPU级别的原子指令，即该指令结束之前，其他处理器不允许访问该内存。执行TSL指令的CPU将锁住内存总线，需要硬件支持。

  
  
  用TSL指令进入和离开临界区

由于忙等待会浪费CPU资源，而且会产生优先级反转问题，所以一般会使用sleep和wakeup这两个系统调用。以下是使用了这两个系统调用后的生产者-消费者问题示例：

生产者-消费者问题

3.3 信号量

信号量（semaphore）是Dijkstra在1965年提出的一种方法，使用一个整型变量来累计唤醒次数。使用两种操作：down和up来修改信号量。修改信号量的操作是原子操作。

使用信号量实现的生产者-消费者问题

如果不需要信号量的计数能力，则可以使用信号量的一个简化版本，称为互斥量（mutex）。互斥量实现简单，常用于实现用户空间线程包。互斥量有两个状态：解锁和加锁。

互斥量的加锁和解锁操作

3.4 管程

管程（monitor）是一种高级同步原语，是用来简化程序和减少死锁。一个管程是一个由过程，变量，及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。管程是语言特性，C语言不支持。Java中的管程是synchronized。

3.5 消息传递

上面的技术都是用来解决访问公共内存的一个或多个CPU上的互斥问题。但若无法共享内存，则无法使用上面的那些方法，因而需要使用消息传递（message passing）的方法来解决。消息传递使用send和receive两条原语在进程间通信。

3.6 屏障

屏障（barrier） 是适用于一组进程的同步机制。在应用中将程序划分成若干段，且规定除非所有进程都就绪准备进入下一个阶段，否则任何进程都不能进入下一个阶段。通过在每个阶段结尾安置屏障来实现这种行为。

4 调度算法

当多个进程或线程同时竞争一个CPU是，就需要操作系统来选择下一个要运行的进程，完成选择工作的这一部分程序称为调度程序（scheduler），该程序使用的算法称为调度算法（scheduling algorithm）。

• 进程行为分为两种：计算密集型和I/O密集型
• 进程调度的时机：
  • 创建新进程时，需要决定是运行父进程还是运行子进程
  • 在一个进程推出时，需要作出调度决策
  • 当进程阻塞在I/O和信号量上或其他原因阻塞时，必须选择另一个进程运行
  • 在一个I/O中断发生时，必须做出调度决策
• 进程调度运行环境分类：批处理、交互式、实时

调度算法的目标：

• 所有系统：
  • 公平：给每个进程公平的CPU份额
  • 策略强制执行：保证规定的策略被执行
  • 平衡：保持系统的所有部分都忙碌
• 批处理系统
  • 吞吐量：每小时最大作业数
  • 周转时间：从提交到终止间的最小时间
  • CPU利用率：保持CPU始终忙碌
• 交互式系统
  • 响应时间：快速响应请求
  • 均衡性：满足用户的期望
• 实时系统：
  • 满足截止时间：避免丢失数据
  • 可预测性：在多媒体系统中避免品质降低

常用调度算法：

• 批处理
  • 先来先服务
  • 最短作业优先
  • 最短剩余时间优先
• 交互式
  • 轮转调度
  • 优先级调度
  • 多级队列
  • 最短进程优先
  • 保证调度
  • 彩票调度
  • 公平分享调度
• 实时
  • 判断是否可以在指定时间执行完所有任务

• 策略和机制分离原则：将调度算法以某种形式参数化，而参数可以由用户进程填写。

参考： 《现代操作系统》第4版