进程的概念
前趋图(Precedence Graph)
前趋图是一个有向无循环图（Directed Acyclic Graph, DAG），用于描述进程之间执行的前后关系。Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。
程序并发执行的特征
1） 间断性：程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。
2） 失去封闭性：程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。
3） 不可再现性：程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。
进程的三种基本状态：就绪、执行、阻塞
1）就绪(Ready)状态
当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。
2）执行状态
进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；
在多处理机系统中，则有多个进程处于执行状态。
3）阻塞状态
正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，也叫等待状态或封锁状态。致使进程阻塞的典型事件有：请求I/O，申请缓冲空间等（缺少资源，如进程请求访问某临界资源，而该资源正被其他资源访问时）。通常将这种处于阻塞状态的进程也排成一个队列。
注意：
只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。
挂起状态
上面三种是系统的基本状态，一些系统引起了挂起状态。
1） 引入挂起状态的原因
（1）终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时使自己的程序静止下来。
（2）父进程请求。有时父进程希望挂起自己的某个子进程，以便考查和修改该子进程，或者协调各子进程间的活动。
（3）负荷调节的需要。当实时系统中的工作负荷较重，已可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。
（4）操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。
2） 进程状态的转换
引入挂起状态后，又将增加从挂起状态（静止状态）到非挂起状态（活动状态）的转换。
创建状态和终止状态
为了管理的需要，又增加了创建状态和终止状态。
1） 创建状态一般两个步骤：一是为新进程创建一个PCB，并填写必要的管理信息；二是把该进程转入就绪状态并插入到就绪队列之中。
2） 终止状态一般也有两个状态：一是等待操作系统进行善后处理，然后将其PCB清零，并将PCB空间返还系统。
进程控制块
1） 进程控制块 (Process Control Block, PCB) 的作用
PCB是进程实体的一部分，是操作系统中重要的记录型数据结构，它描述了进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。当系统创建一个新进程时，就为它建立了一个PCB；进程结束时又回收其PCB，进程于是也随之消亡。OS是根据PCB来对并发执行的进程进行控制和管理的。
由于PCB经常被系统访问，因此PCB应常驻内存。系统将所有的PCB组织成若干个链表(或队列)，存放在操作系统中专门开辟的PCB 区内。例如在Linux 系统中用task_struct数据结构来描述每个进程的PCB；在Windows操作系统中则使用一个执行体进程块(EPROCESS)来表示进程对象的基本属性。
2） 进程控制块中的信息
（1）进程标识符
内部标识：操作系统为每个进程赋予的唯一一个数字标识，通常是进行序号。
外部标识：由用户（进程）在访问该进程时使用的标识。
（2）处理机状态
处理机状态信息由处理机的各种寄存器中的内容组成的。处理机在运行时，许多信息都放在寄存器中。当处理机被中断时，所有这些信息都必须保存在PCB中，以便在该进程重新执行时，能从断点继续执行。
（3）进程调度信息
包括进程状态、进程优先级、进程调度算法、事件（即阻塞原因）。
（4）进程控制信息
程序和数据的地址、进程同步和通信机制（如消息队列、信号量等）、资源清单、链接指针（本进程（PCB）所在队列的下一个进程的PCB首地址）。
3） PCB的组织方式
（1）链接方式
把具有相同状态的PCB用链接字连接成一个队列。
（2）索引方式
根据PCB的状态建立几张索引表。
进程控制
原语（primitive）：原语是由若干指令组成的，用于完成一定功能的一个过程。原语与一般过程的区别在于，原语是原子操作（atomic operation），一个原子操作中的操作要么全做，要么全不做，即它是一个不可分割的基本的单位。它在执行过程中不能被中断，原子操作在管态下执行，常驻内存。
原语的作用：进程的控制和通信。
进程的创建
1） 进程图（process graph）
子进程可以继承父进程所拥有的资源，例如，继承父进程打开的文件，继承父进程所分配到的缓冲区等。当子进程被撤消时，应将其从父进程那里获得的资源归还给父进程。此外，在撤消父进程时，也必须同时撤消其所有的子进程。、
2） 引起创建进程的事件
（1）用户登录
（2）作业调度
（3）提供服务
（4）应用进程
3） 进程的创建过程
一旦操作系统发现了要求创建新进程的事件后，便调用进程创建原语Creat( )按下述步骤创建一个新进程。
（1）申请空白PCB
（2）为新进程分配资源
（3）初始化PCB将
（4）新进程插入就绪队列
进程的终止
1） 引起进程终止的事件
（1）正常结束。如在批处理系统中，通常在程序最后加一条Holt指令终止系统的调用
（2）异常结束
如越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障。
（3）外界干预
操作员或操作系统干扰、父进程请求、父进程终止。
2） 进程的终止过程
如果系统中发生了上述要求终止进程的某事件，OS便调用进程终止原语，按下述过程去终止指定的进程。
（1）根据被终止进程的标识符，从PCB 集合中检索出该进程的PCB，从中读出该进程
的状态。
（2）若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用
于指示该进程被终止后应重新进行调度。
（3）若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防它们成为不可控的
进程。
（4）将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。
（5）将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。
进程的阻塞与唤醒
1） 引起进程阻塞和唤醒的事件
（1）当正在执行的进程请求操作系统提供服务时，由于某种原因，操作系统并不立即满足该进程的要求时。
（2）当进程启动某种操作后，如果该进程必须在该操作完成之后才能继续执行。
（3）对于相互合作的进程，如果其中一个进程需要先获得另一(合作)进程提供的数据后才能对数据进行处理，则只要其所需数据尚未到达，该进程只有(等待)阻塞。
（4）系统往往设置一些具有某特定功能的系统进程，每当这种进程完成任务后，便把自己阻塞起来以等待新任务到来。
2） 进程的阻塞过程
正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block()把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。
3） 进程的唤醒过程
调用唤醒原语wakeup()，将等待该事件的进程唤。唤醒过程：把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。
block()和wakeup()是一对相反的原语。
进程的挂起与激活
1） 进程的挂起
当出现了引起进程挂起的事件时，比如用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。
2） 进程的激活
当发生激活进程的事件时，比如父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的该进程换入内存。这时，系统将利用激活原语active()将指定进程激活。
进程同步
进程同步的概念
1） 临界资源与临界区
许多硬件资源如打印机、磁带机等，都属于临界资源(Critical Resouce)，进程间应采取互斥方式实现对这种资源的共享。
每个进程中访问临界资源（critical resource）的那段代码称为临界区（critical section）。若能保证各个进程互斥地进入临界区，便可实现各个进程对临界资源的互斥访问。
在临界区前增加一段用于进行互斥检查的代码，这段代码称为进入区（entry section）。相应地，在临界区后面也要增加一段称为退出区（exit section）的代码，用于将临界区正被访问的标识恢复为未被访问的标识。
经典的进程同步问题：生产者-消费者（producer-consumer）问题；哲学家进餐问题。
2） 同步机制应遵循的规则
空闲让进、忙则等待、有限等待（有限时间内进入临界区）、让权等待（对不能进入临界区的进程，应立即释放处理机）。
信号量机制
Dijkstra提出的信号量(Semaphores)机制是一种卓有成效的进程同步工具。
1） 整型信号量
最初Dijkstra把整型信号量定义为表示资源数目的整型量S，它仅能通过两个原子操作wait(S)和signal(S)来访问，通常将这两个操作称为P、V操作。
- wait(S)：即P操作，进程请求一个单位的资源，使系统中可供分配的资源少一个。
- signal(S)：即V操作，执行进程释放一个单位的资源，使系统中可供分配的资源增加一个。
P、V操作可描述为：
1 | wait(S) : while S <= 0 do noop; |
2） 记录型信号量
由于整型信号量没有遵循“让权等待”的准则，只要S<=0就会不断测试，让进程处于“忙等”状态。而记录型信号量除了有一个记录资源数目的整型变量value外，还增加了一个进程链表指针L，用于链接上述的所有进程。
3） AND型信号量
若一个进程需要获得多个共享资源后才能执行任务，可以将临界资源（共享的数据）设置为多个互斥的信号量，并令他们的初值为1。
对若干个临界资源的分配（wait操作），采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。避免多个进程处于死锁状态（每个进程都请求不到资源，都陷入阻塞状态）。为此，在wait 操作中，增加了一个“AND”条件，故称为AND 同步，或称为同时wait（Swait，Simultaneous wait）。
4） 信号量集
在有些情况下，当资源数量低于某一下限值时，便不予以分配。因而，在每次分配之前，都必须测试该资源的数量，看其是否大于其下限值t。基于上述两点，可以对AND 信号量机制加以扩充，形成一般化的“信号量集”机制。Swait操作可描述如下，其中S为信号量，d为需求值，而t为下限值。
5） 信号量的作用
（1）实现进程互斥
（2）实现前趋关系
设有两个并发执行的进程P1和P2。P1中有语句S1；P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系，我们只须使进程P1和P2共享一个公用信号量S，并赋予其初值为0，将signal(S)操作放在语句S1后面；而在S2语句前面插入wait(S)操作，即
在进程 P1中，用S1；signal(S)；
在进程 P2中，用wait(S)；S2；
由于S被初始化为0，这样，若P2先执行必定阻塞，只有在进程P1执行完S1；signal(S)；操作后使S增为1时，P2 进程方能执行语句S2 成功。
对前趋图，一层一层地进行P、V操作。
管程机制
由于信号量机制造成大量同步操作wait(S)和signal(S)分散在进程中，给管理带来了麻烦，同时操作不当也容易造成死锁。为了解决这个问题，提出了新的进程同步工具——管程（monitors）。
1） 管程的定义
一个管程定义了一个数据结构，和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据。管程相当于围墙，它把共享变量和对它进行操作的若干过程围了起来，所有进程要访问临界资源时，都必须经过管程(相当于通过围墙的门)才能进入，而管程每次只准许一个进程进入管程，从而实现了进程互斥。
2） 条件变量
为了防止当前进程不释放管程，而使其它进程被迫长时间等待，引入了条件变量。条件变量中是进程被阻塞或挂起的原因。管程中对每个条件变量都须予以说明，其形式为：Var x，y：condition。对条件变量的操作仅仅是wait和signal。
进程通信
进程通信是指进程间的信息交换。进程之间的互斥和同步，由于其所交换的信息量少而被归结为低级通信。在进程互斥中，进程通过只修改信号量来向其他进程表明临界资源是否可用。
信号量机制作为同步工具是有效的，但作为通信工具则不理想，其效率低，通信对用户不透明。
本节所要介绍的是高级进程通信，是指用户可直接利用操作系统所提供的一组通信命令高效地传送大量数据的一种通信方式。操作系统隐藏了进程通信的实现细节。或者说，通信过程对用户是透明的。这样就大大减少了通信程序编制上的复杂性。
进程通信的类型
目前，高级通信机制可归结为三大类：共享存储器系统、消息传递系统以及管道通信系统。
1） 共享存储器系统（shared-memory system）
相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。
2） 消息传递系统
消息传递系统(Message passing system)是当前应用最为广泛的一种进程间的通信机制。在该机制中，进程间的数据交换是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。
3） 管道通信系统
所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)，以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。
消息缓冲队列机制
发送进程利用Send原语将消息直接发送给接收进程；接收进程则利用Receive原语接收消息。
线程
如果说，在操作系统中引入进程的目的，是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量，那么在操作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。
由于进程是一个资源的拥有者，因而在创建、撤消和切换进程过程中，系统必须为之付出较大的时空开销。正因如此，在系统中所设置的进程，其数目不宜过多，进程切换的频率也不宜过高，这也就限制了并发程度的进一步提高。
进程与线程的比较
1） 调度
进程是资源拥有的基本单位，而线程是调度和分派的基本单位，在多线程OS中，线程是能独立运行的基本单位，切换速度快，开销小。
2） 并发性
不仅进程之间可以并发执行，同一进程和不同进程的线程间也可以并发执行。
3） 拥有资源
一般而言，线程不自己拥有资源，但它可以访问它所属进程的资源。同一进程的多个线程可以共享该进程的所有资源，这表现在同一进程的多个线程拥有相同的地址空间，因此在同步和通信方面，线程比进程容易。
4） 系统开销
进程的创建、撤消和切换，所付出的开销大于线程。
线程间的同步和通信
为了支持不同频率的交互操作和不同程度的并行性，在多线程OS中通常提供多种同步机制，如互斥锁、条件变量、计数信号量以及多读、单写锁等。
1）互斥锁（mutex）
互斥锁是一种比较简单的、用于实现线程间对资源互斥访问的机制。由于操作互斥锁
的时间和空间开销都较低，因而较适合于高频度使用的关键共享数据和程序段。互斥锁可
以有两种状态，即开锁(unlock)和关锁(lock)状态。
当一个线程需要读/写一个共享数据段时，关锁命令首先判别mutex 的状态，如果它已处于关锁状态，则试图访问该数据段的线程将被阻塞；而如果mutex 是处于开锁状态，则将mutex 关上后便去读/写该数据段，而进入临界区不一定表示该资源区就能够被访问，也可能该资源正被其它资源使用。在线程完成对数据的读/写后，必须再发出开锁命令将mutex 打开，同时还须将阻塞在该互斥锁上的一个线程唤醒，其它的线程仍被阻塞在等待mutex打开的队列上。
2） 条件变量
在许多情况下，只利用mutex来实现互斥访问可能会引起死锁。
在创建一个互斥锁时联系着一个条件变量。单纯的互斥锁用于短期锁定，主要是用来保证对临界区的互斥进入。而条件变量则用于线程的长期等待，直至所等待的资源成为可用的资源。
3） 信号量机制
前面所说的用于实现进程同步的信号量机制，也可用于多线程OS中。
私用信号量(private samephore)当某线程需利用信号量来实现同一进程中各线程之间的同步，OS并不知道私用信号量的存在；公用信号量是为实现不同进程间或不同进程中各线程之间的同步而设置的。
线程的的实现
1） 内核支持线程
无论是系统进程还是用户进程，进程的创建、撤消，以及要求由系统设备完成的I/O 操作，都是利用系统调用而进入内核，再由内核中的相应处理程序予以完成的。进程的切换同样是在内核的支持下实现的。
2） 用户级线程
用户级线程ULT(User Level Threads)仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。
不论是进程还是线程，都必须直接或间接地取得内核的支持。由于内核支持线程可以直接利用系统调用为它服务，故线程的控制相当简单；而用户级线程必须借助于某种形式的中间系统的帮助方能取得内核的服务，故在对线程的控制上要稍复杂些。