第二章 进程管理

1、第二章 进程管理,在传统的操作系统中，程序并不能 独立运行，作为资源分配和独立运行的 基本单位都是进程。操作系统的四大特 征也都是基于进程的。,第二章 进程管理,一、进程的基本概念,?,问题：程序与进程的关系？,一、进程的基本概念,程序的顺序执行及其特征 程序的并发执行及其特征 进程的特征与状态 进程控制块,1、程序的顺序执行及其特征,程序的顺序执行 把一个应用程序分成若干程序段，在各段程序之间，必须按照某种先后次序顺序执行，仅当前一操作执行完后，才能执行后继操作。 例如：三条语句 S1： a:=x+y; S2： b:=a-5; S3： c:=b+1;,程序顺序执行的特征 顺序性 封闭性 可再

2、现性,2、程序的并发执行及其特征,程序的并发执行 I:输入 C：计算 P：打印,程序并发执行时的特征 间断性 失去封闭性 不可再现性,3,3、进程的特征与状态,进程的概念 进程(Process)：一个独立的程序在一个数据集合上的一次运行过程，是分配资源和调度的独立单位。,3,3、进程的特征与状态,进程的特征 结构特征：由程序段、相关数据段、PCB组成 PCB(Process Control Block)：进程控制块 动态性：由创建而产生，由调度而执行，由撤消而消亡。 并发性：多个进程实体在一段时间内同时运行。 独立性：是运行/获得资源/被调度的独立单位。 异步性：按各自独立的、不可预知的速度前

3、进。,?,问题：程序与进程的关系？,进程是程序的一次执行过程 程序是静态的，进程是动态的 一个程序可对应一个进程，也可对应多个进程（进程对应的数据集不同） 进程可以创建其它进程,3,3、进程的特征与状态,进程的基本状态及状态转换 就绪状态：进程已得到除CPU以外的所有必要资源。 执行状态：进程已获得CPU，其程序正在执行。 阻塞状态：正在执行的进程由于发生某事件而暂时无法继续执行时，放弃CPU而处于暂停状态。,状态转换 （1）就绪状态变化到执行状态 。 （2）执行状态变化到就绪状态。 （3）执行状态变化到阻塞状态。 （4）阻塞状态变化到就绪状态。,状态转换,PCB是进程存在的唯一标志,3,4、

4、进程控制块,为了描述和控制进程的运行，系统为每个进程定义了一个数据结构-进程控制块PCB（Process Control Block），OS根据PCB来对并发执行的进程进行控制和管理。,3,4、进程控制块,PCB中的信息 进程标识符：用于唯一地标识一个进程 处理机状态 进程调度信息 进程控制信息,CPU在进程间的切换,3,4、进程控制块,PCB的组织方式 链接方式,3,4、进程控制块,PCB的组织方式 索引方式,3,二、进程控制,进程的创建 进程的终止 进程的阻塞与唤醒,3,二、进程控制,原语：在系统态下执行的某些具有特定功能的程序段。原语中所有动作不可分割，要么全做，要么全不做。 进程控制原

5、语： 创建原语 撤消原语 阻塞原语 唤醒原语,1、进程的创建,进程图：用于描述一个进程家族关系的有向树。,3,1、进程的创建,引起进程创建的事件 用户登录 作业调度 提供服务 应用请求(父进程创建子进程),3,1、进程的创建,进程的创建 申请空白PCB 为新进程分配资源（为新进程的程序和数据以及用户栈分配必要的内存空间） 初始化进程控制块（标识信息、处理机状态信息、处理机控制信息） 将新进程插入就绪队列,3,2、进程的终止,引起进程终止的事件 正常结束：进程完成。 异常结束：越界错误、保护措、非法指令、特权指令错、运行超时、等待超时、算术运算错误、I/O错。 外界干预：操作员、父进程请求、父进

6、程终止,3,2、进程的终止,进程的终止过程 检索终止进程的PCB，读取该进程的状态。 若为执行状态，终止该进程，设置调度标志为真，指示该进程被终止后应重新进行调度。 若该进程有子孙进程，将子孙进程终止。 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。 将被终止进程的PCB从所在队列中移出，等待其它程序来搜集信息。,3,3、进程的阻塞与唤醒,引起进程阻塞和唤醒的事件 请求系统服务得不到满足 启动某种操作(I/O) 新数据尚未到达 无新工作可做,3,3、进程的阻塞与唤醒,进程阻塞过程 保护现场停止执行，修改进程的状态，将其PCB插入到阻塞队列，调度另一进程。,3,3、进程的阻塞

7、与唤醒,进程唤醒过程 当等待事件发生时唤醒。将其PCB改为就绪状态，并从阻塞队列移入就绪队列。,3,三、进程同步,进程同步的主要任务，是使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行具有可再现性。,3,两种形式的制约关系 间接相互制约关系：源于资源共享。 直接相互制约关系：源于进程间的合作。,3,进程同步Synchronization ：(直接制约)一组并发进程因相互发送消息而进行合作或相互等待。 例：读数进程和计算进程使用同一个缓冲区。,3,进程互斥Mutual Exclusion ：(间接制约) 临界资源：一次仅允许一个进程使用的资源。 临界区：一个进程访问临界资源的那

8、段程序代码。,例：两个排队进程P1、P2共享某一个队列：,例：两个进程共享一个变量x 设：x代表某航班机座号，p1和p2两个售票进程，售票工作是对变量x加1。 这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2 ，两个进程共享一个变量x时，两种可能的执行次序：,情况B为 x = 10+1,3,互斥：不允许两个以上的进程同时使用临界资源或进入临界区。 同步机制应遵循的原则： 空闲让进 忙则等待 有限等待 让权等待,3,进程同步机制信号量和P、V操作,1965年荷兰的计算机科学家Dijkstra提出了新的同步工具信号量和P、V操作。 他将交通管制中多种颜色的信号灯管理交通的方法引入操

9、作系统，让两个或多个进程通过信号量(Semaphore) 展开交互。,3,进程同步机制信号量和P、V操作,信号量(Semaphores)：不要求忙等的同步工具。 信号量S：整型变量，初值=0 一个信号量表示一个资源或一个同步条件 S只能被下面两个原语访问： Wait(s)： 也称P()操作 Signal(s): 也称V()操作,3,进程同步机制信号量和P、V操作,信号量实现 整型信号量 Wait(s):while s=0 do no-op; s:=s-1; Signal(s): s:=s+1;,3,进程同步机制信号量和P、V操作,记录型信号量,P(semaphore s) s.value=s.

10、value-1; If (s.value0) Add p to process L; Block(p); ,V(semaphore s) s.value=s. value+1; If (s. value=0) remove p from L; wakeup(p); ,申请分配资源,释放资源,3,进程同步机制信号量和P、V操作,用P、V实现进程互斥 为临界资源设置一互斥信号量mutex,初值=1。 进程访问该临界资源，需对mutex执行wait操作， 退出临界区后，应对mutex执行signal操作。,进程同步机制信号量和P、V操作,3,进程同步机制信号量和P、V操作,用P、V实现进程互斥,3,

11、四、经典进程同步问题,生产者消费者问题 问题描述：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中，消费者进程可以从一个缓冲区中取走产品去消费。,3,四、经典进程同步问题,生产者消费者问题 要求：尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。,3,四、经典进程同步问题,生产者消费者问题 解决办法： 缓冲池一次只能让一个进程

12、访问。互斥条件设一信号量mutex，初值1。 生产者需要空缓冲来发送数据。同步条件设一信号量empty，初值n。 消费者需要满缓冲来获取数据。同步条件设一信号量full，初值0。,四、经典进程同步问题,生产者消费者问题,V()顺序随意,但P()顺序不能颠倒,思考与说明,如果我们把消费者进程中的两个P操作交换次序，那么会有什么问题吗？ 在这个问题中P操作的次序是很重要的，如果我们把消费者进程中的两个P操作交换次序，那么就会产生与时间有关的错误。 分析如下：,分析说明,在某个时刻,消费者消费的比较快，把所有的产品消费完，有:empty=n,mutex=1,full=0 接着消费者进程运行到P(mu

13、tex)处，使得mutex=0,运行到P(full)处full=-10，消费者进程等待 在接着生产者进程运行到P(empty)处，由于生产了一个产品，故空位置-1，empty=n-1， 运行到P(mutex)处,由于p(mutex)操作，mutex=mutex-1=-10，生产者进程也等待。 故而，这两个程序陷于相互等待的死锁状态。,思考,思考与延伸：交换生产者的两个p操作会不会带来与时间有关的错误呢？如果会，在什么情况下会？请分析之。,思考与结论,所以在使用PV操作实现进程同步时，特别要当心P操作的次序，而V操作的次序倒是无关紧要的。 一般来说，用于互斥的信号量上的P操作，总是在用于协作的P

14、操作之后执行。,3,四、经典进程同步问题,哲学家进餐问题 问题描述：五个哲学家在一张圆桌上进餐，桌上只有五个碗和五支筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近的筷子，只有在他拿到左右两只筷子时才能进餐。进餐毕，放下筷子继续思考。,3,四、经典进程同步问题,哲学家进餐问题 解决方法：每根筷子就是一个临界资源。 设一信号量组chocpstick5,初值为1。,四、经典进程同步问题,请大家注意，如果五个哲学家同时变得饥饿的话，且同时拿起他左边的筷子。这样所有的chopstick都变成0。就有可能出现每个哲学家举起左边的一只筷子，却又在永远等待相

15、邻哲学家手中的筷子的情况哲学家就会饿死。,当每个哲学家都拿起一根(左)筷子时，死锁。,四、经典进程同步问题,思考：如果增加一条指令：吃不到就放下自己手中的筷子，这样哲学家还会饿死吗？ 这样同样会导致哲学家会饿死，因为可能在上面的情况下，五个哲学家因为自己吃不到东西，同时放下筷子，因为大家还饿着呢，环顾一看左右都有筷子，可能又同时拿起筷子，就这样，同时拿起，同时放下循环往复。哲学家们不饿死，也得累死。 这就是死锁情况。,3,四、经典进程同步问题,哲学家进餐问题 解决方法1：至多允许4个哲学家同时拿起筷子。,3,四、经典进程同步问题,哲学家进餐问题 解决方法2：奇数号人先拿左筷，偶数号人先拿右筷。

16、,3,五、线程,线程(Threads)的引入： 进程的两个基本属性：可拥有资源的独立单位；可独立调度和分派的基本单位。 问题的提出：由于进程是一个资源拥有者，因而在创建、撤销和切换中，系统必须为之付出较大的时空开销。,3,五、线程,线程(Threads)的引入： 解决办法：对拥有资源的基本单位（进程），不频繁的进行切换；对被调度运行的基本单位（线程），不拥有资源，使之轻装运行。,3,五、线程,线程(Threads)是一个进程内部的基本调度单位。一个进程可产生多个线程，线程间并发运行。 进程是资源分配和抢占处理机的单位，进程的资源及地址空间供其所有线程共享。 线程不拥有资源，线程执行环境小，同一进程的不同线程间切换和通信时开销小。,3,五、线程,线程的属性： 轻型实体。线程中的实体基本上不拥有资源。 独立调度和分派的基本单位。 可并发执行。 共享进程资源。所有线程都具有相同的地址空间（进程的地址空间）。,习题,一个进程处于就绪态，表示该进程获得了除（ ）以外所有运行所需要的资源。 A主存储器 B打印机 CCPU D磁盘空间 答案：C,习题,某个信号量S初值为3，当前值为-2，则等待在该信号量上的进程数为_。