进程与线程 - 操作系统笔记

进程

进程的三种状态

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

线程

1. 每个线程有自己的堆栈。
2. 线程无法利用时钟中断强制线程让出CPU。

进程间通信

进程间通信需要解决三个问题：

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

线程间通信不需要考虑问题1，因为他们共享内存；但2和3对线程同样适用。

竞争条件：两个或多个进行读写某些共享数据，最后的结果取决于进程运行的精确时序。

互斥：阻止多个进程同时读写共享的数据。

临界区：对共享内存进行访问的程序片段。

忙等待：在单CPU情况下，一个进程进入临界区之后，其他进程因无法满足竞争条件而循环探测竞争条件。其缺点是，在单CPU情况下，等待进程循环探测竞争条件，浪费了时间片。只有在有理由认为等待时间是非常短的情形下，才应使用忙等待。用于忙等待在锁，称为自旋锁。

Peterson算法 (P70)

turn 表示现在轮到哪个进程；interested[N] 表示谁对临界区感兴趣。在进入临界区前执行

1

while (turn == process && interested[other] == TRUE);

Peterson算法会导致忙等待。

TSL指令

1

TSL RX, LOCK

将一个内存字lock读到寄存器RX中，然后在该内存地址上存一个非零值，读字和写字的操作保证是不可分割的，由硬件提供支持。

TSL适用于多处理器的情况，因为内存是共用的。当lock的值为1时，将导致忙等待。

XCHG

和TSL相似，只不过是先在寄存器中放一个1，再交换寄存器和锁变量中的内容，同样会导致忙等待。

信号量

信号量（semaphore）是一种特殊的整型变量，取值可以为0或正值。P/down尝试，使信号量减少；V/up增加或升高。通常将P/V作为系统调用，在测试信号量、更新信号量以及在需要时使某个进程睡眠时暂时屏蔽全部中断。如果使用多个CPU，通过TSL/XCHG命令来确保同一时刻只有一个CPU在对信号量进行操作。

供两个或多个进程使用的信号量，其初值为1，保证同时只有一个进程可以进入临界区，称作二元信号量。

互斥量是一个可以处在两态之一的量：解锁和加锁。当一个进程或线程需要访问临界区时，它调用mutex_lock。如果该互斥量当前是解锁的，此调用成功；否则，进程将被阻塞，直到临界区中的线程完成并调用mutex_unlock。如果有多个线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。在取锁失败时，它会调用thread_yield将CPU放弃给另一个线程，这样就不会导致忙等待。

管程

管程是一个由过程、变量、及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。任一时刻管程中只能有一个活跃进程，这一特性使管程能有效完成互斥。进入管程的互斥由编译器负责。

条件变量可以使进程在无法运行时被阻塞，提供了两个相关操作：wait和signal。当一个管程过程中发现它无法继续运行时，它会在某个条件变量上执行wait操作，该操作将导致进行自身阻塞，并且还将另一个以前等在管程之外的进程调入管程。另一个进程，可以通过signal操作唤醒正在睡眠的伙伴进程。Hoare管程将切换到被唤醒的线程执行，而Hansen管程将继续运行当前线程，因此比Hoare管程少一次切换。在对条件进行判断时，Hoare使用if即可，而Hansen需要使用while，因为当重新回到wait线程的时候情况可能发生了变化，因此需要继续判断。

条件变量不能像信号变量那样积累信号以便以后使用，所以wait操作必须在signal之前，否则signal将永远丢失。

信号量和管程通过TSL或XCHG指令来保护，因此这些机制都是设计用来解决访问公共内存的一个或多个CPU上的互斥问题。如果一个分布式系统具有多个CPU，并且每个CPU拥有自己的私有内存，它们通过一个局域网连接，那么这些原语将失效。

调度

批处理系统

吞吐量：系统每小时完成的作业数量；周转时间：从一个批处理作业提交时刻开始直到该作业完成时刻为止的平均统计时间；CPU利用率

非抢占式先来先服务 (first-come, fisrt-served)

进行按照他们请求CPU的顺序使用CPU，基本上有一个就绪进程的单一队列。作业不会因为运行时间太长而被中断。

优点：易于理解，便于在程序中运用。

缺点：对I/O进程不友好。

非抢占式最短作业优先 (shortest job first)

适用于运行时间可预知的情况，只有在所有的作业都可同时运行的情形下，最短作业优先算法是最优的。

抢占式最短剩余时间优先 (shortest remaining time next)

最短剩余时间优先是最短作业优先的抢占式版本。同样在运行时间可预知的情况下，调度程序总是选择剩余运行时间最短的程序运行。如果新的进程比当前运行进程需要更少的时间，当前进程被挂起而运行新的进程。这种方式可以使新的短作业获得良好的服务。

交互式系统

最小响应时间（最重要的指标）：发出命令到得到命令之间的时间。

轮转调度

假设：所有的进程同等重要。

每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行。如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换。调度程序维护一张可运行进程列表，当一个进程用完它的时间片后，就被移到队列的末尾。

时间片设得太短会导致过多的进程切换，降低了CPU的效率；而设得太长又可能引起对短的交互请求的响应时间变长。将时间片设为20-50ms通常是一个比较合理的折中。

优先级调度

每个进程被赋予一个优先级，允许优先级高的可运行进行先运行。优先级可以静态赋予也可以动态赋予。UNIX中有一条命令nice，它允许用户为了照顾别人而自愿降低自己进程的优先级。

可以很方便地将一级进程按照优先级分成若干类，并且在各类之间采用优先级调度，而在各类进程的内部采用轮转调度。缺点：低优先级进程可能会产生饥饿现象。

多级队列

属于最高优先级类的进程运行一个时间片，属于次高级优先级类的进程运行2个时间片，再次一级3个时间片，以此类推。当一个进程用完分配完的时间片后，它被移到下一类。

最短进程优先

根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。假设终端上每条命令的估计运行时间为$T_0$，现在假设测量到其下一次运行时间为$T_1$，可以用这两个值的加权和来改进估计时间：$aT_0+(1-a)T_1$，这种技术称为老化 (aging)。老化算法在$a=1/2$时特别容易实现，只需相加两个值后再右移一位。

保证调度

这种算法向用户作出明确的性能保证，然后去实现它。一种实际且容易实现的保证是：若用户工作时有$n$个用户登录，则用户将获得CPU处理能力的$1/n$。

彩票调度

保证调度不容易实现，而彩票调度可以给出类似的预测结果而又有非常简单的实现方法。其基本思想是为进程提供各种系统资源（如CPU时间）的彩票。一旦需要做出一项调度决策时，就随机抽出一张彩票，拥有该彩票的进程获得该资源。在应用到CPU调度时，系统可以掌握到每秒钟50次的一种彩票，作为奖励每个获奖者可以得到20ms的CPU时间。

公平共享调度

这种算法在调度处理之前考虑谁拥有进程这一因素。在这种模式中，每个用户分配到CPU时间的一部分，而调度程序以一种强制的方式选择进程。

实时系统

实时系统最主要的要求是满足所有的（或大多数）截止时间要求。

实时系统可以分为硬实时和软实时。前者的含义是必须满足绝对的截止时间的要求，后者可以容忍偶尔错失截止时间。

运行实时系统的调度算法可以是上面算法中的任一一种，从实用性考虑，轮转调度和优先级调度更为常用。