进程

进程概念

导言

• 批处理系统执行作业，而分时系统使用用户程序或任务
• 即使是单用户系统，用户也能同时运行多个程序；即使用户一次只能执行一个程序，操作系统也需要支持本身的内部活动

进程

• 进程是执行的程序，这是一种非正式的说法
• 进程不只是程序代码，程序代码有时称为文本段或代码段，进程还包括当前活动，如程序计数器的值和处理器寄存器的内容等。
• 另外，进程还包括：进程堆栈（包括临时数据，如函数参数，返回地址和局部变量）和数据段（包括全局变量）。
• 进程还可能包括堆，这是在进程运行时动态分配的内存。
• 我们强调：程序本身不是进程，程序只是被动实体，如存储在磁盘上包含一系列指令的文件（经常称为可执行文件），相反，进程是活动实体，具有一个程序计数器用于表示下个执行指令和一组相关资源，当一个可执行文件被加载到内存时，这个程序就成为了进程。
• 进程内存图：

进程状态

• 进程在执行时会改变状态，进程状态，部分取决于进程的当前活动，状态有如下：

• 1. 新的：进程正在创建
  2. 运行：指令正在执行
  3. 等待：进程等待发生某个事件（如I/O完成或收到信号）
  4. 就绪：进程等待分配处理器
  5. 终止：进程已经完成执行

• 重要的是认识到：一次只能有一个进程可在处理器上运行，但是许多进程可处在就绪或等待状态。

• 示意图：非常重要-状态之间跳转的条件

进程控制块

• 操作系统内的每个进程表示，采用进程控制块，也称为任务控制块。

• 进程的相关信息：

• 1. 进程状态：状态可以包含新的、就绪、运行、等待、停止等；
  2. 程序计数器：计数器表示进程将要执行的下个指令的地址；
• 1. CPU寄存器：根据计算机体系结构的不同，寄存器的类型和数量也会不同，她们包括累加器、索引寄存器、堆栈指针、通用寄存器和其他条件码信息寄存器，在发生中断时，这些状态信息与程序计数器一起需要保存，以便进程以后能正确的继续执行；
  2. CPU调度信息：这类信息包括进程优先级、调度队列的指针和其他调度参数；
• 1. 内存管理信息：根据操作系统使用的内存系统，这类信息可以包括基地址和界限寄存器的值、页表或段表；
  2. 记账信息：这类信息包括CPU时间、实际使用时间、时间期限、记账数据、作业或进程数量等；
• 1. I/O状态信息：这类信息包括分配给进程的I/O设备列表、打开文件列表等。

• 简而言之，PCB简单地作为这些信息的仓库，这些信息随着进程的不同而不同。

线程

• 每个进程是一个只能进行单个执行线程的程序，这种单一控制线程使得进程一次只能执行一个任务。

进程调度

导言

• 多道程序设计的目标是，无论何时都有进程运行，从而最大化CPU利用率，分时系统的目的是在进程之间快速切换CPU，以便用户在程序运行时能与其交互，为了满足这些目标，进程调度器选择一个可用进程（可能从多个可用进程集合中）到CPU上执行。

调度队列

• 进程在进入系统时，会被加入到作业队列中，这个队列包括系统内的所有进程。
• 驻留在内存中的、就绪的、等待运行的进程保存在就绪队列中，等待CPU调度，这个队列通常用链表实现，其头节点有两个指针，用于指向链表的第一个和最后一个PCB块，每个PCB还包括一个指针，指向就绪队列的下一个PCB。
• 系统还有其他队列，当一个进程被分配了CPU后，他执行一段时间，最终退出，或者被中断，或者等待特定事件发生如I/O请求的完成。等待特定I/O设备的进程列表，称为设备列表，每个设备都有自己的设备队列。

• 进程调度通常用队列图来表示，每个矩形框代表一个队列（就绪队列，设备队列），圆圈代表服务队列的资源，箭头表示系统列的进程流向。例如：

• 最初，新进程被加到就绪队列中，等待，知道被选中执行或被分配，当该进程分配到CPU执行时，以下事件可能发生：

• 1. 进程可能发出I/O请求，并被放到I/O队列
  2. 进程可能创建一个新的子进程，并等待其终止
  3. 进程可能由于中断而被强制释放CPU，并被放回到就绪队列

• 对于前两种情况，进程最终从等待状态切换到就绪状态，并放回到就绪队列，进程重复这一循环直到终止，然后它会从所有队列中删除，释放他的CPU和资源。

调度程序

• 进程在整个生命周期中，会在各种调度队列之间迁移。操作系统为了调度必须按一定方式从这些队列中选择进程。进程选择通过适当调度器或调度程序来执行。
• 通常，对于批处理系统，提交的进程多于可以立即执行的。这些进程会被保存到大容量存储设备（通常为磁盘）得缓冲池，以便以后执行。长期调度程序或作业调度程序从该池中选择进程加到内存以便执行。短期调度程序或CPU调度程序从准备执行的进程中选择进程，并分配CPU。
• 这两种调度程序的主要区别就是执行频率。短期调度程序必须经常为CPU选择新的进程。进程可能执行几毫秒，就会等待I/O请求。通常，短期调度程序每100ms至少执行一次，由于执行的时间短，短期调度程序必须快速。如果花费10ms来确定执行一个运行100ms的进程，那么10/(100+10)=9%的CPU时间就会浪费在调度工作上。
• 长期调度程序执行并不频繁，在新进程的创建之间，可能有几分钟间隔。长期调度程序控制多道程序程度，也就是内存中的进程数量。如果多道程序程度稳定那么创建进程的平均速度必须等于进程离开系统的平均速度。因此，只有在进程离开系统时，才需要长期调度程序的调度。由于每次执行之间的更长时间间隔长期调度程序可以负担起更多时间，以便决定应该选择执行哪个进程。
• 重要的是，长期调度程序必须认真选择，I/O密集型进程，执行I/O比执行计算需要花费更多时间，相反，CPU密集型进程很少产生I/O请求，而是将更多的时间用于执行计算。因此为了使得性能最佳，系统的长期调度程序应该选择I/O密集型和CPU密集型的合理进程组合。如果所有进程都是I/O密集型的，那么就绪队列几乎总是空的，从而短期调度程序没有什么进程可做，如果所有的进程都是CPU密集型的，那么I/O等待队列几乎总是为空，从而设备没有得到使用，系统会不平衡。
• 有的操作系统如分时系统，可能引入一个额外的中期调度程序。中期调度程序的核心思想是可将进程从内存中（或从CPU竞争）移出，从而降低多道程序程度。之后，进程可被重新调入内存，并从中断处继续执行。这种方案称为交换。通过中期调度程序，进程可换出，并在后来可换入。为了改善进程组合，或者由于内存需求改变导致过度使用内存从而需要释放内存，就有必要使用交换。
• 添加中级进程调度到队列图

上下文切换

• 中断导致CPU从执行当前任务改变到执行内核程序，这种操作在通用系统中经常发生。当中断发生时，系统需要保存当前运行在CPU上的进程的上下文，以便在处理后能够恢复上下文，即先挂起进程，再恢复进程。进程上下文采用进程PCB表示，包括CPU寄存器的值、进程状态和内存管理信息等。通常，通过执行状态保存，保存CPU当前状态（包括内核模式和用户模式），之后，状态恢复重新开始运行。
• 切换CPU到另一个进程需要保存当前进程状态恢复另一个进程的状态，这个任务称为上下文切换。当进行上下文切换时内核会将旧进程状态保存在其PCB中，然后加载经调度而要执行的新进程的上下文。上下文切换的时间是纯粹的开销，因为在切换时系统并没有做任何有用工作。上下文切换的速度因机器的不同而不同，依赖于内存速度，需要复制的寄存器数目，以及是否有特殊指令相关，典型速度为几毫秒。
• 上下文切换的时间与硬件密切相关。操作系统越复杂，上下文切换要做的就越多。

进程运行

导言

• 大多数系统的进程能够并发执行，他们可以动态的创建和删除，因此，操作系统必须提供机制，以创建进程和终止进程。

进程创建

• 进程在执行过程中可能创建多个进程，创建进程为父进程，而新进程而子进程，每个新的进程可以创建其他进程，从而形成进程树。

• 大多数的操作系统，包括Unix，Linux，Windows，对进程的识别采用的是唯一的进程标识符，这通常是一个整数值，系统内的进程都有一个唯一的pid，它可以作为索引，以便访问内核中的进程的各种属性。

• 一般来说，当一个进程创建子进程时，该子进程会需要一定的资源（如CPU时间，内存，文件，I/O设备等）来完成任务。子进程可以从操作系统那里直接获得资源，也可以只从父进程那里获得资源子集，父进程可能要在子进程之间分配资源或共享资源（如内存和文件），限制子进程只能使用父进程资源，可以防止创建过多子进程，导致系统超载。

• 除了提供各种物理和逻辑资源外，父进程也可能向子进程传递初始化数据（或输入）。另外，有的操作系统也会向子进程传递资源。

• 在创建新进程时， 有两种执行可能：

• 1. 父进程与子进程并发执行
  2. 父进程等待，直到某个或全部子进程执行完

• 新进程的地址空间也有两种可能：

• 1. 子进程是父进程的复制品（他具有与父进程同样的数据和程序）
  2. 子进程加载另一个新程序

• 举例说明（Unix）

• • 在UNIX中，每个进程都有一个唯一的整型进程标识符来标识。通过系统调用fork()，可创建新进程，新进程的地址空间复制了原来进程的地址空间。这种机制允许父进程与子进程轻松通信，这两个进程（父与子）都继续执行处于系统调用fork()之后的指令，但有一点不同：对于子进程，系统调用fork的返回值为0，而对于父进程，系统调用的返回值为子进程的进程标识符（非零）。父进程与子进程不共用内存，互不影响。
  • 通常，在系统调用fork之后，有个进程会使用系统调用exec()，以用新程序来取代进程的内存空间。系统调用exec加载二进制文件到内存（破坏了包含系统调用exec的原来程序的内存内内容），并开始执行。采用这种方式，这两个进程能相互通信，并能按各自方法执行。父进程能够创建更多子进程，或者如果在子进程运行时没有什么可做，那么他采用系统调用wait把自己移出就绪队列，直到子进程终止。因为调用exec用新程序覆盖了进程的地址空间，所以调用exec除非出现错误，不会返回控制。
  • 没有什么可以阻止子进程不调用exec，而是继续作为父进程的副本来执行，在这种情况之下，父进程与子进程会并发执行，并采取相同的代码指令，由于子进程是父进程的一个副本，这两个进程都有各自的数据副本。

• 而Windows采用WindowsAPI函数CreateProcess()来创建子进程，不过fork让子进程继承了父进程的地址空间，但create process在创建进程是要求将一个特定程序加载到子程序的地址空间。再者fork不需要传递任何参数，而createprocess至少要传递十个参数。

进程终止

• 当进程完成执行最后语句并且通过系统调用exit()请求操作系统删除自身时，进程终止。这时，进程可以返回状态值(通常为整数)到父进程（通过系统调用wait()）。最后所有进程资源，如物理和虚拟内存、打开文件和i/o缓存区等，会由操作系统释放。

• 在其他情况下也会出现进程终止，进程通过适当系统调用（如Windows的terminate-process），可以终止另一进程。通常，只有终止进程的父进程才能执行这一系统调用。否则，用户可以任意终止彼此的作业。记住，如果终止子进程，则父进程需要知道这些子进程的标识符。因此，当一个进程创建新进程时，新创建进程的标识符要传递到父进程。

• 父进程终止子进程的原因有很多，比如：

• 1. 子进程使用了超过它所分配的资源，为判定是否发生这种情况，父进程应有一个机制，以检查子进程的状态
  2. 分配给子进程的任务，不再需要
  3. 父进程正在退出，而且操作系统不允许无父进程的子进程继续执行

• 有些系统不允许子进程在父进程已终止的情况下存在。对于这类系统，如果一个进程终止（正常或不正常），那么它的所有子进程也应终止。这种现象称为级联终止，通常由操作系统来启动。

• 当一个进程终止时操作系统会释放其资源。不过，它位于进程表中的条目还是在的，直到它的父进程调用wait，这是因为进程表包含了进程的退出状态，当进程已经终止，但是其父进程尚未调用wait，这样的进程称为僵尸进程，所有进程终止时都会过渡到这种状态，但是一般而言僵尸状态只是短暂存在。一旦调wait，僵尸进程的进程标识符和他在进程表中的条目就会释放。

• 如果父进程没有调用wait就终止，以至于子进程成为孤儿进程，Linux和Unix对于这种情况的处理是:将init进程作为孤儿进程的父进程。进程init定期调用wait以便收集任何孤儿进程的退出状态，并释放孤儿进程标识符和进程表条目。

进程间通信

导言

• 操作系统内的并发执行进程可以是独立的也可以是协作的。如果一个进程不能影响其他进程或受其他进程影响，那么该进程是独立的。显然，不与任何其他进程共享数据的进程是独立的。如果一个进程的影响其他进程或受其他进程所影响，那么该进程是协作的。显然与其他进程共享数据的进程是协作进程。

• 提供环境允许进程协作，具有许多理由：

• 1. 信息共享：允许并发访问信息
  2. 加速计算：可以将一个特定任务分成多个子任务，并行执行，需要多个处理核
  3. 模块化：可将系统功能分为独立的进程或线程
  4. 方便：即使单个用户也能同时执行许多任务

• 写作进程需要有一种进程间通信机制，以允许进程相互交换数据与信息。进程间通信有两种基本类型：共享内存和消息传递。共享内存模型会建立起一块供协作进程共享的内存区域，进程通过向此共享区域读出或写入数据来交换信息。消息传递模型通过在协作进程间交换消息来实现通信。

• 消息传递对于交换较少数量的数据很有用，因为无需避免冲突。对于分布式系统，消息传递也比共享内存更易实现。共享内存可以快于消息传递，这是因为消息传递的实现经常采用系统调用，因此需要消耗更多时间以便内核介入。与此相反，共享内存系统仅在建立共享内存区域时需要系统调用，一旦建立共享内存，所有访问都可作为常规内存访问，无需借助内核。在多个处理核系统上，消息传递的性能要优于共享内存。

共享内存系统

• 通常，一片共享内存区域驻留在创建共享内存段的进程地址里，其他希望使用这个共享内存段进行通信的进程应将其附加到自己的地址空间。
• 协作进程的通用范例：生产者-消费者问题：生产者进程生成信息，以供消费者进程消费。
• 解决生产者消费者问题的方法之一是采用共享内存。为了允许生产者进程和消费者进程并发执行，应有一个可用的缓冲区，以被生产者填充或被消费者清空。这个缓冲区驻留在生产者进程和消费者进程的共享内存区域内。当消费者使用一项时，生产者可产生另一项。生产者和消费者必须同步，这样消费者不会试图消费一个尚未生产出来的项。
• 缓冲区类型分为两种，无界缓冲区没有限制缓冲区的大小，消费者可能不得不等待新的项，但生产者总是可以产生新项。有界缓冲区假设固定大小的缓冲区，对于这种情况，如果缓冲区空，那么消费者必须等待，并且如果缓冲区满，那么生产者必须等待。

消息传递系统

• 消息传递提供一种机制，以便允许进程不必通过共享地址空间来实现通信和同步。

• 逻辑实现链路和操作send/receive的方法：

• • 直接或间接的通信
  • 同步或异步的通信
  • 自动或显式的缓冲

• 命名

• • 直接通信：对称寻址，发送和接收进程必须指定对方，非对称寻址，只要发送者指定接收者，接收者不需要指定发送者。
  • 间接通信：通过邮箱或端口来发送和接收消息，每个邮箱有一个唯一的标识符，邮箱可以为进程或操作系统所有，前者进程终止，邮箱消失，后者邮箱独立存在。

• 同步

• • 进程间通信可以通过调用原语send和receive来进行。实现这些原语有不同的设计方案，消息传递可以是阻塞或非阻塞，也称为同步或异步。

  • • 阻塞发送：发送进程阻塞，直到消息由接收进程或邮箱所接收
    • 非阻塞发送：发送进程发送消息，并且恢复操作
    • 阻塞接收：接收进程阻塞，直到有消息可用
    • 非阻塞接收：接收进程收到一个有效消息或空消息

  • 不同组合的send和receive都有可能，当send和receive都是阻塞的，则在发送者和接收者之间就有一个交汇，当采用阻塞的send和receive时，生产者消费者问题的解决就简单了。生产者仅需调用阻塞send并且等待，直到消息被传送到接收者或邮箱。同样，当消费者调用receive时，它会阻塞直到有一个消息可用。

• 缓存

• • 不管通信是直接的还是间接的都靠通信进程交换的消息总是驻留在临时队列中。简单的讲，队列实现有3种方法：

  • • 零容量：队列的最大长度为零，因此，链路中不能有任何消息处于等待，对于这种情况，发送者应阻塞，直到接收者接收到消息。
    • 有限容量：这个长度为有限的n，因此，最多只能有n个消息驻留其中，如果在发送新消息时队列为满，那么该消息可以放在队列中(或者复制该消息，或者保存该消息的指针)，且发送者可以继续执行而不必等待，然而，链路容量是有限的，如和链路已满多好那么发送者因阻塞，直到队列空间有可用的为止
    • 无限容量：队列长度可以无限，因此，不管多少消息，都可以在其中等待，发送者永不阻塞。

  • 零容量情况称为无缓冲的消息系统，其他情况称为自动缓冲的消息系统。

客户机/服务器通信

导言

• 进程通过共享内存和消息传递进行通信，这些技术也用于客户机/服务器系统的通信，客户机/服务系统通信还有3种其他的策略：套接字、远程程序调用和管道。

套接字

• 套接字为通信的端点。通过网络通信的每对进程需要使用一对套接字，即每个进程各有一个。每个套接字由一个IP地址和一个端口号组成。通常，套接字采用客户机-服务器架构。服务器通过监听指定端口，来等待客户请求。服务器在收到请求后，接受来自客户套接字的连接，从而完成连接。实现特定服务（telnet, ftp, http）的服务器监听众所周知的端口由：telnet服务器监听端口23，ftp服务器监听端口21，Web或HTTP服务器监听端口80。所有低于1024的端口都是众所周知的，我们可以用它们来实现标准服务。
• 当客户进程发出连接请求时，它的主机为它分配一个端口。这个端口具有大于1024的某个数字。例如，当IP地址为146.86.5.20的主机X的客户希望与IP地址为161.25.19.8的web服务器建立连接时（监听端口为80），它所分配的端口可为1625。该连接又一对套接字组成：主机X上的164.85.2.2 10:1625，web服务器上的161.25.19.8:80时。根据目的端口号码，主机之间传输的分组可以发送到适当的进程。

• 所有的连接必须是唯一的。因此，当主机X的另一个进程希望与同样的web服务器建立另一个连接时，它会分配到另外一个大于1024但不等于1625的端口号。这确保的所有连接都是唯一的一对套接字组成。
• 使用套接字的通信虽然常用和高效，但是属于分布式进程之间的一种低级形式的通信。一个原因是，套接字只允许在通信线程之间交换无结构的字节流。客户机或服务器程序需要自己加上数据结构。

远程过程调用RPC

• RPC是一种最为常见的远程服务，RPC对于通过网络连接系统之间的过程调用进行了抽象，它在许多方面都类似于IPC机制，并且通常建立在IP之上。不过因为现在的情况是进程处在不同系统上，所以应提供基于消息的通信方案，以提供远程服务。

• 与IPC的消息不一样，RPC通信交换的信息具有明确结构，因此不再仅仅是数据包。消息传到RPC服务，RPC服务监听远程系统的端口号，消息包含用于指定：执行函数的一个表示符以及传递给函数的一些参数，然后函数按要求来执行，而所有结果会通过另一消息传递回到请求者。

• 端口只是一个数字，处于消息分组头部，虽然每个系统通常只有一个网络地址，但是它可以有很多端口号，以便区分所支持的多个网络服务。

• RPC语义允许客户调用远程主机的过程用本地进过程一样。通过客户端提供的存根，RPC系统隐藏通信细节，通常，对于每个单独远程过程，都有一个存根。当客户调用远程过程时，RPC系统调用适当存根，并且传递远程过程参数。这个存根定位服务器的端口，并且封装参数。封装参数打包参数，以便通过网络传输。然后存根通过消息传递，向服务器发送一个消息。服务器的类似存根收到这个消息，并且调用服务器的过程。如果必要，返回值可通过同样技术传回到客户机。对于Windows系统，编译由MIDL语言编写的规范，可以生成存根代码。Microsoft接口定义语言用于定义客户机与服务器之间的接口。

• 他有三个处理事项：

• 一是涉及如何处理客户机与服务器的系统的不同数据表示。

• • 考虑32位整数的表示，有的系统使用内存的高地址，以存储高位字节，称为大端结尾：而其他系统使用内存的高地址，以存储低位字节，称为小端结尾。没有哪种顺序更好，这是由计算机体系结构来选择的，为了解决这一差异，许多RPC系统定义一个独立于机器的数据表示，一种这样的表示称为外部数据表示，在客户端，参数封装将机器相关数据打包成XDR，再发送到服务器。在服务器端，XDR数据被分封，再转成机器相关数据以交给服务器。

• 二是涉及调用语义。

• • 虽然本地过程调用只在极端情况下才失败，但是由于常见网络错误，RPC可能执行失败或者多次重复执行。解决这个问题的一种方法是操作系统确保每个消息执行正好一次，而非执行最多一次。大多数本地过程调用具有正好一次的特点，但是实现更难。
  • 首先，考虑最多一次。这种语义可以通过为每个消息附加时间戳来实现。服务器对所处理的消息应有一个完整的或足够长的时间戳的历史，以便确保能够检测到重复消息。进来的消息，如果其时间戳已出现过则被忽略。这样客户能够一次或多次发送消息，并确保仅执行一次。
  • 对于正好一次，需要消除服务器从未收到请求的风险。为了做到这点，服务器必须执行前面所述最多一次的协议，但是也必须向客户确认：RPC调用已经收到并且已经执行。这些ACK(确认)消息在网络中是常见的。客户机应周期性地重发每个RPC调用，直到它接收到对该调用的ACK。

• 三是涉及服务器和客户机之间的通信。

• • 对于标准的过程调用，链接、加载或执行有一定形式的绑定，以便过程名称被过程的内存地址所替代，RPC方案也要有一个类似于客户机和服务器端口之间的绑定，但是客户机如何知道服务器上的端口呢，这2个都没有对方的完全信息，因为它们并不共享内存。有2个方法是常见的，第一种方法，绑定信息可以按固定的端口地址形式预先固定，在编译时，RPC调用有一个与它关联的固定端口，一旦程序编译后，服务器无法更改请求服务的端口号。第2种方法是绑定通过交会机制动态进行，通常操作系统在一个固定IPC端口上提供交会服务程序或月老。客户程序发送一个包括RPC名称的消息到交会服务程序，以便请求所需执行的RPC的端口地址。在得到返回的端口号后，RPC调用可以发送到这一端口号，直到进程终止或服务器崩溃，这种方式的初始请求需要额外开销，但是比第一种更为灵活。下面是交会实例

• RPC方案可以用于实现分布式文件系统，通过一组RPC服务程序和客户来实现，当要进行文件操作时，消息可以通过服务器的分布式文件系统的调用，该消息包括所要执行的磁盘操作，（读写命名删除等），返回消息包括来自调用的任何数据。

管道

• 管道允许两个进程进行通信，比较简单，但也有局限性

• 普通管道

• • 普通管道允许2个进程按标准的生产者-消费者方式进行通信：生产者向管道的一端（写入端）写，消费者从管道的另一端（读出端）读。因此，普通管道是单向的，只允许单向通信。如果需要双向通信，那么就要采用2个管道，而每个管道向不同方向发送数据。普通管道只能由创建进程所访问，通常情况下父进程创建一个管道，并使用它来与其子进程进行通信。子进程继承了父进程的打开文件，由于管道是一种特殊类型的文件，因此子进程也继承了父进程的管道。

• 命名管道

• • 命名管道提供了一个更强大的通信工具。通信可以是双向的，并且父子关系不是必需的。当建立了一个命名管道后，多个进程都可以用它通信。事实上，在一个典型的场景中，一个命名管道有几个写者。此外，当通信进程完成后，命名管道仍继续存在。

• 管道提供了一个相对简单的进程间的相互通信，普通管道允许父子进程之间的通信，而命名管道允许不相关进程之间的通信