版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
操作系统第五次作业6.1第一种出名的对的解决两个进程的临界区问题的软件办法是Dekker设计的。两个进程P0和P1共享下列变量:
booleanflag[2];
/*initiallyfalse*/
intturn;进程Pi(i==0或1)的构造见图6.25,另一种进程是Pj(j==0或1)。试证明这个算法满足临界区问题的全部三个规定。答:临界区的问题的解答必须满足下列三个条件:1)
互斥:如果进程Pi在其临界区内执行,那么其它进程都不能在其临界区内执行。2)
有空让进:如果没有进程在其临界区内执行且有进程需进入临界区,那么只有那些不在剩余区内执行的进程可参加选择,以拟定谁能下一种进入临界区,且这种选择不能无限推迟。3)
有限等待:从一种进程做出进入其临界区的请求,直到该请求允许为止,其它进程被允许进入其临界区的次数有上限。为了表述方便,接下来用0,1来替代i,j;首先两个进程共享下列变量:
booleanflag[2];
/*initiallyfalse*/
intturn;flag用来统计谁要访问临界区,就让对应的flag=true(例如P0要访问临界区,就让flag[0]=true),相称于“举手示意我要访问”。初始值为0表达一开始没人要访问。trun用于标记现在允许谁进入,turn=0则P0可进入,turn=1则P1可进入。接下来看进程P0的逻辑do{flag[0]=true;
//首先P0举手示意我要访问while(flag[1]){
//看看P1与否也举手了if(turn==1){
//如果P1也举手了,那么就看看终究轮到谁flag[0]=false;
//如果确实轮到P1,那么P0先把手放下(让P1先)while(turn==1);//donothing
//只要还是P1的时间,P0就不举手,始终等flag[0]=true;
//等到P1用完了(轮到P0了),P0再举手}}//Criticalsection
//访问临界区turn=1;
//P0访问完了,把轮次交给P1,让P1能够访问flag[0]=false;
//P0放下手//remaindersection
//剩余区}while(1);P1的逻辑和P0相似:do{flag[1]=true;
//首先P1举手示意我要访问while(flag[0]){
//看看P0与否也举手了if(turn==0){
//如果P0也举手了,那么就看看终究轮到谁flag[1]=false;
//如果确实轮到P0,那么P1先把手放下(让P0先)while(turn==0);//donothing
//只要还是P0的时间,P1就不举手,始终等flag[1]=true;
//等到P0用完了(轮到P1了),P1再举手}}//Criticalsection
//访问临界区turn=0;
//P1访问完了,把轮次交给P0,让P0能够访问flag[1]=false;
//P1放下手//remaindersection
//剩余区}while(1);为了证明第一点,要注意到只有当flag[0]=true并且turn==0的时候,进程P0才会进入临界区。而当flag[0]=true,flag[1]=true表达P0和P1都想进入临界区的时候,P0和P1谁能进入临界区取决于turn的值,当turn==0时,P0能够进入,当turn=1时,P1能够进入;turn的值只可能是0或1,而不可能同时为两个值,因此一次只能有一种进程在临界区内,满足互斥的条件。为了证明第二点和第三点,应注意到,只要条件flag[1]=true,turn==1成立,flag[0]的值就会被设立成false,并且P0陷入while循环语句,那么P0就能被制止进入临界区。如果P1不准备进入临界区(flag[1]=false)或者没有轮到P1进入临界区(turn==0),那么P0就能进入临界区。当P1退出临界区的时候,它会设立flag[0]=true,以允许P0进入临界区。当P0访问完之后退出临界区,它会设立turn==1和flag[0]=false,表达P0访问完了,把轮次交给P1,让P1能够访问,因此P1会进入临界区,满足迈进的条件;同时P1最多在P0进入临界区一次之后就能进入,满足有限等待的条件。总而言之,Dekker算法是满足临界区问题的全部三个规定的。6.4请解释为什么自旋锁不合用于单解决器系统中,而是往往使用于多解决器系统中?自旋锁是专为避免多解决器并发而引入的一种锁,它在内核中大量应用于中断解决等部分(对于单解决器来说,避免中断解决中的并发可简朴采用关闭中断的方式,即在标志寄存器中关闭/打开中断标志位,不需要自旋锁)。在单解决机环境中能够使用硬件提供的swap指令或test_and_set指令实现进程互斥,(Swap指令:交换两个内存单元的内容;test_and_set指令取出内存某一单元(位)的值,然后再给该单元(位)赋一种新值,有关为什么这两条指令能实现互斥我们不在赘述,读者能够理解其算法)这些指令涉及对同一存储单元的两次或两次以上操作,这些操作将在几个指令周期内完毕,但由于中断只能发生在两条机器指令之间,而同一指令内的多个指令周期不可中断,从而确保swap指令或test_and_set指令的执行不会交叉进行.但在多解决机环境中状况有所不同,例如test_and_set指令涉及“取”、“送”两个指令周期,两个CPU执行test_and_set(lock)可能发生指令周期上的交叉,如果lock初始为0,CPU1和CPU2可能分别执行完前一种指令周期并通过检测(均为0),然后分别执行后一种指令周期将lock设立为1,成果都取回0作为判断临界区空闲的根据,从而不能实现互斥.如图4-3所示.为在多CPU环境中运用test_and_set指令实现进程互斥,硬件需要提供进一步的支持,以确保test_and_set指令执行的原子性.这种支持现在多以“锁总线”(buslocking)的形式提供的,由于test_and_set指令对内存的两次操作都需要通过总线,在执行test_and_set指令之前锁住总线,在执行test_and_set指令后开放总线,即可确保test_and_set指令执行的原子性。6.7描述如何用swap()指令来实现互斥并满足有限等待规定运用Swap指令实现进程互斥的算法描述以下:do{waiting[i]=TRUE;key=TRUE;while(waiting[i]&&key)//进程排队Swap(&lock,&key);waiting[i]=FALSE;//进程标注自己已进入临界区//临界区j=(i+1)%n;while((j!=i)&&!waiting[j])j=(j+1)%n;if(j==i)//现在无其它进程排队则释放锁lock=FALSE;elsewaiting[j]=FALSE;//强制拉取后一种进程进入临界区//剩余区}while(TRUE);能够看出,剩余区前的while循环确保一种进程Pi强制拉取了排在其后的进程Pj进入临界区(如果有的话),这确保了有限等待。使用到的共享数据有:booleanwaiting[n]:waiting[i]==TRUE表明进程i已申请进入临界区并正在等待选择。booleanlock:lock是进程间共享的锁。6.11剪发店问题。一家剪发店有一间有n把椅子的等待室和一间有一把剪发椅的剪发室。如果没有顾客,剪发师就去睡觉。如果顾客来时全部的椅子都有人,那么顾客将会拜别。如果剪发师在忙,而又有空闲的椅子,那么顾客会坐在其中一种空闲的椅子上。如果剪发师在睡觉,顾客会摇醒他。编写一种程序来协调剪发师和顾客。答:设计程序以下所示:剪发师进程和顾客进程共享下列数据构造:Semaphoremutex,barber,cutomers;int
waiting;其中barber()表达剪发师程序,customer()表达顾客程序,椅子数量为n;信号量mutex提供了进程之间的互斥规定,并初始化为1;waiting表达正在等待的顾客数量;cut-hair表达正在剪发;get-haircut表达准备剪发。barber(){
while(TRUE);//理完一位顾客,尚有顾客么?
P(cutomers);//如果没有顾客,剪发师睡觉
P(mutex);
//进程互斥
Waiting-=1;//等待顾客数少一种
V(barber);
//剪发师去为一种顾客剪发
V(mutex);
//开放临界区
cut-hair();//正在剪发}Customers;(){
P(mutex);
//进程互斥
if(waiting<n){
waiting+=1;
//等待顾客
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 建筑施工用电安全合同
- IT企业会计岗位合同
- 游乐园钢结构安装施工合同
- 押运员安全意识教育
- 商业大厦改造施工合同
- 广州医疗机构租房合同
- 大连市茶楼租赁合同
- 剧院空调系统工程合同
- 保健品公司财务主管招聘合同
- 文化遗址二手房交易合同范本
- 急性会厌炎护理查房
- 大学生面试全指导课件
- (完整版)俄语动词命令式的构成及用法
- 加油站有限空间安全管理制度规范
- GB/Z 43281-2023即时检验(POCT)设备监督员和操作员指南
- 建筑工地的消防风险分析
- 农村原民办代课教师教龄补助申请表
- 四川省凉山州西昌市2024届九年级物理第一学期期中检测试题含解析
- 江苏开放大学2023年秋《公共关系原理与实务050010》过程性考核作业一参考答案
- 学校消防安全培训课件(ppt37张)
- 广联达BIM土建计量平台GTJ2021使用手册
评论
0/150
提交评论