第二章 进程管理.

Presentation on theme: "第二章 进程管理."— Presentation transcript:

1 第二章 进程管理

2 2.1 进程的基本概念 2.1.1 程序的顺序执行及其特征 1. 程序的顺序执行 S1: a∶=x+y; S2: b∶=a-5;
S3: c∶=b+1;

3 2.1.1 程序的顺序执行及其特征 2. 程序顺序执行时的特征 顺序性： (2) 封闭性： (3) 可再现性：

4 2.1.2 前趋图 前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。 结点：一个程序段或进程，乃至一条语句 有向边：偏序或前趋关系 把没有前趋的结点称为初始结点(Initial Node) 没有后继的结点称为终止结点(Final Node) 每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。

5 2.1.2 前趋图 前趋图中必须不存在循环

6 2.1.3 程序的并发执行及其特征 1. 程序的并发执行 使一个程序分成若干个可同时执行的程序模块（结点）的方法称为并发程序设计，能够并发执行的程序称为并发程序。

7 2.1.3 程序的并发执行及其特征 S1: a∶=x+2 1. 程序的并发执行 S2: b∶=y+4 S3: c∶=a+b
S4: d∶=c+b 1. 程序的并发执行

8 2.1.3 程序的并发执行及其特征 2. 程序并发执行时的特征 1) 间断性 2) 失去封闭性 3) 不可再现性

9 2.1.4 程序并发执行的条件（保持可再现性） 定义读集、写集 读集： 指程序 在执行期间所需参考的所有变量的集合
程序并发执行的条件（保持可再现性） 定义读集、写集 读集： 指程序 在执行期间所需参考的所有变量的集合 写集： 指程序 在执行期间要改变的所有变量的集合 Bernstein条件： 若两个程序P1和P2满足： 则程序P1和P2能并发执行，具有可再现性。 此条件也可描述为：两段程序间无共享变量或对共享变量仅有读操作

10 2.1.4 进程的特征与状态 1. 进程的特征和定义 1) 结构特征 2) 动态性 3) 并发性 进程最基本的特征
PCB 程序 数据 栈 进程控制信息 程序入口点 地址值增加 当前栈顶 分支指令 访问数据 进程映象 1. 进程的特征和定义 1) 结构特征 2) 动态性 3) 并发性 4) 独立性 5) 异步性 进程最基本的特征 由创建而产生、由调度而执行、 由撤销而消亡 进程的重要特征 也是OS的重要特征 进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位

11 进程定义： (1) 进程是程序的一次执行。 (2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 (3) 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。

12 2.1.4 进程的特征与状态 2. 进程的三种基本状态 1、Ready (runnable; temporarily stopped to let another process run) 2、Running (actually using the CPU at that instant) 3、Blocked (unable to run until some external event happens)

13 进程的三种基本状态的转换 Ready Running Blocked Scheduler picks this process
Input becomes available Ready Scheduler picks another process Running Blocked Process blocks for input

14 2.1.4 进程的特征与状态 3. 挂起状态 ★ 引入挂起状态的原因 （1）终端用户的请求。 （2）父进程请求。 （3）负荷调节的需要。
（4） 操作系统的需要。

15 2.1.4 进程的特征与状态 ★进程状态的转换 活动就绪→静止就绪。 (2) 活动阻塞→静止阻塞。 (3) 静止就绪→活动就绪。
(4) 静止阻塞→活动阻塞。

16 引入挂起状态的进程状态转换图 执行 请求I/O 调度 中断 挂起 静止就绪 活动就绪 激活 唤醒 唤醒 活动阻塞 静止阻塞 挂起 激活

17 2.1.5 进程控制块 1. 进程控制块的作用 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的 PCB是进程存在的惟一标志

18 2.1.5 进程控制块 2. 进程控制块中的信息 1) 进程标识符：进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：内部标识符、外部标识符 2) 处理机状态 3) 进程调度信息 4) 进程控制信息

19 2.1.5 进程控制块 3. 进程控制块的组织方式 1) 链接方式

20 2.1.5 进程控制块 3. 进程控制块的组织方式 2) 索引方式

21 2.2 进程控制 2.2.1 进程的创建 1. 进程图(Process Graph)

22 2.2.1 进程的创建 2. 引起创建进程的事件 用户登录。 (2) 作业调度。 (3) 提供服务。 (4) 应用请求。

23 2.2.1 进程的创建 3. 进程的创建(Creation of Progress) (1)申请空白PCB。 (2) 为新进程分配资源。
(3) 初始化进程控制块。 (4) 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程， 便将新进程插入就绪队列。

24 2.2.2 进程的终止 1. 引起进程终止(Termination of Process)的事件 ★ 正常结束 ★ 异常结束
异常事件常见的有：① 越界错误 ② 保护错 ③ 非法指令 ④ 特权指令错 ⑤ 运行超时 ⑥ 等待超时 ⑦ 算术运算错 ⑧ I/O故障

25 2.2.2 进程的终止 1. 引起进程终止(Termination of Process)的事件 ★ 外界干预
这些干预有： ① 操作员或操作系统干预 ② 父进程请求 ③ 父进程终止

26 2.2.2 进程的终止 2. 进程的终止过程 (1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
(2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。 (3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。 (4) 将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统。 (5) 将被终止进程(它的PCB)从所在队列(或链表)中移出， 等待其他程序来搜集信息。

27 2.2.3 进程的阻塞与唤醒 1. 引起进程阻塞和唤醒的事件 1) 请求系统服务 2) 启动某种操作 3) 新数据尚未到达
4) 无新工作可做

28 2.2.3 进程的阻塞与唤醒 2. 进程阻塞过程 进程的阻塞是进程自身的一种主动行为。
a、先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列 b、转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。

29 2.2.3 进程的阻塞与唤醒 3. 进程唤醒过程 a、首先把被阻塞的进程从等待该事件的阻塞队列中移出
b、将其PCB中的现行状态由阻塞改为就绪 c、将该PCB插入到就绪队列中 d、进程调度或返回

30 2.2.4 进程的挂起与激活 1. 进程的挂起 首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。 2. 进程的激活过程 先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。

31 2.3 进程同步 2.3.1 进程同步的基本概念 1. 两种形式的制约关系 间接相互制约关系(资源共享关系)
(2) 直接相互制约关系（相互合作关系）

32 2.3.1 进程同步的基本概念 2. 临界资源(Critical Resource) 临界资源：一次只允许一个进程访问的资源

33 2.3.1 进程同步的基本概念 2. 临界资源(Critical Resource)
生产者-消费者(producer-consumer)问题： 同步关系：不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

34 2.3.1 进程同步的基本概念 2. 临界资源(Critical Resource) int n; int item;
空 … 消息1 消息2 消息n 消息 ↑ out in n-1 int n; int item; int count=0;

35 2.3.1 进程同步的基本概念 2. 临界资源(Critical Resource) 可能出现的情况：
生产时——count＝n，无多余buffer可用 消费时——count＝0；无消息可用

36 2.3.1 进程同步的基本概念 2. 临界资源(Critical Resource) int n=100,count=0;
void producer(void) { int item; while (TRUE) { produce_item(&item); //generate next item if (count==n) sleep(); //if buffer is full, go to sleep enter_item(item); //put item in buffer count=count+1; //increment count of item in buffer if (count==1) wakeup(consumer) //was buffer empty? }

37 2.3.1 进程同步的基本概念 2. 临界资源(Critical Resource) void consumer(void) {
int item; while (TRUE) { if (count==0) sleep(); //if buffer is empty, go to sleep remove_item(item); //take item out of buffer count=count-1; //decrement count of item in buffer if (count==n-1) wakeup(producer); //was buffer full? consume_item(item); //print etem }

38 2.3.1 进程同步的基本概念 2. 临界资源(Critical Resource) 执行顺序： 1、buffer空，即count＝0；
void producer(void) { int item; while (TRUE) { produce_item(&item); if (count==n) sleep(); enter_item(item); count=count+1; if (count==1) wakeup(consumer) } void consumer(void) { int item; while (TRUE) { if (count==0) sleep(); remove_item(item); count=count-1; if (count==n-1) wakeup(producer); consume_item(item); } 2.3.1 进程同步的基本概念 2. 临界资源(Critical Resource) 执行顺序： 1、buffer空，即count＝0； 2、consumer读取count的值，准备判断其是否为0 3、进程调度，执行producer，产生item放入buffer，使count加1；则count＝1； 4、producer判断count＝＝1，唤醒consumer，由于consumer并没有sleep，故唤醒信号无效； 5、进程调度，consumer继续执行，发现调度前读取的count值为0，sleep； 6、producer执行，buffer迟早要满，从而sleep 7、两个进程永远sleep，不再执行

39 2.3.1 进程同步的基本概念 竞争条件(Race Conditions)
Situations like this, where two or more processes are reading or writing some shared data and the final result depends on who runs precisely when, are called race conditions.

40 2.3.1 进程同步的基本概念 3. 临界区(critical section) 临界区（CS）：进程中访问临界资源的那段代码
(The part of the program where the shared memory is accessed is called the critical section)

41 2.3.1 进程同步的基本概念 entry section 3. 临界区(critical section) exit section
可把一个访问临界资源的循环进程描述如下： repeat critical section;  remainder section; until false; entry section exit section

42 2.3.1 进程同步的基本概念 4. 同步机制应遵循的规则 空闲让进。 (2) 忙则等待。 (3) 有限等待。 (4) 让权等待。

43 互斥与同步解决方法（软件方法） Dekker算法、Peterson算法

44 Dekker算法 ★初步设想 定义全局变量turn，值0、1分别标志进程P0和P1可以进入CS： ◆turn=0：P0可以进入CS

45 Dekker算法 ★初步设想 bool turn; /*共享的全局变量，BOOL类型*/ P0 P1 … …
… … while turn≠0 do {nothing} while turn≠1 do {nothing} <CS> <CS> turn=1; turn=0; … … 忙等 busy waiting

46 Dekker算法 ★初步设想 问题： ◆进程严格交替进入临界区。当turn=0时，P1必须等待P0进入CS执行，退出后，才能进入CS；即使此时CS空闲，不符合空闲让进 ◆任何进程在CS内或外失败，其它进程将可能因为等待使用CS而无法向前推进

47 Dekker算法 ★改进1 使用全局共享数组flag标志CS状态： ◆flag[0]或flag[1]=ture：表示P0或P1占用CS
◆flag[0]或flag[1]=false：表示CS空闲

48 Dekker算法 ★改进1 bool flag[2]; /*共享的全局数组，BOOL类型*/ P0 P1 … …
… … while flag[1] do {nothing} while flag[0] do {nothing} flag[0]=true; flag[1]=ture; <CS> <CS> flag[0]=false; flag[1]=false; … …

49 设flag[0]=flag[1]=false 都可进入CS，不能实现互斥，违背忙则等待
Dekker算法 设flag[0]=flag[1]=false ★改进1 bool flag[2]; /*共享的全局数组，BOOL类型*/ P0 P1 … … while flag[1] do {nothing} while flag[0] do {nothing} flag[0]=true; flag[1]=ture; <CS> <CS> flag[0]=false; flag[1]=false; … … 问题： ◆进程在CS内失败且相应的flag=ture，则其它进程永久阻塞 ◆不能实现互斥，如执行顺序: 都可进入CS，不能实现互斥，违背忙则等待

50 Dekker算法 ★改进2 改进1：先检测CS状态 改为先置标志位

51 Dekker算法 ★改进2 bool flag[2]; /*共享的全局数组，BOOL类型*/ P0 P1 … …
… … flag[0]=true; flag[1]=ture; while flag[1] do {nothing} while flag[0] do {nothing} <CS> <CS> flag[0]=false; flag[1]=false; … …

52 Dekker算法 ★改进2 bool flag[2]; /*共享的全局数组，BOOL类型*/ 问题： P0 P1 … …
… … flag[0]=true; flag[1]=ture; while flag[1] do {nothing} while flag[0] do {nothing} <CS> <CS> flag[0]=false; flag[1]=false; … … 问题： ◆不能实现有空让进，有限等待，如执行顺序: 忙等 忙等 都无法进入CS

53 Dekker算法 ★结合初步设想和改进2，得到成功的Dekker算法，P0的执行流程 flag[0]=ture flag[1] P0进入CS
P0进入CS 1 turn 退出CS 1 turn=1 flag[0]=false flag[0]=false turn 其余代码 1 flag[0]=ture

54 Peterson算法 ★代码更简洁。 两个全局共享变量：flag[0]、flag[1]——表示临界区状态及哪个进程正在占用CS
全局共享变量turn：表示能进入CS的进程序号

55 当flag[1]=false或turn＝0，即当进程1没有要求进入CS，或仅允许进程0进入CS时，P0进入CS
Peterson算法 bool flag[2],turn; /*共享的全局数组，BOOL类型*/ P0 P1 … … flag[0]=true; flag[1]=ture; turn=1; turn=0; while (flag[1]&&turn==1) while (flag[0]&&turn==0) do {nothing} do {nothing} <CS> <CS> flag[0]=false; flag[1]=false; … … 当flag[1]=false或turn＝0，即当进程1没有要求进入CS，或仅允许进程0进入CS时，P0进入CS

56 2.3.2 信号量机制 1. 整型信号量 原子操作(Atomic Operation)：wait(S)和signal(S)
这两个操作一直被分别称为P、V操作 wait(S): while S≤0 sleep()； S=S-1; signal(S): S=S+1;

57 信号量机制解决生产－消费者问题 必须成对出现 #define N 100 typedef int semaphore;
semaphore mutex=1; //controls access to critical semaphore empty=N; //counts empty buffer slots semaphore full=0; //counts full buffer slots void producer(void) { int item; while (TRUE) { produce_item(&item); //generate next item to put in buffer wait(empty); //decrement empty count wait(mutex); //enter critical region enter_item(item); //put new item in buffer signal(mutex); //leave CS signal(full); //increment count of full slots }} 必须成对出现

58 信号量机制解决生产－消费者问题 void consumer(void) { int item; while (TRUE) {
wait(full); //decrement full count wait(mutex); //enter critical region remove_item(&item); //take item from buffer signal(mutex); //leave CS signal(empty); //increment count of empty slots consume_item(item); //do something with the item }

59 信号量实现前驱关系 a b c d e f g Var a,b,c,d,e,f,g; semaphore∶=0,0,0,0,0,0,0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; parend end

60 2.3.2 信号量机制 2. 记录型信号量 为解决整型信号量“忙等”问题提出的。 两个数据项 typedef struct{
int value; //某类资源的数目 L; //信号量链表 }semaphore

61 2. 记录型信号量 相应地，wait(S)和signal(S)操作可描述为： wait(S){ semaphore S; S.value=S.value-1; if S.value＜0 block(S.L) } signal(S){ S.value=S.value+1; if S.value≤0 wakeup(S.L);

62 2.3.2 信号量机制 3. AND型信号量 针对进程需共享多个临界资源
AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。 （AND同步，或称为同时wait操作）

63 AND信号量机制解决生产－消费者问题 #define N 100 typedef int semaphore;
semaphore mutex=1, empty=N, full=0; int in=0, out=0; void producer(void) { int nextp; while (TRUE) { produce_item(nextp); //generate next item to put in buffer Swait(empty,mutex); buffer[in]=nextp; in=(in+1) mod N; Ssignal(mutex,full); }

64 AND信号量机制解决生产－消费者问题 void consumer(void) { int nextc; while (TRUE) {
Swait(full,mutex); nextc=buffer(out); out=(out+1) mod N; Ssignal(mutex,empty); consume_item(nexpc); }

65 2.3.2 信号量机制 4. 信号量集 设置阈值，资源数大于阈值，则分配资源，小于阈值，则不予分配

66 4. 信号量集 一般“信号量集”的几种特殊情况： (1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。 (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S＞1时)或互斥信号量(S=1时)。 (3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

67 2.4 经典进程的同步问题 2.4.1 生产者—消费者问题

68 2.4.2 哲学家进餐问题 1. 问题描述 问题描述：5个哲学家，5只碗、5只筷子

69 利用记录型信号量解决哲学家进餐问题 筷子——五个信号量构成信号量数组： semaphore chopstick[4];

70 #define N 5 //number of philosophers
viod philosopher(int i) //i: which philosopher(0 to N-1) {while(ture){ think(); //philosopher is thinking wait(chopstick[i]); //take left chopstick wait(chopstick[i+1] %5); //take right chopstick eat(); signal(chopstick[i]); //put left chopstick back on the table signal(chopstick[i+1] %5);//put right chopstick back on the table }

71 存在的问题 死锁——五位哲学家同时饥饿而各自拿起左边的筷子

72 解决方法 (1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。 (2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。  (3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、 2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。

73 解决方法（例） 思路： 1、哲学家状态数组：state——表示哲学家当前状态：吃、思考、饥饿（准备拿筷子）
2、哲学家进入吃状态的前提——其邻居（左右）哲学家均不在吃的状态

74 代码： #define N 5 //number of philosophers
#define LEFT (i-1)%N //number of i’s left neighbor #define RIGHT (i+1)%N //number of i’s right neighbor #define THINKING 0 // philosopher is thinking #define HUNGRY // philosopher is trying to get chopstick #define EATING // philosopher is eating int state[N]; //to keep track of everyone’s state semaphore mutex=1; //mutual exclusion for CS semaphore s[N]; //one semaphore per philosopher

75 代码： void take_chopstick(int i)//i: which philosopher (0 to N-1) {
wait(mutex); //enter CS state[i]=HUNGRY;//recode fact that philosopher i is hungry test(i); //try to acquire 2 chopsticks signal(mutex); //exit CS wait(s[i]); //block if chopstick were not acquired } 代码： void philosopher(int i) //i: which philosopher (0 to N-1) {while (TURE){ think(); // philosopher is thinking take_chopstick(i); //acquire two chopsticks or block eat(); put_chopstick(i); //put both chopsticks back on table } void test(int i)//i: which philosopher (0 to N-1) { if (state[i]==HUNGRY &&state[LEFT]!=EATING && state[RIGHT]!=EATING){ state[i]=EATING; signal(s[i]); } void put_chopstick(int i)//i: which philosopher (0 to N-1) { wait(mutex); //enter CS state[i]=THINKING;//philosopher i has finished eating test(LEFT); //see if left neighbor can now eat test(RIGHT); //see if right neighbor can now eat signal(mutex); //exit CS }

76 利用AND信号量机制解决哲学家进餐问题 semaphore chopstick[4]; void philosopher(int i)
{while(TURE){ think(); Sswait(chopstick[(i+1) %5], chopstick[i]); eat(); Ssignat(chopstick[(i+1) % 5], chopstick[i]); }

77 2.5 管程机制 2.5.1 管程(monitor)的基本概念 1. 管程的定义
定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据 A monitor is a collection of procedures, variables, and data structures that are all grouped together in a special kind of module or package.

78 2.5.1 管程的基本概念 1. 管程的定义 管程由三部分组成： ① 局部于管程的共享变量说明； ② 对该数据结构进行操作的一组过程；
③ 对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。

79 管程的语法 type monitor-name=monitor variable declarations
procedure entry P1(…); begin … end; procedure entry P2(…);  … procedure entry Pn(…); begin initialization code; end

80 说明 1、目前、并发Pascal、Pascal_Plus、Modula－2、Java等程序设计语言支持管程机制 2、管程本身被作为一种临界区，实现管程时，需考虑互斥、同步和控制变量等问题 3、进程可在任何需要的地方调用管程中的过程，但不能在管程外直接访问管程内的数据结构 4、任何时刻，管程中只能有一个活跃进程。管程的互斥操作通常由编译程序支持，编译时自动为每个管程建立一个初值为1的互斥信号量

81 说明 5、管程实现进程同步，是指在管程中设置一对同步操作原语，wait和signal。与作用于信号量的wait和signal不同的是，管程中的wait和signal作用于条件变量。条件变量不具有累加功能，如果管程中的进程发出一个信号量，却没有在对应的条件变量上对应的条件变量上等待，则该信号量没有作用，会丢失。 6、进程阻塞等待的原因很多，为区别，设置不同的条件变量，将因为不同时间阻塞的进程组织在不同的队列中 7、当一个进程利用管程申请资源而不同满足时，将调用wait原语阻塞自己，并进入相应阻塞队列。当某进程释放出一个临界资源，将用signal原语唤醒等待在该临界资源上的一个阻塞进程 8、目前常用的操作系统很少采用管程机制实现进程的互斥于同步

82 2.5.2 利用管程解决生产者-消费者问题 建立管程——Proclucer-Consumer, 或简称为PC。 两个过程：
(1) put(item)过程 (2) get(item)过程

83 type producer-consumer=monitor
Var in,out,count:integer; buffer:array［0,…,n-1］ of item; notfull, notempty:condition; procedure entry put(item) begin if count≥n then notfull.wait; buffer(in)∶ =nextp; in∶ =(in+1) mod n; count∶ =count+1; if notempty.queue then notempty.signal; end 条件变量

84 procedure entry get(item)
begin if count≤0 then notempty.wait; nextc∶ =buffer(out); out∶ =(out+1) mod n; count∶ =count-1; if notfull.quene then notfull.signal; end begin in∶ =out∶ =0; count∶ =0 end 变量初始化

85 则生产者和消费者可描述为： producer:begin repeat produce an item in nextp;
PC.put(item); until false; end consumer:begin PC.get(item); consume the item in nextc; end

86 Interprocess Communication
2.6 进程通信 进程通信IPC：进程间的信息交换。 进程通信：低级进程通信、高级进程通信 低级进程通信：少量的信息交换，没有专门的通信机制，如信号量机制 缺点：效率低，通信对用户不透明 高级进程通信：大量的信息交换，有专门的通信机制，通信对用户透明

87 2.6.1 进程通信的类型 1. 共享存储器系统(Shared-Memory System) 基于共享数据结构的通信方式。
缺点：低效、适合传递少量数据 (2) 基于共享存储区的通信方式。

88 2.6.1 进程通信的类型 2. 消息传递系统(Message passing system)
直接通信方式、间接通信方式

89 2.6.1 进程通信的类型 3. 管道(Pipe)通信 所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。

90 Unix中的管道 创建管道 #include <unistd.h> int pipe(int fd[2]);
返回两个文件描述字：fd[0]用于打开来读，fd[1]用于打开来写

91 Unix中的管道 单个进程中的通道 管道由单个进程创建，但很少在单个进程中使用

92 典型用途 Unix中的管道 1、单个进程创建管道后，调用fork派生子进程

93 典型用途 Unix中的管道 2、父进程关闭管道的读出端，子进程关闭同一管道的写入端。从而在父子进程提供了一个单向数据流

94 例 Unix中的管道 命令： who|sort|lp

95 Unix中的管道 半双工管道、全双工管道

96 3. 管道(Pipe)通信 协调 ① 互斥：读时不写、写时不读 ② 同步：协调读写速度等问题 ③ 确定对方是否存在，只有确定了对方已存在时，才能进行通信

97 2.6.2 消息传递通信的实现方法 1. 直接通信方式 原语：
Send(Receiver, message); 发送一个消息给接收进程； Receive(Sender, message); 接收Sender发来的消息。 注：原语SEND、RECEIVE和信号量类似，为系统调用 管程monitor是由编程语言构造和设计

98 直接消息传递通信的解决生产－消费者问题 void producer(void) { int item;
message m; //message buffer while (TRUE) { produce_item(item); //generate next item to put in buffer build_message(m,item); //construct a message to send send(consumer,m); //send item to consumer }

99 直接消息传递通信的解决生产－消费者问题 void consumer(void) { int item;
message m; //message buffer while (TRUE) { receive(producer,m); //get message containing item extract_item(m,item); //take item out of message consumer_item(item); //do something with item }

100 2. 间接通信方式 利用信箱传递消息 (1) 信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性(公用、私用或共享)；对于共享信箱， 还应给出共享者的名字。当进程不再需要读信箱时，可用信箱撤消原语将之撤消

101 2. 间接通信方式 (2) 消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利用系统提供的下述通信原语进行通信。 Send(mailbox, message); 将一个消息发送到指定信箱； Receive(mailbox, message); 从指定信箱中接收一个消息；

102 2. 间接通信方式 信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类： 1) 私用信箱 用户进程建立一个新信箱，并作为该进程的一部分 只有信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中 可采用单向通信链路的信箱来实现 拥有该信箱的进程结束时，信箱也随之消失。

103 信箱类型 2) 公用信箱 由操作系统创建，并提供给系统中的所有核准进程使用 核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息 公用信箱应采用双向通信链路的信箱来实现 通常，公用信箱在系统运行期间始终存在

104 信箱类型 3) 共享信箱 它由某进程创建，在创建时或创建后，指明它是可共享的，同时须指出共享进程(用户)的名字 信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。

105 2. 间接通信方式 发送进程与接收进程的关系： (1) 一对一 (2) 多对一，也称为客户/服务器交互(client/server interaction)。 (3) 一对多，可用广播方式，向接收者(多个)发送消息。 (4) 多对多

106 2.6.3 消息传递系统实现中的若干问题 1. 通信链路(communication link) 建链方式：
显式建链：通信前建链，通信后拆链 隐式建链：无须专门建链操作

107 1. 通信链路(communication link)
根据通信链路的连接方法，又可把通信链路分为两类： ① 点—点连接通信链路， ② 多点连接链路 而根据通信方式的不同，则又可把链路分成两种： ① 单向通信链路 ② 双向链路

108 2. 消息的格式 定长消息格式 变长消息格式

109 3. 进程同步方式 发送进程阻塞、 接收进程阻塞。 (2) 发送进程不阻塞、 接收进程阻塞。 (3) 发送进程和接收进程均不阻塞。

110 2.6.4 消息缓冲队列通信机制 1. 消息缓冲队列通信机制中的数据结构
(1) 消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下： type message buffer=record sender; 发送者进程标识符 size; 消息长度 text; 消息正文 next; 指向下一个消息缓冲区的指针 end

111 1. 消息缓冲队列通信机制中的数据结构 (2) PCB中有关通信的数据项 在PCB中应增加的数据项可描述如下： type processcontrol block=record … mq; 消息队列队首指针 mutex; 消息队列互斥信号量 sm; 消息队列资源信号量 end

112 2. 发送原语 procedure send(receiver, a) begin
getbuf(a.size,i); 根据a.size申请缓冲区； i.sender∶ =a.sender; 将发送区a中的信息复制到消息缓冲区之中 i.size∶ =a.size; i.text∶ =a.text; i.next∶ =0; getid(PCB set, receiver.j); 获得接收进程内部标识符； wait(j.mutex); insert(j.mq, i); 将消息缓冲区插入消息队列； signal(j.mutex); signal(j.sm); end

113 2. 发送原语

114 3. 接收原语 procedure receive(b) begin
j∶ =internal name; j为接收进程内部的标识符； wait(j.sm); wait(j.mutex); remove(j.mq, i); 将消息队列中第一个消息移出； signal(j.mutex); b.sender∶ =i.sender; 将消息缓冲区i中的信息复制到接收区b b.size∶ =i.size; b.text∶ =i.text; end

115 2.7 线程 2.7.1 线程的基本概念 进程的基本属性： 1、是一个可拥有资源的独立单位 2、是一个可独立调度和分派的基本单位

116 2.7.1 线程的基本概念 为使程序能并发执行，系统还必须进行以下的一系列操作。 1) 创建进程 2) 撤消进程 3) 进程切换 

117 2.7.1 线程的基本概念 2. 线程的属性 轻型实体：基本上不拥有资源 (2) 独立调度和分派的基本单位。 (3) 可并发执行。
(4) 共享进程资源。

118 线程与进程的比较 (1) 调度 传统操作系统：进程既是拥有资源的基本单位，又是独立调度的基本单位
引入线程的OS：线程是独立调度的基本单位，进程是资源拥有的基本单位。（同一进程中线程的切换不会引起进程切换，当一个进程中的线程切换到另一个进程中的线程，引起进程切换

119 线程与进程的比较 (2) 并发性 引入线程的OS：进程之间可并发执行，同属于一个进程的多个线程之间亦可并发执行 (3) 拥有资源
进程是拥有资源的独立单位，有权申请系统的各类资源。线程除了拥有很少私有资源外，不能申请系统资源，但可共享其所属进程的资源。 (4) 系统开销 创建或撤销进程所需开销大于创建或撤销线程所需开销

120 3. 线程的运行状态 ① 执行状态 ② 就绪状态 ③ 阻塞状态

121 5. 多线程OS中的进程 在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。 多线程OS中的进程有以下属性： (1) 作为系统资源分配的单位。 (2) 可包括多个线程。 (3) 进程不是一个可执行的实体。

122 2.7.2 线程间的同步和通信 1. 互斥锁(mutex) 互斥锁的状态：开锁(unlock)和关锁(lock) 2. 条件变量
3. 信号量机制

123 2.7.3 内核支持线程和用户级线程 1. 内核支持线程 2. 用户级线程

124 附录：Windows2000/XP的进程和线程管理
a、Windows2000/XP的进程对象 Windows 2000/XP的进程是系统中分配资源的基本单位，具有3个重要特征 ◆进程作为对象来控制和管理 ◆一个进程可以包含一个或多个线程 ◆进程对象和线程对象具有内置的同步功能

125 a、Windows2000/XP的进程对象 Windows 2000/XP的进程用对象表示，可以通过句柄（handle）来引用对象，结构如图
对象类型 进程 进程ID 安全描述符 基本优先级 默认处理器集合 定额限制 执行时间 I/O计数器 VM操作计数器 异常/调试端口 退出状态 创建进程 打开进程 查询进程信息 设置进程信息 当前进程 终止进程 a、Windows2000/XP的进程对象 进程的唯一标志 描述谁创建对象、谁可以访问/使用对象或禁止谁访问对象 Windows 2000/XP的进程用对象表示，可以通过句柄（handle）来引用对象，结构如图 进程中线程的基本优先级 可以运行的进程中线程的默认处理器集合 对象体属性 页式存储器及页式文件空间，进程可使用的处理器最大时间 进程中所有线程已经执行的时间总量 记载进程中线程已执行的I/O操作数量、类型的变量 记载进程中线程已执行的虚拟存储器操作数量、类型的变量 进程中的线程异常时，用于进程管理器发送消息的通信信道 进程终止的原因 服务

126 b、Windows2000/XP的进程TDB（任务数据库）
Windows 2000/XP启动一个进程时，将为其建立一个类似于PCB的结构，如图 私有堆栈 链接指针 状态标志(事件计数) 优先级 …… 每个进程都有自己的堆栈 指向系统中下一个进程的TDB 标志一个进程阻塞还是就绪状态 用于调度

127 2、Windows2000/XP的线程 a、Windows2000/XP的线程对象
Windows 2000/XP的一个进程至少包含一个执行线程，该线程还可以创建新的线程。 Windows 2000/XP的线程属于内核级线程，系统以线程为调度单位

128 a、Windows2000/XP的线程对象 线程 线程ID 线程上下文 动态优先权 基本优先级 线程处理器集合 线程执行时间 警告状态
对象类型 线程 线程ID 线程上下文 动态优先权 基本优先级 线程处理器集合 线程执行时间 警告状态 挂起计数器 假冒标志 线程退出状态 创建线程 打开线程 查询线程信息 设置线程信息 当前进程 终止进程 ...... a、Windows2000/XP的线程对象 当线程调用一个服务程序时，标志该线程的唯一值 定义线程执行状态的一组寄存器值和其它易失的数据 任何给定时刻，线程执行优先级 线程动态优先级的下限 对象体属性 可以运行的线程的处理器集合 线程在用户模式和内核模式下执行的时间总量 表示线程是否将执行一个异步过程调用的标志 记载线程被挂起的次数（但未恢复） 允许线程代表另一进程执行的临时访问标志（供子系统使用） 线程终止的原因 服务

129 已选择好线程的执行处理机，正等待描述表切换，以进入运行状态。系统中每个处理机只能有一个处于备用状态的线程
线程创建过程中的状态 已完成描述表切换，进入运行状态 b、Windows2000/XP的线程状态 线程已获得除处理机外的所需资源，正等待调度执行 备用 创建并初始化 终止 初始化 选择执行 描述表切换 抢先 完成 接纳 线程正等待某对象，以同步线程的执行 抢先或时间片完完 就绪 运行 换入的内核堆栈 等待完成 等待完成 等待对象句柄 换出的内核堆栈 转换 等待 与就绪状态类似，但线程的内核堆栈位于外存

130 c、Windows2000/XP的线程控制 Windows 2000/XP提供了一组用于线程控制的系统调用：
★CreateThread：完成线程创建，在调用进程的地址空间上创建一个线程，以执行指定的函数，返回值为所创建线程的句柄 ★ExitThread：结束当前线程 ★SuspendThread：挂起指定的线程 ★ResumeThread：激活指定线程，其对应操作是递减指定线程的挂起计数。当挂起计数减为0时，线程恢复执行

131 允许线程连续运行的最大时间长度，即时间片
d、Windows2000/XP的线程调度 Windows 2000/XP的调度对象为线程。采用严格的抢先动态优先级调度，根据优先级和分配时间配额(quantum)进行调度。 Windows 32中与线程调度相关的API函数： ★Suspend/ResumeThread：挂起/激活一个正在/暂停运行的线程 ★Get/SetPriorityClass：读/设置一个线程的基本优先级类型 ★Get/SetThreadPriority：读/设置一个线程的相对优先级 ★Get/SetProcessPriorityBoost：读/设置当前进程的默认优先级提升控制

132 3、Windows2000/XP的进程互斥和同步 Windows 2000/XP的提供了互斥对象、信号量对象和事件对象等3种同步对象和系统调用，用于进程和线程同步 可实现线程互斥的对象，相当于互斥信号量

133 a、用于互锁变量访问的API函数 ★InterlockedExchange：进行32位数据的先读后写原子操作
★InterlockedExchangePointer：对指针的Exchange原子操作 ★InterlockedCompareExchange：依据比较结果进行赋值的原子操作 ★InterlockedCompareExchangePointer：对战争的CompareExchange原子操作 ★InterlockedExchangeAdd：先加后存结果的原子操作 ★InterlockedDecrement：先减1后存结果的原子操作 ★InterlockedIncrement：先加1后存结果的原子操作

134 b、与互斥对象有关的API函数 ★CreateMutex：创建一个互斥对象，返回对象句柄
★OpenMutex：返回一个已存在的互斥对象句柄，用于后续访问 ★ReleaseMutex：释放对互斥对象的占用，使之成为可用

135 c、与临界区对象有关的API函数 ★InitializeCriticalSection：对临界区对象进行初始化
★EnterCriticalSection：等待占用临界区的使用权，得到使用权时返回 ★TryEnterCriticalSection：非等待方式申请临界区的使用权；申请失败返回0 ★LeaveCriticalSection：释放临界区的使用权 ★DeleteCriticalSection：释放与临界区对象相关的所有系统资源

136 d、与事件对象有关的API函数 事件对象相当于触发器，可以通知一个或多个线程某事件的出现。 API函数：
★CreateEvent：创建事件对象，返回对象句柄 ★OpenEvent：返回一个已存在的时间对象句柄，用于后续访问 ★SetEvent/PulseEvent：设置指定事件对象为可用状态 ★ResetEvent：设置指定事件对象为不可用状态

137 4、Windows2000/XP的进程间通信 ★提供软中断－信号通信方式
★基于文件映射的共享存储区（CreateFileMapping、OpenFileMapping) ★提供无名管道和命名管道两种管道机制（CreatePipe创建无名管道后，利用ReadFile和WriteFile进行无名管道的读写；命名管道为服务器与客户进程间提供通信通道：CreateNamedPipe在服务器创建并返回一个命名管道句柄、ConnectNamedPipe在服务器端等待客户进程的请求、CallNamedPipe从客户进程建立与服务器的管道连接 ★邮件槽：类似邮箱通信，通常采用client/server模式 ★套接字：网络通信机制 ★剪贴板Clipboard：一种信息交流方式，可增强进程的信息交流能力，帮助进程之间按照约定格式交流复杂信息：OpenCilpboard、CloseClipboard、EmptyClipboard、SetCilpboardData、GetClipboardData、RsgisterClipboardFormat