进程与线程
- 进程
- 一个进程就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。
- 进程的创建
- 4 种主要事件会导致进程的创建:
- 系统初始化
- 正在运行的程序执行了创建进程的系统调用
- 用户请求创建一个新进程
- 一个批处理作业的初始化
- 前台进程，与用户交互完成工作的进程
- 后台进程，与特定的用户没有关系，完成专门功能的进程，守护进程
- 在 UNIX 系统中，只有一个系统调用可以用来创建新进程:fork。这个系统调用会创建一个与调用进程相同的副本。在调用了 fork 后，这两个进程(父进程和子进程)拥有相同的内存映像、同样的环境字符串和同样的打开文件。这就是全部情形。通常 ，子进程接着执行 execve 或一个类似的系统调用，以修改其内存映像并运行一个新的程序。之所以要安排两步建立进程，是为了在 fork 之后但在 execve 之前允许该子进程处理其文件描述符，这样可以完成对标准输入文件、标准输出文件和标准错误文件的重定向。
- 在 UNIX 中，子进程的初始地址空间是父进程的一个副本，但是这里涉及两个不同的地址空间，不可写的内存区是共享的。某些 UNIX 的实现使程序正文在两者间共享，因为它不能被修改。或者，子进程共享父进程的所有内存，但这种情况下内存通过写时复制 (copy-on-write) 共享，这意味着一且两者之一想要修改部分内存，则这块内存首先被明确地复制，以确保修改发生在私有内存区域。
- 进程的终止
- 通常有以下几种情况会导致进程的终止
- 正常退出(自愿的)。
- 出错退出(自愿的).
- 严重错误(非自愿)。
- 被其他进程杀死(非自愿).
- 进程的层次结构
- 某些系统中，当进程创建了另一个进程后，父进程和子进程就以某种形式继续保持关联。子进程自身可以创建更多的进程，组成一个进程的层次结构。
- 在 UNIX 中，进程和它的所有子进程以及后裔共同组成一个进程组。
- 进程的状态
- 运行态(该时刻进程实际占用 CPU)。
- 就绪态(可运行，但因为其他进程正在运行而暂时停止)。
- 阻塞态(除非某种外部事件发生，否则进程不能运行).
- 进程的实现
- 操作系统维护进程表
- 每个进程占用一个表项目，称为进程控制块，里面有程序运行的必要信息。
- 所有的中断都从保存寄存器开始，对于当前进程而言，通常是保存在进程表项中。
- 当一个 I/O 中断发生时，中断硬件将程序计数器、程序状态字、有时还有一个或多个寄存器压入堆栈，计算机随即跳转到中断向量所指示的地址。这些是硬件完成的所有操作，然后软件，特别是中断服务例程就接管一切剩余的工作。
- 中断发生后操作系统最底层的工作步骤
- 硬件压人堆栈程序计数器等
- 硬件从中断向量装人新的程序计数器
- 汇编语言过程保存寄存器值
- 汇编语言过程设置新的堆栈
- C 中断服务例程运行 (典型地读和缓冲输入)
- 调度程序决定下一 个将运行的进程
- C 过程返回至汇编代码
- 汇编语言过程开始运行新的当前进程
- 一个进程在执行过程中可能被中断数千次，但关键是每次中断后被中断的进程都返回到与中断发生前完全相同的状态。
- 多道程序设计模型
- 采用多道程序设计可以提高 CPU 的利用率。
- 假设一个进程等待 I/O 操作的时间与其停留在内存中时间的比为 p。当内存中同时有 n 个进程时、则所有 n 个进程都在等待 I/O (此时 CPU 空转)的概率是\( p^n \)。CPU 的利用率由下面的公式给出: \(CPU 利用率=1-p^n\)
- 线程
- 线程的使用
- 人们需要多线程的主要原因是，在许多应用中同时发生若多种活动。其中某些活动随着时间的推移会被阻塞。通过将这些应用程序分解成可以准井行运行的多个顺序线程，程序设计校型会变得更简单。
- 在有了多线程概念之后，我们才加入了一种新的元素: 并行实体拥有共享同一个地址空间和所有可用数据的能力
- 线程比进程更轻量级，所以它们比进程更容易(即更快)创建，也更容易撤销。许多系统中，创建一个线程较创建一个进程要快 1~100 倍
- 如果存在着大量的计算和大量的 I/O 处理，拥有多个线程允许这些活动彼此重叠进行，从而会加快应用程序执行的速度。
- 在多 CPU 系统中，多线程是有益的，在这样的系统中，真正的并行有了实现的可能
- 经典的线程模型
- 进程模型基于两种独立的概念:资源分组处理与执行。
- 进程有存放程序正文和数据以及其他资源的地址空间。这些资源中包括打开的文件、子进程、即将发生的定时器、信号处理程序、账号信息等。把它们都放到进程中可以更容易管理。
- 进程拥有一个执行的线程，通常简写为线程 (thread)。在线程中有一个程序计数器，用来记录接着要执行哪一条指令。线程拥有寄存器，用来保存线程当前的工作变量。线程还拥有一个堆栈，用来记录执行历史，其中每一帧保存了一个已调用的但是还没有从中返回的过程。尽管线程必须在某个进程中执行.但是线程和它的进程是不同的概念，并且可以分别处理。进程用于把资源集中到一起，而线程则是在 CPU 上被调度执行的实体。
- 在同一个进程环境中，允许彼此之间有较大独立性的多个线程执行。在同一个进程中并行运行多个线程，是对在同一台计算机上并行运行多个进程的模拟。
- 由于线程具有进程的某些性质，所以有时被称为轻量级进程
- 一些 CPU 已经有直接硬件支持多线程，并允许线程切换在纳秒级完成。
- 由于各个线程都可以访问进程地址空间中的每一个内存地址，所以一个线程可以读、写或甚至清除另一个线程的堆栈。线程之间是没有保护的。不可能也没有必要实现保护，实现多线程的初衷就是为了贡献资源并协作。
- 每个进程中的内容
- 地址空间
- 全局变量
- 打开文件
- 子进程
- 定时器
- 信号和信号处理程序
- 账户信息
- 每个线程中的内容
- 线程概念试图实现的是，共享一组资源的多个线程的执行能力，以便这些线程可以为完成某一任务而共同工作 。
- 和传统进程一样(即只有一个线程的进程)，线程可以处于若干种状态的任何一个:运行、阻塞、就绪或终止。
- 每个线程有其自己的堆栈,每个线程的堆栈有一帧，供各个被调用但是还没有从中返回的过程使用。在该栈帧中存放了相应过程的局部变量以及过程调用完成之后使用的返回地址。
- 多线程的情况下，进程通常会从当前的单个线程开始。这个线程有能力通过调用一个库函数(如 thread_create)创建新的线程
- 创建线程通常都返回一个线程标识符，该标识符就是新线程的名字。
- 另一个常见的线程调用是 thread_yield, 它允许线程自动放弃 CPU 从而让另一个线程运行。因为不同于进程，(线程库)无法利用时钟中断强制线程让出 CPU。所以设法使线程行 为“高尚”起来，并且随着时间的推移自动交出 CPU, 以便让其他线程有机会运行，就变得非常重要。
- 复杂性
- 如果子进程拥有了与父进程一样的多个线程，如果父进程在 read 系统调用(比如键盘)上被阻塞了会发生什么情况?
- 另一类问题和线程共享许多数据结构的事实有关。如果一个线程关闭了某个文件，而另一个线程还在该文件上进行读操作时会怎样?假设有一个线程注意到几乎没有内存了，并开始分配更多的内存。在工作一半的时候，发生线程切换，新线程也注意到几乎没有内存了，并且也开始分配更多的内存。这样，内存可能会被分配两次。
- POSIX 线程
- 为实现可移植的线程程序，IEEE 在 IEEE 标准 1003.lc 中定义了线程的标准。它定义的线程包叫作 pthread。
- 主要函数特性
- pthread_create，创建一个新的线程，新创建的线程的线程标识符会作为函数值返回
- pthread_exit，终止该线程并释放它的栈。
- pthread_join，用来等待别的特定线程的终止。而要等待线程的线程标识符作为一个参数给出。
- pthread_yield，让出 CPU 时间片
- pthread_attr_init，建立关联一个线程的属性结构井初始化成默认值
- pthread_attr_destroy，删除一个线程的属性结构，释放它占用的内存
- 在用户空间实现线程
- 内核无感知，从内核角度考虑，就是按正常的方式管理，即单线程进程。
- 用户级线程包可以在不支持线程的操作系统上实现
- 在用户空间管理线程时，每个进程需要有其专用的线程表，工作方式于进程表类似
- 切换速度快，不需要陷入内核，不需要上下文切换，也不需要对内存高速缓存进行刷新，这就使得线程调度非常快捷。
- 允许每个进程有自己定制的调度算法
- 扩展性好，内核空间线程需要一些固定表格空间和堆栈空间。
- 实现阻塞调用难度高
- 缺页中断，导致内核中断整个进程直到 I/O 完成
- 没有时钟中断，调度问题
- 在内核空间实现线程
- 内核中有用来记录系统中所有线程的线程表
- 内核的线程表保存了每个线程的寄存器、状态和其他信息。
- 所有能够阻塞线程的调用都以系统调用的形式实现
- 在内核中创建或撤销线程的代价比较大，某些系统采取“环保"的处理方式，回收其线程。当某个线程被撤销时，就把它标志为不可运行的，但是其内核数据结构没有受到影响。稍后，在必须创建一个新线程时，就重新启动某个旧线程，从而节省了一些开销。
- 内核线程不需要任何新的、非阻塞系统调用
- 信号是发给进程而不是线程的，当多个线程注册了同一个信号会发生什么?
- 混合实现
- 人们已经研究了各种试图将用户级线程的优点和内核级线程的优点结合起来的方法。一种方法是使用内核级线程，然后将用户级线程与某些或者全部内核线程多路复用起来。内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。如同在没有多线程能力操作系统中某个进程中的用户级线程 一样，可以创建、撤销和调度这些用户级线程。在这种梭型中，每个内核级线程有一个可以轮流使用的用户级线程集合.
- 调度程序激活机制
- 调度程序激活工作的目标是模拟内核线程的功能，但是为线程包提供通常在用户空间中才能实现的更好的性能和更大的灵活性。
- 当使用调度程序激活机制时，内核给每个进程安排一定数量的虚拟处理器，并且让(用户空间)运行时系统将线程分配到处理器上。
- 使该机制工作的基本思路是，当内核了解到一个线程被阻塞之后，内核通知该进程的运行时系统，并且在堆栈中以参数形式传递有问题的线程编号和所发生事件的一个描述。内核通过在一个已知的起始地址启动运行时系统，从而发出了通知，这是对 UNIX 中信号的一种粗略模拟。这个机制称为上行调用(upcall)。
- 违反分层次系统内在结构
- 弹出式线程
- 一个消息的到达导致系统创建一个处理该消息的线程，这种线程称为弹出式线程
- 对该新线程指定所要处理的消息。使用弹出式线程的结果是.消息到达与处理开始之间的时间非常短。
- 使单线程代码多线程化
- 一些容易犯的错误
- 多线程读写全局变量
- 可重入问题
- 信号共享问题
- 堆栈的管理
- 进程间通信
- 需要解决的问题
- 一个进程如何把信息传递给另一个
- 确保两个或更多的进程在关键活动中不会出现交叉
- 保证相互关联的进程执行的顺序正确
- 竞争条件
- 两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件
- 临界区
- 在某些时候进程可能需要访问共享内存或共享文件，或执行另外一些会导致竞争的操作。我们把对共享内存进行访问的程序片段称作临界区域 (critical region) 或 临界区。
- 需要满足的条件
- 任何两个进程不能同时处于其临界区
- 不应对 CPU 的速度和数量做任何假设
- 临界区外运行的进程不得阻塞其他进程
- 不得使进程无限期等待进人临界区
- 忙等待的互斥
- 几种实现互斥的方案
- 屏蔽中断
- 每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也被屏蔽,阻止了进程切换，在多 CPU 下不适用，而且低效。
- 锁变量
- 设想有一个共享(锁)变量，其初始值为 0。当一个进程想进人其临界区时，它首先测试这把锁。
- 读锁与写锁操作不具有原子性
- 严格轮换法
- 整型变量 turn,初始值为 0,用于记录轮到哪个进程进入临界区，井桧查或更新共享内存。开始时，进程 0 检查 turn,发现其值为 0, 于是进入临界区。进程 1 也发现其值为 0,所以在一个等待循环中不停地测试 turn. 看其值何时变为 1。连续测试一个变量 直到某个值出现为止，称为忙等待。只有当认为当等待时间是很短的时候才使用这种方案
- 用于忙等待的锁，称为自选锁。
- Peterson 解法
- 在使用共享变及(即进入其临界区)之前，各个进程使用其进程号 0 或 1 作为参数来调用 enter_region。该调用在需要时将使进程等待，直到能安全地进入临界区。在完成对共享变量的操作之后，进程将调用 leave_region, 表示操作已完成，若其他的进程希望进入临界区，则现在就可以进入。
- TSL 指令
- TSL RX, LOCK 称为测试并加锁。
- 它将一个内存字 lock 读到寄存器 RX 中，然后在该内存地址上存一个非零值。读字和写字操作保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字。执行 TSL 指令的 CPU 将锁住内存总线，以禁止其他 CPU 在本指令结束之前访问内存。
- 当操作结束时，进程用一条普通的 move 指令将 lock 的值重新设置为 0。
- 锁住存储总线不同干屏蔽中断。屏蔽中断，然后在读内存字之后跟右写操作井不能阻止总线上的第二个处理器在读操作和写操作之间访问该内存字。
- 一个可替代 TSL 的指令是 XCHG, 它原子性地交换了两个位置的内容
- 睡眠与唤醒
- Peterson 解法和 TSL 或 XCHG 解法有忙等待的缺点。
- 低优先级进程无法离开临界区，优先级反转问题
- sleep 原语，wakeup 原语
- 信号量
- 提供一个整型变让来累计唤醒次数，供以后使用。一个信号量的取值可以为 0 (表示没有保存下来的唤醒操作)或者为正值(表示有一个或多个唤醒操作)。
- PV 操作: P 表示尝试 , V 表示升高
- 原子操作，是指一组相关联的操作要么都不间断地执行，要么都不执行。
- 对一信号量执行 down 橾作，则是检查其值是否大干 0。若该值大于 0, 则将其值减 1 井继续；若该值为 0, 则进程将睡眠
- up 操作作对信号量的值增 1。如果一个或多个进程在该信号众上睡眠，无法完成一个先前的 down 操作， 则由系统选择其中的一个并允许该进程完成它的 down 操作。于是，对一个有进程在其上睡眠的信号量执行一次 up 操作之后，该信号量的值仍旧是 0, 但在其上睡眠的进程却少了一个。
- 信号量的另一种用途是用于实现同步
- 互斥量
- 信号量的一个简化版本，称为互斥量
- 互斥量是一个可以处于两态之一的变量:解锁和加锁。这样，只需要一个二进制位表示它，不过实际上，常常使用一个整型量， 0 表示解锁，而其他所有的值则表示加锁 。互斥量使用两个过程。当一个线程(或进程)需要访问临界区时，它调用 mutex_lock。如果该互斥量当前是解锁的(即临界区可用). 此调用成功，调用线程可以自由进入该临界区。
- 另一方面，如果该互斥呈已经加锁，调用线程被阻塞，直到在临界区中的线程完成井调用 mutex_unlock。如果多个线程被阻塞在该互斥量上，将随机选择一个线程井允许它获得锁.
- 当获取 mutex_lock 失败，线程调用 thread_yield 将 CPU 放弃给另一个线程。
- 多个进程如何互斥
- 第一种，有些共享数据结构，如信号量，可以存放在内核中，并且只能通过系统调用来访问。
- 第二种，多数现代操作系统 (包括 UNIX 和 Windows) 提供一种方法，让进程与其他进程共享其部分地址空间。在这种方法中，缓冲区和其他数据结构可以共享。在最坏的情形下，如果没有可共享的途径，则可以使用共享文件。
- 快速用户区互斥量 futex
- futex 由一块能够被多个进程共享的内存空间（一个对齐后的整型变量）组成
- 实现了基本的锁(很像互斥锁)，但避免了陷入内核，除非它真的不得不这样做。
- 一个 futex 包含两个部分 : 一个内核服务和一个用户库。内核服务提供一个等待队列，它允许多个进程在一个锁上等待。
- 没有竞争时，futex 完全在用户空间工作。
- 如果该锁被另一个线程持有，那么线程必须等待。这种情况下，futex 库不自旋，而是使用一个系统调用把这个线程放在内核的等待队列上。
- 当一个线程使用完该锁，它通过原子操作“增加并检验”来释放锁，并检查结果，看是否仍有进程阻塞在内核等待队列上。如果有，它会通知内核可以对等待队列里的一个或多个进程解除阻塞。如果没有锁竞争，内核则不需要参与其中。
- pthread 中的互斥量
- pthread 提供许多可以用来同步线程的函数。其基本机制是使用一个可以被锁定和解锁的互斥量来保护每个临界区。
- 互斥量在允许或阻塞对临界区的访问上是很有用的，条件变量则允许线程由于一些未达到的条件而阻塞。
- 管程
- 一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但它们不能在管程之外声明的过程中直接访问管程内的数据结构。
- 管程有一个很重要的特性.即任一时刻管程中只能有一个活跃进程，这一特性使管程能有效地完成互斥。
- 典型的处理方法是，当一个进程调用管程过程时，该过程中的前几条指令将检查在管程中是否有其他的活跃进程。如果有，调用进程将被挂起，直到另一个进程离开管程将其唤醒。如果没有活跃进程在使用管程，则该调用进程可以进入。
- 进入管程时的互斥由编译器负责，但通常的做法是用一个互斥量或二元信号量。
- java 的 synchronized 就是一种管程的实现
- 用于处理共享内存的访问问题，对于多 CPU 和分布式系统，需要额外的手段。
- 消息传递
- 这种进程间通信的方法使用两条原语 send 和 receive, 它们像信号量而不像管程，是系统调用而不是语言成分。
- 前一个调用向一个给定的目标发送一条消息，后一个调用从一个给定的源接收一条消息。如果没有消息可用，则接收者可能被阻塞，直到一条消息到达，或者，带着一个错误码立即返回 。
- 设计要点
- 一个著名的消息传递系统是消息传递接口(MPI)
- 屏障
- 当一个进程到达屏障时，它就被屏障阻拦，直到所有进程都到达该屏障为止。屏障可用于一组进程同步，
- 避免锁：读-复制-更新
- 在某些情况下，我们可以允许写操作来更新数据结构，即便还有其他的进程正在使用它。窍门在干确保每个读操作要么读取旧的数据版本，要么读取新的数据版本，但绝不能是新旧数据的一些奇怪组合。
- 调度
- 当计算机系统是多道程序设计系统时，通常就会有多个进程或线程同时竞争 CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个 CPU 可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序(scheduler), 该程序使用的算法称为调度算法(scheduling algorithm)。
- 调度简介
- 几乎所有进程的(磁盘或网络) I/O 请求和计箕都是交替突发的
- 典型的计算密集型进程具有较长时间的 CPU 集中使用和较小频度的 I/O 等待。 I/O 密集型进程具有较短时间的 CPU 集中使用和频繁的 I/O 等待。 它是 I/O 类的，因为这种进程 在 I/O 请求之间较少进行计算，并不是因为它们有特别长的 I/O 请求。在 I/O 开始后无论处理数据是多还是少，它们都花费同样的时间提出硬件请求读取磁盘块 。
- 随着 CPU 变得越来越快，更多的进程倾向为 I/O 密集型
- 何时调度
- 在创建一个新进程之后，需要决定是运行父进程还是运行子进程。
- 在一个进程退出时必须做出调度决策。一个进程不再运行(因为它不再存在)，所以必须从就绪进程集中选择另外某个进程。如果没有就绪的进程，通常会运行一个系统提供的空闲进程。
- 当一个进程阻塞在 I/O 和信号量上或由于其他原因阻塞时，必须选择另一个进程运行。
- 在一个 I/O 中断发生时，必须做出调度决策。
- 非抢占式调度算法挑选一个进程，然后让该进程运行直至被阻塞，或者直到该进程自动释放 CPU.即使该进程运行了若干个小时，它也不会被强迫挂起。这样做的结果是，在时钟中断发生时不会进行调度。在处理完时钟中断后，如果没有更高优先级的进程等待到时，则被中断的进程会继续执行 。
- 抢占式调度算法挑选一个进程，井且让该进程运行某个固定时段的最大值。如果在该时段结束时，该进程仍在运行，它就被挂起，而调度程序挑选另一个进程运行。进行抢占式调度处理，需要在时间间隔的末端发生时钟中断，以便把 CPU 控制返回给调度程序。如果没有可用的时钟，那么非抢占式调度就是唯一的选择了 。
- 调度算法分类
- 批处理
- 批处理系统在商业领域仍在广泛应用，用来处理薪水册、存货清单、账目收入、账目支出、利息计算(在银行)、索赔处理(在保险公司)和其他的周期性的作业 。
- 减少了进程的切换从而改善了性能
- 交互式
- 为了避免一个进程霸占 CPU 拒绝为其他进程服务，抢占是必需的
- 抢占也是必要的。服务器也归于此类，因为通常它们要服务多个突发的(远程)用户。
- 实时
- 在有实时限制的系统中，抢占有时是不需要的，因为进程了解它们可能会长时间得不到运行，所以通常很快地完成各自的工作并阻塞。实时系统与交互式系统的差别是，实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶意的程序。
- 调度算法的目标
- 公平一一给每个进程公平的 CPU 份额
- 策略强制执行一一保证规定的策略被执行
- 平衡一一保持系统的所有部分都忙碌
- 批处理系统
- 吞吐量一一每小时最大作业数
- 周转时间一一从提交到终止间的最小时间
- CPU 利用率一一保持 CPU 始终忙碌
- 交互式系统
- 实时系统
- 满足截止时间一避免丢失数据
- 可预测性一一在多媒体系统中避免品质降低
- 批处理系统中的调度
- 交互式系统中的调度
- 轮转调度
- 每个进程被分配一个时间段，称为时间片 (quantum), 即允许该进程在该时间段中运行。如果在时间片结束时该进程还在运行，则将剥夺 CPU 井分配给另一个进程。如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。
- 时间片轮转调度很容易实现，调度程序所要做的就是维护一张可运行进程列表
- 时间片轮转调度中唯一有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间进行管理事务处理的,更新各种表格和列表、消除和重新调入内存高速缓存等。时间片的长度影响 CPU 效率。
- 优先级调度
- 每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。
- 为了防止高优先级进程无休止地运行下去，调度程序可能在每个时钟滴答(即每个时钟中断)降低当前进程的优先级。
- 另一种方法是，给每个进程赋予一个允许运行的最大时间片，当用完这个时间片时，次高优先级的进程便获得运行机会。
- 多级队列
- 设立优先级类。属于最高优先级类的进程运行一个时间片，属于次高优先级类的进程运行 2 个时间片，再次一级运行 4 个时间片，以此类推。当一个进程用完分配的时间片后，它被移到下一类。
- 最短进程优先
- 由于最短作业优先常常伴随君最短响应时间，所以如果能够把它用千交互进程，那将是非常好的。
- 保证调度
- 为了实现所做的保证，系统必须跟踪各个进程自创建以来已使用了多少 CPU 时间。然后它计箕各个 进程应获得的 CPU 时间，即自创建以来的时间除以 n。由于各个进程实际获得的 CPU 时间是已知的，所以很容易计算出真正获得的 CPU 时间和应获得的 CPU 时间之比。比率为 0.5 说明一个进程只获得了应得时间的一半，而比率为 2.0 则说明它获得了应得时间的 2 倍。于是该算法随后转向比率最低的进程，直到该进程的比率超过它的最接近竞争者为止。
- 彩票调度
- 进程提供各种系统资源(如 CPU 时间)的彩禀。 一旦需要做出一项调度决策时，就随机抽出一张彩票，拥有该彩票的进程获得该资源。在应用到 CPU 调度时，系统可以掌握每秒钟 50 次的一种彩票，作为奖励每个获奖者可以得到 20ms 的 CPU 时间。
- 彩栗调度可以用来解决用其他方法很难解决的问题。一个例子是，有一个视频服务器，在该视频服务器上若干进程正在向其客户提供视频流，每个视频流的帧速率都不相同。假设这些进程需要的帧速率分别是 1O、20 和 25 帧/秒。如果给这些进程分别分配 10、 20 和 25 张彩票，那么它们会自动地按照大致正确的比例(即 10:20:25)划分 CPU 的使用。
- 公平分享调度
- 某些系统在调度处理之前考虑谁拥有进程这一因素。在这种模式中，每个用户分配到 CPU 时间的一部分，而调度程序以一种强制的方式选择进程。这样，如果两个用户都得到获得 50% CPU 时间的保证，那么无论一个用户有多少进程存在，每个用户都会得到应有的 CPU 份额。
- 实时系统中的调度
- 实时系统是一种时间起着主导作用的系统。
- 计算机必须在一个确定的时间范围内恰当地做出反应
- 实时系统通常可以分为硬实时 (hard real time) 和软实时 (soft real time) , 前者的含义是必须满足绝对的截止时间，后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。在这两种情形中，实时性能都是通过把程序划分为一组进程而实现的，其中每个进程的行为是可预测和提前掌握的。这些进程 一般寿命较短，并且极快地运行完成。在检测到一个外部信号时 ， 调度程序的任务就是按照满足所有截止时间的要求调度进程。
- 策略和机制
- 对于一个进程有许多子进程井在其控制下运行，调度程序无法知晓哪个进程最重要，解决问题的方法是将调度机制与调度策略分离这个一贯的原则。也就是将调度算法以某种形式参数化，而参数可以由用户进程填写。
- 线程调度
- 当若干进程都有多个线程时，就存在两个层次的并行:进程和线程。在这样的系统中调度处理有本质差别，这取决于所支持的是用户级线程还是内核级线程(或两者都支持)。
- 用户级线程
- 内核级别线程
- 内核选择一个特定的线程运行。它不用考虑该线程属千哪个进程，不过如果有必要的话，它可以这样做。对被选择的线程赋予一个时间片，而且如果超过了时间片，就会强制挂起该线程。
- 用户级线程和内核级线程之间的差别在于性能。用户级线程的线程切换需要少址的机器指令，而内核级线程垢要完整的上下文切换，修改内存映像，使高速缓存失效，这导致了若干数量级的延迟。另一方面，在使用内核级线程时，一且线程阻塞在 I/O 上就不需要像在用户级线程中那样将整个进程挂起 。
- 经典 IPC 问题
- 有关进程于线程的研究
- 多处理器上的线程集群
- 进程执行过程的记录和重放
- 调度间题
- 移动设备上的低能耗调度、超线程级调度