2011年考研计算机之进程管理

1 第二章 进程管理 2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 进程通信 2.6 线程 2.1 进程的基本概念 2.1.1 程序的顺序执行及其特征 2.1.2 前趋图 前趋图 (Precedence Graph)是一个有向无循环图，记为 DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后 关系。 2.1.3 程序的并发执行及其特征 2.1.4 进程的特征与状态 前趋图的形式 前趋图的示 One program which has an independent function works on certain data set dynamically and allocate resources dynamically 进程的定义 一个具有一定独立功能的程序对某个数据集合上 的一次动态执行过程和资源分配过程 进程的元素：代码、数据、进程表（进程控制块） Code、Data、PT（PCB） 进程和程序的区别与联系 • 进程是动态的，程序是静态的 • 进程是暂时的，程序是永久的 • 进程和程序的组成不同 • 程序主要包含代码和数据 • 进程除了包含代码和数据以外，还有进程表 • 进程和程序间有非常紧密的联系 • 程序经过多次创建，可以对应不同的进程 • 一个进程通过系统调用，可以被多个程序所使用 选择填空 • 进程包含（）、（）和（）。 • 数据；记录项；目录；代码；进程 表；文件，共享库。 2 选择填空 • （）是进程存在的唯一标志。 • 数据；记录项；目录；代码；进程 表；文件，共享库。 2. 进程的三种基本状态 1) 就绪(Ready)状态 2) 执行(Running)状态 3) 阻塞(Blocking)状态 后备 2.1.5 进程表 1. 进程表的作用 2. 进程表中的信息 3. 进程表的组织方式 1) 链接方式 2) 索引方式 就绪队列链表（一般为一个） 阻塞队列链表（可能依据不同阻塞原因有多个队列链表） 进程表 就绪队列索引 阻塞队列索引 3 2.2 进 程 控 制 2.2.1 进程的创建 (1)用户登录。 (2) 作业调度。 (3) 提供服务。 (4) 应用请求。 (1) 申请空白进程表。 (2) 为新进程分配资源。 (3) 初始化进程表。 (4) 如果进程就绪队列能够接纳新 进程， 便将新进程插入就绪队列。 2.2.2 进程的创建过程 选择题 • 进程创建后，所有创建完成后的进程 PCB被链接成一个序列，这个序列称 为什么？ • 阻塞序列； • 挂起序列； • 就绪序列； • 运行序列。 选择题 • 10年24．下列选项中，导致创建新进程的操作是 • I．用户登录成功 • II．设备分配 • III．启动程序执行 • A．仅I和II • B．仅II和III • C．仅I和III • D．I、II和III 2.2.2 进程的终止 1) 正常结束（自愿的） 2) 异常结束 ----普通错误退出（自愿的） ----致命错误退出（非自愿的） 3) 外界干预（非自愿的） 2. 进程的终止过程 (1) 根据被终止进程的标识符，从进程表中检索出该进 程的进程控制块，从中读出该进程的状态。 (2) 若被终止进程正处于执行状态，应立即终止该进程 的执行，并置调度标志为真，用于指示该进程被终止后应 重新进行调度。 (3) 若该进程还有子孙进程，还应将其所有子孙进程予以 终止，以防他们成为不可控的进程。 (4) 将被终止进程所拥有的全部资源，或者归还给其父进 程， 或者归还给系统。 (5) 将被终止进程(它的进程控制块)从所在队列(或链表) 中移出， 等待其他程序来搜集信息。 2.2.3 进程的阻塞与唤醒 1. 引起进程阻塞和唤醒的事件 1) 请求系统服务 2) 启动某种操作 3) 新数据尚未到达 4) 无新工作可做 2.2.4 进程的挂起与激活 4 2.3 进 程 同 步 2.3.1 进程同步的基本概念 1. 两种形式的制约关系 (1)间接相互制约关系。 (2) 直接相互制约关系。 2. 临界资源(Critical Resource) 3. 临界区(critical section) 一个飞机订票系统（软件相同），两个终端，运行T1、T2 进程 T1： …… read(x); if x>=1 then x:=x-1; write(x); …… T2： …… read(x); if x>=1 then x:=x-1; write(x); …… 互斥关系 Coming data blocks 初始状态 结果 正确 错误 错误 错误 错误 错误 同步关系 4. 同步机制应遵循的规则 (1)空闲让进。 (2) 忙则等待。 (3) 有限等待。 (4) 让权等待。 (Peterson’s Algorithm)： 先修改、后检查、后修改者等待 • 正确的算法 • turn=j;描述可进入的进程（同时修改标志时） • 在进入区先修改后检查，并检查并发修改的先后： • 检查对方flag，如果不在临界区则自己进入－－空闲则入 • 否则再检查turn：保存的是较晚的一次赋值，则较晚的 进程等待，较早的进程进入－－先到先入，后到等待 选择题 • 10年27．进程P0和P1的共享变量定义 及初值为 • boolean flag[2]; • int turn = 0; • flag[0] = FALSE; flag[1] = FALSE; • 若进程P0和P1访问临界资源的类C伪代码实现如下： • void P0（ ） //进程P0 void P1（ ） //进程P1 • {while（TRUE）{ {while（TRUE）{ • flag[0] = TRUE; turn = 1; flag[1] = TRUE; turn = 0; • while（flag[1]&&（turn == 1））; while（flag[0]&&（turn == 0））; • 临界区; 临界区; • flag[0] = FALSE; flag[1] = FALSE; • } } • } } 5 选择题 • 10年27则并发执行进程P0和P1时产生的情况是 • A．不能保证进程互斥进入临界区，会出现“饥饿”现象 • B．不能保证进程互斥进入临界区，不会出现“饥饿”现象 • C．能保证进程互斥进入临界区，会出现“饥饿”现象 • D．能保证进程互斥进入临界区，不会出现“饥饿”现象 硬件TSL指令 • Entering and leaving a critical region using the TSL instruction 2.3.2 信号量机制 1. 整型信号量 最初由Dijkstra把整型信号量定义为一个整型量，仅能通 过初始化和两个标准的原子操作(Atomic Operation) wait(S)和 signal(S)来访问。两个操作被分别称为P、V操作(primitive)。 28 P 原语wait(s); down(s); P(s) z --s.count; //表示申请一个资源; if (s.count <0) //表示没有空闲资 源; { 调用进程进入等待队列 s.queue; 阻塞调用进程; } 29 V 原语signal(s); up(s); V(s) z ++s.count; //表示释放一个资源； if (s.count <= 0) //表示有进程处于 阻塞状态； { 从等待队列s.queue中取出一个进程P; 进程P进入就绪队列; } 选择题 • 10年25．设与某资源相关联的信号量初值为3， • 当前为1，若M表示该资源的可用个数， • N表示等待该资源的进程数，则M，N分别是 • A．0、1 • B．1、0 • C．1、2 • D．2、0 6 2.4 经典进程的同步问题 2.4.1 生产者—消 费者问题 1. 利用信号量解决 生产者—消费者问题 09年45．（7分）三个进程P1、P2，P3互斥使用 一个包含N（N>0）个单元的缓冲区。P1每次 用produce（）生成一个正整数并用Put（） 送入缓冲区某一空单元中；P2每次用getodd（） 从该缓冲区中取出一个奇数并用countodd（） 统计奇数个数；P3每次用geteven（）从该 缓冲区中取出一个偶数并用counteven（）统计 偶数个数。请用信号量机制实现这三个进程的 同步与互斥活动，并说明所定义信号量的含义。 要求用伪代码描述。 45．【分析】本题是生产者和消费者问题的延伸， 从生产者-消费者的原题出发，正确设置信号量， 保证进程同步和互斥的实现。考虑缓冲区是一互斥 资源，因此设互斥信号量mutex。对于同步问题： P1、P2因为奇数的放置与取用而同步，设同步 信号量odd；P1、P3因为偶数的放置于取用而同步， 设同步信号量even；P1、P2，P3因为共享缓冲区， 设同步信号量empty。 【解答】程序如下： semaphore mutex = 1，odd = 0，even = 0，empty = N； //缓冲区可用，没有放置奇数和偶数，全空，odd + even + empty = N main（） cobegin{ //并发进程 Process P1 //生产者进程 while（true） //等待调度 { number = produce（）； //生产者生产数 P（empty）； //有无空间 P（mutex）； //能否进入缓冲区 put（）； //放置数字 V（mutex）； //释放缓冲区 If number % 2 = = 0 //是否偶数 V（even）； //偶数信号量加1 else V（odd）；} //否则奇数信号量加1 【解答】程序如下： process P2 //消费者进程1 while（true） { P（odd）； //有无奇数 P（mutex）； //能否进入缓冲区 getodd（）； //取奇数 V（mutex）； //释放缓冲区 V（empty）； //空间加1 countodd（）；} //计算奇数个数 Process P3 while（true） { P（even）； //有无偶数 P（mutex）； //能否进入缓冲区 geteven（）； //取偶数 V（mutex）； //释放缓冲区 V（empty）； //空间加1 counteven（）；} //计算偶数个数 }coend //并发结束 Dining Philosophers • Philosophers eat/think • Eating needs 2 forks • Pick one fork at a time • How to prevent deadlock 2.4.2 哲学家进餐问题 7 • 让奇数号的哲学家先取右手边的筷子，让偶数号的 哲学家先取左手边的筷子。 send(i) begin if i mod 2 ==0 then else { { P(c[i]); P(c[i+1 mod 5]); P(c[i+1 mod 5]); P(c[i]); eat; eat; V(c[i+1 mod 5]); V (c[i]); V (c[i]); V(c[i+1 mod 5]); } } end 2.4.3 读者-写者问题 读者-写者问题描述 数据区 读者计数 互斥 互斥 The Readers and Writers Problem 1. 利用信号量解决读者-写者问题 睡眠的理发师问题 编程题1 • 李松和他的女朋友汪媛共享一个银行帐号，他们均可以往 里存款和提款，他们的行为可以编成程序（见例程）。李 松和汪媛可能会同时存、取款，于是可能会发生奇怪的事 件，假设李松先前已经往帐户里存了500美元，当他再往 里存100美元的同时汪媛恰好提取200美元，按程序，他 们谁都执行的同一段代码，那么，考虑不同情形，他们离 开后帐户里会变成多少美元呢？（有多种结果）如何采用 PV操作来避免上述情况的发生呢？请重新修改程序。 8 int amount = 0; { while(TRUE) { proc_save(money) { int m = 0; m = amount; m = m + money; amount = m; }; proc_drawing(money) { int m = 0; m = amount; m = m - money; amount = m; }; } } 编程题2 • 桌子上有一个盘子，只能装一只水果。爸爸弗兰克 能往里放苹果，妈妈杰西卡能往里放桔子。但是它 们必须互斥地进行。儿子汤姆只取桔子吃，女儿安 妮只取苹果吃，它们也是必须互斥操作。那么，请 写出爸爸、妈妈、儿子、女儿四个进程的正确操 作。 Shared memory(共享内存) Message(消息机制) Pipe(管道) Signal(信号) Socket(套接字) Interprocess Communication 2.5 进 程 通 信 2.6 线 程 2.6.1 线程的基本概念 1. 线程的引入 For Example 2. 线程的属性 (1)轻型实体（容易创建和撤销）。 (2) 独立调度和分派的基本单位。 (3) 可并发执行。 (4) 共享进程资源。 (5) 适应硬件的发展 9 线程表 • Items shared by all threads in a process • Items private to each thread 3. 线程的状态 (1) 状态参数。 (2) 线程运行状态。 5. 多线程OS中的进程 在多线程OS中，进程是作为拥有系统资源的基本单位， 通常的进程都包含多个线程并为它们提供资源，但此时的进 程就不再作为一个执行的实体。 多线程OS中的进程有以下 属性： (1) 作为系统资源分配的单位。 (2) 可包括多个线程。 (3) 进程不是一个可执行的实体。 4. 线程的创建和终止 2.6.2 线程间的同步和通信 1. 互斥锁(mutex) 互斥锁是一种比较简单的、用于实现线程间对资源互 斥访问的机制。 2. 条件变量 2.6.3 内核支持线程和用户级线程 1. 内核支持线程 这里所谓的内核支持线程，也都同样是在内核的支持 下运行的，即无论是用户进程中的线程，还是系统进程中 的线程，他们的创建、撤消和切换等，也是依靠内核实现 的。此外，在内核空间还为每一个内核支持线程设置了一 个线程控制块， 内核是根据该控制块而感知某线程的存 在的，并对其加以控制。 Implementing Threads in the Kernel • A threads package managed by the kernel 10 2. 用户级线程 用户级线程仅存在于用户空间中。对于这种线程的创 建、 撤消、线程之间的同步与通信等功能，都无须利用 系统调用来实现。对于用户级线程的切换，通常是发生在 一个应用进程的诸多线程之间，这时，也同样无须内核的 支持。由于切换的规则远比进程调度和切换的规则简单， 因而使线程的切换速度特别快。可见，这种线程是与内核 无关的。 Implementing Threads in User Space • A user-level threads package Hybrid Implementations • Multiplexing user-level threads onto kernel- level threads The Multithreading Revolution Q & A