资源描述
Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,山东农业大学计算机系,*,Click to edit Master title style,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,山东农业大学计算机系,*,上次问题,信号量是什么?,区别整型、记录型、,AND,型信号量以及信号量集,熟练使用记录集型信号量,其,wait,,,signal,具体做了什么?,如何利用记录型信号量实现互斥关系?,如何利用记录型信号量实现前趋关系?,11/19/2026,1,山东农业大学计算机系,第,2,章 进程管理,2.1,进程基本概念,2.2,进程控制,2.3,进程,同步、,管程,2.4,经典进程同步问题,2.5,进程通信,2.6,线程,11/19/2026,2,山东农业大学计算机系,生产者,消费者问题,互斥、同步,哲学家就餐问题,互斥,读者,写者问题,有条件的互斥,11/19/2026,3,山东农业大学计算机系,1.,生产者,消费者问题,The,proceducer,consumer problem,:多个生产者和消费者对,n,个缓冲区的使用。,不考虑互斥、同步问题会导致,counter,计数错误,如何设置信号量?从资源、顺序两个角度分析:,11/19/2026,4,山东农业大学计算机系,无论生产者、消费者使用缓冲池时应保证互斥使用(互斥信号量,mutex,),生产者和消费者间交叉有序:,有序的控制最根源在产品数量上。,设置两个信号量:,分别针对生产者、消费者设置不同的信号量,,empty,和,full,分别表示缓冲池中空缓冲池和满缓冲池(即产品)的数量。,empty,、,full,两者有天然的数量关系,在,PV,控制下值不断变化,但在,值等于,0,的点,上是控制顺序的关键。,11/19/2026,5,山东农业大学计算机系,*变量和信号量,buffer:array 0,n-1 of item;,in,out:integer:=0,0;,不使用,Counter,变量,而是用信号量,Var,mutex,empty,full,:semaphore:=,1,n,0;,11/19/2026,6,山东农业大学计算机系,producer:,repeat,produce an item in,nexp,;,buffer(in,):=,nexp,;,in:=(in+1)mod n;,until false;,wait(mutex,);,signal(mutex,);,wait(empty,);,signal(full,);,11/19/2026,7,山东农业大学计算机系,consumer:,repeat,nextc,:=,buffer(out,);,out:=(out+1)mod n;,consume the item in,nexc,;,until false;,wait(mutex,);,signal(mutex,);,wait(full,);,signal(empty,);,11/19/2026,8,山东农业大学计算机系,检查:,每个程序中用于实现互斥的,wait(mutex,),和,signal(mutex,),必须,成对,地出现。,控制顺序的信号量,empty,和,full,的,wait,和,signal,操作,,成对地出现在不同的进程,中。,在每个程序中的,多个,wait,操作顺序不能颠倒,。且应,先执行对资源信号量的,wait,操作,再执行对互斥信号量的,wait,操作,,否则可能引起进程死锁。,模拟交替,执行过程,检查控制是否正确。,11/19/2026,9,山东农业大学计算机系,模拟交叉运行,1,)两个生产者同时的情况,假设的时间片轮转顺序如下,produce;,produce;,wait(e,);,wait(m,);,buffer(in,):=,nexp,;,wait(e,);,wait(m,);,buffer(in,):=,nexp,;,in:=(in+1)mod n;,signal(m,);,signal(f,);,in:=(in+1)mod n;,signal(m,);,signal(f,);,1,号生产者的,wait,操作使,e=n-1,,,m=0,当,1,号正在,in=0,的,buffer0,放入产品时,,2,号来到,,wait,(,e,)仍通过,,e=n-2,;但,wait,(,m,)会使,2,号阻塞。,m=-1,,,e=n-2,。,转入,1,号生产者执行使,in=1,,唤醒,m,上的等待者,2,号生产者,但可能并不立即切换到,2,号运行,而是其分到的,cpu,时间完成后再转到,2,号。此时,m=0,,,f=1,。,回到,2,号进程后,将产品放入缓冲区;,in=2,;,m=1,;,f=2,。,11/19/2026,10,山东农业大学计算机系,2,)生产者等待消费者情况,设当前运行到一个临界点,缓冲区满了,而,生产者先来了,要生产。,e=0,;,m=1,;,f=n,假设的时间片轮转顺序如下,produce;,wait(e,);,wait(m,);,buffer(in,):=,nexp,;,wait(f,);,wait(m,);,nextc,:=,buffer(out,);,in:=(in+1)mod n;,signal(m,);,signal(f,);,out:=(out+1)mod n;,signal(m,);,signal(e,);,consume;,终于,消费者来了,e=1,f=n-1,11/19/2026,11,山东农业大学计算机系,*,AND,信号量的方式,consumer:,repeat,nextc,:=,buffer(out,);,out:=(out+1)mod n;,consume the item in,nexc,;,until false;,Swait(full,mutex,);,Ssignal(mutex,empty);,11/19/2026,12,山东农业大学计算机系,2.,哲学家进餐,问题,五个哲学家共用一张圆桌,分别坐在周围的五张椅子上,在桌子上有五只碗和五只筷子,他们的生活方式是交替地进行思考和进餐。平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能进餐。进餐毕,放下筷子继续思考。,5,4,1,2,3,可见:,相邻两位不能同时进餐;最多只能有两人同时进餐。,11/19/2026,13,山东农业大学计算机系,1,),记录型信号量解决哲学家进餐问题,筷子是临界资源,,在一段时间内只允许一个哲学家使用。为实现对筷子的互斥使用,用一个信号量表示一只筷子,五个信号量构成信号量数组。,Var,chopstick:array 0,4 of semaphore;,所有信号量均被初始化为,1,。,11/19/2026,14,山东农业大学计算机系,第,i,位哲学家的活动可描述为:,repeat,wait(chopstick,i);,wait(chopstick,(i+1)mod 5);,eat;,signal(chopstick,i);,signal(chopstick,(i+1)mod 5);,think;,until false;,当哲学家饥饿时,总是先拿左边的筷子,再拿右边的筷子。,当哲学家进餐毕,先放下左边的筷子,再放下右边的筷子。,11/19/2026,15,山东农业大学计算机系,2,)就餐死锁问题,假如五位哲学家同时饥饿而各自拿起左边的筷子时,就会使五个信号量,chopstick,均为,0,,当他们再试图去拿右边的筷子时,都将因无筷子可拿而无限等待。,11/19/2026,16,山东农业大学计算机系,解决方法:,数量控制:,至多只允许有四位哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够进餐,并在用毕后释放出他用过的两只筷子,从而使更多的哲学家能够进餐。,-,限制并发执行的进程数,抛砖引玉,:,一个房间,只允许进入,6,个人,如何用信号量进行控制?,11/19/2026,17,山东农业大学计算机系,一刀切:,仅当哲学家的左右两只筷子均可用时,才允许他拿起筷子进餐。,-,采用,AND,信号量。,11/19/2026,18,山东农业大学计算机系,在,哲学家进餐问题中,要求每个哲学家先获得两个临界资源,(,筷子,),后方能进餐。,Var,chopstick:array 0,4 of semaphore:=(1,1,1,1,1);,Process i,repeat,think;,S,wait(chopstick,(i+1)mod 5,chopstick i );,eat;,Ssignal(chopstick,(i+1)mod 5,chopstick i );,until false;,11/19/2026,19,山东农业大学计算机系,IF,编程控制,规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子;偶数号哲学家则相反。保证总会有一个哲学家能同时获得两只筷子而进餐,if I mod 2=0,else,11/19/2026,20,山东农业大学计算机系,3.,读者,写者,问题,一个数据文件被多个进程共享。,Reader,进程只要求读文件,,Writer,进程要求写入内容。,合理的同步关系是:,多个读进程可同时读;,Writer,进程与任何其他进程(包括,Reader,进程或其他,Writer,进程)不允许同时访问文件。,11/19/2026,21,山东农业大学计算机系,*解决思路*,如何设置互斥信号量?,所有进程都对一个互斥信号量,m,进行操作?,不符合读者之间不需要互斥的要求。,Writer:,repeat,w,ait(wmutex,);,写入文件;,signal(wmutex,);,until false;,Reader:,repeat,w,ait(wmutex,);,读文件;,signal(wmutex,);,until false;,11/19/2026,22,山东农业大学计算机系,写者操作要和其他的都互斥,所以必要判断互斥信号量,,没有变化:,只有第一个读进程进行互斥判断;,只要有一个“,读进程”在读就不释放,“写进程”就不能写。,(一种读者优先的方式),Writer:,repeat,w,ait(wmutex,);,写入文件;,signal(wmutex,);,until false;,11/19/2026,23,山东农业大学计算机系,读者,Reader:,begin,repeat,if,Readcount,=0 then,Readcount,:=,Readcount,+1;,perform read operation;,Readcount,:=,Readcount,-1;,if,Readcount,=0 then,until false;,end,w,ait(rmutex,);,signal(rmutex,);,wait(wmutex,);,w,ait(rmutex,);,signal(rmutex,);,signal(wmutex,);,防止写进程再进入,但不影响其他读进程,解决读者问题的关键:除第,1,读者,其他读者不申请读写互斥信号量,防止读者间互斥。,11/19/2026,24,山东农业大学计算机系,类似问题,单行问题,同向不互斥,异向互斥,船闸问题,同闸航道不互斥,不同闸的互斥,11/19/2026,25,山东农业大学计算机系,*利用信号量集机制解决,读者,写者,问题,引入信号量,L,控制读者的数目,初值为,RN,。,互斥信号量,mx,,初值为,1,。,利用信号量集的一种特殊情况,开关。,读者:判断,L,,判断是否有写者;,写者:判断是否有读者;,reader:,repeat,Swait(L,1,1);,读操作,;,Ssignal(L,1);,until false;,writer:,repeat,Swait(mx,1,1;,写操作,;,Ssignal(mx,1);,until false;,L,RN,0);,Swait(mx,1,0);,数量变化在对方身上,所以说开关由对方掌握。,为什么用记录集?,分成两句试试看有什么错误,11/19/2026,26,山东农业大学计算机系,对生产者消费者问题进行交叉运行分析,给出以下情况的过程分析,各情况下的变量值酌情设置。,生产者同时来,消费者同时来,生产者等待消费者的情况,消费者等待生产者的情况,根据哲学家就餐死锁问题的三种解决办法,给出修改后的三种哲学家进程代码。,为什么我们说课本上给出的读者写者问题的解决办法是读者优先的?,作业,11/19/2026,27,山东农业大学计算机系,
展开阅读全文