我们平常说的进程和线程更多的是基于编程语言的角度来说的，那么你真的了解什么是线程和进程吗？那么我们就从操作系统的角度来了解一下什么是进程和线程。
进程
操作系统中最核心的概念就是进程，进程是对正在运行中的程序的一个抽象。操作系统的其他所有内容都是围绕着进程展开的。进程是操作系统提供的最古老也是最重要的概念之一。即使可以使用的CPU只有一个，它们也支持（伪）并发操作。它们会将一个单独的CPU抽象为多个虚拟机的CPU。可以说：没有进程的抽象，现代操作系统将不复存在。
在许多多道程序系统中，CPU会在进程间快速切换，使每个程序运行几十或者几百毫秒。然而，严格意义来说，在某一个瞬间，CPU只能运行一个进程，然而我们如果把时间定位为1秒内的话，它可能运行多个进程。这样就会让我们产生并行的错觉。有时候人们说的两者并行(pseudoparallelism)就是这种情况，以此来区分多处理器系统(该系统由两个或多个CPU来共享同一个物理内存)
再来详细解释一下伪并行：伪并行是指单核或多核处理器同时执行多个进程，从而使程序更快。通过以非常有限的时间间隔在程序之间快速切换CPU，因此会产生并行感。缺点是CPU时间可能分配给下一个进程，也可能不分配给下一个进程。
因为CPU执行速度很快，进程间的换进换出也非常迅速，因此我们很难对多个并行进程进行跟踪，所以，在经过多年的努力后，操作系统的设计者开发了用于描述并行的一种概念模型（顺序进程），使得并行更加容易理解和分析，对该模型的探讨，也是本篇文章的主题。下面我们就来探讨一下进程模型
大家如果还想了解更多Linux内核开发相关的更多知识点，请后台私信我【内核】免费领取，里面记录了许多的Linux内核知识点。
内核学习网站：
Linux内核源码/内存调优/文件系统/进程管理/设备驱动/网络协议栈-学习视频教程-腾讯课堂
进程模型
在进程模型中，所有计算机上运行的软件，通常也包括操作系统，被组织为若干顺序进程(sequentialprocesses)，简称为进程(process)。一个进程就是一个正在执行的程序的实例，进程也包括程序计数器、寄存器和变量的当前值。从概念上来说，每个进程都有各自的虚拟空间CPU，但是实际情况是CPU会在各个进程之间进行来回切换。
如上图所示，这是一个具有4个程序的多道处理程序，在进程不断切换的过程中，程序计数器也在不同的变化。
在上图中，这4道程序被抽象为4各自拥有各自控制流程（即每个自己的程序计数器）的进程，并且每个程序都独立地运行。当然，实际上只有一个物理程序计数器，每个程序要运行时，其逻辑程序计数器会装载到物理程序计数器中。当程序运行结束后，其物理程序计数器就会是真正的程序计数器，然后再把它放回进程的逻辑计数器中。
从下图我们可以看到，在观察足够长的一段时间后，所有的进程都运行了，但在任何一个给定的瞬间仅有一个进程真正运行。
因此，当我们说一个CPU只能真正一次运行一个进程的时候，即使有2个核（或CPU），每一个核也只能一次运行一个线程。
由于CPU会在各个进程之间来回快速切换，所以每个进程在CPU中的运行时间是无法确定的。并且当同一个进程再次出现CPU中运行时，其在CPU内部的运行时间往往也是不固定的。进程和程序之间的区别是非常微妙的。
这里的关键思想是认识到一个进程所需的条件，进程是某一类特定活动的总和，它有程序、输入输出以及状态。单个处理器可以被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另外一个进程提供服务。另外需要注意的是，如果一个进程运行了两遍，则会被认为是两个进程。那么我们了解到进程模型后，那么进程是如何创建的呢？
进程的创建
操作系统需要一些方式来创建进程。下面是一些创建进程的方式
1、系统初始化
启动操作系统时，通常会创建若干个进程。其中有些是前台进程(numerousprocesses)，也就是同用户进行交互并替他们完成工作的进程。一些运行在后台，并不与特定的用户进行交互，例如，设计一个进程来接收发来的电子邮件，这个进程大部分的时间都在休眠，但是只要邮件到来后这个进程就会被唤醒。还可以设计一个进程来接收对该计算机上网页的传入请求，在请求到达的进程唤醒来处理网页的传入请求。进程运行在后台用来处理一些活动像是e-mail，web网页，新闻，打印等等被称为守护进程(daemons)。大型系统会有很多守护进程。在UNIX中，ps程序可以列出正在运行的进程，在Windows中，可以使用任务管理器。
2、系统调用创建
除了在启动阶段创建进程之外，一些新的进程也可以在后面创建。通常，一个正在运行的进程会发出系统调用用来创建一个或多个新进程来帮助其完成工作。例如，如果有大量的数据需要经过网络调取并进行顺序处理，那么创建一个进程读取数据，并把数据放到共享缓冲区中，而让第二个进程取走并正确处理会比较容易些。在多处理器中，让每个进程运行在不同的CPU上也可以使工作做得更快。
3、用户请求创建
在许多交互式系统中，输入一个命令或者双击图标就可以启动程序，以上任意一种操作都可以选择开启一个新的进程，在基本的UNIX系统中运行X，新进程将接管启动它的窗口。在Windows中启动进程时，它一般没有窗口，但是它可以创建一个或多个窗口。每个窗口都可以运行进程。通过鼠标或者命令就可以切换窗口并与进程进行交互。
交互式系统是以人与计算机之间大量交互为特征的计算机系统，比如游戏、web浏览器，IDE等集成开发环境。
4、批处理创建
最后一种创建进程的情形会在大型机的批量处理系统中应用。用户在这种系统中提交批处理作业。当操作系统决定它有资源来运行另一个任务时，它将创建一个新进程并从其中的输入队列中运行下一个作业。
从技术上讲，在所有这些情况下，现有流程执行流程是通过创建系统调用来创建新流程的。该进程可能是正在运行的用户进程，是从键盘或鼠标调用的系统进程或批处理程序。这些就是系统调用创建新进程的过程。该系统调用告诉操作系统创建一个新进程，并直接或间接指示在其中运行哪个程序。
在UNIX中，仅有一个系统调用来创建一个新的进程，这个系统调用就是fork。这个调用会创建一个与调用进程相关的副本。在fork后，一个父进程和子进程会有相同的内存映像，相同的环境字符串和相同的打开文件。通常，子进程会执行execve或者一个简单的系统调用来改变内存映像并运行一个新的程序。例如，当一个用户在shell中输出sort命令时，shell会fork一个子进程然后子进程去执行sort命令。这两步过程的原因是允许子进程在fork之后但在execve之前操作其文件描述符，以完成标准输入，标准输出和标准错误的重定向。
在Windows中，情况正相反，一个简单的Win32功能调用CreateProcess，会处理流程创建并将正确的程序加载到新的进程中。这个调用会有10个参数，包括了需要执行的程序、输入给程序的命令行参数、各种安全属性、有关打开的文件是否继承控制位、优先级信息、进程所需要创建的窗口规格以及指向一个结构的指针，在该结构中新创建进程的信息被返回给调用者。除了CreateProcessWin32中大概有100个其他的函数用于处理进程的管理，同步以及相关的事务。下面是UNIX操作系统和Windows操作系统系统调用的对比
在UNIX和Windows中，进程创建之后，父进程和子进程有各自不同的地址空间。如果其中某个进程在其地址空间中修改了一个词，这个修改将对另一个进程不可见。在UNIX中，子进程的地址空间是父进程的一个拷贝，但是确是两个不同的地址空间；不可写的内存区域是共享的。某些UNIX实现是正是在两者之间共享，因为它不能被修改。或者，子进程共享父进程的所有内存，但是这种情况下内存通过写时复制(copy-on-write)共享，这意味着一旦两者之一想要修改部分内存，则这块内存首先被明确的复制，以确保修改发生在私有内存区域。再次强调，可写的内存是不能被共享的。但是，对于一个新创建的进程来说，确实有可能共享创建者的资源，比如可以共享打开的文件。在Windows中，从一开始父进程的地址空间和子进程的地址空间就是不同的。
进程的终止
进程在创建之后，它就开始运行并做完成任务。然而，没有什么事儿是永不停歇的，包括进程也一样。进程早晚会发生终止，但是通常是由于以下情况触发的
1、正常退出
多数进程是由于完成了工作而终止。当编译器完成了所给定程序的编译之后，编译器会执行一个系统调用告诉操作系统它完成了工作。这个调用在UNIX中是exit，在Windows中是ExitProcess。面向屏幕中的软件也支持自愿终止操作。字处理软件、Internet浏览器和类似的程序中总有一个供用户点击的图标或菜单项，用来通知进程删除它锁打开的任何临时文件，然后终止。
2、错误退出
进程发生终止的第二个原因是发现严重错误，例如，如果用户执行如下命令
ccfoo.c
为了能够编译foo.c但是该文件不存在，于是编译器就会发出声明并退出。在给出了错误参数时，面向屏幕的交互式进程通常并不会直接退出，因为这从用户的角度来说并不合理，用户需要知道发生了什么并想要进行重试，所以这时候应用程序通常会弹出一个对话框告知用户发生了系统错误，是需要重试还是退出。
3、严重错误
进程终止的第三个原因是由进程引起的错误，通常是由于程序中的错误所导致的。例如，执行了一条非法指令，引用不存在的内存，或者除数是0等。在有些系统比如UNIX中，进程可以通知操作系统，它希望自行处理某种类型的错误，在这类错误中，进程会收到信号（中断），而不是在这类错误出现时直接终止进程。
4、被其他进程杀死
第四个终止进程的原因是，某个进程执行系统调用告诉操作系统杀死某个进程。在UNIX中，这个系统调用是kill。在Win32中对应的函数是TerminateProcess（注意不是系统调用）。
进程的层次结构
在一些系统中，当一个进程创建了其他进程后，父进程和子进程就会以某种方式进行关联。子进程它自己就会创建更多进程，从而形成一个进程层次结构。
UNIX进程体系
在UNIX中，进程和它的所有子进程以及子进程的子进程共同组成一个进程组。当用户从键盘中发出一个信号后，该信号被发送给当前与键盘相关的进程组中的所有成员（它们通常是在当前窗口创建的所有活动进程）。每个进程可以分别捕获该信号、忽略该信号或采取默认的动作，即被信号kill掉。
这里有另一个例子，可以用来说明层次的作用，考虑UNIX在启动时如何初始化自己。一个称为init的特殊进程出现在启动映像中。当init进程开始运行时，它会读取一个文件，文件会告诉它有多少个终端。然后为每个终端创建一个新进程。这些进程等待用户登录。如果登录成功，该登录进程就执行一个shell来等待接收用户输入指令，这些命令可能会启动更多的进程，以此类推。因此，整个操作系统中所有的进程都隶属于一个单个以init为根的进程树。
Windows进程体系
相反，Windows中没有进程层次的概念，Windows中所有进程都是平等的，唯一类似于层次结构的是在创建进程的时候，父进程得到一个特别的令牌（称为句柄），该句柄可以用来控制子进程。然而，这个令牌可能也会移交给别的操作系统，这样就不存在层次结构了。而在UNIX中，进程不能剥夺其子进程的进程权。（这样看来，还是Windows比较渣）。
进程状态
尽管每个进程是一个独立的实体，有其自己的程序计数器和内部状态，但是，进程之间仍然需要相互帮助。例如，一个进程的结果可以作为另一个进程的输入，在shell命令中
catchapter1chapter2chapter3|greptree
第一个进程是cat，将三个文件级联并输出。第二个进程是grep，它从输入中选择具有包含关键字tree的内容，根据这两个进程的相对速度（这取决于两个程序的相对复杂度和各自所分配到的CPU时间片），可能会发生下面这种情况，grep准备就绪开始运行，但是输入进程还没有完成，于是必须阻塞grep进程，直到输入完毕。
当一个进程开始运行时，它可能会经历下面这几种状态
图中会涉及三种状态
1、运行态，运行态指的就是进程实际占用CPU时间片运行时
2、就绪态，就绪态指的是可运行，但因为其他进程正在运行而处于就绪状态
3、阻塞态，除非某种外部事件发生，否则进程不能运行
逻辑上来说，运行态和就绪态是很相似的。这两种情况下都表示进程可运行，但是第二种情况没有获得CPU时间分片。第三种状态与前两种状态不同的原因是这个进程不能运行，CPU空闲时也不能运行。
三种状态会涉及四种状态间的切换，在操作系统发现进程不能继续执行时会发生状态1的轮转，在某些系统中进程执行系统调用，例如pause，来获取一个阻塞的状态。在其他系统中包括UNIX，当进程从管道或特殊文件（例如终端）中读取没有可用的输入时，该进程会被自动终止。
转换2和转换3都是由进程调度程序（操作系统的一部分）引起的，进程本身不知道调度程序的存在。转换2的出现说明进程调度器认定当前进程已经运行了足够长的时间，是时候让其他进程运行CPU时间片了。当所有其他进程都运行过后，这时候该是让第一个进程重新获得CPU时间片的时候了，就会发生转换3。
程序调度指的是，决定哪个进程优先被运行和运行多久，这是很重要的一点。已经设计出许多算法来尝试平衡系统整体效率与各个流程之间的竞争需求。
当进程等待的一个外部事件发生时（如从外部输入一些数据后），则发生转换4。如果此时没有其他进程在运行，则立刻触发转换3，该进程便开始运行，否则该进程会处于就绪阶段，等待CPU空闲后再轮到它运行。
从上面的观点引入了下面的模型
操作系统最底层的就是调度程序，在它上面有许多进程。所有关于中断处理、启动进程和停止进程的具体细节都隐藏在调度程序中。事实上，调度程序只是一段非常小的程序。
进程的实现
操作系统为了执行进程间的切换，会维护着一张表格，这张表就是进程表(processtable)。每个进程占用一个进程表项。该表项包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时所必须保存的信息，从而保证该进程随后能再次启动，就像从未被中断过一样。
下面展示了一个典型系统中的关键字段
第一列内容与进程管理有关，第二列内容与存储管理有关，第三列内容与文件管理有关。
一个进程在执行过程中可能被中断数千次，但关键每次中断后，被中断的进程都返回到与中断发生前完全相同的状态。
线程
在传统的操作系统中，每个进程都有一个地址空间和一个控制线程。事实上，这是大部分进程的定义。不过，在许多情况下，经常存在同一地址空间中运行多个控制线程的情形，这些线程就像是分离的进程。下面我们就着重探讨一下什么是线程
线程的使用
或许这个疑问也是你的疑问，为什么要在进程的基础上再创建一个线程的概念，准确的说，这其实是进程模型和线程模型的讨论，回答这个问题，可能需要分三步来回答
多线程之间会共享同一块地址空间和所有可用数据的能力，这是进程所不具备的
线程要比进程更轻量级，由于线程更轻，所以它比进程更容易创建，也更容易撤销。在许多系统中，创建一个线程要比创建一个进程快10-100倍。
第三个原因可能是性能方面的探讨，如果多个线程都是CPU密集型的，那么并不能获得性能上的增强，但是如果存在着大量的计算和大量的I/O处理，拥有多个线程能在这些活动中彼此重叠进行，从而会加快应用程序的执行速度
多线程解决方案
现在考虑一个线程使用的例子：一个万维网服务器，对页面的请求发送给服务器，而所请求的页面发送回客户端。在多数web站点上，某些页面较其他页面相比有更多的访问。这种页面的集合称为高速缓存(cache)，高速缓存也应用在许多场合中，比如说CPU缓存。
上面是一个web服务器的组织方式，一个叫做调度线程(dispatcherthread)的线程从网络中读入工作请求，在调度线程检查完请求后，它会选择一个空闲的（阻塞的）工作线程来处理请求，通常是将消息的指针写入到每个线程关联的特殊字中。然后调度线程会唤醒正在睡眠中的工作线程，把工作线程的状态从阻塞态变为就绪态。
当工作线程启动后，它会检查请求是否在web页面的高速缓存中存在，这个高速缓存是所有线程都可以访问的。如果高速缓存不存在这个web页面的话，它会调用一个read操作从磁盘中获取页面并且阻塞线程直到磁盘操作完成。当线程阻塞在硬盘操作的期间，为了完成更多的工作，调度线程可能挑选另一个线程运行，也可能把另一个当前就绪的工作线程投入运行。
这种模型允许将服务器编写为顺序线程的集合，在分派线程的程序中包含一个死循环，该循环用来获得工作请求并且把请求派给工作线程。每个工作线程的代码包含一个从调度线程接收的请求，并且检查web高速缓存中是否存在所需页面，如果有，直接把该页面返回给客户，接着工作线程阻塞，等待一个新请求的到达。如果没有，工作线程就从磁盘调入该页面，将该页面返回给客户机，然后工作线程阻塞，等待一个新请求。
下面是调度线程和工作线程的代码，这里假设TRUE为常数1，buf和page分别是保存工作请求和Web页面的相应结构。
调度线程的大致逻辑
while(TRUE){get_next_request(&buf);handoff_work(&buf);}工作线程的大致逻辑
while(TRUE){wait_for_work(&buf);look_for_page_in_cache(&buf,&page);if(page_not_in_cache(&page)){read_page_from_disk(&buf,&page);}return_page(&page);}单线程解决方案
现在考虑没有多线程的情况下，如何编写Web服务器。我们很容易的就想象为单个线程了，Web服务器的主循环获取请求并检查请求，并争取在下一个请求之前完成工作。在等待磁盘操作时，服务器空转，并且不处理任何到来的其他请求。结果会导致每秒中只有很少的请求被处理，所以这个例子能够说明多线程提高了程序的并行性并提高了程序的性能。
状态机解决方案
到现在为止，我们已经有了两种解决方案，单线程解决方案和多线程解决方案，其实还有一种解决方案就是状态机解决方案，它的流程如下
如果目前只有一个非阻塞版本的read系统调用可以使用，那么当请求到达服务器时，这个唯一的read调用的线程会进行检查，如果能够从高速缓存中得到响应，那么直接返回，如果不能，则启动一个非阻塞的磁盘操作
服务器在表中记录当前请求的状态，然后进入并获取下一个事件，紧接着下一个事件可能就是一个新工作的请求或是磁盘对先前操作的回答。如果是新工作的请求，那么就开始处理请求。如果是磁盘的响应，就从表中取出对应的状态信息进行处理。对于非阻塞式磁盘I/O而言，这种响应一般都是信号中断响应。
每次服务器从某个请求工作的状态切换到另一个状态时，都必须显示的保存或者重新装入相应的计算状态。这里，每个计算都有一个被保存的状态，存在一个会发生且使得相关状态发生改变的事件集合，我们把这类设计称为有限状态机(finite-statemachine)，有限状态机杯广泛的应用在计算机科学中。
这三种解决方案各有各的特性，多线程使得顺序进程的思想得以保留下来，并且实现了并行性，但是顺序进程会阻塞系统调用；单线程服务器保留了阻塞系统的简易性，但是却放弃了性能。有限状态机的处理方法运用了非阻塞调用和中断，通过并行实现了高性能，但是给编程增加了困难。
经典的线程模型
理解进程的另一个角度是，用某种方法把相关的资源集中在一起。进程有存放程序正文和数据以及其他资源的地址空间。这些资源包括打开的文件、子进程、即将发生的定时器、信号处理程序、账号信息等。把这些信息放在进程中会比较容易管理。
另一个概念是，进程中拥有一个执行的线程，通常简写为线程(thread)。线程会有程序计数器，用来记录接着要执行哪一条指令；线程还拥有寄存器，用来保存线程当前正在使用的变量；线程还会有堆栈，用来记录程序的执行路径。尽管线程必须在某个进程中执行，但是进程和线程完完全全是两个不同的概念，并且他们可以分开处理。进程用于把资源集中在一起，而线程则是CPU上调度执行的实体。
下图我们可以看到三个传统的进程，每个进程有自己的地址空间和单个控制线程。每个线程都在不同的地址空间中运行
下图中，我们可以看到有一个进程三个线程的情况。每个线程都在相同的地址空间中运行。
线程不像是进程那样具备较强的独立性。同一个进程中的所有线程都会有完全一样的地址空间，这意味着它们也共享同样的全局变量。由于每个线程都可以访问进程地址空间内每个内存地址，因此一个线程可以读取、写入甚至擦除另一个线程的堆栈。线程之间除了共享同一内存空间外，还具有如下不同的内容
上图左边的是同一个进程中每个线程共享的内容，上图右边是每个线程中的内容。也就是说左边的列表是进程的属性，右边的列表是线程的属性。
和进程一样，线程可以处于下面这几种状态：运行中、阻塞、就绪和终止（进程图中没有画）。正在运行的线程拥有CPU时间片并且状态是运行中。一个被阻塞的线程会等待某个释放它的事件。例如，当一个线程执行从键盘读入数据的系统调用时，该线程就被阻塞直到有输入为止。线程通常会被阻塞，直到它等待某个外部事件的发生或者有其他线程来释放它。线程之间的状态转换和进程之间的状态转换是一样的。
每个线程都会有自己的堆栈，如下图所示
线程系统调用
进程通常会从当前的某个单线程开始，然后这个线程通过调用一个库函数（比如thread_create）创建新的线程。线程创建的函数会要求指定新创建线程的名称。创建的线程通常都返回一个线程标识符，该标识符就是新线程的名字。
当一个线程完成工作后，可以通过调用一个函数（比如thread_exit）来退出。紧接着线程消失，状态变为终止，不能再进行调度。在某些线程的运行过程中，可以通过调用函数例如thread_join，表示一个线程可以等待另一个线程退出。这个过程阻塞调用线程直到等待特定的线程退出。在这种情况下，线程的创建和终止非常类似于进程的创建和终止。
另一个常见的线程是调用thread_yield，它允许线程自动放弃CPU从而让另一个线程运行。这样一个调用还是很重要的，因为不同于进程，线程是无法利用时钟中断强制让线程让出CPU的。
POSIX线程
为了使编写可移植线程程序成为可能，IEEE在IEEE标准1003.1c中定义了线程标准。线程包被定义为Pthreads。大部分的UNIX系统支持它。这个标准定义了60多种功能调用，一一列举不太现实，下面为你列举了一些常用的系统调用。
POSIX线程（通常称为pthreads）是一种独立于语言而存在的执行模型，以及并行执行模型。它允许程序控制时间上重叠的多个不同的工作流程。每个工作流程都称为一个线程，可以通过调用POSIXThreadsAPI来实现对这些流程的创建和控制。可以把它理解为线程的标准。
POSIXThreads的实现在许多类似且符合POSIX的操作系统上可用，例如FreeBSD、NetBSD、OpenBSD、Linux、macOS、Android、Solaris，它在现有WindowsAPI之上实现了pthread。
IEEE是世界上最大的技术专业组织，致力于为人类的利益而发展技术。
所有的Pthreads都有特定的属性，每一个都含有标识符、一组寄存器（包括程序计数器）和一组存储在结构中的属性。这个属性包括堆栈大小、调度参数以及其他线程需要的项目。
新的线程会通过pthread_create创建，新创建的线程的标识符会作为函数值返回。这个调用非常像是UNIX中的fork系统调用（除了参数之外），其中线程标识符起着PID的作用，这么做的目的是为了和其他线程进行区分。
当线程完成指派给他的工作后，会通过pthread_exit来终止。这个调用会停止线程并释放堆栈。
一般一个线程在继续运行前需要等待另一个线程完成它的工作并退出。可以通过pthread_join线程调用来等待别的特定线程的终止。而要等待线程的线程标识符作为一个参数给出。
有时会出现这种情况：一个线程逻辑上没有阻塞，但感觉上它已经运行了足够长的时间并且希望给另外一个线程机会去运行。这时候可以通过pthread_yield来完成。
下面两个线程调用是处理属性的。pthread_attr_init建立关联一个线程的属性结构并初始化成默认值，这些值（例如优先级）可以通过修改属性结构的值来改变。
最后，pthread_attr_destroy删除一个线程的结构，释放它占用的内存。它不会影响调用它的线程，这些线程会一直存在。
为了更好的理解pthread是如何工作的，考虑下面这个例子
#include<pthread.h>#include<stdio.h>#include<stdlib.h>#defineNUMBER_OF_THREADS10void*print_hello_world(vvoid*tid){/*输出线程的标识符，然后退出*/printf("HelloWorld.Greetingsfromthread%d\n",tid);pthread_exit(NULL);}intmain(intargc,char*argv[]){/*主程序创建10个线程，然后退出*/pthread_tthreads[NUMBER_OF_THREADS];intstatus,i;for(inti=0;i<NUMBER_OF_THREADS;i++){printf("Mainhere.Creatingthread%d\n",i);status=pthread_create(&threads[i],NULL,print_hello_world,(void*)i);if(status!=0){printf("Oops.pthread_createreturnederrorcode%d\n",status);exit(-1);}}exit(NULL);}主线程在宣布它的指责之后，循环NUMBER_OF_THREADS次，每次创建一个新的线程。如果线程创建失败，会打印出一条信息后退出。在创建完成所有的工作后，主程序退出。
线程实现
主要有三种实现方式
1、在用户空间中实现线程；
2、在内核空间中实现线程；
3、在用户和内核空间中混合实现线程。
下面我们分开讨论一下
在用户空间中实现线程
第一种方法是把整个线程包放在用户空间中，内核对线程一无所知，它不知道线程的存在。所有的这类实现都有同样的通用结构
线程在运行时系统之上运行，运行时系统是管理线程过程的集合，包括前面提到的四个过程：pthread_create,pthread_exit,pthread_join和pthread_yield。
运行时系统(RuntimeSystem)也叫做运行时环境，该运行时系统提供了程序在其中运行的环境。此环境可能会解决许多问题，包括应用程序内存的布局，程序如何访问变量，在过程之间传递参数的机制，与操作系统的接口等等。编译器根据特定的运行时系统进行假设以生成正确的代码。通常，运行时系统将负责设置和管理堆栈，并且会包含诸如垃圾收集，线程或语言内置的其他动态的功能。
在用户空间管理线程时，每个进程需要有其专用的线程表(threadtable)，用来跟踪该进程中的线程。这些表和内核中的进程表类似，不过它仅仅记录各个线程的属性，如每个线程的程序计数器、堆栈指针、寄存器和状态。该线程标由运行时系统统一管理。当一个线程转换到就绪状态或阻塞状态时，在该线程表中存放重新启动该线程的所有信息，与内核在进程表中存放的信息完全一样。
在用户空间实现线程的优势
在用户空间中实现线程要比在内核空间中实现线程具有这些方面的优势：考虑如果在线程完成时或者是在调用pthread_yield时，必要时会进程线程切换，然后线程的信息会被保存在运行时环境所提供的线程表中，然后，线程调度程序来选择另外一个需要运行的线程。保存线程的状态和调度程序都是本地过程，所以启动他们比进行内核调用效率更高。因而不需要切换到内核，也就不需要上下文切换，也不需要对内存高速缓存进行刷新，因为线程调度非常便捷，因此效率比较高。
在用户空间实现线程还有一个优势就是它允许每个进程有自己定制的调度算法。例如在某些应用程序中，那些具有垃圾收集线程的应用程序（知道是谁了吧）就不用担心自己线程会不会在不合适的时候停止，这是一个优势。用户线程还具有较好的可扩展性，因为内核空间中的内核线程需要一些表空间和堆栈空间，如果内核线程数量比较大，容易造成问题。
在用户空间实现线程的劣势
尽管在用户空间实现线程会具有一定的性能优势，但是劣势还是很明显的，你如何实现阻塞系统调用呢？假设在还没有任何键盘输入之前，一个线程读取键盘，让线程进行系统调用是不可能的，因为这会停止所有的线程。所以，使用线程的一个目标是能够让线程进行阻塞调用，并且要避免被阻塞的线程影响其他线程。
与阻塞调用类似的问题是缺页中断问题，实际上，计算机并不会把所有的程序都一次性的放入内存中，如果某个程序发生函数调用或者跳转指令到了一条不在内存的指令上，就会发生页面故障，而操作系统将到磁盘上取回这个丢失的指令，这就称为缺页故障。而在对所需的指令进行读入和执行时，相关的进程就会被阻塞。如果只有一个线程引起页面故障，内核由于甚至不知道有线程存在，通常会吧整个进程阻塞直到磁盘I/O完成为止，尽管其他的线程是可以运行的。
另外一个问题是，如果一个线程开始运行，该线程所在进程中的其他线程都不能运行，除非第一个线程自愿的放弃CPU，在一个单进程内部，没有时钟中断，所以不可能使用轮转调度的方式调度线程。除非其他线程能够以自己的意愿进入运行时环境，否则调度程序没有可以调度线程的机会。
在内核中实现线程
现在我们考虑使用内核来实现线程的情况，此时不再需要运行时环境了。另外，每个进程中也没有线程表。相反，在内核中会有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或撤销一个已有线程时，它会进行一个系统调用，这个系统调用通过对线程表的更新来完成线程创建或销毁工作。
内核中的线程表持有每个线程的寄存器、状态和其他信息。这些信息和用户空间中的线程信息相同，但是位置却被放在了内核中而不是用户空间中。另外，内核还维护了一张进程表用来跟踪系统状态。
混合实现
结合用户空间和内核空间的优点，设计人员采用了一种内核级线程的方式，然后将用户级线程与某些或者全部内核线程多路复用起来
在这种模型中，编程人员可以自由控制用户线程和内核线程的数量，具有很大的灵活度。采用这种方法，内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。
进程间通信
关于进程间的通信，这里有三个问题
1、上面提到了第一个问题，那就是一个进程如何传递消息给其他进程。
2、第二个问题是如何确保两个或多个线程之间不会相互干扰。例如，两个航空公司都试图为不同的顾客抢购飞机上的最后一个座位。
3、第三个问题是数据的先后顺序的问题，如果进程A产生数据并且进程B打印数据。则进程B打印数据之前需要先等A产生数据后才能够进行打印。
竞态条件
在一些操作系统中，协作的进程可能共享一些彼此都能读写的公共资源。公共资源可能在内存中也可能在一个共享文件。
假设我们的后台目录有非常多的槽位(slot)，编号依次为0，1，2，…，每个槽位存放一个文件名。同时假设有两个共享变量：out，指向下一个需要打印的文件；in，指向目录中下个空闲的槽位。可以把这两个文件保存在一个所有进程都能访问的文件中，该文件的长度为两个字。在某一时刻，0至3号槽位空，4号至6号槽位被占用。在同一时刻，进程A和进程B都决定将一个文件排队打印，情况如下
墨菲法则(Murphy)中说过，任何可能出错的地方终将出错，这句话生效时，可能发生如下情况。
进程A读到in的值为7，将7存在一个局部变量next_free_slot中。此时发生一次时钟中断，CPU认为进程A已经运行了足够长的时间，决定切换到进程B。进程B也读取in的值，发现是7，然后进程B将7写入到自己的局部变量next_free_slot中，在这一时刻两个进程都认为下一个可用槽位是7。
进程B现在继续运行，它会将打印文件名写入到slot7中，然后把in的指针更改为8，然后进程B离开去做其他的事情
现在进程A开始恢复运行，由于进程A通过检查next_free_slot也发现slot7的槽位是空的，于是将打印文件名存入slot7中，然后把in的值更新为8，由于slot7这个槽位中已经有进程B写入的值，所以进程A的打印文件名会把进程B的文件覆盖，由于打印机内部是无法发现是哪个进程更新的，它的功能比较局限，所以这时候进程B永远无法打印输出，类似这种情况，即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种就被称为竞态条件(racecondition)。调试竞态条件是一种非常困难的工作，因为绝大多数情况下程序运行良好，但在极少数的情况下会发生一些无法解释的奇怪现象。
临界区
在任何操作系统中，为了实现互斥操作而选用适当的原语是一个主要的设计问题，接下来我们会着重探讨一下。
避免竞争问题的条件可以用一种抽象的方式去描述。大部分时间，进程都会忙于内部计算和其他不会导致竞争条件的计算。然而，有时候进程会访问共享内存或文件，或者做一些能够导致竞态条件的操作。我们把对共享内存进行访问的程序片段称作临界区域(criticalregion)或临界区(criticalsection)。如果我们能够正确的操作，使两个不同进程不可能同时处于临界区，就能避免竞争条件，这也是从操作系统设计角度来进行的。
尽管上面这种设计避免了竞争条件，但是不能确保并发线程同时访问共享数据的正确性和高效性。一个好的解决方案，应该包含下面四种条件
1、任何时候两个进程不能同时处于临界区
2、不应对CPU的速度和数量做任何假设
3、位于临界区外的进程不得阻塞其他进程
4、不能使任何进程无限等待进入临界区
从抽象的角度来看，我们通常希望进程的行为如上图所示，在t1时刻，进程A进入临界区，在t2的时刻，进程B尝试进入临界区，因为此时进程A正在处于临界区中，所以进程B会阻塞直到t3时刻进程A离开临界区，此时进程B能够允许进入临界区。最后，在t4时刻，进程B离开临界区，系统恢复到没有进程的原始状态。
忙等互斥
下面我们会继续探讨实现互斥的各种设计，在这些方案中，当一个进程正忙于更新其关键区域的共享内存时，没有其他进程会进入其关键区域，也不会造成影响。
屏蔽中断
在单处理器系统上，最简单的解决方案是让每个进程在进入临界区后立即屏蔽所有中断，并在离开临界区之前重新启用它们。屏蔽中断后，时钟中断也会被屏蔽。CPU只有发生时钟中断或其他中断时才会进行进程切换。这样，在屏蔽中断后CPU不会切换到其他进程。所以，一旦某个进程屏蔽中断之后，它就可以检查和修改共享内存，而不用担心其他进程介入访问共享数据。
这个方案可行吗？进程进入临界区域是由谁决定的呢？不是用户进程吗？当进程进入临界区域后，用户进程关闭中断，如果经过一段较长时间后进程没有离开，那么中断不就一直启用不了，结果会如何？可能会造成整个系统的终止。而且如果是多处理器的话，屏蔽中断仅仅对执行disable指令的CPU有效。其他CPU仍将继续运行，并可以访问共享内存。
锁变量
作为第二种尝试，可以寻找一种软件层面解决方案。考虑有单个共享的（锁）变量，初始为值为0。当一个线程想要进入关键区域时，它首先会查看锁的值是否为0，如果锁的值是0，进程会把它设置为1并让进程进入关键区域。如果锁的状态是1，进程会等待直到锁变量的值变为0。因此，锁变量的值是0则意味着没有线程进入关键区域。如果是1则意味着有进程在关键区域内。我们对上图修改后，如下所示
这种设计方式是否正确呢？是否存在纰漏呢？假设一个进程读出锁变量的值并发现它为0，而恰好在它将其设置为1之前，另一个进程调度运行，读出锁的变量为0，并将锁的变量设置为1。然后第一个线程运行，把锁变量的值再次设置为1，此时，临界区域就会有两个进程在同时运行。
也许有的读者可以这么认为，在进入前检查一次，在要离开的关键区域再检查一次不就解决了吗？实际上这种情况也是于事无补，因为在第二次检查期间其他线程仍有可能修改锁变量的值，换句话说，这种set-before-check不是一种原子性操作，所以同样还会发生竞争条件。
严格轮询法
第三种互斥的方式先抛出来一段代码，这里的程序是用C语言编写，之所以采用C是因为操作系统普遍是用C来编写的（偶尔会用C++），而基本不会使用Java、Modula3或Pascal这样的语言，Java中的native关键字底层也是C或C++编写的源码。对于编写操作系统而言，需要使用C语言这种强大、高效、可预知和有特性的语言，而对于Java，它是不可预知的，因为它在关键时刻会用完存储器，而在不合适的时候会调用垃圾回收机制回收内存。在C语言中，这种情况不会发生，C语言中不会主动调用垃圾回收回收内存。有关C、C++、Java和其他四种语言的比较可以参考链接
进程0的代码
while(TRUE){while(turn!=0){/*进入关键区域*/critical_region();turn=1;/*离开关键区域*/noncritical_region();}}进程1的代码
while(TRUE){while(turn!=1){critical_region();turn=0;noncritical_region();}}在上面代码中，变量turn，初始值为0，用于记录轮到那个进程进入临界区，并检查或更新共享内存。开始时，进程0检查turn，发现其值为0，于是进入临界区。进程1也发现其值为0，所以在一个等待循环中不停的测试turn，看其值何时变为1。连续检查一个变量直到某个值出现为止，这种方法称为忙等待(busywaiting)。由于这种方式浪费CPU时间，所以这种方式通常应该要避免。只有在有理由认为等待时间是非常短的情况下，才能够使用忙等待。用于忙等待的锁，称为自旋锁(spinlock)。
进程0离开临界区时，它将turn的值设置为1，以便允许进程1进入其临界区。假设进程1很快便离开了临界区，则此时两个进程都处于临界区之外，turn的值又被设置为0。现在进程0很快就执行完了整个循环，它退出临界区，并将turn的值设置为1。此时，turn的值为1，两个进程都在其临界区外执行。
突然，进程0结束了非临界区的操作并返回到循环的开始。但是，这时它不能进入临界区，因为turn的当前值为1，此时进程1还忙于非临界区的操作，进程0只能继续while循环，直到进程1把turn的值改为0。这说明，在一个进程比另一个进程执行速度慢了很多的情况下，轮流进入临界区并不是一个好的方法。
这种情况违反了前面的叙述3，即位于临界区外的进程不得阻塞其他进程，进程0被一个临界区外的进程阻塞。由于违反了第三条，所以也不能作为一个好的方案。
Peterson解法
荷兰数学家T.Dekker通过将锁变量与警告变量相结合，最早提出了一个不需要严格轮换的软件互斥算法，关于Dekker的算法，参考链接
后来，G.L.Peterson发现了一种简单很多的互斥算法，它的算法如下
#defineFALSE0#defineTRUE1/*进程数量*/#defineN2/*现在轮到谁*/intturn;/*所有值初始化为0(FALSE)*/intinterested[N];/*进程是0或1*/voidenter_region(intprocess){/*另一个进程号*/intother;/*另一个进程*/other=1-process;/*表示愿意进入临界区*/interested[process]=TRUE;turn=process;/*空循环*/while(turn==process&&interested[other]==true){}}voidleave_region(intprocess){/*表示离开临界区*/interested[process]==FALSE;}在使用共享变量时（即进入其临界区）之前，各个进程使用各自的进程号0或1作为参数来调用enter_region，这个函数调用在需要时将使进程等待，直到能够安全的临界区。在完成对共享变量的操作之后，进程将调用leave_region表示操作完成，并且允许其他进程进入。
TSL指令
现在来看一种需要硬件帮助的方案。一些计算机，特别是那些设计为多处理器的计算机，都会有下面这条指令
TSLRX,LOCK
称为测试并加锁(testandsetlock)，它将一个内存字lock读到寄存器RX中，然后在该内存地址上存储一个非零值。读写指令能保证是一体的，不可分割的，一同执行的。在这个指令结束之前其他处理器均不允许访问内存。执行TSL指令的CPU将会锁住内存总线，用来禁止其他CPU在这个指令结束之前访问内存。
这条指令如何防止两个进程同时进入临界区呢？下面是解决方案
enter_region:|复制锁到寄存器并将锁设为1TSLREGISTER,LOCK|锁是0吗？CMPREGISTER,#0|若不是零，说明锁已被设置，所以循环JNEenter_region|返回调用者，进入临界区RETleave_region:|在锁中存入0MOVELOCK,#0|返回调用者RET
我们可以看到这个解决方案的思想和Peterson的思想很相似。假设存在如下共4指令的汇编语言程序。第一条指令将lock原来的值复制到寄存器中并将lock设置为1，随后这个原来的值和0做对比。如果它不是零，说明之前已经被加过锁，则程序返回到开始并再次测试。经过一段时间后（可长可短），该值变为0（当前处于临界区中的进程退出临界区时），于是过程返回，此时已加锁。要清除这个锁也比较简单，程序只需要将0存入lock即可，不需要特殊的同步指令。
还有一个可以替换TSL的指令是XCHG，它原子性的交换了两个位置的内容，例如，一个寄存器与一个内存字，代码如下
enter_region:|把1放在内存器中MOVEREGISTER,#1|交换寄存器和锁变量的内容XCHGREGISTER,LOCK|锁是0吗？CMPREGISTER,#0|若不是0，锁已被设置，进行循环JNEenter_region|返回调用者，进入临界区RETleave_region:|在锁中存入0MOVELOCK,#0|返回调用者RET
XCHG的本质上与TSL的解决办法一样。所有的Intelx86CPU在底层同步中使用XCHG指令。
睡眠与唤醒
上面解法中的Peterson、TSL和XCHG解法都是正确的，但是它们都有忙等待的缺点。这些解法的本质上都是一样的，先检查是否能够进入临界区，若不允许，则该进程将原地等待，直到允许为止。
这种方式不但浪费了CPU时间，而且还可能引起意想不到的结果。考虑一台计算机上有两个进程，这两个进程具有不同的优先级，H是属于优先级比较高的进程，L是属于优先级比较低的进程。进程调度的规则是不论何时只要H进程处于就绪态H就开始运行。在某一时刻，L处于临界区中，此时H变为就绪态，准备运行（例如，一条I/O操作结束）。现在H要开始忙等，但由于当H就绪时L就不会被调度，L从来不会有机会离开关键区域，所以H会变成死循环，有时将这种情况称为优先级反转问题(priorityinversionproblem)。
生产者-消费者问题
作为这些私有原语的例子，让我们考虑生产者-消费者(producer-consumer)问题，也称作有界缓冲区(bounded-buffer)问题。两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者(producer)，将信息放入缓冲区，另一个是消费者(consumer)，会从缓冲区中取出。也可以把这个问题一般化为m个生产者和n个消费者的问题，但是我们这里只讨论一个生产者和一个消费者的情况，这样可以简化实现方案。
如果缓冲队列已满，那么当生产者仍想要将数据写入缓冲区的时候，会出现问题。它的解决办法是让生产者睡眠，也就是阻塞生产者。等到消费者从缓冲区中取出一个或多个数据项时再唤醒它。同样的，当消费者试图从缓冲区中取数据，但是发现缓冲区为空时，消费者也会睡眠，阻塞。直到生产者向其中放入一个新的数据。
这个逻辑听起来比较简单，而且这种方式也需要一种称作监听的变量，这个变量用于监视缓冲区的数据，我们暂定为count，如果缓冲区最多存放N个数据项，生产者会每次判断count是否达到N，否则生产者向缓冲区放入一个数据项并增量count的值。消费者的逻辑也很相似：首先测试count的值是否为0，如果为0则消费者睡眠、阻塞，否则会从缓冲区取出数据并使count数量递减。每个进程也会检查检查是否其他线程是否应该被唤醒，如果应该被唤醒，那么就唤醒该线程。下面是生产者消费者的代码
/*缓冲区slot槽的数量*/#defineN100/*缓冲区数据的数量*/intcount=0//生产者voidproducer(void){intitem;/*无限循环*/while(TRUE){/*生成下一项数据*/item=produce_item()/*如果缓存区是满的，就会阻塞*/if(count==N){sleep();}/*把当前数据放在缓冲区中*/insert_item(item);/*增加缓冲区count的数量*/count=count+1;if(count==1){/*缓冲区是否为空？*/wakeup(consumer);}}}//消费者voidconsumer(void){intitem;/*无限循环*/while(TRUE){/*如果缓冲区是空的，就会进行阻塞*/if(count==0){sleep();}/*从缓冲区中取出一个数据*/item=remove_item();/*将缓冲区的count数量减一*/count=count-1/*缓冲区满嘛？*/if(count==N-1){wakeup(producer);}/*打印数据项*/consumer_item(item);}}为了在C语言中描述像是sleep和wakeup的系统调用，我们将以库函数调用的形式来表示。它们不是C标准库的一部分，但可以在实际具有这些系统调用的任何系统上使用。代码中未实现的insert_item和remove_item用来记录将数据项放入缓冲区和从缓冲区取出数据等。
用信号量解决生产者-消费者问题
用信号量解决丢失的wakeup问题，代码如下
while(TRUE){wait_for_work(&buf);look_for_page_in_cache(&buf,&page);if(page_not_in_cache(&page)){read_page_from_disk(&buf,&page);}return_page(&page);}0为了确保信号量能正确工作，最重要的是要采用一种不可分割的方式来实现它。通常是将up和down作为系统调用来实现。而且操作系统只需在执行以下操作时暂时屏蔽全部中断：检查信号量、更新、必要时使进程睡眠。由于这些操作仅需要非常少的指令，因此中断不会造成影响。如果使用多个CPU，那么信号量应该被锁进行保护。使用TSL或者XCHG指令用来确保同一时刻只有一个CPU对信号量进行操作。
使用TSL或者XCHG来防止几个CPU同时访问一个信号量，与生产者或消费者使用忙等待来等待其他腾出或填充缓冲区是完全不一样的。前者的操作仅需要几个毫秒，而生产者或消费者可能需要任意长的时间。上面这个解决方案使用了三种信号量：一个称为full，用来记录充满的缓冲槽数目；一个称为empty，记录空的缓冲槽数目；一个称为mutex，用来确保生产者和消费者不会同时进入缓冲区。Full被初始化为0，empty初始化为缓冲区中插槽数，mutex初始化为1。信号量初始化为1并且由两个或多个进程使用，以确保它们中同时只有一个可以进入关键区域的信号被称为二进制信号量(binarysemaphores)。如果每个进程都在进入关键区域之前执行down操作，而在离开关键区域之后执行up操作，则可以确保相互互斥。
斥量
互斥量是一个处于两种状态之一的共享变量：解锁(unlocked)和加锁(locked)。这样，只需要一个二进制位来表示它，不过一般情况下，通常会用一个整形(integer)来表示。0表示解锁，其他所有的值表示加锁，比1大的值表示加锁的次数。
mutex使用两个过程，当一个线程（或者进程）需要访问关键区域时，会调用mutex_lock进行加锁。如果互斥锁当前处于解锁状态（表示关键区域可用），则调用成功，并且调用线程可以自由进入关键区域。
另一方面，如果mutex互斥量已经锁定的话，调用线程会阻塞直到关键区域内的线程执行完毕并且调用了mutex_unlock。如果多个线程在mutex互斥量上阻塞，将随机选择一个线程并允许它获得锁。
由于mutex互斥量非常简单，所以只要有TSL或者是XCHG指令，就可以很容易地在用户空间实现它们。用于用户级线程包的mutex_lock和mutex_unlock代码如下，XCHG的本质也一样。
while(TRUE){wait_for_work(&buf);look_for_page_in_cache(&buf,&page);if(page_not_in_cache(&page)){read_page_from_disk(&buf,&page);}return_page(&page);}1mutex_lock的代码和上面enter_region的代码很相似，我们可以对比着看一下
上面代码最大的区别你看出来了吗？
1、根据上面我们对TSL的分析，我们知道，如果TSL判断没有进入临界区的进程会进行无限循环获取锁，而在TSL的处理中，如果mutex正在使用，那么就调度其他线程进行处理。所以上面最大的区别其实就是在判断mutex/TSL之后的处理。
在（用户）线程中，情况有所不同，因为没有时钟来停止运行时间过长的线程。结果是通过忙等待的方式来试图获得锁的线程将永远循环下去，决不会得到锁，因为这个运行的线程不会让其他线程运行从而释放锁，其他线程根本没有获得锁的机会。在后者获取锁失败时，它会调用thread_yield将CPU放弃给另外一个线程。结果就不会进行忙等待。在该线程下次运行时，它再一次对锁进行测试。
2、上面就是enter_region和mutex_lock的差别所在。由于thread_yield仅仅是一个用户空间的线程调度，所以它的运行非常快捷。这样，mutex_lock和mutex_unlock都不需要任何内核调用。通过使用这些过程，用户线程完全可以实现在用户空间中的同步，这个过程仅仅需要少量的同步。
我们上面描述的互斥量其实是一套调用框架中的指令。从软件角度来说，总是需要更多的特性和同步原语。例如，有时线程包提供一个调用mutex_trylock，这个调用尝试获取锁或者返回错误码，但是不会进行加锁操作。这就给了调用线程一个灵活性，以决定下一步做什么，是使用替代方法还是等候下去。
Futexes
随着并行的增加，有效的同步(synchronization)和锁定(locking)对于性能来说是非常重要的。如果进程等待时间很短，那么自旋锁(Spinlock)是非常有效；但是如果等待时间比较长，那么这会浪费CPU周期。如果进程很多，那么阻塞此进程，并仅当锁被释放的时候让内核解除阻塞是更有效的方式。不幸的是，这种方式也会导致另外的问题：它可以在进程竞争频繁的时候运行良好，但是在竞争不是很激烈的情况下内核切换的消耗会非常大，而且更困难的是，预测锁的竞争数量更不容易。
有一种有趣的解决方案是把两者的优点结合起来，提出一种新的思想，称为futex，或者是快速用户空间互斥(fastuserspacemutex)，是不是听起来很有意思？
futex是Linux中的特性实现了基本的锁定（很像是互斥锁）而且避免了陷入内核中，因为内核的切换的开销非常大，这样做可以大大提高性能。futex由两部分组成：内核服务和用户库。内核服务提供了了一个等待队列(waitqueue)允许多个进程在锁上排队等待。除非内核明确的对他们解除阻塞，否则它们不会运行。
对于一个进程来说，把它放到等待队列需要昂贵的系统调用，这种方式应该被避免。在没有竞争的情况下，futex可以直接在用户空间中工作。这些进程共享一个32位整数(integer)作为公共锁变量。假设锁的初始化为1，我们认为这时锁已经被释放了。线程通过执行原子性的操作减少并测试(decrementandtest)来抢占锁。decrementandset是Linux中的原子功能，由包裹在C函数中的内联汇编组成，并在头文件中进行定义。下一步，线程会检查结果来查看锁是否已经被释放。如果锁现在不是锁定状态，那么刚好我们的线程可以成功抢占该锁。然而，如果锁被其他线程持有，抢占锁的线程不得不等待。在这种情况下，futex库不会自旋，但是会使用一个系统调用来把线程放在内核中的等待队列中。这样一来，切换到内核的开销已经是合情合理的了，因为线程可以在任何时候阻塞。当线程完成了锁的工作时，它会使用原子性的增加并测试(incrementandtest)释放锁，并检查结果以查看内核等待队列上是否仍阻止任何进程。如果有的话，它会通知内核可以对等待队列中的一个或多个进程解除阻塞。如果没有锁竞争，内核则不需要参与竞争。
Pthreads中的互斥量
Pthreads提供了一些功能用来同步线程。最基本的机制是使用互斥量变量，可以锁定和解锁，用来保护每个关键区域。希望进入关键区域的线程首先要尝试获取mutex。如果mutex没有加锁，线程能够马上进入并且互斥量能够自动锁定，从而阻止其他线程进入。如果mutex已经加锁，调用线程会阻塞，直到mutex解锁。如果多个线程在相同的互斥量上等待，当互斥量解锁时，只有一个线程能够进入并且重新加锁。这些锁并不是必须的，程序员需要正确使用它们。
下面是与互斥量有关的函数调用
向我们想象中的一样，mutex能够被创建和销毁，扮演这两个角色的分别是Phread_mutex_init和Pthread_mutex_destroy。mutex也可以通过Pthread_mutex_lock来进行加锁，如果互斥量已经加锁，则会阻塞调用者。还有一个调用Pthread_mutex_trylock用来尝试对线程加锁，当mutex已经被加锁时，会返回一个错误代码而不是阻塞调用者。这个调用允许线程有效的进行忙等。最后，Pthread_mutex_unlock会对mutex解锁并且释放一个正在等待的线程。
除了互斥量以外，Pthreads还提供了第二种同步机制：条件变量(conditionvariables)。mutex可以很好的允许或阻止对关键区域的访问。条件变量允许线程由于未满足某些条件而阻塞。绝大多数情况下这两种方法是一起使用的。下面我们进一步来研究线程、互斥量、条件变量之间的关联。
下面再来重新认识一下生产者和消费者问题：一个线程将东西放在一个缓冲区内，由另一个线程将它们取出。如果生产者发现缓冲区没有空槽可以使用了，生产者线程会阻塞起来直到有一个线程可以使用。生产者使用mutex来进行原子性检查从而不受其他线程干扰。但是当发现缓冲区已经满了以后，生产者需要一种方法来阻塞自己并在以后被唤醒。这便是条件变量做的工作。
下面是一些与条件变量有关的最重要的pthread调用
上表中给出了一些调用用来创建和销毁条件变量。条件变量上的主要属性是Pthread_cond_wait和Pthread_cond_signal。前者阻塞调用线程，直到其他线程发出信号为止（使用后者调用）。阻塞的线程通常需要等待唤醒的信号以此来释放资源或者执行某些其他活动。只有这样阻塞的线程才能继续工作。条件变量允许等待与阻塞原子性的进程。Pthread_cond_broadcast用来唤醒多个阻塞的、需要等待信号唤醒的线程。
需要注意的是，条件变量（不像是信号量）不会存在于内存中。如果将一个信号量传递给一个没有线程等待的条件变量，那么这个信号就会丢失，这个需要注意
下面是一个使用互斥量和条件变量的例子
while(TRUE){wait_for_work(&buf);look_for_page_in_cache(&buf,&page);if(page_not_in_cache(&page)){read_page_from_disk(&buf,&page);}return_page(&page);}2管程
为了能够编写更加准确无误的程序，BrinchHansen和Hoare提出了一个更高级的同步原语叫做管程(monitor)。他们两个人的提案略有不同，通过下面的描述你就可以知道。管程是程序、变量和数据结构等组成的一个集合，它们组成一个特殊的模块或者包。进程可以在任何需要的时候调用管程中的程序，但是它们不能从管程外部访问数据结构和程序。下面展示了一种抽象的，类似Pascal语言展示的简洁的管程。不能用C语言进行描述，因为管程是语言概念而C语言并不支持管程。
while(TRUE){wait_for_work(&buf);look_for_page_in_cache(&buf,&page);if(page_not_in_cache(&page)){read_page_from_disk(&buf,&page);}return_page(&page);}3管程有一个很重要的特性，即在任何时候管程中只能有一个活跃的进程，这一特性使管程能够很方便的实现互斥操作。管程是编程语言的特性，所以编译器知道它们的特殊性，因此可以采用与其他过程调用不同的方法来处理对管程的调用。通常情况下，当进程调用管程中的程序时，该程序的前几条指令会检查管程中是否有其他活跃的进程。如果有的话，调用进程将被挂起，直到另一个进程离开管程才将其唤醒。如果没有活跃进程在使用管程，那么该调用进程才可以进入。
进入管程中的互斥由编译器负责，但是一种通用做法是使用互斥量(mutex)和二进制信号量(binarysemaphore)。由于编译器而不是程序员在操作，因此出错的几率会大大降低。在任何时候，编写管程的程序员都无需关心编译器是如何处理的。他只需要知道将所有的临界区转换成为管程过程即可。绝不会有两个进程同时执行临界区中的代码。
即使管程提供了一种简单的方式来实现互斥，但在我们看来，这还不够。因为我们还需要一种在进程无法执行被阻塞。在生产者-消费者问题中，很容易将针对缓冲区满和缓冲区空的测试放在管程程序中，但是生产者在发现缓冲区满的时候该如何阻塞呢？
解决的办法是引入条件变量(conditionvariables)以及相关的两个操作wait和signal。当一个管程程序发现它不能运行时（例如，生产者发现缓冲区已满），它会在某个条件变量（如full）上执行wait操作。这个操作造成调用进程阻塞，并且还将另一个以前等在管程之外的进程调入管程。在前面的pthread中我们已经探讨过条件变量的实现细节了。另一个进程，比如消费者可以通过执行signal来唤醒阻塞的调用进程。
BrinchHansen和Hoare在对进程唤醒上有所不同，Hoare建议让新唤醒的进程继续运行；而挂起另外的进程。而BrinchHansen建议让执行signal的进程必须退出管程，这里我们采用BrinchHansen的建议，因为它在概念上更简单，并且更容易实现。
如果在一个条件变量上有若干进程都在等待，则在对该条件执行signal操作后，系统调度程序只能选择其中一个进程恢复运行。
顺便提一下，这里还有上面两位教授没有提出的第三种方式，它的理论是让执行signal的进程继续运行，等待这个进程退出管程时，其他进程才能进入管程。
条件变量不是计数器。条件变量也不能像信号量那样积累信号以便以后使用。所以，如果向一个条件变量发送信号，但是该条件变量上没有等待进程，那么信号将会丢失。也就是说，wait操作必须在signal之前执行。
下面是一个使用Pascal语言通过管程实现的生产者-消费者问题的解法
while(TRUE){wait_for_work(&buf);look_for_page_in_cache(&buf,&page);if(page_not_in_cache(&page)){read_page_from_disk(&buf,&page);}return_page(&page);}4读者可能觉得wait和signal操作看起来像是前面提到的sleep和wakeup，而且后者存在严重的竞争条件。它们确实很像，但是有个关键的区别：sleep和wakeup之所以会失败是因为当一个进程想睡眠时，另一个进程试图去唤醒它。使用管程则不会发生这种情况。管程程序的自动互斥保证了这一点，如果管程过程中的生产者发现缓冲区已满，它将能够完成wait操作而不用担心调度程序可能会在wait完成之前切换到消费者。甚至，在wait执行完成并且把生产者标志为不可运行之前，是不会允许消费者进入管程的。
尽管类Pascal是一种想象的语言，但还是有一些真正的编程语言支持，比如Java（终于轮到大Java出场了），Java是能够支持管程的，它是一种面向对象的语言，支持用户级线程，还允许将方法划分为类。只要将关键字synchronized关键字加到方法中即可。Java能够保证一旦某个线程执行该方法，就不允许其他线程执行该对象中的任何synchronized方法。没有关键字synchronized，就不能保证没有交叉执行。
下面是Java使用管程解决的生产者-消费者问题
while(TRUE){wait_for_work(&buf);look_for_page_in_cache(&buf,&page);if(page_not_in_cache(&page)){read_page_from_disk(&buf,&page);}return_page(&page);}5上面的代码中主要设计四个类，外部类(outerclass)ProducerConsumer创建并启动两个线程，p和c。第二个类和第三个类Producer和Consumer分别包含生产者和消费者代码。最后，Our_monitor是管程，它有两个同步线程，用于在共享缓冲区中插入和取出数据。
在前面的所有例子中，生产者和消费者线程在功能上与它们是相同的。生产者有一个无限循环，该无限循环产生数据并将数据放入公共缓冲区中；消费者也有一个等价的无限循环，该无限循环用于从缓冲区取出数据并完成一系列工作。
程序中比较耐人寻味的就是Our_monitor了，它包含缓冲区、管理变量以及两个同步方法。当生产者在insert内活动时，它保证消费者不能在remove方法中运行，从而保证更新变量以及缓冲区的安全性，并且不用担心竞争条件。变量count记录在缓冲区中数据的数量。变量lo是缓冲区槽的序号，指出将要取出的下一个数据项。类似地，hi是缓冲区中下一个要放入的数据项序号。允许lo=hi，含义是在缓冲区中有0个或N个数据。
Java中的同步方法与其他经典管程有本质差别：Java没有内嵌的条件变量。然而，Java提供了wait和notify分别与sleep和wakeup等价。
通过临界区自动的互斥，管程比信号量更容易保证并行编程的正确性。但是管程也有缺点，我们前面说到过管程是一个编程语言的概念，编译器必须要识别管程并用某种方式对其互斥作出保证。C、Pascal以及大多数其他编程语言都没有管程，所以不能依靠编译器来遵守互斥规则。
与管程和信号量有关的另一个问题是，这些机制都是设计用来解决访问共享内存的一个或多个CPU上的互斥问题的。通过将信号量放在共享内存中并用TSL或XCHG指令来保护它们，可以避免竞争。但是如果是在分布式系统中，可能同时具有多个CPU的情况，并且每个CPU都有自己的私有内存呢，它们通过网络相连，那么这些原语将会失效。因为信号量太低级了，而管程在少数几种编程语言之外无法使用，所以还需要其他方法。
消息传递
上面提到的其他方法就是消息传递(messaagepassing)。这种进程间通信的方法使用两个原语send和receive，它们像信号量而不像管程，是系统调用而不是语言级别。示例如下
while(TRUE){wait_for_work(&buf);look_for_page_in_cache(&buf,&page);if(page_not_in_cache(&page)){read_page_from_disk(&buf,&page);}return_page(&page);}6send方法用于向一个给定的目标发送一条消息，receive从一个给定的源接受一条消息。如果没有消息，接受者可能被阻塞，直到接受一条消息或者带着错误码返回。
消息传递系统的设计要点
消息传递系统现在面临着许多信号量和管程所未涉及的问题和设计难点，尤其对那些在网络中不同机器上的通信状况。例如，消息有可能被网络丢失。为了防止消息丢失，发送方和接收方可以达成一致：一旦接受到消息后，接收方马上回送一条特殊的确认(acknowledgement)消息。如果发送方在一段时间间隔内未收到确认，则重发消息。
现在考虑消息本身被正确接收，而返回给发送着的确认消息丢失的情况。发送者将重发消息，这样接受者将收到两次相同的消息。
对于接收者来说，如何区分新的消息和一条重发的老消息是非常重要的。通常采用在每条原始消息中嵌入一个连续的序号来解决此问题。如果接受者收到一条消息，它具有与前面某一条消息一样的序号，就知道这条消息是重复的，可以忽略。
消息系统还必须处理如何命名进程的问题，以便在发送或接收调用中清晰的指明进程。身份验证(authentication)也是一个问题，比如客户端怎么知道它是在与一个真正的文件服务器通信，从发送方到接收方的信息有可能被中间人所篡改。
用消息传递解决生产者-消费者问题
现在我们考虑如何使用消息传递来解决生产者-消费者问题，而不是共享缓存。下面是一种解决方式
while(TRUE){wait_for_work(&buf);look_for_page_in_cache(&buf,&page);if(page_not_in_cache(&page)){read_page_from_disk(&buf,&page);}return_page(&page);}7假设所有的消息都有相同的大小，并且在尚未接受到发出的消息时，由操作系统自动进行缓冲。在该解决方案中共使用N条消息，这就类似于一块共享内存缓冲区的N个槽。消费者首先将N条空消息发送给生产者。当生产者向消费者传递一个数据项时，它取走一条空消息并返回一条填充了内容的消息。通过这种方式，系统中总的消息数量保持不变，所以消息都可以存放在事先确定数量的内存中。
如果生产者的速度要比消费者快，则所有的消息最终都将被填满，等待消费者，生产者将被阻塞，等待返回一条空消息。如果消费者速度快，那么情况将正相反：所有的消息均为空，等待生产者来填充，消费者将被阻塞，以等待一条填充过的消息。
消息传递的方式有许多变体，下面先介绍如何对消息进行编址。
一种方法是为每个进程分配一个唯一的地址，让消息按进程的地址编址。
另一种方式是引入一个新的数据结构，称为信箱(mailbox)，信箱是一个用来对一定的数据进行缓冲的数据结构，信箱中消息的设置方法也有多种，典型的方法是在信箱创建时确定消息的数量。在使用信箱时，在send和receive调用的地址参数就是信箱的地址，而不是进程的地址。当一个进程试图向一个满的信箱发送消息时，它将被挂起，直到信箱中有消息被取走，从而为新的消息腾出地址空间。
屏障
最后一个同步机制是准备用于进程组而不是进程间的生产者-消费者情况的。在某些应用中划分了若干阶段，并且规定，除非所有的进程都就绪准备着手下一个阶段，否则任何进程都不能进入下一个阶段，可以通过在每个阶段的结尾安装一个屏障(barrier)来实现这种行为。当一个进程到达屏障时，它会被屏障所拦截，直到所有的屏障都到达为止。屏障可用于一组进程同步，如下图所示
在上图中我们可以看到，有四个进程接近屏障，这意味着每个进程都在进行运算，但是还没有到达每个阶段的结尾。过了一段时间后，A、B、D三个进程都到达了屏障，各自的进程被挂起，但此时还不能进入下一个阶段呢，因为进程B还没有执行完毕。结果，当最后一个C到达屏障后，这个进程组才能够进入下一个阶段。
避免锁：读-复制-更新
最快的锁是根本没有锁。问题在于没有锁的情况下，我们是否允许对共享数据结构的并发读写进行访问。答案当然是不可以。假设进程A正在对一个数字数组进行排序，而进程B正在计算其平均值，而此时你进行A的移动，会导致B会多次读到重复值，而某些值根本没有遇到过。
然而，在某些情况下，我们可以允许写操作来更新数据结构，即便还有其他的进程正在使用。窍门在于确保每个读操作要么读取旧的版本，要么读取新的版本，例如下面的树
上面的树中，读操作从根部到叶子遍历整个树。加入一个新节点X后，为了实现这一操作，我们要让这个节点在树中可见之前使它"恰好正确"：我们对节点X中的所有值进行初始化，包括它的子节点指针。然后通过原子写操作，使X称为A的子节点。所有的读操作都不会读到前后不一致的版本
在上面的图中，我们接着移除B和D。首先，将A的左子节点指针指向C。所有原本在A中的读操作将会后续读到节点C，而永远不会读到B和D。也就是说，它们将只会读取到新版数据。同样，所有当前在B和D中的读操作将继续按照原始的数据结构指针并且读取旧版数据。所有操作均能正确运行，我们不需要锁住任何东西。而不需要锁住数据就能够移除B和D的主要原因就是读-复制-更新(Ready-Copy-Update,RCU)，将更新过程中的移除和再分配过程分离开。
调度
当一个计算机是多道程序设计系统时，会频繁的有很多进程或者线程来同时竞争CPU时间片。当两个或两个以上的进程/线程处于就绪状态时，就会发生这种情况。如果只有一个CPU可用，那么必须选择接下来哪个进程/线程可以运行。操作系统中有一个叫做调度程序(scheduler)的角色存在，它就是做这件事儿的，该程序使用的算法叫做调度算法(schedulingalgorithm)。
尽管有一些不同，但许多适用于进程调度的处理方法同样也适用于线程调度。当内核管理线程的时候，调度通常会以线程级别发生，很少或者根本不会考虑线程属于哪个进程。下面我们会首先专注于进程和线程的调度问题，然后会明确的介绍线程调度以及它产生的问题。
进程行为
几乎所有的进程（磁盘或网络）I/O请求和计算都是交替运行的
如上图所示，CPU不停顿的运行一段时间，然后发出一个系统调用等待I/O读写文件。完成系统调用后，CPU又开始计算，直到它需要读更多的数据或者写入更多的数据为止。当一个进程等待外部设备完成工作而被阻塞时，才是I/O活动。
上面a是CPU密集型进程；b是I/O密集型进程进程，a因为在计算的时间上花费时间更长，因此称为计算密集型(compute-bound)或者CPU密集型(CPU-bound)，b因为I/O发生频率比较快因此称为I/O密集型(I/O-bound)。计算密集型进程有较长的CPU集中使用和较小频度的I/O等待。I/O密集型进程有较短的CPU使用时间和较频繁的I/O等待。注意到上面两种进程的区分关键在于CPU的时间占用而不是I/O的时间占用。I/O密集型的原因是因为它们没有在I/O之间花费更多的计算、而不是I/O请求时间特别长。无论数据到达后需要花费多少时间，它们都需要花费相同的时间来发出读取磁盘块的硬件请求。
何时调度
第一个和调度有关的问题是何时进行调度决策。存在着需要调度处理的各种情形。首先，在创建一个新进程后，需要决定是运行父进程还是子进程。因为二者的进程都处于就绪态下，这是正常的调度决策，可以任意选择，也就是说，调度程序可以任意的选择子进程或父进程开始运行。
第二，在进程退出时需要作出调度决定。因为此进程不再运行（因为它将不再存在），因此必须从就绪进程中选择其他进程运行。如果没有进程处于就绪态，系统提供的空闲进程通常会运行
什么是空闲进程
空闲进程(system-suppliedidleprocess)是Microsoft公司windows操作系统带有的系统进程，该进程是在各个处理器上运行的单个线程，它唯一的任务是在系统没有处理其他线程时占用处理器时间。SystemIdleProcess并不是一个真正的进程，它是核心虚拟出来的，多任务操作系统都存在。在没有可用的进程时，系统处于空运行状态，此时就是SystemIdleProcess在正在运行。你可以简单的理解成，它代表的是CPU的空闲状态，数值越大代表处理器越空闲，可以通过Windows任务管理器查看Windows中的CPU利用率
第三种情况是，当进程阻塞在I/O、信号量或其他原因时，必须选择另外一个进程来运行。有时，阻塞的原因会成为选择进程运行的关键因素。例如，如果A是一个重要进程，并且它正在等待B退出关键区域，让B退出关键区域从而使A得以运行。但是调度程序一般不会对这种情况进行考量。
第四点，当I/O中断发生时，可以做出调度决策。如果中断来自I/O设备，而I/O设备已经完成了其工作，那么那些等待I/O的进程现在可以继续运行。由调度程序来决定是否准备运行新的进程还是重新运行已经中断的进程。
如果硬件时钟以50或60Hz或其他频率提供周期性中断，可以在每个时钟中断或第k个时钟中断处做出调度决策。根据如何处理时钟中断可以把调度算法可以分为两类。非抢占式(nonpreemptive)调度算法挑选一个进程，让该进程运行直到被阻塞（阻塞在I/O上或等待另一个进程），或者直到该进程自动释放CPU。即使该进程运行了若干个小时后，它也不会被强制挂起。这样会在时钟中断发生时不会进行调度。在处理完时钟中断后，如果没有更高优先级的进程等待，则被中断的进程会继续执行。
另外一种情况是抢占式调度算法，它会选择一个进程，并使其在最大固定时间内运行。如果在时间间隔结束后仍在运行，这个进程会被挂起，调度程序会选择其他进程来运行（前提是存在就绪进程）。进行抢占式调度需要在时间间隔结束时发生时钟中断，以将CPU的控制权交还给调度程序。如果没有可用的时钟，那么非抢占式就是唯一的选择。
调度算法的分类
毫无疑问，不同的环境下需要不同的调度算法。之所以出现这种情况，是因为不同的应用程序和不同的操作系统有不同的目标。也就是说，在不同的系统中，调度程序的优化也是不同的。这里有必要划分出三种环境
1、批处理(Batch)
2、交互式(Interactive)
3、实时(Re altime)
批处理系统广泛应用于商业领域，比如用来处理工资单、存货清单、账目收入、账目支出、利息计算、索赔处理和其他周期性作业。在批处理系统中，一般会选择使用非抢占式算法或者周期性比较长的抢占式算法。这种方法可以减少线程切换因此能够提升性能。
在交互式用户环境中，为了避免一个进程霸占CPU拒绝为其他进程服务，所以需要抢占式算法。即使没有进程有意要一直运行下去，但是，由于某个进程出现错误也有可能无限期的排斥其他所有进程。为了避免这种情况，抢占式也是必须的。服务器也属于此类别，因为它们通常为多个（远程）用户提供服务，而这些用户都非常着急。计算机用户总是很忙。
在实时系统中，抢占有时是不需要的，因为进程知道自己可能运行不了很长时间，通常很快的做完自己的工作并阻塞。实时系统与交互式系统的差别是，实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶意的程序。
调度算法的目标
为了设计调度算法，有必要考虑一下什么是好的调度算法。有一些目标取决于环境（批处理、交互式或者实时）蛋大部分是适用于所有情况的，下面是一些需要考量的因素，我们会在下面一起讨论。
所有系统
在所有的情况中，公平是很重要的。对一个进程给予相较于其他等价的进程更多的CPU时间片对其他进程来说是不公平的。当然，不同类型的进程可以采用不同的处理方式。
与公平有关的是系统的强制执行，什么意思呢？如果某公司的薪资发放系统计划在本月的15号，那么碰上了疫情大家生活都很拮据，此时老板说要在14号晚上发放薪资，那么调度程序必须强制使进程执行14号晚上发放薪资的策略。
另一个共同的目标是保持系统的所有部分尽可能的忙碌。如果CPU和所有的I/O设备能够一直运行，那么相对于让某些部件空转而言，每秒钟就可以完成更多的工作。例如，在批处理系统中，调度程序控制哪个作业调入内存运行。在内存中既有一些CPU密集型进程又有一些I/O密集型进程是一个比较好的想法，好于先调入和运行所有的CPU密集型作业，然后在它们完成之后再调入和运行所有I/O密集型作业的做法。使用后者这种方式会在CPU密集型进程启动后，争夺CPU，而磁盘却在空转，而当I/O密集型进程启动后，它们又要为磁盘而竞争，CPU却又在空转。。。。。。显然，通过结合I/O密集型和CPU密集型，能够使整个系统运行更流畅，效率更高。
批处理系统
通常有三个指标来衡量系统工作状态：吞吐量、周转时间和CPU利用率，吞吐量(throughout)是系统每小时完成的作业数量。综合考虑，每小时完成50个工作要比每小时完成40个工作好。周转时间(Turnaroundtime)是一种平均时间，它指的是从一个批处理提交开始直到作业完成时刻为止平均时间。该数据度量了用户要得到输出所需的平均等待时间。周转时间越小越好。
CPU利用率(CPUutilization)通常作为批处理系统上的指标。即使如此，CPU利用率也不是一个好的度量指标，真正有价值的衡量指标是系统每小时可以完成多少作业（吞吐量），以及完成作业需要多长时间（周转时间）。把CPU利用率作为度量指标，就像是引擎每小时转动了多少次来比较汽车的性能一样。而且知道CPU的利用率什么时候接近100%要比什么什么时候要求得到更多的计算能力要有用。
交互式系统
对于交互式系统，则有不同的指标。最重要的是尽量减少响应时间。这个时间说的是从执行指令开始到得到结果的时间。再有后台进程运行（例如，从网络上读取和保存E-mail文件）的个人计算机上，用户请求启动一个程序或打开一个文件应该优先于后台的工作。能够让所有的交互式请求首先运行的就是一个好的服务。
一个相关的问题是均衡性(proportionality)，用户对做一件事情需要多长时间总是有一种固定（不过通常不正确）的看法。当认为一个请求很复杂需要较多时间时，用户会认为很正常并且可以接受，但是一个很简单的程序却花费了很长的运行时间，用户就会很恼怒。可以拿彩印和复印来举出一个简单的例子，彩印可能需要1分钟的时间，但是用户觉得复杂并且愿意等待一分钟，相反，复印很简单只需要5秒钟，但是复印机花费1分钟却没有完成复印操作，用户就会很焦躁。
实时系统
实时系统则有着和交互式系统不同的考量因素，因此也就有不同的调度目标。实时系统的特点是必须满足最后的截止时间。例如，如果计算机控制着以固定速率产生数据的设备，未能按时运行的话可能会导致数据丢失。因此，实时系统中最重要的需求是满足所有（或大多数）时间期限。
在一些实事系统中，特别是涉及到多媒体的，可预测性很重要。偶尔不能满足最后的截止时间不重要，但是如果音频多媒体运行不稳定，声音质量会持续恶化。视频也会造成问题，但是耳朵要比眼睛敏感很多。为了避免这些问题，进程调度必须能够高度可预测的而且是有规律的。
批处理中的调度
现在让我们把目光从一般性的调度转换为特定的调度算法。下面我们会探讨在批处理中的调度。
先来先服务
很像是先到先得。。。可能最简单的非抢占式调度算法的设计就是先来先服务(first-come,first-serverd)。使用此算法，将按照请求顺序为进程分配CPU。最基本的，会有一个就绪进程的等待队列。当第一个任务从外部进入系统时，将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时，它们排到就绪队列尾部。当正在运行的进程阻塞，处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时，它会像一个新到达的任务，会排在队列的末尾，即排在所有进程最后。
这个算法的强大之处在于易于理解和编程，在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加一个新的作业或者阻塞一个进程，只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。
不过，先来先服务也是有缺点的，那就是没有优先级的关系，试想一下，如果有100个I/O进程正在排队，第101个是一个CPU密集型进程，那岂不是需要等100个I/O进程运行完毕才会等到一个CPU密集型进程运行，这在实际情况下根本不可能，所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。
最短作业优先
批处理中，第二种调度算法是最短作业优先(ShortestJobFirst)，我们假设运行时间已知。例如，一家保险公司，因为每天要做类似的工作，所以人们可以相当精确地预测处理1000个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短优先作业算法
如上图a所示，这里有4个作业A、B、C、D，运行时间分别为8、4、4、4分钟。若按图中的次序运行，则A的周转时间为8分钟，B为12分钟，C为16分钟，D为20分钟，平均时间内为14分钟。
现在考虑使用最短作业优先算法运行4个作业，如上图b所示，目前的周转时间分别为4、8、12、20，平均为11分钟，可以证明最短作业优先是最优的。考虑有4个作业的情况，其运行时间分别为a、b、c、d。第一个作业在时间a结束，第二个在时间a+b结束，以此类推。平均周转时间为(4a+3b+2c+d)/4。显然a对平均值的影响最大，所以a应该是最短优先作业，其次是b，然后是c，最后是d它就只能影响自己的周转时间了。
需要注意的是，在所有的进程都可以运行的情况下，最短作业优先的算法才是最优的。
最短剩余时间优先
最短作业优先的抢占式版本被称作为最短剩余时间优先(ShortestRemainingTimeNext)算法。使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。当一个新作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。这种方式能够使短期作业获得良好的服务。
交互式系统中的调度
交互式系统中在个人计算机、服务器和其他系统中都是很常用的，所以有必要来探讨一下交互式调度
轮询调度
一种最古老、最简单、最公平并且最广泛使用的算法就是轮询算法(round-robin)。每个进程都会被分配一个时间段，称为时间片(quantum)，在这个时间片内允许进程运行。如果时间片结束时进程还在运行的话，则抢占一个CPU并将其分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU立即进行切换。轮询算法比较容易实现。调度程序所做的就是维护一个可运行进程的列表，就像下图中的a，当一个进程用完时间片后就被移到队列的末尾，就像下图的b。
时间片轮询调度中唯一有意思的一点就是时间片的长度。从一个进程切换到另一个进程需要一定的时间进行管理处理，包括保存寄存器的值和内存映射、更新不同的表格和列表、清除和重新调入内存高速缓存等。这种切换称作进程间切换(processswitch)和上下文切换(contextswitch)。如果进程间的切换时间需要1ms，其中包括内存映射、清除和重新调入高速缓存等，再假设时间片设为4ms，那么CPU在做完4ms有用的工作之后，CPU将花费1ms来进行进程间的切换。因此，CPU的时间片会浪费20%的时间在管理开销上。耗费巨大。
为了提高CPU的效率，我们把时间片设置为100ms。现在时间的浪费只有1%。但是考虑会发现下面的情况，如果在一个非常短的时间内到达50个请求，并且对CPU有不同的需求，此时会发生什么？50个进程都被放在可运行进程列表中。如果CP画U是空闲的，第一个进程会立即开始执行，第二个直到100ms以后才会启动，以此类推。不幸的是最后一个进程需要等待5秒才能获得执行机会。大部分用户都会觉得对于一个简短的指令运行5秒中是很慢的。如果队列末尾的某些请求只需要几号秒钟的运行时间的话，这种设计就非常糟糕了。
另外一个因素是如果时间片设置长度要大于CPU使用长度，那么抢占就不会经常发生。相反，在时间片用完之前，大多数进程都已经阻塞了，那么就会引起进程间的切换。消除抢占可提高性能，因为进程切换仅在逻辑上必要时才发生，即流程阻塞且无法继续时才发生。
结论可以表述如下：将上下文切换时间设置得太短会导致过多的进程切换并降低CPU效率，但设置时间太长会导致一个短请求很长时间得不到响应。最好的切换时间是在20-50毫秒之间设置。
优先级调度
轮询调度假设了所有的进程是同等重要的。但事实情况可能不是这样。例如，在一所大学中的等级制度，首先是院长，然后是教授、秘书、后勤人员，最后是学生。这种将外部情况考虑在内就实现了优先级调度(priorityscheduling)
它的基本思想很明确，每个进程都被赋予一个优先级，优先级高的进程优先运行。
但是也不意味着高优先级的进程能够永远一直运行下去，调度程序会在每个时钟中断期间降低当前运行进程的优先级。如果此操作导致其优先级降低到下一个最高进程的优先级以下，则会发生进程切换。或者，可以为每个进程分配允许运行的最大时间间隔。当时间间隔用完后，下一个高优先级的进程会得到运行的机会。
可以静态或者动态的为进程分配优先级。在一台军用计算机上，可以把将军所启动的进程设为优先级100，上校为90，少校为80，上尉为70，中尉为60，以此类推。UNIX中有一条命令为nice，它允许用户为了照顾他人而自愿降低自己进程的优先级，但是一般没人用。
优先级也可以由系统动态分配，用于实现某种目的。例如，有些进程为I/O密集型，其多数时间用来等待I/O结束。当这样的进程需要CPU时，应立即分配CPU，用来启动下一个I/O请求，这样就可以在另一个进程进行计算的同时执行I/O操作。这类I/O密集型进程长时间的等待CPU只会造成它长时间占用内存。使I/O密集型进程获得较好的服务的一种简单算法是，将其优先级设为1/f，f为该进程在上一时间片中所占的部分。一个在50ms的时间片中只使用1ms的进程将获得优先级50，而在阻塞之前用掉25ms的进程将具有优先级2，而使用掉全部时间片的进程将得到优先级1。
可以很方便的将一组进程按优先级分成若干类，并且在各个类之间采用优先级调度，而在各类进程的内部采用轮转调度。下面展示了一个四个优先级类的系统
它的调度算法主要描述如下：上面存在优先级为4类的可运行进程，首先会按照轮转法为每个进程运行一个时间片，此时不理会较低优先级的进程。若第4类进程为空，则按照轮询的方式运行第三类进程。若第4类和第3类进程都为空，则按照轮转法运行第2类进程。如果不对优先级进行调整，则低优先级的进程很容易产生饥饿现象。
多级队列
最早使用优先级调度的系统是CTSS(CompatibleTimeSharingSystem)。CTSS是一种兼容分时系统，它有一个问题就是进程切换太慢，其原因是IBM7094内存只能放进一个进程。
CTSS在每次切换前都需要将当前进程换出到磁盘，并从磁盘上读入一个新进程。CTSS的设计者很快就认识到，为CPU密集型进程设置较长的时间片比频繁地分给他们很短的时间要更有效（减少交换次数）。另一方面，如前所述，长时间片的进程又会影响到响应时间，解决办法是设置优先级类。属于最高优先级的进程运行一个时间片，次高优先级进程运行2个时间片，再下面一级运行4个时间片，以此类推。当一个进程用完分配的时间片后，它被移到下一类。
最短进程优先
对于批处理系统而言，由于最短作业优先常常伴随着最短响应时间，所以如果能够把它用于交互式进程，那将是非常好的。在某种程度上，的确可以做到这一点。交互式进程通常遵循下列模式：等待命令、执行命令、等待命令、执行命令。。。如果我们把每个命令的执行都看作一个分离的作业，那么我们可以通过首先运行最短的作业来使响应时间最短。这里唯一的问题是如何从当前可运行进程中找出最短的那一个进程。
一种方式是根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。假设每个终端上每条命令的预估运行时间为T0，现在假设测量到其下一次运行时间为T1，可以用两个值的加权来改进估计时间，即aT0+(1-1)T1。通过选择a的值，可以决定是尽快忘掉老的运行时间，还是在一段长时间内始终记住它们。当a=1/2时，可以得到下面这个序列
可以看到，在三轮过后，T0在新的估计值中所占比重下降至1/8。
保证调度
一种完全不同的调度方法是对用户做出明确的性能保证。一种实际而且容易实现的保证是：若用户工作时有n个用户登录，则每个用户将获得CPU处理能力的1/n。类似地，在一个有n个进程运行的单用户系统中，若所有的进程都等价，则每个进程将获得1/n的CPU时间。
公平分享调度
到目前为止，我们假设被调度的都是各个进程自身，而不用考虑该进程的拥有者是谁。结果是，如果用户1启动了9个进程，而用户2启动了一个进程，使用轮转或相同优先级调度算法，那么用户1将得到90%的CPU时间，而用户2将之得到10%的CPU时间。
为了阻止这种情况的出现，一些系统在调度前会把进程的拥有者考虑在内。在这种模型下，每个用户都会分配一些CPU时间，而调度程序会选择进程并强制执行。因此如果两个用户每个都会有50%的CPU时间片保证，那么无论一个用户有多少个进程，都将获得相同的CPU份额。
实时系统中的调度
实时系统可以分为两类，硬实时(hardre altime)和软实时(softre altime)系统，前者意味着必须要满足绝对的截止时间；后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。在这两种情形中，实时都是通过把程序划分为一组进程而实现的，其中每个进程的行为是可预测和提前可知的。这些进程一般寿命较短，并且极快的运行完成。在检测到一个外部信号时，调度程序的任务就是按照满足所有截止时间的要求调度进程。
实时系统中的事件可以按照响应方式进一步分类为周期性(以规则的时间间隔发生)事件或非周期性(发生时间不可预知)事件。一个系统可能要响应多个周期性事件流，根据每个事件处理所需的时间，可能甚至无法处理所有事件。例如，如果有m个周期事件，事件i以周期Pi发生，并需要Ci秒CPU时间处理一个事件，那么可以处理负载的条件是
只有满足这个条件的实时系统称为可调度的，这意味着它实际上能够被实现。一个不满足此检验标准的进程不能被调度，因为这些进程共同需要的CPU时间总和大于CPU能提供的时间。
调度策略和机制
到目前为止，我们隐含的假设系统中所有进程属于不同的分组用户并且进程间存在相互竞争CPU的情况。通常情况下确实如此，但有时也会发生一个进程会有很多子进程并在其控制下运行的情况。例如，一个数据库管理系统进程会有很多子进程。每一个子进程可能处理不同的请求，或者每个子进程实现不同的功能（如请求分析、磁盘访问等）。主进程完全可能掌握哪一个子进程最重要（或最紧迫），而哪一个最不重要。但是，以上讨论的调度算法中没有一个算法从用户进程接收有关的调度决策信息，这就导致了调度程序很少能够做出最优的选择。
解决问题的办法是将调度机制(schedulingmechanism)和调度策略(schedulingpolicy)分开，这是长期一贯的原则。这也就意味着调度算法在某种方式下被参数化了，但是参数可以被用户进程填写。让我们首先考虑数据库的例子。假设内核使用优先级调度算法，并提供了一条可供进程设置优先级的系统调用。这样，尽管父进程本身并不参与调度，但它可以控制如何调度子进程的细节。调度机制位于内核，而调度策略由用户进程决定，调度策略和机制分离是一种关键性思路。
线程调度
当若干进程都有多个线程时，就存在两个层次的并行：进程和线程。在这样的系统中调度处理有本质的差别，这取决于所支持的是用户级线程还是内核级线程（或两者都支持）。
首先考虑用户级线程，由于内核并不知道有线程存在，所以内核还是和以前一样地操作，选取一个进程，假设为A，并给予A以时间片控制。A中的线程调度程序决定哪个线程运行。假设为A1。由于多道线程并不存在时钟中断，所以这个线程可以按其意愿任意运行多长时间。如果该线程用完了进程的全部时间片，内核就会选择另一个进程继续运行。
在进程A终于又一次运行时，线程A1会接着运行。该线程会继续耗费A进程的所有时间，直到它完成工作。不过，线程运行不会影响到其他进程。其他进程会得到调度程序所分配的合适份额，不会考虑进程A内部发生的事情。
现在考虑A线程每次CPU计算的工作比较少的情况，例如：在50ms的时间片中有5ms的计算工作。于是，每个线程运行一会儿，然后把CPU交回给线程调度程序。这样在内核切换到进程B之前，就会有序列A1,A2,A3,A1,A2,A3,A1,A2,A3,A1。如下所示
运行时系统使用的调度算法可以是上面介绍算法的任意一种。从实用方面考虑，轮转调度和优先级调度更为常用。唯一的局限是，缺乏一个时钟中断运行过长的线程。但由于线程之间的合作关系，这通常也不是问题。
现在考虑使用内核线程的情况，内核选择一个特定的线程运行。它不用考虑线程属于哪个进程，不过如果有必要的话，也可以这么做。对被选择的线程赋予一个时间片，而且如果超过了时间片，就会强制挂起该线程。一个线程在50ms的时间片内，5ms之后被阻塞，在30ms的时间片中，线程的顺序会是A1,B1,A2,B2,A3,B3。如下图所示
用户级线程和内核级线程之间的主要差别在于性能。用户级线程的切换需要少量的机器指令（想象一下Java程序的线程切换），而内核线程需要完整的上下文切换，修改内存映像，使高速缓存失效，这会导致了若干数量级的延迟。另一方面，在使用内核级线程时，一旦线程阻塞在I/O上就不需要在用户级线程中那样将整个进程挂起。
从进程A的一个线程切换到进程B的一个线程，其消耗要远高于运行进程A的两个线程（涉及修改内存映像，修改高速缓存），内核对这种切换的消耗是了解到，可以通过这些信息作出决定。