第4章 进程与进程管理4.docx
《第4章 进程与进程管理4.docx》由会员分享，可在线阅读，更多相关《第4章 进程与进程管理4.docx（28页珍藏版）》请在冰点文库上搜索。
第4章进程与进程管理4
4.1进程概念的引入
✧所谓程序,就是一个在时间上严格有序的指令集合.
✧在单道程序设计环境下,系统具有如下特点:
（1）资源的独占性:
任何时候,位于内存中的程序可以使用系统的一切资源.没有竞争资源.
（2）执行的顺序性:
各个程序是按次序执行的.如下图:
（3）结果的再现行:
由于执行环境和初始环境相同,重复执行一个程序,获得的结果总是一样
✧
在单道程序环境中执行顺序如下：
:
✧
多道程序环境下系统具有如下特点:
（1）执行的并发性:
并发性:
逻辑上相互独立的程序在执行时间上相互重叠,一个程序的执行还没结束,另一个程序已经开始.
宏观上看:
多道程序环境下,在內存的多个程序都在执行,按照自己的程序步骤推进.
微观上看:
由于CPU在任何时刻只能执行一个程序,程序轮流占用CPU,交替地执行.
（2）相互的制约性:
A间接制约B直接制约
（3）状态的多变性
✧在多道程序环境中执行顺序如下
✧在多道程序设计环境中,程序A和程序B同时在内存中,当然内存中还有其他的程序存在.由于执行的顺序性被打破了,执行过程交织在一起,无规律可循.见书上例子P60:
✧设A1:
N:
=N+1:
B1:
Print（N）;B2:
N:
=0;
有三种情况:
A1B1B2
B1A1B2
B1B2A1
4.1.1进程的定义
✧综合起来,可以从3个方面来描述进程:
（1）进程是程序的一次运行活动.
（2）进程的运行活动是建立在某个数据集合之上的.
（3）进程要在获得资源的基础上从事自己的运行活动.
概括的说:
是指一个程序在给定数据集合上的一次执行过程,是系统进行资源分配和运行调度的独立单位.
✧有两类进程:
一类是系统进程,另一类是用户进程
✧区别:
进程与程序的区别
4.1.2进程的特征
✧进程是程序的一次执行过程,主要特征如下:
（1）进程是一种动态的概念
（2）不同的进程可以执行同一个程序
（3）每个进程都有自己的生命期（4）进程之间具有并发性（5）进程之间相互制约
4.2进程的基本状态及转换
✧进程在其生命期內,可以处于下面3种基本状态之一：
（1）运行状态：
获得CPU的进程。
（2）阻塞状态：
进程为了等待某种外部事件的发生，暂时无法运行，阻塞状态也称等待状态或挂起状态。
（3）就绪状态：
已具备运行所需的一切条件。
✧例如上图的变迁图，试问在什么条件下将会发生下面给出的因果变迁：
（1）一个进程从运行状态变为就绪状态，一定会引起另一个进程从就绪状态变为运行状态。
（2）一个进程从运行状态变为阻塞状态一定会引起另一个进程从运行状态变为就绪状态。
（3）一个进程从阻塞状态变为就绪状态，一定会引起另一个进程从就绪状态变为运行状态。
✧例4－1：
如果系统中有20个进程，不考虑系统的调度开销，在某一时刻处于就绪状态，执行状态，阻塞状态的进程最多有多少个？
最少有多少个？
✧在具有挂起和解挂功能的系统中，进程增加的两种新状态－－－挂起就绪和挂起阻塞
✧挂起：
用户需要暂停自己的进程以检查中间结果或系统管理员为了减轻系统负荷
4.2.1Linux的进程控制块
✧Linux操作系统包括三种不同类型的进程：
交互进程，批处理进程，监控进程。
每种类型的进程都有自己的特点和属性。
✧在Linux中，每个进程在创建时都被分配一个数据结构，称为进程控制块（PCB）。
✧在Linux內核中，用一个称为Task_struts的数据结构作为进程控制块，指向该数据结构的指针形成一个task数组。
4.2.2进程控制块（PCB）的內容
✧一个进程要由３个部分组成：
程序，数据集合以及进程控制块PCB。
PCB是进程存在的唯一标志，具体表示如下：
✧进程控制块队列
✧操作系统三件事：
（1）把处于相同状态的进程的PCB通过各自的队列指针链接在一起，形成一个队列。
（2）为每一个队列设立一个队列头指针，总是指向排在队列之首的进程的PCB。
（3）排在队尾的进程的PCB，它的“队列指针”项內容应该为”-1”或一个特殊的符号，以表示这是该队的对尾PCB。
4.3.1进程的调度算法
✧先来先服务调度算法
此算法基本思想是：
以到达就绪队列的先后次序为标准来选择占用处理机的进程。
采用这种算法时应该这样来管理就绪队列：
到达的进程的PCB总是排在就绪队列末尾，调度程序总是把CPU分配给就绪队列中的第一个进程使用。
例：
就绪队列中依次来了三个进程A，B，C。
A进程需要运行24ms,B和C各需运行3ms.求平均等待时间
✧时间片轮转算法
基本思想：
为就绪队列中的每一个进程分配一个称为“时间片”的时间段，允许该进程运行的时间长度。
在使用完一个时间片后即使进程还没有运行完毕，也要强迫其释放处理机，让给另一个进程使用。
它自己则返回到就绪队列末尾，排队等待下一次调度的到来。
✧与先来先服务不同的是进程每次占用处理机的时间有时间片决定，而不是只要占用处理机就一直运行下去，直到运行完毕成为等待某一事件的发生而自动放弃。
✧在时间片轮转算法中：
时间片大小的设定是一个影响系统效率发挥的重要因素：
（1）太大==先来先服务
（2）太小：
调度程序频率上升，系统耗费在调度上的时间增加，真正运行用户程序的时间减少。
✧例：
有一个分时系统允许10个终端用户同时工作，时间片设定为100ms。
若对用户的每一个请求，CPU将耗费300ms的时间进行处理，做出回答，试问终端用户提出两次请求的时间间隔最小是多少？
✧优先数调度算法
基本思想：
为系统中的每个进程规定一个优先数，就绪队列中具有最高优先数的进程优先得到处理机的权利，优先数相同实行先来先服务的调度。
优先数越小者优先级越大。
✧优先数又分为静态优先数和动态优先数。
（1）静态优先数：
在进程的整个生命周期內优先数保持不变。
（2）动态优先数：
在进程的整个生命周期內可随时修正它的优先级别以适应系统环境和条件的变化。
✧多级队列调度算法：
是时间片调度算法与先来先服务调度算法的结合。
实行这种调度算法时，系统维持多个就绪队列。
每个就绪队列具有不同的调度级别可以获得不同长度的时间片。
具体的调度方法是：
创建一个新进程时，它的PCB将进入第一级就绪队列的末尾。
对于在第一级到第n-1级队列中的进程。
如果在时间片內完成全部工作，那就撤离系统。
如果在时间片没用完时提出了输入/输出请求或要等待某事件发生，那么就进入相应的阻塞队列等待。
4.3.2进程管理的基本原语
✧原语：
为了保证执行时的绝对正确，要求他们以一个整体出现，不可分割，也就是说一旦启动，他们的程序就要保证做完，中间不能插入其他程序的执行序列。
在操作系统中把具有这种特性的程序称为“原语”。
✧创建进程的原语
主要功能有三项：
（1）新建进程申请一个进程控制块PCB。
（2）将创建者（即父进程）提供的信息插入PCB中。
（3）将新建进程设置为就绪状态，按照所采用的调度算法，把PCB排入就绪队列中。
✧撤销进程原语
主要功能是收回该进程占用的资源，将该进程的PCB从所在队列里摘下，将PCB所占用的存储区间归还给系统。
✧阻塞进程原语
一个进程通过调用阻塞进程原语或将自己的状态由运行变为阻塞，或将处于就绪状态的子孙进程改变为阻塞状态。
✧唤醒进程原语
在等待事件发生后，就要调用唤醒进程原语以便把某个等待进程从相应的阻塞队列里解放出来，进入就绪对列，重新参与调度。
习题
1.有两个程序，A程序按顺序使用CPU10s,使用设备甲5s,使用CPU5s,使用设备乙10s,最后使用CPU10s。
B程序按顺序使用设备甲10s,使用CPU10s,使用设备乙5s,使用CPU5s,使用设备乙10s。
在顺序环境下先执行A程序在执行B程序，CPU的利用率是多少？
2．设某计算机系统有一台输入机，一台打印机。
现有两道程序投入运行，且程序A先开始运行，程序B后运行。
程序A的运行轨迹为：
计算50ms,打印100ms,再计算50ms,打印100ms,结束。
试说明：
两道程序运行时，CPU有无空闲等待？
若有，在哪段时间等待？
为何会空闲等待？
程序A，B运行时有无等待现象？
若有，出现在何时？
3.在单机系统中，系统中各个进程到达就绪队列的时刻、执行时间和优先级（优先数越小优先级越高）如表1-3-1所示。
假设进程的调度时间忽略不计。
请分别给出采用下面不同的进程调度算法时各个进程的调度次序，并计算平均周转时间。
表1-3-1
进程
到达就绪队列的队列
执行时间（ms）
优先数
P1
0
3
3
P2
2
6
5
P3
4
4
1
P4
6
5
2
P5
8
2
4
（1）先来先服务调度算法
（2）时间片轮转算法（时间片为1ms）
（3）剥夺式短进程优先调度算法;（4）剥夺式优先级调度算法（5）非剥夺式优先调度算法
4.6进程的互斥和同步
4.6.1互斥和同步
✧进程间共享资源的方式不同，导致不同的制约方式：
间接制约和直接制约。
（1）间接制约：
由于进程之间存在资源共享而引起的。
（2）直接制约：
由于进程之间存在合作关系引起的。
4.6.2临界资源和临界区的引入（见P60）
✧临界资源的定义：
在同一时刻就只能有一个进程使用的资源。
✧临界区的定义：
每个进程中访问临界资源的那段程序。
临界区的使用必须是互斥的，解决问题必须遵循以下原则：
（1）有闲让进
（2）忙则等待（3）有限等待（4）让权等待
4.6.3互斥的加锁实现（P78）
✧用硬件加锁的方法可以简单而有效地实现互斥。
为每个临界区或临界资源设置一个布尔变量lock
（1）Lock=false临界区没有进程，允许等待进程进入。
（2）Lock=true有别的进程，则不允许进入执行。
进程使用临界资源的步骤如下：
（1）测试lock的值。
（2）进程进入临界区，访问临界资源。
（3）退出临界区，置lock为false（开锁），下一个进程才能继续使用该临界资源。
4.6.4信号量与PV操作
✧进程间的制约关系
先看个例子1：
编写一个复制n个记录的程序，它把文件F中的每一个记录依次先读到输入缓冲区R，在从R拷贝到输出缓冲区T，最后写到文件G中。
假定R和T的大小正好存放一个记录，如图所示：
可以编写三个子程序来完成这一工作。
GET:
负责从文件F中按照顺序读出一个记录，然后送入输入缓冲区R。
COPY：
负责把输入缓冲区R中的记录拷贝到输出缓冲区T中。
PUT：
负责从输出缓冲区T中读出一个记录，然后依照顺序写入文件G。
不去考虑GET、COPY和PUT的执行关系，那么它们的执行顺序可以有6种可能：
（1）COPYPUTGET
（2）COPYGETPUT
（3）PUTCOPYGET
（4）PUTGETCOPY
（5）GETCOPYPUT
（6）GETPUTCOPY
✧通过分析这例子，得到进程间具有的两种制约关系：
互斥与同步。
（1）对于共享资源的争夺，导致进程之间出现互斥关系；
（2）由于对任务的协同工作，导致进程之间出现同步关系。
✧wait操作将信号量减1，表示分配资源。
signal操作将信号量增1，表示释放资源。
✧wait操作：
s=s-1;s<0阻塞进程，把它插入等待队列中
signal操作：
s=s+1s<=0在等待队列中还有进程在等待；
✧公用信号量：
为一组互斥共享临界资源的并发进程。
私用信号量：
为一组需同步协作完成任务的并发进程而设置的。
4.6.5信号量实现进程的互斥
✧进程互斥指进程之间互斥的访问CPU。
例：
自习教室中共有50个座位，当教室里没有空余座位时读者只能在教室外等候，直到有人离开教室时方可进入。
请定义相应的信号量并用PV操作给出读者进行自习的同步算法。
解：
begin
semaphores:
=50;
cobegin
processreader;
begin
wait（s）;
进入自习教室；
自习；
离开自习教室；
signal（s）;
end;
coend;
end
✧信号量的取值范围：
有N个进程共用一个临界资源，那么信号量的取值范围是[1-n,1].如果n个进程共用m个临界资源，则信号量的取值范围就是[m-n,m].
4.6.6信号量实现进程同步
✧运算进程与输出进程同步
设置两个私有信号量A和B分别代表空闲缓冲区和缓冲区中的数据这两种资源。
运算进程实现程序中数据的处理，输出进程则把运算进程处理的结果输出。
通过分析可知，在这个程序中有空闲缓冲区和缓冲区中的数据两种资源，因此需要两个私用信号量A和B分别代表这两种资源。
运算进程对信号量A进行wait操作（申请空闲缓冲区），对信号量B进行signal操作（往缓冲区中放入数据，使数据这个资源的数量增加，相当于释放资源操作），而输出进程正好相反，对信号量B进行P操作（申请数据），对信号量A进行V操作（取走数据以后缓冲区就空闲了，相当于释放缓冲区）。
这两个合作进程之间的同步关系可描述如下：
begin
integerA,B;
A:
=1;B:
=0;
Cobegin
CP:
begin｛运算进程｝
Repeat
Computenextnumber;｛计算一批数据｝
wait（A）;｛申请缓冲区空间｝
Addtobuffer;｛放入数据｝
signal（B）;｛释放数据资源｝
Untilfalse
End
OP:
begin｛输出进程｝
Repeat
wait（B）;｛申请数据资源｝
Takefrombuffer;｛取出数据｝
signal（A）;｛释放缓冲区空间｝
Outputthenumber;｛输出数据｝
Untilfalse
End
Coend
end
✧例4-3有三个进程A、B、C共用一个缓冲区buffer，进程A在buffer中存入数据X，进程B从buffer中取出X进行处理后得到数据Y再存入buffer，进程C从buffer中取走数据Y进行处理。
定义相应的信号量并给出用PV操作描述的三个进程的协作关系
解：
定义三个信号量S、SX、SY分别代表缓冲区、数据X和数据Y的可用与否。
对于进程A来说，它需要buffer来存放数据X，对于进程B来说，只有数据X可用才能计算出数据Y，对于进程C来说，只有数据Y可用才能清空buffer让进程A存入下一个数据。
因此同步算法可以表示如下：
begin
semaphoreS,SX,SY:
=1,0,0;{系统初始状态下buffer空间可用，而数据X和数据Y均还未产生}
cobegin
processA
begin
wait（S）;{申请buffer空间，以便存入数据X}
存入数据X；
signal（SX）;{数据X已可用，进程B可继续}
end
processB
begin
wait（SX）;
取出数据X；
计算出数据Y;
signal（SY）;{数据Y可用}
end
processC
begin
wait（SY）;
取出数据Y;
signal（S）;{数据Y被取出后可清空缓冲区，为进程A提供空间以放入下一个数据}
end
coend
end
4.6.7经典进程同步问题
✧生产者－消费者问题
所谓生产者－消费者问题，描述的是生产者向消费者提供产品。
生产者生产产品存入仓库（仓库容量有限），消费者从仓库中提取产品进行消费；当仓库满时停止存入产品，当仓库为空时不能提取产品；
生产者－消费者问题可描述如下：
begin
integerA,B,S;
empty:
=n;full:
=0;mutex:
=1;｛信号量full代表空闲缓冲区个数，初始值为最大缓冲区个数n，信号量empty为缓冲区中已存入的数据个数，初始值为0，信号量mutex是公用信号量，用于控制读写操作的互斥，没有进程在进行读写操作时数值为1｝
Cobegin
Producer:
begin｛生产者进程｝
Repeat
生产数据；
wait（empty）;｛申请缓冲区空间｝
wait（mutex）;｛申请读写权限｝
取得缓冲区空间；
向缓冲区中写入数据；
signal（mutex）;｛释放读写权限｝
signal（full）;｛释放数据资源｝
Untilfalse
End
Consumer:
begin｛消费者进程｝
Repeat
wait（empty）;｛申请数据资源｝
wait（mutex）;｛申请读写权限｝
从缓冲区中取出数据；
signal（mutex）;｛释放读写权限｝
signal（full）;｛释放缓冲区空间｝
Untilfalse
End
Coend
end
✧.读者－写者问题
对于磁盘上的一个文件来说，在同一时刻允许多个进程读取它，不需要互斥，也不存在破坏数据问题，但如果是写进程正在对它进行操作的同时，就不允许其它的读进程或写进程也对它进行操作，也就是说写进程必须和写进程、读进程之间都互斥，否则就会破坏数据的正确性和完整性。
因此在读写进程间必须用一个公用信号量wrt实现读写进程间的互斥。
在读进程数量为0时允许写进程操作，所以在程序中还必须有一个变量readcount统计读进程的数量，开始进行读操作前把readcout加1，读操作进行完毕把readcount减1，但加1和减1的操作必须互斥，当readcount＝0时允许写进程进行操作，否则不允许。
读者－写者问题可以描述如下：
begin
integermutex,wrt;｛信号量mutex实现readcount的加1操作和减1操作间的互斥，wrt实现写进程和其他进程之间的互斥｝
integerreadcount;｛统计读者个数，个数为0时允许写进程操作｝
cobegin
reader:
begin｛读者进程｝
repeat
wait（mutex）;｛实现readcount加1、减1操作的互斥｝
Readcount:
=readcount+1;｛统计读者数量｝
Ifreadcount=1thenwait（wrt）;｛一旦有读者进程在进行读操作，就申请写权限，不允许写进程操作｝
signal（mutex）;
读文件；
wait（mutex）;｛实现readcount加1、减1操作的互斥｝
Readcount:
=reacount-1;｛统计读者数量｝
Ifreadcount=0thensignal（wrt）;｛读者数量为0时就释放写权限，允许写进程操作｝
signal（mutex）;
End
Writer:
begin｛写者进程｝
wait（wrt）;｛申请写权限，不允许另一个写者进程进行写操作｝
写文件；
signal（wrt）;｛释放写权限｝
End
Coend
End
对于磁盘上的一个文件来说，在同一时刻允许多个进程读取它，不需要互斥，也不存在破坏数据问题，但如果是写进程正在对它进行操作的同时，就不允许其它的读进程或写进程也对它进行操作，也就是说写进程必须和写进程、读进程之间都互斥，否则就会破坏数据的正确性和完整性。
在读进程数量为0时允许写进程操作，所以在程序中还必须有一个变量readcount统计读进程的数量，开始进行读操作前把readcout加1，读操作进行完毕把readcount减1，但加1和减1的操作必须互斥，当readcount＝0时允许写进程进行操作，否则不允许.（P85例子）
✧例4.3工厂的仓库最多允许存入50个产品，生产者把生产的产品存入仓库，消费者从仓库中取出产品进行消费，当仓库满时生产者不再生产。
仓库中只有一套搬运设备，生产者存入产品和消费者取出产品均必须依靠搬运设备进行。
试给出生产者和消费者的同步进程算法。
begin
semaphoreSA,SB,X:
=50,0,1;{初始状态下仓库为空，即仓库容量为50，产品数量为0，搬运设备可用}
cobegin
processproducer;
begin
P（SA）;{如果仓库有空就继续生产，如果仓库满则停止}
生产产品；
P（X）;{申请搬运设备}
放入产品；
V（X）;{归还搬运设备}
V（SB）;{产品数量增加}
end
processconsumer;
begin
P（SB）;{如果仓库中有产品，就可取产品进行消费}
P（X）;{申请搬运设备}
取出产品；
V（X）;{归还搬运设备}
V（SA）;{取出产品后仓库容量增加}
消费产品；
end;
coend
end
✧例4.4河上有一个南北向的独木桥，当独木桥上没有人过桥时，允许先到达某一方的人过桥，当独木桥上有人时允许同一方向的人通过，当某一方向最后一个过桥的人上桥后就不再允许其他人再上桥，直到这个方向的人全部过桥后再让等待的其他人过桥。
用PV操作管理独木桥的过桥过程。
解：
对独木桥设一个信号量S，对两个不同方向过桥的人分别设两个信号量SA和SB，用CA和CB分别表示两端过桥的人。
同步算法如下：
begin
semaphoreS,SA,SB:
=1,1,1;
integerCA,CB;
CA:
=0;CB:
=0;
cobegin
processSouthToNorth;
begin
P（SA）;
CA:
=CA+1;
IfCA=1thenP（S）;
V（SA）;
人可从独木桥的南方到北方；
P（SA）;
CA:
=CA-1;
IfCA=0then
Begin
其他人不允许再上桥，只允许桥上从南到北的人通过；
V（S）;
end
end
processNorthToSouth;
begin
P（SB）;
CB:
=CB+1;
IfCB=1thenP（S）;
V（SB）;
人可从独木桥的北方到南方；
P（SB）;
CB:
=CB-1;
IfCB=0then
Begin
其他人不允许再上桥，只允许桥上从北到南的人通过；
V（S）;
end
end
coend
end
4.7死锁
✧死锁的形成
死锁问题是Dijkstra于1965年研究银行家算法时首先提出的，而后为Havender、Lynch等人分别于1968年、1971年相继认识和发展。
在系统中的一组进程由于竞争系统资源或由于彼此通信而永远阻塞，此时称这些为进程处于死锁状态。
✧产生死锁的原因如下：
1.系统资源不足；2.进程推进顺序非法
✧不仅是I/O设备的共享会引起死锁，存储器的共享及临时性资源也都会产生死锁。
因此，产生死锁的必要条件是：
（1）互斥条件
（2）请求和保持条件（
升级会员 