清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 第3章进程管理 31进程的概念 32进程的描述 33进程状态及其转换 34进程控制 35进程互厍 36进程同步 37进程通信 38死锁问题 39线程 本章小结 习题
第3章 进程管理 3.1 进程的概念 3.2 进程的描述 3.3 进程状态及其转换 3.4 进程控制 3.5 进程互斥 3.6 进程同步 3.7 进程通信 3.8 死锁问题 3.9 线程 本章小结 习题
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 31进程的概念 现代操作系统的重要特点是程序的并发执行,及系 统所拥有的资源被共享和系统的用户随机地使用。 这三个特点是互相联系和互相依赖的,它们是互相 独立的用户如何使用有限的计算机系统资源的反映。 通常,操作系统的重要任务之一是使用户充分、有 效地利用系统资源。采用一个什么样的概念,来描 述计算机程序的执行过程和作为资源分配的基本单 位才能充分反映操作系统的执行并发、资源共享及 用户随机的特点呢?这个概念就是进程。为了讲清 进程的概念,以及引入进程概念的必要性等,下面 将从操作系统的特点讲起
3.1 进程的概念 现代操作系统的重要特点是程序的并发执行，及系 统所拥有的资源被共享和系统的用户随机地使用。 这三个特点是互相联系和互相依赖的，它们是互相 独立的用户如何使用有限的计算机系统资源的反映。 通常，操作系统的重要任务之一是使用户充分、有 效地利用系统资源。采用一个什么样的概念，来描 述计算机程序的执行过程和作为资源分配的基本单 位才能充分反映操作系统的执行并发、资源共享及 用户随机的特点呢？这个概念就是进程。为了讲清 进程的概念，以及引入进程概念的必要性等，下面 将从操作系统的特点讲起
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 311程序的并发执行 1.程序的顺序执行 程序是一个在时间上按严格次序前后相继的操作序 列,是一个静态的概念。程序体现了编程人员要求 计算机完成所要求功能时所应该采取的顺序步骤。 显然,一个程序只有经过执行才能得到最终结果, 且一般用户在编写程序时不考虑在自己的程序执行 过程中还有其他用户程序存在这一事实。另外,计 算机CPU是通过时序脉冲来控制顺序执行指令的。 其执行过程可以描述为: Repeat ir←M[pc pC←pc+1 Execute(instruction in IR)) Until cpu halt
3.1.1 程序的并发执行 1. 程序的顺序执行 程序是一个在时间上按严格次序前后相继的操作序 列，是一个静态的概念。程序体现了编程人员要求 计算机完成所要求功能时所应该采取的顺序步骤。 显然，一个程序只有经过执行才能得到最终结果， 且一般用户在编写程序时不考虑在自己的程序执行 过程中还有其他用户程序存在这一事实。另外，计 算机 CPU是通过时序脉冲来控制顺序执行指令的。 其执行过程可以描述为： Repeat IR ← M ［pc］ pc ← pc+1 〈 Execute (instruction in IR)〉 Until CPU halt
000000000 这里R为指令寄存器,p为程序计数器,M为存储 器。显然,程序的顺序性与计算机硬件的顺序性是 致的。我们把一个具有独立功能的程序独占处理 机直至最终结束的过程称为程序的顺序执行。程序 的顺序执行具有如下特点: (1)顺序性 程序顺序执行时,其执行过程可看作一系列严格按 程序规定的状态转移过程。 (2)封闭性 程序执行得到的最终结果由给定的初始条件决定, 不受外界因素的影响。 (3)可再现性 只要输入的初始条件相同,则无论何时重复执行该 程序都会得到相同的结果
这里IR为指令寄存器，pc为程序计数器，M为存储 器。显然，程序的顺序性与计算机硬件的顺序性是 一致的。我们把一个具有独立功能的程序独占处理 机直至最终结束的过程称为程序的顺序执行。程序 的顺序执行具有如下特点： (1) 顺序性 程序顺序执行时，其执行过程可看作一系列严格按 程序规定的状态转移过程。 (2) 封闭性 程序执行得到的最终结果由给定的初始条件决定， 不受外界因素的影响。 (3) 可再现性 只要输入的初始条件相同，则无论何时重复执行该 程序都会得到相同的结果
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 2.多道程序系统中程序执行环境的变化 在许多情况下,需要计算机能够同时处理多个具有 独立功能的程序。批处理系统、分时系统、实时系 统以及网络与分布式系统等都是这样的系统。这样 的执行环境具有下述三个特点: (1)独立性 每道程序都是逻辑上独立的,它们之间不存在逻辑 上的制约关系。 (2)随机性 在多道程序环境下,特别是在多用户环境下,程序 和数据的输入与执行开始时间都是随机的。 (3)资源共享 资源共享将导致对进程执行速度的制约
2. 多道程序系统中程序执行环境的变化 在许多情况下，需要计算机能够同时处理多个具有 独立功能的程序。批处理系统、分时系统、实时系 统以及网络与分布式系统等都是这样的系统。这样 的执行环境具有下述三个特点： (1) 独立性 每道程序都是逻辑上独立的，它们之间不存在逻辑 上的制约关系。 (2) 随机性 在多道程序环境下，特别是在多用户环境下，程序 和数据的输入与执行开始时间都是随机的。 (3) 资源共享 资源共享将导致对进程执行速度的制约
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 3.程序的并发执行 (1)什么是程序的并发执行 所谓并发执行,是为了增强计算机系统的处理能力 和提高资源利用率所采取的一种同时操作技术。程 序的并发执行可进一步分为两种:第一种是多道程 序系统的程序执行环境变化所引起的多道程序的并 发执行。由于资源的有限性,多道程序的并发执行 总是伴随着资源的共享与竞争。从而制约各道程序 的执行速度。而无法作到在微观上,也就是在指令 级上的同时执行。因此,尽管多道程序的并发执行 在宏观上是同时进行的,但在微观上仍是顺序执行 的;第二种并发执行是在某道程序的几个程序段中 (例如几个程序),包含着一部分可以同时执行或 顺序颠倒执行的代码。例如语句:
3. 程序的并发执行 (1) 什么是程序的并发执行 所谓并发执行，是为了增强计算机系统的处理能力 和提高资源利用率所采取的一种同时操作技术。程 序的并发执行可进一步分为两种：第一种是多道程 序系统的程序执行环境变化所引起的多道程序的并 发执行。由于资源的有限性，多道程序的并发执行 总是伴随着资源的共享与竞争。从而制约各道程序 的执行速度。而无法作到在微观上，也就是在指令 级上的同时执行。因此，尽管多道程序的并发执行 在宏观上是同时进行的，但在微观上仍是顺序执行 的；第二种并发执行是在某道程序的几个程序段中 （例如几个程序），包含着一部分可以同时执行或 顺序颠倒执行的代码。例如语句：
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS read(a); read (b); 它们既可以同时执行,也可颠倒次序执行。对于这 样的语句,同时执行不会改变顺序程序所具有的逻 辑性质。因此,可以采用并发执行来充分利用系统 资源以提高计算机的处理能力。 程序的并发执行可总结为:一组在逻辑上互相独立 的程序或程序段在执行过程中,其执行时间在客观 上互相重叠,即一个程序段的执行尚未结束,另 个程序段的执行已经开始的这种执行方式。 程序的并发执行不同于程序的并行执行。程序的并 行执行是指一组程序按独立的、异步的速度执行。 并行执行不等于时间上的重叠。可以将并发执行过 程描述为:
read (a) ； read (b) ； 它们既可以同时执行，也可颠倒次序执行。对于这 样的语句，同时执行不会改变顺序程序所具有的逻 辑性质。因此，可以采用并发执行来充分利用系统 资源以提高计算机的处理能力。 程序的并发执行可总结为：一组在逻辑上互相独立 的程序或程序段在执行过程中，其执行时间在客观 上互相重叠，即一个程序段的执行尚未结束，另一 个程序段的执行已经开始的这种执行方式。 程序的并发执行不同于程序的并行执行。程序的并 行执行是指一组程序按独立的、异步的速度执行。 并行执行不等于时间上的重叠。可以将并发执行过 程描述为：
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS SO Cobegin PI;P2;….Pn Coend Sn 这里,S0,Sn分别表示并发程序段P1,P2,∴,Pn 开始执行前和并发执行结束后的语句。P1, P2,∴,Pn也可以由同一程序段中的不同语句组 成。1966年 bernstein提出了两相邻语句S1,S2可 以并发执行的条件: 将程序中任一语句S划分为两个变量的集合RS)和 W(Si)。其中 R(Si)={ala2…,am},aj(i=1,…,m) 是语句S在执行期间必须对其进行读写的变量;
S0 Cobegin P1；P2；... Pn Coend Sn 这里，S0，Sn分别表示并发程序段P1，P2，…，Pn 开始执行前和并发执行结束后的语句。P1， P2，…，Pn也可以由同一程序段中的不同语句组 成。1966年Bernstein 提出了两相邻语句S1，S2可 以并发执行的条件： 将程序中任一语句Si划分为两个变量的集合R(Si)和 W(Si)。其中 R(Si)={a1 a2 … am}，aj(j=1，…，m) 是语句Si在执行期间必须对其进行读写的变量；
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS W(Si=(b1 b2. bn), bjJ=1 是语句S在执行期间必须对其进行修改、访问的变量 如果对于语句S1和S2,有 ①R(S)∩W(S2)={$}, ②W(S1)nR(S2)={∮}, ③W(S1)∩W(S2)={∮}同时成立,则语句S和S2是 可以并发执行的
W(Si)={b1 b2 … bn}，bj(j=1，…，n) 是语句Si在执行期间必须对其进行修改、访问的变量； 如果对于语句S1和S2，有 ① R(S1)∩ W(S2)={∮}， ② W(S1)∩ R(S2)={∮}， ③ W(S1)∩ W(S2)={∮} 同时成立，则语句S1和S2是 可以并发执行的
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS (2)程序的并发执行所带来的影响 程序的并发执行充分地利用了系统资源,从而提高 了系统的处理能力,这是并发执行好的一方面。但 是,正如前面所提到的那样,由于系统资源有限, 程序的并发执行必然导致资源共享和资源竞争,从 而改变程序的执行速度。如果并发执行的各程序段 中语句或指令满足上述 Bernstein的三个条件,则 认为并发执行不会对执行结果的封闭性和可再现性 产生影响(证明略)。但在一般情况下,系统要判 定并发执行的各程序段是否满足 Bernstein条件是 相当困难的。从而,如果并发执行的程序段不按照 特定的规则和方法进行资源共享和竞争,则其执行 结果将不可避免地失去封闭性和可再现性。下面的 例子说明了这一点
(2) 程序的并发执行所带来的影响 程序的并发执行充分地利用了系统资源，从而提高 了系统的处理能力，这是并发执行好的一方面。但 是，正如前面所提到的那样，由于系统资源有限， 程序的并发执行必然导致资源共享和资源竞争，从 而改变程序的执行速度。如果并发执行的各程序段 中语句或指令满足上述Bernstein 的三个条件，则 认为并发执行不会对执行结果的封闭性和可再现性 产生影响（证明略）。但在一般情况下，系统要判 定并发执行的各程序段是否满足Bernstein 条件是 相当困难的。从而，如果并发执行的程序段不按照 特定的规则和方法进行资源共享和竞争，则其执行 结果将不可避免地失去封闭性和可再现性。下面的 例子说明了这一点