进程及进程管理

进程引入

顺序程序及特点

• 计算：程序的一次执行过程称为一个计算，它由许多简单操作所组成。
• 程序的顺序执行：一个计算的若干操作必须按照严格的先后次序顺序地执行，这类计算过程就是程序的顺序执行过程。

单道系统的工作情况：对用户作业的处理 —— 首先输入用户的程序和数据；然后进行计算；最后打印计 算结果，即有三个顺序执行的操作。 I：输入操作 C：计算操作 P：输出操作

特点：

• 顺序性 —— 处理机的操作严格按照程序所规定的 顺序执行。
• 封闭性 —— 程序一旦开始执行，其计算结果不受 外界因素的影响。
• 可再现性 —— 程序执行的结果与它的执行速度无 关 (即与时间无关)，而只与初始条件有关。

并发程序

若干个程序段同时在系统中运行，这些程序段的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重叠是很小的一部分，也称这几个程序段是并发执行的。

特点：

• 失去程序的封闭性和可再现性
  若一个程序的执行可以改变另一个程序的变量，那么，后 者的输出就可能有赖于各程序执行的相对速度，即失去了 程序的封闭性特点。
• 程序与计算不再一一对应
  一个程序可以对应多个计算。
• 程序并发执行的相互制约
  • 间接的相互制约关系 —— 资源共享
  • 直接的相互制约关系 —— 公共变量

与时间有关的错误

程序并发执行时，若共享了公共变量，其执行结果与各并发程序的相对速度有关，即给定相同的初始条件，若不加以控制，也可能得到不同的结果，此为与时间有关的错误。
为了保证得到唯一的正确结果，需要实现并发程序执行时的互斥和同步。

进程概念

进程定义

什么是进程？
所谓进程，就是一个程序在给定活动空间和初始环境下， 在一个处理机上的执行过程。

进程与程序的区别

• 程序是指令的有序计合，是一个静态的概念，进程是程序在处理及上的一次执行过程，是动态的概念；
• 进程是一个独立运行的活动单位，能与其他进程并行的活动；
• 进程是竞争计算机系统资源的基本单位，也是进行处理机调度的基本单位；
• 一个程序可以对应多个进程，一个进程至少包含一个程序。

进程的状态

进程的基本状态

• 运行状态(running) 该进程已获得运行所必需的资源，它的程序正在处理机上 执行。
• 等待状态(wait) 进程正等待着某一事件的发生而暂时停止执行。这时， 即使给它CPU控制权，它也无法执行。
• 就绪状态(ready) 进程已获得除CPU之外的运行所必需的资源，一旦得到 CPU控制权，立即可以运行。

进程描述

什么是进程控制块
描述进程与其他进程、系统资源的关系以及进程在各个不同时期所处的状态的数据结构，称为进程控制块 PCB (process control block)。

进程的组成

• 程序与数据
  描述进程本身所应完成的功能

• PCB
  进程的动态特征，该进程与其他进 程和系统资源的关系。

  

进程控制块的主要内容

• 进程标识符 进程符号名或内部 id号
• 进程当前状态 本进程目前处于何种状态
• 当前队列指针next 该项登记了处于同一状态的下一个进程的 PCB地址。
• 进程优先级 反映了进程要求CPU的紧迫程度。
• CPU现场保护区 当进程由于某种原因释放处理机时，CPU现场信息被保存在PCB的该区域中。
• 通信信息 进程间进行通信时所记录的有关信息。
• 家族联系 指明本进程与家族的联系
• 占有资源清单

进程控制

进程控制的职责 ：对系统中的进程实施有效的管理，负责进程状态的改变。
常用的进程控制原语：创建原语creat、撤消原语kill、阻塞原语susp、唤醒原语wakeup

进程之间的约束关系

进程竞争与合作

进程之间的约束关系可分为两种情况：

• 由于竞争系统资源而引起的间接相互制约关系
• 由于进程之间存在共享数据而引起的直接相互制约关系
  • 进程协作：信息共享和并行处理

进程互斥

临界资源：一次仅允许一个进程使用的资源称为临界资源。 硬件：如输入机、打印机、磁带机等 软件：如公用变量、数据、表格、队列等 。

临界区是进程中对公共变量 (或存储区)进行审查与修改的程序段，称为相对于该公共变量的临界区。
注意：

• 临界区是针对某一临界资源而言的
• 相对于某临界资源的临界区个数就是共享该临界资源的进程个数
• 相对于同一个公共变量的若干个临界区，必须是互斥地进入

互斥：在操作系统中，当某一进程正在访问某一存储区域时，就 不允许其他进程来读出或者修改存储区的内容，否则，就 会发生后果无法估计的错误。进程间的这种相互制约关系 称为互斥。

进程同步

什么是进程同步：并发进程在一些关键点上可能需要互相等待与互通消息， 这种相互制约的等待与互通消息称为进程同步。 同步意味着两个或多个进程之间根据它们一致同意的协议进行相互作用。同步的实质是使各合作进程的行为保持某种一致性或不变关系。

进程同步示例：

• 病员就诊
• 共享缓冲区的计算进程与打印进程的同步

同步机构

锁和上锁、开锁操作

什么是锁：用变量w代表某种资源的状态，w称为“锁” 。用1表示资源已经被占用。

上锁操作和开锁操作

• 检测w的值 (是0还是1)；
• 如果w的值为1，继续检测；
• 如果w的值为0，将锁位置1 (表示占用资源)，进入临界区执行。 (此为上锁操作)
• 临界资源使用完毕，将锁位置0。 (此为开锁操作)

信号灯和P、V操作

什么是信号灯
信号灯是一个确定的二元组 (s，q)，s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管理。
信号灯是整型变量。
变量值 ≥ 0 时，表示绿灯，进程执行； 变量值 ＜ 0 时，表示红灯，进程停止执行。
注意：创建信号灯时，应准确说明信号灯 s 的意义和初值
(这个初值绝不能为负值)。

P 操作 定义：对信号灯s的 p操作记为 p(s)。p(s)是一个不可分割的原语操作，即取信号灯值减1，若相减结果为负，则调用p(s)的进程被阻，并插入到
该信号灯的等待队列中，否则可以继续执行。

V 操作 定义：对信号灯s的 v操作记为 v(s)。v(s)是一个不可分割的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行，否则，要帮助唤醒在信号灯等待队列上的一个进程。

同步机构

生产者消费者问题

生产者与消费者的同步关系

• 生产者：
  • 当有界缓冲区中无空位置时，要等待；
  • 向有界缓冲区放入物品后，要发消息。
• 消费者：
  • 当有界缓冲区中无物品时，要等待；
  • 从有界缓冲区取出物品后，要发消息。

信号灯设置

• 两个同步信号灯——
  • sb ：表示空缓冲区的数目，初值 = n
  • sa ： 表示满缓冲区 (即信息)的数目，初值 = 0
• 一个互斥信号灯——
  • mutex：表示有界缓冲区是否被占用，初值 = 1

程序描述
程序 prod_cons

main( )
{
   int sa=0； ∕/满缓冲区数目  
   int sb=n； ∕/空缓冲区数目
   int  mutex=1； ∕/对有界缓冲区进行操作 
   cobegin 
   p1 ( )； p2 ( )；… pm ( )； 
   c1 ( )； c2 ( )；… ck ( )； 
   coend
}

pi( )                                                     
{
   while(生产未完成)
   {
      M
      生产一个产品;
      p(sb)；
      p(mutex)； 
      送一个产品到有界缓冲区；
      v(mutex)；
      v(sa)；
   }  
}

cj( ) 
{ 
   while(还要继续消费)
   {
        p(sa)； 
        p(mutex)；
        从有界缓冲区中取产品
        v(mutex)； 
        v(sb)； 
        消费一个产品； 
        M

理发师睡觉问题

理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等。如果没有空椅子，他就离开。

• 一个理发师，一把理发椅，n把等候理发的顾客椅子。

  • 如果没有顾客，则理发师在理发椅上睡觉；
  • 当有一个顾客到达时，首先看理发师在干什么， 如果理发师在睡觉，则唤醒理发师理发； 如果理发师正在理发，则查看是否有空的顾客椅子可 坐； 如果有顾客椅子可坐，则坐下等待，如果没有，则 离开。
  • 理发师为一位顾客理完发后，查看是否有人在等待， 如果有则唤醒下一位顾客理发，没有则理发师去睡觉。

• 理发师和顾客之间的同步关系
  当理发师睡觉时，顾客进来需要唤醒理发师为其理发；
  当有顾客时理发师为其理发，没有的时候理发师睡觉。

• 理发师与顾客、顾客与顾客之间的互斥关系
  由于每次理发师只能为1个人理发，且可供等侯的椅子只有n把，即理发师和椅子是临界资源，顾客之间是互斥的关系。

信号灯设置
引入3个信号量和一个控制变量：

• 控制变量waiting用来记录等候理发的顾客数，初值均为0; 进入理发店的顾客必须先看等候的顾客数，如果少于椅子数， 他留下来等，否则他就离开。
• 信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0;
• 信号量barbers用来记录正在等候顾客的理发师数，并用作 阻塞顾客进程，初值为0;
• 信号量mutex用于互斥，初值为1.

# define CHAIRS 5 /*为等待的顾客准备的椅子数*/ 
typedef int semaphone ; /*信号灯类型*/ 
semaphore customers=0; /*等待服务的顾客数*/ 
semaphore barbers=0; /*等待顾客的理发师数*/ 
semaphore mutex=1; /*用于互斥*/
int waiting=0; /*等待的顾客(还没理发的)，waiting是一个共享变量，对它操作时必须加锁，用mutex加以保护*/

main() 
{   
   …… 
   cobegin 
      barber（）； 
      customers（）； 
   coend 
   …… 
}

void barber(void) 
{ 
   while(TRUE) /*理完1人,还有顾客吗?*/ 
   { 
      p(customers); /*如果顾客数是0，则理发师睡眠*/ 
      p(mutex); /*要求进程等待*/ 
         waiting=waiting-1; /*等待顾客数减1*/ 
      v(barbers); /*一个理发师现在开始理发了*/ 
      v(mutex); /*释放等待*/ 
      cut_hair(); /*理发(非临界区操作)*/ 
   } 
}

void customers(void) 
{       
   p(mutex);/*进入临界区*/ 
   if (waiting < CHAIRS) 
   {/*如果没有空椅子，就离开*/ 
      waiting = waiting + 1;/*等待顾客数加1*/ 
      v(customers); /*如果必要的话，唤醒理发师*/ 
      v(mutex); /*释放访问等待*/ 
      p(barbers); /*无理发师, 顾客坐着养神*/ 
      get_haircut();/*一个顾客坐下等理发*/ 
   } 
   else 
      v(mutex); /*店里人满了，走吧*/ 
} 

进程通信

进程通信(Interprocess Communication, IPC)是指进程之间直 接以较高的效率传递较多数据的信息交互方式。

IPC机制：指消息（message）从一个进程的地址空间拷贝到另一个进程 的地址空间的过程，而不使用共享存储器。

进程通信方式

消息缓冲通信

• 在消息通信中，接收方和发送方之间有明确的协议和消息格式 。
  • 大多数使用消息头：发送/接收进程的ID、被传消息的字节数……
• 消息缓冲通信方式包括消息缓冲、发送原语和接收原语。
  • 发送进程先形成一个消息缓冲区（含消息头和消息内容），然后用发送原语发出。
  • 接收进程在接收前，在本进程的主存空间设置一个接收区，然后用接收原语接收。

信箱通信

• 在信箱通信中，需要定义信箱结构，还包括消息发送和接收功能模块，提供发送原语和接收原语。
• 信箱通信中，所使用的信箱可以位于用户空间中，是接收进程地址空间的一部分；也可以放置在操作系统的空间中。

使用用户空间中的信箱实现消息传递
信箱由用户管理，进程可以直接访问信息

缺点：

• 编译器和加载程序必须为每一个进程分配信箱空间 ；
• 接收进程有可能覆盖信息的部分内容，从而造成错误。

使用系统空间中的信箱实现消息传递
信箱由OS管理，任何进程不能直接访问

缺点：要求OS为所有的进程分配主存信箱，受系统限制，可 能对通信进程数限制。

线程概念及特点

为什么引入线程？

• 为了避免多处理机系统在进行远程访问期间的等待现象。
• 线程就是进程的一个执行路径，一个进程可以有多条执行路径。这样，一个进程内部就有多个可 以独立活动的单位，可以加快进程处理的速度， 进一步提升并行处理能力。

线程 定义：线程是比进程更小的活动单位，它是进程中的一个执行路径。

线程可以这样来描述

• 进程中的一条执行路径；
• 它有自己私用的堆栈和处理机执行环境 ；
• 它与父进程共享分配给父进程的主存；
• 它是单个进程所创建的许多个同时存在的线程中的一个。

线程的特点

• 线程是比进程更小的活动单位，它是进程中的一个执 行路径。创建一个线程比创建一个进程开销要小得多。
• 实现线程间通信十分方便，因为一个进程创建的多个 线程可以共享地址区域和数据。
• 线程是一个动态的概念。
• 在进程内创建多线程，可以提高系统的并行处理能力， 加快进程的处理速度。

进程是任务调度的单位，也是系统资源的分配单位；而线程是进程中的一条执行路径，当系统支持多线程处理时，线程是任务调度的单位，但不是系统资源的分配单位。线程完全继承父进程占有的资源，当它活动时，具有自己的运行现场。

用户线程和内核线程

• 用户线程
  • 在内核的支持下，在用户层通过线程库实现
  • 创建和调度在用户空间进行，无需内核干预
  • 优点：能快速创建和管理
  • 缺点：如果内核是单线程的，一旦一个用户线程执行了等待的系统调用，则整个进程阻塞
• 内核线程
  • 由OS管理，创建和调度在OS主存空间内完成
  • 当一个线程执行时阻塞，内核能调度另一个线 程运行

操作系统的并发机制实例

创建进程及应用实例

调用形式 （UNIX/LINUX系统）：pid=fork();
功能：创建一个子进程，被创建的子进程是父进程的进程映像的一个副本 (除proc结构外)，在UNIX系统中，除了0#进程外，其它进程都是通过调用进程创建系统调用创建的。

系统调用 fork 完成的操作
UNIX/Linux系统的核心为系统调用fork 完成下列操作：
① 为新进程分配一个新的pcb结构；
② 为子进程赋一个唯一的进程标识号 (PID)；
③ 做一个父进程上下文的逻辑副本。由于进程的正文区 (代码段)可被几个进程所共享，所以核心只要增加某个正文区的引用数即可，而不是真的将该区拷贝到一个新的内存物理区。这就意味着父子进程将执行相同的代码。数据段和堆栈段属于进程的私有数据，需要拷贝到 新的内存区中。
④ 增加d与该进程相关联的文件表和索引节点表的引用数。这就意味 着父进程打开的文件子进程可以继续使用。
⑤ 对父进程返回子进程的进程号，对子进程返回零。

如何启动一个新的程序的执行？

• 父进程为了启动一个新的程序的执行，在 UNIX/LINUX系统中需要用到exec()类函数
• Exec()类函数很多 作用是根据参数指定的文件名找到可执行文件 ，并用它来取代调用进程的内容，即在调用进 程内部执行一个可执行文件。

创建线程及应用实例

• LINUX下的多线程程序，需要使用pthread.h，连接时需要使用库libpthread.a。
• Clone( )是LINUX特有的系统调用，用来实现 pthread。与fork( )类似。

调用形式 ：pthread_create(pthread_t *thread, pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);

等待进程终止 wait(); waitpid();
① wait() 语法格式
pid=wait(stat_addr);
wait()函数使父进程暂停执行，直到它的一个子进程结束为止，该函数的返回值是终止运行的子进程的PID。参数status所指向的变量存放子进程的退出码，即从子进程的main函数返回的值或子进程中exit()函数的参数。如果status不是一个空指针，状态信息将被写入它指向的变量。
② waitpid() 语法格式
pid=wait(stat_addr);
waitpid(pid_t pid,int * status,int options)
用来等待子进程的结束，但它用于等待某个特定进程结束。参数pid指明要等待的子进程的PID，参数status的含义与wait()函数中的status相同。

进程调度

进程调度的功能

调度：在众多处于就绪状态的进程中，按一定的原则选择一个进程。

分派：当处理机空闲时，移出就绪队列中第一个进程，并赋予它使用处理机的权利。

进程调度的功能

• 记录进程的有关情况
• 决定调度策略
  • 优先调度
    就绪队列按进程优先级高低排序
  • 先来先服务
    就绪队列按进程来到的先后次序排序
• 实施处理机的分配和回收

进程调度的方式

• 什么是调度方式：当一进程正在处理机上执行时，若有某个更为“重要而紧迫” 的进程需要运行，系统如何分配处理机。
• 非剥夺方式：当“重要而紧迫”的进程来到时，让正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞” 状态时，才把处理机分配给“重要而紧迫”的进程。
• 剥夺方式 当“重要而紧迫”的进程来到时，便暂停正在执行的进程， 立即把处理机分配给优先级更高的进程。

进程调度算法

进程优先数调度算法

什么是进程优先数调度算法
预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权 (优先数和一定的优先级相对应) 的就绪进程。

优先数的分类及确定

• 静态优先数
  在进程被创建时确定，且一经确定后在整个进程运行 期间不再改变。
• 静态优先数的确定
  • 优先数根据进程所需使用的资源来计算
  • 优先数基于程序运行时间的估计
  • 优先数基于进程的类型
• 动态优先数
  进程优先数在进程运行期间可以改变。
• 动态优先数的确定
  • 进程使用CPU超过一定数值时，降低优先数
  • 进程I/O操作后，增加优先数
  • 进程等待时间超过一定数值时，提高优先数

循环轮转调度算法

什么是循环轮转调度算法
当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。

简单循环轮转调度算法
就绪队列中的所有进程以等速度向前进展。
q = t/n
t 为用户所能接受的响应时间，n为进入系统的进程数目。

循环轮转调度算法的发展

• 可变时间片轮转调度
• 多重时间片循环调度

调度用的进程状态变迁图

• 进程状态
  • 运行状态
  • 低优先就绪状态
  • 高优先就绪状态
  • 因I/O而等待状态
• 队列结构
  • 低优先就绪队列
  • 高优先就绪队列
  • 因I/O而等待队列
• 进程调度算法
  优先调度与时间片调度相结合的调度算法
  • 当CPU空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为100ms。
  • 当CPU空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为500ms。
• 调度效果
  优先照顾I∕O量大的进程；适当照顾计算量大的进程。