【操作系统】第二章进程管理1

作业一、选择题1.在计算机系统中配置操作系统的主要目的是（A）。操作系统的主要功能是管理计算机系统中的（B），其中包括（C）、（D），以及文件和设备。这里的（C）管理主要是对进程进行管理。A：（1）增强计算机系统的功能；（2）提高系统资源的利用率；（3）提高系统的运行速度；（4）合理组织系统的工作流程，以提高吞吐量。B：（1）程序和数据；（2）进程；（3）资源；（4）作业；（5）软件；（6）硬件。C，D：（1）存储器；（2）虚拟存储器；（3）运算器；（4）处理机；（5）控制器。2.操作系统有多种类型：允许多个用户以交互方式使用计算机的操作系统称为（A）；允许多个用户将若干个作业提交给计算机系统集中处理的操作系统称为（B）；在（C）的控制下，计算机系统能即使处理由过程控制反馈的数据，并做出响应；在IBM－PC机上的操作系统称为（D）。A，B，C，D：（1）批处理操作系统；（2）分时操作系统；（3）实时操作系统；（4）微机操作系统；（5）多处理机操作系统。3.在设计分时操作系统时，首先要考虑的是（A）；在设计批处理操作系统时，先要考虑的是（B）；在设计实时操作系统时，首先要考虑的是（C）。A，B，C：（1）灵活性和可适应性；（2）交互性和响应时间；（3）周转时间和系统吞吐量；（4）实时性和可靠性。4.分时系统的响应时间（及时性）主要是根据(A)确定的，而试试系统的响应时间则是由（B）确定的。A，B：（1）时间片大小；（2）用户数目；（3）计算机运行速度；（4）用户所能接受的等待时间；（5）控制对象所能接受的时延；（6）实时调度。5.采用（A）结构时，将OS分成用于实现OS最基本功能的内核和提供各种服务的服务器两个部分。通常，下列模块中必须包含在操作系统内核中的是（B）模块。A：（1）整体式；（2）模块化；（3）层次式；（4）微内核。B：（1）内存分配；（2）中断处理；（3）文件处理；（4）命令处理。6.在3.X版本以前的MS－DOS是（A）操作系统，Windows95是（B）操作系统，WindowsXP是（C）操作系统，它们都是由（D）开发的。A，B，C：（1）单用户单任务；（2）单用户多任务；（3）多用户单任务；（4）多用户多任务。D：（1）IBM公司；（2）Microsoft公司；（3）Microsoft和IBM联合；（4）Bell实验室；7.下面8个系统中，必须是实时操作系统的有（）A计算机辅助设计系统；B航空定票系统；C过程控制系统；D机器翻译系统；E办公自动化系统；F计算机激光照排系统；G情报检索系统；H导弹的制导系统•二、简答题1.在操作系统中实现虚拟的关键技术是什么？并加以说明。2.试从交互性、及时性以及可靠性三个方面，比较分时系统与实时系。第二章进程管理重点和难点：•进程的定义和特征•进程的同步和互斥•用信号量机制解决进程同步、互斥、前趋图问题2.1进程的基本概念•2.1.1进程的引入•程序的顺序执行、程序的并发执行特征比较程序的顺序执行程序的并发执行1顺序性1间断性2封闭性2失去封闭性3可再现性3不可再现性进程的引入•多道程序系统的特点是并行性。为了充分利用系统资源，在主存中同时存放多道作业运行，所以各作业之间是并行的•各程序由于同时存在于主存中，它们之间必定会存在相互依赖，相互制约的关系。（间接制约关系、直接制约关系）•在多道程序系统所带来的复杂环境中，程序具有了并行、制约、动态的特性，原来的程序概念，难以刻画系统中的情况了。–程序本身完全是静态的概念–程序概念也反映不了系统中的并行特性•前驱图（ProcedenceGraph）：是一个有向无循环图，图中的每个结点可用于表示一条语句，一个程序段或进程；结点间的有向边则表示在两结点之间存在的偏序或前驱关系。“”，＝{(pi，pj)}•如果(pi，pj)∈可写成pipj，称pi是pj的前驱，而pj是pi的直接后继。•关于前驱图的几个概念：–1直接前趋–2直接后继–3初始结点–4终止结点–5结点的重量：该结点所含的程序量或结点的执行时间来计算。1234567存在下面的前驱关系：P1P2，P1P3；P1P4；P2P5；P3P5；P5P7;P4P6，P6P7或表示为：P＝{P1,P2,P3,P4,P5,P6,P7}={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,p5),(P4,P6),(P5,P7),(P6,P7)}•注意：前驱图中不存在循环。S2S3，S3S2显然这种前驱关系是不可能满足的，S3的执行要依赖于S2的执行结果，S2的执行结果又要依赖于S3的执行结果，这种程序是不可能执行下去的。•一个较大的程序通常都是由若干个程序段组成。在程序执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。•例如：在进行计算时，总是先输入用户的程序和数据，然后才能计算，计算完成后再将结果打印出来。1.程序的顺序执行I1C1P1P2I2C1程序顺序执行时的前驱图对于一个程序段中的多条语句来说，也有一个执行顺序的问题。如果对于下述三条语句的程序段：S1：a：＝x＋yS2：b：＝a－5S3：C：＝b＋1(其中S2必须在a被赋值以后才能执行；同样S3也只能在b被赋值以后才能执行)2.程序顺序执行时的特征（1）顺序性处理机的操作，严格按照程序所规定的顺序执行，即只有前一操作结束后，才能执行后继操作。（2）封闭性（失去交换性）程序是在封闭的环境下运行的。即程序在运行时，它独占全机资源，因而机内各资源的状态（除初始状态外），只有程序才能改变它。程序一旦开始运行，其执行结果不受外界因素的影响。（3）可再现性只要程序执行时的环境和初始条件都相同，不论它是从头到尾的不停顿的执行，还是“走走停停”地执行，都将获得相同的结果。3.多道程序系统中，程序执行环境的变化计算机能够同时处理多个具有独立功能的程序（批处理系统，分时系统、实时系统、网络与分布式系统）。这样的执行环境具有三个特点：独立性随机性资源共享硬件资源：CPU、输入输出设备，存储器软件资源：各种例行程序、各种共享的数据多道程序环境下执行程序的道数计算机系统中CPU的个数单CPU中，则由N－1道程序处在等待CPU的状态输入输出设备有限将导致这些设备被共享、内存有限将导致内存被共享程序的并发执行程序并发执行时的前驱图I1I2I4C1C3P1C4P4P3P2C2I3•在上图中存在下属的前驱关系：•IiCi，IiIi＋1，CiPi，CiCi＋1，PPi＋1•Ii＋1和Ci及Pi－1是可以并发执行的。例：下述四条语句的程序段画出前驱图S1：a：＝x+2S2：b：＝y＋4S3：c：＝a＋bS4：d：＝c＋6S1S2S4S31.程序并发执行可分为两种：•多道程序系统的程序执行环境变化所引起的多道程序的并发执行由于资源有限，多道程序的并发执行总是伴随着资源的共享与竞争，制约了各道程序的执行速度。•在某道程序段中，包含着一部分可以同时执行或顺序颠倒执行的代码例如：read（a）；read（b）；既可以同时执行，也可以颠倒次序执行，同时执行不会改变顺序程序所具有的逻辑性质，可采用并发执行来充分利用资源。•程序并发执行：一组逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠，即一个程序段的执行，尚未结束，另一个程序段的执行已经开始的这种执行方式。程序并发执行时的特征•间断性、失去封闭性、不可再现性•间断性–程序在并发执行时，由于它们共享资源或为完成某一项任务而合作，致使在并发程序之间存在相互制约的关系。(I、C、P是三个相互合作的程序，当计算程序完成Ci－1的计算后，如果输入程序I尚未完成对Ii的处理，则计算程序无法进行Ci处理，致使计算程序暂停运行。)•失去封闭性–程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。•不可再现性–程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。例如：有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时都要做N：＝N＋1操作；程序B每执行一次时，都要做print（N）操作，然后再将N置成“0”，程序A和B以不同的速度运行。（假定某时刻变量N的值为n）–（1）N：＝N＋1在print（N）和N：＝0之前，此时得到的N值分别为n＋1，n＋1，0（2）N：＝N＋1在print（N）和N：＝0之后，此时得到的N值分别为n，0，1（3）N：＝N＋1在print（N）和N：＝0之间，此时得到的N值分别为n，n＋1，0程序并发执行的条件程序并发执行过程可以描述为：S0CobeginP1；P2；……PnCoendSn1966年，Bernstein提出了相邻语句S1，S2可以并发执行的条件。如果并发执行的各程序段中语句或指令满足Bernstein的三个条件，则认为并发执行不会对执行结果的封闭性和可再现性产生影响。将程序中任一语句Si划分为两个变量的集合R（Si）和W（Si）其中R（Si）＝{a1,a2,……am}是语句Si在执行其间必须对其进行读写的变量W（Si）＝{b1，b2，……bn}是语句Si在执行其间必须对其进行修改，访问的变量如果对于语句S1和S2，有①R(S1)∩W(S2)＝{Φ}②W(S1)∩R(S2)＝{Φ}③W(S1)∩W(S2)={Φ}同时成立即：R(S1)∩W(S2)∪W(S1)∩R(S2)∪W(S1)∩W(S2)＝{Φ}则语句S1和S2是可以并发执行的。例：若有两条语句C＝a－b和W＝c＋1，判断它们是否可以并发执行？解：它们的“读集”和“写集”分别为R（C：＝a－b）＝{a，b}；R（W：＝c＋1）＝{c}W（C：＝a－b）＝{c}；W（W：＝c＋1）＝{w}R（C：＝a－b）∩W（W：＝c＋1）={Φ}R（W：＝c＋1）∩W（C：＝a－b）={c}所以：两条语句不能并发执行。有的同学发现，同一语句的“读集”和“写集”的交集是空集。R（C：＝a－b）∩W（C：＝a－b）＝{Φ}W（W：＝c＋1）∩W（W：＝c＋1）={Φ}其实，同一语句的“读集”和“写集”也可能相同（交集不为空）例如：计数语句：x＝x＋1读集和写集相同R（x＝x＋1）＝W（x＝x＋1）＝{x}课后练习例：用Bernstein条件判断以下四条语句是否可以并发执行。S1：a：＝x＋yS2：b：＝z＋1S3：C：＝a－bS4：w：＝c＋1•例：设有堆栈S，栈指针top，栈中存放内存中相应数据块地址，设有两个程序段getaddr（top）和reladdr（blk），其中getaddr（top）从给定的top所指栈中取出相应的内存数据块地址，而reladdr（blk）则将内存数据块地址blk放入堆栈S中。abefabefabeftop执行toptop＋1后toptopgetaddr为了控制和协调各程序段执行过程中的软硬件资源共享和竞争，必须有一个描述各程序执行过程和共享资源的基本单位。（这个单位被成为进程，或任务task）进程的定义•进程有许多各式各样的定义（1）进程是可以并发执行的计算部分（2）进程是一个独立的可以调度的活动（3）进程是一个抽象的实体，当它执行某个任务时，将要分配和释放各种资源（4）行为的规则叫程序，程序在处理机上执行的活动称为进程。（5）一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于以何种详尽程度来描述进程。进程：一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。（在这里，程序指一组操作序列，而数据集则是接受程序规定操作的一组存储单元的内容。）•比较进程和程序的区别：答：1进程是一个动态的概念，进程的实质是程序的一次执行过程，动态性是进程的基本特征，同时进程是有一定的生命期的；而程序只是一组有序指令的集合，本身并无运动的含义，是静态的。2并发性，并发性是进程的重要特征，引入进程的目的正是为了使其程序和其它程序并发执行；而程序(没有建立进程)是不能并发执行的。3独立性，是指进程一个能独立运行、独立分配资源和独立调度的基本单位；凡未建立进程的程序，都不