二进程管理.docx
《二进程管理.docx》由会员分享，可在线阅读，更多相关《二进程管理.docx（25页珍藏版）》请在冰点文库上搜索。
二进程管理
二、进程管理
（一）进程与线程
⒈进程概念
①进程的定义：
可并发执行的程序在一个数据集合上的运行过程。
②进程的特征：
动态性、并发性、独立性、异步性、结构性（程序段，数据段，PCB）。
⒉进程的状态与转换
①进程的三种状态：
就绪态、执行态、阻塞态。
另包含新状态和终止状态。
②状态转换：
⒊进程控制
①系统态（核心态、管态），用户态（目态）。
②原语的概念
③创建原语、撤消原语、阻塞原语、唤醒原语
创建原语流图
撤销原语流图
图3.9阻塞原语图
唤醒原语
⒋进程组织
程序段，数据段，PCB
PCB结构：
进程标识符信息、处理机状态信息、进程调度信息、进程控制信息。
⒌进程通信
①共享存储系统
基于共享数据结构的通信方式；基于共享存储区的通信方式。
②消息传递系统
直接通信；利用信箱的间接通信
汉森（Hansan）方法：
消息缓冲区队列通信机制
管道通信：
连接一个读进程和一个写进程的共享文件（pipe）称为管道，必须满足互斥和同步。
⒍线程概念与多线程模型
线程：
线程是进程中的一个实体，是被系统独立调度的基本单位。
线程本身基本不拥有资源，进程内的线程共享进程资源，故又称线程为轻权进程。
多线程模型：
用户级线程UTL和内核级线程KLT的结合称为多线程的操作系统。
（二）处理机调度
⒈调度的基本概念
主要指分级调度的概念
①高级调度又称作业调度
②中级调度又称交换调度
③低级调度包括进程调度和线程调度，其中进程调度分为抢占方式和非抢占方式。
⒉调度时机、切换与过程
①调度时机
作业调度时机：
内存有空闲空间时。
交换调度：
根据内存使用情况，由系统自动完成。
进程调度时机：
分时系统中时间片用完；执行进程等待某个事件的发生；抢占方式下，在就绪队列中出现优先级更高的进程。
附：
进程调度时机
进程调度发生在什么时机呢？
这与引起进程调度的原因以及进程调度的方式有关。
引起进程调度的原因有以下几类：
（1）正在执行的进程执行完毕。
这时，如果不选择新的就绪进程执行，将浪费处理机资源。
（2）执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。
（3）执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了V原语操作激活了等待资源的进程队列。
（4）执行中进程提出I／O请求后被阻塞。
（5）在分时系统中时间片已经用完。
（6）在执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。
以上都是在CPU执行不可剥夺方式下所引起进程调度的原因。
在CPU执行方式是可剥夺时，还有：
（7）就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度
②切换与过程
发生进程调度时要进行进程上下文切换，进程上下文由正文段、数据段、硬件寄存器的内容以及有关数据结构等组成。
。
切换过程：
进程上下文切换包括4个步骤
（1）决定是否做上下文切换以及是否允许做上下文切换。
（2）保存当前执行进程的上下文。
这里所说的当前执行进程，实际上是指调用上下文切换程序之前的执行进程。
（3）使用某种进程调度算法，选择一个处于就绪状态进程。
（4）恢复或装配所选进程的上下文，将CPU控制权交给所选进程
⒊调度的基本准则
①面向用户的准则：
周转时间短、响应时间快、截止时间（开始执行的最迟时间，用于实时系统）的保证、优先权准则。
②面向系统的准则：
系统吞吐量高、处理机利用率高、各类资源的平衡利用。
⒋调度方式
抢占方式：
抢占原则有时间片原则、优先权原则、短作业（进程）原则。
非抢占方式：
主要用在进程调度中。
⒌典型调度算法
①先来先服务调度算法
②短作业（短任务、短进程、短线程）优先调度算法
③时间片轮转调度算法
④优先级调度算法
⑤高响应比优先调度算法[响应比=（等待时间+要求服务的时间）/要求服务的时间]
⑥多级反馈队列调度算法
（三）进程同步
⒈进程同步的基本概念
①临界资源
②临界区：
每个进程访问临界资源的那段代码叫临界区。
③同步机制应遵循的原则：
空闲让进、忙则等待、有限等待、让权等待（等待时应让出处理机）
⒉实现临界区互斥的基本方法（软件实现方法;硬件实现方法）
①软件实现方法（Peterson算法）：
设有两个进程P1和P2
P1进入临界区的条件是flag1andturn=1为true
P2进入临界区的条件是flag2andturn=2为true
同时申请，后执行turn的进入
flag1=false;
flag2=false;
turn=1;
repeat;
P1:
flag1=true;
turn=2;
while（flag2andturn=2）dono_op;
临界区;
flag1=false;
P2:
flag2=true;
turn=1;
while（flag1andturn=1）dono_op;
临界区;
flag2=false;
untilfalse
②硬件实现方法
Test_and_Set指令
硬件实现方法不能实现让权等待原则。
⒊信号量
①整型信号量
②P、V操作
Ｐ原语操作的主要动作是：
（1）sem减1；
（2）若sem减1后仍大于或等于零，则进程继续执行；
（3）若sem减1后小于零，则该进程被阻塞后与该信号相对应的队列中，然后转进程调度。
Ｖ原语的操作主要动作是：
（1）sem加1；
（2）若相加结果大于零，进程继续执行；
（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。
③用PV操作解决进程同步与互斥
互斥：
sem=1;
PA：
Ｐ（sem）
〈Ｓ〉
Ｖ（sem）
PB：
Ｐ（sem）
〈Ｓ〉
Ｖ（sem）
同步：
Sa=1；Sb=0；
PA:
deposit（data）:
P（Sa）；
送入数据；
Ｖ（Sb）;
PB:
remove（data）:
Ｐ（Sb）；
取出数据；
Ｖ（Sa）;
⒋管程
管程的基本思想是：
把分散在各进程中的控制和管理临界资源的临界区集中起来统一管理。
这样既便于系统管理共享资源，又能保证互斥访问。
Hansen给管程的定义是：
一个管程定义了一个数据结构和在此数据结构上能为并发程序所执行的一组操作，这组操作能同步进程和改变管程中的数据。
一个管程主要由三部分组成：
①局部于该管程的共享数据，这些数据表示了相应资源的状态；②局部于该管程的一组操作过程，每个过程完成对上述数据的某种规定操作；③对局部于该管程的数据的初始化。
进程1
进程1
进程2进程2
进程3进程3
…………
…………
…………
进程n进程n
管程示意图
任一进程要访问某个共享资源，就必须通过相应的管程才能进入。
为了实现对临界资源的互斥访问，管程每次只允许一个进程进入其内。
此外，当一进程进入管程执行管程的某个过程时，如果因某种原因而被阻塞，应立即退出该管程，进入等待状态，否则就会因阻挡其它进程进入该管程，而它本身又无法执行造成死锁。
⒌经典同步问题（生产者-消费者问题;读者-写者问题;哲学家进餐问题）
①生产者-消费者问题
avail=n;full=0;mutex=1;
deposit（data）:
begin
Ｐ（avail）
Ｐ（mutex）
送数据入缓冲区某单元
Ｖ（full）
Ｖ（mutex）
end
remove（data）:
begin
Ｐ（full）
Ｐ（mutex）
取缓冲区中某单元数据
Ｖ（avail）
Ｖ（mutex）
end
注意：
P操作顺序写反，可能产生死锁。
②读者-写者问题
Readers/Writers问题的定义如下：
一些进程共享一个数据区。
数据区可以是一个文件、一块内存空间或一组寄存器。
readers进程只能读数据区中的数据，而writers进程只能写。
所谓读者/写者问题就是指保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。
解决该问题必须满足的条件如下：
•任意多个readers可以同时读；
•任一时刻只能有一个writers可以写；
•如果writers正在写，那么readers就不能读
S=1;//写文件的互斥信号
Sr=1;//管理共享计数器的互斥信号
Rc=0;//正在读文件的读者个数
Readers:
begin
P（Sr）;
Rc=Rc+1;
IfRc=1thenP（S）;
V（Sr）;
ReadfileF;
P（Sr）;
Rc=Rc-1;
IfRc=0thenV（S）;
V（Sr）;
end;
Writer:
begin
P（S）;
WritefileF;
V（S）;
end
③哲学家进餐问题
设有5个哲学家，共享一张放有五把椅子的桌子，每人分得一把椅子。
但是，桌子上总共只有5支筷子，在每人两边分开各放一支。
哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐。
条件：
只有拿到两支筷子时，哲学家才能吃饭。
如果筷子已在他人手上，则该哲学家必须等待到他人吃完之后才能拿到筷子。
任一哲学家在自己未拿到两支筷子吃饭之前，决不放下自己手中的筷子。
方法1：
每个哲学家先拿其左边的筷子然后再拿右边的筷子。
哲学家用完餐后再将筷子放回原来的位置。
这种解决方法可能导致死锁。
方法2：
为避免死锁，可以只允许不超过4个哲学家同时用餐。
这样就至少有一个哲学家可以得到两根筷子。
这个方法可避免死锁和饥饿。
方法1：
fork[5]={1,1,1,1,1};
第i个哲学家进餐过程（i=0,1,2,3,4）
P（fork[i]）;//取左边的筷子
P（fork[（i+1）mod5]）;//取右边的筷子
eat;
V（fork[（i+1）mod5]）;//放下右边的筷子
V（fork[i]）;///放下左边的筷子
方法2：
fork[5]={1,1,1,1,1};
room=4;//限定只能4人同时进餐,可防止死锁。
第i个哲学家进餐过程（i=0,1,2,3,4）
P（room;）
P（fork[i]）;//取左边的筷子
P（fork[（i+1）mod5]）;//取右边的筷子
eat;
V（fork[（i+1）mod5]）;//放下右边的筷子
V（fork[i]）;///放下左边的筷子
V（room）;
④理发师问题：
（见大纲试题示例）
begin
mutex=1;rc=0;
wakeup=0;wait=0;
cobegin
customeri（i=1,…）barber
beginbegin
P（mutex）P（wakeup）//无顾客时理发师睡觉，被第1个顾客唤醒
rc=rc+1;repeat
ifrc=1thenV（wakeup）理发;
elseP（mutex）
ifrc<=nthenP（wait）//顾客<=n时,等待rc=rc-1;
elseifrc<>0thenV（wait）;//让等待中的一个顾客理发
beginV（mutex）
rc=rc-1;untilrc=0;//理发重返到无顾客为止
该顾客离开理发厅;//第n+1个离开end
end;coend
V（mutex）end;
end
⑤甲想往一空盒子里放入一本书A，乙想往这个空盒子里放入一本书B，这个空盒子只允许放一本书，且每次只允许一个人放入。
丙专等取出书A，丁专等取出书B。
若盒子中已有书，放者必须等待；若盒子中没有书，取书者必须等待。
如果将甲、乙、丙、丁四人的行为分别看作四个进程，试回答下列问题：
（1）说明四个人之间存在的同步与互斥关系（哪些进程之间存在互斥关系？
哪些进程之间存在同步关系？
）
（2）用P、V操作来描述四个人之间的同步、互斥关系。
答：
（1）甲乙之间存在互斥关系（互斥使用盒子）；甲丙要同步，乙丁要同步。
（2）empty表示盒子的容量，初值为1；
mutex为甲乙之间的互斥信号量，初值为1；
sa为甲与丙之间的同步信号量，表示盒子中是否有书A,初值为0；
sb为乙与丁之间的同步信号量，表示盒子中是否有书B初值为0。
Begin
Empty,mutex,sa,sb:
semaphore;
Empty=1;（6分）
Mutex=1;
Sa=0;
Sb=0;
Cobegin
Process甲Process乙Process丙Process丁
BeginBeginBeginBegin
L1:
P（empty）;L2:
P（empty）;L3:
P（sa）;L4:
P（sb）;
P（mutex）;P（mutex）;取出书A;取出书B;
放入书A;放入书B;V（empty）;V（empty）;
V（mutex）;V（mutex）;GotoL3;GotoL4;
V（sa）;V（sb）;EndEnd
GotoL1;GotoL2;
EndEnd
Coend
End
思考题①
ab
cd
a=b=c=d=0
P1P（a）P（b）P（c）
V（a）P2P3P（d）
V（b）V（c）V（d）P4
思考题②
一个盘子最多可放两个水果，爸爸专放苹果，妈妈专放桔子。
两个儿子专等吃桔子，两个女儿专等吃苹果。
每次只能放或取一个水果。
用PV操作写出它们的同步与互斥关系。
mutex=1;empty=2;apple=0;orange=0;
father:
mother:
daugbteri（i=1,2）:
soni（i=1,2）
P（empty）P（empty）P（apple）P（orange）
P（mutex）P（mutex）P（mutex）P（mutex）
放苹果放桔子取苹果取桔子
V（（mutex）V（（mutex）V（（mutex）V（（mutex）
V（apple）V（orange）V（empty）V（empty）
（四）死锁
⒈死锁的概念
①死锁定义
②产生死锁的原因：
竞争资源、进程推进顺序非法。
③产生死锁的必要条件：
互斥条件、请求和保持条件、不剥夺条件、环路等待条件。
⒉死锁处理策略
为使系统不发生死锁，必须设法破坏产生死锁4个必要条件中的1个。
允许死锁发生，在死锁发生时能检测出来，加以恢复。
归纳起来有三种策略：
1）采用静态分配法来防止死锁发生。
2）采用有控避免死锁发生。
3）当死锁发生时能检测出来，加以恢复。
⒊死锁预防
静态分配、有序分配（由小到申请，释放时有大到小）。
⒋死锁避免
系统安全状态：
银行家算法。
银行家算法示例：
设有A、B、C、D四种资源，五个进程，考虑如下的资源分配状态，其中AL为可用资源向量，U为各进程已占用资源矩阵，N为各进程尚需资源矩阵：
AL=（1,6,2,2）
ABCDABCD
0032P10012P1
1000P21750P2
U=1354P3N=2356P3
0332P40652P4
0014P50656P5
试问：
1）该状态是安全状态吗？
为什么？
2）如果进程P3提出资源请求（1，2，2，1），能否立即给予满足？
答：
（1）此时存在一个安全序列：
P1-P4-P5-P2-P3,故系统是安全的。
P1P4P5P2P3资源总数
可用资源（A）16221654198619910299103121414
尚需资源（N）00120652065617502356
占有资源（U）00320332001410001354
（2）
若P3提出请求（1，2，2，1）
因为（1，2，2，1）<（2，3，5，6）
（1，2，2，1）<（1，6，2，2）
故可假设将资源分配给P3，修改相应的数据结构，此时资源分配情况如下：
AL=（0，4，0，1）
0032p1
1000p2
U=2575p3
0332p4
0014p5
0012p1
1750p2
N=1135p3
0652p4
0656p5
此时用安全性算法检查系统是否安全,可用资源AL=（0，4，0，1）已不能满足任何进程的需要,故系统处于不安全状态,故不能将资源分配给P3。
⒌死锁检测和解除
①资源分配图：
进程P
同种资源R有3个
P占有R中的1资源
P申请R中的1资源
②死锁定理：
化简资源分配图，去掉可运行完进程的结点及相应的占有边和请求边。
如资源分配图中全部变成孤立结点，则不能发生死锁。
例：
不能发生死锁的例子
R1R2
能发生死锁的例子，R1中有1个资源。
③死锁检测和解除
检测算法：
不断化简资源分配图直至不能化简为止，资源分配图中剩余的进程进入死锁状态。
基本思想：
1）在某时刻t，求得系统中各类可利用资源的数目向量w（t）。
2）对于系统中的一组进程{p1,p2,…pi,…pn}，找出那些对各类资源请求数目均小于系统现在所拥有的各类资源数目的进程。
这样的进程能够获得它们所需要的全部资源并运行结束。
当它们运行结束后释放所占有的全部资源，从而使可用资源数目增加，这样的进程加入到可运行结束的进程序列L中
3）然后对剩下的进程再作上述考查。
如果一组进程{p1,p2,…pn}中有几个进程不属于序列L中，那么它们会被死锁。
④死锁的解除
1）杀死所有的死锁进程
2）逐个杀死死锁进程，直至死锁解除，杀死顺序以开销最小为原则。
3）逐个抢占其它进程的资源，被抢占资源的进程必须撤回到它拥有该资源前的某一点。
抢占顺序也是以开销最小为原则。
《进程管理》选择题示例
1）进程与程序的根本区别在于（A）。
A、静态与动态的特点B、是否被调入到内存中
C、是否具有就绪、运行和等待3种状态D、是否占有处理器
2）一个进程被唤醒，其含义是（D）。
A、该进程重新占有了CPUB、该进程的优先权变为最大
C、该进程的PCB移至等待队列首D、该进程变为就绪状态
3）系统在（C）时，发生从用户态到系统态的转换。
A、发出P操作B、发出V操作C、执行系统调用D、置程序状态字
4）在下列解决死锁的方法中，属于死锁预防策略的是（B）。
A、银行家算法B、资源有序分配法
C、死锁检测法D、资源分配图化简法
5）进程从执行状态到阻塞状态是由（D）完成的。
A.进程调度B.其它进程调用阻塞原语C.硬件自动D.进程自身调用阻塞原语
6）在执行Ｐ操作时，进程若能继续执行，执行Ｐ操作前信号量的值应（A）。
A.大于０B.小于０C.等于０D.大于等于０
7）一次I/O操作的结束，有可能导致（A）。
A．一个进程由睡眠变就绪B．几个进程由睡眠变就绪
C．一个进程由睡眠变运行D．几个进程由睡眠变运行
8）任何两个并发进程之间（D）。
A．一定存在互斥关系B.一定存在同步关系C.一定彼此独立无关D.可能存在同步或互斥关系
9）进程依靠（D）从阻塞状态过渡到就绪状态。
A．程序员的命令B.系统服务C.等待下一个时间片到来D.“合作”进程的唤醒
10）（B）是多道操作系统不可缺少的硬件支持。
A．打印机B．中断机构C．软盘D．鼠标
11）为进程一次性分配所需的资源是一种（A）的方法，它能使系统不发生死锁。
A．死锁预防B．死锁检测C．死锁避免D．死锁解除
12）如果系统中有n个进程，则在就绪队列中进程的个数最少为（A）个。
A．0B．1C．大于等于1D．不确定
13）如果信号量的当前值为-2，则表示系统中在该信号量上有（C）个等待进程。
A．0B．1C．2D．不确定
14）在操作系统中，（B）是资源分配、调度和管理的基本单位。
A．程序B．进程C．线程D．作业
15）有m个进程共享n个同种临界资源，若使用信号量机制实现对资源的互斥访问，则信号量值的变化范围是（D）。
A．0~1B．m~nC．n~mD．n~（n-m）
16）某系统中有4个并发进程，都需要同类资源5个，试问该系统不会发生死锁的最少资源数是（C）。
A．15B．16C．17D．18
注：
解不等式n（x-1）+1<=m得m=17
（n；进程数；x：
一个进程最多申请资源数；m：
系统不会发生死锁的最少资源数）
升级会员 